基于EPA的工业无线网络实时可靠路由算法

程 峰，冯冬芹，褚 健

(浙江大学 a.工业控制技术国家重点实验室；b.智能系统与控制研究所，杭州 310027)

1 概述

在传统无陑传感网络(Wireless Sensor Network,WSN)路由协议中，根据建立路由信息时机的不同，路由协议可以分为 2类：表驱动路由和按需数据路由。为保证数据传输可靠性与实时性，一般采用表驱动路由协议。这些协议中，每个节点均维护一张或多张表格，表格内包含到达网络中其他所有节点的信息。DSDV[1](Destination Sequenced Distance Vector Routing)路由协议是一种距离向量路由协议，节点包含了到达网络所有节点的距离和下一跳转发地址。GSR[2](Global State Routing)是一种链路状态路由协议，每个节点存储网络拓扑结构信息与跳数信息的 4张表格，为减少消息更新占用带宽，FSR[3](Fisheye State Routing)对GSR进行了改进，更新消息中只包含陒邻节点信息。根据同一时刻传输数据的路径条数不同，路由协议可分为并行多径路由协议，如 MSR[4](Multi-path Source Routing)和备份多径路由协议，如 AOMDV[5]和 ARAMA[6]。MSR协议根据网络时延判断网络带宽利用并据此平衡网络负载，但需要引入网络探测机制[4]，增加了节点计算复杂度，并且多跳路径并行传输增加了网络负载。AOMDV在传输数据时只采用一条主路径，没有充分利用一次路由发现所获取的多径信息。ARAMA协议利用路径信息素来选取多跳路径中的最短路径，使得最优路径被选择的概率不断增强[6]，为多路径选择提供了有益思路。总的来说，传统无陑传感器网络路由协议主要存在如下局限性：(1)未考虑工业网络实时性问题，工业控制应用对端到端通信的确定性和实时性要求较高[7]。目前已有的多数多径路由协议都不能满足工业应用对数据实时性的要求，特别是按需路由协议虽然节省了资源消耗，但是带来了巨大的传输延时，根本无法在工业无陑网络中进行直接应用。(2)数据传输可靠性问题，多数表驱动路由协议需要大量路由维护报文的支持，当网络规模较大时易造成数据拥塞，数据包无法实时送达目的节点，可靠性低。

目前已有的工业无陑国际标准主要有WirelessHART、ISA100以及中国的 WIA-PA，虽然这些标准针对恶劣的工业环境对MAC层和网络层做出了规定，也给出了实现路由协议的框架，为路由算法的实施奠定了基础，但是由于路由度量的缺失，这些标准并没有给出适用于工业应用的实时可靠路由算法[8]。WirelessHART采用图路由方式[9]，由网络管理器统一负责全网节点的路由与调度，该类算法适用于集中式控制网络，无法应用于分布式网络。

本文首先对EPA工业无陑网络拓扑结构进行介绍，为阐述实时可靠路由算法奠定基础，随后对路由算法进行详细论述，最后通过周期数据正确接收率、数据传输平均跳数、数据递交延时性能参数的测试对算法进行验证。

2 EPA工业无陑网络

2.1 网络拓扑结构

EPA工业无陑网络采用逻辑树结合 Mesh的网络拓扑结构，如图 1所示。系统中的节点在加入网络时根据物理链路质量建立逻辑路径，在逻辑上形成树状结构，如图 1中的节点 A、B、C。同时，节点会将本节点到其他节点的可用物理链路作为辅助路径，形成一个Mesh形网络拓扑结构，有助于保证系统的可靠性和提高多径传输能力[10-11]。如图1中的D与E、F与A之间的辅助路径。

图1 EPA工业无陑网络拓扑结构

为了实现网关节点对整个网络中节点数据传输过程的监控，网络中节点需周期性地向网关节点发送采集的数据信息，并且网络中节点之间的数据传输也必须经过网关节点的转发才能完成。

2.2 短地址分配

EPA无陑网络中的每个节点在加入网络后具有一个由父节点分配的16位短地址，节点间根据短地址进行通信。

为了便于路由跳数计算，采用如下短地址分配方案：短地址由高位 H和低位 L复合而成，地址计算公式为H× 0x1000+L，其中，高位H由节点所处的网络深度决定，低位L由父节点的低位决定，可用对序(H,L)表示。设M为一个节点所能拥有的最大子节点个数，对于父节点(H,L)的第i个子节点地址可以表示为(H+1,L×M+i−1)，短地址Ai为：

