D2D 中基于鳥群算法的資源分配和模式選擇方案

李永吉，楊永立，王立棟，黃 哲，郭啟航

（武漢科技大學(xué) 信息科學(xué)與工程學(xué)院，武漢430081）

設(shè)備到設(shè)備D2D 通信是5G 中的終端直通技術(shù)[1]。短距離的通信用戶不經(jīng)過基站的轉(zhuǎn)發(fā)而直接進(jìn)行信息交互的通信模式是D2D 通信。該方式有效地降低了基站負(fù)載、通信時延和路徑損耗；由于是短距離直接通信，通信相對安全；通信時消耗功率較低，進(jìn)而增加了電池壽命[2]；相對于其它不依靠基礎(chǔ)網(wǎng)絡(luò)設(shè)施的直通技術(shù)而言，D2D 更加靈活，既可以在基站控制下進(jìn)行連接及資源分配，也可以在無網(wǎng)絡(luò)基礎(chǔ)設(shè)施的時候進(jìn)行信息交互[3]；D2D用戶復(fù)用蜂窩用戶的頻譜資源，有效提高了頻譜利用率。但是，由于共用頻譜自然會造成各用戶之間的干擾，現(xiàn)有的很多研究都是圍繞解決這些問題展開的。

1 國內(nèi)外研究現(xiàn)狀

文獻(xiàn)[4]提出一種基于整體干擾最小的資源分配策略，在D2D 鏈路質(zhì)量進(jìn)行排序時損耗較大；文獻(xiàn)[5]在此基礎(chǔ)上將問題轉(zhuǎn)化為對資源復(fù)用因子進(jìn)行0-1 的最優(yōu)指派問題，一定程度上降低了算法復(fù)雜度；文獻(xiàn)[6]使用頻率復(fù)用的方法減少小區(qū)間的干擾，使用劃定干擾限制區(qū)域的方法減少小區(qū)內(nèi)的干擾。頻率復(fù)用的方法雖然可以減少干擾，但是會造成極大的頻譜資源浪費，在頻譜資源稀缺的現(xiàn)實情況下，顯然此種方法實際的使用價值不高。

文獻(xiàn)[7]提出了資源分配和資源復(fù)用的聯(lián)合分配算法，首先使用比例公平算法給蜂窩用戶分配資源，然后使用啟發(fā)式的貪婪算法給D2D 用戶分配復(fù)用資源，割裂了D2D 用戶和蜂窩用戶在資源分配時的聯(lián)系，且沒有模式選擇方案，因此對系統(tǒng)性能提升作用不大。文獻(xiàn)[8]將D2D 資源分配問題建模成一個整數(shù)非線性最優(yōu)化問題，并通過貪婪和啟發(fā)式算法對該問題進(jìn)行了求解，得出的結(jié)果可以使D2D 用戶與蜂窩用戶的SINR 之和達(dá)到最大，從而達(dá)到小區(qū)信道容量最大的目的。該方案雖然可以達(dá)到最優(yōu)，但是需要逐一計算小區(qū)內(nèi)的蜂窩用戶和D2D 用戶的SINR，算法復(fù)雜度較高，效率較低。

針對上述文獻(xiàn)的不足，在此提出了聯(lián)合資源分配和模式選擇的算法，提高D2D 通信模式的靈活性和空間復(fù)用率。

2 系統(tǒng)模型

系統(tǒng)模型如圖1 所示。考慮基于正交頻分多址OFDMA （orthogonal frequency division multiple ac cess）支持的單小區(qū)混合D2D 通信蜂窩網(wǎng)絡(luò)模式。由于下行通信基站功率較大會對D2D 用戶造成較大干擾，因此考慮小區(qū)共享上行鏈路資源。假設(shè)鏈路是完全信道狀態(tài)信息。小區(qū)內(nèi)有M 個隨機分布的蜂窩用戶（cell users）組成集合Cu=｛Cu1，Cu2，…，CuM｝；小區(qū)內(nèi)有N 對隨機分布的D2D 用戶（D2D users）組成集合Du=｛Du1，Du2，…，DuN｝；D2D 對中的發(fā)射端、接收端分別記為DuT_i，DuR_i（即第i 對D2D 中的發(fā)射端、接收端）；系統(tǒng)資源塊個數(shù)為K個，組成集合為Rb=｛Rb1，Rb2，…，RbK｝，資源塊個數(shù)不少于蜂窩用戶個數(shù)，即K>=M；基站BS（base station）位于小區(qū)中心，各信道服從瑞利衰落模型。

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

