基于MILP模型的无线Mesh网络多径路由优化方案*

李 岱， 韩小纯

(1.汉江师范学院 计算机科学学院，湖北 十堰 442000;2.南京大学 电子科学与工程学院，江苏 南京 210046)



基于MILP模型的无线Mesh网络多径路由优化方案*

李 岱1*， 韩小纯2

(1.汉江师范学院 计算机科学学院，湖北 十堰 442000;2.南京大学 电子科学与工程学院，江苏 南京 210046)

针对多接口多信道无线Mesh网络(WMN)中多径路由优化问题，提出一种基于混合整数线性规划(MILP)模型的多径路由优化方案.首先，利用Selectxfor less thanx拓扑控制算法构建网络连接图.然后，利用MILP模型，在考虑链路容量、节点度约束和链路流量下，构建链路负载均衡的多径路由.另外，利用图着色理论分配信道，形成完整的WMN模型.实验结果表明，该方案具有较高的网络吞吐量和较低的端到端延迟.

无线Mesh网络；多径路由；混合整数线性规划；连接图；负载均衡

无线Mesh网络(WMN)是一种无线接入网络技术[1]，能够在不同环境下提供宽带无线接入服务.对于无线传感器网络和移动Ad Hoc网络，由于这些网络中的节点具有移动性且电池供电，所以路由优化和节约能耗是网络路由机制的主要目标.然而，对于WMN，由于其通常由固定电源供能，所以其路由优化机制侧重于提高网络吞吐量和减少端到端传输延迟[2].WMN中，链路干扰是影响吞吐量的一个重要因素.当具有相同方向的两条链路，使用相同信道同时短距离传输数据时，则会形成无线干扰，进而会严重影响网络的吞吐量[3].另外，WMN是一种相对静态的网络，其中的节点大多位于固定位置，所以WMN的多径路由通常采用树状结构来表示[4].目前，已提出多种多径路由优化方案，其中，无线网络中比较典型的有按需距离矢量路由(AODV)协议、优化链路状态路由(OLSR)协议等.然而，当网络规模不断增大时会出现瓶颈节点，致使路由稳定性大大下降.[5]融入了先验式路由来改进传统AODV协议，称为HWMP协议.然而，HWMP协议中的网关节点需要转发大量数据，这种负载不均衡现象会使一些节点的能量过度消耗而降低网络性能.

WMN的优化问题在实际应用中分为路由优化和信道分配，基于连接图构建多径路由，基于冲突图分配信道.本文主要研究多径路由的优化，利用Selectxfor less thanx拓扑控制算法(TCA)[6]构建网络连接图.然后，考虑链路容量和节点度约束，利用混合整数线性规划(MILP)模型，构建低成本的负载均衡多径路由.对于信道分配，则采用常用的图着色理论.实验结果表明，本文方案能够有效提高网络吞吐量，降低网络延迟.

1 WMN网络模型

无线Mesh网络由网关、无线路由器和移动站组成.多播树的源节点表示网关，中间节点表示WMN骨干网络中的无线路由器，多播树中的接收者是移动站.组播树中构建节点多径路由是一个NP完全问题[7].

设定WMN中的路由器分布在一维平面上，并利用图论理论来构建WMN模型.其中，每个路由器的全向天线具备1个或多个无线接口，且每个无线接口传输时的传输范围和干扰范围都相同.那么，WMN中的节点连接图就可以用一个无向图C(V，E)来表示.如果两个节点位于各自的传输范围之内，那么，它们之间就存在一条通信链路，用一条边表示.图1(a)为一个具有5个节点和7条边的WMN网络结构.

由于WMN节点连接图中的链路之间可能存在干扰，那么可以根据连接图，构建一个反映网络干扰情况的冲突图Cc(Vc，Ec).以图1(a)中的连接图为例，将连接图中的每条边设定一个标识符，并作为冲突图中的顶点.如果连接图中某两条边在各自干扰范围内，即存在干扰，那么在冲突图中将这两条边对应的顶点之间用一条边连接，最终构建一个冲突图，如图1(b)所示.以冲突图作为网络干扰模型能够直观地描述干扰情况[8].

