王 軍， 趙子君

(沈陽化工大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院， 遼寧 沈陽 110142)

隨著科學(xué)技術(shù)的發(fā)展和無線傳感器網(wǎng)絡(luò)(wireless sensor networks,WSNs)的普及應(yīng)用，無線傳感器網(wǎng)絡(luò)在我們的生活中扮演著越來越重要的角色[1].無線傳感器網(wǎng)絡(luò)柵欄覆蓋技術(shù)不僅應(yīng)用在海上監(jiān)測(cè)、海洋污染、森林火災(zāi)等自然災(zāi)害方面，而且在軍事、國(guó)防安全等方面具有廣泛的應(yīng)用價(jià)值[2]，能有效偵測(cè)入侵目標(biāo).通過在監(jiān)測(cè)區(qū)域內(nèi)投放大量的靜態(tài)無線傳感器節(jié)點(diǎn)可獲取實(shí)時(shí)信息，但是由于節(jié)點(diǎn)投放的隨機(jī)性導(dǎo)致監(jiān)測(cè)區(qū)域的覆蓋不均勻，無法形成有效的柵欄覆蓋，因此，設(shè)計(jì)一種移動(dòng)節(jié)點(diǎn)調(diào)度優(yōu)化方案以提高柵欄覆蓋質(zhì)量至關(guān)重要.

目前，對(duì)傳統(tǒng)無線傳感器網(wǎng)絡(luò)中的柵欄覆蓋問題已經(jīng)進(jìn)行了很多研究.1992年，Gage等人定義了柵欄覆蓋，并使移動(dòng)目標(biāo)穿越柵欄時(shí)不被發(fā)現(xiàn)的概率最低[3]；2007年Kumar等人對(duì)柵欄進(jìn)行了強(qiáng)弱的區(qū)別，提出了強(qiáng)K重柵欄覆蓋和弱K重柵欄覆蓋，并且研究了其形成柵欄時(shí)所需的最少節(jié)點(diǎn)數(shù)和相關(guān)參數(shù)[4]；2009年，Saipulla等人研究了混合無線傳感器網(wǎng)絡(luò)通過節(jié)點(diǎn)移動(dòng)判斷存在柵欄覆蓋的算法[5].

本文研究由固定節(jié)點(diǎn)和移動(dòng)節(jié)點(diǎn)共同組成混合無線傳感器網(wǎng)絡(luò)柵欄覆蓋，通過添加移動(dòng)節(jié)點(diǎn)，實(shí)現(xiàn)目標(biāo)區(qū)域的1-柵欄覆蓋，優(yōu)化無線傳感器網(wǎng)絡(luò)柵欄覆蓋策略，有效地對(duì)移動(dòng)目標(biāo)進(jìn)行檢測(cè).

1 相關(guān)問題

1.1 柵欄覆蓋

柵欄覆蓋(barrier coverage)是利用無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)布置在狹長(zhǎng)區(qū)域形成,用于監(jiān)測(cè)是否有入侵目標(biāo)穿越覆蓋區(qū)域的一種無線傳感器網(wǎng)絡(luò)覆蓋問題[6].

Meguerdichian等人提出最好情形和最壞情形的柵欄覆蓋控制算法[7-8]，算法依據(jù)Voronoi圖與Delaunay三角網(wǎng)為理論基礎(chǔ).如圖1所示，如果某入侵目標(biāo)沿著Voronoi圖的邊穿越網(wǎng)絡(luò)時(shí)，即沿著實(shí)線的SD路徑入侵時(shí)，由于路徑上的每個(gè)點(diǎn)所在的位置與最近節(jié)點(diǎn)所在位置的距離最大，因此，被監(jiān)測(cè)到的概率最小，該路徑被稱為“最大突破路徑(maximal breach path)”，由Voronoi 圖中的線段組成.對(duì)于偵察的一方，這樣的路徑就是“最壞情形的路徑”；如果路徑上的每個(gè)點(diǎn)所在的位置與最近節(jié)點(diǎn)所在位置的距離最小，則稱該路徑為“最大支撐路徑(maximal support path)”.即當(dāng)目標(biāo)沿著由Delaunay三角網(wǎng)中的線段穿越網(wǎng)絡(luò)時(shí)，即沿著虛線SD路徑入侵時(shí)，被檢測(cè)到的概率最大，因此，對(duì)于監(jiān)測(cè)方，這樣的路徑就是“最好情形路徑”.

