凡高娟，孫力娟，王汝傳,2，黃海平

(1.南京郵電大學(xué) 計(jì)算機(jī)學(xué)院，江蘇 南京 210003；2.南京大學(xué) 計(jì)算機(jī)軟件新技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室，江蘇 南京 210093)

1 引言

由于傳感器網(wǎng)絡(luò)節(jié)點(diǎn)的處理能力、通信帶寬以及能量等資源有限，且部署在惡劣環(huán)境中，對(duì)節(jié)點(diǎn)替換電池或能量補(bǔ)充是不可能的，所以網(wǎng)絡(luò)一般采用高密度(20node/m3)部署策略[1]。但這種部署會(huì)造成信息冗余、信息沖突、網(wǎng)絡(luò)消耗能量過多、網(wǎng)絡(luò)生存時(shí)間縮短等問題。

在密集部署的監(jiān)測(cè)區(qū)域內(nèi)達(dá)到節(jié)約能量的方法就是去除一些覆蓋冗余節(jié)點(diǎn)，在保證整個(gè)網(wǎng)絡(luò)性能的前提下，將一部分節(jié)點(diǎn)處于工作狀態(tài)，而讓其他節(jié)點(diǎn)處于低功耗的休眠狀態(tài)。覆蓋是無(wú)線傳感器網(wǎng)絡(luò)對(duì)物理世界感知能力的體現(xiàn)，常作為描述無(wú)線傳感器網(wǎng)絡(luò)監(jiān)測(cè)服務(wù)質(zhì)量(QoS, quality of service)的標(biāo)準(zhǔn)，所以工作節(jié)點(diǎn)的選擇必須以對(duì)目標(biāo)區(qū)域的覆蓋為基礎(chǔ)[2]。如何判別一個(gè)節(jié)點(diǎn)的監(jiān)測(cè)區(qū)域是否被其鄰居節(jié)點(diǎn)完全覆蓋是選擇節(jié)點(diǎn)的前提。人們?cè)诠ぷ鞴?jié)點(diǎn)選擇及節(jié)點(diǎn)調(diào)度方面進(jìn)行大量研究[3～13]。文獻(xiàn)[4,5]將全部網(wǎng)絡(luò)節(jié)點(diǎn)組織成若干個(gè)互不相交的節(jié)點(diǎn)集，并且每個(gè)節(jié)點(diǎn)集都能夠完全覆蓋目標(biāo)區(qū)域。在每個(gè)時(shí)刻只有一個(gè)節(jié)點(diǎn)集處于工作狀態(tài)，其他處于低功耗的睡眠狀態(tài)?？梢钥闯觯瑹o(wú)相交節(jié)點(diǎn)集合的個(gè)數(shù)k越大，網(wǎng)絡(luò)生存時(shí)間越長(zhǎng)，但計(jì)算滿足上述覆蓋要求的無(wú)相交節(jié)點(diǎn)集合的最大個(gè)數(shù)是 NP完全問題。DiTian[6]提出一個(gè)基于網(wǎng)絡(luò)覆蓋的節(jié)點(diǎn)調(diào)度算法，它是根據(jù)自身位置及鄰居節(jié)點(diǎn)個(gè)數(shù)來(lái)判斷節(jié)點(diǎn)與其鄰居的覆蓋關(guān)系，保證一定的覆蓋能力。Jaekyu等[7]提出能夠保證感知覆蓋的分布式節(jié)點(diǎn)調(diào)度算法。通過節(jié)點(diǎn)的有效感知區(qū)域(ESA, effective sensing area)對(duì)節(jié)點(diǎn)進(jìn)行調(diào)度。以上這些算法都需要精確知道節(jié)點(diǎn)的位置信息，而位置信息的獲得要依賴于GPS、有向天線等基礎(chǔ)設(shè)施或定位機(jī)制，這種機(jī)制不僅有成本和復(fù)雜度較高、較多的能量消耗等問題外，還存在準(zhǔn)確定位的問題，不易用于軍事等應(yīng)用場(chǎng)所。

