通信人家园

标题: 一种无线传感器网络简单按需路由协议 [查看完整版帖子] [打印本页]

时间: 2005-9-13 11:19

作者: tian7163 标题: 一种无线传感器网络简单按需路由协议

一种无线传感器网络简单按需路由协议
A Simple On-demand Routing Protocol for Wireless Sensor Networks
苗付友,熊焰,卫国

摘要：对被监测对象进行实时监测，在有敏感事件突然发生时，由监测传感器及时向监测者报告被监测对象的相关信息是一类非常重要的无线传感器网络应用。针对这类应用，文章提出了一种无线传感器网络简单按需路由协议：SOD。协议通过动态汇聚节点生成协议使得节点能量消耗尽可能均衡化；利用扩散算法减少路由建立和恢复过程中消息的发送。考虑到此类应用的数据突发性和实时性特点，协议采取紧凑设计的原则，将路由请求消息与最初的突发数据相绑定，在路由建立的同时很好地保证了监测的实时性。仿真和实验表明该协议具有简单性、能量有效性和实时性等特点。

关键词：实时监测；能量有效；按需；实时性

Abstract:Monitoring and reporting to observers immediately when interested events happen are a kind of important application of wireless sensor networks. Therefore, the paper proposes a simple on-demand (SOD) routing protocol, in which the dynamic sink node algorithm improves the uniformity of power consumption, and the diffusion algorithm decreases the traffic of route generation and resumption. Allowing for bursting and real-time data transmission, SOD binds the route request and the first reading up to provide immediate data transmission as well as route generation. Simulation and experiment show that SOD is simple, power-efficient and real-time.

Key words:real-time monitoring; power-efficient; on-demand; real-time

基金项目：中国科学院方向性课题(KGCX2-SW-108)

无线传感器网络[1]是一种由大量具有无线通信功能传感器构成的动态、分布式、自组织网络，其目的是通过协作的方式感知、采集和处理网络覆盖区域中感知对象的信息，并发布给观察者。

定向扩散(DD)[2]是一种以数据为中心的协议，通过在相邻节点间建立以数据为属性的梯度构造路由。但它是一种查询驱动的路由协议，并且基站以洪泛(Flooding)方式发布查询。传闻路由(Rumor Routing)[3]是在监测事件比较少的情况下对DD的一种改进，通过事件代理减少网络流量。基于梯度的路由(GBR)[4]以节点到基站的最小跳数为梯度，提供了随机、能量和数据流3种数据传输方案。能量感知路由(Energy Aware Routing)[5]等协议也都在DD的基础上针对不同的应用环境做了相应的改进。但这些协议都是查询驱动的路由协议，不适合事件驱动的实时监测应用的需求。低能耗自适应分组层次路由(LEACH)[6]是一种层次化协议，它将整个网络分成很多小区域，每个区域有一个头节点，区域中的其他传感器以时分复用方式周期性地在自己的时间片内采集数据，并通过头节点发送到基站。它仅仅适用于每个节点在单位时间内需要发送的数据量基本相同的情况，而不适合突发数据通信。自组织距离矢量按需路由(AODV)[7]协议是一种事件驱动的移动自组网按需路由协议，源节点只在需要向目的节点发送数据时，才主动通过洪泛方式发送路由请求消息，建立到目的节点的路由，然后沿路由发送数据到目的节点。这种路由建立方式非常适合事件驱动的具有突发通信特点监测应用需求。但是它的在路由建立后节点间需要通过周期性的问候消息探测邻居节点状态，维持路由。加上通过洪泛方式发布路由请求，产生了大量的冗余通信；同时协议控制也比较复杂，路由建立过程需要一定的时间，往往不能很好地满足实时应用的需求。因此，该协议不能有效满足实时监测型无线传感器网络应用的需求。

如何建立一种无线传感器网络路由协议，使之不仅符合无线传感器网络节点能量、处理和通信能力有限、动态拓扑的要求，而且能够充分满足实时监测应用的需求已变得至关重要。本文以AODV为基础，借鉴DD及其改进协议的优点，提出了一种简单按需路由协议——SOD。

