馮秀芳,辛 英,陰成軍,常建峰
(太原理工大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,山西 太原030024)
無線多媒體傳感器網(wǎng)絡(luò)使人類的視野更為廣闊,是一個(gè)新型、前沿、多學(xué)科高度交叉的研究領(lǐng)域[1-2]。覆蓋控制和部署策略對于整個(gè)多媒體傳感器網(wǎng)絡(luò)的監(jiān)測性能、監(jiān)測質(zhì)量具有至關(guān)重要的作用[3]。
不同于傳統(tǒng)傳感器網(wǎng)絡(luò)全向感知節(jié)點(diǎn),無線多媒體傳感器網(wǎng)絡(luò)中,無論是紅外線傳感器,超聲波傳感器還是視頻傳感器都是有向的。學(xué)術(shù)界已有前輩在研究此方面。Jing Ai[4],發(fā)表文章討論了在隨機(jī)分布的無線傳感器網(wǎng)絡(luò)中,有向傳感器節(jié)點(diǎn)的覆蓋問題。文獻(xiàn) [5]介紹了無線傳感器網(wǎng)絡(luò)中,不明位置下的覆蓋問題。文獻(xiàn) [6]討論有向傳感器網(wǎng)絡(luò)中,二維和三維空間在隨機(jī)部署下的入侵目標(biāo)檢測算法。Daniel[7]等討論了無線傳感器網(wǎng)絡(luò)中,基于有向的視頻傳感器節(jié)點(diǎn)的覆蓋問題。文獻(xiàn) [8]向我們介紹有向傳感網(wǎng)絡(luò)的覆蓋及其能量有效利用等問題。Prasan[9]等向我們介紹了無線傳感器網(wǎng)絡(luò)中,基于拓?fù)浣Y(jié)構(gòu)的能量控制問題。陶丹[10]等進(jìn)行了有向傳感器網(wǎng)絡(luò)的覆蓋增強(qiáng)研究,提出了一種基于虛擬力的有向傳感器網(wǎng)絡(luò)覆蓋增強(qiáng)算法。文獻(xiàn)[11]提出一種基于粒子群算法的無線傳感網(wǎng)絡(luò)覆蓋優(yōu)化方法。文獻(xiàn) [12]把基本粒子群算法和與擬物力算法相融合,設(shè)計(jì)出擬物力導(dǎo)向的無線傳感網(wǎng)絡(luò)覆蓋優(yōu)化策略。文獻(xiàn)[13],提出了一種微粒群優(yōu)化的有向傳感器網(wǎng)絡(luò)覆蓋增強(qiáng)算法。本文在研究前面成果的基礎(chǔ)上,結(jié)合虛擬力和粒子群優(yōu)化算法提出了一種新的覆蓋增強(qiáng)算法。此算法在能量有效利用的前提下,能有效提高網(wǎng)絡(luò)的覆蓋率。
感知模型的研究是進(jìn)行覆蓋控制研究的基礎(chǔ)。不同于傳統(tǒng)的全向感知模型,多媒體傳感器網(wǎng)絡(luò)中的節(jié)點(diǎn)具有有限的感知角,所以需要研究有向感知模型。如圖1所示,有向感知模型。

