無(wú)線傳感器網(wǎng)絡(luò)多柵欄覆蓋構(gòu)建算法研究*

楊 濤，慕德俊

(西北工業(yè)大學(xué)自動(dòng)化學(xué)院，西安 710072)

0 引言

覆蓋問(wèn)題是無(wú)線傳感器網(wǎng)絡(luò)配置首先面臨的基本問(wèn)題，它決定著一個(gè)無(wú)線傳感器網(wǎng)絡(luò)的工作性能。柵欄覆蓋較全覆蓋模型，更加符合實(shí)際應(yīng)用中長(zhǎng)時(shí)間、無(wú)間斷工作的需要，已成為無(wú)線傳感器網(wǎng)絡(luò)的研究熱點(diǎn)之一[1－3]。

已有工作主要基于隨機(jī)部署的靜態(tài)傳感器網(wǎng)絡(luò)對(duì)監(jiān)控區(qū)域?qū)嵤﹩螙艡诟采w，存在兩個(gè)問(wèn)題：1)由于部署的隨機(jī)性，傳感器網(wǎng)絡(luò)中可能存在空隙，或隨著時(shí)間延續(xù)，網(wǎng)絡(luò)中出現(xiàn)死節(jié)點(diǎn)的弱區(qū)域，使得入侵者可能通過(guò)監(jiān)控區(qū)域而不被檢測(cè)到;2)隨機(jī)部署時(shí)，監(jiān)控區(qū)域內(nèi)會(huì)散布大量節(jié)點(diǎn)，而單柵欄覆蓋只選取其中一部分，這就造成節(jié)點(diǎn)冗余浪費(fèi)。

文中針對(duì)帶狀監(jiān)控區(qū)域內(nèi)隨機(jī)部署的無(wú)線傳感器網(wǎng)絡(luò)，研究如何通過(guò)分治算法高效的構(gòu)建k－覆蓋的問(wèn)題。主要研究工作包括：1)形式化定義了傳感器節(jié)點(diǎn)k－覆蓋的條件，確保在監(jiān)控區(qū)域中，入侵者穿越路徑至少被一個(gè)傳感器節(jié)點(diǎn)覆蓋;2)提出了區(qū)域多柵欄覆蓋構(gòu)建算法DPA。實(shí)驗(yàn)表明該算法與傳統(tǒng)的多邊形柵欄構(gòu)筑算法相比，構(gòu)筑柵欄數(shù)目超出30%，并降低了通信開銷和計(jì)算復(fù)雜度，延長(zhǎng)了網(wǎng)絡(luò)的工作壽命。

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

1.1 網(wǎng)絡(luò)模型

傳感器網(wǎng)絡(luò)N，是一組傳感器節(jié)點(diǎn)的集合，它們被隨機(jī)布置于大小為A的二維模型環(huán)境中，假設(shè)這個(gè)二維環(huán)境是一個(gè)帶狀區(qū)域，這個(gè)帶狀區(qū)域有4條邊界，兩條水平的，兩條豎直的，其中寬度為w，長(zhǎng)度為l，A2d=l×w，見圖1，則可以假設(shè)每個(gè)傳感器節(jié)點(diǎn)隨機(jī)泊松分布在區(qū)域A中，設(shè)數(shù)量為N(A)的傳感器以參數(shù)為na分布，則得到：

圖1 傳感器部署帶狀區(qū)域

用u來(lái)代表一個(gè)傳感器節(jié)點(diǎn)，設(shè)每一個(gè)傳感器節(jié)點(diǎn)的感應(yīng)半徑為rs，當(dāng)傳感器節(jié)點(diǎn)u與監(jiān)測(cè)區(qū)域的任意點(diǎn)p的歐式距離小于傳感半徑rs時(shí)，則點(diǎn)p被覆蓋。

1.2 問(wèn)題描述

監(jiān)測(cè)的帶狀區(qū)域的每一個(gè)點(diǎn)都被覆蓋的模型叫做全覆蓋模型。在帶狀區(qū)域中，僅在水平方向部署傳感器的模型叫做柵欄覆蓋模型。當(dāng)入侵者的入侵軌跡經(jīng)過(guò)k個(gè)傳感器節(jié)點(diǎn)感應(yīng)區(qū)域時(shí)，稱之為k－覆蓋。一個(gè)覆蓋區(qū)域的所有入侵路徑都最少經(jīng)過(guò)k個(gè)傳感器節(jié)點(diǎn)的感應(yīng)區(qū)域，就稱該覆蓋支持k－覆蓋。如圖2所示。

