無線傳感器網(wǎng)絡路徑覆蓋問題研究

李 磊 張寶賢 黃河清 劉海濤

①(中國科學院上海微系統(tǒng)與信息技術(shù)研究所 中國科學院無線傳感網(wǎng)與通信重點實驗室 上海 200050)②(中國科學院研究生院泛在與傳感網(wǎng)研究中心 北京 100049)

1 引言

無線傳感器網(wǎng)絡(Wireless Sensor Network,WSN)是一項新興技術(shù)，被廣泛應用于國防、工業(yè)、環(huán)境、健康等多個領(lǐng)域。在實際應用中，無線傳感器網(wǎng)絡節(jié)點通常是隨機分布在目標區(qū)域，在某些應用場景下，如環(huán)境檢測，往往要求區(qū)域滿足k(k≥1)覆蓋，即區(qū)域內(nèi)的每一個點至少被k個傳感器覆蓋到，這樣的問題通常被稱為區(qū)域覆蓋(area coverage)。區(qū)域覆蓋度能充分反映傳感器網(wǎng)絡對目標檢測區(qū)域的覆蓋情況，是無線傳感器網(wǎng)絡QoS指標之一，文獻[1-3]對區(qū)域覆蓋進行了詳細的分析。而在另外一些應用場景下，如入侵檢測和目標跟蹤，人們更加關(guān)心的是入侵目標移動路徑的覆蓋情況，這樣的覆蓋問題通常被稱為路徑覆蓋(path coverage)。根據(jù)實際應用需求的不同，衡量路徑覆蓋的標準也不同，其中最常用的有以下兩種：(1)路徑滿足k覆蓋的平均比例，即目標沿任意路徑移動時，該路徑滿足k覆蓋的部分所占的比例。(2)路徑滿足k覆蓋的概率，即目標沿任意路徑移動時，該路徑上的點全部滿足k覆蓋的概率。現(xiàn)有的關(guān)于路徑覆蓋的研究往往都是針對直線路徑，這是因為在入侵者不知道網(wǎng)絡中節(jié)點的位置信息時，往往會選擇沿直線路徑穿越檢測區(qū)域，這樣可以用最少的時間穿越檢測區(qū)域，從而減小被發(fā)現(xiàn)的可能性。本文的研究也是基于這個假設，所以除非特殊聲明，后文所提到的路徑覆蓋都是指直線路徑覆蓋。針對以上兩種覆蓋標準，文獻[4,5]分別在節(jié)點同構(gòu)(Homogeneous)模型和節(jié)點異構(gòu)(Heterogeneous)模型下對2維區(qū)域節(jié)點布設密度與路徑滿足k覆蓋的平均比例之間的關(guān)系進行了分析，并給出計算表達式。文獻[6]對節(jié)點布設密度與路徑滿足1覆蓋的概率之間的關(guān)系進行了分析，并給出計算表達式，但是并沒有給出k(k＞1)覆蓋概率的分析。然而，路徑k(k＞1)覆蓋有著非常廣泛的應用場景，比如說當網(wǎng)絡用來進行目標跟蹤時，為了達到定位的目的，往往要求k≥3[7,8]。另外文獻[6]在分析時假設傳感器節(jié)點的感知半徑是相同的，而這一點在實際應用中是很難保證的。因此本文對節(jié)點布設密度與路徑滿足k(k≥1)覆蓋概率之間的關(guān)系進行了分析，并給出路徑滿足k(k≥1)覆蓋概率的理論下限。實驗表明，在k值較小時，本文給出的理論下限與實際仿真結(jié)果比較接近。

本文的組織結(jié)構(gòu)如下：第2節(jié)給出系統(tǒng)模型和本文所要解決的問題，第3節(jié)將2維區(qū)域的路徑覆蓋問題轉(zhuǎn)化為1維線段覆蓋問題，第4節(jié)給出1維直線段滿足k覆蓋的概率分析，第5節(jié)給出在2維區(qū)域內(nèi)判定直線路徑是否滿足k覆蓋的方法，第6節(jié)給出仿真結(jié)果，第7節(jié)總結(jié)全文。

