基于多態(tài)蟻群優(yōu)化算法的認(rèn)知無線電動(dòng)態(tài)頻譜接入策略

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

(1. 東北電力大學(xué) 現(xiàn)代電力系統(tǒng)仿真控制與綠色電能新技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室, 吉林 吉林 132012; 2. 東北電力大學(xué) 電氣工程學(xué)院, 吉林 吉林 132012)

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

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

1 頻譜分配模型

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

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

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

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

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

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

(1)

2 基于蟻群的頻譜分配算法的轉(zhuǎn)移概率建立

2.1 蟻群算法相關(guān)參量和規(guī)則

1) 節(jié)點(diǎn)為螞蟻可能訪問的每一個(gè)認(rèn)知用戶.

2) 移動(dòng)路徑為分配給用戶的一個(gè)信道.

3) 螞蟻訪問的節(jié)點(diǎn)數(shù)即為認(rèn)知用戶的個(gè)數(shù)N,用編號(hào)n表示.信道總數(shù)為M,用編號(hào)m表示.

4) 螞蟻的個(gè)數(shù)可用X來表示,迭代次數(shù)用ξ來表示.

5) 干擾約束條件決定螞蟻經(jīng)過節(jié)點(diǎn)時(shí)釋放信息素的多少、螞蟻到達(dá)該節(jié)點(diǎn)時(shí)能獲得的信道效益和螞蟻所經(jīng)歷路線的長短及螞蟻能否到達(dá)終點(diǎn).

6) 每個(gè)認(rèn)知用戶擁有同樣的螞蟻數(shù)量,即每個(gè)認(rèn)知用戶成為源節(jié)點(diǎn)的概率相同,且每個(gè)節(jié)點(diǎn)不會(huì)被相同的螞蟻重復(fù)經(jīng)過.

2.2 轉(zhuǎn)移概率建立過程

2.2.1初始化參數(shù)的設(shè)置

設(shè)置的參數(shù)包括迭代次數(shù)和節(jié)點(diǎn)螞蟻個(gè)數(shù).可用信道矩陣L和效益矩陣C是動(dòng)態(tài)調(diào)節(jié)矩陣,每個(gè)螞蟻一旦位置變化,這兩個(gè)矩陣便會(huì)自動(dòng)調(diào)節(jié)數(shù)值.對(duì)禁忌表進(jìn)行參數(shù)設(shè)定,對(duì)螞蟻?zhàn)哌^的每個(gè)節(jié)點(diǎn)進(jìn)行記憶,且每只螞蟻只能走過相同的節(jié)點(diǎn)一次.信息素矩陣是TN×M×ξ.

2.2.2信道分配

(2)

1) 螞蟻行為判斷.螞蟻行動(dòng)函數(shù)決定螞蟻下一步行動(dòng),判斷準(zhǔn)則如下:

(3)

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

2) 螞蟻轉(zhuǎn)移概率.螞蟻行動(dòng)未終止時(shí)根據(jù)公式選下一節(jié)點(diǎn),為了保證路徑的多樣性,螞蟻的行動(dòng)既要考慮信息素,同時(shí)又要考慮觀測值,觀測值是和消耗與干擾有關(guān)的函數(shù),即

(4)

DLn,m為用戶n使用信道m(xù)時(shí)的信道切換時(shí)延Dswitching,ln,m與排隊(duì)時(shí)延Dqueueing,ln,m之和,其公式為

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

(5)

Dswitching,ln,m為節(jié)點(diǎn)n從前一信道k接入下一信道所產(chǎn)生的切換時(shí)延.計(jì)算公式為

(6)

但是,次用戶j可能正在使用信道m(xù),所以需要等待次用戶j不再使用信道m(xù),由此產(chǎn)生排隊(duì)等候時(shí)延Dqueueing,ln,m,即

(7)

由此得到轉(zhuǎn)移概率公式:

(8)

式中:N體現(xiàn)螞蟻接下來可能經(jīng)過的所有節(jié)點(diǎn)數(shù),禁忌表中的元素不包含在N中;α和β為權(quán)重因子,分別代表信息素和信道效益的相對(duì)重要程度;tn,m,ξ代表信息素矩陣的元素,用以表達(dá)螞蟻在第ξ次迭代時(shí)用戶n在信道m(xù)處釋放的信息素多少.

3) 選擇后繼用戶節(jié)點(diǎn).螞蟻的每一步移動(dòng),代表解的一個(gè)可行路徑,螞蟻下一步移動(dòng)到哪個(gè)節(jié)點(diǎn)由以下公式?jīng)Q定:

(9)

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

若g

3 改進(jìn)的基于時(shí)間效率的信息素分配方法

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

(10)

式中:Q為信息素的強(qiáng)度;d′為螞蟻訪問的節(jié)點(diǎn)個(gè)數(shù)，個(gè).

(11)

