多射频无线mesh网中的联合协作路由与信道分配算法

乔　宏,张大方,谢　鲲,何施茗,张　继

(1.　湖南大学信息科学与工程学院,湖南长沙410082;2.长沙理工大学计算机与通信学院,湖南长沙410014)



多射频无线mesh网中的联合协作路由与信道分配算法

乔宏1,张大方1,谢鲲1,何施茗2,张继1

(1.湖南大学信息科学与工程学院,湖南长沙410082;2.长沙理工大学计算机与通信学院,湖南长沙410014)

现有的协作路由算法没有考虑多射频无线mesh网中的信道分配问题.为了给多并发业务流提供更优质的网络服务,本文结合多射频多信道技术和协作通信技术来降低同信道干扰并获得协作分集增益.基于协作通信模块虚拟化的方法,本文将联合协作路由和信道分配问题简化为联合直接路由和信道分配问题,将其建模为一个混合整数线性规划问题,并证明该问题为NP-hard问题.为了解决该问题,提出了一种宽松的联合协作路由选择和信道分配算法(Loose Joint Cooperative Routing and Channel Assignment algorithm,L-JCRCA).仿真实验结果表明,L-JCRCA可以有效提升网络整体吞吐量.

无线mesh网;协作路由;信道分配

1　引言

作为一种克服信道衰落的有效方法,协作通信技术通过将多用户环境下的单天线用户组成虚拟的MIMO (Multiple-Input Multiple-Output)系统来取得空间分集增益.协作路由则是将物理层协作通信技术和网络层路由选择结合起来的跨层路由方案,它通过选择合适的协作中继结点参与路由中的某一跳或某几跳传输,提高无线传输的容量或降低传输的能耗,为无线用户提供更好的网络服务.

相关的研究表明,相对于传统路由,协作路由在增强无线网络性能方面具有诸多优势.但是,这些研究大多数是在没有考虑无线传输干扰下获得.实际上,由于信道竞争,无线网络存在的同信道干扰会造成数据的冲突和重传,严重影响网络性能.由于协作结点的参与,协作通信在带来分集增益的同时会增加额外的同信道干扰,导致了现有的协作路由算法很难在多跳无线网络中得到良好性能[1].而多射频多信道技术可以降低同信道干扰,将两种技术相结合可以在充分利用协作通信分集增益的同时,降低无线传输的同信道干扰,有效提升网络整体吞吐量.

而对于多射频无线mesh网络中的协作路由,需要同时考虑协作路由的选择和信道分配问题.现有的协作路由算法没有考虑结点射频和信道数量限制下的信道分配问题[2～5],无法充分利用多射频多信道的优势,而已有的信道分配算法主要是针对直接传输网络[6,7],没有考虑协作传输的特性,无法直接扩展到协作传输网络.因此,为了给业务流提供更优质的网络服务,本文结合多射频多信道技术和协作通信技术来降低同信道干扰并获得协作分集增益.针对协作通信多对一的传输特性,本文提出了一种基于协作通信模块虚拟化的方法,在此基础上将联合协作路由和信道分配问题JCRCA(Joint Cooperative Routing and Channel Assignment)简化为联合直接路由和信道分配问题,同时将该问题建模成一个混合整数线性规划问题,并证明该问题是一个NP-hard问题.为了解决该问题,本文进一步提出了一种宽松的联合协作路由选择和信道分配算法L-JCRCA(Loose Joint Cooperative Routing and Channel Assignment algorithm).实验结果表明,L-JCRCA可以有效提升网络总吞吐量.

2　联合协作路由和信道分配问题

多射频无线mesh网中联合协作路由和信道分配问题是如何为每条业务流确定最优的协作路由和信道分配策略.如图1,带箭头的线段组成的路径表示业务流使用的转发路径,线段上的数字表示为链路分配的正交信道.

然而,现有的协作路由没有考虑多射频无线mesh网中的信道分配问题,而已有的信道分配方法主要是针对直接传输网络,没有考虑协作传输的特性,无法直接扩展到协作传输网络.此外,在多射频多信道网络中,联合直接路由和信道分配问题已是一个NP-hard问题,如果再将协作结点的分配加入进去,问题将变得更为复杂.

本节针对协作通信多对一的传输特性,提出了一种协作通信模块虚拟化方法,通过为每个协作通信模块加入相应的虚拟结点和虚拟链路,构建新的基于协作传输的网络拓扑图,并在此基础上将联合协作路由和信道分配问题简化为联合直接路由和信道分配问题.同时,在路由约束和信道资源约束的条件下,将该问题建模成一个混合整数线性规划问题.

