考慮最大暴露值的無線傳感器網(wǎng)絡(luò)最小暴露路徑優(yōu)化算法

楊廷鴻，方海洋，姜大立，方玲

(1.陸軍勤務(wù)學(xué)院 軍事物流系, 重慶 401331; 2.陸軍勤務(wù)學(xué)院 基礎(chǔ)部, 重慶 401331)

0 引言

作為一類分布式網(wǎng)絡(luò)，無線傳感器網(wǎng)絡(luò)(WSN)具有可大規(guī)模部署、擴(kuò)展性強(qiáng)、能耗較低、價格低廉等特點(diǎn)[1-2]，能對環(huán)境信息進(jìn)行實(shí)時采集、處理和傳輸[3-5]。WSN現(xiàn)有的研究成果已被廣泛應(yīng)用于環(huán)境監(jiān)測[6]、軍事偵察[7]、智慧城市建設(shè)等多個領(lǐng)域[8]。

最小暴露路徑(MEP)是用來衡量WSN覆蓋效果[9-13]的重要方法，其優(yōu)化問題一直是廣大學(xué)者密切關(guān)注的熱點(diǎn)問題。一般來說，該類問題可歸結(jié)為曲線積分優(yōu)化問題[14-15]，其數(shù)值解法主要有兩種：基于Voronoi圖的方法和網(wǎng)格劃分的方法。Voronoi圖方法最早在文獻(xiàn)[16]中提出，該方法根據(jù)監(jiān)測區(qū)域內(nèi)傳感器的幾何位置來構(gòu)建Voronoi圖，然后計(jì)算每條邊的暴露值，并通過最短路徑算法求解出MEP. 在此基礎(chǔ)上，其他文獻(xiàn)又提出了很多改進(jìn)的方法：Djidjev[17]整合Voronoi圖和歐拉- 拉格朗日方程尋找MEP；Zhang等[18]在解決MEP問題過程中以Voronoi圖為基礎(chǔ)，提出了分布式路徑搜索方法；文獻(xiàn)[19]則利用Voronoi圖和Dijkstra算法(DA)搜索傳感器網(wǎng)絡(luò)中易受攻擊的路徑。對于網(wǎng)格劃分的方法而言，它首先將監(jiān)測區(qū)域劃分成正方形的網(wǎng)格，并限制目標(biāo)只能在網(wǎng)格的邊或者對角線上移動，然后再找出MEP[20]. Liu等[21]利用該方法研究了有向傳感器網(wǎng)絡(luò)中的MEP問題；文獻(xiàn)[22]提出了基于滲流的方案，將MEP問題轉(zhuǎn)化到三維均勻網(wǎng)格中，再利用網(wǎng)格劃分的方法求解；針對區(qū)域限制下的MEP問題，F(xiàn)eng等[23]將路徑分成3段，其中第2段需要穿過限制區(qū)域，第1段和第3段使用網(wǎng)格劃分的方法求解，第2段使用混合遺傳算法來求解。針對不同的研究背景，很多其他的基于網(wǎng)格劃分的改進(jìn)方法也被相繼提出。然而，基于Voronoi圖的方法對傳感器數(shù)量以及傳感器有無方向性具有很大限制，網(wǎng)格劃分的方法雖然能克服上述不足，但其計(jì)算復(fù)雜度對網(wǎng)格規(guī)模非常敏感。

事實(shí)上，在一些重點(diǎn)監(jiān)測或防御區(qū)域，傳感器部署的密度相對較高。例如在軍事上，交戰(zhàn)雙方會在重要的關(guān)口、要塞、道路上設(shè)置大量的各類型監(jiān)控傳感器，對敵方入侵進(jìn)行密切監(jiān)控；在珍稀動物保護(hù)區(qū)，為了監(jiān)測珍稀動物的生活習(xí)慣，會在保護(hù)區(qū)內(nèi)部署大量的攝像頭或紅外探測儀以進(jìn)行實(shí)時監(jiān)測。同時，當(dāng)網(wǎng)格規(guī)模越大，分辨率越高，離散化帶來的模型誤差越小。因此，網(wǎng)格規(guī)模大、傳感器密度高的WSN中MEP優(yōu)化問題引起了學(xué)者的關(guān)注。

