異構協作網絡中采用令牌漏桶的多接入業務分配算法

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

（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］