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

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

?

有向異構(gòu)傳感器網(wǎng)絡(luò)覆蓋優(yōu)化算法*

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

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

針對(duì)有向異構(gòu)傳感器網(wǎng)線(xiàn)隨機(jī)部署產(chǎn)生覆蓋重疊和盲區(qū)這一問(wèn)題，受到虛擬勢(shì)場(chǎng)算法的啟發(fā)，提出了基于虛擬勢(shì)場(chǎng)的有向異構(gòu)傳感器網(wǎng)絡(luò)覆蓋優(yōu)化算法(PCADH)。以有向感知模型為基礎(chǔ)，引入重疊質(zhì)心、有效質(zhì)心和虛擬邊界質(zhì)心的概念，對(duì)有向異構(gòu)傳感器網(wǎng)絡(luò)進(jìn)行虛擬受力優(yōu)化、節(jié)點(diǎn)往復(fù)運(yùn)動(dòng)優(yōu)化和邊界優(yōu)化處理。仿真結(jié)果表明:算法可以快速有效地提高有向異構(gòu)無(wú)線(xiàn)傳感器網(wǎng)絡(luò)的覆蓋率。

有向異構(gòu)傳感器網(wǎng)絡(luò)； 虛擬勢(shì)場(chǎng)； 節(jié)點(diǎn)運(yùn)動(dòng)； 邊界優(yōu)化； 覆蓋優(yōu)化

0 引 言

目前，有很多學(xué)者已經(jīng)對(duì)有關(guān)有向傳感器網(wǎng)絡(luò)、異構(gòu)傳感器網(wǎng)絡(luò)的覆蓋控制進(jìn)行了研究[1,2]。文獻(xiàn)[3]引入了有向感知模型進(jìn)行覆蓋的研究。文獻(xiàn)[4]首次引入了虛擬勢(shì)場(chǎng)的方法來(lái)優(yōu)化覆蓋增強(qiáng)問(wèn)題。在此基礎(chǔ)上，文獻(xiàn)[5]引入質(zhì)心的概念，結(jié)合虛擬勢(shì)場(chǎng)研究覆蓋增強(qiáng)問(wèn)題；文獻(xiàn)[6]引入了虛擬節(jié)點(diǎn)和角度自我調(diào)節(jié)機(jī)制以提高網(wǎng)絡(luò)覆蓋；文獻(xiàn)[7]加入了計(jì)算幾何改進(jìn)虛擬力算法來(lái)解決異構(gòu)無(wú)線(xiàn)傳感器網(wǎng)絡(luò)的覆蓋問(wèn)題;文獻(xiàn)[8]結(jié)合簡(jiǎn)單隨機(jī)抽樣理論和最優(yōu)化算法對(duì)異構(gòu)無(wú)線(xiàn)傳感器網(wǎng)絡(luò)的覆蓋問(wèn)題進(jìn)行優(yōu)化。以上的研究，只是針對(duì)有向傳感器網(wǎng)絡(luò)或者異構(gòu)傳感器網(wǎng)絡(luò)進(jìn)行研究，很少有對(duì)有向異構(gòu)傳感器網(wǎng)絡(luò)覆蓋問(wèn)題的研究。

本文提出了基于虛擬勢(shì)場(chǎng)的有向異構(gòu)傳感器網(wǎng)絡(luò)覆蓋優(yōu)化算法(potential field-based coverage algorithm for directional heterogeneous,PCADH)，仿真結(jié)果表明：算法可以有效提高覆蓋率。

1 有向異構(gòu)傳感器網(wǎng)絡(luò)感知模型與覆蓋問(wèn)題

1.1 有向感知模型

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

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

1.2 有向異構(gòu)傳感器網(wǎng)絡(luò)覆蓋問(wèn)題描述

首先假設(shè)：節(jié)點(diǎn)隨機(jī)初始部署以后，節(jié)點(diǎn)的位置不變；節(jié)點(diǎn)可以通過(guò)繞自身轉(zhuǎn)動(dòng)的方式來(lái)調(diào)節(jié)點(diǎn)的主感知方向；節(jié)點(diǎn)能獲取自身的位置坐標(biāo)信息和感知方向信息。

(1)

式中 Vi為N個(gè)節(jié)點(diǎn)的感知方向向量組；SΩ為研究區(qū)域面積。

2 有向異構(gòu)傳感器網(wǎng)絡(luò)覆蓋優(yōu)化算法

2.1 虛擬受力優(yōu)化分析

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

定義1 在研究區(qū)域Ω中，節(jié)點(diǎn)i和j的歐氏距離小于2倍的Ri，其中，Ri≤Rj，稱(chēng)節(jié)點(diǎn)i和j互為鄰居節(jié)點(diǎn)。