2.1协作通信模块虚拟化

在协作路由中,每个通信模块是由三个相互连通的结点组成,每条业务流会使用一个或多个协作通信模块来传输数据.一个协作通信模块在路由过程中可能发生的协作传输最多有三种.如图2(a),A,B,C三个结点可以组成一个协作通信模块,可能发生的协作传输有(A,B)->C,(A,C)->B以及(B,C)->A,为了将这些协作传输链路清晰地表示出来,我们提出一种协作通信模块虚拟化的方法来构建新的基于协作传输的网络拓扑图.如图2(b),为A,B,C组成协作通信模块增加(A,B),(A,C),(B,C)三个虚拟结点,(A,B)->C,(A,C)->B,(B,C)->A三条协作链路,以及A->(A,B),B->(A,B),B->(B,C),C->(B,C),A->(A,C),C->(A,C)六条超级链路.之所以称其它六条边为超级链路,是因为在协作传输中,这些链路的发送端和接收端可以看作是在同一时刻收到信号,它们的MAC (Media Access Control)层传输速率趋向于无穷大.为网络中的每个可能的协作通信模块增加虚拟结点和虚拟链路后,就可以构建新的基于协作传输的网络拓扑图.在此基础上,我们就可以按照选择直接路由的方式来寻找协作路由,从而将联合协作路由和信道分配的问题简化为联合传统路由和信道分配问题.

2.2问题形式化描述

我们用G(V,E)表示一个无线mesh网拓扑图,V表示结点集合,E表示链路集合;用C表示正交信道集合;用F表示业务流集合;用H(u)表示结点u∈V配置的射频数量.利用2.1提出的协作通信模块虚拟化方法,将相应的虚拟结点和虚拟链路加入到拓扑图中后,构建新的基于协作传输的网络拓扑图G(V′,E′),V′=V∪Vs,E′=E∪Es,其中,Vs表示虚拟结点集合,Es表示虚拟链路集合.

在对JCRCA问题建模时,必须满足以下路由约束和信道资源约束条件.

(1)业务流必须遵守流守衡定律.

(1)

其中,a(u,v,k,c)表示链路(u,v)在信道c上传输流k的速率,s(k)表示业务流k的源结点,d(k)表示业务流k的目的结点,r(k)表示业务流最终的转发速率.该式表示业务流的源结点只有出境流量,目的结点只有入境流量,而在其它中间结点,入境流量必须等于出境流量.

(2)链路传输速率必须满足同信道干扰限制,即链路(u,v)和其干扰范围内链路的使用率之和不超过1.

∀c∈C,∀(u,v)∈E′

(2)

I(u,v)表示链路(u,v)干扰范围内的链路集合,b(u,v)表示链路的传输速率,可以根据文献[8]提出的AF-Rake方法计算得到;p(u,v)表示链路的传输成功率,在本文中每条链路的传递成功率是恒定的.

(3)只有为链路(u,v)分配了信道c,(u,v)才能使用信道c传输数据.

(3)

L(u,v,c)表示链路(u,v)是否分配了信道c,L(u,v,c)=1表示链路(u,v)可以使用信道c,否则L(u,v,c)=0.

(4)如果链路(u,v)分配了信道c,则u和v的射频都需要分配信道c.

N(u,c)≥L(u,v,c),∀u∈V′,∀c∈C

(4)

N(v,c)≥L(u,v,c),∀v∈V′,∀c∈C

(5)

(6)

N(u,c)表示结点u∈V是否分配了信道c,如果结点u分配了信道c,N(u,c)=1,否则N(u,c)=0;

(5)当虚拟结点us的射频分配了信道c时,它的组成结点的射频也必须分配信道c.

N(u,c)≥N(us,c),∀u∈M(us),∀c∈C

(7)

M(us)表示虚拟结点us的组成结点集合.

(6)u分配信道的数量要不大于u所配置的射频数量.

(8)

(9)

在给出约束条件和目标函数后,联合协作路由和信道分配问题可以形式化表示如下:

(10)

s.t.式(1),(2),(3),(4),(5),(6),(7),(8)

定理1公式(10)所定义的联合协作路由和信道分配问题是一个NP-hard问题.

证明我们通过将式(10)所定义的联合协作路由和信道分配问题转化联合直接路由和信道分配问题来进行证明.

