基于Q學習的WLAN/WIMAX接入控制網絡選擇策略*

徐玉濱 陳佳美 馬琳

(哈爾濱工業大學通信技術研究所，黑龍江哈爾濱150080)

下一代無線通信系統將趨向于由若干個異構網絡組成［1-2］．多種無線接入技術將在同一個地區共存，有著不同性能的多模終端會通過時變的無線信道并提出不同的服務需求．這種需求使得接入控制技術的作用越來越得到重視，即解決如何在異構網絡環境中合理地接入呼叫用戶．接入控制算法的合理應用將會滿足不同用戶的QoS需求，并且能夠提高系統資源利用率．接入控制面臨的第一個問題就是網絡選擇，因此，異構網絡選擇技術在異構網絡性能保證上起著關鍵作用．

4G草案中提出將融合所有無線網絡技術，其中包括3G、WLAN 以及 WIMAX［3］．很多文獻中討論過3G與WLAN的融合，但遺憾的是對于WLAN與WIMAX的融合所做的研究并不是很多．考慮到未來無線網絡環境會相當復雜，多種不同類型的無線接入網絡會同時存在于一個地區，所以很有必要討論各種網絡的相互融合，以便在未來能夠提供給用戶服務質量最好且價格最合理的接入網絡．WLAN網絡的優點是傳輸速率高且價格便宜，但其覆蓋范圍有限，很難滿足未來網絡隨時隨地為用戶提供接入網絡的服務［4］．IEEE802．16能夠在大范圍內提供數據傳輸．于是很自然的趨勢就是結合 IEEE802．11和IEEE802．16建立一個完全的無線解決方案［5］．這個系統可以充分利用IEEE802．11提供的合理價格和IEEE802．16提供的廣泛覆蓋率，給用戶提供便宜且質量更高的服務．

很多著名的方法已經被提出來解決異構網絡選擇問題，這些方法可以分為兩類:基于測量的方法和基于模型的方法．基于測量的方法是有效且易于執行的，但是由于沒有任何理論基礎，所以很難得到全局優化．更進一步，有一種普遍的基于測量的方法名為多屬性決策，這種方法包括簡單多屬性決策(SAW)［6］、逼近理想解排序法(TOPSIS)［7］和灰度關系分析法(GRA)［8］．這些方法都是應用幾個QoS參數與相應的權重相乘，再求和，建立回報函數或者代價函數．這些權重一般來自于經驗或由幾個專家給出，并不精確，而且在服務類型確定后也不能適應網絡的動態變化．相反，基于模型的方法由于具有自適應特性而顯得更加靈活，因而很流行．但是，很多基于模型的方法［9］并沒有真正考慮到異構網絡本身自有的特性．文獻［10］中用馬爾可夫決策(MDP)方法解決網絡選擇問題，取得了較優的結果，但是它的狀態空間的維度和計算復雜度會隨著用戶數增加而激增，所以并不適合實際的網絡環境．鑒于此，文中提出一種不受模型約束的強化學習方法［11］，即Q學習方法，來解決異構網絡接入控制中的網絡選擇問題;從一個新的角度分析異構網絡的網絡狀態，使網絡狀態估計更加準確，從而有利于系統做出更加準確的接入判斷．

1 系統模型

系統做出網絡選擇判決之前首先需要了解各個子網絡的網絡狀態，因為只有充分了解網絡的負載和信道等條件，才能在用戶發出接入請求之后，判斷接入還是拒絕接入該用戶，若接入，還要判斷接入哪個子網絡．因此網絡狀態分析顯得尤為重要．

1．1 WLAN 系統測量

IEEE802．11標準定義了兩種基本的媒體接入控制(MAC)機制，即強制實現的分布式協調機制(DCF)和可選的集中式協調機制(PCF)［12］．由于PCF是可選的MAC協議，絕大多數802．11的產品并不支持PCF，因此文中主要關注DCF下容量的研究．

