基于TOPSIS的匹配博弈網(wǎng)絡(luò)選擇算法

于秀蘭，曾　成

(重慶郵電大學 重慶市移動通信市級重點實驗室，400065 重慶 )

?

基于TOPSIS的匹配博弈網(wǎng)絡(luò)選擇算法

于秀蘭，曾成

(重慶郵電大學 重慶市移動通信市級重點實驗室，400065 重慶 )

摘要：針對無線通信中網(wǎng)絡(luò)資源利用率的重要性，提出一種基于逼近理想解排序法(technique for order preference by similarity to ideal solution，TOPSIS)的匹配博弈論異構(gòu)網(wǎng)絡(luò)選擇算法，聯(lián)合考慮用戶端的網(wǎng)絡(luò)選擇和網(wǎng)絡(luò)端的用戶選擇，分析用戶和網(wǎng)絡(luò)的時延、傳輸速率、丟包率，運用匹配博弈的原理選擇出雙方滿意度最高的網(wǎng)絡(luò)選擇方案。仿真結(jié)果表明，在多用戶同時存在的情況下，給出TOPSIS的匹配博弈論異構(gòu)網(wǎng)絡(luò)選擇算法具有較低的阻塞率和較高的滿意度。

關(guān)鍵詞：異構(gòu)網(wǎng)絡(luò)；逼近理想解排序法(TOPSIS)；多用戶；匹配博弈

0引言

隨著無線通信的快速發(fā)展以及802.11ad，F(xiàn)emtocell，WiMAX等新型無線接入技術(shù)的廣泛使用，下一代無線網(wǎng)絡(luò)必將是多種網(wǎng)絡(luò)同時存在的無線異構(gòu)網(wǎng)絡(luò)，不同的網(wǎng)絡(luò)接入技術(shù)在接入速率、工作頻率、覆蓋范圍、接入方式和應(yīng)用場景等方面都各不相同。用戶在不同的情況下對網(wǎng)絡(luò)的需求不同，同時用戶需要根據(jù)不同的需求選擇最優(yōu)的網(wǎng)絡(luò)，沒有一種網(wǎng)絡(luò)始終符合用戶的需求。移動通信系統(tǒng)是一個異構(gòu)的網(wǎng)絡(luò)體系，需要協(xié)調(diào)各種無線網(wǎng)絡(luò)，使得多個用戶同時達到需要的時延、抖動、傳輸速率、丟包率等要求。因此，多用戶的網(wǎng)絡(luò)選擇方案，已成為無線移動通信研究的熱點課題。

目前，對異構(gòu)網(wǎng)絡(luò)選擇的研究已取得一些成果。以用戶為中心的網(wǎng)絡(luò)選擇算法主要考慮用戶的滿意度，通過對網(wǎng)絡(luò)參數(shù)進行分析運算，選擇使用戶滿意度最高的網(wǎng)絡(luò)進行接入。文獻[1]提出了一種新穎的網(wǎng)絡(luò)選擇算法。該算法的提出是基于文獻[2]的層次分析法(analytic hierarchy process， AHP)和文獻[3]的灰色關(guān)聯(lián)分析法(grey relational analysis，GRA)。AHP算法用于計算每個網(wǎng)絡(luò)的權(quán)重大小，但其對于網(wǎng)絡(luò)參數(shù)權(quán)重的確定具有較強的主觀性，網(wǎng)絡(luò)權(quán)重分配不夠合理。GRA算法對各樣本采用平權(quán)處理，客觀性較差，不符合網(wǎng)絡(luò)選擇的實際情況。文獻[4] 提出一種AHP與破產(chǎn)博弈論的聯(lián)合算法，該聯(lián)合算法估計潛在貢獻率，選擇貢獻率最大的網(wǎng)絡(luò)，但算法復雜度較高，會造成過多的網(wǎng)絡(luò)判決延遲。文獻[5]提出一種在長期演進 (long term evolution，LTE)和無線局域網(wǎng) (wireless local area networks，WLAN)系統(tǒng)中的自組織網(wǎng)絡(luò)選擇算法。該算法采用WLAN接收信號強度閥值來控制接入選擇，由于僅從接收信號的強度來進行網(wǎng)絡(luò)選擇，考慮因素單一，造成網(wǎng)絡(luò)選擇的片面性。文獻[6] 基于估計信號的信號干擾噪聲比(signal to interference plus noise ratio，SINR)的網(wǎng)絡(luò)選擇策略，在異構(gòu)網(wǎng)絡(luò)中考慮所有用戶的QoS需求，但僅從用戶的QoS考慮網(wǎng)絡(luò)的選擇，忽略了網(wǎng)絡(luò)端的影響。文獻[7]提出一種基于蜂群演化的網(wǎng)絡(luò)選擇方案，同時利用灰度值分析方法、博弈論方法、遺傳算法考慮網(wǎng)絡(luò)選擇的其他問題，使得算法復雜度較高，無法應(yīng)用于實際環(huán)境。

