基于Dijkstra算法的ISA100.11a路由策略

　　摘要：为了有效利用网络能量，针对工业现场无线网络数据传输可靠性和实时性要求，提出了一种基于Dijkstra算法的ISA100.11a路由策略。以网络能耗、链路质量和端到端平均延时为评价指标，建立复合权值模型，依据Dijkstra算法选择I/O节点到骨干路由器数据传输最优路径。首先与ISA-Floyd路由算法相比较，在同等条件下，ISA100.11a网络生命周期得到延长；然后分析网络能耗、链路质量和端到端平均延时三个评价指标的相互作用关系，并优化其在路由算法中的权重。最终测试结果表明，该算法在延长网络生命周期的同时，有效保障了网络通信的可靠性和确定性。

　　关键词：无线传感网络；ISA100.11a；Dijkstra算法；图路由；复合权值

　　中图分类号：TP393文献标识码：A文章编号：2095-1302（2019）01-00-05

　　0引言

　　随着《中国制造2025》制造强国战略的开展，智能制造关键技术的研发与应用成为热点。智能制造标准体系是智能制造工作的顶层设计和基础保障，明确了智能制造系统的架构组成[1]。无线传感网络位于智能制造系统架构中的互联互通层面，贯穿智能制造系统架构生命周期和系统层级[2]。因此，无线传感网络是智能制造的重要技术支撑。

　　无线传感网络具备高密度特征，在固定区域内包含大量具有无线通信能力的感知节点和路由节点，它们以自组织和多跳方式相互协调实现区域内信息的感知、采集、处理和传输[3]。无线传感网络有效解决了布局布线困难、安装维修费用高等问题，但在工业现场复杂环境下，区域内监控设备密度大，节点信号间相互串扰且受外界干扰较多，使得无线网络资源开销较大，数据通信可靠性和实时性受到影响，使其成为工业无线技术的应用瓶颈[4]。路由技术作为无线传感网络的关键技术，影响整个网络生命周期及其可靠性和实时性，因此提出一种适用于工业现场的路由算法至关重要。

　　ISA100.11a标准作为三大工业无线传感网络标准之一，以用户需求为导向，力求满足工业现场低复杂度、低功耗和合理成本需求，是第一个开放的、面向工业应用的标准[5]。ISA100.11a标准阐明了ISA100.11a网络体系架构、拓扑结构以及所采用的关键技术，但未指定具体路由算法。同时，由于传统路由协议AODV[6]，OSPF[7]，DSR[8]等的运行机制与ISA100.11a网络底层IEEE 802.15.4时分多址（Time Division Multiple Access，TDMA）机制不兼容，因此无法满足确定性调度需求。为此，ISA100.11a网络路由技术成为了研究热点。谢昊飞和李小占等人以链路质量和剩余能量为评价指标寻找一条从感知节点到网关的优化路径[9-10]。T Nhon等人采用流量感知消息调度和竞争窗口尺寸调整算法优化所选路径的链路质量和端到端平均延时[11]。Pham等人以节点剩余能量和端到端平均延时为评价指标，基于整数线性规划算法构建路由算法，结果表明该路由算法在延长网络生命期的同时提高了网络数据通信的实时性[12]。

　　随着工业现场应用复杂化和精细化程度逐渐加深，基于网络数据实现决策和分析的业务应用场景逐渐增强，这便要求网络通信具备良好的可靠性和实时性[13]。为满足如上需求，本文提出了一种基于最短路径Dijkstra算法的ISA100.11a路由策略，以网络能耗、链路质量、端到端平均延时作为路径选择的评价指标，建立复合权值模型，优化工业现场网络通信数据传输路径，在延长网络生命周期的同时，保障网络通信数据的可靠性和实时性。

　　1ISA100.11a概述

