逼近納什均衡的動(dòng)態(tài)蜂窩選擇方案

王文浩,王祿生,開彩紅,劉 超

(合肥工業(yè)大學(xué) 計(jì)算機(jī)與信息學(xué)院,安徽 合肥 230601)

0 引 言

蜂窩選擇指的是異構(gòu)蜂窩網(wǎng)絡(luò)中終端選擇不同蜂窩進(jìn)行接入的技術(shù),可以是以系統(tǒng)性能最優(yōu)為目的的蜂窩選擇優(yōu)化,也可以是以每個(gè)終端自身選擇最佳接入策略為目的的蜂窩選擇博弈[1-2]。蜂窩范圍擴(kuò)展是蜂窩選擇優(yōu)化中一種具有代表性的方法,在根據(jù)參考信號(hào)接收功率門限確定小蜂窩接入邊界的基礎(chǔ)上,加上一個(gè)偏置值以擴(kuò)大小蜂窩的覆蓋范圍。一個(gè)場(chǎng)景中不同地方的稀疏程度不同,對(duì)應(yīng)著完全不同的最優(yōu)偏置值,這意味著固定的偏置值設(shè)置是不能得到系統(tǒng)最優(yōu)的,而針對(duì)每個(gè)蜂窩設(shè)置不同偏置值的做法在有大量終端和基站的高密度網(wǎng)絡(luò)中需要消耗非常長的優(yōu)化時(shí)間[3-4]。同時(shí),通過蜂窩選擇優(yōu)化來追求系統(tǒng)全局最優(yōu)可能會(huì)犧牲一些終端的利益,使得這些終端可能期望改變選擇策略來提升自身收益。因此,也有許多文獻(xiàn)對(duì)蜂窩選擇博弈的納什均衡[5](即沒有任何決策者單獨(dú)改變策略而獲益的策略組合)進(jìn)行研究。例如,文獻(xiàn)[6]從開放式和封閉式2種接入方式的角度分析了系統(tǒng)性能,同時(shí)證明了2種博弈模型純策略納什均衡的存在性。文獻(xiàn)[7]提出了一個(gè)異構(gòu)蜂窩選擇博弈模型,并從理論上證明了混合策略納什均衡的存在性;文獻(xiàn)[8]針對(duì)不同無線接入技術(shù)場(chǎng)景,提出了3種支付函數(shù)的蜂窩選擇博弈模型,并通過數(shù)學(xué)規(guī)劃理論解決最優(yōu)納什均衡問題。然而,上述研究中均未提出搜索納什均衡的有效方法。文獻(xiàn)[9]證明了勢(shì)博弈存在接近全局最優(yōu)的納什均衡點(diǎn),同時(shí)提出了擴(kuò)展性的最大分對(duì)數(shù)算法,得到了場(chǎng)景接近全局最優(yōu)的納什均衡點(diǎn);文獻(xiàn)[10]從蜂窩選擇和資源分配聯(lián)合的角度,分別研究終端選擇最佳基站的蜂窩間博弈與終端選擇最佳子信道的蜂窩內(nèi)資源博弈,并針對(duì)該2層模型分別提出了2個(gè)納什均衡收斂算法;文獻(xiàn)[11]在有多種接入方式的異構(gòu)蜂窩場(chǎng)景內(nèi),利用演化博弈分析蜂窩選擇過程,并且通過增強(qiáng)型學(xué)習(xí)算法得到演化均衡;文獻(xiàn)[12]通過博弈理論模型對(duì)流量卸載問題進(jìn)行分析,提出基于回報(bào)的對(duì)數(shù)線性學(xué)習(xí)算法,并收斂得到ε-納什均衡。

雖然文獻(xiàn)[9-12]均提出了搜索納什均衡的方法,但是這些方法都需要耗費(fèi)大量的時(shí)間。在異構(gòu)網(wǎng)絡(luò)場(chǎng)景中終端會(huì)不斷地移動(dòng),導(dǎo)致此前選擇的結(jié)果偏離原納什均衡,但是利用上述搜索納什均衡的方法無法非常快速地重新逼近到新的納什均衡。本文提出一種動(dòng)態(tài)逼近納什均衡的蜂窩選擇方案,能夠迅速調(diào)整終端的蜂窩選擇策略,使整個(gè)系統(tǒng)始終保持逼近納什均衡。

1 系統(tǒng)模型