針對(duì)位置信息中覆蓋判別存在的問題，DiTian[8]等對(duì)文獻(xiàn)[6]進(jìn)行改進(jìn)，提出了位置無(wú)關(guān)的覆蓋判別模型，節(jié)點(diǎn)根據(jù)自身感知半徑內(nèi)的鄰居節(jié)點(diǎn)個(gè)數(shù)或最近距離信息，設(shè)定節(jié)點(diǎn)成為冗余節(jié)點(diǎn)的閾值，若鄰居節(jié)點(diǎn)個(gè)數(shù)或最近距離達(dá)到設(shè)定的閾值，則該節(jié)點(diǎn)為休眠節(jié)點(diǎn)。該算法計(jì)算簡(jiǎn)單，易于實(shí)現(xiàn)，但沒有考慮到節(jié)點(diǎn)休眠后其鄰居節(jié)點(diǎn)是否真正達(dá)到對(duì)該監(jiān)測(cè)區(qū)域的完全覆蓋，不能保證監(jiān)測(cè)的質(zhì)量。Gao[9]等分析了節(jié)點(diǎn)完全冗余的概率上下限，節(jié)點(diǎn)感知半徑內(nèi)鄰居節(jié)點(diǎn)個(gè)數(shù)計(jì)算自身成為冗余節(jié)點(diǎn)的概率，但覆蓋判別運(yùn)算復(fù)雜度高，且多個(gè)鄰居節(jié)點(diǎn)造成節(jié)點(diǎn)覆蓋冗余度高，消耗過多能量的缺點(diǎn)。后來(lái)的位置信息未知的一些節(jié)點(diǎn)調(diào)度算法[10～13]都是在這個(gè)思想上進(jìn)行擴(kuò)展，但沒有考慮節(jié)點(diǎn)位置信息未知帶來(lái)的覆蓋判別精度問題，不能保障目標(biāo)區(qū)域的監(jiān)測(cè)質(zhì)量。所以，如何提高節(jié)點(diǎn)的覆蓋判別精度是選擇工作節(jié)點(diǎn)和調(diào)度的前提，也是網(wǎng)絡(luò)生存時(shí)間延長(zhǎng)、保證目標(biāo)區(qū)域覆蓋的基礎(chǔ)。

為了克服基于位置信息計(jì)算帶來(lái)的能量消耗及位置信息未知時(shí)帶來(lái)的覆蓋判別精度不高、覆蓋判別誤差大等問題，設(shè)計(jì)一種距離輔助的節(jié)點(diǎn)覆蓋判別模型。其基本思想是在節(jié)點(diǎn)隨機(jī)部署情況下，根據(jù)節(jié)點(diǎn)與鄰居節(jié)點(diǎn)的距離信息，計(jì)算出該節(jié)點(diǎn)被鄰居節(jié)點(diǎn)的覆蓋程度，若覆蓋度達(dá)到應(yīng)用的需求，則該節(jié)點(diǎn)為冗余節(jié)點(diǎn)。理論分析和仿真實(shí)驗(yàn)結(jié)果說(shuō)明，距離輔助的覆蓋判別模型具有較高的覆蓋判別精度，在節(jié)點(diǎn)位置未知與精確位置已知情況下，對(duì)覆蓋判別的誤差僅為6.396 0%，能精確達(dá)到節(jié)點(diǎn)的覆蓋判別。與DiTian和Gao算法相比，覆蓋判別精度明顯提高，為服務(wù)質(zhì)量保證的節(jié)點(diǎn)覆蓋調(diào)度提供了基礎(chǔ)。

本文組織如下：第2節(jié)描述了節(jié)點(diǎn)的部署機(jī)制及感知模型，并說(shuō)明覆蓋判別中存在的問題；第3節(jié)提出覆蓋判別模型并對(duì)模型進(jìn)行分析；第4節(jié)對(duì)覆蓋判別模型進(jìn)行驗(yàn)證及分析；第5節(jié)是本文的結(jié)束語(yǔ)。

2 網(wǎng)絡(luò)模型和問題描述

2.1 節(jié)點(diǎn)部署和感知模型

假定M個(gè)傳感器節(jié)點(diǎn)隨機(jī)部署在監(jiān)測(cè)區(qū)域A內(nèi)，對(duì)于每一個(gè)傳感器節(jié)點(diǎn)Ui(i = 1, 2, 3,…, M)，做如下假設(shè)：

