基于信道排序的認知頻譜分配算法?

蔣孜浩，鄭安琪，秦寧寧

(江南大學輕工過程先進控制教育部重點實驗室，江蘇 無錫 214122)

認知傳感網(Cognitive Radio Sensor Network，，CRSN)利用認知無線電技術(Cognitive Radio，CR)加持傳感器節點以克服頻譜資源短缺問題，在頻譜受限的情況下認知節點利用頻譜感知結果判斷信道是否可接入，相比傳統無線傳感器網絡(Wireless Sensor Networks，WSN)可以有效減少信道之間的干擾以增加網絡的吞吐，適應更加復雜的場景，有著良好的應用前景[1]。

認知節點通過感知并對授權用戶進行空洞檢測，以機會接入頻譜，因此可以實現在不干擾授權用戶的情況下積極使用空洞頻譜的功能[2]。基于認知無線電技術機會利用頻譜的特性，在頻譜受限情況下，認知傳感網相比于傳統無線傳感器網絡，可以有效減少信道碰撞所產生的能耗，降低信道競爭帶來的網絡時延與吞吐受限問題。但其較高的資源開銷卻擊中了無線傳感器網絡的另一個痛點[3]。無線傳感器網絡節點通常擁有受限的能量且某些情況下無法通過外界供能，而認知無線電技術則需要對環境進行持續的監聽以有機會接入空洞頻譜，這不僅壓縮了節點的休眠時間，同時又產生了額外的能量消耗，增加了節點的續航壓力。

不同的頻譜有著不同的通信質量，這意味著認知傳感網中的節點選擇不同的頻譜進行通信將會有不同的吞吐量與不同的能耗，因此為網絡中次用戶進行適當的頻譜分配是認知傳感器網絡中的關鍵技術。傳統認知無線電與傳統無線傳感器網絡的核心技術顯然不適合直接搬運至認知傳感網的組網與頻譜分配中，需要對相關的認知傳感網頻譜分配方案進行深入研究。

認知傳感網的頻譜分配問題被明確提出于文獻[4]，該文獻將頻譜分配算法大致分為靜態分配與動態分配兩大類。靜態頻譜分配主要針對較為穩定的網絡環境，分得資源后的節點短期內不會改變其頻譜的選擇，通常網絡會先行給出頻譜資源與相關的約束條件，再將網絡中的路由固定后，便可將頻譜分配問題轉換為數學優化問題，通過各類算法求解頻譜分配問題。

不少學者將頻譜分配問題建模為圖染色問題，通過粒子群算法[5]和灰狼算法[6]等群尋優算法實現問題的解決。文獻[7]與文獻[8]則基于微觀經濟學中定價拍賣原理對頻譜分配問題進行建模，通過確認目標函數與指定贏家勝出規則實現最優化的頻譜分配。

針對認知傳感網頻譜分配對網絡能耗的影響，本文提出了適應信道的改進遺傳算法(Adapt Channel Improved Genetic Algorithm，ACGA)進行頻譜分配。通過一種基于信道貪婪排序的交叉方式與一種混合變異策略實現種群的更新與優化。仿真結果顯示，基于信道貪婪排序的交叉方式可以明顯增強ACGA 算法的尋優能力與尋優速度，而混合變異策略則在不同的信道數量下有著不同的效果。

1 系統模型及問題描述

1.1 網絡模型

網絡中存在著M個主用戶節點PU 與N個次用戶節點SU，其中PU＝{pum｜m＝1，2，…，M}，SU＝{sun｜n＝1，2，…，N}，PU 均等占用網絡中的頻譜資源，即有M個信道C＝{cm｜m＝1，2，…，M}平等分配給每個PU。

SU 作為次用戶僅可在PU 未占用頻譜的狀態下使用其頻譜的空閑間隙。圖1 所示為認知傳感網的多跳路由，圖中左右虛線圓圈分別為基于雙天線認知節點與基于單天線認知節點的多跳路由，網絡中實線鏈路為用于上傳節點數據至基站的下跳鏈路，而虛直線則是傳輸控制信息的上跳鏈路，網絡中的可用信道集合為{c1，c2，c3}。

圖1 單、雙天線下認知傳感網的多跳路由

顯然單天線模式的多跳路由上下行信道相異，勢必使得網絡存在大量的數據傳輸沖突進而增加網絡能耗，且切換收發信道的能耗浪費也不容忽視。在能耗之外，單天線路由還減少了網絡的可用資源，如圖1 中網絡選擇信道c3作為公共控制信道[9]導致了網絡的可選擇信道數量減少。

