基于不等簇半徑分簇的無線傳感器網絡能量空洞避免

楊宛楠，陳志剛，趙明

(中南大學 信息科學與工程學院，湖南 長沙，410083)

在無線傳感器網絡中，由于數據是基于多對一(many-to-one)的多跳路由通信模型進行中繼和轉發的，節點既產生數據也轉發數據[1]，網絡中通常存在能量消耗不均衡的現象，靠近Sink 的節點由于要轉發更多的外層數據而過早地耗盡能量死亡，死亡節點附近的節點因此需要中繼已死亡節點的數據轉發任務，從而進一步加快這一區域其他節點的死亡速度，形成漏斗效應(funneling effect)[2]，使得外層其他節點的數據不能傳送到Sink，導致整個網絡過早死亡或陷于癱瘓，縮短了網絡壽命。這一現象被稱為無線傳感器網絡的能量空洞問題(Energy Hole Problem)[3-6]。有關研究表明，能量空洞形成后，網絡中的剩余能量高達90%[7]。因此，如何均衡網絡負載，延長網絡壽命，提高網絡的能量利用率，具有重要的應用前景與實際價值。國內外研究人員己經提出許多有效的無線傳感器網絡的能量空洞避免方法[2-5]。吳小兵等[8]論述了離Sink 不同距離處的節點密度比例關系，Lian 等[9]通過在Sink 附近區域部署初始能量更大的節點來避免能量空洞。曾志文等[10]給出在滿足應用延遲前提下使網絡壽命最長的節點發射功率選擇算法。Wang 等[11]使用一個移動中繼節點來延長網絡生存周期。Luo 等[12]證明若采用移動Sink 方式，Sink 沿網絡邊緣移動最符合節能要求。Soro 等[13]首次運用非均勻分簇思想來解決能量空洞問題，證明非均勻分簇算法[13-14]能夠起到使網絡能量消耗均勻，延長網絡壽命的作用。Soro等[13]的研究思想主要為通過減少靠近Sink 節點的簇成員數目，來降低簇內數據收集能耗，從而預留更多的能量進行簇間的數據轉發，但各簇頭為超級節點，且位置是事先計算好的，無法動態建簇，適應性較弱。本文在其研究基礎上，從理論分析出發，提出基于遞增簇半徑的非均勻動態分簇策略，有效解決了距離Sink 不同距離的簇頭簇內通信與簇間通信能量消耗不平衡的問題，均衡了網絡負載，延長了網絡壽命。

1 網絡模型

1.1 網絡結構模型

N 個傳感器節點以密度ρ 隨機均勻分布在1 個半徑為R 的圓形監測區域中，Sink 位于圓心，對各節點進行非均勻分簇，形成周期性的數據收集分簇網絡。從內向外，相鄰的簇半徑等比遞增，處于同一層中的各簇簇半徑相等，如圖1 所示。用Ci表示位于第i 層的簇，各簇簇頭居于簇中心位置，Ri表示第i 層圓環外邊界至Sink的距離(同時也是第i+1層圓環內邊界至Sink 的距離)，di表示Ci的簇頭至Sink 的距離，τi為Ci的簇半徑。圖1 中陰影部分所示即為處于第3 層的1 個簇C3。節點可以調整其發射功率以降低能量消耗，例如，Berkeley Motes 節點具有100 個發射功率等級[14]。

圖1 網絡結構模型Fig.1 Network model structure

每一輪生命周期由Sink 廣播建簇信息開始，各節點成簇后通過單跳通信向簇頭發送數據，各簇頭負責簇內數據收集以及簇外數據轉發，通過多跳通信將數據發送至Sink，當全部數據均轉發至Sink 后，即1次全局數據收集完成，各簇解散，1 輪生命周期結束。

1.2 網絡能耗模型

采用典型的能量消耗模型[8]，發送數據的能量消耗公式如式(1)所示，接收數據的能量消耗公式如式(2)所示。

式中：Eelec表示發射電路損耗的能量，若傳輸距離小于閾值do，功率放大損耗采用自由空間模型，當傳輸距離大于等于閾值do時，采用多路徑衰減模型；εfs和εamp分別為這2 種模型中功率放大所需的能量。ER(l)為節點接收l bit 的數據消耗的能量。在本文中，以上參數的具體設置取自文獻[15]，如表1 所示。

