形心導向虛擬力的無線傳感器網絡部署算法

宋鑫宏， 方 偉， 熊偉麗

(江南大學物聯網工程學院，江蘇無錫214122)

無線傳感器網絡(Wireless Sensor Networks，WSNs)的隨機部署問題是指如何引導移動傳感器節點［1］改變位置實現對監測區域的最大化覆蓋。隨機部署問題是WSNs研究和應用的關鍵問題之一，它一方面關系到無線傳感器節點能量的有效控制、感知服務質量和整體生存時間;另一方面也關系到網絡相關傳輸、管理、存儲和計算的代價［2］。

虛擬力算法［3-4］作為處理覆蓋部署問題的有效手段，自提出以來得到了國內外學者的廣泛關注。Li等［5］提出了面向目標跟蹤的虛擬力算法(Target involved virtual force algorithm，TIVFA)，使傳感器節點根據目標位置和重要性程度自動調整網絡布局，以改善網絡覆蓋率和提升目標探測概率;Yu等［6］將Delaunay三角網引入虛擬力算法，定義鄰居節點為通信半徑內由Delaunay三角網連接的節點，使覆蓋率得到提升;Lee等［7］提出了基于泰森多邊形形心的部署策略(Centroid-Based Scheme，CBS)，將若干傳感器節點覆蓋監測區域的問題分解成每個傳感器節點覆蓋其對應泰森多邊形的問題，降低了問題的復雜性;Han等［8］將CBS與傳統虛擬力算法結合提出了一種混合部署算法，使障礙物、鄰居節點以及泰森多邊形形心對傳感器節點產生虛擬力從而引導傳感器節點移動。但在該算法中，泰森多邊形形心對各傳感器節點的虛擬力需通過權重值加以限制。由于CBS具有無需設置參數、邊界自適應、覆蓋率高等優點，文中保留CBS的優點，并與虛擬力算法調整節點間相對位置的能力相結合，提出一種新的基于泰森多邊形形心導向虛擬力的部署算法(CBVFA)。

1 無線傳感器網絡覆蓋問題

1.1 問題模型

假設在A×B的監測區域內隨機拋撒N個感知半徑為r、通信半徑為cth的同構無線傳感器節點，傳感器節點集 S={s1，s2，…，sN}，節點位置 si=(xi，yi)。將監測區域均勻離散化為a×b個目標點，目標點位置 tj=(xj，yj)j∈［1，a × b］。

文中使用使用二元感知模型計算節點si對目標點 tj的感知概率 p(si，tj)［9］。si與 tj的距離記為 d(si，tj)，具體表示為

當 d(si，tj)≤ r時，si覆蓋 tj，p(si，tj)記為 1;否則 si未覆蓋 tj，p(si，tj)記為0。計算公式如下:

傳感器節點集S對目標點tj的感知概率使用聯合感知概率Qj表示。在N個傳感器節點中若存在一個傳感器節點覆蓋tj，則tj的聯合感知概率Qj為1，否則記為0。聯合感知概率表示為

1.2 性能指標

WSNs對監測區域的覆蓋情況使用覆蓋率CR表示，CR的計算方法為已覆蓋目標點之和與總目標點數之比，具體表示為

節點分布均勻性U是衡量網絡壽命長短的標準之一，U越小WSNs的分布越均勻，其網絡壽命越長。U的計算方法為N個傳感器節點與其對應鄰居節點距離的標準差取均值［11］，公式如下:

式中:Mi為第i個傳感器節點與其所有鄰居節點的平均距離;Di，j為第i個傳感器節點與其第j個鄰居節點的距離;ki為第 i個傳感器節點的鄰居節點總個數。

2 虛擬力算法與基于泰森多邊形形心的部署策略特點分析

2.1 虛擬力算法

虛擬力算法(VFA)將移動傳感器節點抽象成虛擬的帶電粒子，當節點間的距離小于某一閾值時，節點間產生斥力;當節點間的距離大于某一閾值時，節點間產生引力。某一節點所受的虛擬力為所有鄰居節點對其產生作用力的合力。

假設第i，j個傳感器節點為si和sj，它們之間的距離為dij，Cth為傳感器節點的通信半徑，Dth為產生吸引力或排斥力的閾值，通常取r≤Dth≤2r［5］，Fij為傳感器節點si受傳感器節點sj的作用力。Fij的計算公式［12］如下:

Fi為傳感器節點si受到所有傳感器節點的合力，具體表示為