因此可采取一種區分接收與發送的工作方式，將一個節點的收發工作分給兩根天線完成，在實現單一SU 上下行相不干擾的同時，降低SU 之間的干擾，由此便產生了雙天線路由。在雙天線的認知路由中，節點間的上下行信道可實現分離，并避免接收控制信息而產生的額外頻譜切換次數，降低網絡沖突和信道切換帶來的額外能耗。

1.2 PU 模型與信道檢測

PU 是網絡中的主用戶，在網絡資源的使用中處于優勢地位，其對信道的占用行為可類比為一個馬爾可夫過程[10]，通過能量檢測識別PU 對于信道占用情況是最為常見的方式。能量檢測通過統計PU 信號一段時間內的能量并與預設閾值對比，判斷PU 對于頻譜的占用情況。該方案復雜度低且無需知道檢測信道中的信號細節，但檢測結果易受到環境噪聲與PU 信號的影響，在低信噪比的情況下，檢測結果的可信度會顯著降低[11]。

假設PU 的發射信號xPU服從正態分布，則在SU 處接收的對應信道中信號x也服從正態分布，在節點SU 計算得到所接收PU 的信號強度方差后。可根據已知的呈正態分布的網絡噪聲方差，計算得到sun認知cm檢測概率Qn，m:

式中:Q(?)表示正態分布右尾函數；γ＝βNT＋(1－β)NT(SNR＋1)；β為檢測因子，其取值區間為[0，1]；SNR＝

1.3 問題規劃

在將頻譜資源劃分為多條可用信道的情況下，可將CRSN 的頻譜分配問題抽象為一個基于圖染色理論的信道分配模型。若將各節點發送信道抽象為色塊，則可將鄰近節點選擇不同發送信道的問題轉化為相鄰色塊的染色問題[12]。

假設每個傳感器都攜帶有一個初始能量固定的電池。將通信信道看作簡單的路徑損耗模型，則使用時隙進行傳輸的能量消耗建模如下:

式中:Ecir為射頻電路的能量消耗，s為一個時隙可以發送的數據大小，εs和εm分別為接收機所需的放大器能量。dn，i為sun與sui之間的通信距離，sui為sun的下跳節點。d0是常數，取決于傳感器網絡應用的環境。

由于節點需對信道進行認知才能進行接入并開始傳輸，則sun在信道cm上傳輸成功一次的統計期望能耗如下:

假設相關沖突節點間使用信道競爭機制進行數據的上傳，則節點間的信道競爭也需要能耗。不同的節點若選擇相同信道就可能產生認知信道的競爭問題，顯然節點的競爭次數與干擾節點數量和干擾節點所傳數據量相關。假設節點競爭獲得信道的概率相同，有i個節點通過競爭占用信道，則參與競爭的節點sun平均競爭次數tn可建模如下:

式中:Dj表示節點suj的周期數據量，以單位時隙所發數據量作為單位；∑(Dj/Qj，m)表示參與競爭的所有節點理想傳輸次數之和，則sun使用信道cm的統計期望能耗如下:

其中Ecom為節點的競爭能耗，由此最小化網絡能耗U的問題如下所示:

式中:XSU為節點信道分配矩陣，xi為節點sui所選信道編號，即節點cxi所選信道。若以遍歷的方式計算最佳的信道分配，意味著需要計算MN次才能確定，這顯然是一個NP 難問題。為此論文提出了一種適應信道的改進遺傳算法(Adapt Channel Improved Genetic Algorithm，ACGA)進行頻譜選擇。

2 基于信道排序的頻譜分配

2.1 基于信道排序的交叉過程

遺傳算法中，解域的編碼是算法實現的第一步[13]，在該步驟下遺傳算法會將解空間進行離散化，如若解域連續，則離散化也勢必使得算法的問題求解精度有所下降。在頻譜分配問題中，由于可選信道數量是固定的，因此認知節點的解空間可以依據數字編號依次與信道所對應以實現離散化編碼，這表明了頻譜分配問題是一類解域離散的優化問題。但由于頻譜分配問題的可選擇信道數量較少，因此在遺傳交叉過程中，極易產生父類相似度過高的近親交叉問題，這會降低算法的交叉有效性，進而影響算法的頻譜分配能力。

在頻譜分配問題中，一個解X就代表著一個個體，其中每個維度xk，k＝1，2，…，K即代表著一個節點的信道選擇，也代表著個體中的基因。為保證交叉的有效性，采用了一種基于信道貪婪排序的交叉方法。

①個體相似度

