王婷婷，孫彥景，2*，徐　釗，張曉光

（1.中國(guó)礦業(yè)大學(xué)信息與電氣工程學(xué)院，江蘇徐州221116；2.江蘇省煤礦電氣與自動(dòng)化工程實(shí)驗(yàn)室，江蘇徐州221008）

基于虛擬力的異構(gòu)無(wú)線傳感器網(wǎng)絡(luò)覆蓋優(yōu)化策略*

王婷婷1，孫彥景1，2*，徐釗1，張曉光1

（1.中國(guó)礦業(yè)大學(xué)信息與電氣工程學(xué)院，江蘇徐州221116；2.江蘇省煤礦電氣與自動(dòng)化工程實(shí)驗(yàn)室，江蘇徐州221008）

針對(duì)異構(gòu)無(wú)線傳感器網(wǎng)絡(luò)覆蓋優(yōu)化過(guò)程中，固定Sink節(jié)點(diǎn)的虛擬作用力限制移動(dòng)節(jié)點(diǎn)的位置移動(dòng)，導(dǎo)致覆蓋盲區(qū)得不到全局修復(fù)的問(wèn)題，本文結(jié)合計(jì)算幾何理論，提出基于Voronoi多邊形形心引力的虛擬力覆蓋優(yōu)化算法（CAVFA）。虛擬力算法能有效指導(dǎo)移動(dòng)節(jié)點(diǎn)的散布過(guò)程，形心引力能更好地實(shí)現(xiàn)全局的覆蓋優(yōu)化。通過(guò)合理設(shè)置虛擬力的距離閾值參數(shù)和優(yōu)先級(jí)，調(diào)整固定節(jié)點(diǎn)對(duì)移動(dòng)節(jié)點(diǎn)的約束。仿真表明，相比傳統(tǒng)VFA算法和CBA算法，本文提出的CAVFA算法能夠更有效地提高異構(gòu)網(wǎng)絡(luò)的覆蓋率，且算法收斂速度更快。

無(wú)線傳感器網(wǎng)絡(luò)；異構(gòu)網(wǎng)絡(luò)；網(wǎng)絡(luò)覆蓋；虛擬力；優(yōu)化算法

現(xiàn)代傳感器與執(zhí)行器相結(jié)合實(shí)現(xiàn)了傳感器節(jié)點(diǎn)的移動(dòng)，可移動(dòng)的無(wú)線傳感器網(wǎng)絡(luò)WSNs（Wireless Sensor Networks）以其高度的靈活性和集成功能多樣化，其應(yīng)用已經(jīng)滲透到軍事偵察、防爆救災(zāi)、環(huán)境監(jiān)測(cè)等各個(gè)領(lǐng)域［1-4］。覆蓋是無(wú)線傳感網(wǎng)絡(luò)應(yīng)用的基礎(chǔ)，覆蓋性能的好壞直接體現(xiàn)網(wǎng)絡(luò)的感知、監(jiān)視和通信等服務(wù)質(zhì)量，覆蓋算法的性能優(yōu)劣同樣影響著網(wǎng)絡(luò)的生存周期。傳感器節(jié)點(diǎn)受到能量、存儲(chǔ)容量、計(jì)算能力、移動(dòng)性等自身?xiàng)l件的約束限制，通常具有異構(gòu)性，主要包括移動(dòng)性、感知和通信能力以及能量等方面差異［5-7］。

近年來(lái)，對(duì)無(wú)線傳感器網(wǎng)絡(luò)覆蓋性能優(yōu)化的算法研究已有大量的成果，包括基于計(jì)算幾何理論的理想節(jié)點(diǎn)模型約束下的無(wú)線傳感網(wǎng)絡(luò)覆蓋建模方法，如基于Delaunay、Voronoi等網(wǎng)格劃分分析方法［2-3，8-9］；仿生物學(xué)的智能群體優(yōu)化算法［10-11］，以及基于物理力學(xué)原理的虛擬力算法［3，9］等。Lee 2009等［12］提出了基于泰森多邊形形心的部署策略CBS （Centroid-Based Scheme），采用移動(dòng)節(jié)點(diǎn)的分布式模式，提出基于Voronoi多邊形形心的概念，設(shè)計(jì)了基于CBS（Centroid-Based Scheme）的自組織節(jié)點(diǎn)部署優(yōu)化策略，將節(jié)點(diǎn)移動(dòng)至本地Voronoi多邊形的形心位置，覆蓋性能得到一定程度的改善，但是在節(jié)點(diǎn)移動(dòng)后容易產(chǎn)生新的覆蓋盲區(qū)。虛擬力導(dǎo)向算法［3，9-10，13-14］在擴(kuò)大網(wǎng)絡(luò)覆蓋范圍，優(yōu)化網(wǎng)絡(luò)連接等方面表現(xiàn)突出。但是僅能夠滿足純移動(dòng)節(jié)點(diǎn)構(gòu)成的無(wú)線傳感網(wǎng)絡(luò)的部署優(yōu)化需求。

