基于網(wǎng)格掃描的實(shí)現(xiàn)目標(biāo)點(diǎn)覆蓋的確定性傳感器節(jié)點(diǎn)部署方法*

郭秀明，趙春江 ，楊信廷，孫傳恒，李 明，李文勇，周 超

(1．中國(guó)農(nóng)業(yè)大學(xué)信息與電氣工程學(xué)院，北京100083;2．國(guó)家農(nóng)業(yè)信息化工程技術(shù)研究中心，北京100097;3．農(nóng)業(yè)部農(nóng)業(yè)信息技術(shù)重點(diǎn)開(kāi)放實(shí)驗(yàn)室，北京100097)

無(wú)線傳感器網(wǎng)絡(luò)(Wireless Sensor Networks，WSNs)是由部署在觀測(cè)環(huán)境附近的大量微型低功耗的傳感器節(jié)點(diǎn)組成的多跳網(wǎng)絡(luò)系統(tǒng)，目的是實(shí)時(shí)檢測(cè)、感知和采集各種對(duì)象的信息。這些信息通過(guò)無(wú)線方式發(fā)送，并以自組織的網(wǎng)絡(luò)方式傳送到用戶終端，從而實(shí)現(xiàn)物理世界、計(jì)算世界以及人類(lèi)社會(huì)的三元世界的聯(lián)通。WSN在軍事國(guó)防、環(huán)境監(jiān)測(cè)、生物醫(yī)療、智能家居、危險(xiǎn)區(qū)域的遠(yuǎn)程監(jiān)控等領(lǐng)域得到了廣泛的應(yīng)用，引起了學(xué)術(shù)界和工業(yè)界的高度重視［1－2］。

在構(gòu)建無(wú)線傳感器網(wǎng)絡(luò)過(guò)程中，網(wǎng)絡(luò)覆蓋是最基本的問(wèn)題之一［3］。根據(jù)覆蓋對(duì)象，覆蓋可分為區(qū)域性全覆蓋［4］、關(guān)鍵點(diǎn)覆蓋［5］、邊界覆蓋［6］、柵欄覆蓋［7］等，根據(jù)部署方式可分為隨機(jī)部署和確定性部署［8］。在人類(lèi)很難到達(dá)的地區(qū)，如戰(zhàn)場(chǎng)、森林等，多使用隨機(jī)部署方式;飛機(jī)拋灑大量節(jié)點(diǎn)到目標(biāo)區(qū)域，節(jié)點(diǎn)自動(dòng)組網(wǎng)［9］。在人類(lèi)容易到達(dá)的地方如農(nóng)田等，手工確定性部署節(jié)點(diǎn)能減少傳感器節(jié)點(diǎn)數(shù)目，降低成本［5］。

近年來(lái)，眾多學(xué)者對(duì)WSN的覆蓋問(wèn)題進(jìn)行了研究，取得了一定成果［10］。林祝亮等［11］在粒子進(jìn)化的多粒子群算法的基礎(chǔ)上，提出了一種無(wú)線傳感器網(wǎng)絡(luò)覆蓋的優(yōu)化策略，擴(kuò)大了網(wǎng)絡(luò)覆蓋范圍，延長(zhǎng)了網(wǎng)絡(luò)壽命。李明等［12］針對(duì)異構(gòu)傳感器網(wǎng)絡(luò)節(jié)點(diǎn)的高密度部署和監(jiān)測(cè)目標(biāo)非均勻分布的情況，提出了一種基于模擬退火算法的成本最優(yōu)化部署方法。Yan Ruoyu等［13］通過(guò)網(wǎng)格掃描的再部署方法使用較少的傳感器節(jié)點(diǎn)實(shí)現(xiàn)了較大的區(qū)域覆蓋率。目前的覆蓋技術(shù)研究多數(shù)集中在區(qū)域覆蓋的隨機(jī)部署［14－15］、確定性部署［16］以及目標(biāo)覆蓋的隨機(jī)部署等方面［17］;而針對(duì)目標(biāo)覆蓋的確定性部署問(wèn)題卻很少涉及。

