基于遺傳算法的蜂窩網(wǎng)絡接入信道動態(tài)分配方案的設計

摘 要： 蜂窩網(wǎng)絡中，使用信道復用技術能夠在很大程度上提高移動通信的容量和質(zhì)量。但是，信道復用過程中會產(chǎn)生不同程度的電子干擾問題，使得信道復用的作用大打折扣。傳統(tǒng)的進行信道優(yōu)化的方法很多，但是效果都不是很理想。這里利用遺傳算法進行蜂窩網(wǎng)絡接入信道的動態(tài)分配，主要通過對集中常出現(xiàn)的信道干擾問題加上一些約束條件，這樣建立的數(shù)學模型能夠獲得一最小干擾信號的信道分配方案，在很大程度上避免了移動用戶之間的干擾問題。

關鍵詞： 遺傳算法； 信道重用； 信號干擾； 動態(tài)分配

中圖分類號： TN911.22?34 文獻標識碼： A 文章編號： 1004?373X（2016）15?0005?03

Abstract： The channel reuse technology is used in cellular network to improve the capacity of mobile communication and communication quality to a great extent. However， the electronic jamming problems with varying degrees can be generated in the process of channel reuse， which makes the effect of channel reuse weaken. The traditional channel optimization methods are massive， but the effect of them is undesirable. The dynamic allocation of cellular network access channel based on genetic algorithm is studied. For the interference problems appearing in the channel frequently， the mathematical model was established by adding some constraint conditions to obtain a channel allocation scheme with minimum interference signal， and avoid the common interference problems of mobile users to a great extent.

Keywords： genetic algorithm； channel reuse； signal interference； dynamic allocation

0 引 言

現(xiàn)在的移動通信主要采用蜂窩移動通信技術，移動通信用戶的增長率非?？?，為了提高移動通信的質(zhì)量和效率，需要充分利用信道復用技術，這樣就能在很大程度上提高移動通信的容量和資源的使用頻率。但是，信道復用技術本身是有缺陷的：信道復用會產(chǎn)生電子干擾從而使得移動通信的質(zhì)量大打折扣。所以，需要采用各種優(yōu)化算法進行信道分配。蜂窩網(wǎng)絡信道分配問題就是一個優(yōu)化問題，也是一個優(yōu)化方面的難題?？梢赃M行信道分配優(yōu)化的算法很多：神經(jīng)網(wǎng)絡算法、粒子優(yōu)化算法、模擬退火算法等。但是這些算法在解決信道分配方面的優(yōu)化結構上都不是很理想。本文研究的是基于遺傳算法的蜂窩網(wǎng)絡接入信道動態(tài)分配方案，主要目的是解決移動蜂窩網(wǎng)絡中的幾種主要干擾問題。

1 遺傳算法概述

遺傳算法是一種智能型的搜索算法，能夠利用遺傳算法計算解空間滿足約束條件的最優(yōu)解，遺傳算法求解空間最優(yōu)解的步驟主要包括編碼、初始化、適應值函數(shù)確定、選擇、交叉和變異等幾個基本的步驟。

（1） 編碼：在解空間中搜索最優(yōu)解的過程中，首先要將數(shù)據(jù)編碼成一個字符串，這個字符串就是遺傳算法中的一個基因型數(shù)據(jù)，這些數(shù)據(jù)在字符串中會進行不同的組合，這樣就形成了不同的基因型字符串。

（2） 生成初始種群：初始種群的生成是隨機的，選擇[N]個隨機的初始字符串，每個字符串可以作為一個染色體，[N]個染色體就是一個最初的群體，也是遺傳算法開始迭代的種群。

（3） 適應值函數(shù)的確定：適應性函數(shù)的作用是能夠表示最終的解空間的解是優(yōu)是劣。所以，針對問題的不同適應值函數(shù)也是不一樣的。

（4） 選擇：要進行最優(yōu)解的尋找，就要從當前種群中找到最為優(yōu)良的染色體做為父代進行繁殖，找到這個優(yōu)良父代的過程就是選擇。進行選擇的依據(jù)是達爾文的適者生存原則，只有能夠達到最佳適用性的父代才能被選擇繼續(xù)下去，這樣的父代會為下一代貢獻更多的后代。

