无线传感器网络节点调度技术研究

邱树伟

(汕头职业技术学院,汕头 515078)

无线传感器网络节点调度技术研究

邱树伟

(汕头职业技术学院,汕头 515078)

探讨了无线传感器网络的节点硬件体系结构和网络体系结构;论证了无线传感器网络节点调度的必要性和价值;从网络覆盖度及连通性等角度分析了若干较有代表性的节点调度算法.

无线传感器网络;传感器节点;节点调度;网络覆盖;连通

0 引 言

无线传感器网络(Wireless Sensor Networks,简称WSNs)由部署在监测区域内的一组静态微型的传感器节点和一个固定的基站节点组成,是一个任务型的信息采集平台.传感器节点通过人工配置、飞行器撒播或火箭弹射等方式部署在室内/外,通过无线通信方式形成一个多跳的自组织网络系统,协作地实时感知、采集和处理感知对象的信息,并发送给观察者.无线传感器网络在工业、军事、农林业、海洋、医疗、环境等领域应用非常广泛.

但是,由于支撑传感器节点正常工作的能量十分有限,加上大部分监测任务都要求网络有较长的生命期,因此,如何提高节点能量的使用效率,最大化网络的生命期,是设计此类网络的一个基本挑战.网络的生命期通常被定义为最先因电池能量耗尽而失效的传感器节点的生命期[1].

为了延长无线传感器网络的生命期,学者们长期从事该类网络的节能研究,并从硬件和软件两方面提出了多种有效的节能方法.本文着重讨论了节点调度技术,给出全局的节能解决方案.

1 无线传感器网络概述

1.1 节点体系结构

通用传感器节点主要由传感器模块、处理器模块、通信模块和能量供应模块等四个部分组成.传感器模块与具体应用密切相关,主要包括采集物理信息的传感器和模数转换(AC/DC)部件.其它三个模块相对独立,其中,处理器模块负责对节点进行控制和管理、存储和处理本身采集的数据以及其它节点发来的数据;通信模块负责与其它节点进行信息交换;能量供应模块提供节点运行所需的能量.部分节点还包括定位系统和执行模块等[2][3].如图1所示.

图1 传感器节点体系结构

1.2 网络体系结构

无线传感器网络包括传感器节点、汇聚节点和管理节点等.传感器节点监测到数据后,通过无线多跳的通信方式将数据传送到汇聚节点,汇聚节点再通过因特网、移动通信网或卫星等方式,与管理节点互联,最终由远程的观察者来处理收集到的数据.同时,观察者也可以通过管理节点对网络进行配置、管理以及部署新的监测任务等.传感器节点不仅具备终端和路由双重功能,而且还能进行数据的存储和处理等任务,节点相互之间是一种协同的关系.

如果网络规模较大,则可以采用聚类分层的管理模式.该模式将网络划分为若干个簇,每个簇由一个簇头节点和若干个成员节点组成.这些簇头节点互联形成高一级的网络.在高一级的网络中,又可以分簇,形成更高一级的网络[4].如图2所示.

图2 无线传感器网络体系结构

1.3 几个典型的系统

目前,比较著名的无线传感器网络系统有弗吉尼亚大学的VigiNet,哈佛大学的Motelab以及加利福尼亚大学伯克利分校Trio等[5].由于不同系统有不同的应用领域和需求,因此它们的规模、部署时长、部署方式以及电源类型等有所不同.如表1所示.

表1 典型的无线传感器网络系统

2 无线传感器网络节点调度探讨

2.1 节点状态转换

传感器节点有四种状态:

工作状态所有部件都处于工作状态,节点收集环境数据、收发消息以及对数据与消息进行处理.

感知状态感知部件和计算部件处于工作状态,通信部件关闭,节点不能收发消息.

通信状态通信部件和计算部件处于工作状态,关闭感知部件,节点不能收集环境数据.

睡眠状态所有部件都被关闭,但节点可以通过定时器或其他方法激活.

传感器节点状态转换如图3所示.图中,四种节点状态的能耗从低到高的顺序是:睡眠状态、感知状态、通信状态、工作状态[2].

为简化本文的讨论,将每个节点的状态仅分为工作和休眠两种.当节点处于工作状态时同时承担感知和通信工作,而当节点处于休眠状态时,节点不承担任何工作,仅留较低的能量备用.

图3 传感器节点状态转换图

