信息不可見混合式接入網(wǎng)絡(luò)納什均衡問題的研究①

劉 俊 余 靖 齊佳興 金順福

(燕山大學(xué)信息科學(xué)與工程學(xué)院 秦皇島 066004)

0 引 言

隨著移動電子設(shè)備的普及，移動用戶希望在任意時間和任意地點訪問互聯(lián)網(wǎng)，因此對混合式接入網(wǎng)絡(luò)的需求越來越大[1]。如何科學(xué)、高效和均衡地使用混合式接入網(wǎng)絡(luò)，成為相關(guān)領(lǐng)域的研究熱點。

針對cellular網(wǎng)絡(luò)、Wi-Fi網(wǎng)絡(luò)和混合式接入網(wǎng)絡(luò)的傳輸過程，相關(guān)學(xué)者研究了網(wǎng)絡(luò)資源管理算法。文獻[2]為消除微蜂窩型基站傳輸功率對網(wǎng)絡(luò)服務(wù)質(zhì)量消極的影響，給出一種啟發(fā)式搜索算法(power search algorithm，PSA)，提高了cellular網(wǎng)絡(luò)的傳輸效率，并降低了微蜂窩型基站的傳輸功耗。文獻[3]考慮Wi-Fi網(wǎng)絡(luò)致密化情況，設(shè)計了一種具有靈活、可伸縮和易擴展特點的高效管理密集Wi-Fi接入網(wǎng)絡(luò)的控制架構(gòu)(control architecture for efficient management of dense Wi-Fi access networks，CADWAN-A)，提升了Wi-Fi網(wǎng)絡(luò)的傳輸性能。文獻[4]針對可用合法頻譜稀缺致使網(wǎng)絡(luò)資源分配出現(xiàn)混亂的問題，研究一種基于軟件定義蜂窩網(wǎng)絡(luò)(software defined cellular networks，SDCN)的分布式資源分配算法，增大了混合式接入網(wǎng)絡(luò)的資源使用率。文獻[5]通過研究多覆蓋Wi-Fi接入點組成的異構(gòu)網(wǎng)絡(luò)中的下行Wi-Fi模型，提出一種面向混合式接入網(wǎng)絡(luò)的分布式資源分配算法，增加了流量傳輸效率。以上算法專注于網(wǎng)絡(luò)傳輸過程的研究，但是缺少對用戶接入行為的研究。

部分學(xué)者將排隊博弈理論和網(wǎng)絡(luò)傳輸理論相結(jié)合，從系統(tǒng)性能出發(fā)，研究了移動用戶的行為策略。文獻[6]利用排隊模型和博弈論研究了認知無線網(wǎng)絡(luò)(cognitive radio network，CRN)的決策問題，將移動用戶之間的決策行為視為一種非合作博弈，并根據(jù)CRN的平均等待時間，給出CRN中用戶訪問的最優(yōu)行為及納什均衡策略，實現(xiàn)了CRN用戶之間的資源合理分配。文獻[7]考慮移動終端用戶之間的資源競爭現(xiàn)象，構(gòu)建一種非合作博弈排隊模型，證明了納什均衡的存在性，給出用戶最優(yōu)策略，提升了移動終端無線通信的性能。文獻[8]考慮無線傳感網(wǎng)絡(luò)中的資源競爭問題，給出一種基于博弈思想的多任務(wù)調(diào)度策略，不僅滿足了移動用戶多樣化的需求，而且提升了節(jié)點和鏈路資源的利用率。文獻[9]針對可開閉異構(gòu)網(wǎng)絡(luò)，提出基于納什均衡的離散粒子群算法，以用戶和基站為博弈參與方建立博弈模型，給出非合作博弈條件下的納什均衡策略和社會最優(yōu)策略。以上文獻從排隊論和博弈論的角度，研究了移動用戶的接入行為，但是缺少對混合式接入網(wǎng)絡(luò)傳輸過程的研究，尤其是對社會最優(yōu)策略的研究。

