基于分簇的铁路应急通信网络路由算法

谢健骊，李翠然＋

（1.兰州交通大学 电子与信息工程学院，甘肃 兰州730070；2.北京交通大学 轨道交通控制与安全国家重点实验室，北京100044）

0 引 言

铁路地形及传输环境的复杂性常常会使铁路移动通信系统中的基站等网元工作失效，此时，需要启动铁路应急通信［1］，以保证铁路行车调度的顺利进行。GSM－R 作为我国铁路综合数字移动通信系统［2，3］，其技术标准 《EIRENEFRSv7》［4］和 《EIRENE－SRSv15》［5］都 提 到 了 为 实 现 故 障 小区内车内终端 （节点）和地面终端之间的正常通信以提供铁路沿线的无线覆盖，需要构建GSM－R应急通信网络。在铁路沿线的应急地点，一般来说节点数目相对较多、移动性相对较强，宜采用分簇结构的GSM－R应急通信网络。综合权重分簇算法作为一种折中各种参数影响的方法，它以优良的簇稳定性而成为一种常用的分簇算法。已有加权分簇算法［6－9］大都基于同构节点、节点数目一般不超过70个且其最大移动速度不超过120km／h而设计，无法很好地支持铁路应急通信中具有不同功能角色的大量异构节点的高速移动，尤其当铁路复杂地形的传播环境极为恶劣时，问题更加突出。此外，在上述文献中，影响簇头选择的各参数权重值相对固定，因此，如何通过调节各参数权重值以适应高速铁路的复杂应用环境是本文的研究重点。此外，我们还将对铁路应急通信网络的分簇路由算法展开研究，通过对平均端到端时延和平均吞吐量性能的仿真，以及与GSM－R的服务质量 （quality of service，QoS）指标对比分析，以验证所提算法在铁路应急通信中的适用性。

1 分簇及簇头选择参数的权重分配

簇头选择参数直接影响到分簇结构的合理性。如何确定簇头选择参数以及各参数对于评估结果的重要性是影响分簇算法性能优劣的关键。我们可以借助粗糙集理论解决这个问题［2］。

（1）建立簇头选择参数决策表。决策表由各样本的条件属性值 （簇头选择参数的决策值）和决策属性值 （网络性能评估等级）组成。其中，样本的条件属性决策值vij由样本每个条件属性参数的测量值和其阈值vjk共同决定，见式 （1）；决策属性则来自灰色聚类理论对服务质量体系进行预评估的结果

对于铁路应急通信网络中的簇头选择参数，除了考虑一般的簇头选择因素外，还需要兼顾GSM－R节点业务等级的差异性等铁路通信特色。因此，本文的簇头选择过程将综合考虑节点度与理想节点度之差 （Dv）、节点的相对簇稳定性 （Sv）、节点与其1跳邻居节点的距离之和 （Pv）、节点已消耗的电池能量 （Cv）、节点的类型 （Tv）、节点的移动性 （Mv）等6个参数。假设由各参数的取值构成的评估决策表见表1。

表1 评估决策

表1中，条件属性中的样本值是根据对该参数的实际测量值进行分级量化后的结果；评估等级值 “1，2，3”的含义分别为簇头选择参数使分簇结构的合理性强、使分簇结构的合理性一般、使分簇结构不合理。

（2）计算决策属性D 的条件属性集C 正域posC（D）和D 的 ｛C－cj｝正域pos｛C－cj｝（D），其中 ｛C－cj｝为属性集C 减去属性cj后的子集。根据表1中的数据，计算得

（3）计算决策属性D 对条件属性集C 的依赖度γC（D）和D 对 ｛C－cj｝的依赖度γ｛C－cj｝（D）

（4）计算条件属性cj关于决策属性D 的重要性σCD（cj）。条件属性子集C′C 关于D 的重要性被定义为

于是，可得各属性的重要性为

（5）计算各属性重要性的归一化权重wj

将式 （8）代入式 （9），可得权重集W 为

可见，决策表中的不同属性 （簇头选择参数）具有不同的重要性 （权重）。若权重为0，则说明该参数存在与否都不会影响评估的结果，此参数在本次评估中被定为冗余参数。对应表1的数据，本次评估中的簇头选择有效参数及其权重分配为：节点度与理想节点度之差 （Dv）权重为3／8，节点的相对簇稳定性 （Sv）权重为1／4，节点已消耗的电池能量 （Cv）权重为1／4，节点的类型 （Tv）权重为1／8。

（6）计算节点v的组合权重Wv

在邻居节点中选择具有最小Wv值的节点作为簇头，其一跳邻居节点成为该簇的成员并不再参与分簇。若当具有最小Wv值的节点数目大于或等于两个时，从节约节点发射功率的角度出发，则选择剩余能量最多的节点成为簇头。之后，簇头节点发送 “Hello”消息，收到此信息的节点成为簇成员节点，至此，簇头选择和分簇过程结束。

2 分簇路由算法与仿真

