無線傳感器網絡中目標覆蓋圖的分解

張紅武，張 聰，豐洪才，楊博斐，劉昌華，袁 操，夏祥勝，管 華

(1.武漢工業學院 a.數學與計算機學院；b.現代教育技術中心，武漢 430023；2.浙江大學信息與電子工程系，杭州 310058)

1 概述

無線傳感器網絡是由部署在監測區域內大量傳感器節點組成[1-2]，通過無線通信連接成一個多跳的自組織網絡系統[3-4]。它能協作地感知[5-6]、采集和處理網絡覆蓋區域內被感知對象的信息[7-8]，并發送給觀察者[9-10]。

目標覆蓋是無線傳感器網絡的一個重要問題[11]，研究在完成監測任務的前提下，如何盡量節省能耗以最大化目標覆蓋生命期[12]。最大化目標覆蓋生命期的主要途徑，是合理配置網絡中各節點狀態，平衡網絡能耗和有效覆蓋率，提高網絡能效[13]。文獻[14-15]給出了最大目標覆蓋生命期問題的定義。

定義 1 給定傳感器網絡，目標覆蓋問題(Target Coverage Problem, TCP)是，在保證全部目標被連續監測的條件下，調度節點的活動，使網絡覆蓋的生命期最大。

TCP是一個NP完全問題[14-15]。隨著目標和傳感器節點的增加，無線傳感器網絡的規模迅速增大，TCP問題的難度也呈指數增長。

在無線傳感器中，減小網絡規模是減低算法復雜度的重要方法。但國內外還沒有刪除冗余節點、刪除冗余目標、將無線傳感器網絡的目標覆蓋圖分解成多個獨立子圖的算法相關的研究。

本文采用減小網絡規模的方法來降低算法的復雜度。首先，提出刪除冗余的傳感器節點的方法。其次，給出刪除冗余的目標的方法。最后，將目標覆蓋圖分解成多個獨立子圖，并描述構建獨立子圖算法(Construct Independent Sub Graph Algorithm,CISGA)。

2 問題描述

在二維平面內，m個隨機分布的目標要求被連續監測。為完成檢測任務，n個傳感器節點(簡稱節點)隨機投放在目標區域內。假設每個節點的有效監測半徑均為Rs，通信半徑為 Rc，且Rc≥2Rs。

假設基站能獲得全部傳感器節點和目標的坐標，并能計算出傳感器節點對目標的覆蓋關系。

傳感器網絡用圖G(S,T,E,W)表示[10]。其中，S是隨機分布的傳感器節點集，S={s1,s2,…,sm}；T是m個隨機分布的目標集合，T={t1,t2,…,tm}；E是eij中eij=1位置關系集，E={eij|i∈{1,2,…,n}, j∈{1,2,…, m}}，eij表示節點si與目標tj的位置關系，eij=1，當且僅當目標 tj與節點 si的歐氏距離小于或等于覆蓋半徑 R，d(si,tj)≤R 時；否則，eij=0；W= {w1,w2,…,wn}是傳感器節點初始能量集，wi表示傳感器節點 si的初始能量，wi用節點能工作的最大單位能量數表示。

3 問題分析

3.1 冗余節點的刪除

隨著傳感器節點和目標的增加，目標覆蓋問題的計算復雜度急劇增長。減少問題的規模是減少計算復雜度的最好方法。為此，本文設計了3種措施來減少目標覆蓋問題的規模。

傳感器網絡及其目標覆蓋網絡分解如圖1所示。圖1(a)所示是一個有5個傳感器節點{s1, s2, s3, s4, s5}和4個目標{t1, t2, t3, t4}的傳感器網絡。每個節點的覆蓋區域是以節點為圓心的圓，圓的半徑是節點的感知半徑。圖1(b)描述了節點和目標的覆蓋關系。若用T(si)

表示節點si覆蓋的目標集，則在圖1(b)中，T(s1)={t1,t2}, T(s2)={t3,t4}, T(s3)={t1,t2}, T(s4)= {t3,t4}, T(s5)=Φ。