其中，aij為傳感器節點si與sj的向量角度;wA，wR為權重系數。節點位置更新公式［12］如下，

圖1為一個無線傳感器節點在虛擬力算法作用下的受力情況。其中:s1為當前分析的節點，s2，s3，s4位于s1的通信半徑范圍之內，是s1的鄰居節點;s5位于s1的通信半徑范圍之外;s2對s1產生排斥作用力F12;s4對s1產生吸引作用力F14;s3和s5不對s1產生作用力;s1所受得虛擬力為F1。

圖1 傳感器節點的虛擬力分析Fig.1 Virtual force analysis diagram of the sensors

缺陷1。虛擬力算法通過距離閾值Dth使傳感器節點間產生引力或斥力從而影響傳感器節點的疏密程度和分布形式，但合適的Dth不僅與傳感器節點的感知范圍r有關，還受到監測區域的面積與形狀的影響，不易求得。即便在最簡單的矩形監測區域，虛擬力算法的最佳Dth可能由2種或3種閾值組合而成。圖2為使用Dth=的無間隙等邊三角形分布形式。不考慮監測區域的影響，理論上可以獲得82.7% 的最佳覆蓋效率［13-14］。但由于受監測區域的面積和形狀的影響，完全覆蓋監測區域需使用33個節點，實際覆蓋效率為61.7%。若使用接近等邊三角形的分布形式(見圖3)，使用30個節點便可完全覆蓋被監測區域，此時覆蓋效率為67.9%。

圖2 理論最佳分布Fig.2 Theoretically optimal distribution

圖3 實際最佳分布Fig.3 Actually optimal distribution

缺陷2。虛擬力算法中進行向量運算所得的虛擬力方向未必指向監測區域的盲區位置。如圖1所示，節點s1沿虛擬力F1方向移動易與節點s3，s4產生較大的重疊覆蓋區域。虛擬力算法中的增益系數wA，wR雖然可以調整虛擬力的方向和大小，但該系數的選擇目前主要依靠人為經驗［5，12，15］，無具體選擇方法。

2.2 基于泰森多邊形的部署策略

基于泰森多邊形的部署算法［7-8，16］(CBS)的基本思路是先對二維監測區域進行 Voronoi圖劃分［17］，使每個傳感器節點覆蓋對應的泰森多邊形以降低問題復雜度［7］，然后通過不同的方法在泰森多邊形的中心區域為傳感器節點尋找一個合適的位置，使傳感器節點在對應泰森多邊形內的覆蓋率最大化。將泰森多邊形形心作為傳感器節點位置是較為簡單直接的方法。若將n邊泰森多邊形n≥3的頂點坐標按順時針方向記為(X1，Y1)，(X2，Y2)，…，(Xn，Yn)，則其形心(cx，cy)可表示為

n邊形的面積M可由如下公式計算

2.3 兩種算法的特點分析

VFA通過設置節點間的距離閾值Dth調整傳感器節點的疏密，從而使覆蓋率提升。VFA調整節點間相對位置的能力較強，在節點分布均勻性方面相比CBS有一定的優勢;CBS無需設置參數，且在覆蓋率上優于VFA。這兩種算法的特點在文中的實驗部分也將得到印證。

3 基于泰森多邊形的形心導向虛擬力的部署算法

3.1 擾動向量

在Voronoi圖中，可使用傳感器節點判斷其對應的泰森多邊形頂點處是否存在盲區［18］。若泰森多邊形頂點被覆蓋則該頂點處不存在盲區，且節點與其鄰居節點在該頂點處形成重疊覆蓋，故文中設計頂點對其形心位置產生排斥作用力，使節點離開重疊覆蓋區域，排斥作用力的大小為感知半徑r與形心至頂點的距離之差;若泰森多邊形頂點未被覆蓋則該頂點處存在盲區，故文中設計頂點對其形心位置產生吸引作用力使節點向盲區移動，吸引作用力的大小為形心至頂點的距離與感知半徑r之差。在此定義單個泰森多邊形形心受其所有頂點的吸引作用力與排斥作用力的合力為擾動向量。

圖4為一個位于泰森多邊形形心處的傳感器節點所對應的擾動向量。圖4中當前分析節點si處于泰森多邊形的形心，泰森多邊形的4個頂點為v1，v2，v3，v4。頂點v1位于si的感知圓上不產生作用力，故f1=0;頂點v2和v3被si覆蓋，對si分別產生排斥作用力f2，f3定義為