針對網(wǎng)格規(guī)模大、傳感器高密度的MEP優(yōu)化問題，一些學(xué)者提出利用啟發(fā)式算法來降低算法的復(fù)雜度，如文獻(xiàn)[24]提出了多頭絨孢菌優(yōu)化算法，利用多頭絨孢菌的避光性來解決這一問題。但當(dāng)網(wǎng)格規(guī)?；騻鞲衅髅芏雀淖儠r，這一算法中的參數(shù)需要重新調(diào)整，算法的普適性不夠強(qiáng)。文獻(xiàn)[25]中，在考慮目標(biāo)導(dǎo)向的情況下，以隨機(jī)漫步算法和DA為基礎(chǔ)，提出了導(dǎo)向相遇隨機(jī)漫步算法(TGSARWI DA)。該算法能獲得與DA暴露度高度一致的路徑，且很大程度上克服了計(jì)算復(fù)雜度對網(wǎng)格規(guī)模和傳感器密度的敏感性。不過上述算法只關(guān)注路徑的暴露度之和，而忽略了路徑上局部路段(邊)的最大暴露值。根據(jù)木桶短板原理，暴露值最大的邊往往在很大程度上決定了WSN覆蓋質(zhì)量的好壞。例如，在WSN應(yīng)用的某些特殊領(lǐng)域(諸如軍事上的穿越戰(zhàn)場、城市安防建設(shè)等問題)，通常涉及到在通往重要目標(biāo)的關(guān)鍵區(qū)域部署更多的傳感器來加強(qiáng)對外來目標(biāo)的監(jiān)測問題。雖然經(jīng)過該區(qū)域的路徑能保證暴露度之和最小，但路徑上的最大暴露值相對較高，反而更容易暴露目標(biāo)。文獻(xiàn)[26]考慮了路徑長度的影響，但是網(wǎng)格化的WSN是典型的加權(quán)網(wǎng)絡(luò)，直接用路徑的長度顯得不夠合理。

本文首先簡述了基于網(wǎng)格劃分的WSN中MEP優(yōu)化問題；隨后在考慮路徑中最大暴露值影響的情況下對經(jīng)典的DA進(jìn)行改進(jìn)，形成考慮最大暴露值的DA(DAME)，并在此基礎(chǔ)上結(jié)合TGSARWI算法提出了解決網(wǎng)格大規(guī)模、傳感器高密度WSN中MEP優(yōu)化問題的TGSARWI DAME；最后從參數(shù)分析、算法性能評估以及實(shí)例驗(yàn)證3個方面對算法進(jìn)行了仿真和分析。

1 基于網(wǎng)格劃分的WSN的MEP優(yōu)化問題

設(shè)N個傳感器{S1,…,Si,…,SN}部署在某一網(wǎng)格劃分的區(qū)域，WSN中的MEP優(yōu)化問題是指在該區(qū)域中，找到一條MEP連接源節(jié)點(diǎn)vs和目標(biāo)節(jié)點(diǎn)ve，其中s和e分別表示源頭和目標(biāo)。

1.1 暴露度定義

假設(shè)目標(biāo)在傳感器監(jiān)測下的暴露強(qiáng)度和它們之間的距離呈反比，即目標(biāo)距離傳感器越遠(yuǎn)，目標(biāo)的暴露度越小。根據(jù)文獻(xiàn)[24]，定義距離傳感器Si為d的目標(biāo)O在其監(jiān)測下的暴露度為

(1)

式中：μ和τ為傳感器的性能參數(shù)，根據(jù)文獻(xiàn)[26]，可取值為1.

如果傳感器的探測具有方向性，則目標(biāo)被傳感器監(jiān)測的暴露度還與方向角有關(guān)。一般地，偏離傳感器中心方向的角度越大，暴露度越低。因此，對于方向型傳感器，定義目標(biāo)在傳感器下的暴露度為

(2)

式中：Vi表示有向傳感器探測的中心方向向量；SiO表示傳感器Si和目標(biāo)O的方向向量；φ(A,B)表示A、B兩向量間的夾角；γ為傳感器的性能參數(shù)，根據(jù)文獻(xiàn)[27]，可取值為1.

根據(jù)上述定義，在部署有N個傳感器的區(qū)域內(nèi)，目標(biāo)被監(jiān)測的暴露度有兩種表示方法[24]：一是將目標(biāo)在所有單個傳感器下的暴露度相加，即

(3)

二是取被監(jiān)測暴露度的最大值，即

(4)

由(1)式和(2)式可知，雖然區(qū)域內(nèi)任意位置目標(biāo)在所有傳感器的監(jiān)測下均具有一定的暴露度，但是根據(jù)文獻(xiàn)[28]，該暴露度隨目標(biāo)與它們之間距離以及偏離有向傳感器中心方向角度的增大而急劇衰減。因此，在目標(biāo)被多個傳感器監(jiān)測暴露度的計(jì)算中，往往由監(jiān)測效果最佳的一個或者少數(shù)幾個傳感器起決定作用。另一方面從計(jì)算復(fù)雜度的角度考慮，(4)式的計(jì)算復(fù)雜度遠(yuǎn)遠(yuǎn)小于(3)式，尤其是在傳感器大量部署的情況下這一差異更為顯著。因此，依據(jù)文獻(xiàn)[24]，本文采用第2種方式。

