陳發(fā)堂，陳永鈦，陳 峰，王 丹

重慶郵電大學(xué)通信與信息工程學(xué)院，重慶400065

設(shè)備間通信是一種不需要借助基站，讓用戶設(shè)備之間直接進行數(shù)據(jù)通信的通信模式[1]。隨著當(dāng)今通信需求的日益增長，設(shè)備到設(shè)備（device to device,D2D）通信技術(shù)作為一種可以增加蜂窩系統(tǒng)資源復(fù)用率和系統(tǒng)總速率的方法吸引了廣泛的關(guān)注。該技術(shù)引入了4 種不同類型的增益[2]：設(shè)備間高度接近引起的比特率增益、蜂窩用戶和D2D 用戶之間同時復(fù)用資源引起而獲得的復(fù)用增益、當(dāng)經(jīng)由傳統(tǒng)蜂窩通信模式的接入點連接時，使用單個D2D 模式而不是使用單獨的上下行鏈路資源而獲得的跳數(shù)增益、D2D 用戶拓寬了蜂窩網(wǎng)絡(luò)的覆蓋范圍而獲得的覆蓋增益。在第三代合作伙伴計劃（3rd generation partnership project,3GPP）中，D2D用戶被分配用于接收調(diào)度分配的時間和頻域資源池，采用共享載波的模式與蜂窩網(wǎng)絡(luò)復(fù)用資源[3]。由于D2D 用戶與蜂窩用戶共享下行鏈路資源時會產(chǎn)生嚴(yán)重的帶內(nèi)泄露及遠(yuǎn)近效應(yīng)，因此側(cè)行鏈路共享載波時只能選擇上行鏈路資源。然而鏈路資源的共享不可避免會產(chǎn)生D2D 用戶與蜂窩用戶間的干擾，同時多個D2D 用戶復(fù)用一條通信鏈路時，設(shè)備之間也會產(chǎn)生干擾，嚴(yán)重影響通信質(zhì)量和網(wǎng)絡(luò)性能[4]。因此，考慮如何有效控制干擾的資源管理算法成為蜂窩網(wǎng)下D2D 通信的研究熱點。

一個有效的解決辦法便是通過功率控制進行干擾管理，文獻[5] 提出了一種預(yù)定義的最大功率電平用于干擾管理，從而達到降低D2D 發(fā)射機干擾強度的目的，保證蜂窩用戶的通信質(zhì)量。同時，復(fù)雜的功率控制算法常用于最小化功率消耗或者最大化整個網(wǎng)絡(luò)的容量，如文獻[6] 提出了基于粒子群的功率控制方案，但該方案所提算法的復(fù)雜度并不能滿足當(dāng)前通信的需求且容易陷入局部最優(yōu)解。除了功率控制的方法，另一個高效的算法便是設(shè)計一種智能的資源管理算法?？紤]干擾抑制的信道分配算法是D2D 通信干擾管理問題領(lǐng)域中的研究熱點[7]。文獻[8] 提出了一種基于兩階段拍賣的公平資源分配算法，在第1 階段以最小化總的系統(tǒng)干擾為條件進行用戶匹配，第2 階段根據(jù)競標(biāo)數(shù)值進行用戶匹配更新及剩余用戶分配；文獻[9] 針對公平和受限的情況下分別提出了基于貪婪的資源分配算法；文獻[10] 將最小背包算法與貪婪算法進行結(jié)合。文獻[8-10] 僅針對單個D2D 用戶與蜂窩用戶復(fù)用上行鏈路資源的情況，不能解決有限頻譜資源與用戶更優(yōu)通信質(zhì)量之間的矛盾。文獻[11] 提出了用于干擾管理的一種基于背包的干擾感知算法資源分配算法，然而該算法并不能讓所有D2D 用戶處于公平競爭的狀態(tài)且在許多情況下不存在可行解；文獻[12] 提出了復(fù)用強度因子的概念，先執(zhí)行匈牙利算法進行初始分配，再根據(jù)復(fù)用強度因子將剩余的D2D 用戶復(fù)用到信道中；文獻[13]提出一種新的基于貪婪算法的信道分配算法，將信道分配問題轉(zhuǎn)化為圖著色的問題；文獻[14]將超圖理論運用到信道分配中，以協(xié)調(diào)用戶之間的相互干擾。文獻[12-14] 所提算法復(fù)雜度過高，不能滿足用戶高速移動下實時完成數(shù)據(jù)互通的需求。通過前人的研究可知圖論是解決此類資源分配問題的有效工具，然而傳統(tǒng)的基于圖的資源管理算法并不能很好地滿足當(dāng)今用戶與日俱增的通信需求。因此，如何優(yōu)化傳統(tǒng)的圖理論算法以滿足當(dāng)下的需求值得深入研究。

