基于TinyOS的無線傳感器網絡LEACH算法的改進

朱　明，劉漫丹

(華東理工大學 信息科學與工程學院，上海 200237)

?

基于TinyOS的無線傳感器網絡LEACH算法的改進

朱明，劉漫丹

(華東理工大學 信息科學與工程學院，上海 200237)

LEACH協議是無線傳感器網絡中最流行的分簇路由協議之一。針對LEACH算法簇分布不均勻以及網絡能耗不均衡等問題提出了一種高效節能多跳路由算法。在簇建立階段，新算法根據網絡模型計算出最優簇頭間距值，調整節點通信半徑以控制簇的大小，形成合理網絡拓撲結構；在數據傳輸階段，簇頭與基站之間采用多跳的通信方式，降低了節點能耗。在TinyOS操作系統下，使用nesC語言設計實現了LEACH-EEMH算法。基于TOSSIM平臺的仿真結果表明，新算法較LEACH算法在均衡網絡能耗、延長網絡壽命方面具有顯著優勢。

TinyOS系統；無線傳感器網絡；路由協議；高效節能

無線傳感器網絡(Wireless Sensor Networks，WSN)由大量的小型傳感器節點組成，它可以實時地收集和處理各種環境和對象的信息，并通過衛星或互聯網將其發送到用戶終端[1]。它使得人們能夠在任何時間、地點和環境下實現對物理世界的動態、智能、泛在的感知[2]。

由于節點電池能源有限，計算及存儲能力弱，它們的操作系統需具備耗能少且可以適應各類應用環境的特點，TinyOS[3]正是具備了上述特點的WSN操作系統。TinyOS采用組件層次結構，是一個基于事件的系統，現階段大部分無線傳感器網絡研究項目都采用TinyOS操作系統，TinyOS已成為WSN研究領域上的標準平臺。

WSN路由協議決定了網絡的運行效率和執行能力，由于網絡資源受限，WSN路由協議算法的研究核心便是降低傳感器網絡的能耗，提高資源利用率，延長網絡壽命[4]。WSN路由協議根據網絡結構可分為平面路由協議和分簇路由協議兩種類型。平面路由協議網絡中各節點功能相同，算法簡單，容易實現，但是網絡的可擴展性小，應用范圍較窄。常見的平面路由協議有SPIN[5]、Flooding Protocol[6]、Directed Diffusion[7]等。分簇路由協議將網絡劃分為“簇”，每個簇由一個簇頭和多個成員節點構成，相比平面路由協議有較好的可擴展性，應用范圍廣。常見的分簇路由協議有LEACH[8]、TEEN[9]、PEGASIS[10]等。

LEACH(Low Energy Adaptive Clustering Hierarchy)是WSN中具有代表性的分簇路由算法，具有低功耗自適應的特點，LEACH的循環周期使用了“輪”的概念，一輪包括簇建立和數據傳輸階段兩個部分。簇建立階段，各節點隨機生成一個0～1間的數，若該數小于閾值Tn，則此節點成為簇頭，同時廣播成為簇頭的信息。非簇頭節點根據收到簇頭廣播消息，選擇加入離自己最近的簇頭成簇。數據傳輸階段，簇成員節點將其監測到的數據發送給簇頭節點；簇頭進行數據融合處理，然后以單跳的方式將數據發送給基站。Tn計算式如

(1)

式中：p是期望的簇頭數占網絡中總節點數的比例；r是當前輪數；每1/p輪為一個周期，G是最近一個周期內沒有成為簇頭的節點集合。

LEACH提出了一種簇頭輪流當選的機制，初步解決了負載平衡的問題，且采用分布式算法，容易實現，但還是存在一些問題。例如LEACH采用隨機選擇簇頭的方式，不能保證簇的均勻分布，致使簇頭的能耗不均衡，網絡壽命縮短；且簇頭與基站采用單跳通信的方式限制了網絡的規模。LEACH-C[11]是LEACH的改進算法，采用集中式的分簇算法選出較優的簇頭，使簇分布更加合理；但簇間采用單跳通信，傳輸距離過遠仍會產生大量能耗。

