一種有向網(wǎng)絡(luò)目標(biāo)概率覆蓋增強(qiáng)算法*

范興剛,張哲鋮,王晨浩,陶 俊

(1.浙江工業(yè)大學(xué)之江學(xué)院,浙江 紹興 310023;2.浙江工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,杭州 310023)

如何部署和調(diào)度節(jié)點(diǎn),高效實(shí)現(xiàn)監(jiān)控區(qū)域內(nèi)覆蓋要求,是有向傳感器網(wǎng)絡(luò)的研究熱點(diǎn)之一[1-5]。目標(biāo)覆蓋是用少量的節(jié)點(diǎn)實(shí)現(xiàn)給定目標(biāo)的覆蓋要求,本文針對(duì)有向感知網(wǎng)絡(luò)的目標(biāo)覆蓋展開(kāi)研究。有向節(jié)點(diǎn)的感知區(qū)域不僅和節(jié)點(diǎn)的位置有關(guān),也和節(jié)點(diǎn)的感知方向密切相關(guān)。很多研究者從選擇和調(diào)整節(jié)點(diǎn)感知方向來(lái)實(shí)現(xiàn)目標(biāo)覆蓋要求。Ai and Abouzeid最先研究了有向網(wǎng)絡(luò)的目標(biāo)覆蓋問(wèn)題,選擇覆蓋最多目標(biāo)的感知方向,用最少節(jié)點(diǎn)實(shí)現(xiàn)目標(biāo)的最大覆蓋[6];Shahrokhzadeh B等人基于博弈論研究了目標(biāo)覆蓋,根據(jù)目標(biāo)覆蓋貢獻(xiàn)和轉(zhuǎn)動(dòng)能耗,設(shè)計(jì)節(jié)點(diǎn)效能函數(shù),通過(guò)最大節(jié)點(diǎn)效能函數(shù)實(shí)現(xiàn)網(wǎng)絡(luò)壽命最大化[7-8]。如果在隨機(jī)部署的網(wǎng)絡(luò)中,有向節(jié)點(diǎn)是異構(gòu)的,有不同的半徑,角度和代價(jià),而且不同目標(biāo)的覆蓋要求也不一樣。在這種情況下,Zhu等人研究了如何用最小的代價(jià)實(shí)現(xiàn)不同目標(biāo)覆蓋要求[9]。以上研究都是從固定的和預(yù)定義的感知扇區(qū)集合中選擇提供最大覆蓋率的合適扇區(qū)。而在文獻(xiàn)[10-11]中,節(jié)點(diǎn)可以轉(zhuǎn)動(dòng)到任意方向,Wu等人用最少的節(jié)點(diǎn),較低的能耗實(shí)現(xiàn)目標(biāo)覆蓋要求[10]。Jia等人選擇具有最大剩余能量的方向組建覆蓋集合,實(shí)現(xiàn)不同要求的目標(biāo)覆蓋,延長(zhǎng)網(wǎng)絡(luò)壽命[11]。Cai 等人根據(jù)目標(biāo)的權(quán)值。選擇節(jié)點(diǎn)的最優(yōu)感知方向,實(shí)現(xiàn)目標(biāo)覆蓋[12]。

實(shí)際上,節(jié)點(diǎn)對(duì)目標(biāo)的感知概率隨著距離的增大而減少,而且目標(biāo)感知概率是多個(gè)節(jié)點(diǎn)聯(lián)合感知的結(jié)果。同時(shí),目標(biāo)并不一定100%的覆蓋才能達(dá)到要求,只要達(dá)到一定的感知概率,就能滿(mǎn)足性能要求。利用概率感知模型研究網(wǎng)絡(luò)的區(qū)域覆蓋成為近年的研究熱點(diǎn)[13-18]。Zorbas等人在概率感知模型下,通過(guò)構(gòu)建網(wǎng)絡(luò)的主連通集(CDS),選擇目標(biāo)覆蓋集的方法實(shí)現(xiàn)目標(biāo)的概率覆蓋[14]。Fan等人利用有向概率感知模型實(shí)現(xiàn)了有向節(jié)點(diǎn)的概率柵欄覆蓋[15]。而關(guān)于目標(biāo)的有向概率覆蓋還鮮有研究。作者構(gòu)建覆蓋空洞的修補(bǔ)半徑,移動(dòng)節(jié)點(diǎn)在修補(bǔ)圓上選擇保持連通的修補(bǔ)位置;增強(qiáng)區(qū)域概率覆蓋[16]。

