基于遺傳算法的混疊式非正交多址接入方法

閆珍珍,李 波,楊 懋,閆中江

(西北工業大學電子信息學院,陜西 西安 710072)

0 引 言

隨著人們對網絡需求的爆炸式增長,現有的寬帶網絡越來越無法滿足超密集的無線連接和超大規模的網絡容量需求[1]。由于傳統的正交多址接入技術很難滿足上述需求,因此引入了非正交多址接入(non-orthogonal multiple access,NOMA)方法[2-5]。通過多種在不同維度上的多路復用方式,目前已經提出了眾多NOMA方案,其中稀疏碼多址接入(sparse code multiple access,SCMA)方法[6-9]是其代表性技術之一,也是下一代寬帶網絡中極具競爭力的NOMA方法之一。

在傳統的多址接入方法中,基站(base station,BS)作為上下行傳輸的調度中心,不可避免地伴隨著較多的接入時延和較高的信令開銷。作為一種行之有效的解決方案,SCMA支持調度接入和隨機競爭接入兩種接入模式。兩種接入模式適用場景不盡相同。其中,調度接入適用于業務需求穩定或者業務量大的用戶,而隨機競爭接入適用于業務臨時到達且對于延時較為敏感或者業務量較小的業務需求[10]。然而已有研究中,分配給調度接入和隨機競爭接入兩種訪問模式的資源(例如信道或者時頻資源塊)是嚴格分離的,這種資源的嚴格分離難以適配業務的動態變化。例如,在業務量較大的需求占主導的時段,調度接入的資源不夠而隨機競爭接入的資源浪費。在臨時到達的業務占主導的時段,調度接入的資源產生了浪費而隨機競爭的資源出現了嚴重的沖突。因此,現有研究降低了系統的資源利用率和吞吐量。

作為寬帶網絡中非常有前途的關鍵技術之一,SCMA引起了世界上眾多專家和學者的極大興趣。研究者們做了大量的研究工作,并從中提出了許多關于SCMA的資源分配方法[11-15]。其中,一部分研究使用隨機資源分配方法,一部分研究只優化了分配給調度用戶的資源,極少有研究對全部用戶的資源分配進行優化或者對分配給競爭用戶的資源進行優化。更嚴重的是,在絕大多數的研究中,分配給調度用戶和競爭用戶兩者的資源是嚴格分離的。由于調度用戶的個數和競爭用戶的個數是不斷變化的,這將導致非常嚴重的資源浪費。為了提高資源利用率,需要提出一種新的解決方法,該方法可以允許調度用戶和競爭用戶兩者共享相同的資源單元。

為了解決上述問題,實現調度用戶和競爭用戶兩者的資源共享,并且同時滿足不斷增長的超密集無線連接和超大規模網絡容量需求,本文提出一種基于遺傳算法的混疊式NOMA方法,允許相同的資源單元混疊地同時承載調度接入和隨機競爭接入業務,從而實現兩種接入方式的細粒度融合。進一步,針對混疊式NOMA方法中如何高效地進行資源分配的問題,設計了基于遺傳算法的混疊式NOMA資源分配算法。將調度接入和隨機競爭接入的總容量作為優化目標以及遺傳算法的適配度,建立了最優化問題,并通過交叉和變異操作的多次迭代來優化資源分配效果。仿真實驗表明，與3種對比方案相比較,本文提出的混疊式NOMA方法及其遺傳算法在各個場景下均可以獲得更好的吞吐量性能。

1 系統模型

1.1 網絡場景

假設BS位于寬帶網絡社區的中心,調度用戶和隨機競爭用戶隨機地分布在BS四周,如圖1所示。由BS作為調度中心進行資源分配的用戶稱為調度用戶,用U={u1,u2,…,uNg}表示,其中,Ng表示調度用戶個數;沒有調度中心,隨機競爭接入資源的用戶稱為競爭用戶,用V={v1,v2,…,vNgf}表示,其中,Ngf表示競爭用戶個數。

圖1 網絡場景Fig.1 Network scene

