如何选择路由协议

2024-09-24

如何选择路由协议(12篇)

1.如何选择路由协议 篇一

在各种路由协议中,路由选择协议还是比较常用的,于是我研究了一下路由选择协议的综合说明,在这里拿出来和大家分享一下,希望对大家有用,管理路由器需要了解路由选择协议的基础知识。你对基本的路由选择协议越熟悉,将来诊断网络路由选择协议中的故障就越容易。本文节选自研究内部和外部网关协议的基本特点的Informit网站。

开放式最短路径优先协议(OSPF)

OSPF克服了路由选择协议(RIP)中的缺陷,但是,这个协议并不是专有协议,但是,它仅支持IP路由选择协议。这个协议是以互联网工程任务组(IETF)为支持庞大的异构网络开发的Dijkstra算法为基础的一种链路状态的内部网关协议(IGP)。在至最后确定目前应用的OSPFv2期间,完成了很多有关这个问题的研究报告。链路状态通告(LSA)要发给所有的设备,从而引起路由器的大量通信。然后,OSPF就开始高效率地工作了,

这个路由选择协议使用了三个不同的数据库表记录邻居、链路状态和路由。下面是OSPF的特点:

1、开放式协议。

2、适用于小型至大型网络。

3、仅支持IP第三层路由选择协议栈。

4、链路状态路由选择协议(不像距离矢量仅发送给邻居)。

5、内部网关协议。

6、多播链路状态通告。

7、在多播地址224.0.0.5和224.0.0.6上升级。

8、IP协议号89。

9、管理距离是110。

10、衡量标准是累积成本(与带宽成反比)。

11、仅支持等价均分负载,但是,某些执行可利用服务类型请求的好处。

12、要求在那个每一个区域都有一个路由结构,每一个区域必须要接触到骨干区域(否则要使用虚拟链接等临时的补丁)。LSA、区域和状态等各种路由类型需要根据你的设计和第二层拓扑结构而定。

13、使用Dijkstra算法选择无路由自环路经,并且提供迅速的融合。这将使用LSA和SPF算法。

14、支持变长子网掩码(VLSM)和汇总(没有级别)。

15、仅支持手动汇总;这并不像增强型内部网关路由选择协议(EIGRP)那样是自动化的。只能在ABR(区域范围)或者ASBR(汇总地址)上执行。

16、基于政策的路由。

2.如何选择路由协议 篇二

路由器根据路由表转发数据分组, 路由表的各项路由信息取决于路由协议, 其核心是路由选择算法, 路由选择算法计算路径的方法一般利用评价因子、权重及算法思想的差异来划分。下面介绍较常用的动态路由协议--路由信息协议RIP的配置及其应用。

1工作原理

RIPv1是分布式的基于距离向量的路由选择协议, 优点是简单, 要求网络中的所有路由器都要维护从自身到其余目的网络的距离记录, RIPv1协议按如下方法定义“距离”:路由器到直连的网络的距离定义“1”;路由器到非直接的网络的距离是所经过的路由器数“+1”。“+1”是因到目的网络后就直接交付, 而到直接连接的网络的距离已定义为1;每经过一个路由器, 距离就“+1”。RIPv1认为“好的”路由是它通过的路由器的数目最少, 允许一条路径最多包括15个路由器, “距离”为16时相当于不可达, 只适用于小型因特网。RIPv1协议没有负载平衡的特性, 不能在两个网络之间同时适用多条路由。RIPv1选择具有最少路由器的路由, 即使存在另一条高速具有较多的路由的路由器。

2改进的RIPv2

距离矢量路由协议的路径的基本评价因子采用跳数作为衡量标准, RIPv1协议的收敛过程较快, 虽然算法实现和配置都较为简单, 但是路由更新采用与相邻路由器定期进行路由信息交换的机制, 易形成路由环路;也不支持VLSM。因此对其改进得到RIPv2。

虽然RIPv2本身没多少改变, 但改进了性能 (路由评价因子仍是跳数及最大跳数15) :

提供前缀路由, 在路由更新中发送子网掩码信息, 支持在同一AS中使用VLSM;更新信息中提供了认证机制, 路由信息的可信性与安全性均增强了。RIPv2向下兼容RIPv1。

3应用举例

建立路由表:路由器刚开始工作时, 只知到直连网络的距离;此后, 每一路由器只和数目有限的相邻路由器交换并更新路由信息。经若干次更新后, 全部路由器都会知道到达本AS中任一网络的最短距离和下一跳路由器的地址。

应用举例:已知路由器A有表1所示的路由表。

现在收到相邻路由器X发来的路由更新信息, 见表2所示。

试求出更新后路由器A的路由表。

解答:如同路由器一样, 不需要知道该网络的拓扑。

先把表2的距离都加1, 并把下一跳路由器都改为X, 得下表3:

把表3的每一行和表1进行比较:

第1行的Net1在表1中没有, 把这一行添加到表1中;

第2行Net2在表1有且下一跳地址也是X, 距离增大, 要更新;

第3行Net3在表1中没有, 把这一行添加到表1;

第4行Net6在表1中有, 但下一跳路由器不同, 比较距离, 新的路由器的距离2, 小于原来表中的8, 要更新;

第5行Net8在表1中有, 但下一跳路由器不同, 比较距离, 新的路由器的距离是4, 原来表中的是4, 不更新;

第6行Net9在表1中有, 不同下一跳路由器, 于是比较距离, 新路由器的距离6, 大于原表中的距离, 不更新;

因此, 得出更新后的A的路由表如表4所示:

结论

RIPv2是RIPv1的改进版本, 它保留了RIP的大部分特点, 增加了支持VLSM和CIDR的功能, 在其路由更新信息中会发送子网掩码信息, 其应用性更强。

摘要:路由表是根据路由选择协议来获得表中的各项路由信息的, 而路由选择协议的核心是路由选择算法。在此基础上, 提出了基于距离向量的路由选择协议 (RIP) 及应用。

关键词:路由选择,网关协议,距离向量

参考文献

[1]李太君、林元乖等.《计算机网络》 (第1版) .北京:清华大学出版社.2009年7月.

[2]林元乖编著.《计算机网络实验教程》.北京:机械工业出版社.2012年6月.

[3]李莉, 李然, 鲍嘉伟.RIP路由协议测试软件的设计与实现[J].现代电信科技.2015 (01) :7-11.

[4]张樱子.RIP协议在GPON OLT上的实现[D].武汉邮电科学研究院.2012.

3.路由器・什么是路由协议 篇三

路由协议作为TCP/IP协议族中重要成员之一,其选路过程实现的好坏会影响整个Internet网络的效率。按应用范围的不同,路由协议可分为两类:在一个AS(Autonomous System,自治系统,指一个互连网络,就是把整个Internet划分为许多较小的网络单位,这些小的网络有权自主地决定在本系统中应采用何种路由选择协议)内的.路由协议称为内部网关协议(interior gateway protocol),AS之间的路由协议称为外部网关协议(exterior gateway protocol)。这里网关是路由器的旧称。现在正在使用的内部网关路由协议有以下几种:RIP-1,RIP-2,IGRP,EIGRP,IS-IS和OSPF。其中前4种路由协议采用的是距离向量算法,IS-IS和OSPF采用的是链路状态算法。对于小型网络,采用基于距离向量算法的路由协议易于配置和管理,且应用较为广泛,但在面对大型网络时,不但其固有的环路问题变得更难解决,所占用的带宽也迅速增长,以至于网络无法承受。因此对于大型网络,采用链路状态算法的IS-IS和OSPF较为有效,并且得到了广泛的应用。IS-IS与OSPF在质量和性能上的差别并不大,但OSPF更适用于IP,较IS-IS更具有活力。IETF始终在致力于OSPF的改进工作,其修改节奏要比IS-IS快得多。这使得OSPF正在成为应用广泛的一种路由协议。现在,不论是传统的路由器设计,还是即将成为标准的MPLS(多协议标记交换),均将OSPF视为必不可少的路由协议。

外部网关协议最初采用的是EGP。EGP是为一个简单的树形拓扑结构设计的,随着越来越多的用户和网络加入Internet,给EGP带来了很多的局限性。为了摆脱EGP的局限性,IETF边界网关协议工作组制定了标准的边界网关协议--BGP。

RIP协议

OSPF协议

BGP协议

IGRP协议

EIGRP协议

4.如何选择路由协议 篇四

数字最能说明问题。在有一个100Mbps上行链路的交换机里,每个10Mbps受控交换机端口的成本为100美元。 路由选择技术并不真正按给每个端口分配一个用户的方式来分段网络,每个路由选择技术端口的成本至少是交换机端口的三四倍, 因而管理负担大得惊人。尽管用路由器分段的网络只有TCP/IP通信量,但由于成本高,性能不高,子网太多,并且配置工作量大, 所以很快就行不通了。相比而言,交换机和集线器一样,是即插即用设备。目前正在出现具有“自学”功能的路由选择设备, 采用所支持的协议自动配置端口。在缺省情况下,纯交换网络是平面网络。如果每个节点都有自己的交换端口, 网络就很难发生争用情况,即入站通信量与节点的出站通信量发生资源争用,反之亦然。相比而言,在传统的共享网段或者环里, 每个节点的吞吐量随着节点的增多而下降,例如有25个节点的10BaseT网络只能给每个节点平均提供400Kbps带宽, 而有专业交换端口的节点却拥有10Mbps吞吐量。