為了適應頻譜分配問題中解的交叉問題，論文首先將父類個體Xi和Xj中的基因進行了相似分類。對于Xi和Xj中相同位置的基因，若二者相同則稱該基因為相似基因，不同則稱作不同基因。顯然相似基因無需交叉，因此只需執行不同基因的交叉工作，但若是Xi和Xj相似度過高，則會出現交叉程度不明顯的問題，為了數值化個體間的相似度，定義父類個體Xi和Xj之間的個體相似度Si，j如下:

式中:☉為同或運算符號；sum()為計算求和矩陣中的非零值；當Si，j較高時，代表著個體Xi和個體Xj之間的相似程度較高，即此時Xi與Xj是一種近親的關系。被選擇交叉的二者若為近親關系，也許是兩者都已經貼近了全局或局部最優解，又或許兩者僅僅只是相似。在遺傳算法的運行中，隨著迭代次數的增加種群將越來越靠近全局最優解，因此也容易陷入局部最優解中，顯然前一種的概率較高，因此近親交叉極其容易陷入局部最優解。

②個體的信道貪婪排序

假設網絡中所有節點間不存在競爭關系，則可以基于不同信道選擇下的節點周期能耗對信道進行從小到大的排序，依據從小到大的順序將1～M編號與信道進行對應形成信道排序矩陣R:

式中:rk內元素需相互不重復，rand(M)為取[1，M]的隨機整數，用以對應信道排序后的編號，rk[m]的值代表cm在節點sun中的排序編號。顯然這是一類貪婪排序，因為每個節點在排序信道的過程中只考慮了自己的收益。

③基于信道排序的交叉過程

在此信道排序基礎上，提出了基于信道收益排序的交叉算法。對于不同基因的交叉，首先計算Xi和Xj中的不同基因對應節點sun的排序和。然后在交叉過程中，隨機產生一個小于該排序和的整數，在Rk中選擇出與該整數對應的信道作為交叉后Xi的基因，并將排序和與該整數的差對應的信道作為交叉后Xj的基因。

所提交叉算法基于信道的貪婪排序實現交叉信道的重組替換，基于兩個父代個體中基因總體收益重選子類的基因，保留了父代的基因信息。

當兩個相似度過高的父代進行交叉算法時，不僅容易導致交叉的失效，同時也大大降低了交叉隨機性。為了解決近親交叉帶來的子代缺陷問題，論文為交叉算法增加了一種交叉變異機制，以期待減少子代的基因缺陷。

圖2 所示是一次基于信道排序的交叉過程，假設可選信道集合為{c1，c2，c3，c4}，其中父代個體X1和X2進行交叉并產生兩個新的子代個體X3和X4。對比父代個體，可見兩個個體在su2位置上的基因不同，因此對該位置進行交叉，依據su2的信道排序，計算得到X1和X2在su4上的排序和為4，隨機產生一個隨機數2 后，su2位置的基因交叉結果為{c2，c2}并將該兩位基于隨機給予子代個體X3和X4。

圖2 基于信道排序的交叉過程

由于X1和X2中僅存在一位不同基因，因此判斷兩者相似度過高并進入隨機交叉流程，在隨機選中su4作為變異交叉基因后，對該su4基因位置執行如su2一樣的交叉過程。可見在執行交叉算法后，子代個體X3和X4相比父代保留了較多的基因特征。基于貪婪信道排序的交叉方式在使得子代產生了一定的個體異化的同時，也在一點程度上均衡了子代之間的總體收益。

為了執行變異交叉步驟，需要提前設置相似度閾值S和最小不相似個數SN，當計算得到Si，j大于S時，判斷Xi和Xj屬于近親，并基于SN 選擇隨機基因進行變異交叉。相似度閾值S和最小不相似個數SN 可以通過下式計算:

式中:算法會首先隨機產生大量樣本解，然后從中選出收益最佳的num 個進行S的計算。并依據以下規則進行交叉變異:當Si，j大于S時，計算相似基因的個數與SN 求差值，然后隨機選取與二者差值個數相同的相似基因進行基于信道排序的基因交叉算法。

則輸入兩個父代個體求取兩個子代個體的交叉算法偽代碼如下:

其中，calS(X1，X2)為根據式(8)求取兩個父代的相似度S12；find(X1≠X2)為找出兩個父代不同的基因，并輸出不同基因的編號矩陣；choose(temp1，num)為從temp1 中隨機抽取num 個基因編號組成新的矩陣；random(point－1)輸出一個小于point－1的正整數；Line4～Line8 為判斷是否需要執行變異交叉的過程；Line9～Line17 根據需交叉基因矩陣temp 進行交叉，獲得子代個體X3和X4。

2.2 混合變異策略