針對上述情況的不足，本文提出一種基于K-means 與Gale-Shapley 算法的D2D 通信干擾管理資源分配算法。在進行資源共享前，首先對D2D 用戶進行處理，以最小化系統(tǒng)干擾為條件進行分組，在保證用戶正常通信質(zhì)量的情況下實現(xiàn)系統(tǒng)干擾最小化，同時實現(xiàn)蜂窩用戶與D2D 用戶的多對一復(fù)用。完成分組后，實施基于Gale-Shapley 穩(wěn)定匹配算法的信道分配方案，保證用戶的公平性并實現(xiàn)系統(tǒng)容量最大化。與基于貪婪的圖著色算法、隨機算法和傳統(tǒng)的圖著色算法比較可得，本文所提算法相較隨機算法和傳統(tǒng)的圖算法在系統(tǒng)容量方面有15%～50% 的提升，與基于貪婪的圖著色算法相比，本文所提算法在犧牲一定系統(tǒng)容量換取了更高效的干擾管理，保證整個蜂窩網(wǎng)絡(luò)的正常工作。

1 系統(tǒng)模型與問題規(guī)劃

1.1 系統(tǒng)模型與信道模型

為更加直觀地體現(xiàn)通信系統(tǒng)模型，我們考慮整個蜂窩網(wǎng)絡(luò)由一個基站、N個蜂窩用戶（以下簡稱CUE）和M個D2D 用戶（以下簡稱DUE）組成，其中N={c1,c2,···,cn},n≤N，M={d1,d2,···,dm},m≤M。在這里DUE 一般由兩部分組成，用dT 表示DUE的發(fā)射機，dR 表示DUE 的接收機。正交頻分復(fù)用技術(shù)用于支持CUE 和DUE 的多址接入，其中有K條信道用于分配資源。在整個通信系統(tǒng)中，演進型基站（eNB）負(fù)責(zé)協(xié)調(diào)CUE 與DUE 之間的資源分配，用Pc表示CUE 的發(fā)射功率，Pd表示DUE 的發(fā)射功率。通過隨機生成算法生成的蜂窩網(wǎng)絡(luò)用戶位置分布圖如圖1 所示。

圖1 蜂窩網(wǎng)絡(luò)用戶位置分布圖（N=10, M=20）Figure 1 Location map of cellular network users (N=10, M=20)

本文主要側(cè)重于D2D 通信在蜂窩網(wǎng)絡(luò)中上行鏈路的場景，當(dāng)復(fù)用上行資源時，D2D 接收機會受到來自蜂窩用戶的干擾，同時eNB 也會面臨來自D2D 發(fā)射機的干擾。在本文描述的通信系統(tǒng)中，信道被建模為瑞利衰弱信道，因此各個信道響應(yīng)都遵從獨立且相同分布的高斯過程。在文獻[15] 中描述了城市微系統(tǒng)（UMi）的路徑損耗模型，本文借鑒使用的與距離相關(guān)的路徑損耗模型如下

式中：d為不同設(shè)備之間的通信距離；fc為載波頻率。

信道增益與干擾表示為信道損失與小尺度衰弱的乘積的形式

式中：PathLossa,b代表通信設(shè)備a 和通信設(shè)備b 之間的信道損失；ha,b表示通信設(shè)備a 和通信設(shè)備b 之間的小尺度衰弱。在接下來的公式中，Gc,eNB表示蜂窩用戶與eNB 之間的信道增益，GdT,dR表示D2D 發(fā)射機與接收機之間的信道增益，GdT,eNB表示D2D 發(fā)射機對CUE在eNB 處的信道干擾，Gc,dR表示CUE 對DUE 在D2D 接收機的信道干擾，GdT′,dR表示D2D 用戶之間的信道干擾。

1.2 問題規(guī)劃

