曹 龍 趙杭生 鮑麗娜 張建照

?

分層認(rèn)知無線電網(wǎng)絡(luò)中基于穩(wěn)定匹配的資源分配算法

曹 龍*①②趙杭生②鮑麗娜③張建照②

①(解放軍理工大學(xué)通信工程學(xué)院 南京 210007)②(南京電訊技術(shù)研究所 南京 210007)③(中國聯(lián)通江蘇分公司 南京 210019)

頻譜資源的合理分配是認(rèn)知無線電技術(shù)追求的目標(biāo)之一，隨著認(rèn)知無線電網(wǎng)絡(luò)中的次用戶(SUs)數(shù)量不斷增加，頻譜資源的精確、實(shí)時(shí)分配與管控越來越難以實(shí)現(xiàn)。針對此問題，該文提出一種分層的認(rèn)知無線電網(wǎng)絡(luò)(CRN)架構(gòu)，多個(gè)管理實(shí)體專注于為各層用戶提供頻譜服務(wù)；并在該架構(gòu)下，提出一種基于穩(wěn)定匹配的資源分配算法，用戶通過自主協(xié)商形成分配結(jié)果，不僅保證了主用戶(PUs)對次用戶的功率限制，還充分考慮了各自的效用。仿真結(jié)果表明，所提算法的性能接近于最優(yōu)方案，并降低了計(jì)算復(fù)雜度和系統(tǒng)時(shí)延。

認(rèn)知無線電；資源分配；匹配理論；穩(wěn)定匹配；最優(yōu)化

1 引言

移動(dòng)互聯(lián)網(wǎng)、物聯(lián)網(wǎng)以及智能終端的出現(xiàn)帶來了便捷的生活方式和良好的用戶體驗(yàn)(Quality of Experience, QoE)，不斷增長的多媒體業(yè)務(wù)對帶寬和數(shù)據(jù)速率的要求越來越高，相關(guān)機(jī)構(gòu)預(yù)測到2020年無線網(wǎng)絡(luò)流量將是2010年的1000倍[1]，如何高效地利用有限的頻譜資源成為工業(yè)和學(xué)術(shù)界關(guān)注的重點(diǎn)[2,3]。

認(rèn)知無線電(Cognitive Radio, CR)[4]技術(shù)的出現(xiàn)提高了頻譜利用率，在不影響主用戶(Primary Users, PUs)通信的前提下，次用戶(Secondary Users, SUs)能夠接入空閑的PUs頻段。CR網(wǎng)絡(luò)(CR Networks, CRNs)內(nèi)PUs和SUs共存，資源分配技術(shù)能夠合理地將空閑頻段分配給SUs，提高了頻譜利用率，減小了SUs間、SUs與PUs間的干擾。

目前的資源分配方法大多都只考慮SUs的效用函數(shù)，例如吞吐量、能量有效性和對PUs的干擾限制等，博弈論利用SUs間的競爭關(guān)系進(jìn)行建模，求解問題的均衡解[9]，然而聯(lián)合考慮PUs和SUs性能的研究尚不多。

本文首先提出了一種分層的CRNs架構(gòu)，支持異構(gòu)認(rèn)知無線網(wǎng)絡(luò)，利用多個(gè)管理實(shí)體為用戶提供頻譜服務(wù)。在此基礎(chǔ)上，提出了一種新的資源分配算法用于SUs接入授權(quán)信道過程。利用經(jīng)濟(jì)學(xué)中的雙邊匹配理論，將該過程建模為一對一匹配問題，SUs和PUs根據(jù)設(shè)計(jì)的效用函數(shù)生成偏好信息，通過自主協(xié)商形成最終“穩(wěn)定”的資源分配方案，降低了計(jì)算復(fù)雜度和系統(tǒng)時(shí)延，提高了頻譜資源利用率。

2 分層認(rèn)知無線電網(wǎng)絡(luò)