在有向概率柵欄覆蓋基礎(chǔ)上,本文利用節(jié)點(diǎn)之間的位置關(guān)系,結(jié)合聯(lián)合概率感知,研究如何擴(kuò)大可用節(jié)點(diǎn)選擇范圍,利用節(jié)點(diǎn)的轉(zhuǎn)動(dòng)能力,實(shí)現(xiàn)目標(biāo)的有向概率覆蓋。提出一種基于目標(biāo)概率覆蓋圓的目標(biāo)增強(qiáng)覆蓋方法TarpC(target coverage enhancing scheme based on probabilistic sensing circle)。優(yōu)化節(jié)點(diǎn)感知方向,提高目標(biāo)概率覆蓋率,增大部署效率。

本文余下章節(jié)安排如下:第1節(jié)描述網(wǎng)絡(luò)模型。第2節(jié)詳細(xì)介紹基于目標(biāo)概率覆蓋圓的目標(biāo)增強(qiáng)覆蓋方法(TarpC)。第3節(jié)通過(guò)仿真實(shí)驗(yàn)對(duì)提出的算法進(jìn)行性能評(píng)估。第4節(jié)總結(jié)全文并介紹下一步工作。

1 相關(guān)模型和定義

要研究有向概率目標(biāo)覆蓋,先給出有向概率感知模型。

定義1有向概率覆蓋模型

采用6元組(Pmin,Ls,A0,S,α,θ)表示(如圖1所示)。其中Pmin表示概率閾值,當(dāng)目標(biāo)點(diǎn)的感知概率大于Pmin時(shí),我們就認(rèn)為這個(gè)目標(biāo)點(diǎn)可以被完全監(jiān)測(cè)到;Ls=(x,y)表示節(jié)點(diǎn)的位置;A0為單個(gè)節(jié)點(diǎn)的感知區(qū)域閾值,在這個(gè)區(qū)域內(nèi)的目標(biāo)都以概率1被感知;S表示單個(gè)節(jié)點(diǎn)的概率感知區(qū)域,在這個(gè)區(qū)域內(nèi)的目標(biāo)感知概率≥Pmin;α表示節(jié)點(diǎn)的感知方向;θ為感知角度,在這個(gè)角度內(nèi)的目標(biāo)能被節(jié)點(diǎn)概率感知。

在單個(gè)節(jié)點(diǎn)的作用下,目標(biāo)感知概率通過(guò)式(1)來(lái)計(jì)算。其中,d表示傳感器與目標(biāo)t之間的距離,P(d)表示節(jié)點(diǎn)對(duì)目標(biāo)的感知概率,λ表示目標(biāo)與節(jié)點(diǎn)連線(xiàn)和感知方向的夾角,μ為感知強(qiáng)度衰減系數(shù)。

圖1 有向柵欄感知模型

(1)

在圖1中目標(biāo)B,E滿(mǎn)足概率覆蓋要求。目標(biāo)C,D初始感知概率小于概率閾值。在概率感知模型下,目標(biāo)可以被多個(gè)節(jié)點(diǎn)聯(lián)合感知的。

定義2目標(biāo)聯(lián)合感知概率

在多個(gè)節(jié)點(diǎn)的綜合作用下,目標(biāo)t感知概率為式(2):

(2)

式中:Sn表示可以感知目標(biāo)t的所有節(jié)點(diǎn),而Pn(Sn,t)則表示事件t的n個(gè)節(jié)點(diǎn)的聯(lián)合檢測(cè)率,即事件的感知概率。

當(dāng)目標(biāo)的聯(lián)合感知概率Pn(Sn,t)≥Pmin,就稱(chēng)這個(gè)目標(biāo)實(shí)現(xiàn)了概率覆蓋。

我們研究的問(wèn)題就是:在感興趣區(qū)域中,隨機(jī)部署N個(gè)有向節(jié)點(diǎn),M個(gè)目標(biāo),如何利用節(jié)點(diǎn)的轉(zhuǎn)動(dòng)能力,擴(kuò)大可使用節(jié)點(diǎn)范圍,使盡可能多的目標(biāo)實(shí)現(xiàn)概率覆蓋。

2 目標(biāo)聯(lián)合感知概率分析

(3)

