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

余育青，郝 平

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

2.浙江工業(yè)大學 計算機科學與技術學院，杭州 310032

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

余育青1，郝 平2

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

2.浙江工業(yè)大學 計算機科學與技術學院，杭州 310032

1 引言

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

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

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

2 網(wǎng)絡模型

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

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

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

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

3 能量空洞的時空分析

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

（5）j=1

（6）計算出在此情況下每個區(qū)域節(jié)點的壽命：

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

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

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

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

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

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

（13）j=j+1；

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

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

（16）算法結束

4 實驗結果與分析

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

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

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

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

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

4.2 能量空洞情況分析

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

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

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

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

圖8給出的是隨著能量空洞的擴展，能量空洞遠離sink一側(cè)區(qū)域的負載變化情況。從圖8中可以清楚地看到隨著能量空洞的擴展，未死亡區(qū)域的負載上升非常快，從而導致節(jié)點加速死亡，能量空洞加速形成。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 結論

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

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

[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)絡中基于可調(diào)發(fā)射功率的能量空洞避免[J].計算機學報，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]李巧勤，劉明，楊梅，等.負載相似節(jié)點分布解決傳感器網(wǎng)絡能量洞問題[J].軟件學報，2011，22（3）：452-465.

[13]陸海明，劉學軍，錢江波.基于有線長鏈解決傳感器網(wǎng)絡的能量空洞[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)絡帶來了很大的損害，確定能量空洞的時間與空間演化規(guī)律對于無線傳感器網(wǎng)絡的研究起著重要的支撐作用。采用微分的方法從理論上分析得到了多跳無線傳感器網(wǎng)絡節(jié)點承擔的數(shù)據(jù)量。給出了計算傳感器網(wǎng)絡能量空洞時間與空間的演化過程的算法。算法第一次較為準確地從時間上給出第一個節(jié)點死亡（First Node Died，F(xiàn)ND）到全部節(jié)點死亡（All Node Died，AND）的演化過程，以及能量空洞在空間上發(fā)生，發(fā)展的全過程。采用Omnet++平臺進行了大量的模擬實驗，結果證明了該算法的正確性，從而可為傳感器網(wǎng)絡的部署、優(yōu)化、能量空洞避免提供很好的指導作用。

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

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.

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

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

2013-03-12

2013-05-09

1002-8331（2013）15-0105-08

◎數(shù)據(jù)庫、數(shù)據(jù)挖掘、機器學習◎