郭新明，陳 偉，謝 飛，李 康

(1．咸陽(yáng)師范學(xué)院 計(jì)算機(jī)學(xué)院，陜西 咸陽(yáng) 712000；2.西安電子科技大學(xué) 前沿交叉研究院，陜西 西安 710068)

0 引 言

隨著網(wǎng)絡(luò)技術(shù)、傳感器技術(shù)、微電子等技術(shù)的不斷發(fā)展，無(wú)線傳感器網(wǎng)絡(luò)(wireless sensor networks，WSNs)技術(shù)及其應(yīng)用已經(jīng)成為目前的研究熱點(diǎn)，柵欄覆蓋是WSNs覆蓋技術(shù)中一個(gè)重要研究方向，該技術(shù)重點(diǎn)關(guān)注如何能有效監(jiān)測(cè)穿越WSNs覆蓋區(qū)域的入侵對(duì)象[1]。柵欄覆蓋技術(shù)如今已經(jīng)被廣泛地應(yīng)用到工業(yè)控制、智慧農(nóng)業(yè)、安保防御及軍事監(jiān)測(cè)等范疇。柵欄覆蓋的概念是由Gage在機(jī)器人領(lǐng)域首次提出的[2]，Kumar S等人首次將柵欄覆蓋分為強(qiáng)柵欄和弱柵欄兩種覆蓋方式[3]。柵欄覆蓋研究中強(qiáng)柵欄覆蓋[4～9]和弱柵欄覆蓋[10～13]均取得了一些研究成果。文獻(xiàn)[14]將Voronoi圖引入WSNs柵欄覆蓋的研究中，通過(guò)對(duì)監(jiān)測(cè)區(qū)域進(jìn)行Voronoi劃分，實(shí)現(xiàn)WSNs中覆蓋漏洞的快速查找。文獻(xiàn)[15]針對(duì)高效節(jié)能的柵欄漏洞修復(fù)問(wèn)題進(jìn)行研究，通過(guò)建立靜止節(jié)點(diǎn)的權(quán)重圖，再利用迪杰斯特拉算法尋找所需最少數(shù)目的移動(dòng)節(jié)點(diǎn)和構(gòu)建柵欄覆蓋的最短路徑，算法明顯減少了移動(dòng)節(jié)點(diǎn)的移動(dòng)距離，實(shí)現(xiàn)了高效的柵欄覆蓋。為了實(shí)現(xiàn)對(duì)被監(jiān)測(cè)區(qū)域的全方位覆蓋，以及能夠捕捉到進(jìn)入該區(qū)域目標(biāo)的有效信息,文獻(xiàn)[16]提出了一種基于異構(gòu)節(jié)點(diǎn)的全視角強(qiáng)柵欄覆蓋模型，借助紅外線傳感器輔助相機(jī)傳感器節(jié)點(diǎn)完成對(duì)指定區(qū)域的監(jiān)測(cè)。采用分治策略和喚醒機(jī)制有效延長(zhǎng)了網(wǎng)絡(luò)的生命周期。

以上有關(guān)柵欄覆蓋的研究均是在帶狀區(qū)域中實(shí)現(xiàn)柵欄構(gòu)建的，但在實(shí)際應(yīng)用中發(fā)現(xiàn)監(jiān)測(cè)區(qū)域不完全是帶狀的，如監(jiān)測(cè)野生動(dòng)物是否進(jìn)入投飼點(diǎn)，由于無(wú)法確定野生動(dòng)物進(jìn)入投飼點(diǎn)的方向，因此需在投飼點(diǎn)周圍建立環(huán)狀柵欄。

針對(duì)WSNs的山地三維環(huán)狀柵欄構(gòu)建問(wèn)題，本文提出一種基于等位區(qū)域的環(huán)狀柵欄構(gòu)建算法，算法能夠?qū)⒉渴鹪谏襟w上的WSNs劃分為多個(gè)等位區(qū)域，并在每個(gè)等位區(qū)域中構(gòu)建一條柵欄，形成了以山頂為中心的三維多重環(huán)狀柵欄，從而實(shí)現(xiàn)山地中移動(dòng)目標(biāo)軌跡的有效追蹤。

1 模型構(gòu)建與問(wèn)題概述

1.1 山地三維柵欄覆蓋問(wèn)題概述

傳統(tǒng)的柵欄覆蓋主要在二維空間中進(jìn)行柵欄構(gòu)建，但隨著WSNs應(yīng)用范圍的不斷拓展，許多應(yīng)用要求在三維環(huán)境下實(shí)現(xiàn)柵欄覆蓋，比如在山區(qū)進(jìn)行野生動(dòng)物監(jiān)測(cè)和保護(hù)。由于山區(qū)地表高度落差較大，二維空間的柵欄覆蓋技術(shù)已經(jīng)不能滿足這種復(fù)雜地貌中的數(shù)據(jù)采集需求，因此需要研究三維空間中的無(wú)線網(wǎng)絡(luò)柵欄覆蓋問(wèn)題，從而有效提高復(fù)雜地貌環(huán)境下移動(dòng)目標(biāo)的監(jiān)測(cè)質(zhì)量。

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

