有向移動異構(gòu)傳感網(wǎng)分布式部署策略*

余穎華，李　艷，吳德恩，秦寧寧，3*

（1.江南大學(xué)物聯(lián)網(wǎng)工程學(xué)院，江蘇無錫214122；2.無錫商業(yè)職業(yè)技術(shù)學(xué)院物聯(lián)網(wǎng)技術(shù)學(xué)院，江蘇無錫214153；3.江南大學(xué)輕工過程先進(jìn)控制教育部重點(diǎn)實(shí)驗(yàn)室，江蘇無錫214122）

有向移動異構(gòu)傳感網(wǎng)分布式部署策略*

余穎華1，李艷2，吳德恩1，秦寧寧1，3*

（1.江南大學(xué)物聯(lián)網(wǎng)工程學(xué)院，江蘇無錫214122；2.無錫商業(yè)職業(yè)技術(shù)學(xué)院物聯(lián)網(wǎng)技術(shù)學(xué)院，江蘇無錫214153；3.江南大學(xué)輕工過程先進(jìn)控制教育部重點(diǎn)實(shí)驗(yàn)室，江蘇無錫214122）

針對移動異構(gòu)有向傳感網(wǎng)的覆蓋增強(qiáng)問題，提出了一種基于虛擬全向感知圓的節(jié)點(diǎn)分布式部署策略DDS（Distributed Deployment Strategy）。DDS采用等面積虛擬全向感知圓替代有向節(jié)點(diǎn)感知扇形，根據(jù)不同感知圓之間的位置與半徑大小關(guān)系為每個有向節(jié)點(diǎn)合理構(gòu)建區(qū)域覆蓋子區(qū)間，最后由該子區(qū)間多邊形的形心確定節(jié)點(diǎn)的候選位置坐標(biāo)。同時，DDS策略充分利用有向節(jié)點(diǎn)的旋轉(zhuǎn)特性，計(jì)算節(jié)點(diǎn)視角方向使其面向檢測區(qū)域外側(cè)。節(jié)點(diǎn)通過視角調(diào)整和合理移動，不斷提高網(wǎng)絡(luò)覆蓋率。仿真結(jié)果表明，DDS在提高網(wǎng)絡(luò)覆蓋率，增強(qiáng)節(jié)點(diǎn)分布均衡性方面具有明顯的優(yōu)勢。

有向傳感網(wǎng)；虛擬全向感知圓；覆蓋子區(qū)間；覆蓋率

移動傳感器網(wǎng)絡(luò)［1］是由部署在目標(biāo)區(qū)域內(nèi)的大量移動傳感器節(jié)點(diǎn)組成的一個多跳自組織網(wǎng)絡(luò)，被廣泛運(yùn)用于環(huán)境感知、軍事安全、醫(yī)療監(jiān)控等多個領(lǐng)域。

在現(xiàn)有的移動傳感器網(wǎng)絡(luò)覆蓋部署研究中，大量算法主要針對以全向感知模型為基礎(chǔ)的傳統(tǒng)網(wǎng)絡(luò)。在全向感知模型中，目標(biāo)點(diǎn)是否被節(jié)點(diǎn)感知僅與二者之間的距離有關(guān)，與方向無關(guān)，可用于對溫度、濕度、濃度等信息采集的場景。然而，對于相機(jī)、超聲波、視頻監(jiān)控等傳感器，節(jié)點(diǎn)受自身物理特性的限制，對目標(biāo)點(diǎn)的感知性能是分方向的，即節(jié)點(diǎn)具有固定的感知方向。目前，以有向感知模型為基礎(chǔ)的有向網(wǎng)絡(luò)部署問題，研究成果還相對缺乏。文獻(xiàn)［2］較早提出了有向傳感器的概念以及有向感知節(jié)點(diǎn)的4-維感知模型，開啟了直接面向有向傳感器網(wǎng)絡(luò)的研究工作。文獻(xiàn)［3］進(jìn)一步將基本的有向感知模型擴(kuò)展為視覺方向可調(diào)感知模型，提出了一種基于虛擬勢場的有向傳感器網(wǎng)絡(luò)覆蓋增強(qiáng)算法PFCEA（Potential Field Based Coverage-Enhancing Algorithm）。通過引入感知模型“質(zhì)心”的概念，將有向傳感器網(wǎng)絡(luò)的覆蓋增強(qiáng)問題轉(zhuǎn)化為虛擬勢場作用下質(zhì)心點(diǎn)的均勻分布問題，網(wǎng)絡(luò)部署成本以及計(jì)算復(fù)雜度得到了極大降低，但由于算法性能易受節(jié)點(diǎn)位置影響，覆蓋率提升空間相對有限。Liang等人［4］率先提出有向移動傳感器網(wǎng)絡(luò)的部署問題［5］，針對同構(gòu)有向可移動節(jié)點(diǎn)，分別設(shè)計(jì)了基于扇形感知模型內(nèi)切圓圓心和外接圓圓心的兩種解決方案，可有效提高網(wǎng)絡(luò)覆蓋率，但忽略了節(jié)點(diǎn)感知視角大小對網(wǎng)絡(luò)部署效果的影響，適用性較差。針對移動異構(gòu)有向傳感器網(wǎng)絡(luò)，文獻(xiàn)［6］提出了一種基于虛擬力［7］的最優(yōu)部署算法 OPT（Optimized Deployment Algorithm），將節(jié)點(diǎn)移動特性和旋轉(zhuǎn)特性相結(jié)合，極大提高了網(wǎng)絡(luò)覆蓋效果，但每個節(jié)點(diǎn)的受力計(jì)算需要全網(wǎng)節(jié)點(diǎn)信息，通信能耗大，計(jì)算復(fù)雜度高。

