基于非均勻分簇的無線傳感器網絡多跳路由算法

林 仁，夏方禮，王 扉(湖南城市學院 數學與計算科學學院，湖南 益陽 413000)

基于非均勻分簇的無線傳感器網絡多跳路由算法

林 仁，夏方禮，王 扉
(湖南城市學院 數學與計算科學學院，湖南 益陽 413000)

針對低功耗自適應分簇(LEACH)路由協議中均勻分簇方式和簇頭選擇的不合理以及遠距離數據傳輸過程中能量消耗過多的問題，提出了一種基于非均勻分簇的多跳路由算法LEACH-MRUC．在分簇過程中，該算法充分考慮了節點的能量及地理位置，同時采用非均勻分簇方式構建規模不同的簇結構；在數據傳輸過程中，簇頭與基站之間采用單跳和多跳相結合的路由方式來進行通信．仿真結果表明，LEACH-MRUC算法既使得網絡的能量消耗有效地得到均衡，又使得能量的利用效率得到顯著提高，并且顯著延長了網絡的壽命．

負載均衡；非均勻分簇；無線傳感器網絡；能量高效

1 概述

無線傳感器網絡是大量微小傳感器節點組成的自組織(Ad-hoc)網絡系統，這些微小傳感器部署在監測區域內，其目的就是協助感知、采集和處理監測區域內感知對象的有效信息，并最終將其發送給觀測者[1]．無線傳感器網絡很好的將網絡世界、客觀的物質世界以及人類社會有機的結合在一起，它無需固定網絡設施的支持，具有快速展開、抗毀性強等特點，可廣泛應用于軍事偵察、環境監測、醫療護理以及空間探索等領域[2-3]．由于傳感器節點通常被隨機部署在無人值守的區域且一般采用電池供電，因此，研究高效、負載均衡的路由協議對無線傳感器網絡意義重大．

目前，研究者們已提出了各種路由協議．一般從網絡的邏輯結構來看，可以分為層次路由協議和平面路由協議兩種.所有傳感器節點在平面路由協議中地位平等且缺乏中心控制節點．因此，網絡的可擴展性以及對資源的優化管理能力較弱，對動態變化網絡的反應速度也相對較慢；層次路由協議則通過將網絡劃分為多個規模較小的簇，由簇頭節點來實現局部范圍內簇內成員的管理，從而實現節點之間的協同工作．層次路由協議的出現在很大程度上解決了平面路由協議中存在的一些問題，它也是當前路由協議研究的主流[4]．

LEACH[5]協議是無線傳感器網絡中最經典的層次路由協議之一，本文研究了LEACH協議及相關改進協議，并且針對其數據傳輸以及簇頭選舉等一些方面存在的先天性不足，進而提出了一種基于非均勻分簇的多跳路由算法 LEACHMRUC(Mutil-hop Routing Algorithm Based on Uneven Clustering of LEACH)．

2 LEACH協議

2.1 LEACH協議介紹

MIT的Heinzelman等人提出的第一個基于分簇思想的層次路由協議便是 LEACH，其后許多路由協議都是在它基礎上發展而來的．LEACH協議的主要思想是通過自適應分簇的方式將整個網絡劃分為多個不同的簇，并采用輪換的隨機性簇頭選舉機制來達到均衡網絡負載、延長網絡生命周期的目的．其拓撲結構見圖1．

圖1 LEACH協議的拓撲結構圖

LEACH引人了“輪”(round)的概念，每輪循環由兩個階段組成，即簇的建立階段和穩定傳輸階段，并且其協議的執行過程是周期性的．每個傳感器節點在簇的建立階段選擇一個介于0和1之間的隨機數．若該隨機數小于閾值T(n)，則此節點在這一輪中被選舉為簇頭．

其中，p表示在網絡中簇頭所占節點的百分比大小；集合G中的元素表示在最近1/p輪中還未當選過簇頭的節點；輪數r表示當前已完成的．

