余幸运， 孙 茜， 王小艺， 许继平， 王 立， 张慧妍

(北京工商大学 计算机与信息工程学院，北京 100048)



基于粒子群优化算法的水质传感器优化部署研究*

余幸运， 孙 茜， 王小艺， 许继平， 王 立， 张慧妍

(北京工商大学 计算机与信息工程学院，北京 100048)

针对不同污染程度的水域提出重点监测区域的集中性覆盖监测问题。在重点监测区域的传感器网络部署之前，对于监测水域大面积覆盖监测问题采用一种基于加权因子调整的粒子群优化(PSO)算法，对比了不同粒子群数目对网络覆盖能力的影响。仿真结果表明：PSO算法保证在最大覆盖率的条件下，实现传感器网络节点快速自适应均匀部署，运算速度快且能够避免局部最优；网络覆盖能力先随粒子群数目的增加而增大，当粒子群个数达到20后，网络覆盖能力随之减小；网络实现最大范围均匀部署之后，能较好地保障重点水域的集中性覆盖监测，从而保障真实客观的水质监测数据。

传感器网络； 覆盖部署； 水环境监测； 粒子群优化

0 引 言

水质监测是用科学的方法监测和检测反映水体质量的变化趋势及污染的来龙去脉，是监视和测定水体中污染物种类、各类污染物浓度及变化趋势，评价水质状况的过程。由于近几年内生活废水、工业废水和恶劣气象条件对水环境的剧烈影响，致使不同水域的污染程度各不相同，希望对于污染严重的区域进行实时监控，以保障水质信息的全面真实可靠。由于在实际的水环境监测系统中，水质监测往往通过传感器网络监测获得水质参数数据，合理部署传感器节点的位置使网络的覆盖范围最大，那么获得数据实时可靠性也就越大，水质状况的信息越完整。传统的水环境监测系统一般采用大规模投放传感器的方式，这样的投放方式快速却很难一次性地将传感器节点放置在合适位置，很容易形成感知重叠区和盲区。另外一种方式是将监测水域平均分割为固定大小的网格，并在每个网格的中心位置布测点，这种方法简单易行，但往往会导致相邻断面出现水质监测结果相近，造成监测资源浪费。文献[1]针对无线传感器网络(WSNs)节点定位问题，阐述了WSNs的分布迭代式定位方法，仿真证明了该方法能有效提高了节点定位精度；文献[2]提出了一种近邻点联合测距修正粒子群优化(PSO)的定位算法，仿真证明了修正定位算法能有效提高定位精度和稳定性；文献[3]采用多目标优化的二进制粒子群算法对节点部署进行多目标优化，选取不同传感器对不同区域进行覆盖监测；文献[4]提出蚁群算法实现传感器网络节点的非均匀覆盖，虽然结果中对比了几种算法对覆盖率的影响，但对实验过程没有很好的说明；文献[5]通过模拟鱼群行为，并结合拥挤度控制，使节点自主趋向并覆盖事件，但没有说明在整片监测水域中传感器节点的布置情况；文献[6]提出一种约束PSO的无线传感器网络节点定位算法，提高节点的定位精度，但没有说明网络覆盖能力的问题；文献[7，8]采用PSO算法实现传感器网络的覆盖增强，但是没有说明网络的分布情况；文献[9]将聚集度指标作为判定条件应用于PSO中，实现参数的自适应调整，仿真证明了该算法能提高网络覆盖率。

为克服以上问题，本文采用加权因子调整的PSO算法对传感器节点进行自适应部署，通过更新节点的位置快速计算每次迭代的最优解，并提高收敛速度。本文考虑到水下环境复杂多变，监测区域动态性较强等因素的影响，利用传感器节点可移动性好的特点，采用粒子群智能部署算法，以适应值为最终优化目标，综合邻居节点信息实现传感器节点的自适应均匀部署，在实现重点区域监测之前保障最大覆盖范围，部署方式快速且可靠性高。

1 网络覆盖率度量标准

