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

曹 龍 趙杭生 鮑麗娜 張建照

?

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

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

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

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

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

1 引言

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

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

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

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

2 分層認知無線電網絡

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

圖1 分層認知無線電網絡

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

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

3 系統(tǒng)模型

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

圖2 系統(tǒng)模型

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

同理由于每個SU也只能接入單個授權信道，可以得到約束條件：

3.1 次用戶的效用函數

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

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

3.2 主用戶的效用函數

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

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

在傳統(tǒng)的集中式方法中，管理實體通常會選取一個全局效用作為求解的目標函數，這里選擇PUs和SUs效用函數的加權和。

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

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

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

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

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

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

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

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

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

5 仿真結果與分析

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

圖3 用戶分布情況

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

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

圖4 主用戶數Ni=5的仿真結果

圖5 主用戶數Ni=10的仿真結果

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

圖4(c)，圖5(c)給出了不同SUs數下算法的while循環(huán)次數比較，可以看出循環(huán)次數隨著用戶數的增多而增大。結合圖4(b)和圖4(c)，圖5(b)和圖5(c)可以看出，相同SUs數時算法的循環(huán)次數總是大于等于最大申請次數，這是因為在迭代過程中部分匹配對被新的申請所破壞。

6 結束語

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

參考文獻

[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)中基于公平性和精細化帶寬分配的資源分配算法[J]. 電子與信息學報, 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；網絡出版：2016-07-14

曹龍 caolong460@sohu.com

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

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

曹 龍： 男，1988 年生，博士生，研究方向為認知無線電、動態(tài)頻譜管理.

趙杭生： 男，1962 年生，研究員，博士，研究方向為認知無線電、動態(tài)頻譜管理.

鮑麗娜： 女，1987 年生，工程師，碩士，研究方向為網絡資源管理、認知無線電.

張建照： 男，1985 年生，工程師，博士，研究方向為認知無線電、Ad Hoc網絡、動態(tài)頻譜管理.