頂點v4未被si覆蓋，對si產生吸引作用力f4，定義為

則si所受的作用力合力f'i，即該位置的擾動向量可由下式計算得出，

其中，r2，r3，r4分別為過頂點v2，v3，v4并以 si為終點且長度為感知圓盤半徑r的向量。

圖4 擾動向量分析Fig.4 Disturbance vector analysis diagram

鄰居節點為可相互通信的傳感器節點且其對應的泰森多邊形共邊(共點)。

考慮如圖1所示的5個無線傳感器節點，傳感器節點 si為當前分析的節點，s2，s3，s4，s5為 s1的鄰居節點(s5位于s2的通信半徑之內，s5可采用多跳方式通過s2與s1進行通信，故將s5定義為s1的鄰居節點)。傳統虛擬力算法計算s1的移動方向F1易與s3，s4產生重疊覆蓋(缺陷2)。為了使s1的移動方向更加有效地指向監測區域的盲區位置，分析節點s1擾動向量的同時，考慮其所有鄰居節點的擾動向量，從而使當前分析節點獲得鄰居節點所探測到的盲區信息和重疊覆蓋區域信息，最后取有鄰居關系的節點的擾動向量的均值合成虛擬力。虛擬力擾動形心分析如圖 5 所示。若 s1，s2，s3，s4，s4的擾動向量分別為 f'1，f'2，f'3，f'4，f'5則 s1所受虛擬力為

由圖5中可以看出，泰森多邊形形心位置C受虛擬力F'1干擾后指向的擾動位置S'1相比位置C能夠更有效引導節點向監測區域的盲區擴散。

圖5 虛擬力擾動形心分析Fig.5 Virtual force disturbs centroid analysis diagram

3.2 通信半徑對Voronoi圖劃分的影響

文中使用圖論中無向圖連通的概念表示WSNs的連通性。若WSNs中任意兩個傳感器節點之間至少存在一條通信路徑，則該WSNs連通;否則，此WSNs不連通。不連通的WSNs按圖論中連通分量的概念劃分為多個子網，每個子網在監測區域內單獨進行Voronoi圖劃分(注:子網中傳感器節點數量≥3時劃分Voronoi圖)。圖6～圖9闡述了初始化位置不連通的WSNs采用CBVFA的一次部署過程。圖中的圓盤表示傳感器節點的感知范圍，半徑為r，通信半徑 Cth=2r。

圖6 傳感器節點的初始化位置Fig.6 Initial position of sensors

由圖6可以看出，由30個傳感器節點組成的WSNs，初始化覆蓋率為67.88%。初始化位置的WSNs不連通，將其劃分為 A={s1，s11，s16，s19，s26，s28，s30}和 B={s2，…，s10，s12，…，s15，s17，s18，s20，…，s25，s27，s29}兩個子網。A與B無法通信，故對A和B單獨進行Voronoi圖劃分(實線為子網A的Voronoi圖，虛線為子網B的Voronoi圖)，并按CBVFA單獨部署。在單獨部署過程中，位于雙方網絡邊緣的節點易產生過大的移動步長，如子網A中的s16和s28，子網B中的s10和s23。文中從節省能量的角度出發，設置最大移動步長［12］Maxstep=0.5r。如此經過一次迭代后WSNs連通(見圖7)。

圖7 第一次迭代后傳感器節點位置Fig.7 Position of the sensors after Round 1

圖8為部署算法迭代150次的部署移動軌跡。其中，空心圓標記為節點初始位置，實心三角標記為節點最終位置。圖9為迭代完成時的節點位置，覆蓋率為99.98%。

圖8 傳感器節點的部署軌跡Fig.8 Deployment trace of the sensors

圖9 150次迭代后傳感器節點的位置Fig.9 Position of the sensors after Round 150

3.3 CBVFA步驟描述

1)在監測區域T內隨機部署N個傳感器節點，節點的位置集合為S={s1，s2，…，sN}，si=(xi，yi)。

2)按通信半徑Cth對無線傳感網絡連通性的影響劃分子網 Subnett1，Subnett2，…，Subnetti，…。

3)在監測區域T內對子網Subnetti中的Nsub個傳感器節點進行Voronoi圖劃分，得到泰森多邊形的集合為V={v1，v2，…，vi，…，vNsub}，節點si對應的泰森多邊形為vi。

5)計算所有節點位于形心處的擾動向量，擾動向量的集合為 f'={f'1，f'2，…，f'i，…，f'Nsub}。

