無(wú)線傳感網(wǎng)中基于特征點(diǎn)集的虛擬力覆蓋優(yōu)化

侯義飛 楊勇

摘要：無(wú)線傳感網(wǎng)的覆蓋率通常利用覆蓋區(qū)域中稠密的網(wǎng)格點(diǎn)來(lái)近似計(jì)算，導(dǎo)致了計(jì)算量龐大。因此，提出了一種基于特征點(diǎn)集的無(wú)線傳感網(wǎng)虛擬力覆蓋優(yōu)化算法。該算法引入了特征點(diǎn)集的概念，并結(jié)合虛擬力算法，將網(wǎng)絡(luò)節(jié)點(diǎn)對(duì)區(qū)域網(wǎng)格點(diǎn)的覆蓋計(jì)算轉(zhuǎn)化為對(duì)若干特征點(diǎn)的覆蓋計(jì)算，利用有限的特征點(diǎn)的覆蓋情況去描述整個(gè)網(wǎng)絡(luò)，從而達(dá)到減小計(jì)算量的目的。實(shí)驗(yàn)結(jié)果表明：與傳統(tǒng)基于網(wǎng)格點(diǎn)的虛擬力算法相比，在滿足區(qū)域覆蓋要求的同時(shí)，算法執(zhí)行效率明顯提升，運(yùn)行時(shí)間縮短了56.55%。

關(guān)鍵詞：無(wú)線傳感網(wǎng);無(wú)線傳感網(wǎng);特征點(diǎn)集;虛擬力算法

中圖分類號(hào)：TP393文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1009-3044（2020）16-0003-05

開(kāi)放科學(xué)（資源服務(wù)）標(biāo)識(shí)碼（OSID）：

Abstract： The coverage of wireless sensor networks is usually approximated by the use of dense grid points in the coverage area， resulting in a lot of computation. Therefore， a virtual force coverage optimization algorithm for wireless sensor networks based on feature point sets is proposed. The algorithm introduces the concept of feature point set， and combines the virtual force algorithm to transform the coverage calculation of the network nodes to the regional grid point into the coverage calculation of several feature points， which uses the coverage of the limited feature points to describe the whole network， so as to reduce the calculation amount. The experimental results show that compared with the traditional grid-based virtual force algorithm， while meeting the regional coverage requirements， the algorithm execution efficiency is significantly improved， and the running time is shortened by 56.55%.

Key words： Wireless sensor network; Network coverage; Feature point set; Virtual force algorithm

無(wú)線傳感器網(wǎng)絡(luò)[1]（Wireless Sensor Networks，WSN）是大量具有傳感、數(shù)據(jù)處理、無(wú)線通信和計(jì)算能力的低成本、低功耗的微型傳感器節(jié)點(diǎn)通過(guò)自組織方式形成的，廣泛應(yīng)用于大型農(nóng)場(chǎng)的安全監(jiān)測(cè)，環(huán)境監(jiān)測(cè)和預(yù)報(bào)，大型車間和倉(cāng)庫(kù)管理等方面。然而，在對(duì)大規(guī)模監(jiān)控區(qū)域進(jìn)行節(jié)點(diǎn)部署時(shí)，通常采用隨機(jī)部署的方式，容易造成區(qū)域內(nèi)節(jié)點(diǎn)過(guò)密或過(guò)疏[2]，進(jìn)而導(dǎo)致區(qū)域存在覆蓋冗余和監(jiān)測(cè)盲點(diǎn)。因此，網(wǎng)絡(luò)覆蓋問(wèn)題作為WSN中的基本問(wèn)題，有著重要的研究意義。

