有向異構傳感器網絡覆蓋優化算法*

王昌征，毛劍琳，付麗霞，郭 寧，曲蔚賢

(昆明理工大學 信息工程與自動化學院，云南 昆明 650500)

?

有向異構傳感器網絡覆蓋優化算法*

王昌征，毛劍琳，付麗霞，郭 寧，曲蔚賢

(昆明理工大學 信息工程與自動化學院，云南 昆明 650500)

針對有向異構傳感器網線隨機部署產生覆蓋重疊和盲區這一問題，受到虛擬勢場算法的啟發，提出了基于虛擬勢場的有向異構傳感器網絡覆蓋優化算法(PCADH)。以有向感知模型為基礎，引入重疊質心、有效質心和虛擬邊界質心的概念，對有向異構傳感器網絡進行虛擬受力優化、節點往復運動優化和邊界優化處理。仿真結果表明:算法可以快速有效地提高有向異構無線傳感器網絡的覆蓋率。

有向異構傳感器網絡； 虛擬勢場； 節點運動； 邊界優化； 覆蓋優化

0 引 言

目前，有很多學者已經對有關有向傳感器網絡、異構傳感器網絡的覆蓋控制進行了研究[1,2]。文獻[3]引入了有向感知模型進行覆蓋的研究。文獻[4]首次引入了虛擬勢場的方法來優化覆蓋增強問題。在此基礎上，文獻[5]引入質心的概念，結合虛擬勢場研究覆蓋增強問題；文獻[6]引入了虛擬節點和角度自我調節機制以提高網絡覆蓋；文獻[7]加入了計算幾何改進虛擬力算法來解決異構無線傳感器網絡的覆蓋問題;文獻[8]結合簡單隨機抽樣理論和最優化算法對異構無線傳感器網絡的覆蓋問題進行優化。以上的研究，只是針對有向傳感器網絡或者異構傳感器網絡進行研究，很少有對有向異構傳感器網絡覆蓋問題的研究。

本文提出了基于虛擬勢場的有向異構傳感器網絡覆蓋優化算法(potential field-based coverage algorithm for directional heterogeneous,PCADH)，仿真結果表明：算法可以有效提高覆蓋率。

1 有向異構傳感器網絡感知模型與覆蓋問題

1.1 有向感知模型

有向感知模型[9]是一個扇形的感知區域。可以表示成一個四元素組成的向量組，即D(Mi(xi,yi),Ri,Vi(t),α)。如圖1所示，Mi(xi,yi)為節點的坐標位置； Ri為節點的感知半徑；單位向量Vi(t)為t時刻節點的感知方向。特別指出，θi為節點從t1時刻到t2時刻感知方向的變化值。α為節點的感知夾角，其中，β=2α表示該扇形感知區域的視角。半徑異構的有向異構傳感器網絡滿足半徑同構傳感器網絡有向感知模型。

圖1 有向感知模型Fig 1 Directed perception model

1.2 有向異構傳感器網絡覆蓋問題描述

首先假設：節點隨機初始部署以后，節點的位置不變；節點可以通過繞自身轉動的方式來調節點的主感知方向；節點能獲取自身的位置坐標信息和感知方向信息。

(1)

式中 Vi為N個節點的感知方向向量組；SΩ為研究區域面積。

2 有向異構傳感器網絡覆蓋優化算法

2.1 虛擬受力優化分析

為了研究方便，本文首先做以下定義：

定義1 在研究區域Ω中，節點i和j的歐氏距離小于2倍的Ri，其中，Ri≤Rj，稱節點i和j互為鄰居節點。

定義2 如果節點i和j互為鄰居節點，那么節點i和節點j的覆蓋重疊區域為Si∩Sj。其中，將覆蓋重疊區域的質心稱為重疊質心。

定義3 如果節點i和j互為鄰居節點，那么節點i的有效覆蓋區域為Si-Si∩Sj。其中，將有效覆蓋區域的質心稱為有效質心。

如圖2所示，節點i的有效覆蓋區域為Si1，節點j的有效覆蓋區域為Sj2；重疊區域為Sij；節點i的有效質心點為O(Si1)，節點j的有效質心點為O(Sj2)，重疊質心點為O(Sij)。

圖2 質心虛擬受力分析Fig 2 Analysis on virtual force of mass center

研究區域Ω的指定質心點離散分布，因此，指定質心點坐標O(x,y)可以通過離散化方法求得，公式如下

(2)

式中 xi為指定質心的橫坐標；yi為指定質心的縱坐標；num為研究區域中指定質心的個數。

兩個電荷之間受斥力的作用，類比到質心的受力分析。如圖2所示，虛擬斥力Fj的模型可以類比表達為

(3)

式中 k為常數系數； Dis為重疊質心點O(Sij)與有效質心點O(Sj2)之間的歐氏距離；v為所受的虛擬斥力Fj的方向。

