赵 凌

(铁道警察学院 轨道交通安全保卫系， 郑州 450053)

依照《铁路安全管理条例》，高铁线路应全线封闭管理，禁止无关人员入内。然而，不法分子往往通过翻越或破坏护栏，攀爬低矮路基、低矮桥墩或疏散通道等重要部位进入高铁线路内部对相关设施或在建设备实施破坏、盗窃，危及列车行车安全及工程建设[1]。通常情况下，事发后不法分子已逃之夭夭，且高铁线路多地处郊外，实施全线视频监控成本较高、可行性尚需调研，这进一步加大了案件取证难度。

无线传感器网络(wireless sensor networks， WSN)的应用特点[2]为高铁线路重要部位入侵报警提供了可行方案。然而，在高铁线路重要部位大量部署传感器节点会使得目标监测区域内的各节点通信覆盖相互交叉，共享的无线信道干扰加剧，数据可靠传输受影响，导致节点因网络冗余能耗开销过大而提前“消亡”[3-4]。而监测盲区一旦形成将会给不法分子可乘之机。从近年的研究成果来看，文献[5]提出了一种WSN节点覆盖重叠最大有效覆盖率的控制算法，对节点控制覆盖进行了求解和验证，并结合概率方法在一定程度上解决了节点冗余问题。文献[6]为防止目标区域出现监测盲区，首先利用改进人工鱼群算法对WSN节点进行了自适应定位寻优，再以此为基础对节点分布模型进行优化，改善了节点覆盖质量。文献[7]在对WSN节点覆盖漏洞分类的基础上，提出了最小圆修补算法和蜂窝生长修补算法，提高了目标监测区域的节点覆盖率。但上述算法对节点覆盖质量缺乏明确的评价方法，对节点交叉覆盖也缺乏直观的优化依据。本文针对目标监测区域特点，使用二元感知模型[8]，基于遗传算法[9]优化节点覆盖率，同时尽可能减少工作节点数量。

1 高铁线路重要部位与WSN节点感知模型

从人力防范和实体防范的角度，可将高铁线路重要部位分为有人值守、无人值守和定期巡守3类，本文主要研究定期巡守的3种重要部位：低矮路基、低矮桥墩和在建高铁建材设备所在地[1]。其入侵报警系统结构见图1。

图1 基于WSN的高铁线路重要部位入侵报警系统结构

1.1 网络模型

在环境条件比较恶劣的高铁线路重要部位(低矮路基、低矮桥墩外围护栏内侧和在建高铁建材设备附近)部署WSN节点实现入侵报警功能。假设网络模型如下：

1) 将图1中涉及的高铁线路重要部位看作一个二维平面的目标监测区域，部署在该区域的WSN节点都由1个汇聚节点和大量分布于平面上的无线传感器节点组成，每个节点都有全网唯一标识；

2) 所有节点一经部署不再移动；

3) 除汇聚节点外，其余节点能量有限；

4) 每个节点的位置信息是确定的；

5) 所有节点时间同步；

6) 节点周期性感知所在区域的入侵报警信号，借助已有的路由协议(如LEACH[10]或PEGASIS[11])经汇聚节点和无线网络将信息传至监控中心，实现实时预警。

1.2 提出问题

若监测区域中的每个目标节点至少被集合E中的一个节点感知覆盖，仅当d(ei，ej)≤Rc时，认为集合E中各节点之间都至少存在一条通信路径。各节点和通信路径形成的网络图形为通信连通图，集合E为目标监测区域的一个连通覆盖集[12]。由此，本文研究的重点可转化为：确定在二维平面上部署WSN节点时所形成的最优连通覆盖集，即利用最少节点达到最大网络覆盖率。

1.3 WSN节点感知模型

节点的感知模型是节点覆盖范围和监测能力的决定性因素。从现有的文献来看，节点感知模型一般分为3类：二元感知模型、概率感知模型和分段感知模型[13]。后两种模型在一定概率的条件下可以转化为简单二元感知模型[14]。为方便分析计算，本文采用二元感知模型模拟节点的感知能力。

以二维平面作为目标监测对象，二元感知模型将传感器节点抽象为1个以节点位置为圆心、以Rs为感知半径的平面圆，Rs由节点本身的物理特性决定。

在二元感知模型下，若传感器节点ei的坐标为(xi，yi)，对于监测区域内的任意目标点T(x，y)，ei与T(x，y)间的欧氏距离为

