有向無(wú)線傳感器網(wǎng)絡(luò)弱柵欄覆蓋構(gòu)建算法設(shè)計(jì)

郭新明，李 康，陳 偉，賈 浩

（咸陽(yáng)師范學(xué)院 計(jì)算機(jī)學(xué)院，陜西 咸陽(yáng) 712000）

隨著傳感技術(shù)的不斷進(jìn)步，無(wú)線傳感器網(wǎng)絡(luò)已經(jīng)成為當(dāng)前的一個(gè)研究熱點(diǎn)。無(wú)線傳感器網(wǎng)絡(luò)柵欄覆蓋技術(shù)是其中一個(gè)重要的研究方向，目前已經(jīng)被廣泛應(yīng)用到軍事、國(guó)防、工業(yè)、農(nóng)業(yè)等領(lǐng)域[1]。柵欄覆蓋是由Gage首次在機(jī)器人研究領(lǐng)域提出來(lái)的[2]，Kumar等首次給出了強(qiáng)柵欄和弱柵欄的定義，并設(shè)計(jì)了一個(gè)判定監(jiān)測(cè)區(qū)域是否被k條柵欄覆蓋的算法[3]。有關(guān)柵欄覆蓋的研究中，強(qiáng)柵欄覆蓋已經(jīng)取得了許多研究成果[4-7]，而弱柵欄覆蓋的研究成果相對(duì)較少[8]。弱柵欄覆蓋關(guān)注移動(dòng)目標(biāo)沿垂直于帶狀區(qū)域的路徑穿越時(shí)能否被監(jiān)測(cè)到，在實(shí)際應(yīng)用中，可利用較少的節(jié)點(diǎn)構(gòu)建柵欄，大大減少網(wǎng)絡(luò)冗余和節(jié)點(diǎn)能耗[3]。有向傳感網(wǎng)絡(luò)由于對(duì)環(huán)境數(shù)據(jù)的感知受“視域（field of view，簡(jiǎn)稱FOV）”的限制，具有方向特性，所形成的感知范圍是以節(jié)點(diǎn)為圓心，其感知距離為半徑的扇形區(qū)域[9]。有向傳感器網(wǎng)絡(luò)柵欄覆蓋研究依然存在強(qiáng)柵欄和弱柵欄兩種覆蓋方式，文獻(xiàn)[9-11]均針對(duì)有向傳感器網(wǎng)絡(luò)強(qiáng)柵欄覆蓋進(jìn)行研究，而有向傳感器網(wǎng)絡(luò)弱柵欄覆蓋方面的研究依然較少。

針對(duì)有向無(wú)線傳感器網(wǎng)絡(luò)的弱柵欄覆蓋問(wèn)題，本文提出了一種基于有向無(wú)線傳感器投影的弱柵欄構(gòu)建算法，該算法能夠?qū)崿F(xiàn)監(jiān)控區(qū)域的弱柵欄覆蓋，從而實(shí)現(xiàn)對(duì)監(jiān)測(cè)區(qū)域中移動(dòng)目標(biāo)的有效追蹤。

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

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

本文的監(jiān)測(cè)區(qū)域是一個(gè)長(zhǎng)L寬W的矩形區(qū)域，并在其中隨機(jī)部署N個(gè)傳感器節(jié)點(diǎn)，節(jié)點(diǎn)的坐標(biāo)可以用（x，y）來(lái)表示其在矩形區(qū)域中的相對(duì)位置，并且節(jié)點(diǎn)在部署后位置不改變。

定義1有向無(wú)線傳感器節(jié)點(diǎn)感知模型：一般采用四元組＜L，r，V，β＞表示，其中 L=（x ，y）表示傳感器節(jié)點(diǎn)的位置坐標(biāo)；r為節(jié)點(diǎn)的最大感知半徑；單位向量V為節(jié)點(diǎn)的感知方向，是扇形感知區(qū)域的中軸線；β為感知夾角，即邊界偏移感知向量V的角度；2β是感知區(qū)域的視角，通常記為FOV，α為扇形感知區(qū)域的起始角度，結(jié)構(gòu)如圖1所示。

圖1 有向傳感器節(jié)點(diǎn)感知模型

定義2有向無(wú)線傳感器弱柵欄路徑：是監(jiān)測(cè)區(qū)域中的一個(gè)節(jié)點(diǎn)集，若移動(dòng)目標(biāo)沿任意垂直于監(jiān)測(cè)區(qū)域的方向穿越該區(qū)域時(shí)，都會(huì)被該集合中至少一個(gè)有向無(wú)線傳感器節(jié)點(diǎn)監(jiān)測(cè)到。有向無(wú)線傳感器弱柵欄路徑如圖2所示，每個(gè)傳感器節(jié)點(diǎn)的FOV=60°。

