多播路由协议论文

多播路由协议论文（共5篇）

多播路由协议论文 篇1

摘要：多播是一种面向群组计算的通信传播方式, 它使用单一的源地址把数据发给一组主机。如何在移动自组网中实现有效的多播路由技术是当前此领域研究中亟待解决的问题。针对基于树和网格结构多播路由协议, 它们各自的能量消耗进行了分析, 给出相应的能量消耗区间。最后结合分析所得的结论, 提出一个新的多播路由协议。

关键词：无线自组网,组播,能耗

移动AdHoc网络[1] (MANET—mobileAdHoc network) 是指一组无线移动节点组成的多跳的, 临时性的、无基础设施支持的无中心网络。多播是一种面向群组计算的通信传播方式, 它使用单一的源地址把数据发给一组主机, 将信号从信源节点同时传送到多个目的节点, 良好的多播路由算法能够控制数据包传送的延迟时间与带宽的使用率以及能源的利用率。在这样的网络中, 节点的频繁随机性运动将导致网络拓扑结构呈现出时变特性, 因此路由算法是AdHoc网络研究中的一个核心问题和难点问题。

1基于树和网格的多播路由协议

现有的无线自组网多播协议按照参与路由的节点构成的网络拓扑结构分为两大类型基于树的协议和基于网格的协议。

树型 (Tree-based) 结构在任意两点之间只有一条路径, 转发多播数据包的带宽比较节, 具有高的转发效率, 但易受自组网拓扑结构动态变化的影响, 树的结构很容易被破坏, 容易出现分割现象, 需要不断根据网络的变化对树进行重构, 维护树结构的开销较大, 协议的鲁棒性不佳。其典型的协议有[2,3]等

网格 (Mesh-based) 结构在任意两点之间存在多条路径, 这些冗余的路径提高了网络的动态适应能力, 健壮性好, 不需因为少量链路的失效而重新配置多播网结构, 路由维护开销少, 代价是数据经过多条路径转发, 浪费了网络带宽, 增加了网络的负担, 消耗了节点的能量, 转发效率低。其典型的协议有:ODMRP[4]、CAMP[5]等。

2基于不同拓扑结构的能量分析

有研究结果表明基于网格的多播网在结构性能上要优于基于树的多播网, 但在能耗上要远差于基于树的协议。在这节, 我们给定相应的网络模型, 对基于树和网格的组播协议, 进行相应的定量分析。

