無(wú)線密集網(wǎng)絡(luò)中的低損耗多臂老虎機(jī)算法*

趙耀，羅喜良

(1 上?？萍即髮W(xué)信息科學(xué)與技術(shù)學(xué)院， 上海 201210； 2 中國(guó)科學(xué)院上海微系統(tǒng)與信息技術(shù)研究所， 上海 200050； 3 中國(guó)科學(xué)院大學(xué)， 北京 100049) (2020年1月14日收稿； 2020年4月20日收修改稿)

異構(gòu)網(wǎng)絡(luò)的快速發(fā)展在各類(lèi)無(wú)線網(wǎng)絡(luò)應(yīng)用中發(fā)揮中極其重要的作用，例如，物聯(lián)網(wǎng)、車(chē)聯(lián)網(wǎng)、智慧工廠等。而為了應(yīng)對(duì)正在快速增長(zhǎng)的無(wú)線數(shù)據(jù)量的需求，無(wú)線網(wǎng)絡(luò)密集化，即密集組網(wǎng)被認(rèn)為是下一代無(wú)線網(wǎng)絡(luò)發(fā)展的必然趨勢(shì)之一[1]。各種類(lèi)型小型基站，例如，微基站、皮基站、飛基站的密集布置對(duì)于擴(kuò)大小區(qū)的覆蓋范圍以及增強(qiáng)用戶(hù)基站之間鏈接的通信質(zhì)量大有裨益，而相比較于只有宏基站部署的解決方案，各種小型基站的密集部署也有利于不同區(qū)域的頻譜復(fù)用。

但是無(wú)線網(wǎng)絡(luò)的密集化往往會(huì)導(dǎo)致嚴(yán)重的網(wǎng)絡(luò)頻繁切換的問(wèn)題，有時(shí)也被稱(chēng)之為網(wǎng)絡(luò)的乒乓效應(yīng)，其會(huì)嚴(yán)重影響到網(wǎng)絡(luò)性能，這也是目前密集無(wú)線網(wǎng)絡(luò)面臨的主要挑戰(zhàn)之一。

為解決這一問(wèn)題，近年來(lái)已有的很多研究工作把目光集中在自組織網(wǎng)絡(luò)(self-organizing network, SON)中，并且這也是最早在3GPP Rel-8標(biāo)準(zhǔn)中提出的解決方案。

Lee和Cho[2]提出一個(gè)用戶(hù)集體網(wǎng)絡(luò)切換的解決方案，該方案通過(guò)優(yōu)化用戶(hù)接入初期階段的延遲來(lái)降低網(wǎng)絡(luò)中斷的概率。Fischionei等[3]提出混合型的系統(tǒng)模型來(lái)優(yōu)化用戶(hù)接入，并且該項(xiàng)工作同時(shí)考慮了用戶(hù)的移動(dòng)速度以及用戶(hù)的距離造成的影響。文獻(xiàn)[4]提出一個(gè)馬爾科夫分析模型，利用特定的場(chǎng)景參數(shù)，例如路徑損耗參數(shù)、用戶(hù)移動(dòng)速度，以及小區(qū)負(fù)載等等，最終得到依場(chǎng)景變化的最優(yōu)網(wǎng)絡(luò)切換解決方案。Ye等[5]提出一個(gè)分布式負(fù)載感知的用戶(hù)接入算法，該算法復(fù)雜度低且考慮了負(fù)載均衡以及用戶(hù)接入過(guò)程中涉及的頻譜劃分等因素。文獻(xiàn)[6]從降低能量消耗的角度出發(fā)，優(yōu)化在用戶(hù)接入過(guò)程中的頻譜分配及功率分配。孟慶民等[7]提出一種基于馬爾科夫鏈預(yù)測(cè)的切換方案，在觸發(fā)網(wǎng)絡(luò)切換時(shí)會(huì)預(yù)測(cè)下一個(gè)基站的相關(guān)狀態(tài)信息。

