余育青，郝 平

1.浙江工業(yè)職業(yè)技術(shù)學(xué)院，浙江 紹興 312000

2.浙江工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，杭州 310032

WSN中基于時(shí)空特性的網(wǎng)絡(luò)能量空洞研究

余育青1，郝 平2

1.浙江工業(yè)職業(yè)技術(shù)學(xué)院，浙江 紹興 312000

2.浙江工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，杭州 310032

1 引言

在無線傳感器網(wǎng)絡(luò)中sink節(jié)點(diǎn)作為數(shù)據(jù)收集的中心，所有節(jié)點(diǎn)產(chǎn)生的數(shù)據(jù)都需要經(jīng)過多跳路由傳送到sink，因此sink附近的節(jié)點(diǎn)承擔(dān)了更多的路由數(shù)據(jù)轉(zhuǎn)發(fā)[1-3]，其能量消耗水平高于其他區(qū)域，稱為熱區(qū)（hotspot）[2-4]，熱區(qū)內(nèi)的節(jié)點(diǎn)過早消耗完自己的能量死亡而使網(wǎng)絡(luò)失效稱為能量空洞（Energy Hole）[2]現(xiàn)象。而能量空洞形成后，會導(dǎo)致空洞附近的節(jié)點(diǎn)需要承擔(dān)已經(jīng)死亡節(jié)點(diǎn)的數(shù)據(jù)轉(zhuǎn)發(fā)，從而會使其能量消耗水平更加增大（負(fù)載加速）而使空洞快速擴(kuò)大，這稱為漏斗效應(yīng)（funneling effect）[2，5]，最后使整個(gè)網(wǎng)絡(luò)過早死亡或陷于癱瘓。

“能量空洞“現(xiàn)象給無線傳感器網(wǎng)絡(luò)帶來了很大的損害，如文獻(xiàn)[3]中的模擬實(shí)驗(yàn)表明對于平面網(wǎng)絡(luò)，由于能量空洞的影響，當(dāng)網(wǎng)絡(luò)失效時(shí)，網(wǎng)絡(luò)中還有高達(dá)90%的能量未能被利用。因而有大量的關(guān)于能量空洞避免的研究。（1）節(jié)點(diǎn)密度（部署）控制策略。這類策略的主要原理是：在能量消耗的熱區(qū)（hotspots）部署更多的節(jié)點(diǎn)，從而有更多的節(jié)點(diǎn)用于中繼遠(yuǎn)方的數(shù)據(jù)，就能夠減弱能量空洞的影響，相關(guān)研究可參見文獻(xiàn)[3，5]。（2）移動sink或者與中繼節(jié)點(diǎn)：移動sink沿網(wǎng)絡(luò)能量充裕的區(qū)域移動來收集數(shù)據(jù)，就可以減少能量空洞的發(fā)生。與此原理相似，在能量消耗的熱區(qū)（hotspot）利用部分可移動的節(jié)點(diǎn)，作為數(shù)據(jù)收集與中繼的工具（“數(shù)據(jù)騾子”），同樣也可以減弱能量空洞的影響。此類的研究可見文獻(xiàn)[6-8]。（3）可調(diào)的發(fā)射半徑：這類策略的主要原理是：由于傳感器節(jié)點(diǎn)的能量消耗是與發(fā)射的距離成指數(shù)關(guān)系，因此，在能量消耗高的熱區(qū)采用較小的發(fā)射半徑，在能量充裕區(qū)域采用較大的發(fā)射半徑，這樣能夠做到能量均衡消耗，減弱能量空洞的影響，此類研究可參見文獻(xiàn)[2，9]。文獻(xiàn)[10]的非均勻分簇策略實(shí)質(zhì)上也包含了采用不同發(fā)射半徑的方法。（4）能量空洞的分析與評價(jià)模型：由于影響能量空洞的因素很多，因而有研究人員試圖分析給出影響能量空洞的一些因素，以指導(dǎo)能量空洞避免。Li和Mahapatra[11]提出一個(gè)數(shù)學(xué)模型用于分析無線傳感器網(wǎng)絡(luò)中的能量空洞問題。他們得到的結(jié)論是：在一個(gè)節(jié)點(diǎn)均勻分布的無線傳感器網(wǎng)絡(luò)中，減少數(shù)據(jù)的傳送可緩解能量空洞問題，例如采用層次結(jié)構(gòu)（如分簇網(wǎng)絡(luò)）和數(shù)據(jù)壓縮策略。增加數(shù)據(jù)采集率使能量空洞問題更加惡化，而增加節(jié)點(diǎn)的效果不明顯。

