基于全局貪心的有向傳感器網(wǎng)絡覆蓋算法

摘要：針對分布式貪心算法(DGreedy)以傳感器節(jié)點的剩余能量為優(yōu)先級，節(jié)點處理順序沒有考慮相鄰節(jié)點間的關系對網(wǎng)絡覆蓋率的影響，從而影響覆蓋率的不足，在此提出了一種新的有向傳感器網(wǎng)絡覆蓋算法?；谌重澬牡脑瓌t，以節(jié)點一重覆蓋區(qū)域面積的大小為優(yōu)先級，優(yōu)先確定一重覆蓋區(qū)域面積最大的傳感器節(jié)點方向，從而保證傳感器網(wǎng)絡的一重覆蓋區(qū)域面積更大，重疊覆蓋區(qū)域較少。對比實驗結(jié)果表明，該算法能有效提高覆蓋率。
關鍵詞：有向傳感器網(wǎng)絡；全局貪心；一重覆蓋；Matlab

0 引言
    覆蓋問題是無線傳感器網(wǎng)絡的一個基本問題，是近年來該領域的研究熱點。目前多數(shù)覆蓋控制的研究成果都是基于滿足全向性感知模型的傳感器進行的，但在實際應用中，許多有向傳感器，如視頻傳感器，已被廣泛應用于無線多媒體傳感器網(wǎng)絡中。與基于滿足全向性感知模型的無線傳感器網(wǎng)絡相比，有向傳感器網(wǎng)絡的覆蓋問題更復雜，是該領域的一個重要研究方向。
    Ma等首先提出了有向傳感器網(wǎng)絡的概念，設計了一種有向傳感器感知模型，并研究了有向傳感器網(wǎng)絡的覆蓋完整性問題。文獻等都采用了基于虛擬勢場的思想進行有向傳感器網(wǎng)絡覆蓋控制。陶丹等在文獻中設計了一種方向可調(diào)的感知模型，并以此為基礎首先提出了基于虛擬勢場的有向傳感器網(wǎng)絡覆蓋增強算法，通過引入“質(zhì)心”的概念，將有向傳感器用質(zhì)心點代替，并將有向傳感器網(wǎng)絡的覆蓋問題轉(zhuǎn)化為質(zhì)心分布問題，質(zhì)心點在虛擬力的作用下運動，消除感知盲區(qū)和重疊區(qū)。傳統(tǒng)基于虛擬勢場的有向傳感器網(wǎng)絡覆蓋增強算法只判斷和調(diào)整方向，節(jié)點的調(diào)整量為固定值，針對這一問題，黃帥等在文獻中利用虛擬力與角度調(diào)整量間的關系，根據(jù)虛擬力的大小改變節(jié)點的角度調(diào)整量，提高了網(wǎng)絡的調(diào)整效率。但是，以上基于虛擬勢場思想的無線傳感器網(wǎng)絡覆蓋方法，每個節(jié)點均需計算多個相鄰節(jié)點的合力，節(jié)點受力隨轉(zhuǎn)動過程不斷變化，使得算法較復雜；且節(jié)點根據(jù)力矢量的大小和方向進行轉(zhuǎn)動，轉(zhuǎn)動角度取值過小會增加調(diào)整時間，取值過大則會引起頻繁的計算和傳感方向的反復調(diào)整，且因合力未必為0，可能導致調(diào)整過程中角度往復震蕩。文獻提出了一種分布式貪心算法(DGreedy)，以傳感器節(jié)點的剩余能量為優(yōu)先級，每個傳感器基于局部貪心原則選擇工作方向，使傳感器網(wǎng)絡覆蓋盡可能大的區(qū)域。但是，DGreedy算法受傳感器節(jié)點處理順序影響較大，以剩余能量為優(yōu)先級的方法沒有考慮節(jié)點問覆蓋區(qū)域的相互影響，從而影響整個網(wǎng)絡的覆蓋率。
    本文基于全局貪心原則，提出了一種有向傳感器網(wǎng)絡覆蓋算法。以節(jié)點各方向下一重覆蓋區(qū)域的大小為優(yōu)先級，優(yōu)先確定一重覆蓋區(qū)域面積最大的傳感器節(jié)點方向，保證了傳感器網(wǎng)絡的一重覆蓋區(qū)域面積更大，重疊覆蓋區(qū)域較少。對比實驗驗證了本文算法的有效性。

1 覆蓋算法
1．1 DGreedy算法
    分布式貪心算法DGreedy由程衛(wèi)芳等人提出，并應用于有向傳感器網(wǎng)絡覆蓋中。DGreedy假設傳感器節(jié)點不同方向的感應范圍互不重疊，4個可選方向的傳感器節(jié)點示例如圖1所示，圖中Si,j表示第i個傳感器的第j個方向。文中還假定所有傳感器節(jié)點具有相同的結(jié)構(gòu)。給每個傳感器分配一個彼此不同的優(yōu)先級，并定義Gi,j表示節(jié)點Si的第J個方向上，沒有被更高級的感應鄰居所覆蓋的面積。

    DGreedy算法具體描述如下：
   