1 系统结构
图1是一个典型的监测型无线传感器网络系统结构，每个无线传感器除了具有特定的传感功能外，还有一个很小的全球定位系统(GPS)模块用以确定该传感器的位置，该位置信息可以方便实现节点的标识。

每个传感器对处于自己感知范围内的对象进行监测，具体的监测行为分为两种：非实时监测和实时监测。非实时监测是指在一般情况下，传感器定期采集数据，将采集到的数据发送给距离自己最近的汇聚节点，汇聚节点对来自邻近传感器的数据进行分析和处理，然后根据需要将结果发送到基站，基站最终将这一结果发送给观测者；实时监测是指当传感器检测到某一敏感事件突然发生时，依据设定的策略对监测对象进行连续密集监测，并将监测结果根据需要经由汇聚节点进行预处理后立即发送给观测者。实时监测结束后，传感器节点必须通过特殊的消息向基站通告实时监测的结束。
当然，观测者也可以根据需要及时查询各个传感器的监测结果：用户向传感区域内的传感器发送请求，被查询的(一个或多个)传感器向观测者发送监测结果。

2 简单按需路由协议

2.1 协议设计原则
无线传感器网络是一种能量有限的网络，如果网络中的某些节点能量消耗过快，则会使节点在短时间内失效，从而导致有效传感区域变小，影响传感结果。同时在无线传感器网络中，能量比带宽更重要。如何有效减少并平衡网络中各个节点的能量消耗，从而使得网络寿命最大化，是协议设计的关键之一。

如前所述，无线传感器网络节点的处理、存储和通信能力有限，因此，在协议设计时不适宜采用传统计算机网络中的分层设计原则来设计结构性良好但复杂、效率较低的协议。综合考虑无线传感器网络自身特点和应用需求，设计紧凑、高效而简单的路由协议是应遵循的重要原则。

2.2  路由建立
2.2.1  动态汇聚节点生成算法
汇聚节点负责对其临近节点采集的数据进行汇总、分析和预处理。通过汇聚节点的预处理，可以将网络中多个传感器节点采集的数据压缩为一个数据，然后传送给基站，从而有效减少消息的传输次数，节省网络的带宽。但是，由于其特殊功能要求，汇聚节点必须花费比一般传感器节点更多的能量与邻近节点进行通信、处理收集到的数据。因此，它必然消耗更多的能量。

为了保证网络中各个节点能量消耗的相对均衡性，需要使得充当汇聚节点的节点是可变的，任何节点都有机会担当汇聚节点并且机会均等。为此本文提出了一种基于现有能量的汇聚节点动态生成算法。算法在(0，1)之间选取能量参考值r、一个随机数p和一个百分数q。具体算法步骤如下：

(1)每个节点读取以百分比表示的自身当前能量值e。
(2)对于任何一个节点，譬如N，如果它的e >r，则已概率p 向邻近节点发送通告消息，声明自己是一个汇聚节点，同时设定它的汇聚节点就是其自身。

(3)邻居节点如果此时还没有汇聚节点，就将N 设置为它的汇聚节点。如果已经有汇聚节点，则忽略此通告。

(4)将能量参考值调整为r ×q。

所有节点周期性地执行此生成算法。算法具体描述如下：
sink-set (float r, float p, float q, long
mySinknode)
{
Long id;       //代表一个节点的标识；
mySinknode=-1; //初始化汇聚节点设置；
e =read-energy();    //读取当前能量值
            (百分数表示)；
s =random();    //获取一个随机数;
If(e >r & s <p)
{
mySinknode=myID;
send-notification(id);  //通告消息中包含
            发送节点的ID号
}
Receive-notification(id);  //接收邻居节
                        点通告，其中
               包含通告节
            点的ID号；
If (mysinknode==-1)
  mySinknode=id；    //设置汇聚节点
r =r *q ;                //将能量参考值减小为
            原来的q 倍，q <1
}

2.2.2  路由生成
在源节点获取了被监测对象的数据后，如果没有该节点到基站的路由，就要确定一条从源节点到基站的路由。