簇頭在節點選定后通過廣播方式將其成為簇頭的消息告知網絡，而其他節點是根據接收到信息的信號強弱來決定其所從屬的簇，并向相應簇頭發送請求加入消息，從而完成簇的建立工作．隨后，簇頭節點采用TDMA方式為簇內成員分配傳播數據的時間片，并告知簇內成員．

穩定傳輸階段，簇內成員節點將在所屬時間片內采集到的數據發送給簇頭，簇頭節點將接收到的簇內成員數據進行相應的融合處理，最后將融合后的數據發往基站，之后又開始新一輪循環．

2.2 LEACH協議缺陷

LEACH 協議在無線傳感器網絡中意義重大，但也有幾點缺陷：(1)LEACH協議基于初始能量同構前提，在實際應用中存在著局限；(2)LEACH協議采用隨機性的簇頭選舉及均勻分簇方式，可能使得某些節點過多擔任簇頭而過早耗盡能量，從而產生網絡監測“盲區”；(3)由于所有簇頭與基站之間采用單跳路由方式，導致簇頭負載過重，遠距離通信能耗開銷較大；(4)LEACH協議的可擴展性差，不適合大規模的無線傳感器網絡．

3 LEACH-MRUC協議

在LEACH-MRUC協議的簇頭選舉過程中，它充分考慮了節點的能量及位置因素，確保剩余能量較高的節點優先當選為簇頭，并且在能量消耗大致相同的情況下，距離基站較近的節點成為簇頭的可能性更大；此外，由于距離基站較遠的簇頭能量消耗速度較快，因此，LEACH-MRUC協議采用非均勻分簇策略，通過構建規模不同的簇結構來均衡負載；在數據傳輸的過程中，采用單跳和多跳相結合的路由方式來實現簇頭與基站的數據通信，既節省了簇頭節點與基站遠距離通信的開銷，也使得網絡的可擴展性得以加強．

3.1 新的成簇機制

在進行簇頭選舉時，LEACH-MRUC算法與LEACH具有相似的選舉機制．不同的是，基站在網絡部署階段需發送一個廣播消息，其功率足夠大，根據接收到的信號強度RSSI，需要計算傳感器節點與基站的近似距離[7]．考慮到 LEACH協議不適合節點初始能量不同的場合，且簇頭選舉算法沒有考慮節點的實際情況，本文結合節點的能量和距離因子，給出了如下閾值T(n)的計算公式：其中，Ecurrt：節點的剩余能量，Einit：節點的初始能量，n：網絡預計要運行的輪數，d：當前節點到基站的距離，節點到基站的最大值、最小值，常數w大于0小于1，隨網絡規模和場景的不同進行大小設置．

基于公式(2)的改進，當選為簇頭往往是剩余能量較高的節點，而如果能量相當，成為簇頭的可能性就處決于距離基站遠近，從而確保選出的簇頭位置合理且具有較多能量，優化所形成簇的結構．

無線傳感器網絡中，第一順序無線電模型[6]一般被采用，節點發送k比特數據所消耗的能量：

其中，Eelec：電路消耗的能量，功率放大器的能量損耗系數，d：傳輸距離，dc：距離閾值．

節點接收數據時的能耗為

在基于多跳方式的路由協議中，距離基站較近的節點需承擔數據轉發工作，此外，根據多徑衰減模型可知，節點與基站進行遠距離傳輸時能量的消耗與距離的4次方成正比，因此，為了均衡不同地理位置的簇頭節點的能耗，LEACHMRUC算法中采用非均勻分簇的策略，通過控制各簇頭的廣播范圍來構建不均等的簇結構．

定義節點i的廣播半徑Ri為

由公式(5)可知，節點的廣播半徑與節點到基站距離的大小成正比，節點的廣播范圍始終在R與之間變化，與基站相距越近的節點其廣播半徑越小，用于管理簇內成員所消耗的能量也就越少，從而使其具有更多的能量用于多跳通信時的數據轉發．

3.2 數據傳輸策略