1．2 改進的DGreedy算法
    DGreedy算法每個傳感器以局部貪心的原則確定工作方向，只要感應鄰居間的覆蓋消息能準確傳遞，就能在有限時間內(nèi)終止。但是，傳感器的決策順序，即優(yōu)先級對最終的覆蓋效果有極大的影響，文中以傳感器剩余能量為優(yōu)先級，但以剩余能量為優(yōu)先級的處理順序沒有考慮覆蓋區(qū)域面積的影響，因此并不一定能保證傳感器的覆蓋區(qū)域面積最大。同時，文中沒有考慮孤立傳感器或優(yōu)先級最高的傳感器的傳感方向，如圖2(a)所示S1～S5五個傳感器，假設它們的剩余能量，即優(yōu)先級從高到低，則S1的傳感方向最先被確定，由于S1的優(yōu)先級最高，其它傳感器的存在對它沒有影響，此時S1的傳感方向可以是4個可選方向中的任意一個；由于S1～S4四個節(jié)點互不為鄰居，且它們的優(yōu)先級均高于S5，同理S2～S4的傳感方向也可以是4個可選方向中的任意一個，若S1～S4最終選擇的方向如圖2(a)所示，此時S5的4個可選方向中，均存在重疊區(qū)域，顯然應選擇重疊區(qū)域最小的S5,2方向。

    本文傳感器節(jié)點以全局貪心的思想確定工作方向，以傳感器節(jié)點的最大一重覆蓋區(qū)域面積大小為優(yōu)先級，最大一重覆蓋區(qū)域的定義與DGreedy算法中的Gi,j類似，即節(jié)點與鄰居間沒有重疊的區(qū)域，某一節(jié)點在某方向上的一重覆蓋區(qū)域面積越大，則該節(jié)點和方向越先被確定。如圖2(a)所示，S1～S4四個節(jié)點在一個方向上與S5均有重疊覆蓋區(qū)域，以S1為例，S1存在一個方向為完一重覆蓋，因此擁有最高優(yōu)先級；同理，S2～S4擁有與S1相同的優(yōu)先級。因此S1～S4的傳感方向最先被確定，且選擇的方向均為完全一重覆蓋方向，如圖2(b)所示，此時S5的4個可選方向中，均為完全一重覆蓋，可依據(jù)固定順序或指向覆蓋區(qū)域中心等原則，選擇其中任一方向。顯然，圖2(b)的覆蓋效果好于圖2(a)。
    改進的Greedy算法描述如下：

   

2 實驗及分析
    下面通過模擬實驗評估本文算法的性能，所有實驗都用Matalb 7．4．0實現(xiàn)。實驗中設定監(jiān)測區(qū)域大小為邊長500 m的正方形，不同數(shù)目的有向傳感器節(jié)點隨機部署在監(jiān)測區(qū)域中，傳感器的覆蓋角度為α=90°，傳感器可選方向數(shù)為P=4，傳感半徑Rs=60 m。比較了本文算法、DGreedy算法及傳感器隨機選擇工作方向的隨機算法Random算法的性能。

    當節(jié)點個數(shù)N=50時，3種算法的覆蓋效果如圖3所示，圖中的圓形表示每個節(jié)點的可能覆蓋范圍，灰色扇形表示每個節(jié)點的實際覆蓋區(qū)域，顏色越深，表示覆蓋重疊數(shù)越多。很顯然，Random算法的覆蓋結(jié)果中重疊覆蓋區(qū)域最多，因此覆蓋率最低，本文算法覆蓋率最高。不同傳感器節(jié)點數(shù)目時，3種算法的覆蓋率如圖4所示。由于本文算法每次都取一重覆蓋區(qū)域面積最大的傳感器節(jié)點及其傳感方向，使得整個網(wǎng)絡的一重覆蓋率較高，多重覆蓋率較低；DGreedy算法以剩余能量為優(yōu)先級，選取一重覆蓋區(qū)域面積最大的方向，但優(yōu)先級最高的節(jié)點所選方向不一定是所有節(jié)點中一重覆蓋區(qū)域面積最大的方向，因此覆蓋率較本文算法有所降低；Random算法節(jié)點的覆蓋方向隨機產(chǎn)生，重疊覆蓋區(qū)域最多，因此覆蓋率最低。

3 結(jié)語
    有向傳感器由于傳感范圍有限，其覆蓋問題比基于全向感知模型的傳感器覆蓋更復雜。有向傳感器的覆蓋問題，就是按某種原則選擇每個傳感器的工作方向，以減少重疊覆蓋區(qū)域，增加一重覆蓋區(qū)域。本文以傳感器最大一重覆蓋區(qū)域面積作為優(yōu)先級，以全局貪心原則確定傳感器的工作方向，旨在調(diào)度傳感器的工作方向以覆蓋盡可能大的區(qū)域。通過仿真實驗，與DGreedy算法和Random算法進行比較，驗證了本文有向傳感器網(wǎng)絡覆蓋增強算法的有效性。