定義2 如果節(jié)點(diǎn)i和j互為鄰居節(jié)點(diǎn)，那么節(jié)點(diǎn)i和節(jié)點(diǎn)j的覆蓋重疊區(qū)域?yàn)镾i∩Sj。其中，將覆蓋重疊區(qū)域的質(zhì)心稱(chēng)為重疊質(zhì)心。

定義3 如果節(jié)點(diǎn)i和j互為鄰居節(jié)點(diǎn)，那么節(jié)點(diǎn)i的有效覆蓋區(qū)域?yàn)镾i-Si∩Sj。其中，將有效覆蓋區(qū)域的質(zhì)心稱(chēng)為有效質(zhì)心。

如圖2所示，節(jié)點(diǎn)i的有效覆蓋區(qū)域?yàn)镾i1，節(jié)點(diǎn)j的有效覆蓋區(qū)域?yàn)镾j2；重疊區(qū)域?yàn)镾ij；節(jié)點(diǎn)i的有效質(zhì)心點(diǎn)為O(Si1)，節(jié)點(diǎn)j的有效質(zhì)心點(diǎn)為O(Sj2)，重疊質(zhì)心點(diǎn)為O(Sij)。

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

研究區(qū)域Ω的指定質(zhì)心點(diǎn)離散分布，因此，指定質(zhì)心點(diǎn)坐標(biāo)O(x,y)可以通過(guò)離散化方法求得，公式如下

(2)

式中 xi為指定質(zhì)心的橫坐標(biāo)；yi為指定質(zhì)心的縱坐標(biāo)；num為研究區(qū)域中指定質(zhì)心的個(gè)數(shù)。

兩個(gè)電荷之間受斥力的作用，類(lèi)比到質(zhì)心的受力分析。如圖2所示，虛擬斥力Fj的模型可以類(lèi)比表達(dá)為

(3)

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

如圖2所示，斥力Fj可以分解成兩個(gè)分力Fj∥和Fj⊥。分力Fj⊥是使節(jié)點(diǎn)改變感知方向的分力；分力Fj∥是使節(jié)點(diǎn)位置移動(dòng)的分力。本文規(guī)定了節(jié)點(diǎn)的位置不能改變。所以，使節(jié)點(diǎn)移動(dòng)的分力Fj∥不起作用，可以忽略。分力Fj⊥可以導(dǎo)致節(jié)點(diǎn)的感知方向發(fā)生變化，則節(jié)點(diǎn)j感知角度的變化公式為

(4)

節(jié)點(diǎn)受到斥力的作用，就可以改變節(jié)點(diǎn)的感知方向。當(dāng)分斥力Fj⊥=0時(shí)，覆蓋控制基本達(dá)到最優(yōu)。

2.2 節(jié)點(diǎn)往復(fù)運(yùn)動(dòng)優(yōu)化分析

在有向異構(gòu)傳感器網(wǎng)絡(luò)中，普遍存在節(jié)點(diǎn)往復(fù)運(yùn)動(dòng)的問(wèn)題。假設(shè)節(jié)點(diǎn)j與i,k 均是互為鄰居節(jié)點(diǎn)。如圖3所示，有效質(zhì)心O(Sj2)受到覆蓋重疊區(qū)域Sij的斥力Fij，受到覆蓋重疊區(qū)域?yàn)镾jk的斥力Fjk。斥力Fij可以分解成分力Fij∥和分力Fij⊥，斥力Fij可以分解成分力Fij∥和分力Fij⊥。其中，因?yàn)楣?jié)點(diǎn)位置固定，所以，分力Fij∥和分力Fik∥不起作用，可以忽略。那么，當(dāng)分力Fij⊥和分力Fjk⊥大小相差很小時(shí)，而且受設(shè)定的轉(zhuǎn)動(dòng)角度的限制。當(dāng)Fij⊥>Fik⊥時(shí)，節(jié)點(diǎn)感知方向往右轉(zhuǎn)動(dòng)一個(gè)角度；旋轉(zhuǎn)之后就導(dǎo)致了Fij⊥

圖3 節(jié)點(diǎn)運(yùn)動(dòng)受力分析Fig 3 Force analysis of node movements

