黄 聪，董利达，管林波

(浙江大学信息与电子工程学系，杭州310027)

随着无线技术、传感技术和通信技术的快速发展，无线传感器网络已然成为焦点。2007年，HCF在其HART的基础上提出无线HART，这是第一个专门面向工业过程自动化的通信协议[1]。无线HART规范采用了TDMA时间同步技术，并提出了Graph路由这种能在复杂多变的通信环境中高可靠传递数据的路由方式，除此之外还应用了用于防干扰的跳频技术，使得其网络的鲁棒性大大高于其他无线网络。

与其他大部分无线网络不同的是，无线HART网络是由网络管理器集中管理控制的，路由和通信资源的维护和配置是由网络管理器负责的。网络管理器为申请加入节点和离开节点建立和回收路由和通信资源，并定期收集网络中所有节点的信息优化拓扑，优化网络。

无线HART规范中采用的是先应式路由协议，包括两种路由方式，Graph图表路由和Source源路由。由于是事先计算好的路由，需要定期进行维护，因此与按所需路由相比，先应式路由协议和中心化调度增大了网络维护的开销。路由开销通常是由路由存储开销和路由维护开销组成，路由存储开销是节点所需的路由表单存储空间，而路由维护开销指的是路由维护时所需要的控制命令数。路由开销是衡量网络性能的一个非常重要的指标，较大的开销将会给网络的运行带来负面影响。

1 背景及相关研究

1．1 无线HART网络

无线HART网络支持Mesh拓扑结构，如图1所示，一个基本的无线HART网络由网络管理器、网关、AP接入点和现场设备[3]组成。网络中主要存在两种数据流，一种是设备节点采集数据发至网关;另一种是网关到设备节点的控制和管理数据流。

图1 WirelessHART网络拓扑结构[2]

无线HART规范中定义的路由协议是一种中心管理控制的先应式路由协议，网络管理器负责收集整个网络的信息然后为每个节点计算路由并分配GraphId，最后为每个节点配置到网络中其他节点的下一跳的Connection信息(节点只存储下一跳信息)，网络节点并不需要自己寻找路由，只需要在发送数据包时查询网络管理器事先配置好的路由信息，然后根据通信资源的情况发给最先可用的下一跳邻居。无线HART规范中采用两种路由方式，Graph路由和Source路由。Graph路由是一种全冗余路由，路由中的每一跳都至少拥有两个下一跳的选择。这种路由方式使得数据包在路由路径中的某节点离开网络也仍能成功发往目的地，大大提高了网络的健壮性，但其复杂性也使得网络维护变得困难，网络维护的代价较高。

无线HART规范中还定义了另一种路由方式:Source路由，这是一种单径路由，它严格指定数据通信途中的每一跳地址，这种路由方式网络节点可以不知道路由，只需要按照数据包中指定的下一跳地址转发即可。

1．2 研究现状

无线传感器路由协议[4－6]的研究已经很多，大部分是基于分布式网络，AODV[4]协议是其中最著名的之一，Zigbee协议规范正是采用这种路由协议。它是按所需路由协议，只有向目的节点发送包时，源节点才在网络中发起路由查找过程，找到相应的路由。当链路断掉，源节点需要重新发起路由查找的过程。

中心管理控制网络由网络中心进行计算、维护和配置路由，对于这种中心管理控制网络路由算法也已经有不少的研究，大部分都是TBR(Tree-Based Routing)算法，即基于树的路由算法。文献[7]提出过多的Intra-mesh流会让中心Root负担过大，为了减轻中心Root的负担提出了RDR算法，其中提到了如何修复路由树。文献[8]中路由算法同样是通过构建路由树的方式，它采用孩子个数作为构建路由树的参数考虑之一。文献[9－10]构建路由树的主要思想是将Graph拓扑先分层，再根据一定的规则选择双亲。这些基于路由树的路由算法得到的路由仅是一条单路径路由，其可靠性低，与Graph路由有一定的差距，并不适合无线HART网络。单径路由可靠性低，一旦其中有个链路断掉则不能通信，多径路由[11]相比于单径路由增加了可靠性，研究者通常通过构造不相交(点不相交或边不相交)的两棵或多棵树[12]来获得两条或多条路径，但是获得的多条路径往往不能够保证所有的路径长度是相等的，即不能获得多条最短路径的路由。

也有少数对无线HART的Graph路由算法的研究，文献[13]将Graph路由和AODV做比较，指出Graph路由在吞吐量和延迟方面具有一定的优势。文献[14]提出的路由算法采用分层Graph的思想，但没有涉及到节点离开及更新机制。文献[15]提出了一种GRAPH路由生成算法ELHFR和路由更新机制，根据拓扑Graph和BFS树来构建子图，其路由更新机制是周期性的重新生成子图，这种方法必然会产生网络的大面积变动。文章还提出了加入过程和离开过程，其加入过程是通过构建临时路由然后再等周期更新来获得正式的路由，这种方法导致节点加入过慢。文献[16]提出一种基于BFS算法得到最短路径Graph路由的方法，引入RSL作为链路质量衡量标准，剔除质量较差的链路和设置每跳的邻居数上限而简化Graph路由，但其同样不支持节点逐个加入，且路由开销大。