在圖1(b)中，s5不覆蓋任何目標，為研究其能否被刪除，下面證明冗余節點的刪除定理。

圖1 傳感器網絡及其目標覆蓋網絡分解

定義 2 在不考慮節點連通的條件下，冗余節點是不覆蓋任何目標的傳感器節點。

定理 1 如果某節點不覆蓋任何目標，則該節點可以被刪除。

證明：由定義可知，在不考慮傳感器節點連通的情況下，目標覆蓋問題是調度能覆蓋目標的節點，而與不覆蓋目標的節點沒有任何影響。因此，刪除冗余節點，目標覆蓋問題沒有任何變化。

下面導出冗余節點刪除規則。

規則1 冗余節點可以刪除。

如圖1所示，刪除節點s5能減少無線傳感器網絡中的節點數目。特別是，在大量節點密集部署的無線傳感器網絡中，存在大量冗余節點。刪除這些冗余節點能大幅減少節點數目，從而減少目標覆蓋問題的計算復雜度。

3.2 冗余目標的刪除

如圖1所示，當t2被覆蓋時，則t1也一定被覆蓋，反之亦然。當t4被覆蓋時，則t3也一定被覆蓋，反之亦然。也就是說，若有 2個目標 ti和 tj，當 ti的覆蓋集等于tj的覆蓋集時，刪除其中的一個目標，能減少無線傳感器網絡中目標的數目，但對于目標覆蓋問題的最大生命期沒有影響。

若Ci表示目標ti的覆蓋集，Ci是由能夠覆蓋目標ti的節點組成的集合。如圖 1所示，C1={s1,s3},C2={s1,s3}, C3={s2,s4}, C4={s2,s4}。

定理 2 若 Ci=Ck，則當 ti被覆蓋，則 tk也一定覆蓋。

證明：當ti節點覆蓋，則 ? su∈ Ci，su覆蓋 ti。又因 Ci=Ck，所以 su∈Ck。也就是說，su也覆蓋tk。

從定理2可知，若2個目標的覆蓋集相等，當其中的一個目標被覆蓋時，則另一個目標也一定被覆蓋。因此，給出冗余目標的定義。

定義3 當2個或2個以上的目標覆蓋集相等時，則下標最小的目標是必要目標，其他目標都是冗余目標。冗余目標可以被刪除。

假設在某一時間段 b1內，為保證目標集 T的完全覆蓋，最優的活動節點集為S1。下面要證明刪除冗余目標后，為保證目標集T’的完全覆蓋，最優的活動節點集S1不改變。

定理 3 為保證目標的完全覆蓋，刪除冗余目標不會減少活動節點集中的活動節點。

證明：設 T1={ti,ti+1,…,tj}是一個具有相同覆蓋集的目標集，活動節點sk(sk∈S1)唯一覆蓋目標集T1。

當刪除T1中的冗余目標時，一定要保留T1中的必要目標，為保證該必要目標的覆蓋，sk必須保持活動狀態。也就是說，刪除冗余目標后，不會減少活動節點集中的活動節點。

由此，引出定理4。

定理 4 若刪除冗余目標，目標覆蓋問題的最大生命期不變。

證明：設目標覆蓋問題的最大生命期的最優時間序列為,,…,。其中，T是初始目標集；bk表示活動時刻；Sk是 bk的活動節點集。

由定理3，可知刪除目標集中的冗余節點后，不改變該時刻的活動節點集。則刪除 T中的冗余節點后，各活動節點集不會減少，當然也不會增加。這樣，目標覆蓋問題的最大生命期的最優時間序列不會發生變化。定理得證。

下面導出冗余目標刪除規則。

規則 2 當 Ci=Ck時，保留必要目標，刪除冗余目標。

特別地，在目標分布密集的無線傳感器網絡中，刪除冗余節點能大幅減小目標數目，從而減小目標覆蓋問題的算法復雜度。