LEACH-MRUC協議中，簇頭與基站進行通信時采用單跳和多跳相結合的傳輸模式．算法中引入了一個臨界值TD_MAX，當簇頭與基站的距離大于臨界值TD_MAX時，簇頭以多跳路由的方式與基站進行通信，否則與基站直接進行通信，最終形成一棵以基站為根節點的路由樹．

在穩定傳輸階段開始前，各個當選為簇頭的節點以相同的功率向全網廣播一條包含其自身ID、當前剩余能量以及它與基站距離的消息，當某個簇頭節點收到來自其他簇頭節點的廣播消息后通過計算獲得它們之間的距離值．在采用多跳路由進行通信的過程中，假設簇頭i的下一跳候選簇頭節點的集合為MCH，則MCH應滿足

假設簇頭i選擇簇頭j作為其數據轉發的下一跳并將數據發往基站，根據能耗計算公式，傳輸k比特數據所消耗的總能量為

圖2 路由樹模型

4 仿真結果及分析

本文通過NS2平臺對LEACH-MRUC算法仿真，將200個傳感器節點隨機部署在300 m*300 m的監測區域，基站坐標為(150,350)，節點的初始能量為 3 J，發送和接受數據的能量損耗為 50 nJ/bit，ω為0.8，TD_MAX為140 m，λ為0.5，假設數據在轉發過程中無丟失．

本文分別從網絡存活節點數、網絡能量消耗及每輪簇頭所消耗的總能量三方面對 LEACHMRUC、LEACH以及HEED協議進行比較．

4.1 每輪存活節點數目比較

圖3 網絡存活節點對比

圖3為網絡存活節點數的對比，從圖中可以看出，在210 s及350 s附近，LEACH和HEED協議開始有節點出現死亡，到600 s和760 s的時候網絡中的節點已全部死亡，而LEACH-MRUC算法中第一個死亡節點出現的時間為620 s附近，最后一個節點死亡的時間則為970 s左右．

圖3中的曲線顯示，LEACH-MRUC算法的存活節點數目隨時間變化的曲線明顯優于LEACH 和HEED，這主要是因為LEACH-MRUC算法中節點的負載均衡度更好，避免了某些節點負載過重而過早死亡的現象．

此外，在無線傳感器網絡中，第一個節點和最后一個節點死亡的時間跨度可以很好的反映網絡穩定工作的情況，跨度越短說明網絡的能耗均衡度越好，因而性能也就越穩定．表 1顯示LEACH-MRUC既使得網絡壽命得到有效的延長，并且由于時間跨度明顯小于另外兩種協議，使得網絡的性能得到顯著提高．

表1 節點壽命值對照

4.2 總能量消耗對比

圖4為網絡的總損耗隨時間變化的曲線，圖中顯示LEACH的總能量消耗速度最快，HEED略優于LEACH，而LEACH-MRUC算法的曲線斜率大都低于LEACH和HEED，因而其總能量消耗速度相對而言更為緩慢，這很大程度上得益于LEACH-MRUC算法在簇頭選舉過程中考慮了位置因素和節點能量，對所形成簇的結構進行了優化，同時改進了對簇間的路由方式，減少了基站與簇頭遠距離通信的開銷，節約了能量．

圖4 網絡總能耗比較

4.3 每輪簇頭消耗能量對比

在分簇路由協議中，簇頭節點所消耗的能量在網絡的總能量消耗中所占比重非常大，簇頭相對普通節點所承擔的任務更多，因而也更容易由于負載過重而導致失效，因此，對比網絡中每輪簇頭節點所消耗的能量也是評估協議性能優劣的重要手段．圖5為實驗過程中各隨機選取連續16輪所統計的簇頭總能耗對比．

從圖5可以看出，LEACH-MRUC各輪中簇頭節點消耗的總能量低于LEACH、HEED，這與該算法中采用非均勻分簇的策略進行分簇是密不可分的，非均勻的簇結構很好的均衡了不同地理位置的簇頭的負載．同時，LEACH-MRUC在通信過程中采用了單跳與多跳相結合的通信機制，減少了與基站直接通信的簇頭的數目，節省了簇頭遠距離通信的能耗代價．相對LEACH和HEED而言，圖5中LEACH-MRUC算法所代表的曲線的波動性也較小，這也說明LEACH-MRUC算法在穩定性及負載均衡度方面得到了提升．

