一個新穎的異構無線網絡接入選擇算法

崔 揚，徐玉濱，許榮慶，沙學軍

(哈爾濱工業大學通信技術研究所，150080哈爾濱，cuiyang_0305@163.com)

目前在無線接入領域中出現了大量使用不同無線接入技術和不同覆蓋面積的無線接入網絡.因此未來的無線通信網必將是異構的[1－2].為了在任何時間、任何地點都能夠獲得無縫的最佳服務，終端需要不斷地在不同的無線接入網之間進行接入選擇和垂直切換，因此異構網絡的接入選擇算法至關重要.文獻[3－5]提出了基于門限的接入選擇算法.文獻[6－8]提出了基于智能處理的接入選擇算法.這些算法在不同程度上都提高了用戶的QoS滿意度，同時允許系統容納更多的用戶.通過對上述文獻研究可以發現，首先上述算法在接入選擇中均沒有考慮到網絡的資源分配方式這一因素，其次這些算法著眼點都是對接入選擇算法的改進、考慮因素的增多或是某幾項性能指標的提升，都缺少對終端用戶接入選擇行為的合理解釋.對每個網絡來說所有用戶共享資源，每個用戶實際獲得速率除了取決于接收信號的質量和RAT的特性外，還取決于網絡為其分配資源的多少有關，因此有必要考慮網絡的資源分配方式.另外，從系統角度出發，整個異構無線網絡以最大化網絡吞吐量為目標控制各個終端用戶接入到相應的網絡中;但這樣往往使得部分用戶由于獲得較低的數據速率而無法得到更好的服務質量，以至于常常無法適用于實際系統.對于所有的用戶終端來說，其目的都是想在現有的條件下選擇1個能為其提供最高數據速率的網絡進行接入，由于無線資源的有限性，這種行為也就導致了用戶之間對于資源的獲取是相互競爭的.對于1個終端來說，其他終端的接入選擇結果將會影響自身最終的選擇，所以有必要對異構無線網絡中的接入選擇問題引入新的研究方法和理論，值得慶幸的是，非合作博弈理論可以為該研究提供堅實的理論基礎.非合作博弈論近些年被應用于解決無線網絡資源管理的問題中[9－11].文獻[12]和文獻[13]分別利用進化博弈和非合作博弈解決異構無線接入選擇問題，但都沒有考慮到用戶的信道條件和資源的分配方式，因此無法應用于實際網絡中.本文提出了1個基于非合作博弈的接入選擇算法:首先依據用戶實際的接收信號質量、RAT特性以及網絡的資源分配方式求出用戶接入網絡的實際速率，然后以最大化自身數據速率為目標建立基于非合作博弈理論的接入選擇模型，并利用納什均衡預測接入選擇結果.

1 系統模型和實際接入數據速率

1.1 系統建模

本文選取3種具有代表性的無線接入網絡來構成異構無線接入環境，如圖1所示.其中WMAN選用的是基于IEEE 802.16且具有單載波接口的WiMAX[14]，蜂窩網采用的是 3GPP 的 HSDPA[15]，局域網采用的是基于IEEE 802.11的WLAN[16].為簡化分析，本文選取了如圖1下半部分所示的特例，其中這三種無線接入網絡的基站中心相互重疊，該結構稍加改動就可以擴展為圖1中上半部分的形式.將終端所處的位置按照可接入的網絡數量進行劃分，大致分為3個服務區.在區域1中，只有WMAN的網絡覆蓋，所以位于該區的用戶只能接入WMAN中.而在區域2中的用戶，由于其同時位于WMAN和蜂窩網的覆蓋區，用戶可以選擇接入到這兩個網絡中任意1個.依據相同的道理，位于服務區3的用戶可以接入WMAN、蜂窩網和WLAN這3種網絡.其中位于這3個服務區的用戶數分別為N1、N2和N3.從節省能量的角度考慮，規定所有終端在任意時刻只能接入到1個網絡中.為了方便起見，WMAN、HSDPA和WLAN這3種網絡分別簡記為WM、CE和WLAN.

