一種采用剩余服務(wù)時(shí)間的異構(gòu)網(wǎng)絡(luò)選擇算法

杜 白，李紅艷

（西安電子科技大學(xué)綜合業(yè)務(wù)網(wǎng)理論及關(guān)鍵技術(shù)國家重點(diǎn)實(shí)驗(yàn)室，陜西西安 710071）

一種采用剩余服務(wù)時(shí)間的異構(gòu)網(wǎng)絡(luò)選擇算法

杜 白，李紅艷

（西安電子科技大學(xué)綜合業(yè)務(wù)網(wǎng)理論及關(guān)鍵技術(shù)國家重點(diǎn)實(shí)驗(yàn)室，陜西西安 710071）

針對(duì)異構(gòu)網(wǎng)絡(luò)環(huán)境中的網(wǎng)絡(luò)選擇問題，提出了使用剩余服務(wù)時(shí)間的異構(gòu)網(wǎng)絡(luò)選擇算法.大部分現(xiàn)有的工作都是在一個(gè)時(shí)刻點(diǎn)只考慮用戶或者網(wǎng)絡(luò)收益全局的最優(yōu)化，而沒有考慮最優(yōu)分配結(jié)果對(duì)后續(xù)到達(dá)業(yè)務(wù)影響的問題.剩余服務(wù)時(shí)間的概念將這個(gè)影響引入文中提出的建模中，從而得到一個(gè)在長時(shí)間尺度上更好的網(wǎng)絡(luò)選擇方案.文中使用非合作博弈對(duì)網(wǎng)絡(luò)進(jìn)行建模，并證明了文中提出的博弈模型的納什均衡點(diǎn)同時(shí)也是全局的最優(yōu)解；最后，利用李雅普諾夫理論證明了文中算法的穩(wěn)定性.仿真結(jié)果說明，剩余服務(wù)時(shí)間的引入能夠使網(wǎng)絡(luò)的性能得到改善，降低了用戶的阻塞率，提高了網(wǎng)絡(luò)總的收益.

異構(gòu)網(wǎng)絡(luò)；網(wǎng)絡(luò)選擇；非合作博弈；李雅普諾夫；剩余服務(wù)時(shí)間

近年來，新式無線網(wǎng)絡(luò)接入技術(shù)快速發(fā)展帶來了很多新問題，比如異構(gòu)環(huán)境中的網(wǎng)絡(luò)發(fā)現(xiàn)、網(wǎng)絡(luò)選擇和網(wǎng)絡(luò)切換等［1］.網(wǎng)絡(luò)選擇是其中一個(gè)關(guān)鍵性問題，直接影響整個(gè)網(wǎng)絡(luò)資源的利用率和用戶體驗(yàn)的滿意度.網(wǎng)絡(luò)選擇中，為了得到不同參數(shù)合理的權(quán)重，找到合適的折中點(diǎn)，很多數(shù)學(xué)方法，比如博弈論、多目標(biāo)優(yōu)化、效應(yīng)函數(shù)、層次分析法和模糊邏輯等被廣泛使用［2-6］.

博弈論專門用于解決博弈參與者的均衡問題，非常適用于網(wǎng)絡(luò)選擇場(chǎng)景［7-8］.文中使用非合作博弈研究新用戶到達(dá)時(shí)如何進(jìn)行博弈，使整個(gè)網(wǎng)絡(luò)的收益達(dá)到最大.目前已有的工作大多考慮在用戶到達(dá)時(shí)，如何進(jìn)行網(wǎng)絡(luò)選擇使全網(wǎng)達(dá)到最優(yōu)，而沒有考慮當(dāng)前的決策對(duì)網(wǎng)絡(luò)后續(xù)性能的影響.這種做法會(huì)導(dǎo)致網(wǎng)絡(luò)資源在長時(shí)間尺度上的分配達(dá)不到最優(yōu).筆者使用剩余服務(wù)時(shí)間的概念，將新用戶的網(wǎng)絡(luò)選擇對(duì)整個(gè)網(wǎng)絡(luò)長時(shí)間的影響引入模型中，使用李雅普諾夫穩(wěn)定理論和排隊(duì)論進(jìn)行建模，并證明在網(wǎng)絡(luò)的容量域內(nèi)，文中提出的算法具有穩(wěn)定性［9-10］.仿真的結(jié)果證明了文中算法的有效性，降低了用戶的拒接概率，減少了網(wǎng)絡(luò)中數(shù)據(jù)的隊(duì)列長度，使業(yè)務(wù)數(shù)據(jù)在整個(gè)系統(tǒng)中的分布更加均衡，提高了網(wǎng)絡(luò)業(yè)務(wù)容量.

