异构协作网络中采用令牌漏桶的多接入业务分配算法

李建东，郑 杰，刘 勤，李渝舟，杨小牛

（1.西安电子科技大学综合业务网理论与关键技术国家重点实验室，710071，西安；2.中国电子科技集团公司第三十六研究所，314001，浙江嘉兴）

传统的单个无线网络（radio access network，RAN）独立地管理自身有限资源的机制，已经不能满足现在和未来无线业务的需求［1］。因此，异构无线网络的融合和协作已经成为未来无线网络的发展趋势［2-3］，同时具有接入多个网络能力的多模终端（multi-mode terminal，MMT）的出现使异构无线网络的融合逐渐成为可能。

近几年来，并行多接入作为异构无线网络融合中的重要方法之一，引起了学术界和工业界的广泛关注［4-5］。并行多接入是指终端可以同时接入多个网络，以便获得更大的带宽、吞吐量或者更小的时延。目前这方面的研究大体上可以分为2大类，第一类为研究单跳的并行多接入业务分流，如文献［6］联合分配带宽和功率，最大化异构无线网络的吞吐量；文献［7］在文献［6］的基础上，增加考虑了用户的QoS约束，进而联合分配带宽和功率最大化系统的吞吐量；文献［8］针对视频业务，利用零膨胀模型推导了两条路径并行传输的平均时延，时延抖动和时延中断概率，并提出一种基于概率的分流策略，但这类分流策略很难扩展到3个以上网络共存的异构网络中。第二类为多跳的并行多接入业务分流，如文献［9］考虑了终端接入网络能力的不同，提出了城域网和个域网协作传输的模型，利用串联的M／M／1模型建模协作的网络，合理的分配业务使传输时延最小；文献［10］考虑了实时业务的QoS要求以及网络价格的不同，从统计的角度最大化满足传输时延要求的概率。然而文献［9-10］都没有考虑业务的突发性和终端速率受限的情况，这在一定程度上会影响业务分流的性能。针对多跳并行多接入业务分流中业务突发和终端速率受限带来的网络拥塞问题，本文提出一种采用令牌漏桶的并行多接入业务分配（TATB）算法，减少了网络的阻塞，降低了系统的时延。

1 系统模型

考虑一个由无线城域网（wireless metropolitan area networks，WMAN）和无线个域网（wireless personal area network，WPAN）组成的异构协作网络场景［7］，包含有N个不同的 WMAN，以及1个由多个MMT组成的WPAN，系统结构如图1所示，其中表示在WMAN中第i个无线接入网络，表示在 WPAN中的无线接入网络，Mi表示第i个多模终端（MMT），i=1，…，N。在该系统中，假设从WMAN中有数据要传输给M1，输入的业务流可以分成多个业务子流，分别通过不同的，i∈｛1，…，N｝传输到与之关联的终端Mj，j∈｛1，…，N｝，然后经过 WPAN中的不同 MMT协作传输，分割的业务流最终到达M1，在M1进行业务子流的聚合和恢复，从而完成端到端的协作传输。假设业务分组的到达过程服从泊松分布，分组长度服从均值为L（bit）的指数分布，其到达速率为λ（注意本文没有考虑强突发性的分组到达），则多个业务子流为到达速率为λi的泊松过程，且满足=λ。

图1 异构协作网络中端到端的并行多接入系统

在WMAN和WPAN组成的异构网络协作网络传输中，由于在WPAN中终端速率受限，尤其突发业务的情况下会造成拥塞，因此，在并行多接入中需要考虑两方面的问题：每条传输路径上速率瓶颈对传输业务的影响；传输路径性能的差异对分流的影响。针对这两方面的问题，本文提出了基于令牌漏桶的业务分流方法。

2 问题描述和最优的业务分配

2.1 采用令牌漏桶的分流优化问题

考虑基于令牌漏桶的业务分流方法：令牌产生的速度（即可允许进入网络比特流的速率）为r（b／s），漏桶容量为W（bit），则传输分组的平均速率为μ=r／L，t=W／r为令牌积累的时间。假设业务到达为泊松过程，令牌漏桶系统允许排队的队长可以无限长（系统的缓存容量无限大），将令牌漏桶系统看作M／G／1／∞队列，建立一个离散时间马尔科夫链，分组经过令牌漏桶的平均时延为［11］

式中：令牌的积累时间t与个域网可以提供的传输速率有关（t≤μN+1）。

由于WMAN遵循令牌漏桶的速率控制规则，因此分组到达MMT的业务分布是不确定的。下面以i∈｛2，…，N｝为例进行分析，异构协作网络传输模型的等效分析过程如图2所示。

图2 异构协作网络传输模型的等效分析