本文研究的蜂窩選擇是針對(duì)2層異構(gòu)蜂窩場(chǎng)景中的上行信道特征,場(chǎng)景內(nèi)分布M個(gè)基站,表示為Ω={1,…,M},其中包括若干個(gè)宏蜂窩基站和飛蜂窩基站。假設(shè)任意基站k∈Ω和其他任意基站l∈Ω的距離為Dl→k,由于不涉及蜂窩內(nèi)的終端資源分配與調(diào)度,只能假設(shè)來自蜂窩l的干擾是其內(nèi)終端的平均效應(yīng),可將其簡化為蜂窩l的中心到基站k的干擾,計(jì)算公式為:

(1)

(2)

因此,基站k受到的總干擾計(jì)算公式為:

(3)

在場(chǎng)景內(nèi)分布m個(gè)終端,它們的蜂窩選擇策略組合為S={si|i=1,…,m}。其中,si為終端i的選擇策略,其可選策略集為所有基站,因此選擇基站k的終端個(gè)數(shù)計(jì)算公式為:

(4)

其中,bki為終端i選擇接入基站k的二進(jìn)制變量,即

(5)

本文采用信道容量評(píng)估終端i性能的效用,計(jì)算公式為:

(6)

定義1 若?i∈{1,…,m},有

(7)

表示當(dāng)前沒有任何一個(gè)終端可以通過單獨(dú)改變策略來獲益,則此時(shí)所有終端組成的純策略組合S*對(duì)應(yīng)1個(gè)純策略納什均衡。

2 逼近納什均衡的動(dòng)態(tài)方案

在一個(gè)2層異構(gòu)多蜂窩的動(dòng)態(tài)網(wǎng)絡(luò)場(chǎng)景中,整個(gè)系統(tǒng)以納什均衡點(diǎn)作為終端的蜂窩選擇結(jié)果。由于終端在場(chǎng)景中不斷地移動(dòng),導(dǎo)致此前的蜂窩選擇結(jié)果偏離了原有的納什均衡,系統(tǒng)若想要在短時(shí)間內(nèi)重新逼近到新的納什均衡,就必須不停地快速搜索出納什均衡點(diǎn)。但是,傳統(tǒng)搜索納什均衡的方法需要反復(fù)地判斷當(dāng)前場(chǎng)景中是否有終端想改變策略,而這個(gè)過程需要耗費(fèi)大量的時(shí)間,這將導(dǎo)致系統(tǒng)的蜂窩選擇結(jié)果因終端不斷移動(dòng)而始終無法逼近新的納什均衡。因此,打破傳統(tǒng)搜索納什均衡方法中的思維定式是解決這個(gè)問題的突破口。本文根據(jù)原有的納什均衡點(diǎn),構(gòu)造出一組經(jīng)驗(yàn)公式,系統(tǒng)通過這組公式計(jì)算出當(dāng)前網(wǎng)絡(luò)狀態(tài)下各個(gè)蜂窩內(nèi)需要更改策略的終端數(shù)量,并根據(jù)蜂窩邊緣終端更改策略的意愿強(qiáng)度對(duì)這些終端進(jìn)行降序排列,從而直接對(duì)應(yīng)出各個(gè)蜂窩內(nèi)需要改變策略的終端。這是本文提出的逼近納什均衡的動(dòng)態(tài)蜂窩選擇方案的核心思想。

按照上述思路,系統(tǒng)可以非常快速地逼近到新的納什均衡。但是,系統(tǒng)只能得到近似的納什均衡點(diǎn),而經(jīng)過數(shù)次調(diào)整終端的蜂窩選擇策略后,可能會(huì)逐漸偏離納什均衡。因此,為了保證系統(tǒng)始終動(dòng)態(tài)逼近到新的納什均衡,系統(tǒng)每隔一段時(shí)間就需要通過傳統(tǒng)搜索納什均衡的算法進(jìn)行一次慢速的納什均衡搜索。

本文逼近納什均衡的動(dòng)態(tài)蜂窩選擇方案(簡稱“本文方案”),如圖1所示。圖1中,將時(shí)間軸分成了無數(shù)個(gè)長周期,每個(gè)長周期再分成若干個(gè)短周期。每個(gè)長周期結(jié)束后,系統(tǒng)觸發(fā)一個(gè)傳統(tǒng)搜索納什均衡的算法搜索納什均衡進(jìn)行精確調(diào)整,該算法為本文改進(jìn)的Milchtaich算法(簡稱“改進(jìn)Milchtaich算法”);每個(gè)短周期結(jié)束后,系統(tǒng)通過設(shè)計(jì)的經(jīng)驗(yàn)公式進(jìn)行粗略調(diào)整,從而快速校正納什均衡。