本文基于信息不可見情況，考慮數(shù)據(jù)傳輸與網(wǎng)絡(luò)連接狀態(tài)的特點，在離散時域下，建立具有2種工作狀態(tài)單服務(wù)臺的馬爾可夫排隊系統(tǒng)。采用矩陣幾何解方法獲得系統(tǒng)的穩(wěn)態(tài)分布，給出移動用戶平均響應(yīng)時間的封閉解。按照混合式接入網(wǎng)絡(luò)工作原理進行仿真實驗，給出系統(tǒng)性能指標統(tǒng)計結(jié)果。權(quán)衡移動用戶回報與損耗，構(gòu)造預(yù)期收益函數(shù)，分別從個人與社會角度給出移動用戶的納什均衡進入策略與社會最優(yōu)進入策略。改進灰狼智能尋優(yōu)算法，以最大化系統(tǒng)收益為目標，獲得社會最優(yōu)到達率和納什均衡到達率。針對不同系統(tǒng)參數(shù)，面向移動用戶給出合理收費方案。

1 系統(tǒng)模型與模型分析

1.1 系統(tǒng)模型

移動用戶交替使用的cellular網(wǎng)絡(luò)和Wi-Fi網(wǎng)絡(luò)可以看作是一個混合式接入網(wǎng)絡(luò)。在混合式接入網(wǎng)絡(luò)系統(tǒng)中，cellular網(wǎng)絡(luò)和Wi-Fi網(wǎng)絡(luò)被視為2種不同的服務(wù)狀態(tài)。假設(shè)移動用戶發(fā)送訪問請求后不會反悔，發(fā)出的數(shù)據(jù)包可能會在cellular網(wǎng)絡(luò)下傳輸完成，也可能在Wi-Fi網(wǎng)絡(luò)下傳輸完成。考慮cellular網(wǎng)絡(luò)和Wi-Fi網(wǎng)絡(luò)交替出現(xiàn)，建立服務(wù)臺狀態(tài)可變的系統(tǒng)排隊模型。

假設(shè)用戶數(shù)據(jù)包的到達服從參數(shù)為Λ的二項分布，Wi-Fi連接的持續(xù)時間xw服從參數(shù)為pw的幾何分布，Wi-Fi連接的間斷時間xc服從參數(shù)為pc的幾何分布。假設(shè)用戶發(fā)出的數(shù)據(jù)包在Wi-Fi網(wǎng)絡(luò)持續(xù)連接狀態(tài)下所需的傳輸時間Sw服從參數(shù)為μw的幾何分布，在cellular網(wǎng)絡(luò)持續(xù)連接狀態(tài)下所需的傳輸時間Sc服從參數(shù)為μc的幾何分布。實際應(yīng)用中，Wi-Fi網(wǎng)絡(luò)下的傳輸速度往往比cellular網(wǎng)絡(luò)下的傳輸速度快，規(guī)定μw>μc。

1.2 轉(zhuǎn)移概率矩陣

將t時刻系統(tǒng)中數(shù)據(jù)包的數(shù)量表示為L(t)=i,i∈{0, 1, 2,…}，稱為系統(tǒng)水平，將t時刻接入網(wǎng)絡(luò)的狀態(tài)表示為J(t)=j,j∈{0, 1}，其中j=0表示cellular網(wǎng)絡(luò)，j=1表示W(wǎng)i-Fi網(wǎng)絡(luò)。{L(t),J(t),t≥0}構(gòu)成了一個二維離散時間馬爾可夫鏈，其狀態(tài)空間表示為

Ω={(i,j)|i∈{0, 1, 2,…},j∈{0, 1}}

(1)

假設(shè){L(t),J(t),t≥0}的一步狀態(tài)轉(zhuǎn)移概率矩陣為P，系統(tǒng)由水平i(i=0, 1, 2, …)至水平k(k=0, 1, 2,…)的一步轉(zhuǎn)移概率子陣為Pi, k。接下來分析子陣Pi, k的5種表現(xiàn)形式。

(1) 當i=0，k=0時，表明系統(tǒng)未發(fā)生用戶數(shù)據(jù)包的到達。一步轉(zhuǎn)移概率子陣P0,0為