1 系統(tǒng)的非合作博弈模型和網(wǎng)絡(luò)選擇算法

如圖1所示，異構(gòu)網(wǎng)絡(luò)的場(chǎng)景包含1個(gè)蜂窩網(wǎng)和兩個(gè)無線局域網(wǎng)（Wireless Local Area Network，WLAN），3個(gè)網(wǎng)絡(luò)重疊覆蓋.用戶在不同的區(qū)域有不同的可接入網(wǎng)絡(luò).用ui表示用戶i，Nj表示接入網(wǎng)j，其中，N1表示蜂窩網(wǎng)，N2和N3分別表示兩個(gè)WLAN網(wǎng).假設(shè)網(wǎng)絡(luò)分時(shí)隙運(yùn)行，用戶以泊松過程隨機(jī)到達(dá)整個(gè)網(wǎng)絡(luò).每個(gè)用戶需求的最小帶寬用βi表示，如果用戶獲得的帶寬小于βi，則認(rèn)為ui的滿意度為0，也就是支付函數(shù)為0，后面會(huì)給出支付函數(shù)的具體定義.

圖1　異構(gòu)網(wǎng)絡(luò)場(chǎng)景

由于不考慮切換，所以忽略網(wǎng)絡(luò)的預(yù)留帶寬，假設(shè)每個(gè)接入網(wǎng)都會(huì)把網(wǎng)內(nèi)的所有資源分配出去，也就是說，如果網(wǎng)絡(luò)中只有1個(gè)用戶，網(wǎng)絡(luò)會(huì)把所有資源都給這個(gè)用戶使用.當(dāng)有新用戶到達(dá)時(shí)，新老用戶會(huì)競(jìng)爭整個(gè)網(wǎng)絡(luò)的資源，每個(gè)用戶實(shí)際分配的帶寬用bi表示，可利用非合作博弈來對(duì)這個(gè)競(jìng)爭過程進(jìn)行建模.

現(xiàn)在進(jìn)行非合作博弈的建模:博弈參與者為新用戶和老用戶.老用戶是指已經(jīng)接入網(wǎng)絡(luò)的用戶，新用戶是指還未接入網(wǎng)絡(luò)的用戶所有的用戶用u表示

策略:老用戶讓出的帶寬，用xi表示.新用戶從老用戶手中搶到的帶寬，用αi表示.假設(shè)網(wǎng)絡(luò)中已有n個(gè)用戶｛u1，…，un｝，新到達(dá)用戶為un+1，對(duì)于老用戶，定義支付函數(shù)如下:

只要讓所有的偏導(dǎo)等于0，則可以得到如下方程組:

方程組式（3）的解就是優(yōu)化問題式（2）的最優(yōu)解.

下面介紹文中提出的博弈方案的納什均衡點(diǎn)，并證明這個(gè)納什均衡點(diǎn)同時(shí)也是式（2）的最優(yōu)解.

這里使用最佳響應(yīng)函數(shù)的方法來求納什均衡點(diǎn)［7］.具體方法為:對(duì)所有老用戶的支付函數(shù)求導(dǎo)，使其等于0，然后聯(lián)立求解.

2 剩余服務(wù)時(shí)間的引入和算法的穩(wěn)定性分析

剩余服務(wù)時(shí)間表示網(wǎng)絡(luò)隨時(shí)間的推移其忙碌情況的變化.若只看帶寬，一個(gè)網(wǎng)絡(luò)中有很多需要大帶寬的用戶，導(dǎo)致新用戶到達(dá)時(shí)，可以分出的帶寬很小.但是，這些用戶可能很快會(huì)結(jié)束業(yè)務(wù)離開網(wǎng)絡(luò).使用剩余服務(wù)時(shí)間，可以使新用戶選擇更適合的接入網(wǎng).下面給出加入剩余服務(wù)時(shí)間后的算法，并使用李雅普諾夫理論分析其穩(wěn)定性.

第1步 新用戶到達(dá)時(shí)，根據(jù)式（3）進(jìn)行博弈，得到接入每個(gè)接入網(wǎng)j能夠得到的帶寬，用Bj來表示.

