基于概率感知模型的集中式区域覆盖算法研究

孙荣凯　衣晓　薛兴亮

摘 要： 覆盖问题是无线传感器网络完成目标监测和信息获取任务的前提。为了更贴近实际地描述区域覆盖问题，采用概率感知模型，并把对被监测区域的覆盖问题转化为对可数个点目标的覆盖问题，然后利用点覆盖算法对整个监测区域的覆盖问题进行了研究。最后通过仿真实验，对网络采用单重覆盖与多重覆盖的效果进行了比较，验证了区域多重覆盖的优越性。

关键词： 无线传感器网络； 概率感知模型； 区域覆盖； 集中式算法

中图分类号： TN921?34； TP393 文献标识码： A 文章编号： 1004?373X（2015）01?0001?04

Abstract： Region coverage is a basic premise to realize target monitoring and information acquisition in wireless sensor network. In order to describe the region coverage more closely to the actuality， the probabilistic sensing model is applied， and the coverage of the monitored area is turned to the coverage of the countable point targets. The coverage of the whole monitored area is investigated by means of the point target coverage algorithm. The effects of single coverage algorithm and multiple coverage algorithm are compared by means of simulation experiment. The superiority of multiple coverage algorithm was verified.

Keywords： wireless sensor network； probability perceptual model； region coverage； centralized algorithm

0 引 言

无线传感器网络的覆盖问题与网络能效性和节点连接性密切相关，是网络完成目标监测和信息获取任务的前提，是无线传感器网络设计和规划面临的基本问题之一[1?2]。在实际应用中，传感器对目标的感知能力是随着距离的增大而不断衰减的，因而概率感知模型[3]更贴近实际情况。本文基于概率感知模型，把被监测区域的覆盖问题转化为对可数个点目标的覆盖问题，利用点覆盖算法思想对区域覆盖进行了研究，并通过仿真实验，对网络采用单重覆盖与多重覆盖的效果进行了比较。

1 区域到点目标的转化

为了简化问题，本文假设被监测区域内已经部署好所有节点，节点已完成自身定位[4?6]，节点不可移动且无新节点加入，同时采用的传感器节点是同构的[7]，节点的感知半径固定不变。

1.1 基于布尔感知模型的区域划分思想

先就布尔感知模型的情况进行研究，如图1所示。在已经部署好传感器节点的被监测区域中，每个传感器节点感知圆盘的边界线相互交割，形成可数条相交的弧线段；这些弧线段围成一个个最小区域块，这些区域块不可再分，且所有区域块的并集为整个被监测区域。此时，这些区域块可看作为一个个点目标，只要覆盖了这些点目标，就可以覆盖整个被监测区域。这样，区域覆盖问题就转化成为点覆盖问题。

1.2 区域块权值的求取

应当注意，这个以点目标覆盖思想进行划分的区域覆盖算法与点覆盖算法还是有所区别的。因为点覆盖算法中，在工作节点竞选时进行的传感器节点贡献值[8]大小比较中，所有目标均为同等地位，只是以传感器节点能够覆盖的尚未被覆盖的点目标个数来衡量贡献值大小。而在经过划分的区域覆盖算法中，对于每一个被看作为点目标的区域块而言，可能几个区域块的面积之和还不如另一个区域块的面积大，因此应当计算每个小区域块的面积，以此面积作为此区域块对应虚拟点目标的权值，这样在节点竞选时，就以该节点能够覆盖的尚未被覆盖区域块的权值之和来确定其贡献值大小。

1.3 扩展至概率感知模型的区域划分思想

按照前面的区域划分原则，被监测区域被划分为可数个最小区域块。然而，对于概率感知模型，因为最小区域块上的任意一点到节点的距离不同，从而任意一点被感知的概率不同，而且这样的点是无穷多的，因此难以用明确的形式表征节点对区域块的感知概率。这里介绍一种简化的概率感知模型[9]，既可以满足节点概率感知模型中感知概率依距离增加而递减的特性，又便于表示节点对每个区域块的感知概率，如图3所示。

