基于時序差分的動態(tài)信道分配算法*

王娟，史冬陽，邵浚哲

（1.南京郵電大學(xué)計算機(jī)學(xué)院、軟件學(xué)院、網(wǎng)絡(luò)空間安全學(xué)院，江蘇 南京 210023；2.浩鯨云計算科技股份有限公司，江蘇 南京 211100）

0 引言

隨著科學(xué)技術(shù)的不斷進(jìn)步，通信技術(shù)也在飛速地發(fā)展。據(jù)工信部統(tǒng)計，2020 年中國移動通信基站總數(shù)達(dá)931 萬個，5G 網(wǎng)絡(luò)建設(shè)在逐步推進(jìn)。移動通信設(shè)備每年以驚人的速度增加，預(yù)計到2025 年將達(dá)到59 億，意味著用戶對移動蜂窩網(wǎng)絡(luò)帶寬的需求也越來越高。

在移動通信網(wǎng)絡(luò)中，無線電頻譜覆蓋的范圍通常被劃分為多個不相交且固定大小的區(qū)域，稱為蜂窩，又被稱作小區(qū)（cell）。每個小區(qū)由自己的基站（BS,Base Station）提供服務(wù)，基站通過無線收發(fā)器使移動用戶接入無線網(wǎng)絡(luò)提供語音傳輸?shù)确?wù)[1]。研究如何高效地利用有限且寶貴的帶寬資源，可以更好地提高服務(wù)質(zhì)量（QoS,Quality of Service），滿足用戶的需求[2-3]。

然而，移動通信網(wǎng)絡(luò)作為提供帶寬資源的整體，其通信無線電頻譜帶寬資源被劃分為信道，移動用戶必須擁有本小區(qū)的信道資源獨(dú)占訪問權(quán)才能不受干擾地進(jìn)行通信。采用多址接入方式可以提高信道資源的利用率，諸如碼分多址、時分多址和頻分多址等技術(shù)，帶寬資源被劃分成互不干擾的信道供用戶共享使用[4]。若不指定特定的多址接入技術(shù)，在移動通信網(wǎng)絡(luò)中信道是資源分配的基本單位[5]。目前對信道分配算法的研究有固定分配和動態(tài)分配兩種。固定信道分配（FCA,Fixed Channel Allocation），其分配給每個小區(qū)的信道個數(shù)固定且一成不變。優(yōu)點(diǎn)是實(shí)現(xiàn)簡單，但是它不能適應(yīng)網(wǎng)絡(luò)動態(tài)變化的通信流量?？赡軙霈F(xiàn)網(wǎng)絡(luò)一部分小區(qū)信道全部占用而無法滿足再次到來的呼叫請求，而另一部分小區(qū)存在信道閑置，造成網(wǎng)絡(luò)信道不均衡使用甚至出現(xiàn)浪費(fèi)的情況[6-7]。動態(tài)信道分配（DCA,Dynamic Channel Allocation）指網(wǎng)絡(luò)中所有的信道按需分配給不同的小區(qū)，信道和小區(qū)之間沒有固定分配關(guān)系，算法需要進(jìn)行實(shí)時計算，具有很高的復(fù)雜性[8-11]。Nie 等人在移動通信網(wǎng)絡(luò)中使用強(qiáng)化學(xué)習(xí)優(yōu)化動態(tài)資源分配算法，可以降低算法的計算復(fù)雜度[12]。然而，在蜂窩網(wǎng)絡(luò)用戶的高移動性以及高通信流量情景下，提高切換呼叫性能的信道分配算法的研究較少?；诖?，本文根據(jù)用戶移動模型分析了切換呼叫的時空特性，開展基于強(qiáng)化學(xué)習(xí)的動態(tài)信道分配算法，進(jìn)一步提高切換呼叫的性能。

1 相關(guān)知識

1.1 信道分配