DCF是一種基于載波偵聽多點接入/沖突檢測標準協議(CSMA/CA)的訪問機制．文中分析DCF提供的一種可供選擇的4次握手技術，即RTS/CTS(Request-To-Send/Clear-To-Send)機制下的有效帶寬．圖1為其工作原理圖，觀察站點是所觀察的準備發送數據的站點，它在發送數據前，先偵聽信道，發現圖中站點A正在發送數據，站點B接收數據，則該站點延遲發送，并將自己的狀態設置成“信道被占用”，并退避一段時間［12］．退避之后繼續再一次監聽信道，當檢測到信道持續空閑(DIFS)時間時，并不是立即發送數據，而是代之發送一個請求發送幀(RTS)，當接收站點收到RTS信號后，立即在一個短針幀間間隔(SIFS)內，回應一個準許發送幀(CTS)，告知對方已經準備好接收數據．只有當雙方在成功交換RTS/CTS信號后才開始真正的數據傳輸，其他接收站點檢測到信道中的RTS/CTS信號后，會更新其狀態為“信道被占用”，然后退避一段時間．觀察站點在兩種情況下認為信道處于忙的狀態，一種是自己的狀態處于“信道被占用”，這意味著信道正在被另一個接收站點占用;另一種情況是信道被該接收站點本身作為發送者或接收者占用．這樣，累積這些信道忙的時間間隔，站點便能夠估計信道利用率以及可用帶寬．

圖1 WLAN系統DCF的工作原理Fig．1 DCF operational principle of WLAN system

假設觀察時間為 ，在該段觀察時間內信道被數據傳輸所占用的時間可以表示為

式中，Tdata_busy表示信道被其他站點(如站點A)占用的時間內用來傳輸數據所用的時間，Tdata_trans表示觀察站點在競爭到傳輸周期后傳輸數據所用的時間．那么信道利用率就可寫為

然而，如圖1所示，在信道忙時并不是所有時間都用來傳輸數據，因為CSMA/CA還明確規定了SIFS以及DIFS等幀間間隔，以及隨機回退時間等．由此可以得到信道忙期的時間內純粹用來傳輸數據的比例為

式中，μdata為觀察站點所要傳輸的平均數據長度，其以字節為單位．μR/C/A為RTS/CTS/ACK幀的長度總和，TSIFS、TDIFS分別為SIFS和DIFS的持續時間，Tbackoff(t)為平均隨機回退時間，C(t)為時間t處的數據速率．通過以上的信息就能計算可用帶寬，即

1．2 WIMAX 系統測量

與WLAN類似，文中也為WIMAX網絡進行網絡負載能力分析，即網絡狀態分析．需要注意的是，WIMAX中的資源分配方法與WLAN中是不同的．WLAN中的資源是被多個用戶以競爭的方式共享，但是WIMAX中的資源被基站分為上行和下行兩部分，因此在考慮網絡負載能力時，需要分別考慮上、下行兩方面的資源［13］，可用帶寬應該為

假設將WIMAX中的帶寬資源以數據突發的形式分配．每個數據突發包含幾個整數倍的物理時隙(PSs)．定義Tframe為傳輸一幀所需的時間，SDL-total與SUL-total分別為上、下行一幀中的總的物理時隙數．假設在觀察時間 內，存在整數倍的幀個數．那么幀的個數可以表示為

為了更清楚地說明問題，下面給出了各個時間概念之間的關系:

那么，時間內空閑的物理時隙數為

式中，SDL-used(i)、SUL-used(i)分別為每一個上行、下行的幀里被占用的PSs數．

根據上面的介紹，WIMAX的上、下行可用帶寬分別可表示為

式中，CDL-slot(t)、CUL-slot(t)分別是上、下行的一個PSs中能夠傳輸的比特數．

2 Q學習基礎

當一個系統所做出的決策不僅依賴于環境當前的狀態，也依賴于接下去的狀態以及他們相關的動作時，強化學習就成了這種優化決策的一個合適的學習技術［14-15］．文中接入控制的優化策略通過一種不受模型約束的強化學習方法即Q學習方法得到．