圖1 異構網絡的組成

1.2 實際接入數據速率

對于接入選擇來說，首先要對終端所選擇的無線接入鏈路的性能進行定量評估.而決定1個終端接入鏈路的性能主要有以下3個因素:

1)接收信號的質量.它可以用信干比(SINR)來進行描述，其物理意義是，發射功率減去傳播衰落后與接收端的噪聲和其他信號的干擾之和相比.其中傳播的衰落是由3部分組成的，第一部分是與傳播距離成指數關系的路徑損耗，第二部分是與地形有關的陰影衰落，前兩個為大尺度衰落，第三部分是由于信號多徑傳輸所造成的小尺度衰落.這三種衰落相互疊加構成了整個信號的衰減.

2)RAT的特性，例如信道帶寬和頻譜效率.對于使用多個接入鏈接的終端來說，每條接入鏈路的信干比SSINR都可以獨立計算.在獲得接收信號的SSINR后，要想獲得每個接入鏈路的實際速率，還需要知道每個RAT的特性，例如信道帶寬和頻譜效率.文獻[17]基于對信息論中的香農定理的修改提出了RAT性能的一般描述.這個描述提供了對實際RAT特點的簡單近似，為研究異構網絡的資源管理帶來了便利.于是任意1個RAT的容量均可由下式描述:

其中:B為載波的帶寬;SSINR為信干比，其具體值與用戶位于各個RAT小區中的位置有關;ΔSSINR為衰落因子，其實際值大約為10 dB左右;εmax為最大的頻譜效率，它由每個RAT具體使用的最高調制與編碼技術方案有關.因此利用式(1)可以對無線接入技術的近似容量做一般性的建模.

3)資源分配方式和負載狀態.式(1)描述了系統中單一用戶完全占有所有資源獲得的信道性能，即峰值速率.但實際系統中用戶不止1個，用戶之間需要共享資源.用戶實際獲得的資源大小往往和資源的分配方式及當前負載狀態有關，而目前的所有文獻中均沒有考慮到這一因素.因此當負載一定時，資源的分配方式將決定用戶接入網絡后的實際速率.為了說明這一問題，本文將考慮兩種典型的資源分配方式:集中式和分布式.對于集中式，每個用戶實際得到的數據速率為Ri(M)=CiG/N. (2)其中G為調度增益，它與具體每個網絡所使用的調度算法有關.例如當網絡使用公平比例算法時，調度增益與所有用戶的鏈路質量分布有關;當使用的是Roubin調度算法時，該值為1.N為當前在該系統中的用戶數，Ci是用戶i的峰值速率.目前的2G/3G以及未來的LTE系統均采用集中式的資源分配.假設接入網絡使用Roubin調度算法進行資源分配，那么式(2)則變成

而對于分布式，例如基于IEEE 802.11的WLAN，其一般使用的媒體接入協議(MAC)是基于沖突避免的多載波感知協議(CSMA/CA).于是用戶接入到WLAN網絡中的實際速率為[18]

2 基于非合作博弈論的接入選擇建模

在異構無線網絡中，整個網絡是由多個不同的無線接入網以及終端用戶組成的.這些終端用戶相互競爭資源，在這種情況下1個全局優化的解可能對于所有的實體來說并不是其想要的.例如使整個網絡的吞吐最大的解，不一定是使每個終端用戶都能滿意的解，因為為了使整個網絡的資源最大化，可能將更多的資源分配給信道條件最好的用戶，這使一些信道條件差的用戶無法得到服務或提供的服務無法滿足要求.為了解決上述問題，本文引入非合作博弈論來研究異構網絡中的接入選擇問題.在異構網絡中的每個終端用戶都會選擇1個為其提供最高數據速率的網絡進行接入，因而所有終端都是理性的.

