第一作者:邓胜江(1979—),北京人,副研究员.研究方向为铁路旅客运输. email:13811345060@139.com.
客运车站环境的监测对于保障车站安全运营和为旅客提供舒适出行具有重大意义.基于无线传感器网络(WSN)的客运车站环境监测全覆盖策略,依据被监测区域中已部署的传感器节点对区域进行Voronoi划分,计算Voronoi图中三角形的覆盖比,提出基于Voronoi三角形覆盖比的全覆盖算法,该算法通过逐个添加新的传感器节点修复覆盖空洞.仿真结果表明:所提算法在实现监测区域全覆盖的同时能够有效减小由于大量部署传感器节点所造成的覆盖冗余.
It is of great significance for environmental monitoring of passenger station to ensure the safe operation and provide comfortable travel for passengers. This paper mainly studies, based on Wireless Sensor Network (WSN), coverage strategy for environmental monitoring of the passenger station. According to the deployed sensor nodes, the monitored area is divided by Voronoi diagram and the coverage status of all triangles in it is calculated. Then an algorithm named Voronoi Triangle Coverage Ratio (VTR) is presented, which can repair the coverage holes by adding corresponding new nodes. The simulation results show that the proposed algorithm not only achieves the full coverage, but also effectively reduces the redundant coverage due to mass deployed sensor nodes.
客运车站是旅客乘坐火车出行过程中进行候车、登乘、中转换乘的主要场所, 而客运站内的环境状况也直接影响着旅客出行的舒适体验度.通常情况下, 客运站内的环境主要由温度、湿度、亮度和噪声等4个关键要素形成, 考虑到无线传感器网络所具有的免布线、低功耗、部署灵活、易维护等特点, 通过在客运车站内部署温度、湿度、亮度、噪声等传感器监测客运站环境参数, 并依据旅客舒适度指标自动调整车站空调、风机、照明、LED显示屏、扬声器等设备, 从而为旅客的温馨出行提供保障.
针对无线传感器网络, 网络的覆盖情况反映了其对被监测区域的监控完整程度, 是衡量无线传感器网络服务质量的一项基本指标[1].因而, 如何针对车站内各环境因素的特点合理部署传感器节点从而达到对客运车站无盲区全覆盖的监测是基于WSN的客运站环境监测研究中首要解决的问题.
为了实现对被监测区域的充分覆盖, 实际工程中往往通过大规模、高密度地部署传感器节点来提高网络的覆盖率.然而, 在这样的部署策略下, 虽然可以显著提高网络覆盖率, 但同时也会造成网络中节点的覆盖区域严重重叠, 由此引起信息的冗余采集和传输, 以及信道冲突和干扰.
现有针对网络覆盖控制的相关研究主要可以分为两类:一类是基于冗余节点的休眠调度策略, 如文献[2]中采用对满足冗余的节点进行休眠调度方法保证网络的覆盖率和连通性, 同时减少网络总能耗.文献[3]提出了基于冗余节点休眠和分阶段唤醒的传感器网络三维覆盖控制算法.不同于基于休眠调度策略通常需要部署大量的冗余节点; 另一类覆盖控制方法是以Voronoi图为基础研究无线网络的空洞侦测和修复策略.文献[4]将全覆盖问题转化为Voronoi构建和圆覆盖的几何问题.文献[5]研究了基于Voronoi图和移动节点的动态空洞修复.文献[6, 7, 8]研究了不同应用领域中将Voronoi图用于基于能耗的传感器部署.文献[9]提出基于Voronoi覆盖机制的MRTc算法, 通过准确控制节点工作状态, 实现活动节点对目标区域的完全覆盖.然而, 现有的基于Voronoi网络覆盖的文献中大都采用静态修复的方式, 容易造成网络中存在大面积感知区域重叠, 且在空洞修复过程中缺乏对传感器节点感知区域和Voronoi多边形几何位置的量化描述.
本文作者结合客运车站环境监测需求, 通过初始部署的传感器节点将车站中被监测区域进行Voronoi划分, 并利用局部Voronoi图寻找覆盖率最小的区域, 提出了三角覆盖比的概念, 对Voronoi多边形与传感器节点感知范围的位置关系进行量化描述, 同时从空洞的占比大小角度寻找具有最小覆盖比的区域作为优先修复区, 并指定节点部署具体位置来迭代添加新的传感器节点.所提方法完全采用分布式的计算方式, 针对密集部署的传感器网络本文所提算法的复杂度也不会出现指数增加.
本文的主要工作:1)通过已部署节点将整个被监测区域进行Voronoi划分, 提出针对Voronoi图中每个三角形区域的空洞面积覆盖比概念; 2)提出基于Voronoi三角形覆盖比的网络全覆盖算法(VTR), 通过指定每次新节点的部署位置, 迭代更新Voronoi划分, 在保证网络完全覆盖的同时减小覆盖冗余.
假设客运车站中部署的传感器节点集合为
现有文献中关于传感器节点感知模型的研究大致可以分为二元感知模型, 概率感知模型和分段感知模型[10]3类.由于概率感知模型和分段感知模型在满足一定感知概率的条件下可以简化为二元感知模型, 且目前关于WSN覆盖问题的研究工作中大部分采用二元感知模型[11], 本文为了计算和分析的方便, 同样采用如下所述的二元感知模型.
具体地, 在二元感知模型中, 位于传感器节点
针对客运车站的环境监测, 通常需要部署不同类型的传感器节点如温、湿度传感器、亮度传感器和噪声传感器节点等.而不同类型的传感器所具有的感知半径不完全相同, 假设温度、湿度、亮度和噪声传感器的感知半径分别为
针对传感器节点传输半径和感知半径的不同, 本文给出如下的WSN的连通覆盖和感知覆盖的定义, 并进一步给出两者之间相关性的定理.
定义1(连通覆盖) 对于空间
定义2(感知覆盖) 对于空间
定理1 若传感器节点集合
证明:采用反证法, 假设对于给定的节点
那么, 对于除
由定理1可知满足感知覆盖的节点集
基于客运车站待监测区域中已部署传感器节点的位置, 首先构建每个传感器节点的Voronoi多边形.具体地, 如图1所示, 节点
定义3(Voronoi三角形覆盖比) 将Voronoi多边形内的节点与Voronoi多边形的各顶点相连, 构成多个三角形, 以节点为圆心, 以传感器感知距离为半径作圆, 则每个三角形与圆的交集大小与三角形自身面积大小的比值为Voronoi三角形覆盖比.
由于传感器节点
根据节点感知半径大小的不同, 节点的感知覆盖范围通常与节点的Voronoi多边形呈现如图2所示的3种不同的关系.具体地, 假设与传感器节点
1)图2(a)中, 节点
2)图2(b)中, 节点
3)图2(c)中, 节点
针对Voronoi多边形与内部传感器节点所构成的多个三角形, 通过上述Voronoi三角形覆盖比的分类计算可获得每个三角形的Voronoi三角形覆盖比情况.
引理1[14] 假设Voronoi内存在一定数量的空洞, 且
依据引理1可知针对存在空洞的Voronoi多边形中添加新的传感器节点的最优方位为夹角的平分线上, 又由于对两个相邻的Voronoi多边形具有公共Voronoi边的两个三角形是对称的, 如图3所示, 节点
对于同构的无线传感器网络来说, 节点具有相同的感知范围, 因而图3所示的以
针对客运车站中存在感知覆盖空洞的WSN, 1.3节中指出在空洞修复过程中新的传感器节点的添加区域和部署位置通过算法1(VTR算法)详细说明如何通过逐个添加节点来迭代地修复覆盖空洞.
算法1.VTR算法
输入:已知部署位置的初始传感器节点集
输出:全覆盖的客运站环境监测网络
1:for
2:构建Voronoi多边形
3:连接
4:计算
5:end for
6:
7:合并
8:计算集合
9:获得以
10:在
11:重复1~10直到
上述算法中1~5步依据被监测区域中当前所部署传感器节点集合
仿真实验基于Matlab R2014a平台进行, 首先模拟一个200 m× 200 m大小的客运站区域, 在其中随机部署一定数量的某一类型传感器节点, 且传感器节点可以通过定位技术获得自身位置和邻居节点的位置信息.
被监测区域中初始部署20个传感器节点, 图4和图5分别给出了感知半径
通过本文所提的VTR算法对上述覆盖空洞进行修复, 为了说明本文算法的有效性, 将仿真结果与文献[4]中所提出的空洞修复策略(PAL算法)进行比较.图6和图7分别为VTR算法和PAL算法在
图8和图9分别为VTR算法和PAL算法在
此外, 图6和图9还对VTR和PAL算法的覆盖冗余情况进行比较, 其中浅蓝色区域表示同时被两个节点覆盖的区域, 绿色区域为同时被3个节点覆盖区域, 红色则为同时被4个及以上节点覆盖的区域.表1中给出了VTR和PAL算法覆盖冗余的数值比较, 其中
进一步通过改变网络中初始部署的节点个数, 即改变初始节点浓度来观察VTR和PAL算法在所需添加新节点个数及至少被3个节点
针对基于WSN的车站环境监测的全覆盖问题, 本文作者提出了基于Voronoi三角形覆盖比的全覆盖算法, VTR算法具有以下优点:
1)将传感器节点感知范围与Voronoi多边形的覆盖比进行量化描述, 并指定了新添加节点的具体部署位置; 2)通过动态添加节点的方式进行覆盖漏洞的修复, 有效地降低了传感器节点感知区域的重叠.
此外, 本文的研究对于客运站监测区域中实际部署传感器节点实现网络的全覆盖具有良好的借鉴意义.在以后的工作中可以进一步研究算法的精度及模型的应用规模.
The authors have declared that no competing interests exist.
[1] |
|
[2] |
|
[3] |
|
[4] |
|
[5] |
|
[6] |
|
[7] |
|
[8] |
|
[9] |
|
[10] |
|
[11] |
|
[12] |
|
[13] |
|
[14] |
|