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

劉 軍

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

?

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

劉 軍

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

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

無線多媒體傳感器網絡； 覆蓋優化； 虛擬力； 質心

0 引 言

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

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

1 WMSNs覆蓋問題研究

1.1 方向可調感知模型

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

圖1 方向可調的感知模型Fig 1 Adjustable directional sensing model

當區域中的點pi被傳感器節點si覆蓋時，當且僅當滿足以下條件：

在該模型的WMSNs覆蓋優化中，區域覆蓋率p、節點個數N、區域面積A、感知視角α、感知半徑R之間的關系滿足如下關系(具體推導過程見文獻[9])

(1)

2.2 問題描述

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

(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}。

區域覆蓋率p的求解如下

(3)

式中 N為部署在區域中的傳感器節點數量。

2 VFARCR算法

2.1 虛擬力分析

改進算法利用鄰居節點的斥力優化節點感知方向，斥力的方向為節點感知區域質心的連線方向，斥力大小與兩節點間覆蓋重疊區域大小成正比，與節點感知質心間的距離的平方成反比,即

(4)

(5)

式中 m為節點i的鄰居節點個數。

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

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

2.2 覆蓋重疊區域面積的計算方法

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

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

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

(6)

節點i的覆蓋冗余度可以定義為

(7)

式中 m為節點i的鄰居節點個數。

2.3 節點感知方向調整規則

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

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

(8)

式中 Rcagi為節點i的覆蓋冗余度，α為感知中心線距離扇形感知區域兩側邊界的夾角。當Rcagi很小時，在實際操作中很難實現，所以，設定一個閾值η來實現角度調整的可行性，當Rcagi≥η時，角度進行調整。

3 仿真實驗

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

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

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

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

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

4 結 論

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

[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] 趙 旭,雷 霖,代傳龍.無線傳感器網絡的覆蓋控制[J].傳感器與微系統,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中目標覆蓋算法與通信策略研究[J].傳感器與微系統,2013,32(8):32-34.

[7] 何 璇,郝 群,宋 勇.一種移動無線視頻傳感器節點的覆蓋算法[J].傳感技術學報,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].計算機研究與發展，2009,46(12):2126-2133.

[10] 張 璐.無線多媒體傳感器網絡覆蓋技術研究[D].西安：西安電子科技大學,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-)，男，北京人，碩士，教授，研究生導師，從事無線數據通信、電子技術應用、戰場態勢感知方面研究工作。