基于半徑遞增有向成簇的WSN路由算法

李長庚，于澄澄，陳東海

（中南大學物理與電子學院，長沙410083）

無線傳感器網絡［1］實現了計算機世界、自然世界與人類社會三元世界的無縫連接［2-4］，是一個全新的信息獲取平臺，其節點一般部署在無人值守地域，資源能量有限，因而在相關研究和設計時必須突出考慮能量因素，以獲得更長的網絡生命周期。

分簇路由算法（如LEACH［5］）采用劃區組簇的方式，減小了與基站直接通信的節點數量，降低了通信開銷，其簇頭輪換機制能有效均衡簇頭的能耗消耗。其缺點在于簇頭地位關鍵，能量消耗大，容易出現“熱點”，簇頭選舉成本大，算法復雜度高，另外，簇規模與位置難以控制。

鏈式路由算法（如PEGASIS［6］）通過減小節點間的平均通信距離，降低了網絡通信成本。其不足之處包括：一是鏈式結構層級眾多，通信延時較大；二是每個節點都承擔融合數據的任務，使得全網在數據融合方面的能量消耗偏大；三是由于采用貪婪算法尋找下一跳節點，在組網后期容易出現下一跳節點的距離較遠的情況；四是鏈式結構不能對低能量節點進入篩選，結構中任何一個低能量節點的死亡都將導致結構重組，增大了重組頻率。

LEACH算法是經典的分簇路由算法，所有節點等概率地隨機擔當簇頭，不考慮節點能量問題。HEED［7］算法和TEEN［8］算法在選擇簇頭時考慮了能量因素，使得能量較大的節點擔任簇頭的概率較高。EEUC［9］算法、EOUCP［10］算法、CHTD算法、LDB?PL［11］算法引入了競選半徑非均勻、競選時間延遲、分層次成鏈等概念，文獻［12］還提出了代理簇頭的思想，這些算法改進了選舉簇頭過程，其結果更趨合理，但依然存在一定的隨機性，且選舉過程受到多個約束條件限制，這增加了算法復雜度，同時提高了節點成簇組網過程的能耗。

基于以上分簇算法和鏈式算法優點與不足，設計一種半徑遞增有向成簇路由算法，其基本思想為“向基站方向成鏈，鏈中盡量成簇”，在操作程序上，各節點以較小半徑值R0組簇，然后簇頭和未進入網絡的其他節點以更大的半徑2R0，在其前向傳輸區域內選擇下一跳節點，之后再增大組網半徑，直至所有節點加入網絡。最后通過與LEACH算法和目前較典型的EEUC算法進入仿真實驗比較，驗證算法性能并進行參數分析。

1 系統模型與理論描述

1.1 網絡模型

無線傳感器網絡是一個面向應用的系統，不同的應用環境需要不同的網絡模型。假定N個傳感器節點隨機均勻分布在一個面積為M×M的區域A內，并且有如下性質：①所有節點部署后不移動，能量不補充；②基站部署在區域A內或邊界外一個固定位置，并且是唯一的；③無線信道滿足對稱性，即正向傳輸和反向傳輸等量的數據消耗的能量相同；④節點同構，具有相同的處理和通信能力，在網絡中地位平等；⑤節點無線發射功率可控，可根據距離調整發射功率；⑥節點可以獲取無線接收信號的強度［13］；⑦采用數據融合技術減少傳輸的數據量。

1.2 無線通信能量模型

網絡中節點通信采用Heinzelman等人在文獻［14，15］中提出的無線通信模型。當發送節點與接收節點的距離小于閾值d0時，采用自由空間模型，否則采用多路衰減模型［16.17］。發送方發送長度為lbit的數據到距離為d的位置消耗的能量為：

而接收方接收lbit的數據所需能量為

其中，發射電路系數與接收電路系數數值相等，ETx-elec=ERx-elec=Eelec=50 nJ/bit，自由空間模型發射放大器εfs=10 pJ/bit/m2，多徑衰減模型發射放大器εmp=0.0013 pJ/bit/m4，數據融EDA=5 nJ/（bit/signal），閾值。

1.3 前向傳輸概念

