蔣一波,梅佳東,汪念華,盛尚浩

(浙江工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,杭州 310023)

1 引 言

如今有向傳感器網(wǎng)絡(luò)憑借自身應(yīng)用的廣泛性和多樣性,在各領(lǐng)域越來越受到重視和關(guān)注.有向傳感器網(wǎng)絡(luò)是由一系列有向傳感器所組成,比如視頻攝像頭,超聲波發(fā)生器等.而相比于傳統(tǒng)的全向傳感器,有向傳感器的覆蓋區(qū)域是為一個(gè)以節(jié)點(diǎn)為圓心、半徑為其感知距離的扇形區(qū)域,且不能在同一時(shí)間感知到四周的事物,而只能感知一個(gè)方向,通過利用硬件旋轉(zhuǎn)裝置,能夠讓有向傳感器實(shí)現(xiàn)感知方向的改變,即覆蓋區(qū)域的變化.

對(duì)于無線傳感器網(wǎng)絡(luò),覆蓋控制一直是個(gè)熱點(diǎn)問題,合理的覆蓋優(yōu)化有利于對(duì)周圍事物的監(jiān)測(cè)感知,獲取更全面的信息參數(shù),使得網(wǎng)絡(luò)資源分配更合理,也有利于進(jìn)一步提高網(wǎng)絡(luò)的生存周期.現(xiàn)有的傳感器節(jié)點(diǎn)覆蓋研究主要分為目標(biāo)覆蓋,柵欄覆蓋和區(qū)域覆蓋.

目前,提升區(qū)域覆蓋質(zhì)量的技術(shù)主要有節(jié)點(diǎn)的初始部署和感知節(jié)點(diǎn)方向的有效調(diào)配.對(duì)于復(fù)雜環(huán)境的節(jié)點(diǎn)布置,通常采用隨機(jī)拋灑方式,而如此方法易產(chǎn)生覆蓋盲區(qū)和重疊區(qū),大大削減了節(jié)點(diǎn)的覆蓋效率.因此在節(jié)點(diǎn)隨機(jī)部署后,要想獲得更理想的網(wǎng)絡(luò)覆蓋性能,往往會(huì)采用覆蓋優(yōu)化算法去改變節(jié)點(diǎn)的感知方向.所以如何正確地調(diào)節(jié)有向傳感器節(jié)點(diǎn)的感知視角(FoV)是一個(gè)解決覆蓋問題的關(guān)鍵.

2 相關(guān)研究

針對(duì)有向傳感器的區(qū)域覆蓋控制理論,現(xiàn)有國(guó)內(nèi)外的研究方法也有一些相關(guān)的研究成果,且大都傾向于設(shè)計(jì)分布式算法,通過相互間交換信息數(shù)據(jù)再獨(dú)立實(shí)行算法.如Kandoth等人[2]提出的分布式Face-Away算法,通過相鄰節(jié)點(diǎn)的感知視角,找到每個(gè)傳感器鄰居點(diǎn)密度最小的方向,有效降低了節(jié)點(diǎn)間的覆蓋冗余區(qū).對(duì)于存在障礙物的情況,Tezcan等人[6]加入了對(duì)相鄰節(jié)點(diǎn)間非覆蓋區(qū)域考慮,根據(jù)節(jié)點(diǎn)的多媒體覆蓋確定其方向,來實(shí)現(xiàn)覆蓋提升.Sung 等人[7]對(duì)隨機(jī)部署節(jié)點(diǎn)構(gòu)建了泰森多邊形,再根據(jù)貪心算法確定節(jié)點(diǎn)方向,實(shí)現(xiàn)高效率覆蓋.陶等人[3]將虛擬勢(shì)場(chǎng)引入到有向傳感器網(wǎng)絡(luò)中,并加入質(zhì)心的概念,提出了基于虛擬勢(shì)場(chǎng)的有向傳感器網(wǎng)絡(luò)覆蓋增強(qiáng)算法PFCEA.在勢(shì)場(chǎng)中的虛擬力作用下,各節(jié)點(diǎn)互相推開,作擴(kuò)散運(yùn)動(dòng),減少了區(qū)域內(nèi)的盲區(qū)和重疊區(qū).在最大有向區(qū)域覆蓋MDAC問題的研究上,程衛(wèi)芳等人[4]不僅證明其是NP完全的,還提出貪心算法DGreedy和具備網(wǎng)絡(luò)拓?fù)湫畔⒌腜Greedy,后者通過局部貪心選擇覆蓋區(qū)域最大的方向來獲得一個(gè)次優(yōu)解.