Q學習系統用一個控制者(學習者)來學習如何通過歷史經驗優化它的決策．在決策時隙t，控制者觀察到環境的當前狀態st然后執行動作at．執行動作后，環境會通過給予控制者正回報或負回報rt+1來指示所執行的動作正確與否，而后轉換到下一個新狀態st+1．控制者的最終目的是為所有狀態s找到最優策略*(s)∈A，也就是一系列動作{a1，a2，…}，其能夠使得系統的總期望折扣回報最大．系統的總期望折扣回報能夠被定義為一個值函數，其表達式如下

式中，E代表取期望操作，rt為在時間t得到的回報函數．在Q學習中這個回報函數不需事先定義，而只需要定義在每個狀態下執行動作后的立即回報即可．γ為折扣因子，它是立即回報的重要性表現且0≤γ≤1．最優值函數V*s為

式中，rs(a)為在當前狀態動作對(s，a)下得到的立即回報．該立即回報不是整體的回報函數，而是一個實時回報值，更加能夠體現算法的自適應性．V*s為未來執行了最優可用動作后的期望折扣回報，那么最優策略可以表達為

Q學習不需知道回報函數及狀態間轉移概率的具體分布便能得到最優決定策略*．為獲得獨立性，式中方括號內部分被定義為Q值，用Qs(a)表示，即

式中，Vs'為系統在下一狀態s'的值函數．繼而定義最優Q值(a)，

式中，ac表示所有可選動作，Qs，t+1(a)為經過更新之后的Q值，α為學習參數，一個Q學習控制者在每個特殊的狀態st執行一個動作，并通過在未來獲得的立即回報或懲罰估計動作執行的結果．通過在不同的時隙執行動作，它學習到最優動作，即能夠獲得長期的最大折扣回報的動作．

3 接入控制算法設計

3．1 動作與回報定義

異構網絡中用戶偏向于選擇總是能夠獲得最好服務的網絡，基于此，應該設計算法合理地將用戶接入WLAN網絡或WIMAX網絡，所以定義所執行的動作:

在每個狀態下執行動作后就獲得立即回報，這個立即回報與動作執行后的網絡負載性能有關．如果一個用戶被接入到WLAN網絡，獲得立即回報rs(a)=1，若其被接入到WIMAX網絡，同樣rs(a)=1．如果兩個網絡都沒有足夠的資源，那么該呼叫就被阻塞，立即回報rs(a)=-2．

3．2 Q學習算法步驟

圖2是異構網絡接入控制的Q學習過程的結構圖．

圖2 接入控制系統的Q學習框架Fig．2 Framework of Q-learning in the access control system

定義向量

則系統的狀態向量可表示為

對于每個狀態st都有一系列可用動作A={a1，a2，…，ak}，每個可用動作代表選擇一個子網絡．因此，此算法不僅可以用于WLAN和WIMAX網絡，還可以容易地被擴展到多個網絡．Q學習算法的控制者執行一個動作然后計算回報rs(a)．根據這個回報，控制者按照公式更新每個動作對應的Q值表．具體的Q學習步驟如下:

(1)初始化Q值表．

(2)在每個新呼叫到達時:①在動作集選擇可用動作并記錄該動作;②在用戶到達時間記錄系統狀態st時，在執行動作后記錄下一狀態st+1．

(3)當異構網絡狀態變化后，計算立即回報rs(a)．

(4)根據下式更新Q值:

(5)令ΔQ(s，a)為Q值更新前后的值之間的差值．如果滿足 ΔQ(s，a)＜ ε，?s∈S，a∈A，則說明收斂條件滿足;否則繼續返回執行步驟(2)-(4)．

4 算法驗證與仿真分析

4．1 仿真環境

