余云河，孫君

機器類通信中集中式與分布式Q學習的資源分配算法研究

余云河，孫君

（南京郵電大學通信與信息工程學院，江蘇 南京 210023）

針對海量機器類通信（massive machine type communication，mMTC）場景，以最大化系統(tǒng)吞吐量為目標，且在保證部分機器類通信設(shè)備（machine type communication device，MTCD）的服務(wù)質(zhì)量（quality of service，QoS）要求前提下，提出兩種基于Q學習的資源分配算法：集中式Q學習算法（team-Q）和分布式Q學習算法（dis-Q）。首先基于余弦相似度（cosine similarity，CS）聚類算法，考慮到MTCD地理位置和多級別QoS要求，構(gòu)造代表MTCD和數(shù)據(jù)聚合器（data aggregator，DA）的多維向量，根據(jù)向量間CS值完成分組。然后分別利用team-Q學習算法和dis-Q學習算法為MTCD分配資源塊（resource block，RB）和功率。吞吐量性能上，team-Q和dis-Q算法相較于動態(tài)資源分配算法、貪婪算法分別平均提高了16%、23%；復雜度性能上，dis-Q算法僅為team-Q算法的25%及以下，收斂速度則提高了近40%。

資源分配；集中式Q學習；分布式Q學習；余弦相似度；多維向量

1 引言

機器型通信（machine type communication，MTC）允許智能物體在沒有人為干預(yù)情況下實現(xiàn)相互通信，3GPP（3rd Generation Partnership Project）認為MTC將會對物聯(lián)網(wǎng)（internet of things，IoT）的發(fā)展起到關(guān)鍵作用[1-2]。隨著IoT的普及，對“物”之間的通信具有很高的需求，即使5G也不能保證滿足未來新業(yè)務(wù)的所有需求，因此在B5G（beyond 5G）和6G網(wǎng)絡(luò)中，MTC將會是研究人員關(guān)注的重點[3-4]。思科預(yù)測到2022年各行業(yè)中將會有39億個MTC設(shè)備連接到網(wǎng)絡(luò)中[5]，而海量機器類通信設(shè)備（machine type communication device，MTCD）連接不僅導致頻譜資源匱乏，還會造成網(wǎng)絡(luò)擁塞，給基站（base station，BS）帶來沉重負擔。

在部署了高密度MTCD的mMTC網(wǎng)絡(luò)中，將MTCD分組為較小集群被視為一種有助于緩解MTC網(wǎng)絡(luò)擁塞，提高MTCD接入成功率，進而促進吞吐量提升的技術(shù)[6]。為此，國內(nèi)外學者提出了一系列關(guān)于MTCD分組聚類算法。文獻[6-7]分別依據(jù)設(shè)備的QoS要求、地理位置進行分組，文獻[8]為了延長網(wǎng)絡(luò)壽命，依據(jù)MTCD剩余能量以及與BS間的距離進行聚類。文獻[9-10]在傳統(tǒng)-means算法基礎(chǔ)上作出改進，分別針對MTCD能量效率與MTC網(wǎng)絡(luò)傳輸時延要求，對MTCD進行聚類。然而，上述研究中提出的MTCD聚類策略，有的僅考慮了地理位置和QoS要求中的單個因素，并未充分發(fā)掘MTCD之間的關(guān)聯(lián)性，導致在MTCD聚簇內(nèi)不能很好地協(xié)調(diào)干擾，潛在影響系統(tǒng)吞吐量；有的僅針對特定優(yōu)化目標進行聚類，不具有普遍適用性。

文獻[11-12]均考慮H2H（human to human）與M2M（machine to machine）共存場景中系統(tǒng)用戶過載情況下的資源分配問題。然而，文獻[11]未考慮時延敏感M2M業(yè)務(wù)的傳輸需求，導致無法滿足此類M2M業(yè)務(wù)的QoS要求，文獻[12]則利用基于背包模型的資源分配算法，保證了時延敏感M2M通信業(yè)務(wù)的QoS，但在文獻[12]中僅將所提算法同傳統(tǒng)的優(yōu)先為H2H終端分配資源的算法進行性能比較，無法充分驗證該算法的優(yōu)越性。文獻[13]提出了一種動態(tài)資源分配策略用于解決MTCD間的資源分配問題，雖然考慮了MTCD請求過載的情況，但并不允許資源復用，導致頻譜利用率較低，同時由于接入網(wǎng)絡(luò)的MTCD數(shù)量較少，也造成系統(tǒng)吞吐量下降。文獻[14]針對多輸入多輸出系統(tǒng)中動態(tài)資源分配問題，提出了一種確保用戶最低QoS要求的資源分配算法，能獲得較高的系統(tǒng)吞吐量，然而該方法是在用戶功率等分配的前提下執(zhí)行的，并不符合實際，具有一定的局限性。文獻[15]討論了在頻譜資源匱乏條件下，基于設(shè)備到設(shè)備（device to device，D2D）分簇的車通信資源分配問題，在保證車用戶正常通信下，最大化蜂窩用戶的吞吐量。文獻[16]研究了基于容量最大化地mMTC場景的資源分配問題，但使用的是傳統(tǒng)粒子群算法，該算法對容量提升作用有限，且沒有考慮MTCD分組問題。在功率有限、頻譜資源匱乏的MTC網(wǎng)絡(luò)中，傳統(tǒng)資源分配方法難以滿足MTCD不斷增長的QoS要求。近年來研究表明基于機器學習的資源分配策略已經(jīng)優(yōu)于傳統(tǒng)的方法[17-18]，而Q學習作為一種著名無模型強化學習（reinforcement learning，RL）算法引起了人們的關(guān)注。