在分簇結構中，簇內和簇間時常會出現某節點距離基站的距離比其下一跳節點距離基站更近的情況，即數據傳送到了距離基站更遠的節點，為避免這種數據“回流”現象，這里引入前向傳輸的概念。如圖1，節點i只把數據傳輸給在其通信范圍內距離基站更近的鄰節點中的一個，其可能位置為：以基站為中心、dtoBS(i)為半徑的圓和以節點i為中心、以節點i通信距離參數dR為半徑的圓的重合區域，這排除了節點向后傳輸數據的可能。

圖1 前向傳輸區域示意圖

在前向傳輸區域內選擇一個最終的節點作為節點的下一跳節點，引入節點度、剩余能量、節點間距、節點與匯聚節點的距離等參數，構建節點i到節點j的通信鏈路的前向傳輸因子FTF(ij)（Forward Transmission Factor）：

其中，Dback(j)為節點j的反向節點度（即由其節點度減去其可能的下一跳節點個數），E(j)為節點j當前的剩余能量，dtoBS(i)和dtoBS(j)為節點i和節點j到基站的距離，d(i,j)為節點i與節點j之間的距離。

1.4 鏈中成簇思想

如圖2（a）所示，鏈式結構層級眾多，導致時延較大，同時，每個節點都承擔有融合數據的任務，造成額外能量消耗，再者，鏈式結構無法考慮能量因素，低能量節點也進入鏈中，一旦某個節點過早消亡，鏈路即遭到破壞。圖2（b）和圖2（c）為不同能量條件下鏈中盡量成簇示意圖，即在鏈式結構基礎上，較為密集的節點或個別能量較低的節點，以簇的方式加入網絡。這種混合結構保證了數據傳輸距離趨向最近，而傳輸層次也較少，且參與數據融合的節點也較少，最重要的是可以將低能量的節點以簇內成員節點或者子節點的形式加入網絡，避免該節點進入主路徑后由于過快消亡后導致大片區域數據丟失。

圖2 鏈中盡量成簇示意圖

1.5 平均剩余能量估計

為提高能量消耗均衡性，便于節點了解自身剩余能量在全網絡中所處的水平，通常需要對節點的平均能量進行計算，但平均能量的計算需要統計全網的剩余能量信息，這對分布式路由算法是非常困難的，這里引入估計方法，對平均能量進行相應估計。首先粗略估計全網每一輪消耗的能量Eround

式（4）中，Etotal為全網初始總能量，r0為估計輪數，即網絡理論生存周期，在實驗過程中可采用遞歸的方法取得，這里不作論述。估計全網剩余能量的平均值為

其中，N為節點數目，r為實驗輪數。

2 半徑遞增有向成簇路由算法

根據本文算法的步驟，首先進行初始化；然后在半徑R0內組簇；然后若有節點尚未接入網絡則增加半徑，在新的半徑內組簇；最后直至所有節點接入網絡，算法結束。

2.1 初始化

算法開始時，各節點自動獲得一個唯一的節點ID，基站首先以額定的功率向全網廣播消息，節點根據接收消息的信號強度確定自身與基站的近似距離di-BS(i)［18］，并通過限定的功率與周圍節交換信息，分別確定半徑R0，2R0，3R0內的節點度Ddegree1，Ddegree2，Ddegree3，反向節點度Dback1，Dback2，Dback3，并更新鄰節點信息表、緩存表等信息，如圖3所示。

2.2 半徑R0內組簇

算法中，在半徑R0內選擇簇頭和半徑2R0以上選擇下一跳節點時，引入了一個能量閾值，即要求節點能量必須大于，才有可能被選為簇頭或者下一跳節點。這里，為平均能量估計值，由式（4）～式（5）得到，w為調節參數，取值范圍為［0，1］。

圖3 隨機分布的傳感器節點

根據初始化數據，采用投票機制競選簇頭。在未對全網節點劃分區域的情況下，各節點在包含自身在內的半徑R0范圍內，根據式（6）計算權值，將票投給權值最大的節點，使其成為備選簇頭，各備選簇頭統計自身被投票次數，并檢查半徑R0范圍內有無其它備選簇頭，若有，則再次進行權值比較，權值小的節點退出簇頭競選，若無，則宣布自身成為簇頭，并召集簇內成員。

