Flooding算法改进及其应用

唐坚刚+潘锐

摘 要：针对泛洪式路由算法（Flooding）中路由信息内爆的缺点，提出一种基于Flooding的改进路由算法，该算法根据所有路灯采用静态地址，并通过序列号对协调器所发的命令帧进行标记。子节点根据序列号对数据帧进行过滤。最后，结合智能路灯控制系统和改进的Flooding算法进行路由实验。

关键词关键词：Flooding算法；静态地址；路灯控制系统

DOIDOI：10.11907/rjdk.161531

中图分类号：TP312

文献标识码：A ：1672-7800（2016）008-0006-04

0 引言

随着网络技术的迅速发展与人们对共享资源需求的不断增长，网格技术已成为分布式计算领域近年来研究的一个热点[1]。无线传感器网络是集信息采集、信息处理、信息传输于一体的综合系统[2]。Flooding路由协议[3]是传统网络中最为经典和简单的路由协议，是基于泛洪机制的路由协议，可以应用到无线传感器网络中。该协议不要求维护网络的拓扑结构和相关路由计算，仅要求传感器网络节点在接收到信息后以广播的方式向邻居节点转发数据包，邻居节点重复执行上述过程（转发时除去刚刚发送给它们的节点），直到数据包到达目的地或者该数据包的生命周期结束。

1 国内外研究现状

路由协议是无线传感器网络的重要技术[4]，目前国内外学者作了相关研究。在路由表中，通过增加路由方向与资源状态信息两者之间的关联度，有效增加资源请求被转发到可满足节点的概率[5]；根据Power-Law规律，总选择具有最大聚集度的节点进行转发[6]；先根據一定的标准判断两个查询请求的相似性，然后将最新的查询请求转发给最近满足相似查询的邻居节点[7]。

2 Flooding路由算法

在无线传感器网络中数据包的生命周期中，一般预先设定该数据包所转发的最大跳转数。假设源节点A需要将数据包p发送至汇聚节点D，网络拓扑结构如图1所示，节点之间的联机表示两者在通信范围内可通信。节点A首先将p的副本进行广播，则其邻居节点B、E、G接收到p副本之后，直接将p副本通过广播的形式转发（除去节点A），以此类推，直到p达到汇聚节点D或TTL。以节点B、C为例，如图2所示，B将p副本转发至节点C、E、F，C将p副本转发至节点E、F、D。

3 改进后的Flooding路由算法

针对Cluster-Tree算法和Flooding算法的缺点，给出了一种基于Flooding算法的改进路由算法。该算法通过修改网络层的帧结构，在末尾加入序列号，标记中心协调器每次发送的数据帧。中心协调器在每次发帧时生成序列号。当路由节点收到一个数据帧时，提取帧中的序列号，将其跟之前刚收到的序列号进行校验，若相同，则不进行任何操作，反之，就会处理接收的数据帧，执行相关命令，记录数据帧并进行广播。算法流程如图3所示。

4 改进后的Flooding路由算法实现

4.1 平台简介

为了有效提高网络的传输效率，中心协调器和路由器以MC13213芯片安装在路灯上，软件部分采用基于MsstatePAN的协议栈，在网络层部分，不采用Cluster-Tree的地址分配方法，使用改进的Flooding算法进行测试。

4.2 数据帧结构设计

在重新定义帧结构时，由于考虑到路灯的实际使用情况，结合该算法，总共设定了60字节的帧结构，目前只使用了33个字节，剩余27个字节作保留，数据帧结构定义如图4所示。在设计帧时，网络ID是识别该网络的唯一标识，帧总共分为两种类型，命令帧和确认帧，命令帧是从协调器发出的，确认帧是从节点发出的，协调器需要处理的帧如图5所示。

（1）目的地址。标识接收开关灯等命令的最终节点，而不一定是指路由结点。如果不是0xFF，则表示控制单盏灯，如果是0xFF，则表示控制多盏灯，此时“开灯间隔参数”有效。

（2）开灯间隔。由协调器进行处理，间隔为1表示开二分之一的灯，2表示开三分之一的灯，表示单侧灯的间隔状况。这是为某些天气情况下，需要开间隔灯而设计的。

（3）左右标识。表示路两侧哪一侧的灯，0x01表示“左”侧，0x02表示“右”侧，0x03表示所有的侧，“左右”由人为指定包含在帧里面。只有当“目的地址”为0xFF时，“开灯间隔”以及“左右标识”参数才有效。这3个参数由协调器进行处理。

（4）序列号。由协调器生成，大小为2个字节，当值达到0xFFFF时，系统自动清零，目的是对协调器发出的命令帧进行标记。

4.3 命令帧及确认帧的演示及说明

如图6所示，总共八盏灯被依次编号，每盏灯都被看作是一个节点。在所有节点正常运作情况下，使用协调器通过串口发出命令，命令7号灯开灯，并且运用改进的Flooding路由算法，图6展示的是其中一种可能路径。

从图6看出，黑色实心圆是协调器，空心圆是子节点，当协调器发出第一条命令时，给命令帧标序列号1，节点1和节点2收到序列号为1的命令帧，然后节点1和节点2对这命令帧进行处理，并广播出去。如果节点3先接收到节点1的命令帧进行处理，然后又收到节点2的命令帧，但是判断序列号相同且都为1，则不对第二次收到的帧进行处理，其它节点跟节点3相同。最终节点7收到命令帧，判断后处理，灯亮。

