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

侯義飛 楊勇

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

關鍵詞：無線傳感網;無線傳感網;特征點集;虛擬力算法

中圖分類號：TP393文獻標識碼：A

文章編號：1009-3044（2020）16-0003-05

開放科學（資源服務）標識碼（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

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

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

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

1網絡覆蓋模型建立

為了便于研究網絡覆蓋首先做以下假設：

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

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

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

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

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

2.1特征點的定義與選取

傳統(tǒng)方法求解網絡覆蓋率比較難，因為傳感器節(jié)點之間有重疊且重疊的面積不規(guī)則。因此，一些學者就提出基于網格點虛擬力算法[19-20]求解網絡的覆蓋率，此方法求解覆蓋率，會受到網格點大小的影響，網格點越小，算法復雜度越高，算法的運行時間就越長。網格點選取越大，則精度就會不高。在特征點集的基礎上，通過計算傳感器節(jié)點對特征點的聯合覆蓋率，進而求出整個區(qū)域的網絡覆蓋率。將傳統(tǒng)的求區(qū)域覆蓋率轉化為對特征點集的覆蓋率，降低了算法的復雜度，縮短了算法的運行時間。因此，本文在特征點、特征點集的概念基礎上來求解無線傳感器網絡中的覆蓋率。

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

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

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

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

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

本文中的算法是基于網格點的虛擬力算法，此算法求解網絡覆蓋率，精確度取決于選取網格的大小，網格選取的越小，計算復雜度就越大，拓展性也越差。

針對以上問題，通過研究兩點間覆蓋率的關系，將特征點集的概念與虛擬力算法結合起來，把傳統(tǒng)的區(qū)域覆蓋轉化為對特征點集的覆蓋優(yōu)化問題，利用有限的特征點的覆蓋情況去描述整個網絡，并且能夠保證區(qū)域內的覆蓋要求。同時，降低了算法的復雜度，加快收斂速度，減少計算量。

算法流程如圖4所示：

3仿真實驗

3.1 仿真設置

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

3.2 實驗結果與分析

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

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

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

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

為了避免實驗的隨機性對結果造成的誤差，選取10次獨立實驗，求取最小覆蓋率和程序運行時間的均值和標準差，從圖10的運行時間對比圖可以得出加入特征點集后算法的運行時間明顯加快。另外，基于網格點虛擬力運行10次的總時間為56.407s，加入特征點集的算法運行10次的總時間為31.9024s，運行時間提高了56.55%。

4 結論

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

參考文獻：

[1] 陳宇晨. 基于AUV的無線傳感器網絡覆蓋研究及應用[D]. 南京： 南京郵電大學， 2014.

[2] 邵晶. 基于地理位置的WSN拓撲控制研究[D]. 成都： 電子科技大學， 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] 劉明，曹建農，鄭源，等.無線傳感器網絡多重覆蓋問題分析[J].軟件學報，2007，18（1）：127-136

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

[6] 李強懿，馬冬前，張聚偉.基于感知概率的無線傳感器網絡節(jié)點部署算法[J].計算機測量與控制，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] 謝佳華，劉軍.無線網絡通信覆蓋優(yōu)化仿真研究[J].計算機仿真，2015，32（6）：271-275.

[10] 張濤，余翔宇，藍俊健，等.改進的無線傳感器網絡節(jié)點虛擬力部署方法[J].計算機應用研究，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] 田一鳴，陸陽，魏臻，等.無線傳感器網絡虛擬力覆蓋控制及節(jié)能優(yōu)化研究[J].電子測量與儀器學報，2009，23（11）：65-71.

[14] 范興剛，王恒，張兆娟，等.一種基于虛擬力導向微粒群的有向傳感器網絡覆蓋增強策略[J].傳感技術學報，2015，28（11）：1720-1726.

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

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

[17] 丁旭，吳曉蓓，黃成.基于改進粒子群算法和特征點集的無線傳感器網絡覆蓋問題研究[J].電子學報，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] 李賢，何啟麗，唐秋玲，等.一種基于網格劃分的虛擬力部署算法的研究[J].廣西大學學報（自然科學版），2012，37（6）：1164-1169.

【通聯編輯：梁書】