(1)

那么，当d(ei，T)≤Rs时，认为目标点T(x，y)被传感器节点ei覆盖。假设Pxy(ei)表示ei对T的感知概率，那么：

(2)

为进一步构建传感器节点集合E={e1，e2，…ei，…，en}的感知模型，需引入随机变量mi，i∈[1，n]，用于描述目标点T(x，y)被ei覆盖，即mi：d(ei，T)≤Rs。令mi对应的概率为P{mi}，那么：

(3)

(4)

当ei与ej共同覆盖目标点T(x，y)时，可用mi∪mj表示。若监测区域中各WSN节点相互独立感知同一目标点，即各mi相互独立，mi与mj是不相关的，i，j∈[1，n]，且i≠j，则有：

(5)

由式(5)可得，对于传感器节点集合E，目标点T(x，y)被E覆盖的概率即各mi对应概率的并集，可得该概率为

(6)

在二元感知模型下，若E中有1个节点覆盖了目标点T(x，y)，则称T(x，y)被E覆盖；若E中没有传感器节点监测到T(x，y)，则称T(x，y)未被E覆盖。

将目标监测区域TA看作由l×k个像素点组成的离散区域，如图2所示，每个像素点即传感器节点要感知的目标点。设每个像素点的面积为Δx·Δy，据此可以计算出目标监测区域的总面积，记为ATA，则：

(7)

设E的区域覆盖面积为AES，结合式(5)可得：

(8)

由此，传感器节点集合E对目标监测区域的覆盖率CR=AES/ATA为

(9)

1.4 WSN节点交叉覆盖模型

(10)

其中i，j∈[1，n]，且i≠j。由此可知，当目标点T(x，y)与传感器节点ei和ej的距离都小于传感器节点感知半径Rs时，认为T(x，y)被ei和ej交叉覆盖。若节点ei所覆盖的区域已完全被其他节点覆盖，此时ei可进入低功耗休眠状态，不影响对整个目标监测区域的覆盖。

图2 二元感知模型下的目标监测区域示意图

2 基于遗传算法的WSN节点覆盖集优化算法设计

文献[15]证明了节点集选取问题属于NP完全问题[16]，遗传算法按并行方式群体寻优，在解决NP问题方面优势强大[17]，其运算流程如图3所示。

图3 遗传算法运算流程

2.1 编码

节点覆盖集选取的任务是从WSN节点集合中选择一组覆盖效果最优的节点工作，其余节点进入低功耗休眠状态。采用位串bs={bs1，bs2，…bsi，…，bsn}将实际问题映射为对应的编码参数集，即：

(11)

若目标监测区域部署10个WSN节点，则位串长度为10位。假设传感器节点e2、e4、e6、e8、e10处于工作状态，则此位串可表示为0101010101，如图4所示。

图4 编码映射示意图

2.2 建立初始种群

利用编码映射建立1个由L个传感器节点组成的初始种群，每个个体的染色体均由m个基因构成，初始化种群如式(12)所示。

(12)

2.3 确定适值函数

文献[18]中已经证明：当传感器节点的无线通信半径至少是其感知半径的2倍，即当Rc≥2Rs时，在传感器节点充分覆盖目标监测区域的前提下，传感器节点集合E总能保持连通性。

第1个目标函数是节点覆盖率函数，设为f1(x)，由式(9)可知：

f1(x)=CR

(13)

第2个目标函数是工作节点数量函数，设为f2(x)，则有：

f1(x)=n′

(14)

其中n′为工作状态节点数量。

由式(13)(14)可知，将f1(x)、f2(x)作为比值，比值越大，节点覆盖率相对越高，同时节点数量就相对越少。如此，将多目标函数转化为单目标函数。总目标优化函数设为fobt(x)，则有

(15)

当fobt(x)值越大时，节点选取方案越优越。

2.4 选择、交叉、变异、取代

选择操作提高了遗传算法的全局收敛性，常用的选择算子有随机联赛法、随机便利抽样法和轮盘赌法[19]，本文采用轮盘赌法。传感器节点个体被选择的概率与其适值大小成正比，设个体被选择的概率为Pcl，则

(16)

其中：wi是个体bsi的适值；K是种群规模。

