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

李 磊 張寶賢 黃河清 劉海濤

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

1 引言

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

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

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

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

本文研究的第1個(gè)問題表述如下：

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

3 問題轉(zhuǎn)化

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

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

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

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

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

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

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

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

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

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

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

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

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

綜合以上兩點(diǎn)，該定理得以證明。 證畢

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

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

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

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

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

5 路徑k覆蓋的判定方法

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

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

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

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

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

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

6 仿真結(jié)果

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

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

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

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

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

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

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

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

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

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

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

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

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

7 結(jié)論

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

[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.