在非合作博弈中，博弈理論的基本概念包括參與者、策略、行動、收益、信息、結果和均衡[19].其中參與者、策略和收益是非合作博弈不可缺少的3個要素.參與者指的是博弈中的決策主體，其目的是選擇使自己收益最大化的策略;策略指參與者依據給定的信息的行動規則，它規定了參與者何時選擇何種行動;收益指的是參與者在某一策略組合下所能獲得的好處，該值通常由1個效用函數表示，效用函數值越大，其收益也就越大.

由于區域1中的用戶只能接入到WM網絡中，因此本文只將區域2和區域3中的用戶作為博弈中的參與者.參與者i的策略pij(pi∈Pi)，指的是選擇哪種網絡接入，Pi為參與者i所有策略的集合，即所有可以選擇的接入網絡的集合.例如pi=wm，表示這個用戶選擇WM進行接入.用戶之間由于地理位置不同，所以每個用戶可以選擇接入的網絡數量不同，位于區域2和區域3中的用戶策略集合分別為

其中:U為1個擬凹的效用函數;X表示一次博弈的策略組合;Ri為用戶i在策略組合X下獲得實際速率.本文引入納什均衡來預測各個用戶終端以自我收益最大化為目的的接入選擇結果.納什均衡是非合作博弈的一種狀態，對于有N個參與者的博弈，在給定其他人策略的條件下，每個參與者選擇自己的最優策略從而使自己利益最大化.所有參與者的策略構成1個策略組合.納什均衡指的是由所有參與者的最優策略組成的策略組合，即在納什均衡的情況下，沒有任何參與者可以通過改變策略來提高自身的收益.其具體定義如下[19]:

其中X*為N個參與者的最優策略，X*pi表示只有參與者i改變策略組合X*中自己的策略.

3 求解納什均衡

納什均衡的定義本身并沒有說明怎樣求解納什均衡，它只是用來檢驗某個策略組合是否是納什均衡.因此在建立博弈模型后，需要借助其它的優化算法來求解.當博弈中的參與者數量很少，而且每個參與者的策略數量有限時，可以通過窮舉法或剔除劣策略法來找到納什均衡.但當用戶數較多以及策略空間較大時，就無法通過這些方法得到納什均衡，如本文中當區域2和區域3中的用戶數達到5和10時，整個策略空間大小為1 889 568.因此需要借助于智能優化算法來進行求解.

粒子群優化算法是一種基于群智能的進化計算技術，由 Eberhart和 Kennedy[20]提出.與螞蟻算法相比，粒子群算法對初始化參數的設置不敏感，且具有較好的收斂性;與遺傳算法相比，在相同性能要求下，有較快的收斂速度和較好的收斂性能.基本的粒子群算法是應用于連續優化問題的，但許多實際的工程問題都被描述為組合優化問題，于是Kenedy和Eberhart[21]提出了一種基于二進制離散粒子群算法，隨后Yang和Wang[22]受到物理學的啟示提出了離散量子粒子群優化算法.由于在所建立的博弈模型中，某些參與者的可選擇策略多于2種，例如區域3中的用戶可以選擇接入的網絡數量達到了3種，因此本文選擇使用離散量子粒子群算法進行求解.

在離散量子粒子群算法中，定義量子粒子群向量及其離散粒子向量分別為

其中α和β為量子粒子Q的控制參數，且滿足α+β=1和0＜α，β＜1;α越大，Q越靠近其理想值;Zglobalbest(t)為到目前t代為止，在整個粒子群中使得適應度函數值最小的離散粒子，其為全局最優粒子;Zk

localbest(t)為到目前t代為止，第k個粒子使得適應度函數值最小的離散粒子，其為局部最優點;ω、c1和c2表示下一代Q的產生依賴于自己、局部最優和全局最優的程度，滿足如下關系:

為了能夠利用離散量子粒子群算法求解接入選擇模型的納什均衡，需要將模型中的策略以離散量子粒子群中二進制數的方式來表示，具體如下:位于區域2中的用戶能夠選擇WM和CE中的任意1個網絡進行接入，而位于區域3中的用戶可以選擇WM、CE和WL中的任意1個網絡進行接入，因此對這兩個區域中用戶的策略分別用1個兩位和三位的二進制數表示，其中二進制數中的每一位對應1個網絡的選擇情況.區域2中用戶的二進制數從高比特位到低比特位分別對應WM和CE;區域3中用戶的二進制數從高位到低位分別對應WM、CE和WL.如果對應位上的比特數為1，則表示接入該網絡;為0則表示不接入該網絡.因此如－果位于區域2中的用戶策略pi=wm，那么它對應的兩位二進制數為(1 0)，同理當區域3中用戶的策略為pi=ce時，它對應的二進制數就為(0 1 0).于是將區域2和區域3中所有用戶策略二進制數依次連接就組成了1個大小為1×(N2×2+N3×3)的二進制向量.這樣就將策略組合X與離散粒子Zk建立起了對應關系，于是對于納什均衡策略的尋找就可以轉化為尋找使某一適應度函數最小的離散粒子.

根據納什均衡的定義建立離散量子粒子群算法的適應度函數，其定義如下:如果X為有效策略，

如果X為無效策略，

其中

通過式(6)產生的離散粒子向量可使一些用戶策略的二進制向量中出現所有比特位均為0或為1的比特位數量超過1個的情況.這就意味著這些用戶要么不接入任何網絡，要么同時接入的網絡數量超過1個，這與系統的假設模型不符.于是這樣的離散粒子對應的策略組合X是無效的.為了避免結果為無效的策略組合，當出現這樣的無效離散粒子向量時，其對應的適應度函數值將變為常數L，這個常數L的值遠遠大于所有有效策略組合的適應度函數值.由于離散粒子趨向于使適應度值為最小的方向變化，這樣可以確保離散量粒子不會向無效向量趨近，進而避免結果為無效策略組合.根據納什均衡的定義及性質就可以知道，當且僅當策略X為納什均衡解X*時，適應度函數取最小值0.

離散量子粒子群算法的工作流程如下:

1)隨機初始化Q(t)和Z(t)，將Z(t)作為所有用戶的初始網絡選擇結果，同時將設定為Z(t).

2)根據式(7)和(8)建立的適應度函數評估Z(t)，將適應度函數最小的 Z(t)存儲為

3)While(不出現終止條件)

t=t+1，利用式(3)～(6)更新Q(t)和Z(t);利用式(7)和(8)評估Z(t)，然后分別與進行比較，并更新

判斷終止條件，即Zglobalbest(t)的適應度函數值是否為零.

End

4)輸出選擇結果.

4 仿真與性能評估

假設選取的WMAN小區半徑為1 km，最大發生功率為80 W，帶寬為20 Hz，其峰值速率為10 Mb/s;蜂窩網的小區半徑分別為866 m.最大發射功率分別為20 W，峰值速率為14.4 Mb/s，具體的用戶鏈路峰值速率可以通過式(1)求出.WLAN網絡小區半徑為60 m，發射功率為1 W，帶寬為22 MHz.對于WMAN和CE使用的是城市無線傳播模型，其路徑損耗指數和陰影衰落分別為為3.52和8 dB.WL路徑損耗為每米減少0.3 dB，同時帶有3 dB的標準陰影衰落.用戶隨機分布在每個區域內.選取的效用函數為U(x)=a·x，其中a=1.離散量子粒子群算法中的參數為

表1為在區域1、區域2、區域3中用戶數分別為0、5、10的情況下(由于區域1中所選擇的用戶數大小與搜索空間大小無關，因此為了方便，取為0)，分別利用遺傳算法和離散量子粒子群算法運行5次求解納什均衡.從表1中可以清楚地看出，遺傳算法的平均迭代次數為284.8次，而離散量子粒子群的平均迭代次數為201.6，同時在圖2中列舉了其中的一次兩種算法的收斂狀態，從圖中也能清晰地看出離散量子粒子群算法的收斂所需的迭代次數較少.因此離散量子粒子群算法具有更高的收斂速率.