圖1 最好情形和最壞情形的柵欄覆蓋Fig.1 The best and worst case of the barrier coverage

1.2 蟻群算法

蟻群算法(Ant Colony Optimization,ACO)是在20世紀(jì)90年代初期，意大利學(xué)者Colorni，Dorigo和Maniezzo等人，從螞蟻尋找食物的行為中受到啟發(fā)，通過模擬螞蟻尋找食物的方式得出了一種群智能算法[9].當(dāng)螞蟻尋找食物時(shí)會(huì)在路徑上留下一種外激素的化學(xué)物質(zhì)，又叫信息素(pheromone).通過識(shí)別信息素的濃度，螞蟻可以找到回到巢穴的最優(yōu)路徑，而且不會(huì)迷路.螞蟻選擇信息素濃度較高的方向，從而形成了正反饋機(jī)制，使得該方法易于發(fā)現(xiàn)較好解.蟻群算法還有許多優(yōu)點(diǎn)，它具有較強(qiáng)的魯棒性，易于和其他算法結(jié)合，所以，在現(xiàn)實(shí)生活中諸多方面均有應(yīng)用[10].

1.3 Delaunay圖

Delaunay圖即對(duì)于一組無線傳感器固定節(jié)點(diǎn)，可以得到很多種不用的三角剖分，其中最優(yōu)三角剖分就是Delaunay三角網(wǎng)[11].其最重要的兩個(gè)性質(zhì)體現(xiàn)在：唯一性，一組點(diǎn)無論如何構(gòu)造都能得到同一個(gè)Delaunay三角網(wǎng)；不相交性，Delaunay三角網(wǎng)內(nèi)各邊都不相交.

1.4 Voronoi圖

Voronoi 圖亦稱泰森多邊形，與Delaunay三角剖分是對(duì)偶關(guān)系,是一組由連接兩個(gè)相鄰點(diǎn)的直線的垂直平分線組成的連續(xù)多邊形，平面由節(jié)點(diǎn)集劃分成多個(gè)多邊形區(qū)域，而且每個(gè)區(qū)域只包括節(jié)點(diǎn)集中的一個(gè)節(jié)點(diǎn)[12].Voronoi 圖可以應(yīng)用于柵欄覆蓋中.根據(jù)Voronoi 圖可以直觀地觀察出柵欄覆蓋的目標(biāo)穿越路徑，如圖2所示.

圖2 移動(dòng)目標(biāo)穿越路徑Fig.2 Moving target traversing path

2 基于D-ACO的覆蓋優(yōu)化策略

2.1 覆蓋空洞的判斷

在狹長(zhǎng)的柵欄覆蓋區(qū)域中，通過對(duì)各傳感器節(jié)點(diǎn)和它所在的Voronoi區(qū)域所有邊之間的距離d和節(jié)點(diǎn)感知半徑Rs的大小比較，判斷是否存在覆蓋空洞[13].根據(jù)Voronoi圖的性質(zhì)，該距離d等于兩個(gè)相鄰節(jié)點(diǎn)Oa、Ob距離的一半.已知每個(gè)傳感器節(jié)點(diǎn)都能獲取自身位置信息以及Voronoi圖中相鄰節(jié)點(diǎn)的位置信息.其中，傳感器節(jié)點(diǎn)到Voronoi 多邊形邊的距離用d表示，O表示傳感器節(jié)點(diǎn)，則有

(1)