然而，以上的方法都未有研究能夠準(zhǔn)確給出無線傳感器網(wǎng)絡(luò)中能量空洞產(chǎn)生的位置，能量空洞發(fā)生的大小，發(fā)生時(shí)間，持續(xù)時(shí)間。大多數(shù)研究都只研究了傳感器網(wǎng)絡(luò)在穩(wěn)態(tài)（指網(wǎng)絡(luò)中未有節(jié)點(diǎn)死亡的狀態(tài)）下的能量消耗情況[12-13]。相對來說，在穩(wěn)態(tài)下，無線傳感器網(wǎng)絡(luò)的能量消耗比較容易確定。但是，一旦網(wǎng)絡(luò)中有一個(gè)節(jié)點(diǎn)死亡，那么網(wǎng)絡(luò)就不再是穩(wěn)態(tài)了，此時(shí)，網(wǎng)絡(luò)死亡區(qū)域的節(jié)點(diǎn)承擔(dān)的負(fù)載就需要由附近未死亡的節(jié)點(diǎn)來承擔(dān)，因而加速了未死亡節(jié)點(diǎn)的負(fù)載，而隨著死亡節(jié)點(diǎn)的增多，死亡節(jié)點(diǎn)附近存活節(jié)點(diǎn)的負(fù)載呈現(xiàn)加速的趨勢，因而形成所謂的“漏斗效應(yīng)”。實(shí)際上研究能量空洞產(chǎn)生的時(shí)間，區(qū)域與大小就是從時(shí)間上和空間上來研究網(wǎng)絡(luò)的動態(tài)演化規(guī)律。時(shí)間上的能量空洞研究能夠在部署網(wǎng)絡(luò)前評估能否達(dá)到應(yīng)用的需求，并在網(wǎng)絡(luò)運(yùn)行時(shí)采用最佳的網(wǎng)絡(luò)參數(shù)以使網(wǎng)絡(luò)壽命最大化；而空間上的能量空洞研究能夠使人們在部署網(wǎng)絡(luò)時(shí)加強(qiáng)網(wǎng)絡(luò)中薄弱區(qū)域的節(jié)點(diǎn)能量部署，或者采取措施減弱熱區(qū)（hotspot）節(jié)點(diǎn)的能量消耗量，以較小的代價(jià)換取網(wǎng)絡(luò)壽命的大幅提高?？梢姕?zhǔn)確計(jì)算能量空洞區(qū)域的空洞分布，時(shí)間變化規(guī)律，以指導(dǎo)網(wǎng)絡(luò)的設(shè)計(jì)與規(guī)劃，對網(wǎng)絡(luò)參數(shù)進(jìn)行優(yōu)化選取以避免能量空洞，提高網(wǎng)絡(luò)壽命具有重要的意義。

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

（1）網(wǎng)絡(luò)結(jié)構(gòu)模型：本文研究的網(wǎng)絡(luò)為一種周期性數(shù)據(jù)收集傳感器網(wǎng)絡(luò)[1，9]，即：網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)在每一個(gè)數(shù)據(jù)收集周期中都產(chǎn)生一個(gè)數(shù)據(jù)包，并需要將采集的數(shù)據(jù)包以多跳方式發(fā)送到sink[1-5]。節(jié)點(diǎn)隨機(jī)均勻地分布在網(wǎng)絡(luò)半徑為R的圓形區(qū)域內(nèi)，節(jié)點(diǎn)的通信半徑為r，密度為ρ。傳感器節(jié)點(diǎn)的發(fā)射功率可變，傳感器節(jié)點(diǎn)的發(fā)射功率可以根據(jù)兩節(jié)點(diǎn)間的距離而自動調(diào)整其通信半徑。例如，Berkeley Motes節(jié)點(diǎn)具有100個(gè)發(fā)射功率等級[1，9]。

（2）能量消耗模型：采用典型的能量消耗模型，發(fā)送數(shù)據(jù)的能量消耗見式（1），接收數(shù)據(jù)的能量消耗見式（2），具體的詳細(xì)情況可參見文獻(xiàn)[1，9]。

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

表1 網(wǎng)絡(luò)參數(shù)

3 能量空洞的時(shí)空分析

3.1 網(wǎng)絡(luò)穩(wěn)態(tài)下節(jié)點(diǎn)承擔(dān)的數(shù)據(jù)量與能量分析

在網(wǎng)絡(luò)開始運(yùn)行的階段，網(wǎng)絡(luò)中處于沒有節(jié)點(diǎn)死亡的穩(wěn)定狀態(tài)。因此，本節(jié)首先分析網(wǎng)絡(luò)在穩(wěn)態(tài)下網(wǎng)絡(luò)不同區(qū)域處節(jié)點(diǎn)承擔(dān)的數(shù)據(jù)情況。對于節(jié)點(diǎn)需要接收與轉(zhuǎn)發(fā)的數(shù)據(jù)量，有如下定理1。

定理1距離sink為l處的任意節(jié)點(diǎn)，其接收與發(fā)送的數(shù)據(jù)量為下式：

證明 網(wǎng)絡(luò)處于穩(wěn)態(tài)下的情況如圖1（a）所示，設(shè)距離sink為l處的任意節(jié)點(diǎn)其處寬度為?的圓環(huán)為（即距sink為h跳處的第i個(gè)圓環(huán)），取圓環(huán)弧度為θ的任意區(qū)域。由于節(jié)點(diǎn)的發(fā)射半徑為r，那么，必定接收距離其為r處圓環(huán)的弧度為θ的相應(yīng)區(qū)域的數(shù)據(jù)。依此類推，接受與轉(zhuǎn)發(fā)，一直到網(wǎng)絡(luò)的最外的對應(yīng)區(qū)域（?為網(wǎng)絡(luò)的最大跳數(shù)）的數(shù)據(jù)。當(dāng)?→0，θ→0時(shí)，也就是區(qū)域非常小時(shí)，區(qū)域內(nèi)的任意節(jié)點(diǎn)承擔(dān)的數(shù)據(jù)量都相等，即代表了區(qū)域的負(fù)載情況。那么區(qū)域承擔(dān)的數(shù)據(jù)量計(jì)算如下：