圖2 覆蓋模型

圖3 帶狀區(qū)域沒(méi)有被柵欄覆蓋因?yàn)榇嬖谝粭l無(wú)覆蓋突破路徑

在文獻(xiàn)[1]中發(fā)現(xiàn)柵欄覆蓋對(duì)于全覆蓋有一定的局限性，例如，在一段長(zhǎng)約500km，寬度為50m的帶狀區(qū)域中，通過(guò)全局柵欄覆蓋定義，仍存在一條近似于帶狀區(qū)域?qū)挾鹊臒o(wú)覆蓋穿越路徑，稱之為突破路徑，如圖3所示。

Ai等人提出L本地化柵欄覆蓋的概念用于解決此問(wèn)題，將帶狀區(qū)域分成若干長(zhǎng)度為L(zhǎng)的片段，每一個(gè)L長(zhǎng)度片段內(nèi)實(shí)現(xiàn)柵欄覆蓋，則該片段內(nèi)的每一條路徑就實(shí)現(xiàn)了覆蓋[4]。Liu.等人提出強(qiáng)柵欄覆蓋的概念解決此問(wèn)題，提出了在帶狀區(qū)域的豎直方向上建立柵欄，保證每一條路徑在穿越時(shí)都至少經(jīng)過(guò)一條豎直方向的柵欄，這樣就實(shí)現(xiàn)了所有穿越路徑的柵欄覆蓋[5]。

這兩種方法在一定程度上都能解決這個(gè)問(wèn)題，但本地化的算法對(duì)傳感器能量消耗過(guò)大，不利于延長(zhǎng)網(wǎng)絡(luò)壽命。在豎直方向上建立柵欄的強(qiáng)柵欄覆蓋又不能保證豎直柵欄正好建立在兩個(gè)漏洞點(diǎn)中間。所以文中將提出利用多柵欄構(gòu)筑算法實(shí)現(xiàn)多柵欄切換，加強(qiáng)覆蓋質(zhì)量的方法。

2 柵欄覆蓋的基本條件

一般無(wú)線傳感器網(wǎng)絡(luò)的配置是由飛機(jī)等在空中隨機(jī)播撒傳感器節(jié)點(diǎn)，所有的傳感器節(jié)點(diǎn)就會(huì)在帶狀監(jiān)測(cè)區(qū)域內(nèi)部的一條線段上隨機(jī)分布。假設(shè)這個(gè)線段為[0，L]，把它分為N個(gè)片段，每一個(gè)片段的長(zhǎng)度為傳感器感應(yīng)半徑的兩倍2rs，即N=L/2rs。

在兩個(gè)相鄰的片段i和i+1中，片段i中的最右端節(jié)點(diǎn)A的位置為X1，片段i+1中的最左端節(jié)點(diǎn)B的位置為X2，需要以下條件保證傳感器全覆蓋，如圖4所示。

1)每個(gè)長(zhǎng)度為2rs的片段內(nèi)都必須有一個(gè)傳感器節(jié)點(diǎn)u。

2)當(dāng)相鄰傳感器節(jié)點(diǎn)距離大于等于兩個(gè)感應(yīng)半徑即2rs≤X2－ X1＜ 3rs時(shí)，在[X1+rs，X2－ rs]，即區(qū)域CD中至少有一個(gè)傳感器節(jié)點(diǎn)。

3)當(dāng)相鄰傳感器節(jié)點(diǎn)距離大于等于3倍感應(yīng)半徑即3rs≤X2－ X1＜ 4rs時(shí)，在[X1+2rs，X2－ rs]即區(qū)域FD或者[X1+rs，X2－2rs]即區(qū)域CE內(nèi)至少有一個(gè)傳感器節(jié)點(diǎn)。

圖4 片段i全覆蓋的條件(1＜i＜N)

