移動異構(gòu)傳感器網(wǎng)絡(luò)分布式部署算法*

秦寧寧，余穎華，吳德恩（.江南大學(xué)物聯(lián)網(wǎng)工程學(xué)院，江蘇無錫2422；2.江南大學(xué)輕工過程先進控制教育部重點實驗室，江蘇無錫2422）

?

移動異構(gòu)傳感器網(wǎng)絡(luò)分布式部署算法*

秦寧寧1，2*，余穎華1，吳德恩1
（1.江南大學(xué)物聯(lián)網(wǎng)工程學(xué)院，江蘇無錫214122；2.江南大學(xué)輕工過程先進控制教育部重點實驗室，江蘇無錫214122）

摘要：針對移動異構(gòu)傳感器網(wǎng)絡(luò)中的最大覆蓋問題，論文提出了一種分布式部署算法。該算法依據(jù)節(jié)點坐標及其感知范圍而更新目標劃分子區(qū)間，使子區(qū)間內(nèi)的各個節(jié)點能結(jié)合自身及其delaunay鄰居節(jié)點當前的幾何位置和剩余能量值確定速度向量，同時利用節(jié)點的移動特性，使調(diào)整后的網(wǎng)絡(luò)最大化覆蓋目標區(qū)域。仿真結(jié)果表明，該算法在提高網(wǎng)絡(luò)覆蓋率和協(xié)調(diào)速度的同時，能兼顧網(wǎng)絡(luò)節(jié)點剩余能量的均衡。

關(guān)鍵詞：傳感器網(wǎng)絡(luò)；最大覆蓋；目標劃分子區(qū)間；速度向量；剩余能量

傳感器節(jié)點的合理部署是無線傳感器網(wǎng)絡(luò)［1］正常工作的基礎(chǔ)，移動傳感器網(wǎng)絡(luò)作為無線傳感器網(wǎng)絡(luò)的一種特殊應(yīng)用，已為解決部署問題開辟了新途徑。通過為節(jié)點配備移動模塊，發(fā)揮了移動傳感器節(jié)點的可驅(qū)動性；引入分布式協(xié)調(diào)部署策略，摒棄了對全局信息的依賴，激勵移動節(jié)點進行獨立的移動部署，可以達到對整個網(wǎng)絡(luò)的最優(yōu)配置。

目前，針對最大限度地覆蓋目標區(qū)域的移動節(jié)點部署問題［2-4］，相關(guān)研究人員已經(jīng)提出了許多有價值的解決方案。其中Voronoi圖［5-6］作為移動傳感器網(wǎng)絡(luò)中節(jié)點自我決策的基礎(chǔ)，通過將目標區(qū)域的覆蓋任務(wù)分配給每一個傳感器節(jié)點，實現(xiàn)了節(jié)點移動速度與所在子區(qū)域的良好適配。利用歐幾里德Voronoi圖劃分目標區(qū)域，文獻［7］提出了一種面向同構(gòu)網(wǎng)絡(luò)最優(yōu)覆蓋的Lloyd控制策略，使同構(gòu)網(wǎng)絡(luò)趨于最優(yōu)狀態(tài)即覆蓋面積最大，但該算法中節(jié)點移動距離較大，節(jié)點運動能量消耗較高。針對具有不均衡感知半徑的移動傳感網(wǎng)，文獻［8-10］采用了加權(quán)的Voronoi圖分割目標區(qū)間，取得了較高的覆蓋率，但新產(chǎn)生的子區(qū)域的邊界包含曲線段部分，增加了運算的復(fù)雜度［11］。文獻［12］提出了一種受節(jié)點剩余能量約束的移動傳感網(wǎng)部署算法，該算法根據(jù)各節(jié)點的剩余能量劃分與之對應(yīng)的覆蓋子區(qū)間，在保證一定覆蓋率的同時，網(wǎng)絡(luò)節(jié)點剩余能量［13-15］相對均衡，但各節(jié)點感知半徑隨自身能量的消耗而不斷改變。Yiannis［16］等人采用改進的Voronoi圖［17］提出了一種定向覆蓋協(xié)調(diào)算法COC（Coverage-Oriented Coordination），網(wǎng)絡(luò)中各節(jié)點根據(jù)自身感知圓與對應(yīng)覆蓋凸多邊形的關(guān)系確定當前移動向量，最終使各個節(jié)點均勻分布在目標區(qū)域內(nèi)。但COC忽略了未分配到Voronoi子區(qū)間的個別小感知半徑節(jié)點的協(xié)調(diào)問題，當此類節(jié)點位于其他節(jié)點的感知范圍內(nèi)時，會造成覆蓋冗余，覆蓋效率還有待提升。同時網(wǎng)絡(luò)中各個節(jié)點移動向量的大小不受能量的限制，導(dǎo)致各節(jié)點間的剩余能量相差較大。

