一种适用于ISA100.11a 工业无线网络的路由算法

谢昊飞，黄荣科，陈良平

(重庆邮电大学工业物联网与网络化控制教育部重点实验室，重庆 400065)

0 引言

无线传感器网络［1－2］是由大量部署在特定区域具有无线通信能力的微型传感器以自组织和多跳的方式构成的智能网络系统。其意义在于能够协作地感知、采集、处理和传输网络覆盖区域内被感知对象的信息。目前，无线传感器网络广泛应用于智能交通、环境监测、军事安全、智能家居、现代农业、医疗健康、航天航空等众多领域。

ISA100.11a［3－4］标准是由 ISA100 协会定义，旨在工业无线传感网标准，为目前工业无线领域国际三大标准之一。长期以来，无线传感器网络路由［5－7］机制的研究一直是一项热门。大多选择终端设备到网关之间跳数最短的路径来传输数据，但是，在工业无线应用环境中，跳数最短的路径并不能保证数据的可靠传输，而且如果频繁使用同一条路径传输，就会造成该路径上节点能量消耗过快而过早失效，从而使整个网络被分割成互不相连的孤立部分，缩短了整个网路的生存期［8］。文献［9］提出了一种基于时隙查询与缓冲队列的通信调度方法。文献［10］提出了一种基于确定性调度与链路质量的前k优路径路由算法。但都没有考虑无线传感器网络中能量局限性的问题。

本文选取网络的链路质量和设备剩余能量为指标，基于改进的 Floyd［11］算法，提出了 ISA－Floyd 路由算法，为ISA100.11a工业无线网络提供了一种良好的路由解决方案。

1 ISA100.11a拓扑结构

遵循 ISA100.11a标准，ISA100.11a工业无线网络包括ISA100.11a DL子网和ISA100.11a骨干网。研究的主要对象为ISA100.11a DL子网，不做特别说明，本文的ISA100.11a网络指的是ISA100.11a DL子网。ISA100.11a网络拓扑结构可以分为星形网、树形网和Mesh网。

ISA100.11a网络中的设备包括系统管理器、安全管理器、网关、路由和终端设备。在ISA100.11a网络的设备中，路由设备具有转发功能，终端设备没有转发功能。终端设备一般携带相关传感器，能收集到感兴趣的信息。这些信息通过路由设备最终上传到网关。网关能够对这些数据进行相应的处理，执行相关动作。

2 ISA100.11a通信配置

ISA100.11a网络采用时分多址(time division multiple access，TDMA)机制，数据链路(data link，DL)子网中所有设备之间的数据通信都基于超帧结构，系统管理器为设备分配相应的时隙和通信链路等通信资源。设备获得系统管理器配置的通信资源后，就可以准确、可靠和实时地传输用户应用数据。

时隙表示一段时间;超帧指时隙的集合，是一个循环的时隙表;链路指时隙的使用，即描述在一个超帧循环时间表中重复发生特定的活动。每个超帧周期中的时隙数目决定了该超帧周期的重复频率。图1显示在一个拥有3个时隙的超帧中设备的通信情况。

图1中，超帧循环在每个超帧周期的第1个时隙，设备A发送信息给设备B;在每个周期的第2个时隙，设备B发送信息给设备C;每个周期的第3个时隙是空闲的(未分配)。每3个时隙，重复循环。系统管理器在一组彼此通信设备间配置匹配的链路。在超帧的第1个时隙，系统管理器在设备A上配置一条链路去发送信息给设备B;在同一时隙，给设备B配置一条链路去侦听信息。在超帧的第2个时隙，系统管理器在设备B上配置一条链路去发送信息给设备C;在同一时隙，给设备C配置一条链路去侦听信息。系统管理器配置网络中设备的时隙和链路进行相互配合操作，使得系统稳定运行。

图1 超帧、链路、路由关系Fig.1 Relationship of superframe，link and route

超帧和链路作为单独的但相关的可配置实体，实际上它们是相互依赖、相互对应、相互配合的。图1说明了这种对应关系和相互结构，解释了超帧、链路和路由的区别与联系。

