基于蛙跳博弈優(yōu)化算法的認(rèn)知頻譜分配*

蔣孜浩秦寧寧

(1.江南大學(xué)輕工過程先進(jìn)控制教育部重點(diǎn)實(shí)驗(yàn)室，江蘇 無錫 214122；2.南京航空航天大學(xué)電磁頻譜空間認(rèn)知?jiǎng)討B(tài)系統(tǒng)工信部重點(diǎn)實(shí)驗(yàn)室，江蘇 南京 211106)

認(rèn)知無線傳感器網(wǎng)絡(luò)(Cognitive Radio Sensor Networks，CRSN)將認(rèn)知無線電(Cognitive Radio，CR)技術(shù)引入無線傳感器網(wǎng)絡(luò)，使每個(gè)傳感器節(jié)點(diǎn)擁有頻譜感知和動(dòng)態(tài)接入頻譜的能力。隨著頻譜資源日益受限的發(fā)展現(xiàn)狀，為保證主用戶(Primary user，PU)優(yōu)先使用頻譜，勢(shì)必需要對(duì)作為次用戶(Secondary user，SU)的網(wǎng)絡(luò)節(jié)點(diǎn)進(jìn)行必要的頻譜的限制?；贑R技術(shù)機(jī)會(huì)利用頻譜特性，在頻譜受限情況下CRSN相比于傳統(tǒng)的無線傳感器網(wǎng)絡(luò)(Wireless Sensor Networks，WSN)可以有效減少信道碰撞和競(jìng)爭(zhēng)所造成的時(shí)延和能耗[1]。SU在認(rèn)知到頻譜空閑時(shí)才有占用的權(quán)限，目前頻譜認(rèn)知可使用能量檢測(cè)(Energy Detection，ED)、匹配濾波器檢測(cè)(Matched Filter Detection，MFD)和靜態(tài)循環(huán)特征檢測(cè)(Cyclostationary Feature Detection，CFD)等方式。

系統(tǒng)吞吐量低是CRSN受限于頻譜的體現(xiàn)，合理的頻譜分配方案可以明顯增加系統(tǒng)吞吐量。根據(jù)計(jì)算主體的不同，CRSN中頻譜分配方式可分為集中式和分布式。集中式方案依靠基站收集各個(gè)節(jié)點(diǎn)的數(shù)據(jù)來分配全局的頻譜[2]，分布式分配方案一般以一個(gè)集群或節(jié)點(diǎn)為主體，通過與鄰居的集群或節(jié)點(diǎn)互換收集的數(shù)據(jù)并自行選擇頻譜[3]?；赑U頻譜占用的差異，頻譜分配可區(qū)分為固定與動(dòng)態(tài)兩種形式，前者主要應(yīng)用于頻譜資源較為豐富的網(wǎng)絡(luò)，將頻譜分配給難以對(duì)主用戶產(chǎn)生干擾的節(jié)點(diǎn)，分得頻譜后的節(jié)點(diǎn)短期內(nèi)不會(huì)改變。目前已有許多研究人員基于博弈論[4]、圖論染色[5]、群優(yōu)化算法[6]等方法對(duì)其開展研究。后者是應(yīng)對(duì)頻譜資源極其受限場(chǎng)景下的動(dòng)態(tài)頻譜分配方案，通常會(huì)給一個(gè)節(jié)點(diǎn)分配幾段頻譜，并使用各類智能算法計(jì)算頻譜的時(shí)間使用片段[7-8]。針對(duì)PU位置固定場(chǎng)景，為不失一般性，掌控全局頻譜分配，提升網(wǎng)絡(luò)吞吐量，論文聚焦于集中式的固定頻譜分配方案。

CRSN受限于頻譜數(shù)量與路由，有限的頻譜數(shù)量在降低SU通信靈活性的同時(shí)，也帶來了網(wǎng)絡(luò)熱區(qū)與路由的多枝隱患。路由是固定頻譜分配的基礎(chǔ)，而傳統(tǒng)的WSN路由受節(jié)點(diǎn)隨機(jī)分布與頻譜的影響，無法滿足CRSN網(wǎng)絡(luò)的吞吐和延遲要求，所以傳統(tǒng)WSN路由不適合直接用于CRSN。因此在兼顧網(wǎng)絡(luò)吞吐量和通信限制的同時(shí)，如何構(gòu)建路由與頻譜分配方案將至關(guān)重要[9-10]。

針對(duì)頻譜局限與路由困難對(duì)CRSN系統(tǒng)吞吐的不利影響，論文提出了基于蛙跳博弈優(yōu)化算法(Improve Swarm optimization method based on Leapfrog Game，ISLG)的認(rèn)知頻譜分配方案。使用自適應(yīng)的調(diào)節(jié)路由優(yōu)化網(wǎng)絡(luò)負(fù)載，解決節(jié)點(diǎn)分布不合理所導(dǎo)致的網(wǎng)絡(luò)熱區(qū)和局部多枝問題。在此路由基礎(chǔ)上，使用ISLG搜尋最佳頻譜分配方案，通過蛙跳博弈(Leapfrog Game，LG)對(duì)基礎(chǔ)尋優(yōu)算法的分配群進(jìn)行再移動(dòng)，以尋找最佳頻譜分配方案。通過仿真比較分析，LG可以顯著加強(qiáng)各類群體尋優(yōu)算法的搜索性能，ISLG相比未改進(jìn)前算法在頻譜分配問題的求解上有著更高的性能，可以有效提高系統(tǒng)總吞吐。