1) 節(jié)點(diǎn)的位置信息未知；

2) 節(jié)點(diǎn)密集部署且服從均勻分布，即不存在 2個(gè)節(jié)點(diǎn)重疊的情況；

3) 節(jié)點(diǎn)的感知模型采用圓形區(qū)域的布爾模型，且所有節(jié)點(diǎn)的感知半徑相等；

2.2 相關(guān)定義

在下面的討論中，對(duì)需要進(jìn)行覆蓋判別的節(jié)點(diǎn)稱為節(jié)點(diǎn)U，首先給出一些定義及定理。

1) 感知點(diǎn)。指在監(jiān)測(cè)區(qū)域內(nèi)的任意點(diǎn)xi。對(duì)于布爾感知模型，用感知點(diǎn)可以表示為

2) 網(wǎng)絡(luò)覆蓋度。指處于活動(dòng)狀態(tài)節(jié)點(diǎn)的覆蓋總面積與監(jiān)測(cè)區(qū)域總面積的比值，對(duì)于工作節(jié)點(diǎn)覆蓋面積來(lái)說(shuō)，取的是工作節(jié)點(diǎn)覆蓋的并集，即

其中，Acoverage代表工作節(jié)點(diǎn)對(duì)網(wǎng)絡(luò)覆蓋程度，Ai表示第i個(gè)工作節(jié)點(diǎn)的覆蓋面積，k表示監(jiān)測(cè)區(qū)域內(nèi)工作節(jié)點(diǎn)的個(gè)數(shù)。

3) 鄰居節(jié)點(diǎn)集。設(shè)節(jié)點(diǎn)的感知半徑為R，則存在任意節(jié)點(diǎn) U的鄰居集是指與該節(jié)點(diǎn)的距離小于或等于R的所有節(jié)點(diǎn)的集合，用Neighbor(U)表示，則

如圖1所示，節(jié)點(diǎn)U的感知區(qū)域內(nèi)的所有節(jié)點(diǎn)都屬于U的鄰居節(jié)點(diǎn)集。

圖1 節(jié)點(diǎn)的鄰居集

4) 鄰居覆蓋。若某一節(jié)點(diǎn)的感知范圍被其鄰居節(jié)點(diǎn)集 Neighbor(U)的感知范圍所覆蓋，則稱該節(jié)點(diǎn)被鄰居覆蓋。

5) 鄰居覆蓋期望。指節(jié)點(diǎn)的鄰居節(jié)點(diǎn)集對(duì)本節(jié)點(diǎn)的覆蓋程度，它是鄰居集在該節(jié)點(diǎn)的感知范圍內(nèi)構(gòu)成的監(jiān)測(cè)面積并集與該節(jié)點(diǎn)感知面積的比值。

其中，Cneighbor(U)表示節(jié)點(diǎn)U的鄰居覆蓋期望，AU表示節(jié)點(diǎn)U的覆蓋面積，Aj表示U鄰居集對(duì)節(jié)點(diǎn)U的覆蓋面積。

定理1 在節(jié)點(diǎn)感知半徑為R的感知區(qū)域內(nèi)存在鄰居集，對(duì)于任意感知點(diǎn)x，如果x在R的感知范圍內(nèi)且被某一鄰居節(jié)點(diǎn)覆蓋的概率為Px，則在R內(nèi)平均有Px的感知區(qū)域被鄰居節(jié)點(diǎn)覆蓋。

證明 假設(shè)R內(nèi)有N個(gè)感知點(diǎn){x1, x2,…, xN}，感知點(diǎn)在R內(nèi)服從均勻分布，且感知點(diǎn)被鄰居節(jié)點(diǎn)覆蓋情況相互獨(dú)立，設(shè)N個(gè)感知點(diǎn)中，有n個(gè)感知點(diǎn)被鄰居節(jié)點(diǎn)覆蓋的事件為X，Px表示某一感知點(diǎn)被某一鄰居節(jié)點(diǎn)覆蓋的概率，可知事件X服從

從式(4)中可以看出，事件X服從二項(xiàng)分布，即X～ B(Px，N)。

通過對(duì)事件X求期望，得：