仿真考慮一個融合的WLAN/WIMAX系統，其包含一個WLAN網絡和一個WIMAX網絡．WLAN系統重疊覆蓋在WIMAX系統之上．WLAN的基站AP的覆蓋半徑是100 m．物理層應用IEEE802．11b協議，平均比特速率是11 Mb/s，并且應用瑞利信道模型．信標間隔為20 ms;CFP的最大持續時間為15ms;物理層的時隙為9 μs．WIMAX基站與網絡邊緣的最遠距離是1000m，物理層應用IEEE802．16e協議，支持的數據速率是24Mb/s．

學習因子α設置為0．1，折扣因子γ設置為0．95．這兩個參數由經典的文獻給出［16］．對于18個用戶進行考察，并假設用戶在任意時間內必在WLAN或者WIMAX的覆蓋范圍內．假設WLAN/WIMAX融合網絡的新呼叫服從泊松分布，平均到達速率為 ．定義平均到達速率和一個呼叫的平均持續時間為話務強度．假設用戶在WIMAX網絡內平均分布，并且對于每個用戶的移動模型應用經典的隨機行走模型．類似地，WLAN中的所有用戶位置也是隨機分布的．基于蒙特卡洛進行仿真．

4．2 仿真結果

仿真比較了文中提出的Q學習算法與文獻［10］中提出的馬爾科夫決策(MDP)算法的性能．

圖3(a)、3(b)分別給出了語音和數據呼叫業務的阻塞率隨呼叫到達率的變化趨勢．可以看到隨呼叫到達率的增大，業務阻塞率隨之增大．這是由于，呼叫到達率越大，被占用的網絡資源越多，因此越容易發生阻塞．并且，Q學習算法的阻塞率性能明顯優于MDP算法，在到達率高時，Q學習算法的優勢更加明顯．這是由于在到達率低時，網絡內用戶少，可用資源充足，兩者都能保持較低阻塞率，隨著用戶到達率的增大，由于Q學習算法考慮了更加符合實際的、也是更重要的系統能力測量參數，而且Q學習算法的自我學習的性能使其能夠更好適應網絡動態變化，從而能夠獲得更低的阻塞率．

圖3 呼叫阻塞率隨用戶呼叫到達率的變化曲線Fig．3 Call blocking probability curves with the arrival rate

由圖3還可以看出，呼叫阻塞率達到穩定后，語音業務的阻塞率大于數據業務的阻塞率，這是由于給語音和數據業務分配了不同的排隊模型．由于語音業務用戶通常在呼叫發生阻塞后將不會等待，所以沒有給語音用戶建立排隊模型，即語音用戶在呼叫得不到服務后會立即離開網絡;對數據業務用戶則采用M/M/n排隊模型，因此其穩態阻塞率會比語音用戶低．

圖4為系統獲得的總折扣回報．很明顯可以看出，Q學習算法都能夠獲得比MDP算法更大的總回報，其原因是Q學習算法能夠更精確地反應系統的狀態，從而做出準確的接入決策．另外，由于Q學習算法具有自學習能力，其能夠隨環境變化而自適應地變化接入策略，因此，應用Q學習算法能夠接入更多的用戶，并且同時保證業務的QoS．兩條曲線平直的原因是仿真中每次仿真設置的用戶數是一樣的，所以在算法收斂后，取得的回報是相等的．這也說明，回報的大小和到達率是沒有關系的，只和應用的算法和仿真次數有關．

圖4 總折扣回報隨用戶呼叫到達率的變化曲線Fig．4 Total discount reward curves with the arrival rate

圖5 學習因子α對收斂性指標ΔQ(s，a)的影響Fig．5 Influence of learning parameter α to convergence performanceΔQ(s，a)

5 結論

提出一種不受模型約束的Q學習方法，用以解決WLAN/WIMAX異構網絡中的接入控制問題．算法從一個新的角度分析了WLAN和WIMAX兩種網絡的狀態，從而能夠更加符合實際的反應網絡的負載能力變化，為Q學習算法提供更加精確的底層參數．系統應用值迭代的思想逼近Q值，從而獲得了使系統總回報達到最大的最優策略．仿真結果表明，所提出的Q學習算法比傳統的基于MDP的算法能夠獲得更高的期望總回報和更低的呼叫阻塞率．