但是以上的這些工作其實(shí)都很少考慮用戶(hù)頻繁切換網(wǎng)絡(luò)的這個(gè)問(wèn)題。在相關(guān)的參考文獻(xiàn)當(dāng)中，想嘗試解決該問(wèn)題更多地還是依賴(lài)于機(jī)器學(xué)習(xí)的方法。例如文獻(xiàn)[8]借助于深度強(qiáng)化學(xué)習(xí)訓(xùn)練得到一個(gè)最優(yōu)的系統(tǒng)控制器，該控制器可以用來(lái)降低網(wǎng)絡(luò)切換的次數(shù)同時(shí)也保障了網(wǎng)絡(luò)的吞吐量性能。目前為止和本文工作最相關(guān)的是文獻(xiàn)[9]，在該項(xiàng)工作當(dāng)中，作者首次論述建立無(wú)線網(wǎng)絡(luò)切換過(guò)程和多臂老虎機(jī)模型之間的等價(jià)性，除此以外該文獻(xiàn)也提出一種改進(jìn)的置信區(qū)間上界(upper-confidence bound, UCB)策略以較低復(fù)雜度來(lái)解決用戶(hù)接入頻繁切換的問(wèn)題。

1 系統(tǒng)模型

1.1 網(wǎng)絡(luò)模型

考慮一個(gè)區(qū)域范圍內(nèi)的無(wú)線密集網(wǎng)絡(luò)，如圖1所示，該區(qū)域內(nèi)部署了前文所述的各類(lèi)型基站:宏基站、微基站、皮基站、飛基站。這些基站的集合表示為

B={1,2,…,N},

(1)

其中N為基站總數(shù)目。用戶(hù)的集合表示為

U={1,2,…,K},

(2)

所有這些基站都可以為其覆蓋范圍內(nèi)的用戶(hù)提供無(wú)線服務(wù)。

圖1 無(wú)線密集網(wǎng)絡(luò)示意圖Fig.1 Wireless dense network

為描述簡(jiǎn)潔，本文假設(shè)時(shí)間尺度劃分為均等長(zhǎng)度的時(shí)隙。在傳統(tǒng)的無(wú)線網(wǎng)絡(luò)系統(tǒng)中，用戶(hù)接入與切換往往是由配備在基站端的控制器來(lái)決定的。但是很多研究已經(jīng)表明在下一代無(wú)線網(wǎng)絡(luò)系統(tǒng)中，由于網(wǎng)絡(luò)的高度異構(gòu)性，網(wǎng)絡(luò)用戶(hù)主導(dǎo)的接入方案正成為主流的趨勢(shì)[1,10]，這也是本文中所考慮的用戶(hù)接入機(jī)制模型。

對(duì)于某一個(gè)特定的網(wǎng)絡(luò)用戶(hù)，記該用戶(hù)在時(shí)隙t所選擇建立鏈接的基站為at∈B。那么在總時(shí)間長(zhǎng)度T范圍內(nèi)的用戶(hù)接入模式可以表示為

Θ=(a1,a2,…,aT).

(3)

本文并不考慮其他復(fù)雜的接入模式，例如，3GPP Rel-12中的雙連接，即一個(gè)用戶(hù)可以同時(shí)接入2個(gè)不同的基站接受服務(wù)。

用戶(hù)在時(shí)隙t結(jié)束后會(huì)立即收到獎(jiǎng)勵(lì)u(t,at)。在本文中，我們旨在建立適用于用戶(hù)接入模型的通用框架和解決思路，故在此并不指定這里獎(jiǎng)勵(lì)的具體指標(biāo)。在實(shí)際的系統(tǒng)當(dāng)中，這里的獎(jiǎng)勵(lì)通?？坍?huà)的是某項(xiàng)網(wǎng)絡(luò)性能指標(biāo)的優(yōu)化，例如，最大化數(shù)據(jù)吞吐量、最小化網(wǎng)絡(luò)時(shí)延，或者是最小化用戶(hù)能量消耗等。

假設(shè)獎(jiǎng)勵(lì)由一個(gè)隨機(jī)變量產(chǎn)生，出于理論分析的方便，這里將獎(jiǎng)勵(lì)歸一化至0～1。每一個(gè)基站都有各自的隨機(jī)變量，其數(shù)學(xué)期望表達(dá)為

