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

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

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

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

1 國內外研究現狀

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

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

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

2 系統模型

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

圖1 系統模型Fig.1 System model

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

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

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

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

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

則小區總的吞吐量C 為

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

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

吞吐量為

D2D 用戶的SINR 為

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

吞吐量為

此時，小區總吞吐量為

該系統的優化目標是在保證蜂窩用戶和D2D用戶的服務質量的前提下最大化吞吐量，最小化各用戶之間的干擾，則在此采用的約束條件為

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

3 鳥群算法

3.1 基本原理

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

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

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

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

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

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

鳥類的具體行為如下：

（1）覓食行為

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

規則b，每只鳥會根據自身經驗和種群經驗尋找食物。描述為

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

（2）警覺行為

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

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

（3）飛行行為

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

其中

式中：randn（0，1）為標準高斯分布隨機數；FL為乞討者跟隨生產者覓食的概率。另假設鳥類定期飛往另一地覓食的周期為Fq。

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

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

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

3.2 算法流程

針對所采用的通信模型，結合系統性能指標，適應度函數F（x）為

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

鳥群算法優化模型參數的流程如圖2 所示，具體流程描述如下：

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

步驟1初始化鳥群算法各參數，每個個體對應一組優化參數；

步驟2計算各個體的目標適應度值，初始篩選非劣解，從中選出最優解；

步驟3根據鳥群算法對應的更新策略，對種群進行更新；

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

步驟5判斷是否滿足循環終止條件，若滿足則輸出最優解，否則轉至步驟3。

4 仿真試驗及分析

4.1 仿真參數

為了驗證所提算法的有效性，用MatLab 在LTE支持的單小區蜂窩系統的場景中進行系統仿真。基站位于小區中心，4 個隨機分布的蜂窩用戶和4 對D2D 對，D2D 對之間的距離小于50 m。鳥群算法參數設置： 群體大小M 為30 只鳥，迭代數T 為100次，其他主要參數設置見表1。

表1 鳥群算法參數的設置Tab.1 BSA setting parameters

4.2 仿真結果及分析

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

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

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

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

5 結語

聚焦行業熱點問題，針對D2D 的巨大發展潛力及其與蜂窩網絡通信在資源分配、通信干擾等方面存在的矛盾，結合現有文獻中已有的研究基礎，提出綜合考慮資源分配和模式選擇的基于鳥群算法的聯合算法。新算法可較大程度地緩解D2D通信與蜂窩網絡的矛盾，并在不影響蜂窩網絡用戶體驗的前提下，在一定范圍內提高頻譜利用率，增加系統吞吐量，降低延遲；通過仿真試驗也印證了BSA 優于對比的幾種方案。在此通信模型暫未考慮動態功率控制，未來的研究方向可以在此基礎之上結合功率控制對系統進行改進，提高系統性能。