基于遺傳算法的蜂窩網絡接入信道動態分配方案的設計

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

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

中圖分類號： 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 引 言

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

1 遺傳算法概述

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

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

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

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

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

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

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

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

2 蜂窩網絡拓撲結構

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

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

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

3 信道動態分配方案設計

3.1 信道動態分配數學建模

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

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

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

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

3.2 信道動態分配策略

（1） 定義適用值函數

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

（2） 編碼及解碼

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

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

（3） 選擇策略

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

（4） 交叉算子

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

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

（5） 變異算子

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

4 結 語

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

參考文獻

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

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

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

[4] 張敏，黨安紅.一種基于改進神經網絡的動態信道分配算法[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].電子與信息學報，2005，27（9）：1429?1432.

[10] 朱曉錦，陳艷春，邵勇，等.面向信道分配的分段退火混沌神經網絡模型[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] 鞏敦衛，孫曉燕.協同進化遺傳算法理論及應用[M].北京：科學出版社，2009：15?19.

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