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

無線傳感器網(wǎng)絡低復雜度覆蓋算法研究

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

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

無線傳感器網(wǎng)絡；低復雜度；覆蓋算法；鄰居節(jié)點

1 引言

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

2 低復雜度算法

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

2.1 算法原理

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

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

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

圖1 近鄰節(jié)點覆蓋情況

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

圖2 能覆蓋ADBE區(qū)域的節(jié)點的范圍

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

圖3 第2個節(jié)點覆蓋情況

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

2.2 算法描述

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

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

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

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

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

算法流程圖如圖4所示。

圖4 算法流程圖

3 結束語

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

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

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