在引入D2D 通信之前，蜂窩用戶的信干燥比SINR（signal to interference plus noise ratio）為

式中：Rck為只有第k 個蜂窩用戶通信時的SINR；Pck為蜂窩用戶的發(fā)送功率；Gck為蜂窩鏈路的信道增益；Ick為小區(qū)內(nèi)干擾；N0為高斯白噪聲。此時，系統(tǒng)吞吐量為

式中：ω 為頻譜資源塊的帶寬。

引入少量D2D 用戶之后，由于用戶較少，則按照文獻(xiàn)[9]為D2D 用戶預(yù)留正交頻譜資源是完全滿足的，而且這種情況除了能提高頻譜利用率外，還能有效地避免2 種用戶之間的干擾。但是這只適用于D2D用戶很少的情況，現(xiàn)實情況往往不是這樣。此時蜂窩用戶的SINR 和吞吐量同上。D2D 用戶的SINR 為

式中：Rdk為D2D 用戶的SINR；Pdk為D2D 中的第k個用戶的發(fā)送功率；Gdk為D2D 鏈路的信道增益；Idk為小區(qū)內(nèi)干擾。D2D 用戶的吞吐量為

則小區(qū)總的吞吐量C 為

D2D 通信負(fù)載增加到一定程度，預(yù)留的頻譜資源不足以滿足正交D2D 用戶，堅持正交模式則頻譜利用率得不到提升，故使D2D 用戶復(fù)用蜂窩用戶的上行頻譜資源。此時蜂窩用戶的SINR 為

其中 1≤i≤N，1≤k≤M

吞吐量為

D2D 用戶的SINR 為

其中 1≤i≤M，1≤k≤N

吞吐量為

此時，小區(qū)總吞吐量為

該系統(tǒng)的優(yōu)化目標(biāo)是在保證蜂窩用戶和D2D用戶的服務(wù)質(zhì)量的前提下最大化吞吐量，最小化各用戶之間的干擾，則在此采用的約束條件為

式（11）為最大化吞吐量；式（12）和式（13）設(shè)定最小接收信干燥比閾值，以確保用戶能正常通信；式（14）和式（15）通過設(shè)定功率閾值，有效抑制干擾，保證用戶服務(wù)質(zhì)量。該約束容易陷入局部最優(yōu)而難以找到全局最優(yōu)解，鳥群算法BSA（bird swarm algorithm） 具有優(yōu)于大多數(shù)啟發(fā)式算法的跳出局部最優(yōu)解的能力及穩(wěn)定性[10]。因此，決定采用一種生物啟發(fā)式算法——鳥群算法，完成這部分工作。

3 鳥群算法

3.1 基本原理

2015 年由Meng Xian-bing 提出的鳥群算法BSA，是計算機智能領(lǐng)域中一種生物啟發(fā)式智能優(yōu)化算法。該算法模擬鳥群覓食行為、警覺行為、遷移行為，同時具有粒子群算法和微分進(jìn)化算法的優(yōu)點，搜索效率較高而且穩(wěn)定性較好。算法中，每個虛擬鳥類的位置就代表了問題中的一組潛在解，其分散搜索的方式有利于保持其種群多樣性，避免陷入局部最優(yōu)解。計算鳥群的社會行為可以簡化為以下理想規(guī)則：

規(guī)則a每只鳥可隨機選擇警惕行為或覓食行為。

規(guī)則b選擇覓食行為時，每只鳥可以迅速記錄和更新自身先前尋找食物的最佳位置，鳥群也將更新群體的食物最佳位置，而且此信息可以在整個鳥群實時共享。

規(guī)則c選擇警覺行為時，每只鳥嘗試向種群的中心移動，這種行為受種群間競爭的影響，食物儲備多的鳥比儲備少的鳥有更大的概率接近種群中心。

