楊鳳偉，陳小惠，劉銀鋒

（南京郵電大學(xué)自動(dòng)化學(xué)院，江蘇 南京，210003）

0 引言

無(wú)線傳感器網(wǎng)絡(luò)(wireless sensor network，WSN)是隨著無(wú)線通信技術(shù)、傳感器技術(shù)、移動(dòng)計(jì)算技術(shù)和嵌入式信息處理技術(shù)的發(fā)展而新興的研究課題，可以應(yīng)用到人類無(wú)法到達(dá)的地方，比如戰(zhàn)場(chǎng)、受污染區(qū)域等[1]。

覆蓋問(wèn)題和連通問(wèn)題是無(wú)線傳感器網(wǎng)絡(luò)中的基本問(wèn)題，是直接影響網(wǎng)絡(luò)性能和服務(wù)質(zhì)量的關(guān)鍵因素之一。無(wú)線傳感器網(wǎng)絡(luò)中的覆蓋問(wèn)題指被監(jiān)測(cè)區(qū)域內(nèi)的每一點(diǎn)至少在一個(gè)傳感器節(jié)點(diǎn)的傳感范圍內(nèi)；連通問(wèn)題指網(wǎng)絡(luò)內(nèi)沒(méi)有孤立節(jié)點(diǎn)存在，任意兩個(gè)節(jié)點(diǎn)都可以通信。無(wú)線傳感器網(wǎng)絡(luò)中的覆蓋問(wèn)題、連通問(wèn)題及節(jié)點(diǎn)布置問(wèn)題對(duì)提高WSN的魯棒性，容錯(cuò)性等性能以及降低成本和節(jié)省能量等方面有著直接的影響，因此對(duì)這些問(wèn)題的研究已經(jīng)成為目前的一個(gè)研究熱點(diǎn)[2-3]。

近年來(lái)，許多學(xué)者都對(duì)WSN的覆蓋問(wèn)題進(jìn)行了研究，并取得了一定的成果[4]。許多研究[5-9]都在完全覆蓋或k覆蓋方面做了很多工作，因此研究“通過(guò)使用盡可能少的工作節(jié)點(diǎn)來(lái)達(dá)到所期望的任意覆蓋率”的方案是很有意義的[10]。

1 隨機(jī)調(diào)度覆蓋算法

1.1 傳感器節(jié)點(diǎn)部署模型

本文考慮如下性質(zhì)的傳感器網(wǎng)絡(luò)[11]：

（1）需要檢測(cè)的目標(biāo)區(qū)域相對(duì)傳感器感知范圍足夠大，可以忽略邊界因素對(duì)目標(biāo)覆蓋帶來(lái)的影響。

（2）傳感器節(jié)點(diǎn)采用隨機(jī)部署，部署后不再移動(dòng)。

（3）傳感器感知采用0-1感知模型，即每個(gè)節(jié)點(diǎn)具有相同的感知半徑，在感知半徑內(nèi)的事件可被傳感器節(jié)點(diǎn)偵測(cè)。

（4）傳感器節(jié)點(diǎn)間需要用某種機(jī)制或者算法完成有一定精度的時(shí)鐘同步，保證節(jié)點(diǎn)之間時(shí)鐘誤差在一定范圍內(nèi)。

1.2 問(wèn)題描述及分析

為了滿足實(shí)際應(yīng)用需求，在部署無(wú)線傳感器網(wǎng)絡(luò)時(shí)，往往會(huì)存在許多冗余節(jié)點(diǎn)。如果所有節(jié)點(diǎn)始終處于活動(dòng)狀態(tài)，會(huì)產(chǎn)生許多冗余數(shù)據(jù)，從而造成能量浪費(fèi)。利用傳感器節(jié)點(diǎn)的高冗余特性，通過(guò)調(diào)度傳感器節(jié)點(diǎn)的工作狀態(tài)，關(guān)閉眾多的冗余節(jié)點(diǎn)，可有效減少節(jié)點(diǎn)的能耗，由此可見，研究節(jié)點(diǎn)調(diào)度方式延長(zhǎng)網(wǎng)絡(luò)的生存時(shí)間完全有必要并且是可行的。