(2)

(2) 當i=0，k=1時，表明系統(tǒng)到達了一個用戶數(shù)據(jù)包。一步轉(zhuǎn)移概率子陣P0,1為

(3)

(3) 當k=i-1(i≥1)時，表明系統(tǒng)未發(fā)生用戶數(shù)據(jù)包的到達，且有一個用戶數(shù)據(jù)包離去。一步轉(zhuǎn)移概率子陣Pi,i-1為

(4)

(4) 當k=i(i≥1)時，表明系統(tǒng)未發(fā)生用戶數(shù)據(jù)包的到達和離去，或者系統(tǒng)發(fā)生一個用戶數(shù)據(jù)包的到達和一個用戶數(shù)據(jù)包的離去。一步轉(zhuǎn)移概率子陣Pi,i為

(5)

(5) 當k=i+1(i≥1)時，表明系統(tǒng)發(fā)生一個用戶數(shù)據(jù)包的到達，且沒有用戶數(shù)據(jù)包離去。一步轉(zhuǎn)移概率子陣Pi, i+1為

(6)

由以上分析可知，系統(tǒng)的狀態(tài)轉(zhuǎn)移僅發(fā)生于相鄰水平且狀態(tài)轉(zhuǎn)移從水平i≥1開始重復(fù)。令A(yù)0=P0,0，C0=P0,1，A=Pi,i，B=Pi,i-1，C=Pi,i+1，給出一步轉(zhuǎn)移概率矩陣P的分塊三對角形式的系統(tǒng)如下式所示。

(7)

1.3 穩(wěn)態(tài)概率分布

令πi, j表示穩(wěn)態(tài)下混合式接入網(wǎng)絡(luò)水平為i、網(wǎng)絡(luò)連接狀態(tài)為j的概率分布，則有：

i=0, 1, 2,…,j=0, 1 (8)

令πi表示穩(wěn)態(tài)下系統(tǒng)水平為i的概率向量，則有：

πi={πi,0,πi,1}i=0, 1, 2, …

(9)

二維馬爾可夫鏈{L(t),J(t),t≥0}的穩(wěn)態(tài)分布Π為

Π={π0,π1,π2, …}

(10)

由一步轉(zhuǎn)移概率矩陣P的結(jié)構(gòu)可知{L(t),J(t),t≥0}是一個擬生滅過程[10](quasi birth and death process, QBD)，通過高斯-賽德迭代法[11]與矩陣幾何解[12]求解其穩(wěn)態(tài)分布。

構(gòu)造二次矩陣等式：

R2B+R(A-I)+C=0

(11)

其中，設(shè)R為率陣。式(11)具有非負解且最小非負解小于1，即譜半徑[13](spectral radius, SR)小于1，QBD{L(t),J(t),t≥0}正常返具有穩(wěn)態(tài)分布。

構(gòu)造方程組如下：

(12)

其中，I為單位矩陣，e為全1列向量。

使用高斯-賽德爾方法求解式(12)可得π0和π1，基于矩陣幾何解的形式，進一步得到：

πk=π1Rk-1k≥1

(13)

2 系統(tǒng)響應(yīng)性能

數(shù)據(jù)包的平均逗留時間D定義為數(shù)據(jù)包從進入系統(tǒng)開始到服務(wù)完成為止的平均時間長度。在潛在到達率Λ一定的情形下，數(shù)據(jù)包平均逗留時間與數(shù)據(jù)包進入系統(tǒng)的概率q有關(guān)，表示為

(14)

其中，πi+1，0、πi+1，1為有效到達率λ=qΛ條件下的系統(tǒng)穩(wěn)態(tài)分布。