當(dāng)d>Rs時(shí)一定存在覆蓋漏洞，當(dāng)dRs時(shí)一定不存在覆蓋漏洞.通過比較距離與節(jié)點(diǎn)感知半徑的大小關(guān)系可知節(jié)點(diǎn)的通信范圍和所在Voronoi多邊形之間可能存在以下3種位置關(guān)系：

(1)節(jié)點(diǎn)的感知范圍即通信半徑可能和Voronoi多邊形的邊有一個(gè)交點(diǎn)或多個(gè)交點(diǎn)，如圖3所示，可能和其中一個(gè)邊相交，此時(shí)距離d等于感知半徑Rs；也可能和其中多個(gè)邊相交，此時(shí)距離d小于感知半徑Rs.

圖3 一個(gè)或多個(gè)交點(diǎn)Fig.3 One or more intersection points

(2)Voronoi多邊形可能完全包圍節(jié)點(diǎn)的通信區(qū)域，此時(shí)距離d大于感知半徑Rs；也可能完全被通信區(qū)域所覆蓋，此時(shí)距離d小于感知半徑Rs，如圖4所示.

圖4 包圍或覆蓋Fig.4 Enclosure or coverage

(3)當(dāng)幾個(gè)節(jié)點(diǎn)相鄰時(shí)，傳感器節(jié)點(diǎn)中心與Voronoi區(qū)域的邊的距離d大于感知半徑Rs時(shí)，則傳感器節(jié)點(diǎn)之間一定存在覆蓋空洞，如圖5所示.

圖5 一定存在覆蓋空洞Fig.5 There must be an empty hole

2.2 蟻群算法的改進(jìn)

在傳統(tǒng)的蟻群算法中，螞蟻在向著食物方向搜索的過程中會(huì)釋放信息素，不過信息素的濃度是隨著時(shí)間的增加而增加的，因此，螞蟻在搜索初期的初始信息素匱乏，導(dǎo)致算法收斂速度慢，算法中后期，信息素濃度過高易陷入局部最優(yōu)[14].

2.2.1 正向搜索

首先為蟻群設(shè)置搜索起點(diǎn)，即狹長(zhǎng)區(qū)域最左側(cè)的固定節(jié)點(diǎn)為搜索起點(diǎn)，相對(duì)于傳統(tǒng)的蟻群算法，正向搜索是令蟻群從狹長(zhǎng)區(qū)域的一端向另一端進(jìn)行正向搜索，不可以反方向搜索.

2.2.2 根據(jù)Delaunay三角網(wǎng)最短邊進(jìn)行搜索

最初的蟻群算法是由于螞蟻留下的信息素經(jīng)過的時(shí)間越長(zhǎng)剩余的就越少，螞蟻在短路徑上往返的時(shí)間較少，所以信息素還沒揮發(fā)完，就有新的信息素產(chǎn)生.因此，短路徑上的信息素濃度比長(zhǎng)路徑上的信息素濃度高，從而吸引更多螞蟻選擇短路徑，然后又留下新的信息素，如此反復(fù)，整個(gè)蟻群最終聚集到最短路徑上[15].而改進(jìn)的蟻群算法是根據(jù)Delaunay三角網(wǎng)的最短邊進(jìn)行搜索，省去了很多選擇路徑的時(shí)間，提高了算法的搜索效率.由此根據(jù)Delaunay三角形邊長(zhǎng)判斷是否需要填充移動(dòng)節(jié)點(diǎn)，下面分3種情況進(jìn)行討論.

(1)當(dāng)BC<2Rs時(shí)，即兩個(gè)傳感器節(jié)點(diǎn)的距離小于傳感器節(jié)點(diǎn)的通信直徑時(shí)(圖6)，傳感器節(jié)點(diǎn)間無覆蓋空洞，不需要填充移動(dòng)節(jié)點(diǎn).

圖6 BC<2RsFig.6 BC<2Rs

(2)當(dāng)BC=2Rs時(shí)，即兩個(gè)傳感器節(jié)點(diǎn)的距離等于傳感器節(jié)點(diǎn)的通信直徑時(shí)(圖7)，傳感器節(jié)點(diǎn)間無覆蓋空洞，不需要填充移動(dòng)節(jié)點(diǎn).