1 系統(tǒng)模型及問題描述

1.1 網(wǎng)絡(luò)模型

給定一個(gè)CRSN網(wǎng)絡(luò)，其中隨機(jī)分布著M個(gè)PU與N個(gè)SU，其中PU＝{pum｜m＝1，2，…，M}，SU＝{sun｜n＝1，2，…，N}，并且存在一個(gè)基站BS?；陬l分復(fù)用與PU均等原則，將網(wǎng)絡(luò)中的頻譜資源均勻分割成M個(gè)信道C＝{cm｜m＝1，2，…，M}，并對(duì)應(yīng)分配給每個(gè)PU，其中PU信號(hào)功率符合正態(tài)分布且均值為0。

為滿足節(jié)點(diǎn)信道固定的需求，在單向多跳路由中的所有節(jié)點(diǎn)，不得不使用指定的同一信道，降低頻譜利用率的同時(shí)也增加了網(wǎng)絡(luò)沖突。因此，論文采用一種區(qū)分接收與發(fā)送的工作方式，將一個(gè)節(jié)點(diǎn)的收發(fā)工作分給兩根天線完成，實(shí)現(xiàn)固定頻譜的吞吐量擴(kuò)大，平衡單一信道下的互擾與沖突浪費(fèi)。

節(jié)點(diǎn)區(qū)分接收與發(fā)送的工作方式，可在保證發(fā)送信道與其下跳節(jié)點(diǎn)接收信道相同的情況下，解除其下跳節(jié)點(diǎn)的發(fā)送信道選擇限制。SU的接收與發(fā)送信道分別為互不相同的獨(dú)立信道，這讓多跳網(wǎng)絡(luò)整體呈現(xiàn)出一種以信道為區(qū)分標(biāo)志的類分簇結(jié)構(gòu)，如此便實(shí)現(xiàn)了部分節(jié)點(diǎn)的綁定，有助于進(jìn)行信道分配。構(gòu)成的簇彼此之間可具有相同節(jié)點(diǎn)，但除以基站作為下跳節(jié)點(diǎn)的簇，不會(huì)有兩個(gè)簇的下跳節(jié)點(diǎn)相同。

如圖1中su1、su2、su3，就形成了一個(gè)簇，其包含了多個(gè)上跳節(jié)點(diǎn){su2，su3}與一個(gè)下跳節(jié)點(diǎn)su1，其中各個(gè)上跳節(jié)點(diǎn)基于頻分復(fù)用原則共享信道。

圖1 類簇下的頻分復(fù)用

簇內(nèi)節(jié)點(diǎn)綁定之后，可以將原本對(duì)節(jié)點(diǎn)信道分配問題轉(zhuǎn)換為對(duì)簇的信道分配問題。為降低簇間干擾，在信道分配中臨近簇之間需盡量分配不同的信道。顯然在路由確定后，各個(gè)簇也可隨之確定，則存在的K個(gè)簇構(gòu)成的集合L可描述如下:

式中:k＝1，2，…，K；lk(0)為簇lk的唯一下跳節(jié)點(diǎn)；lk(i)∈SU，1≤i≤K則是簇lk中的上跳節(jié)點(diǎn)。

在網(wǎng)絡(luò)信息較為固定的情況下，一次頻譜的分配通?？梢猿掷m(xù)較長時(shí)間，因此在此類情況下分布式的頻譜分配方式相比集中式的分配方案沒有太多優(yōu)勢(shì)，反而因?yàn)闆]有全局信息而使得分配效果較差。

網(wǎng)絡(luò)路由的初始建立過程中，每個(gè)節(jié)點(diǎn)都設(shè)置有相同的信道，通過此信道，基站可以建立起路由。在基礎(chǔ)路由建立后，便可以進(jìn)行節(jié)點(diǎn)之間的信道信息收集工作，用于信道分配。在路由初始化的過程中，不管是分布式還是集中式的頻譜分配方案，最終都會(huì)建立起一條可以聯(lián)通基站的路由。

若是采取分布式的分配方案，在本文的網(wǎng)絡(luò)條件下，節(jié)點(diǎn)若想多獲取鄰近節(jié)點(diǎn)的信息，則需要更改信道才可以去相關(guān)節(jié)點(diǎn)進(jìn)行信息的交互，則有違本文初衷，因此選擇集中式的分配方案。

1.2 PU模型與信道檢測(cè)

基于已知的PU位置與通信信息，CRSN網(wǎng)絡(luò)中每個(gè)PU占用信道的行為都可類比為一個(gè)馬爾可夫過程[11]。

節(jié)點(diǎn)的認(rèn)知傳輸模型如圖2中所示，對(duì)于每個(gè)時(shí)長為T的時(shí)隙，SU會(huì)將其分為認(rèn)知與傳輸兩個(gè)階段，其中每個(gè)時(shí)隙開始的τ時(shí)間內(nèi)為認(rèn)知階段，剩余的T-τ時(shí)間則被作為傳輸階段。在認(rèn)知階段pum占用信道cm，并以pm和qm分別表示cm在當(dāng)前時(shí)隙上信道狀態(tài)由空閑轉(zhuǎn)為占用和由占用轉(zhuǎn)為空閑的概率。只有當(dāng)信道空閑時(shí)，SU才有機(jī)會(huì)進(jìn)行傳輸，因此信道cm的理論傳輸占比Dm為:

圖2 SU認(rèn)知傳輸模型

對(duì)于qm和pm的確定，可以通過能量檢測(cè)的方式進(jìn)行測(cè)定。能量檢測(cè)是最常見的信道占用檢測(cè)方法[12]，通過統(tǒng)計(jì)PU信號(hào)一段時(shí)間內(nèi)的能量并與預(yù)設(shè)閾值對(duì)比，可以判斷PU對(duì)于頻譜的占用情況。在本文中，PU的占空比可以通過各個(gè)節(jié)點(diǎn)對(duì)PU的認(rèn)知信息在基站的融合以求取。該方案復(fù)雜度低且無需知道檢測(cè)信道中的信號(hào)細(xì)節(jié)，但檢測(cè)結(jié)果易受到環(huán)境噪聲與PU信號(hào)的影響，在低信噪比的情況下，檢測(cè)結(jié)果的可信度會(huì)顯著降低。

在時(shí)長τ內(nèi)SU對(duì)信道能量采樣了NT次，PU 的發(fā)射信號(hào)xPU服從正態(tài)分布，則在SU處接收的對(duì)應(yīng)信道中信號(hào)x也服從正態(tài)分布，由于SU具有認(rèn)知能力，因此其可計(jì)算得到所接收PU的信號(hào)強(qiáng)度方差。根據(jù)已知的呈正態(tài)分布的網(wǎng)絡(luò)噪聲方差，可得sun認(rèn)知cm檢測(cè)概率。

式中:Q(·)表示正態(tài)分布右尾函數(shù)；β為檢測(cè)因子，其取值區(qū)間為[0，1]；。

可計(jì)算得sun使用cm信道的理論傳輸時(shí)長占比gn，m:

考慮到gn，m主要受到信噪比的限制，因此可通過增大信噪比的方式增大檢測(cè)的成功率?；谒ヂ鋫鞑ツＰ?，可知距離越近其接收功率越高，接收信噪比也越高，因此在網(wǎng)絡(luò)節(jié)點(diǎn)無法移動(dòng)的情況下，頻譜分配方案會(huì)趨向于給SU分配距離較近PU的信道。

1.3 問題規(guī)劃

在將頻譜資源劃分為多條可用信道的情況下，可將CRSN的頻譜分配問題抽象為一個(gè)基于染色理論的信道分配模型。若將各節(jié)點(diǎn)發(fā)送信道抽象為色塊，則可將鄰近節(jié)點(diǎn)選擇不同發(fā)送信道的問題轉(zhuǎn)化為相鄰色塊的染色問題。

當(dāng)sun檢測(cè)的pum距離其越近時(shí)，接收信號(hào)強(qiáng)度越高，則sun在cm上的信道容量en，m以及sun對(duì)cm認(rèn)知成功率Qn，m也越高?？紤]到每個(gè)時(shí)隙中[0，τ]與[τ，T]的時(shí)間分離，[0，τ]時(shí)間段不會(huì)產(chǎn)生節(jié)點(diǎn)間傳輸干擾。但在[τ，T]時(shí)間段，選擇相同信道的節(jié)點(diǎn)之間不可避免會(huì)產(chǎn)生節(jié)點(diǎn)間傳輸干擾，降低系統(tǒng)吞吐量。

sun在cm上的信道容量en，m，如公式(8)所示:

式中:lk是節(jié)點(diǎn)sun作為上跳節(jié)點(diǎn)對(duì)應(yīng)簇；an＝｜lk｜-1是簇lk中上跳節(jié)點(diǎn)個(gè)數(shù)；1/(anai)是節(jié)點(diǎn)sun與sui的信道重疊期望比；B是信道帶寬；rn，i則是同信道中節(jié)點(diǎn)sui對(duì)sun的干擾，可由節(jié)點(diǎn)sun事先感知得到。

節(jié)點(diǎn)sun在信道cm上的吞吐量bn，m可計(jì)算如下:

由于熱區(qū)效應(yīng)，考慮離基站越近的節(jié)點(diǎn)所需信道容量更大。因此在每個(gè)節(jié)點(diǎn)數(shù)據(jù)量相同的前提下，為保證網(wǎng)絡(luò)整體的吞吐均衡，需首先滿足轉(zhuǎn)發(fā)數(shù)據(jù)較多節(jié)點(diǎn)的吞吐需求。為此在全局收益的計(jì)算中設(shè)置各個(gè)節(jié)點(diǎn)有吞吐權(quán)重wn，以在算法中提高數(shù)據(jù)量高節(jié)點(diǎn)的信道分配優(yōu)先級(jí)，其值正比于其期望的數(shù)據(jù)發(fā)送量。wn以需發(fā)送數(shù)據(jù)量與自身數(shù)據(jù)量的比值表征，存在有節(jié)點(diǎn)權(quán)重矩陣W:

由于路由的綁定效果，一個(gè)簇中所有上跳節(jié)點(diǎn)所選信道相同，則對(duì)單個(gè)SU的發(fā)送信道分配可轉(zhuǎn)換為對(duì)于簇中上跳節(jié)點(diǎn)的發(fā)送信道分配，則信道分配矩陣X可如式(9)表示，其中xk為lk所選信道編號(hào)，即cxk為lk選擇信道。

