基于改進遺傳算法的D2D資源分配策略

安浩杰，彭 藝，劉煜恒，付曉霞

（昆明理工大學信息工程與自動化學院，昆明650500）

引 言

近些年，隨著智能設(shè)備的發(fā)展以及5G時代的到來，用戶對網(wǎng)絡的速度和容量的要求也隨之增高，從而對頻譜資源的需求也越來越高。但是傳統(tǒng)的蜂窩系統(tǒng)不允許終端設(shè)備直接通信，所有的通信數(shù)據(jù)都要經(jīng)過蜂窩網(wǎng)絡轉(zhuǎn)發(fā)，效率和資源利用率都不高，已經(jīng)無法滿足用戶日益增長的需求。D2D（Device to device）通信作為一種終端直通手段開始受到廣泛的關(guān)注［1-3］。D2D技術(shù)不需要經(jīng)過基站轉(zhuǎn)發(fā)就能夠?qū)崿F(xiàn)距離較近的兩個用戶直接進行信息交換，因此有效地提高了通信效率、資源的使用效率以及系統(tǒng)吞吐量。D2D通信按照其復用蜂窩系統(tǒng)資源的方式可以分為正交通信和非正交通信兩種模式。正交通信模式中蜂窩用戶（Cellular-users，CU）設(shè)備與D2D設(shè)備頻譜是正交的［4-7］，工作在此模式下的用戶不會產(chǎn)生干擾，但是這種模式的資源利用率較低。非正交通信模式中CU設(shè)備與D2D用戶的頻譜是非正交的，這種模式下資源使用效率較高，但是由于D2D用戶的位置是隨機的并且在復用蜂窩系統(tǒng)資源的同時會帶來嚴重的干擾［8-11］。因此干擾控制是D2D通信中的重要研究方向，而系統(tǒng)內(nèi)的干擾和D2D的功率息息相關(guān)，因此可以通過調(diào)節(jié)發(fā)射功率來限制干擾［12］。

D2D用戶的功率控制問題一直是近年來的研究熱點。文獻［13］提出一種啟發(fā)式算法，當D2D和CU進行信道分配時，會優(yōu)先滿足CU的需要；文獻［14］更近一步地對D2D的接入率同各設(shè)備之間信道增益的聯(lián)系進行了分析，并提出了一種基于貪婪思想的啟發(fā)式資源分配方法，提高了D2D的接入率及系統(tǒng)吞吐量；文獻［15］把智能化算法即Q學習應用到D2D資源分配中，提出一種基于Q學習的聯(lián)合資源分配和功率控制算法，把D2D發(fā)射端的功率控制問題轉(zhuǎn)化為Q學習問題。在學習過程中，不斷地動態(tài)調(diào)整發(fā)射功率，在保證服務質(zhì)量（Quality-of-service，QoS）的同時最大化系統(tǒng)吞吐量；文獻［16］在兼顧系統(tǒng)吞吐量和D2D對之間互相干擾的情況下，為了控制D2D用戶的功率，提出了一種干擾避免與資源管理算法。以上所述文獻能從不同方向解決D2D的資源分配問題，但是一般考慮的是CU和D2D只能一對一進行資源復用，這樣就對D2D技術(shù)的發(fā)展有了局限性，沒有使系統(tǒng)性能最大化。

因此，本文在當前研究的基礎(chǔ)上，對于一個CU的信道資源可以與多個D2D對共用的通信場景，提出一種基于改進自適應遺傳算法的資源分配策略。首先計算出能夠保證用戶QoS的D2D設(shè)備的發(fā)射功率，然后再利用改進的遺傳算法根據(jù)適應度條件對這個范圍內(nèi)的候選功率進行測算，根據(jù)適應度進行取舍，從而選擇出最優(yōu)的發(fā)射功率。仿真結(jié)果表明，改進后的遺傳算法相對于改進之前的標準遺傳算法其信道利用率提高了大約14%。

1 系統(tǒng)模型及問題描述

1.1 系統(tǒng)模型

本文研究的是蜂窩小區(qū)場景下的D2D通信資源分配問題，圖1為系統(tǒng)模型。由于D2D用戶復用的是CU的上行鏈路資源，假設(shè)當前整個系統(tǒng)處于全負載狀態(tài)，即所有的資源均被CU占用，且各個CU占用的資源相互正交不存在干擾。假設(shè)整個系統(tǒng)中的信道數(shù)為N，每個CU占有一個信道即CU的數(shù)目依然是N，同時還有M對D2D用戶。用集合C={1，2，…，N}，D={1，2，…，M}分別表示CU集合和D2D用戶集合，其中一個D2D對包含一個發(fā)射端和一個接收端。

根據(jù)文獻［17］，CUi和D2D用戶j的路徑損耗（Path-loss，PL）分別為

式中：di表示CU到基站的距離，dj表示D2D對之間的距離，f表示系統(tǒng)的載波頻率。

由文獻［18］可以得知，信道增益是由路徑損耗、多徑衰落帶來的快衰落以及陰影衰落帶來的慢衰落構(gòu)成。由此可知，信道增益為