目標(biāo)覆蓋的確定性部署，主要針對(duì)位置已知的離散目標(biāo)點(diǎn)，尋找最少的傳感器節(jié)點(diǎn)數(shù)及最佳的節(jié)點(diǎn)部署位置。當(dāng)目標(biāo)點(diǎn)分散或者對(duì)目標(biāo)點(diǎn)的覆蓋水平要求很高時(shí)，須在每個(gè)目標(biāo)點(diǎn)處都放置一個(gè)感知節(jié)點(diǎn)，如監(jiān)測(cè)目標(biāo)點(diǎn)的溫濕度［18］。但當(dāng)目標(biāo)點(diǎn)密度較大且對(duì)目標(biāo)點(diǎn)覆蓋水平要求不是很高時(shí)，一個(gè)節(jié)點(diǎn)可以同時(shí)覆蓋多個(gè)目標(biāo)點(diǎn)。何欣等［5］利用目標(biāo)點(diǎn)的最多層交疊域和遺傳算法，提出了一個(gè)面向目標(biāo)覆蓋的最優(yōu)確定性部署方法;該方法極大的降低了網(wǎng)絡(luò)的部署成本，實(shí)現(xiàn)了目標(biāo)覆蓋的確定性部署;但該方法也存在一些不足之處，最多層交疊域的計(jì)算復(fù)雜，而且遺傳算法可能存在早熟問(wèn)題。

本文提出了一種簡(jiǎn)單有效的基于網(wǎng)格掃描的目標(biāo)點(diǎn)覆蓋的確定性部署方法，首先把目標(biāo)點(diǎn)所在區(qū)域劃分為若干正方形網(wǎng)格，然后從中選擇最合適的網(wǎng)格作為下一個(gè)節(jié)點(diǎn)的放置位置，直到覆蓋所有目標(biāo)點(diǎn);同時(shí)為了評(píng)價(jià)覆蓋水平，本文引入了概率感知模型，更準(zhǔn)確的表示節(jié)點(diǎn)對(duì)目標(biāo)點(diǎn)的感知水平。文章第二部分詳細(xì)介紹了基于網(wǎng)格掃描的目標(biāo)點(diǎn)覆蓋的確定性部署方法;在第三部分，針對(duì)網(wǎng)格邊長(zhǎng)和概率感知模型的感知概率下限分別選取不同數(shù)值進(jìn)行仿真實(shí)驗(yàn)，驗(yàn)證本文算法的有效性;最后是論文的總結(jié)和結(jié)論。

1 基于網(wǎng)格掃描的目標(biāo)點(diǎn)覆蓋的節(jié)點(diǎn)

如何使用最少的節(jié)點(diǎn)實(shí)現(xiàn)對(duì)已知目標(biāo)點(diǎn)的覆蓋并達(dá)到預(yù)設(shè)的覆蓋水平是本文要解決的問(wèn)題。為了更準(zhǔn)確評(píng)價(jià)覆蓋水平，本文引入了概率感知模型，把節(jié)點(diǎn)能感知到目標(biāo)點(diǎn)的最小感知概率作為覆蓋水平的評(píng)價(jià)指標(biāo);為了方便確定節(jié)點(diǎn)的位置，算法把目標(biāo)點(diǎn)所在區(qū)域劃分為若干正方形網(wǎng)格;算法通過(guò)網(wǎng)格掃描，不斷從中選擇最合適的網(wǎng)格作為下一個(gè)節(jié)點(diǎn)的放置位置，實(shí)現(xiàn)目標(biāo)點(diǎn)的覆蓋。

1．1 概率感知模型