如圖2所示，斥力Fj可以分解成兩個分力Fj∥和Fj⊥。分力Fj⊥是使節點改變感知方向的分力；分力Fj∥是使節點位置移動的分力。本文規定了節點的位置不能改變。所以，使節點移動的分力Fj∥不起作用，可以忽略。分力Fj⊥可以導致節點的感知方向發生變化，則節點j感知角度的變化公式為

(4)

節點受到斥力的作用，就可以改變節點的感知方向。當分斥力Fj⊥=0時，覆蓋控制基本達到最優。

2.2 節點往復運動優化分析

在有向異構傳感器網絡中，普遍存在節點往復運動的問題。假設節點j與i,k 均是互為鄰居節點。如圖3所示，有效質心O(Sj2)受到覆蓋重疊區域Sij的斥力Fij，受到覆蓋重疊區域為Sjk的斥力Fjk。斥力Fij可以分解成分力Fij∥和分力Fij⊥，斥力Fij可以分解成分力Fij∥和分力Fij⊥。其中，因為節點位置固定，所以，分力Fij∥和分力Fik∥不起作用，可以忽略。那么，當分力Fij⊥和分力Fjk⊥大小相差很小時，而且受設定的轉動角度的限制。當Fij⊥>Fik⊥時，節點感知方向往右轉動一個角度；旋轉之后就導致了Fij⊥

圖3 節點運動受力分析Fig 3 Force analysis of node movements

針對該問題，本文設置了一個節點停止運動的閾值w，w1是分力Fij⊥和分力Fjk⊥的差值的絕對值，即w1=|Fij⊥-Fjk⊥|。當分力Fij⊥和分力Fjk⊥的差值的絕對值小于w1時，則節點就停止轉動。這樣就可以避免節點的往復運動，提高算法的收斂性。

2.3 節點邊界優化處理

邊界節點到邊界的距離小于感知半徑，導致了大部分的覆蓋區域都在研究區域的邊界以外，影響了網絡覆蓋性能。如圖4所示，節點i是一個邊界節點。本文提出的有向異構傳感器網絡邊界節點處理方法：增加一個感知半徑最大鄰居節點j；質心點O(Si)與質心點O(Sj)的連線與邊界線垂直。假設不存在覆蓋重疊區域，則質心點O(Si)受到質心點O(Sj)的虛擬斥力可以表達為

(5)

式中 k為常數系數；Dis1為節點i與鄰居節點j之間的歐氏距離；λ為所受的虛擬斥力Fj的方向。

圖4 邊界節點受力分析Fig 4 Force analysis of boundary nodes

節點i受到虛擬斥力Fj的作用以后，節點i的感知方向會發生變化，則變化角度θc可以表示為

(6)

式中 θc為邊界節點i完成邊界優化感知角度的變化量；Fjmax為斥力的最大值，用來限制斥力的改變，是一個與最大感知半徑有關的常量；θmax為邊界節點i感知角度變化的最大值，用來限制角度的變化，是一個常量。而且，規定了一個覆蓋面積的閾值w2，閾值w2與節點i的半徑Ri有關。當節點i受到虛擬斥力Fj的作用，感知方向發生變化。當節點i的覆蓋區域面積大于閾值w2時，節點i就停止轉動。

2.4 PCADH算法描述

輸入：異構節點的個數、位置坐標信息、半徑的取值范圍與取值方法、感知方向信息、感知夾角信息。

輸出：各個異構節點最后的感知方向。

t←0；

獲取有向異構傳感器網絡節點Mi(xi,yi)以及它的鄰居節點的相關信息；

規定PCAHD算法的循環次數；

