无线传感网络覆盖优化技术研究

张江山 熊哲源

(江西警察学院安全管理系 江西南昌 103003)

无线传感网络（Wireless Sensor Networks，WSN）是由部署于所监控区域内的大量微小传感器构成，可把采集到的监控信息发送给外部终端监测人员[1]。无线传感网络的应用非常广泛，现已是一个国内外关注比较多的领域，网络覆盖是影响无线传感网络工作效率主要因素之一。目前，市场上已有很多种类的无线传感节点如视频传感器节点、图像传感器节点、超声波传感器节点、红外线传感器节点等具有强感知的方向性[2]。如果能研究一种方法来控制这些全向传感器的方向，增强网络覆盖范围将有一定的现实意义。

该文对多媒体传感网络的有向传感器感知方向控制方法进行了深入研究探讨，在节点之间假设存在万有引力和排斥库伦力叫作拟物力，提出一种改进的粒子群算法。基于粒子群算法加上拟物力的算法对传感网的有向传感器感知方向和位置进行计算控制，能有效地提高无线传感网络覆盖率。

1 覆盖优化流程

1.1 网络覆盖定义

目前，常用来衡量传感器网络覆盖性能的指标主要有：覆盖率、覆盖效率、覆盖均匀性和覆盖度[3]。该文把提高的网络覆盖率作为网络增强覆盖算法的追求。覆盖率的定义如下。

其中，Si、S、N分别表示一只传感器节点覆盖面积、监测区域总面积、网络中传感器节点数量。P的取值为[0，1]。

1.2 覆盖增强优化流程

网络覆盖优化增强分3 个阶段：网络初始化阶段划分连通子网、改进粒子群优化算法计算控制方向最优值、调节节点感知方向，覆盖优化流程如图1 所示。组网的有向传感器随机部署后，由汇聚节点启动整个网络的工作初始化节点位置、感知半径、感知方向等。利用优先遍历算法根据节点的感知半径和位置信息将整个无线网络划分成若干个连通子图，运用改进式粒子群优化算法对传感连通子网的各个有向传感器感知方向进行最优计算，算出各传感节点的最佳感知方向，各子网的汇聚节点通过多跳无线通信方式将感知方向值派发到各自的节点，网络中各节点根据接收的计算结果自发调整感知方向，从而实现了整个网络覆盖增强。

图1 覆盖增强流程图

2 粒子群算法优化

2.1 PSO算法优化

粒子群算法优化（Particle Swarm Optimization，PSO）是一种基于自然界鸟类寻觅食物的仿生搜索算法[4]，此前，已有很多学者对其进行了研究和分析，此算法具有参数少容易实现，简单高效的优点。

在粒子群优化算法中，群被称为粒子群，群中的个体称为一个粒子，用来表示优化问题的一个解向量。有N个粒子，每个粒子都一个有D维位置向量和一个D 维速度向量，Xi=(Xi1，Xi2，…，XiD)表示粒子位置向量，Vi=(Vi1，Vi2，…，ViD)表示粒子速度向量。算法初始每个粒子随机产生位置和速度，然后进行迭代更新，每个粒子第K+1次更新位置和速度的公式为

式中，C1和C2是学习因子，是两个正常数取值为2，R1和R2为（0，1）区间的随机数。Vid(K+1)和xid(k+1)是第K+1 次迭代粒子i第D维的速度和位置。每个粒子有一个适应值，式（1）中的第一部分W是惯性权重因子，用于算法控制搜索步长；第二部分表示粒子不断地趋向的自己最好位置；第三部分表示粒子会趋向整个网络的传感节点的最佳位置。粒子群中的每个粒子在解空间内不断迭代计算，改变调整自己的速度和位置，并逐渐趋向全局最佳位置和方向，直到最大迭代次数达到规定值或满足规定的误差标准时算法结束。

2.2 POS优化算法不足

粒子群算法虽然具有简单易实现、控制参数少、具有并行性等优点，但同其他优化算法一样也有些固有的缺点，具体为：（1）在后期阶段收敛速度比较慢；（2）当问题解空间维度比较高时，容易出现“早熟收敛”现象，陷入局部最优；（3）控制参数少，但对算法的精度和效率影响很大，在不同的应用环境不同的优化问题，参数的最优设置值需要通过大量实验或凭经验确定。

2.3 拟物力算法

拟物算法也是从自然界中得以启发而学来的一种优化算法[5]，可以用于解决复杂程度不确定性的问题。该文提出把拟物力算法和粒子群优化算法结合在一起优化网络覆盖的想法，利用两种算法相结合来改进粒子的位置与速度更新迭代过程，使唤粒子改变移动方向、收敛加快，拟物力算法可以更好地调整粒子间的距离，使得无线传感网络更有效地覆盖监控区域。与基本粒子群算法比较，融入了拟物力算法后的粒子群算法有更强的全局搜索能力，无线传感网络收敛更快，能更早达到全局最优状态，降低算法耗时与冗余覆盖也降低了。拟物力[6]算法主要包括拟万有引力和拟库仑力。

2.3.1 拟万有引力

将每一个传感器节点看作为一个规则的半径为r的圆盘[7]，如果两个圆盘之间距离小于通信距离的就会产生引力，称拟万有引力，大于通信距离的节点不会产生引力，“拟万有引力”可表达如下。

