ＷＳＮ中有效的最小單位圓集覆蓋算法
2009-01-01 00:00:00張晉劉大昕徐悅竹
計算機應用研究 2009年6期
摘 要：針對具有不同傳輸半徑的無線傳感器網絡覆蓋與廣播數據轉發問題，提出了一種以最小單位圓覆蓋集作為廣播數據轉發集的算法。該算法能有效計算出覆蓋范圍的輪廓集，具有最優的時間復雜度O(n log n)。對每個節點，該算法以其最少數量的鄰居節點子集實現所有鄰居節點的覆蓋，并證明了該算法找到的最小單位圓覆蓋集與其輪廓集是相等的。詳細的仿真實驗及與現有算法的比較表明，提出的覆蓋算法不僅以最少數量的節點實現了網絡覆蓋與廣播數據轉發，同時延長了網絡生命期。
關鍵詞：無線傳感器網絡；覆蓋算法；單位圓覆蓋集；能量
中圖分類號：TP302文獻標志碼：A
文章編號：1001-3695(2009)06-2195-04
doi:10.3969/j.issn.1001-3695.2009.06.059
Efficient minimum unit disks set coverage algorithm in wireless sensor networks
ZHANG Jin，LIU Da-xin，XU Yue-zhu
(College of Computer Science Technology， Harbin Engineering University， Harbin 150001， China)
Abstract:To overcome coverage and broadcasting data forwarding problems in wireless sensor networks with different transmission radius nodes，this paper proposed a novel algorithm based on minimum unit disks cover set to forward broadcasting data， which could calculate skyline set efficiently with the optimal time complexity O(n log n).The proposed algorithm covered each node with minimum unit disk cover set， and the minimum unit disk cover set of a node was equivalent to its skyline set. Detailed simulation results and comparisons with existed algorithms prove that the proposed algorithm not only covers all nodes with minimum nodes， but also prolongs the network lifetime.
Key words:wireless sensor networks(WSN); covering algorithm; unit disk cover set; energy
無線傳感器網絡（WSN）利用大量具有數據采集、處理及無線通信功能的微型智能節點在網絡覆蓋區域內協作完成復雜的監測任務，而WSN覆蓋優化可以有效提高測量可靠度與精度，成為WSN領域研究的重要問題之一[1]。尤其是實現WSN中的信息覆蓋[2，3]，不僅可以實現感知數據的有效轉發，同時可以節省傳感器網絡節點能量，延長網絡的生命周期，進而使感知、監視、傳感、通信等各種服務質量得到改善。
目前，國內外學者相繼開展了信息覆蓋問題的研究，并取得了一定的進展[2~5]。文獻[2， 3]提出了信息覆蓋的概念，對隨機布置的WSN中的信息覆蓋問題進行了研究，考慮傳感器節點密度的前提下的完全信息覆蓋性能，并給出了基于概率的信息覆蓋上邊界。Zou等人[4]對WSN中以覆蓋與連通性為中心的傳感器節點選擇問題進行了研究，通過選擇合適的節點實現網絡覆蓋并保證連通性。文獻[5]對WSN中具有能量有效性的覆蓋問題進行了研究，提出了保證節點能量的覆蓋算法。文獻[6， 7]對不可靠格點傳感器的覆蓋、連通性進行了研究，考慮了不同覆蓋半徑對連通性與覆蓋范圍的影響，但是該方法并沒有考慮能量有效性的問題。Calinescu等人[8]則通過選擇合適的轉發節點實現數據的發送，以實現覆蓋的功能，但該方法并不適合于監控范圍廣的場景。盡管目前有很多工作對覆蓋增強問題進行了研究[5~8]，并且研究熱點正逐步向著實用化、實際的應用場景方向發展，但是在很多實際應用中，尤其是對于監控范圍較廣的場景，不僅需要考慮能量有效性、連通性與覆蓋范圍，同時必須對網絡中的數據信息（如廣播信息、感知數據等）進行有效的覆蓋，而現有的覆蓋算法并沒有針對上述問題提出有效的解決方法。
1 最小單位圓集覆蓋算法
1.1 問題描述
為了降低節點的能量消耗，對于傳感器網絡中的廣播數據，一方面要以盡可能少的節點作為轉發節點集，同時又需要保證廣播數據必須到達整個網絡中的所有節點。因此，對當前節點，其選擇的轉發節點必須保證數據能到達該節點所有的兩跳鄰居節點，即實現局部信息覆蓋，進而實現整個網絡的全局信息覆蓋。假設所有節點分布在一個二維平面R2中，‖x‖表示二維平面R2中節點的歐氏范式。對于任意兩個節點x，y∈R2，‖x-y‖表示兩個節點之間的歐氏距離，xy表示與兩個節點之間的線段，xy→表示從x到y的一條射線。網絡的拓撲結構用具有雙向鏈路的單位圓進行模擬。如圖1（a）所示，節點ui的傳輸半徑為ri。當兩個節點ui與uj之間的距離小于兩者的傳輸半徑之和時，兩個節點之間存在一條鏈路。當兩個節點ui與uj之間的歐氏距離滿足：
‖ui-uj‖≤min(ri，rj)（1）
ui與uj稱為鄰居。如圖1（b）所示，對于節點ui，其覆蓋范圍表示以ui為中心、半徑為ri的圓，用B(ui，ri)表示。當節點uj∈B(ui，ri)時，稱節點uj被ui覆蓋。集合SR2的拓撲邊界表示為S，因此B(ui，ri)表示以ui為中心、半徑為ri的圓。假定每個節點都知道其一跳范圍內的鄰居節點信息，如位置信息與傳輸半徑，根據雙向鏈路模型，對于任意兩個節點ui與uj，如果ui為uj的一跳鄰居節點，則意味著uj也是ui的一跳鄰居節點。因此對于一跳鄰居節點的覆蓋范圍其交集滿足：
∩ui∈S(ui，ri)≠（2）
其中：S表示一跳內的鄰居節點。為了保證廣播數據能到達該節點所有的兩跳鄰居節點，對于節點集合，定義單位圓覆蓋集SV，并滿足：
∩ui∈SN(ui，ri)=∩ui∈VN(ui，ri)（3）
對于節點集V，如果存在一個節點使得V中的所有其他節點都為該節點的鄰居節點，則V稱為本地集，其對應的單位圓集{N(ui，ri)，…，N(un，rn)}稱為本地單位圓集。
為了保障廣播數據到達整個網絡的同時，降低節點的能量消耗并延長網絡生命周期，有效的方式是選擇合適的節點作為轉發節點，形成一個有效的覆蓋，減少轉發節點的數量。該問題可以表示為最小本地單位圓覆蓋集求解問題：
已知本地單位圓集{N(u0，r0)，N(u1，r1)，…，N(un，rn)}，對于所有的i∈[1，n]，滿足‖u0-ui‖≤min(r0，ri)，其中ui∈N(u0，r0)，u0∈N(ui，ri)，V={u0，u0，…，un}表示單位圓中心的集合。求解V的最小子集S，即min|S|，同時滿足∩ui∈SN(ui，ri)=∩ui∈VN(ui，ri)。
1.2 算法描述
對于給定的本地單位圓集{N（u0，r0），N(u1，r1)，…，N(un，rn)}以及節點單位圓中心集V={u0，u1，…，un}，不失一般性，假設n0=o，為了構建最小本地單位圓覆蓋集，引入以下引理。
引理1 對于任意點m∈N(ui，ri)，所以有線段omN(ui，ri)。
證明 由于‖o-ui‖≤ri，有oN(ui，ri)。因為N(ui，ri)為凸連接，且o，m∈N(ui，ri)，有線段omN(ui，ri)。
推論1 對于以o為起點的任意射線，與輪廓線只相交于一點。
證明 顯然，以o為起點的任意射線必定與其覆蓋的輪廓線相交，因此只需要證其惟一性。假設存在一條射線與輪廓線相交于兩點a與b；不失一般性，假設a離o比b離o遠。由于a在輪廓線上，存在i使得a∈N(ui，ri)。根據引理1，有oaN(ui，ri)，這意味著b在N(ui，ri)內部，不可能在其覆蓋范圍的輪廓線上，與假設矛盾，推論得證。
根據推論1可知，輪廓線由一系列弧組成，一段弧可以用四個參數(αi，uj，ruj，αi+1)表示。這里uj和ri分別表示該弧對應的圓的圓心和半徑；αi和αi+1分別表示以x軸開始按逆時針方向，段弧的起點和終點與o點之間的線段所對應的夾角。由n段弧組成的輪廓線可以表示為(α0，us0，rs0
，αi+1，us1，rs1，α2，…，αn)。其中：α0=0；αi＜αi+1；i∈[0，n-1]；αn=2π。
定理1 對于給定的本地單位圓中心的集V={u0，u1，…，un}，其最小單位圓覆蓋集為相應的本地單位圓集{N(u0，r0)，N(u1，r1)，…，N(un，rn)}的輪廓線集。
證明 為了證明輪廓線集是最小單位圓覆蓋集，先證明輪廓線集是單位圓覆蓋集。假設輪廓線由分別屬于N(ui1，ri1)，N(ui2，ri2)，…，N(uik，rik)的弧段a1b1，a2b2，…，akbk組成。用≮oajbj表示由線段oaj、obj與ajbj圍成的扇區，每個扇區與其他扇區沒有重疊區域。因此有
∪ni=0N(ui，ri)=∪kj=1≮oajbj（4）
根據引理1，每個輪廓線弧≮oajbjN(uij，rij)，因此有∪ni=0N(ui，ri)∪kj=1N(uij，rij)，這意味著{N(ui1，ri1)，N(ui2，ri2)，…，N(uik，rik)}是一個單位圓覆蓋集。
假設點a在N(ui，ri)的輪廓線弧段內，對任一N(ui，ri)，j≠i，有‖uj-a‖＞rj。定義r=(minj≠i‖uj-a‖-rj)/2，可以a為圓心、r為半徑得到圓。對任意點x∈N(a，r)，j≠i，有
‖uj-x‖≥‖uj-a‖-‖x-a‖≥‖uj-a‖-(minj≠i‖uj-a‖-rj)/2＞‖uj-a‖-(‖uj-a‖-rj)=rj（5）
對于任一j≠i，有N(a，r)∩N(uj，rj)=。這意味著
N(a，r)∩N(uj，rj)屬于N(ui，ri)，但不屬于任何其他圓。
N(a，r)∩N(uj，rj)被N(ui，ri)惟一覆蓋。當N（ui，ri）屬于輪廓線集時，N(ui，ri)必定在任一單位圓覆蓋集中。定理得證。
輪廓線求解算法algorithm(MS)偽代碼如下：
輸入 MS={(u1，r1)，…，(un，rn)}
輸出 最小單位圓覆蓋集S
begin
if|MS|=1 return {N(u1，r1)}的輪廓線
else begin
MS1={(u1，ru1)，…，(un/2」，run/2」)}
MS2={(un/2」，run/2」+1)，…，(un，run)}
輪廓線集S1=algorithm(MS1)
輪廓線集S2=algorithm(MS2)
對集合S1，S2中的弧段進行排列，計算出S1=(α0，u1，ru1，α1，…，αm)，
S2=(α0，v1，rv1，α1，…，αm)
對每個i∈[0，m]，根據具有相同角度的弧段(αi，ui，rui，αi+1)與
(αi，vi，rvi，αi+1)計算出新的輪廓弧段
對相同單位圓，合并鄰居輪廓弧段，得到最小單位圓覆蓋集S
end
end
算法將單位圓集分為兩個子集S1、S2，并采用遞歸方式實現輪廓線集查找，再對集合中的弧段進行排列得到新的集合。對具有相同角度的弧段計算出新的輪廓弧段；對相同單位圓的，合并鄰居輪廓弧段，得到最小單位圓覆蓋集S。
2 算法性能分析
為了分析算法的性能，引入以下引理：
引理2 對于輪廓線B1，B2，…，Bn，如果Bn產生至少三段弧，當Bn產生的三段弧為Bi、Bj、Bk、Bn時，一定能從B1，B2，…，Bn-1中找出Bi、Bj、Bk。
證明 假設Bn產生的段弧大于3，由于每段弧有兩個端點，Bn中至少包含八個交點。但是Bi、Bj、Bk與Bn至多只有六個交點，與假設矛盾，因此Bn只能產生三段弧。從輪廓線B1，B2，…，Bn中選出Bn產生的三段弧，并考慮與Bn相交的單位圓。由于每個單位圓的邊界與Bn可以產生一或兩個交點，這六個交點是Bn與另外的3或者4、5、6個單位圓產生的。如果另外的單位圓個數為3，則引理得證。因此，只需考慮個數為4、5或6個時的情況。通過結算端點數量可知，如果單位圓個數大于3，則與Bn至少有一個交點位于輪廓線上。如果刪除與Bn相交只有一個交點的單位圓，則由Bn產生的段弧并不會減少。
如圖2（a）所示，輪廓線包括四個單位圓B1、B2、B3、B4及Bn產生的三段弧，其中產生的段弧用虛線表示。由于B4與Bn只有一個交點，刪除B4并不會減少Bn產生的段弧數量，如圖2（b）所示。重復上述步驟，直到只剩三個單位圓為止。引理得證。
引理3 假設兩個圓B1與B2有兩個交點a和d，用ac′和ab′分別表示B1和B2的直徑，c和b分別表示弧段c′d和b′d上的點。如果角∠cab為鈍角，有
‖b-c‖＞2 min(r1，r2)(6)
證明 首先考慮B1與B2相切的情況。如果a、c′、b′在一條直線上，a和d重合，∠cab=π/2。由于ac′和ab′分別為B1和B2的直徑，∠c′ca和∠b′ba分別為直角。△c′ca與△b′ba相似。如果r1≤r2，有
‖b-c‖2＞‖a-c‖2+‖a-b‖2=‖b-c‖2+（(r2/r1)‖c′-c‖)2≥(2r1)2=(2 min(r1，r2))2(7)
當r1≥r2時，同理可得‖b-c‖2≥(2 min(r1，r2))2。因此有‖b-c‖≥2 min(r1，r2)，引理得證。
對于一般的情況，可對該不等式作簡單的變換。將B1或B2以點a進行旋轉使∠c′ab′變小，但保持ac′與ac不相交，ab′與ab不相交。用c″表示射線ac與B1的交點，b″表示射線ab與B2的交點，此時有
‖a-b″‖≥‖a-b‖（8）
‖a-c″‖≥‖a-c‖（9）
因此有‖b″-c″‖≥‖b-c‖（10）
引理完全證明。
引理4 給定銳角，對于銳角的每條邊，以該邊為弦，圓心在角外，以外接圓半徑為半徑作圓，三個圓相交于重心。
根據幾何知識易證該引理，證明略。
推論2 給定一個銳角或直角，對于該角的每個邊，以邊為弦，圓心在角外，以大于外接圓半徑為半徑作圓，三個圓無交點。
根據幾何知識與引理4易證該推論，證明略。
引理5 具有n個單位圓的輪廓線的弧段數量的上邊界為2n。
證明 不失一般性，假設所有的n個節點在輪廓線中都有弧段，且B1，B2，…，Bn已經按照半徑大小降序排列。
當n=1時，只有一個單位圓，因此輪廓線包含一個弧段。
當n=2時，兩個單位圓相交于兩點，在輪廓線中至多有兩個弧段。
當n=3時，單位圓之間的拓撲位置關系可以表示為圖3所示。很顯然，此時仍然有輪廓線的弧段數量不大于2n。
假設當n=k時，有輪廓線至多包含2k段弧。當n=k+1時，假設Bk+1為B0，B1，…，Bk+1中半徑最小的單位圓，假設Bk+1至少產生三段弧，根據引理2，假定Bk+1產生的三段弧在輪廓線B1、B2、B3、Bk+1中，根據圖3中所示B1、B2、B3可能的兩種情況進行證明。
用a表示在B1和B2但不在B3的交點，b表示在B1和B3但不在B2的交點，c表示在B2和B3但不在B1的交點。為了產生三段弧，Bk+1必須與三個單位圓相交且包含a、b、c。
a)當△abc為銳角或直角三角形時，用rc表示△abc直徑。由于△abc為銳角或直角三角形，Bk+1包含a、b、c，有rk+1＞rc。由于Bk+1為B0，B1，…，Bk+1中半徑最小的單位圓，有r1，r2，r3≥rk+1＞rc。但是根據推論2，如果r1，r2，r3＞rc，B1、B2、B3無交點，這與假設矛盾。
b)當△abc為鈍角三角形時，如果∠abc為鈍角，由于Bk+1產生的三段弧在輪廓線B1、B2、B3、Bk+1中，并且有r1，r2，r3≥rk+1，每個弧段的角度都大于π。如果ac′為B2的直徑，ab′為B1的直徑，c′與b′位于輪廓線B1、B2、B3上。根據引理3，如果∠abc為鈍角，有‖b-c‖＞2 min(r1，r2)。由于Bk+1包含△abc，有rk+1≥‖b-c‖/2，即2rk+1≥‖b-c‖＞2 min(r1，r2)。因此存在矛盾。
根據上述討論可知，Bk+1不可能產生大于三段的弧線。因此，輪廓線的數量至多為2(k+1)，引理得證。
定理2 當單位圓為n時，輪廓線求解算法的時間復雜性為O(n log n)。
證明 對于輪廓線求解算法，其運行時間為
T(n)=O(1)n=1
2T(n/2)+f(n)n＞1(11)
根據引理，合并算法的時間復雜度為O(n)，因此，根據算法理論[6]有T(n)=O(n)， f(n)與弧段數量成線性關系，根據引理5可知其上限為2n，有f(n)=O(n)。因此，輪廓線求解
算法的時間復雜性為O(n log n)。
3 仿真結果
為了證明提出算法的有效性，仿真系統對基于網格的覆蓋算法（GCA）[7]、選擇性轉發集算法（SFA）[8]與提出的最小單位圓集覆蓋算法（MUSCA）進行了性能比較。仿真系統對所有節點傳輸半徑都相同的同構網絡與節點傳輸半徑不同的異構網絡的性能進行了分析。考察每個節點的一跳鄰居節點數量變化時所選節點的數量以及所選轉發節點數量變化時系統能覆蓋節點的數量變化情況。
圖4為所有節點傳輸半徑都相同的同構網絡一跳鄰居節點數量變化時，三種不同的算法所產生的轉發集節點數。很明顯，在任意一跳鄰居節點數情況下，提出的算法都具有最少的轉發集節點數。隨著一跳鄰居節點數的增加，三種算法所產生的轉發集節點數也相應地增加。對于基于網格的覆蓋GCA算法，其轉發集節點數與一跳鄰居節點數相等，這與該算法的思想是一致的。對于選擇性轉發集算法SFA，隨著一跳鄰居節點數的增加，其轉發集節點數從3.1到13個，比GCA算法要少；而對于提出的MUSCA算法，隨著一跳鄰居節點數的增加，其轉發集節點數從2.5增加到6.7個，是三種算法中產生的轉發集節點數最少的，而且其產生的轉發集節點數隨著一跳鄰居節點數的增加并不明顯，這也表明提出的MUSCA算法具有很強的適應性。
圖5為同構網絡中所選轉發集節點數變化時，三種算法所能覆蓋的節點數量。從圖5中可以看出，當所形成的轉發集節點數量變化時，提出的算法能覆蓋的節點數明顯比其他兩種算法多。隨著轉發集節點數的增加，對于選擇性轉發集算法SFA，其覆蓋的節點數從12增加到174個；對于基于網格的算法GCA，其覆蓋的節點數從8增加到154個；對于提出的MUSCA算法，覆蓋的節點數從25增加到180個。原因在于，當所選的轉發集節點數相同時，此時對GCA算法而言，并沒有選擇每個節點的所有一跳鄰居節點，因此并不能實現所有節點的覆蓋，導致其覆蓋節點數最少；而對于提出的MUSCA算法，盡管此時選擇的轉發節點數比鄰居節點數少，但該算法均能以覆蓋范圍為目標，盡可能地選擇合適的轉發節點，因此其覆蓋節點數最大，這也證明了提出的MUSCA算法具有良好的覆蓋能力。
圖6為同構網絡中數據轉發跳數變化時，三種算法的網絡生命周期。從圖6中可以看出，當數據轉發跳數變化時，提出的算法的網絡生命期明顯比其他兩種算法長；隨著跳數增加，對于選擇性轉發集算法，其生命期從48增加到114；對于泛洪算法，其生命期基本上保持在40左右；而對于提出的算法，生命期從65增加到192個。原因在于，無論轉發跳數為多少，泛洪算法總是選擇所有的節點轉發數據，因而所有節點都消耗能量，其生命期與單一節點一直發送數據的時間相同，保持為一常數；而對于提出的算法，由于該算法以覆蓋范圍為目標，盡可能地選擇合適的轉發節點，減少了轉發節點的數量，延長了網絡的生命期。
圖7為所有節點傳輸半徑不同的異構網絡一跳鄰居節點數量變化時，三種不同的算法所產生的轉發集節點數。從圖7中可以看出，無論一跳鄰居節點數為多少，提出的算法都具有最少的轉發集節點數；隨著一跳鄰居節點數的增加，三種算法所產生的轉發集節點數也相應地增加。對于GCA算法，其轉發集節點數與一跳鄰居節點數相等，但有時比一跳鄰居節點數還大，這表明該算法在節點傳輸半徑不同的網絡中，并不能形成有效的覆蓋網絡，可能出現回路情況，即同一節點多次選擇，這與GCA算法在覆蓋時假設所有節點的覆蓋范圍相同的假設思想是一致的；對于選擇性轉發集算法SFA，隨著一跳鄰居節點數的增加，其轉發集節點數從3.8增加到11.7個，比GCA算法要少；對于提出的算法，隨著一跳鄰居節點數的增加，其轉發集節點數從2增加到2.1個，是三種算法中產生的轉發集節點數最少的，而且其產生的轉發集節點數隨著一跳鄰居節點數的增加并不明顯，這也表明提出的算法具有很強的適應性。另外，與圖4中所示的同構網絡相比，選擇性轉發集算法與提出的算法所產生的轉發集節點數都要小一些。其原因在于，節點傳輸半徑不同時，形成了重疊覆蓋區域，這兩種算法都能選擇盡可能少的節點形成覆蓋整個網絡節點的輪廓線集，因此，重疊覆蓋區域的出現減少了選擇的節點數。
圖8為異構網絡中所選轉發集節點數變化時，三種算法所能覆蓋的節點數量。從圖8中可以看出，當所形成的轉發集節點數量變化時，提出的算法MUSCA能覆蓋的節點數比其他兩種算法多，隨著轉發集節點數的增加，對于GCA算法，其覆蓋的節點數從19增加到200個；對于選擇性轉發集算法，其覆蓋的節點數從9增加到168個；而對于提出的MUSCA算法，覆蓋的節點數從27增加到204個。原因在于，當所選的轉發集節點數相同時，此時對GCA算法而言，并沒有選擇每個節點的所有一跳鄰居節點，因此并不能實現所有節點的覆蓋，導致其覆蓋節點數最少；對于提出的MUSCA算法，盡管此時選擇的轉發節點數比鄰居節點數少，但該算法都能以覆蓋范圍為目標，盡可能選擇合適的轉發節點，因此其覆蓋節點數最大，這也證明了提出的算法具有良好的覆蓋能力。另外，與圖5中所示的結果相比，選擇性轉發集算法的性能有所降低，其原因是該算法是針對同構網絡提出的，當節點的傳輸范圍不同時，該算法并不能很好地實現轉發節點的選擇；而對于提出的MUSCA算法，其覆蓋的節點數量有所增加，這也證明了提出的算法不僅適合于同構網絡，也適合于異構網絡。
圖9為異構網絡中數據轉發跳數變化時，三種算法的網絡生命周期。從圖9中可以看出，當跳數增加時，提出的算法MUSCA的網絡生命期明顯比其他兩種算法長，這與圖6所示的結果基本一致。但與圖6相比，存在幾點不同：a）對于選擇性轉發集算法，其網絡生命期有所延長，原因在于該算法并不適合于異構網絡，因此有部分節點并沒有被選中，從一定程度上延長了網絡生命期；b)對于提出的MUSCA算法，該算法在考慮覆蓋范圍重疊的前提下，以覆蓋范圍為目標，盡可能選擇合適的轉發節點，減少了轉發節點的數量，進一步延長了網絡的生命期，因此其網絡生命周期性能進一步得到提高。
4 結束語
本文提出一種以最小單位圓覆蓋集作為廣播數據轉發集的算法。該算法具有最優的時間復雜度O（n log n），并能有效地計算出輪廓線覆蓋集，為WSN中的信息覆蓋與廣播數據的轉發提供了一種切實可行且有效的方法。
參考文獻：
［1］CORTES J， MARTINEZ S， KARATAS T，et al.Coverage control for mobile sensing networks [J].IEEE Trans on Robotics and Automation，2004，20(2):243-255.
［2］WANG Bang，WANG Wei，SRINIVASAN V，et al.Information coverage for wireless sensor networks[J].IEEE Communications Letters，2005，9(11):967-969.
［3］WANG Bang， KEE C C， SRINIVASAN V，et al.Information coverage in randomly deployed wireless sensor networks[J].IEEE Trans on Wireless Communications，2007，6(8):2994-3004.
［4］ZOU Yi，CHAKRABARTY K.A distributed coverage and connectivity-centric technique for selecting active nodes in wireless sensor networks[J].IEEE Trans on Computers，2005，54(8):978-991.
［5］MIHAELA C，WU Jie. Energy-efficient coverage problems in wireless Ad hoc sensor networks[J].Computer Communications，2006，29(4): 413-420.
［6］CORMEN T H， LEISERSON C E， RIVEST R L，et al.Introduction to algorithms[M].2nd ed. New Jersey:MIT Press，2001.
［7］SHAKKOTTAI S， SRIKANT R， SHROFF N.Unreliable sensor grids:coverage， connectivity and diameter[C]//Proc of the 22nd Annual Joint Conference on Computer and Communications Societies.San Francisco:IEEE Press，2003:1073-1083.
［8］CLINESCU G， MNDOIU I， WAN Peng-jun，et al.Selecting forwarding neighbors in wireless sensor network[C]//Proc of the 5th International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications.New York:ACM Press，2001：34-43.