為解決個別節(jié)點部署及節(jié)點剩余能量不均衡的問題，論文依托基于感知半徑的Voronoi圖劃分提出了一種移動異構(gòu)傳感器網(wǎng)絡(luò)分布式部署算法DDA（Distributed Deployment Algorithm in Mobile Heterogeneous Networks），并以節(jié)點的剩余能量來約束其移動的驅(qū)動輸入（即輸入向量），不僅提高了網(wǎng)絡(luò)覆蓋率和部署速度，同時使網(wǎng)絡(luò)中各節(jié)點的剩余能量更加趨于平衡。

1　問題陳述

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

若移動傳感器網(wǎng)絡(luò)中所有節(jié)點的感知半徑不完全相同，則稱為移動異構(gòu)傳感器網(wǎng)絡(luò)［18］。設(shè)存在一個由N個互不重合的移動異構(gòu)傳感器節(jié)點組成的節(jié)點集合S={Si|i=1，2，…，N}，隨機地部署在一個二維凸多邊形檢測區(qū)域Ω(Ω??2)內(nèi)。集合S中的所有節(jié)點均采用二進制感知模型，且射頻能力滿足delaunay鄰居節(jié)點間通信要求，其收發(fā)所產(chǎn)生的瞬時時間消耗，在本研究中可忽略。各個節(jié)點對Ω的邊界已知，其移動范圍均不超出Ω。

設(shè)定任一節(jié)點Si的感知范圍Ci={x∈?2| ||x-xi||≤ri}，位置坐標記xi，感知半徑ri，當前剩余能量記為Ei，其中||·||表示兩節(jié)點之間的歐幾里德距離。分布密度函數(shù)φ(x)用于描述Ω內(nèi)任一位置點x的重要性，即目標出現(xiàn)在點x上的可能性。

節(jié)點位移和能量標定在Ω內(nèi)，任意移動節(jié)點Si的速度向量為ui，其位置xi及當前能量Ei的動態(tài)變化表達式為：

其中，gi(|·|)表示任一遞增函數(shù)，且當|·|=0時有g(shù)i(|·|)=0，|·|為表達式·的模長。

1.2Voronoi圖

Voronoi圖是以不包含重復(fù)位置的點為生長核，并以相同的速度各自向四周擴張，直到彼此相遇為止而生成的分割圖，如圖1（a）所示。采用Voronoi圖分割目標檢測區(qū)域Ω，其中任意節(jié)點Si所劃分到的Voronoi子區(qū)域Vi可定義為

區(qū)域Ω內(nèi)的每一個位置點x被分配給S中距其最近的節(jié)點，其中xi，xj分別為2個不同節(jié)點Si，Sj的坐標。若Si，Sj所劃分到的Voronoi子區(qū)間Vi，Vj擁有一條公共的邊界，則稱Si，Sj互為delaunay鄰居節(jié)點。在傳統(tǒng)Voronoi圖分割中，任意節(jié)點Si均可劃分到一個Voronoi子區(qū)間Vi，節(jié)點Si的感知范圍Ci與所屬傳統(tǒng)Voronoi子區(qū)間Vi的交集稱為受其感知半徑ri限制的Voronoi單元，其定義為：

1.3基于感知半徑的Voronoi圖

傳統(tǒng)Voronoi圖分割僅根據(jù)節(jié)點的幾何位置劃分空間，而不考慮節(jié)點的感知范圍Ci，所以并不適用于感知半徑不唯一的異構(gòu)傳感器網(wǎng)絡(luò)。文獻［17］曾采用基于感知半徑的Voronoi圖來分割目標區(qū)間。任意節(jié)點Si所劃分到的基于感知半徑的Voronoi子區(qū)域如圖1（b）所示，可定義為：