從式(5)可以看出，在 R感知范圍內(nèi)平均有 NPx個(gè)感知點(diǎn)被鄰居節(jié)點(diǎn)覆蓋。

當(dāng)N趨于無(wú)窮大時(shí)，感知區(qū)域R可以看成是由無(wú)窮多個(gè)感知點(diǎn)組成，所以R感知范圍被鄰居節(jié)點(diǎn)平均覆蓋程度可以看成 R內(nèi)的感知點(diǎn)被鄰居節(jié)點(diǎn)覆蓋的程度，即

定理得證。

2.3 問題描述

在節(jié)點(diǎn)位置信息未知的情況下，節(jié)點(diǎn)U的感知半徑為 R，在其感知區(qū)域內(nèi)存在鄰居節(jié)點(diǎn)集Neighbor(U)，判別節(jié)點(diǎn) U的鄰居覆蓋期望是否達(dá)到某一閾值Cth，即

也就是說(shuō)式(3)是否精確達(dá)到應(yīng)用中需要的覆蓋期望值，如圖2所示，判別節(jié)點(diǎn)U的覆蓋面積被鄰居節(jié)點(diǎn)A、B、C、D、E覆蓋的程度。

圖2 問題描述

3 節(jié)點(diǎn)覆蓋判別模型

設(shè)在節(jié)點(diǎn)U感知區(qū)域內(nèi)由x={x1, x2,…, xi,…}感知點(diǎn)組成的感知集，由定理1可知，如果感知集x能被其鄰居節(jié)點(diǎn)覆蓋，則節(jié)點(diǎn)U可被其鄰居節(jié)點(diǎn)覆蓋。

假設(shè)在半徑為R的節(jié)點(diǎn)U內(nèi)存在n個(gè)鄰居節(jié)點(diǎn)，且鄰居節(jié)點(diǎn)在U內(nèi)服從均勻分布，對(duì)于任意一點(diǎn)xi，其在半徑為R的感知范圍內(nèi)的分布函數(shù)為

對(duì)節(jié)點(diǎn)的覆蓋判別，若只考慮鄰居節(jié)點(diǎn)個(gè)數(shù)，首先定義覆蓋函數(shù)fp= f (p,n1,…,nn)，其中p表示節(jié)點(diǎn)被鄰居節(jié)點(diǎn)覆蓋的概率，n1,…,nn表示鄰居節(jié)點(diǎn)。

若節(jié)點(diǎn)內(nèi)任意監(jiān)測(cè)點(diǎn) xi被一個(gè)鄰居節(jié)點(diǎn)覆蓋的概率為

存在2個(gè)鄰居節(jié)點(diǎn)，至少被一個(gè)鄰居節(jié)點(diǎn)覆蓋的概率為

n個(gè)鄰居節(jié)點(diǎn)中，至少被一個(gè)鄰居節(jié)點(diǎn)覆蓋的概率為

根據(jù)式(9)～式(11)可以求出節(jié)點(diǎn)U被鄰居節(jié)點(diǎn)覆蓋的程度，但在節(jié)點(diǎn)位置信息未知的情況下，鄰居節(jié)點(diǎn)與U的距離各不相同，造成在相同的鄰居節(jié)點(diǎn)個(gè)數(shù)情況下，對(duì)節(jié)點(diǎn)U的覆蓋程度存在很大誤差，如圖3、圖4所示，同樣為3個(gè)鄰居節(jié)點(diǎn)，從式(9)～式(11)計(jì)算的覆蓋概率是相同的，但實(shí)際上或者是部分覆蓋(如圖3所示)，或者是全覆蓋(如圖4所示)。

圖3 節(jié)點(diǎn)部分覆蓋

圖4 節(jié)點(diǎn)全覆蓋

為了解決覆蓋判別誤差大的問題，對(duì)覆蓋函數(shù)fp=f (p,n1,…,nn)改寫，引入節(jié)點(diǎn)到鄰居節(jié)點(diǎn)的距離信息，其改寫后的覆蓋函數(shù)為fp= f {p, (p1, d1), (p2, d2),…, (pi,di) ,…, (pn, dn) }，pi(i = 1, 2, 3,…, n)表示距離為 di的鄰居節(jié)點(diǎn)對(duì)節(jié)點(diǎn)的覆蓋概率。