2 系統(tǒng)模型和問題描述

本節(jié)首先給出系統(tǒng)模型，然后定義所要解決的問題。本文中“傳感器節(jié)點”與“節(jié)點”含義相同。本文研究的無線傳感器網(wǎng)絡系統(tǒng)模型基于如下假設：

(1)無線傳感器節(jié)點按泊松分布隨機散布在面積為A的正方形監(jiān)測區(qū)域。令λ表示節(jié)點的布設密度，N 表示監(jiān)測區(qū)域的節(jié)點數(shù)。顯然，N服從以λA為期望的泊松分布。

(2)無線傳感器節(jié)點為同構(gòu)節(jié)點，節(jié)點的感知模型采用0/1模型，即：節(jié)點以概率1檢測以其為中心、以r為半徑的圓形檢測區(qū)域(不包括圓上的點)，這樣的感知模型通常被稱為泊松布爾模型(Poisson Boolean model)。

(3)本文用xi(0＜i≤N)表示區(qū)域內(nèi)的節(jié)點，其感知范圍用ri表示，ri的取值范圍為(0, R]，概率密度函數(shù)用f(ri)表示，期望值用β表示。

本文研究的第1個問題表述如下：

問題1 目標沿某直線路徑L移動一段距離s(假設s?R，且s＜)，求該路徑滿足k覆蓋的概率。

3 問題轉(zhuǎn)化

本節(jié)將路徑覆蓋問題轉(zhuǎn)化為普通的1維線段覆蓋問題。由于本文采用的是0/1感知模型，任意節(jié)點xi(0＜i≤N)與路徑L的距離小于其感知范圍ri時，都可以在L上覆蓋一定區(qū)域，本文用li表示該區(qū)域的長度(見圖1，不失一般性，假設L位于坐標系的橫軸上)，文獻[5]給出了li的概率分布函數(shù)：

另外，所有與L的距離小于其感知范圍ri的節(jié)點xi都在L上有一個映射點yi(如圖1所示)，文獻[5]通過證明給出“yi所形成的點過程是以2λβ為期望值的泊松點過程(Poisson point process)”。這樣，圖1所示入侵路徑問題可以轉(zhuǎn)化為如下1維線覆蓋問題：

圖1 一條直線路徑在2維無線傳感器網(wǎng)絡中的覆蓋情況

問題2 在已知線段L上以密度λ'=2λβ布設節(jié)點，節(jié)點的感知直徑l的概率密度函數(shù)為g(l)，求該線段滿足k覆蓋的概率(見圖2)。

圖2 問題2給出的1維線覆蓋示意圖

由于問題2和問題1是等價的，所以問題2的解答顯然適用于問題1，另外由于問題2也是一個普通的1維線覆蓋問題，因此問題2的解答也適用于其它的1維線k覆蓋問題，比如說弱柵欄覆蓋(weak barrier coverage)[9,10]。弱柵欄覆蓋是指入侵者沿垂直于入侵邊界的路線穿越帶狀檢測區(qū)域時所引發(fā)的覆蓋問題，由于該覆蓋問題只與節(jié)點在水平方向的位置有關(guān)，因此同樣可以轉(zhuǎn)化為普通的1維線覆蓋問題。

為方便后文的表述，定義節(jié)點yi的覆蓋區(qū)域的左邊界為起始點(starting point)，yi的覆蓋區(qū)域的右邊界為結(jié)束點(ending point)，并用zi表示節(jié)點yi的覆蓋區(qū)域的左邊界(見圖2)，很顯然，這些起始點同樣組成以2λβ為期望的泊松點過程。

4 1維線段滿足k覆蓋的概率建模分析

為了保證1維直線段滿足k覆蓋，則要求該線段上的任意點都被至少k個節(jié)點覆蓋，一條線段上有無數(shù)個點，因此1維線全覆蓋的問題是一個連續(xù)域的問題，為了計算1維直線段滿足k覆蓋的概率，首先需要將該問題從連續(xù)域轉(zhuǎn)換到離散域。