图3是由圆心相同而半径不同的圆组成，所有半径的值都介于0和[R]之间。任意两个相邻的圆，假设其半径分别是[Ri，][Ri-1i=1，2，…]，由这两个圆构成圆环的被感知概率介于[11+ξ?Riσ]和[11+ξ?Ri-1σ]之间。而如果所形成的圆环的被感知概率用其最小概率值[11+ξ?Riσ]代替，则节点[O]对监测区域内任意一点[P]处的感知概率为：[p（O，P）=0，d（O，P）>R11+ξ?Riσ，Ri-1≤d（O，P）≤Ri≤R] （3）

其中，[d（O，P）]为节点[O]与目标[P]之间的欧氏距离；[R]为设定的阈值，由节点感知单元的物理特性决定；[ξ]和[σ]为与传感器物理特性有关的类型参数，通常[σ]取值为[1，4]之间的整数，而[ξ]是个可调的参数。

本文把节点感知圆盘中每个[Ri]和[Ri+1]之间的部分称之为感知圆环，依据此概率模型，每个感知圆环内任何一点的被感知概率是相等的。假设[Ri]和[Ri+1]之间的差值为[φii=1，2，…，]很明显只要[φi]值越小，[Ri]和[Ri+1]的值就会越接近，则此概率模型就越接近于实际情况。

本文中讨论的区域划分问题，即可以依据此概率感知模型加以扩展，由所有节点的感知圆环的边界线相互交割而形成一个个最小区域块，每个最小区域块均满足任意一个节点对此区域块中的任意一点仅有一个感知概率。而此时每个区域块都可以被看成一个点目标，区域覆盖问题同样转化为对点目标的覆盖问题。

2 基于概率感知模型的区域覆盖集中式算法

在概率模型的覆盖问题中，一般采用设定一个概率值[η0<η<1]的方法作为覆盖要求。如果在覆盖区域内，每一点处的覆盖概率都大于设定的概率值[η]，则认为已达到了覆盖要求，此区域完成覆盖。在本文中，假设被监测区域中的节点存在足够的冗余，且区域已划分完毕，即此时的被监测区域可看作为可数个已编号的最小区域块的集合；同时所有传感器节点覆盖的区域块及对应面积都已确定，并且所有节点均可确定自身剩余能量以及落入其感知范围内的最小区域块编号、权值以及感知概率。

2.1 单重覆盖的集中式算法

所谓概率感知模型中的单重覆盖即为选取一个工作节点集，保证被监测区域中每个区域块的被覆盖概率均可达到覆盖要求[η。]

2.1.1 算法思想

该算法的思想为被监测区域中所有的普通传感器节点均向中心节点上报其感知信息。与布尔模型情况有所区别，感知信息应除了包括该节点的位置信息、剩余能量以及覆盖的所有最小区域块的编号、权值以外，还应包括该节点覆盖的所有最小区域块相应的感知概率。当所有的节点向中心节点上报完毕后，中心节点将上报信息分类存储并进行统计，对于任意一个最小区域块，计算出可令其达到覆盖要求[η]的全部节点集的集合[G1，G2，G3，…]。选取节点集[Gj（j=1，2，…）]的原则应设定为：节点集合中全部节点对该区域块的联合概率可达到覆盖要求，不同的集合之间可以存在交集，但是其中每一个集合都不能成为另外任何一个集合的子集，即：

然后，对所有区域块的可满足其覆盖要求的节点集合个数进行比较，拥有这样的集合数目最少的也就是最少覆盖区域块。继而从此最少覆盖区域块的满足其覆盖要求的节点集合中，根据一定的竞争规则选取一个进入工作状态。竞争规则为：该节点集合中节点个数尽可能少，节点集合中剩余能量最少的节点的剩余能量尽可能多，节点集合与已确定工作的节点集合中元素重合个数尽可能多。

在确定了工作节点集合之后，中心节点更新未被覆盖区域块集合，只要未被覆盖区域块集合不为空，则需要继续在未被覆盖区域块集合中选取下一个最少覆盖区域块，继而选取工作节点集合，直至所有区域块都达到覆盖要求。

2.1.2 算法流程