覆蓋調(diào)度算法的基本思想是將全部隨機(jī)部署的傳感器節(jié)點(diǎn)組織成為若干個(gè)節(jié)點(diǎn)的集合，并且每個(gè)節(jié)點(diǎn)集合都能夠完全覆蓋被監(jiān)測(cè)的目標(biāo)，這些節(jié)點(diǎn)集以時(shí)間槽的方式輪流交替工作。并且在每個(gè)時(shí)間槽內(nèi)只有一個(gè)節(jié)點(diǎn)集合處于工作模式，不屬于此集合的其它傳感器節(jié)點(diǎn)都處于低功耗的休眠模式。通過(guò)采用這樣的方式調(diào)度每個(gè)傳感器節(jié)點(diǎn)，可以延長(zhǎng)整個(gè)網(wǎng)絡(luò)的生存時(shí)間。

隨機(jī)調(diào)度覆蓋算法是一種基于分組的節(jié)點(diǎn)調(diào)度覆蓋算法，它的基本思想是：每個(gè)傳感器節(jié)點(diǎn)隨機(jī)賦予1到K的某個(gè)值i(K，i∈N*),并將自身分配到第i組。在執(zhí)行完算法之后，依次調(diào)度每一組的傳感器節(jié)點(diǎn)對(duì)目標(biāo)區(qū)域進(jìn)行監(jiān)測(cè)[12]。由于位置非常臨近的傳感器節(jié)點(diǎn)可能分配到同一組或者是少數(shù)幾組，導(dǎo)致目標(biāo)區(qū)域內(nèi)節(jié)點(diǎn)分布不均勻，目標(biāo)區(qū)域中某些小區(qū)域節(jié)點(diǎn)分布過(guò)于密集，增加了該區(qū)域的通信沖突和數(shù)據(jù)冗余。而有些小區(qū)域節(jié)點(diǎn)分布過(guò)于稀疏，導(dǎo)致傳感器節(jié)點(diǎn)不能對(duì)目標(biāo)區(qū)域進(jìn)行有效監(jiān)控，并且降低了網(wǎng)絡(luò)的連通性。

基于隨機(jī)選取節(jié)點(diǎn)實(shí)現(xiàn)無(wú)交集節(jié)點(diǎn)分組的調(diào)度覆蓋算法雖然執(zhí)行簡(jiǎn)單，運(yùn)行時(shí)間較快，但它獲得的分組數(shù)較少且節(jié)點(diǎn)的通信半徑必須是傳感半徑的2倍。研究一種改進(jìn)的基于無(wú)交集節(jié)點(diǎn)分組的節(jié)點(diǎn)調(diào)度覆蓋算法，確保傳感器網(wǎng)絡(luò)獲得的分組較多，且保證網(wǎng)絡(luò)的連通性。

2 一種基于無(wú)交集的節(jié)點(diǎn)分組算法

2.1 問(wèn)題分析

給定一個(gè)特定目標(biāo)區(qū)域，在目標(biāo)區(qū)域上采用冗余布置節(jié)點(diǎn)辦法，大量的傳感器節(jié)點(diǎn)隨機(jī)散布目標(biāo)區(qū)域。當(dāng)傳感器節(jié)點(diǎn)布置完畢后，形成區(qū)域A，它由眾多不同覆蓋度的小區(qū)域組成。區(qū)域劃分結(jié)束之后，假定Acri區(qū)域：在所有組成區(qū)域A的小區(qū)域中覆蓋度最低的區(qū)域，稱之為關(guān)鍵區(qū)域。

