铁路监测WSN网络的非均匀优化分簇算法

吕安琪， 李翠然， 谢健骊， 段宝峰

(兰州交通大学 电子与信息工程学院， 甘肃 兰州 730070)

目前高速铁路列车的时速已高达350 km/h，在确保高速列车安全运行方面，轨旁环境监测系统已至关重要。无线传感器网络WSN(Wireless Sensor Network)具有部署简单、维护成本低、组网灵活、中继转发等特点，在轨道两侧部署基于WSN的环境监测系统可以高效、可靠地采集环境数据，从而对列车运行做出正确的防护措施。铁路环境的特殊性使铁路沿线部署的WSN网络呈线型结构，同时由于WSN节点只能由电池供电，由此产生了“能量空洞”现象[1]，即网络以多跳的方式进行信息传输，随着跳数的增多，信息累积量增大，靠近Sink节点的普通WSN节点能耗大，其电能过早耗尽而导致网络中断的现象。如何构建合理的节点部署模型，有效降低甚至避免“能量空洞”现象，是铁路沿线WSN部署研究亟待解决的关键问题。

关于线型WSN网络中的“能量空洞”问题，已有大量研究成果。ZHANG等[2]提出一种基于信息融合的数据传输机制，通过控制信息粒度对原始数据进行不同程度的信息融合，从而减少传输数据量，节省传感器网络能量；刘安丰等[3]提出一种基于能量效率的高效节点部署算法，在已知网络规模和节点感知距离的情况下，可求出最佳中继节点部署和节点最优传输距离；文献[4]通过节点休眠机制调整路由算法，从而提高网络的能量利用率、可靠性以及实时性；在文献[5]提出的能耗均衡算法中，采用了改进粒子群策略，对WSN中继节点的位置进行寻优，均衡了节点能耗；文献[6]以轨道交通为背景，提出基于布朗圆盘和Voronoi图的几何算法，通过建立两棵传感器树形结构得到理想拓扑结构，延长网络寿命，提高网络性能。

上述文献中，多假设节点随机分布，并不适用于实际的监测环境。文献[7]中以WSN节点的线性、均匀部署为前提，以节点转发信息的能量消耗和能量平衡作为约束条件，采用非线性方法建立了一种线性WSN网络调度策略以平衡节点能量消耗。王楠等[8]提出了一种等距分组多跳路由算法，建立了能耗数学模型，通过优化数据传输方式延长了网络寿命。文献[9]以铁路环境为依托，通过非均匀分区方式调整各区内的节点数目，以达到均衡节点能耗和延长网络寿命的目标。基于上述研究成果，本文着重从铁路环境的监测应用角度出发，全面地考虑了直线轨道、弧线轨道监测区域内的节点非均匀优化分簇与部署，以簇头负载均衡度和簇头能耗平衡度为计算依据，确定了簇的大小和簇头的优化位置。仿真测试表明，所提算法在均衡簇头节点能耗和提高网络通信效率方面性能较优，有效地解决了“能量空洞”问题，延长了监测网络生命周期。

1 节点部署模型

针对铁路环境监测，以直线轨道和弧线轨道监测为具体应用场景，需对WSN节点部署模型展开分析。本文给出的假设条件：设轨道长度为L(直线或弧线长度)，节点感知半径为r，簇的数目为k，分别为c1,c2,…,ck。网络中节点类型分为2类，即簇头节点CH(Cluster Head)与簇成员节点CM(Cluster Member)，节点部署方式有:

(1) 直线轨道部署 首先是初始化CM节点位置。CM节点沿直线轨道单侧部署，节点间距相等且小于2r，见图1(a)，CM节点监测信息的采集。采用非均匀分簇算法(见下文)将监测区域划分为不同的簇，并通过仿真筛选出合适的CH节点位置，见图1(b)，CH节点位置坐标记为ci(i=1,…,k)，用于接收、处理和转发簇内CM节点采集到的信息；di为第i个簇的覆盖距离。CM节点将采集的数据发送至本地CH节点，本地CH将信息融合后传输至相邻CH，通过多跳、转发方式就可将信息传输至用于连接外网的汇聚节点Sink，即c1→…→ck→Sink。

(2) 弧线轨道的分簇部署 CM节点沿弧线半径R轨道单侧等距部署，且相邻CM间的直线距离小于2r，见图2(a)。同样通过仿真非均匀分簇算法(见下文)即可筛选出合适的CH节点位置，见图2(b)中，O表示圆心，R为弧线轨道半径，θi(i=1,…,k)为第i个簇的圆心角，弧线轨道WSN中的信息传输方式与直线轨道相同,(x,y)为传感器节点坐标。

2 非均匀分簇算法

2.1 算法设计