其中，E(i)為節點剩余能量，為全網節點平均剩余能量，Ddegree1(i)為節點的節點度，w為調節系數。該權值綜合了節點能量和節點位置兩個因素，第一項反映了節點的能量因素，其對節點競選簇頭設置了一個閾值，在達到這個閾值的條件下，節點能量越高，權值也會越大；式中第二項反映了節點的位置因素，即節點的節點度越大，其成為簇頭的權值也會越大。

如圖4，節點7和節點8在半徑R0范圍內互為唯一鄰節點，在能量相同區別不大的情況下，由于節點8離基站更近，故而成為簇頭；又如節點6、節點9、節點10三個節點中，由于節點10的后向節點度大于節點6和節點9，更容易成為區域簇頭。

圖4 節點在半徑R0內組簇示意圖

2.3 半徑2R0范圍內組網

在半徑R0范圍內完成組簇的路由結構是不完整的，仍然存在較多的節點和簇頭未接入網絡，這些節點可以擴大組簇半徑至2R0進行組簇，其步驟和與前面相似。未接入網絡的節點i（或簇頭）查看半徑至2R0范圍內鄰節點信息，若存在距離基站更近的鄰節點j（或簇頭），則根據根據公式（7）確定一個節點作為自身的簇頭并加入。

該權值計算式的前提是節點i必須位于節點j的前向傳輸區域內（見圖1），即節點i必須位于以基站為中心、dtoBS(i)為半徑的圓和以節點i為中心、以通信距離參數dR=2R0為半徑的圓的重合區域，這排除了節點向后傳輸形成“回流”或“環路”的可能性。權值計算式的第一項為節點能量參考因素，它設置了一個閾值，即能量低于的節點不能成為備選節點；第二項為位置參考因素，它能保證更加靠近節點i和基站連線的節點具有更高的權值；第三項是基于盡量成簇思想（見圖2）的權重因子，它能保證反向節點度較大的節點同時接收更多的子節點，節省數據融合的成本，減少路由層次。圖5為節點在半徑2R0內組簇示意圖。

圖5 節點在在半徑2R0內組簇示意圖

針對仍未接入網絡的節點或者簇頭，繼續采取增加組簇半徑至3R0，4R0的方式，直至所有節點均接入網絡，構成一個連通的簇樹。如圖6是半徑為3R0時的網絡圖，圖7為最終路由結構。

圖6 節點在半徑3R0內組簇示意圖

圖7 最終路由結構圖

3 仿真實驗與參數分析

3.1 仿真實驗

仿真場景參數設置為：在邊長M=100 m的區域內隨機分布N=100個傳感器節點，節點初始能量E=0.5 J，部署后不移動，基站位于（150，50），其能量不受限制，初始成簇概率p=0.05，基準半徑R0=22 m，假設節點每次發送或接收數據長度為l=4 000 bits。在相同的條件下，對LEACH、EEUC和本案算法三者進行比較，得到三種算法死亡節點個數隨仿真輪數的變化圖，見圖8。

圖8 N=100時生命周期比較圖

由圖8可以看出，LEACH算法在750輪左右開始出現死亡節點，到1350輪左右全部節點死亡，時間跨度約為600輪；EEUC算法在1200輪左右時節點開始死亡，在1600輪左右全部死亡，跨度約為400輪；本案算法在1500輪左右出現第一個死亡節點，到1800輪左右節點全部死亡，時間跨度約為300輪。這說明新算法在能夠保證各節點的能量消耗速度更加平衡，即有能耗均衡性能上有較大提高。能量均衡性能提高帶來的直接結果是網絡生命周期的延長，尤其是第一個節點死亡的時間延遲效果明顯。在上述仿真條件下重復實驗50次，統計其第一個節點死亡時間（FD）和全部節點死亡時間（AD），得到如表數據，從數據結果可知，新算法在第一個節點死亡時間和全部節點死亡時間上比EEUC分別提高了17%、9%。

表1 網絡生命周期

