無線傳感器網絡低復雜度覆蓋算法研究

中國船舶重工集團公司第七一六研究所 莊 強

無線傳感器網絡低復雜度覆蓋算法研究

中國船舶重工集團公司第七一六研究所 莊 強

無線傳感器網絡的應用基礎是網絡覆蓋，傳感節點能量有限、存儲及運算能力受限等特點決定了覆蓋算法的低復雜度。本文通過研究若干鄰居節點對某一節點的覆蓋情況，判定該節點是否為冗余節點，提出了低復雜度覆蓋算法。

無線傳感器網絡；低復雜度；覆蓋算法；鄰居節點

1 引言

無線傳感器網絡是伴隨無線通信、嵌入式傳感器技術以及分布式信息處理技術的發展而新興的一種信息獲取技術[1]。網絡覆蓋是無線傳感器網絡的應用基礎，它體現了無線傳感器網絡對物理世界的感知能力，網絡覆蓋算法的優劣直接影響著網絡的感知質量。覆蓋控制問題，就是在節點所攜能量、計算、存儲能力和網絡通信帶寬等資源受到嚴重約束的條件下，通過對網絡中傳感器節點進行優化部署和合理調度等手段，有效地利用傳感器網絡極其有限的節點資源，最后達到改善傳感器網絡監控服務質量的目的[2]。

2 低復雜度算法

目前，有關判定節點是否為冗余節點的覆蓋算法主要有Perimeter Pruning算法和CNNN算法[3]。CNNN算法的復雜度相比Perimeter Pruning算法有一定程度的降低，我們在此基礎上進一步降低算法復雜度，以更好的滿足傳感節點低運算能力、低能耗的要求。

2.1 算法原理

為了便于研究，我們參照CNNN算法做如下定義：節點的鄰居節點集合為

根據CNNN算法，只有在節點有近鄰節點的情況下，它才有可能成為冗余節點。

如圖1所示，三個圓分別表示節點v、u的覆蓋圓及節點v的二倍感知半徑圓，即遠鄰節點所在范圍的最大值。已知節點v的覆蓋圓被近鄰節點u的覆蓋圓覆蓋了一部分，那么只需要考察節點v的覆蓋圓未被覆蓋的部分ADBE，即弧ADB和弧AEB所圍成的區域的覆蓋情況。能夠覆蓋上述區域的節點一定是v的鄰居節點，而且這些節點一定位于以v為圓心、以為半徑的圓的一定范圍內。

圖1 近鄰節點覆蓋情況

如圖2所示，扇形HAu和扇形FBu分別以點A、點B為圓心、以為半徑，其中H為線段vA的延長線與大圓的交點，F為線段vB的延長線與大圓的交點。由幾何知識可以證明，由弧Hu、弧Fu和弧HJF所圍成的范圍HuFJH，其中的節點不能覆蓋到ADBE區域；而由弧Hu、弧Fu和弧HKF所圍成的范圍HuFKH，其中的節點可以覆蓋到ADBE區域。因此，只需要考察HuFKH范圍內的節點對ADBE區域的覆蓋情況，即可完成節點v是否為冗余節點的判定。HuFKH區域的面積是u與v的距離函數，即。假設無線傳感節點均勻分布，則HuFKH區域內節點的數量與它的面積成正比。

圖2 能覆蓋ADBE區域的節點的范圍

如圖3所示，在鄰居節點u覆蓋的前提下，在HuFKH范圍內選擇一個節點w，它必能覆蓋ADBE區域的一部分。在節點w的覆蓋下，ADBE區域的未被覆蓋的區域變得更小。圖4中的圖形LGw是以Lv為直徑、LG為半徑的扇形，圖形MIw是以Mv為直徑、MI為半徑的扇形。然后繼續考察ADBE區域其余部分的覆蓋情況，也就是只需要考察HuFMwLH區域內的節點，其中表示方位。由于HuFMwLH區域的面積比HuFKH區域的面積更小，則需要考察的節點的數量也相應的減小了，從而進一步降低算法的復雜度。

圖3 第2個節點覆蓋情況

同理，在節點u、w覆蓋的前提下，在HuFMwLH范圍內找到第三個節點，它必能覆蓋ADBE區域內未被覆蓋的一部分。接下來再考察余下的覆蓋部分的覆蓋情況，則需要考察更小的范圍內的節點，算法的復雜度會更進一步降低。以此類推，直到v的覆蓋范圍被完全覆蓋、判定v是冗余節點，或遍歷相關范圍內的所有節點后判定v不是冗余節點，算法結束。

2.2 算法描述

（1）初始狀態時，每個節點在距離自己的范圍內廣播一個HELLO消息，消息包括本節點ID號和地理位置信息。每個節點隨機等待一段時間后再廣播，以免多個節點同時廣播HELLO消息造成信道沖突和信息丟失；

（2）每個節點收到其他節點的HELLO消息后，建立鄰居節點信息表，包括鄰居節點的方位、距離，并區分出近鄰節點和遠鄰節點；

（3）節點判斷是否有距離為0的節點，如果有，則自己為冗余節點，結束；

（4）節點如果沒有近鄰節點，或鄰居節點總數小于3，則自己不是冗余節點，結束；

（5）節點選擇一個距離自己最近的節點，考察該鄰居節點對自己的覆蓋圓的覆蓋情況，根據上述算法原理，再在確定范圍內選擇第二個鄰居節點，繼續考察第二個節點對自己的覆蓋情況，這樣依此類推直到完全覆蓋為止，則判定節點為這冗余節點，否則不是冗余節點，程序結束。

算法流程圖如圖4所示。

圖4 算法流程圖

3 結束語

本文研究了無線傳感器網絡覆蓋算法的復雜度問題，通過分析Perimeter Pruning算法和CNNN算法的原理，認為算法復雜度可以進一步降低，因而提出了一種低復雜度的覆蓋算法。本文提出的低復雜度覆蓋算法比另兩種算法的復雜度有明顯的降低。但是，算法對網絡模型過于理想化，沒有考慮到實際中的障礙、噪聲和實際通信距離的影響，今后的工作中將解決上述問題。

[1]孫利民,李建中,陳渝,等無線傳感器網絡[M].北京：清華大學出版社,2005

[2]趙大勝.無線傳感器網絡廣播與節點休眠算法中的節能覆蓋問題研究[D].武漢:華中科技大學,2005.