组播路由器

组播路由器（精选八篇）

组播路由器 篇1

1988年斯坦福大学的博士生Steve Deering首次在其博士论文中提出IP多播的概念[1,2]。由于有许多的应用需要由一个源点发送到许多的终点，如视频点播，网络电视，软件更新，交互式会议，视频会议，远程医疗，远程教学，新闻发布等[3]。1992年，为了适应交互式音频和视频信息的多播需求，人们在因特网上开始研究多播主干网MBONE(Multicast Backbone On the Internet)，它可以把数据包传播到属于同一分组但地点分散的多个主机。至2012年年底，全球已有超过24亿的互联网用户[3]，增长的用户量绝大部分来自于移动终端的普及。目前，全球移动设备用户约为15亿，而去年同期仅为1亿[4]。随着网络用户数的急剧增加，以及多媒体通信的广泛应用，越来越多的业务需要多播来支持。IP组播技术[5]主要用于解决点到多点的高效数据通信问题。自组播提出以来，一直是因特网中的一个热门课题。

服务器与多台主机进行通信时，即点对多点通信时，可以通过单播建立多个点对点的连接来实现点对多点的通信。此时源点(通常为服务器)将与各个接收点建立连接，服务器将有多份相同的数据包分别发向分散的各个接收点。这种方式不仅加重服务器的负荷，而且同时增加了网络流量，加重了网络的负担并可能导致网络拥塞。IP组播又称作IP多播，是指向一个包含零个或多个主机的主机组传送相同的IP数据包。在组播中，使用最短路径树(SPT)或共享树(ST)或二者的结合来进行组播数据包的转发。组播与单播不同，组播使用组播传送树来发送数据包;发送方只需要发一份数据包，之后的数据包只是在需要复制分发的地方才会被复制分发;这样就可以大大减轻服务器的负担，减少重复的冗余数据包，从而节省网络带宽。因此在一对多的通信中，组播更具有优势，组播可大大节约网络资源，节省网络带宽，并大大减轻发送端的负担。

本文将传统组播存储转发模型，称之为TMSF(Traditiona Multicast Storage and Forwarding)模型。在TMSF模型中，组播路由转发表采用完全存储方式，即在每一个线卡中都存储全部的组播转发项。然而，组播路由器收到组播数据包时要进行RPF(Reverse Path Forwarding)检查，因此入接口不属于入线卡(接收到组播数据包的线卡)的转发项一定会匹配失败，所以入接口不属于入线卡的接口的转发项不必在入线卡中存储。由于出接口列表的出接口个数的不确定性，导致组播转发项长度为不定长;而且线卡号会被重复存储，例如out＿if＿list为{1/1,2/1,3/1,1/2}，此时线卡号‘1’存储了3次，实际上只需存储一次;而且在转发数据包时，转发引擎会复制3份数据包，通过路由器内部高速交换网络发往线卡1，实际上只需要向线卡1发送1份数据包。因此TMSF模型中存在存储冗余与数据包转发冗余，不仅浪费组播路由器的存储空间，而且存在较大的内部交换时延。

本文通过分析TMSF模型的不足，提出了组播路由优化存储转发模型，即OMSF(Optimized Multicast Storage and Forwarding)模型。OMSF模型对TMSF模型进行了存储优化与转发优化，在OMSF模型中只存储部分转发项，而不是全部转发项，且不存在线卡号的冗余存储;该模型转发数据包时，同一出线卡(组播转发项出接口列表中的线卡)只转发一份数据包。OMSF模型不仅减轻了组播路由器的存储与转发负担，而且大大减少了网络流量。

1 传统组播存储转发模型

1.1 线卡功能模型

图1是现在商业路由器广泛使用的线卡模型，线卡主要由转发引擎、转发表、接口等模块组成。在此假设每个线卡有n个硬件接口。在进行组播分组报文转发时，将收到报文的接口称为入接口;将发出报文的接口称为出接口。在此将第i个入接口标识为IFi(0≤i≤n)，第j个出接口标识为OFj(0≤j≤n)。线卡i的可能的最大入接口总数为IF＿LCi，其可能的最大出接口总数为OF＿LCi。假设组播路由器线卡总数为n LC，则可能的最大入接口总数为，可能的最大出接口总数为，显然nIF=nOF。出接口与入接口硬件相同，在此只是做逻辑功能上的划分，每个硬件接口既可以是入接口，也可以是出接口，入接口可能与出接口相同。

1.2 传统组播存储转发模型存储分析

TMSF模型组播路由器路由转发表项为<mlticast＿group,src＿addr,in＿if,flag,out＿if＿list>，简记为<G,S,IF,FLAG,OF＿LIST>。G表示组播组，S表示源地址，IF表示组播数据包的入接口，OF＿LIST表示组播数据包的转发出接口列表。单播转发表项的出接口只有一个，而多播路由转发表中出接口可以有很多个且个数不确定，因此组播转发表每一表项的占用存储空间大小并不相同，容易产生过多不可利用的存储碎片;OF＿LIST中的线卡号会被重复存储，造成存储空间的浪费;同时也不利于存储空间的优化管理。在OMSF模型中将对组播转发表项进行优化，将表项长度统一为固定长度，并解决了线卡号重复存储的问题。

假定G,S,IF,FLAG字段所占用的存储空间分别为Sg,Ss,Sif,Sflag;一个转发接口所占的存储空间大小为Sof;转发出接口的个数为α;则TMSF模型一个转发项所占的总的存储空间为:

其中Sg,Ss,Sif,Sflag,Sof所占用存储空间的大小均为常数。因TMSF模型采用完全存储方式，在每个线卡上均需存储，所以此模型中一条转发项的总存储销耗为:nLC×Stmsf。

1.3 传统组播存储转发模型转发分析

TMSF模型转发过程，如图2所示。组播路由器从入线卡LCin收到一个组播数据包后，查找组播转发表，将数据包中的组地址G与源地址S与转发表中的<G,S>项进行匹配;若匹配成功，则进行RPF(Reverse Path Forwarding)检查，若匹配失败，则丢弃该组播数据包;RPF检查成功后查询组播转发表，若RPF检查未通过，则丢弃数据包;匹配成功后将得到出接口列表，而后根据所得到的出接口列表将数据包发往相应的出线卡，若匹配失败，则直接将该数据包丢弃[6,7]。

组播与单播不同，组播路由器可能从多个接口接收到数据包。但有的接口并不在多播转发路径上。例如PIM-SM协议[8,9]，会建立由目的路由器到源路由器的最短路径树(SPT树)，不在SPT路径上的流量应该被剪枝;接口IF1的流量并不在SPT树上，应该将该接口的流量剪除，因此RPF检查是必需的。以图3为例，路由器r源主机s发来的多播数据包和进入路由器时的接口IF，然后路由器r执行RPF检查。尝试着用单播方式由r向s发送数据包，查找单播路由转发表，查得发送接口为IF0。若收到数据包的组播路由器的入接口也为IF0，则RPF检查成功;否则RPF检查失败，将该数据包丢弃。这样，就确保了入接口的唯一性。

在线卡上，组播转发表项的入接口非本线卡的接口时，RPF检查一定会失败。因此转发表入接口不属于本线卡接口的转发项不必存储在该线卡中。例如，假设LC0有4个接口:0/0,1/0,2/0,3/0。对于<G,S,0/1,FLAG,OF＿LIST>的转发项，RPF检查必定失败。对于入接口不属于入线卡接口的转发项在OMSF模型中一律不再存储。这样即节约了存储空间，又节省了RPF检查的时间。

路由器组播转发，收到的一个数据包组播路由表匹配成功后，需要查询出接口列表，依据出接口列表为每个出接口复制一份数据包发出。显然当一个数据包需要从分布在不同线卡的多个出接口转发时，转发引擎可能通过内部高速交换网络向同一出线卡多次发送相同的数据包。这些冗余的数据包会消耗大量系统内部的高速交换带宽。入线卡需要复制多份相同的数据包，因而会消耗其大量的处理资源。虽然TMSF模型简单有效且易于实施，但存在冗余处理，一次完整的组播转发时延较长。下面以三个线卡为例来分析TMSF模型，如图4所示。

入线卡LC0从IF1收到一个组播数据包后匹配组播转发表并根据出接口列表进行转发，在此假设出接口列表为{0/1,1/2,2/1,3/2}，入线卡根据出接口列表，依次将出接口信息放到数据包边带信息中，并通过内部高速交换网络向对应出线卡LC1、LC2发送数据包，LC0会分别向LC1、LC2发送两份重复的数据包。出线卡LC1与LC2均会收到两份相同的数据包。此过程存在2份冗余的数据包，此时内部数据包交换次数为4次;而且出线卡中的转发出接口越多，冗余数据包及内部数据包交换次数也越多。

时延包括:数据包接收时延Trecv;从数据包进入线卡到被处理的时间，即排队时延Tqueue;组播转发表查询时间Tlookup;假设转发出接口的个数为，则板间转发时延为(α×Tsw),Tsw为一次板间转发所需要的时间;数据包的发送时延Tout。假定出线卡发发送数据包的时间大致相同，且忽略数据包在出线卡上的排队时延，则数据包转发的总时延为:

2 OMSF模型

2.1 OMSF存储模型

在TMSF模型中，入线卡查询组播路由项后，会根据出接口列表为每一个出接口复制一份数据包并转发。在组播转发项的出接口列表中，往往多个出接口会处于同一个出线卡上，此时在TMSF模型中会进行多次转发，存在冗余数据包。随着多播技术的广泛应用，多播数据包的快速增长，势必要消耗大量的内部网络交换带宽。为了减少内部交换网络的冗余数据流量，减轻入线卡的负载，本文提出了OMSF模型。

定义线卡表示位k，即用k位二进制数来标识线卡。设路由器中线卡总数为n LC，则k应满足k=n LC。本文以n LC=3为例进行阐述，此时k=3，即可用3位二进制数来标识线卡。例如LC0→001，表示用3位二进制数‘001’来标识LC0，同理，LC1→010,LC2→100。由于组播路由器中线卡个数有限，因此不会占用过多存储空间。

定义出接口标识ofid，即用ofid位二进制数来标识一个组播分组出线卡上的出接口，其值等于最大出接口个数，即ofid=0≤mi≤anxLC{OF＿LCi}。通常，一般路由器线卡最多支持16个接口。本文假设LC0,LC1与LC2均有4个接口，因此ofid=4，即使用4位二进制数来标识线卡的接口。

定义组播路由器线卡转发标识符OUTID。用于表示出线卡的转发出接口，OUTID为ofid位。出接口列表为{0/1,1/2,2/1,3/2}，组播数据包将从线卡LC1的第0号与第2号接口转发，线卡LC2的第1号与第3号接口转发。设LCj(0≤j≤n LC)对应的OUTID可表示为OUTID＿LCj，则LC1与LC2的OUTID值可表示为OUTID＿LC1→'0101'与OUTID＿LC2→'1010'。

定义出线卡标识符OUT。OMSF模型组播路由转发表项由<G,S,IF,FLAG,OF＿LIST>简化为<G,S,IF,FLAG,OUT>,OUT为出线卡标识符，由它可得到出线卡。在TMSF模型中OF＿LIST是不定长的，因此组播转发表的表项也是不定长的。现在将OF＿LIST改为OUT,OUT是定长的，长度为k。假设路由中有3块线卡且OF＿LIST为{0/1,1/2,2/1,3/2}，则OUT为‘110’，表示此组播数据包将会从线卡LC1、LC2转发。