式中：Γ為路徑損耗常數(shù)，μ為快衰落增益因子，ξ為慢衰落增益因子，d為距離，τ為路徑損耗指數(shù)。

因為一個資源可能被多個D2D用戶復用，所以CU就會受到復用相同頻譜資源的D2D用戶的干擾，把βj，i作為復用指示因子，當D2D用戶j復用CUi的頻譜資源時βj，i為1，否則βj，i為0。因此CUi的SINR表示為

圖1 系統(tǒng)模型Fig.1 System model

式中：PC表示CU的傳輸功率，為固定值；表示D2D用戶復用CU信道資源時的傳輸功率；Gi，B，Gjs，B分別表示CU到BS的信道增益和D2D對發(fā)射端到BS的信道增益；表示噪聲功率，表示滿足CUi通信服務質(zhì)量的最小SINR。

D2D用戶j在被復用的CUi信道資源上的SINR為

式中：Gjs，jr表示D2D用戶j的發(fā)射端到接收端的信道增益，Gi，js表示CUi到D2D用戶j接收端的信道增益，Gls，jr表示D2D用戶l發(fā)射 端對D2D用戶j接收端的信道增益。

中庸思想是中國傳統(tǒng)文化中人們認識世界、對待事物的基本方法之一，其“執(zhí)兩端而允中”的智慧對于華人的心理、思維和行為處事等各層面都有巨大而深遠的影響(思維，1999)。探究中庸在當代的表現(xiàn)形式和運作規(guī)律，有助于更好理解人們的生活方式和行為處事方法，提升生活品質(zhì)，促進社會和諧。

由香農(nóng)公式可知，CUi和D2D用戶j的傳輸速率（單位：bit/s）分別為

1.2 問題描述

若滿足式（4）的條件則βj，i為1，根據(jù)式（4）此時D2D的最小發(fā)射功率應該滿足

在對功率進行限制之后假設(shè)CU的信道資源都已經(jīng)確定，在保證其QoS的條件下，將最大化系統(tǒng)吞吐量作為目標函數(shù)為D2D用戶分配信道資源。根據(jù)式（6）和式（7），則目標函數(shù)與約束條件分別為

式中：Pmax表示D2D的最大發(fā)射功率，表示滿足CUi通信服務質(zhì)量的最小SINR，表示D2D的傳輸功率限制。其中，式（9）為最大化系統(tǒng)吞吐量的表達式，式（11）表示D2D的傳輸功率不應該超出限制閾值，式（12）表示一個D2D用戶只能復用一個CU的資源，并且一個CU的資源可以被多個D2D復用。由式（9～12）可知，本文定義的目標函數(shù)和其約束條件屬于混合整數(shù)非線性規(guī)劃問題（Mixed-integer-non-linear-problem，MINLP）。

2 改進的自適應遺傳算法

然而MINLP問題用一般的方法很難求得最優(yōu)解，而標準遺傳算法通過二進制編碼尋找最優(yōu)解，易陷入部分最優(yōu)，并且存在算法搜索速度較慢、易早熟等缺點。采用實數(shù)方式進行編碼的遺傳算法能直接搜索解空間，與二進制編碼相比更加的快速和準確，因此本文首先采用實數(shù)編碼的方法，改進了交叉算子和遺傳算子的計算方法，并引進精英保存方案避免破壞已經(jīng)產(chǎn)生的較好個體，在整個限制區(qū)域內(nèi)搜索最優(yōu)解并確定D2D的最優(yōu)發(fā)射功率。

其次，標準遺傳算法中的交叉和變異算子均采用固定值。交叉率越大，進化速度越快，但是進化速度過快很容易把進化時產(chǎn)生的較好個體給破壞掉，容易讓算法局部收斂；反之，交叉率越小，又會導致進化搜索過程緩慢甚至停滯。若變異率取值較大，就會使遺傳算法變成隨機算法，從而使得結(jié)果無法達到全局收斂；如果取值較小，就會使得種群產(chǎn)生全新個體的幾率變小。因此，對于這兩個算子的取值一定要符合進化的實際要求，標準遺傳算法的交叉率一般取值在0.4～0.99這個范圍內(nèi)，變異率的取值在0.001～0.2范圍內(nèi)。針對交叉率和變異率的取值問題，本文結(jié)合改進粒子群算法中基于非線性動態(tài)的慣性權(quán)重策略對交叉率進行改進，改進的動態(tài)自適應交叉率Pc的表達式為

對于變異率，本文結(jié)合改進粒子群算法中基于反余弦策略的非線性學習因子思想來對變異率進行改進［19］，改進的動態(tài)自適應變異率Pm的表達式為

圖2 自適應交叉率和變異率Fig.2 Adaptive crossover rate and mutation rate

由圖2可知，本文設(shè)計的自適應交叉率和變異率均滿足要求。而文中所說的精英保留方案其實就是擇優(yōu)而取即將每一輪新產(chǎn)生的高適應度個體同上一輪的高適應度個體進行比較，觀察二者的適應值高低，若上一輪的適應值更高，則用上一輪的高適應度個體隨機替換新一輪中的低適應度個體。精英保留使得最優(yōu)個體免受遺傳操作的破壞。因此，精英保留方案是保證算法收斂的重要方法。