假設(shè)：Acri為{S1,S2,S3,S4},其覆蓋度為4。每一次選出一個(gè)子集Ci,覆蓋區(qū)域Acri的節(jié)點(diǎn)至少有一個(gè)被選入，因此所能獲得的最大子集數(shù)為4。在考慮Acri時(shí)，選擇了S1加入Ci，當(dāng)遍歷到下面某個(gè)區(qū)域Ai={S2,S3,S6,S7},如果選擇S2或S3，作為覆蓋區(qū)域Ai的節(jié)點(diǎn)加入Ci，則進(jìn)入Ci+1子集時(shí)，以前的Acri覆蓋度至少減少2，減少了能分得的子集數(shù)。

任意給定無(wú)線傳感器網(wǎng)絡(luò)的兩個(gè)節(jié)點(diǎn)Si和Sj，Si的位置為（xi,yi），Sj的位置為（xj,yj）。若兩個(gè)傳感器節(jié)點(diǎn)之間的距離小于或等于通信半徑Rc，即:

則稱Si和Sj互為傳感鄰居，即節(jié)點(diǎn)Si和節(jié)點(diǎn)Sj之間是連通的。

2.2 算法流程圖

流程圖如圖1所示。

圖1 算法流程圖

其中A為目標(biāo)區(qū)域，C為所有的傳感器節(jié)點(diǎn)集合；U為沒(méi)有被傳感器節(jié)點(diǎn)覆蓋到的區(qū)域；V為可用節(jié)點(diǎn)集合。

該算法試圖選擇這樣的傳感器節(jié)點(diǎn)，能盡可能多地覆蓋還沒(méi)有被已選擇的節(jié)點(diǎn)覆蓋的區(qū)域，盡可能地沒(méi)有覆蓋已經(jīng)被其他節(jié)點(diǎn)覆蓋的區(qū)域。算法期望得到的每個(gè)節(jié)點(diǎn)分組都能對(duì)目標(biāo)區(qū)域?qū)崿F(xiàn)全覆蓋，并且通過(guò)考慮節(jié)點(diǎn)之間的距離來(lái)使整個(gè)網(wǎng)絡(luò)連通。

3 仿真結(jié)果與分析

3.1 工作節(jié)點(diǎn)分布

我們用MATLAB隨機(jī)生成一個(gè)節(jié)點(diǎn)分布區(qū)域,在500m×500m的范圍內(nèi)隨機(jī)安放節(jié)點(diǎn)，如圖2所示。

圖2 節(jié)點(diǎn)分布圖

為了對(duì)比隨機(jī)選取節(jié)點(diǎn)實(shí)現(xiàn)無(wú)交集節(jié)點(diǎn)分組方式和本文改進(jìn)的節(jié)點(diǎn)調(diào)度覆蓋算法的性能表現(xiàn)，本文考慮了在節(jié)點(diǎn)傳感半徑和目標(biāo)區(qū)域劃分為小區(qū)域的數(shù)目一定的情況下，所獲得連通覆蓋集數(shù)與節(jié)點(diǎn)數(shù)目之間的關(guān)系。

3.2 實(shí)驗(yàn)結(jié)果

首先設(shè)定傳感半徑為Rs=50m，下面來(lái)對(duì)比隨機(jī)選取節(jié)點(diǎn)實(shí)現(xiàn)無(wú)交集節(jié)點(diǎn)分組方式和本文改進(jìn)的無(wú)交集節(jié)點(diǎn)分組算法分別在節(jié)點(diǎn)通信半徑Rc=100m、Rc=80m所獲得的連通覆蓋集數(shù)，仿真結(jié)果如圖3與圖4所示。

圖3 Rc=100m時(shí)獲得的連通覆蓋集數(shù)

圖4 Rc=80m時(shí)獲得的連通覆蓋集數(shù)

從圖3, 4中可以看出，改進(jìn)的無(wú)交集節(jié)點(diǎn)分組算法比隨機(jī)選取節(jié)點(diǎn)的無(wú)交集節(jié)點(diǎn)分組能獲得更多的連通覆蓋集，即能延長(zhǎng)網(wǎng)絡(luò)的壽命。且改進(jìn)的無(wú)交集節(jié)點(diǎn)分組算法因?yàn)榭紤]了網(wǎng)絡(luò)的連通性，所以隨著通信半徑的變化，獲得的連通覆蓋集個(gè)數(shù)變化很小。而隨機(jī)選取節(jié)點(diǎn)的無(wú)交集節(jié)點(diǎn)分組算法因?yàn)橐笸ㄐ虐霃绞莻鞲邪霃降?倍，所以獲得的連通覆蓋集個(gè)數(shù)會(huì)明顯減少。

