劉 軍

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

?

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

劉 軍

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

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

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

0 引 言

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

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

1 WMSNs覆蓋問題研究

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

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

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

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

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

(1)

2.2 問題描述

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

(2)

所以，WMSNs覆蓋增強(qiáng)問題可以表述為：尋找一組解(V→1(t)，V→2(t),…,V→3(t)),使對(duì)于初始的(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é)點(diǎn)數(shù)量。

2 VFARCR算法

2.1 虛擬力分析

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

(4)

(5)

式中 m為節(jié)點(diǎn)i的鄰居節(jié)點(diǎn)個(gè)數(shù)。

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

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

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

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

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

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

(6)

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

(7)

式中 m為節(jié)點(diǎn)i的鄰居節(jié)點(diǎn)個(gè)數(shù)。

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

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

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

(8)

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

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

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

圖4為Δθ=1°,Δθ=20°以及Δθ為變化取值時(shí)的仿真結(jié)果對(duì)比。從仿真結(jié)果可以看出:當(dāng)Δθ變化取值時(shí)，在算法運(yùn)行23次時(shí)，算法就開始收斂且覆蓋率達(dá)到了92.4 %，比Δθ=1°時(shí)的91.3 %提高了1.1 %，與Δθ=20°時(shí)的覆蓋性能相比較，當(dāng)Δθ變化取值時(shí)，在算法迭代6次就達(dá)到了Δθ=20°的最大覆蓋率，且沒有出現(xiàn)振蕩的情況，穩(wěn)定性更好。所以，當(dāng)Δθ變化時(shí)，既能達(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算法的覆蓋效率最低，覆蓋率增長(zhǎng)率最緩慢，最少需要迭代25次才能達(dá)到最大的覆蓋率；PFCEA算法優(yōu)化效率比VCFCEA算法更高，在算法迭代30次基本達(dá)到最大的覆蓋率，但算法會(huì)出現(xiàn)震蕩的現(xiàn)象；本文VFARCR算法運(yùn)行21次時(shí)開始收斂，基本達(dá)到最大覆蓋率，且不出現(xiàn)震蕩。這主要是該算法解決了虛擬力與調(diào)整角度大小相互牽制的矛盾，將覆蓋冗余度與調(diào)整方向的大小關(guān)聯(lián)起來，解決了采用固定步長(zhǎng)算法難以收斂的問題。

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

4 結(jié) 論

針對(duì)WMSNs覆蓋優(yōu)化過程中節(jié)點(diǎn)轉(zhuǎn)動(dòng)角度調(diào)整策略存在的不足，本文提出一種改進(jìn)的虛擬力算法，改進(jìn)算法有兩點(diǎn)創(chuàng)新：一是將節(jié)點(diǎn)間的虛擬力與它們之間的重疊塊面積關(guān)聯(lián)起來，使虛擬力的大小隨著重疊塊的大小變化，優(yōu)化了虛擬力的構(gòu)造；二是將節(jié)點(diǎn)轉(zhuǎn)動(dòng)角度的大小與覆蓋冗余度關(guān)聯(lián)起來，解決了固定轉(zhuǎn)動(dòng)角度中覆蓋效果與覆蓋效率難以統(tǒng)一的矛盾。仿真實(shí)驗(yàn)表明:改進(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] 何 璇,郝 群,宋 勇.一種移動(dòng)無線視頻傳感器節(jié)點(diǎn)的覆蓋算法[J].傳感技術(shù)學(xué)報(bào),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] 肖 甫,王汝傳,葉曉國(guó),等.基于改進(jìn)勢(shì)場(chǎng)的有向傳感器網(wǎng)絡(luò)路徑覆蓋增強(qiáng)算法[J].計(jì)算機(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)場(chǎng)態(tài)勢(shì)感知方面研究工作。