对于非实时监测而言，节点对被监测对象进行周期性的监测，各个节点将监测数据首先汇集到汇聚节点。汇聚节点对数据进行融合后建立一条从自身到基站的路由，并将数据沿此路由发送给基站；对于实时监测而言，如果源节点突然监测到预定事件，需要立即将监测数据发往基站，在没有从该节点到基站的路由时，会建立一条从该节点到基站的路由(未必包含源节点的汇聚节点)，然后将数据沿建立的路由发送到基站。
如前所述，每间隔一定的时间，就要对一个节点的汇聚节点进行重新生成。在非实时监测情况下，每次汇聚节点重新生成，就要重新确定路由。通过路由的重新生成使得源节点和基站之间节点的能量均衡消耗，从而有利于传感器网络节点寿命的最大化。路由的重新生成有可能导致极个别的数据丢失，但在传感器网络中这是允许和可以接受的。在实时监测情况下一般不因汇聚节点的改变进行路由的重新生成。

能量是无线传感器网络中的稀缺资源和协议设计中需要考虑的非常重要的因素。在建立传感器网络路由时，不仅要考虑传感器节点之间连接的带宽，更要考虑传感器节点的能量。为此，SOD协议为每个节点增设一个能量参数E，用以反映节点现存能量。
各节点(包括基站)通过其位置信息进行标识。为了建立源节点和基站之间的路由，源节点需要知道基站的具体位置，对于静止基站而言，基站可以通过广播方式使各节点一次性获得其位置信息；对定期移动的基站而言，可以在每次位置改变后广播其当前的位置信息。源节点根据基站的位置信息通过定向扩散方式将路由请求发送到基站，基站在收到源节点请求后选取一条最优路径作为从源到基站的路由。

衡量一条链路的质量需要综合考虑多种因素，如带宽、时延、节点能量等。为简单起见，本文只考虑带宽和能量两个因素。假设b 代表链路带宽，e 代表节点的现存能量。一条由相邻两节点构成的链路的质量可以用链路值Q 来表示：
Q = w1×b+w2×e             (1)

其中w1、w2分别表示带宽和能量的权重。对于由两个相邻节点，比如A、B构成的链路，b表示链路AB的带宽，e表示下游节点B的现有能量。对于一条路由而言，其质量可以用构成该路由的各段链路的质量之和表示。路由建立过程如下：

(1)源节点根据基站位置信息向基站方向一次一跳地扩散路由请求，在路由请求消息中包含有源节点坐标、本节点坐标、基站坐标、消息编号、扩散角、链路值和以及实时数据等。本节点坐标指发送或转发该消息的节点的坐标；链路值和是指从源节点开始到本节点之间各链路值之和，初始值为0；实时数据是可选的，仅在实时监测中才出现。

(2)在路由请求消息扩散方向上，下游节点收到上游节点的路由请求后，通过自身坐标和上游节点坐标计算判定是否满足扩散角的要求。如果满足，则记录上游节点的位置信息，并对链路质量值进行累加，修改路由请求消息的本节点坐标和链路值和字段，其他字段保持不变，继续向其邻近下游节点扩散路由请求。否则，将路由请求消息丢弃。对于邻近下游节点，如果收到相同编号的消息，则简单地将后来的消息丢弃。

(3)假设节点间的所有链路均为双向链路，当路由请求消息最终到达基站后，基站选择具有最好质量的链路，向其上游节点发送响应消息，直到响应消息到达源节点。这样源节点就获得了到基站的路由。

(4)对于一条路由上的中间节点，在收到响应消息后，建立一个关于该路由的表项，其中包括路由的源节点、目的节点(基站)、相邻上游节点、邻近下游节点、路由标识(即路由请求的消息编号)。

SOD协议中，路由请求消息格式如图2所示。路由请求消息按一定的方向进行扩散，扩散的方向由扩散角决定。

对于一个扩散路由请求消息的节点而言，扩散角是指扩散边界与过该节点指向基站方向的射线之间的夹角，路由请求扩散角如图3所示。其邻近下游节点包含于夹角内或则位于夹角的一条射线上。

假设节点(0,2)根据基站坐标向(2,3)等节点方向扩散路由请求消息，∠ABD为(0,2)的扩散范围，BA和BD为扩散边界，∠ABC为(0,2)的扩散角。∠CBD=∠ABC。显然，当扩散角等于90°时，路由请求消息在一半的空间进行传播；当扩散角等于180°时，路由请求消息向所有邻近节点广播。

