陳　瑩, 曹立志

(江南大學輕工控制教育部重點實驗室, 江蘇 無錫 214122)

?

基于虛擬勢場和學習自動機的有向傳感網覆蓋控制

陳瑩, 曹立志

(江南大學輕工控制教育部重點實驗室, 江蘇 無錫 214122)

摘要：針對目前有向傳感網中覆蓋增強和冗余節(jié)點休眠調度算法存在的問題,提出虛擬勢場結合學習自動機的覆蓋控制算法。引入基于質心距離和重復感知率的虛擬力改進模型,綜合考慮虛擬向心力和切向力對感知角度調整的影響,建立微觀虛擬力與轉動角度的關系模型,并根據網絡整體覆蓋率增長率對節(jié)點調整幅度進行宏觀控制,合理調整節(jié)點感知方向。在此基礎上,根據節(jié)點重復感知率和能量因素建立學習自動機與環(huán)境信息的交互機制,學習最優(yōu)的冗余節(jié)點休眠調度策略。仿真實驗結果表明,該算法能夠顯著增強網絡覆蓋,并有效地控制網絡覆蓋冗余。

關鍵詞：有向傳感器網絡; 虛擬勢場; 學習自動機; 覆蓋增強; 節(jié)點休眠調度

0引言

隨著人們對細粒度、精準信息的環(huán)境監(jiān)測應用的迫切需求,由大量有向監(jiān)測周圍環(huán)境,且數(shù)據信息量較大的多媒體傳感器組成的無線多媒體傳感器網絡(wireless multimedia sensor networks, WMSNs)已越來越受到人們的關注,并被廣泛應用于軍事偵察、環(huán)境監(jiān)測、醫(yī)療護理和交通管理等軍事和民用領域[1]。由于傳感器節(jié)點通常具有電源能量低、二次補充能量難、信息采集能耗大的缺點,因此無線多媒體傳感器網絡存在嚴重的能量約束問題。覆蓋控制是該網絡的一個基礎問題,反映著網絡所能提供的“感知”服務質量[2]。 而傳統(tǒng)基于全向覆蓋模型的覆蓋控制算法無法直接應用于有向的多媒體傳感器網絡中,因此設計一種合理的有向傳感覆蓋控制算法以增強網絡覆蓋并有效利用網絡能量,從而實現(xiàn)網絡高效長期覆蓋是WMSNs需要解決的突出問題。

文獻[3]根據有向傳感器特點設計了一種2-D有向感知模型,并首次應用于有向傳感器網絡中。在此模型的基礎上,國內外展開了大量針對無線多媒體傳感器網絡覆蓋的研究工作[4-5]。其中,虛擬勢場(potential force,PF)方法可以有效地調整有向傳感網節(jié)點的感知方向,已廣泛應用于多媒體傳感器網絡覆蓋增強問題。文獻[6]首次將虛擬勢場應用于有向傳感器網絡中,提出基于虛擬勢場的覆蓋增強算法(potential field based coverage-enhancing algorithm, PFCEA),創(chuàng)新性的引入感知“質心”概念,根據質心點受虛擬斥力進行擴散運動,進而調整各節(jié)點感知方向,將覆蓋控制問題轉化為質心點均勻分布問題,以達到去除覆蓋重疊區(qū)和盲區(qū),增強網絡覆蓋的目的。但該算法采用固定轉動調整角度限制了覆蓋優(yōu)化的效果和收斂速度,并且僅采用歐氏距離參數(shù)并不能細致的描述具有重復感知區(qū)域的網絡節(jié)點受力情況。其后的改進工作大多從這2方面展開。文獻[7]采用配對的切點排斥機制(paired tangent point repulsion mechanism,PTPRM),建立了角度調整量、合力與感知方向夾角這兩者的函數(shù)模型。但其僅考慮最近2個節(jié)點的斥力作用,并沒有充分考慮其余鄰居節(jié)點的影響,因此限制了其覆蓋提升效果。文獻[8]則根據切向分力的大小調整每次轉動角度。文獻[9]提出了基于虛擬向心力模型的覆蓋增強算法(virtual centripetal force-based coverage enhancing algorithm, VCFCEA),通過建立感知區(qū)域網格模型,將感知重疊網格數(shù)引入虛擬力計算公式,并且建立了向心力與調整角度的關系模型,根據向心力大小調整轉動角度,但由于不同位置網格的面積不盡相同,因此采用網格數(shù)目參數(shù)無法得到精確的虛擬力,從而影響進一步通過虛擬力調整感知角度。這類單獨考慮切向力或向心力作用的模型,并不能全面細致的描述節(jié)點受力調整規(guī)律,在某些特殊情況,如文獻[7]中算法在圖1(a)情況、文獻[8]在圖1(b)情況下,節(jié)點甚至無法調整感知方向。