假设出现节点损坏，且中心协调器需要对此节点后面的节点进行操作，则其它节点在将数据帧传送给此节点时，此节点不能对其进行处理，但是基于此算法的优点，数据帧可以通过此节点的左右邻节点或者对面的节点进行广播，从而数据帧能够被后面的节点接收。

经过上述过程，节点7打开灯后，需要返回一个确认帧给协调器，将原来的命令帧改为确认帧。节点5和节点8判断这是确认帧就不比较刚才的序列号，确认帧经过不断转发，最终协调器收到此确认帧。具体过程如图7所示。

5 应用实例介绍

通过上文对Flooding算法的分析及改进可知，理论上，改进后的算法具备实现的可能。结合ZigBee技术设计路灯硬件系统，并制作节点模型进行实验，将改进的Flooding算法和原始算法的执行效果进行对比。

5.1 路灯控制系统硬件设计

根据照明控制器所实现的主要功能，硬件部分如图8所示，主要包括ZigBee模块、功率检测模块、电源管理模块、超声波模块、光线检测模块继电器模块以及微处理器（MCU）模块等。

5.2 软件开发环境

在设计程序时，选择Windows XP操作系统、CodeWarrior 软件开发环境以及硬件仿真器 USB Multilink 连接工具来完成程序的编写、调试。CodeWarrior 软件开发工具支持飞思卡尔处理器芯片的软件编程、连接和源程序调试[8]。使用CodeWarrior软件编写代码时，使用C语言进行编写，编写完成后通过 USB Multilink 连接工具与硬件平台连接[9]，并将程序下载到芯片中。

5.3 路灯模型展示

为了测试该新型智能照明控制器的感应性能，结合路灯控制特点，搭建一个由6个节点组成的智能照明模拟测试环境，测试环境由PC机控制界面以及配置照明控制器节点的组网模型组成。测试的主要项目是稳定性、智能响应等，通过户外模拟进行实际性能测试。制作路灯模型后进行实验，如图9所示。

由于帧结构设计得比較完整，通过串口向节点发送不同的帧，可以实现不同模式的亮灯模式，使用一个上面装有6个节点的木板模型来模拟，有单盏点亮、间隔开关灯和全灯点亮等模式，全灯点亮如图10所示。

6 实验结果及分析

6.1 实验场景设置

实验场景设置如下：①节点个数：中心协调器1个，子节点数目6个；②节点间传送数据距离为30m；③实验规则：路灯以左边为奇数，右边为偶数依次排列；④实验次数：同时重复实验500次；⑤针对Cluster-Tree算法设置：CM=4，RM=4，LM=3。

6.2 无故障节点实验结果

假设所有节点为正常，没有损坏，分别对改进Flooding和Cluster-Tree算法进行开全灯实验，通过灯是否全亮或者主节点接收到的数据包查看是否有丢包情况。从实验结果中可以看出，在所有节点正常的情况下，协调器命令所有节点开灯，改进的Flooding算法和Cluster-Tree算法路由转发能力相当，其中有几次节点转发不成功。实验结果如图11所示。

6.3 节点故障实验结果

假设其中一个节点损坏，则分别对改进Flooding和Cluster-Tree算法进行开全灯实验，从实验结果中可以看出，在一个节点损坏的情况下，协调器命令所有节点开灯。改进的Flooding算法明显比Cluster-Tree算法路由转发能力强，开灯成功率高、丢包率低。

对于不能使所有灯全开的情况，多次发帧仍然可以使没有亮的灯开灯。通过多次实验发现可能由以下原因引起：①发帧过于频繁；②节点之间相互干扰。实验结果如图12所示。

7 结语

改进后的Flooding算法实现方法浅显易懂，继承了原来Flooding的优点，即每个节点只需将接收到的数据包进行判断，再进行广播，而无需查找路由表，选择下一跳节点的计算。并且，其无需特殊的算法来保持网络拓扑信息的更新以及新路由的发现，而且避免了原来Flooding信息内爆、部分重迭和网络资源利用不合理的缺点。

参考文献：

[1] 张秋余，乔赞，袁占亭.基于偏好和M-Flooding的网格资源发现[J].计算机工程，2010，36（14）：40-45.

[2] I F AKYILDIZ，W SU，Y SANKARASUBRAMANIAM.A Survey on sensor networks[J].IEEE Commianications Magazine，2002，40（8）：102-114.

[3] 殷波.无限传感网络路由算法研究[D].武汉：华中科技大学，2006.

[4] 郭文静.无限传感器网络生命期优化路由协议的研究[D].上海：华东师范大学，2013.

[5] 周从华，刘志锋.具有过去时态算子的计算树逻辑模型检测[J].计算机工程，2007，33（22）：98-100.

[6] 李健，唐文忠，宋长福.角色访问控制技术在管理信息系统中的应用[J].北京航空航天大学报，2003，29（6）：534-538.

[7] LI XIAOOU，MEDINA J M，CHAPA S V.Applying petri nets in active database systems[J].IEEE Transactions on Systems，Man and Cybernetics，2007，37（4）：482-493.

[8] 王江峰.基于ZigBee无限传感网络的实现[D].济南：济南大学，2010.

[9] 位元文化.精通 PalmOS 程序设计：Codewarrior 入门教程[M].北京：清华大学出版社，2001.

（责任编辑：孙 娟）