在GSM－R应急自组网系统中，采用分簇路由算法能够减少节点移动对算法的影响，降低路由维护开销以及路由洪泛的范围，加快路由查找过程。另外在分簇结构中，簇成员只需维护到簇内其它节点的路由信息，而到簇间的路由则借助簇头和网关的转发完成，这不仅减少了参与路由查找的节点数目，而且能够降低路由通信开销，具有很好的可扩展性。

2.1 分簇路由算法

基于上述分簇过程可知：簇内节点具有相似的移动性，并且簇的大小充分考虑了GSM－R应急网络中的节点数目以及节点的计算处理能力，因此在簇内适合采用主动路由算法。它为每个节点保存了一张到簇内其它节点的本地路由表，并周期性地向其邻居进行广播以实时更新。这样，簇内节点间的路由不用花费时间去进行路由查找，有效地减少了GSM－R应急网络中地面节点之间以及车内节点之间的通信时延。

在每个簇内，每个节点仅知道到其一跳范围内的邻居节点的路由信息，为了得到该节点到簇内所有节点的本地路由表，同时避免洪泛方式耗费大量的簇内路由查找时延，在此定义一种簇内路由请求数据包RREQ，其格式见表2［10］。

表2 RREQ 格式

经过一段时间的RREQ 包交互，簇内每个节点都会形成一张到簇内其它节点的本地路由表，并且该路由表还包含到相邻簇的网关／分布式网关的路由。

由于GSM－R应急通信节点的随机移动性，特别是位于高速行驶的列车内的节点，其相对于地面上的节点具有较高的移动速度，车地间的网络拓扑频繁变化，因此簇间路由算法宜采用按需路由算法［11］，以减少车地间拓扑改变对路由算法的影响，降低簇间路由建立和维护的通信开销。簇间路由算法通过将路由请求数据包RREQ 发送到网关／相邻簇的分布式网关，以搜索相邻簇的簇内路由，相邻簇再搜索到其相邻簇的簇内路由，依次进行下去，直至找到目的节点。该路由算法能够发现多条路由，对于路由的选择，它综合考虑了路径中节点的剩余能量、簇头的数目以及总跳数，并为各因素分配一定的权值，选择路径中权重最小的作为最佳路由，其余作为备用路由。

路由算法的仿真性能指标包括：平均端到端时延和网络平均吞吐量。需要指出的是，为了方便与GSM－R 平均吞吐量指标进行对比，网络平均吞吐量TH 的单位取为Byte／h。计算式如下

其中，NR为目的节点在时间T 内接收到的数据分组数目。

2.2 仿真分析

以青藏线上格尔木站－南山口站区间这一铁路实际运行环境为模型，利用NS2仿真工具搭建铁路应急通信网络仿真平台，对平均端到端时延和网络平均吞吐量性能进行仿真。仿真参数包括：网络环境参数、GSM－R 节点相关参数、负载参数以及算法参数，主要仿真参数见表3。

表3 相关仿真参数值

仿真实验分为两组，第一组设置节点最大移动速度为3m／s，考察在应急场景1中各项性能指标随参与应急通信的节点数目的变化情况；第二组设置网络中的节点数目为50个，考察在应急场景2中节点最大移动速度的不同对各项性能指标的影响情况。

（1）平均端到端时延

在GSM－R网络中，列车调度命令采用电路方式传输，电路数据的传输性能会直接影响到列车运行的安全。因此语音业务的平均端到端时延指标值要求为0.4～0.5s［12］。GSM－R分组域数据业务的时延等级共分为4级，根据铁路现行规定，要求调度数据信息无线传送业务的时延等级小于或等于2级。在进行端到端数据传输时，产生的时延有两种：一种是平均时延，另一种是95%的数据分组被传送的最大时延。本文主要对比的是平均时延。

平均端到端时延与应急网络中的节点数目以及节点最大移动速度的关系曲线分别如图1 （a）和图1 （b）所示。

图1 端到端时延性能

由图1 （a）可以看出，当应急网络中的节点具有较低的移动性时，无论节点数目如何变化，提出的应急分簇路由算法EBCR （emergency－based clustering routing）的平均端到端时延均维持在0.5s以下，符合GSM－R 网络语音业务的时延指标和数据业务的时延指标要求。而当网络中的节点数为60个时，时延值最低，为0.251s。

由图1 （b）可以看出，当节点移动速度增加时，时延随之增大。这是因为，节点高速运动引起了无线链路通信的频繁中断而使端到端时延增加。当节点移动速度小于50m／s时，平均端到端时延小于0.5s，符合GSM－R网络语音业务的时延指标要求。而随着节点移动速度的增加，时延值不再符合语音业务的时延指标要求，但符合GSM－R 数据业务的时延指标要求。

（2）平均吞吐量

吞吐量用来表示单位时间内在一个连接上传递的最大字节数。平均吞吐量是用户在较长时间内得到的数据传输速率，以Byte／h 为单位来衡量。GSM－R 分组域数据业务的平均吞吐量级别主要受到无线资源的限制，同时也受到移动台的无线接入能力的影响。

图2 （a）和图2 （b）分别为网络平均吞吐量随参与应急通信的节点数目以及节点最大移动速度的变化曲线。