1.2 網(wǎng)格劃分區(qū)域

網(wǎng)格劃分區(qū)域的基本思想是將無線傳感器監(jiān)測區(qū)域劃分為m×n的網(wǎng)格，假設(shè)目標(biāo)只能沿著網(wǎng)格的邊進(jìn)行移動。

一般可以用無向圖G=(V,E,W)表示網(wǎng)格型網(wǎng)絡(luò)，其中V為所有網(wǎng)格節(jié)點(diǎn)的集合，E為所有網(wǎng)格邊的集合，W為邊的權(quán)重(網(wǎng)格邊的暴露度)的集合。參照文獻(xiàn)[24]，若記網(wǎng)格邊的長度為l，編號i的節(jié)點(diǎn)記為vi，其坐標(biāo)記為(xi,yi)，網(wǎng)格網(wǎng)絡(luò)中相鄰兩個節(jié)點(diǎn)vi、vj之間邊的權(quán)重wij表示為

(5)

2 考慮最大暴露值的WSN中MEP優(yōu)化問題求解算法

2.1 考慮最大暴露值的優(yōu)化目標(biāo)

一般地，如果不考慮路徑上的最大暴露值，路徑H={vt1,vt2,…,vtp}上的暴露度等于路徑H上各路段暴露值之和，即

(6)

vt1，vt2，…，vtp表示路徑H上的p個節(jié)點(diǎn)，t1，t2，…，tp表示路徑H上節(jié)點(diǎn)對應(yīng)于網(wǎng)格網(wǎng)絡(luò)中的節(jié)點(diǎn)編號。經(jīng)典的DA尋求源點(diǎn)至網(wǎng)絡(luò)中其他各節(jié)點(diǎn)的最短路，就是以E(1)(H)最小為目標(biāo)進(jìn)行的。

若要考慮路徑上邊的最大暴露值，可以改進(jìn)(6)式，定義路徑H的暴露度為

(7)

式中：α為權(quán)重，0<α<1.

對于短路徑而言，其暴露度總和與最大暴露值之間的數(shù)量級差異不明顯，但對于長路徑而言，兩者差異可能較大，這可能導(dǎo)致最大暴露值無法發(fā)揮其作用。因此，(7)式中參數(shù)的選取難以兼顧不同路徑長度。

考慮到DA求解最短路徑的過程是借助已知的最短路像滾雪球一樣一層一層地?cái)U(kuò)展出新的最短路徑。每一次探尋新的最短路其實(shí)就是嘗試將已知最短路再延伸一段，即新的最短路只會由某條已知的最短路增加一條邊構(gòu)成。受到該算法的啟發(fā)，給出具有遞推關(guān)系的衡量路徑暴露程度的指標(biāo)為

E(3)(H{vtp′})=

(8)

事實(shí)上，(8)式中罰因子β的作用依然受到網(wǎng)格規(guī)模和路徑長度的影響。但是，可以通過兩階段運(yùn)行本算法來克服：第1階段運(yùn)行以(8)式目標(biāo)尋找臨時MEP，并記該路徑的最大暴露值為epmax；第2階段運(yùn)行以(9)式為目標(biāo)尋找MEP. 只要β足夠大，就能有效回避路徑最大暴露值的增加。

E(3)(H{vtp′})=

(9)

因此，若將經(jīng)典DA的優(yōu)化目標(biāo)由E(1)(H)改為E(3)(H)，則可以將路徑上的最大暴露值納入MEP問題的求解之中，形成DAME.

2.2 DAME的構(gòu)建

為了便于算法的描述，記E(3)(v)為源點(diǎn)vs到節(jié)點(diǎn)v的MEP考慮最大暴露值的路徑暴露度；maxEP(v)為源點(diǎn)vs到節(jié)點(diǎn)v的MEP最大暴露值。

由于DAME更改了DA的優(yōu)化目標(biāo)，相應(yīng)的算法步驟內(nèi)容也應(yīng)作相應(yīng)改進(jìn)，其流程圖如圖1所示，其中Γ(v)記錄節(jié)點(diǎn)v到源節(jié)點(diǎn)vs最短路徑的父節(jié)點(diǎn)信息。

在無向圖G=(V,E,W)中的DAME具體描述如下(其中k表示算法運(yùn)行階段：0表示第1階段，1表示第2階段)：

