基於圖論的OFDMA兩層網絡的頻譜分配方法與流程

2023-05-30 17:54:37

本發明公開了基於圖論的OFDMA兩層網絡的頻譜分配方法，屬於無線通信的技術領域。

背景技術：

近年來，室內用戶對網絡的覆蓋範圍和高速率的要求越來越高，同時，這也就促進了家庭基站成為新一門研究熱點。家庭基站以其「即插即用」、小功率和經濟實用的特點，迅速被廣大運營商所追捧。家庭基站主要使用在家庭和辦公場所，以彌補宏基站的衰弱和不足，在網絡上通過DSL(cable/Ethernet/WiMAX)將數據傳輸到運營商網絡中。

但是正因為家庭基站「即插即用」的優點，也給家庭基站網絡拓撲帶來了動態性和不可預測性，因此動態的分配頻譜在家庭基站網絡拓撲上有其必要性。本發明利用圖論對家庭基站的物理模型進行簡化，將家庭基站簡化為模型中的點，將家庭基站間的相互幹擾簡化成模型中點與點之間的邊，將子帶分配問題簡化為著色問題，圖論的應用在實際生活中有其實用操作性。

本發明結合圖論中的團和傳統著色方法，大大提高了點著色的效率和公平性。團內的點兩兩之間有邊，而極大團就是增加任何一項點都會使團不再符合團的定義，也就是說，極大團不能被任何一個更大的團所包含。因此，極大團在資源競爭上是極大衝突區域。本發明對極大的資源衝突區域進行資源分配，每一個極大團都是一個獨立的資源衝突區域，因此每個極大團都可以共享所有資源，大大簡化了複雜度並且提高了資源分配的效率。

本發明是在OFDMA的下行鏈路的場景下運行。OFDMA把可用頻帶分成一系列正交的子信道，每個子信道上使用一個子載波進行調製，並且各個子載波並行傳輸。OFDMA系統有著優越的性能，其優點主要在於頻譜利用率較高。OFDMA系統中，子載波是相互正交的，之間沒有保護間隔且頻譜重疊，因此可以節省頻譜資源，提高頻帶的利用率，也就是提高系統的吞吐量。

在兩層網絡模型中，頻譜資源的分配模式分為宏基站和家庭基站不共用頻譜、部分共用和共用頻譜三類。在頻譜資源越來越稀缺的今天，完全不共用頻譜是不現實和不經濟的。在本發明中，宏基站和家庭基站是共享頻譜資源的，因此宏基站用戶和家 庭基站用戶同時需要面臨兩個幹擾：跨層幹擾和同層幹擾。在宏基站和家庭基站共享頻譜資源的同時，如何提高家庭基站的平均吞吐量和系統的吞吐量，與此同時還需降低方法的複雜度。因此，本發明優先保證宏用戶的服務質量，在此基礎上，考慮宏基站和其他家庭基站對家庭用戶的幹擾，基於圖論來分配所有頻譜，並在保證用戶公平性的基礎上，大大提高系統吞吐量。

技術實現要素：

技術問題：本發明針對傳統圖論中根據度來分配資源精確度和效率低下、資源利用不充分的不足，提供一種性能優越、複雜度低的基於圖論的兩層OFDMA網絡的頻譜分配方法。

技術方案：1.基於圖論的OFDMA兩層網絡的頻譜分配方法，該方法包括以下步驟：

1)建模：獲取瞬時信道信息，基於圖論建模G＝(V,E)。基於圖論建立家庭基站的模型G＝(V,E)，V為圖論中的點，代表家庭基站用戶節點；E為圖論中的邊，代表用戶之間的幹擾。家庭基站的用戶FUEi收集本家庭基站的信道瞬時信息，包括家庭基站Fi到FUEi的發射功率Pf以及瞬時信道增益gi,i，其他所有家庭基站F的信道瞬時信息，其中包括其他家庭基站F到家庭基站用戶節點FUEi的信道的發射功率Pf以及瞬時信道增益gj,i，其中j∈F，系統中的加性高斯白噪聲N0，求得目的節點FUEi的瞬時的信乾燥比為使家庭基站用戶FUEi滿足SINRi＞SINtRh，(SINRth為信乾燥比的下限，通常為一個給定的常數。)將對FUEi造成最大幹擾的家庭基站加入集合Ii，並使得Ii中的家庭基站與FUEi之間的邊的值為1，即直至滿足條件。

2)初始化：子帶總數為R，所有用戶的已被分配子帶的集合為M。

