WSN中SPIN协议的研究与模拟实现

1、（2009届）本科毕业设计（论文）资料题 目 名 称： wsn中spin协议的研究 与模拟实现 学 院（部）： 计算机与通信学院 专 业： 通信工程 学 生 姓 名： 班 级： 通信053 学号 指导教师姓名： 职称 讲师 最终评定成绩： 湖南工业大学教务处 2009届本科毕业设计（论文）资料第一部分 设计说明书（2009届）本科毕业设计（论文）wsn中spin协议的研究与模拟实现学 院（部）： 计算机与通信学院 专 业： 通信工程 学 生 姓 名： 刘 蕾 芳 班 级： 通信053 学号 指导教师姓名： 职称 讲师 最终评定成绩 2009年 6 月 湖南工业大学本科毕业设计（论文）摘 要无线

2、传感器网络技术将是21世纪最有发展前景的技术之一。由于其具有组网快捷、灵活，且不受有线网络约束的优点，因而可应用于紧急搜索、灾难救助、环境监测等领域，具有广泛的应用前景，进而使得更节能高效的路由协议的研究变得越来越迫切。论文首先介绍了无线传感器网络发展现状和未来发展前景。接着简略描述了无线传感器网络的基本知识及其特点和性能，并对其网络结构和网络协议体系结构做了简要分析。然后阐述了协议的分类，并比较性的分析了当前一些较为重要的路由协议，分别总结了它们的优缺点和应用范围。最后着重介绍了基于协商的路由协议 spin，针对网络特点对其进行了一些改进，进而解决了“路由选择盲点”和“数据发送盲点”问题。最

3、后在ns2环境下模拟该协议的运行，从得到的数据中分析其节能性和快速性。在spin算法研究中，首先给出了基本的spin-pp算法的有限自动机制，描述了节点间传输数据的过程；接着分析了改进的spin-bc、spin-ec算法；然后又对spin-pp算法的节能性进行了研究；最后通过对仿真实验结果的分析，得到了对spin路由协议的综合评价。 关键词：无线传感器网络，路由协议，基于协商的路由协议spin，ns2abstractwireless sensor network technology will be the one of the most promising technologies in t

4、he 21st century. due to its fast , flexible network, and it is not bound by the merits of cable networks, so it can be used in emergency search, disaster relief, environmental monitoring and other areas. because it has broadly application prospects, thereby making it more energy efficient routing pr

5、otocol research is becoming increasingly urgent.paper firstly introduce the development of wireless sensor networks current status and future prospects for development. then it briefly describes the wireless sensor network and the basic knowledge of the characteristics and performance, its network s

6、tructure and network protocol architecture have also done a brief analysis. and then an agreement on the classification, and comparative analysis of the current routing of some of the more important agreements, respectively, summed up the advantages and disadvantages and their applications. finally,

7、 it focused on the routing protocol spin based on the consultations, its network features a number of improvements to resolve the blind spot routing and data to send blind spot problems. finally, i run the agreement in the simulation environment of ns2 , and analysis its energy-saving and fast from

8、the data obtained.in the research of spin arithmetic, we give the fam of basic spin-pp, and analyze the process of transfer data among the nodes. we analyze the improved spin-bc arithmetic and spin-ec arithmetic, and then analyze the spin-pp arithmetics energy saving property. by the simulate experi

9、ment, we get the synthesized appraise of spin. keywords: wsn，routing protocol ,spin，ns2iv湖南工业大学本科毕业设计（论文）目 录第1章 引言11.1 无线传感器网络研究背景11.2 无线传感器网络国内外研究现状11.3 无线传感器网络存在的问题21.4 无线传感器网络前景和应用21.5 本文组织方式3第2章 无线传感器网络概述42.1 无线传感器网络基本概念42.2 无线传感器网络主要特点42.3 无线传感器网络性能分析52.4 无线传感器网络结构62.5 无线传感器网络协议体系结构6第3章 无线传感器网络

10、路由协议83.1 无线传感器网络路由协议概念83.2 无线传感器网络路由协议分类83.3 无线传感器网络部分路由协议优缺点93.3.1 泛洪协议（flooding）93.3.2 平面路由协议93.3.3 层次路由协议103.4 无线传感器网络spin协议113.4.1 spin协议113.4.2 spin算法123.4.3 spin-pp算法133.4.4 spin-bc算法153.4.5 spin-rl算法173.4.6 spin-ec算法173.4.7 spin算法节能性研究183.4.8 对spin-pp协议的改进方法19第4章 spin协议的ns2仿真结果及分析214.1 ns2仿真平