（5） 交叉：交叉操作是將兩個染色體中的數(shù)據(jù)進行交換，從而可以產(chǎn)生新的染色體，也就是交叉可以產(chǎn)生新一代的個體，這些新個體能夠將其父輩的特性進行組合。

（6） 變異：在某一代的群體中隨機選擇一個個體，然后對這個個體中的數(shù)據(jù)按照某種規(guī)律進行隨機的變化，這就是遺傳算法的變異。遺傳算法就是模擬生物的進化，所以遺傳算法的變異概率是很低的，一般在0.001～0.01之間。通過遺傳算法的變異操作有可能產(chǎn)生新的個體。

遺傳算法在解空間中搜索最優(yōu)解的流程如圖1所示。

2 蜂窩網(wǎng)絡拓撲結構

蜂窩網(wǎng)絡之所以被廣泛應用于移動通信中，是因為數(shù)學領域的一個定理。如果一個平面以多個同半徑的圓形覆蓋，當圓心和正六邊形網(wǎng)格的各正六邊形中心重合，也就是圓心在正三角網(wǎng)格的格點上時，圓的數(shù)量是最少的。雖然，在實際的移動通信中可以采用圓形結構實現(xiàn)網(wǎng)絡的構建，但是這樣做的成本是比較高的。所以，從節(jié)約成本的角度考慮，移動通信的網(wǎng)絡建設采用了正三角網(wǎng)格，也就是簡單六角網(wǎng)格這也是蜂窩網(wǎng)絡的由來。

之所以在個人移動通信服務系統(tǒng)中使用蜂窩網(wǎng)絡的拓撲結構是因為蜂窩網(wǎng)絡能夠提高移動通信的效率和網(wǎng)絡的有效利用率。蜂窩網(wǎng)絡的拓撲結構如圖2所示。

從圖2可以看出，蜂窩網(wǎng)絡中的每個蜂窩都表示一個小區(qū)，小區(qū)的大小不是固定的，需要根據(jù)其實際的大小和整個蜂窩網(wǎng)絡的總用戶數(shù)來確定。如果是在用戶密集的區(qū)域設置蜂窩網(wǎng)絡，需要采用的小區(qū)必須是小尺寸的。還有的情況下，用戶會有較高的平均運動速度，這種情況下，采用的小區(qū)尺寸適合大尺寸的。另外，如果是用戶密度較低的區(qū)域，也適合大尺寸的小區(qū)。

3 信道動態(tài)分配方案設計

3.1 信道動態(tài)分配數(shù)學建模

在進行數(shù)學建模時，要充分考慮所有的約束問題，本研究的約束主要有三種：同頻約束、鄰頻約束和同位置約束。所以，首先要建立一個兼容矩陣：[C=cij，]如果小區(qū)為[n]個，那么[C]就可以設置為[n×n]的對稱矩陣。該矩陣用來表示小區(qū)之間的頻率兼容性的大小。[cij]表示第[i]個小區(qū)和第[j]個小區(qū)之間的信道間隔，也就是同頻約束和鄰頻約束。而在對角線上的所有元素[cii]表示在同一個小區(qū)內(nèi)分配的任意兩個信道之間的最小間隔的大小，也就是同位置約束。

每個小區(qū)的話務需求量不同，所以需要先建立一個小區(qū)話務需求向量[D=di，][n]個小區(qū)的信道需求關系就可以描述為一個[1×n]的向量，[di]就是第[i]個小區(qū)內(nèi)的信道數(shù)量，如果小區(qū)需求的話務量發(fā)生了變化，[di]也隨著發(fā)生變化。