第h跳處的區(qū)域的面積為：

區(qū)域的節(jié)點(diǎn)個(gè)數(shù)為：nl=Slρ。

區(qū)域總共接收的數(shù)據(jù)量為：

圖1 能量空洞及其演化過程

區(qū)域每個(gè)節(jié)點(diǎn)接收的數(shù)據(jù)量為：

區(qū)域每個(gè)節(jié)點(diǎn)發(fā)送的數(shù)據(jù)量為接收的數(shù)據(jù)量再加上自己產(chǎn)生的一個(gè)數(shù)據(jù)包量，因此接收的數(shù)據(jù)量從而得證。

3.2 網(wǎng)絡(luò)非穩(wěn)態(tài)下節(jié)點(diǎn)承擔(dān)的能量消耗分析

圖2是依據(jù)推理1給出的在不同發(fā)射半徑r下，距離sink不同距離處的網(wǎng)絡(luò)處于穩(wěn)態(tài)下的能量消耗情況（圖中的能量消耗曲線有跳躍是因?yàn)镽并不正好是r的整數(shù)倍，因而環(huán)的一部分多承擔(dān)了一個(gè)最外環(huán)的數(shù)據(jù)），可見不同r下，節(jié)點(diǎn)的能量消耗差別是比較大的，因而直接影響能量空洞出現(xiàn)的時(shí)間，位置，持續(xù)的時(shí)間。網(wǎng)絡(luò)從第一節(jié)點(diǎn)死亡開始，網(wǎng)絡(luò)就處于非隱態(tài)。下面分析網(wǎng)絡(luò)非隱態(tài)下節(jié)點(diǎn)的能量消耗情況，從而為確定能量空洞的時(shí)、空演化規(guī)律奠定基礎(chǔ)。

圖2 離sink節(jié)點(diǎn)不同距離的節(jié)點(diǎn)的能量消耗

能量空洞的形成是網(wǎng)絡(luò)上能量消耗最大的節(jié)點(diǎn)最先死亡開始。如圖3所示，能量消耗最高的圓環(huán)最先死亡，也就是對應(yīng)圖1（a）的平面圖圓環(huán)處，此時(shí)也就是網(wǎng)絡(luò)中的第一個(gè)節(jié)點(diǎn)死亡（First Node Died，F(xiàn)ND）時(shí)間。但是，網(wǎng)絡(luò)FND后，網(wǎng)絡(luò)的能量消耗情況就變得比較復(fù)雜。如圖1（b）所示，由于圓環(huán)的死亡，導(dǎo)致遠(yuǎn)sink一側(cè)的圓環(huán)需要承擔(dān)原先由轉(zhuǎn)發(fā)的數(shù)據(jù)，因而其負(fù)載比FND前變大了。而隨后死亡后，導(dǎo)致承擔(dān)原先由和轉(zhuǎn)發(fā)的數(shù)據(jù)，導(dǎo)致加速死亡。同時(shí)，區(qū)域的能量消耗與FND前一樣，但是由于其能量消耗本身比較大而死亡。這樣，導(dǎo)致，，，區(qū)域死亡，如圖1（c）所示。這時(shí)，所有死亡區(qū)域節(jié)點(diǎn)的負(fù)載都增加到了區(qū)域。最后，區(qū)域死亡，同時(shí)能量消耗較高的區(qū)域也死亡。這時(shí)，死亡區(qū)域的寬度超過了節(jié)點(diǎn)的發(fā)送半徑r，導(dǎo)致網(wǎng)絡(luò)空洞外圍區(qū)域節(jié)點(diǎn)的數(shù)據(jù)不能傳送到sink，從而能量空洞最終形成，如圖1（d）所示。

圖3 網(wǎng)絡(luò)的能量消耗與節(jié)點(diǎn)的死亡順序