本文主要針對信道的分配問題，其中多個DUE 都會分配一個CUE，分配意味著DUE 與CUE 將會共享信道資源。我們的目標(biāo)是在保證整個通信網(wǎng)絡(luò)用戶在正常工作的前提下，最大化整個系統(tǒng)的通信容量。當(dāng)DUE 與CUE 共享信道資源時，不可避免會產(chǎn)生干擾，反之亦然。同時多個DUE 復(fù)用一條信道時，不同DUE 之間也會產(chǎn)生干擾，因此在eNB 處與DUE 接收機處的SINR 表達式為

式中：N0為噪聲功率；I為相鄰小區(qū)之間的干擾；是一個二進制變量，=0 表示該DUE不與該CUE 復(fù)用第k條信道，反之則代表復(fù)用該信道。

在整個通信網(wǎng)絡(luò)中，干擾項主要由3 部分組成：

2）C2D 干擾項即式(4) 中的Gc,dRPc，這是CUE 在DUE 接收機處的干擾項，也可表達為蜂窩鏈路對D2D 鏈路的干擾；

整個蜂窩網(wǎng)絡(luò)的通信鏈路及干擾示意如圖2 所示。

圖2 蜂窩異構(gòu)網(wǎng)絡(luò)中鏈路及干擾示意圖Figure 2 Schematic diagram of link and interference in cellular heterogeneous network

根據(jù)香農(nóng)公式可得整個通信網(wǎng)絡(luò)的信道容量為

因此我們可以得到優(yōu)化問題的目標(biāo)函數(shù)及約束條件為(6)～(9)

式(6) 為CUE 處的SINR 必須要大于門限值，在保證CUE 的正常工作的前提下與DUE共享信道資源；式(7) 為DUE 接收機處的SINR 必須要大于門限值，在保證DUE 正常工作的前提下盡可能多的復(fù)用多個DUE；式(8) 保證一條信道只能復(fù)用一個CUE，確保蜂窩用戶之間不會互相干擾。

2 基于K-means 與Gale-Shapley 算法的D2D 干擾管理方案

在D2D 通信中，圖論是對解決與蜂窩用戶共享資源的一種非常有效的工具，然而傳統(tǒng)的圖論匹配算法僅支持一對一的匹配，而不能實現(xiàn)多對一的匹配，這對D2D 的發(fā)展造成極大的限制。為此，我們在進行匹配算法之前，先對DUE 進行預(yù)處理，采用K-means 聚類算法讓DUE 成組，一個DUE 組與一個CUE 共享信道，這樣既能運用圖論的理論解決資源分配問題，又能夠?qū)崿F(xiàn)一對多的復(fù)用且保證用戶間的公平性。

2.1 基于K-means 的用戶分組算法

在利用K-means 算法實現(xiàn)用戶分組前，首先進行蜂窩網(wǎng)絡(luò)用戶位置隨機生成算法，使所有用戶在限定范圍內(nèi)隨機分布于小區(qū)中且DUE 的發(fā)射機與接收機距離限定在50 m 以內(nèi)。

1）隨機選取N個DUE 坐標(biāo)作為初始聚類中心μ=μ1,μ2,···,μN；

為使該算法收斂，定義損失函數(shù)：

在K-means 用戶分組算法中，最終優(yōu)化目標(biāo)為

假設(shè)當(dāng)前目標(biāo)沒有達到最小值，可以通過固定每個分組的聚類中心μj，調(diào)整每個DUE的所屬的分組φ(i) 來讓目標(biāo)函數(shù)減少，同樣也可以固定φ(i)，調(diào)整每個分組的聚類中心達到最終優(yōu)化目標(biāo)。當(dāng)目標(biāo)收斂到最小值時，完成用戶分組。通過分析等式(1) 與(4) 可得，通過K-means 算法，能夠使D2D 用戶得到有效分組。同時，將該分組算法與后續(xù)的Gale-Shapley算法結(jié)合使用，使得在獲得系統(tǒng)容量提升的同時，能夠有效降低用戶之間的干擾影響。

2.2 基于Gale-Shapley 的資源分配算法