11、台214.2 ns2仿真的其它辅助工具214.3 ns2网络仿真流程224.4 spin协议的ns2仿真及分析224.4.1 生成随机场景224.4.2 生成随机数据流234.4.3 编写otcl网络仿真代码234.4.4 运用grep 进行数据分析254.4.5 运用gawk进行数据分析264.4.6 运用gnuplot进行画图分析274.4.7 运用nam查看模拟进程304.4.8 各种协议的对比分析31结 论35参考文献36致 谢37湖南工业大学本科毕业设计（论文）第1章 引言无线传感器网络在现实生活中所起的作用已经越来越引起广大国内外科研工作者的兴趣。其研究成果也日益显著，经济科技的飞

12、速发展进一步加快了无线传感器网络应用到现实生活中的步伐。本章节主要介绍了无线传感器网络的研究背景和国内外研究现状，接着又分析了无限传感器网络在研究方面存在的问题及其发展前景和应用。1.1 无线传感器网络研究背景随着传感器技术、无线通信技术和数据处理技术的迅猛发展，已经出现了集这三种技术为一体的传感器器件。这种大量的具有无线通信能力和数据处理能力的传感器器件通过一定的协议构成自组织网络，进而进行数据的收集和传输，为用户提供有用信息，这就是无线传感器网络技术。无线传感网络是继因特网之后，将对21世纪人类生活方式产生重大影响的it热点技术1。2003年，美国商业周刊在其“未来技术专版”中发表文章指出

13、，传感器网络是全球未来的四大高新技术产业之一，将掀起新的产业浪潮。无线传感器网络可应用于军事、应急、环境监控、交通等各个领域，比如企业和社区采用无线传感器网络负责保安与安全、供应监测、人员流动与车辆进出等。在各种社会活动中，无线传感器网络的应用更是举不胜举。而由于无线传感器网络其节点小，分布广的特点，大多都采用电池供电，因而都受到能量消耗的限制，因此电源管理一直是无线传感器网络应用领域关注的重点。目前，在无线传感网的各种应用中，还并没有完善的电源管理机制，因此实现有效的电源管理仍然是无线传感器网络发展的一个巨大技术挑战。 基于协商的路由协议spin就是针对能耗问题而产生的。它通过三次握手的方式

14、有效的提高了能量的使用期限，传输数据消耗的能量相对减少了。清华大学，电子科技大学对spin协议都进行了相关的研究，并提出了一些改进机制。总之，无线传感器网络中对spin协议的研究具有非常大的研究前景和现实意义2。1.2 无线传感器网络国内外研究现状 美国自然科学基金委员会2003年制定了无线传感器网络研究计划，投资3400万元，支持相关基础理论的研究，美国国防部和各军事部门也对无线传感器网络给予了高度重视，把无线传感器网络作为一个重要研究领域，设立了一系列的军事传感器网络研究项目。美国康奈大学、麻生理工学院、南加州大学等先后提出了几类路由协议，包括spin（sensor protocol fo

15、r information via negotiation）、定向扩散协议和泛洪式路由协议等。我国在无线传感器网络方面的研究工作刚开始，清华大学、电子科技大学等单位已经进行了该领域的研究工作，但目前主要集中在介绍国外的研究进展，提出新的研究问题，尚未有新的协议提出。由于无线传感器网络是一门新兴技术，ieee尚未成立无线传感器网络的标准制定小组，美国也是在2000年才开始出现相关研究结果的报道，所以国内与国际水平差距并不算太大3。电子科技大学计算机学院正在开展无线传感器网络路由协议的设计和实现工作。但无线传感器网络依然只处于研究模拟阶段，真正用于生产生活还需要进一步的研究与探索。无线传感器网络的

16、研究方向非常广泛，其发展前景具有长远的现实意义。在网络技术这一层，主要研究点是节点定位问题、时间同步技术的实现连同对网络层协议进行研究。其中在协议研究方面，协议的研究和节能的实现又是息息相关的。本论文主要对路由协议中的spin协议及其改进办法进行研究。1.3 无线传感器网络存在的问题 与以往传统网络相比，无线传感器网络是集成了监测、控制以及无线通信的网络系统，研究传感器网络就不得不提到无线自组网(mobile adhoc network)，实际上他们两者有相似之处，但同时也存在很大的差别。传感器网络是集成了监测、控制以及无线通信的网络系统，节点数目更为庞大(上千甚至上万)，节点分布更为密集。由