圖7 BC=2RsFig.7 BC=2Rs

(3)當(dāng)BC>2Rs時(shí)，即兩個(gè)傳感器節(jié)點(diǎn)的距離大于傳感器節(jié)點(diǎn)的通信直徑時(shí)(圖8)，此時(shí)柵欄出現(xiàn)了覆蓋漏洞，需要填充移動(dòng)節(jié)點(diǎn).

圖8 BC>2RsFig.8 BC>2Rs

2.3 填充移動(dòng)節(jié)點(diǎn)方法

根據(jù)改進(jìn)的蟻群算法和Delaunay三角網(wǎng)的最短邊進(jìn)行正向搜索確定下來的柵欄覆蓋路徑，再利用蟻群算法以每2Rs為距離進(jìn)行移動(dòng)節(jié)點(diǎn)的填充，直到路徑上沒有未被覆蓋的區(qū)域，最終形成柵欄覆蓋.如圖9所示.

圖9 填充移動(dòng)節(jié)點(diǎn)方法Fig.9 Filling mobile node method

2.4 算法執(zhí)行過程

算法具體步驟如下：

步驟1：在目標(biāo)區(qū)域A×B的狹長(zhǎng)帶狀區(qū)域內(nèi)隨機(jī)部署固定節(jié)點(diǎn)，并且根據(jù)固定節(jié)點(diǎn)部署情況生成對(duì)應(yīng)的Voronoi圖.

步驟2：通過Voronoi圖判斷是否存在柵欄覆蓋空洞，若存在，進(jìn)行步驟3修復(fù)覆蓋空洞；否則，此覆蓋符合柵欄覆蓋要求，退出算法.

步驟3：根據(jù)節(jié)點(diǎn)分布構(gòu)建Delaunay三角網(wǎng)，再依據(jù)改進(jìn)的蟻群算法，根據(jù)Delaunay三角網(wǎng)最短邊進(jìn)行正向搜索，得到的路徑便是需要修復(fù)的柵欄覆蓋路徑.

步驟4：根據(jù)填充移動(dòng)節(jié)點(diǎn)方法進(jìn)行節(jié)點(diǎn)填充.

步驟5：再次構(gòu)建Voronoi圖判斷是否存在柵欄覆蓋空洞.若仍然存在，轉(zhuǎn)到步驟3修復(fù)覆蓋空洞，若不存在轉(zhuǎn)到步驟6.

步驟6：記錄移動(dòng)節(jié)點(diǎn)的最終位置并生成最終的網(wǎng)絡(luò)覆蓋圖.

3 仿 真

使用Matlab仿真軟件進(jìn)行仿真實(shí)驗(yàn).構(gòu)建網(wǎng)絡(luò)模型為1 000 m×300 m的狹長(zhǎng)帶狀仿真區(qū)域，初始條件下隨機(jī)放置40個(gè)固定節(jié)點(diǎn)和兩端固定位置的2個(gè)節(jié)點(diǎn)，左側(cè)初始節(jié)點(diǎn)坐標(biāo)為(0，150)，右側(cè)最終節(jié)點(diǎn)坐標(biāo)為(1 000，150)，生成對(duì)應(yīng)的Voronoi圖,如圖10所示.經(jīng)過Voronoi柵欄覆蓋空洞檢測(cè)后，運(yùn)用本文算法，構(gòu)建Delaunay三角網(wǎng)，利用蟻群算法修復(fù)柵欄覆蓋漏洞，添加了11個(gè)移動(dòng)節(jié)點(diǎn)，最終形成完整的1-柵欄覆蓋，如圖11所示.經(jīng)過100組實(shí)驗(yàn)仿真分析，柵欄完全修復(fù)的誤差低于10 %，證明算法可行.

圖10 初始部署狀態(tài)Fig.10 Initial deployment status

圖11 優(yōu)化后部署狀態(tài)Fig.11 Optimized post deployment status

