劉 軍

(武警工程大學(xué) 信息工程系，陜西 西安 710086)

?

基于虛擬力算法的WMSNs覆蓋研究

劉 軍

(武警工程大學(xué) 信息工程系，陜西 西安 710086)

為了提高無線多媒體傳感器網(wǎng)絡(luò)(WMSNs)區(qū)域覆蓋率，在傳感器節(jié)點隨機部署后，通過調(diào)節(jié)傳感器節(jié)點的感知方向，使節(jié)點從感知重疊區(qū)域向覆蓋盲區(qū)轉(zhuǎn)動，提高網(wǎng)絡(luò)覆蓋率。針對現(xiàn)有算法中存在覆蓋效率和覆蓋率不能統(tǒng)一的問題，提出一種改進(jìn)的虛擬力覆蓋算法(VFARCR)，該算法利用傳感器節(jié)點感知扇形區(qū)域質(zhì)心點間的斥力調(diào)節(jié)感知方向，且通過傳感器節(jié)點間的覆蓋冗余度的決定方向調(diào)整的大小，虛擬力和覆蓋冗余度共同控制傳感器的轉(zhuǎn)動。仿真實驗表明:該算法提高了覆蓋效率和覆蓋效果，提高了虛擬力覆蓋算法的性能。

無線多媒體傳感器網(wǎng)絡(luò)； 覆蓋優(yōu)化； 虛擬力； 質(zhì)心

0 引 言

傳統(tǒng)的無線傳感器網(wǎng)絡(luò)(wireless sensor networks ,WSNs)只提供簡單的感知數(shù)據(jù)，如溫度、濕度、震動等[1～3]。隨著WSNs的應(yīng)用需求越來越廣泛以及相關(guān)技術(shù)不斷提高，無線多媒體傳感器網(wǎng)絡(luò)(wireless multimedia sensor networks，WMSNs)應(yīng)運而生，WMSNs能夠提供更復(fù)雜的數(shù)據(jù)，如語音、圖像和視頻等。所以，相比于傳統(tǒng)的WSNs，WMSNs更加全面地反映監(jiān)測環(huán)境的真實情況，能夠滿足更廣泛的需求[4～6]。

在無線多媒體節(jié)點的覆蓋優(yōu)化過程中，節(jié)點的方向調(diào)整規(guī)則直接關(guān)系到覆蓋效率。現(xiàn)有的研究中，節(jié)點的方向變化基本上是按固定步長調(diào)整[7]或連續(xù)性調(diào)整[8]，存在計算量較大、優(yōu)化時間較長，效率相對較低的問題。本文提出一種改進(jìn)的基于虛擬力覆蓋冗余算法(virtual force algorithm related with coverage redundancy,VFARCR)，解決優(yōu)化精度與優(yōu)化時間的矛盾。

1 WMSNs覆蓋問題研究

1.1 方向可調(diào)感知模型

改進(jìn)文獻(xiàn)[8]的感知模型，本文定義五元組表示多媒體傳感器的感知模型，即(s,V→i(t),α,Qi,R)，改進(jìn)的模型如圖1所示，其中，s為傳感器節(jié)點i的位置坐標(biāo)s(xi,yi)，節(jié)點隨機部署后，位置坐標(biāo)不會變動；V→i(t)為傳感器節(jié)點i在t時刻的感知方向；α為感知中心線距離扇形感知區(qū)域兩側(cè)邊界的夾角，2α為傳感器感知區(qū)域的夾角；Q為傳感器節(jié)點i的質(zhì)心位置坐標(biāo)Q(xi,yi),在優(yōu)化調(diào)整傳感器的方向的過程中，節(jié)點的質(zhì)心坐標(biāo)會隨著感知方向的變化而變化；R為傳感器節(jié)點的感知半徑。

圖1 方向可調(diào)的感知模型Fig 1 Adjustable directional sensing model