基于以上分析，本文在確保承擔高信噪比傳輸任務(wù)的MTCD最低QoS要求前提下，提出兩種Q學習算法：team-Q學習算法和dis-Q學習算法，解決網(wǎng)絡(luò)內(nèi)MTCD之間的資源塊和功率聯(lián)合分配問題。該資源分配算法分為兩個階段：第一階段設(shè)計一種基于CS的聚類方案，即借鑒商品推薦系統(tǒng)中求取用戶之間相似度的做法，分別為MTCD、DA構(gòu)造多維向量，再利用向量之間余弦相似度進行分組。第二階段中，針對分組后的MTC網(wǎng)絡(luò)上行鏈路資源塊和功率分配問題，提出了兩種基于Q學習的分配算法：team-Q學習和dis-Q學習，其中dis-Q算法在team-Q算法基礎(chǔ)上改進了Q值表和獎勵函數(shù)。最后，通過仿真驗證了所提算法能在復雜性、收斂速度以及對系統(tǒng)吞吐量促進作用等方面的有效性。

2 系統(tǒng)模型

本文研究的系統(tǒng)模型如圖1所示，隨機分布的MTCD經(jīng)過聚類后形成MTCD聚簇，每個聚簇內(nèi)含有一個數(shù)據(jù)聚合器DA，構(gòu)成MTC網(wǎng)絡(luò)。在MTC網(wǎng)絡(luò)中，MTCD通過稀疏碼分多址技術(shù)[19]與DA連接，DA充當數(shù)據(jù)接收和轉(zhuǎn)發(fā)的角色，即負責接收MTCD數(shù)據(jù)并轉(zhuǎn)發(fā)至BS，使得整個網(wǎng)絡(luò)變成雙層架構(gòu)，可以減輕BS的接入負擔。假定聚簇與聚簇間使用正交的頻譜資源，而聚簇內(nèi)的MTCD之間以非正交多址方式共用資源塊。因此，在MTC網(wǎng)絡(luò)內(nèi)由于資源塊的復用會產(chǎn)生多址干擾，在接收端則可采用串行干擾消除（successive interference cancellation，SIC）技術(shù)進行正確解調(diào)。

圖1 系統(tǒng)模型

所以針對使得整個MTC網(wǎng)絡(luò)吞吐量最大化的目標，根據(jù)香農(nóng)信道容量計算公式可以構(gòu)造出如下最優(yōu)化問題：

上述問題屬于混合整數(shù)非線性規(guī)劃（mixed integer nonlinear programming，MINLP）問題，通常是NP難[17]的，很難直接求解，在本文中使用Q學習算法解決。

3 算法的提出

3.1 MTCD聚簇形成

算法1 基于余弦相似度的MTCD聚類算法

初始化：

循環(huán)：

3.2 MTC網(wǎng)絡(luò)內(nèi)部資源分配

（1）基于team-Q學習算法的資源分配策略

（2）基于dis-Q學習算法的資源分配策略

算法2 dis-Q學習資源分配算法

初始化：

迭代：

根據(jù)式（10）更新Q值表；

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

本節(jié)主要對本文所提算法的性能進行分析驗證，包括收斂性、復雜度和系統(tǒng)吞吐量等，仿真平臺是MATLAB工具，仿真參數(shù)見表1[12,20]。

表1 仿真參數(shù)