其中di用于確定兩節(jié)點之間的區(qū)間分割線位置，其取值由節(jié)點Si，Sj之間的二維歐氏距離wij=|xi-xj|及其感知半徑ri，rj聯(lián)合決定。此時，節(jié)點Si受其感知半徑ri限制的基于感知半徑的Voronoi單元為：

如圖1（b）中的節(jié)點S6，由于其過小的感知半徑，在基于感知半徑的Voronoi圖分割中，所劃分得到的子區(qū)間為空集，即不被分配給獨立的子區(qū)域。Voronoi圖分割改良后的最大特點，即對任意兩個節(jié)點Si，Sj，若存在節(jié)點Si的感知圓Ci包含于節(jié)點Sj的感知圓Cj時，則Si將不會劃分得到一個獨立的子區(qū)域。定義分配得到子區(qū)域的節(jié)點為一般節(jié)點，否則稱為特殊節(jié)點。

圖1　兩種Voronoi的空間劃分

2　DDA算法

移動異構(gòu)傳感器網(wǎng)絡(luò)的最大覆蓋應(yīng)是使各節(jié)點的有效覆蓋面積總和最大化，DDA算法將兼顧各節(jié)點自身及delaunay鄰居節(jié)點的幾何位置和剩余能量條件，從而確定其下一刻的速度向量ui?；诟兄霃降腣oronoi圖分割可以產(chǎn)生一般節(jié)點和特殊節(jié)點兩種節(jié)點的現(xiàn)實，對于向量ui的確定分兩種情況開展研究，即：一般節(jié)點的移動向量ui以及特殊節(jié)點移動向量uj的確定。最終，實現(xiàn)移動節(jié)點在ui和uj指導(dǎo)下的定向移動，在最大化網(wǎng)絡(luò)覆蓋面積Ψ的同時，保證網(wǎng)絡(luò)中所有節(jié)點剩余能量均衡。

2.1節(jié)點位移對網(wǎng)絡(luò)覆蓋的影響

鑒于在基于感知半徑的Voronoi圖分割中，一般節(jié)點Si所劃分得到的子區(qū)域為，受其感知半徑ri限制的基于感知半徑的Voronoi單元為，則節(jié)點集S對目標區(qū)域Ω的總覆蓋面積為。其中，任意節(jié)點Si的位置變化，對Ψ的尺度大小具有影響?？紤]若要使Ψ最大，Si則應(yīng)向令Ψ增大的方向移動，令Ψ對任意一般節(jié)點Si的坐標xi求偏導(dǎo)：

進一步，由于φ(x)與xi無關(guān)，根據(jù)廣義萊布尼茲積分公式，式（6）可化簡為：

令：

其中k(Ei，Eiave)≥0，是一個與Si剩余能量Ei及其可移動Delaunay鄰居節(jié)點的平均剩余能量Eiave有關(guān)的函數(shù)，用于約束節(jié)點速度向量ui的大小。則，即

基于式（1），節(jié)點的能量消耗動態(tài)方程［8］

式中負號體現(xiàn)了剩余能量消耗減少的過程，可見節(jié)點能耗隨著k(Ei，Eiave)的增大而增加。

2.2基于k(Ei，Eiave)的一般節(jié)點ui的確定

鑒于節(jié)點移動速度對能量消耗動態(tài)方程的增函數(shù)關(guān)系，節(jié)點在移動過程中勢必會消耗大量能量，當網(wǎng)絡(luò)中某些節(jié)點的移動距離較大時，節(jié)點極易在到達自身最優(yōu)位置前，出現(xiàn)能量過低或耗盡的情況，從而喪失檢測功能，造成資源浪費的同時，意外降低了網(wǎng)絡(luò)覆蓋率。為此，設(shè)定節(jié)點驅(qū)動移動的能量閥值Eth，當一般節(jié)點Si的剩余能量小于能量閥值Eth時，節(jié)點Si不再移動，提前避免因移動距離過長，個別節(jié)點早衰現(xiàn)象。由公式（10）可知，節(jié)點能量消耗受節(jié)點的移動速率|ui|的激勵呈平方增長，即當節(jié)點的移動速率增長時，其能量消耗相應(yīng)以平方速率更快的增長。為使網(wǎng)絡(luò)中所有節(jié)點的剩余能量均衡，當一般節(jié)點Si相對可移動delaunay鄰居節(jié)點剩余能量較高時，可增大其移動速度，有助于加速網(wǎng)絡(luò)達到最大覆蓋效果；當Si相對可移動delaunay鄰居節(jié)點剩余能量較低時，應(yīng)減小其移動速度，避免能量過早耗盡。