在各個(gè)簇的信道選擇約束下的最大化全局吞吐量收益U的問題則可轉(zhuǎn)換為式(10)與(11):

可見lbk，xk同時(shí)受到簇lk所選信道與其他簇的信道選擇的影響，可映射為圖染色中顏色選擇沖突問題。若以遍歷的方式計(jì)算最佳的信道分配，意味著需要計(jì)算MK次才能確定，這顯然是一個(gè)NP問題。于此論文提出基于蛙跳博弈優(yōu)化算法的認(rèn)知頻譜分配，在有限時(shí)間下，盡可能獲取最優(yōu)的頻譜分配方案。同時(shí)輔以路由層的優(yōu)化以降低信道分配后沖突的可能性。

2 基于蛙跳博弈優(yōu)化算法的認(rèn)知頻譜分配

2.1 基于自適應(yīng)PU數(shù)量路由的節(jié)點(diǎn)分簇

路由是頻譜分配的基礎(chǔ)，一般WSN路由直接移植在CRSN中易產(chǎn)生多枝路由與過多單跳直達(dá)基站的熱區(qū)節(jié)點(diǎn)，這會(huì)明顯影響系統(tǒng)吞吐量。

考慮到三角剖分擁有最大化最小角的特性[14]，運(yùn)用到網(wǎng)絡(luò)路由的形成中，可以減少網(wǎng)絡(luò)中鈍角的產(chǎn)生進(jìn)而減少長邊產(chǎn)生，可降低路由中遠(yuǎn)距單跳路徑出現(xiàn)的概率。由此，論文提出了一種基于三角剖分分層的自適應(yīng)PU數(shù)量路由(Adaptive PU Quantity Routing Based on Triangulation Layering，APRT)，基于最大化最小角等特點(diǎn)限制路由調(diào)度，增加節(jié)點(diǎn)選擇鏈路時(shí)距離與空間的合理性，因此可緩解網(wǎng)絡(luò)中局部沖突的產(chǎn)生。

由于單基站路由的匯聚特性[15]，網(wǎng)絡(luò)中多枝路由的產(chǎn)生不可避免，且過多節(jié)點(diǎn)基于頻分復(fù)用共用一條信道時(shí)，也會(huì)導(dǎo)致相關(guān)節(jié)點(diǎn)的吞吐量顯著降低。為使路由中枝葉分配更為均衡，設(shè)置APRT網(wǎng)絡(luò)最多產(chǎn)生兩枝節(jié)點(diǎn)，以路由枝葉長度的增加換取路由枝杈的減少，可極大增加局部的吞吐量。

基站同時(shí)作為最大的多枝節(jié)點(diǎn)與最大的數(shù)據(jù)匯聚節(jié)點(diǎn)極易引起周圍的熱區(qū)問題，作為全局吞吐的匯聚中心，熱區(qū)節(jié)點(diǎn)的吞吐需求遠(yuǎn)在其余節(jié)點(diǎn)之上，因此在信道分配中，應(yīng)首先滿足熱區(qū)節(jié)點(diǎn)的需求。

基站可同時(shí)接收所有信道數(shù)據(jù)，因此熱區(qū)節(jié)點(diǎn)不必局限于復(fù)用一條信道，即熱區(qū)節(jié)點(diǎn)單跳至基站的信道可以相互不同。若嚴(yán)格限制APRT中單跳到基站的節(jié)點(diǎn)數(shù)量小于等于網(wǎng)絡(luò)中信道的數(shù)量，則可滿足熱區(qū)節(jié)點(diǎn)間選用的上跳信道互不相同的條件，這保證了熱區(qū)中各個(gè)節(jié)點(diǎn)的吞吐性能，同時(shí)也可以避免熱區(qū)沖突。由于信道數(shù)量是固定的，因此，上述條件下，只能限制熱區(qū)節(jié)點(diǎn)的數(shù)量。

如此，APRT中限制多枝節(jié)點(diǎn)與熱區(qū)節(jié)點(diǎn)數(shù)量的規(guī)則如式(12)與式(13)所示。

式中:A＝{ak＝｜lk｜-1｜k＝1，2，…，K}為L對(duì)應(yīng)的簇中上跳節(jié)點(diǎn)數(shù)量矩陣；｜·｜表示取集合的元素?cái)?shù)量。

APRT路由的生成可分為分層與分配兩步。首先將所有節(jié)點(diǎn)包括基站進(jìn)行三角剖分，依據(jù)剖分圖進(jìn)行分層。其次，從最內(nèi)層開始，每個(gè)節(jié)點(diǎn)依據(jù)規(guī)則尋找最近的下一層節(jié)點(diǎn)作為自己的上跳節(jié)點(diǎn)。

2.2 基于蛙跳博弈的認(rèn)知頻譜分配

在對(duì)節(jié)點(diǎn)進(jìn)行分簇后，對(duì)節(jié)點(diǎn)的信道分配問題便可轉(zhuǎn)換為對(duì)簇的信道分配問題，這大大降低了問題的復(fù)雜度。

根據(jù)青蛙在石塊上覓食時(shí)的種群分布變化，有人提出了混合蛙跳算法(Shuffled Frog Leaping Algorithm，SFLA)[13]。SFLA中粒子跳躍的策略選擇有如下特征:對(duì)于下次跳躍粒子的選擇與適應(yīng)度相關(guān)且呈現(xiàn)偽順序性，粒子的跳躍選擇呈現(xiàn)無序性，粒子的收斂具有規(guī)律性。