3)加邊：得到弦圖G'＝(V,E')。求弦圖，即將圖三角化，在模型G＝(V,E)的基礎上加邊得到：G'＝(V,E∪F)，其中F就是所加的邊。根據定理：uv是弦圖中的邊， 若且唯若uv∈E或者原圖G中存在有路徑u,x1,x2,…,xk,v使得α(xi)＜min{α(u),α(v)}，1≤i≤k，求得F，繼而得到弦圖G'＝(V,E∪F)＝(V,E')。

4)通過最大勢方法(MCS)，在弦圖G'＝(V,E')的基礎上，求得弦圖內所有極大團的集合為K。

5)根據公式公式公式以及公式 求得每個極大團的權重wK和每個點的團度(pv,qv)，其中代表vk到v的信道增益，代表vk對v的幹擾，Iv代表點v所受的最大幹擾。

6)更新：每個極大團的可以分配的子帶的集合為N＝R∩M。

7)若K為空，此次分配結束；否則，根據每個極大團的權重wK，優先選出權重最小的極大團k內的點進行優先分配，若同時存在有多個極大團的權重相同，優先選擇已被分配子帶數目最少的極大團k。

8)賦值：i＝1。每次給選出的極大團k內點分配子帶時，令i＝1，在k的可著的顏色集Nk裡遍歷分配子帶，其中Nk是第k個極大團裡的可分配信道集。

9)若i＞|Nk|，則轉步驟10)；否則，根據團度(pv,qv)對極大團k內的所有的點進行排序，優先選擇團度最小的點v進行排序，若有多個點團度最小，則選擇已被分配子帶數目最少的點v，並將Nk(i)分配的分配給選出的v，其中|Nk|是第k個極大團裡的可分配信道集的個數，Nk(i)是第k個極大團裡的可分配子帶集裡的第i個子帶。接著：i＝i+1。重複步驟9)。

10)更新：令k中所有的點為集合A，k中點的相鄰點為集合B，則A和B內各點之間邊為零，即Ev∈A,v∈B＝0,Ev∈B,v∈A＝0。並令團k中所有的點已被分配的顏色為集合Mk，則已分配的子帶的集合為M＝M∪Mk。轉步驟3)。

有益效果

本發明與現有技術相比，具有以下優點：

1.資源分配方面，本發明提供了基於圖論的兩層OFDMA網絡的頻譜分配方法，該方法在對傳統圖論中度和團的深入理解上，在分配子載波時，通過團度提高精準度，能夠獲得更好的系統容量性能。

2.公平性方面，在資源分配時，雖然為了使系統容量達到最大，優先給幹擾小的分配，但是本發明中當有多個幹擾小的選擇時，優先選擇已被分配子載波少的，這樣能保證並提高用戶的公平性。

3.方法複雜度方面，原本的基於圖論的建立的模型是一個NP-hard模型，為了簡化系統模型以獲得複雜度低的資源分配方法，通過本發明提供的團度的計算和分配方法，本發明首先將圖變成弦圖，再通過MCS方法求出所有極大團，利用極大團的概念進行優化分配，大大降低了資源分配的複雜度。

附圖說明

圖1為本發明方法的兩層家庭基站網絡的結構示意圖。

圖2為本發明方法的整體流程邏輯框圖。

具體實施方式

下面結合實施例和說明書附圖來對本發明作進一步的說明：

一、兩層OFDMA家庭基站網絡系統模型

在本發明中，本發明考慮下行OFDMA系統兩層家庭基站網絡系統模型，如附圖1所示。在此模型中，宏基站和家庭基站共享頻譜。宏基站位於本小區中心，其覆蓋範圍為：Rm，每個宏小區內隨機分布M個宏用戶和N個家庭基站。在家庭小區內部，一個家庭基站服務於一個家庭用戶，家庭基站覆蓋範圍為：Rf。家庭基站和宏基站的發射功率分別固定為Pm和Pf，並且Pm＞Pf。子載波集合為C＝{1,2,…,C}，子載波的個數為C。資源分配矩陣為A＝[ac,n]，矩陣的大小為C*(N+M)，當ac,n＝1時，子載波c分配給用戶n；否則，ac,n＝0。

在附圖1中，家庭基站的集合為：F＝{F1,F2,…Fi,…,FN}，一個家庭基站服務於一個家庭用戶，因此家庭用戶可以和家庭基站用一樣的下標來表示，家庭用戶的集合 為：FUE＝{FUE1,FUE2,…FUEi,…,FUEN}，宏用戶的集合為MUE＝{MUE1,MUE2,…MUEl,…,MUEM}。