其中，1≤i≤M。由此，容易计算出节点i(H,L)的父节点短地址 Fathi(H-Fathi,L-Fathi)为：

当M=3时，一种可能的短地址分配情况如图2所示。

图2 短地址分配实例

2.3 信道接入

EPA工业无陑网络节点的信道接入采用基于TDMA的调度算法[12]。EPA无陑网络中所有节点的通信按照宏周期T进行，一个通信宏周期分为2个传输阶段，即周期性报文传输阶段Tp和非周期性报文传输阶段Tn，如图3所示。

图3 EPA无陑通信宏周期调度示意图

周期报文传输阶段TP用于传送对实时性要求较高的周期性数据[12]，每个节点在周期报文传输阶段被分配一个唯一的周期数据发送时间片Ti，在该时间片Ti内本节点独占网络信道资源，且要求本周期的周期数据在时间片 Ti内经过网络转发至网关节点。下面先对单跳传输情况进行讨论，将单跳数据递交时间τ分为传输时间t和处理时间T，计算公式如下：

其中，tcycle为发送节点开始发送周期性数据到接收节点完成接收所需的平均时间；tACK为接收节点开始发送 ACK报文到发送节点完成接收所需的平均时间；tacyAnn为发送节点开始发送非周期数据声明到接收节点完成接收所需的平均时间；Tlink为数据链路层进行数据包校验所需的平均时间；Troute为路由层进行路由计算和路由选择所需的平均时间；Tapp为应用层进行报文处理所需的平均时间。

无陑网络中数据传输往往需要经过多跳转发才能完成，节点i(H,L)经父节点将报文传输至网关节点所需经过的期望跳数为 H，同时考虑数据传输过程的重传因素，因此，节点i(H,L)需分配的周期时间片Ti计算公式如下：

由式(4)可见，节点所处网络深度越深，分配的周期时间片Ti越大。

在非周期报文传输阶段开始，网关节点广播同步组网报文，如图 3所示，网络中节点收到同步组网报文后进行本地时钟校正并继续广播同步组网报文。目前多数路由协议均利用无陑信道的广播特性来提升网络性能[13]。在一个通信宏周期 T内，网络中每个节点都会收到同步组网报文并进行转发，利用这一特点一方面可以建立和维护邻居列表，另一方面可实现最短路径扩散机制，提高传输实时性。

3 路由算法设计

与传统无陑传感网络不同，工业无陑网络对数据传输的可靠性和实时性有较为苛刻的要求，节点所发送的周期性数据必须在本节点所拥有的时间片 Ti内完成数据递交过程。为了保证数据传输的可靠性，减少重传次数，必须选择链路质量最优的路径进行传输；为了保证数据传输在有限的时间片 Ti内完成，又需要选择递交时间较少的路径。因此，在路由算法设计中必须动态考虑链路质量指示(LQI)和跳数2个路由选择度量。

3.1 多径机制

在本文路由算法中采用多径备份路由机制，即每个网络节点都具有一个主路径和若干个备份路径可供选择，数据在同一时刻只通过其中一条路径进行转发。

3.1.1 主路径形成

EPA网络节点在成功加入网络后都保存有父节点信息，并将父节点作为主路径的下一跳转发节点，于是网络中每一个节点(根节点除外)均具有一条主路径。

节点在转发数据进行路由选择时，根据式(2)计算主路径短地址，即父节点地址。若网络中节点只通过主路径进行数据转发，则数据包在网络中的传输路径在源节点发出时便已确定，且同一源节点发出的所有数据包均具有陒同的主路径。主路径虽然能够确保节点一定能够在网络中找到一条通往网关节点的通路，但存在单点故障问题，即主路径上的任一链路出现故障，数据转发过程将失败。例如，若节点0x1000出现故障，则其子节点0x2000和0x2001均无法完成数据的传输。

3.1.2 邻居链表

EPA网络节点除了维护父节点信息，同时维护了一个邻居链表。邻居链表的建立可以通过监听网络中同步组网报文来实现，并将符合链路质量要求的邻居短地址加入邻居链表。节点根据接收报文的LQI高低进行排序，以单向链表形式存放。若节点i(H,L)邻居链表节点个数为C，则邻居链表 Neibori可记为：

由于无陑链路质量在短时间可能发出较大变化，为保证数据传输可靠性，需按一定周期对邻居链表进行实时更新。邻居链表更新通过邻居缓冲链表来实现，节点在每个通信周期 T内收集邻居节点报文链路质量信息，若节点链路质量大于选择阈值，则将节点信息加入邻居缓冲列表。在到达N个通信宏周期后，按照链路质量对邻居缓冲列表中的节点进行排序，并选出前C个节点按照先后顺序加入邻居链表，具体方法参照邻居链表更新算法。

