无线网状网络的多路径路由与调度算法*

崔智军

(1.安康学院 电子与信息工程学院，陕西 安康 725000；2.西北工业大学 电子信息学院，陕西 西安 710129)

无线网状网络的多路径路由与调度算法*

崔智军1，2

(1.安康学院电子与信息工程学院，陕西安康725000；2.西北工业大学电子信息学院，陕西西安710129)

提出了一种保障服务质量的多路径路由算法，数据分组可通过多条不同的路径进行传输，以提升网络总吞吐量性能。进一步提出了一种多路径调度策略。通过使用调度策略，基于当前可用带宽信息和路径所引入的时延信息，数据分组在传输前可被分成多段并通过不同的路径发送，根据路径时延调整优化调度策略，从而使得数据可通过在不同的路径上进行更高效地传输。仿真实验进一步验证了本文提出的路由机制和调度策略在不同网络负载下的优越性。

无线网状网络； 多路径； 负载均衡

0 引 言

无线网状网络(wireless mesh networks，WMNs)是一种呈网状拓扑结构且节点资源有限的无线自组织网络，通常由网关、Mesh节点和路由器组成[1～3]。WMNs是一种高效且鲁棒的可扩展无线通信系统，且随着各种路由及调度方法的出现，使得音视频流的服务在WMNs上可行[4,5]，因而适用于实时应急通信方案。由于无线链路之间的干扰和传输信号的衰落容易造成链路流量下降，会导致WMNs中的数据传输过程存在巨大的挑战[6]。针对该问题，有研究提出了利用多路径传输视频，一般根据路由跳数及时延对路由进行评估，通过最小化路由的跳数或时延获得最优路径[6，7]。而在WMNs中，采用多路径路由协议可以节省带宽，提高安全性和可靠性，也可以避免路由频繁更新，提高数据的传输，增加带宽。尽管目前基于WMNs已开发了一些多路径路由协议与算法，例如AOMDV,TORA,SMR协议与EECA算法[8～12]等，但多路径负载平衡仍然是路由协议中难以解决的关键问题。一方面，源节点的数据包分发策略可能导致速率分配不公平的问题；另一方面，由于无线通信自身内在的属性可能会导致无线网状网中的多路径负载平衡的优势不太明显。可以看出，高效的多路径路由协议有助于延长WMNs的生命周期。因此，在多路径路由协议中，一方面，制定更有效的拥塞控制和速率调整策略亦变得尤为重要；另一方面，针对多路径路由协议制定合适的路径质量评价指标，对评估负载平衡和拥塞控制计划同样至关重要。

1 数学定义及描述

假设用图G(V,E)描述一个包含N个节点的WMNs，其中,V为网络节点的集合，E为集合V中节点组成的连接集合。每一个网络节点v∈V，其传输范围为Rt(v)，载波感知范围为Rc(v)。令eij表示连接节点vi到vj的边，其中vi,vj∈E，且1≤i,j≤N。当节点ni处于nj的传输范围之内，同时nj也在ni之内时，则有eij∈E。

定义1：在连接e=(u,v)∈E上的负载LL(e)∈R表示在连接上L(u,v)的传输，其为通过该链路所有不同路径流量负载之和。对于一个连接e∈E(e为两个相临节点u和v之间的连接)，令fm为链路e上的流量，e在路径pm上，如果有M条路径通过e，则e上的负载可表示为

(1)

类似地，pm上的负载为

(2)

定义2：链路上的传输延时d(e)∈R，由两部分组成，队列延时与传输延时。一般，不同链路间的延时互相独立。

定义3：路径上pm的延时d(pm)。对于从源节点i到目标节点j的每条路径，路径pm由一组节点表示，ni,ni+1,… ,nj,且∀k,i≤k≤j,(ni,ni+1)∈E，并且所有节点仅出现一次，如式(3)

(3)

定义4：路径pm上的可得带宽b(pm)，由路径上最低链路的带宽决定，如式(4)

b(pm)=min{b(nk,nk+1)},i≤k≤j

(4)

定义5：端到端的丢包率。链路上的丢包率相互独立，令dr(nk,nk+1)为路径(i,j)上的链路(nk,nk+1)的丢包率，则路径(i,j)上的丢包率可由式(5)近似表示

(5)

此外，从源节点到目的节点的多条路径可以定义为P={p1,p2,...,pM}，其中,M为路径的数量。总的M条路径的带宽B可表示为

(6)

本文多路径路由问题可以拆分为最小化端到端时延和拥塞检测两个子问题进行研究:

1)最小化端到端时延

数据分组被分发到M条路径上，当多路径路由启动后，接收端节点为了能够合并数据分组，需要从最长的路径发送的数据到达以后开始解码，因此，所产生的时延为

D(P)=max{D(pm)},m∈{1,…,M}

(7)

2)拥塞检测

在多径路由中的关键问题之一是根据当前的流量检测即将来临的超载，从而进行流量控制。对于M条路的多路径路由，源节点S需要通过多路径发送或转发。当一个新的视频流f以基本比特率rf进入，并希望通过多路径集合P输出，S检查是否f的传输会造成过载。基于S的传入率检测结果，数据分组被传递到多路径。可以看出，如果路径p的带宽B(p)满足条件B(p)≥rf，则S认为多路径集合P为能够承载f；否则，如果B(p)