　　ISA100.11a网络设备包括系统管理器（System Manager，SM）、网关（Gateway，GW）、中间件（Middleware，MW）骨干路由器（Backbone Router，BBR）、路由节点（Router Device，RD）、I/O节点等。其中，路由资源管理与分配算法运行在SM中。当ISA100.11a网络中存在BBR时，网络可划分为骨干网络和数据链路（Data Link，DL）子网，如图1所示。

　　由于骨干网络多采用以太网或工业现场总线等高速通信特性网络以满足ISA100.11a网络大容量、高带宽、通信实时性的要求，故而不在本文讨论范围内。

　　DL子网内节点依据SM分配链路和操作时隙，采用多跳方式与BBR进行信息交互，通过中间件存取数据库信息，并利用Web系统和数据库组成B/S模型实现人机交互进行工业现场监控[9]。ISA100.11a标准阐明了DL子网内的数据传输主要依赖ISA100.11a标准中的图路由协议。图作为DL子网的有向链路集合，采用八进制字符串索引集合dlmo.Graph管理，包括图ID、优化分支指示、邻居数、数据缓冲队列、最大生命周期、邻居表索引。DL子网内设备可占据多个图且图之间可存在重叠，因此可形成多条到达目的设备的路径。在图1中DL子网内包含虚线和实线两个图，分别具有不同的图ID，I/O节点1#可通过实线或虚线路径上传数据到BBR。

　　具体工作过程如下：

　　（1）I/O节点提取协议数据单元（Protocol Data Unit，PDU）中的契约Contract ID搜索图ID。

　　（2）判断优化分支指示值决定所选邻居后，将缓冲队列中的PDU传递给邻居节点，邻居节点重复上述过程直到PDU到达BBR。

　　本文的重点是依据路径选择的评价指标，借助最短路径Dijkstra算法合理规划DL子网内数据传播路径形成图，优化PDU传播过程。

　　2算法设计

　　对工业现场控制而言，不仅要保证数据传输过程的完整性，还要保证数据传输的实时性；对于工业现场监测而言，则需要维持整体网络及局部节点的长久存活周期。为满足上述需求，本文路由算法以网络能耗、链路质量和端到端平均延时为评价指标，保证网络运行的可靠性、健壮性和实时性。

　　2.1路由评价指标

　　2.1.1网络能耗

　　常用无线链路传输模型根据设备节点之间的距离划分为Friss自由空间模型（d2衰减）和多径衰弱模型（d4衰

　　减）[14]。如果发送节点与接收节点之间的传输距离小于交叉距离d0，则使用自由空间模型，否则使用多径衰弱模型。交叉距离d0计算公式如下：

　　（1）

　　式中：Ds与网络丢包率相关；Hr和Ht分别与发送天线和接收天线的高度有关；b代表电磁波波长。本文中，式（1）中的各参数分别为：Ht=Hr=1.5，Ds=1。由于ISA100.11a基于IEEE802.15.4 2.4 GHz频段，因此b=0.125 m，可得d0=226 m。

　　ISA100.11a网络设备多采用电池供电，有限的能量决定了设备的工作寿命，因此在满足网络工作条件下，尽可能采用Friss自由空间模型传播信息以减少设备能耗。

　　同时，也应考虑节点剩余能量，防止路由节点频繁超负荷工作，导致路由节点剩余能量过低而失效，使网络中的相关链路断开，引发网络失衡，缩短网络生命周期。本文从延长网络生命周期角度出发，设定路由节点能量阈值。节点阈值函数见式（2）：

　　（2）

　　式中：Pj为节点j被选择作为路由节点的概率；Ej为节点剩余能量；为能量阈值系数；N为节点数量。

　　2.1.2链路质量