虛擬勢(shì)場(chǎng)作為解決傳感器網(wǎng)絡(luò)覆蓋的典型方法,Howard等人[14]和Poduri等人[15]依據(jù)機(jī)器人的運(yùn)動(dòng)路徑規(guī)劃研究,先后將虛擬勢(shì)場(chǎng)方法引入到傳感器網(wǎng)絡(luò)的覆蓋問題中.Zou等人[5]對(duì)隨機(jī)部署后的節(jié)點(diǎn)提出了一種虛擬力優(yōu)化算法(VFA),通過有效結(jié)合引力和斥力來決定節(jié)點(diǎn)新的位置,提升覆蓋性能.陳義軍等人[8]在區(qū)域邊界外引入了虛擬節(jié)點(diǎn),以增強(qiáng)網(wǎng)絡(luò)對(duì)邊界區(qū)域的覆蓋率,此外還提出了節(jié)點(diǎn)的自調(diào)整角速度機(jī)制,提高了算法的執(zhí)行效率.Xiao等人[9]將虛擬勢(shì)場(chǎng)運(yùn)用到有向傳感器網(wǎng)絡(luò)的路徑覆蓋增強(qiáng)問題上,利用了節(jié)點(diǎn)的共同覆蓋率設(shè)計(jì)了一種改進(jìn)的勢(shì)場(chǎng)函數(shù),達(dá)到了路徑的較好覆蓋.蔣一波等人[12]為了應(yīng)對(duì)監(jiān)控區(qū)域存在障礙物的情況,加入了遮擋區(qū)域的作用力,提出了一種適用于無盲區(qū)覆蓋模型的動(dòng)態(tài)優(yōu)化算法PFOFSA,顯著地消除了感知重疊區(qū)和盲區(qū).

以上算法都能取得較好的區(qū)域覆蓋效果,但都是直接運(yùn)用節(jié)點(diǎn)相互間的虛擬引力或斥力作為感知視角旋轉(zhuǎn)的作用力,沒有加入對(duì)于虛擬力的其他修正指標(biāo),節(jié)點(diǎn)間會(huì)存在不適宜斥力的情況.針對(duì)這一個(gè)問題,本文提出了改進(jìn)虛擬力的有向傳感器網(wǎng)絡(luò)區(qū)域覆蓋優(yōu)化算法MVPFCEA,該算法采用新的虛擬力分解策略,并對(duì)虛擬斥力增加修正指標(biāo),優(yōu)化了節(jié)點(diǎn)旋轉(zhuǎn)的作用力.仿真實(shí)驗(yàn)表明,該算法能夠?qū)崿F(xiàn)較好的覆蓋效果.

3 感知模型與問題描述

3.1 有向感知模型

圖1 有向傳感器感知模型Fig.1 Directional sensor perceptual model

本文采用二元有向感知模型,即當(dāng)目標(biāo)點(diǎn)落在節(jié)點(diǎn)的感知范圍內(nèi),則目標(biāo)點(diǎn)被覆蓋.當(dāng)且僅當(dāng)滿足以下條件時(shí),目標(biāo)點(diǎn)pi被判為落在節(jié)點(diǎn)的感知范圍內(nèi),被覆蓋.

3.2 問題描述

本文假設(shè)網(wǎng)絡(luò)中所有節(jié)點(diǎn)同構(gòu),即都具有相同的感知半徑、感知視角,節(jié)點(diǎn)在隨機(jī)初始部署后,自身位置不再改變,但其感知視角能夠左右旋轉(zhuǎn),節(jié)點(diǎn)能夠獲取自身位置和感知信息.

對(duì)于一個(gè)邊界有限的二維監(jiān)控區(qū)域平面,陶等人[3]根據(jù)有向傳感器感知模型和隨機(jī)部署策略,推導(dǎo)出當(dāng)目標(biāo)區(qū)域內(nèi)網(wǎng)絡(luò)覆蓋率至少達(dá)到p0時(shí),需要部署的節(jié)點(diǎn)規(guī)模計(jì)算公式:

(1)