假设WSN网络中的CM节点具有如下性质[10]：

(1) CM节点同构，每个节点在单位时间内产生lbits数据，且均需发送至Sink节点；

(2) 节点具有相同的初始能量E0，仅考虑节点发送、接收数据的能量消耗，而感知与处理数据的能量消耗忽略不计，且不考虑数据传送时数据的冲突和重传；

(3) 节点间通信距离等于实际部署中两节点间的直线距离。

节点采用典型的能量消耗模型[11]，发送、接收数据的能量消耗分别为

( 1 )

ER=lEelec

( 2 )

式中:ET为节点发送lbits数据消耗的能量;ER为节点接收lbits数据消耗的能量;α取值为 2时采用自由空间模型或α取值为4时采用多径衰减信道模型;d0为区分两种模型的距离阈值;d为收、发两端的距离;Eelec为发射电路消耗的能量;εfs为自由空间信道模型功率放大系数；εamp为多径衰减信道模型功率放大系数。

在需要监测的铁路沿线(直线轨道或弧线轨道)等距部署CM节点，以均衡CH单位时间能耗为优化目标，对监测区域进行非均匀分簇，且所分簇间不发生重叠(即前一个簇的末端是下一个簇的始端)，并根据簇的覆盖距离确定CH位置。非均匀分簇算法的执行步骤为

Step1沿待监测的轨道沿线等距部署CM节点。

Step2初始化簇1和簇2的相关参数(簇头节点位置坐标c1、c2，簇的覆盖距离d1、d2)。

Step3计算CH的位置坐标ck，k=3,4, …。

2.2 直线轨道的节点分簇

在直线轨道节点部署图1(b)中，令ai为第i个CH节点与第i+1个CH节点间的传输距离，表示为

ai=ci+1-cii=1,2,…

( 3 )

当给定相邻CM节点间的传输距离D时，则第i个簇内的CM节点数目Ni(取整后)计算为

Ni=di/D+0.5i=1,2,…

( 4 )

节点c1在一轮数据采集周期Tc内的能量消耗E1包括2部分，即接收d1区域数据的能耗Er1和传输数据至c2的能耗Et1,E1为

( 5 )

节点c2的单位周期能耗E2包括3部分，即接收d1区域数据的能耗、接收d2区域数据的能耗和传输数据至c3的能耗,E2为

( 6 )

当k=3,4, …时，节点ck的单位周期能耗为

( 7 )

当各CH节点的能耗满足式( 8 )时，WSN网络能耗达到均衡

E1=E2=…=Ek

( 8 )

根据式( 3 )～式( 8 )，可得到CH节点的位置坐标递推式为

( 9 )

直线轨道情形下的节点非均匀分簇部署约束条件为

(10)

2.3 弧线轨道的节点分簇

在弧线轨道节点部署图2(b)中，令hi为第i个簇对应的弧长，表示为

(11)

假设θci为第i个簇内的簇头节点与初始点对应的圆心角，ai为弧线轨道上节点ci与节点ci+1间的直线传输距离，计算为

(12)

为相邻CM节点间的弧线距离H为

H=2πR[2arcsin(D/2R)/360°]

(13)

则第i个簇内的CM节点数目Ni(取整后)计算为

Ni=⎣hi/H+0.5i=1,2,…

(14)

当各CH节点的能耗满足式( 8 )时，WSN网络能耗达到均衡。由此得到CH节点对应的圆心角递推式为

(15)

假设弧线轨道的圆心坐标用(R, 0)表示，簇边界坐标为(xi,yi)，CH节点坐标为(xci,yci)，其间的函数关系可表示为

(16)

弧线轨道情形下节点非均匀分簇部署约束条件为

(17)

继而给出网络生存周期和网络效率的定义。

定义1网络生存周期 网络中第1个节点死亡的时间(节点寿命)。

定义2网络效率 网络寿命与网络内CH节点数目的比值。

假设WSN网络中的节点初始能量为E0，CH节点ci的单位时间能耗为Ei，则节点ci的寿命ti和网络生存周期T分别为

ti=E0/Eii=1,2,…

(18)

T=min{ti}i=1,2,…

(19)

文中引入了簇头负载均衡度B与簇头能耗平衡度BH这2个参量，分别表示为

(20)

(21)

3 仿真分析

本节利用Matlab工具对提出的节点非均匀分簇部署算法进行仿真评估。具体仿真参数见表1[12]。