圖1 逼近納什均衡的動(dòng)態(tài)蜂窩選擇方案

2.1 經(jīng)驗(yàn)公式粗略調(diào)整

每當(dāng)短周期結(jié)束時(shí),系統(tǒng)需要快速校正納什均衡,即要調(diào)整相鄰蜂窩邊緣交界處終端的蜂窩選擇策略,而這些終端所獲得的頻譜資源量是影響它們決策的主要因素,這與它們所選擇蜂窩的終端數(shù)量有直接的關(guān)系。事實(shí)上,這些蜂窩內(nèi)終端的數(shù)量不僅與其蜂窩內(nèi)部可能移出的終端有關(guān),還與這些蜂窩的相鄰蜂窩邊緣交界處可能移入的終端有關(guān)。換句話說,需要調(diào)整策略的終端受到覆蓋它們的蜂窩以及這些蜂窩的相鄰蜂窩的綜合影響。因此,為方便后續(xù)描述,定義了蜂窩k和蜂窩l以及它們相鄰蜂窩的相關(guān)符號(hào)。

假設(shè)基站k有若干個(gè)相鄰基站,表示為Φk?Ω,其任意相鄰基站為基站i∈Φk。蜂窩k內(nèi)的終端數(shù)量在終端移動(dòng)之前與在終端移動(dòng)之后分別表示為Nk、Nk′,蜂窩i內(nèi)的終端數(shù)量在終端移動(dòng)之前與在終端移動(dòng)之后分別表示為Ni、Ni′。對(duì)于位于蜂窩k與蜂窩i的邊緣交界處且接入基站k的任意終端u,它們的集合表示為Ψk,i;同樣,基站l也有若干個(gè)相鄰基站,表示為Φl?Ω,其任意相鄰基站表示為基站j∈Φl。蜂窩l內(nèi)的終端數(shù)量在終端移動(dòng)之前與在終端移動(dòng)之后分別表示為Nl、Nl′。由蜂窩k和蜂窩l相鄰可知,l∈Φk且k∈Φl。具體算法過程如下。

(8)

(9)

(10)

下文中將上述經(jīng)驗(yàn)公式粗略調(diào)整終端蜂窩選擇策略稱為“方案1”。

2.2 改進(jìn)Milchtaich算法精確調(diào)整

為了得到蜂窩選擇博弈納什均衡的結(jié)果,本文引用文獻(xiàn)[14]中的一個(gè)算法,稱為Milchtaich算法。該算法采用在擁塞博弈中1次改變1個(gè)終端的策略,并最終使場(chǎng)景達(dá)到納什均衡狀態(tài)。但是,該算法不適用于大規(guī)模終端的異構(gòu)蜂窩場(chǎng)景,原因有2個(gè):

(1) 該算法在異構(gòu)蜂窩網(wǎng)絡(luò)場(chǎng)景中效率很低。由于終端數(shù)量龐大,若在某個(gè)場(chǎng)景狀態(tài)下只改變1個(gè)終端,則場(chǎng)景達(dá)到納什均衡狀態(tài)需要很長的時(shí)間。

(2) 終端會(huì)在2個(gè)基站之間來回切換,產(chǎn)生“乒乓效應(yīng)”。當(dāng)場(chǎng)景達(dá)到近似均衡的狀態(tài)時(shí),可能會(huì)有少數(shù)在2個(gè)蜂窩邊緣的終端不停地切換基站,場(chǎng)景始終都無法達(dá)到納什均衡的狀態(tài)。

因此,本文對(duì)該算法做了改進(jìn)和拓展。當(dāng)場(chǎng)景處于某個(gè)狀態(tài)下,所有需要改變策略的終端以一定的概率同時(shí)離開原來的蜂窩。這大大減少了算法循環(huán)判斷場(chǎng)景內(nèi)是否有終端需要改變策略的次數(shù),同時(shí)降低了少部分終端在相鄰蜂窩之間同時(shí)來回切換的概率。這樣做提高了算法的效率,也能減少“乒乓效應(yīng)”帶來的影響。同時(shí),本文改進(jìn)后的算法不僅適用于1個(gè)宏蜂窩(macrocell)和1個(gè)微微蜂窩(picocell)構(gòu)成的簡單場(chǎng)景,還適用于多蜂窩的復(fù)雜場(chǎng)景。改進(jìn)Milchtaich算法步驟如下:

(1) 初始狀態(tài)下,任意終端給其所有基站發(fā)送1個(gè)有效傳輸信號(hào),根據(jù)這些基站接收信號(hào)強(qiáng)度的最大值,終端做出決策接入相應(yīng)的基站,此時(shí),場(chǎng)景內(nèi)所有終端的蜂窩選擇策略組合表示為S。

(2) 所有終端接收到資源管理決策中心廣播的有關(guān)場(chǎng)景狀態(tài)的信息,并由此判斷,在當(dāng)前狀態(tài)下是否需要改變策略。

(3) 資源管理決策中心收集所有需要改變策略的終端和它們需要接入基站的信息,以0.5的概率選出被允許更改策略的終端,再通知相應(yīng)的終端改變策略;終端改變策略后,更新場(chǎng)景內(nèi)所有終端的蜂窩選擇策略組合,本輪算法結(jié)束。

(4) 下一輪算法重復(fù)本輪算法的過程,直到場(chǎng)景達(dá)到納什均衡為止。

下文中將改進(jìn)Milchtaich算法精確調(diào)整終端蜂窩選擇策略稱為“方案2”。

3 性能仿真結(jié)果分析

本文考慮擁有大量飛蜂窩基站和終端的高密度蜂窩的仿真場(chǎng)景,參數(shù)設(shè)置[13,15]如下:宏蜂窩和飛蜂窩的終端發(fā)射功率分別為23、13 dBm,宏蜂窩基站和飛蜂窩基站的載波頻率分別為2.0、3.5 GHz,宏蜂窩和飛蜂窩的路徑損耗因子分別為3.00、3.19,宏蜂窩和飛蜂窩的陰影衰落分別為6.80、8.29 dB,宏蜂窩和飛蜂窩的帶寬均為20 MHz,噪聲功率密度為-174 dBm/Hz。

3.1 仿真場(chǎng)景設(shè)計(jì)

在異構(gòu)蜂窩網(wǎng)絡(luò)場(chǎng)景中,終端會(huì)不斷地移動(dòng)。為了方便研究,設(shè)置終端周期性地在場(chǎng)景內(nèi)移動(dòng)。若終端在整個(gè)場(chǎng)景內(nèi)隨機(jī)移動(dòng),則新的納什均衡結(jié)果相比于第1次的納什均衡結(jié)果不會(huì)發(fā)生明顯的變化。因此,將場(chǎng)景平均分成4個(gè)正四邊形區(qū)域,場(chǎng)景內(nèi)的終端均在各自的區(qū)域內(nèi)逆時(shí)針移動(dòng)。以其中1個(gè)正四邊形區(qū)域?yàn)槔?將該區(qū)域再分成4個(gè)小的正四邊形區(qū)域。在某個(gè)短周期內(nèi),當(dāng)場(chǎng)景達(dá)到納什均衡狀態(tài)后,從某個(gè)小區(qū)域內(nèi)開始,隨機(jī)選取該小區(qū)域內(nèi)10%～20%的終端,并以逆時(shí)針的方向同時(shí)向相鄰小區(qū)域隨機(jī)移動(dòng),終端移動(dòng)到任意蜂窩內(nèi)就接入該蜂窩的基站。同理,下個(gè)短周期再從終端到達(dá)的小區(qū)域內(nèi)開始,終端按照上一輪短周期的方式移動(dòng)。終端移動(dòng)場(chǎng)景與蜂窩選擇納什均衡結(jié)果如圖2所示。

圖2 終端移動(dòng)場(chǎng)景與蜂窩選擇納什均衡結(jié)果

通過直觀地對(duì)比方案1、方案2得出的仿真場(chǎng)景圖,大致地評(píng)估方案1的性能。由于每個(gè)短周期內(nèi),只有場(chǎng)景中的某個(gè)區(qū)域內(nèi)有終端發(fā)生位置移動(dòng),本文仿真終端移動(dòng)4個(gè)短周期后的蜂窩場(chǎng)景。圖2b、圖2c中,更改策略的終端與其更改策略后接入的基站圖形相同,由此可以直觀地看出由方案1蜂窩選擇結(jié)果逼近方案2結(jié)果。

