适用于WirelessHART网络中实现图路由机制的R－Dijkstra算法

李世兴，王 宏，周桂平

(1.中国科学院沈阳自动化研究所网络化控制系统实验室，辽宁沈阳 110016;2.中国科学院大学，北京 100039;3.国网辽宁省电力有限公司电力科学研究院，辽宁沈阳 110055)

0 引言

微电子技术的发展和无线传感器网络的研究为过程工业无线化奠定了技术基础。工业过程环境复杂，信号采用有线传输的方式有造价成本高、不易于维护，线缆易老化、腐蚀等弊端［1］。在此背景下，2007年9月 WirelessHART标准由 HCF(Hart Communication Foundation)发布，得到了艾默生、西门子等自动化国际巨头的支持［2］。WirelessHART是一种专门为过程控制领域而设计的网络通信协议，其典型的网络应用如图1所示。WirelessHART协议的发布，放宽了传统有线HART总线的使用环境限制，大大增强了工业无线技术的应用潜力。在WirelessHART网络中，路由作为数据的传输和分发机制，是网络的一大核心任务，是不可或缺的。在工业应用现场，网络节点之间无线通信往往受到周围环境电磁干扰、信号衰减、信号反射等不利因素影响，对无线传输的性能带来很大挑战。因此，WirelessHART采用图路由，引入多路径路由机制，增强了数据传输的路径冗余，以确保数据可靠无误的传输。

1 问题描述与研究现状

图1 WirelessHART网络结构

WirelessHART针对应用现场复杂的工作环境和高可靠性的应用需求［3］，采用mesh网络拓扑结构［4］。网络中的节点都可以作为路由节点，都具备发送和接收的功能，能够与一个或者多个节点进行通信。目前，AODV(反应式路由协议)、OLSR(先应式路由协议)等主流的路由算法，大部分是采用的分布式协议，路由的计算选择过程由数据的发送或者转发者来承担，采用网络各个成员来选择路由和维护路由的策略。在一个WirelessHART网络中，网络管理者负责节点路由和通信资源的分配管理［5－6］，通过命令将路由信息发送到网络设备，是一种集中式路由配置方案［7］，而不需要网络其他节点进行路由计算。此外，当前主要路由算法集中在单路径路由的研究，当路由路径上某个节点故障时，通信就要受到影响，也不符合WirelessHART对网络的要求。所以，当前成熟的路由算法不能直接应用于WirelessHART网络当中。

为保证数据传输可靠性，在WirelessHART协议中提出了图路由的路由机制。图路由是一种全冗余的路由机制，路由中的每一跳至少有两个路由选择，属于多径路由［8］，所有的网络设备到目的节点的路径通过网络子图来指定。子图就是连接网络节点的路径上所有节点的集合，由网络管理者创建和管理，并通知给相关网络节点。在一个WirelessHART网络中，每个子图都有一个唯一的图ID号来表示，所有的网络节点都必须预先配置，该ID指出了下一跳可以选择的邻居节点。网络节点对数据进行转发时，通过数据包里面的图ID域，然后查找自己的图路由表，找出可以选择的下一跳的邻居地址，然后将数据通过邻居节点转发出去。在图2的网络拓扑中，节点6要给节点3、节点4或者节点5发送数据，可以使用子图1或者子图2。节点6若要给节点1或节点2发送数据，只能通过子图1。

图2 图路由示例图

虽然WirelessHART给出了图路由的机制，但并未给出图路由的实现算法。国际上Dust、Nivis等公司已经有相关的WirelessHART产品面世，然而这些公司将相关的算法作为公司的核心技术，并没有公开。当前，在图路由方面的研究有少量的成果，其中孙健波等人指出图路由在实时性和网络容量方面比传统的AODV路由算法有明显改善［9］。国外的一些学者提出采用网络节点分层的思想用于实现图路由的分配［6］，这需要额外增加节点的层的信息。党魁等人采用BFS搜索算法生成子图，实现图路由机制，但算法不支持节点逐个加入［10，11］。黄聪提出了双树的策略来实现图路由，涉及到网络拓扑的分解与合成，过程较为繁琐［12］。总体上，该领域可获得的文献很少，还处于研究起步阶段，有广阔的研究空间。因此，目前开展WirelessHART图路由实现算法的研究是很有必要的。

2 R－Dijkstra算法

根据WirelessHART网络构建的过程可以得出，新的节点要加入网络，首先要侦听已经在网设备广播出来的广告包，将侦听到的发出广告包的设备作为自己的邻居，然后向网络管理者发送加入请求，并汇报自己的邻居信息。网络管理者根据要入网节点报告的邻居信息，采用相应的路由算法，生成图路由信息，形成网络拓扑，然后网关通过命令将图ID和参考邻居信息发送给待加入节点。在形成网络拓扑之前，网络管理者采用R－Dijkstra算法来计算路由信息。

2.1 网络模型