其中S為目標(biāo)區(qū)域面積.根據(jù)公式(1)所得,要想節(jié)點(diǎn)的初始覆蓋率越高,在節(jié)點(diǎn)感知半徑和視角不變下,所需要的節(jié)點(diǎn)數(shù)量N也越多,且增長(zhǎng)率越來越大,所以通過增加傳感器節(jié)點(diǎn)數(shù)量來提升覆蓋率的做法顯得不切實(shí)際,費(fèi)成本,而合理的覆蓋優(yōu)化策略則可以節(jié)省大量成本.

(2)

4 覆蓋優(yōu)化算法

4.1 傳統(tǒng)虛擬勢(shì)場(chǎng)方法

本文的有向傳感器節(jié)點(diǎn)一經(jīng)部署后位置不再改變,而感知方向可調(diào),在虛擬勢(shì)場(chǎng)中受力時(shí)表現(xiàn)為扇形感知區(qū)域繞軸心即節(jié)點(diǎn)圓心旋轉(zhuǎn).文獻(xiàn)[3]引入了“質(zhì)心”的概念,將有向傳感器節(jié)點(diǎn)感知方向的調(diào)整轉(zhuǎn)換為其扇形區(qū)域的質(zhì)心點(diǎn)繞傳感器節(jié)點(diǎn)做圓周運(yùn)動(dòng).如圖2所示,對(duì)于一個(gè)均勻的有向感知扇形區(qū)域,其質(zhì)心點(diǎn)位置是在扇形對(duì)稱軸上且與圓心距離為2R sinα/3α,每一個(gè)傳感器節(jié)點(diǎn)有且僅有一個(gè)質(zhì)心點(diǎn)與之對(duì)應(yīng).

圖2 質(zhì)心點(diǎn)位置Fig．2 Centroidposition圖3 兩質(zhì)心點(diǎn)間斥力作用Fig．3 Repulsionbetweentwocentroids

在有向傳感器網(wǎng)絡(luò)中,當(dāng)兩節(jié)點(diǎn)間的歐式距離不大于節(jié)點(diǎn)感知半徑(R)的2倍時(shí),兩者互為鄰居節(jié)點(diǎn),且存在虛擬斥力.在虛擬勢(shì)場(chǎng)中,質(zhì)心點(diǎn)受到相鄰一個(gè)或多個(gè)質(zhì)心點(diǎn)斥力作用,每個(gè)扇形面受力繞圓心旋轉(zhuǎn),并逐漸相互遠(yuǎn)離擴(kuò)散,最終實(shí)現(xiàn)區(qū)域的最大化覆蓋.

如圖3所示,dij表示有向傳感器節(jié)點(diǎn)si和sj之間的歐式距離.dij小于傳感器節(jié)點(diǎn)感知半徑(R)的2倍,且兩個(gè)節(jié)點(diǎn)的感知區(qū)域間存在重疊,故它們兩者之間存在虛擬斥力,該斥力作用在傳感器節(jié)點(diǎn)對(duì)應(yīng)的質(zhì)心點(diǎn)ci和cj上.

(3)

其中,Dij表示質(zhì)心點(diǎn)ci到質(zhì)心點(diǎn)cj的歐式距離;KR表示斥力系數(shù)(KR=1);αij為單位向量,表示斥力方向(由質(zhì)心點(diǎn)cj指向質(zhì)心點(diǎn)ci);ψi則表示為傳感器節(jié)點(diǎn)si的鄰居節(jié)點(diǎn)集合.

(4)

在扇形覆蓋區(qū)域旋轉(zhuǎn)的過程中,質(zhì)心點(diǎn)所受到的虛擬合力是時(shí)刻變化的,為此節(jié)點(diǎn)需要每隔時(shí)間Δt重新獲取相鄰節(jié)點(diǎn)的感知方向和質(zhì)心點(diǎn)位置,再重新計(jì)算該時(shí)刻的虛擬力,得出旋轉(zhuǎn)方向和旋轉(zhuǎn)角度.

質(zhì)心點(diǎn)轉(zhuǎn)動(dòng)的方向沿所受力在圓弧切線方向上的分量,轉(zhuǎn)動(dòng)大小則是按固定轉(zhuǎn)動(dòng)角度Δθ進(jìn)行旋轉(zhuǎn).當(dāng)固定角度較大時(shí),節(jié)點(diǎn)后期旋轉(zhuǎn)易越過最優(yōu)感知方向,而較小時(shí),則降低了算法的收斂速度.所以文獻(xiàn)[8]設(shè)立了節(jié)點(diǎn)角度自調(diào)整機(jī)制,根據(jù)每一次覆蓋率增加的情況來實(shí)時(shí)調(diào)整節(jié)點(diǎn)轉(zhuǎn)動(dòng)角度的大小,使節(jié)點(diǎn)較快地穩(wěn)定在最佳感知角度.

