神顯豪，李 軍，奈 何

(廣西高校嵌入式技術(shù)與智能信息處理重點(diǎn)實(shí)驗(yàn)室(桂林理工大學(xué))，廣西 桂林 541004)

(*通信作者電子郵箱leejun19901113@163.com)

感知受限的移動(dòng)傳感器節(jié)點(diǎn)掃描覆蓋優(yōu)化算法

神顯豪，李 軍*，奈 何

(廣西高校嵌入式技術(shù)與智能信息處理重點(diǎn)實(shí)驗(yàn)室(桂林理工大學(xué))，廣西 桂林 541004)

(*通信作者電子郵箱leejun19901113@163.com)

移動(dòng)無(wú)線傳感器網(wǎng)絡(luò)(WSN)的應(yīng)用中，因?yàn)閭鞲衅鞴?jié)點(diǎn)的感知范圍受限，其覆蓋分析就是一個(gè)針對(duì)目標(biāo)區(qū)域的掃描覆蓋問(wèn)題。提出了一種基于多目標(biāo)優(yōu)化的掃描覆蓋算法。在目標(biāo)區(qū)域中，采用雙目標(biāo)優(yōu)化策略對(duì)單個(gè)移動(dòng)傳感器節(jié)點(diǎn)進(jìn)行路徑規(guī)劃，一方面使節(jié)點(diǎn)的覆蓋面最大化，另一方面使掃描覆蓋的路徑最短。仿真實(shí)驗(yàn)在含有障礙物和不含障礙物的情況下進(jìn)行，與多節(jié)點(diǎn)的編隊(duì)覆蓋算法相比，所提算法在適度降低覆蓋率的情況下，可大幅降低移動(dòng)能耗。

移動(dòng)傳感器節(jié)點(diǎn)；掃描覆蓋；雙目標(biāo)優(yōu)化；覆蓋率；能耗

GuilinGuangxi541004,China)

0 引言

在無(wú)線傳感器網(wǎng)絡(luò)(Wireless Sensor Network, WSN)研究中，覆蓋問(wèn)題是基本問(wèn)題之一，它直接影響到WSN的工作效率和質(zhì)量。在移動(dòng)無(wú)線傳感器網(wǎng)絡(luò)的應(yīng)用中，因?yàn)橐苿?dòng)傳感器節(jié)點(diǎn)的感知范圍受限，其覆蓋分析就是一個(gè)針對(duì)目標(biāo)區(qū)域的掃描覆蓋問(wèn)題。近年來(lái)國(guó)內(nèi)外對(duì)移動(dòng)傳感器節(jié)點(diǎn)的掃描覆蓋目標(biāo)區(qū)域的算法也有一些研究。王偉等[1]提出了一種模擬退火算法的掃描覆蓋機(jī)制，比傳統(tǒng)的掃描覆蓋表現(xiàn)出更好的性能；雍毅等[2]提出了一種動(dòng)態(tài)興趣點(diǎn)的掃描覆蓋，更能適應(yīng)動(dòng)態(tài)的目標(biāo)區(qū)域；李小康等[3]提出了一種關(guān)于路徑增量與覆蓋間隔差異的插入啟發(fā)式算法；劉晨光等[4]設(shè)計(jì)了一種使用聚類方法的掃描覆蓋方法；舒莉等[5]設(shè)計(jì)了一種關(guān)于興趣點(diǎn)問(wèn)題的掃描覆蓋；林鋒等[6]設(shè)計(jì)了一種掃描覆蓋方法，它使用具有移動(dòng)性的傳感器節(jié)點(diǎn)當(dāng)作輔助來(lái)修復(fù)覆蓋洞。上述幾種算法都是通過(guò)多個(gè)移動(dòng)傳感器節(jié)點(diǎn)之間的編隊(duì)對(duì)覆蓋洞進(jìn)行掃描覆蓋，沒(méi)有考慮到節(jié)點(diǎn)的能耗和生命周期，也沒(méi)有考慮在含有障礙物的情況下的路徑規(guī)劃等問(wèn)題[7]。