以上研究主要針對單用戶在異構(gòu)網(wǎng)絡(luò)中的選網(wǎng)，沒有考慮多個用戶同時進行網(wǎng)絡(luò)選擇的情況。同時，僅從用戶端考慮用戶對網(wǎng)絡(luò)的偏好或僅考慮網(wǎng)絡(luò)端對用戶的偏好，這都是單向選擇算法，以最大化自己的效用函數(shù)為目標。針對目前網(wǎng)絡(luò)選擇存在的不足，本文提出一種基于逼近理想解排序法(technique for order preference by similarity to ideal solution，TOPSIS)的匹配博弈算法，從用戶和網(wǎng)絡(luò)的角度出發(fā)，綜合考慮多種參數(shù)指標，同時考慮兩者的偏好，運用匹配博弈，達到用戶和網(wǎng)絡(luò)的雙贏。

1用戶端的網(wǎng)絡(luò)偏好

逼近最優(yōu)解排序法是多屬性決策算法，考慮網(wǎng)絡(luò)的多個參數(shù)，根據(jù)計算目標對象與理想解的相對接近程度來選擇最優(yōu)的網(wǎng)絡(luò)。TOPSIS的理想解分為正理想解和負理想解。采用歐式距離計算每個目標方案與理想方案的距離。TOPSIS算法的最優(yōu)目標方案距離正理想解比較近，同時距離負理想解比較遠[8-10]。

1.1AHP法參數(shù)權(quán)重的確定

文獻[11]介紹了常見的網(wǎng)絡(luò)參數(shù)權(quán)重的計算方法。本文采用AHP計算網(wǎng)絡(luò)參數(shù)的權(quán)重值。AHP應(yīng)用于難于定量分析的問題，將問題中難以處理的部分劃分為相對簡單的問題加以處理。

1.2相對接近程度計算

假設(shè)判決矩陣為Y，表示為

(1)

(1)式中：行表示網(wǎng)絡(luò)；列表示網(wǎng)絡(luò)的參數(shù)指標。

1)判決矩陣標準化。由于各判決指標的單位不同、量綱不同、數(shù)量級不同，需要對所有判決指標進行標準化處理。判決矩陣標準化為

(2)

(2)式中：i表示網(wǎng)絡(luò)，i=1,2,…,m；j表示網(wǎng)絡(luò)的參數(shù)指標，j=1,2,…,n。得到標準化矩陣Z=(zij)m×n。

2)建立加權(quán)標準化矩陣。

(3)

(3)式中，uj是由上述AHP法求得的網(wǎng)絡(luò)參數(shù)的權(quán)重值。

3)確定正理想解和負理想解。

(4)

(5)

(4)—(5)式中:vij為加權(quán)標準化矩陣V中的元素；J為效益型參考集合；J′為成本型參數(shù)集合。

4)計算距離。每個方案距離正負理想方案的距離為

(6)

(7)

5)計算與理想解的相對接近程度。

(8)

然后依據(jù)Ci大小進行排序。則用戶i的網(wǎng)絡(luò)排序U(N)i表示為

(9)

(9)式中：netm表示第m個網(wǎng)絡(luò)。

2網(wǎng)絡(luò)端的用戶偏好