因此，當一般節(jié)點Si滿足移動的條件，即Ei>Eth時，可分2種情況確定k(Ei，Eiave)：①若Ei≥Eiave，則k(Ei，Eiave)=1；②若Ei

當節(jié)點Si不滿足運動的條件，即Ei≤Eth時，k(Ei，Eiave)=0。

基于上述分析，結(jié)合式（9），確定任意一般節(jié)點Si的速度向量ui如下：

2.3特殊節(jié)點uj的確定

特殊節(jié)點的產(chǎn)生，源于網(wǎng)絡(luò)中節(jié)點感知半徑相差較大，且小感知半徑節(jié)點較多。在這類移動傳感網(wǎng)中，當節(jié)點的初始分布較為密集時，會有大量小感知半徑節(jié)點不能分配到基于感知半徑的Voronoi子區(qū)間從而成為特殊節(jié)點。

任意兩不重合節(jié)點Si，Sj的位置坐標分別為xi，xj，感知半徑分別為ri，rj，且存在Cj?Ci，此時Sj成為特殊節(jié)點，Sj感知圓內(nèi)所有的點均由節(jié)點Si覆蓋。若Sj的控制輸入uj≠0，當節(jié)點Sj的感知圓Cj與節(jié)點Si的感知圓Ci的位置關(guān)系由內(nèi)含變?yōu)橄嘟粫r，Sj可轉(zhuǎn)變?yōu)橐话愎?jié)點，則目標區(qū)域總覆蓋面積將會隨著Sj的位置變化而增大。同時，由于此類特殊節(jié)點的運動參與，將提高網(wǎng)絡(luò)部署速度。

為有效覆蓋目標區(qū)域，節(jié)點Sj應(yīng)盡快脫離Si的感知區(qū)域，同時遠離其他鄰近節(jié)點。受到虛擬力的啟發(fā)，可設(shè)計滿足Ej>Eth的特殊節(jié)點Sj的移動策略如下：

情況1

若特殊節(jié)點Sj與任一節(jié)點Sk（特殊節(jié)點或一般節(jié)點）之間的距離小于兩者感知半徑之和，即||xj-xk||

情況2

若存在n個節(jié)點Sk1，Sk2，…，Skn（特殊節(jié)點或一般節(jié)點），特殊節(jié)點Sj與其中任意一個節(jié)點Skp( )

1≤p≤n的距離均小于兩者相應(yīng)的感知半徑之和，則節(jié)點Sj的速度向量應(yīng)與n個一般節(jié)點的向量合一致，如圖2（b）所示。

此時，任意特殊節(jié)點Sj的速度向量uj可表示為：

其中，特殊節(jié)點Sj相對于節(jié)點Skp的速度向量為ujkp=(rkp+rj)mjkp-(xj-xkp)，mjkp表示與同向的單位向量。

圖2　特殊節(jié)點Sj控制輸入（速度向量）的確定

2.4 DDA算法實現(xiàn)步驟

初始狀態(tài)下，N個具有相同初始能量E0的節(jié)點隨機分布在目標區(qū)域Ω內(nèi)。對網(wǎng)絡(luò)中每個節(jié)點Si本地化執(zhí)行DDA算法，節(jié)點位置坐標為，收斂性判定精度θ，循環(huán)次數(shù)初始值ki=0，循環(huán)終止閥值kith，節(jié)點每個循環(huán)移動時間為Δt。

步驟1 Si向其周圍鄰居節(jié)點發(fā)送包括其當前坐標xi[ki]，剩余能量Ei[ki]，以及感知半徑ri的數(shù)據(jù)包，同時接收由鄰居節(jié)點發(fā)來的包含同類信息的數(shù)據(jù)包。

步驟2 Si接收到鄰居節(jié)點的信息后，更新自身鄰居節(jié)點信息列表Li[ki]。

步驟3 Si根據(jù)自身信息列表Li[ki]按照式（4）判斷是否被劃分到基于感知半徑的Voronoi子區(qū)間。若是，進入步驟4；否則進入步驟5。

