基于演化博弈的多用戶網絡選擇算法

唐 夲，李 樂，肖靜薇，吳維農，馮文江

(1.國網重慶市電力公司信息通信分公司，重慶 400022；2.重慶大學通信工程學院，重慶 400044)

1 引言

無線通信技術的發展改變了人們的生活和工作方式，而通信需求的日益增長又促進了無線通信技術的進一步發展。不同于傳統無線網絡中通信體制的單調演進，新一代無線通信系統著重于多類網絡異構網絡融合。不同網絡為用戶提供差異化服務的同時，用戶也能根據QoS(Quality of Service)選擇不同的網絡實現最佳接入[1]。從而提升網絡頻譜效率和服務質量。

典型的網絡選擇算法有博弈論法[2 - 4]、遺傳算法[5,6]、人工神經網絡法[7]、排隊論法[8]、馬爾科夫鏈法[9]等。但是，在熱點區域，當密集分布的大量用戶同時發起同種業務請求時，如果采取多屬性決策進行網絡選擇，雖然可以實現單用戶最優，但未顧及用戶間競爭，且缺乏公平性，難以高效、合理利用不同網絡資源。針對多用戶的網絡選擇算法則大多利用博弈論，如用戶間博弈[2,10]、用戶與網絡間博弈[3]和網絡間博弈[11,12]等。文獻[4]提出一種網絡選擇算法，將網絡與用戶間的關系抽象為非合作博弈，搜尋納什均衡以最大化用戶性價比；而在以用戶為中心的網絡選擇中，需要同時滿足用戶的QoS需求和最大化網絡效益，如文獻[13]運用匹配博弈，提出一種異構網絡選擇算法，能同時兼顧用戶和網絡效益。

在異構多網共存和重疊覆蓋區域，當多個用戶同時請求同種業務時，用戶間表現為一種非合作競爭關系。本文提出一種基于動態演化博弈的多用戶網絡選擇算法，根據選擇網絡的用戶數設計效益函數，給出了演化博弈的復制動態方程。與接收信號強度指示RSSI(Received Signal Strength Indication)算法[13]的對比仿真結果表明：該算法能快速達到演化均衡，用戶平均收益高于RSSI算法，接入網絡的用戶分布更均勻，能合理利用網絡資源。

2 演化博弈模型

如圖1所示，WCDMA 蜂窩網、LTE蜂窩網和無線局域網(WLAN)重疊、交叉覆蓋，構成異構多網共存環境。根據各用戶位置、請求業務類型和傳輸速率，將用戶劃分為不同群體，即不同群體的用戶具備不同屬性。在圖1中，兩種業務的不同群體用戶分別分布于網絡覆蓋區域1、2、3。

Figure 1 A network scenario圖1 網絡場景

將多用戶選擇網絡過程抽象為一種演化博弈，以圖1為例說明，其中：

參與者：在特定區域內請求特定業務類型的用戶群體。區域2的參與者為競爭LTE和WLAN的用戶群體；區域3的參與者為競爭WCDMA、LTE和WLAN的用戶群體，而區域1只有WCDMA覆蓋，用戶無網絡選擇過程，不屬于演化博弈參與者。在動態演化博弈中，參與者能在自我復制過程中變異和選擇。

種群：在特定區域內請求同種業務的用戶。區域2中請求接入LTE的用戶構成一個種群，請求接入WCDMA的用戶構成另一個種群；區域3中請求接入WCDMA、LTE和WLAN的用戶也分別構成種群。

決策：用戶可選擇接入的網絡。區域2有兩張網絡覆蓋，決策集合為{WCDMA,LTE}，區域3有三張網絡覆蓋，決策集合為{WCDMA,LTE,WLAN}。

收益：用戶選擇網絡能獲得的效用。

3 網絡選擇算法

3.1 用戶效用函數設計

針對特定業務類型，設計一個凸函數來衡量用戶收益，表示如下：

(1)

3.2 演化博弈復制動態方程

(2)

在演化博弈中，種群a的復制動態方程為：

(3)

3.3 演化均衡穩定性

3.4 算法流程

在網絡重疊覆蓋區域部署一個控制中心，基于演化博弈的多用戶網絡選擇算法如圖2所示，算法流程描述如下。

具體步驟為：

Step1初始化各類參數，用戶隨機選擇網絡；

Step2控制中心執行演化博弈網絡選擇算法，根據當前用戶的網絡選擇狀態計算各用戶收益和種群內用戶平均收益，并將計算結果廣播至各用戶；

Step4重復執行Step 2和Step 3，直到達到演化均衡。

Figure 2 Flowchart of multi-user network selection algorithm based on evolutionary game圖2 基于演化博弈的多用戶網絡選擇算法流程

4 仿真及分析

圖3所示為本文研究的網絡場景中的用戶分布情況圖，WCDMA、LTE和WLAN分布于1.5 km×1.5 km區域，最外圓區域內WCDMA基站坐標為(550,530)，覆蓋半徑為600 m,網絡帶寬為7 Mbps,代價系數取0.02；正六邊形區域內LTE基站坐標為(550,480)，覆蓋半徑為300 m,網絡帶寬為20 Mbps,代價系數取0.03；中心橢圓區域內WLAN接入點坐標為(550,400)，覆蓋半徑為150 m，網絡帶寬和價格系數分別為10 Mbps和0.01。兩種不同業務請求的用戶隨機分布于整個區域內，業務1請求用戶數為50，業務2請求用戶數為30。

Figure 3 Distribution of networks and users圖3 網絡及用戶分布仿真圖