17、于环境影响和能量耗尽，节点更容易出现故障；环境干扰和节点故障易造成网络拓扑结构的变化。通常情况下，大多数传感器节点是固定不动的，而无线自组网节点却往往处于运动之中。另外，与无线自组网节点相比，传感器节点具有的能量、处理能力、存储能力和通信能力等都十分有限。此外传感器网络的首要设计目标是能源的高效使用，这也是传感器网络和传统网络最重要的区别之一。 因此无线传感器网络存在的主要问题有节点的定位、能量的存储以及通信能力的改善等。1.4 无线传感器网络前景和应用 微小传感器技术和节点间的无线通信能力为传感器网络赋予了广阔的应用前景，主要表现在军事、环境、健康、家庭和其他商业领域。当然，在空间探索和灾难

18、拯救等特殊领域，传感器网络也有其得天独厚的技术优势。在军事应用方面，因为传感器网络是由密集型、低成本、随机分布的节点组成的，自组织性和容错能力使其不会因为某些节点在恶意攻击中的损坏而导致整个系统的崩溃，使传感器网络非常适用于恶劣的战场环境中，包括监控我军兵力、装备和物资，监视冲突区，侦察敌方地形和布防，定位攻击目标，评估损失，侦察和探测核、生物和化学攻击。在环境科学方面，随着人们对环境的日益关注，环境科学所涉及的范围越来越广泛。通过传统方式采集原始数据是一件困难的工作。传感器网络为野外随机性的研究数据获取提供了方便，比如，跟踪候鸟和昆虫的迁移，研究环境变化对农作物的影响，监测海洋、大气和土壤的

19、成分等。类似地，传感器网络对森林火灾准确、及时地预报也应该是有帮助的。此外，传感器网络也可以应用在精细农业中，以监测农作物中的害虫、土壤的酸碱度和施肥状况等。在医疗健康方面，如果在住院病人身上安装特殊用途的传感器节点，如心率和血压监测设备，利用传感器网络，医生就可以随时了解被监护病人的病情，进行及时处理。还可以利用传感器网络长时间地收集人的生理数据，这些数据在研制新药品的过程中是非常有用的，而安装在被监测对象身上的微型传感器也不会给人的正常生活带来太多的不便。此外，在药物管理等诸多方面，它也有新颖而独特的应用。总之，传感器网络为未来的远程医疗提供了更加方便、快捷的技术实现手段。1.5 本文组织

20、方式本文主要分为四个部分。第一章 引言。介绍了无线传感器网络的研究背景、国内外的研究现状，然后分析了无线传感器网络当前存在的问题及其未来的发展前景和应用。同时又对无线传感器网络的性能指标做了简单分析。第二章 无线传感器网络的基本知识。介绍了无线传感器网络的基本概念，主要特点，性能分析及其网络结构和网络体系结构。第三章 无线传感器网络路由协议。首先介绍了无线传感器网络路由协议的分类，后又对部分协议的优缺点进行了分析。最后着重介绍了无线传感器网络基于协商的路由协议spin 。第四章 spin协议的ns2仿真结果及分析。首先对ns2工具进行了简单介绍。其次又介绍了ns2的网络仿真流程。最后详细阐述了

21、spin协议ns2的仿真及分析。38第2章 无线传感器网络概述 无线传感器网络的自组织性、容错性等特殊性能使其比较适应于火山，自然保护区等特殊环境的检测。网络架构和网络协议体系结构保证了信息的正常合理高效的传输。本章节主要介绍了无线传感器网络的基本知识，其中包括无线传感器网络的基本概念、主要特点、主要性能、网络架构和网络协议体系结构。2.1 无线传感器网络基本概念 无线传感器网络(wsn，wireless sensor networks)是由部署在监测区域内大量廉价的微型传感器节点组成，通过无线通信方式形成的一个多跳自组织网络，是当前在国际上备受关注的、涉及多学科高度交叉、知识高度集成的前沿热

22、点研究领域。他综合了传感器技术、嵌入式计算机技术、现代网络及无线通信技术、分布式信息处理技术等，能够通过各类集成化的微型传感器协作地实时监测、感知和采集各种环境或监测对象的信息，这些信息通过无线方式被发送，并以自组多跳的网络方式传送到用户终端，从而实现物理世界、计算机世界连同人类社会三元世界的连通。无线传感器网络是有一组传感器以ad hoc方式构成的无线网络，起目的是协作地感知、采集和处理网络覆盖的地理区域中感知对象的信息，并发布给观察者。2.2 无线传感器网络主要特点无线传感器网络不同于传统网络，它有自己独特的性能特点，其主要特点是4：（1）硬件资源有限。节点由于受价格、体积和功耗的限制，其

