關(guān)志艷，黃向生

1(山西大學(xué) 商務(wù)學(xué)院 信息學(xué)院，太原 030001) 2(中國科學(xué)院 自動化研究所，北京 100190)

1 引 言

隨著物聯(lián)網(wǎng)時代的到來，人們對于各種監(jiān)控環(huán)境信息的采集，已經(jīng)不局限于溫濕度、氣體濃度、光感等全向傳感器的采集，越來越多的情況下，像視頻、超聲波、紅外等有向傳感器對細粒度、精準信息的環(huán)境監(jiān)測更為廣泛[1,2].任何環(huán)境監(jiān)測首先要解決的就是節(jié)點部署覆蓋問題，這關(guān)乎到信息采集的全面性及準確性，對傳感器網(wǎng)絡(luò)“感知”服務(wù)質(zhì)量至關(guān)重要[3,4].

有向傳感器網(wǎng)絡(luò)DSN(Directional Sensor Networks)覆蓋分為區(qū)域覆蓋、目標覆蓋、柵欄覆蓋[5].本文是在DSN區(qū)域覆蓋前提下進行研究，國內(nèi)外已有一些算法來提高區(qū)域覆蓋質(zhì)量.Sung等[6]提出將DSN劃分為Voronoi單元，應(yīng)用分布式貪婪算法來提高覆蓋率.Kandoth等[7]提出分布式Face Away算法，以鄰居節(jié)點間密度最小的方向來改善感知重疊度.大多數(shù)算法傾向于無障礙物環(huán)境下節(jié)點分布式計算，相互間交換信息再進行獨立算法執(zhí)行.

虛擬勢場作為解決傳感器網(wǎng)絡(luò)覆蓋的典型方法，自2007年陶丹等[8]第一次將虛擬勢場引入有向傳感器網(wǎng)絡(luò)DSN中，近些年很多專家都對虛擬力算法VFA(Virtual Force Algorithm)應(yīng)用于DSN有了各種改進.陳瑩等[9]在虛擬力模型基礎(chǔ)上建立學(xué)習(xí)自動機與環(huán)境信息的交互機制來提高覆蓋質(zhì)量；蔣一波等[10]對將鄰居節(jié)點影響引入到質(zhì)心計算中，進而調(diào)整角度機制，提高算法執(zhí)行效率；肖甫等[11]將鄰居節(jié)點對路徑軌跡點的共同覆蓋率引入虛擬斥力計算中以提高覆蓋率.以上VFA均沒有分析障礙物對虛擬力的影響，且對鄰居節(jié)點的定義也均是以圓心間距離小于感知半徑之和作為判斷條件，未考慮節(jié)點方向性造成的影響，勢必造成節(jié)點計算成本高等缺陷.

粒子群算法PSO(Particle Swarm Optimization)是典型的全局優(yōu)化算法，張聚偉等[12]建立有向傳感器模糊感知模型，將其應(yīng)用于PSO中來解決路徑覆蓋問題；顧曉燕等[13]采用改進的多步式位置來更新粒子角度，從而減少覆蓋重疊區(qū)和盲區(qū).以上單純粒子群算法應(yīng)用于DSN，由于初始代的位置、角度及角速度都是隨機分配，容易使算法陷于“早熟”，不易達到適度值最優(yōu)狀態(tài).

范興剛等[14]將VFA與PSO結(jié)合應(yīng)用于有向傳感器網(wǎng)絡(luò)，對網(wǎng)絡(luò)覆蓋率有一定的改善作用，但在隨機部署網(wǎng)絡(luò)計算虛擬力后，應(yīng)用粒子群算法時節(jié)點的初始角速度未考慮虛擬力影響，這就導(dǎo)致網(wǎng)絡(luò)覆蓋的不可控性增強，且未考慮隨機障礙物的影響.

本文首次將VFA和PSO結(jié)合起來應(yīng)用于隨機障礙物下的有向傳感器網(wǎng)絡(luò)中，詳細分析了有向概率感知模型，定義了受質(zhì)心限制的鄰居節(jié)點，分析了VFA應(yīng)用于障礙物DSN的虛擬力計算，虛擬合力與旋轉(zhuǎn)角度之間的關(guān)系，用PSO來弱化VFA的局部極值效應(yīng)，仿真實驗表明受障礙物影響的VFA融合PSO的DSN覆蓋算法能有效改善隨機障礙物下DSN的覆蓋盲區(qū)和重疊區(qū).