本文針對LEACH算法的不足提出了一種基于簇分布的高效節能多跳路由算法——LEACH-EEMH(EnergyEfficientMulti-Hop)。

1　LEACH-EEMH算法

1.1LEACH-EEMH算法的設計思想

LEACH-EEMH算法的設計思想主要體現在以下幾個方面：

1)根據網絡能耗最小的原則計算出簇頭節點之間最優的間距值，在這個條件的約束獲得合理的簇分布，使簇較為均勻地分布在網絡中；2)簇頭選舉首先考慮節點的能量水平，能量多的節點當選本輪簇頭；3)為避免頻繁的全網動態分簇造成大量能量開銷，只在每個周期的首輪進行整個網絡的動態分簇，其余時間則采用簇內獨立的簇頭輪換機制；4)簇頭節點和基站之間采用多跳的方式進行通信，以減少網絡能耗，延長網絡壽命。

1.2能耗模型

LEACH-EEMH算法的能量模型與LEACH相同，采用一階無線電能耗模型，節點發送kbit的數據到距離d的位置，根據該模型耗能為

(2)

式中：Eelec表示發送或接收1bit數據消耗的能量；εfs和εmp分別表示自由空間模型和多路衰減模型下的功率放大損耗常數。在傳輸距離小于閾值d0時，功率放大損耗采用自由空間模型，傳輸距離大于d0時，采用多路衰減模型。節點接收和融合數據k(單位bit)消耗的能量分別為

Erx(k,d)=kEelec

(3)

Efusion(k,d)=kEDA

(4)

式中：EDA是融合1bit數據消耗的能量。

1.3最優簇頭間距值求取

簇頭節點之間最優的間距值是根據最優簇頭數計算得到，下面首先計算最優簇頭節點的個數。

假設在M×M的監測區域內隨機分布著n個節點，若有k個簇，那么每個簇內平均有n/k個節點。簇頭節點的能耗主要包括接收成員節點監測到的數據、簇內數據融合、將整個簇的數據傳輸到基站這3個部分。由于簇頭遠離基站，能量損耗可采用多路衰減模型，單個簇頭節點的能耗為

(5)

式中：l是數據包大小；dtoBS是簇頭到基站的距離。

簇成員節點的能耗主要是將監測到的數據發送給簇頭。簇頭與成員節點之間的距離較近，采用自由空間模型，單個成員節點的能耗為

(6)

式中：dtoCH是成員節點到簇頭的距離。

簇可以看做是以簇頭為圓心的圓形區域，每個簇所覆蓋的面積平均為M2/k，其成員節點到簇頭距離的平方的期望值為

(7)

此時成員節點的能耗為

(8)

每個簇的能耗為

(9)

全網的能耗為

(10)

式中：DtoBS表示基站到網絡區域中心的距離。

令Etotal的一階導數為零，可得使Etotal值最小的k值為

(11)

網絡運行中不斷會有節點因能量耗盡而死亡，因此kopt的值是變化的。

kopt個簇要覆蓋整個面積為M×M的正方形區域，簇頭均勻分布，理想的網絡拓撲結構如圖1所示，以簇頭為圓心的圓半徑為R，整個監測區域由kopt個小正方形所覆蓋，那么

(12)

簇的半徑R為

(13)

可得簇頭間最小間距D的值為

(14)

由式(14)可知，D會隨著kopt的變化而變化。LEACH-EEMH算法中基站每個周期(1/ p 輪)重新計算D值，然后向全網廣播該值。

圖1　理想的網絡拓撲結構

1.4LEACH-EEMH算法的流程

LEACH-EEMH以輪為周期，每輪分為簇建立、簇間路由建立以及數據傳輸3個階段，數據傳輸階段與LEACH算法相同，這里詳細介紹前兩個階段。

1.4.1簇建立階段

簇建立階段分為每周期首輪簇建立和非首輪簇建立兩種情況。

1) 情況一

每周期首輪簇建立階段，在簇頭選舉之前，節點根據自己的能量水平確定一個定時時間，能量大的節點比能量小的節點時間短。