把頻域分為J個子信道,并且每相鄰K個子信道組成一個資源塊。這樣,可以得到n個資源塊,即

(1)

對于下行鏈路而言,所有的信息由BS進行調度。對于上行鏈路而言,用戶不僅可以由BS進行調度,也可以通過隨機競爭的方式接入資源[16-17]。換而言之,只有上行鏈路包含調度接入和隨機競爭接入兩種訪問模式。因此,本文主要考慮上行鏈路的信息傳輸。

1.2 SCMA

在發送端,用戶信息以比特流的形式通過SCMA編碼器直接映射為多維復數域碼字,之后,不同用戶的碼字通過稀疏碼擴頻的方式在各個子信道上非正交疊加[18-21]。同時,為了降低接收端解碼的復雜度,每個碼字的非零元素個數應該不超過碼字總元素個數的一半。

基于SCMA的稀疏性、過載性等特征,接收端可以利用低復雜度的多用戶聯合檢測算法完成解碼,恢復原始的信息比特流。

2 混疊式NOMA

SCMA可以在一定程度上增加連接數目和系統網絡容量,但是,由于分配給調度接入和隨機競爭接入兩種訪問模式的資源是嚴格分離的,在一定程度上造成了資源浪費。在此基礎上,需要尋求一種可以打破調度接入和隨機競爭接入資源分配壁壘的方法。

本文提出了一種混疊式NOMA方法,允許調度接入和隨機競爭接入兩種接入模式以細粒度融合的方式共享同一信道單元。也就是說,基于某一信道單元上的虛擬層既可以分配給調度接入,也可以分配給隨機競爭接入。在該方法中,首先把資源分配給調度接入,之后剩余的資源供給隨機競爭接入。當調度用戶的個數減少時,供給隨機競爭接入的資源增多,因此,競爭用戶成功接入的個數也會相應增加;當調度用戶的個數增多時,由于在該方法中,首先把資源分配給調度接入,因此供給隨機競爭接入的資源相應減少,導致競爭用戶之間發生碰撞沖突的概率增加,競爭用戶成功接入的個數也會相應減少,并且由于調度接入比隨機競爭接入的性能更加穩定,因此全部用戶的吞吐量性能也相應增加。

圖2是傳統NOMA方法和混疊式NOMA方法的對比分析圖。其中,左側部分運用了混疊式NOMA方法,右側部分運用了傳統的NOMA方法。假設某蜂窩網絡社區包含8個子信道和10個用戶,并且把50%的子信道分配給調度接入,剩余的子信道供隨機競爭接入。如果調度用戶有7個,分別表示為(u1,u2,u3,u4,u5,u6,u7);競爭用戶有3個,分別表示為(v1,v2,v3)。在此場景中,如果運用傳統的NOMA方法,也就是說,分配給調度接入和隨機競爭接入兩種訪問模式的資源是嚴格分離的,那么將會有1個調度用戶(假設是u7)是分配不到資源的,需要等待BS的下一次調度分配;與此同時,供隨機競爭接入的資源尚有部分閑置。在同一社區中,如果調度用戶有3個,分別表示為(u1,u2,u3);競爭用戶有7個,分別表示為(v1,v2,v3,v4,v5,v6,v7)。由于供給隨機競爭接入的資源相對匱乏,不同的競爭用戶之間發生碰撞沖突的概率相應增加;與此同時,分配給調度接入的資源尚有部分閑置。基于先把資源分配給調度接入,之后剩余的資源供隨機競爭接入的特性,混疊式NOMA方法可以滿足調度用戶個數和競爭用戶個數的時變需求,很好地解決上述兩種場景中由于用戶個數的時變性而出現的問題。由上述兩種NOMA方法的對比分析可以看出,混疊式NOMA技術可以進一步滿足時變的網絡需求,縮短調度用戶的等待時延,提高網絡吞吐量。

圖2 兩種NOMA方法對比圖Fig.2 Comparison of two NOMA methods

