基于虛擬力和泰森多邊形的分布式覆蓋算法

祁春陽，戴 歡，趙曉燕，李克清,4+

(1.中國礦業大學 計算機科學與技術學院，江蘇 徐州 221116；2.蘇州科技大學 電子與信息工程學院，江蘇 蘇州 215009；3.常熟理工學院 計算機科學與工程學院，江蘇 常熟 215500；4.蘇州市職業大學 計算機科學與工程學院，江蘇 蘇州 215002)

0 引 言

近些年來，學術界提出了不少無線傳感器網絡[1]覆蓋算法。通常將這些算法歸結為兩類：一方面是集中式覆蓋算法，即通過預先部署固定節點在限定區域內，通過節點通信范圍計算此限定區域的覆蓋率，而后加入移動型節點，由集中式算法獲得的網絡全局信息對于覆蓋盲區進行補充、修整。代表算法有粒子群優化算法[2](particle swarm optimization，PSO)、概率感知模型算法[3]等。另一方面是分布式覆蓋算法，即直接部署移動節點，通過感知周圍節點的信息進行自主移動提高覆蓋率，無需獲取全局網絡信息，減少能量消耗，具有部署簡單、自主化程度高等特點。代表算法有虛擬力算法[4](virtual force，VF)、節點感知方向調節算法[5](distributed node orientation adjust，DNOA)。

虛擬力算法的主要思想是在限定區域內尋找節點間的受力平衡位置，以此作為傳感器節點在后期相關算法迭代過程中的移動位置。基于虛擬力的覆蓋算法，取得了較好的覆蓋率，但其計算量大、收斂速度慢并且易陷入局部最優，使其覆蓋率出現不穩定現象。本文提出了基于虛擬力和泰森多邊形劃分[6]的分布式覆蓋算法，該算法可有效避免單獨虛擬力情況下陷入局部最優，實現較高覆蓋率。

1 算法的提出

1.1 虛擬力算法

虛擬力算法由物理學中力的相互作用引入覆蓋問題的研究[7]，此算法假設所研究的限定區域內的節點間存在相互力，在無線傳感器節點覆蓋算法優化中采取節點所受合力移動方式，直到區域節點間相互受力平衡。假設無線網絡中的傳感器節點si的所受虛擬力為Fi；傳感器節點sj對傳感器節點si的力為Fij，相鄰傳感器節點間距離為d。FiR定義為限定區域內未被覆蓋的網格節點對傳感器節點si的合力，若區域邊界存在大量節點，根據上述規則必然會存到強斥力作用，將會浪費一些傳感器節點的覆蓋能力，此時規定一個邊界約束力Fb，傳感器節點所受合力如式(1)所示

(1)

其中，傳感器節點間的相互作用力Fij包含引力和斥力兩個部分，當區域內的特定范圍節點密集時斥力影響大于引力，反之同理。根據最終引力和斥力的大小確定移動距離和位置，各傳感器根據虛擬力將原位置(xold,yold)更新為新位置(xnew,ynew)，如式(2)所示

(2)

其中，MS為傳感器節點在算法單次迭代過程中的最大移動距離，Fxy是全局對傳感器節點的合力，Fx，Fy是傳感器節點所受合力兩個二維分量，分別表示為傳感器節點在x軸和y軸所受力的分量。虛擬力方案可有效的擴散限定區域內節點，使其處于一種相對平衡的位置。

1.2 Voronoi圖