在上述研究的理論基礎(chǔ)上，本文提出了一種優(yōu)化的掃描覆蓋算法。在目標(biāo)區(qū)域中，采用雙目標(biāo)優(yōu)化策略對(duì)單個(gè)移動(dòng)傳感器節(jié)點(diǎn)進(jìn)行路徑規(guī)劃，一方面使得節(jié)點(diǎn)的覆蓋面最大化，另一方面使掃描覆蓋的路徑最短。通過(guò)優(yōu)化掃描覆蓋算法，既降低了節(jié)點(diǎn)在掃描覆蓋的過(guò)程中的能耗，又延長(zhǎng)了節(jié)點(diǎn)的生命周期。

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

本文將計(jì)算域定義為D，緊子集定義為R2,障礙物的集合定義為Ω，一個(gè)封閉的集合包含了有限數(shù)量的連接部件和多個(gè)特定的障礙物。傳感器節(jié)點(diǎn)的半徑為r，水平集函數(shù)ψ(x)表明的環(huán)境包含了兩種情況：如果定義域的覆蓋部分是在障礙里面，那就表示為負(fù)的；如果定義域的覆蓋部分是在障礙外面，那就表示為正的。本文定義ψ(x)是障礙物Ω邊界的典型符號(hào)距離函數(shù)。一個(gè)傳感器節(jié)點(diǎn)x位于存在障礙物Ω的計(jì)算域D中，x為起始點(diǎn)，以直線的形式向前移動(dòng)并且在點(diǎn)y的位置停下。如果x和y的絕對(duì)值之差小于等于r，那么就表示點(diǎn)y在障礙物的邊界或者之內(nèi)。部分公式概念如表1所示。

下面定義半徑為r的傳感器節(jié)點(diǎn)移動(dòng)到點(diǎn)y位置的檢測(cè)面積的水平集函數(shù)φ：

(1)

其中L(x，y)表示x到y(tǒng)的連線部分。z的位置在障礙物的邊界時(shí)ψ(z)=0，在障礙物內(nèi)的時(shí)候ψ(z)<0,在障礙物外界的時(shí)候ψ(z)>0。

表1 公式概念

2 移動(dòng)傳感器節(jié)點(diǎn)的路徑規(guī)劃

2.1 節(jié)點(diǎn)單位置的路徑規(guī)劃

考慮了移動(dòng)傳感器節(jié)點(diǎn)單位置的最大覆蓋，更確切地說(shuō)就是將移動(dòng)傳感器節(jié)點(diǎn)移動(dòng)到最大覆蓋范圍V的最佳位置。本文使用梯度上升的方法來(lái)實(shí)現(xiàn)這個(gè)目標(biāo)，即本文按照梯度流來(lái)移動(dòng)節(jié)點(diǎn)x的位置，公式[8]如下：

(2)

其中，Δx表示關(guān)于x的梯度算子。梯度算子可以近似地看作有限差分方程。如本文使用中心差分方程可以得到：

(3)

其中h表示空間步長(zhǎng)。

為了能夠清晰地表示出移動(dòng)傳感器節(jié)點(diǎn)達(dá)到最大化覆蓋的移動(dòng)路徑，本文在目標(biāo)區(qū)域中設(shè)置了三個(gè)障礙物，并且通過(guò)梯度流的方法移動(dòng)傳感器節(jié)點(diǎn)，得到最大化覆蓋面積。如圖1所示，表示傳感器節(jié)點(diǎn)的初始位置；如圖2所示，表示移動(dòng)傳感器節(jié)點(diǎn)x位移到與障礙物相切的位置，達(dá)到最大化覆蓋面積的位置[9]。移動(dòng)傳感器節(jié)點(diǎn)在目標(biāo)區(qū)域中移動(dòng)，當(dāng)碰撞到計(jì)算域D的邊界時(shí)，停止計(jì)算。其中陰影部分表明三個(gè)障礙物，虛線圓圈表示傳感器節(jié)點(diǎn)的感知面積。

圖1 傳感器節(jié)點(diǎn)初始位置

圖2 傳感器節(jié)點(diǎn)最大化覆蓋面積

2.2 節(jié)點(diǎn)多位置的路徑規(guī)劃