2.2 节点调度的必要性和价值论证

在无线传感器网络中,节点是体积微小的嵌入式设备,一般依靠电池供电,因而对能源的限制很大,加上节点的分布数量较多,且有些监测环境非常恶劣,人们难以接近,因此要对所有节点可持续的补充能源非常困难.同时,现时传感器电池供应技术的发展还不能够让节点在没被替换或回收充电的情况下长时间工作.近年来,研究者积极研发先进的节能方法,主要包括:节能传感器硬件体系结构的设计、优化网络拓扑管理、改善路由算法、调节节点的发射功率等等.但是,以上各种方法仍无法明显降低系统的能耗.

较合理的节能方法是节点调度技术,即在保证网络覆盖范围的基础上,在一定的时空范围内合理的对节点进行调度,选择一部分节点进入工作状态,而另一部分节点进入睡眠状态并在合适的时候被唤醒,节点进行切换的同时,其工作部件也进行切换[6].

采用节点调度技术的原因有以下两点[2]:

(1)传感器节点收发器的状态有:传输、接收、空闲和休眠四种.一般节点功耗比例为:传输状态为0.38～0.7 W,接收状态为 0.36 W,空闲状态为0.34 W,休眠状态为0.03 W,其中完全用于感知任务的能耗为0.02 W.研究表明空闲状态的能耗同传输和接收状态的能耗几乎相等,由以上分析得知,为了节省能耗,应尽量增加休眠节点的数量和节点休眠时间.

(2)为了提高监测质量,观察者通常将传感器节点大规模、高密度地部署在监测区内,从而导致节点通信半径内的邻居节点间有较高的重叠感知区域,并且邻居节点产生的数据信号有较大的相关性(即对同一事件有多个节点对此产生相同的数据),观察者并不需要来自所有节点的数据,而且当它们与基站通信时将不可避免地出现数据冗余、信道干扰或网络拥塞等问题,造成不必要的能耗.因此,在不影响网络基本性能的前提下,可以利用调度技术来协调节点的状态,避免以上问题的出现.

由此可见,节点调度技术的研发不仅很有必要,而且很有价值,是无线传感器网络设计的核心问题之一,它决定了系统是否能够满足日益增长的用户需求.

2.3 节点调度模型设计

为了实现对传感器节点的有效调度,设计了节点调度模型.该模型将整个调度过程分为若干个相等的周期,在每个周期开始时,采用一定的策略来决定节点处于工作状态还是休眠状态.

如图4所示,假设每个节点的工作过程分为N轮(N为正整数且N≥1),每轮周期为T,在每一轮开始的时候,按照特定的算法进行节点工作/休眠调度,使部分节点工作,其他的节点休眠,整个网络的监测工作仅由处于工作状态的节点来完成[4].

图4 节点调度模型

3 经典节点调度算法分析

3.1 基于网络覆盖的节点调度算法

根据监测目标的不同,网络覆盖问题可分为三类,即点覆盖、区域覆盖和栅栏覆盖.限于篇幅,笔者重点讨论点覆盖及区域覆盖问题.

3.1.1 基于点覆盖的节点调度算法

点覆盖是指在一些特定应用中,需要对某些离散的目标点进行监测而在其附近随机部署大量传感器节点.为了延长网络生命期,将目标点附近的节点分成若干互不相交的节点集,每个节点集都能够实现对若干个目标点的有效覆盖.通过周期性地调度节点集的工作状态,就能够延长网络生命期.

文献[7]提出了离散点覆盖问题:给定网络中一些需要监测的离散目标点,通过调度节点使得任意时刻随机分布的节点能够覆盖到所有目标点,并且最大化网络的持续工作时间.将所有感知节点划分为互不相交的覆盖集.显然这样的覆盖集越多,网络生命期就越长.这就是基于混合整数规划的启发式算法.

在此基础上,Cardei等指出,设计互不相交的覆盖集并不一定是最优的,某些感知节点可以属于多个覆盖集.如图5所示,感知节点与目标节点的覆盖关系为:S1={O1,O3},S2={O1,O2},S3={O1,O2,O3},S4={O2,O3}.假定感知节点的初始能量相同且每个节点最多可以持续工作1T(T=1个单位时间),根据以上讨论,得出两种情况:(1)一个可能最大数量互不相交的覆盖集S={{S1,S2},{S3,S4}},即网络的最大工作时间为2T;(2)当节点可以属于多个不同的覆盖集时,一个可能的覆盖集为S={{S1,S2},{S2,S4},{S1,S4},{S3}},其中令集合{S1,S2}工作0.5T,令集合{S2,S4}工作0.5T,令集合{S1,S4}工作0.5T,令集合{S3}工作1T,则网络的最大工作时间为2.5T.显然,第二种情况可以更有效地延长网络生命期.