圖1　基于切向力、向心力的轉動角度模型無法調整角度的情況

另一方面,能量問題一直是無線多媒體傳感器網絡需要解決的突出問題[10],文獻[11]根據節(jié)點當前能量值關閉網絡節(jié)點,但僅考慮節(jié)點能量因素,仍無法解決網絡覆蓋冗余問題,因此實際提升效果并不明顯。文獻[9]根據節(jié)點的感知重復網格數(shù),同時關閉覆蓋重復率過高的節(jié)點以延長網絡覆蓋時間。但此類同一時間關閉節(jié)點的休眠調度算法在可能造成覆蓋同一區(qū)域的節(jié)點同時關閉,出現(xiàn)覆蓋盲區(qū)(coverage hole,CH)。針對這一問題,文獻[12]采用了基于重復覆蓋優(yōu)先級的策略,優(yōu)先關閉重復覆蓋優(yōu)先級高的節(jié)點,在一定程度上緩解了關閉冗余節(jié)點造成的覆蓋盲區(qū)問題,但關閉處于同一優(yōu)先級的節(jié)點時仍會存在上述問題。同時,作為新型的機器學習算法,學習自動機(learning automata, LA)主要解決具有感知環(huán)境能力的自治agent通過與環(huán)境交互,對其所選動作獎懲,自適應的學習到最優(yōu)動作策略。這一特性正適用于WMSNs中節(jié)點調度策略的選擇。目前已有文獻[13-14]將其應用于有向傳感網中,并取得較好的效果。

針對有向傳感器網絡覆蓋增強和能耗控制的應用,并綜合研究上述各文獻存在的問題,本文提出了一種基于虛擬勢場結合學習自動機的網絡覆蓋控制算法。首先,在根據節(jié)點距離和感知重復率建立的虛擬力模型的基礎上,綜合虛擬向心力和切向力對節(jié)點角度調整的影響,建立了虛擬力與轉動角度的關系模型,并根據網絡覆蓋率增長率對節(jié)點調整幅度做了進一步調整,從而更為合理的調整了節(jié)點感知方向。同時,采用基于學習自動機的增強學習機制,根據節(jié)點的感知冗余和能量情況,通過學習自動機與環(huán)境信息的交互和對選擇動作的獎懲,從而學習到最優(yōu)的休眠調度策略。

1系統(tǒng)模型

1.1網絡模型

所采用的網格模型具有以下特點。

(1) 網絡中所有節(jié)點同構,即所有節(jié)點具有相同的感知半徑和夾角等參數(shù)規(guī)格。

(2) 網絡節(jié)點具有固定的ID,且隨機部署,節(jié)點均勻分布在監(jiān)測區(qū)域。

(3) 網絡節(jié)點在部署后位置固定不變,但其感知方向可調。

(4) 網絡節(jié)點都了解自身位置及傳感方向信息,且對自身感知方向可控。

1.2感知模型

不同于普通傳感器的全向感知模型,無線多媒體傳感器通常具有受限的扇形感知區(qū)域。文獻[6]采用方向可調的2-D感知模型〈P,R,V(t),α〉。如圖2所示,其中P表示節(jié)點的位置坐標(x, y);R表示節(jié)點的感知半徑;單位向量V(t)沿著扇形感知區(qū)域的中軸線,表示節(jié)點在t時刻的感知方向;2α代表傳感區(qū)域視角(fieldofview,FOV)。Δφ表示節(jié)點轉動角度,centroid表示節(jié)點覆蓋區(qū)域的質心點,分布在感知區(qū)域的中軸線,與圓心距離為2R·sinα/(3α)。

1.3重復感知區(qū)域網格模型

WMSN的節(jié)點的扇形感知區(qū)域,造成其不規(guī)則的覆蓋重疊區(qū)域,與文獻[12]相同,論文采用如圖3所示的網格模型來計算這一區(qū)域:把感知區(qū)域分成M×N塊網格(本文設為10×10),即將感知半徑R和感知視角FOV分為M和N等份;從而位于第p行q列網格的面積為

(1)

由式(1)可知,網格的面積僅與其所在的列數(shù)q有關。

圖2　感知模型

圖3　重復感知網格模型

基于上述模型,本文定義如下變量。

(1) 鄰居節(jié)點:節(jié)點距離小于2R的兩節(jié)點互為鄰居節(jié)點。N(vi)表示節(jié)點vi的鄰居節(jié)點集合。

(2)OSAij:節(jié)點vi的感知區(qū)域被鄰居節(jié)點vj重復感知覆蓋的面積(overlap-sensearea,OSA),見圖4。即

(2)

