一种基于有向感知模型的传感器节点覆盖算法

周有为，张 君，晁志超

（重庆通信学院 重庆 400035）

无线传感器网络具有大规模部署、自组织、拓扑结构动态性强、以数据为中心、与应用相关等特点。覆盖控制能力是衡量无线传感器网络工作能力的主要标准之一。覆盖控制作为传感器网络中的一个基本问题，反映了无线传感器网络所能提供的“感知”服务质量，其目的是获取物理世界的信息。优化传感器网络覆盖对于合理分配网络的空间资源，更好地完成环境感知、信息获取任务以及提高网络生存能力都具有重要的意义。

1 传感器网络部署和覆盖模型

目前传感器的部署方式通常有两种。一种是受控部署，这种部署方式通常用于物理环境良好，人员易到达的区域，通常可以预先设计出节点的拓扑结构，从而进行针对性的部署；另一种部署方式为随机部署，这种部署方式适用于人员难以到达的区域，通常采用大规模、高密度抛洒的方式部署节点。由于节点部署的随机性，会造成大量的覆盖重叠区和覆盖盲区，需要采取相应的覆盖策略进行调整，使监控区域的覆盖均衡，同时使无线传感器网络的覆盖性能得到增强。

无线传感器网络的覆盖感知模型主要有3种。

1）圆盘感知模型

在二维平面中，传感器节点的感知范围可以看作一个以节点为圆心，半径为R的圆形区域，该圆形区域就是传感器节点的感知区域，R是传感器节点的感知半径，在节点感知区域内的任意一点都能够被监测到。圆盘感知模型中，被监控区域中的一点存在两种状态，要么被传感器节点监测，要么未被监测，因此圆盘感知模型又被称为布尔感知模型（Boolean Sensing Model）。

2）概率感知模型

圆盘感知模型的假设是传感器对感知区域的监测具有确定性，也就是说，只要是感知区域内的信息，传感器节点就一定能够感知。在实际的情况中，受外部环境因素的影响，传感器节点的感知能力具有不确定性。一般说来，传感器节点感知的信息和对目标的监测与目标与节点之间的距离由较为密切的关系，感知节点与目标的距离越近，则传感器节点感知的信息准确度越高。随着目标与节点距离的增大，感知信息的不确定性也就越大。概率感知模型反映了这种不确定性。在概率感知模型中，传感器节点s检测到任意点p处的目标的概率为[1]：

其中，d（s，p）为目标点 p和节点 s之间的欧氏距离，参数α表示传感器节点的感知能力及信号随距离增大的衰减程度[2-3]。

3）有向感知模型

圆盘感知模型和概率感知模型的假设前提是传感器节点的感知能力是全向的，在二维平面上，可以用圆来描述这种全向感知的能力，但是在某些场合，传感器节点对目标的感知是有向的，节点的感知能力具有固定的朝向。例如，照相机或者视频传感器，类似于这样的节点感知模型可以用有向感知模型来描述[4]。根据有向感知模型的方向是否可调以及方向的个数可以将有向感知模型分为3类：方向固定的感知模型、方向连续可调的感知模型和方向个数固定的感知模型。

有向传感器具有多个感知方向，工作方向的感应范围称作它的覆盖区域。因此，有向传感器的覆盖区域是由其位置和工作方向共同决定的。在网络随机部署后，不同传感器的覆盖区域可能相互重叠。所以需要调度传感器工作在适当的方向，使整个网络的覆盖区域最大，即覆盖盲区最小。

文献[4]提出了一个固定方向个数的有向感知模型，并证明了利用最少的传感器覆盖指定区域中尽可能多的目标是一个NP问题，并且提出了一个贪心的集中式近似算法和分布式近似算法。文献[5]基于固定方向个数的有向感知传感器覆盖指定目标的场景，调度传感器节点的工作方向来满足覆盖要求，使其他节点睡眠，从而延长网络生存时间。文献[6]针对有向感知模型提出了调度节点工作方向使覆盖区域最大的问题MDAC，并证明了MDAC是NP完全问题，进而提出了一种分布式贪心算法DGreedy解决MDAC问题。在此基础上，利用局部迭代计算的可能覆盖贡献比反映网络拓扑信息，提出了一个增强的算法PGreedy，让覆盖贡献最大的节点优先选择工作方向。

2 问题描述

本文针对方向个数固定的有向感知模型，提出一种基于复杂网络社团结构划分的覆盖增强算法。问题可以描述为，在区域C中随机部署了N个传感器节点，每个节点Ni具有s个感知方向（记作K1，K2，…Ks），在初始时刻每个传感器随机选择一个方向为自己当前的感知方向。当节点部署完成后，需要采取策略重新调整部分节点的感知方向，使监控区域的覆盖率最大。求解目标是使监控区域覆盖率取得最大值的传感器节点感知方向序列。

