基于不等簇半徑分簇的無線傳感器網(wǎng)絡(luò)能量空洞避免

楊宛楠，陳志剛，趙明

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

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

1 網(wǎng)絡(luò)模型

1.1 網(wǎng)絡(luò)結(jié)構(gòu)模型

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

圖1 網(wǎng)絡(luò)結(jié)構(gòu)模型Fig.1 Network model structure

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

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

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

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

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

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

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

2.1 能耗分析

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

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

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

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

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

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

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

證畢。

2.2 分簇策略理論分析

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

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

將式(3)帶入上式，得

又因?yàn)?/p>

由式(2)，可得

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

即為

所以，

由式(1)，可得：

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

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

證畢。

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

證明：由命題知

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

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

上式顯然成立，證畢。

定理4：當(dāng)內(nèi)層簇與相鄰?fù)鈱哟氐拇匕霃揭缘缺萹(q＞1)遞增時，滿足各簇簇頭能量消耗均衡條件。

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

證畢。

由定理4 可知，采用內(nèi)層簇與相鄰?fù)鈱哟氐拇匕霃揭缘缺冗f增的策略進(jìn)行分簇，可達(dá)到各層簇頭能耗平衡，避免網(wǎng)絡(luò)空洞問題。

3 仿真結(jié)果與分析

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)論

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

(2) 采用等比遞增的簇半徑分簇策略，各簇根據(jù)網(wǎng)絡(luò)實(shí)際情況動態(tài)構(gòu)建，對前期的網(wǎng)絡(luò)拓?fù)湓O(shè)計和節(jié)點(diǎn)部署工作的依賴性較低，具有較強(qiáng)的適應(yīng)性和廣泛的適用性。

[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)絡(luò)中節(jié)點(diǎn)非均勻分布的能量空洞問題[J]. 計算機(jī)學(xué)報, 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)絡(luò)中基于可調(diào)發(fā)射功率的能量空洞避免[J]. 計算機(jī)學(xué)報, 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] 劉安豐, 任炬, 陳志剛. 異構(gòu)傳感器網(wǎng)絡(luò)能量空洞分析與避免研究[J]. 軟件學(xué)報, 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.