優(yōu)先級(jí)保護(hù)的分布式動(dòng)態(tài)頻譜分配算法

李宴濱,汪李峰,魏勝群,魏政霞

(1.解放軍理工大學(xué)通信工程學(xué)院,南京210007;2.中國(guó)電子設(shè)備系統(tǒng)工程公司研究所,北京100141;3.總參通信訓(xùn)練基地有線研究室,河北張家口075100)

1 引 言

近年來,隨著無線用戶數(shù)量及通信需求的急劇增加,可用頻譜稀缺的現(xiàn)象越來越明顯。研究表明,不是頻譜資源不夠用,而是頻譜資源沒有得到合理的應(yīng)用:一方面非授權(quán)頻段比較少并且用戶多,比較擁擠;另一方面很多授權(quán)頻段利用率很低,從聯(lián)邦通信委員會(huì)的調(diào)查數(shù)據(jù)來看,已分配的頻譜利用率在15%～85%[1]。認(rèn)知無線電(CR)[2]作為一種新興的技術(shù),得到了越來越多的關(guān)注。CR可以通過學(xué)習(xí),不斷感知環(huán)境變化,并根據(jù)環(huán)境的變化對(duì)自身傳輸參數(shù)進(jìn)行調(diào)整,從而保證可靠通信。認(rèn)知無線電的一個(gè)重要應(yīng)用是機(jī)會(huì)頻譜接入,即在不對(duì)主用戶造成干擾的前提下使用授權(quán)頻譜,從而滿足自身通信需求,因此可以對(duì)空閑的頻譜進(jìn)行有效利用。

無線通信中的認(rèn)知用戶本質(zhì)上是一個(gè)自治的智能主體,他們之間對(duì)頻譜的選擇利用是一個(gè)相互影響相互交互的過程。博弈論主要用于研究具有對(duì)抗局勢(shì)的模型,能夠?yàn)橄鄳?yīng)的博弈過程找到納什均衡點(diǎn)。因此,博弈論為動(dòng)態(tài)頻譜分配問題提供了一種新的方法和模型。

基于博弈論的動(dòng)態(tài)頻譜分配算法已經(jīng)有了很多的研究。文獻(xiàn)[3]針對(duì)不同的信道有不同的信道特征,而不同的用戶有不同的需求,以達(dá)到最優(yōu)的頻譜利用率為目標(biāo)設(shè)計(jì)了分配方法。文獻(xiàn)[4-6]研究了分布式Ad Hoc網(wǎng)絡(luò)中采用位勢(shì)博弈,以最大化信干比為目標(biāo)設(shè)計(jì)效用函數(shù),而后兩者分別就保護(hù)授權(quán)鏈路和OFDM機(jī)制進(jìn)行了進(jìn)一步的研究。文獻(xiàn)[7]通過CSMA的方式接入信道,根據(jù)反饋信息估計(jì)成功接入的概率,在設(shè)計(jì)效用函數(shù)的時(shí)候,加入懲罰函數(shù),通過學(xué)習(xí)方法達(dá)到相關(guān)均衡。文獻(xiàn)[8]中作者應(yīng)用匹配博弈提出了一種頻譜分配算法,以最大系統(tǒng)總傳輸速率為目標(biāo),通過雙向選擇機(jī)制達(dá)到均衡點(diǎn)且為最優(yōu)。文獻(xiàn)[9]指出不同用戶有不同的傳輸要求和傳輸類型,分別要求不同的傳輸速率,通過動(dòng)態(tài)博弈達(dá)到均衡,有較好的頻譜利用率和用戶滿足率。

上述文獻(xiàn)大多只是單純的分配信道,沒有考慮發(fā)射功率的影響,而在能量受限的情況下功耗是很重要的參數(shù)。文獻(xiàn)[10]提出了單信道ADP(Asynchronous Distributed Pricing)算法,可以實(shí)現(xiàn)功率和信道的聯(lián)合分配,但是需要所有認(rèn)知用戶具有相同的通信需求。然而在實(shí)際情況中,往往會(huì)有相對(duì)來說更重要的用戶,即高優(yōu)先級(jí)用戶。本文提出一種帶有干擾價(jià)格因子的ADP算法,可以提高高優(yōu)先級(jí)用戶的性能。

