節點分布不均勻的無線傳感網絡低功耗算法

張雙雙，王延年

（西安工程大學 電子信息學院，陜西 西安710048）

0 引 言

無線傳感網絡（Wireless Sensor Network，簡稱WSN）的目的是收集和處理目標檢測區域內被感知對象的相關信息，并將處理過的信息傳送至基站［1］.WSN中的節點在自身能量有限的條件下，要不斷獲取信息并傳送給基站，這樣就必須考慮節點的能量消耗問題.要延長WSN的網絡生命周期就必須盡量降低節點功耗［2］.

目前，針對無線傳感網絡節點能量、儲存能力和計算能力有限的特點，學者們提出了很多適合無線傳感器網絡的路由算法［3-5］.分層路由主要包括低功耗自適應分簇路由算法（LEACH）和門限敏感高效能耗傳感網絡算法（TEEN）［6］.TEEN算法通過合理的設置硬門限和軟門限，僅僅傳輸用戶感興趣的信息，從而可以有效地降低系統的能耗［7］.LEACH路由算法是具有代表性的層次路由，該算法采用輪概念，在每一輪數據采集過程中隨機選舉簇首，使網絡節點都有機會分擔通訊任務.但是，LEACH算法存在一些不足：無線傳感器節點數目大且分布不均勻，從而導致簇首節點負載不均衡，并且長距離的數據傳輸會加速一些遠距離節點的死亡，縮短網絡生存時間.

本文針對經典的LEACH算法存在的不足，提出了一種改進的LEACH算法.通過對傳統的簇首隨機選擇機制進行改進，將節點的剩余能量考慮在內，這樣就可以盡量避免低能量的節點成為簇首；并且在簇間構造多跳通信路徑，這樣可以降低網絡能量消耗，延長網絡生存周期.

1 無線傳感網絡路由協議

1.1 LEACH算法

LEACH協議采用分布式成簇技術，因此，簇頭節點在整個網絡中的作用很重要.

LEACH分為初始化階段和穩定階段兩個階段.在初始化階段，傳感器節點選擇一個［0，1］之間的隨機數.如果這個隨機數比門限T（n）要小，它就被選為簇頭.T（n）的計算公式［8］為

其中，P為節點中成為簇頭的百分比；r為目前輪數；G為過去1／P輪中沒有被選中為簇頭的節點集.

簇頭被選出來之后，它們就會通知網絡中的所有節點.一旦節點接收到簇頭的通知，節點就會根據與簇頭之間通信的強弱來選擇它要加入的分組，并通知簇頭它將成為該管轄區內的成員.然后，簇頭通過時分復用的方式為每個成員分配通信的時隙.在穩定階段，節點根據時隙表中分配的時間發送數據，其余時間內都處于休眠狀態［9-10］.簇頭將自己區域內所有節點的數據進行匯集，然后發送給基站.持續一段時間后，整個網絡進入下一輪的工作周期，重新選擇簇頭.

無線傳感網絡LEACH算法中，簇首的選取依靠隨機數與閥值的比較，具有很大的隨機性，使得部分簇首相距過近或部分簇首距離基站過遠，以及每個簇中節點數目分布不均勻，這樣就會加重個別簇首的負擔，降低網絡的負載平衡程度.另外，沒有考慮節點的剩余能量，如果剩余能量過低的節點當選為簇首時，就會加速該節點的死亡，影響整個網絡的生命周期.

1.2 能量消耗模型

2 LEACH算法改進

本文對經典的LEACH算法進行改進，在LEACH算法計算公式中，并沒有考慮各個節點的剩余能量，要想每個節點消耗的能量值相等，必須網絡中所有節點初始能量都相等，并且保證網絡任何一個簇首在向基站傳輸數據的過程中消耗的能量一樣.這樣就必須要求每個簇的大小相同，距離基站的距離相同.顯然，是不符合實際情況的，這必然導致網絡能量分布不均勻的情況.

2.1 簇首選擇

如式（4）所示，在簇頭選舉的過程中考慮到節點當前的剩余能量，所有節點必須監控各自的能量變化情況，若能量低于平均能量水平，降低其成為簇首的概率，以保證每輪中能夠選舉出剩余能量較多的節點為簇首節點.

