基于灰狼優化和匈牙利算法的D2D資源分配策略

摘 要： 當前，車聯網系統中存在頻譜資源有限、系統干擾較大、D2D（device to device）用戶通信質量差等問題。針對上述情況，提出了一種基于灰狼優化和匈牙利算法的D2D資源分配策略。在保證蜂窩用戶以及D2D用戶通信質量的前提下，該模型首先利用灰狼優化獲得每個D2D用戶的最佳發射功率，然后利用匈牙利算法實現D2D用戶與蜂窩用戶的最佳信道匹配，最大化D2D用戶的總容量。仿真結果表明，該算法與和聲搜索算法和遺傳算法相比，在有效提升D2D用戶的總容量同時，單個D2D用戶也能獲得較高的最大、最小容量。

關鍵詞： D2D； 灰狼優化； 匈牙利算法； 資源分配； 車聯網

中圖分類號： TN929.5"" 文獻標志碼： A

文章編號： 1001-3695（2022）05-042-1529-05

doi：10.19734/j.issn.1001-3695.2021.10.0467

D2D resource allocation strategy based on gray wolf optimizer and Hungarian algorithm

Xiao Yaoa，b， Liu Huihengb， Cheng Xiaohongc， An Mangmangb

（a.School of Mechanical Engineering， b.School of Physics amp; Electronic Engineering， c.Hubei Key Laboratory of Low Dimensional Optoelectronic Materials amp; Devices， Hubei University of Arts amp; Science， Xiangyang Hubei 441053， China）

Abstract： At present， there are some problems in the Internet of Vehicles system， such as spectrum resources shortage， large system interference， and the communication quality of D2D users. To solve these problems， this paper proposed a D2D resource allocation strategy based on GWO-HA. On the premise of meeting the communication quality of cellular users and D2D users， this model used the gray wolf optimizer （GWO） to get the optimal transmission power of each D2D user. Then it reali-zed the optimal channel matching between DUE and CUE by the Hungarian algorithm （HA） and obtained the maximum total capacity of D2D users. Simulation results show that， compared with harmony search （HS） and genetic algorithm （GA）， the proposed algorithm can effectively improve the total capacity of D2D users. At the same time， single D2D user can also obtain high maximum and minimum capacities.

Key words： D2D; grey wolf optimizer; Hungarian algorithm; resource allocation; Internet of Vehicles

0 引言

無線通信技術的發展，加速了社會邁進萬物互聯信息時代的步伐。隨著智能網聯汽車業務類型的增加和海量數據的指數增長，無線頻譜資源日益緊缺，傳統的蜂窩通信模式已支持不了現有通信數據要求［1］。5G關鍵技術之一——D2D技術通過允許頻譜之間的復用，使 終端用戶之間得以進行信息交互。在保證各種類型用戶通信需求的前提下，D2D用戶（D2D user，DUE）允許選擇合適的蜂窩用戶（cellular user， CUE）進行頻譜復用，不僅能夠大幅度提升頻譜利用率，緩解基站負載壓力，還能改善D2D用戶的總容量，提升車聯網終端的通信質量［2～4］。在保證系統內各用戶通信質量的前提下，DUE用戶發射功率的合理分配，有限頻譜資源的合理復用，是目前D2D技術應用于車聯網領域急需解決的問題之一［5～7］。文獻［8］提出了一種基于粒子群算法結合干擾控制及功率匹配的D2D資源分配方式，算法有效控制了系統總干擾，但未考慮高效的頻譜復用模式，系統頻譜利用率未得到有效提升。文獻［9］提出了一種基于遺傳算法和二進制粒子群算法的容量優化方案，使得D2D對的容量有所提升，但未考慮功率優化問題。文獻［10］通過在有限集中搜索最優解來解決功率分配這一非線性規劃問題，算法仿真結果表明系統容量明顯提升，但用戶之間的干擾未得到有效控制。文獻［11］提出了一種基于終端速率需求的資源分配方法，算法為處于干擾限制區外的DUE用戶公平地分配資源，但系統D2D用戶容量未有顯著提升。