一般被节点用于做广告或者寻找目前未知的广播技术可大大提供这种网络的吞吐量, 而通常的单址广播帧只能广播到一个目的地节点和中间交换端口。自从网桥流行的那一天起, 我们就知道我们实际上并不希望有数千个节点的广播域,因为广播风暴无法预测且难以控制。把平面网络变成较小的广播域,无异于使交换网络变成一种丰富多彩的调色板。与其用路由选择技术定义任意大小的子网, 倒不如用交换机建立VLAN。

VLAN的管理

VLAN与交换网络密不可分,但实施VLAN要重新定义管理环境。VLAN定义的逻辑域涉及网络里的可能视图, 因而网络管理平台可显示IP图像,有时还会显示基于IPX的图像。如果部署VLAN,其拓扑可能与上述视图不匹配。 当VLAN部署完毕之后,你很可能对根据逐个VLAN监视通信量并生成警报这一点感兴趣。

在目前,大多数基于交换机的VLAN是专用的。IEEE 802.1P委员会开发出一种多址广播标准, 使VLAN成员可以在取消VLAN广播抑制任务的情况下通信。在可互操作的软件和硬件里实现上述标准之前, VLAN配置仍将要求维护单一供应商交换机环境。

即使在单一供应商VLAN里,网络管理也是一种挑战, 例如检查VLAN对话要求管理软件处理的统计信息不同于检查常见的LAN或IP子网对话: RMON MIB和RMON-2 MIB分别提供确定LAN和子网信息的框架,而VLAN配置必须定义自己的MIB, 或者配置如何根据其他MIB获得上述信息,

此外,为了提供连贯的VLAN行为特性图,管理软件要收集并合并来自多个RMON检测器的数据。

如果上述问题很严重,就要考虑捕捉多交换机VALN数据的地方只限于中间交换机链路或者主干网。在大型网络里, 主干几乎都在100Mbps以上,高速控制器的部署与常见VLAN不一样,而且成本很高。

VLAN的配置

如果根据交换机端口定义VLAN,通常很容易用某种拖放软件把一个或多个用户分配到特定的VLAN。在非交换环境里,移动、 添加或更改操作很麻烦,有可能要改动接线板上的跳线充一个集线器端口移动到另一个端口。然而,改动VLAN分配仍然要靠人工进行: 在大型网络里,这样做很费时,因而很多联网供应商鼓吹采用VLAN可以简化移动、添加和更改操作。

基于MAC地址的VLAN分配方案确实可使某些移动、添加和更改操作自动化。 如果用户根据MAC地址被分配到一个VLAN或多个VLAN, 他们的计算机可以连接交换网络的任何一个端口,所有通信量均能正确无误地到达目的地。显然,管理员要进行VLAN初始分配, 但用户移动到不同的物理连接不需要在管理控制台进行人工干预;例如有很多移动用户的站, 他们并非总是连接同一端口?D?D或许因为办公室都是临时性的,采用基于MAC地址的VLAN可避免很多麻烦。

传统的Layer3技术怎么样呢?这里离开VLAN最近的是IP子网:每个子网需要一个路由器端口, 因为通信量只能通过一个路由器从一个子网移动到另一个子网。由于IP32位地址提供的地址空间很有限,所以很难分配子网地址, 还有看你是否熟悉二进制算法。因此,在IP网络里执行移动、添加和更改操作很困难,速度慢,容易出错,而且费用大。另外, 在公司更换ISP或者采用新安全策略时,可能有必要重新编号网络,这对于大型网络来说是无法想像的。实际上,如果有人采用现有的有子网的路由IP网络,并根据IP地址访问任意VLAN成员,路由选择技术就可能会被不必要的通信量淹没。

如果很多子网里都有VALN成员,常用的VLAN广播必须通过路由技术才能达到所有成员。此外, 糟糕的是广域链路会生成额外广播通信量;有WAN连接服务的VLAN成员数通常应该保持在最低水平。实际上, 基于Layer3地址的VLAN成员值有可能在增强和修改现有子网分布方面很有用,例如可通过一个全子网给VLAN添加两个新节点, 或者可用两个子网组成一个VLAN而无须重新编号。

5.动态路由协议配置实验心得 篇五

2、DHCP的工作过程:需要自动获取IP地址的客户端开启自动获取IP地址之后,本地广播发出DHCP Discover数据包,

源IP地址0.0.0.0,目标IP地址255.255.255.255,源MAC地址为本地网卡MAC,目标MAC为FFFF-FFFF-FFFF,

源端口为68,目标端口为67;

开启了DHCP服务的服务器收到此数据包后,发送免费ARP以确定所要下发的IP地址没有冲突,再本地基于广播的形式回复DHCP Offer数据包,

源IP是服务器IP地址,目标IP地址255.255.255.255,源MAC为服务器网卡MAC,目标MAC为FFFF-FFFF-FFFF,

源端口为67,目标端口为68;

客户端使用DHCP Request数据包请求IP地址,服务器回复ACK给客户端,客户端拿到IP地址。

租期:默认租期为1440min/24h/一天。

续租:当租期到达1/2时,客户端若依然在线,客户端主动发出Request数据包来续租;

若续租失败,继续在7/8的租期再次发送Request数据包续租;

若依然失败,那租期到达时地址被收回,客户端若想继续使用,需要重新获取地址。

3、当路由器作为DHCP服务器时:

有两种配置方法

(1)以全局的池塘下发地址

(2)以接口的IP地址的范围下发地址

4、RIP:路由信息协议

动态试验的步骤

1、搭建拓扑图,划分区域网

2、编写各个端口IP

3、进入DHCP为每个路由器下的PC自动配置IP

6.可扩展路由协议研究 篇六

随着IPV4全球路由表(global routing table)项数目的枯竭以及IPV6的开发使用,全球互联网的路由体系面临着巨大的挑战。这一严峻的形势让全球的网络研究者意识到,继续使用层次化结构路由模式无疑会使得现有的形势继续恶化,而IPV6的使用只能使其得到暂时性的缓解,却无法从根本上解除危机。随着互联网使用人数呈指数型增长,日益庞大的路由表带来的路由器空间消耗和处理器的开销会持续增加,硬件上的升级也无法匹配该速度。

因此,近年来,针对互联网路由的延展问题在全世界范围内掀起了一股热潮,诸多理论研究相继开展,并针对不同的方向提出了不同的解决方案,如基于DHT的VRR[1]以及BVR[2]、基于Landmark的TZ策略[3,4](Thorup-Zwick)、基于DHT和TZ策略结合的Disco[5]等。在国内,互联网的可扩展性研究也已经受到了学术界的广泛关注,清华大学、国防科技大学等名校也都长期开展了可扩展性方面的研究工作,但目前还没有较优的研究成果出现。本文通过介绍几种常见的紧凑路由策略,列出评价紧凑路由策略的三项重要指标,着重讲述对紧凑路由算法Disco在算法缺陷上进行的改进,使其在stretch方面得到了有效的降低,同时弥补了Disco在完善性上的缺陷,从而使得改进后的算法达到了延展性更优、缺陷度更小的目的。并且,在文章的最后,通过几种算法的实际问题,指出目前紧凑路由急需解决的问题和未来可能的发展方向。

1 背景

随着互联网路由体系的弊端逐步显露,新的概念也随之提出。“以内容为中心”这一概念最早由MIT的AdjieWinoto等人于1999年明确提出[6]。2008年提出的NDN(N-amed Data Networking)网络形式因之受到了重点关注。而今,这一概念已被广泛接受,并进行了着重的研究。

“以内容为中心”,顾名思义,就是以数据提到主机成为网络中的第一类对象,将数据显式的命名,从而将数据的名字与数据的位置相分离,这就与当今的IP层次化路由模式显现不同。这种基于数据名字的路由方式,被称为命名数据路由。现今,已有较多的算法实现了命名数据路由,如TRLAD[7]、FARA[8]、LISP9[9]等。

命名数据路由最终的目标是以命名数据层替代IP层成为新的thin-waist。这种方式可以在极大程度上解决因IP路由表项数目的枯竭所引发的问题,实现命名空间无限化。

命名数据路由的思想一经提出,即受到了广泛关注,在互联网发展受到局限的现如今,寻求新型的路由模式成为了主要任务之一,而这种“寻找关注,而非关注寻找”的行为模式完全符合绝大多数互联网用户的需求。

基于这种思想,以命名数据网络为目标的紧凑路由研究已发展得如火如荼,而且,因为现有的层次化路由模式中灵活度弱、地址空间消耗过大等问题的存在,使得这方面的研究工作的开展更是显得迫在眉睫,刻不容缓。

2 紧凑路由策略与评价指标

2.1 评价指标

(1)可扩展性(Scalability),表示路由器存储空间的上界。现如今的互联网路由协议在n个节点的网络中要求每个节点的路由表大小为O(n)比特,这是现有路由体系的弊端之一,随着未来互联网体系的扩大,网络拓扑下的可扩展性必然会成为路由评价一项重要指标。保证可扩展性不仅仅是对算法本身的一种优化,更多的则是对所设计的协议在使用期限上的一种保障。若要具有较好的可扩展性,紧凑路由策略则应具有较小的空间要求,并且传递的消息也要尽可能地少(不考虑拓扑的情况下)。