用戶的流失率與網(wǎng)絡(luò)的偏好直接相關(guān)，用戶i是否接入網(wǎng)絡(luò)，直接影響著網(wǎng)絡(luò)的偏好。而用戶的流失率又與數(shù)據(jù)速率、時延、丟包率、帶寬、價格相關(guān)。

2.1用戶滿意度計算

用戶的滿意度與網(wǎng)絡(luò)提供給用戶的速率、時延、丟包率、帶寬、價格直接相關(guān)。定義用戶的滿意度函數(shù)為

(10)

根據(jù)文獻[12]，速率、時延、丟包率的評估函數(shù)定義為

(11)

(12)

(13)

(14)

(14)式中：x，μ為2個函數(shù)變量。

ζj定義為

(15)

(15)式中：ρj表示網(wǎng)絡(luò)j的負載強度；ρ0表示網(wǎng)絡(luò)j的最小負載門限。

根據(jù)Sigmoid函數(shù)，定義網(wǎng)絡(luò)j的帶寬及價格的評估函數(shù)分別為(16)式和(18)式。

(16)

(17)

(18)

(19)

(20)

(21)

(22)

2.2網(wǎng)絡(luò)端的效用函數(shù)

網(wǎng)絡(luò)端的效用函數(shù)為網(wǎng)絡(luò)接入用戶帶來的收益減去網(wǎng)絡(luò)不接入用戶帶來的損失，定義為

(23)

(23)式中：Pi,j表示用戶i接入網(wǎng)絡(luò)j給網(wǎng)絡(luò)帶來的收益；Si,j表示用戶i不接入網(wǎng)絡(luò)j給網(wǎng)絡(luò)帶來的損失。

用戶流失率定義為

(24)

網(wǎng)絡(luò)的損失效用Si,j定義為

(25)

(25)式中，Li,j表示用戶i離開網(wǎng)絡(luò)j時網(wǎng)絡(luò)的損失。

根據(jù)不同用戶的M大小，排列出網(wǎng)絡(luò)j對用戶的偏好排序N(U)j表示為

(26)

(26)式中：usern表示第n個用戶。

3匹配博弈網(wǎng)絡(luò)選擇

匹配博弈是合作博弈的一種，由Gale和Shapley于1962年在一篇關(guān)于大學生就業(yè)和婚姻匹配的問題中提出[13]。1984年Roth對其進行了重要發(fā)展。匹配博弈的參與者被分為2個集合，網(wǎng)絡(luò)集合和用戶集合，其中網(wǎng)絡(luò)集合包括femtocell，802.11ad，Wimax，LTE等一些網(wǎng)絡(luò)組成的異構(gòu)網(wǎng)絡(luò)系統(tǒng)，用戶集合是運行會話類、流類、互動類、背景類[14]的一系列業(yè)務(wù)的用戶。這是2個完全不相交的集合，用戶和網(wǎng)絡(luò)根據(jù)自身的情況進行相互選擇。假設(shè)在一次博弈中每個用戶只能接入一個網(wǎng)絡(luò)，一個網(wǎng)絡(luò)可以接入多個用戶。

3.1匹配博弈算法

假設(shè)網(wǎng)絡(luò)集合為

Net={net1,net2,…,netm}

(27)

用戶集為

User={user1,user2,…,usern}

(28)

匹配博弈采用多對一匹配博弈，即在第1次匹配博弈中，所有用戶同時進行匹配博弈。每一輪匹配過程中，排在網(wǎng)絡(luò)排序U(N)和用戶排序N(U)前面的參與人最先完成匹配，沒有匹配的用戶會在多次匹配之后完成匹配[15]。匹配博弈的具體步驟如下。

1)第1次匹配。假設(shè)已完成匹配的用戶不在用戶集合中。用戶端中的每一個用戶根據(jù)自己的網(wǎng)絡(luò)優(yōu)先級排序U(N)，選擇優(yōu)先級最高的網(wǎng)絡(luò)。網(wǎng)絡(luò)端需要設(shè)定匹配窗口的大小，即網(wǎng)絡(luò)端一次匹配中考慮多少個用戶。如果網(wǎng)絡(luò)端用戶位于匹配窗口內(nèi)，則匹配成功。