圖4 質(zhì)心點(diǎn)受力模型Fig．4 Centroidpointforcemodel圖5 力F⊥很小，不易轉(zhuǎn)動(dòng)Fig．5 ForceF⊥isverysmall，noteasytoturn

4.2 改進(jìn)虛擬力算法

4.2.1 虛擬力方向分解、大小不分解

傳統(tǒng)虛擬勢(shì)場(chǎng)覆蓋算法中,有向傳感器節(jié)點(diǎn)質(zhì)心之間的受力模型如圖4所示.

圖6 陷入局部最優(yōu)的狀態(tài)Fig.6 Fall into the local optimal state

4.2.2 引入虛擬斥力的修正指標(biāo)

在虛擬勢(shì)場(chǎng)的現(xiàn)有研究工作中,推動(dòng)節(jié)點(diǎn)旋轉(zhuǎn)調(diào)整感知視角的力往往只是各相鄰節(jié)點(diǎn)互相作用的虛擬合力,并沒有其他對(duì)于此虛擬力的修正或改變指標(biāo).

此外通過對(duì)于有向傳感器的理解和仿真,可以認(rèn)為圖7的3種情況已經(jīng)較好地展現(xiàn)了有向傳感器節(jié)點(diǎn)的覆蓋效率,對(duì)于要想通過其他節(jié)點(diǎn)來覆蓋圖7空隙部分區(qū)域,則必然會(huì)付出巨大冗余覆蓋的代價(jià),另外圖7中每個(gè)節(jié)點(diǎn)依然受到相鄰節(jié)點(diǎn)的虛擬斥力,而會(huì)導(dǎo)致其逐漸偏離現(xiàn)在的較好覆蓋位置.相反,圖8的兩種覆蓋情況則更需要其他節(jié)點(diǎn)來覆蓋未覆蓋區(qū)域,或得到其他節(jié)點(diǎn)的斥力來使覆蓋區(qū)域靠近聚合.

圖7 三組較好覆蓋的節(jié)點(diǎn)Fig．7 Threegroupsofbettercoveragenodes圖8 待覆蓋優(yōu)化節(jié)點(diǎn)Fig．8 Nodestobecoveredoptimization

(5)

圖9 改進(jìn)虛擬力后同一位置的變化Fig.9 Same location changes after the effect of modify virtual force

根據(jù)修正指標(biāo)來削減兩節(jié)點(diǎn)間不合適的虛擬斥力,使得相鄰節(jié)點(diǎn)的覆蓋區(qū)域更加緊湊,來實(shí)現(xiàn)有向傳感器節(jié)點(diǎn)覆蓋的合理化,但同時(shí)也帶來了相鄰節(jié)點(diǎn)覆蓋出現(xiàn)重疊區(qū),如圖9所示,可以直觀地得出圖9(a)的覆蓋效果要比圖9(b)的覆蓋效果好,但由于我們?cè)黾恿颂摂M斥力的修正指標(biāo),導(dǎo)致其斥力的削弱,往往使實(shí)際情況更加容易趨向于圖9(b)的狀態(tài).

為此簡(jiǎn)單地對(duì)之前提出的修正指標(biāo)再增加了與兩節(jié)點(diǎn)覆蓋面積重疊率φij大小相關(guān)的修正項(xiàng)(1+φij)ρ,ρ為指數(shù).最終,對(duì)于虛擬斥力的修正指標(biāo)模型為公式(6):

(6)

其中k1,k2分別表示對(duì)于各部分的修正因子,縮小數(shù)量級(jí).

(7)