在上面的分析中，揭示了死亡區(qū)域連續(xù)的情況。如果死亡區(qū)域不是連續(xù)的，其情況就更復(fù)雜了。如圖2中，當(dāng)r=150和200時(shí)，最近sink的區(qū)域與離sink為r遠(yuǎn)處的能量消耗最高，就有可能死亡的區(qū)域在位置r出現(xiàn)后，再在近sink的區(qū)域出現(xiàn)，因而導(dǎo)致有多個(gè)不連續(xù)的死亡區(qū)域出現(xiàn)?？梢娋W(wǎng)絡(luò)處于非穩(wěn)態(tài)下，其能量消耗變化的情況是非常復(fù)雜的，導(dǎo)致從理論上事先分析得到能量空洞的演化情況變得非常復(fù)雜。據(jù)研究所知，還未見有類似網(wǎng)絡(luò)非穩(wěn)態(tài)下的研究，本文試圖解決這個(gè)難題。從理論上來說，網(wǎng)絡(luò)中處于同一環(huán)上的節(jié)點(diǎn)能量消耗是對稱均等的，因而死亡的區(qū)域都是以環(huán)形的區(qū)域死亡。如果將死亡的環(huán)的寬度劃分很小，例如其寬度為?，那么就可以認(rèn)為在這樣的一個(gè)寬度為?的環(huán)的死亡時(shí)間內(nèi)，網(wǎng)絡(luò)是穩(wěn)態(tài)的，而在此穩(wěn)態(tài)下就能夠計(jì)算出此穩(wěn)態(tài)維持的時(shí)間；而一個(gè)環(huán)死亡后，網(wǎng)絡(luò)上不同區(qū)域節(jié)點(diǎn)承擔(dān)的負(fù)載又發(fā)生了變化，從而進(jìn)入到下一個(gè)很小的穩(wěn)態(tài)。如此下去，網(wǎng)絡(luò)的死亡過程就是每次由死亡的環(huán)形區(qū)域?qū)挾葹?的區(qū)域不斷死亡的過程，直到有連續(xù)死亡的區(qū)域?qū)挾?r時(shí)，能量空洞就形成了。而死亡寬度為?的環(huán)形區(qū)域的連續(xù)變化過程就從空間上描述了能量空洞形成的演化過程；而每個(gè)環(huán)形區(qū)域死亡所需的持續(xù)時(shí)間就形成能量空洞在時(shí)間上演化過程。通過這樣的方法就能夠很好從空間與時(shí)間揭示能量空洞的時(shí)空演化規(guī)律。首先，下面的定理2給出了死亡區(qū)域在[s，s+?]處的環(huán)的負(fù)載情況（數(shù)據(jù)承擔(dān)情況）。

定理2將網(wǎng)絡(luò)劃分為很小的環(huán)形區(qū)域，環(huán)徑為?，設(shè)第i個(gè)死亡區(qū)域距離sink的位置為[s，s+?]，那么第i個(gè)死亡區(qū)域的環(huán)的負(fù)載為下式：

證明由于第i個(gè)死亡區(qū)域距離sink的位置為[s，s+?]。第i個(gè)區(qū)域死亡后，原來由[s，s+?]承擔(dān)的數(shù)據(jù)量會由其他區(qū)域的節(jié)點(diǎn)承擔(dān)。第i個(gè)死亡區(qū)域需要承擔(dān)數(shù)據(jù)的這些區(qū)域的集合為：

很容易可得第j個(gè)區(qū)域[s+jr，s+jr+?]產(chǎn)生的數(shù)據(jù)個(gè)數(shù)為：π(2(s+jr)?+?2)ρ。

由此，可得此死亡區(qū)域需要承擔(dān)總的負(fù)載（數(shù)據(jù)量個(gè)數(shù)）為：

定理3將網(wǎng)絡(luò)劃分為很小的環(huán)形區(qū)域，即環(huán)徑為?，設(shè)第i個(gè)死亡區(qū)域距離sink的位置為[s，s+?]，當(dāng)其負(fù)載由距離sink為[z，z+?]的第j個(gè)環(huán)形區(qū)域承擔(dān)，則第j個(gè)環(huán)形區(qū)域增加的負(fù)載為下式：

證明由定理2可知，第i個(gè)死亡區(qū)域需要承擔(dān)的負(fù)載δs=xπρ?(2s+(1+x)r+?)。第j個(gè)環(huán)形區(qū)域的節(jié)點(diǎn)個(gè)數(shù)為：π(2z?+?2)ρ。因此，j個(gè)環(huán)形區(qū)域每個(gè)節(jié)點(diǎn)增加的負(fù)載為：

定理4設(shè)距離sink為[s，s+?]的第i個(gè)區(qū)域死亡后，此區(qū)域的遠(yuǎn)離sink方向距離此區(qū)域最近的未死亡的第j個(gè)區(qū)域距離sink為[z，z+?]，則此區(qū)域在第i個(gè)區(qū)域死亡后增加的負(fù)載為：

3.3 傳感器網(wǎng)絡(luò)能量空洞時(shí)間與空間演化算法

基于上面的分析，下面給出計(jì)算能量空洞時(shí)、空演化過程的計(jì)算方法。計(jì)算方法的思想是：采用前面論述的近似計(jì)算方法（微分學(xué)方法），將網(wǎng)絡(luò)區(qū)域分給很小的環(huán)形區(qū)域?，以?為單位來代表能量空洞形成過程上空間擴(kuò)展的基本單位，在此穩(wěn)態(tài)下持續(xù)的時(shí)間就是網(wǎng)絡(luò)在此階段的壽命，這樣就可通過區(qū)域?的死亡過程來揭示能量空洞的時(shí)、空演化過程。采用的具體方法是：（1）起始時(shí)：節(jié)點(diǎn)的剩余能量為初始能量；依據(jù)定理1與推理1計(jì)算出每個(gè)區(qū)域?的負(fù)載。（2）計(jì)算最先死亡區(qū)域的壽命：用節(jié)點(diǎn)的剩余能量除以節(jié)點(diǎn)的負(fù)載，得到每個(gè)區(qū)域?的壽命。其中，壽命最小(Tmin)的區(qū)域?為當(dāng)前最先死亡的區(qū)域。（3）更新節(jié)點(diǎn)的剩余能量：每個(gè)節(jié)點(diǎn)的新的剩余能量為當(dāng)前的剩余能量減去此節(jié)點(diǎn)的負(fù)載與壽命(Tmin)的積。（4）更新節(jié)點(diǎn)的負(fù)載：壽命最小的區(qū)域死亡后，依據(jù)定理4更新承擔(dān)此死亡區(qū)域負(fù)載的區(qū)域的負(fù)載，其負(fù)載為原負(fù)載（推理1計(jì)算出的負(fù)載）加上依據(jù)定理4計(jì)算出的增加的負(fù)載。（5）重復(fù)第（2）～（4）步，直到連續(xù)死亡區(qū)域的寬度>r為止。下面給出能量空洞時(shí)、空演化過程的計(jì)算方法。