本文的仿真平臺(tái)是一個(gè)規(guī)整的山體模型，其縱剖面是一個(gè)正態(tài)分布函數(shù)，如式(1)所示，其中σ=1.2

(1)

在上述的山體模型表面隨機(jī)部署n個(gè)無(wú)線傳感器節(jié)點(diǎn)，所有無(wú)線節(jié)點(diǎn)同構(gòu)，且部署后位置不再變化，如圖1所示。

圖1 基于正態(tài)分布函數(shù)的山體模型

WSNs節(jié)點(diǎn)的感知模型可用一個(gè)二元組〈Pi，r〉表示，其中Pi=(xi，yi，zi)表示其在山體表面的位置；r為無(wú)線節(jié)點(diǎn)的最大感知半徑，若移動(dòng)目標(biāo)與Pi的距離小于r，則其即可被無(wú)線節(jié)點(diǎn)感知，否則不能被感知，如圖2所示。

圖2 傳感器節(jié)點(diǎn)的三維感知模型

1.3 有關(guān)定義

定義1等位區(qū)域：山體表面高度在[a,b)范圍內(nèi)的環(huán)狀區(qū)域，被稱為一個(gè)等位區(qū)域，其中a為高度下限，b為高度上限，如圖3中陰影部分所示。

圖3 山體等位區(qū)域示意

定義2鄰居節(jié)點(diǎn)：在一個(gè)等位區(qū)域中，如果節(jié)點(diǎn)b是節(jié)點(diǎn)a的鄰居節(jié)點(diǎn)，那么應(yīng)滿足以下條件：1)節(jié)點(diǎn)b與節(jié)點(diǎn)a均應(yīng)位于同一等位區(qū)域中；2)節(jié)點(diǎn)b與節(jié)點(diǎn)a的距離應(yīng)小于或等于2r；3)節(jié)點(diǎn)b應(yīng)出現(xiàn)在節(jié)點(diǎn)a的順時(shí)針?lè)较蛏稀?/p>

如圖4所示，凡是出現(xiàn)在陰影部分的節(jié)點(diǎn)均是節(jié)點(diǎn)a的鄰居節(jié)點(diǎn)。

圖4 鄰居節(jié)點(diǎn)示意

定義3無(wú)線節(jié)點(diǎn)對(duì)：如果節(jié)點(diǎn)b是節(jié)點(diǎn)a的鄰居節(jié)點(diǎn)，則稱節(jié)點(diǎn)a和節(jié)點(diǎn)b是一個(gè)無(wú)線節(jié)點(diǎn)對(duì)，a稱為頭節(jié)點(diǎn)，b稱為尾節(jié)點(diǎn)。

定義4環(huán)狀柵欄：在一個(gè)等位區(qū)域中，由多個(gè)互為鄰居節(jié)點(diǎn)的無(wú)線節(jié)點(diǎn)對(duì)依次首尾相接形成的封閉的環(huán)路稱為一條環(huán)狀柵欄。

2 山地三維環(huán)狀柵欄覆蓋算法設(shè)計(jì)

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

帶狀區(qū)域中構(gòu)造的柵欄不封閉，因此在無(wú)屏障可依時(shí)，柵欄兩端間的空白區(qū)域?qū)⒊蔀闊o(wú)法檢測(cè)到移動(dòng)目標(biāo)的漏洞。這種現(xiàn)象在自然環(huán)境中表現(xiàn)得尤為突出，例如在野外補(bǔ)飼點(diǎn)周圍構(gòu)建的柵欄如果不封閉，那么就存在遺漏監(jiān)測(cè)到野生動(dòng)物的可能，如圖5所示。

圖5 帶狀柵欄漏洞示意

山地三維環(huán)狀柵欄覆蓋算法首先在山體模型上隨機(jī)部署n個(gè)無(wú)線傳感器節(jié)點(diǎn)，再將山體按照不同的高度范圍劃分成多個(gè)等位區(qū)域，然后運(yùn)用弗洛伊德算法[17]在每個(gè)等位區(qū)域的無(wú)線網(wǎng)絡(luò)中至少找到一條環(huán)狀柵欄，最終實(shí)現(xiàn)對(duì)山體的三維環(huán)狀柵欄覆蓋。

2.2 山地三維環(huán)狀柵欄覆蓋算法

算法的具體步驟如下：

步驟1 將山體表面從山腳到山頂每隔高度d劃分一個(gè)等位區(qū)域。

步驟2 按照定義2建立每個(gè)等位區(qū)域中無(wú)線傳感器網(wǎng)絡(luò)的鄰接矩陣。

步驟3 遍歷所有等位區(qū)域，找到一個(gè)未訪問(wèn)過(guò)的等位區(qū)域執(zhí)行步驟4，否則執(zhí)行步驟7。

