基于超圖著色的D2D網絡資源分配算法

陳雨潔，馬彩虹

(武警工程大學 信息工程學院，陜西 西安 710086)

0 引 言

基于蜂窩網絡的D2D通信被認為是5G系統中一種極具潛力的新型網絡架構。通過允許兩個相鄰用戶設備共享蜂窩用戶設備的頻譜資源直接進行通信，D2D通信能有效提高蜂窩網絡的頻譜利用率[1]。但如果通信資源分配不當，來自多方鏈路的干擾會使D2D通信帶來的系統性能提升大打折扣，故合理的資源分配是D2D通信發揮優勢的基礎。文獻[2-4]分別以系統吞吐量、能耗與中斷概率、系統容量為改善指標，通過引入博弈論和模擬退火算法等思想，提出了有效的資源分配方案。

上述文獻均是對LTE(long term evolution)系統中的正交頻譜分配進行研究，但頻率資源的有限性仍限制了系統容量和頻譜利用率的進一步提升，故基于SCMA等非正交多址技術的D2D通信受到了廣泛關注。文獻[5]提出一種基于沖突圖的資源分配方案，驗證了結合SCMA的D2D通信相比LTE網絡在系統和速率上可獲得更大增益。文獻[6,7]分別從碼本的優化分配、碼本和功率聯合優化分配兩個角度出發，給出了兩種較好的資源分配方案。本文針對SCMA系統中的多小區網絡場景，提出一種改進的超圖著色算法完成D2D用戶碼本分配。考慮到傳統超圖著色法在多小區模型中構建超圖的計算過于復雜，提出基于通信距離建立D2D用戶的蜂窩復用備選集，并以此建立超圖和進行著色。仿真結果表明所提算法能有效提升系統容量，且相比傳統超圖著色法復雜度更低。

1 系統模型

為縮小算法規模、降低系統復雜度，對本文研究的多小區場景進行預處理。首先根據鄰接關系將系統中的小區劃分為不同小區簇，簇內用戶通過SCMA碼本共享預分配的正交頻譜。不同簇內的蜂窩用戶使用相同資源，以此保證使用相同資源的用戶間距離足夠大，從而相比簇內相距較近的D2D鏈路干擾，簇間的蜂窩同頻干擾可忽略不計。于是多小區異構網絡中的資源分配問題轉化到各小區簇內進行，由此控制了算法的規模。本文研究均基于該假設，所關注的多小區異構網絡由一個小區簇內的多個相鄰小區構成，且簇內所有蜂窩用戶已完成資源分配，本文旨在對簇內D2D用戶進行碼本分配。

1.1 網絡場景

考慮在SCMA系統中，一個蜂窩與D2D異構的多小區上行網絡場景。

圖1 系統模型

設信道為瑞利衰落模型，則各鏈路的增益可表示為

(1)

于是占用SCMA層k的蜂窩用戶Un接收信號的信干噪比(SINR)為

(2)

復用k層SCMA碼本資源的D2D對Dm接收信號的信干噪比(SINR)為

(3)

其中，Ck表示復用同一碼本的蜂窩用戶和D2D對的集合。

1.2 問題建模

為使系統吞吐量最大，要將網絡中的蜂窩用戶及D2D對合理的分配到各SCMA層。假設一個蜂窩用戶或一個D2D對只占用一層SCMA資源，一個SCMA層最多可分配給一個蜂窩用戶，則資源分配矩陣可表示為

(4)

式中： AN×K=[αn,k] (1≤n≤N，1≤k≤K) 表示蜂窩用戶的碼本分配矩陣，當SCMA層k分配給蜂窩用戶Un時αn,k=1， 否則αn,k=0； BM×K=[βm,k] (1≤m≤M，1≤k≤K) 表示D2D對的碼本分配矩陣，當SCMA層k分配給D2D對Dm時βm,k=1， 否則βm,k=0。

由此可得目標函數及限制條件為

