WPAN Mesh 网络自适应快速路由修复算法

雷宏江，邓 科，郑 渊，任 智

(重庆邮电大学移动通信技术重庆市重点实验室，重庆 400065)

0 引言

无线个域网(wireless personal area network，WPAN)是一种能使便携式家用电子产品和通信设备以 Ad Hoc 方式组网工作的无线网络［1－2］，WPAN Mesh网络在不增加无线接入点的基础上，利用WMN(wirelessmesh network)网络的组网方式完成了网络连接。在WPAN Mesh网络中，网状网的组网方式不仅增大了网络的覆盖范围，而且还增加了网络的吞吐量，提高了数据传输的可靠性［3－4］。

目前，WPAN Mesh网络的路由协议主要都是基于mesh树路由协议的改进。文献［5］以IEEE802.15.5标准低速WPAN中的网状自适应树(meshed adaptive tree，MAT)为基础，将MAT划分为2层结构，且在划分后的2层结构采用不同的路由算法，提出了分级路由算法。但是，该路由算法由于采用传统的无线自组网按需平面距离矢量路由协议(ad hoc on－demand distance vector routing，AODV)［6］，从而存在由泛洪引起的过多控制开销、消耗大量网络资源等问题。文献［7］中以MAT为基础，将MAT和 AODV 结合，提出了 TLMR(two－level mesh routing)路由算法。即先在MAT中查询有效路径，如果不存在有效路由，则采用AODV。该路由算法同样存在AODV的缺点。文献［8］提出了一种基于树的先验式路由协议，在该协议中路由不是统一在根节点进行计算，而是分散到各个枝干上的节点进行分布式计算，该算法能够有效地避免在根节点处出现拥塞现象，但是该算法仍然会引起过多的控制开销。文献［9］提出了一种基于拓扑服务器的高效率低时延的寻路算法，但没有考虑到基于拓扑服务器的路由(server routing，SR)算法在路由修复操作上存在冗余控制开销和操作。

1 基于拓扑服务器的路由算法

基于拓扑服务器的路由算法［1，8］是针对高速WPAN Mesh网络拓扑结构特点和网络中节点特性而设计的路由协议。其主要思想是源节点通过访问距离源和目的节点最近的公共父节点来获得到达目的节点的最优路径。

SR算法路由建立过程如图1所示，由源节点(Src节点)向目的节点(Dest节点)传送数据。根据基于拓扑服务器的路由算法原理，Src节点通过向它们的公共父节点MC发送Route Discovery消息请求最优路径信息，在MC节点计算完最优路径后，将发送捎带有该最优路径信息的Route Notification消息给Dest节点，Dest节点再根据最优路径信息转发Route Formation消息给Src节点，最后，Src节点将沿着最优路径传送数据。

图1 SR算法路由建立过程Fig.1 Process of SR routing establishment

当有链路失效时，节点发送Route Error消息通知源节点，并由源节点转发Route Error消息给公共父节点，如图2所示。当公共父节点收到Route Error消息后，重新计算被失效链路所影响的源和目的节点之间的最优路径，之后的路由修复过程与最优路径建立过程相同。

SR路由修复过程中存在以下问题。

1 )基于SR算法在转发Route Error消息时是先转发给源节点，然后转发给公共父节点，没有实际考虑当前探测到链路失效节点到公共父节点的距离是否比源节点到公共父节点的距离近。图2中的G节点要比Src节点离公共父节点MC更近一些，在此，可能存在冗余的Route Error控制消息。

2 )基于SR算法由于Route Error消息的转发路径不是最优的，使得路由修复过程存在明显的时延。

本文针对以上缺点提出了一种自适应快速路由修复算法(self－adaptive and fast route recovery algorithm，SFRR)。

图2 SR算法路由修复过程Fig.2 Process of SR routing recovery

2 SFRR算法

SFRR算法包含2种新机制:捎带式发布源节点信息机制和自适应选择路由修复过程机制。新机制的采用使SFRR路由算法比原始基于SR算法减少了不必要的控制开销，并加快了路由修复过程。

2.1 捎带式发布源节点信息机制

在最优路径建立阶段中，在公共父节点计算完最优路径时，将会发送装有最优路径信息的Route Notification消息到目的节点，此时，在Route Notification消息中增加源节点信息域，用来存放跳数信息，并将该信息传递给目的节点。目的节点再将跳数信息装入到Route Formation消息中的新增源节点信息域，同时转发给中继节点，中继节点收到更改后的Route Formation消息后保存源节点信息域中所存的跳数信息。新机制的采用使得中继节点能够直接知道源节点跳数信息，为后续路由修复做铺垫，同时删除了“长度”和“路径控制开销类型”2个不必要的字节域，总体上减小了控制开销。更改后的Route Notification消息格式和更改后的Route Formation消息格式如图3和图4所示。

图3 更改后的Route Notification控制消息格式Fig.3 Corrected Route Notification controlmessage style

