放置中繼節(jié)點解決無線傳感器網(wǎng)絡(luò)能量空洞問題

傅菊平 ，王東方 ，齊小剛

（1.西安電子科技大學 數(shù)學科學系，陜西 西安 710071；

2.西安電子科技大學 綜合業(yè)務(wù)網(wǎng)國家重點實驗室，陜西 西安 710071）

放置中繼節(jié)點解決無線傳感器網(wǎng)絡(luò)能量空洞問題

傅菊平1，2，王東方1，2，齊小剛1，2

（1.西安電子科技大學 數(shù)學科學系，陜西 西安 710071；

2.西安電子科技大學 綜合業(yè)務(wù)網(wǎng)國家重點實驗室，陜西 西安 710071）

在無線傳感器網(wǎng)絡(luò)中，傳感器節(jié)點往往采用多跳的方式進行數(shù)據(jù)傳輸，造成了基站sink周圍節(jié)點能量消耗過快，易形成能量空洞問題。針對這個問題，提出了一種改變中繼節(jié)點能量的能耗均衡策略，即將中繼節(jié)點的能量加大為原傳感器節(jié)點能量的數(shù)倍，同時減少中繼節(jié)點的數(shù)量。理論分析和仿真結(jié)果表明，這種方法有效地解決了能量空洞問題?？紤]到成本和數(shù)據(jù)冗余問題，在中繼節(jié)點數(shù)為理想數(shù)目的3/5時，網(wǎng)絡(luò)能耗沒有太大的提高，即放置少量的中繼節(jié)點也能達到能耗均衡的目的。

無線傳感器網(wǎng)絡(luò)；能量空洞；中繼節(jié)點；能耗均衡

無線傳感器網(wǎng)絡(luò) WSNs（Wireless Sensor Networks）是由部署在監(jiān)測區(qū)域內(nèi)大量的廉價微型傳感器節(jié)點組成，通過無線通信方式組成的一個多跳的自組織的網(wǎng)絡(luò)系統(tǒng)。其主要功能是對周邊環(huán)境信息進行采集和管理,并將感知到的數(shù)據(jù)發(fā)送到基站進行進一步的處理[1]。無線傳感器網(wǎng)絡(luò)節(jié)點體積小、價格低，在工業(yè)、農(nóng)業(yè)、交通、軍事、安全、醫(yī)療、空間探測，以及家庭和辦公環(huán)境等眾多領(lǐng)域廣泛應(yīng)用。

與傳統(tǒng)的Ad hoc網(wǎng)絡(luò)相比，節(jié)點電源能量有限、通信能力有限以及計算和存儲能量有限是無線傳感器網(wǎng)絡(luò)最大的特點，也是制約路由協(xié)議的主要因素。因此，無線傳感器網(wǎng)絡(luò)的能效利用非常重要，傳感器節(jié)點往往采用多跳的方式，一些節(jié)點既能轉(zhuǎn)發(fā)數(shù)據(jù)又能產(chǎn)生數(shù)據(jù)[2]。而且，離sink近的節(jié)點消耗更多的能量，因此這些節(jié)點更容易過早的死亡。參考文獻[3]中用理論和計算機模擬證明：與sink距離越近，節(jié)點消耗的能量越快。在參考文獻[4]中，將這種因部分節(jié)點過早耗盡自身能量導致網(wǎng)絡(luò)原有覆蓋區(qū)域缺失或者數(shù)據(jù)無法送達sink節(jié)點的現(xiàn)象稱作“能量空洞”現(xiàn)象。因此，如何解決能量空洞問題，延長網(wǎng)絡(luò)生命周期，成為當前無線傳感器網(wǎng)絡(luò)研究中的一個熱點問題。

1 研究現(xiàn)狀