3.3 目標覆蓋圖的分解

每一個目標覆蓋網絡都可以用一個目標覆蓋圖表示。例如圖1(a)可以表示成圖1(b)。為便于理解，將目標覆蓋網絡的分解描述成目標覆蓋圖的分解。

在目標覆蓋圖中，如果一個子圖與其他部分沒有公共節點和公共邊，則該子圖能被分割出來，成為一個獨立子圖。

如圖1(b)所示，目標覆蓋圖分割成2個獨立自網絡，一個子圖是 G(S1,T1,E1,W1)，其中，S1={s1,s2}；T1={t1,t2}；E1={e11,e12,e31,e32}。另一個子圖是G(S2,T2,E2,W2)，其中，S2={s2,s4}；T2={t3,t4}；E1={e23,e24,e43,e44}。

給定目標覆蓋圖 G(S,T,E,W)。G(S,T,E,W)能被分解成 2個獨立子網 G(S1,T1,E1,W1)和 G(S2,T2,E2,W2)，當且僅當 S1∪S2=S, T1∪T2=T, E1∪E2=E, W1∪W2=W,S1∩S2=Φ, T1∩T2=Φ, E1∩E2=Φ, W1∩W2=Φ。如此類推，可將子圖分解成更小的獨立子圖，直到不能再分為止。

下面提出一種構造獨立子圖算法CISGA。

定理 5 CISGA算法不改變目標覆蓋問題的最大生命期。

證明：CISGA算法只是將結構上獨立的子網從整體上分離出來。它既沒有增加邊，也沒有減少邊；它沒有增加或減少任何節點。也就是說，它沒有改變目標覆蓋圖的結構，不會改變目標覆蓋問題，所以也不會改變目標覆蓋問題的最大生命期。

4 算法仿真

在Windows XP上采用Matlab作為仿真軟件，在設定的500 m×500 m的矩形區域內，隨機產生目標的二維坐標、節點的二維坐標和初始能量。假設傳感器節點為全向覆蓋，覆蓋半徑為Rs=40 m。

實驗1 在監測區域內隨機放置25個目標后，再分別隨機放置40個、60個、80個、100個、120個、140個、160個、180個、200個節點。比較冗余節點的數目，取多次實驗的均值為實驗結果，實驗結果如圖2所示。

圖2 不同節點的無線傳感器網絡中的冗余節點個數

從圖2可見，無線傳感器網絡中存在冗余節點。刪除冗余節點能大幅減少目標覆蓋問題的規模。當節點分布越密集，則在非目標區域內存在更多的冗余節點，則刪除冗余節點來減小算法規模的效果越明顯。

實驗結果表明：刪除冗余節點能大大減少目標覆蓋問題的規模。

實驗 2 在監測區域內隨機放置 100個節點，再分別隨機放置25個、55個、85個、115個、135個、175個、205個、235個、265個、295個、325個目標。比較冗余目標的數目，取多次實驗的均值為實驗結果，實驗結果如圖3所示。

從圖3可見，無線傳感器網絡中存在冗余目標。刪除冗余目標能大大減少目標覆蓋問題的規模。當目標分布越密集，則在節點覆蓋區域內存在更多的目標，則冗余目標就越多。

圖3 不同目標的無線傳感器網絡中冗余目標的個數

實驗結果表明：刪除冗余目標能大幅減少目標覆蓋問題的規模。

實驗3 在監測區域內隨機放置25個目標后，再分別隨機放置25個、55個、85個、115個、135個、175個、205個、235個、265個、295個、325個目標。比較獨立子網的最大規模，取多次試驗的均值為實驗結果，實驗結果如圖4所示。

圖4 不同節點網絡中最大獨立子網的規模

從圖4可見，CISGA算法能大幅減小目標覆蓋圖的規模。隨著節點數目的增大，CISGA算法減小網絡規模的效果越明顯。

5 結束語