基于上述分析，針對有向移動異構(gòu)傳感網(wǎng)的覆蓋問題［8］，論文提出了一種分布式部署策略DDS。該策略根據(jù)有向節(jié)點(diǎn)的覆蓋特征求其全向虛擬替代感知圓，并依據(jù)相鄰虛擬替代感知圓的幾何空間位置，為每個節(jié)點(diǎn)劃分覆蓋子區(qū)域，當(dāng)且僅當(dāng)節(jié)點(diǎn)的位置更新可提高對自身所在子區(qū)域的覆蓋面積時，節(jié)點(diǎn)才能移動。同時，各個節(jié)點(diǎn)根據(jù)自身在目標(biāo)區(qū)域的位置調(diào)整感知方向，以確保網(wǎng)絡(luò)中所有節(jié)點(diǎn)的感知視角面向檢測區(qū)域邊界。節(jié)點(diǎn)通過逐輪移動和旋轉(zhuǎn)，最終使得整個網(wǎng)絡(luò)覆蓋面積最大化。

1　DDS應(yīng)用前提

1.1感知模型

論文所用有向感知模型［9］是一個以節(jié)點(diǎn)位置坐標(biāo)為圓心，以感知距離為半徑的扇形區(qū)域［10］。如圖1示，有向感知模型可用一個五元組表示。

圖1 有向感知模型

圖1中，p指代節(jié)點(diǎn)的位置坐標(biāo)（x，y），v表示與扇形中軸線重合的感知方向向量，r表示節(jié)點(diǎn)感知半徑，α表示節(jié)點(diǎn)感知視角大小，β表示節(jié)點(diǎn)感知方向角。

1.2網(wǎng)絡(luò)運(yùn)行環(huán)境

1.3虛擬替代感知圓

在以往有向傳感網(wǎng)的部署工作中，常采用全向圓替代有向節(jié)點(diǎn)感知扇形，以簡化部署過程。隨著節(jié)點(diǎn)si感知視角αi的大小變化，si感知扇形常用三

種替代感知圓：內(nèi)切圓（虛實(shí)線）、外接圓（實(shí)線）、質(zhì)心圓（虛線）的替代效果如圖2所示。

圖2　不同感知角度下三種虛擬替代感知圓

由圖2可知，當(dāng)節(jié)點(diǎn)感知視角較小時，外接圓和內(nèi)切圓的替代效果相對較好，質(zhì)心圓的替代效果最差；而當(dāng)節(jié)點(diǎn)感知角度較大時，質(zhì)心圓的替代效果變好，而內(nèi)切圓與外接圓的替代效果相對變差。因此當(dāng)異構(gòu)網(wǎng)絡(luò)節(jié)點(diǎn)的感知視角差異較大時，上述三種虛擬感知圓的替代效果均不理想。

求解可得Ri≈ri。