2)匹配窗口的平移。如果網(wǎng)絡(luò)j是用戶i中優(yōu)先級最高的網(wǎng)絡(luò)，網(wǎng)絡(luò)j的用戶優(yōu)先級窗口中如果有用戶i，則匹配完成。若用戶i與網(wǎng)絡(luò)j匹配不成功，即網(wǎng)絡(luò)窗口中無用戶i。第1次匹配結(jié)束后，需要對匹配窗口進行平移。網(wǎng)絡(luò)j的窗口刪除網(wǎng)絡(luò)j第1次匹配中匹配成功用戶及其他網(wǎng)絡(luò)經(jīng)過第1次匹配成功的用戶，加入優(yōu)先級排序中未參加匹配的用戶。

3)第2次匹配。網(wǎng)絡(luò)j仍是用戶i中優(yōu)先級最高的網(wǎng)絡(luò)，網(wǎng)絡(luò)j的匹配窗口已經(jīng)發(fā)生了平移。如果用戶i在平移后的匹配窗口中，則匹配完成。第2次匹配可進行多次。

4)用戶匹配失敗。用戶i在第1次匹配和第2次匹配中都未完成匹配，則用戶i選擇優(yōu)先級逐漸次之的網(wǎng)絡(luò)。重復以上過程，直到所有用戶匹配完成。

3.2匹配博弈算法的穩(wěn)定性

匹配博弈始終存在穩(wěn)定的博弈。完成匹配后的網(wǎng)絡(luò)和用戶都能獲得最高的收益，因此，整個算法滿足博弈的穩(wěn)定性。

用戶端的最優(yōu)匹配網(wǎng)絡(luò)指用戶經(jīng)過第k次匹配后所能接入的滿意度最高的網(wǎng)絡(luò)；網(wǎng)絡(luò)端的最優(yōu)匹配用戶指經(jīng)過第k次匹配后，網(wǎng)絡(luò)所能接入的滿意度最高的w個用戶。

在整個匹配算法結(jié)束后，網(wǎng)絡(luò)j最終和d個用戶完成了匹配。對于用戶i在第k次匹配后，用戶i已經(jīng)與其滿意度最高的網(wǎng)絡(luò)完成了匹配，滿意度比網(wǎng)絡(luò)j高的網(wǎng)絡(luò)已經(jīng)被用戶i在k次匹配之前從用戶端的網(wǎng)絡(luò)排序中刪除；對于網(wǎng)絡(luò)j在第k次匹配后，網(wǎng)絡(luò)j已經(jīng)與窗口中參與匹配的用戶i完成了匹配，因此，第k次匹配后窗口中的用戶集滿意度低于匹配刪除的用戶集，整個匹配博弈的結(jié)果是穩(wěn)定的，即不存在一個更優(yōu)的網(wǎng)絡(luò)匹配來破壞原來的匹配結(jié)果。

4仿真結(jié)果與分析

本文的仿真場景如圖1所示，多個用戶同時處于femtocell，Wimax，802.11ad，LTE的覆蓋區(qū)域內(nèi)。根據(jù)3GPP將業(yè)務(wù)類型分為4類(會話類、流類、互動類、背景類)，用戶的業(yè)務(wù)類型包含了全部的4種類型。仿真中的無線網(wǎng)絡(luò)參數(shù)值如表1所示。

圖1　多用戶網(wǎng)絡(luò)選擇模型Fig.1　Multi-user network selection model

候選網(wǎng)絡(luò)時延/ms抖動/ms速率/(Mbit·s-1)丟包率/%femtocell10—252—5500.001802.11ad8—201—8800.002Wimax35—502—7150.003LTE60—1003—10300.004