ui=E[u(t,i)],i=1,…,N,

(4)

為方便表達(dá)同時(shí)也不失一般性，令這里的N個(gè)數(shù)學(xué)期望是依升序排列

u1≤u2≤…≤uN,

(5)

同時(shí)記它們之間的均值差距為

(6)

從時(shí)隙1開(kāi)始計(jì)時(shí)至?xí)r隙T為止，該用戶(hù)所接受到的總獎(jiǎng)勵(lì)可以表示為

(7)

用戶(hù)的目標(biāo)是在缺乏關(guān)于可向其提供無(wú)線服務(wù)的這N個(gè)基站的準(zhǔn)確統(tǒng)計(jì)信息情況下最大化其可以獲得的總獎(jiǎng)勵(lì)量。而為了實(shí)現(xiàn)這一優(yōu)化目標(biāo)，用戶(hù)需要在盡可能短的時(shí)間內(nèi)分辨出有最高數(shù)學(xué)期望獎(jiǎng)勵(lì)的那個(gè)最優(yōu)基站。而想要做到這一點(diǎn)就需要對(duì)每個(gè)基站進(jìn)行足夠的接入嘗試，以對(duì)其分布做足夠的采樣估計(jì)。在實(shí)際系統(tǒng)中，若以最大化獎(jiǎng)勵(lì)為目標(biāo)，則用戶(hù)所采用的決策就必須平衡好“探索”與“利用”之間的均衡。一方面，用戶(hù)為了增加眼前的獎(jiǎng)勵(lì)，決策應(yīng)偏向盡可能 “利用”經(jīng)驗(yàn)最佳基站；另一方面，如果是從長(zhǎng)遠(yuǎn)角度考慮，用戶(hù)需要更多地“探索”其他基站以找到可能潛在的性能更佳的基站。為平衡這種關(guān)系，一種流行的方法在統(tǒng)計(jì)學(xué)以及機(jī)器學(xué)習(xí)領(lǐng)域內(nèi)廣泛使用，該方法是將“探索”與“開(kāi)發(fā)”困境建模為多臂老虎機(jī)問(wèn)題[11]。

解決多臂老虎機(jī)問(wèn)題的經(jīng)典算法為置信上界算法[12]。該方法為多臂老虎機(jī)的N個(gè)操縱桿維護(hù)它們各自的置信上界

(8)

用戶(hù)在每一個(gè)時(shí)隙開(kāi)始時(shí)做出決策決定其在該時(shí)隙內(nèi)選擇建立鏈接的基站。我們稱(chēng)用戶(hù)觸發(fā)了一次網(wǎng)絡(luò)切換為用戶(hù)在相鄰的2個(gè)時(shí)隙選擇了不同的基站接入。用戶(hù)觸發(fā)一次網(wǎng)絡(luò)切換會(huì)造成一些額外的損失，例如，時(shí)延、能量消耗或者是額外的頻譜資源開(kāi)銷(xiāo)用來(lái)發(fā)送網(wǎng)絡(luò)切換的控制信號(hào)。所以，頻繁的網(wǎng)絡(luò)切換很可能會(huì)嚴(yán)重降低服務(wù)質(zhì)量(quality of service, QoS)以及體驗(yàn)質(zhì)量(quality of experience, QoE)。與文獻(xiàn)[8]及文獻(xiàn)[10]類(lèi)似，假設(shè)每一次切換會(huì)導(dǎo)致固定的損失C，那么在使用給定算法Π情況下，截止到時(shí)隙T為止，用戶(hù)的網(wǎng)絡(luò)切換損失可以表達(dá)為

(9)

這里1S表示事件S的指示函數(shù)。