圖1 有向感知模型
如圖1所示,有向傳感器節(jié)點(diǎn)P覆蓋區(qū)域是一個(gè)扇形,可以用四元組 (P,Rs,dij,θ)來表示。一般在二維空間中的有向感知模型如圖1所示,這種模型的一個(gè)特殊情況是,當(dāng)θ=360°時(shí),就成了全向感知模型。三角形點(diǎn)是感知事件,陰影扇形區(qū)域是有向傳感器節(jié)點(diǎn)的感知范圍,感知范圍和有向傳感器節(jié)點(diǎn)的感知半徑和市場角度有關(guān)。節(jié)點(diǎn)可以選擇不同的工作方向來覆蓋事件和區(qū)域。其中,P是傳感器節(jié)點(diǎn)的位置,dij是單位向量,定義了有向傳感器的方向。θ是視角 (FoV),描述了有向傳感器的最大感應(yīng)角。Rs為傳感器的感知半徑。
使用虛擬力算法來控制傳感器節(jié)點(diǎn)的移動,使網(wǎng)絡(luò)中的節(jié)點(diǎn)分布均勻,從而提高網(wǎng)絡(luò)的覆蓋性能。由于每個(gè)有向傳感器節(jié)點(diǎn)可能有很多的感知方向,感知方向不同,傳感器節(jié)點(diǎn)的覆蓋區(qū)域也不一樣。針對此問題,該算法首先使用虛擬力全局調(diào)整節(jié)點(diǎn)的位置,然后通過粒子群優(yōu)化算法局部調(diào)整節(jié)點(diǎn)的感知方向,減少節(jié)點(diǎn)之間的重疊區(qū),同時(shí)減少節(jié)點(diǎn)之間的感知盲區(qū),提高整個(gè)區(qū)域的覆蓋率。
2.2.1 基于虛擬力覆蓋增強(qiáng)算法
該算法的核心思想是,傳感器網(wǎng)絡(luò)中的節(jié)點(diǎn)和其他的對象之間都存在著大小不等的引力和斥力,斥力和引力是用傳感器節(jié)點(diǎn)之間的位置、方向以及設(shè)定的一些參數(shù)來刻畫的。利用傳感器網(wǎng)絡(luò)中節(jié)點(diǎn)的可移動性,通過受力的不同,使傳感器節(jié)點(diǎn)沿著力的方向進(jìn)行移動,從而使網(wǎng)絡(luò)中的節(jié)點(diǎn)分布合理,最終合理的覆蓋整個(gè)區(qū)域,更好的提供感知目標(biāo)區(qū)域的信息。
給出節(jié)點(diǎn)的受力分析如圖2所示:dij表示傳感器節(jié)點(diǎn)si的中心點(diǎn)vi和節(jié)點(diǎn)sj的中心點(diǎn)vj之間的歐式距離。當(dāng)dij小于傳感器節(jié)點(diǎn)的半徑的時(shí)候,它們的感知區(qū)域才存在重疊的可能,故兩個(gè)傳感器節(jié)點(diǎn)之間存在的斥力的作用,該斥力作用于傳感器節(jié)點(diǎn)的中心點(diǎn)vi和vj上。根據(jù)基本虛擬力公式,中心點(diǎn)所受引力的大小與中心點(diǎn)vi和vj之間的距離成正比,而中心點(diǎn)的位置由傳感器節(jié)點(diǎn)si和sj的位置決定。

圖2 有向傳感器節(jié)點(diǎn)受力
當(dāng)dij大于傳感器節(jié)點(diǎn)的半徑的時(shí)候,它們的感知區(qū)域不存在重疊,這時(shí)兩個(gè)傳感器節(jié)點(diǎn)之間存在著引力的作用,該引力作用于傳感器節(jié)點(diǎn)的中心點(diǎn)vi和vj上。根據(jù)基本虛擬力公式,中心點(diǎn)所受斥力的大小與中心點(diǎn)vi和vj之間的距離成反比,同樣,中心點(diǎn)的位置由傳感器節(jié)點(diǎn)si和sj的位置決定。
各傳感器節(jié)點(diǎn)根據(jù)虛擬力將原位置 (x,y)更新為新位置 (x,,y,),如式 (1)所示,其中,MaxStep是傳感節(jié)點(diǎn)最大移動距離,F(xiàn)xy是作用于傳感節(jié)點(diǎn)的虛擬力,F(xiàn)x,F(xiàn)y是虛擬力的x軸和y軸的分量,F(xiàn)th是虛擬力閾值,當(dāng)傳感節(jié)點(diǎn)所受虛擬力小于該值時(shí),則認(rèn)為它不需移動