1)初始化k=0，為源節(jié)點(diǎn)vs標(biāo)號P，并令E(3)(vs)=0，maxEP(vs)=0；其余節(jié)點(diǎn)標(biāo)號T，記Δ={vj|vj∈V&vj≠vs}，有?vj∈Δ，T(vj)=∞；

2)遍歷vj∈Δ&(vs,vj)∈E，令T(vj)=wsj，Γ(vj)=vs，轉(zhuǎn)步驟4；

3)針對所有vt∈R，遍歷vj∈Δ&(vt,vj)∈E，若T(vj)>E(3)(vt)+wtj+βmax {0,wtj-maxEP(vt)}，則令T(vj)=E(3)(vt)+wtj+βmax {0,wtj-maxEP(vt)}，Γ(vj)=vt；

4)令R=?；

6)若k=0，則轉(zhuǎn)步驟7，否則算法結(jié)束；

7)記epmax=maxEP(ve)，并重置各參數(shù)：k=1,為源節(jié)點(diǎn)vs標(biāo)號P，并令E(3)(vs)=0，maxEP(vs)=epmax，其余節(jié)點(diǎn)標(biāo)號T，記Δ={vj|vj∈V&vj≠vs}，有?vj∈Δ，T(vj)=∞，轉(zhuǎn)步驟2.

上述算法中，Γ記錄的源節(jié)點(diǎn)vs到其他各點(diǎn)的最短路徑信息并不完全，但一定包含了源節(jié)點(diǎn)vs到目標(biāo)節(jié)點(diǎn)ve的最短路徑Hmin的完整信息。Hmin可以通過以下回溯算法求解：

1)初始化Hmin={Γ(ve),ve}，令vt=Γ(ve)；

2)若vt=vs則回溯結(jié)束，否則轉(zhuǎn)步驟3；

3)令Hmin={Γ(vt)}Hmin、vt=Γ(vt)，轉(zhuǎn)步驟2.

2.3 TGSARWI DAME的構(gòu)建

TGSARWI算法主要通過模擬多個探路者在陌生區(qū)域的探路過程尋找連通源節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)的連通子網(wǎng)絡(luò)[25]，其核心思想是通過建立通路子網(wǎng)絡(luò)以降低網(wǎng)格規(guī)模。

若某一探路者t時刻由路徑Ht到達(dá)節(jié)點(diǎn)vt，位置坐標(biāo)為(xt,yt)，則其目的地(源節(jié)點(diǎn)或者目標(biāo)節(jié)點(diǎn))為v*，位置坐標(biāo)為(x*,y*)。探路者在網(wǎng)格上進(jìn)行隨機(jī)移動，他從當(dāng)前節(jié)點(diǎn)vt移動到下一個節(jié)點(diǎn)vj的轉(zhuǎn)移概率為

(10)

(11)

利用該轉(zhuǎn)移概率可以排除已經(jīng)走過的節(jié)點(diǎn)，提升探路效率，但也有可能造成探路者被密集的傳感器“堵死”或者被自己前面經(jīng)過的路徑“圍死”而無路可走。因此，在隨機(jī)游走過程中必須設(shè)置游走的局部回溯功能以及重啟功能。

由于單條路徑具有一定的隨機(jī)性，從源節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)同時派出nf個探路者進(jìn)行探路，直到形成nh條通路為止，再將這些通路組合成一個連通的子網(wǎng)絡(luò)G1=(V1,E1,W1)。此時，子網(wǎng)絡(luò)G1的規(guī)模遠(yuǎn)遠(yuǎn)小于原網(wǎng)絡(luò)G.

將TGSARWI算法與本文提出的DAME相結(jié)合，構(gòu)建TGSARWI DAME，算法的基本思想是：首先，利用TGSARWI算法構(gòu)建通路子網(wǎng)絡(luò)；然后，利用DAME在通路子網(wǎng)絡(luò)中尋找考慮最大暴露值的MEP.

DAME是在DA的基礎(chǔ)上更改了生成新的最短路的標(biāo)準(zhǔn)以及記錄相應(yīng)最短路的父節(jié)點(diǎn)，其復(fù)雜度與DA相當(dāng)。因此，TGSARWI DAME與TGSARWI DA的復(fù)雜度也是相當(dāng)?shù)?。文獻(xiàn)[25]的研究表明，TGSARWI DA的復(fù)雜度甚至不足DA的1‰，這充分表明了TGSARWI DAME也具備求解網(wǎng)格規(guī)模大、傳感器密度高的MEP優(yōu)化問題的能力。

3 算法仿真與結(jié)果分析

3.1 參數(shù)分析

