首页> FAQ> 当前页

问:请问在DTN网络中基于洪泛的经典路由算法有哪些?

答:1)Epidemic路由算法     Vahdat等提出的著名的传染病路由算法[19]是基于洪泛的一个代表性路由协议。 算法利用节点移动性来增加节点间的连接能力,进行消息交换,最终将源节点产生的消息传输到目的节点,并通过增加束副本的份数来增大传输率。该算法模仿生物环境中传染性病毒的传播方式,每个被病毒传染的个体将把病毒传给与其接触的其他个体,用生物传染方式增大传输率。体现在DTN网络中,每个节点维护一个消息总结向量,该向量记录节点缓存中存储携带了哪些消息。当两个节点能够连接时通过交换消息向量来彼此交换缺少的消息。经过一段时间,网络中的每个节点将收到所有的消息。传染病路由算法本质上是基于洪泛策略的,每个节点存储所要转发的消息,优点是不需要额外的拓扑控制信息,同时可以取得高的消息投递率和低的端到端时延,无需对链路状态进行预测与估计,实施起来较为简单。缺点是网络中存在大量的冗余副本将导致节点能耗增加和缓存溢出,进而导致网络的资源利用率低和整体运行效能低下,该算法主要适用于缓存和带宽充足的场景。图2.2描绘了传染病路由算法的传递过程,圆点表示移动的节点,灰色区域表示节点的通信范围。 在图2.2(a)中,源节点S希望传递消息给节点D,但是两个节点之间不存在相连的通路。因此节点S将消息传递给它的两个邻居节点彳和8。一段时间后,如图2.2(b) 所示,节点B进入节点C的通信范围,将消息传递给C。而节点C又在目的节点D 的通信范围内,最终消息被传送到它的目的地。 传染病路由协议设计的目标是:①最大限度地提高消息传递率;②尽量减少信息延迟;③减少消息传递过程中总资源的消耗。因此,文献fl9]就相关Ad—Hoc网络的联通性做以下假设:①发送节点不在基站的通信范围内;②节点不知道目的地目前所在位置和最佳路由路径;③消息接收方也可以是一个漫无目的运动的无线主机;④通过节点移动,一对主机节点定期随机地进行通信。     每个节点维护一个缓冲区,存储该节点生成的消息和其他节点传递来的消息。为了提高效率,由哈希表索引消息列表,称为总结向量(summary vector),每个消息都由唯一的相关联的标识符锁定。当两个主机进入彼此的通信范围内,与较小的标识符的节点向具有较大标志符的节点发起反熵会话(anti—entropy session)比81。为了避免冗余连接,每个节点记录最近与它通信的节点。当两个节点能够连接(接触,表示具有l个通信机会)时,用交换的消息总结向量来确定本地缓存中所没有的消息,接下来发送所需消息列表的请求,从而完成消息交换。考虑到节点资源消耗,传染病协议采用长为32bit的标识符描述消息路由跳数,限定消息交换的最大次数。     图2.3描述了传染病路由协议的消息交换过程主要分为三步。节点A接触到节点B,启动一个反熵的会话。首先,A节点将其总结向量SVA传送到B,SvA记录节点4缓存的所有消息。然后,B执行集合SVA和SVB之间逻辑与(And)运算,即B节点测定4节点携带而B没有的消息,并向4节点请求发送这些消息。最后,爿节点发送所需消息给曰。当8接触到一个新的邻居节点时,重复上述过程。 卡内基梅隆大学的Monarch[29]项目对网络仿真器(Network Simulator)进行扩 展,在该平台上模拟传染病路由算法,从多方面评估路由效用,并探讨设计适宜的 空间和系统参数。在一些场景中现有的Ad—Hoc网络路由算法难以成功传递消息, 因为节点间有限的连通性导致网络中不存在一条端到端的路径。但仿真实验的研究 结果表明,在间歇性连接的网络场景中,传染病路由算法能够传递几乎所有的消息。另外,文献[19】还调查研究传染病路由在网络可用资源方面的灵敏度。在某个特殊 的场景中,假设节点的内存足够大能够存储网络中生成所有消息总数的10%~25%,那么传染病路由的数据传输率能达到l00%。因此,虽然传染病路由算法可以增加 网络资源消耗,但在某些情况下它可能是成功地传输应用程序数据唯一可行的方法。     2)Spray&Wait路由算法     基于效用的单副本的路由协议降低了资源的消耗,但带来了较大的延迟。在某 些DTN网络中,最小化延迟和最小化消息丢失率也是需要优先考虑的,文献[18] 提出了一种传输时延低、跳数少的有效限制副本数量的多副本路由协议(Spray& wait)算法,它由两个阶段组成:Spray阶段和wait阶段。Spray阶段实际上是一种 基于三个邻居的泛洪,源节点将需要传输的消息复制L份,并独立地转发给£个不 同的中继节点,如果在该阶段发现目的节点,则消息传输结束,若在该阶段没有发 现目的节点,则转入Wait阶段。在Wait阶段,携带消息副本的三个中继节点不再 转发消息,而是各自执行直接传输算法,等待与目的节点的相遇机会。     Spray&Wait路由算法结合了传染病路由(Epidemic)的迅速性和DD路由算法 的简约性的优点。它最初“起跳开始”传播消息副本的方法和传染病路由很相似。 当足够多的副本扩散到能够保证其中至少有一个副本会很快找到目的地的程度时, Spray阶段停止,并让每个承载副本的节点进行直接传输。换句话说,Spray&Wait 路由可以看作是单一副本路由和多副本复制路由方案之间的权衡策略。     根据在Spray&Wait路由算法最初的Spray阶段三个消息副本如何扩散的问题, 可以设计多种不同的“Sprayin9”启发式方法。最简单的方法是源节点向首先遇到 的三个不同的节点发送l份消息副本,这称为Source Spray&Wait算法。另一个更 好的方法是在Spray阶段,消息的源节点将L个初始消息副本中的一半分发给第一 个遇到的节点,然后当源节点或者中间节点有n>1个消息副本时,若遇到新的节点,则将一半(向上取整)的消息复制转发给该节点,本身保留余下的副本信息,当节点 只剩下一个副本信息时,则不再向其他中间节点传送副本,而是进行等待,对目的 节点执行直接传输,这称为Binary Spray&Wait算法。为了方便理解,图2.4和图 2.5分别描述了Binary Spray&Wait和Source Spray&Wait两种路由算法在Spray阶 段分发消息副本的方式,其中L=4。相比于Source Spray&Wait算法,只有源节点 承担三个消息副本的分发任务,Binary Spray&Wait算法中有更多的网络节点参与 到分发消息副本的过程,因此加快了三个消息副本在网络中传播的速度,体现在路由算法性能上可以明显地减少消息投递时延。可以证明,Binary Spray&Wait算法在节点的移动符合独立同分布(independent and identically distributed,IID)的情况下可以取得最优的消息期望投递,故适用于节点移动具有该特性的网络环境。随着三变大,Spray启发式的复杂程度对Spray&Wait路由协议消息延迟的影响也越来越大。图2.6表示在一个100×lOOm2面积、有l00个节点的网络中,Spray&Wait 路由算法和Binary Spray&Wait路由算法的预期时延与消息副本数量变化的函数关系。     Spray&Wait路由协议的另一个关键问题是如何选择消息副本的初始化数量三, 所需消息副本的数量三的值只与网络中节点的个数有关。具体公式如下,其中M是网络节点个数,口、提参数。 Spray&Wait路由算法的优点是在一定程度上减少了网络中传输的信息数量,   降低网络的负载,算法简单易实现;缺点是与传染病算法相比,Spray&Wait算法   加大了消息传输的平均时延。该算法适用于缓存和带宽较为充足,但是需要有效利   用这些资源的网络中。     3)Spray&Focus路由算法     如果节点限制在较小的移动范围内或者节点间的移动具有很强的关联性,那么   喷射等待路由协议的性能将会有所下降。为了克服这个问题,Spray&Focus路由协   议l20J基于文献[18]做了改进,该策略的Spray阶段和文献[18]中的对应阶段相同,其   不同之处在于第二阶段一ocus阶段,单份的副本信息集中在更优的中继节点中,   从而将信息传送到目的节点。     当节点缓存中只剩余一个消息副本时,中继节点转换到聚焦阶段(focus phase)。   与Spray&Wait算法不同的是,在等待阶段节点直接将消息传递给目的节点,而在   聚焦阶段按照给定的标准可以将消息转发给其他中继节点。转发决策是建立在一系   列计时器的基础上的,那些计时器记录两个节点最后相遇的时间。     为了使路由协议在稀疏网络中取得更好的表现,文献[201为单副本设计新的效   用函数。每个节点维护一个时间向量,记录该节点与网络中其他节点从最后相遇到   现在时刻的时间间隔,文献[20]N用时间变量定义了一个效用函数∽(,),表示一个   节点i给另一节点/传递信息的能力。只有当%(D)>uA(D) ‰时,节点4才将消   息传递给节点8,其中‰是效用值门限参数。     然而随着时间增加,时间效用值也变得不可靠,所以文献[20]又提出传递性的   定义。如果节点4经常遇见节点8,而节点8和节点C频繁相遇,即使彳与C几   乎不接触,但节点彳仍会是一个(通过B)向C投递消息很好的候选者。因此,当节 点A遇到节点8时,还应该增加A到那些与8频繁接触的节点的效用值。时间传递性函数能使远离目标的节点快速分散新鲜消息,因此减少一个给定节点因移动带来的位置的不稳定性。     定义2.1(时间传递性)  令节点么与节点B相遇,它们的距离为d4口。又令tm(d) 表示节点在给定模型中移动距离d的期望时间。那么对彳节点和B节点,有以下公式:     4)Prophet路由算法   文献[30]提出的Prophet(probabilistic routing protocol using history of encounters &transitivity)路由算法是基于历史预测策略的典型代表,与传染病路由算法盲目地向所有邻居节点复制消息不同,Prophet路由算法中的每个节点将会利用节点问相遇的历史信息和传递性来估计到达目的节点的概率,选择下一跳节点。该算法定义了一个称之为投递预测值(deliver probability)的指标来描述节点之间成功传输消息的概率。与传染病路由算法相比,每当两个节点彳和B相遇时,除了要交换向量,还需要交换投递预测值,只有当B到达目的节点的投递预测值大于彳时,彳才向8复制消息。Prophet路由算法是为了克服基于复制策略中消息复制的盲目性而提出的,通过消息历史传输的成功概率进行估算和比较,选择到达目的节点概率更高的中继节点。通过这种有选择性的复制消息,避免生成低效传输的消息副本,提高网络的资源利用率。     投递预测值P圳的计算包含三部分:更新、衰退、传递性。当两个节点相遇时,首先更新两节点的投递预测值。若两个节点相遇越频繁,那么他们彼此的投递预测值也越高。根据式(2.1)计算更新节点的投递预测值,其中圪。∈[0,1]表示初始常量。       如果在一段时间内一对节点没有遇到彼此,则表示他们不太可能会传递消息给对方,因此在这个过程中投递预测值按式(2.2)所示衰减,其中,,是衰减参数,k表示从最后一次相遇到当前时间所经历的时间块的个数。       此外,投递预测值也具有传递性,根据观察,如果节点彳经常遇到节点B,而节点8经常遇到节点C,那么对目的地为节点彳的消息而言,节点c可能是一个很好的中继节点。式(2.3)表示出这种传递性如何影响投递预测值日。1,其中∥∈[0,1] 是一个度量参数,它决定了传递性对投递预测值影响的比重。   在文献[30]的仿真实验中使用的是随机路点(RWP)移动模型和社区模型 (community model),RWP模型的节点随机移动没有规律;社区模型的每个子社区含有一个固定(非移动)节点。仿真结果表明,不论是在随机移动模型或是社区模型中,与Epidemic算法相比,Prophet算法具有更高的平均消息传输率和更低的通信负载,平均时延方面也表现较好。事实上,在随机路点移动模型中,即使节点随机移动,也存在以前互相接近的节点还没有远离对方的情景,而在实际场景中更是合理的、会发生的,因此传递率的可预测性有利于路由决策。     然而Prophet算法还存在许多有待改进的方面。在消息管理机制方面,Prophet 算法使用FIF0队列存储节点中的消息,所以每当一个新的消息到达已满节点时,队列中存储时间最长的消息会被丢弃。在这里可以使用一些其他更好的策略,例如丢弃被转发次数最大的信息。其次,为了减少所需的缓冲空间,并进一步提高性能,可以允许节点广播一个ACK给其他节点,通知其他节点删除已传递的消息。这将给其他消息留更多的资源,很可能增加那些被传递的消息的概率。   在文献[30]的仿真实验中使用的是随机路点(RWP)移动模型和社区模型