若節(jié)點(diǎn)U存在鄰居節(jié)點(diǎn)V，如圖5所示，設(shè)U到V的距離為d (d≤R)，則節(jié)點(diǎn)V對(duì)節(jié)點(diǎn)U的覆蓋面積為

節(jié)點(diǎn)U的面積為

圖5 節(jié)點(diǎn)V對(duì)節(jié)點(diǎn)U的覆蓋面積

假定節(jié)點(diǎn)U內(nèi)有一個(gè)感知點(diǎn)xi，則該感知點(diǎn)被一個(gè)鄰居節(jié)點(diǎn)覆蓋的覆蓋函數(shù)為fp= f {p, (p1, d1)}，該感知點(diǎn)被覆蓋的概率為

若存在2個(gè)鄰居節(jié)點(diǎn)，感知點(diǎn)xi至少被一個(gè)鄰居節(jié)點(diǎn)覆蓋的覆蓋函數(shù)為fp= f {p, (p1, d1), (p2, d2)}，被鄰居節(jié)點(diǎn)覆蓋的概率為

其中，

表示節(jié)點(diǎn)被距離為di的鄰居節(jié)點(diǎn)覆蓋的面積。

若存在n個(gè)鄰居節(jié)點(diǎn)，則被鄰居節(jié)點(diǎn)覆蓋的概率為

根據(jù)定理1，可以從鄰居節(jié)點(diǎn)的距離信息判別出節(jié)點(diǎn)被其鄰居節(jié)點(diǎn)覆蓋的程度，若被鄰居節(jié)點(diǎn)覆蓋的程度滿足需要的鄰居覆蓋期望，即滿足式(7)，則可以認(rèn)為節(jié)點(diǎn)可以被鄰居節(jié)點(diǎn)覆蓋。

4 驗(yàn)證與分析

4.1 實(shí)驗(yàn)環(huán)境及參數(shù)

為了評(píng)價(jià)和分析本文提出的節(jié)點(diǎn)覆蓋判別算法，在MATLAB7.0上進(jìn)行多次驗(yàn)證，對(duì)該模型與覆蓋精確計(jì)算及節(jié)點(diǎn)信息未知的Gao[9]方案和DiTian[8]方案進(jìn)行了對(duì)比驗(yàn)證。

假定某一節(jié)點(diǎn)的感知半徑為40個(gè)單位，在其內(nèi)部隨機(jī)部署1～20個(gè)鄰居節(jié)點(diǎn)。

4.2 實(shí)驗(yàn)及分析

4.2.1 與精確計(jì)算覆蓋度比較

為了確保鄰居節(jié)點(diǎn)對(duì)節(jié)點(diǎn)的覆蓋精確性，在節(jié)點(diǎn)半徑為40個(gè)單位的節(jié)點(diǎn)感知范圍內(nèi)產(chǎn)生361 201個(gè)像素，隨機(jī)生成n個(gè)鄰居節(jié)點(diǎn)均勻獨(dú)立地分布在R內(nèi)。每個(gè)像素定義為一個(gè)結(jié)構(gòu)，根據(jù)感知半徑的大小和n個(gè)鄰居節(jié)點(diǎn)的坐標(biāo)，依次計(jì)算節(jié)點(diǎn)內(nèi)的像素被其鄰居節(jié)點(diǎn)的覆蓋情況，若像素點(diǎn)沒有被鄰居節(jié)點(diǎn)覆蓋，結(jié)構(gòu)內(nèi)的值為0，若被鄰居節(jié)點(diǎn)覆蓋其值為1。顯然，節(jié)點(diǎn)被鄰居節(jié)點(diǎn)覆蓋的情況就是被鄰居節(jié)點(diǎn)覆蓋的像素點(diǎn)的數(shù)目與總的像素?cái)?shù)目的比值。為了更好地反映統(tǒng)計(jì)規(guī)律，所有的結(jié)果都是200次模擬實(shí)驗(yàn)的平均抽樣，其比較結(jié)果如圖6所示。

