基于遺傳算法的多信道無線網絡信道分配方案

劉耀中，余旭濤

(東南大學毫米波國家重點實驗室，南京 210008)

1 概述

在傳統的單信道無線網絡中，多個節點同時傳輸時，彼此間的干擾會帶來容量降低的問題。尤其是節點密度增加將加劇節點間的競爭和發送分組之間的沖突，同時，大量的節點退避降低了信道利用率，并導致吞吐量的迅速下降。因此，信道干擾成為影響無線網絡容量的重要因素。而在多信道無線網絡中，節點可以用不同的信道發送和接收數據，從而減少沖突。由于信道數目受限，因此如何合理有效地利用多信道技術增加無線網絡并行傳輸的鏈路數目，提升無線網絡的吞吐量，成為無線網絡研究中的關鍵問題之一。多信道網絡的性能與網絡中可用信道的數目以及通信時采用何種信道分配方案相關。一個好的信道分配策略，能夠降低無線鏈路之間的干擾，提高無線網絡的吞吐量，優化網絡的性能和降低網絡通信時數據的丟包率。因此，多信道無線網絡中信道分配成為研究的熱門話題。

目前，已提出多種信道分配方案，如按需動態信道分配(Dynamic Channel Assignment,DCA)[1]協議，DCA協議中每個節點配置 2個無線接口，其中，一個接口固定工作在控制信道上傳輸控制信息；另一個接口在其余的信道上進行切換，完成數據傳輸的任務，通過節點同時偵聽控制信道和數據信道，有效降低了沖突。文獻[2]研究信道數小于接口數的情況，在固定部分接口卡的情況下，提出一種可以平衡網絡負載的信道分配和信道切換策略。文獻[3-4]提出一種基于學習的多接口信道分配協議(Learning-based Channel Allocation Protocol,LCAP)，LCAP通過自動從鄰節點學習信道的使用信息，從而自適應地進行高效率的信道分配。文獻[5]提出一種混合信道分配策略，根據相鄰節點使用相同信道的固定接口數目分配信道。信道跳躍多址接入(Channel Hopping Multiple Access,CHMA)協議[6]首先將時間劃分為若干個時隙，網絡中的節點按照同樣的順序進行工作頻率的跳變，在同一個時隙里網絡中的所有空閑節點處于同一工作信道。如果節點有數據需要發送，則先發送一個請求發送包，接收節點收到請求發送包后在下一跳回復一個清除發送包，這樣收發節點將停留在此信道上完成數據的傳輸。分割插入信道跳躍(Slotted Seeded Channel Hopping,SSCH)協議[7]同樣使用了信道跳躍技術，但是各個節點的信道跳躍順序并不相同，節點根據偽隨機序列同步切換信道，且每個節點都有多個序列，每個序列都由唯一的偽隨機序列發生器產生。網絡中任意 2個節點至少有一個時隙停留在同一信道，這樣網絡中的各個節點就可以通過廣播來了解各自的信道調度情況。

本文針對單接口多信道無線網絡，提出一種基于改進自適應遺傳算法的多信道無線網絡信道分配方案。建立多信道無線網絡信道分配問題的數學模型，將信道分配問題轉化為相應的優化問題。采用遺傳算法對其進行求解，針對傳統遺傳算法容易早熟和局部收斂的缺點，對傳統遺傳算法進行改進，使用新的交叉方式，并且使算法能夠在運行的過程中自適應地調整相應的參數。

2 多信道無線網絡信道分配模型

對于一個由 n個節點組成的多信道無線網絡，設節點存在l條鏈路，有c個正交的無線信道可以同時傳輸數據。用頂點v(v∈V)表示網絡中的節點，如果2個節點之間存在通信鏈路，則用一條邊e(e∈E)表示，這樣就得到網絡的拓撲圖G(V,E)，然后用頂點v’(v’∈V’)表示網絡拓撲圖的邊，若在單信道情況下，2個頂點所對應的鏈路間存在沖突，則用一條邊e’(e’∈E’)將2個頂點相連，這樣便由網絡的拓撲圖 G(V,E)得到網絡沖突圖G(V’,E’)，再由網絡沖突圖G推出網絡的沖突矩陣A，網絡沖突矩陣A為一個l×l的矩陣，用來描述網絡中鏈路間的沖突情況。根據沖突矩陣A求信道分配矩陣B。