(5)

式中：C1和C2限制了最低用戶速率，即保證系統內所有用戶均能正常通信，C3和C4限制了碼本最多分配給一個蜂窩用戶，每個蜂窩用戶或D2D對最多占用一個碼本資源。

從目標函數可以看出，系統吞吐量提升的關鍵在于優化信道分配變量，又注意到上述資源分配問題是具有非線性約束的NP-hard優化問題，而圖著色是解決此類資源分配問題的近似且有效的方法。因此考慮將SCMA碼本資源建模為K種不同顏色，N個蜂窩用戶建模為N個(蜂窩)頂點，M個D2D對建模為平面中的M個(D2D)頂點，從而將信道分配問題被轉化為具有固定顏色的頂點著色問題加以解決。

2 基于超圖著色的資源分配算法

在多小區系統模型中，由于允許多用戶復用同一SCMA碼本，大部分通信用戶會受到來自其它用戶的干擾，包括兩個用戶間的成對干擾和多用戶間的累積干擾。為了提升用戶通信質量，更好地描述和控制鏈路間的復雜干擾，提出建立超圖并利用圖著色法進行碼本分配。

2.1 超圖模型

假定網絡中的N個蜂窩用戶已完成碼本分配，接下來只需進行D2D對的碼本分配，因此超圖建立過程中只需考慮D2D接收端受到的干擾。設X={x1,…,xM+N} 為超圖H中的所有頂點元素(即所有蜂窩用戶和D2D對)，則H={e1,…,eL}, 其中e1,…,eL為X中頂點所構成干擾邊的集合。具體的，對D2D用戶對Dm，干擾邊建立原則為

于是滿足式(6)的蜂窩用戶Un和滿足式(7)的D2D對Di與D2D對Dm構成2超邊(包含兩個頂點的超邊)，滿足式(8)的多個D2D對或滿足式(9)蜂窩用戶Un、D2D對Di與D2D對Dm構成3超邊(包含3個頂點的超邊)，某一頂點所在干擾邊的數量稱為該頂點的干擾度[10]。圖2為超圖模型示例。

圖2 超圖模型

利用關聯矩陣可以方便表示超圖中的干擾情況，圖2中超圖的關聯矩陣I為

其中，行數表示頂點數，列數表示超邊數。超邊e1中包含4、5、6這3個頂點，對應矩陣中元素(4，1)、(5，1)、(6，1)為1，且由圖2可知3個頂點的干擾度分別為3、2、2。

完成超圖構建后即可通過圖著色進行碼本資源分配。在著色過程中將K個SCMA碼本看作K種不同顏色，由于蜂窩用戶已經完成了資源分配，即蜂窩頂點已著色只需對D2D頂點著色。于是依據構建的超圖中，同一超邊所包含頂點不能著相同顏色的原則，按照干擾度從大到小的順序依次為D2D頂點著色，直到所有頂點著色完畢或沒有可用的顏色為止，顏色相同的頂點即為復用同一碼本的用戶。

2.2 蜂窩復用備選集構建

超圖著色算法主要包括超圖構建和超圖著色兩個步驟，但由于本文考慮的是多小區場景，直接構建超圖所涉及鏈路多，計算量大，算法復雜度過高，因此通過為D2D對建立基于距離的蜂窩復用候選集，在保證D2D用戶通信質量的同時集簡化超圖結構，降低算法復雜度。

考慮蜂窩用戶對復用其碼本的D2D對的干擾，要使D2D對Di能正常通信，其信干比應滿足

SINRDi≥η0

(10)

式中：η0為D2D用戶接收信號的信干比門限。

于是根據式(1)可推導出

(11)

由于信道增益是一個隨機過程，對式(11)兩邊同時求期望可得

(12)

(13)

于是滿足式(13)的蜂窩用戶可作為Di的復用備選對象。構建復用備選集的具體過程如算法1所示。

算法1：復用備選集建立算法