式中,Cgijpq表示節(jié)點vi的感知區(qū)域內第p行q列網格是否被鄰居節(jié)點vj重復覆蓋:若該網格被覆蓋則Cgijpq=1；否則其值為0。

圖4　重復感知區(qū)域面積的計算

(3)OSRij:表示節(jié)點vi的感知區(qū)域被節(jié)點vj重復感知覆蓋區(qū)域與其感知區(qū)域的比率為

(3)

(4)OSRi:表示節(jié)點vi的感知區(qū)域內被其鄰居節(jié)點N(vi)重復感知的總面積占其感知區(qū)域的比例為

(4)

2虛擬勢場與學習自動機簡介

2.1虛擬勢場及傳統(tǒng)虛擬力模型

虛擬勢場的概念借鑒了物理學電磁場模型。其基本思想是把網絡中每個節(jié)點感知范圍的質心看做一個虛擬電荷,每個質心點都在其鄰居質心點的虛擬斥力作用下作擴散運動,并在運動學和動力學的雙重約束下趨于平衡,即采用質心點的圓周運動替代節(jié)點感知角度的轉動調整,從而將基于虛擬勢場的有向傳感器網絡覆蓋增強問題抽象為節(jié)點質心點之間通過虛擬斥力作用達到質心點均勻分布問題[4]。

根據傳統(tǒng)的虛擬力模型,節(jié)點vi受到鄰居節(jié)點vj的虛擬力為

(5)

式中,kR為斥力常數(shù)；rij為單位向量;方向由質心點cj指向質心點ci；rij表示質心點間的歐氏距離。

2.2學習自動機簡介

學習自動機是一種基于增強學習并在未知的隨機環(huán)境中完成自適應決策的智能單元[15],LA的學習過程實質上是與隨機環(huán)境的一組互動:如圖5所示,首先LA從其動作集α中選擇一個動作αi,并輸入到隨機環(huán)境中;然后,隨機環(huán)境對該動作進行評估并向自動機反饋一個反映獎勵或懲罰響應的增強信號βi；最后,基于這個增強信號和選擇的動作,LA根據相應的學習算法T()更新動作選擇概率集并依據其進行下一輪動作選擇。通過有限次的交互迭代過程,LA逐漸學習到最佳動作。

圖5　LA與環(huán)境關系模型

3基于虛擬勢場與學習自動機的網絡覆蓋控制算法

本文主要解決網絡覆蓋增強和冗余節(jié)點的關閉2方面問題:先采用基于虛擬勢場的覆蓋增強改進算法提高網絡的覆蓋率;然后,采用基于學習自動機的節(jié)點休眠調度算法學習到合理的關閉冗余節(jié)點的優(yōu)化策略,從而達到提升網絡覆蓋率并且高效利用網絡能量的目的。

3.1基于虛擬勢場的覆蓋增強改進算法

虛擬勢場算法通過相鄰傳感器質心點之間的虛擬斥力調整節(jié)點的感知方向,達到網絡覆蓋增強的效果。但傳統(tǒng)算法存在2方面問題:首先,虛擬力模型僅考慮質心點的距離參數(shù),而沒有考慮節(jié)點間冗余覆蓋對虛擬力的影響,使得不同重復覆蓋率的節(jié)點調整幅度相同。另一方面,傳統(tǒng)算法采用固定的轉動角度調整影響了覆蓋優(yōu)化的收斂速度和精度,這表現(xiàn)在當該轉動角度值設置較小時,將會減緩網絡覆蓋收斂速度,限制了算法的執(zhí)行效率;而當轉動角度值較大時,則會降低網絡調整精度,甚至造成網絡遲遲不能進入穩(wěn)定狀態(tài)。同時，還應根據網絡整體覆蓋情況動態(tài)調整角度:在網絡調整初期,需要增大轉動角度以迅速提升網絡覆蓋率;而在網絡覆蓋趨于收斂時,則需降低節(jié)點轉動角度以實現(xiàn)快速收斂并增強覆蓋精度。

基于以上2個問題,本文在引入考慮節(jié)點重復覆蓋率的虛擬力改進模型的基礎上,根據相鄰節(jié)點間的虛擬力大小調整節(jié)點的感知方向;同時,結合網絡覆蓋增長率進一步調整轉動角度,因而從微觀(虛擬力)、整體(網絡覆蓋率)2個方面共同調整節(jié)點感知方向。

3.1.1改進的虛擬力模型

本文綜合考慮節(jié)點間距離和重復覆蓋的情況,在僅考慮質心距離的傳統(tǒng)虛擬力模型(式(5))的基礎上,根據相鄰節(jié)點重復覆蓋率大小進一步調整虛擬力,其定義如下:

(6)

節(jié)點vi所受的虛擬力合力為

(7)