針對無線傳感器網(wǎng)絡(luò)能量空洞問題，近年來提出了許多解決方案。參考文獻[5]首先提出一個數(shù)學模型用于解決無線傳感器網(wǎng)絡(luò)中的能量空洞問題。文中假定一個圓形網(wǎng)絡(luò)中節(jié)點均勻分布，從網(wǎng)絡(luò)流的角度出發(fā)，分析了數(shù)據(jù)壓縮和融合策略的優(yōu)勢。但是sink附近節(jié)點所承擔的轉(zhuǎn)發(fā)任務(wù)依然很重。在參考文獻[4]中作者提出將節(jié)點放置于圓形區(qū)域中，并分成若干個半徑遞增的圓環(huán)，證明了如果網(wǎng)絡(luò)中的節(jié)點數(shù)目從圓環(huán)CR-1到最內(nèi)圓環(huán) C1以等比 q（q＞1）遞增，且圓環(huán) CR和圓環(huán) CR-1中的節(jié)點數(shù)目比為1/（q-1），則在網(wǎng)絡(luò)中能夠?qū)崿F(xiàn)次優(yōu)的能耗均衡。這種策略量化了網(wǎng)絡(luò)中相鄰環(huán)間的節(jié)點數(shù)目，在此基礎(chǔ)上可以算出圓環(huán)間的節(jié)點數(shù)目關(guān)系，模擬分析顯示了使用這種節(jié)點非均勻分布策略達到了次優(yōu)的能耗效率，網(wǎng)絡(luò)中僅有非常小的能量被浪費。但是，非均勻策略只是在理論上有一定的可行性，可以想象，非均勻分布策略同時伴隨著一些網(wǎng)絡(luò)開銷，在sink節(jié)點周圍分布節(jié)點密度較大，只有當傳感器節(jié)點能夠低成本大規(guī)模生產(chǎn)時，這種策略才有可能實現(xiàn)。因此，這種策略并不能從根本上解決能量空洞問題。

[6]提出了采用放置中繼節(jié)點方式解決能量空洞問題。文中提到的中繼節(jié)點只具有接收數(shù)據(jù)和轉(zhuǎn)發(fā)數(shù)據(jù)的功能，而不具有產(chǎn)生數(shù)據(jù)的能力，而且理論分析和仿真結(jié)果表明，這種方式延長了網(wǎng)絡(luò)的生命周期。但是因為能量空洞問題導致sink周圍節(jié)點能耗大，因此，在sink節(jié)點的周圍要放置更多的節(jié)點才能使能耗均衡，但是理論值表明，當最內(nèi)層放置的中繼節(jié)點數(shù)幾乎等于整個網(wǎng)絡(luò)放置的傳感器節(jié)點總數(shù)時，才能達到能耗均衡，這在實際應(yīng)用中很難實現(xiàn)，而且會造成大量數(shù)據(jù)冗余和網(wǎng)絡(luò)擁塞，導致不必要的浪費。

因此，本文提出改變中繼節(jié)點的能量來解決能量空洞問題。假設(shè)中繼節(jié)點能量為傳感器節(jié)點能量的數(shù)倍，進而通過理論計算和仿真分析來確定中繼節(jié)點的個數(shù)，從而達到網(wǎng)絡(luò)能耗均衡的目的。

2 算法提出

2.1 符號說明

R——節(jié)點分布區(qū)域網(wǎng)絡(luò)半徑；

e——節(jié)點的初始能量；

λ——網(wǎng)絡(luò)在單位區(qū)域內(nèi)生成數(shù)據(jù)的速度；

T——發(fā)送單位數(shù)據(jù)消耗的能量；

E——接收單位數(shù)據(jù)消耗的能量；

n——網(wǎng)絡(luò)中初始節(jié)點個數(shù)；

ki——第i層圓環(huán)中加入的中繼節(jié)點個數(shù)；

r——節(jié)點的發(fā)射半徑，也為圓環(huán)的寬度，為R的整數(shù)分之一；

R/r——網(wǎng)絡(luò)總層數(shù)。

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

2.3 理論分析

從網(wǎng)絡(luò)模型的建立過程來看，可以知道最外層節(jié)點數(shù)為：

因為最外層節(jié)點只發(fā)送數(shù)據(jù)，不用轉(zhuǎn)發(fā)和接收數(shù)據(jù)，故最外層節(jié)點平均負載可求為（表示最外層面積）：

由于該層節(jié)點既要接收其外層節(jié)點的數(shù)據(jù)包，也要轉(zhuǎn)發(fā)本層及外層所有節(jié)點的數(shù)據(jù)包，故各個節(jié)點平均負載可求為：