針對(duì)該問(wèn)題，本文設(shè)置了一個(gè)節(jié)點(diǎn)停止運(yùn)動(dòng)的閾值w，w1是分力Fij⊥和分力Fjk⊥的差值的絕對(duì)值，即w1=|Fij⊥-Fjk⊥|。當(dāng)分力Fij⊥和分力Fjk⊥的差值的絕對(duì)值小于w1時(shí)，則節(jié)點(diǎn)就停止轉(zhuǎn)動(dòng)。這樣就可以避免節(jié)點(diǎn)的往復(fù)運(yùn)動(dòng)，提高算法的收斂性。

2.3 節(jié)點(diǎn)邊界優(yōu)化處理

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

(5)

式中 k為常數(shù)系數(shù)；Dis1為節(jié)點(diǎn)i與鄰居節(jié)點(diǎn)j之間的歐氏距離；λ為所受的虛擬斥力Fj的方向。

圖4 邊界節(jié)點(diǎn)受力分析Fig 4 Force analysis of boundary nodes

節(jié)點(diǎn)i受到虛擬斥力Fj的作用以后，節(jié)點(diǎn)i的感知方向會(huì)發(fā)生變化，則變化角度θc可以表示為

(6)

式中 θc為邊界節(jié)點(diǎn)i完成邊界優(yōu)化感知角度的變化量；Fjmax為斥力的最大值，用來(lái)限制斥力的改變，是一個(gè)與最大感知半徑有關(guān)的常量；θmax為邊界節(jié)點(diǎn)i感知角度變化的最大值，用來(lái)限制角度的變化，是一個(gè)常量。而且，規(guī)定了一個(gè)覆蓋面積的閾值w2，閾值w2與節(jié)點(diǎn)i的半徑Ri有關(guān)。當(dāng)節(jié)點(diǎn)i受到虛擬斥力Fj的作用，感知方向發(fā)生變化。當(dāng)節(jié)點(diǎn)i的覆蓋區(qū)域面積大于閾值w2時(shí)，節(jié)點(diǎn)i就停止轉(zhuǎn)動(dòng)。

2.4 PCADH算法描述

輸入：異構(gòu)節(jié)點(diǎn)的個(gè)數(shù)、位置坐標(biāo)信息、半徑的取值范圍與取值方法、感知方向信息、感知夾角信息。

輸出：各個(gè)異構(gòu)節(jié)點(diǎn)最后的感知方向。

t←0；

獲取有向異構(gòu)傳感器網(wǎng)絡(luò)節(jié)點(diǎn)Mi(xi,yi)以及它的鄰居節(jié)點(diǎn)的相關(guān)信息；

規(guī)定PCAHD算法的循環(huán)次數(shù)；

While (t

for i = 1 ∶N

if Mi是邊界節(jié)點(diǎn)

構(gòu)建半徑最大的有向異構(gòu)節(jié)點(diǎn)Mj為虛擬鄰居節(jié)點(diǎn)；

While Mi是邊界節(jié)點(diǎn)

計(jì)算節(jié)點(diǎn)Mi受到節(jié)點(diǎn)Mj的虛擬斥力 ；

If節(jié)點(diǎn)Mi受到的虛擬鄰居節(jié)點(diǎn)Mj的虛擬斥力Fj

計(jì)算節(jié)點(diǎn)Mi的轉(zhuǎn)動(dòng)角度θc；

else

節(jié)點(diǎn)Mi停止轉(zhuǎn)動(dòng)；

end;

end;

else

if節(jié)點(diǎn)Mi與鄰居節(jié)點(diǎn)之間存在覆蓋重疊區(qū)域；

計(jì)算節(jié)點(diǎn)Mi受到的兩個(gè)鄰居節(jié)點(diǎn)的虛擬斥力分力Fji⊥和Fki⊥；

if節(jié)點(diǎn)Mi存在節(jié)點(diǎn)的往復(fù)運(yùn)動(dòng)情況

else

節(jié)點(diǎn)Mi停止轉(zhuǎn)動(dòng)；

end;

end

end;

end;

獲取有向異構(gòu)節(jié)點(diǎn)Mi以及鄰居節(jié)點(diǎn)的位置、感知方向相關(guān)信息；

t←t+1；

end

3 算法的仿真結(jié)果與分析

3.1 算法實(shí)例仿真

本文通過(guò)Matlab R2012a對(duì)有向異構(gòu)傳感器網(wǎng)絡(luò)的覆蓋問(wèn)題進(jìn)行仿真。仿真區(qū)域?yàn)?00 m×500 m；節(jié)點(diǎn)個(gè)數(shù)N為70個(gè)；節(jié)點(diǎn)感知半徑Ri為[60,90]范圍內(nèi)的70個(gè)隨機(jī)數(shù);感知夾角α為45°；區(qū)域視角β為90°

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

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

圖6 PCADH優(yōu)化效果圖Fig 6 Effect picture of PCADH optimization

