一種基于有向感知模型的傳感器節(jié)點覆蓋算法

周有為，張 君，晁志超

（重慶通信學院 重慶 400035）

無線傳感器網絡具有大規(guī)模部署、自組織、拓撲結構動態(tài)性強、以數據為中心、與應用相關等特點。覆蓋控制能力是衡量無線傳感器網絡工作能力的主要標準之一。覆蓋控制作為傳感器網絡中的一個基本問題，反映了無線傳感器網絡所能提供的“感知”服務質量，其目的是獲取物理世界的信息。優(yōu)化傳感器網絡覆蓋對于合理分配網絡的空間資源，更好地完成環(huán)境感知、信息獲取任務以及提高網絡生存能力都具有重要的意義。

1 傳感器網絡部署和覆蓋模型

目前傳感器的部署方式通常有兩種。一種是受控部署，這種部署方式通常用于物理環(huán)境良好，人員易到達的區(qū)域，通常可以預先設計出節(jié)點的拓撲結構，從而進行針對性的部署；另一種部署方式為隨機部署，這種部署方式適用于人員難以到達的區(qū)域，通常采用大規(guī)模、高密度拋灑的方式部署節(jié)點。由于節(jié)點部署的隨機性，會造成大量的覆蓋重疊區(qū)和覆蓋盲區(qū)，需要采取相應的覆蓋策略進行調整，使監(jiān)控區(qū)域的覆蓋均衡，同時使無線傳感器網絡的覆蓋性能得到增強。

無線傳感器網絡的覆蓋感知模型主要有3種。

1）圓盤感知模型

在二維平面中，傳感器節(jié)點的感知范圍可以看作一個以節(jié)點為圓心，半徑為R的圓形區(qū)域，該圓形區(qū)域就是傳感器節(jié)點的感知區(qū)域，R是傳感器節(jié)點的感知半徑，在節(jié)點感知區(qū)域內的任意一點都能夠被監(jiān)測到。圓盤感知模型中，被監(jiān)控區(qū)域中的一點存在兩種狀態(tài)，要么被傳感器節(jié)點監(jiān)測，要么未被監(jiān)測，因此圓盤感知模型又被稱為布爾感知模型（Boolean Sensing Model）。

2）概率感知模型

圓盤感知模型的假設是傳感器對感知區(qū)域的監(jiān)測具有確定性，也就是說，只要是感知區(qū)域內的信息，傳感器節(jié)點就一定能夠感知。在實際的情況中，受外部環(huán)境因素的影響，傳感器節(jié)點的感知能力具有不確定性。一般說來，傳感器節(jié)點感知的信息和對目標的監(jiān)測與目標與節(jié)點之間的距離由較為密切的關系，感知節(jié)點與目標的距離越近，則傳感器節(jié)點感知的信息準確度越高。隨著目標與節(jié)點距離的增大，感知信息的不確定性也就越大。概率感知模型反映了這種不確定性。在概率感知模型中，傳感器節(jié)點s檢測到任意點p處的目標的概率為[1]：

其中，d（s，p）為目標點 p和節(jié)點 s之間的歐氏距離，參數α表示傳感器節(jié)點的感知能力及信號隨距離增大的衰減程度[2-3]。

3）有向感知模型

圓盤感知模型和概率感知模型的假設前提是傳感器節(jié)點的感知能力是全向的，在二維平面上，可以用圓來描述這種全向感知的能力，但是在某些場合，傳感器節(jié)點對目標的感知是有向的，節(jié)點的感知能力具有固定的朝向。例如，照相機或者視頻傳感器，類似于這樣的節(jié)點感知模型可以用有向感知模型來描述[4]。根據有向感知模型的方向是否可調以及方向的個數可以將有向感知模型分為3類：方向固定的感知模型、方向連續(xù)可調的感知模型和方向個數固定的感知模型。

有向傳感器具有多個感知方向，工作方向的感應范圍稱作它的覆蓋區(qū)域。因此，有向傳感器的覆蓋區(qū)域是由其位置和工作方向共同決定的。在網絡隨機部署后，不同傳感器的覆蓋區(qū)域可能相互重疊。所以需要調度傳感器工作在適當的方向，使整個網絡的覆蓋區(qū)域最大，即覆蓋盲區(qū)最小。