針對(duì)文獻(xiàn)[8]中提到的邊界節(jié)點(diǎn)問題,本文同樣地在目標(biāo)區(qū)域的邊界外設(shè)立了虛擬節(jié)點(diǎn),所不同的是我們?cè)诰嚯x目標(biāo)區(qū)域每條邊界線外2Rsinα/3α處都布置一排等間距的虛擬節(jié)點(diǎn)而不是簡(jiǎn)單地只針對(duì)邊界節(jié)點(diǎn)獨(dú)立設(shè)立一個(gè)虛擬節(jié)點(diǎn),另外我們還根據(jù)邊界節(jié)點(diǎn)覆蓋非目標(biāo)區(qū)域的面積比,同樣來對(duì)邊界節(jié)點(diǎn)產(chǎn)生向內(nèi)的虛擬斥力增加了修正項(xiàng)(1+μi)ρ,μi為邊界節(jié)點(diǎn)si覆蓋非目標(biāo)區(qū)域與總覆蓋區(qū)域的面積比,μi越大則表示該節(jié)點(diǎn)覆蓋非目標(biāo)區(qū)域的面積越多,因此受虛擬節(jié)點(diǎn)向內(nèi)的斥力也越大,有利于減少邊界節(jié)點(diǎn)對(duì)非目標(biāo)區(qū)域的覆蓋,提高目標(biāo)區(qū)域的網(wǎng)絡(luò)覆蓋率.

表1 MVPFCEA算法描述
Table 1 MVPFCEA algorithm description

輸入?yún)?shù)：節(jié)點(diǎn)si及其相鄰節(jié)點(diǎn)的位置和感知方向信息．輸出結(jié)果：節(jié)點(diǎn)si最終的感知方向信息 Vi(t)．1． t←0；//初始化時(shí)間步長(zhǎng)變量2． 計(jì)算節(jié)點(diǎn)si相應(yīng)質(zhì)心點(diǎn)ci初始位置pci(t)；3． 計(jì)算節(jié)點(diǎn)si的所有鄰居節(jié)點(diǎn)為集合ψi，M表示鄰居節(jié)點(diǎn)集合中元素的個(gè)數(shù)；4． While(true) 4．1 t←t+1 4．2 Fi(t)←0→； 4．3 For(j=0；j

同時(shí),本文還采用了自調(diào)整的方法來改變節(jié)點(diǎn)優(yōu)化覆蓋時(shí)的轉(zhuǎn)動(dòng)角度θ,基于以上算法的改進(jìn),依據(jù)修正后虛擬斥力的大小調(diào)整節(jié)點(diǎn)轉(zhuǎn)動(dòng)角度大小.斥力越大則說明節(jié)點(diǎn)覆蓋效果越不佳,節(jié)點(diǎn)轉(zhuǎn)動(dòng)角度越大,反之則越小.轉(zhuǎn)動(dòng)角度θ與虛擬斥力合分量F⊥的關(guān)系如公式(8):

(8)

其中,θmax表示初始設(shè)定的最大轉(zhuǎn)動(dòng)角度,本文設(shè)θmax為15,θmin表示初始設(shè)定的最小轉(zhuǎn)動(dòng)角度,本文設(shè)θmax為1,k3為力與角度的單位轉(zhuǎn)化系數(shù),本文取1.

另外,我們對(duì)節(jié)點(diǎn)角度的自調(diào)整機(jī)制增加了反饋結(jié)構(gòu),即當(dāng)節(jié)點(diǎn)在調(diào)整過程中,目標(biāo)區(qū)域的網(wǎng)絡(luò)覆蓋率出現(xiàn)幾次負(fù)提升時(shí),則對(duì)以上的最大轉(zhuǎn)動(dòng)角度和最小轉(zhuǎn)動(dòng)角度進(jìn)行一些削減處理,比如相應(yīng)的除以某個(gè)相關(guān)系數(shù)使其減小,如此能夠在之后迭代過程中,節(jié)點(diǎn)逐步靠近最優(yōu)感知方向,實(shí)現(xiàn)對(duì)區(qū)域覆蓋率提升的微調(diào)效果.

4.2.3 算法描述

本文在已有文獻(xiàn)的基礎(chǔ)上,首先對(duì)虛擬力的分解進(jìn)行改變,再對(duì)虛擬斥力增加了修正指標(biāo),同時(shí)也加入了邊界虛擬節(jié)點(diǎn),引入節(jié)點(diǎn)轉(zhuǎn)動(dòng)角度自調(diào)整機(jī)制,提出的改進(jìn)虛擬力有向傳感器目標(biāo)覆蓋優(yōu)化算法MVPFCEA是一種分布式算法,要求每個(gè)傳感器節(jié)點(diǎn)上并發(fā)執(zhí)行.其算法描述見表1.

5 算法仿真和性能評(píng)價(jià)

