周有為，張 君，晁志超

（重慶通信學院 重慶 400035）

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

1 傳感器網(wǎng)絡(luò)部署和覆蓋模型

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

無線傳感器網(wǎng)絡(luò)的覆蓋感知模型主要有3種。

1）圓盤感知模型

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

2）概率感知模型

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

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

3）有向感知模型

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

有向傳感器具有多個感知方向，工作方向的感應(yīng)范圍稱作它的覆蓋區(qū)域。因此，有向傳感器的覆蓋區(qū)域是由其位置和工作方向共同決定的。在網(wǎng)絡(luò)隨機部署后，不同傳感器的覆蓋區(qū)域可能相互重疊。所以需要調(diào)度傳感器工作在適當?shù)姆较颍拐麄€網(wǎng)絡(luò)的覆蓋區(qū)域最大，即覆蓋盲區(qū)最小。

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

2 問題描述

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

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

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

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

3 求解算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)束語

文中針對無線傳感器網(wǎng)絡(luò)中的有向感知模型提出一種基于復雜網(wǎng)絡(luò)社團結(jié)構(gòu)劃分的覆蓋增強算法，在節(jié)點部署完成后，重新調(diào)整節(jié)點的感知方向，增強網(wǎng)絡(luò)的覆蓋性能。同時該算法是完全分布式的，所采用的社團結(jié)構(gòu)劃分算法能夠分析的節(jié)點數(shù)目能夠達到百萬個，適用于無線傳感器網(wǎng)絡(luò)大規(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)芳.無線傳感器網(wǎng)絡(luò)覆蓋控制技術(shù)研究[D].長沙:國防科學技術(shù)大學.博士，2008.

[7]姜楠.無線傳感器網(wǎng)絡(luò)自組織演化模型及其關(guān)鍵技術(shù)研究[D].南京:南京航空航天大學.博士，2008.

[8]蘇羽.傳感器網(wǎng)絡(luò)中的無尺度路由問題 [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]解鄒，汪小帆.復雜網(wǎng)絡(luò)中的社團結(jié)構(gòu)分析算法研究綜述[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.