一種采用剩余服務時間的異構網絡選擇算法

杜 白，李紅艷

（西安電子科技大學綜合業務網理論及關鍵技術國家重點實驗室，陜西西安 710071）

一種采用剩余服務時間的異構網絡選擇算法

杜 白，李紅艷

（西安電子科技大學綜合業務網理論及關鍵技術國家重點實驗室，陜西西安 710071）

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

異構網絡；網絡選擇；非合作博弈；李雅普諾夫；剩余服務時間

近年來，新式無線網絡接入技術快速發展帶來了很多新問題，比如異構環境中的網絡發現、網絡選擇和網絡切換等［1］.網絡選擇是其中一個關鍵性問題，直接影響整個網絡資源的利用率和用戶體驗的滿意度.網絡選擇中，為了得到不同參數合理的權重，找到合適的折中點，很多數學方法，比如博弈論、多目標優化、效應函數、層次分析法和模糊邏輯等被廣泛使用［2-6］.

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

1 系統的非合作博弈模型和網絡選擇算法

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

圖1　異構網絡場景

由于不考慮切換，所以忽略網絡的預留帶寬，假設每個接入網都會把網內的所有資源分配出去，也就是說，如果網絡中只有1個用戶，網絡會把所有資源都給這個用戶使用.當有新用戶到達時，新老用戶會競爭整個網絡的資源，每個用戶實際分配的帶寬用bi表示，可利用非合作博弈來對這個競爭過程進行建模.

現在進行非合作博弈的建模:博弈參與者為新用戶和老用戶.老用戶是指已經接入網絡的用戶，新用戶是指還未接入網絡的用戶所有的用戶用u表示

策略:老用戶讓出的帶寬，用xi表示.新用戶從老用戶手中搶到的帶寬，用αi表示.假設網絡中已有n個用戶｛u1，…，un｝，新到達用戶為un+1，對于老用戶，定義支付函數如下:

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

方程組式（3）的解就是優化問題式（2）的最優解.

下面介紹文中提出的博弈方案的納什均衡點，并證明這個納什均衡點同時也是式（2）的最優解.

這里使用最佳響應函數的方法來求納什均衡點［7］.具體方法為:對所有老用戶的支付函數求導，使其等于0，然后聯立求解.

2 剩余服務時間的引入和算法的穩定性分析

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

第1步 新用戶到達時，根據式（3）進行博弈，得到接入每個接入網j能夠得到的帶寬，用Bj來表示.

第2步 得到每個接入網當前時刻的剩余服務時間Tj，然后計算DiTjRj-VBj.在所有接入網中找出最小的一個DiTjRj-VBj進行接入，其中，V是常數，代表帶寬的權重.文中使用帶寬進行博弈，來獲得當前時刻的全局最優，所以，V取值越大，最終結果越傾向于瞬時的全局最優；反之，則傾向于長時間尺度的優化，而損失當前時刻網絡的收益.

第3步 新用戶選擇好網絡后，所有用戶的帶寬按照式（3）的博弈結果進行分配.

下面證明，當用戶的到達速率在容量域內時，文中提出的算法可以使整個網絡穩定.

當用戶到達時，只要自己進行一次博弈就可以得到最終的選擇結果.下面給出具體的網絡選擇算法.

第1步 新用戶到達時，對所有它可以選擇的接入網分別按照式（3）進行求解，得到它接入每一個可選的接入網可獲得的帶寬.

（1）容量域.假如存在一種網絡選擇策略，可使網絡在到達率λ的情況下穩定，那么這個到達率λ就是在容量域內的，所有這樣的到達率λ的集合ζ稱為網絡的容量域.

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

3 仿真結果

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

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

圖2　用戶的拒絕概率隨到達率的變化

圖3　用戶的平均收益

4 結束語

文中提出了基于非合作博弈的異構網絡選擇算法，并且證明了在文中的建模方法中，納什均衡點正好也就是全局的最優點.然后，在模型中引入了剩余服務時間的概念來研究新用戶對網絡后續運行的影響，并且利用李雅普諾夫理論證明了在整個容量域內，筆者提出的算法可以使網絡穩定.最后仿真表明，剩余服務時間的引入降低了用戶的拒絕概率，并且提高了用戶的平均收益.這是因為考慮了網絡選擇在長時間尺度上的影響，使得用戶更加均勻地分布在了整個網絡中.

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

［2］宋建鋒，李建東.性價比最大化的異構網絡博弈選擇策略［J］.西安電子科技大學學報，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 網絡出版時間：2015-04-14

國家自然科學基金資助項目（91338115，61231008）；國家科技重大專項資助項目（2011ZX03005-004，2011ZX03004-003，2013ZX03004007-003，2011ZX03005-003）；陜西省13115科技創新工程資助項目（2010ZDKG-26）；國家重點基礎研究發展計劃資助項目（2009CB320404）；國家重點實驗室基金資助項目（ISN1002005，ISN090305）；長江學者和創新團隊發展計劃資助項目（IRT0852）

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

網絡出版地址：http://www.cnki.net/kcms/detail/61.1076.TN.20150414.2046.002.html