考慮到質(zhì)心作為物體質(zhì)量的集中點(diǎn)，是質(zhì)量分布均勻扇形的幾何中心，因選定si扇形的質(zhì)心Oi作為其替代圓ci的圓心位置。其中質(zhì)心點(diǎn)Oi的坐標(biāo)（xOi，yOi）的計(jì)算公式如下所示：

此時，以si感知扇形的質(zhì)心Oi為圓心，以Ri=為半徑的圓ci即為節(jié)點(diǎn)si的等面積虛擬替代感知圓。當(dāng)si的感知視角αi分別為，時，ci的替代效果如圖3所示。

圖3　不同感知角度下ci的替代效果

1.4改進(jìn)Voronoi圖

Voronoi圖［11-12］是由一組通過連接兩鄰點(diǎn)直線的垂直平分線圍成的連續(xù)多邊形組成，多被用于節(jié)點(diǎn)感知半徑均等的全向傳感器網(wǎng)絡(luò)中。

針對感知半徑不均衡的全向傳感器網(wǎng)絡(luò)，文獻(xiàn)［13］提出了一種改進(jìn)Voronoi圖劃分方法。在平面Ω上任意給定兩全向節(jié)點(diǎn) Sm，Sn，坐標(biāo)分別為pm，pn。以兩節(jié)點(diǎn)連線的垂線為界對平面Ω進(jìn)行劃分，Sm所得責(zé)任半平面內(nèi)任一點(diǎn)t的坐標(biāo)p滿足如下條件：

其中dm為Sm到分割線的歐氏距離，其取值由Sm，Sn之間的歐氏距離以及二者感知圓半徑rm，rn共同決定。由節(jié)點(diǎn)Sm與其各個相鄰節(jié)點(diǎn)間的區(qū)間劃分線所圍成的凸多邊形即為Sm所劃分到的改進(jìn)Voronoi多邊形。

采用改進(jìn)Voronoi圖劃分目標(biāo)檢測區(qū)域，結(jié)果如圖4所示。由圖4可知，當(dāng)節(jié)點(diǎn)感知圓完全包含在其他節(jié)點(diǎn)的感知范圍內(nèi)時，則該節(jié)點(diǎn)將不被分配到覆蓋子區(qū)間，如節(jié)點(diǎn)S6，此時記=Φ。在改進(jìn)Voronoi圖中，節(jié)點(diǎn)感知半徑差異會造成目標(biāo)區(qū)域內(nèi)部分小區(qū)域不被分割給任何節(jié)點(diǎn)，如圖中陰影部分。當(dāng)節(jié)點(diǎn)感知半徑相同時，每個陰影區(qū)域縮減為一個點(diǎn)，改進(jìn)Voronoi圖還原成標(biāo)準(zhǔn)的Voronoi圖。

圖4　改進(jìn)Voronoi圖分割

2　DDS策略

2.1節(jié)點(diǎn)移動策略

為最大化網(wǎng)絡(luò)區(qū)域覆蓋面積，論文提出了在DDS指導(dǎo)下的節(jié)點(diǎn)部署策略。在DDS作用下，各節(jié)點(diǎn)受到其所劃分多邊形形心引力 CPF（Centroid Pull Force）的作用，迫使節(jié)點(diǎn)向多邊形形心移動。節(jié)點(diǎn)通過逐輪移動，最終均勻分布在目標(biāo)區(qū)域內(nèi)。

圖5　節(jié)點(diǎn)所受質(zhì)心引力

如圖5所示，檢測區(qū)域內(nèi)節(jié)點(diǎn)si的位置坐標(biāo)pi=（xi，yi），基于式（2）得si虛擬替代感知圓ci的圓心Oi的坐標(biāo) pOi=（xOi，yOi）。si覆蓋子區(qū)間多邊形V?i的形心記為OVi，其坐標(biāo)。此時si受到來自的引力CPFi的作用，表達(dá)式：

設(shè)si位于點(diǎn)pi和p′時對的覆蓋面積分別為Ai和Ai′，若Ai＞Ai′，則si移動到新位置p′，否則，si保持不動。以此類推，網(wǎng)絡(luò)節(jié)點(diǎn)受改進(jìn)Voronoi多邊形形心的引力作用，向所屬覆蓋子區(qū)間的形心靠攏，不斷提高對所對應(yīng)子區(qū)間的覆蓋面積，實(shí)現(xiàn)整個網(wǎng)絡(luò)覆蓋率的提高。