目前，有關(guān)覆蓋問(wèn)題的許多成果大多是基于布爾感知模型，如文獻(xiàn)[3-4]。布爾感知模型是一種理想化的模型，但傳感器在實(shí)際監(jiān)測(cè)目標(biāo)時(shí)，監(jiān)測(cè)范圍與傳感和通信半徑有一定的概率關(guān)系，因此，選用基于概率感知模型更符合實(shí)際情況，文獻(xiàn)[5]在概率感知模型的基礎(chǔ)上提出了一種分布式k重覆蓋算法。類似地，文獻(xiàn)[6]提出一種基于改進(jìn)虛擬力算法概率感知模型的部署方法。在選定感知模型后，學(xué)者對(duì)覆蓋優(yōu)化算法進(jìn)行了深入的研究，覆蓋優(yōu)化算法有虛擬力算法，人工勢(shì)場(chǎng)法，群體智能算法等。群體智能算法包括粒子群算法[7-9]，遺傳算法等。但是群體智能算法依靠群體合作進(jìn)行尋優(yōu)，存在計(jì)算量較大的缺點(diǎn)。而且若節(jié)點(diǎn)分布不均，監(jiān)測(cè)區(qū)域?qū)⒋嬖诟采w冗余和監(jiān)測(cè)盲點(diǎn)，不僅影響數(shù)據(jù)傳輸?shù)目煽啃裕覍?dǎo)致不必要的能量消耗。在移動(dòng)傳感器節(jié)點(diǎn)部署算法中，虛擬力算法 [10]只依據(jù)周圍臨近節(jié)點(diǎn)分布情況動(dòng)態(tài)地調(diào)整自身位置，使整個(gè)網(wǎng)絡(luò)覆蓋趨向均勻。因此，許多學(xué)者對(duì)虛擬力優(yōu)化算法進(jìn)行了研究，使區(qū)域中節(jié)點(diǎn)分布均勻，提高網(wǎng)絡(luò)區(qū)域的覆蓋率。文獻(xiàn)[11]基于虛擬力算法最大化區(qū)域的覆蓋率。文獻(xiàn)[12]在力函數(shù)上加約束條件，提出了一種分布式虛擬力算法。在節(jié)能方面，文獻(xiàn)[13]推導(dǎo)建立了多目標(biāo)非線性規(guī)劃數(shù)學(xué)模型，提出一種節(jié)能的虛擬力優(yōu)化算法。然而，虛擬力算法部署傳感器節(jié)點(diǎn)時(shí)，容易陷入局部受力平衡，使節(jié)點(diǎn)來(lái)回移動(dòng)，文獻(xiàn)[14]提出一種虛擬力導(dǎo)向微粒群的有向覆蓋增強(qiáng)策略，加快收斂到全局最優(yōu)解。此外，一些新興的智能算法，如人工蜂群算法[15]也已經(jīng)應(yīng)用于覆蓋問(wèn)題當(dāng)中。

針對(duì)傳統(tǒng)基于網(wǎng)格點(diǎn)虛擬力算法求解網(wǎng)絡(luò)覆蓋率受網(wǎng)格點(diǎn)的精度影響，導(dǎo)致計(jì)算量大的缺點(diǎn)。在特征點(diǎn)集概念的基礎(chǔ)上，將特征點(diǎn)集與傳統(tǒng)的虛擬力算法結(jié)合，將傳統(tǒng)的區(qū)域覆蓋問(wèn)題轉(zhuǎn)化成了對(duì)特征點(diǎn)集優(yōu)化覆蓋問(wèn)題，通過(guò)求解傳感器對(duì)特征點(diǎn)的覆蓋率，等價(jià)分析整個(gè)區(qū)域的覆蓋。通過(guò)實(shí)驗(yàn)證明了文中算法相較于傳統(tǒng)虛擬力算法降低了復(fù)雜度，減少了運(yùn)行時(shí)間和計(jì)算量。這是一種比較新穎的結(jié)合方式，并且能夠較好地滿足覆蓋要求。

1網(wǎng)絡(luò)覆蓋模型建立

為了便于研究網(wǎng)絡(luò)覆蓋首先做以下假設(shè)：