本文同文獻[4,5]一樣假設s?R，從而忽略掉路徑邊界效應對結(jié)果的影響。為了將該問題轉(zhuǎn)換到離散域以便于計算，首先給出如下定理：

定理1 直線段L滿足k覆蓋的充分必要條件是該線段上的所有起始點都至少被k個節(jié)點覆蓋。

證明 必要性是很顯然的，如果該線段滿足k覆蓋，那么這條線上所有的點都滿足k覆蓋，當然也包括所有的起始點。

然后證明充分性。在1維線段上任取一點u，如果能夠證明u為k覆蓋，則該線段滿足k覆蓋。假設v是u右邊距離u最近的一個起始點，為了保證點v為k覆蓋，則至少有k個覆蓋區(qū)域的起始點處于v的左邊，且其結(jié)束點處于v的右方，而u與v之間不存在起始點，所以能夠覆蓋v的覆蓋區(qū)域均能覆蓋點u，因此點u滿足k覆蓋。這里，一個“覆蓋區(qū)域”是指一個節(jié)點在目標直線上的覆蓋區(qū)域。

綜合以上兩點，該定理得以證明。 證畢

假設2維區(qū)域內(nèi)共有n個節(jié)點與路徑L的距離小于其感知半徑，根據(jù)第2節(jié)的系統(tǒng)模型，n服從以λ's=2λs β為期望的泊松分布，在s足夠大的情況下，n近似取值2λ s β。如果用Ak(i)表示第i個起始點zi(1≤i≤n)被至少k個節(jié)點覆蓋到這一事件，則根據(jù)定理1，L滿足k覆蓋的概率可以用下式表示：

其中Pr[T]表示事件T發(fā)生的概率。在起始點所形成的泊松點過程下，任一起始點滿足k覆蓋的概率Pr[Ak(i)]可以用下式表示：

其中a=E(l)，式(3)的推導可以參見文獻[1]。盡管可以得出某一個點滿足k覆蓋的概率，但是很顯然Ak(i)，1≤i≤n，之間并不一定具有相互獨立的性質(zhì)，因此很難為式(2)求得一個準確的計算形式。本文利用FKG不等式[11]來計算式(2)的下限，F(xiàn)KG不等式是指在泊松布爾模型下，如果有事件B1和B2隨著節(jié)點密度的增加都是增函數(shù)或都是減函數(shù)，則有如下性質(zhì)：

由式(3)可以看出，Ak(i)，1≤i≤n，是節(jié)點密度的增函數(shù)，則利用FKG不等式有

可以利用式(5)計算長度為s的直線段滿足k覆蓋的概率下限，特別地，當k=1時，有如下表達式：

5 路徑k覆蓋的判定方法

在給出仿真結(jié)果之前，首先對如何在2維區(qū)域判定一條直線路徑是否滿足k覆蓋的方法做一些說明。由于直線路徑在2維坐標系中可以是任意走向的，因此，為了簡化計算的復雜度，本文首先將其映射到橫軸，然后通過判定映射后的線段是否滿足k覆蓋的方法來判定目標路徑能否滿足k覆蓋。具體流程如下：

首先以正方形布設區(qū)域的左下角為原點建立坐標系，假設直線路徑的兩個端點的坐標分別為(X1,Y1)，(X2,Y2)，不失一般性，假設X1＜X2。為方便描述，本節(jié)用[α, ?]表示點(α,0)與點(?,0)之間的線段。則線段[X1, X2]就是目標路徑在橫軸的投影。

然后找出所有與目標路徑距離小于其感知半徑的節(jié)點，假設共有Num個，并計算這些節(jié)點在目標路徑上的覆蓋區(qū)域的兩個端點的坐標值，分別記這兩個端點的橫坐標為LPi，RPi，1≤i≤Num。不失一般性，同樣假設LPi＜RPi，如果LPi＜ X1，則LPi=X1，如果RPi＞X2，則RPi= X2。則[LPi, RPi]，?1≤i≤Num，就是節(jié)點在目標路徑上的覆蓋區(qū)域在橫軸上的投影，顯然，如果[LPi, RPi]，?1≤i≤Num，可以k覆蓋線段[X1, X2]，則目標路徑滿足k覆蓋，否則目標路徑不滿足k覆蓋(如圖3所示)。