2 DSN分析

2.1 有向感知能力衰減概率模型

圖1 有向感知能力衰減概率模型Fig.1 Directed sensor reduction probability model

凡是在扇形感知區(qū)域內(nèi)的目標均被感知，但有的有向傳感器節(jié)點的感知能力會隨感知方向向兩側(cè)衰減和由內(nèi)向外衰減，目標監(jiān)測點會因為在扇形區(qū)不同區(qū)域，呈現(xiàn)不同的感知概率[15].如圖1所示，將扇形劃分為5個區(qū)域，1區(qū)域完全在扇形感知區(qū)，2區(qū)域接近扇形兩側(cè)，4區(qū)域接近扇形外側(cè)，3區(qū)域則是扇形兩側(cè)與外側(cè)交織處，2、3、4區(qū)域感知概率會有不同程度衰減.

如圖1所示αe為衰減偏移角度，re為衰減感知長度，目標點Mj在扇形區(qū)域5個分區(qū)的感知概率見式(1)：

(1)

表1 有向扇形5分區(qū)關(guān)系表Table 1 Directed sector 5 partition relation table

不同的有向傳感器有不同的衰減方式，有的傳感器并不會兩側(cè)或外側(cè)衰減，如視頻節(jié)點、超聲波節(jié)點，因此在細粒度目標感知時，需要參照有向感知能力衰減模型具體情況具體分析.

2.2 障礙物下的有效覆蓋率

針對障礙物下的有向傳感器網(wǎng)絡(luò)區(qū)域覆蓋，用盡量少的節(jié)點達到避障下最大的覆蓋面積是區(qū)域覆蓋的優(yōu)化方向.有向傳感器節(jié)點部署在監(jiān)測區(qū)域后位置不變，感知視角可調(diào)，因此最優(yōu)有效覆蓋率則是求取一組<β1,β2,…,βn>的有向節(jié)點使除去與障礙物重疊的覆蓋總面積(重疊面積不重復(fù)算)與監(jiān)測面積之比達到最大.

(2)

其中A為監(jiān)測區(qū)域面積,B為障礙物面積，A=l·k，l、k為監(jiān)測區(qū)域長與寬，Ai為有向節(jié)點覆蓋面積，Bi為節(jié)點i與障礙物的重疊面積.當滿足初始有效覆蓋率CE0時需要的傳感器節(jié)點規(guī)模為[9]：

(3)

3 障礙物虛擬力分析

3.1 問題描述

本文主要研究區(qū)域覆蓋，旨在經(jīng)過算法求得一組<β1,β2,…,βn>，以使有效覆蓋率最大化.所有有向傳感器節(jié)點同構(gòu)，采用五元組扇形模型.真實環(huán)境下必然遇到節(jié)點能量供給不均衡、感知不靈敏及監(jiān)測環(huán)境的不可控性等情況.本文在matlab下進行仿真,有些條件是理想化的，因此有必要做以下假設(shè)：

1)有向傳感器節(jié)點為計算能力較強的智能傳感器，采用分布式節(jié)點計算，每個節(jié)點兼顧網(wǎng)絡(luò)終端和路由雙重功能.每個節(jié)點收集到其他節(jié)點位置信息后，會在自身執(zhí)行算法[16]；

2)初始隨機部署后，位置將不再移動，只調(diào)整角度,節(jié)點可通過自身GPS獲得圓心坐標Si，感知視域夾角2α；

3)整個監(jiān)測環(huán)境為矩形平面區(qū)，通信半徑大于2Rs，監(jiān)測區(qū)域完全連通，不考慮信道對稱性、多徑和衰減等問題[17].

3.2 鄰居節(jié)點虛擬力分析

(4)

圖2 鄰居節(jié)點間受力模型Fig.2 Virtual force model between neighbor nodes

如圖2所示，分析有向節(jié)點S1、S2、S3、S4間的作用力，以S1為分析點，d12<1.5dth,S2對S1為斥力F12；d13≥1.5dth，S3對S1為引力F13；S4與S1非鄰居節(jié)點，它們之間沒有作用力.將Fij分解成垂直于感知方向的分量Fij′和指向節(jié)點圓心方向的分量Fij″，F(xiàn)ij′=Fij·sinθij，F(xiàn)ij″=Fij·cosθij.