假設(shè)某50×50的網(wǎng)格區(qū)域部署了50個傳感器，網(wǎng)格長度l=10 m，傳感器密度為0.02，有向傳感器和無向傳感器是混合隨機(jī)分布的。根據(jù)文獻(xiàn)[28]，取導(dǎo)向調(diào)節(jié)因子ρ=0.9，罰因子β在區(qū)間[10-2,106]之間取值，分別探尋最佳路徑H，并計(jì)算其暴露度總和E(1)(H)和最大暴露值maxEP(H)。

由于傳感器類型及分布是隨機(jī)的，為了克服樣本隨機(jī)性帶來的影響，對于每一個β值均隨機(jī)生成50組傳感器類型及分布，并計(jì)算相應(yīng)的E(1)(H)和maxEP，然后取其平均值作為該β值下的相應(yīng)指標(biāo)。圖2給出了路徑H的暴露度總和E(1)(H)和最大暴露值maxEP(H)隨著罰因子β的變化曲線圖。

由圖2可以發(fā)現(xiàn)，當(dāng)β<1時，E(1)(H)和maxEP(H)幾乎沒有變化，說明較小的β值很難對算法求解產(chǎn)生影響。當(dāng)β>1時，maxEP(H)呈現(xiàn)出快速下降趨勢，并在β>100之后再次呈現(xiàn)出穩(wěn)定趨勢，而在相應(yīng)的階段中E(1)(H)一直呈現(xiàn)明顯的上升趨勢，直至β>1 000后呈現(xiàn)平穩(wěn)態(tài)勢。因此，可以認(rèn)為β=100為最佳取值。

另外，當(dāng)取其他網(wǎng)格規(guī)模和傳感器密度時，E(1)(H)和maxEP(H)的變化趨勢和上述仿真一致。這一結(jié)果說明TGSARWI DAME具有很好的普適性，一旦罰因子值確定后，在不同的傳感器網(wǎng)絡(luò)背景下均無需再分析其最佳取值。因此，后續(xù)分析直接將算法中的罰因子取值為100.

3.2 對比分析

3.2.1 TGSARWI DAME與TGSARWI DA對比分析

設(shè)HTDAME、HTDA分別表示TGSARWI DAME、TGSARWI DA得到的最佳路徑。為對比分析兩種算法，定義路徑HTDAME相對于路徑HTDA關(guān)于暴露度總和E(1)的虧損率為

(12)

關(guān)于最大暴露值maxEP的收益率為

(13)

同時，定義收益虧損比為

(14)

η類似于經(jīng)濟(jì)中的投入產(chǎn)出比：若η>1，則說明犧牲較小的路徑暴露度獲得了較大的最大暴露度改進(jìn)，此時算法有效；反之亦然。

3.2.1.1 網(wǎng)格規(guī)模的影響

假設(shè)傳感器的密度為0.02，傳感器類型(含方向)和位置都是隨機(jī)生成的(下文也進(jìn)行相應(yīng)的設(shè)定)，網(wǎng)格規(guī)模從10×10到700×700進(jìn)行變化?？紤]到傳感器的隨機(jī)性，仿真時對于每一個網(wǎng)格規(guī)模都進(jìn)行30次重復(fù)仿真，分別取暴露度E(1)和最大暴露值maxEP的平均值，在此基礎(chǔ)上計(jì)算虧損率和收益率。

圖3給出了不同網(wǎng)格規(guī)模下路徑HTDAME和HTDA暴露度的對比趨勢圖以及它們的相對誤差和收益率的變化圖。通過圖3(a)和3(b)可以看出：兩條路徑的暴露值幾乎重合，都呈現(xiàn)出上升趨勢；最大暴露值也都呈現(xiàn)出增加趨勢，但是后者的最大暴露值都大于前者，并且相對差值越來越顯著。從圖3(c)中可知，最大暴露值的收益率要遠(yuǎn)遠(yuǎn)高于路徑暴露度的虧損率。表1給出了不同網(wǎng)格規(guī)模下路徑暴露度總和與最大暴露值的虧損率、收益率以及收益虧損比的信息。從圖3(d)和表1可以看出，該方法下的最大收益比為29.49，平均值為11.18，均遠(yuǎn)大于1.

表1 不同網(wǎng)格規(guī)模下路徑暴露度總和與最大暴露值的虧損率、收益率以及收益虧損比的信息
Tab.1 Loss rate of path exposure, profit rate of maximum exposure, and ratio of profit rate to loss rate under the condition of various grid scales

參數(shù)最小值平均值最大值RE(E(1))0 00630 01650 0377RE(maxEP)0 05670 14900 2259η2 081211 177029 4896

3.2.1.2 傳感器密度的影響