由移動(dòng)傳感器節(jié)點(diǎn)單位置發(fā)散到移動(dòng)傳感器節(jié)點(diǎn)的多位置，本文設(shè){x1，x2，…，xm}表明m個(gè)傳感器節(jié)點(diǎn)，{r1，r2，…，rm}表明m個(gè)傳感器節(jié)點(diǎn)的半徑，每個(gè)傳感器節(jié)點(diǎn)的覆蓋范圍不同[10]?？偟臋z測(cè)范圍是多個(gè)傳感器節(jié)點(diǎn)的聯(lián)合覆蓋，多個(gè)傳感器節(jié)點(diǎn)的水平集函數(shù)如下所示：

(4)

另外，多個(gè)傳感器節(jié)點(diǎn)檢測(cè)面積V如下所示：

(5)

其中H表示一維的赫維賽德函數(shù)。

在目標(biāo)區(qū)域中，兩個(gè)移動(dòng)傳感器節(jié)點(diǎn)的情況下，需要尋找兩個(gè)新的位置達(dá)到彼此的覆蓋范圍不相交，這樣就使得覆蓋面積達(dá)到最大化[11]。如圖3所示兩個(gè)移動(dòng)傳感器節(jié)點(diǎn)的初始狀態(tài)，如圖4所示兩個(gè)移動(dòng)傳感器節(jié)點(diǎn)通過(guò)移動(dòng)達(dá)到與障礙物相切，最終達(dá)到最大化覆蓋面積，其中陰影部分表明三個(gè)障礙物，虛線圓圈表明傳感器節(jié)點(diǎn)的檢測(cè)面積[12]。

圖3 兩個(gè)移動(dòng)傳感器節(jié)點(diǎn)初始狀態(tài)

圖4 兩個(gè)節(jié)點(diǎn)的最大化覆蓋面積

當(dāng)有三個(gè)移動(dòng)傳感器節(jié)點(diǎn)時(shí)，本文也考慮了多個(gè)節(jié)點(diǎn)的局部?jī)?yōu)化。圖5為三個(gè)傳感器節(jié)點(diǎn)的初始狀態(tài)；圖6為三個(gè)傳感器節(jié)點(diǎn)達(dá)到的局部最大化覆蓋。其中陰影部分表示三個(gè)障礙物，虛線圈表示傳感器節(jié)點(diǎn)的覆蓋范圍[13]。

圖5 三個(gè)傳感器節(jié)點(diǎn)的初始狀態(tài)

圖6 三個(gè)傳感器節(jié)點(diǎn)的局部最大化覆蓋

2.3 解鎖方法

在移動(dòng)傳感器節(jié)點(diǎn)的掃描過(guò)程中，面對(duì)障礙物的阻攔時(shí)需要改變位移的路徑[14]。掃描過(guò)程中有可能會(huì)出現(xiàn)路徑交叉的情況，這樣會(huì)延長(zhǎng)完成覆蓋的時(shí)間[15]。為了解決交叉路徑問(wèn)題，完成最短時(shí)間的優(yōu)化，本文在交叉點(diǎn)的位置補(bǔ)充了兩個(gè)移動(dòng)的位置。這樣就可以達(dá)到解鎖的目的，完成最短時(shí)間的最大覆蓋優(yōu)化。如圖7所示，移動(dòng)傳感節(jié)點(diǎn)的四個(gè)位置出現(xiàn)交叉，此時(shí)本文在交叉點(diǎn)位置加上了兩個(gè)移動(dòng)位置完成解鎖，如圖8所示。

圖7 初始位置 圖8 解鎖

Fig.7InitialpositionFig.8Nodepositionafterunlock

為了能夠清晰地表示出該方法如何解鎖，本文給出了一般情況下的解鎖方法。

步驟1 假設(shè)移動(dòng)傳感器節(jié)點(diǎn)的路徑為x1,x2,…,xm，其中路徑線段xixi+1和xjxj+1存在交叉點(diǎn)。

步驟2 假設(shè)路徑線段的交叉點(diǎn)為xinter，那么將xinter分別加入到xixi+1和xjxj+1兩個(gè)路徑線段之間。

步驟3 將交叉點(diǎn)加入到路徑線段之后，對(duì)移動(dòng)傳感器節(jié)點(diǎn)的路徑重新排序如下所示：xi,xinter,xj,xj-1,xj-2,…,xi+2,xi+1,xinter,xj+1。