其中，Ecur為第r輪開始時節點剩余的能量；Eave為第r輪節點的平均能量.

2.2 簇的形成

當節點當選為簇首之后，每個簇首用非持續CSMA（carrier-sense multiple access）MAC以相同的傳輸能量向剩余節點廣播自己成為簇首的消息，此消息稱為ADV，此消息包括簇首節點的ID號和包頭標示，其他節點接收到簇首的ADV消息，在一定的時間內可以接收到多個ADV消息，然后根據接收到的ADV消息強度來決定加入離自己最近的那個簇.節點發送加入簇的JOIN請求信息，此消息包括節點的ID號和簇首的ID號［12］.簇首接收到所有JOIN請求信息之后，根據成員節點的數目，簇頭為簇內每個節點分配TDMA時間表，并用廣播的形式發送到簇內所有的節點，這就可以保證簇內的每個節點只在相應的時隙內進行數據傳輸，而在其他時間內進入休眠狀態，從而減小了能量的消耗.每個節點得到自己的時隙表消息后，無線傳感網絡就進入了數據傳輸階段.

2.3 數據傳輸階段

無線傳感器網絡節點在完成簇的形成之后，需要各個簇與Sink節點進行通信.對LEACH簇間通信方式進行改進，利用Prim算法在簇頭之間構造最小生成樹，采用多跳路的通信方式，減少簇頭和sink節點之間直接通信所消耗的能量.

（1）在進行Prim算法時，首先選擇一個簇頭作為起始點，選擇簇頭的當前能量剩余狀況和它到基站的距離作為參考值，兩個參考值的關系Pi［13］：

其中，Ecurrent為當前節點剩余能量；lBE為簇頭節點距離基站的距離.比較Pi值的大小，選用最大的Pi值作為多跳的起始點，也就是最小生成樹的頂點.

（2）以簇頭之間的通信距離作為路徑權值，選擇權值最小的簇頭作為下一跳的子節點.

（3）繼續尋找該子節點的下一跳：選擇權值最優的節點成為它的下一跳，找到的下一跳節點作為它的子節點，依次執行下去.

在樹形路由建立以后，簇首節點將融合處理后的數據沿著多跳樹形方向向該簇頭的父節點傳輸，最后，起始節點把數據發送至基站.

在無線傳感器網絡中，基站一般都遠離信息采集區域，而我們知道信號傳輸距離越短，能量消耗越少，所以利用最小生成樹算法選取的最優多跳路徑可以減少因為距離而產生的能量消耗.

3 仿真與討論

本文使用Matlab仿真工具對改進好的算法進行仿真實驗.在100m×100m的范圍內，隨機部署了100個傳感器節點.節點分布如圖1所示，每個節點的初始能量為2J；每個節點在每輪數據傳輸階段傳輸的數據位100bit；最大運行輪數r為1 500.

圖2為節點存活個數與網絡生存時間的關系圖.在同樣網絡初始條件下對LEACH算法和改進后的算法進行了仿真實驗，比較兩者網絡生存時間.從圖2可以看出，LEACH網絡中出現第一個死亡節點在250輪左右，而改進后的網絡中出現第一個死亡節點是在接近于500輪，使網絡的生命周期延長了將近1倍.在1 000輪左右時，LEACH算法的節點已經全部死亡，改進算法節點的存活率仍然將近80%.這是由于改進算法在簇頭選舉過程中考慮到節點的剩余能量，避免了剩余能量過低的節點被選作為簇頭節點.并且改進后的算法在簇頭與基站的通信過程中，簇頭節點并不直接與基站進行數據傳輸，而是采用多跳路的通信方式，由能量的消耗公式可知，通信距離的遠近對節點能量的消耗有很大的影響，多跳路的通信方式就大大減少了遠距離數據傳輸對節點能量的消耗.說明改進后的算法不但能進一步降低網絡的能量消耗，有效地延長了網絡的生命周期，還使得整個網絡能量分布更加均衡.

圖1 節點分布圖

圖2 網絡生存時間圖

4 結束語