固定網(wǎng)格規(guī)模為50×50，傳感器密度從0.4%～40.0%之間進(jìn)行變化。與網(wǎng)格規(guī)模變化類似，同樣比較TGSARWI DAME與TGSARWI DA之間的路徑暴露度總和與最大暴露值的變化趨勢，并計(jì)算虧損率和收益率等。

圖4和表2分別給出了不同傳感器密度下，路徑HTDAME和HTDA的暴露度總和與最大暴露值對比趨勢圖、它們的相對誤差和收益率變化圖以及相應(yīng)的量化分析結(jié)果。從圖4(a)中可以發(fā)現(xiàn)，兩種算法得到的路徑暴露度幾乎重合，均隨傳感器密度增加而呈現(xiàn)出上升的趨勢。這說明不同傳感器密度下，TGSARWI DAME保持了TGSARWI DA探尋MEP的特征。從圖4(b)可以看出，路徑HTDAME最大暴露值明顯小于HTDA的 最大暴露值，且當(dāng)傳感器密度達(dá)到一定值(約0.12)時，前者的最大暴露值幾乎穩(wěn)定，而后者依然在顯著上升。一方面，充分體現(xiàn)了在不同傳感器密度下，TGSARWI DAME回避最大暴露值的優(yōu)異性能；另一方面，從傳感器網(wǎng)絡(luò)覆蓋的角度而言，單純依靠增加傳感器密度來提高覆蓋質(zhì)量，在密度達(dá)到一定的臨界值后，其效果將微乎其微。圖4(c)中給出了不同傳感器密度下TGSARWI DAME的虧損率和收益率的變化曲線。虧損率始終在接近于0的附近波動，而收益率則遠(yuǎn)大于虧損率，其呈現(xiàn)出明顯的上升趨勢。從圖4(d)和表2看出，虧損收益比平均值大約為8.84，最大值達(dá)到35.62，它們同樣遠(yuǎn)大于1.

以上結(jié)論充分說明了TGSARWI DAME能夠適應(yīng)大規(guī)模網(wǎng)格和高密度傳感器下的MEP優(yōu)化問題求解，并且能通過損失較小的路徑暴露度(平均上升小于2.2%)來顯著改善路徑上的最大暴露值(平均降低約15%)。這使得該方法可以在很多傳感器網(wǎng)絡(luò)的應(yīng)用上發(fā)揮重要作用，如軍事上的穿越戰(zhàn)場監(jiān)控區(qū)域問題。

表2 不同傳感器密度下路徑暴露度和最大暴露值的虧損率、收益率以及收益比的信息
Tab.2 Loss rate of path exposure, profit rate of maximum exposure, and ratio of profit rate to loss rate under the condition of various sensor densities

參數(shù)最小值平均值最大值RE(E(1))0 00410 02170 0546RE(maxEP)0 03600 14710 3428η2 59118 841035 6200

3.2.2 TGSARWI DAME與DA對比分析

DA是求解網(wǎng)格化MEP問題的最優(yōu)算法，下面將對比TGSARWI DAME與DA以分析前者求解MEP問題的性能。為了便于后文描述，記HDA為由DA在全局網(wǎng)格上尋求的MEP路徑。由于DA的計(jì)算復(fù)雜度為O(m2n2)，相對較高，限制了仿真比較的網(wǎng)格規(guī)模范圍。因此，在仿真過程中，僅讓網(wǎng)格規(guī)模從10×10到150×150進(jìn)行變化，其他仿真條件及研究方法與3.2.1節(jié)相同。

圖5給出了由TGSARWI DAME和DA得到的路徑暴露度總和與最大暴露值在不同網(wǎng)格規(guī)模以及不同傳感器密度下的變化曲線。由圖5(a)和圖5(b)可知，在網(wǎng)格規(guī)模較小時，兩種算法得到的路徑暴露度總和與最大暴露值都基本重合。當(dāng)網(wǎng)格規(guī)模進(jìn)一步增大時，盡管由TGSARWI DAME得到的路徑暴露度總和略微高于DA，但路徑上的最大暴露度明顯低于DA，這一趨勢隨著網(wǎng)格規(guī)模的增加會更加顯著。由圖5(c)和圖5(d)可知，二者得到的路徑在不同傳感器密度下的路徑暴露度總和基本一致，但當(dāng)傳感器密度增加到一定程度時，TGSARWI DAME得到的最大暴露值基本穩(wěn)定到某一固定值，DA得到的路徑上最大暴露值則處于繼續(xù)增長的趨勢，這充分說明TGSARWI DAME降低路徑上最大暴露度的優(yōu)勢是非常明顯的。