无线HART的Graph路由方式可靠性高，维护难，开销大，在保证网络的可靠性的基础上，尽量减少无用的路由路径，降低路由开销，同时也降低了路由对通信资源的需求，对于网络的优化和减负具有重要的意义。本文为了解决无线HART网络中Graph路由的高开销的问题，提出了一种实用的路由策略。

2 路由算法及实现

无线HART网络具有此特点:节点到网关的数据流远远大于网关到节点的数据流，而且节点到网关的服务一般是非ACK服务，即不需要端到端应答和不需要端到端的重发，具有较高的实时性要求，容易造成堵塞;而网关到节点的服务一般是ACK服务，即需要端到端应答，如果未收到应答则会重发;而且点对点之间具有重发和跳频的功能，增加了路由的可靠性。基于这些特点，同时为了减少Graph的存储空间，本文通过构造双树结构，将Graph拓扑简化为两棵树，网关到节点的路由由多路径路由代替，而节点到网关的路由则是全冗余Graph路由。

2．1 网络结构模型

本研究引入双树结构，如图2所示，图2(a)为原始Graph拓扑，图2(b)为转化后的双树拓扑，左边那棵树称为母系树，右边的称为父系树。

图2 双树拓扑结构

本文给予双树一些假定规则:

①同辈(层数即Level相同)之间不允许通信;

②相差两辈或两辈以上的节点之间不允许通信;

③父母亲必须是同辈关系;

④每个节点的总孩子个数具有上限;

⑤每个节点均有父母亲，若父母亲均断则该节点从双树中离开;

⑥树枝断掉后可嫁接修复，并不会破坏断枝中的连接关系;

规则①、②和③保证了节点和网关之间的路由路径长度均是相等的，且是最短路径;规则4使整个网络更加均衡;规则5和6增加了网络的可靠性，即使父母亲有一个断了仍然能够正常通信，而且能够很快的修复双树。另外，网络管理器仅需存储双树即可快速获得每个节点的路由，而不需要存储每个路由，从而减小了网络管理器的路由存储开销，同时也减小了节点的路由表存储开销。

2．2 路由算法

无线HART网络是一种集中管理控制型网络，无论是路由生成、回收还是维护都需要网络管理器进行计算，并下发命令配置给路由路径中的每个节点。本节基于上节所描述的双树拓扑结构提出Graph路由方式的实现算法。本节详细描述对于网络节点加入、离开和链路失败等网络拓扑的改变Graph路由相应的实现算法。

2．2．1 节点加入

当网络生成时就会生成一个到达网关的上行路由(GraphId=0，以下简称路由0)，当节点加入网络时，网络管理器必须更新路由0，并为该节点生成新路由。以下是详细的算法描述。

以图3为例，假设节点7是正申请加入的节点，定时到时时获得了双向邻居 3、4、5、6，其中 3、4、5离网关距离较近且相同，则母系树从左到右搜索，优先选择了母系孩子数最少的节点4作为母亲，同理父系树从右到左搜索，选择了3作为父亲。最终添加到双树中。

图3 双树生长

此算法使得所生成的路由路径最短，从而减小了传输延时;双树父母亲搜索方向的不同使双树之间的关联小，即使其中一棵树断了仍然能够正常通信。而且新加入节点成为树的叶子节点从而不会对网络中其他节点的下行路由造成影响，只需增加加入节点的下行路由以及更新路由0，涉及的节点减少，所需的管理维护配置开销也就减小。

2．2．2 节点链路失败

当节点从双树断开时，形成断枝(由该节点与其子孙构成)，会影响断枝节点的下行路由和路由0，网络管理器必须更新相应路由，回收相关路由路径。算法如下。

此算法由于节点的离开只对树结构下的断枝节点的下行路由以及路由0造成影响，而且由于断枝节点之间并未断开，因此不需要删除它们之间的Connections，所以路由配置开销也相应减少。

2．2．3 节点路由定时更新

网络管理器定期扫描路由树，通过选择继父母来修复路由树。以下是详细的算法描述。

此算法在更新时只对树结构下的断枝节点的下行路由以及路由0造成影响。由于双树是嫁接修复的，在路由回收时，断枝节点之间的Connections并未回收，因此不需要为断枝节点增加新的下行路由Connections。所以路由配置开销也相应减少。