以pc=0.4、pw=0.6為例，揭示了數(shù)據(jù)包的進隊概率q對平均逗留時間D(q)的影響。理論分析實驗在Matlab R2016a的環(huán)境下實現(xiàn)，仿真統(tǒng)計實驗在MyEclipse 2017 CI環(huán)境下使用Java語言實現(xiàn)。計算機操作系統(tǒng)為Windows 10 企業(yè)版，處理器為Intel Core i5-6 500 3.20 GHz，內(nèi)存為4 GB。圖1揭示了不同cellular網(wǎng)絡(luò)服務(wù)率μc和Wi-Fi網(wǎng)絡(luò)服務(wù)率μw下，平均逗留時間D(q)隨數(shù)據(jù)包的進隊概率q的變化趨勢。

圖1 數(shù)據(jù)包平均逗留時間的變化趨勢

從圖1中可以看出，當數(shù)據(jù)包的進隊概率q較低(如q<0.6)時，平均逗留時間D(q)隨進隊概率q的變化趨勢平緩，而且Wi-Fi網(wǎng)絡(luò)服務(wù)率μw和cellular網(wǎng)絡(luò)服務(wù)率μc對平均逗留時間D(q)的影響很小。當數(shù)據(jù)包的進隊概率q適中(如0.60.8)時，平均逗留時間D(q)隨進隊概率q的變化趨勢快速增長，且Wi-Fi網(wǎng)絡(luò)服務(wù)率μw或cellular網(wǎng)絡(luò)服務(wù)率μc越小，該趨勢增長越強。

3 納什均衡與社會最優(yōu)

3.1 納什均衡進隊概率

一個數(shù)據(jù)包進入系統(tǒng)后的平均收益Yp(q)是回報M與逗留期間成本D(q)N的差，則

Yp(q)=M-D(q)N

(15)

標記到達混合式接入網(wǎng)絡(luò)的一個數(shù)據(jù)包，根據(jù)該數(shù)據(jù)包收益情況討論其均衡進隊概率qe[14]。

(1) 如果M

(2) 如果M>D(1)N，則數(shù)據(jù)包進入系統(tǒng)后，預(yù)期收益是正值。因此進隊概率qe=1是唯一的均衡策略。

(3)當M-D(0)N

M=D(qe)N

(16)

以pc=0.4、pw=0.6為例，圖2揭示了不同cellular網(wǎng)絡(luò)服務(wù)率μc和Wi-Fi網(wǎng)絡(luò)服務(wù)率μw下，數(shù)據(jù)包的個人收益Yp(q)隨進隊概率q的變化趨勢。

從圖2中可以看出，數(shù)據(jù)包的個人收益Yp(q)隨進隊概率q的增加呈現(xiàn)單調(diào)遞減的趨勢。當進隊概率q較低(如q<0.6)時，數(shù)據(jù)包的個人收益Yp(q)隨進隊概率q的增加呈現(xiàn)緩慢下降的趨勢，且個人收益Yp(q)的3條曲線之間的分散距離較小。當進隊概率q較高(如q>0.6)時，數(shù)據(jù)包的個人收益Yp(q)隨進隊概率q的增加呈現(xiàn)快速下降的趨勢，而且個人收益Yp(q)的3條曲線之間的分散距離逐漸加大，個人收益Yp(q)的3條曲線到達0點(納什均衡點)的快慢也不相同。此時，若固定Wi-Fi網(wǎng)絡(luò)服務(wù)率μw，增大cellular網(wǎng)絡(luò)服務(wù)率μc，則個人收益Yp(q)隨進隊概率q的增加延后到達0點(納什均衡點)。若固定cellular網(wǎng)絡(luò)服務(wù)率μc，增大Wi-Fi網(wǎng)絡(luò)服務(wù)率μw，則個人收益Yp(q)隨進隊概率q的增加延后到達0點(納什均衡點)。此時，延后的程度較增大cellular網(wǎng)絡(luò)服務(wù)率μc延后的程度小一些(免費使用的Wi-Fi網(wǎng)絡(luò)，對比收費使用的cellular網(wǎng)絡(luò)，減少了使用費用的支出，使得個人收益Yp(q)的下降趨勢得以減緩)。因此，在相同條件下，適當增大Wi-Fi網(wǎng)絡(luò)服務(wù)率μw或cellular網(wǎng)絡(luò)服務(wù)率μc，可以有效提升數(shù)據(jù)包的個人收益Yp(q)及混合式接入網(wǎng)絡(luò)的性能體驗。