本實(shí)驗(yàn)在Windows10環(huán)境下,利用Matlab工具仿真了MVPFCEA算法,通過分析比較了MVPFCEA與PFCEA、IPFCEA算法之間的性能,驗(yàn)證了MVPFCEA算法的優(yōu)越性.實(shí)驗(yàn)仿真參數(shù)如表2所示.

表2 仿真參數(shù)
Table 2 Simulation parameters

參 數(shù)值目標(biāo)區(qū)域500×500m2有向傳感器節(jié)點(diǎn)數(shù)量106節(jié)點(diǎn)的感知半徑60m節(jié)點(diǎn)的感知視角(FoV)π/2

5.1 實(shí)例研究

假設(shè)預(yù)期的網(wǎng)絡(luò)覆蓋率p0=70%,根據(jù)公式(1)可以得到初始部署節(jié)點(diǎn)數(shù)為106,基于上述參數(shù),本文記錄了執(zhí)行MVPFCEA算法每時(shí)刻的節(jié)點(diǎn)覆蓋情況,共40個(gè)時(shí)間步長(zhǎng).初始節(jié)點(diǎn)隨機(jī)部署的分布圖如圖10(a)所示,其初始覆蓋率為63.93%,目標(biāo)區(qū)域內(nèi)存在大量覆蓋盲區(qū),以及節(jié)點(diǎn)間存在大量冗余覆蓋,整體的網(wǎng)絡(luò)覆蓋率不夠理想.在執(zhí)行MVPFCEA算法后,各節(jié)點(diǎn)都受到相鄰節(jié)點(diǎn)的虛擬斥力影響,感知方向得到調(diào)整優(yōu)化,逐步消除了區(qū)域中的覆蓋盲區(qū)和重疊區(qū),明顯提升了整個(gè)網(wǎng)絡(luò)的覆蓋率.最終節(jié)點(diǎn)覆蓋效果如圖10(e)所示,網(wǎng)絡(luò)覆蓋率穩(wěn)定在81.2%,比初始覆蓋率提高了17.3%.根據(jù)式(1)可知當(dāng)網(wǎng)絡(luò)覆蓋率為81.2%時(shí),至少需要部署的節(jié)點(diǎn)規(guī)模數(shù)是147個(gè),所以說通過執(zhí)行MVPFCEA算法優(yōu)化后的網(wǎng)絡(luò)可以大大節(jié)省覆蓋成本.

5.2 對(duì)比分析

本節(jié)主要進(jìn)行MVPFCEA算法與IPFCEA、PFCEA算法的比較和性能分析,針對(duì)這三種算法,基于上述的相同仿真參數(shù)進(jìn)行多次的實(shí)驗(yàn)仿真,并對(duì)每個(gè)時(shí)間步長(zhǎng)的節(jié)點(diǎn)覆蓋率取均值得到圖11,通過圖中數(shù)據(jù)可以分析出:三種算法對(duì)目標(biāo)區(qū)域的網(wǎng)絡(luò)覆蓋率都有明顯的提升,但PFCEA算法由于采用節(jié)點(diǎn)轉(zhuǎn)動(dòng)固定角度的方法來調(diào)整感知方向,且對(duì)邊界節(jié)點(diǎn)不做處理,故最終覆蓋率提升量不大且慢;IPFCEA算法則使用了依據(jù)覆蓋率增長(zhǎng)速度來改變節(jié)點(diǎn)轉(zhuǎn)動(dòng)角度的自調(diào)整機(jī)制,算法收斂性初期較快,但維持不久,覆蓋增長(zhǎng)率很快就變得緩慢,另外對(duì)目標(biāo)區(qū)域外設(shè)立虛擬節(jié)點(diǎn)的措施,覆蓋率雖有提升但也并不明顯;而本文所提出的MVPFCEA算法加入了對(duì)虛擬力的修正指標(biāo)使得網(wǎng)絡(luò)覆蓋率的提升效果更加顯著,合理的角度自調(diào)整機(jī)制也使覆蓋收斂速度變得最快,維持時(shí)間長(zhǎng),在第10個(gè)時(shí)間步長(zhǎng),網(wǎng)絡(luò)覆蓋率提高了近 13%,覆蓋提升效果顯著;之后提升量緩慢增加,趨于穩(wěn)定,最終的覆蓋效果也較優(yōu)于其他兩種算法.

5.3 性能比較