由此可見(jiàn)，雖然多臂老虎機(jī)模型很好地刻畫(huà)了“探索”與“利用”之間的均衡問(wèn)題，但是這種方法無(wú)法直接運(yùn)用于用戶(hù)接入問(wèn)題，因?yàn)樵撍惴ㄐ枰诟鱾€(gè)基站之間反復(fù)切換。而該問(wèn)題在無(wú)線網(wǎng)絡(luò)中會(huì)尤其嚴(yán)重?？紤]如下場(chǎng)景，當(dāng)擁有最高數(shù)學(xué)期望獎(jiǎng)勵(lì)的2個(gè)基站之間的數(shù)學(xué)期望差距ΔN-1非常小的時(shí)候，該算法很難區(qū)分哪一個(gè)才是最好的，從而陷入在二者之間反復(fù)切換的僵局。為克服這一問(wèn)題，在文獻(xiàn)[13]中，算法設(shè)置在運(yùn)行足夠長(zhǎng)的時(shí)間后終止探索過(guò)程，進(jìn)而選擇任意一個(gè)足夠好的基站一直建立鏈接。

1.2 在線學(xué)習(xí)中的后悔值與切換次數(shù)上界

為評(píng)價(jià)以置信上界算法等為代表的在線學(xué)習(xí)算法的性能優(yōu)劣，常用的性能指標(biāo)為后悔度。該指標(biāo)定義為截止到T時(shí)所獲得的總獎(jiǎng)勵(lì)與一直采用最高獎(jiǎng)勵(lì)均值的決策之間的差值。通常在理論分析時(shí)，關(guān)注的是后悔度的數(shù)學(xué)期望

(10)

Auer等[12]的早期工作已經(jīng)表明傳統(tǒng)置信上界算法的期望后悔度有嚴(yán)格上界：O(logT)，這意味著該算法的后悔值是時(shí)隙T的高階無(wú)窮小量，但同時(shí)文獻(xiàn)也指出該算法運(yùn)行時(shí)在不同操作桿之間切換次數(shù)的數(shù)學(xué)期望上界也是O(logT)。而這就意味著在無(wú)線密集網(wǎng)絡(luò)問(wèn)題中，由于網(wǎng)絡(luò)切換帶來(lái)的損失不可忽略，置信上界算法無(wú)法直接運(yùn)用。

Shen和Schaar[9]提出一種直接的改進(jìn)置信上界算法并給出了理論分析。在該算法中，連續(xù)的k個(gè)時(shí)隙會(huì)被組合在一起成為一個(gè)大時(shí)隙，并且k會(huì)從1開(kāi)始逐一增加。在這連續(xù)的k個(gè)時(shí)隙內(nèi)，用戶(hù)只在第一個(gè)時(shí)隙開(kāi)始時(shí)做出決策選擇基站并一直與該基站保持接入。作者證明了在該策略下，其依舊能保證以O(shè)(logT)為上界的期望后悔度，但用戶(hù)在不同基站之間切換次數(shù)的數(shù)學(xué)期望上界可以降低為：o(logT)。這樣一來(lái)就可以保證用戶(hù)在不同基站之間切換造成的損失在階數(shù)上可以忽略不計(jì)。

2 高效的用戶(hù)接入策略

本節(jié)首先提出基于操作桿淘汰機(jī)制的一種用戶(hù)接入算法。隨后的理論分析可以表明，該算法在保持期望后悔度上界O(logT)不變的情況下，可以將用戶(hù)在不同基站之間切換次數(shù)的數(shù)學(xué)期望上界降低為常數(shù)階。相比較于前文提到的算法有重要改進(jìn)。

2.1 基于淘汰機(jī)制的用戶(hù)接入算法

每個(gè)回合的均等采樣步驟所需要的時(shí)隙總數(shù)由當(dāng)前所剩余的候選基站總數(shù)和當(dāng)前的回合數(shù)所決定。用戶(hù)在該步驟對(duì)每個(gè)基站保持接入連續(xù)的Lm個(gè)時(shí)隙

Lm=nm-nm-1,

(11)

其中nm的定義如下

(12)

用戶(hù)在完成上述步驟之后會(huì)用其所獲得的獎(jiǎng)勵(lì)數(shù)據(jù)來(lái)更新參數(shù)，包括均值的更新、監(jiān)控變量的更新和采樣次數(shù)的更新。