圖2 數(shù)據(jù)包個人收益的變化趨勢

3.2 社會最優(yōu)進隊概率

混合式接入網(wǎng)絡(luò)的社會收益Ys定義為單位時間內(nèi)進入系統(tǒng)的全部數(shù)據(jù)包在完成服務(wù)后所獲收益的總和。混合式接入網(wǎng)絡(luò)的社會收益Ys為

Ys(q)=qΛ(M-ND(q))

(17)

為了使社會收益Ys最大，混合式接入網(wǎng)絡(luò)的社會最優(yōu)進隊概率q*為

(18)

以pc=0.4、pw=0.6為例，圖3揭示了不同cellular網(wǎng)絡(luò)服務(wù)率μc和Wi-Fi網(wǎng)絡(luò)服務(wù)率μw下，混合式接入網(wǎng)絡(luò)的社會收益Ys(q)隨進隊概率q的變化趨勢。

圖3 混合式接入網(wǎng)絡(luò)社會收益的變化趨勢

由圖3可知，混合式接入網(wǎng)絡(luò)的社會收益Ys(q)隨進隊概率q從0開始快速增長，到達峰值后又呈現(xiàn)大幅下降的趨勢。當進隊概率q略低時，社會收益Ys(q)隨進隊概率q的加大呈現(xiàn)單調(diào)上升趨勢，而且社會收益Ys(q)的3條曲線在前期分散程度不明顯，在后期分散程度逐漸加大。當進隊概率q略高時，社會收益Ys(q)隨進隊概率q的加大呈現(xiàn)單調(diào)下降趨勢，并最終達到0點。在社會最優(yōu)進隊概率q*下，會有最高的社會收益Ys(q*)，也就是社會最優(yōu)策略下的收益。

4 智能尋優(yōu)算法和收費方案

4.1 智能尋優(yōu)算法的數(shù)值結(jié)果

為了獲得納什均衡進隊概率和社會最優(yōu)進隊概率，引入仿生群智能優(yōu)化算法?；依侵悄軆?yōu)化算法[15]是模擬自然界中灰狼種群抓捕獵物過程構(gòu)造的隨機群體算法。灰狼智能優(yōu)化算法的求解精確度與灰狼群體位置的初始值、預(yù)判獵物位置的收斂性質(zhì)及灰狼群體更新位置的方法密切相關(guān)。本文在原有灰狼智能優(yōu)化算法的基礎(chǔ)上，增加了混沌初始化，使得灰狼群體的初始位置分布更加均勻，從而提高全局搜索的精確度；在原有的非線性收斂函數(shù)基礎(chǔ)上，增加了收斂性較高的對數(shù)函數(shù)，以提升全局最優(yōu)解的確定速度。該算法的主要步驟如下。

步驟1設(shè)定初始迭代次數(shù)為t=1，最大迭代次數(shù)為tmax，灰狼種群數(shù)量為n，搜索空間上界為ub、下界為lb。

步驟2采用混沌logistic映射初始化第1次迭代(t=1)灰狼種群位置Xi(t)(i=1, 2,…,n)。

X1(t)=rand

%rand表示(0， 1)之間的隨機生成數(shù)%

fori=2:n

Xi(t)=uXi-1(t)(1-Xi-1(t))

%u為混沌因子，設(shè)定u=3.5%

endfor

步驟3計算灰狼種群的適應(yīng)度，依次找出最好的3個灰狼α、β、γ，位置分別為Xα(t)、Xβ(t)、Xγ(t)。

%在納什均衡下，適應(yīng)度絕對值最小的位置為最佳位置%

%在社會最優(yōu)下，適應(yīng)度最大的位置為最佳位置%

步驟4計算影響灰狼移動的協(xié)同系數(shù)。

C(t)=2rand

步驟5更新灰狼種群的位置。

fori=1:n

Y1=Xα(t)-A(t)|C(t)Xα(t)-Xi(t)|