该算法流程图如图4所示。

2.2 多重覆盖的集中式算法

对于概率感知模型，多重覆盖需要确保被监测区域中的每个区域块都能被多个节点集合覆盖，而这些节点集合的要求是对区域块的覆盖概率达到覆盖要求[η]且相互不相交。

其后的算法步骤，双重覆盖与单重覆盖完全一致，并且[k（k>2）]重覆盖的情况可以按照双重覆盖的情况进行类推。多重覆盖算法仅仅是对每个最小区域块选取达到覆盖要求节点集合的原则与单重覆盖算法有所不同，其算法流程与单重覆盖算法完全一致，因此多重覆盖的算法流程框图可参看图4。

3 仿真分析

在仿真中，工作节点集的工作轮次即为整个网络的生命周期[10]。在对被监测区域实行不同覆盖标准的效果进行比较时，本文采取网络覆盖质量指标[11]来刻画区域多重覆盖的重要意义，从下面两个方面进行：

3.1 网络的监测概率

当障碍物在节点感知圆盘内的出现概率为[pc]时，对区域采取多重覆盖对比仅采取单重覆盖，可极大提高网络监测概率，如图5所示。

3.2 网络的未达覆盖要求概率

当节点自身存在失效概率[ps]时，采取多重覆盖对比仅采取单重覆盖，会远远降低网络未达覆盖要求的概率，如图6所示。

通过仿真对比发现，网络采用双重覆盖时的生命周期几乎是网络采用单重覆盖时的一半，这是因为网络采用双重覆盖时每一轮次使用的节点远远多于网络采用单重覆盖时使用的节点。通过对网络监测概率和网络未达覆盖要求概率两个方面的比较可知，网络采用双重覆盖要远远优于采用单重覆盖。因此当对传感器网络的监测效果要求较高时，双重覆盖相对于单重覆盖具有较高的优越性。

4 结 语

本文基于概率感知模型，依据节点感知圆盘之间的相互关系，将被监测区域划分为可数个最小区域块的并集，由此将区域覆盖问题转化为点覆盖问题，最终通过改进的点覆盖中的贪婪式算法给予解决；并通过仿真实验对网络采用单重覆盖与多重覆盖的效果进行了比较，验证了区域多重覆盖在监测和覆盖概率方面的优越性。

参考文献

[1] 孙利民，李建中，陈渝，等.无线传感器网络[M].北京：清华大学出版社，2005.

[2] 许毅.无线传感器网络原理及方法[M].北京：清华大学出版社，2012.

[3] 赵静，曾建潮.无线多媒体传感器网络感知模型与数量估计[J].软件学报，2012，23（8）：2104?2114.

[4] LU J， SUDA T.Coverage?aware self?scheduling in sensor networks [C]// Proceedings of 2003 IEEE 18th Annual Workshop on Computer Communications. [S.l.]： IEEE， 2003： 117?123.

[5] 衣晓，刘瑜.无线传感器网络Range?free自身定位算法仿真分析[J].海军航空工程学院学报，2009，24（4）：369?375.

[6] 刘瑜，衣晓，何友.基于分治求精的无线传感器网络节点定位算法[J].系统工程与电子技术，2012，34（9）：1906?1913.

[7] 李海波，杜庆伟.一种能量有效的无线传感器网络覆盖控制算法[J].小型微型计算机系统，2011，32（2）：233?236.

[8] LIU Yu， WANG Yu?mei， ZHANG Lin. Approximation for a scheduling problem with application in wireless networks [J]. Science China （Mathematics）， 2010， 29（06）： 62?66.

[9] 薛兴亮，衣晓，马德良，等.基于概率感知模型的边界线多重覆盖算法研究[J].扬州大学学报，2013，16（3）：16?23.

[10] LIU Ying， YANG Zhen， MEI Zhong?hui. Research on adaptive compression coding for network coding in wireless sensor network [J]. Journal of Electronics， 2012， 29（05）： 415?421.

[11] 张硕，蒲菊华，刘玉恒.无线传感器网络覆盖质量问题[J].北京航空航天大学学报，2009，35（5）：631?635.