（电磁场与微波技术专业论文）频率分配算法及其应用.pdf

摘要 频率分配是一类最优化问题，在数学上是一个n p 完全问题，即完全多项式非确定性 问题，可以用穷举法得到答案，但是这样的算法，其计算的时间随问题的复杂程度成指数 增长，很快便变得不可计算了。在文献中，频率分配的算法一般有确定性算法、启发式算 法和计算智能方法三类，本文采用的遗传算法属于计算智能方法的一种。 论文的主要内容是首先论述频率分配技术和遗传算法的基本理论，然后给出一个g s m 移动通信系统频率分配的例子，使用遗传算法求解该例子的频率分配问题，使未满足约束 条件的次数尽量减小。同时通过这个例子分别对遗传算法的两种选择算子和两种交叉算子 的性能做比较。文章最后就如何设置遗传算法各个运行参数给出了自己的建议。 在论文的第四章中，结合给出的例子，详细介绍了使用遗传算法的各个步骤，每个步 骤都给出文字或者图形表达的编程思想。其中关于编码的策略在参考文献 1 3 】的基础上增 加了新的要求，使得从一开始同一小区内的频率相互之间便不存在干扰。为了和编码策略 相适应，在变异操作时也使用了特殊的变异算子。 第四章的试验结果表明在限定一定数量的可用频率的条件下，该算法能够使未满足约 束条件的次数尽量减小。在试验一和试验二中比较了遗传算法的选择算子和交叉算子的性 能，结论是在文章给出的例子中双点交叉操作优于单点交叉操作，确定式采样选择法优于 比例选择法。试验三比较了不同的变异概率对遗传算法性能的影响，变异概率耿值过大则 使遗传算法类似于随机搜索算法，取值过小则产生新个体的能力较弱。 关键词：频率分配遗传算法 a b s t r a c t t h ef r e q u e n c ya s s i g n m e n ti sac l a s so fn p - c o m p l e t ep r o b l e m s c o n v e n t i o n a l l y , t h i sk i n do f p r o b l e mc o u l db es o l v e db ye n u m e r a t i o n h o w e v e r , t h ec o m p u t a t i o n a lc o s to fe n u m e r a t i o n e x p o n e n t i a l l yi n c r e a s e sa st h eo r d e ro ft h ep r o b l e mg o e su p i nt h el i t e r a t u r e s ，t h e r ea r eb a s i c a l l y t h r e ec l a s s e so fa l g o r i t h m st os o l v et h i sp r o b l e m ：e x a c ta l g o r i t h m ，h e u r i s t i ca l g o r i t h ma n d c o m p u t a t i o ni n t e l l e c t i v ea l g o r i t h m t h eg e n e t i ca l g o r i t h m ，w h i c hb e l o n g st o t h ec l a s so f c o m p u t a t i o ni n t e l l e c t i v ea l g o r i t h m ，i se m p l o y e d i nt h i st h e s i s f i r s to fa l l ，t h ef r e q u e n c ya s s i g n m e n tt e c h n o l o g ya n dt h ep r i n c i p l eo fg e n e t i ca l g o r i t h ma l e i n t r o d u c e d ，a n df o l l o w e db ya ne x a m p l eo fs o l v i n gt h ef r e q u e n c ya s s i g n m e n tp r o b l e m o fag s m s y s t e m t h en u m b e ro fv i o l a t e d c o n s t r a i n t si s l a r g e l yr e d u c e dw i t h t h i s a l g o r i t h m t h e p e r f o r m a n c e so ft h es e l e c t i o no p e r a t o ra n dt h ec r o s s o v e ro p e r a t o ra l ec o m p a r e di nt h eg i v e n e x a m p l e s o m ea d v i c e sa r eg i v e na b o u th o w t os e tt h ep a r a m e t e ro f g e n e t i ca l g o r i t h m i nc h a p t e r4 ，t h eg e n e t i ca l g o r i t h mi sd e s c r i b e di nd e t a i l s b a s e do nt h ec o d i n gs t r a t e g yi n l i t e r a t u r e 13 ，an e wr e q u i r e m e n ti se n f o r c e di no r d e rt oe l i m i n a t et h ei n t e r f e r e n c e sa m o n g d i f f e r e n tf r e q u e n c i e si no n ec e l l t ob ec o n s i s t e n tw i t ht h ec o d i n gs t r a t e g y , an e wm u t a t i o n o p e r a t o ri su s e d i ti ss h o w ni nt h ee x p e r i m e n tt h a ta m o n gt h el i m i t e dn u m b e ro fa v a i l a b l ef r e q u e n c i e s ，t h e n u m b e ro fv i o l a t e dc o n s t r a i n t si sr e d u c e dw i t ht h i sa l g o r i t h m t h r o u g ht h ee x p e r i m e n t s ，i ti s f o u n dt h a tt i l et w o p o i n tc r o s s o v e ro p e r a t o ri sb e t t e rt h a nt h eo n e p o i n tc r o s s o v e ro p e r a t o r , t h ed e t e r m i n i s t i cs a m p l i n gi sb e t t e rt h a nt h ep r o p o r t i o n a lm o d e la n dt h em u t a t i o np o s s i b i l i t y s h o u l db ec h o s e nc a r e f u l l y k e yw o r d s ：f r e q u e n c ya s s i g n m e n t g e n e t i ca l g o r i t h m u 南京邮电大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的 地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包 含为获得南京邮电大学或其它教育机构的学位或证书而使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了 明确的说明并表示了谢意。 研究生始社瞒中以 南京邮电大学学位论文使用授权声明 南京邮电大学、中国科学技术信息研究所、国家图书馆有权保留 本人所送交学位论文的复印件和电子文档，可以采用影印、缩印或其 他复制手段保存论文。本人电子文档的内容和纸质论文的内容相一 致。除在保密期内的保密论文外，允许论文被查阅和借阅，可以公布 ( 包括刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权 南京邮电大学研究生部办理。 研究生始她导师始皴隰z 出肛 南京邮电大学硕+ 研究生学位论文 第一章绪论 第一章绪论 1 1 遗传算法发展现状简介 近年来，一种在思路和方法上别开生面的新的优化算法遗传算法( g e n e t i c a l g o r i t h m s ，简称g a s ) 正在迅速发展。遗传算法以其很强的解决问题的能力和广泛的适应 性渗透到研究与工程的各个领域，并取得了良好的效果。在国外，几种会议已设遗传算法 的专题，而且已有专门的遗传算法国际会议，每两年召开一次，目前为止，发表了数千篇 论文，对其基本理论、方法和技巧做了较充分的研究。今天，遗传算法的研究已成为国际 学术界跨学科的热门话题之一【l9 1 。 遗传算法的基本思想起源于达尔文的生物进化论，目前已用于科学研究和工程实际中 的种种搜索和优化问题，如管道线路优化、机器学习、模型识别，神经网络结构参数优化 及权重学习、精调模糊逻辑控制器、飞船控制系统优化等。 遗传算法是一种随机的全局多点搜索算法，同其它搜索方法，如随机查找、梯度下降、 模拟退火等算法相比的主要优点是简单、通用、鲁棒性强。遗传算法实现全局并行搜索， 搜索空间大，并且在搜索过程中不断地向可能包含最优解的方向调整搜索空间，以便寻找 到最优解或准最优解。用遗传算法解决的问题越复杂，目标越不明确，其优越性越明显。 由于遗传算法可以较有效求解组合优化和复杂函数的优化问题，目前许多学科的研究人员 都开始探索采用这种技术来解决各自学科中长期未能很好解决的困难的优化问题。 1 2 频率分配问题概述 在无线通信中，频率是最宝贵的资源。如何在无线通信中将有限的频率分配给数目庞 大的基站与终端群，就是频率分配问题( 简称f a p ) 从频率分配的策略来看，主要有以下几类【2 】： ( 1 ) 固定信道分配( f c a ，f i x e dc h a n n e la s s i g n m e n t ) 各个基站采用预先分配好 的频点或者频点组进行通信。 ( 2 ) 动态信道分配( d c a ，d y n a m i cc h a n n e la s s i g n m e n t ) 各个基站不预先分配 信道，而是根据网络的负载实时、自适应的调整信道分配。 ( 3 ) 混合信道分配( h c a ，h y b r i dc h a n n e la s s i g n m e n t ) 前两者的综合。 南京l | 1 i j 电大学硕一l 研究生学位论文第一苹鲜 论 这几种策略各有自己的使用场合。例如信号强、覆盖均匀的g s m 网络采用f c a 算法； 而为了信号较弱、覆盖区域不广的p h s 系统基站，则采用d c a 算法。 从频率分配的实现手段来看，主要有以下两类： ( 1 ) 基于协作( c o o r d i n a t i o n b a s e d ) 的分配基站使用的频点预先规划，或者随着 网络的使用情况由一个算法进行动态的规划，进行分配。 ( 2 ) 基于测量( m e a s u r e m e n t b a s e d ) 的分配基站不对频率进行规划，而是不断的 扫描其所处的无线环境，寻找可用的频点使用。 g s m 网络即是一个基于协作的分配，而p h s 网络则采用基于测量的分配。同样，这 两种分配手段也有其优点与缺点。 若采用基于协作的分配，必须对基站群规划他们的使用频点，以降低他们的同频干扰。 在文献中，此类f a p 问题一般描述为整数规划问题或者图染色问题。根据规划目标的不同， 有最低呼损f a p ，最低干扰f a p 等各种模型。这些模型都是n p h a r d 问题，其精确求解 算法不可避免的存在指数爆炸问题。因此除精确搜索外，有大量的文献探讨了各种启发式 搜索算法以及遗传算法等智能计算技术以快速的得到一个近似最优解。 1 3 论文的选题背景和意义 由于广播、电视、移动通信等领域的飞速发展，合理的分配频率能有效的提高频谱利 用率。 ( 1 ) 广播和电视领域。2 0 世纪8 0 年代初，在大容量的有线电视和卫星广播出现之前， 无线电是最快捷方便的传送广播和电视信号的方式。为了使广播和电视信号覆盖一个区 域，需要在这个地区附近用到天线。对于广播，天线一般发射a m 或者f m 信号。a m 调 制信号使用的频率范围在5 4 0 k h z 到1 6 0 0 k h z 之间，而f m 调制信号使用的频率范围在 8 7 m h z 到1 0 8 m h z 之间。天线发射的广播或者电视信号之间不能够有明显的干扰存在，因 此，发射的频率需要精心的选择。 ( 2 ) 基于卫星的蜂窝通信系统。1 9 6 0 年8 月，美国发射了“回声l 号 卫星，这是人 类使用人造天体实现通信所迈出的第一步，从此，无线通信又开辟了空间通信的新领域。 与一般的卫星通信系统不同的是，基于卫星的蜂窝通信系统所使用的卫星高度在7 8 9 k m 的 高度，远低于一般的3 6 0 0 0 k m 。和广播电视一样，卫星蜂窝通信也同样要选取适当的频率 使干扰最小化。 ( 3 ) 陆地蜂窝移动通信系统。在蜂窝移动通信系统中有成百上千个小区，每个小区都 2 南京邮电大学硕：l ：研究生学位论文 第一币绪论 需要若干频道( 发射频道和接收频道) ，这些频道有待分配合适的频率。方面由于无线 电波传播空间的开放特性，每一发射机发出的无线电波都可以传播到相当广阔的空间范 围；另一方面，各个小区的众多发射机和接收机在工作时间、地点和频率上都可能相同或 相近，所以彼此之间可能产生相当复杂的严重干扰。如果对小区发射机指配的频率不适当， 这种干扰必然会很严重，甚至引起网络的局部瘫痪。只有对整个无线网内各个小区的各无 线发射机分配正确的频率，才能使众多的收、发信机彼此兼容，相互干扰减少到可容许的 范围，使千千万万的用户与网络内的各种通信设备连接起来，组成一个有序、有效的蜂窝 移动通信网。 因此，做好频率分配工作对各种通信系统自身以及相互之间避免干扰具有重要的意 义。 1 4 论文的主要内容和目标 论文的主要内容是在论述频率分配技术和遗传算法的基础上，给出一个g s m 移动通 信系统4 2 小区频率分配的例子，用遗传算法来求解该例子的频率分配问题，与此同时通 过这个例子分别对遗传算法的两种选择算子和两种交叉算子的性能做比较。文章最后就如 何设置遗传算法各个运行参数给出了自己的建议。 论文的结构如下： 第一章为绪论，首先介绍了论文的选题背景和意义，然后对论文的主要内容和目标作 了说明。 第二章主要介绍了移动通信系统的频率分配技术，包括无线通信中存在的干扰，频道 分配策略，常用的频率分配模型以及各种求解方法。 第三章介绍了遗传算法的原理，包括遗传算法的简介，基本遗传算法的各个步骤的说 明以及遗传算法的发展动态。 第四章论述使用遗传算法对频率分配问题进行求解的详细过程，对遗传算法的每个步 骤都给出了文字或者图形的编程思想的说明，接着给出程序在不同参数和不同遗传算子的 情况下运行的结果。最后对如何设置遗传算法的运行参数做了总结。 第五章是对整篇文章的总结，列举了文章所作的工作和结论。 第二章移动通信系统的频率分配技术 2 1 无线通信中的干扰 在对小区进行频道分配之前，要进行干扰分析。要有好的通信质量必须要有足够高的 载干比来保证。在移动通信中，主要存在的干扰包括：接收机内部噪声，来自于环境的外 部噪声干扰，同频干扰，邻频干扰，互调干扰8 1 。 2 1 1 外部噪声干扰 外部噪声包括自然噪声和人为噪声。自然噪声主要有大气噪声、太阳噪声和宇宙噪声。 从自然噪声的功率谱分布看，大气噪声和太阳噪声主要分布于1 0 0 m h z 以下，宇宙噪声在 1 0 0 m h z 以上范围内则低于接收机内部噪声。 一般来讲，人为噪声随时间和地点的不同呈现为随机量，通过对人为噪声的大量测量 和统计分析表明，人为噪声的平均值随地点呈对数j 下态分布规律。 2 1 2 同频干扰 同频干扰是指所有落在接收机通带内的与有用信号频率相同的无用信号的干扰。在诸 多干扰因素中，同频干扰主要地决定了系统的通信质量。存在同频干扰的频率范围是 f o ：l z e ( 2 1 ) 其中石为有用信号载波频率，耳为接收机带宽。 同频干扰是由于系统的频率复用引起的。通常，同频小区之间距离越小，同频干扰越 大，但频率利用率提高，因此两者要兼顾考虑。 设当前小区周围有聆个同频干扰小区数，则移动台接收到的载干比为 导：# ( 2 2 ) ，壹厶 一 式中c 为来自于当前服务小区的信号功率，厶为第刀个同频干扰小区所在发射机引起 的干扰功率。移动无线传播测量表明，接收到的平均信号功率随发射机和接收机之间距离 南京邮电火学硕l ：研究生学位论文第二章移动通信系统的频牢分酣技术 的幂指数下降，即离发射天线d 处的平均信号功率p ，可由下式估算为 时 亿3 ， 式中，p o 为距离发射天线d o 处的参考点接收功率，为路径衰减指数。 同频复用距离和频率分配方案对接收台的载干比有直接的影响。在实际组网应用中， 应确定发射基站覆盖区及同频复用距离，对不符合c i 要求的频率予以调整，考虑通信传 播环境、业务量等的变化，对网络实施优化调整。 2 1 3 邻频干扰 邻频干扰是一种来自相邻或相近频道的干扰，是由发射机的带外辐射和接收机选择性 共同作用引起的。 发射机的辐射功率为一个带宽而非单频，因此其邻道的辐射功率可以和有用信号一起 进入接收机，而接收机响应对邻道发射机的主要辐射衰减不够大，从而一起构成邻道干扰。 邻道干扰有两个方面，一是由于工作频带紧随的若干频道的寄生边带功率、宽带噪声、杂 散辐射等产生的干扰；二是指移动通信网内，一组空间离散的邻近工作频道引入的干扰。 存在多个干扰源时，总载干比可由下式计算得出 c 吣乃= - 1 0 l g 喜鬻 亿4 ， 其中另承jp t a o ( l , r ) 分别代表有用信号及第个干扰的功率。 邻道干扰作为移动通信网的一种干扰方式，比同频干扰更容易控制。邻道干扰的抑制 涉及到收信机的寄生辐射、接收机选择性及邻近频道间隔等因素。可以通过这些措施来降 低邻频干扰：频率规划优化调整，增加邻频道之间的间隔，降低发射机落入相邻频道的干 扰功率，提高接收机的邻频道选择性。 2 1 4 互调干扰 在移动通信系统中，除了外界干扰和系统内同频、邻频干扰外，还有互调干扰。移动 通信中，互调干扰也是要考虑的主要问题之一。 互调干扰的机理是由于通信设备中某些电路的非线性使输入频率相互叠加，产生新的 频率，从而造成对本频道或外频道的干扰。当有多个不同频率的信号加到非线性器件上时， 南京邮l 乜人学颀1 ：研究生学位论文第- 二章移动通信系统的频牢分配技术 非线性变换将产生许多组合频率信号，其中一部分可能落到接收机通带内，成为对有用信 号的干扰。 电路的非线性是造成互调干扰的根本原因。同时，在单机互调指标一定时，各个干扰 信号必须满足一定频率关系且具有一定幅度才能造成互调干扰。所以，我们可以从频率分 配上和干扰信号强度上设法破坏构成互调干扰的条件，这就是系统设计时应该考虑的问 题。 多频道移动通信网络中各无线频率和频道序号可由下式表示 z = 石+ q 矽 ( 2 5 ) 其中，z 为无线信道频率，石为起始频率，馘为频道间隔。设巳为频道序号，则刀个 频道序号按照上升顺序排成序列时，任意两个频道间的差值( 即频距) 为 r = j 以= q - q = 厶卅 ( 2 6 ) 对于频道qeq 的信号，因三次非线性失真引起的三阶互调产物在频道巳上的充分 条件为 菱嚣旷唧 ， 由于移动通信系统中，三阶互调成分的幅度比较大，其它的互调成分幅度较小，故一 般只考虑三阶互调。所以在判别某个预选的频道组之间是否存在互调干扰关系，只要根据 公式( 2 7 ) 确定频道序号差值序列中有无相等的差值即可。 2 2 频道分配策略 频道分配策略的基本思想和基本目标就是使整个系统的干扰达到最小，使系统的整体 性能达到最佳。根据不同特点和应用方式，频道分配策略可以分为许多不同的种类【l 引。 根据频道与小区的关系，可以把频率分配策略分为固定频率分配策略( f c a ) 、动态频 率分配策略( d c a ) 和混合频率分配策略( h c a ) 。 对于固定频道分配，小区间的频率配置是固定的。当位于某小区的移动台需要通信时， 该小区的接入点或基站就为它服务，在分给小区的频道中搜索空闲频道。如果能搜索到空 闲频道，就可进行通信，否则，用户就不能通信，即使邻近小区有空闲频道，也不能借来 使用。固定频率分配策略是很简单的，其不随小区业务量和用户分布的变化而变化，缺点 6 南京邮电人学硕士研究生学位论文 第二章移动通信系统的频率分配技术 是频道利用率不高，当通信流量增加时，容易造成阻塞。 为了克服固定频率分配策略的这些弱点，于是人们又提出了动念频率分配策略。在动 态频率分配策略中，所有信道都被放置在信道库内，根据各个小区的需要进行分配。因为 通常在中央库中有多个候选信道可分配给需要的小区，所以必须利用一些准则来选择信 道。动态频率分配的主要思想就是通过代价函数去评估每个候选信道的耗费情况，选择一 个即满足干扰条件又使系统开销最小的信道。代价函数可能包含下列因素：相邻小区的未 来呼叫阻塞率、候选信道的使用频率、信道复用距离、在一定话务量条件下的信道占用分 布、每个移动台所测量的信道质量以及系统的平均阻塞率。动态频率分配以高复杂性的代 价换取频率分配的灵活性和对于小区业务变化的自适应性。然而在较高业务承载条件下， 动态频率分配策略的有效性低于固定频率分配。为了克服这个缺点，人们又提出了结合动 态频率分配和固定频率分配两种策略的混合频率分配技术。 信道分配策略根据其具体应用方式又可以分为集中式和分布式两种。采用集中式时， 信道通过一个中央控制器来进行分配；而采用分布式时，信道通过移动终端采用自动方式， 或者是接入点基于对接受信号的测量来选择信道。虽然集中式能获得较好的频谱利用率， 但是由于必须在分配时间内获知每个频道的当前状态，因此需要在中央控制器和交换机之 间进行大量的信令交换，从而加重处理器的工作负担。而分布式只需要较少的信令通信， 因为每个小区基站都保留着其相邻小区信道利用状态，且每次状态更改只有对涉及到的小 区才进行信令通信。显然，后者是通过降低频谱利用率来实现降低复杂度的效果的。 在进行频道分配时，不管采用哪种分配策略，固定分配还是动态分配，集中式分配还 是分布式分配，都需要注意考虑以下几点： ( 1 ) 同频干扰量应低于规定值的门限值。 ( 2 ) 对于小区系统，如果是多个收发机共用- n 天线，频率问隔应符合共用设备的条 件。 ( 3 ) 由于收发机的非线性特性，多个输入信号就会与其它频率信号相互调制叠加。因 此，进行信道分配时应该注意这种调制叠加的影响。 ( 4 ) 分配的频道数应该与各小区预测语音或数据流量时所需要的频道数相符合，如果 分配的频道数太少，则造成通信质量不能满足要求，如果分配的频道数太多，则造成频道 的浪费。 本文中的频率规划借鉴了f c a 的思想，因此在本文中仅对固定信道分配问题进行阐 述。 在固定频道分配策略中，服务区域被分为许多小区，频道根据一定的复用模式分配给 7 南京邮电大学硕士研究生学位论文 第二章移动通信系统的频牢分配技术 每个小区，这些频道被称为标称频道。只要小区之间的距离满足复用距离d ，同一组频道 就可以在其它小区中使用。复用距离是指为了保证采用相同载波频率的信道接收信号具有 一定载：f p 匕( c i r ) 所需的小区之间的最小距离。 d = 3 r ( 2 8 ) 这里r 是小区半径，m 是d , x e 复用因子。由式( 2 8 ) 我们可以得到小区复用因子为 c = 矧2 ( 2 9 ) 假设系统总的可用频道数为m ，那么每个小区可用的频道数s 为 s ：3 m ( r ) 2 c 2 。， 显然，频道复用距离越短，频道在整个服务系统内复用的次数就越多。 图2 1 分别给出了在蜂窝小区环境下m = 7 和n c = 3 时频道的复用模式。 n = 7n = 3 图2 1 复用模式 对于简单的固定频道分配策略，对每个小区分配数目相同的标称信道。当系统的业务 也是平均分布时，均匀频道分配是有效的。若通信流量均匀，蜂窝系统的每个小区拥有相 同的频道数，承担相同数量的流量，整个系统的总平均阻塞率与每小区的阻塞率相同。 南京邮电大学硕七研究生学位论文 第二荦移动通信系统的频率分配技术 在起用新系统和流量均匀的情况下，简单的固定频道分配策略是一个不错的选择，而 且在高流量的情况下性能也是非常好的。但是移动通信系统中的流量分布多数情况是不均 匀的，随空间和时间在不断起伏，因此需要对每个小区进行非均匀地频道分配，以便使每 个小区所拥有的频道数与承担的通信量相匹配。固定频道分配一个主要的缺点就是当它面 对在时间和空间变化的不均匀流量分布时，均匀的频道分配可能会导致在流量高的小区有 很高的阻塞率，而在流量低的相邻小区却有可能存在空闲的频道。这主要是因为简单的固 定分配策略不能够重新分配频道，导致很低的频道利用率。 针对这个问题，有几种固定频道分配的变种形式可以改进性能。一种就是进行非均匀 频道分配。在非平均频道分配策略中，分配给每个小区的标称频道数取决于该小区的统计 通信量。因此高承载小区比低承载小区分配更多的频道，从而改善频道利用率。 另一种克服非均匀流量分布影响的方法是采用频道借用策略，即从相邻小区借用频 道，严格来说就是：当一个小区没有空闲的标称频道时，如果满足干扰约束条件，那么该 小区可以从相邻小区借用一个频道来容纳更高的通信量。频道借用的基础是它只对相邻小 区产生最小的影响。当一个频道被借用了，则在其它一些小区将禁止使用，称之为“频道 锁定”。由于频道借用导致禁止使用该频道的小区数取决于所采用的频道复用因子，、小 区结构类型以及频道初始分配类型。频道借用是暂时的，一旦通信结束，被借用的频道将 返回到它原来的小区，并将频道锁定释放。 频道借用策略只需要本地或者相邻小区相关信息。它们可以分为两类：简单频道借用 策略和混合频道借用策略。它们的主要区别在于从相邻小区选取空闲频道的方式不同。 在通信流量较低和中等条件下，频道借用策略的性能比简单的固定频道分配要好一 些，但是在通信量很高条件下，后者的性能要优于前者，因为当通信量很低时，借用的频 道数比较少，它们能够处理所承担的流量波动；但是当承担的通信流量高时，借用的频道 数将迅速增大，当激增到一定程度将导致频道利用率急剧下降，阻塞率上升，这主要是由 于信道锁定所致。 2 3 常用的频率分配问题( f a p ) 模型 建立频率分配问题的模型，需要考虑以下三个方面的信息： ( 1 ) 基站间的无线干扰模型 ( 2 ) 基站所需的信道数( 即频率数) ( 3 ) 问题求解的目标 o 南京邮电大学硕二l ：研究生学位论文 第二章移动通信系统的频翠分配技术 下面对这三个方面进行阐述。 1 关于基站间的无线干扰模型 频率规划是建立在基站间的无线干扰模型基础之上的。在文献中，大多数模型仅考虑 一个基站对另一个基站的干扰，而不考虑多个基站对同一个基站的干扰，即将基站间的干 扰简化为一个二元关系。基站间的无线干扰在建模时体现为各种频率分配约束。这些约束 主要有以下几种，按强弱由大到小分别为： 同天线约束：同一个天线分配几个信道，要求信道i 匐隔一定距离 同基站约束：同一个基站分配几个信道，要求信道间隔一定距离 同信道约束：同一个信道分配给几个基站，要求基站间间隔一定距离 邻信道约束：相邻的信道分配给几个基站，要求基站间间隔一定距离 频率约束越强，意味着给基站分配频率时的限值条件越多。 上述几种频率分配约束，应视实际问题的不同而加以取舍。 2 关于基站所需的信道数 为提高系统容量，无线信道中通常采用各种时分复用及频分复用技术。一个基站可以 同时使用若干个信道，在每个信道上使用不同的载频。因此在建立频率分配模型时需要考 虑基站的所需信道数，即所需的频率个数。总结以往的文献，若一个基站需要分配刀个信 道，则在建模上可以使用两种处理方式： ( 1 ) 把该基站看作刀个只有1 个信道的基站，称为“基站分裂”处理方式。这种方式 可以把问题简化成一张有向图，图中每个顶点为一个信道的顶点，缺点是问题的规模将会 随着分裂成的基站的增加而成倍扩大。 ( 2 ) 与( 1 ) 相反，依旧把该基站视作一个基站。这种方式可以避免方式( 1 ) 带来的问题规 模变大的缺陷，但是在建立模型时必须将基站的信道数考虑在内，增加了规划问题描述的 复杂性以及算法的复杂性。 3 关于问题求解的目标 为建立起一个特定的频率分配问题，必须确立问题求解的目标。问题求解的目标不同， 建立的频率规划模型也就不同( 目标函数形式不同) 。综合以往的文献，通常频率规划的 目标有以下一些 ( 1 ) 在满足需要及信道约束的前提下，占用的频率数最少 ( 2 ) 在满足信道约束和现有的频率资源的前提下，提供最大的服务 ( 3 ) 在满足信道约束和现有的频率资源的前提下，用户的呼损最小 ( 4 ) 在满足信道约束和现有的频率资源的前提下，网络中的干扰降至最小 1 0 南京邮电大学硕七研究生学位论文第二二章移动通信系统的频率分配技术 以上三个方面中，不同的处理方式可以形成不同的组合，每种组合就是一种频率规划 问题的描述。选择具体哪种描述取决于实际问题的结构以及要求。 在描述各类f a p 模型之前，首先给出符号定义。 f总的可用频率集 f 特定频率 矿 总的基站集合 v w 特定基站 ，( 力 基站1 ，的可用频率集 g = ( y ，e ) 干扰有向图，矿为基站集合，有向边集合e 表示基站1 白j 的干 扰关系 p 。( g )基站1 ，分配频率厂，基站w 分配频率g ，此时两个频率间的干 扰函数，为简便计，建模时常令p 函数仅与基站v ，w 以及厂，g 之 间的距离l 厂，g i 有关。 h频率分配变量= l 表示基站1 ，分配了频率厂，否则表明基站1 ， 未分配频率。 表2 1f a p 模型符号定义 下面介绍文献中出现的各种频率分配模型。根据实际问题的复杂性不同，有下列几种 f a p 模型【2 l 】。各个模型从简单到复杂依次排列。 2 3 1 可行f a p 问题( f - f a p ) 可行f ap 问题是f a p 模型中比较简单也是比较基本的一种。它的问题描述是：寻找 可行的一种频率分配方案，满足以下的约束： ( 1 ) 对基站1 ，分配历个频率，这些频率都属于f ( 2 ) 任意两个基站间的频率干扰小于域值双 使用先前定义的数学符号，该问题可以被描述成以下模型： 目标函数： 无目标函数 南京邮电人学硕十研究生学位论文第二章移动通信系统的频牢分配技术 约束条件： = 历，对任意的1 ， f e f ( v ) h + 1f ( v ，w ) e 且( ，g ) ( 2 1 1 ) 在文献中，f - f a p 问题一般被描述为一个典型的t - 染色问题。染色问题的一般提法 是研究如何把一个无向图的所有顶点染上不同颜色，其中颜色用数字编号，染色方案要保 证相邻的顶点之间颜色的距离( 颜色编号之差的绝对值) 要满足一定要求。 2 3 2 最大服务f a p 问题( m a x - f a p ) 最大服务f a pi h - j 题( m a x f a p ) 的问题描述是：假设每个基站有个频率分配的上限朋。， 寻找可行的一种频率分配方案，满足以下条件： ( 1 ) 总的分配频率数最大 ( 2 ) 对任一基站1 ，其分配的频率数刀( v ) 小于豫 ( 3 ) 任意两个基站间的频率干扰小于域值 使用先前定义的数学符号，该问题可以被描述成以下模型： m a x 行( v ) v e l , s u b j e c t t o h = 行( 1 ，) 对任意的1 ， ，e 一( p ) n ( v ) m ， 对任意的1 ， x 矿+ lf ( v ，川e 且p 。( 厂，g ) p 赢 m a x f a p 问题是一个典型的整数规划问题。 2 3 3 最小呼损f a p 问题( m b - f a p ) ( 2 1 2 ) 当频率资源一定时，需要将频率在所有基站问合理分配。若频率分配的不当，话务量 大的基站分配的频率过少，则会损失话务量。因此文献中提出最小呼损f a p 问题用于合理 分配基站的频率来减少由于分配不当造成的网络呼损。首先给出呼损的描述。 假设基站1 ，分配了n ( v ) 个频率，其话务量为a ，则其呼损可由e r l a n g b 公式给出： 1 2 南京邮电入学硕- 1 ：研究生学位论文 第一二章移动通信系统的频半分配技术 件： 脚，= ( 剿一焉 给基站的呼损率定义一个权值w v ，表示该基站的话务量占总话务量的l l 仞j ： ( 2 1 3 ) 2 轰 亿 在给出以上定义之后，最小呼损问题( m b f a p ) f l 商 题可以描述成为： 假设每个基站v 有个频率分配的上限，寻找可行的一种频率分配方案，满足以下条 ( 1 ) 各基站的加权呼损率之和最小 ( 2 ) 对任一基站v ，其分配的频率数n ( v ) 小于 ( 3 ) 对任意两个基站，其频率干扰小于域值 使用先前定义的数学符号，该问题可以被描述成以下模型： m a ) 【b ( 丑，疗( 1 ，) ) v g v s t = 力( 1 ，) 对任意的v ，e f ( y ) n ( v ) m v 对任意的， + 喀s i f ( v ，w ) e且p 。( 厂，g ) 戤 m b f a p 问题是一个非线性整数规划问题。 2 3 4 最小干扰f a p 问题( - f a p ) ( 2 1 5 ) 当频率资源一定时，如何在各基站间合理分配频率的准则，除了呼损最小外，还经常 有另一个准则：使网络中存在的无线干扰最小。衡量网络中的无线干扰可以将各个基站间 的干扰相加得到。由此得到最小干扰f a p 问题( m i f h p ) 的提法。假设每个基站v 有个频率 分配的上限，m i f a p 要求得到一个频率分配方案，使得满足： ( 1 ) 基站间总的频率干扰最小 ( 2 ) 任一基站v 分配的频率数小于m ， ( 3 ) 任意两个基站频率间干扰小于域值双 1 3 南京邮电大学硕士研究生学位论文第二章移动通信系统的频率分配技术 使用先前定义的数学符号，该问题可以被描述成以下模型： m a x p ，( 厂，g ) x 矿 v w ) = f ，e l l ，l g e l ) s t = ，f ( ，) 对任意的v f e f ( v ) 刀( y ) 眠 对任意的1 ， b + x 。譬1 ( ，们e 且p 。( ，g ) p m 双 m i f a p 问题是一个非线性整数规划问题。 2 4 频率分配模型求解方法 ( 2 1 6 ) 为求出2 3 节中各种模型的解，必须采用一定的求解算法。决定采用哪种算法时，要 全面考虑具体的模型、问题的规模和拥有的资源。在文献中，一般有确定性算法、启发式 算法和计算智能方法三类【2 l 】。 下面分别对这几类求解算法进行阐述。 2 4 1 确定性方法 确定性算法用于求出频率分配问题的精确解，然而f a p 问题为n p h a r d 问题，因此当 问题规模较大时，确定性方法计算时间往往过大，因而不适用。 绝大部分确定性算法的主要思想是采用树搜索的策略来求解整数规划。在求解过程中 常采用各种策略来“剪枝 ，减少不必要的搜索分支。常用的有整数规划中的分支定界法。 确定性算法的优点是能求出问题的精确解，解的质量是最高的，然而计算时间随问题 规模增大而指数级增长，因此只适用于小规模问题。 2 4 2 启发式算法 启发式算法不要求求解出频率分配问题的精确解，而是试图求出一个高质量的可行 解。启发式算法般利用各种经验准则进行解的搜索，而不像确定性算法一样搜索整个解 空间，因此计算时间要比确定性算法小很多。 在本文中主要介绍两类启发式搜索方法：贪婪算法以及各种局部搜索算法。 1 4 南京邮电大学硕j 研究生学位论文第二章移动通信系统的频率分配技术 2 4 2 1 贪婪算法 贪婪算法的基本思想为按照“贪婪 的准则，根据一个评价标准，不断选取一个认为 最合适的基站分配给一个最合适的频率。算法由一个循环组成，循环的每次迭代根据一定 经验准则选取一个基站，然后再给这个基站按照使目标函数最小的准则分配频率，直至所 有基站都被分配到为止。 算法中最关键的是如何选取下一个被分配的基站。总结文献，该基站选取的准则有以 下几种： 度数最大的节点优先( g r e a t e s td e g r e ef i r s t ) 每次迭代选取度数最大的节点进行频率分 配。节点即基站的度数表示该基站与哪些附近的基站的距离在可能产生频率干扰的范围之 内。度数越大的节点表明该节点所代表的基站所处的区域越密集。 不可行频率数最多的节点优先( d a s t u r ) 选取不可行( b l o c k e d ) 频率数最大的节点。在 迭代过程中，己分配了频率的基站会对邻近的未分配频率的基站造成干扰，致使它们分配 频率时不能分配那些已分配频率基站所使用的频率。这些不能分配的频率称为不可行频率 ( b l o c k e df r e q u e n c y ) 。一个基站的不可行频率越多，表明附近频率干扰越厉害，因此应当优 先加以考虑。 随机选取( r a n d o m ) ：随意指定下一个待考虑的节点。 在以往的文献中，d a s t u r 用的比较多，在大多数情况下解的质量也比其他两种要好。 每次迭代中，一旦选取了基站之后，必须再给基站分配频率。分配的准则为使当前的 目标函数增加幅度最小。 由于贪婪算法不作回溯，算法只需迭代一次，其时间复杂度为o ( n ) ，因而可以很快得 出结果。然而贪婪算法的解的质量往往不高，在应用中常常用于估算问题的下限。 2 4 2 2 局部搜索 局部搜索算法的基本原理是：给定一个原始的分配方案，从这个方案出发不断的做出 调整以搜索一个更好的方案，一直到不能优化为止。 在频率分配问题的文献中，对当前分配方案进行修改的方法一般称为一步修正 ( 1 e x c h a n g em o v e ) ，即以某一种策略选取一个基站，然后按照一定策略改变其已经分配的 频率。 在局部规划中，一般要求施行一步修正后，得到的新的分配方案使得目标函数可以下 南京邮电人学硕i 二研究生学位论文 第二章移动通信系统的频率分配技术 降。但为了不陷入局部极值，也有一些技术来跳出当前的局部极值点。文献中提到的常用 的局部搜索方法有下山法，t a b u 搜索法等等。 由于局部搜索方法存在容易陷入局部极值的问题，达到局部最优之后难以再做进一步 修正使得目标函数下降，因此算法解的质量比较依赖于初始分配方案的选取。 总体来说，局部搜索算法的计算时间较小，解的质量比贪婪算法要好。适用于对解的 质量要求不是很高的场合。 2 4 3 计算智能方法 由于计算机网络的迅速发展，对海量数据的信息处理受到理论和工程界的广泛关注， 其中尤以基于仿生学原理的计算智能在高级信息处理中占据重要的地位。使用计算智能技 术，可以很好的解决使用传统算法难以求解的问题，如n p h a r d 问题。 常用的计算智能技术有人工神经网络、遗传算法、模糊逻辑与蚁群算法等等。文献中 使用计算智能技术求解频率分配问题的比较多，常见的有模拟退火算法以及遗传算法。 2 4 3 1 模拟退火 模拟退火( s a ) 算法通过模拟晶体在高温退火过程中自动达到能量最小的排列，达到对 问题优化的目的。 同局部搜索类似，模拟退火算法也是从一个给定的分配方案出发进行修正。但是模拟 退火算法使用一套独特的机制来跳出局部极值点。算法由一个循环构成，每次迭代算法按 照一定的规则将当前的解加以随机修改，生成一个新的解。若新的解使得目标函数下降， 则无条件接受这个新的、更好的解；否则，算法以一定的概率接受比当前分配分配方案更 差的解，以跳出局部最优点。 这里算法接受使目标函数上升的解的概率是和当前迭代时的“温度”值以及目标函数 上升的值相关的。温度越高，上升的值越小，则概率越大，否则越低。该概率和温度、目 标函数的变化值的关系可以如下式表示 t：tf)一if) p r o b ( f ) = l e 7 ( 2 1 7 ) 在公式( 2 1 7 ) q bf 、f 分别为当前解、修正后得到的新的解。函数c 仍表示解厂对应 的目标函数。丁为当前的温度。温度丁的值是随着迭代次数的增加而不断变小的，变小的 规律一般为： 1 6 南京邮电人学顾i ：研究生学位论文 第二帝移动通信系统的频术分配技术 z 卜a t ( 2 1 8 ) 模拟退火算法在迭代一开始首先设置一个初始温度。然后每一次迭代之后按照公式 ( 2 1 8 ) 降低当前温度，直到温度降到一个门限值为止，然后算法结束，当前的解就成为最 终解。每一次迭代中，算法在同一温度值上不断的尝试去改变当前解，直到尝试失败的次 数超过预先设置的数值为止。 模拟退火算法的计算效果要比局部搜索、贪婪算法等启发式搜索算法要好。其计算时 间尽管要比上两个算法要长一些，但是要比确定性算法要小的多。因此模拟退火算法比较 适合工程应用。 2 4 3 2 遗传算法 遗传( g a ) 算法通过模拟自