圖5 各協議每輪簇頭總能耗比較

5 結束語

本文對LEACH協議進行了詳細的分析，并針對其問題提出了一種基于非均勻分簇的無線傳感器多跳路由算法(LEACH-MRUC)．在LEACHMRUC算法中，新的成簇機制確保了選出簇頭的合理性，同時非均勻分簇的方式也很好的均衡了網絡中簇頭節點的負載，此外單跳與多跳相結合的路由方式避免了所有簇頭與基站遠距離直接通信時不必要的能量消耗．仿真實驗表明，該算法在節點存活情況、網絡總能耗以及每輪簇頭所消耗能量方面均優于LEACH和HEED，既延長了網絡的生命周期，又有效提高了能量的利用效率．

[1]黃海寧, 任豐原, 林闖. 無線傳感器網絡[J]. 軟件學報, 2003, 14(7): 1252-1291.

[2]Yick J, Mukherjee B, Ghosal D. Wireless sensor network survey[J]. Computer Networks, 2008, 52(12): 2292-2330.

[3]Zhonghua Zhao,Wei Huangfu, Linmin Sun.NSSN: A network monitoring and packet sniffing tool for wireless sensor networks[C]//Proceedings of the 8th International Conference on Wireless Communications and Mobile Computing, 2012: 537-542.

[4]Zhang Wenya, Liang Zize, Hou Zengguang,et al. A power efficient routing protocol for wireless sensor network[C]// Proceedings of the IEEE International Conference on Networking Sensing and Control. Washington, DC: IEEE Computer Society, 2007: 20-25.

[5]Heinzelman W, Chandrakasan A, Balakrishnan H. Energyefficient communication protocol for wireless Micro-sensor networks[C]//Proceedings of the 33rd Annual Hawaii International Conference on System Sciences. Maui: IEEE Computer Society, 2000: 3005-3014.

[6]Zhang Jun-guo, LI Wen-bin, CUI Dong-xu,et al. The NS2-based simulation and research on wireless sensor network route protocol[C]//Proceedings of the 5th International Conference on Wireless Communications, Netwarking and Mobile Computing. Piscataway, 2009: 3146-3149.

[7]李成法, 陳貴海, 葉懋, 等. 一種基于非均勻分簇的無線傳感器網絡路由協議[J]. 計算機學報, 2007, 30(1): 27-36.

(責任編校：蔣冬初)

A Mutil-hop Routing Algorithm Based on Uneven Clustering for Wireless Sensor Networks

LIN Ren, XIA Fang-li, WANG Fei
(College of Mathematics & Computer Science, Hunan City University, Yiyang, Hunan 413000, China)

Concerning the deficiencies of Low Energy Adaptive Clustering Hierarchy (LEACH) routing protocol, approximately uniform cluster structure, unreasonable cluster-head nodes selection and also more than one cluster-heads consuming excessive energy in the process of long-distance communications, a mutil-hop routing algorithm based on uneven clustering is proposed. In the set-up phase, the remaining energy and the geographical position of nodes are fully considered, and it uses non-uniform clustering way to build cluster structure of different sizes. In the steady-state phase, a routing method with single-hop and multi-hop is also introduced to the communicate between cluster-heads and Base Station (BS). Simulation results show that the algorithm effectively balances the energy consumption of networks, improves energy efficiency and obvious prolongs the network lifetime.

wireless sensor networks; load balancing; uneven clustering; energy efficient

O646

A

10.3969/j.issn.1672-7304.2017.01.11

1672–7304(2017)01–0049–05

2016-11-10

中央高校基本科研業務費專題項目(SWJTU12ZT12)；國家教育部人文社會科學研究規劃基金項目(13YJA630144)；益陽市科技計劃項目(益科字[2016]51號)

林仁(1979-)，男，湖南邵陽人，講師，博士，主要從事項目管理與調度優化、智能優化算法研究．E-mail: 232898945@qq.com