3.3 障礙物與節(jié)點間斥力分析

在監(jiān)測環(huán)境下，難免會有障礙物，有向傳感器節(jié)點盡量避開與障礙物的大面積重疊，如圖3所示，Oj為障礙物，本文假設(shè)障礙物為類似于此的矩形區(qū).

FiOj=(ρb/diOj，θiOj+π)

(5)

其中ρb為障礙物斥力參數(shù)，ρb與障礙物面積SOj成正比，ρb=SOj/(α·Rs2)，diOj為Ci到Oj的距離，θiOj為FiOj的方向角度，其計算與θij類似，對于FiOj′、FiOj″的分量拆解與Fij類似.

圖3 障礙物斥力模型Fig.3 Barrier repulsion model

3.4 虛擬合力分析

每個節(jié)點都有可能受多個鄰居節(jié)點、多個障礙物的影響，節(jié)點所受虛擬力均可拆分成垂直感知方向的分量(即切線分量)和指向節(jié)點圓心的分量(即向心分量)，k1、k2為節(jié)點i的鄰居節(jié)點個數(shù)和鄰居障礙物個數(shù)，兩分量之和分別為:

(6)

3.5 轉(zhuǎn)動角度計算

從動力學(xué)角度分析，可知節(jié)點轉(zhuǎn)動角度由向心分量Fi′和切線分量Fi″共同決定,假設(shè)在Δt時間內(nèi)Fi′、Fi″不變.

3.5.1 切線方向

(7)

3.5.2 向心方向

本文分析的節(jié)點所受虛擬力由物理學(xué)圓周運動可知‖F(xiàn)i″‖=γ·vt2·Rs,vt為向心力提供的角速度.

(8)

結(jié)合式(7)、式(8),節(jié)點i所受虛擬斥力的轉(zhuǎn)動角度Δθi：

Δθi=kθ·(Δθi′+Δθi″)

(9)

3.6 障礙物影響下虛擬力算法流程

1)初始化網(wǎng)絡(luò)節(jié)點規(guī)模n，鄰居節(jié)點引力系數(shù)ρg，斥力參數(shù)ρr，障礙物斥力系數(shù)ρb，視域范圍2α，感知半徑Rs，隨機部署n個有向傳感器節(jié)點，自動獲取圓心坐標，感知方向夾角，經(jīng)過計算可獲得質(zhì)心坐標，節(jié)點生成五元組感知模型.

2)設(shè)置最大循環(huán)次數(shù)Hmax

for loop=1:Hmax

{fori=1:n%建立n×n矩陣，存放節(jié)點間距離

{forj=1:n

{計算節(jié)點i,j的圓心距離Dij和質(zhì)心距離dij；

if(dij<2Rs&&Dij<2Rs) %判斷是否鄰居節(jié)點

{建立節(jié)點的鄰居節(jié)點質(zhì)心距離dij矩陣;

式(4)計算鄰居節(jié)點間引力斥力Fij及Fij′、Fij″；}

}

}

forj=1:k2%計算節(jié)點與障礙物間斥力

{計算diOj；

if(diOj<2RS)

式(5)計算FiOj及FiOj′、FiOj″；

式(6)計算節(jié)點i在切線方向和向心方向的分量合力；

式(7)-式(9)計算節(jié)點i旋轉(zhuǎn)角度Δθi，對節(jié)點進行二維灰度變化求得有效覆蓋率；}

}

依據(jù)障礙物影響下虛擬算法流程，假設(shè)在100m×100m監(jiān)測區(qū)域內(nèi)，分布一個矩形障礙物，假設(shè)初始覆蓋率至少達到50%，由式(3)計算需要50個90°視域Rs=12m的有向傳感器節(jié)點，經(jīng)過10次隨機分布節(jié)點障礙物，每次迭代30次，觀察網(wǎng)絡(luò)有效覆蓋率情況，圖4可以看出，經(jīng)過虛擬力算法節(jié)點分布均勻化，但由于避障手法單一而使障礙物附近出現(xiàn)覆蓋空洞效應(yīng).

圖4 虛擬力作用節(jié)點分布對比圖Fig.4 Contrast figure after virtual force

4 障礙物下的虛擬力融合粒子群的DSN覆蓋分析

4.1 粒子群模型

