低能耗無線傳感器網絡路由協議研究

潘雪峰，李臘元，，何延杰

（1.武漢生物工程學院 計算機與信息工程系，湖北 武漢430415；2.武漢理工大學 計算機科學與技術學院，湖北 武漢430063）

0 引 言

無線傳感器網絡的應用較為廣泛，其中一個重要的研究方向就是路由協議的研究與分析［1］。路由協議對無線通信模塊的能量消耗起著關鍵影響。路由協議的研究一般放在路由機制和數據驅動上，由此劃分了階段，并出現了一些優秀的路由算法［2－3］。

針對LEACH協議和PEGASIS協議的不足，給出了改進方案。在簇首選取的過程中經過公式推導，找出最優簇首的數量與參數間的關系；簇的建立的過程中給出了算法流程；并對簇間路由中路由樹建立的過程進行了描述。最后使用NS2.27進行了仿真，并給出了數據分析及結論。

1 具有代表性的無線傳感器網絡路由協議的分析

無線傳感器網絡路由協議所包含內容較多，但其核心內容是選擇簇首節點、形成簇、簇間數據的路由［4－5］。分簇方式種類較多，一個簇能夠使用不同的數據交換方式［6］。同時，由于選擇簇首節點機制的不同，算法也不同［7－8］。課題分析研究了兩種典型的層次路由協議，它們屬于分布式算法。

1.1 LEACH協議 （低功耗自適應簇分層型協議）

在LEACH協議中，形成簇時使用自我組織、自動適應性、隨機選擇的機制［9］。圖1描述了無線傳感器網絡中的節點分為5個簇，使用的是LEACH協議，圖中簇首節點用黑色圓圈表示，非簇首節點用白色圓圈表示。協議隨機選擇簇首節點，使每個傳感器節點平均分配了整個網絡的能量消耗［10］。

圖1 低功耗自適應簇分層型協議的簇結構

低功耗自適應簇分層型協議的執行過程是周而復始的，每一個周期又分為很多輪，每輪中簇首的選擇是隨機的［11－12］。簇建立階段和穩定傳輸階段是一輪中的兩個重要組成部分。

從以上分析看出LEACH協議具有以下不足：①使用簇首節點隨機輪換法雖然能降低能量消耗，但反復重建簇還是會消耗更多的能量；②不同的簇內，簇首節點與非簇首節點的距離各不相同，通信過程中簇首的能量消耗增多；③由于簇首節點需要與匯聚節點通信、完成數據融合等工作，能量消耗增多。

1.2 PEGASIS協議

PEGASIS協議在進行鏈接時，節點采用鏈式結構。使用PEGASIS協議時，首先根據接收的信號的強度，區分鄰居節點距離的遠近，在尋找距離最近鄰居的時，為了使信號僅有該鄰居接收，還要調整發送信號的強度。接下來，每個節點向鏈路中鄰居節點發送隨機數據，并且只選擇一個節點作為鏈首向匯聚節點傳輸數據［13－15］。

從以上分析看出PEGASIS協議有以下不足：①協議設計鏈路過于理想化，將匯聚節點與簇首節點通信時，能夠直接通信，在實際情況中，簇首節點需要用多跳的方式與匯聚節點通信；②協議對各節點能量的設計有所不足，假定它們的能量基本相當，在能量耗盡的情況下，它們可能會全部脫離網絡或在網絡中消失；③協議對拓撲結構的設計有所不足，節點要獲取周圍節點的狀態及能量，這樣便于收發數據，但拓撲結構同時也會受到影響；④設計協議時，未引入備用鏈首節點，鏈路如果過長，就會產生數據發送接收的滯后。

2 EBLP協議的設計

2.1 改進切入點

通過對低功耗自適應簇分層型協議和低功耗傳感器信息系統協議的分析，找出這兩個協議的不足，從選擇簇首節點、形成簇、簇間路由等方面對LEACH協議進行了改進。給出了以下改進的切入點：①減少簇重組次數，從而降低了簇多次反復形成而損失的能量；②改變選擇簇首節點的算法，考慮決定能耗的參數的影響和減小簇首節點之間的距離；③調整簇和簇成員的個數，使得簇首的負載均衡，簇的劃分合理；④在建立路由樹的過程中，要考慮簇首節點與匯聚節點的距離遠近，還要考慮簇首節點的能量，簇首節點采用多跳通信的方式，可以解決一些簇首節點因離匯聚節點過遠，在采用單跳收發數據時，消耗能量太大的問題。

2.2 具體描述

2.2.1 簇首選取