由于該算法的退出條件是不能找到一個(gè)節(jié)點(diǎn)集合能覆蓋整個(gè)給定目標(biāo)區(qū)域且保證整個(gè)網(wǎng)絡(luò)連通，算法中止。在傳感器網(wǎng)絡(luò)中，會(huì)存在空閑節(jié)點(diǎn)?？臻e節(jié)點(diǎn)的數(shù)量可以反映出對(duì)傳感器節(jié)點(diǎn)的利用程度。

為了更形象的表示，我們對(duì)節(jié)點(diǎn)數(shù)和節(jié)點(diǎn)利用率進(jìn)行了仿真，結(jié)果如圖5所示。

圖5 節(jié)點(diǎn)利用率比較

4 結(jié)論

綜上所述，本文研究的算法比隨機(jī)選取節(jié)點(diǎn)實(shí)現(xiàn)無(wú)交集節(jié)點(diǎn)分組算法能獲得更多的分組且保證網(wǎng)絡(luò)連通。

[1] Wall J, Platt G, James G. Wireless sensor networks as agents for intelligent control of distributed energy resourcees[C]. In: Wireless Pervasive Computing, Sydney, Australia, 2007.

[2] 李德識(shí),李薇.無(wú)線傳感器網(wǎng)絡(luò)中覆蓋問(wèn)題的研究[J].微電子學(xué)與計(jì)算機(jī),2005,22(8):150-152.

[3] 王燕莉，安世全.無(wú)線傳感器網(wǎng)絡(luò)的覆蓋問(wèn)題研究[J].傳感技術(shù)學(xué)報(bào)，2005，18(2):307-312.

[4] ZHANG H,HOU J C.Maintaining sensing coverage and connectivity in large sensor networks[J].Ad Hoc & Sensor Networks,2005,1(1-2):89-124.

[5] CARLE J,SMPLOT-PYL D.Energy-efficient area monitoring for sensornetworks[J]. Computer,2004,37(2):40-46.

[6] GUPTA H,ZHOU Z,DAS S R,et al Connected sensor cover.self-organization of sensor networks for efficient query execution[J].IEEE/ACM Transactions on Networking,2006,14(1):55-67.

[7] M E G U E R D I C H I A N S,K O U S H A N F A R F,POTKONJAK M,et al Coverage Problems in Wireless Ad-hoc Sensor Networks[C]//Twentieth Annual Joint Conference of the IEEE Computer and Communications Societies Anchorage:[sn],2001:1380-1387.

[8] SHAKKOTTAI S,SRIKANT R,SHROFF N.Unreliable Sensor Grids:Coverage,Connectivity and Diameter[C]. Proc IEEE NFOCOM 2003.SanFrancisco:[sn],2003.

[9] ZHOU Z,DAS S,GUPTA H.Connected K-coverage Problem in Sensor Networks[C]//13th Intemational Conference on Computer Communications and Networks Chicagv:[sn],2004:373-378.

[10] LIU Y,LIANGW.Approximate Coverage in Wireless Sensor Networks[C].Proceedings of IEEE Conference on Local Computer Networks 30th Anniversary(LCN’05). Sydney:[sn],2005.

[11] 蔣 杰, 方 力, 張鶴穎. 無(wú)線傳感器網(wǎng)絡(luò)最小連通覆蓋集問(wèn)題求解算法[J].軟件學(xué)報(bào),2006,17(2): 175-184.

[12] Liu C, Wu K, King V. Randomized coverage-preserving scheduling schemes for wireless sensor networks[C]. In: Proc. of Fourth IFIP International Conference on Networking. HCMC, Viet Nam, 2005, 956-967.