在OMSF模型中增加一个线卡接口转发表。该表有三个表项:ID、OUTLC和OUTID。ID=F{G,S}，ID由<G,S>通过一定的规则变换生成，其作用是使线卡接口转发表项与组播转发表项对应。函数F可以使用哈希函数，也可根据需要自己定义。OUTLC为出线卡标识符，OUTID为线卡出接口转发标识符。OUTLC为m位，m=log2n LC，则OUTLC0→'00',OUTLC1→'01',OUTLC2→'10'。OUTID为ofid位。设ID字段所占的存储空间为Sid，则该表项共占Sid+m+ofid位。因此OMSF模型组播路由转发项所占用的存储空间如式(3)所示。使用ID会增加转发表项的长度，但可以让线卡接口转发表存储在一个单独的区域，方便管理。当然，也可以不使用ID字段，将<OUTLC,OUTID>这两个字段构成的序列直接接在组播转发表项的后面。形式如:<G,S,IF,FLAG,OUT><OUTLC0,OUTID0><OUTLC1,OUTID1>…。不使用ID字段的存储消耗如式(4)所示。

2.2 OMSF转发模型

在OMSF模型中，当入线卡LC0收到一个组播数据包后，将此数据包复制2份，分别向LC1、LC2发送1份数据包，如图5所示。而在TMSF模型中需要复制4份数据包，因此冗余数据包减少了一半。此时内部交换次数为2次，也减少了一半。当出线卡LC1、LC2收到数据包后，根据线卡转发标识符从相应的接口发送出去。

OMSF模型组播数据包转发流程如图6所示:入线卡LCin收到组播数据包后，查询组播路由转发表，此时的转发表项为<G,S,IF,FLAG,OUT>。<G,S>匹配成功后进行RPF检查。在此模型中只存储入接口是本线卡中的接口的转发项。因为在TMSF模型中存储所有的组播转发项，所以OMSF模型中组播转发表表项数量比TMSF模型少得多，同时缩短了RPF检查所需的时间。RPF检查失败时，丢弃该数据包。RPF检查通过后，从转发表中查得转发线卡标识OUT。然后，根据OUT的值在线卡转发出接口表中查找各个转发出线卡所对应的转发接口标识OUTID。入线卡从OUT中解析出要转发到的出线卡，并将OUTID加入到转发边带信息中。入线卡复制数据包并通过内部高速交换网络发往相应的出线卡。出线卡接收到数据包后，从边带信息中提取出OUTID。出线卡根据OUTID的值将数据包从相应的接口转发数据包。

假设n LC=3且每块线卡有4个接口，所以k=3,ofid=4。在此在线卡接口转发表中使用ID字段，以方便讲解。TMSF模型中的转发表如表1所示。其对应的OMSF模型转发表如表2所示。线卡转发接口表如表3所示。

假设某数据包匹配<G2,S2>成功，且数据包从入线卡的IF0口进入，则RPF检查成功。从OMSF模型转发表中查得OUT值为‘110’,OUT的第2位与第3位为1，说明此数据包应该分别从LC1,LC2转发。然后查询线卡转发接口表，得到OUTID＿LC1→'0001'与OUTID＿LC2→'1110'。将OUTID＿LC1与OUTID＿LC2加入到边带信息中，通过内部高速交换网络分别发往LC1与LC2。出线卡LC1收到数据包，并从连带信息中得到OUTID＿LC1，发现其第1位为1，说明应该从第1个接口(OF0)转发该数据包。LC2从边带信息中得到OUTID＿LC2，其2、3、4位为1，说明数据包应该从第2、3、4号接口转发，即OF1,OF2与OF3。

实际工程中，如果想要进一步节省存储空间，可以不使用ID字段。此时的组播转发表如表4所示。组播转发过程与使用ID字段时的转发过程相似，不再重复叙述。但是这样使得组播转发表的长度变得不固定，不利于存储优化与管理。

OMSF模型时延包括:数据包接收时延Trecv;从数据包进入线卡到被处理的时间，即排队时延Tqueue;组播转发表查询时间Tlookup。假设转发线卡(出线卡)的个数为β，则板间转发时延为(β*Tsw),Tsw为一次板间转发所需要的时间;数据包的发送时延Tout。假定出线卡发送数据包的时间大致相同，且忽略数据包在出线卡上的排队时延，则数据包转发的总时延为:

3 仿真及性能分析

在转发出接口列表中，同一出线卡的转发出接口数越多，TMSF模型的板间交换的冗余数据包也就越多，其转发时延越大。现假设只有一个出线卡，且n OF≥1。此时α≥1，β=1。此时Tout,Tlookup,Trecv并不影响两模型时延的对比，虽然它们会随n OF的增加而增加，但两模型的增加量差异不大，因此对分析结果影响较小，在此设C=Trecv+Tqueue+Tlookup+Tout,C为常数。TMSF模型与OMSF模型的转发时延分别如式(6)与式(7)所示，转发时延用T表示(T个时间单位)，设Tsw=C=1，转发时延与此出线卡的出接口数的关系如图7所示。由图可知，OMSF模型在β=1的情况下转发时延不随出接口数的变化而变化，TMSF模型的转发时延呈线性增长均势。

OMSF模型组播数据包的内部交换总次数只与β有关，且成正比关系;TMSF模型的内部交换次数只与α有关，且其正比关系。

为了进一步比较分析两个模型内部交换次数的优劣，在此，假设出有20个出接口，即α=20，则内部交换次数随出线卡数β(β≤20)的变化关系如图8所示。由图可知只有当出线卡数与出接口数相等时，内部交换次数才相等。OMSF模型可以大大减少内部交换次数，减轻内部交换网络的负担，降低组播数据包转发时延。

现假设多播路由器有16个线卡，即n OF=16，且出线卡数β=16，则出接口数α≥β，即α≥16。当α=16时，说明每一个出线卡上都有一个出接口，此时两模型的内部转发次数相同。内部交换次数随α的变化情况如图9所示。

由图9可知TMSF模型的内部交换次数呈线性增长趋势，而OMSF模型始终处于内部交换次数的最小值。由图8与图9综合分析可得，只有当α=β时，两模型的内部交换次数相同;其他情况下OMSF模型的内部交换次数都少于TMSF模型。随着内部交换次数的显著减少，组播数据包的转发时延也随之大大减少。

现在使用MATLAB实现两模型的转发算法并进行实验仿真，仿真模型如图5所示。随机生成1000个组播分组，TMSF模型分组的数据包格式为:<G,S,IF,FLAG,OF＿LIST>;OMSF模型分组的数据包格式为<G,S,IF,FLAG,OUT>{<OUT-LC,OUTID>}。使用三个程序模块来模拟三个线卡，其中一个模块用来接收并转发组播分组(模拟入线卡)，另外两个模块用来接收组播分组(模拟出线卡)。线卡LC0收到组播分组后，查询组播转发表，将组播分组分发到LC1与LC2的相应接口。转发算法如表5所示。

实验结果如图10所示。为方便更清晰的观察，将0～50个组播分组时的图像进行放大，如图11所示。TMSF模型内部交换次数随着组播分组个数的增加而显著增大，且成线性增长趋势，而OMSF模型的内部交换次数相对比较稳定。

现将表5所示算法进行修改，将线卡个数设为变量，统计线卡个数与内部交换次数的关系。仍然发送1000个随机组播数据分组进行测试，所得到的实验结果如图12所示。TMSF模型内部交换次数始终处于高位。OMSF模型内部交换次数随线卡数的增加呈先增涨后平稳的变化趋势，但交换次数较少。

设路由器中组播转发项总数为x，每块线卡上均有n个硬件接口。由于Sg,Ss,Sif,Sflag字段在两模型中均相同，故设W=Sg,+Ss,+Sif,+Sflag,W为一常量。根据式(1)可得TMSF模型路由器总的存储消耗为:

其中。根据式(4)可得OMSF模型的存储消耗为:

为方便分析，取W=1;α=2,4;β=2,4;两模型的存储消耗对比如图13所示。

结合上述推导表达式分析可知，TMSF模型表项的存储消耗与α有关，且与α成平方级别的变化关系，而与β无关;α越大，代表该模型的直线的斜率越大，该模型每条转发项所占的存储空间越大，路由器总的存储消耗越大。相比之下，OMSF模型表项存储消耗与β有关，与β成线性变化关系，而与α无关;由图可看出其增速缓慢，且存储消耗较低。因此可知OMSF模型所消耗的存储资源较少，具有较高的存储优势。

4 结语

本文通过分析传统的组播路由器存储转发模型(TMSF模型)，发现其存在存储空间的浪费与冗余的内部交换数的包，占用较大的内部交换网络带宽，加大了组播数据包的转发时延。优化存储转发模型(OMSF模型)根据TMSF模型的不足，进行了存储优化与转发优化。将原先的完全冗余备份存储，变为只存储根据入线卡的接口而得到的部分转发项;并且不再存储冗余的出接口号，大大减轻了存储负担。OMSF模型，转发引擎通过内部交换网络只向出线卡转发一份数据包，这样大大减轻了内部交换网络的负担，并减少了转发时延。本文对两模型的转发时延与内部交换次数进行了比较分析，得出OMSF模型的转发效率更高。

参考文献

[1]Deering S E,Cheriton D R.Host Groups:A Multicast Extension to the Internet Protocol[S].RFC 966,December,1985.

[2]Deering S E.Host Extensions for IP Multicasting[S].RFC988,July,1986.

[3]许亚梅,包怀忠.IP组播技术的优势及其应用[J].中国科技信息,2009(9):150.

[4]D11大会.互联网趋势报告[R],Mary Meeker,2013.

[5]Deering,Stephen E.Multicast Routing in a Datagram Internetwork[D].California:Univ.of Stanford,December,1991.

[6]Beau Williamson.IP组播网络设计开发[M].电子工业出版社,2001.

[7]William R Parkhunst.Cisco Multicast Routing and Switching[M].Mc Graw-Hill,1999.

[8]Fenner B,Handley M,Holbrook H,et al.Protocol Independent Multicast-Sparse Mode(PIM-SM):Protocol Specification[S].RFC4601,August,2006.

组播路由器 篇2

关键词：物联网；路由算法；链路稳定；能量感知

中图分类号：TP39303文献标志码：A文章编号：1672-1098（2016）01-0019-06

Abstract：In view of the problem that the energy consumption is not balanced， the routing stability is poor， and the data is easy to be lost in Internet of Things （IoTs）， an improved network routing algorithm based on link stability and node residual energy aware is proposed.Firstly， a hybrid routing model based on link stability and residual energy of nodes is established. By using this model， the energy and the link stability parameters of nodes are combined to predict the optimal nodes to form the network.Simulation results showed that compared with AODV algorithm， the algorithm can effectively control the network overhead， improve the data transfer rate， prolong the network lifetime， and reduce the network delay.

Key words：internet of things； routing algorithm； link stability； energy aware

在许多实际应用中，由于传统的物联网路由协议中传感器节点的移动性、能量的有限性和射频距离的有限性，容易出现节点的能量消耗不均衡，路由稳定性差，数据容易丢失等问题，传输效率不高。针对上述问题，本文提出了一种基于链路稳定和节点能量感知混合模型的组播路由协议（Link Stability and Energy-aware Hybrid model-Based Multicast Routing Protocol，LEHMR），LEHMR路由算法的主要思想是根据节点间的链路状态和节点的当前剩余能量控制整个网络的路由发现。该方法采用广播请求应答（RREQ-RREP）方式，利用网络节点间的链路状态信息和节点的剩余能量信息来建立路由选择机制，来建立网络路由。

1路由模型

11链路稳定和节点能量混合的路由选择机制

如图1所示，主要展示了LEHMR算法路由建立的过程。当有数据转发时，源节点将广播一个RREQ包，邻居节点将根据自身的节点剩余能量和链路保持时间来判断是否接受该数据包，来转发数据。该算法与以往任何算法的不同之处在于，每个节点在接受RREQ包时，要根据节点的剩余能量和链路保持时间综合判断出是否接收RREQ包，而成为路由链路上的节点，进而接收并转发RREQ包。该RREQ包中的节点以链路的保持时间与节点的剩余能量作为度量值，来搜索数据转发路径，建立网络路由。