本文在监测水域的二维平面上用PSO算法进行节点自动部署，以区域最大覆盖和重点区域的覆盖监测为目标，针对不同区域进行不同程度的覆盖，从而保证监测数据的真实客观性并克服了传统部署的资源浪费问题，同样的方法也可以推广到三维空间上。现假设工厂将处理未达排放标准的污染废水排向附近水域，在这片水域中进行传感器节点的部署，使网络覆盖率最大并对受影响较大的区域进行实时重点监测。在100 m×100 m的水域内部署传感器节点，每2 m划分一个网格，如图1所示，图中的方框内表示需要重点监测的区域。覆盖率的计算方式采用网格点实现，定义为受到监测的区域大小与整个监测目标区域大小的比值。图1中所产生的网格点记为K，区域内的网格点总数记作KK，第K个网格点被一个传感器监测到的概率记为c。本文采用布尔感知模型完成传感器的覆盖监测，模型的数学表达式如下

(1)

(2)

统计检测概率等于1的网格数量，进而计算出目标区域的覆盖率。

图1 监测水域模型示意图Fig 1 Schematic diagram of monitoring water area model

2 算法设计

2.1 PSO基本原理

假设在一个二维平面上，需要监测的区域为S，在解的D维搜索空间里有n个粒子作为预备解，随机部署m个传感器节点，则群体中的第i个粒子位置为si=(xi1,yi1;xi2,yi2;xi3,yi3;…;xim,yim)，其中，每一个传感器节点在更新过程中有一个速度向量，用于更新当前速度和位置。每个粒子在自动更新过程中，会经历一个表征个体最优解的位置和一个表征全局最优解的位置。首先是每个传感器节点根据当前的速度和自身位置以及邻居节点的位置更新当前的速度，进而更新当前的位置，所有传感器节点的当前速度和当前位置得到更新之后就计算一次适应值，粒子则通过新的适应值不断跟踪个体最优解Pid=(pi1,pi2,pi3,…,piD)和全局最优解Pg=(pg1,pg2,pg3,……,pgd)进行搜索，以最优适应值为目标更新自己。适应值由传感器网络的节点位置所确定的覆盖率大小决定，每次更新之后的覆盖率应当大于上次更新之后的覆盖率，在达到最终条件或最大迭代次数时终止。

根据粒子的自动移动特点，速度和位置的更新公式为

(3)

(4)

2.2 重点区域监测

经过PSO运算后的传感器节点位置是使网络覆盖均匀且覆盖率最大的最优位置，考虑到受污染严重的区域需要更多的传感器进行监测，本文运用传感器节点可以自由移动的特点，将距离重点监测区域小于传感器半径的节点，部署到重点监测区域内，实现对污染严重区域的实时重点监测。

3 仿真结果

本文采用PSO算法对传感器节点在监测区域内进行网络覆盖率最大化的最优部署，在100m×100m的水域内，以2m为边长划分网格以计算覆盖率。设定传感器半径为10m，最大迭代次数为300，最小覆盖率为50 %，粒子速度更新加权因子采用线性变化的调节方式，粒子速度更新的加权常数c1和c2设定为2。迭代计算中，当迭代次数大于最大迭代次数或者覆盖率小于最小覆盖率，则计算停止，保存最优结果退出粒子更新过程。为了选取最合适的粒子群数目，本文首先进行了多组不同粒子群数目的实验仿真，结果如图2，实验结果表明，随着粒子群数目的增大，网络覆盖率先增大后减小，当粒子群数目为20时，网络覆盖率最大。

基于PSO的网络覆盖率优化的最终仿真结果如图3～图6，图3表示在设有重点监测区域的水域内随机部署传感器节点的位置，一般应用于传感器网络的初始部署，监测水域内部的方框内需要重点监测的区域。图4是节点随机部署经过PSO算法迭代更新后的最优位置，此时网络节点实现均匀部署且覆盖率取得最大。

图2 粒子群数目对网络覆盖率的影响Fig 2 Effect of particle swarm number on network coverage

图3 传感器网络随机部署Fig 3 Random deployment of sensor networks

图4 传感器网络均匀优化部署Fig 1 Acoustic field of two different probes in oil pipeline