信道的分配必須避免同信道干擾（CCI,Co-Channel Interference）才能被小區(qū)復(fù)用[13]。換句話說，為不小于最小重用距離的兩個小區(qū)的用戶分配同一信道，既能保證通信質(zhì)量又能提高信道復(fù)用效率。如圖1 中移動蜂窩網(wǎng)絡(luò)小區(qū)劃分的同信道分配集合，相同字母標(biāo)識的六邊形代表同信道小區(qū)，該移動蜂窩網(wǎng)絡(luò)的最小重用距離為3，相同字母表示分配給小區(qū)的相同的信道集合，這樣分配信道不會發(fā)生干擾。

圖1 移動蜂窩網(wǎng)絡(luò)小區(qū)

1.2 強(qiáng)化學(xué)習(xí)

強(qiáng)化學(xué)習(xí)（RL,Reinforcement Learning）是一種機(jī)器學(xué)習(xí)方法，由智能體和環(huán)境兩部分組成[14]。

圖2 中智能體與環(huán)境交互，在時刻t觀察周圍環(huán)境的狀態(tài)st，根據(jù)當(dāng)前狀態(tài)執(zhí)行動作at，然后智能體會收到環(huán)境反饋的一個即刻獎勵rt+1，進(jìn)入下一個狀態(tài)st+1。策略π定義為從狀態(tài)到動作的映射。強(qiáng)化學(xué)習(xí)最終目的是使智能體從環(huán)境中獲得的獎勵最大。衡量策略的好壞用狀態(tài)價值函數(shù)V值和狀態(tài)行動值函數(shù)Q值表示，它們的計算分別用式(1) 和式(2) 表示：

圖2 強(qiáng)化學(xué)習(xí)過程

其中，r為即刻獎勵，γ為獎勵折扣因子。

時序差分（TD,Temporal Difference）、QLEARNING都是基于無模型的強(qiáng)化學(xué)習(xí)算法[15-16]。二者求解問題的最終形式表現(xiàn)為利用V值和Q值，選擇獲得最大獎勵的動作策略。

2 基于TD的動態(tài)分配算法

2.1 相關(guān)定義

用戶移動時位置將發(fā)生變化，用戶離開當(dāng)前服務(wù)小區(qū)，此時服務(wù)該用戶的基站隨之變化，在移動蜂窩網(wǎng)絡(luò)中，把這種情況稱為區(qū)間切換（Handoff）。通常，移動蜂窩網(wǎng)絡(luò)為一個用戶的呼叫分配一個信道資源，用戶發(fā)生呼叫切換時在當(dāng)前小區(qū)的呼叫結(jié)束，則釋放為其分配的信道資源。如圖3 所示，箭頭表示移動用戶切換的方向，灰色標(biāo)識區(qū)域是25 號小區(qū)移動用戶可能切換的六個鄰居小區(qū)。

圖3 移動蜂窩網(wǎng)絡(luò)的鄰區(qū)切換

定義小區(qū)n的沖突小區(qū)I(n) 是指與n距離小于d的小區(qū)集合，用式(3) 表示：

其中，d是最小重用距離。

I(25)={18,19,24,26,31,32,11,12,13,20,27,33,39,38,3 7,30,23,17}為圖3 中25 號小區(qū)的沖突小區(qū)集合。

定義小區(qū)n的合理信道集A(n) 是指小區(qū)n和沖突小區(qū)均空閑的信道，用式(4) 表示：

其中，xmk(t) 指m小區(qū)信道k的當(dāng)前狀態(tài)，m是小區(qū)n的沖突小區(qū)。信道分配算法為圖3 所示的25 號小區(qū)用戶呼叫分配信道k時滿足k∈A(25)。

定義小區(qū)n的鄰區(qū)N(n) 是指與n距離為1 的小區(qū)集合，用式(5) 表示：

其中，dist(n,m) 表示小區(qū)n與m的距離。

不難看出，由于用戶的高速移動，呼叫發(fā)生切換，則切換時刻t當(dāng)前小區(qū)的呼叫結(jié)束，同時鄰區(qū)產(chǎn)生新呼叫（切換呼叫），結(jié)束呼叫和切換呼叫發(fā)生的時間一致；切換呼叫發(fā)生的位置一定在它的鄰區(qū)，因此移動蜂窩網(wǎng)絡(luò)切換呼叫具有時空相關(guān)性。