链路稳定和节点能量混合的路由选择机制当节点S向节点D发送数据时，节点S将广播RREQ数据包，所有邻居节点将接收这个RREQ数据包。在传统的AODV算法中，节点1，2，3中若无有效的到节点D的路由，节点1，2，3都将转播RREQ包。在LEHMR算法中，将检测节点1，2，3与节点S的链路保存时间和节点1，2，3的剩余能量，因节点1的剩余能量少、节点2与节点S的链路保持时间小，根据LEHMR算法节点1与节点2将放弃接收到的RREQ包。只有节点3满足能量和链路保持时间要求，只有节点3再次广播RREQ包，从而建立起S-3-D的路径传送数据。

12链路稳定和节点能量混合数学模型

1） 链路稳定性描述

假设节点坐标为（xi，xj），其移动速度、运动方向和信号传播半径分别用vi、θi和Ri来表示。则两个移动节点ai和aj之间的链路保持时间LET可用公式（1）表示

LETij=

-（ab+ad）+（a2+c2）r2-（ad-bc）2a2+c2（1）

式中：a=vicos θi-vjcos θj，b=xi-xj、c=visin θi-vjsin θj，d=yi-yj、r=Ri

2） 节点能量描述

如图2所示，物联网路由算法的研究大都采用此节点能量消耗模型， 该模型由传送装置、放大装置和接收装置三部分构成，传感器节点所消耗的总体能量为上述三部分所消耗的能量总和。图2节点能量消耗模型

将L bit的信息量数据传送d距离所消耗能量的公式模型如式（2）所示

EL.Tx（L）=L×Eb.txe+L×εfs×d2d≤d0

L×Eb.txe+L×εmp×d4d>d0（2）

接收L bit信息量数据所消耗能量的公式模型如式（3）所示

EL .Rx（L）=L×Eb.Rx（3）

中转L bit信息量数据所消耗能量的公式模型如式（4）所示

Eralay（L）=EL .Rx（L）+EL .Tx=

L×Eb.txe+L×Eb.Rx+L×εfs×d2d≤d0

L×Eb.txe+L×Eb.Rx+L×εmp×d2d≤d0（4）

式中：εfs和εmp是所选用模型的发送放大器系数，Eb.Rx表示接收1bit信息量数据所需能量，Eb.Tx表示发送1bit信息量数据所需能量。路径损耗指数为α值，当d≤d0时，α等于2，当d>d0，α等于4。

节点发送、接收或转发的Lbit信息量数据后的剩余能量Es（L）用公式（5）表示

Es（L）=E0-EL.Tx节点为源节点

E0-EL.Rx节点为目的节点

E0-Eralay节点为源节点（5）

2LEHMR算法描述

21LEHMR算法路由建立流程

LEHMR算法路由建立的流程图，如图3所示。

图具体描述如下：首先判断接收RREQ包的节点中是否存在有效路由，若存在，则建立链路；否则根据公式（1）和公式（5）分别计算出接收RREQ包节点的剩余能量和接收RREQ包节点和发送RREQ包节点间的链路保持时间；判断接收RREQ包节点与发送RREQ包节点间的链路保持时间和接收RREQ包节点的剩余能量值是否大于阈值，若大于设定的阈值，在发送RREQ节点的路由信息表中记录满足条件的节点路径信息。反之，则放弃该节点。并根据公式（1）和和公式（5）选择最优节点转发RREQ包，直到建立路由。

22LEHMR算法流程

本文提出的LEHMR路由算法，是属于应答式的组播路由协议。该算法中将链路稳定度和能量信息结合到路由发现机制中，改进路由选择机制，只有满足链路稳定度和能量要求的路径才能被选择，其总体的流程如图4所示。

图4LEHMR路由算法的总体流程图算法流程说明：

1） 对节点各项参数进行初始化设置，包括节点的能量值，链路稳定值，能量阈值，链路稳定阈值等。

2） 首先源节点将以广播的形式进行传送，RREQ信息包中记录有：各个节点的能量值，链路稳定值，能量阈值，链路稳定阈值、源节点和目标节点的位置以及有效的路径信息。

3） 在发送RREQ节点的通信范围内的所有邻居节点将接收RREQ数据包，同时将检测自身的路有信息表，是否存在从源节点到目的节点的有效路由信息。

4） 若某节点路由信息表中存在从源节点到目的节点的有效路由信息，则向前一级节点发送RREP路由回应数据包，建立路由。若所有邻节点中都没有有效的路径信息，则各个节点判断自身的能量值和前级节点间的链路保持时间是否满足设定的阈值。

5） 根据判断条件，若节点的能量信息和链路稳定信息满足设定的阈值，则该节点继续转发RREQ路由请求数据包，继续执行3）。若节点的能量信息和链路稳定信息不满足设定的阈值，则丢弃RREQ路由请求数据包，路由请求结束。

3仿真与分析

利用NS2对LEHMR算法仿真，条件设定如下，节点数：150个，传输距离：250 m，随机分布范围：700m×700m，采用随机路径来构建节点移动模型。测试时，节点移动速度变化范围：5～25 m/s，仿真持续时间：500 s，数据包的恒定比特率为：1 000 bit，数据包固定间隔生成比率为：4包每秒。在仿真中，15个移动节点被随机配置成源节点和目标节点。

1） 网络开销

如图5所示，AODV算法和LEHMR算法相比，随着节点移动速度变大，两种算法的网络开销都会变大。AODV算法的网络开销要明显大于LEHMR算法，这是因为AODV算法没有选取最优邻居节点广播RREQ消息，LEHMR算法要求任意节点在接收转发RREQ消息前都要检查节点的能量水平和与发送RREQ包节点间的链路保持时间。这个规则减少了RREQ包的转发量，提高了路径的稳定性，因此，生成的节点路由有一个很好的链路生存周期和很好的能量水平。由图5可知：当节点的能量水平在1到4之间变化时，由于节点的能量增加，路由开销相应减少。

2） 数据转发率

从图6显示结果表明，综合考虑能量和移动因素的影响。LEHMR算法的数据包的平均转移率要高于AODV算法，通过这个可得出结论：与AODV算法相比，LEHMR算法建立的路由要稳定，具有较高的网络生存周期。LEHMR算法选择路径时，构建路由的节点都具有很高的剩余能量、节点间具有很高的链路生存周期。而AODV算法构成路由的节点没有此种功能，它们间发送了大量的冗余信息，导致了节点能量很快耗尽，因此具有较低的转发率。

3） 网络生存周期

图7显示，当增大网络节点的能量值时，网络生存周期相应增大。节点能量阈值的提高意味着若节点的能量低于阈值的，将停止转发RREQ数据包，这将造成大量的节点为节省能量而停止转发RREQ包，同时整个网络区域内的其它节点因不转发RREQ包，也节省了能量，高稳定度的路由会减少用于路由维护控制数据包，同时消耗的能量更少。

4） 网络延迟

如图8所示的仿真结果表明：LEHMR算法的延迟时间要明显优于AODV算法，因为LEHMR算法中的路由节点拥有非常好链路生存周期和能量。另外，观察到当提高链路生存周期阈值，网络的延迟时间将增大，因为在节点移动的状态下，满足这么高的链路生存周期和高能量水平的节点很难找到，数据包通过少量跳数进行转发。

4结束语

本文提出了一种基于链路稳定和节点能量感知混合模型的组播路由算法。该路由算法根据节点的剩余能量和链路生存时间来控制路由发现，在路由发现的过程中，大大减少了传感器节点间交互信息量和计算任务。仿真结果表明：该算法明显增大了数据包转移率，减小了控制开销和网络延迟。

参考文献：

[1]夏辉，贾智平. 移动 Ad Hoc 网络中基于链路稳定性预测的组播路由协议[J]. 计算机学报， 2013， 36（5）： 926-936.

[2]郑石，吴伟强. 基于能量感知的ad hoc路由算法研究[J]. 通信学报， 2012， 33（4）： 9-16.

[3]陶洋， 李冉， 李勇. 无线 Ad Hoc 网络中基于链路稳定预测的路由协议[J]. 广东通信技术， 2012， 32（2）： 43-46.

[4]曾文锋，戴建辉. 能量感知和链路稳定度的多径 MANET 路由[J]. 通信技术， 2011， 44（8）： 54-57.

[5]ZHENG Z. WDM： An Energy-Efficient Multi-hop Routing Algorithm for Wireless Sensor Networks[C]// International Conference on Computational Science， 2005.

[6]沈波. 无线传感器网络分簇路由协议 [J]. 软件学报， 2006， 17（7）： 1 588-1 600.

[7]林亚平. 传感器网络中一种分布式数据汇聚层次路由算法[J]. 电子学报， 2004，32（11）： 1 801-1 805.

[8]HONG LI. Overall energy-balanced routing protocol[J]. Computer Engineering and Applications，2010，46 （2）：86-90.

[9]LIANG W F. Prolonging network lifetime via a controlled mobile sink in wireless sensor networks[C]// In：IEEE Communications Society，IEEE Globecom 2010，Proceedings of IEEE Globecom 2010： 978-983.

[10]LU G. An adaptive energy-effieient and Low-latency MAC for data gathering in wireless sensor networks[C]// Proeeedings of 18th International Parallel and Distributed Proeessing Symposium， 2004：26-30.

[11]周杰. 移动Ad-Hoc网络的路由算法和位置管理方案[J]. 计算机工程与应用，2004（7）：22-26.

[12]唐勇. 无线传感器网络路由协议研究进展[J]. 软件学报， 2006， 17（3）： 410-421.

[13]WU K， HARMS J. Location trace aided routing in mobile ad hoc networks[C]// Computer Communications and Networks， 2000. Proceedings. Ninth International Conference on. IEEE， 2000： 354-359.

[14]任敬安，涂亚庆.基于蚁群优化的无线自组织网络能量感知路由协议与参数优化研究[J]. 计算机应用与软件， 2012， 29（9）： 66-70.

[15]蔡苏亚. 改进的最优链路状态路由协议算法[J].计算机与现代化，2014（8）：106-109.

[16]王靖，李芳芳.基于链路状态感知的无线Mesh网优化路由算法[J].计算机科学，2012，39（11）：37-40.

[17]朱斌，曾孝平.能量高效与移动预测的路由算法分析[J].重庆大学报，2010，33（10）：88-93.

[18]洪利，杨淑玲.一种全局能量均衡的路由协议[J].计算机工程与应用，2010，46（2）： 86-90.

[19]周德荣，夏龄.一种改进的AODV路由协议的实现与仿真[J].实验室研究与探索，2014，33（11）：67-71.

量子进化组播路由算法 篇3

关键词：遗传算法,早熟,量子进化算法,组播路由问题

0 引 言

随着网络和通信技术的发展,由于网络多媒体需要达到某种服务质量,组播路由服务将成为网络媒体应用的关键。组播是将相同的信息通过组播树传达给多个接受者。过去的工作主要集中在研究用于计算低代价组播树的算法,从而有效分配网络资源。研究表明,在网络中计算最小代价组播树是NP完全问题[1],针对这一问题,在过去几年里,已经提出了很多启发式路由算法[2,3,4]。然而,这些算法普遍存在的问题是算法的复杂度太大,实现复杂。仿真表明[5],这些算法得到的组播树费用通常较大。

除了启发式算法外,遗传算法作为一种全局优化算法被用于求解最小代价组播树问题[6,7],从多数仿真看来,遗传算法取得了比确定性算法更好的结果,但其易“早熟”的特性也影响了算法性能的进一步提高,特别是当搜索空间很大的时候,其求解能力更加不如人意。