網絡中Sink 沒有能量限制。每個節點具有相同的初始能量，在1 輪生存周期中產生并向簇頭發送1 bit數據。處于非最外層的簇(Ci|i≠R)需向Sink 轉發自身以及來自外層簇(Cj|(i+1)≤j≤R)的數據。以圖1 中的C3為例，C3的簇頭除承擔簇內節點的數據收集與轉發任務外，還承擔由射線OC 與射線OD 所確定的扇形區域外層簇的數據轉發任務。

2 不等簇半徑分簇策略理論分析

本節從能量的角度對在無線傳感器網絡中采用基于不等簇半徑分簇的策略進行理論分析，證明根據各節點至Sink 距離的由近至遠，采用依次等比遞增的不等簇半徑進行分簇，實現整個網絡負載均衡，緩解能量空洞問題是可能的。

2.1 能耗分析

用Ni表示簇Ci中傳感器節點的數目；Ei表示簇Ci中簇頭在1 輪生命周期中的能耗，簇Ci中簇頭發送1 bit 數據消耗能量ei1，接收1 比特數據消耗能量ei2；假設各簇中數據由簇頭收集后，能夠經過1 跳傳遞給相鄰的內層簇，最終經過i 跳后到達Sink。

定理1：簇Ci中的簇頭在每一輪生命周期中，消耗的能量為

證明：處于最外層的簇CR僅對簇內數據進行收集與轉發，沒有外層簇間數據的轉發任務，所以，簇CR在1 輪生命周期中簇頭的能量消耗為

其他處于非最外層的簇既要對簇內數據進行收集和轉發，還要對來自外層的簇間數據進行收集和轉發。所以，在1 輪生命周期中，次外層簇CR-1中的簇頭能量消耗為

在1 輪生命周期中，簇CR-2中的簇頭能量消耗為

由以上2 式可得：在1 輪生命周期中，非最外層簇Ci中的簇頭能量消耗為

經驗證，ER也符合上式，所以簇Ci中的簇頭在1輪生命周期中的能量消耗為

證畢。

2.2 分簇策略理論分析

定理2：當各簇簇頭能量消耗均衡時，各層外邊界至Sink 的距離滿足不等式：

證明：各簇簇頭能量消耗均衡，即Ei=Ei-1。

將式(3)帶入上式，得

又因為

由式(2)，可得

將式(11)～(13)帶入式(10)，可得

即為

所以，

由式(1)，可得：

將上帶入式(16)，可得：

無論d＜d0還是d≥d0，化簡后均為

證畢。

定理3：當各簇所在圓環的外邊界至Sink 的距離與內邊界至Sink 的距離以等比q(q＞1)遞增時，滿足各簇簇頭能量消耗均衡條件。

證明：由命題知

將式(20)帶入式(9)，可得：

化簡，可得：Ri-2＜Ri-1。

上式顯然成立，證畢。

定理4：當內層簇與相鄰外層簇的簇半徑以等比q(q＞1)遞增時，滿足各簇簇頭能量消耗均衡條件。

根據定理3，可得

證畢。

由定理4 可知，采用內層簇與相鄰外層簇的簇半徑以等比遞增的策略進行分簇，可達到各層簇頭能耗平衡，避免網絡空洞問題。

3 仿真結果與分析

基于OMNet++4.1 對理論分析結論進行實驗場景仿真，并選用經典的固定簇半徑分簇的LEACH 算法進行仿真結果對比。

將1 000 個節點均勻分布在半徑為400 m 的圓形網絡中，LEACH 算法采用固定的簇半徑50 m 成簇；本文的能量空洞避免算法稱為UCR 算法，采用初始簇半徑為50 m，從Sink 至最外層相鄰層之間的簇半徑以2.5 為系數等比遞增成簇。其他參數設置參如表1所示。

實驗場景的每輪生命周期分為簇內數據收集和簇間數據轉發2 個階段。在簇內收據收集階段，2 種算法分別按各自策略成簇，簇內采用TDMA 協議對其覆蓋范圍內的節點進行數據收集。在簇間數據轉發階段，各簇頭采用CDMA 協議進行數據傳輸，將自己簇內數據以及外層簇間數據轉發至內層臨近簇頭。

當網絡中出現有簇頭在臨近內層中無法找到中繼簇頭完成數據轉發時，此時網絡分離，宣告網絡死亡。

3.1 節點死亡時間與網絡壽命分析