如圖1所示，分層的CRNs包括3層：管理層、網(wǎng)絡(luò)層和用戶層。管理層由頻譜服務(wù)中心(Spectrum Service Center, SSC)、頻譜管理人員和數(shù)據(jù)中心組成，SSC通過解析國際、國內(nèi)、地區(qū)、地域等不同范圍的頻譜使用管理規(guī)則、規(guī)定、政策，監(jiān)測頻譜使用情況，收集、梳理、分析頻譜使用信息，分析和預(yù)測頻譜使用形勢和變化趨勢，對頻譜服務(wù)提供商(Spectrum Service Providers, SSPs)的頻譜服務(wù)請求做出響應(yīng)，分配可用的授權(quán)頻譜；數(shù)據(jù)中心主要存儲(chǔ)數(shù)字化的頻譜政策[10]、用頻案例和頻譜監(jiān)測數(shù)據(jù)等。網(wǎng)絡(luò)層由頻譜服務(wù)提供商和基礎(chǔ)網(wǎng)絡(luò)組成，SSPs主要向網(wǎng)絡(luò)內(nèi)的用戶提供用頻服務(wù)，綜合全網(wǎng)的用頻需求、用戶體驗(yàn)(Quality of Experience, QoE)和經(jīng)費(fèi)預(yù)算等向SSC租借頻譜，在指定的時(shí)間和區(qū)域享有部分授權(quán)頻譜的獨(dú)占式使用權(quán)。SSC與SSPs可以是無線或有線連接，按照規(guī)定的格式(例如頻譜消費(fèi)模型[10])進(jìn)行數(shù)據(jù)交互，相互之間是松耦合的關(guān)系。用戶層內(nèi)的用戶終端(User Equipments, UEs)主要包含PUs和SUs, PUs同樣會(huì)根據(jù)自身的用頻需求、QoE和預(yù)算等向SSPs租借頻譜，而SUs可以采用頻譜感知、頻譜數(shù)據(jù)庫訪問[11,12]等方法進(jìn)行機(jī)會(huì)式頻譜接入(Opportunistic Spectrum Access, OSA)。

圖1 分層認(rèn)知無線電網(wǎng)絡(luò)

分層的CRNs是一個(gè)異構(gòu)無線網(wǎng)絡(luò)，同一SSP內(nèi)可以采用不同的接入方式，例如PUs采用蜂窩移動(dòng)方式，而SUs采用WiFi或D2D(Device-to-Device)方式；不同SSPs也同樣可以采用不同的接入方式。

圖1所示的網(wǎng)絡(luò)內(nèi)包含多個(gè)頻譜分配(指配)過程：(1)SSC將一段時(shí)間、特定區(qū)域內(nèi)可用頻譜分配給SSPs; (2)SSPs將擁有的授權(quán)頻譜分配給本網(wǎng)PUs; (3)SUs根據(jù)用頻需求選擇接入PUs擁有的頻段。本文重點(diǎn)研究SSP網(wǎng)絡(luò)內(nèi)SUs接入PUs擁有的授權(quán)頻段(即第3個(gè)過程)，提出的基于穩(wěn)定匹配的資源分配算法也可以推廣到其它分配過程。

3 系統(tǒng)模型

考慮授權(quán)頻段被均勻地劃分為多個(gè)帶寬相等、相互正交的子信道，每個(gè)SSP擁有一定數(shù)量的子信道，SSC分配給SSP的信道集合，并且、每個(gè)子信道帶寬為；設(shè)SSP為個(gè)SUs集合提供頻譜服務(wù)。每個(gè)授權(quán)子信道都分配給一個(gè)PU，假設(shè)占用子信道的PU為，因此主用戶集合；如果該子信道空閑則有,SSP內(nèi)活動(dòng)的PUs集合。PUs是授權(quán)頻譜的租賃者，在不影響自身通信質(zhì)量的前提下，PUs允許SUs機(jī)會(huì)式頻譜接入，并且可以選擇Overlay和Underlay兩種接入方式。假設(shè)SU最多只能選擇一個(gè)授權(quán)信道，而每個(gè)子信道最多也只能被一個(gè)SU占用，這樣SSP就能夠很容易地計(jì)算和排除PUs受到的干擾。系統(tǒng)模型如圖2所示。

圖2 系統(tǒng)模型