給定Pmin可以得到節(jié)點(diǎn)的概率感知區(qū)域S,再結(jié)合感知角度θ可以得到節(jié)點(diǎn)概率感知區(qū)域S的半徑rmin(式(3))。

(4)

(5)

定義3目標(biāo)概率覆蓋圓

以目標(biāo)為圓心,以某個(gè)距離為半徑畫(huà)一個(gè)圓,圓內(nèi)任一未覆蓋此目標(biāo)的節(jié)點(diǎn)只要調(diào)整感知方向,使此目標(biāo)在其感知角度內(nèi),目標(biāo)的聯(lián)合感知率就能達(dá)到最小感知率要求,則這個(gè)圓稱(chēng)為目標(biāo)概率覆蓋圓。

(6)

3 基于概率感知半徑的目標(biāo)覆蓋增強(qiáng)算法(TarpC)

由上面的分析可知,對(duì)于不滿(mǎn)足最小感知概率要求的目標(biāo),如果一個(gè)節(jié)點(diǎn)再對(duì)目標(biāo)貢獻(xiàn)感知概率Pd,目標(biāo)聯(lián)合感知概率就等于最小感知概率。根據(jù)這個(gè)原理我們提出一種目標(biāo)概率覆蓋增強(qiáng)算法(TarpC)。

3.1 算法的基本思想

TarpC算法的基本思想如下:運(yùn)用節(jié)點(diǎn)與目標(biāo)之間的位置關(guān)系,選擇有效覆蓋節(jié)點(diǎn)計(jì)算目標(biāo)的初始聯(lián)合感知概率,得到目標(biāo)的概率覆蓋圓。根據(jù)這個(gè)概率覆蓋圓,增大可使用節(jié)點(diǎn)數(shù)量,選擇最優(yōu)節(jié)點(diǎn),調(diào)整其感知方向,實(shí)現(xiàn)目標(biāo)概率覆蓋。

3.2 算法具體過(guò)程

TarpC算法偽代碼如圖2,參數(shù)的定義如表1所示。TarpC算法具體步驟如下:

Step1選擇覆蓋節(jié)點(diǎn)集合

計(jì)算每個(gè)節(jié)點(diǎn)的每個(gè)感知方向覆蓋節(jié)點(diǎn)數(shù),為節(jié)點(diǎn)選擇覆蓋目標(biāo)數(shù)最大的感知方向,覆蓋目標(biāo)數(shù)大于零的節(jié)點(diǎn)為覆蓋節(jié)點(diǎn)。

Step2計(jì)算每個(gè)目標(biāo)的初始感知概率

根據(jù)節(jié)點(diǎn)和目標(biāo)的位置關(guān)系,計(jì)算每個(gè)節(jié)點(diǎn)對(duì)每個(gè)目標(biāo)的感知概率。當(dāng)對(duì)目標(biāo)的最大感知概率大于最小概率閾值0.3時(shí),此節(jié)點(diǎn)標(biāo)注為覆蓋節(jié)點(diǎn),不再轉(zhuǎn)動(dòng)。否則,標(biāo)記為不可使用節(jié)點(diǎn)。

覆蓋節(jié)點(diǎn)集合作用下,根據(jù)式(2)計(jì)算每個(gè)目標(biāo)的初始聯(lián)合感知概率。

Step3確定目標(biāo)概率覆蓋圓

對(duì)于沒(méi)有滿(mǎn)足概率覆蓋要求的目標(biāo),確定其概率覆蓋半徑,得到概率覆蓋圓。

這個(gè)概率覆蓋圓內(nèi)的未使用節(jié)點(diǎn),變?yōu)楹蜻x可使用節(jié)點(diǎn)。

圖2 TarpC算法偽代碼

參數(shù)參數(shù)說(shuō)明M目標(biāo)集合N1覆蓋節(jié)點(diǎn)集合N2不可使用節(jié)點(diǎn)集合Ri第i個(gè)目標(biāo)的概率覆蓋半徑Pinitiali第i目標(biāo)的初始感知概率β節(jié)點(diǎn)的目標(biāo)感知方向Ca目標(biāo)覆蓋率Da部署效率

Step4選擇最佳節(jié)點(diǎn)

在每個(gè)概率覆蓋圓內(nèi),確定候選可使用節(jié)點(diǎn)與目標(biāo)的距離,選擇距離最小的節(jié)點(diǎn)轉(zhuǎn)動(dòng)來(lái)增強(qiáng)目標(biāo)覆蓋。如圖3中,目標(biāo)A的概率覆蓋半徑為R,在這個(gè)概率覆蓋圓內(nèi),有可使用節(jié)點(diǎn)B和C,到目標(biāo)A的距離分別為dB、dC,因?yàn)閐B