修改仿真場景參數：在邊長M=100 m的方形區域內部署節點N=200個，其他條件不變，即不改變監控區域大小而將節點密度增加1倍，得到數據如圖9。與圖8相比，圖9所示各算法的生命周期均有所延長，這是由于當節點密度增加后，各節點間的通信距離減小，使得通信能耗也隨之降低。從網絡生命周期來看，本案算法比EEUC算法在FD和AD上分別提高約24%和9%。從時間跨度上來講，LEACH和EEUC算法相對于低密度節點場景均有一定程度的增加，這是由于隨著節點密度的增大，整個網絡的層次結構和簇成員數量也相應增加，致使簇頭能量消耗加快，使網絡能耗的均衡性能下降。而本案算法在節點密度增大時，第一個節點死亡和全部節點死亡的時間跨度增加較小，這說明算法在節點高密度條件下的能量均衡性能和能量效率更優。

圖9 N=200時生命周期比較圖

3.2 參數分析

此節分析了基準半徑R0與調節參數w對本文算法的影響。首先是對R0的分析。

半徑遞增有向成簇算法的提出中，引入了一個新的參數——基準半徑R0，算法的的一個核心內容是在半徑R0的范圍內組簇，R0直接決定了簇的大小和簇的數量，所以在應用和仿真中應該首先給出參數R0的值。在具體的應用與仿真中，由于監控區域的規模、節點的密度等條件的不同，R0的最優值并不是固定不變的。

在上述M=100 m，E=0.5J，基站（150，50）條件下，分別對N=100和N=200兩個場景仿真，R0從10 m到40 m按步長2 m遞增，對每個值進行10次實驗，得到其第一個節點死亡的平均時間（輪數）的變化，如圖10和圖11。

圖10 N=100時第一個節點死亡時間隨R0變化圖

圖11 N=200時第一個節點死亡時間隨R0變化圖

從圖10和圖11中可以看到，當基準半徑R0的取值從10 m到25 m左右時，第一個節點死亡的時間逐漸延遲，這是因為隨著基準半徑R0的增大，簇類結構在路由結構中所占的比例也越來越高，分簇路由的優勢在算法中的優勢得到更多體現。當基準半徑R0的取值從25 m左右繼續增大時，第一個節點死亡的時間是逐漸提前的，尤其是在R0=30 m左右時，出現斷崖式的下降，原因在于隨著基準半徑R0的繼續增加，分簇結構在網絡路由中所占比例過大，擠壓了鏈式結構的比重，前文所述的前向傳輸思想的應用范圍逐漸縮小，導致網絡生命周期大大縮短。尤其是當R0=30 m以后，路由結構中簇在直徑達到60 m以上，這跟LEACH算法已經十分類似。

通過對比還可以看到，圖11比圖10在相同的基準半徑條件下第一個節點死亡的時間均有所延遲，即網絡生命周期延長，原因是在于節點密度增大后，節點間的通信距離減小，通信能耗也相應減小，利于延長網絡生命周期。另外，在節點數量N=100條件下，基準半徑在20 m～24 m左右時第一個節點死亡時間最遲，最佳基準半徑為R0=22 m；在節點數量N=200條件下，基準半徑在22 m～26 m左右時網絡生命周期是長，最佳基準半徑R0=24 m。說明隨著節點密度的增大，最佳基準半徑也有所增大，這是由于密度增大時，相同半徑內的鄰節點也會越多，各個簇內的成員節點也越多，由于數據融合而節省的能量也更多，在相同總能量的條件下，節省的這部分能量可以使節點將數據發送到更遠的距離，基準半徑的值也相應的增大。

然后分析了w對算法的影響。w調節參數，取值范圍為［0，1］。w越小，對被選節點能量要求越低，那么符合條件的備選節點數量也就越多，反之亦然。為確定w對算法的影響，采用前述M=100 m仿真場景，令w從0按步長0.05增加到1時，記錄其第一個節點死亡的平均時間（輪數）的變化，如圖12。

圖12 第一個節點死亡時間隨參數w變化圖

從圖中可知，w從0增加到0.2的過程中，第一個節點死亡的平均時間逐漸延遲，這是由于算法對簇頭或父節點具有一定的能量要求，過低能量的節點擔任簇頭或父節點會快速死亡，增加網絡重組頻率；隨著w從0.2繼續增大，越來越多的節點達不到該能量閾值，使得一些能量較高但位置不合理的節點被選為簇頭或下一跳節點，增加了節點間的通信距離，從而影響了網絡生命周期，所以0.2為在該應用場景條件下的最優值。