距離閾值Fth在傳感器網(wǎng)絡(luò)部署的疏密程度起到一個(gè)重要的作用。當(dāng)Fth很小時(shí),傳感節(jié)點(diǎn)會分布過密,從而傳感器網(wǎng)絡(luò)不能很好的覆蓋整個(gè)區(qū)域,無法保證網(wǎng)絡(luò)的覆蓋率;當(dāng)Fth設(shè)定很大的時(shí)候,傳感節(jié)點(diǎn)的分布很稀疏,這就容易形成感知盲區(qū)。因此,虛擬力算法在實(shí)際的應(yīng)用中,一些參數(shù)只能通過經(jīng)驗(yàn)來確定,無法自動的滿足不同檢測環(huán)境的需求。
虛擬力移動節(jié)點(diǎn)算法流程:
(1)隨機(jī)分布n個(gè)節(jié)點(diǎn),獲取有向傳感器節(jié)點(diǎn)位置信息,生成有向傳感器節(jié)點(diǎn)模型
(2)for loop=1:MAXLOOP%循環(huán)迭代次數(shù)
(3)計(jì)算傳有向傳感器節(jié)點(diǎn)中心點(diǎn)之間的距離Dij,計(jì)算網(wǎng)絡(luò)的覆蓋率C,計(jì)算網(wǎng)絡(luò)的覆蓋效率CE,覆蓋均勻性U:
for i=1:n%計(jì)算節(jié)點(diǎn)之間的虛擬力Fi
for j=1:n
計(jì)算傳感器節(jié)點(diǎn)Si,Sj的中心點(diǎn)Mi和Mj的虛擬力Fij
End
End
End
(4)計(jì)算傳感器節(jié)點(diǎn)的新位置
(5)計(jì)算節(jié)點(diǎn)的平均移動距離
(6)將新位置賦值給舊位置End
2.2.2 粒子群優(yōu)化覆蓋增強(qiáng)算法
根據(jù)2.2.1的分析,經(jīng)過虛擬力作用的調(diào)整后,多媒體傳感器網(wǎng)絡(luò)中節(jié)點(diǎn)分布相對均勻。本節(jié)用粒子群算法局部調(diào)整有向傳感器網(wǎng)絡(luò)的感知方向,針對有向傳感器網(wǎng)絡(luò)感知方向調(diào)整的需要,設(shè)計(jì)微粒適應(yīng)值計(jì)算函數(shù)和種群進(jìn)化策略,在此基礎(chǔ)上,以網(wǎng)絡(luò)的覆蓋率為優(yōu)化目標(biāo),調(diào)整傳感器節(jié)點(diǎn)的感知方向最后實(shí)現(xiàn)有向傳感器網(wǎng)絡(luò)覆蓋的增強(qiáng)[14]。
設(shè)監(jiān)測區(qū)域中的有向傳感器節(jié)點(diǎn)數(shù)為n,每個(gè)節(jié)點(diǎn)的初始感知方向向量為 (O1,O2,…,ON)。引入的微粒群種群規(guī)模為m,微粒群的搜索空間d為監(jiān)測區(qū)域中傳感器節(jié)點(diǎn)數(shù)n。微粒i的角度向量αi為 (αi1,αi2,…,αin),其中αi1,αi2,…,αin依次表示傳感器節(jié)點(diǎn)1至n的感知方向。微粒i的角度調(diào)整向量ωi,為 (ωi1,ωi2,…,ωin)。
定義微粒i的適應(yīng)值函數(shù)fi為

適應(yīng)值fi應(yīng)傳感器節(jié)點(diǎn)在感知方向 (O1,O2,…,ON)= (αi1,αi2,…,αin)下的有向傳感器網(wǎng)絡(luò)的有效覆蓋率,群體中所有微粒經(jīng)歷的最佳位置pg為

為了找到全局最優(yōu)解,需要對微粒進(jìn)行迭代的進(jìn)化,微粒進(jìn)化對應(yīng)的角度調(diào)整計(jì)算公式如下所示

式中:C1、C2——加速因子,它們的作用是用于調(diào)節(jié)每個(gè)微粒向局部最優(yōu)解和全局最優(yōu)解的進(jìn)化步長;pbestaij——微粒i的第j維經(jīng)歷的局部最佳角度;gbestaij——用為全局最佳角度;aij(t)——第i代種群中的第j個(gè)微粒的第j維,即傳感器j的感知方向;在進(jìn)化過程中對于每次調(diào)整的角度大小ωij應(yīng)限制于一定范圍內(nèi),這樣就能進(jìn)使迭代進(jìn)化比較穩(wěn)定。當(dāng)ωij超出該范圍時(shí),則調(diào)整為ωmax或ωmin;β﹙t﹚∈ (0,1)為隨機(jī)數(shù),稱為慣性因子,隨迭代次數(shù)增加應(yīng)逐步減少,從而使得算法在初期能快速到達(dá)全局最優(yōu)解附近,后期則能穩(wěn)定收斂至全局最優(yōu)解。β﹙t﹚的取值如
式 (6)所示[15]

