基于QoS約束的感知網絡覆蓋研究

賈海云

(合肥財經職業學院,安徽 合肥 230601)

0 引言

工業生產各領域中傳感器相互協作形成的感知網絡的部署發揮了不可替代的作用。由于單一個體的傳感器在不同環境中的感知能力有限,要擴展整個感知網絡的感知范圍,提升全網感知能力使之具備服務質量(Quality of Service,QoS)級網絡服務能力,就必須科學規劃每一個傳感器的部署方位。這不僅有利于解決傳感器重復感知的問題,也有助于優化整個感知網絡的能效。因此,針對感知網絡中傳感器的方位部署問題,業界展開了一系列相關研究。GHOLAMI等[1]提出了高密度部署感知節點方案。感知節點被大量撒布在待檢目標附近以確保目標數據被穩定精確地廣播,然而該部署方案下的大量感知節點可能存在同時覆蓋感知某一個區域內的多個待測目標。這將導致感知網絡浪費大量能耗用于維持待測目標數據的冗余傳輸,同時網絡資源的過度開銷勢必弱化感知網絡的生存性和感知性能。并且成本也是一個制約該部署方案的瓶頸。GURUPRIYA等[2]提出了基于睡眠的感知節點部署方案,該方案根據感知節點差異化的感知性能為異構感知網絡設計了評估算法。算法通過評估待測目標是否已處于感知節點監測之下,來控制相鄰感知節點的睡眠狀態以及睡眠時長。雖然該睡眠方案下的評估算法規避了重復覆蓋和成本控制的問題,但是此類靜態部署方案下的感知節點無法適時更新方位信息,導致感知節點無法自適應地解決覆蓋漏洞問題。OTMAN等[3]考慮引入粒子群算法(Particle Swarm,PS),該算法下的粒子解均可作為科學部署感知節點方位坐標值的有效依據。雖然這一特征解決了文獻[1]和文獻[2]關于部署密度不均衡和靜態感知所導致的覆蓋漏洞、效能度低等QoS問題,但PS算法在粒子空間內開展搜索計算時存在收斂過早的問題,導致該算法的搜索值并不具備全局普適性,進而弱化了PS算法的部署成效?；诖?本文考慮通過調整PS算法在局部空間內的搜索權重,并引入變異評估機制來規避因算法陷入早熟導致搜索的粒子值缺乏全局普適性。根據普適性提升后的粒子值來部署感知節點,可有效地兼顧部署成本和服務覆蓋的QoS,從而達到基于QoS約束的感知網絡覆蓋算法(QoS Constrained Aware Network Coverage Algorithm,ANC)目標成效。

1 數學計算模型

假設在一個N×K的目標區域范圍內共有像素點[4]規模N×K個,且隨機部署K個感知節點。感知節點的方位數據、感知半徑范圍以及工作能耗均可通過廣播方式向感知全網共享。定義每個節點在感知網絡內的坐標和感知半徑范圍分別為sk(Xk,Yk)和r。其中,感知節點坐標即為PS算法的初始參數。感知全網內的感知節點集合記作S={s1,s2,…,sk}。感知節點sk(Xk,Yk)和待測目標節點R(XR,YR)的間距表征為:

(1)

其中,k=1,2,…,K。

引入覆蓋[5]判斷機制F(sk,R)。當該值置為0時,代表待測目標節點R(XR,YR)不在感知節點sk(Xk,Yk)的感知范圍內,此時滿足條件rD(sk,R)。由于同一個待測目標可能同時被多個感知節點感知,故待測目標節點R(XR,YR)被感知節點集合S感知的概率為:

(2)

同理,當f(S,R)的值置為0時,代表待測目標節點R(XR,YR)不在感知節點集合S的感知范圍之內。反之,當f(S,R)的值置為1時,代表待測目標節點R(XR,YR)已在感知節點集合S的感知范圍之內。求得被覆蓋的像素點規模為:

(3)

根據公式(3)可得到運行PS算法后最終獲得的具有全局普適性的粒子目標適應值,即待測目標節點被整個感知網絡覆蓋的概率,將其表征為:

(4)

2 覆蓋算法模型

PS算法在粒子求解空間內搜索出來的值是否具有良好的普適性[6],與PS算法搜索權重存在一定的關系。通常搜索權重越小,PS算法在求解空間內搜索出來的值越具備良好的局部普適性。反之,搜索權重越大,PS算法在求解空間內搜索出來的值越具備良好的全局普適性。為使PS算法能夠在最短時間內快速地對局部網絡范圍內的求解空間進行強有力的目標值搜索,本文針對搜索權重做了優化設計。假設PS算法開展迭代計算的頻次為d,允許迭代計算的最高頻次為dH。為了實現隨迭代計算頻次的持續增加,搜索權重曲線的斜率下降幅度有所減慢,將部署算法搜索權重設計為:

I=0.5d/dH-0.2.

(5)

(6)

粒子移動后的新的方位矢量為:

(7)

公式(6)和公式(7)的優勢在于通過優化算法在粒子求解空間的搜索權重,進一步強化迭代計算值在局部范圍內的自適應性,以提升算法在局部范圍內的最優適應解的搜索能力。

(8)

同時引入適應度標準差A,用于評估PS算法迭代計算出來的值是否逼近于最優解。

(9)

若評估出來的適應度標準差的值較小,則表示PS算法收斂出來的值逼近于全局最優適應解和局部最優適應解。當適應度標準差的值為0時,判斷當前迭代頻次是否小于允許的最高迭代計算頻次。若是,則啟動變異操作,即根據公式(6)和公式(7)更新粒子的方位矢量和搜索速度,再次開展計算得出該粒子的個體歷史最優適應值;反之,則無需啟動變異操作。

3 算法部署

在PS算法基礎上引入搜索權重自適應調整機制,并借鑒遺傳算法變異處理機制科學地開展QoS級自適應粒子群求解計算。通過頻繁迭代計算出來的全局歷史最優適應解,可視為感知節點在感知網絡范圍內的最佳方位部署方案。優化后的算法實施流程如圖1所示。

圖1 ANC算法流程圖

4 算法測試

本文構思的ANC算法是由PS算法優化而來,故在算法測試環節將ANC算法的測試數據與PS算法展開對比。測試前首先在MATLAB平臺構建一個邊長為200 m的正方形區域作為感知網絡的模擬環境,并投放80個傳感器和30個粒子。其中,傳感器節點所能感知的半徑范圍在4 m至12 m之間,粒子突變概率設為0.01,且粒子開展迭代計算的最高頻次為600。然后在傳感器感知半徑范圍內,通過調整傳感器數量及感知半徑大小來收集測試數據,并對比兩種算法方案下粒子解的普適性。進而驗證ANC算法覆蓋的服務成效[9]。

根據算法模型可知,感知節點的網絡覆蓋程度高低與感知節點自身感知范圍大小成正比,即當感知節點的感知半徑擴大時,全網覆蓋率必然提升?；诖?第一組實驗引入80個傳感器作為感知節點,通過逐步擴大傳感器感知范圍來考察兩種算法下的網絡覆蓋性能。觀察圖2曲線走勢可知,隨著傳感器感知半徑的擴大,兩種算法下的網絡覆蓋率均有不同程度提升,尤其在擴大感知半徑的初期,兩條曲線斜率均線性遞增,這表明兩種算法的覆蓋優勢均得到發揮。但隨著感知半徑進一步擴大,PS算法曲線的斜率持續走低,增量逐漸減少,這意味著PS算法的覆蓋率接近于極限。相反,ANC算法由于在粒子搜索權重設計方面引入了優化機制,在本組覆蓋率測試中算法曲線斜率依然表現出良好的線性遞增趨勢,且與PS算法曲線走勢形成鮮明對比。

圖2 感知半徑對覆蓋率的影響力 圖3 感知節點數量對覆蓋率的影響力

第二組實驗主要考察傳感器節點數量的變化對覆蓋率的影響力,實驗結果如圖3所示。從兩條算法曲線走勢不難看出,傳感器數量可在一定程度上助力提升覆蓋率。在傳感器數量遞增初期,由于傳感器節點數量不多,ANC算法優勢未能得到發揮,所以未表現出明顯的相對優勢。隨著傳感器數量增至50個,兩種算法下的網絡覆蓋指標開始出現差異,ANC算法下的覆蓋率曲線持續走高,相比之下PS算法曲線的覆蓋率曲線走勢有所減緩。這是由于在設計ANC算法時為粒子個體引入了目標適應值這一考察指標,該指標有助于確保粒子解兼顧局部普適性和全局自適應性,這是PS算法所不具備的優勢。因此根據ANC算法計算得到的粒子解來部署傳感器的方位,可具備更有效的感知性能和覆蓋能力。因此,在傳感器節點數量較多的復雜環境下,ANC算法覆蓋優勢越得到發揮,越能表現出差異化優勢。

從上述兩個實驗結果可知,通過優化設計搜索權重和引入基因突變處理機制的ANC算法,在復雜感知環境中能夠科學地保障粒子解同時具備全網普適性和局部網絡普適性,從而使該算法在實驗中表現出了良好的科學性。

5 結語

本文從普適性出發總結了傳統PS算法在粒子空間內搜索解的過程中存在的問題,提出了優化的迭代計算機制和粒子解的評估機制。該機制主要通過自適應重置粒子搜索權重和普適性目標函數來解決傳統PS算法在求解空間內的收斂瓶頸。將針對傳統PS算法提出的兩個優化機制進行實驗測試,結果表明,本文算法具備良好的覆蓋成效。