2 提出的多径路由优化机制

2.1 构建连接图

Selectxfor less thanxTCA中，每个路由器都以最大功率广播一个Hello信息，包括了节点ID和位置.根据接收的Hello信息，每个路由器都按照距离的升序安排相邻节点，形成最大功率邻居表(MPNT).然后每个路由器通过控制通道发送器MPNT及其位置和节点ID到网关(GW).对于网络中的每个路由器，网关通过选出最少x个距离路由器最近的节点来构建一个直接的邻居表，然后将一个网孔节点的直接邻居表中的单向链接转变为双向链接，形成最终的邻居表，从而构建连接图.

2.2 基于MILP模型的多径路由优化

本文将对无线WMN中的多径路由问题构建为一种混合整数线性规划(MILP)模型[9].所涉及到的参数定义如表1所示.

表1 WMN多径路由模型中的参数Tab.1 The parameters of WMN multipath routing model

本文中，采用标准链接容量值，即IEEE802.11中，当链接数据速率为12、24、36和54 Mbps时，最大实际吞吐量(最大链接吞吐量)分别为9.18、15.52、20.03和24.73 Mbps.

(1) 目标

(1)

在考虑连接图、链路容量、节点度约束和源-终对之间的单位流量需求下，路由问题的目标为最大化y，即路由中的单位流量需求的倍数，以便在使用多径路由的网络获得源-终对的最大总流量.在本文中，最大网络吞吐量意味着网络最大可能的总流量，即从所有源到达GW的最大可能流量.由于所有源-终对之间的流量需求为1且y为该流量需求的倍数，所有y也代表了从源到达GW的流量的总量.通过最大化y来确保从每个源到达GW的流量得到最大化.公式(1)中costij较小的值，可用来在不影响结果的情况下避免多余的流动回路.

(2) 约束

下面分别为源节点、汇聚节点(即GW)和中间节点的流量平衡约束.对于源节点(或汇聚节点)，一个路由的总输出流量等于该路由的总输入流量以及该路由从该路由的源(或汇聚点)得到的流入(或流出)的量.对于中间节点，一个路由的总流入量等于该路由的总流出量：

(2)

(3)

(4)

下面的公式代表了WMN中节点的节点度约束.在该网络中的任何网格节点中，存在着有限的接口数量，因此有了对输入和输出链接数量的限制.如果限制为4，即如果dc=4，那么在每个网格节点ni的节点度约束为：

(5)

网络中的最大总流量取决于特定节点度约束下的GW(汇聚点)节点的链接数.针对不同的节点度约束，改变Selectxfor less thanxTCA中的x来确保节点度约束增加时，网络的总流量也增加.TCA在给定的节点度约束下创造了一定数量的连通性，并为GW创造了一定数量的链接.对于节点度约束为3时，本文选择Select 3 for less than 3 TCA来确保连接图中的GW至少有3个链接；对于节点度约束为4的情况，本文选择Select 4 for less than 4 TCA来确保连接图中的GW至少有4个链接，等等.由于Select 2 for less than 2 TCA会导致随机情况下网络断开情况，所以，本文在节点度约束为2时，也使用Select 3 for less than 3 TCA.

下面的约束保证了多径路由中流量间的均衡性，即y的改变(路由中单位流量需求的倍数)确保了所有路由的流入量同时改变：

(6)

下面约束保证了节点中无线接口的半双工传输，即链接可用于传输或接收，但不能同时执行这两种操作：

zij+zji, for all i and j，i,j∈V.

(7)

下面约束为链接容量约束，用来确保一个链接上路由流量的总和不超过链接容量：

(8)

链路容量不能为负：

cij≥0, for all i and j，i,j∈V.

(9)