2 系統(tǒng)模型

分布式CR網(wǎng)絡(luò)如圖1所示,可用信道集合為C={1,2,3,…,M},其中存在K條鏈路代表K個(gè)用戶κ={1,2,3,…,K},M

圖1 網(wǎng)絡(luò)拓?fù)鋱DFig.1 The network topology

其中,k用戶選擇的信道用φ(k)表示,φ(k)∈ Μ,k用戶在信道φ(k)上選擇的功率用表示∈[0,pmax],傳輸質(zhì)量可以表現(xiàn)在誤碼率上,同樣可以表現(xiàn)在信干噪比上。k用戶在信道φ(k)上的信干噪比為

式中,hkk表示k用戶發(fā)送端和接收端之間的增益,hjk表示j用戶的發(fā)送端到k用戶的接收端之間的增益。

3 博弈模型

博弈論[11]是研究具有對(duì)抗或競(jìng)爭(zhēng)現(xiàn)象的數(shù)學(xué)理論和方法,它是現(xiàn)代數(shù)學(xué)的一個(gè)分支,也是運(yùn)籌學(xué)的一個(gè)重要學(xué)科。作為一種研究決策過程的數(shù)學(xué)工具,博弈論可以有效地預(yù)測(cè)決策結(jié)果,并選擇最佳策略[12]。

在頻譜分配模型中,各個(gè)認(rèn)知用戶選擇的信道和功率不僅影響自己的性能,同時(shí)也影響其它鄰居用戶的性能。認(rèn)知用戶本質(zhì)上是一個(gè)自治的智能主體,他們之間對(duì)頻譜資源的選擇利用是一個(gè)相互影響相互交互的過程,因此,博弈論為動(dòng)態(tài)頻譜資源分配問題提供了一種新的方法和模型[13]。

一般的博弈模型可以用下式表示:

式中,N={1,2,3,…,n}表示博弈的參與者,在頻譜分配模型中就是參與分配的用戶;Si為第i個(gè)用戶的策略空間,即認(rèn)知用戶的傳輸參數(shù),在本文中表示認(rèn)知用戶所選擇的信道和功率;Ui表示第i個(gè)用戶的效用函數(shù),它是所有用戶的策略空間映射到實(shí)數(shù)的一個(gè)函數(shù),由于每個(gè)用戶的收益不僅與自己選擇的策略有關(guān)還與其它用戶選擇的策略有關(guān),參與者的效用函數(shù)Ui是自身策略 si和其競(jìng)爭(zhēng)對(duì)手策略 s-i的函數(shù),根據(jù)博弈者的喜好不同有不同的效用函數(shù)。

博弈分析中一個(gè)重要的概念就是納什均衡,所謂納什均衡是指所有參與者選定的策略的組合,當(dāng)且僅當(dāng):

這組策略就是納什均衡。公式(3)表示的意思是任何一個(gè)參與者單獨(dú)改變行動(dòng),都會(huì)使其自身的效用函數(shù)降低。

本文應(yīng)用了動(dòng)態(tài)博弈(Dynamic Game)[11]模型。動(dòng)態(tài)博弈是指參與人的行動(dòng)有先后順序,而且后行動(dòng)者可以觀察到先行動(dòng)者的選擇,并據(jù)此做出選擇,先行動(dòng)者的選擇影響后行動(dòng)者的選擇空間。本文運(yùn)用簡(jiǎn)單的迭代來指配各用戶的博弈次序,重復(fù)進(jìn)行動(dòng)態(tài)博弈過程直至收斂。一個(gè)動(dòng)態(tài)博弈過程為一個(gè)迭代周期,一個(gè)迭代周期分為K個(gè)時(shí)隙(K= N ),每個(gè)時(shí)隙對(duì)應(yīng)一個(gè)用戶,即每個(gè)時(shí)隙中有一個(gè)用戶進(jìn)行決策,所有用戶依次進(jìn)行決策。

4 算法設(shè)計(jì)的目標(biāo)和效用函數(shù)

對(duì)于每個(gè)用戶,無論其優(yōu)先級(jí)的高低,由于各個(gè)信道的帶寬相同,其信干噪比直接影響到其效用,我們可以定義k用戶的效用為