2 多径路由与调度算法

2.1 路由发现机制

对具有N个节点的无线网状网络中，节点i的邻居节点集合记为N(i)，则Sij∈N(i)表示到达目标节点j的子节点集合，令Sij(k)表示以i为源节点，以j为目标节点数据流路径上的节点k的下一跳节点集。

在网络设置初始阶段，所有节点均可以找到多个路径到网关χ，网关χ广播HELLO消息至其邻节点。在收到HELLO消息后，在N(χ)的邻近节点将启动“路径发现”以寻找到所有网关的路径并以可得带宽升序进行排列。这些节点进一步广播HELLO与链路的信息。其中，HELLO消息包含所有到χ的路径及其序列。其他收到HELLO消息的节点可能会收到由同一χ发出的来自不同的路径HELLO消息，进而节点决定每条路径上的父(parent)节点并增加到路由表中。之后，该节点单播一个Parent消息到选定的Parent节点。Parent消息包含了其已经由HELLO消息选择的所有路径。至此，通过Parent消息将所用来传输的路径告知其Parent节点，从而Parent节点在路由表中记录其子(child)节点并更新相应的路径。之后，Parent节点单播一个Child消息，通知所有路径上的相应节点，包括关于Child节点的网关χ和关于Child节点的可达路径。在收到Child信息时，每个Parent节点在各自的路由表中注册其Child节点，并按照类似的步骤注册该Child节点可到达的多条路径。通过这种方式，在从网关到Child节点的路径中，包括网关的每个中间节点均有一个或多个路径到响应的Child节点。

2.2 路由维护机制

在WMNs中，当添加新节点或一些现有的节点退出网络之后，路由协议必须进行更新维护。在寻找新的路径或新的节点时，一个节点将更新其路由表，并将该信息通知邻居节点。受影响的节点将及时通过该信息更新其路由表，并进一步广播。一个节点仅在得到网关χ准入后，才可以被添加到该Mesh网络中。入网后，每一个新的节点将发送一个Find信息，并找到网关的路由，进而由网关来回复准入或否决信息。

2.3 多径调度算法

本文将数据流分割成多个片段，片段被传递到多路径。为了克服流量拥塞的局限性，本文基于多路径负载感知提出了一种新的自适应调度传输方案。首先通过过载检测提高多路径传输的鲁棒性。对于一个有M条路径的无线网状网路，起初能够找到一种多路径集。假设路径pk具有最大d(pk)，则目标节点将所有来自延时小于pk的路径上的数据包缓存。本文针对每个节点上数据流的分发，提出了一种多路径调度算法(multipath scheduling algorithm,MSA)，如图1所示。

图1 视频流的多路径调度

由图1可以看出，给定M条路径，P={p1,p2,…,pM}，则相应的延迟分别为{d(p1),d(p2),…,d(pM)}。一个数据源在时间上分成t1,t2,…,tk个片段，其中，k为路径数，各个路径上的延迟有d(p1)<…

(8)

式中B为M条路径的总带宽；b(pi)为路径pl上的带宽;d(pi)为路径pi上的延时。为了避免一个链路的负荷超载，流量根据瓶颈的剩余容量按比例分配。当多路径中的路径彼此独立时，负载均衡能够有效抑制拥塞并获得较高的数据传输率。因此，通过采用MSA，当不同的路径上的负载不同时，沿不同的路径传送相同数据段，将在同一时间到达目标,从而保证数据流的连续性。

3 仿真分析

3.1 衡量指标

1)平均时延：所有传输成功的数据分组时延之和与所成功传输的数据分组个数之比

(9)

式中Di为第i个数据分组的端到端时延，主要包括MAC排队时延、分组传输时延以及帧间间隔等时长；N为传输成功的数据分组个数。

2)时延抖动:连续的数据分组延迟之间的差。例如，节点j在路径m上的时延抖动可表示为

(10)

(11)

r在m条路径上的平均时延抖动可表示为

(12)

3)丢包率：由于干扰或冲突导致丢失的分组个数Numlost与发送分组的总数Numtotal之比

η=Numlost/Numtotal

(13)

3.2 仿真设置

仿真基于NS—2网络仿真软件所搭建，使用的软件版本为NS—2.35。网络拓扑如图2所示，所有节点处于一个1 km×1 km的正方形区域内。数据源的输入为CBR视频流业务，速率为128 kbps，视频流输入到WMNs并通过多条路径传输到目标节点，而目标节点再将接收到的数据流进行解调与恢复。该WMNs有6个节点，其中有一个源节点S和一个目标节点R。信道带宽设置为2 Mbps，主要仿真参数遵循IEEE 802.11b协议[13]。

图2 网络仿真拓扑

3.3 仿真结果

图3为平均分组时延曲线，其中每个点为50轮仿真均值。可以看出：当网络流量负载大于600 kbps时，采用本文所提出的MSA可明显降低数据包的传输时延。随着网络流量的持续增加，MSA可大幅度提升网络性能。