首先對比兩種Q學習算法的收斂速度。如圖2所示，可以得到team-Q算法和dis-Q算法隨著迭代次數(shù)增加都趨向于收斂，但從迭代次數(shù)角度出發(fā)，dis-Q學習算法的收斂速度相比team-Q學習算法提高了近40%。這是由于在team-Q學習算法中，Q值表的維度遠大于dis-Q學習算法，當動作空間和智能體agent數(shù)量都增大時，team-Q算法復雜度會呈現(xiàn)指數(shù)級增長，最終導致dis-Q學習算法的收斂速度快于team-Q學習算法。

圖2 兩種Q學習算法收斂性分析

圖3 不同下team-Q、dis-Q算法中Q值表維度對比

圖4 不同算法下系統(tǒng)吞吐量對比

圖5 不同聚類算法下系統(tǒng)吞吐量對比

5 結(jié)束語

本文研究了在mMTC場景中以系統(tǒng)吞吐量最優(yōu)化為目標的資源分配問題。首先，提出了一種基于余弦相似度的聚類算法，根據(jù)MTCD與DA之間的相對位置和QoS要求，將MTCD分組。該算法能充分發(fā)掘出MTCD之間的關(guān)聯(lián)性，能更好地協(xié)調(diào)MTC聚簇內(nèi)的干擾，有利于提升系統(tǒng)性能。此外，針對MTC網(wǎng)絡(luò)中的資源分配問題，提出了team-Q學習算法和dis-Q學習算法。仿真結(jié)果表明，兩種Q學習算法對系統(tǒng)吞吐量的提升作用相較于對比算法均有較大幅度的提高，其中team-Q算法在系統(tǒng)吞吐量性能上略優(yōu)于dis-Q算法，但是dis-Q算法在信令消耗、收斂速度方面明顯優(yōu)于team-Q算法，這也更加符合“綠色通信”的理念。

[1] CHEN S Y, MA R F, CHEN H H, et al. Machine-to-machine communications in ultra-dense networks—A survey[J]. IEEE Communications Surveys & Tutorials, 2017, 19(3): 1478-1503.

[2] 錢志鴻, 王義君. 物聯(lián)網(wǎng)技術(shù)與應(yīng)用研究[J]. 電子學報, 2012, 40(5): 1023-1029.

QIAN Z H, WANG Y J. IoT technology and application[J]. Acta Electronica Sinica, 2012, 40(5): 1023-1029.

[3] Service-aware transport network: opportunities and chanenges[J]. Proceedings of SPIE - The International Society for Optical Engineering, 2005.

[4] ZHOU Y Q, TIAN L, LIU L, et al. Fog computing enabled future mobile communication networks: a convergence of communication and computing[J]. IEEE Communications Magazine, 2019, 57(5): 20-27.

[5] Cisco visual networking index: global mobile data traffic forecast update 2014-2019[EB]. 2014.

[6] LIANG L, XU L, CAO B, et al. A cluster-based congestion-mitigating access scheme for massive M2M communications in internet of things[J]. IEEE Internet of Things Journal, 2018, 5(3): 2200-2211.

[7] GHAVIMI F, LU Y W, CHEN H H. Uplink scheduling and power allocation for M2M communications in SC-FDMA-based LTE-A networks with QoS guarantees[J]. IEEE Transactions on Vehicular Technology, 2017, 66(7): 6160-6170.

[8] GAO H, XU X D, HAN S J. Homogeneous clustering algorithm based on average residual energy for energy-efficient MTC networks[C]//Proceedings of 2018 24th Asia-Pacific Conference on Communications (APCC). Piscataway: IEEE Press, 2018: 28-33.

[9] HUSSAIN F, HUSSAIN R, ANPALAGAN A, et al. A new block-based reinforcement learning approach for distributed resource allocation in clustered IoT networks[J]. IEEE Transactions on Vehicular Technology, 2020, 69(3): 2891-2904.

[10] XU Y Q, FENG G, LIANG L, et al. MTC data aggregation for 5G network slicing[C]//Proceedings of 2017 23rd Asia-Pacific Conference on Communications (APCC). Piscataway: IEEE Press, 2017: 1-6.

[11] 王鑫, 邱玲. H2H與M2M共存場景的準入控制及資源分配[J].中國科學院大學學報, 2016, 33(3): 427-432.

WANG X, QIU L. Admission control and resource allocation of H2H & M2M co-existence scenario[J]. Journal of University of Chinese Academy of Sciences, 2016, 33(3): 427-432.

[12] 蔣繼勝, 朱曉榮. H2H與M2M共存場景下的上行資源分配算法[J]. 電子學報, 2018, 46(5): 1259-1264.

JIANG J S, ZHU X R. An uplink resource allocation algorithm under the scenario of coexistence of H2H & M2M based on knapsack model[J]. Acta Electronica Sinica, 2018, 46(5): 1259-1264.