令牌漏桶的输出由输入的业务流和服务特性决定，当队列中没有积累的分组，并且输入业务流服从泊松过程时，输出为泊松过程［12］。在可逆的开放队列中，如果每个分组进入队列不能够立即离开，则每个队列的状态是独立的［13］。影响令牌漏桶的输出流特性有2个方面：一方面是漏桶的整形特性；另一方面是阻塞率对输入流的影响，若进入第2个队列的业务阻塞率很大，则进入第2个队列业务不服从泊松分布。但是，当队列的阻塞率足够小，在第1个令牌漏桶中队列的输出仍然可以近似为泊松过程。同样，对于M／G／K／K系统，其输出过程也可以近似为泊松过程［14］。因此，本文将第1个令牌漏桶的队列看作M／G／1，当阻塞率足够小时，将第1个队列的输出过程近似为泊松过程；将第2个队列看作M／M／1，建立如下的优化问题。

若链路1中的R1可以直接连接到M1，则分组传输的平均时延为

若链路i中的Ri不能直接连接到M1，则需要Mi的协助，i∈｛2，3，…，N｝，链路i的分组传输平均时延为

引理1 式（4）优化问题是一个凸问题。

证明 约束条件式（5）为λ一个线性组合，既是凸函数也是凹函数，满足式（5）点的集合是凸集。另一个约束条件式（6）表示半空间，半空间为凸集。因此，要证明问题（P）是一个凸问题，只需证明目标函数式（4）为凸函数。为了便于证明，将目标函数写成如下的形式

2.2 基于对偶分解的分布式算法

将式（4）优化问题转化为拉格朗日对偶函数

式中：v∈R为约束条件式（5）的拉格朗日乘子；λ和v的最小值可表示为

由于原问题是一个凸问题（见引理1），易验证Slater条件成立，强对偶存在，原问题的最优值与对偶问题的最优解相等［15］，从而可通过求解对偶问题求解原问题。

为求解对偶问题式（9），先求解式（8）。因为变量λ1，λ2，…，λN间相互独立没有耦合，式（8）可以分解成N个子问题。

（1）当i=1时，链路1的优化问题为

（2）当i＞1时，链路i的优化问题为

对于给定的v，在单个网络i，用牛顿投影法［13］迭代得到最优的分流λi，由式（11）和式（12）得到牛顿投影法的第k次迭代表达式

对于式（13）的收敛性和收敛速度的证明，以及迭代次数的分析如下。

（1）收敛性证明：该牛顿投影迭代法可以收敛到最优解。

如果f′（a）≠0，f（a）=0，则d′（a）≤0，牛顿投影法是局部收敛的。若f″（λi）＞0，则牛顿法收敛到极小值点。由于该优化问题是一个凸规划的问题，所以局部极小值即为全局最小值。

（2）收敛速度证明：该迭代法为二阶收敛［16］。证明 由于f″（λij）＞0，则d″（a）≠0，因此迭代法λij=d（λij）是二阶的，即是二次收敛的。

（3）迭代次数分析：迭代的次数与终止的精度有关，本文将通过仿真来分析（见第3部分）。

对于求解问题式（9）得到的速率λi，采用梯度投影法求解对偶问题式（10），得到乘子v为

式中：ε＞0表示固定步长因子；k为迭代次数。

2.3 TATB算法设计

本文提出的TATB算法通过分布式方式实现，具体步骤如下：

（1）获得每个网络的参数μi、ti；

（2）令k=0，设置终止精度δ，初始化v0；

（6）k=k+1，返回步骤（3）。

3 数值分析

为了验证本文提出的算法的有效性，采用MATLABR2009b进行仿真。本文的网络场景和参数如表1所示。

表1 网络场景及相应参数设置

本文采用以下3种算法与本文TATB算法进行对比：①基于路径等分配的业务分配算法（即在不同的网络中分配相等业务）；②负载均衡算法（即根据负载在不同网络中的比例来进行业务分配，λi=，（1≤i≤N））；③non-TATB算法［9］（即不考虑令牌漏桶的分流算法）。

图3 几种算法的时延性能比较及受令牌积累时间的影响

图3 a显示了随着到达率的不同各分流算法的时延性能。从图3a中可以看出，不同算法的传输时延随着业务到达率的增加而增大，本文TATB算法可以获得最小传输时延，与non-TATB算法、负载均衡算法和基于路径等分配算法相比，在轻负载时可以获得71.67%、72.94%、74.42%的时延性能增益；在重负载时可以获得70.65%、72.10%、83.49%的时延性能增益。这是因为，本文提出的基于令牌漏桶分流算法平滑了业务的突发性，降低了终端速率受限引起的网络拥塞。

图3b显示了令牌积累时间t取不同值对本文算法的性能影响。从图3b中可以看出，当令牌积累时间不变时，本文算法可以获得最小的时延。当令牌积累时间变为原来的1／2以及2倍时，TATB算法的时延平均增加了17.9%和7.5%。这是因为τ随t的增加而减少，随着t的增加，本文算法的时延减少，但随着t的进一步增加，由于协作传输中受到第2跳终端速率的限制，导致时延反而增大。

图4给出了精度在σ=1×10-5时TATB算法的迭代次数。在负载较轻（λ=1）时，15次迭代可以收敛。在负载较重（λ=4）时，20次迭代可以收敛结果。因为牛顿法收敛的速度与初始值选取有关，当负载较重时，初始值离最优值较远，需要多次迭代才能得到最优解。

