異構協(xié)作網(wǎng)絡中采用令牌漏桶的多接入業(yè)務分配算法

李建東，鄭 杰，劉 勤，李渝舟，楊小牛

（1.西安電子科技大學綜合業(yè)務網(wǎng)理論與關鍵技術國家重點實驗室，710071，西安；2.中國電子科技集團公司第三十六研究所，314001，浙江嘉興）

傳統(tǒng)的單個無線網(wǎng)絡（radio access network，RAN）獨立地管理自身有限資源的機制，已經(jīng)不能滿足現(xiàn)在和未來無線業(yè)務的需求［1］。因此，異構無線網(wǎng)絡的融合和協(xié)作已經(jīng)成為未來無線網(wǎng)絡的發(fā)展趨勢［2-3］，同時具有接入多個網(wǎng)絡能力的多模終端（multi-mode terminal，MMT）的出現(xiàn)使異構無線網(wǎng)絡的融合逐漸成為可能。

近幾年來，并行多接入作為異構無線網(wǎng)絡融合中的重要方法之一，引起了學術界和工業(yè)界的廣泛關注［4-5］。并行多接入是指終端可以同時接入多個網(wǎng)絡，以便獲得更大的帶寬、吞吐量或者更小的時延。目前這方面的研究大體上可以分為2大類，第一類為研究單跳的并行多接入業(yè)務分流，如文獻［6］聯(lián)合分配帶寬和功率，最大化異構無線網(wǎng)絡的吞吐量；文獻［7］在文獻［6］的基礎上，增加考慮了用戶的QoS約束，進而聯(lián)合分配帶寬和功率最大化系統(tǒng)的吞吐量；文獻［8］針對視頻業(yè)務，利用零膨脹模型推導了兩條路徑并行傳輸?shù)钠骄鶗r延，時延抖動和時延中斷概率，并提出一種基于概率的分流策略，但這類分流策略很難擴展到3個以上網(wǎng)絡共存的異構網(wǎng)絡中。第二類為多跳的并行多接入業(yè)務分流，如文獻［9］考慮了終端接入網(wǎng)絡能力的不同，提出了城域網(wǎng)和個域網(wǎng)協(xié)作傳輸?shù)哪Ｐ停么?lián)的M／M／1模型建模協(xié)作的網(wǎng)絡，合理的分配業(yè)務使傳輸時延最小；文獻［10］考慮了實時業(yè)務的QoS要求以及網(wǎng)絡價格的不同，從統(tǒng)計的角度最大化滿足傳輸時延要求的概率。然而文獻［9-10］都沒有考慮業(yè)務的突發(fā)性和終端速率受限的情況，這在一定程度上會影響業(yè)務分流的性能。針對多跳并行多接入業(yè)務分流中業(yè)務突發(fā)和終端速率受限帶來的網(wǎng)絡擁塞問題，本文提出一種采用令牌漏桶的并行多接入業(yè)務分配（TATB）算法，減少了網(wǎng)絡的阻塞，降低了系統(tǒng)的時延。

1 系統(tǒng)模型

考慮一個由無線城域網(wǎng)（wireless metropolitan area networks，WMAN）和無線個域網(wǎng)（wireless personal area network，WPAN）組成的異構協(xié)作網(wǎng)絡場景［7］，包含有N個不同的 WMAN，以及1個由多個MMT組成的WPAN，系統(tǒng)結構如圖1所示，其中表示在WMAN中第i個無線接入網(wǎng)絡，表示在 WPAN中的無線接入網(wǎng)絡，Mi表示第i個多模終端（MMT），i=1，…，N。在該系統(tǒng)中，假設從WMAN中有數(shù)據(jù)要傳輸給M1，輸入的業(yè)務流可以分成多個業(yè)務子流，分別通過不同的，i∈｛1，…，N｝傳輸?shù)脚c之關聯(lián)的終端Mj，j∈｛1，…，N｝，然后經(jīng)過 WPAN中的不同 MMT協(xié)作傳輸，分割的業(yè)務流最終到達M1，在M1進行業(yè)務子流的聚合和恢復，從而完成端到端的協(xié)作傳輸。假設業(yè)務分組的到達過程服從泊松分布，分組長度服從均值為L（bit）的指數(shù)分布，其到達速率為λ（注意本文沒有考慮強突發(fā)性的分組到達），則多個業(yè)務子流為到達速率為λi的泊松過程，且滿足=λ。

圖1 異構協(xié)作網(wǎng)絡中端到端的并行多接入系統(tǒng)

在WMAN和WPAN組成的異構網(wǎng)絡協(xié)作網(wǎng)絡傳輸中，由于在WPAN中終端速率受限，尤其突發(fā)業(yè)務的情況下會造成擁塞，因此，在并行多接入中需要考慮兩方面的問題：每條傳輸路徑上速率瓶頸對傳輸業(yè)務的影響；傳輸路徑性能的差異對分流的影響。針對這兩方面的問題，本文提出了基于令牌漏桶的業(yè)務分流方法。