[13] SALAM T, REHMAN W U, TAO X F. Cooperative data aggregation and dynamic resource allocation for massive machine type communication[J]. IEEE Access, 2018, 6: 4145-4158.

[14] 郭濤, 李有明, 雷鵬, 等. MIMO中繼系統(tǒng)中一種基于用戶QoS的資源分配方法[J]. 電信科學, 2015, 31(4): 121-126.

GUO T, LI Y M, LEI P, et al. A resource allocation scheme based on user’s QoS in MIMO relay system[J]. Telecommunications Science, 2015, 31(4): 121-126.

[15] 張海波, 向煜, 劉開健, 等. 基于D2D通信的V2X資源分配方案[J]. 北京郵電大學學報, 2017, 40(5): 92-97.

ZHANG H B, XIANG Y, LIU K J, et al. V2X resource allocation scheme based on D2D communication[J]. Journal of Beijing University of Posts and Telecommunications, 2017, 40(5): 92-97.

[16] 劉佳言, 秦鵬, 趙雄文, 等. 基于容量最大化的mMTC場景的資源分配問題研究[J]. 電力信息與通信技術(shù), 2020, 18(12): 17-22.

LIU J Y, QIN P, ZHAO X W, et al. Research on resource allocation of m MTC scenario based on capacity maximization[J]. Electric Power Information and Communication Technology, 2020, 18(12): 17-22.

[17] SHARMA S K, WANG X B. Toward massive machine type communications in ultra-dense cellular IoT networks: current issues and machine learning-assisted solutions[J]. IEEE Communications Surveys & Tutorials, 2020, 22(1): 426-471.

[18] HUSSAIN F, HASSAN S A, HUSSAIN R, et al. Machine learning for resource management in cellular and IoT networks: potentials, current solutions, and open challenges[J]. IEEE Communications Surveys & Tutorials, 2020, 22(2): 1251-1275.

[19] NIKOPOUR H, BALIGH H. Sparse code multiple access[C]//Proceedings of 2013 IEEE 24th Annual International Symposium on Personal, Indoor, and Mobile Radio Communications (PIMRC). Piscataway: IEEE Press, 2013: 332-336.

[20] KAI C H, LI H, XU L, et al. Joint subcarrier assignment with power allocation for sum rate maximization of D2D communications in wireless cellular networks[J]. IEEE Transactions on Vehicular Technology, 2019, 68(5): 4748-4759.

Research on resource allocation algorithm of centralized and distributed Q-learning in machine communication

YU Yunhe, SUN Jun

College of Telecommunications and Information Engineering, Nanjing University of Posts and Telecommunications, Nanjing 210023, China

Under the premise of ensuring partial machine type communication device (MTCD)’s quality of service (QoS) requirements, the resource allocation problem was studied with the goal of maximizing system throughput in the massive machine type communication (mMTC) scenario. Two resource allocation algorithms based on Q-learning were proposed: centralized Q-learning algorithm (team-Q) and distributed Q-learning algorithm (dis-Q). Firstly, taking into account MTCD’s geographic location and multi-level QoS requirements, a clustering algorithm based on cosine similarity (CS) was designed. In the clustering algorithm, multi-dimensional vectors that represent MTCD and data aggregator (DA) were constructed, and MTCDs can be grouped according to the CS value between multi-dimensional vectors. Then in the MTC network, the team-Q learning algorithm and dis-Q learning algorithm were used to allocate resource blocks and power for the MTCD. In terms of throughput performance, team-Q and dis-Q algorithms have an average increase of 16% and 23% compared to the dynamic resource allocation algorithm and the greedy algorithm, respectively. In terms of complexity performance, the dis-Q algorithm is only 25% of team-Q algorithm and even below, the convergence speed is increased by nearly 40%.

resource allocation, centralized Q-learning, distributed Q-learning, consine similarity, multi-dimensional vector

TP929.5

A

10.11959/j.issn.1000?0801.2021244

余云河（1995? ），男，南京郵電大學通信與信息工程學院碩士生，主要研究方向為大規(guī)模機器類通信網(wǎng)絡(luò)中的資源分配。

孫君（1980? ），女，南京郵電大學碩士生導師，主要研究方向為無線網(wǎng)絡(luò)資源管理。

s: The National Natural Science Foundation of China (No.61771255), Open Project of Key Laboratory of Chinese Academy of Sciences (No.20190904)

2021?04?30；

2021?10?20

孫君，sunjun@njupt.edu.cn

國家自然科學基金資助項目（No.61771255）；中國科學院重點實驗室開放課題（No.20190904）