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

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

1 概述

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

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

定義 1 給定傳感器網(wǎng)絡(luò)，目標覆蓋問題(Target Coverage Problem, TCP)是，在保證全部目標被連續(xù)監(jiān)測的條件下，調(diào)度節(jié)點的活動，使網(wǎng)絡(luò)覆蓋的生命期最大。

TCP是一個NP完全問題[14-15]。隨著目標和傳感器節(jié)點的增加，無線傳感器網(wǎng)絡(luò)的規(guī)模迅速增大，TCP問題的難度也呈指數(shù)增長。

在無線傳感器中，減小網(wǎng)絡(luò)規(guī)模是減低算法復雜度的重要方法。但國內(nèi)外還沒有刪除冗余節(jié)點、刪除冗余目標、將無線傳感器網(wǎng)絡(luò)的目標覆蓋圖分解成多個獨立子圖的算法相關(guān)的研究。

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

2 問題描述

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

假設(shè)基站能獲得全部傳感器節(jié)點和目標的坐標，并能計算出傳感器節(jié)點對目標的覆蓋關(guān)系。

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

3 問題分析

3.1 冗余節(jié)點的刪除

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

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

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

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

圖1 傳感器網(wǎng)絡(luò)及其目標覆蓋網(wǎng)絡(luò)分解

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

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

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

下面導出冗余節(jié)點刪除規(guī)則。

規(guī)則1 冗余節(jié)點可以刪除。

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

3.2 冗余目標的刪除

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

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

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

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

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

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

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

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

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

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

由此，引出定理4。

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

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

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

下面導出冗余目標刪除規(guī)則。

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

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

3.3 目標覆蓋圖的分解

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

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

如圖1(b)所示，目標覆蓋圖分割成2個獨立自網(wǎng)絡(luò)，一個子圖是 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個獨立子網(wǎng) 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=Φ。如此類推，可將子圖分解成更小的獨立子圖，直到不能再分為止。

下面提出一種構(gòu)造獨立子圖算法CISGA。

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

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

4 算法仿真

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

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

圖2 不同節(jié)點的無線傳感器網(wǎng)絡(luò)中的冗余節(jié)點個數(shù)

從圖2可見，無線傳感器網(wǎng)絡(luò)中存在冗余節(jié)點。刪除冗余節(jié)點能大幅減少目標覆蓋問題的規(guī)模。當節(jié)點分布越密集，則在非目標區(qū)域內(nèi)存在更多的冗余節(jié)點，則刪除冗余節(jié)點來減小算法規(guī)模的效果越明顯。

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

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

從圖3可見，無線傳感器網(wǎng)絡(luò)中存在冗余目標。刪除冗余目標能大大減少目標覆蓋問題的規(guī)模。當目標分布越密集，則在節(jié)點覆蓋區(qū)域內(nèi)存在更多的目標，則冗余目標就越多。

圖3 不同目標的無線傳感器網(wǎng)絡(luò)中冗余目標的個數(shù)

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

實驗3 在監(jiān)測區(qū)域內(nèi)隨機放置25個目標后，再分別隨機放置25個、55個、85個、115個、135個、175個、205個、235個、265個、295個、325個目標。比較獨立子網(wǎng)的最大規(guī)模，取多次試驗的均值為實驗結(jié)果，實驗結(jié)果如圖4所示。

圖4 不同節(jié)點網(wǎng)絡(luò)中最大獨立子網(wǎng)的規(guī)模

從圖4可見，CISGA算法能大幅減小目標覆蓋圖的規(guī)模。隨著節(jié)點數(shù)目的增大，CISGA算法減小網(wǎng)絡(luò)規(guī)模的效果越明顯。

5 結(jié)束語

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

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

[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]鄭增威, 吳朝暉, 金水祥.無線傳感器網(wǎng)絡(luò)及其應(yīng)用[J].計算機科學, 2003, 30(10): 138-140.

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

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

[8]文 戈, 王國軍, 過敏意.無線傳感器網(wǎng)絡(luò)中基于Voronoi圖的覆蓋和連通綜合配置協(xié)議[J].傳感技術(shù)學報, 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]張西紅, 妙文亮, 高彥彥.無線傳感器網(wǎng)絡(luò)的覆蓋問題研究[J].計算機工程, 2009, 35(16): 109-111.

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

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

[13]王小平, 羅 軍, 沈昌祥.無線傳感器網(wǎng)絡(luò)定位理論和算法[J].計算機研究與發(fā)展, 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]曲家慶, 張 曙.連通和覆蓋性優(yōu)化無線傳感器網(wǎng)絡(luò)壽命的方法[J].通信學報, 2011, 32(3): 361-365.

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

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