值得注意的是,為了最大程度挖掘混疊式NOMA方法所帶來的優勢,需要進一步研究高效的問題,該問題的特點在于調度接入用戶的需求已知,但是競爭用戶采用隨機的方式獲取信道資源,會帶來不確定性以及沖突。因此,純粹的調度式接入或者純粹的隨機性接入方式均不能達到兩類接入方式整體的資源高效利用。因此,本文對該問題進行建模之后，設計了一種基于遺傳算法的混疊式NOMA資源分配算法,以使兩類接入方式的總容量達到最高。

3 問題建模

對于采用基于遺傳算法的混疊式NOMA方法的寬帶網絡社區,已知:① 全部用戶的業務需求;② 每個用戶在不同信道上各自的信噪比(signal to noise ratio,SNR)信息;③ 分配給每個調度用戶的資源。在此基礎上,根據香農定理,可以得到資源分配問題的目標優化函數為

(2)

式中,c表示全部用戶的香農容量;cg表示調度用戶的香農容量,即

(3)

約束條件:

(4)

(5)

αi,j=0,1

(6)

式(4)和式(5)約束了每個用戶最多可以占據一個虛擬層,并且每個虛擬層最多可以分配給一個用戶。式(6)表示用戶被分配到某一個信道上只可能存在兩種情況:被分配和未被分配。

根據上述分析可以得知,這是一個非確定性多項式(non-deterministic polynomial,NP)問題,所以無法在多項式時間內找到該問題的優化解。在此前提下,本文引入遺傳算法,對資源分配進行優化,以找到該問題的優化解。

4 算法描述

對于運用混疊式NOMA方法的寬帶網絡社區,可以引入遺傳算法對資源分配進行優化。本文采用的遺傳算法主要包括6個環節,分別表示為:初始化環節、整數編碼環節、計算適配度函數環節、選擇操作環節、交叉操作環節和變異操作環節,具體流程如圖3所示。

初始化環節:需要設定遺傳算法的最大迭代次數、交叉概率ρc和變異概率ρm,并隨機生成初始群體。其中,群體規模由染色體個數和每個染色體的基因位數決定。并且,用染色體的基因位表示虛擬層。

整數編碼環節:首先,假設群體中某個染色體表示為c=(x1,x2,…,xL),其中,L表示虛擬層個數,xi表示分配給每個虛擬層的用戶,并且,xi=u(u≠0)表示該虛擬層分配給調度用戶u接入使用,xi=0表示該虛擬層供競爭用戶隨機競爭接入。

圖3 遺傳算法流程Fig.3 Flow of genetic algorithm

計算適配度函數環節:采用香農公式刻畫信息傳輸速率,并以全部用戶的香農容量之和作為遺傳算法的適配度函數。其中,針對調度用戶部分,該算法計算其在所分配的虛擬層上的香農容量;針對競爭用戶部分,該算法根據估算出的成功接入的競爭用戶個數得到其香農容量。

選擇操作環節:在上述計算環節中得到的每個染色體的適配度函數值中,選擇用適配度函數值最大的染色體代替適配度函數值最小的染色體。完成上述選擇操作后,采用最優保留策略,直接保留一個適配度函數值最大的染色體進入下一輪迭代中。

交叉操作環節:依次隨機地選擇兩個染色體進行配對,直至全部染色體均完成配對操作。其中,如果染色體個數是奇數,那么適配度函數值最大的一個染色體不參與配對操作。之后,將交叉算子運用于群體,并對已完成上述配對操作的染色體對采用改進的單點交叉法。該方法具體表現為:假設選擇的兩個染色體分別表示為c1=(0,1,2,3,4,5)和c2=(4,2,1,5,0,3),交叉操作后產生的兩個新染色體分別表示為c3和c4,交叉點位置隨機地選擇為第3個基因位,那么根據交叉概率ρc,將染色體c1第3個基因位左側的所有基因作為新染色體c3左側的基因,之后開始從左到右依次查找染色體c2尚未出現在新染色體c3中的基因,并按在原染色體中的順序依次放到新染色體c3已有基因的后面,直至查找完染色體c2的所有基因,至此,可以得到新染色體c3=(0,1,4,2,5,3)。同理,可以得到新染色體c4=(4,2,0,1,3,5)。

