一種有向網絡目標概率覆蓋增強算法*

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

(1.浙江工業大學之江學院,浙江 紹興 310023;2.浙江工業大學計算機科學與技術學院,杭州 310023)

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

實際上,節點對目標的感知概率隨著距離的增大而減少,而且目標感知概率是多個節點聯合感知的結果。同時,目標并不一定100%的覆蓋才能達到要求,只要達到一定的感知概率,就能滿足性能要求。利用概率感知模型研究網絡的區域覆蓋成為近年的研究熱點[13-18]。Zorbas等人在概率感知模型下,通過構建網絡的主連通集(CDS),選擇目標覆蓋集的方法實現目標的概率覆蓋[14]。Fan等人利用有向概率感知模型實現了有向節點的概率柵欄覆蓋[15]。而關于目標的有向概率覆蓋還鮮有研究。作者構建覆蓋空洞的修補半徑,移動節點在修補圓上選擇保持連通的修補位置;增強區域概率覆蓋[16]。

在有向概率柵欄覆蓋基礎上,本文利用節點之間的位置關系,結合聯合概率感知,研究如何擴大可用節點選擇范圍,利用節點的轉動能力,實現目標的有向概率覆蓋。提出一種基于目標概率覆蓋圓的目標增強覆蓋方法TarpC(target coverage enhancing scheme based on probabilistic sensing circle)。優化節點感知方向,提高目標概率覆蓋率,增大部署效率。

本文余下章節安排如下:第1節描述網絡模型。第2節詳細介紹基于目標概率覆蓋圓的目標增強覆蓋方法(TarpC)。第3節通過仿真實驗對提出的算法進行性能評估。第4節總結全文并介紹下一步工作。

1 相關模型和定義

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

定義1有向概率覆蓋模型

采用6元組(Pmin,Ls,A0,S,α,θ)表示(如圖1所示)。其中Pmin表示概率閾值,當目標點的感知概率大于Pmin時,我們就認為這個目標點可以被完全監測到;Ls=(x,y)表示節點的位置;A0為單個節點的感知區域閾值,在這個區域內的目標都以概率1被感知;S表示單個節點的概率感知區域,在這個區域內的目標感知概率≥Pmin;α表示節點的感知方向;θ為感知角度,在這個角度內的目標能被節點概率感知。

在單個節點的作用下,目標感知概率通過式(1)來計算。其中,d表示傳感器與目標t之間的距離,P(d)表示節點對目標的感知概率,λ表示目標與節點連線和感知方向的夾角,μ為感知強度衰減系數。

圖1 有向柵欄感知模型

(1)

在圖1中目標B,E滿足概率覆蓋要求。目標C,D初始感知概率小于概率閾值。在概率感知模型下,目標可以被多個節點聯合感知的。

定義2目標聯合感知概率

在多個節點的綜合作用下,目標t感知概率為式(2):

(2)

式中:Sn表示可以感知目標t的所有節點,而Pn(Sn,t)則表示事件t的n個節點的聯合檢測率,即事件的感知概率。

當目標的聯合感知概率Pn(Sn,t)≥Pmin,就稱這個目標實現了概率覆蓋。

我們研究的問題就是:在感興趣區域中,隨機部署N個有向節點,M個目標,如何利用節點的轉動能力,擴大可使用節點范圍,使盡可能多的目標實現概率覆蓋。

2 目標聯合感知概率分析

(3)

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

(4)

(5)

定義3目標概率覆蓋圓

以目標為圓心,以某個距離為半徑畫一個圓,圓內任一未覆蓋此目標的節點只要調整感知方向,使此目標在其感知角度內,目標的聯合感知率就能達到最小感知率要求,則這個圓稱為目標概率覆蓋圓。

(6)

3 基于概率感知半徑的目標覆蓋增強算法(TarpC)

由上面的分析可知,對于不滿足最小感知概率要求的目標,如果一個節點再對目標貢獻感知概率Pd,目標聯合感知概率就等于最小感知概率。根據這個原理我們提出一種目標概率覆蓋增強算法(TarpC)。

3.1 算法的基本思想

TarpC算法的基本思想如下:運用節點與目標之間的位置關系,選擇有效覆蓋節點計算目標的初始聯合感知概率,得到目標的概率覆蓋圓。根據這個概率覆蓋圓,增大可使用節點數量,選擇最優節點,調整其感知方向,實現目標概率覆蓋。

3.2 算法具體過程

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

Step1選擇覆蓋節點集合

計算每個節點的每個感知方向覆蓋節點數,為節點選擇覆蓋目標數最大的感知方向,覆蓋目標數大于零的節點為覆蓋節點。

Step2計算每個目標的初始感知概率

根據節點和目標的位置關系,計算每個節點對每個目標的感知概率。當對目標的最大感知概率大于最小概率閾值0.3時,此節點標注為覆蓋節點,不再轉動。否則,標記為不可使用節點。

覆蓋節點集合作用下,根據式(2)計算每個目標的初始聯合感知概率。

Step3確定目標概率覆蓋圓

對于沒有滿足概率覆蓋要求的目標,確定其概率覆蓋半徑,得到概率覆蓋圓。

這個概率覆蓋圓內的未使用節點,變為候選可使用節點。

圖2 TarpC算法偽代碼