SUs可以采用Overlay和Underlay兩種接入方式利用授權(quán)頻段[13]：當(dāng)PUs空閑，SUs采用Overlay接入方式，SUs發(fā)射機(jī)可以根據(jù)自己的需求采用合適的發(fā)射功率；當(dāng)PUs工作，SUs采用Underlay接入方式，SUs發(fā)射機(jī)的發(fā)射功率必須滿足PUs或是SSP的限制要求。

同理由于每個(gè)SU也只能接入單個(gè)授權(quán)信道，可以得到約束條件：

3.1 次用戶的效用函數(shù)

假設(shè)SU采用Overlay接入方式時(shí)，SU發(fā)射機(jī)以最大發(fā)射功率進(jìn)行通信，則SU在授權(quán)信道上可獲得的平均可達(dá)速率(機(jī)會(huì)速率)可以表示為

假設(shè)SU采用Underlay接入方式時(shí)，SU發(fā)射機(jī)以不大于信道規(guī)定的最大發(fā)射功率進(jìn)行通信，同理，此時(shí)的平均可達(dá)速率可以表示為

3.2 主用戶的效用函數(shù)

PUs作為授權(quán)信道的擁有者，資源分配時(shí)應(yīng)考慮其由于頻譜共享而受到的影響。當(dāng)SU采用Underlay方式接入時(shí)，授權(quán)信道上PU的可達(dá)速率會(huì)受到干擾功率的影響；SSP將根據(jù)SU可獲得的速率、QoE等制定差異化的付費(fèi)規(guī)則，并且PU愿意將授權(quán)信道租借給付費(fèi)高的SU，因此將PU的效用函數(shù)設(shè)計(jì)為可達(dá)速率與收入的乘積。

4 基于穩(wěn)定匹配的資源分配算法

在傳統(tǒng)的集中式方法中，管理實(shí)體通常會(huì)選取一個(gè)全局效用作為求解的目標(biāo)函數(shù)，這里選擇PUs和SUs效用函數(shù)的加權(quán)和。

式(8)是0-1整數(shù)規(guī)劃問題，其復(fù)雜度為指數(shù)冪，并且隨著網(wǎng)絡(luò)規(guī)模的增大而急劇變大。傳統(tǒng)的匈牙利算法通過集中式方案進(jìn)行求解[14]，然而在實(shí)際執(zhí)行中通常需要設(shè)立協(xié)調(diào)中心專門負(fù)責(zé)計(jì)算和資源協(xié)調(diào)分配，此外IBM公司開發(fā)的CPLEX應(yīng)用程序也可用于求解此類問題[15]。

SUs選擇接入PUs占用的授權(quán)子信道可以看成雙邊匹配問題[16]，諾貝爾獎(jiǎng)經(jīng)濟(jì)學(xué)獎(jiǎng)獲得者GALE和SHAPLEY[17]在1962年首先提出了典型匹配問題婚姻匹配，其性能與集中式方案相當(dāng)?shù)珡?fù)雜度相當(dāng)?shù)蚚18]。實(shí)際上，匹配理論通常用于建模兩個(gè)獨(dú)立主體集合間的分配問題，一方主體(集合)內(nèi)的個(gè)體對另一方主體(集合)內(nèi)的個(gè)體存在偏好(preferences)關(guān)系，它反映該個(gè)體在選擇對方主體(集合)中個(gè)體時(shí)的先后順序。經(jīng)濟(jì)學(xué)中一般假設(shè)偏好是完全有序的、可傳遞的，在資源分配背景下該條件是完全滿足的。通常以符號來表示個(gè)體的偏好，例如表示相比于個(gè)體，個(gè)體情愿選擇。文獻(xiàn)[19]給出了匹配理論中的部分定義，我們將其擴(kuò)展到分層CRNs中的資源分配問題。

簡而言之，相比于目前已經(jīng)匹配的對象，兩個(gè)個(gè)體都傾向于彼此稱為阻塞對。

我們采用經(jīng)濟(jì)學(xué)中的G-S算法對資源分配問題進(jìn)行求解，該算法通常用于求解一對一問題，擴(kuò)展后可以求解多對一問題，廣泛應(yīng)用于美國住院醫(yī)師匹配計(jì)劃、大學(xué)生入學(xué)和腎臟移植等實(shí)際問題[21]。其算法計(jì)算復(fù)雜度低，并且性能與最優(yōu)化算法相當(dāng)。