變異操作環節:在該環節,將變異算子運用于群體中。具體操作為:首先在每個染色體上隨機地選取兩個不同的基因位,之后,根據變異概率ρm,對每個染色體選取的兩個基因位上的基因進行互換操作。

本文不斷重復上述環節中的計算適配度函數、選擇操作、交叉操作和變異操作4個環節,直至達到初始化部分設定的最大迭代次數。之后,將上述操作輸出的染色體矩陣作為最優資源分配方案,輸出的全部用戶的香農容量作為整個系統的效用函數,至此該算法完成。

5 仿真驗證

5.1 仿真設置

本文利用軟件模擬平臺NS2搭建仿真平臺,并根據相關標準和文獻中的典型配置設置仿真參數。

在采用混疊式NOMA方法的網絡場景中,假設BS位于場景中間,100個用戶隨機分布在BS四周。之后,把1 MHz的系統帶寬分為40個子信道,并把每相鄰的4個子信道作為一個子信道組。假設過載因子是1.5,根據SCMA方法的性質可知,每個子信道組包含6個虛擬層。同時,假設每個時隙的時長為0.5 ms,每個時隙發送的比特流長度為1 000 Bits,信道編碼采用1/2碼率的低密度奇偶校驗碼(low density parity check code,LDPC)。與以往仿真不同的地方是,在本仿真場景中,每個用戶在不同子信道上的SNR不同,并且SNR在文獻[2]中呈均勻分布。

5.2 仿真性能分析

基于采用的資源分配算法和NOMA方法的不同,本仿真對比了4種不同的方案,分別為:基于隨機資源分配算法且沒有運用混疊式NOMA方法的方案、基于隨機資源分配算法且運用混疊式NOMA方法的方案、基于啟發式算法且運用SGMA方法的方案和基于遺傳算法且運用混疊式NOMA方法的方案。其中,在基于隨機資源分配算法且沒有運用混疊式NOMA方法的方案中,分配給調度用戶和競爭用戶兩者的信道資源是嚴格分離的;而在其他3種方案中,信道資源優先分配給調度用戶,之后,剩余的信道資源供競爭用戶隨機接入。并且,啟發式算法僅考慮到優化調度用戶的資源分配,而遺傳算法則全面考慮優化全部用戶的資源分配。

5.2.1 調度用戶的個數對系統性能的影響

假設該場景中2/3的信道資源分配給調度用戶,剩余的信道資源供競爭用戶隨機接入;并且,競爭用戶的隨機接入概率是1/2。

平均吞吐量性能與調度用戶個數的關系如圖4和圖5所示,基于遺傳算法且運用混疊式NOMA方法的方案，平均吞吐量性能優于其他3種方案。

圖4 全部用戶的平均吞吐量性能與調度用戶個數的關系Fig.4 Relationship between the average throughput performance of all users and the number of scheduled users

圖5 調度用戶和競爭用戶各自的平均吞吐量性能與調度用戶個數的關系Fig.5 Relationship between the average throughput performance of scheduled users and competing users and the number of scheduled users

對于基于隨機資源分配算法且沒有運用混疊式NOMA方法的方案,分配給調度用戶和競爭用戶兩者的信道資源是嚴格分離的。因此,隨著調度用戶個數的增加,其吞吐量持續增長,直到所有的虛擬層均分配給調度用戶,之后,其吞吐量基本保持不變。與此同時,競爭用戶的個數逐漸減少,相互之間發生碰撞沖突的概率隨之減小。因此,競爭用戶的吞吐量略有增加;之后,隨著競爭用戶的個數越來越少,競爭用戶的吞吐量也逐漸減少。由于調度用戶的吞吐量性能比競爭用戶的吞吐量性能更加穩定,因此該方案的平均吞吐量隨著調度用戶個數的增加呈現先增加后減少的趨勢。