图4 更改后的Route Formation控制消息格式Fig.4 Corrected Route Formation controlmessage style

2.2 自适应选择路由修复过程机制

在采用捎带式发布源节点信息新机制的前提下，当节点检测到链路失效时，本节点判断并找到源节点和邻居节点集中距离公共父节点最短的节点，并将沿着该节点转发Route Error控制消息给公共父节点。新机制在完成Route Error控制消息向源节点和公共父节点转发操作的同时，减少了控制开销。同时为了区分是否采用本机制，借助Route Error控制消息中的“长度”域的值(该值为7字节固定值，用于表征Route Error控制消息长度)，当采用了本机制，长度值就会增加 1;否则长度值不变，即没有采用本机制。

2.3 SFRR路由算法具体过程

SFRR路由算法建立过程和数据传输过程与基于拓扑服务器的路由算法一致。其链路修复过程如下。

步骤1 当节点检测到链路失效(链路断开、容量低、电量低等)时，节点根据已知的源节点和邻居节点集信息(到公共父节点距离，用跳数表示)选择距离公共父节点最近的节点(当源节点和邻居节点距离公共父节点相同时，选择邻居节点，因为邻居节点能较早地将Route Error消息通知给公共父节点，并由公共父节点进行后续最优路径的计算)。

步骤2 当节点收到Route Error消息后，判断“长度”域的值:①为固定值“7”时，表明收到原始的Route Error消息，则直接转发给下一跳;②为固定值“8”时，表明收到更改后的Route Error消息，当前节点若不为源节点则直接转发给下一跳。

步骤3 当源节点收到Route Error消息后或更改后的Route Error消息，判断“长度”域的值，若为固定值“7”时，则在修改帧头值后沿着树结构转发给公共父节点;若为固定值“8”时，则销毁该Route Error消息，停止地转发。

步骤4 当公共父节点收到Route Error消息或更改后的Route Error消息时，则根据消息中错误信息重新计算受失效链路影响的源和目的节点对之间的最优路径，之后的最优路径通知、最优路径形成以及数据的传输与SR路由算法的路由建立过程一致。

根据以上4个步骤得出最优Route Error消息的转发路径如图5所示。由此可见，SFRR路由算法省去了冗余的Route Error消息。

图5 SFRR路由修复算法Fig.5 SFRR route recovery algorithm

2.4 计算复杂度

为了验证所提算法的效率，本文从时间复杂度、存储复杂度和通信复杂度3个方面比较SR算法和SFRR算法的计算复杂度。

2.4.1 时间复杂度

设节点平均度为D，节点最大深度为M，则网络直径为2M。根据数据传输的方式可知，数据在相邻节点间传送的时间与D正相关;则SR算法的时间复杂度为o(D(2M+M+M+2M))，即 o(6DM)。设SFRR算法找到通往MC节点捷径的概率为p，显然，0＜p＜1，则SFRR算法的时间复杂度为o(D((2M+M)(1－p)+Mp+M+2M))，即 o(D(6M －2Mp))。显然，o(D(6M－2Mp))＜o(6DM)，即SFRR算法的时间复杂度更低。

2.4.2 存储复杂度

SR算法中占用节点较大存储空间的是到达全网其他节点的路由信息，因此，它的存储复杂度为O(N)，其中，N是网络中节点个数;SFRR算法中节点主要存储路由信息，因此，SFRR算法的存储复杂度也是由网络中节点个数决定，为O(N)，即SFRR算法和SR算法的存储复杂度相同。

2.4.3 通信复杂度

设节点最大深度为M，则网络直径为2M。根据Route Error转发方式可知，其转发次数与深度M正相关;则SR算法的通信复杂度为o(2M+M+M+2M)，即o(6M)。设SFRR算法找到通往MC捷径的概率为p，显然，0＜p＜1，则SFRR算法的通信复杂度为o((2M+M)(1－p)+Mp+M+2M))，即o(6M－2Mp)。显然，o(6M －2Mp)＜o(6M)，即SFRR算法通信复杂度更低。

3 仿真结果及性能分析

3.1 仿真场景设置

为了验证所提算法的性能，在网络仿真器OPNET［10－11］上将 SFRR 算法和传统的 SR 算法进行了性能比较。整个网络中每个节点随机选择非本节点作为自己的目的节点，并按照均值为5的指数分布发送长度为 116 Byte［1，12］的数据分组，仿真参数设置如表1所示。

表1 仿真参数设置Tab.1 Simulation parameters set

3.2 统计量定义

本文统计了平均端到端时延，网络开销，路由修复平均时间3个性能指标。其中，平均端到端时延、网络开销的定义详见文献［9］。路由修复平均时间定义为当整个网络中有链路失效时，节点从发送Route Error消息起到公共父节点收到Route Error消息为止的时间差之和除以失效链路，计算公式为