为此,本文提出了量子进化组播路由算法(QEA),该算法通过量子比特的叠加性很好地利用了其并行能力,且量子比特的表达形式可以携带更多的信息[8],使得作用在量子比特上的量子变异操作能够利用更少个体数的搜索空间在更短时间内寻找全局最优解,从而使得该方法即保持了种群的多样性又兼顾到了收敛速度问题,从而有效地克服了早熟现象。仿真表明,该算法是有效可行的,且实现简单,控制灵活,随着网络规模的增大,尤其问题规模可以增加到千级,相比GA和CS具有更令人满意的结果。

1 量子进化组播路由算法

基于量子计算和进化算法相结合的研究开始于20世纪90年代,量子进化算法是一种应用于现有数字计算机的优化方法,本文中将组播路由问题转化为在有限时延内求解最小代价组播树(Steiner树),其中最小代价组播树的求解看成为一个组合优化问题,采用深度优先搜索构造满足约束的备选路径集,然后通过量子编码对备选路径集中的路径进行编码,采用量子进化算法对备选路径集中的路径进行搜索,期望找到代价最小的路径组合来构造这颗最小代价组播树。

1.1 求解备选路径集

假设Graphic是一个总节点数为n的完全图,即网络中每个节点的度都为n-1,则从网络中某一节点出发到达另一指定节点之间的可行路径共有PathCount条,大约可以计算为:

$\begin{array}{l}\text{Ρ}\text{a}\text{t}\text{h}\text{C}\text{o}\text{u}\text{n}\text{t}=1+{\rm P}{}_{n-2}^1+{\rm P}{}_{n-2}^2+{\rm P}{}_{n-2}^3+\cdots +{\rm P}{}_{n-2}^{n-2}\\ >n!(1)\end{array}$

若在这样一个网络上构建组播树,可供选择的组合数约有:

$\underset{\text{目}\text{的}\text{节}\text{点}\text{个}\text{数}}{{\displaystyle \text{Ρ}\text{a}\text{t}\text{h}\text{C}\text{o}\text{u}\text{n}\text{t}\times \text{Ρ}\text{a}\text{t}\text{h}\text{C}\text{o}\text{u}\text{n}\text{t}\times \cdots \times \text{Ρ}\text{a}\text{t}\text{h}\text{C}\text{o}\text{u}\text{n}\text{t}}}$

对于一个无约束的全连通网络来说,其备选路径集十分庞大,但是加上时延约束后便会使部分原来连通的路径因为不满足时延条件而变得不再连通,因而缩小了问题的规模。时延约束越紧,则备选路径集越小。

那么先求出从目的节点到源节点的所有满足时延条件的路径,并且将备选路径集按代价升序排列。

1.2 基于精英策略对备选路径编码

从统计学的角度来看组播问题,真正构成最优组播树的路径往往是备选路径集合中代价较小的几条,并且也可以从Prim 和Kruskal算法(即最小生成树算法)[1]中看出这个规律,这两种算法采用的都是贪婪算法的思想,逐次将与生成树之间有最短边的节点加入树中。因此,在一棵最小生成树中,从源节点到某个目标节点的路径代价一定在从源节点到这个目标节点的所有路径中较小的,但不一定是最小的。因此,有必要减少备选路径的数目,加快算法的收敛速度,缩小搜索空间,即备选路径集合。根据最小生成树算法可以假定,组成最优组播树的路径必然包含到达某些目的结点的最短路径。因此本文的算法是只选择备选路径集中代价最小的若干路径组成“Elite Group”。所以对每个目标节点包含的备选路径数目,只选择其中2N条,这样就可以用N个量子比特位表示每个目标节点的备选路径集,当有m个目的节点时,那么量子比特个体就有$\left|D\right|\times {\rm N}$个比特位,如式(2):

$q{}^t=\left[\begin{array}{ccccccccc}\alpha {}_{11}^t& \alpha {}_{12}^t& \cdots & \alpha {}_{1{\rm N}}^t& \cdots & \alpha {}_{m1}^t& \alpha {}_{m2}^t& \cdots & \alpha {}_{m{\rm N}}^t\\ \beta {}_{11}^t& \beta {}_{11}^t& \cdots & \beta {}_{1{\rm N}}^t& \cdots & \beta {}_{m1}^t& \beta {}_{m2}^t& \cdots & \beta {}_{m{\rm N}}^t\end{array}\right](2)$

这里满足归一化条件$\left|\alpha {}_{ij}\right|{}^2+\left|\beta {}_{ij}\right|{}^2=1(i=1,2,\cdots ,m$;j=1,2,…,N),并且所有αij,βij都初始化为$1/\sqrt{2}$。qt表示一个在第t代的量子比特个体完成编码后,根据其机理就可表示在0～1之间的叠加状态。

1.3 量子观测

为了计算适应度函数值,采用如下观测方式将一个量子个体生成一个二进制编码的普通个体,设Q(t)为第t代的量子个体种群,通过量子观测产生的确定解为P(t)={x${}_{11}^t$,x${}_{12}^t$,…,x${}_{1{\rm N}}^t$,…,x${}_{m1}^t$,x${}_{m2}^t$,…,x${}_{m{\rm N}}^t$},其中x${}_{ij}^t$(i=1,2,…,m;j=1,2,…,N)是一个长度为m×N的二进制串。P(t)中的每一位以$\left|\alpha {}_{ij}^t\right|{}^2$或$\left|\beta {}_{ij}^t\right|{}^2(i=1,2,\cdots ,m$;j=1,2,…,N)为概率选择得到。具体操作如下:产生一个[0,1]的随机实数,若它大于$\left|\alpha {}_{ij}^t\right|{}^2‚{\rm P}(t)$的相应位取值为1,否则取值为0。

这样就得到了一个二进制字符串,然后进行解码,比如说当N=3时,110就表示选取这一目标节点的第7条路径。当某个目标节点路总路径数为7时,111,110都表示7,然后计算组播树代价。

1.4 量子变异

基于进化算法的基本框架,采用量子比特来表示个体,设计了针对量子个体的量子旋转门变异策略。在群体内部采用量子旋转门变异加速收敛,向着组播数代价更小的状态演化,且这种策略作用在量子个体上,保持了更好的多样性,防止早熟的发生。

在量子理论中,各个状态间的迁移是通过量子门的变换矩阵得以实现[9],但用量子旋转门的旋转角度同样也可表征量子个体中的变异操作,进而方便地在变异中加入最优个体的信息,加快算法收敛。在本文中由于采用量子个体,这里使用量子旋转门,定义如下:

$U(\text{Δ}\theta )=\left[\begin{array}{cc}\cos (\text{Δ}\theta )& -\sin (\text{Δ}\theta )\\ \sin (\text{Δ}\theta )& \cos (\text{Δ}\theta )\end{array}\right](3)$

这里Δθi为旋转角度的大小,控制算法的收敛。Δθi定义如下:

$\text{Δ}\theta {}_i=\delta \cdot s(\alpha {}_i,\beta {}_i)(4)$

式中:δ为控制算法的收敛速度;s(αi,βi)为控制算法的收敛方向。如果δ值太小,收敛速度将会变缓,如果δ值过大将有可能产生早熟现象。所以在这里采取了一个根据进化代数动态选取旋转角度值的策略,使δ保持在0.1π和0.005π之间。

经变异操作后的量子比特变为:

$\left[\begin{array}{l}\alpha {}_i^{t+1}\\ \beta {}_i^{t+1}\end{array}\right]=U(\text{Δ}\theta {}_i^t)*\left[\begin{array}{l}\alpha {}_i^t\\ \beta {}_i^t\end{array}\right],i=1,2,\cdots ,{\rm N}\times m(5)$

1.5 适应度函数评价

有时还应该考虑到边数对组播树代价的影响,如果能尽可能多地利用公共路径(到不同的目的节点时重合的路径),那么就有可能减小组播树代价,所以定义适应度函数如下:

$\begin{array}{l}\text{F}\text{i}\text{t}\text{n}\text{e}\text{s}\text{s}=\text{a}\text{l}\text{p}\text{h}\text{a}\times 20.0/\text{Μ}\text{u}\text{l}\text{t}\text{i}\text{Τ}\text{r}\text{e}\text{e}\text{C}\text{o}\text{s}\text{t}+\\ (1.0-\text{a}\text{l}\text{p}\text{h}\text{a})\times 1.0/\text{Τ}\text{r}\text{e}\text{e}\text{e}\text{d}\text{g}\text{e}\text{s}\text{C}\text{o}\text{u}\text{n}\text{t}\end{array}$

式中alpha∈[0.5,1.0]。

1.6 终止条件

实际应用中一般采用限定进化(运行)代数或在连续若干次进化(运行)中群体的最优解都没有改善,以及二者的混合形式作为终止条件。本文综合考虑最大进化代数作为本文算法的终止条件。

1.7 算法复杂度分析

假设网络规模为n,目的节点数为m,备选路径集为P,种群规模为M,算法迭代次数为g,则寻找备选路径的复杂度为O(n);对备选路径进行升序排列的复杂度为O(log P);寻找最优组播树的时间复杂度为O(g×M×m),所以算法的时间复杂度近似为:O(g×M×m)+O(log P)+O(n)。

通过化简,算法总的时间复杂度近似为:O(n2×m)。

但是BMSA算法的时间复杂度为[2]O(n3×log n),从时间复杂度上看QEA优于经典的启发式算法BMSA。

2 仿真实验比较研究

仿真网络的生成采用了改进的Waxman随机网络模型[5],它保证了生成网络的连通性,并保证每个节点的度数大于等于2。以GA和CS为比较基础,采用如下的性能指标:

$R{}_{\text{c}\text{o}\text{s}\text{t}}=\frac{1}{{\rm T}}{\displaystyle \sum _{i=1}^{{\rm T}}\frac{\text{C}\text{o}\text{s}\text{t}({\rm T}{}_{\text{Q}\text{E}\text{A}})}{\text{C}\text{o}\text{s}\text{t}({\rm T}{}_{(\text{G}\text{A})\text{o}\text{r}(\text{C}\text{S})})}}(6)$

式中:T表示实验次数;R值小于1表示QEA的平均性能优于GA和CS,R值变大,则说明QEA的平均性能变差,其中这里考察了算法的组播树的代价方面的性能。实验中,QEA的参数设置如下:种群规模M=10,N表示在QEA算法中用N个量子比特表示备选路径集中的一个目的节点。CS的参数设置如下:种群规模M=10,克隆规模20,变异概率pm=0.6;遗传算法的参数设置如下:种群规模M=10,变异概率pm=0.03,交叉概率pc=0.6。k表示在CS和GA算法中对于每个目的节点的备选路径集只选择其前k%条。为了比较的公平性,所有算法都只迭代100次。所有实验结果均是在独立运行30次的基础上得到的。

实验1:算法随网络节点数增长的性能比较

图1为d/n=15%(d是目的节点数,n是网络规模数)组播树代价与网络规模的性能比较,其中k=20表示在CS和GA算法中对于每个目的节点的备选路径集只选择其前k%条,N=3表示在QEA算法中用N个量子比特表示一个目的节点的备选路径集。从图1中可以看出,在不同的参数下QEA算法都是优于GA和CS算法的,并且在同时缩小备选路径的情况下随着网络规模的增大QEA有下降的趋势,这说明QEA更适合于大规模网络。且R小于1且比较稳定,这充分表明QEA较GA和CS算法具有更优的性能和良好的扩展性。

实验2:算法随目的节点数增长的性能比较

从图2中可以看出,在网络规模为1 000的情况下,随着目的节点数不断增加的情况下,QEA算法也能获得较低的组播树代价,并且呈现出下降趋势,这说明QEA算法比GA和CS算法具有更强的搜索能力。

3 结 语