當(dāng)區(qū)域中的點pi被傳感器節(jié)點si覆蓋時，當(dāng)且僅當(dāng)滿足以下條件：

在該模型的WMSNs覆蓋優(yōu)化中，區(qū)域覆蓋率p、節(jié)點個數(shù)N、區(qū)域面積A、感知視角α、感知半徑R之間的關(guān)系滿足如下關(guān)系(具體推導(dǎo)過程見文獻(xiàn)[9])

(1)

2.2 問題描述

假設(shè)監(jiān)測區(qū)域的面積為A，傳感器節(jié)點的位置是均勻分布的，但感知方向V→i(t)是隨機的，假定區(qū)域中任意兩個節(jié)點不在同一坐標(biāo)位置。節(jié)點的最近感知半徑R和傳感區(qū)域視角2α都是相同的，即所部署的傳感器節(jié)點是同構(gòu)的。部署的節(jié)點個數(shù)為N，節(jié)點集表示為S(s1,s2,…,sN)。Ai(t)表示在t時刻傳感器節(jié)點在感知向量V→i(t)上區(qū)域的覆蓋面積，當(dāng)感知向量值為(V→1(t),V→2(t),…,V→s(t))時，區(qū)域的覆蓋率可表示為

(2)

所以，WMSNs覆蓋增強問題可以表述為：尋找一組解(V→1(t)，V→2(t),…,V→3(t)),使對于初始的(V→1(t),V→2(t),…,V→N(t))，有max{p(V→1(t),V→2(t),…,V→3(t))-p0}。

區(qū)域覆蓋率p的求解如下

(3)

式中 N為部署在區(qū)域中的傳感器節(jié)點數(shù)量。

2 VFARCR算法

2.1 虛擬力分析

改進(jìn)算法利用鄰居節(jié)點的斥力優(yōu)化節(jié)點感知方向，斥力的方向為節(jié)點感知區(qū)域質(zhì)心的連線方向，斥力大小與兩節(jié)點間覆蓋重疊區(qū)域大小成正比，與節(jié)點感知質(zhì)心間的距離的平方成反比,即

(4)

(5)

式中 m為節(jié)點i的鄰居節(jié)點個數(shù)。

節(jié)點的虛擬力分析為對節(jié)點B的受力分析，如圖2所示，A，B，C和D為傳感器節(jié)點，a，b，c和d為其質(zhì)心點，V→b(t)為節(jié)點B的感知方向，節(jié)點A對節(jié)點B的斥力為F→ab，節(jié)點C對B的斥力為F→cb，節(jié)點B所受合力為F→b，由于節(jié)點D和節(jié)點B沒有重疊區(qū)域，所以，D對B的斥力為0。

圖2 節(jié)點的虛擬力分析Fig 2 Virtual force analysis of nodes

2.2 覆蓋重疊區(qū)域面積的計算方法

在節(jié)點的感知扇形區(qū)域中建立p行q列的網(wǎng)格，如圖3所示。具體方法為將節(jié)點的感知視角2α均分為q等份，并將節(jié)點感知半徑R劃分為p等份，即將節(jié)點感知扇形區(qū)域劃分為p×q個網(wǎng)格，每個網(wǎng)格中心作為該網(wǎng)格的位置坐標(biāo)。

圖3 重疊區(qū)域面積計算Fig 3 Area computation of overlap region

建立網(wǎng)格后，需要判斷哪些網(wǎng)格被鄰居節(jié)點覆蓋。定義一個參數(shù)Cgijpq，當(dāng)節(jié)點i中的網(wǎng)格被其鄰居節(jié)點j覆蓋，則Cgijpq=1;否則,Cgijpq=0。所以，Mij可以通過下式計算

(6)

節(jié)點i的覆蓋冗余度可以定義為

(7)

式中 m為節(jié)點i的鄰居節(jié)點個數(shù)。

2.3 節(jié)點感知方向調(diào)整規(guī)則