如果节点未离开网络，均可沿着双树路径达到该节点，如果该节点双树中的双路径均不能到达，则网络管理器使用临时的Source路由来修复双树。

图4 Source路由方式修复双树

3 结论与分析

3．1 建立实验环境

实验测试平台为搭建的无线HART基本网络，包括网络管理器、网关、AP和现场设备，均是在CC2430－f128通信模块实现的，其中采用了文献[17－18]提出的同步策略。网络管理器和网关通过有线连接，而网关和AP捆绑在一块。另外网络管理器和网关均与PC机相连，用于监测整个网络的情况以及观测现场设备采集的数据，如图5所示。

图5 无线HART基本网络和监测

选用的拓扑图如图6所示，共16个节点，其中0号节点是网关，其余的均是普通节点。每个节点，都有多个邻居节点以保证冗余度。在生成树之后，相同Level的节点的邻居是相同的，且邻居的通信质量也是相同的，因此是等价的，以便于分析。由于网络的运行，除了路由之外还需要网络管理器进行通信资源的调度，本文采用静态调度方式，超帧长度为100，超帧中为每个Connection分配一个通信资源。图7简单的示意了分配的超帧。

图6 实验拓扑图

3．2 实验测试

3．2．1 成功率

设置干扰源，分别以3%(弱干扰)和10%(强干扰)的概率干扰全网络，然后实测端到端的单向传送成功率。网络中端到端传送均采用无重发模式，而点对点保留重发和跳频功能，重发次数为M次，测试结果见图8。

实验结果显示，本方案的端到端的传送成功率实测值由于自身链路的质量以及程序的影响，较低于理论值，且低于不使用本方案的Graph路由，但相差并不是很大。当全网干扰时，下行双路径路由的成功率比上行Graph路由的成功率略低，但基本相同。这是由于无线HART网络中点对点的重发和跳频机制降低了下行双路径路由的失败率，使得下行双路径路由仍然具有较高的可靠性。而在强干扰的情况下，只要提高重发次数即可保证较高的可靠性。

图7 超帧示意图

图8 端到端传送成功率测试图

设置干扰源，分别以3%(弱干扰)和10%(强干扰)的概率干扰全网络，然后实测端到端的双向通信成功率。一次双向通信成功指的是发送方接收到接收方的应答包。端到端传送采用重发模式，重发次数为N次，而点对点保留重发和跳频功能，重发次数M=2次，测试结果如图9所示。

图9 端到端双向通信成功率测试图

而实验结果显示，本方案的下行端到端的通信成功率在重发的机制下变得相对的可靠，高于无线HART网络对网络通信可靠性的要求(3σ，99．730 020 4%)。而在强干扰的情况下，只要提高端到端的重发次数即可保证较高的可靠性。而无线HART规范中定义的默认重发次数为5。因此本文所提出的路由方案虽然简化了Graph路由，但仍然具有较高的可靠性。

3．2．2 路由存储开销

网络中的节点，既要存储到达网关上行路由表，又要存储所有的需要其作为路由器的下行路由表，当网络规模变大时，存储空间就会变得很紧张。如图10所示，纵坐标Connection开销指的是节点所需存储路由的Connection的个数，从图中可知越靠近网关路由存储开销越大，本方案减小了路由存储的开销，并且越靠近网关节点所需存储Connection的个数增加的幅度减小。另外，网络管理器需要存储整个网络必要的路由信息，使得能够快速获得每个节点的路由。本文策略中仅需存储双树即可表示整个网络的路由信息以及快速获得每个节点的路由，而不需要存储每个路由，从而减小了网络管理器的路由存储开销。

图10 connection开销示意图

3．2．3 路由维护开销

路由维护开销主要来自3部分，分别是节点加入、离开和更新时产生的开销。以下对路由维护开销的评估均分为2部分:影响路由，即Graph的个数和维护路由所需管理命令的个数。其中影响Graph个数在一定程度上体现了网络的拓扑变化对整个网络的影响大小，而维护管理命令个数直接体现了路由维护开销的大小。

①加入过程

分别测试对于不同Level的申请加入节点的加入过程的路由维护开销。如图11所示，本文策略由于加入节点成为树的叶子节点从而不会对网络中其他节点的下行路由造成影响，只需增加节点的下行路由以及更新路由0，因此其影响的Graph个数固定为2。加入节点距离网关越近，它新增加的路由路径短，所涉及的节点少，所需的配置开销也就越少。而未使用本方案的Graph路由则相反，当距离网关越近，所影响的Graph越多，那么所需的配置开销也相应越多。

图11 加入过程路由开销示意图

从图中可知，未使用本方案的Graph路由所下发的管理命令较多，影响范围大，严重影响了网络的效率，加入速度慢。本文提出的方案对于节点加入时所需的路由维护开销较小，影响范围小，并支持单节点逐个加入网络。

