基于全局貪心的有向傳感器網(wǎng)絡(luò)覆蓋算法
掃描二維碼
隨時(shí)隨地手機(jī)看文章
摘要:針對(duì)分布式貪心算法(DGreedy)以傳感器節(jié)點(diǎn)的剩余能量為優(yōu)先級(jí),節(jié)點(diǎn)處理順序沒有考慮相鄰節(jié)點(diǎn)間的關(guān)系對(duì)網(wǎng)絡(luò)覆蓋率的影響,從而影響覆蓋率的不足,在此提出了一種新的有向傳感器網(wǎng)絡(luò)覆蓋算法?;谌重澬牡脑瓌t,以節(jié)點(diǎn)一重覆蓋區(qū)域面積的大小為優(yōu)先級(jí),優(yōu)先確定一重覆蓋區(qū)域面積最大的傳感器節(jié)點(diǎn)方向,從而保證傳感器網(wǎng)絡(luò)的一重覆蓋區(qū)域面積更大,重疊覆蓋區(qū)域較少。對(duì)比實(shí)驗(yàn)結(jié)果表明,該算法能有效提高覆蓋率。
關(guān)鍵詞:有向傳感器網(wǎng)絡(luò);全局貪心;一重覆蓋;Matlab
0 引言
覆蓋問題是無線傳感器網(wǎng)絡(luò)的一個(gè)基本問題,是近年來該領(lǐng)域的研究熱點(diǎn)。目前多數(shù)覆蓋控制的研究成果都是基于滿足全向性感知模型的傳感器進(jìn)行的,但在實(shí)際應(yīng)用中,許多有向傳感器,如視頻傳感器,已被廣泛應(yīng)用于無線多媒體傳感器網(wǎng)絡(luò)中。與基于滿足全向性感知模型的無線傳感器網(wǎng)絡(luò)相比,有向傳感器網(wǎng)絡(luò)的覆蓋問題更復(fù)雜,是該領(lǐng)域的一個(gè)重要研究方向。
Ma等首先提出了有向傳感器網(wǎng)絡(luò)的概念,設(shè)計(jì)了一種有向傳感器感知模型,并研究了有向傳感器網(wǎng)絡(luò)的覆蓋完整性問題。文獻(xiàn)等都采用了基于虛擬勢場的思想進(jìn)行有向傳感器網(wǎng)絡(luò)覆蓋控制。陶丹等在文獻(xiàn)中設(shè)計(jì)了一種方向可調(diào)的感知模型,并以此為基礎(chǔ)首先提出了基于虛擬勢場的有向傳感器網(wǎng)絡(luò)覆蓋增強(qiáng)算法,通過引入“質(zhì)心”的概念,將有向傳感器用質(zhì)心點(diǎn)代替,并將有向傳感器網(wǎng)絡(luò)的覆蓋問題轉(zhuǎn)化為質(zhì)心分布問題,質(zhì)心點(diǎn)在虛擬力的作用下運(yùn)動(dòng),消除感知盲區(qū)和重疊區(qū)。傳統(tǒng)基于虛擬勢場的有向傳感器網(wǎng)絡(luò)覆蓋增強(qiáng)算法只判斷和調(diào)整方向,節(jié)點(diǎn)的調(diào)整量為固定值,針對(duì)這一問題,黃帥等在文獻(xiàn)中利用虛擬力與角度調(diào)整量間的關(guān)系,根據(jù)虛擬力的大小改變節(jié)點(diǎn)的角度調(diào)整量,提高了網(wǎng)絡(luò)的調(diào)整效率。但是,以上基于虛擬勢場思想的無線傳感器網(wǎng)絡(luò)覆蓋方法,每個(gè)節(jié)點(diǎn)均需計(jì)算多個(gè)相鄰節(jié)點(diǎn)的合力,節(jié)點(diǎn)受力隨轉(zhuǎn)動(dòng)過程不斷變化,使得算法較復(fù)雜;且節(jié)點(diǎn)根據(jù)力矢量的大小和方向進(jìn)行轉(zhuǎn)動(dòng),轉(zhuǎn)動(dòng)角度取值過小會(huì)增加調(diào)整時(shí)間,取值過大則會(huì)引起頻繁的計(jì)算和傳感方向的反復(fù)調(diào)整,且因合力未必為0,可能導(dǎo)致調(diào)整過程中角度往復(fù)震蕩。文獻(xiàn)提出了一種分布式貪心算法(DGreedy),以傳感器節(jié)點(diǎn)的剩余能量為優(yōu)先級(jí),每個(gè)傳感器基于局部貪心原則選擇工作方向,使傳感器網(wǎng)絡(luò)覆蓋盡可能大的區(qū)域。但是,DGreedy算法受傳感器節(jié)點(diǎn)處理順序影響較大,以剩余能量為優(yōu)先級(jí)的方法沒有考慮節(jié)點(diǎn)問覆蓋區(qū)域的相互影響,從而影響整個(gè)網(wǎng)絡(luò)的覆蓋率。
本文基于全局貪心原則,提出了一種有向傳感器網(wǎng)絡(luò)覆蓋算法。以節(jié)點(diǎn)各方向下一重覆蓋區(qū)域的大小為優(yōu)先級(jí),優(yōu)先確定一重覆蓋區(qū)域面積最大的傳感器節(jié)點(diǎn)方向,保證了傳感器網(wǎng)絡(luò)的一重覆蓋區(qū)域面積更大,重疊覆蓋區(qū)域較少。對(duì)比實(shí)驗(yàn)驗(yàn)證了本文算法的有效性。
1 覆蓋算法
1.1 DGreedy算法
分布式貪心算法DGreedy由程衛(wèi)芳等人提出,并應(yīng)用于有向傳感器網(wǎng)絡(luò)覆蓋中。DGreedy假設(shè)傳感器節(jié)點(diǎn)不同方向的感應(yīng)范圍互不重疊,4個(gè)可選方向的傳感器節(jié)點(diǎn)示例如圖1所示,圖中Si,j表示第i個(gè)傳感器的第j個(gè)方向。文中還假定所有傳感器節(jié)點(diǎn)具有相同的結(jié)構(gòu)。給每個(gè)傳感器分配一個(gè)彼此不同的優(yōu)先級(jí),并定義Gi,j表示節(jié)點(diǎn)Si的第J個(gè)方向上,沒有被更高級(jí)的感應(yīng)鄰居所覆蓋的面積。
DGreedy算法具體描述如下:
1.2 改進(jìn)的DGreedy算法
DGreedy算法每個(gè)傳感器以局部貪心的原則確定工作方向,只要感應(yīng)鄰居間的覆蓋消息能準(zhǔn)確傳遞,就能在有限時(shí)間內(nèi)終止。但是,傳感器的決策順序,即優(yōu)先級(jí)對(duì)最終的覆蓋效果有極大的影響,文中以傳感器剩余能量為優(yōu)先級(jí),但以剩余能量為優(yōu)先級(jí)的處理順序沒有考慮覆蓋區(qū)域面積的影響,因此并不一定能保證傳感器的覆蓋區(qū)域面積最大。同時(shí),文中沒有考慮孤立傳感器或優(yōu)先級(jí)最高的傳感器的傳感方向,如圖2(a)所示S1~S5五個(gè)傳感器,假設(shè)它們的剩余能量,即優(yōu)先級(jí)從高到低,則S1的傳感方向最先被確定,由于S1的優(yōu)先級(jí)最高,其它傳感器的存在對(duì)它沒有影響,此時(shí)S1的傳感方向可以是4個(gè)可選方向中的任意一個(gè);由于S1~S4四個(gè)節(jié)點(diǎn)互不為鄰居,且它們的優(yōu)先級(jí)均高于S5,同理S2~S4的傳感方向也可以是4個(gè)可選方向中的任意一個(gè),若S1~S4最終選擇的方向如圖2(a)所示,此時(shí)S5的4個(gè)可選方向中,均存在重疊區(qū)域,顯然應(yīng)選擇重疊區(qū)域最小的S5,2方向。
本文傳感器節(jié)點(diǎn)以全局貪心的思想確定工作方向,以傳感器節(jié)點(diǎn)的最大一重覆蓋區(qū)域面積大小為優(yōu)先級(jí),最大一重覆蓋區(qū)域的定義與DGreedy算法中的Gi,j類似,即節(jié)點(diǎn)與鄰居間沒有重疊的區(qū)域,某一節(jié)點(diǎn)在某方向上的一重覆蓋區(qū)域面積越大,則該節(jié)點(diǎn)和方向越先被確定。如圖2(a)所示,S1~S4四個(gè)節(jié)點(diǎn)在一個(gè)方向上與S5均有重疊覆蓋區(qū)域,以S1為例,S1存在一個(gè)方向?yàn)橥暌恢馗采w,因此擁有最高優(yōu)先級(jí);同理,S2~S4擁有與S1相同的優(yōu)先級(jí)。因此S1~S4的傳感方向最先被確定,且選擇的方向均為完全一重覆蓋方向,如圖2(b)所示,此時(shí)S5的4個(gè)可選方向中,均為完全一重覆蓋,可依據(jù)固定順序或指向覆蓋區(qū)域中心等原則,選擇其中任一方向。顯然,圖2(b)的覆蓋效果好于圖2(a)。
改進(jìn)的Greedy算法描述如下:
2 實(shí)驗(yàn)及分析
下面通過模擬實(shí)驗(yàn)評(píng)估本文算法的性能,所有實(shí)驗(yàn)都用Matalb 7.4.0實(shí)現(xiàn)。實(shí)驗(yàn)中設(shè)定監(jiān)測區(qū)域大小為邊長500 m的正方形,不同數(shù)目的有向傳感器節(jié)點(diǎn)隨機(jī)部署在監(jiān)測區(qū)域中,傳感器的覆蓋角度為α=90°,傳感器可選方向數(shù)為P=4,傳感半徑Rs=60 m。比較了本文算法、DGreedy算法及傳感器隨機(jī)選擇工作方向的隨機(jī)算法Random算法的性能。
當(dāng)節(jié)點(diǎn)個(gè)數(shù)N=50時(shí),3種算法的覆蓋效果如圖3所示,圖中的圓形表示每個(gè)節(jié)點(diǎn)的可能覆蓋范圍,灰色扇形表示每個(gè)節(jié)點(diǎn)的實(shí)際覆蓋區(qū)域,顏色越深,表示覆蓋重疊數(shù)越多。很顯然,Random算法的覆蓋結(jié)果中重疊覆蓋區(qū)域最多,因此覆蓋率最低,本文算法覆蓋率最高。不同傳感器節(jié)點(diǎn)數(shù)目時(shí),3種算法的覆蓋率如圖4所示。由于本文算法每次都取一重覆蓋區(qū)域面積最大的傳感器節(jié)點(diǎn)及其傳感方向,使得整個(gè)網(wǎng)絡(luò)的一重覆蓋率較高,多重覆蓋率較低;DGreedy算法以剩余能量為優(yōu)先級(jí),選取一重覆蓋區(qū)域面積最大的方向,但優(yōu)先級(jí)最高的節(jié)點(diǎn)所選方向不一定是所有節(jié)點(diǎn)中一重覆蓋區(qū)域面積最大的方向,因此覆蓋率較本文算法有所降低;Random算法節(jié)點(diǎn)的覆蓋方向隨機(jī)產(chǎn)生,重疊覆蓋區(qū)域最多,因此覆蓋率最低。
3 結(jié)語
有向傳感器由于傳感范圍有限,其覆蓋問題比基于全向感知模型的傳感器覆蓋更復(fù)雜。有向傳感器的覆蓋問題,就是按某種原則選擇每個(gè)傳感器的工作方向,以減少重疊覆蓋區(qū)域,增加一重覆蓋區(qū)域。本文以傳感器最大一重覆蓋區(qū)域面積作為優(yōu)先級(jí),以全局貪心原則確定傳感器的工作方向,旨在調(diào)度傳感器的工作方向以覆蓋盡可能大的區(qū)域。通過仿真實(shí)驗(yàn),與DGreedy算法和Random算法進(jìn)行比較,驗(yàn)證了本文有向傳感器網(wǎng)絡(luò)覆蓋增強(qiáng)算法的有效性。