WPAN Mesh 网络中基于服务器的高效路由算法

雷宏江，汪坤露，高 潮，任 智

(1.重庆邮电大学移动通信技术重庆市重点实验室，重庆 400065;2.重庆大学光电技术及系统教育部重点实验室，重庆 400044)

0 引言

无线个域网(wireless personal area network，WPAN)是一种能使便携式家用电子产品和通信设备以Ad hoc方式组网工作的无线网络［1-2］，根据应用场合的不同可分为高速WPAN和低速WPAN。其中，高速WPAN具有支持11～55 Mbit/s的数据传输速率、便于加入或离开网络等特点。在WPAN中使用Mesh结构进行网络连接［3］，构成了WPAN Mesh(无线个域网状网)，可以在保持WPAN特点的基础上弥补其存在的带宽较窄、覆盖范围小等不足，并具有以下优点:不需要增加发射功率或提高接收灵敏度就可扩展网络的覆盖范围;能够通过冗余路由增加数据传递的可靠性;可以简化网络节点配置、延长节点寿命。在高速 WPAN中，有两种节点:PNCs(piconet coordinators)节点和DEVs(devices)节点。PNC节点通常是静止且电源供电的复杂设备，而DEV节点通常是移动且电池供电的精简设备。

适用于WPAN Mesh网络的现有路由算法有很多，主要都是基于mesh树路由协议的改进。文献［4］以IEEE802.15.5标准低速 WPAN 中的网状自适应树(meshed adaptive tree，MAT)为基础，将MAT划分为两层结构，且在划分后的两层结构采用不同的路由算法，提出了分级路由算法。但是，该路由算法由于采用传统的无线自组网按需平面距离矢量路由协议(ad hoc on-demand distance vector routing，AODV)，从而存在由泛洪引起的过多控制开销、消耗大量网络资源等问题。文献［5］中以MAT为基础，将MAT和AODV结合，提出了TLMR(two-level mesh routing)路由算法。即，先在MAT中查询有效路径，如果不存在有效路由，则采用AODV。该路由算法同样存在AODV的缺点。文献［6］中提出了改进的基于树结构的路由算法。其主要思想是在设备发现过程中父PNCs节点将建立到本微微网的子设备和子PNCs以及子微微网里的设备的路由信息，同时子PNCs也会建立到本微微网子设备以及它的子PNCs(如果存在)的路由信息。当父PNCs或子PNCs节点收到数据分组时，将根据路由信息接收或者转发。但是该路由算法在有横向节点通信时所选路径不是最短或最优的路径。

1 基于服务器的路由算法

基于服务器的路由算法［1］是针对高速WPAN Mesh拓扑结构特点和网络中节点特性而设计的树路由协议。该算法分为3个阶段:链路状态信息的注册阶段、最优路径的建立阶段和数据传输阶段，其主要思想是源节点通过访问距离源和目的节点最近的公共父节点获得到达目的节点的最优路径(采用Dijkstra或Ford算法计算得到)。

图1为路由算法(server routing，SR)的路由过程。Src为源节点，Dest为目的节点，R为网络中的服务器节点(根节点)，即 Src和Dest的公共父节点。Src到Dest经SR算法计算后得到的最优路径为Src-F-E-Dest，而树路由得到的路径为Src-A-B-RC-D-Dest。与树路由相比，SR算法能在横向路径上找出最优路径。

SR算法仍然存在冗余的操作过程:每次转发中继列表信息，都是将整条最优路径的信息进行转发，这样存在转发已经达到的中继节点的冗余列表信息。本文针对这个缺点，提出了一种改进的路由算法—高效率低时延的路由算法(high-efficiency and low-delay routing algorithm，HLRA)，该算法在解决以上问题的同时，实现了快速创建最优路径。

图1 SR算法寻路过程示意图Fig.1 Processes of server routing algorithm

2 HLRA算法

针对原始SR算法的缺点，本文提出了两种新机制:广播链路状态注册消息和缩短中继列表长度，并基于它们提出了新的路由算法HLRA。新机制的采用使HLRA算法具有减少不必要的控制信息、缩短建路时间，提高路由算法效率等优点。

2.1 广播链路状态注册消息

链路状态注册消息是链路状态信息注册阶段由子孙节点发给父辈节点包含链路状态信息的控制消息。在HLRA算法中，节点在转发链路状态注册消息时，在媒体访问控制(media access control，MAC)子层采用广播的方式，且在该消息的“Destination TREEID”域填入父节点地址。新机制的采用不仅能完成链路信息的注册，而且能使所有邻居节点获得该消息中的链路信息，有利于后续更快地建立最优路径。

2.2 缩短中继列表长度

路径形成消息是用来在所得最优路径上传递路径信息的控制消息，SR算法中每个路径形成消息将传递整条路径上的中继列表信息。而在本新机制中，路径形成消息的长度是可变的:在转发过程中，将该消息经历过的节点信息删除后再转发，如图2所示。改进后的路径形成消息在不改变原有的功能下，长度缩短还减少了通信开销。

引理 在相同的网络条件下，采用缩短中继列表信息机制可以使HLRA算法比SR算法有更少的控制开销。

证明 假设网络中一共产生m次需要借助服务器计算最优路径的数据传输过程，每次过程的中继列表有ni(i∈(1，m))个中继节点信息(2ni字节的节点标识和2ni字节的节点开销)需要被转发。

在SR算法中，需要转发中继列表信息的平均开销为

(1)式中，ni+1表示目的节点需要将中继列表信息转发ni+1次才能到达源节点。