2.2旋轉(zhuǎn)力矩

有向節(jié)點(diǎn)的感應(yīng)范圍已不再是各向均一的圓盤，感知方向的朝向差異也影響覆蓋范圍，這一點(diǎn)在邊界附近的節(jié)點(diǎn)覆蓋中更加明顯。

對網(wǎng)絡(luò)中任一節(jié)點(diǎn)si，文獻(xiàn)［6］曾給出了基于節(jié)點(diǎn)坐標(biāo)位置的感知力矩Tib的求解方法，即

圖6　節(jié)點(diǎn)感知方向旋轉(zhuǎn)前后

對于靠近檢測區(qū)域邊界處的某一節(jié)點(diǎn)si，按照式（6）求取旋轉(zhuǎn)力矩Tib，si感知方向按照Tib進(jìn)行調(diào)整后，其虛擬替代感知圓的圓心將位于檢測區(qū)域外，使得si無法分配到覆蓋子區(qū)間，從而導(dǎo)致si無法再次移動。而此時si有效感知扇形區(qū)域的絕大部分位于檢測目標(biāo)區(qū)域外，最終造成網(wǎng)絡(luò)絕對感知面積不升反降的尷尬，如上圖6所示。

為防止節(jié)點(diǎn)旋轉(zhuǎn)后其虛擬替代感知圓的圓心脫離檢測區(qū)域，而最終導(dǎo)致節(jié)點(diǎn)移動部署策略失效的狀況發(fā)生，需對節(jié)點(diǎn)旋轉(zhuǎn)力矩Tib進(jìn)行選擇性使用，使用過程如下：

①若節(jié)點(diǎn)si到檢測區(qū)域Ω任意邊界線的距離不小于該節(jié)點(diǎn)到其虛擬替代感知圓圓心的距離，則節(jié)點(diǎn)感知方向旋轉(zhuǎn)Tib。

②若si到邊界線的距離小于到其虛擬替代感知圓ci圓心的距離，計(jì)算si按Tib旋轉(zhuǎn)后ci的圓心Oi。根據(jù)點(diǎn)Oi的分布情況，分兩種情況討論si的旋轉(zhuǎn)方案：

情況1若Oi∈Ω，則si按照Tib進(jìn)行旋轉(zhuǎn)。

情況2若Oi?Ω，則節(jié)點(diǎn)在本輪次中不做旋轉(zhuǎn)，即Tib=0。

上述修正既保證了絕大部分節(jié)點(diǎn)的感知視角面向檢測區(qū)域外，增大整個區(qū)域的覆蓋率，同時避免了個別情況下節(jié)點(diǎn)旋轉(zhuǎn)角度較大造成其替代感知圓圓心脫離檢測區(qū)域?qū)е乱苿硬呗允У那闆r。

2.3DDS步驟

針對目標(biāo)檢測區(qū)域Ω內(nèi)隨機(jī)部署的一個有向節(jié)點(diǎn)集合S ，為實(shí)現(xiàn)網(wǎng)絡(luò)節(jié)點(diǎn)對Ω的最大覆蓋，DDS策略主要包含兩大部分：①各個節(jié)點(diǎn)在旋轉(zhuǎn)力矩的作用下進(jìn)行逐輪逐步旋轉(zhuǎn)；②各個節(jié)點(diǎn)受形心引力的作用進(jìn)行逐輪移動。為避免不必要的能量損耗，當(dāng)且僅當(dāng)節(jié)點(diǎn)移動后可提高對其所在覆蓋子區(qū)間的覆蓋面積時，節(jié)點(diǎn)才能移動，否則節(jié)點(diǎn)在本輪次保持原位置。DDS算法實(shí)現(xiàn)步驟如下：