而在移動(dòng)特性異構(gòu)的WSN中，往往是由位置固定的Sink節(jié)點(diǎn)和移動(dòng)傳感器節(jié)點(diǎn)組成。在用傳統(tǒng)虛擬力算法（VFA）進(jìn)行覆蓋優(yōu)化時(shí)，移動(dòng)節(jié)點(diǎn)會(huì)因?yàn)槭艿焦潭ü?jié)點(diǎn)的虛擬力約束，難以實(shí)現(xiàn)覆蓋區(qū)域的全局優(yōu)化。為解決這一問(wèn)題，王雪等［10］提出基于概率感知模型的傳感器網(wǎng)絡(luò)進(jìn)行的虛擬力導(dǎo)向粒子群覆蓋優(yōu)化策略，關(guān)志艷等［14］提出虛擬力導(dǎo)向群居智能優(yōu)化算法，虛擬力距離閾值參數(shù)來(lái)改善固定節(jié)點(diǎn)作用在移動(dòng)節(jié)點(diǎn)上的虛擬力，用虛擬力影響群聚智能算法中粒子速度和距離的進(jìn)化，以節(jié)點(diǎn)有效覆蓋率為適應(yīng)值，指導(dǎo)微粒進(jìn)化。雖然虛擬力算法能有效指導(dǎo)移動(dòng)節(jié)點(diǎn)的散布過(guò)程，微粒群算法具有很強(qiáng)的全局優(yōu)化能力，能消除固定節(jié)點(diǎn)對(duì)全局優(yōu)化的影響。但是計(jì)算耗時(shí)仍是嚴(yán)重制約微粒群算法在無(wú)線傳感網(wǎng)絡(luò)布局優(yōu)化中應(yīng)用的瓶頸之一。

為實(shí)現(xiàn)對(duì)異構(gòu)無(wú)線傳感器網(wǎng)絡(luò)的覆蓋優(yōu)化，受計(jì)算幾何理論啟發(fā)，結(jié)合Voronoi圖的特點(diǎn)，對(duì)虛擬力算法進(jìn)行了改進(jìn)，提出基于Voronoi多邊形形心引力的虛擬力覆蓋優(yōu)化算法 CAVFA（Centroidbased Attractive Virtual Force Algorithm）。通過(guò)合理設(shè)置虛擬力距離閾值參數(shù)和優(yōu)先級(jí)來(lái)改善固定節(jié)點(diǎn)對(duì)移動(dòng)節(jié)點(diǎn)的約束，通過(guò)實(shí)驗(yàn)證明了所提算法對(duì)實(shí)現(xiàn)異構(gòu)WSN全局覆蓋的有效性。

1　問(wèn)題與假設(shè)

假設(shè)無(wú)線傳感器網(wǎng)絡(luò)由N1個(gè)固定Sink節(jié)點(diǎn)集G和N2個(gè)移動(dòng)傳感器節(jié)點(diǎn)集S組成，移動(dòng)傳感器節(jié)點(diǎn)通過(guò)直接或間接多跳的方式連接到Sink節(jié)點(diǎn)，進(jìn)行數(shù)據(jù)傳輸。節(jié)點(diǎn)的感知半徑均為Rs，隨機(jī)拋撒在監(jiān)測(cè)區(qū)域A中，A為二維平面應(yīng)用場(chǎng)景下的面積為L(zhǎng)×H的矩形區(qū)域。節(jié)點(diǎn)模型均采用布爾感知模型，Rc為節(jié)點(diǎn)的通信半徑，并滿足Rc≥2Rs。對(duì)無(wú)線傳感器網(wǎng)絡(luò)參數(shù)進(jìn)行如下假設(shè)：①Sink節(jié)點(diǎn)位置固定，并較均勻地分布在待覆蓋區(qū)域中；②無(wú)線傳感器網(wǎng)絡(luò)中的所有節(jié)點(diǎn)初始位置可自知，第i個(gè)傳感器節(jié)點(diǎn)Si的位置坐標(biāo)為（xi，yi）；③節(jié)點(diǎn)的通信半徑是感知半徑的2倍，即Rc=2Rs，在節(jié)點(diǎn)通信范圍內(nèi)的節(jié)點(diǎn)為鄰居節(jié)點(diǎn)；④網(wǎng)絡(luò)包含一個(gè)信息處理中心節(jié)點(diǎn)，具有較強(qiáng)的計(jì)算能力，用于實(shí)現(xiàn)網(wǎng)絡(luò)布局優(yōu)化；⑤每個(gè)傳感器節(jié)點(diǎn)配備移動(dòng)執(zhí)行器，可以在監(jiān)測(cè)區(qū)域內(nèi)自由移動(dòng)，且有足夠的能量到達(dá)指定位置，忽略邊界的斥力。

相關(guān)定義如下：

定義1布爾感知模型［1］節(jié)點(diǎn)的最大感知范圍是以自身位置坐標(biāo)（xi，yi）為中心、長(zhǎng)度r為半徑的圓形，即為布爾感知模型。目標(biāo)點(diǎn)t與傳感器節(jié)點(diǎn)s之間的歐式距離記為

若d（si，tj）≤Rs，則目標(biāo)點(diǎn)被覆蓋，節(jié)點(diǎn)si對(duì)目標(biāo)點(diǎn)tj的感知概率p為1，否則為0，如下式所示：