每個(gè)回合的最后階段，用戶(hù)會(huì)根據(jù)更新后的系統(tǒng)參數(shù)來(lái)淘汰掉被分類(lèi)判斷為次優(yōu)的基站，也就是說(shuō)在這之后的所有回合用戶(hù)都不會(huì)再選擇這個(gè)基站接入。這里設(shè)置淘汰判決條件為

(13)

其中Bm為當(dāng)前回合m尚未被淘汰的基站集合。在該回合之后所有滿(mǎn)足上述判決條件的基站i都會(huì)被淘汰。

完整算法的具體流程見(jiàn)算法1。

算法1UAAE(user association with arm-elimination)用戶(hù)接入算法：

步驟2)若|Bm|=1，則用戶(hù)保持接入Bm中的唯一基站直到時(shí)隙T，否則執(zhí)行步驟3)。

步驟3)均等采樣：依次選擇接入|Bm|中的基站，并且每個(gè)基站保持接入Lm個(gè)時(shí)隙，計(jì)算從每個(gè)基站i獲得的總獎(jiǎng)勵(lì)

(14)

步驟4)參數(shù)更新：按以上得到數(shù)據(jù)更新如下系統(tǒng)參數(shù)

(15)

t=t+Lm|Bm|,

(16)

(17)

步驟5)操作桿淘汰：按照新的系統(tǒng)參數(shù)以及淘汰判決條件(13)更新Bm，

m=m+1,

(18)

步驟6)若t>T，算法結(jié)束，否則跳轉(zhuǎn)返回至步驟2)。其中，|S|表示集合S的勢(shì)。

2.2 理論分析

定理1算法1保持了和置信上界相同的后悔度數(shù)學(xué)期望上界，同時(shí)用戶(hù)在不同基站之間切換次數(shù)的數(shù)學(xué)期望上界可以降低為常數(shù)階：

a) 算法1可以保證如下后悔度的上界

(19)

(20)

算法1可以保證如下切換次數(shù)的上界

(21)

證明為描述簡(jiǎn)潔，首先需要定義3個(gè)事件：E1，E2，E3。

1)E1：每一個(gè)次優(yōu)基站i都會(huì)在第mi+1回合之前滿(mǎn)足淘汰判決條件，從而被淘汰掉不再被使用；

2)E2：存在某一個(gè)次優(yōu)基站i沒(méi)有在第mi+1回合之前滿(mǎn)足淘汰判決條件，被繼續(xù)使用；

3)E3：最優(yōu)基站被錯(cuò)誤淘汰。

這里需要注意，以上事件分解得到的3個(gè)子集的并集是事件全集，但是交集未必是空集。

當(dāng)事件E1發(fā)生時(shí)，每一個(gè)次優(yōu)基站i都只能提供接入至多mi回合。在所有的次優(yōu)基站都被淘汰掉以后，網(wǎng)絡(luò)用戶(hù)便不會(huì)再觸發(fā)網(wǎng)絡(luò)切換，由此可以得到在該事件發(fā)生的情況下用戶(hù)觸發(fā)網(wǎng)絡(luò)切換次數(shù)的上界

(22)

其中m0=0。

相應(yīng)地，由于每一個(gè)次優(yōu)基站i被選擇接入的次數(shù)都不超過(guò)nmi。結(jié)合Δi并且通過(guò)不等式放縮，可以得到當(dāng)事件E1發(fā)生時(shí)，所造成的后悔度

(23)

(24)

這里利用用戶(hù)最大可能觸發(fā)的網(wǎng)絡(luò)切換次數(shù)

(25)

上式成立的條件也是基于事實(shí)在均等采樣步驟中每個(gè)基站保持接入Lm個(gè)時(shí)隙，而Lm是單調(diào)遞增的。對(duì)所有N-1個(gè)次優(yōu)基站求和，可以得到針對(duì)事件E2的用戶(hù)觸發(fā)網(wǎng)絡(luò)切換次數(shù)的上界

(26)

相應(yīng)地，當(dāng)事件E2發(fā)生時(shí)，其造成的后悔度可以如下表達(dá)：

(27)

(28)

注意該求和上下限為從0到mN-1回合，這是因?yàn)樽顑?yōu)基站在mN-1回合之后被淘汰的情況實(shí)際上已經(jīng)被包含在了事件E2當(dāng)中。