定義3邊界節(jié)點(diǎn)：覆蓋區(qū)域與監(jiān)測(cè)區(qū)域左邊界相交的有向無(wú)線傳感器節(jié)點(diǎn)稱為該監(jiān)測(cè)區(qū)域的左邊界節(jié)點(diǎn)，覆蓋區(qū)域與監(jiān)測(cè)區(qū)域右邊界相交的有向無(wú)線傳感器節(jié)點(diǎn)稱為該監(jiān)測(cè)區(qū)域的右邊界節(jié)點(diǎn)。

定義4弱柵欄集合：構(gòu)成一條弱柵欄的所有有向無(wú)線傳感器節(jié)點(diǎn)，稱為弱柵欄集合。

圖2 FOV=60°的弱柵欄部署圖

1.2 有向無(wú)線傳感器網(wǎng)絡(luò)弱柵欄覆蓋問(wèn)題

有向無(wú)線傳感器網(wǎng)絡(luò)弱柵欄覆蓋問(wèn)題是針對(duì)無(wú)線傳感器網(wǎng)絡(luò)中節(jié)點(diǎn)覆蓋密度較低或盡可能延長(zhǎng)網(wǎng)絡(luò)生命周期的情況下，實(shí)現(xiàn)對(duì)監(jiān)測(cè)區(qū)域中移動(dòng)目標(biāo)有效追蹤的一種監(jiān)控策略。有向無(wú)線傳感器網(wǎng)絡(luò)弱柵欄覆蓋既降低了網(wǎng)絡(luò)能耗又避免了因網(wǎng)絡(luò)中節(jié)點(diǎn)部署不均而造成強(qiáng)柵欄構(gòu)建受限的缺陷，是一種靈活高效的覆蓋策略。本文提出的基于有向無(wú)線傳感器節(jié)點(diǎn)投影的弱柵欄構(gòu)建算法，旨在依靠投影的連通性構(gòu)建有向無(wú)線傳感器網(wǎng)絡(luò)弱柵欄，進(jìn)而實(shí)現(xiàn)對(duì)監(jiān)測(cè)區(qū)域中移動(dòng)目標(biāo)的有效追蹤。

2 有向無(wú)線傳感器網(wǎng)絡(luò)弱柵欄覆蓋算法

2.1 算法的設(shè)計(jì)思想

要在有向無(wú)線傳感器網(wǎng)絡(luò)中實(shí)現(xiàn)弱柵欄覆蓋，首先應(yīng)該獲得每個(gè)有向無(wú)線傳感器的覆蓋范圍在直角坐標(biāo)系中的投影，再根據(jù)有向無(wú)線傳感器投影間的重合關(guān)系建立弱柵欄，弱柵欄覆蓋不要求節(jié)點(diǎn)的覆蓋區(qū)域相互重疊，只需弱柵欄集合中所有節(jié)點(diǎn)覆蓋區(qū)域的投影相互重疊即可。有向無(wú)線傳感器的投影因其起始角度的不同而變化，可將其分為如下4種情況，如圖3所示。

用p表示有向無(wú)線傳感器投影的長(zhǎng)度。情況1，如圖3（a）所示，投影為式（1）。

情況2，如圖3（b）所示，投影為式（2）。

圖3 有向無(wú)線傳感器節(jié)點(diǎn)投影示意圖

情況3，如圖3（c）所示，投影為式（3）。

1）在梨小食心蟲(chóng)越冬前，樹(shù)干綁誘蟲(chóng)帶，誘集幼蟲(chóng)越冬，冬末解除集中燒毀。春季越冬幼蟲(chóng)化蛹羽化前，刮除樹(shù)干老翹皮，消滅根頸周圍土壤中的越冬代幼蟲(chóng)。

情況4，如圖3（d）所示，投影為式（4）。

2.2 弱柵欄構(gòu)建算法

本算法以有向無(wú)線傳感器節(jié)點(diǎn)在直角坐標(biāo)系中的投影為依據(jù)，利用Floyd算法計(jì)算監(jiān)測(cè)區(qū)域左右邊界節(jié)點(diǎn)間的最短弱柵欄，算法描述如下：

步驟1遍歷監(jiān)測(cè)區(qū)域中的節(jié)點(diǎn)，將監(jiān)測(cè)區(qū)域左右邊界節(jié)點(diǎn)分別放入LeftNode和RightNode集合中。

步驟2遍歷監(jiān)測(cè)區(qū)域中的節(jié)點(diǎn)，計(jì)算節(jié)點(diǎn)的投影長(zhǎng)度和起始位置。

步驟3遍歷監(jiān)測(cè)區(qū)域中的節(jié)點(diǎn)，依據(jù)節(jié)點(diǎn)投影間的垂直重合關(guān)系，建立網(wǎng)絡(luò)的鄰接矩陣。

