基于动态路由的SPIN路由协议改进

冯立波，李 全，张 梅，罗桂兰

（大理学院数学与计算机学院，云南大理 671003）

无线传感器网络（Wireless Sensor Networks，WSN）是由部署在监测区域内大量的廉价微型传感器节点，通过无线通信方式形成的一个多跳自组织网络，现已经广泛应用于军事、生态环境、医疗卫生、空间探索、抢险救灾等领域〔1〕。在WSN中，路由安全对无线传感器网络的应用有着至关重要的作用。由于无线传感器网络硬件设备的特殊性，其更易受到攻击〔2〕。如何增加无线传感器网络被攻击时的抗攻击性，以及如何使得网络具备更高的吞吐量、降低丢包率，延长网络生命周期是当前研究的重点〔3〕。

基于信息协商的传感器协议SPIN（Sensor Protocol for Information via Negotiation）协议采用高级的描述符即元数据（meta-data）来描述数据，节点收到数据后，广播数据的描述信息，感兴趣的节点在收到数据的描述信息后，返回请求信息，只有在收到相应的请求后，节点才向目的地发送数据〔4〕。国内外很多学者对其进行研究，取得了较为显著的成果〔5〕。但是SPIN安全路由协议数据转发过于复杂、重复转发相同数据包的问题影响了SPIN 协议转发时的网络吞吐量，增加了丢包率，缩短了网络的生命周期〔6〕。

本文在研究了SPIN 协议的基础上，提出了一种动态路由信息协商传感器协议D-SPIN（Directional-routing Sensor Protocol for Information via Negotiation）协议，其在SPIN 协议基础上加入了动态路由表建立算法和验证下一跳id选择性转发策略，并利用NS2 仿真软件对算法进行仿真。仿真结果表明，D-SPIN 算法在网络吞吐量、丢包率和网络时延等性能参数上有较大的提高。

1 SPIN协议算法思想及过程

SPIN 是一种以数据为中心的自适应通信路由协议，其数据转发比较复杂，重复转发相同数据包，这给系统性能带来了较为严重的影响。它通过使用节点间的协商制度和资源自适应机制，解决了传统协议所存在的内爆，重叠以及盲目使用资源问题。 SPIN 协议有3 种数据包类型，即ADV、REQ和DATA。ADV 用于元数据的广播，REQ 用于请求发送数据，DATA 为传感器采集的数据包〔7〕。SPIN协议通过两个关键的革新，即信息协商（negotiation）和资源自适应（resource-adaptation）克服了flooding协议的内爆和重叠问题〔8〕。

1.1 元数据与消息类型SPIN 协议使用元数据（meta-data）简洁而完美地描述传感器所收集的数据。SPIN协议没有特殊地规定元数据格式，这种格式是基于实际应用的〔9〕。例如，覆盖的地理区域不相交的传感器可以简单地把自己独有的标识作为元数据。由于每个实际应用中的元数据格式可能都不一样，所以SPIN根据每个应用来解释和综合元数据。

SPIN协议包含3个消息类型，分别是：

①ADV（advertisement）消息（广播消息）：用于新数据的广播。当一个采用SPIN 协议的节点有新数据时，通过发送一个包含元数据的ADV广播消息通知其邻居节点。

②REQ（request）消息（请求消息）：用于请求数据。当一个节点收到其邻居节点的数据包广播，亦即ADV广播消息，若达到规定条件并且需要接收该数据包时可以发送一个REQ 消息向发送节点请求该数据包。

③DATA：实际数据包。DATA是含有携带着一个元数据报头（meta-data header）的传感器采集的实际数据包。

将这些有新数据需要转发而发送ADV 消息的节点统称为“发送节点”，其中网络中第一个封装并广播ADV 数据包的节点称为“源节点”。将所有发送REQ 请求的节点以及所有接收数据数据包的节点统称为“接收节点”，即接收节点接收的数据可能是ADV、REQ或DATA中的任何一类或几类〔10〕。

1.2 SPIN协议工作过程SPIN协议工作过程大致分为3个步骤（又称为“三次握手”）：

步骤1：当一个传感器节点（源节点）有新数据需要传输时，使用ADV数据包对其所有的邻居进行广播，等待接收REQ响应消息。

步骤2：当邻居节点收到这个广播消息时，首先检查其自身的能量值是否低于设定阈值，若能量充足则检查是否已经接收过或请求过该广播的数据；若请求接收该数据，且其拥有足够的能量，就发送REQ消息请求接收新的数据；若已经接收过或请求过该数据或能量低于设定阈值，则不响应。