［1］Lu Ke-jie，Qian Yi，Guizani Mohsen，et al．A framework for a distributed key management scheme in heterogeneous wireless sensor networks［J］．IEEE Transactions on Wireless Communications，2008，7(2):639-647．

［2］Lai Yen-cheng，Lin Phone，Cheng Shin-ming．Performance modeling for application-level integration of heterogeneous wireless networks［J］．IEEE Transactions on Vehicular Technology，2009，58(5):2426-2434．

［3］Angoma Blaise，Erradi Mohammed，Benkaouz Yahya，et al．HaVe-2W3G:averticalhandoffsolutionbetween WLAN，WiMAX and 3G networks［C］∥International Wireless Communications and Mobile Computing Conference．Istanbul:IEEE CS，2001:101-106．

［4］Zhai Hong-qiang，Chen Xiang，Fang Yu-guang．How well can the IEEE 802．11 wireless LAN support quality of service?［J］．IEEE Transactions on Wireless Communications，2005，4(6):3084-3094．

［5］Nie Jing，Wen Jiang-chuan，Dong Qi，et al．A seamless handoff in IEEE 802．16a and IEEE 802．1 in hybrid networks［C］∥International Conference on Communications，Circuits and System．Hong Kong:IEEE CS，2005:383-387．

［6］Lee SuKyoung，Sriram Kotikalapudi，Kim Kyungsoo，et al．Vertical handoff decision algorithms for providing optimized performance in heterogeneous wireless networks［J］．IEEE Transactions on Vehicular Technology，2009，58(2):865-881．

［7］Zhang Wen-hui．Handover decision using fuzzy MADM in heterogeneous networks［C］∥Wireless Communications and Networking Conference．Atlanta:IEEE Inc，2004:653-658．

［8］Stevens-Navarro Enrique，Wong Vincent W S．Comparison between vertical handoff decision algorithms for heterogeneous wireless networks［C］∥IEEE 63rd Vehicular Technology Conference．Melbourne:IEEE Inc，2006:947-951．

［9］Gelabert Xavier，Perez-Romero Jordi，Sallent Oriol，et al．A Markovian approach to radio access technology selection in heterogeneous multiaccess multiservice wireless networks［J］．IEEE Transactions on Mobile Computing，2008，7(10):1257-1270．

［10］Yu Fei，Krishnamurthy Vikram．Optimal joint session admission control in integrated WLAN and CDMA cellular networks with vertical handoff［J］．IEEE Transactions on Mobile Computing，2007，6(1):126-139．

［11］Venkatesh T，Kiran Y V，Murthy C S R．Joint path and wavelength selection using Q-learning in optical burst switching networks［C］∥IEEE International Conference on Communications．Dresden:IEEE Inc，2009:1-5．

［12］IEEE 802．11 WG，Part 11:Wireless LAN medium access control(MAC)and physical layer(PHY)specifications．IEEE Standard［S］．

［13］IEEE 802．16 WG，Part 16:Air interface for fixed broadband wireless access systems．IEEE Standard ［S］

［14］Saker L，Ben Jemaa S，Elayoubi S E．Q-learning for joint access decision in heterogeneous networks［C］∥IEEE Wireless Communications and Networking Conference．Budapest，Hungary:IEEE CS，2009:1-5．

［15］Zhang Dong-mei，Ma Hua-dong．A Q-learning-based decision making scheme for application reconfiguration in sensor networks［C］∥International Conference on Computer Supported Cooperative Work in Design．Melbourne:IEEE CS，2007:1122-1127．

［16］Nasri Ridha，Altman Zwi，DubreilHervé．Optimal tradeoff between RT and NRT services in 3G-CDMA networks using dynamic fuzzy Q-learning［C］∥The 17th Annual IEEE International Symposium on Personal，Indoor and Mobile Radio Communications．Helsinki:IEEE Inc，2006:1-5．