式中:βmax——慣性因子的最大值,βmin——慣性因子的最小值,t——當(dāng)前迭代次數(shù),MaxDT——最大迭代次數(shù)。
基于微粒群優(yōu)化算法的多媒體傳感器網(wǎng)絡(luò)覆蓋增強(qiáng)算法流程:
(1)初始化多媒體傳感器節(jié)點(diǎn)的位置,設(shè)定種群的規(guī)模為n,隨機(jī)生成每個(gè)粒子的初始位置Xi、初始感知角度αi和速度Vi。
(2)根據(jù)多媒體傳感器網(wǎng)絡(luò)覆蓋率的計(jì)算方法,計(jì)算傳感器節(jié)點(diǎn)初始部署下的覆蓋率。
(3)對每個(gè)微粒,根據(jù)公式更新最優(yōu)位置pbest_aij和全局最優(yōu)位置gbest_aij。
(4)判斷粒子是否達(dá)到當(dāng)前的近似最優(yōu)解,重新生成各粒子速度,計(jì)算適應(yīng)值。
(5)是否達(dá)到停止的條件 (粒度減少到特定的值、達(dá)到最好的適應(yīng)值或到了最大的跌代數(shù)),返回步驟 (2)。
實(shí)驗(yàn)采用Matlab7.0仿真環(huán)境,用到粒子群工具箱對覆蓋增強(qiáng)算法的調(diào)整。假設(shè)在邊長為1000cm的正方形監(jiān)測區(qū)域中隨機(jī)部署70個(gè)有向傳感器節(jié)點(diǎn),所有傳感器節(jié)點(diǎn)感知半徑R=70cm,通信半徑為2R=140cm。虛擬力算法的參數(shù)為:ωA=2與ωR=4,采用微粒群算法的加速因子C1=C2=1。傳感器網(wǎng)絡(luò)的初始角度為60°,每次調(diào)整的角度為5°。圖3(a)為初始隨機(jī)部署70個(gè)傳感器節(jié)點(diǎn)的分布圖,從圖中可以看出,有些區(qū)域中節(jié)點(diǎn)的分布集中,有些空白區(qū)域沒有被節(jié)點(diǎn)覆蓋,因此,節(jié)點(diǎn)的分布不均勻,不能最大化覆蓋檢測區(qū)域,同時(shí)也浪費(fèi)了傳感器節(jié)點(diǎn)資源。圖3(b)、(c)、 (d)為用虛擬力算法先全局調(diào)整節(jié)點(diǎn)的位置,然后用粒子群優(yōu)化算法調(diào)整每個(gè)傳感器網(wǎng)絡(luò)的感知方向,通過仿真實(shí)驗(yàn)進(jìn)行200次的迭代的結(jié)果。
(1)節(jié)點(diǎn)數(shù)分析:多媒體傳感器網(wǎng)絡(luò)的感知半徑對網(wǎng)絡(luò)的覆蓋率有很大的影響,在感知角度一定的情況下,隨著感知半徑的增加,覆蓋區(qū)域的面積相應(yīng)的增加。表1為不同節(jié)點(diǎn)數(shù)覆蓋率數(shù)據(jù),從表中看以看出,節(jié)點(diǎn)數(shù)越多覆蓋率越高。
圖4表示隨著節(jié)點(diǎn)的變化,隨機(jī)部署、基于虛擬了算法的優(yōu)化和粒子群算法優(yōu)化的覆蓋率的比較圖。通過圖可以看出,初始的隨機(jī)部署節(jié)點(diǎn)的覆蓋率不是很高,進(jìn)過虛擬力的作用調(diào)整節(jié)點(diǎn)的位置后,覆蓋率有了明顯的提高。在調(diào)整位置的基礎(chǔ)上,采用粒子群優(yōu)化算法對節(jié)點(diǎn)的感知方向進(jìn)行局部的調(diào)整,可以看出,網(wǎng)絡(luò)的覆蓋率又提升了很多。