輸入：UN，DM(UN為蜂窩用戶集合，DM為D2D對集合)

輸出：M個蜂窩復用備選集{OM}

(1)n=1(n為當前判斷的蜂窩用戶)

(2)m=1(m為需要建立蜂窩復用備選集的D2D對序號)

(3)Om=?(Om為第m個D2D對的蜂窩復用備選集)

(4)對第n個蜂窩用戶Un和第m個D2D對Dm， 判斷是否滿足式 (13) 條件

(5)如果 滿足

Om=Om∪Un

否則

n=n+1

(6)如果 n≤N

轉向執行 (4)

否則

轉向執行 (7)

(7)m=m+1

(8)如果 m≤M

轉向執行 (4)

否則

轉向執行 (9)

(9)結束

2.3 超圖構建

根據網絡中通信鏈路間的干擾關系可建立一個描述各類干擾的超圖，由于本文算法只考慮D2D對的碼本分配，故構建超圖時只考慮D2D用戶所受干擾。

對D2D用戶來說干擾對象包括兩類，復用碼本對應的蜂窩用戶和共享同一碼本的其它D2D用戶。由于復用備選集限制了D2D用戶的復用對象，因此只需考慮備選集中蜂窩用戶及備選集中包含相同蜂窩用戶的D2D對造成的干擾。基于上述干擾對象，D2D用戶所受干擾的類型又分兩種，二個用戶間的成對干擾和多用戶間的累積干擾，對復用備選集中的蜂窩用戶，D2D用戶與其可能存在成對干擾；對復用備選集中的蜂窩用戶和備選集中包含相同蜂窩用戶的D2D對，D2D用戶與其可能構成累積干擾。為了便于判斷干擾的建立，構造一個描述復用關系的集合 {Sn}(n=1,2,…,N)， Sn={Un,Dm,…,Di} (Un為蜂窩用戶， Dm,…,Di為備選集中包括Un的D2D對的集合)。超圖構建的具體過程如算法2所示。

算法2：超圖構建算法

輸入：DM，{SN}，{OM}(DM為D2D對集合，{SN}為描述復用關系的集合，{OM}為蜂窩復用備選集)

輸出：超圖關聯矩陣I

(1)m=1(m為當前考慮干擾邊建立的D2D對序號)

(2)n=1(n為當前判斷復用關系集合中干擾的序號)

(3)如果 Om∩Sn=?

轉向執行 (4)

否則

轉向執行 (8)

(4)對Sn中的蜂窩用戶Un或D2D對Di， 根據式 (6) 或式 (7) 判斷其對Dm的干擾是否滿足干擾邊建立條件

(5)如果 滿足

Dm分別與Un或Di構成2超邊

否則

轉向執行 (6)

(6)對Sn中的蜂窩用戶Un、 D2D對Di或D2D對Di、 Dj， 根據式 (8) 或式 (9) 判斷其對Dm的干擾是否滿足干擾邊建立條件

(7)如果 滿足

Dm分別與Un、 Di或Di、 Dj構成3超邊

否則 轉向執行(8)

(8)n=n+1

(9)如果 n≤N

轉向執行 (3)

否則 轉向執行 (10)

(10)m=m+1

(11)如果 m≤M

轉向執行 (3)

否則 轉向執行 (12)

(12)結束

2.4 超圖著色算法

由于蜂窩用戶已完成碼本分配，故蜂窩頂點已著色。根據超圖計算所有D2D頂點的干擾度，并按照由大到小的順序依次為其著色(同一超邊所連接的頂點不能著相同顏色)，直到所有頂點著色完畢，具體過程如算法3所示。

算法3：超圖著色算法

輸入：UN，DM，{OM}，I(UN為蜂窩用戶集合，DM為D2D對集合，{OM}為蜂窩復用備選集，I為超圖關聯矩陣)

輸出：D2D對碼本分配方案