覆盖率是指被工作节点覆盖的区域面积占总面积的比例。在局部覆盖的无线传感器网络中，通常用覆盖率α这一指标来衡量网络的覆盖性能。

C代表整个监测区域的面积，Ci表示第i个节点的覆盖区域，N表示传感器节点的数目。

根据问题描述，区域中所有节点的感知方向构成了一个序列（N1，N2，…Nn），Ni∈{K1，K2，…Ks}。 这样的序列共有 sN个。对于任一序列，对应着一个网络覆盖率，问题可以转化为求出使覆盖率取得最大值的传感器节点感知方向序列。本问题属于最大有向区域覆盖问题 （MDAC），文献已经证明MDAC问题为NP完全问题。问题无法使用遍历所有序列的方法求解，问题的规模与每个节点的感知方向个数以及网络中节点的数目有关。传感器网络中的节点部署规模巨大，序列的个数与节点数目呈指数级增长关系。

3 求解算法

本文对监控区域中的节点作出如下假设：

1）所有传感器节点同构，所有节点的感知半径和通信半径相同，传感器节点的通信半径为感知半径的2倍，即Rc=2Rs；

2）传感器的每个方向有相同大小的感应区域，并且不同方向的感应区域互不重叠。本文假定每个传感器节点具有固定方向个数的感知方向。如图1所示，表示了具有4个互不相交的感知方向 K0、K1、K2、K3的节点；

3）每个传感器知道自身的地理位置。

图1 节点感知方向示意图Fig.1 Diagrammatic sketch of Nodes'sensing direction

本文求解算法的过程是，传感器节点完成随机部署后，根据节点之间的通信半径形成的节点网络拓扑图进行社团结构的划分。“社团”这一概念没有明确的定义，一般说来，各个社团内部的节点之间连接较为紧密，各个社团之间的连接较为稀疏。社团结构划分完成后，对每个社团Ci分别求最优的感知方向序列{…Kcn}，使αCi最大。各个社团的节点感知序列组合成为整个监测区域的节点感知序列，得到求解问题的近似最优解。

算法的思想是分社团降低求解问题的规模。所求解问题的时间复杂度为O（sN），N表示整个传感器网络的节点数量，可以达到百万量级。通过社团划分，将节点划分到不同的子集中去。对于每个节点子集，使社团覆盖率最优的时间复杂度为，CN表示社团中节点的个数，社团划分的算法可以迭代进行，直到达到易于求解的规模（CN＜＜N）。算法总的时间复杂度为 O（T））（CN＜＜N），其中 O（T）表示社团结构划分算法的时间复杂度。

传感器网络是一种演化的复杂系统，传感器网络的节点数量级高，节点之间的连接关系复杂，整个网络具有开放性、动态性、自组织、自适应的复杂性特点[7]。苏羽[8]博士假设并证明了传感器网络是一种复杂网络结构，并具有无标度网络的特征。无线传感器网络具有复杂网络的特征，可以用复杂网络模型对无线传感器网络进行分析。

复杂网络中的社团结构划分算法有多种。由于无线传感器网络的节点数量级较高，采用Newman提出的凝聚算法[9]，该算法能够分析的节点数目能够达到百万个，适用于无线传感器网络大规模高密度的特性。

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

1）将每个节点独立的看作一个社团，这样在初始条件下网络中一共有n个社团。

2）依次合并有边相连的社团对，按照式下面给出的公式计算合并后的Q值增量，每次合并沿着使Q增大或者减小的方向进行。

3）重复第2）步，不断合并社团，直到整个网络都合并成为一个社团。这个过程最多执行n-1次。

以上步骤完成后能够得到一个社团结构分解的树状图。在不同位置断开就可以得到不同的社团结构。在这些社团结构中，选取局部最大的Q值，就可以得到最好的社团结构[11]。凝聚算法的时间复杂度为O（（m+n）n），其中m为网络的边的数目，n为网络的节点数目。

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

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

4 结束语

文中针对无线传感器网络中的有向感知模型提出一种基于复杂网络社团结构划分的覆盖增强算法，在节点部署完成后，重新调整节点的感知方向，增强网络的覆盖性能。同时该算法是完全分布式的，所采用的社团结构划分算法能够分析的节点数目能够达到百万个，适用于无线传感器网络大规模部署的特点。

[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]程卫芳.无线传感器网络覆盖控制技术研究[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].复杂系统与复杂性科学，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.