文獻［12］在基于聯合干擾管理和資源分配的情況下，提出一種聯盟博弈模型，采用合并和分裂序列指導D2D用戶在聯盟中合并或從聯盟中拆分的順序，D2D系統容量得到顯著提升，但文章僅考慮DUE用戶接入量對系統容量的影響，未考慮車輛密度、行駛速度等其他因素對系統容量的影響。文獻［13］提出一種信道增益因子為每個DUE用戶確定候選復用信道，利用拉格朗日對偶分解法為DUE用戶分配最佳功率，優化系統容量，仿真結果表明系統吞吐量可得到有效提升，在信道復用階段CUE用戶選擇距離較近的DUE用戶作為頻譜復用對象，但未考慮信道復用的公平性以及干擾影響。文獻［14］ 提出一種基于復雜穩定匹配的松弛在線算法，有效減小了算法的復雜度使系統容量有效提升，但未考慮用戶之間存在干擾的問題。文獻［15］分兩個階段實現了多對DUE匹配同一信道的問題，控制干擾的同時有效提升了系統的信道利用率，但系統容量較其他優化類算法未得到顯著提升。

針對上述問題，本文提出了一種基于灰狼優化和匈牙利算法（gray wolf optimizer and Hungarian algorithm，GWO-HA）的資源分配策略來解決DUE用戶的資源分配問題，在保證系統內各用戶通信質量的基礎上最大化系統DUE容量。灰狼種群中的每個個體表示DUE用戶的發射功率，在種群中三個最優個體的引導下，其他灰狼個體不斷向最優解靠近，最后得到最優個體的位置，完成DUE用戶的功率分配方案的優化。最后通過構建DUE容量二分矩陣，用匈牙利算法優化信道匹配問題，完成所有DUE與CUE用戶的一對一匹配，進而實現DUE用戶容量的全局優化。

1 系統模型

本文考慮D2D通信模式與蜂窩通信模式共存的移動通信場景，如圖1所示。系統模型中存在M個CUE用戶，K個DUE用戶，CUE用戶與基站進行上行鏈路的信息交互，第m個CUE用戶表示為CUEm，m={1，…，M}，第k個DUE用戶對表示為DUEk，k={1，…，K}。假設車輛均服從空間泊松分布［16］。為了提升系統的頻譜利用效率，最大化所有DUE用戶的系統總容量，考慮DUE用戶復用CUE用戶的上行頻譜資源，并作以下假設：系統中存在M個互相正交的頻譜資源，一個CUE用戶僅允許一個DUE用戶進行信道復用，一個D2D用戶也只能復用一個CUE用戶的頻譜資源；基站為eNB演進型基站，并且可以在基站處獲取整個系統的瞬時信道鏈路狀態信息。

4 仿真結果與分析

4.1 仿真參數

本文以MATLAB為仿真平臺驗證算法性能，仿真實驗環境假定在單蜂窩小區中，模擬遵循3GPP TR 36.885［18］中詳述的高速公路場景設置（圖1），對通過蜂窩單元的多車道高速公路進行建模，其中基站位于其中心，車輛根據空間泊松分布在道路上，車輛密度由車輛速度決定。具體仿真參數設置如表1所示，通信鏈路模型采用表2所示模型設置。

4.2 仿真結果分析

為了驗證所提算法性能，本文從DUE用戶吞吐量累計分布函數，DUE用戶總容量，系統中單個DUE用戶對最小容量、最大容量的變化情況來進行驗證。同時將遺傳算法［9］和聲搜索算法［20］結合匈牙利算法進行全局優化時的性能與本文算法進行了比較。

當Pcmax=23 dBm時，DUE系統吞吐量的累積分布函數如圖4所示。從圖中可以看出，GWO-HA的性能優于HS-HA（harmony search and Hungarian algorithm）和GA-HA（genetic algorithm and Hungarian algorithm）。例如，GWO-HA中，DUE系統吞吐量小于或等于3 500 Mbps/Hz的概率約為20%，而HS-HA約為30%，提高了約10%，GA-HA約為50%，提高了約30%。這是因為GWO算法考慮了種群中最優的三個解對其他解的影響，在迭代次數結束時找到種群中最優的個體作為DUE發射功率最優解，相較于HS和GA，解的優化考慮的參數更多，因而系統的全局優化效果更好，容量收斂值更大。