图1中，时隙0和时隙1对应下的2条相关链路就形成了设备A到设备C的路由，路由是本文主要研究的对象。链路的配置依赖于路由算法，良好的路由算法能使链路高效可靠地传输数据。

ISA100.11a系统通信配置主要包括ISA100.11a设备的超帧、时隙、模板等。系统管理器通过合约服务来进行这些通信配置。合约是ISA100.11a系统管理器与设备之间达成的一致协定，用来建立和支持ISA100.11a设备之间的通信路径以满足应用进程的通信需求。设备的应用进程需要同另一个设备的应用进程通信时，这个设备应该首先向系统管理器申请特定的合约。系统管理器通过建立、维护、修改和终止合约来执行网络中设备之间交互操作。

3 路由设计

ISA100.11a网络中，未加入ISA100.11a网络的设备通过已经入网的代理设备加入网络，其路由是依赖于已加入网络的代理设备，所以，ISA100.11a网络中的路由算法着重在设备入网后系统管理器分配的链路情况上。

3.1 选路依据

链路质量。在ISA100.11a网络中，链路质量一定意义上决定了数据传输的可靠性，链路质量的好坏往往与重传次数、网络的流量控制息息相关。

ISA100.11a设备扫描邻居设备收集链路质量。当设备收到数据帧和确认帧时，记录下该数据对应的接收信号强度指示(received signal strength indication，RSSI)和相关值循环冗余校验码(cyclic redundancy check，CRC)，设备解析数据帧时取出尾部相关值，计算出链路质量 (link quality indicator，LQI)值，并存入设备的邻居表中。设备周期上传邻居表给系统管理器，系统管理器收到设备与其邻居设备的链路质量LQI值，存储在相关表项中，作为路由选择时的依据。

剩余能量。ISA100.11a网络中的节点使用电池供电，能量有限。如果某条路径上的节点频繁、超负荷的工作而使能量过低时，整条路径都会失效。当网络中有多条路径失效后，剩余节点会变成孤立节点，网络结构遭到破坏，引起网络失衡，降低了网络寿命。此外，当节点的剩余能量偏低时，传播的数据包将变得不可靠。网络中节点能量合理使用能增加网络的公平性，延长网络的生存周期。

ISA100.11a网络设备往往都是电池供电，网络中的各个设备有不同级别的可用能量。ISA100.11a标准定义了 dlmo.EnergyDesign，dlmo.EnergyLeft属性。dlmo.EnergyDesign表明了设备设计的能量容量，此属性固定地贯穿设备的整个生命周期。dlmo.EnergyLeft属性是一个动态的只读属性，可以用来报告设备的剩余能量容量。在启动时通过dlmo.DeviceCapability dlmo.EnergyLeft报告，也可以通过健康报告HRCO定期报告给系统管理器。

3.2 数值处理

设备参数的 LQI值和 EnergyLeft，EnergyDesign最后都上传到系统管理器。系统管理器首先对这些值做如下处理。

链路质量处理结果为

3.3 路由选择

ISA100.11a系统管理器时刻维持最新的网络链路质量情况和网络中节点剩余能量信息。系统管理器以链路质量处理结果LQIRate为权值，形成整个网络的链路质量邻接矩阵，建立链路质量加权图。

ISA100.11a网络拓扑结构如图2所示。2节点之间的权值表示其之间的链路质量。对于加权图G=(V，E，W);V={v1，v2，v3，…，vn}代表网络中的节点;E={e1，e2，e3，…，ek}表示网络中节点之间的链路。W(vi，vj)表示2节点之间该链路上的链路质量权值。ISA100.11a网络中2节点之间有2条方向相反的链路，一般认为这2条链路的链路质量相等。

图2 拓扑结构图Fig.2 Topology structuremap

图2中，网络中共有9个设备，因此，可以用9×9的邻接矩阵表示，2节点不连接的链路设定其权值为0，节点本身之间权值为无穷大∞，其邻接矩阵为