在能量模型 (一阶无线电模型) [6]中, 我们把每个多播信息所消耗的所有能量为定义为E, E包括传输所消耗能量 (ETX) , 以及接收所需要的能量 (ERX) 。只考虑数据包的简单的情况。根据一阶无线电模型得到, E=ETX+ERX=NTXeTX+NRXeRX。其中NTX和NRX是传输和接收的数量, 而eTX和eRX分别对应在无限链路中传送和接收每单位多播信息所需的能量消耗。如果我们假设的eTX和eRX都相同, 并定义为e, 那么能源消费总量E= (NTX+NRX) ×e。将F+, F1, F0分别定义为有一个以上的接收器的树节点, 只有一个接收器的树节点, 以及没有接收器的树节点。因此, 可以得到所有树节点数量F=F++F1+F0。在多播树中, NTX是除去树的叶节点数后整个树的节点数 (根和中间节点) 而NRX=∑iEF+Fi+F1, fi表示节点i的邻居节点数。在网格多播中, NTX是整个树的节点数 (根和中间节点和接收节点而是所有节点的邻居节点数

2.1网络模型范例分析

考虑一个静态AdHoc网络, 由64个节点放置在一个8×8网格组成, 图1, 图2分别为两个由8个成员节点构成的不同拓扑结构的多播图。图1显示了从根节点到接收节点的基于树的多播树, 图2显示了具有一跳冗余路径的网格多播。图中并不包括那些最终为接受节点所抛弃的数据传输的链路。为简单起见, 假设无线电传输距离以及传输功率是固定的, 不能动态控制。节点密度设定为4, 也就是说, 无线电传输范围仅限于一个节点的四个直接邻居:东, 西, 南, 北。如果节点密度设定为8时, 则一个节点可以与所有周围8个方向的邻居链接。在图1, 图2所示内容中, 实线代表每一棵树的联系, 虚线代表冗余链接。

2.2 范例的能量比较

基于先前所提的能源公式, 比较基于树和网格的能源效率。例如, 分别考虑图1和图2所示的多播图。Etree (图1所示) 的Etree= 40e, 其中NTX是14 ( 20树节点, 6叶接收节点) 而 NRX是26 (4×4+10) 。由8个成员组节点构成成的网格多播中 (图2所示) , 可估计Emesh = 94e , 其中NTX是20 (20树节点) 而 NRX是74 (20个节点的邻居节点总数) 。由上可知, 可以得出结论认为, 网格为基础的多播 (Em/Et =94e/40e) 比树基多播的多播多消耗2.35倍的能量。图3显示了节点密度为4的情况下, 不同多播结构的能量消耗 。总之, 多播网格比多播树消耗约2—4倍以上的能量。另外一个重要点是, 高节点连接或密集网络使得以网格为基础的多播协议产生了更多的冗余的联系。

2.3 能量消费的定量分析

在本节中, 对网格和多播树的能源消耗总量进行定量分析。考虑静态Ad Hoc网络由K2个节点分布在K×K的网格中。对于K×K的网络中, 分析边界情况的话, 一共有三种情况:

2.3.1 完全多播组

这个时候在整个网络中的所有节点都是多播成员, 即多播组成员数量为K2个。

2.3.2 边缘多播组

在能源消耗总量与完全多播组一样的情况下最差的节点网络结构形式。发生这种情况时, 成员节点位于网络的边缘。这时候成员节点间具有最长的网络路径。

2.3.3 最小能量消耗多播组

这个时候, 整个多播组只由成员节点所构成。

根据范例中所得到的结果, 我们给出了下面两个定理, 分别定义了, 在一个静态的Ad Hoc网络的基础上, 以树为基础和网格为基础的多播中能源消耗总量的上下界。

定理1:在节点连接度为f的静态Ad Hoc网络的k×k拓扑结构, 以树为基础的多播传送总的能源消耗Etree的范围为, (2n-O (n1/2) ) e ≤Etree≤ (2 k2-O (k) ) e, 其中n是成员节点数量, e是以通过链接传送或接收多播信息所需的能量消耗。

定理证明:在给定的节点连接度为f的静态Ad Hoc网络的k×k拓扑结构中, 可以将a的情况能量消耗视为以树为基础结构的多播方法的能量消耗的上限。在一个完全多播树中, NTX= k2-O (k) , 其中O (k) 是具有链接节点数量少于f的边界节点数 , NRX =k2 -1 + O (k) , 因此, Etree= (NTX + NRX) e≤ (2k2-O (k) ) e。在最小能量消耗多播组情况发生情况下, 我们可以得到能量消耗的下限, 这时有NTX=n-O (n1/2) , NRX=n-1+O (k) 。因此 Etree≥ (2n-O (n1/2) ) e。

定理2在节点连接度为f的静态Ad Hoc网络的k×k拓扑结构, 以网格为基础的多播传送总的能源消耗Emesh的范围为, ( (f+1) n-O (n1/2) ) e≤Emesh≤ ( (f+1) k2-O (k) ) e, 其中n是成员节点数量, e是以通过链接传送或接收多播信息所需的能量消耗。

定理证明:在给定的节点密度为f的静态Ad Hoc网络的k×k拓扑结构中, 可以将完全多播树的能量消耗视为以网格为基础结构的多播方法的能量消耗的上限。在一个完全多播树中, NTX = k2, NRX = fk2-O (k) , 其中O (k) 是具有链接节点数量少于f的边界节点数, 因此, Emesh=

(NTX + NRX) e≤ ( (f+1) k2-O (k) ) e。在最好情况下, 也就是网格多播只由成员节点构成的情况下NTX= n, NRX =fn-O (n1/2) 。因此Emesh ≥ ( (f + 1) n-O (n1/2) ) e。

根据定理1和定理2, 可以得出结论,

Emesh/Etree≈ (f+1) /2, 节点的连接度f, 通常是要远远大于2 (否则, 网络会发生隔离) 。因此, 基于上述的分析, 在相同的网络条件下, 基于树的多播结构在能耗上要比基于网格的结构来的节能。

3 多播协议ABTM的提出

根据上述分析的结果, 我们提出一种新的多播协议, 后备树多播——Alternative Backup Tree Multicast (ABTM) , ABTM利用一个主树和后备树来构建相应多播组。当主树无法使用或超载, 立刻使用后备树来承担的主树的责任, 同时立刻构造一个新的后备树。 组成员中具有最大的剩余电池能量的节点被选中作为新的后备树根节点。这与根节点定期改为一个中心网络附近的节点, 实现从根节点向所有接收节点最短的平均跳距离[7]的方法有所类似。使用两棵树的方式可以主要树发生链接错误时, 通过立即切换到后备树, 减少等待时间的目的。树更换的方法也有助于缓解共享树多播所固有的能源平衡问题。 同时, 基于后备树的结构在路径的重建过程上也能节省相关的网络开销。

ABTM协议构建思想为在ABTM 协议中接收节点可以通过定期向rp和ra发送join message来构建两棵树:主树以及替代备份树 (primary tree and alternative backup tree) 。rp、ra分别为构造主树以及替代备份树的根节点。join message包含的信息, 有相应的节点剩余的电池能量, 利用它可以选择新的替代树的根节点。这两个根源节点通过信息遍历 (称为树的建造和维修的程序) 遍历的路径独立构造多播树 。当某个节点打算发送一个多播数据包, 转发数据包到rp;然后rp沿着主树的链接向成员节点传送信息[8,9] (称为多播信息传递程序) 。当节点间的链接于节点移动而被损坏, 或节点的剩余能量降低到预定的阈值, 使得主树的路径失效, 这时立刻使用后备树的路径来代替原有的主树路径传播, 同时立刻开始一个后备树的更新过程, 即rp发送一个控制信息到ra, 通知后备树准备替代主树。在收到控制信息后, 后备树的根节点 (ra) 选择一个新的节点 (r’a) 作为新后备树的根节点, 在选择过程中以成员节点的剩余电池量作为选择的约束条件, 挑选节点剩余能量最大的作为根节点。然后, ra通知发送端 (s) 和所有成员包括r’a更换树。当每一个成员收到ra传送的控制讯息后, 向ra (此时的ra即为新的rp) 和r’a发出了一个加入请求消息, 从而构建出新的主树和后备树, 完成路径的修复重构过程。

4 结论和今后的工作

虽然, 在结构上来看, 基于网格的多播协议具有更好的鲁棒性, 但通过对基于树和基于网格的多播结构的能量分析, 我们可以清楚的看到, 基于树的结构在多播协议中具有良好的节能性能。因此结合两者相应的有点, 我们提出了ABTM协议, 通过这个协议我们可以平衡能量消耗与协议鲁棒性, 从而有效的来延长整个网络的生存时间。后续研究将在上述研究基础上深入和完善, 包括ABTM协议在功率控制及构建多播树时造成的网络延时等各种因素的优化改进等, 使路由协议能更充分表现出优异的性能。

参考文献

[1] Perkins C.Ad Hoc networks.Reading, MA:Addison Wesley, 2000

[2]Royer E M, Perkins C E, Multicast operation of the Ad Hoc on-de-mand distance vector routing protocol.Proceedings of ACM/IEEE MOBICOM99, Seattle, WA, Aug.1999:207—218

[3]Wu C W, TayY C, Toh C K Ad.Hoc multicast routing rrotocol utilizing Increasing id-umberS[AMRIS]Functional Specification.In-ternet draft, Nov.1998

[4]Lee S J, Su W, Gerla M.On demand multicast routing protocol (ODMRP) for Ad Hoc networks.Internet raft, draft-ietf-manet-odm-rp02.txt.Jan2000

[5]Garcia-Luna-Aeeves J J, Madroga C E.The core-assisted mesh proto-co.IEEE Journal on Selected Areas in Communications, 1999, 17 (8) :1380—1394

[6]Heinzelman W R.Chandrakasan A, Balakrishnan H.Energy effi-cient communication protocols for wireless microsensor networks.In Proc of the Hawaii Int Conf on System Science, 2000:3005—3014

[7] Chiang C C, Gerla M, Zhang L. Adaptive shared tree multicast in mobile wireless networks. In: Proc of the IEEE Global Telecomm Conference (GlobeCom ’98) , 1998; 3: 1817—1822

[8] Ji L, Corson M. A lightweight adaptive multicast algorithm. In: Proc of IEEE Global Telecomm Conference (GlobeCom ’98) , 2:1998; 1036—1042

[9] Lee S, Gerla M, Chiang C. On-demand multicast routing protocol.In Proc. of IEEE Wireless Communications and Networking Conference (WCNC ’99) 1999: 1298—1302

多播路由协议论文 篇2

目前,移动自组织网MANET(Mobile Ad Hoc Network)成为无线网络研究的一个热点。构建MANET的主要目的是通过一群带有无线收发装置的移动节点组成一个临时性、无基础设施的移动网络[1],该网络具有临时性、多跳路由等特点。

在MANET中,由于节点的通信范围受限,需要多跳方式向其他节点传输数据,并且节点随机移动,网络拓扑变化频繁,这使得在MANET中建立稳定、可靠的路由协议成为一项挑战性的工作。为此,研究人员针对MANET的路由协议进行了大量的研究工作,提出不同策略的路由协议[2,3,4,5,6]。

通常,MANET中的源节点需要向多点传输数据,即一点对多点,就采用了多播(Multicasting)。由于多播是向多个节点传输同样的数据,降低了通信消耗,包括链路带宽以及传输时延。依据路由协议的特性,可将现有的多播路由(multicast routing)协议分为基于树形(tree-based)路由协议[7]、基于mesh路由协议[8,9]以及混合路由协议。

基于树路由协议在源节点至目的节点间建立树型拓扑。典型的基于树路由协议如自组织多播路由协议AMR(Ad Hoc Multicast Routing)、多播按需距离矢量路由协议MAODV(Multicast Ad Hoc on demand Distance Vector)[10]、可靠多播RM(Reliable Multicast)。而基于mesh的多播路由协议在两节点间建立多条路径,即使链路失败,也没有必要重新计算mesh结构,典型的有CAMP(Core-Assisted Mesh Protocol)、按需组播ODM(On-Demand Multicast)以及DCMP(Dynamic Core based Multicast)路由协议。

尽管基于mesh路由协议能够在源节点至目的节点间建立多条路径,但是这是以能量消耗为代价的。然而,在MANET中,每个节点的能量是受限的。在设计路由协议时,应考虑节点的能量受限的特性。因为一旦节点能量耗尽,链路就断裂,缩短了网络寿命,必然会引用数据传输中断,增加了数据传输时延,降低了数据传输的效率。

为了最大化网络寿命,应以最小的能量消耗实现有效的数据传输。为此,研究人员也提出面向节点能量消耗的路由协议,如最小传输功率MTP(Minimum Total Transmission Power)路由[11]、最小-最大电池消耗MMBC(Min-Max Battery Cost)路由[12]以及可选择的最大-最小传输能量CMMBC(Conditional Max-Min transmission Battery Capacity)路由[13]。

为此,本文考虑节点能量信息,并利用树型拓扑以及多播路由特性,提出基于树的能量感知的多播路由MTMR(Energy of node Tree-based Multicast Routing)协议。MTMR协议首先节点考虑节点的能量,若节点能量小于门限值,则不允许该节点参与数据转发。然后,将节点构建3种不同树,源节点依据这3种树向目的节点传输数据包,提高了数据传输效率。

1 能量消耗模型

MTMR协议考虑了节点的传输能量信息,节点在传输、转发以及接收数据时,均需消耗自身能量。无线电能量消耗主要由两部分组成:运行电子元器件、功率放大器所消耗的能量和接收器所消耗的能量。为了在两节点间传输q bit的数据信息,且两节点间的距离为d,消耗的能量为:

其中,Eelec表示运行发射器或接收器固定的能量消耗,Efrris表示自由空间传播模型单位功率放大器的能量消耗。

相应地,对于接收q bit的数据包,消耗的能量:

节点依据式(1)或式(2)计算自己剩余能量。

2 MTMR协议

MTMR协议是属于能量感知协议,提高了多播路由的稳定性,同时引用基于多树路由协议的理念,进而提高数据传输的效率。为此,假定网络内所有节点随机划分为三类,分别为组1(Group-1)、组2(Group-2)、组3(Group-3)。相应地,利用Group-1、Group-2、Group-3节点分别构建3种树Tree-1、Tree-2、Tree-3。

此外,每节点保持两个表:邻居表(Neighbouring table)和多播路由表(Multicast routing table)。节点通过周期地交互Hello消息建立邻居表。邻居表用于保存邻居节点的信息,包括邻居节点的ID、位置信息。多播路由表用于保存传输数据的路径,格式如图1所示。

其中,Source_ID、Destination_ID分别标识源节点、目的节点。Route_class用于标识路由组Group-1、Group-2、Group-3。Route_class=1、2、3分别代表Group-1、Group-2、Group-3。Next_node表示用于转发数据的下一跳节点。

2.1 路由发现过程

当源节点需要向目的节点发送数据包时,就向邻居节点广播路由请求RREQ(Route Request)控制包。RREQ控制包内包含源节点、目的节点以及路径信息(Path Information)等。

当节点接收了RREQ控制包,就将自己剩余能量E与门限值Eth进行比较,如果大于Eth,就存储RREQ,并重播RREQ,致使RREQ控制包传输得更远。同时,将自己的ID加入到RREQ控制包的路径区域(Path Information)。

接收了控制包RREQ时,就将用于向源节点转发路由回复控制包RREP(Route Reply Packet),RREP控制包携带了、源节点、目的节点、返回路径(Reverse Path Information)、Route_Class。其中,Reverse Path Information记载了传输RREP的路径信息。

2.2 控制包传输过程

邻居节点不断向目的节点转发RREQ控制包,直到目的节点接收。当目的节点接收到不同树的RREQ控制包后,目的节点将沿着该树向源节点传输回复RREP控制包。数据传输如图2所示。

接收到RREQ控制包后,目的节点P、Q、R将这3个树的最后一跳节点作为传输RREP的上级节点,如图2(b)所示。节点P、Q、R选择I作为TREE-1的上级节点、H作为TREE-2的上级节点以及J作为TREE-3的上级节点。图2(c)显示了基于多树的数据传播过程。

3 性能分析

3.1 仿真参数

利用网络仿真软件NS2.3.5构建仿真平台[14]。考虑1 000 m×1 000 m仿真区域,20~80个移动节点随机分布于仿真区域。同时,选择random way point作为移动模型,每个节点随机地选择移动方向,移动速度从1~25 m/s间选择。节点的通信范围为150 m。此外,随机选择移动节点作为源节点和目的节点。数据包的大小225 B。仿真时间为10 000 s。

在分析仿真数据时,考虑的场景:移动节点的速度为20 m/s,移动节点数从20~80变化;考察端到端传输时延、数据包丢失率传输率以及控制路由开销作为评估路由协议的性能指标。

3.2 数值分析

为了更充分地分析MTMR协议性能,选用AODV进行同步仿真,并进行性能比较。选择AODV协议作为参考,原因在于:AODV是经典的按需路由协议,其也是采用RREQ控制包发现路由。在路由发现阶段,当源节点需要向目的节点传输数据时,源节点先广播路由请求RREQ控制包,含有目的节点地址、广播ID以及遍历的跳数。接收到RREQ数据包后,邻居节点检查自己是否有至目的节点的路由,如果有,就向源节点回复RREP控制包;否则,邻居节点就转播RREQ。图3描述了AODV协议RREQ和RREP的传输过程。

(1)某场景路由性能

图4(a)所示,MTMR的端到端传输时延比AODV下降了33.928%。图4(b)所示,MTMR的数据包丢失率下降了55.655%。图4(c)显示MTMR和AODV归一化的路由开销,这说明MTMR在提高端到端传输时延、数据包丢失率时,并没有增加路由负担。

(2)能量性能分析

本次实验分析与节点能量相关的网络稳定时长和网络寿命。其中,稳定时长等于从网络初始开始计算第一节点失效时所经历的时间。而网络寿命数值等于网络内最后一个节点失效时所经历的时间,时间越长,网络寿命越长。

表1列举了10次测试的实验数据。从表1可知,AODV、CAMP、DCMP和MTMR协议的稳定时长分别为969 s、1 355 s、1 432 s和1 717 s,而网络寿命分别为5 535 s、5 673 s、8 638 s和8 640 s。这些数据表明,提出的MTMR协议能够有效地延长稳定时期,扩展网络寿命。

4总结

本文针对移动自组织网络移动节点能量受限问题,提出基于树的能量感知的多播路由MTMR协议。MTMR协议首先利用无线电能量消耗模型,计算移动节点的剩余能量。若移动节点的剩余能量小于门限值,则不参与路由,降低了因节点能量耗尽而中断路由的概率。同时,MTMR协议引用树,源节点依据3种树实现多播路由。仿真结果表明,提出的MTMR协议在端到端传输时延、数据包丢失率以及路由开销性能方面有显著的提高。

摘要：由于移动节点能量耗尽严重影响了移动自组织网(MANET)路由性能,有效地使用移动节点的能量是非常重要的。为此,提出基于多树的移动自组织网多播路由协议(MTMR)。MTMR协议先计算移动节点能量,将能量低于门限值的节点不参与路由。然后,将参与路由的节点构建不同的树,源节点通过这些树向目的节点传输数据,从而实现多播路由。仿真结果表明,提出的MTMR协议有效地提高了数据传输率,降低了端到端传输时延。

DTN多播路由算法研究 篇3

关键词：DTN,路由,算法,多播

0前言

DTN是延迟容忍网络 (Delay Tolerant Network) [1]的简称, 由K.Fall等科学家于2002年在ICIR会议上提出来的。是从具有延时容忍特性的一类网络中抽象出来的, 最初来源于对星际因特网IPN (Inter-Planet Network) [2]项目的研究, 把节点间的长延时、高不对称性和间歇性连接作为主要的场景加以考虑。多播服务支持一组用户的数据分发, 许多潜在的DTN应用是基于多播方式的 (例如军事战场、灾难营救过程) , 通过多播技术, 能够提高网络的资源利用率, 降低通信成本, 节约带宽。多播技术在因特网和移动自组网中已有深入广泛的研究。但是对于DTN, 由于频繁网络断开的特性使得DTN中的多播成为一个难题。网络设计者若把适用于Internet中多播路由 (例如MOSPF和DVMRP) 或ad hoc网络中的多播路由 (例如AMRoute和ODMRP) 直接应用于DTN环境, 将面临很大的障碍和挑战。因此, DTN多播需要新的定义和路由设计, 本文针对DTN的特点, 对DTN的多播路由算法进行论述。

1 DTN概述

当前, Internet在互连全球异构的网络上取得了巨大的成功, TCP/IP协议已成为互连网络的事实标准。但是随着计算机技术, 微电子技术的发展以及军事和其他领域研究的需要, 越来越多的新型网络开始出现, 如陆地移动网络、外来媒体网络、军事无线自组织网络和无线传感网络等。这些受限网络中存在共同的特点:高延迟、低数据率、间歇性连接、缺少端到端路径、能量和存储受限, 给传统的基于TCP/IP协议的端到端通信的Internet技术带来严峻的挑战。为了使这些受限网络可以和现有的因特网互联, 并改善网络的传输性能。K.Fall等科学家于2002年在ICIR会议上提出了延迟容忍网络 (Delay Tolerant Network, DTN) 的架构。

不同于现有的网络, DTN的主要特征表现为:高延迟、低数据率、连接中断频繁以及较长的排队时间等。对DTN来说, 传输率可能是比较小的, 延迟相对来说却比较大, 上行和下行的数据率很大程度上不对称的。在一些特殊的情况下, 单向链路的可能性也是存在的, 如在军用中同一些需要隐蔽的装备进行通信。同时, 在DTN中, 连接中断频繁, 而且中断的原因也不一定全都是由于出错导致的。尤其是在无线移动网络中, 连接中断的原因主要来自节点的运动和低占空比操作。在一些传统的分组网络中, 消息的排队时间经常对整个延时起决定性作用的。但在这些网中, 排队时间通常是非常短的, 一般都远远小于1秒钟。而且, 当下一个节点无法连接时, 数据包就会丢失。相比之下, DTN的连接断开情况比较常见, 节点的排队时间相对而言比较大, 有可能达到几个小时甚至几天。[3]

2 DTN多播服务技术应用与发展

多播服务支持一组用户的数据分发。随着通信网络的发展以及通信研究领域的深入, 许多潜在的DTN应用是基于多播方式的, 例如在军事战场中, 利用多播技术可以将控制中心的命令快速、可靠地发送到各个现场指挥基地, 实现士兵之间的有关战场周边环境信息的共享;在灾难营救过程中, 通过多播技术, 可以快速地实现营救工作者之间共享伤者有关的信息以及现场可能存在的一些潜在危险。[4]另一方面, 利用多播技术能够提高网络的资源利用率, 降低通信成本, 节约带宽。多播技术在因特网和移动自组网中已有深入广泛的研究。但是对于DTN, 由于频繁网络断开的特性使得DTN中的多播成为一个难题。网络设计者若把适用于Internet中多播路由 (例如MOSPF和DVMRP) 或ad hoc网络中的多播路由 (例如AMRoute和ODMRP) 直接应用于DTN环境, 将面临很大的障碍和挑战。首先, 在DTN多播消息传输过程中, 保持多播结构 (树形或者是网状结构) 的连通性是困难的。第二, 由于DTN自身的特点, 多播结构不断发生变化而引起中断从而导致消息传输时发生频繁失败或大的端到端延迟。第三, 传统多播路由方案的设计是基于网络连通性较好的假设, 而这种假设在DTN环境中是不可能的。所以, DTN多播不仅要求新的多播定义, 而且带来了路由设计的新问题。

3 DTN多播路由

现有的DTN多播路由算法从大的方向看, 可以大致分为域内多播路由算法和域间多播路由算法。

3.1 域内多播路由算法

域内多播是指在属于同一个管理域内进行一组用户的数据分发。目前, 主要的DTN域内多播路算法, 根据寻路路由机制的不同, 大概可分为2类:基于知识的多播路由算法和基于概率的多播路由算法。[4] (1) 基于知识的多播路由算法主要有:①U-Multicast (Unicast-based Multicast) 是一种基于单播的简单的DTN多播路由算法, 它通过使用多个从源节点到目的节点的单播服务来实现组播数据传输;②ST-Multicast (Static-tree-based Multicast) 是一种基于静态树的多播路由算法;③DTBR (Dynamic Tree-Based Routing) 是一种基于动态树的多播路由算法, 每个中继节点都要计算自己的多播树;④OS-multicast (On-demand Situation-aware Multicasting) 是在DTBR的基础上发展起来的。针对DTBR的不能很好地动态利用当前可行路径的缺陷而提出的改进算法;⑤CAMR (Context-Aware Multicast Routing) 是基于节点密度的自适应的多播路由算法, 它主要利用了网络一些额外的信息, 如节点的位置、节点的速度等来进行路由选择。 (2) 基于概率的多播路由算法主要有:①EMR (Epidemic Multicast Routing) 将Vahdat和Becker的Epidemic算法的设计思想引入到容断网络的多播路由中;②EBMR (Encounter Based Multicast Routing) 是在Prophet基础上发展而来的。Prophet是一种采用相遇或投递转移的历史信息, 为每个节点估算将数据成功转发到目的节点的概率, 即到达概率, 节点只会将数据转发给比自己到达概率高的节点。在转发策略上, EBMR对Prophet作了一些改进:如果下一跳节点的到达概率 (delivery predictability) 大于设定的门限值, 上游节点就会向该下游节点转发消息;如果没有找到合适的下一跳节点, 该节点缓存束信息, 直到等待时间 (wait timer) 到达极限值。

基于知识的多播路由算法依据一定的网络知识做出路由选择, 这些网络知识主要涉及到网络拓扑、节点间的连通模式、节点的地理位置信息、节点的运动时刻表等等。并且基于知识的多播路由算法假定:网络能够预先发现一定的相关网络知识。所以其鲁棒性及扩展性相对较差。比较适用于节点相对比较集中或者节点密度较大的情况。基于概率的多播路由算法不需要维护任何网络拓扑信息以及一些网络的额外知识, 实现比较简单, 而当节点较为稀疏或节点的位置变化较为剧烈时, 基于概率的路由算法仍可获得较好的路由效果。EBMR不依赖于任何路由发现过程, 属于一种基于概率的多播路由算法。这种多播路由算法, 有比较广的适用范围。

3.2 域间多播路由算法

在不同管理域间进行一组用户的数据分发叫做域间多播。目前, 关于容迟网络路由的研究大部分集中在单域即域内消息传递的问题上。然而, 许多实际应用场景, 特别在发展中区域, 往往需要在多域间进行信息传递。目前, 实现域间通信的多播路由算法主要有:①SHIM是一种可扩展 (scalable) 的分等级的域间多播路由方案。在SHIM中, 组长 (域头) 形成高层 (upper layer) , 各个组除组长外其余的节点形成低层 (lower layer) 。多播源节点发送消息包到它的组长, 然后由组长分发要发送的数据包给所有包含兴趣接收点的组的组长。该方案的主要缺点是它利用DTBR或者OS-Multicast作为域内多播路由方案。因为DTBR或者OS-Multicast采用类似于DSR的路由决策算法进行组长之间的路由发现, 所以, 这两者方案在节点密度比较稀疏DTN环境下, 适用性不强。②基于摆渡的域间多播 (FBIMR) :FBIMR借助于特定的叫“摆渡”的节点完成域与域之间的消息通信[5], 而域内节点间的通信则采用增加冗余消息复制的基于相遇 (EBMR2) 的多播方案。该机制采用“摆渡”节点在域与域之间中转数据, 可以有效避免过多的能量损耗和网络资源负担, 但需要预先规划节点运动路径或要求节点移动可控。

4 总结

DTN是一种新型的无线网络体系结构, 至力于解决频繁间断网络中的数据通讯问题。许多潜在的DTN应用是基于多播方式的, 由于DTN高延迟、间歇性连接、资源受限等特点, 其多播技术需要新的定义和路由设计。本文对DTN多播路由算法目前的研究进展进行论述, 综合分析了目前存在的DTN多播路由算法, 在这基础上, 将进一步深入研究, 设计更合理有效的路由算法。

参考文献

[1]Fall K.A delay-tolerant network architecture for challenged Internets[J].In:Proc.of the 2003 Conf.on Applications, Technologies, Architectures, and Protocols for Computer Communications.Karlsruhe:ACM, 2003:27-34.

[2]Akyildiz IF, Akan B, Chen C, Fang J, Su W.Inter-Planet Network Internet:State-of-the-Art and research challenges[J].Computer Networks, 2003, 43 (2) :75-112.

[3]郑炜.延迟容忍网络的相关问题研究及仿真[D].上海:上海交通大学, 2007.

[4]尤齐, 徐昌彪, 毕元梅, 祁彦.容断网络中的组播路由算法研究[J].数据通信, 2008 (03) .

多播路由协议论文 篇4

随着网络通信技术的发展, 视频点播、远程教育、网络会议等多媒体应用越来越广泛, 建立一种高效的、有QoS保障的数据通信机制显得尤为重要。基于这种需要, 多播技术已被应用到多媒体通信中, 由于多播传输的多为多媒体数据, 数据量大而且有着相对严格的QoS要求, 因此, 为了寻找合适的多播路径, 原有的点对点路由算法已经不能满足要求, 需要针对多播的特点设计专门的组播路由算法, 找到满足业务QoS要求的源结点到目的结点的传输路径。求解带有QoS约束的多播路由算法被等效为构造一棵最小代价的多播树——斯坦纳最小树SMT (Steiner minimum tree) [1], 源节点的数据能够通过这棵多播树传送到每一个目标节点。寻找SMT的问题已经被证明为一个NP问题[2], 针对这个问题提出了很多近似算法[3,4,5]。由于应用背景的复杂性, QoS多播路由问题仍然是一个充满挑战性的问题。

遗传算法是一种模拟生物界自然选择和遗传机制, 高度并行、随机和自适应的新型最优化搜索算法, 广泛应用于解决各种组合优化问题。Zhang 等[6]对延时约束代价最小多播路由问题提出了一种遗传算法, 但它假定所有多播目的节点的延时约束相同, 限制了算法的应用范围。Munemoto 等[7]建议了可变长度的染色体编码, 是较好的编码方案, 但该算法不适合大型网络和实时性较强的网络。文献[8]中Wang 等针对带宽时延约束代价最小的多播路由问题提出了一种效率较高的遗传算法, 但其交叉和变异算法还是过于复杂。本文利用遗传算法来解决多约束的多播问题, 可同时考虑可变的多个QoS参数, 根据具体需要选择参数个数, 使用适应性惩罚函数方法来处理不可行个体, 既保存不可行解的有用信息, 又对不可行解施加选择压力, 提高了搜索效率。

1网络模型和问题描述

多媒体通信网络可表示成一个有向图G (V, E) , 其中V表示节点集, E表示连接节点的通信链路的集合。图G (V, E) 中包含n=|V|个节点和L=|E|条链路。对任意节点vi∈V (1≤i≤n) 定义以下几个QoS参数:可用CPU资源c (vi) 、缓存资源b (vi) 、排队延迟t (vi) 、包丢失率函数packet-loss (vi) 和发送延迟τ (vi) ;对每条传输链路eij= (vi, vj) ∈E (1≤i≠j≤n) 定义以下几个QoS参数:可用带宽w (eij) 和传输延迟δ (eij) 。

设p (ui, uj) 表示图G (V, E) 中源节点ui到目标节点uj的一条路径, 则可以定义该条路径的以下QoS参数:

带宽:

bandwith (p (ui, uj) ) =min{w (emn) , emn∈p (ui, uj) }

可用CPU资源:

cpu-resourse (p (ui, uj) ) =min{c (vi) , c (vi) ∈p (ui, uj) }

缓存资源:

buffer (p (ui, uj) ) =min{b (vi) , b (vi) ∈p (ui, uj) }

传输延迟:

$delay(p(u{}_i,u{}_j))=[{\displaystyle \sum _{v{}_i\in {\rm P}(u{}_i,u{}_j)}(}t(v{}_i)+\tau (v{}_i))+{\displaystyle \sum _{e{}_{ij}\in {\rm P}(u{}_i,u{}_j)}(}\delta (e{}_{ij}))]$

包丢失率:

$packet-loss(p(u{}_i,u{}_j))={\displaystyle \sum _{v{}_i\in p(u{}_i,u{}_j)}p}acket-loss(v{}_i)$

在网络G (V, E) 中, 节点集U={u0, u1, …, um} (U⊆V) 需要进行多媒体多播通信, 并且需要以下资源:CPU资源C、缓存资源B和带宽资源W, 要求任一源节点到任一目的节点的端到端延时不超过Δ, 包丢失率不超过θ。

QoS多播问题就是寻找一棵树T (X, F) , U⊆X⊆V, F⊆E, 并满足以下条件:

(1) ∀vi∈X c (vi) ≥C, b (vi) ≥B

(2) ∀eij∈F w (eij) ≥W

(3) ∀ui∈U ∀uj∈U and ui≠uj

delay (p (ui, uj) ) ≤Δ packet-loss (p (ui, uj) ) ≤θ

(4) 该多播树的代价函数cost () 最小, 代价函数定义如下:cost$({\rm T})={\displaystyle \sum _{v{}_i\in X}h}(v{}_i)+{\displaystyle \sum _{e{}_{ij}\in F}{\rm H}}(e{}_{ij})$, 其中h、H分别表示节点和链路的代价函数。定义如下:

$h(v{}_i)=\frac{k{}_{1}C}{c(v{}_i)}+\frac{k{}_{2}B}{b(v{}_i)}{\rm H}(e{}_{ij})=\frac{k{}_{3}W}{w(e{}_{ij})}$

2QoS多播路由的遗传算法

2.1多播路由的编码策略

在遗传算法中, 如何将问题的解转化为编码表达的染色体是需要解决的首要问题。本文采用二进制编码的形式, 每个染色体解由一个二进制串来表示。其中, 二进制串中每一位代表图G (V, E) 的一个节点, 因此每个染色体字符串的长度都为n=|V|。用G′ (V′, E′) 代表相应的染色体解s, 设函数bit (s, k) 代表s的第k位, 则G′ (V′, E′) 由以下方式构造:

如果bit (s, k) =1, 则vk∈V′;

如果bit (s, k) =0, 则vkV′;

如果vi∈V′, vj∈V′, 并且 (vi, vj) =eij∈E, 则eij∈E′。

用T′i (X′i, F′i) 表示G′ (V′, E′) 的最小生成树, 可以由Prim算法求出, 如果在树T′i中存在不属于U的叶子节点, 则从树T′i中删除这些节点和他们相邻的边。记这棵树为Ti, 则Ti即为染色体s所代表的多播树。

代表解s的图G′ (V′, E′) 有可能是不连通的, 如果所有参与多播的节点都位于G′ (V′, E′) 的某一个连通的子图之内, 则该解是可行的, 否则需要加上一个额外的惩罚函数。

2.2预处理

在选择初始种群之前, 可先除去所有不满足带宽约束的链路, 即去除不满足条件 (1) 的节点, 以及所有不满足条件 (2) 的链路。经过精简处理后, 网络可能不再是连通图, 而是包含几个连通的子图。如果所有参与多播的结点都位于同一连通子图, 则表明网络满足基本的约束限制, 选择此连通子图作为算法研究的基图;否则表明网络不能满足带宽约束条件, 这时与应用协商, 放宽约束限制以便重新处理。

上述预处理机制, 简化了算法设计的难度, 同时也优化了算法的性能, 减少了算法搜索的空间。

2.3适应度函数

适应度函数是遗传算法用来判断个体好坏的标准, 本算法中个体是一棵覆盖源节点和目的节点的子树, 其代价越小, 表明树的性能越好。性能好的个体适应度大;性能差的个体适应度小。本算法的适应度函数定义为:

F (T) =fcost (fcount+fd+fpl)

$f{}_c=\frac{\alpha }{cost(s)}f{}_{count}=\rho {}^{(count({\rm T}{}_i)-1)}$

fd = rdQ (Ti) fpl=r${}_{pl}^{L({\rm T}{}_i)}$

其中, α、ρ、rd、rpl均为正实数, 且ρ、rd、rpl均小于1。ρ表示解s的图G′ (V′, E′) 连通性的惩罚系数, rd表示当有源节点到目标节点延时超过Δ的惩罚系数, rpl表示当有源节点到目标节点延时超过θ的惩罚系数。以上参数决定了惩罚的力度, 在实验中, 选择ρ=0.2, rd=rpl=0.5。

2.4种群的初始化

在遗传算法中, 每个染色体都代表相应的解, 初始种群由一定数量的个体染色体组成, 所以在进行种群初始化之前, 先讨论怎样产生单独的个体。按照以下算法产生种群中的个体:

对需要进行多播的节点集U={u0, u1, …, um} (U⊆V) , 随机的选择一个节点作为源节点, 例如u0, 对进行过预处理的图G (V, E) 进行以下操作:

(1) 设i=1, 用Dijkstra算法计算从u0到ui的最短路径, 用Ti (Wi, Fi) 来代表这条路径, U=U-{u0, ui}。

(2) 如果U=ϕ, 则算法终止, 否则转 (3)

(3) i=i+1, 以ui为源节点, u0为目标节点, 使用Dijkstra算法计算从ui到u0的最短路径, 把该路径加入到Ti-1, 这样一个新的树Ti (Wi, Fi) 生成了, U=U-{ui}, 转 (2) 。

算法结束时, 树Ti (Wi, Fi) 即为初始解。

种群初始化算法如下:

(1) i=0, 产生特殊染色体sp;

(2) i=i+1, 随机产生染色体si;

(3) 设K代表种群的规模, 如果i<K, 则转 (2) , 否则结束。

2.5选择策略

采用锦标赛选择法来选择个体, 随机从种群中挑选一定数目的个体, 然后将最好的个体作为父个体, 这个过程重复进行完成个体的选择。锦标赛选择的参数为竞赛规模, 实验中选择竞赛规模为5。

2.6交叉操作

交叉操作是指按一定概率随机从亲代群体中选择两个个体, 并随机将两个亲代个体的部分结构相互交换, 生成两个新的子代个体。 交叉操作产生的两个子代个体, 都包含两个亲代个体的遗传基因, 但与亲代个体不同。因此, 交叉操作能提高遗传算法的搜索能力, 在适当选择策略下, 通过交叉操作可提高向全局最优解的收敛程度。

采用单点交叉的方式, 交叉点随机选择, 例如, 染色体si=101101, sj=110101进行交叉操作, 首先随机的选择交叉点, 例如选择二进制串的第二个bit和第三个bit之间作为交叉点, 进行交叉操作, 操作之后的结果为:si=100101, sj=111101。

按照这种交叉方式产生的结果中, 多播组U可能不在一个连通图中, 但是在计算适应度函数的时候会被加上惩罚系数, 降低适应度函数, 这样的个体不会遗传到下一代中。

2.7变异操作

变异操作是在染色体上自发地产生随机的变化, 它是以一个较小的随机概率改变个体字符串上的某些位, 与种群的大小无关。

采用bit位变异的方式。例如, s由111001经过变异成为111101。但是这种方式有可能产生错误的个体, 即在以上例子中, 变异之后的个体为111101, 如果节点4是属于多播组的节点, 但是bit (s, 4) =0, 则表示节点4不在多播树中, 因此该染色体是一个错误的个体。为解决该问题, 定义一个只包含所有多播节点的特殊染色体sp, 变异之后的个体都与这个特殊染色体做“或”操作, 即s=sp∨s, 这样便可保证变异之后的个体均为正常个体。

3实验结果

采用C语言实现上述QoS多播路由的遗传算法, 并就性能与启发式算法和文献[8]进行比较。实验网络的拓扑结构生成部分借鉴salama提出的拓扑结构生成方法[9], 该算法保证节点度平均为4, 与现实网络环境非常接近, 在研究中被广泛采用。实验过程中多播组随机选择, 试验中多播组的选择为节点总数的1/4, 初始种群数量为20, 交叉概率pc=0.4, 变异概率pm=0.01, 终点的延时约束在[100, 150]ms之间均匀分布, 带宽约束在[20, 50]之间均匀分布。试验主要对算法结果的代价以及算法的效率两方面进行验证。

图1和图2分别表示了启发式算法、文献[8]提出的算法及本文算法在性能和效率上的对比, 从这两个图可以看出, 本文提出的算法在性能和效率上都有所提高。

4结论

针对QoS多播路由问题, 首先给出了带多约束代价最小的QoS多播路由问题的网络模型, 并在前人工作的基础上提出了一种新的基于遗传算法来解决多播路由问题。采用定长的染色体编码, 简化了编码和后续的交叉和变异操作;采用预处理机制, 有效减少了算法的编码空间, 提高了算法的效率;种群初始化时随机选择多播源节点, 使最终的解不仅仅对多播组中特定的源节点是最优的, 还考虑了其它节点发送信息时的情况, 这样更符合大部分应用场合的实际情况。实验表明, 该算法收敛速度快、可靠性高。尤其是在网络规模较大时, 该算法搜索速度更快, 能大大减小路由计算时间, 能满足在实时通信环境QoS 多播路由的网络结构的需求。

摘要：深入研究基于遗传算法的QoS多播路由算法, 建立支持QoS的多播路由模型。对已有的QoS多播路由算法进行优化, 提出适用于下一代网络的基于遗传算法的QoS多播路由算法。采用定长的染色体编码和预处理机制降低算法复杂度。仿真试验表明, 该算法收敛速度快, 可靠性高, 能够更好地满足多播业务的需要。

关键词：遗传算法,服务质量,多播,路由算法

参考文献

[1] Hwang F K.Steiner tree problems[J].IEEE Networks, 1992, 22 (1) :55-89.

[2] Jia Xiaohua, Pissinou N.A real-time multicast routing algorithm for multimedia applications[J].Computer Communications, 1997, 20:1098-1106.

[3]Kapsalis A, Rayward-Smith VJ.Solving the graphical Steiner tree prob-lem using genetic algorithm[J].JORS, 1993, 44 (4) :397-406.

[4] Esbensen H.Compute near-optimal solutions to the Steiner problem in a graph using a genetic algorithm[J].IEEE Networks, 1995, 26 (1) :173-185.

[5]Aharoni E, Cohen R.Restricted dynamic Steiner trees for scalable mul-ticast in datagram networks[J].IEEE/ACMTrans.Netw, 1998, 6 (3) :286-297.

[6] Zhang Q, Lenug Y W.An Orthogonal Genetic Algorithm forMultimedia Multicast Routing[J]//IEEE Trans Evolutionary Computation, 1999, 3:53-62.

[7]Munemoto M, Takai Y, Sato Y.A Migration Scheme for the Genetic A-daptive Routing Algorithm[C]//IEEE International Conference on Systems, Man, and Cybernetics, 1998:2774-2779.

[8] Wang Z, Shi B X, Zhao E D.Bandwidth Delay Constrainted Least Cost Multicast Routing Based on Heuristic Genetic Algorithm[J].Computer Communications, 2001 (24) :685-692.

多播路由协议论文 篇5

本文对GAAC (Genetic Algorithm and Ant Colony Algorithm) 方法进行研究, 目的是为了更好地解决Ad Hoc网络中的Qo S多播路由问题。GAAC方法是利用具有快速全局搜索能力的遗传算法具和有正反馈收敛机制的蚂蚁算法, 初期采用遗传算法过程生成信息素分布, 后期利用蚂蚁算法正反馈求精确解, 从而获得时间性能和优化性能的双赢。

1 Qo S多播路由问题是寻找一棵多播树Q (a, A) 满足以下约束

(1) 延迟约束:delay (p (a, d) ) ≤Y, Y为最大时延。

(2) 带宽约束:bandwidth (p (5, d) ) ≥C, C为瓶颈带宽。

(3) 延迟抖动约束:delay_jiter (p (a, d) ) ≤YL, YL为最大时延抖动。

(4) 包丢失率约束:packetloss (P (5, d) ) ≤F, F为最大包丢失率。

使得多播树 (S, M) 的总费用cost (Q (a, A) ) 最小。

2 基于遗传蚁群算法的Qo S多播路由算法分析

GAAC算法的基本指导思想是:先由遗传算法产生较优解, 较优的路径留下信息素, 其它路径不改变;然后在有一定初始信息素分布的情况下再按照蚁群算法, 充分利用蚁群算法正反馈性、并行性求精解。既能发挥遗传算法与蚁群算法在寻优搜索中各自的优势, 又能克服遗传算法在搜索到一定阶段时最优解搜索效率低以及蚁群算法初始信息素匮乏的问题。但这种算法虽然能够有效地选择一条最优路径, 但却忽视了一个问题, 即实际网络的最优路径一经形成, 那么所有的数据就将会选择最优路径传输。这就使得当负载较大时发生拥塞的可能性就比较大, 并且一旦发生拥塞, 要消除它将需花较长时间。这时如果采用拥塞回避的策略将可以获得较好的效果, 从而实现网络负载均衡。

3 GAAC中的遗传算法规则

3.1 遗传编码

通用的遗传算法编码模式使得算法编码、解码过程都很复杂, 并且算法的搜索空间会随网络规模增加而急剧增加, 这就使得算法效率大大降低。本文根据网络路由的特点和遗传算法的编码原则, 采用节点序列编码, 对给定的路径的物理节点标识序列作为该路径的编码值, 并保持不变, 这种编码方式自然而且直观。

3.2 初始群体的生成

采用随机方法从中选择若干个体组成初始种群, 其具体做法是:首先精简网络, 删除不满足Qo S约束条件的节点及与之相连的链路, 再删除不满足带宽要求的链路, 得到一个新的网络拓扑。基于此拓扑图进行搜索, 从源节点开始, 随机地选择一个与之相关联的节点, 将两点相连;然后从选择的节点继续随机地选择与其关联的下一个节点, 在连接时要判断是否有回路, 如有就重新选择节点, 一直循环至搜索到目的节点。

3.3 选择算子

本遗传算法采用最佳保留选择机制, 先将当前的解群体中适应度最高的个体结构完整地复制到下一代群体中, 然后按照轮盘赌选择机制执行选择功能。

4 GAAC中的蚁群算法规则

(1) 路径选择规则。该策略增强了搜索的多样性, 以避免过早陷于搜索停滞。

(2) 信息素初值设置规则。通过遗传算法得到了一定的路径信息素, 因此把信息素的进行初值设置。

(3) 信息素更新规则。即采用局部更新和全局更新相结合的策略, 既可避免蚂蚁在上次最好的路径有限相邻区域内搜索又对历史最优解的路径上的信息素进行了更新。

(4) 拥塞回避规则。通过节点的平均队列长度来衡量网络拥塞状态, 以便向网络层实时提供传输信道的拥塞信息。

5 算法的实现过程

(1) 精简网络拓扑, 删除不满足Qo S约束条件的节点和与之相连的链路, 再删除不满足带宽要求的链路, 得到一个新的网络拓扑, 基于此拓扑图进行搜索;

(2) 随机产生一组实数编码;

(3) 根据遗传算法进行若干次迭代, 依据目标函数, 生成网络初始信息素分布;

(4) 在源节点放置多只蚂蚁, 每个蚂蚁依据状态转移概率选择下一跳节点;

(5) 蚂蚁完成一步后, 进行局部信息素更新, 同时按照拥塞回避规则回避拥塞节点;

(6) 所有的蚂蚁完成一次循环后, 进行全局信息素更新;

(7) 若满足结束条件及输出最优解;否则跳转到步骤4。

6 小结

本文针对Ad Hoc网络Qo S多播路由问题进行分析, 对基于遗传蚁群算法的Qo S多播路有时产生的拥塞问题进行了分析, 采取拥塞回避策略, 从而实现了业务流的均衡分配。经过分析发现这种方法比其它单一采用蚁群算法进行路由选择更适合于动态Ad Hoc网络环境。但这种算法没有考虑到Ad Hoc网络节点能量受限的特点, 还需进一步完善。

摘要：随着网络信息的推广和普及, 用户在网络时延、带宽等方面要求提供的保障越来越多, 随之在Ad Hoc网络中提供QoS支持也就显得越来越重要。但是考虑到Ad Hoc网络节点并非是固定不动的, 网络拓扑结构也是不断发生变化的, 而且它们的存储容量和计算能力较低, 并且能量也受到一定的限制, 那么如何设计出满足多个QoS约束条件的多播路由算法便成为重要的研究课题。

关键词：网络节,拓扑结构,遗传算法,蚁群算法

参考文献

[1]胡光岷, 李乐民, 安红岩.最小代价多播生成树的快速算法[J].电子学报, 2002, 30 (6) :880-882.