圖3 路徑覆蓋度判定方法示意圖

判定[X1, X2]是否滿足k覆蓋的具體方法如下：因為點(LPi,0)，(RPi,0)，?1≤i≤Num，和端點(X1,0)，(X2,0)將線段[X1, X2]分成2×Num+1個小線段(包括長度為0的小線段)，如果這些小線段全部滿足k覆蓋，則[X1, X2]滿足k覆蓋。因此定義變量Cov_degree記錄當前小線段的覆蓋度，并將其初始值設為0。從X1開始檢測每個小線段的覆蓋度，如果當前小線段的右端點屬于集合{LPi, 1≤i≤Num}，則下一小段的Cov_degree加1，否則減1。一旦出現(xiàn)Cov_degree＜k，并且當前段的長度不為0，則說明[X1, X2]不滿足k覆蓋。

下面以圖3為例對上述方法進行說明，[X1, X2]在圖3中被分成了5段，分別是[X1, LP1]，[LP1, RP1]，[RP1, LP2]，[LP2, RP2]，[RP2, X2]。Cov_degree的初始值設置為0，所以[X1, LP1]的覆蓋度為0，但是由于[X1, LP1]的長度為0，所以不影響路徑覆蓋度的判定。線段[X1, LP1]的右端點LP1屬于集合{LPi,1≤i≤2}，所以[LP1, RP1]的覆蓋度為1，同理可以求得其余各小段的覆蓋度。顯然，由于[RP1, LP2]和[RP2, X2]的覆蓋度為0，圖3的目標路徑不滿足1覆蓋。本文提出的映射檢測法可以使路徑覆蓋度的判定擺脫2維坐標系的影響，從而簡化計算的復雜度，同理也可以把路徑映射到縱軸進行判定。

6 仿真結(jié)果

為了驗證式(5)的正確性，本文采用MATLAB進行仿真，并將實驗統(tǒng)計結(jié)果與理論分析結(jié)果進行比較。在仿真實驗中，λ以0.2為步長由0變化到6，在每次實驗中，節(jié)點按泊松分布隨機布設在A=100 m×100 m的正方形區(qū)域，然后在其中隨機地選擇長度s=30 m的直線路徑，并檢測其是否滿足k覆蓋。仿真過程中，為了避免區(qū)域邊界效應的影響，在選擇直線路徑的兩個端點時使它們與邊界的距離大于R。針對每個λ，該實驗重復300次，并按下式計算路徑滿足k覆蓋的概率：

下面分別給出節(jié)點感知半徑服從不同概率分布時對第4節(jié)推導的理論分析結(jié)果的仿真驗證。

6.1 節(jié)點感知半徑相等

假設所有節(jié)點的感知半徑都相等，即：感知半徑都是R，這種感知模型也是覆蓋問題的理論分析中使用最廣泛的一種。根據(jù)第2節(jié)的定義有β=R，li服從如下概率分布：

可以很容易地求得a=E(l)=πR/2，將β和a的值代入式(5)得到如下式子

圖4給出R=1 m時路徑滿足k覆蓋的概率隨λ的變化趨勢。

6.2 節(jié)點感知半徑服從均勻分布

假設節(jié)點的感知半徑在[R/2, R]的區(qū)間內(nèi)服從均勻分布，則有β=3R/4，li服從概率分布：

a=E(l)的具體數(shù)值可以用數(shù)值計算方法得到，圖4給出R=1.5 m時路徑滿足k覆蓋的概率隨λ的變化趨勢。