给定一个协作传输网络图G=(V,E),通过2.1提出的协作模块虚拟化的方法,为网络中的每个可能的协作通信模块增加虚拟结点和虚拟链路,就可将协作传输网络重构成直接传输网络G′=(V′,E′),联合协作路由和信道分配问题就简化成联合直接路由和信道分配问题.而文献[9]将联合直接路由和信道问题转换成一个精确覆盖问题,并证明了其是一个NP-hard问题,因此,联合协作路由和信道分配是一个NP-hard问题.

所以,联合协作路由和信道分配问题JCRCA的计算复杂度是指数级.而为了在多项式时间内确定合理的协作路由和信道分配策略,我们进一步提出了一种宽松的联合协作路由和信道分配算法L-JCRCA.

3　宽松的联合协作路由和信道分配算法

L-JCRCA的基本思想是首先将JCRCA的混合整数线性规划宽松为普通线性规划,然后对其最优的信道分配策略进行局部调整,使得所有结点分配到的信道数量都满足射频数量的限制条件的同时最大化网络吞吐量.

3.1宽松的联合协作路由和信道分配策略

首先,将JCRCA宽松为普通线性规划.为了公平分配网络资源,目标函数式(9)保持不变.此外,流守恒定律式(1)必须得到满足,链路传输速率必须遵守同信道干扰限制式(2),发生的变化主要是对结点射频数量限制条件进行了宽松.

将传输的时间延长至T个时槽,可以得到

≤H(v),∀v∈E′

(11)

如果业务流传输长期处于稳定状态,式(11)可以转化成:

(12)

宽松后的线性规划问题为:

s.t.式 (1),(2),(12)

(13)

通过广播的方式,每个结点可以获取整个网路的拓扑状态信息,并在此基础上为业务流选择协作传输路由和为链路分配信道.具体而言,如果a(u,v,k,c)>0,就代表链路(u,v)使用信道c为传输流k的数据.因此,通过a(u,v,k,c)的解就可以得到每条业务流的传输链路以及使用的正交信道,从而确定业务流的协作路由和信道分配方案.

但射频限制条件式(12)并不是严格约束,可能会导致有些链路被分配的信道数量超过其可使用的射频数量.因此,需要对式(12)确定的信道分配方案进行局部调整,使得所有链路被分配的信道数量符合射频数量的限制要求.

此外,由于没有严格的射频数量限制的约束条件,式(13)比JCRCA的约束更加宽松,其确定的协作路由和信道分配方案的网络吞吐量可以看作是JCRCA的上界(UP-JCRCA).

3.2信道分配策略调整

信道分配策略的调整主要是对超过结点射频数量的正交信道进行合并.如图3(a),u总共分配了1,2,3三个信道,而只配置了两个射频.因此,需要对它们的信道进行调整,调整的结果必须保证每个结点发出链路使用信道的总数量不超过结点配置的射频数量.

用U(u)表示从u发出的链路集合,假设我们选择将U(u)中使用信道3的链路的信道变成2,链路(u,a)的的工作信道由1和3变为1和2,链路(u,d)的工作信道将由3变为2.这时,结点u所发出的链路已经满足射频数量约束条件.同时,为了避免由此引起其它结点违反射频数量约束条件,发生改变的链路的另一端结点所发出的链路也需要发生同样的变化,例如,链路(a,v)的工作信道将变为1和2,链路(d,v)的工作信道会变为1和2,如图3(b).最终所有的结点分配的信道数量都满足了射频数量的约束条件.当网络结点和信道数量较多时,可能需要通过多次这样的调整才能完全满足射频数量的限制要求.为了保证虚拟结点和其组成的普通结点的信道分配保持同步,每当虚拟结点的信道发生合并时,其组成的普通结点的信道也要相应地进行类似的调整,反之亦然.

具体的调整过程如下:

步骤1选择出境速率最大并且信道数量超过射频数量的结点u.

步骤2从u的信道列表中,选择两个信道c1,c2进行合并.用ϖ(u,c)表示Ec(u)中的链路在信道c上的使用率之和,即:

步骤3如果网络中还有结点的信道数量超过射频数量,重复步骤1、步骤2直至所有结点的信道数量符合限制要求.

最后,结合3.1和3.2描述的方法,我们确定最终的联合协作路由和信道分配算法步骤如下:

步骤1根据网络结点的广播信息,获取整个网络的原始拓扑结构和链路状态信息.

步骤2根据2.1的方法构建新的基于协作传输的网络拓扑结构.