對單信道的無線網絡，根據沖突圖可以得到網絡沖突矩陣A=[aij]l×l，矩陣中各元素取值如下：

其中，i和j表示網絡拓撲圖中的鏈路，1≤i≤l，1≤j≤l，i和j都為自然數。

網絡中如何給各個鏈路分配信道，用道分配矩陣B來表示。假設可用信道數目為 c，在信道分配矩陣 B=[bij]l×c中，每一行有且僅有一個元素為 1，其余元素為 0，即若bij=1，表明第i條鏈路被分配到第j個信道上。另外，用列向量Bj表示矩陣B的第j列，Bj描述了網絡中的鏈路分配到第j個信道的情況。因為網絡的沖突矩陣A中，取值為1的元素總和代表在單信道的情況下，網絡所有鏈路之間總的沖突值，所以表示所有被分配到第j個信道鏈路之間的沖突值，整個網絡的沖突值可用來表示，即所有信道對應沖突值的總和。因此，信道分配問題可以歸結為求矩陣 B=[bij]l×c，使得網絡沖突值最小：

3 改進的自適應遺傳算法

本文采用遺傳算法解決上述極小化問題，遺傳算法是模擬生物的遺傳進化過程而形成的全局優化概率搜索算法[8]。對于傳統的遺傳算法來說，控制參數是在遺傳進化中保持不變的，因此，容易出現早熟和局部收斂。而自適應遺傳算法可以實現參數的可變，能夠使交叉率和變異率隨群體的適應度自適應改變，能提供相對某個解的最佳交叉率和變異率[9]。與傳統遺傳算法相比，自適應遺傳算法的交叉率與變異率不是一個固定值，而是按群體的適應度進行自適應調整[10]。

本文使用一種改進的自適應遺傳算法[11]，該算法采用了一種新的交叉方式，增強算法的全局搜索能力，同時，能夠在優化過程中，根據具體情況自動調節交叉概率和變異概率，避免算法陷入局部最優，從而顯著提高搜索效率。

該遺傳算法將進化過程分成 2個部分：初期和后期。在初期執行固定參數的遺傳操作，在后期執行自適應遺傳操作。這樣可以在初期讓優良的染色體也有較大的機會參與交叉運算，提高種群的多樣性。為了防止出現局部最優的情況，本文算法提出一種新的交叉方式。每次遺傳操作后，將所有的染色體按照適應值大小排序并分為 2組，即將高適應值的染色體分為一組，剩下的為另一組。在交叉操作之前，分別從 2組中各隨機選一個染色體進行交叉運算，這樣可以讓最優的染色體和最差的染色體有較大的交叉概率，整個染色體種群的適應值同時向最優解靠近，防止了局部最優的出現。該算法在生成子代時，采用父子競爭機制的原理，兩父代交叉產生2個新一代，當2個子代中具有最大適應值的個體值大于父代中具有最大適應值的個體時，認為子代優于父代，將子代替換父代，否則，保留父代，讓其進入下一輪的進化。這樣，就不會只要進行交叉算子操作子代就替換父代，而是在父子兩代中選擇最優的個體進入下一代，子代總是優于它們的父代，進化總是朝著最優的方向發展。

改進的自適應遺傳算法過程如下：

步驟1 進行編碼設計，并生成初始群體。

步驟2 定義適應度函數，計算各個個體的適應度fi。

步驟3 計算群體的平均適應度favg和最大適應度fmax，將群體按適應值大小排序并分為2組。

步驟4 進行交叉操作，首先判斷種群的代數，若小于n，執行固定的交叉概率；若大于等于 n，執行自適應交叉概率。n為執行固定參數遺傳操作的代數，自適應交叉概率Pc如下：

其中，fc為要交叉的2個個體中較大的適應度值；favg為群體的適應度平均值；fmax為群體的最大適應度；k1、k2為預先設定的常數。

步驟5 進行變異操作，首先判斷種群的代數，若小于n，則執行固定的變異概率；若大于或等于 n，則執行自適應變異概率Pm如下：

其中，fm為要變異個體的適應度值；k3、k4為預先設定的常數。

步驟6 計算由交叉和變異生成的新個體的適應度，構成新一代群體。

步驟7 判斷是否達到預定的迭代次數。如果是，則結束尋優過程；否則，轉步驟4。

4 編碼方式及參數設置