DDS策略2-1Ω內(nèi)N個傳感器有向節(jié)點(diǎn)S=｛s1，s2，…，sN｝，節(jié)點(diǎn)位置坐標(biāo)｛?。齪i［k］Ni=1，感知半徑｛?。齬i［k］Ni=1。初始迭代k=0，最大迭代門限kmax，坐標(biāo)節(jié)點(diǎn)移動標(biāo)志flag=1，移動系數(shù)αi=0.2，每輪移動節(jié)點(diǎn)數(shù)目sum。2-2　whilek＜kmax&sum≠0 2-3　sum=0 2-4　forsi∈S 2-5　計(jì)算感知方向旋轉(zhuǎn)力矩Tib′［k］，并按照Tib′［k］進(jìn)行旋轉(zhuǎn)2-6　節(jié)點(diǎn)感知方向旋轉(zhuǎn)后，計(jì)算虛擬替代感知圓ci［k］2-7　end for 2-8　forsi∈S 2-9　flag=0 2-10　廣播虛擬替代感知圓信息ci［k］，同時接收鄰居節(jié)點(diǎn)信息，構(gòu)造改進(jìn)Voronoi多邊形V?i［k］2-11　計(jì)算si所受形心引力CPFi［k］%基于式（4）2-12　求取si候選位置坐標(biāo)pi′［k］%基于式（5）2-13　計(jì)算si分別位于pi［k］和pi′時對V?i［k］的覆蓋面積A［k］和A′［k］2-14　ifA′［k］＞A［k］，2-15　更新節(jié)點(diǎn)si坐標(biāo)：pi［k+1］←pi′，k←k+1，flag=1 2-16　else　保留si當(dāng)前坐標(biāo)：pi［k+1］←pi［k］，k←k+1 2-17　end if 2-18　sum=sum+flag 2-19　end for 2-20　end while

3　仿真實(shí)驗(yàn)

3.1仿真環(huán)境

為驗(yàn)證DDS策略的有效性，采用MATLAB進(jìn)行仿真驗(yàn)證，并以文獻(xiàn)［6］中的OPT算法作為對比方案。初始狀態(tài)下，網(wǎng)絡(luò)所有節(jié)點(diǎn)隨機(jī)分布在檢測區(qū)域 Ω=4 m×4 m范圍內(nèi)。節(jié)點(diǎn)感知半徑范圍0.4m～0.9m，感知視角范圍，節(jié)點(diǎn)移動系數(shù)αi=0.2，迭代次數(shù)上限kmax=100。

3.2算法有效性分析

圖7給出了同構(gòu)和異構(gòu)網(wǎng)絡(luò)中，DDS和OPT算法部署的效果圖。在圖7（a）～7（c）考察了在節(jié)點(diǎn)數(shù)目 N=40，感知半徑 r=0.6，感知視角的同構(gòu)網(wǎng)絡(luò)中DDS策略和OPT算法下的部署情況。由圖7（b）可知，在OPT算法的部署作用下，節(jié)點(diǎn)感知扇形外接圓相對均衡地分布在目標(biāo)區(qū)域內(nèi)，但由于外接圓面積遠(yuǎn)大于扇形面積，產(chǎn)生較大的替代失真，網(wǎng)絡(luò)最終覆蓋率為66.30%，節(jié)點(diǎn)感知扇形之間存在嚴(yán)重的覆蓋冗余，覆蓋效果較差。DDS策略采用等面積虛擬感知圓代替感知扇形，當(dāng)節(jié)點(diǎn)感知視角較大時，依舊可以保持較好的替代效果。各節(jié)點(diǎn)通過等面積替代圓確定自身移動候選位置，不斷趨近自身所在子區(qū)間的形心，網(wǎng)絡(luò)覆蓋率由初始條件下的 47.32%最終提升到80.10%，如圖7（c）所示。

圖7（d）～7（f）比較了在節(jié)點(diǎn)數(shù)目N=40的異構(gòu)網(wǎng)絡(luò)中DDS策略和OPT算法的部署效果。在初始狀態(tài)下，網(wǎng)絡(luò)覆蓋率為40.98%，如圖7（d）。在OPT 和DDS作用下，網(wǎng)絡(luò)可獲得的最終覆蓋率分別為61.76%和65.99%，此時網(wǎng)絡(luò)中大感知視角傳感器節(jié)點(diǎn)的數(shù)目比重變小，但等面積虛擬替代感知圓較外接圓依舊表現(xiàn)出較好的替代優(yōu)越性。

圖7　DDS和OPT作用下的網(wǎng)絡(luò)覆蓋效果其中，（a）～（c）同構(gòu)，（d）～（f）異構(gòu)

3.3覆蓋率