假設蜂窩網(wǎng)絡中的可用信道數(shù)量為[m]個，就可以采用[n×m]的二維矩陣[F=fij]表示信道的分配方案，用矩陣的列表示信道數(shù)目，行表示小區(qū)的數(shù)目，如果信道[j]是分配給小區(qū)[i]的，就將[fij]設置為1，否則為0。小區(qū)和信道的關系不可以違反三種兼容約束，所以需要建立一個違反矩陣[Ncell=ncellij，]如果小區(qū)[i]與[j]之間違反兼容約束，則[ncellij]就設置為1，否則設置為0。還需要對小區(qū)之間違反兼容約束的信道數(shù)目進行描述，所以再建立一個矩陣[Nch=nchij，][nchij]就是小區(qū)[i]與小區(qū)[j]之間違反兼容約束的信道數(shù)目，如果信道[f1]是分配給小區(qū)[i]的一個信道，[f2]是分配給小區(qū)[j]的一個信道，如果[f2-f1

式中：[cmini]就是小區(qū)[i]內(nèi)實際分配信道的最小間隔距離。[cii]就是要滿足同位置約束時同小區(qū)內(nèi)分配的信道的最小間隔距離。式（1）就是要實現(xiàn)的目標函數(shù)，使得小區(qū)間違反兼容約束的小區(qū)和信道的數(shù)量都要達到最小；式（2）表示同一小區(qū)內(nèi)的信道數(shù)要滿足話務需求；式（3）表示同一小區(qū)內(nèi)的最大用戶數(shù)不能大于設置的小區(qū)容量，也就是[mcii]；式（4）表示同一小區(qū)內(nèi)設計分配的信道的最小間隔必須大于或者等于同位置約束。其中， [1≤i≤n，1≤j≤n]。

3.2 信道動態(tài)分配策略

（1） 定義適用值函數(shù)

設定一個最小目標函數(shù)[O（F），]可以將適應值函數(shù)設定為：[f（F）=max1O（F），]這就是信道分配方案[F]的適應值。如果能得到越小的函數(shù)值，得到的適應值就越大，所以本研究的目標就是能夠找到一組能夠使得適應值[f（F）]最大的信道分配方案。

（2） 編碼及解碼

信道分配方案中，需要在同一小區(qū)中設置一個信道中的最小頻率間隔，所以本研究中選取的編碼方案為：假設有[q]個話務請求 ，用長度為[p]的二進制串表示個體，[dmin]表示連續(xù)元素間的最小間隔，[dmin]的第一位用1表示，它后面的[dmin-1]個0用[1]表示。然而，當1的位置不是在[dmin]的第一個位置，而是在后面的[dmin-1]個位置時，編碼就會出現(xiàn)問題，所以本研究在初始的二進制串編碼中，就在[p]個二進制串的后面補了[dmin-1]個0，這樣，二進制串的長度就發(fā)生了變化，變?yōu)閇p+dmin-1。]

小區(qū)信道分配采用的是最小間隔編碼法，[1]被解碼為1和[dmin-1]個0，每個個體的長度為[p+dmin-1，]需要將[dmin-1]個0減去，這樣就得到了一個動態(tài)信道分配矩陣[F，]也就知道信道是如何在每個小區(qū)內(nèi)實際分配的。

（3） 選擇策略

本研究采用的選擇策略是輪盤賭選擇法，該方法的選擇依據(jù)同樣是個體適應值的大小，如果個體適應值小它就很有可能被丟棄，如果個體的適應值大，它被選中的概率就大。為了保證最佳個體在選擇和交叉的過程中不被丟失，本研究還在算法的實施過程中設置了最佳個體保存策略，通過該策略就能保存每一代的最佳個體，把最佳個體復制到下一代，用其替換最差個體，這樣就能保證群體中的最佳個體越來越多，最快的達到最終結果，提高了算法的收斂速度。

（4） 交叉算子

需要在最小間隔編碼的種群中進行交叉操作，需要交叉的是兩個染色體，通過交叉產(chǎn)生新的后代。本研究采用的是固定交叉算子，這樣能夠保證在交叉的過程中，始終滿足信道分配需求。