步驟4 在該等位區(qū)域中查找一組未使用過(guò)的無(wú)線節(jié)點(diǎn)對(duì)執(zhí)行步驟5，否則執(zhí)行步驟3。

步驟5 以無(wú)線節(jié)點(diǎn)對(duì)的尾節(jié)點(diǎn)為起點(diǎn)，頭節(jié)點(diǎn)為終點(diǎn)，采用弗洛伊德算法在該等位區(qū)域的無(wú)線網(wǎng)絡(luò)中搜索最短路徑，如果最短路徑存在，則執(zhí)行步驟6，否則執(zhí)行步驟4。

步驟6 將步驟5中求得的最短路徑首尾相接形成環(huán)路并存入環(huán)狀柵欄集，執(zhí)行步驟3。

步驟7 返回環(huán)狀柵欄集。

3 仿真實(shí)驗(yàn)與數(shù)據(jù)分析

3.1 實(shí)驗(yàn)平臺(tái)構(gòu)建

本文的仿真平臺(tái)使用Eclipse4.9進(jìn)行構(gòu)建，實(shí)驗(yàn)環(huán)境是一個(gè)底面為700 m×700 m,高為400 m的山體模型，在山體表面部署若干無(wú)線傳感器節(jié)點(diǎn)，每個(gè)傳感器節(jié)點(diǎn)的傳感半徑r=100 m，山體表面按照從山腳起每上升100 m劃分一個(gè)等位區(qū)域。圖6為山體表面無(wú)線網(wǎng)絡(luò)按照等位區(qū)域劃分后的鄰接關(guān)系俯視圖。

圖6 山體等位區(qū)域WSNs鄰接關(guān)系示意

3.2 算法仿真實(shí)驗(yàn)

仿真實(shí)驗(yàn)結(jié)果顯示，山體環(huán)狀柵欄的形成效果直接受網(wǎng)絡(luò)節(jié)點(diǎn)部署密度的影響。如圖7中分別顯示的是在山體上部署了80個(gè)和160個(gè)無(wú)線傳感器節(jié)點(diǎn)形成的環(huán)形柵欄效果圖。

圖7 山體表面環(huán)狀柵欄仿真效果俯視圖

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

由實(shí)驗(yàn)數(shù)據(jù)分析可知，在山體表面的WSNs中構(gòu)造環(huán)狀柵欄覆蓋，無(wú)論是形成環(huán)狀柵欄的節(jié)點(diǎn)個(gè)數(shù)還是環(huán)狀柵欄的長(zhǎng)度，均隨著部署在山體表面無(wú)線節(jié)點(diǎn)個(gè)數(shù)的增加而增加。如果山體表面無(wú)線節(jié)點(diǎn)個(gè)數(shù)保持不變，若將無(wú)線節(jié)點(diǎn)對(duì)間的距離定義為1，所形成的環(huán)狀柵欄的節(jié)點(diǎn)個(gè)數(shù)要遠(yuǎn)遠(yuǎn)小于無(wú)線節(jié)點(diǎn)對(duì)間距離為實(shí)際距離的情況，但柵欄長(zhǎng)度卻大于無(wú)線節(jié)點(diǎn)對(duì)間距離為實(shí)際距離的情況。實(shí)驗(yàn)數(shù)據(jù)分析結(jié)果如圖8、圖9所示。

圖8 生成環(huán)狀柵欄的節(jié)點(diǎn)數(shù)與部署節(jié)點(diǎn)數(shù)關(guān)系

圖9 生成環(huán)狀柵欄的長(zhǎng)度與部署節(jié)點(diǎn)數(shù)關(guān)系

4 結(jié)束語(yǔ)

本文針對(duì)WSNs山地三維柵欄構(gòu)建問(wèn)題，提出了一種基于等位區(qū)域的環(huán)狀柵欄構(gòu)建算法。從實(shí)驗(yàn)數(shù)據(jù)分析表明：形成環(huán)狀柵欄的節(jié)點(diǎn)個(gè)數(shù)和環(huán)狀柵欄長(zhǎng)度均會(huì)隨著無(wú)線節(jié)點(diǎn)部署密度的增大而增加。在山體表面無(wú)線節(jié)點(diǎn)密度不變的情況下，若只考慮無(wú)線節(jié)點(diǎn)間的可達(dá)性，則所形成的環(huán)狀柵欄的節(jié)點(diǎn)個(gè)數(shù)要遠(yuǎn)遠(yuǎn)小于無(wú)線節(jié)點(diǎn)對(duì)間距離為實(shí)際距離的情況，但柵欄長(zhǎng)度卻大于無(wú)線節(jié)點(diǎn)對(duì)間距離為實(shí)際距離的情況。該算法能夠在三維空間的山體表面形成環(huán)狀柵欄覆蓋，有效地解決了山地表面高度落差大，傳統(tǒng)的柵欄覆蓋技術(shù)數(shù)據(jù)采集困難的問(wèn)題，從而有效提高了復(fù)雜地貌環(huán)境下移動(dòng)目標(biāo)的監(jiān)測(cè)和軌跡追蹤質(zhì)量。