　　ISA100.11a网络为无线共享网络，在复杂工业现场环境下，网络链路易受噪声、多径衰落和其他信号的影响，导致链路数据受损或丢包。有效评估链路质量是保障网络信息可靠传输的基础。在ISA100.11a网络中链路质量（Link Quality，LQ）多采取硬度量方式度量[15]，其度量参数为链路质量标识（Link Quality Indicator，LQI）、接收信号强度（Received Signal Strength Indication，RSSI）和信噪比（Signal to Noise Ratio，SNR）。通过ISA100.11a网络物理层相关API函数可获取邻居节点的LQI，RSSI值，而SNR值在设备运行环境确定后相对稳定，可通过能量检测API函数获取值推导得出。本文所使用射频芯片的LQI与RSSI值相关[16]，采用文献[17]所述LQ值估计方法，可得：

　　（3）

　　链路质量LQ值记录在邻居表中，周期性上传给SM作为路径选择评价指标，以保障工业数据通信的可靠性。

　　2.1.3端到端平均延时

　　ISA100.11a网络采用集中式管理，以超帧结构和时隙调度原则管控设备节点之间的确定性调度。节点数据发送、接收或空闲操作会在超帧结构所对应操作时隙内完成，而各设备操作均存在时隙偏移，如I/O节点与路由节点通信，路由节点经过多跳与BBR交互，从而产生端到端延时。端到端平均延时是网络I/O节点与BBR通信过程的平均时间。针对具备实时操控需求的工业现场，合理规划超帧结构、设备操作时隙以及数据传输路径是保障工业现场实时性操作的有效

　　措施。

　　2.2复合权值模型

　　将ISA100.11a网络抽象为有向图G（M，N），集合M的

　　元素代表ISA100.11a网络的节点；集合N的元素为ISA100.11a网络相邻节点i与j的边集合，i，j均属于M。综合考虑网络能耗、链路质量和端到端平均延时对通信路径的影响，定义路径W=1→2→3→…→n的复合权值模型如下：

　　（4）

　　式中：cost（W）为网络通信复合权值；A，B，C分别为网络能耗、链路质量和端到端平均延时指标的加权系数，依据网络生命周期、数据通信可靠性和实时性要求设置；

　　Eij_consume为节点i向邻居节点j发送数据过程的能量消耗，

　　Eij_remainder为节点i的邻居节点j的剩余能量；LQij是节点i与j之间的LQ；Td为端到端平均延时；Tth为端到端平均延时阈值，即Td≤Tth。

　　2.3算法描述

　　Dijkstra算法作为典型的最短图路径算法，可用于寻求有向图中从一个点到其他点的最短路径[18]。本文结合复合权值模型和Dijkstra算法搜索ISA100.11a网络中I/O节点到BBR复合权值最小路径。具体步骤如下：

　　（1）SM收集网络中所有节点信息，以BBR为源节点，将BBR信息放入集合S中，网络其余节点信息放入集合V中。首先从集合V中删除剩余能量小于能量阈值的节点，然后计算源节点的邻居节点的复合权值并将最小复合权值放入数组F中，对应邻居节点v1放入集合S中并从集合V中将其删除。此步骤形成第一层到达BBR最小复合权值路径。

　　（2）以集合S中节点v1为源节点重复（1）过程，求出最小复合权值及对应节点v2，在该步骤中对比从BBR经过和不经过v1到达v2节点的复合权值大小，以此决定BBR到达v2的有效最小复合权值。此步骤形成第二层到达BBR最小复合权值路径。

　　（3）重复步骤（2）遍历整个集合V，最终形成BBR到达所有节点的最小复合权值路径。

　　（4）根据ISA100.11a网络超帧结构和链路时隙计算步骤（3）各路径端到端平均延时，确保Td≤Tth，否则抛弃延时最长节点并选取较小延时节点重复上述步骤。

　　（5）在数据频繁转发RD节点处，采取上述步骤重新计算较小复合权值路径作为冗余路径，防止链路断开造成网络严重失衡。

　　（6）网络突发情况可能导致链路断开，如果没有其他链路可供数据传输，则在SM更新网络资源后，在链路断开处按照上述步骤重新计算最小复合权值路径并更新网络拓扑

　　结构。

　　3试验结果与分析