本文將DSN中的大量有向傳感器節(jié)點簡化為平面內(nèi)沒有質(zhì)量且允許旋轉(zhuǎn)的粒子，粒子據(jù)適度值函數(shù)來衡量粒子位置優(yōu)劣，粒子旋轉(zhuǎn)角速度和角度受自身旋轉(zhuǎn)經(jīng)驗和鄰居粒子的旋轉(zhuǎn)經(jīng)驗來進行綜合調(diào)整[19，20]，每次迭代中，粒子據(jù)式(10)更新角速度和感知方向水平夾角.

(10)

(11)

4.2 虛擬力融合粒子群覆蓋算法

本文在傳統(tǒng)粒子更新速度公式中加入虛擬力作用下的旋轉(zhuǎn)角度的影響，并且將隨機分布下受障礙物虛擬力作用的角速度，作為粒子群第0代的初始角速度，粒子據(jù)式(12)更新角速度和感知方向水平夾角.

(12)

(13)

4.3 障礙物下的虛擬力融合粒子群DSN覆蓋算法流程

基本思想：首先隨機分布節(jié)點，分布式計算每個節(jié)點所受虛擬合力，在合力作用下的旋轉(zhuǎn)角度及角速度；然后節(jié)點粒子化，將隨機分布下的角速度及旋轉(zhuǎn)角度，作為粒子群第0代的初始角速度，據(jù)更新公式進行粒子進化；最后以網(wǎng)絡(luò)有效覆蓋率為適度值函數(shù)來得到節(jié)點迭代最優(yōu)解.

1)初始化網(wǎng)絡(luò)粒子規(guī)模n，學(xué)習(xí)因子a1、a2、b1、b2，虛擬力影響加速因子av、bv，最大迭代次數(shù)tmax；

3)fork=1:tmax

{fori=1:n

matlab下對節(jié)點進行二維灰度變化求得有效覆CEK+1;

if(CEK+1>CEK)

}

4)CEmax=max(CE0,CE1,…,CEtmax)

5 算法仿真與性能分析

5.1 實驗參數(shù)設(shè)定

本文利用matlab在隨機部署矩形障礙物的監(jiān)測環(huán)境下，利用虛擬力融合粒子群覆蓋算法仿真，主要進行三方面觀察：

1)通過實例展示算法適度值優(yōu)化效果；

2)對虛擬力算法(VFA)和虛擬力融合粒子群算法(VFA-PSO)進行收斂效果驗證；

3)不同網(wǎng)絡(luò)參數(shù)對虛擬力融合粒子群算法(VFA-PSO)性能的影響.

實驗涉及到的參數(shù)如表2所示.

表2 參數(shù)列表Table 2 List of parameters

5.2 實例效果

5.2.1 算法適度值優(yōu)化效果比較

首先在表2所示的監(jiān)測環(huán)境下，初始預(yù)估覆蓋率至少達到60%，隨機部署Rs=12m，2α=π/2的有向傳感器節(jié)點需100個(據(jù)式(3)計算可得n=90，但考慮到監(jiān)測環(huán)境覆蓋稍微冗余，故n=100)，隨機部署3個矩形障礙物于監(jiān)測環(huán)境下，觀察實例效果，由于隨機部署的隨意性較大，算法優(yōu)化后的效果也有質(zhì)量差異，因此某次的實驗效果不具有代表性，本文對20次隨機部署進行統(tǒng)計觀察，有效覆蓋率則取50次迭代對應(yīng)算法作用后CE的平均值，來提高實驗普適性，減少誤差.圖5是實驗的一次采樣，圖5(a)是隨機部署3個障礙物于監(jiān)測環(huán)境下，圖5(b)是VFA算法迭代過程的一次，并不能確保迭代到最后的優(yōu)化效果一定是最好的，單可以看出節(jié)點分布比隨機分布更均勻些，圖5(c)經(jīng)過VFA-PSO算法迭代過程的一次，節(jié)點覆蓋更均勻，且障礙物的覆蓋空洞效應(yīng)也有所改善.在這20次隨機部署中，并不是每一次算法后效果都如圖5(c)所示，如何能夠更加穩(wěn)定地發(fā)揮VFA-PSO算法優(yōu)化效果將是下一步工作的重點，這可能與VFA、PSO參數(shù)有關(guān)，只有經(jīng)過大量的實驗總結(jié)才能找到最佳網(wǎng)絡(luò)參數(shù).

