固定頻率分配問(wèn)題的綜述*

佈仁巴圖

(內(nèi)蒙古大學(xué)數(shù)學(xué)科學(xué)學(xué)院，內(nèi)蒙古呼和浩特010021)

固定頻率分配問(wèn)題的綜述*

佈仁巴圖

(內(nèi)蒙古大學(xué)數(shù)學(xué)科學(xué)學(xué)院，內(nèi)蒙古呼和浩特010021)

本文對(duì)固定頻率分配問(wèn)題進(jìn)行了簡(jiǎn)單的介紹，敘述了固定頻率分配問(wèn)題中所考慮的干擾因素、數(shù)學(xué)模型，并且討論了固定頻率分配問(wèn)題的一些典型的算法。

固定頻率分配;干擾因素;算法

1 引言

無(wú)限電頻率是一種有限的資源，隨著移動(dòng)通信網(wǎng)絡(luò)的飛速發(fā)展，移動(dòng)通信設(shè)備已經(jīng)成為了人們?cè)谌粘Ｉ钪胁豢扇鄙俚耐ㄓ嵐ぞ摺８鶕?jù)聯(lián)合國(guó)有關(guān)機(jī)構(gòu)調(diào)查，在2014年初，手機(jī)用戶超過(guò)70億，目前世界71億人口中68億手機(jī)用戶。根據(jù)工業(yè)與信息化部網(wǎng)站數(shù)據(jù)顯示，隨著服務(wù)能力持續(xù)提升，截至2014年中國(guó)大陸手機(jī)用戶已經(jīng)超過(guò)了14.77億。高速增長(zhǎng)的用戶數(shù)量，即頻率使用需求量與有限的頻率資源之間的矛盾越來(lái)越激烈。如何將有限的頻率資源合理的分配面臨著一個(gè)新的挑戰(zhàn)。所以研究頻率分配問(wèn)題是一個(gè)非常有意義的工作。

頻率分配問(wèn)題是一種典型的NP－Complete組合優(yōu)化問(wèn)題，而固定頻率分配問(wèn)題是最典型的、最常用的一類(lèi)頻率分配問(wèn)題。過(guò)去常用的頻率分配算法有:啟發(fā)式算法、圖形著色算法等等。這些算法求解頻率分配問(wèn)題時(shí)，花費(fèi)時(shí)間較長(zhǎng)，效果也不太理想。近年來(lái)，隨著利用計(jì)算機(jī)模仿人類(lèi)電腦、生命進(jìn)化過(guò)程、生物群體行為、物理現(xiàn)象的智能技術(shù)和智能算法的發(fā)展，出現(xiàn)一些智能優(yōu)化算法來(lái)解決頻率分配問(wèn)題。如遺傳算法、禁忌搜索算法、模擬退火算法、蟻群算法、粒子群優(yōu)化算等等。

2 頻率分配問(wèn)題的相關(guān)知識(shí)

2.1 固定頻率分配問(wèn)題的簡(jiǎn)介

這是典型的一種頻率分配方式。是在固定的頻率集合下，將服務(wù)區(qū)域被分成多個(gè)蜂窩小區(qū)，根據(jù)每個(gè)小區(qū)的頻率使用數(shù)據(jù)需求和電磁干擾約束對(duì)各個(gè)小區(qū)進(jìn)行分配頻率，使求得總干擾數(shù)最小化的分配方案。

2.2 頻率復(fù)用

頻率復(fù)用的原理是源于無(wú)線電波傳播路徑損耗特性的，即如果兩個(gè)小區(qū)之間距離足夠大，那么用于一個(gè)小區(qū)的頻率可以在另一個(gè)小區(qū)上同時(shí)復(fù)用，這樣可以提高頻率的利用率。

2.3 電磁干擾約束

由于電磁波在傳播過(guò)程中，遇到相同或相近的電磁波時(shí)，出現(xiàn)一些電磁干擾。在頻率分配問(wèn)題中主要考慮的干擾有:同頻干擾、鄰頻干擾、同址干擾、互調(diào)干擾。

(1)同頻干擾約束(Co－Channel－Constraints.簡(jiǎn)稱(chēng)CCC)

在分配頻率時(shí)，在距離較近的兩個(gè)或多個(gè)小區(qū)內(nèi)同時(shí)不能分配相同的頻率，必須在干擾范圍以外的小區(qū)內(nèi)可以同時(shí)分配同樣的頻率。