對于其他3種方案,其平均吞吐量隨著調度用戶個數的增加呈現先增加后基本保持不變的趨勢。這是由于資源優先分配給調度用戶,之后剩余的資源供競爭用戶隨機接入,所以隨著調度用戶個數的增加,調度用戶的吞吐量持續增加,直至所有的虛擬層均分配給調度用戶,之后其吞吐量基本保持穩定。與此同時,分配給競爭用戶的虛擬層逐漸減少,競爭用戶的吞吐量逐漸減少,直至接近零。基于啟發式算法和遺傳算法分別針對調度用戶和全部用戶的資源分配進行優化,后兩種方案的吞吐量性能優于基于隨機資源分配算法且運用混疊式NOMA方法的方案。并且,基于遺傳算法且運用混疊式NOMA方法的方案平均吞吐量性能優于基于啟發式算法且運用SGMA方法的方案。

5.2.2 調度用戶所占信道比率對系統性能的影響

假設在該場景中,調度用戶有40個,競爭用戶有60個,且競爭用戶的隨機接入概率是0.5。

如圖6和圖7所示,基于遺傳算法且運用混疊式NOMA方法的方案平均吞吐量性能優于其他3種方案。在基于隨機資源分配算法且沒有運用混疊式NOMA方法的方案中,其平均吞吐量隨著調度用戶所占信道比率的增加呈現先增加后減少的趨勢。這是因為在該方案中,分配給調度用戶和競爭用戶兩者的資源是嚴格分離的。因此,隨著調度用戶所占信道比率的增加,調度用戶的吞吐量持續增長,直到所有的用戶均已分配到虛擬層,之后其吞吐量基本保持不變。與此同時,競爭用戶所占信道比率減少,開始階段,競爭用戶基本均可以接入虛擬層,故其吞吐量基本保持不變,之后,隨著可供競爭用戶接入的虛擬層越來越少,相互之間發生碰撞沖突的概率隨之增加,故其吞吐量逐漸減少。由于調度用戶的吞吐量性能比競爭用戶的吞吐量性能更加穩定,因此,該方案的平均吞吐量隨著調度用戶所占信道比率的增加呈現先增加后減少的趨勢。

圖6 全部用戶的平均吞吐量性能與調度用戶所占信道比率的關系Fig.6 Relationship between the average throughput performance of all users and the ratio of channels allocated to scheduled users

對于其他3種方案,其平均吞吐量隨著調度用戶所占信道比率的變化基本保持穩定不變。這是因為資源優先分配給調度用戶,之后剩余的資源供競爭用戶隨機接入,因此,調度用戶所占信道比率的變化對調度用戶和競爭用戶兩者的吞吐量基本沒有影響,均基本保持不變。并且,由于后兩種方案分別對調度用戶和全部用戶的資源分配進行優化,因此,其吞吐量性能更佳,并且基于遺傳算法且運用混疊式NOMA方法的方案的吞吐量性能優于基于啟發式算法且運用SGMA方法的方案。

圖7 調度用戶和競爭用戶各自的平均吞吐量性能與調度用戶所占信道比率的關系Fig.7 Relationship between the average throughput performance of scheduled and competing users and the ratio ofchannels allocated to scheduled users

6 結 論

為了解決寬帶網超密集無線連接和超大規模網絡容量的問題,本文提出了一種混疊式NOMA方法,該方法允許調度用戶和競爭用戶以細粒度融合的方式共享同一信道單元。在此基礎上,進一步提出了基于遺傳算法的NOMA資源分配算法,該算法針對調度接入和隨機競爭接入兩種接入模式的資源分配進行了整體優化。通過與其他3種方案的仿真對比證明,本文提出的混疊式NOMA方法及其資源分配算法在各種場景下均能夠提升吞吐量性能。隨著無線連接愈發密集以及網絡規模不斷擴大,本文所設計的方法能夠進一步凸顯其優勢。一方面,本文仿真結果證明了隨著用戶數的增大,所提方案持續具有性能增益。另一方面,無線連接數和網絡規模的擴大使得隨機競爭接入為系統所帶來的不確定性加大,如果依然沿襲傳統的基于資源隔離的分配方法會使得資源利用率更低,而本文方法正是充分考慮了調度接入和隨機接入的聯合性能,因而具有更好的適應性和擴展性。