為了減小目標覆蓋問題的規模，本文設計了刪除冗余節點和冗余目標、分解獨立子圖的策略，并提出了一種構造獨立子網算法。仿真實驗證明，CISGA算法能降低30%的網絡規模，大幅減少了目標覆蓋問題的復雜度。該算法的復雜度低、效率高、可擴展性好。

目前，在無線傳感器網絡中，目標覆蓋與連通[16]、基于定向天線節點的目標覆蓋、基于移動節點的目標覆蓋[17]、三維空間的目標覆蓋、多目標的關聯覆蓋[18]等問題，都是NP-完全問題。研究這些問題的網絡分解算法是下一步的工作內容。

[1]Huang G T.Casting the Wireless Sensor Network[J].Technology Review, 2003, 106(6): 50-56.

[2]Kahn J, Katz R H, Pister K.Next Century Challenges:Mobile Networking for Smart Dust[C]//Proc.of the 5th Annual International Conference on Mobile Computing and Networking.New York, USA: ACM Press, 1999: 271-278.

[3]Raghunathan V, Schurgers C, Park S, et al.Energy-aware Wireless Microsensor Networks[J]. IEEE Signal Processing Magazine, 2002, 19(2): 40-50.

[4]Cardei M, Du Dingzhu.Improving Wireless Sensor Network Lifetime Through Power Aware Organization[J].ACM Wireless Networks, 2005, 11(3): 333-340.

[5]鄭增威, 吳朝暉, 金水祥.無線傳感器網絡及其應用[J].計算機科學, 2003, 30(10): 138-140.

[6]沈 波, 張世永, 鐘亦平.無線傳感器網絡分簇路由協議[J].軟件學報, 2006, 17(7): 1589-1600.

[7]張媛媛, 谷大武.無線傳感器網絡密鑰建立協議的能耗分析[J].信息安全與通信保密, 2007, 8(8): 85-89.

[8]文 戈, 王國軍, 過敏意.無線傳感器網絡中基于Voronoi圖的覆蓋和連通綜合配置協議[J].傳感技術學報, 2007, 20(10): 2294-2302.

[9]Zhang Hongwu, Wang Hongyuan, Feng Hongcai.A Heuristic Greedy Optimum Algorithm for Target Coverage in Wireless Sensor Networks[C]//Proc.of IEEE International Conference on Circuits, Communications and Systems.[S.l.]: IEEE Press, 2009: 39-42.

[10]張西紅, 妙文亮, 高彥彥.無線傳感器網絡的覆蓋問題研究[J].計算機工程, 2009, 35(16): 109-111.

[11]張紅武, 王宏遠, 豐洪才.一種無線傳感器網絡目標的最優覆蓋算法[J].小型微型計算機系統, 2009, 30(11):2146-2149.

[12]孫澤宇, 邢蕭飛, 巍 巍.無線傳感器網絡中的目標關聯覆蓋算法[J].計算機工程, 2011, 37(9): 138-143.

[13]王小平, 羅 軍, 沈昌祥.無線傳感器網絡定位理論和算法[J].計算機研究與發展, 2011, 48(3): 353-363.

[14]Cardei M, Thai M T, Li Yingshu, et al.Energy-efficient Target Coverage in Wireless Sensor Networks[C]//Proc.of the 24th Annual Joint Conference of the IEEE Computer and Communications Societies.[S.l.]: IEEE Press, 2005:1976-1984.

[15]Garey M R, Johnson D S.Computers and Intractability: A Guide to the Theory of NP-completeness, Freeman[M].New York, USA: [s.n.], 1977.

[16]曲家慶, 張 曙.連通和覆蓋性優化無線傳感器網絡壽命的方法[J].通信學報, 2011, 32(3): 361-365.

[17]王良民, 李 菲, 秦 穎.基于移動節點的無線傳感器網絡覆蓋洞修復方法[J].通信學報, 2011, 32(4): 456-461.

[18]孟凡治, 王換招, 何 暉.基于聯合感知模型的無線傳感器網絡連通性覆蓋協議[J].電子學報, 2011, 39(4):772-779.