本文對經典LEACH路由算法進行改進，提出一種改進的分簇路由算法.改進的分簇路由算法考慮到節點的剩余能量，并且在數據傳輸的過程中采用多跳路的通訊方式，減少了節點能量，特別是簇頭節點的能量消耗，從而延長網絡生存時間，能夠很好地改善無線傳感網絡的能量負載平衡問題.

［1］ 牛瑛琦.無線傳感器網絡低功耗路由算法研究與仿真實現［D］.北京：北京郵電大學，2013：12-18.NIU Yingqi.Research and simulation on a low-power cluster routing algorithm for wireless sensor networks［D］.Beijing：Beijing University of Posts and Telecommunications，2013：12-18.

［2］ 宋杭選，李儒，牛斗.無線傳感器網絡低功耗分簇路由算法研究［J］.單片機與嵌入式系統應用，2009（3）：17-19.SONG Hangxuan.LI Ru，NIU Dou.Research on a low-power cluster routing algorithm for wireless sensor networks［J］.Microcontrollers &Embedded Systems，2009（3）：17-19.

［3］ 宋旭文，李曉偉，沈冬冬，等.一種低功耗的多跳無線傳感網時間同步算法［J］.電子科技，2014，27（4）：9-11.SONG Xuwen，LI Xiaowei，SHEN Dongdong，et al.A low power time synchronization algorithm for the multi-hop wireless sensor networks［J］.Electronic Science and Technology，2014，27（4）：9-11.

［4］ 郭振格.無線傳感網絡中低功耗協議的優化策略研究［D］.秦皇島：燕山大學，2011：16-18.GUO Zhenge.Optimization strategies for low-power protocols based on wireless sensor networks protocols［D］.Qinhuangdao：Yanshan University，2011：16-18.

［5］ SINGH M，SETHI M.A Tree based routing protocol for mobile sensor networks（MSNs）［J］.International Journal on Computer Science and Engineering，2010，2（SI）：55-60.

［6］ 王璨，駱堅，張大方，等.一種基于移動性的無線傳感器網絡分簇路由協議［J］.計算機工程與科學，2012，34（3）：6-12.WANG Can，LUO Jian，ZHANG Dafang，et al.A mobility-based cluster routing protocol for mobile wireless sensor networks［J］.Computer Eenineering &Science，2012，34（3）：6-12.

［7］ 張源.一種 TEEN協議的節能型改進算法［J］.現代計算機，2009（5）：61-64.ZHANG Yuan.An improved energy-saving algorithm based on TEEN［J］.Modern Computer，2009（5）：61-64.

［8］ 陶駿.WSN中LEACH路由算法的改進及應用研究［D］.蘇州：蘇州大學，2010：6-8.TAO Jun.The application and improvement on the LEACH routing protocol in wireless sensor networks［D］.Suzhou：Suzhou University，2010：6-8.

［9］ 顧明霞.一種新的基于LEACH 的 WSN路由算法［J］.計算機仿真，2011，28（8）：129-133.GU Mingxia.New LEACH-based algorithms for wireless sensor networks［J］.Computer Simulation，2011，28（8）：129-133.

［10］ 孔令榮，王昊，莊濤.基于 WSN的分簇路由協議研究與改進［J］.無線電工程，2014，44（12）：48-51.KONG Lingrong，WANG Hao，ZHUNAG Tao.Research and improvement of clustering routing protocol based on WSN［J］.Radio Engineering，2014，44（12）：48-51.

［11］ 趙凡.一種能量均衡的無線傳感器網絡多跳分簇路由算法［D］.哈爾濱：哈爾濱理工大學，2014.ZHAO Fan.An energy-balanced multi-hop clustering routing algorithm in wireless sensor neiworks［D］.Harbin：Harbin University of Science and Technology，2014.

［12］ LIU Zhixin，DAI Lili，MA Kai，et al.Balance energy-efficient and real-time with reliable communication protocol for wireless sensor network［J］.The Journal of China Universities of Posts and Telecommunications，2013，20（1）：37-46.

［13］ 徐建軍，沙力妮，張艷，等.一種新的最小生成樹算法［J］.電力系統保護與控制，2011，39（14）：107-112.XUN Jianjun，SHA Lini，ZHANG Yan，et al.A new algorithm of the minimum spanning tree［J］.Power System Protection and Control，2011，39（14）：107-112.