基因變異不僅是為了跳出當前局部最優解，同時也是遺傳算法增加新優秀基因的重要渠道。為了更好地增加變異的效果，對于被選中需變異的個體，采用一種混合變異策略，當節點被選中變異時，會隨機生成一個[0，1]的隨機數η與變異閾值α進行對比，以此判斷采取的策略，如式(12)所示:

當η>α時，該個體將會基于隨機變異進行個體的異化，通過隨機基因的隨機替換實現個體的變異，該變異方式無法確定變異后個體收益的好壞，但卻可以引入一些較差的解以均衡種群生態。

當η≤α時，該個體將會基于博弈進行個體的進化。該博弈基于帕累托最優規則[14]進行，遵守每次策略的選擇都必須符合博弈者只能做出對自己更好且不使其他參與者變差的規則。運用到頻譜分配過程中，每個節點的信道選擇基于隨機順序產生，且單次博弈過程中，該順序不產生變化。顯然上述博弈過程是一種近似求解算法，因此個體在使用博弈進行變異后，必然會使得該個體變異后收益提升，這可以保證個體變異后種群整體質量的增加。

通過改變變異閾值α可以適當搭配博弈論與隨機變異以獲得足夠的跳出當前局部最優解和尋找其他局部最優解的能力。博弈論可以為種群增加新的局部最優解，而隨機變異則會均衡種群的平均收益，盡量為種群注入新的基因。

3 仿真及結果分析

利用MATLAB 建立仿真實驗，對均衡能耗的頻譜分配問題進行分析，同時驗證基于信道排序的交叉算法和混合變異算法對ACGA 的改進作用。仿真實驗在已知路由的網絡上建立，對ACGA 算法的頻譜分配效果進行分析。

仿真假設網絡區域為邊長為100 m 的正方形，BS 處于正中心，30 個作為次用戶的認知節點與M個PU 隨機散布在區域中，其余參數如表1 所示。

表1 仿真參數設置

3.1 頻譜分配解域分析

由于頻譜分配問題是一類NP 難問題，為分析頻譜分配在不同主用戶數量M下解的大致收益情況，在不同M數量的相同網絡快照下，對隨機產生的10 000 個初始解進行收益統計。

圖3 為去除了離散值后統計得出的周期能耗箱線圖，可見，在不同的M數量下，大部分解的收益都分布于箱線圖的中間區。當M≤5 時，信道數量對于網絡能耗的限制較為明顯，隨著M數量的增加，網絡的能耗中位數與能耗最小值也相應呈現單調下降的趨勢，這是節點間信道競爭減少帶來的能耗收益。而M數量增加所帶來的增益也存在一定的邊際效應，即若網絡中信道的數量多至節點可以隨意選擇且不存有干擾后，此時M的增長對網絡的影響較為微小。

圖3 隨機樣本解能耗在不同M 下的分布情況

基于上述隨機樣本，取其中收益最佳的100 個解對相似度閾值S和最大相似個數SN 進行求取，對此在不同的M數量下，S和SN 的值如表2 所示，其中SN 需向上取整后才能進行使用。

表2 相似度閾值S 和最小不相似個數SN 的取值

可見隨著M數量的增加，相似度閾值呈現單調上升趨勢。這是因為隨著M數量的增加，網絡中節點的沖突減少，收益較好解中的節點信道選擇會趨向貪婪，即每個節點會選擇信道貪婪排序中順位較高的信道而不考慮節點間干擾。

3.2 交叉與變異性能分析

為分析ACGA 的交叉與變異算法的性能，設置GA 和ACGA 的初始種群數量為1 000，ACGA 中變異概率為0.1 且將變異閾值α分別設置為0、0.5、1，而GA 的交叉概率和變異概率分別設置為0.5 和0.1，且利用10 位二進制對信道進行編碼。以M作為變量，每輪均在相同的網絡快照下對ACGA 和GA 各進行50 次仿真并取平均值。

圖4 和圖5 分別為ACGA 和GA 的網絡周期平均能耗對比圖和算法平均收斂迭代次數圖，當變異閾值α＝0 時，ACGA 中個體將只進行隨機變異，這意味著此時ACGA 對比GA 就只進行了交叉的改進。將GA 與變異閾值α＝0 的ACGA 對比，可以看到ACGA 在優化效果和收斂速度上，相比基礎GA更具備優勢，這說明基于信道排序的交叉算法可以有效增加交叉后子代的優秀率，增強種群的進化速度。

圖4 不同M 下GA 和ACGA 網絡周期平均能耗

圖5 不同M 下GA 和ACGA 算法平均收斂迭代次數