圖6說(shuō)明了節(jié)點(diǎn)位置信息已知和未知情況下，隨著鄰居節(jié)點(diǎn)個(gè)數(shù)增加，對(duì)節(jié)點(diǎn)的覆蓋判別的比較結(jié)果。從圖中可以看出，當(dāng)只有一個(gè)鄰居節(jié)點(diǎn)時(shí)，通過精確計(jì)算的節(jié)點(diǎn)覆蓋度為59.654 3%，DANCI計(jì)算的覆蓋度為64.996 6%，二者的誤差為5.342 3%；鄰居節(jié)點(diǎn)個(gè)數(shù)增加到 4時(shí)，精確計(jì)算的節(jié)點(diǎn)覆蓋度為96.137 6%，DANCI計(jì)算值為98.885 8%，二者的誤差為2.748 2%；節(jié)點(diǎn)個(gè)數(shù)增加到7時(shí)，精確計(jì)算的節(jié)點(diǎn)覆蓋度為 99.543 5%，DANCI的節(jié)點(diǎn)覆蓋度為99.975 5%，二者誤差僅為 0.432 0%；節(jié)點(diǎn)個(gè)數(shù)達(dá)到12時(shí)，精確計(jì)算的值為99.977 3%，DANCI的節(jié)點(diǎn)覆蓋度為99.999 9%，二者誤差為0.022 6%，可以看作節(jié)點(diǎn)被鄰居節(jié)點(diǎn)全覆蓋。

圖6 與精確位置信息誤差情況

通過對(duì)誤差值進(jìn)行統(tǒng)計(jì)分析，得出在2種方法下，當(dāng)距離確定時(shí)，隨著節(jié)點(diǎn)個(gè)數(shù)的增加，二者覆蓋判別最大誤差為6.396 0%，最小誤差為0.000 1%，說(shuō)明DANCI節(jié)點(diǎn)覆蓋判別模型已達(dá)到十分精確的值。但從總體上來(lái)說(shuō)，DANCI對(duì)節(jié)點(diǎn)覆蓋判別的程度比精確計(jì)算的覆蓋度要略高一些。

4.2.2 與鄰居節(jié)點(diǎn)個(gè)數(shù)比較

Gao[9]等在位置信息未知的情況下，用鄰居節(jié)點(diǎn)個(gè)數(shù)對(duì)節(jié)點(diǎn)的覆蓋進(jìn)行分析與驗(yàn)證，同樣在節(jié)點(diǎn)位置信息未知情況下，當(dāng)采用DANCI判別時(shí)，二者覆蓋判別精度上的比較，如圖7所示。

圖7 與鄰居節(jié)點(diǎn)個(gè)數(shù)比較

從圖7可以看出，在相同的鄰居節(jié)點(diǎn)個(gè)數(shù)下，采用距離輔助的節(jié)點(diǎn)覆蓋判別的精度比Gao的要高，當(dāng)節(jié)點(diǎn)內(nèi)有 2個(gè)鄰居節(jié)點(diǎn)時(shí)，Gao的判別覆蓋度為62.791 9%，DANCI的判別覆蓋度為90.712 3%；當(dāng)有4個(gè)鄰居節(jié)點(diǎn)時(shí)，Gao的判別覆蓋度為 86.241 3%，DANCI的判別覆蓋度為99.015 5%，其對(duì)節(jié)點(diǎn)的覆蓋度明顯提高，這是因?yàn)椴捎昧司嚯x輔助信息，節(jié)點(diǎn)的距離代表了鄰居節(jié)點(diǎn)對(duì)節(jié)點(diǎn)的覆蓋程度，極大地提高了節(jié)點(diǎn)的覆蓋判別精度。

隨著鄰居節(jié)點(diǎn)個(gè)數(shù)的增加，節(jié)點(diǎn)的覆蓋度呈上升趨勢(shì)，Gao有10個(gè)鄰居節(jié)點(diǎn)時(shí)，節(jié)點(diǎn)覆蓋度才達(dá)到99.298 3%，而DANCI在有5個(gè)鄰居節(jié)點(diǎn)時(shí)，對(duì)節(jié)點(diǎn)的覆蓋判別已達(dá)到99.669 2%，這說(shuō)明DANCI在相同覆蓋度的情況下，減少鄰居節(jié)點(diǎn)的個(gè)數(shù)，進(jìn)而達(dá)到節(jié)約節(jié)點(diǎn)能量，減少覆蓋冗余帶來(lái)的信息冗余，信息沖突等體現(xiàn)較好的效果，在節(jié)點(diǎn)調(diào)度中，可以保證較少的工作節(jié)點(diǎn)，最小化網(wǎng)絡(luò)能量消耗。

