一种连通有向传感器网络的目标覆盖增强算法

2021-11-30王瑞欣范兴刚周鹏飞

浙江工业大学学报 2021年6期

王洁，王瑞欣，范兴刚，周鹏飞

(1.浙江工业大学之江学院，浙江绍兴 312030；2.浙江工业大学计算机科学与技术学院，浙江杭州 310023)

目标覆盖是有向传感器网络的重点研究内容[1-2]。Jing等[3]最先研究了有向网络的目标覆盖问题，每个节点选择覆盖目标最多的感知方向，用最少的节点实现目标的最大覆盖。文献[4-5]将节点的目标覆盖贡献和转动能耗比值设定为节点效能函数，通过最大节点效能函数实现目标覆盖，延长网络寿命。Zhu等[6]研究了在异构有向网络中如何用最小的代价实现不同目标覆盖要求。以上研究都是从预先设定的感知扇区集合中选择最优扇区来实现目标覆盖。而在文献[7-8]中，节点可以转动到任意方向，也就是节点的感知区域可以是任意方向的。Wu等[7]用最少的节点和较低的能耗实现目标覆盖要求。Jia等[8]选择具有最大剩余能量的方向组建覆盖集合，实现不同要求的目标覆盖，延长网络寿命。Cai等[9]根据目标权值选择节点的最优感知方向，实现权重目标覆盖。

利用节点概率感知特性增强区域覆盖成为近年研究趋势[10-15]。Fan等[15]利用有向概率感知模型高效实现有向概率栅栏覆盖。范兴刚等[16]利用相邻节点的联合概率感知能力，用更少的节点实现目标的有向概率覆盖，但该方法仅实现目标覆盖，没有考虑网络连通问题。网络连通是检测数据及时传输的重要保障。因此，笔者在之前研究基础上，提出保障网络连通的目标概率覆盖增强算法(Probabilistic target coverage and connection enhancing scheme，简称为PacE)。

1 相关模型和定义

为了简化研究，作如下假设：1)节点对目标是概率感知的，目标与节点的距离越远，目标感知概率越小；2)假设传感器的通信半径为2rmin，通信能力随着感知概率阈值Pmin的变化而变化。有向概率感知模型定义如下：

定义1有向概率覆盖模型。参考文献[16]，有向概率覆盖模型采用6元组(Pmin,Ls,A0,rmin,α,θ)表示，如图1所示。其中Pmin表示概率阈值；Ls=(x,y)表示节点的位置；A0表示感知区域阈值，在该区域内的目标都以概率1被感知；rmin表示概率感知区域的半径，在单个节点作用下，这个区域内的目标感知概率≥Pmin；α表示节点的感知方向；θ表示感知角度，在这个角度内的目标能被节点概率感知。图1中，在感知角度内，随着距离的增大，颜色逐渐变淡，感知概率逐渐变小。

图1 有向概率感知模型

单个节点对目标的感知概率计算公式为

(1)

式中：d为传感器与目标t之间的距离；P(d)为节点对目标的感知概率；λ为目标与节点连线和感知方向的夹角；μ为感知强度衰减系数。

目标被多个节点联合感知，其感知概率计算公式为

(2)

式中：St为可以感知目标的所有节点；P(i)为第i个节点对目标的感知概率；P0为目标的联合感知概率。当P0≥Pmin时，就称这个目标实现了概率覆盖；如果P0

(3)

定义2目标概率覆盖圆。构造一个以目标为圆心的圆，如果圆内存在一个未覆盖此目标的节点，即用式(1)计算的感知概率为0，那么只要调整节点感知方向，使目标在其感知角度内，就可以实现目标概率感知，即用式(3)计算的目标联合感知概率≥Pmin，称该圆称为目标概率覆盖圆，其半径计算公式为

(4)

假设传感器的通信半径为2rmin，通信能力随着感知概率阈值Pmin的变化而变化。网络用一个无向图G=(V，E)表示，顶点集合V是一组节点集合，每个节点表示一个有向传感器节点；E是一组边的集合，能够直接通信的两个节点之间的直线为一条边。

定义3最大连通集。一个图G的某个节点子集是连通集，是指子集中的节点可以两两通信。节点数量最多的连通子集是整个网络的最大连通集。