图5 点覆盖示意图

3.1.2 基于区域覆盖的节点调度算法

区域覆盖可分为全局覆盖和局部覆盖.全局覆盖要求工作节点的传感范围完全覆盖整个区域(即区域中的任意一点能够至少被一个工作节点覆盖).局部覆盖仅要求满足一定的网络覆盖度即可.

比较典型的算法是 RTSS(Reference Timebased Scheduling Scheme),该算法能够根据不同监测区域的服务要求而动态调整网络覆盖度[8],它将监测区域分为若干网格,通过保证每个网格的覆盖实现区域的局部/全局覆盖.

算法分为两个执行阶段:传感阶段和初始化阶段.在传感阶段,将时间分为等长的轮,各节点之间的时间轮是同步的.在初始化阶段,节点首先确定自身的绝对或相对位置,并与邻居节点实现时间同步;之后每个节点在[0,t](t为时间轮的长度)之间产生一个随机的时间基准,并广播该时间基准信息和节点位置信息.一段时间之后,每个节点都能得到邻居节点的时间基准和位置信息,然后根据各自感知区域内每个网格的覆盖情况来决定自身的调度.由于每个节点都对应多个网格,所以会得到多个不同的调度结果,最后进行节点调度融合,得到最终的调度结果.如果增加每个节点的调度长度,则各节点之间的调度会相互重合,网格的覆盖度也会得到提高,这样就实现了对不同监测区域的区分服务.为了提高健壮性,该算法还可以支持对指定位置的多重覆盖.

3.2 基于网络连通的节点调度算法

对于无线传感器网络而言,要真正完成监测任务,除了要保证网络对目标区域的有效覆盖度,还必须保证网络的连通.只有这样才能使节点将采集的数据传送到汇聚节点,并最终传送给观察者.在某些应用中,一定程度的有效覆盖面积的丢失是可以容忍的,但是网络如果不连通,节点采集的数据将毫无价值.因此,许多应用中要以保证网络连通为基础.

具有代表性的是GAF(Geographic Adaptive Fidelity)算法.它是一种依据节点的地理位置进行分簇,并对各簇内的节点选择性地进行休眠的路由算法[9].GAF算法中,每个节点需要知道自身的位置信息并利用该信息将整个区域划分为若干个大小相同的正方形网格,网格的划分恰好使得相邻网格内的任意对节点均能一跳可达(直接通信),从而在任意时刻每个网格中只有一个节点参与数据的传输而网格内其它节点进入休眠以节省能量.如图6所示,当每个网格的大小为R2时,若要保证网络的连通则每个节点的通信半径至少为R .为平衡节点间的能耗,同一网格内的节点需要轮流进行数据的转发.GAF算法所提出的节点状态转换机制和按虚拟单元格进行分簇的思想非常有价值.

图6 GAF算法示意图

3.3 基于网络覆盖和连通的节点调度算法

网络覆盖性与连通性是传感器网络的两个必备条件,节点必须同时满足连通和覆盖这两个条件,无线传感器网络才有实际意义.因此,基于网络覆盖和连通的节点调度算法也是众多研究者关注的热点.

OGDC(Optimal Geographical Density Control)算法是一种分布式、局部化的最优地理位置密度控制算法[10].在该算法中,任意时刻节点只能是以下三种状态之一:UNDECIDED、ON或OFF状态.网络生存时间被划分为若干个时间段,在每个时段的开始阶段,网络中一个或多个节点首先作为工作节点,其它节点的状态置为 UNDECIDED.经过一段随机退避时间后,初始工作节点开始向外广播POWERON消息,该POWERON消息中包含了发送节点的位置信息以及所期望的下一个工作节点理论上所处的方向信息,该方向由POWERON消息的发送节点随机选择.通过随机选择每个时间段开始阶段的初始工作节点,可以确保网络中各节点的均匀能量消耗.同时随机退避机制有利于避免信道冲突.通过消息的交换,每个节点都会得到邻居节点位置的列表信息.