傳感器節(jié)點感知方向的調(diào)整需要考慮兩個問題，一是在虛擬力的作用下，往哪個方向調(diào)整；二是方向變化的大小問題，即如何規(guī)定方向變化大小的依據(jù)。

明確節(jié)點方向調(diào)整的問題后，需要進(jìn)一步考慮節(jié)點在該方向上是如何調(diào)整的。本文將覆蓋冗余度作為方向變化大小Δθ的依據(jù)。文獻(xiàn)[8]提出采用固定的Δθ，并未考慮結(jié)合覆蓋重疊面積與Δθ的關(guān)系，根據(jù)該文獻(xiàn)的研究，對Δθ作以下改進(jìn)

(8)

式中 Rcagi為節(jié)點i的覆蓋冗余度，α為感知中心線距離扇形感知區(qū)域兩側(cè)邊界的夾角。當(dāng)Rcagi很小時，在實際操作中很難實現(xiàn)，所以，設(shè)定一個閾值η來實現(xiàn)角度調(diào)整的可行性，當(dāng)Rcagi≥η時，角度進(jìn)行調(diào)整。

3 仿真實驗

該仿真實驗在Matlab R2008b上進(jìn)行。參數(shù)設(shè)置如下：監(jiān)測區(qū)域為500 m×500 m，節(jié)點半徑R=60 m，感知視角2α=60°，虛擬系數(shù)k=1，節(jié)點扇形感知區(qū)域的劃分為10 m×10 m，覆蓋冗余度閾值η=0.01。若預(yù)期的覆蓋率為85 %，根據(jù)公式(1)以及所設(shè)置的相關(guān)參數(shù)可求得在該區(qū)域中需要的最少節(jié)點個數(shù)N為

圖4為Δθ=1°,Δθ=20°以及Δθ為變化取值時的仿真結(jié)果對比。從仿真結(jié)果可以看出:當(dāng)Δθ變化取值時，在算法運行23次時，算法就開始收斂且覆蓋率達(dá)到了92.4 %，比Δθ=1°時的91.3 %提高了1.1 %，與Δθ=20°時的覆蓋性能相比較，當(dāng)Δθ變化取值時，在算法迭代6次就達(dá)到了Δθ=20°的最大覆蓋率，且沒有出現(xiàn)振蕩的情況，穩(wěn)定性更好。所以，當(dāng)Δθ變化時，既能達(dá)到較理想的覆蓋效果，又能提高算法的收斂速度，使算法以較快的速度達(dá)到較高的覆蓋率。

圖4 固定Δθ和變化Δθ的算法收斂性的比較Fig 4 Comparison of algorithm convergence between fixed Δθ and changed Δθ

將本文VFARCR算法與文獻(xiàn)[7]提出的PFCEA算法和文獻(xiàn)[10]所提出的VCFCEA算法覆蓋性能進(jìn)行比較。仿真結(jié)果如圖5所示。三種算法最終的覆蓋率都相差不大，均在91 %左右。但VCFCEA算法的覆蓋效率最低，覆蓋率增長率最緩慢，最少需要迭代25次才能達(dá)到最大的覆蓋率；PFCEA算法優(yōu)化效率比VCFCEA算法更高，在算法迭代30次基本達(dá)到最大的覆蓋率，但算法會出現(xiàn)震蕩的現(xiàn)象；本文VFARCR算法運行21次時開始收斂，基本達(dá)到最大覆蓋率，且不出現(xiàn)震蕩。這主要是該算法解決了虛擬力與調(diào)整角度大小相互牽制的矛盾，將覆蓋冗余度與調(diào)整方向的大小關(guān)聯(lián)起來，解決了采用固定步長算法難以收斂的問題。

圖5 算法性能比較Fig 5 Comparison of algorithm performance

4 結(jié) 論