蛙跳博弈(Leapfrog Game，LG)結(jié)合了SFLA的特征并使用合作博弈進(jìn)行策略選擇。其中合作博弈遵守每次策略的選擇都必須符合博弈者只能作出對(duì)自己更好且不使其他參與者變差的規(guī)則，這可以保證在有限輪次博弈下，一定會(huì)收斂到帕累托最優(yōu)[16]。

SFLA的策略與思想主要突出于對(duì)于博弈者與策略的偽隨機(jī)性，而偽隨機(jī)性則可以在保證不同的初始解擁有唯一的帕累托最優(yōu)的條件下，增加博弈的無序性。這使得基于LG可以在頻譜分配問題中降低問題的復(fù)雜度以獲得較好的全局搜索能力。同時(shí)基于上述合作博弈理論下的LG可以在保證效果的前提下限制算法的復(fù)雜度。

對(duì)于某次信道分配，可將每個(gè)簇作為一只青蛙，信道代表可跳上的石頭，簇吞吐收益lbk，m則表征青蛙lk處于石頭cm的心情。每只青蛙擁有各自獨(dú)立的隨機(jī)跳躍序列fk，該序列可以增加蛙跳的隨機(jī)性與蛙跳后解的離散程度，這降低相同跳躍順序下青蛙跳躍時(shí)出現(xiàn)的信道選擇沖突概率。對(duì)于一次信道分配，各個(gè)簇lk的隨機(jī)跳躍序列fk可組成如下跳躍矩陣F:

式中:fk內(nèi)元素需相互不重復(fù)，rand(M)為取[1，M]的隨機(jī)整數(shù)，用以對(duì)應(yīng)信道編號(hào)。

在信道分配中，LG的偽代碼如下:

Algorithm 1 LG Input:隨機(jī)信道分配矩陣X，隨機(jī)蛙跳矩陣F，節(jié)點(diǎn)權(quán)重矩陣W，簇集合L，網(wǎng)絡(luò)信道數(shù)量M Output:蛙跳后信道分配矩陣X Line1 S＝{}；K＝L.szie Line2 while S.szie≠K Line3 XK＝X %備份X Line4 u＝lb(X)Line5 k＝chooseMin(b(X)，S)Line6 for i＝1∶M Line7 X[k]＝F[k，i] %改變信道Line8 if u-lb(X)＞＝zeros(1，K)Line9u＝lb(X)Line10 break %退出for循環(huán)Line11 else Line12 X＝XK %回退Line13 S.add(lk)Line14 end if Line15 end for Line16 end Line17 return X

在信道分配已知的情況下，式(11)可直接計(jì)算得各個(gè)簇的吞吐收益，算法中b(X)表示基于式(7)求解所有簇中下跳節(jié)點(diǎn)的信道容量，并按順序組成1×K的矩陣；lb(X)對(duì)應(yīng)式(11)，即求解所有簇的吞吐收益，其輸出為1×K的矩陣；chooseMin(b，S)表示依據(jù)b與S選擇吞吐最小且不屬于S的簇編號(hào)；Line8判斷改變前后吞吐收益值，需滿足收益變好，且其他簇收益不變差的條件。

2.3 基于蛙跳博弈優(yōu)化算法的認(rèn)知頻譜分配

若僅使用LG進(jìn)行信道分配，可知其效果受限于初始解。而標(biāo)準(zhǔn)的群優(yōu)化算法則難以在此類高維度的離散問題中尋找到全局最優(yōu)解，且極易陷入局部最優(yōu)解[8]。

針對(duì)上述問題，本文提出基于蛙跳博弈的改進(jìn)群體尋優(yōu)方法(ISLG)來尋找最優(yōu)的頻譜分配方案。通過LG對(duì)群尋優(yōu)算法中的各個(gè)分配集進(jìn)行再移動(dòng)，以在單次群優(yōu)化迭代中實(shí)現(xiàn)低復(fù)雜度的再尋優(yōu)。在單次智能算法的迭代中，ISLG以蛙跳博弈確定群優(yōu)化算法中各個(gè)分配集對(duì)應(yīng)的局部最優(yōu)解，并將其作為對(duì)應(yīng)分配集的收益，隨后執(zhí)行下一輪的更新，在此將所有基于LG改進(jìn)群優(yōu)化的算法統(tǒng)稱為ISLG。

ISLG類算法實(shí)現(xiàn)頻譜分配的偽代碼如下:

Algorithm 2 ISLG Input:粒子群數(shù)量num，最大迭代次數(shù)Iteration，隨機(jī)信道分配矩陣X，隨機(jī)蛙跳矩陣F，節(jié)點(diǎn)權(quán)重矩陣W，簇集合L，網(wǎng)絡(luò)信道數(shù)量M，簇?cái)?shù)量K Output:頻譜分配最優(yōu)解X_BEST Line1 X＝initializeX()；V＝initializeV()Line2 XX＝X %粒子的歷史最佳位置Line3 u＝U(X)；Line4 while(Iteration＞＝0)Line5 X＝X+V %位置更新Line6 XL＝LG[round(X)，F(xiàn)，W，L，M]Line7 for i＝1∶K Line8 XX[i，:]＝u[i]＞U(XL)[i]? XX[i，:]:X[i，:]Line9 end for Line10 u＝U(XL) %蛙跳后收益Line11 [X_BEST，best]＝Max XL(XL，u)Line12 X[best]＝X_BEST Line13 V＝updateV()Line14 Iteration--Line15 end Line16 return X_BEST