假如网络中所有节点用图中的顶点来表示，节点之间的链接用图中顶点的有向边来表示，这样一个WirelessHART网络可以用一个有向图模型G=(V，E)来表达，其中V表示网络中节点的集合，E为有向边集合。网络中每两个节点之间的链接可以赋予权值 w(i，j)，表示由节点i到节点j的链接权值。w(i，j)具体值的计算可以根据链路质量、带宽等多个指标计算获得。为了研究方便，暂且将两节点之间是否直接链接作为w(i，j)取值依据，有链接的邻居之间的权值都为1，否则为无穷大。网络管理者根据节点加入时汇报邻居信息，构建模型图G，然后采用R－Dijkstra算法，得出待加入节点的路由信息。

2.2 R －Dijkstra算法

2.2.1 R －Dijkstra算法简介

Dijkstra算法是由荷兰计算机科学家Edsger Wybe Dijkstra提出的，在图论领域有着广泛的应用，是经典的最短路径算法［13］。Dijkstra算法的输入为一个非负权重的有向图 。在给定出某个发顶点的情况下，该算法能够找出出发顶点到图中其余顶点的最短距离［14］。然而Dijkstra算法得出的结果是最短的距离和路径，只有单一路径，不符合WirelessHART中图路由机制的要求，因此提出了基于Dijkstra算法搜索的冗余路径搜索算法R－Dijkstra算法。它首先根据冗余度参数，对待加入节点汇报的邻居进行选择，然后对将每个选出的邻居作为出发顶点，分别采用Dijkstra算法进行对目的节点搜索，得出每条路径后，最后将待加入节点分别添加到每条路径的起点上，这样就得出了冗余度的图路由路径，这些路径都是待加入节点到目的节点冗余的目标代价最小的路由，目标代价可以考虑传输跳数、信号质量、节点能量以及负载等因素［15－17］，从路由实时性考虑［18］，这里采用跳数作为目标代价。

2.2.2 R －Dijkstra算法描述

在Dijkstra算法中引入冗余度参数r，表示每个节点在路由转发数据时候可选择的邻居个数为r个。在图G中，由上面模型可知，节点之间的链接情况，可以根据权值w(i，j)来确定。

(1)在r个邻居节点中，选择一个未被选择过的节点作为出发顶点S，目的顶点为T，距离数组D用来表示S到其余各节点的传输跳数，路径记录数组为Path，其中D［i］表示S到节点i的最短距离，Path［i］表示S到节点i最短路径需要经过的节点。

(2)在图G中，根据w(i，j)的值，初始化D、Path的值。

(3)从数组D中选择值最小的且未被选择过的顶点X，作为中间节点，其中X1S，X1T。

(4)令Z^IV且Z构S，Z X，则数组D中S到Z的距离值为D［Z］，其中D的值用D［Z］_new来更新，按照以下策略:

如果发生D［Z］值发生变化，则相应的Path［Z］做路径记录，Path［Z］=X，表示S到Z的最短路径需要经过中间节点X，即S到X再到Z。

(5)不断重复(3)、(4)，直到所有D中的顶点都被选择过。这时，所获得的矩阵D中的值就是从S顶点出发到网络中其余各点的最短距离，目的节点为T，找出Path［T］中记录节点，将其输出，然后将Path［T］中的结点作为新的目的节点赋给T，按照该操作方法，依次循环逆向输出Path［T］中记录的节点，直到不能取出新的目的节点T，然后输出起始节点S，最后将上述输出内容反序，该路径就是S到T最短路径。

(6)如果个邻居都已经被选择过，则算法结束，否则返回步骤(1)。

根据以上算法描述，可以将这几个步骤用流程图的形式来表示，算法的流程图如图3所示。

图3 R－Dijkstra算法流程图

2.2.3 R －Dijkstra算法实现

图在计算机中的存储有邻接矩阵、邻接表、十字链表等多种方式。为了图路由操作方便和节省空间，本算法数据结构吸收了邻接表的思想，采用链表的形式来表示网络拓扑和图路由参考邻居。整个拓扑由图节点链表构成，图节点中包含图ID对应的参考邻居信息。其中，参考邻居信息为参考邻居链表的头结点指针。按照WirelessHART协议，图路由数据分为上行数据和下行数据，上行数据的目的地址为网关或网络管理者，其余的为下行数据，所有上行数据采用一个子图，因此上行数据的图ID域相同，规定为0。在路由选择中，每个节点都有该图ID的参考邻居集合。设计的网络节点的数据结构类型如下:

图路由参考邻居的数据结构类型如下:

若网络中有n个节点，则距离数组D、路径记录数组Path设计为n维的数组，如果S到节点i不需要绕行其他节点，则Path［i］置为 NULL。

算法实现过程如下:

2.2.4 算法复杂度分析

由Dijkstra算法的执行过程可以得出，Dijkstra算法的复杂度主要在两个循环中［19］，因此Dijkstra算法的复杂度为O(n2)。RDijkstra算法在Dijkstra算法基础上引入了冗余度参数，以Dijkstra算法为基础，进行了r次循环。因此，R－Dijkstra算法的复杂度为O(r′n2)。在实际应用中r的取值是比较小的，WirelessHART规定r32。由于n相对较大，则r=n，可见该参数对算法复杂度的影响不很严重，对于当前硬件的运算速度是完全可以接受的。