規(guī)則d每只鳥會周期性地飛向新的位置。當(dāng)鳥飛向新的位置時，其身份會在生產(chǎn)者與乞討者之間轉(zhuǎn)換。生產(chǎn)者即為儲備食物最多的鳥，對應(yīng)的儲備食物最少的為乞討者，其余鳥類則在生產(chǎn)者和乞討者之間隨意選擇。

規(guī)則e生產(chǎn)者會主動尋找食物，乞討者則隨意跟隨一個生產(chǎn)者尋找食物。假設(shè)N 只虛擬鳥在t時刻的位置為，在D 維空間內(nèi)飛行和尋找食物。

鳥類的具體行為如下：

（1）覓食行為

規(guī)則a 是一個隨機決定。如果均勻隨機數(shù)rand（0，1）小于常數(shù)P（P∈（0，1）），則鳥會選擇搜尋食物，否則繼續(xù)警惕行為。

規(guī)則b，每只鳥會根據(jù)自身經(jīng)驗和種群經(jīng)驗尋找食物。描述為

式中：rand（0，1）為0 與1 之間的獨立隨機數(shù)；C 和S分別為認(rèn)知系數(shù)、社會加速系數(shù)；pi，j為第i 只鳥更新前的最佳位置；gj為再次更新之前種群的最佳位置。

（2）警覺行為

規(guī)則c，每個鳥不能直接移向種群中心，而是在與其它鳥類的競爭中嘗試移向種群中心。其行為的數(shù)學(xué)描述為

式中：k 為1～N 正整數(shù)，且k≠i；a1，a2為正常數(shù)，且a1，a2∈［0，2］；Fpi為第i只鳥的個體最佳適應(yīng)值；sumF 為群體的最佳適應(yīng)值之和；ε 為計算機可表示的最小常數(shù)，用于避免“0 除”錯誤；meanj為第j 代整個種群的適應(yīng)度平均值。

（3）飛行行為

鳥類會因為逃避天敵、覓食或其他原因而進(jìn)行飛行活動。當(dāng)它們到達(dá)一處新領(lǐng)域，將再次覓食。其中，生產(chǎn)者主動尋找食物，乞討者則跟隨生產(chǎn)者搜尋食物。根據(jù)規(guī)則d，可以明確種群中鳥類個體自己的角色，且生產(chǎn)者和乞討者行為的數(shù)學(xué)描述為

其中

式中：randn（0，1）為標(biāo)準(zhǔn)高斯分布隨機數(shù)；FL為乞討者跟隨生產(chǎn)者覓食的概率。另假設(shè)鳥類定期飛往另一地覓食的周期為Fq。

鳥群算法在初始化時是連續(xù)的。作為解決混合整數(shù)非線性優(yōu)化問題的更好方法，首先要將問題轉(zhuǎn)化為連續(xù)的問題。每個粒子的位置代表一個模式選擇和子信道分配問題的解決方案，構(gòu)成由2×N 個實數(shù)元素組成的向量，每個元素在0 和1 之間。每個信道對應(yīng)向量的2 個元素即哪個用戶采用哪種模式。對于Z 個信道和M 只鳥，第m 只鳥的位置為

在此，信道z 最多有2 種模式的用戶可供選用：在1～Z 之間的用戶為蜂窩模式，在（Z+1）～2Z 之間的用戶為D2D 模式可以表示采用蜂窩模式的占用信道z 的用戶索引； 類似的表示采用D2D 模式的占用信道z 的用戶索引值是離散的，而經(jīng)過BSA算法處理的是連續(xù)的。為了使適應(yīng)于將通過執(zhí)行以下操作離散化：

對于約束（12）和約束（13），在此引入一個懲罰函數(shù)。如果用戶速率比最低要求速率高，則其對提升系統(tǒng)吞吐量有益不懲罰，函數(shù)值為0，反之則懲罰有效。為了能確保剔除不能提升吞吐量的用戶，對函數(shù)值做平方處理。對于約束（14）和約束（15），假設(shè)基站的功率是平均分配給各個子信道的。（在此暫不考慮功率控制）

3.2 算法流程

針對所采用的通信模型，結(jié)合系統(tǒng)性能指標(biāo)，適應(yīng)度函數(shù)F（x）為

