基于多態蟻群優化算法的認知無線電動態頻譜接入策略

滕志軍, 滕利鑫, 謝露瑩, 曲福娟

(1. 東北電力大學 現代電力系統仿真控制與綠色電能新技術教育部重點實驗室, 吉林 吉林 132012; 2. 東北電力大學 電氣工程學院, 吉林 吉林 132012)

近年來,無線通信領域持續繁榮,導致頻譜資源嚴重緊缺,認知無線電技術是解決該問題的一種有效方式,這項技術可以自動找尋和充分利用可用頻譜資源.在認知無線電網絡中,認知用戶可以接入頻譜資源的前提條件是不能對主用戶產生干擾,前者是以一種機會的方式占用可用頻譜資源[1-2].頻譜分配的核心思想是對感知到的未被占用的頻譜進行公平且高效的分配,提高頻譜的使用效率[3].頻譜分配問題本質上是一種優化問題,且具有非確定性特點.因此,利用智能優化算法求解十分有效.蟻群算法是一種新興的群智能算法,其核心思想是由 M. DORIGO等最先提出的,在解決全局優化求解問題中得到廣泛使用,無論是在解決簡單的單目標優化問題,還是復雜的多目標優化問題上都行之有效.文獻[4]所研究的蟻群優化算法(ant colony optimization,ACO),在信息素積累方面做了改良,引入學習因子,使得到最優解的時間縮短,非確定性多項式(nondeterministic polynomially,NP)問題得到有效解決,節約時間開銷.但在ACO分配模型中,由于效益函數不完善,未能兼顧到增益矩陣,導致網絡總效益有所下降.文獻[5]研究的遺傳蟻群算法提高了網絡平均效益,但沒有針對頻譜分配的公平性問題進行討論.文獻[6]在解決系統吞吐量問題上,采用聯合頻譜分配方法,從頻譜感知時間和子信道感知門限入手,確保系統擁有較高吞吐量,但是導致認知用戶間的競爭增大,系統的公平性很難保證.文獻[7]以傳統蟻群算法為基礎,設置了自助查詢搜索窗口,指定了螞蟻的前進路徑,縮短了搜索時間,以達到提高系統整體效益的目的,但是該研究算法在整體尋優方面存在不足,不能很好地得到全局最優解.現有模型的分配大多未能考慮差別用戶對頻譜的需求程度,總是采用平均分配模式,未從認知用戶需求角度考慮,導致公平性降低,頻譜資源不能更好地被利用[7-10].蟻群算法可以充分利用系統中的反饋信息,具有求解精確、收斂速度快等優勢,十分適用于頻譜分配算法.

為此,筆者針對認知無線電頻譜分配中存在的認知用戶間競爭大、網絡效益低和認知用戶接入可用信道所用時間長的問題,提出一種基于蟻群優化的分配算法,借助信息素的增強型積累,為蟻群算法中螞蟻的行動提供依據,即通過信息素計算螞蟻的行動概率,使頻譜以更高的概率分配到信息素較多的信道上,從而快速收斂到最優路徑上,提高網絡效益,增強認知用戶間的公平性,節省頻譜分配所需要時間,提升系統吞吐量.

1 頻譜分配模型

分布式認知無線電頻譜共享系統模式下,認知用戶(次用戶)都是根據其自身性質、性能及方位等情況,來感知主用戶(授權用戶)信號的情況[11].繼而認知用戶可以得到其各自可用的頻譜,以及了解受到的干擾約束條件[12].認知用戶間可以實現信息交互.頻譜共享的方式有兩種:一種是通過控制信道得到需要的信息;另一種是通過認知無線網絡基站了解頻譜的占用情況[13-16].具體的頻譜分配可以用以下矩陣描述:

1) 可用信道矩陣L=[ln,m|ln,m∈[0,1]]N×M.主用戶如果已經占用信道m,這時要是使用該信道,便會對主用戶的正常接入造成不必要的干擾.可用信道矩陣只用于主用戶之間,所以可用信道矩陣對認知用戶間的相互干擾不予考慮.

2) 干擾約束矩陣C=[cn,k,m|cn,k,m∈[0,1]]N×K×M.該矩陣說明的是認知用戶之間的干擾約束問題.如果cn,k,m=1,說明當用戶n和k一起占用同一個信道m的話,就會使彼此之間的干擾變大.決定干擾約束的條件主要有用戶所在區域、用戶之間距離和信號強度.

3) 信道效益矩陣B=[bn,m]N×M.該矩陣說明的是一個認知用戶接入該信道時得到的信道吞吐量,就是該用戶是否順利接入該信道.bn,m說明的是在沒有鄰道干擾時,用戶n接入信道m后,能獲得的最大帶寬吞吐量比.若可用信道矩陣中元素ln,m=0,則bn,m=0.

