傳感器網絡中一種基于網格的密度控制算法
2009-01-01 00:00:00羊四清林亞平李小龍易葉青
計算機應用研究 2009年6期
摘 要：在保證完全覆蓋和網絡連通的前提下，設計了一種基于網格的密度控制算法GDCA。仿真實驗表明，與其他連通覆蓋集求解算法相比，GDCA算法能夠獲得更小的連通覆蓋集；且這種算法屬于分布式算法，具有良好的擴展性，節點的傳感區域可為任意凸形區域，更符合實際情況。
關鍵詞：傳感器網絡;網格;密度控制;覆蓋
中圖分類號：TP393文獻標志碼：A
文章編號：1001-3695(2009)06-2190-05
doi:10.3969/j.issn.1001-3695.2009.06.058
Grid-based density control algorithm for sensor networks
YANG Si-qing1a，2，LIN Ya-ping1b，LI Xiao-long3，YI Ye-qing1a，2
(1.a.School of Computer Communication，b.School of Software， Hunan University， Changsha 410082， China;2.Dept. of Computer Science Technology， Hunan Institute of Humanities Science Technology， Loudi Hunan 417000， China;3.School of Mathematics Computational Science， Guilin University of Electronic Technology， Guilin Guangxi 541004， China)
Abstract:Under the premise of complete coverage and guaranteed connectivity，this paper proposed a grid-based density control algorithm (GDCA). Experimental simulations show that GDCA outperforms other algorithm for minimum connected cover set problem in terms of the size of constructed connected cover set. GDCA is totally distributed. In addition， the algorithm is applicable to scenarios where the sensing area of a sensor does not follow the unit disk model， but have any convex area.
Key words:sensor network; grid; density control; coverage
0 引言
無線傳感器網絡是由大量計算、通信及存儲能力有限的傳感器節點組成的特殊Ad hoc網絡，在軍事和民用領域具有廣泛的應用，如戰場監視、環境和交通監測、災難救助等，是目前一個非常活躍的研究領域[1]。傳感器節點體積較小，節點提供的能量有限，且能量難以補充。如何節約節點能量、最大化網絡生命周期是傳感器網絡研究中的中心問題。
當成千上萬個傳感器節點隨機部署在人難以到達或危險區域時，由于節點個數多、分布區域廣闊、部署的環境復雜，傳感器網絡通過更換電池的方式來補充是不現實的。已有大量的文獻證明[2]，密度控制可以有效延長網絡生存時間。密度控制就是在不犧牲系統性能的前提下，選擇一部分節點作為活躍工作節點，而讓其他節點進入到低功耗的睡眠狀態。密度控制可以降低網絡中活躍節點的密度、感知數據的冗余性以及減少無線通信沖突和干擾，從而降低整個系統的能量消耗。為了不降低網絡性能，要求處于活躍狀態的節點集具有以下屬性：a)節點集能夠完全覆蓋目標區域，當目標區域用網格點集表示時，完全覆蓋目標區域等價于目標區域內的每個格點至少被一個節點所覆蓋；b)節點集構成的網絡是連通網絡。
為保證完全覆蓋和網絡的連通性，大部分的方法是將完全覆蓋和連通性當做兩個獨立的問題來處理，即先通過覆蓋算法選擇若干個節點，使得它們能夠完全覆蓋目標區域；然后采用連通算法從未選擇的節點集中選擇一些必要的節點加入到覆蓋集中，使其構建成一個連通的傳感器網絡。目前基于密度控制的覆蓋和網絡連通問題已取得了不少研究成果，但是卻只有較少的文獻同時兼顧調度算法中的覆蓋和網絡連通問題[3，4]，如文獻[5，6]僅針對覆蓋問題，而文獻[7，8]只考慮網絡連通問題。
Himanshu Gupta在文獻[3]中設計的算法通過選擇連通的傳感器節點路徑來得到最大化的覆蓋區域。當指令中心向WSN發送一個感應區域查詢消息時，設計連通覆蓋集求解算法的目標是選擇最小的連通傳感器節點集合并完全覆蓋WSN區域。文獻[3]設計了一種貪婪算法，其基本思想是：假設已選擇的傳感器節點集為M，剩余與M有相交傳感區域的傳感器節點稱為候選節點，連接候選節點到M中某個節點的路徑稱為候選路徑。如圖1(a)所示，候選節點有{C1，C2，C3，C4}，候選路徑有{(C1，I1)，(C2，C1，I1)，(C3，I2)，(C4，C3，I2)}。集中式算法隨機選擇初始節點構成M之后，在所有從初始節點集合出發到候選節點的路徑中選擇一條可以覆蓋更多未覆蓋子區域的路徑。將該路徑經過的節點加入M，算法繼續執行直到網絡查詢區域可以完全被M所覆蓋。候選路徑中的某一些路徑只是其他路徑的子路徑，這些路徑上的節點覆蓋的M未覆蓋子區域面積顯然不是最大的，無須參與進行比較，所以圖1(a)中只注明兩條路徑P1(C2，C1，I1)和P2(C4，C3，I2)。圖1表示了貪婪算法執行的方式。在圖1(a)中，P2上的節點覆蓋的M未覆蓋子區域面積大于P1，因此貪婪算法會選擇路徑P2得到圖1(b)。這種算法可適應節點的傳感區域為任意凸形區域的情況，更加符合實際環境。在保證網絡覆蓋任務的同時，考慮了網絡的連通性，算法周期執行降低了網絡通信代價，并可以延長網絡的生存時間。然而它仍然存在以下不足：a）文獻[9]采用的是全局貪婪思想，容易陷入局部最優，導致構造的連通覆蓋集較大。b）若采用文獻[9]提出的集中式貪婪算法，算法的時間復雜度較高，且不具備良好的擴展性，而采用分布式貪婪算法時，算法的通信開銷很大。
文獻[4]首先指出求解傳感器網絡的最小連通覆蓋集屬于NP難問題，并針對這個NP難問題提出了一個近似求解算法。在給出的近似算法中，連通覆蓋集的構造通過兩個步驟完成：在對目標區域 R進行 Voronoi 劃分的基礎上求出R的近似最小覆蓋集。
CVT算法的基本思想如下：a)傳感器網絡中的所有節點都作為Voronoi生成點，從而得到目標區域R的惟一劃分；b)識別出網絡中的冗余節點，也就是關閉該節點后不會在網絡中形成覆蓋漏洞；c)計算出可以同時被關閉的冗余節點；d)由所有的活躍工作節點組成目標區域的覆蓋集。
當節點的通信半徑Rc≥2Rs(Rs為傳感半徑）時，該覆蓋集同時就是連通覆蓋集；當Rc<2Rs時，構造的覆蓋集并不能保證網絡的連通性。文獻[4]設計了一種基于最小生成樹的連通算法MST，用于計算確保覆蓋集連通所需的輔助節點。算法的基本思想如下：
將覆蓋集中的每個最大連通子圖作為一個虛擬節點，通過使用寬度優先搜索(breadth-first search，BFS)算法在線性時間內計算出每對虛擬節點之間的最短輔助路徑構建一個圖Gw。其中圖的頂點對應虛擬節點，邊的權值對應虛擬節點之間的最短輔助路徑上輔助節點的個數。然后計算Gw的最小生成樹；最后返回與該最小生成樹的邊相對應的輔助節點，這些節點就是構造覆蓋集連通所需的輔助節點。
CVT+MST算法的優點在于能求解出近似最優的連通覆蓋集，但存在的主要缺點是：a）需要知道整個網絡的全局信息，因此算法不具備良好的可擴展性(scalability)，僅適合于小規模的傳感器網絡；b）僅適用于節點的感知模型為圓形區域感知模型的情況。
1 問題描述及分析
1.1 網絡模型
傳感器節點往往隨機分布在目標區域，即節點在部署之前預先不知道自己在目標區域內的位置。現假設傳感器網絡具有如下性質:
a)傳感器節點部署密集；
b)傳感器節點的感知模型為圓形區域感知模型，且節點的傳感半徑均為r；
c)所有節點部署后不再移動；
d)傳感器網絡并不是層次結構，也就是說，傳感器網絡是平面的；
e)部署后節點能夠獲取自身準確的位置信息。
1.2 問題分析
當傳感器節點的傳感區域為任意凸形區域時，對于存儲空間小、計算能力有限的傳感器節點來說，它的傳感區域和通信區域難以用線性函數進行表述，節點之間的共同傳感區域和交點位置也難以求解。為了簡化運算，本文將離散的點集代表連續的區域，將目標區域和點的傳感區域用網格進行剖分，目標區域和節點的傳感區域用若干個格點集來表示。
在基于網格思想的覆蓋算法中，目標區域G={g1，g2，…，gk}。其中：gi表示序號為i的格點；k為格點的個數。
為表述方便，首先給出幾個定義。
定義1 所有處于傳感器節點si的覆蓋范圍的格點稱為傳感器節點si的覆蓋格點集，用Psi來表示。
定義2 覆蓋區域內包含了格點gi的所有傳感器節點稱為格點gi的覆蓋節點集，用Mgi來表示。
定義3 所有處于傳感器節點si的通信范圍的節點稱為傳感器節點si的通信節點集，用Csi來表示。
對于一個傳感器網絡，若目標區域內的每個格點均至少被網絡中的一個節點所覆蓋，即如下等式成立：G=∪Ni=1Psi。其中N為網絡中傳感器節點的個數，則代表目標區域被這個傳感器網絡完全覆蓋。
1.3 網格大小選擇
值得注意的是，覆蓋精度與網格的大小有關。如圖2(a)所示，當網格較稀疏時，雖然所選取的六個傳感器節點覆蓋住了所有的格點，然而格點g10、g11、g17、g16圍成的網格區域有一部分區域是盲區，沒有被覆蓋到。對于相同的目標區域和節點分布，當網格較稠密時，圖2(a)選取的六個傳感器滿足了覆蓋住所有格點的要求，但是在圖2(b)中卻沒有達到要求，因為格點g45沒有被覆蓋。因此，所選取網格尺寸越大，覆蓋精度越小；反之，覆蓋精度越大。
傳感器節點的傳感區域為任意凸形區域，顯然在傳感器網絡中，一個目標區域被完全覆蓋也就等價于其中的每一個傳感器節點的凸形傳感區域的邊緣被其他傳感器節點所覆蓋。因此，所被選取處于活動狀態下的任意傳感器節點在各個方向總是與其他節點的傳感區域相交。在分析選擇網格合適的大小時，為了簡化問題，本文在該節假設傳感器的傳感區域為一種特殊的凸形區域——圓。
引理1 假設任意相交的兩個傳感器節點重疊部分的長度為p，傳感器節點的傳感半徑均為r時，如果重疊區域恰好能夠容納一個正方形，則正方形邊長l的長度必須滿足：
0≤l≤（-2r+p+4r2+p2/2）/2
證明 如圖3所示。由引理1可知，假設傳感器節點的位置均不相同，那么p的取值范圍是(0，2r)，如果p在此區間均勻分布，那么p在區間(0，0.01r)的概率僅為0.5%，當p=0.01r， l的最大長度≈p/2=0.005r。
定理1 將一個2d×2d正方形任意放置在一個網格區域內，網格大小為d×d，必然有一個格點在該正方形區域內。
證明 先進行一個命題轉換。將若干個網格任意放置在一個2d×2d正方形區域內，網格大小為d×d，必然有一個格點在該正方形區域內與定理1等價。如圖4所示，定義正方形左下角的頂點為原點。假設存在四個點(x1，y1)、(x2，y2)、(x3，y3)、(x4，y4)構成的區域為一個d×d的網格貫穿這個正方形區域。
a)如果貫穿方式是有兩個點分布在正方形的兩側，假設(x1，y1)在這個正方形區域的左側，(x3，y3)在這個正方形區域的右側，那么x1<0，x3>2d。很顯然，(x3-x1)2+( y3-y1)2≥(x3-x1)2=((x3-2d)+(2d-0)+(0-x1))2>2d2因為正方形任意兩點之間的距離為d或2d，顯然這種假設不成立。
b)如果貫穿方式是一個點在正方形區域的上側，假設是(x2，y2)，y2>d，一個點在正方形區域的下側，不妨設(x4，y4)，y4<0，(x4-x2)2+(y4-y2)2≥(y4-y2)2=((y2-2d)+(2d-0)+(0-y4))2>2d2。同理，這種假設也不成立。
綜上所述，也就是并不存在一個網格貫穿這個正方形區域，因此，必然有一個格點落在該區域內，即命題成立。
根據定理1，當d=2l/2=2p/4時，任意相交的兩個傳感器節點重疊部分的長度為p的重疊區域內，總是存在著一個格點在重疊區域內。當d=2r/400，任意相交的兩個傳感器節點的重疊部分有一個格點在重疊區域內的概率大于99.5%。
2 基于網格的密度控制算法GDCA
2.1 基于網格的密度控制覆蓋算法GCDCA
如果不考慮連通性，對于貪婪算法來說，總是選擇能夠覆蓋住個數最多的還沒有覆蓋到格點的傳感器節點。如圖5所示，當N1與N4已經被選擇，如果候選節點有N2和N3，因為N3與N2相比覆蓋了更多的還沒有被覆蓋到的格點，所以選擇了N3，但是導致格點g40沒有被覆蓋到。
為了使格點g40被覆蓋到，最后格點g40的覆蓋節點N2也被選擇，所以使用貪婪算法需要較多的傳感器節點。一個目標區域被完全覆蓋也就等價于其中的每一個傳感器節點的凸形傳感區域的邊緣被其他傳感器節點所覆蓋，選擇的傳感器節點必須要覆蓋住N1與N4的交點，因此N2與N3相比，N2是更為合適的選擇。為了改進貪婪算法的不足，本文給出了交點的判斷方法（見步驟c）），提出了一種基于網格的密度控制覆蓋算法GCDCA。具體描述如下：
a)建立虛擬網格，計算每個傳感器節點的覆蓋格點集。
b)任意選擇一格點gi，從gi的覆蓋節點集中選擇兩個節點sj、sk，而這兩個節點的覆蓋格點集交集中包含的格點個數最少，P=Psi∪Psk。
c）計算兩節點位于交點處的格點，該格點屬于兩節點的覆蓋格點集的交集。
(a)令t=兩節點覆蓋格點集的交集大小，nm代表該集合中的第i個格點；m=1。
(b)如果nm的鄰近四個格點滿足如下條件：其中一個格點屬于Psi-Psi∩Psj，一個格點屬于Psj-Psi∩Psj；一個格點屬于Psi∩Psj；一個格點不屬于Psi∪Psj；則nm為這兩個交點處的格點。
(c)m++，重復步驟c）的（b），直到m=t；
d)從該格點的覆蓋節點集中選擇它的覆蓋格點集與P的交集中包含格點個數最少的節點，假設為sv；temp=n1。
(a)t=該網格的覆蓋節點集中包含的節點個數。m=1；ni代表該集合中的第i個節點。
(b)如果temp的覆蓋格點集與P的交集包含的元素個數大于nm+1的覆蓋格點集與P的交集包含的元素個數，temp=nm+1。
(c)m++，重復步驟d)的（b），直到m=t。
(d)Sv= temp。
e)P=P∪Psv，重復步驟c）和d），直到P=G。
定理2 假設傳感器網絡的節點感知模型為圓形區域感知模型，節點的傳感范圍和通信范圍分別為Rs和Rc。若Rc≥2Rs，GCDCA構造的覆蓋集是連通的。
證明 數學歸納法。
當n=2時，根據GCDCA算法，這兩個節點的覆蓋格點集都包含了gi，因而這兩個節點重疊部分的長度p>0，它們之間的距離為2Rs-p＜Rc，兩節點是相互連通的。
假設當n=N時，GCDCA已經選擇N個傳感器，它們構成的傳感器網絡是連通的。那么當n=N+1時，根據GCDCA算法，選擇的節點(假設為A)至少包含了某兩節點位于交點處的格點，而這個格點又屬于某兩節點的覆蓋格點集，因此A節點與這兩個節點之間是相互連通的，此N+1個傳感器構成的傳感器網絡也是連通的。
綜上所述，命題成立。
2.2 基于網格的密度控制算法GDCA
當傳感器節點傳感區域為任意凸形區域時，完全覆蓋目標區域的覆蓋集并不能保證構成的網絡是連通的。在GCDCA算法的基礎上，本文選擇節點時同時考慮網絡的連通性，提出了一種基于網格的密度控制算法GDCA。GDCA算法步驟具體描述如下：
a)建立虛擬網格，計算每個傳感器節點的覆蓋格點集，計算每個傳感器節點的通信節點集。
b)任意選擇一格點gi，在sk屬于sj的通信節點集的基礎上，從gi的覆蓋節點集中選擇兩個節點sj、sk，其中這兩個節點的覆蓋格點集交集中包含的格點個數最少，P=Psi∪Psk。
c)計算兩節點(不妨假設為sj和sk)位于交點處的格點，不妨假設為gc，該格點屬于兩節點的覆蓋格點集的交集。
d)從格點gc的覆蓋節點集與sj或sk的通信節點集的交集中選擇它的覆蓋格點集與P的交集中包含格點個數最少的節點，假設為sv。
(a)t=格點gc的覆蓋節點集與sj的通信節點集的交集中包含的節點個數。m=1；ni代表該集合中的第i個節點；temp=n1。
(b)如果temp的覆蓋格點集與P的交集包含的元素個數大于nm+1的覆蓋格點集與P的交集包含的元素個數，temp=nm+1。
（c）m++，重復(b），直到m=t。
（d）t=格點gc的覆蓋節點集與sk的通信節點集的交集中包含的節點個數。m=1；ni代表該集合中的第i個節點；temp1=n1。
(e)如果temp1的覆蓋格點集與P的交集包含的元素個數大于nm+1的覆蓋格點集與P的交集包含的元素個數，temp1=nm+1。
(f)m++，重復e），直到m=t。
(g)如果temp的覆蓋格點集與P的交集包含的元素個數大于temp1的覆蓋格點集與P的交集包含的元素個數，sv= temp1；否則，sv=temp。
e)P=P∪Psv，重復c）和d)，直到P=G。
定理3 假設傳感器網絡的節點傳感區域為任意凸形區域，GDCA算法選擇出來的節點集為連通覆蓋集。
證明 證明過程類似于定理2，略。
3 性能評估
當目標區域為50×50 m2的矩形區域，傳感半徑Rs=10 m，網格d=0.1 m時，根據文獻[10]中給出的算法，首先將集合覆蓋問題轉換為線性規劃問題，即使傳感器節點的個數僅僅是100時，該線性方程組存在的約束方程也將達到2.7萬個，解該方程組的執行時間超過了1 000 s；而當區域面積增長到100×100 m2時，即使網格大小不變，此時的約束方程將增長到13萬個。這對于目前存在的PC機來說，顯然是不可能計算出最優解的。因此，本文不考慮將GDCA算法與文獻[10]中提出的算法之間的性能相比，而僅將GDCA算法與貪婪算法、GAF-like算法[9]和CVT+MST算法之間進行性能比較。
為了比較貪婪算法、CVT+MST算法、GAF-like算法和GDCA算法的優劣性，本文用MATLAB語言在Windows XP操作系統的平臺下設計了基于網格的密度控制算法的仿真程序，并實現了文獻[3]提出的貪婪算法、文獻[4]提出的CVT+MST算法和GAF-like算法。實驗條件如下：把100個以上的傳感器節點隨機均勻分布在50×50 m2的區域內，傳感器節點的傳感區域和通信區域均是一個圓形區域，傳感半徑Rs=10 m，通信半徑Rc=10~20 m，網格d=0.1 m。每一個仿真結果都是20次仿真實驗的平均值。
3.1 在不同節點個數下連通覆蓋集的大小
表1給出了當Rs=10 m，Rc=20 m時，上述四種算法網絡節點個數與連通覆蓋集的大小之間的關系。從表中可以看出，在具有相同節點個數的條件下，改進的GAF算法得到的連通覆蓋集最大，貪婪算法次之，GDCA算法略小于CVT+MST算法。這是由于貪婪算法總是尋找選擇能夠覆蓋住個數最多的還沒有覆蓋到格點的傳感器節點，這種全局貪婪導致得到的連通覆蓋集較大。而對于改進的GAF算法，因為它的每一個正六邊形的邊長最多為Rs/2，所以在最理想的情況下它至少需要8l2/（33Rs2）個活動的傳感器節點才能覆蓋l×l的區域。CVT+MST算法隨著網絡節點個數的增加，連通覆蓋集的大小略有增長；而GDCA算法連通覆蓋集的大小基本保持不變，當節點個數從200增加到300時，連通覆蓋集的大小略有下降。這是因為隨著節點個數的增加，選擇調度節點時候選節點增加，處于或接近最佳位置的節點概率增加。
當通信半徑小于2倍的傳感半徑時，GAF-like算法得到的覆蓋集不能保證網絡的連通。在本實驗中，GAF-like通過結合SPAN[7]算法來生成傳感器網絡的連通覆蓋集。表2為當Rs=10 m，Rc=15 m時，上述四種算法連通覆蓋集的大小與網絡節點個數之間的對應關系表。對比表1和2，當連通半徑Rc從20 m下降到15 m時，四種算法的連通覆蓋集都略有增長。當節點個數在100~200時，GDCA算法的連通覆蓋集稍微大于CVT+MST算法；隨著節點個數進一步增加，GDCA算法的連通覆蓋集基本保持在20.3左右，而CVT+MST算法呈現逐步遞增的趨勢。從上述兩個表中得到，GDCA算法構造與GAF-like算法和貪婪算法相比，前者構造的連通覆蓋集大小明顯低于后兩者，具有較為明顯的優勢；與CVT+MST算法相比，在不同節點密度下，前者構造的連通覆蓋集大小基本不變，而后者的連通覆蓋集大小保持著遞增的態勢；且前者為分布式算法，具有良好的擴展性，節點的傳感區域可為任意凸形區域，更符合實際情況，后者為集中式算法，僅適用于節點的傳感模型為圓盤模型的情況。
3.2 在不同通信范圍時連通覆蓋集的大小
圖6為在節點具有不同通信范圍時，連通覆蓋集大小與網絡節點個數的曲線。從圖中可以看出，當Rc/Rs≥3/2時，連通覆蓋集大小隨Rc/Rs的減少增長并不大；然而，當Rc/Rs很小時(如Rc/Rs≤1)，連通覆蓋集的大小隨Rc/Rs的減少急劇增加。當Rc/Rs=1與Rc/Rs=3/2相比，前者的連通覆蓋集的大小是后者的2.5倍以上。從圖中還可以看出，當Rc/Rs≥1時，連通覆蓋集的大小隨網絡節點個數的增加基本上是一個常量，當Rc/Rs≤1/2時，隨著網絡節點個數的增長，連通覆蓋集的大小一直保持著遞增的趨勢，然而遞增的幅度隨網絡節點個數的增長逐步放緩。
4 結束語
完全覆蓋和網絡連通是傳感器網絡應用于軍事監測、災難救助等重要領域需要滿足的服務。在保證完全覆蓋和網絡連通的前提下，本文設計了一種基于網格的密度控制算法GDCA。首先提出了一種基于網格的密度控制覆蓋算法，該算法得到的覆蓋集是完全覆蓋目標區域；然后在基于網格的密度控制覆蓋算法的基礎上提出了改進算法GDCA，確保被選擇出來的節點集構成的網絡為連通網絡。理論分析和仿真實驗表明，在不同的覆蓋半徑和通信半徑的比例下，與其他連通覆蓋算法相比，本文提出的算法能夠獲得更小的連通覆蓋集；且這種算法屬于分布式算法，具有良好的擴展性，節點的傳感區域可為圓形、矩形等任意凸形區域，更符合實際情況。
參考文獻：
［1］AGRE J，CLARE L.An integrated architecture for cooperative sensing networks[J].IEEE Trans on Computer，2000，33(5):106-108.
[2]任彥，張思東，張宏科.無線傳感器網絡中覆蓋控制理論與算法[J].軟件學報，2006，17(3):422-433.
[3]GUPTA H，DAS S R，GU Q.Connected sensor cover:self-organization of sensor networks for efficient query execution[C]//Proc of the 4th ACM International Symposium on Mobile Ad hoc Networking Computing.New York:ACM Press，2003:189-200.
[4]蔣杰，方力，張鶴穎.無線傳感器網絡最小連通覆蓋集問題求解算法[J].軟件學報，2006，17(2):175-184.
[5]YE Fan，ZHONG G，LU Song-wu，et al.PEAS:a robust energy conserving protocol for long-lived sensor networks[C]//Proc ofthe 23rd International Conference on Distributed Computing Systems.2003:28-37.
[6]ROMIT R C，ROBIN K.Location-independent coverage in wireless sensor networks[EB/OL].(2004).http://www crhc.uiuc.edu/～croy/pubs.
[7]CHEN Ben-jie，JAMIESON K，BALAKRISHNAN H，et al.Span:an energy efficient coordination algorithm for topology maintenance in Ad hoc wireless networks[J].ACM Wireless Networks，2002，8(5):481-494.
[8]GODFREY P，RATAJCZAK D.Naps:scalable，robust topology management in wireless Ad hoc networks[C]//Proc of the 3rd International Symposium on Information Processing in Sensor Networks. Berkeley: ACM Press，2004:443-451.
[9]ZHANG Hong-hai，HOU J C.Maintaining sensing coverage and connectivity in large sensor networks[J].Wireless Ad hoc and Sensor Networks，2005，1(1):89-123.
[10]CHEN Hai-ning，WU Hong-yi，ZENG Nian-feng.Grid-based approach for working node selection in wireless sensor networks[C]//Proc of International Conference on Communications.Piscataway:IEEE，2004:3673-3678.