第2步 得到每個(gè)接入網(wǎng)當(dāng)前時(shí)刻的剩余服務(wù)時(shí)間Tj，然后計(jì)算DiTjRj-VBj.在所有接入網(wǎng)中找出最小的一個(gè)DiTjRj-VBj進(jìn)行接入，其中，V是常數(shù)，代表帶寬的權(quán)重.文中使用帶寬進(jìn)行博弈，來獲得當(dāng)前時(shí)刻的全局最優(yōu)，所以，V取值越大，最終結(jié)果越傾向于瞬時(shí)的全局最優(yōu)；反之，則傾向于長時(shí)間尺度的優(yōu)化，而損失當(dāng)前時(shí)刻網(wǎng)絡(luò)的收益.

第3步 新用戶選擇好網(wǎng)絡(luò)后，所有用戶的帶寬按照式（3）的博弈結(jié)果進(jìn)行分配.

下面證明，當(dāng)用戶的到達(dá)速率在容量域內(nèi)時(shí)，文中提出的算法可以使整個(gè)網(wǎng)絡(luò)穩(wěn)定.

當(dāng)用戶到達(dá)時(shí)，只要自己進(jìn)行一次博弈就可以得到最終的選擇結(jié)果.下面給出具體的網(wǎng)絡(luò)選擇算法.

第1步 新用戶到達(dá)時(shí)，對(duì)所有它可以選擇的接入網(wǎng)分別按照式（3）進(jìn)行求解，得到它接入每一個(gè)可選的接入網(wǎng)可獲得的帶寬.

（1）容量域.假如存在一種網(wǎng)絡(luò)選擇策略，可使網(wǎng)絡(luò)在到達(dá)率λ的情況下穩(wěn)定，那么這個(gè)到達(dá)率λ就是在容量域內(nèi)的，所有這樣的到達(dá)率λ的集合ζ稱為網(wǎng)絡(luò)的容量域.

由于Aj（t）Rj和Td（t）都是有界的.所以

3 仿真結(jié)果

仿真的網(wǎng)絡(luò)場(chǎng)景如圖1所示.蜂窩網(wǎng)的服務(wù)速率設(shè)為10 MB/s，兩個(gè)WLAN的服務(wù)速率為54 MB/s.假設(shè)業(yè)務(wù)分為兩種，一種總數(shù)據(jù)量為2 MB到20 MB的均勻分布，另一種為50 MB到200 MB的均勻分布.這樣假設(shè)是因?yàn)楝F(xiàn)在的移動(dòng)用戶的業(yè)務(wù)需求中，很少有數(shù)據(jù)量非常大的業(yè)務(wù)，其中，比較大的在線視頻，在一種終端中觀看1 h左右的視頻，多數(shù)在200 MB以下，而用戶又很少會(huì)使用移動(dòng)終端看超過1 h以上的業(yè)務(wù).用戶需要的最小帶寬為0.5 MB到2.0 MB的均勻分布.所有的用戶按泊松過程到達(dá)整個(gè)網(wǎng)絡(luò).仿真中若不考慮剩余服務(wù)時(shí)間，就只需使用上文中的博弈結(jié)果進(jìn)行網(wǎng)絡(luò)選擇；若考慮剩余服務(wù)時(shí)間，就使用上文中提出的加入剩余服務(wù)時(shí)間的算法.

由圖2可以看出，用戶的拒絕概率隨著到達(dá)率的提高而提高，并且由于考慮了剩余服務(wù)時(shí)間后，用戶在長時(shí)間尺度上會(huì)更加均勻地分布在整個(gè)網(wǎng)絡(luò)中，從而降低了用戶被拒絕的概率.并且能夠支持更多的用戶，也就是可以服務(wù)更多的數(shù)據(jù).

圖2　用戶的拒絕概率隨到達(dá)率的變化

圖3　用戶的平均收益

4 結(jié)束語

文中提出了基于非合作博弈的異構(gòu)網(wǎng)絡(luò)選擇算法，并且證明了在文中的建模方法中，納什均衡點(diǎn)正好也就是全局的最優(yōu)點(diǎn).然后，在模型中引入了剩余服務(wù)時(shí)間的概念來研究新用戶對(duì)網(wǎng)絡(luò)后續(xù)運(yùn)行的影響，并且利用李雅普諾夫理論證明了在整個(gè)容量域內(nèi)，筆者提出的算法可以使網(wǎng)絡(luò)穩(wěn)定.最后仿真表明，剩余服務(wù)時(shí)間的引入降低了用戶的拒絕概率，并且提高了用戶的平均收益.這是因?yàn)榭紤]了網(wǎng)絡(luò)選擇在長時(shí)間尺度上的影響，使得用戶更加均勻地分布在了整個(gè)網(wǎng)絡(luò)中.

