遺傳算法蜂窩網(wǎng)絡(luò)信道分配中的應(yīng)用

謝日星

?

遺傳算法蜂窩網(wǎng)絡(luò)信道分配中的應(yīng)用

謝日星

武漢軟件工程職業(yè)學(xué)院王路群工作室，湖北 武漢 430000

現(xiàn)在移動(dòng)通信的主流拓?fù)浣Y(jié)構(gòu)——蜂窩網(wǎng)絡(luò)中，使用信道復(fù)用技術(shù)能夠在很大程度上提高移動(dòng)通信的容量和通信質(zhì)量。但是，信用復(fù)用過程中會(huì)產(chǎn)生不同程度的電子干擾問題，這些問題使得信道復(fù)用的作用大打折扣。研究嘗試?yán)眠z傳算法進(jìn)行蜂窩網(wǎng)絡(luò)接入信道的動(dòng)態(tài)分配，在很大程度上避免了移動(dòng)用戶常見的電子干擾問題。

遺傳算法；信道復(fù)用；信號(hào)干擾；動(dòng)態(tài)分配

21世紀(jì)科學(xué)技術(shù)的飛速發(fā)展使信息與通信技術(shù)達(dá)到了空前高度，傳統(tǒng)的通信模式已經(jīng)不能滿足人們對通信的質(zhì)量和效率日益高漲的需求，于是，在通信技術(shù)上開始了傳統(tǒng)技術(shù)的更新，出現(xiàn)了新的通信技術(shù)。現(xiàn)在的移動(dòng)通信主要還是蜂窩移動(dòng)通信技術(shù)。現(xiàn)在的移動(dòng)通信用戶的增長率非常快，為了提高移動(dòng)通信的質(zhì)量和效率，需要充分利用信道復(fù)用技術(shù)，這樣就能在很大程度上提高移動(dòng)通信的容量和資源的使用頻率。但是，信道復(fù)用技術(shù)是本身是有缺陷的，信道復(fù)用會(huì)產(chǎn)生電子干擾，從而使得移動(dòng)通信的質(zhì)量大打折扣。所以，需要采用各種優(yōu)化算法來進(jìn)行信道的分配。蜂窩網(wǎng)絡(luò)信道分配問題就是一個(gè)優(yōu)化問題，也是一個(gè)優(yōu)化方面的難題。可以進(jìn)行信道分配優(yōu)化的算法很多：神經(jīng)網(wǎng)絡(luò)算法、粒子優(yōu)化算法、模擬退火算法等。但是這些算法在解決信道分配方面的優(yōu)化結(jié)構(gòu)都不是很理想。本文研究的是基于遺傳算法的蜂窩網(wǎng)絡(luò)接入信道動(dòng)態(tài)分配方案。主要的目的是解決移動(dòng)蜂窩網(wǎng)絡(luò)中的幾種主要的干擾問題。[1]

1 蜂窩網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)

蜂窩網(wǎng)絡(luò)或移動(dòng)網(wǎng)絡(luò)（Cellular network）是一種移動(dòng)通信硬件架構(gòu)，移動(dòng)通信的整個(gè)服務(wù)區(qū)被分為正六邊形的小區(qū)，每個(gè)小區(qū)有一個(gè)基站，這種結(jié)構(gòu)就像“蜂窩”一樣，所以稱為蜂窩網(wǎng)絡(luò)。[2]

之所以在個(gè)人移動(dòng)通信服務(wù)系統(tǒng)中使用蜂窩網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)就是因?yàn)榉涓C網(wǎng)絡(luò)能夠提高移動(dòng)通信的效率和網(wǎng)絡(luò)的有效利用率。所以，現(xiàn)在的移動(dòng)通信中大多數(shù)的蜂窩網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)都如圖1所示。

圖1 蜂窩網(wǎng)絡(luò)簡單拓?fù)浣Y(jié)構(gòu)

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

2 信道動(dòng)態(tài)分配方案設(shè)計(jì)

2.1 信道動(dòng)態(tài)分配數(shù)學(xué)建模

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

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

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

（2）

（3）

2.2 信道動(dòng)態(tài)分配策略

（1）定義適用值函數(shù)。本研究就是要設(shè)定一個(gè)最小目標(biāo)函數(shù)O（F），所以可以將適應(yīng)值函數(shù)設(shè)定為：f（F）=max{1/O（F）}，這就是信道分配方案F的適應(yīng)值。如果能得到越小的函數(shù)值，得到的適應(yīng)值就越大，所以本研究的目標(biāo)就是能夠找到一組能夠使得適應(yīng)值f（F）最大的信道分配方案。

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

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

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

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

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

3 結(jié)語

現(xiàn)在移動(dòng)通信基本上使用的都是蜂窩網(wǎng)絡(luò)，使用信道服用技術(shù)能夠在很大程度上提高移動(dòng)通信的容量和通信質(zhì)量。但是，信用復(fù)用過程中會(huì)產(chǎn)生不同程度的電子干擾問題，這些問題使得信道復(fù)用的作用大打折扣。傳統(tǒng)的進(jìn)行信道優(yōu)化的方法有神經(jīng)網(wǎng)絡(luò)算法、粒子優(yōu)化算法、模擬退火算法，但是效果都不是很理想。[6]本研究提出了一種動(dòng)態(tài)信道分配方案，該方案利用遺傳算法在建立數(shù)學(xué)模型時(shí)，對常見的對信道復(fù)用影響的幾種電子干擾進(jìn)行了約束，在進(jìn)行動(dòng)態(tài)信道分配時(shí)，利用建立的數(shù)學(xué)模型，得到了一組干擾最小的信道動(dòng)態(tài)分配方案。

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

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

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

[4]盧瑜.遺傳算法在移動(dòng)通信傳輸領(lǐng)域的應(yīng)用[J].工會(huì)博覽，2009（1）：56-57.

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

[6]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.

謝日星（1973—），男，漢族，江西興國人，武漢軟件工程職業(yè)學(xué)院王路群工作室副教授，工學(xué)碩士，研究方向?yàn)檐浖_發(fā)、信息安全研究。

TP18；TN929.5

A

1009-6434（2016）04-0060-02