參數參數說明M目標集合N1覆蓋節點集合N2不可使用節點集合Ri第i個目標的概率覆蓋半徑Pinitiali第i目標的初始感知概率β節點的目標感知方向Ca目標覆蓋率Da部署效率

Step4選擇最佳節點

在每個概率覆蓋圓內,確定候選可使用節點與目標的距離,選擇距離最小的節點轉動來增強目標覆蓋。如圖3中,目標A的概率覆蓋半徑為R,在這個概率覆蓋圓內,有可使用節點B和C,到目標A的距離分別為dB、dC,因為dB

圖3 選擇最佳節點

Step5確定新覆蓋節點目標方向

假設新覆蓋節點與目標連線的夾角為β,則喚醒節點的目標方向就是β,如圖3中,喚醒節點B的目標感知方向就是β。

圖4 節點目標感知方向

3.3 算法的理論分析

假設目標的個數為m,移動節點的數目為N,概率目標覆蓋算法時間復雜度為O(m×N)。

由于在目標覆蓋的增強過程中,節點只是轉動。如果某個目標附近沒有節點,可通過聯合概率覆蓋達到概率覆蓋要求,也有可能即使考慮聯合概率感知也達不到概率覆蓋要求。因此達到概率覆蓋要求的目標占總目標的比例即目標覆蓋率是反應算法性能的一個關鍵指標。

隨機部署節點實現目標覆蓋要求時,只有一小部分節點參與了目標覆蓋。這是最小的節點數實現目標覆蓋。從另一個角度考慮,能否充分利用已經部署的節點,部署增大目標覆蓋。也就是效率問題,參與目標覆蓋的節點數在總節點數的比例即為部署效率。部署效率越高,越多的節點參與了目標覆蓋,從而減少了節點浪費。即部署效率是反應算法性能的又一個指標。

4 仿真結果

本文運用MATLAB7.0對此算法進行仿真,每組實驗數據采用重復50次獨立實驗取平均值的方式獲得。如果沒有特別指明,實驗的默認參數如表2所示。為了說明算法的性能,我們選用文獻[10]的DCS-greedy算法和文獻[9]的NWCGA2算法進行性能對比。在DCS-greedy算法中,距離節點越近的目標權值越大,節點選擇權值最大的目標實現覆蓋。在NWCGA2中,每個節點選擇覆蓋目標數最多的感知方向,實現目標覆蓋。為了一致,這2個算法都選擇rmin為節點的感知半徑。主要考察目標覆蓋率和部署效率兩個性能指標。

表2 實驗參數

4.1 算法性能

算法本身的性能如圖5、圖6所示。由于節點僅能夠改變感知方向,不能移動改變位置。當節點數較少時,有些目標周圍沒有節點,僅靠轉動不能實現概率目標覆蓋。所以,當區域中節點數較少時,目標覆蓋率較低只有67%左右。隨著總節點數的增加,目標周圍的節點數也在增加,通過旋轉概率覆蓋目標的可選節點增多,目標覆蓋率逐漸增加。增大感知角度,根據式(3)節點概率感知半徑也相應減少,并不能增大感知面積。所以,同樣的目標概率感知閾值下,節點的概率覆蓋面積相同,改變感知角度并不能增大目標覆蓋成功率。角度變小,覆蓋周圍的目標數減少。可以使用更多的節點覆蓋同樣的目標集合,從而提高算法的部署效率。

圖5 算法目標覆蓋率

圖6 算法部署效率

4.2 感知概率閾值的影響

感知概率的影響如圖7、圖8所示,由有向概率感知模型的特點可知,感知概率閾值越大,單個節點概率感知區域越小,在節點概率感知區域內的目標數越少,對同一個目標的感知概率越小。所以,3種算法的性能都隨著感知概率的增大而減少。

圖7 概率閾值VS目標覆蓋率

圖8 概率閾值VS部署效率

對于沒有在任何一個節點的概率感知區域內的目標,距離目標較遠的節點對這個目標的感知概率

4.3 節點數的影響

節點數的影響如圖9、圖10所示。隨機部署的節點數越多,被覆蓋的目標數越多,可使用的節點數越多,所以3個算法的性能隨著節點數的增多,目標覆蓋率,部署效率逐漸提高。由于DCS-greedy只保證權值最大的目標覆蓋,而NWCGA2算法使每個節點覆蓋最多的目標。而TarpC算法在覆蓋最多目標的基礎上,進一步考慮了相鄰節點對目標的聯合概率感知,一些沒有被單個節點概率感知區域覆蓋的目標,因為聯合感知很有可能達到感知概率閾值要求,從而提高目標覆蓋率。同時,盡管有些節點的概率感知區域沒有覆蓋目標,但很有可能對一些目標有感知概率。所以,相對其他2種算法,TarpC算法具有較好的目標覆蓋率和部署效率。

圖9 節點數VS目標覆蓋率

圖10 目標數VS目標覆蓋率

5 結論

本文主要研究有向網絡的目標概率覆蓋問題,提出TarpC算法,利用聯合概率感知理論,提出目標概率覆蓋圓模型,擴大覆蓋節點集合,選擇最優節點調整感知方向,實現目標概率覆蓋。仿真結果證明TarpC算法可以提高目標覆蓋率,增大部署效率。

連通是傳感器網絡的又一個基本性能要求,如何在實現概率目標覆蓋的同時,保持網絡的連通性是下一步要研究的內容。