(2)鄰頻干擾約束(Adjacent－Channel－Constraints.簡(jiǎn)稱(chēng)ACC)

在給兩個(gè)鄰近小區(qū)分配頻率時(shí)，必須滿足所要分配的頻率間隔大于或等于某一個(gè)預(yù)先知道的特定值。也就是說(shuō)間隔較小的兩個(gè)或多個(gè)頻率不能分配給較近的小區(qū)。

(3)同址干擾約束(Co－site－Channel－Constraints.簡(jiǎn)稱(chēng)CSC)

對(duì)于給某一個(gè)小區(qū)內(nèi)分配頻率時(shí)，也需要滿足所分配的頻率間隔大于或等于某一個(gè)預(yù)先知道的特點(diǎn)值。也就是說(shuō)間隔較小的兩個(gè)或多個(gè)頻率不能分配給同一個(gè)小區(qū)。

(4)三階互調(diào)干擾約束(Third－Order－Interception－Constraints.簡(jiǎn)稱(chēng)TOIC)，互調(diào)干擾是指分配某一個(gè)小區(qū)的頻率fi和頻率fj經(jīng)過(guò)非線性作用后出現(xiàn)的新頻率fk，接近或相同本小區(qū)或者相鄰小區(qū)的頻率時(shí)產(chǎn)生的干擾。可以分為二階互調(diào)干擾、三階互調(diào)干擾等等。其中三階互調(diào)干擾是最嚴(yán)重的互調(diào)干擾。

由頻率fi和頻率fj產(chǎn)生的二階、三階、四階互調(diào)干擾下產(chǎn)生的新頻率(或產(chǎn)生物)可以定義如下:

(ⅰ)由頻率fi和頻率fj產(chǎn)生的二階互調(diào)產(chǎn)生物:fi±fj;

(ⅱ)由頻率fi和頻率fj產(chǎn)生的三階互調(diào)產(chǎn)生物:fi± 2fj，2fi±fj，fj－2fi，2fj－fi;

(ⅲ)由頻率fi和頻率fj產(chǎn)生的四階互調(diào)產(chǎn)生物:2fi± 2fj，3fi±fj，3fj±fi，fi－3fj，fj－3fi。

3 固定頻率分配問(wèn)題的數(shù)學(xué)模型

1982年A.Gamst和W.Rave提出了頻率分配問(wèn)題的經(jīng)典數(shù)學(xué)模型，在該模型中構(gòu)造了一個(gè)兼容矩陣C，假設(shè)小區(qū)的個(gè)數(shù)為N，則這個(gè)兼容矩陣就是一個(gè)N×N維的對(duì)稱(chēng)矩陣，即形式為:

其中矩陣C的元素cij表示分配給小區(qū)i和小區(qū)j的頻率最小頻率間隔，cij=0表示小區(qū)i和小區(qū)j可以復(fù)用頻率，對(duì)角元素cij(i=j)表示小區(qū)i(或小區(qū)j)的同址干擾約束，即小區(qū)i(或小區(qū)j)中頻率之間所需要的最小間隔。除了兼容矩陣之外還需要構(gòu)建各小區(qū)所需要的頻率個(gè)數(shù)向量D，即形式為:

其中需求向量D的元素di，表示第i小區(qū)的頻率需求個(gè)數(shù)。

數(shù)學(xué)模型1:

其中

則，固定頻率分配策略的數(shù)學(xué)模型為:

s．t

數(shù)學(xué)模型2:

其中

小區(qū)i的需求約束可以描述為:

小區(qū)i的同址干擾(CSC)約束可以描述為

小區(qū)i與小區(qū)j的同頻干擾(CCC)、鄰頻干擾(ACC)約束可以描述為:

則，電磁兼容約束函數(shù)為:

(其中α+β=1)則，固定頻率分配策略的數(shù)學(xué)模型為:

4 固定頻率分配問(wèn)題的算法研究

4.1 啟發(fā)式算法(Heuristic－Algorithm.簡(jiǎn)稱(chēng)HA)

4.1.1 頻率窮舉搜索算法(Frequency－Exhaust－Algorithm.簡(jiǎn)稱(chēng)FEA)