為了考察異構(gòu)網(wǎng)絡(luò)規(guī)模大小對算法性能的影響，圖8統(tǒng)計(jì)了隨著節(jié)點(diǎn)數(shù)目變化，DDS策略和OPT算法作用下網(wǎng)絡(luò)覆蓋率的變化情況。由圖中曲線可知，隨著節(jié)點(diǎn)數(shù)目的增加，兩種算法中網(wǎng)絡(luò)覆蓋率均逐漸增大，但DDS下的網(wǎng)絡(luò)覆蓋效果始終優(yōu)于OPT算法，且當(dāng)節(jié)點(diǎn)數(shù)目在小于70時，DDS策略的覆蓋優(yōu)越性較明顯。這是由于當(dāng)節(jié)點(diǎn)數(shù)目極少時，網(wǎng)絡(luò)節(jié)點(diǎn)還不足以覆蓋整個目標(biāo)檢測區(qū)域，OPT算法采用感知扇形外接圓進(jìn)行網(wǎng)絡(luò)部署，大感知視角節(jié)點(diǎn)的替代效果較差，致使OPT覆蓋效果不佳，而DDS采用替代效果較好的等面積虛擬替代節(jié)點(diǎn)感知扇形，其部署優(yōu)越性得到了處分發(fā)揮；而當(dāng)節(jié)點(diǎn)數(shù)目較多時，兩種算法均已取得較高的覆蓋，網(wǎng)絡(luò)覆蓋率上升空間均較為有限。

圖8　網(wǎng)絡(luò)覆蓋率隨節(jié)點(diǎn)數(shù)目的變化

3.4能耗

在節(jié)點(diǎn)移動和旋轉(zhuǎn)過程中會消耗大量能量，節(jié)點(diǎn)移動距離和旋轉(zhuǎn)角度作為衡量算法有效性的兩個重要指標(biāo)，直接反映出算法能耗的大小。圖9比較了隨節(jié)點(diǎn)數(shù)目的增大，節(jié)點(diǎn)總移動距離和總旋轉(zhuǎn)角度的變化情況。由圖9可知，DDS策略和OPT算法下，網(wǎng)絡(luò)節(jié)點(diǎn)的總移動距離和旋轉(zhuǎn)角度數(shù)均隨節(jié)點(diǎn)數(shù)的增加而增大。由于DDS策略下節(jié)點(diǎn)的每次移動均以能提高對其自身所在覆蓋子區(qū)間的覆蓋面積為前提，避免了部署過程中的無效移動，使得在相同節(jié)點(diǎn)數(shù)目下，網(wǎng)絡(luò)節(jié)點(diǎn)移動總距離始終低于OPT算法。當(dāng)節(jié)點(diǎn)數(shù)目高于70以后，DDS中每個節(jié)點(diǎn)分配到的子區(qū)間變小，節(jié)點(diǎn)通過較少的移動即可達(dá)到終止條件，表現(xiàn)為節(jié)點(diǎn)移動距離曲線的斜率隨節(jié)點(diǎn)數(shù)目的增加逐漸減小。另外，由于節(jié)點(diǎn)每輪次的旋轉(zhuǎn)角度數(shù)由其當(dāng)前坐標(biāo)決定，當(dāng)節(jié)點(diǎn)位置改變較小時，其旋轉(zhuǎn)角度也相應(yīng)較小。

圖9　總旋轉(zhuǎn)角度和總移動距離隨節(jié)點(diǎn)數(shù)目的變化

3.5節(jié)點(diǎn)覆蓋效率