式中,kR, rij,r0ij,N(i)與傳統(tǒng)虛擬勢場算法定義相同,OSRij表示節(jié)點間的重復覆蓋率。

從式(6)可以看出當2個節(jié)點重復覆蓋率較大時,其虛擬力也應相應增大,有利于提高了角度調整的幅度,加快了網絡覆蓋調整速度。并且不同于文獻[9],本文虛擬力模型采用基于面積的網絡重復覆蓋率取代重復覆蓋的網格數(shù)目,從而可以為進一步調整感知角度提供更為準確的虛擬力數(shù)值。

3.1.2轉動角度的計算

本文主要從微觀虛擬力和網絡整體覆蓋增長率2個方面對轉動角度進行調整。

(1) 基于虛擬力調整轉動角度

從動力學角度分析,節(jié)點轉動角度由虛擬力F的向心分力Fc提供的角速度wc和切向分力Ft提供的線加速度αt共同決定。本文假設在Δt時間內,Fc和Ft保持不變。

1) 在切向方向上

由動力學可知,切向力提供切向加速度,即

式中，km為比例系數(shù);θ為合力方向與向心方向的夾角;αt為切向加速度。

由運動學可知,加速度αt在Δt時間內轉過弧長為

故切向力提供的角度變化為

(8)

2) 在向心方向上

當θ∈[0,90°]時,合力的向心分量指向節(jié)點,表現(xiàn)為向心力,大小為‖F(xiàn)‖·cosθ。

當θ∈[90°,180°]時,虛擬力的向心分量背離節(jié)點,但質心并未做離心運動,因此設定該離心方向力與系統(tǒng)保持圓周運動所提供的力抵消,大小為0。

因此向心力定義為

由物理學圓周運動知識得

從而向心力提供的角度變化為

為了簡化計算,本文設定相應閾值對合力歸一化處理;在式(8)和式(9)中,由于Δt,km,R均為常數(shù),從而令knorm=(Δt)2/(km·R)為歸一化系數(shù),歸一化合力定義為Fnorm=min(Knorm·F, 1)。

綜合式(8)和式(9),根據虛擬力的轉動角度調整為

(10)

式中，kφ為角度調整系數(shù),由式(10)可知,轉動角度ΔφF僅與虛擬力Fnorm和夾角θ的取值有關,其關系模型如圖6所示,其中轉動角度ΔφF隨虛擬力Fnorm的遞增而逐漸增大,且轉動角度ΔφF隨著夾角θ的變化反映了切向力和向心力對轉動角度不同的影響關系。

圖6　轉動角度與歸一化虛擬力與夾角θ的關系模型

(2) 根據網絡覆蓋的增長率的模型

轉動角度除了受微觀虛擬力決定之外,還應從宏觀上根據網絡整體覆蓋增長率動態(tài)調整:在覆蓋增長率較大時(如網絡調整初期),需要增大轉動角度以迅速提升網絡覆蓋率;而在網絡覆蓋趨于收斂時,此時覆蓋增長率較小,則需要降低節(jié)點轉動角度以實現(xiàn)快速收斂并提高覆蓋效果。從而進一步調整節(jié)點轉動角度如下:

(11)

式中,ΔφF如式(10)所示；θmax為轉動角度的上限值；θmin為轉動角度的下限值;Vp為網絡覆蓋增長率；Vinit為網絡初始覆蓋率。

根據對算法的反復實現(xiàn)和分析,節(jié)點在初始的10次調整過程覆蓋增長變化較快,因此在此過程設定轉動角度取較大的轉動角度;而在覆蓋增長率較低時(遠低于平均),近似認為此時節(jié)點進入穩(wěn)定狀態(tài)調整過程,因此需要降低角度調整的幅度;從而在提高網絡覆蓋調整效率的同時,進一步提升了網絡覆蓋效果。

本文節(jié)點調整方向為:當切向力方向大于0時,此時節(jié)點沿著切向力方向旋轉Δφi角度;而當切向力方向為0時,則規(guī)定節(jié)點沿著順時針方向調整Δφi角度。

3.1.3改進算法描述

算法輸入:節(jié)點vi及其鄰居節(jié)點的位置和感知方向。

算法輸出:節(jié)點vi的最終感知方向，具體算法描述如下。

(1) 初始化計數(shù)步長t←0。

(2) 初始化各節(jié)點停止調整標志flag(i)←0。

(3) 計算節(jié)點vi對應的質心ci初始位置Pci(t)。

(4) 計算監(jiān)測區(qū)域初始覆蓋率Vinit。

(5) 計算節(jié)點vi鄰居節(jié)點集合N(vi),及鄰居節(jié)點數(shù)目M。