簇頭選舉工作開始，全網同時進入定時時間的倒計時，能量最大的節點倒計時首先結束，當選第一個簇頭。該節點以D為通信半徑廣播簇頭消息，然后增大通信半徑向基站發送一條簇頭消息。

在定時時間內，若某個節點收到了簇頭的廣播消息，則立即結束倒計時，放棄成為簇頭節點。直到倒計時結束仍然沒有收到簇頭廣播消息的節點，宣布自己成為簇頭。

如果基站收到的簇頭消息達到了最佳簇頭數目，則停止選舉簇頭的操作。

簇頭選舉結束，簇頭節點增大通信半徑廣播簇頭消息。非簇頭節點選擇距離最近的簇頭節點作為自己的簇頭，加入該簇并向簇頭節點發送入簇消息，至此每周期的首輪簇建立階段完成。

2) 情況二

非首輪簇建立階段不進行全網簇重組，當前輪的簇頭由上一輪的簇頭節點指定；上一輪的簇頭節點在數據傳輸的最后階段選擇簇內能量最大的節點作為下一輪簇頭，新簇頭廣播成為簇頭的消息，非簇頭節點入簇。

1.4.2簇間路徑建立階段

每個簇頭節點都維護著一個路由表Troute，它是根據其接收的簇頭廣播消息建立的。當簇頭i收到簇頭j的廣播消息時，比較兩簇頭到基站的距離值dtoBS。若j的dtoBS值小于i的dtoBS值，將簇頭j加入到i的Troute中，反之則不加入。若簇頭i的dtoBS值不大于d0或其Troute為空，則選擇基站作為下一跳節點。 反之，簇頭i從其Troute中選擇距離最近的簇頭節點作為下一跳節點。

2　LEACH-EEMH協議實現

2.1總體框架

本文采用TinyOS 2.1操作系統和nesC語言實現LEACH-EEMH協議。圖2是LEACH-EEMH協議的結構框圖，其中實線框表示模塊，每個模塊實現一種功能；虛線框表示配件，它表示模塊的連接關系；箭頭代表接口。箭頭上方是上層組件，箭頭下方是下層組件，上層組件通過接口調用下層組件的功能，下層組件通過接口向上層組件觸發事件。LEACH-EEMH協議采用單配件多模塊的程序模型，整個協議在一個配件LeacheemhC里實現。配件內包含LeacheemhP，ClusterFormP和ClusterMultiRouteP共3個模塊。除此之外還包括TinyOS系統自帶的TimerMilliC，AMSenderC，AMReciverC，ActiveMessageC和RandomC等組件。路由層的功能對于上層應用來說是不透明的，LeacheemhC組件為上層提供了與數據傳輸有關的StdControl，AMSend和Receive接口，接口的相關函數在LeacheemhP模塊里實現。

圖2　LEACH-EEMH結構框圖

2.2主要功能模塊

LEACH-EEMH算法的主要功能模塊是LeacheemhP,ClusterFormP和ClusterMultiRouteP模塊，其中LeacheemhP模塊是其他兩個模塊的管理者，對外界提供開放的功能接口。ClusterFormP是簇建立模塊，ClusterMultiRouteP是簇間多跳路徑建立模塊。

1)LeacheemhP模塊

LeacheemhP是LEACH-EEMH協議的核心處理模塊。LeacheemhP模塊通過調用AMControl接口控制無線通信模塊ActiveMessageC的開啟與關閉，調用CFControl接口控制ClusterFormP模塊完成簇的建立，調用CMRControl接口控制ClusterMultiRouteP模塊建立簇間多跳路徑。簇間多跳路徑建立完成后，LeacheemhP向上觸發RouteFormDone事件，開始數據傳輸。LeacheemhP模塊向上層提供了StdControl和AMSend和Receive接口。StdControl是標準控制接口，能夠控制路由層功能的開啟和關閉。AMSend是主動消息發送接口，AMSend在其發送命令里指定了AM目標地址，它的實質是經過路由層的多跳傳輸后到達該目標，LEACH-EEMH協議的目標地址是基站。Receive是消息接收接口，提供了接收到消息時觸發的事件函數，當基站接收到消息包時會觸發Receive接口的事件。

2)ClusterFormP模塊