　　本文ISA100.11a网络所采用的I/O节点设备兼具路由和感知功能，空空测试距离为1.5 km，在工厂设备密集区的有效传输距离为1 km，3跳设备网络可覆盖厂内所有区域。图2所示为采用Web监控系统显示在5 400 m2厂房中ISA100.11a网络运行初期的拓扑结构[19]，包括SM，GW，BBR，RD和I/O设备，含有46个I/O设备。经实地试验的近2个月中，ISA100.11a网络无故障稳定运行，可通过自组网功能自动更新网络拓扑结构，并及时反映厂房中各位置的温度、湿度等信息，通过Web系统下发命令控制现场

　　设备。

　　在试验中，设置DL子网通信代价比例系数A，B，C分别为26，11，28，当节点能量无法加入网络时定义为死亡节点。图3所示为节点平均剩余能量、死亡节点与网络运行时间关系曲线，在网络起始阶段，无论采用本文路由算法或文献[9]

　　中的ISA-Floyd路由算法，节点平均剩余能量都随时间逐渐减少。当网络运行到25天左右，节点平均剩余能量急剧减少，主要原因是随着死亡节点数量增多，路由选择困难以及传输可靠性降低，数据包重传概率增大，导致能量消耗增加。但由式（2）可知，本文路由算法对节点能量消耗和剩余能量进行了约束，使得整体网络节点能量消耗相对均衡，限制个别节点能量过快消耗成为死亡节点，从而延长了网络生命

　　周期。

　　包接收率（Packet Receive Rate，PRR）表示正确接收与节点发送报文数量的比值，反映了网络数据传输的可靠性。尽管有损链路无法保证节点之间的连通性，但LQ值越高，节点之间可靠传输的几率就越高。图4所示为在工厂环境下，随着死亡节点的比例增大，PRR逐渐降低，主要原因是死亡节点数量增多加剧了路径选择困难程度，导致LQ值较低链路被选择。

　　端到端平均延时包括传输延迟和等待延时，传输延时主要与跳数相关，而等待延时与节点操作时隙相关。由图4可知，随着死亡节点比例增加，端到端平均延时减小，这是由于中间路由节点转发数据量和频率较大，能量消耗过快，在达到能量限制后节点角色仅作为感知节点，使作为路由节点的数量减少，导致路由平均跳数减少。

　　同时，由图4可以看出，无论增大加权系数B或C值，都会加剧PRR或端到端平均延时随死亡节点比例的降低速度。加权系数的增大，提高了相应评价指标在路由算法中的权重，使其在路径规划过程中得到优化。

　　表1所列为当死亡节点为50%时，加权系数A值为26，设置不同加权系数B，C值条件下的节点平均剩余能量、PRR和端到端平均延时。可以看出，随着B或C的减小，PRR和端到端平均延时得到优化，但节点平均剩余能量却降低。结合式（4）和工业现场无线传感网络性能需求，调节加权系数A，B，C为26，11，28，确定网络能耗、链路质量和端到端平均延时评价指标在路由算法中的权重，使ISA100.11a网络适用于工业现场。上述试验结果和分析表明，本文路由策略可以采用不同加权系数值权衡网络生命周期、包接收率和网络延时等网络性能指标，确保工业现场的无线传感网络可高效运行。

　　表1不同加权系数B，C条件下的节点平均剩余能量、PRR和

　　端到端平均延时

　　C B

　　6 11 16

　　19 （29，97.6，322） （32，97.4，324） （37，97.2，328）

　　28 （27，97.4，320） （30，97.2，323） （34，97.1，326）

　　37 （25，97.3，319） （28，97.0，321） （32，96.8，324）

　　4结语

　　针对工业现场控制和监测需求，既要维持网络节点长久存活，又要维持网络数据通信过程的完整性、可靠性和时效性，本文提出了一种基于Dijkstra算法的ISA100.11a路由策略，以网络能耗、LQ和端到端平均延时作为评价指标，建立了复合权值模型。通过均衡网络消耗延长了网络生命周期并权衡评价指标在路由过程所占权重，提升网络整体性能。该算法在工业现场已经得到应用，为复杂化工业现场监测和精细化管控的无线传感网络路由策略提供了一种有效的解决方案。

