沈阳理工大学学士学位论文
4 Flooding路由协议的分析与研究
泛洪(Flooding)路由算法是一种经典的路由算法，由于其具有实现简单，容错能力强等特点，无论在有线网络中还是在无线网络中都得到了广泛的应用。由于实现简单，泛洪算法在传感器网络中也得到了广泛应用。但是泛洪算法能耗过大的缺点又在相当程度上抵消了其优势，使其不适合直接地应用于无线传感器网络。如果将泛洪作为一种路由算法应用于传感器网络，需要解决其能耗过大、数据冗余量高问题。如DD、SPIN、Gossiping等算法都是Flooding的改进算法。
4.1 泛洪算法模型
在泛洪算法中，任一节点ni接收到报文的动作可用如下伪代码描述。每个报文都包含TTL（报文存活时间）、DATA（数据）等内容。算法基本步骤如下： Step1：Sink和其他节点广播自己的位置信息和序列号； Step2：源节点广播报文；
Step3：若收到报文的节点为Sink则报文已传送到目的地；否则转Step4； Step4：若报文的TTL－1＝0或节点已收到过该报文，则转Step5，否则转Step6； Step5：节点丢弃该报文；
Step6：节点将报文转发给它所有的邻居节点。
报文中的TTL字段，通常用来防止报文在网络内被无限制的转发，在洪泛的工作模式下，网络中有节点要发送报文时，它将把报文发送给所有的邻居节点；而收到报文的节点则将报文转发给自己所有的邻居节点，除非TTL－1＝0或接收节点本身就是汇集点。其中TTL通常表示跳数或时间，当TTL－1＝0时，报文将被丢弃。传感器网络中基于自适应的路由算法研究。
27
沈阳理工大学学士学位论文
4.2 算法流程图
是否 是否 是否 开 始 Sink和其他节点广播自己的位置信息和序列号 源节点广播报文 收到报文的节点为Sink 将数据包交高层处理并失去对该数据包的转发权 报文的TTL－1＝0？ 丢弃该报文 节点已收到过该报文 丢弃该报文
图4.1 泛洪算法流程图
28
沈阳理工大学学士学位论文
4.3 基于延迟的自适应泛洪路由算法
在整个网络内进行泛洪时，因为每个节点无论是否在最终的转发路径上，都要转发报文，这使网络中充斥了大量的无用报文，浪费了许多资源，节点的能量也消耗很快。为了解决泛洪模型的缺陷，本章提出了一种基于延迟的自适应泛洪模型，算法的主要思想是初始化阶段后，源节点先在全网内用较小的路由请求报文(Routing Request Packets，RREQ)和路由回复报文(Routing Reply Packets，RREP)来建立路由，在建立路由的过程中当有节点收到RREQ时，若它比上一跳节点离Sink更远或该报文的TTL－1＝0则它不转发RREQ并丢弃该报文；否则，节点先根据网络的实际情况等待一段时间看是否有更优的来自同一Source的RREQ，若有则转发更优的RREQ直到Sink。Sink接收到RREQ后向最优路回复RREP。而后源节点将沿着建立好的路径转发较大的数据报文。新算法可以分为初始化、路由建立和数据传输阶段。其中，路由建立阶段主要是找到一条较优的从源节点到目的节点的路径，而数据传输阶段则依据路由建立阶段建立的路径传输数据报文。
4.3.1 算法中用到的报文和数据
各阶段中用到的报文和各节点需要维护的表格分别如表4.1、4.3所示：
表4.1 flooding报文表
报文名称 NIP：Neighbors Information Packet(节点信息报文) RRE：Routing Request Packet (路由请求报文) RREP：Routing Reply Packet (路由回复报文) DP：Data Packet（数据报文） RR：Rerouting(重建路由报文)
报文中包含的域 PT＝0,POS,SN PT＝1,SNL,POSS,E,TTL PT＝2,SNL,POSS,TTL PT＝3,SNL,Data PT＝5,SN 长度（bit） 21 ≥24 ≥16 2000 11 29
沈阳理工大学学士学位论文
表4.2 对flooding报文及表格中各数据域的说明
域名 PTP SN POSS E TTL SNLS Data Type
注解 长度（bit） acket Type，报文类型，PT＝0..5分别表示NIP、RREQ、RREP 3 和DP、RR五种中不同的报文 Serial Number，节点序列号 Position，位置信息，其中POSS表示源节点位置信息 Energy，记录报文传送到目前为止所消耗的能量 Time-to-live，报文存活时间 8 10 8 3 Serial Numbers List序列号表，将报文经过的节点序列号都=报文经过的依次列出来 节点数×8 数据，数据报文一律统一为2000bit － 节点类型，TYPE=0,1分别表示存活(Alive，默认值)或死亡 1 表4.3 flooding中各节点需要维护的表格
表格名称 NIT：Neighbors Information Table (邻居信息表) RQT：RREQ Table (RREQ表) RPT：RREP Table (RREP表) 表格中包含的域 POS，SN，Type SNL，POSS SNL，POSS 4.3.2 SFD算法描述
算法包括以下三个阶段：初始化阶段（Initialization Phase，In P）、路由建立阶段（Routing Building Phase，RBP）和数据传输阶段（Data Forwarding Phase，DFP）。 1、初始化阶段（Initialization Phase，In P） Step1：各节点广播节点信息报文NIP；
Step2：收到NIP报文的节点将相关信息存储到邻居信息表NIT中。 2、路由建立阶段（Routing Building Phase，RBP）
30
沈阳理工大学学士学位论文
Step1：Source查找RPT表，若它是某个RREP报文SNL中的一个节点，则它直接沿该RREP确定的路径转发DP，否则广播一个新的RREQ；
Step2：节点ni接收到RREQ后查找RPT表，若它是某个RREP报文SNL中的一个节点，则它直接沿该RREP确定的路径向它的上一跳节点回复RREP，否则：
Step I：若报文的TTL－1＝0，或ni的剩余能量已不够转发一个DP，则转Step IV，否则转Step II；
Step II：ni分别计算ni和该RREQ上一跳节点与Sink之间的距离，若ni较上一跳离Sink更近，则转Step III，否则转Step IV；
Step III：ni等待Δt时间，若来自同源节点有转发能耗更小的RREQ，则将到目前为止收到的来自同一源节点的RREQ中能耗最小的那个报文转发，直到RREQ到达Sink； Step IV：ni丢弃该报文。
Step3：Sink收到RREQ后，沿能耗最小的那些RREQ确定的路径回复RREP，直到RREP到达指定的Source。
3、数据转发阶段（Data Forwarding Phase，DFP）
Step1：Source收到RREP后沿该RREP指定的路径向Sink发送数据报文。
Step2：当ni剩余能耗不够转发DP时，则其广播RR报文，收到该报文的节点在其NIT中将ni状态改为Dead。若ni是目前正在使用的到Sink的路径中的一个节点，则其在该路径中的邻居节点向自己在路径中的上一跳节点发送RR报文，并将RPT表中对应的RREP信息删除，直到RR报文到达该路径的起点。当Source收到RR后，转2。（RR报文中记录了ni的序列号）传感器网络中基于自适应的路由算法研究
4.3.3 性能比较尺度
为了更好的比较各路由算法的优缺点，本文定义了如下一些尺度来具体地衡量算法性能。本文在后面几章中进行算法的性能评价时，仍然使用这些指标。 (1)时间复杂度（Time Complexity，TC）：算法实现时所耗费的时间量级。 (2)消息域（Message Field，MF）：算法实现时所需要的信息范围。
(3)网络检测到的事件总数（即从Source传送到Sink的数据报文总数，Total Detected Events，TDE）：反映了系统的吞吐量。
(4)传送一个事件的平均能耗(Average Energy Expenditure per Event，AEE)：
AEE?网络总能量。
所检测到的时间总数31