2.2 TD算法

本文把信道分配問題看作馬爾可夫決策過程（MDP,Markov Decision Process），使用TD 求解。MDP 模型進(jìn)一步形式化描述為：

（1）狀態(tài)：st=(xt,et)，xt表示移動蜂窩網(wǎng)絡(luò)信道分配情況，et表示呼叫事件。其中，具體使用xnk(t)={0,1}表示信道的占用與空閑。n表示小區(qū)，k表示網(wǎng)絡(luò)信道，xnk=1表示占用，xnk=0 表示空閑。呼叫事件有新呼叫（new）、切換呼叫（handoff）、結(jié)束呼叫（end）三種。

（2）動作：at=k，k∈{1,2,…K}。執(zhí)行動作a就是從合理信道集合中選取一個信道k分配給當(dāng)前小區(qū)n的呼叫。若當(dāng)前小區(qū)無合理信道則拒絕呼叫。

（3）即刻獎勵r：執(zhí)行動作從環(huán)境獲得的獎勵，它的計算用式(6) 表示：

（4）TD 求解MDP 模型

MDP 信道分配求解是通過采取的動作策略從環(huán)境獲取的獎勵最多，在強(qiáng)化學(xué)習(xí)TD 算法中，一般使用V 值評判當(dāng)前環(huán)境狀態(tài)下執(zhí)行動作策略的優(yōu)劣，選擇狀態(tài)值最大的策略執(zhí)行動作就能從環(huán)境中得到最大獎勵。因此，使用TD 即可求解動態(tài)的信道分配問題。

利用2.1 節(jié)切換呼叫的時空相關(guān)性，切換發(fā)生時，TD 處理的事件分為當(dāng)前小區(qū)的結(jié)束事件和鄰區(qū)的新呼叫事件。結(jié)束呼叫信道重分配結(jié)合鄰區(qū)信道預(yù)分配兩步狀態(tài)值更新策略，用式(7) 表示：

其中，handoffn,m,k,t表示時刻t的切換呼叫，該呼叫從小區(qū)n切換至鄰區(qū)m，k表示當(dāng)前結(jié)束事件占用的信道。先處理結(jié)束事件endn,k,t，執(zhí)行動作a到達(dá)第一步狀態(tài)s′，再處理鄰區(qū)新呼叫事件newm,t+1，當(dāng)前狀態(tài)s′執(zhí)行動作a′到達(dá)狀態(tài)s′′，使用該狀態(tài)值更新切換呼叫事件的狀態(tài)值。

2.3 算法性能評價指標(biāo)

采用新呼叫阻塞率pn_block、切換呼叫阻塞率ph_block和總呼叫阻塞率pt_block來評價信道分配算法的性能[11]。計算公式分別用式(8)、式(9) 和式(10) 表示如下：

其中Nrej_n表示新呼叫事件被拒絕的個數(shù)，Nincoming表示新呼叫到達(dá)事件的個數(shù)。

其中，Nrej_h表示切換呼叫事件被拒絕的個數(shù)，Nhandoff表示切換呼叫到達(dá)事件的個數(shù)。

3 仿真實(shí)驗(yàn)

3.1 仿真環(huán)境

本文使用python 語言實(shí)現(xiàn)離散呼叫事件模擬器，搭建移動蜂窩網(wǎng)絡(luò)信道資源分配管理仿真平臺。參照文獻(xiàn)[11]設(shè)置蜂窩網(wǎng)絡(luò)的呼叫環(huán)境以及性能評價指標(biāo)（呼叫阻塞率），其中，移動用戶呼叫到達(dá)服從泊松分布λ，呼叫持續(xù)時間服從指數(shù)分布1/μ。話務(wù)量指用戶呼叫的負(fù)荷，用呼叫到達(dá)率與呼叫持續(xù)時間的乘積表示，單位是Erl。實(shí)驗(yàn)部分參數(shù)設(shè)置如表1 所示，設(shè)置移動蜂窩網(wǎng)絡(luò)總的信道個數(shù)K為70，實(shí)驗(yàn)分別采用TD、QLEARNING、RANDOM 以及FCA 四種算法實(shí)現(xiàn)信道資源的分配。TD算法采用本文提出的策略更新方法，實(shí)現(xiàn)信道的動態(tài)分配，RADOM 算法采用動態(tài)隨機(jī)分配信道，F(xiàn)CA 算法按照圖1的信道集分配給49 個小區(qū)且固定信道個數(shù)為10。