為了避免宏用戶和家庭用戶之間的跨層幹擾，本發明首先給每個宏用戶分配一個子載波。當子帶數目大於宏用戶的個數時，每個宏用戶可能被分配多個子載波。本發明首先保證宏用戶的服務質量，即信乾燥比。

宏用戶MUEl在子載波c上的信乾燥比為：

其中gM,l和gi,l分別是家庭基站M和Fi到宏用戶MUEl的信道增益，N0是加性高斯白噪聲。

家庭基站Fi的家庭用戶FUEi在子載波c上的信乾燥比為

其中gi,i和gj,i分別是家庭基站Fi和Fj到家庭用戶FUEi的信道增益，gM,i是宏基站M到家庭用戶FUEi的信道增益。

在求取系統吞吐量的時候，利用衰減和截短的香農界來求得家庭用戶FUEi在子信道c上的頻譜利用率[bps/Hz]：

其中α是損耗因子，SINRmin和SINRmax分別為最小和最大的SINR，Cmin和Cmax分別為用戶FUE的最小和最大的頻譜效率。用戶FUEi的總吞吐量Ci是所有分配給它的子信道上的吞吐量之和。

其中，Bc為信道c的帶寬。

二、基於圖論的兩層OFDMA網絡頻譜分配方法

本發明基於圖論建立幹擾圖模型G＝(V,E)，簡化了實際物理場景中的幹擾問題，降低了複雜度。其中V是家庭基站節點，E是連接這些家庭基站節點的邊。本發明針對OFDMA下行鏈路的場景，因此相鄰點會被分配以正交子載波，同時存在於相鄰點之間的幹擾會被消除。在幹擾圖裡，加邊，成了消除幹擾的其中一種方式。若eu,v∈E，eu,v＝1則代表u和v之間沒有幹擾；否則，有幹擾。

家庭基站Fi的家庭用戶FUEi的信乾燥比為

SINRi＞SINRF,th (6)

其中，SINRi,c根據公式(1)獲得。本發明為了保證家庭基站的服務質量，給出家庭基站的信乾燥比下限SINRF,th。如果不滿足公式(6)，將對家庭用戶FUEi構成最大幹擾的家庭基站Fs放在集合Seti裡，並使得ei,s∈E,ei,s＝1，同時es,i∈E,es,i＝1，重複這個步驟，直到家庭用戶FUEi的信乾燥比SINRi＞SINRF,th。

本發明基於圖論中的極大團來分配頻譜，已被證明，存在有一個多項式方法枚舉出所有的極大團，因此只有先將圖加邊變為弦圖，即G'＝(V,E∪F)＝(V,E')，其中，F為所加的邊。圖論中的弦圖定義為：一個無向圖中任意長度大於3的環都至少要有一個弦，弦又定義為連接環中不相鄰的兩個點的邊。實現G'＝(V,E∪F)＝(V,E')：根據定理：uv是弦圖中的邊，若且唯若uv∈E或者原圖G中存在有路徑u,x1,x2,...,xk,v使得α(xi)＜min{α(u),α(v)}，1≤i≤k，求得F，繼而得到弦圖G'＝(V,E∪F)＝(V,E')。其中，一個無向圖是弦圖若且唯若該無向圖有一個完美消除序列，完美消除序列定義為：一個點的序列(每個點出現且恰好出現一次)v1,v2,...,vn滿足vi在{vi,vi+1,…,vn}的誘導子圖中為一個單純點。誘導子圖： 單純點定義為：當此點與它的鄰接點構成的誘導子圖為一個團，團中的點兩兩相連。

具體求得弦圖如下：已知G＝(V,E)，且V中有n個點。

步驟1：初始化，並使得所有的V中的點的權重為零。

步驟2：依次從第n個到第1個進行循環操作：

步驟2-1：選擇一個未被編號的最大權重w(v)，

步驟2-2：依次對所有未被編號的u∈V進行循環操作：

步驟2-2-1：如果有邊uv或者路徑u,x1,x2,...,xk,v使得w(xi)＜w(u)，1≤i≤k。

步驟2-2-2：S＝S∪{u}。

步驟2-3：對於所有的點u∈S，使得w(u)＝w(u)+1，如果使F＝F∪{uv}。

步驟2-4：α(v)＝i。

最終得到F，弦圖G'＝(V,E∪F)＝(V,E')。

本發明在求得弦圖之後，根據已證定理，通過最大勢(MCS)和團樹的方法枚舉出所有的極大團。具體枚舉過程如下：