（1）無(wú)線傳感器網(wǎng)絡(luò)中的傳感器節(jié)點(diǎn)全部是可以自由移動(dòng)的。（2）移動(dòng)節(jié)點(diǎn)的能源充足，能夠完成位置的更新。（3）傳感器類型全部是同構(gòu)類型，通信半徑Rc是感知半徑Rs的2倍。

無(wú)線傳感器網(wǎng)絡(luò)部署模型中最常用的模型是布爾感知模型，也叫0-1圓盤模型，它是一種理想化的覆蓋模型，但傳感器在實(shí)際監(jiān)測(cè)目標(biāo)時(shí)，傳感器的感知能力隨著傳感器節(jié)點(diǎn)與目標(biāo)距離的增大而逐漸減小甚至無(wú)法感知，概率感知模型更符合實(shí)際監(jiān)測(cè)環(huán)境，因此選用概率感知模型。

首先假設(shè)傳感器節(jié)點(diǎn)s的位置為（x，y），目標(biāo)物體m的位置（xm ，ym），那么它們之間的距離d（s，m）則可以表示為：

2基于特征點(diǎn)集虛擬力的覆蓋優(yōu)化

在介紹特征點(diǎn)集之前，首先介紹點(diǎn)覆蓋問(wèn)題。通過(guò)分析點(diǎn)覆蓋問(wèn)題，可以擴(kuò)展到研究整個(gè)區(qū)域覆蓋問(wèn)題。

2.1特征點(diǎn)的定義與選取

傳統(tǒng)方法求解網(wǎng)絡(luò)覆蓋率比較難，因?yàn)閭鞲衅鞴?jié)點(diǎn)之間有重疊且重疊的面積不規(guī)則。因此，一些學(xué)者就提出基于網(wǎng)格點(diǎn)虛擬力算法[19-20]求解網(wǎng)絡(luò)的覆蓋率，此方法求解覆蓋率，會(huì)受到網(wǎng)格點(diǎn)大小的影響，網(wǎng)格點(diǎn)越小，算法復(fù)雜度越高，算法的運(yùn)行時(shí)間就越長(zhǎng)。網(wǎng)格點(diǎn)選取越大，則精度就會(huì)不高。在特征點(diǎn)集的基礎(chǔ)上，通過(guò)計(jì)算傳感器節(jié)點(diǎn)對(duì)特征點(diǎn)的聯(lián)合覆蓋率，進(jìn)而求出整個(gè)區(qū)域的網(wǎng)絡(luò)覆蓋率。將傳統(tǒng)的求區(qū)域覆蓋率轉(zhuǎn)化為對(duì)特征點(diǎn)集的覆蓋率，降低了算法的復(fù)雜度，縮短了算法的運(yùn)行時(shí)間。因此，本文在特征點(diǎn)、特征點(diǎn)集的概念基礎(chǔ)上來(lái)求解無(wú)線傳感器網(wǎng)絡(luò)中的覆蓋率。

通過(guò)式（6）可以得出，區(qū)域內(nèi)任意一點(diǎn)都至少被一個(gè)特征點(diǎn)所覆蓋，能夠求出每個(gè)特征點(diǎn)的聯(lián)合覆蓋率和其中的最小值。

2.2 傳統(tǒng)虛擬力算法模型

虛擬力算法[21]（Virtual Force Algorithm，VFA）是把移動(dòng)傳感器節(jié)點(diǎn)看成是帶電粒子，節(jié)點(diǎn)間有萬(wàn)有引力，也有斥力的作用。當(dāng)傳感器節(jié)點(diǎn)間的距離小于某一值時(shí)，傳感器節(jié)點(diǎn)間表現(xiàn)為斥力，當(dāng)傳感器節(jié)點(diǎn)間的距離大于某一值時(shí)，傳感器節(jié)點(diǎn)間表現(xiàn)為引力。一個(gè)節(jié)點(diǎn)所受到的虛擬力是區(qū)域內(nèi)所有傳感器節(jié)點(diǎn)所施加的虛擬力的合力，合力的大小和方向決定節(jié)點(diǎn)的移動(dòng)距離和方向，節(jié)點(diǎn)在合力的作用下移動(dòng)到合適的位置，使區(qū)域內(nèi)的節(jié)點(diǎn)分布比較均勻，進(jìn)而完成良好的部署。