交叉算子Pc决定了遗传算法的全局搜索能力，本文采用单点交叉方式[20]实现交叉操作。若Pc值过大，个体更新过快，高适值个体会被快速破坏；反之，Pc值过小也会导致搜索停滞甚至算法不收敛，故Pc值一般取0.25～1。

变异算子Pm决定了遗传算法的局部搜索能力，本文采用基本位交叉方式[17]实现交叉操作。若Pm值过大，很可能致使遗传算法变为随机算法；反之，Pm值过小将难以产生新的个体。一般Pm值取0.001～0.1。

当子代个体的适值大于父代时，发生取代操作。

2.5 局部搜索优化策略

在每一代取代操作发生之前，改变Indi的基因gij对应节点ej的工作状态，即由1变为0，若此时的节点覆盖率提高或保持不变，则保留0状态；若节点覆盖率下降则恢复节点为ej工作状态[21]。遍历所有基因，比较新旧染色体适应度值，若适应度值变大或不变，则保持修改，否则恢复修改。运行遗传算法和局部搜索优化策略后得到新种群的适应度值至少大于等于原种群，进一步加速算法收敛过程。

3 仿真实验分析

采用Matlab R2014a遗传算法工具箱，对所设计的算法进行测试，在100 m×100 m的目标监测区域部署WSN节点。取种群大小为L=10，交叉算子Pc=0.75，变异算子Pm=0.05。

3.1 随机部署节点覆盖仿真

为验证本文设计算法的优化效果，首先对随机部署节点情况进行仿真。

随机状态下，设置节点覆盖率>99%时，算法停止部署节点。由图5可知，当节点感知半径Rs=8 m时，所需节点数量为229；当Rs=14 m时，所需节点数量为116。即使感知半径增加，所需工作节点总数有所减少，但节点交叉覆盖依然突出。

图5 随机部署节点

3.2 遗传算法优化节点覆盖仿真

为获得最优连通覆盖集，在仿真中考虑了高铁线路防入侵精度及便于部署节点等因素，将节点的感知半径设置为一个变化的区间，选取Rs∈[5，11]。算法从开始运行至100代期间，覆盖率每变化1次，算法抓拍1次运行结果，顺序抓拍结果如图6所示。

图6 顺序抽样抓拍节点覆盖情况

根据算法运行结果，图6(a)～(f)所对应的总目标函数值如表1所示。

表1 顺序抽样总目标函数值对照表

由图5和表1可知，算法在前100代运行期间，Rs由5增至10，节点覆盖率整体变化趋势不稳定，但工作节点数量逐渐变少。由此可见，随着Rs的增大，工作节点数逐渐减少，总目标函数值逐渐变大，节点覆盖集优化趋势明显。

为进一步验证优化效果，令算法分别运行100、200、300和400代，得到节点覆盖情况如图7所示。

由图7可知，随着算法迭代次数的增加，节点覆盖率由96.06%增至97.73%，工作节点数量为54，保持不变，算法优化成效显著。根据算法运行结果，图7(a)～(d)对应的总目标优化函数值如表2所示。

表2 算法运行结果统计

图7 节点覆盖集优化过程

显然，算法运行至100代后，工作节点数量始终为54，输出结果显示此时的节点感知半径Rs=10 m，如图8所示。

图8 算法运行400代时的结果

图9给出了表2对应的总目标函数在算法运行400代期间的变化曲线。随着迭代次数的增加，总目标函数变化曲线趋于直线，搜索向着全局最优解方向发展。由此可见，该节点覆盖算法获得了理想的覆盖集选择方案。

图9 总目标函数变化曲线

为进一步验证本文算法的先进性，进行节点覆盖率对比。由图10可知：在相同实验环境和算法运行的迭代次数条件下，本文算法的节点覆盖率大于遗传算法，且随着迭代次数的增加，本文算法要早于遗传算法实现对目标监测区域的全覆盖。由此可见，局部搜索优化策略进一步优化了节点覆盖能力。

图10 节点覆盖率对比曲线

4 结束语

本文基于遗传算法优化设计了WSN节点覆盖集的高铁线路重要部位入侵报警过程，为在二维平面区域科学合理地部署传感器节点提供了参考。设计的节点覆盖集优化算法同时减少了目标监测区域的节点交叉覆盖和节点数量，与遗传算法相比，优化了节点覆盖能力。仿真结果表明：该算法具有良好的收敛特性，为下一步实地部署WSN节点、测试全网入侵报警功能提供了理论支撑。