Gale-Shapley 資源分配算法的核心思想在于偏好表的建立。偏好表為兩組待匹配的樣本組中每個樣本對別的組別中各個樣本的喜好程度，例如樣本組中1 號樣本的偏好表為{3,1,2,4,5}，則表示該樣本對對方樣本組的樣本最優(yōu)先匹配意愿為3 號樣本，其次為1 號樣本，以此類推。在本文中，樣本組分別為CUE：c1,c2,···,cn,n≤N及DUE組：j1,j2,···,jn,n≤N。CUE 樣本組與DUE 組樣本組建立的偏好表分別記為CU_LIKE與DU_LIKE。通過Gale-Shapley 匹配算法，根據(jù)雙方偏好表的選擇實現(xiàn)CUE 與DUE 組的匹配，最大化通信系統(tǒng)容量。

結(jié)合K-means 算法與Gale-Shapley 算法，本文設(shè)計的D2D 通信干擾管理方案如下：

步驟1初始化參數(shù)，隨機生成CUE 與DUE 的坐標(biāo)位置，設(shè)置各用戶的發(fā)射功率，根據(jù)式(1) 計算路徑損失并根據(jù)式(2) 計算各用戶到eNB 的信道增益；從DUE 坐標(biāo)點中隨機選取N個點作為聚類中心；確定迭代次數(shù)x。

步驟2預(yù)分組過程，計算DUE 各點到聚類中心的距離，進行D2D 用戶分組過程。在完成一輪分組之后，更新聚類中心點位置，重新執(zhí)行步驟2，直到不再改變或者達到最大迭代次數(shù)停止。

步驟3對組成員進行篩選，根據(jù)式(1)～(4)，為保證用戶正常通信質(zhì)量，對DUE 組用戶進行篩選，讓每組D2D 用戶與蜂窩用戶匹配進行SINR 的計算，如若存在某一設(shè)備的SINR小于門限值，則剔除D2D 組成員干擾貢獻值最大成員，重新計算每個設(shè)備的SINR 直至所有設(shè)備均滿足式(6)～(7)。

步驟4建立Gale-Shapley 算法偏好表，將蜂窩用戶和D2D 用戶劃分為兩個點集合，同時建立蜂窩用戶和D2D 用戶組的偏好程度表，用于存儲雙方用戶相互之間的偏好程度。通過分析式(3)～(4)，將作為確定CUE 偏好表的依據(jù)，Gc,dRPc作為確定DUE偏好表的依據(jù)，建立CUE 偏好表和DUE 組偏好表，作為匹配算法的匹配依據(jù)。

步驟5執(zhí)行Gale-Shapley 穩(wěn)定匹配算法，輪詢蜂窩用戶，若當(dāng)前蜂窩用戶已有配對對象則跳過輪詢，否則會根據(jù)當(dāng)前輪詢用戶的偏好表，向偏好程度排位靠前的D2D 用戶發(fā)起配對請求。如果當(dāng)前D2D 用戶未完成匹配則兩者結(jié)成配對，否則被選擇的D2D 用戶將會根據(jù)自身偏好表選擇配對對象。若發(fā)起請求的蜂窩用戶在偏好表中的位置比當(dāng)前已配對的蜂窩用戶靠前，則被選擇的D2D 用戶會與之前匹配的蜂窩用戶解除匹配，與當(dāng)前輪詢蜂窩用戶匹配；反之則會拒絕配對請求，被拒絕的蜂窩用戶會加入到下一輪次的輪詢中。不斷遍歷剩余蜂窩用戶，直至所有蜂窩用戶完成配對或者當(dāng)前配對陣容不再改變，算法終止。

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

為了驗證所提算法的性能，本文用Matlab R2020a 進行仿真。在小區(qū)半徑為200 m 的蜂窩小區(qū)中，隨機生成蜂窩用戶與D2D 用戶的位置。為保證仿真結(jié)果的可靠性，本文采用Monte Carlo 方法重復(fù)執(zhí)行算法2 000 次，最后取平均值作為最終的仿真結(jié)果進行性能分析，具體仿真環(huán)境的參數(shù)設(shè)置如表1 所示。

表1 仿真參數(shù)Table 1 Simulation parameters

采用K-means 算法來完成用戶分組，進行干擾管理，此算法復(fù)雜度為O(n ?l ?k ?m)，其中n為樣本點數(shù)，l為迭代次數(shù)，k為簇的數(shù)目，m為樣本維度，因此該算法復(fù)雜度可簡化為O(M)。在完成DUE 分組之后執(zhí)行Gale-Shapley 算法完成DUE 組與CUE 共享信道資源，實現(xiàn)多對一復(fù)用，此算法復(fù)雜度為O(N2)。因此本文總的時間復(fù)雜度為O(M+N2)。