算法1能量空洞區(qū)域時(shí)、空演化求解算法

輸入：網(wǎng)絡(luò)半徑R以及節(jié)點(diǎn)發(fā)射半徑r。

輸出：網(wǎng)絡(luò)FND值Tf，AND值TΑ，網(wǎng)絡(luò)死亡區(qū)域的順序序列l(wèi)={l1，l2，…，ln}，對應(yīng)區(qū)域的持續(xù)時(shí)間序列：T={t1，t2，…，tn}。

（1）將網(wǎng)絡(luò)劃分成寬度為?的n個(gè)區(qū)域（環(huán)）：

（2）據(jù)定理1，計(jì)算出每個(gè)環(huán)的初始負(fù)載（能量消耗速率）：

（3）每個(gè)環(huán)的負(fù)載存儲在向量?中

（4）每個(gè)區(qū)域節(jié)點(diǎn)的剩余能量為初始能量；

（5）j=1

（6）計(jì)算出在此情況下每個(gè)區(qū)域節(jié)點(diǎn)的壽命：

（7）查找序列ξT中壽命最小且>0的區(qū)域ξk；

（9）ifj=1thenTf=tj//FND壽命

（10）TΑ=TΑ+tj//AND壽命累加

（11）重新計(jì)算每個(gè)區(qū)域的剩余能量；

//死亡區(qū)域的剩余能量必為0

（12）據(jù)定理4更新承擔(dān)此死亡區(qū)域負(fù)載的區(qū)域的負(fù)載；

（13）j=j+1；

（14）計(jì)算是否有連續(xù)死亡區(qū)域的寬度>r,如果沒有，則轉(zhuǎn)步驟（6）；否則轉(zhuǎn)下一步；

（15）輸出網(wǎng)絡(luò)FND值Tf，AND值TΑ，網(wǎng)絡(luò)死亡區(qū)域的順序序列l(wèi)={l1，l2，…，ln}，對應(yīng)區(qū)域的持續(xù)時(shí)間序列：T={t1，t2，…，tn}。

（16）算法結(jié)束

4 實(shí)驗(yàn)結(jié)果與分析

4.1 節(jié)點(diǎn)承擔(dān)的數(shù)據(jù)量與能量消耗

采用得到學(xué)術(shù)界廣泛認(rèn)可的模擬工具OMNEΤ++來進(jìn)行實(shí)驗(yàn)驗(yàn)證[14]，其中，網(wǎng)絡(luò)的拓?fù)湓O(shè)置（如sink的位置、節(jié)點(diǎn)的分布律和密度等參數(shù)）與文獻(xiàn)[9]一致，其他的模擬參數(shù)如沒有特別說明均采用表1所示的數(shù)據(jù)。

圖4給出的是在網(wǎng)絡(luò)處于穩(wěn)態(tài)時(shí)節(jié)點(diǎn)承擔(dān)的數(shù)據(jù)包個(gè)數(shù)的實(shí)驗(yàn)結(jié)果（僅給出了距離sink近100 m的情況）。從圖4可以看出，實(shí)驗(yàn)結(jié)果與本文的理論計(jì)算結(jié)果（定理1）是一致的，結(jié)果的誤差大多在1%～5%之間，在近sink附近最多時(shí)為7.12%。圖5給出了節(jié)點(diǎn)的能量消耗情況，由于能量消耗情況是根據(jù)數(shù)據(jù)量計(jì)算得到的，因而其實(shí)驗(yàn)結(jié)果與圖4的實(shí)驗(yàn)結(jié)果類似。從上面的實(shí)驗(yàn)結(jié)果可以看出本文理論計(jì)算和實(shí)驗(yàn)結(jié)果相一致。說明本文的理論分析結(jié)果較好地反映了傳感器網(wǎng)絡(luò)的負(fù)載情況。

圖4 節(jié)點(diǎn)承擔(dān)的數(shù)據(jù)包量情況（R=500 m）

圖5 節(jié)點(diǎn)的能量消耗情況（R=500 m）

4.2 能量空洞情況分析