設定兩個染色體分別為[A]和[B，]創(chuàng)建一個棧，如果染色體的對應位置的兩個基因值[Ak]和[Bk]異或為1，也就是[Ak]和[Bk不]不能同時為1或者同時為0，就把當前的[k]放進棧中。隨機產(chǎn)生兩個交叉點[c1]和[c2，]將這兩點交叉，從[c1]開始向[c2]進行遍歷，如果在一個點[i]使得[Ai]和[Bi]異或不為1，把[i]放入其中，然后繼續(xù)，直到找到另一點[j]使得[Aj]和[Bj]異或為1。然后，比較[Aj]和棧頂元素[As1，]如果[Aj]等于[As1，]把[j]推進棧中，否則，交換 [（Aj，Bj）]和[（As1，Bs1），]將[s1]從棧中彈出。重復上述操作直到遍歷到[c2。]

（5） 變異算子

染色體的變異過程同樣需要滿足信道的分配需求，所以本研究采用的變異算法也是固定的。變異操作在最小間隔編碼的種群中進行，先根據(jù)變異率選出需要變異的基因[bi，]然后按照隨機的方式選中一個位置[j，]取出[j]對應的基因[bj，]如果[bi]和[bj]異或為1，就將[bi]和[bj]交換。

4 結 語

本文提出了一種動態(tài)信道分配方案，該方案利用遺傳算法在建立數(shù)學模型時，對常見的對信道復用有影響的幾種電子干擾進行了約束，在進行動態(tài)信道分配時，利用建立的數(shù)學模型得到了一組干擾最小的信道動態(tài)分配方案。

參考文獻

[1] 王聯(lián)國，洪 毅，趙付青，等.一種改進的人工魚群算法[J].計算機工程，2008，34（19）：192?193.

[2] 于雪晶，麻肖妃，夏斌，等.動態(tài)粒子群優(yōu)化算法[J].計算機工程，2010，36（4）：193?197.

[3] 黨安紅，張敏，朱世華，等.一種新的優(yōu)化動態(tài)信道分配策略及建模分析[J].電子學報，2004，32（7）：1152?1155.

[4] 張敏，黨安紅.一種基于改進神經(jīng)網(wǎng)絡的動態(tài)信道分配算法[J].計算機工程與應用，2005（28）：124?126.

[5] 盧瑜.遺傳算法在移動通信傳輸領域的應用[J].工會博覽，2009（1）：56?57.

[6] 何迪，賈振紅.基于混洗蛙跳算法的頻率分配方法[J].計算機工程，2011，37（21）：133?135.

[7] LIMA M A C， ARAUJO A F R， CESAR A C. Adaptive genetic algorithms for dynamic channel assignment in mobile cellular communication systems [J]. IEEE transactions on vehicular technology， 2007， 56（5）： 2685?2696.

[8] 徐俊杰，忻展紅.基于微正則退火的頻率分配方法[J].北京郵電大學學報，2007，30（2）：67?70.

[9] 朱志宇，姜長生.基于混沌神經(jīng)網(wǎng)絡移動通信信道分配方法研究[J].電子與信息學報，2005，27（9）：1429?1432.

[10] 朱曉錦，陳艷春，邵勇，等.面向信道分配的分段退火混沌神經(jīng)網(wǎng)絡模型[J].通信學報，2008，29（5）：122?127.

[11] VIDYARTHI G， NGOM A， STOJMENOVIC I. A hybrid channel assignment approach using an efficient evolutionary strategy in wireless mobile networks [J]. IEEE transactions on vehicular technology， 2005， 54（5）： 1887?1895.

[12] 尹燕飛，張遠平.基于免疫策略的信道資源分配算法[J].計算機工程與應用，2008，44（29）：125?127.

[13] JOSE?REVUELTA L M S. A new adaptive genetic algorithm for fixed channel assignment [J]. Information sciences， 2007， 177（13）： 2655?2678.

[14] 鞏敦衛(wèi)，孫曉燕.協(xié)同進化遺傳算法理論及應用[M].北京：科學出版社，2009：15?19.

[15] 高家全，何桂霞.并行遺傳算法研究綜述[J].浙江工業(yè)大學學報，2007，35（1）：56?59.