步驟4 Si劃分到子區(qū)間，根據(jù)式（11）求取速度向量ui[ki]，預(yù)計算Si位于坐標xi[ki]+ui[ki]Δt時的凈覆蓋面積是否增加。若是，進入步驟6；否則節(jié)點保持靜止，返回步驟1。

步驟5 Si未劃分到，按式（12）求取速度向量ui[ki]，預(yù)計算點xi[ki]+ui[ki]Δt是否在檢測區(qū)域內(nèi)，若是，進入步驟6；否則節(jié)點保持靜止，返回步驟1。

步驟6 Si按照其速度向量ui[ki]進行移動作用時間為Δt，更新位置變量xi及當前能量變量Ei，即

步驟7若任一節(jié)點均滿足|ui[ki]|≤θ或循環(huán)次數(shù)kith，算法結(jié)束；否則返回步驟1。

可設(shè)定收斂判定精度θ=2ri/1 000，由一般節(jié)點的速度向量表達式可知，一般節(jié)點Si的最大運行速率|ui|max=2ri，即當Si的移動速率|ui[ki]|不大于其最大移動速率的千分之一時，則可以認為節(jié)點Si滿足收斂性判定標準。

3　仿真實驗

3.1仿真環(huán)境

為驗證DDA的有效性，論文采用Matlab軟件進行模擬仿真實驗。目標檢測區(qū)域Ω是二維平面上的一個凸多邊形，延續(xù)文獻［5，16］中多邊形頂點坐標設(shè)置。節(jié)點集S隨機分布在目標區(qū)域內(nèi)，節(jié)點數(shù)目N=10，并模擬節(jié)點分布相對集中的實驗場景，不斷調(diào)整網(wǎng)絡(luò)節(jié)點最大最小感知半徑，如表1所示。當網(wǎng)絡(luò)規(guī)模即節(jié)點數(shù)目N發(fā)生改變時，按比例調(diào)整檢測區(qū)域多邊形的面積A0，并保持多邊形形狀不變，節(jié)點感知半徑取值范圍為0.10~0.60。仿真中，分布密度函數(shù)φ(x)為常數(shù)1，即事件發(fā)生在每一點的概率相等，單次實驗循環(huán)終止閾值kith=100，Δt取0.02。為保證實驗數(shù)據(jù)的可靠性，所有結(jié)論數(shù)值均為20次獨立實驗的平均值。

表1　實驗參數(shù)取值

3.2網(wǎng)絡(luò)協(xié)調(diào)的有效性

相同初始條件下，分別運行COC和DDA算法，某次實驗所得目標區(qū)域Ω覆蓋情況如圖3所示。其中，圖3（a）~3（c）為COC算法運行結(jié)果，圖3（d）~ 3（f）為DDA算法運行的結(jié)果。在COC算法中，由于忽略了未分配到Voronoi子區(qū)間的特殊節(jié)點的移動情況，在整個網(wǎng)絡(luò)節(jié)點的協(xié)調(diào)運動過程中，存在四個小感知半徑特殊節(jié)點7~10始終位于其他節(jié)點的感知范圍內(nèi)；而DDA算法則充分考慮了此類特殊節(jié)點的協(xié)調(diào)需求，通過調(diào)度，使其自主脫離大感知半徑節(jié)點的監(jiān)測范圍，在網(wǎng)絡(luò)覆蓋率提高4.13%的同時，網(wǎng)絡(luò)節(jié)點間的剩余能量標準差減小0.21。

3.3半徑跨度與協(xié)調(diào)速度的影響分析

本實驗將比較COC算法和DDA算法，隨節(jié)點半徑跨度（最大半徑rmax與最小半徑rmin的差值）增大的情況下，網(wǎng)絡(luò)協(xié)調(diào)所需的時間的變化情況。實驗中的節(jié)點數(shù)目和檢測區(qū)域均采用本章初始設(shè)置，且保持不變。