定義2形心［15］形心是抽象幾何圖形的幾何中心。對(duì)于密度均勻的物體，形心與假想的質(zhì)量中心相重合，因此有的文獻(xiàn)也稱質(zhì)心。

定義3覆蓋率［16］已被節(jié)點(diǎn)覆蓋的區(qū)域面積S（B）與待監(jiān)測(cè)區(qū)域面積S（A）之比為覆蓋率，記為η，定義為

2　Voronoi多邊形的形心計(jì)算

將網(wǎng)絡(luò)覆蓋問(wèn)題簡(jiǎn)化為二維平面中隨機(jī)布散的點(diǎn)，為簡(jiǎn)化覆蓋求解過(guò)程，借助計(jì)算幾何中的Voronoi圖，對(duì)這N個(gè)在平面上有區(qū)別的點(diǎn)，按照最鄰近原則劃分平面，又叫泰森多邊形或Dirichlet圖，它是由一組由連接兩鄰點(diǎn)直線的垂直平分線組成的連續(xù)多邊形組成，構(gòu)成Voronoi圖的凸多邊形稱為泰森多邊形或者Voronoi單元，如圖1（a）所示。不難發(fā)現(xiàn)，在每個(gè)多邊形內(nèi)的點(diǎn)到該節(jié)點(diǎn)的距離比到其他任何節(jié)點(diǎn)的距離都小。

圖1　Voronoi網(wǎng)格圖與多邊形形心

泰森多邊形的形心是所有將多邊形平分成兩個(gè)等面積區(qū)域的直線的交點(diǎn)［12］。如圖1（b）所示，節(jié)點(diǎn)S所在VOR多邊形包含有m個(gè)邊和m個(gè)頂點(diǎn)，多邊形頂點(diǎn)坐標(biāo)集合為V=｛（vx1，vy1），（vx2，vy2）…（vxm，vym）｝。通過(guò)修正Lee在文獻(xiàn)［12］中所用的形心計(jì)算方法，計(jì)算該多邊形的形心（Cx，Cy），公式如下：

其中Sv為Voronoi多邊形的面積，計(jì)算如下：

Voronoi多邊形與目標(biāo)點(diǎn)的覆蓋情況的對(duì)應(yīng)幾何關(guān)系可以有效確定盲區(qū)位置［3，12］，Voronoi（簡(jiǎn)寫(xiě)為VOR）圖是解決覆蓋控制問(wèn)題的一種有效的幾何方法，VOR單元結(jié)構(gòu)可實(shí)現(xiàn)局部的或者分布式算法設(shè)計(jì)，而無(wú)需已知全局信息；通過(guò)網(wǎng)格劃分將網(wǎng)絡(luò)覆蓋優(yōu)化問(wèn)題轉(zhuǎn)換為每個(gè)傳感器節(jié)點(diǎn)各自覆蓋對(duì)應(yīng)VOR多邊形區(qū)域內(nèi)的優(yōu)化問(wèn)題，降低了問(wèn)題的復(fù)雜性與計(jì)算復(fù)雜度。本文利用VOR形心的幾何特性，將其引入虛擬力算法中，解決異構(gòu)網(wǎng)絡(luò)中固定節(jié)點(diǎn)對(duì)移動(dòng)節(jié)點(diǎn)的束縛問(wèn)題，通過(guò)引力約束，優(yōu)化全局的節(jié)點(diǎn)覆蓋率和均勻性。

3　相關(guān)算法

3.1VFA算法

虛擬力算法VFA（Virtual Force Algorithm）起源于虛擬勢(shì)場(chǎng)［17］，起初被用于機(jī)器人移動(dòng)過(guò)程中的障礙物避讓，后來(lái)被引用到WSN節(jié)點(diǎn)部署策略中［1］，優(yōu)化網(wǎng)絡(luò)覆蓋。通過(guò)將移動(dòng)傳感器節(jié)點(diǎn)虛擬成帶電粒子，并假設(shè)存在一個(gè)距離閾值，當(dāng)兩個(gè)粒子間的距離大于該閾值，粒子間的作用力為引力；當(dāng)粒子間的距離小于該閾值，粒子間的作用力為斥力。通過(guò)虛擬作用力的引導(dǎo)，網(wǎng)絡(luò)可以通過(guò)節(jié)點(diǎn)間的距離調(diào)整，實(shí)現(xiàn)區(qū)域的有效覆蓋，通過(guò)合理的閾值設(shè)定，達(dá)到滿足部署要求的覆蓋效果。假設(shè)節(jié)點(diǎn)Si所受的虛擬作用力包括其他節(jié)點(diǎn)的作用力FιJ，障礙物和邊界的斥力，以及待覆蓋區(qū)域中未被覆蓋的點(diǎn)對(duì)節(jié)點(diǎn)的引力等，將總的斥力記為（repulsive）FιR，引力記為（attractive）FιA，節(jié)點(diǎn)Si所受的合力記為Fι，則有

節(jié)點(diǎn)間的作用力屬性是由距離決定的，通常根據(jù)網(wǎng)絡(luò)的具體應(yīng)用環(huán)境以及對(duì)覆蓋性能的要求進(jìn)行設(shè)置。