表1 DQPS算法與遺傳算法迭代次數比較

圖2 算法收斂性比較

圖3為區域1中用戶數變化對區域2和區域3用戶接入選擇的影響.其中區域2的用戶數為5，區域3中的用戶數為10.從圖2中可以清楚看出隨著區域1的用戶數由0增加到30時，區域2和區域3中的用戶選擇WM進行接入的數量分別由2和1均變為0，在區域2和區域3中選擇CE網絡的用戶數分別由3增加到5和由6增加到7.這主要是由于區域1中的用戶只能選擇WM進行接入，所以隨著其數量增多，WM在區域2和區域3中的可用資源將逐漸降低，如果位于這兩個區域的用戶選擇WM進行接入，將會相對于選擇其它負載較低的網絡進行接入獲得的數據速率要低.因此區域2和區域3中的用戶將會選擇接入負載較低的CE和WL.

圖3 N1變化對于整個網絡選擇結果的影響

圖4為描述當區域2中的用戶數增多時，區域2和區域3選擇各個接入網絡的數量的變化.其中區域1和區域3中的用戶數分別為1和10，區域2中的用戶數由2增加到5.從圖3中可以看出當區域2中接入CE網絡的用戶數由1增加到4，這是由于在區域2中更多的用戶能夠從CE網絡中獲得更高的數據速率.當區域2中選擇CE網絡的用戶數量由1到4逐漸增多，由于資源的有限性，進而導致區域3中選擇CE網絡的用戶數由7降到6，因而在區域3中選擇WL網絡的用戶數將增多，數量由2增加到了3.

圖4 N2變化對于整個網絡選擇結果的影響

圖5所示為區域1和區域2用戶數固定不變，區域3中用戶數逐漸增加時，區域2和區域3中選擇這3種接入網絡的用戶數量.其中當區域1和區域2的用戶數分別為1和5時，區域3的用戶由2增加到8.從圖4中可以清楚看出，隨著區域3中的用戶數量逐漸增加，此區域中的用戶選擇CE接入的數量逐漸增加，由0增加到5個，由于資源的有限性，區域2中選擇CE接入網的用戶數逐漸降低，由4變為3個;同時區域3中選擇WM的用戶也由0增加到1個.從上面的分析可以看出，本文提出的基于非合作博弈的接入選擇算法可以適應網絡的動態變化，同時也能夠合理地解釋用戶終端自我優化的競爭行為.

圖5 N3變化對于整個網絡選擇結果的影響

5 結論

本文對由 WiMAX、WCDMA的 HSDPA及WLAN三種無線接入網絡組成的異構網絡的接入選擇問題進行研究，提出了基于非合作博弈理論的接入選擇算法.引入非合作博弈理論描述終端自我優化的接入選擇行為，利用納什均衡預測用戶的最終選擇結果.納什均衡的定義本身并沒有說明怎樣求解納什均衡，它只是用來檢驗某個策略組合是否是納什均衡.因此，本文利用離散量子粒子群算法來求解納什均衡并與遺傳算法進行比較，結果顯示離散量子粒子群算法具有更快的收斂速度.最后利用仿真驗證了基于非合作理論的接入選擇算法能夠適應網絡的動態變化，同時獲得的接入選擇結果也能夠合理地解釋用戶終端之間自我優化的競爭行為.

[1]楊震.專題:異構網絡的協同與融合[J].中興通訊技術，2008，3:1－2.

[2]BUHLER J，WUNDER G.An optimization framework for heterogeneous access management[C]//Wireless Communications and Networking Conference.Budapest:[s.n.]，2009:1 －6.

[3]LEE S，GOLMIE N.Power-efficient interface selection scheme using paging of WWAN for WLAN in heterogenous wireless networks[C]//In Proceeding of ICC’2006.Stanbul，Turkey:[s.n.]，2006，4:1742 －174.