步骤3在新的网络拓扑结构基础上,根据3.1的方法进行求解,初步确定业务流的协作传输路径和传输路径上链路的工作信道.

步骤4利用3.2的方法对步骤3的结果进行局部的信道调整,使得所有的结点分配到的信道数量都不超过其配置的射频数量,并为业务流确定最终的协作路由和信道分配方案.

4　实验

我们的实验场景是在600m*600m的区域内均匀地分布若干无线结点,每个结点的固定发送功率都设置为0.22W,每个信道的带宽都为22MHZ,干扰距离和传输距离都为150m,路径衰减指数为4,结点的噪音方差都为10-10W.

为了评估算法的性能,我们将从多个角度与以下三种算法得到的吞吐量进行对比:

(1)Uni-ETT:统一信道分配+最短期望传输时间路由;

(2)Ran-ETT:随机信道分配+最短期望传输时间路由;

(3)Tra-ETT:传统信道分配[10]+最短期望传输时间路由.此外,我们还将L-JCRCA与其上界UP-JCRCA进行对比.

4.1不同数量并发流下的吞吐量比较

在网络中均匀分布25个结点,每个结点都配置了2个射频,每个射频可以工作3个正交信道上.图4(a)显示了在不同数量的并发流下,网络吞吐量的变化情况.从图中可以看出,在不同数量并发流下,L-JCRCA比Uni-ETT的吞吐量要提高55%到110%,比Ran-ETT的吞吐量要提高65%到120%,比Tra-ETT的吞吐量要提高135%到190%.提高的主要原因有两个,一是L-JCRCA采用了协作通信技术,可以有效提高单条链路的传输速率;二是L-JCRCA平衡了协作通信的分集增益和同信道干扰.图4(b) 显示了L-JCRCA与 UP-JCRCA的比较结果.从图中可以看出,L-JCRCA获得的网络吞吐量略小于UP-JCRCA,这是因为当射频数量与信道数量非常接近时,JCRCA为结点分配的信道数量基本上不会超过射频数量,需要进行信道调整的结点数量比较少,调整幅度也会比较小,所以,L-JCRCA获得的吞吐量与没有考虑射频数量限制的UP-JCRCA差距较小.

4.2不同信道数量下的吞吐量比较

在网络中均匀部署25个结点,每个结点配置2个射频,随机选择5条业务流的源结点和目的结点.图5(a)显示了在不同数量的可用正交信道下,网络吞吐量的变化情况.从图中可以看出,L-JCRCA比Uni-ETT的吞吐量要提高25%到115%,比Ran-ETT的吞吐量要提高25%到180%,比Tra-ETT的吞吐量要提高75%到280%.图5(b)显示了随着信道数量的增加,L-JCRCA与UP-JCRCA的差距越来越大,这是因为可用正交信道数量越多,UP-JCRCA分配给每个结点的信道数量也会随之增加,L-JCRCA需要对结点信道进行调整幅度也就越大,最终导致两者之间的吞吐量差距越来越大,但还是比其它三种的吞吐量要高.

4.3不同结点密度下的吞吐量比较

网络中的每个结点配置了2个射频,每个射频可以工作在3个正交信道上,随机选择5条业务流的源结点和目的结点.从图6(a)中可以看出,网络吞吐量会随着结点数量的增加而逐步增加,L-JCRCA比Uni-ETT的吞吐量要提高10%到75%,比Ran-ETT的吞吐量要提高30%到95%,比Tra-ETT的吞吐量要提高35%到210%.从图6(b)可以看出,随着结点数量的增加,L-JCRCA与UP-JCRCA差距有所增加,这是因为随着结点数量的增加,会有更多的结点参与传输,造成违反射频数量限制的结点数量有所增加,L-JCRCA进行信道调整幅度会随之增大,所以差距会有所扩大.

5　结论

为了给多条业务流提供最优的网络性能,本文同时利用多射频多信道和协作通信两者的技术优势,提出来一种协作通信模块虚拟化的方法,在此基础上将联合协作路由和信道分配问题建模为一个混合整数线性规划问题,并证明该问题为一NP-hard问题.为了解决该问题,本文进一步提出了一种宽松的联合协作路由和信道分配算法L-JCRCA.实验结果表明,L-JCRCA算法可以有效提升网络的总吞吐量.

[1]ZHANG J,ZHANG Q.Cooperative routing in multi-source multi-destination multi-Hop wireless networks [A].MERRILL D. INFOCOM 2008—The 27th Conference on Computer Communications[C].Phoenix,AZ:IEEE Press,2008.2369-2377.