實驗通過增大節(jié)點半徑跨度取值，觀測網(wǎng)絡(luò)協(xié)調(diào)時間在不同算法中的變化情況。如圖4（a）所示，隨著節(jié)點跨度的不斷增大，兩種算法所需要的協(xié)調(diào)時間均呈現(xiàn)增加趨勢，但是相比而言，本論文中所提出的DDA算法所消耗的協(xié)調(diào)時間始終小于傳統(tǒng)的COC算法；且當節(jié)點半徑跨度在適中的0.20~0.40范圍時，DDA算法在協(xié)調(diào)速度上的優(yōu)勢更加明顯，所用協(xié)調(diào)時間占COC算法的81%左右。

節(jié)點半徑跨度越大，網(wǎng)絡(luò)協(xié)調(diào)前期階段實際參與有效覆蓋的一般節(jié)點數(shù)目越少，協(xié)調(diào)網(wǎng)絡(luò)所需時間必然越長。但由于DDA算法中特殊節(jié)點可以參與協(xié)調(diào)工作進行移動，縮短了其變?yōu)橐话愎?jié)點所用的時間，因此網(wǎng)絡(luò)協(xié)調(diào)速度在DDA中得到了較大的提高，協(xié)調(diào)時間相對減少。當節(jié)點半徑跨度過小時，特殊節(jié)點涌現(xiàn)的數(shù)目較少，DDA算法利用特殊節(jié)點移動性能的優(yōu)勢不明顯；而當節(jié)點半徑跨度較大時，特殊節(jié)點感知半徑極大的小于一般節(jié)點的感知范圍，移出一般節(jié)點感知范圍的時間增長，對網(wǎng)絡(luò)有效覆蓋面積的影響減弱，網(wǎng)絡(luò)協(xié)調(diào)工作主要依賴于具有大感知半徑的一般節(jié)點，使得DDA算法中移動特殊節(jié)點的效應(yīng)不明顯。因此，存在節(jié)點半徑跨度較為適中0.20~0.40。

圖3　COC和DDA兩種算法實現(xiàn)的網(wǎng)絡(luò)覆蓋情況，圖（a~c）為COC協(xié)調(diào)過程，圖（d~f）為DDA協(xié)調(diào)過程

3.4網(wǎng)絡(luò)規(guī)模適應(yīng)性分析

本實驗將驗證DDA算法對于網(wǎng)絡(luò)規(guī)模的適應(yīng)性能。在保證目標區(qū)域多邊形狀不變的情況下，擴張多邊形面積A0的同時，保持等分布密度（單位面積2個節(jié)點）增加網(wǎng)絡(luò)節(jié)點數(shù)目N，圖4 （b）對比了COC和DDA算法，隨上述網(wǎng)絡(luò)規(guī)模調(diào)整過程中移動節(jié)點的協(xié)調(diào)部署時間。兩種算法隨檢測區(qū)域Ω面積的不斷增大，需要協(xié)調(diào)的節(jié)點增多，所用時間均呈增大趨勢。另一方面，由于COC僅依賴于劃分到Voronoi子區(qū)間的一般節(jié)點移動來協(xié)調(diào)網(wǎng)絡(luò)，而忽略了未分配到Voronoi子區(qū)間的特殊節(jié)點的部署能力，因此，在網(wǎng)絡(luò)規(guī)模變化的各個階段，DDA算法的協(xié)調(diào)速度均優(yōu)于COC算法。

圖4　網(wǎng)絡(luò)協(xié)調(diào)部署時間

3.5網(wǎng)絡(luò)覆蓋率分析

在此，定義任一節(jié)點Si的有效覆蓋面積Ai，為節(jié)點的感知圓在其相應(yīng)基于感知半徑的Voronoi子區(qū)間內(nèi)的面積，即，則網(wǎng)絡(luò)的總覆蓋面積為A=∑Ai，相應(yīng)網(wǎng)絡(luò)覆蓋率為P=A/A0，其中A0為目標區(qū)域Ω的面積。

圖5比較了隨著節(jié)點半徑跨度和數(shù)目N的變化，COC和DDA的網(wǎng)絡(luò)覆蓋率變化情況。從圖5可知：兩種算法的網(wǎng)絡(luò)覆蓋率均高于70%；無論半徑跨度和網(wǎng)絡(luò)規(guī)模如何變化，和COC相比，DDA始終保持優(yōu)勢；且隨半徑跨度增大，DDA的優(yōu)勢也逐漸擴大。當節(jié)點半徑跨度大于0.30時，COC算法中成為冗余節(jié)點的數(shù)目逐漸增多，造成覆蓋率降低，而DDA算法中小感知半徑特殊節(jié)點的運動能力使得網(wǎng)絡(luò)中各個節(jié)點均能有效覆蓋目標區(qū)域，避免了冗余情況的發(fā)生，相應(yīng)提高了覆蓋率。圖5（b）表明，隨著節(jié)點數(shù)目的變化，DDA算法始終具備調(diào)度COC算法中的冗余節(jié)點加入到網(wǎng)絡(luò)覆蓋的能力，有效增大了網(wǎng)絡(luò)凈覆蓋面積。

