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

(1.南京郵電大學 計算機學院，江蘇 南京 210003；2.南京大學 計算機軟件新技術國家重點實驗室，江蘇 南京 210093)

1 引言

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

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

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

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

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

2 網絡模型和問題描述

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

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

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

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

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

2.2 相關定義

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

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

2) 網絡覆蓋度。指處于活動狀態(tài)節(jié)點的覆蓋總面積與監(jiān)測區(qū)域總面積的比值，對于工作節(jié)點覆蓋面積來說，取的是工作節(jié)點覆蓋的并集，即

其中，Acoverage代表工作節(jié)點對網絡覆蓋程度，Ai表示第i個工作節(jié)點的覆蓋面積，k表示監(jiān)測區(qū)域內工作節(jié)點的個數。

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

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

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

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

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

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

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

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

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

通過對事件X求期望，得：

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

當N趨于無窮大時，感知區(qū)域R可以看成是由無窮多個感知點組成，所以R感知范圍被鄰居節(jié)點平均覆蓋程度可以看成 R內的感知點被鄰居節(jié)點覆蓋的程度，即

定理得證。

2.3 問題描述

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

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

圖2 問題描述

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

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

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

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

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

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

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

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

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

圖4 節(jié)點全覆蓋

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

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

節(jié)點U的面積為

圖5 節(jié)點V對節(jié)點U的覆蓋面積

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

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

其中，

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

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

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

4 驗證與分析

4.1 實驗環(huán)境及參數

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

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

4.2 實驗及分析

4.2.1 與精確計算覆蓋度比較

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

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

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

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

4.2.2 與鄰居節(jié)點個數比較

Gao[9]等在位置信息未知的情況下，用鄰居節(jié)點個數對節(jié)點的覆蓋進行分析與驗證，同樣在節(jié)點位置信息未知情況下，當采用DANCI判別時，二者覆蓋判別精度上的比較，如圖7所示。

圖7 與鄰居節(jié)點個數比較

從圖7可以看出，在相同的鄰居節(jié)點個數下，采用距離輔助的節(jié)點覆蓋判別的精度比Gao的要高，當節(jié)點內有 2個鄰居節(jié)點時，Gao的判別覆蓋度為62.791 9%，DANCI的判別覆蓋度為90.712 3%；當有4個鄰居節(jié)點時，Gao的判別覆蓋度為 86.241 3%，DANCI的判別覆蓋度為99.015 5%，其對節(jié)點的覆蓋度明顯提高，這是因為采用了距離輔助信息，節(jié)點的距離代表了鄰居節(jié)點對節(jié)點的覆蓋程度，極大地提高了節(jié)點的覆蓋判別精度。

隨著鄰居節(jié)點個數的增加，節(jié)點的覆蓋度呈上升趨勢，Gao有10個鄰居節(jié)點時，節(jié)點覆蓋度才達到99.298 3%，而DANCI在有5個鄰居節(jié)點時，對節(jié)點的覆蓋判別已達到99.669 2%，這說明DANCI在相同覆蓋度的情況下，減少鄰居節(jié)點的個數，進而達到節(jié)約節(jié)點能量，減少覆蓋冗余帶來的信息冗余，信息沖突等體現較好的效果，在節(jié)點調度中，可以保證較少的工作節(jié)點，最小化網絡能量消耗。

4.2.3 與最近距離算法比較

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

圖8 與最近距離比較

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

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

圖9 節(jié)點個數、鄰居距離與節(jié)點覆蓋度關系

5 結束語

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

[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] 陶丹, 孫巖, 陳后金. 視頻傳感器網絡中最壞情況覆蓋檢測與修補算法[J]. 電子學報, 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.