基于SPSO算法的无线传感器网络覆盖可行性分析

郑涵文

摘要：从诞生之初，无线传感器网络（WSNs）作为一种新的测控网络，在民用领域与军事领域的应用前景非常广阔，这得益于它的多样性和广泛性。又因WSNs拓扑结构变化繁杂，节点使用周期短，又常处于比较极端恶劣的环境中运用，所以怎样改善网络节点分布，提高部署效率是当前的迫切问题。目前，WSNs节点分布的方法研究还在探索的阶段，所以寻找一种较为高效的优化算法是当前重中之重。本文首次提出基于SPSO算法的无线传感器网络覆盖方案，探讨其在WSNs领域的可行性。

关键词：SPSO算法；无线传感网络；覆盖优化

一.研究意义

在关于WSNs的各项应用与研究里，傳感器节点的部署问题一直困扰着研究人员。其原因是WSNs通常有拓扑结构的复杂变化，节点生命周期短，数量大，同时进行工作的环境又往往极端恶劣等特点。因而，常用的算法与协议、传统的网络技术都可能因WSNs的这些现实情况，而较难用于WSNs上。这就有了一个亟待解决的问题：怎样在WSNs布局中，找到减少传感器节点的能源损耗，并且能够平衡以延长网络寿命为目的的能量损耗优化方案，同时提高传感器节点的群体智能的协作能力与认知能力。

为了有效降低网络的构建周期，让监测区域满足迅速覆盖，且让WSNs的拓扑结构能拥有高的适应性，同时使网络通过协调控制能够有效地增长使用时长，一个合适、可行的WSNs节点部署方案非常重要。所以为了让节点覆盖达到最优化效果，必须提出一种高效的控制算法对WSNs节点进行部署。

二.仿真模型

传感器节点感知模型及每个节点的位置分布与WSNs的覆盖问题往往联系紧密。换句话说，传感器节点感知模型确定的空间位置和节点的物理位置关系被视作度量感知函数的服务好坏的标准。由于感知模型的种类繁多，所以模型的改变是依照具体的应用环境而进行多种变化的。

1.二元感知模型

将监测区域平面化，节点的覆盖范围指的是以传感节点位置为中心，RS为半径的圆形面积。该圆形区域叫做传感器节点的“感知圆盘”，RS表示传感器节点的感知半径，其值由节点感知设备的物理性质确定。假定传感节点S的位置坐标是（XS，YS），存在平面上一点坐标为P（XP，YP），则在二元感知模型中，节点S成功检测到位置P的概率Pr：为Pr（s，p）当d（s，p） ≤Rs时，反之则为0。

在概率公式中， 为节点S和P之间的欧氏距离。同样的，节点在三维世界里的感知范围与二元感知模型内类似，都是以一个节点位置为圆心，RS是半径的球形区域。

2.传感网络问题模型

假设监测范围D是m×n的矩形区域，在该区域中随机播撒参数相同的固定传感节点和移动传感节点，两种传感节点数量都为N。每个节点的监测区域都是以节点位置为中心、r是半径的圆形范围。在问题模型中，采用的是节点的二元感知模型。通信范围的半径为R。为了保障无线网络的连通性，往往将节点通信半径设置感知半径的两倍以上，即R≥2r。

将监测范围D分割成个像素点，每个真实的地理位置都用像素点表示，像素点p的坐标为（X，Y），用表示Di传感器节点i（xi，yi）覆盖像素点p发生的事件，Pr（Di）表示该事件发生的概率，值取1或者0。当像素点位于节点的感知范围内，则Pr（Di）取1，否则取0。

三.算法原理

1.PSO算法

基本PSO算法的原理是通过模仿对大自然中鱼群捕食与鸟群捕食的过程，随机产生鸟群在一定空间内，而群体通过独立个体间的探索与协作最后成功获得食物所在的区域。可以构造这样的一个场景图，一群独立的鸟在自行不干涉的进行寻找食物，它们无法确定食物所处的精确区域，但有一个潜在的规则使得独立的鸟知晓其相距食物的路径长度（比如：食物气味的大小，食物发出声响音量等等）。在这种情况下，每个独立的小鸟会在搜寻的期间内不断地刷新与存档其曾经过距离食物最近的方位，同时还间断地跟着鸟群中全体个体所存在过的最近方位进行刷新。所以，鸟群通过参考本身的历史最优位置与种群的历史最优位置不停地刷新其所在方位与前进的速度，最后让群体汇聚在食物的位置。PSO算法的进化方程为：

2.SPSO算法

SPSO算法继承了基本PSO算法的优点，而对其容易陷入局部收敛的问题，SPSO算法对算法过程进行了改进。首先去掉粒子中飞行速度记忆力以增加算法局部收敛能力，然后通过在搜索空间中随机产生停止粒子来退出局部收敛，同时可以拥有较高的收敛速度。当惯性系数w=0时，粒子的探索速度只由粒子的实时位置、历史最好位置与粒子群的目前最好位置来决定，探索速度不存在记忆性。所以，当粒子在种群最好位置上的会立刻不再探索，同时别的粒子会想着与的加权中心而趋近。换句话说，群体将紧缩至目前的，类似一个局部算法；若是，则让粒子能够具有扩展搜索空间的势头，也就是有能力满足全局搜索。同时w越大意味着全局搜索能力就越强。

四.可行性分析

基本PSO算法是通过随机产生粒子群进行迭代，寻找最优解。而WSNs网络节点覆盖初始化正符合随机性这一特点，所以使得两者可以有效的结合起来。虽然和PSO算法相比，SPSO算法取消了惯性系数，使得粒子本身没有速度记忆性，以致降低了全局搜索能力。然而这也让种群在进化时，每一代都能够满足有一个粒子由于处于粒子群的历史最优位置而不再进化，通过停止进化的粒子改进全局搜索能力是SPSO算法的中心思路。因此SPSO算法可以有效保障全局收敛性，

本文构建了监测范围为D的传感网络仿真模型，采用了二元感知模型，将粒子维度控制在二维上，设定节点数目，将覆盖率作为优化的适应度函数。使得现实中的WSNs网络节点覆盖问题可以转换为一个寻优问题。通过对比SPSO算法和PSO算法的全局收敛性，可以推测出SPSO算法在WSNs网络节点覆盖问题具有更强的收敛性。

同时SPSO算法带有一定的随机性，特别是对粒子长度较长，维度较低的寻优问题，随机性更容易跳出PSO算法所产生的局部收敛。因此在适用性上，SPSO算法比PSO算法更适合WSNs网络节点覆盖问题。

五.总结语

本文在研究了无线传感器网络的结构和特征以及传感节点部署的工作原理后，分析SPSO算法作为传感节点部署问题控制算法的适应性，并且提出了采用SPSO算法解决节点覆盖最大化问题的设想，还分析其优于PSO算法的可行性。在以后的深入研究中，将通过仿真实验对该方案进行验证。