基于遺傳算法的多信道無線網(wǎng)絡信道分配方案

劉耀中，余旭濤

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

1 概述

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

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

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

2 多信道無線網(wǎng)絡信道分配模型

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

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

其中，i和j表示網(wǎng)絡拓撲圖中的鏈路，1≤i≤l，1≤j≤l，i和j都為自然數(shù)。

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

3 改進的自適應遺傳算法

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

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

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

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

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

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

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

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

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

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

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

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

步驟7 判斷是否達到預定的迭代次數(shù)。如果是，則結(jié)束尋優(yōu)過程；否則，轉(zhuǎn)步驟4。

4 編碼方式及參數(shù)設置

遺傳算法有二進制編碼方式、實數(shù)編碼方式和整數(shù)編碼方式[12]。本文采用整數(shù)編碼的方式。對于一個可行解矩陣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)是這個個體被選擇的概率。

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

5 仿真結(jié)果與分析

圖1是一個包含10個節(jié)點的無線網(wǎng)絡拓撲。

圖1 含有10個節(jié)點的網(wǎng)絡拓撲

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

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

圖2 算法改進前后的網(wǎng)絡沖突值對比

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

圖3 不同信道數(shù)對應的網(wǎng)絡沖突值

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

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

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

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

圖4 發(fā)送距離為100 m時不同信道數(shù)對應的網(wǎng)絡沖突值

圖5 發(fā)送距離為100 m時2種分配方式的網(wǎng)絡沖突值

圖6 發(fā)送距離為150 m時2種分配方式的網(wǎng)絡沖突值

6 結(jié)束語

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

[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]梁 旭,黃 明.現(xiàn)代智能優(yōu)化混合算法及其應用[M].北京: 電子工業(yè)出版社,2011.

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

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