23、计算能力、程序空间和内存空间比普通的计算机功能要弱的多。这一点要求在节点操作系统中，协议层次不能太复杂。（2）电源容量有限。网络节点有电池供电，电池的容量一般不是很大。其特殊的应用领域决定了在使用过程中，不能给电池充电或更换电池，一旦电池能量用完，这个节点也就失去了作用（死亡）。（3）无中心。无线传感器网络没有严格的控制中心，所有节点地位平等，是一个对等式网络。节点可以随时加入和离开网络，任何节点出故障不会影响整个网络的运行，具有很强的抗毁性。（4）自组织。网络的布设和开展无需依赖于任何预设的网络设施，节点通过分层协议和分布式算法协调各自的行为，节点开机后就可以快速、自动地组成一个独立的网络。

24、（5）多跳路由。网络中节点通信距离有限，一般在几百米范围内，节点只能与它的邻居节点直接通信。如果希望与其射频范围之外的节点进行通信，则需要通过中间节点进行路由。（6）动态拓扑。无线传感器网络是一个动态的网络，节点可以随处移动；一个节点可能因为电池能量耗尽或其他故障，退出网络运行；一个节点也可能由于工作的需要而被添加到网络中。这些都会使网络拓扑结构随时发生变化。（7）节点数量众多，分布密集。为了对一个区域进行检测任务，往往有成千上万传感器节点空投到该区域。传感器节点分布非常密集，利用节点之间的相对连接性来保证系统的容错性和抗毁性。2.3 无线传感器网络性能分析传感器网络的性能直接影响其可用性，至

25、关重要。如何评价一个传感器网络的性能是一个需要深入研究的问题，主要有以下几个指标5。（1）能源有效性：传感器网络的能源有效性是指该网络在有限的能源条件下能够处理的请求数量，能源有效性是传感器网络的重要性能指标。（2）生命周期：传感器网络的生命周期是指从网络启动到不能为观察者提供所需要的信息为止所持续的时间。（3）时间延迟：传感器网络的延迟时间是指当观察者发出请求到其接收到回答信息所需要的时间。（4）感知精度：传感器网络的感知精度是指观察者接收到的感知信息的精度。传感器的精度、信息处理方法、网络通信协议等都对感知精度有所影响、感知精度、时间延迟和能量消耗之间具有密切的关系。（5）可扩展性：传感器

26、网络可扩展性表现在传感器数量、网络覆盖区域、生命周期、时延迟、感知精度等方面的可扩展极限、给定可扩展性级别，传感器网络必须提供支持该可扩展性级别的机制和方法，目前不存在可扩展性的精确描述和标准，还需要进一步的深入研究。（6）容错性：传感器网络中的传感器经常会由于周围环境或电源耗尽等原因而失效。由于环境或其他原因，物理地维护或替换失效传感器常常是十分困难或不可能的，这样，传感器网络的软、硬件必须具有很强的容错性，以保证系统具有高强壮性。2.4 无线传感器网络结构在传感器网络中，节点通过飞机布撒或人工布置等方式，大量部署在被感知对象内部或附近，这些节点通过自组织方式构成无线网络，以协作的方式实时感

27、知、采集和处理网络覆盖区域中的信息，并通过多跳网络将数据经由sink节点(接收发送器)链路将整个区域内的信息传送到远程控制管理中央。反之，远程管理中央也能够对网络节点进行实时控制和操纵。整个网络主要包括如图2.1所示的几部分7：互联网和卫星汇聚节点任务管理节点监测区域传感器节点 图2.1 无线传感器网络结构传感网络：这是传感器网络的核心。在感知区域中，大量的节点自组成网，监测、感知信息向sink节点发送，或接收来自sink节点的操作命令，改变自身的工作状态。sink节点(接收发送器)：它拥有足够的能量，能够将从传感器网络中能量有限的节点上传来的信息转发到传输介质上2。 传输介质(interne

28、t网或通讯卫星)：它是用户和传感网络间的桥梁和纽带。网络用户(任务管理节点)：它负责从网络中获取所需要的信息，同时也能够对网络做出各种各样的指示、操作等。2.5 无线传感器网络协议体系结构从网络分层模型的角度分析，无线传感器网络的通信协议体系主要包括物理层、数据链路层、网络层、传输层和应用层，如图2.2所示。其中，物理层提供了简单但健壮的调制、发送和接受技术；数据链路层负责无线信道的使用，控制减少另外节点广播引起的冲突。网络层实现数据融合，路由经过处理检测数据汇聚点（sink）；传输层在传感器网络通过internet或其它网络互连的时候是不可少的；应用层为用户开发各种传感器网络应用提供有效的软