為了驗證所提算法的性能，將基于Gale-Shapley 算法的D2D 干擾管理資源分配算法與基于貪婪的圖著色算法（GGC）、隨機算法（RA）和傳統(tǒng)的圖著色算法（GC）進行比較。同時為了更好的評估算法的公平性，采用Jain’s fairness 指數(shù)[16]來衡量各算法的性能，通過分析該公式可知隨著該系數(shù)值的增加，算法的公平性越高，以此來確定設(shè)備是否獲得了系統(tǒng)資源的公平共享。

在蜂窩用戶數(shù)量為10 的情況下，不同算法在D2D 對數(shù)目逐漸增加的情況下對系統(tǒng)容量的影響如圖3 所示。通過分析可得，本文所提算法在D2D 對數(shù)量小于20 時，系統(tǒng)容量遠(yuǎn)大于其余3 種算法的系統(tǒng)容量。當(dāng)D2D 對數(shù)量大于20 時，所提算法與GC 和RA 算法相比，系統(tǒng)容量仍有較大的提升，與GGC 相比系統(tǒng)容量有所下降，原因是本文在滿足蜂窩網(wǎng)絡(luò)中所有用戶通信質(zhì)量的同時，為保證公平性，盡可能讓更多的DUE 能夠復(fù)用上行鏈路的資源所致。

圖3 D2D 對數(shù)量對系統(tǒng)容量在不同算法下的影響(N=10)Figure 3 Impact of D2D pair quantity on system capacity under different algorithms (N=10)

圖4 分析比較了各算法的Jain’s fairness 指數(shù)。通信鏈路在受到強干擾時，會極大地限制整個系統(tǒng)容量，因此分析各用戶之間的干擾影響尤其重要。通過分析圖4 可得，本文所提的算法實現(xiàn)較高的Jain’s fairness 指數(shù)，這是由于本文在用戶分組階段以最小化組別累計干擾值為目標(biāo)，且在進行復(fù)用匹配時，旨在最小化整體干擾的情況下盡可能提升整個蜂窩網(wǎng)絡(luò)的系統(tǒng)容量。與其余3 個算法相比，本文所提算法有較大的提升，可見本文所提算法的優(yōu)越性。

圖4 D2D 對Jain’s fairness 指數(shù)在不同算法下的影響(N=10)Figure 4 Impact of D2D pair quantity on Jain’s fairness index under different algorithms(N=10)

圖5 分析了本文所提算法中蜂窩數(shù)量對整個系統(tǒng)容量的影響。通過逐漸遞增蜂窩用戶的數(shù)量，分別在DUE 對數(shù)量為30、40 和50 的情況下，研究了蜂窩用戶數(shù)量對系統(tǒng)容量的影響。由圖可得在3 種不同的情況下，蜂窩用戶的數(shù)量與系統(tǒng)容量成正相關(guān)，隨著蜂窩用戶數(shù)量的增加，整個蜂窩網(wǎng)絡(luò)的系統(tǒng)容量也穩(wěn)定增加，確保本算法的可靠性。

圖5 本文所提算法中蜂窩用戶數(shù)量對系統(tǒng)容量的影響Figure 5 Impact of the number of cellular users on the system capacity in the proposed algorithm

4 結(jié)語

本文所提出的基于K-means 與Gale-Shapley 算法的D2D 干擾管理方案能夠在蜂窩用戶與D2D 用戶共享信道資源的場景下，實現(xiàn)整體干擾最小化和系統(tǒng)容量最大化。以往的信道資源分配算法往往是在完成一對一復(fù)用之后再通過其他方式實現(xiàn)多對一復(fù)用，而本文所提算法為實現(xiàn)整個蜂窩網(wǎng)絡(luò)整體干擾最小，在進行信道資源共享前，先對D2D 用戶進行分組處理，保證D2D 用戶公平性的同時以最小化蜂窩網(wǎng)絡(luò)整體干擾為條件完成分組，最后實施穩(wěn)定匹配算法以最大化整個蜂窩系統(tǒng)的通信容量。通過與基于貪婪的圖著色算法、隨機算法和傳統(tǒng)圖著色算法相比較，本文在干擾管理方面性能表現(xiàn)出色，且算法復(fù)雜度僅為O(M+N2)，能夠滿足D2D 用戶在高速移動的場景下的通信需求。