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

(1.武漢工業(yè)學(xué)院 a.數(shù)學(xué)與計算機(jī)學(xué)院；b.現(xiàn)代教育技術(shù)中心，武漢 430023；2.浙江大學(xué)信息與電子工程系，杭州 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]。

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

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

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

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

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

2 問題描述

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

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

傳感器網(wǎng)絡(luò)用圖G(S,T,E,W)表示[10]。其中，S是隨機(jī)分布的傳感器節(jié)點集，S={s1,s2,…,sm}；T是m個隨機(jī)分布的目標(biāo)集合，T={t1,t2,…,tm}；E是eij中eij=1位置關(guān)系集，E={eij|i∈{1,2,…,n}, j∈{1,2,…, m}}，eij表示節(jié)點si與目標(biāo)tj的位置關(guān)系，eij=1，當(dāng)且僅當(dāng)目標(biāo) 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é)點和目標(biāo)的增加，目標(biāo)覆蓋問題的計算復(fù)雜度急劇增長。減少問題的規(guī)模是減少計算復(fù)雜度的最好方法。為此，本文設(shè)計了3種措施來減少目標(biāo)覆蓋問題的規(guī)模。

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

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

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

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

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

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

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

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

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

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

3.2 冗余目標(biāo)的刪除

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

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

定理 2 若 Ci=Ck，則當(dāng) ti被覆蓋，則 tk也一定覆蓋。

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

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

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

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

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

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

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

由此，引出定理4。

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

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

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

下面導(dǎo)出冗余目標(biāo)刪除規(guī)則。

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

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

3.3 目標(biāo)覆蓋圖的分解

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

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

如圖1(b)所示，目標(biāo)覆蓋圖分割成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}。

給定目標(biāo)覆蓋圖 G(S,T,E,W)。G(S,T,E,W)能被分解成 2個獨立子網(wǎng) G(S1,T1,E1,W1)和 G(S2,T2,E2,W2)，當(dāng)且僅當(dāng) 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算法不改變目標(biāo)覆蓋問題的最大生命期。

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

4 算法仿真

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

實驗1 在監(jiān)測區(qū)域內(nèi)隨機(jī)放置25個目標(biāo)后，再分別隨機(jī)放置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é)點能大幅減少目標(biāo)覆蓋問題的規(guī)模。當(dāng)節(jié)點分布越密集，則在非目標(biāo)區(qū)域內(nèi)存在更多的冗余節(jié)點，則刪除冗余節(jié)點來減小算法規(guī)模的效果越明顯。

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

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

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

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

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

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

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

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

5 結(jié)束語

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

目前，在無線傳感器網(wǎng)絡(luò)中，目標(biāo)覆蓋與連通[16]、基于定向天線節(jié)點的目標(biāo)覆蓋、基于移動節(jié)點的目標(biāo)覆蓋[17]、三維空間的目標(biāo)覆蓋、多目標(biāo)的關(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].計算機(jī)科學(xué), 2003, 30(10): 138-140.

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

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

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

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

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

[13]王小平, 羅 軍, 沈昌祥.無線傳感器網(wǎng)絡(luò)定位理論和算法[J].計算機(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].通信學(xué)報, 2011, 32(3): 361-365.

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

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