對(duì)于所有用戶θk為相同參數(shù),所以用戶的效用函數(shù)只跟SINRk有關(guān)系。我們的設(shè)計(jì)目標(biāo)是各用戶選擇信道和功率值使得:

若各個(gè)用戶的效用函數(shù)定義為式(4),則每個(gè)用戶一定選擇最好的信道,并且以最大功率發(fā)送,另外也不能有效保證高優(yōu)先級(jí)用戶的特殊需求,這種自私的發(fā)送方式往往會(huì)降低整個(gè)系統(tǒng)的性能,使博弈過程的納什均衡偏離全局最優(yōu)策略,即個(gè)人理性與集體理性沖突。因此,分布式節(jié)點(diǎn)間既要保證自身的正常工作和通信需求,又要考慮對(duì)其它節(jié)點(diǎn)的干擾,應(yīng)用合作博弈設(shè)計(jì)算法可以有效解決上述問題。

原來的ADP算法中[10]定義干擾價(jià)格如下:

干擾價(jià)格表示了用戶所受干擾每增加一個(gè)單位帶來的收益的降低,每個(gè)用戶輪流發(fā)布干擾價(jià)格,在知道其它用戶的干擾價(jià)格時(shí),定義用戶的效用函數(shù)如下:

式中,第一項(xiàng)為其自身收益,第二項(xiàng)為代價(jià)函數(shù)。由于網(wǎng)絡(luò)中用戶有不同的優(yōu)先級(jí),原來的算法不能體現(xiàn)優(yōu)先級(jí)的區(qū)別,因此,從干擾價(jià)格的發(fā)布上進(jìn)行改進(jìn),加入干擾價(jià)格因子α。改進(jìn)后的干擾價(jià)格定義為

式中,αk為用戶j的干擾價(jià)格因子。

文獻(xiàn)[10]中我們可以認(rèn)為對(duì)于所有用戶 αk=1,從式(6)和式(7)可知,此時(shí)對(duì)于用戶 k,自身收益和代價(jià)函數(shù)的權(quán)值是一樣的,因此,可以達(dá)到網(wǎng)絡(luò)的整體收益最大。然而,為了提高高優(yōu)先級(jí)用戶的性能,就必須犧牲網(wǎng)絡(luò)中其它用戶或其中一部分用戶的性能。高優(yōu)先級(jí)用戶在發(fā)布干擾價(jià)格的時(shí)候可以使αk的值大于1,這樣其它用戶在選擇與其相同的信道時(shí)第二項(xiàng)的代價(jià)函數(shù)值增大,使其效用函數(shù)減小,從而選擇其它效用函數(shù)值高的信道或者減小發(fā)射功率,達(dá)到了對(duì)高優(yōu)先級(jí)用戶的保護(hù)。如果干擾價(jià)格因子取小于1的正實(shí)數(shù)時(shí),則表明此用戶更重視對(duì)其它用戶的干擾,優(yōu)先級(jí)為最低的用戶類型。

5 算法流程

每個(gè)認(rèn)知用戶都維持一個(gè)干擾價(jià)格矩陣、各用戶的信道使用矩陣和一個(gè)增益矩陣,每個(gè)用戶異步執(zhí)行分配算法,具體的算法流程如下:

(1)各個(gè)用戶參數(shù)的初始化,包括信道選擇、功率值、干擾價(jià)格;

(2)若當(dāng)前時(shí)隙屬于用戶k,則用戶k執(zhí)行以下步驟:

1)根據(jù)公式(7),計(jì)算使用各個(gè)信道時(shí)效用函數(shù)的最大值及其效用函數(shù)最大時(shí)的功率值pk;

2)選擇其中效用函數(shù)最大的信道及其對(duì)應(yīng)的功率值;

3)根據(jù)公式(8)計(jì)算其干擾價(jià)格,向外發(fā)布干擾價(jià)格和所選擇的信道;

(3)各用戶更新干擾價(jià)格和信道使用矩陣;

(4)所有用戶輪流進(jìn)行流程2,直至收斂。

6 仿真結(jié)果