步驟4 重復(fù)步驟1到步驟3，直至路徑中不存在交叉點(diǎn)。

一般解鎖方法如圖9所示。

圖9 一般解鎖方法

3 掃描覆蓋算法設(shè)計(jì)

掃描覆蓋問(wèn)題的目標(biāo)是以最少數(shù)量的移動(dòng)傳感器達(dá)到最大的覆蓋面積。在掃描覆蓋問(wèn)題的相關(guān)場(chǎng)合中，決策者在目標(biāo)區(qū)域布置少許的移動(dòng)傳感器節(jié)點(diǎn)進(jìn)行周期性的覆蓋，代替了大規(guī)模固定式傳感器節(jié)點(diǎn)覆蓋的間隔需要。由于目標(biāo)區(qū)域覆蓋所需的節(jié)點(diǎn)數(shù)量減少，目標(biāo)區(qū)域覆蓋所需的工作成本也隨之降低。

在傳感器節(jié)點(diǎn)覆蓋功能的水平集框架中，目標(biāo)區(qū)域被描述的正值表示在覆蓋區(qū)域的障礙外，負(fù)值表示在障礙物內(nèi)，零值表示在障礙物的邊界。傳感器節(jié)點(diǎn)直線前進(jìn)遇到障礙物時(shí)，會(huì)導(dǎo)致覆蓋范圍丟失，如果目標(biāo)區(qū)域中的點(diǎn)和傳感器節(jié)點(diǎn)的線段不相交于任何障礙物，那么該目標(biāo)區(qū)域的點(diǎn)就會(huì)被傳感器節(jié)點(diǎn)所覆蓋。本文考慮了傳感器節(jié)點(diǎn)的有限覆蓋范圍，使用單個(gè)移動(dòng)傳感器節(jié)點(diǎn)代替多個(gè)固定傳感器節(jié)點(diǎn)對(duì)目標(biāo)區(qū)域進(jìn)行掃描覆蓋。對(duì)于存在障礙物的目標(biāo)區(qū)域，本文通過(guò)移動(dòng)傳感器節(jié)點(diǎn)的路徑規(guī)劃方法實(shí)現(xiàn)最大化覆蓋。掃描算法設(shè)計(jì)如下：

步驟1 將多個(gè)固定傳感器節(jié)點(diǎn)，依次地加入到目標(biāo)區(qū)域中，按照幾何方式布置達(dá)到全覆蓋。

步驟2 存在障礙物的情況下，利用單個(gè)移動(dòng)傳感器節(jié)點(diǎn)代替多個(gè)固定傳感器節(jié)點(diǎn)，按原路徑進(jìn)行掃描覆蓋。

步驟3 根據(jù)路徑規(guī)劃，使得移動(dòng)傳感器節(jié)點(diǎn)達(dá)到最大覆蓋，通過(guò)位移多個(gè)節(jié)點(diǎn)所掃描的位置，達(dá)到節(jié)點(diǎn)的最大化覆蓋面積，并且刪除冗余的節(jié)點(diǎn)。

步驟4 按照最短路徑算法Dijkstra，利用移動(dòng)傳感器節(jié)點(diǎn)求出全覆蓋下的最優(yōu)路徑。

步驟5 如果初始化路徑中存在交叉路徑，那么使用解鎖方法來(lái)達(dá)到收斂。

步驟6 計(jì)算原有路徑長(zhǎng)度和掃描覆蓋之后的路徑長(zhǎng)度，進(jìn)行比較。如果優(yōu)化之后的路徑長(zhǎng)度較短，那就說(shuō)明本文掃描覆蓋方法的有效性；反之，則效果不佳。

4 仿真實(shí)驗(yàn)及性能評(píng)估

4.1 實(shí)驗(yàn)參數(shù)設(shè)置

本文采用Matlab2012b仿真平臺(tái)來(lái)進(jìn)行仿真。平臺(tái)是基于IntelCorei5-2300的CPU，4GB的運(yùn)行內(nèi)存的PC。為了表示傳感器節(jié)點(diǎn)的覆蓋性能，本文分別在沒(méi)有障礙物的情況和存在障礙物的情況下進(jìn)行分析。

1)無(wú)障礙物場(chǎng)景下的參數(shù)設(shè)置。