(6) 令t←t+1,Fi(t)←0,計算當前網絡覆蓋率和覆蓋增長率Vp,并根據式(6)計算質心點cj對ci的虛擬斥力Fij(t),其中vj∈N(vi)。

(7) 計算Fi(t)←Fi(t)+Fij(t),將Fi(t)帶入式(10),計算出虛擬力調整的旋轉角度ΔφF。若 ΔφF≥ε,則根據下述規(guī)則進行節(jié)點角度和位置調整。

1) 根據式(11)調整節(jié)點轉動角度Δφi。

2) 質心點ci沿規(guī)定方向轉動角度Δφi。

3) 調整質心點ci到新位置Pci(t)。

4) 計算節(jié)點vi指向當前質心點ci向量并單位化,從而得到傳感方向V(t)。

(8) 返回描述(6),直至算法收斂。

3.2基于學習自動機的節(jié)點休眠調度算法

通過上述網絡節(jié)點感知方向調整后,網絡覆蓋得到了顯著的增強(如圖7(c)),但網絡中仍存在覆蓋冗余節(jié)點,并且隨著部署節(jié)點數(shù)目的增加,覆蓋冗余問題也越嚴重。而針對網絡冗余覆蓋存在2個相互矛盾的問題,即關閉冗余節(jié)點可以有效提高能量利用效率,延長網絡存活時間;但同時也會造成網絡覆蓋率會在一定程度降低。傳統(tǒng)算法采用在同一時間關閉所有覆蓋率高的節(jié)點,雖然可以降低網絡覆蓋冗余,容易造成網絡中覆蓋同一區(qū)域的節(jié)點同時關閉,出現(xiàn)網絡覆蓋盲區(qū)問題(如圖7(b))。

為了解決這一問題,本文采用基于學習自動機的節(jié)點休眠調度方法,針對覆蓋重復率高于一定閾值OSRthr的特定節(jié)點,根據其覆蓋區(qū)域內的重復覆蓋率和自身能量,通過其學習自動機與鄰居節(jié)點進行覆蓋信息的交互和動作概率的獎懲,從而網絡選擇出最優(yōu)動作策略。基本過程如下:

(1) 在初始階段,節(jié)點si中的學習自動機從其動作集(工作(a0)或休眠(a1))中隨機的選擇一個動作,并向周圍鄰居節(jié)點發(fā)送內容為是否為特定節(jié)點,選擇動作、感知范圍、自身能量等信息的廣播包,從而網絡中的特定節(jié)點都建立了周圍鄰居的信息表。

(2) 接著,在以后各輪動作選擇過程中,節(jié)點si以接受到的鄰居節(jié)點信息作為隨機環(huán)境,計算出相應的獎懲性反饋信號βi反饋到節(jié)點si。其中βi定義如下。

1) 當si選擇的動作為工作時

當節(jié)點感知區(qū)域被工作的鄰居節(jié)點重復覆蓋超過特定閾值時,環(huán)境懲罰這一動作,βi=1;否則,環(huán)境獎勵這一動作,返回信號βi=0。

2) 當si選擇的動作為關閉時

當節(jié)點的感知區(qū)域被工作的鄰居節(jié)點重復覆蓋超過特定閾值時,環(huán)境獎勵這一動作,βi=1;否則,環(huán)境懲罰這一動作,返回信號βi=0。

(3)最后,根據環(huán)境的反饋信號βi,學習自動機采用不同學習算法更新下一輪動作概率。

(12)

(13)

式中,式(12)、式(13)分別表示有利響應和不利響應下動作更新概率的表達式；a(n)，b(n)分別是獎勵和懲罰函數(shù),且隨迭代次數(shù)n而時變,其定義如下:

(14)

(15)

其中

(16)

網絡節(jié)點調度學習過程的終止條件為:網絡學習過程次數(shù)超過特定的次數(shù)MAX_ITERATION; 特定的節(jié)點都確定自身狀態(tài)(休眠或工作)。特定網絡節(jié)點選擇休眠狀態(tài)條件為其選擇休眠動作概率超過特定的閾值,否則節(jié)點則選擇處于工作狀態(tài)的動作。

4仿真實驗與結果分析

本文采用Matlab進行仿真實驗。為了評估網絡覆蓋提升效率和冗余節(jié)點休眠調度情況。本文首先通過一個實例直觀的展示算法的運行效果,然后分別對節(jié)點覆蓋增強和冗余節(jié)點控制2個算法的收斂效果進行驗證;最后,針對不同參數(shù)的網絡,將本文算法與VCFCEA在網絡覆蓋增強和冗余節(jié)點關閉2方面進行性能比較和分析。實驗涉及到的其余參數(shù)值如表1所示,其中φ, ρ參數(shù)值為實驗經驗值。

表1　網絡環(huán)境及參數(shù)