2.3.2 拟库仑力

节点的圆盘会产生交叠覆盖情况，要增强网络覆盖就应尽量减少节点圆盘交。拟库仑力就是如果两个圆盘之间的距离小于圆盘距离阈值就会相互之间有排斥力，每个节点圆盘排斥与自己距离过近的其他圆盘，以便减少交叉覆盖。根据库仑力定理，无线传感网络节点圆盘间的斥力势表达式为

式（3）（4）中，fij表示节点圆盘之间虚拟力（吸引力或排斥力）；dij为节点之间的欧拉距离；RC为节点通信距离；wb为排斥力系数；wa为引力系数。

2.4 算法的覆盖优化方案设计

为了改善粒子群算法收敛慢和早熟收敛的问题，该文提出了拟物力和基本粒子群优化算法相融的算法方案，根据拟物力作用策略，改进基本粒子群算法的速度迭代公式，后面加上拟物力算法式子，位置的迭代方式不变，速度迭代表达式如下。

式（6）中w、c1、R1、c2、R2和式（1）中的相关解释式相同。c3、c4分别为拟万有引力系数和拟库仑力系数；r3、r4为两个随机数（0～1）；f1ij(n)、f2ij(n)为节点受到的拟万有引力合力和库仑力合力，计算每个传感器节点受到的其他节点的万有引力合力和库伦力合力并水平和纵向分解，然后计算各节点分解力水平和纵向的万有引力和昆仑力的合力。

把拟万有引力和拟库仑力影响项加入基本粒子群算法中后，网络冗余覆盖可以减少，收敛速度也加快，有效覆盖率增加，算法如下。

第一步，初始化，设置好监控区域，算法中各参数进行初始，在监控区域边界内随机产生N个粒子的初始位置xid、初始速度vid，计算覆盖率初始值。

第二步，按照（1）式基于本粒子群算法迭代更新粒子的速度和位置并计算盖率。

第三步，将更新后的粒子位置覆盖率与个体最优位置的覆盖率进行比较，更新粒子个体最优位置和最优覆盖率。

第四步，比较各个粒子个体最位置的覆盖率大小，设置全局最优位置值和全局最优覆盖率。

第五步，计算判断覆盖率变化率是否为“零”，若是则按式（5）“拟物力”一次。

第六步，判断满足结束条件终止迭代输出结果，否则返回从第二步继续进行迭代更新计算。

3 算法仿真

该文监控区域设置为边长100 m 正方形，节点数为45 个，节点感知半径为10 m，仿真是利用MATLAB平台工具，结果与标准粒子群算法进行了比较。仿真参数具体见表1。

表1 算法仿真参数

优化算法仿真运行结果见图2～图4，“*”号表示传感器节点中心所在位置，圆来表示传感器节点在监测区域够中覆盖的范围。初始传感器节点覆盖情况见图2，运行基本粒子群算法后传感节点覆盖情况见图3，基于拟物力粒子群结合拟物力算法传感器节点覆盖情况见图4。初始在监测区域内随机撒布45个无线传感器网络节点，分别用基本粒子群算法和结合拟物力算法后的基本粒子群算法对传感器节网络进行网络覆盖优化[8]。对比与分析3张传感节点覆盖图，可以看出，相同初始条件下，基本粒子群算法加入拟物力算法后，粒子位置分布相对均匀些，在监测区域范围内覆盖情况得到一定程度上的改善。而仅仅是基本粒子群算法，则是粒子分布不均匀存在很多重叠覆盖区域和大量的未覆盖区；从两种粒子算法覆盖变化曲线图（见图5）可以明显看出，基本粒子群算法加入拟物力项式改进后的区域覆盖程度相比基本粒子群算法改善近10%。

图2 传感器节点分布初始覆盖情况

图3 基本粒子群算法后节点分布覆盖情况

图4 基本粒子群结合拟物力算法后覆盖情况

图5 两种粒子算法覆盖变化曲线

图3和图4是两种粒子算法迭代1 000次后的仿真结果图，图5 是两种算法后传感器节点覆盖率变化曲线图。仿真曲线趋势表明，基本粒子群算法在经198次迭代后就趋于收敛了，覆盖率为81.32%。然而，加上拟物力影响项的粒子群算法，由于有拟万有引力和拟库伦力的作用使得节点根据距离相互排挤或吸引。在迭代220次后，节点覆盖突破92%，在迭代600次后，达到了94%的覆盖程度。

在仿真参数相同的情况下，仿真数据结果表明，基于拟物力的粒子群算法相比基于粒子群算法，对监测区域无线传感网络优化具有覆盖面积更大，覆盖效果更好的优势。

4 结语

该文探讨了无线传感网络的覆盖增强优化方法，对粒子群优化算法进行了研究并提出了改进方法。将拟物力算法作为多项式的一项加入基本粒子群算法中影响算法搜索。迭代过程中，在基本粒子群算法进入局部收敛覆盖率不变时启动拟物力算法加入。仿真结果充分说明对基本粒子群算法加入拟物力算法改进后相比基本粒子算法，有效覆盖率更高，避免算法早熟陷入局部最优的问题也有所改善，无线传感器网络部署的有效性也提高了。