假定在20m×20m的目標(biāo)區(qū)域內(nèi)，依次布置的固定式傳感器節(jié)點(diǎn)數(shù)N=16，節(jié)點(diǎn)的理想探測(cè)半徑為r=6。無(wú)障礙物的仿真參數(shù)如表2所示。

表2 無(wú)障礙物場(chǎng)景下的仿真參數(shù)

2)有障礙物場(chǎng)景下的參數(shù)設(shè)置。

表3 有障礙物場(chǎng)景下的仿真參數(shù)

4.2 實(shí)驗(yàn)結(jié)果對(duì)比

1)無(wú)障礙物場(chǎng)景。

本文使用16個(gè)固定式傳感器節(jié)點(diǎn)依次部署在20 m×20 m的目標(biāo)區(qū)域中，達(dá)到全覆蓋的效果，如圖10所示。

接下來(lái)本文利用單個(gè)移動(dòng)傳感器節(jié)點(diǎn)按照原來(lái)的路徑進(jìn)行掃描，掃描過(guò)程按照幾何的方法進(jìn)行。如圖11所示，移動(dòng)傳感器節(jié)點(diǎn)移動(dòng)了16次位置，并且存在冗余覆蓋面積。接下來(lái)本文會(huì)使用優(yōu)化的掃描覆蓋算法來(lái)對(duì)移動(dòng)次數(shù)優(yōu)化，防止移動(dòng)傳感器節(jié)點(diǎn)的能量耗盡。

由圖11可知，移動(dòng)傳感器節(jié)點(diǎn)代替固定傳感器節(jié)點(diǎn)進(jìn)行掃描覆蓋完成后，明顯存在冗余節(jié)點(diǎn)位置，冗余覆蓋。使用本文提出的掃描覆蓋算法，進(jìn)行路徑規(guī)劃，并且將冗余節(jié)點(diǎn)位置去除。這樣可以達(dá)到移動(dòng)傳感器節(jié)點(diǎn)以最少時(shí)間、最短路徑，達(dá)到最大化覆蓋面積的效果。如圖12可知，移動(dòng)傳感器節(jié)點(diǎn)移動(dòng)了10次位置，達(dá)到了全覆蓋的效果。

圖10 16個(gè)固定節(jié)點(diǎn)的全覆蓋

圖11 移動(dòng)傳感器節(jié)點(diǎn)路徑覆蓋16個(gè)固定傳感器節(jié)點(diǎn)

圖12 優(yōu)化掃描覆蓋的路徑

2)有障礙物場(chǎng)景。

在含有障礙物的情況下，該算法先假設(shè)障礙物不存在，使用36個(gè)固定傳感器節(jié)點(diǎn)依次部署在30 m×30 m的目標(biāo)區(qū)域中，達(dá)到全覆蓋的效果，如圖13所示。

接下來(lái)利用單個(gè)移動(dòng)傳感器節(jié)點(diǎn)按照原來(lái)的路徑進(jìn)行掃描，掃描過(guò)程按照幾何的方法進(jìn)行。如圖14所示，移動(dòng)傳感器節(jié)點(diǎn)移動(dòng)了36次位置，并且存在冗余覆蓋面積。接下來(lái)本文會(huì)使用優(yōu)化的掃描覆蓋算法來(lái)對(duì)移動(dòng)次數(shù)優(yōu)化，防止移動(dòng)傳感器節(jié)點(diǎn)的能量耗盡，來(lái)延長(zhǎng)網(wǎng)絡(luò)壽命。

此時(shí)加入障礙物，也就相當(dāng)于在復(fù)雜地形下，移動(dòng)傳感器節(jié)點(diǎn)的路徑位置，如圖15所示障礙物阻擋了多個(gè)傳感器節(jié)點(diǎn)位置的感知面積。

圖13 36個(gè)固定節(jié)點(diǎn)的全覆蓋

圖14 移動(dòng)傳感器節(jié)點(diǎn)路徑覆蓋36個(gè)固定傳感器節(jié)點(diǎn)

圖15 存在障礙物的移動(dòng)路徑