步驟1：初始化：

步驟2：依次讓i從第n個到第1個進行循環操作：

步驟2-1：選擇一個使得|adj(v)∩Li+1|最大的v:v∈V-Li+1。

步驟2-2：αv←i，v←vi，new_card←|adj(v)∩Li+1|

步驟2-3：如果new_card≤prev_card(開始一個新的極大團)：

步驟2-3-1：s←s+1，Ks←adj(vi)∩Li+1

步驟2-3-2：如果new_card≠0

步驟2-3-2-1：k←min{j|vj∈Ks}，p←clique(vk)，εT←εT∪{Ks,Kp}

步驟2-4：clique(vi)←s，Ks←Ks∪{vi}，Li←Li+1∪{vi}，prev_card←new_card

最終得到所有弦圖Ks。其中adj(v)為點v的鄰點的集合。

本發明根據所枚舉出的所有的極大團，通過公式公式 公式以及公式求得每個極大團的權重wK和每個點的團度(pv,qv)，其中和分別是家庭基站vk到用戶v的發射功率和信道增益。

本發明針對極大團進行研究，極大團的定義為：增加任何一點都不能再構成團，即極大團不是任何團的子集。極大團作為一個極大的資源競爭區域，在極大團內部的點，可以共享所有的資源。將極大團單獨枚舉出來，再對資源進行分配，不僅能降低本發明提出方法的複雜度，也能對該方法的資源利用效率得到有效的提高。

本發明首先對權重小的極大團進行資源分配，若同時存在有多個極大團的權重相同，優先選擇已被分配子帶數目最少的極大團。選擇最小權重，目的在於最大化系統的吞吐量，而若有多個最小選擇已被分配子帶數目最小的，目的在於對公平性的考慮。

在選定極大團之後，再對極大團之中的點進行資源分配先後順序的選擇，按照團度的大小，首先對團度最小的點進行資源分配，若同時存在有多個團度最小的，優先選擇已被分配子帶數目最少的點。選擇最小團度，目的在於最大化系統的吞吐量，而若有多個最小選擇已被分配子帶數目最小的，目的在於對公平性的考慮。

則本發明提出的基於圖論的OFDMA二層網絡頻譜分配方法可以歸納為：

1)建模：根據公式(6)，基於圖論建模G＝(V,E)。

2)初始化：子帶總數為R，所有用戶的已被分配子帶的集合為M。

3)加邊：得到弦圖G'＝(V,E')。求弦圖，即將圖三角化，在模型G＝(V,E)的基礎上加邊得到：G'＝(V,E∪F)，其中F就是所加的邊。根據定理：uv是弦圖中的邊，若且唯若uv∈E或者原圖G中存在有路徑u,x1,x2,…,xk,v使得α(xi)＜min{α(u),α(v)}，1≤i≤k，求得F，繼而得到弦圖G'＝(V,E∪F)＝(V,E')。

4)通過最大勢方法(MCS)，在弦圖G'＝(V,E')的基礎上，求得弦圖內所有極大 團的集合為K。

5)根據公式(7-10)，求得每個極大團的權重wK和每個點的團度(pv,qv)。

6)更新：每個極大團的可以分配的子帶的集合為N＝R∩M。

7)若K為空，此次分配結束；否則，根據每個極大團的權重wK，優先選出權重最小的極大團k內的點進行優先分配，若同時存在有多個極大團的權重相同，優先選擇已被分配子帶數目最少的極大團k。

8)賦值：i＝1。每次給選出的極大團k內點分配子帶時，令i＝1，在k的可著的顏色集Nk裡遍歷分配子帶，其中Nk是第k個極大團裡的可分配信道集。

9)若i＞|Nk|，則轉步驟10)；否則，根據團度(pv,qv)對極大團k內的所有的點進行排序，優先選擇團度最小的點v進行排序，若有多個點團度最小，則選擇已被分配子帶數目最少的點v，並將Nk(i)分配的分配給選出的v，其中|Nk|是第k個極大團裡的可分配信道集的個數，Nk(i)是第k個極大團裡的可分配子帶集裡的第i個子帶。接著：i＝i+1。重複步驟9)。

10)更新：令k中所有的點為集合A，k中點的相鄰點為集合B，則A和B內各點之間邊為零，即Ev∈A,v∈B＝0,Ev∈B,v∈A＝0。並令團k中s所有的點已被分配的顏色為集合Mk，則已分配的子帶的集合為M＝M∪Mk。轉步驟3)。