文獻[4]提出了一個固定方向個數的有向感知模型，并證明了利用最少的傳感器覆蓋指定區(qū)域中盡可能多的目標是一個NP問題，并且提出了一個貪心的集中式近似算法和分布式近似算法。文獻[5]基于固定方向個數的有向感知傳感器覆蓋指定目標的場景，調度傳感器節(jié)點的工作方向來滿足覆蓋要求，使其他節(jié)點睡眠，從而延長網絡生存時間。文獻[6]針對有向感知模型提出了調度節(jié)點工作方向使覆蓋區(qū)域最大的問題MDAC，并證明了MDAC是NP完全問題，進而提出了一種分布式貪心算法DGreedy解決MDAC問題。在此基礎上，利用局部迭代計算的可能覆蓋貢獻比反映網絡拓撲信息，提出了一個增強的算法PGreedy，讓覆蓋貢獻最大的節(jié)點優(yōu)先選擇工作方向。

2 問題描述

本文針對方向個數固定的有向感知模型，提出一種基于復雜網絡社團結構劃分的覆蓋增強算法。問題可以描述為，在區(qū)域C中隨機部署了N個傳感器節(jié)點，每個節(jié)點Ni具有s個感知方向（記作K1，K2，…Ks），在初始時刻每個傳感器隨機選擇一個方向為自己當前的感知方向。當節(jié)點部署完成后，需要采取策略重新調整部分節(jié)點的感知方向，使監(jiān)控區(qū)域的覆蓋率最大。求解目標是使監(jiān)控區(qū)域覆蓋率取得最大值的傳感器節(jié)點感知方向序列。

覆蓋率是指被工作節(jié)點覆蓋的區(qū)域面積占總面積的比例。在局部覆蓋的無線傳感器網絡中，通常用覆蓋率α這一指標來衡量網絡的覆蓋性能。

C代表整個監(jiān)測區(qū)域的面積，Ci表示第i個節(jié)點的覆蓋區(qū)域，N表示傳感器節(jié)點的數目。

根據問題描述，區(qū)域中所有節(jié)點的感知方向構成了一個序列（N1，N2，…Nn），Ni∈{K1，K2，…Ks}。 這樣的序列共有 sN個。對于任一序列，對應著一個網絡覆蓋率，問題可以轉化為求出使覆蓋率取得最大值的傳感器節(jié)點感知方向序列。本問題屬于最大有向區(qū)域覆蓋問題 （MDAC），文獻已經證明MDAC問題為NP完全問題。問題無法使用遍歷所有序列的方法求解，問題的規(guī)模與每個節(jié)點的感知方向個數以及網絡中節(jié)點的數目有關。傳感器網絡中的節(jié)點部署規(guī)模巨大，序列的個數與節(jié)點數目呈指數級增長關系。

3 求解算法

本文對監(jiān)控區(qū)域中的節(jié)點作出如下假設：

1）所有傳感器節(jié)點同構，所有節(jié)點的感知半徑和通信半徑相同，傳感器節(jié)點的通信半徑為感知半徑的2倍，即Rc=2Rs；

2）傳感器的每個方向有相同大小的感應區(qū)域，并且不同方向的感應區(qū)域互不重疊。本文假定每個傳感器節(jié)點具有固定方向個數的感知方向。如圖1所示，表示了具有4個互不相交的感知方向 K0、K1、K2、K3的節(jié)點；

3）每個傳感器知道自身的地理位置。

圖1 節(jié)點感知方向示意圖Fig.1 Diagrammatic sketch of Nodes'sensing direction

本文求解算法的過程是，傳感器節(jié)點完成隨機部署后，根據節(jié)點之間的通信半徑形成的節(jié)點網絡拓撲圖進行社團結構的劃分。“社團”這一概念沒有明確的定義，一般說來，各個社團內部的節(jié)點之間連接較為緊密，各個社團之間的連接較為稀疏。社團結構劃分完成后，對每個社團Ci分別求最優(yōu)的感知方向序列{…Kcn}，使αCi最大。各個社團的節(jié)點感知序列組合成為整個監(jiān)測區(qū)域的節(jié)點感知序列，得到求解問題的近似最優(yōu)解。