經(jīng)過(guò)掃描覆蓋優(yōu)化方法之后，去除冗余的移動(dòng)傳感器節(jié)點(diǎn)位置，減小了移動(dòng)路徑的長(zhǎng)度，縮短了移動(dòng)到全覆蓋的時(shí)間，移動(dòng)傳感器節(jié)點(diǎn)位移了33次，如圖16所示。

4.3 計(jì)算開(kāi)銷性能和路徑長(zhǎng)度

圖16 優(yōu)化的移動(dòng)路徑

表4 有無(wú)障礙情況下的參數(shù)對(duì)比

Tab.4 Parameter comparison with/without obstacles

場(chǎng)景路徑網(wǎng)絡(luò)區(qū)域范圍/(m×m)固定傳感器節(jié)點(diǎn)數(shù)感知半徑/m通信半徑/m節(jié)點(diǎn)的移動(dòng)次數(shù)移動(dòng)路徑長(zhǎng)度/m無(wú)障礙物有障礙物原始路徑20×20166121660．00優(yōu)化路徑20×20166121036．27原始路徑30×303652/25236175．00優(yōu)化路徑30×303652/25233164．48

4.4 仿真對(duì)比

與傳統(tǒng)掃描覆蓋[5]相比，本文采用的是單個(gè)移動(dòng)傳感器節(jié)點(diǎn)掃描覆蓋，通過(guò)路徑規(guī)劃使得節(jié)點(diǎn)達(dá)到最大覆蓋面積，而不是用多個(gè)移動(dòng)傳感器節(jié)點(diǎn)實(shí)行編隊(duì)掃描覆蓋，后者大幅增加了成本，也增加了能耗。下面對(duì)本文提出的單個(gè)移動(dòng)傳感器節(jié)點(diǎn)掃描覆蓋方法和雙節(jié)點(diǎn)編隊(duì)的掃描覆蓋方法進(jìn)行仿真對(duì)比。如圖17所示，本文采用單個(gè)移動(dòng)傳感器節(jié)點(diǎn)和兩個(gè)節(jié)點(diǎn)作對(duì)比，評(píng)估它們每個(gè)節(jié)點(diǎn)的時(shí)間和能耗。如圖18所示，在有限的時(shí)間內(nèi)本文提出的單移動(dòng)傳感器節(jié)點(diǎn)和雙移動(dòng)傳感器節(jié)點(diǎn)編隊(duì)的覆蓋率作出了對(duì)比。

圖17 能耗仿真對(duì)比

根據(jù)圖17的仿真結(jié)果，在相同時(shí)間內(nèi)本文提出的單個(gè)移動(dòng)傳感器節(jié)點(diǎn)，沒(méi)有節(jié)點(diǎn)之間的編隊(duì)和通信，減少了能量消耗，延長(zhǎng)了節(jié)點(diǎn)的生命周期。這樣可以確保移動(dòng)傳感器節(jié)點(diǎn)在維持覆蓋的時(shí)間上能夠延長(zhǎng)。根據(jù)圖18的仿真結(jié)果可知，隨著時(shí)間的增加，單移動(dòng)傳感器節(jié)點(diǎn)和雙移動(dòng)傳感器節(jié)點(diǎn)的覆蓋率都在增加，其中雙移動(dòng)節(jié)點(diǎn)的覆蓋率較高些。

圖18 覆蓋率仿真對(duì)比

相比之下，雖然雙移動(dòng)傳感器節(jié)點(diǎn)的覆蓋率較高些，但是它的兩個(gè)節(jié)點(diǎn)之間需要進(jìn)行編隊(duì)和通信消耗了部分能量，每個(gè)節(jié)點(diǎn)能耗是單移動(dòng)傳感器節(jié)點(diǎn)的近乎兩倍。為了延長(zhǎng)節(jié)點(diǎn)的生命周期，在滿足覆蓋維持的前提下，可以選擇單移動(dòng)傳感器節(jié)點(diǎn)對(duì)目標(biāo)區(qū)域進(jìn)行掃描覆蓋。

5 結(jié)語(yǔ)