本文使用Matlab建立認(rèn)知無線電系統(tǒng)的仿真平臺(tái),背景噪聲 n0=10-2,每個(gè)用戶的傳輸功率的范圍pmax=1,仿真場(chǎng)景中可用信道數(shù)為4,存在10個(gè)認(rèn)知用戶,其中2個(gè)為高優(yōu)先級(jí)用戶,10個(gè)發(fā)送節(jié)點(diǎn)隨機(jī)分布在3×3的區(qū)域內(nèi),其相應(yīng)的接收節(jié)點(diǎn)隨機(jī)分布在距離發(fā)送節(jié)點(diǎn)距離大約為1的范圍內(nèi),鏈路增益定義為距離的函數(shù),假設(shè)各個(gè)信道增益相同,即,β為固定的參數(shù)。

設(shè)置仿真迭代次數(shù)為20,仿真結(jié)果如圖2～5所示。初始信道分配狀況和收斂后的信道分配狀況見表1。

表1 算法前后信道分配狀況對(duì)比Table 1 The comparison before and after the channel allocation

圖2～5分別顯示了迭代過程中所有用戶的發(fā)射功率、信道選擇、干擾價(jià)格以及信干噪比的變化情況,并且分別在 9、3、8、9 次達(dá)到收斂狀態(tài) ,因此 ,改進(jìn)后的算法具有極快的收斂速度,能夠很快達(dá)到納什均衡,可以很好地適應(yīng)環(huán)境的變化。同時(shí),從圖2中可以看出,并不是所有的用戶都以最大功率發(fā)送,達(dá)到了同時(shí)分配信道和功率的目的。

圖2 功率更新Fig.2 Power update

圖3 信道更新Fig.3 Channel update

圖4 干擾價(jià)格更新Fig.4 Interference price update

圖5 信干噪比更新Fig.5 SINR update

由于初始信道選擇、初始功率、初始價(jià)格、產(chǎn)生的拓?fù)涠际请S機(jī)的,故達(dá)到的納什均衡有可能是不一樣的,為比較使用改進(jìn)后ADP算法和原來ADP算法高優(yōu)先級(jí)用戶的信干噪比的前后差別,需要運(yùn)用統(tǒng)計(jì)的方法得到平均信干比。選取一個(gè)隨機(jī)產(chǎn)生的拓?fù)浜碗S機(jī)產(chǎn)生的初始信道分配,分別使用原來算法和改進(jìn)后的ADP算法進(jìn)行上述仿真過程1 000次,分別記錄其結(jié)果,最后取平均,如圖6所示。此柱狀圖有兩組數(shù)據(jù),前面一組是改進(jìn)前的信干噪比,后一組為改進(jìn)后的信干噪比,高優(yōu)先級(jí)用戶為用戶9、10,干擾價(jià)格因子為5,其它用戶干擾價(jià)格因子為1。運(yùn)用改進(jìn)后算法提高了高優(yōu)先級(jí)用戶的性能,但是由于價(jià)格因子的作用使得低優(yōu)先級(jí)用戶減少對(duì)高優(yōu)先級(jí)用戶的干擾,低優(yōu)先級(jí)用戶有不同程度的性能損失。因此高優(yōu)先級(jí)用戶性能的提高是以低優(yōu)先級(jí)用戶的性能損失為代價(jià)的。

為了得到干擾價(jià)格因子對(duì)用戶性能的影響,下面以用戶10為例,仿真過程與以上類似,得到干擾價(jià)格因子分別為 0、0.1、0.5、1、5、10、30、50 時(shí)的性能變化情況,如圖7所示?？梢钥闯?用戶10隨著干擾價(jià)格因子的不斷增大信干噪比不斷增大,這與理論是相符的。隨著干擾價(jià)格因子的增大,其性能增長(zhǎng)速度減慢直到不再變化,這是因?yàn)楦蓴_價(jià)格因子大到一定程度,影響用戶性能的因素主要是自身的鏈路增益等其它因素,而不是其它用戶的干擾。

圖6 兩種算法性能Fig.6 Performance of the two algorithms

圖7 不同干擾價(jià)格的性能Fig.7 The performance of different interference price

7 結(jié) 論