圖3 選擇最佳節(jié)點(diǎn)

Step5確定新覆蓋節(jié)點(diǎn)目標(biāo)方向

假設(shè)新覆蓋節(jié)點(diǎn)與目標(biāo)連線(xiàn)的夾角為β,則喚醒節(jié)點(diǎn)的目標(biāo)方向就是β,如圖3中,喚醒節(jié)點(diǎn)B的目標(biāo)感知方向就是β。

圖4 節(jié)點(diǎn)目標(biāo)感知方向

3.3 算法的理論分析

假設(shè)目標(biāo)的個(gè)數(shù)為m,移動(dòng)節(jié)點(diǎn)的數(shù)目為N,概率目標(biāo)覆蓋算法時(shí)間復(fù)雜度為O(m×N)。

由于在目標(biāo)覆蓋的增強(qiáng)過(guò)程中,節(jié)點(diǎn)只是轉(zhuǎn)動(dòng)。如果某個(gè)目標(biāo)附近沒(méi)有節(jié)點(diǎn),可通過(guò)聯(lián)合概率覆蓋達(dá)到概率覆蓋要求,也有可能即使考慮聯(lián)合概率感知也達(dá)不到概率覆蓋要求。因此達(dá)到概率覆蓋要求的目標(biāo)占總目標(biāo)的比例即目標(biāo)覆蓋率是反應(yīng)算法性能的一個(gè)關(guān)鍵指標(biāo)。

隨機(jī)部署節(jié)點(diǎn)實(shí)現(xiàn)目標(biāo)覆蓋要求時(shí),只有一小部分節(jié)點(diǎn)參與了目標(biāo)覆蓋。這是最小的節(jié)點(diǎn)數(shù)實(shí)現(xiàn)目標(biāo)覆蓋。從另一個(gè)角度考慮,能否充分利用已經(jīng)部署的節(jié)點(diǎn),部署增大目標(biāo)覆蓋。也就是效率問(wèn)題,參與目標(biāo)覆蓋的節(jié)點(diǎn)數(shù)在總節(jié)點(diǎn)數(shù)的比例即為部署效率。部署效率越高,越多的節(jié)點(diǎn)參與了目標(biāo)覆蓋,從而減少了節(jié)點(diǎn)浪費(fèi)。即部署效率是反應(yīng)算法性能的又一個(gè)指標(biāo)。

4 仿真結(jié)果

本文運(yùn)用MATLAB7.0對(duì)此算法進(jìn)行仿真,每組實(shí)驗(yàn)數(shù)據(jù)采用重復(fù)50次獨(dú)立實(shí)驗(yàn)取平均值的方式獲得。如果沒(méi)有特別指明,實(shí)驗(yàn)的默認(rèn)參數(shù)如表2所示。為了說(shuō)明算法的性能,我們選用文獻(xiàn)[10]的DCS-greedy算法和文獻(xiàn)[9]的NWCGA2算法進(jìn)行性能對(duì)比。在DCS-greedy算法中,距離節(jié)點(diǎn)越近的目標(biāo)權(quán)值越大,節(jié)點(diǎn)選擇權(quán)值最大的目標(biāo)實(shí)現(xiàn)覆蓋。在NWCGA2中,每個(gè)節(jié)點(diǎn)選擇覆蓋目標(biāo)數(shù)最多的感知方向,實(shí)現(xiàn)目標(biāo)覆蓋。為了一致,這2個(gè)算法都選擇rmin為節(jié)點(diǎn)的感知半徑。主要考察目標(biāo)覆蓋率和部署效率兩個(gè)性能指標(biāo)。

表2 實(shí)驗(yàn)參數(shù)

4.1 算法性能

