组网算法（共9篇）
组网算法 篇1
一、引言
无线自组网(Wireless Self-organizing Network)是计算机网络和移动无线通信网络相互融合发展的产物，其显著特点是节点采用无线通信方式、网络无中心、自组织和多跳中继，无线自组网(MANET)、无线传感网(WSN)和无线网状网(WMN)都可归属于无线自组网这一范畴。为了提高无线自组网的可扩展性和QoS保障能力，往往采用分级网络结构。分簇算法按系统要求将众多网络节点组织成可管理的簇，是构造分级网络结构的关键技术，它的好坏直接影响着无线自组网的各种性能指标。
基于簇的分级网络结构如图1所示，网络划分成若干个簇，每个簇由一个簇头和多个普通节点组成，并且簇头和网关/分布式网关形成高一级的虚拟骨干网(VBN)。在蜂窝网络中，资源的分配比较容易实现，因为各个移动终端可以直接或借助基站获得对方的带宽要求。通过把网络划分成簇可以将这种方法扩展到无线自组网，在簇内，簇头可以控制节点的业务接入请求并合理地分配带宽。基于分簇结构，还可以采用混合式路由算法，簇内采用先验式路由，而簇间使用反应式路由来减少路由开销。此外，借助于虚拟骨干网可以提高业务的QoS保障。因此，通过分簇算法将网络划分成簇，可以在很大程度上提高无线自组网的性能和实用性，具有重要的意义。
二、分簇算法的原则和目标
分簇算法根据系统要求按照某种规则将网络划分成可以相互连通并覆盖所有节点的多个簇，并且在网络结构发生变化时进行簇结构的更新以维护网络的正常功能。簇的大小应根据节点的传输功率和簇本身的特性来决定。如果簇过大，簇头的负担较重，并且普通节点到簇头的距离过远而会消耗过多能量。如果簇较小，可以相应增加信道的空间重用率，提高系统容量，并可以减少节点的传输功耗。但是簇的尺寸过小会导致网络中簇的数目较多，源目的节点对之间的路由所经过的跳数较多，从而会增加分组的投递时延和中转业务量。此外，在选择簇的大小时还应考虑簇头的处理能力、功率损耗和地理环境等约束条件。
分簇算法要在拓扑探测的同时完成分簇形成和分簇连接的工作。拓扑探测指各节点通过收发探询分组来获得邻节点以及整个网络的拓扑连通情况。分簇形成是指按照某种规则选举簇头并划分簇的过程，各种分簇算法的不同之处主要体现于此。分簇连接是指相邻的簇选择关联节点的过程。为了减少关联节点数过多引入的控制开销，网关节点和分布式网关节点的选取可以按照节点度最小的原则进行。
分簇算法的目标就是以较少的计算和通信开销来构造和维护一个能够覆盖整个网络的、可以较好支持资源管理和路由协议的相互连接的簇集合。为了减少分簇算法带来的开销，分簇算法应简单高效，并在只有很少的节点移动和拓扑变化较慢时尽量维持原有结构，从而减少重新生成簇引入的开销和提高网络的总体效能。理想情况下，希望以最少的簇头覆盖整个网络，即簇头的集合为最小统治集(MDS)。满足MDS的簇头优化选择问题是NP完全问题，因此一般采用启发式分簇算法。好的分簇机制应尽量保持网络拓扑稳定，减少重新分簇的次数，优化簇内和簇间连接，并且还应考虑节点的能量级别、网络的负载平衡以及对路由算法和信道接入协议的支持等方面。
三、无线自组网中分簇算法的分类比较
迄今为止，针对无线自组网已经提出了大量的分簇算法来构建和维护分簇网络结构。分簇算法的选择依赖于应用的需求、网络的环境和节点的特征。不同的分簇算法具有不同的优化目标，包括最小化簇计算和维护开销、最小化簇头、最大化簇稳定性和最大化节点生存时间等。考虑到现存的分簇算法很多，下面按照簇头选举方式以及优化目标对它们进行分类和比较。
1. 基于节点ID的分簇算法
C.R.Lin提出的最小节点ID (LowID)分簇算法是基于ID的分簇算法的典型代表。LowID算法规定，相邻节点中具有最小ID的节点作为簇头，其一跳邻居节点成为该簇头所在簇的成员节点，并不再参与簇头选举过程，重复以上过程直到所有节点都加入某个簇。该分簇算法计算简单，实现方便。在移动环境下，最小ID算法中簇头更新的频率较慢，维护簇所需花费的开销较小。缺点在于这种算法倾向选择ID较小的节点作为簇头，使得这些节点消耗更多的能量，从而会减少整个网络出现分区的时间，此外它没有考虑网络负载平衡等因素。
2. 最高节点度分簇算法
最高节点度分簇算法也称作最高连接度算法，目标是提高网络的控制能力和减少簇的数目。该算法规定：相邻节点中具有最大节点度的节点被选为簇头，节点度是指该节点的一跳邻居节点的数目，当节点度相同时，则选择ID最小的节点作为簇头。簇头的一跳邻居节点则成为该簇的成员节点，并不再参与簇生成过程。这种算法的优点在于网络中簇的数目较少，即源目的节点对之间的平均跳数较少，从而减少了分组投递时延。但是，较少的簇数量也减少了信道的空间重用率。此外，当节点移动性较强时，簇头更新频率会急剧上升，簇结构变化较快，引入了大量维护开销。最高节点度算法适用于移动性较弱并且节点密度较低的场合。
3. 最低节点移动性分簇算法
为适应节点的移动性，提高簇结构的稳定性，可以根据节点的移动性为节点分配权重，并依据节点的权重来选举簇头。最低节点移动性分簇算法规定：节点的移动性越高，其分配的权重越低，选择邻居节点中具有最高权重的节点作为簇头。在这种分簇算法中，需要一种机制来量化节点的移动性。一种简单的方法规定任何节点对的移动性为它们相对速度绝对值的时间平均，但是这种方法需要通过GPS来获得节点的位置。为此，可以采用一种聚集本地移动性指标，节点通过比较收到的来自某一邻居节点的连续两次的信号的强度来估计它们之间的相对移动性。在移动性较强时，最低移动性分簇算法可以明显地减少簇头更新频率，它的缺点在于节点权重的更新较频繁，簇头的计算开销较大，并且没有考虑系统的负载平衡和节点的能量损耗。
4. 组合加权分簇算法
簇头的选举对于网络的性能至关重要，需要考虑多种因素，并基于网络环境和业务需求进行合理的折衷。基于以上考虑，可以采用一种组合的加权分簇算法(WCA)。在WCA算法中，每个节点分配一个权值来指示该节点适合充当簇头的程度。每个节点的权值可以使用一个考虑多种因素的通用公式表示：Weight=a×mobility+b×degree+c×power+d×e nergy-left，其中参数a, b, c, d由应用和网络环境决定;Mobility表示节点移动的速度或相对邻居节点的移动性;degree表示节点度;power表示节点的传输功率;energyleft表示节点剩余的能量。此外，每个变量需要根据具体的应用选用合适的单位，并且还可以根据需要增加更多的变量。
5. 无簇头分簇算法
在实现分簇算法时，存在两种观点：不选举簇头或选举簇头。前者认为簇头承担过重任务而可能成为网络瓶颈，当簇头出现故障时，会严重影响网络的性能。如果不选举簇头，簇内每个节点需维护簇内和簇间的路由信息，维护开销较大，并且不能充分利用分簇结构带来的好处，例如实施网络管理和资源分配等。当存在簇头时，簇头充当簇内的协调者和管理者，并可以和关联节点构成虚拟骨干网络，从而方便地实现分级路由、移动管理和资源分配，减少维护簇结构所需的控制开销，特别是当网络规模较大时。在网络规模不大，节点密度较高并且节点的处理能力很低的情况下，为了防止簇头成为瓶颈节点，可以考虑采用无簇头分簇算法。基于分区的分级链路状态路由协议(ZHLS)利用无簇头分簇结构来提高路由协议的性能，簇内每个节点被同等对待，从而可以避免业务量瓶颈以增强系统的健壮性。
6. 考虑簇大小的分簇算法
大多数分簇算法产生的簇都是一跳有头簇或两跳无头簇，这种分簇结构实现起来相对简单，但是没有考虑簇内的节点数量，有时将会影响基于簇的网络协议的性能。当簇内节点数过多时，将会导致簇头负担较重;簇内节点数过少又使得簇的数量较多，簇的维护开销和分组投递时延较大。因此，需要通过某种机制来控制簇的大小和簇的数量。一种解决方法是根据节点的密度和数量来确定簇内节点与簇头的最大距离d。Max-Min d跳分簇算法是一种基于节点ID来选择簇头的多跳簇分簇算法，该算法可以有效地减少簇头数，算法的时间复杂性为O (d) 。另外，还可以通过限制簇内节点数来调节簇的尺寸，MMWN体系结构通过簇的分离/合并来限制簇内节点数。簇的分离和合并由三个参数控制：分离门限Nsplit，合并门限Nmerge和最佳尺寸Npref。如果一个簇的节点数超过Nsplit，那么将执行簇分裂过程;当簇内节点的数小于Nmerge时，它可能与相邻的簇合并，同时尽量使新簇的尺寸接近Npref。多跳簇可以减少簇的数量和分组的时延，但是会加重簇头的负担，并且簇结构的产生和维护更加复杂，特别是当节点运动性较强时。因此，应根据节点的密度、数量、运动模式和业务需求来确定簇的尺寸以优化网络的性能。
7. 基于地理位置的分簇算法
上述的分簇算法没有考虑节点的位置信息，如果可以借助GPS或者根据接收信号的强度来估算节点的位置坐标，那么可以采用基于地理位置的分簇算法。郭虹等人描述了一种简单的基于节点位置坐标进行分簇的方法(参见图2)：假定每个簇是正方形，互不交叠且大小相等，簇内不存在簇头，簇内节点可以直接通信，即节点的通信范围等于正方形簇的对角线长度。那么节点可以按照下式来确定自己所在的簇：
式中，x和y为节点的物理坐标;r为节点的通信范围;floor表示下取整; (x'，y') 表示节点所在的簇。
考虑到信道的空间重用，即相距两跳以上的节点可以重用信道而不发生干扰。另外，在基于节点的位置信息划分簇后，可以根据节点分布密度、移动性和发送功率来动态调整簇的大小以优化网络性能。这种基于地理位置的动态分簇算法能较好地对节点进行管理，但是消息开销较大。当节点的传输范围动态变化时，倾向于选择基于图的分簇算法，因为基于地理位置的分簇算法不能很好地适应这种情况。
8. 被动分簇算法
以上讨论的分簇算法都可以看作主动分簇算法，因为它们或者假设知道邻居节点信息，或者通过周期性交换控制分组来获得邻居节点信息。在这些分簇算法中，节点既使没有发送数据，也会引入大量控制开销，特别是当节点密度较高或移动性较强时。对于一些特殊的应用场合，如战术通信网络和传感网络，周期性的控制分组会暴露节点位置、造成信息泄密并会过多消耗传感节点的能量。为此，可以采用被动分簇算法，不使用专门的分簇控制消息，而是将数据的传输和分簇的形成紧密结合在一起。例如，基于信道接入的被动分簇算法(ABCA)在簇形成过程中，每个节点都试图接入控制信道来声明自己是簇头，一个节点如果在它的所有邻居节点中最先成功地发送了簇头声明控制消息，那么它成为簇头，即按照“最先声明优先”的规则来选举簇头。收到簇头声明消息的普通节点成为该簇头的成员节点。一旦某个节点成为簇头并且至少有一个成员节点，它将一直充当簇头直到它离开网络或者出现故障。当一个节点刚加入网络或想改变簇时，它可以根据接收到的簇头声明消息来选择加入一个邻居簇。被动分簇的开销较小，但是被动分簇算法得到的分簇结构是用户数据传输的副产品，如果节点不发送数据则不能形成簇结构。所以产生的簇的随机性较大，簇结构不够优化并不易控制，不能随时利用分簇结构带来的好处。因此，这种被动分簇通常用于提高广播协议的效率和某些特殊的场合。
9. 比较分析
综上所述，不同的分簇算法有不同的优化目标和使用场合，应根据网络环境和系统的要求进行合理选择。例如，最小ID分簇算法实现简单方便，但是没有考虑节点的能量损耗和负载平衡。最高节点度分簇算法可以减少簇头数，但是会进一步加重簇头的负担。最小移动性分簇算法能较好地适应节点的移动性，但是需要合理地估算节点的移动性。组合加权分簇算法综合考虑了影响分簇网络结构性能的多种因素，具有较高的灵活性和适应性。调节簇尺寸的分簇算法可以用来优化分簇结构的性能，但是实现较复杂。基于地理位置的分簇算法更加强调节点之间的地理分布，能更好地对节点进行移动管理，但是要求节点可以获悉自己的位置坐标，消息开销较大。无簇头分簇算法和被动分簇算法是两类比较特殊的分簇算法，前者的初衷是避免簇头成为瓶颈节点，但是削弱了分簇结构的效能;被动分簇算法可以减少开销，但是簇结构不够优化。
四、簇维护策略
在分簇网络中，节点会经常加入或离开簇，更为严重的是，剧烈的节点移动有时会导致簇头的更新和网络结构的重新配置，从而引入较大的计算和通信开销，并且严重影响其他网络协议的性能，如分组调度、路由和资源管理等。因此，需要合理的簇维护机制来尽量减量减少控制开销和维持簇结构的稳定。现存的许多簇维护机制采用周期性重新分簇的方法，这种簇维护策略中，簇更新周期很难确定。如果更新频率过低，簇结构不够优化;否则，控制开销过大，并且在重新分簇的时候网络无法获得簇结构带来的好处。这种簇维护策略通常适用于节点数较少并且移动性较低的场合。另一些机制需要每个节点了解其两跳范围内邻居节点的状况，簇维护的原则是尽量使节点度最高的节点及其邻节点保留在原簇中，以此来减少簇结构的变化，但簇维护的开销仍较大并且获得的簇结构也不够优化。还有一些机制采用动态的基于消息驱动的簇维护策略，这种簇维护策略可以根据网络环境和应用的需要设置各种簇维护门限和条件，一旦超过预设门限或条件满足时则触发相应的动作，包括簇的调整或重新分簇。这种方法可以在一定程度上减少簇维护开销，保持簇结构的相对稳定，并能适应节点的移动和链路质量的变化，是一种较好的簇维护策略。
具体而言，簇维护包括两方面内容：节点(链路)的管理和簇的管理。前者包括节点出现、消失和移动;后者包括簇的消失、分裂和合并。由于链路的产生、故障、删除、恢复对分簇结构造成的影响包含在节点出现、消失和移动造成的结果中，因此通常不再单独考虑。
五、结束语
基于分簇算法的分簇结构对于提高Ad Hoc网络的性能至关重要，分簇结构既有利于移动管理、资源分配和信道接入，又可以比较方便地采用结合先验式和反应式优点的混合式路由，此外还可以用来提高广播的效率和用于构造蓝牙网络。但是分簇算法本身会带来计算、通信和维护开销，为了减少分簇算法的负面影响，必须提高分簇算法的性能，特别是减少通信和维护开销。本文介绍、分析和比较了无线自组网中现存的多种分簇算法，包括有无簇头、单跳簇和多跳簇、主动分簇和被动分簇算法等，它们各有优缺点，必须根据用户需求和应用场合进行合理的选择。
摘要：分簇算法是构造分级网络结构的关键技术, 它的好坏直接影响着无线自组网的性能。本文介绍了无线自组网中分簇算法提出的背景, 并阐述了分簇算法的原则和目标, 并对无线自组网现存的多种分簇算法进行了详尽的分类介绍和比较分析, 包括有簇头和无簇头、单跳簇和多跳簇、主动分簇和被动分簇算法等。最后, 对簇维护策略进行了简要说明。
关键词：无线自组网,分簇算法,服务质量,虚拟骨干网,最小统治集
组网算法 篇2
1．光纤直接接到网吧，然后通过一光纤收发器将光信号转换成10M/100M电信号。接入采用光纤，速度快、稳定性好、障碍率低、抗干扰性特强。
2．用一路由器作为局域网的网关，此路由器在功能与性能上必须满足网吧网络的需求，由于它是专门用于路由转发、地址映射的硬件设备，在工作效率上比电脑主机强百倍，且具有非常优异的稳定性。此路由器需具备双以太口：一个用与光纤收发器连接、另一个用与交换机连接，连接介质均为网线。路由器作网关，路由转发能力强、稳定性好、具有很高的安全性，可以确保局域网内部机器安全上网无后顾之忧，而且可以保持长期在线。
3．用一交换机用于局域网内部互连。与集线器的共享总线式带宽相比，交换机使用独享式带宽，在功能和性能上远远超过集线器。交换机可以大大提高网络利用率，减少局域网内部冲突，提高上网速度。尤其是在较多机器同时运行的情况下，交换机发挥的作用将更大。
组网算法 篇3
本文主要研究无线Ad Hoc网络的路由技术, 通过对比现有的无线路由协议, 找出一种适合于社区等多障碍物环境下的多跳路由协议。
1 无线路由协议分类及关键技术
无线自组织网络的路由协议主要包括主动路由协议、按需路由协议、混合路由协议[2]。它们的优缺点见表1。
1.1 DSDV协议
DSDV协议是先应式路由协议, 其特点是利用目的节点序列号解决了传统DV算法中的路由循环和计数至无穷的问题。当节点收到多个不同的矢量表数据包时, 首先要检查序列号的大小, 采取序列号较大的来计算。如果序列号相同, 则看谁的路径更短。这样就避免了环路的产生[2]。
DSDV要求每个节点同时保存两个矢量表, 表中列出了所有可到的目的节点及到达该目的节点所需的跳数。每个节点周期性地发送自己的矢量表D (i) , 其他节点根据自己的DV表和从相邻节点收到的DV表来更新自己的路由表, 即对任意一个节点k, 有dki=Min[dkj+dji], jA, A为节点k收到的相邻节点的矢量表。DSDV的触发方式是根据路由表的改变来触发路由器的更新。每个节点周期性地和以它为起点的, 到其他目的节点的最短距离与自己已知的距离相比较, 若比已知的小, 则更新路由表[3]。
1.2 AODV协议
AODV协议是一种按需路由协议, 其特点是它根据业务需求建立和维护路由。即当有源节点需要向某目的节点通信时, 才在节点之间建立路由。且路由信息不会一直被保存, 它有一定的生命周期, 若某条路由已经不需要, 就会被删除[4]。AODV也是通过使用序列号来避免形成路由环, 这点同DSDV一样。
AODV路由协议主要分路由发现和路由维护以及路由删除三个部分[3]。为了建立一个路由, 源节点将广播一个RREQ (路由请求分组) , 收到RREQ分组的中间节点根据RREQ中的信息, 建立到源节点的路由, 并且将RREQ再发送给本节点的邻节点。目的节点收到RREQ则向源节点回复RREP (路由回复分组) [3]。AODV路由的分组无需包含完整的路径信息, 采用逐跳转发的方式, 从而减小了分组开销。
在AODV中, 一条已经建立起来的路由会被一直维护, 直到源节点不再需要它为止。移动Ad Hoc网中节点的移动仅仅影响含有该节点的路由, 这样的路径被称为活动路径, 不在活动路径上的节点移动不会产生任何协议的动作, 因为它不会对路由产生任何影响。如果是源节点移动, 就会重新启动路由发现建立新的路由[4]。
1.3 ABR协议
ABR协议是从路由的有效时间的角度来设计, 采用路径有效时间的长短 (稳定性) 而不是路径长短, 作为选择路径的标准。
ABR由3个部分组成:路由建立阶段、路由重建阶段和路由删除阶段。它明确提出使用邻节点空间、时间、连接和功率特点来构建一条生存时间长的路由。因此, 在自组织网络中, 应当要求路由可以持续较长一段时间, 最好持续到一个连接结束。另外, ABR协议是源始发协议, 意味着不需要周期的路由更新, 也不需等待路由收敛, 自然地克服了表驱动协议的暂时环路现象。ABR协议不使用路由缓存, 因为维护这些缓存信息的有效性将占用大量的控制开销。
2 路由协议性能评价标准
路由协议性能评价标准的主要指标:
1) 丢包率:网络中数据传输是以发送和接收数据包的形式进行的, 理想状态下发送了多少数据分组就能接收多少数据分组, 但是由于信号衰减、网络质量等诸多因素影响下, 可能产生数据分组丢失[5]。在单位时间内未收到的数据分组与发送的数据分组的比率就是丢包率, 这个数字越小越好。丢包率的计算公式见式 (1) 。
2) 端到端平均时延:指单位数据包从源节点到目的节点所用的时间, 时延越小, 说明响应越快, 网络质量越令人满意。该统计量反应了网络的拥塞状况, 计算公式见式 (2) 。
3 实验及仿真
本文通过NS2仿真平台着重对DSDV和AODV进行比较分析[7], 在相同环境下, 通过对比延时率、丢包率这两种指标来比较这两种协议的优劣。
3.1 延时对比
对比图1和图2, 在130 s时, 0节点开始发包, DSDV因为之前已经交换了路由信息, 所以延时很小就开始发送数据包, 而AODV在130 s时才开始广播寻找路由路径, 所以延时明显增加。直到250 s, 两组数据传输都比较稳定。250 s后, 由于节点开始移动, 使得路由路线频繁变换, 当节点到达相对位置后两组都开始寻找路径。DSDV必须定时与临近节点交换路由信息, 直到接收到来自接收端的路由响应消息, 开销比较大, 直到300 s后才找到路径, 开始传输数据。而AODV源节点发送数据广播一个路由请求消息, 附近节点收到后再次广播, 直到请求消息到达目的节点或到达知道目的节点路由的中间节点, 目的节点或中间节点沿原来路径返回响应消息, 开销比较小[6], 所以260 s后就开始传输。延时小。
3.2 丢包率对比
对比图3和图4, DSDV在250 s之前基本没有丢包, 数据传输相对稳定。而AODV在150 s之前未建立完整路由时丢包比较严重。在250 s以后, 随着节点开始移动, 在移动情况下, DSDV协议的丢包率明显大于AODV, 证明在移动情况下AODV开销小于DSDV。移动情况下, 按需式路由协议优于主动式路由协议[7,8]。
4 结论
通过对比典型主动路由协议DSDV和典型按需路由协议AODV的延时率、丢包率以及吞吐量的数据得知, 当网络拓扑频繁变化时, 按需路由协议的性能优于主动路由协议当网络拓扑变化相对较慢时, 主动路由协议的性能优于按需路由协议。
摘要：随着人们生活水平的提高, 各种小型自动处理设备逐渐走进了人们的日常生活。为了方便对这些设备进行自动化管理, 就需要对小区内的设备进行组网。针对此, 主要研究无线自组织网络中的数据路由协议和算法, 实现每个自动处理设备到信息控制中心的自动信息传输。
关键词：无线自组织网络,路由协议,信息传输,组网
参考文献
[1]王金龙, 吴启辉.认知无线网络[M].北京:机械工业出版社, 2010:12.
[2]方何旭, 何蓉.短距离无线与移动通信网络[M].北京:人民邮电出版社, 2004.
[3]孙弋.短距离无线通信及组网技术[M].西安:西安电子科技大学出版社, 2008:226-297.
[4]陆琳玉.无线移动自组织网络移动路由的设计与仿真[D].成都:电子科技大学通信与信息系统硕士学位论文, 2003.3.
[5]Wu J.“Dominating-set-Based Routing in Ad Hoc wireless Networks”, wireless Networks and Mobile Computing, I.Stojmenovic (ed.) [M].John Wiley&Sons, 2002:425-450.
[6]夏丹丹, 李刚, 李加庆, 等.基于NS2的AODV改进协议仿真实现[J].微计算机信息, 2008 (8) :128-130.
[7]方路平, 刘世华, 陈盼, 等.NS-2网络模拟基础与应用[M].北京:国防工业出版社, 2008.
VOIP组网实例 篇4
VoIP(Voice over Internet Protocol)是利用 IP 网络传送语音，为用户节省话费的一种通信设备;主要适合有分支机构的企业和集团用户，能给企业节省大量的国际、国内和郊区长途话费。
VoIP透过因特网，可以将语音数字化，经过压缩，以封包型态传输，再解压缩还原为语音，藉s此执行通话功能，如此将可大幅节省传统电路式 交换网络的扩充成本，并且能更有效的利用现有数据网络与传输骨干网络，目前最常运用VoIP技术的就是因特网电话。由于VoIP可以为企业或个人节省可观的长途电话费，尤以跨国企业受低廉电信费的吸引纷纷转用VoIP，因此，许多人都在谈论VoIP，许多的服务及设备公司也都想参与VoIP的发展。
VoIP效益：
1、节费：节省电话费用是VoIP明显而立即的效用，尤其长途或国际电话费的节省，对于跨国企业而言更是重要节省营运成本的方式之一。
2、简化：通话与数据开放性网络(Networks)的整合可以容许更多标 准作业及减少硬设备需求，家庭或企业不须备置语音与数据传输两套网络，所有的通讯将整合在单一网络。
3、先进：VoIP长期效益包括支持多媒体应用等，这是目前的传统电 话系统所无法与之一较长短的。
VoIP通讯技术：
目前VoIP 所使用的通讯技术有两大主流，分别是H.323及MGCP。H.323是由国际电信联盟(ITU-T)所制定，Microsoft NetMeeting等视频会议软件即是使用H.323来作沟通，具有容易管理的网络架构与高附加价值;MGCP(Media Gateway Control Protocol)是由IETF(Internet Engineering Task Force)所制定，它相对于H.323在软件及通讯协议的设计上较为容易。另外，新一代的网络电话通讯协议与架构有MEGACO、SIP、SIGTRAN等。
传统的电话网(PSTN——Public Switch Telephone Network)是以电话交换方式传输语音，所要求的传输宽带为64bit/s，而VOIP 是以IP数据网络为传输平台，对模拟的语音信号进行数字化，并进行压缩，打包等一系列特 殊处理使之可以采用无连接的UDP协议进行传 输。随着近几年公共互联网以及高端企业内部 网络的普及，如何利用现成的公共互联网以及 企业内部的的数据网络来达到降低企业长途和 国际电话费用以成为企业决策者的当务之急。
一、VoIP基本概念
VOIP是建立在IP技术上的分组化、数字化传输技术，其基本原理是：通过语音压缩算法对语音数据进行压缩编码处理，然后把这些语音数据按IP等相关协议进行打包，经过IP网络把数据包传输到接收地，再把这些语音数据包串起来，经过解码解压处理后，恢复成原来的语音信号，从而达到由IP网络传送语音的目的。
IP电话系统把普通电话的模拟信号转换成计算机可联入因特网传送的IP数据包，同时也将收到的IP数据包转换成声音的模拟电信号。经过IP电话系统的转换及压缩处理，每个普通电话传输速率约占用8～11kbit/s带宽，因此在与普通电信网同样使用传输速率为64kbit/s的带宽时，IP电话数是原来的5～8倍。
二、VoIP基本原理
VOIP是建立在IP技术上的分组化、数字化传输技术，其基本原理是：通过语音压缩算法对语音数据进行压缩编码处理，然后把这些语音数据按IP等相关协议进行打包，经过IP网络把数据包传输到接收地，再把这些语音数据包串起来，经过解码解压处理后，恢复成原来的语音信号，从而达到由IP网络传送语音的目的。
IP电话系统把普通电话的模拟信号转换成计算机可联入因特网传送的IP数据包，同时也将收到的IP数据包转换成声音的模拟电信号。经过IP电话系统的转换及压缩处理，每个普通电话传输速率约占用8～11kbit/s带宽，因此在与普通电信网同样使用传输速率为64kbit/s的带宽时，IP电话数是原来的5～8倍。
三、VoIP的基本传输过程
1、语音-数据转换
2、原数据到IP转换
3、传送
4、IP包-数据的转换
5、数字语音转换为模拟语音
四、VoIP的实现方式
在实现方式上，VOIP有电话机到电话机、电话机到PC、PC到电话机和PC到PC等4种方式。最初VOIP方式主要是PC到PC，利用IP地址进行呼叫，通过语音压缩、打包传送方式，实现因特网上PC机间的实时话音传送，话音压缩、编解码和打包均通过PC上的处理器、声卡、网卡等硬件资源完成，这种方式和公用电话通信有很大的差异，且限定在因特网内，所以有很大的局限性。电话到电话即普通电话经过电话交换机连到IP电话网关，用电话号码穿过IP网进行呼叫，发送端网关鉴别主叫用户，翻译电话号码/网关IP地址，发起IP电话呼叫，连接到最靠近被叫的网关，并完成话音编码和打包，接收端网关实现拆包、解码和连接被叫。对于电话到PC或是PC到电话的情况，是由网关来完成IP地址和电话号码的对应和翻译，以及话音编解码和打包。
五、VOIP的优势
低廉的通信资费
低廉的网络租赁维护费用
视频会议、数据存储转发、传真、流媒体
网络结构:要求14个分点实现VOIP通话
本文将介绍笔者参与建设的某省级国家统计局基于迈普方案的VOIP组网方案。该方案要求全省14个市的统计局与省机关实现全面VOIP通话，当然各单位内部也能实现各自的VOIP通话，我们可以看到这个VOIP语音方案对原有网络结构是不做任何改动的，网络配置也不需要做任何改动，只需要在语音语关上做是相关配置，若原电话布线系统不健全，可能需要进行桌面电话集中到网络中心的电话布线。在这个方案中，VOIP电话系统利用现在的统计局专线网络与各市局相连，然后各市局机关VOIP电话系统连接到现有办公局域网就可以了。网络结构非常简单。
组网设备：语音网守和语音网关
迈普VOIP语音组网方案需要两种关键的语音设备，分别是：语音网守和语音网关。
(一)语音网守
IP电话网守是H.323 VoIP系统方案的关键设备，负责实现地址解析、接入认证和带宽管理等核心控制功能。网守最重要的功能是地址解析，它在它的路由表中查找目的网关的IP地址，如果目的网关不在本区域中，向上级网守或邻近网守请求在别的区域(一个网守就是一个“区域”)中查找。找到目的网关后返回对应网关的IP地址，这样就可以跨语音网关通话。迈普MyPower VGK2X系列IP电话网守由VGK2X和VGK2X-B两个型号构成，基于专用嵌入式结构设计，采用迈普带宽控制、聪明路由等专有技术，具有安全可靠、功能强大、组网灵活等特点，适用于组建各类规模的H.323 VoIP网络，或者多协议的VoIP协作通信网络。
本方案采用的是一台VGK2X(图2)网守部署在省局，各市局语音网关在其上注册，最终实现各市局跨语音网关远程通话。
(二)语音网关
迈普语音网关MyPower VG系列包括：VG M6000、VG2000、VG800和VG A600四个型号，与迈普VGK2X系列网守配合使用，可为用户构建以VoIP为基础的网络语音通信平台。
MyPower VG系列语音网关同时支持成熟的H.323协议和先进的SIP协议，采用迈普专有通话质量提升技术，包括静音压缩及舒适噪声、回波抵消功能、动态JitterBuff调整和丢包补偿等机制，提供可与传统PSTN相媲美的高品质通话。并采用迈普特有的“聪明路由”，能够动态地为当前呼叫选择最佳路径，即使在IP网络阻塞和单点设备故障等异常情况下，也能够为用户提供高品质的通话。“1：1绑定”技术，可以实现VOIP电话与原有PSTN电话一对一绑定，能够完全不改变用户的原有电话号码和拨打习惯，并且在单点设备掉电等异常情况下，也能够为用户提供PSTN通话，保证电话永远不会出现断路。这样，使用电话的用户完全不会感觉得到他或她在打的电话是经过VOIP还是普通市话。但本方案中，采用的是“纯”的IP电话，语音网关没有接入PSTN线路，因此没有做“1：1绑定”。MyPower VG系列语音网关还支持PSTN附加业务和特色增值业务，极大提升VoIP系统价值，包括：电话会议，群组振铃，呼叫代答，来电显示，呼叫转接，呼叫等待，热线拨号，IVR录音等增值功能。
在本方案中，在省局机关采用两台MyPower VG M6000来实现大容量的电话接入，分别是64门和94门;在各市局采用MyPower VG 2000来实现16~32门的电话接入。
MyPower VG M6000是核心级语音网关，采用全模块化设计，支持接入端口类型、端口数量和处理能力的按需配置，支持板卡热插拔、双电源冗余、“1:1绑定组网”和“掉电逃生”，也就是语音网关掉电时，一样可以打电话。最大可以提供4路E1中继(用来接入外线电话)和96线模拟接入(用来接到桌面普通电话机)。
MyPower VG2000是地市级语音网关，采用全模块化设计，支持业务端口类别、端口数量和处理能力的按需配置，最大提供1路E1中继和32线模拟接入或提供48线模拟接入。
如何进行号码规划方案
有两种号码规划方法：一种是纯的VOIP电话方案，自定义本单位内部的VOIP电话号码;另一种是使用原有的电信市话号码做为VOIP电话的电话号码，并做“1：1绑定”。
方案1：自定义VOIP电话号码方案
这种方案一般使用三位或四位数字来规划，号码随意制订。上面已经提到过本方案是“纯”的VOIP电话组网，也就是没有接入市话线路，因此不需跟市话号码做“1：1绑定”。若做“1：1绑定”，我们一般采用市话的号码来规划VOIP号码，这样方便记忆和操作。在这里不需绑定市话号码，所以采用自定义三位(数字)小号，在前面加各市区号来组合成VOIP电话号码，本地(指语音网关内部)通话直拨小号，跨市局通话，前面加拨区号，由网守来路由。
这种方案只使用模拟接入板卡模块(FXS卡)，用来接入普通桌面电话机。
方案2：使用原有电信市话号码来作为对应的VOIP电话号码
这种方案使用桌面电话的原有电信市话号码作为内部VOIP电话的号码，这样最终使用电话的用户还是按照原来拨号方式打电话，他(她)并不知在打的电话是经过IP网络还是经过电信公司的市话线路。在VOIP网络通畅时，电话是优先经过VOIP链路通话的，只有在VOIP出现故障或打外线电话时，才会通过电信公司市话线路通话。
这种方案除了使用模拟接入板卡模块(FXS卡)，用来接入普通桌面电话机，还要使用VOS卡或E1中继模块来接入电信市话，这样在打外线、VOIP线路不通或者语音网关掉电的情况下，均可以用市话正常通话。
设备链接配置
迈普的这套VOIP语音方案只适合在已经部署了完善的内网专线上运行，语音网关和语音网守的安装都非常简单。只要保证专线内网的路由是通的，没有做限制VOIP所使用的IP地址和端口的访问控制列表，中间经过的防火墙没有对VOIP所使用的IP地址、端口、协议等参数做了限制就可以了。在本工程中，笔者遇到的拦路虎很多都是各种不同品牌的防火墙对VOIP系统的限制，有时是无法理解的，明明似乎是对VOIP全放开了，网络能PING得通，但VOIP电话就是不通。这需要网络工程师和网管人员用心来研究防火墙的设置问题。实际工程中，经常是绕过防火墙就没有问题，一经过防火墙就可能出现注册不上网守或通话不正常的情况。
物理连接：
(1)网络部分，只需将语音网关和网守的以太网口接入局域网交换机的交换口就行了。
(2)桌面电话过来的电话线应打在标准的RJ45配线架或者110配线架上，然后使用相应接口的电话跳线接到语音网关的模拟卡上对应号码的RJ11接口上。语音网关若需接入市话线路的，就将来自电信公司的电话线接在VOS卡的RJ11接口上即可。
总结：迈普VOIP方案的安装部署非常简单，几乎不用做原有专线内网的任何改造。配置命令也不复杂，关键位置也只有少数几句而已。迈普语音方案具有极高的性价比优势，组网以后，本系统单位内部的电话将全面实现免费通话。本语音方案非常适合具有专线内网的单位实施。
根据语音网关的型号不同，语音网关的连接方法一般有以下几种： 一种是最简单功能的语音网关，没有路由器，只有LAN口，FXS电话接口和电源接口。这种语音网关首先需要通过路由器上网，一般不能直接接猫（cable modem），因为这样的语音网关没有分配IP地址的解析功能。也就是说，语音网关的LAN口用网线连接路由器的宽带出口，FXS口接普通电话，电源线当然就不用说了。
第二种是带路由器功能的语音网关，这中语音网关一般都有一个WAN口（也有的叫INTERNET口）和一个以上的LAN（有的叫ETHERNET)，这样的语音网关也有两种接法，一是直接接在猫（modem)上，如果是用中国电信电话线的ADSL上网，就要对这种语音网关的路由器进行设置，设置方法基本和普通路由器的设置一样。它的LAN口可以接电脑上网。另外一种就是接在其它路由器上（其实其它路由器也可以接路由器），这样一般就不用对其路由功能进行重新设置。而其FXS或FXO的电话接口就直接接电话就可以了。
第三种，有的语音网关带有FXO口，也就是通常说的逃生口，逃生口的功能是，当设备因为断电断网等原因不能通过网络打电话的时候可以通过逃生口连接pstn（公共电话接入网)也就是普通的电话线接口以便切换到传统电话拨打方式上。传统电话运营商（如中国电信）的电话线接入逃生口后，不影响外部电话拨打原来运营商提供的电话号码，也就是说可以接听原来的电话，而打出电话时是自动采用网络电话方式拨出的，如果网络有故障，网络电话不清楚或者无法打通，这时候先拨打一个转切号（一般是“9”），就可以转用到传统电话了。这种带FXO口德好处就是可以接听打入的电话和防止网络故障时保证通话。
组网算法 篇5
中压载波通信借助电力公司自身的10kV配电网进行数据传输,不需要投资敷设新的通信电缆或昂贵的无线数据传输系统,也不需要支付进行连接的费用,具有可靠性高、投资小、灵活性强等优点。因此,其可以成为城市配电自动化通信的首选方式之一。然而,电力线并不是专门用于传输通信数据的,在传输通信信号时,信道特性相当复杂,通信还存在传输线路阻抗不匹配,传输信号具有较高选择性衰落,传输距离很长需要考虑中继和电力信道噪声特性,以及专用的有线信道和无线信道噪声特性不同[1,2]等问题,此时一般会采用选频通信、中继通信和抑制噪声干扰等方法。其中,中继通信是提高配电线载波通信距离和可靠性的主要手段。
在中压载波通信中,必须采用主从式的通信方式,一台主载波器必须管理多台从载波器,这就决定了在使用中压载波通信时必须进行组网设计[3]。人工组网设计是按预先指定的方式固定路由,这种方式不能动态适应电力线环境的变化,很难有效可靠地进行通信,更不能满足规模日益扩大的载波电力线的通信。因此,中压电力线载波通信的自动组网研究具有十分重要的意义。
目前研究较多的通信组网方法有遗传算法(GA)[4]、模拟退火法(SA)[5]、禁忌搜索算法(TS)[6]、蚁群算法(ACO)[7]、粒子群算法(PSO)[8]等。这些仿生算法的研究,在理论和应用中不断发展,但也存在一些自身缺陷,其相关数学分析还比较薄弱,算法中涉及的各种参数设置一直没有确切的理论依据,通常都按照经验型方法确定,对具体问题和应用环境的依赖性比较大,需要不断改进。
本文提出一种较为简单的适合10kV电力线载波通信的,基于通信质量最优化的动态路由组网算法。这种算法是在非交叠分簇路由算法[9]和一种低压自动组网方案[10]上进行改进的动态路由算法。文献[9]中的算法简单易行,但是已经获得ID号的节点退出分簇过程中,初始路由表可靠性不高,抗毁性不强。文献[10]虽然加上了动态重构和优化的方法来克服上述缺点,但其初始分层方法与文献[9]基本相同,其耗时分析只包括逻辑分层及路由初始化时间分析,并未将优化的时间计算在内,而优化所采取的策略基本与初始分层相同,需要通信进行路径测试,所需要的时间不可忽略。本文采用的算法在初始分层时各子站间的路径便已经完备,优化时只需从路由表中进行操作,不再与各子站进行通信,因此其耗时很短,可以忽略。
1 基于通信质量最优化动态路由算法
1.1 通信协议设计
本文算法参考IEC 870-5-101协议[11]及循环远动协议定义相应的通信协议。信息以帧为基本单元传输,每帧由帧起始符、标志域、控制域、数据长度域、数据域、帧信息纵向校验域及帧结束域等组成,每个域由一定字节组成。其中,命令帧的数据格式如图1所示,响应帧的数据格式如图2所示。
在帧格式中,起始域标态一帧信息的开始。控制域表示报文传输方向及用户数据级数。二级功能代码根据DL/T 721—2000《配电网自动化系统远方终端》的基本功能要求制定。目的板号表示主站向子站发送的报文所要发送到的目的子站板号。中继板号表示用于中继通信的中继子站号,根据路由表变化实现自动中继。数据位记录主站发送M包数据中的成功次数s和失败次数f,且有s+f=M。根据数据位返回的噪声大小和信号大小,可计算出信噪比。通信频率表示当前通信的频率。循环冗余码校验(CRC)表示从起始位到通信频率进行奇偶校验的结果。结束符表示一帧信息的结束。
1.2 初始分层算法
设定有主站和n个子站,每个子站有自己的站号,记为1,2,…,n。任意子站至少与一个其他子站通信,即不存在通信孤立点,主站与子站完成一次完整通信不发生冲突的时间为Tm。组网过程中信道的通信质量不变。设定线路返回失败次数固定值FC,当线路返回失败次数f小于FC时,该路径为有效通信路径。
1)在时间Tm内,主站向所有子站发送数据,子站向主站返回响应帧,主站分析响应帧数据,若M包数据中失败次数f≤FC,则定义该子站逻辑层数为1,分配逻辑地址,并记录下噪声大小和信号大小,算出信噪比。若失败次数f>FC,则进行下一次的分层和逻辑地址分配。若有n1(1≤n1≤n)个子站有效通信,则逻辑1层子站数为n1,剩余子站数为n-n1,若n1=n,即逻辑1层包括所有子站,则分层结束,否则继续分层。
2)逻辑2层的分层中,以逻辑1层的子站为中继站,中继站按照逻辑地址从低到高依次分层。主站向剩余n-n1个子站发送数据,通过返回的数据分析有效通信路径,分配逻辑地址,记录信噪比。若有n2(1≤n2≤n-n1)个子站有效通信,则逻辑2层的子站数为n2,剩余子站数为n-n1-n2,若n1+n2=n,即逻辑1和逻辑2层包括所有子站,则分层结束,否则继续分层。
3)在逻辑i(i>1)层中,主站以已分层的子站为中继站向剩余的个子站发送数据,通过返回的数据分析有效通信路径,分配逻辑地址,记录信噪比。若有个子站有效通信,则逻辑i层有ni个子站。剩余子站数为,若,则分层结束,否则继续分层直至所有的子站终端都分配到逻辑地址。
图3为初始分层后的路由表示意图。
1.3 初始路由表的通信质量优化
初始分层的路由表结构较为复杂,通信质量不高,子站终端有多条路径,需要对其进行优化来提高通信质量,完成通信质量的最优化。设定优化后的子站终端与上层终端的通信路径最多为P条。初始分层的路由表优化具体步骤如下。
步骤1:设定组网过程中通信信道不变,因此,对已建立的初始路由表进行优化,首先对逻辑2层的所有子站终端进行路径优化,若终端只有一条路径则不改变,若终端有多条路径,则分析每条路径的信噪比,记录信噪比较大的不超过P条的通信路径。
步骤2:同理优化逻辑3层,在逻辑2层的基础上对逻辑3层的所有终端进行优化,记录信噪比较大的不超过P条的通信路径。
步骤3:继续相同的步骤,直到所有的路由都完成优化。
1.4 路由表的维护和重构
由于电力线信道环境的特殊性和时变性,必须对路由表进行维护和重构。路由表维护是指当已建立的路由表变得无效或为了寻找更加适合当前电力线通信的更优路由,对路由表进行动态更新的过程。
当主站按照路由表向某一子站终端发送命令时,若主站与该子站之间不止一条路径时,则优先选择信噪比较大的通信路径,若通信失败则选择信噪比次大的通信路径,直到通信成功。每一次通信主站将响应帧返回的信噪比代替原来的信噪比。
如果在一定时间内,该子站的所有路径都通信失败,则主站确认该子站路径不适合当前信道,删除其通信路径,对该子站进行路由局部重构。局部重构时,按照初始分层的方法,主站向该子站发送重构命令帧,若返回的响应帧显示通信无效,则以逻辑2层的子站为中继站向该子站发送数据:若通信成功则记录初始路径,并进行优化;若失败则继续使用二级中继进行分层,直至通信成功。如果逻辑n层以后都不能与该子站通信,则认为其已损坏或移出网络,主站删除该子站。
若主站按照路由表向多个子站终端发送命令的通信路径都失败,则所有子站重新建立路由表。
1.5 逻辑分层和初始化耗时分析
设定对各终端子站进行逻辑分层时,主站与一个子站之间的通信在Tm内完成,组网的总时间(即各逻辑层分层时间之和)为Ttotal。每一逻辑层需要的时间为上层每一个站点与未分层的子站通信时间之和。Ttotal计算公式如下:
式中:k为逻辑层数。
2 仿真与结果分析
2.1 仿真环境与参数
在MATLAB中模拟主站和n个子站,设定n=20,构建XY坐标系,坐标值均为-10~10,主站位于(-10,10)处,20个点均在该坐标内按图5所示物理拓扑结构图有序分布,并且不存在通信孤立点。以两点间的通信距离与最大有效通信距离D的大小判定代替实际项目中的失败次数f与FC的大小判定来确定通信路径是否有效。两点间的距离越小,表示两站间的通信失败次数越少,质量越好,信噪比越大,抗毁性越强。
2.2 MATLAB初始逻辑分层及优化仿真
图6(a)为D=6时初始逻辑分层通信结构图。图6(b)为P=1时路由表进行优化后的通信结构图。图6(c)为P=2时路由表进行优化后的通信结构图。图7为D=27时初始逻辑分层通信结构图。图中,2个标号分别为子站的站号和逻辑地址。
从上面仿真图可知,通过逻辑分层建立路由表可以实现电力线网络的中继功能,实现主站与任意子站的通信。
路由表优化后,整个网络得到了简化,当网络出现问题,P=1时需要进行重构,P=2时只需启用另外一条通信路径即可,将节省重构的时间,提高通信的实时性和整个网络的抗毁性。因此,综合考虑网络通信状况和通信的质量及抗毁性可以选择合适的P值进行组网优化。
2.3 初始逻辑分层及优化通信质量分析
图8给出了不同D值和P值下组网的平均通信距离变化。
从图中可看出,在相同D值下,路由表优化后的平均通信距离比初始分层的平均距离要小,即优化后通信质量得到了提高,抗干扰能力得到了加强。当D值达到一定值时,主站能与所有的子站直接通信,3种情况等效,通信质量相同。
2.4 逻辑分层及优化的耗时分析
图9为不同D值时的耗时情况(以Tm为基准进行了标幺化)。
结合图6(b)、图7和图9可知,一般情况下D值越大,通信质量越好,逻辑层数k相应越小。因此,逻辑分层和初始化时所消耗的时间也会相应减少。
3 结语
本文在非交叠分簇路由算法上进行改进,提出了一种适合10kV电力线载波通信的基于通信质量最优化的动态路由算法。
1)该算法对现有的通信协议进行相应改变,通过发送命令帧和响应帧,从返回的数据中使用动态路由算法进行自动组网。
2)本文使用MATLAB对算法进行仿真分析,证明该算法简单可行,可以实现电力线网络的中继功能,实现主站与任意子站的通信。
3)路由表优化后通信质量得到了提高,抗干扰性和抗毁性得到了加强。
4)耗时会随着通信质量的增加而减少,达到最优质量时稳定。
该算法将在实际项目中进行试验和改进,为中压电力线载波自动组网提供一种参考方案。
摘要：为了实现远距离传输,获取更高通信质量,提高通信的可靠性和抗毁性,提出了一种适合10kV电力线载波通信的改进动态路由自动组网算法,其以通信质量最优化理论和非交叠分簇路由算法为基础,并结合相应通信协议实现自动组网的目的。该算法以10kV电力通信网中的主站和子站终端为网络节点,按照通信方式进行逻辑分层,建立初始路由表,并对路由表进行基于通信质量的优化、更新及重构策略设定。在MATLAB环境下对该算法进行了模拟仿真,分析了通信质量和耗时。仿真实验证明,该算法能够实现中压电力线载波通信的自动组网,有效提高网络的可靠性和抗毁性。
关键词：电力线载波通信,自动组网,质量最优化,逻辑分层
参考文献
[1]邢志民,侯思祖,李晶,等.中压电力线信道特性的测量与研究[J].华北电力技术,2005(10):1-4.XING Zhimin,HOU Sizu,LI jing,et al.Measurement andresearch of channel characteristics for medium voltage power line[J].North China Electric Power,2005(10):1-4.
[2]RAMSELER S,ARZBERGER M,HAUSER A.MV and LVpowerline communications:new proposed IEC standards[C]//Proceedings of Transmission and Distribution Conference,April11-16,1999,New Orleans,LA,USA:235-239.
[3]王宏亮.基于中压电力线载波的通信技术研究[D].哈尔滨:哈尔滨工业大学,2006.
[4]徐晶,王成山,李晓辉,等.基于自适应遗传算法的配电网改造方案优化[J].电力系统自动化,2007,31(14):111-115.XU Jing,WANG Chengshan,LI Xiaohui,et al.Reconstructionscheme optimization of distribution network based on adaptivegenetic algorithm[J].Automation of Electric Power Systems,2007,31(14):111-115.
[5]LIAO G C,TSAO T P.Application of a fuzzy neural networkcombined with a chaos genetic algorithm and simulated annealingto short-term load forecasting[J].IEEE Trans on EvolutionaryComputation,2006,10(3):330-340.
[6]EL RHAZI A,PIERRE S.A tabu search algorithm for clusterbuilding in wireless sensor networks[J].IEEE Trans on MobileComputing,2009,8(4):433-444.
[7]DORIGO M,BIRATTARI M,STUTZLE T.Ant colonyoptimization[J].IEEE Computational Intelligence Magazine,2006,1(4):28-39.
[8]卢志刚,董玉香.基于改进二进制粒子群算法的配电网故障恢复[J].电力系统自动化,2006,30(24):39-43.LU Zhigang,DONG Yuxiang.Distribution system restorationbased on improved binary particle swarm optimization[J].Automation of Electric Power Systems,2006,30(24):39-43.
[9]戚佳金,刘晓胜,徐殿国,等.低压电力线通信分簇路由算法及网络重构[J].中国电机工程学报,2008,28(4):65-71.QI Jiajin,LIU Xiaosheng,XU Dianguo,et al.Simulation studyon cluster-based routing algorithm and reconstruction method ofpower line communication over lower-voltage distribution[J].Proceedings of the CSEE,2008,28(4):65-71.
[10]冉庆华,吴玉成,祁美娟.低压电力线载波通信网络自动组网方法研究[J].电力系统保护与控制,2011,39(10):53-58.RAN Qinghua,WU Yucheng,QI Meijuan.Research onautomatic routing method of low-voltage power line carriernetwork[J].Power System Protection and Control,2011,39(10):53-58.
组网算法 篇6
雷达组网优化部署属于最优化问题范畴, 追求防空侦察效能最优是雷达组网最主要的战术目的。区域防空雷达组网要提高雷达抗电磁干扰、抗隐身技术、抗低空突防、抗反辐射导弹的能力, 就是要在多个优化方案中获取最优解, 这就涉及到对有限的雷达资源如何合理分配, 进行优化布站。早期工程应用中, 对雷达布站的研究探索主要是集中在简单的均衡布站和加权布站, 分别对应面防御和点防御的战术目的, 均衡布站就是在警戒任务区周边等间隔的布置雷达, 加权布站则是针对重点部位以敌可能来袭方向进行倒三角式加权布站, 力求空域覆盖有重叠减少盲区面积, 由于没有精确细致的部署方案便造成一定程度资源浪费, 使雷达网没有发挥应有的作战效能。
利用现代优化方法解决雷达资源分配最优化问题是近期研究热点, 尤其是实战条件下面对复杂战场态势, 要完成雷达网合理部署, 依赖现代优化算法可以在很短时间内得到自动部署方案, 大大提高了雷达部署的科学性和准确性。目前, 研究较多的现代优化方法主要包括:禁忌搜索算法、模拟退火算法、遗传算法、蚁群算法、粒子群算法和人工神经网络算法等。这些算法借助计算机工具对求解资源分配问题有普遍的适用性。其中, 遗传算法借鉴生物进化特征, 通过遗传选优、交叉配对和基因变异等运算具备很强的全局搜索能力, 但算法收敛速度太慢, 后代个体有一定的随机性从而容易丢失最优解。粒子群算法讲究信息共享, 粒子的运动方向性很强, 有较高的收敛速度, 但很容易陷入局部最优。本文综合两种算法优点开发出遗传粒子群算法, 通过仿真实验证明该算法能在更短时间周期内得到全局最优化的雷达布站方案。
2 数学模型
雷达网的防控侦察效能评价指标除了作战任务划定的警戒任务区和重点责任区, 还应包含雷达组网针对不同空袭目标及威胁情况确定雷达网不同功能贡献度, 由于雷达在实战中面对复杂的地形、电磁环境和多样的空袭目标威胁, 这里我们提出雷达网基于“四抗”功能的加权模型, 即最终汇总成雷达网防空侦察效能评价函数F。
式中:将雷达探测空域高度分成n个部分, wj拜师不同高度下的权重, G1j、G2j对应不同高度下雷达网所能覆盖警戒任务区和重点责任区面积, S1、S2为划定的警戒任务区和重点责任区面积, f1j～f4j分别为不同高度下四抗效能达到的函数值, 雷达网优化部署问题转化为多目标优化加权问题。下面的实验将以求解第一项为例比较不同算法优劣。
3 遗传粒子群算法
3.1 设计思想
遗传算法主要借鉴了生物进化的一些特征, 借用“适者生存”规律, 通过对现实问题进行染色体编码, 经过遗传选优、交叉配对、基因突变3种遗传算子得到新一代个体, 然后计算个体适应度, 以个体适应度为依据完成对局部最优点的选取和最差点的淘汰, 保持群体数量不变, 这样一次遗传运算完成, 再经过数代遗传完成对全局搜索的最优化处理。
粒子群优化算法则是基于对位置和速度的计算, 与达尔文进化思想不同的是体现群体中个体之间的协作和信息共享, 不断从别的个体及经验中提取信息, 通过不断修正位置和速度完成对全局的探索, 同时保存迄今为止个体最优点和群体最优点。全局最优点一定会出现在局部最优点中, 所以每一次迭代运算都能使个体粒子向着局部和全局最优点运动, 算法具有编码简单、收敛快速的特点。
综合以上两种算法, 遗传算法有较强的全局搜索能力但编码复杂, 数据精度不高, 收敛性不好, 粒子群算法有较强的收敛能力, 编码简单且精度很高, 但全局搜索能力较差。所以, GPSO算法旨在以遗传算法为主体进化思想, 保留交叉配对和基因突变算子取其全局搜索能力, 进化手段则采取粒子群粒子随速度智能更新的移动方法, 使每一次迭代粒子个体经速度矢量的求和运算, 瞄准个体局部最优点和群体最优点的方向, 向着最优解方向进化, 大大提高了收敛进化速度, 从而得到解决雷达优化部署的新算法。
3.2 实现步骤
本文设计的遗传粒子群算法, 通过对初始化群体、交叉配对、基因突变、粒子进化移动运算的扩充修改, 完成全局搜索强和局部收敛快的统一。
1) 初始化种群数量为sum=100, 把实际问题转化为实数编码, 每一个粒子包含实际问题d维变量初始群体变量值和相应速度随机产生, 建立个体适应度与目标函数对应关系。这里采用随机方法得到个体粒子初始坐标和相应的速度, 建立个体适应度函数, 即为3部雷达在高度j获得的覆盖区域面积) , 求取个体适应度fi, 保存个体最优点pid和群体最优点pgd, 设定最大移动速度Vmax=30。
2) 进行遗传算子进化运算:
交叉配对运算:交叉概率设为Pc=0.6, 经实验分析二进制编码的交叉运算可以得到两交叉染色体表示数值 (low, high) 范围之内的数, 例如 (11011, 10001) 取其中第2位交叉得到 (10011, 11001) , 即为 (27, 17) 得到 (19, 25) , 则实数编码以此得到交叉运算后的数值。
基因突变运算:变异概率设为Pm=0.05, 经实验分析二进制编码变异运算范围小于最大编码范围, 即100以内二进制编码取7位, 选 (1000001) 第一位由1变0, 变化范围由65变1, 小于该变量取值范围 (针对100进行二进制编码) , 这里便设定变异后取值为其间任意数字, 更加大了遗传变异性。
3) 进行粒子群算法进化运算:每一代个体的进化以个体最优点pid和群体最优点pgd为依据, 进化方程描述为:
其中, 下标d表示粒子的第d维, i表示第i个粒子, k表示第k次迭代, w为惯性权重, c1, c2为加速常数取2, r1、r2是分布在区间 (0, 1) 的随机数, pid和pgd分别为迄今为止个体局部和群体最优点。
对经过遗传运算的粒子求取适应度, 保存个体局部和群体最优值, 每个粒子包含6个坐标变量, 都为一维变量, 经过粒子群智能移动速度进化, 可快速产生新粒子, 每一个粒子都与上一代相应粒子比较, 设运算代数为t, 则设最大移动速度Vmax≤30运动产生新粒子个体 (100个) , 保存新一代产生的100个粒子, 计算并保存个体最优点和群体最优点。
4) 运行500 (Gmax) 代, 保存粒子个体 (100*Gmax) 。
4 实验仿真
实验采用VC6.0编程, 电脑配置cpu2.99G, 512M内存, 统一选取 (100km*100km) 警戒任务区, 假设3部雷达在某一高度探测半径为20km、25km、30km, 分别以最佳适应度和收敛性进行比较。
1) 图1为单独采用遗传算法求解实验结果, 每个变量编码长度取7, 初始群体数量100, 选优概率取0.1, 交叉概率取0.6, 编译概率取0.05, 运行500代:
从第437代最优解坐标: (80, 76) , (73, 25) , (31, 60) , 图1示, 最佳适应度为0.6035。选取500代中10个最优点分析算法收敛性如图所示, 算法收敛性有波动, 在100代附近便取得已很接近全局最优解的局部最优值, 但没有停止搜索, 体现了较好的全局搜索能力, 但在取得最优值后又出现下滑趋势, 存在丢失最优解现象。
2) 图2为单独采用。粒子群算法实验结果, 初始群体数量为100, 最大速度取30, 运行500代:
从第278代得到最优解坐标: (80.526031, 73.527931) , (26.491432, 68.500107) , (67.381386, 28.696005) , 如图2所示, 最佳适应度为0.6013。选取500代中10个最优点分析算法收敛性, 如图4所示, 算法由于采用实数编码, 坐标准确性较高, 但全局最优点不及遗传算法, 由于收敛速度过快, 容易陷入局部收敛。
3) 图3为遗传粒子群算法实验结果:
从第71代得到最优解坐标: (78.524567, 21.524311) , (26.506573, 33.496101) , (67.372490, 70.409256) , 如图3所示, 最佳适应度为0.604352。选取500代中10个最优点分析算法收敛性, 算法以最少时间得到全局最优点。事实证明GAPSO算法继承了2个算法的优点, 遗传算法提供了全局搜索的框架, 粒子群则修正了遗传算法随机性太强的问题, 从而实现了高效收敛性, 又通过扩展种群保存的数量及最优点记录, 使算法始终朝着目标函数方向进行, 弥补了遗传算法丢解的过失。
5 结论
遗传粒子群算法体现的高效收敛、高精度、低复杂度的特点, 对现代优化方法之间的整合互补提供了有效的证明。区域防空雷达组网是一个系统工程, 本文的实验探索简化了雷达在不同环境及空袭威胁背景下的性能, 通过对3雷达组网在某一高度理想情况下, 设计使用遗传粒子群算法得到较好的验证, 对下一步丰富雷达网数学模型和面对更大规模雷达组网及更多复杂情况都有很大的参考意义。
摘要：综合吸取遗传算法全局搜索能力强和粒子群算法局部收敛速度快的优点, 应用于雷达网部署变量的求解, 仿真结果证明它能在更短时间周期内得到全局最优化的雷达布站方案。
关键词：雷达组网,优化部署,遗传粒子群算法
参考文献
[1]邢文训, 谢金星.现代优化计算方法 (第二版) [M].2005.
[2]杨仕明, 柯炳清.基于遗传算法的区域雷达网优化布站方法[J].2005.
[3]刘以安, 孟献海.粒群算法在雷达优化组网中的应用研究[J].2007.
[4]Kevin J.Binkley.Masafumi Hagiwara.Particle Swarm Optimization with area of influence:increasing the effectiveness of the swarm.Swarm Intelligence Sympo-sium.SIS2005.Proceedings2005IEEE June8-10, Pages (s) :45-52.
组网算法 篇7
电力线通信(Power Line Communication,PLC)技术是指利用现有工频电力线作为信号传输介质,以载波形式进行数据传送的一种通信方式。
由于电力线信道噪声干扰[1]、阻抗不匹配[2]等原因导致现有电力线通信系统的可靠性较低。若能提高系统的通信质量,将对电网、电信网、计算机网与有线电视网的四网合一技术的发展[3]和智能电网的普及[4]具有重要意义。
对于提高电力线通信可靠性的研究,目前有明显通信效果改善的技术来自物理层和网络层协议的研究。物理层技术中,基于BFSK、扩频通信[5]、OFDM[6]的电力线载波通信技术能部分解决电力线信道背景噪声问题;而对于低压电力线网络自适应性、时变性等特点一般使用网络层组网算法解决。
目前常用的低压电力线通信组网算法分为以蚁群算法为代表的智能算法和以分簇算法为代表的层次结构算法两类。其中蚁群算法已有不少研究成果,文献[7,8]仿真了小节点数情况下电力线网络组网蚁群算法,文献[9,10,11,12,13]基于电力线信道各方面特点改进了蚁群算法中的评价函数。这类智能算法自适应性较好,但网络搜索具有盲目性,同时需要专用交互协议协调节点间通信,因此占用了大量带宽,系统时效性较低,不太适应时效性要求较高的低压窄带电力线网络。相比之下,分簇算法中的非交叠分簇算法直接通过广播组网,无需迭代,时效性较高。文献[14]仿真了非交叠分簇算法,但组网结果拥有较多优化空间;在此基础上,文献[15]在节点相关度,即每个节点到中心节点跳数方面进行优化;文献[16]在父节点流量平衡方面有更多考虑;文献[17]提出从信噪比距离方面进行重组,优化节点到上一级节点路径选择以得到更好的组网结果。
上述算法通过算法层面仿真,理论上对组网结果有一定优化,但较少考虑实际组网过程中的实时数据流信息和组网所需时间。本文在此基础上,以信道强度距离为优化目标,建立时分复用信道模型和相应中心节点、子节点模型,仿真实时数据流信息,并利用路由信息提出了一种优化的最短路径分簇算法(Nearest Path Cluster-based Dynamic Routing Algorithm),能在组网时间和网络性能方面取得较好的平衡。
1 低压电力线网络特点及算法建模
1.1 信道特点分析及设计需求
低压电力线网络从物理结构上看基本是一个基于星型和树型的混合拓扑结构[18],典型的低压电力线通信系统结构如图1所示,其中数据集中器设置在变压器位置,通过电力线分支与用户子节点形成物理上的连接。由于终端节点发射功耗限制,节点通信距离有限,低压电力线通信系统即让中心节点通过中继通信读取所有节点数据组成网络,如图1的中心节点通过节点1访问节点2。
由于低压电力线网络并非为了通信而铺设,其信道有许多不利于通信的特点:
(1)节点分布随机:不同台区网络拓扑不同,需要组网算法具有自适应性;
(2)信道衰减大:由容性、感性负载和电力线本身组合成的共振电路使得信道有大幅衰减,同时由于终端节点发射功率限制,信号传输距离有限,中心节点需要通过中继方式覆盖所有子节点;
(3)时变性强:大功率设备的接入会在电力线上引入突发噪声,让节点脱离网络,需要组网算法具有网络变化识别能力并自我修复网络。
(4)时效性要求:由于网络通信带宽和时变性限制,组网算法需要有较高的时效性,能快速完成组网。
1.2 组网分析的前提假设
(1)根据文献[19,20]估算,设定网络中有1个中心节点(编号0)和200个子节点(编号1~200);
(2)节点能检测信号强度并适度量化,信号强度越大,节点间逻辑距离越小,当距离大于一定数量级时通信失效;
(3)根据文献[2]可设定一个节点能与周边10~20个节点通信,一个台区可换算为160×160范围内随机分布的200个子节点,节点间有效通信距离小于25;
(4)物理上所有节点共享并独占信道;
(5)系统采用主从半双工通信方式;
(6)组网过程中网络信道质量不变。
1.3 Matlab网络模型
为了找到兼顾网络性能和组网时效性的算法,本文从实时数据流信息着手,建立了信道网络层数据流模型和帧格式以分析组网实时数据流信息。
1.3.1 帧结构及分类
为了让节点帧数据具有路由功能,定义了如图2所示的帧格式,各数据段功能见表1。
1.3.2 时分复用机制
网络采用时分复用信道接入机制,节点轮流占用时间片Tslice发送数据,当某个节点占用信道时,其他节点处于侦听数据状态,所有节点轮询一次称为一个通信周期Tcycle,如图3所示。
由于帧数据中有当前发送帧节点编号,可据此知道当前发送数据时间片,并逐渐同步到所有节点。
1.3.3 信道网络仿真机制
实际上各节点并不知道自己到其他节点的距离,为了模拟信号在信道上的衰减,信道模型会告知当前正从信道上接收数据节点,离发送数据节点间的距离。若大于有效通信距离25,接收数据节点认为此数据无效。
同时Matlab是串行执行仿真程序,为了模拟各节点并行收发情况,信道模型在每个节点发送数据后更新其他节点接收数据信息,实现宏观上的并行。
通过设计上述Matlab模型,即可仿真网络实时数据流信息和组网时间。
2 分簇算法分析与改进
2.1 非交叠分簇算法
非交叠分簇算法[21]思想及组网流程如下:
(1)中心节点(0)广播组网帧,节点1,2,3收到有效信息并回馈给中心节点,加入第一层网络;
(2)节点1,2,3分别转发组网消息,节点4加入节点1的分簇,节点5,6加入节点2的分簇,节点6虽然能收到节点3的消息,但因为已经加入节点2的分簇,故不再回复节点3,第二层网络完成;
(3)循环上一步,最终得到如图4所示的网络结构。
文献[14]分析了此算法的组网结果,本文为了仿真组网过程中的数据流信息和组网时间,在其基础上建立了如图5,图6所示的非交叠分簇组网算法节点状态机模型,其中中心节点包括5个状态,子节点包括6个状态。将节点模型挂载到第1.3.2节所述时分复用网络模型中进行仿真,得到如图7所示的200个节点的组网结果。
这里以3个比较重要的指标来评估网络性能:
(1)组网通信周期(Networking Cycle):节点数相同时完成组网所需通信周期,周期越少组网越快;
(2)平均通信长度(Average Length):中心节点到所有子节点信号强度距离的平均值。因为信道噪声影响表现为节点的随机移动,此长度越小,节点信号强度越大,抗干扰性越强;
(3)平均通信跳数(Average Jump):中心节点到所有子节点通信跳数的平均值。跳数越少,数据中继次数越少,通信实时性越高。
在图7测试中,组网经历139个通信周期,平均通信长度为92.17,平均跳数为4.86。
在上述非交叠分簇算法中,子节点由于不知道周围节点的位置信息,组网结果受节点位置分布和发送帧的顺序影响,具有一定随机性,从图7中可以看到,很多路由路径还有优化空间。
2.2 基于信噪比的分簇算法
文献[17]提出基于信噪比距离来优化节点到上一级父节点路径,其思想是先以文献[14]的非交叠分簇算法实现组网,再让每一层子节点分别寻找上一层所有节点到中心节点距离最小的节点作为新路径进行优化,优化结果如图8所示。
可以看到,该算法对组网结果有明显优化,但分析其组网过程发现仍有不足:
(1)每一层子节点优化目标在上一层节点中选择,因而优化过程不会减少子节点到中心节点的中继跳数。在某些情况下(例如图9),跨层级优化能进一步减少距离。
(2)优化网络时,子节点本身并不知道上一层所有节点的路由信息,要得到此信息只能在完成初次组网后,中心节点将完整的路由信息广播给所有子节点,并且每完成一层节点的优化后就要将新路径广播给所有子节点,让下一级子节点在选择父节点时知道最新的路由信息。此过程需要较复杂的节点间通信协议来实现,使子节点状态机变得比较复杂,同时节点间多次互相沟通会占用大量组网时间。
2.3 最短路径分簇算法
上述算法提出利用路径距离优化父节点选择是一个比较好的思路,不足在于子节点难以获取上一层网络信息。通过上文使用数据流信道模型进行分析可以发现,子节点要获取周围节点路由信息比较容易,只需对信道进行一段时间侦听即可。基于侦听-择优的思想,本文提出了可跨层级优化、节点间交互简单的最短路径分簇算法。
在时分复用信道接入机制下,节点轮流占用时间片发送帧数据,如图9所示,以4个子节点组网为例进行分析。时间片0,中心节点发送组网帧被节点1侦听到;时间片1,节点1转发组网帧被节点2侦听到;时间片2,节点2转发组网帧被节点3侦听到;到了时间片3,节点3并不知道还有节点4的存在,因此以节点2为父节点转发组网帧,经过节点2,节点1回送到中心节点进行组网,最终选择路径0→1→2→3。
最短路径分簇算法提出,节点3在侦听到节点2的帧信息后,到第3时间片时并不急于选择路径发送组网回复帧,而是继续侦听一个通信周期,由于所有节点在转发组网帧时会在帧的数据段加入自己到中心节点的路径,如此节点3即可了解周围节点路由信息。到时间片4,节点3侦听到节点4发送的更优的路径信息,当再次循环到第3时间片时,节点3再发送以节点4为父节点的最短路径0→4→3回复组网帧。
最短路径分簇算法的节点状态机模型见图10。
使用改进的分簇算法对图7的网络节点分布进行组网,仿真可得如图11所示的组网结果。
可以看到,在相同环境情况下,相比文献[14]的非交叠分簇算法,组网周期从139减少为30,平均通信长度从92.17减少为64.51,平均跳数从4.86减少为3.54。
接下来,本文针对160×160的200个节点的随机分布情况又做了50次测试,分别比较文献[14]非交叠分簇算法、文献[17]基于信噪比距离的路由重组分簇算法和本文的最短路径分簇算法。从表2的比较结果可以看到,本文算法较非交叠分簇算法有明显优化,同时由于对网络进行了跨层级优化,组网结果也优于信噪比重组的分簇算法(由于信噪比重组算法的交互协议比较复杂,本文并未对其节点进行建模,无法仿真组网周期,只能从算法层面仿真组网结构)。
为了测试算法对网络不同节点数量的自适应性,本文分别测试了不同算法在50,100,200,500,1 000节点情况下的组网时间(见图12)、平均通信长度(见图13)、平均跳数(见图14)的性能对比,测试环境见表3。
可以看到,随着节点数目的增加,改进效果更明显。
3 结论
本文提出了一种基于信号强度距离的低压电力线网络通信组网算法,能在组网时效性和组网性能方面取得较好平衡。为了提高算法的时效性,建立了电力线网络层数据流模型,可以分析实时数据流信息;在此基础上,以现有分簇算法为基础,改进了子节点选择到中心节点路径的算法,让子节点侦听一个通信周期再选择到中心节点信号强度距离最短的节点作为父节点。通过不同节点数网络环境测试,结果表明,改进的最短路径分簇算法对组网结果有一定提升,同时,每层节点在组网时即选择了距离最短路径,优化了中继跳数,因此组网时效性得到明显提升。
算法对大节点数网络情况有较好的包容性,但算法分析建模基于时分复用信道分配机制,信道利用率较低,若能对信道接入机制有更多研究,将对算法改进有更多帮助。
摘要：为了满足低压电力线网络的自适应性、时效性需求,在分析了电力线网络信道特点及拓扑结构后,指出了侦听一个时间片循环以优选最短路径的思路,提出了一套基于时分复用信道接入机制的自适应组网算法,给出了算法网络层协议及对应状态机,并使用Matlab建立了一系列仿真模拟机制及节点模型,以仿真电力线网络上实时数据流信息和组网结果。仿真结果表明,相比近年来的分簇算法,该算法在组网时间、平均通信长度和平均通信跳数方面都有明显优化,能在组网时效性和网络性能方面取得平衡。
组网算法 篇8
低压配电网由于其具有分布广、用户数量多等特点,使其在节约资源、方便用户、减少安装费、实现多媒体通信等方面被广泛关注。但由于低压配电网电气负载环境的复杂性和介质环境的共享性、开放性和多样性的影响,造成通信可靠性低,使目前电力线载波通信的广泛应用受到限制和普遍质疑。针对建立网络中继提高电力线通信可靠性的方法,国内外的研究人员进行了一定的研究。其中,文献[1-2]提出基于蚁群算法的电力线载波通信组网方法在一定程度上解决了电力线载波通信网络的通信可靠性问题。笔者对蜘蛛织网的行为、圆形蛛网的结构特性、猎物在蛛网上信息传递机理等方面进行大量的研究[3],同时借鉴前人的相关研究成果[4,5,6,7,8,9,10,11,12,13,14,15,16,17,18],提出了基于人工蛛网通信模型,并将低压配电网的主要负责通信协议部分(Media Access Control,MAC)层网络转化成由多个人工蛛网组成的逻辑拓扑,制定了一种新的自动路由协议,建立了人工蛛网仿真模型,验证了该种新型网络结构及路由协议的优越性,试图为研究适合电力线载波通信网络的路由模式,提高电力线通信的可靠性,提供一条新的思路。
1 新型网络模型
1.1 人工蛛网拓扑
蜘蛛经过了约18亿年的进化,现在的蜘蛛网不仅具有优雅、超轻的结构,而且具有超级弹性和抗张强度,可以抵抗各种大风、昆虫等的冲击。即使有几个网格单元遭到破坏,它仍能作为网来捕获猎物,具有极强的抗毁能力。针对蜘蛛网的结构特点、蜘蛛的捕食机理以及人工蜘蛛网通信拓扑的构建等方面问题,文献[3]中已进行了详尽的阐述,并建立了双层六边形人工蛛网逻辑拓扑模型。本文以单层六边形人工蛛网为通信子网模型进行组网,并进行了相应的分析与仿真。
1.1.1 人工蛛网逻辑拓扑模型
电力线载波通信的时变性、频率选择性和强干扰性等特点,使电力线通信的组网方式具有其独特的特点,如,网络物理拓扑和逻辑拓扑具有时变性,没有专用的交换机和中继器,通信媒质共享信道,弱数据处理能力,一对多通信等。为保证一定的通信距离/组网规模,电力线通信组网通常需要通过路由器/中继器将同一个物理子网划分成多个逻辑子网。低压电力线通信网络是由星形网络和树形网络组成的混合网络。从物理层看,图1所示的单层人工蛛网除具有多个星形网络(如v1,v2,vh,v4,v5)和树形网络(如v1,vh,v3,v2,v4)外,还具有自己独特的环形网络(如v1,v2,v3,v4,,vm);从数据链路层角度,人工蛛网的结构是一对多、多对一的这种通信方式,与低压配电网的总线型逻辑拓扑相吻合,所以,不论从物理层还是数据链路层,人工蛛网结构都能作为低压配电网的组网结构。
1.1.2 人工蛛网数学模型
为了能更清楚地阐释人工蛛网的结构特征和建立新型路由模型,且为进一步研究蛛网提供理论基础,本文定义了人工蛛网的主要特征参数如下。
(1)Nr为围绕中心节点vh的蛛网层数,即同心圆层数。该参数反映人工蛛网的复杂度,同时也决定人工通信蛛网所覆盖的通信范围,本文中取值为1。
(2)Ns为中心节点vh与周边节点iv(i=,1,m)相连的蛛网轮辐数,即中心节点与相邻周边节点通信路径数量。
(3)Nn为人工蛛网总节点数,与Nr,Ns的关系如式(1)所示。
(4)Dw为蛛网直径,直接反映蛛网所覆盖的物理范围。
(5)Hm为网眼高度,是同一径向上相邻两层节点之间的距离。该参数反映网络的密度,与wD,Nr的关系如式(2)所示。
(6)Δθ为蛛网扇区角,即相邻两径向路径的夹角。
这样,蛛网中任一节点的位置可由式(4)所示的极坐标方程来表示。
其中:ri=i×Hm,i=0,1,,Nr,为径向方向上的路径长度;θk=k⋅Δθ,k=0,1,,Ns-1,为径向路径与水平线的夹角。这些只是网络的逻辑关系,因此式(2),式(3)可以标准化为式(5)、式(6)。
则式(4)可以简化为式(7)。
1.2 PLC网络的人工蛛网结构
在PLC系统中,下行方向定义为信息由基站传输到所有的用户终端,每个终端可以直接或通过中继间接收到下行信息;上行方向定义为用户终端传送信息给基站。上行方向的信息不仅可以被基站接收,也可以被其他用户终端接收。所以,从MAC层角度,PLC网络是一个树形物理拓扑下的总线型逻辑结构[19],如图2所示。其中BS(Base Station)为基站,负责网络内所有节点的数据采集及组网等。近、中、远的定义是根据收到BS广播信息的节点与BS的距离定义的,如BS一次广播后,收到该广播的节点定义为“近”,收不到该广播,且需要以“近”节点为中继与BS通信的节点定义为“中”、“远”节点是以“中”、“近”的节点为中继与BS通信的节点。基于网络的此种结构特点,本文建立这种基于蛛网结构的PLC组网模型。
低压配电网三相之间的衰减较大,在没有相间耦合器的情况下,低压配电网三相之间可以看作并列且相对独立的逻辑关系,因此可将其中某一相的逻辑拓扑作为重点研究对象。由于电力线通信数据传输距离有限,在实际应用中,某一相内可能只有离基站物理距离近的用户终端能与该相基站可靠通信。假设某相网络内用户节点总数为n,基站一次广播后有m(1≤m≤n)个节点能与之可靠通信,剩下n-m个用户节点虽然物理链路是连通的,但由于信号随传输距离的衰减等原因,不能与基站通信。为了解决这个问题,本文提出了基于单层蛛网的组网模型。
在m个能与基站可靠通信的节点中,假设相邻两节点间是可靠通信的,m个节点组成图1所示的m-1边蛛网结构,相邻节点之间能可靠通信,不相邻节点可通过节点h为中继进行通信。节点v1,v2,,vm代表用户终端节点。假定节点vh位于逻辑子网的中心(vh为v1~vm中的一个,1≤h≤m),其与所有周边节点均能可靠通信,功能与基站类似,负责收集其所在蛛网周边各节点的数据,维护子网内的路由以及与其他子网的中心节点通信。同时,由此节点发起对剩下的n-m个用户节点的组网广播。由于节点vh较基站与其余n-m个节点物理上的相近性,所以当vh继续发起组网广播后,有新的节点收到vh的组网广播,这些新的节点构成新的人工蛛网子网。然后,新的子网选取中心节点vm+1,确定子网节点数目,由vm+1与上一子网的中心节点vm+1保持数据通信,同时,进行新一次的组网广播,会有新的节点收到该广播。依次类推,最终该网络内的所有节点组成了多个类似的人工蛛网。如图3所示,离基站节点“近”的蛛网的中心节点(例如h),可以直接与基站通信,处在“中间”位置的蛛网的中心节点需要以“近”的中心节点为中继与基站通信,同样,处在“较远”位置的蛛网的中心节点,是以“中间”、“近”的中心节点为中继与基站通信。基站只要确保每个子网的中心节点能与之可靠通信即可,这样在一定程度上提高单相基站采集数据的效率,降低了网络节点的数量,降低了数据冲突率。
2 电力线通信人工蛛网路由
2.1 人工蛛网组网算法
2.1.1 子网中心点选取算法
研究电力线通信组网可以将低压配电网抽象为图G(V,E),记为G(V(G),E(G))。如图1所示,其中,V(G)为图G的节点集,元素v∈V称为图G的一个顶点或节点,E(G)是V中节点组成的无序对的集合,称为边集。图G每条边的权值vivj,代表任意两个终端节点间的通信距离。这里“通信距离”是指网络内可以直接通信的两个节点所跨过的节点个数,相邻两个节点的通信距离为1。通过Dijkstra算法[20]求出图G中所有顶点间的最短通信距离,并组成距离矩阵D,其元素vivj是图G中顶点vi与顶点vj间的距离,i,j=1,2,,m。
给图G的所有顶点赋权值T(v),代表各终端节点在一定时间段内产生的数据量。对j=1,2,,m,给矩阵D的第j行乘以T(v j),并求所得矩阵的行和。
比较所有行和f(g(v i)),根据Dijkstra算法,其中最大者所在的行对应的顶点即为子网的中心点,故对于某个子网选取中心节点的优化目标函数可表示为式(11)。
2.1.2 组网算法
人工蛛网组网算法如下:
(1)组网开始,由基站节点发送组网广播,在收到该广播的m(1≤m≤n)个节点中,通过中心节点选择算法选择其中一个用户终端节点为第一个蛛网的中心节点h,由节点h对剩下的m-1个节点分配逻辑ID,直到所有m个节点均获得逻辑ID为止。
(2)第一个人工蛛网组网完成后,基站向节点h发送指令,由节点h再次发送组网广播,设有k(m≤k≤n)节点收到节点h的广播,剔除掉已经获得逻辑ID的m个节点,在剩下的k-m个节点中选择一个与节点h可靠通信的终端节点为第二个人工蛛网的中心节点l,重复步骤(1),直到所有k-m个节点均获得逻辑ID。
(3)基站以节点h为中继给节点l发送指令,由节点l发送组网广播,重复步骤(1),假设第二个蛛网已经将剩下的所有n-m个节点连通,此时节点l会得到空响应,并把该响应通过节点h传回基站,至此,组网结束。形成了以节点h为中继节点的m-1边蛛网逻辑通信拓扑和以节点l为中心的n-m-1边蛛网逻辑通信拓扑,这样就建立了基站到该单相网络内所有节点的通信路由。
2.2 自动路由协议
假设某单相网络组网完成后由三个蛛网子网组成,路由协议利用这三个子网进行数据包的发送、接收。数据包格式如图4(a)所示,包括帧头、数据源地址、目的地址、子网中心节点地址、节点层数,分层标志位、节点数据及帧尾。其中,帧头、帧尾用于区分数据帧的起始和结束;数据源地址为源节点的地址标识,为基站,各子网中心节点地址;目的地址为目的节点的地址标识,本文均设置为基站地址;子网中心节点地址为各个子网的中心节点地址标识,是各周边节点发送数据的目的地址;节点层数为网络内组成的子网个数,与分层标志位作比较;分层标志位用于判定节点所在子网及数据包来源,同时,防止发送到基站的数据包被反复广播,提高数据处理效率。数据传输流程图如图4(b)所示。数据传输开始,设置所有节点的初始化节点层数为3,分层标志位为0,基站地址为0。数据传输开始,基站广播分层标志位为0的数据包,只有子网1内的节点收到数据包,判断数据源地址是否等于基站地址,如果是基站地址,则创建新的数据包,包括选取中心节点地址,数据源地址设置为该子网的中心节点地址,目的地址设为基站地址,分层标志位设置为1,节点层数与分层标志位相等,添加节点数据。子网1的周边节点将数据包发给中心节点,中心节点处理完所有数据包后,将其发送至基站节点。基站收到来自子网1的数据包后,进行记录。然后,子网1的中心节点广播请求数据包,这个数据包会被子网1内的周边节点、子网2的所有节点收到。子网1内的节点收到数据包后,判断数据包节点层数与分层标志位是否相等,相等则结束传输。子网2的节点收到子网1的中心节点广播数据包后,首先判断数据源地址是否为基站地址,如果不是,再判断节点层数大于分层标志位,子网2内的所有节点创建新的数据包,与子网1创建数据包过程一致,数据包的节点层数与分层标志位相等,设置为2。子网2的中心节点处理完周边节点数据后将其发送至子网1的中心节点,子网1的中心节点比较本节点数据包的节点层数小于收到数据包的分层标志位,则将该数据包发送至基站,至此完成子网2的数据与基站之间的通信。然后,子网2的中心节点广播请求数据包,被子网1,子网3的节点收到,子网1的周边节点收到该广播数据包,结束程序,中心节点收到该数据包将其发送至基站。子网3的节点判断收到数据包的节点层数大于分层标志位,创建数据包。节点层数与分层标志位相等,设置为3。子网3的中心节点处理来自周边节点的数据后,以子网2,子网1的中心节点为中继节点,将数据发送到基站,至此完成所有节点与基站的通信。子网1到子网3的网络内数据采集以及数据广播是依次进行的,例如,子网1数据采集完成后,将数据发给基站,中心节点h向子网2的中心节点发送广播,子网2开始数据采集与发送,依次类推。同一时间段内,只有一个子网占用信道,进行数据采集与传输,在一定意义上减少了节点数量。
利用三层网络进行数据包的产生,发送过程如图5所示。在每一层子网中都创建新数据包,其中源地址设置为其所在子网的上一层子网的中心节点/基站地址,目的地址均为基站地址,子网的中心节点把数据发送到上一级子网的中心节点/基站,同时对下一层网络进行数据广播。这种将大型网络分割成若干小型子网的数据传输方式在理论上有利于降低总线型信道的数据冲突率,提高信道的利用率和系统的效率。
2.3 终端节点建模
在本文中,不考虑用户终端节点的物理故障造成的通信失败。假设在信道环境良好的情况下,每个用户终端均工作良好,只有信道环境的改变,造成用户终端节点的工作状态的改变。因此,可以应用两状态马尔科夫模型来表征由于信道环境改变造成的用户终端节点通信状态的变化情况[21],仿真观察故障节点对系统的影响。如图6所示,“良好”“故障”表示用户终端节点的两种工作状态。“良好”代表终端节点可以与其所在子网的中心节点直接通信,“故障”代表终端节点不能与其所在的子网中心节点通信。本文假设,在一个数据采集周期内,节点的工作状态是不变的。在一个采集周期结束后,由于信道状况的改变,“良好”“故障”两种状态才发生改变。Pg和Pb分别定义为节点在一定信道状况下处于“良好”和“故障”状态的概率,Pgg和Pgb分别定义为一个数据收集周期后,“良好”状态的节点仍处于“良好”状态或是变成“故障”状态的概率,Pbb和Pbg也是类似的定义。式(12)~式(15)为状态变换的数学表达式。
3 仿真与试验研究
3.1 仿真环境
本文根据实际低压配电网的配电环境,在半径50 m范围内分布14个用户终端和一个基站节点,以PC机为仿真硬件平台,以Opnet14.5为编译和仿真环境。在不考虑数据处理延时的情况下,具有2个子网的网络结构就可以表示路由协议的有效性。假设在仿真时间内所有节点组成的两个6边形蛛网结构不发生改变,并依据式(11)确定每个子网的中心节点。由于中心节点到每个周边节点的“距离”都为1,则此处的中心节点为与各个周边节点通信流量最大的节点。图7所示为组网完成后的网络拓扑,subnet_0代表基站节点,subnet_1_0和subnet_2_0为各自子网的中心节点,其他节点为终端节点,信道传输速率为1 000 bps,每个数据包大小为24 bits。对采用新的蛛网路由协议后的信道数据冲突率,吞吐量,信道利用率等参数与采用CSMA协议下的相关参数进行仿真对比分析。本文设定一个数据采集周期为600 s,所有的仿真时间设定为3 000 s,即5个数据采集周期。
3.2 试验结果分析
从马尔科夫模型两状态表达式(12)~式(15),可以明显看出在Pg,Pb,Pgg,Pgb,Pbb,Pbg六个变量中,只有Pg和Pgb为独立变量,其他参数均可由这两个参数来表达。因此,分析这两个变量来观察新型重路由算法的时间特性和工作效率。由式(15)可知Pgb=(Pb Pg)·Pbg,由于0
图9所示为gP=0.9情况下的信道状态仿真结果。图9(a)为两种协议的吞吐量仿真结果,图9(b)为与之相对应的链路利用率的仿真结果。从仿真结果中可以得出,CSMA协议下的信道数据冲突率比较高,信道吞吐量及利用率均比较低,相同条件下,CWRP协议由于数据冲突率很低,信道的吞吐量与利用率均有大幅提高,这对电力线通信的上层应用,保证服务质量是非常重要的。
4 结论
(1)本文从提高低压配电网通信可靠性角度出发,提出了基于人工蛛网的电力线通信组网拓扑,并建立了相应的蛛网数学模型,为以后针对蛛网模型的相关研究提供理论基础。
(2)建立基于蛛网的组网结构,针对该结构,首次提出中心节点选取算法,详细叙述组网过程,建立新的自动路由协议,理论分析表明该路由协议在降低数据冲突率,提高信道吞吐量,信道利用率方面有很大优势。以两状态马尔科夫模型表征通信节点,具有代表性。
(3)与CSMA协议在数据冲突率,信道吞吐量,利用率方面进行仿真对比结果显示,新的CWRP协议在以上方面表现均大幅度优于CSMA协议,证明了理论分析的正确性,以及CWRP协议的优越性,在提高通信可靠性方面具有一定的意义。
摘要：针对低压电力线载波通信可靠性低的问题,提出了人工蛛网通信网络模型,并建立了相应的数学模型。将三相配电网的MAC层转化成由多个人工蛛网组成的逻辑拓扑。详细叙述了组网过程,提出了中心节点选取算法,制定了自动路由协议。以两状态马尔科夫模型表征用户终端的工作状态,模拟实际中由于信道变化产生的终端节点通信失效。针对数据冲突率、通信流量、链路利用率等方面进行建模仿真对比实验,仿真结果表明新的组网方式及路由协议在提高电力线载波通信可靠性方面具有较大优势。
组网算法 篇9
目前除了蒙特卡罗定位算法, 几乎没有专门为动态传感器网络设计的定位算法。在绝大多数文献中, 为了支持动态传感器网络的定位, 仅仅提出了将静态环境下适用的定位算法每间隔一段时间执行一次从而实现对动态节点的定位。在很多情况下, 因为该方法会使那些需要依靠来自较远处的节点的信息的定位算法遭受到非常严重的数据延迟的限制, 很有可能当远处节点所需的信息到达它时, 整个网络的结构以及拓扑都发生了变化, 这样节点的定位将失去精确性。因此, 上述方法并不适用于动态环境下的传感器网络定位。分析发现, 上述方法不适用于动态环境的主要原因并不是信息的稀缺或是算法本身的不精确, 而是由于定位算法收集信息的方式, 导致了定位算法的可靠性大大降低。为了提高定位算法的精确度和可靠性, 本文基于蒙特卡罗方法提出一种序列蒙特卡罗定位方法, 解决了在动态环境情况下传感器网络节点的定位问题。
二、序列蒙特卡罗算法原理
由于传感器节点以及定位精度的原因, 使得移动无线自组网中的定位比机器人定位难得多。但是, 使用这种定位方法, 在网络中节点间可以通过合作来共享位置信息来实现定位。
将时间分成离散的时间片, 因为节点都在相对于之前的位置移动, 所以在每个时间单元内都需要对节点进行重新定位。想要得到节点可能位置的概率分布, 从而协助定位。因为节点在网络中持续运动, 之前的位置信息对目前的位置来讲将会越来越无用。从另一方面来说, 可以根据从锚节点新收到的观察信息滤除不正确的估计位置估计。在移动并接收了观察信息之后, 节点之前可能位置的概率分布就更难确定了。除了一些特殊的情况 (线性高斯状态模型卡尔曼滤波器) , 想要用数值法解出之前的分布几乎是不可能的。
序列蒙特卡罗法提供了一种基于仿真的方法用于估计之前的非线性离散时间动态模型的位置分布。序列蒙特卡罗法的核心思想就是通过一系列, N个带有权重的采样, 使用“重要性采样” (importance sampling) 法, 递归的对这N个带有权重的采样进行更新。序列蒙特卡罗定位法已经成功地应用在目标跟踪, 机器人定位与计算图形学中。
三、基于测距的序列蒙特卡罗定位算法
序列蒙特卡罗方法虽然相对于其它现有的定位算法更适于动态传感器网络, 但是这种算法仍然存在定位精度较低的不足。针对这个问题, 这部分基于序列蒙特卡罗算法, 提出一种基于测距的蒙特卡罗定位算法, 解决了动态传感器网络定位精度较低的问题。
基于以上的序列蒙特卡罗定位算法, 再考虑到无线自组网节点相对于传感器节点存在着能够携带更多电能, 机能相对强大等优势, 在节点上加装测距模块的可行也相对更高, 本文提出一种基于测距的序列蒙特卡罗算法, 算法与传统序列蒙特卡罗算法类似, 但由于位置生成步骤相对简单了许多, 于是与前一步骤合并, 故步骤分为三步:
⑴位置预测:根据滤波后的位置估计, 对下一步可能位置进行预测, 在N个估计点周围以本步估计位置为圆心, v为半径的圆形区域内生成N个预测点。
⑵收取观测信息:由于是基于测距的定位算法, 故未知节点可直接测得在自身测距半径d内的锚节点到自己的距离r, 并将此距离保存。
⑶位置滤波与位置生成:根据以上观察信息, 将不可能的位置估计从估计矩阵中删除, 删除后根据观测信息将删除的估计点数与预测点数补齐, 假设r为测得距离, e为测距误差, 删除与预测策略如下:
Ⅰ.若在自身测距半径d内只有一个锚节点, 则将预测中不在以该锚节点为圆心, r为半径, e为测距误差的圆环上的预测点及下步位置估计删除, 并在该圆环中随机生成本步估计点坐标, 并根据运动模型预测下步坐标。
Ⅱ.若在自身测距半径d内有两个锚节点, 则根据两圆相交关系可求出该未知节点的两个可能存在的位置, 将位置预测中不在以这两个位置为圆心, 测距误差为半径的小圆外的预测点及下步位置估计删除, 并在这两个小圆内生成位置估计点坐标, 并根据运动模型预测下步坐标。
Ⅲ.若在自身测距半径d内有两个以上锚节点, 根据多圆相交关系, 可以确定出未知节点的位置, 再将以该位置为圆心, 测距误差为半径的小圆外的预测点及下步位置估计删除, 并在此小圆内生成位置估计点坐标, 并根据运动模型预测下步坐标。
Ⅳ.若没有任何消息, 则不删除位置估计与位置预测。
四、基于测距的序列蒙特卡罗定位算法仿真分析
在仿真环境中, 节点被随机的撒在一个250m x 250m的矩形区域, 我们给节点设定一个固定的通信半径r, 锚节点与未知节点的通信半径r都等于25m, 节点采用自由随机运动模型, 可以变化的各项参数如下:
⑴锚节点与未知节点最大速度v:每个节点的速度都服从[0, v]的均匀分布
⑵未知节点密度:在1倍通信半径范围内的平均未知节点数。可以用下式计算:
其中, nm为整个部署区域的所有未知节点数, Total Area为部署区域面积
⑶锚节点密度:在1倍通信半径范围内的平均锚节点个数。可用下式计算:
其中, sm为整个部署区域的所有锚节点数, Total Area为部署区域面积
⑷采样点数 (N) :未知节点对自身位置估计以及下步位置预测的估计个数。
在此引入一个新参数e:测距误差。e=10%的含义为:测距误差是所测距离的10%, 如果所测得距离为d, 那么实际距离介于 (1-e) d之间 (1+e) d。
3.1锚节点密度
当sd=1, nd=10, v=d=25, N=10, e=0时, 如图1所示。
由返回误差数据计算得到, 当锚节点密度为1时, 定位稳定后的平均定位误差约为56.32%。
当sd=2, nd=10, v=d=25, N=10, e=0时, 如图2所示。
由返回误差数据计算得到, 当锚节点密度为2时, 定位稳定后的平均定位误差约为41.21%。
当sd=4, nd=10, v=d=25, N=10, e=0时, 如图3所示。
由返回误差数据计算得到, 当锚节点密度为4时, 定位稳定后的平均定位误差约为13.13%。
由以上一组图可以发现, 在锚节点密度较低, 如sd=1时, 定位精度较差, 结果并不比传统非测距序列蒙特卡罗算法好很多, 但当锚节点密度提高时, 定位精度增加比较明显, 在其他条件不变, sd=4时, 其定位精度13.13%要远好于传统序列蒙特卡罗方法的40%左右, 虽然由于测距模块的引进可能引起网络节点的体积增加以及耗电量增大等结果, 但对于通常情况下的无线自组网节点, 如PDA, 笔记本电脑等来说, 这样的体积增加与耗电量增大一般来说是可以接受的, 故这种定位算法具有较强的实用性。
3.2测量误差
当sd=4, nd=10, v=d=25, N=10, e=0时, 如图4所示。
由返回误差数据计算得到, 当测距误差为0时, 定位稳定后的平均定位误差约为13.13%。
当sd=4, nd=10, v=d=25, N=10, e=5%时, 如图5所示。
由返回误差数据计算得到, 当测距误差为5%时, 定位稳定后的平均定位误差约为24.95%。
当sd=4, nd=10, v=d=25, N=10, e=15%时, 如图6所示。
由返回误差数据计算得到, 当测距误差为15%时, 定位稳定后的平均定位误差约为31.90%。
由以上一组图以及数据可以发现, 测距误差也是影响定位精度的一个重要参数, 当测距误差提高后, 精度下降的比较明显, 原因是很显然的, 如果测距出现误差, 那么之后的对节点位置计算估计等都会出现误差, 由于误差的重叠积累导致了结果的误差, 所以高精度测距模块的选择也是提高定位精度的一个有效方法。
五、结语
本文在传统序列蒙特卡罗定位算法的基础上提出了一种基于测距的序列蒙特卡罗定位算法, 从而在条件相似的情况下, 明显地提高了动态传感器网络节点的定位精度。仿真结果表明, 这部分提出算法的定位精度将远高于序列蒙特卡罗算法, 从而有效解决了动态传感器网络定位精度较低的问题。
摘要：在无线Ad Hoc网络中, 本文提出一种基于测距的序列蒙特卡罗定位算法, 使定位精度大大提高, 对于比传感器节点能够携带更多硬件与电源的无线自组网节点来说, 这种新的定位算法有很强的实用意义。