圖5 3個隨機障礙物下算法節(jié)點分布對比圖Fig.5 Contrast deployment after algorithm by three obstacles

5.2.2 算法收斂效果分析

本文以3個障礙物環(huán)境下的20次初始預(yù)估覆蓋率60%的隨機分布的網(wǎng)絡(luò)有效覆蓋率CE優(yōu)化為分析藍本，VFA、VFA-PSO以50次循環(huán)迭代為一次算法周期，并將20次隨機分布下算法相同迭代次數(shù)下的CE平均值作為觀察對象，這樣可以相對減少算法發(fā)揮的不穩(wěn)定性，圖6可以看出，VFA-PSO算法迭代到30次附近，CE沒有明顯變化趨于穩(wěn)定，VFA迭代到50次，CE趨于穩(wěn)定，整體來看，VFA-PSO的收斂速度更快，迭代幾乎是VFA算法的一半.

圖6 算法收斂對比圖Fig.6 Convergence contrast diagram of algorithm

5.2.3 不同網(wǎng)絡(luò)參數(shù)對算法性能的影響

本文主要討論節(jié)點數(shù)量n和感知半徑Rs對網(wǎng)絡(luò)優(yōu)化的影響.增加一定數(shù)量的節(jié)點，某種程度上可以提高網(wǎng)絡(luò)有效覆蓋率CE，但同時增加開銷，用最少的節(jié)點達到最大的CE是算法優(yōu)化的方向之一.

表3 兩種算法隨節(jié)點數(shù)量變化CE(%)比較表Table 3 Comparisons of CE(%)with the number of nodes

表3 是以3個隨機障礙物下的節(jié)點數(shù)量對CE的影響，結(jié)合圖6觀察可以看出，初始預(yù)估覆蓋率設(shè)定為60%，但實際做實驗仿真下3個障礙物下20次隨機部署下的初始覆蓋率是51.12%，節(jié)點數(shù)量為100個時，經(jīng)過兩種算法覆蓋率分別比初始隨機部署下提升11.2%和22.05%，同樣情況150個節(jié)點的初始隨機覆蓋率是64.44%，經(jīng)過兩種算法覆蓋率分別提升4.5%和11.69%，可見隨著節(jié)點數(shù)量的增加，并不能使CE有明顯提高，而且增加網(wǎng)絡(luò)開銷，因此節(jié)點數(shù)量的確定還要綜合項目成本，達到均衡.

圖7為感知半徑對算法的影響，Rs太小或太大對CE的提高改善都不明顯，太小容易產(chǎn)生覆蓋盲區(qū)，太大又容易產(chǎn)生覆蓋重疊，圖7可以觀察在監(jiān)測范圍內(nèi)，當節(jié)點半徑為10m和12m時，對網(wǎng)絡(luò)有效覆蓋率的提升最高，這是圖5-圖7及表3的數(shù)據(jù)都是在Rs=12m的基礎(chǔ)上進行的原因.

圖7 感知半徑影響Fig.7 Perception radius effect

6 結(jié)束語

本文研究了在隨機障礙物下的有向傳感器網(wǎng)絡(luò)中，如何應(yīng)用虛擬力算法和粒子群算法來有效改善網(wǎng)絡(luò)避障效果差及覆蓋重疊區(qū)空洞區(qū)等問題.單獨的虛擬力算法對網(wǎng)絡(luò)有一定的改善作用，但易出現(xiàn)障礙物附近覆蓋空洞效應(yīng).將節(jié)點抽象成粒子模型來弱化虛擬力算法的局部極值效應(yīng)，從仿真實驗可以看出將虛擬力算法和粒子群算法融合后的算法對覆蓋率效果明顯，提高將近20%，收斂速度也更快.后續(xù)將從以下兩方面繼續(xù)深入研究：

1)涉及到虛擬斥力、引力參數(shù)、運動比例參數(shù)、學(xué)習(xí)因子等很多參數(shù)選定對算法至關(guān)重要，本論文中的參數(shù)是在參考了大量文獻的基礎(chǔ)上，在實驗中不斷測試取效果最佳情況下的值，后續(xù)將深入對算法參數(shù)等方面的研究；

2)本文算法并未分析算法能耗，而這對于能量受限的傳感網(wǎng)絡(luò)非常重要，后續(xù)將結(jié)合真實節(jié)點實驗完善能耗研究.