中國船舶重工集團(tuán)公司第七一六研究所 莊 強(qiáng)

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

中國船舶重工集團(tuán)公司第七一六研究所 莊 強(qiáng)

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

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

1 引言

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

2 低復(fù)雜度算法

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

2.1 算法原理

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

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

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

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

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

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

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

圖3 第2個(gè)節(jié)點(diǎn)覆蓋情況

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

2.2 算法描述

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

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

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

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

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

算法流程圖如圖4所示。

圖4 算法流程圖

3 結(jié)束語

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

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

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