Line1為對(duì)位置與速度的初始化，initializeX()輸出為num×K的矩陣X，其每一行都是一次隨機(jī)信道分配；LG(·)為蛙跳函數(shù)，其輸入包含num行的信道分配矩陣X，輸出為num行的蛙跳后分配矩陣XL；round(·)為取整函數(shù)；Line7-Line10為對(duì)歷史最佳位置矩陣XX的更新，其中Line8為三目判斷式；Max XL(XL，u)函數(shù)輸出為XL中收益最高的一解X_BEST與X_BEST對(duì)應(yīng)的行號(hào)best；Line12為對(duì)蛙跳結(jié)果的選擇性持久化，ISLG中僅對(duì)最佳解X_BEST進(jìn)行了持久化。

initializeV()為對(duì)粒子速度V的初始化，輸出num×K的矩陣V；updateV()為速度更新函數(shù)。對(duì)于使用不同群優(yōu)化算法進(jìn)行優(yōu)化的ISLG，上述兩函數(shù)的公式也不盡相同，因此不同的ISLG應(yīng)用在頻譜分配上也會(huì)存在效果的差異。

3 仿真及結(jié)果分析

利用MATLAB建立仿真實(shí)驗(yàn)。對(duì)基于蛙跳博弈優(yōu)化算法的認(rèn)知頻譜分配方案進(jìn)行仿真分析。

論文假設(shè)網(wǎng)絡(luò)區(qū)域?yàn)檎叫危珺S處于正中心，SU與PU隨機(jī)播撒在區(qū)域中，信道采用自由空間模型，仿真參數(shù)如表1所示。

表1 仿真參數(shù)設(shè)置

3.1 APRT對(duì)頻譜分配的影響分析

為對(duì)比APRT與WSN中常用的路由在認(rèn)知傳感器網(wǎng)絡(luò)中的網(wǎng)絡(luò)效果。通過APRT與開放最短路徑優(yōu)先路由(Open Shortest Path Firs Routing，OSPF)、距離向量路由(Bellman-Ford Routing，BFR)以及三角剖分分層路由(Triangulate Hierarchical Routing，THR)進(jìn)行對(duì)比，其中THR中節(jié)點(diǎn)簡單選擇歐氏距離最近的上層節(jié)點(diǎn)作為下跳節(jié)點(diǎn)。

以M作為變量，在相同M下，設(shè)置不同的網(wǎng)絡(luò)快照，并使用DPLG分配信道，每輪算法運(yùn)行50次求取平均值。

仿真結(jié)果如圖3所示，可見在M逐漸增加的情況下，4種路由下的全局吞吐收益都呈現(xiàn)上升趨勢(shì)，且逐漸變緩。這是由于M的增加使得節(jié)點(diǎn)的可選信道增多，減少了選擇沖突，進(jìn)而增加全局吞吐。由于單獨(dú)的節(jié)點(diǎn)吞吐存在飽和，因此當(dāng)全局吞吐收益上升到一定程度時(shí)，此時(shí)M再增加也很難提高全局的收益。

圖3 路由吞吐收益對(duì)比

對(duì)比四類路由算法，BFR始終最差，這是因?yàn)锽FR單純以跳數(shù)進(jìn)行約束，導(dǎo)致了某些鏈路的多枝問題極其嚴(yán)重，這使得BFR的收益遠(yuǎn)低于其他3種。OSPF較之BFR的鏈路更為合理一些，但也存在大量的多枝節(jié)點(diǎn)。THR是基于三角剖分的分層路由，在分層后進(jìn)行路由的選擇可以讓網(wǎng)絡(luò)顯得更為均衡，這大大降低了網(wǎng)絡(luò)中多枝節(jié)點(diǎn)的出現(xiàn)概率，使得該路由的效果較BFR與OSPF有了較大提升，顯然基于三角剖分的路由對(duì)于網(wǎng)絡(luò)的優(yōu)化是有效果的。

在4≤M≤5的熱區(qū)受限段可以明顯看到4類路由算法的收益較之全局都顯得極差，一方面的原因是較少的M限制了信道選擇，另一方面則是因?yàn)闊釁^(qū)節(jié)點(diǎn)信道的沖突。APRT雖然也局限于信道數(shù)量的選擇，但由于沒有熱區(qū)沖突的問題，因此較之THR，其曲線在4≤M≤5的上升梯度更平緩，且起點(diǎn)也更高。

3.2 蛙跳博弈的頻譜分配效果分析

3.2.1 時(shí)間復(fù)雜度分析

為分析LG的時(shí)間復(fù)雜度，進(jìn)行如下仿真:在不同的M下隨機(jī)產(chǎn)生1 000個(gè)初始解，找出對(duì)應(yīng)蛙跳博弈中計(jì)算局部收益的次數(shù)，并求其平均計(jì)算次數(shù)，以測(cè)定LG在不同PU數(shù)量下的時(shí)間復(fù)雜度，結(jié)果如表2所示。

表2 LG局部收益計(jì)算次數(shù)與PU數(shù)量關(guān)系表