(2)延展性(stretch),具有延展性,则延展度低。延展度表示实际路由的路径与理论最短路径之间的比值,用来衡量协议路由策略的优劣。直观地,延展度越低,路由策略越优。

(3)扁平性(flat names),这一性质针对命名数据网络。具有扁平性,则可以在数据上,而非地址上进行路由。

紧凑路由,从理论上来说,就是同时既具有可扩展性,又保证了延展性的路由算法。其基本思想是,平衡路由表的大小和路径的长度,允许有限的路径延展以换取较大幅度的空间缩减。而满足扁平性,则是针对“以内容为中心”这一概念,致力于使紧凑路由同样适用于目前较为流行的理论体系。

2.2 典型紧凑路由策略

目前,已提出的多种紧凑路由策略多为集中式,并不适用于分布式网络当中,而且算法本身相对而言,也较为复杂,所以,紧凑路由的研究仍处于理论阶段,如何将其转化入实践层面,目前尚不够明确。但理论体系的发展却非常地迅速,广泛流传的算法也已经较多,如Landmark routing、TZ、S4、BVR、VRR、Ford[10]和Disco等。

2.2.1 界标层次化路由

界标层次化路由[11](Landmark routing)是对基于分区的层次化路由的一种改进,目的是使得层次化更有利于动态管理。基本思想是,迭代地选择网络中的节点作为界标,并且在界标的基础上构建层次化结构;节点中除了存储路由表之外,还需存储若干界标的信息。路由时,如目标节点不在自身的路由表当中,该信息则被传递到最近的界标上,然后通过界标转发给目标节点。

界标层次化路由的关键部分为界标以及基于界标层次化的构建,如图1所示。当一个界标被选取出来之后,以r为半径范围内的所有节点均需要存储该界标的信息,这些节点被称为邻域,而界标本身却不需要存储邻域的信息。当这一步骤完成后,LMi[id]表示标识为id的第i级界标,层次化构建指的是第i+1层均需要从第i级界标中选取,且半径ri+1需要大于ri,从而保证上一级的界标必然能够找到下一级的界标,实现层次化。该路由策略中,节点地址是由层次化界标构成的,使得通过各级界标,最终可找到目标节点。

S4将TZ算法改进用于无线传感器网络中,形成的S4网络拓扑如图2所示。S4算法的基本思想是随机产生多个界标,均匀地分布在网络当中,节点邻域是以节点到最近界标距离为半径范围内的所有节点的集合。每个节点除存储自身邻域信息之外,还需要存储全部的界标信息;界标本身则存储着所有的以其自身为最近的节点信息。路由时,如果目标节点不在节点自身的邻域当中,则将该信息发送到目标节点的最近界标中去,利用该界标转发。S4策略对于TZ的改进表现在界标选取、邻域构建以及地址存储三个方面,但需要指出的是,虽然S4对无线传感网络的适应性较好,却同时破坏了TZ策略对于可扩展性的限制。

2.2.3 BVR

BVR的基本思想是利用贪心的方式局部优化,从而达到全局优化的目的。构建灯标(Beacon)并且以到达灯标的距离向量作为节点地址,在这样的节点地址上通过构建距离方程进行贪心路由;如贪心算法失败,BVR同样构建了回溯算法,通过周围可以抵达目标节点的“邻居”重新路由。BVR数据包头含有目标节点标识、目标BVR地址以及最短距离地址向量三个部分,这种结构保证了源节点必然能够找到目标节点的目的的实现。BVR算法很好地提高了路由算法的可扩展性,但因为贪心算法的局限性,该算法可能会驻停在局部极小处,从而导致过高的延展度。

2.2.4 虚拟环路由

虚拟环路由(Virtual Ring Routing)的基本思想是使用DHT技术,将所有节点根据自身的标识大小排序,组成一个虚拟环。每一个节点的路由表中需存储其在环上的前驱和后继节点的路由信息、物理邻居的路由信息以及所有经过i的最短路径的源节点和目标节点的路由信息。与Chord环相类似,路由时,当前节点通过路由表中与目标节点标识最为相近的节点转发消息。VRR的可扩展性平均起来是较好的,但在某些个别节点上却较差,另外,VRR算法本身的延展性较差,延展度高。

基于已经提出的三项评价指标,上文中简单介绍的几种路由策略以及下文着重介绍的Disco关于这三项指标的比较结果如表1所示。

3 Disco改进策略

3.1 Disco的简单介绍

Disco是基于TZ策略以及DHT技术结合产生的、一种具有较好的可扩展性、延展性以及扁平性的紧凑路由策略。

Disco中的基本要素分为五个部分:界标、邻域、路径学习、地址以及命名无关到命名相关的映射。

(1)界标:Disco采用随机模式选取界标,以概率[(logn)/n]1/2为基础,均匀地选取,从而保障了整个网络中界标的数目会在左右变动。节点界标指的是距离本节点最近的界标。

(2)邻域:指个距离本节点最近的节点集合。节点中需存储邻域范围内所有节点的路由信息。如图3所

(3)路径学习:每个节点路由表中需存储到达所有界标以及邻域中所有节点的路由信息,因此,就需要对这些节点进行路径学习。

(4)地址:节点地址模式为lv→v,lv表示节点界标,v表示目标节点,→表示最短路径。地址的使用借助了显示路由模式,将地址空间的使用量降到了相当的程度,使得每个数据包携带的地址空间都不大,可扩展性因之得到了保障。

(5)命名无关到命名相关的映射:使用DHT技术,将名字与地址分布式地映射在多个分布式的哈希数据库中。

除了以上五个基本要素之外,为了确保能够降低第一个数据包的延展度,Disco采用了color-group的思想,重新建组,将组内信息在组内共享。Disco中的路有方式如下:

当源节点s需向目标节点t发送数据包时,若t为界标或在s的邻域中,则直接路由;若t在s的哈希数据库中,则直接利用地址路由;否则,s查找自己的邻域中与t哈希值匹配位数最高的节点,由该节点转发。

3.2 Disco改进策略

设V(v)表示节点v的邻域,L表示landmark的集合,L(v)表示节点v的节点界标,G(v)表示节点v的匹配组,Addr(v)表示节点v的地址。

目标节点为t,源节点为s,s→t表示s到t的最短路径。路由过程可以简单描述如下:

在路由的过程中,除了目标节点或者t∈L或者t∈V(s):可以直接使用最短路径路由之外,其余的路由模式都是通过界标或者其他节点转发,这也是导致延展度可能增加的主要原因所在。针对这种状况,在上述基础上,使用捷径启发的方式,则能够较好地降低延展度。当然,并不需要对路径中所有的节点均采用捷径启发式;对于转发节点之后的每个节点,就没有必要进行学习。因此,在源节点s到目标地址的Landmark发送消息的过程中,对于途径上的每个节点,均进行捷径启发,判断该节点是否存有到达目标节点的最短路径,如存在,则直接通过最短路径到达目标节点。即,在上文路由过程的基础上,数据包每到一个节点k,路由器自动查找自己的邻域,一旦找到最短路径,直接k→t。

以上的三种路由选择,可以很明显地看出Disco算法存在的缺陷,在目标节点非Landmark且不属于V(s),同时也不存在于G(s)中的时候,Disco选择邻域中与目标节点t哈希值匹配最长的节点进行转发,从k的取值中可知这种情况下找到目标节点t的概率极大,但仍然存在无法找到目标节点t的概率。这样网络中就可能存在着不可达点,目标节点的延展度会无限加大,超越设置的延展度界限,同时在安全性和完整性方面也各有缺陷。

因此,增加如下的模块:在Landmark选取结束,节点进行路径学习的初期,Landmark之间相互通信的过程中,每个Landmark均分配一个特殊的标识M(L)。M(l)是独属于Landmark l本身的一种标记,所有Landmark均明确其它Landmark的标识。在节点进行路径学习的过程中,Landmark将接收到的所有节点哈希值与M(l)匹配的节点地址存储在I自身的哈希数据库中。文中,称与M(l)相匹配的所有节点为界标l的关联组。

路由时,当源节点s无法找到目标节点t时,则将消息发送到节点界标中去;节点界标通过识别标识,将该消息转发到该标识的界标中去,从而最终找到目标节点。即,在上述的路由过程中增加第四项:

(4)若s无法找到t,则

当然,这样的设计势必会增加Landmark的负载,接下来,将会证明,增加的部分不会过度加重界标的负载。

证明:在界标相互通信时确定标识M,假定标识是均匀的,这也是需要致力于完成的。

3.3 实验结果分析

拓扑图:G(n,m)随机图,节点数目1 024,节点平均度为8。

Disco和改进后的Disco在空间可扩展性方面的实验比较结果如图4所示。改进后的Disco相比改进前在空间使用上有所增长,但增长的幅度很小。所以,通过适当地改进空间使用,达到了降低延展度的目的。

Disco和改进后的Disco在路径延展度方面的实验比较结果如图5所示。图5表明了改进后的Disco在路径延展度方面相对S4以及原有的Disco较优。改进后的Disco在延展度方面已经有了提高。

4 结束语