表1算法主要步驟包含3個(gè)部分：初始化、SUs申請和信道(PUs)決策。算法具體實(shí)現(xiàn)步驟如表1所示，步驟1-步驟3進(jìn)行算法的初始化，建立相應(yīng)的矩陣和集合；步驟5, SUs根據(jù)偏好矩陣提出申請；步驟6，信道(PUs)對這些申請進(jìn)行決策；重復(fù)上述步驟直到SUs的申請不被拒絕。當(dāng)SSP網(wǎng)絡(luò)的狀態(tài)發(fā)生變化或下一個(gè)分配周期時(shí)，重復(fù)執(zhí)行該算法。

表1 基于穩(wěn)定匹配的資源分配算法實(shí)現(xiàn)步驟

定理1 表1算法的解是穩(wěn)定的。

證明 算法步驟1根據(jù)式(5)和式(6)效用函數(shù)值的大小建立偏好矩陣，由于信道狀態(tài)的隨機(jī)性，,，同理,。因此匹配中不存在阻塞個(gè)體。,，滿足，由算法步驟5可知：SU曾經(jīng)向信道提出過申請；由可知：算法結(jié)束時(shí)，信道拒絕了SU的申請。根據(jù)算法步驟6可知，，滿足。因此匹配中不存在阻塞對。綜上，根據(jù)定義4可知，算法的解是穩(wěn)定的。 證畢

定理2 表1算法的解對于SUs來說是弱帕累托最優(yōu)的。

5 仿真結(jié)果與分析

仿真時(shí)考慮SSP網(wǎng)絡(luò)部署在400 m×400 m的正方形區(qū)域內(nèi)，子信道的數(shù)量分別取5和10, SUs的數(shù)量在動(dòng)態(tài)變化。UEs的地理位置隨機(jī)生成，圖3給出了用戶數(shù)最多時(shí)的用戶分布示意圖(PUs和SUs分別從序號最大的開始減少)。藍(lán)色的代表PUs收發(fā)機(jī)，紅色的代表SUs收發(fā)機(jī)，發(fā)射機(jī)為實(shí)心，而接收機(jī)為空心。PUs收發(fā)機(jī)之間的距離為120 m, SUs收發(fā)機(jī)之間的距離則為100 m。

圖3 用戶分布情況

為了說明算法性能，本文與式(8)的最優(yōu)解和隨機(jī)分配進(jìn)行了對比，隨機(jī)匹配的結(jié)果是106次仿真結(jié)果的平均值。

圖4(a)，圖5(a)給出了不同SUs數(shù)下效用值的比較，可以看出算法獲得的全局效用值、SUs效用值與最優(yōu)解非常接近，而PUs效用值略次于最優(yōu)解，并且3種效用都遠(yuǎn)好于隨機(jī)匹配，這是因?yàn)楸?算法對于SUs來說是弱帕累托最優(yōu)的。對比圖4(a)和圖5(a)，隨著子信道數(shù)量的增多，SUs可用的頻譜接入機(jī)會(huì)增加，SSP的全局效用、SUs效用和PUs效用都明顯增大，也就是說向SSC申請到更多的授權(quán)信道對SSP內(nèi)的SUs和PUs都有益。

圖4 主用戶數(shù)Ni=5的仿真結(jié)果

圖5 主用戶數(shù)Ni=10的仿真結(jié)果

圖4(b)，圖5(b)給出了不同SUs數(shù)下用戶申請次數(shù)的比較，可以看出當(dāng)用戶數(shù)較少時(shí)()，用戶申請次數(shù)小，這是因?yàn)榇藭r(shí)接入授權(quán)信道的競爭小；隨著用戶數(shù)的增多，某些不受PUs偏愛的用戶需要多次申請才能完成匹配。假設(shè)SU通過bit的數(shù)據(jù)向PU提出申請，該P(yáng)U通過bit的數(shù)據(jù)反饋結(jié)果，根據(jù)圖4(b)，圖5(b)可以估算出基于穩(wěn)定匹配的資源分配算法所帶來的通信開銷。

