DTN与新兴信息转移模式北京邮电大学计算机学院 段鹏瑞
提纲 ?DTN网络概述 ?DTN网络体系结构?DTN路由机制 ?节点移动模型 ?DTN网络支撑技术?应用
DTN网络概述 ?DTN ?Delay Tolerant Networks，Disruption Tolerant Networks， 容迟网络、容断网络、受限网络 ?DTN is a network of regional networks. It is an overlay on top of regional networks, including the Internet. ?DTN 最初是容迟网络研究组(DTNRG)为星际网络 IPN(interplanetary network)通信而提出来的,其主要目标是支持具有间歇性连通、延迟大、错误率高等通信特征的不同网络的互联和互操作,如互联Internet 和传感器网络、移动自组织网络等.
?物联网的四层架构 ?DTN 网络体系由多个底层运行独立通信协议的DTN 域组成,域间网关利用“存储-转发” 的模式工作,当去往目标DTN 域的链路存在时转发消息,否则,将消息存储在本地持久存储器中等待可用链路.服务理解交换感知 DTN网络概述
新型的网络 ?星际网络InterPlaNetary ?野生动物监测跟踪网 ?乡村通信网 ?水下传感网 ?车载网 ?Wireless military battlefield networks
传统TCP/IP网络 ?Internet ?A network of networks ?Packet switching ?IP with different link layer ?IP over everyting ?Everything over IP
路由算法及分类 路由算法及分类： 1、非自适应算法，静态路由算法 不能根据网络流量和拓扑结构的变化更新路由表，使用静态路由表，也称为固定式路由选择算法。 特点：简单，开销少；灵活性差。 2、自适应算法，动态路由算法 可根据网络流量和拓扑结构的变化更新路由表。 特点：开销大；健壮性和灵活性好。 3、最优化原则（optimality principle） 如果路由器J 在路由器I 到K 的最优路由上，那么从J 到K 的最优路由会落在同一路由上。 4、汇集树（sink tree） 从所有的源结点到一个给定的目的结点的最优路由的集合形成了一个以目的结点为根的树，称为汇集树； 路由算法的目的是找出并使用汇集树。 几种典型的路由选择算法： 1、最短路径路由算法（Shortest Path Routing） 1）基本思想 构建子网的拓扑图，图中的每个结点代表一个路由器，每条弧代表一条通信线路。为了选择两个路由器间的路由，算法在图中找出最短路径。
2）测量路径长度的方法 结点数量 地理距离 传输延迟 距离、信道带宽等参数的加权函数 3）Dijkstra算法 每个结点用从源结点沿已知最佳路径到本结点的距离来标注，标注分为临时性标注和永久性标注； 初始时，所有结点都为临时性标注，标注为无穷大； 将源结点标注为0，且为永久性标注，并令其为工作结点； 检查与工作结点相邻的临时性结点，若该结点到工作结点的距离与工作结点的标注之和小于该结点的标注，则用新计算得到的和重新标注该结点； 在整个图中查找具有最小值的临时性标注结点，将其变为永久性结点，并成为下一轮检查的工作结点； 重复第四、五步，直到目的结点成为工作结点； 2、洪泛及选择洪泛算法 1）洪泛算法（Flooding） 属于静态路由算法 a)基本思想 把收到的每一个包，向除了该包到来的线路外的所有输出线路发送。
无线传感器网络的关键技术有路由协议、MAC协议、拓扑控制、定位技术等。路由协议: 数据包的传送需要通过多跳通信方式到达目的端,因此路由选择算法就是网络层设计的一个主要任务。路由协议主要负责将数据分组从源节点通过网络转发到目的节点,它主要包括两个方面的功能: 1、寻找源节点与目的节点间的优化路径。 2、将数据分组沿着优化路径正确转发。 无线传感器与传统的无线网络协议不同之处,它受到能量消耗的制约,并且只能获取到局部拓扑结构的信息,由于这两个原因,无线传感器的路由协议要能够在局部网络信息的基础上选择合适路径。传感器由于它很强的应用相关性,不同应用中的路由协议差别很大,没有通用的路由协议。无线路由器的路由协议应具备以下特点: （1）能量优先。需要考虑到节点的能量消耗以及网络能量均衡使用的问题。（2）基于局部拓扑信息。WSN为了节省通信能量,通常采用多跳的通信模式,因此节点如何在只能获取到局部拓扑信息与资源有限的情况下实现简单高效的路由机制,这就是WSN的一个基本问题。 （3）以数据为中心。传统路由协议通常以地址作为节点的标识与路由的依据,而WSN由于节点的随机分布,所关注的就是监测区域的感知数据,而不就是具体哪个节点获取的信息,要形成以数据为中心的消息转发路径。（4）应用相关。设计者需要针对每一个具体应用的需求,设计与之适应的特定路由机制。 现介绍几种常见的路由协议(平面路由协议、网络分层路由协议、地理定位辅助路由协议): 一、平面路由协议 平面路由协议中,逻辑结构时平面结构,节点间地位平等,通过局部操作与反馈信息来生成路由。当汇聚点向某些区域发送查询并等待来自于这些区域内传感器所采集的相关数据,其中的数据不能采用全局统一的ID,而就是要采用基于属性的命名机制进行描述。平面路由的优点就是结构简单、鲁棒性(即路由机制的容错能力)较好,缺点就是缺乏对通信资源的优化管理,对网络动态变化的反应速度较慢。其中典型的平面路由协议有以下几种: 1、1、洪泛式路由(Flooding): 这就是一种传统的网络通信路由协议。这种算法不要求维护网络的拓扑结构与相关路由的计算,仅要求接受到信息的节点以广播形式转发数据包。例如:S节点要传送一段数据给D节点,它需要通过网络将副本传送给它每一个邻居节点,一直到传送到节点D为止或者为该数据所设定的生存期限为零为止。优点在于:实现简单;不需要为保持网络拓扑信息与实现复杂路由发现算法消耗计算资源;适用于鲁棒性较高的场合。但同时也有相应的缺点:一个节点可能得到一个数据的多个副本;存在部分重叠,如果相邻节点同时对某件事作出反应,则两个节点的邻居节点将收到两份数据副本;盲目使用资源,无法作出自适应的路由选择。 为克服Flooding算法这些固有的缺陷,S、Hedetniemi等人提出闲聊式(Gossiping)策略。这种算法采用随机性原则,即节点发送数据时不再采用广播形式,而就是随机选取一个相邻节点转发它接收到的数据副本(避免了消息爆炸的结果)。
1、RIP overview： 1. rip是tcp/ip协议开发的第一个路由选择标准；是一个distance vector协议，协议号为17；利用UDp来封装数据，用520端口发 送接受更新。 2. rip适用于小型网络，路由器数目不大于15台（默认16台不可 达），广播更新。 3. 发送和接收的更新为路由表条目，并且每个更新包最多携带25 条路由条目。 4. 基本原理：每个启动RIP协议的端口发出目标为 255.255.255.255的广播（RIP Request message），其邻居路由 器收到后发送他所知道的路由表信息（Response message）， 同时在发出后出端口的时候将hop count加1（如果路由表中显 示的跳数为“1”则表示通告路由器是与自己直连的）以上过程 周期性执行（默认30秒一次）；当接收方收到更新后就作如下 处理： ⑴更新信息是自己没有的，则加入路由表。 ⑵更新信息的目标是自己有的，则比较跳数，如果比自己原有的小 则更新路由表； 如果跳数比较大或为不可达（跳数大于15），则看更新信息的源地址（即为自己 去往目标的下一跳），是否与自己原来的下一跳一样，如果不一样则丢弃此更新； 如果一样，这时为了防止有不断变化的产生会启动抑制计时器（Holddown timer） 默认180秒，同时将该路由设为不可达，如果在180秒后还收到同样的更新消息 则接受。 ⑶对于接受的更新在加入路由表的同时会附加一个无效计时器 （Invalidation timer） 默认180秒，即在180秒后还没收到相关更新信息则认为不可达设跳数为16，如 果在过60秒（一共240秒）还没收到则从路由表中删除该条路由（刷新计时器 （flush timer））。这样做的好处是防止了路由黑洞 ⑷为了防止同时发更新造成广播风暴，随机设置一个25.5～30秒的数值以实 现不同 时送更新，这就是debug时看到的更新间隔不为30秒的原因。
计算机网络实验报告 班级： 姓名： 学号：
实验一 一．实验目的及要求 编写程序，模拟距离矢量路由算法的路由表交换过程，演示交换后的路由表的变化。 二．实验原理 距离矢量路由算法是这样工作的：每个路由器维护一张路由表（即一个矢量），它以网络中的每个路由器为索引，表中列出了当前已知的路由器到 每个目标路由器的最佳距离，以及所使用的线路。通过在邻居之间相互交换 信息，路由器不断地更新他们的内部路由表。 举例来说，假定使用延迟作为“距离”的度量标准，并且该路由器发送一个列表，其中包含了他到每一个目标路由器的延时估计值；同时，他也从 每个邻居路由器接收到一个类似的列表。假设一个路由器接收到来自邻居x 的一个列表，其中x（i）表示x估计的到达路由器i所需要的时间。如果该 路由器知道他到x的延时为m毫秒，那么他也知道在x（i）+m毫秒之间内经 过x可以到达路由器i。一个路由器针对每个邻居都执行这样的计算，就可 以发现最佳的估计值，然后在新的路由器表中使用这个最佳的估计值以及对 应的输出路线。 三．源程序： #include "stdio.h" #include "stdlib.h" #include "malloc.h" #include "graphics.h" #include "dos.h" #define VERNUM 7 typedef struct { int dis; int flag; int flag2; }RoutNode; char tmp[10]; RoutNode data[VERNUM][VERNUM]; void welcome(); void InitRoutData(FILE* pfile); void PrintRoutData(); void SendInf(int recv, int send); void Exchange(); int main() { int start, end, i, j, m, n; FILE *pfile;
收稿日期：２０１１－０６－ ２４基金项目：国家自然科学基金资助项目（６１１０１２１４ ）作者简介：周瑞涛（１９８１—），男，博士生，Ｅ－ｍａｉｌ：ｚｒｔ＠ｂｉｔ．ｅｄｕ．ｃｎ；曹元大（１９４４—），男，教授，博士生导师，Ｅ－ｍａｉｌ：ｙ ｄｃａｏ＠ｂｉｔ．ｅｄｕ．ｃｎ．第３２卷 第９期２０１２年９月 北京理工大学学报 Ｔｒａｎｓａｃｔｉｏｎｓ ｏｆ Ｂｅｉｊｉｎｇ Ｉｎｓｔｉｔｕｔｅ ｏｆ ＴｅｃｈｎｏｌｏｇｙＶｏｌ．３２ Ｎｏ．９Ｓｅｐ ．２０１２基于社区的容迟网络路由方法 周瑞涛１， 曹元大１， 胡晶晶２， 朱东锋 １ （１．北京理工大学计算机学院智能信息技术实验室，北京 １０００８１；２．北京理工大学软件学院，北京 １０００８１）摘 要：提出一种基于社区的容迟网络路由方法．通过对网络节点历史运动轨迹点聚类建立其热点活动区域，把热点区域重叠度较高的节点归为同一社区．在源节点和目的节点社区中以洪泛的方式加快消息扩算和传递速度．同时，针对热点区域准确地选择中继节点，降低了冗余消息数量．模拟结果显示，该方法能够提高消息传递数量，并且大大降低系统负载率． 关键词：容迟网络（ＤＴＮ） ；聚类；社区中图分类号：ＴＰ ３９３．０３ 文献标志码：Ａ 文章编号：１００１－０６４５（２０１２）０９－０９６６－ ０５Ｃｏｍｍｕｎｉｔｙ Ｂａｓｅｄ Ｒｏｕｔｉｎｇ ｉｎ Ｄｅｌａｙ ａｎｄ Ｔｏｌｅｒａｎｃｅ ＮｅｔｗｏｒｋｓＺＨＯＵ Ｒｕｉ－ｔａｏ１， ＣＡＯ Ｙｕａｎ－ｄａ１， ＨＵ Ｊｉｎｇ－ｊｉｎｇ２， ＺＨＵ Ｄｏｎｇ－ｆｅｎｇ １ （１．Ｂｅｉｊｉｎｇ Ｌａｂｏｒａｔｏｒｙ ｏｆ Ｉｎｔｅｌｌｉｇｅｎｔ Ｉｎｆｏｒｍａｔｉｏｎ Ｔｅｃｈｎｏｌｏｇｙ，Ｓｃｈｏｏｌ ｏｆ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ，Ｂｅｉｊｉｎｇ Ｉｎｓｔｉｔｕｔｅ ｏｆＴｅｃｈｎｏｌｏｇｙ，Ｂｅｉｊｉｎｇ １０００８１，Ｃｈｉｎａ；２．Ｓｃｈｏｏｌ ｏｆ Ｓｏｆｔｗａｒｅ，Ｂｅｉｊｉｎｇ Ｉｎｓｔｉｔｕｔｅ ｏｆ Ｔｅｃｈｎｏｌｏｇｙ，Ｂｅｉｊｉｎｇ １０００８１，Ｃｈｉｎａ）Ａｂｓｔｒａｃｔ：Ａ ｎｅｗ ｔｅｃｈｎｉｑｕｅ ｆｏｒ ｃｏｍｍｕｎｉｔｙ ｂａｓｅｄ ｒｏｕｔｉｎｇ ｉｎ ｄｅｌａｙ ａｎｄ ｔｏｌｅｒａｎｃｅ ｎｅｔｗｏｒｋｓ（ＤＴＮｓ）ｉｓ ｐｒｏｐｏｓｅｄ．Ｔｈｅ ｈｉｓｔｏｒｙ ｍｏｂｉｌｉｔｙ ｔｒａｃｋｓ ａｒｅ ｕｓｅｄ ｔｏ ｅｓｔａｂｌｉｓｈ ｔｈｅ ｍｏｓｔ ｖｉｓｉｔｅｄ ａｒｅａ ｏｆ ＤＴＮｎｏｄｅｓ，ｃａｌｌｅｄ ｈｏｍｅ ａｒｅａ，ｔｈｒｏｕｇｈ ｃｌｕｓｔｅｒｉｎｇ．Ｔｈｅ ｎｏｄｅｓ ｗｈｏｓｅ ｈｏｍｅ ａｒｅａｓ ｏｖｅｒｌａｐ ｍｏｓｔ ａｒｅｒｅｇａｒｄｅｄ ａｓ ｉｎ ｔｈｅ ｓａｍｅ ｃｏｍｍｕｎｉｔｙ．Ｔｈｅ ｄｅｌｉｖｅｒｙ ｓｐｅｅｄ ｃｏｕｌｄ ｂｅ ａｃｃｅｌｅｒａｔｅｄ ｂｙ ｆｌｏｏｄｉｎｇ ｎｏｄｅｓ ｉｎｔｈｅ ｓｏｕｒｃｅ ａｎｄ ｄｅｓｔｉｎａｔｉｏｎ ｃｏｍｍｕｎｉｔｉｅｓ．Ｆｕｒｔｈｅｒｍｏｒｅ，ｔｈｅ ｈｏｍｅ ａｒｅａ ｆａｃｉｌｉｔａｔｅｓ ｔｈｅ ｓｅｌｅｃｔｉｏｎ ｏｆｉｎｔｅｒｍｅｄｉａｔｅ ｎｏｄｅｓ．Ｓｉｍｕｌａｔｉｏｎ ｒｅｓｕｌｔｓ ｓｈｏｗ ｔｈａｔ ｔｈｉｓ ｍｅｔｈｏｄ ｃｏｕｌｄ ｉｍｐｒｏｖｅ ｔｈｅ ｍｅｓｓａｇｅ ｄｅｌｉｖｅｒｙｒａｔｅ ａｎｄ ａｃｈｉｅｖｅ ｌｅｓｓ ｏｖｅｒｈｅａｄ．Ｋｅｙ ｗｏｒｄｓ：ｄｅｌａｙ ａｎｄ ｔｏｌｅｒａｎｃｅ ｎｅｔｗｏｒｋｓ（ＤＴＮ）；ｃｌｕｓｔｅｒ；ｃｏｍｍｕｎｉｔｙ 容迟网络体系结构用来解决受限环境下的网络通信问题［１］ ，此类环境中，由于节点的运动规律、生命周期等特性，节点间往往不存在一条永久的端到端路径，例如星际网络、传感器网络等． “存储转发”是该类网络最基本的路由方式．消息需要缓存在中继节点中等待合适的转发机会出现才被传至下一跳节点，直到成功传递．容迟网络路由技术要解决的关键问题是如何选择合适的中继节点． Ｅｐ ｉｄｅｍｉｃ［２］ 通过以洪泛方式传播消息，能够适应各种网络环境，但是往往导致非常高的网络负载；通过限制Ｅｐ ｉｄｅｍｉｃ洪泛的副本数量，其很多变体被提出来［３－ ４］；在社区模型下，ＰＲＯＰＨＥＴ［５］利用节点 间接触的历史信息预测未来的相遇概率指导路由； Ｎｅｔｗｏｒｋ ｃｏｄｉｎｇ［６］和Ｅｒａｓｕｒｅ ｃｏｄｉｎｇ［７］ 通过编码的 方式应对报文丢失；此外，还有基于模型［８］ 、控制节点运动［ ９］ 等方法应对各种各样的容迟网络环境．作者针对社区模型的特点，通过对节点历史运动轨迹点聚类，建立热点活动区域，进而建立社区辅助路由．在源节点社区中洪泛消息使其在产生之初迅速传播开，同样在目的节点社区中通过洪泛的方式迅速路由消息到目的节点．同时，利用节点活动的热点区域准确地选择中继节点降低消息冗余，节省网络资源．
1.1机会网路典型路由算法研究 机会网络是一种节点分布稀疏、网络拓扑结构不断发生变化的间歇性通信网络。数据以多跳方式，采用“接收-携带-转发”的机制传输给目的节点，如果中间节点没有合适的可供传输的路径或节点，则无法立刻将数据转发出去，而是保存在节点缓存中，等到出现合适的传输机会之后，再将消息转发出去。而现有的有线网络和无线自组织网络中基于TCP/IP 协议的端到端路由协议已经不再适用于机会网络。因此，如何在机会网络中寻找一条时延尽可能低、消耗尽可能小、传输成功率尽可能高的路径，将消息准确传递到目的节点，是机会网络中一个极具挑战性的问题。从不同角度出发，机会网络的路由策略有不同的分类方式[27]。按照消息传输方式可分为洪泛路由策略和转发路由策略；按照路由所使用报文的份数可分为单报文路由策略和多报文路由策略；按照节点所掌握的网络拓扑信息还可分为确定性路由策略和随机性路由策略。本文按照消息传输方式不同将目前的路由协议分为如下几类：直接传输路由策略(Direct Transmission)、基于泛洪的路由策略(Flooding Based)、基于情景感知的路由策略(Context Based)、基于社区的路由策略(Community Based)、基于编码的路由策略(Coding Based)、基于预测的路由策略(Predicted Based)。 1.1.1基于副本或泛洪的路由策略 直接传输(Direct Transmission，DT)路由在运行过程中，不产生消息副本，消息一直保存在源节点缓存中，直到源节点在运动过程中遇到目的节点，才将消息转发给目的节点。DT 路由协议由于没有进行路由优化处理，也没有产生任何副本消息，因此传输时延很大。为了减少网络中消息的传输时延，研究人员提出了基于泛洪的路由协议，通过消息携带节点产生大量的消息副本，转发给每一个相遇的节点，完成消息的投递。根据网络中消息副本数量的多少，还可以将基于泛洪的路由分为两大系列：泛洪路由和限制性泛洪路由。 最简单的泛洪路由为传染病路由或称为流行性路由(Epidemic Routing)[13]。顾名思义，传染病路由中消息的分发类似于传染病病毒散发，当消息携带节点在移动过程中碰到没有携带该消息的节点时，便产生消息副本并传递给对方，然后该节点将消息存储在自身缓存中，继续转发给所遇到的其他节点，直到消息传递到目的节点或者消息的TTL 等于零。 实际的网络中，节点的缓存和能量都有限，不可能保证足够的带宽资源，Epidemic 路由的性能将急剧下降，另外大量的冗余信息将过多地消耗节点能量，
容迟网络的体系结构及关键技术 樊秀梅? xmfan@ （北京理工大学计算机科学技术学院，北京，100081） 摘要：当前的Internet体系结构和其中许多协议无法很好的适用存在高延迟路径和频繁分裂的网络。当端节点具有严格的能量和存储限制时，问题将更加恶化。由于移动性和特殊应用缺乏“常常连接”的基础结构，像陆地移动网络、军事无线自组织网络、星际网络及传感器网络这样的网络有它们自己的专有协议而不采用IP协议。为了实现这些网络之间的互联，研究者们提出了在端到端连接和节点资源都受限时的一种网络体系结构和应用接口，称为延迟容忍网络（简称容迟网络，DTN）。DTN作为网络互联时传输层上的覆盖网可用来满足随意的异步信息可靠转发。本文综述和分析了容迟网络的应用背景、体系结构、关键技术和开放研究问题，并给出了未来的发展方向和应用前景。 关键词：容迟网络、高延迟路径、频繁网络分裂、覆盖网络 中图分类号: TP393 文献标识码: A 文章编号: State-of-the-Art Architecture and Techniques for Delay-Tolerant Networks Fan Xiumei （School of computer science and technology, Beijing Institute of Technology, Beijing,100081） xmfan@ Abstract: The successful architecture and supporting protocols of today’s Internet operate poorly when faced with operating environments characterized by very long delay paths and frequent network partitions. These problems are exacerbated by end-nodes that have severe power or memory constraints. Because of lacking “always-on” infrastructure in mobile and extreme environments, many such networks have their own specialized protocols, and do not utilize IP. To achieve interoperability between them, researchers have proposed a network architecture and application interface structured around optionally and reliable asynchronous message forwarding, with limited expectations of end-to-end connectivity and node resources. This architecture is called Delay-Tolerant Networks (DTN). It operates as an overlay network above the transport layer. In this paper, we discuss state-of-the-art architecture and key techniques for DTN and potential issues. It is our purpose to stimulate more research in this new emerging network. Key words: Delay-Tolerant Networks, high delay path, frequently network disconnection, overlay network. 1 引言 TCP/IP提供了一种基于不同链路层技术的端到端通信机制，已成为不同网络互联的基础。通常来说，TCP/IP协议簇的平稳运行依赖如下物理链路特性假定：①在数据源和目的地之间存在端到端的路径；②在网络中任何节点对之间的最大往返时间（RTT）不能太长；③端到端的分组丢失率较小。不幸的是，现在有一类越来越重要的所谓“受限网络（Challenged network）[1]”，它可能违反了上述假定中的一个或多个，这使得当前的TCP/IP模型不能很好地为其提供服务。 “受限网络”最初是由于主机和路由器的移动而出现的，也可能是由于能量管理或冲突导致的网络断 ?本文受到国家自然科学基金（No. 90604012）与北京理工大学基础研究基金（No. BIT-UBF-200501F4209）资助。樊秀梅，博士，副教授。研究领域为计算机网络传输控制、无线网络、网络性能评价。
路由算法是路由协议必须高效地提供其功能，尽量减少软件和应用的开销。 路由器使用路由算法来找到到达目的地的最佳路由。 关于路由器如何收集网络的结构信息以及对之进行分析来确定最佳路由，有两种主要的路由算法：总体式路由算法和分散式路由算法。采用分散式路由算法时，每个路由器只有与它直接相连的路由器的信息——而没有网络中的每个路由器的信息。这些算法也被称为DV（距离向量）算法。采用总体式路由算法时，每个路由器都拥有网络中所有其他路由器的全部信息以及网络的流量状态。这些算法也被称为LS（链路状态）算法。 收敛是在最佳路径的判断上所有路由器达到一致的过程。当某个网络事件引起路由可用或不可用时，路由器就发出更新信息。路由更新信息遍及整个网络，引发重新计算最佳路径，最终达到所有路由器一致公认的最佳路径。收敛慢的路由算法会造成路径循环或网络中断。 路由算法的核心是路由选择算法，设计路由算法时要考虑的技术要素有： 1、选择最短路由还是最佳路由； 2、通信子网是采用虚电路操作方式还是采用数据报的操作方式； 3、采用分布式路由算法还是采用集中式路由算法； 4、考虑关于网络拓扑、流量和延迟等网络信息的来源； 5、确定采用静态路由还是动态路由。 各路由算法的区别点包括：静态与动态、单路径与多路径、平坦与分层、主机智能与路由器智能、域内与域间、链接状态与距离向量。 链接状态算法（也叫做短路径优先算法）把路由信息散布到网络的每个节点，不过每个路由器只发送路由表中描述其自己链接状态的部分。 距离向量算法（也叫做 Bellman-Ford算法）中每个路由器发送路由表的全部或部分，但只发给其邻居。 也就是说，链接状态算法到处发送较少的更新信息，而距离向量算法只向相邻的路由器发送较多的更新信息。 metric是路由算法用以确定到达目的地的最佳路径的计量标准，如路径长度。
容迟网络中路由算法 摘要：容迟网络的主要目标是支持具有链路间歇性连通、时延大、错误率高等通信特征的不同网络的互联和互操作；由于节点移动性、链路间歇连通、网络频繁割裂等特点，容迟网络中的源节点和目的节点之间在多数情景下不存在一条连通路径，因此节点采用“存储携带转发”的路由模式。数据转发算法是移动容迟网络研究的一个重要方面。相比传统无线传感器网络的路由算法，移动容迟网络的数据转发算法不仅要提高网络节点的能量效率、延长网络生存期，对如何提高消息传输成功率、降低消息传输时延与通信开销的研究则更加具有实际意义。现有的移动容迟网络数据转发算法大致可分为：基于消息复制的转发算法、基于历史信息的转发算法、基于先验知识的转发算法、基础设施辅助的转发算法和基于社会网络的转发算法。 关键词容迟网络；社会网络；路由协议；数据分发；优化算法 容迟网络（Delay Tolerant Networks,DTNs）是近年来无线网络领域内的一个研究热点，泛指部署在极端环境下由于节点的移动或者能量调度等原因而导致节点间只能间歇性进行通倍甚至长时间处于中断状态的一类网络[1-3]。其概念起源于星际网络（Interplanetary Internet,IPN），与传统通信网络模型相比，移动容迟网络具有网络间歇性连通、节点资源受限、传播时延高等特点。DTN作为未来互联网络发展的一个新方向，在环境监测、交通管理、水下探测和发展中国家偏远地区网络基础建设具有广泛的应用前景和实用价值。 如何做出正确高效的路由选择一直是无线网络领域内的关键技术和主要研究课题，然而传统的基于的路由协议、移动网络和无线传感网络的路由协议均很难在容迟网络中工作。一方面，与传统通信网络模型不同，移动容迟网络中不存在稳定可靠的端到端链路，使得现有的基于端到端连通性假设的无线传感器网络路由算法不能适用于该网络环境。另一方面，相对于传统的无线传感器网络路算法，移动容迟网络数据转发算法不仅需要综合考虑如何提高网络节点的能量效率、延长网络生存期，研究如何提高消息传输成功率、降低消息传输延迟与通信开销则具有更加实际的意义。目前，移动容迟网络的数据转发算法大致可分为以下几种方式：基于消息复制的转发算法、基于历史信息的转发算法、基于先验知识的转发算法、基础设施辅助的转发算法和基于社会网络的转发算法。 1容迟网络概述 1.1 容迟网络起源 上世纪九十年代，美国国家航空航天局(National Aeronautics and Space Administration, NASA)等研究机构在美国国防部高级研究计划署(Defense
计算机网络实验报告
距离矢量路由算法 一，实验内容： A D 设计一个算法，实现上面拓扑图的各个结点之间路由表的交换，要求显示出结点路由表的交换过程并显示每次交换结束后的各个结点保存的路由表的内容。最后显示交换了几次后各个结点路由表开始变得稳定。 二，算法设计： 首先创建一个类。它有两个成员变量。一个是二维数组型的x[i][j]用来存放从加点i到结点j的距离，一个是一位数组型的y[i]用来存放从源结点到目标结点i的路径上的第一个途经的结点。然后为每一个结点实例化一个对象用来存放此节点的路由表。初始化各个节点的路由表，如果两个节点之间有连线则将其之间的距离赋给x[i][j],y[j]=j.如果没有直接路径则设 x[i][j]=1000,y[j]=0.算法开始的时候各个结点交换路由表。比较如果有类似x[i][j]和x[j][k]的项则设置 x[i][k]=MIN(x[i][k],x[i][j]+x[j][k]),为了在结点A的邻居节点执行距离矢量路由更新时，它使用的是A的旧表，可以再设置两个二
维数组用来暂时存放各个节点的新路由表，待各个节点一次交换都完毕后在把暂存的新节点依次赋给各个节点的路由表。各个节点都执行此操作，为了确定供交换了几次可以设置一个标质量k.初始k=0，交换一次K就加一，最后k的值便是交换的次数。 三，遇到的问题及解决方案： 刚开始遇到这个题目是觉得无从下手，觉得这个图这么复杂函数循环又没有规律怎样让各个节点依次交换呢，又怎样判断什么时候各个节点的路由表变稳定呢？着一些列的问题使自己变得很烦躁。待到心情平静下来认真的一点一点推敲的时候发现只有七个节点，为每个节点设置一个交换函数也不麻烦而且这样思路便变得非常的清楚，至于怎样知道何时路由表稳定则我在每个结点函数中设置了一个标志量，在主函数中将其初始化为零，在下面的结点函数中都将其变成1，这样只有调用子函数这个标志量便会变成1，检测标质量是否为1来判断路由表是否变的稳定。 四，源代码 package wangluo; class Jiedian { int y[]=new int[8]; //存放路径上的下一个节点 int x[][]=new int[8][8]; //存放节点间的距离 } public class Luyou { public static void main(String[] args) { Jiedian a=new Jiedian();
基于地理位置的路由协议：GEAR与GPSR协议对比 2011-06-16 14:19 现有的路由协议分为：能量感知路由协议、以数据为中心的路由协议、基于地理位置的路由协议、可靠的路由协议和层次路由协议五类。 地理位置路由假设节点知道自身及目标区域的位置，以这些位置信息作为路由选择的依据，按照一定策略转发数据到目标区域。 位置和能量感知的地理路由（geographical and energy aware routing，GEAR）：能量感知的基于位置的地理路由协议，与传统非能量感知的地理路由相比，GEAR 路由能极大地延长网络寿命。 由于Sink发出的查询消息中经常包含位置属性，GEAR路由协议在向目标区域散布查询消息的同时考虑了地理位置信息的使用。其主要思想是通过利用位置信息使得“兴趣”的传播仅到达目标区域，而不是传播到整个网络，从而避免洪泛方式，减少路由建立的开销。 GEAR路由中查询消息的传播包括2个阶段：（1）查询消息转发到目标区域：从Sink节点开始的路径建立过程采用贪婪算法，节点在邻居中选择到目标区域代价最小的节点作为下一跳节点，并将自己的路由代价设为该下一跳节点的路由代价加上到该节点一跳通信的代价。若陷入路由洞，节点则选取邻居中代价最小的节点作为下一跳节点，并修改自己的路由代价；（2）在目标区域内散布查询消息：查询消息到达目标区域后，通过迭代地理（节点密度较大时）或洪泛方式（节点较少时）将查询消息传播到目标区域内的所有节点。这2个阶段完成后，监测数据沿查询消息的反向路径向Sink节点传送。 GPSR(贪婪周边无状态路由协议) 贪婪周边无状态路由( Greedy Perimeter Stateless Routing,GPSR)是一种基于传统贪婪转发方案的路由协议。为了避免传统贪婪转发方案中通信空洞造成的路由寻径失败，以及由此产生的重复路由请求带来的额外开销，GPSR利用传感节点对位置信息的可知性和节点处于静态的特点，在路由过程遭遇通信空洞而失效时根据网络原始拓扑，生成一个平面子图并沿子图中空洞的周界进行分组转发。同时GPSR算法还利用该机制来支持传感节点的移动性。GPSR协议建立在传统贪婪转发算法之上，具有贪婪转发和周界转发两种分组转发方式。路由开始时采用贪婪转发方式进行分组转发，当贪婪方式失效时（即遇到通信空洞时）转入周界转发模式继续路由，当条件满足时恢复贪婪转发模式，如此反复直至分组到达目的地。 GEAR（geographical and energy aware routing，位置和能量感知的地理路由）协议是一个基于贪婪转发与节点能耗均衡性相结合方案的路由协议，在选择邻节点进行下一跳转发的同时，把各直接邻节点的能量信息结合起来考虑，选择综合开销最小的邻节点进行分组转发。基于贪婪转发与节点能耗均衡性相结合方案的路由算法中，综合开销最小邻节点的选择至关重要。GEAR根据邻节点通往目的
思东张宏科 Rip协议的工作原理及仿真分析--中国空间技术研究院西安分院李园利王宇二 三距离向量路由算法(Bellman-Ford Routing Algorithm)，也叫做最大流量演算法(Ford-Fulkerson Algorithm)，其被距离向量协议作为一个算法，如RIP, BGP, ISO IDRP, NOVELL IPX。使用这个算法的路由器必须掌握这个距离表(它是一个一维排列-“一个向量”)，它告诉在网络中每个节点的最远和最近距离。在距离表中的这个信息是根据临近接点信息的改变而时时更新的。表中数据的量和在网络中的所有的接点(除了它自己本身)是等同的。这个表中的列代表直接和它相连的邻居，行代表在网络中的所有目的地。每个数据包括传送数据包到每个在网上的目的地的路径和距离/或时间在那个路径上来传输(我们叫这个为“成本”)。这个在那个算法中的度量公式是跳跃的次数，等待时间，流出数据包的数量，等等。 在距离向量路由算法中，相邻路由器之间周期性地相互交换各自的路由表备份。当网络拓扑结构发生变化时，路由器之间也将及时地相互通知有关变更信息。
相邻路由器B发送请求报文，路由器B的RIP收到请求报文后，响应请求，回发包含本地路由表信息的响应报文。路由器A的RIP收到响应报文后，修改本地路由表的信息，同时以触发修改的形式向相邻路由器B广播本地路由修改信息。路由器B收到触发修改报文后，又向其各自的相邻路由器发送触发修改报文。在一连串触发修改广播后，各路由器的路由都得到修改并保持最新信息。同时，RIP每30秒向相邻路由器广播本地路由表，各相邻路由器的RIP在收到路由报文后，对本地路由进行的维护，在众多路由中选择一条最佳路由并向各自的相邻网广播路由修改信息，使路由达到全局的有效。运行RIP协议的路由器并不是把每一条新的路由信息都添加到自己的路由表中。而是根据Bellman-ford算法的最佳度量的计算公式获得D(i,j)，并根据D(i,j)的结果，更新路由条目： （1）如果路由条目是新的，则接受路由器将把该条目加入路由表中； （2）如果此路由已存在于路由表，但新的路由条目具有不同的来源，并且该条目具有更低的跳数，则路由表将用新的条目替换已存在的条目； （3）如果此路由已存在于路由表中，并且两个条目的来源相同，则路由表将用新的条目替换已存在的条目，尽管两者的度量值一样。 五稳定性---RIP 协议每30秒向相邻路由器发送一次路由更新信息，同时监听来自网络中的其它相邻路由器的路由信息，从而实现对本地路由表的动态维护，以确保IP层发送报文时选择正确的路由。 在实际系统中，我们可以将无穷大设置为网络的最大跳数加1。但是当采用时延作为距离的长度时，将很难定义一个合适的时延上界。该时延的上界应足够大，以避免将长时延的路径认为是故障的链路 六公平性---它对好消息的反应迅速，但对坏消息却反应迟钝 1)、协议中规定，一条有效的路由信息的度量（metric）不能超过15，这就使得该协议不能应用于很大型的网络，应该说正是由于设计者考虑到该协议只适合于小型网络所以才进行了这一限制。对于metric为16的目标网络来说，即认为其不可到达。 2)、该路由协议应用到实际中时，很容易出现“计数到无穷大”的现象，这使得路由收敛很慢，在网络拓扑结构变化以后需要很长时间路由信息才能稳定下来。 3)、该协议以跳数，即报文经过的路由器个数为衡量标准，并以此来选择路由，这一措施欠合理性，因为没有考虑网络延时、可靠性、线路负荷等因素对传输质量和速度的影响。
武汉工程大学计算机科学与工程学院 《计算机网络》实验报告
实验内容 实验目的 1、进一步理解路由器的主要组成部分及其功能，初步掌握IOS的一些基本命令，学习对路由器进行安全设置和基本的日常维护。 2、理解利用路由器IP包进行路由的基本原理及方法，初步掌握相关的一些IOS命令，学习对路由器的路由表进行查看。 实验要求 1、按照上述实验步骤进行正确的配置后，可以观察到运用TFTP服务器进行IOS备份的过程，可以在一台路由器的控制台上对远程登录的路由器进行配置的查看和修改，另外，还可以对各种口令设置的有效性进行考证。 2、按照上述实验步骤进行正确的配置后，可以用“ping”命令进行网络的连通测试，可以看到：无论是采用静态路由方式，还是采用动态路由方式，都可以达到连通网络的目的。 实验内容 1、学习检查路由器的主要参数和进行一些基本的设置； 2、学会对路由器进行各种口令的设置； 3、掌握路由器一些关键文件的备份。 4、静态路由的配置； 5、ＲＩＰ协议的配置； 6、ＩＧＲＰ协议的配置 实验设备 三台Cisco 25XX路由器和一台PC。 实验原理图 图 1-1 实验原理图1
图 1-1 实验原理图2 实验步骤 一、路由器的基本配置 1、将路由器与终端相连，加电启动路由器，进入命令行配置方式； 2、在“用户模式”下输入“Enable”进入“特权模式”，在“特权模式”下输入“conf t”进入“全局配置”模式； 3、用“hostname”命令为路由器命名； 4、用“int e0”、“int s0”、“int to0”命令进入路由器的某个端口的配置状态，这时可为路由器的该端口指定进行一些参数（如：IP地址、速率等）的设置； 5、按“ctrl+z”回到“特权模式”下，用“sh ver”、“sh running”、“sh start”和“show int”命令分别查看路由器的IOS版本、配置和端口状态； 6、练习“ctrl+A”、“ctrl+E”、“ctrl+B”、“ctrl+P”等组合键的使用； 7、学习如何进行“端口配置模式”、“全局配置”、“特权模式”和“用户模式”之间的转换，学习不同状态下帮助的获得； 8、练习进行各种命令的配置，包括：“console password”、“telnet password”、“auxiliary passwod”、“enable password”、“secret password”等； 1、router(config)#enable password cisco 命令解释：开启特权密码保护。 2、router(config)#enable secret class 命令解释：开启特权密匙保护。 这两个密码是用来限制非授权用户进入特权模式。因为特权密码是未加密
竭诚为您提供优质文档/双击可除 qos路由协议 篇一：详解路由器qos流量控制管理与设置方法 详解路由器qos流量控制管理与设置方法 现在越来越多的路由器都带上了qos的这个功能。作为网络管理人员。qos这个词已经越来越多的出现在我们的耳边。究竟什么是qos流量控制？今天我们来学习一下。 简单的来说。qos用来解决带宽解决网络延迟和阻塞等问题的一种技术，一般里面包含优先级别（小包优先、ip/网段优先、端口优先、剩余带宽抢占优先级）、弹性带宽管理等等。 小包优先：小包通常指小于64k的包，如：ping包。请求包、响应包等。在上网过程中。会出现很多请求，响应。这些包优先后，给我们的感觉就会快很多。 ip/网段优先：可针对源ip、目的ip。或者段来设置优先级别。比如。局域网中。我首先保证我的web服务器的带宽。再保证客户机的带宽，再保证服务器的带宽。都可以进行设置。 端口优先：可针对源端口、目的端口进行设置优先的级
别。一般来说。网吧都是玩游戏为主。那么我可以针对一些主流游戏的端口。优先这些游戏的带宽。 剩余带宽抢占优先级：顾名思义指在使用中。当网络的带宽有剩余的时候。剩余的这些带宽可以分配给某些ip，某些端口。这样，可以让你充分的使用带宽。而不浪费！ 弹性带宽管理： 以下载限速为例，比如总带宽为10mbit(总最大下载速度为1000kbytes/s)。共20人使用，限速为保证下载速度100kbytes/s，最大下载速度200kbytes/s。详细阐述如下： 1、带宽空闲时,速度可达到“最大速度” 如果带宽有空闲（上网的人比较少，带宽使用率在50%左右，比如只有10人在线），则下载速度最大可以达到200k，200k是下载的峰值速度，即使带宽只有一个人在使用，也不会超过这个峰值速度。这200k里面的100k是暂时借用他人的，当别人需要时，将会自动退让出来。 2、带宽有一定的使用率，速度在“保证速度”和“最大速度”之间 如果带宽有一定的使用率（有一定的上网人数，带宽使用率在80%左右，比如有15人在线），则下载速度会降低到“保证下载速度”和“最大下载速度”之间，即100k~200k。通常，这种情况占多数。 3、带宽使用率较高或全部使用，速度等于或小于“保
1无线自组织网络路由算法研究 摘要：移动Ad Hoc网络是一种特殊的无线移动网络，其路由设计问题是无线移动网络领域的热点问题。随着制造工艺和设备性能的不断进步以及基础理论研究的不断深入，移动Ad Hoc网络开始从军用进入商用和民用领域，如会议数据分发、数字化农业、保健医疗、智能公路等。因此如何进一步提高路由协议的性能是当前急需解决的重要问题。本文从自组织网络常用路由协议出发，简要介绍表驱动路由协议CGSR、WRP、DSDV，以及按需路由协议AODV、DSR，其中以DSDV、AODV、DSR为本文重点内容，介绍其路由算法，分析比较表驱动路由协议以及按需路由协议的性能。本文也简要介绍了AODV路由节点中断时如何应对的改进办法--本地修复。另外，本文也将Ad Hoc多播路由协议作为研究对象，综述多播路由协议面临问题及其主要协议，但不涉及具体算法。 关键词：Ad Hoc；DSDV；DSR；AODV；多播路由协议 Routing for ad-hoc wireless networks Liu Shuang (Class 001111，Student No. 00111127) Abstract:Mobile Ad Hoc networks are a special kind of wireless mobile networks, its routing design problem is a hot issue in the field of wireless mobile networks. With the deepening of the manufacturing process and equipment performance and progress of basic research, starting with mobile Ad Hoc networks into commercial and military civilian areas, such as meeting data distribution, digital agriculture, health care, smart highways. So how to further improve the performance of the routing protocol is an important current problems need to be resolved. In this paper, self-organizing network routing protocols commonly used starting brief table-driven routing protocols CGSR, WRP, DSDV, as well as on-demand routing protocols AODV, DSR, which DSDV, AODV, DSR key content for this article introduces its routing algorithm, analysis and comparison table performance-driven routing protocols and on-demand routing protocols. This article also briefly describes ways to improve how to deal with the AODV routing node is interrupted - local repair. In addition, the paper will also Ad Hoc multicast routing protocol for the study, summarized the problems faced by the multicast routing protocol and its main agreement, but does not involve a specific algorithm. Key words:Ad Hoc；DSDV；DSR；AODV；Multicast Routing Protocol 1 引言 无线自组织网络是一种没有固定基础设施的移动通信网络。也正因为没有固定基础设施的限制，无线自组织网络具有很大的灵活性，不受有线网络的限制，适合军事通信以及发生自然灾害现场有线通信设施已经被破坏的情况，具有广阔的发展前景。本文基于无线自组网络背景，立足于其特殊性，比较当前几种已经存在的路由协议，分析其优缺点，给出结论。 2 Ad Hoc网络特点 无线自组网是一种无线多跳通信网络，无固定基础设施，具有移动、自治的特点，可以在不能利用或不便利用现有通信设施的情况下，建立起通信支撑环境，拓宽了移动通信应用场合，其主要特征如下[2]： ⑴独立组网：即网络的组织无需依赖于任何规划和先验信息。节点开机后可以迅速、独立的组成一个网络。 ⑵多跳路由：由于单一节点发射功率以及覆盖范围的限制，当需要通信节点超出当前节点覆盖范围时，需要其它节点的转发，即要进行多跳路由。 ⑶动态拓扑结构：由于其移动性，使得网络内节