圖3 70個(gè)節(jié)點(diǎn)覆蓋優(yōu)化迭代

表1 節(jié)點(diǎn)數(shù)變化的覆蓋性能測試數(shù)據(jù)

圖4 初始部署與覆蓋增強(qiáng)后比較
(2)感知半徑分析:有向傳感器網(wǎng)絡(luò)的感知半徑對網(wǎng)絡(luò)的覆蓋性能有很大的影響,表2為不同的感知半徑下,網(wǎng)絡(luò)的覆蓋率數(shù)據(jù)。
如圖5所示,在隨機(jī)部署下,節(jié)點(diǎn)數(shù)的不同初始覆蓋率有很大的區(qū)別。在固定的區(qū)域中,傳感器節(jié)點(diǎn)的感知半徑不變的時(shí)候,節(jié)點(diǎn)數(shù)越多,傳感器網(wǎng)絡(luò)的覆蓋率就越高,節(jié)點(diǎn)數(shù)為90個(gè)時(shí)候比節(jié)點(diǎn)數(shù)45個(gè)的時(shí)候的覆蓋率對了42%。同樣在虛擬力算法的優(yōu)化中,節(jié)點(diǎn)數(shù)為90的覆蓋率比節(jié)點(diǎn)數(shù)為45個(gè)時(shí)候的覆蓋率多了49%。在粒子群優(yōu)化算法優(yōu)化后,節(jié)點(diǎn)數(shù)為90的覆蓋率比節(jié)點(diǎn)數(shù)為45的時(shí)候覆蓋率多了38%。

表2 傳感器節(jié)點(diǎn)半徑覆蓋性能測試數(shù)據(jù)