Disco是一种同时具备可扩展性、延展性以及扁平性的紧凑路由策略,有着较好的性能和应用前景。通过对Disco的改进,较好地降低了路径延展度,并进一步保障了Disco的正确性。

需要说明的是,包括Disco在内的紧凑路由策略,均是以要优于现有的路由机制为目的而提出的,然而,互联网是一个大型、动态的拓扑结构,对于现有的互联网的拓扑结构和演化机理方面的知识体系不足以支持紧凑路由策略的深入研究,因此,目前的紧凑路由策略多还是基于静态的拓扑层面上,对于各种频繁的拓扑变化、节点变动等问题还没有一个可以完全的适应的算法。因此,对于现实的网络,如何匹配、改进、评估现有的紧凑路由算法仍是个需要进一步探究的问题。另外,如何将紧凑路由机制与现有的BGP协议相融合,也是急需解决的问题之一。

“以内容为中心”概念的提出以及紧凑路由策略的研究发展给出一个网络路由模式未来的发展方向,在现有的互联网机制弊端频现的今天,各种路由算法以及路由架构正在不断地被提出。在未来,以内容为接口,以“寻找关注,而非关注寻找”行为模式为主体,抛弃复杂有限的层次化地址路由模式,将成为一种极具有前景的研究方向。

参考文献

[1]CAESAR M,CASTRO M,NIGHTINGALE E,et al.Virtual r-ing routing:network routing inspired by DHTs.ACM SIGCO-MM Computer Communication Review,2006:36(4):362.

[2]FONSECA R,RATNASAMY S,ZHAO J,et al.Beacon vectorrouting:Scalable point-to-point routing in wireless sensornets.In NSDI,2005-05.

[3]THOURUP M,ZWICK U.Compact routing schemes[C]//Proc.SPAA,ACM,2001:1-10.

[4]KRIOUKOV D,FALL K,YANG X.Compact routing on Inter-net-like graphs.In IEEE INFOCOM,Citeseer,2004,1:209-219.

[5]SINGLA A,GODFREY P B.Scalable routing on flat names.[C]//Proc of ACM CoNEXT,2010-11.

[6]ADJIE-WINOTO W,SCHWARTZ E,BALAKRISHNAN H.etal.The design and implementation of an intentional naming s-ystem.SIGOPS Oper.Syst.Rev.,1999,33(5):186-201.

[7]GRITTER M,CHERITON D R.An architecture for content r-outing support in the internet[C]//USENIX Symposium on Int-ernet Technologies and Systems,2001-03.

[8]CLARK D,BRADEN R,FALK A,et al.Fara:reorganizing theaddressing architecture.SIGCOMM Comput.Commun.Rev.,2-003,33(4):313-321.

[9]FARINACCI D,FULLER V,MEYER D,et al.Locator/ID s-eparation protocol(LISP).In Internet-Draft,2009-03.

[10]FORD B A.UIA:A Global Connectivity Architecture for M-obile Personal Devices[D].Massachusetts Institute of Techno-logy,2008-09.

[11]TSUCHIYA P F.The landmark hierarchy:a new hierarchy f-or routing in very large networks[C]//Proc.SIGCOMM,NewYork,USA,ACM,1988:35-42.

7.如何选择路由协议 篇七

概要:

虚拟路由冗余协议VirtualRouterRedundancyProtocol(VRRP),VRRP协议是保证访问一些资源不会中断,即通过多台路由器组成一个网关集合,如果其中一台路由器出现故障,会自动启用另外一台,两个或多个路由器建立起一个动态的虚拟集合,每一个路由器都可以参与处理数据,这个集合最大不能超过255个虚拟路由器(可参考虚拟路由协议)。一般现在的路由器都支持该协议。

规格

需要功能包:system

软件等级:Level1

操作路径:/ipvrrp

相关协议和标准:VRRP,AH,HMAC-MD5-96withinESPandAH

属性

虚拟路由冗余协议是一种为路由提供高效率的路由选择协议。一个或多个IP地址可以分配到一个虚拟路由上,一个虚拟路由节点应该具备以下状态:

?MASTER状态,一个节点回答所有的请求给相应请求的IP地址。仅只有一个MASTER路由器在虚拟路由中。每隔一段时间这个主节点发出VRRP广播包给所有backup路由器。

?BACKUP状态,VRRP路由器监视Master路由器的状态。它不会回答任何来至相应IP地址的请求,当MASTER路由器无法工作时(假设至少三次VRRP数据连接丢失),选择过程发生,新的MASTER会根据优先级产生。

VRRPRouters

操作路径:/ipvrrp

属性描述

name(名称)?CVRRP名称

interface(名称)?C选择那个接口(interface)在VRRP上运行。

vrid(整型:0-255;默认:1)?C虚拟路由的身份号(必须是在接口(interface)上是唯一的)

priority(整型:1-255;默认:100)?C当前节点的优先级(高的数值代表高的优先级)

interval(整型:1-255;默认:1)?CVRRP更新间隔秒数。定义MASTER经过多少时间未向VRRP集合节点发出广播数据。

preemption-mode(yes|no;默认:yes)?C是否启用优先模式。

no?C一个backup节点在当前的master失效之前,是不会选择master,即使该backup的优先高于当前master的级别

yes?C该节点总是拥有最高优先级。

authentication(none|simple|ah;默认:none)?C使用VRRP的广播数据包的验证方法

none?C没有验证

simple?C纯文本的验证

ah?C验证标题使用HMAC-MD5-96算法

password(文本;默认:“”)?C需要验证时的密码,不使用验证时可以被忽略。8位字符长文本字符串(为纯文本验证方式);16位字符长文本字符串(为需要128位key的AH验证)

on-backup(名称;默认:“”)?C当节点为backup状态时执行的脚步

on-master(名称;默认:“”)-当节点为master状态时执行的脚步

注:

所有同一个集合的节点,必须使相同的vrid,interval,preemption-mode,authentication和password.

第255的优先级被保留为真正的虚拟路由的主机IP地址。

添加一个VRRP事例在ether1的接口上,一个虚拟路由的vrid设置为1,因为是虚拟路由的主机,所有优先级为255:

ipvrrp>addinterface=ether1vrid=1priority=255

ipvrrp>print

Flags:X-disabled,I-invalid,M-master,B-backup

0Iname=“vr1”interface=ether1vrid=1priority=255interval=1

preemption-mode=yesauthentication=nonepassword=“”on-backup=“”

on-master=“”

ipvrrp>

虚拟IP地址

操作路径:/ipvrrpaddress

属性描述

address(IP地址)?CIP地址适用于虚拟路由belongstothevirtualrouter

network(IP地址)?CIP地址的子网掩码addressofthenetwork

broadcast(IP地址)?CIP地址广播段

virtual-router(名称)-VRRP路由的名称

Notes

虚拟IP地址应与每个节点的虚拟路由器相同,

在vr1VRRP路由器上添加虚拟地址192.168.1.1/24:

admin@MikroTik]ipvrrp>addressaddaddress=192.168.1.1/24

...virtual-router=vr1

ipvrrp>addressprint

Flags:X-disabled,A-active

#ADDRESSNETWORKBROADCASTVIRUAL-ROUTER

0192.168.1.1/24192.168.1.0192.168.1.255vr1

ipvrrp>

一个简单的VRRP事例

让我们假设,我们有一个192.168.1.0/24的网络,且我们需要为它提供高效率的Internet连接。这个网络将作NAT,我们连接了两个不同的ISP,并且他们其中的一个优先选取(如:速度最快)。

这个例子在上面的图解中显示了如何用两个路由器配置VRRP.这两个路由器被初始化为以下:接口以启用,每一个接口都配置了相应的IP地址;路由表设置正确(应至少有一个默认路由);SRC-NAT或伪装应配置。如何设置这些配置,看各自的说明手册。

我们将假设这个接口的网段192.168.1.0/24以连接,并在VRRP路由器上命名为local

配置MasterVRRP路由器

首先将创建一个VRRP项,我们将这个路由器设置为优先选取,使用255的优先级

ipvrrp>addinterface=localpriority=255

ipvrrp>print

Flags:X-disabled,I-invalid,M-master,B-backup

0Mname=“vr1”interface=localvrid=1priority=255interval=1

preemption-mode=yesauthentication=nonepassword=“”on-backup=“”

on-master=“”

ipvrrp>

下一步,将虚拟IP地址添加到这个VRRP项目中

ipvrrp>addressaddaddress=192.168.1.1/24

...virtual-router=vr1

ipvrrp>addressprint

Flags:X-disabled,A-active

#ADDRESSNETWORKBROADCASTVIRTUAL-ROUTER

0192.168.1.1/24192.168.1.0192.168.1.255vr1

ipvrrp>

现在这个地址将出现在/ipaddress列表中:

ipaddress>print

Flags:X-disabled,I-invalid,D-dynamic

#ADDRESSNETWORKBROADCASTINTERFACE

010.0.0.1/2410.0.0.010.0.0.255public

1192.168.1.2/24192.168.1.0192.168.1.255local

8.多协议结合的RIP路由应用 篇八

各路由协议一般来说都定一个固定的preference值,preference值越小,协议对应的路由的优先级越高.一般情况下路由优先级规定如下:

直接路由 0

OSPF 路由 10