假設(shè)BCOV(α)是該區(qū)域被覆蓋的概率，Yi代表i片段被傳感器全覆蓋，P(Yi)表示事件Yi發(fā)生的概率，當(dāng)片段長(zhǎng)度為2rs時(shí)，可以得到P(Yi|Y1∩Y2…，并且事件 Yi和Y1…Yi－2是相互獨(dú)立的。所以：

把圖4中填充區(qū)域的CE、FD分成無(wú)數(shù)個(gè)長(zhǎng)度為Δθ的小片段，無(wú)線傳感器節(jié)點(diǎn)以參數(shù)為λ的泊松分布配置在區(qū)域中，由離散逼近可以得到：

將式(3)～式(5)代入式(2)就可以得到P(Y1∩Y2…∩YN)的值。

3 多柵欄構(gòu)筑算法

3.1 分治算法

在滿足以上覆蓋條件的基礎(chǔ)上，就可以進(jìn)行多柵欄構(gòu)筑。同時(shí)，將覆蓋區(qū)域分為若干個(gè)小的片段區(qū)域，就可以有效降低整個(gè)網(wǎng)絡(luò)的能量開銷，增大網(wǎng)絡(luò)的使用壽命。在水平與豎直方向分別構(gòu)筑柵欄，比傳統(tǒng)的多邊形覆蓋算法(PMI)更有效。

區(qū)域分割的機(jī)制如圖5所示，先通過(guò)傳感器節(jié)點(diǎn)上的GPS模塊獲得各節(jié)點(diǎn)的地理位置信息，然后在與帶狀區(qū)域的延伸方向上選取豎直方向的傳感器節(jié)點(diǎn)，并把他們相連，形成圖6中的豎直構(gòu)筑區(qū)，該豎直構(gòu)筑區(qū)是隨機(jī)產(chǎn)生的，其余的節(jié)點(diǎn)即在水平方向上互連，形成水平構(gòu)筑區(qū)。

圖5 分離后的多柵欄覆蓋圖

3.2 DPA算法描述

由上節(jié)中討論的分治算法思想，可以知道多柵欄構(gòu)筑算法DPA在能夠獲知網(wǎng)絡(luò)全局信息的中心簇頭節(jié)點(diǎn)上運(yùn)行，中心節(jié)點(diǎn)可以通過(guò)選舉等方式確定。通過(guò)分割覆蓋區(qū)域的方式，整個(gè)網(wǎng)絡(luò)的信息延遲、通信開銷和計(jì)算消耗都明顯降低。對(duì)于連通網(wǎng)絡(luò)G(V，E)，其網(wǎng)絡(luò)開銷和構(gòu)筑柵欄的計(jì)算復(fù)雜度分別是O(|V||E|)和O(|V|3)。如果帶狀覆蓋區(qū)域被分為n個(gè)小區(qū)域，則每個(gè)區(qū)域的節(jié)點(diǎn)不多于 |v|/n，則它們的通信開銷就是O(|V|2/n2)算法復(fù)雜度為O(|V|3/n3)。

District Partition Algorithm(DPA)Require：Many Sensors are deployed in the belt region Ensure：Different barrier in the belt region，barrieri;The work time of barrieri，ti.1：Invoke the Edmond-Karp algorithm to find a maximum flow from s to t in G(N).2：Deleting all value of vertices with 0 from G(N).3：Choosing sensors from far left in the deployed belt，which means the sensors are connecting with node s.4：Connecting the neighbor sensors one by one until the sensor is connecting with node t.The neighbor sensors location must to the right of prior sensor.5：Collecting the GPS information of sensors in a barrier and calculating the average vertical value to differentiate the barriers.Then different barrier are constructed.6：Sort these barriers by descending order ofrest energy.Then get the rest energy sequence sq1，sq2...，sqi 7：We denote the work time of barrierias ti.Then t1sq1∑n i=1sqi= t2sq2∑n i=1sqi= t3sq3∑n i=1sqi=…= tisqi∑n i=1sqi If t1is the work time of barrier1，then the work time of barrier s2t2ist1sq1 sq3…8：return ti ;

4 仿真實(shí)驗(yàn)

為了驗(yàn)證上述方法的真實(shí)有效性，文中利用Matlab進(jìn)行仿真實(shí)驗(yàn)。在實(shí)驗(yàn)中，設(shè)定部署區(qū)域長(zhǎng)度為7000m，寬度為1000m。布置一定數(shù)量的傳感器節(jié)點(diǎn)，可以看到文中使用的區(qū)域分割法(DPA)構(gòu)筑柵欄比傳統(tǒng)的多邊形柵欄構(gòu)筑方式IPM更加有效。如圖6。

當(dāng)泊松分布參數(shù)由0.001到0.05。傳感器感應(yīng)半徑為100m到200m。通過(guò)仿真實(shí)驗(yàn)與式(3)～式(5)推導(dǎo)出來(lái)的結(jié)果進(jìn)行比較得出，分析公式能夠很好的指導(dǎo)實(shí)際仿真結(jié)果。實(shí)際結(jié)果如圖7所示。其中 x軸為泊松分布參 λ的值，y軸為覆蓋率。

圖6 多柵欄構(gòu)筑

圖7 泊松分布參數(shù)與覆蓋率關(guān)系圖

當(dāng)節(jié)點(diǎn)數(shù)量不斷增加時(shí)，DPA算法可以根據(jù)傳感器節(jié)點(diǎn)剩余能量決定各條柵欄的工作時(shí)長(zhǎng)，可以有效延長(zhǎng)系統(tǒng)的工作時(shí)間。圖8中的參考值是部署4500個(gè)節(jié)點(diǎn)時(shí)，傳感器網(wǎng)絡(luò)工作的時(shí)長(zhǎng)T，縱坐標(biāo)為通過(guò)DPA算法構(gòu)筑的多柵欄網(wǎng)絡(luò)的工作時(shí)長(zhǎng)與T的比率?？梢钥闯鐾ㄟ^(guò)DPA算法構(gòu)筑的多柵欄有效延長(zhǎng)了網(wǎng)絡(luò)的工作時(shí)間。

圖8 DPA構(gòu)筑多柵欄的網(wǎng)絡(luò)壽命

5 結(jié)論

柵欄覆蓋是無(wú)線傳感器網(wǎng)絡(luò)覆蓋的一種更高效的模型。已有研究工作主要針對(duì)單柵欄覆蓋。文中研究如何改進(jìn)單柵欄覆蓋的質(zhì)量，更高效的實(shí)現(xiàn)k柵欄覆蓋的問(wèn)題，提出了DPA算法。將監(jiān)控區(qū)域分割成多個(gè)子區(qū)域，分別進(jìn)行柵欄構(gòu)筑，最終連接所有區(qū)域，實(shí)現(xiàn)高效可靠的覆蓋。實(shí)驗(yàn)表明，DPA可以構(gòu)筑更多柵欄，并且可以有效的延長(zhǎng)網(wǎng)絡(luò)的工作壽命。

[1]S Kumar，T H Lai，A Arora.Barrier coverage with wireless sensors[C]//Proc.of ACM MobiCom，Cologne，2005：284－298.

[2]Bai XL，Yun ZQ，Xuan D，et al.Deploying four-connectivity and full-coverage wireless sensor networks[C]//Proc.of the IEEE INFOCOM，2008：296－300.

[3]I F Akyildiz，T Melodia，K R Chowdhury.A survey on wireless multimedia sensor networks[J]Computer Networks Journal，2007，51(4)：921－960.

[4]Ai Chen，S Kumar，T H Lai.Designing localized algorithms for barrier coverage[C]//Proc.of ACM MobiCom，2007：63－74.

[5]Liu BY，Dousse O，Wang J，et al.Strong barrier coverage of wireless sensor networks[C]//Proc.of the 9th ACM Int’l Symp.on Mobile Ad Hoc Networking and Computing(Mobihoc)，2008：411－420.

[6]Balister P，Bollobas B，Sarkar A，et al.Reliable density estimates for coverage and connectivity in thin strips of finite length[C]//Proc.of the 13th Annual ACM Int’l Conf.on Mobile Computing and Networking(MobiCom)，2007：75－86.

[7]Jren-Chit Chin，Yu Dong，Wing-Kai Hon，et al.Detection of intelligent mobile target in a mobile sensor network[J].IEEE/ACM Transactions on Networking，2010，18(1)：41－52.

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