本文中提出了一种量子进化算法用于解决组播路由。通过应用量子计算的原理,用一组量子比特表示一个个体,提高了种群的多样性且在一定程度上避免了早熟的发生,再通过使用量子门旋转门策略加速了算法的收敛。通过大量仿真实验表明该算法的搜索能力强于GA算法和CS算法,并且算法操作简单,易于实现,所用的时间也明显小于二者。但由于采用构造备选路径集的方法,其复杂度会随着网络规模的增加而成平方级增长,因此,接下来研究分布式量子进化组播路由算法,期望降低备选路径集的复杂度。

参考文献

[1]WAXMAN B M.Routing of multipoint connections[J].IEEE Journal of Selected Areas in Communications,1988,6(9):1617-1622.

[2]PARSA M,ZHU Q,GARCIA-LUNA-ACEVES J J.Aniterative algorithm for delay-constrained minimum-cost mul-ticasting[J].IEEE/ACM Trans.on Networking,1998,6(4):461-474.

[3]KOMPELLA V P,PASQUALE J C,POLYZOS G C.Multicasting for Multimedia applications[C]//EleventhAnnual Joint Conference of the IEEE Computer and Com-munications Societies.Piscataway,NJ,USA:IEEEPress,1992:2078-2085.

[4]SUN Q,LANGENDORFER H.Efficient multicast routingfor delay-sensitive applications[C]//Proceedings of the 2thWorkshop on Protocols for Multimedia Systems.[S.l.]:[s.n.],1995:242-458.

[5]SALAMA H F,REEVES D S,VINIOTIS Y.Evaluationof multicast routing algorithm for real-time communicationon high-speed networks[J].IEEE J.on Sel.Areas inComm.,1997,15(3):332-345.

[6]王新红,王光兴.基于遗传算法的时延受限代价最小组播路由选择方法[J].通信学报,2002,23(3):112-117.

[7]HAGHIGHAT A T,FAEZ K,DEHGHAN M,et al.GA-based heuristic algorithms for bandwidth-delay-constrainedleast-cost multicast routing[J].Computer Communication,2004,27(1):111-127.

[8]JIAO L C,LI Y Y,GONG M G,et al.Quantum-inspiredimmune clonal algorithm for global optimization[J].IEEETransactions on System,Man,and Cybernetics,Part B,2008,38(5):1234-1253.

组播路由器 篇4

Ad Hoc网络终端具有路由功能, 是由一组带有无线收发装置的可移动节点组成的一个多跳的临时性自治系统。Ad Hoc网络不依赖于任何基础固定设施, 不相邻的节点间进行通信需要中间节点中继。由于网络中的节点可以任意移动, 所以网络拓扑是动态变化的。Ad Hoc网络具有独立组网能力, 以及自组织性、无中心、动态性、易于铺设等特点, 因而被广泛应用于紧急救援、道路交通、军事战场、偏远野外和探险等临时信息系统的建设[1,2,3], 成为当今的一个研究热点。

路由协议的设计大多着眼于最小跳数路由的研究, 即需要通信的源节点和目的节点在选择路由时, 选择利用最少数量的中间节点中继就可以到达的路径。由于Ad Hoc网络采用无线通信, 并且网络中的通信终端可以自由移动, 因此通信能力受到节点移动性、节点能量和通信范围等的影响较大。这就造成了无线链路频繁断裂的可能。当一条路径上的任何一个链路断裂时, 这一路径就必须找到另一条可用的链路来恢复连接, 或者断裂路径被新发现的另一路径所代替[4]。这些重路由操作大大消耗了有限的网络资源和节点能量, 从而极大地降低了网络的通信性能。因此设计一个选择稳定路径的路由协议, 尽量减少重路由操作, 具有非常重要的意义。

目前也出现了一些对稳定路由的研究, 文献[5]利用一种权重的思想进行稳定路由的选择, 文献[6]利用GPS定位获得节点位置的思想进行稳定路由的选择, 文献[7]利用预测路由生存时间的方法来选择稳定路由。这些都只考虑到节点的移动对路由稳定性的影响, 并没有考虑节点能量对稳定性的影响。由于Ad Hoc网络中, 节点能量是有限的, 一旦能量耗尽, 节点将无法工作, 使得两节点间的链路断裂, 整条路由就会失效。因此考虑路由的稳定性必须考虑能量的影响。

1 链路稳定性模型

在Ad Hoc网络中, 整条路由是由两个节点间的链路组成的, 因此考虑路由的稳定性, 需要选择具有稳定性的链路。两个节点间链路的稳定性主要由两个因素来决定:节点间的距离和节点的能量。信号的强度与信号的传输距离有关, 所以链路连接需要两个节点间的距离小于节点信号的有效传输距离。节点的可利用能量越多, 在数据发送过程中才能保证路由不会因能量的消耗而失效。

1.1 节点间距离

假设在Ad Hoc网中所有节点的有效传输距离相同, 均为R, 节点的信号传输能力一致, 信号的强度仅与信号的传输距离有关。所以在某一时刻, 链路保持连接只需要两个节点之问的距离小于节点信号的有效传输距离R。在移动自组织网中, 节点不是固定的, 而是可以自由移动的。两节点在这一时刻处在有效传输距离内, 在下一时刻可能已经移出这一距离范围。因此, 不能用某一时刻的节点间距作为衡量指标。链路保持连接的时间越长, 这条链路才能越稳定。

文献[8]提出通过GPS获得移动节点的位置、运动速度和运动方向对链路可能保持连接的时间LET (Link Expiration Time) 进行了预测。设某时刻节点i, j可以直接通信, (xi, yi) , (xj, yj) 分别为它们的位置坐标, 用vi, vj分别表示两节点的速度, 用θi, θj分别表示两节点的方向, 则节点i, j保持连接的时间预测公式为:

${\rm T}{}_{ij}=\frac{\sqrt{(a{}^2+c{}^2)R{}^2-(ad-bc){}^2}-(ab+cd)}{a{}^2+c{}^2}(1)$

其中:a=vicos θi-vjcos θj, b=xi-xj, c=visin θi-vjsin θj, d=yi-yj。

1.2 节点能耗

Ad Hoc网络中的节点不仅能看作数据传输的终端, 而且可作为路由器来帮助超出传输范围的终端交换数据时进行中继。Ad Hoc网的一个重要问题是活动的节点是能量受限的。目前考虑到能量问题的路由协议并不多。MTPR (The Minimum Total Transmission Power Routing) [9]提出最小化传输中需用的能量, 但是它并没有考虑到剩余节点的能量, 不能延长每个节点的生存时间。MMBCR (The Min-Max Battery Cost Routing) [10]考虑到了剩余节点的能量问题, 它比较每条路由剩余能量最小的节点, 选择这些节点中具有最大能量的节点所在路由, 但是它却没有考虑到整体的能量消耗问题。

在实际应用中, 自组织网中节点通信能量的开销要远远大于数据计算的能量开销, 因此可以主要考虑节点在通信时的能量消耗。根据文献[11]提出的模型:

$E{}^c=a\cdot \text{s}\text{i}\text{z}\text{e}+\text{Δ}E(2)$

其中:Ec表示节点消耗的能量;a为发送单位数据所需消耗的能量;size为数据包的大小;ΔE为节点其他情况下的能量消耗。

从 (2) 式可以看出能量的消耗与数据传输的大小成线性关系。数据的传输存在发送和接收两种状态, 在这两种状态下所消耗的能量不同, 设节点初始能量为E0, 由 (2) 式可得节点i的剩余能量:

$\begin{array}{l}E{}_i=E{}_0-E{}_i^c=\\ E{}_0-(r{}_i\cdot \text{s}\text{i}\text{z}\text{e}{}_i^r+s{}_i\cdot \text{s}\text{i}\text{z}\text{e}{}_i^s+\text{Δ}E{}_i)(3)\end{array}$

其中:E${}_i^c$表示节点已消耗的能量, ri表示节点i接收单位数据消耗的能量, size${}_i^r$是节点i接收数据包的大小, si表示节点i发送单位数据消耗的能量, size${}_i^s$是节点i发送数据包的大小。

可以看出, 每个节点根据自己的数据包的发送和接收就可以得到自己的剩余能量, 这样可以节省网络中节点能量信息的传递, 节省了开销。

1.3 组播路由稳定性指标设计

由于节点间距和节点能量均对路由稳定性产生影响, 因此可以采用通用加权的思想将两者结合起来。设节点i为节点j的下游节点, 它们之间的链路为Lij, 将由式 (1) 和式 (3) 得到的链路生存时间Tij及下游节点i的能量作为链路Lij的稳定性指标, 设为Wij, 将两个指标的权值分别设为aij和bij, 其中aij+bij=1, 则该指标为:

$W{}_{ij}=a{}_{ij}{\rm T}{}_{ij}+b{}_{ij}E{}_i(4)$

Wij值越大, 说明Lij稳定性越好。当Tij很小, 而Ei很大时, 由式 (4) 得出的结果可能也会符合要求, 为避免这样的结果, 将上式的权值公式用相乘的形式来写:

$W{}_{ij}={\rm T}{}_{ij}{}^{a{}_{ij}}E{}_i{}^{b{}_{ij}}(5)$

由式 (5) 得到的Wij只要有一项指标为零, 不论其余的指标有多大, 得到的总指标都将为零, 这样可以避免由式 (4) 带来的极端情况。将式 (5) 两端取对数, 得到:

lg Wij=Tijlg aij+Eilg bij

此式又成为通用加权公式的形式。因此链路Lij的稳定性指标Wij可用式 (5) 得到的公式表示。

2 LSMRP路由协议

路由是由两个节点间的链路组成的, 将上面得到的链路稳定性指标设计到组播路由协议中, 该协议称为LSMRP (Link Stability for Multicast Routing Protocol) 。LSMRP是按需驱动的组播树路由协议。

2.1 组播树的创建

组播树的创建过程如下:

(1) 每个组播组有一个组长, 负责维护和更新本组的序列号, 并定期用Group Hello包向全网广播该组序列号。节点通过发送RREQ-J发起加入组播组请求。如果该节点的组长表中有该组的项目, RREQ-J以单播发送给该组的组长;否则, RREQ-J以广播发送。接收到RREQ-J的节点在组长列表中检查是否有该组的项目, 如果没有, 节点将RREQ-J的组地址以及RREQ的源地址记录入组长列表。每个RREQ-J包都包含发送该包节点的位置信息, 每个接收到RREQ-J包的节点通过计算W值, 对链路进行稳定性判断。将W与预先设定好的门限值V进行比较, 若W≥V就认为该条链路是稳定的, 建立到源节点的反向链路, 并将RREQ-J重新广播, 否则就认为该条链路不稳定, 丢弃该包。

(2) 收到RREQ-J的组播树成员向源节点单播发送RREP-J以回复加入请求。 RREP-J沿RREQ-J传输时建立的反向路径传送。RREP-J传输时, 沿途节点在组播路由表中创建对应该组的项目, 并把上游节点设置成将RREP-J转发给它的邻居节点。

(3) 源节点在发送完RREQ-J等待一段时间后, 通常会接收到多个RREP-J。源节点选择具有最大序列号和最小跳数的路径, 并向下游节点单播发送MACT-J。MACT-J沿RREP-J传播时建立的正向路径传输。所有接收到MACT-J的节点在组播路由表中设置下游节点, 这样一个更新的组播树就建立好了。

如果源节点在重试若干次加入请求后仍然没有接收到回复, 说明该组播组在网络上不存在或者不可达。源节点成为新组的组长, 并负责维护该组的信息。

2.2 组播树的维护

(1) 若非叶节点想离开组播组, 则需要作为树成员保留。