由于第一層節(jié)點的平均負載最大，最外層負載最小，故在第一層中加入中繼節(jié)點使最內(nèi)層節(jié)點平均負載等于最外層負載。設(shè)最內(nèi)層加入k1個中繼節(jié)點，則得到等式：

同理，若第i層加入ki個中繼節(jié)點，則：

由上述推導，得到了各個圓環(huán)所放置的中繼節(jié)點數(shù)目。

3 仿真分析

3.1 仿真計算

在仿真過程中，用到參考文獻[7]中的能量公式及表1中的數(shù)據(jù)。

表1 仿真數(shù)據(jù)一覽表

節(jié)點接收數(shù)據(jù)消耗的能量：E=er·B

節(jié)點發(fā)送數(shù)據(jù)消耗的能量：T=（et+eddij4）B，其中dij為節(jié)點i與j之間的距離。

此時，將 dij近似為 r，從 2.3節(jié)中的公式推導可以算出，每個圓環(huán)內(nèi)放置的節(jié)點數(shù)從最內(nèi)層到次外層分別為 100、88、67、38，但是可以看出最內(nèi)層放置的中繼節(jié)點數(shù)是原來所放置傳感器節(jié)點的總和，這在實際中是很難實現(xiàn)的。所以想到能否通過加大中繼節(jié)點的能量來減少中繼節(jié)點的個數(shù)，在下面的仿真過程中，將中繼節(jié)點的能量加到原來的2倍、4倍和5倍，而各個圓環(huán)內(nèi)的中繼節(jié)點數(shù)分別減少為原來的1/2、1/4和1/5，即最內(nèi)層節(jié)點數(shù)分別為 50、25和 20，其他層節(jié)點數(shù)按上述比例放置。在整個過程中，采用隨機產(chǎn)生一個源節(jié)點，并運用最短路徑，以多跳的方式來進行數(shù)據(jù)轉(zhuǎn)發(fā)。

3.2 仿真結(jié)果

圖2是在網(wǎng)絡(luò)放置不同能量中繼節(jié)點的情況下，隨機產(chǎn)生100個拓撲結(jié)構(gòu)后，在網(wǎng)絡(luò)生命周期結(jié)束時，各個圓環(huán)內(nèi)節(jié)點消耗的平均能量。從圖中可以看出當加入中繼節(jié)點后，盡管中繼節(jié)點的能量改變不一樣，中間各個圓環(huán)消耗的平均能量趨于平衡。而且三條線幾乎重合，可以想到在總能量不變的情況下，能量均衡性是不變的。然而最外層和最內(nèi)層節(jié)點的能量還是未能達到均衡。最內(nèi)層節(jié)點能量未達到平衡是因為最內(nèi)層放置的中繼節(jié)點數(shù)太多，為原有傳感器節(jié)點的5～15倍，因此這層的傳感器節(jié)點大部分不會參與數(shù)據(jù)的轉(zhuǎn)發(fā)，只是本身產(chǎn)生數(shù)據(jù)發(fā)送數(shù)據(jù)。而最外層節(jié)點只是本身產(chǎn)生數(shù)據(jù)，因此消耗能量較少。

從所放置中繼節(jié)點的數(shù)量可以看出，雖然加大中繼節(jié)點的能量以后數(shù)量有所減少，但是最內(nèi)層中繼節(jié)點數(shù)量較原傳感器節(jié)點數(shù)量仍然很多，可能造成不必要的浪費和數(shù)據(jù)冗余，所以想到能否減少中繼節(jié)點的數(shù)量也能使能量消耗達到次優(yōu)均衡。

從表2中可以看出，隨著最內(nèi)層中繼節(jié)點數(shù)量的增加，方差也在不斷地變化，而當節(jié)點數(shù)為計算出的理論值時（即比例為1），方差最小，與理論上一致。但是，當中繼節(jié)點能量加到原來的2倍、中繼節(jié)點個數(shù)為30，即為理論中繼節(jié)點數(shù)的3/5時，方差次最小，那么可以認為在中繼節(jié)點能量加大到原來的2倍時，最內(nèi)層放置30個節(jié)點仍然可以達到預(yù)期的能量均衡的效果。而從4倍和5倍能量表中也觀察到，最內(nèi)層中繼節(jié)點分別為15和12時，方差均值也是一個分界點，即方差明顯減小，此中繼節(jié)點數(shù)也為理論值的3/5，比例與一倍時相同。所以考慮到成本和數(shù)據(jù)冗余問題，放置少量的中繼節(jié)點就能達到能耗均衡的目的。