图4 本文TATB算法的收敛性分析（σ=1×10-5）

4 结 论

本文建立了一种基于令牌漏桶的动态业务分流模型，通过在城域网中引入令牌漏桶平滑业务的突发性，并减小传输时延，提出一种分布式的业务分流算法。该分布式算法将业务分配问题放在各个网络独立求解，没有中心资源管理，易应用于不同网络由不同运营商管理的场景。此外，本文算法由于采用牛顿投影法，因而迭代次数少，信令开销小。未来需要考虑多终端对多终端的场景，进一步研究存在干扰时的多接入业务分配算法。

［1］ GOZALVEZ J.Heterogeneous wireless networks［J］.IEEE Vehicular Technology Magazine，2011，6（2）：9-13.

［2］ PIAMRAT K，KSENTINI A，BONNIN J，et al.Radio resource management in emerging heterogeneous wireless networks ［J］.Computer Communications，2011，34（9）：1066-1076.

［3］ 宋婧，丛梨，葛建华，等.双层网络中一种协作博弈的动态资源分配方法 ［J］.西安交通大学学报，2012，46（10）：89-94.

SONG Jing，CONG Li，GE Jianhua，et al.A dynamic resource allocation approach using cooperative game theory for two-tie networks ［J］.Journal of Xi’an Jiaotong University，2012，46（12）：89-94.

［4］ 李建东，姜建，刘鑫一.采用时延限制和资源预测的异构无线网络选择策略 ［J］.西安交通大学学报，2014，48（2）：74-79.

LI Jiandong，JIANG Jian，LIU Xinyi.A network selection policy under delay constraint and resource prediction in integrated wireless systems［J］.Journal of Xi’an Jiaotong University，2014，48（2）：74-79.

［5］ PENG X，PENG G，JAE H P，et al.Radio resource management with proportional rate constraint in the heterogeneous networks ［J］.IEEE Transactions on Wireless Communications，2012，11（3）：1066-1075.

［6］ YONGHOON C，HOON K，SANGWOOK H，et al.Joint resource allocation for parallel multi-radio access in heterogeneous wireless networks ［J］.IEEE Transactions on Wireless Communications，2010，9（11）：3324-3329.

［7］ MIAO Jie，ZHENG Hu，WANG Canru，et al.Joint power and bandwidth allocation algorithm with QoS support in heterogeneous wireless networks［J］.IEEE Communications Letters，2012，16（4）：479-481.

［8］ WEI Song，ZHUANG Weihua.Performance analysis of probabilistic multipath transmission of video streaming traffic over multi-radio wireless devices［J］.IEEE Transactions on Wireless Communications，2012，4（11）：1-11.

［9］ SUN Lei，TIAN Hui，SUN Qiaoyun，et al.Traffic allocation scheme with cooperation of WWAN and WPAN ［J］.IEEE Communications Letters，2010，14（6）：551-553.

［10］WANG Canru，TIAN Hui，MIAO Jie.Dynamic traffic allocation scheme for optimum distribution in heterogeneous networks ［C］∥ IEEE Vehicular Technology Conference.Piscataway， NJ， USA：IEEE，2011：1-5.

［11］李建东.信息网络理论基础 ［M］.西安：西安电子科技大学出版社，2001.

［12］DEVECIANA G.Leaky buckets and optimal self-tuning rate control ［C］∥ Proceedings of IEEE Global Telecommunication Conference.Piscataway， NJ，USA：IEEE，2011：1-5.

［13］KELLY F P.Reversibility and stochastic networks［M］.New York，USA：Wiley，1979.

［14］TENG J.A study of optical burst switched networks with the jumpstart just-in-time signaling protocol［D］.Raleigh，NC，USA：North Carolina State University，2004.

［15］BOYD S，VANDENBERGHE L.Convex optimization［M］.Cambridge，UK：Cambridge University Press，2004.

［16］KENDALL A，HAN Weimin.Elementary numerical analysis［M］.New York，USA：Wiley，2004：72-120.

［本刊相关文献链接］

李建东，姜建，刘鑫一.采用时延限制和资源预测的异构无线网 络 选 择 策 略.2014，48（2）：74-79.［doi：10.7652／xjtuxb 201402013］

卢冀，肖嵩，吴成柯.无线网络中应用机会式网络编码的广播重传方法.2011，45（2）：68-72.［doi：10.7652／xjtuxb201102 014］

司江勃，李赞，刘增基.无线协作网络中存在干扰时的中继选择协议.2010，44（2）：72-76.［doi：10.7652／xjtuxb201002015］

吕政，余志军，刘海涛.协作通信中联合信道-网络编码的性能分 析 与 资 源 分 配.2012，46（4）：83-87.［doi：10.7652／xjtuxb 201204014］

魏全瑞，刘俊，韩九强.改进的无线传感器网络无偏距离估计与节点 定 位 算 法.2014，48（6）：1-6.［doi：10.7652／xjtuxb 201406001］