上游扩散节点按一定的方向向邻近下游节点扩散路由请求消息，下游节点计算过扩散节点和自身的射线与扩散节点指向基站方向的射线构成的夹角是否小于或等于路由请求消息中指定的扩散角。如果是，则接收、处理并继续扩散路由请求，否则丢弃。
在图4中，假设扩散节点坐标为(a,b)，邻近下游节点的坐标为(c,d)，基站坐标为(x b,y b)，过(c,d)的直线与过(a,b)、(x b,y b)的直线垂直相交于点(x,y)，扩散角为α，则当0≤α<90°时，邻近下游节点需要解方程组求x和y：
(y-b)/(x-a)= (y b -b)/(x b -a)
(c-a)2+(d-b)2=(x-a)2+(y-b)2+(c-x)2+(d-y)2

并判断不等式组：

或者

是否成立。如果成立则下游节点接收、处理并继续扩散路由请求消息；否则将消息丢弃。

2.3  路由维护
路由建立之后，为了在维持每条路由的信息的同时减少对节点存储空间的需求，每个传感器节点仅对经过本节点的当前路由信息进行缓存。路由信息仅在节点上保存较短的时间，如果现存的路由信息得不到及时刷新，则该路由信息将会被置为无效，并最终被清除。为了维护现存的路由，在一条路径上如果当前路由信息仍然有效，则每当有新的数据发送后，当前的路由信息就被及时刷新。这样可以保证对于突发通信可以实现连续的数据传输。

2.4  路由恢复
在实时监测中，传感器节点需要在短时间内连续向基站发送数据，因此希望在一次路由建立成功后，沿该路由连续发送数据。但是中间节点会因为电源耗尽或受到物理损毁后失效，从而导致路由中断，为了尽快恢复节点间的通信能力，需要对路由进行修复。

为了能够及时发现损坏的路由，路由协议需要具备有效的路由中断的发现机制。传统的方法是使邻近节点之间定期发送Hello消息，从而探测邻近节点的状态，确定路由断点，从而修复路由。但是周期性的Hello消息会在网络中产生大量的流量，这将导致带宽和能量有限、通信不可靠的无线传感器网络在消耗大量能量的同时，性能急剧恶化。为了减少网络中的流量，节省节点能量，必须以尽可能少的消息恢复源节点和基站之间的路由。

对于建立起来的一条路由，在实时监测结束前，如果有节点损坏必然会导致基站节点在很长时间内无法接收到沿此路由发来的数据，从而导致此路由项失效。基站在路由失效后立即沿反向扩散路由请求消息。在路由请求消息中，以基站为起始点，以原路由的源节点为目的节点，其他字段保持不变。本文假设所有链路都是双向的，因此通过由基站到源节点的反向路由扩散，可以立即建立一条新的由源节点到基站的路由。

3 SOD协议仿真和实验结果
由以上可以看出，该无线传感器路由协议具有简单性、能量有效和实时性等特点。

(1)简单性
无线传感器网络节点无论在处理、存储还是通信能力方面，都是比较弱的。因此，在协议设计时应该尽可能地使其简化，以适应节点自身的要求。该协议相对于AODV协议而言，去除了周期性的Hello消息，使得大部分节点在不传输数据时(包括为其他节点转发数据)基本不需要主动发送消息。在路由恢复问题上，考虑到无线网络路由修复的复杂性，不采用传统的路由断点修补方法，而是通过反向路由扩散来恢复源节点和基站之间的路由。这样可以简化协议的设计，使节点功能更加简单。

图5(a)是在SOD扩散角为45°时，假定节点均匀分布在一个圆形区域中，由位于圆心的节点向位于区域边界上的基站发送路由请求，建立路由过程中SOD和AODV需要处理的平均消息数对比的仿真结果。

(2)能量有效
能量有效不仅仅指低能耗，更重要的是反映在单位能量发送的有效数据量上。为了减少能量盲目消耗，源节点在路由建立过程中采用扩散方式向基站发送路由请求消息。扩散时，路由按一定的扩散角度向基站传递，只有满足扩散角要求的中间节点才会转发路由请求消息。相对于广播方式(或条件广播方式)而言，避免了消息传播的盲目性。适当选择扩散角可以大大减少路由建立过程所需的消息量。同时由于本协议不采用周期性Hello消息探测邻居节点的状态，在很大程度上减少了节点的辅助消息发送量，节省了节点的能量。