圖5給出了GWO-HA、HS-HA、GA-HA三種算法在CUE最大發射功率分別為23 dBm和17 dBm兩種情況下，DUE系統容量隨車輛速度的變化情況。仿真結果表明，隨著車輛速度的增加，三種算法中DUE系統的總容量減小。因為車輛速度的增加必然導致車輛密度減小，車間距變大，V2V車輛之間連接的穩定性降低，DUE系統容量減小。通過仿真結果可以發現，相比于Pcmax=23 dBm、Pcmax=17 dBm時，三種算法的DUE系統容量性能都更優。例如GWO-HA中，當v=100 km/h、Pcmax=17 dBm時，較23 dBm相比提高了約20 Mbps/Hz。這是因為當CUE用戶的發射功率變大時，CUE用戶對于DUE用戶的干擾更大，由式（2）和（5）可知，DUE用戶受到的干擾越大，接收端的信噪比減小，導致DUE系統容量減小。相比于HS-HA和GA-HA，GWO-HA性能有明顯改善。例如，當車輛速度為v=120 km/h、Pcmax=23 dBm時，本文提出的GWO-HA性能較HS-HA相比，DUE系統容量提升了約11%，較GA-HA，DUE系統容量提升了約6%，說明車輛在高速公路場景下，GWO-HA較HS-HA和GA-HA更能將系統容量保持在較優水平，并且隨著車輛速度的增加，所提算法的性能改善越來越明顯。

圖6、7給出了GWO-HA、HS-HA和GA-HA三種算法在CUE最大發射功率為17 dBm和23 dBm兩種情況下，單個DUE對最小容量、最大容量隨車輛速度變化的仿真結果。仿真結果表明，隨著車輛速度的增加，三種算法中單個DUE對的最小、最大容量都會減小，這是因為車輛速度的增加，車輛密度的減小在影響DUE系統容量的同時，對單個DUE對的最大最小容量也會有所影響。通過圖6可以發現，所提算法DUE用戶最小容量略低于HS-HA，但明顯優于GA-HA。例如當v=100 km/h、Pcmax=23 dBm時，GWO-HA和HS-HA中，單個DUE用戶對的最小容量分別為83 Mbps/Hz和85 Mbps/Hz，僅低了約2 Mbps/Hz，但GA-HA下單個DUE用戶對的最小容量僅為68 Mbps/Hz，相比GWO-HA降低了15 Mbps/Hz。但是單個DUE對的最大容量，所提算法較HS-HA和GA-HA均有較大提高。例如，當車輛速度為v=100 km/h、Pcmax=23 dBm時，HS-HA和GA-HA中單個DUE對的最大容量為220 Mbps/Hz和264 Mbps/Hz，而GWO-HA中單個DUE對的最大容量維持在273 Mbps/Hz，分別提高了約53 Mbps/Hz和9 Mbps/Hz，從而能夠更好地保證DUE用戶高速行駛的通信質量。

通過圖7還可以發現，車輛速度由60 km/h變化至120 km/h的過程中，GWO-HA相比HS-HA可以將單個DUE對的最大容量保持在較穩定的水平，容量值變化約為10 Mbps/Hz，而HS-HA下的單個DUE對最大容量值的變化較大，約為42 Mbps/Hz；GA-HA雖然也能在車速變化時將單個DUE對的最大容量保持在穩定范圍內，但容量低于GWO-HA。說明在當車輛速度越來越大時，GWO-HA對比GA-HA更有利于提升單個DUE用戶的最大容量；GWO-HA相比HS-HA，更能保證CUE用戶通信的穩定性。在高速公路場景下，大部分車輛的行駛速度在100～120 km/h內，所提算法更加符合實際場景。

圖8為DUE系統容量隨DUE車輛數量變化圖，這里假設CUE用戶數為20。仿真結果表明，隨著DUE車輛數量的增加，DUE系統容量增加。因為DUE接入數量的增加，由目標函數式（6）可知，DUE系統容量不斷增加。圖8中，相比于Pcmax=23 dBm，Pcmax=17 dBm時DUE系統容量性能有所改善。這是因為CUE用戶的發射功率越大，對DUE用戶的干擾就越大，從而影響整個DUE系統容量性能。相比于HS-HA和GA-HA，當接入的DUE用戶比較小時，例如當DUE用戶數為5～10時，GWO-HA性能改善不是很明顯。但是隨著D2D系統中DUE用戶接入數量的增加，所提算法性能改善越來越明顯。例如，當DUE用戶數為15、Pcmax=23 dBm時，GWO-HA功率分配策略下的DUE系統容量較HS-HA提升約5%，較GA-HA提升約8%，這說明隨著DUE用戶的增加，GWO-HA優化系統的容量更優。

