認(rèn)知無線電網(wǎng)絡(luò)遺傳－蟻群聯(lián)合優(yōu)化路由算法

陳善學(xué)，張佳佳，朱 江，鄭文靜

（重慶郵電大學(xué) 移動通信技術(shù)重慶市重點實驗室，重慶400065）

0 引 言

人們對認(rèn)知無線電的研究主要集中在物理層、媒體訪問控制層［1－3］。其中，作為認(rèn)知無線電技術(shù)的重要組成部分，至今認(rèn)知無線電路仍未有一個具有代表性的路由協(xié)議。在認(rèn)知無線電中，頻譜可能隨著空間、時間的變化而變化，所以只考慮物理層、MAC層往往是不夠的，只有在優(yōu)化物理層、MAC層的基礎(chǔ)上，同時優(yōu)化網(wǎng)絡(luò)層才能取得更好的性能指標(biāo)。因此路由算法將會成為認(rèn)知無線電的一個重要研究方向。

為了提高網(wǎng)絡(luò)的性能指標(biāo)，很多學(xué)者利用NP完全（NP complete，NPC）問題來解決。其中，在解決NP完全問題方面啟發(fā)式算法具有很明顯的優(yōu)勢。為了解決NP完全問題，模擬退火算法［4］、神經(jīng)網(wǎng)絡(luò)［5］、遺傳算法［6］、蟻群算法［7］等啟發(fā)式算法被學(xué)者們采納。但在求最小時延最優(yōu)解過程中遺傳算法計算量比較大，得到的結(jié)果可靠性差，不能穩(wěn)定得到解且容易產(chǎn)生局部收斂不能得到最優(yōu)解。然而，蟻群算法在求解復(fù)雜問題時具有很好的優(yōu)越性，但容易過早收斂陷入局部最優(yōu)化。為了找出最小時延最優(yōu)解，本文通過結(jié)合遺傳算法和蟻群算法的優(yōu)點提出了遺傳－蟻群聯(lián)合優(yōu)化路由算法。在遺傳算法求最優(yōu)解的基礎(chǔ)上，利用蟻群算法使螞蟻有一個很高的起點，然后采用自適應(yīng)搜索方式求解最優(yōu)路徑。在自適應(yīng)搜索過程中，當(dāng)信息素積累很多時，收斂性會變慢但搜索范圍擴大。因此，遺傳－蟻群聯(lián)合算法在求最優(yōu)解問題上穩(wěn)定性、全局性比較好。

1 系統(tǒng)模型

認(rèn)知無線電網(wǎng)絡(luò)是由一系列的次用戶組成，當(dāng)主用戶未占用授權(quán)頻段時次用戶可以機會接入該頻段。本文采用的是分布式網(wǎng)絡(luò)結(jié)構(gòu)，每個次用戶自身可進行頻譜感知。這里用G＝（N，L）來表示一個認(rèn)知無線電網(wǎng)絡(luò)，其中N為網(wǎng)絡(luò)中的次用戶集合，L為網(wǎng)絡(luò)中通信鏈路集合。這里每個次用戶在獲得自身可用頻譜后都可以進行信道轉(zhuǎn)換和接入空閑信道。在通信范圍之內(nèi)，當(dāng)兩個次用戶之間存在空閑信道時，兩次用戶可以進行通信。在干擾范圍內(nèi)的兩條鏈路如果使用同一條信道彼此之間會產(chǎn)生一定的干擾。

本文目的是為了找出最小時延路徑及其所使用的信道，因此我們這里的優(yōu)化目標(biāo)為其中

式中：h′——上一跳節(jié)點到節(jié)點i所使用的信道，h——節(jié)點i到節(jié)點j所使用的信道，I——數(shù)據(jù)包長度，信道切換、退避時延以及排隊時延之和為

節(jié)點i經(jīng)過H＋1個次用戶后到達(dá)目的節(jié)點，由于信道切換引起的時延為

不同節(jié)點競爭同一條信道引起的退避時延為

式中：pc——節(jié)點沖突概率，Numi——頻段Bandi的沖突節(jié)點個數(shù)，W0——退避窗口最小值。

排隊等候時延為

式中：Bh——頻段Bandi的帶寬。

信道容量為

式中：RSNj——從節(jié)點i到節(jié)點j使用h信道通信的信噪比，其中噪聲主要包括高斯白噪聲和使用相同信道引起的鏈路間的干擾，為傳輸損 耗為節(jié)點i到節(jié)點j的距離，λ為路徑損耗指數(shù) （這里設(shè)置為4），N0為高斯白噪聲密度為鏈路上的傳輸時延。