[2]XU H L,HUANG L S,QIAO C M,et al.Bandwidth-power aware cooperative multipath routing for wireless multimedia sensor networks[J].IEEE Transactions on Wireless Communications,2012,11(4):1532-1543.

[3]ZHANG X Y,SHIN K.G.Cooperation without synchronization:practical cooperative relaying for wireless networks[J].IEEE Transactions on Mobile Computing,2014,14(5):937-950.

[4]XU Z C,LIANG W F.Collusion-resistant repeated double auctions for relay assignment in cooperative networks[J].IEEE Transactions on Wireless Communications,2014,13(3):1196-1207.

[5]YANG S S,SHENG Z G,MCCANN J A,et al.Distributed stochastic cross-layer optimization for multi-hop wireless networks with cooperative communications[J].IEEE Transactions on Mobile Computing,2013,13(10):2269-2282.

[6]杜振国,洪佩琳,周武旸，等.多射频无线Mesh网中的接口分域信道分配[J].电子学报,2011,39(3):723-726.

DU Z G,HONG P L,Zhou W Y,et al.ICCA:Interface-clustered channel assignment in multi-radio wireless mesh network[J].Acta Electronica Sinica,2011,39(3):723-726.(in Chinese)

[7]DHANANJAY A,ZHANG H,LI J Y,et al.Practical,distributed channel assignment and routing in dual-radio mesh Networks[J].ACM SIGCOMM Computer Communication Review,2009,39(4):99-110.

[8]ZHU Y,ZHENG H T.Understanding the impact of interference on collaborative relays[J].IEEE Transactions on Mobile Computing,2008,7(6):724-736.

[9]MUMEY B,TANG J,JUDSON I R,et al.On routing and channel selection in cognitive radio mesh networks[J].IEEE Transactions on Vehicular Technology,2012,61(9):4118-4128.

[10]SUBRAMANIAN A P,GUPTA H,DAS S R,et al.Minimum interference channel assignment in multi-radio wireless mesh networks[J].IEEE Transactions on Mobile Computing,2008,7(12):1459-1473.

乔宏男，1984年生，湖南岳阳人.湖南大学博士生，主要研究方向为无线Mesh网、协作路由.

E-mail:hqiao@ hnu.edu.cn

张大方男，1959年生，上海人，湖南大学教授、博士生导师，主要研究方向为可信系统与网络、软件容错.E-mail:dfzhang@ hnu.edu.cn

谢鲲女，1978年生，湖南黔阳人，湖南大学副教授，博士生导师，主要研究方向为分布式计算、协作路由.

E-mail: xiekun@ hnu.edu.cn

何施茗女，1986年生，湖南永州人，博士，长沙理工大学讲师，主要研究方向为机会路由．

E-mail:heshiming-hsm@163.com

张继男，1984年生，湖南长沙人，湖南大学博士生，主要研究方向为协作路由．

E-mail:tosky1984@163.com

Joint Cooperative Routing and Channel Assignment in Multi-radio Wireless Mesh Network

QIAO Hong1,ZHANG Da-fang1,XIE Kun1,HE Shi-ming2,ZHANG Ji1

(1.SchoolofInformationScienceandEngineering,HunanUniversity,Changsha,Hunan410082,China;2.SchoolofComputerandCommunicationEngineering,ChangshaUniversityofScienceandTechnology,Changsha,Hunan410004,China)

The existing cooperative routing algorithms ignored channel assignment issue in multi-radio wireless mess network.To provide high performance service for concurrent flows,this paper combined both multi-radio multi-channel technique and cooperative communication technique to reduce co-channel interference and obtain cooperative diversity gain.Based on virtualized representation method for the cooperative communication module,this paper simplified the problem of joint cooperative routing and channel assignment to the problem of joint direct routing and channel assignment,and modeled the problem as a mixed integer linear programming,and proved it NP hard.In order to solve the problem,this paper further proposed a loose joint cooperative routing and channel assignment algorithm (L-JCRCA).The simulation results show that L-JCRCA can promote network throughput effectively.

wireless mesh network;cooperative routing;channel assignment

2014-12-11;修回日期:2015-05-05;责任编辑：梅志强

国家973重点基础发展计划(No.2012CB315805);国家自然科学基金(No.61173167，No.61472130)

TP393

A

0372-2112 (2016)06-1400-06