步骤3：若源节点没有收到REQ消息，则进入结束状态，等待下一次数据传输；若源节点收到REQ消息，则发送数据DATA 给请求节点。接收节点若不是汇聚节点，在接收数据后就变为源节点，返回到第一步，继续执行。

这个过程重复下去，直到数据被传输到汇聚节点。

2 D-SPIN协议算法

针对SPIN 存在的问题，文章在分析了SPIN 协议的基础上，加入了动态路由表建立算法和验证下一跳id选择性转发策略，提出了一种基于动态路由的信息协商传感器协议D-SPIN协议。

2.1 D-SPIN协议改进方法

2.1.1 初始化路由建立算法 D-SPIN协议在SPIN协议基础上增加了动态路由算法，在网络初始化阶段（以下简称“初始化阶段”）建立可用路由记录表，这样在节点有数据转发的时候直接查找路由表中的下一跳节点id，将节点id 封装到ADV 包中，接收节点收到ADV 包后首先匹配id，只有当ADV 包中的id 信息（用变量nexthop_表示）与自身id 相同时，才判断是否已经有该数据，然后执行后续的工作。从而保证了一个数据包只被无线传感器网络中一条链路传输。

D-SPIN协议在建立路由表阶段，将可用的邻居节点（处于正常工作状态并且可以到达的邻居节点）id 都记入路由表中，在有数据需要发送或转发时，使用随机选择算法从路由表中随机选择节点直接进行转发。

此路由建立算法用在网络初始化阶段，通过此算法在每个节点上建立可用路由表。当节点监测到检测对象变化情况或者网络中有数据需要节点转发时，节点即可随机读取可用路由表中的一条记录作为下一跳地址进行转发。

与SPIN协议的原始过程相对比，路由建立算法在节点“有数据需要发送”这一状态和“发送ADV消息”这一动作之间。见图1。

图1 D-SPIN协议路由建立算法

2.1.2 D-SPIN 协议网络正常工作阶段算法改进D-SPIN 协议在网络初始化完成以后即进入网络正常工作阶段，以下简称“正常工作阶段”。在正常工作阶段，协议的算法比起初始化阶段大为简化，相比SPIN 协议原始工作流程图仅仅多了维护可用路由表的工作。只要节点路由表中还有可用路由（可用路由记录指：该路由表nexthop_变量所代表的节点可达，并且处于正常工作状态或可以被唤醒进入正常工作状态），就不会再次启用路由建立算法。只有当节点路由表中已经没有可用路由才会使用路由建立算法重建可用路由表。

维护可用路由表的工作分为两部分，分别由发送节点（源节点或者转发节点）和接收节点完成。分工如下。

①发送节点：在原始流程中“生成ADV包”动作之后，“发送ADV消息”之前这个区间内加入了对下一跳路由记录（本文中等价于“下一跳id 记录”，即变量“nexthop_”所示）的判断，并且随机读取一个下一跳id记录到ADV包中专门预留的地址字段，文章中用变量“id_”表示。如果无可用的下一跳id 则节点自动启用路由建立算法获取并更新可用路由表。如果成功读取了可用的下一跳id 并已经正确添加到ADV包的“id_”字段，则发送该ADV包，接下来的工作与SPIN原始协议流程图相同。见图2。

图2 发送节点算法改进

②接收节点：在正常工作状态，接收节点在收到ADV消息后，先读取ADV包中的“nexthop_”变量（即上一跳节点指定的id字段值），将读取的nexthop_存放到一个临时变量hop 中，判断hop 的值是否等于自身的id，如果不相等，则不作进一步的判断，直接丢弃ADV 包；如果hop 的值与自身id 相等，则表示该包确实是发给自己的，就对ADV声明的数据包进行判断，同时核对自己是否已经有该数据包DATA，如果已经有该DATA，就对该ADV 消息进行简要记录，以便在一段时间内用于判断是否有重复的包送达，在一段规定的时间后，该ADV 自动失效。接下来的过程与原始SPIN协议流程一致。见图3。

图3 接收节点算法改进

2.2 D-SPIN适用环境D-SPIN协议，保留了SPIN协议的诸多特点：平面路由协议，以数据为中心，能量管理机制，资源自适应，使用元数据表示数据等。因此SPIN 协议适用的环境D-SPIN 协议都适用。具体而言，主要用于可以形成平面或者直线的监控网络均可以采用D-SPIN协议，比如桥梁监控，公路路况监控，交通监控，铁路监控，甚至通过在潜艇上部署以用来检测水流速等。