一个链接上的路由p的流量应为非负数，但并不需要是整数：

(10)

本文使用一种求解大规模复杂数学问题的建模语言：AMPL语言来描述多径路由问题，使用IBM CPLEX12.2来解决产生的MILP问题.本文在CPLEX中设定mipemphasis=1并要求其查询第一个可行解.如果该求解程序不同于找到节点度约束为2或3的多路径路由问题的解决方案，本文将改用较高的TCA来构建连接图，即Select 4 for less than 4 TCA或Select 5 for less than 5 TCA，直到找到第一个可行解决方案.

3 基于图着色理论分配信道

对于多接口WMN，每个节点都配备有多个无线接口，节点间的干扰会使网络的传输性能严重降级.为此，需要在WMN路由模型和冲突图基础上进行信道分配.信道分配的主要目的是为在彼此干扰范围内的两条链路分配两个不同的信道，以此来避免信道冲突.由于本文重点在WMN的路由协议，所以本文采用传统的图着色理论[10]来进行信道分配.图着色理论是以冲突图为基础，以不同的颜色来表示不同的链路信道，将信道分配问题转变为冲突图中节点着色问题.通过图着色理论，为冲突图中的节点分配不同颜色，以使冲突图中边的数量最小化，致使整个网络的干扰最小，提高网络吞吐量.

4 实验及分析

4.1 网络环境

利用网络仿真软件OPNET[11]构建1 000 m×1 000 m大小的无线Mesh网络，并划分成单元格，将节点随机放入单元格中，构建包含11～51个节点的不同拓扑结构的网络.将节点1设定为网关节点，并放置在网络中央，用于汇聚各节点信息.采用IEEE802.11标准作为MAC层协议，利用CSMA/CA作为传输机制.设定链接数据速率为24 Mbps、节点传输距离为150 m、数据帧大小为1 024 bit、数据产生率为50帧/s、网络中可用信道数为12.

4.2 性能比较

首先，在不同节点度下评估网络吞吐量性能，将本文方案与传统OLSR协议和文献[5]提出的HWMP协议进行比较.其中，网络吞吐量为网络中所有流量源所传输的流量总和.实验中，设定普通节点数量为50，节点度(NDC)为2～7不同的场景.通常节点度越多(即链路数量越多)，干扰越强.实验中的数据都为在10个不同拓扑结构网络上实验结果的平均值，结果如图2所示.然后，本文分析在不同节点数量下，网络传输延迟的性能.其中，传输延迟定义为数据包从源节点传输到目的节点所需的时间.设定网络中的普通节点数量分别为10、20、30、40和50个，节点度设定为3.实验结果如图3所示.

由图2可以看出，随着节点度的增加，网络吞吐量也增加，但达到一定程度后趋于稳定.这是因为节点度的增加使网络中链路数量增加，从而使节点发送数据的量增加，最终提高了网络吞吐量.但增加链路数量也增加了网络干扰，影响了吞吐量，所以最终会趋于稳定.其中，本文方案具有最高的吞吐量，例如，在节点具有4个接口时，与OLSR和HWMP相比，吞吐量分别提高了25.6%和10.7%.这是因为本文采用Selectxfor less thanxTCA构建了有效连接图，并利用MILP构建多径路由，实现了链接均衡负载.

由图3可以看出，各种协议的端到端延迟随着节点数量的增加都呈上升趋势.其中OLSR协议的延迟最高，而本文协议最低.这是因为OLSR协议使用广播机制来构建路由，这个过程会增加延时；HWMP协议中采用了先验式拓扑结构，能够有效降低数据的等待时间，然而，随着节点数量的增加，HWMP协议中的网关节点数据传输量增大，负载过重，致使延迟也急剧增加.本文协议在MILP模型中考虑了链接容量约束，有效均衡了链路负载.另外，能够在较短时间内找到最优传输路径，有效降低了传输延迟.

5 结束语