2 問題描述和最優(yōu)的業(yè)務分配

2.1 采用令牌漏桶的分流優(yōu)化問題

考慮基于令牌漏桶的業(yè)務分流方法：令牌產生的速度（即可允許進入網(wǎng)絡比特流的速率）為r（b／s），漏桶容量為W（bit），則傳輸分組的平均速率為μ=r／L，t=W／r為令牌積累的時間。假設業(yè)務到達為泊松過程，令牌漏桶系統(tǒng)允許排隊的隊長可以無限長（系統(tǒng)的緩存容量無限大），將令牌漏桶系統(tǒng)看作M／G／1／∞隊列，建立一個離散時間馬爾科夫鏈，分組經(jīng)過令牌漏桶的平均時延為［11］

式中：令牌的積累時間t與個域網(wǎng)可以提供的傳輸速率有關（t≤μN+1）。

由于WMAN遵循令牌漏桶的速率控制規(guī)則，因此分組到達MMT的業(yè)務分布是不確定的。下面以i∈｛2，…，N｝為例進行分析，異構協(xié)作網(wǎng)絡傳輸模型的等效分析過程如圖2所示。

圖2 異構協(xié)作網(wǎng)絡傳輸模型的等效分析

令牌漏桶的輸出由輸入的業(yè)務流和服務特性決定，當隊列中沒有積累的分組，并且輸入業(yè)務流服從泊松過程時，輸出為泊松過程［12］。在可逆的開放隊列中，如果每個分組進入隊列不能夠立即離開，則每個隊列的狀態(tài)是獨立的［13］。影響令牌漏桶的輸出流特性有2個方面：一方面是漏桶的整形特性；另一方面是阻塞率對輸入流的影響，若進入第2個隊列的業(yè)務阻塞率很大，則進入第2個隊列業(yè)務不服從泊松分布。但是，當隊列的阻塞率足夠小，在第1個令牌漏桶中隊列的輸出仍然可以近似為泊松過程。同樣，對于M／G／K／K系統(tǒng)，其輸出過程也可以近似為泊松過程［14］。因此，本文將第1個令牌漏桶的隊列看作M／G／1，當阻塞率足夠小時，將第1個隊列的輸出過程近似為泊松過程；將第2個隊列看作M／M／1，建立如下的優(yōu)化問題。

若鏈路1中的R1可以直接連接到M1，則分組傳輸?shù)钠骄鶗r延為

若鏈路i中的Ri不能直接連接到M1，則需要Mi的協(xié)助，i∈｛2，3，…，N｝，鏈路i的分組傳輸平均時延為

引理1 式（4）優(yōu)化問題是一個凸問題。

證明 約束條件式（5）為λ一個線性組合，既是凸函數(shù)也是凹函數(shù)，滿足式（5）點的集合是凸集。另一個約束條件式（6）表示半空間，半空間為凸集。因此，要證明問題（P）是一個凸問題，只需證明目標函數(shù)式（4）為凸函數(shù)。為了便于證明，將目標函數(shù)寫成如下的形式

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

將式（4）優(yōu)化問題轉化為拉格朗日對偶函數(shù)

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

由于原問題是一個凸問題（見引理1），易驗證Slater條件成立，強對偶存在，原問題的最優(yōu)值與對偶問題的最優(yōu)解相等［15］，從而可通過求解對偶問題求解原問題。

為求解對偶問題式（9），先求解式（8）。因為變量λ1，λ2，…，λN間相互獨立沒有耦合，式（8）可以分解成N個子問題。

（1）當i=1時，鏈路1的優(yōu)化問題為

（2）當i＞1時，鏈路i的優(yōu)化問題為

對于給定的v，在單個網(wǎng)絡i，用牛頓投影法［13］迭代得到最優(yōu)的分流λi，由式（11）和式（12）得到牛頓投影法的第k次迭代表達式

對于式（13）的收斂性和收斂速度的證明，以及迭代次數(shù)的分析如下。

（1）收斂性證明：該牛頓投影迭代法可以收斂到最優(yōu)解。

如果f′（a）≠0，f（a）=0，則d′（a）≤0，牛頓投影法是局部收斂的。若f″（λi）＞0，則牛頓法收斂到極小值點。由于該優(yōu)化問題是一個凸規(guī)劃的問題，所以局部極小值即為全局最小值。

（2）收斂速度證明：該迭代法為二階收斂［16］。證明 由于f″（λij）＞0，則d″（a）≠0，因此迭代法λij=d（λij）是二階的，即是二次收斂的。

（3）迭代次數(shù)分析：迭代的次數(shù)與終止的精度有關，本文將通過仿真來分析（見第3部分）。

