賈海云

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

0 引言

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

1 數(shù)學(xué)計算模型

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

(1)

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

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

(2)

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

(3)

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

(4)

2 覆蓋算法模型

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

I=0.5d/dH-0.2.

(5)

(6)

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

(7)

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

(8)

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

(9)

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

3 算法部署

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

圖1 ANC算法流程圖

4 算法測試

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

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

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

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

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

5 結(jié)語

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