典型路由协议.ppt

WSN典型的路由协议分析,目录1、泛洪路由(Flooding)2、Gossiping路由协议3、SPIN协议4、DD定向扩散路由协议5、Rumor路由协议6、GPSR路由协议7、LEACH路由协议,什么是路由协议,路由协议是WSN的关键技术之一，它负责将数据分组从源节点通过网络转发到目的节点。主要包括两个方面的功能：寻找源节点和目的节点的优化路径将数据分组沿着优化路径正确转发,1、泛洪路由(Flooding),一节点S希望发送一块数据给节点D，节点S首先通过网络将数据副本传送给它的每一个邻居节点，每一个邻居节点又将其传输给各自的每一个邻居节点，除了刚刚给它们发送数据副本的节点S外。如此继续下去，直到将数据传输到目标节点D为止或者为该数据所设定的生命期限（在传感器网络里面通常定义为最大跳数）变为零为止或者所有节点拥有此数据副本为止。,1、泛洪路由(Flooding),1、泛洪路由(Flooding),洪泛路由（Flooding）的优点：实现简单不需要为保持网络拓扑信息和实现复杂的路由发现算法而消耗计算资源适用于健壮性要求高的场合。,1、泛洪路由(Flooding),洪泛路由（Flooding）的不足：存在信息爆炸(Implosion)问题，即出现一个节点可能得到一个数据多个副本的现象出现部分重叠(Overlap)现象，如果处于同一观测环境的两个相邻同类传感器节点同时对一个事件作出反应，二者采集的数据性质相同，数值相近，那么，这两个节点的邻居节点将收到双份数据副本盲目使用资源，即扩散法不考虑各节点能量可用状况因而无法作出相应的自适应路由选择。,1、泛洪路由(Flooding),洪泛路由（Flooding）的应用情况：网络资源过于浪费，实际很少直接采用具有极好的健壮性，可用于军事应用作为衡量标准评价其它路由算法,2、Gossiping路由协议,Gossiping协议是对Flooding协议的改进,节点将产生或收到的数据随机转发给一个或者若干个相邻节点,避免了内爆,但增加了时延，且无法避免重叠问题。,3、SPIN协议,SPIN（sensorprotocolforinformationvianegotiation)a.为了避免出现扩散法的信息爆炸问题和部分重叠现象，传感器节点在传送数据之前彼此进行协商，协商制度可确保传输有用数据。,3、SPIN协议,b.节点间通过发送元数据，而不是采集的整个数据进行协商。c.在传输或接收数据之前，每个节点都必须检查各自可用的能量状况，如果处于低能量水平，必须中断一些操作。,3、SPIN协议,d.SPIN有3种数据包类型，即ADV、REQ和DATA.节点用ADV宣布有数据发送，用REQ请求希望接收数据，用DATA封装数据ADV：用于新数据广播。REQ：用于请求发送数据。DATA：包含附上元数据头(meta-dataheader)的传感器采集的数据的数据包SPIN-PP采用点到点的通信模式，并假定两节点间的通信不受其他节点的干扰，分组不会丢失，功率没有任何限制。,3、SPIN协议,3、SPIN协议,SPIN协议的优点：1、小ADV消息减轻了内爆问题;2、通过数据命名解决了交叠问题；3、节点根据自身资源和应用信息决定是否进行ADV通告，避免了资源利用盲目问题，有效地节约了能量。,2019/12/12,15,可编辑,3、SPIN协议,SPIN协议的不足：在传输新数据的过程中，直接向邻居节点广播ADV数据包，而没有考虑其所有邻居节点由于自身能量的原因，不愿承担起转发新数据的功能，则新数据无法传输，将会出现“数据盲点”，进而影响整个网络信息的收集。,4、DD定向扩散路由协议,在DirectedDiffusion中，可以对路径进行修复。在建立多条数据源到Sink节点的路径之后，Sink节点可以选择增强其中的一条路径用于数据的传输，而同时保持另外一条低速数据传输的路径。当高速路径，也就是经过增强的路径出现故障时，Sink节点可以增强低速路径，保证源节点到Sink节点的数据传输。,DD路由协议的优点,1、采用多路径,健壮性好;2、节点只需要和邻居节点通信，因而不需要全局的地址机制，使用查询驱动机制按需建立路由,避免了保存全网信息；3、每个节点都可以进行数据融合操作，能减少数据通信量，节省能量消耗；4、sink点根据实际情况采取增强或减弱方式能有效利用能量；5、节点不需要维护网络的拓扑结构，数据的发送是基于需求的，因此它是一个非常节能的路由协议。,DD路由协议的缺点：,1、基于查询驱动模型的，不适用于环境监测的WSN；2、Gradient的建立开销很大,不适合多sink点网络；3、数据聚合过程采用时间同步技术,会带来较大开销和时延；4、不同的应用中需要定义不同的命名方案，也就是对，从而限制了它的应用。,5、Rumor路由协议（谣传路由）,RumorRouting是在DirectedDiffusion的基础上演化而来的。通常情况下，DirectedDiffusion协议需要向整个网络广播兴趣，而在某些应用中，只有少量的数据需要从源节点传递到Sink节点。在这种情况下，没有必要向整个网络广播兴趣。当WSN中的事件（对应着数据的传递）数量很少，而查询（对应着兴趣的广播）数量很多的时候，可以采用广播事件的方法，以节省能量的消耗。RumorRouting是一个介于事件广播（向整个网络广播事件）和兴趣广播（向整个网络广播兴趣）之间的一种路由协议在多sink点、查询请求数目很大、网络事件很少的情况下，Rumor协议较为有效。但如果事件非常多,维护事件表和收发Agent带来的开销会很大。,6、GPSR路由协议,GPSR(GreedyPerimeterStatelessRouting)GPSR协议核心思想：GPSR协议是一个典型的基于位置的路由协议。使用GPSR协议，网络节点都知道自身地理位置并被统一编址，各节点利用贪心算法尽量沿直线转发数据。产生或收到数据的节点向以欧氏距离计算最靠近目的节点的邻节点转发数据，但由于数据会到达没有比该节点更接近目的点的区域(称为空洞)，导致数据无法传输，当出现这种情况时，空洞周围的节点能够探测到，并利用右手法则沿空洞周围传输来解决此问题。,GPSR协议优点：,1、避免了在节点中建立、维护、存储路由表，只依赖直接邻节点进行路由选择，几乎是一个无状态的协议；2、使用接近于最短欧氏距离的路由，数据传输时延小;并能保证只要网络连通性不被破坏，一定能够发现可达路由。,GPSR协议的不足,1、当网络中sink点和源节点分别集中在两个区域时，由于通信量不平衡易导致部分节点失效，从而破坏网络连通性；2、需要GPS定位系统或其他定位方法协助计算节点位置信息。,7、LEACH路由协议,Low-EnergyAdaptiveClusteringHierarchy1、LEACH协议分为两个阶段操作，即类准备阶段(set-upphase)和就绪阶段(readyphase)。为了使能耗最小化，就绪阶段持续的时间比类准备阶段长。类准备阶段和就绪阶段所持续的时间总和称为一轮(round)2、在类准备阶段，LEACH协议随机选择一个传感器节点作为类头节点(clusterheadnode)，随机性确保类头与基站之间数据传输的高能耗成本均匀地分摊到所有传感器节点。,7、LEACH路由协议,3、具体的选择办法是：一个传感器节点随机选择0和1之间的一个值，如果选定的值小于某一个阈值T(n)，那么这个节点成为类头节点。T(n)值按右边公式计算N：网络中传感器节点的总数；p：一轮中网络的类头节点数；r：己完成的轮数；Gr：在剩余的N/k-r个回合中未成为类头节点的传感器节点组成的集合；,7、LEACH路由协议,4、在类头节点选定后，该类头节点对网络中所有节点进行广播，广播数据包含有该节点成为类头节点的信息。一旦传感器节点收到广播数据包，根据接收到的各个类头节点广播信号强度，该节点选择信号强度最大的类头节点加入，向其发送成为其成员的数据包。类形成后，类头节点采用TDMA策略分配通道使用权给类内节点。,7、LEACH路由协议,5、一旦处于就绪阶段，类头节点开始接收类内各节点采集的