不同窗口大小滿意度情況如圖2所示。從圖2可以看出，隨著用戶數(shù)的增加，用戶端的平均滿意度下降，網(wǎng)絡(luò)端的平均滿意度緩慢上升后趨于平穩(wěn)。當窗口大小大于或等于用戶數(shù)時，用戶的平均滿意度最大且不變，此時的匹配選擇相當于用戶端采用TOPSIS算法選擇，用戶選擇性能最好的網(wǎng)絡(luò)，此時用戶的平均滿意度最高，但是用戶間無法相互通信，所有用戶都同時接入性能最好的網(wǎng)絡(luò)，必將造成最優(yōu)網(wǎng)絡(luò)擁塞。匹配窗口越大，要達到的匹配博弈的要求需要的用戶數(shù)越多，且此時用戶的滿意度開始下降，表示通過匹配博弈，用戶的平均滿意度下降，部分用戶選擇了滿意度較小的網(wǎng)絡(luò)，與僅考慮用戶端TOPSIS算法比較，避免了網(wǎng)絡(luò)擁塞。窗口數(shù)越小對用戶端和網(wǎng)絡(luò)端的滿意度影響越明顯，窗口過大時，基于博弈論文的網(wǎng)絡(luò)選擇等同于用戶端的網(wǎng)絡(luò)選擇算法。用戶滿意度與網(wǎng)絡(luò)滿意度的交點表示最佳匹配點，用戶數(shù)為70時，網(wǎng)絡(luò)的最佳窗口大小為10。

圖2　不同窗口大小滿意度情況Fig.2　Satisfaction with different window size

博弈次數(shù)隨窗口大小的變化情況如圖3所示。從圖3可以看出，隨著用戶數(shù)目的增加，博弈的匹配次數(shù)增加。相同用戶數(shù)的情況下，博弈的次數(shù)隨窗口大小的減小而增加。

圖3　博弈次數(shù)隨窗口大小的變化Fig.3　Number of game along with the change of window size

由于不同用戶的參數(shù)不同，網(wǎng)絡(luò)的參數(shù)不同，造成用戶對網(wǎng)絡(luò)的優(yōu)先級偏好，網(wǎng)絡(luò)對用戶的優(yōu)先級偏好不同，所以博弈的次數(shù)也會造成不同。

5結(jié)束語

本文提出了一種適用于多用戶的基于TOPSIS的匹配博弈，不同于已有文獻僅考慮用戶端或網(wǎng)絡(luò)端進行網(wǎng)絡(luò)選擇的算法，該匹配博弈算法同時考慮用戶對網(wǎng)絡(luò)的偏好及網(wǎng)絡(luò)對用戶的偏好，運用匹配博弈找到博弈的均衡點，即是最優(yōu)的網(wǎng)絡(luò)選擇。仿真結(jié)果表明，基于TOPSIS的匹配博弈網(wǎng)絡(luò)選擇算法，不但滿足用戶和網(wǎng)絡(luò)的滿意度而且有利于提升網(wǎng)絡(luò)的利用率，降低網(wǎng)絡(luò)的擁塞率。

參考文獻：

[1]SASAKI M,YAMAGUCHI A,IMAGAKI Y,et al. Novel Communication System Selection applying the AHP Algorithm in Heteogeneous Wireless Networks[C]//Springer. Proceedings of The First International Conference on Wireless Communications and Applications.Sanya:Springer Berlin Heidelberg Press,2011:241-249.

[2]SONG Q, JAMALIPOUR A. Network selection in an integrated wireless LAN and UMTS environment using mathematical modeling and computing techniques [J].IEEE Wireless Communications,2005, 12(3):42-48.

[3]FU Jianqing, WU Jiyi, ZHANG Jianlin, et al. A Novel AHP and GRA Based Handover Decision Mechanism in Heterogeneous Wireless Networks[C]//Springer.Information Computing and Applications.Tangshan:Springer Berlin Heidelberg,2010:213-220.

[4]LIU Bin,TIAN Hui, WANG Bin,et al.AHP and Game Theory based Approach for Network Selection in Heterogeneous Wireless Networks [C]//IEEE.IEEE Consumer Communications and Networking Conference(CCNC).LasVegas, NV:IEEE,2014:501-506.

[5]WANG Y,DJAPIC R, BERGSTROM A,et al. Performance of WLAN RSS based SON for LTE/WLAN access network selection[C]//IEEE.IEEE Wireless Communications Systems(ISWCS).Barcelona: IEEE,2014:460-464.