②离开过程

图12 离开过程路由开销示意图

分别测试不同Level的申请离开节点的离开过程的路由维护开销。如图12所示，本文策略由于节点的离开只对树结构下的断枝节点的下行路由以及路由0造成影响。而未使用本方案的Graph路由策略，节点离开会对网络中层次大于离开节点的大部分节点造成影响。因此相比之下，本文策略影响的节点个数减少，影响的Graph个数也减少，配置开销也减少。

③更新过程

分别测试对于不同Level的节点路由更新过程的路由维护开销。本测试所采用的情形是删除一条路径并增加一个新的路径。图13中只显示了单个节点的开销情况。测试结果表明，本文策略由于节点路径的删除和增加只对树结构下的断枝节点的下行路由以及路由0造成影响，从而影响的节点个数减少，影响的Graph个数也减少，配置开销也减少。

图13 更新过程路由开销示意图

4 结论

本文针对无线HART网络的特点，提出了一种基于双树结构的路由策略。该方法简化了无线HART协议中提出的Graph路由，得到了较好结果。本文以CC2430通信模块为实验平台进行测试，实测表明:虽然简化了Graph路由，但其可靠性仍然较高，却减小了路由存储和维护的开销，并很好的支持节点逐个加入和离开。此方法提高了网络的效率，为无线HART的路由算法提出了一种实用的方案。

[1]彭瑜．无线HART协议——种真正意义上的工业无线短程网协议的概述和比较[J]．仪器仪表标准化与计量，2007(5):40－46．

[2]The Hart Communication Foundation．HCF_LIT－89．WirelessHART Technical Data Sheet[S]．USA，2007．

[3]The Hart Communication Foundation．HCF_SPEC－285，WirelessHART Device Specification(Revision 1．1)[S]．USA，2008．

[4]Perkins C E．Ad-Hoc on-Demand Distance Vector Routing[C]//Proceedings—2nd IEEE Workshop on Mobile Computing Systems and Applications，USA:IEEE Computer Society，1999．90－100．

[5]马祖长，孙怡宁，梅涛．无线传感器网络综述[J]．通信学报，2004，25(4):114－124．

[6]周贤伟，刘宾，覃伯平．无线传感器网络的路由算法研究[J]．传感技术学报，2006，19(2):463－467．

[7]Lim A O，Wang X，Kado Y．A Hybrid Centralized Routing Protocol for 802．11s WMNs[J]．Mobile Networks and Applications，2008(13):117－131．

[8]Al-Hemyari A，Noordin N K，Ismail A．Centralized Scheduling，Routing Tree in WiMAX Mesh Networks[C]//2008 International Conference on Innovations in Information Technology，USA:Inst of Elec and Elec Eng Computer Society，2008:539－543．

[9]Al-Hemyari A，Ng C K，Noordin N K．Constructing Routing Tree for Centralized Scheduling Using Multi-ChannelSingle Transceiver System in 802．16 Mesh Mode[C]//2008 IEEE International RF and Microwave Conference，USA:IEEE Computer Society，2008．191－195．

[10]Lo S，Ou L．Efficient Algorithms for Routing and Centralized Scheduling for IEEE 802．16 Mesh Networks[C]//International Conference on Scalable Computing and Communications—The 8th International Conference on Embedded Computing，USA:IEEE Computer Society，2009．212－217．

[11]Ramasubramanian S，Krishnamoorthy H，KrunzM．Disjoint Multipath Routing Using Colored Trees[J]．Computer Networks，2007，51(8):2163－2180．

[12]Medard M，Finn S G，Barry R A．Redundant Trees for Preplanned Recovery in Arbitrary Vertex-Redundant or Edge-Redundant Graphs[J]．IEEE-ACM Transactions on Networking，1999，7(5):641－652．

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

[14]Li D，Quan J，Zhang S，et al．An Innovative Routing and Resource Optimization Strategy for WirelessHART[C]//Proceedings of the 2012 International Conference on Technology and Management，Germany:Springer Verlag，2012．353－360．

[15]Zhao J，Liang Z，Zhao Y．ELHFR:A Graph Routing in Industry Wireless Mesh Network[C]//2009 IEEE International Conference on Information and Automation，USA:IEEE Computer Society，2009．106－110．

[16]党魁，沈继忠，董利达．基于RSL筛选的WirelessHART最短路径路由算法[J]．计算机工程与应用，2012，48(6):69－72．

[17]华苗苗，董利达，傅健丰，等．基于闭环调整策略的无线HART时间同步方法[J]．传感技术学报，2012，25(3):391－196．

[18]Hua M，Dong L．A Closed-Loop Adjusting Strategy for WirelessHART Time Synchronization[C]//11th InternationalSymposium on Communications and Information Technologies，USA:IEEE Computer Society，2011．131－135．