式中：σ 為懲罰因子；Rk為用戶速率；ξmin為最低要求速率。

鳥群算法優(yōu)化模型參數(shù)的流程如圖2 所示，具體流程描述如下：

圖2 鳥群算法流程Fig.2 BSA flow chart

步驟1初始化鳥群算法各參數(shù)，每個個體對應(yīng)一組優(yōu)化參數(shù)；

步驟2計算各個體的目標(biāo)適應(yīng)度值，初始篩選非劣解，從中選出最優(yōu)解；

步驟3根據(jù)鳥群算法對應(yīng)的更新策略，對種群進(jìn)行更新；

步驟4計算新種群的適應(yīng)度值，判斷個體的身份形成新的非劣解，與之前的解對比，剔除重復(fù)個體，更新最優(yōu)解；

步驟5判斷是否滿足循環(huán)終止條件，若滿足則輸出最優(yōu)解，否則轉(zhuǎn)至步驟3。

4 仿真試驗及分析

4.1 仿真參數(shù)

為了驗證所提算法的有效性，用MatLab 在LTE支持的單小區(qū)蜂窩系統(tǒng)的場景中進(jìn)行系統(tǒng)仿真?；疚挥谛^(qū)中心，4 個隨機分布的蜂窩用戶和4 對D2D 對，D2D 對之間的距離小于50 m。鳥群算法參數(shù)設(shè)置： 群體大小M 為30 只鳥，迭代數(shù)T 為100次，其他主要參數(shù)設(shè)置見表1。

表1 鳥群算法參數(shù)的設(shè)置Tab.1 BSA setting parameters

4.2 仿真結(jié)果及分析

鳥群優(yōu)化算法的仿真如圖3 所示。設(shè)置最低要求速率為1000 kb/s 后執(zhí)行算法，由圖可見，優(yōu)化過程在迭代100 次的過程中跳出局部最優(yōu)解3 次，最后找到近似的全局最優(yōu)解。它反映了鳥群算法具有良好的全局優(yōu)化能力、處理資源分配和模式選擇問題的能力。

圖3 鳥群算法仿真Fig.3 Bird swarm algorithm optimization simulation

不同速率、 不同方案吞吐量的對比如圖4 所示。圖中對比了資源分配和模式選擇問題的3 種不同解決方案：throughput-PSO 曲線對應(yīng)于文獻(xiàn)[11]完成的解決方案，即標(biāo)準(zhǔn)粒子群算法處理模式選擇和資源分配問題的仿真結(jié)果；throughput-OS 曲線對應(yīng)于文獻(xiàn)[9]實現(xiàn)的解決方案，即粒子群算法處理正交分配資源后的模式選擇問題的仿真結(jié)果。在最小速率為2100 kb/s 之前，該算法優(yōu)于2 種解決方案。在高速率下，優(yōu)化不如其他2 種算法好。然而，由于其在低速率下的顯著優(yōu)勢和跳出局部最優(yōu)的能力，該算法具有更好的應(yīng)用前景。

圖4 不同速率不同方案吞吐量的對比Fig.4 Comparison of throughput of different rates and schemes

5 結(jié)語

聚焦行業(yè)熱點問題，針對D2D 的巨大發(fā)展?jié)摿捌渑c蜂窩網(wǎng)絡(luò)通信在資源分配、通信干擾等方面存在的矛盾，結(jié)合現(xiàn)有文獻(xiàn)中已有的研究基礎(chǔ)，提出綜合考慮資源分配和模式選擇的基于鳥群算法的聯(lián)合算法。新算法可較大程度地緩解D2D通信與蜂窩網(wǎng)絡(luò)的矛盾，并在不影響蜂窩網(wǎng)絡(luò)用戶體驗的前提下，在一定范圍內(nèi)提高頻譜利用率，增加系統(tǒng)吞吐量，降低延遲；通過仿真試驗也印證了BSA 優(yōu)于對比的幾種方案。在此通信模型暫未考慮動態(tài)功率控制，未來的研究方向可以在此基礎(chǔ)之上結(jié)合功率控制對系統(tǒng)進(jìn)行改進(jìn)，提高系統(tǒng)性能。