OGDC算法规定了节点收到POWERON消息后所应该采取的动作.如果发现邻居节点能够覆盖自身的覆盖区域,则该节点成为休眠节点,状态置为OFF.否则,如果周围已有两个工作节点且自身与这两个工作节点的距离最接近于最佳距离(即与这两个节点的距离均为3Rs)的话,该节点也将成为工作节点,状态置为ON.据此,每个节点设定自己的状态为ON或者OFF状态,然后节点在该时间段内状态保持不变,直到下一个时间段开始.节点重复上述过程,重新决定状态.实践表明,OGDC算法在监测区域的覆盖比率、工作节点的数量以及网络生存时间等方面性能优越.

由本节的讨论可以看出,研究者从不同的角度出发提出了众多的节点调度算法,本文为了突出讨论的代表性,只分析了部分经典的算法.更详细的关于节点调度算法的内容请参考文献[6].

4 结束语

无线传感器网络将逻辑上的信息世界与真实世界融合在一起,极大地提高了人们认识和改造世界的能力[11].它扩展了计算机网络的功能,广泛深入地影响着人类社会各领域的发展,有着重要的应用前景和空间.因此,研究支撑其运行的节能节点调度技术显得格外重要.学者们在提出各种软节能技术的同时,硬节能技术也要同步发展,比如电池供应技术、能源的利用和再生、节能传感器硬件体系结构设计以及智能技术等方面都需要更深入研究.

虽然无线传感器网络领域已取得丰硕的成果,但仍存在若干关键问题需要进一步解决:①感知精确度问题;②网络动态自适应能力问题;③服务质量支持问题等[12].我们相信,通过科研工作者们的不断努力,尚存的难题将得到解决,无线传感器网络将对社会的发展做出更大贡献.

[1]唐 伟,郭 伟.无线传感器网络中的最大生命期基因路由算法[J].软件学报,2010,21(7):1646-1656.

[2]王 娟.无线传感器网络节点调度算法的研究[D].西安:西安电子科技大学,2009,1.

[3]崔 莉,刘 强,李 栋.物联网系统及核心设备[J].中国计算机学会通讯,2010,6(4):18-22.

[4]赵 霁.基于人工免疫算法的无线传感器网络调度[D].成都:电子科技大学,2009,5.

[5]刘云浩.绿野千传.突破自组织传感网大规模应用壁垒[J].中国计算机学会通讯,2010,6(4):35-37.

[6]胡湘华,杨学军.传感网节点调度方法综述[J].计算机工程与科学,2008,30(3):93-96、129.

[7]Cardei M,Du D Z.Improving Wireless Sensor Network Lifetime through Power Aware Organization[J].Wireless Networks,2005,11(3):333-340.

[8]T yan,T He,J Stankovic.Differentiated Surveillance for Sensor Networks[C].In:Proc of ACM SENSYS＇03,New York:ACM Press,2003:51-62.

[9]赵学鹏,邹传云.无线传感器网络GAF算法的性能分析与仿真[J].计算机仿真,2008,25,(11):154-156.

[10]Xing Guo-liang,Wang Xiao-rui,Zhang Yuan-fang,et al.Integrated Coverage and Connectivity Configuration for Energy Conservation in Sensor Networks[J].ACM Trans on Sensor Networks,2005,1(1):36-72.

[11]任 彦,张思东,张宏科.无线传感器网络中覆盖控制理论与算法[J].软件学报,2006,17(3):422-433.

[12]康 波,柯 欣,孙利民,任 雍.无线传感器网络中的调度算法研究[J].计算机科学,2008,35(2):47-51.

Research on Node Scheduling Technology for Wireless Sensor Networks

QIU Shu-wei
(Shantou Polytechnic,Shantou 515078,China)

Node hardware architecture and network architecture of wireless sensor networks are discussed in this paper.The necessity and value of node scheduling technology for wireless sensor networks are revealed.Several node scheduling algorithm of the most representative from the network coverage and connectivity point of view are analyzed.

wireless sensor networks;sensor nodes;node scheduling;network coverage;connectivity

TP212

A

1671-119X(2011)01-0059-05

2010-10-15

邱树伟(1979-),男,硕士,讲师,研究方向:网络与分布计算、人工智能.

book=97,ebook=97