定义4最近连通节点。对于未达到概率覆盖要求的目标，最大连通集内，距离这个目标最近的节点称为这个目标的最近连通节点。

笔者要研究的问题是：在感兴趣区域中，随机部署N个有向节点，M个目标，如何利用节点的有向感知特性，在保持网络连通的同时增强目标覆盖。

2 理论分析

图2 概率覆盖圆

图3 连通图和连通支配图

根据目标最近连通节点的连通圆与目标概率感知圆的关系，综合调度节点，满足目标覆盖和网络连通要求，目标概率覆盖圆和连通集上的连通圆如图4所示。

图4 目标概率覆盖圆和连通集上的连通圆

图4中A是未覆盖目标点，B是其最近连通节点。以点A为圆心的粗线小圆为概率覆盖圆，以B为圆心的细线大圆是节点B的连通圆。如果节点B在目标A的概率覆盖圆内(图4a)，且没有覆盖任何目标，只要调整节点B的感知方向，就可以概率覆盖目标A，这时节点B的目标位置就是其初始位置。节点覆盖目标的最终位置和目标的连线与x轴的夹角用λ表示，则该节点最终感知方向计算方式为

(5)

式中：若λ-θ/2≤α0≤λ+θ/2，则不进行转动；若|λ-θ/2-α0|<π，转至λ-θ/2处；否则，转至λ+θ/2处。

如果目标A和最近连通节点B距离较远，节点B不在目标A的概率覆盖圆内。最大连通集中，节点B通过节点D与其他节点连通。节点B在目标A的概率覆盖圆外，节点D的连通圆与目标A的概率覆盖圆存在公共区域，如图4(b)所示，这个重叠区域有2 个边界，一个在节点D的连通圆上(边界1)，另一个在目标A的概率覆盖圆上(边界2)。选择节点移动到这2 个边界上，也可以同时实现目标覆盖和网络连通。这个时候，候选覆盖节点的最终位置(xt,yt)计算方式为

(xt,yt)=min((xcon,ycon),(xpco,ypco))

(6)

式中：(xcon,ycon)表示节点初始位置与连通节点D的连线与边界1的交点；(xpco,ypco)表示节点初始位置与目标的连线与边界2的交点；min()表示从这2 个位置中选择距离初始位置较近的点。图4(b)中，针对节点F，点G坐标为(xcon,ycon)；针对最近连通节点B，点C坐标为(xpco,ypco)。节点移动到最终位置，连通网络以后，再用式(5)调整节点感知方向，实现目标覆盖。图4(c)中，如果两个圆之间没有公共区域，C点代表节点的目标位置，则在目标A和节点B的附近，找到距离节点B最近的节点D，确定最终位置点C，移动到点C，保持网络连通，点C计算方式为

(xtc,ytc)=(xcon,ycon)

(7)

进一步找到点C的通信圆和目标A的概率覆盖圆的重叠区域，如果这个区域存在点F，只要再按照式(5)的方法调整其感知方向就可以实现目标覆盖；如果重叠区域没有节点，则按照式(6)的方法，保持网络连通的同时实现目标覆盖。

3 基于概率感知半径的目标覆盖增强算法(PacE)

对于不满足最小感知概率要求的目标，根据其和最近连通节点的几何关系，可以选择最优节点，以较小的能耗实现目标覆盖和网络连通，据此，笔者提出一种基于概率感知半径的目标覆盖增强算法(PacE)，PacE参数的定义如表1所示。

表1 参数定义

3.1 算法的基本思想

PacE算法的基本思想是：找到网络最大连通集，运用连通集节点计算每个目标的初始感知概率，构造目标的概率覆盖圆，根据其与最近连通节点的几何关系，选择调度节点，优化其位置和感知方向，同时实现目标概率覆盖和网络连通。PacE算法伪代码为

Input: targets, nodes,θ,Pmin

Output: coverage ratioCa, connection ratioLa

Calculatingrmin;

Ascertaining connection domainNeof the network;

Ascertaining the working direction of each node inNc;

Calculating each target’sP0by(1)and(2);

For each target withP0

Calculating itsRby(3)and(4);

Ascertianingdto its nearest connecting node;

Ifd

Finding the node’s new location by(6);

Selecting the optimal node to move and rotate;

Else