2.3 基于特征點(diǎn)集虛擬力覆蓋優(yōu)化

傳統(tǒng)的虛擬力算法可以使傳感器節(jié)點(diǎn)更快地從密集區(qū)域擴(kuò)散開(kāi)來(lái)，且每個(gè)節(jié)點(diǎn)移動(dòng)的距離更短，節(jié)省了節(jié)點(diǎn)的能量并延長(zhǎng)了網(wǎng)絡(luò)的壽命。然而，傳感器節(jié)點(diǎn)可能因受力平衡而產(chǎn)生局部來(lái)回移動(dòng)，使得傳感器節(jié)點(diǎn)沒(méi)有移動(dòng)到合適的位置。還有，節(jié)點(diǎn)在移動(dòng)時(shí)存在能耗差異，使得節(jié)點(diǎn)能耗不均勻，算法復(fù)雜度更高，使算法收斂速度下降。

本文中的算法是基于網(wǎng)格點(diǎn)的虛擬力算法，此算法求解網(wǎng)絡(luò)覆蓋率，精確度取決于選取網(wǎng)格的大小，網(wǎng)格選取的越小，計(jì)算復(fù)雜度就越大，拓展性也越差。

針對(duì)以上問(wèn)題，通過(guò)研究?jī)牲c(diǎn)間覆蓋率的關(guān)系，將特征點(diǎn)集的概念與虛擬力算法結(jié)合起來(lái)，把傳統(tǒng)的區(qū)域覆蓋轉(zhuǎn)化為對(duì)特征點(diǎn)集的覆蓋優(yōu)化問(wèn)題，利用有限的特征點(diǎn)的覆蓋情況去描述整個(gè)網(wǎng)絡(luò)，并且能夠保證區(qū)域內(nèi)的覆蓋要求。同時(shí)，降低了算法的復(fù)雜度，加快收斂速度，減少計(jì)算量。

算法流程如圖4所示：

3仿真實(shí)驗(yàn)

3.1 仿真設(shè)置

在100m×100m的區(qū)域大小內(nèi)，傳感器的個(gè)數(shù)為N=25。傳感器感知半徑Rs=15 m，傳感器參數(shù)Re=1/3Rs，α1=β1=β2=1，α2=0，迭代次數(shù)為100。傳感器節(jié)點(diǎn)在網(wǎng)格點(diǎn)作用下移動(dòng)的最大步長(zhǎng)max step=2.5 m，傳感器在傳感器節(jié)點(diǎn)的作用下移動(dòng)的最大距離max sensor=4.5 m。概率閾值為0.7，由推論1[17]可得 MFPD≤10.42，所以MFPD取10。

3.2 實(shí)驗(yàn)結(jié)果與分析

對(duì)所提的算法進(jìn)行仿真分析，圖5是傳感器節(jié)點(diǎn)數(shù)為25初始化的位置分布圖。在進(jìn)行100次迭代之后，從圖6可以看出最終可以滿足區(qū)域覆蓋的要求。圖7是迭代100次后的覆蓋率變化曲線。

加入特征點(diǎn)集的目的是把傳感器對(duì)區(qū)域的覆蓋轉(zhuǎn)化為對(duì)特征點(diǎn)的覆蓋，可以證明每個(gè)被覆蓋的傳感器節(jié)點(diǎn)的覆蓋率都大于或等于其周圍的覆蓋率。因此，通過(guò)研究分析求解傳感器對(duì)特征點(diǎn)的覆蓋率，可以清楚整個(gè)區(qū)域的覆蓋情況。

