楊宛楠，陳志剛，趙明

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

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

1 網(wǎng)絡模型

1.1 網(wǎng)絡結構模型

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

圖1 網(wǎng)絡結構模型Fig.1 Network model structure

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

1.2 網(wǎng)絡能耗模型

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

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

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

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

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

2.1 能耗分析

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

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

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

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

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

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

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

證畢。

2.2 分簇策略理論分析

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

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

將式(3)帶入上式，得

又因為

由式(2)，可得

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

即為

所以，

由式(1)，可得：

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

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

證畢。

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

證明：由命題知

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

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

上式顯然成立，證畢。

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

根據(jù)定理3，可得

證畢。

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

3 仿真結果與分析

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

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

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

當網(wǎng)絡中出現(xiàn)有簇頭在臨近內層中無法找到中繼簇頭完成數(shù)據(jù)轉發(fā)時，此時網(wǎng)絡分離，宣告網(wǎng)絡死亡。

3.1 節(jié)點死亡時間與網(wǎng)絡壽命分析

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

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

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

3.2 網(wǎng)絡能耗分析

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

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

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

3.3 節(jié)點死亡位置分析

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

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

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

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

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

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

4 結論

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

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

[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] 吳小兵, 陳貴海. 無線傳感器網(wǎng)絡中節(jié)點非均勻分布的能量空洞問題[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] 曾志文, 陳志剛, 劉安豐. 無線傳感器網(wǎng)絡中基于可調發(fā)射功率的能量空洞避免[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] 劉安豐, 任炬, 陳志剛. 異構傳感器網(wǎng)絡能量空洞分析與避免研究[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.