7)計算si位于形心ci處的所受得虛擬力f'i，f'i為集合f'Z中擾動向量的均值。并計算si受虛擬力f'i擾動后位置 s'i，s'i=si+f'i。計算 s'i與 si的距離 D，若D ＞Maxstep，則按sis'i方向取步長Maxstep修正s'i的位置。

8)計算節點集合{ci，z1，z2，…，zn}對的覆蓋率

9)計算節點集合{s'i，z1，z2，…，zn}對的覆蓋率

11)重復6)～10)，直至子網Subneti內所有節點的位置更新結束。

12)重復3)～11)，直至所有子網內的節點完成位置更新。

13)重復2)～12)，直至滿足迭代停止條件。

4 仿真實驗

將文獻［5］中的TIVFA、文獻［7］中的CBS與文獻［8］中的CDVFA在覆蓋率CR和節點分布均勻性U兩方面與文中提出的CBVFA進行仿真實驗對比。

監測區域T的大小設置為20 m×20 m，采用文獻［18］中提出的方法計算完全覆蓋T的理論節點數NT為30。仿真實驗中各個算法采用的參數見表1。

表1 仿真實驗參數Tab.1 Parameters of simulation experiment

實驗1取小于NT的節點數量15在30種隨機初始化位置下進行部署實驗，每個實驗迭代50次，得到如圖10所示的部署算法在欠覆蓋情況下的覆蓋能力。此時，監測區域中可供節點移動的盲區大而集中。由圖10可知，CBVFA的覆蓋率提升較快。各部署算法的最終平均覆蓋率分別為:72.67%(CBVFA)，72.46%(CDVFA)，71.19%(CBS)，61.32%(TIVFA)。

圖10 15個節點數量下平均覆蓋率變化曲線Fig.10 Curves of the average coverage rates under different node number

實驗2取30至34個傳感器節點數，每種節點數量在30種隨機初始化位置下進行部署實驗，每個實驗迭代100次。表2為理論節點數量下取不同wA和wR在30種隨機初始化位置下進行部署實驗對CDVFA的最終平均覆蓋率的影響。

表2 不同wA，wR對CDVFA覆蓋率的影響Tab.2 Influence of different wA，wRon the coverage of CDVFA

圖11比較了4種部署算法的最終平均覆蓋率。表3統計了30次部署實驗中各算法100%覆蓋監測區域的次數。由圖11和表3可知，CBVFA在覆蓋率上相比其他3種部署算法具有明顯優勢。隨著節點數量的增加只有CBVFA出現100%覆蓋監測區域的情況。

圖11 不同節點數量下最終覆蓋率比較Fig.11 Comparison of the final coverage rates under different node number

表3 不同節點數量下30次實驗得到100%覆蓋率的次數Tab.3 Times of getting 100% coverage rate in 30 experiments under different node number

圖12比較了在不同節點數量下，4種部署算法在30次部署實驗中的節點分布均勻性的均值。

圖12 不同節點數量下節點分布均勻性比較Fig.12 Distribation uniformity ofsensors under different node number

由圖12可以看出，CDVFA的節點分布均勻性最好，CBVFA次之。

5 結語

文中提出的CBVFA利用泰森多邊形頂點對傳感器節點產生虛擬力，避免了傳統虛擬力算法需要設置距離閾值Dth和權重參數wR，wA的缺陷，并在CBS中加入鄰居節點的影響，與傳統的虛擬力算法和CBS相比較，文中所提的部署算法具有較好的性能。

［1］毛曉峰，楊珉，毛迪林.無線傳感器網絡應用綜述［J］.計算機應用與軟件，2008，25(3):179-181.

MAO Xiaofeng，YANG Min，MAO Dilin.Research on sensor technology face to wireless sensor network［J］.Computer Applications and Software，2008，25(3):179-181.(in Chinese)

［2］任彥，張思東，張宏科.無線傳感器網絡中覆蓋控制理論與算法［J］.軟件學報，2006，17(3):422-433.

REN Yan，ZHANG Sidong，ZHANG Hongke.Theories and algorithms of coverage control for wireless sensor networks［J］.Journal of Software，2006，17(3):422-433.(in Chinese)

［3］Howard A，Mataric M J，Sukhatme G S.An incremental self-deployment algorithm for mobile sensor networks［J］.Autonomous Robots，2002，13(2):113-126.

