三维路由算法（共7篇）
三维路由算法 篇1
0 引言
水声传感器网络(UANs)以其部署灵活、成本低廉、覆盖广泛等优势成为人类认知和开发海洋资源的重要手段。水声传感器网络通常由能耗较低、通信距离较短的水下传感器节点、自主式水下航行器(AUV)和海面的汇聚节点组成,它们通过声数据链构成无线通信网络。节点随机或者按照要求布置在目标海洋环境中,获取环境的信息并通过特定的协议自组织起来,相互协同地完成特定任务。
水声传感器网络与陆上无线传感器网络的路由协议有很大的区别。为了采集更完备的信息,水声传感器节点一般布置在水体各个位置,形成一个三维立体的网络,而陆上的无线传感器网络一般为布置在地表的二维网络。针对二维空间的路由协议无法直接应用于三维环境中,因此随着水声传感器网络的兴起,对三维网络路由协议的研究正广泛展开。目前已有的三维无线传感器网络的路由算法可以分为两类:一类是基于实际位置的路由算法,另一类是基于虚拟位置的路由算法[1,2,3]。基于实际位置的路由算法又可以分为树状路由、分簇路由[4,5,6]和分层路由[7]。贪婪路由是树状路由中应用广泛的一种[8],算法选择距离目标节点最近或者夹角最小的邻居节点作为下一跳。贪婪路由存在路由空洞问题,即局部最小节点无法路由。该空洞问题可以通过LAR[9]的局部泛洪、GLS[10]的网格路由以及GPSR[11]的面路由等方式解决。
本文的主要内容是以能量高效和延长网络生存时间为目标,设计一种基于三维水声网络设计的路由算法。首先建立水声信道的能耗模型,并在研究现存路由协议的基础上,探究影响网络能耗的因素,设计合理的能量高效的路由协议。
1 水声信道能耗模型
作为水声传感器网络部署的关键环节,能量消耗直接决定了网络的生存状况。而作为网络能耗的基础,本节主要研究水声信道的能耗模型,并根据衰减模型给出基于WHOI系统的水声信道能耗计算方法,为能量高效的路由设计打下基础。
1.1 水声信道衰减和噪声
对于给定的距离l和频率f,水声信道的衰减系数A定义为[1,2]:
其中,k为扩散因子,a(f)为吸收系数。将衰减系数写成d B的形式得到:
其中,第一项表示扩散损耗,第二项表示吸收损耗。扩散因子k描述了传播的几何构型,一般地,球形传播取2,圆柱形传播取1,实际应用中一般取1.5。根据Thorp的经验公式,在f以k Hz为单位时,吸收系数a(f)可用下式计算,以d B/km为单位:
上式适用于频率在几百赫兹以上时对吸收系数的估计,对于较低的频率,应用下式计算吸收系数[13]:
海洋中的环境噪声可以用四种噪声源建模:湍流噪声,航船噪声,波浪噪声以及热噪声。环境噪声可用服从高斯分布的统计量和连续功率谱密度函数描述。下述经验公式给出了四种成分的连续功率谱密度[14]:
环境噪声的总体的噪声功率谱密度N(f)=Nt(f)+Ns(f)+Nω(f)+Nth(f)。在1k Hz到30k Hz的频率范围内,噪声的功率谱密度对数尺度上近似按线性衰减,可用下式近似估计[13]:
1.2 单跳传输能量消耗
对于有噪声的水声传感器网络,其能耗包括两部分:发送能耗及接收能耗。其中发送能耗由发送功率以及发送信息量和带宽决定,发送功率为:
其中,B(l)为距离为l时的最优带宽,f0(l)为最优频率,N(f0(l))为最优频率下的噪声功率谱密度,A(l,f0(l))为信道衰减系数,SNRtgt为接收端正确接收数据所需的信噪比。本文认为带宽B(l)为窄带,即在带宽范围内,噪声功率谱密度为一常量。
式(7)给出的发送功率为声功率,需转换为电功率计算电池能耗[15]:
其中,ξ为声功率(以d B reμPa为单位)转化为电功率(以Watt为单位)的转换系数,ηel为电子线路的总效率,包括功放和传感器等部件。
与发送功率不同的是,接收功率Pr与传播距离无关,而与接收操作相关,如相干检测和均衡技术等。可以认为Pr为常数。为了简化能耗模型,该模型忽略其他固定并且数量较小的能耗部分如系统耗能等。因此,对于给定SNR,单跳传输总能耗与传播距离相关,为Pr+Ptel,单跳传输时间可用传输信息长度和可用带宽计算:
其中,L为传输信息长度,单位为bit,B(l)为带宽,α为调制器的带宽利用率,单位为bps/Hz。
综上所述,单跳能耗可以用下式计算:
1.3 水声信道最优频率
由式(10)可以看出,对于给定网络和传感器节点,能耗的频率相关部分由衰减系数A(l,f0(l))及噪声功率谱密度N(f0(l))决定。A(l,f0(l))和N(f0(l))越小,单跳传播能耗越小。因此参量AN积可用于研究最优频率与传播距离的关系:
根据式(2),式(3)和式(6)可得出AN积的分贝形式:
为求AN积的最小值,将AN积对频率求导:
求其零点得到的频率即为最优频率:
2 Hybrid Leach路由协议
根据平面无线传感器网络的研究,分簇路由有均衡能量负载的特点,从而其网络生存周期比一般的平面多跳路由更长。文献[4]提出一种新的三维低功耗自适应聚簇分层协议NEW LEACH。该协议改善了LEACH协议中的簇头选举的阈值,将节点剩余能量、能量消耗率和节点位置纳入考量范围内,减小能量较低的节点以及距离sink节点较远的节点成为簇头的概率,进一步均衡了节点能耗。但由于在阈值设置方面引入了位置信息,势必造成远离sink节点的传感器节点成为簇头的概率降低。当网络规模很大时,如果远离sink节点的区域没有选举出簇头,则在通信距离有限的条件下,远离sink节点的传感器节点很可能无法加入簇中,造成大量数据的缺失。因此,在网络规模很大情况下,New LEACH协议并不适用。
三维夹角循环路由3DIAIR[16]算法是分布式的、基于迭代的算法,作为贪婪路由的改进,3DIAIR的切入点是转发节点与目标节点的夹角,可以避免死路以及环路路由。但该算法采用了贪婪的路由方式,其计算的传播路径并不是使能耗最低的最优解。而且需要节点已知节点本身、sink节点以及所有一跳邻居的具体位置。
为了解决网络规模较大时簇头选举不均匀以及过长的传播距离造成的簇头过早死亡的问题,本文提出了一种混合的分簇路由算法:Hybrid LEACH。在簇头选举阈值的设置方面,去掉了地理信息的影响,使簇头分布尽量均匀。同时为了减少簇头的能量消耗,簇间数据传输采用3DIAIR算法,将单跳传输改为多跳传输,并且簇间传输不只在簇头节点集合中选择下一跳节点,也可以利用普通节点,以此进一步分散网络能耗,尽可能延长网络的生存时间。
具体地说,在簇头选举的阈值设置方面,去除New LEACH中的地理信息的影响。阈值设置如下式:
其中,Ec为节点当前剩余能量,E0为节点初始能量,Eb为节点前一轮消耗的能量。p1*为簇头选举的最优概率。W1和W2分别是剩余能量和能量消耗率对阈值贡献的权值。
在阈值设置中涉及到对节点当前能量和能量消耗率的衡量。节点的当前能量信息ζ用式(16)表示,用节点剩余能量占初始能量的比例表征,ζ较大的节点成为簇头的概率更高。
节点能量消耗率用式(17)表示。表征节点上轮传输中能量消耗的速度,若过大,则本轮被选为簇头的概率会降低:
对权值的约束如下式:
3 性能分析
Hybrid LEACH算法的性能仿真参数如下:第一种网络称为小规模网络,其大小为18.7*22.2*0.02km,其中深度分别为0m、5m、10m、15m和20m。最大分辨率10×10×5,传感器节点数为200,接入概率为0.7,传输频率9k Hz。第二种网络称为大规模网络,其大小为37.4*44.4*0.075km。最大分辨率20×20×10,传感器节点数为400,接入概率为0.7,传输频率9k Hz。能耗计算方法由第2节给出。
图1到图4描述了Hybrid LEACH协议在不同网络规模下的生存时间以及数据包上传数量。由图1和图2可以看出,当最大传播距离在3.5km时网络生存时间最长,随着最大传播距离的增加,生存时间逐渐下降。对于给定的网络和簇头分布,在满足节点能够接入簇的条件下,若最大传输距离较低,则节点接收的簇头广播信息较少,接收以及处理数据的能耗较低,反之接收和处理数据的能耗会提高。由图3和图4可知,随着最大传播距离的增加,上传的数据包数量逐渐降低,这是由于最大传播距离增加引起簇间传输跳数降低,从而减少多余的数据传输。
图5和图6将3DIAIR,New LEACH和Hybrid LEACH三种路由算法的性能在网络规模较大情况下加以比较。由图5可以看出Hybrid LEACH算法在网络生存时间方面性能最好。数据上传数量方面如图6所示,3DIAIR由于路由经过的节点较多,因此会收集到更多的数据,New LEACH协议除了传输数据的节点和簇头节点没有其他节点参与到数据传输中,因而数据传输量最低,Hybrid LEACH的数据传输量处于二者之间。综合以上参数,当网络规模较大时,Hybrid LEACH算法的性能更好。
4 结束语
在水声传感器网络的背景下,本文以水声信道的能耗模型为基础,结合分簇路由和树状路由的优点,提出一种混合路由算法Hybrid LEACH。该算法有效利用分簇算法网络能耗均衡的特点,并且簇间传输使用3DIAIR算法以降低簇头的能量消耗。实验结果表明,该算法在网络规模较大时,网络生存时间的性能优于其他算法,且数据上传量也较为可控。
摘要：针对三维水声传感器网络,在研究水声信道能耗特性的基础上,设计了一种能量高效的路由算法Hybrid LEACH。它基于经典的LEACH算法,而在簇间传输中使用一种树状路由取代簇头与汇聚节点直接通信,减少了簇头节点的能耗,达到延长网络生存时间的目的。仿真结果显示,Hybrid LEACH算法在网络规模较大的情况下可以有效延长网络生存时间。
关键词：水声传感器网络,路由算法,网络生存时间
三维路由算法 篇2
关键词：无线传感器,伪三维地理位置,算法分析
一、前言
在一个三维无线传感网络中, 我们用S来表示源节点, 用D来表示目的节点, 在与S相邻的节点内, 我们将距离节点D欧氏距离最近的节点用C表示。根据三维无线路由策略, S会选择C作为数据发送的下一跳。在理想情况下, 这种基于欧氏距离的选择策略, 可以保证数据传输的范围围绕着目的节点上下浮动, 维持源节点到目的节点的最短距离。但就实际情形而言, 传感器的节点经常是在高低不同的曲面上分布, 所以传输路线只能延路面起伏传播, 而不能按照我们设想的理想路线进行, 起伏地势表面的路径必然比其他邻居节点到目标节点的沿起伏地势的表面路径长, 所以, 基于欧氏距离的选择路径参考标准来说, 这种计算方式效果并不是很理想。为了能够满足实际的需求, 获得最理想的起点到目标点的路径长度, 需要根据起伏路的实际地势, 通过电子地图来对节点之间的起伏地势进行最短路径进行分析, 探讨新的计算距离的方法。
二、起伏地势上的最短路径的计算方式
电子地图是可以通过卫星来进行遥感的技术, 它以数字的形式存储在介质上, 采集到的信息精度可以到深入到厘米, 包含河流、道路、等高线、建筑物标等多方面的信息。在一个电子地图上, 某一地点的地理位置要通过x轴、y轴、z轴表示。我们假设R点是在电子地图上的一个位置, 那么在x轴、y轴信息已知的情况下, 我们就可以通过电子地图得到P点的Z坐标。即Z=f (x, y) 。
针对上文中所描述的三维无线路由算法在崎岖不平的地势情形下, 利用欧氏距离的选择路径算法不理想的现象, 我们用起伏地势上的近似最短路径来代替欧氏距离的方式, 利用电子地图空间取点的做法, 采用起伏地势上的近似最短路径, 在电子地图表面选取几个离散点进行计算。但这些离散点的选择要能从整体上反映电子地图表面的起伏趋势。对相邻离散点直接的欧氏距离进行计算后, 便可以将相邻两点之间的关系映射到一个二维平面上。根据上文提到的计算路径最短的方法, 计算出电子地图表面各个离散点之间的最短路径, 这条路径是通过对电子地图上的各个离散点的选取得来的, 所以能够很好的反应出其实际的最短路径。每次当传感器节点散落在电子地图所设计的区域时, 节点就会根据自己所在的地理坐标寻找到离自己最近的那个离散点, 然后根据离散点之间的最短距离去映射实际地势上两点之间的最短距离。
要计算出起伏地势上最短的路径, 首先要建立网格, 在电子地图上寻找离散点。建立网格的第一步是要截取要建立传感器网络区域内的电子地图, 根据这部分电子地图在电子地图的垂直投影面上按照横轴X方向和纵轴Y方向建立一个正方形的网格;第二步是把这些网格产生的交点从其垂直方向找出其与电子地图的交点, 同时要求每个交点的横轴X方向和纵轴Y方向上的距离是相等的, Z坐标则取电子地图与网格交点的垂线。其次要对电子地图上交点之间的相邻关系进行确定。电子地图上的交点投影到横轴X方向和纵轴Y方向上面得到一些按照正方形网格分布的离散点, 每个点只能与周围的8个点相邻, 并且每个点之间只计算它与相邻点之间的距离。再次, 将三维空间上的点映射到二维平面上, 并建立邻接。每个相邻点投影之间的记录与空间相邻点之间的距离对应, 这就便可以将计算空间内各相邻点之间的距离问题转化为计算二维图上的点与点之间的距离问题, 如此根据矩阵的行数与列数都为空间中点或者投影点的个数来建立邻接矩阵。邻接矩阵建立之后要寻找最短路径, 对应已经建立邻接矩阵的根据最短路径计算法计算投影面上任意点与点之间的最短距离, 得出的结果就是在电子地图上所选取的对应两点之间在起伏地势上的拟最短路径。最后当实际已知自己地理位置的传感器节点, 便可以依靠横轴X方向和纵轴Y方向来对相近的离散点进行定位, 确定了当前传感器节点对应的离散点和目标传感器节点对应的离散点就可以将实际中传感器节点的地理位置映射到与之相对应的离散点, 得出最短距离。
三、起伏地势上最短路径对下一跳的选择
为了方便计算, 我们在对电子地图采样选点的时候, 大部分取的是有规律的分布均匀的点, 但是当传感器上的节点在起伏的地势上随机分布时, 一定要采取定位策略使节点在最近的采样点上定位。即根据传感器节点上自身的坐标, 去找寻与这个节点相邻的四个采样点, 然后分别求得这四个采样点与目标节点之间的最短距离, 取与目标距离最短的那个点作为这个传感器节点对应的采样点。当多个采样点到目标节点之间的距离一样时, 则可以通过空间欧氏距离的计算方式来进行下一跳的选择。
利用无线传感器网络的过程中, 当源节点S向目标节点D进行数据转发时, 首先获得的是相邻节点的位置, 获取位置后再进行判断, 看一下目标节点是不是在它的邻居节点内。当目标节点在它的邻居节点内时可以直接发送数据, 如果目标节点不在它的邻居节点内便要采用上面描述的四个采样点选最短的方式进行选择。如果同时存在多个邻居节点对应到该采样点的情形, 那么就可以利用空间欧氏距离的方式对下一跳进行选择, 如果不这样就应该选取与这一采样点对应的邻居节点作为下一跳。如此不断的重复, 一直将数据传到目标节点。
此外, 理想的传感器节点应该是均匀分布的, 有着同电子地图的采样点一样的X坐标和Y坐标轴, 并且可以在电子地图上获取Z坐标。采用这种理想的分布方式, 既可以在路由的过程中可以避免定位和采样点带来的误差, 又可以有意识的避开有较大起伏的地势, 进行理想的路径选择。
四、小结
文章基于实际情况下无线传感网络分布的地势环境, 提出伪三维地理位置网络的路由算法, 并对其进行分析, 其核心思想是运用起伏地势上的拟最短路径取代过去一直运用的空间欧氏距离, 使路由选择能够更贴近现实。伪三维地理位置网络的路由算法对建立在有起伏路上的无线传感器网络而言, 用上文描述的以起伏地势上的最短路径代替空间距离, 一方面可以有效的减少路由的跳数, 另一方面也可以减少能量的损耗, 延长网络的生存时间。
参考文献
[1]张衡阳, 李莹莹;基于地理位置的无线传感器网络路由协议研究进展[J];计算机应用研究;2008-01
[2]林观康, 程良伦;基于地理信息静态分簇的无线传感器网络路由算法[J];计算机应用与软件;2011-02
路由器的构造及路由算法的研究 篇3
关键词：网络时代,路由器构造,路由算法
1 路由器的构造
路由器是组建互联网的重要设备，路由器和PC机非常相似，有硬件部分和软件部分组成，只不过它没有键盘、鼠标、显示器等外设。IOS是路由器的操作系统，是它的软件组成。路由器是第三层设备，通过运行路由协议了解整个网络的路由情况，并建立一个指示路径的路由表。当用户数据进入路由器后，路由器根据接收到的数据包包头中的第三层地址信息，查阅路由表，把数据从一个接口交换到另一个接口。
1.1 中央处理器（CPU)
和计算机一样，路由器也包含中央处理器。路由器的处理器负责许多预算工作，比如维护路由所需的各种表项以及做出路由选择等。路由器处理数据包的速度在很大程度上取决于处理器的类型。某些高端的路由器上会拥有很多个CPU并行工作。
1.2 内存
在路由器中，主要有以下几个类型的内存：1)只读内存(ROM);2)随即访问内存(RAM);3)闪存(FLASH);4)非易失性内存 (NVRAM) 。
1.3 接口（Interface)
路由器的接口是配置路由器的主要考虑对象之一，同一台路由器上不同接口的地址应属于不同的网络。路由器通过接口在物理上把处于不同逻辑地址的网络连接起来。这些网络的类型可以相同，也可以不同。路由器的一些接口是ISDN接口、串行接口，它们通常将路由器连接到广域网链路上;还有一些是局域网接口(LAN接口)，例如Ethe rne t、令牌环网和FDDI等。
1.4 路由器的软件
如PC机一样，路由器也需要操作系统才能运行。路由器的操作系统叫做IOS (InternetworkOperating System)。路由器平台不同、功能不同，运行的IOS也不尽相同。
2 路由器算法
2.1 硬件算法
目前使用最多的硬件实现方法是使用CAM (Content Addressable Me m ory)内容可寻址存储器，它是一种特殊的存储器件，用来实现路由表查找的一种硬件方法。CAM的最大特点是能够在一个硬件时钟周期内完成关键字的精确匹配查找。为了能够实现最长前缀匹配，一个CAM表存放一类定长的前缀集。IPV4下需要32个CAM。这种方法有一个明显的缺点，在对地址前缀长度具体分配没有准确的了解之前，为了能够保证存储N个前缀表项目，每个CAM都要有N个表项的空间，因此，CAM存储空间的利用率大大降低了。
另一种基于硬件的改进CAM算法是基于TCAM(三值CAM)的算法。在进行搜索的时候，所有的TCAM项都需要同时进行匹配，在有多个匹配项时，TCAM规定在所有匹配的表项中选取地址最低的表项作为最后的结果。因此，为了能够进行最长前缀路由的查找，就需要保证在TCAM的低地址区域存储前缀路由项，而在高地址区域存储短前缀路由项。TCAM具有速度快、实现简单的优点，但它也具有几个不足之处：1)单位比特昂贵;2)容量小;3)并行匹配导致功耗很大;4)更新复杂。
2.2 软件算法
IP路由要求查找最长匹配的前缀地址，因此树形结构的路由查找算法将最长前缀匹配查找模型话为一棵二进制树的过程。用Trie表示前缀并不存储在Trie的结点中，而是用结点间的路径表示前缀，一般规定一个结点到其左子结点的路径表示前缀中的对应比特为0，结点到其右子结点的路径代表前缀中的对应比特为1。IPv4中地址长度为32，所以二进制trie树的深度为32层，前缀长度即子网掩码长度为L的网络路由会被存放在第L层的结点中。二进制trie树算法一次更新操作只需要首先查询定位并修改一个结点，开销较小，它的最大不足在于查找过程中要进行大量的存储访问，对于IPv4地址查找最多需要32次，IPv6地址为128次。
三维路由算法 篇4
一般来说。路由包含着两个方面的功能, 一方面是对在搜集过程中的网络状态进行着不断的更新与整理。另一方面则是对已经搜集到的信息计算可行路。当前存在的很多的协议都是为了给目标地址搜寻最适合的短路。具体的过程是当数据包传送至路由器时, 路由器就会根据其数据的属性以及相关信息进行及时处理和分析。然后在进行科学的发送。由于目前比较热门的话题就是研发智能路由器, 如果在研发路由器时能够有具有某种能力的平台或媒介, 当给出的一组输出路线的数据包到达时, 接着根据资源管路系统中的信息, 就能够使路由器自己判断出这组线路中哪一条线路能够最先使用, 然后将数据包进行科学化的整理和归纳, 最后的一个步骤就是等待上传。整个路由过程是一个随着外界环境变化以及需求变化的一个系统, 所以要对整个路由算法进行及时的调整, 以保证整个信息的时效性与完整性。
2 Qos路由
一个比较完整而且较为系统的三元组所界定实时信息的产生。其包括最大信息尺寸, 最大信息速率以及最后一个最大突发信息数, 其实质是一个简单的模型控件, 而相对来说, 在每次模型连接的过程中, 一般都会有两个相对的约束, 第一个是在一定时间t的间隔中, 所达到的信息数一般不超过Bmax+t Rmax;第二个是每个信息的长度一般不超过Smax。因此在此基础上, 如果只是单方面的采用一个估算值来对实时信息就行分析与计算, 就会出现延迟以及不准确的情况。我们针对不同网络的运行情况, 给出了以下路由的算法:
在目前网络科技还不够发达的情况下, 为了根据实际情况的需要, 就应该建立起一个相对连接较少的通信量。简单得到可以表述为:若t点希望与dest点建立连接Mk+1.在点i的积极出狐集A中路由器现则最先空闲的路线A, 通过a上建立的Mk+1来计算出所需要的时间, 即rk+1, 如果计算结果不超过预定的边界值D, 连接请求信息被放于卢新A发热环城区内以等待发送。当然在此过程中, 连接请求信息包括:谜底地址、最大信息储存、信息到达最小间隔、端到端延迟边界、请求过时时间。当一个中间点A收到连接建立请求时, 首先需要确定信息是否已经超时, 如果采用A作为目的点, 就应该调用search-one来做出回答, 相反, 若不是采用A作为目的点, 我们就应该采取相对应的措施来对信息进行更加深入的加工与处理。通过上述的算法来计算发送信息传输的时间, 如果在同一延迟边界的条件下, 当期望值小于或等于最短路的传输时间, 这种连通率的算法远远超过了最短路的算法。
3 多路路由算法在Qo S路由中的应用
1) 随着社会网络技术变革所带来的转变, 分布式多媒体的广泛应用, 在局域网或者广域网上进行语音、视频等实时信息的传输等的要求, 都给目前网络技术的研究提出了新的挑战, 就拿因特网来说, 同一个会话的数据包就能够有不同的路径达到同一个目的地, 虽然这种结果具有一定的合理性与科学性, 但在实际运用中远不能满足目前多种数据类型的综合服务的要求。因为数据包会因为多种不同上网因素造成一定的延迟, 导致的结果是到达目的地是错乱的, 因此信息的质量不仅得不到保障, 而且对整个信息网络的系统话都会带来很大的影响。一般来说, 在网络信息之间的服务质量通常是来表达服务者和使用者之间在数量或质量上有定义性的约定, 即一次连接的服务质量一般都是受着一系列的约束条件所限制的。最为常见的就是宽带约束、延迟约束以及抖动约束。在这种情况下, 寻找服一条资源可靠而且合理的可行路, 是非常有必要的。
2) 近年来, Qos路由已经已经被越来越多的人所关注, 很多新颖的具有创造性的算法被提出, 多路路元就是其中一个典型的算法, 也是在路由算法中一个发展趋势相对来说比较不错的路由算法, 但是其主要针对的是网络流量较少的情况。这也就是说, 多路路由存在的最为主要的任务就是更好的去实现网络信息数据承载的平衡性, 把流量分布得更加均衡, 这样就会增加路由未来连接请求的连通率, 并且能够使没有经过Qos保证的数据也有更充足的回应时间。除此之外, 如果整个网路的信息负载量过大, 同时还在不断的变化, 就能够把多路路由器的算法分成三类。其中, 最为常见的就是PNNI, 就是通过回绕的方式搜素连接路由的路径。但是如果其选择的路径不能够满足Qos的实际需要时, 整个寻路过程就回重新回到起点, 寻找下一条符合实际发展需要的路径, 这个方法的好处是可以比较能动性的去适应实际需求的变化, 但也有其缺点, 就是整个的连接所耗的时间比较长。另一个就是并行多由路径, 他就能够克服这方面的缺点, 所谓的并行多路路就是路由将所有的洗洗脑沿多条路径同时出发, 但是在沿途过程中会预留一些信息资源, 当其中任何一个信息到达所需要的目的地的时候, 整个过程中就算被完成, 其他路径的所有信息就会被停止释放。
4 总结
文章通过对路由的具体分析与探讨, 提出了一种可以调节服务质量的路由算法, 这种算法的基本原理就是根据实际网络情况变化而进行相应的调整与变化, 这种算法能够根据网络的实际运行情况自行的寻找路由范围, 即在设定的传输时间的上限期限值B, 如果B的值越大, 就表示寻路的范围越广, 需要花费的寻路也更多。如果当B减少了, 就表示寻路的范围也相应的减少, 从而减少寻路的花费, 但是会影响到连通率, 导致用户对连通率的期望值大打折扣, 也会影响到网络运营商对于网络资源的利用率。通过大量的实验证明, search-one的算法比最短路的算法具有更高的连通率, 并且通信的花费和连通率的比值最小。所以, 以后searchone的算法很有可能会代替最短路的算法。而在多路路由的算法之中, opti-mal可以选择的可行路具有最少的跳数, 并且所化的通信费与连通率的比值是最小的, 因此, 要想花费最少, 而且寻找出最可靠可行的线路, 就可以选择采用opti-mal的算法。
参考文献
[1]汪芸, 顾冠群, 网络服务质量 (Qos) 参数研究, 计算机研究与发展, 2012.35 (6) :543-547.
[2]李昌兵, 基于计算智能的多播QoS路由技术研究[D], 重庆大学, 2010年
ZigBee路由算法的改进 篇5
近年来, 作为在低速率的无线传感器网络和控制网络中最受瞩目的技术之一, Zig Bee以其低成本、低功耗、低速率、高可靠性等特性, 广泛应用于工业、医疗、军事、智能家居等需要低功耗、低成本, 对数据传输速率和服务质量要求不高的无线通信应用场合[1]。
Zig Bee网络层 (NWK) 介于MAC层和应用层之间, 是由Zig Bee联盟制定的。Zig Bee网络层的主要功能就是确保Zig Bee的MAC层能正常工作, 并且提供适合的服务接口给应用层。网络层提供了两个必要的功能服务实体用于向应用层提供接口:数据服务实体和管理服务实体[1,2]。
NWK主要功能有: (1) 加入和离开网络; (2) 帧的安全机制管理; (3) 根据路由发送帧到目的地址; (4) 发现和维护路由; (5) 发现单跳邻居节点和维护邻居节点信息。
二、Zig Bee网络层技术简介
2.1 网络拓扑结构及地址分配
Zig Bee网络中存在三种网络节点, 分别为中心协调器、路由节点和终端节点。协调器是整个Zig Bee网络的中心, 是协调点, 负责整个网络的组织、维护和管理工作, 必须由FFD (全功能设备) 构成;路由节点负责数据的传输和转发功能, 必须由FFD构成, 但路由节点必须由协调器控制;终端节点负责自身数据的发送并接收其他节点传过来的数据, 可以由FFD或RFD (精简功能设备) 构成。
Zig Bee网络有星型、网状型和树型三种拓扑组织形式。由于树型网络结合了星型结构和网状结构的优点, 且具有较好的扩展性, 所以Zig Bee网络一般采用簇树拓扑结构组织节点。中心协调器启动后就创建一个网络, 设置自身网络地址为0, 路由节点和终端节点选择相应的有路由功能的父节点加入网络, 形成父子关系。成功加入网络后, 该节点获得父节点分配的一个唯一的网络地址。
规定每个父节点最多可以连接Cm个子节点, 这些子节点中最多可以有Rm个路由节点, 网络的最大深度为Lm, Cskip (d) 是网络深度为d的父节点为其子节点分配的地址之间的偏移量, 它的值按公式 (1) 计算, 分配给第k个子路由节点的地址Ak满足式 (2) , 分配给第n个子路由器节点的地址Ak满足式 (3) 。其中, Afather代表父节点的地址。
2.2 Cluster-tree路由算法
Cluster-tree算法根据树结构转发分组, 如果终端节点要发送数据包到网络中的其他节点, 则直接将该数据包转发给其父节点, 由父节点进行转发。
如果一个路由器节点要转发数据包到网络地址为D的目的节点, 已知该路由器节点的网络地址和深度分别为A和d。
首先, 该路由器节点会依据下述表达式判断目的节点是否是其后裔节点:
如果目的节点是其后裔节点, 则下一跳节点地址为:
否则, 如果目的节点不是其后裔节点, 则下一跳节点为该节点的父节点。
2.3 AODVjr路由算法
AODVjr[3]是AODV的简化版本, 具有AODV的主要功能, 但考虑到降低成本、节能、使用的方便性等因素, 简化了AODV的一些特点。
首先AODVjr舍弃了AODV中的目的节点序列号, 为保证路由无环路, AODVjr中规定只有分组的目的节点可以对RREQ (路由请求) 分组进行响应, 即使中间节点存在通往目的节点的路由也不能回复。同时AODVjr不存在AODV中的“先驱节点列表”, 从而简化了路由表结构。另外AODVjr取消了HELLO信息的发送, 由目标节点定期向源节点发送KEEP_ALIVE连接信息来维持路由[4,5,6]。
三、改进的算法设计
3.1 问题的提出
Cluster-tree算法不存在路由发现过程, 限制了寻址的灵活性, 建立的路由不一定是最优的, 从而浪费网络能耗并且引入服务延迟。因而, Zig Bee中允许有路由能力的节点使用AODVjr去发现一条最优路由。但是AODVjr算法在路由发现过程中会产生多余的RREQ分组, 容易引起广播风暴。例如, 图1中节点1发起路由发现, 寻找到节点7的路径, 节点1向所有邻居节点发送RREQ分组, 而向节点1的后裔节点2和3发送RREQ分组对寻找路由帮助不大, 成为多余的RREQ分组。同理节点7要寻找到节点9的路径, 向其父节点0广播也将产生多余的RREQ分组。
此外, 由于网络中某些节点传输数据量过大, 特别是距离中心协调器越近的节点, 从而提前耗尽自身能量, 容易造成网络分割, 影响了整个网络的通信, 缩短了网络的寿命。
针对以上问题, 本文从控制RREQ分组以及能量均衡的角度出发, 提出一种改进的算法, 有效的限制AOD-Vjr路由发现过程中的RREQ的广播, 延迟网络分割出现的时间, 从而提高网络的性能。
3.2 改进的路由算法M_ZBR
3.2.1 冗余RREQ分组的控制
改进的路由算法M_ZBR在路由发现阶段, 利用Cluster-tree结构及算法的特点, 根据公式 (4) 判断出目的节点与当前节点的关系, 从而判断出RREQ分组转发最佳的大致方向。因此, M_ZBR算法在RREQ分组中增加一个标志位flag。当目的节点为当前节点的后裔节点时, flag=0, 即表示当前节点的父节点不宜转发该RREQ分组;当目的节点不是当前节点的后裔节点时, flag=1, 即表示当前节点的后裔节点不宜转发该RREQ分组。
另外, 从树结构可以看出, 若在使用Cluster-tree路由算法时, 可能存在的最长路径应是网络最大深度的2倍。由此, M_ZBR算法通过设定最大传输跳数也可以减少部分冗余的RREQ分组, 本算法中, 当跳数hops>2Lm时, 节点便丢弃该RREQ分组。
3.2.2 节点能量的控制
M_ZBR算法根据Zig Bee路由算法的特点, 对Zig Bee网络中的路由节点采用了能量控制机制, 这对延长网络寿命, 延迟死亡节点以及网络分割出现的时间都是十分必要的。因此, M_ZBR算法定义了节点最小路由能量Emin, 当节点的能量低于Emin时, 路由节点将不再发起路由发现, 即不再采用AODVjr路由算法。
在Zig Bee网络中, 越靠近中心协调器的节点参与数据传输就越频繁, 对整个网络的通信来说也就越重要, 所以Emin的能量控制应与节点深度成反比, 深度越小节点应具有相对较大的最小路由能量, 因此, 将Emin定义为:
其中, Elimit为节点正常工作需要的最小能量值, 为控制系数, 可以根据需要人为的控制Emin的大小, d为节点的深度。
此外, M_ZBR算法依据节点最小路由能量的定义, 设置一个节点能量警戒值Ewarning:
其中, k为大于1的控制系数。
依据以上节点能量阈值的设置, M_ZBR算法在RREQ分组中增加了能量标志位energy_flag, 用于统计RREQ分组传输过程中统计处于能量警戒区内的节点个数。
3.2.3 算法流程
(1) 当RFD节点要给网络中其他节点发送数据时, 直接采用Cluster-tree算法, 即将数据转发给其父节点, 由其父节点转发。 (2) 当FFD节点要发送数据到网络中其他节点时, 首先查找路由表中有无到目的节点的路由表项, 若有则按路由表转发数据包, 若无则启动路由发现过程。 (3) 在路由发现阶段, 任意节点收到RREQ分组时, 首先检测本节点是不是该RREQ分组的目的节点, 如果不是, 则转 (4) ;若是, 则转 (9) 。 (4) 判断节点自身的剩余能量, 如果剩余能量小于节点最小路由能量Emin则直接丢弃RREQ分组, 否则转 (5) 。 (5) 查看RREQ分组中的跳数值, 若hops>2Lm, 则丢弃RREQ分组, 否则转 (6) 。 (6) 查看RREQ分组中的标志位flag, 若flag=0, 转 (7) , 若flag=1, 则转 (8) 。 (7) flag=0表明本节点不宜转发子节点发送的分组, 需判断本节点是否为前一跳的父节点, 若是, 则丢弃RREQ分组;若不是, 则判断目的节点是否为当前节点的后裔节点, 如果是, flag的值继续为0, 直接转发分组, 若目的节点是当前节点的后裔节点, 则设置flag=1。 (8) flag=1表明本节点不宜转发父节点发送的分组, 需判断本节点是否为前一跳的子节点, 若是, 则丢弃该分组;若不是, 则需判断目的节点是否为当前节点后裔节点, 如果是, 则设置flag=0, 若目的节点不是当前节点的后裔节点, flag的值继续为1, 直接转发分组。 (9) 当目的节点收到RREQ分组时, 判断自身剩余能量, 若小于Emin, 直接回复RREP;否则将收到的分组放入缓存区, 在缓存时间t内, 比较各RREQ分组的能量标志位energy_flag, 选择energy_flag最小的RREQ分组且回复RREP。
四、仿真结果分析
为了验证改进算法的实际效果, 通过仿真实验对比原来的AODVjr算法, 分别比较了死亡节点个数以及总能量损耗, 仿真结果证明了算法的可行性和有效性。
图3是原AODVjr算法与改进算法死亡节点数的比较, 曲线 (1) 是原AODVjr算法随数据流量增加而变化的死亡节点数, 曲线 (2) 是改进后的算法的死亡节点数。当数据流量较小时, 节点能耗就较少, 节点死亡数相对就比较少。当数据流量增加时, 死亡节点数也会增加, 改进的算法通过能量标志位的判断, 选取能量标志位最小的RREQ分组并回复, 明显比原算法的死亡节点数增加的缓慢。
图4比较了改进算法与原算法的网络总能量耗损。曲线 (1) 是原AODVjr算法随数据流量增加而变化的网络总能量耗损, 曲线 (2) 是改进后的算法的网络总能量耗损。显然, 改进的AODVjr算法通过控制了RREQ分组减少了网络的耗能。
五、结论
本文主要针对Zig Bee的路由协议进行分析, 基于能量均衡对Zig Bee现有的路由算法AODVjr提出了改进, 通过限制路由发现过程中的RREQ的广播, 很好的延迟网络分割出现的时间, 从而提高网络的性能。仿真实验将原算法和改进的算法进行了比较, 改进的路由算法有效地减少了总耗能与死亡节点数。
摘要：网络层的路由协议是ZigBee协议规范的研究重点之一, 因为网络节点中节点的能量资源、计算能力和带宽都非常有限, 路由算法优化与否对整个网络的性能有着至关重要的作用。从控制RREQ分组以及能量均衡的角度出发, 对AODVjr算法提出了改进。通过仿真实验, 将改进的算法与原AODVjr算法进行性能参数的比较分析, 实验结果验证了改进后的算法的有效性。
关键词：ZigBee,路由算法,AODVjr,无线传感器网络
参考文献
[1]ZigBee Alliance.ZigBee Document053474r13[S].December1, 2006.
[2]朱向庆, 王建明.ZigBee协议网络层的研究与实现.电子技术应用.2006.1:129
[3]Hakeres I D, KleinBerodt.AODVjr, AODVsimplified[J].Mobile Computingand Communication Review, 2002, 6 (3) :100-101.
[4]班艳丽, 柴乔林, 王芳.改进的ZigBee网络路由算法.计算机工程与应用, 2009, 45 (5) :95-97
[4]谢川.基于ZigBee的AODVjr算法研究.计算机工程, 2011, 37 (10) :87-89
浅谈机会网络路由算法 篇6
机会网络是一种不需要在源节点和目标节点之间存在完整连通路径, 利用节点移动带来的相遇机会实现通信的时延和断裂可容忍的自组织网络[1]。在机会网络中, 节点之间的链路经常间歇性的中断且这种中断一般持续时间较长, 以至于在任何时刻源节点和目标节点之间可能一直不存在连通的路径。
很明显, 机会网络和现有的常用的网络不同, 它具有以下特性:
(1) 低数据传输速率、高延迟 (2) 网络断开 (Network disconnection) (3) 长排队时间。正是由于这些特性, 使得传统的存储—转发模式不适合于机会网络, 在机会网络中要采用存储—携带—转发模式来进行通信。
2、机会网络路由算法
路由问题是任何组网技术的首要问题。机会网络的路由问题更是机会网络中的研究重点。现有常用的网络路由协议中都是假设在源节点和目标节点之间至少存在一条完整的通信路径, 所以不适合在机会网络中运行。机会网络中的路由转发机制是以“存储—携带—转发” (Store-CarryForwarding) 的模式工作。要设计出高效机会网络路由协议的关键问题在于如何针对每个消息来找出最好的下一跳转发节点和何时进行数据转发。良好的路由算法能提高报文传输的成功概率, 降低传输延迟, 减少能量的消耗。
人们针对不同类型的机会网络提出了各式各样的路由算法。目前现有机会网络路由算法主要有以下几类:
2.1 基于复制的转发算法
在基于复制的路由转发机制中, 一条消息会有多份拷贝被注入网络, 只要其中有一份拷贝被传送到目标节点, 这条消息则传输成功。然而, 它的核心问题在于消息拷贝数怎么确定才算合适以及怎样来产生消息拷贝。最简单的方法就是直接传输 (Direct Transmission, 简称DT) [2]方法, 即源节点直在和目标节点相遇时才进行数据转发, 这样做网络耗费是最小的, 但往往会传输延迟较大, 并且经常会因为源节点碰不到目标节点而造成传输失败, 其传输成功率最低。在源扩散Source Spray and Wait (SSW) 算法[3]中, 事先指定消息的最大拷贝数为L。源节点起始时拥有一个消息的L个拷贝, 源节点先将消息拷贝给最先遇到的L-1个中继节点, 然后源节点和中继节点只在遇到目标节点时才进行转发。
2.2 基于编码的转发算法
这类机制中, 会把要传输的数据先编码成互相冗余的消息, 目标节点接收到编码后的一部分消息, 就能够通过一定的运算来重组原始数据。在Ling-Jyh[4]等人提出的H-EC中, 针对每个编码后的小消息会生成两个拷贝。当遇见邻居节点的时候, 首先会将消息的第l份拷贝传递给该邻居节点, 然后会在该连接持续的时间内, 将其他消息的第2份拷贝传输给该节点。该机制因为充分利用了所有的连接机会所以传输性能更好。
2.3 基于相遇预测的转发算法
根据对历史概率进行统计, 每个节点都具有一个与目标节点相遇的概率, 人们也可以通过节点的历史移动来预测该概率值。在节点移动过程中每个节点选择与目标节点相遇的概率值更高的节点作为转发的中继节点, 这就是基于相遇预测的机会转发机制。比如Seek and Focus[5]协议中, 针对每一个节点, 当前节点都会记录下自上次相遇之后所经历的时间, 并据此来估计节点间的相遇概率值。此外, 节点间的相遇概率还可以根据节点的位置和节点的运动方向来进行估计。
2.4 基于链路估计的转发算法
基于链路估计的机会转发机制在选择转发节点时则根据节点之间的“端到端”的链路状态。在机会网络中是否转发可以依照根据收集到的单跳链路状态进行估算得出的端到端路径的效用值。在最短期望路径路由 (Shortest Expected Path Routing Protocol) [6]中, 利用节点所维护的到达已知节点的链路效用值也即链路可用概率值。再通过Dijkstra算法计算出当前节点与目标节点之间的最短路径。
2.5 冗余效用混合转发算法
冗余效用混合转发机制结合了并行传输和基于效用的转发决策的优点来提高传输的性能。PROPHET (Probabilistic Routing Protocol Using History of Encounters and Transitivity) [7]就是综合了传染转发和基于相遇预测转发二者的优点。在PROPHET中, 每个节点都维护着对网络中其它节点的一个效用值, 在转发过程中会根据节点对消息的目的节点的效用值来选择是否进行转发。只是在PROPHET中概率效用值的更新使用了概率的传递性, 即如果节点a有可能遇到节点b, 而节点b又有可能遇到节点c时, 则认为节点a也可以成为目标节点为c的消息的转发节点。当节点相遇的时候, PROPHET会将消息传输给那些到达目标节点的概率比自身高并且没有存储该消息的节点, 从而降低了传染转发中因为广播消息引起拥塞而导致的性能下降。
2.6 基于节点主动运动的转发算法
当网络中拓扑变化或因节点稀疏而存在较强的随机性时, 以上所介绍的机会转发机制都因为被动等待与更好的转发节点相遇, 而造成传输成功率降低或者传输时延增大。在基于节点主动移动的转发机制中, 有一部分特殊的节点可以通过自身的主动移动, 为其他的普通节点提供通信服务。DataMULEs系统[8]即是通过引入移动节点从而实现稀疏传感器网络中的数据收集。
3、结语
机会网络路由是一个富有挑战性的问题, 它要求对路径选择、评估传递性能、缓存管理和调度传输等多种技术来综合考虑。而目前的各种机会路由技术还存在一些关键的问题需要解决, 可以预见, 未来对于机会网络路由问题的研究可能会致力于实际应用的考虑, 使机会网络得到更大范围的应用。
摘要：随着传感技术、嵌入式技术、无线通信技术、高性能计算等相关领域的迅猛发展, 以物联网为代表的新一代的智能互联网络应运而生。出现了一种新的基于机会转发的路由技术, 使用该技术的网络, 称为机会网络。本文主要介绍了机会网络的概念和理论基础, 并分析比较了当前机会网络的一些较为重要的路由算法。
关键词：机会网络,路由,路由算法
参考文献
[1]熊永平, 孙利民, 牛建伟, 刘燕.机会网络[J].软件学报, 2009, 20 (1) :125-134.
[2]肖明军, 黄刘生.容迟网络路由算法[J].计算机研究与发展, 2009, 46 (7) :1065-1073.
[3]spyropoulos T, Psounis k, Raghavendra CS.Spray andwait:An efficient routing scheme for intermittently connect-ed mobile networks[C].In:Proc.of the 2005 ACM SIG-COMM Workshop on Delay-Tolerant Networking.Philadelphia:ACM, 2005, 252-259.
[4]Chen L, Yu C, Sun T, Chen YC, Chu HH.A hybrid rout-ing approach for opportunistic networks[C].In:Proc.of the2006 SIGCOMM Workshop on Challenged Networks.Pisa:ACM, 2006, 213-220.
[5]Spyropoulos T, Psounis K, Raghavendra C.Single-Copyrouting in intermittently connected mobile networks[C].In:Proc.of the 2004 1st Annual IEEE Communications SocietyConf.on Sensor and Ad Hoc Communications and Net-works.2004, 235-244.
[6]Tan K, Zhang Q, Zhu W.Shortest path routing in partial-ly connected ad hoc networks[J].In:Global Telecommunica-tions Conf.the GLOBECOM 2003, Vol.2, 2003, 1038-1042.
[7]Lindgren A, Doria A, Schelen O.Probabilistic routing inintermittently connected networks[J].ACM SIGMOBILEMobile Computing and Communications Review, 2003, 7 (3) :19-20.
三维路由算法 篇7
随着Internet分布式计算的迅速发展, Anycast (选播) 这种新型网络通信方式也随之被定义, 选播是实现一台主机与一组主机之间的通信方式。其特点在于, 可以使多个www镜像服务器共享一个选播地址, 极大改善网络资源和服务器的负载均衡, 还能简化一些网络服务的工作。由于是接收者共享一个选播地址, 因此选播路由算法相当重要。该算法不仅要适用于选播通信服务, 而且要尽量保证服务质量 (QoS) , 尤其要考虑服务器负载、网络剩余带宽分配等问题。
本文利用遗传算法GA (Genetic Aglorithm) 来改进选播路由算法。
1 算法设计分析
我们把通信网看成是一个有向连通图G= (V, E) , 其中V={v1, v2, …, vn}是网络中的节点集, E={e1, e2, …, en}是网络中连接两个节点的链路集合。每一条链路上都具有链路带宽Bi, 在选播路由算法中包含如下一些度量值, R= (S, D, Q) , 其中S表达选播路由的源节点, D表一组目标节点组, Q则是一些QoS相关质量参数, 这些质量包括:传输带宽B, 传输延时T, 服务器负载P等。
· 有效传播带宽 反映网络动态性能的参数, 通过协议SNMP中的MIB来得到路径已用带宽b, 即某路径的有效传输带宽为:B-b 。
· 延时 假设路径上各节点的延时为静态可加性延时, 这样便可采用该路径中所经历的所有节点的延时总和来作为整条路径的延时。
即
其中
· 服务器负载 服务器负载参数是为了均衡服务器负载, 提高服务质量的一个重要参数。
在具体应用中, 一般服务数据比请求数据多。服务数据的服务质量比请求数据更重要, 而两个方向的可用带宽不总是相同的, 所以选取的是逆向路径指标来度量服务质量[1]。
Q=t (kt+kb (1-b/B) +kpp)
t:路径逆向传输延时
b:路径逆向已用带宽
p:路径对应的选播成员的服务器负载
B:网络最大带宽
kt, kb, kp:相应调整系数, 可根据具体网络中应用情况来调整延时、带宽和负载的关系。
2 基于GA的路由算法设计
2.1 GA概述
GA是一种模拟生物种群自然选择的遗传进化机制。GA本质上是从一个初始种群进行不断迭代, 在迭代过程中根据一定条件进行优胜劣汰的选择, 从而产生出性能更优的下一代群体, 直到得到满意的解为止。
2.2 染色体的编码方法和初始种群的生成
本文讨论的是在一定约束条件下的最佳路径的搜索问题, 显然所得路径结果长度不尽相同, 因此采用不定长编码来构造染色体。在网络拓扑结构中, 每个节点都有相应的数字编号, 而每条染色体就代表一条搜索的路径, 因此, 从源点到目的节点的每个节点编号序列组织在一起便构成一条染色体[2]。
在生成初始种群时, 按照网络拓扑结构由宽度搜索算法生成popsize条路径 (popsize是规定的初始种群大小) 。初始种群中的染色体编码设计与节点的自然路径相同, 从而减少了编码转换的过程。
2.3 适应度函数
GA算法进行进化的根本依据是适应度函数, 由它引导着选择、交叉、变异等遗传操作的进行, 因此好的适应度函数对GA算法的收敛速度和有效进化、寻找全局最优解有着至关重要的作用。根据选播度量的参数, 将适应度函数定义为:
Fitness= (kt/t+kb (1-b/B) +kp/p)
可以看出, 它能充分地考虑到剩余带宽、延时和服务器负载等因素。
2.4 遗传操作
· 选择与复制操作
本文采用轮盘赌的方法进行染色体的选择, 按每个个体适应度值的比例得到一个轮盘赌的轮转切片, 然后转轮转动次数达到能够使个体在群体中满足popsize为止, 选出其中较优的染色体复制到下一代中, 以维持下一轮进化。
· 交叉操作的改进
适当的交叉和变异操作可以增强染色体多样性, 提高遗传算法搜索能力, 从而避免出现早熟的情况。交叉操作是交换一对父染色体部分基因片断而生成下一代染色体。本文采用单点交叉的方法[3]:
在两条父代染色体P1, P2中找到一个相同点, 以此为分界点将P1的前段基因与P2后段基因组合, P2的前段基因与P1后段基因组合, 生成两个新的子代基因P′1, P′2, 交叉后可能形成环路, 应对其进行修复, 判断新基因中是否有重复节点。若有则将两个相同的节点之间的路径删掉, 从而保证路径中不出现环路。P1: (1, 3, 4, 9, 7, 12, 13, 19, 26) , P2: (1, 2, 6, 5, 7, 11, 9, 17, 21, 22, 24, 26) , 搜索到第一个相同点7, 以此为分界点使P1, P2相互交叉。得到P′1: (1, 3, 4, 9, 7, 11, 9, 17, 21, 22, 24, 26) , P′2: (1, 2, 6, 5, 7, 12, 13, 19, 26) 。检查P′1中存在环路, 因此删除两个相同节点9之间的路径后变为:P′1: (1, 3, 4, 9, 17, 21, 22, 24, 26) 。P′1, P′2为交叉并修复后的染色体。
· 变异操作的改进
变异操作首先在群体中随机选择一个个体, 并将其中的基因片断作修改, 变异成一个新的个体。如P1: (1, 3, 4, 9, 7, 12, 13, 19, 26) 随机选择其中一个基因片断 (9, 7, 12) , 然后以9作为起点, 12作为终点, 随机生成一条路径: (9, 10, 13, 12) , 用此新路径替代原基因片断, 得到变异后新染色体P′1 (1, 3, 4, 9, 10, 13, 12, 13, 19, 26) ;若有环路出现, 则删除环路 (同交叉操作中去除环路的方法) , 修复后得到子代的变异染色体P′1为 (1, 3, 4, 9, 10, 13, 19, 26) 。
2.5 交叉率与变异率的改进
在进行交叉操作和变异操作时, 如果交叉率和变异率过小, 则种群很难产生出优秀新个体, 但若过大, 则容易破坏染色体中的优良基因, 导致搜索不稳定。本算法在考虑交叉率和变异率时, 不使用固定的交叉率和变异率[4]。当进化初期适应度较低时, 增强极差个体的变异能力, 使之更易产生出优秀新个体, 进化后期, 高适应度个体较集中, 此时降低交叉率和变异率, 更好地保护优良模式, 这样既能使算法跳出局部最优解, 克服早熟现象, 又能加快收敛速度, 提高全局搜索能力。在每代遗传操作中交叉率Pc和变异率Pm的定义如下:
fmin:表示种群中最小适应度 favg:表示种群中平均适应度
f:表示变异个体的适应度
f ′:参与交叉的两个个体中较大的适应度
Pc:交叉率 Pm:变异率
Pcmin, Pcmax:表交叉率上、下限
Pmmin, Pmmax:表变异率上、下限
实验表明:Pcmin=0.5, Pcmax=0.9, Pmmin=0.005, Pcmax=0.05, 效果良好。
2.6 收敛性分析
论文中提出的遗传算法能够收敛到全局最优解。
证明, 根据文献[5] 定理2.6, 具有变异率Pm∈ (0.1) , 交叉率Pc∈[0, 1], 同时采用比例选择法, 且在选择后保留当前最优解的遗传算法, 最终能收敛到全局最优解。
3 仿真实验
实验设置为:种群规模50, 交叉率Pc∈[0.5, 0.9], 变异率Pn∈[0.005, 0.05]。进化终止代数100, 网络拓扑图30个节点, 源节点S=1, 目的节点为四个选播服务器D= (10, 15, 20, 25) , 服务器利用率设置为P10=0.5、P15=0.4、P20=0.3、P25=0.2 , 延时范围为10～20随机数, 剩余带宽率范围为 (0～1) 随机数, 适应度函数中调整系数设为Kt=3、Kb=1.5、Kp=1 。
4 结 论
本文针对选播路由算法的特点, 对遗传算法中的交叉、变异操作以及交叉率Pc和变异率Pm作了改进, 使之能更有效地满足选播路由中的最大剩余带宽、最小传输延时和最快服务器响应速度, 从而提高选播路由的服务质量。
摘要：随着基于IPv6选播应用的研究与发展, 选播路由算法已成为选播服务质量的关键。以遗传算法为基础, 提出一种改进的交叉、变异遗传操作, 在克服传统算法中早熟现象的基础上, 加快了收敛速度;同时本算法以延时、带宽和服务器负载作为选择操作的依据。仿真结果显示, 该算法能够在合理利用网络资源的同时找到最优解。
关键词：选播,遗传算法,服务质量
参考文献
[1]张丽, 贾维嘉, 严伟, 李晓明.使用特殊复合距离的选播路由算法[J].计算机研究与发展, 2005, 42 (1) :252-258.
[2]Massanori Sugisaka, Xinjian Fan.Adaptive Genetic Algorithm with a Cooperative Mode[C].Proceedings of IEEE International Symposium on Industrial Electronics, 2001.
[3]马炫.求解K条最优路径问题的遗传算法[J].计算机工程与应用, 2006, 12:100-101.
[4]邝航宇, 金晶, 苏勇.自适应遗传算法交叉变异算子的改进[J].计算机工程与应用, 2006, 12:93-96.