圖6的實(shí)驗(yàn)結(jié)果是記錄了當(dāng)能量空洞開始時(shí)到能量空洞擴(kuò)展到r時(shí)的網(wǎng)絡(luò)壽命變化情況。從圖6可以看出，由于在實(shí)驗(yàn)中?的取值為1，因此，當(dāng)能量空洞的寬度為1時(shí)的壽命其實(shí)就對應(yīng)了網(wǎng)絡(luò)的FND壽命。隨后，能量空洞繼續(xù)擴(kuò)展，網(wǎng)絡(luò)壽命也隨之延長，即在圖中壽命的曲線上升。從圖上可以看出的規(guī)律是：當(dāng)能量空洞的寬度較小時(shí)，壽命上升的幅度較大，當(dāng)能量空洞的擴(kuò)展到較大的寬度時(shí)，其壽命上升非常緩慢。其原因是：當(dāng)網(wǎng)絡(luò)達(dá)到FND時(shí)，這時(shí)節(jié)點(diǎn)的剩余能量較多，而隨著網(wǎng)絡(luò)的運(yùn)行，節(jié)點(diǎn)的能量越來越少，又由于空洞邊緣節(jié)點(diǎn)要承擔(dān)死亡區(qū)域節(jié)點(diǎn)的負(fù)載上升非?？?，這兩方面的因素導(dǎo)致出現(xiàn)圖6所示的現(xiàn)象：能量空洞一旦出現(xiàn)，節(jié)點(diǎn)就加速死亡的“漏斗效應(yīng)”。

圖6 網(wǎng)絡(luò)壽命與能量空洞擴(kuò)展的關(guān)系（R=500 m）

圖7詳細(xì)地給出了能量空洞從每一個(gè)死亡區(qū)域?下穩(wěn)持的網(wǎng)絡(luò)壽命情況。與圖6的實(shí)驗(yàn)是一致的，在能量空洞剛剛開始時(shí)，第一個(gè)死亡區(qū)域?維持的網(wǎng)絡(luò)壽命最長，隨后的區(qū)域維持的時(shí)間呈快速下降的趨勢。實(shí)際上，將網(wǎng)絡(luò)的FND再累加上圖7的第一個(gè)死亡區(qū)域維持的時(shí)間就得到了網(wǎng)絡(luò)AND。

圖7 不同死亡區(qū)域?持續(xù)的運(yùn)行時(shí)間情況

圖8給出的是隨著能量空洞的擴(kuò)展，能量空洞遠(yuǎn)離sink一側(cè)區(qū)域的負(fù)載變化情況。從圖8中可以清楚地看到隨著能量空洞的擴(kuò)展，未死亡區(qū)域的負(fù)載上升非?？欤瑥亩鴮?dǎo)致節(jié)點(diǎn)加速死亡，能量空洞加速形成。

圖8 隨著能量空洞的擴(kuò)展，未死亡區(qū)域的負(fù)載變化情況（R=500 m）

圖9與圖10分別給出了r=150 m和r=200 m時(shí)，隨著能量空洞的擴(kuò)展，網(wǎng)絡(luò)中節(jié)點(diǎn)的剩余能量情況。在圖9中，當(dāng)網(wǎng)絡(luò)運(yùn)行到800輪（round）時(shí)，能量消耗最高的近sink區(qū)域的節(jié)點(diǎn)的能量剩余最少，因而最先死亡。而次近sink的區(qū)域雖然其剩余能量較大（從圖8中可見，距sink 100 m的節(jié)點(diǎn)在網(wǎng)絡(luò)運(yùn)行到800輪時(shí)，其剩余能量比200 m處的節(jié)點(diǎn)的剩余能量還多）。但是由于死亡區(qū)域邊緣節(jié)點(diǎn)承擔(dān)的負(fù)載增加非常大（見圖8），因而在圖8中能量空洞是在近sin的區(qū)域內(nèi)形成（剩余能量為0的區(qū)域）。但是，圖10的能量空洞區(qū)域形成卻并不是在近sink的區(qū)域，而是距sink為r處形成的。其原因是r處的能量消耗最高，最高處死亡后，而造成近死亡區(qū)域類似于“雪崩”的效果，從而形成如圖10所示的能量空洞區(qū)域。據(jù)研究所知，以往的研究中大多認(rèn)為能量空洞一定出現(xiàn)在近sink的第一個(gè)r內(nèi)，但從理論與實(shí)驗(yàn)中經(jīng)過細(xì)致的分析第一次發(fā)現(xiàn)，能量空洞可以出現(xiàn)在[0，2r]的范圍（參見圖11）。

圖9 隨著能量空洞的擴(kuò)展，節(jié)點(diǎn)剩余能量情況（R=500 m，r=150 m）

圖10 隨著能量空洞的擴(kuò)展，節(jié)點(diǎn)剩余能量情況(R=500 m，r=200 m)

圖11給出了網(wǎng)絡(luò)不同位置的節(jié)點(diǎn)的壽命情況。圖11中的縱坐標(biāo)（壽命）為坐標(biāo)的壽命減去了網(wǎng)絡(luò)FND的值。從圖中可以看出，能量空洞最先出現(xiàn)的區(qū)域就是圖中節(jié)點(diǎn)壽命最小的位置，隨后出現(xiàn)的位置就是壽命次小的位置，依次類推，直到能量空洞的寬度>r，網(wǎng)絡(luò)死亡，這時(shí)能量空洞外的其他區(qū)域節(jié)點(diǎn)的壽命都相同，為網(wǎng)絡(luò)的AND壽命。故圖11下凹的低于網(wǎng)絡(luò)AND壽命的區(qū)域就是能量空洞的區(qū)域。因此，從圖11中可以較全面地反映能量空洞演化發(fā)展的時(shí)間與空間關(guān)系。