圖4(c)，圖5(c)給出了不同SUs數(shù)下算法的while循環(huán)次數(shù)比較，可以看出循環(huán)次數(shù)隨著用戶數(shù)的增多而增大。結(jié)合圖4(b)和圖4(c)，圖5(b)和圖5(c)可以看出，相同SUs數(shù)時(shí)算法的循環(huán)次數(shù)總是大于等于最大申請次數(shù)，這是因?yàn)樵诘^程中部分匹配對被新的申請所破壞。

6 結(jié)束語

本文提出了一種分層的認(rèn)知無線電網(wǎng)絡(luò)，多個(gè)管理實(shí)體為不同層的用戶提供頻譜服務(wù)。在此基礎(chǔ)上，提出了適用于該分層架構(gòu)的資源分配算法。利用經(jīng)濟(jì)學(xué)中的雙邊匹配理論，將該過程建模為一對一匹配問題，SUs和PUs根據(jù)設(shè)計(jì)的效用函數(shù)生成偏好信息，用戶根據(jù)各自的偏好自主協(xié)商形成最終的資源分配方案。資源分配的目標(biāo)不再是目標(biāo)函數(shù)的最大化，而是獲得系統(tǒng)穩(wěn)定的弱帕累托解。仿真表明，該算法的性能接近于最優(yōu)解，并且大大降低了計(jì)算復(fù)雜度和系統(tǒng)時(shí)延，所帶來的通信開銷也很小，有利于實(shí)際部署。

參考文獻(xiàn)

[1] Osseiran A, Braun V, Hidekazu T,. The foundation of the mobile and wireless communications system for 2020 and beyond: challenges, enablers and technology solutions[C]. IEEE Vehicular Technology Conference, Dresden, 2013: 1-5. doi: 10.1109/VTCSpring.2013.6692781.

[2] Ahmad A, Ahmad S, Rehmani MH,. A survey on radio resource allocation in cognitive radio sensor networks[J].&, 2015, 17(2): 888-917. doi: 10.1109/COMST.2015.2401597.

[3] Vassaki S, Poulakis M I, and Panagopoulos AD. Spectrum leasing in cognitive radio networks: a matching theory approach[C]. IEEE Vehicular Technology Conference, Glasgow, 2015: 1-5. doi: 10.1109/VTCSpring.2015.7146101.

[4] Mitola J, Guerci J, Reed J,.Accelerating 5G QoE via public-private spectrum sharing[J]., 2014, 52(5): 77-85. doi: 10.1109/ MCOM.2014.6815896.

[5] Musavian LandAissa S. Capacity and power allocation for spectrumsharing communications in fading channels[J]., 2009, 8(1): 148-156. doi: 10.1109/TWC.2009.070265.

[6] Asghari V and Aissa S. Adaptive rate and power transmission in spectrum-sharing systems[J]., 2010, 9(10): 3272-3280. doi: 10119/TWC.2010.090210.100291.

[7] Zhou X, Li GY, LiD,. Probabilistic resource allocation for opportunistic spectrum access[J]., 2010, 9(9): 2870-2879. doi: 10119/ TWC.2010.070610.091511.

[8] 潘甦, 曹跑跑, 劉勝美. 一種多無線電系統(tǒng)中基于公平性和精細(xì)化帶寬分配的資源分配算法[J]. 電子與信息學(xué)報(bào), 2015, 37(2): 399-404. doi: 10.11999/ JEIT140339.

Pan S, Cao P, and Liu S. A resource allocation algorithm based on proportional fairness and refined bandwidth allocation for multi-radio systems[J].&, 2015, 37(2): 399-404. doi: 10.11999/ JEIT140339.

[9] Xu Y, Anpalagan A, Wu Q,. Decision-theoretic distributed channel selection for opportunistic spectrum access: strategies, challenges and solutions[J].&, 2013, 15(4): 1689-1713. doi: 10.1109/ SURV.2013.030713.00189.

[10] IEEE 1900.5-2011. Standard for policy language requirements and system architectures for dynamic spectrum access (DSA) systems [S]. 2011.