借助Floyd算法的思想，本文在文献［11］基础上，提出了在如矩阵H所示的带有链路质量权值的邻接矩阵中寻找2节点之间最优路径的方法。不同于文献［11］中求取2节点之间权值的最小值，对于ISA100.11a网络中的节点u和 v，需要寻找到2节点之间链路权值的最大值。判断是否存在一个节点w使得从u到w再到v的链路质量权值比已知的权值更大，这里的判断依据是将uw，wv这2个权值乘积再开方与uv权值做大小的比较，如果是，就更新它。在这之前先要做一些文献［11］中未考虑完备的预处理:首先，判断要插入的节点不能是节点u和v，如果是，则跳到下一个节点;其次，判断要插入节点到节点u和节点v之间是否可到达，即判断插入节点到节点u和节点v之间的距离是否为0，如果为0，则跳到下一节点;最后，判断要插入节点分别到节点和节点v的距离是否小于节点u，v之间的距离，如果都小于，则考虑下一节点。

具体实现方法如下:

上面方法实现了在带有链路质量权值的邻接矩阵寻找最优路径的方法。ISA－Floyd路由算法对于能量的考虑是将剩余能量做分级处理，这样能有效地平均网络能量消耗，从而延长网络生命周期。由于设备没有路由的转发功能，所以，路由和设备用一个Bool标志位IsRouter来区别。路由和设备在选路的时候区别处理。ISA－Floyd路由算法的具体实现流程如图3所示。

首先，设定能量等级为最高级等级1，在以链路质量为权值的邻接矩阵中，当存在节点能量低于该等级时，将该节点及其相对应的邻接关系从邻接矩阵中删除。运算Floyd改进算法，找到最优路径。如果没有找到合适的路径，则将能量等级降低一级后，再重新按照链路质量权值选择路径，直至能量等级降到最低等级。

4 路由算法测试

本文的测试方法是搭建ISA100.11a工业无线网络测试平台。分别在系统管理器中使用 ISAFloyd路由算法和 ISA－k 优路径路由算法［10］以及ISA－时隙调度方法［9］3种路由方法，其他条件一定的3次测试，对比3次结果中的网络剩余能量、数据分组投递率、数据传输平均时延。

图3 路由算法流程图Fig.3 Flow chart of routing algorithm

本文搭建的测试系统由1个网关，6个路由器，10个终端设备和1台电脑组成。更多终端节点可以根据测试需要添加。本测试系统将系统管理器集成到网关，本测试系统的路由算法也即是在网关上实现。本测试系统的终端设备包括智能电表、二氧化硫传感器、烟雾传感器、阀门定位器、一氧化碳传感器、甲烷传感器、温湿度传感器、粉尘传感器、压力变送器。终端设备每隔200 ms向网关传输一次现场数据，网关每隔200 ms就向设备传输一次控制数据，路由器负责转发数据。在测试系统中，时隙长度为10 ms，超帧长度设定为20。

网络剩余能量是网络生存的关键因数，较小的能量消耗是衡量路由算法的重要指标，图4是ISAFloyd和ISA－k优路径以及ISA－时隙调度方法3种路由方法的网络剩余能量曲线图。从图4可以看出，ISA－Floyd将能量分等级处理，在任意时刻网络剩余能量多于ISA－k优路径和ISA－时隙调度方法，在整体上延长了网络的生命时间。随着时间的推移，网络剩余能量呈锐减趋势。这是由于在网络生存的后期，随着节点剩余能量减少，寻找路径变得困难，传输的可靠性降低，重传次数增多，能量消耗过快。可以看出，ISA－Floyd路由算法明显延长了网络的生存时间。

图4 网络剩余能量曲线图Fig.4 Curve graph of network residual energy

图5是 ISA－Floyd 和 ISA－k 优路径以及 ISA－时隙调度方法3种路由方法的数据分组投递率曲线图。数据分组投递率(packet delivery ratio，PDR)是一定时间内正确接收的报文数量与发送报文总量的比值，反映了网络传输的可靠性。ISA－Floyd路由算法和ISA－k优路径算法都是基于链路质量考虑，这2种算法的分组投递率明显优于ISA－时隙调度方法。ISA－Floyd路由算法考虑链路质量，能有效地提高数据传输可靠性。