3.2CBA算法

針對(duì)移動(dòng)傳感器節(jié)點(diǎn)分布式自組織優(yōu)化算法研究中，最早由Lee 2009等［12］提出的基于VOR多邊形形心的部署策略CBS（Centroid-Based Scheme），包括 Centroid和 Dual-Centroid兩種模式。Dual-Centroid是將節(jié)點(diǎn)移動(dòng)至Voronoi多邊形和鄰居節(jié)點(diǎn)構(gòu)成的多邊形的兩個(gè)質(zhì)心的線段中點(diǎn)處，如圖2所示：A點(diǎn)為節(jié)點(diǎn)S所在VOR多邊形的質(zhì)心，點(diǎn)B為鄰居節(jié)點(diǎn)構(gòu)成的多邊形的質(zhì)心點(diǎn)，C為線段AB的中點(diǎn)。Centroi-Based Algorithm（CBA）是將節(jié)點(diǎn)移動(dòng)至本地Voronoi多邊形質(zhì)心位置處。雙質(zhì)心的算法求解過(guò)程比較復(fù)雜，且覆蓋優(yōu)化效果并不優(yōu)于CBA算法，因此本文采用CBA算法作為對(duì)比算法。

由于CBA算法是基于VOR圖網(wǎng)格劃分實(shí)現(xiàn)的，節(jié)點(diǎn)被看作分布在區(qū)域內(nèi)的點(diǎn)，并不考慮節(jié)點(diǎn)的感知范圍因素，在半徑異構(gòu)的WSN覆蓋優(yōu)化應(yīng)用中，CBA算法并不直接適用，需要與虛擬力算法相結(jié)合，以實(shí)現(xiàn)更優(yōu)的覆蓋。

圖2　基于質(zhì)心的部署策略

4CAVFA算法描述

4.1受力分析

本文的網(wǎng)絡(luò)環(huán)境包括位置固定的骨干節(jié)點(diǎn)和移動(dòng)的傳感器節(jié)點(diǎn)，網(wǎng)絡(luò)初始化設(shè)定骨干節(jié)點(diǎn)位置，并保持靜止，傳感器節(jié)點(diǎn)在待測(cè)區(qū)域隨機(jī)部署，并在虛擬力的約束下進(jìn)行散布行為決策，調(diào)整網(wǎng)絡(luò)覆蓋度和冗余度。本文采用布爾圓盤(pán)感知模型，假設(shè)節(jié)點(diǎn)的通信半徑為Rc，節(jié)點(diǎn)位置為中心的圓盤(pán)，質(zhì)心即為該節(jié)點(diǎn)的坐標(biāo)，記為受力點(diǎn)S。假設(shè)監(jiān)測(cè)區(qū)域?yàn)榫匦?，但現(xiàn)實(shí)中的區(qū)域邊界并不規(guī)則，因此本文忽略邊界的作用力?？梢苿?dòng)傳感器節(jié)點(diǎn)的受力包括固定骨干節(jié)點(diǎn)的作用力、移動(dòng)節(jié)點(diǎn)間的作用力、未被覆蓋區(qū)域格點(diǎn)引力以及Vornoi多邊形質(zhì)心引力的作用。具體受力分析如下。

其中未被覆蓋的區(qū)域中的格點(diǎn)Gi（gxi，gyi）對(duì)傳感器節(jié)點(diǎn)Si（xi，yi）的作用力設(shè)為引力（attractive），Dij為Gi與Si之間的距離，記為FιA，計(jì)算如下：

節(jié)點(diǎn)Si所在的VOR多邊形的形心Ci對(duì)節(jié)點(diǎn)的作用力設(shè)為引力，方向?yàn)镾i到Ci連線的方向，記為FιC，計(jì)算如下：

節(jié)點(diǎn)Si和其他節(jié)點(diǎn)（可以是固定節(jié)點(diǎn)或者移動(dòng)節(jié)點(diǎn)）Sj之間的作用力記為FιJ（且i≠j），作用力的性質(zhì)由節(jié)點(diǎn)間的歐式距離決定。虛擬勢(shì)場(chǎng)算法采用距離閾值來(lái)調(diào)整WSN節(jié)點(diǎn)間的相互作用力FιJ的屬性，設(shè)dij是節(jié)點(diǎn)Si與Sj之間的歐式距離，如式（1）所示，dth是節(jié)點(diǎn)間通信的臨界距離。當(dāng)dij大于dth且小于Rc時(shí)，兩者之間的作用力為引力；當(dāng)dij小于dth時(shí)，作用力為斥力，F(xiàn)ιJ關(guān)系式如式（9）所示。

其中，αij是節(jié)點(diǎn)Si到節(jié)點(diǎn)Sj線段的方向角，ka/kb分別為虛擬力引力/斥力系數(shù)。且FιJ僅在兩鄰居節(jié)點(diǎn)之間產(chǎn)生，即dij≤RC，減少算法計(jì)算量。已知區(qū)域一次覆蓋的最佳部署方式為正三角形部署方式，如圖3所示，因此本文以正三角形為覆蓋目標(biāo)，設(shè)置節(jié)點(diǎn)間的距離為。