圖5 節(jié)點(diǎn)半徑對覆蓋優(yōu)化的影響
小結(jié):通過實(shí)驗(yàn)表明,該算法很好的消除了初始部署中傳感器節(jié)點(diǎn)的感知盲區(qū)和重疊區(qū),并分析傳感器節(jié)點(diǎn)的半徑和個(gè)數(shù)對網(wǎng)絡(luò)覆蓋率的影響,隨著傳感器節(jié)點(diǎn)的感知半徑和個(gè)數(shù)的增加,網(wǎng)絡(luò)的覆蓋也有所增加。虛擬力參數(shù)對網(wǎng)絡(luò)的覆蓋具有很大的影響。在實(shí)驗(yàn)的過程中粒子群優(yōu)化算法具有陷入局部最優(yōu)解的確定,有時(shí)候在迭代次數(shù)增加的時(shí)候,網(wǎng)絡(luò)的覆蓋率有所減少。后續(xù)的工作是進(jìn)一步對粒子群算法改進(jìn)和參數(shù)調(diào)整,是網(wǎng)絡(luò)達(dá)到更優(yōu)的覆蓋。
本文圍繞無線多媒體傳感器網(wǎng)絡(luò)的有向感知模型,研究基于虛擬力和粒子群算法的覆蓋增強(qiáng)算法。采用隨機(jī)部署方法在檢測區(qū)域中投放地大量有向傳感器節(jié)點(diǎn),由于初始部署后節(jié)點(diǎn)分布往往不合理和不均勻,不能最大化的覆蓋整個(gè)區(qū)域,因此,在完成初始部署后,需要采用相應(yīng)的覆蓋增強(qiáng)策略來調(diào)整傳感器節(jié)點(diǎn)的分布和感知方向,進(jìn)而改善多媒體傳感器網(wǎng)絡(luò)的覆蓋性能。本算法通過節(jié)點(diǎn)之間及節(jié)點(diǎn)和障礙物之間的虛擬力,調(diào)整傳感器節(jié)點(diǎn)的分布位置,使網(wǎng)絡(luò)中的節(jié)點(diǎn)最后分布合理、均勻,同時(shí),有效地調(diào)整有向傳感器節(jié)點(diǎn)的工作方向,使得能夠用最少的節(jié)點(diǎn)達(dá)到最大的覆蓋。
[1]DeBardelaben J A.Multimedia sensor networks for ISR applications [C].Conference Record of the Thirty-Seventh Asilomar Conference on Signals,Systems and Computers.Pacific Grove,Califomia:IEEE Press,2005:2009-2012.
[2]Akyildiz I F,Melodia T,Chowdhury K R.A survey on wireless multimedia sensor networks [J].Computer Networks,2007,51 (4):921-960.
[3]Misra S,Reisslein M,Xue G.A survey of multimedia streaming in wireless sensor networks [J].IEEE Communications Surveys Tutorials,2008,10 (4):18-39.
[4]Jing Ai·Alhussein A.Abouzeid coverage by directional sensors in randomly deployed wireless sensor networks [J].Comb Optim,2006,11 (1):21-41.
[5]Ossama Younis,Marwan Krunz,Srinivasan Ramasubramanian location-unaware coverage in wireless sensor networks [J].Ad Hoc Networks,2008,6 (7):1078-1097.
[6]Yang Xiao,Zhang Yanping,Miao Peng,et al.Intrusion object detection under Two and three-dimensional randomized scheduling algorithms in sensor networks [J].Computer Networks,2009,53 (14):2458-2475.
[7]Daniel G Costa,Luiz Affonso Guedes.The coverage problem in video-based wireless sensor networks:A survey [J].Sensors,2010,10:8215-8247.
[8]Ma H,Liu Y.Some problems of directional sensor networks[J].International Journal of Sensor Networks(InderScience),2007,2 (1-2):44-52.
[9]Prasan Kumar Sahoo,Sheu Jang-Ping,Hsieh Kun-Ying.Power control based topology construction for the distributed wireless sensor networks [J].Computer Communications,2007,30(14-15):2774-2785.
[10]TAO Dan.Research on coverage control and collaborative approach of video sensor network [D].Beijing:Beijing University of Posts and Telecommunications,2007 (in Chinese).[陶丹.視頻傳感器網(wǎng)絡(luò)覆蓋控制及協(xié)作處理方法研究 [D].北京:北京郵電大學(xué),2007.]
[11]TAO Dan,MA Donghua,LIU Liang.The coverage enhancement algorithm of sensor network based on virtual potential field [J].Journal of Software,2007,18 (5):1152-1163(in Chinese).[陶丹,馬華東,劉亮.基于虛擬勢場的有向傳感器網(wǎng)絡(luò)覆蓋增強(qiáng)算法 [J].Journal of Software,2007,18 (5):1152-1163.]
[12]WANG Xue,WANG Chen,MA Junjie.The virtual poweroriented particle swarm optimization strategy for the layout of wireless sensor network [J].Chinese Journal of Electronics,2007,35 (11):2038-2042 (in Chinese). [王雪,王晨,馬俊杰.無線傳感網(wǎng)絡(luò)布局的虛擬力導(dǎo)向微粒群優(yōu)化策略 [J].電子學(xué)報(bào),2007,35 (11):2038-2042.]
[13]LIN Zhuliang.The study on coverage problem optimization Strategy of wireless sensor network based on particle swarm optimization [D].Hangzhou:Zhejiang University of Industrial,2009(in Chinese).[林祝亮.基于粒子群算法的無線傳感網(wǎng)絡(luò)覆蓋問題優(yōu)化策略研究 [D].杭州:浙江工業(yè)大學(xué),2009.]
[14]SUN Lijuan,DU Pengling,XIAO Pu,et al.The enhanced coverage problem of sensor network coverage based on particle swarm optimization [J].Journal of Computer Research and Development,2010,47 (Supply.):22-25. [孫力娟,杜鵬玲,肖甫,等.基于微粒群優(yōu)化的有向傳感器網(wǎng)絡(luò)覆蓋增強(qiáng)算法 [J]. 計(jì) 算 機(jī) 研 究 與 發(fā) 展,2010,47 (Supply.):22-25.]
[15]LU Xiaoling.Model based on particle swarm optimization deployment of wireless sensor network nodes [D].Taiyuan:Taiyuan University of Science and Technology,2009 (in Chinese).[戶曉玲.基于微粒群模型的無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)部署研究 [D].太原:太原科技大學(xué),2009.]