图6是 ISA－Floyd 和 ISA－k 优路径以及 ISA－时隙调度方法3种路由方法数据传输平均时延曲线图。ISA－k优路径算法基于时隙偏移的考虑，数据传输延时较小好。对于无线传感器网络中的路由协议，端到端平均时延越低越好。ISA－Floyd路由协议数据传输延时处在50ms内，对网络的影响在可控范围内，能够满足应用要求。

5 结束语

本文设计了一种适用于ISA100.11a工业无线网络的路由算法ISA－Floyd，并搭建测试系统，与传统路由算法进行了比较，测试结果验证了该算法的可行性和优势。ISA100.11a系统管理器能量、资源充分、处理速度快，将 ISA－Floyd算法应用在ISA100.11a系统管理器中，能够得到很好的支持。本文中能量的处理可能有其他更好的方式，路由的效率需要更进一步的改进提高。

图5 数据分组投递率曲线图Fig.5 Curve graph of packet delivery ratio

［1］王平.测量与控制用无线通信技术［M］.北京:电子工业出版社，2008:229－224.

WANG Ping.Measurement and control in wireless communication technologies［M］.Beijing:Electronic Industry Press，2008:229－224.

［2］孙利民，李建中，陈渝，等.无线传感器网络［M］.北京:清华大学出版社，2005:109－132.

SUN Liming，LI Jianzhong，CHENG Yu，et al.Wireless Sensor Network［M］.Beijing:Tsinghua University Press，2005:109－132.

［3］ISA Std.100.11a.Wireless Systems for Industrial Automation:Process Control and Related Applications［S］.U－nited States of America:［s.n.］，2009.

［4］王平，王泉，王恒，等.工业无线技术ISA100.11a的现状与发展［J］. 中国仪器仪表，2009(10):59－63.

WANG Ping，WANG Quan，WANG Heng，et al.Overview and Analysis of the IndustrialWireless Technology ISA100.11a［J］.Chinese instrument，2009(10):59－63.

［5］KEMAL Akkaya，MOHAMED Younis.A survey on routing protocols for wireless sensor networks［J］.Ad Hoc Networks，2005，3(3):325－349.

［6］HONG Li，HUANG Tingpei，ZHOU Weixia，et al.Research of AODV routing protocol based on link availability prediction［J］.Journal on Communications，2008，29(7):118－123.

［7］ALKARAKI JN，KAMAL A E.Routing Techniques in－Wireless Sensor Networks:A Survey［J］.IEEEWireless Communications，2004，11(6):6－28.

［8］王良民，廖闻剑.无线传感器网络可生存理论与技术研究［M］.北京:人民邮电出版社.2011:1－7.

WANG Liangmin，LIAO Wenjian.Survival Theory and Technology Research in Wireless Sensor Network［M］.Beijing:People’s Posts and Telecommunications Press.2011:1－7.

［9］王平，刘其琛，王恒，等.一种适用于ISAl00.11a工业无线网络的通信调度方法［J］.仪器仪表学报，2011，32(5):1189－1195.

WANG Ping，LIU Qichen，WANG Heng，et al.A communication schedule mechanism for ISAl00.11 aIndustrial wireless network［J］.Chinese Journal of Scientific Instrument，2011，32(5):1189－1195.

［10］王恒，李敏，刘其琛，等.一种基于确定性调度的工业无线网络路由算法［J］.仪器仪表学报，2011，32(9):1921－1928.

WANG Heng，LIMin，LIU Qichen，et al.Routing algorithm for industrialwireless network based on deterministic scheduling［J］.Chinese Journal of Scientific Instrument，2011，32(9):1921－1928.

［11］张德全，吴果林，刘登峰.最短路问题的Floyd加速算法与优化［J］.计算机工程与应用，2009，45(17):41－43.

ZHANG Dequan，WU Guolin，LIU Dengfeng.Accelerated and optimized method of Floyd algorithm to find out shortest path［J］.Computer Engineering and Applications，2009，45(17):41－43.

(编辑:刘 勇)