29、件开发环境和软件工具。与各层网络协议相关的管理平台，管理平台有能量管理平台、移动管理平台和任务管理平台。能量管理平台管理传感器节点如何使用能量；移动管理平台检测和注册传感器节点的移动，维护到汇聚点的路由，使得传感器节点能够跟踪它的邻居；任务管理平台在一个给定的区域内平衡和调度检测任务2。任务管理平台移动管理平台能量管理平台应用层传输层网络层数据链路层物理层图2.2 无线传感器网络协议体系结构第3章 无线传感器网络路由协议一个完整的路由协议是保证网络信息正常高效传输的最根本保证。因此无线传感器网络路由协议的研究就显得越来越重要和关键。本章主要描述了无线传感器网络的路由协议方面的知识。首先介绍了无

30、线网络的路由协议的概念及其分类。然后又对一些重要的路由协议的优缺点进行了简单的分析。最后着重介绍了无线传感器网络spin协议，并研究了spin-pp协议的改进方法。3.1 无线传感器网络路由协议概念路由协议是无线传感器网络层的核心技术。路由协议负责将数据分组从源节点通过网络转发到目的节点，它主要包括两个方面的功能：寻找源节点和目的节点间的优化路径以及将数据分组沿着优化路径正确转发。3.2 无线传感器网络路由协议分类无线传感器网络路由协议负责在汇聚节点和传感器节点间可靠地传输数据。 由于其应用的相关性,单一的路由协议不能满足各种应用需求,因而研究人员提出了多种不同的路由协议。但到目前为止,仍缺乏

31、一个完整和清晰的路由协议分类3。 第一种分类方法：将目前已有的路由协议和算法分为无路由表型和基于路由表型。就路由建立的时机而言,基于路由表的路由协议又可分为主动型和响应型。基于路由表的主动型路由协议按网络结构又可分为平面型和层次型。路由协议的分类层次，如图3.1所示。第二种分类方法：根据不同的无线传感器网络路由结构和数据传输模型。对目前的路由协议作了以下4种分类：以数据为中心的路由协议、层次路由协议、地理位置路由协议、基于qos的路由协议3。第三种分类方法：根据网络的结构，将无线传感器网络路由协议分为三种，即平面路由协议、分等级路由协议和位置路由协议。第四种分类方法：根据路由的作用，无线传感器

32、网络路由协议可以分类为基于多路径、基于查询、基于协商、基于qos或基于相关的路由协议。第五种分类方法：根据如何获得从源到目的的路由，无线传感器网络路由协议也可以分为先验式、反应式和混合式。无路由表型有路由表型主动型响应型平面型层次型floodingspeedsarspinpegasisleachddrumor图3.1 路由协议的分类层次3.3 无线传感器网络部分路由协议优缺点无线传感器网络的协议栈由物理层、数据链路层、网络层、传输层和应用层组成。网络层负责路由的发现和维护，一个网络设计的成功与否，路由协议非常关键。在这里我们选择了一部分wsn路由协议进行分析，比较它们各自的优缺点。3.3.1

33、泛洪协议（flooding）flooding and gossiping 这种算法是传统网络中最基本的路由方式,不需要知道网络拓扑结构和使用任何路由算法。每个传感器节点把自己接收到的packet发送给所有它的邻居节点,这个过程一直重复直到该分组到达sink节点或者该分组的生命到期( ttl ,在传感器网络里面通常定义为最大跳数) 。gossiping算法改进了flooding 过程,每个传感器节点只把自己接收到的packet 随机发送给它的某个邻居节点,其他不变，这种方式虽然实现简单,但是并不适用于相关应用程序,而且还很容易带来内爆(implosion)和重叠(overlap)问题。3.3.2