在M≤5 的情況下，ACAG 中基于博弈論的變異方式并不能給種群帶來優質個體，反而會因為博弈占用了資源卻無法取得良好效果的問題導致算法性能受到影響。對ACGA 算法而言，設置變異閾值α＝1 意味著算法在M≤5 時同時失去了博弈變異能力與隨機變異的能力，這使得種群快速迭代并收斂到最終較差的局部最優解。而α＝0 的ACGA 算法在M≤5 時則可以依靠隨機變異的進行更大范圍的搜索，通過增加迭代次數的方式增加算法性能。

而在M>5 后，隨M的增加，α＝1 的ACGA 算法尋優能力逐步加強，在快速收斂的同時也擁有較較強的尋優能力，這是因為博弈在M≥10 之后優異的近似求解性能為算法提供了大量不同的局部最優解，在較少的迭代后就可以進行收斂并取得不錯的收益。從總體上看，設置α＝0.5 的ACGA 可以獲得較為平衡的性能，在利用博弈算法M≥10 尋找局部最優解的同時，又不使得算法失去獲取隨機基因的能力。

3.3 頻譜分配效果分析

為分析ACGA 在頻譜分配問題上的尋優效果，將其與離散粒子群算法[15](Discrete Particle Swarm Optimization，DPSO)、離散灰狼算法[16](Discrete Gray Wolf Optimization，DGWO) 和基礎遺傳算法(Genetic Algorithm，GA)進行仿真對比，以M為變量分析4 種尋優算法的性能。仿真設置DPSO 和DGWO 的初始粒子和狼群數量為1 000，GA 和ACGA 的初始種群數量為1 000，交叉概率和變異概率分別設置為0.5 和0.1，其中設置ACGA 的變異閾值α＝0.5。每次仿真均在相同的網絡快照下，對ACGA、DPSO、DGWO 和GA 進行50 次仿真。

圖6 所示為4 種算法在不同M下進行頻譜分配所獲得的平均網絡周期能耗，可以看到4 種算法的執行結果都符合隨著M增大而網絡周期能耗減小的趨勢，這與3.1 節中分析結果相同。DPSO、DGWO 在頻譜分配問題上的求解效果類似，兩者的求解效果較GA 和ACGA 均稍差，這是因為DPSO和DGWO 這兩類基于步長迭代的算法顯然更適合用于連續問題的求解，而在頻譜分配問題中解與收益的離散性較強，導致基于步長迭代的兩類算法并不能實現較好的迭代效果以增加全局搜索能力，反而因為步長的限制更容易陷入局部最優解中而導致過早停止迭代。

圖6 不同M 下4 種算法平均網絡周期能耗

對比GA 與α＝0.5 的ACGA 的平均網絡周期能耗，可以發現二者在M變化下的曲線趨勢相似。二者在M＝13 和M＝8 時分別產生了最大和最小的差值，分別為0.005 2 J 和0.031 1 J，從全局上看，α＝0.5 的ACGA 有著較為均衡的性能，相比原始GA 算法有著較強的尋優能力。

圖7 給出了4 種算法在不同M值下的平均收斂次數，GA 算法因為本身的全局搜索能力就較強，因此相比DPSO 和DGWO 迭代次數較高且尋優性能較好，但因為頻譜分配問題屬于NP 難問題，僅靠普通的交叉算法與變異算法很難優到最優解。圖中GA在算法在經過高于36 次的迭代后就因難以找到更好的局部最優解而停止了迭代，而DPSO、DGWO 則因為步長迭代的方式以至于算法運行中快速進行了收斂而導致算法停止，相比較GA，兩種算法的迭代次數只有GA 迭代次數的75%左右。α＝0.5 的ACGA 因為改進了交叉算法以及變異算法，相比GA 可以更多接觸到局部最優解，同時較強的全局搜索能力也保證了性能的優勢，因此可以在較少的迭代次數下獲得較高的收益。顯然ACGA 相比其余三類算法在頻譜分配的問題上有著較大的優勢，由于頻譜分配屬于一類多維度的離散的NP 難問題，因此在類似的相關問題中，ACGA 也可以實現良好的效果。

圖7 不同M 下4 種算法收斂次數

4 總結

針對認知傳感網中的能耗問題，提出了一種基于適應信道問題的改進遺傳算法。為了增加執行交叉算法后父代與子代的聯系，采用了一種基于信道排序的交叉算法實現種群的交叉迭代。其后利用混合博弈論的變異算法進行個體的異化工作，以在維持種群多樣性的同時增加挑選優秀基因的能力。仿真結果表明，ACGA 相比基礎的遺傳算法在頻譜分配問題上有著優秀的尋優性能，可以較好地優化基于網絡能耗的頻譜分配問題。