4.2.3 與最近距離算法比較

DiTian[8]等在節(jié)點(diǎn)位置信息未知的情況下，采用最近距離算法來(lái)判別節(jié)點(diǎn)的覆蓋度相對(duì)于使用DANCI模型時(shí)的覆蓋度的比較，比較結(jié)果如圖 8所示。

圖8 與最近距離比較

從圖8可以看出，當(dāng)節(jié)點(diǎn)與鄰居節(jié)點(diǎn)的距離越小時(shí)，對(duì)節(jié)點(diǎn)的覆蓋度越大。當(dāng)僅存在一個(gè)鄰居節(jié)點(diǎn)時(shí)，2種覆蓋判別的結(jié)果是相等的，這是因?yàn)镈iTian是在鄰居節(jié)點(diǎn)中選擇了一個(gè)最近距離的鄰居節(jié)點(diǎn)來(lái)判別覆蓋，不考慮其他鄰居節(jié)點(diǎn)對(duì)它的覆蓋度。DiTian算法隨著距離的增大，對(duì)節(jié)點(diǎn)的判別覆蓋度呈線性下降趨勢(shì)，DiTian對(duì)節(jié)點(diǎn)的覆蓋判別不受鄰居節(jié)點(diǎn)個(gè)數(shù)增加的影響，但DANCI模型隨著鄰居節(jié)點(diǎn)個(gè)數(shù)越多具有明顯優(yōu)勢(shì)。鄰居節(jié)點(diǎn)個(gè)數(shù)越多，對(duì)節(jié)點(diǎn)的覆蓋度就越大，在與節(jié)點(diǎn)的距離為25個(gè)單位時(shí)，3個(gè)鄰居節(jié)點(diǎn)可以達(dá)到90.405 2%，4個(gè)鄰居節(jié)點(diǎn)對(duì)節(jié)點(diǎn)的覆蓋度可達(dá)到94.951 7%。

圖9說(shuō)明了DANCI模型在鄰居節(jié)點(diǎn)個(gè)數(shù)與距離增加的情況下，對(duì)節(jié)點(diǎn)的覆蓋度情況。從圖中可以看出，隨著鄰居節(jié)點(diǎn)個(gè)數(shù)的增加，對(duì)節(jié)點(diǎn)的覆蓋度判別呈上升趨勢(shì)，但隨著距離的加大，對(duì)節(jié)點(diǎn)的覆蓋判別呈下降趨勢(shì)，但二者在某個(gè)數(shù)據(jù)值上對(duì)節(jié)點(diǎn)的覆蓋度達(dá)到飽和。

圖9 節(jié)點(diǎn)個(gè)數(shù)、鄰居距離與節(jié)點(diǎn)覆蓋度關(guān)系

5 結(jié)束語(yǔ)

本文深入研究了無(wú)線傳感器網(wǎng)絡(luò)中節(jié)點(diǎn)覆蓋判別中存在的問題，針對(duì)當(dāng)前節(jié)點(diǎn)位置信息未知的情況下，基于鄰居節(jié)點(diǎn)個(gè)數(shù)、單一距離信息下節(jié)點(diǎn)覆蓋判別存在不精確問題，提出了基于距離的節(jié)點(diǎn)覆蓋判別模型，通過理論驗(yàn)證及仿真分析，證明該模型相對(duì)于節(jié)點(diǎn)位置信息已知的情況下，覆蓋判別的精度最大誤差僅存在6.396 0%，相對(duì)于鄰居節(jié)點(diǎn)個(gè)數(shù)和最近距離覆蓋判別算法，具有較高的覆蓋判別精度，為保證整個(gè)監(jiān)測(cè)區(qū)域的覆蓋提供基礎(chǔ)。在本文中假設(shè)節(jié)點(diǎn)間的距離信息已知，然而在實(shí)際的應(yīng)用中，節(jié)點(diǎn)間距離信息的不穩(wěn)定會(huì)對(duì)節(jié)點(diǎn)的覆蓋判別產(chǎn)生很大的影響，造成覆蓋判別上的誤差，在將來(lái)的工作中，著重分析節(jié)點(diǎn)位置對(duì)覆蓋判別的影響，進(jìn)而在此基礎(chǔ)上進(jìn)行節(jié)點(diǎn)調(diào)度，達(dá)到節(jié)約節(jié)點(diǎn)能量，延長(zhǎng)網(wǎng)絡(luò)生存時(shí)間的目的。