图5是PSO下覆盖率的更新变化过程，可见传感器的初始随机部署下的覆盖率并不是很大，这反映出在传统部署中，随机抛洒传感器节点的部署方式没有经过PSO后的部署方式覆盖范围大。经过PSO的传感器网络覆盖率在全局和局部上都可以提高到0.837 6，说明PSO 的优化性能有很高的有效性和可靠性，且不容易陷入局部最优。图6是在传感器网络满足目标函数的最优部署前提下，利用传感器节点可移动的特点，将重点监测区域周边，距离小于传感器半径的节点移动到重点监测区域内，实现实时重点监测，其他区域仍可保证均匀最大范围的部署方式。

图5 网络覆盖率更新过程Fig 5 Network coverage update process

图6 传感器网络对重点监测区域的有效部署Fig 6 Sensor network to optimize the final deployment

4 结束语

采用PSO算法以最大覆盖率为最优目标对传感器节点进行最优部署，使网络在监测水域上达到最大范围的覆盖，从而测量到最完整准确的水质信息，并针对重点监测水域进行了集中性的实时覆盖监测。本文仿真结果说明了算法的有效性，对传感器网络的重点区域的集中性监测也使本文的研究具有重要的实际意义。值得注意的是，粒子群数目的选取需要根据经验和实验判断，选取最优的参数值，能够保证得到最好的仿真结果。

[1] 赵 吉，纪志成.基于量子行为粒子群优化算法的定位技术研究[J].传感器与微系统，2012，31(5):58-61.[2] 王 哲，李 平.近邻点联合测距修正粒子群优化定位算法[J].传感器与微系统，2016,35(8):130-133.

[3] 冀文娟，石为人，李 明，等.异构无线传感器网络中多目标优化节点部署策略[J].传感器与微系统，2012，31(3):29-31.

[4] 彭丽英.改进的蚁群算法网络节点覆盖优化研究[J].计算机仿真，2011，28(9):151-153.

[5] 夏 娜，王长生，郑 榕，等.鱼群启发的水下传感器节点布置[J].自动化学报，2012，38(2):295-302.

[6] 欧阳丹彤，何金胜，白洪涛.一种约束粒子群优化的无线传感器网络节点定位算法[J].计算机科学，2011，38(7):46-50.

[7] 顾晓燕，孙力娟，郭 剑，等.一种有向传感器网络改进粒子群覆盖增强算法[J].重庆邮电大学学报:自然科学版，2011，23(2):214-219.

[8] 林威建，郝泳涛.基于改进粒子群的无线传感器网络覆盖优化算法[J].电脑知识与技术，2015，11(28):36-39.

[9] 仲元昌，赵贞贞，王 恒，等.无线传感器网络中的覆盖优化算法[J].计算机工程， 2012，38(8):57-60.

孙 茜，通讯作者，E—mail:sunqian0403@hotmail.com。

Research on optimization deployment of water quality sensor based on particle swarm optimization algorithm*

YU Xing-yun, SUN Qian, WANG Xiao-yi, XU Ji-ping, WANG Li, ZHANG Hui-yan

(School of Computer and Information Engineering,Beijing Technology and Business University,Beijing 100048,China)

It is desirable to propose a centralized coverage method when monitoring key areas under different pollution levels.Particle swarm optimization(PSO)algorithm based on weighted factors adjustment is used,and compare effect of particle numbers on network coverage ability.According to the simulation results,the sensor nodes can achieve fast-adaptive and well-distributed deployment,as well as avoiding local optimal.With the increase of swarm size,coverage ability of the sensor network is becoming larger,however decreasing after 20.It is of high importance that key water area is covered by sensor nodes after uniformly deployment,hence ensuring the reliability of the water quality data.

sensor network; covering deployment; water environment monitoring; particle swarm optimization(PSO)

10.13873/J.1000—9787(2016)12—0030—03

2016—10—19

北京市市属高校创新能力提升计划资助项目(PXM2014—014213—000033)；2014年度北京市市属高校青年拔尖人才培育计划资助项目(CIT&TCD201404031)；北京工商大学青年教师科研启动基金资助项目(QNJJ2015—20)

TP 212.9

A

1000—9787(2016)12—0030—03

余幸运(1992-)，女，重庆人，硕士研究生，研究方向为水环境监测技术、传感器网络技术。