遺傳算法有二進制編碼方式、實數編碼方式和整數編碼方式[12]。本文采用整數編碼的方式。對于一個可行解矩陣B(l×c)，可以用一個l維的向量M表示，向量中每個元素的取值范圍為1,2,…,c。比如一個l為8，c為4的矩陣B表示為：

對應的l維向量M為(1,1,2,2,3,3,4,4)。

向量M第i個元素的值x代表矩陣BT第i列的第x行元素為1，而其余行的元素為0。比如M中第8個元素值為4，在BT中對應第8列第4行的元素為1。

隨機生成200個個體作為初始群體，即200個l維向量，向量中每個元素的取值范圍為1,2,…,c。然后，采用輪盤賭選擇方式從種群中選擇個體。即每個個體進入下一代的概率等于它的適應度值與整個種群中個體適應度值總和的比例。一個個體被選擇的概率由下式給出：

其中，f(xi)是個體 xi的適應度；F(xi)是這個個體被選擇的概率。

采用單點交叉的方式產生新的種群。對于2個長度為k的向量P、Q，選擇一個均勻分布的隨機整數m，在[1,k?1]間，在P和Q間交換m+1～k之間的各變量。另外，步驟4中的k1、k2分別設定為0.8和0.9。同時，步驟5中的k3、k4均設定為 0.05，n設定為50，即執行固定交叉率和變異率的遺傳代數為50。同時，設定最大遺傳代數為300。

5 仿真結果與分析

圖1是一個包含10個節點的無線網絡拓撲。

圖1 含有10個節點的網絡拓撲

10個節點分布在400 m×200 m的區域中。如果2個節點a和節點b之間的距離小于節點的發送距離，則節點a和節點b之間存在一對雙向鏈路，即以節點a為發送節點，節點b為接收節點的一條鏈路和以節點b為發送節點，節點a為接收節點的一條鏈路。當節點發送距離為150 m時，一共存在 52條鏈路，于是可以得出一個 52×52的沖突矩陣。其中，沖突矩陣中1的數目為2268。所以，當信道數為c時，如果采用隨機的方式把52條鏈路分配給c個信道，則網絡中鏈路的沖突值為2268/c。而根據遺傳算法可以求出當信道數為 c時，目標函數值的變化，取出其中的最小值，即為使用遺傳算法分配信道時對應的沖突值。

圖2是信道數c=4時，采用簡單遺傳算法和改進的自適應遺傳算法進行信道分配對應的網絡沖突值對比，通過簡單遺傳算法得到的分配矩陣B對應的網絡沖突值為444，而通過改進的自適應遺傳算法得到的分配矩陣B對應的網絡沖突值為432。通過圖2的比較可以看出，使用改進的自適應遺傳算法比使用簡單遺傳算法的收斂速度更快，當遺傳代數為 100時，采用簡單遺傳算法求解得到的網絡沖突值僅收斂到454，而遺傳代數同樣為100時，采用改進的自適應遺傳算法求解得到的網絡沖突值已收斂到442。且采用改進的自適應遺傳算法求解所得到的解對應的網絡沖突值更小，因此，所求的解更加逼近最優解。另外，整個種群個體對應的網絡沖突值的均值更小，正如前面提到的，整個種群的適應值同時向最優解靠近。

圖2 算法改進前后的網絡沖突值對比

圖3顯示了信道數分別為3、5和7時，網絡沖突值隨遺傳代數的變化。

圖3 不同信道數對應的網絡沖突值

采用改進的自適應遺傳算法所求的網絡沖突值分別為624、332、208。在每條實線的上方的虛線分別對應不同的信道數的情況下，采用隨機方式分配信道相對應的網絡沖突值，在信道數為3、5和7的情況下，分別為756、454、324。從圖3可以看出，采用改進的自適應遺傳算法進行鏈路分配可以大幅降低網絡的沖突，尤其在信道數較多的情況下效果更為明顯。

當節點發送距離為100 m時，以上的網絡拓撲圖中一共存在28條鏈路，于是可以得出一個28×28的沖突矩陣。其中，矩陣中1的數目為500。同樣，當信道數為c時，如果采用隨機的方式把28條鏈路分配給c個信道時，則鏈路的沖突值為 500/c。而采用改進的自適應遺傳算法求解，信道數分別為3、5和7時，網絡沖突值隨遺傳代數的變化如圖4所示。