從小區(qū)列表的頂部開(kāi)始，將當(dāng)前頻率分配給當(dāng)前小區(qū)，如果頻率不與已分配好的頻率發(fā)生沖突，則將該頻率分配給當(dāng)前小區(qū)，否則試探下一個(gè)頻率是否合適，直到所有頻率全部試探完畢。

4.1.2 需求窮舉搜索算法(Requirement－Exhaust－Algorithm.簡(jiǎn)稱(chēng)REA)

將從第一個(gè)頻率開(kāi)始，將當(dāng)前頻率按小區(qū)列表的順序逐一進(jìn)行試探性地分配，如果當(dāng)前頻率能夠?qū)σ呀?jīng)分配好的頻率不產(chǎn)生干擾，則將該頻率分配給當(dāng)前小區(qū)。否則繼續(xù)試探下一個(gè)小區(qū)是否適合，直至所有小區(qū)試探完畢。

4.1.3 后向回溯算法(After－the－Backtracking－Algorithm.簡(jiǎn)稱(chēng)ATBA)

后向回溯是最簡(jiǎn)單的窮舉搜索算法，小區(qū)被順序分配頻率.首先從頻率集合D中取出頻率fk分配給小區(qū)i，即fik=1 .然后檢查已經(jīng)分配頻率的小區(qū)j，j＜i是否有違反約束的情況發(fā)生.如果沒(méi)有違反，則接著進(jìn)行下一個(gè)小區(qū)的頻率分配，這一步驟稱(chēng)為前向移動(dòng)。如果有違反，則從頻率集合中取出下一個(gè)頻率分配給小區(qū)i，即fik+1=1，如果頻率集合D中所有的頻率都不能滿足所有約束，則回溯一步，對(duì)前一個(gè)小區(qū)i－1重新進(jìn)行頻率分配。

4.1.4 前向檢測(cè)算法(Former－to－the－Backtracking－Algorithm.簡(jiǎn)稱(chēng)FTTBA)

4.2 智能算法(Intelligent－Algorithm.簡(jiǎn)稱(chēng)IA)

4.2.1 遺傳算法(Genetic－Algorithm.簡(jiǎn)稱(chēng)GA)

遺傳算法是20世紀(jì)70年代由美國(guó)密執(zhí)安(Michigan)大學(xué)約翰·霍蘭德(John.Holland)教授提出的一種模擬生物在自然環(huán)境中的遺傳和進(jìn)化過(guò)程而形成的自適應(yīng)的全局優(yōu)化概率搜索算法，

遺傳算法求解固定頻率分配問(wèn)題時(shí)，首先對(duì)實(shí)際的頻率分配問(wèn)題進(jìn)行編碼，解決頻率分配問(wèn)題時(shí)常用的編碼方式有:二進(jìn)編碼、最小間隔編碼、實(shí)數(shù)編碼。

讓后產(chǎn)生初始種群進(jìn)行交叉、變異操作，最后對(duì)個(gè)別個(gè)體進(jìn)行局部尋優(yōu)。

4.2.2 蟻群算法(Ant－Colony－Algorithm.簡(jiǎn)稱(chēng)ACA)

蟻群算法是由意大利學(xué)者馬克·多里戈(Marco Dorigo)在1991年提出的模仿群體在尋找食物或?qū)ふ一爻驳穆窂綍r(shí)，根據(jù)它們前面螞蟻留下的化學(xué)物質(zhì)，稱(chēng)之為“信息激素(Pheromone)”作為信息，尋找信息素濃度較大的路徑的群體行為的一種優(yōu)化算法。

蟻群算法求解固定頻率分配問(wèn)題時(shí)，首先需要構(gòu)造有N個(gè)頂點(diǎn)，每對(duì)頂點(diǎn)之間有M條邊的多邊圖G。假設(shè)系統(tǒng)有q只螞蟻，則每一只螞蟻?zhàn)哌^(guò)多邊圖G的路徑代表一種頻率分配方案。

4.2.3 粒子群算法(Particle－Swarm－Algorithm.簡(jiǎn)稱(chēng)PSA)

粒子群算法是1995年由美國(guó)心理學(xué)家肯尼迪(James Kennedy)和電氣工程師埃伯哈特(Russell Eberhart)提出的一種模仿鳥(niǎo)群尋覓食物行為的智能算法。