2 種策略下每輪節點死亡之數目對比見圖2。由圖2 可知：當網絡出現分離宣告死亡時，基于LEACH算法網絡中還有524 個節點未死亡，占節點總數的52.4%，網絡生存周期為432 輪，可知能量空洞問題對該網絡的生命周期有較大影響，因為能量空洞較早出現，致使在還有超過1/2 節點存活的情況下，網絡就已經分離而無法繼續傳輸數據，導致網絡死亡。

而在基于UCR 算法的網絡中，當網絡分離死亡時，僅有61 個節點未死亡，占節點總數的6.1%，網絡生存周期為718 輪。可知，相對于固定簇半徑分簇，不等簇半徑分簇策略可以有效均衡網絡中各簇頭負載，從而延緩能量空洞現象的出現，延長網絡壽命約66%。

圖2 2 種策略下每輪節點死亡數目對比Fig.2 Comparison of node numbers of deaths per round under two strategies

3.2 網絡能耗分析

2 種策略下每輪能量消耗情況對比見圖3。由圖3可見：當網絡出現分離宣告死亡時，基于LEACH 算法網絡中還有約40%的剩余能量。而在基于UCR 算法的網絡中，當網絡分離死亡時，還有約3%的剩余能量。這表明相對于固定簇半徑分簇，不等簇半徑分簇策略可以有效均衡網絡的能量負載。

同時，由圖3 所示線條走勢可知：在每一輪生命周期中，基于不等簇半徑分簇的網絡能量消耗要比基于固定簇半徑分簇的網絡能量消耗大。這主要是因為基于不等簇半徑分簇的網絡，在網絡外層的成簇半徑較大，甚至簇半徑超過了傳輸閾值do，導致簇內數據收集與簇間數據轉發采用了多路徑衰減能耗模型，增加了能量開銷，但卻有效地避免了網絡中能量空洞的出現。

圖3 2 種策略下每輪能量消耗情況對比Fig.3 Comparison of energy consumption per round under two strategies

3.3 節點死亡位置分析

圖4 與圖5 所示分別為2 個網絡各輪節點死亡信息統計圖，其中X 軸代表節點在圓形分布區域中的X坐標，Y 軸代表節點在圓形分布區域中的Y 坐標，即X-Y 平面為節點分布平面；Z 軸為各節點的死亡輪數，由上往下輪數增加。

上層的波峰區域表示處于該位置的節點在較早的輪數中就已死亡，主要為Sink 附近區域以及各層簇頭所在區域；下層的波谷區域表示處于該位置的節點在網絡分離死亡時還未死亡。

圖4 固定簇半徑分簇策略下每輪死亡節點位置信息Fig.4 Death node position information per round using equivalent cluster-radius clustering

在固定簇半徑分簇網絡中，各簇頭的簇內數據收集能量消耗基本相同，而簇間數據轉發能量消耗差距較大，距離Sink 越近的節點承擔越多的外層數據轉發任務，整體能量消耗既大且快，因此，圖4 中Sink 附近區域顏色最深，由Sink 附近區域向外，各層簇頭所在的上部波峰區域顏色依次變淡，說明距離Sink 越近的內層簇頭越早死亡，距離Sink 越遠的外層簇頭越晚死亡，甚至最外層的一些簇頭在網絡分離死亡時仍未死亡。正是由于各層簇頭節點死亡時間的不均衡，導致了能量空洞出現，內層簇頭多在較早輪數內死亡；而此時外層簇頭還未死亡，仍具有較大的數據轉發需求，進一步加劇內層簇頭能量消耗，促使內層簇頭死亡，形成能量空洞，導致網絡分離死亡。在網絡死亡時，大量節點存活，主要集中在外層區域，即為圖4中的底部波谷區域。

圖5 不等簇半徑分簇策略下每輪死亡節點位置信息Fig.5 Death node position information per round using unequal cluster-radius clustering

在不等簇半徑分簇網絡中，不同層間的簇頭簇內數據收集能量消耗不同，簇間數據轉發能量消耗也不同。距離Sink 較近的節點依然承擔較多的外層數據轉發任務，但由于其簇半徑較小，簇內數據收集能耗較小。距離Sink 較遠的節點，承擔較少的簇間數據轉發任務，但由于其簇半徑較大，簇內數據收集能耗較大。整體而言，不等簇半徑分簇網絡中的不同層簇頭節點整體能量消耗基本相同，所以，圖5 中Sink 附近以及各層簇頭所在的藍色區域顏色深度基本一致。正是由于各層簇頭節點的死亡節奏一致，保證了網絡數據的收集與轉發，有效避免了能量空洞的出現。