为了避免汇聚节点因频繁地收发消息而使能量很快耗尽，导致节点失效，本协议引入了动态汇聚节点，它可以保证充当汇聚节点的传感器总是由能量相对充足的节点轮流担当。从而可以基本保证节点能量的均衡消耗，提高传感器网络的寿命。这一点可以从图5(b)中可以得到验证，该图反映了在与图5(a)相同的假设下，假定r、p、q值分别取0.9、0.5、0.8，在不同时刻分别采用SOD和AODV协议传感器网络节点失效情况下的仿真结果。

(3)实时性
为了满足实时监测应用的需求，保证监测数据能够及时发送到基站和用户，SOD协议在路由建立过程中，将数据和路由请求消息绑定，以扩散方式在路由建立过程中将最先监测到的数据发送给基站，从而保证了传感器网络对突发事件的及时响应。路由建立后，后继数据可以沿已经建立的路由将数据快速发送给基站，而不需要在每次发送数据前临时寻找到基站的路径。图5(c)是假定路由带宽为500 kb/s，分组长度为15字节时，不同路由长度下分别采用SOD和AODV协议传感器网络对突发事件响应延迟的仿真结果。

本文所设计的SOD协议已在中科院上海微系统信息研究所研发的一个典型监测型无线传感器网络上进行了实验运行，实验运行结果表明：SOD协议简单、高效、节能和实时，在中科院方向性课题的中期检查中受到了军方以及中科院领导和专家的一致好评。

4 结束语
实时监测是无线传感器网络的一类非常重要的应用，它要求传感器节点在检测到突发事件时可以主动建立到基站的路由，并将数据及时发送到基站。本文针对这一类需求，考虑到无线传感器网络的特点，在AODV协议基础上提出并具体实现了一种无线传感器网络简单按需路由协议。仿真和实验结果表明该协议具有简单性、能量有效性以及实时性，可以满足无线传感器网络实时监测应用的需求。该协议目前还不太完善，旨在改进协议服务质量的进一步实验和测试正在进行中。

5 参考文献
[1] Rai Lav, Kotapati Kameswari. A Survey on Sensor Network [DB/OL]. http://www.cse.ohio-state.edu/~duttap/echelon/readings/rai03survey.pdf.
[2] Chalermek Intanagonwiwat, Ramesh Govindan, Deborah Estrin. Directed Diffusion for Wireless Sensor Networking [J]. IEEE/ACM Transactions on Networking, 2003,11(1): 2—16  .
[3] David Braginsky, Deborah Estrin. Rumor Routing Algorithm for Sensor Networks [C]. First Workshop on Sensor Networks and Applications, Atlanta, GA, 2002(10).
[4] Jabed Faruque, Ahmed Helmy. Gradient-Based Routing in Sensor Networks [DB/OL]. http://www.sigmobile.org/mobicom/2003/posters/4-Faruque.pdf.
[5] Shah R C, Rabaey J. Energy Aware Routing for Low Energy Ad hoc Sensor Networks [C]. IEEE Wireless Communications and Networking Conference, 2002(3).
[6] Heinzelman W B, Chandrakasan P, Balakrishnan H. An Application-specific Protocol Architecture for Wireless Microsensor Networks [J]. IEEE Transactions on Wireless Communications, 2002,1(4): 660—670.
[7] Perkins C. Ad hoc On-Demand Distance Vector (AODV) Routing [S]. RFC3561, 2003(7).

收稿日期：2005-05-16

作者简介：
苗付友，中国科学技术大学信息科学技术学院讲师，在读博士，研究方向为移动计算、密码学、移动网络等。

熊焰，中国科学技术大学信息科学技术学院教授、博导，研究方向为分布式计算、信息安全、移动计算、移动网络等。

卫国，中国科学技术大学信息科学技术学院执行院长，教授、博士生导师，多媒体计算与通信教育部微软重点实验室主任，国家“863”计划通信技术主题未来移动通信系统总体组成员。研究方向为无线通信、通信网络和信号处理。

通信人家园 (https://www.txrjy.com/)