在二值感知模型中，當(dāng)節(jié)點(diǎn)距離目標(biāo)點(diǎn)的距離小于或等于感知半徑rs時(shí)，認(rèn)為能感知覆蓋目標(biāo)點(diǎn);否則，不能感知覆蓋目標(biāo)點(diǎn)。由于受到距離、障礙物等各種情況的影響，實(shí)際情況與二值感知模型并不一致。本文采用與實(shí)際情況較一致的概率感知模型［19］，把信號(hào)強(qiáng)弱轉(zhuǎn)化為感知概率。目標(biāo)點(diǎn)gi被節(jié)點(diǎn)sk感知到的概率為p如式(1)所示:

參數(shù)α代表感知節(jié)點(diǎn)的物理特性，dki為感知節(jié)點(diǎn)和目標(biāo)點(diǎn)之間的距離。由式(1)可知，目標(biāo)點(diǎn)與感知節(jié)點(diǎn)之間的距離dki小于或等于rs時(shí)，節(jié)點(diǎn)對(duì)目標(biāo)點(diǎn)的感知概率為 e－αdki，目標(biāo)點(diǎn)距離節(jié)點(diǎn)越近，被感知的概率越大。當(dāng)距離大于感知半徑rs時(shí)，目標(biāo)節(jié)點(diǎn)不能被感知到。

本文假定當(dāng)節(jié)點(diǎn)與目標(biāo)點(diǎn)的距離小于或等于rs且感知概率不小于預(yù)定值β時(shí)，節(jié)點(diǎn)能感知到目標(biāo)點(diǎn)，否則不能感知到，如式(2)所示，Ski為1表示節(jié)點(diǎn)能感知到目標(biāo)點(diǎn)，否則不能。β取值越大，覆蓋水平越好;反之則越較差。

1．2 網(wǎng)格劃分

網(wǎng)格劃分是無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)部署中常用的一種方法，它把感興趣區(qū)域劃分為若干網(wǎng)格。網(wǎng)格可以有多種形狀，如正方形、六邊形、三角形等。目前網(wǎng)格劃分多應(yīng)用于區(qū)域覆蓋的節(jié)點(diǎn)部署方法［20］中，把目標(biāo)區(qū)域劃分為若干邊長(zhǎng)相同的網(wǎng)格，網(wǎng)格頂點(diǎn)放置感知節(jié)點(diǎn)來(lái)監(jiān)測(cè)感興趣區(qū)域。相同形狀的網(wǎng)格，網(wǎng)格邊長(zhǎng)越大，使用的節(jié)點(diǎn)越少。但為了滿足節(jié)點(diǎn)間的覆蓋連通的要求，網(wǎng)格邊長(zhǎng)不能過(guò)大。

受區(qū)域覆蓋中網(wǎng)格劃分的啟發(fā)，本文把網(wǎng)格劃分引入到目標(biāo)點(diǎn)覆蓋的算法中。為了方便確定節(jié)點(diǎn)的位置，算法把目標(biāo)點(diǎn)所在區(qū)域劃分為若干正方形網(wǎng)格，整個(gè)監(jiān)測(cè)區(qū)域離散化為若干網(wǎng)格的集合。劃分網(wǎng)格的目的和在區(qū)域覆蓋中不同，算法把每個(gè)網(wǎng)格抽象為一個(gè)位置點(diǎn)。當(dāng)網(wǎng)格邊長(zhǎng)較小時(shí)，不同形狀的網(wǎng)格對(duì)結(jié)果影響較小;本文算法為中心式確定性部署，網(wǎng)格邊長(zhǎng)可以取值很小。

本文假定目標(biāo)區(qū)域?yàn)殚L(zhǎng)方形，用等距的分別與長(zhǎng)和寬平行的直線將長(zhǎng)方形區(qū)域劃分為若干正方形網(wǎng)格。算法通過(guò)網(wǎng)格掃描，不斷從中選擇最合適的網(wǎng)格作為下一個(gè)節(jié)點(diǎn)的放置位置。

1．3 節(jié)點(diǎn)部署算法

