基于QoS約束的感知網(wǎng)絡覆蓋研究

賈海云

(合肥財經(jīng)職業(yè)學院,安徽 合肥 230601)

0 引言

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

1 數(shù)學計算模型

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

(1)

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

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

(2)

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

(3)

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

(4)

2 覆蓋算法模型

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

I=0.5d/dH-0.2.

(5)

(6)

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

(7)

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

(8)

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

(9)

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

3 算法部署

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

圖1 ANC算法流程圖

4 算法測試

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

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

圖2 感知半徑對覆蓋率的影響力 圖3 感知節(jié)點數(shù)量對覆蓋率的影響力

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

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

5 結語

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