ClusterFormP是簇建立模塊，負責完成簇頭的選舉、簇的形成和維護等工作。向上層提供了CFControl接口，用于控制簇建立的開始與結束，獲得簇的信息等。ClusterFormP模塊調用AMSenderC組件的AMSend接口和AMReceiveC組件的Receive接口完成簇內路由和數據消息包的發送與接收，調用TimerMilliC組件的Timer接口完成與定時器有關的操作，調用RandomC組件的Random接口獲得簇頭選舉時需要的隨機數。

3)ClusterMultiRouteP模塊

ClusterMultiRouteP是簇間多跳路徑建立模塊，負責建立簇頭與匯聚節點之間的多跳路徑，完成路由的選擇工作。向上層提供了CMRControl接口，用于控制簇間多跳路徑建立的開始與結束，獲得路由信息等。ClusterMultiRouteP模塊調用AMSenderC組件的AMSend接口和AMReceiveC組件的Receive接口來完成簇間路由和數據消息包的發送與接收，調用TimerMilliC組件的Timer接口完成一系列與定時器有關的操作。

3　仿真結果與分析

3.1參數設置

本文選用TinyOS操作系統自帶的仿真工具TOSSIM(TinyOS simulator)[12]對LEACH-EEMH算法進行仿真，TOSSIM可以支持大規模的網絡仿真。100個節點隨機分布在100 m×100 m區域內，基站的坐標為(50，175)，其他參數如表1所示。

表1仿真參數

參數含義參數值Einit節點初始能量2JEelec單位數據發送/接收能耗50nJ/bitεfs自由空間系數10(pJ·bit-1·m-2)εmp多路衰減系數0.0013(pJ·bit-1·m-4)EDA簇頭數據融合能耗5nJ/bitd0信道模型距離閾值87mpdata數據包長度4000bit

3.2結果與分析

本文采用網絡生存時間和負載平衡程度這兩個性能評價指標，對比LEACH-EEMH，LEACH-C和LEACH算法，仿真結果如圖3、圖4所示。

圖3　網絡生存時間仿真結果

圖4　網絡負載平衡因子仿真結果

由圖3可知， LEACH算法第一個節點死亡的時間約是240輪，最后一個節點死亡的時間約為510輪；LEACH-C算法第一個節點死亡的時間約是290輪，最后一個節點死亡的時間約為560輪；LEACH-EEMH算法第一個節點死亡的時間約是300輪，最后一個節點死亡的時間約為610輪。經計算得到，LEACH-C第一個節點死亡時間比LEACH延長了21%，網絡生存時間比LEACH延長了9.8%；而LEACH-EEMH的一個節點死亡時間比LEACH延長了25%，網絡生存時間比LEACH延長了20%。LEACH-EEMH算法的網絡生存周期明顯高于LEACH和LEACH-C算法，因此LEACH-EEMH算法在減少網絡能耗，延長網絡生存時間方面具有較好的性能。

圖4對比了3種算法的負載平衡程度，負載平衡因子越大，網絡的負載平衡度越好，網絡壽命越長。從圖4可知，LEACH的負載平衡因子最大值約為0.023 5，最小值約為0.012 5；LEACH-C的負載平衡因子最大值約為0.025 5，最小值約為0.019 5；LEACH-EEMH的負載平衡因子最大值約為0.028 0，最小值約為0.022 5，且波動較小。表明LEACH-EEMH在平衡網絡負載方面具有較好的性能，這是因為LEACH-EEMH算法的簇頭數量最優，且設置了簇頭的最小間距使簇頭分布較為均勻，更好地均衡了網絡負載。

4　結論

本文選取經典的LEACH路由算法作為研究原型，針對其不足提出了LEACH-EEMH算法，并將該算法在TinyOS操作系統上實現。TOSSIM仿真結果表明LEACH-EEMH算法能有效節省能量，均衡網絡負載，延長網絡生存周期。但LEACH-EEMH算法也有不足之處，該協議在設計時著重考慮能耗問題，忽略了時延、丟包率、安全因素等情況，今后還需對此做進一步的研究。