可見隨著M的增加，LG的中的計(jì)算次數(shù)也在快速上升，且呈現(xiàn)類等比增長的趨勢(shì)。雖然問題的維度隨著PU數(shù)量的上升而上升，但隨M的增加，蛙跳博弈中信道選擇的沖突也大大減少，因此相比于NP問題中解域的指數(shù)增長速度，蛙跳博弈類等比增長的速度顯然是較為緩慢的。

3.2.2 蛙跳博弈頻譜分配效果分析

為分析LG在信道分配上的性能，通過將LG、離散粒子群算法(Discrete particle swarm optimization，DPSO)和離散灰狼算法(Discrete gray Wolf optimization，DGWO)在相同的網(wǎng)絡(luò)快照上進(jìn)行信道分配，以M作為變量對(duì)比性能。設(shè)置DPSO和DGWO的初始粒子和狼群數(shù)量為1 000，在相同M下對(duì)LG、DPSO和DGWO各進(jìn)行50次仿真并取平均值。

仿真結(jié)果如圖4所示，可見隨M的增加三種算法總體呈現(xiàn)出上升趨勢(shì)，但DPSO和DGWO上升趨勢(shì)較為緩慢，甚至出現(xiàn)不同程度的下降。而LG則更為穩(wěn)定，并且其吞吐收益U在M≥9之后優(yōu)于DPSO與DGWO。這是因?yàn)樵贛≥9時(shí)，網(wǎng)絡(luò)中信道的選擇較為充分，此時(shí)LG中蛙跳選擇信道的局限性降低，因此M數(shù)量越高，其收益也越高。而對(duì)于DPSO與DGWO，作為群優(yōu)化算法，在處理此類離散問題上天生具有劣勢(shì)，而M的增加意味著問題復(fù)雜度的提升，因此在搜索力差強(qiáng)人意的情況下，極容易陷入局部最優(yōu)。

圖4 不同PU數(shù)量下LG與群優(yōu)化算法的性能

而在M較小時(shí)，群優(yōu)化算法性能比LG好，且在M＝4時(shí)，使用LG算法的收益明顯低于群優(yōu)化類算法。這是因?yàn)榛趫D染色原理，在排除周圍簇已選信道后，待選簇的信道選擇有極大的局限性，這大大降低了LG的效果，使其難以跳出局部最優(yōu)，因此LG效果極差。

3.3 ISLG的頻譜分配效果分析

根據(jù)3.2.1節(jié)的分析可知蛙跳博弈的性能會(huì)隨著M的增大而增加，各類群優(yōu)化算法則相反，因此引入群優(yōu)化算法輔助LG進(jìn)而增加性能在理論上是可行的，ISLG算法可以分別吸取群優(yōu)化算法與LG的優(yōu)點(diǎn)，在M較大與較小的情況下都獲得良好的表現(xiàn)。

為分析ISLG算法在信道分配上的性能，作以下仿真:將ISLG類算法基于LG改進(jìn)后的蛙跳粒子群算法(An improved DPSO based on LG，DPLG)與蛙跳灰狼算法(An improved DGWO based on LG，DGLG)與改進(jìn)前DPSO與DGWO算法進(jìn)行仿真。在相同的網(wǎng)絡(luò)快照下，設(shè)置不同的M對(duì)優(yōu)化前后的兩種群優(yōu)化算法進(jìn)行仿真對(duì)比?；?.2.1對(duì)時(shí)間復(fù)雜度的分析，為體現(xiàn)時(shí)間復(fù)雜度的公平，在設(shè)置ISLG類算法粒子數(shù)量為num＝10的前提下，設(shè)置優(yōu)化前算法的初始粒子數(shù)等于表2中計(jì)算次數(shù)與num的乘積，且最大迭代次數(shù)為200。對(duì)改進(jìn)前后的兩種算法在不同M下各進(jìn)行50次仿真并取平均值，結(jié)果如圖5所示。

圖5 不同PU數(shù)量下各算法優(yōu)化前后性能

圖5中，4種算法雖然總體效果都隨著M的變大而上升，但DPSO與DGWO顯然沒有ISLG類算法穩(wěn)定，而是呈波動(dòng)上升，此結(jié)果與4.2.2節(jié)的結(jié)論相同，這證明了ISLG可以繼承LG的優(yōu)點(diǎn)以填補(bǔ)群優(yōu)化類算法的缺點(diǎn)。圖6為四種分配算法50次實(shí)驗(yàn)的平均迭代次數(shù)圖，可見ISLG類算法相比改進(jìn)前收斂速度更快，這是因?yàn)镮SLG類算法的尋優(yōu)性能更佳，因此可以快速收斂。基礎(chǔ)群尋優(yōu)算法的平均迭代次數(shù)總體隨著M的增加而增加，而ISLG類算法的平均迭代次數(shù)則不隨M有增加或者減少的趨勢(shì)，這說明隨M增加，ISLG算法的主導(dǎo)者逐漸變成了LG。

圖6 算法的平均迭代次數(shù)

從效果對(duì)比上看，在M＝4時(shí)，ISLG類算法效果不佳。這是由于在M＝4時(shí)，LG的效果較差，導(dǎo)致ISLG算法由對(duì)應(yīng)的群優(yōu)化算法主導(dǎo)，而ISLG類算法的粒子數(shù)量遠(yuǎn)少于改進(jìn)前的算法，因此出現(xiàn)了DPLG與DGLG的效果分別低于DPSO與DGWO的情況。