在一個(gè)已知若干目標(biāo)點(diǎn)的區(qū)域中，在每個(gè)目標(biāo)點(diǎn)處放置一個(gè)感知節(jié)點(diǎn)能達(dá)到最好的覆蓋水平。但如果目標(biāo)點(diǎn)密度較大且對(duì)目標(biāo)點(diǎn)的覆蓋水平要求不高時(shí)，每個(gè)目標(biāo)點(diǎn)處都放置一個(gè)節(jié)點(diǎn)是沒(méi)有必要的。針對(duì)這種情況，結(jié)合網(wǎng)格劃分的方法，本文提出了一種覆蓋算法，實(shí)現(xiàn)用最少的節(jié)點(diǎn)覆蓋所有目標(biāo)點(diǎn)并達(dá)到預(yù)設(shè)的覆蓋水平，降低了成本。

節(jié)點(diǎn)對(duì)目標(biāo)點(diǎn)的覆蓋水平可由概率感知模型中的感知概率下限β約束，β取值越大則覆蓋水平越好，反之則越差。

初始時(shí)，待覆蓋目標(biāo)點(diǎn)集t為所有目標(biāo)點(diǎn)的集合。逐行掃描所有的網(wǎng)格，選擇節(jié)點(diǎn)感知到目標(biāo)點(diǎn)的個(gè)數(shù)最多的網(wǎng)格放置下一個(gè)節(jié)點(diǎn)，如式(3)所示，網(wǎng)格u作為下一個(gè)節(jié)點(diǎn)的放置位置。當(dāng)放置了一個(gè)新的節(jié)點(diǎn)后，將能被它感知到的目標(biāo)點(diǎn)從待覆蓋的目標(biāo)點(diǎn)集中移出，以防止重復(fù)覆蓋。繼續(xù)逐行掃描所有網(wǎng)格，以同樣的方法選擇下一個(gè)放置感知節(jié)點(diǎn)的網(wǎng)格，并從待覆蓋目標(biāo)點(diǎn)集合中移除新加節(jié)點(diǎn)感知到的目標(biāo)點(diǎn)直到待覆蓋目標(biāo)點(diǎn)集合為空。

在掃描網(wǎng)格選擇下一個(gè)放置節(jié)點(diǎn)的網(wǎng)格時(shí)，可能存在一個(gè)以上的網(wǎng)格，在這些網(wǎng)格處節(jié)點(diǎn)能感知到同樣最大數(shù)量的目標(biāo)點(diǎn)。此時(shí)應(yīng)選擇覆蓋性較好的網(wǎng)格，在被每個(gè)網(wǎng)格處的節(jié)點(diǎn)感知的目標(biāo)點(diǎn)中，被感知概率值最小的目標(biāo)點(diǎn)決定著整體覆蓋水平，如式(4)所示，ei決定著節(jié)點(diǎn)i的總體覆蓋水平。算法選擇目標(biāo)點(diǎn)被感知概率最小值最大的網(wǎng)格，即網(wǎng)格q放置下一個(gè)節(jié)點(diǎn)，見(jiàn)式(5)。

算法描述如下:

①初始化:t:目標(biāo)點(diǎn)集合，初始化為所有目標(biāo)點(diǎn);l:目標(biāo)點(diǎn)被覆蓋標(biāo)記，初始化為0;d:網(wǎng)格的邊長(zhǎng);a:整個(gè)區(qū)域長(zhǎng)方形的長(zhǎng)度;b:長(zhǎng)方形區(qū)域的寬度;β:預(yù)設(shè)的感知概率下限值;grid(x，y):記錄當(dāng)前節(jié)點(diǎn)能以不小于β感知到最多的未被覆蓋的目標(biāo)點(diǎn)的網(wǎng)格;c:記錄grid(x，y)以不小于概率β感知到的目標(biāo)點(diǎn)的個(gè)數(shù);p:記錄grid(x，y)能以不小于概率β感知到的目標(biāo)點(diǎn)中的感知概率的最小值;x:網(wǎng)格grid(x，y)所在的行號(hào);y:網(wǎng)格grid(x，y)所在的列號(hào);i:當(dāng)前網(wǎng)格的行號(hào)，初始化為1;j:當(dāng)前網(wǎng)格的列號(hào)，初始化為1。

