一種基于ＬＥＡＣＨ的改進型無線傳感器網絡路由算法
2009-03-19 01:59:12閆仁強田華
現代電子技術 2009年3期
閆仁強 田 華
摘 要：路由算法是無線傳感器網絡研究的核心技術之一。在LEACH算法的基礎上，提出了一種基于距離和能量考慮選擇第二層簇頭的兩層LEACH算法DE-LEACH，有效避免了低能量且離基站較遠的節點與基站直接通信，提高了網絡生存時間和數據采集能力。利用事件驅動的方法，減少了發送數據量，進一步延長了網絡生存期。
關鍵詞：路由算法；第二層簇頭選擇；網絡生存時間；數據采集能力；數據融合；事件驅動
中圖分類號：TN915文獻標識碼：B
文章編號：1004-373X(2009)03-036-05
Improved Wireless Sensor Network Routing Algorithm Based on LEACH
YAN Renqiang,TIAN Hua
(Institute of Communication and Engineering,PLA University of Science & Technology,Nanjing,210007,China)
Abstract：Routing algorithm is one of the key technologies of wireless sensor network.Based on the LEACH algorithm.A two-layer algorithm called DE-LEACH is proposed,it takes the cluster-head′s residual energy and distance to BS into account,and then chooses a senior cluster-head.The new algorithm avoids direct communication between BS and the cluster-head which has low energy and far away from BS,thus prolongs lifetime of the network,enhances the ability of data collection.Technique of event-driven can cut down the data transmission,further extend the lifetime of network.
Keywords：routing algorithm;selection of senior cluster-head;lifetime of network;ability of data collection;data fusion;event-driven
0 引 言
微電子技術、計算機技術和無線通信等技術的不斷發展，使設計低功耗多功能的無線傳感器成為可能。無線傳感器網絡在監測區域內部署大量的廉價低功耗傳感器節點，其目的是協作的感知、采集和處理網絡覆蓋區域中感知對象的信息，并以無線通信的方式通過多跳自組織網絡發送給遠程基站(BS)。無線傳感器網絡是未來全球的三大高科技產業之一，具有廣闊的應用前景，在軍事國防、災害預警、環境監測、醫療等許多領域都有巨大的應用價值［1,2］。
作為無線傳感器網絡核心技術之一，路由協議的性能在很大程度上決定了網絡的整體性能［3］，因此，路由算法始終是無線傳感器網絡研究的熱點。根據各個節點在網絡中功能的異同，可將路由算法分為平面型和層次型路由。由于平面型路由可擴展性差，且維護動態變化的路由需要大量的控制信息，若部署在人類到達比較困難的地區，維護相對困難。層次型路由算法克服了以上不足，可擴充性好，網絡中控制信息相對較少，得到了廣泛的應用［4］。LEACH［5,6］是第一個基于多簇結構的層次型路由協議，其成簇思想在其后很多協議中都被用到，如TEEN［7］等。
在LEACH算法中，各節點根據簇頭概率p自主決定在該輪是否充當簇頭，一旦成為簇頭便通過廣播告知整個網絡，由于簇頭選擇是完全自主和隨機的，不需要節點間通信協調，因此LEACH算法具有節約能量、實現簡單、可擴展性好等特點，便于部署于人們難以到達區域。但是，隨機簇頭選擇不能保證每輪簇頭節點的數目和分布，易造成網絡內節點能量損耗不均［3］，節點生存期散布較大，到網絡生存期后期會形成監控盲點，影響了網絡的整體性能。
本文在LEACH的基礎上提出了一種兩層簇頭算法DE-LEACH(Distance-Energy LEACH)，第一層簇頭選舉機制與LEACH相同，之后從已選出的簇頭中根據剩余能量大小和距離基站(BS)的遠近折衷考慮選出第二層簇頭。第一層簇頭采集到的數據經過融合處理后發送到第二層簇頭，再由第二層簇頭完成二次融合和將監測數據轉發到基站的工作。由于第二層簇頭選舉機制綜合考慮了節點剩余能量和其到基站的距離，因此避免了剩余能量較少且距基站較遠的第一層簇頭與基站間的直接通信。仿真結果表明，DE-LEACH延長了網絡首節點死亡時間，縮短了首節點死亡到末節點死亡的時間間隔，同時網絡總的數據采集能力得到明顯提高。
1 LEACH算法簡介
LEACH算法引入了輪的概念，每輪簇頭節點進行輪換，以達到分散各節點能量消耗的目的。每一輪包括簇建立和穩定運行兩個階段。為減少管理消耗，穩定運行階段時間要長于簇建立階段［5］。
在簇建立階段，每個節點自主決定是否在本輪充當簇頭，具體的選舉辦法是：由各節點自主生成0~1之間的隨機數，若此隨機數小于某門限T(n)，則此節點在本輪充當簇頭。這種簇頭產生的隨機性保證了簇頭與基站之間較高的通信代價在網內各節點之間得到分攤［8］。
門限T(n)定義為：
T(n)=p1-p×(rmod1p)，n∈G
0，其他(1)
其中：p是網絡中簇頭節點占總節點數的百分比；r是已完成輪數；G是在前1/p輪中沒有充當過簇頭節點的節點集合。舉例來說，第1輪(r=0)，每個節點成為簇頭的概率都是p，第1輪的簇頭在包括此輪之后的1/p輪中都不再充當簇頭節點(即第1~20輪)。此后，由于能夠充當簇頭節點的節點數目變少了，因此每個節點成為簇頭的概率就必須增加以保證每輪簇頭數。1/p-1輪過后，沒當過簇頭的節點充當簇頭的概率都是1，都能夠成為簇頭節點。1/p輪后，所有節點又都可以自主隨機決定是否充當簇頭節點［5］。在文獻［9］中，作者論證了最優簇頭節點百分比為p=5%。
一旦簇頭選定后，簇頭節點會利用CSMA MAC協議對全網所有節點發送廣播數據包，其中包含該節點成為簇頭的信息。根據網絡的對稱性原則，其他節點選擇接收到信號最強的簇頭加入，至此簇建立階段完成。
在穩定運行階段，普通節點利用CSMA MAC協議向其簇頭發送加入數據包。簇頭節點收到加入數據包后，會產生一個TDMA時刻表，為簇內所有節點分配發送時隙，并將此時刻表向各成員廣播。此后，簇頭節點即開始接收各成員采集到的數據，并將其融合后發送到基站。簇頭節點在此階段保持接收機始終處于開機狀態以便接收數據，而普通節點只有在自己發送時打開發射機，其余時刻關閉發射機以節約能量［5］。
相比于平面路由算法，LEACH算法明顯減少了能量消耗，并且將能量耗散分攤到整個網絡，有效延長了網絡生存時間。在文獻［5］中，作者的仿真表明LEACH比平面型的Direct communication協議網絡生存時間提高了約6倍，比層次型固定簇頭協議Static Clusters網絡生存時間提高了約10倍。
然而，完全自主隨機的簇頭選擇不能保證每輪簇頭節點的數目和分布，存在距離基站較遠且能量較少的節點擔當簇頭的可能性，造成網絡內節點能量損耗不均，節點的生存期散布較大，到網絡生存期后期會形成監控盲點，影響了網絡的整體性能。為了改善這種情況，本文提出了基于距離和能量選擇第二層簇頭的兩層LEACH算法DE-LEACH。
2 基于距離能量選擇的兩層LEACH算法DE-LEACH
DE-LEACH算法與LEACH算法一樣，分為簇建立階段與穩定運行階段。
在簇建立階段，首先，各節點仍然利用自身產生的隨機數自主決定是否成為簇頭并通知網絡中所有節點，在此不再贅述。不同之處在于，選出的簇頭節點將自己的剩余能量和到基站的距離加入到廣播數據包中進行廣播。之后，在已選出的第一層簇頭中根據其剩余能量和到基站的距離關系參數Th選出第二層簇頭。
Th定義為：
Th(i)=En(i)Dist(i)
其中i是網絡中節點編號，En(i)是i節點剩余能量，Dist(i)是i節點到基站的距離。
具體的選舉第二層簇頭的策略為：簇頭j將自己的Th(i)值與接收、計算出到的其他簇頭Th值進行比較，若自己最大，則成為第二層簇頭；若比較中發現簇頭i節點的Th(i)值最大，則認為i是第二層簇頭。這里需要注意的是：
(1) 第二層簇頭同時也完成第一層簇頭的廣播、分配時隙、采集數據和融合的工作；
(2) 各個簇頭節點在計算Th值并比較過后，已經能夠確認哪個第一層簇頭節點同時承擔第二層簇頭節點職能，因此第二層簇頭節點不需要再就自己身份進行廣播；又由于各簇頭節點已經收到其他簇頭節點編號，可按編號順序進行數據傳遞，因此第二層簇頭節點不需要為第一層簇頭節點分配時隙而進行廣播；這樣就省去了廣播開銷；
(3) 各個普通節點無需知道誰是第二層簇頭，他們只與第一層簇頭通信，而第二層簇頭同時也承擔第一層簇頭的功能。
在穩定運行階段，普通節點與第一層簇頭通信方式與LEACH相同。但數據采集、融合工作完成之后不是將數據包直接發送到基站，而是依據簇頭節點編號順序分時隙由第一層簇頭發送到第二層簇頭節點。再由第二層簇頭節點進行二次融合后，發送至基站。
LEACH算法假設基站離監控區域較遠，若第一層簇頭節點均與基站直接通信，則通信能量消耗較大，且易造成網絡中各節點剩余能量差距較大的情況，使首末節點死亡時間間隔較長，產生監控盲點。而DE-LEACH算法能夠有效推遲首節點死亡時間，縮小首末節點死亡時間間隔，使監控盲點出現時間明顯縮短。這樣，在所有節點集中死亡后再進行拋撒，無疑在經濟上和控制上都將更加高效。
另外，考慮到傳感器節點所采集的數據在較短時間內具有相關性，可以采用事件驅動［10］的方式進一步延長網絡生存期。下面將對DE-LEACH與LEACH進行性能上的比較，并仿真分析了加入事件驅動因素后DE-LEACH的生存期改善程度。
3 仿真分析
3.1 DE-LEACH與LEACH性能比較
利用Matlab工具對LEACH算法和DE-LEACH算法進行仿真比較，主要比較：
(1) 存活節點數隨輪次變化曲線；
(2) 數據采集總比特數(二次融合前)隨輪次變化曲線。
仿真中，假設無線傳感器網絡由100個相同的無線傳感器節點組成，隨機拋撒在100 m×100 m的區域內，遠程基站位于坐標點(x=0,y=-100)。每個節點初始能量為0.5 J，發送和接收電路損耗為Elec=50 nJ/b，數據融合消耗為Eda=5 nJ/b。放大系數為Efs=10 pJ/b/m2(d
根據第二層簇頭對收到的第一層簇頭數據進行二次融合的融合率不同，這里分完全不融合、50%融合、完全融合分別進行了仿真比較。
完全不融合，即將第一層簇頭發送來的數據包不加處理地組成一個長數據包發送到基站，這時第二層簇頭相當于只是完成了數據接收和轉發的功能。仿真發現，即使在完全不融合的情況下，DE-LEACH的首節點死亡時間也要比LEACH晚30%，50%節點死亡時間晚15%(如圖1)。數據采集總比特數DE-LEACH比LEACH高出12%(如圖2)。雖然末節點死亡時間早于LEACH，但網絡中存活期非常集中，網絡出現大面積監控盲區的時間短，若要保證數據采集的持續性和完整性，對監控區域重新部署節點將比LEACH算法更經濟有效。
圖1 完全不融合存活節點數隨輪次變化曲線
圖2 完全不融合采集數據量隨輪次變化曲線
50%融合，即將第一層簇頭發送來的數據包壓縮一半之后發送到基站。各個第一層簇頭發送的數據包中仍然含有第一層簇頭數據包的包頭等基站不需要的冗余信息，可以進行進一步融合。仿真發現，進行50%融合后，DE-LEACH的首節點死亡時間比LEACH晚40%，50%節點死亡時間晚25%(如圖3)。數據采集總比特數DE-LEACH比LEACH高出22%(如圖4)。
圖3 50%融合存活節點數隨輪次變化曲線
完全融合，即將第一層簇頭發送來的數據包壓縮成一個2 000 b的數據包發送到基站。由于融合率較大，不僅要用到數據級融合，特征級融合，還要用到決策級融合［1］。即最后傳輸到基站的已不是簡單的數據，而是第二層簇頭節點對采集到的數據進行綜合分析后所得到的結果。仿真發現，完全融合后，DE-LEACH的首節點死亡時間比LEACH晚40%，50%節點死亡時間晚30%(如圖5)。數據采集總比特數DE-LEACH比LEACH高出28%(如圖6)。
圖4 50%融合采集數據量隨輪次變化曲線
圖5 完全融合存活節點數隨輪次變化曲線
圖6 完全融合采集數據量隨輪次變化曲線
由仿真比較可見，綜合考慮了簇頭節點到基站的距離以及剩余能量并據此選出第二層簇頭的DE-LEACH算法，性能較LEACH有明顯的改善。
DE-LEACH算法的優點:延長了首節點死亡時間，曲線斜率明顯比LEACH大，縮短了首末節點死亡時間間隔，相比于LEACH，節點死亡時間更加集中，監控盲點出現時間短，重新部署傳感器節點更加經濟高效；數據采集總量明顯提高。DE-LEACH算法的不足：由于在原來LEACH算法的簇頭與基站之間又增加了一跳路由，網絡延遲有所增加。另外，節點的運算能力要有所提高。就仿真來看，要想得到更長的網絡生存時間和更高的數據采集量，就要加大數據融合率，這對節點的數據融合能力提出了更高的要求。在實際應用中，需要根據應用對性能和成本的要求進行綜合考慮。
表1 LEACH與不同融合率的DE-LEACH性能比較
算法首節點死亡/輪50%節點死亡/輪采集數據×108 b
LEACH9411 2702.438
DE-LEACH不融合1 2171 4562.733
DE-LEACH 50%融合1 3111 5922.982
DE-LEACH完全融合1 3111 6593.117
3.2 事件驅動型DE-LEACH生存期分析
針對傳感器節點所采集的數據(如溫度、壓力等)在較短時間內的相關性，可設定一個門限值，當相鄰兩次所采集數據變化超過此門限值時，節點才向簇頭發送數據，并保留后一次數據在該節點存儲器中；若變化小于門限值，則不進行發送，仍保留前一次數據以防止數據以漸進的方式變化。門限值可設定為前次采集數據的百分比或具體的數值，視具體情況而定。圖7的仿真設定門限值為前次采集數據的10%(完全不融合情況)。
圖7 事件驅動對生存期的影響
由圖7可見加入事件驅動因素后，網絡生存期延長約9%，仿真中為方便采集數據用隨機數的方式產生，不具有相關性。當實際應用中的數據具有相關性時，生存期延長將更加明顯。另外，門限值的大小可根據需要更改，適應性較強。加入事件驅動的缺點：由于需要存儲兩次采集的數據進行比較，提高了對傳感器節點存儲能力的要求。
4 結 語
路由協議在很大程度上決定了網絡的整體性能。因此，作為無線傳感器網絡核心技術之一，路由協議一直是研究的熱點。LEACH算法是一種經典的層次型路由協議，它利用簇頭輪換機制有效的將能量消耗較均勻地分攤到整個網絡。在LEACH算法的基礎上提出了一種基于距離和能量選擇第二層簇頭的兩層改進型LEACH算法DE-LEACH，并簡要分析了事件驅動對網絡生存期的影響。仿真結果表明，該算法進一步平均了網絡中的能量消耗，有效延長了網絡生存時間，提高了網絡的數據采集能力。
LEACH算法的實現作了一些假設。其中一點是網絡中每個節點當選簇頭后都進行全網廣播，這樣的假設在網絡覆蓋范圍較大的情況下損耗將明顯加大，因此在大規模應用中多層多跳路由成為必然的選擇。這也將是今后工作繼續探討的方向之一。
參考文獻
［1］孫利民,李建中,陳渝.無線傳感器網絡［M］.北京:清華大學出版社,2005.
［2］馬祖長,孫怡寧,梅濤.無線傳感器網絡綜述［J］.通信學報,2004,25(4):114-124.
［3］梁英,曾鵬,于海斌.無線傳感器網絡中一種能量自適應的簇首選擇機制［J］.信息與控制,2006,35(2):141-146.
［4］李莉,溫向明,董樹松.無線傳感器網絡路由協議的研究與展望［J］.中國電子科學研究院學報,2006,1(1):17-21.
［5］Heinzelman W,Chandrakasan A,Balakrlshnan H.Energy Efficient Communication Protocol for Wireless Sensor Networks［A］.Proceedings of the Hawaii International conference on System Sciences［C］.Piscataway:IEEE,2000:175-187.
［6］胡剛,謝冬梅,吳元中.無線傳感器網絡路由協議LEACH的研究與改進［J］.傳感技術學報:自然科學版,2007,20(6):1 391-1 396.
［7］Manjeshwar A,Agrawal D P.TEEN:A Routing Protocol for Enhanced Efficiency in Wireless Sensor Networks［A］.Proceedings of the 15th Parallel and Distributed Processing Symposium.San Francisco:IEEE Computer Society,2001:2 009-2 015.
［8］劉守軍.無線傳感器網絡LEACH算法的研究［J］.武漢理工大學學報,2007,29(10):43-45.
［9］Heinzelman W,Chandrakasan A,Balakrishnan H.An Application-specific Protocol Architecture for Wireless Microsensor Networks［J］.IEEE Trans.on Wireless Communications,2002,10:660-670.
［10］汪全弟,孔衛,李彬.事件驅動型無線傳感器網絡生存期分析［J］.重慶大學學報:自然科學版,2007,30(6):30-34.
作者簡介
閆仁強 男，1983年出生，河北石家莊人，碩士生。研究方向為無線傳感器網絡組網與定位技術。
田 華 男，1967年出生，湖北荊門人，副教授、碩士生導師。主要研究方向為無線通信。
注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。