表1 仿真實(shí)驗(yàn)部分參數(shù)

3.2 仿真結(jié)果

（1）小區(qū)均勻流量分布

這種情況下，移動蜂窩網(wǎng)絡(luò)中每個小區(qū)話務(wù)量強(qiáng)度值相同，分別在話務(wù)量為5，5.5，6，6.5，7，7.5，8，8.5，9，9.5，10，即到達(dá)率每小時100，110，120，130，140，150，160，170，180，190，200 次呼叫下進(jìn)行仿真實(shí)驗(yàn)，執(zhí)行四種算法后性能對比如圖4 所示：

圖4 均勻流量分布下算法的性能

從圖4 可以看出，隨著話務(wù)量的增大，呼叫阻塞率都會隨之而增加。RANDOM 算法優(yōu)于FCA 算法，TD 和QLEARNING 算法性能較好，那是因?yàn)閯討B(tài)分配算法更能適應(yīng)呼叫環(huán)境的動態(tài)變化。TD 算法性能優(yōu)于QLEARNING 算法，是因?yàn)門D 算法的動作選擇策略利用了切換呼叫時空相關(guān)性，切換呼叫使用兩步狀態(tài)值更新，結(jié)合考慮鄰區(qū)切換預(yù)分配和小區(qū)信道重分配，進(jìn)一步提高了TD 分配算法的靈活性。實(shí)驗(yàn)結(jié)果可以看出TD 算法極大地降低切換呼叫阻塞率，滿足用戶高移動性的需要。

（2）小區(qū)非均勻流量分布

這種情況下，每個小區(qū)的話務(wù)量強(qiáng)度值不同，小區(qū)不均勻分布實(shí)例假設(shè)如圖1 所示，數(shù)字代表各小區(qū)的呼叫到達(dá)率，此時整個網(wǎng)絡(luò)話務(wù)量均值為5，若將小區(qū)呼叫到達(dá)率等比例增加100% 可以達(dá)到平均話務(wù)量為10。在這種分布下，模擬處理的呼叫事件個數(shù)不等，執(zhí)行四種算法后性能對比如圖5 所示：

圖5 非均勻流量分布下算法的性能

從圖5 可以看出，不管移動蜂窩網(wǎng)絡(luò)需要處理多少呼叫事件，四種算法的性能穩(wěn)定，處理事件的多少會影響仿真實(shí)驗(yàn)的時間開銷不影響算法的性能。在不同小區(qū)非均勻流量和高話務(wù)量強(qiáng)度下，TD 算法始終保持最低的呼叫阻塞概率，尤其是切換呼叫概率的性能得到了很大的提升與改善，明顯優(yōu)于其他算法。那是因?yàn)樗浞掷们袚Q呼叫時空特性，結(jié)束呼叫信道重分配結(jié)合鄰區(qū)信道預(yù)分配兩步狀態(tài)值更新強(qiáng)化學(xué)習(xí)的策略，算法靈活適應(yīng)動態(tài)環(huán)境的變化。因此TD 算法性能最好。

4 結(jié)束語

利用預(yù)分配和重分配機(jī)制，改進(jìn)切換呼叫的動作選擇策略，本文提出了一種基于TD 的動態(tài)信道分配算法。通過小區(qū)均勻流量和不均勻流量分布場景下對各種算法的仿真實(shí)驗(yàn)可以看出，TD 算法大大降低切換呼叫阻塞率，滿足高移動高流量通信場景下的用戶需求。