IS-IS的level 1的路由 15

IS-IS的level 2的路由 18

NSFnet主干的SPF路由 19

缺声网关和EGP缺省 20

重定向路由 30

由route socket得到的路由 40

由网管加入的路由 50

路由器发现的路由 55

静态路由 60

Cisco IGRP的路由 80

DCN的hello的路由 90

Berkeley的RIP路由 100

点对点接口聚集的路由 110

down状态的接口路由 120

聚集的缺省路由优先级 130

OSPF的扩展路由 140

BGP的路由 170

EGP的路由 200

路由的优先级的概念是优先级高的新路由可替代优先级低同信宿的路由,反之,则不然.不过,在具体实现中,有可能将对其作一定的改变.如quidway2501下的RIP-2提供了一个改变RIP路由优先级的命令.通过这个命令可改变RIP路由的优先级.quidway2501的配置静态路由时,也可指定路由的优先级,这是针对具体应用而作的处理.但是我们不鼓励修改优先级.

9.趣谈OSPF动态路由协议 篇九

OSPF 是自治系统内部路由协议, 负责计算同一个自治系统内的路由。在这里“自治系统”是指彼此相连的运行OSPF 路由协议的所有路由器的集合。对于OSPF来说, 整个网络只有“自治系统内”和“自治系统外”之分。需要注意的是:“自治系统外”并不一定在物理上或拓扑结构中真正的位于自治系统的外部, 而是指那些没有运行OSPF 的路由器或者是某台运行OSPF 协议的路由器中没有运行OSPF 的接口。

二、OSFP协议中DR、BDR

在广播和NBMA 类型的网络上, 任意两台路由器之间都需要传递路由信息 (flood) , 如果网络中有 N 台路由器, 则需要建立N * (N-1) /2 个邻接关系。任何一台路由器的路由变化, 都需要在网段中进行N* (N-1) /2 次的传递。这是没有必要的, 也浪费了宝贵的带宽资源。为了解决这个问题, OSPF 协议指定一台路由器DR (Designated Router) 来负责传递信息。所有的路由器都只将路由信息发送给DR, 再由DR 将路由信息发送给本网段内的其他路由器。两台不是DR 的路由器 (DROther) 之间不再建立邻接关系, 也不再交换任何路由信息。这样在同一网段内的路由器之间只需建立N 个邻接关系, 每次路由变化只需进行2N 次的传递即可。

DR 的选举过程如下: (1) 登记选民——本网段内的运行OSPF 的路由器; (2) 登记候选人——本网段内的Priority>0 的OSPF 路由器;Priority 是接口上的参数, 可以配置, 缺省值是1; (3) 竞选演说——部分Priority>0 的OSPF 路由器认为自己是DR; (4) 在所有自称是DR 的路由器中选priority 值最大的当选, 若两台路由器的priority值相等, 则选Router ID 最大的当选。选票就是HELLO 报文, 每台路由器将自己选出的DR 写入HELLO 中, 发给网段上的每台路由器。

三、OSFP协议中三张表

(一) 邻居表。

包括所有建立联系的邻居路由器。

(二) 链接状态表 (拓扑表) 。

包含了网络中所有路由器的链接状态。它表示着整个网络的拓扑结构。同Area内的所有路由器的链接状态表, 都是相同的。

(三) 路由表。

也称转发表, 在链接状态表的基础之上, 利用SPF算法计算而来。

四、OSFP协议中四种链路类型

(一) Broadcast。

当链路层协议是Ethernet 时, OSPF 缺省认为网络类型是Broadcast。在这种类型网络中, 以组播地址 (224.0.0.5, 224.0.0.6) 发送协议报文, 需要选举DR, BDR。

(二) NBMA。

当链路层协议是Frame Relay、X.25 时, OSPF 缺省认为网络类型是NBMA。在这种类型网络中, 以单播地址发送协议报文, 必须手工配置邻居的IP 地址, 需要选举DR, BDR。

(三) Point-to-Multipoint。

没有一种链路层协议会被缺省的认为是Point-to-Multipoint类型, 通常由NBMA的类型手工修改而来, 如果NBMA类型的网络不是全连通的。在这种类型网络中, 以组播地址 (224.0.0.5) 发送协议报文, 不需要选举DR, BDR。

(四) Point-to-Point。

当链路层协议是PPP, HDLC, LAPB时, OSPF缺省认为网络类型是Point-to-Point。在这种类型网络中, 以组播地址 (224.0.0.5) 发送协议报文, 不需要选举DR, BDR。

五、OSFP协议中五种的报文类型

(一) HELLO报文。

最常用的一种报文, 周期性的发送给本路由器的邻居。内容包括一些定时器的数值, DR, BDR, 以及自己已知的邻居。HELLO报文中包含有Router ID、Hello/dead intervals、Neighbors、Area-ID、Router priority、DR IP address、BDR IP address、Authentication password、Stub area flag等信息, 其中Hello/dead intervals、Area-ID、Authentication password、Stub area flag必须一致, 相邻路由器才能建立邻居关系。

(二) DBD报文。

两台路由器进行数据库同步时, 用DBD报文来描述自己的LSDB, 内容包括LSDB中每一条LSA的摘要 (摘要是指LSA的HEAD, 通过该HEAD可以唯一标识一条LSA) 。这样做是为了减少路由器之间传递信息的量, 因为LSA的HEAD只占一条LSA的整个数据量的一小部分, 根据HEAD, 对端路由器就可以判断出是否已经有了这条LSA。

(三) LSR报文。

两台路由器互相交换过DBD报文之后, 知道对端的路由器有哪些LSA是本地的LSDB所缺少的或是对端更新的LSA, 这时需要发送LSR报文向对方请求所需的LSA。内容包括所需要的LSA的摘要。

(四) LSU报文。

用来向对端路由器发送所需要的LSA, 内容是多条LSA (全部内容) 的集合。

(五) LSAck报文。

用来对接收到的DBD, LSU报文进行确认。内容是需要确认的LSA的HEAD (一个报文可对多个LSA进行确认) 。

六、Ospf协议中6种LSA

(一) Router LSA (Type=1) 。

是最基本的LSA类型, 所有运行OSPF的路由器都会生成这种LSA。主要描述本路由器运行OSPF的接口的连接状况, 花费等信息。对于ABR, 它会为每个区域生成一条Router LSA。这种类型的LSA传递的范围是它所属的整个区域。

(二) Netwrok LSA (Type=2) 。

本类型的LSA由DR生成。对于广播和NBMA类型的网络, 为了减少该网段中路由器之间交换报文的次数而提出了DR的概念。一个网段中有了DR之后不仅发送报文的方式有所改变, 链路状态的描述也发生了变化。在DROther和BDR的Router LSA中只描述到DR的连接, 而DR则通过Network LSA来描述本网段中所有已经同其建立了邻接关系的路由器。 (分别列出它们Router ID) 。同样, 这种类型的LSA传递的范围是它所属的整个区域。

(三) Network Summary LSA (Type=3) 。

本类型的LSA由ABR生成。当ABR完成它所属一个区域中的区域内路由计算之后, 查询路由表, 将本区域内的每一条OSPF路由封装成Network Summary LSA发送到区域外。LSA中描述了某条路由的目的地址、掩码、花费值等信息。这种类型的LSA传递的范围是ABR中除了该LSA生成区域之外的其他区域。

(四) ASBR Summary LSA (Type=4) 。

本类型的LSA同样是由ABR生成。内容主要是描述到达本区域内部的AS-BR的路由。这种LSA与Type3类型的LSA内容基本一样, 只是Type4的LSA描述的目的地址是ASBR, 是主机路由, 所以掩码为0.0.0.0。这种类型的LSA传递的范围与Type3的LSA相同。

(五) AS External LSA (Type=5) 。

本类型的LSA由ASBR生成。主要描述了到自治系统外部路由的信息, LSA中包含某条路由的目的地址、掩码、花费值等信息。本类型的LSA是唯一一种与区域无关的LSA类型, 它并不与某一个特定的区域相关。这种类型的LSA传递的范围整个自治系统 (STUB区域除外) 。

(六) AS External LSA (Type=7) 。

类型7的LSA被应用在非完全末节区域中 (NSSA) 。

七、OSPF的7种状态机

(一) Down。

邻居状态机的初始状态, 是指在过去的Dead-Interval时间内没有收到对方的Hello报文。

(二) Init。

本状态表示已经收到了邻居的HELLO报文, 但是该报文中列出的邻居中没有包含我的Router ID (对方并没有收到我发的HELLO报文)

(三) 2-Way。

本状态表示双方互相收到了对端发送的HELLO报文, 建立了邻居关系。在广播和NBMA类型的网络中, 两个接口状态是DROther的路由器之间将停留在此状态。其他情况状态机将继续转入高级状态。

(四) Ex Start。

在此状态下, 路由器和它的邻居之间通过互相交换DBD报文 (该报文并不包含实际的内容, 只包含一些标志位) 来决定发送时的主/从关系。建立主/从关系主要是为了保证在后续的DBD报文交换中能够有序的发送。

(五) Exchange。

路由器将本地的LSDB用DBD报文来描述, 并发给邻居。

(六) Loading。

路由器发送LSR报文向邻居请求对方的DBD报文。

(七) Full。