算法的思想是分社團降低求解問題的規(guī)模。所求解問題的時間復雜度為O（sN），N表示整個傳感器網絡的節(jié)點數量，可以達到百萬量級。通過社團劃分，將節(jié)點劃分到不同的子集中去。對于每個節(jié)點子集，使社團覆蓋率最優(yōu)的時間復雜度為，CN表示社團中節(jié)點的個數，社團劃分的算法可以迭代進行，直到達到易于求解的規(guī)模（CN＜＜N）。算法總的時間復雜度為 O（T））（CN＜＜N），其中 O（T）表示社團結構劃分算法的時間復雜度。

傳感器網絡是一種演化的復雜系統(tǒng)，傳感器網絡的節(jié)點數量級高，節(jié)點之間的連接關系復雜，整個網絡具有開放性、動態(tài)性、自組織、自適應的復雜性特點[7]。蘇羽[8]博士假設并證明了傳感器網絡是一種復雜網絡結構，并具有無標度網絡的特征。無線傳感器網絡具有復雜網絡的特征，可以用復雜網絡模型對無線傳感器網絡進行分析。

復雜網絡中的社團結構劃分算法有多種。由于無線傳感器網絡的節(jié)點數量級較高，采用Newman提出的凝聚算法[9]，該算法能夠分析的節(jié)點數目能夠達到百萬個，適用于無線傳感器網絡大規(guī)模高密度的特性。

其中||e||表示矩陣e中所有元素之和。凝聚算法的步驟如下[11]：

1）將每個節(jié)點獨立的看作一個社團，這樣在初始條件下網絡中一共有n個社團。

2）依次合并有邊相連的社團對，按照式下面給出的公式計算合并后的Q值增量，每次合并沿著使Q增大或者減小的方向進行。

3）重復第2）步，不斷合并社團，直到整個網絡都合并成為一個社團。這個過程最多執(zhí)行n-1次。

以上步驟完成后能夠得到一個社團結構分解的樹狀圖。在不同位置斷開就可以得到不同的社團結構。在這些社團結構中，選取局部最大的Q值，就可以得到最好的社團結構[11]。凝聚算法的時間復雜度為O（（m+n）n），其中m為網絡的邊的數目，n為網絡的節(jié)點數目。

算法的流程圖如圖2所示。

圖2 算法流程圖Fig.2 Flow diagram of algorithm

4 結束語

文中針對無線傳感器網絡中的有向感知模型提出一種基于復雜網絡社團結構劃分的覆蓋增強算法，在節(jié)點部署完成后，重新調整節(jié)點的感知方向，增強網絡的覆蓋性能。同時該算法是完全分布式的，所采用的社團結構劃分算法能夠分析的節(jié)點數目能夠達到百萬個，適用于無線傳感器網絡大規(guī)模部署的特點。

[1]Rappaport.T.S.Wireless Communications:Principles and Practice[M].New Jersey:Prentice Hall；1996.

[2]S.S.Dhillon， K.Chakrabarty， S.S.Iyengar， editors.Sensor Placement for Grid Coverage under Imprecise Detections[C]//International Conferrence on Infomation Fusion，2002.

[3]S.S.Dhillon KC，editor.Sensor Placement for Effective Coverage and Surveillance in Distributed Sensor Networks[C]//Wireless Communications and Networking Conference（WCNC）； 2003.

[4]Ai J，Abouzeid A A.Coverage by Directional Sensors in Randomly Deployed Wireless Sensor Networks [J].Combinatorial Optimization，2006，11（1）:21-41.

[5]Cai Y，Lou W，Li M，et al.Target-oriented scheduling in directional sensor networks[C].lEEE Infocom，2007.

[6]程衛(wèi)芳.無線傳感器網絡覆蓋控制技術研究[D].長沙:國防科學技術大學.博士，2008.

[7]姜楠.無線傳感器網絡自組織演化模型及其關鍵技術研究[D].南京:南京航空航天大學.博士，2008.

[8]蘇羽.傳感器網絡中的無尺度路由問題 [D].沈陽:東北大學，2005

[9]Newman M E J.Fast Algorithm for detecting community structure in networks[J].Physrev E，2004，69（6）:066133.

[10]Newman M E J，Givran M.Finding and evaluating community structure in networks[J].Phys rev E，2004，69（2）:026113.

[11]解鄒，汪小帆.復雜網絡中的社團結構分析算法研究綜述[J].復雜系統(tǒng)與復雜性科學，2005，2（3）:1-12.

XIE Zhou，WANG Xiao-fan.An overview of algorithms for analyzing community structure in complex networks[J].Compiex Systems and Complexity Science，2005，2（3）:1-12.