4 結論

(1) 采用簇半徑不等的非均勻分簇策略，對比固定簇半徑分簇策略，可實現各層簇頭的能量均衡消耗，提高能量使用效率，避免能量空洞的產生，延長網絡壽命。

(2) 采用等比遞增的簇半徑分簇策略，各簇根據網絡實際情況動態構建，對前期的網絡拓撲設計和節點部署工作的依賴性較低，具有較強的適應性和廣泛的適用性。

[1] Akyildiz I F, Su W, Sankarasubramaniam Y, et al. A survey on sensor networks[J]. IEEE Communications Magazine, 2002,40(8): 102-114.

[2] Cheng T E，Bajcsy R. Congestion control and fairness for many-to-one routing in sensor networks[C]//Proc of ACM SenSys'04, Baltimore, USA: ACM, 2004: 148-161.

[3] Wu X B, Chen G H, DAS S K. Avoiding energy holes in wireless sensor networks with nonuniform node distribution[J]. IEEE Transactions on Parallel and Distributed Systems, 2008, 19(5):710-720.

[4] Olariu S, Stojmenovic I. Design guidelines for maximizing lifetime and avoiding energy holes in sensor networks with uniform distribution and uniform reporting[C]//Proc of the IEEE INFOCOM. New York, USA: IEEE Communications Society,2006: 1-12.

[5] Li J, Mohapatra P. An analytical model for the energy hole problem in many-to-one sensor networks[C]//Proc of IEEE Conference on Vehicular Technology, 2005: 2721-2725.

[6] Lian J, Naik K, Agnew G. Data capacity improvement of wireless sensor networks using non-uniform sensor distribution[J]. International Journal of Distributed Sensor Networks, 2006, 2(2): 121-145.

[7] Li J, Mohapatra P. Analytical modeling and mitigation techniques for the energy hole problem in sensor networks[J].Pervasive and Mobile Computing, 2007, 3(3): 233-254.

[8] 吳小兵, 陳貴海. 無線傳感器網絡中節點非均勻分布的能量空洞問題[J]. 計算機學報, 2008, 31(2): 253-261.WU Xiaobing, CHEN Guihai. The energy hole problem of nonuniform node distribution in Wireless Sensor Networks[J].Chinese Journal of Computers, 2008, 31(2): 253-261.

[9] Lian J, Chen L, Naik K, et al. Modeling and enhancing the data capacity of Wireless Sensor Networks[C]//Proc of the IEEE Monograph on Sensor Network Operations, IEEE Press, 2004:91-183.

[10] 曾志文, 陳志剛, 劉安豐. 無線傳感器網絡中基于可調發射功率的能量空洞避免[J]. 計算機學報, 2010, 33(1): 12-22.ZENG Zhiwen, CHEN Zhigang, LIU Anfeng. Energy-Hole avoidance for WSN based on adjust transmission power[J].Chinese Journal of Computers, 2010, 33(1): 12-22.

[11] Wang W, Srinivasan V, Chua KC. Using mobile relays to prolong the lifetime of wireless sensor networks[C]//Proc of ACM MobiCom. Cologne, Germany, 2005: 270-283.

[12] Luo J, Hubaux J P. Joint mobility and routing for lifetime elongation in wireless sensor networks[C]//Proc of the IEEE INFOCOM. Seattle, WA: IEEE Press, 2005: 819-830.

[13] Soro S, Heinzelman W. Prolonging the lifetime of wireless sensor networks via unequal clustering[C]//Proc of the 5th International Workshop on Algorithms for Wireless, Mobile, Ad Hoc and Sensor Networks. Denver: ACM, 2005: 236-240.

[14] Chen G, LI C F, Ye M, et al. An unequal cluster-based routing strategy in wireless sensor networks[J]. Wireless Networks (JS),2009, 15(2): 193-207.

[15] 劉安豐, 任炬, 陳志剛. 異構傳感器網絡能量空洞分析與避免研究[J]. 軟件學報, 2012, 23(9): 2438-2448.LIU Anfeng, RENG Ju, CHEN Zhigang. Analysis and Avoidance of Energy Hole Problem in Heterogeneous Wireless Sensor Networks[J]. Journal of Software, 2012, 23(9): 2438-2448.