隨機障礙物下的有向傳感器網絡覆蓋優化算法

關志艷，黃向生

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

1 引 言

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

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

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

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

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

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

2 DSN分析

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

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

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

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

(1)

表1 有向扇形5分區關系表Table 1 Directed sector 5 partition relation table

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

2.2 障礙物下的有效覆蓋率

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

(2)

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

(3)

3 障礙物虛擬力分析

3.1 問題描述

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

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

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

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

3.2 鄰居節點虛擬力分析

(4)

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

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

3.3 障礙物與節點間斥力分析

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

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

(5)

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

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

3.4 虛擬合力分析

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

(6)

3.5 轉動角度計算

從動力學角度分析，可知節點轉動角度由向心分量Fi′和切線分量Fi″共同決定,假設在Δt時間內Fi′、Fi″不變.

3.5.1 切線方向

(7)

3.5.2 向心方向

本文分析的節點所受虛擬力由物理學圓周運動可知‖Fi″‖=γ·vt2·Rs,vt為向心力提供的角速度.

(8)

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

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

(9)

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

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

2)設置最大循環次數Hmax

for loop=1:Hmax

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

{forj=1:n

{計算節點i,j的圓心距離Dij和質心距離dij；

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

{建立節點的鄰居節點質心距離dij矩陣;

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

}

}

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

{計算diOj；

if(diOj<2RS)

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

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

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

}

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

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

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

4.1 粒子群模型

本文將DSN中的大量有向傳感器節點簡化為平面內沒有質量且允許旋轉的粒子，粒子據適度值函數來衡量粒子位置優劣，粒子旋轉角速度和角度受自身旋轉經驗和鄰居粒子的旋轉經驗來進行綜合調整[19，20]，每次迭代中，粒子據式(10)更新角速度和感知方向水平夾角.

(10)

(11)

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

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

(12)

(13)

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

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

1)初始化網絡粒子規模n，學習因子a1、a2、b1、b2，虛擬力影響加速因子av、bv，最大迭代次數tmax；

3)fork=1:tmax

{fori=1:n

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

if(CEK+1>CEK)

}

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

5 算法仿真與性能分析

5.1 實驗參數設定

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

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

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

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

實驗涉及到的參數如表2所示.

表2 參數列表Table 2 List of parameters

5.2 實例效果

5.2.1 算法適度值優化效果比較

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

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

5.2.2 算法收斂效果分析

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

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

5.2.3 不同網絡參數對算法性能的影響

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

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

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

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

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

6 結束語

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

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

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