3 算法验证

为了验证算法的效果，选取了一个一般情况下的WirelessHART应用场景，该网络拓扑如图4(a)所示。其中节点1是AP(Access Point)节点，节点2～7为WirelessHART网络已经在网的设备节点，它们要向节点1传输测量数据和状态信息。当某时刻，新的设备节点8要加入网络，在冗余度参数r为2的情况下，选取节点6和节点7为邻居节点，经过R－Dijkstra算法运算，得出两条路径的结果为8→6→4→1，8→7→5→1，如图4(b)所示。R－Dijkstra算法在保证路径冗余的同时，实现了以跳数为指标的路径最优，该算法得出的结果较好的满足了WirelessHART网络的要求。

4 结束语

WirelessHART协议中，提出了图路由的数据传输方式，并-未给出具体的实现方法，这就给广大的研究人员和工程人员提出了研究课题。在本文中描述的R－Dijkstra算法是符合Wire lessHART中规定的图路由机制的一种实现方法。该方法在吸收了Dijkstra算法的思想和方法步骤的基础上，针对图路由的具体特点，满足了路径冗余的要求，完成了WirelessHART网络中的图路由路径分配任务。通过选取典型应用案例，经过RDijkstra算法运算，从实际应用的角度验证了该算法的有效性。

需要说明的是，上文研究以跳数作为路径选择的目标代价，在此基础上开展路由优化目标相关算法研究，使网络更加健壮，是下一步要开展的研究工作。

［1］方原柏.流程行业无线技术应用发展综述.自动化仪表，2013，34(2):1－6.

［2］赵亦兵，吴志盛，庞涛.基于无线HART网络的时钟同步算法研究.自动化与仪器仪表，2010(4):3－5.

［3］陈权，高宏.RSPEED:无线传感器网络中基于不确定延迟的可靠实时路由.通信学报，2013，34(8):110 －119.

［4］LEE M J，ZHANG R，ZHENG J J，et al.IEEE 802.15.5 WPAN mesh standard － low rate part:meshing the wireless sensor networks.IEEE Journal on Selected Areas in Communications，2010，28(7):973 －983.

［5］HONG S，SAHU R P，SRIKANTH M R，et al.Real－ time query scheduling for wireless sensor networks.Proceedings of 17th International Conference on Database Systems for Advanced Applications，U-nited States:Institute of Electrical and Electronics Engineers Inc，2012:224－233.

［6］FANG M J，LI D D，QUAN J G，et al.An innovative routing and resource optimization strategy for wireless HART.Proceedings of 2012 International Conference on Technology and Management，Jeju，Jeju －Island，Korea，Republic of，2012:353 －360.

［7］董利达，黄聪，管林波.基于双树结构的无线HART调度策略.浙江大学学报(工学版)，2014，48(3):391 －397.

［8］RAMASUBURAMANIAN S，KRISHNAMOORTHY H，KRUNZ M.Disjoint multipath routing using colored tree.Computer Networks，2007，51(8):2163 －2180.

［9］孙健波，孙强，申巍，等.对无线HART网络的图表路由算法的研究.铁路计算机应用，2011，20(8):35 －38.

［10］ZHAO J D，LAING Z J，ZHAO Y P.ELHFR:A graph routing in industrial wireless mesh network.Proceedings of 2009 IEEE International Conference on Information and Automation，Zhuhai，Macau，China，2009:106 －110.

［11］党魁，沈继忠，董利达.基于RSL筛选的WirelessHART最短路径路由算法.计算机工程与应用，2012，48(6):69 －72，83.

［12］黄聪，董利达，管林波.一种低开销无线HART路由策略.传感技术学报，2013，26(2):252 －259.

［13］DIJKSTRA E.A note on two problems in connection with graphs.Numerical Mathematic，1959(1):269 －271.

［14］王怡苹，李文海，文天柱.面向信号测试的路径搜索算法研究.仪器仪表学报，2013，34(7):1650 －1658.

［15］ATHANASIOU G，KORAKIS T，ERCETIN O，et al.A Cross－ Layer framework for association control in wireless mesh networks.IEEE Transactions on Mobile Computing，2009，8(1):65 －80.

［16］HOU R H，LUI K S，LI J D.Routing in multi－radio multi－channel multi－ hop wireless mesh networks with bandwidth guarantees.Proceedings of IEEE 73rd Vehicular Technology Conference.Budapest，2011:1－5.

［17］刘铁流，巫咏群.一种新的基于分簇的无线传感器网络多跳节能路由协议.信息与控制，2012，41(1):27 －32.

［18］BANSAL S，JUNEJA D，MUKHERJEE S.An analysis of real time routing protocols for wireless sensor networks.International Journal of Engineering Science and Technology，2011，3(3):1797 －1801.

［19］王杰臣，杨得志，张伟.最短路径问题的一种改进算法.解放军测绘学院学报，1999，16(4):282 －285.