②c1:grid(i，j)以不小于概率β感知到的目標(biāo)點(diǎn)的個(gè)數(shù);p1:grid(i，j)以不小于β感知到的目標(biāo)點(diǎn)的感知概率的最小值;

③如果c1＞c或者(c1=c且p1＞p)繼續(xù);否則轉(zhuǎn)⑤;

④c=c1;;p=p1;x=i;y=j

⑤j=j+1;如果 j＞b/d，繼續(xù);否則轉(zhuǎn)②;

⑥i=i+1;j=1;如果 i＞a/d，繼續(xù);否則，轉(zhuǎn)②;

⑦輸出網(wǎng)格所在的行號(hào)、列號(hào)(x，y)以及部署在該網(wǎng)格的節(jié)點(diǎn)能以不小于β感知到的目標(biāo)點(diǎn)集合t1;t=t－t1;如果t為空，結(jié)束;否則轉(zhuǎn)②。

其中，第二步計(jì)算當(dāng)前網(wǎng)格處節(jié)點(diǎn)以不小于概率β感知到的待覆蓋目標(biāo)點(diǎn)的個(gè)數(shù)c1及其中感知概率的最小值p1。根據(jù)節(jié)點(diǎn)到各目標(biāo)點(diǎn)的歐式距離，由式(1)可計(jì)算出節(jié)點(diǎn)對(duì)各目標(biāo)點(diǎn)的感知概率。與已掃描的以不小于概率β感知到的待覆蓋目標(biāo)點(diǎn)的個(gè)數(shù)的最大值c比較，若c1＞c，說(shuō)明當(dāng)前網(wǎng)格更適合選為下一個(gè)放置節(jié)點(diǎn)的位置，把當(dāng)前網(wǎng)格記錄為最優(yōu)網(wǎng)格，如第四步所示。如果c1=c，即當(dāng)前網(wǎng)格與已掃描的最優(yōu)網(wǎng)格能以不小于概率β感知到同樣數(shù)目的最多的待覆蓋目標(biāo)點(diǎn)，如果p1大于當(dāng)前以不小于概率β感知到的目標(biāo)點(diǎn)中的感知概率的最小值p，則當(dāng)前網(wǎng)格比當(dāng)前最優(yōu)網(wǎng)格更適合作為下一個(gè)節(jié)點(diǎn)的放置位置。逐行掃描所有網(wǎng)格，選出最優(yōu)的網(wǎng)格放置新節(jié)點(diǎn)。把節(jié)點(diǎn)以不小于概率β感知到的待覆蓋目標(biāo)點(diǎn)從待覆蓋目標(biāo)點(diǎn)集中移出。重復(fù)執(zhí)行，直到待覆蓋目標(biāo)點(diǎn)集合為空。

2 實(shí)驗(yàn)結(jié)果及分析

為了驗(yàn)證算法的有效性，設(shè)計(jì)了兩組仿真實(shí)驗(yàn)分別測(cè)試網(wǎng)格邊長(zhǎng)和感知概率下限β對(duì)節(jié)點(diǎn)部署的影響。本文假定實(shí)驗(yàn)均在100 m×100 m的區(qū)域內(nèi)，采用隨機(jī)方式分別產(chǎn)生10、20個(gè)目標(biāo)點(diǎn)。同時(shí)，假定所有的傳感器節(jié)點(diǎn)具有同樣的感知半徑20 m，即式(1)中rs等于20 m，概率感知模型中的α取固定值0．04。考慮到實(shí)際情況，目標(biāo)點(diǎn)的位置坐標(biāo)精確到0．1 m。