由于在HLRA算法中，每经过一个中继节点，都将该节点对应的信息删除，所以HLRA算法的平均开销为

图2 缩短中继列表长度Fig.2 Reducing the relay list

3 性能评估

本节通过仿真比较分析网络开销、平均端到端时延和包的投递率三方面的性能，从而验证HLRA算法的有效性和优越性。

3.1 仿真设置

采用 OPNET 14.5［7］仿真软件构建高速 WPAN Mesh网络5 个仿真场景，分别为:50，100，150，200和250个节点;网络中的所有节点都有唯一的地址;每个节点随机地选择其他节点作为目的节点;每个节点按照均值为5的指数分布发送长度为116 Byte［1，8］的数据分组;链路状态信息以跳数为默认值。

3.2 性能参数

1)网络开销:网络中发送的控制分组比特数和数据分组比特数之和，用于评价算法的效率。网络开销C的计算公式如下

(3)式中，NB，NDi，NN，NF，NReq，NReg分别表示网络中信标消息、路径发现消息、路径通知消息、路径形成消息、链路状态请求消息和链路状态注册消息在发送时的比特数。

2)平均端到端时延:指所有数据分组从源节点到达目的节点的平均时延。平均端到端时延的计算公式如下

(4)式中，Ti和Di分别表示第i个数据分组到达目的节点所需时间和当前网络中总的收到的数据包个数。

3)包的投递率:指成功收到的数据包数比上发送的数据包数的比值

(5)式中:Ri表示成功收到的数据包个数;Sj表示发送的数据包个数。

3.3 仿真结果及分析

以原始的SR算法作为比较对象，在相同的仿真条件下分析该算法与HLRA算法的平均端到端时延、网络开销等性能。

3.3.1 网络开销

通过累计发送的信标、链路状态注册、路径通知、路径形成等控制分组的比特开销和发送数据分组时比特开销之和得到网络开销。而在HLRA算法中，路径形成消息的长度会动态变化。

图3为两种算法在多个场景中分别统计出的网络开销。由图3可知，在网络开销方面，HLRA算法在各个网络仿真场景都比原始的SR算法低。开销减少的主要原因来自于两跳邻居节点建路过程的省略以及中继列表信息长度的缩短。

图3 网络开销Fig.3 Network overhead

3.3.2 平均端到端时延

图4是两种算法在5个仿真场景中分别统计出的平均端到端时延。由图4可知，HLRA算法的数据分组平均端到端时延都低于SR算法的时延。HLRA算法的平均端到端时延较小的原因有两方面:①广播链路状态注册信息新机制可以缩短建立两跳邻居节点通信的时间，省去了一定建路时间;②中继列表长度的缩短，减少了节点对这些控制消息的处理和传送时间。

图4 平均端到端时延Fig.4 Average end-to-end delay

3.3.3 包的投递率

表1为SR算法和HLRA算法在仿真中的包投递率。由表1可知，SR算法和HLRA算法在各个场景中包的投递率几乎一样，基本能到达100%的理论值。

表1 包的投递率Tab.1 Packet delivery ratio

4 结束语

本文针对IEEE802.15.5标准中高速部分的SR算法存在的转发冗余的中继列表信息问题，提出了HLRA路由算法，通过广播链路状态注册消息和缩短中继列表长度新机制解决了SR算法存在的上述问题。理论分析和仿真结果表明HLRA算法相对于SR算法，在网络开销、平均端到端时延等性能上具有更好的表现。未来的工作将在HLRA算法的基础上，增加节能功能和对动态拓扑的适应，通过设计绿色的路由算法来构建绿色的WPAN Mesh网络［9］。

［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.LEI Zhenzhou.The High-rate Wireless Personal Area Networks［J］.Telecommunications Science，2002，18(6):5-7.

［3］杨震，田峰.基于环境感知的异构无线Mesh网络体系结构及关键技术［J］.中兴通讯技术，2010，16(4):81-86.YANG Zheng，TIAN Feng.Research on Architecture and key Techniques of Ambient Heterogeneous wireless Mesh Networks［J］.ZTE，2010，16(4):81-86.

［4］江禹生，何芳.改进的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.

［5］江禹生，何芳，宋香丽.改进的WPAN mesh路由协议［J］.计算机工程与应用，2011，47(9):109-111.JIANG Yusheng，HE Fang，SONG Xiangli.Improved WPAN Mesh Routing Protocol［J］.Computer Engineering and Applications，2011，47(9):109-111.

［6］SANG Bongjung，HYUN Kikim，SOON Binyim，et al.Channel Time Allocation and Routing Algorithm for Multi-hop Communications in IEEE 802.15.3 High-Rate WPAN Mesh Networks［C］//Yong Shi.The International Conference on Computational Science 2007(ICCS 2007).Beijing:Springer-Verlag，2007:457-465.

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

［8］EUNCHANG Choi，JAEDOO Huh，KWANGSIK Kim，et al.Selection of Serving PNCs Based on Measured FER within IEEE 802.15.5 Wireless Mesh Network［C］//Jungwoo Lee.2007 International Conference on Convergence Information Technology.Gyeongju:IEEE Press，2007:2130-2135.

［9］林闯，田源，姚敏.绿色网络和绿色评价:节能机制、模型和评价［J］.计算机学报，2011，34(4):593-612.LIN Chuang，TIAN Yuan，YAO Min.Green Network and Green Evaluation:Mechanism，Modeling and Evaluation［J］.Chinese Journal of Computer，2011，34(4):593-612.