在LEACH協議中選取簇首時，存在著一定的不足，由于簇首是在簇內選取出來，所處的位置相對不固定，如果簇首節點位置相對集中，某些節點會被孤立，出現未被分到任何簇中的情況，這時候網絡就會局部不連通。與此同時，簇首節點位置相對集中，還會使系統內部重復數據過多，收發這些數據需要更多的能量，如果能減少這些重復的數據，就能在降低能耗。設計的EBLP算法近似求出簇首節點個數較為合理的值，結合無線傳感器網絡中的節點分布、規模大小，求出簇首節點之間間隔的最小值，然后根據式 （1）中改進后的閾值T （n）來選擇簇首。

式中：p——選為簇首的節點占所有總節點數的百分比，r——所經歷的輪數，rs——一直沒被選為簇首的輪數，En＿current——當前能量，En＿initial——初始能量。如果節點被選為簇首，rs便重置為0。

簇首節點消耗的能量會受到各種因素的影響，由于簇首節點的主要工作是與匯聚節點、簇內節點進行通信，因而簇首節點的能耗主要用于與簇內成員進行數據收發消耗的能量 （N／K－1）Eelec，以及與匯聚節點通信消耗的能量（Eelec＋εamp（）），其中簇的數量用K表示，接收或發送數據所需的能量用Eelec表示，簇首節點到匯聚節點的距離用dtoBS表示，簇首與匯聚節點通信時的無線信號傳播參數為εamp。簇內成員節點在一輪中消耗的能量EnonCH為：（Eelec＋εfsE（）），其中成員節點到簇首節點的距離用dtoCH表示，成員與簇首通信時的無線信號傳播參數為εfs。在一輪中每個簇消耗的能量Ecluster包括兩部分，分別是一個簇首所需能量ECH，及簇內成員所需能量 （N／K－1）EnonCH。因此在一輪中K個簇消耗的能量的累加和可使用全網消耗的能量Etotal來表示，代入前面的表達式后可得到：Etotal＝KEcluster＝K （N／K－1） （2Eelec＋εfsE））＋ （KEelec＋KεampE（））；考慮到K的值較大，那么K－1的值驅近于K的值，即可得到

假設模擬區域為正方形區域，其邊長為A，則無線傳感器網絡覆蓋的面積是A2，很容易得到，網絡中的一個簇得到的平均面積應是A2／K。簇內非簇首節點分布于簇首節點周圍，構成一個圓形，得到半徑為r＝A／的圓，根據半徑的值能夠算出圓心與圓內的點的距離平方的平均值，即數學期望為：E （） ＝ A2／2Kπ，同時，E（）與K無關，將其用常量L表示，因此式 （2）可變為

為了求出Etotal的最小值，對式 （3）左右兩邊同時對K求導數，令結果為0，這時就可以求出最優的K值

通過推導出的式 （4）找出結論：Kopt與N、A、dtoBS有關。為得到最優簇首數，可在設置網絡時設置時，給出這幾個具體的參數值。

2.2.2 簇的建立

當選取好簇首節點之后，為了建立簇，簇首會向周圍的非簇首節點發出簇首特有的信號，周圍的非簇首節點對接收到的信號的強弱進行判斷，一般加入信號強的簇首節點的那一簇中，并控制節點加入的數量，控制簇的大小。如果簇首同意周圍的非簇首節點加入簇中，會向該非簇首節點發送允許加入的信號，否則就發送拒絕加入信號。待簇建立完成，通過一條鏈路將簇首和成員節點鏈接，鏈接是采用貪婪算法，鏈的形成過程與PEGASIS協議相同。這樣一來，在每個簇中的節點數會比要比整個網絡中的節點少很多，傳輸的位置信息也相對較少，使得傳輸數據的延遲也不很明顯。

2.2.3 簇間路由

匯聚節點一般在無線傳感器網絡外部，與無線傳感器網絡所在的區域有一定的距離，在簇首節點都與匯聚節點進行數據交互的過程中，根據前面的推導，系統中節點的能耗將與它們之間距離的四次方成正比。在設計LEACH協議時，有著一定的不足，體現在簇間路由中，就是簇首在與匯聚節點進行信息交換時，對簇首的當前能量考慮不足，簇首可能會因能量損耗過快，能量耗盡而停止工作。為了解決上述的不足，同時還要考慮離匯聚節點較遠的簇首的能耗，在設計EBLP協議時，采用了多跳的方式，由此只需少量的簇首與匯聚節點直接通信。