總體上，M＞4時(shí)ISLG算法效果皆優(yōu)于未改進(jìn)前的算法，由圖中可知，DPSO效果比DGWO更好，同時(shí)DPLG對(duì)比DGWO效果也總體更好。這與預(yù)想的效果一致，即ISLG所繼承的基礎(chǔ)群優(yōu)化算法也會(huì)對(duì)其效果產(chǎn)生影響。而在PU數(shù)量較高時(shí)，DPLG與DWLG的效果已經(jīng)趨向同步，這是因?yàn)榇藭r(shí)ISLG算法中的主導(dǎo)角色已經(jīng)由基礎(chǔ)群優(yōu)化算法變?yōu)長G。

顯然ISLG在大部分情況下都可以獲得更好的效果，ISLG可以充分利用LG本身的優(yōu)勢(shì)與基礎(chǔ)智能算法形成互補(bǔ)從而尋找到更優(yōu)解。以DGLG與DGWO為例，在M＝4時(shí)，DGWO與DPLG收益差距最小，而在M＝10時(shí)，兩者的差距最大，因?yàn)樵贛＝10時(shí)，DGLG已經(jīng)獲得了LG的良好性能，而在DGLG中，DGWO的性能通過LG也獲得了合適的釋放，因此使得DGLG的性能遠(yuǎn)高于只使用DGWO。如此蛙跳可以改進(jìn)群優(yōu)化算法在高維度情況下效果不佳的特點(diǎn)，而群優(yōu)化算法則可以間接提高蛙跳博弈跳出局部最優(yōu)的能力，因此ISLG可以保證在復(fù)雜度較低的同時(shí)，也在信道分配中有著更佳的性能。

3.4 不同信道模型對(duì)頻譜分配效果的影響

由于上述仿真實(shí)驗(yàn)都執(zhí)行在較為理想的自由空間信道下，為不失去公平性地分析本文算法在不同信道下的效果，在此對(duì)瑞利衰落模型(Rayleigh)與對(duì)數(shù)正態(tài)衰落模型(Lognormal)進(jìn)行仿真分析。

衰落信道模型如式(15)所示:

式中:P(d)為經(jīng)過衰落信道后的接收信號(hào)功率，Pr(d)為自由空間模型下的理想接收功率，S(d)為大尺度陰影衰落增益對(duì)應(yīng)對(duì)數(shù)正態(tài)衰落模型，R(d)為多徑衰落增益對(duì)應(yīng)瑞利衰落模型。

設(shè)置Rayleigh信道，其增益用實(shí)部和虛部分別建模成均值為0方差為1的獨(dú)立同分布的高斯隨機(jī)過程表述；設(shè)置Lognormal模型的均值為1，方差為1[17]。其中為了限制Lognormal的衰落效果，設(shè)置其增益處于區(qū)間[0.1，1]。

對(duì)兩種信道模型，分別使用OSPF配以DPSO與APRT配以DPSO兩種算法進(jìn)行仿真，仿真與3.3節(jié)中場(chǎng)景保持一致。對(duì)于不同的M，每次的信道增益將重新計(jì)算，算法各進(jìn)行50次仿真并取平均值，結(jié)果如圖7所示。

圖7 不同信道模型下不同算法優(yōu)化性能

在衰落信道下，全局的吞吐收益的確受到了影響，由于每次仿真其信道增益都重新獲取，因此曲線并不隨M呈現(xiàn)上升趨勢(shì)，而是存在隨機(jī)性。

在仿真中Rayleigh的期望增益約為0.63，Lognormal的期望增益約為0.58。因此可以看到二者的全局收益相差不多，但Rayleigh信道下的收益稍好一些。若單純以期望增益推斷全局的吞吐，那么基于3.3節(jié)計(jì)算，Rayleigh信道下的全局收益應(yīng)該為720 Mbyte/s左右。但結(jié)果遠(yuǎn)比此好，這是因?yàn)樾诺涝鲆媸欠蟁ayleigh分布的，信道分配算法會(huì)傾向于分配給SU以擁有較好增益的信道，因此實(shí)際給SU所分配的信道的增益一般都會(huì)大于Rayleigh的期望增益。

從算法對(duì)比角度來說，在不同的衰落信道下，基于OSPF與DPSO的信道吞吐收益較之基于APRT與DPLG的信道吞吐收益差較多，這與上述3.1~3.3的仿真結(jié)論一致。這表明了對(duì)于不同的信道模型，本文算法都可以實(shí)現(xiàn)較優(yōu)的信道頻譜分配。

4 總結(jié)

針對(duì)認(rèn)知傳感器網(wǎng)絡(luò)中存在的難以尋找到最佳頻譜分配方案的問題，提出了一種基于蛙跳博弈優(yōu)化算法的頻譜分配算法。通過對(duì)路由層進(jìn)行調(diào)整，并使用蛙跳博弈優(yōu)化算法，實(shí)現(xiàn)最佳的頻譜分配以及最大化系統(tǒng)吞吐。仿真結(jié)果表明本文方案以最大化系統(tǒng)吞吐量為目標(biāo)，在保證PU正常傳輸?shù)那闆r下具有較好的分配信道、增加網(wǎng)絡(luò)吞吐的效果。APRT相較于FRT可以有效優(yōu)化網(wǎng)絡(luò)質(zhì)量，ISLG類算法相比改進(jìn)前智能算法有著更高的算法效率和性能，適用于不同信道模型下CRSN的頻譜分配。