若叶节点要离开组播组, 它首先将组播路由表中对应该组的路由项删除, 并向上游链路发送MACT-P通知上游节点它要离开组播树。接收到MACT-P的上游节点将退出组播树的下游节点从组播路由表中删除。如果上游节点删除自己的下游节点后成为叶节点且不是组成员, 该节点也向上游节点发送MACT-P退出组播组。上述的过程会重复进行直到达到一个组成员或者非叶节点。

(2) 由于节点的移动以及能量的消耗, 每条链路的W是变化的。

因此每隔一段时间, 链路的下游节点就对链路稳定性进行重新判断, 若发现W<V, 则说明该条链路不再稳定, 下游节点需要找到一条新的稳定链路代替。在新的稳定链路没有找到, 而有数据需要发送时, 仍然使用该链路。在寻找新的稳定链路时, 该下游节点发起一个到多目标组组长节点的RREQ-J包, 多目标树上的任一个具有足够新的序列号的节点, 当收到该包并进行稳定性链路判断后, 都可以发送一个RREP-J包来响应该下游节点的请求包。这个下游节点在限定的时间里收到若干个RREP-J包, 选择具有最大序列号和最小跳数的路径建立路由。路由建立后, 即可断开原链路。

由于多次局部重建, 会导致组播树是一个非最优树, 因此每隔一段时间要由源节点重新发起一个路由发现过程, 以连接到组播树上。

3 仿真分析

为了评测LSMRP协议的性能, 使用NS-2[12,13]仿真工具对其性能进行模拟研究, 并与Ad Hoc网络中典型的组播路由协议MAODV[14]进行比较。

3.1 仿真环境设置

在800×800单位的平面区域, 随机布置50个节点, 仿真时间为100 s, 数据包大小为512 B, 节点平均移动速度分别为1 m/s, 5 m/s, 10 m/s, 15 m/s, 20 m/s和25 m/s, 研究节点不同的移动速度下丢包数和投递率的变化。为了防止仿真中极端环境的影响, 每个不同速度, 产生多个场景环境, 记录所得数据的平均值。

3.2 仿真结果及其分析

图1为丢包数随节点移动速度的变化。可以看到, 随着节点移动速度的增大, MAODV和LSMRP的丢包数均增大。这是因为节点速度变大, 网络的拓扑变化也加快了。在相同移动速度下, LSMRP明显比MAODV的丢包数少, 而且速度越大, 丢包数差值越大。这是因为, LSMRP在建立路由前对链路的性能进行比较, 选出具有较高连接性的链路, 可大大降低丢包数。

图2为投递率随节点移动速度的变化。可以看到, 当节点移动速度低于5 m/s时, 两种协议的投递率都保持在80%以上, 但当移动速度加快时, MAODV的投递率急速下降, 当移动速度高于15 m/s时, 它的投递率不能达到70%。而LSMRP协议在节点移动速度为25 m/s时, 投递率仍能高于70%。这是因为LSMRP在路由选择上对链路生存时间和节点能量进行了综合考虑, 并且及时的链路修复保证了它较高的投递率。

4 结 语

LSMRP是一种考虑路由稳定性的组播路由协议。它综合考虑了节点移动以及节点能量对路由稳定性的影响, 所选路径能够维持较长时间的连接以及传输数据的节点具有较高的能量, 并且采用在链路断裂前进行修复的机制。仿真结果证明, LSMRP能够降低网络丢包数, 并且提高了数据传输的可靠性。每条链路选择了具有较优性能的稳定链路, 因此延长了路由生存时间, 从而延长了网络生存时间。

该协议在路由建立时, 会对链路性能进行比较, 会增加网络时延, 对于有快速数据传输要求的网络不适应。另外, 在链路未断而即将断裂时就会进行路由修复, 会对资源和节点能量造成浪费。因此还需在路由修复上进行改进。

组播路由器 篇5

移动Ad Hoc网络是一组具有路由功能的移动节点组成的一个多跳的临时性自治系统, 这种无线网络由于没有基础结构, 故而组网非常方便、灵活, 广泛应用于灾难救助、临时会议、战场知会等场合。这些应用有一个共同的特征, 就是一到多或多到多的数据传输。而组播在传输组方通信的数据时, 不仅能够减轻发送源系统的处理负荷, 也降低了网络带宽的使用。为了提高移动Ad Hoc网络组播路由的性能, 研究人员提出了多种组播路由算法。下面根据不同的分类方法对移动Ad Hoc网络组播路由协议经行介绍。

2 组播路由协议

组播路由协议是实现组播的基础, 其功能主要是形成一定的机制来完成组播任务。目前已经提出了不少移动Ad Hoc网络组播路由协议, 要研究和比较这些组播路由协议, 采用适当的分类方法是非常重要的。分类方法可以帮助研究者理解不同的组播路由协议的特点和内在联系。

2.1 表驱动和按需组播路由路由协议

根据组播路由协议路由信息建立和维护时机的不同可以分为两大类:表驱动路由协议和按需组播路由协议。表驱动组播路由协议每个节点路由表中记录了最新的拓扑信息, 当节点有数据发送时, 能够根据路由表迅速找到到达目的节点的路经, 即分组发送时延小。但它需要大量的控制报文, 造成路由协议开销增大。代表协议有AMRIS[1]、CAMP、LGT[2]。按需组播路由协议不需要维护网络的拓扑结构, 仅当需要时才查找相应的路由, 节省了路由维护的开销, 但查找路由会引起较大的时延, 不适应时延敏感型应用。代表协议由ACMP、CQMP[3]。

2.2 基于树、基于网格网格和基于混合结构组播路由协议

这是一种广泛的组播路由分类方法, 它根据通往组成员的路由产生方法的不同进行分类。主要分为3类:基于树、基于网格、混合型组播路由协议。

基于树的组播路由协议根据组播树根节点的位置进一步划分为:基于源树和基于核心树组播路由协议。在基于源树的组播路由协议中, 源节点就是组播树的根节点, 且由源节点进行组播树的建立和维护。这要求源节点必须知道网络的拓扑信息和接收节点的地址。因此, 基于源树的组播路由协议有非常高的管理开销。AMRoute[4]就是此种协议典型的例子。在基于核心树组播路由协议中, 由核心节点进行数据发送和组播树的建立、维护。与基于源树的组播路由协议不同, 组播树的根节点是核心节点。MAODV[5]、STAMP和ACMP就是基于核心树组播路由协议的代表。

在基于网格的组播路由协议中, 数据包沿着网格进行传送。利用广播进行路由发现, 用核心或者中心节点发送数据包建立网格。与其他协议相比, 当节点在高速运动时, 基于网格的组播路由协议性能最好, 因为从源节点到目的节点网格提供了冗余路径。CQMP[3]、E-ODMRP[6]和BODS都是基于网格的组播路由协议的典型代表。

基于混合结构组播路由协议充分利用树结构和格网结构各有优点, 研究人员将两种思想结合起来, 提出了基于混合结构的组播路由协议, 这种混合结构的基本思想是在格网结构基础上建立组播树。这种协议的优点是, 传输数据使用组播树, 具有树的数据转发效率高的特点;同时, 由于组播树是建立在格网之上的, 当节点间的链路断开后, 无需重构组播树, 因此具有较好的健壮性。EHMRP是此类协议的典型代表。

2.3 节点能力、网络结构、位置组播路由协议

大多数组播路由协议都假定节点拥有相同的网络资源和计算能力, 且移动节点组成的网络是扁平的。实际上, 这种假定并不是经常成立, 因为许多不同的移动节点拥有不同的角色、能力、移动类型。在基于结构组播路由协议中, 移动节点是分层结构的, 并且能够形成不同层次的节点, 在每个层次上都建立一个组播结构, 在其中进行高效的数据传送。而在基于位置组播路由协议中, 节点利用GPS或者其他定位系统获取地理信息, 通过发一个包确定目的节点的地理信息, 然后以地理信息作为依据将数据发送到转发节点, 由转发节点确定下一步路由, 直至转发到目的节点。LGF和SPBM是典型的基于位置组播路由协议。

2.4 服务质量

大多组播路由协议都是以最小平均跳数或者最小数据业务量作为判据进行设计。当考虑服务质量时, 一些路由协议就显得非常的不切实际, 主要由于缺乏网络资源, 过多的计算开销, 缺乏对全局网络状态的了解或过多的信息处理开销。Qo S组播路由不仅要求找到从源节点到目的节点路由, 而且必须满足端到端Qo S要求。移动Ad Hoc网络在许多领域有大量的应用, 一种考虑带宽、延时、包丢失率、路由协议开销的Qo S判据应该被提出。MCEDAR就是基于Qo S组播路由协议的典型。

2.5 能量效率

在移动Ad hoc网络中每一个节点既是通信终端又必须具有路由功能, 所以能量约束问题成了移动Ad hoc网络的一个非常重要的问题。在一次通信过程中, 不可能给电池充电或更换电池, 如果部分节点的电池被耗尽。整个网络将变成几个分离的网络, 网络的生命周期减少。在设计Ad hoc路由协议时如何考虑能量约束, 尽量延长网络中每个节点的寿命是一个关键问题。MWIA、RB-MIDP和D-MIDP就是高效能量组播路由协议的典型例子。

2.6 网络编码

网络编码是近年来通信领域的重大突破, 其基本思想是网络节点不仅参与数据转发, 还参与数据处理, 这样可以大幅提高网络性能。网络编码除了能够提高系统的容量外, 在数据压缩、负载均衡、降低节点能量消耗、减少传播时延、提高网络健壮性及信息安全等方面都有重要的应用前景。它已被证明是可以逼近网络容量理论传输极限的有效方法, 已被国际学术界和美国军方认定为解决网络问题的重要手段。

2.7 可靠的组播路由协议

在移动Ad hoc网络中, 每个移动的节点都是通过无线链路进行连接的, 这导致组播路由很容易丢失数据, 使组播路由不可靠和效率较低。因此, 可靠组播问题成为了一个极具挑战性的课题。研究人员已经提出了一些Ad hoc网络可靠组播协议, 根据修复机制的不同, 将移动Ad hoc网络可靠组播协议分为基于ARQ、基于Gossip和基于FEC三类。典型例子有BEMA和Re MHoc。

2.8 重叠组播播路由协议

在大多协议中, 协议必须维护从源节点到目的节点的一条通路, 从而, 协议必须探测和恢复由组成员或非组成员移动带来的失败链路, 这需要大量的控制信息。通过Overlay组播路由协议减少在网格或树结构中的非组成员的移动引起的重新配置数量, 可以提高包传送率。OMHF就是此协议的典型例子。

2.9 单源、多源组播路由协议

在网络中, 由于不同种类的服务和应用同时进行, 则一个组播组可能包含多个源。每个源组播路由协议都需要付出大量的管理开销, 从而在多源组播环境中将浪费大量的网络资源。因此, 研究者提出利用“簇”的方法, 将一个庞大的网络分为几个具有簇头的子网络, 每个簇头维护本簇的信息, 且防止无用的泛洪包和浪费带宽资源。因此, 在移动Ad hoc网络中就能获得高效的多源组播路由协议了。组播路径维护和簇技术能够应用在动态网络拓扑中, 这将是很大的优势。

3 结论

在移动Ad Hoe网络中实现组播应用是一个崭新的域, 目前国内的研究者对组播路由协议及算法的研究还处于起步阶段。移动Ad Hoe网络应用环境的不同, 导致了组播路由协议性能的不同。从文中所述的组播路由协议可以看出, 不同类型的组播路由协议具有自身的优缺点, 以及不同的应用场合。同时由于在下一代通信网络中, 移动Ad Hoe网络应用还需要与固定网络和移动网络环境应用结合起来, 因此, 移动Ad Hoe的组播路由协议和算法还需要进行深入的研究, 以适应移动Ad Hoe网络的应用需求。

