移動異構傳感器網絡分布式部署算法*

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

?

移動異構傳感器網絡分布式部署算法*

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

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

關鍵詞：傳感器網絡；最大覆蓋；目標劃分子區間；速度向量；剩余能量

傳感器節點的合理部署是無線傳感器網絡［1］正常工作的基礎，移動傳感器網絡作為無線傳感器網絡的一種特殊應用，已為解決部署問題開辟了新途徑。通過為節點配備移動模塊，發揮了移動傳感器節點的可驅動性；引入分布式協調部署策略，摒棄了對全局信息的依賴，激勵移動節點進行獨立的移動部署，可以達到對整個網絡的最優配置。

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

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

1　問題陳述

1.1網絡模型

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

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

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

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

1.2Voronoi圖

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

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

1.3基于感知半徑的Voronoi圖

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

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

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

圖1　兩種Voronoi的空間劃分

2　DDA算法

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

2.1節點位移對網絡覆蓋的影響

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

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

令：

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

基于式（1），節點的能量消耗動態方程［8］

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

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

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

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

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

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

2.3特殊節點uj的確定

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

任意兩不重合節點Si，Sj的位置坐標分別為xi，xj，感知半徑分別為ri，rj，且存在Cj?Ci，此時Sj成為特殊節點，Sj感知圓內所有的點均由節點Si覆蓋。若Sj的控制輸入uj≠0，當節點Sj的感知圓Cj與節點Si的感知圓Ci的位置關系由內含變為相交時，Sj可轉變為一般節點，則目標區域總覆蓋面積將會隨著Sj的位置變化而增大。同時，由于此類特殊節點的運動參與，將提高網絡部署速度。

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

情況1

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

情況2

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

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

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

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

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

2.4 DDA算法實現步驟

初始狀態下，N個具有相同初始能量E0的節點隨機分布在目標區域Ω內。對網絡中每個節點Si本地化執行DDA算法，節點位置坐標為，收斂性判定精度θ，循環次數初始值ki=0，循環終止閥值kith，節點每個循環移動時間為Δt。

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

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

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

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

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

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

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

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

3　仿真實驗

3.1仿真環境

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

表1　實驗參數取值

3.2網絡協調的有效性

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

3.3半徑跨度與協調速度的影響分析

本實驗將比較COC算法和DDA算法，隨節點半徑跨度（最大半徑rmax與最小半徑rmin的差值）增大的情況下，網絡協調所需的時間的變化情況。實驗中的節點數目和檢測區域均采用本章初始設置，且保持不變。

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

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

圖3　COC和DDA兩種算法實現的網絡覆蓋情況，圖（a~c）為COC協調過程，圖（d~f）為DDA協調過程

3.4網絡規模適應性分析

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

圖4　網絡協調部署時間

3.5網絡覆蓋率分析

在此，定義任一節點Si的有效覆蓋面積Ai，為節點的感知圓在其相應基于感知半徑的Voronoi子區間內的面積，即，則網絡的總覆蓋面積為A=∑Ai，相應網絡覆蓋率為P=A/A0，其中A0為目標區域Ω的面積。

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

圖5　網絡覆蓋率分析

3.6剩余能量分析

在相同初始條件下，分別采用COC和DDA算法所提供的控制方案，驅動各個節點進行協調部署。網絡達到穩定后節點的剩余能量標準差如圖6。其中，標準差為各數據的離差平方和與數據個數比值的算術平方根。

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

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

圖6　網絡節點剩余能量分析

4　結束語

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

參考文獻：

［1］錢志鴻，王義君.面向物聯網的無線傳感器網絡綜述［J］.電子與信息學報，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］胡照鵬，張長森.基于矩形分區覆蓋的節點確定部署策略［J］.傳感器技術學報，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］秦寧寧，陳家樂，丁志國.覆蓋率均衡區域覆蓋［J］.傳感技術學報，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］杜曉玉，孫力娟，郭劍，等.異構無線傳感器網絡覆蓋優化算法［J］.電子與信息學報，2014，36（3），696-702.

秦寧寧（1980-），女，江南大學副教授，研究方向為無線傳感器網絡覆蓋，ningning801108@163.com；

吳德恩（1988-），男，江南大學碩士研究生，研究方向為無線傳感器網絡連通性修復，1004995682@qq.com。

余穎華（1989-）女，江南大學碩士研究生，研究方向為無線傳感器網絡覆蓋，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年國家公派高級研究學者及訪問學者（含博士后）項目；國家自然科學基金項目（61304264）；江蘇高校優勢學科建設工程項目；江蘇省產學研聯合創新資金前瞻性聯合研究項目（BY2014023-31）