(1)式中:Treci表示网络中节点(公共父节点)第i次收到Route Error消息的时刻;Tsendi表示检测到链路断开的节点第i次发送Route Error消息的时刻;N为失效链路数。该统计量能很好地表明改进后的算法能更快速进入重新计算最优路径的过程，缩短路由修复过程的时间。

3.3 仿真结果及分析

3.3.1 路由修复平均时间

在网络节点数不同的情况下，SFRR算法和SR算法路由平均修复时间的比较如图6所示。由图6可见，与SR算法相比，SFRR算法具有更小的路由修复平均时间。这是由于SFRR算法在转发Route Error消息的时候选择了更优的路径，从而缩短了路由修复时间。

3.3.2 平均端到端时延

在网络节点不同的情况下，SFRR算法和SR算法在平均端到端时延方面的比较如图7所示。由图7可见，与SR路由算法相比，SFRR算法具有更小的平均端到端时延，这是因为SFRR算法能快速地进入最优路径重新建立阶段，使得数据包能够及时地到达目的节点，缩短了时延。

图6 路由修复平均时间Fig.6 Route recovery average time

图7 平均端到端时延Fig.7 Average end－to－end delay

3.3.3 网络开销

在网络节点不同情况下，SFRR算法和SR算法在网络开销上的比较如图8所示。由图8可见，在网络开销方面，SFRR算法在各个仿真场景上都比SR算法低。这主要是因为SFRR中Route Notification和Route Formation控制包长度的减小以及最优路径的选择会导致控制包转发次数减少的原因。

4 结束语

本文针对IEEE 802.15.5标准中高速部分的SR算法在路由修复部分存在冗余开销和操作的问题，提出了SFRR路由算法，通过捎带式发布源节点信息、自适应选择路由修复机制解决了SR算法存在的问题。理论分析和仿真结果表明，SFRR算法相对于SR算法，在路由修复平均时间、网络开销、平均端到端时延性能上具有更好的表现。

图8 网络开销Fig.8 Network overhead

［1］LAN/WAN Standards Committee of the IEEE Computer Society.IEEE Std.802.15.5－2009，part 15.5:mesh topology capability in wireless personal area networks(WPANs)［S］.New York:IEEE Press，2009.

［2］雷震洲.高速率无线个域网(WPAN)［J］.电信科学，2002，18(6):5－7.

LEIZhenzhou.The High－rate Wireless Personal Area Networks［J］.Telecommunications Science，2002，18(6):5－7.

［3］LEE Myung，ZHANG Rui，ZHU Chunhui.Meshing Wireless Personal Area Networks:Introducing IEEE 802.15.5［J］.IEEECommunications Magazine，2010，48(1):54－61.

［4］史晓晨，刘凯明，高锦春，等.无线个域网mesh网络标准——IEEE 802.15.5［J］.计算机应用研究，2011，28(1):243－246.

SHIXiaochen，LIU Kaiming，GAO Jinchun，et al.Standard of Mesh Wireless Personal Area Network ——IEEE 802.15.5 ［J］.Application Research of Computers，2011，28(1):243－246.

［5］江禹生，何芳.改进的WPAN网状自适应树路由算法［J］.重庆大学学报，2010，33(4):88－91，97.

JIANG Yusheng，HE Fang.Improved WPAN Meshed A－daptive Tree Routing Algorithm［J］.Journal of Chongqing University，2010，33(4):88－91，97.

［6］CHAKERES I D，KLEIN B L.AODV simplified［J］.ACM SIGMOBILE Mobile Computing and Communications Review，2002，6(3):100－101.

［7］江禹生，何芳，宋香丽.改进的WPAN mesh路由协议［J］.计算机工程与应用，2011，47(9):109－111.

JIANG Yusheng，HE Fang，SONG Chunli.Improved WPAN Mesh Routing Protocol［J］.Computer Engine－ ering and Application，2011，47(9):109－111.

［8］JIW J，MA J F，MA Z，et al.Tree－Based Proactive Routing Protocol forWireless Mesh Network［J］.China Communications，2012，1:25－33.

［9］REN Z，WANG K，LEIH，et al.An Effective Low－Delay Server Routing Algorithm in WPAN Meshes［C］//2012 Second International Conference on Business Computing and Global Informatization. Shanghai:IEEE Press，2012:611－614.

［10］李馨.OPNETModeler网络建模与仿真［M］.西安:西安电子科技大学出版，2006:148－218.

LIXin.OPNETModeler Network Simulation［M］.Xian:Xidian University Press，2006:148－218.

［11］陈敏.OPNET网络仿真［M］.北京:清华大学出版社，2004:51－97.CHEN Min.OPNET Network Simulation［M］.Beijing:Tsinghua University Press，2004:51－97.

［12］EUNCHANG C，JAEDOO H，KWANGSIK K，et al.Selection of Serving PNCs Based on Measured FER within IEEE 802.15.5Wireless Mesh Network［C］//2007 International Conference on Convergence Information Technology.Gyeongju:IEEE Press，2007:2130－2135.

(编辑:刘 勇)