圖12給出了當(dāng)網(wǎng)絡(luò)達(dá)到AND時(shí)的網(wǎng)絡(luò)能量消耗情況。從圖中可以看出：能量空洞區(qū)域的能量已經(jīng)消耗盡，但其他區(qū)域還有能量剩余，且剩余的能量較多（參見圖13）；不同r下，網(wǎng)絡(luò)的能量剩余情況很不相同，從圖12中可以看出：當(dāng)r=120 m的剩余能量遠(yuǎn)大于r=200 m的剩余能量。

圖11 網(wǎng)絡(luò)不同位置的節(jié)點(diǎn)壽命

圖12 網(wǎng)絡(luò)不同位置的能量消耗情況

圖13 網(wǎng)絡(luò)剩余能量的比率（R=500 m）

圖13給出了在相同的網(wǎng)絡(luò)中部署不同數(shù)量節(jié)點(diǎn)的情況下網(wǎng)絡(luò)的剩余能量情況。從圖中可以看出，當(dāng)網(wǎng)絡(luò)達(dá)到FND時(shí)，網(wǎng)絡(luò)中的剩余能量率正如以往研究給出的那樣非常高[3]，而當(dāng)網(wǎng)絡(luò)達(dá)到AND時(shí)網(wǎng)絡(luò)的剩余能量率有較多的減少。由于定理1的公式（3）中節(jié)點(diǎn)承擔(dān)的數(shù)據(jù)量沒有節(jié)點(diǎn)的密度ρ，這說明節(jié)點(diǎn)的能量消耗與節(jié)點(diǎn)密度ρ沒有關(guān)系，圖13的實(shí)驗(yàn)驗(yàn)證了這一點(diǎn)（并參見圖14的實(shí)驗(yàn)），不管網(wǎng)絡(luò)部署的節(jié)點(diǎn)個(gè)數(shù)如何增長，不同實(shí)驗(yàn)網(wǎng)絡(luò)剩余能量率幾乎沒有變化。

4.3 網(wǎng)絡(luò)參數(shù)對性能的影響

節(jié)點(diǎn)密度對網(wǎng)絡(luò)壽命的影響見圖14的實(shí)驗(yàn)。前面的論述說明：節(jié)點(diǎn)密度不影響節(jié)點(diǎn)負(fù)載情況。而圖14的實(shí)驗(yàn)結(jié)果表明在不同節(jié)點(diǎn)密度下，網(wǎng)絡(luò)的FND與AND基本相同，這就驗(yàn)證了前面論述的正確性，同時(shí)也說明了本文理論推導(dǎo)的正確性。

圖14 不同節(jié)點(diǎn)密度下的網(wǎng)絡(luò)壽命

圖15給出的是在不同r下網(wǎng)絡(luò)的FND與AND壽命情況，從中可以發(fā)現(xiàn)選擇不同的r有不同的網(wǎng)絡(luò)壽命，必有一個(gè)最佳的r使得網(wǎng)絡(luò)壽命（FND，AND）最大。綜合以上的結(jié)論可得：在部署傳感網(wǎng)絡(luò)時(shí)，只需要考慮網(wǎng)絡(luò)的覆蓋與連通的情況下，選擇最優(yōu)的發(fā)射半徑r來使網(wǎng)絡(luò)壽命最大化。

圖15 不同r下的網(wǎng)絡(luò)壽命

5 結(jié)論

本文針對節(jié)點(diǎn)隨機(jī)均勻分布的多跳平面無線傳感器網(wǎng)絡(luò)，在網(wǎng)絡(luò)部署后，網(wǎng)絡(luò)保持連通與覆蓋的前提下，通過理論分析得到了能量空洞產(chǎn)生的區(qū)域，大?。荒芰靠斩窗l(fā)生的時(shí)間，持續(xù)的時(shí)間，以及網(wǎng)絡(luò)的壽命情況。從時(shí)間與空間上分析了能量空洞演化規(guī)律，并通過模擬工具Omnet++進(jìn)行了仿真實(shí)驗(yàn)，證實(shí)了本文理論計(jì)算的正確性。

能量空洞的理論分析與驗(yàn)證具有重要的研究意義，但又非常具有挑戰(zhàn)性。本文主要是通過微分分析的方法，通過細(xì)致的分析得到了網(wǎng)絡(luò)中不同區(qū)域的數(shù)據(jù)承擔(dān)情況與能量消耗情況，從而第一次能夠準(zhǔn)確推導(dǎo)能量空洞的時(shí)間與空洞規(guī)律，這是本文在求解方法上的一個(gè)創(chuàng)新，同時(shí)，本文這種建立在數(shù)學(xué)微分分析方法基礎(chǔ)上的理論推導(dǎo)具有嚴(yán)謹(jǐn)性。

[1]Liu Anfeng，Zhang Penghui，Chen Zhigang.Τheoretical analysis of the lifetime and energy hole in cluster based Wireless Sensor Networks[J].Journal of Parallel and Distributed Computing，2011，71（10）：1327-1355.

[2]曾志文，陳志剛，劉安豐.無線傳感器網(wǎng)絡(luò)中基于可調(diào)發(fā)射功率的能量空洞避免[J].計(jì)算機(jī)學(xué)報(bào)，2010，33（1）：12-22.

[3]Olariu S，Stojmenovic I.Design guidelines for maximizing lifetime and avoiding energy holes in sensor networks with uniform distribution and uniform reporting[C]//Proceedings of the IEEE INFOCOM，Barcelona，Spain，2006：1-12.