3.1 節(jié)點(diǎn)自身屬性對(duì)算法的影響

當(dāng)節(jié)點(diǎn)自身的屬性變化時(shí)，會(huì)對(duì)移動(dòng)節(jié)點(diǎn)添加數(shù)量產(chǎn)生影響.如圖12所示，在一定大小的仿真區(qū)域內(nèi)，節(jié)點(diǎn)的通信半徑一定時(shí)，可以明顯看出，固定節(jié)點(diǎn)數(shù)量越大，所需添加移動(dòng)節(jié)點(diǎn)數(shù)量越少；當(dāng)固定節(jié)點(diǎn)數(shù)量一定時(shí)，隨著節(jié)點(diǎn)通信半徑的增大，所需添加移動(dòng)節(jié)點(diǎn)的個(gè)數(shù)逐漸變少.綜上所述，隨著固定節(jié)點(diǎn)數(shù)量的增加，當(dāng)節(jié)點(diǎn)的通信半徑增大時(shí)，所需添加移動(dòng)節(jié)點(diǎn)個(gè)數(shù)逐漸變少，算法執(zhí)行速度越快.

圖12 節(jié)點(diǎn)數(shù)量和移動(dòng)節(jié)點(diǎn)數(shù)量的關(guān)系Fig.12 The relationship between the number of nodes and the number of mobile nodes

3.2 不同算法的比較

為了更好地體現(xiàn)D-ACO算法的性能，現(xiàn)與其他的柵欄覆蓋修復(fù)算法進(jìn)行對(duì)比，分別是Voronoi算法[13]和CBGB算法[16].如圖13所示，D-ACO算法執(zhí)行速度和1-柵欄覆蓋的形成效率明顯優(yōu)于Voronoi算法和CBGB算法.當(dāng)節(jié)點(diǎn)數(shù)量是20時(shí)，Voronoi算法和CBGB算法所形成柵欄的長(zhǎng)度均比D-ACO算法長(zhǎng)；當(dāng)節(jié)點(diǎn)數(shù)量為80時(shí)，3個(gè)算法形成的柵欄長(zhǎng)度趨于相同.3個(gè)算法都是隨著節(jié)點(diǎn)的增加，形成的柵欄長(zhǎng)度越來越短，Voronoi算法和CBGB算法的優(yōu)點(diǎn)在于固定節(jié)點(diǎn)冗余明顯小于D-ACD算法.

圖13 節(jié)點(diǎn)數(shù)量和柵欄長(zhǎng)度的關(guān)系Fig.13 The relationship between the number of nodes and the length of the fence

4 結(jié)束語

柵欄覆蓋問題是無線傳感器網(wǎng)絡(luò)中的基本問題.本文提出一種改進(jìn)后的蟻群算法(D-ACO 算法)，用于混合無線傳感器網(wǎng)絡(luò)中指導(dǎo)移動(dòng)節(jié)點(diǎn)的部署.通過仿真結(jié)果分析表明：D-ACO算法形成效率和柵欄長(zhǎng)度明顯優(yōu)于其他算法，D-ACO算法優(yōu)化了混合傳感器網(wǎng)絡(luò)的柵欄覆蓋策略，能夠有效地偵測(cè)入侵目標(biāo).本課題所研究的改進(jìn)智能蟻群算法指導(dǎo)混合無線傳感器網(wǎng)絡(luò)中各個(gè)節(jié)點(diǎn)完成最初的規(guī)劃部署位置后，移動(dòng)節(jié)點(diǎn)需要改變自身位置，到達(dá)目標(biāo)地點(diǎn)，在此過程中包括移動(dòng)路徑、節(jié)點(diǎn)能量消耗等問題.本課題組在對(duì)網(wǎng)絡(luò)基本規(guī)劃完成的基礎(chǔ)上，需要進(jìn)一步研究移動(dòng)節(jié)點(diǎn)的路徑尋優(yōu)、能量分配方案等問題，完成傳感器網(wǎng)絡(luò)部署的整個(gè)過程.