【经典的泛洪优化算法原理介绍概述2100字】

经典的泛洪优化算法原理介绍概述在第一章中提到，为了优化移动自组织网络，减少网络中的冗余数据包，可以将解决方式拆解为四类基本的优化方式，分别是基于计数器、基于概率、基于区域、基于邻居信息的优化方式，其他的方式可以视为四种基本方式组合。本小节将对以上四种经典的泛洪优化算法的原理进行介绍。1.1基于计数器的优化方式基于计数器优化方式假设节点在接收到同一条消息的多个副本后，自身的转发将不会对网络产生额外增益，因此副本数量达到一定门限后，取消转发。基于计数器的广播算法中提出了随机转发延迟RRD的概念ADDINNE.Ref.{FD5F84C6-AFF9-4B66-B336-B54F976E7878}[12]，即在随机时间t∈[0,Tmax]内转发数据，在第一次接收到数据之后设置一个冗余计数器，当接收到重复数据之后，冗余计数器的值+1，随机转发延迟定时器到期后，如果冗余计数器的值小于某个数，执行转发操作，如果大于某个数，则不进行转发。由于考虑到冗余数据的处理，基于计数器的优化算法极大的抑制了冗余数据的转发。后来应用在在RPL(RoutingProtocolforLowPowerandLossyNetworks

)中的一系列Tickle类算法ADDINNE.Ref.{CECFFE2E-B87A-4C7F-81FD-4489BC056C65}[14,32]本质上是一种基于计数器算法的变体，Drizzle算法ADDINNE.Ref.{54C48A57-C9EE-42ED-BC09-913E7DED2D32}[33]是其中的Tickle算法一个变体，Trickle算法基于随机计时器和窗口加倍机制来平衡流量负载和响应时间。定义了三个参数，一是冗余常数k，也就是监听到的冗余数据量，第二个参数是最小间隔长度Tmin，第三个参数是最大间隔长度Tmax，冗余常数k是在间隔长度时间内监听到的冗余数据量，一旦k超过每个数值，则放弃对数据包的转发，对计数器的改进主要体现在时间间隔的改进上，普通的基于计数器的方案采用的方案一般采用固定等待时间或者固定上下限的随机等待时间。1.2基于概率的优化方式基于概率的优化方式是指节点以一定的概率广播，从而减少一次通信过程中产生的冗余数据包。最经典的概率广播方式是固定概率广播，以固定的概率在网络中进行广播，其基本的步骤是接收到数据包p1然后检查节点缓存中是否有p1的副本，如果有，则丢弃p1结束流程，如果不存在p1的副本，则先将p1保存在本地缓存中，然后生成一个小于1的随机数x，与预定转发概率Pt比较，如果随机数x小于Pt,则对p1进行转发，否则放弃转发，终止流程。典型的有Gossip类算法ADDINNE.Ref.{713A8189-F6AC-4C2D-9B03-DAFD6C3D890C}[16]。Gossip算法大多采用固定概率转发，对整个网络设置一个固定的概率值转发。也有采用自适应概率广播方式，但实际自适应概率广播方式一般都是和其他广播方式结合的结果，例如动态概率计数器广播算法(DBCPS)ADDINNE.Ref.{E84BAD62-47F9-4878-A207-57830AD0C347}[15]，在DBCPS算法中，结合了概率方案和基于计数器方案的特点，使用依赖于计数器的概率函数，动态的给定节点的转发概率，设置最大随机转发延迟为Tmax，如果在随机转发延迟内计数器的值达到某个阈值，则以较低概率转发，否则以高概率转发，两个转发概率的计算使用公式2-1给定的指数函数确定。fc其中c表示计数器当前值，C表示计数器阈值。概率广播的优点在于可以有效减少冗余数据数量，在密集网络中只需要很小的概率即可实现较高的投递率，但是主要问题也是投递率的问题，因为一个网络也有可能是稀疏的，也有可能是分布不均匀的，在网络中容易出现双峰现象,即几乎全部可达或者几乎全部不可达，这在文献中有详细的讨论。也有部分学者采用前k跳以概率1转发，以此抑制双峰现象。1.3基于区域的优化方式基于区域的优化方式的原理是从节点的几何关系上推导出最佳拓扑，对网络进行提前配置，在保证连通性的前提下来实现最少的冗余ADDINNE.Ref.{7338CE3B-4D97-49E3-BBE2-132AC8D0FE3F}[18,19]。对于蓝牙Mesh网络，可以视为一个有向图G(V,E),其中V代表顶点集，也就是蓝牙Mesh网络中的节点集，E表示有向图的边，如果蓝牙Mesh网络中一个节点的无线电范围可以覆盖另一个节点，则这种覆盖关系就代表着有向图E中的一个边。求解最佳拓扑的问题等价于求该有向图的最小连通支配集MCDS问题ADDINNE.Ref.{ADB5D04A-3556-4B93-9AB7-45674B616AD3}[34]基于区域方式的优点是节点知晓自身位置信息和目标节点位置信息，因此可以更好的规划自身是否转发，实现很好的冗余数据抑制效果。但是主要的问题是需要知道每个节点的具体位置，来得到当前网络的有向图，位置信息的获取需要额外的辅助设备，但在一般的网络中，不会配备GPS等辅助定位设备，定位精度也有问题。存在的另一个问题是需要把位置信息封装到数据包中，难以应用在蓝牙Mesh网络中。1.4基于邻居信息的优化方式在对泛洪算法的优化中，邻居信息对节点的转发决策至关重要，适当地使用邻居信息可以有效的抑制冗余数据。在网络中可选择的信息包括邻居信息的距离、数量、节点密度、电量等。其中自裁剪方案ADDINNE.Ref.{AE537E18-907C-4276-ACD7-CDAA776E51B5}[35]就是基于邻居信息的优化方案中的一个代表,自裁剪方案的基本原理是根据邻居节点信息，对转发节点进行裁剪，减少参与转发的节点数量。图2-8展示了自裁减算法的基本原理。如图所示，节点u转发分组，节点v接收该分组。节点u在数据包中携带其邻居列表N(u)。收到来自u的数据包后，节点v检查该集合Uu,v图2-8自裁剪算法基于邻居信息广播方式的优点是无需掌握整个网络的拓扑，只需