節(jié)點(diǎn)覆蓋效率CE用于反映節(jié)點(diǎn)的冗余程度，定義為檢測區(qū)域的凈覆蓋面積與所有節(jié)點(diǎn)感知面積總和的比值。CE越大，表明節(jié)點(diǎn)的利用率越高，節(jié)點(diǎn)冗余程度越小［14］。圖10統(tǒng)計(jì)了DDS和OPT在特定網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)目下，節(jié)點(diǎn)覆蓋效率CE隨節(jié)點(diǎn)感知視角跨度（網(wǎng)絡(luò)中節(jié)點(diǎn)最大感知視角與最小感知視角的差值）的變化情況。實(shí)驗(yàn)曲線表明，無論節(jié)點(diǎn)的數(shù)目和感知視角跨度如何變化，DDS的節(jié)點(diǎn)覆蓋效率CE平面始終保持在OPT平面之上，體現(xiàn)出較好的網(wǎng)絡(luò)覆蓋有效性。當(dāng)節(jié)點(diǎn)數(shù)目較少且節(jié)點(diǎn)感知視角跨度越大時，DDS覆蓋效率優(yōu)越性尤為明顯。原因在于：DDS中等面積虛擬替代感知圓對節(jié)點(diǎn)視角大小變化具有較好的適應(yīng)性，使得每個節(jié)點(diǎn)可根據(jù)自身感知范圍大小獲得合理的覆蓋子區(qū)間。節(jié)點(diǎn)逐漸向自身所在子區(qū)間多邊形的形心靠攏，彼此分散開來。同時，節(jié)點(diǎn)感知方向均面向邊界，相鄰節(jié)點(diǎn)感知方向一致，為節(jié)點(diǎn)相對整齊地排列部署提夠了條件，有效避免了節(jié)點(diǎn)冗余，增強(qiáng)了網(wǎng)絡(luò)覆蓋。

圖10　節(jié)點(diǎn)覆蓋效率隨節(jié)點(diǎn)數(shù)目和感知視角跨度的變化

4　總結(jié)

針對移動異構(gòu)有向傳感器網(wǎng)絡(luò)，提出了一種基于虛擬替代感知圓的分布式部署策略—DDS。該策略將有向節(jié)點(diǎn)的旋轉(zhuǎn)特性與移動特性相結(jié)合，采用基于虛擬替代圓的改進(jìn)Voronoi圖為每個節(jié)點(diǎn)構(gòu)造覆蓋子區(qū)間，最終確定各節(jié)點(diǎn)移動候選目標(biāo)位置，

且所有節(jié)點(diǎn)移動以提高覆蓋為前提，有效避免了能量浪費(fèi)。仿真分析表明，DDS具有較優(yōu)的網(wǎng)絡(luò)部署效果以及較小的網(wǎng)絡(luò)能耗，各節(jié)點(diǎn)僅通過鄰居節(jié)點(diǎn)信息自行計(jì)算移動位置，避免了全局算法OPT中通信量巨大的缺陷，在大規(guī)模網(wǎng)絡(luò)中尤為適用。

［1］Weiser M.The Computer for the 21st Century［J］.Pervasive Computing，2002，1（1）：19-25.

［2］Ma H D，Liu Y H.On Coverage Problems of Dire-Ctional Sensor Networks［M］.Berlin：Springer，2005.721-731.

［3］陶丹，馬華東，劉亮.基于虛擬勢場的有向傳感器網(wǎng)絡(luò)覆蓋增強(qiáng)算法［J］.軟件學(xué)報(bào)，2007，18（5）：1152-1163.

［4］Liang C K，He M C，Tsai C H.Movement AssistedSensor Deployment in Directional Sensor Networks［C］//Proc of 2010 Sixth International Conference on Mobile Ad-Hoc and Sensor Networks （MSN）.Piscataway：IEEE，2010.226-230.

［5］胡照鵬，張長森.基于矩形分區(qū)覆蓋的節(jié)點(diǎn)確定部署策略［J］.傳感器技術(shù)學(xué)報(bào)，2013，26（3）：411-414.

［6］Panditharathne C.Lin T Y，T，Chen K H.Heterogeneous Directional Sensors Self-Deployment Problem in a Bounded Monitoring Area［C］//Proc of Wireless Communications and Networking Conference（WCNC）.Cancun：IEEE，2011.623-628.

［7］Chiu-Kuo Liang，Cheng-Yen Chung，Chuan-Feng Li.A Virtual Force Based Movement Scheme for Area Coverage in Directional Sensor Networks［C］//Proc of 2014 Tenth International Conference on Intelligent Information Hiding and Multimedia Signal Processing（IIH-MSP）.Kitakyushu：IEEE，2014.718-722.

［8］秦寧寧，余穎華，吳德恩.移動異構(gòu)傳感器網(wǎng)絡(luò)分布式部署算法［J］.傳感技術(shù)學(xué)報(bào)，2016，29（1）：95-102.

［9］陳常超，孫力娟，韓崇，等.有向傳感網(wǎng)分塊區(qū)域p-覆蓋節(jié)點(diǎn)調(diào)度算法研究［J］.傳感器技術(shù)學(xué)報(bào)，2015，28（1）：107-114.