以節(jié)點(diǎn)間虛擬力為例，那么節(jié)點(diǎn)Si所受鄰居節(jié)點(diǎn)作用力的總和記為Fι，表達(dá)式如式（10）所示。

節(jié)點(diǎn)所受虛擬力Fι可分解為x與y兩個(gè)方向，力的大小為Fxy，且存在如下向量關(guān)系和矢量關(guān)系：

無(wú)線傳感器節(jié)點(diǎn)在虛擬力Fxy作用的約束下，將按照如下配置方式對(duì)節(jié)點(diǎn)位置進(jìn)行調(diào)整：

其中，（x_old，y_old）為節(jié)點(diǎn)原來(lái)的位置坐標(biāo)，算法每執(zhí)行一輪，節(jié)點(diǎn)位置坐標(biāo)更新為（x_new，y_new）。max_step是虛擬力步長(zhǎng)，可分為max_grid、max_sensor、max_center，分別為在熱點(diǎn)區(qū)域網(wǎng)格點(diǎn)、傳感器節(jié)點(diǎn)和質(zhì)心引力的作用下的半徑調(diào)整步長(zhǎng)。虛擬力算法的設(shè)計(jì)過(guò)程就是尋找使網(wǎng)絡(luò)內(nèi)部節(jié)點(diǎn)所受虛擬力達(dá)到平衡狀態(tài)的一個(gè)過(guò)程。

圖3　正三角形部署模式

4.2算法偽代碼

基于上述分析，合計(jì)算幾何理論，提出一種基于泰森多邊形形心引力的虛擬力覆蓋優(yōu)化算法（CAVFA）。虛擬力算法能有效指導(dǎo)移動(dòng)節(jié)點(diǎn)的散布過(guò)程，形心引力能更好地實(shí)現(xiàn)全局的覆蓋優(yōu)化。通過(guò)合理設(shè)置虛擬力距離閾值參數(shù)和優(yōu)先級(jí)來(lái)改善固定節(jié)點(diǎn)對(duì)移動(dòng)節(jié)點(diǎn)的約束，以實(shí)現(xiàn)全局的覆蓋優(yōu)化，提高網(wǎng)絡(luò)覆蓋效率和虛擬力算法性能。算法實(shí)現(xiàn)的偽代碼如下。

輸入：

監(jiān)測(cè)區(qū)域L×H，N1個(gè)固定骨干節(jié)點(diǎn)坐標(biāo)SN1=｛（x1，y1），（x2，y2…（xN1，yN1）｝，N2個(gè)移動(dòng)傳感器節(jié)點(diǎn)的坐標(biāo)的集合SN2=｛（x1，y1），（x2，y2…（xN2，yN2）｝，節(jié)點(diǎn)感知半徑Rs，迭代次數(shù)max-iteration，節(jié)點(diǎn)間的距離閾值 dth，最大移動(dòng)步長(zhǎng) max_sensor、max_grid、max_center，虛擬力閾值fth.

輸出：移動(dòng)傳感器節(jié)點(diǎn)坐標(biāo)SN2，覆蓋率fth.

算法描述：

（1）SN1；rand（SN2）；//初始化部署

（2）while（t＜max-iteration）

（3）Fι←0，F(xiàn)ιJ←0，F(xiàn)ιC←0，F(xiàn)ιA←0；

（4） VOR網(wǎng)格劃分，根據(jù)式（4）、式（5）計(jì)算每個(gè)V單元的質(zhì)心Ci（cxi，cyi）；

（5）for（i=0；i＜N2；i++）

（6）if（cxi，cyi）∈A

（7）根據(jù)式（7）進(jìn)行FιC計(jì)算；

（8）根據(jù)式（11），帶入max_center進(jìn)行節(jié)點(diǎn)虛擬移動(dòng)；

（9）end

（10）end

（11） for（i=0；i＜N2；i++）

（12）計(jì)算節(jié)點(diǎn)間的距離dij

（14）按式（8）進(jìn)行FιJ計(jì)算

（15） 根據(jù)式（11），帶入max_sensor進(jìn)行節(jié)點(diǎn)虛擬移動(dòng)；

（16）end

（17） end

（18） for（i=0；i＜N2；i++）

（19）計(jì)算未被覆蓋格點(diǎn)與節(jié)點(diǎn)間距離Dij

（20）if Dij＜Rc

（21）按式（6）計(jì)算引力FιA

（22） 根據(jù)式（11），帶入max_grid進(jìn)行節(jié)點(diǎn)虛擬移動(dòng)；

（23） end

（24） end

（25） 更新節(jié)點(diǎn)位置，進(jìn)行位移移動(dòng)，計(jì)算覆蓋率

（26） 循環(huán)迭代

（27）end%算法結(jié)束

5　仿真結(jié)果及性能分析