图2 平均吞吐量性能

图2 （a）表明，随着节点数目的增加，网络吞吐量也呈增长趋势。值得注意的是，当节点数目足够多 （大于80个）时，吞吐量的增长将趋于平缓或基本维持不变。无论节点数目如何变化，EBCR 算法的平均吞吐量性能均可达到GSM－R数据业务平均吞吐量级别的12级，可提供较高的网络吞吐量。

由图2 （b）可以看出，节点的高速移动会使无线通信链路的中断概率增大，网络的平均吞吐量下降，但基本能维持在12级以上，满足目前铁路数据业务吞吐量多为10级的要求。

3 结束语

本文提出了一种用于铁路应急通信网络的分簇路由算法，以解决GSM－R故障小区内的节点间通信问题，该算法同时兼顾了GSM－R 网络的特点和铁路通信服务质量（quality of service，QoS）指标要求。仿真分析结果表明，当列车高速经过故障小区时，若列车速度不超过50m／s（180km／h）时，所提算法的时延性能满足铁路语音业务和数据业务的指标要求，可用于在列车运行中断的GSM－R 应急场景中传送调度语音和调度数据；当列车速度在50m／s（180km／h）和80m／s（288km／h）之间时，该算法适用于一些非关键性调度数据的传输；而当列车速度超过80m／s（288km／h）时，所提算法不再适用于GSM－R 铁路应急通信。综上可知，当列车或移动节点的速度低于60m／s （约220km／h），该算法的平均端到端时延和平均吞吐量性能指标均达到了铁路移动通信系统GSM－R的服务质量要求。

下一步工作将研究如何在分簇路由算法的指标权重分配合理性和算法复杂度方面取得良好的折中，以较好地适应铁路应急通信场景的动态变化特性。

［1］TIAN Shang，SHEN Yaoxing.Railway emergency communications［M］.Beijing：China Railway Publishing House，2008（in Chinese）. ［田裳，沈尧星.铁路应急通信 ［M］.北京：中国铁道出版社，2008.］

［2］ZHONG Zhangdui，AI Bo，LIU Qiuyan，et al.Application theory of GSM－R ［M］.Beijing：Tsinghua University Press，Beijing Jiaotong University Press，2009 （in Chinese）. ［钟章队，艾渤，刘秋妍，等.铁路数字移动通信系统 （GSM－R）应用基础理论 ［M］.北京：清华大学出版社，北京交通大学出版社，2009.］

［3］LI Cuiran，ZHONG Zhangdui，XIE Jianli，et al.Analysis of multicast routing algorithm for railway emergency communication network ［J］.China Railway Science，2012，33 （4）：83－90 （in Chinese）. ［李翠然，钟章队，谢健骊，等.铁路应急通信网络组呼的组播路由算法分析 ［J］.中国铁道科学，2012，33 （4）：83－90.］

［4］GSM－R Functional Group.UIC project EIRENE functional requirements specification V7 ［S］.2006.

［5］GSM－R Operators Group.UIC Project EIRENE system requirements specification V15 ［S］.2006.

［6］Hussein A H，Abu Salem A O，Yousef S A.Flexible weighted clustering algorithm based on battery power for mobile Ad hoc networks［C］／／IEEE International Symposium on Industrial Electronics，2008：2102－2107.

［7］Bouabdallah N，Langar R，Boutaba R.Design and analysis of mobility－aware clustering algorithms for wireless mesh networks［J］.IEEE／ACM Transactions on Networking，2010，18（6）：1677－1690.

［8］XIE Jianli，LI Cuiran，MA Qiaona.A clustering algorithm for GSM－R emergency network ［J］.Journal of the China Railway Society，2011，33 （12）：51－55 （in Chinese）.［谢健骊，李翠然，马巧娜.一种适用于GSM－R 应急网络的分簇算法 ［J］.铁道学报，2011，33 （12）：51－55.］

［9］Bradonjic M，Lazos L.Graph－based criteria for spectrum－aware clustering in cognitive radio networks［J］.Journal of Ad Hoc Networks，2012，10 （1）：75－94.

［10］TAO Cheng.Research on multi－hop clustering protocol for Ad hoc network ［D］.Nanjing：Nanjing University of Aeronautics and Astronautics，2009 （in Chinese）.［陶成.基于多跳分簇的Ad Hoc网络路由协议研究 ［D］.南京：南京航空航天大学，2009.］

［11］SUN Huitao.Study on clustering algorithms in Ad hoc network ［D］.Jilin：Jilin University，2010 （in Chinese）. ［孙慧涛.无线Ad Hoc网络中分簇路由算法的研究 ［D］.长春：吉林大学，2010.］

［12］ZHONG Zhangdui，WU Hao，LI Cuiran，et al.GSM－R wireless network planning and optimization ［M］.Beijing：Tsinghua University Press，Beijing Jiaotong University Press，2012 （in Chinese）.［钟章队，吴昊，李翠然，等.铁路数字移动通信系统 （GSM－R）无线网络规划与优化 ［M］，北京：清华大学出版社，北京交通大学出版社，2012.］