34、 平面路由协议1. spinspin( sensor protocols for information via negotiation)是一组基于协商并且具有能量自适应功能的信息传播协议。 它使用三种类型的信息进行通信,即adv、req和data信息。在传送data信息前,传感器节点仅广播包含该data 数据描述机制的adv信息,当接收到相应的req请求信息时,才有目的地发送data信息。使用基于数据描述的协商机制和能量自适应机制的spin协议能够很好地解决传统的flooding gossiping协议所带来的信息爆炸、信息重复和资源浪费等问题。2. dd定向扩散路由dd(directed

35、diffusion)是一种以数据为中心的信息传播协议,与已有的路由算法有着截然不同的实现机制。 运行dd的传感器节点使用基于属性的命名机制来描述数据,并通过向所有节点发送对某个命名数据的interest (任务描述符)来完成数据收集。在传播interest的过程中,指定范围内的节点利用缓存机制动态维护接收数据的属性及指向信息源的梯度矢量等信息 ,同时激活传感器来采集与该interest相匹配的信息。节点对采集的信息进行简单的预处理后,利用本地化规则和加强算法建立一条到达目的节点的最佳路径。经仿真分析,该算法具有很好的节能性和可扩展特性。3.3.3 层次路由协议1. leachleach(low

36、 energy adaptive clustering hierarchy)是一种基于多簇结构的路由协议。它的基本思想是通过随机循环地选择簇首节点将整个网络的能量负载平均分配到每个传感器节点中,从而达到降低网络的能源消耗，提高网络整体生存时间的目的。leach在运行过程中不断地循环执行簇重构过程。每个重构过程分成两个阶段:簇的建立阶段和传输数据的稳定阶段。为了节省资源开销,稳定阶段的持续时间要长于建立阶段的持续时间4。 与一般的基于平面结构的路由协议和静态的基于多簇结构的路由协议相比。leach 可将网络的整体生存时间延长15%。2. teen节能的阈值敏感路由teen( threshold

37、sensitive energy efficient sensor network protocol)是具有实时性的路由协议。它采用与leach 相同的多簇结构和运行方式。不同的是,在簇的建立过程中,随着簇首节点的选定,簇首除了通过tdma方法实现数据的调度,还向簇内成员广播有关数据的硬阈值和软阈值两个参数。通过设置硬阈值和软阈值两个参数, teen能够大大地减少数据传送的次数,从而达到比leach算法更节能的目的。teen协议的优点是适用于实时应用系统,可以对突发事件做出快速反应。 它的缺点是不适用于需要持续采集数据的应用环境。3.4 无线传感器网络spin协议3.4.1 spin协议spi

38、n路由算法假设所有传感器节点都可能是希望获得数据的汇聚节点，每个传感器节点知道自己是否需要数据以及是否在数据源到汇聚节点的路径上。为了减少节点的能量消耗，传感器节点在传送数据之前彼此进行协商，协商制度可以确保只传输有用的数据。为了成功的进行协商，节点必须能够描述它所采集的数据。spin协议中用于协商的描述符成为元数据。由于元数据的大小小于采集的数据，所以传输数据消耗的能量相对较少。 为了避免盲目使用资源，所有传感器节点必须能监控各自的能量变化情况。在spin协议中，节点在数据传输之前检查各自的能量，每一个传感器节点都有用来监控能量消耗的资源管理器，应用程序在传输或处理数据之前都要探查管理器。如

39、果超出其能量水平，则必须中止一些操作。spin协议有adv、req、和data这3种类型的消息。adv用于新数据的广播，req用于请求数据，data是数据信息。spin-1和spin-2是两个比较重要的spin协议。spin-1协议是一个通过无损网络分发数据的简单握手协议，它采用三次握手的方式，当节点有新的数据想要分发时，它向其所有邻居节点广播简短的包括数据描述符的adv消息；当邻居节点收到这个adv消息后，如果对这个数据感兴趣，则先检查自己是否已经收到该数据，若没有它将发送req请求消息请求该数据，否则不予响应；源节点在收到req消息后，发送data给请求节点，这些邻居节点重复以上过程，从而

40、可以使网络中所有对数据感兴趣的传感器节点都能获得它 (如图3.2所示) 。spin-2协议在spin-1协议的基础上增加了一个最低能量门限。当节点所具有的能量是充足的，spin-2和spin-1一样，采用三次握手的方式。然而，当节点的能量开始接近于最低能量门限时，它将减少自己在协议中的参与。也就是说，节点只有在确定它能完成三次握手而能量不会低于最低能量门限时，才会参与协议。spin协议的优点在于简单，节点仅需要知道它的邻居节点，无需其它拓扑信息。 图3.2 spin-1协议3.4.2 spin算法1、spin-pp。采用点到点的通信模式，并假定两节点间的通信不受其它任何节点的干扰，分组不会丢失

41、，功率没有任何限制。要发送数据的节点通过adv向它的相邻节点广播消息，感兴趣的节点通过req发送请求，数据源向请求者发送数据。接收到数据的节点再向它的相邻节点广播adv消息，如此重复，使所有节点都有机会接收到任何数据。2、spin-ec。在spin-pp的基础上考虑了节点的功耗，只有能够顺利完成所有任务且能量不低于设定阈值的节点才可参与数据的交换。3、spin-bc。设计了广播信道，使所有在有效半径内的节点可以同时完成数据交换。为了防止产生重复的req请求，节点在听到adv消息以后，设定一个随机定时器来控制req请求的发送，其它节点听到该请求，主动放弃请求权利。4、spin-rl。它是对spi