本文提出了一種優(yōu)化的掃描覆蓋。在目標(biāo)區(qū)域中，使用單個(gè)移動(dòng)傳感器節(jié)點(diǎn)來(lái)代替固定傳感器節(jié)點(diǎn)，對(duì)目標(biāo)區(qū)域進(jìn)行掃描修復(fù)。通過(guò)節(jié)點(diǎn)的路徑規(guī)劃，使得節(jié)點(diǎn)的覆蓋面最大化，同時(shí)掃描覆蓋的路徑最短。實(shí)驗(yàn)結(jié)果表明，本文提出的算法在適度降低覆蓋率的情況下，可大幅降低移動(dòng)能耗。

References)

[1] 王偉，林鋒，周激流.Sweep Coverage中的節(jié)點(diǎn)移動(dòng)控制[J].四川大學(xué)學(xué)報(bào)(自然科學(xué)版),2010,47(5):1015-1019.(WANG W, LIN F, ZHOU J L.Controlling the mobility of sensors in sweep coverage [J].Journal of Sichuan University (Natural Science Edition), 2010, 47(5): 1105-1109.)

[2] 雍毅，林鋒，周激流.基于Dynamic POIs的Sweep Coverage節(jié)點(diǎn)移動(dòng)算法[J].四川大學(xué)學(xué)報(bào)(自然科學(xué)版),2012,49(4):795-799.(YONG Y, LIN F, ZHOU J L.Controlling the mobility of sensors in sweep coverage based on dynamic POIS [J].Journal of Sichuan University (Natural Science Edition), 2012, 49(4): 795-799.)

[3] 李小康，林鋒，周激流.一種Sweep coverage問(wèn)題的插入啟發(fā)式算法[J].四川大學(xué)學(xué)報(bào)(自然科學(xué)版),2015,52(1):74-78.(LI X K, LIN F, ZHOU J L.A novel insert heuristic algorithm for sweep coverage problem [J].Journal of Sichuan University (Natural Science Edition), 2015, 52(1): 74-78.)

[4] 劉晨光，林鋒，周激流.一種基于A-means聚類算法的Sweep coverage機(jī)制[J].計(jì)算機(jī)應(yīng)用研究,2012,29(3):1051-1053.(LIU C G, LIN F, ZHOU J L.Sweep coverage approach with A-means clustering algorithm [J].Application Research of Computers, 2012, 29(3): 1051-1053.)

[5] 舒莉，林鋒，劉中豪,等.基于興趣點(diǎn)分類的無(wú)線傳感器網(wǎng)絡(luò)掃描覆蓋機(jī)制[J].西南交通大學(xué)學(xué)報(bào),2014,49(1):165-172.(SHU L, LIN F, LIU Z H.POI classfication based sweep coverage scheme in wireless sensor networks [J].Journal of Southwest Jiaotong University, 2014, 49(1): 165-172.)

[6] 林鋒，王偉，周激流.MASC:一種基于移動(dòng)輔助節(jié)點(diǎn)的Sweep Coverage機(jī)制[J].四川大學(xué)學(xué)報(bào)(工程科學(xué)版),2010,42(6):119-125.(LIN F, WANG W, ZHOU J L.MASC: a sweep coverage approach with mobile-assisted carriers [J].Journal of Sichuan University (Engineering Science Edition), 2010, 42(6): 119-125.)[7] 張洪德,石為人,楊磊,等.基于粒子均衡的移動(dòng)傳感器網(wǎng)絡(luò)覆蓋控制研究[J].儀器儀表學(xué)報(bào),2016,37(5):1049-1057.(ZHANG H D, SHI W R, YANG L, et al.Study on equilibrium of particle based coverage control for mobile sensor network [J].Chinese Journal of Scientific Instrument, 2016, 37(5): 1049-1057.)

[8] XIAO Y L, KAI L W, YANMIN Z, et al.Mobility increases the surface coverage of distributed sensor networks [J].Computer Networks, 2013, 57(11): 2348-2361.

[9] 方如舉,王建平,孫偉.無(wú)線傳感器網(wǎng)絡(luò)通信的擁塞控制策略[J].電子測(cè)量與儀器學(xué)報(bào),2016,30(4):558-567.(FANG R J, WANG J P, SUN W.The congestion control strategy for WSNs communication [J].Journal of Electronic Measurement and Instrumentation, 2016, 30(4): 558-567.)