4.1實例效果

首先,在500×500 m2的目標區(qū)域內隨機部署200個傳感半徑R=60 m,感知視角2α=90°的節(jié)點,如圖7(a)所示,此時網絡初始覆蓋率為 86.37%,并且存在著大量的覆蓋冗余。圖7(b)為同一時間關閉覆蓋冗余度較高的節(jié)點,雖然降低了網絡覆蓋冗余;但由于關閉較多有效覆蓋節(jié)點(工作節(jié)點數(shù)為113),造成大量的覆蓋盲區(qū),大大降低了網絡的覆蓋率(77.92%)。圖7(c)表示經過本文基于虛擬勢場的網絡節(jié)點調整,在第27輪網絡達到穩(wěn)定,其覆蓋率為 96.28%,但網絡仍存在覆蓋冗余節(jié)點。圖7(d)表示經過本文基于學習自動機的節(jié)點休眠調度策略后網絡覆蓋情況,可以看出網絡冗余覆蓋率得到顯著的降低,但由于保留大量有效覆蓋節(jié)點(工作節(jié)點數(shù)為137),網絡整體覆蓋率無太大影響,仍保持在 95.83%。

4.2收斂效果分析

本文分別考慮改進的虛擬勢場算法和學習自動機節(jié)點調度算法的收斂性。

圖7　網絡覆蓋的實例效果

(1) 改進的虛擬勢場算法

由于文獻[6]已經對虛擬勢場算法的收斂性進行過驗證,本部分主要從收斂速度兼顧覆蓋效果2方面將本文算法與PFCEA、VCFCEA中虛擬勢場算法進行比較,節(jié)點的傳感半徑R=50 m其余實驗參數(shù)與相同。

從圖8可以看出, PFCEA、VCFCEA和本文改進的虛擬勢場收斂次數(shù)分別為25、31和37,并且在覆蓋率方面本文算法也優(yōu)于PFCEA、VCFCEA算法。本文算法和VCFCEA在這2方面優(yōu)于PFCEA的原因是:前2種算法均采用考慮網絡覆蓋的虛擬力模型,根據虛擬力動態(tài)調整節(jié)點轉動角度,因此在收斂速度和覆蓋率方面相對PFCEA都有提升。同時,本文算法優(yōu)于VCFCEA是因為本文采用了改進的虛擬力覆蓋模型,并綜合考慮虛擬力的向心和切向分力對轉動角度的作用,進一步結合網絡覆蓋率變化對轉動角度調整,從而提高網絡覆蓋率的同時,加快了網絡收斂速度。并且從圖8中可以看出,由于本文算法根據網絡覆蓋率變化自適應調整轉動角度,因此在覆蓋初期網絡可以快速調整,并且在覆蓋收斂時網絡調整的幅度也相應降低,有利于網絡快速達到穩(wěn)定狀態(tài)。

圖8　PFCEA、VCFCEA和本文中虛擬勢場算法比較

(2) 基于學習自動機的節(jié)點休眠調度算法

為了討論該算法的收斂性,本文針對4種不同節(jié)點規(guī)模的網絡(100, 150, 200, 250,300)分別隨機生成網絡拓撲,首先采用基于虛擬勢場的節(jié)點感知方向調整算法得到調整后的網絡覆蓋率p0,在其基礎上采用本文節(jié)點休眠調度算法得到網絡最終覆蓋率p1，每種網絡分別執(zhí)行50次,并統(tǒng)計對應的收斂次數(shù)平均值。實驗結果如表2所示。

表2　基于學習自動機的節(jié)點休眠調度算法收斂性分析

由表2可知,基于學習自動機的節(jié)點調度算法在各種規(guī)模網絡的收斂次數(shù)一般維持在20次左右，而在近于飽和的網絡中(如網絡節(jié)點為300),學習迭代次數(shù)也只有27次,因此該算法具有良好的收斂性。同時,經過節(jié)點休眠調度后各的網絡覆蓋率也沒有受到明顯的影響(僅降低0.01左右)。需要注意的是:本文采用學習自動機學習休眠控制策略看似增加了算法的復雜度,但一方面,僅有部分特定節(jié)點參與學習過程;另一方面，學習自動機中算法相對于虛擬力調整過程的運算復雜度較低,從而并不影響算法高效執(zhí)行。 因此這種算法可以在有限次學習過程內完成冗余節(jié)點的休眠調度控制,并緩解了關閉冗余節(jié)點帶來的網絡覆蓋盲區(qū)問題。

4.3網絡參數(shù)分析

本節(jié)主要討論網絡中3個主要參數(shù)對本文算法性能的影響,其分別為:網絡節(jié)點規(guī)模N、節(jié)點感知半徑R和感知視角2α。針對這3個參數(shù),本節(jié)將本文算法和VCFCEA算法在網絡覆蓋增強和關閉冗余覆蓋情況進行綜合比較和分析。

