基于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路由策略，以网络能耗、链路质量、端到端平均延时作为路径选择的评价指标，建立复合权值模型，优化工业现场网络通信数据传输路径，在延长网络生命周期的同时，保障网络通信数据的可靠性和实时性。

1 ISA100.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 算法设计

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