對于求解問題式（9）得到的速率λi，采用梯度投影法求解對偶問題式（10），得到乘子v為

式中：ε＞0表示固定步長因子；k為迭代次數(shù)。

2.3 TATB算法設計

本文提出的TATB算法通過分布式方式實現(xiàn)，具體步驟如下：

（1）獲得每個網(wǎng)絡的參數(shù)μi、ti；

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

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

3 數(shù)值分析

為了驗證本文提出的算法的有效性，采用MATLABR2009b進行仿真。本文的網(wǎng)絡場景和參數(shù)如表1所示。

表1 網(wǎng)絡場景及相應參數(shù)設置

本文采用以下3種算法與本文TATB算法進行對比：①基于路徑等分配的業(yè)務分配算法（即在不同的網(wǎng)絡中分配相等業(yè)務）；②負載均衡算法（即根據(jù)負載在不同網(wǎng)絡中的比例來進行業(yè)務分配，λi=，（1≤i≤N））；③non-TATB算法［9］（即不考慮令牌漏桶的分流算法）。

圖3 幾種算法的時延性能比較及受令牌積累時間的影響

圖3 a顯示了隨著到達率的不同各分流算法的時延性能。從圖3a中可以看出，不同算法的傳輸時延隨著業(yè)務到達率的增加而增大，本文TATB算法可以獲得最小傳輸時延，與non-TATB算法、負載均衡算法和基于路徑等分配算法相比，在輕負載時可以獲得71.67%、72.94%、74.42%的時延性能增益；在重負載時可以獲得70.65%、72.10%、83.49%的時延性能增益。這是因為，本文提出的基于令牌漏桶分流算法平滑了業(yè)務的突發(fā)性，降低了終端速率受限引起的網(wǎng)絡擁塞。

圖3b顯示了令牌積累時間t取不同值對本文算法的性能影響。從圖3b中可以看出，當令牌積累時間不變時，本文算法可以獲得最小的時延。當令牌積累時間變?yōu)樵瓉淼?／2以及2倍時，TATB算法的時延平均增加了17.9%和7.5%。這是因為τ隨t的增加而減少，隨著t的增加，本文算法的時延減少，但隨著t的進一步增加，由于協(xié)作傳輸中受到第2跳終端速率的限制，導致時延反而增大。

圖4給出了精度在σ=1×10-5時TATB算法的迭代次數(shù)。在負載較輕（λ=1）時，15次迭代可以收斂。在負載較重（λ=4）時，20次迭代可以收斂結果。因為牛頓法收斂的速度與初始值選取有關，當負載較重時，初始值離最優(yōu)值較遠，需要多次迭代才能得到最優(yōu)解。

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

4 結 論

本文建立了一種基于令牌漏桶的動態(tài)業(yè)務分流模型，通過在城域網(wǎng)中引入令牌漏桶平滑業(yè)務的突發(fā)性，并減小傳輸時延，提出一種分布式的業(yè)務分流算法。該分布式算法將業(yè)務分配問題放在各個網(wǎng)絡獨立求解，沒有中心資源管理，易應用于不同網(wǎng)絡由不同運營商管理的場景。此外，本文算法由于采用牛頓投影法，因而迭代次數(shù)少，信令開銷小。未來需要考慮多終端對多終端的場景，進一步研究存在干擾時的多接入業(yè)務分配算法。

［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］ 宋婧，叢梨，葛建華，等.雙層網(wǎng)絡中一種協(xié)作博弈的動態(tài)資源分配方法 ［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］ 李建東，姜建，劉鑫一.采用時延限制和資源預測的異構無線網(wǎng)絡選擇策略 ［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］李建東.信息網(wǎng)絡理論基礎 ［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.

［本刊相關文獻鏈接］

李建東，姜建，劉鑫一.采用時延限制和資源預測的異構無線網(wǎng) 絡 選 擇 策 略.2014，48（2）：74-79.［doi：10.7652／xjtuxb 201402013］

盧冀，肖嵩，吳成柯.無線網(wǎng)絡中應用機會式網(wǎng)絡編碼的廣播重傳方法.2011，45（2）：68-72.［doi：10.7652／xjtuxb201102 014］

司江勃，李贊，劉增基.無線協(xié)作網(wǎng)絡中存在干擾時的中繼選擇協(xié)議.2010，44（2）：72-76.［doi：10.7652／xjtuxb201002015］

呂政，余志軍，劉海濤.協(xié)作通信中聯(lián)合信道-網(wǎng)絡編碼的性能分 析 與 資 源 分 配.2012，46（4）：83-87.［doi：10.7652／xjtuxb 201204014］

魏全瑞，劉俊，韓九強.改進的無線傳感器網(wǎng)絡無偏距離估計與節(jié)點 定 位 算 法.2014，48（6）：1-6.［doi：10.7652／xjtuxb 201406001］