約束條件為

其中，M為網(wǎng)絡(luò)中空閑信道的集合，lij為從節(jié)點i到節(jié)點j的鏈路，式 （8）是對源節(jié)點、中間節(jié)點、目的節(jié)點的定義；式 （9）是為了保證從源節(jié)點到目的節(jié)點路徑的連通性；式 （10）是指h信道的授權(quán)用戶使用該信道時次用戶不能使用該信道；式 （11）是指在通信范圍內(nèi)，若鏈路lij檢測到可用信道集中含有h信道為1，否則為0，且只能取二進制數(shù)；式 （12）是指在通信范圍內(nèi)，鏈路lij若使用h信道進行通信為1，否則為0，且只能取二進制數(shù)；式 （13）是指鏈路lij只有檢測到h信道可用時才能使用h信道進行通信，即式 （14）是指節(jié)點i不能同時使用同一個信道進行發(fā)送和接收信息，否則節(jié)點i不能進行正常通信，主要是為了避免通信過程中的耳聾現(xiàn)象。

2 遺傳－蟻群聯(lián)合優(yōu)化路由算法

遺傳－蟻群聯(lián)合優(yōu)化路由算法主要由兩部分組成：初始信息素求解算法、最優(yōu)路徑求解算法。首先通過遺傳算求解初始信息素，然后利用遺傳算法求出的初始信息素進行蟻群算法求最優(yōu)路徑。

2.1 初始信息素求解算法設(shè)計

這里利用遺傳算法求解初始信息素，遺傳算法是用來解決整數(shù)規(guī)劃問題的方法之一，它主要由5個部分組成：染色體、適應(yīng)函數(shù)、交叉、變異、生存選擇。

（1）染色體：這里的染色體代表在認(rèn)知無線電網(wǎng)絡(luò)中所有通信鏈路上空閑信道的使用情況，基因代表一條鏈路上的一個信道的使用情況，它的值是二進制數(shù)如下所示

圖1 染色體

（2）適應(yīng)度函數(shù)：適應(yīng)度函數(shù)是一個衡量時延大小的參數(shù)，目的是為了最小化從源節(jié)點到目的節(jié)點的路徑總時延。其中，在滿足式 （8）～式 （14）約束條件的基礎(chǔ)上，若一條染色體中存在多條不同的從源節(jié)點到目的節(jié)點的路徑，則從中隨機選擇一條路徑及其相關(guān)信道計算其適應(yīng)度函數(shù)。這里將適應(yīng)度函數(shù)定義為

（3）染色體交叉：隨機地從父代染色體中選取兩條染色體，首先對兩個染色體進行異或運算。然后，判斷兩者相同的基因是否超過60%，若超過60%繼續(xù)隨機選取兩個染色體操作直到相同基因個數(shù)小于60%。通過此次判斷可以提高染色體交叉變換后的多樣性。最后，隨機分配給其中一個染色體的每個基因一個 （0，1）的概率值，判斷相對應(yīng)基因位置的概率值是否小于給定的門限概率pe（這里設(shè)置為0.7），若兩基因的概率值都小于pe則進行交叉互換。

染色體交叉如圖2所示。

圖2 染色體交叉

（4）染色體變異：隨機分配給每個子染色體的每個基因一個 （0，1）的概率值，給定一個突變概率門限pm（這里pm＝0.9），當(dāng)基因的概率值大于pm時對該基因值取非。

染色體變異如圖3所示。

圖3 染色體變異

（5）生存選擇：重復(fù) （1）～ （4）步驟直到染色體個數(shù)達(dá)到要求值，利用式 （16）求出各個染色體的適應(yīng)度函數(shù)值，從適應(yīng)度函數(shù)值不等于∞且路徑信息不相同的染色體中，提取前30%最小適度函數(shù)值的染色體作為生存選擇后的染色體，將該染色體集合記為F。將F中適應(yīng)度函數(shù)計算時被選中的從源節(jié)點到目的節(jié)點的路徑相關(guān)的鏈路、信道及其對應(yīng)的時延等信息進行存儲，其它鏈路及其相關(guān)信道對應(yīng)的時延設(shè)置為∞。并將各鏈路時延轉(zhuǎn)換為蟻群算法的初始信息素。這樣可以避免蟻群算法由于缺乏初始信息素造成的收斂速度過慢的現(xiàn)象。