42、n-bc的完善，主要考虑如何恢复无线链路引入的分组差错与丢失。记录adv消息的相关状态，如果在确定时间间隔内接收不到请求数据，则发送重传请求，重传请求的次数有一定的限制。由于spin算法的数据选择性转发并没有方向性，完全可能向着错误的方向传输。如图3.3所示的无线传感器网络中，是一个存在“凸点”的半岛地形，传输到“凸点”的数据会丢失。图3.3 spin-bc路由算法的缺陷所以，spin算法的最适用场合是无线传感器网络部署的区域为一个长矩形，sink节点在长矩形的两端均有部署，在这种情况下，既不会出现前面的问题，又能够充分发挥spin算法的优势。无线传感器网络部署区域为长矩形的应用很多，例如高速

43、公路上部署无线传感器网络来采集天气信息，又如桥梁上部署无线传感器网络来采集桥墩的压力信息，再如潜水艇上部署无线传感器网络来收集水流的相关信息。这种情况下使用更复杂平面的路由或层次路由算法都没有必要，不仅不能得到更好的性能，反而因为这种特殊的无线传感器网络拓扑结构，造成网络性能的恶化。3.4.3 spin-pp算法使用spin路由的节点，需要用有限自动机来管理节点的状态。节点有如下的这些状态7：表3.1 有限自动机的状态状态编号状态描述begin待机状态有数据要发送状态（发送数据或转发数据）已发送adv消息，等待req回应已收到req消息，等待发送data数据已发出data消息已收到adv消息，

44、等待发送req消息已发送req消息，等待接收data数据end处理完毕有限自动机节点有如下这些事件导致状态变化：表3.2 有限自动机的事件事件编号事件描述发送adv消息发送req消息发送data消息接收adv消息接收req消息接收data消息超时随机延时传感器采集到数据要发送在这种情况下，我们可以画出spin-pp路由的节点的有限自动机（如图3.4所示）。图3.4 spin-pp路由算法节点的有限自动机我们来看使用该有限自动机，节点状态的变化。(a)(b)（e）图3.5：spin-pp路由算法节点的状态变化第1个时钟周期内，如图3.5（b）所示，节点1、2处于有数据要发送的状态，数据可能是其它

45、节点转发的，也可能本节点的传感器采集的；节点3、4、5处于待机状态。节点1、2发送adv消息后，根据有限状态机的规则，变为状态；而节点3、4、5收到adv消息，变为状态，如图3.5（c）。在第2个时钟周期内，节点3、4、5发送req消息，变为状态；节点1、2收到req消息以后，变为状态,如图3.5（d）。在第3个时钟周期内，节点1、2发出data数据，变为状态；节点3、4、5收到data数据，变为状态，如图3.5（e）。节点1、2经过一段时间没有再收到req消息的请求以后，进入end状态。节点3、4、5开始重复节点1、2的过程，转发数据。此时，节点1、2收到adv消息以后，将不会响应。这就解决

46、了flooding路由算法的“重复”问题。 3.4.4 spin-bc算法从上面的分析可以看出，spin-pp路由算法已经有效的解决了flooding路由算法的“重复”问题，但依然存在“内爆”的问题。因此，在此引入了spin-bc路由算法试图来解决该问题。如图3.6所示，引入了状态x1和事件8，事件8是指进行一个随机时间长度的延迟。节点在有数据要发送的状态，首先经过一个随机的延迟，才进入待发送数据的x1状态。在状态和状态x1收到req消息，表明周围的其它节点开始了数据转发的流程，自己不需要重复发送，可以直接进入end状态。图3.6 spin-bc路由算法节点的有限自动机我们来看使用spin-b

47、c路由算法的节点的状态变化。 如图3.7（b）所示，节点1、2处在状态，此时不直接发送数据，而分别进行一个随机延迟。假设节点1的延迟先完成，率先进入状态1，此时节点1开始发送adv消息，如图3.7（c）所示。节点3、4收到adv消息以后，返回req消息。节点1收到该消息以后，发送data数据；而节点2当时不管处于状态还是延迟完成进入状态1，收到req消息以后，均进入end状态，如图3.7（c）和（d）所示。节点3、4收到data数据以后，完成此轮数据转发。可以看出，通过新引入状态1、随机延迟的事件和有限自动机的改进，spin-bc算法可以解决spin-pp路由算法的“内爆”问题。（a）（a）图