Finding the node’s new location by(7);

Selecting the optimal node to connect the network;

Finding the node’s new location by(6);

End

Determining this node’satby(5);

Selecting the optimal node to move and rotate;

End

Ca=covered targets/targets;

La=conencting nodes/nodes;

3.2 算法过程

PacE算法基本步骤如下：

Step1确定整个网络的最大连通集。构建整个网络图，采用文献[17]的最小生成树算法，找到网络最大连通集Nc，组成覆盖节点集合。

图5 连通支配节点的最佳目标方向

Step3计算目标感知概率。把Nc作为初始覆盖集合，用式(1，2)计算目标感知概率。

Step4确定目标概率覆盖圆。对于没有满足概率覆盖要求的目标，根据式(3，4)计算其概率覆盖半径，得到概率覆盖圆。

Step5找到目标最近连通节点。针对每个未覆盖目标，确定最近的连通节点。例如，在图4中，未覆盖目标A最近的连通节点为B。

Step9算法结束。直到所有目标都达到了概率覆盖要求或者没有节点可以移动，算法结束，统计覆盖率和连通度。

3.3 算法的理论分析

假设目标的个数为M，移动节点的数目为N，为了实现概率覆盖，需要考查每个节点对每个目标的概率覆盖情况，因此，PacE算法时间复杂度为O(M×N)。

4 仿真结果

运用Matlab 7.0对PacE算法进行仿真分析，先做50 次独立实验，再以求取平均值的方式获得实验数据。默认参数如表2所示。为了验证算法性能，选用文献[16]的TarpC算法和其改进算法作比较。为了提高连通性，先用TarpC改进算法得到网络最大连通集，再使用TarpC算法优化连通节点集感知方向，增强目标覆盖。

表2 实验参数

4.1 算法性能

算法性能如图6所示。当节点密度较小时，相邻节点距离较远，覆盖率(图6 a)和连通度(图6 b)较低。节点密度越高，节点数量越多，覆盖率越高。当节点密度达到一定程度时，节点之间的距离变得很短，所有节点都在同一个连通集内，整个网络保持连通，目标覆盖率也接近100%。增大传感角度同样会造成影响。根据式(4)，给定Pmin，当初始角度较小时，rmin较大，由于假设通信半径为2rmin，因此通信半径也较大。由于较大的感知半径可以覆盖相对远的目标，所以较小的感知角度具有较高的覆盖率和连通度。

图6 算法性能

4.2 概率感知阈值的影响

Pmin的影响如图7，8所示。由有向概率感知模型的特点可知：感知概率阈值越大，节点概率感知半径rmin越小，连通半径与rmin成正比，rmin越小，连通节点越少，所以3 种算法的性能都随着感知概率的增大而降低。TarpC算法仅通过调整节点感知方向实现目标概率覆盖，但可能会出现信息孤岛，无法保证网络的连通性。改进的TarpC算法用连通集内的节点实现概率覆盖，可以消除信息孤岛，实现感知信息的及时传输，而PacE算法优化节点的运动方式，同时实现结合目标概率覆盖和网络连通。因此，PacE算法具有最好的目标覆盖和网络连通度。TarpC算法通过联合概率感知，综合利用整个网络的感知能力，具有较好的覆盖度，但网络连通度最低。改进的TarpC算法能够提高连通度，但由于用于覆盖目标的节点数量下降，目标覆盖率最低。

图7 概率阈值与目标覆盖率

图8 概率阈值与部署效率

4.3 节点数量的影响

节点数量的影响如图9，10所示。随机部署的节点数越多，可以对目标进行覆盖的节点数越多，可以连通的节点数也越多。因此，随着节点数的增多，3 个算法的目标覆盖率和网络连通度均逐渐提高。

图9 节点数与目标覆盖率

图10 节点数与网络连通度

由行改进先得到网络最大连通集，再通过转动连通集内的节点增强覆盖，这样做虽然降低了覆盖率，但保证了连通性。PacE算法通过分析目标和其最近节点的几何关系，选择最优节点移动和转动，实现网络连通和目标覆盖。因此，PacE算法性能较好，能在保持网络连通的同时实现目标概率覆盖。仿真结果表明笔者算法所选取的移动方式能够在保持连通性的基础上增强覆盖率。