圖9表示針對不同節(jié)點數(shù)目的網絡覆蓋率和冗余節(jié)點關閉數(shù)目。從圖9(a)中可以看出,2種算法網絡節(jié)點數(shù)較低時,網絡初始覆蓋率較低,并且經節(jié)點感知角度調整后覆蓋冗余也較小,因此關閉的節(jié)點較少。在網絡節(jié)點數(shù)超過100時,本文算法的網絡覆蓋率較VCFCEA有了顯著提升，并且隨著節(jié)點數(shù)目增多,網絡覆蓋提升差值Δp呈逐漸增大趨勢,當節(jié)點數(shù)目為150時,該值達到最大。此后隨著節(jié)點數(shù)目進一步增多,2種算法都保持在較高的覆蓋率,而本文算法的網絡覆蓋率始終領先于VCFCEA。同時,隨著網絡節(jié)點的增加,網絡中關閉的重復冗余覆蓋節(jié)點也不斷增加。需要注意的是:本文算法關閉的網絡節(jié)點數(shù)目始終低于VCFCEA,這是由于VCFCEA在同一時間關閉所有覆蓋冗余度高的節(jié)點,因此關閉了更多節(jié)點,但這樣容易產生網絡覆蓋盲點,造成網絡覆蓋率降低(如圖9(a))。本文則采用學習自動機,通過相鄰節(jié)點間交互信息,不斷對所選動作進行獎懲,從而逐漸選擇更為合理的節(jié)點調度策略,緩解覆蓋盲點問題的同時保留更多有效節(jié)點,提升了網絡覆蓋率。綜合圖9(a)和圖9(b)可以看出,不論稀或疏密集的網絡,本文算法都能取得更高的覆蓋率和更優(yōu)的網絡節(jié)點休眠調度策略。

圖9　節(jié)點規(guī)模N的影響,R=60 m, 2α=90

圖10和圖11分別表示在不同感知半徑、感知視角2個參數(shù)下算法的實際效果,從圖中不難看出這2個參數(shù)具有和節(jié)點數(shù)目類似對算法的影響效果。當感知半徑或感知視角逐漸增大時, 2種算法的網絡覆蓋率均得到提升,并且本文算法相對于VCFCEA網絡覆蓋增強幅度更大,而當網絡參數(shù)增大到一定值時,網絡覆蓋率維持在較高的覆蓋率。在此過程中,網絡中休眠節(jié)點也在不斷增加,本文算法能夠更為合理的關閉冗余節(jié)點,使得網絡有更多有效節(jié)點用以感知環(huán)境信息提高覆蓋質量。

圖10　感知視角2α的影響, R=60 m, N=200

圖11　傳感半徑R的影響, N=200, 2α=90°

5結論

針對傳統(tǒng)虛擬勢場方法采用固定角度調整感知方向的問題,本文采用基于距離和網絡重復覆蓋率的虛擬力改進模型,根據虛擬力的向心和切向分力綜合控制感知方向的改變,并根據網絡覆蓋率變化速率進一步調整節(jié)點的轉動角度,從而達到自適應調整網絡節(jié)點感知方向的目的。針對同時關閉冗余節(jié)點造成的網絡覆蓋盲點問題,本文引入學習自動機,根據其與周圍環(huán)境的交互、自身動作的獎懲等增強學習機制,經過有限次學習過程學習到更為合理的冗余節(jié)點調度策略。仿真實驗表明,相對于PFCEA、VCFCEA算法,本文能夠高效的提升網絡覆蓋率和覆蓋調整速度,并學習到更為合理的冗余節(jié)點休眠調度策略,從而實現(xiàn)了增強網絡覆蓋的同時均衡能耗的目的。

參考文獻：

[1] Akyildiz I F, Melodia T, Chowdury K R. Wireless multimedia sensor networks:a survey[J].IEEEWirelessCommunications, 2007, 14(6):32-39.

[2] Ren Y, Zhang S D, Zhang H K. Theories and algorithms of coverage control for wireless sensor networks[J].JournalofSoftware, 2006, 17(3):422-433.(任彥, 張思東, 張宏科. 無線傳感器網絡中覆蓋控制理論與算法[J].軟件學報, 2006, 17(3):422-433.)

[3] Ai J, Abouzeid A A. Coverage by directional sensors in randomly deployed wireless sensor networks[J].JournalofCombinatorialOptimization, 2006, 11(1):21-41.