相應(yīng)地，當(dāng)事件E3發(fā)生時(shí)，記最優(yōu)基站在m*回合被淘汰，那么最優(yōu)基站被淘汰后的每一個(gè)時(shí)隙都會(huì)增加后悔值。這里可以將該情況下的后悔值做如下不等式放縮：

(29)

結(jié)合以上事件分解后的分部結(jié)論相加，可以得到定理1中的結(jié)論。

證明完畢。

在該算法中，用戶(hù)對(duì)每個(gè)基站保持接入連續(xù)的Lm個(gè)時(shí)隙，而Lm可以被驗(yàn)證是指數(shù)增長(zhǎng)的。文獻(xiàn)[9]中的算法是逐一增長(zhǎng)的。這樣做的好處是更有利于減緩前文中已經(jīng)提到的當(dāng)擁有最高數(shù)學(xué)期望獎(jiǎng)勵(lì)的2個(gè)基站之間的數(shù)學(xué)期望差距ΔN-1非常小的時(shí)候，算法會(huì)很難區(qū)分這兩者的問(wèn)題。而從另一方面來(lái)說(shuō)，非常小的ΔN-1也保證了即使用戶(hù)需要在較長(zhǎng)的連續(xù)時(shí)隙內(nèi)選擇次優(yōu)的那個(gè)基站接入，也不會(huì)造成特別大的后悔度。

Lm同時(shí)也會(huì)隨著T的增加而增加。這個(gè)設(shè)計(jì)能夠保證如果總時(shí)間足夠長(zhǎng)，算法會(huì)在每個(gè)回合執(zhí)行淘汰機(jī)制之前對(duì)當(dāng)前回合還存在的基站做充分的估計(jì)。同時(shí)由于總時(shí)間足夠長(zhǎng)，在所有次優(yōu)基站被淘汰前對(duì)它們進(jìn)行采樣所使用的時(shí)隙造成的后悔度也相對(duì)影響較小。

該算法所保障的低切換的特性為更實(shí)際的網(wǎng)絡(luò)模型提供了很好的使用條件。在實(shí)際的網(wǎng)絡(luò)環(huán)境中，網(wǎng)絡(luò)的各方面性能往往是動(dòng)態(tài)變化的，即前文中所假設(shè)的獎(jiǎng)勵(lì)值由一個(gè)穩(wěn)定分布所產(chǎn)生的條件不再成立。而算法往往需要在環(huán)境發(fā)生變化時(shí)重新開(kāi)始學(xué)習(xí)以適應(yīng)新的網(wǎng)絡(luò)環(huán)境。這樣一來(lái)，如果使用常規(guī)的多臂老虎機(jī)算法，則不可避免地重新造成了大量的網(wǎng)絡(luò)切換。所以，在動(dòng)態(tài)環(huán)境下，當(dāng)用戶(hù)需要重新開(kāi)始學(xué)習(xí)過(guò)程時(shí)，UAAE算法能夠保證節(jié)省大量的切換次數(shù)。

3 實(shí)驗(yàn)結(jié)果分析

本節(jié)將利用蒙特卡洛仿真的方法驗(yàn)證本文所提算法的有效性。所有結(jié)果均為500次仿真實(shí)驗(yàn)的平均結(jié)果。

參數(shù)設(shè)定如下，系統(tǒng)中總共包含30個(gè)基站。每一個(gè)基站的期望獎(jiǎng)勵(lì)值由正態(tài)分布產(chǎn)生，N(5,δ2)?；緄在每次被用戶(hù)選中接入時(shí)產(chǎn)生的獎(jiǎng)勵(lì)同樣服從正態(tài)分布N(ui,1)。這樣設(shè)定的好處是可以通過(guò)控制方差δ來(lái)調(diào)節(jié)不同基站之間的優(yōu)劣差距。δ越小意味著△i也越小。仿真的總時(shí)間長(zhǎng)度為T(mén)=5×105，監(jiān)控變量初始值為b=1，用戶(hù)每次網(wǎng)絡(luò)切換的損失為C=1。