圖8是區(qū)域內(nèi)傳感器節(jié)點(diǎn)對(duì)每個(gè)特征點(diǎn)進(jìn)行覆蓋的覆蓋率，最小覆蓋率的大小是0.743。從圖中可以看出，每個(gè)傳感器對(duì)區(qū)域內(nèi)的特征點(diǎn)集的覆蓋效果好，覆蓋率高。

另外，為了防止傳感器節(jié)點(diǎn)的個(gè)數(shù)對(duì)實(shí)驗(yàn)有影響，選取了三種不同傳感器節(jié)點(diǎn)個(gè)數(shù)得到了如圖9所示的網(wǎng)絡(luò)覆蓋圖，結(jié)果表明選取傳感器節(jié)點(diǎn)N=25適合算法的要求，既能滿足區(qū)域的覆蓋要求，又能不造成大量的覆蓋冗余。

為了避免實(shí)驗(yàn)的隨機(jī)性對(duì)結(jié)果造成的誤差，選取10次獨(dú)立實(shí)驗(yàn)，求取最小覆蓋率和程序運(yùn)行時(shí)間的均值和標(biāo)準(zhǔn)差，從圖10的運(yùn)行時(shí)間對(duì)比圖可以得出加入特征點(diǎn)集后算法的運(yùn)行時(shí)間明顯加快。另外，基于網(wǎng)格點(diǎn)虛擬力運(yùn)行10次的總時(shí)間為56.407s，加入特征點(diǎn)集的算法運(yùn)行10次的總時(shí)間為31.9024s，運(yùn)行時(shí)間提高了56.55%。

4 結(jié)論

本文在基于特征點(diǎn)集概念的基礎(chǔ)上，將特征點(diǎn)集與虛擬力算法結(jié)合在一起，將傳統(tǒng)區(qū)域覆蓋問(wèn)題轉(zhuǎn)化為對(duì)特征點(diǎn)集的覆蓋，也是求解覆蓋率的一種新的方法。實(shí)驗(yàn)仿真結(jié)果表明，本文所提出的方法相比較傳統(tǒng)的網(wǎng)格點(diǎn)求覆蓋率能明顯減少算法的運(yùn)行時(shí)間，能夠較快地使網(wǎng)絡(luò)達(dá)到穩(wěn)定狀態(tài)，并且具有較高的覆蓋率。今后將進(jìn)一步研究特征點(diǎn)集的選取對(duì)覆蓋率的影響。

參考文獻(xiàn)：

[1] 陳宇晨. 基于AUV的無(wú)線傳感器網(wǎng)絡(luò)覆蓋研究及應(yīng)用[D]. 南京： 南京郵電大學(xué)， 2014.

[2] 邵晶. 基于地理位置的WSN拓?fù)淇刂蒲芯縖D]. 成都： 電子科技大學(xué)， 2010.

[3] Hefeeda M，Bagheri M.Randomized k-coverage algorithms for dense sensor networks[C]//IEEE INFOCOM 2007 - 26th IEEE International Conference on Computer Communications，May 6-12， 2007. Anchorage， AK， USA. IEEE， 2007： 2376-2380.

[4] 劉明，曹建農(nóng)，鄭源，等.無(wú)線傳感器網(wǎng)絡(luò)多重覆蓋問(wèn)題分析[J].軟件學(xué)報(bào)，2007，18（1）：127-136

[5] 蔣麗萍，王良民，熊書明，等.基于感知概率的無(wú)線傳感器網(wǎng)絡(luò)k重覆蓋算法[J].計(jì)算機(jī)應(yīng)用研究，2009，26（9）：3484-3486，3489.

[6] 李強(qiáng)懿，馬冬前，張聚偉.基于感知概率的無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)部署算法[J].計(jì)算機(jī)測(cè)量與控制，2014，22（2）：643-645.

[7] Wan Ismail W Z，Abd Manaf S.Study on coverage in Wireless Sensor Network using grid based strategy and Particle Swarm Optimization[C]//2010 IEEE Asia Pacific Conference on Circuits and Systems，December 6-9， 2010. Kuala Lumpur， Malaysia. IEEE， 2010： 1175-1178.