在移动环境中D-SPIN协议仍然适用。D-SPIN协议对节点使用了唯一标识，并且必须保证下一跳信息即“nexthop_”变量与使用的唯一标识一致，这样的设计保证了对移动节点的有效标识。但为了准确地对移动节点引起的路由变化进行准确的识别并更新，不论是否还有可用路由记录，必须根据移动节点的移动速度制定具体的路由更新计划。如果移动节点的移动速度快，即需要缩短更新周期，如果移动节点的移动速度较慢，就可以将路由表更新周期相应延长。

3 性能分析

为了对新协议D-SPIN 的性能进行评价，本文利用NS2 仿真平台对SPIN，D-SPIN 两个协议进行仿真。仿真环境在100M*100M 的区域内随机部署100个节点，仿真参数包括系统吞吐量、丢包率和节点的传输时延。通过编写tcl脚本对协议测试，编写awk 脚本对仿真结果提取数据计算协议的参数指标，使用gnuplot画图工具绘制效果图。

网络吞吐量对比图，见图4。从实验结果来看，D-SPIN 协议的吞吐量在网络工作一段时间后比起SPIN协议有所提高，在网络初始化阶段略低于SPIN 协议，但是在系统稳定之后，D-SPIN 协议比SPIN协议在吞吐量方面提高约5.6%。

图4 系统吞吐量对比图

两个协议的对比曲线，见图5。D-SPIN 协议丢包率全程都低于SPIN，并且稳定在一个较低的范围，同时可以看出，D-SPIN协议比SPIN协议的丢包率减少了11%。

图5 丢包率对比曲线

传输时延比对比图，见图6，传输时延在网络开始时比较明显，高于SPIN 协议，但是网络稳定后维持在一个较低的比值范围，D-SPIN 协议比SPIN 协议的传输时延节省约45%，从而提高了网络的生命周期。

图6 传输时延比对比图

由于网络初始化阶段需要建立路由，而没有现成的可用路由进行转发，而且数据转发所消耗的时间会比SPIN协议长，表现出的特征就是前期时延比较大。在网络稳定后，由于节点已经建立了可用路由表，可直接进行转发，而节点在接收数据时使用了id 匹配后才接收，这样不仅传输效率提升了，网络吞吐量即有所上升，丢包率和传输时延有所下降并保持在一个较低水平。

4 结论

在分析SPIN 协议的基础上提出了一种动态路由信息协商传感器协议D-SPIN 协议，其在SPIN 协议基础上加入了动态路由表建立算法和验证下一跳id选择性转发策略，并利用NS2仿真软件对算法进行仿真。仿真结果表明，D-SPIN 算法在网络吞吐量、丢包率和网络时延等性能参数上有较大的提高。同时，D-SPIN 协议仍然保持了SPIN 协议的诸多优点，而提供了较多的可改进和扩展空间。但是路由表的建立同样会增加节点负担，增加能耗成本，这将是下一步工作的方向。

〔1〕冯立波，黄婷，罗桂兰.一种用于森林防火的无线传感器网络定位算法〔J〕.传感器与微系统，2011，30（5）:123-126.

〔2〕张江丰.基于网格拓扑的无线传感器网络低能耗路由策略〔J〕.传感器与微系统，2013，32（7）:45-49.

〔3〕冯立波，潘丽静，杨润标，等.一种适用于异构网络的TCP New Vegas 算法〔J〕.大理学院学报，2014，13（6）:10-14.

〔4〕任秀丽，李政.基于无线传感器网络SPIN 协议的一种改进方案〔J〕.化工自动化及仪表，2O06，33（2）:35-38.

〔5〕彭志娟，王汝传.基于SPINS的无线传感器网络低能耗安全路由协议〔J〕.计算机应用，2010，30（5）:1149-1152.

〔6〕敬超，常亮，古天龙.基于SPIN的无线传感器网络安全协议建模与分析〔J〕.2009，36（10）:132-135.

〔7〕朱磊，吴灏，王清贤.基于可信基站的SPINS 协议研究与改进〔J〕.计算机应用研究，2010，27（10）:2331-2335.

〔8〕邢明彦，李腊元，何延杰.基于声誉机制的WSN安全路由协议的研究〔J〕. 武汉理工大学学报，2009，31（6）:896-899.

〔9〕PERRIG A，SZEWCZYK R，WEN V，et a1．SPINS：Security protocols for sensor networks〔J〕．Wireless Networks，2002，8（5）：521-534.

〔10〕程宏兵，王江涛，杨庚.SPINS安全框架协议研究〔J〕.计算机科学，2006，33（8）:106-108.