算法本身的性能如圖5、圖6所示。由于節(jié)點(diǎn)僅能夠改變感知方向,不能移動(dòng)改變位置。當(dāng)節(jié)點(diǎn)數(shù)較少時(shí),有些目標(biāo)周?chē)鷽](méi)有節(jié)點(diǎn),僅靠轉(zhuǎn)動(dòng)不能實(shí)現(xiàn)概率目標(biāo)覆蓋。所以,當(dāng)區(qū)域中節(jié)點(diǎn)數(shù)較少時(shí),目標(biāo)覆蓋率較低只有67%左右。隨著總節(jié)點(diǎn)數(shù)的增加,目標(biāo)周?chē)墓?jié)點(diǎn)數(shù)也在增加,通過(guò)旋轉(zhuǎn)概率覆蓋目標(biāo)的可選節(jié)點(diǎn)增多,目標(biāo)覆蓋率逐漸增加。增大感知角度,根據(jù)式(3)節(jié)點(diǎn)概率感知半徑也相應(yīng)減少,并不能增大感知面積。所以,同樣的目標(biāo)概率感知閾值下,節(jié)點(diǎn)的概率覆蓋面積相同,改變感知角度并不能增大目標(biāo)覆蓋成功率。角度變小,覆蓋周?chē)哪繕?biāo)數(shù)減少?？梢允褂酶嗟墓?jié)點(diǎn)覆蓋同樣的目標(biāo)集合,從而提高算法的部署效率。

圖5 算法目標(biāo)覆蓋率

圖6 算法部署效率

4.2 感知概率閾值的影響

感知概率的影響如圖7、圖8所示,由有向概率感知模型的特點(diǎn)可知,感知概率閾值越大,單個(gè)節(jié)點(diǎn)概率感知區(qū)域越小,在節(jié)點(diǎn)概率感知區(qū)域內(nèi)的目標(biāo)數(shù)越少,對(duì)同一個(gè)目標(biāo)的感知概率越小。所以,3種算法的性能都隨著感知概率的增大而減少。

圖7 概率閾值VS目標(biāo)覆蓋率

圖8 概率閾值VS部署效率

對(duì)于沒(méi)有在任何一個(gè)節(jié)點(diǎn)的概率感知區(qū)域內(nèi)的目標(biāo),距離目標(biāo)較遠(yuǎn)的節(jié)點(diǎn)對(duì)這個(gè)目標(biāo)的感知概率

4.3 節(jié)點(diǎn)數(shù)的影響

節(jié)點(diǎn)數(shù)的影響如圖9、圖10所示。隨機(jī)部署的節(jié)點(diǎn)數(shù)越多,被覆蓋的目標(biāo)數(shù)越多,可使用的節(jié)點(diǎn)數(shù)越多,所以3個(gè)算法的性能隨著節(jié)點(diǎn)數(shù)的增多,目標(biāo)覆蓋率,部署效率逐漸提高。由于DCS-greedy只保證權(quán)值最大的目標(biāo)覆蓋,而NWCGA2算法使每個(gè)節(jié)點(diǎn)覆蓋最多的目標(biāo)。而TarpC算法在覆蓋最多目標(biāo)的基礎(chǔ)上,進(jìn)一步考慮了相鄰節(jié)點(diǎn)對(duì)目標(biāo)的聯(lián)合概率感知,一些沒(méi)有被單個(gè)節(jié)點(diǎn)概率感知區(qū)域覆蓋的目標(biāo),因?yàn)槁?lián)合感知很有可能達(dá)到感知概率閾值要求,從而提高目標(biāo)覆蓋率。同時(shí),盡管有些節(jié)點(diǎn)的概率感知區(qū)域沒(méi)有覆蓋目標(biāo),但很有可能對(duì)一些目標(biāo)有感知概率。所以,相對(duì)其他2種算法,TarpC算法具有較好的目標(biāo)覆蓋率和部署效率。

圖9 節(jié)點(diǎn)數(shù)VS目標(biāo)覆蓋率

圖10 目標(biāo)數(shù)VS目標(biāo)覆蓋率

5 結(jié)論

本文主要研究有向網(wǎng)絡(luò)的目標(biāo)概率覆蓋問(wèn)題,提出TarpC算法,利用聯(lián)合概率感知理論,提出目標(biāo)概率覆蓋圓模型,擴(kuò)大覆蓋節(jié)點(diǎn)集合,選擇最優(yōu)節(jié)點(diǎn)調(diào)整感知方向,實(shí)現(xiàn)目標(biāo)概率覆蓋。仿真結(jié)果證明TarpC算法可以提高目標(biāo)覆蓋率,增大部署效率。

連通是傳感器網(wǎng)絡(luò)的又一個(gè)基本性能要求,如何在實(shí)現(xiàn)概率目標(biāo)覆蓋的同時(shí),保持網(wǎng)絡(luò)的連通性是下一步要研究的內(nèi)容。