2．1 實(shí)驗(yàn)一:不同網(wǎng)格邊長(zhǎng)

分別在網(wǎng)格邊長(zhǎng)為0．02 m、0．1 m、1 m 三種情況下進(jìn)行仿真實(shí)驗(yàn)，為了不引入其它影響因素，該仿真試驗(yàn)中的β值均取0。圖1、圖2分別為目標(biāo)點(diǎn)為10、20時(shí)的實(shí)驗(yàn)結(jié)果。

圖1、圖2中，藍(lán)色圓圈代表目標(biāo)點(diǎn)位置，綠色的點(diǎn)代表節(jié)點(diǎn)位置，綠色的圓代表節(jié)點(diǎn)的感知范圍，綠點(diǎn)后面的數(shù)字表示該節(jié)點(diǎn)放置的先后次序。由圖可知，網(wǎng)格邊長(zhǎng)grid_side取值越小，節(jié)點(diǎn)的放置位置越精確。圖1(c)中節(jié)點(diǎn)4明顯比圖1(a)中的節(jié)點(diǎn)4放置的位置更精確，圖2(c)中的節(jié)點(diǎn)7比圖2(a)中的節(jié)點(diǎn)6位置更精確。當(dāng)網(wǎng)格處的節(jié)點(diǎn)能覆蓋相同最大數(shù)目的目標(biāo)點(diǎn)時(shí)，如圖2(c)中的4以及4周?chē)娜舾删W(wǎng)格，放在它們處的節(jié)點(diǎn)均能感知到同樣的最多的兩個(gè)目標(biāo)點(diǎn)，但網(wǎng)格4處，最小感知概率值最大，具有最好的覆蓋性，所以網(wǎng)格4是放置下一個(gè)節(jié)點(diǎn)的最優(yōu)位置。

圖1 不同網(wǎng)格邊長(zhǎng)下傳感器節(jié)點(diǎn)的位置及覆蓋情況(目標(biāo)點(diǎn)個(gè)數(shù)為10)

圖2 不同網(wǎng)格邊長(zhǎng)下傳感器節(jié)點(diǎn)的位置及覆蓋情況(目標(biāo)點(diǎn)個(gè)數(shù)為20)

2．2 實(shí)驗(yàn)二:不同感知概率下限

該實(shí)驗(yàn)中，目標(biāo)點(diǎn)取實(shí)驗(yàn)一中的20個(gè)目標(biāo)點(diǎn)、網(wǎng)格邊長(zhǎng)均為0．1米。在這種情況下測(cè)試感知概率下限β 分別取 0．2、0．4、0．6、0．8 時(shí)，對(duì)節(jié)點(diǎn)數(shù)量及位置的影響。實(shí)驗(yàn)結(jié)果如圖3 所示。

圖3 β不同取值時(shí)節(jié)點(diǎn)個(gè)數(shù)及位置

由圖可知，當(dāng)β為0．2和0．4時(shí)，所需節(jié)點(diǎn)個(gè)數(shù)及節(jié)點(diǎn)位置均相同。這是因?yàn)橛墒?1)可計(jì)算出當(dāng)節(jié)點(diǎn)與目標(biāo)點(diǎn)距離為rs時(shí)，感知概率值為0．44，0．2和0．4 均小于0．44，β 取值0．2 和0．4 時(shí)，距離節(jié)點(diǎn)小于rs的目標(biāo)點(diǎn)能被感知到，所以結(jié)果相同。而當(dāng)β遞增至0．6和0．8時(shí)，感知概率下限的增加要求目標(biāo)點(diǎn)與節(jié)點(diǎn)有更小的距離才能被感知，一部分原來(lái)能被感知到的目標(biāo)點(diǎn)將不能被感知，所以需要部署更多的節(jié)點(diǎn)。如圖3(b)、3(c)所示。