本節(jié)主要考察相關(guān)參數(shù)對(duì)MVPFCEA算法性能的影響,通過在傳感器節(jié)點(diǎn)數(shù)目、感知半徑和感知視角上分別取不同數(shù)目和大小,與現(xiàn)有的覆蓋增強(qiáng)算法PFCEA,IPFCEA進(jìn)行比較.目標(biāo)區(qū)域大小等其他參數(shù)與上一節(jié)相同.為了更直觀表現(xiàn)算法的優(yōu)化性能,使用了節(jié)點(diǎn)優(yōu)化后的覆蓋率pf和初始覆蓋率p0進(jìn)行相減處理后所得的覆蓋提升量Δp指標(biāo),即Δp=pf-p0,對(duì)每種參數(shù)改變的情況同樣進(jìn)行多次實(shí)驗(yàn)取均值的方法來衡量各算法的差異性.

圖10 實(shí)例迭代優(yōu)化Fig.10 Example iterative optimization

圖11 三種算法覆蓋率比較分析圖Fig.11 Comparison of three algorithm coverage

從圖12中變化的曲線可以看出,三種算法性能對(duì)于節(jié)點(diǎn)相關(guān)參數(shù)變化的趨勢(shì)基本相同,但本文MVPFCEA算法的穩(wěn)定性和覆蓋增強(qiáng)性較優(yōu)于其他算法.在圖12(a)中,當(dāng)節(jié)點(diǎn)規(guī)模較小時(shí),隨著節(jié)點(diǎn)數(shù)的增加,覆蓋率的提升量逐漸變大,而當(dāng)節(jié)點(diǎn)規(guī)模大于一定程度時(shí),覆蓋率的增加量則隨節(jié)點(diǎn)數(shù)的增加而逐步降低,這是由于節(jié)點(diǎn)數(shù)量的增加使得目標(biāo)區(qū)域的初始覆蓋率較大,節(jié)點(diǎn)間的覆蓋盲區(qū)面積大大減小,這無疑會(huì)削弱各算法的性能.對(duì)于圖12(b)、(c),節(jié)點(diǎn)感知半徑和感知視角的改變對(duì)算法的影響與此類似.感知半徑或感知視角取值較小時(shí),單個(gè)節(jié)點(diǎn)的覆蓋范圍較小而導(dǎo)致相鄰節(jié)點(diǎn)間的感知重疊區(qū)域也較少,因而通過算法的優(yōu)化改善后,網(wǎng)絡(luò)整體覆蓋率提升量不高,隨著感知半徑或感知視角的增大,算法對(duì)網(wǎng)絡(luò)覆蓋性能的提升顯著,達(dá)到一定值之后,網(wǎng)絡(luò)覆蓋率的提升量同樣逐漸減小.

圖12 節(jié)點(diǎn)相關(guān)參數(shù)對(duì)覆蓋性能的影響Fig.12 Influence of Node-related parameters on coverage performance

6 結(jié)束語

本文從有向傳感器感知特性出發(fā),深入分析研究基于虛擬勢(shì)場(chǎng)的有向傳感器網(wǎng)絡(luò)覆蓋優(yōu)化算法,對(duì)該類算法所涉及到的關(guān)鍵點(diǎn)虛擬斥力問題進(jìn)行了改進(jìn).通過改變虛擬合力的分解方法,并引入對(duì)虛擬斥力的修正指標(biāo),削弱不合適的虛擬斥力來對(duì)該類算法進(jìn)行優(yōu)化,提出了MVPFCEA算法,本文最后,經(jīng)過一系列仿真實(shí)驗(yàn)驗(yàn)證了MVPFCEA算法不僅提高了有向傳感器節(jié)點(diǎn)的覆蓋率,也使得節(jié)點(diǎn)感知方向的調(diào)整得到快速收斂.本文提出的MVPFCEA算法雖然能對(duì)目標(biāo)區(qū)域的覆蓋進(jìn)行了較好的提升,但其對(duì)虛擬力的修正指標(biāo)不夠完善,且缺少對(duì)障礙物的修正項(xiàng).所以下一步的工作是繼續(xù)完善斥力的修正指標(biāo)公式,并使其能夠適用于帶有障礙物的目標(biāo)區(qū)域.

[1] Cheng W F,Liao X K,Shen C X.Maximal coverage scheduling in wireless directional sensor networks[J].Journal of Software,2009,20(4):975-984.

