（通信与信息系统专业论文）蜂窝式采集网络中微区构造与mac算法研究.pdf

摘要 物探数据采集网络技术正由有线向无线方向演进，同时该网络中传感器铺设的密度 高、范围广成为趋势，因此为了确保所有采集数据迅速、可靠的传输到控制中心，建立 一个覆盖范围广、高效独立、网络延迟小且经济的无线多跳传输网络是必然的。而目前 现有的无线网络技术，诸如w l a n 、w i m a x 、g s m 等，或多或少还不适合上述应用场 合，因此需要独立的设计一个专用的无线多跳传输网络来满足这一发展要求。 针对石油物探数据全无线采集网络项目研究的背景，网络中主要包含传感器与基站 两种节点，且它们的位置固定，项目实现方案所采用的网络架构由两层无线网络构成： 下层无线蜂窝网络承担传感器与蜂窝基站间的接入通信；上层无线m e s h 网络承担蜂窝 基站之间的骨干通信。本文重点研究了目标网络中基站自动布置的方法和频率分配方 案，以及下层蜂窝网的m a c 算法设计，目标是有效实现基站的自动高效区域覆盖配置 和频率指配，以及蜂窝网采集节点的数据业务传输延时最小且无差错。 关键词：微区构造遗传算法频率分配m a c 算法 a b s t r a c t a b s t r a c t t h et e c h n o l o g yo fs e i s m i cd a t aa c q u i s i t i o nc o m m u n i c a t i o nn e t w o r ki s e v o l v i n gf r o m w i r e dt ow i r e l e s s t h ef u t u r et r e n di sl a y i n gt h eh i g l ld e n s i t ya n dl a r g es c o p ea r r a n g i n go ft h e s e n s o r s t oe n s u r et h a ta l la c q u i s i t i o nd a t af r o ms e n s o r si st r a n s m i t t e dt ot h ec o n t r o lc e n t e r r a p i d l ya n dr e l i a b l y , i ti sn e c e s s a r yt oe s t a b l i s haw i r e l e s sm u l t i h o pn e t w o r kw h i c hi sw i d e c o v e r a g e ，h i g he f f i c i e n c ya n ds m a l ld e l a y a l t h o u g hc u r r e n t l ya v a i l a b l et e c h n o l o g i e s ， i n c l u d i n gw l a n w j m a x a sw e l la sg s mn e t w o r kt e c h n o l o g yh a v eb e c o m em a t u r ea n d w i d e l yu s e d ，t h c ya r e n ts u i t a b l ef o rt h ea b o v er e q u i r e m e n t s s oi tn e e d st od e s i g nad e d i c a r e d w i r e l e s sm u l t i h o pn e t w o r kt om e e tt h ea b o v er e q u i r e m e n t s a c c o r d i n gt ot h er e s e a r c ha i mo ft h ew i r e l e s ss e i s m i cd a t aa c q u i s i t i o nn e t w o r k t h e a r c h i t e c t u r eo ft h en e t w o r ki st w o 1 a y e r ：t h el o wl a y e ri sw i r e l e s sc e l l u l a rn e t w o r k ；a n dt h e a b o v ei sw i r e l e s sm e s hb a c k b o n en e t w o r k t 1 l en e t w o r kc o n t a i n st w ok i n 幽o f n o d e s ：b sa n d s e n s o r , a n dt h e i rl o c a t i o i l sa r ef i x e d t l l i st h e s i sm a i n h , g i v e sr e s e a r c ho nt h em e t h o d so f b a s e s t a t i o na u t o m a t i cd i s t r i b u t i o n s c h e m e so ff r e q u e n c yd i s t r i b u t i o na n dm a c a l g o r i t h mi nac e l l t h eg o a li st or e a l i z et h ec o v e r a g eo ft h ea i m e da r e aa n dt og u a r a n t e et h a ta c q u i s i t i o nd a t a p a s st h r o u 曲t h ec e l l u l a rn e t w o r kw i t hs m a l ld e l a ya n de r r o r - f r e e k e yw o r d s ：m i c r o - c e l lc o n s t r u c t i o n i n h e r e n ta l g o r i t h md i s t r i b u t i o no ff i c q u e n c y r e s o l l r c 嚣m a c a l g o r i t h m 东南大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取德的研究 成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发 表或撰写过的研究成果，也不包含为获得东南大学或其它教育机构的学位或证书而使用 过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明 并表示了谢意。 研究生签名： 东南大学学位论文使用授权声明 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位论文的 复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本人电子文档的内 容和纸质论文的内容相一致。除在保密期内的保密论文外，允许论文被查阅和借阅，可 以公布( 包括刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权东南大学研 究生院办理。 研究生签名： 工鹭 导师签名 日期： 绪论 1 1 项目背景 第1 章绪论 目前，伴随着石油物探地震传感器密度高、范围铺设广的发展趋势，相应的地震数 据采集技术也由有线传输向无线传输方向发展，因此为了确保所有采集数据迅速、可靠 的传输到现场控制处理中心，建立一个覆盖范围广，环境适应性强，延迟小且高效经济 的无线数据传输网络是实现这一发展的关键支撑技术与系统。而目前现有的技术，诸如 w l a n ，w i m a x 以及g s m 网络技术虽然已经成熟，并得到广泛使用，但是由于它们 要么需要网络基础设施，要么缺乏环境适应性及灵活经济性。或多或少不适合这一需求 的背景。因此研究并开发一个适应针对性需求的专用多跳无线传输网络不仅是十分必要 的，而且具有广泛的意义。 物探技术在石油勘探开发领域占据着举足轻重的位置，尤其是地震勘探技术。随着 电子通信技术、计算机网络技术的高速发展，物探装备和物探技术也在不断的发展。传 统的石油物探数据采集网络一般采用有线方案，即通过线缆将传感器采集的数据信息传 送到控制中心进行分析但是，基于有线传输的采集网络在布设、移动、效率、维护等 方面有着先天的劣势，随着勘探区域的扩大( 面积超过百平方公里) 和传感器密度的增 加( 间距密度2 0 米以下) ，传统的采用有线传输方案的物探采集网络已经不能满足当今 的要求，无线传输方案正逐步得到应用。国际上某些先进的设备制造企业已经研制出并 逐步推广应用蜂窝式无线数据采集系统，在物探系统中融入先进的无线传输和网络技 术，已经成为当今物探技术发展的方向。 图1 1 v i b t e c hi t s 系统原理构成一混合有无线网络 目前，英国的v i b t e c hi t s 系统是一套比较知名的采用了无线传输方案的物探数据 采集网络，整套采集网络的结构如图1 1 所示。该方案采用了蜂窝式的网络结构，混合 有线、无线传输方式，整套系统由两层网络构成，其中控制中心是网络的核心，基站旧s ， 东南大学硕士学位论文 b a s es t a t i o n ) 设备将其分管小区内采集站所采集的信息进行汇聚，并通过有线网络传送 给控制中心【1 1 。 采集网络中，采集站与基站之间采用了无线传输方式，具体可以采用 i e e e 8 0 2 1 i b 8 0 2 1 1 9 标准；而基站与控制中心间则采取了有线传输方案，例如i e e e 8 0 2 3 以太网方案。这种顶层采用有线传输、底层采用无线接入的网络体系结构比传统的完全 采用有线传输方式的采集系统更加灵活，也更便于布设和移动。 然而，基站与控制中心间的有线传输方式还是在一定程度上限制了物探系统的灵活 性和移动性，在某些情况下基站和控制中心间的布线也存在较大的困难。将项层基站到 控制中心间的有线传输方式改为无线传输，使之成为一个具各两层无线传输能力的采集 网络，这样可以进一步减小布设采集网络的工作量，并提高该采集网络的灵活性和移动 性。可以想象，全无线传输方式将成为物探采集网络新的发展方向。 1 2 项目来源与目标 本课题的研究是依托东南大学移动通信国家重点实验室和中石化的合作项目选定 的，将在一个较大的范围1 0 k m * 1 0 k m 区域内采集到的数据通过无线的方式传输给控制中 心或者说是汇聚点。在1 0 k m * 1 0 k m 区域内铺设全覆盖的传感器网络，传感器的间距大约 2 0 m ，总计约2 5 0 0 0 0 个传感器，传感器每隔l m s 采样一次，每次采集的信息量为2 4 b i t ， 一共采样8 s 即采样8 0 0 0 次，每个传感器大约产生1 9 2 k b i h 业务量，网络中所有传感器 在8 秒钟内产生的总业务量1 9 2 k b i h * 2 5 0 0 0 0 - - 4 8 g ，如何将这些数据业务无线传输给汇 聚点就是项目所要研究的内容。 总体目标： 建设一个能够实现大面积覆盖、适应环境复杂性的无线通信网络，在网络拓扑结构 固定，数据业务模型确知的情况下，利用高效的无线接入，调度与路由算法等先进的无 线通信技术实现在石油物探地震的环境下把传感器采集的数据以最短的延时，可靠地传 输到汇聚点。 方案概述： 采用基于无线蜂窝构造的，两层传输的网络结构，如图1 2 所示。 下层网络即蜂窝网主要负责基站与传感器在无线蜂窝内的通信，传感器通过无线链 路将产生的业务发送到所属蜂窝的基站。蜂窝网并不需要实现目标区域的无缝覆盖，允 许盲区节点的存在。对于基站有效覆盖范围内的传感器节点可以直接一跳接入基站，而 盲区中的传感器节点通过中继节点多跳接入基站。 上层网络为基于m e s h 的骨干网，负责基站之间的无线通信，基站将蜂窝内接收到 的业务通过骨干无线m e s h 网络传送到汇聚点，汇聚点再通过有线网络传送到服务器。 网络的构建采用无线蜂窝技术，这样可以利用有限的频率资源实现大范围的覆盖。 在频率选择上，我们选择2 4 g h z 的公用频段，在频率规划上，选择了4 个频点，每个 频点带宽为2 0 m h z 。 2 - 基站的有效覆盖半径大约5 0 0 r a ，则一个蜂窝的面积为7 ( s o o m ) 2 ，若要在理想环境 下实现基站在1 0 o n * 1 0 o n 范围内的无缝覆盖，则至少需要的基站数为 ( 1 0 o n * l o k m ) n ( 5 0 0 r e ) 2z 1 2 8 个，实际环境下，由于基站有效覆盖区形状的不规则， 实现无缝覆盖需要的基站数是远大于这个值的；若允许盲区的存在且基站之间无重叠区 域，则至少需要的基站数为( 嘉鞠丽l 丽o k m ) = 1 0 0 4 - 。 1 3 课题任务 i * “ 一1 一 无垃链路o 删 # l - ) 图1 2全网的网络结构 s 无境i 麝( o f o m ， 要对目标区域实现大面积覆盖、有效地利用频谱资源并进行高效的无线数据传输， 除了基站与终端设备的硬件支持外，需要制定合理的微区构造方案、频率分配方案、完 善的通信协议及传输控制方案。这就是本课题所要研究的内容。 对于不同环境下的目标区域，给出能够合理地划分小区、确定基站位置的一般方法； 对频率进行合理的分配，以使小区间的同频干扰最小，保证无线通信的质量；设计适合 目标网络特点的蜂窝m a c 算法，在最大地延长网络生命周期的前提下，将传感器节点 采集到的数据在最短的时间内无差错地传输给所属蜂窝的基站。 蜂窝网的结构如图1 3 所示： 东南大学硕士学位论文 。墨 。 图1 3蜂窝网结构 需要解决的问题以及所涉及的研究内容： 如何在不同的环境下划分小区、布置基站。研究无线蜂窝网络规划的方法，重 点研究如何应用遗传算法解决自动基站布置问题。 如何充分利用有限的频率资源为各小区分配频点，并使各个同频小区之间的干 扰最小。研究如何通过数学建模的方法构建信道分配问题。 如何设计蜂窝m a c 算法，使其满足延时和节能的要求。基于物理层机制上的可 借鉴性，半双工、同频下的无线通信，及传感器网络节能方面要求的特点，在 研究8 0 2 1 i 标准和8 0 2 1 5 4 标准的m a c 机制的基础之上，设计蜂窝m a c 算法。 1 4 论文的内容安排 论文总体上分为两个部分。第一部分是围绕无线蜂窝网络规划展开，第二部分主要 是研究蜂窝m a c 算法。 第二章“微区构造及频率分配”介绍了网络规划的目标和内容，从无线覆盖角度给 出了计算基站自动布置的算法和实现，并对其进行了简单验证；在此基础上，从尽可能 降低小区间同频干扰的角度设计了频率规划的算法。 第三章“m a c 机制的研究”先简要介绍m a c 机制，m a c 层要解决的核心问题； 再对i e e e 8 0 2 1 1 和i e e e 8 0 2 1 5 4 m a c 协议进行分析，并在对其优劣和适用范围进行比 较的基础上，针对目标网络蜂窝接入的特点提出相应的m a c 机制。 第四章“m a c 算法设计及分析”设计适合目标网络蜂窝接入的m a c 算法，对蜂 窝内采集点采取分层接入的思想，位于盲区的采集点选择中继节点多跳接入，结合功率 控制功能，综合考虑能量效率和接入延迟，给出m a c 算法并分析。 第五章“总结及展望”总结了全文工作，提出需要继续研究和改进的地方。 第2 章微区构造及频率分配 第2 章微区构造及频率分配 早期的移动通信系统依靠单个的大功率发射机获得一个大面积的覆盖范围。虽然这 种方式能够获得很好的覆盖，但是在此覆盖区域内，为了避免干扰，不能重复使用相同 的频率。这样，当业务增长对，有限频率的分配便不能满足需要。蜂窝技术就是在用户 容量不断增大的情况下，解决频率不足问题的一个重大突破，其思想是用许多小功率的 发射机来代替单个的大功率发射机，每一个小覆盖区只提供服务范围内的一小部分覆 盖。每个基站分配了整个系统可用信道中的一部分，相邻基站则分配另外一些不同的信 道。通过给相邻基站分配不同的信道组，基站之间及其范围内的移动用户之间的干扰最 小。随着服务需求的增加，基站的数目也需要增加，从而提供额外的容量。这一基本原 理是所有现代无线通信的基础，因为它通过在整个覆盖区域内复用信道，实现了用固定 数目的信道来为任意多的用户服务【2 1 1 3 1 。下面将首先简要介绍无线蜂窝网络规划的目标， 对基站的布置和频率的分配问题进行描述，接着引入遗传算法，实现了基站自动覆盖， 最后在给定四个频点石、正、五、正的条件下，给出频率分配方案。 2 1 网络规划的目标及内容 无线蜂窝网络规划中的一个重要目标就是在保证较好的服务质量的前提下，争取获 得比较高的频谱利用率，并且尽可能减少基站的数量，以降低成本。换句话说，要尽可 能地在单位面积的覆盖区域内容纳更多的用户，而同时使每个用户得到的服务质量维持 在一种可以接受的服务等级上。在我们所设计的蜂窝式采集网络中，这一根本目标所涉 及的主要是两方面： 场强覆盖一保证无线信号对目标区域的一定强度覆盖，即要求接收机接收到的无 线信号强度必须大于按照接收灵敏度所设定的某一阀值。 信号传播质量网络中无线信道的同频干扰必须被控制在可以保证可靠的信号传 播的范围内。 除了上述的目标，网络建设成本、系统在未来业务需求的增长也是规划中不能不考 虑的一个重要方面4 】【5 】【6 1 。一个完善的系统规划不仅可以很好地满足网络建设初期的需 求。而且可以为网络建设后期的优化提供方便的条件。 2 1 1 基站布置 蜂窝网络规划的第一步是划分小区、确定基站位置，如果能够合理规划基站位置， 这将有利于网络的后期优化。 布置基站的目标主要有两个：( 1 ) 优化基站的位置( 2 ) 优化基站的数量。 我们可以借鉴一些算法来实现。传统的方法，如随机搜索算法( r a n d o ms e a r c h 5 东南大学硕士学位论文 a l g o r i t h m s ，t o ma n d z i l i n s k a s1 9 8 9 ) 、统计局域搜索算法( s t o c h a s t i cl o c a ls e a r c ha l g o r i t h m s ， h o r s ta n dp a r d a l o s l 9 9 5 ) 、模拟退火算法( s i m u l a t e da n n e a l i n g , t o ma n dz i l i n s k a s1 9 8 9 ) 、 禁忌搜索算法( t a b o os e a r c h ，g t o v c r , t a i t l a r d ，a n d d e w c r r a1 9 9 3 ) 等，是已经通过实践验证 有效的经典算法。但是，这些经典的方法有一个共同的缺点，它们是单目标算法，需要 运行多次来逼近最优集，当进行多次独立的运行时，这些方法将耗费大量的资源。近来， 进化算法己经成为替代经典算法的一个很好的选择：首先，可以搜索很大的目标空间； 其次，可以满足多个目标并且一次运行得到折衷解。如何应用遗传算法解决基站自动布 置问题在下面两节中将有详细讲述。 2 1 2 频率规划 如何在有限的频带资源下，满足用户容量的需求，这就要求对频率要进行合理的规 划，尽可能的在不同小区间对频率进行复用，同时要避免干扰，这就是所谓的信道分配 问题( c a p ，c h a n n e la s s i g n m e n tp r o b l e m ) 。信道分配问题实际就是用尽可少的信道数， 满足小区的业务需求和电磁兼容( e m c ，e l e c t r o m a g n e t i cc o m p a t i b i l i t y ) 限制，对各小区 进行的信道分配1 7 1 。 对蜂窝小区而言，电磁兼容( e m c ) 限制主要体现在以下三个方面： 1 ) 同频限制( c c c ，c o c h a n n e lc o n s t r a i n t ) ，同一频率必须在大于它的复用距离后 才能被再次使用； 2 ) 邻频限制( a c c ，a d j a c e n tc h a n n e lc o n s t r a i n t ) ，频域上相邻的两个频率不能同 时分配绘相邻小区； 3 ) 同场地限制( c s c ，c o s i t ec o n s t r a i n t ) ，分配给同一小区的任一对频率在频域上 必须有一定的间隔。 为了在数学上构建信道分配问题，引用了需求向量r 和兼容矩阵c 的概念 8 】，下面 我们用以表示蜂窝网中小区的数量或者基站的数量，m 表示可用信道的数日。 需求向量r 有咒个元素， r = n 乞r j 7 ( 2 1 ) 其中的每一个元素为小区f 所需的信道数。 兼容矩阵c = c j ，) ，它是一个b x b 的对称矩阵，任意项白确定了小区f 和小区，之间 能够同时使用的信道的最小间隔，当白= 0 时表示小区i 和小区，可以使用相同的信道。 兼容矩阵是一种针对信道和小区关系的模型，这个矩阵全面反映了蜂窝网络中小区间的 互扰关系，是频点分配方案的一个必要约束条件。兼容矩阵的初始化需要通过计算小区 间的干扰概率，再分段量化出各个小区间的频点间隔。在完成了兼容矩阵后，就可以根 据此兼容矩阵进行频率规划。 频率规划问题主要考虑两方面的因素： 舌 第2 章徽区构造及频率分配 一是必须保证满足兼容矩阵的要求； 二是要在有限的频率资源内实现。 采用所力的二进制矩阵s 来表示信道分配方案，该矩阵也称为信道服务矩阵，矩阵 的行代表信道的数目，矩阵的列代表小区的数目。每个元素用表示，它的值为0 或1 ， 即当信道巧 配给小区_ ，时，- - 1 ，否则，勘= o 。 当信道总数和各个小区的信道需求确定后，在兼容矩阵的前提下，c a p 被描述为一 个n p - h a r d 的组合优化问题。用遗传算法解决信道分配问题也是一种很有效的途径。 信道分配问题可以描述如下： 给定： ( 1 ) 兼容矩阵c ( 2 ) 需求向量只 ( 3 ) 可用的信道数历 求解： 信道服务矩阵s ，s 应该满足： ( 1 ) 兼容限制( 由兼容矩阵c 描述) ( 2 ) 业务需求( 由需求向量r 给出) 2 2 遗传算法简介 在介绍遗传算法之前，先简单介绍一下数学上著名的n p 问题，n p 就是 n o n - d e t e r m i n i s t i cp o l y n o m i a l ，非确定复杂程度的多项式性，对一个问题寻求一种多项式 的算法是一个很好的解答，但是对于很多问题来说，找不到一个多项式的解决方法，只 能尝试很多种方案，才能得出一个答案，这显然是很费时的，这种问题为n p 问题。 n p c o 卿c o m p l e t e ) 问题，可以这么认为，这种问题只有把解域里面的所有可能都穷举了 之后才能得出答案，这样的问题是n p 里面最难的问题，这种问题就是n p c 问题。n p c 问题被定义为满足下面两个条件的问题，首先得是一个n p 问题，然后所有的n p 问题 都可以约化到它。n p c 问题目前没有多项式的有效算法，只能用指数级甚至阶乘级复杂 度的搜索。n p h a r d 问题是这样一种问题，它满足n p c 问题定义的第二条但不一定要 满足第一条( 就是说，n p h a r d 问题要比n p c 问题的范围广) 。n _ p 。h a r d 问题同样难以 找到多项式的算法，因为n p h a r d 问题不一定是n p 问题，即使n p c 问题发现了多项 式级的算法，n p h a r d 问题有可能仍然无法得到多项式的算法。事实上，由于n p h a r d 放宽了限定条件，它将有可能比所有的n p c 问题的时间复杂度更高从而更难以解决。 遗传算法是基于进化论的原理发展起来的一种广为应用的，高效的随机搜索与优化 的方法1 9 】。其优点在于对于复杂的搜索空间，能快速的找到最优解。和传统的搜索算法 不同，遗传算法从一组随机产生的初始解( 称为种群p o p u l a t i o n ) 开始搜索。种群中的 每个个体( i n d i v i d u a l ) 是问题的一个解，由染色体( c h r o m o s o m e ) 构成。染色体是一串 东南大学硕士学位论文 符号，比如一个二进制字符串。这些染色体在后续迭代中不断改交，产生新的解。在每 一代形成中，根据适值的大小选择适值高的后代，淘汰适值较低的后代，从而产生进化。 这样经过若干代之后，整个种群的适值逐步提高，从而得到理想的最优解。遗传算法用 于最优化求解的一般过程如图2 1 所示。 由于遗传算法的整体搜索策略和优化搜索方法在计算上是不依赖于梯度信息或其 它辅助知识，而只需要影响搜索方向的目标函数和相应的适应度函数，所以遗传算法提 供了一种求解复杂系统问题的通用框架，它不依赖于问题的具体领域，对问题的种类有 解空间o 专基因编码空间c 产生一组随机编码解，p ( ) c ，k 【1 ，】 这组随机编码解构成原始种群，每个 解为一个个体，种群个体数n 对种群中的每一个个体所代表的解计算相 应的适值。评估解的优劣 通过交叉和变异操作产生新的后代个体群 d ( f ) c ，t 【l ，m 】，m n 在p c k ) 和o ( t ) 中按适值大小优胜劣汰，选择 n 个个体重新构成子代种群 图2 1 遗传算法求解过程 很强的鲁棒性，所以广泛应用于许多科学，主要应用领域有： 1 、函数优化 函数优化是遗传算法的经典应用领域，也是遗传算法进行性能评价的常用算例，许 多人构造出了各种各样复杂形式的测试函数：连续函数和离散函数、凸函数和凹函数、 低维函数和高维函数、单峰函数和多峰函数等。对于一些非线性、多模型、多目标的函 数优化问题，用其它优化方法较难求解，而遗传算法可以方便地得到较好的结果。 2 、组合优化 随着问题规模的增大，组合优化问题的搜索空间也急剧增大，有时在目前的计算上 用枚举法很难求出最优解。对这类复杂的问题，人们已经意识到应把主要精力放在寻求 满意解上，而遗传算法是寻求这种满意解的最佳工具之一。实践证明，遗传算法对于组 合优化中的n p 问题非常有效。例如遗传算法已经在求解旅行商问题、背包问题、装箱 问题、图形划分问题等方面得到成功的应用。 2 2 1 编码 如何将问题的解转化为用编码表达的个体是遗传算法的关键问题。通常采用的编码 方法是二进制方法，但对于许多遗传算法的应用来说，这种简单的编码方法很难直接描 述出问题的性质。近年来，针对特殊问题，提出了各种非二进制编码方案。遗传算法的 一个显著特点就是它交替地在编码空间和解空间中工作，如图2 2 所示，它在编码空间 对染色体进行遗传运算，而在解空间对解进行评估和选择。 8 第2 章微区构造及频率分配 对于非二进制编码，个体和解之间的编码和解码有三个问题： ( 1 ) 色体的可行性 ( 2 ) 色体的合法性 ( 3 ) 映射的唯一性 可行性为染色体解码成为解后是否在给定问题的可行域内的性质。合法性是指染色 体是否代表了给定问题的一个解，如图2 3 所示。 图2 2编码空间和解空间的映射 图2 3可行解、不可行解和非法解 染色体的非可行性概念源于约束优化问题，无论是传统方法还是遗传算法都必须满 足约束。对于许多优化问题来说，可行域是用不等式或不等式组来表达的。这种情况下， 可以采用惩罚法来消除不可行的染色体。 非法性的概念源于编码技术。许多组合优化问题采用了问题专用的编码方法，这些 编码方法采用的交叉方案通常可能获得非法的后代。由于非法的染色体不能解码为解， 这样的染色体就不能进行评估操作，因此惩罚法就无法适用。通常采用强制修复的办法， 将非法染色体转化为合法染色体。著名的p m x 算子就是为解决单断点交叉的非法性问 题提出的一种将替代编码和修复技术结合起来的双断点交叉方法。有专家指出，对于许 多组合优化问题，修复非可行或非法染色体相对容易实现，这种修复策略远胜于拒绝策 略和惩罚策略。 通常染色体到解的映射不外乎如下三种情况： ( 1 ) 1 1 映射 ( 2 ) n 一1 映射 ( 3 ) l - n 映射 在遗传算法的应用中，为了获得比较高的算法效率，一个合理而准确的基因编码方 东南大学硕士学位论文 法是相当重要的。对于各种实际工程问题，有不同的基因表达。在本文中，我们就采用 了一种完全实数化的基因表达方式。 2 2 2 评估操作和适值函数 遗传算法在进化搜索中基本不利用外部信息，仅以适值函数( f i t n e s sf u n c t i o n ) 为依 据，利用种群中每个个体的适值来进行搜索的过程。因此，适值函数的选取至关重要， 直接影响到遗传算法的速度以及能否找到最优解。在遗传算法运行的初期，通常会产生 一些超常的个体，由于这些个体的竞争力突出，从而控制了后期的选择过程；而在遗传 算法的后期，由于种群中个体差异值很小，而继续优化的可能性变小。这两种现象叫做 遗传算法的欺骗性问题，适值函数设计不当就极有可能造成这两个问题。 适值函数的设计往往要满足以下条件： ( 1 ) 单值，连续，非负和最大化 ( 2 ) 合理，一致性 ( 3 ) 计算量小 ( 4 ) 通用性强 在解决实际问题中，通常将目标函数作为适值函数来使用，这样可以使适值函数更 接近于实际问题的解决。为了加强算法的效率，常常也对目标函数进行某种变换作为适 值函数。适值变化有静态变换和动态变换。这种划分是按变换后的适值和原适值之间的 关系是恒定的还是可变的来划分的。 常用的适值函数变换方法有几种： ( 1 ) 线形变换法 设原适值函数为，变换后的适值函数为g ，则线性变换可用下式表示 g = a f + 口 上式中的系数确定方法有很多种，但要满足以下条件： 原适值的平均值要等于定标后的适值平均值， 一代的期望复制数为1 ，即 ( 2 2 ) 以保证适值为平均值的个体在下 = 岛 ( 2 3 ) 变换后的适值应大于原适值平均值的倍数，以控制适值最大的个体在下一代中 的复制数。 ( 2 ) s 截断 线性变换的一种改进方法，主要用来解决负适值的问题。交换公式为 g = ，一( ，一c x 回 ( 2 4 ) 其中，c 是一个小整数；万是种群的标准差；，是原适值的平均：如果变换g 为负， 第2 章微区构造及频率分配 则设为0 。 ( 3 ) 幂率变换法 幂率变换的定义为 g k = 0 x 五+ 6 ( 2 5 ) 变换后的最好适值和最坏适值随a 值的增加而增加。 ( 4 ) 指数变换法 指数变换法的公式为 g = e 一掣( 2 6 ) 这种变换方法的基本思想来源于模拟退火过程( s a ) ，其中的系数a 决定了复制的强 制性，其值越小，复制的强制就越趋向于那些具有最大适值的个体。针对种群中的每个 个体，计算出相应的适值大小。每个个体的适值大小反映了各个个体的在特定适值函数 ( 通常是目标函数) 恒量下的优劣。这个过程就是对在解空间中解的评估过程。 2 2 3 选择操作 遗传算法的基本原理就是达尔文的自然选择原理，选择是遗传算法的推动力。选择 压力是一个内含的准则，压力过大搜索会过早终止，压力过小搜索又会不必要地缓慢。 一般说来，算法的初始阶段应该选择较低的压力，这有利于扩展搜索空间；而在终止阶 段建议采用较高的选择压力，这有利于找到最好的解域。这样选择就能将搜索引向最优 解。 选择主要包括下面三个方面，它们对选择压力以至于遗传算法的性能都有很大影 响： ( 1 ) 采样空间 选择过程可以基于全部或部分双亲和后代来产生下一代的新种群。这就带来了采样 空间的问题，采样空间由两个因素来确定：大小和成分( 双亲或后代) 。令p o p n u m 为种 群大小，o f f n u m 为每代产生的后代数。规则的采样空间的大小为p o p n u m ，含有所有后 代和部分双亲。扩大的采样空间的大小为p o p n u m t - o f f n l l r , i i ，包括所有双亲和后代。 在规则的采样空间中，如果后代一旦产生就替代掉双亲，这称为整体替代。由于遗 传运算本质上是盲目进行的，后代可能不如其双亲。这种后代完全替代双亲的策略会在 进化过程中失去一些较好的染色体。通过采用概率机制，可以用转轮法来随机选择双亲 进行替代。我们就是采用了这一机制。在扩大的采样空间中，双亲和后代有同样的生存 竞争机会。通过父代和子代个体的集体参与竞争，最后选出最好的p o p n u m 个个体重新 构成新的一代。采用基于扩大的采样空间的显著特点是可以用增加交叉率和变异率的方 法来改进遗传算法的性能。如果选择是在扩大的采样空间中进行，就不用担心高的交叉 率和变异率会造成太多的随机变动。 ( 2 ) 采样机理 东南大学硕士学位论文 采样机理是如何从采样空问中选择染色体的理论，选择染色体的方法有三种：随机 采样、确定采样和混合采样。 随机采样的特点是在选择阶段根据生存概率来确定每个染色体的实际繁殖数。 选择阶段由两个部分构成：一是确定各个染色体的期望值；二是将期望值转化为后代数。 染色体的期望值是表明该染色体应产生的后代的平均数的实数，采样过程则将这个 实数转换为后代数。这个方法的典型代表就是转轮选择法。其基本思想就是每个染色体 的选择概率正比于它的适值。对于适值为丘的染色体k ，其选择概率p 。如下 p 型! ! ” p k = 五，乃 ( 2 7 ) z l 然后根据这些概率构造一个转轮。旋转转轮p o p n u m 次，每次选一个染色体加入新 的种群中。 确定采样的思想比较简单，它是从采样空间中选择p o p n u m 个最好的染色体构 成下一代新的种群。通过计算采样空间中每个个体的适值，排序比较来实现这一目的， 整代替代( 即用后代代替所有双亲) 也可以视为一种确定选择。 混合采样同时具有随机采样和确定采样的特征，典型的例子是竞赛选择。通过 随机的在采样空间中选出一组染色体，从中选出最好的个进行繁殖，每组的染色体数 称为竞赛人数。 竞赛选择也有两种不同的分类。随机竞赛选择按一般方法计算选择概率，用转轮法 选出成对的个体，然后将每对中适值高的个体加入新种群，直到种群充满为止。 保留随机采样是确定采样的改进版本。它为每个个体分配其期望值的整数部分的样 本，然后所有个体按其期望值的分数部分来竞争种群中的空缺。 ( 3 ) 选择概率 通常的应用中，按正比选择法来进行个体选择。选择概率正比于染色体的适值。这 种简单的办法有一些不好的性质，即它会导致某些超级个体过早霸占选择过程，而在较 晚的代中种群集中在一起，个体的竞争减弱，变得象随机搜索。因此，常常采用前面所 提到的适值函数进行适值交换，再利用变换后的适值确定选择概率。 2 2 4 交叉和变异操作 交叉是最主要的遗传算法，它同时对两个染色体操作，组合二者的特性产生新的后 代。交叉的简单方法是在双亲( 两个父代个体) 的染色体上随机的选取一个断点，将断 点的右段互相交换，从而形成两个新的后代，这种方法对于二进制表示最为合适。遗传 算法的性能很大程度上取决于采用的交叉算法的性能，好的交叉操作能比较迅速的产生 优秀的个体。 交叉率( p ) 定义为各代中交叉产生的后代数与种群中的个体数( 通常记为c p o p n u m ) 的比，它将参加交叉运算的染色体个数的期望值控制为p c * p o p n u m ，较高的 第2 章徽区构造及频率分配 交叉率可达到更大的解空间，从而降低停在非最优解上的机会。但是，当这个比率太高 的时候，会因为搜索不必要的解空间而耗费大量的计算时间。 变异则是另一种基本的遗传运算，它在染色体上自发地产生随机的变化。一种简单 的变异方法是替换一个或多个基因。在遗传算法中，变异可以提供初始种群中不含有的 基因，或找回选择过程中丢失的基因，为种群提供新的内容。 变异率，记为以，定义为种群中变异基因数在总基因数中的百分比。变异率控制 了新基因导入种群的比例。若变异概率太低，一些有用的基因就不能进入选择；若太高， 即随机的变化太多，那么后代就可能失去从双亲继承下来的好特性，这样算法就会失去 从过去的搜索中学习的能力。 2 3 遗传算法在基站自动覆盖中的应用 2 3 1 遗传算法的应用 采用了j i nk h 提出的实数表示方法，每一个个体代表了一种基站布置方案。种群 ( p o p u l a t i o n ) 中个体( i n d i v i d u a l ) 的基因组( g e n o m e ) 为：g = ( q ，岛，q ) ，式中染色体 ( c h r o m o s o m e ) q = ( 工，力，i = 1 ，2 ，oo 7 k ，o ，力即基站位置在数字地图中的坐标。若 e = ( n u l l ，n u l l ) 表示此染色体为空，不代表基站位置。从而基因组不仅可以表示基站的 位置，而且可以表示基站的数目。 我们考虑的目标是：面积覆盖率石、成本五、。一方面要我们需要扩大覆盖面积， 一方面要降低成本，另外还要考虑一些其他要求和因素，这些显然存在矛盾，这就需要 遗传算法进行多目标优化【。 五= s 。“s a 。 ( 2 8 ) 厶= n ( 2 9 ) 式中， s 0 。被覆盖到的区域面积； 只。目标区域的总面积； 基站的数目； 在数字地图上是按照经纬度划分成一个个小方格，所谓的面积就是符合相应条件的 小方格数目。 出于算法验证的方便，先只考虑上述两个目标。另外，我们采用了限制条件的适值 分配算法，这样可以免去无谓的搜索。选择面积覆盖率的下限c o v e r l i m i t 、基站个数下 限m i n b s n u m 和基站个数上限m a x b s n u m 作为限制条件，用e 表示对目标的加权平均。 e = w l e l + w 2 岛 ( 2 1 0 ) 13 东南大学硕士学位论文 q = 。等z f ，l ：口毗i m 矗 (211)c，= o v e r l i m f f 、7 岛：j ? ”删拥- a ) 脚鼬m 五 0 ，那么它将被 胜出，将其置入相应的集合中。如果两个个体都不满足限制条件，则比较哪个个体超出 限制条件更少，e 值小的被认为是较优的个体。 我们令初始化概率等于由基站个数上下限所确定的基站个数均值占染色体个数的 百分比。 尼删= ( m a x b s n u m + m i n b s n u m ) 2 k( 2 。1 3 ) 当产生的随机数小于此概率时，随机产生一个基站坐标，而当随机数大于此概率时， 我们将此染色体置空。基因组长度，即染色体数目k 为 k = e m a x b s n u m f 2 1 4 ) 其中，c 为大于1 的放大因子，从而使染色体个数能够超过需要的基站的个数，使 得染色体可以正确的反映所需基站的个数。验证时设定为1 2 。 为了增大选择压力，在计算适值之后同时更新个体的索引，使较优的个体拥有较小 的索引值，同时产生随机数盯【o ，1 】，o x o x k 即为选中的个体索引值，另外，还将种 群中相同的个体删除，以避免了高适值个体迅速占领整个种群而引起早熟。虽然增加少 量的计算量，却有效提高了高适值的个体的繁殖能力。接下来，采用二元随机竞争法确 定参加繁衍的个体。从种群中一次随机选择两个个体，比较这些个体，适值较高的个体 将在此次竞争中获胜，被选择加入到下一代种群中。 在确定参加繁殖的个体中依次选相邻索引的个体进行交叉，而后最后一个个体和第 一个个体交叉，共产生k 个后代，对每个后代进行变异。交叉是根据选定的两个双亲对 应位置的染色体状态进行的。假设 f a t h e r = ( ，z ，) ，m o t h e r = ( ，m i ，) ( 2 1 5 ) 式中， f 代表父亲的第i 个染色体： m ：代表母亲的第i 个染色体； ( z ，m 1 ) ( g ，g ) ，( g ，n u l l ) ，( n u l l ，g ) ，( n u l l ，n u l l ) ，i = l ，2 ，k ( 2 1 6 ) g 表示该染色体所代表的基站位置不为空； n u l l 表示空的。 第2 章徽区构造及频率分配 后代为 曲删= ( ，c h i l d i ，) ，c h i l d i g ，n u l l ，i = 1 ，k ( 2 1 7 ) 交叉之后就是进行变异操作，变异后的个体为 m u t = ( ，r o u t , ，) ，r o u t i = g ，n u l l ，i = 1 ，k ( 2 1 8 ) 染色体交叉状态转移矩阵如下，表示交叉后4 种可能状态向状态g 、n u l l 转移的转 移概率， i ( 啊+ ，) 7 2 + 触i m , 一加z + 弛7 ) m l + 掌( o ，r ) ui( 2 1 9 ) i 肌l l n u l ln u l l n u l li 、 染色体变异状态转移矩阵如下，表示变异后状态g 、n u l l 之间的转移概率， 防“0 ，) mi ( 2 2 0 ) un u l ll 、 其中，i m l 一，l 表示双亲相应染色体向量对应坐标的距离；善( 工，_ y ) 表示以工为均值、 y 为方差的高斯变量；，表示按传播模型计算的基站覆盖半径；( ，表示定义在基站所分 布的二维空间上的均匀分布变量。 假定区域平坦，采用自由空间传播模型，使用全向天线。图2 4 、2 5 是以繁殖代数 作为终止条件，分别选用6 个基站和9 个基站对遗传算法进行简单验证的结果。 图2 46 个基站的分布 左：第2 代；右：第5 0 代 图2 59 个基站的分布 左：第5 0 代；中：第1 0 0 代：右：第3 0 0 代 1 5 东南大学硕士学位论文 我们的目标网络覆盖区域是1 0 k m x l o k m ，为减少计算的复杂度，我们选取其中一部 分区域5 o n x 3 k m 用1 5 个基站进行覆盖。图2 6 是理