式中:τi為螞蟻到達(dá)第i節(jié)點(diǎn)所經(jīng)歷的時(shí)間,在本算法中,螞蟻每到達(dá)一個(gè)節(jié)點(diǎn),時(shí)間重置,并記錄螞蟻從上一節(jié)點(diǎn)出發(fā)到達(dá)當(dāng)前節(jié)點(diǎn)的時(shí)間;τ為循環(huán)過程經(jīng)歷的總時(shí)間.

則有

(12)

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

(13)

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

(14)

當(dāng)一只螞蟻停在某個(gè)節(jié)點(diǎn)不再繼續(xù)移動(dòng)時(shí),算法的循環(huán)結(jié)束.螞蟻移動(dòng)過程中,記錄到達(dá)每一個(gè)節(jié)點(diǎn)的時(shí)間τ.根據(jù)螞蟻路線和時(shí)間,在式(14)基礎(chǔ)上對(duì)信息素矩陣中各元素進(jìn)一步更新:

(15)

傳統(tǒng)的蟻群算法是將信息素按螞蟻所經(jīng)歷的節(jié)點(diǎn)數(shù)平均分配給每一個(gè)節(jié)點(diǎn),即Q/dn.通過該公式,按照螞蟻通過信道m(xù)到達(dá)每一個(gè)節(jié)點(diǎn)的時(shí)間,將信息素分配給每一個(gè)節(jié)點(diǎn),時(shí)間少的分配信息素多,時(shí)間多的分配信息素少.

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

(16)

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

(17)

在完成全局信息素更新后,將所有節(jié)點(diǎn)信息素進(jìn)行比較,按照信息素大小順序來分配信道.即

(18)

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

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

圖1 算法流程圖

4 試驗(yàn)仿真及結(jié)果分析

首先進(jìn)行場景的設(shè)置.設(shè)定螞蟻訪問的區(qū)域?yàn)橐粋€(gè)N×M的點(diǎn)陣空間,其中有M個(gè)可用信道提供認(rèn)知用戶接入,每個(gè)授權(quán)用戶都有固定的保護(hù)范圍.當(dāng)授權(quán)用戶接入信道后,認(rèn)知用戶再準(zhǔn)備接入.

仿真設(shè)定區(qū)域?yàn)橐粋€(gè)30×30的網(wǎng)格區(qū)域,存在20個(gè)認(rèn)知用戶,可提供給認(rèn)知用戶使用的信道有30個(gè).認(rèn)知用戶先不進(jìn)行任何行動(dòng),當(dāng)主用戶未對(duì)其授權(quán)頻段進(jìn)行使用時(shí),認(rèn)知用戶根據(jù)分配的頻譜乘機(jī)接入到該頻譜.每個(gè)認(rèn)知用戶的干擾范圍d為[3,6].根據(jù)上述參數(shù)能夠計(jì)算出可用矩陣L、干擾矩陣C和效益矩陣B.設(shè)定搜索蟻數(shù)量X=25只,最大迭代次數(shù)為ξmax=100次,信息素?fù)]發(fā)因子ρ=0.11,信息素指數(shù)設(shè)為1,啟發(fā)式信息指數(shù)為3,初始信息量c=5,信息素強(qiáng)度Q=2.仿真進(jìn)行50次獨(dú)立試驗(yàn),并記錄結(jié)果,且每次試驗(yàn)時(shí)的矩陣L,B和C均隨機(jī)生成.

圖2為3種算法下可用信道數(shù)與網(wǎng)絡(luò)收益總和的關(guān)系比較.由圖2可知:選取本研究中改進(jìn)的算法進(jìn)行頻譜分配時(shí),網(wǎng)絡(luò)效益總和高于另外兩種算法;隨著可用信道m(xù)的數(shù)量不斷增大,本研究算法的網(wǎng)絡(luò)收益總和始終高于AOC算法和QGA算法.這是由于引入的時(shí)間參數(shù)對(duì)信道的效益起到了很好的調(diào)節(jié)作用,減少了認(rèn)知用戶的搜索時(shí)間,繼而提高了系統(tǒng)網(wǎng)絡(luò)收益.

圖2 3種算法下可用信道數(shù)與網(wǎng)絡(luò)收益總和的關(guān)系比較

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

圖3 3種算法下認(rèn)知用戶數(shù)與網(wǎng)絡(luò)收益總和的關(guān)系比較

圖4為3種算法下認(rèn)知用戶數(shù)與算法網(wǎng)絡(luò)公平性關(guān)系比較.由圖4可知,認(rèn)知用戶數(shù)增多時(shí),競爭也隨之增大.本研究算法通過比較認(rèn)知用戶的信道使用情況來權(quán)衡頻譜分配公平性,進(jìn)而使系統(tǒng)公平性有了顯著提高.

圖4 3種算法下認(rèn)知用戶數(shù)與算法網(wǎng)絡(luò)公平性關(guān)系比較

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

圖5 3種算法下認(rèn)知用戶數(shù)與收斂時(shí)迭代次數(shù)關(guān)系比較

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

圖6 3種算法下可用信道數(shù)與系統(tǒng)吞吐量關(guān)系比較

5 結(jié) 論

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