基于全局貪心的有向傳感器網絡覆蓋算法

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

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

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