根據區域1、2、3內用戶分布以及請求業務類型分成4個種群，區域3內請求業務1的用戶為種群1，可選擇接入WCDMA、LTE或WLAN；區域2內請求業務1的用戶為種群2，可選擇接入WCDMA或LTE；區域3內請求業務2的用戶為種群3，可選擇接入WCDMA、LTE或WLAN；區域2請求業務2的用戶為種群4，可選擇接入WCDMA或LTE。位于區域1內的用戶無論請求何種業務只能選擇接入WCDMA，因此區域1用戶不構成種群。對網絡中用戶進行統計分析，各種群用戶數分布依次為9、22、2、18。

Figure 4 Change rate of access user proportion of different groups圖4 各種群接入用戶比例變化率

Figure 5 Proportion of user selection network of different groups圖5 各種群用戶選擇網絡比例

根據演化博弈理論，當達到演化均衡時，種群內用戶收益等于用戶平均收益，用戶選擇不會再改變。下面從數值角度驗證：以種群1為例，最終演化均衡時所有用戶全部選擇WLAN，根據式(2)計算此時用戶收益為13.780 0，假設該用戶背離演化均衡選擇另一個網絡，那么在其他用戶不改變網絡選擇的情況下該用戶收益為13.047 6，小于此前的收益，因此該用戶不會做出該選擇；假設另一個用戶選擇WCDMA，那么在其他用戶不改變網絡選擇的情況下，用戶收益為12.331 1，同樣小于演化均衡時的收益，也不會選擇與演化均衡不一致的結果。同理可證種群2、3、4的演化均衡均穩定。

當達到演化均衡時，各種群選擇接入各網絡的收益值如表2所示。

需要說明的是，本文未考慮用戶離散性，鑒于演化博弈是一個連續的動態選擇過程，在均衡時各用戶收益均采用四舍五入方式近似取值，因此均衡時每個種群的收益并非完全相等，但這不影響演化均衡結果，滿足演化均衡定義，該演化均衡仍是穩定的。

Table 1 User selection statistics of different groups

Table 2 Benefit statistics obtained by different groups

圖6所示為用戶平均收益隨時間變化曲線。由圖6可知，相比于RSSI算法[13]，本文算法用戶平均收益更高。圖7所示為不同業務在演化博弈和RSSI兩種算法仿真下，最終選擇接入各網絡的用戶數。由圖7可知，采用本文算法，選擇各網絡的用戶數比RSSI算法[13]更均衡，各網絡資源利用更合理。

Figure 6 Average benefit of users圖6 用戶平均效益

Figure 7 Number of access users圖7 接入用戶數

5 結束語

本文研究了在用戶密集區域且多個異構網絡共存時，大量用戶同時發起同種業務請求時如何高效進行網絡選擇，旨在滿足用戶QoS，均衡網絡負載，提高頻譜效率。提出了一種基于演化博弈的多用戶網絡選擇算法，設計了一種隨選擇網絡用戶數變化的用戶效用函數，并給出了演化博弈的復制動態方程。

與RSSI算法的對比仿真結果表明：本文算法能快速達到演化均衡，用戶平均收益高于文獻[13]提出的RSSI算法，接入異構網絡的用戶分布更均勻，網絡資源能得到合理利用。

[1] Gustafsson E,Jonsson A.Always best connected[J].IEEE Wireless Communications,2003,10(1):49-55.

[2] Trestian R,Ormond O,Muntean G M.Game theory-based network selection:Solutions and challenges[J].IEEE Communications Surveys & Tutorials,2012,14(4):1212-1231.

[3] Maheswaran C P,Sulochana C H.Network selection mechanism for future generation networks using game theory model[C]∥Proc of International Conference on Computer Science and Information Technology,2014:405-413.

[4] Salih Y K,See O H,Ibrahim R W,et al.A novel noncooperative game competing model using generalized simple additive weighting method to perform network selection in heterogeneous wireless networks[J].International Journal of Communication Systems,2015,28(6):1112-1125.

[5] Gu C,Song M,Zhang Y,et al.Novel network selection mechanism using AHP and enhanced GA[C]∥Proc of the 7th Annual Communication Networks and Services Research Conference,2009:397-401.

[6] Tang Liang-rui,Li Wen-meng,Sheng Jie,et al.Chaos inheritance based access selection strategy on heterogeneous wireless network [J].Acta Electronica Sinica,2014,42(8):1564-1570.(in Chinese)

[7] Xing H Z,Mu D W,Ge X L,et al.An NN-based access network selection algorithm for heterogeneous networks[C]∥Proc of the 22nd Wireless and Optical Communications Conference (WOCC),2013:378-383.

[8] Sun Y,Liu C,Yang P,et al.A smart vertical handoff decision algorithm based on queuing theory[C]∥Proc of the 16th International Conference on Advanced Communication Technology (ICACT),2014:1217-1222.

[9] Du Z Y,Wu Q H,Yang P L.Dynamic user demand driven online network selection[J].IEEE Communications Letters,2014,18(3):419-422.

[10] Salih Y K,See O H,Ibrahim R W,et al.A user-centric game selection model based on user preferences for the selection of the best heterogeneous wireless network[J].Annals of Telecommunications-Annales Des Telecommunications,2015,70(5-6):239-248.

[11] 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.

[12] El-Hajj A M,Dawy Z,Saad W.A stable matching game for joint uplink/downlink resource allocation in OFDMA wireless networks[C]∥Proc of IEEE International Conference on Communications (ICC),2012:5354-5359.

[13] Feng Ya-nan.The research of access selection strategy and algorithm on heterogeneous wireless network [D].Hangzhou:Zhejiang University,2014.(in Chinese)

附中文參考文獻:

[6]唐良瑞,李文猛,盛潔,等.基于混沌遺傳的異構無線網絡接入選擇策略[J].電子學報,2014,42(8):1564-1570.

[13]馮亞男.異構無線網絡接入選擇策略與算法的研究[D].杭州:浙江大學,2014.