[4]Dagher J，Marcellin C，Neifeld M A.A theory for maximizing the lifetime of sensor networks[J].IEEE Τransactions on Communications，2007，55（2）：323-332.

[5]Wu X B，Chen G，Das S K.Avoiding energy holes in Wireless Sensor Networks with nonuniform node distribution[J]. IEEE Τransactions on Parallel and Distributed Systems，2008，19（5）：710-720.

[6]Xu Hongli，Huang Liusheng，Liu Gang，et al.Optimal relay assignment for fairness in wireless cooperative networks[J]. International Journal of Ad Hoc and Ubiquitous Computing，2012，9（1）：42-53.

[7]Luo J，Hubaux J P.Joint mobility and routing for lifetime elongation in wireless sensor networks[C]//Proceedings of the IEEE INFOCOM，Washington，2005：1735-1746.

[8]Chatzigiannakis I，Kinalis A，Nikolets S.Efficient data propagation strategies in wireless sensor networks using a single mobile sink[J].Computer Communications，2008，31（2）.

[9]Chao S，Liu M，CAO J N，et al.Maximizing network lifetimebased on transmission rangeadjustmentin wireless sensor networks[J].Computer Communications，2009，32（11）：1316-1325.

[10]Chen G，Li C F，Ye M，et al.An unequal cluster-based routing strategy in Wireless Sensor Networks[J].Wireless Networks，2009，15（2）：193-207.

[11]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）.

[12]李巧勤，劉明，楊梅，等.負(fù)載相似節(jié)點(diǎn)分布解決傳感器網(wǎng)絡(luò)能量洞問題[J].軟件學(xué)報(bào)，2011，22（3）：452-465.

[13]陸海明，劉學(xué)軍，錢江波.基于有線長鏈解決傳感器網(wǎng)絡(luò)的能量空洞[J].計(jì)算機(jī)研究與發(fā)展，2010，47（S2）：1-4.

[14]Varga A.Τhe OMNEΤ++ discrete event simulation system[EB/OL].[2013-01-05].http：//www.omnetpp.org.

YU Yuqing1,HAO Ping2

1.Zhejiang Industry Polytechnic College,Shaoxing,Zhejiang 312000,China
2.College of Computer Science and Τechnology,Zhejiang University of Τechnology,Hangzhou 310032,China

Τhe Energy Hole（EH）problem has brought big damage to Wireless Sensor Networks（WSNs）,and the evolution law of Energy Hole from spatial and temporal plays an important role in WSNs.Τhis paper theoretically obtains nodal data load in multi-hop WSNs through the differential method,and then the algorithm which calculates the evolution of Energy Hole from spatial and temporal is given.Τhe algorithm accurately gives the death evolution from first node to all nodes,as well as the entire evolution of Energy Hole from spatial for the first time.A large number of simulation results based on Omnet++prove the correctness of the algorithm in this paper,which shows this paper can be a good guide for Energy Hole avoiding,deployment and optimization in sensor networks.

Wireless Sensor Networks（WSN）;Energy Hole（EH）;lifetime;load acceleration;space-time character

能量空洞（Energy Hole，EH）現(xiàn)象給傳感器網(wǎng)絡(luò)帶來了很大的損害，確定能量空洞的時(shí)間與空間演化規(guī)律對于無線傳感器網(wǎng)絡(luò)的研究起著重要的支撐作用。采用微分的方法從理論上分析得到了多跳無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)承擔(dān)的數(shù)據(jù)量。給出了計(jì)算傳感器網(wǎng)絡(luò)能量空洞時(shí)間與空間的演化過程的算法。算法第一次較為準(zhǔn)確地從時(shí)間上給出第一個(gè)節(jié)點(diǎn)死亡（First Node Died，F(xiàn)ND）到全部節(jié)點(diǎn)死亡（All Node Died，AND）的演化過程，以及能量空洞在空間上發(fā)生，發(fā)展的全過程。采用Omnet++平臺進(jìn)行了大量的模擬實(shí)驗(yàn)，結(jié)果證明了該算法的正確性，從而可為傳感器網(wǎng)絡(luò)的部署、優(yōu)化、能量空洞避免提供很好的指導(dǎo)作用。

無線傳感器網(wǎng)絡(luò)；能量空洞；網(wǎng)絡(luò)壽命；負(fù)載加速；時(shí)空特征

A

ΤP393

10.3778/j.issn.1002-8331.1303-0148

YU Yuqing,HAO Ping.Research on energy hole based on time and space characteristics in WSNs.Computer Engineering and Applications,2013,49（15）：105-112.

國家科技部科技人員服務(wù)企業(yè)項(xiàng)目（No.20090628）；紹興市科技計(jì)劃項(xiàng)目（No.2012B70024）。

余育青（1972—），男，講師，研究方向?yàn)閿?shù)字控制、管理控制、系統(tǒng)優(yōu)化等工程；郝平（1961—），男，副教授，研究方向?yàn)閿?shù)據(jù)倉庫與數(shù)據(jù)挖掘、故障診斷和管理控制系統(tǒng)等。

2013-03-12

2013-05-09

1002-8331（2013）15-0105-08

◎數(shù)據(jù)庫、數(shù)據(jù)挖掘、機(jī)器學(xué)習(xí)◎