摘要：近年来, 研究者已经提出了各种各样移动Ad Hoc网络组播路由协议。这些组播路由协议拥有不同的特性和采用不同恢复机制。对这些路由协议做全面了解和归纳现有的观点可以为组播路由协议设计者提供便利。我们根据组播路由协议的性能和设计特点进行分类, 帮助移动Ad Hoc网络组播路由协议的研究者和应用开发着确定合适的组播协议进行研究。

关键词：移动Ad HOC网络,组播路由,分类,网格,树

参考文献

[1]C.W.Wu, Y.C.Tay, C.K.Toh, Ad-hoc Multicast Routing Protocol Utilizing Increasing Id-numbers (AMRIS) Functional Specification, Internet draft, November1998.

[2]K.Chen, K.Nahrstedt, Effective loca-tion-guided tree construction algorithms for small group multicast in MANET, Proceedingsof the INFOCOM (2002) 1180-1189.

[3]H.Dhillon, H.Q.Ngo, CQMP:a mesh-based multicast routing protocol with consolidated query packets, in:IEEE Wireless Communications and Networking Conference, WCNC2005, pp.2168-2174.

[4]E.Bommaiah et al., AMRoute:Ad-hoc Multicast Routing Protocol, Internet draft, Au-gust1998.

[5]M.Royer, C.E.PerKins.Multicast Ad Hoc On-Demand Distance Vector (MAODV) Rout-ing, IETF Internet Draft, draft-i-etf-manet-maodv-00.txt, 2000.

无线自组织网络组播路由协议的研究 篇6

关键词：组播,无线自组网,路由

1 研究背景

无线自组织网络[1]不仅能利用移动终端之间的自组织功能,灵活自组织构建成网状架构,消除网络传输瓶颈,而且能使用路由协议根据网络状态灵活选择单播、组播和广播路由方式。然而,无线网络固有的链路鲁棒性差、报文传输可靠性低的难题制约了自组织网络的组播应用。因此,研究无线自组织网络中的组播路由协议具有非常重要的作用。

2 组播理论研究

本文首先对典型的组播路由协议包括基于洪泛FLOOD、基于树型的MAODV及基于网状结构的ODMRP和PUMA进行理论分析与比较。1) PUMA和FLOOD都使用洪泛技术。PUMA先单跳广播,到达组播组后组内洪泛数据;FLOOD仅是简单全网洪泛数据。因此,FLOOD虽不需要控制报文,但在稀疏网络或者发送节点增多的情况下,网络中数据报文成几何倍数递增,导致大量延迟和报文丢失。因此,理论认为PUMA性能优于FLOOD。2) PUMA和MAODV都是面向接收者的组播协议。PUMA是基于网状结构的,接收节点存在冗余路径。而MAODV是基于树型的,接收节点和发送节点仅存在单条链路。当组播树枝因故障而断开时,会因链路断开出现报文丢失,而后链路修复的控制报文可能与网络中报文发生碰撞,使得网络传输环境恶化。因此,理论认为PUMA性能优于MAODV。3) PUMA和ODMRP都是基于网状的组播协议。ODMRP是面向发送节点的,发送节点增多的情况下,控制报文数量急剧增加。因此,理论认为PUMA性能优于ODMRP。

3 仿真性能分析

由于自组织网络拓扑结构的动态性,理论上建立和维持一个有效的组播分布结构很可能是无效的。为此,该文为FLOOD、MAODV、ODMRP与PUMA搭建NS-2仿真环境进行性能对比。在1000*1000的无线环境中,1个组播组,起始时刻接收节点加入组播组中,30秒开始发送CBR,900秒结束,每秒发送2个CBR,CBR长度为256kbytes,仿真时长为910秒。节点移动速度为2米/秒。发送者数分别为1、2、5、10,组播成员数分别为5、10、20、30、40。

本文选择比较四种协议在30个接收节点,不同数量发送节点的报文投递率和端到端延迟的比较;5个发送节点,不同数量发送节点的报文投递率和端到端延迟的比较。仿真结果显示:

当接收节点固定,发送节点少于5个的情况下,FLOOD报文投递率与PUMA几乎持平,略优于ODMRP;但是发送节点数量超过5个后,FLOOD报文投递率要比PUMA和ODMRP低10%左右。这是网络中FLOOD广播数据报文骤然增多,数据链路报文碰撞概率增大,必然影响到数据报文传输的投递率。当发送节点固定5个,而接收节点增多的情况下,FLOOD性能低于PUMA,但略高于ODMRP。这是因为ODMRP接收节点增多而新增网状结构,冗余链路增多,控制报文数量增多,导致数据报文投递率下降。而PU.MA使用核心节点管理组播组,接收节点增加仅扩充网状结构,而网络中控制报文数量增加有限,故报文传递率较高。因此,在发送节点数量适中且接收节点数量较多的场景中,PUMA协议报文投递率高于其它三种路由协议。

在发送节点少的情况下,FLOOD网络延迟略低于PUMA和ODMRP。但随着发送节点的增多,网内洪泛报文数量猛增,网络延迟增大,发送节点增至10个时其网络延迟最大超过2秒。ODMRP和PUMA延迟均超过1s,且ODMRP略优于PUMA。这是因为发送节点的增多,它们维护网状结构的控制报文增多,故此时端到端延迟都很高。而且PUMA采用周期性广播方式维护组播结构,这导致网络修复过程中将额外新增延迟。接收节点增加对PUMA、ODMRP和FLOOD延迟影响不大。接收节点少的情况下,ODMRP4延迟少于0.01s,略优于PUMA。随着接收节点增多,在40个接收节点的情况下,ODMRP延迟与PUMA之间差距很小。因此,在发送节点较少、节点移动速度较慢的场景中,ODMRP端到端延迟略优于PUMA,而PUMA端到端延迟则比MAODV和FLOOD要低很多。

4 结束语

组播路由器 篇7

1 概述

满意度最早被许多学者作为一种准则提出。从H.A.Simon的令人满意准则，任平的满意优化准则[2]，到靳蕃的神经计算满意解输出准则[3]。这些研究的共同点就是用满意准则来代替传统的最优化准则，并逐渐走向具体化、应用化。满意函数是满意标准的数学表达式，它将问题的解映射为用户对解的满意程度。满意度函数是为了满足科研与工程计算的需要，对一些常用的、易操作的、合理的表示形式进行了量化描述。满意问题比最优化问题更具一般性，其典型的解题步骤包括问题识别、模型建立、满意度设计、求解和评价等。

2 应用

2.1 问题概述

网络服务质量(QoS)是指数据流通过网络时的性能。服务质量在CCIT建议中描述为服务质量是服务表现的综合效果，它决定了用户对服务感到满意的程度。QoS路由问题可分为4大类：单播、组播、广播和选播。文中着重研究多约束条件下的组播路由算法。组播技术的优点主要体现在以下几个方面：带宽、服务器负载和网络负载。为进行有效的组播通信，确定组播路由是非常关键的，组播路由算法就是用来确定组播树的。

2.2 模型建立

QoS组播路由问题是典型的多目标优化问题，是NP完全问题，要想找到问题的最优解计算成本太高，将失去应用价值。所以，人们通常退一步求取该问题的次优解，即通过某种寻优算法，找到问题的若干潜在解，并通过某种评价体系去评价这些潜在解，最终筛选出认为“满意”的解。QoS组播路由是由单参数多目标的优化问题，该问题的惟一系统参数组播数，T=(VT,ET)，其中VT∈V,ET∈E。设评价组播树T的性能指标(QoS度量)有4个，构成性能指标集Q:Q={(q1,q2,q3,q4)|qi∈1,2,3,4}。其中，q1,q2,q3,q4分别代表组播树的代价、时延抖动、丢包率等4个QoS度量。

2.3 遗传算法

采用源结点到各目的结点的路径集合来表征一棵组播树。目标函数采用前面小节给出的综合满意度函数，且个体的适应值与目标函数值成正比。即目标函数值越大，个体的适应值就越高，采用线性排序的方法分配个体的适应值。采用赌轮盘选择机制来选出种群的优良个体。交叉算子是按照一定的概率选择两个个体分别作为父个体和母个体，依次计算出父母个体中路径集合每条路径的目标函数值综合满意度值，比较父母个体到同一个目标结点路径的目标函数值，将值大者遗传给子个体。依次重复这个比较过程，直到遍历所有的目的结点，最后得到一个新的子个体。交叉完成后，新的子女个体以概率p进行变异，完成变异算子的设计。

3 计算结果

使用Waxman随机网络模型[4]生成网络拓扑结构。网络结点在4200×2400km2的矩形区域随机产生，网络中任意两个结点i和j之间的链路按照以下概率产生。

其中L为网络中结点间距离的最大值。d(i,j)为结点i和结点j之间的欧式距离。参数α表示取值[0,1]的实数，用来控制长链路和短链路的比率，当∂增大时，长链路和短链路的比率岁随之增大。参数β表示取值[0,1]的实数，用来控制网路结点的平均度数，当β增大时，网络链路的密度随之增大。用Waxman提出的方法生成的网络并不保证一定连通，通常在实际使用中，需要在生成算法之后检测网络拓扑图，对孤立的结点需添加链路将其连入网络。

统一设定网络拓扑生成器的参数为：α=0.25，β=0.4，结点的平均度数为4，这样生成的网络拓扑接近实际网络。

3.1 对照算法

在研究QoS组播路由问题过程中，许多学者提出了启发式算法。这些算法大多是以时延为约束条件的，即在给定时延限制的情况下，找到一棵符合时延约束的、代价最小的组播树，其中著名的有KPP、CDKS、BSMA算法等。为了验证文中提出的多目标满意优化一遗传算法的计算质量，需要将一些性能指标与KPP等算法[5,6]进行比较。

3.2 算法结果

由于KPP等算法找寻的是最小代价组播树，而文中将链路的剩余带宽作为代价指标，组播树代价越大越好。为了便于比较，在计算前规定，用链路的已用带宽作为链路代价，将组播树代价统一为最小代价。做法是把MRSIM软件的拓扑生成器生成的链路带宽固定为155Mbps，链路的剩余带宽在10Mbps至120Mbps间随机分配，用固定带宽减去当前剩余带宽就得到了链路的已用带宽。

用Matlab软件实现了提出的算法。遗传算法的初始种群设为120，为了精确地模拟生物进化的过程，本文引入了种群迁移的策略，将120个初始个体分为4个子种群，分别为40,20,20,40，在进化过程中每隔5代在各个子种群间交换各自的优良个体，以避免遗传算法过早陷入局部最优解。最大进化代数为60，交叉概率为0.9，变异概率为0.1。在此过程中，当个体的综合满意度大于0.6时，算法提前终止。在计算之前，首先用MRSIM软件生成网络拓扑，在生成的拓扑图中随机选择m个结点作为组播终点集，再随机选择除这m个节点之外的某个结点作为组播源点，得到源结点与目的结点。

下面测试各算法计算出的组播树的代价。设用户所需要QoS参数为：带宽要求Bmin=8.0Mbps，时延要求Dmax=60ms,时延抖动要求Jmax=10ms，丢包率要求Lostmax=10-3。设定网络流量模型WFQ的参数为：

图1为组播树代价和网络结点数n的关系。网络结点数n由20变化到100，目的节点数m=10，从图1中可以看出，BSMA算法法计算的组播树代价最小，CDKS算法和KPP算法计算出的组播树代价分别比BSMA算法高出20%和10%，而本文提出的算法计算所得的组播代价介于KPP与BSMA之间，比BSMA算法高出。

图2为组播树代价和目的结点数的关系。网络结点数固定n为80，目的结点数量m由5变化到25时，各算法的组播代价随目的结点数量的增加呈类线性增长。显然，目的结点数增加导致组播树的链路增多，组播树的代价也因此增大。从图2中可以看出，目的结点数对本文提出的算法的计算质量有一定影响。在目的结点较多时，网络中的非基本结点数减少，遗传算法的搜索的空间渐小，导致计算的组播树代价偏大。

