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

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

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

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

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

1 系統(tǒng)模型

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.2 基于對(duì)偶分解的分布式算法

將式（4）優(yōu)化問(wèn)題轉(zhuǎn)化為拉格朗日對(duì)偶函數(shù)

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

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

為求解對(duì)偶問(wèn)題式（9），先求解式（8）。因?yàn)樽兞喀?，λ2，…，λN間相互獨(dú)立沒(méi)有耦合，式（8）可以分解成N個(gè)子問(wèn)題。

（1）當(dāng)i=1時(shí)，鏈路1的優(yōu)化問(wèn)題為

（2）當(dāng)i＞1時(shí)，鏈路i的優(yōu)化問(wèn)題為

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

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

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

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

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

（3）迭代次數(shù)分析：迭代的次數(shù)與終止的精度有關(guān)，本文將通過(guò)仿真來(lái)分析（見(jiàn)第3部分）。

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

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

2.3 TATB算法設(shè)計(jì)

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

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

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

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

3 數(shù)值分析

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

表1 網(wǎng)絡(luò)場(chǎng)景及相應(yīng)參數(shù)設(shè)置

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

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

圖3 a顯示了隨著到達(dá)率的不同各分流算法的時(shí)延性能。從圖3a中可以看出，不同算法的傳輸時(shí)延隨著業(yè)務(wù)到達(dá)率的增加而增大，本文TATB算法可以獲得最小傳輸時(shí)延，與non-TATB算法、負(fù)載均衡算法和基于路徑等分配算法相比，在輕負(fù)載時(shí)可以獲得71.67%、72.94%、74.42%的時(shí)延性能增益；在重負(fù)載時(shí)可以獲得70.65%、72.10%、83.49%的時(shí)延性能增益。這是因?yàn)椋疚奶岢龅幕诹钆坡┩胺至魉惴ㄆ交藰I(yè)務(wù)的突發(fā)性，降低了終端速率受限引起的網(wǎng)絡(luò)擁塞。

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

圖4給出了精度在σ=1×10-5時(shí)TATB算法的迭代次數(shù)。在負(fù)載較輕（λ=1）時(shí)，15次迭代可以收斂。在負(fù)載較重（λ=4）時(shí)，20次迭代可以收斂結(jié)果。因?yàn)榕ｎD法收斂的速度與初始值選取有關(guān)，當(dāng)負(fù)載較重時(shí)，初始值離最優(yōu)值較遠(yuǎn)，需要多次迭代才能得到最優(yōu)解。

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

4 結(jié) 論

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

［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)絡(luò)中一種協(xié)作博弈的動(dòng)態(tài)資源分配方法 ［J］.西安交通大學(xué)學(xué)報(bào)，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］ 李建東，姜建，劉鑫一.采用時(shí)延限制和資源預(yù)測(cè)的異構(gòu)無(wú)線網(wǎng)絡(luò)選擇策略 ［J］.西安交通大學(xué)學(xué)報(bào)，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)絡(luò)理論基礎(chǔ) ［M］.西安：西安電子科技大學(xué)出版社，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.

［本刊相關(guān)文獻(xiàn)鏈接］

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

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

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

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

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