簇首間層次路由樹的建立過程如圖2所示，其中M為匯聚節點，A、B、C、D均為無線傳感器網絡中的簇首節點。①M首先向整個WSN發出一個消息，能量設為∞，設置跳數為0。②收到這個消息的簇首，加上匯聚節點一起構造路由樹，路由樹中的根節點是匯聚節點，路由樹中葉子節點是簇首節點，將自身的剩余能量的值保存為包中的能量值，將收到的數據包經過的跳數值增加1，并轉發此廣播包給周圍的簇首。③由于B、C兩個簇首節點距離近，B會先收到來自于C的廣播包 （1，EC），后收到來自于A的廣播包 （1，EA）。但是由于A、C兩節點剩余能量不同，且EA＞EC，雖然兩者的跳數值都為1，但是節點B會選擇剩余能量較大的節點作為其父節點，因此構造路由樹時，節點A是節點B的父節點。依照上述規則可構造出路由樹的結構。

圖2 簇首間路由樹

3 仿真實驗和結果分析

3.1 仿真環境

為了驗證EBLP協議的有效性，在Linux下進行仿真實驗，實驗環境為：NS2.27。選取99m＊99m的正方形區域為仿真實驗區域，在仿真區域中隨機地分布著99個節點，設置匯聚節點位置在坐標 （59，179）處。如圖3所示。

圖3 EBLP算法的網絡拓撲

3.2 設置仿真參數

在測試EBLP協議的仿真前，應構建仿真環境、設置仿真參數，以上工作需要寫入腳本文件。主要腳本如下：

.／ns tclfile／eblp／wsn.tcl－sc setting／nodescen

－rp eblp＼

－x 99＼

－y 99＼

－nn 99＼

－stop 1200

－eq＿energy 1 ＼－init＿energy 2＼－filename result－bs＿x 59＼－bs＿y 179＼

3.3 仿真結果及分析

3.3.1 最優簇首數的仿真

在無線傳感器網絡區域中，在 （59，99）和 （0，0）的位置的簇首結點，距離匯聚節點 （59，179）的距離dtoBS的值分別是80至188.4，同樣也選取99m＊99m的正方形區域為仿真實驗區域，在仿真區域中隨機地分布著99個節點，εfs為10pJ／bit／m2將，εamp為0.0013pJ／bit／m4，將以上參數代入網絡最優簇首個數的計算式 （4）中，可得最優簇首數的值在2到5.5間。仿真后，得出了簇首數目與平均每輪能耗的關系如圖4所示。

圖4 簇首數與能耗的關系

3.3.2 能量消耗的仿真

在圖5中可以看到全網的能耗的比較，可以看出：實線為EBLP協議，兩條虛線分別是LEACH協議和PEGASIS協議；在網絡在前180輪，使用EBLP協議的無線傳感器網絡能耗高于LEACH和PEGASIS；在180輪后，使用EBLP協議的無線傳感器網絡能耗略低于LEACH和PEGASIS。

根據圖5可以得出以下結論：由于EBLP協議要進行簇首選擇、簇的建立和簇間路由樹的建立，而該過程都與簇首有關，其它非簇首節點協同工作，因此前180輪EBLP協議消耗的能量較多；但是網絡運行穩定后，由于簇間使用了路由樹來多跳通信，能量消耗相對較少。

4 結束語

通過對LEACH協議和PEGASIS協議進行了重點的分析，總結出這兩種協議各自的優缺點，針對LEACH協議生成非均勻的簇造成能量損耗的問題，以降低能量損耗為研究目的，結合PEGASIS協議的特點，從選擇簇首節點、形成簇、簇間路由等方面對LEACH協議進行了改進。經過理論分析和仿真實驗，對該協議的性能進行測試。可以得出結論，整個無線傳感器網絡的能量消耗上，EBLP路由算法要優于LEACH協議和PEGASIS協議。

圖5 全網能耗比較

［1］LI Shuhua，LIU Zhenyu，LI Yingqiu.Energy adaptive clustering in wireless sensor network routing protocol［J］.Computer Engineering and Design，2010，31 （3）：504－507 （in Chinese）.［李樹華，劉振宇，李迎秋.能量自適應的無線傳感器網絡分簇路由協議 ［J］.計算機工程與設計，2010，31 （3）：504－507.］

［2］LI Chengfa，CHEN Guihai，YE Mao，et al.A clustering based on non－uniform routing protocol for wireless sensor networks ［J］.Journal of Computers，2007，30 （1）：27－36 （in Chinese）.［李成法，陳貴海，葉懋，等.一種基于非均勻分簇的無線傳感器網絡路由協議 ［J］.計算機學報，2007，30（1）：27－36.］

［3］GONG Haigang，LIU Ming.DEED：A wireless sensor network energy－efficient data communication protocol ［J］.Chinese Journal of Electronics，2005，33 （8）：1392－1396 （in Chinese）.［龔海剛，劉明.DEED：一種無線傳感器網絡中高效節能的數據通信協議 ［J］.電子學報，2005，33 （8）：1392－1396.］