图3为组播树代价和时延约束的关系。网络结点数固定为40，目的结点数固定为5，时延约束由40ms变化到80ms。随着时延约束的逐步放松，各种算法计算的组播树代价有可能出现下降趋势，这是因为放松约束条件使得网络中有更多的路径可以选择，从而有可能构造更低代价的组播树。

这里提出的基于满意优化思想的多约束组播路由算法是切实可行的。在较短的时间内，它找到的组播树不仅能满足组播的多个性能指标，还能很好地平衡网络负载，提高网络资源利用率。

4 结语

对于QoS路由算法，文中提出了用满意解代替最优解的方法。通过引入满意度函数，使得建立多约束的QoS路由算法成为可能。以QoS各性能指标(带宽、时延、时延抖动、丢包率)为目标，建立了相应的多目标满意优化模型。以用户提出的各性能指标要求为基准，分别建立了各自的满意度函数，证明了满意优化模型广泛的适应性。

摘要：随着不断增长的多媒体应用需求,对网络的服务质量(QoS)提出了更高的要求,高效的支持变得越来越重要。本文分析了组播和组播路由选择技术的原理,用多目标满意优化求解模型来求解组播路由树,设计了适合模型求解的遗传算法。在随机生成的网络上测试组播路由算法,并与己知的算法进行了比较。

关键词：满意优化,Qos路由,遗传算法,组播树

参考文献

[1]王飞,金跃辉,陈山枝.MPLS支持移动IP的QoS机制研究[J].计算机应用研究,2006,04.

[2]任平.优化理论中的令人满意准则[M].模糊数学,1983,4:111-112.

[3]靳蕃.神经计算的满意解原理[J].科学杂志,1992,44(4):40-43.

[4]Waxman B M.Routing of multipoint connections.[J].IEEE Journal on Seclected Areas in Communications,1998,6(9):1617-1622.

[5]Kou L,Markowsky G,Berman L.A Fast Algorithm for Steiner Tree.[J].Acta Informatica,1981,15(1):141-145.

组播路由器 篇8

1 组播路由算法

随着互联网技术的发展和网络应用的普及,因特网上的用户数量持续呈爆炸性增长,网上的应用由传统的电子邮件转向FTP、WWW等多媒体业务。此外,基于因特网的新应用和业务也在不断地推出,如电子商务、IP电话、视频会议等。但是,要满足这些业务的需求,特别是要保证一些实时业务的带宽、时延等特殊需求,以目前因特网的“尽力而为”的服务模式是难于完成的。“尽力而为”服务模式的特点是对所有应用提供同种数据传输服务,对网络的资源缺乏有效的分配和管理,当网络负载较轻时,各个应用得到的传输服务质量尚可,但是随着用户数目的增多,网络的负载也将增加。此时,各种应用的行为表现为无序地竞争网络资源,造成网络资源的不合理占用,各种应用各为其利,其结果是服务质量互相恶化。

目前的因特网技术急需进行改进以提供有效的资源分配与管理。上面提到的新型网络应用,如视频会议、交互式游戏、声音/视频电话、实时多媒体播放、分布式计算、视频点播和远程教学等应用的特点是涉及多个成员的交互,本质上具有组播的特征。为了支持大量存在的此类应用,组播路由技术应运而生。

组播是一端节点将同一信息传送到多个目的端节点,参与组播的多个目的端点组成了一个组播组,每个端节点称为组播组成员。随着多媒体实时应用业务的出现和发展,使得组播组的规模、业务的特征和要求发生了很大变化,为了满足这种需求,有必要寻求网络层对组播通信的支持,使组播技术满足多媒体实时应用的要求。从而出现了以组播树(MULTICASTINGTREE)实现组播的方式。组播树是覆盖所有组播组成员的一棵生成树,组播树有以下两个优点:(1)信息以并行的方式沿着树枝发送到不同的组成员,降低了信息传递的时延;(2)网络中需要传送的复制信息最少,而且信息的复制只在树杈处进行,这样能够节省网络带宽资源,提高每次组播通信时的资源利用率,并能减少拥塞,降低网络负载。

2 蚁群优化算法

自然界常常是人类创新思想的源泉。自然界中蕴含的内在规律、生物的作息规则往往被借鉴,并诞生新的学科。许多这种在自然界启示下诞生的新学科新方法都在数学基础没有被完全证明的情况下,通过仿真实验验证了其有效性,因为神奇的生物界常常可以通过自身的演化解决许多在人类看来十分复杂的优化问题。蚁群算法属于仿生优化算法,具有鲁棒性强、全局搜索、并行分布式计算、易与其他方法结合等优点。

蚂蚁在寻找食物的过程中往往是随机选择路径的,但它们能感知当前地面上的信息素浓度,并倾向于往信息素浓度高的方向行进。信息素由蚂蚁自身释放,是实现蚁群内间接通信的物质。由于较短路径上蚂蚁的往返时间比较短,单位时间内经过该路径的蚂蚁多,所以信息素的积累速度比较长路径快。因此,当后续蚂蚁在路口时,就能感知先前蚂蚁留下的信息,并倾向于选择一条较短的路径前行。这种正反馈机制使得越来越多的蚂蚁在巢穴与食物之间的最短路径上行进。由于其他路径上的信息素会随着时间蒸发,最终所有的蚂蚁都在最优路径上行进。蚂蚁群体的这种自组织工作机制适应环境的能力特别强,假设最优路径上突然出现障碍物,蚁群也能够绕行并且很快重新探索出一条新的最优路径。

蚂蚁从每一个网络节点被释放,朝着期望的被选终节点梦动(释放遵循某个随机的或具体问题的时间表)。蚂蚁,像数据包一样,通过应用一种概率的转移规则,沿着网络移动并建立从源节点至终节点的路径。概率的转移规则充分利用了保持在与链路链接关联的信息素轨迹变量中的信息,和在一些情况下额外的局部信息。具体算法的启发法和信息结构用于评价已经找出的路径和设置蚂蚁释放的信息素量。在有向连接网络中,同一个话路的所有数据包沿着一条共同的路径传输,这条路径是由一个初步设置状态选出的。相反,在无连接或数据包中,同一话路的网络系统数据包可以沿着不同的路径传输。在沿着信道从源节点到终节点的每一个中间节点上,一个具体包转寄决策是由局部路由组件做出的。在两种类型的网络中,效果最好的路由,即没有保留任何外部资源(软件或硬件)的路由,都能够被传送。而且,在有向连接的网络系统中也可以进行资源的外部保留(软件或硬件),通过这种方式,可以传送需要特殊特征(在带宽、延迟等方面)的服务。

3 组播路由算法的蚁群优化

3.1 生成备选路径集

以深度优先算法求解有效路径,将目的节点Di∈D(i=l,2,…,m)与源节点s之间所有满足时延约束的有效路径,并集合Ω做为备选路径,一条有效路径可表示为P(s,Di),则P(s,Di)的编码为{s,v1,…,vk,…,Di},vk∈V,其中s,v1,…,vk,…,Di依次为从源节点s到目的节点Di所经过的节点编号,m为目的节点数目。深度优先搜索算法的基本思想是从源节点开始,随机选择一个没有访问过的邻节点,并判断从源节点到该节点的时延是否满足时延约束条件。如果满足,将该节点加入这条路径中,重复该过程,直到找到目的节点为止,则找到了一条有效路径,再从分支节点找出其他满足时延约束条件的路径,直到找到所有满足约束条件的路径,组成备选路径集。

3.2 适应度函数

蚁群算法在选择路径时的依据为适应度函数,即为在备选路径集Ω中,蚂蚁选中路径标号为j的概率。

式中,的分泌物强度,表明了在备选路径集中路径被选中的概率与路径的分泌物强度呈正相关。

3.3 蚁群算法信息

在蚁群寻路的调整中,路径的信息调成过程要满足以下规则:

(1)能够调整蚂蚁已经走过路径分泌物的强度,下式中α为常量参数,l是所经过路径的代价,目的节点Di与源节点s之间的路径分泌物强度为,而调整之后

式中,信息的调整并不是固定不变的,调整中需要以所选路径的代价做为依据,在增加调整过程自适应性的同时,提高收敛速度。

(2)当所有路径都被蚂蚁经过之后,对路径的分泌物强度进行整体调整,式中ρ为路径挥发度,Δ是路径初始的信息强度

(3)在蚂蚁寻找到所有的目的节点之后,将会构成组播树,根据式4调整信息

式中,B是常量参数,cost(T)是组播树代价,Pi(s,Di)为被选路径。

3.4 算法步骤

步骤一:首先为备选路径集的生成。以深度优先算法求解有效路径,将目的节点Di∈D(i=l,2,…,m)与源节点s之间所有满足时延约束的有效路径,并集合Ωi做为备选路径。

步骤二:将B、α、antnum、ρ与备选集Ωi中所有路径的信息强度Δ进行初始化处理。

步骤三:由源点使数量为antnum的蚂蚁出发,根据式1求解路径集Ωi中所有路径的适应度,之后以赌轮旋转规则使所有蚂蚁选择路径,再根据式2调整路径的分泌物强度。

步骤四:在所有蚂蚁都完成路径选择后,以式3为依据调整分泌物的挥发性。

步骤五:步骤三和步骤四反复执行,当所有蚂蚁找到通往目的节点的所有路径后,将每只蚂蚁找到的路径分别组成组播树。计算组播树的代价(相同链路的代价不重复计算),判断蚂蚁是否多数都收敛于一个组播树。答案为确定,该组播树即为最优的路由路径,结束程序;答案为否定,以代价最小的组播树替换最大的组播树,执行步骤六。

步骤六:将蚂蚁以原路返回源节点,重新以式4为依据调整返回路径的分泌物强度,执行步骤三。

4 实验仿真

网络图是随机产生的网络拓扑结构,每对节点(u,v)之间的距离采用欧几里得距离d(u,v),两个节点u,v之间存在边的概率由下面的公式5决定

d(u,v)为节点u到节点v之间的欧几里得距离,参数α、β控制产生网络的(0,1)之间,α控制短边与长边的比例,β控制边的密度。α越大,则长边与短边的比值也越大;β越大,边越密集。n为网络图中节点数目,其中α=0.2,β=0.3。

首先分析算法的复杂度,从算法描述看,算法的复杂度由两部分决定。一是深度优先搜索算法的复杂度为O(n2),则生成备选路径集时所用的复杂度O(n2);进行蚁群寻路时的复杂度为O(nc·n2),则总的复杂度为0(n2),其中nc为循环次数,n为网络节点数。如果路由问题的规模较大,由于挥发系数ρ存在,会减少未知的路径信息量并使其接近于零,从而将算法全局的搜索能力降低;如果挥发系数ρ过大,路径解信息量在增大的时候,重复选择路径解的可能性增大,也会降低算法的全局搜索能力。减小ρ能够有效提高算法的全局搜索能力,同时会降低算法的收敛速度。蚂蚁数目与算法的全局搜索能力呈正相关,但蚂蚁数目与算法的收敛速度呈负相关。在蚂蚁数目相同的情况下,问题规模不断增加,算法的全局搜索能力会降低。蚂蚁优化路由算法最大的缺陷是易陷入局部最优解和收敛速度慢。

参考文献

[1]王肖楠,程东年,张建辉.基于蚁群优化的容错组播路由算法[J].信息工程大学学报,2010,11(4):498-503.

[2]郑啸,罗军舟,宋爱波.基于Agent和蚁群算法的分布式服务发现[J].软件学报,2010,(8):1795-1809.

[3]郝晓青.基于蚁群优化的无线传感器网络路由算法[J].电脑知识与技术:学术交流,2010,6(1):34-36.