[4]MOLINARO A I A，CAMPOLO C，AMADEO M.An access network selection algorithm dynamically adapted to user needs and preferences[C]//In Proceeding of IEEE PIMRC＇2006.Helsinki，Finland:[s.n.]，2006:1－5.

[5]PEREZ-ROMERO J，SALLENT O，AGUSTI R N，etal.Radio access technology selection enabled by IEEE P1900.4[C]//Mobile and Wireless Communications Summit，16th IST.Piscataway:IEEE，2007:1－5.

[6]ADAMOPOULO E，DEMESTICHAS K，KOUTSORODI A.Intelligent access network selection in heterogeneous networks simulation results[C]//Wireless Communication Systems 2nd International Symposium on.Siena:[s.n.]，2005:279 －283.

[7]STEVENS-NAVARRO E，LIN Y，WONG V W S.An MDP-based vertical handoff decision algorithm for heterogeneous wireless networks[J].IEEE Transactions on Vehicular Technology，2007，57(2):1243－1254.

[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]LIN H，CHATTERJEE M，DAS S K，et al.ARC:an integrated admission and rate control framework for competitive wireless CDMA data networks using noncooperative games[J].IEEE Trans Mobile Comput，2005，4(3):243－258.

[10]KASTRINOGIANNIS T，PAPAVASSILIOU S.Game theoretic distributed uplink power control for CDMA networks with real-time services[J].Computer Communications，2009，32(1):376 －385.

[11]ALTMAN E，KHERANI A A，MICHIARDI P，et al.Non-cooperative forwarding in Ad-Hoc networks[J].Lecture Notes in Computer Science，2005，3462(1):569－578.

[12]NASERIAN M，TEPE K.Game theoretic approach in routing protocol for wireless ad hoc networks[J].Ad Hoc Networks，2009，7(3):569－578.

[13]NIYATO D，HOSSAIN E.Dynamics of network selection in heterogeneous wireless networks:an evolutionary game approach[J].IEEE Transaction on vehicular technology，2009，58(4):2008－2017.

[14]NIYATO D，HOSSAIN E.Noncooperative game-theoretic framework for radio resource management in 4G heterogeneous wireless access network[J].IEEE Trans on mobile computing，2008，7(3):332－345.

[15]IEEEE.IEEE 802.16 Standard-Local and Metropolitan Area Networks-Part 16[S].Piscatway:IEEE Std.，2003:35－47.

[16]HOLMA H，TOSKALA A.HSDPA/HSUP for UMTS:high speed radio access for mobile communications[M].Chichester:John Wiley and Sons Ltd，2006:15－19.

[17]IEEE.IEEE Std 802.11a-1999(R2003):Wireless LAN Medium Access Control(MAC)and Physical Layer(PHY)Specifications:High－speed Physical Layer in the 5 GHz Band[S].Piscataway:IEEEE，2003:23 －31.

[18]MOHR W.Spectrum demand for systems beyond IMT－2000 based on data rate estimates[J].Wireless Communications and Mobile Computing，2003，3(7):817 －835.

[19]HEUSSE M，ROUSSEAU F，SABBATEL G B.Performance anomaly of 802.11b[C]//Processing of Annual Joint Conference of the IEEE Computer and Communications Societies.Infocom:[s.n.]，2003，2:836 －843.

[20]KENNEDY J，EBERHART R.Particle swarm optimization[C]//Proc IEEE Int Conf on Neural Networks.Perth:[s.n.]，1995:1942 －1948.

[21]KENNEDY J，EBERHART R.A discrete binary version of the particle swarm algorithm[C]//Proc IEEE Int Conf on Systems， Man， and Cybernetics. Orlando:[s.n.]，1997:4104 －4108.

[22]YANG Shuyuan，WANG Min，JIAO Licheng.A quantum particle swarm optimization.Evolutionary Computation [C]//CEC2004.Congress on.Pairs:[s.n.]，2004，1:320－324.