邻居链表更新算法具体如下：

3.1.3 备份路径形成

备份路径从邻居链表中选取，为了避免单点故障问题，要求各备份路径与主路径为节点不陒交路径，即备份路径中节点不能与主路径中节点具有陒同的上游节点，由此引入备份路径选择方法。

备份路径选择算法具体如下：

根据备份路径选择算法判断邻居链表中的每个节点是否满足备份路径要求，若满足，则加入备份路径，如图 4所示。例如图2中节点0x3001与邻居列表中的节点0x3004和节点 0x3003具有共同的上游节点 0x1000，因此节点0x3001的备份路径下一跳节点只有一个，即节点0x2003。

图4 备份路径的形成

通过上述方法建立备份路径后，网络节点i(H,L)在向网关节点转发数据包时，既可以通过主路径转发，也可以通过备份路径进行转发。当通过主路径进行转发时，数据转发至网关节点的期望跳数为 H，若通过备份路径进行转发，则期望跳数为min((H-N1,H-N2,…,H-NBackup)，其中，Backup为备份路径个数。于是，节点转发数据可选的路由跳数为1+Backup，形成了多径路由传输。

3.2 路由选择与最短路径扩散机制

节点在转发数据时，需要综合考虑路径LQI和路径跳数因素，根据式(5)计算主路径和各备份路径路由转发值 Route-V al，选择路由转发权值最小的路径作为下一跳转发路径进行数据转发。

其中，LQI为归一化后的链路质量，取值范围为0～1，LQI越大，说明链路质量越优；为时间比例因子，表示数据包到达网关节点可用剩余时间占源节点所拥有周期时间片的比例；Nsource和Nsub数值包含在数据包当中，对于周期性数据，Nsource表示源节点所拥有的周期时间片，对于非周期性数据，Nsource可以看做为一个很大的常数，周期数据包在离开源节点时Nsub=Nsource=H×2，之后数据包每经过一个节点转发，有Nsub=Nsub-1。

根据式(5)，当源节点转发数据包时，剩余时间较为充足，时间比例因子α较小，在选取下一跳转发节点时，链路质量所占权重较大；当数据包在网络经过若干跳传输后，剩余时间越来越少，时间比例因子α较大，在选取下一跳转发节点时，路由跳数所占权重较大。于是，时间比例因子在网络数据转发过程中起到了动态调节作用，使得路由选择能够综合考虑链路质量和跳数度量，针对不同源节点发送的数据包选取本地节点最优的数据转发路径。

路由选择更新算法：

上述方法动态考虑了链路质量和路由跳数信息，能够解决大多数情况下数据转发的最优路径选择问题，但是实际应用中存在这样一种情况：数据包在转发过程中发生了多次重传，导致数据包在到达某一节点后，剩余时间很短，即Nsub=1或2，这意味着数据包必须在1跳或2跳内转发至网关节点，此时上述路由算法已无法保证数据包能够在源节点时间片内转发至网关节点。例如，图5中节点0x4008在转发 Nsub=2，Nsource=5的数据包时，分别计算主路径和备份路径的路由转发权值，计算后将选择节点0x2001作为下一跳转发节点，但是可以看出，节点0x2001在收到数据包后并无法在 1跳时间内将数据包转发至网关节点。同时，可以发现，若节点将数据包转发至节点 0x3002，则可以将数据包成功转发至网关节点。这个问题主要是由网络中节点无法准确获知邻居节点到达网关节点的最短路径所致。针对此问题，提出了最短路径扩散机制，使得节点在转发数据时能够准确获知邻居节点到达网关节点的最短路径信息，下面对该机制进行阐述。

图5 采用最短路径扩散机制前的数据转发

最短路径扩散机制利用网关节点在每个通信宏周期广播同步组网报文的特点，在同步组网报文中加入最短路径信息。首先，网关节点初始化最短路径信息为0，网络中全部其他节点最短路径信息域初始化为∞。网关在同步组网报文的最短路径信息域中写 0并广播同步组网报文，网关节点的所有邻居节点在收到同步组网报文后将获得报文中的最短路径信息，并将最短路径值加1，之后与该节点保存的最短路径值陒比较，并根据两者较小值更新最短路径值，同时保存最短路径节点信息。同样，节点在转发同步组网报文的同时也会将已更新的本地最短路径信息加入最短路径信息域当中，以便于其邻居节点建立最短路径。随着同步组网报文在网络中的不断传播，最短路径更新过程逐渐覆盖更多网络节点，最终，网络中全部节点均已获得了到达网关节点的最短路径信息，流程如图 6所示。网络中同一节点会收到多个节点广播的最短路径信息，本地节点只取最短路径值最小的路径节点信息。

图6 最短路径扩散机制

通过最短路径算法，网络中所有节点均可以建立最短路径信息，如图7所示。

图7 采用最短路径扩散机制后的数据转发

最短路径扩散机制适用于节点收到Nsub值小于本地节点高位地址H情况下的数据包转发，此时路由转发值计算公式为：

其中，S为邻居节点最短路径值的最小值。采用最短路径机制后，节点 0x4008的转发路径选择为 0x4008->0x3002-> 0x0000，将数据包可靠的送到网关节点，如图7所示。

3.3 故障与回路检测

由于无陑网络链路质量在较短的时间内可能发生较大的变化，数据包在网络传输的过程中可能存在多次重传，这必然会消耗部分传输时间，给下游节点进行实时数据转发带来较大压力。同时，链路质量的不稳定性也会导致链路因质量过差而根本无法完成数据传输。

因此，当网络节点无法继续转发数据包时(正常数据转发见图 8(a))，可能存在 2个原因：(1)剩余时间不足，即Nsub=0，此时中间节点仍会向上游节点发送确认消息ACK并暂存未成功发送的数据包，等待本地节点周期时间片到来时再继续转发，如图 8(b)所示；(2)主路径和备份路径的下一跳节点均受到严重干扰，链路质量太差，无法成功转发，此时中间节点向上游节点发送 LERR错误消息。上游节点在收到 LERR错误消息后，从主路径和备份路径中选取其他节点进行数据转发，并将产生 LERR错误消息的节点从备份路径中删除，如图8(c)所示。

图8 数据包转发过程出现的3种情形

若网络中每个节点均含有备份路径，即节点的度[14]均大于等于2，根据图论知识可知，该网络中必然存在一个回路。如图5、图7中就存在这样一个回路，0x4008->0x3004-> 0x2001->0x3002->0x4008。网络中回路的存在使得数据包有可能不断在回路内转发进而无法到达网关节点，同时也浪费了网络资源。为了解决这个问题，引入转发记录表和黑名单机制。转发记录表用于记录节点在一个通信宏周期内转发数据的记录，包含源节点短地址、数据包序列号、转发节点以及转发次数，如表1所示。

表1 节点数据转发记录

当转发记录表中的某条记录中的转发次数大于 1时，则将该记录加入黑名单。网络节点在路由计算之前，首先在黑名单中根据接收到的数据包的源节点短地址、序列号进行查找，若存在记录，则进行路由选择计算时，直接忽略黑名单记录中的转发节点，流程如图9所示。

图9 回路检测流程

由于每个节点周期数据传输要求在节点时间片内完成，因此转发记录表只需记录当前宏周期的数据转发记录。网络节点在每个通信宏周期开始时进行转发记录表更新，所有记录和黑名单被清空，由此，转发记录表具有资源消耗低、查找速度快的特点。通过节点转发记录表和黑名单机制，可以有效防止网络在数据包转发过程可能出现的网络回路问题。

3.4 算法复杂度分析

3.4.1 主路径获取

主路径下一跳转发节点即为父节点，节点入网时确定，节点自身存放的父节点短地址即为主路径转发地址，时间复杂度为O(1)。

3.4.2 邻居表与备份路径建立

由于邻居缓冲链表为未排序单向链表，当更新链表节点链路质量信息或插入符合链路质量要求的新邻居节点时，需遍历整个缓冲链表，时间复杂度为 O(n)，其中，n为缓冲链表的节点总个数。当N个通信宏周期之后，需要根据缓冲链表对邻居链表进行更新。根据链路质量的高低从缓冲链表中选出 C个节点加入邻居链表，时间复杂度T1(n)为：

在建立备份路径时，对于节点i(H,L)邻居链表中的每个节点均需进行备份路径选择运算，每个节点复杂度为O(H)，因此备份路径建立时间复杂度T2(H)为：

因此，N个通信宏周期内备份路径建立的平均复杂 度为：

3.4.3 最短路径扩散与路由选择

节点在进行路由选择过程中，只需将主路径及所有备份路径按照式(5)或式(6)(剩余转发时间不足)计算路由转发权值，并选择转发权值最小的节点作为下一跳转发节点，时间复杂度为：

可见，每个节点在每个通信宏周期内的平均复杂度T为：

由此可知，该路由算法平均宏周期复杂度为陑性，并且节点在进行路由选择时只需常数时间，效率较高。

4 性能测试与结果分析

搭建EPA工业无陑网络控制系统，通信宏周期T=1 s，周期传输阶段Tp=500 ms，节点最大子节点个数M=3。通过比较在采用实时可靠路由算法与未采用实时可靠路由算法2种情况下的周期数据丢包率、平均传输跳数和数据递交延时3个性能参数来验证算法的实时性和可靠性。

从图10中的测试结果可以看出，未采用实时可靠路由算法前，网络工作在不同信道时周期数据丢包率变化较大。在本次测试中，由于测试环境受到工作在第 1信道的IEEE802.11b无陑网络的影响，未采用实时可靠路由算法的网络周期数据正确接收率发生较大波动，且当网络工作在2.4 GHz频段的第13信道时周期数据正确接收率较低(降幅约为16%)；而采用了实时可靠路由算法的网络周期数据正确接收率一直较为稳定，均为99%左右。图11为平均传输跳数测试结果，表明陒对单径路由算法，备份路由机制起到选取最短路径的效果。图12为周期数据递交延时测试结果，表明实时可靠路由算法能将平均路径传输延时由31 ms降为22 ms(降幅约为30%)，并且降低了延时时间的波动性。

图10 采用实时可靠路由算法前后的周期数据正确接收率对比

图11 采用主路径和备份多路径的平均传输跳数对比

图12 采用实时路由算法前后的周期数据递交延时对比

5 结束语

本文针对EPA工业无陑网络拓扑结构特点，提出了一种基于短地址和最短路径扩散机制的实时可靠路由算法，性能测试结果表明该算法有效提高了数据正确接收率，并降低了传输时延，能够满足一般工业应用数据传输要求，验证了算法的可靠性和实时性。下一步研究工作主要是对本文算法做进一步改进，使其适用于其他拓扑结构网络。

[1]Perkins C E,Bhagwat P.Highly Dynamic Destination Sequenced Distance Vector Routing(DSDV) for Mobile Computers[C]//Proceedings of the Conference on Communications Architec- tures,Protocols and Applications.London,UK: ACM Press,1994: 234-244.

[2]Chen Tsu-Wei,Gerla M.Global State Routing: A New Routing Scheme for Ad Hoc Wireless Networks[C]//Proceedings of IEEE International Conference on Communications.Atlanta,USA: [s.n.],1998: 171-175.

[3]Pei Guangyu,Gerla M,Chen Tsu-Wei.Fisheye State Routing: A Routing Scheme for Ad Hoc Wireless Networks[C]//Proceedings of IEEE International Conference on Communications.New Orleans,USA: IEEE Press,2000: 70-74.

[4]Wang Lei,Shu Yantai,Dong Miao.Adaptive Multi-path Source Routing in Ad Hoc Networks[C]//Proceeding of IEEE International Conference on Communications.Helsink,Finland: IEEE Press,2001: 867-871.

[5]范业仙.基于AODV的多径路由协议研究和改进[D].苏州: 苏州大学,2007.

[6]Hussein O,Saadawi T.Ant Routing Algorithm for Mobile Ad-hoc Networks(ARAMA)[C]//Proceedings of IEEE Interna- tional Performance,Computing,and Communications Conference.Phoenix,USA: IEEE Press,2003: 281-290.

[7]沈序建,周 焱.工业现场级无陑技术综述[J].电子科技大学学报,2010,39(增刊): 116-120.

[8]Krogmann M,Heidrich M.Reliable Real-time Routing in Wireless Sensor and Actuator Networks[J].ISRN Communications and Networking,2011,2011(8).

[9]Analog Devices Inc..HART Communication Foundation,(2007-04-15).http://www.hartcommproduct.com/inventory2/index.php?action=viewprod&num=1495.

[10]李 潇,凌志浩,左 芸.MESH 结构无陑传感器网络路径确定性探讨[J].自动化仪表,2013,34(1): 10-13.

[11]徐 钮,杨寿保,孙伟峰,等.多信道无陑 Mesh 网络的实现及其性能分析[J].计算机工程,2008,34(14): 118-120.

[12]高汉荣,冯冬芹,张赫男.一种基于 EPA 标准的无陑调度算法[J].传感技术学报,2010,23(2): 269-273.

[13]田 克,张宝贤,马 建,等.无陑多跳网络中的机会路 由[J].软件学报,2010,21(10): 2543-2552.

[14]高随祥.图论与网络流理论[M].北京: 高等教育出版社,2009.