关键字：无线传感器网络;路由协议;TinyOS操作系统
LI Liang, LIU Lin-Lan, SHU Jian, CHEN Ying
Abstract: routing protocol of wireless sensor networks （WSN） is an important hotspot. The routing protocol based on minimum hop can efficiently reduce the number of message into lowest, has the trait of easy implement and wide application. For the aim of increasing the packet success rate, this paper proposes a routing protocol base on reliable minimum hop field, particularly introduce the building process of the reliable minimum hop field and the routing method. Simulation in TinyOS operation system shows the correctness of our protocol.
Keywords: wireless sensor network; routing protocol; TinyOS operation system
1. 引言
无线传感器网络由大量随机布置在监测区域的传感器节点自组织构成，能够对环境实施实时监测，并以多跳的方式向用户返回监测消息[1]。由于无线传感器节点价格低廉，网络能够快速展开，具有抗毁性强的特点，因而在军事侦察，环境监测，农业生产，建筑，工业生产控制上有着广泛的应用前景。
路由协议是无线传感器网络中的一个重要的研究领域。文献[2]对无线传感器网络中的路由协议有比较详细的概述。由于传感器节点存储空间小、通信半径短、计算能力和能量有限的特点[3]，因而在现有的节点硬件基础上实现简单且低能耗的路由协议是无线传感器网络研究的研究重点。文献[4]从减少网络内的消息数量出发，提出了基于最小跳的路由协议。监测区域中，处于不同区域的传感器节点在节点通信半径不变的情况下，以最优的方式（经历的节点数最少），向汇聚节点发送数据。节点只需记录一定数量大小的节点转发集和自身的跳数，就可实现路由，协议实现简单，能够减少信息传输时延和减少网内信息数量，实现了网络的低能量消耗。
然而，基于最小跳的路由协议存在一个明显的不足，即没有考虑到环境及节点自身因素的影响。在建立最小跳数场的过程中，两个相邻节点（跳数不同但在彼此的通信半径之内），都建立起父子关系。而在实际情况下，由于环境影响及节点通信的不对等性，链路上的丢包率很大，节点间的链路通信质量很低。本文从提高网络的包发送成功率出发，提出了一种基
于可靠最小跳数场的路由协议，采用通信链路质量进行评估的方式，在网内建立可靠最小跳数场。为验证算法的可靠性，作者在TinyOS操作系统下，进行了一系列试验，证明了算法的正确性。
2.TinyOS操作系统简介
TinyOS操作系统是加州大学Berkeley分校专门为无线传感器网络开发的一种微型操作系统。它是一个适用于网络化嵌入式系统的编程框架，通过在这个框架内链接一组必要的组件，就能方便地编译出面向特定应用的操作系统，这对于存储资源极为有限的系统来说是非常重要的。针对无线传感器网络节点众多，以及多并发操作的工作方式，该操作系统采用了事件驱动的体系结构。无线传感器网络既具有多样化的上层应用，又强调了系统的节能性要求，为此，系统采用既便于上层应用的开发，也有利于程序快速执行的模块化设计方案。TinyOS操作系统具有以下特点：事件驱动的体系结构;单一的共享栈;无内核，无进程管理，无内存管理和无虚拟内存。
TinyOS操作系统由众多组件构成，如主组件（main）、应用组件（application）、执行组件（actuating）、传感组件（sensing）、通信组件（communication）和硬件抽象组件（hardware abstractions），在此基础上用户只需编写相关的应用层组件即可，便于用户利用已有组件开发新的应用，大大提高开发效率。
3.基于可靠最小跳数场的路由协议
基于可靠最小跳数场的路由协议包括两个方面的内容：⑴在网内建立起可靠最小跳数场;⑵网内节点路由的实现。建立可靠最小跳数场又包含两个方面的内容：⑴相邻节点临时父子关系的确立;⑵临时通信链路的质量评估。
3.1 可靠最小跳数场的建立
3.1.1 相邻节点临时父子关系的确立
协议中的节点拥有唯一的网络标识，并初始化汇聚节点的跳数为0，其余节点的跳数为一极大值。监测区域内网络布置完毕后，汇聚节点向外广播建立可靠最小跳数场的消息M，M包含以下三项内容：
Type; 消息的类型
ID; 节点的网络标识
Hop; 节点当前跳数
网络中的节点收到此类型消息后，启动一个计时器Twait1，在该时间段内，节点持续接收此类消息。在计时器Twait1超时后，节点选取消息源节点中跳数最小的节点将作为临时父节点并存储临时父节点的ID，同时置自身跳数为该最小跳数值加1。对于节点的临时父节点，节点自身称为临时子节点。临时父子节点的关系一旦确定，则称它们之间的一条临时通信链路已经建立起来了。
3.1.2 临时通信链路的质量评估
临时通信链路并不说明对应的两节点能够对等通信，也不能说明该临时通信链路有比较高的通信质量。为此，协议使用质量评估的方法，测量临时通信链路的数据发送成功率，从而达到对临时通信链路的通信质量进行评估的目的。在评估过程中，具有较高数据发送成功率的临时链路将被保留下来，成为固定链路，对应临时父子关系变为正式父子关系;否则该临时链路将被丢弃，对应的临时父子关系亦被取消。
如图1所示，节点1与节点2之间存在一条临时链路，其中节点1为临时父节点，节点2为临时子节点。Twait1超时后，节点2启动计时器T并向节点1发送N个测试消息。消息中包含自身ID，测试消息编号，节点所有临时父节点的ID。临时父节点接收到含有自身ID的测试消息后，启动计时器Twait2，同时对收到的测试消息计数，得到计数值n。Twait2超时后，节点1向节点2发送带有n值的返回消息。节点2将计算出到节点1的数据发送成功率Pt（n与N的比值）。当Pt大于等于阀值P时，它们之间的临时链路将被保留成为固定链路，两者形成正式的父子关系;如果T超时或Pt小于阀值P时该临时，临时通信链路将被取消。临时父节点与临时子节点的执行逻辑图如图1所示：
图1：节点执行逻辑图
临时通信链路质量评估后，新产生的子节点开始生成并向外广播建立可靠最小跳数场的消息。所有已存在父子关系的节点将不再受理该消息，而所有没有父节点的传感器节点在收到该消息后，参与新一轮的建立可靠最小跳数场的操作。当网内所有节点的父子关系确定下来后，可靠最小跳数场的建立也宣告完成。
3.2协议路由的实现
可靠最小跳数场建立起来后，网络中的每个节点都记录了它的所有父节点。当有消息发送时，节点以轮询的方式选择自己的父节点作为下一跳。这主要基于两个方面来考虑：⑴减少瓶颈的产生，当多个节点选择相同父节点作为下一跳时，容易造成拥塞;⑵网络负载平衡的需要，让更多节点参与分担能量消耗，避免单个节点的能量过快消耗而死亡。
4 模拟实验及结果分析
作者在TinyOS操作系统下模拟建立最小跳数场的实验。在阀值P不同的情况下，得到如图2的一个拓扑关系图。如图2所示，节点0是汇聚节点，其余节点在它的通信半径之内，在阀值较小的情况下，节点2、3、4、5的跳数为1，从而得到一个在阀值P为0.4时的拓扑图。而当P为0.6时，节点4、5与汇聚节点的链路不符合要求，此时它们选择了节点2、3为它们的父节点;在P为0.8时，节点2、3选择节点1为它们的父节点。由此可知，在阀值P不同的情况下，网络内的拓扑关系变化明显。
本文也对建场过程中网络的最大跳数以及消息到达网络边缘的时延之间的关系进行了分析和研究。时延的大小与节点跳数、节点对消息的处理时间、所设定的各种计时器有关。
图2：不同阀值下网络拓扑变化图
图 3：时延与跳数的关系图
通过实验，我们得出如图3所示的一个关系图。在Twait2不变的情况下，时延与Twait1的关系，当Twait1减小时，网络的时延可以明显减少。但是通过实验得知，在Twait1很小的情况下，节点可能没有收到具有最小跳节点发出的建立可靠最小跳数场的消息，因而网络内拓扑变化很大，而当Twait1增大到一个定值后，网络的拓扑变化将非常小。
图4：不同阀值下汇聚节点收包情况
图4说明的是在不同的阀值P的情况下，汇聚节点收到的数据包情况。网络中的节点向汇聚节点发送一定数量的数据包。在阀值P增大的情况下，汇聚节点收到了更多的数据包，这也说明了在阀值P增大的情况下，数据包的丢失越少，从而也验证了本算法的正确性。
5. 结论
人们已经在无线传感器网络路由协议方面做了很多卓有成效的工作，并已有许多切实可行的成果。本文在最小跳路由协议的基础上，提出了一种基于可靠最小跳数场的路由协议，着重介绍了可靠最小跳场的建立过程，并对该过程中临时父子关系的确立以及链路评估方法进行详细的叙述。TinyOS操作系统下的实验表明，基于可靠最小跳数场的路由协议在提高数据发送成功率上效果明显。
论文创新点：1. 提出了可靠最小跳数场的概念并对可靠最小跳数场的建立进行了研究。
参考文献
[1] 李建中,李金飞,石胜飞.传感器网络及其数据管理的概念、问题与进展[J].软件学报， 2003,14（10）:1717～1727.
[2] 刘昌鑫,夏春和.无线传感器网络路由协议比较研究[J].微计算机信息,2006,9-1:02-05.
[3] 刘云璐,柴乔林,赵晋.无线传感器网络方向性分区路由算法[J]. 2006;1: 26.
[4] 马祖长,孙怡宁.大规模无线传感器网络的路由协议研究[J].计算机工程与应用,2004:156.
[5] 孙利民,李建中,陈渝,朱红松.无线传感器网络[M]. 清华大学出版社,2005.