［1］GUSTAFSSON E，JONSSON A.Always Best Connected［J］.IEEE Wireless Communications，2003，10（1）:49-55.

［2］宋建鋒，李建東.性價(jià)比最大化的異構(gòu)網(wǎng)絡(luò)博弈選擇策略［J］.西安電子科技大學(xué)學(xué)報(bào)，2014，41（1）:18-22. SONG Jianfeng，LI Jiandong.Gaming Network Selection Scheme Considering Performance-price Ratio Maximization in Heterogeneous Wireless Networks［J］.Journal of Xidian University，2014，41（1）:18-22.

［3］WANG L，KUO G S G S.Mathematical Modeling for Network Selection in Heterogeneous Wireless Networks—a Tutorial［J］.IEEE Communications Surveys&Tutorials，2013，15（1）:271-292.

［4］HOU J，O’BRIEN D.Vertical Handover-decision-making Algorithm Using Fuzzy Logic for the Integrated Radio-and-OW System［J］.IEEE Transactions on Wireless Communications，2006，5（1）:176-185.

［5］CHEN Q B，ZHOU W G，CHAI R，et al.Game-theoretic Approach for Pricing Strategy and Network Selection in Heterogeneous Wireless Networks［J］.IET Communications，2011，5（5）:676-682.

［6］LAHBY M，CHERKAOUI L，ADIB A.Network Selection Algorithm Based on Diff-AHP and TOPSIS in Heterogeneous Wireless Networks［C］//Proceedings of the International Conference on Multimedia Computing and Systems.Piscataway: IEEE，2012:485-490.

［7］NIYATO D，HOSSAIN E.Dynamics of Network Selection in Heterogeneous Wireless Networks:an Evolutionary Game Approach［J］.IEEE Transactions on Vehicular Technology，2009，58（4）:2008-2017.

［8］CHARILAS D E，PANAGOPOULOS A D.A Survey on Game Theory Applications in Wireless Networks［J］.Computer Networks，2010，54（18）:3421-3430.

［9］NEELY M J.Stochastic Network Optimization with Application to Communication and Queueing Systems［M］. California:Morgan&Claypool，2010.

［10］URGAONKAR R，KOZAT U C，IGARASHI K，et al.Dynamic Resource Allocation and Power Management in Virtualized Data Centers［C］//Proceedings of the IEEE Network Operations and Management Symposium.Piscataway: IEEE Computer Society，2010:479-486.

（編輯:齊淑娟）

Network selection algorithm in heterogeneous wireless networks based on residual service time

DU Bai，LI Hongyan
（State Key Lab.of Integrated Service Networks，Xidian Univ.，Xi’an 710071，China）

We propose a network selection algorithm based on the residual service time for the network selection problem in heterogeneous networks.There have been already many research works and achievements in this area，but most of the existing works just consider the optimal user or network revenue which does not consider the impact of new users.This paper presents the concept of the residual service time，and uses it to model the impact of the new users，in order to get a better network option on long time scales.In this paper，we use the noncooperative game to model the network，and prove that the Nash equilibrium of the model is also the global optimal solution.Finally，we use the Lyapunov stability theory to show that the proposed algorithm is stable. Simulation results show that the introduction of the residual service time can improve the network performance，reduce the blocking rate，and increase the total network revenue.

heterogeneous networks；network selection；non-cooperative game；Lyapunov；residual service time

10.3969/j.issn.1001-2400.2016.01.002

TN929.5

A

1001-2400（2016）01-0007-05

2014-08-20 網(wǎng)絡(luò)出版時(shí)間：2015-04-14

國家自然科學(xué)基金資助項(xiàng)目（91338115，61231008）；國家科技重大專項(xiàng)資助項(xiàng)目（2011ZX03005-004，2011ZX03004-003，2013ZX03004007-003，2011ZX03005-003）；陜西省13115科技創(chuàng)新工程資助項(xiàng)目（2010ZDKG-26）；國家重點(diǎn)基礎(chǔ)研究發(fā)展計(jì)劃資助項(xiàng)目（2009CB320404）；國家重點(diǎn)實(shí)驗(yàn)室基金資助項(xiàng)目（ISN1002005，ISN090305）；長江學(xué)者和創(chuàng)新團(tuán)隊(duì)發(fā)展計(jì)劃資助項(xiàng)目（IRT0852）

杜 白（1986-），男，西安電子科技大學(xué)博士研究生，E-mail:du198614@163.com.

網(wǎng)絡(luò)出版地址：http://www.cnki.net/kcms/detail/61.1076.TN.20150414.2046.002.html