綜上論述，本文設(shè)計算法的計算流程如圖3所示。

3 仿真結(jié)果及性能分析

3.1 仿真參數(shù)

為驗證本文提出算法的有效性，使用M ATLAB進行仿真分析。本次仿真的蜂窩系統(tǒng)設(shè)為半徑500 m的正六邊形區(qū)域，系統(tǒng)中CU和D2D隨機分布于其中，其中為了保證QoS，D2D對之間的距離限制在50 m內(nèi)。主要的仿真參數(shù)如表1所示。

圖3 自適應遺傳算法流程圖Fig.3 Flow chart of adaptive genetic algorithm

3.2 復雜度和仿真結(jié)果分析

3.2.1 復雜度分析

除系統(tǒng)性能外，算法的復雜度也是體現(xiàn)算法優(yōu)劣的重要指標。在此，分析改進的自適應遺傳算法對整體復雜度的影響。假設(shè)種群大小為N，迭代T次，并且計算適應值所需的時間復雜度是O(t)，那么改進的自適應遺傳算法的時間復雜度就是O(N×T×t)。由于算法只是改進了交叉和變異兩個算子，因此與標準遺傳算法相比，需要相同的復雜度。雖然和標準遺傳算法相比，本文算法的復雜度沒有降低，但是系統(tǒng)性能得到了優(yōu)化，因此優(yōu)于標準遺傳算法。

3.2.2 仿真結(jié)果

為了驗證本文算法的性能，在仿真參數(shù)設(shè)置相同的前提下，將本文所提算法與以下3種算法的性能進行了比較：改進之前的標準遺傳算法以及兩種經(jīng)典算法即文獻［9］提出的啟發(fā)式算法和隨機算法。為了便于比較本文將對比算法進行了多對一情況下的仿真。隨機算法就是將D2D發(fā)射功率在不超過最大值的前提下隨機選擇。

表1 主要仿真參數(shù)Table 1 Main simulation parameters

在不同的D2D對數(shù)條件下，其信道利用率的變化曲線如圖4所示。由圖可見隨著D2D對的增加，系統(tǒng)的信道利用率呈下降趨勢，這是因為隨著D2D對數(shù)的增加D2D對以及CU和D2D之間的干擾越來越復雜，從而導致信道利用率下降。在相同條件下，本文算法分別比標準遺傳算法、啟發(fā)式算法和隨機算法的信道利用率提高了14%、19%、27%。

圖4 信道利用率變化曲線Fig.4 Channel utilization curves

對于不同的D2D用戶數(shù)目，4種算法的D2D資源分配策略的系統(tǒng)吞吐量變化曲線如圖5所示。圖5描述的是當CU的數(shù)量是50的時候，4種算法的系統(tǒng)吞吐量隨著D2D對數(shù)量不斷增加的變化趨勢。并且因為4種算法都能實現(xiàn)多個D2D用戶復用一個頻譜資源，因此隨著D2D對數(shù)量的增加，系統(tǒng)吞吐量也隨之不斷增加。但是當D2D對的數(shù)量超過10之后，吞吐量的增加速度就逐漸降低，這是因為隨著用戶數(shù)目的增多，系統(tǒng)內(nèi)的干擾也在增加，因此增長趨勢逐漸放緩。

為了測試本文方案下的D2D用戶的通信質(zhì)量，采用累計分布函數(shù)圖描述4種資源分配算法的系統(tǒng)吞吐量的分布情況。4種資源管理方案下D2D用戶的系統(tǒng)吞吐量累計分布函數(shù)圖的變化趨勢如圖6所示，從圖6中的曲線趨勢可以看出本文算法在取同一CDF的情況下系統(tǒng)吞吐量明顯優(yōu)于另外3種算法的系統(tǒng)吞吐量，說明系統(tǒng)性能得到了提高。

綜上所述，本文所提改進的遺傳算法能夠解決標準遺傳算法搜索速度慢、易早熟以及容易陷入局部最優(yōu)解等問題，能夠有效提升系統(tǒng)性能。

圖5 系統(tǒng)吞吐量變化曲線Fig.5 System throughput change curves

圖6 系統(tǒng)平均吞吐量的累積分布函數(shù)Fig.6 Cumulative distribution function of the average throughput of the system

4 結(jié)束語

本文針對D2D用戶在復用蜂窩系統(tǒng)資源時帶來的干擾和資源分配問題，提出一種基于改進自適應遺傳算法的資源分配策略，該方案在保證QoS的條件下通過尋找D2D用戶的最優(yōu)發(fā)射功率，達到降低系統(tǒng)干擾和吞吐量最大化的目的。因為本文是針對多個D2D用戶能復用同一CU資源的情況下對比以往的CU與單個D2D對共享資源的情況，資源利用率得到了提升。并且在與其他3種優(yōu)化方法進行對比測試后，由仿真結(jié)果可以看出本文算法明顯優(yōu)于對比算法，能有效地提高信道利用率和系統(tǒng)吞吐量。