圖5　網(wǎng)絡(luò)覆蓋率分析

3.6剩余能量分析

在相同初始條件下，分別采用COC和DDA算法所提供的控制方案，驅(qū)動各個節(jié)點進行協(xié)調(diào)部署。網(wǎng)絡(luò)達到穩(wěn)定后節(jié)點的剩余能量標準差如圖6。其中，標準差為各數(shù)據(jù)的離差平方和與數(shù)據(jù)個數(shù)比值的算術(shù)平方根。

隨著節(jié)點半徑跨度的增大，COC算法中大小感知半徑節(jié)點參與網(wǎng)絡(luò)部署的時間間隔逐漸增大，各節(jié)點間的移動距離相差變大，最終造成整個網(wǎng)絡(luò)節(jié)點的剩余能量標準差越來越大。由于DDA算法特殊小感知半徑節(jié)點與大感知半徑節(jié)點同步移動，同時利用各個一般節(jié)點以自身和delaunay鄰居節(jié)點的剩余能量關(guān)系來調(diào)整其速度向量，最終使整個網(wǎng)絡(luò)中各個節(jié)點的剩余能量更加均衡。當半徑跨度位于0~0.50范圍內(nèi)時，網(wǎng)絡(luò)所有節(jié)點剩余能量標準差始終低于0.20。

圖6（b）中，隨著節(jié)點數(shù)目N和目標區(qū)域的多邊形面積A0的增大，使得節(jié)點部署運動距離變大。COC算法中此類運行消耗主要由大感知半徑節(jié)點支付，而DDA算法中的所有節(jié)點同時參與網(wǎng)絡(luò)部署，此類由于檢測范圍變大而增加的能量消耗由網(wǎng)絡(luò)中所有節(jié)點共同承擔，使得整個網(wǎng)絡(luò)的節(jié)點剩余能量相差不大。

圖6　網(wǎng)絡(luò)節(jié)點剩余能量分析

4　結(jié)束語

論文提出了一種移動混合傳感器網(wǎng)絡(luò)分布式部署算法—DDA，算法利用節(jié)點對目標檢測空間的合理劃分，使得各節(jié)點能根據(jù)自己是否劃分得到Voronoi子區(qū)間的情況，兼顧自身與其delaunay鄰居節(jié)點當前剩余能量的關(guān)系來確定自身速度向量。算法在提高網(wǎng)絡(luò)覆蓋率以及節(jié)點部署快速性的同時，使節(jié)點間的剩余能量更加均衡，有助于控制網(wǎng)絡(luò)的整體能耗。考慮到Voronoi分割的幾何特點，該算法的初始任務(wù)定位為凸形目標區(qū)域，對于凹形或者孔型等復(fù)雜的形狀區(qū)域，雖然可以通過區(qū)域分塊形成多個凸形區(qū)域，進行平行解決，但一定程度上依然會增加許多不確定性因素，因此，近一步研究移動傳感器在復(fù)雜區(qū)域的部署問題將被重視。

參考文獻：

［1］錢志鴻，王義君.面向物聯(lián)網(wǎng)的無線傳感器網(wǎng)絡(luò)綜述［J］.電子與信息學(xué)報，2013，35（1）：215-227.

［2］Bartolini N. Distributed Deployment Algorithms for Improved Cov?erage in a Network of Wireless Mobile Sensors［J］. IEEE Transac?tions on Industrial Informatics，2014，9（1）：163-174.

［3］Sengupta S，Das S，Nasir M D，et al. Multi-Objective Node Deploy?ment in WSNs：in Search of an Optimal Trade-Off Among Cover?age，Lifetime，Energy Consumption，and Connectivity［J］. Engi?neering Applications of Artificial Intelligence，2013，26（1）：405-416.

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

［5］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.