在此状态下, 邻居路由器的LSDB中所有的LSA本路由器全都有了。即, 本路由器和邻居建立了邻接 (adjacency) 状态。

八、结语

OSPF协议的SPF算法保证area内无环路。其中维护的3张表。邻居表 (显示邻接关系) , 拓扑表 (列举所有收到的LSA (link state advertisement) , 是一个LSA数据库) , 路由表 (记录到达某个网段的最佳路径, 是由前边2个表算出来的) 所有厂家都支持, 且数据包的格式都通用, 便于延展;带宽开销少, 触发式路由更新等优点, 所以广泛应用于各组网拓扑中。

摘要:OSPF是Open Shortest Path First (即“开放最短路由优先协议”) 的缩写。它是IETF (Internet Engineering Task Force) 组织开发的一个基于链路状态的自治系统内部路由协议 (IGP) , 用于在单一自治系统 (Autonomous system, AS) 内决策路由。在IP网络上, 它通过收集和传递自治系统的链路状态来动态地发现并传播路由。本文简要梳理了OSPF的相关知识点。

10.如何选择路由协议 篇十

常清

摘 要:无线传感器网络是继因特网之后对人类生活产生重大影响的技术,它在逻辑上将虚

幻的信息和真实的物理世界联系起来。无线传感器网络是由大量无处不在的、具有通信与计 算能力的微小传感器节点密集地布设在无人值守的监控区域而构成的能够根据环境自主完 成指定任务的智能自治测控网络系统。它能为人类生活带来不可估量的好处,所以,传感器 网络的路由协议的设计也是对人类的一项挑战,需要利用节点有限的能量更好的为人类服 务。目前已有多种路由协议,但其分类方式不是很清晰,本文以节点的传播方式为出发点,对几种典型的路由协议给予重新分类,并对其进行分析,最后选出相对好的类别。

1.引言

随着微电子技术、计算技术和无线通信技术的进步,多功能传感器快速发展,进而使无 线传感器网络(wireless sensor network, WSN)成为目前研究热点。WSN 是由部署在检测区域内的大量廉价微型传感器节点组成,形成一个多跳的自组织网络系统,使其在小体积内集成信息采集、数据处理和无线通信等功能,其目的是协作地感知、采集和处理网络覆盖区域中感知对象的信息,并提供给终端用户。WSN 能够广泛应用于军事、环境检测和预报、健康护理、智能家居、建筑物状态监控、复杂机械监控、城市交通、空间探索、大型车间和仓库管理、以及机场、大型工业园区的安全检测和其他商业等领域,且将逐渐深入到人类生活的各个领域。本文首先简要说明衡量路由协议的四个标准,然后就WSN 中路由协议的几种路由协议提出新的分类方法并利用标准加以比较。

2.路由协议的衡量标准

无线传感器网络的路由协议不同于传统网络的协议,它具有能量优先、基于局部的拓扑 信息、以数据为中心和应用相关四个特点,因而,根据具体的应用设计路由机制时,从四个 方面衡量路由协议的优劣【1】:(1)能量高效

传统路由协议在选择最优路径时,很少考虑节点的能量问题。由于无线传感器网络 中节点的能量有限,传感器网络路由协议不仅要选择能量消耗小的消息传输路径,更要 能量均衡消耗,实现简单而且高效的传输,尽可能地延长整个网络的生存期。(2)可扩展性

无线传感器网络的应用决定了它的网络规模不是一成不变的,而且很容易造成拓扑 结构动态发生变化,因而要求路由协议有可扩展性,能够适应结构的变化。具体体现在 传感器的数量、网络覆盖区域、网络生命周期、网络时间延迟和网络感知精度等方面。(3)鲁棒性

无线传感器网络中,由于环境和节点的能量耗尽造成传感器的失效、通信质量的降 低使网络变得不可靠,所以在路由协议的设计过程中必须考虑软硬件的高容错性,保障 网络的健壮性。

4)快速收敛性

由于网络拓扑结构的动态变化,要求路由协议能够快速收敛,以适应拓扑的动态变 化,提高带宽和节点能量等有限资源的利用率和消息传输效率。

3.路由协议的分类

针对不同传感器网络的应用,研究人员提出了不同的路由协议,目前已有的分类方式主 要有两种:按网络结构可以分为平面路由协议、分级网络路由协议和基于位置路由协议;按 协议的应用特征可以分为基于多径路由协议、基于可靠路由协议、基于协商路由协议、基于 查询路由协议、基于位置路由协议和基于QoS 路由协议。但这种分类方式太过分散,没有 整体概念,本文就各个协议的不同侧重点提出一种新的分类方法,把现有的代表性路由协议 按节点的传播方式划分为广播式路由协议、坐标式路由协议和分簇式路由协议。下面进行详 细的介绍和分析。

4.广播式路由协议

4.1 扩散法(Flooding)

扩散法是一种传统的网络通信路由协议。它实现简单,不需要为保持网络拓扑信息和实 现复杂的路由算法消耗计算资源,适用于健壮性要求高的场合。但是,扩散发存在信息爆炸 问题,即能出现一个节点可能得到数据多个副本的情况,而且也会出现部分重叠的现象,此 外,扩散法没有考虑各节点的能量,无法作出相应的自适应路由选择,当一个节点能量耗尽,网络就死去。

具体实现:节点 A 希望发送数据给节点B,节点A 首先通过网络将数据的副本传给其 每一个邻居节点,每一个邻居节点又将其传给除A 外的其他的邻居节点,直到将数据传到B 为止或者为该数据设定的生命期限变为零为止或者所有节点拥有此副本为止。

4.2 定向路由扩散DD(Directed Diffusion)

C.Intanagonwiwat【2】等人为传感器网络提出一种新的数据采集模型,即定向路由扩散。它通过泛洪方式广播兴趣消息给所有的传感器节点,随着兴趣消息在整个网络中传播,协议 逐跳地在每个传感器节点上建立反向的从数据源节点到基站或者汇聚节点的传输梯度。该协 议通过将来自不同源节点的数据聚集再重新路由达到消除冗余和最大程度降低数据传输量 的目的,因而可以节约网络能量、延长系统生存期。然而,路径建立时的兴趣消息扩散要执 行一个泛洪广播操作,时间和能量开销大。

具体实现:首先是兴趣消息扩散,每个节点都在本地保存一个兴趣列表,其中专门存在 一个表项用来记录发送该兴趣消息的邻居节点、数据发送速率和时间戳等相关信息,之后建 立传输梯度。数据沿着建立好的梯度路径传输。

4.3 谣传路由(Rumor Routing)

D.Braginsky【3】等人提出的适用于数据传输量较小的无线传感器网络高效路由协议。其 基本思想是时间监测区域的感应节点产生代理消息,代理消息沿着随机路径向邻居节点扩散 传播。同时,基站或汇聚节点发送的查询消息也沿着随机路径在网络中传播。当查询消息和 代理消息的传播路径交叉在一起时就会形成一条基站或汇聚节点到时间监测区域的完整路 径。

具体实现:每个传感器节点维护一个邻居列表和一个事件列表,当传感器节点监测到一 个事件发生时,在事件列表中增加一个表项并根据概率产生一个代理消息,代理消息是一个 包含事件相关信息的分组,将事件传给经过的节点,收到代理消息的节点检查表项进行更新 和增加表项的操作。节点根据事件列表到达事件区域的路径,或者节点随机选择邻居转发查 询消息。

4.4 SPIN(Sensor Protocols for Information via Negotiation)

W.Heinzelman【4】等人提出的一种自适应的SPIN 路由协议。该协议假定网络中所有节 点都是Sink 节点,每一个节点都有用户需要的信息,而且相邻的节点拥有类似的数据,所 以只要发送其他节点没有的数据。SPIN 协议通过协商完成资源自适应算法,即在发送真正 数据之前,通过协商压缩重复的信息,避免了冗余数据的发送;此外,SPIN 协议有权访问

每个节点的当前能量水平,根据节点剩余能量水平调整协议,所以可以在一定程度上延长网 络的生存期。

具体实现:SPIN 采用了3 种数据包来通信:ADV 用于新数据的广播,当节点有数据 要发送时,利用该数据包向外广播;REQ 用于请求发送数据,当节点希望接收数据时,发 送该报文;DATA 包含带有Meta-data 头部数据的数据报文;

当一个传感器节点在发送一个 DATA 数据包之前,首先向其邻居节点广播式地发送ADV 数据包,如果一个邻居希望接收该DATA 数据包,则像该节点发送REQ 数据包,接着节点向其邻居节点发送DATA 数据包。

4.5 GEAR(Geographical and Energy Aware Routing)

Y.Yu 等人提出了GEAR 路由协议,即根据时间区域的地址位置,建立基站或者汇聚节 点到时间区域的优化路径。把GEAR 划分为广播式路由协议有点牵强,但是由于它是在利 用地理信息的基础上将数据发送到合适区域,而且又是基于DD 提出,这里仍然作为广播式 的一种。具体实现:首先向目标区域传递数据包,当节点收到数据包时,先检查是否有邻居比它更接近目标区域。如有就选择离目标区域最近的节点作数据传递的下一跳节点。如果数据包已经到达目标区域,利用递归的地理传递方式【3】和受限的扩散方式发布该数据。