[4] Tao D, Ma H D. Coverage control algorithms for directional sensor networks[J].JournalofSoftware, 2011, 22(10):2317-2334.(陶丹, 馬華東. 有向傳感器網絡覆蓋控制算法[J]. 軟件學報, 2011, 22(10):2317-2334.)

[5] Guvensan M A, Yavuz A G. On coverage issues in directional sensor networks:a survey[J].AdHocNetworks, 2011, 9(7):1238-1255.

[6] Tao D, Ma H D, Liu L. A virtual potential field based coverage-enhancing algorithm for directional sensor networks[J].JournalofSoftware, 2007, 18(5):1152-1163.(陶丹, 馬華東. 基于虛擬勢場的有向傳感器網絡覆蓋增強算法[J]. 軟件學報, 2007, 18(5):1152-1163.)

[7] Huang H, Sun L, Wang R, et al. A novel coverage enhancement algorithm for image sensor networks[J].InternationalJournalofDistributedSensorNetworks, 2012,32(1):1-11.

[8] Huang S, Cheng L L. A low redundancy coverage-enhancing algorithm for directional sensor network based on fictitious force[J].ChineseJournalofSensorsandActuators, 2011, 24(3):418-422.(黃帥,程良倫. 一種基于虛擬力的有向傳感器網絡低冗余覆蓋增強算法[J]. 傳感技術學報, 2011, 24(3):418-422.)

[9] Zhao J, Zeng J C. A virtual centripetal force-based coverage-enhancing algorithm for wireless multi-media sensor networks[J].IEEESensorsJournal, 2010, 10(8):1328-1334.

[10] Akyildiz I F, Melodia T, Chowdhury K R. Wireless multimedia sensor networks:applications and testbeds[J].ProceedingsoftheIEEE, 2008, 96(10):1588-1605.

[11] Pescaru D, Istin C, Curiac D, et al. Energy saving strategy for video-based wireless sensor networks under field coverage preservation[C]∥ProcoftheIEEEInternationalConferenceonAutomation,QualityandTesting, 2008:289-294.

[12] Chen J, Zhang L, Kuo Y H. Coverage-enhancing algorithm based on overlap-sense ratio in wireless multimedia sensor networks[J].IEEESensorsJournal, 2013, 13(6):2077-2083.

[13] Mohamadi H, Ismail A S, Salleh S, et al. Learning automata-based algorithms for solving the target coverage problem in directional sensor networks[J].WirelessPersonalCommunications, 2013, 73(3):1309-1330.

[14] Mohamadi H, Ismail A S, Salleh S. Utilizing distributed learning automata to solve the connected target coverage problem in directional sensor networks[J].SensorsandActuatorsA:Physical, 2013, 198(1):21-30.

[15] Nicopolitidis P, Papadimitriou G I, Pomportsis A S, et al. Adaptive wireless networks using learning automata[J].IEEEWirelessCommunications, 2011, 18(2):75-81.

陳瑩(1976-),女,副教授,博士,主要研究方向為多媒體傳感器網絡、計算機視覺。

E-mail:chenying@jiangnan.edu.cn

曹立志(1987-),男,碩士研究生,主要研究方向為無線傳感器網絡。

E-mail:coleadge@qq.com

網絡優(yōu)先出版地址：http://www.cnki.net/kcms/detail/11.2422.TN.20141120.1831.003.html

Virtual potential field and learning automata based coverage control

algorithm for directional sensor networks

CHEN Ying, CAO Li-zhi

(KeyLaboratoryofAdvancedProcessControlforLightIndustry,MinistryofEducation,

JiangnanUniversity,Wuxi214122,China)

Abstract:Aiming at solving the problems of network coverage enhancement and redundant node scheduling, a coverage control protocol based on virtual potential field and learning automata is presented. An improved virtual force model based on both the distance and the overlapping sensing rate is proposed, which considers the effect of virtual centripetal and tangential force on the perceived angle adjustment. By establishing the relational model between the micro virtual force and the rotational angle, the algorithm macroscopically controls the adjustment of the node angle according to the coverage rate of the overall network, and adjusts the node sensing direction reasonably. Furthermore, a coverage strategy based on learning automata(LA)is presented, in which the LAis designed for information exchange with the surrounding environment according to the overlapping sensing rate and energy level of nodes. It learns to choose the optimal scheduling scheme for redundant nodes in the network. Simulations show that the algorithm can significantly enhance the network coverage, and effectively control the network coverage redundancy.

Keywords:directional sensor network; virtual potential field; learning automata; coverage enhancement; node scheduling

作者簡介：

中圖分類號：TP 391

文獻標志碼：ADOI:10.3969/j.issn.1001-506X.2015.05.31

基金項目：國家自然科學基金(61104213)資助課題

收稿日期：2013-12-18；修回日期：2014-10-12；網絡優(yōu)先出版日期：2014-11-20。