為對(duì)比本文提出算法的有效性，本文選擇如下算法作為對(duì)比算法：

a) 置信上界算法；

b) 改進(jìn)置信上界算法[9]；

首先驗(yàn)證4種不同算法的后悔值性能表現(xiàn)。如圖2所示，可以清晰地看出，除貪心算法的后悔值曲線幾乎是線性增長(zhǎng)，其他3個(gè)算法增長(zhǎng)的階數(shù)是一致的，但是UAAE算法有一定系數(shù)上的損失。

圖3表現(xiàn)的是4種算法下用戶(hù)所觸發(fā)的網(wǎng)絡(luò)切換次數(shù)隨時(shí)隙的變化曲線對(duì)比。UAAE算法相較于其他3個(gè)算法有著絕對(duì)的優(yōu)勢(shì)。這其中的原因正如前文所解釋?zhuān)脩?hù)最終淘汰掉N-1個(gè)基站，從而不會(huì)再觸發(fā)任何網(wǎng)絡(luò)切換。貪心算法的網(wǎng)絡(luò)切換次數(shù)為線性增長(zhǎng)。另外2種算法均為對(duì)數(shù)增長(zhǎng)。

接下來(lái)驗(yàn)證不同基站之間的期望獎(jiǎng)勵(lì)差距大小對(duì)算法性能的影響及敏感度分析。針對(duì)這點(diǎn)的研究是必要的，但是往往被很多使用多臂老虎機(jī)模型的研究工作所忽略。不同于其他可以使用多臂老虎機(jī)的應(yīng)用系統(tǒng)(例如推薦系統(tǒng)等)。在實(shí)際無(wú)線網(wǎng)絡(luò)系統(tǒng)中，用戶(hù)所能選擇接入的基站往往可能不會(huì)有太大的性能差距。這就給很多多臂老虎機(jī)算法帶來(lái)了挑戰(zhàn)。在該實(shí)驗(yàn)中，參數(shù)δ變化范圍0.05～0.5。從圖4可以看出，貪心算法雖然不受參數(shù)δ的任何影響，但是用戶(hù)所觸發(fā)的網(wǎng)絡(luò)切換次數(shù)也是最多的。另外3個(gè)算法中，文獻(xiàn)[9]中的改進(jìn)置信上界算法性能要略好于置信上界算法。而本文所提算法UAAE可以在任何參數(shù)δ下保持最小的網(wǎng)絡(luò)切換次數(shù)。

圖2 不同算法下的后悔值性能指標(biāo)對(duì)比Fig.2 Cumulative regrets with various bandit handover algorithms

圖3 不同算法下的用戶(hù)觸發(fā)網(wǎng)絡(luò)切換次數(shù)對(duì)比Fig.3 Cumulative numbers of handovers with various bandit handover algorithms

圖4 不同算法對(duì)于基站間差距大小的敏感度對(duì)比Fig.4 Sensitivity to the gaps between the SBSs

4 結(jié)論與討論

本文利用多臂老虎機(jī)模型提出一個(gè)低復(fù)雜度的無(wú)線網(wǎng)絡(luò)用戶(hù)接入算法。通過(guò)3組不同角度的對(duì)比試驗(yàn)，驗(yàn)證了本文所提算法的有效性、魯棒性，為下一代無(wú)線通信網(wǎng)絡(luò)中用戶(hù)接入系統(tǒng)設(shè)計(jì)提供一種解決思路。該算法除了有效降低用戶(hù)觸發(fā)網(wǎng)絡(luò)切換的次數(shù)，也保證其后悔值性能不會(huì)受到影響。

本文主要考慮的是穩(wěn)定環(huán)境下的解決方案，即基站產(chǎn)生獎(jiǎng)勵(lì)值的概率分布是恒定不變的。但是正如前文的討論中所指出，當(dāng)用戶(hù)面臨動(dòng)態(tài)變化的網(wǎng)絡(luò)環(huán)境時(shí)，其需要頻繁重新開(kāi)始學(xué)習(xí)過(guò)程。而本文所提算法為在動(dòng)態(tài)環(huán)境下的部署使用提供了很好的基礎(chǔ)。