[1]YICK J，MUKHERJEE B，GHOSAL D. Wireless sensor network survey[J]. Computer networks，2008，52(12)：2292-2330.

[2]孫利民.無線傳感器網絡[M].北京：清華大學出版社有限公司，2005.

[3]LEVIS P，MADDEN S，POLASTRE J，et al. TinyOS：an operating system for sensor networks[M]. Ambient intelligence：Springer Berlin Heidelberg，2005.

[4]XIANGNING F，YULIN S. Improvement on LEACH protocol of wireless sensor network[C]// International Conference on Sensor Technologies and Applications. [S.l.]：IEEE，2007：260-264.

[5]KULIK J，HEINZELMAN W，BALAKRISHNAN H. Negotiation-based protocols for disseminating information in wireless sensor networks[J].Wireless networks，2002，8(2/3)：169-185.

[6]FARIVAR R，FAZELI M，MIREMADI S G. Directed flooding：a fault-tolerant routing protocol for wireless sensor networks[C]// Proceedings of Systems communications. [S.l.]：IEEE，2005：395-399.

[7]INTANAGONWIWAT C，GOVINDAN R，ESTRIN D，et al. Directed diffusion for wireless sensor networking[J]. IEEE/ACM transactions on networking，2003，11(1)：2-16.

[8]鄒虹，彭國龍.一種基于 LEACH 改進的均勻分簇路由算法[J].電視技術，2013，37(3)：133-136.

[9]MANJESHWAR A，AGRAWAL D. TEEN：a protocol for enhanced efficiency in WSNs[C]//Proc. the First International Workshop on Parallel and Distributed Computing Issues in Wireless Networks and Mobile Computing. [S.l.]：IEEE，2001：2009-2015.

[10]JUNG S M，HAN Y J，CHUNG T M. The concentric clustering scheme for efficient energy consumption in the PEGASIS[C]// Proc. the 9th International Conference on Advanced Communication Technology. [S.l.]：IEEE，2007：260-265.

[11]HEINZELMAN W B，CHANDRAKASAN A P，BALAKRISHNAN H. An application-specific protocol architecture for wireless microsensor networks[J]. IEEE transactions on wireless communications，2002，1(4)：660-670.

[12]LEVIS P，LEE N，WELSH M，et al. TOSSIM：accurate and scalable simulation of entire TinyOS applications[C]//Proceedings of the 1st international conference on Embedded networked sensor systems. [S.l.]：ACM，2003：126-137.

朱明(1990— )，女，碩士生，主研無線傳感器網絡；

劉漫丹(1973— )，女，教授，博士生導師，主要研究方向為無線傳感器網絡、智能優化計算等。

責任編輯：許盈

Improvement of LEACH algorithm based on TinyOS for wireless sensor network

ZHU Ming, LIU Mandan

(SchoolofInformationScienceandEngineering,EastChinaUniversityofScienceandTechnology,Shanghai200237,China)

LEACH protocol is one of the most popular clustering routing protocols in wireless sensor networks. To deal with the unbalanced clustering and energy consumption problems exist of LEACH algorithm, an energy efficient multi-hop routing algorithm is proposed. In the clustering stage, the new algorithm calculates the optimal cluster head distance value, adjust the node communication radius to control the size of the cluster, thus forming a reasonable network topology structure. In the stage of data stable transmission, a multi-hop communication mode is adopted between the cluster head and the base station to reduce the energy cost. Based on TinyOS system, LEACH-EEMH is designed and realized with the language nesC. Simulations in TOSSIM platform reveal that, in contrast with LEACH, the new algorithm has obvious advantages in balancing the network energy consumption and prolonging the network lifetime.

TinyOS system; wireless sensor network; routing protocol; energy efficient

TP393

ADOI：10.16280/j.videoe.2016.10.015

中央高校基本科研業務費專項(WH1213010)

2015-12-31

文獻引用格式：朱明，劉漫丹. 基于TinyOS的無線傳感器網絡LEACH算法的改進[J].電視技術，2016，40(10)：71-76.

ZHU M，LIU M D. Improvement of LEACH algorithm based on TinyOS for wireless sensor network[J].Video engineering，2016，40(10)：71-76.