佈仁巴圖

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

固定頻率分配問題的綜述*

佈仁巴圖

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

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

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

1 引言

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

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

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

2.1 固定頻率分配問題的簡介

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

2.2 頻率復(fù)用

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

2.3 電磁干擾約束

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

(1)同頻干擾約束(Co－Channel－Constraints.簡稱CCC)

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

(2)鄰頻干擾約束(Adjacent－Channel－Constraints.簡稱ACC)

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

(3)同址干擾約束(Co－site－Channel－Constraints.簡稱CSC)

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

(4)三階互調(diào)干擾約束(Third－Order－Interception－Constraints.簡稱TOIC)，互調(diào)干擾是指分配某一個小區(qū)的頻率fi和頻率fj經(jīng)過非線性作用后出現(xiàn)的新頻率fk，接近或相同本小區(qū)或者相鄰小區(qū)的頻率時產(chǎn)生的干擾?？梢苑譃槎A互調(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 固定頻率分配問題的數(shù)學(xué)模型

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

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

其中需求向量D的元素di，表示第i小區(qū)的頻率需求個數(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 固定頻率分配問題的算法研究

4.1 啟發(fā)式算法(Heuristic－Algorithm.簡稱HA)

4.1.1 頻率窮舉搜索算法(Frequency－Exhaust－Algorithm.簡稱FEA)

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

4.1.2 需求窮舉搜索算法(Requirement－Exhaust－Algorithm.簡稱REA)

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

4.1.3 后向回溯算法(After－the－Backtracking－Algorithm.簡稱ATBA)

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

4.1.4 前向檢測算法(Former－to－the－Backtracking－Algorithm.簡稱FTTBA)

4.2 智能算法(Intelligent－Algorithm.簡稱IA)

4.2.1 遺傳算法(Genetic－Algorithm.簡稱GA)

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

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

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

4.2.2 蟻群算法(Ant－Colony－Algorithm.簡稱ACA)

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

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

4.2.3 粒子群算法(Particle－Swarm－Algorithm.簡稱PSA)

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

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

4.2.4 模擬退火算法(Simulated－Annealing－Algorithm.簡稱SAA)

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

5 總結(jié)和展望

本文從固定頻率分配策略中主要考慮的電磁干擾約束、數(shù)學(xué)模型、典型的算法等幾個方面對固定頻率分配問題進(jìn)行了總結(jié)。固定頻率分配問題是頻率分配問題的一類典型的、過去常用的頻率分配策略。由于在實際通信網(wǎng)絡(luò)中，每個小區(qū)的頻率使用需求是隨著時間、空間等因素發(fā)生變化的。然而固定頻率分配策略中所討論的小區(qū)頻率需求是固定的。為了克服固定頻率分配策略對頻率使用需求的時間和空間變化缺乏自適應(yīng)性的缺，出現(xiàn)了點動態(tài)頻率分配策略、混合頻率分配策略等新的頻率分配策略。目前頻率分配問題的大部分算法都集中在固定頻率分配問題的研究，研究動態(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］趙秋紅，肖依永.基于單點搜索的元啟發(fā)式算法［M］.北京:科學(xué)出版社，2013.

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

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

［7］韋景俐.離無線電網(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ǎng)絡(luò)優(yōu)化中的有效的頻率分配方法的研究［D］.新疆大學(xué)，2012:21－43.

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

［12］玄光男，程潤偉.遺傳算法與工程優(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級碩士研究生。