48、9(a) (c) (d) (b) （e） （f）图3.7 spin-bc路由算法节点的状态3.4.5 spin-rl算法spin-rl路由算法在spin-bc路由算法的基础上，增加了一个机制，节点发送adv消息以后，等待req消息的过程中，如果超过设定的时间阈值，则返回状态，重新发送adv消息(如图3.8所示)。图3.8 spin-rl路由算法的有限自动机3.4.6 spin-ec算法spin路由算法跟flooding相比，能量消耗得到很大节约，但相应的代价就是时间的消耗成倍的增加了。设相邻节点发送消息到收到消息平均消耗的时间为t，在某区域内，节点a经过j跳达到节点b。那对于flooding路

49、由算法，从节点a到节点b的总时间为：tflooding=tj （3.1） 对于spin-pp路由算法，任何一跳都要经过adv、req、data三次信息的交换，则节点a到节点b的总时间为：tspin-pp=3tj （3.2）对于改造后的spin-bc路由算法，每一跳还要经过发送adv和req之前的2次随机延迟。随机迟延的长短取决于网络节点部署的密集程度，对于n-邻点网络，平均延迟应为n/2。则我们认为节点a到节点b的总时间为：tspin-bc=(3t+n/2*2t)*j=(3+n)tj （3.3）可以得出，在时间消耗上，spin-pp路由算法是flooding路由算法的3倍，spin-bc路由算

50、法是它的3+n倍。n的典型值包括38，那么可以认为spin-bc路由算法的时间消耗是flooding路由算法的611倍，随着网络规模的扩大，差值会不断增大。由此可以看出，spin路由算法适用于对数据传输的延迟要求不高，而节点能量特别有限的场合。3.4.7 spin算法节能性研究无线传感器网络的能量是非常有限的，任何环节都要考虑能量的消耗。设节点发送1个字节消耗能量es，节点接受1个字节消耗能量er。假设一种应用，在n-邻点网络中，1个节点将m个字节的数据广播到该网络中的所有n个节点中，分析这种情况的能量消耗。在理论上，能量消耗的最小值为4： e=nm(es+er) （3.4）我们首先考虑使用洪

51、泛路由的情况。对于网络中的任一节点a，要转发m个字节的数据，此时消耗发送能量： e1=mes （3.5）a节点周围的n个节点，在洪泛情况下均会向a节点转发这m个字节的数据，所以a节点会消耗接收能量：e2=nmer （3.6）那么，由（3.5）和（3.6）式，在n个节点的网络中广播m个字节的信息，总共会消耗能量：eflooding=nmes+nmner （3.7）我们再考虑spin路由的情况。对于网络中任一节点b，转发m个字节数据的步骤是：1、发送adv消息，消耗es的能量；2、收到周围n个节点的req消息，消耗的ner的能量；3、发送data+m个字节信息，消耗（m+1）es的能量.节点b接收

52、m个字节的数据的步骤是：1、接收adv消息，消耗er的能量；2、发送req消息，消耗es的能量；3、接收q次data+m个字节信息，消耗q（m+1）er的能量，其中nq1，q的取值取决于网络节点部署的情况。 根据上面的描述，spin路由消耗的能量为：espin=n(es+ner+(m+1)es)+(er+es+q(m+1)er) （3.8） 化解为：espin=n(m+3)es+n(n+1+qm+)qer （3.9）比较式（3.9）和式（3.7）可以看出：与洪泛路由算法相比，spin路由多付出3nes+(n+1+q)ner的管理上的能量消耗，但节约了(n-q)mner的能量消耗。这个结论说明，

53、在传输的数据较多，m的值较大时，spin路由算法比洪泛路由算法进行了很大的优化。3.4.8 对spin-pp协议的改进方法spin协议有4种不同的形式：spin-pp，spin-ec，spin-bc，spin-rl。这里只分析spin-pp，并介绍对它所做的改造。一个传感器节点在发送一个data数据之前，首先向其邻居节点广播adv数据包，那么它向该节点发送一个req数据包，接着节点向该邻居节点发送data数据包，类似地进行下去，data数据包可被传输到远处的sink节点。 但是spin协议不能保证数据的传递性。产生这种结果有两种可能，一种是由于邻居节点自身能量的原因，不愿意承担转发新的数据，使数据无法传输；另一种是对信息感兴趣的节点远离了源节点，使数据也无法传到目的地。因此造成了能量浪费，降低了数据投递率，增加了传输延时，以致影响整个网路的信息收集。针对存在的这个问题，