本節(jié)通過(guò)仿真來(lái)驗(yàn)證算法對(duì)提高網(wǎng)絡(luò)覆蓋質(zhì)量的有效性，并對(duì)算法性能進(jìn)行分析，包括收斂性能、復(fù)雜性，及其影響參數(shù)的討論。本章的算法是針對(duì)節(jié)點(diǎn)異構(gòu)的移動(dòng)無(wú)線傳感器網(wǎng)絡(luò)進(jìn)行的覆蓋優(yōu)化，通過(guò)引入VOR形心約束力對(duì)節(jié)點(diǎn)的移動(dòng)進(jìn)行干預(yù)，提高感知覆蓋率的同時(shí)，加速了算法收斂。與VFA和CBA算法進(jìn)行了對(duì)比分析，結(jié)果驗(yàn)證了VOR形心引力導(dǎo)向?qū)μ摂M力算法性能改進(jìn)的有效性。本節(jié)中的仿真實(shí)驗(yàn)均是在Matlab R2012b環(huán)境下進(jìn)行的，仿真實(shí)驗(yàn)參數(shù)設(shè)置如表1所示。

文獻(xiàn)［18］在對(duì)距離閾值調(diào)節(jié)虛擬力屬性的模型的研究中指出，用到的虛擬力的引力系數(shù)和斥力系數(shù)幾乎是與覆蓋率不相關(guān)，故設(shè)為相同的常數(shù)值?？紤]到覆蓋算法的能效性，節(jié)點(diǎn)的最大移動(dòng)步長(zhǎng)一般取感知半徑的1/2［10］。本文通過(guò)幾組步長(zhǎng)值對(duì)覆蓋率的優(yōu)化效果對(duì)比分析實(shí)驗(yàn)，從經(jīng)驗(yàn)值中選取了對(duì)算法有利的步長(zhǎng)值，作為下一步的實(shí)驗(yàn)仿真參數(shù)。

表1　仿真實(shí)驗(yàn)參數(shù)

首先對(duì)幾個(gè)參數(shù)對(duì)算法性能的影響進(jìn)行分析，包括最大移動(dòng)步長(zhǎng)，固定和移動(dòng)節(jié)點(diǎn)數(shù)量分配。圖4所示為4組不同的最大移動(dòng)步長(zhǎng)設(shè)置條件下的覆蓋有效效果圖，參數(shù)設(shè)置如表2所示，且其他參數(shù)設(shè)置為Rs=7 m，N1=16，N2=60，初始化覆蓋率為67%，算法運(yùn)行100次以后的覆蓋率分別為80%，85%，90%，89%。

圖4　CAVFA算法運(yùn)行時(shí)待監(jiān)測(cè)區(qū)域覆蓋情況，綠色為固定節(jié)點(diǎn)，藍(lán)色的為移動(dòng)傳感器節(jié)點(diǎn)

表2　參數(shù)對(duì)優(yōu)化性能的影響

仿真結(jié)果表明適當(dāng)減小最大移動(dòng)步長(zhǎng)，覆蓋率有一定程度的提高，且當(dāng)max_grid＞max_center時(shí)的覆蓋效果最佳。第4組數(shù)據(jù)表明移動(dòng)步長(zhǎng)并不是越小越好。在后面的算法對(duì)比分析中都選用第3組步長(zhǎng)設(shè)置。

部署在待覆蓋區(qū)域的節(jié)點(diǎn)總數(shù)為100個(gè)，分析固定節(jié)點(diǎn)和移動(dòng)節(jié)點(diǎn)的不同分配方式對(duì)算法性能的影響，選取兩組數(shù)據(jù)，并與VFA和CBA算法進(jìn)行了性能對(duì)比，如圖5和表3所示。仿真結(jié)果顯示，在N1= 80，N2=20的條件下，經(jīng)過(guò)100次循環(huán)后，CAVFA算法所能提高的覆蓋率百分比為16%，VFA和CBA算法分別能提高的覆蓋率百分比為15%和12%，CAVFA性能略優(yōu)于其他算法；在N1=40，N2=60的條件下，經(jīng)過(guò)100次循環(huán)后，CAVFA算法提高了覆蓋率的31%，明顯優(yōu)于其他兩種算法的覆蓋效果28%和27%。從圖5（d）可以看出，即使在固定節(jié)點(diǎn)數(shù)遠(yuǎn)多于傳感器節(jié)點(diǎn)數(shù)時(shí)，CAVFA也能實(shí)現(xiàn)全局的均勻覆蓋，這是因?yàn)橥ㄟ^(guò)Voronoi網(wǎng)格劃分提高了節(jié)點(diǎn)覆蓋的公平性，進(jìn)而解決了固定節(jié)點(diǎn)對(duì)移動(dòng)節(jié)點(diǎn)的約束問(wèn)題。

圖5　VFACBACAVFA算法覆蓋優(yōu)化效果圖

表3　固定節(jié)點(diǎn)與移動(dòng)節(jié)點(diǎn)數(shù)的分配