表2 圓環(huán)平均能量方差隨最內(nèi)層中繼節(jié)點數(shù)的變化

本文針對能量空洞問題，提出了通過改變中繼節(jié)點的能量減少各個圓環(huán)內(nèi)中繼節(jié)點的個數(shù)達到網(wǎng)絡(luò)能耗均衡。理論分析和仿真結(jié)果表明，這種方法有效地解決了能量空洞問題。同時，考慮到成本和數(shù)據(jù)冗余問題，在中繼節(jié)點數(shù)為理論中繼節(jié)點數(shù)的3/5倍時，網(wǎng)絡(luò)能耗沒有太大變化，即放置少量的中繼節(jié)點也能達到網(wǎng)絡(luò)能耗均衡的目的。但是，在做仿真的過程中忽略了一些細節(jié)，沒有考慮到協(xié)議等多方面的因素，這也是以后要研究和努力的方向。

參考文獻

[1]孫利民，李建中，陳渝，等.無線傳感器網(wǎng)絡(luò)[M].北京：清華大學出版社，2005.

[2]AKYILDIZ I F，SU W，SANKARASUBRAMANIAM Y，et al.Wireless sensor networks：a survey[J].Computer Networks，2002，38（4）：393-422.

[3]LUO J，HUBAUX J P.Joint mobility and routing for lifetime enlongation in wireless sensor networks[J]，Proc.INFOCOM，2005：819-830.

[4]吳小兵，陳貴海.無線傳感器網(wǎng)絡(luò)中節(jié)點非均勻分布的能量空洞問題[J].計算機學報，2008，31（2）：253-261.

[5]LI J，MOHAPATRA P.An analytical model for the energy hole problem in many-to-one sensor networks[C].Proceedings of IEEE Vehicular Technology Conference，Dallas，TX，2005：2721-2725.

[6]YU Fengxin，GUVEN T，SHAYMAN M.Relay deployment and power control for life time elongation in sensor networks[C].Proc.IEEE int’l Conf.Comm，2006：3461-3466.

[7]掌明.基于最大生存周期的無線傳感器網(wǎng)絡(luò)能力模型研究[J].現(xiàn)代電子技術(shù)，2007，31（21）：38-40.

Using relay-nodes to solve energy hole in wireless sensor networks

Fu Juping1，2，Wang Dongfang1，2，Qi Xiaogang1，2

（1.Department of Applied Mathematics,Xidian University,Xi′an 710071，China；2.State Key Laboratory of Integrate Services Networks,Xidian University,Xi′an 710071，China）

In wireless sensor networks,sensor nodes use multipoint-to-point to transmit data.The closer to the sink,the quicker they will consume its battery,which forms the energy hole problem.To this problem,an energy consumption balance strategy,changing relay-node energy,is proposed,that is increasing energy of relay-nodes,and decreasing the number of relay-nodes.Theory analysis and simulation results indicate that this method can solve energy hole problem effectively.Moreover,for the cost of nodes and data redundancy,when the number of relay-nodes is decreased to 3/5 that of the ideal number,energy consumption is not extended more.That shows that decreasing the number of relay-nodes can also solves the problem.

wireless sensor networks；energy hole；relay-node；energy consumption balance

TP393

A

1674-7720（2011）02-0072-03

2010-08-20）

傅菊平，女，1985年生，碩士研究生，主要研究方向：無線傳感器網(wǎng)絡(luò)優(yōu)化。

王東方，女，1984年生，碩士研究生，主要研究方向：無線傳感器網(wǎng)絡(luò)路由算法。

齊小剛，男，1973年生，副教授，博士，碩士生導師，主要研究方向：圖論與組合最優(yōu)化、網(wǎng)絡(luò)優(yōu)化理論與方法以及路由與交換。