圖9和10仿真分析了當CUE用戶數為20，不同DUE用戶接入時， DUE用戶最大最小吞吐量變化情況。從圖9可知，隨著DUE用戶的增加，單個DUE用戶對的最小容量不斷減小。這是因為隨著DUE用戶的增加，信道復用的DUE數量增加使得對CUE用戶的干擾也增加，導致基站所受負載增加，系統內DUE用戶的最小容量性能下降。對于單個DUE用戶對的最小容量來說，所提算法略低于HS-HA，但明顯優于GA-HA。例如，當DUE用戶數為10時，單個DUE對的最小容量較HS-HA約低5 Mbps/Hz，較GA-HA約高20 Mbps/Hz。

從圖10中可以看出，隨著DUE接入用戶數的增加，CUE用戶的最大發射功率為17 dBm和23 dBm兩種情況下，單個DUE對的最大容量差別越來越小。這是因為，隨著接入車輛數的增加，單個DUE用戶受到的總干擾主要來自于各個DUE對帶來的干擾，而CUE用戶帶來的干擾表現減弱，從而當DUE用戶數較大時，例如20個DUE用戶時，不同CUE用戶最大發射功率下單個DUE用戶的最大容量基本趨于一致。圖10證實，隨著DUE用戶數的增加，GWO-HA和GA-HA下的單個DUE對的最大容量值不斷增加，而HS-HA下的單個DUE對的最大容量值基本呈現下降趨勢，且HS-HA較其他兩種算法的性能差距越來越大。例如，當DUE用戶數為15時、Pcmax=17 dBm，GWO-HA和GA-HA下的單個DUE對的最大容量為273 Mbps/Hz和264 Mbps/Hz，而HS-HA的容量僅為230 Mbps/Hz，GWO-HA較GA-HA和HS-HA容量分別提高了約3%和16%。這表明隨著DUE接入數量不斷增加中，GWO-HA中單個DUE對的最大容量改善尤為明顯。

5 結束語

本文提出了一種車聯網系統中的D2D資源分配策略。首先根據空間泊松分布構建高速公路車輛分布模型，以最大化系統D2D容量為優化目標;接著利用灰狼優化算法，使種群個體在α、β、δ三個最優個體的引導下，不斷向最優解靠近，輸出α狼的位置作為DUE用戶的最佳發射功率;最后采用匈牙利算法，最大化系統容量的情況下解決CUE用戶與DUE用戶一對一信道匹配問題。仿真結果表明，本文提出的結合灰狼優化算法和匈牙利算法（GWO-HA）的聯合資源分配算法可以通過復用CUE用戶的頻譜，有效提升頻譜利用效率，解決通信系統中的頻譜資源緊缺問題。同時，與和聲搜索算法和遺傳算法相比，所提GWO-HA是最優的。GWO-HA在改善DUE系統全局容量的同時，單個DUE對的最大吞吐量也是三種算法中最優的，最小吞吐量也優于GA-HA且接近于HS-HA。下一步的研究方向將放在基站只能獲取部分信道狀態信息的情況下，如何優化系統資源分配策略，以及如何優化CUE用戶的發射功率，進一步提升系統性能。

參考文獻：

[1]張進，蔡之駿，楊波.車聯網關鍵技術及應用研究［J］.汽車實用技術，2021，46（13）：23-26.（Zhang Jin， Cai Zhijun， Yang Bo. Research on key technologies and applications of Internet of Vehicles［J］.Automobile Practical Technology，2021，46（13）：23-26.）

［2]Kuutti S， Fallah S， Katsaros K， et al. A survey of the state-of-the-art localization techniques and their potentials for autonomous vehicle applications［J］.IEEE Internet of Things Journal，2018，5（2）：829-846.