3.3 實(shí)例驗(yàn)證

實(shí)例1假定WSN的網(wǎng)絡(luò)與3.1節(jié)相同，β=100，分別利用TGSARWI DAME和TGSARWI DA尋找MEP.

圖6中分別給出了TGSARWI DAME和TGSARWI DA得到的MEP比較圖。從圖6中可以看出，TGSARWI DAME找到的MEP(紅色)能夠很好地避開暴露值較大的區(qū)域，與TGSARWI DA相比較而言，雖然前者的E(1)與后者基本一致，但實(shí)現(xiàn)了將maxEP降為后者約一半的目標(biāo)。

實(shí)例2設(shè)定網(wǎng)格規(guī)模為700×700，傳感器密度為0.02，即傳感器的數(shù)量約為9 800個。源點(diǎn)和目標(biāo)點(diǎn)的坐標(biāo)分別為(1 120 m, 6 160 m)和(5 880 m, 1 680 m)。

這里，分別利用TGSARWI DAME、TGSARWI DA找出MEP. 圖7和圖8分別給出了計(jì)算結(jié)果的全局圖和局部圖。

從圖7中可以看出，整個網(wǎng)格區(qū)域規(guī)模非常大，且傳感器密密麻麻，基本上無法正常判斷出MEP. 但是算法依然給出了相應(yīng)的路徑。從圖8中可以發(fā)現(xiàn)TGSARWI DA為了尋求路徑暴露度的最小化，強(qiáng)行通過暴露度較大的路段。而TGSARWI DAME雖然相對于TGSARWI DA損失0.786 0的路徑暴露度，但能使得整條路徑上最大暴露值降低0.328 51.

現(xiàn)有的MEP問題求解算法中，最大的計(jì)算網(wǎng)格規(guī)模為150×150，實(shí)例2的網(wǎng)格規(guī)模遠(yuǎn)遠(yuǎn)超過該規(guī)模。3.2節(jié)中對比分析涉及的網(wǎng)格規(guī)模和傳感器密度以及實(shí)例2的解決充分說明了TGSARWI DAME具備求解大規(guī)模網(wǎng)格和高密度傳感器背景下的WSN中考慮最大暴露值MEP優(yōu)化問題的能力。

4 結(jié)論

本文將路徑最大暴露值的有效控制納入MEP問題的求解，提出了TGSARWI DAME，經(jīng)過與傳統(tǒng)算法仿真進(jìn)行對比，得出以下結(jié)論：

1)該算法能夠有效規(guī)避MEP中暴露值較大路段，在不同網(wǎng)格尺度、不同傳感器密度下，最大暴露值平均降低14.7%.

2)路徑暴露度能夠保持與DA、TGSARWI DA相當(dāng)?shù)木?，在不同網(wǎng)格尺度、不同傳感器密度下，路徑暴露度平均偏差不超過2.2%.

總體而言，本算法能夠求解網(wǎng)格大尺度、傳感器高密度與考慮最大暴露值的MEP問題，適用于戰(zhàn)場監(jiān)控區(qū)域的穿越等問題。

參考文獻(xiàn)(References)

[1] Shahid N, Naqvi I H, Qaisar S B. Characteristics and classification of outlier detection techniques for wireless sensor networks in harsh environments: a survey[J]. Artificial Intelligence Review, 2015, 43(2): 193-228.

[2] Mahmood M A, Seah W K G, Welch I. Reliability in wireless sensor networks: a survey and challenges ahead[J]. Computer Networks, 2015, 79(1):166-187.

[3] Lewis F L. Wireless sensor networks[M]∥Cook D J, Das S K. Smart Environments: Technologies, Protocols, and Applications. Hoboken, NJ, US:Wiley-Interscience, 2005: 11-46.

[4] Iyengar S S, Brooks R R. Distributed sensor networks: sensor networking and applications[M]. Boca Raton, FL, US: CRC Press, 2016: 35-56.

[5] Khan S, Pathan A S K, Alrajeh N A. Wireless sensor networks: current status and future trends[C] ∥ Proceedings of 2012 IEEE Symposium on Computer Applications and Industrial Electronics. Boca Raton, FL, US:IEEE, 2012: 267-272.

[6] Srbinovska M, Gavrovski C, Dimcev V. Environmental parameters monitoring in precision agriculture using wireless sensor networks[J]. Journal of Cleaner Production, 2015, 88: 297-307.

[7] Ball M G, Qela B, Wesolkowski S. A review of the use of computational intelligence in the design of military surveillance networks [M]. Heidelberg, Germany: Springer，2016: 663-693.