［6］Bartolini N，Bongiovanni G，La Porta T，et al. Voronoi-Based De?ployment of Mobile Sensors in the Face of Adversaries［C］//Pro?ceedings of 2014 IEEE International Conference，Sydney，2014：532-537.

［7］Cortés J，Martinez S，Karatas T，et al. Coverage Control for Mobile Sensing Networks［J］. IEEE Transactions on Robotics and Auto?mation，2004，20（2）：243-255.

［8］Kwok A，Martinez S. Deployment Algorithms for a Power Con?strained Mobile Sensor Network［J］. International Journal of Ro?bust and Nonlinear Control，2010，20（7）：745-763.

［9］Mahboubi H，Aghdam A G. Distributed Deployment Strategies to Increase Coverage in a Network of Wireless Mobile Sensors［C］// Proceedings of 2013 American Control Conference（ACC），Wash?ington，2013：17-19.

［10］Mahboubi H. Distributed Deployment Algorithms for Efficient Coverage in a Network of Mobile Sensors with Nonidentical Sens?ing Capabilities［J］. IEEE Transactions on Vehicular Technology，2014，63（8）：3998-4016.

［11］Kashi S S，Sharifi M. Coverage Rate Calculation in Wireless Sen?sor Networks［J］. Computing，2012，94（11）：833-856.

［12］Kwok A，Martinez S. Energy-Balancing Cooperative Strategies for Sensor Deployment［C］//Proceedings of the IEEE International Conference on Decision and Control，New Orleans，2007：12-14.

［13］Naderan M，Dehghan M，Pedram H. Sensing Task Assignment Via Sensor Selection for Maximum Target Coverage Coverage in WSNs［J］. Journal of Network and Computer Applications，2013，36（1）：262-273.

［14］秦寧寧，陳家樂，丁志國.覆蓋率均衡區(qū)域覆蓋［J］.傳感技術(shù)學(xué)報，2015，28（4）：578-584.

［15］Lee J W，Lee J Y，and Lee J J. Jenga-Inspired Optimization Algo?rithm for Energy- Efficient Coverage of Unstructured WSNs［J］. IEEE Wireless Communications Letters，2013，2（1）：34-37.

［16］Stergiopoulos Y，Tzes A. Coverage-Oriented Coordination of Mo?bile Heterogeneous Networks［C］//Proceedings of the 19th Medi?terranean Conference on Control and Automation，Corfu，2011：175-180.

［17］Stergiopoulos Y，Tzes A. Convex Voronoi Space-Partitioning for Coverage Purposes in Heterogeneous Sensor Networks［C］//Pro?ceedings of 2009 IEEE European Control Conference，Budapest，2009：2361-2366.

［18］杜曉玉，孫力娟，郭劍，等.異構(gòu)無線傳感器網(wǎng)絡(luò)覆蓋優(yōu)化算法［J］.電子與信息學(xué)報，2014，36（3），696-702.

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

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

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

A Strategy of Energy Hole Avoided in Homogeneous WSNs*

LONG Shengchun*，LU Dingqian，CHI Kaikai
（College of Computer Science and Technology，Zhejiang University of Technology，Hangzhou 310023，China）

Abstract：Aiming at the problem of uneven energy consumption in wireless sensor networks（WSNs），this paper put forward an energy-hole avoidance strategy based on homogeneous WSNs with the unequal cluster radius. First?ly，this study presents the Balanced Cluster Scale based LEACH（BCS-L）algorithm through improving the existing LEACH routing algorithm. Then jointly applying the BCS-L algorithm and the network structure with concentric rings，the energy-hole avoidance problem is converted to a polynomial problem which calculates the outer radius of the adjacent ring bands，with the objective of minimizing and balancing the nodes average energy consumption that in different rings. The locally optimal solution can be obtained by solving this problem. Theoretical analysis and sim?ulation results show that the strategy greatly improves the network lifetime and avoids the energy hole effectively，and can be deployed in the large sensor networks.

Key words：homogeneous sensor network；energy consumption balancing；BCS-L；rings

doi：EEACC：6150P10.3969/j.issn.1004-1699.2016.01.018

收稿日期：2015-08-02修改日期：2015-09-16

中圖分類號：TP393

文獻標識碼：A

文章編號：1004-1699（2016）01-0095-08

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