從圖4和圖5可以看出，在k值較小的時候，本文所給出的理論下界與實際仿真結(jié)果的差距較小。但是隨著k值變大，理論值與實際仿真值的差距變大，這是因為隨著k的變大，相鄰Ak(i)，1≤i ≤n的相關(guān)性也在變大，使用FKG不等式所帶來的誤差也隨之變大。另外，隨著覆蓋概率的變大，理論值與仿真值之間的差距呈現(xiàn)變小的趨勢，考慮到在實際布設情況下，往往要求較高的k覆蓋概率，且k值的設置不會很大，本文給出的分析結(jié)果對實際網(wǎng)絡布設有著較為重要的指導意義。

圖4和圖5中分析結(jié)果與仿真結(jié)果偶爾有交叉，尤其是在k=1和k=2時，這是由實驗樣本的隨機性及樣本空間有限引起的，隨著k的變大，由FKG不等式所帶來的誤差也隨之變大，交叉也越來越少。

圖4 節(jié)點的感知半徑相等時路徑滿足k覆蓋的概率隨λ的變化趨勢

圖5 節(jié)點的感知半徑服從均勻分布時 路徑滿足k覆蓋的概率隨λ的變化趨勢

7 結(jié)論

本文對2維無線傳感器網(wǎng)絡中直線路徑滿足k覆蓋的概率進行了建模分析，并給出其理論下界。給定路徑滿足k覆蓋所需要的概率，由該下界求得的節(jié)點密度可以保證路徑以不低于給定的概率滿足k覆蓋，而且從仿真結(jié)果中可以看出，在k值較小時，由該下界求得的節(jié)點密度與使路徑以給定概率滿足k覆蓋所需的最小節(jié)點密度非常接近，因此本文的結(jié)果對網(wǎng)絡規(guī)模的設置有重要的參考價值。

[1] Hall P. Introduction to the Theory of Coverage Processes[M].New York: John Wiley & Sons, 1988: 79-119.

[2] Shakkottai S, Srikant R, and Shroff N. Unreliable sensor grids:coverage, connectivity and diameter[C]. Proceedings of IEEE INFOCOM’03, San Francisco, CA, USA, Mar. 30-Apr. 3,2003: 1073-1083.

[3] Kumar S, Lai T H, and Balogh J. On k-coverage in a mostly sleeping sensor network[C]. Proceedings of ACM MOBICOM’04, Philadelphia, PA, USA, Sept. 26 - Oct. 1,2004: 144-158.

[4] Ram S S, Manjunath D, Iyer S K, and Yogeshwaran D. On the path coverage properties of random sensor networks[J].IEEE Transactions on Mobile Computing, 2007, 6(5):494-506.

[5] Manohar P, Ram S S, and Manjunath D. Path coverage by a sensor field: the nonhomogeneous case[J]. ACM Transactions on Sensor Networks, 2009, 5(2): 1-26.

[6] Harada J, Shioda S, and Saito H. Path coverage property of randomly deployed sensor networks with nite communication ranges[C]. Proceedings of IEEE ICC’08,Beijing, China, May 19-23, 2008: 2221-2227.

[7] Goldenberg D K, Bihler P, and Cao M, et al.. Localization in sparse networks using sweeps[C]. Proceedings of ACM MOBICOM’06, Los Angeles, CA, USA, Sep. 23-29, 2006:110-121.

[8] Sheu J, Hu W, and Lin J. Distributed localization scheme for mobile sensor networks[J]. IEEE Transactions on Mobile Computing, 2010, 9(4): 516-526.

[9] Kumar S, Lai T H, and Arora A. Barrier coverage with wireless sensors[C]. Proceedings of ACM MOBICOM’05,Cologne, Germany, Aug. 28-Sept. 2, 2005: 284-298.

[10] Saipulla A, Westphal C, Liu B, and Wang J. Barrier coverage of line-based deployed wireless sensor networks[C].Proceedings of IEEE INFOCOM’09, Rio de Janeiro, Brizil,Apr. 19-25, 2009: 127-135.

[11] Meester R and Roy R. Continuum Percolation[M].Cambridge: Cambridge University Press, 1996: 31-34.