可以得到最終解對應的網絡沖突值分別為108、48、22。從圖4可以看出，相比于發送距離為150 m的情況，其網絡沖突值的下降幅度更為明顯。

圖5和圖6采用條形圖比較了信道數不同，發送距離為100 m(網絡中一共存在28條鏈路)、150 m(網絡中一共存在52條鏈路)時，采用隨機分配方式和使用改進的自適應遺傳算法分配鏈路對應的網絡沖突值。可以看到，采用改進的自適應遺傳算法進行網絡鏈路分配相比于隨機的鏈路分配方式，可以顯著地減小網絡的沖突值，尤其在網絡中的可用信道數較多，以及網絡節點發送距離較小、沖突矩陣稀疏時，效果更為明顯。如發送距離為100 m，信道數為7時，采用改進的自適應遺傳算法進行網絡鏈路分配得到的網絡沖突值僅為隨機的分配方式對應網絡沖突值的30%。

圖4 發送距離為100 m時不同信道數對應的網絡沖突值

圖5 發送距離為100 m時2種分配方式的網絡沖突值

圖6 發送距離為150 m時2種分配方式的網絡沖突值

6 結束語

針對單接口多信道無線網絡的信道分配問題，本文提出一種改進的自適應遺傳算法。利用沖突圖的概念為網絡建立模型，進而導出網絡的沖突矩陣，將問題轉化為求信道分配矩陣，使網絡沖突值最小，通過對信道分配矩陣進行合適的編碼，從而利用遺傳算法加以解決。仿真結果表明，該算法進行分配可以大幅降低網絡的沖突值，從而提升網絡的性能。本文僅考慮了單接口多信道的情況，給每個節點配備多個接口可以進一步降低網絡的干擾，因此，今后將對多接口多信道網絡進行研究。

[1]Wu Shih-Lin,Lin Chih-Yu,Tseng Yu-Chee,et al.A New Multi-channel MAC Protocol with On-demand Channel Assignment for Multi-hop Mobile Ad Hoc Networks[C]//Proc.of International Symposium on Parallel Architectures,Algorithms,and Networks.Dallas,USA: IEEE Computer Society,2000.

[2]He Pingshi,Xu Ziping.Channel Assignment and Routing in Multi-channel,Multi-interface Wireless Mesh Networks[C]//Proc.of the 2nd Computer Engineering and Technology.Chengdu,China: IEEE Press,2010.

[3]Ghosh A,Hamouda W.Cross-layer Antenna Selection and Channel Allocation for MIMO Cognitive Radios[J].IEEE Transactions on Wireless Communications,2011,10(11):3666-3474.

[4]Pediaditaki S,Arrieta P,Marina M K.A Learning-based Approach for Distributed Multi-radio Channel Allocation in Wireless Mesh Networks[C]//Proc.of the 17th IEEE International Conference on Network Protocols.Princeton,USA: IEEE Press,2009.

[5]Kyasanur P,Vaidya N.Routing and Link-layer Protocols for Multi-channel Multi-interface Ad Hoc Wireless Networks[J].Mobile Computing and Communications Review,2006,10(1):31-43.

[6]Tzamaloukas A,Garcia J J,Channel-hopping Multiple Access[C]//Proc.of International Conference on Communications.New Orleans,USA: IEEE Press,2000.

[7]Paramvir B,Chandra R,Dunagan J.SSCH: Slotted Seeded Channel Hopping for Capacity Improvement in IEEE 802.11 Ad-hoc Wireless Networks[C]//Proc.of the 10th Annual International Conference on Mobile Computing and Networking.New York,USA: ACM Press,2004.

[8]Holland J H.Adaptation in Natural and Artificial System[M].[S.l.]: MIT Press,1975.

[9]Srinivas M,Patnaik L M.Adaptive Probabilities of Crossover and Mutation in Genetic Algorithm[J].IEEE Transactions on System,Man and Cybernetics,1994,24(4): 656-667.

[10]梁 旭,黃 明.現代智能優化混合算法及其應用[M].北京: 電子工業出版社,2011.

[11]梁 霞,梁 旭,黃 明.改進的自適應遺傳算法及其在作業車間調度中的應用[J].大連鐵道學院學報,2005,26(4):33-35.

[12]雷英杰,張善文,李續武,等.遺傳算法工具箱及應用[M].西安: 西安電子科技大學出版社,2005.