遺傳算法中生存選擇得到的30%較優(yōu)解，其實是從源節(jié)點到目的節(jié)點尋找的路徑信息以及路徑時延，不同染色體中可能存在相同且被選擇作為路由的基因，若該基因位于f染色體中將其時延記為。這里可將這些路徑時延通過轉(zhuǎn)換作為初始信息素，轉(zhuǎn)換后的初始信息素定義為

2.2 最優(yōu)路徑求解算法設(shè)計

在使用蟻群算法尋找最優(yōu)路由過程中，首先利用遺傳算法得到解，然后經(jīng)轉(zhuǎn)換后作為蟻群算法的初始信息素，最后運用尋路規(guī)則以及信息素的更新規(guī)則找出本次迭代的最優(yōu)解。

2.2.1 尋路規(guī)則

在第NC次迭代時，由節(jié)點i到節(jié)點j傳輸信息使用h信道且上游鏈路使用h′信道時路徑選擇概率為

這里在滿足式 （8）～式 （14）約束條件的基礎(chǔ)上通過輪盤賭的方式利用選擇下一跳節(jié)點及其所使用的信道。由式 （18）可知，信息素越大，就越大，該路徑及信道就越容易被選中。當(dāng)j為目的節(jié)點時停止尋路，否則按照尋路規(guī)則繼續(xù)尋路。

2.2.2 信息素更新規(guī)則

當(dāng)螞蟻k找到目的節(jié)點時停止尋路，利用式 （16）計算螞蟻k的路徑總時延Lk（NC），當(dāng)所有螞蟻到達(dá)目的節(jié)點時計算本次迭代螞蟻的平均時延即ML（NC），其中m為螞蟻的總數(shù)。更新后的信息素為

其中

2.3 遺傳－蟻群聯(lián)合優(yōu)化路由算法流程

GACA算法融合了遺傳算法和蟻群算法兩種算法的優(yōu)點，使得該算法具有全局性并且穩(wěn)定性較好。該算法首先求出遺傳算法求得的前30%的最優(yōu)解，然后把它作為蟻群算法的初始信息素，這樣在求最優(yōu)解時會比蟻群算法有一個更好的起點，并且初始的收斂速度也會比蟻群算法更快。最后利用蟻群算法求最優(yōu)解。在求最優(yōu)路徑過程中，隨著信息素的積累，揮發(fā)度增大即ρ1（NC）減小，收斂速度減慢，搜索范圍得到增大，這樣可以找出比蟻群算法更優(yōu)的解。在遺傳－蟻群聯(lián)合優(yōu)化路由算法流程圖中，條件1：遺傳算法中染色體總數(shù)達(dá)到一個定值時結(jié)束循環(huán)。條件2：蟻群算法中經(jīng)過一定次數(shù)的迭代后求出的最優(yōu)解一直保持不變時結(jié)束循環(huán)。其流程如圖4所示。

圖4 遺傳－蟻群聯(lián)合優(yōu)化路由算法流程

3 實驗仿真

3.1 仿真環(huán)境

仿真中，在一個1500m×1500m網(wǎng)絡(luò)中，最大通信距離和干擾范圍分別為300m和600m，由n個節(jié)點組成，節(jié)點位置隨機分布在該網(wǎng)絡(luò)中。在20MHz～2.4GHz的頻譜范圍內(nèi)隨機選取5個頻段作為仿真場景中的SOP集合，每個節(jié)點隨機選取2～5個頻段作為可用信道，發(fā)射功率為1000 W。在n個節(jié)點中隨機取10組節(jié)點，每組節(jié)點由2個節(jié)點組成，分別作為路由的源節(jié)點和目的節(jié)點。傳輸?shù)臄?shù)據(jù)包長度I＝100kbit。GACA算法中遺傳算法的第一代染色體個數(shù)都為30，種群的總個數(shù)為6000。GACA算法和AC算法中的蟻群算法Q設(shè)置為0.5，控制參數(shù)α為2，螞蟻的個數(shù)都設(shè)置為30。AC算法中的初始信息素全部為1，揮發(fā)因子ρ為常數(shù)1。此外，迭代次數(shù)對時延與吞吐量影響的仿真是在由9個節(jié)點組成的網(wǎng)絡(luò)中進行的。在最優(yōu)路由求解過程中，GACA算法和AC算法循環(huán)結(jié)束條件為連續(xù)40次迭代求出的最優(yōu)解不變。然后，分別計算上述10組數(shù)據(jù)的總時延和端到端吞吐量，最后對10數(shù)據(jù)值求平均。本文評估的性能主要分為3個方面：端到端時延、端到端吞吐量以及算法時間復(fù)雜度。端到端時延是指從源節(jié)點發(fā)送長度為I的數(shù)據(jù)包到目的節(jié)點所需要的時間。端到端吞吐量是指大小為I的數(shù)據(jù)包，除以其從源節(jié)點到目的節(jié)點的各段鏈路中所用的時間，得到的最大數(shù)據(jù)傳輸速率［8］。時間復(fù)雜度是指執(zhí)行算法所需要的計算工作量。