Voronoi圖是基于Delaunay三角對于空間內限定區域采用節點中垂線相連接方法組成的區域劃分圖，采用歐式距離為標準對于平面區域進行分塊[8]。由于Voronoi圖具有最近性、鄰接性等性質和比較完善的理論體系，所以Voronoi圖常被用來解決影響范圍、最近鄰近查詢問題、最大空圓問題和Delaunay三角對偶問題[9]。構建Voronoi圖的基本思想：基于限定平面區域內的隨機離散節點集(如圖1所示)中的相鄰節點做出中垂線，然后去除多條中垂線連接后的多余線段，形成多塊不同形狀的多邊形，并且每個多邊形中包含唯一對應的節點，最終形成一個對于該節點的最近二維平面區域，形成的二維區域內的所有數據點集距離區域內該點的距離相對于距離鄰近區域的點都為最近。即對應該節點的影響范圍稱為Voronoi多邊形(如圖2所示)，若刪除任意生成點，那么與之對應的影響范圍將消失，并且只能影響與之鄰近的Voronoi多邊形區域。

圖1 隨機部署節點初始位置

圖2 Voronoi劃分下的初始節點位置

基于以上的Voronoi幾何方案，引入質心算法、Minmax算法將提高虛擬力條件下的后期覆蓋率穩定性及收斂速度，可在較少的迭代次數下獲得較好的網絡覆蓋率。

2 VFVP覆蓋算法

上述虛擬力算法可以相對解決前期傳感器節點分布過于密集的問題，Voronoi算法具有很強的區域劃分能力，有利于提升算法的收斂速度，質心算法可以優化節點迭代過程中的移動位置[10]，因此本文提出了一種VFVP算法策略，算法流程如圖3所示。

圖3 算法流程

2.1 網絡模型構建

假設有N個節點，每個節點感知半徑為Rs。無線傳感器網絡節點集S被隨機部署在一個二維空間A內[11]，節點具有自主移動性，其通信半徑為Rc，Rc≥2Rs。節點Si屬于S集合，以節點為感知圓心，假設節點具有以下性質：①初步在監測區域部署移動傳感器節點，其拒用可移動性，可根據自身優化的分布式算法進行自主移動到相對位置，節點間相互采取分布式通信逐個建立無線傳感器網絡；②節點的通信半徑為感知半徑的2倍，即Rc=2Rs,任意兩個節點互為鄰居；③將監測區域進行分割成正方形，計算在傳感器節點感知半徑內的格點數，計算覆蓋率。

2.2 相關定義

定義1 節點集：監測區域A內隨機部署節點集S，將A根據節點集S劃分為不同的Voronoi多邊形區域，即Si∈Vi(S，Rs，V), 其中，Vi為Si所在Voronoi多邊形區域。傳感器節點集S?V。

定義2 衍生節點集：已知監測區域A被劃分為多個不規則的Voronoi多邊形，因多邊形區域根據隨機部署的節點集劃分，每個不規則多邊形內包含一個可移動傳感器節點S1，多邊形的各個頂點集為衍生節點集W，記對應節點S1的衍生節點集個數為k。

定義3 質心節點集：定義2中給出了衍生節點集W，將衍生節點集進行質心計算得到質心節點集N，如式(3)、式(4)所示

(3)

(4)

2.3 離散節點覆蓋率計算

假設二維空間A，被劃分為m×n個網格節點，網格節點Q的坐標為(xi,yi)，其中，節點Si={xi,yi,RS}， 則Q點與節點Si的距離為d(Si,Q)。由布爾模型得出節點Si與網格節點Q的概率模型

(5)

由于實際環境中的噪聲等其它因素的干擾，節點測量模型表現出特定的概率分布

(6)