5.坐标式路由协议

5.1 GEM(Graph Embedding)

J.Newsome 和D.Song 提出了建立一个虚拟极坐标系统(VPCS, Virtual Polar 的

Coordinate System)GEM 路由协议,用来代表实际的网络拓扑结构。整个网络节点形成一 个以基站或汇聚节点为根的带环树(Ringed Tree)。每个节点用距离树根的跳数距离和角度 范围两个参数表示。

具体实现:首先建立虚拟极坐标系统,主要有三个阶段:由跳数建立路由并扩展到整个 网络形成生成树型结构,再从叶节点开始反馈子树的大小,即树中包含的节点数目,最后确 定每个子节点的虚拟角度范围。建立好系统之后,利用虚拟极坐标算法发送消息,即节点收 到消息检查是否在自己的角度范围内,不在就向父节点传递,直到消息到达包含目的位置角 度的节点。另外,当实际网络拓扑结构发生变化时,需要及时更新,比如节点加入和节点失效

5.2 GRWLI(Geographic Routing Without Location Information)

A.Rao【3】等人提出了建立全局坐标系的路由协议,其前提是需要少数节点精确位置信 息。首先确定节点在坐标系中的位置,根据位置进行数据路由。关键是利用某些知道自己位 置信息的信标节点确定全局坐标系及其他节点在坐标系中的位置。

具体实现:A.Rao 等人提出了3 中策略确定信标节点。一是确定边界节点都为信标节 点,则非边界节点通过边界节点确定自己的位置信息。在平面情况下,节点通过邻居节点位 置的平均值计算。二是使用两个信标节点,则边界节点只知道自己处于网络边界不知道自己 的精确位置消息。引入两个信标节点,并通过边界节点交换信息建立全局坐标系。三是使用 一个信标节点,到信标节点最大的节点标记自己为边界节点。

6.分簇式路由协议

6.1 LEACH(Low Energy Adaptive Clustering Hierarchy)

MIT 的Chandrakasan【5】等人为无线传感器设计的一种分簇路由算法,其基本思想是以 循环的方式随机选择簇首节点,平均分配整个网络的能量到每个传感器节点,从而可以降低 网络能源消耗,延长网络生存时间。簇首的产生是簇形成的基础,簇首的选取一般基于节点 的剩余能量、簇首到基站或汇聚节点的距离、簇首的位置和簇内的通信代价。簇首的产生算

法可以被分为分布式和集中式两种【6】,这里不予介绍。

具体实现:LEACH 不断地循环执行簇的重构过程,可以分为两个阶段:一是簇的建立,即包括簇首节点的选择、簇首节点的广播、簇首节点的建立和调度机制的生成。二是传输数 据的稳定阶段。每个节点随机选一个值,小于某阈值的节点就成为簇首节点,之后广播告知 整个网络,完成簇的建立。在稳定阶段中,节点将采集的数据送到簇首节点,簇首节点将信 息融合后送给汇聚点。一段时间后,重新建立簇,不断循环。

6.2 GAF(Geographic Adaptive Fidelity)

Y.Xu【3】等人提出的一种利用分簇进行通信的路由算法。它最初是为移动Ad Hoc 网络 应用设计的,也可以适用于无线传感器网络。其基本思想是网络区被分成固定区域,形成虚 拟网格,每个网格里选出一个簇首节点在某段时间内保持清醒,其他节点都进入睡眠状态,但是簇首节点并不做任何数据汇聚或融合工作。GAF 算法即关掉网络中不必要的节点节省 能量,同样可以达到延长网络生存期的目的。

具体实现:当划分好固定的虚拟网格之后,网络中每个节点利用 GPS 接受卡指示的位 置信息将节点本身与虚拟网格中某个点关联映射起来。网格上同一个点关联的节点对分组路 由的代价是等价的,因而可以使某个特定网格区域的一些节点睡眠,且随着网络节点数目的 增加可以极大地提高网络的寿命,在可扩展性上有很好的表现。

7.比较与分析

经过上面的简单介绍,每个协议在其设计的时候都有各自的侧重点和最优的方面,按照 衡量标准可以把以上协议做简略的比较并找出相对较好的一类协议。其中,如何提供有效的 节能,即能量有效性是无线传感器网络路由协议最首要注重的方面,可扩展性和鲁棒性是路 由协议应该满足的基本要求,而快速收敛性和网络存在的时间有紧密的联系。依据上述四个 标准,对本文所列举的路由协议的比较见表1。

由上表可见,广播式总是存在一种矛盾,当具有好的扩展性时势必以差的鲁棒性和能量 高效为代价,即以牺牲鲁棒性换取扩展性和高能量,这同时也严重影响了节点的快速收敛性。而坐标式弥补了广播式的不足,可以同时达到四个衡量标准。分簇式相对于前两种方式来说,具备了较好的性能,可以满足人们对传感器网络的一般要求。所以,以能量高效、可扩展性、鲁棒性和快速收敛性四个基本标准来衡量路由协议,分簇式是最佳的选择。

8.总结

本文首先确定了四个衡量路由协议的标准,并按一种新的方法把现有一些协议分成三 类,之后进行比较,最后得出分簇式是相对来讲最优的路由协议类。但是,分簇式只是相对 较好的协议类别,由于分簇式总是依附簇首节点的能量,即使簇首在不断的更替选出,仍有 最后某个簇首节点能量耗尽的情况,因此势必影响整体网络的生存时间。再者,由于衡量标 准的局限性,本文未能考虑安全性等方面的要求,因此得出的结论仅仅是一定的范围内比较 结果。由此,一种尽可能考虑多方面要求的路由协议仍是被期望的。参考文献

11.五个无线路由器选择标准 篇十一

对于普通家庭用户来说,网络知识有限,因此我们选购的产品最好是有简洁的基于浏览器配置的管理界面,能有智能配置向导,能提供软件升级。笔者有幸试用过几款无线产品,在这些品牌中,Netcore(磊科)的路由器,在产品升级方面做的相对较好,它的升级包更新较快,同时是终身免费的,售后服务也不错。

现在上网对于很多人来说已经成为每天生活的一部分,更便捷灵活的上网方式也成为人们追求的新目标。随着无线设备价格不断下降,普通人实现无线网络的梦想,已成为现实。希望上面一些选购的技巧能给大家带来一些小帮助。

12.如何选择路由协议 篇十二

摘要:

针对我国煤矿井下特殊的环境,基于LEACH路由协议提出新的高效,能量均衡的分簇 路由协议。簇首节点选取将以邻居节点的平均剩余能量与节点本身的剩余能量的比值,与邻 居节点的距离作为节点竞争簇头的参数,簇内节点均加入距离自己最近的簇头节点;经数据 融合后的簇首节点之间通过多跳方式通信,最终将融合后的信息通过网关节点,由有线网络 发送到地面的监控系统。利用NS2进行仿真,实验结果证明,改进后的协议能够均衡网络节点能耗,延长网络生命时间,适应煤矿井下特殊环境。1 前言

目前,我国煤矿采用的检测系统都以工业总线作为基础,井下检测系统与地面信息中心一般通过电缆或者光纤连接,构成有线的检测系统。但有线系统对线路依赖性强,受布线局 限,且需要专业人员维护,一旦设备出现故障,会使局部区域失去监测能力。因此,有线通 信其扩展性,网络覆盖率,灵活性存在不足,成本较高。但无线传感网络的出现给煤矿监控带来前所未有的希望,无线传感器网络具有放置灵活、扩展简便、移动性强、具有自组织性等特点,因此建立基于无线传感网络的煤矿无线监测系统可以对有线监控系统起到强大的补充功能,无线与有线的结合,将极大的提高全煤矿的安全监控水平。

但是,通常传感器节点的通信距离有限,在10~100 m范围内,节点只能与其射频覆盖范围内的邻居直接通信,因此限制了无线传感器网络在大规模范围的应用。现有的路由协议具有良好的自组织性,在一定程度上提高了网络的自组织性能,延长了网络寿命,但大多数适合小规模网络,节点的能耗分布不均衡,不适用于工作面有限异质可变空间,并且工作面的不断向前推进,信息流量不均衡,对网络的自组织性也提出了更高的要求。2 LEACH路由协议

路由协议按网络的拓扑结构可分为2类:平面路由协议和分簇路由协议。在平面路由协议中,各节点地位平等,通过局部操作和反馈信息来生成路由。平面路由缺乏对通信资源的优化管理,对网络动态变化的反应速度较慢。在分簇路由协议中,通常对网络中的节点进行层次划分,若干地理位置相邻的节点构成一个簇,每个簇内选举一个簇首。簇首节点负责簇内信息的收集、融合及簇间数据的转发。

分簇路由便于管理,能对系统变化做出快速反应,为网络提供高质量的通信服务。

典型的分簇路由协议LEACH(low energy adaptive clustering hierarchy)协议是Heinzelman 等人2002年提出的基于分簇的层次性路由协议,它采用分簇的网络结构,各节点独立地按照一定概率决定自己是否做簇首,周期性地进行簇首选举和网络重组,避免簇首节点能耗过 多,影响网络寿命。相比一般的平面协议或静态分簇协议,LEACH可以减少网络能量损耗,延长网络生命周期。在此基础上,很多人基于不同应用提出了改进方案,如Stephanie Lindsey等人提出的PEGASIS(power-efficient gathering in sensor information systems)协议,就是对LEACH协议的改进,其基本思想是使节点仅和它们最近的邻节点进行通信,增加网络生命时间。