［4］SHEN Bo，ZHANG Shiyong.Wireless sensor network clustering routing protocol ［J］.Journal of Software，2006，17（7）：1588－1600 （in Chinese）.［沈波，張世永.無線傳感器網絡 分 簇 路 由 協 議 ［J］. 軟 件 學 報，2006，17 （7）：1588－1600.］

［5］SUN Yugeng，ZHOU Yin，BIAN Guinian，et al.Wireless sensor networks a network of energy efficient clustering algorithm ［J］.Chinese Journal Sensors and Actuators，2007，20（2）：377－381 （in Chinese）.［孫雨耕，周寅，邊桂年，等.無線傳感器網絡中一種能量有效的分簇組網算法 ［J］.傳感技術學報，2007，20 （2）：377－381.］

［6］Muruganathan S D，MA D C F，Bhasin R I，et al.A centralized energy－efficient routing protocol for wireless sensor networks［J］.IEEE Communications Magazine，2005，43（3）：8－13.

［7］WANG Chunlei，CHAI Qiaolin，WANG Hua，et al.Based on cluster energy efficient routing algorithm for wireless sensor networks ［J］.Journal of Computer Applications，2007，27 （2）：342－345（in Chinese）.［王春雷，柴喬林，王華，等.基于分簇的無線傳感器網絡節能路由算法 ［J］.計算機應用，2007，27 （2）：342－345.］

［8］TAO Xiaoling，WANG Guifeng，WANG Yong.Dijkstra for wireless sensor networks based on clustering routing algorithm［J］.Computer Engineering and Design，2010，31 （17）：3807－3811（in Chinese）.［陶曉玲，王桂鳳，王勇.基于Dijkstra的無線傳感器網絡分簇路由算法 ［J］.計算機工程與設計，2010，31 （17）：3807－3811.］

［9］WU Zhenhua，YIN Zhijun.WSNs based on optimization of non－uniform cluster radius clustering routing ［J］.Computer Engineering and Design，2010，31 （15）：3374－3378 （in Chinese）.［吳振華，尹志軍.基于優化簇半徑的 WSNs非均勻分簇路由 ［J］.計算機工程與設計，2010，31（15）：3374－3378.］

［10］NIU Kang，DENG Yaping，MAN Wen.Low－latency data fusion algorithms for wireless sensor networks ［J］.Computer Engineering and Design，2010，31 （12）2710－2712 （in Chinese）.［牛康，鄧亞平，滿文.低時延的無線傳感器網絡數據融合 算 法 ［J］.計 算 機 工 程 與 設 計，2010，31 （12）2710－2712.］

［11］TANG Yong，ZHOU Mingtian，ZHANG Xin.Routing protocol for wireless sensor networks research progress ［J］.Journal of Software，2006，17 （3）：410－421 （in Chinese）.［唐勇，周明天，張欣.無線傳感器網絡路由協議研究進展［J］.軟件學報，2006，17 （3）：410－421.］

［12］WU Chenwen，WANG Tiejun.NS2－based model of wireless sensor network routing protocol design and study ［J］.Journal of Lanzhou Jiaotong University，2007，26 （1）：1－5 （in Chinese）.［吳辰文，王鐵君.基于NS2無線傳感器網絡路由協議模型的設計與研究 ［J］.蘭州交通大學學報，2007，26（1）：1－5.］

［13］FU Jun，ZHANG Xiaofeng.A cluster head selection model based on wireless sensor network clustering algorithm ［J］.Journal of Computer Applications，2007，20 （8）：1856－1859（in Chinese）.［傅軍，張曉鋒.一種基于簇頭選擇模型的無線傳感器網絡分簇算法 ［J］.傳感技術學報，2007，20 （8）：1856－1859.］

［14］LIU Qin，WANG Fubao，MA Junyan，et al.A wireless sensor network effective distributed clustering ［J］.Computer Application，2007，27 （1）：4－6（in Chinese）. ［劉琴，王福豹，馬峻巖，等.無線傳感器網絡中一種有效的分布式簇劃分算法 ［J］.計算機應用，2007，27 （1）：4－6.］

［15］JIANG Shaofeng，YANG Minghua，SONG Hantao，et al.Sensor networks centroid－based distributed clustering algorithm ［J］.Journal of Computer Applications，2007，27（1）：1－3 （in Chinese）.［姜少峰，楊明花，宋瀚濤，等.傳感器網絡中一種基于質心的分布式成簇算法 ［J］.計算機應用，2007，27 （1）：1－3.］