3.2 節(jié)點個數(shù)對時延的影響

隨著網(wǎng)絡(luò)中節(jié)點數(shù)目的增多，頻譜切換次數(shù)增加從而導(dǎo)致信道切換時延的增加，此時競爭同一條信道的節(jié)點增多使得退避時延也會增加，另外由于路由跳數(shù)的增多使得排隊時延也會增加，因此隨著網(wǎng)絡(luò)中節(jié)點數(shù)的增多路徑總時延會逐漸增加。比較GACA算法和AC算法，如圖5所示，隨著節(jié)點個數(shù)的增多GACA算法時延增加的速度比AC算法的慢，并且時延比AC算法求出的要小，主要由于隨著節(jié)點個數(shù)的增加，AC算法的局部收斂現(xiàn)象越來越嚴(yán)重。

圖5 不同節(jié)點個數(shù)下平均時延的比較

3.3 節(jié)點個數(shù)對吞吐量的影響

由于數(shù)據(jù)包傳輸時間和吞吐量是成反比的，隨著節(jié)點數(shù)目的增加，端到端的吞吐量逐漸減小。如圖6所示，隨著節(jié)點個數(shù)的增多GACA算法吞吐量減小的速度比AC算法的慢，并且吞吐量比AC算法求出的要大。

3.4 迭代次數(shù)對時延的影響

圖6 不同節(jié)點個數(shù)下端到端吞吐量的比較

隨著迭代次數(shù)的增加時延越來越小，最終會收斂到一點。如圖7所示，在迭代次數(shù)20時，GACA算法得出的時延值比AC算法得出的值要小很多，主要由于AC算法中的初始信息素是相同的，而GACA算法利用遺傳算法求出30%最優(yōu)解作為蟻群算法的初始信息素，使其在尋優(yōu)過程中比AC蟻群算法有一個更好的起點。此外，AC算法迭代次數(shù)靠近100時已經(jīng)收斂，而GACA算法迭代次數(shù)靠近160時收斂，可見GACA算法由于引入了參數(shù)ρ1（NC）與路徑時延有關(guān)，使得當(dāng)路徑總時延很小時收斂速度變慢，這樣可以擴大螞蟻的搜索范圍找出更優(yōu)的解，從GACA算法的最終收斂時延值比AC算法小可驗證。

圖7 迭代次數(shù)對端到端時延的影響

3.5 迭代次數(shù)對吞吐量的影響

分別通過GACA算法和AC算法求吞吐量，隨著迭代次數(shù)的增大端到端的吞吐量越來越大，如圖8所示在起始點由于遺傳算法的引入GACA算法求出的吞吐量明顯比AC算法大，隨著迭代次數(shù)的增大GACA算法的收斂速度比AC算法的慢，這樣使得GACA算法避免算法過早陷入局部收斂的狀態(tài)同時擴大搜索范圍。由圖8可知GACA算法的最終收斂值是比AC算法更好。

3.6 復(fù)雜度分析

由于GACA算法在AC算法基礎(chǔ)上引入了GA算法，所以它的復(fù)雜度比AC算法要高。表1中，M是指網(wǎng)絡(luò)中的空閑信道個數(shù)，N是指網(wǎng)絡(luò)中的節(jié)點個數(shù)。由表1可知，GACA算法的加減、乘除、取對數(shù)運算復(fù)雜度明顯比AC算法要高。

圖8 迭代次數(shù)對端到端吞吐量的影響

表1 算法復(fù)雜度分析

4 結(jié)束語