［10］王林，劉文遠(yuǎn)，王琳，等.基于有向傳感器網(wǎng)絡(luò)的強(qiáng)柵欄覆蓋優(yōu)化策略［J］.小型微型計(jì)算機(jī)系統(tǒng)，2014，35（4）：740-745.

［11］Cortés J，Bullo F.Coordination and geometric optimization via distributed dynamical systems［J］.SIAM Journal on Control and Optimization，2005，44（5）：1543-1574.

［12］Bartolini N，Bongiovanni G，La Porta T，et al.Voronoi-based Deployment of Mobile Sensors in the Face of Adversaries［C］.Proc. of 2014 IEEE International Conference on Communications （ICC）.Sydney：IEEE，2014.532-537.

［13］Stergiopoulos Y，Tzes A.Convex Voronoi Space-Partitioning for Coverage Purposes in Heterogeneous Sensor Networks［C］//Proc. of 2009 IEEE European Control Conference（ECC）.Budapest：IEEE，2009.2361-2366.

［14］方偉，宋鑫宏.基于Voronoi圖盲區(qū)的無線傳感器網(wǎng)絡(luò)覆蓋控制部署策略［J］.物理學(xué)報(bào)，2014，63（22）：220701（1-10）.

余穎華（1989-）女，江南大學(xué)碩士研究生，研究方向?yàn)闊o線傳感器網(wǎng)絡(luò)覆蓋，yuyinghuahn@163.com；

李艷（1979-）女，無錫商業(yè)職業(yè)技術(shù)學(xué)院講師，研究方向?yàn)殡娮油ㄐ偶夹g(shù)，454169095@qq.com；

吳德恩（1988-），男，江南大學(xué)碩士研究生，研究方向?yàn)闊o線傳感器網(wǎng)絡(luò)連通性修復(fù)，1004995682@qq.com；

秦寧寧（1980-），女，江南大學(xué)副教授，研究方向?yàn)闊o線傳感器網(wǎng)絡(luò)覆蓋，ningning801108@163.com。

A Distributed Deployment Strategy in Heterogeneous Mobile Directional Sensor Networks*

YU Yinghua1，LI Yan2，WU Deen1，QIN Ningning1，3*
（1.School of Internet of Things Engineering，Jiangnan University，Wuxi Jiangsu 214122，China；
2.Institute of Internet of Things Technology，Wuxi Vocational Institute of Commerce，Wuxi Jiangsu 214153，China；
3.Key Laboratory of Advanced Process Control for Light Industry Ministry of Education，Jiangnan University，Wuxi Jiangsu 214122，China）

Aiming at the coverage enhancement problem of heterogeneous mobile directional sensor networks，a distributed deployment strategy（DDS）based on the virtual omni-directional perception circle is proposed.DDS uses the equal-area virtual omnidirectional sensing circles to replace the sensing sectors of nodes，then structures the regional coverage subinterval for every node depending on the relationship of the positions and radiuses of different sensing circles.Finally，the candidate target location of every node is determined according to the centroid of its subinterval polygon.At the same time，making full use of the rotation of nodes，DDS gets the node's perspective direction to face the outside of the detection area.All nodes adjust their perspective directions and move reasonably to increase the network coverage continuously.The simulation results show DDS has obvious advantages in improving the coverage rate of network and enhancing the distribution balance of nodes.

directionalsensornetworks；virtualomni-directionalperceptioncircle；coveragesubinterval；coveragerate EEACC：6150P

10.3969/j.issn.1004-1699.2016.08.025

TP393

A

1004-1699（2016）08-1273-07

項(xiàng)目來源：江蘇省“六大人才高峰”第十一批高層次人才項(xiàng)目（DZXX-026）；2014年國家公派高級研究學(xué)者及訪問學(xué)者（含博士后）項(xiàng)目；國家自然科學(xué)基金項(xiàng)目（61304264）；江蘇高校優(yōu)勢學(xué)科建設(shè)工程資助項(xiàng)目；江蘇省產(chǎn)學(xué)研聯(lián)合創(chuàng)新資金前瞻性聯(lián)合研究項(xiàng)目（BY2014023-31）；中央高?；究蒲袠I(yè)務(wù)費(fèi)專項(xiàng)資金項(xiàng)目（JUSRP51510）

2015-12-17修改日期：2016-04-15