在直线轨道情形下，仿真得到了50组满足式( 8 )CH节点能量均衡条件的数据，记为(ck， ∑di)。CH节点的能耗波动趋势见图3(a)。其中，x轴为数据组编号，1～50；y轴为对应组号的数据，即CH节点的位置；z轴为CH节点的单位时间能耗。能量等高线见图3(b)，可见第37～50组的CH节点能耗波动最大且能耗最高，第1～14组的CH节点能耗波动次之且能耗较高；第31～36组的CH节点能耗波动较小且能耗中等；第15～30组的CH节点能耗波动最小且能耗最低。不同数据组的B/BH值见图3(c)，进一步筛选出较优的数据组。

表1 仿真参数

在筛选数据组时，先考虑CH节点能耗及其波动，再综合考虑B/BH这2个参数值，由此得到较好的数据组号为16，17，20，24和28。可从以上5组数据中任取一组数据构建WSN网络模型，以下仿真使用的是第28组数据，对应的(ck，∑di)取值为：(160，180)，(420，440)，(567，580)，(686，700)，(786，820)，(870，920)和(942，1000)，得到的节点优化部署模型见图4。在绿色圆点与红色加号重合的位置，可将该CM节点设定为CH节点，此时无需再另行放置CH节点。

在弧线轨道情形下，通过仿真得到了66组满足式( 8 )CH节点能量均衡条件的数据组，以CH的位置坐标(xci,yci)及其圆心角来标记。CH节点的能耗波动趋势见图5(a)。由图5(a)可看出，沿弧线轨道部署的WSN网络几乎达到了理想的CH能量均衡状态，其中，第1～9组和第10～21组的CH能耗最小。再结合图5(b)给出的B/BH参数值，筛选出的较优数据组为第9组，对应CH坐标值为(2.4，140)，(20，399)，(37.4，545.7)，(55.9，666.5)，(74.3，767.5)，(92.3，854.5)和(109.4，929.2)，圆心角分别为2°、5.7°、7.8°、9.6°、11.1°、12.3°、13.4°，得到的节点优化模型见图5(c)。图中标识与直线轨道模型中的相同，不再赘述。

为进一步评估文中所提出的非均匀优化分簇算法部署效果，在相同簇数目情形下，不同算法构建的WSN网络中的CH节点能耗、CH节点寿命和网络效率分别见图6～图8。

图6中，簇头固定的非均匀分簇是指CH节点位于簇几何中心；均匀分簇是指WSN网络中各个簇的覆盖距离相等；组数据传输是指将网络中的节点分组，数据由多条链路同时传输[13]。由图6可见，均匀分簇算法和组数据传输算法的节点能耗呈非均匀态势，组数据传输算法的节点能耗远低于均匀分簇算法；文中算法与簇头固定的非均匀分簇算法的节点能耗呈均匀态势，所提算法在直线和弧线轨道部署中的节点能耗均低于簇头固定的非均匀分簇算法。分析可知，组数据传输算法虽然降低了某些节点能耗，但无法消除节点能耗不均衡的现象，本文提出的非均匀优化分簇算法的节点能耗分布均匀且能耗低于组数据传输算法的最大节点能耗，具有较优的性能。

非均匀优化分簇算法在直线与弧线情况下的节点寿命相差无几，仿真时会出现线条掩盖现象，因此，图7中选择非均匀优化分簇算法(直线)与其他算法进行对比。由于网络生存周期或节点寿命仅与最早死亡节点的时间有关，非均匀优化分簇算法的节点寿命最长，其次为簇头固定的非均匀分簇和组数据传输算法，均匀分簇算法的网络生存周期最短。

图8中算法1～算法5分别对应簇头固定的非均匀分簇、非均匀优化分簇(直线)、非均匀优化分簇(弧线)、均匀分簇和组数据传输算法。由图8可明显看出，非均匀优化分簇算法的网络效率最高，簇头固定的非均匀分簇和组数据传输算法次之，均匀分簇算法性能最差。

4 结束语

为解决铁路沿线WSN线性部署导致的“能量空洞”问题，本文提出了一种节点非均匀优化分簇算法。算法以簇头节点能耗、簇头节点数目和簇成员节点数目之间的函数关系为基础，构建了直线轨道、弧线轨道监测区域内的节点非均匀优化分簇模型，实验结果表明，本文算法与簇头固定的非均匀分簇、均匀分簇以及组数据传输算法相比，有效地降低了CH节点能耗、提高了网络效率，延长了WSN监测网络的生存周期。考虑到铁路场景中相邻站点间的距离较长，当簇数目增多时，算法性能会有所下降。下一步的研究将通过控制策略调整簇的覆盖距离，并在铁轨沿线每隔一定距离处增设汇聚节点Sink。此外，如何快速构建最优的非均匀分簇是面向铁路应用的关键，进一步的研究思路是根据不同站点间的铁路轨道长度和类型(直线、弧线)，评估算法的时间复杂度，以满足铁路应用的监测组网需求。