目標(biāo)點(diǎn)個(gè)數(shù)固定為10和20時(shí)，本文分別隨機(jī)產(chǎn)生了10組目標(biāo)點(diǎn)集，計(jì)算不同的β值下所需的節(jié)點(diǎn)個(gè)數(shù)。圖4顯示了β取不同值時(shí)所需節(jié)點(diǎn)個(gè)數(shù)的平均值。由圖4可知，覆蓋相同的目標(biāo)點(diǎn)，β取值越大，需要的節(jié)點(diǎn)個(gè)數(shù)越多。β取1時(shí)，每個(gè)目標(biāo)點(diǎn)處須放置一個(gè)節(jié)點(diǎn)，達(dá)到最好的覆蓋水平。目標(biāo)點(diǎn)個(gè)數(shù)越多時(shí)，隨著β的增加需增加更多的節(jié)點(diǎn)。

圖4 不同β值下覆蓋相同的目標(biāo)點(diǎn)所需的節(jié)點(diǎn)個(gè)數(shù)

3 結(jié)論

本文提出了一種基于網(wǎng)格掃描的實(shí)現(xiàn)目標(biāo)點(diǎn)覆蓋的確定性節(jié)點(diǎn)部署方法。算法首先把目標(biāo)區(qū)域劃分為若干網(wǎng)格，掃描所有網(wǎng)格，從中選擇最佳的網(wǎng)格作為下一個(gè)傳感器節(jié)點(diǎn)的放置位置，直到所有的目標(biāo)點(diǎn)都被覆蓋。本文引入概率感知模型，把節(jié)點(diǎn)能感知到目標(biāo)點(diǎn)的最小感知概率值作為約束總體覆蓋水平的指標(biāo)。把節(jié)點(diǎn)能感知到目標(biāo)點(diǎn)的個(gè)數(shù)及對(duì)目標(biāo)點(diǎn)的最小感知概率值作為網(wǎng)格的評(píng)價(jià)標(biāo)準(zhǔn)。本文對(duì)網(wǎng)格邊長(zhǎng)和感知概率下限取不同數(shù)值時(shí)，分別進(jìn)行仿真實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果表明，網(wǎng)格邊長(zhǎng)越小，節(jié)點(diǎn)放置位置越精確;當(dāng)網(wǎng)格邊長(zhǎng)不變時(shí)，感知概率下限取值越大，所需的節(jié)點(diǎn)越多，覆蓋性能越好。給定感知概率下限，算法能使用最少的節(jié)點(diǎn)實(shí)現(xiàn)目標(biāo)覆蓋，達(dá)到較好的總體覆蓋水平且能計(jì)算出較優(yōu)的節(jié)點(diǎn)部署位置。

本文提出的算法也存在一些不足之處，本文只考慮了對(duì)目標(biāo)點(diǎn)的覆蓋問(wèn)題，節(jié)點(diǎn)間的連通問(wèn)題是下一步需要解決的問(wèn)題。此外，每個(gè)節(jié)點(diǎn)覆蓋目標(biāo)點(diǎn)的個(gè)數(shù)不均勻，在不增加算法所需的最少節(jié)點(diǎn)個(gè)數(shù)的前提下，調(diào)整節(jié)點(diǎn)的位置達(dá)到較好的均勻性可以延長(zhǎng)網(wǎng)絡(luò)生命周期。

［1］ 任豐原，黃海寧，林闖．無(wú)線傳感器網(wǎng)絡(luò)［J］．軟件學(xué)報(bào)，2003，14(7):1282－1291．

［2］ Jennifer Yick，Biswanath Mukherjee，Dipak Ghosal．Wireless Sensor Network Survey［J］．IEEE Computer Networks，2008，52(12):2292－2330．

［3］ 傅質(zhì)馨，徐志良，黃成．無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)部署問(wèn)題研究［J］．傳感器與微系統(tǒng)，2008，14(7):1282－1291．