［4］Howard A，Mataric M J，Sukhatme G S.Mobile Sensor Network Deployment Using Potential Fields:A Distributed，Scalable Solution to the Area Coverage Problem［M］.Tokyo:Springer Japan，2002:299-308.

［5］LI S，XU C，PAN W，et al.Sensor deployment optimization for detecting maneuvering targets［C］//Proceedings of the 2005 8th International Conference on Information Fusion.Piscataway，NJ:IEEE，2005:1629-1635.

［6］YU X，HUANG W，LAN J，et al.A novel virtual force approach for node deployment in wireless sensor network［C］//Proceedings of the 2012 IEEE 8th International Conference on Distributed Computing in Sensor Systems.Piscataway，NJ:IEEE，2012:359-363.

［7］LEE H J，KIM Y H，HAN Y H，et al.Centroid-based movement assisted sensor deployment schemes in wireless sensor networks［C］//Proceedings of the 2009 IEEE 70th Vehicular Technology Conference Fall.Piscataway，NJ:IEEE，2009:1-5.

［8］HAN Y H，KIM Y H，KIM W，et al.An energy-efficient self-deployment with the centroid-directed virtual force in mobile sensor networks［J］.Simulation，2011，88(10):1152-1165.

［9］張騫，李克清，戴歡，等.基于協同進化蜂群算法的覆蓋優化策略［J］.計算機工程與設計，2014，25(4):1142-1146.

ZHANG Qian，LI Keqing，DAI Huan，et al.Coverage optimization strategy based on co-evolution bee colony algorithm［J］.Computer Engineering and Design，2014，25(4):1142-1146.(in Chinese)

［10］熊偉麗，劉欣，陳敏芳，等.基于差分蜂群算法的無線傳感器網絡節點分布優化［J］.控制工程，2014，21(6):1036-1040.

XIONG Weili，LIU Xin，CHEN Minfang，et al.Node distribution optimization in wireless sensor networks based on differential bee colony algorithm［J］.Control Engineering of China，2014，21(6):1036-1040.(in Chinese)

［11］劉麗萍.無線傳感器網絡節能覆蓋［D］.杭州:浙江大學，2006.

［12］王雪，王晟，馬俊杰.無線傳感網絡布局的虛擬力導向微粒群優化策略［J］.電子學報，2007，35(11):2038-2042.

WANG Xue，WANG Sheng，MA Junjie.Dynamic sensor deployment strategy based on virtual force-directed particle swarm optimization in wireless sensor networks［J］.Acta Electronica Sinica，2007，35(11):2038-2042.(in Chinese)

［13］關志艷，耿巖.虛擬力導向群聚智能優化的無線傳感器網絡覆蓋策略［J］.傳感器與微系統，2015，34(1):40-42，46.

GUAN Zhiyan，CENG Yan.Coverage strategy for wireless sensor networks based on virtual force directed swarm intelligence optimization［J］.Transducer and Microsystem Technologies，2015，34(1):40-42，46.(in Chinese)

［14］楊云，石婷婷，徐平，等.一種具有魯棒性的異構傳感器網絡部署策略［J］.計算機應用與軟件，2011(6):51-53，68.

YANG Yun，SHI Tingting，XU Ping，et al.A new deployment strategy for heterogeneous wireless sensor networks with robustness［J］.Computer Applications and Software，2011(6):51-53，68.(in Chinese)

［15］WANG Y C，WU F J，TSENG Y C.Mobility management algorithms and applications for mobile sensor networks［J］.Wireless Communications and Mobile Computing，2012，12(1):7-21.

［16］Mahboubi H，Moezzi K，Aghdam A G，et al.Distributed deployment algorithms for improved coverage in a network of wireless mobilesensors［J］.IEEE Transactions on Industrial Informatics，2014，10(1):163-174.

［17］趙春江，吳華瑞，劉強，等.基于Voronoi的無線傳感器網絡覆蓋控制優化策略［J］.通信學報，2013(9):115-122.

ZHAO Chunjiang，WU Huarui，LIU Qiang，et al.Optimization strategy on coverage control in wireless sensor network based on Voronoi［J］.Journal on Communications，2013(9):115-122.(in Chinese)

［18］方偉，宋鑫宏.基于Voronoi圖盲區的無線傳感器網絡覆蓋控制部署策略［J］.物理學報，2014，63(22):132-141.

FANG Wei，SONG Xinhong.A deployment strategy for coverage control in wireless sensor networks based on the blind-zone of Voronoi diagram［J］.Acta Phys Sin，2014，63(22):132-141.(in Chinese)