算法運(yùn)行時(shí)間和收斂性的比較與分析，如圖6所示，描繪了待監(jiān)測(cè)區(qū)域內(nèi)的覆蓋率在覆蓋優(yōu)化算法隨執(zhí)行時(shí)間的變化情況，節(jié)點(diǎn)數(shù)：N1=40，N2=60，算法運(yùn)行時(shí)間：T_CAVFA=40 s，T_CBA=28 s，T_VFA= 30 s。雖然CAVFA算法運(yùn)行100次所需的時(shí)間大約為40 s，耗時(shí)比CBA和VFA各自的運(yùn)行時(shí)間長(zhǎng)，但是本文所提的算法完成了對(duì)形心和虛擬力的遍歷搜索，并且耗時(shí)小于CBA與VFA算法之和，這說(shuō)明本文的算法迅速有效。從圖6可以看出前5個(gè)步長(zhǎng)內(nèi)，待監(jiān)測(cè)區(qū)域的覆蓋率均得到了較大幅度的提升，其中本文提出的CAVFA算法與初始覆蓋率相比提高了22個(gè)百分點(diǎn)，并高于VFA和CBA算法。在5個(gè)步長(zhǎng)以后，CAVFA算法對(duì)覆蓋率的優(yōu)化效果減慢，但仍有提升的空間，并趨于平穩(wěn)；而VFA優(yōu)化效果不穩(wěn)定，隨著步長(zhǎng)的增加反而出現(xiàn)了下降的趨勢(shì)；CBA算法的優(yōu)化性能趨于平緩。三種算法在10個(gè)步長(zhǎng)以后均趨于收斂。由此可見(jiàn)本文提出的算法CAVFA結(jié)合了VFA和CBA算法的優(yōu)點(diǎn)，充分利用虛擬力算法的全局搜索特性，又將局部單元優(yōu)化方法引入，克服了傳統(tǒng)虛擬力算法優(yōu)化過(guò)程中出現(xiàn)的局部節(jié)點(diǎn)聚焦的現(xiàn)象，從而實(shí)現(xiàn)了對(duì)待監(jiān)測(cè)區(qū)域高效、均勻的覆蓋。

圖6　算法運(yùn)行100次所需的時(shí)間與覆蓋率的關(guān)系圖

6　總結(jié)

基于Voronoi多邊形形心引力的虛擬力優(yōu)化的異無(wú)線傳感器網(wǎng)絡(luò)覆蓋策略在傳統(tǒng)虛擬力算法的基礎(chǔ)上，引入了基于計(jì)算幾何理論中的Voronoi多邊形形心的虛擬引力，通過(guò)調(diào)整虛擬力距離閾值參數(shù)、節(jié)點(diǎn)移動(dòng)步長(zhǎng)和虛擬力優(yōu)先級(jí)等參數(shù)設(shè)置，來(lái)改善來(lái)克服固定節(jié)點(diǎn)對(duì)移動(dòng)節(jié)點(diǎn)的虛擬力作用限制。通過(guò)實(shí)驗(yàn)驗(yàn)證了本算法的有效性，結(jié)果表明：相比傳統(tǒng)虛擬力算法和基于Voronoi形心的覆蓋優(yōu)化策略，基于Voronoi多邊形形心引力的虛擬力優(yōu)化算法實(shí)現(xiàn)了對(duì)異構(gòu)無(wú)線傳感器網(wǎng)絡(luò)的全局部署優(yōu)化，且覆蓋效率最高，收斂更快。但是由于本實(shí)驗(yàn)環(huán)境所有節(jié)點(diǎn)初始化部署的隨機(jī)性，算法執(zhí)行過(guò)程中并沒(méi)有實(shí)現(xiàn)百分之百的覆蓋率，算法中的參數(shù)設(shè)置對(duì)實(shí)驗(yàn)結(jié)果的影響，有待下一步繼續(xù)研究。

［1］Zhu C，Zheng C，Shu L，et al.A Survey on Coverage and Connectivity Issues in Wireless Sensor Networks［J］.Journal of Network and Computer Applications，2012，35（2）：619-632.DOI：10.1016/ j.jnca.2011.11.016

［2］Sung T，Yang C.Distributed Voronoi-Based Self-Redeployment for Coverage Enhancement in a Mobile Directional Sensor Network ［J］.International Journal of Distributed Sensor Networks，2013，2013：1-15.DOI：10.1155/2013/165498

［3］Ye G，Zhang B，Wen L，et al.Extended Virtual Force-Based Coverage Scheme for Heterogeneous Wireless Sensor Networks［C］//2014 14th International Conference on Control，Automation and Systems （ICCAS 2014）.KINTEX，Gyeonggi-do，Korea，2014：1560-1564

［4］Jiang H，Sun Y，Sun R，et al.Fuzzy-Logic-Based Energy Optimized Routing for Wireless Sensor Networks［J］.International Journal of Distributed Sensor Networks，2013，2013：1-8.DOI：10.1155/2013/216561

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

［6］Donmez M Y，Kosar R，Ersoy C.An Analytical Approach to the Deployment Quality of Surveillance Wireless Sensor Networks Considering the Effect of Jammers and Coverage Holes［J］.Computer Networks，2010，54（18）：3449-3466.DOI：10.1016/j.comnet. 2010.07.007

［7］孫彥景，林昌林，江海峰.一種能量高效的分布式非均勻分簇路由算法［J］.傳感技術(shù)學(xué)報(bào)，2015，28（8）：1194-1200.