本文针对多信道多接口的WMN，提出一种基于MILP模型的WMN多径路由优化方案，利用Selectxfor less thanxTCA构建网络连接图.在考虑链路容量和节点度约束下，利用MILP模型，构建低成本的负载均衡多径路由.采用常用的图着色理论进行信道分配.与传统OLSR协议和HWMP协议相比，本文方案能够有效提高网络吞吐量，降低网络延迟，具有较高的应用价值.

[1] 邝祝芳, 陈志刚. 认知无线Mesh网络中一种有效的多目标优化频谱分配算法[J]. 中南大学学报：自然科学版, 2013, 44(6):124-129.

[2] 黄向党, 羊秋玲, 金志刚. 无线Mesh网络延迟及丢包控制机制研究[J]. 湘潭大学自然科学学报, 2013, 35(3):95-101.

[3] PENG Y, YU Y, GUO L, et al. An efficient joint channel assignment and Qos routing protocol for IEEE 802.11 multi-radio multi-channel wireless mesh networks[J]. Journal of Network and Computer Applications, 2013, 36(2): 843-857.

[4] 郭诚欣, 李陶深, 葛志辉. 基于紧密中心性的无线mesh骨干网网关部署[J]. 电信科学, 2015, 31(2): 80-85.

[5] GUESMIA M, GUEZOURI M, MBAREK N. A dynamic update of the HWMP proactive tree for IEEE 802.11s based wireless mesh networks[J]. Journal of Communications Software & Systems, 2013, 9(6): 205-211.

[6] CHAUDHRY A U, AHMAD N, HAFEZ R H. Improving throughput and fairness by improved channel assignment using topology control based on power control for multi-radio multi-channel wireless mesh networks[J]. Eurasip Journal on Wireless Communications & Networking, 2012, 32(6):701-710.

[7] 李陶深, 张宏宇, 叶进,等. 基于M/M/1的无线mesh网络网关分析模型[J]. 电信科学, 2015, 31(1): 58-64.

[8] 冯琳函, 钱志鸿, 金冬成. 增强型的无线 mesh 网络信道分配方法[J]. 通信学报, 2012, 33(10): 44-50.

[9] CHOI J, SEO H, LEE C. An integer linear programming (ILP)-based optimization for finding the optimal independent sets in wireless ad hoc networks[C]// Proceedings of the 7th International Conference on Ubiquitous Information Management and Communication. ACM, 2013:83-84.

[10] 窦宁, 万亮. 面向自然图像的年画风格化算法[J]. 计算机应用研究, 2016, 33(2): 636-640.

[11] 张丽果, 杜慧敏. 分层路由交叉互连Mesh网络的建模与仿真[J]. 系统仿真学报, 2014, 26(4): 749-754.

责任编辑：龙顺潮

Multipath Routing Optimization Scheme for Wireless Mesh Network Based on Mixed Integer Linear Programming Model

LIDai1*,HANXiao-chun2

(1.Department of Computer Science, Hanjiang Normal University, Shiyan 442000;2.School of Electronic Science and Engineering, Nanjing university, Nanjing 210046 China)

For the issues that the optimization of multipath routing in multi-radio and multi-channel wireless Mesh networks (WMN), a multipath routing optimization scheme based on mixed integer linear programming (MILP) model is proposed. Firstly, the selectxfor less thanxtopology control algorithm is used to construct the network connection graph. Then, the MILP model is used to build the link load balancing multipath routing that under considering the link capacity, node constraint and link traffic. In addition, the graph coloring theory is used to allocate channel, and finally form a complete WMN model. Experimental results show that the proposed scheme has higher network throughput and lower end to end delay.

wireless Mesh network; multipath routing; mixed integer linear programming; connection graph; load balancing

2016-03-22

湖北省教育科学“十二五”规划项目(2012B454)

李岱(1972-)，男，湖北 房县人，副教授. E-mail:lidaihjnu@126.com

TP393

A

1000-5900(2016)03-0054-05