图3 平均分组时延

图4为仿真中的平均时延抖动性能。可以看出：当网络业务量大于400 kbps时，采用MSA可以显著降低网络的分组时延抖动，平均降幅约为30 %。需要注意的是，当业务量大于1 400 kbps时，不采用MSA，时延抖动急剧上升。表明MSA可以获得高效的负载平衡性能。

图4 平均时延抖动

图5为丢包率与网络流量负载的关系。可以看出，随着网络流量负载的增加，丢包率呈现出逐渐增加的趋势。对于无MSA而言，当网络流量负载提高到600 kbps，其丢包率增加了约3.4 %左右。当网络流量负载逐渐增加时，无MSA算法与采用MSA算法之间的丢包率差距越来越大。表明MSA算法能自适应地将数据分组分流到不同的路径上。

图5 丢包率

4 结束语

提出了一种基于Mesh网络中多路径路由与调度算法。根据不同路径的带宽和延迟，数据分组被分割为大小不同的数据流并分发到相应的路径上，数据流通过多条路径到达目标，从而提高Mesh网络总吞吐量。该多路径路由与调度算法可应用于密集部署的网络环境，如5G等网络。

[1] Birlik Firat,Ercetin O,Gurbuz O.Prioritized video streaming in wireless mesh networks[J].Journal of Medical Genetics,2007,47(3):1-3.

[2] Chen Jiancong,Chan S,Li V.Multipath routing for video delivery over bandwidth limited networks [J].IEEE Journal on Selected Areas in Communications,2004,22(10):1920-1932.

[3] Li Shancang,Wang Xinheng,Zhao Shanshan.Multipath routing for video streaming in wireless mesh networks[J].Ad Hoc & Sensor Wireless Networks,2011,11(1):73-92.

[4] Mao Shiwen,Hou Y,Sherali H,et al.Multimedia-centric routing for multiple description video in wireless mesh networks[J].IEEE Network,2008,22(1):19-24.

[5] Wang Xinheng,Iqbal M,Zhou X.Design and implementation of a dual-radio wireless mesh network testbed for healthcare[C]∥Proceedings of the 5th International Conference on Information Technology and Application in Biomedicine,Shenzhen,China,2008:300-304.

[6] Wang Tao,Cui Xunxue,Liu Ping.A novel video monitoring system based on wireless mesh network[C]∥International Colloquium on Computing,Communication,Control,and Management,2008:542-546.

[7] Alariki H D E,Swamy M N S.A survey and analysis of multipath routing protocols in wireless multimedia sensor networks[J].Wireless Networks,2017,23(6):1823-1835.

[8] Zhu Yingnan,Zeng Wenjun,Liu Hang,et al.Supporting video streaming services in infrastructure wireless mesh networks:Architecture and protocols[C]∥IEEE International Conference on Communications,2009:1850-1855.

[9] Zhu Xiaoqing,Girod Bernd.Media-aware multi-user rate allocation over wireless mesh network[C]∥The 1st Workshop on Operator-Assisted Community Networks,Berlin,German,2006:1-8.

[10] Shui Guojun,Shen Shuchun.Video streaming transmission over multi-channel multi-path wireless mesh networks[C]∥The 4th International Conference on Wireless Communications,Networking and Mobile Computing,Dalian,China,2008:1-4.

[11] 杨海波.一种能量高效的无线传感器网络分簇路由算法[J].传感器与微系统,2008,27(7):50-52.

[12] 王世强，邢建春，李决龙,等.面向无线传感器网络的无线携能通信研究[J].传感器与微系统,2015,34(8):46-53.

[13] ANSI/IEEE.802.11:Wireless LAN medium access control (MAC) and physical layer (PHY) specifications[S].IEEE 802.11 Std.2012:380-437.

Multipathroutingandschedulingalgorithmforwirelessmeshnetworks*

CUI Zhi-jun1,2

(1.CollegeofElectronicsandInformationEngineering,AnkangUniversity,Ankang725000,China;2.CollegeofElectronicsandInformation,NorthwesternPolytechnicalUniversity,Xi’an710129,China)

A novel multipath routing algorithm with QoS provision is presented,in which traffic takes multipath to reach the destination,thereby increasing the aggregated throughput.Based on proposed multipath routing algorithm,a scheduling strategy is further proposed,by which the traffic is divided into multiple segments before transmitted according to the path available bandwidth and path delay.The scheduling strategy can be adjusted according to the path delay,therefore data packets can be transmitted on multipath with more high efficiency.The routing scheme and the multipath scheduling strategy are verified by network simulations performed with different network load.

wireless mesh networks; multipath; load-balancing

10.13873/J.1000—9787(2017)12—0137—04

TN 925

A

1000—9787(2017)12—0137—04

2017—10—16

国家自然科学基金资助项目(61461025)；陕西省教育厅科学研究计划资助项目(17JK0018)；国家级大学生创新训练项目(G201711397005)；安康学院校级青年基金资助项目(2017AYQN08)

崔智军(1978-)，男，博士研究生，讲师，主要从事微型磁通门传感器研究工作。