4) 無沖突分配矩陣S=[sn，m|sn，m∈[0,1]]N×M.當sn,m=1時,表示用戶n正在使用信道m.若信道m不能分配給用戶n使用,則sn,m=0.此外,該矩陣需要達到可用信道矩陣LN×M和干擾約束矩陣CN×K×M規定的干擾約束條件如下:

sn，m+sk，m≤1,cn,k,m=1，
?n≥1,k≤N,1≤m≤M.

(1)

2 基于蟻群的頻譜分配算法的轉移概率建立

2.1 蟻群算法相關參量和規則

1) 節點為螞蟻可能訪問的每一個認知用戶.

2) 移動路徑為分配給用戶的一個信道.

3) 螞蟻訪問的節點數即為認知用戶的個數N,用編號n表示.信道總數為M,用編號m表示.

4) 螞蟻的個數可用X來表示,迭代次數用ξ來表示.

5) 干擾約束條件決定螞蟻經過節點時釋放信息素的多少、螞蟻到達該節點時能獲得的信道效益和螞蟻所經歷路線的長短及螞蟻能否到達終點.

6) 每個認知用戶擁有同樣的螞蟻數量,即每個認知用戶成為源節點的概率相同,且每個節點不會被相同的螞蟻重復經過.

2.2 轉移概率建立過程

2.2.1初始化參數的設置

設置的參數包括迭代次數和節點螞蟻個數.可用信道矩陣L和效益矩陣C是動態調節矩陣,每個螞蟻一旦位置變化,這兩個矩陣便會自動調節數值.對禁忌表進行參數設定,對螞蟻走過的每個節點進行記憶,且每只螞蟻只能走過相同的節點一次.信息素矩陣是TN×M×ξ.

2.2.2信道分配

(2)

1) 螞蟻行為判斷.螞蟻行動函數決定螞蟻下一步行動,判斷準則如下:

(3)

當AX,ξ=0時,表示認知用戶n使用信道m時對其他認知用戶經過該節點不造成干擾,這時螞蟻會繼續移動,直到終點,否則螞蟻X繼續留在該節點,不再前進.反之,當AX,ξ=1時,螞蟻前進尋找新的節點.每當螞蟻完成一次行動,進行下次行動之前,刪除上一個節點分配的信道以及與其產生干擾的信道,并重新設置用戶節點與信道的干擾約束關系.隨著螞蟻行為的不斷變化,用戶的可用信道和干擾約束關系也隨之變化.這些都是通過設置L和C完成的.

2) 螞蟻轉移概率.螞蟻行動未終止時根據公式選下一節點,為了保證路徑的多樣性,螞蟻的行動既要考慮信息素,同時又要考慮觀測值,觀測值是和消耗與干擾有關的函數,即

(4)

DLn,m為用戶n使用信道m時的信道切換時延Dswitching,ln,m與排隊時延Dqueueing,ln,m之和,其公式為

DLn,m=Dswitching,ln,m+Dqueueing,ln,m.

(5)

Dswitching,ln,m為節點n從前一信道k接入下一信道所產生的切換時延.計算公式為

(6)

但是,次用戶j可能正在使用信道m,所以需要等待次用戶j不再使用信道m,由此產生排隊等候時延Dqueueing,ln,m,即

(7)

由此得到轉移概率公式:

(8)

式中:N體現螞蟻接下來可能經過的所有節點數,禁忌表中的元素不包含在N中;α和β為權重因子,分別代表信息素和信道效益的相對重要程度;tn,m,ξ代表信息素矩陣的元素,用以表達螞蟻在第ξ次迭代時用戶n在信道m處釋放的信息素多少.

3) 選擇后繼用戶節點.螞蟻的每一步移動,代表解的一個可行路徑,螞蟻下一步移動到哪個節點由以下公式決定:

(9)

式中:n′為行動判決依據;g為隨機數,g=(0，1);螞蟻行動判定閾值G=0.9;RW代表輪盤賭法.

若g

3 改進的基于時間效率的信息素分配方法

在傳統的以蟻群算法為核心的頻譜分配問題中,僅考慮了頻譜分配中的干擾和信道效益[17-19],而未考慮到用戶n在占用信道m時所需時間,這會影響到信道使用效率,所以通過在信息素的更新過程中引入時間參數來對蟻群算法進行優化,最終得到一個新的信息素更新公式,通過改進后的信息素更新公式提升頻譜接入速度.在傳統蟻群算法中,信息素矩陣各元素按照下式更新:

(10)

式中:Q為信息素的強度;d′為螞蟻訪問的節點個數，個.

(11)

式中:τi為螞蟻到達第i節點所經歷的時間,在本算法中,螞蟻每到達一個節點,時間重置,并記錄螞蟻從上一節點出發到達當前節點的時間;τ為循環過程經歷的總時間.

則有

(12)

由式(12)可得出最終信息素更新時間系數ηi：

(13)

信息素矩陣各元素更新公式如下:

(14)

當一只螞蟻停在某個節點不再繼續移動時,算法的循環結束.螞蟻移動過程中,記錄到達每一個節點的時間τ.根據螞蟻路線和時間,在式(14)基礎上對信息素矩陣中各元素進一步更新:

(15)

傳統的蟻群算法是將信息素按螞蟻所經歷的節點數平均分配給每一個節點,即Q/dn.通過該公式,按照螞蟻通過信道m到達每一個節點的時間,將信息素分配給每一個節點,時間少的分配信息素多,時間多的分配信息素少.

將局部信息素進行更新,繼而將全局信息素進一步更新,每次迭代完成后,由式(16)重新計算每條路徑上的信息素.即

(16)

根據式(16)得到最終的信息素更新公式:

(17)

在完成全局信息素更新后,將所有節點信息素進行比較,按照信息素大小順序來分配信道.即

(18)

式中:ωn為信道的最終判決依據.

在經過ξmax次迭代后,將信道分配給信息素最大的用戶.分配后,需要將信息素矩陣初始化,然后進行下一輪分配.算法總體流程圖如圖1所示.

圖1 算法流程圖

4 試驗仿真及結果分析

首先進行場景的設置.設定螞蟻訪問的區域為一個N×M的點陣空間,其中有M個可用信道提供認知用戶接入,每個授權用戶都有固定的保護范圍.當授權用戶接入信道后,認知用戶再準備接入.

仿真設定區域為一個30×30的網格區域,存在20個認知用戶,可提供給認知用戶使用的信道有30個.認知用戶先不進行任何行動,當主用戶未對其授權頻段進行使用時,認知用戶根據分配的頻譜乘機接入到該頻譜.每個認知用戶的干擾范圍d為[3,6].根據上述參數能夠計算出可用矩陣L、干擾矩陣C和效益矩陣B.設定搜索蟻數量X=25只,最大迭代次數為ξmax=100次,信息素揮發因子ρ=0.11,信息素指數設為1,啟發式信息指數為3,初始信息量c=5,信息素強度Q=2.仿真進行50次獨立試驗,并記錄結果,且每次試驗時的矩陣L,B和C均隨機生成.

圖2為3種算法下可用信道數與網絡收益總和的關系比較.由圖2可知:選取本研究中改進的算法進行頻譜分配時,網絡效益總和高于另外兩種算法;隨著可用信道m的數量不斷增大,本研究算法的網絡收益總和始終高于AOC算法和QGA算法.這是由于引入的時間參數對信道的效益起到了很好的調節作用,減少了認知用戶的搜索時間,繼而提高了系統網絡收益.

圖2 3種算法下可用信道數與網絡收益總和的關系比較

圖3為3種算法下認知用戶數與網絡收益總和的關系比較.由圖3可知:當認知用戶數量不斷增多時,3種算法的網絡收益總和都在減小;認知用戶數量不斷增多,作用于可用信道的干擾也隨之增多,繼而分配可用信道的時間也相應變長.本研究算法改進后收斂速度顯著提高,在信道數量一定時,能夠使認知用戶更好地做出選擇,提高網絡收益.

圖3 3種算法下認知用戶數與網絡收益總和的關系比較

圖4為3種算法下認知用戶數與算法網絡公平性關系比較.由圖4可知,認知用戶數增多時,競爭也隨之增大.本研究算法通過比較認知用戶的信道使用情況來權衡頻譜分配公平性,進而使系統公平性有了顯著提高.

圖4 3種算法下認知用戶數與算法網絡公平性關系比較

圖5為3種算法下認知用戶數與收斂時迭代次數關系比較.由圖5可知:由于筆者在蟻群算法中引入了時間效率這一個量化因子,所以使多態蟻群算法的收斂速度明顯增加,從而節約了時間,節省了認知用戶的搜索時間,使認知用戶能更快速地接入可用信道.

圖5 3種算法下認知用戶數與收斂時迭代次數關系比較

圖6為3種算法下可用信道數與系統吞吐量關系比較.由圖6可知,當可用信道數增多時,系統吞吐量越來越大.本研究算法在加快收斂速度的同時,使系統吞吐量也顯著增加,彌補了其他兩種算法在系統吞吐量方面的不足,改善了系統整體性能.

圖6 3種算法下可用信道數與系統吞吐量關系比較

5 結 論

本研究算法在偵查素和信息素方面進行了調整,得到一種基于時間效率的認知無線電頻譜分配方案.在考慮偵查蟻偵查效益高的路徑同時,動態考慮頻譜接入時間的消耗,在偵查素的揮發上做了調整,使原有的信息素改變機制得到調整,在考慮網絡效益的同時兼顧了時間開銷.以最大網絡公平性和網絡收益總和作為目標函數的仿真試驗表明:改進的基于時間效率的多態蟻群算法與傳統蟻群算法、量子遺傳算法相比,可有效加快頻譜分配速度,增加網絡效益,降低認知用戶間的競爭,提升系統公平性.下一階段的研究,將在本研究基礎上,從頻譜分配時間的角度考慮,對算法的觀測值和轉移概率加以改進,以達到全局的最優分配效率.