While (t

for i = 1 ∶N

if Mi是邊界節點

構建半徑最大的有向異構節點Mj為虛擬鄰居節點；

While Mi是邊界節點

計算節點Mi受到節點Mj的虛擬斥力 ；

If節點Mi受到的虛擬鄰居節點Mj的虛擬斥力Fj

計算節點Mi的轉動角度θc；

else

節點Mi停止轉動；

end;

end;

else

if節點Mi與鄰居節點之間存在覆蓋重疊區域；

計算節點Mi受到的兩個鄰居節點的虛擬斥力分力Fji⊥和Fki⊥；

if節點Mi存在節點的往復運動情況

else

節點Mi停止轉動；

end;

end

end;

end;

獲取有向異構節點Mi以及鄰居節點的位置、感知方向相關信息；

t←t+1；

end

3 算法的仿真結果與分析

3.1 算法實例仿真

本文通過Matlab R2012a對有向異構傳感器網絡的覆蓋問題進行仿真。仿真區域為500 m×500 m；節點個數N為70個；節點感知半徑Ri為[60,90]范圍內的70個隨機數;感知夾角α為45°；區域視角β為90°

如圖5所示，為初始(t=0)覆蓋圖和初始覆蓋率P0=64.96 %。圖6(d)為PCADH優化的覆蓋圖與覆蓋率。

圖5 初始覆蓋圖Fig 5 Effect picture of initial coverage

圖6 PCADH優化效果圖Fig 6 Effect picture of PCADH optimization

從圖5、圖6可以看出:初始覆蓋率經過1次優化以后，提高幅度達到了12.59 %，優化效果很明顯。隨優化次數的增加，提高幅度變緩。

70個有向異構傳感器節點經過PCADH算法優化1～40次的覆蓋率變化圖，如圖7所示。從圖中可以看出，經過PCADH算法優化以后，覆蓋率得到了大幅度的提升。尤其是在前10次優化，提高幅度最為明顯，提高了22.03 %，10次以后提高就變的緩慢。變化趨勢顯示了算法具有良好的收斂性。

圖7 70個節點不同算法覆蓋率優化趨勢Fig 7 Coverage rate optimization trend of 70 nodes with different algorithms

3.2 仿真結果對比

從圖7中可以看出，本文提出的PCADH算法，在第一次優化就可以大幅度的提高網絡的覆蓋率。且整個過程的優化效果比SOA[7]，PFCEA[8]算法提高明顯。此外算法PCADH優化8次后，基本達到了最優的覆蓋率，比其他兩種算法的收斂速度明顯要快。

在規定的研究區域隨機部署50,70,90,110個傳感器節點，感知半徑Ri為[60,90]范圍內50,70,90,110個隨機數，三種算法PCADH,SOA,PFCEA經過40次優化以后，可以得到覆蓋率提升幅度P′與傳感器節點個數的關系，如圖8所示。可以看出，無論傳感器節點個數多少，經過40次算法PCADH優化以后，網絡覆蓋率提升幅度都比其他兩種算法有大幅度提升。

圖8 40次優化覆蓋率提高幅度Fig 8 Increasing of 40 times optimal coverage rate

4 結 論

本文提出的PCADH算法，能夠很大幅度地提高有向異構傳感器網絡的覆蓋率，且具有良好的收斂性和收斂速度。在后期的工作中，應該在對有向異構傳感器網絡的覆蓋問題進行研究的基礎上，考慮障礙物對有向異構傳感器網絡的覆蓋影響。

[1] 張春華，劉方愛,申志遠.一種新的異構無線傳感器網絡分簇算法[J].傳感器與微系統,2013,32(6):143-146.

[2] 李 明.異構傳感器網絡覆蓋算法研究[D].重慶：重慶大學,2011.

[3] Ma Huadong，Liu Yonghe．On coverage problems of directional sensor network[C]∥Proc of International Conference on Mobile Ad Hoc and Sensor Networks，2005:721-731．

[4] Howard A，Mataric M J，Sukhatme G S.Mobile sensor network deployment using potential field:A distributed scalable solution to the area coverage problem[C]∥Proceedings of the 6th International Conference on Distributed Autonomous Robotics Systems,New York，USA:ACM，2002:299-308．

[5] 程衛芳,廖湘科,沈昌祥.有向傳感器網絡最大覆蓋調度算法[J].軟件學報,2009,20(4):975-984.

[6] 陳義軍,白光偉,張進明,等.基于虛擬勢場的有向傳感器網絡覆蓋增強算法的改進[J].小型微型計算機系統,2013,34(2):243-246.

[7] 馮秀芳,關志艷,全欣娜,等.基于虛擬力的異構節點網絡覆蓋增強算法[J].計算機工程,2009,35(5):103-105.

[8] 杜曉玉,孫力娟,郭 劍,等.異構無線傳感器網絡覆蓋優化算法[J].電子與信息學報,2014,36(3):696-702.

[9] 戴 寧,毛劍琳,付麗霞,等.基于虛擬勢場的有向傳感器網絡覆蓋優化算法[J].計算機應用研究,2014,31(3):905-907.

毛劍琳，通訊作者，E—mail:km_mjl@aliyun.com。

Coverage optimization algorithm for directional heterogeneous sensor networks*

WANG Chang-zheng,MAO Jian-lin,FU Li-xa,GUO Ning,QU Wei-xian

(Faculty of Information Engineering and Automation,Kunming University of Science and Technology, Kunming 650500,China)

Aiming at problem of coverage overlapping areas and blind spots that nodes deployed randomly in directional heterogeneous sensor networks,introduce a virtual potential field-based coverage algorithm for directional heterogeneous (PCADH) networks inspired by virtual potential field algorithm.Through involving concepts of overlapping centroid,effective centroid and virtual boundary centroid to the model,this algorithm carries out optimization processing of virtual force,node advance and return movements and boundary in directional heterogeneous networks based on directed perception model.Simulation results show that the proposed algorithm can improve coverage rate of directional heterogeneous sensor networks rapidly and effectively.

directional heterogeneous sensor networks;virtual potential field;node movements;boundary optimization;coverage optimization

10.13873/J.1000—9787(2016)11—0132—04

2016—01—06

國家自然科學基金資助項目(61163051);云南省應用基礎研究基金資助項目(2009ZC050M)

TP 393

A

1000—9787(2016)11—0132—04

王昌征(1990-)，男，山東青島人，碩士研究生，主要研究方向為無線傳感器網絡覆蓋研究。