　　参考文献

　　[1]李清，唐骞璘，陈耀棠，等.智能制造体系架构、参考模型与标准化框架研究[J].计算机集成制造系统，2018，24（3）：539-549.

　　[2]李俊杰.智能制造体系架构探究[J].卷宗，2017（8）：141-142.

　　[3]鲁力，朱金奇.无线传感器网络中虫洞攻击实时被动式探测[J].软件学报，2016，27（12）：3085-3103.

　　[4]王恒，李敏，刘其琛，等.一种基于确定性调度的工业无线网络路由算法[J].仪器仪表学报，2011，32（9）：1921-1928.

　　[5] RAWAT P，SINGH K D，CHAOUCHI H，et al. Wireless sensor networks： a survey on recent developments and potential synergies[J].The journal of supercomputing，2014，68（1）：1-48.

　　[6] KHAN M K U，RAMESH K S. The performance of wireless sensor network simulators using Advanced On-Demand Vector （AODV） protocol[J].IUP journal of telecommunications，2017，9（4）：40-51.

　　[7] SAINI H，GARG A K.Performance analysis of OSPF routing protocol under single and multiple link failure[C]// International Conference on Recent Developments in Science Engineering and Technology.India：GD Goenka University，2017：450-458.

　　[8] SINGH S，DHALIWAL B S，MALHOTRA R.Impact of node density and mobility on performance of DSR routing protocol in mobile Ad Hoc network[J].International journal of advanced research in computer science，2016，7（1）：8-14.

　　[9]谢昊飞，黄荣科，陈良平.一种适用于ISA100.11a工业无线网络的路由算法[J].重庆邮电大学学报（自然科学版），2014，26（2）：160-164.

　　[10]李小占，李静，刘冬，等.适用于冶金环境下的ISA100.11a路由算法研究[C]// 中国计量协会冶金分会2015年年会.重庆：中国计量协会冶金分会，2015：106-109.

　　[11] NHON T，KIM D S. Real-time message scheduling for ISA100. 11a networks[J].Computer standards & interfaces，2015（37）：73-79.

　　[12] PHAM T L，KIM D S. Routing protocol over lossy links for ISA100.11a industrial wireless networks[J].Springer-Verlag New York，Inc.，2014，20（8）：1-12.

　　[13]钟珂珂，郭具涛，何其昌，等.实时数据驱动的生产线状态监控与效能评估技术研究[J].航空制造技术，2017（7）：51-55.

　　[14]陈友荣，任条娟，刘半藤，等.基于最短路径树的分布式功率控制路由算法[J].传感技术学报，2012，25（8）：1138-1145.

　　[15]翁丽娜，刘轶铭，刘磊，等.无线链路质量评估及预测方法综述

　　[J].中国电子科学研究院学报，2016，11（3）：239-244.

　　[16]黄海辉，李龙连.WSN中一种基于RSSI的移动节点改进定位算法[J].电子技术应用，2015（1）：86-89.

　　[17] BOANO C A，ZUNIGA M，VOIGT T，et al.The triangle metric：fast link quality estimation for mobile wireless sensor networks[C]// International Conference on Computer Communication Networks，Chicago：IEEE J Sel Areas Commun，2010：1-7.

　　[18]向敏，唐亮，王平.基于Dijkstra能量均衡的无线HART图路由算法[J].仪器仪表学报，2016，37（11）：2628-2636.

　　[19]成斐鸣，王鼎衡，刘志刚.基于ISA100.11a的Web监控系统的设计与实现[J].计算机工程与设计，2016，37（8）：2042-2049.

　　琚成，杨会甲，成斐鸣，张建奇

　　（西安航天自动化股份有限公司西北物联网协同创新中心，陕西西安710000）