3.2 方案性能對(duì)比

為了評(píng)估本文方案的效率,本文引用了基于Q學(xué)習(xí)的蜂窩選擇方案(簡稱“方案3”)。方案3能夠幫助終端學(xué)習(xí)它們過去的知識(shí),并且在未知其他終端完全信息的情況下可以使它們做出近似最優(yōu)的決策。在終端做決策時(shí),為了避免ε-貪婪算法使其陷入局部最優(yōu)的蜂窩選擇結(jié)果,本文采用Boltzmann搜索方法[16]。

(1) 時(shí)間消耗量。方案1、方案2及方案3的時(shí)間消耗量對(duì)比如圖3所示。對(duì)于傳統(tǒng)的搜索納什均衡的方案2、方案3,所有蜂窩邊緣的終端需要不斷地變更策略,因此需要經(jīng)過很多次迭代運(yùn)算。而方案1是根據(jù)經(jīng)驗(yàn)公式直接得出每個(gè)蜂窩內(nèi)需要變更策略的終端,它比任何搜索納什均衡的方案都快。

圖3 蜂窩選擇方案的時(shí)間消耗量對(duì)比

(2) 平均信道容量。為了評(píng)估本文方案的系統(tǒng)性能,本文引用了經(jīng)典的基于接收信號(hào)強(qiáng)度方案(簡稱“方案4”)。由于傳統(tǒng)搜索納什均衡方案的運(yùn)行速度太慢,這些方案在動(dòng)態(tài)的場(chǎng)景中不具

有應(yīng)用性,因此,不考慮算法的運(yùn)行時(shí)間,直接比較這些方案所得的動(dòng)態(tài)系統(tǒng)平均信道容量。考慮到每個(gè)周期內(nèi)變更蜂窩選擇的終端總是位于蜂窩邊緣附近,這里的動(dòng)態(tài)系統(tǒng)平均信道容量是指蜂窩邊緣終端的平均信道容量。4種方案終端移動(dòng)的動(dòng)態(tài)場(chǎng)景系統(tǒng)性能如圖4所示。由圖4可知,本文方案所得的蜂窩邊緣終端性能與傳統(tǒng)搜索納什均衡方案所得結(jié)果的性能相近,并且比方案4的結(jié)果性能好。

圖4 蜂窩選擇方案的性能對(duì)比

(3) 存在不同蜂窩選擇策略終端的數(shù)量。為了檢驗(yàn)本文方案所得的系統(tǒng)蜂窩選擇結(jié)果逼近納什均衡的程度,對(duì)方案2和本文方案所得的蜂窩選擇結(jié)果進(jìn)行比較,并統(tǒng)計(jì)2種結(jié)果中存在不同蜂窩選擇策略終端的數(shù)量λ。共有15個(gè)長周期,每個(gè)長周期包含20個(gè)短周期,每個(gè)短周期內(nèi)均有20個(gè)終端移動(dòng),本文隨機(jī)選取5個(gè)有終端移動(dòng)場(chǎng)景的仿真結(jié)果,如圖5所示。

圖5本文方案的蜂窩選擇結(jié)果與納什均衡點(diǎn)的對(duì)比中存在策略不同的終端數(shù)量

圖6 本文方案逼近納什均衡的程度

4 結(jié) 論

在異構(gòu)蜂窩網(wǎng)絡(luò)中,對(duì)于以每個(gè)終端自身選擇最佳接入策略為目的的蜂窩選擇博弈問題,在終端移動(dòng)的網(wǎng)絡(luò)場(chǎng)景下,傳統(tǒng)搜索納什均衡的方法無法使整個(gè)系統(tǒng)從近似的納什均衡快速逼近到新的納什均衡。針對(duì)這個(gè)問題,本文提出了一種逼近納什均衡的動(dòng)態(tài)蜂窩選擇方案。通過仿真發(fā)現(xiàn),該方案可以使整個(gè)系統(tǒng)始終動(dòng)態(tài)地逼近納什均衡,所得的蜂窩邊緣終端性能與傳統(tǒng)搜索納什均衡方案所得結(jié)果的性能相近,并且比經(jīng)典的基于接收信號(hào)強(qiáng)度方案的結(jié)果性能好。