[6]JABBAN A,NASSER Y, HELARD M. Performance Analysis of Heterogeneous Networks Based on SINR Selection Strategy[C]//IEEE. International Conference on Telecommunications(ICT).Casablanca:IEEE,2013:1-5.

[7]ZHANG Chengbo, WANG Xingwei . A Network Selection Scheme Based on Bee Colony Evolution [C]//IEEE.IEEE Computer Science and Network Technology (ICCSNT).Dalian:IEEE,2013: 650-654.

[8]BARI F, LEUNG V C M.Automated network selection in a heterogeneous wireless network environment[J].IEEE Network, 2007, 21(1):34-40.

[9]ZHOU Shaoqi, CHANG Wenbing, ZHOU Shenghan,et al.The method of risk evaluation for equipment development based on triangular fuzzy number and TOPSIS [C]//IEEE.Proceedings of IEEE Control and Decision Conference (CCDC).Changsha:IEEE,2014:2272-2276.

[10] LIU Fang, ZHANG Weiguo. TOPSIS Based Consensus Model for Group Decision Making with Incomplete Interval Fuzzy Preference Relations [J]. IEEE Transactions on,2014, 44(8):1283-1294.

[11] MOHAMED L, LEGHRIS C, ABDELLAH A. A survey and comparison study on weighting algorithms for access network selection[C]// IEEE .Annual Conference on Wireless On-demand Network Systems and Services(WONS). Courmayeur:IEEE，2012：35-38.

[12] CHEN Yunghan, YANG Nuanyu, CHANG Chungju. A utility function based access selection method for heterogeneous WCDMA and WLAN network[C] //IEEE.IEEE 18th International Symposium on Personal, Indoor and Mobile Radio Communications(PIMRC). Athens:IEEE, 2007:l-5.

[13] GALE D, SHAPLEY L S.College Admissions and the Stability of Marriage [J].The American Mathematical Monthly, 1962，2013,69(5):9-15.

[14] 3GPP.Technieal Specification TS23.107, V4.0.0，QoS, Concept and Architecture [S].[s.l.]: 3GPP Organization Partners, 2000.

[15] ZENG Yi, ZHANG Zufan. Joint transmit beamforming and power control in multi-user MIMO downlink using a game theoretic approach [J]. The Journal of China Universities of Posts and Telecommunications, 2007,14(2)：14-18.

DOI：10.3979/j.issn.1673-825X.2016.04.002

收稿日期：2015-06-15

修訂日期：2016-02-29通訊作者：曾成448212556@qq.com

基金項目：國家自然科學基金(61440062)；國家863計劃(2014AA01A705)

Foundation Items：The National Natural Science Foundation of China(61440062)；The National High Technology Research and Development Program of China(“863”Program)(2014AA01A705)

中圖分類號：TN929.5

文獻標志碼：A

文章編號：1673-825X(2016)04-0451-05

作者簡介：

于秀蘭(1973-)，女，四川廣安人，副教授，碩士，研究方向為無線通信。E-mail: yuxl@cqupt.edu.cn。

曾成(1989-)，男，四川眉山人，碩士研究生，研究方向為無線通信。E-mail:448212556@qq.com。

(編輯：王敏琦)

Matching game network selection algorithm based on TOPSIS

YU Xiulan， ZENG Cheng

(Chongqing Key Laboratory of Mobile Communication, Chongqing University of Posts and Telecommunications, Chongqing 400065, P.R.China)

Abstract:According to the importance of enhancing the network resources efficiency for wireless communication, this paper proposes a heterogeneous network selection algorithm based on technique for order preference by similarity to ideal solution (TOPSIS)matching game. We consider network selection at client and user selection at server and analyze delay, transmission rate, packet loss rate of the whole system. Based on the TOPSIS matching game, we select the most appropriate network selection program which meets the requirements of both clients and servers. The simulation shows that in the presence of multiple users at the same time, heterogeneous network selection algorithm based on TOPSIS matching game has lower blocking rate and achieve higher satisfaction.

Keywords：heterogeneous network; technique for order preference by similarity to ideal solution (TOPSIS); multiple users; matching game