式(6)中的re(0

由以上公式所得，對于點的監測概率有可能是小于1，因此通常使用傳感器節點多點聯動方案，其概率分布如下

(7)

在網格劃分中，網格節點Q被傳感器節點有效覆蓋的標準如下

P(S,Q)≥cth

(8)

式(8)的cth表示網格節點是否被有效覆蓋的閾值。

區域覆蓋中的覆蓋率表示為傳感器節點的感知范圍與監測區域A面積的比值，將A離散分割后，覆蓋率表示如下

(9)

式(9)中參數count由式(8)給出有效覆蓋網格節點數。

2.4 算法步驟

本文算法可分為以下4個階段：

步驟1 由虛擬力算法將節點集S充分受力盡可能分布均勻；

步驟2 關閉虛擬力，為移動后節點集S進行Voronoi劃分，對檢測區域A內的衍生節點集W進行存儲；

步驟3 將區域A內的點集W進行質心改進，得到質心點集N；

步驟4 將質心點集與移動后節點集進行對比移動，優化位置；

步驟5 Minmax算法調整后期精度，提高節點覆蓋在迭代后期穩定性。

3 實驗仿真及結果分析

3.1 實驗仿真

為了驗證VFVP分布式覆蓋優化策略的覆蓋程度與收斂速度，與VF、VFVM、VFC覆蓋優化策略做了對比實驗。仿真環境：Matlab 2015。實驗過程中分析了無線傳感器節點對監測區域的覆蓋程度及收斂速度，兩項指標定義如下：①覆蓋程度：所有節點的覆蓋面積總和與整個監測區域的比值。②收斂速度：對比虛擬力算法在同一時間節點下的覆蓋率。

假設在邊長60 m的正方形區域內布置55個可移動的無線傳感器節點，所有傳感器節點的測量半徑為6 m，節點通信半徑Rc=2Rs。圖4顯示節點的初始隨機分配狀態和算法最終覆蓋圖，該狀態下的節點在覆蓋區域的左上角和中間部分形成了大量的覆蓋重合節點，使得監測區域內的覆蓋率很低，經過VFVP算法規劃后得到很好的覆蓋效果。VF算法代表虛擬力下的覆蓋算法，VFVM算法為虛擬力環境下加入Voronoi規劃、Minmax的覆蓋算法，VFC代表虛擬力條件下直接使用質心算法的覆蓋模式。圖5給出了4種算法運行過程中覆蓋情況，可看出算法在迭代了25次的情況，覆蓋率得到明顯提高，對比3種算法迭代相同次數的結果。VFVP算法在初期運行方面得到的覆蓋率明顯高于VF、VFVM、VFC算法。

圖4 VFVP初始狀態和算法結果

圖5 迭代次數為25次時節點覆蓋情況

3.2 覆蓋率與收斂速度評估

無線傳感器網絡中節點對于監測區域的覆蓋率與收斂速度是判斷算法優劣的重要指標，如圖6所示。

圖6 迭代過程覆蓋率增長

引入Voronoi規劃的VFVP算法在監測區域A中的覆蓋率都優于另外3種算法，該算法隨著迭代次數的增加，覆蓋率上升較為平滑。虛擬力算法前期收斂速度較慢，VFC算法初期快速收斂現象很好解決了這個問題。但VFC算法后期出現覆蓋率的大幅度降低，VFVP算法的出現解決了后期VF算法覆蓋率不規則下降的問題，通過Minmax算法的后期調整得到了很好的效果。

如圖7所示，虛擬力算法存在著收斂速度慢，引入質心解決方案后的VFVP算法收斂速度得到了很大的提升，質心解決方案中采取Voronoi多邊形質心算法可快速提高VFVP算法的前期收斂速度。

如圖8所示，4種不同節點數量條件下的4種算法的最終覆蓋率對比中，VFVP在節點數量條件下的覆蓋對比算法中取得了較好的覆蓋率，VFVM算法的覆蓋率增長圖與VF算法接近，驗證了Minmax算法對于VFVP算法的有效性，VFC算法在節點數量較小時覆蓋率較小，隨著節點數量增加，其覆蓋率增長最快，可提高VFVP算法的收斂速度。

4 結束語

本文算法采用虛擬力算法為基礎，幾何Voronoi算法、質心算法、Minmax算法為輔，有效優化了在虛擬力環境下易陷入局部最優的問題，提高了監測區域的覆蓋率，加快了算法的收斂速度。仿真實驗驗證了本文算法的有效性，采用的VFVP算法比原始虛擬力算法提高了約5%覆蓋率。下一步將會在本文算法的基礎上引入障礙物的情況，并進行相關減小覆蓋重合區域的工作。

圖7 收斂速度對比

圖8 節點數目增加過程中的覆蓋率增長

[1]SUN Zeyu,WU Weiguo,WANG Huanzhao,et al.An enhanced coverage control algorithm for wireless sensor networks based on adjustable parameters[J].Chinese Journal of Electronics,2015,43(3):466-474(in Chinese).[孫澤宇,伍衛國,王換招,等.無線傳感器網絡基于參數可調增強型覆蓋控制算法[J].電子學報,2015,43(3):466-474.]

[2]WANG Changzheng,MAO Jianlin,FU Lixa,et al.Coverage optimization algorithm for three-dimensional directional heterogeneous sensor network[J].Journal of Computer Applications,2016,36(9):2362-2366(in Chinese).[王昌征,毛劍琳,付麗霞,等.面向三維的有向異構傳感器網絡覆蓋優化算法[J].計算機應用,2016,36(9):2362-2366.]

[3]FAN Xinggang,YANG Jingjing,WANG Heng.Algorithm for enhancing probabilistic coverage in wireless sensor network[J].Journal of Software,2016,27(2):418-431(in Chinese).[范興剛,楊靜靜,王恒.一種無線傳感器網絡的概率覆蓋增強算法[J].軟件學報,2016,27(2):418-431.]

[4]LIU Wei,HU Anlin.Reaserch of coverage ratio and energy saving in wireless sensor network[J].Application of Electronic Technique,2016,42(6):98-100(in Chinese).[劉偉,胡安林.無線傳感器網絡覆蓋率與節能性研究[J].電子技術應用,2016,42(6):98-100.]

[5]WANG Lili,WU Xiaobei,HUANG Cheng,et al.Node scheduling strategy based on target coverage for heterogeneous directional sensor networks[J].Control and Decision,2016,31(12):2140-2146(in Chinese).[王力立,吳曉蓓,黃成,等.基于目標覆蓋的異構有向傳感器網絡分布式節點調度策略[J].控制與決策,2016,31(12):2140-2146.]

[6]QIN Zefeng,TAN Ying,ZHAO Jing,et al.Research on coverag algorithm in wireless sensor network based on the Voronoi[J].Journal of Taiyuan University of Science and Technology,2013,34(3):185-190(in Chinese).[秦澤峰,譚瑛,趙靜,等.基于Voronoi圖的無線傳感器網絡覆蓋算法研究[J].太原科技大學學報,2013,34(3):185-190.]

[7]Mahboubi H,Aghdam A G.Distributed deployment algorithms for coverage improvement in a network of wireless mobile sensors:Relocation by virtual force[J].IEEE Transactions on Control of Network Systems,2016,PP(99):1-1.

[8]HUANG Sheng,LIU Guangzhong,XU Ming.Distributed Voronoi control strategy based on virtual force[J].Computer Science,2016,43(10):125-129(in Chinese).[黃勝,劉廣鐘,徐明.一種基于虛擬力的分布式Voronoi控制策略[J].計算機科學,2016,43(10):125-129.]

[9]Abo Zahhad M,Sabor N,Sasaki S,et al.A centralized immune-Voronoi deployment algorithm for coverage maximization and energy conservation in mobile wireless sensor networks[J].Information Fusion,2016,30(C):36-51.

[10]Pietrabissa A,Liberati F,Oddi G.A distributed algorithm for Ad-hoc,network partitioning based on Voronoi tessellation[J].Ad Hoc Networks,2016,46:37-47.

[11]Le D V,Oh H,Yoon S.VirFID:A virtual force (VF)-based interest-driven moving phenomenon monitoring scheme using multiple mobile sensor nodes[J].Ad Hoc Networks,2015,27:112-132.