Y2=Xβ(t)-A(t)|C(t)Xβ(t)-Xi(t)|

Y3=Xγ(t)-A(t)|C(t)Xγ(t)-Xi(t)|

ifXi(t+1)ub

Xi(t+1)=Xi(t)

endif

endfor

步驟6判斷迭代過程是否結(jié)束。

ift

t=t+1

轉(zhuǎn)到步驟3

else

輸出灰狼α的位置Xα(tmax)。

%在納什均衡條件下，Xα(tmax)作為納什均衡進隊概率qe%

%在社會最優(yōu)條件下，Xα(tmax)作為社會最優(yōu)進隊概率q*%

endif

設(shè)定tmax=50、n=12、ub=1、lb=0，利用改進的灰狼智能優(yōu)化算法，給出不同cellular網(wǎng)絡(luò)服務(wù)率μc和Wi-Fi網(wǎng)絡(luò)服務(wù)率μw下的納什均衡進隊概率qe和社會最優(yōu)進隊概率q*，如表1所示。

表1 納什均衡與社會最優(yōu)進隊概率

4.2 社會最優(yōu)進隊概率

從表1中，可以看出納什均衡進隊概率qe普遍要比社會最優(yōu)進隊概率q*大。為確保社會收益的最大化，需調(diào)整納什均衡進隊概率qe，使其與社會最優(yōu)進隊概率q*保持一致。因此，需要征收額外的接入費用支付給網(wǎng)絡(luò)服務(wù)商。假設(shè)接入費用為f，數(shù)據(jù)包進入系統(tǒng)后的平均收益變更為

Yp(q)=M-D(q)N-f

(19)

令Yp(q)=0，可得網(wǎng)絡(luò)用戶的接入費用為

f=M-D(q)N

(20)

將表1中社會最優(yōu)進隊概率q*帶入式(20)，得到不同cellular網(wǎng)絡(luò)服務(wù)率μc和Wi-Fi網(wǎng)絡(luò)服務(wù)率μw下的接入費用f，如表2所示。

表2 接入費用

5 結(jié) 論

在互聯(lián)網(wǎng)接入系統(tǒng)中，cellular網(wǎng)絡(luò)一般收費使用，Wi-Fi網(wǎng)絡(luò)則對特定用戶免費使用。移動用戶通常根據(jù)實際情況，交替使用cellular網(wǎng)絡(luò)和Wi-Fi網(wǎng)絡(luò)，即混合式接入網(wǎng)絡(luò)訪問互聯(lián)網(wǎng)?；谛畔⒉豢梢姷那樾危芯苛嘶旌鲜浇尤刖W(wǎng)絡(luò)的納什均衡策略和社會最優(yōu)策略。結(jié)合系統(tǒng)中數(shù)據(jù)包數(shù)量和接入網(wǎng)絡(luò)狀態(tài)建立馬爾可夫鏈，利用矩陣幾何解方法給出了移動用戶的平均響應(yīng)時間表達式。通過建立收益函數(shù)，從移動用戶個體出發(fā)，給出了納什均衡進隊策略，綜合考慮混合式接入網(wǎng)絡(luò)的服務(wù)提供者與移動用戶全體，給出了社會最優(yōu)進隊策略。針對不同cellular網(wǎng)絡(luò)服務(wù)率和Wi-Fi網(wǎng)絡(luò)服務(wù)率進行系統(tǒng)實驗，揭示出納什均衡進隊概率高于社會最優(yōu)進隊概率。改進灰狼智能尋優(yōu)算法，給出了納什均衡進隊概率和社會最優(yōu)進隊概率數(shù)值結(jié)果。面向數(shù)據(jù)包制定收費方案，實現(xiàn)了納什均衡進隊概率和社會最優(yōu)進隊概率的統(tǒng)一。本文的研究為混合式接入網(wǎng)絡(luò)的控制與管理提供了理論依據(jù)，同時也為排隊理論和博弈理論在混合式接入網(wǎng)絡(luò)中的應(yīng)用提供了有效途徑。