[1] SHIH E, CHO S, ICKES N, et al. Physical layer driven protocol and algorithm design for energy-efficient wireless sensor networks[A].Proceedings of the 7th Annual International Conference on Mobile Computing and Networking[C]. Rome, Italy, 2001.272-287.

[2] 陶丹, 孫巖, 陳后金. 視頻傳感器網(wǎng)絡(luò)中最壞情況覆蓋檢測(cè)與修補(bǔ)算法[J]. 電子學(xué)報(bào), 2009, 37(10)∶ 2284-2290.TAO D, SUN Y, CHEN H J. Worst-case coverage detection and repair algorithm for video sensor networks[J]. Acta Electronica Sinica, 2009,37(10)∶ 2284-2290.

[3] WANG L, XIAO Y. A survey of energy efficient scheduling mechanisms in sensor networks[J]. IEEE Transactions on Wireless Communications, 2007, 1(4)∶ 660-670.

[4] LIU C, WU K. Random coverage with guaranteed connectivity∶ joint scheduling for wireless sensor networks[J]. IEEE Transactions on Parallel and Distributed Systems, 2006, 17(6)∶ 562-575.

[5] XIAO Y, CHEN H, et al. Modeling detection metrics in randomized scheduling algorithm in wireless sensor networks[A]. IEEE Conference on Wireless Communications and Networking (WCNC’07)[C].Kowloon, Hong Kong, China, 2007. 3741-3745.

[6] TIAN D, GEORGANAS N. A node scheduling scheme for energy conservation in large wireless sensor networks[J]. Journal of Wireless Communications and Mobile Computing Journal, 2003, 3(2)∶ 271-290.

[7] JAEKYU C, GILSOO K, TAEKYOUNG K, et al. A distributed node scheduling protocol considering sensing coverage in wireless sensor networks[A]. IEEE 66th Vehicular Technology Conference[C]. Baltimore, MD, 2007. 352-356.

[8] TIAN D, GEORGANAS N. Location and calculation-free nodescheduling schemes in large wireless sensor networks[J]. Ad Hoc Networks, 2004, 2(1)∶ 65-85.

[9] GAO Y, WU K, LI F. Analysis on the redundancy of wireless sensor networks[A]. Proceedings of the 2nd ACM International Conference on Wireless Sensor Networks and Applications[C]. San Diego, CA,USA, 2003. 108 - 114.

[10] ZHANG M, CHAN M, CHOON A A. Coverage protocol for wireless sensor networks using distance estimates[A]. The 4th Annual IEEE Communications Society Conference on Sensor, Mesh and Ad Hoc Communications and Networks (SECON '07)[C]. San Diego, CA,USA, 2007. 183-192.

[11] JIANG S F, YANG, M H. An enhanced perimeter coverage based density control algorithm for wireless sensor network[A]. Third International Conference on Wireless and Mobile Communications(ICWMC '07)[C]. Guadeloupe, French Caribbean, 2007.79-79.

[12] GAO Y, WU K, LI F, et al. Lightweight deployment-aware scheduling for wireless sensor networks[J]. Mobile Networks and Applications,2005, 10(6)∶ 837-852.

[13] CHEN J, YU F Q. A location independent and coverage efficient protocol for wireless sensor networks[A]. IEEE International Conference on Integration Technology(ICIT '07)[C]. Shenzhen, China, 2007.751-755.

[14] BEJERANO Y. Simple and efficient k-coverage verification without location information[A]. The 27th Conference on Computer Communications (INFOCOM’08)[C]. Phoenix, AZ, 2008. 291-295.