［8］Al-Turjman F M，Hassanein H S，Ibnkahla M.Quantifying Connectivity in Wireless Sensor Networks with Grid-Based Deployments［J］.Journal of Network and Computer Applications，2013，36（1）：368-377.DOI：10.1016/j.jnca.2012.05.006

［9］江海峰，錢(qián)建生，孫彥景.WSN中基于虛擬靜電場(chǎng)的多Sink路由算法［J］.中國(guó)礦業(yè)大學(xué)學(xué)報(bào)，2011（02）：321-326.

［10］王雪，王晟，馬俊杰.無(wú)線傳感網(wǎng)絡(luò)布局的虛擬力導(dǎo)向微粒群優(yōu)化策略［J］.電子學(xué)報(bào)，2007，35（11）：2038-2042.

［11］張智威，孫子文.基于蟻群算法的無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)可信安全路由［J］.傳感技術(shù)學(xué)報(bào)，2016，29（2）：256-263.

［12］Lee H，Kim Y，Han Y，et al.Centroid-Based Movement Assisted Sensor Deployment Schemes in Wireless Sensor Networks［C］// 2009 IEEE 70thVehicular Technology Conference Fall（VTC 2009-Fall）.2009：1-5.DOI：10.1109/VETECF.2009.5379087

［13］馮秀芳，關(guān)志艷，全欣娜.基于虛擬力的異構(gòu)節(jié)點(diǎn)網(wǎng)絡(luò)覆蓋增強(qiáng)算法［J］.計(jì)算機(jī)工程，2009（5）：103-105.

［14］關(guān)志艷，耿巖.虛擬力導(dǎo)向群聚智能優(yōu)化的無(wú)線傳感器網(wǎng)絡(luò)覆蓋策略［J］.傳感器與微系統(tǒng)，2015（1）：40-42.

［15］Wang G，Cao G，La Porta T F.Movement-Assisted Sensor Deployment［J］.IEEE Transactions on Mobile Computing，2006，5（6）：640-653.

［16］S K S，M S.Coverage Rate Calculation in Wireless Sensor Networks［J］.Computing，2012，94（11）：833-856.

［17］A H，Matarimj，Sukhatmegs.An Incremental Self-Deployment Algorithm for Mobile Sensor Networks［J］.Autonomous Robots 2002，2002，13（1）：13-26.DOI：10.1023/A：1019625207705

［18］任孝平，蔡自興，任清雄.四種虛擬力模型在傳感器網(wǎng)絡(luò)覆蓋中的性能分析［J］.信息與控制，2010（4）：441-445.

王婷婷（1986-），女，江蘇連云港，博士研究生，主要研究無(wú)線傳感器網(wǎng)絡(luò)及智能優(yōu)化算法等；

孫彥景（1977-），男，山東滕州，博士，教授，博士生導(dǎo)師，主要研究無(wú)線傳感器網(wǎng)絡(luò)，信息物理系統(tǒng)及感知物聯(lián)網(wǎng)等，yjsun@cumt.edu.cn；

徐釗（1955-），男，江蘇宿遷，教授，博士生導(dǎo)師，主要研究數(shù)字礦山綜合傳輸網(wǎng)絡(luò)及無(wú)線通信系統(tǒng)等；

張曉光（1978-），女，遼寧昌圖，副教授，碩導(dǎo)，主要研究無(wú)線通信和數(shù)字信號(hào)處理。

Coverage Optimization Algorithm Based on Virtual Force for Heterogeneous Wireless Sensor Networks*

WANG Tingting1，SUN Yanjing1，2*，XU Zhao1，ZHANG Xiaoguang1
（1.School of Information and Electrical Engineering，China University of Mining and Technology，Xuzhou Jiangsu 221116，China；2.Coal Mine Electrical Engineering and Automation Laboratory in Jiangsu Province，Xuzhou Jiangsu 221008，China）

In heterogeneous wireless sensor networks with diversified mobility，the global optimization of coverage usually can’t be achieved because that the mobility of mobile sensor nodes will be constrained by the fixed ones.In order to solve this problem，we propose a Centroid-based Attractive Virtual Force Algorithm（CAVFA）inspired by computational geometry theory.The traditional Virtual Forces Algorithm（VFA）has been used to guide mobile nodes to move.And the Centroid-based algorithm（CBA）has potential to improve networks coverage in the whole interest of area.Also parameters including distance thresholds and priorities of virtual forces have been set to adjust the binding effect between fixed nodes and mobile ones.Simulation results are presented to demonstrate that the proposed CAVFA strategy has higher coverage rate and convergent speed than VFA and CBA strategies.

wireless sensor networks；heterogeneous network；network coverage；virtual force；optimization algorithm EEACC：6150P；7230

10.3969/j.issn.1004-1699.2016.08.022

TP393

A

1004-1699（2016）08-1253-07

項(xiàng)目來(lái)源：國(guó)家自然科學(xué)基金項(xiàng)目（51274202）；國(guó)家自然科學(xué)基金青年項(xiàng)目（51504255，51504214）；江蘇省自然科學(xué)基金項(xiàng)目（BK20130199，BK20131124）

2016-02-14修改日期：2016-04-05