4 結束語

文中通過對分簇路由和鏈式路由的優、缺點進行分析，提出一種基于半徑遞增有向成簇的無線傳感器網絡路由算法。算法按照“向基站方向成鏈，鏈中盡量成簇”的基本思路，生成一種簇、鏈、樹相結合的混合路由結構。實驗證明，新算法能夠有效優化路由結構，在能量效率和均衡性能兩個方面更具優勢，能夠將網絡生命周期提高9-17%，且在傳感器節點高密度部署的無線傳感器網絡中表現更優。

［1］Akvildiz I F，Su W，Sankarasubramaniam Y，et al.A Survey on Se?nor Networks［J］.IEEE Communications Magazine，2002，40（8）：102-114.

［2］倪文亞，劉慶威，劉漫丹.基于能量和距離的無線傳感器網絡路由協議［J］.2015，41（1）：84-88.

［3］靳淑娟.無線傳感器網絡中的能量均衡路由協議研究［D］.大連：大連理工大學，2009.

［4］王汝傳，孫力娟，黃海平，等.無線傳感器網絡中間件技術［M］.北京：科學出版社，2011.

［5］Heinzelman W，Handrakasan A，Alakrishnan H.Energy-Efficient Communication Protocol for Wireless Micro Sensor Networks［C］//Proceedings of the Hawaii Internationnal Conference on System Sciences，LosAlamitos，CA，USA：IEEE Computer Society，2000：3005-3014.

［6］Lindsey S，Raghavendra C.PEGASIS：Power Efficient Gathering in Sensor Information Systems［C］//Proceedings of the IEEE Aero?space Conference，Vol.3，May 2002.1125-1130.

［7］Ossama Y，Sonia F.HEED：A Hybird，Energy-Efficient，Distribut?ed Clustering Approach for Ad Hoc Sensor Networks［J］.IEEE Transactions on Mobile Computing，2004，3（4）：366-379.

［8］Manjeshwar A，Agrawal D P.TEEN：A Routing Protocol for En?hanced Efficiency in Wireless Sensor Networks［C］//Proceedings of the15th International Parallel and Distributed Processing Sym?posium（IPDPS），San Francisco，2001：2009-2015.

［9］李成法，陳貴海，葉懋，等.一種基于非均勻分簇的無線傳感器網絡路由協議［J］.計算機學報，2007，30（1）：27-36.

［10］劉鐵流，巫永群.基于能量優化的無線傳感器網絡分簇路由算法研究［J］.傳感技術學報，2011，24（5）：764-770.

［11］嚴英，郭麗，許建真.一種基于LEACH與PEGASIS協議的分層成鏈優化路由算法［J］.傳感技術學報，2011，24（9）：1311-1316.

［12］劉東江，賈卓生.基于分簇的無線傳感器網絡路由協議的研究［J］.計算機學報，2012，39（10）：23-38.

［13］史久根，胡小博.高效節能的無線傳感器網絡數據收集協議［J］.電子測量與儀器學報，2012（5）：437-445.

［14］Heinzelman W B，Chandrakasan A，Balakrishman H.An Applica?tion-Specific Protocol Architecture for Wireless Microsensor Net?works［J］.IEEE Transactions on Wireless Communications，2002，1（4）：660-670.

［15］Soro S，Einzelman W B.Prolonging the Lifetime of Wireless Sen?sors Networks Via Unequal Clustering［J］.Proc of the 19th IEEE International on Parallel and Distributed Processing Symposium.San Francisco：IEEE Computer Society Press，2005：236-240.

［16］張德干，張曉丹，李光.無線傳感與路由技術［M］.北京：科學出版社，2013.

［17］周則順，李臘元，許毅，等.無線傳感器網絡中能量有效分簇路由算法［J］.武漢理工大學學報，2011，35（6）：1157-1160.

［18］韓萬強，劉云.WSN中基于分簇的路由改進協議［J］.計算機工程，2012，38（5）：105-113.