[8] Wu J, Ota K, Dong M X,et al. A hierarchical security framework for defending against sophisticated attacks on wireless sensor networks in smart cities[J]. IEEE Access, 2016(4):416-424.

[9] Zhu C, Zheng C L, Shu L, et al. A survey on coverage and connectivity issues in wireless sensor networks[J]. Journal of Network and Computer Applications, 2012, 35(2): 619-632.

[10] Mini S, Udgata S K, Sabat S L. Sensor deployment and scheduling for target coverage problem in wireless sensor networks[J]. IEEE Sensors Journal, 2014, 14(3): 636-644.

[11] Megerian S, Koushanfar F, Potkonjak M. Worst and best-case coverage in sensor networks[J]. IEEE Transactions on Mobile Computing, 2005, 4(1): 84-92.

[12] Meguerdichian S, Koushanfar F, Qu G, et al. Exposure in wireless ad-hoc sensor networks[C]∥Proceedings of the 7th Annual International Conference on Mobile Networking & Computing. Rome, Italy: ACM, 2001:139-150.

[13] Clouqueur T, Phipatanasuphorn V, Ramanathan P, et al. Sensor deployment strategy for target detection[C]∥Proceedings of the 1st ACM International Workshop on Wireless Sensor Networks & Applications. Atlanta, GA, US: ACM, 2002: 42-48.

[14] Gelfand I M, Fomin S V. Calculus of variations[M]. Heidelberg, Germany: Springer, 1966: 727-751.

[15] Djidjev H N. Approximation algorithms for computing minimum exposure paths in a sensor field[J]. ACM Transactions on Sensor Networks, 2010, 7(3): 145-153.

[16] Veltri G, Huang Q F, Qu G, et al. Minimal and maximal exposure path algorithms for wireless embedded sensor networks[C]∥International Conference on Embedded Networked Sensor Systems. Los Angeles, CA, US:IEEE, 2003.

[17] Djidjev H N. Efficient computation of minimum exposure paths in a sensor network field[C]∥Proceedings of the International Conference on Distributed Computing in Sensor Systems. Santa Fe, NM, US: Springer, 2007: 295-308.

[18] Zhang W Z, Li M L, Shu W，et al . Smart path-finding with local information in a sensory field[C]∥2nd International Conference on Mobile Ad-hoc and Sensor Networks . Hong Kong, China: IEEE，2006.

[19] Zhou J. A nodal integration and post-processing technique based on Voronoi diagram for Galerkin meshless methods[J]. Computer Methods in Applied Mechanics and Engineering, 2003, 192(35): 3831-3843.

[20] Megerian S, Koushanfar F, Qu G, et al. Exposure in wireless sensor networks: theory and practical solutions[J]. Wireless Networks, 2002, 8(5): 443-454.

[21] Liu L, Zhang X, Ma H D. Minimal exposure path algorithms for directional sensor networks[J]. Wireless Communications and Mobile Computing, 2014, 14(10): 979-994.

[22] Liu X S, Kang G X, Zhang N B. Percolation theory-based exposure-path prevention for 3D-wireless sensor networks coverage[J]. KSII Transactions on Internet & Information Systems, 2015, 9(1): 126-148.

[23] Feng H, Luo L, Wang Y, et al. A novel minimal exposure path problem in wireless sensor networks and its solution algorithm[J]. International Journal of Distributed Sensor Networks, 2016, 12(8): 1550147716664245.

[24] Liu L, Song Y N, Zhang H Y. Physarum optimization: a biology-inspired algorithm for the steiner tree problem in networks[J]. IEEE Transactions on Computers, 2015, 64(3): 818-831.

[25] Yang T H, Jiang D L, Fang H Y. Target guiding self-avoiding random walk with intersection algorithm for minimum exposure path problem in wireless sensor networks[J]. EURASIP Journal on Wireless Communications and Networking, 2018(1): 33.

[26] 羅卿, 林亞平, 尹波. 傳感器區(qū)域中基于網(wǎng)格的穿越軌跡算法研究 [J]. 通信學(xué)報, 2011, 32(6): 67-77.

LUO Qing, LIN Ya-ping, YIN Bo. Traversal trajectory based on grid in wireless sensor networks field[J]. Journal on Communications, 2011, 32(6): 67-77. (in Chinese)

[27] Liu L, Han G, Wang H. Obstacle-avoidance minimal exposure path for heterogeneous wireless sensor networks[J]. Ad Hoc Networks, 2017, 55:50-61.

[28] Liu L, Zhang X, Ma H D. Minimal exposure path algorithms for directional sensor networks[C]∥IEEE Conference on Global Telecommunications. Honolulu, Hawaii, US: IEEE, 2009:6155-6160.