針對WMSNs覆蓋優(yōu)化過程中節(jié)點轉(zhuǎn)動角度調(diào)整策略存在的不足，本文提出一種改進(jìn)的虛擬力算法，改進(jìn)算法有兩點創(chuàng)新：一是將節(jié)點間的虛擬力與它們之間的重疊塊面積關(guān)聯(lián)起來，使虛擬力的大小隨著重疊塊的大小變化，優(yōu)化了虛擬力的構(gòu)造；二是將節(jié)點轉(zhuǎn)動角度的大小與覆蓋冗余度關(guān)聯(lián)起來，解決了固定轉(zhuǎn)動角度中覆蓋效果與覆蓋效率難以統(tǒng)一的矛盾。仿真實驗表明:改進(jìn)算法具有有效性，且與同類算法相比較，具有明顯的優(yōu)越性。

[1] Akyildiz L E,Su W L,Sankamsubramanizm Y,et al.A survey on sensor networks[J].IEEE Communications Magazine,2002,40(8):102-114.

[2] Liu B，Towsley D．A study of the coverage of large-scale sensor networks[C]∥IEEE International Conference on Mobile Ad-Hoc and Sensor Systems，MASS’04，2004:475-483．

[3] 趙 旭,雷 霖,代傳龍.無線傳感器網(wǎng)絡(luò)的覆蓋控制[J].傳感器與微系統(tǒng),2007,26(8):62-66.

[4] Akyildiz I F,Vuran M C.Wireless multimedia sensor network-s[M].New York:John Wiley &Sons Ltd,2008:49-59.

[5] Almalkawi I T.Wireless multimedia sensor networks:Current trends and future directions[J].Sensors,2010,10(7):6662-6717.

[6] 王曉晨,馮秀芳,辛 英.WMSNs中目標(biāo)覆蓋算法與通信策略研究[J].傳感器與微系統(tǒng),2013,32(8):32-34.

[7] 何 璇,郝 群,宋 勇.一種移動無線視頻傳感器節(jié)點的覆蓋算法[J].傳感技術(shù)學(xué)報,2009,22(8):1163-1168.

[8] Tao D,Ma H D,Liu L.A virtual potential field based coverage-enhancing algorithm for directional sensor networks[J].Journal of Software,2007,18(5):1152-1163.

[9] 肖 甫,王汝傳,葉曉國,等.基于改進(jìn)勢場的有向傳感器網(wǎng)絡(luò)路徑覆蓋增強算法[J].計算機研究與發(fā)展，2009,46(12):2126-2133.

[10] 張 璐.無線多媒體傳感器網(wǎng)絡(luò)覆蓋技術(shù)研究[D].西安：西安電子科技大學(xué),2014.

Research on WMSNs coverage based on virtual force algorithm

LIU Jun

(Department of Information Engineering Engineering University of CAPF,Xi’an 710086,China)

In order to improve area coverage rate of wireless multimedia sensor networks(WMSNs),after sensor nodes are randomly deployed,by regulating sensing direction of sensor nodes,enable node rotates from perception overlapping areas to cover blind areas,so as to enhance network coverage rate.Aiming at problem of existing algorithms that coverage efficiency and covering rate can’t be unified,propose an improved virtual force algorithm related with coverage redundancy(VFARCR),the algorithm using sensor nodes to sense repulsion between the centroid point of fan-shaped area,adjust sensing direction,and size of direction adjusting is determined by coverage redundancy,virtual force and coverage redundancy control rotating of sensor collectively.Simulation results show that the algorithm improves coverage efficiency and coverage effect and improve performance of virtual force covering algorithm.

wireless multimedia sensor networks(WMSNs);coverage optimization;virtual force;centroid

10.13873/J.1000—9787(2016)11—0074—03

2015—12—03

TP 393

A

1000—9787(2016)11—0074—03

劉 軍(1963-)，男，北京人，碩士，教授，研究生導(dǎo)師，從事無線數(shù)據(jù)通信、電子技術(shù)應(yīng)用、戰(zhàn)場態(tài)勢感知方面研究工作。