(1)根據關聯矩陣求出所有D2D頂點的干擾度

(2)m=1(m為當前進行著色的D2D對序號)

(3)選擇所有D2D對DM中具有最小干擾度的Dm

(4)根據關聯矩陣I， 判斷Dm對應Om中的蜂窩用戶Un與Dm所屬超邊中的其它D2D對是否著相同顏色

(5)如果 是

將Un從Om中刪除

否則 給Dm著Un相同顏色

(6)判斷Om是否為空集

(7)如果 是

Dm保持靜默并將其從DM中刪除，轉向執行 (8)

否則 對Om中的下一個蜂窩用戶執行 (4)

(8)判斷DM是否為空集

(9)如果 是

轉向執行 (10)

否則 轉向執行 (3)

(10)結束

3 仿真分析

3.1 仿真參數

針對多小區蜂窩上行鏈路設置仿真參數見表1。

表1 仿真參數

3.2 仿真結果

圖3為一次仿真中的用戶分布，在坐標軸上建立了一個包括3個蜂窩小區、30個蜂窩用戶和45個D2D對的網絡場景。基站位于各小區中心，蜂窩及D2D對在小區中隨機分布，系統內用戶通過36個正交的SCMA碼本復用9個正交的時頻資源。

圖3 仿真場景示例

接下來將本文算法分別與傳統超圖著色法[11]、隨機選擇算法和圖著色法[12]進行對比。為了更好地體現D2D用戶接入數的變化，后續仿真結果中橫坐標均設置為D2D對與蜂窩用戶數量之比，蜂窩用戶數為30。

圖4 干擾邊判斷次數對比

其次比較了4種算法下D2D用戶的接入數。如圖5所示，隨著網絡中D2D對的增加，4種算法下D2D鏈路數均有增加，且從斜率變化可以看出，本文算法對系統容量的提升最為明顯。同時，起初幾條曲線間差距較小，但隨著用戶的進一步密集化，本文算法的D2D鏈路建立優勢逐漸顯現，這是由于多小區覆蓋的用戶可選擇多個小區中的碼本資源進行復用，解決了小區邊緣用戶因距離遠、受干擾嚴重導致無法建立D2D鏈路的問題，從而有效提升了系統容量。

圖5 系統容量對比

最后比較了4種算法下信道吞吐量的累積分布函數和系統和速率如圖6、圖7所示。當D2D對數量為60時，由圖6可知本文算法下約88%的信道吞吐量達到4×106bit/s以上，而隨機選擇算法、圖著色法和傳統超圖著色法分別只有84%、72%和61%，可見本文算法在一定程度上提升了信道吞吐量。由圖7則可以看出，本文算法提升系統和速率的性能明顯優于其它3種算法，同樣隨著D2D對數量的增加差距逐漸拉大。這是因為在用戶密集分布的場景中，本文算法不僅能保證用戶通信質量還能擴大系統容量，故而有效提升了系統吞吐量，且不同于其它3條曲線趨于收斂的走勢，本文算法對系統和速率的增益還有一定上升空間，也充分說明了本文算法在多小區、多用戶的場景中具備良好的性能。

圖6 信道吞吐量累計分布函數對比

圖7 系統和速率對比

4 結束語

在SCMA系統中，由于蜂窩用戶和多個D2D對共享相同碼本資源，故用戶間存在嚴重干擾，本文要解決的就是通過合理的SCMA碼本分配，在控制干擾的同時有效提升系統容量的問題。為了更好建模蜂窩與D2D異構網絡，達到全局最優，在多小區蜂窩上行鏈路的場景中建立系統模型和目標函數，而后針對直接利用超圖著色算法會導致的超圖復雜度高、著色過程計算量大等問題，提出建立蜂窩復用候選集簡化超圖構建過程，從而在控制D2D用戶所受干擾的同時簡化了算法，提升了系統容量和通信和速率。最后通過仿真驗證了本文算法的有效性。