粒子群算法求解固定頻率分配問(wèn)題時(shí)，首先將每一種頻率分配方案類(lèi)比于搜索空間的一個(gè)無(wú)質(zhì)量、無(wú)體積、有速度的粒子。然后隨機(jī)的選擇初始種群，進(jìn)行迭代，在每次迭代中每一個(gè)粒子往歷史局部最優(yōu)解Pbest方向飛行。

4.2.4 模擬退火算法(Simulated－Annealing－Algorithm.簡(jiǎn)稱(chēng)SAA)

模擬退火算法是由米特羅波利斯(Metropolis)在1953提出的一種優(yōu)化算法，在1983年柯克帕特里克(Kirkpatrick)將模擬退火算法成功地應(yīng)用在組合優(yōu)化問(wèn)題領(lǐng)域。

5 總結(jié)和展望

本文從固定頻率分配策略中主要考慮的電磁干擾約束、數(shù)學(xué)模型、典型的算法等幾個(gè)方面對(duì)固定頻率分配問(wèn)題進(jìn)行了總結(jié)。固定頻率分配問(wèn)題是頻率分配問(wèn)題的一類(lèi)典型的、過(guò)去常用的頻率分配策略。由于在實(shí)際通信網(wǎng)絡(luò)中，每個(gè)小區(qū)的頻率使用需求是隨著時(shí)間、空間等因素發(fā)生變化的。然而固定頻率分配策略中所討論的小區(qū)頻率需求是固定的。為了克服固定頻率分配策略對(duì)頻率使用需求的時(shí)間和空間變化缺乏自適應(yīng)性的缺，出現(xiàn)了點(diǎn)動(dòng)態(tài)頻率分配策略、混合頻率分配策略等新的頻率分配策略。目前頻率分配問(wèn)題的大部分算法都集中在固定頻率分配問(wèn)題的研究，研究動(dòng)態(tài)頻率分配、混合頻率分配策略的算法很少。

［1］孫媛媛.基于遺傳算法的GSM網(wǎng)絡(luò)頻率規(guī)劃優(yōu)化研究與應(yīng)用［D］.北京郵電大學(xué)，2008.

［2］W Gamst，Rave.On Frequency Assignment in Mobile Automatic Telephone Systems［J］.In.Proc.GIOBLECOM，1982，82:309－315.

［3］趙秋紅，肖依永.基于單點(diǎn)搜索的元啟發(fā)式算法［M］.北京:科學(xué)出版社，2013.

［4］古邦倫.電磁頻譜管理中的頻率分配技術(shù)研究［D］.國(guó)防科學(xué)技術(shù)大學(xué)，2006.

［5］郭文志，陳國(guó)龍.離散粒子群優(yōu)化算法及其應(yīng)用［M］.北京:清華大學(xué)出版社，2012.

［7］韋景俐.離無(wú)線電網(wǎng)絡(luò)規(guī)劃中的頻率規(guī)劃研究［D］.北京郵電大學(xué)，2012.

［8］范曉光.頻率分配算法適用性研究.［D］解放軍信息工程大學(xué)，2010:2－37.

［9］高亞男.有效的優(yōu)化算法在頻率分配上的應(yīng)用［D］.新疆大學(xué)，2010:21－43.

［10］石飛.GSM無(wú)線網(wǎng)絡(luò)優(yōu)化中的有效的頻率分配方法的研究［D］.新疆大學(xué)，2012:21－43.

［11］何迪.基于選擇性變異技術(shù)的頻率分配方法［D］.新疆大學(xué)，2011:1－39，55－67.

［12］玄光男，程潤(rùn)偉.遺傳算法與工程優(yōu)化［M］.北京:清華大學(xué)出版社，1999.

Fixed Frequency Assignment Problem

Burenbatu
(School of Mathematical Sciences，Inner Mongolia University;Hohhot 010021)

In this paper，the fixed frequency assignment problem has carried on the simple introduction，describes the interference factors of fixed frequency assignment problem，mathematical model，and discusses the fixed frequency assignment problem of some typical algorithms.

fixed frequency assignment problem;interference constraints;algorithm

TN925

A

1004－1869(2014)02－0033－04

2014－04－12

佈仁巴圖(1987－)，男，蒙族，內(nèi)蒙古錫林郭勒人，2011級(jí)碩士研究生。