[10] 徐雪松,楊勝杰,陳榮元.復(fù)雜環(huán)境移動(dòng)群機(jī)器人最優(yōu)路徑規(guī)劃方法[J].電子測(cè)量與儀器學(xué)報(bào),2016,30(2):274-282.(XU X S, YAN S J, CHEN R Y.Dynamic differential evolution algorithm for swarm robots search path planning [J].Journal of Electronic Measurement and Instrumentation, 2016, 30(2): 274-282.)

[11] MA H-C, SAHOO P K, CHEN Y-W.Computational geometry based distributed coverage hole detection protocol for the wireless sensor networks [J].Journal of Network and Computer Applications, 2011, 34(5): 1743-1756.

[12] 張建軍,陳曉,趙意.一種無(wú)線傳感器節(jié)點(diǎn)動(dòng)態(tài)采樣策略[J].電子測(cè)量與儀器學(xué)報(bào),2016,30(2):249-255.(ZHANG J J, CHEN X, ZHAO Y.Dynamic sampling control strategy for wireless sensor nodes [J].Journal of Electronic Measurement and Instrumentation, 2016, 30(2): 249-255.)

[13] SUNG H K, SEONG J K, HAOMIN Z.Path optimization with limited sensing ability [J].Journal of Computational Physics, 2015, 299: 887-901.

[14] 鄧亞平，吳川平.基于移動(dòng)節(jié)點(diǎn)的無(wú)線傳感器網(wǎng)絡(luò)中的瓶頸節(jié)點(diǎn)[J].計(jì)算機(jī)應(yīng)用,2011,31(7):1939-1943.(DENG Y P, WU C P.Bottleneck nodes in wireless sensor networks based on mobile sensors [J].Journal of Computer Applications, 2011, 31(7): 1939-1943.)

[15] GORAIN B, MANDAL P S.Approximation algorithms for sweep coverage in wireless sensor networks [J].Journal of Parallel and Distributed Computing, 2014, 74(8): 2699-2707.

This work is partially supported by National Natural Science Foundation of China (E050603), Scientific Research Project of Guangxi Higher Education Institutions (YB2014157), Natural Science Foundation of Guangxi (2015GXNSFBA139254).

SHEN Xianhao, born in 1980, Ph.D., associate professor.His research interests include intelligent fault diagnosis, wireless sensor network.

LI Jun, born in 1990, M.S.candidate.His research interests include wireless sensor network.

NAI He, born in 1992, M.S.candidate.His research interests include wireless sensor network.

Sweep coverage optimization algorithm for mobile sensor node with limited sensing

SHEN Xianhao, LI Jun*, NAI He

(GuangxiUniversitiesKeyLaboratoryofEmbeddedTechnologyandIntelligentInformationProcessing(GuilinUniversityofTechnology),

In the applications of mobile Wireless Sensor Network (WSN), since the sensing range of the sensor nodes is limited, the coverage analysis is a scan coverage problem for the target area.In this paper, a new scan coverage algorithm based on multi-objective optimization was proposed.In the target area, the double objective optimization strategy was used on path planning for a single mobile sensor node, which could maximize the coverage of the node and make scan coverage path to the shortest.Simulation experiments were carried out under the conditions with obstacles and without obstacles.Compared with the formation coverage algorithm for multiple nodes, the proposed algorithm can significantly reduce the mobile energy consumption while moderately reducing coverage rate.

mobile sensor node; sweep coverage; double objective optimization; coverage rate; energy consumption

2016-07-26;

2016-08-06。 基金項(xiàng)目:國(guó)家自然科學(xué)基金資助項(xiàng)目(E050603)；廣西高等學(xué)?？蒲许?xiàng)目(YB2014157)；廣西自然科學(xué)基金資助項(xiàng)目(2015GXNSFBA139254)。

神顯豪(1980—)，男，廣西橫縣人，副教授，博士，主要研究方向：智能故障診斷、無(wú)線傳感器網(wǎng)絡(luò)； 李軍(1990—)，男，安徽滁州人，碩士研究生，主要研究方向：無(wú)線傳感器網(wǎng)絡(luò)； 奈何(1992—)，男，湖北襄陽(yáng)人，碩士研究生，主要研究方向：無(wú)線傳感器網(wǎng)絡(luò)。

1001-9081(2017)01-0060-05DOI:10.11772/j.issn.1001-9081.2017.01.0060

TP

A