本文利用重復(fù)博弈和動(dòng)態(tài)博弈對(duì)認(rèn)知無線網(wǎng)絡(luò)中的分布式動(dòng)態(tài)頻率選擇和功率控制策略進(jìn)行了研究,在ADP算法的基礎(chǔ)上引入干擾價(jià)格因子,從而達(dá)到提高高優(yōu)先級(jí)用戶性能的目的。通過認(rèn)知用戶之間進(jìn)行合作博弈來共享頻譜資源,減小干擾,提高算法性能。仿真結(jié)果表明,改進(jìn)后的算法可以實(shí)現(xiàn)信道和功率的聯(lián)合分配,可以達(dá)到納什均衡并且具有極快的收斂速度,在存在不同優(yōu)先級(jí)用戶的情況下可以一定程度提高高優(yōu)先級(jí)用戶的性能,但是是以犧牲其它用戶性能為代價(jià)。另外,實(shí)際系統(tǒng)中用戶可能存在欺騙行為,本文未曾涉及,這是今后的研究重點(diǎn)。

[1]Federal Communications Commission.Spectrum policy task force[R]//Report of Spectrum Efficiency Working Group.Washington:FCC,2002.

[2]Mitola J III.Cognitive Radio:An Integrated Agent Architecture for Software Defined Radio[D].Sweden:Royal Institute of Technology,2000.

[3]Liu Jishun,Shen Lianfeng,Song Tiecheng,et al.Demand-Matching Spectrum Sharing Game for Noncooperative Cognitive Radio Network[C]//Proceedings of 2009 International Conference on Wireless Communications&Signal Processing.Nanjing:IEEE,2009:1-5.

[4]Nie N,Comaniciu C.Adaptive channel allocation spectrum etiquette for cognitive radio networks[J].Mobile Networks and Applications,2006(11):779-797.

[5]馮春燕,郭義武,薛鈺,等.授權(quán)鏈路保護(hù)的頻譜分配算法[J].電子科技大學(xué)學(xué)報(bào),2008,37(6):855-859.FENG Chun-yan,GUO Yi-wu,XUE Yu,et al.Spectrum Allocation Algorithm Based on Protecting Licensed Link[J].Journal of University of Electronic Science and Technology of China,2008,37(6):855-859.(in Chinese)

[6]Quang Duy La,Yong Huat Chew,Boon-Hee Soong.An Interference Minimization Game Theoretic Subcarrier Allocation Algorithm for OFDMA-based Distributed Systems[C]//Proceedings of the 28th IEEEConference onGlobal T elecommunications.Honolulu,Hawaii,USA:IEEE,2009:2799-2804.

[7]Michael Maskery,Vikram Krishnamurthy,ZHAO Qing.Decentralized Dynamic Spectrum Access for Cognitive Radios:Cooperative Design of a Non-Cooperative Game[J].IEEE Transactions on Communications,2009,57(2):459-469.

[8]Chengquan An,Liang Zhang,Wenyan Liu.A Spectrum Allo-cation Algorithm Based On Matching Game[C]//Proceedings of the 5th International Conference on Wireless Communications,Networking and Mobile Computing.Beijing:IEEE,2009:1626-1628.

[9]Tao Jin,Chunxiao Chigan,Zhi Tian.Game-theoretic Distributed Spectrum Sharing for Wireless Cognitive Networks with HeterogeneousQoS[C]//Proceedings ofGlobal Telecommunications Conference.San Francisco,CA,USA:IEEE,2006:1-6.

[10]Huang J,Berry R,Honig M L.Spectrum Sharing with Distributed Interference Compensation[C]//Proceedings of IEEE DySPAN Conference.Baltimore,USA:IEEE,2005:88-93.

[11]范如國(guó),韓民春.博弈論[M].武漢:武漢大學(xué)出版社,2006.FAN Ru-guo,HAN Min-chun.Game Theory[M].Wuhan:Wuhan University Press,2006.

[12]Varian H R.Microeconomic Analysis[M].New York,USA:W.W.Norton&Company,1992.

[13]Allen BMackenzie,Luiz A Dasilva.Game Theory for Wireless Engineers[M].San Rafael,CA:Morgan and Claypool,2006.