步驟4若LeftNode和RightNode集合均不為空，且其中存在未遍歷節(jié)點(diǎn)，執(zhí)行步驟5，否則執(zhí)行步驟7。

步驟5從監(jiān)測(cè)區(qū)域左右邊界節(jié)點(diǎn)集LeftNode和RightNode中分別取一個(gè)未遍歷的節(jié)點(diǎn)作為起始和結(jié)束節(jié)點(diǎn)，利用Floyd算法在網(wǎng)絡(luò)的可用節(jié)點(diǎn)中計(jì)算最短路徑，若得到最短路徑，執(zhí)行步驟6，否則執(zhí)行步驟4。

步驟7輸出最短路徑集ShortestPath中的所有路徑，算法結(jié)束。

3 實(shí)驗(yàn)與分析

3.1 實(shí)驗(yàn)平臺(tái)的搭建

仿真實(shí)驗(yàn)平臺(tái)使用Eclipse開(kāi)發(fā)工具進(jìn)行搭建，實(shí)驗(yàn)環(huán)境為一個(gè)800 m×200 m的矩形區(qū)域，內(nèi)部部署若干個(gè)夾角60°、半徑為50 m的有向傳感器節(jié)點(diǎn)，節(jié)點(diǎn)的傳感方向和位置均隨機(jī)分布，如圖4所示。

圖4 仿真實(shí)驗(yàn)平臺(tái)效果圖

3.2 算法實(shí)現(xiàn)

在監(jiān)測(cè)區(qū)域的矩形范圍內(nèi)，隨機(jī)部署若干節(jié)點(diǎn)，根據(jù)部署節(jié)點(diǎn)個(gè)數(shù)的不同，構(gòu)建出不同數(shù)量的弱柵欄覆蓋，算法實(shí)驗(yàn)的結(jié)果如圖5-7所示（說(shuō)明：黑色扇形代表當(dāng)前已經(jīng)構(gòu)建好的弱柵欄，加粗黑色直線表示構(gòu)建好的弱柵欄中相應(yīng)節(jié)點(diǎn)的投影）。

圖5 部署90個(gè)無(wú)線節(jié)點(diǎn)的弱柵欄覆蓋構(gòu)建效果圖

圖6 部署120個(gè)無(wú)線節(jié)點(diǎn)的弱柵欄覆蓋構(gòu)建效果圖

圖7 部署150個(gè)無(wú)線節(jié)點(diǎn)的弱柵欄覆蓋構(gòu)建效果圖

3.3 實(shí)驗(yàn)數(shù)據(jù)分析

根據(jù)實(shí)驗(yàn)數(shù)據(jù)顯示，當(dāng)部署節(jié)點(diǎn)為90時(shí)，構(gòu)建的弱柵欄有1條，柵欄節(jié)點(diǎn)數(shù)目為21個(gè)；當(dāng)部署節(jié)點(diǎn)為120時(shí)，構(gòu)建的弱柵欄有2條，柵欄節(jié)點(diǎn)數(shù)目分別為20個(gè)和19個(gè)；當(dāng)部署節(jié)點(diǎn)為150時(shí)，構(gòu)建的弱柵欄有3條，柵欄節(jié)點(diǎn)數(shù)目分別為19、20和20。由此可知，節(jié)點(diǎn)數(shù)密集時(shí)，會(huì)增加構(gòu)建的弱柵欄數(shù)，但是構(gòu)成柵欄節(jié)點(diǎn)的數(shù)目沒(méi)有明顯變化。

從實(shí)驗(yàn)結(jié)果可以看出，有向無(wú)線傳感器節(jié)點(diǎn)部署的密度越大，構(gòu)建的弱柵欄數(shù)量就越多，形成弱柵欄的節(jié)點(diǎn)平均數(shù)目也相對(duì)減少。

4 結(jié)語(yǔ)

隨著傳感器技術(shù)的不斷發(fā)展，有向傳感器網(wǎng)絡(luò)已經(jīng)逐漸走進(jìn)人們的生活，如城市中的攝像頭，通過(guò)有向感知實(shí)現(xiàn)環(huán)境監(jiān)測(cè)。本文針對(duì)有向無(wú)線傳感器網(wǎng)絡(luò)的弱柵欄覆蓋問(wèn)題，提出了一種基于有向無(wú)線傳感器投影的弱柵欄構(gòu)建算法。實(shí)驗(yàn)結(jié)果顯示，隨著網(wǎng)絡(luò)中部署節(jié)點(diǎn)的增多，形成的弱柵欄數(shù)量也會(huì)隨之增加。該算法能夠?qū)崿F(xiàn)監(jiān)控區(qū)域的弱柵欄覆蓋，進(jìn)而實(shí)現(xiàn)對(duì)監(jiān)測(cè)區(qū)域入侵對(duì)象的有效追蹤，但是在節(jié)點(diǎn)性能優(yōu)化方面還需要進(jìn)一步研究。