從圖5、圖6可以看出:初始覆蓋率經(jīng)過(guò)1次優(yōu)化以后，提高幅度達(dá)到了12.59 %，優(yōu)化效果很明顯。隨優(yōu)化次數(shù)的增加，提高幅度變緩。

70個(gè)有向異構(gòu)傳感器節(jié)點(diǎn)經(jīng)過(guò)PCADH算法優(yōu)化1～40次的覆蓋率變化圖，如圖7所示。從圖中可以看出，經(jīng)過(guò)PCADH算法優(yōu)化以后，覆蓋率得到了大幅度的提升。尤其是在前10次優(yōu)化，提高幅度最為明顯，提高了22.03 %，10次以后提高就變的緩慢。變化趨勢(shì)顯示了算法具有良好的收斂性。

圖7 70個(gè)節(jié)點(diǎn)不同算法覆蓋率優(yōu)化趨勢(shì)Fig 7 Coverage rate optimization trend of 70 nodes with different algorithms

3.2 仿真結(jié)果對(duì)比

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

在規(guī)定的研究區(qū)域隨機(jī)部署50,70,90,110個(gè)傳感器節(jié)點(diǎn)，感知半徑Ri為[60,90]范圍內(nèi)50,70,90,110個(gè)隨機(jī)數(shù)，三種算法PCADH,SOA,PFCEA經(jīng)過(guò)40次優(yōu)化以后，可以得到覆蓋率提升幅度P′與傳感器節(jié)點(diǎn)個(gè)數(shù)的關(guān)系，如圖8所示?？梢钥闯觯瑹o(wú)論傳感器節(jié)點(diǎn)個(gè)數(shù)多少，經(jīng)過(guò)40次算法PCADH優(yōu)化以后，網(wǎng)絡(luò)覆蓋率提升幅度都比其他兩種算法有大幅度提升。

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

4 結(jié) 論

本文提出的PCADH算法，能夠很大幅度地提高有向異構(gòu)傳感器網(wǎng)絡(luò)的覆蓋率，且具有良好的收斂性和收斂速度。在后期的工作中，應(yīng)該在對(duì)有向異構(gòu)傳感器網(wǎng)絡(luò)的覆蓋問(wèn)題進(jìn)行研究的基礎(chǔ)上，考慮障礙物對(duì)有向異構(gòu)傳感器網(wǎng)絡(luò)的覆蓋影響。

[1] 張春華，劉方愛(ài),申志遠(yuǎn).一種新的異構(gòu)無(wú)線(xiàn)傳感器網(wǎng)絡(luò)分簇算法[J].傳感器與微系統(tǒng),2013,32(6):143-146.

[2] 李 明.異構(gòu)傳感器網(wǎng)絡(luò)覆蓋算法研究[D].重慶：重慶大學(xué),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] 程衛(wèi)芳,廖湘科,沈昌祥.有向傳感器網(wǎng)絡(luò)最大覆蓋調(diào)度算法[J].軟件學(xué)報(bào),2009,20(4):975-984.

[6] 陳義軍,白光偉,張進(jìn)明,等.基于虛擬勢(shì)場(chǎng)的有向傳感器網(wǎng)絡(luò)覆蓋增強(qiáng)算法的改進(jìn)[J].小型微型計(jì)算機(jī)系統(tǒng),2013,34(2):243-246.

[7] 馮秀芳,關(guān)志艷,全欣娜,等.基于虛擬力的異構(gòu)節(jié)點(diǎn)網(wǎng)絡(luò)覆蓋增強(qiáng)算法[J].計(jì)算機(jī)工程,2009,35(5):103-105.

[8] 杜曉玉,孫力娟,郭 劍,等.異構(gòu)無(wú)線(xiàn)傳感器網(wǎng)絡(luò)覆蓋優(yōu)化算法[J].電子與信息學(xué)報(bào),2014,36(3):696-702.

[9] 戴 寧,毛劍琳,付麗霞,等.基于虛擬勢(shì)場(chǎng)的有向傳感器網(wǎng)絡(luò)覆蓋優(yōu)化算法[J].計(jì)算機(jī)應(yīng)用研究,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

國(guó)家自然科學(xué)基金資助項(xiàng)目(61163051);云南省應(yīng)用基礎(chǔ)研究基金資助項(xiàng)目(2009ZC050M)

TP 393

A

1000—9787(2016)11—0132—04

王昌征(1990-)，男，山東青島人，碩士研究生，主要研究方向?yàn)闊o(wú)線(xiàn)傳感器網(wǎng)絡(luò)覆蓋研究。