本文提出的GACA算法主要適用于認(rèn)知無線電路由的研究，該算法綜合了遺傳算法和AC算法各自的優(yōu)點，使得該算法在初始時收斂速度快，但它的算法復(fù)雜度要比AC算法高出很多。然而，隨著計算機處理技術(shù)的發(fā)展，這種代價是完全可以接受的。另外，自適應(yīng)搜索方式的引入使得算法的收斂速度變慢但擴大了搜索范圍，這樣可以有效地避免了GACA算法過早陷入局部收斂狀態(tài)。經(jīng)仿真結(jié)果比較，GACA算法不受種群數(shù)目的限制求出的結(jié)果比較穩(wěn)定。雖然在迭代的后期算法收斂速度較慢，但與AC算法相比，GACA算法的實時性提高了18%，網(wǎng)絡(luò)吞吐量提高了23%。

［1］Akyildiz I，Lee W Y，Vuran M C，et al.Next generation dynamic spectrum access cognitive radio wireless networks：A survey ［J］.Computer Networks，2006，50 （13）：2127－2159.

［2］Khalife H，Ahuja S，Malouch N，et al.Probabilistic path selection in opportunistic cognitive radio networks ［C］／／IEEE Global Telecommunications Conference，2008：4861－4865.

［3］YANG Chungang，LI Jiandong，LI Weiying，et al.Cognitive radio power allocation method based on non－cooperative game theory ［J］.Xi’an University of Electronic Science and Technology，2009，36 （1）：1－4 （in Chinese）.［楊春剛，李建東，李維英，等.認(rèn)知無線電中基于非合作博弈的功率分配方法［J］.西安電子科技大學(xué)學(xué)報，2009，36 （1）：1－4.］

［4］Ahmed Tariq Sadiq，Amaal Ghazi Hamad.A hybrid bees simulated annealing algorithm to solve optimization ＆ NP－complete problems［J］.Eng ＆Tech Journal，2010，28 （2）：271－281.

［5］FAN Yuanyuan，SANG Yingjun.The research of nonlinear control based on fuzzy neural network ［C］／／Proceedings of International Conference on Electrical and Control Engineering.Wuhan：IEEE，2010：2417－2420.

［6］WANG Zhenchao，WANG Jing，JING Xin.Multipath routing based on genetic algorithms ［J］.Computer Engineering，2011，37 （20）：197－199 （in Chinese）. ［王振朝，王靜，荊鑫.基于遺傳算法的多路徑路由研究 ［J］.計算機工程，2011，37 （20）：197－199.］

［7］QI Jin，ZHANG Shunyi，SUN Yanfei，et al.Multi－constrained QoS routing algorithm based on ant colony algorithm independent cognitive networks ［J］.Nanjing University of Posts and Telecommunications，2012，32 （6）：86－90 （in Chinese）.［亓?xí)x，張順頤，孫雁飛，等.基于自主蟻群算法的認(rèn)知網(wǎng)絡(luò)多約束QoS路由算法 ［J］.南京郵電大學(xué)學(xué)報，2012，32（6）：86－90.］

［8］LI Yun，ZHANG Zhihui，HUANG Wei，et al.Cognitive radio networks based on multi－h(huán)op routing algorithms channel allocation ［J］.Systems Engineering and Electronics，2013，35（4）：852－858 （in Chinese）. ［李云，張智慧，黃巍，等.基于信道分配的多跳認(rèn)知無線電網(wǎng)絡(luò)路由算法 ［J］.系統(tǒng)工程與電子技術(shù)，2013，35 （4）：852－858.］

［9］XIANG Biqun，ZHANG Zhenghua，QIN Fengxie，et al.A routing algorithm based on cognitive radio channel capacity estimation［J］.Journal of Chongqing University of Posts and Telecommunications，2011，23 （4）：406－410 （in Chinese）.［向碧群，張正華，覃鳳謝，等.基于信道容量估計的一種認(rèn)知無線電路由算法［J］.重慶郵電大學(xué)學(xué)報，2011，23 （4）：406－410.］

［10］Re E，Gorni G，Ronga L S，et al.Flexible and dynamic use of spectrum：The cognitive radio approach ［J］.Globalization of Mobile and Wireless Communications，2011，5 （1）：159－183.

［11］Beltagy I，Youssef M，Mohamed E D.A new routing metric and protocol for multipath routing in cognitive networks［C］／／Proc of the IEEE Wireless Communications and Networking Conference，2011：974－979.

［12］GAO Cunhao，YI Shi，THOMAS Y.Multicast communications in multi－h(huán)op cognitive radio networks ［J］.IEEE Journal on Selected Areas in Communications，2011，29 （4）：784－793.