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

陳　瑩, 曹立志

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

?

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

陳瑩, 曹立志

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

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

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

0引言

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

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

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

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

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

1系統模型

1.1網絡模型

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

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

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

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

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

1.2感知模型

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

1.3重復感知區域網格模型

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

(1)

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

圖2　感知模型

圖3　重復感知網格模型

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

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

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

(2)

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

圖4　重復感知區域面積的計算

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

(3)

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

(4)

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

2.1虛擬勢場及傳統虛擬力模型

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

根據傳統的虛擬力模型,節點vi受到鄰居節點vj的虛擬力為

(5)

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

2.2學習自動機簡介

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

圖5　LA與環境關系模型

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

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

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

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

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

3.1.1改進的虛擬力模型

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

(6)

節點vi所受的虛擬力合力為

(7)

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

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

3.1.2轉動角度的計算

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

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

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

1) 在切向方向上

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

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

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

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

(8)

2) 在向心方向上

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

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

因此向心力定義為

由物理學圓周運動知識得

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

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

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

(10)

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

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

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

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

(11)

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

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

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

3.1.3改進算法描述

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

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

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

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

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

(4) 計算監測區域初始覆蓋率Vinit。

(5) 計算節點vi鄰居節點集合N(vi),及鄰居節點數目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≥ε,則根據下述規則進行節點角度和位置調整。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(12)

(13)

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

(14)

(15)

其中

(16)

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

4仿真實驗與結果分析

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

表1　網絡環境及參數

4.1實例效果

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

4.2收斂效果分析

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

圖7　網絡覆蓋的實例效果

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

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

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

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

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

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

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

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

4.3網絡參數分析

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

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

圖9　節點規模N的影響,R=60 m, 2α=90

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

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

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

5結論

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

參考文獻：

[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

網絡優先出版地址：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；網絡優先出版日期：2014-11-20。