［4］ Dhillon S S，Chakrabarty K．Sensor Placement for Effective Coverage and Surveillance in Distributed Sensor Networks［C］//IEEE Wireless Communications and Networking Conference(WCNC－03)，2003:1609－1614．

［5］ 何欣，桂小林，安健．面向目標(biāo)覆蓋的無(wú)線傳感器網(wǎng)絡(luò)確定性部署方法［J］．西安交通大學(xué)學(xué)報(bào)，2010，44(6):6－10．

［6］ Ka-Shun Hung，King-Shan Lui．On Perimeter Coverage in Wireless Sensor Networks［J］．IEEE Transactions on Wireless Communications，2010，9(7):2156－2164．

［7］ 秦寧寧，蓋祎，張林，等．Voronoi圖在無(wú)線傳感器網(wǎng)絡(luò)柵欄覆蓋中的應(yīng)用研究［J］．計(jì)算機(jī)應(yīng)用研究，2008，25(3):863－865．

［8］ 劉麗萍，王智，孫優(yōu)賢．無(wú)線傳感器網(wǎng)絡(luò)部署及其覆蓋問(wèn)題研究［J］．電子與信息學(xué)報(bào)，2006，28(9):1752－1757．

［9］ Yi Zou，Krishnendu Chakrabarty．A Distributed Coverage and Connectivity Centric Technique for Selecting Active Nodes in Wireless Sensor Networks［J］．IEEE Transactions on Computers，2005，54(8):978－991．

［10］ Zhang H，Hou J C．Maintaining Sensing Coverage and Connectivity in Large Sensor Networks［J］．AdHoc＆Sensor Networks，2005，1(1－2):89－124．

［11］林祝亮，馮遠(yuǎn)靜，俞立．無(wú)線傳感器網(wǎng)絡(luò)覆蓋的粒子進(jìn)化優(yōu)化策略研究［J］．傳感技術(shù)學(xué)報(bào)，2009，22(6):873－877．

［12］李明，石為人．異構(gòu)無(wú)線傳感器網(wǎng)絡(luò)中基于模擬退火算法的成本最優(yōu)部署機(jī)制［J］．傳感技術(shù)學(xué)報(bào)，2010，23(6):855－858．

［13］ Yan Ruoyu，Zheng Qinhua．Using Renyi Cross Entropy to Analyze Traffic Matrix and DetectDdoS Attacks［J］．Information Technology Journal，2009，8(8):1180－1188．

［14］ Anukool L，Mark C，Christophe D．Mining Anomalies Using Traffic Feature Distributions［C］//Proceedings of Special Interest Group on Data Communication Conference，USA:ACM，2005:217－228．

［15］ George N，Vyas S，David G．An Empirical Evaluation of Entropy-Based Traffic Anomaly Detection［C］//Proceedings of Internet Measurement Conference，USA:ACM，2008:151－156．

［16］ Qin Tao，Guan Xiaohong，Li Wei．Dynamic Features Measurement and Analysis for Large-scale Networks［C］//Proceedings of International Conference on Communications，USA:IEEE，2008:212－216．

［17］ Xingfa Shen，Jiming Chen，Youxian Sun．Grid Scan:A Simple and Effective Approach for Coverage Issue in Wireless Sensor Networks［C］//IEEE International conference on Communications，2006:3480－3484．

［18］ Xiaoyu Chu，Harish Sethu．A New Distributed Algorithm for Even Coverage and Improved Lifetime in a Sensor Network［C］//IEEE INFCOM，2009:361－369．

［19］ Hekmat R，van Mieghem P．Connectivity in Wireless Ad-Hoc Networks with a Log-Normal Radio Model［J］．Mobile Networks and Applications，2006，11(3):351－360．

［20］ Xueqing Wang，Shuxue Zhang．Comparison of Several Sensor Deployments in Wireless Sensor Networks［C］//International Conference on E-Health Networking Digital Ecosystems and Technologies，2010:236－239．