研究发现,这些分簇路由协议具有很好的自组织特性,一定程度上提高了网络性能,延 长了网络寿命。但在工作面上无线传感网络是由信息采集端向外单向传输,组成的网络节点是一种带状分布、信息流量不均衡的网络,会造成节点的功耗分布不均,接近出口的汇聚节 点数据流量大,负载重,寿命短等现象。另外,随工作面的不断向前推进,网络结构将随之变化。现有的路由协议无法满足矿井下这种特殊环境。因此在LEACH路由协议的基础上,本文提出了一种能量平衡的大规模无线传感器网络分簇路由协议,以实现节能和均衡能耗相结合。3 网络模型

3.1 假设

为增加模拟工作面的真实性,我们将仿真场景大小设置为长带状区域,N个节点随机的布置在该区域。节点需满足以下条件: 所有的节点具有相同的且与无线电信号在各个方向上能耗相同,各节点的初始能量相等且能量有限,能感知自己的剩余能量,且具有功率控制能力可以改变发射功率,从而控制发送的距离,每个节点都具有足够的计算能力支持不同的MAC协议和数据处理。2 所有节点的通信距离不超过节点的有效通信距离 sink节点是固定放置在巷道的末端,且有持续的电源供给 4 相邻节点采集的数据具有较高的相关性,可进行数据融合 5 所有节点时间同步 3.2具体的能量公式

该模型考虑了发射电路的发射能量、接收电路接收能量, 且能量损耗与传输距离有关。发射机发射m比特消息消耗的能量为:

2mEelecmEfsd,dd0ETx(m,d)

(1)4mEelecmEmpd,dd0接收机接收m比特消息消耗的能量为:

ERx(m)mEelec

(2)ETx(m,d)为发射m比特数据所消耗的能量,ERx(m)为收到m比特数据所消耗的能量,d为传输距离,Eelec为每发送或接收1比特数据传输所消耗的能量,Efs为自由空间常数,Emp为多路径衰落传输常数,Efs和Emp与所采用的输信道模型有关。d0为传输距离的门限值d0Efs,当传输距离大于d0时数据传输的消耗相当大。Emp4分簇路由协议改进方案 4.1 簇形成过程

在LEACH协议中,簇首的产生具有很大的随机性,不能均衡能耗。矿井工作面的特殊 地形,各个簇都是相邻的,LEACH协议没有考虑节点的剩余能量,地理位置等因素。因此,我们根据工作面的特殊环境,设计改进的LEACH协议LEACH—IM 协议。在LEACH的基础上,簇头节点的个数为N,我们假设理想的成簇概率为P,最终成簇的数目为K=NP。簇 首节点选取将以邻居节点的平均剩余能量与节点本身的剩余能量的比值,担任簇首节点的总个数及邻居节点个数作为节点竞争簇头的参数。将能量的比值转化成时延,比值越小,时延越小,反之时延越大。网络所有节点在成为簇头之前,均等待一个时延,时延先到达的节点优先成为簇首节点。

在描述算法之前,先规定每个节点保存各自信息(节点ID,初始能量,节点剩余能量)及邻居节点信息(节点ID,剩余能量)。每轮分簇开始时,规定获取邻居节点信息时段为 TD。每个节点将以通信半径r,广播自身信息(节点ID,节点剩余能量Er)然后接收邻居节点信息,并更新本节点信息中邻居节点的平均剩余能量Ea和邻居节点的个数d。任取某节点Vi,邻居节点Vj,则Vi节点的平均剩余能量为:

1dEaEr

dj1当Vi节点的剩余能量Er>Ea时:

(3)t1Ea1TD

Erd(4)当Vi节点的剩余能量ErEa时:

t2TDET(1r)D

2E

2(5)在上式中的E是节点的初始能量,ρ是一个均匀分布在[0.9,1]之间的一个随机实数,其作用是减小两个节点可能取相同t值的概率。

在LEACH协议中簇首的选择还考虑到该节点在过去的操作中担当簇首节点的次数,在LEACH—IM协议中,我们将节点担当簇首节点的总时间作为衡量参数。我们将采用基于加权的分簇算法。

节点i的权值计算公式表示为:

Wiwt1w2T(to)

(6)其中,w1、w2是加权因子且满足w1w21。t表示由上式邻居节点的平均剩余能量与节点本身的剩余能量的比值转化成的时延;T(to)表示该节点从网络运行开始当过簇首的总时间。若节点的剩余能量较多,担任簇首节点的时间较短,则时延先到达的节点将优先成为簇头节点。

簇首确定后,其他节点从睡眠中醒来,接收簇首节点广播的信息,依据距离远近选择要加入的簇,并向簇首发送个人信息。簇首在接到节点加入信息后,将根据加入节点的数目,为簇内每个节点分配一个通信时隙,告知节点何时发送数据,至此就形成整个网络。簇形成之后就不再改变,当簇首节点低于预设的门限值后,将在簇内重新选择簇首节点,选择依据依然参照公式(6)。4.2 数据传输

形成簇之后,簇首节点将对采集到的数据进行必要处理和融合,随后进入数据传输阶段。数据传输包括簇内传输和簇间传输。簇内传输采用TDMA模式,可有效的防止信道冲突,节约能量;而簇间传输,传输数据量大,能耗大,考虑到工作面的特殊环境和采集检测数据的冗余性,我们采用最小生成树算法的多跳路由,实现簇头节点与sink节点的通信。5仿真结果

为了比较LEACH及其改进协议LEACH-IM的性能,将这两个算法在NS2中仿真。假 设仿真环境为400m * 10m,节点总数N=200个,节点的初始能量为2J,sink节点位于原点(0,0),理想的成簇概率为P=8%,能量模型参数参照文献[y]:Eelec50nJ/bit,Efs10nJ/bit/m2,Emp0.013nJ/bit/m2,代入公式可以得到有效通信距离

d087.7m,但参照文献[y],依照具体的应用环境,有效通信距离为d050m。最优簇首节点个数Kp*N16。簇内簇间数据融合率设置为0.7。

0.80.70.60.50.40.30.20.10——LEACH+-+-LEACH-IM节点死亡概率050010001500工作周期轮数200025003000

图1

图1显示了网络中节点死亡率随工作周期数的变化情况。从图中结果可以看出,LEACH-IM在延长网络生存时间方面性能突出。此外,从第一个节点开始死亡的时间点来看, LEACH-IM也具有明显的优势。结果还表明,LEACH-IM死亡速率变化相当缓慢。表明CEUC使整个网络的能耗分布趋于平均,使各节点的能量几乎同时耗尽,避免了某些节点被过度使用。

——LEACH+-+-LEACH-IM21.5节点平均能耗10.50050010001500工作周期轮数200025003000

图2 图2在能耗指标上对LEACH和LEACH-IM进行了比较。可以看到,LEAC-IM方法

使得簇内节点能耗均衡,每轮的能耗都比LEACH协议少很多;而LEACH簇内节点能耗与簇首位置分布及数目相关,当簇首分布均匀时簇内节点能耗均衡,反之不均衡,因此每轮的性能十分不稳定。新的算法比LEACH有了显著改进。4结束语

本文通过对LEACH协议的分析,并针对矿井下的实际环境对协议进行改进。仿真结果显示,改进后的协议能更好地平衡网络负载、节约能量消耗且具有更高的能量使用效率,实现了多方面的优化。参考文献

[1] 孙利民,李建中,陈 渝,等.“无线传感器网络”[M].北京:清华大学出版社,2005:3-4.Sun [2] 徐卫克.LEACH协议成簇机制的改进计算机与现代化[A] 2010年第11期:72—79 Xu Weike.[3] 吴 征,朱 军,韩永远。一种新的基于LEACH的WSN分簇协议[J],计算机技术与发展.2010.Vol.20 No.5:29—33

[4] 周莉娟,陈光柱,罗成名.采煤工作面无线传感器网络的无线通信信道建模,传感技术学报。2010 Vol 23 No.5: 722—726

[5] Soojung Hur,Jaehyen Kim,Jeonghee Choi,Yongwan Park.“An Efficient Addressing Scheme and Its Routing Algorithmfor a Large-ScaleWireless Sensor Network” EURASIP Journal onWireless Communications and Networking.Volume 2008,1—13 [6] Neeraj Kumar, Manoj Kumar, R.B.Patel.“Coverage and Connectivity Aware Neural Network Based Energy Efficient Routing in Wireless Sensor Networks” International jouenal on applications of graph theory in wireless ad hoc networks and sensor networks,Vol.2,No1,2010:45—60 [7] Adeel Akhtar, Abid Ali Minhas, and Sohail Jabbar.“Energy Aware Intra Cluster Routing for Wireless Sensor Networks” International Journal of Hybrid Information Technology Vol.3, No.1, January, 2010 :29—47 [8] 曲文虎,谷雨,屈玉贵 管彬“WSN中一种最优的汇聚节点移动方案”通信技术。Vol.43,No.08,2010 9—11

上一篇:舞会活动策划书下一篇:新教师培养工作总结