[2] Kandoth C,Chellappan S.Angular mobility assisted coverage in directional sensor networks[C].International Conference on Network-Based Information Systems,IEEE,2009:376-379.

[3] Tao Dan,Ma Hua-dong,Liu Liang.A virtual potential field based coverage-enhancing algorithm for directional sensor networks [J].Journal of Software,2007,18(5):1152-1163.

[4] Cheng Wei-fang,Liao Xiang-ke,Shen Chang-xiang,et al.Maximal coverage scheduling in wireless directional sensor networks[J].Journal of Software,2009,20(4):975-984.

[5] Zou Y.Coverage-driven sensor deployment and energy-efficient information processing in wireless sensor networks[J].Dissertation Abstracts International,Volume:66-06,Section:B,page:3338.;Adviser:Krishnendu Cha,2004.

[6] Tezcan N,Wang W.Self-orienting wireless multimedia sensor networks for maximizing multimedia coverage[C].IEEE International Conference on Communication,IEEE,2008:2206-2210.

[7] Sung T W,Yang C S.Voronoi-based coverage improvement approach for wireless directional sensor networks[J].Journal of Network & Computer Applications,2014,39(1):202-213.

[8] Chen Yi-jun,Bai Guang-wei,Zhang Jin-ming.Improvement of the virtual potential field based on coverage-enhancing algorithm for directional sensor networks[J].Journal of Chinese Computer Systems,2013,34(2):243-246.

[9] Xiao F,Wang R,Ye X,et al.A path coverage-enhancing algorithm for directional sensor network based on improved potential field[J].Journal of Computer Research & Development,2009,46(12):2126-2133.

[10] Zhang Mei-yan,Cai Wen-yu.Research on directional K-coverage control algorithm for wireless video sensor networks[J].Chinese Journal of Sensors and Actuators,2013,26(5):728-733.

[11] Huang Shuai,Cheng Liang-lun.A low redundancy coverage·enhancing algorithm for directional sensor network based on fictitious force [J].Chinese Journal of Sensors and Actuators,2011,24(3):418-422.

[12] Jiang Yi-bo,Wang Wan-liang,Chen Wei-jie,et al.Coverage optimization of occlusion-free surveillance for video sensor networks[J].Journal of Software,2012,23(2):310-322.

[13] Li Na,Xiang Feng-hong,Mao Jian-lin,et al.Coverage optimization algorithm of directional sensor network in multi-obstacles scene[J].Compuer Engineering,2015,41(4):19-25.

[14] Howard A,Matari M J,Sukhatme G S.Mobile sensor network deployment using potential fields:a distributed,scalable solution to the area coverage problem[M].Distributed Autonomous Robotic Systems 5,Springer Japan,2002:299-308.

[15] Poduri S,Sukhatme G.Constrained coverage for mobile sensor networks[C].IEEE International Conference on Robotics and Automation,Proceedings,ICRA,IEEE Xplore,2004:165-171.

附中文參考文獻(xiàn)：

[3] 陶 丹,馬華東,劉 亮.基于虛擬勢(shì)場(chǎng)的有向傳感器網(wǎng)絡(luò)覆蓋增強(qiáng)算法[J].軟件學(xué)報(bào),2007,18(5):1152-1163.

[4] 程衛(wèi)芳,廖湘科,沈昌祥,等.有向傳感器網(wǎng)絡(luò)最大覆蓋調(diào)度算法[J].軟件學(xué)報(bào),2009,20(4):975-984.

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

[10] 張美燕,蔡文郁.無線視頻傳感器網(wǎng)絡(luò)有向感知K覆蓋控制算法研究[J].傳感技術(shù)學(xué)報(bào),2013,26(5):728-733.

[11] 黃 帥,程良倫.一種基于虛擬力的有向傳感器網(wǎng)絡(luò)低冗余覆蓋增強(qiáng)算法[J].傳感技術(shù)學(xué)報(bào),2011,24(3):418-422.

[12] 蔣一波,王萬良,陳偉杰,等.視頻傳感器網(wǎng)絡(luò)中無盲區(qū)監(jiān)視優(yōu)化[J].軟件學(xué)報(bào),2012,23(2):310-322.

[13] 李 娜,向鳳紅,毛劍琳,等.多障礙場(chǎng)景的有向傳感器網(wǎng)絡(luò)覆蓋優(yōu)化算法[J].計(jì)算機(jī)工程,2015,41(4):19-25.