[11] Al-Ali AK, SUN Y, FELICE M D,. Accessing spectrum databases using interference alignment in vehicular cognitive radio networks[J]., 2015, 64(1): 263-272. doi: 10.1109/TVT.2014. 2318837.

[12] Chen X and Huang J. Database-assisted distributed spectrum sharing[J]., 2013, 31(11): 2349-2361. doi: 10.1109/ JSAC.2013.131110.

[13] Goldsmith A, Jafar SA, Maric I,. Breaking spectrum gridlock with cognitive radios: an information theoretic perspective[J]., 2009, 97(5): 894-914. doi: 10.1109/JPROC.2009.2015717.

[14] Papadimitriou C H and Steiglitz K. Combinatorial Optimization: Algorithms and Complexity[M]. New York,USA, Dover Press, 1998: 248-255.

[15] IBM. Cplex optimizer[OL].http://www-01.ibm.com/software/commerce/optimization/cplex-optimizer, 2016.

[16] Gusfield D and Irving RW. The Stable Marriage Problem: Structure and Algorithms[M]. Cambridge, MA, USA, MIT Press, 1989: 1-8.

[17] Gale D and Shapley LS. College admissions and the stability of marriage[J]., 1962, 69(1): 9-15. doi: 10.2307/2312726.

[18] Gu Y,Saad W, Bennis M,. Matching theoryfor future wireless networks: fundamentals and applications[J]., 2015, 53(5): 52-59. doi: 10.1109/ MCOM.2015.7105641.

[19] Jorswieck E. Stable matchings for resource allocation in wireless networks[C]. International Conference on Digital Signal Processing (DSP), Corfu, 2011: 1-8. doi:10.1109/ICDSP.2011.6004983.

[20] Naeem M, Anpalagan A, Jaseemuddin M,. Resource allocation techniques in cooperative cognitive radio networks[J].&, 2014, 16(2): 729-744. doi:10.1109/SURV.102313.00272.

[21] Manlove D F. Algorithmics of Matching Under Preferences[M]. Singapore, World Scientific Press, 2013: 1-47.

Resource Allocation Algorithm Based on Stable Matching in Hierarchical Cognitive Radio Networks

CAO Long①②ZHAO Hangsheng②BAO Lina③ZHANG Jianzhao②

①(,,210007,)②(,210007,)③(,,210019,)

The rational spectrum resource allocation is one of the goals of Cognitive Radio (CR) technology. With the rapid increase of Secondary Users (SUs) numbers, the precise and real-time management becomes more and more difficult to achieve.In order to solve this problem, a hierarchical Cognitive Radio Network (CRN) architecture that several administration entities focus on providing spectrum services for users of variety tiers is proposed. The corresponding resource allocation algorithm based on stable matching in this architecture is also given. This algorithm guarantees the restriction on SUs’ transmission power for Primary Users (PUs), and also considers both utility functions of users. Simulation results demonstrate that the proposed method can roughly achieve the same performance of optimal solution with lower computation complexity and system delay.

Cognitive Radio (CR); Resource allocation; Matching theory; Stable matching; Optimization

TN929.5

A

1009-5896(2016)10-2605-07

10.11999/JEIT151460

2015-12-24；改回日期：2016-05-26；網(wǎng)絡(luò)出版：2016-07-14

曹龍 caolong460@sohu.com

國家自然科學(xué)基金(61471395, 61471392, 61301161)，江蘇省自然科學(xué)基金(BK20141070)

The National Natural Science Foundation of China (61471395, 61471392, 61301161), The Natural Science Foundation of Jiangsu Province (BK20141070)

曹 龍： 男，1988 年生，博士生，研究方向?yàn)檎J(rèn)知無線電、動(dòng)態(tài)頻譜管理.

趙杭生： 男，1962 年生，研究員，博士，研究方向?yàn)檎J(rèn)知無線電、動(dòng)態(tài)頻譜管理.

鮑麗娜： 女，1987 年生，工程師，碩士，研究方向?yàn)榫W(wǎng)絡(luò)資源管理、認(rèn)知無線電.

張建照： 男，1985 年生，工程師，博士，研究方向?yàn)檎J(rèn)知無線電、Ad Hoc網(wǎng)絡(luò)、動(dòng)態(tài)頻譜管理.