[8] Kennedy J，Eberhart R.Particle swarm optimization[C]//Proceedings of ICNN'95 - International Conference on Neural Networks，Perth， WA， Australia. IEEE， 10.1109/icnn.1995.488968.

[9] 謝佳華，劉軍.無(wú)線網(wǎng)絡(luò)通信覆蓋優(yōu)化仿真研究[J].計(jì)算機(jī)仿真，2015，32（6）：271-275.

[10] 張濤，余翔宇，藍(lán)俊健，等.改進(jìn)的無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)虛擬力部署方法[J].計(jì)算機(jī)應(yīng)用研究，2015，32（11）：3356-3358，3363.

[11] Zou Y，Chakrabarty K.Sensor deployment and target localization based on virtual forces[J].Proceedings - IEEE INFOCOM，2003，2（1）：1293-1303.

[12] Tsai R G，Kuo H C，Wang H L，et al.Target coverage QoS control with multiple sensing units in wireless heterogeneous sensor networks[C]//2012 Sixth International Conference on Sensing Technology （ICST），December 18-21， 2012. Kolkata. IEEE， 2012： 428-433.

[13] 田一鳴，陸陽(yáng)，魏臻，等.無(wú)線傳感器網(wǎng)絡(luò)虛擬力覆蓋控制及節(jié)能優(yōu)化研究[J].電子測(cè)量與儀器學(xué)報(bào)，2009，23（11）：65-71.

[14] 范興剛，王恒，張兆娟，等.一種基于虛擬力導(dǎo)向微粒群的有向傳感器網(wǎng)絡(luò)覆蓋增強(qiáng)策略[J].傳感技術(shù)學(xué)報(bào)，2015，28（11）：1720-1726.

[15] 文政穎，翟紅生.基于混沌人工蜂群算法的無(wú)線傳感器網(wǎng)絡(luò)覆蓋優(yōu)化[J].計(jì)算機(jī)測(cè)量與控制，2014，22（5）：1609-1612.

[16] 劉維亭，范洲遠(yuǎn).基于混沌粒子群算法的無(wú)線傳感器網(wǎng)絡(luò)覆蓋優(yōu)化[J].計(jì)算機(jī)應(yīng)用，2011，31（2）：338-341.

[17] 丁旭，吳曉蓓，黃成.基于改進(jìn)粒子群算法和特征點(diǎn)集的無(wú)線傳感器網(wǎng)絡(luò)覆蓋問(wèn)題研究[J].電子學(xué)報(bào)，2016，44（4）：967-973.

[18] Yang Q Q，He S B，Li J K，et al.Energy-efficient probabilistic full coverage in wireless sensor networks[C]//2012 IEEE Global Communications Conference （GLOBECOM），December 3-7， 2012. Anaheim， CA， USA. IEEE， 2012： 591-596.

[19] LI Hui， ZHANG Xiao-guang， et al. A hybrid deployment algorithm based on clonal selection and artificial physics optimization for wireless sensor network[J]. Information Technology Journal， 2013， 12（5）： 917-925.

[20] Shen X F，Chen J M，Sun Y X.Grid scan：a simple and effective approach for coverage issue in wireless sensor networks[C]//2006 IEEE International Conference on Communications，June 11-15， 2006. Istanbul. IEEE， 2006： 3480-3484.

[21] Wang X B，Han S H，Wu Y B，et al.Coverage and energy consumption control in mobile heterogeneous wireless sensor networks[J].IEEE Transactions on Automatic Control， 2013，58（4）：975-988.

[22] 李賢，何啟麗，唐秋玲，等.一種基于網(wǎng)格劃分的虛擬力部署算法的研究[J].廣西大學(xué)學(xué)報(bào)（自然科學(xué)版），2012，37（6）：1164-1169.

【通聯(lián)編輯：梁書】