［3]Storck C R， Duarte-Figueiredo F. A survey of 5G technology evolution， standards， and infrastructure associated with vehicle-to-everything communications by Internet of Vehicles［J］.IEEE Access，2020，8：117593-117614.

［4]Zhou Haibo， Xu Wenchao， Chen Jiacheng， et al. Evolutionary V2X technologies toward the Internet of Vehicles： challenges and opportunities［J］.Proceedings of the IEEE，2020，108（2）：308-323.

［5]Hayati M， Kalbkhani H， Shayesteh M G. Energy-efficient relay selection and power allocation for multi-source multicast network-coded D2D communications［J］.AEU-International Journal of Electro-nics and Communications，2021，128：153522.

［6]Alnasser A， Sun Hongjian， Jiang Jing. Recommendation-based trust model for vehicle-to-everything［J］.IEEE Internet of Things Journal，2020，7（1）：440-450.

［7]Wang Jian， Shao Yameng， Ge Yuming， et al. A survey of vehicle to everything （V2X） testing［J］.Sensors，2019，19（2）：334.

［8]劉煜恒，彭藝，付曉，等.聯合干擾控制與PSO的D2D網絡資源分配［J］.應用科學學報，2021，39（2）：338-346.（Liu Yuheng， Peng Yi， Fu Xiao， et al. D2D network resource allocation of joint interfe-rence control and PSO［J］.Journal of Applied Science，2021，39（2）：338-346.）

［9]Hamdi M， Zaied M. Resource allocation based on hybrid genetic algorithm and particle swarm optimization for D2D multicast communications［J］.Applied Soft Computing，2019，83：105605.

［10]趙季紅，董志海，樺曲，等.車聯網D2D通信中最大化頻譜資源利用率分配算法［J］.計算機應用研究，2021，38（7）：2145-2148.（Zhao Jihong， Dong Zhihai， Hua Qu， et al. Allocation algorithm for maximizing spectrum resource utilization in D2D communication of Internet of Vehicles［J］.Application Research of Computers，2021，38（7）：2145-2148.）

［11]Wang Xin， Qian Zhihong， Wang Xue， et al. Resource allocation scheme based on rate-requirement for device-to-device downlink communications［J］.International Journal of Pattern Recognition and Artificial Intelligence，2019，33（13）：1959040.

［12]Sun Yongjun， Wang Fanli. Joint resource allocation and interference management in the D2D uplink underlaying cellular networks［J］.Telecommunication Systems，2021，78（1）：57-64.

［13]Esmat H， Elmesalawy M， Ibrahim I. Adaptive resource sharing algorithm for device-to-device communications underlaying cellular networks［J］.IEEE Communications Letters，2016，20（3）：530-533.

［14]Hossen M S， Hassan M Y， Hussain F， et al. Relax online resource allocation algorithms for D2D communication［J］.International Journal of Communication Systems，2018，31（10）：e3555.

［15]Mach P， Becvar Z， Najla M. Resource allocation for D2D communication with multiple D2D pairs reusing multiple channels ［J］.IEEE Wireless Communications Letters，2019，8（4）：1008-1011.

［16]Wang Shanshan， Di Renzo M. On the meta distribution in spatially correlated non-Poisson cellular networks［J］.EURASIP Journal on Wireless Communications and Networking，2019，2019（1）：article No.161.

［17]Buzzi S， D’Andrea C， Fresia M， et al. Pilot assignment in cell-free massive MIMO based on the Hungarian algorithm［J］.IEEE Wireless Communications Letters，2021，10（1）：34-37.

［18]Standard 3GPP TR 36. 885 V2. 0. 0， Technical specification group radio access network： study LTE-based V2X services： （release 14）［S］.［S.l.］：3GPP，2016.

［19]Kyosti P， Meinila J， Hentila L， et al. IST-4-027756， Winner Ⅱ D1.1.2 V1.2：Winner Ⅱ channel models ［R］. Munich： Winner， 2007.

［20]卓干兵.蜂窩網絡中D2D通信無線資源分配算法研究［D］.南京：南京郵電大學，2020.（Zhuo Ganbing. Research on radio resource allocation algorithms for D2D communication in cellular networks［D］.Nanjing：Nanjing University of Posts and Telecommunications，2020.）