趙耀，羅喜良

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

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

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

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

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

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

1 系統(tǒng)模型

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

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

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

(1)

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

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

(2)

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

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

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

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

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

(3)

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

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

假設(shè)獎勵由一個(gè)隨機(jī)變量產(chǎn)生，出于理論分析的方便，這里將獎勵歸一化至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開始計(jì)時(shí)至?xí)r隙T為止，該用戶所接受到的總獎勵可以表示為

(7)

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

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

(8)

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

(9)

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

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

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

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

(10)

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

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

2 高效的用戶接入策略

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

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

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

Lm=nm-nm-1,

(11)

其中nm的定義如下

(12)

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

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

(13)

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

完整算法的具體流程見算法1。

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

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

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

(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的勢。

2.2 理論分析

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

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

(19)

(20)

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

(21)

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

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

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

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

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

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

(22)

其中m0=0。

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

(23)

(24)

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

(25)

上式成立的條件也是基于事實(shí)在均等采樣步驟中每個(gè)基站保持接入Lm個(gè)時(shí)隙，而Lm是單調(diào)遞增的。對所有N-1個(gè)次優(yōu)基站求和，可以得到針對事件E2的用戶觸發(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í)隙都會增加后悔值。這里可以將該情況下的后悔值做如下不等式放縮：

(29)

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

證明完畢。

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

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

該算法所保障的低切換的特性為更實(shí)際的網(wǎng)絡(luò)模型提供了很好的使用條件。在實(shí)際的網(wǎng)絡(luò)環(huán)境中，網(wǎng)絡(luò)的各方面性能往往是動態(tài)變化的，即前文中所假設(shè)的獎勵值由一個(gè)穩(wěn)定分布所產(chǎn)生的條件不再成立。而算法往往需要在環(huán)境發(fā)生變化時(shí)重新開始學(xué)習(xí)以適應(yīng)新的網(wǎng)絡(luò)環(huán)境。這樣一來，如果使用常規(guī)的多臂老虎機(jī)算法，則不可避免地重新造成了大量的網(wǎng)絡(luò)切換。所以，在動態(tài)環(huán)境下，當(dāng)用戶需要重新開始學(xué)習(xí)過程時(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è)基站的期望獎勵值由正態(tài)分布產(chǎn)生，N(5,δ2)?；緄在每次被用戶選中接入時(shí)產(chǎn)生的獎勵同樣服從正態(tài)分布N(ui,1)。這樣設(shè)定的好處是可以通過控制方差δ來調(diào)節(jié)不同基站之間的優(yōu)劣差距。δ越小意味著△i也越小。仿真的總時(shí)間長度為T=5×105，監(jiān)控變量初始值為b=1，用戶每次網(wǎng)絡(luò)切換的損失為C=1。

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

a) 置信上界算法；

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

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

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

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

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

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

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

4 結(jié)論與討論

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

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