无线传感器网络中的拓扑控制

作者简介:卞永钊(1976 ),男,博士研究生,主要研究方向为无线传感器网络的网络管理、拓扑控制(b i an _yz @s i a .cn);于海斌(19 ),男,研

究员,博导,主要研究方向为智能控制系统、网络化技术等;曾鹏(1976 ),男,研究员,硕导,主要研究方向为协议工程、无线传感器网络.

无线传感器网络中的拓扑控制

*

卞永钊1,2

,于海斌1

,曾 鹏

1

(1.中国科学院沈阳自动化所,沈阳110016;2.中国科学院研究生院,北京100039)

摘 要:拓扑控制是无线传感器网络研究中的核心问题之一,它对于提高网络生存周期、降低通信干扰、提高

MAC 和路由协议、保证网络连通和覆盖质量、提高网络服务等具有重要意义。阐述了拓扑控制技术研究的进展,首先描述了拓扑控制及其方法、评价标准,然后从平面网络、层次型网络拓扑控制介绍了一些代表性的研究工作,并指出了这些工作存在的不足,最后总结了研究现状中存在的问题以及拓扑控制研究的发展方向。关键词:无线传感器网络;拓扑控制;功率控制;支配集;成簇算法

中图分类号:TP309 文献标志码:A 文章编号:1001 3695(2008)10 3128 06

Topol ogy contro l for w i reless sensor net w orks

B I AN Y ong zhao 1,2,YU H a i b i n 1,ZENG Peng 1

(1.Shenyang In stit u t e of Au to ma tion,Ch inese Acad e my o f S ciences ,Sh e nyang 110016,China;2.G raduate S c hool ,Chinese A c ade my of S cie nces ,B eijing 100039,China )

Abstract :Topology control i s one of t he f unda m ental proble m s i n w ireless sensor net works .It i s of great m i portance for pro

longi ng net w ork lifetm i e ,reduci ng rad i o i nterference ,increasi ng the efficiency ofMAC and routi ng protocol s ,ensure the qua lit y of connecti ng and coverage ,increasi ng the net work servi ces and so on .Th i s paper descri bed the t opology control prob le m and its m ethods ,criteri on of estm i ation firstly ,t hen m ade an introduction of representative research efforts ,from t wo aspects ,ho m ogeneous and non ho m ogeneous net w orks respectivel y ,and pointed out the defects of those efforts .Fi nally ,su mm ari zed existi ng proble m s ,open i ss ues and research trends .Key words :w irel ss sensor net w orks(W S N );topol ogy contro;l trans m i t po w er con tro;l do m i nati ng se;t cl usteri ng al gorit h m

0 引言

无线传感器网络是一种新兴的网络,一般具有大规模、自组织、随机部署、环境复杂、传感器节点资源有限、网络拓扑经常发生变化的特点[1]。无线传感器网络的这些特点决定了拓扑控制在无线传感器网络研究中的重要作用,同时这些特点也使得它的拓扑控制研究具有挑战性。首先,拓扑控制是一种重要的节能技术;其次,拓扑控制保证网络覆盖的质量和连通质量;另外拓扑控制能够降低通信干扰、提高M AC 协议和路由协议的效率,为数据融合提供拓扑基础;拓扑控制能够提高网络的容量、可靠性、可扩展性等其他性能。总之拓扑控制对网络性能具有重大的影响,因而对它研究具有十分重要的意义。

本文提到的拓扑控制是指控制网络拓扑结构,网络拓扑结构由活动节点的子集和进行直接通信的活动链路决定。拓扑控制算法以图G =(V,E )代表网络。其中:V 是网络中所有节点的集合,当且仅当v 1与v 2之间有直接通信时,边(v 1,v 2) E V 2存在,将它变换到图T =(V T ,E T ),可以得到V T V,E T E 。

图G 代表原始网络,为了能从图G 计算出变化后的图T,拓扑控制算法有以下几种常用的方法:

a)减少活动节点的数量(V T V )。例如可以利用网络的冗余部署特性,周期性地关闭剩余能量较少的节点,激活其他

节点来代替被关闭的节点。

b)可以控制活动链路集或邻节点集。如果无须使用网络中的所有链路,那么可以剔除一些链路,将通信在重要链路中。

如果网络是同构的,即平面网络,控制节点的邻节点集只需不与某些节点通信即可。在无线传感器网络中选择邻节点最适合的方法就是控制节点的信号发射范围,也就是采用功率控制或者采用自适应的功率调整方法。图1和2给出了原始的网络拓扑和功率控制之后的拓扑结构。

拓扑控制也可以采用第二种方法,即重新安排活动链路或邻节点,形成一个层次型的网络拓扑结构,并假设处于上层的节点具有特殊的功能。

如选择某些节点作为骨干节点,只保持骨干节点之间的连接,其他节点的连接都指向骨干节点,所以骨干节点就形成了一个支配集(dom ina ti ng set):子集D V,V 中的所有节点要么

第25卷第10期2008年10月 计算机应用研究Application R esearc h of C o m puters Vo.l 25N o .10

O c.t 2008

在D 中,要么是节点d D 的单跳邻节点(!v V:v D ∀d D:(v ,d) E )。支配集节点之间相互通信以及支配集与其邻节点之间可以进行通信,这样能够保证网络的连通性。

另一种与支配集相关但略有不同的思想就是将网络划分成簇(c l uste rs)。簇是包括原始网络中所有节点的节点集的子集,每个簇中有簇首(cluster heads),它是簇的代表,每个簇内的节点距离簇首一般只有一跳。如果使簇的数量最小,就相当于寻找最大集(i ndependent se t)(存在子集C V,使!v V -C:∀c C:(v ,c) E,且C 中没有两个节点在边E -!c 1,c 2 C:(c 1,c 2)

E 上相交)。在这样的分簇型的网络中,簇首负责与簇内节点之间的通信,同时簇间连接也是通过簇首的通信来实现的,这样就可以保证整个网络的连通性。图3和4给出了采用骨干节点控

制和簇结构控制之后的拓扑结构。

1 拓扑控制的评价标准

拓扑控制要保证在一定的网络连通质量和覆盖质量的前提下,一般以延长网络生存周期为主要目标,兼顾通信干扰、网络延迟、负载均衡、可靠性、可扩展性等其他性能,形成一个优化的拓扑结构。无线传感器网络是与应用相关的,不同的应用其设计目标不尽相同,采用的拓扑结构控制手段也不尽相同。以下提出一般拓扑控制算法的几个评价指标。

1)连通性 拓扑控制不能使连通图G 变成非连通图。也就是说,如果G 中的节点u 与v 之间有一条(可能是多跳)路径,那么在T 中也应该有这样一条路径(显然,不一定是同一条路径)。如果至少要去掉k 个节点才能使网络不连通,那么就称网络是k 连通的,或者网络的连通度为k 。拓扑控制要保证网络是连通的(即至少1 连通),这是拓扑控制的基本要求。

2)覆盖率 覆盖率可以看成是对传感器服务质量的度量。覆盖问题可以分为区域覆盖、点覆盖和栅栏覆盖[2]。区域覆盖研究对目标区域的覆盖(监测)问题;点覆盖研究对一些离散的目标点的覆盖问题;栅栏覆盖研究运动物体穿越网络部署区域被发现的概率问题。相对而言,对区域覆盖的研究较多。如果目标区域中的任何一点都被k 个传感器节点监测,就称网络是k 覆盖的,或者称网络的覆盖度为k 。一般要求目标区域的每一个点至少被一个节点监测,即1 覆盖。

3)吞吐量 化简后的网络拓扑结构应该能够支持与原始网络相似的通信量,尤其是在有大量突发事件时。设目标区域是一个凸区域,每个节点的吞吐率为 bps 。在理想情况下有下面的关系式[3]:

!(16AW / 2L )(1/nr )bps

其中:A 是目标区域的面积;W 是节点的最高传输速率; 是圆周率; 是大于0的常数;L 是源节点到目的节点的平均距离;n 是节点数;r 是理想球状无线电发射模型的发射半径。由此可以看出,减小发射半径或减小工作网络的规模,在节省能量的同时可以在一定程度上提高网络的吞吐能力。

4)鲁棒性 当在原始图G 中的邻近关系发生变化时(如节点运动、失效或无线信道特性发生变化),一些节点的拓扑信息可能会发生变化。显然鲁棒的拓扑结构只需进行少量的调整就可以避免对本地节点重新组织而造成整个网络的波动。

5)算法总开销 对于资源有限的节点来说,算法本身的开销应该小一些,如附加信息少、计算量小;另外分布式实现也是一个必要条件。

在当前的无线传感器网络中,连通性、覆盖性和扩展因子可能是除了必不可少的分布式性质和低开销量之外的拓扑控制算法最重要的特性。除此之外,拓扑控制还要考虑网络的生存周期、网络中的干扰和竞争、延迟、拓扑性质、负载均衡等其他方面,拓扑控制的各种设计目标之间有着复杂的关系,这些关系也是拓扑控制研究的重要内容。

2 平面网络中的拓扑控制∀∀∀功率控制

在平面网络中,所有的节点都是同构的,具有同样的硬件、同样的能力,完成同样的任务。在平面网络中拓扑控制最基本的方法是控制与一个节点通信的邻节点集。而这个问题与控制节点的发射功率有着密切的关系,所以一般称为功率控制。

目前,对平面网络的拓扑控制研究方法主要分为两类:a)概率分析的方法,在节点按照某种概率密度分布的情况下,计算使拓扑满足某些性质(一般是连通性、覆盖率)所需要的最小发射功率和最小邻节点个数;b)计算几何方法,以某些几何结构为基础构建网络拓扑,以满足某些性质。2#1 概率分析方法

研究人员针对无线传感器网络的特点提出了几何随机图理论。假设网络采用单位圆盘图模型(un it d i sk g raph ,UDG )以及在给定面积为A 的区域内节点是均匀分布的,这个假设模型正好对应于几何随机图理论。

文献[4]采用了一种基于几何随机图的类似算法来确定图是k 连通的概率表达式,如果节点的发射功率大到足以保证图的最小度数至少为k (概率很大),那么有大量节点的图就是k 连通的。Bettstetter 利用这个结论推导出了一个图中最小节点度的概率公式:

P (G 是连通的)#1-∃k -1

l =0(! r 2)l /l !%e -! r 2

(1)

其中:r 为节点的发射半径;!为节点的密度(假设节点在给定区域内均匀分布)。

L i 等人[5]也研究过k 连通问题,提出了当发射半径r 在k >0时满足n r 2&l n n +(2k -1)l n l n n -2l n k +2∀且n 足够大时,节点数为n 的网络(k +1)连通的概率至少是e e -∀

。

如果网络中的节点并不是均匀分布的,尤其是稀疏网络,那么几何随机图理论就无法应用,但是研究人员对此也做了一些工作。Santi 等人[6]假设n 个节点(节点数固定,也可能变化)在d 维部署区域R =[0,l]d 内随机均匀部署,对于节点密度!=n /l d 没有,他们的目标是使所有节点都具有最小半径发射半径r,使得到的图是连通的。

对一维d =1的情况,可以证明,如果rn &2l ln l ,那么图是连通的概率很高;如果rn !l l n l ,图是非连通的概率很高。对于d =2,3的情况,给出了如下结论:

对于某常数k >0,设r d l =k l d l n l ,r =r (l )<>1。如果k >d ∋2d d d /2(或k =d ∋2d d d /2及r =r (l)>>

%3129%第10期卞永钊,等:无线传感器网络中的拓扑控制

设r=r(l)<>1。如果f d O(l d),那么图是非连通的概率很高。

还有其他一些平面网络的研究结果,Kubisch等人[7]描述了两种将邻节点数控制在一定数量内的分布式算法,并通过仿真实验评价了它们的性能。L i u等人[8]研究了关于节点有不同最大发射范围的问题,得到了非连接的信息,采用了一个分布式拓扑结构控制算法来最小化最大功率,保持了每个节点的可达性。R oyer等人[9]研究了功率控制和移动性的关系,功率控制与A d ho c路由协议之间的相互作用,即A d hoc按需距离矢量(AODV)的性能,证明了不存在最优密度,但是密度会随着节点的运动而增大。当前大部分研究把功率控制看做与网络中其他层是无关的。C ruz等人[10]研究了跨层问题,提出了一个结合连接调度表和功率控制的算法。

2#2 计算几何方法

如果能够获得节点之间的距离或它们的相对位置的信息,那么可以有效地实现将网络拓扑变得稀疏。利用计算几何方法构建邻近图的方法能够实现拓扑控制。经常使用的几何结构有以下几种:

a)最小生成树(M ST)。文献[11]提出了一种基于本地信息的最小生成树的构造法,其思想是每个节点会收集它的邻节点,然后构造(如使用pr i m算法)这些节点的最小生成树,将能量代价作为连接权重(代价相同的连接由加入的节点表示符作为间断符来区分)。下一步的关键就是在化简后的拓扑中保留这些对应于最小生成树中直接邻节点的边。这种构造法保持了原图的连通性,而且每个节点的最大度数是6。它能双向连接,也比较容易加入功率控制。而且,平均节点度数比较小,接近理论界限。

b)G abrie l图(G abrie l graph,GG)。在传输功率正比传输距离的平方时,GG是最节能的拓扑。M ST是GG的子图,GG 也满足连通性。在文献[12]中介绍了GG的分布式构造法。一个节点必须要对于它的所有邻节点都测试边的圈定义是否还成立,如果所有的节点都与它们的邻节点的位置相交换,那么这是很容易做到的。

c)相关邻近图(re lati ve ne i ghbor graph,RNG),很容易用本地算法实现。如果原始图G是连通的,那么它也是连通的。其稀疏程度在M ST和GG之间,连通性也在M ST和GG之间,优于M ST,冲突干扰优于GG,是两者的折中。RNG易于用分布式算法构造。

L i等人[13]提出的DRNG和DL M S T是两个具有代表性的基于邻近图理论的算法。基于邻近图的功率控制算法的基本思想是:设所有节点都是用最大发射功率发射时形成的拓扑图G,按照一定的邻居判别条件求出该图的邻近图G(,每个节点以自己所邻近的最远节点来确定发射功率。DRNG是基于有向RNG的,DLM ST是基于有向局部M S T的。DRNG和D L M S T 能够保证网络的连通性,在平均功率和节点度等方面具有良好的性能。

平面网络的功率控制算法除了上面两类基本类型之外,研究人员也提出了一些其他算法,如分布式公共功率协议COM POW[14],K NE I GH协议[15]等。

分布式公共功率协议COM PO W。简单地将功率控制与路由协议相结合的解决方案。其基本思想是:所有的传感器节点使用同样的发射功率,在保证网络连通的前提下,将功率最小化。COM POW在各个功率层上建立路由表,在功率P

i

层上,

通过使用功率P

i

交换HELLO消息建立路由表RT

P i

,所有可达节点都是路由表中的表项。COM POW选择最小的发射功率

P

c o m

,使得RT

P c o w

和RT

P m ax

具有相同的表项。其中P

m ax

是最大

发射功率。于是整个网络都使用公共的发射功率P

co m

。在节点分布均匀的情况下,COM POW具有较好的性能,但是一个相对孤立的节点会导致所有的节点使用很大的发射功率。另外这个理论虽然实现起来相对简单,但是它需要保留所有潜在节点的路由表,这一点使得它基本上不适合无线传感器网络。

K NE I GH协议的思想是使每个节点的邻节点数保持k个或接近于k个。这个协议是分布式的,基于节点间的距离是估计的,而且需要总量为2|V|的信息交换量。这种方法是节点用大发射功率发布它们的信标,收集它们观察到的邻节点的信息,按距离对邻节点进行分类,并计算能够互相到达的k个最近的邻节点,这样每个节点用最小的发射功率就能到达刚才计算的所有邻节点。在这个协议的设计中,需要注意的是要等待足够长的时间随机地唤醒节点,以及适当解决潜在的非对称链路的问题。

3 层次型网络中的拓扑控制结构

研究无线传感器网络拓扑结构的另一种方法是在网络节点中形成一种层次关系,构成一个层次型的网络。目前主要有两种研究手段,即采用支配集的层次型网络和采用分簇结构的层次型网络。

3#1 采用支配集的层次型网络

在网络中选出一些虚拟骨干节点组成虚拟骨干网,这些节点又叫做支配集,即如果V中所有节点或在D中,或是某个节点d D的单跳邻节点(!v V:v D∀d D:(v,d) E),这里D就是支配集。而这个支配集在某种程度上应该尽量小,这也是最小支配集问题(m i n i m u m do m i nati ng se t,M DS)。

文献[16]介绍了两种集中式的例子。a)生成树结构。主要思想是像生成树型结构一样构造支配集,迭代地给树加入旧节点和边,直到所有的旧节点都被覆盖为止。这个算法用节点的颜色来表示:白色节点表示没有被处理,黑色节点属于支配集,灰色节点表示受控集。b)先构造一个不一定连通的支配集,然后在下一个阶段,把集合内的所有节点连接在一起。把非连通的支配集连通起来也叫做寻找斯坦纳树(Stei ner tree)问题。

生成树的分布式算法可以由文献[17]介绍的分布式算法来实现。从本质上来说,就是所有灰色节点发现它们的两跳邻节点,并确定每个节点能够得到的最大收益,然后分布式地选择最大收益,就可以确定下一个黑色节点了。

T opD isc(topo l ogy d i scove ry)算法[18]来源于图论的思想,是基于最小支配集问题的经典算法。它利用颜色区分节点状态,解决骨干网拓扑结构的形成问题。在T op D isc算法中,由网络中的一个节点启动发送用于发现邻节点的查询消息,查询消息携带发送节点的状态信息。随着查询消息在网络中传播,T op D isc算法依次为每个节点标记颜色。最后,按照节点颜色区分出骨干网节点,并通过反向寻找查询消息的传播路径在骨干网节点之间建立通信链路。每个骨干网节点管理与自己相邻

%

3130

%计算机应用研究 第25卷的普通节点。

T opD isc算法中提出了两种具体的节点状态标记办法,分别称为三色算法和四色算法。这两种算法的区别在于寻找骨干网节点的标准不一样,所以最后形成的拓扑结构也有所不同。

3#2 采用簇结构的层次型结构

前面介绍了通过把一些节点作为骨干节点形成支配集,把层次结构引入了网络。另一种形成层次结构的想法是把一些节点标记为具有特殊的功能,如控制其邻节点等,这样就形成了簇,这个具有特殊功能的节点就叫做簇首。这种分簇方法的优点与骨干节点类似,但是更着重于本地资源的优化使用,能够屏蔽网络高层的动态特性,使高层协议更具有可扩展性,另外簇首还能够进行本地数据融合、压缩任务。

LE A C H(l ow energy adap tive c l uste ri ng hierarchy)[19]算法是一种自适应分簇算法,它的执行过程是周期性的,每轮循环分为簇的建立阶段和稳定的数据通信阶段。在簇的建立阶段,相邻节点动态地形成簇,随机产生簇首;在数据通信阶段,簇内节点把数据发送给簇首,簇首进行数据融合并把结果发送给汇聚节点。由于簇首需要完成数据融合、与汇聚节点通信等工作,能量消耗大,LEACH算法能够保证各节点等概率地担任簇首,使得网络中的节点相对均衡地消耗能量。

GAF算法[20]是基于地理位置的拓扑算法,但是它没有考虑节点的剩余能量,而是随机地选择节点作为簇首。该算法中的簇首承担更多的数据处理和通信任务,消耗的能量相对较大,因此,簇首应该选择剩余能量较多的节点。P.Santi等人[21]提出了一种GAF改进算法,他设计了两种不同的簇首选择机制,并详细分析了簇首节点产生后的网络运行方式,同时验证了改进的GAF算法对网络生存时间的影响。与GA F算法相比,GA F改进算法除了要求每个节点知道自己的ID以及属于哪个单元格外,还要求同一单元格中的节点保持时间同步。GAF改进算法有两种簇首选择机制,即完全型簇首选择算法和随机型簇首选择算法。虚拟单元格建立起来后,每个节点都知道自己所属的虚拟单元格。节点根据已知本单元格相关信息的多少决定采取哪种簇首节点选择机制。

HEED[22]的基本思想是:根据对作为第一因素的剩余能量和作为第二因素的簇内通信代价的综合考虑,周期性地通过迭代的办法实现分簇。HEED用最小平均可达功率(AM R P)作为当某个节点被选为簇首时的簇内通信代价的度量。

HEED不依赖于网络的规模,通过O(1)次迭代实现分簇。迭代每一步的时间要足够长,使得节点能够收到来自邻节点的消息。初始时,每个节点要确定在一跳范围内的邻节点的集合,计算并广播AMR P,计算自己成为临时簇首的初始概率C H p。

HEED综合考虑了生存时间、可扩展性和负载均衡,对节点的分布和能力也没有特殊要求,虽然H EED的执行并不依赖于同步,但是不同步却会严重影响分簇的质量。

4 层次型拓扑结构与功率控制相结合

层次型方法(骨干网节点控制、成簇控制)和平面网络中功率控制都是影响无线网络拓扑的有效方法。现在的一个研究方向就是将这两种机制结合在一起。

1)基于引导信号的功率控制[23]

这是一种早期的方法,簇首用这种方法来进行功率控制,与在蜂窝网络中进行的功率控制相类似。在建立初始的分簇结构之后,簇首在引导信号和数据通信中使用功率控制。如果基于这些引导信号,所有节点都加入了同一个簇,那么就可以使用引导信号功率控制来控制簇的成员。数据通信功率控制用于保证远处节点的误码率足够低以及对附近节点能高效地发送信息;它也能防止出现非常差的发射条件。功率控制的主要优点是它在簇首中是集中式的,这简化了完全分布式的功率控制问题。

2)A d hoc网络设计算法

A d hoc网络设计算法(A d hoc net work design a l go rith m, ANDA)[24]允许簇首通过功率控制来控制簇的大小,并且导出了一些具体的规则以尽可能延长网络的生存期。假设网络的生存期主要由簇首决定,因为簇首负责收集、转发感知信息,完成最主要的任务,能量消耗应该在簇首间均衡。

这个方法的基本假设是:a)普通节点和(预选出的)簇首的位置是已知的;b)通信量在普通节点间均匀分布;c)簇首的生存期与它的初始能量成正比,与cr∀+dn成反比。其中:r是簇首覆盖区域的半径;n是簇内成员的个数;∀是路径损耗系数;c、d是常数。算法的最佳目标是使所有簇首的生存期最长,或者相应地使簇首中的最小生存期最长。

这种求最大值的问题是一个优化问题,用决策变量来描述簇j中普通节点i的成员身份。其中也隐含着所需的发射半径。对于静态网络来说,用一个简单的贪婪算法就能求得最优解:将节点i分配给有最长生存期的簇首,对所有节点重复这一操作。对于动态网络来说,需要一个额外的重新配置过程,而且无法保证求得的是最优解,但其实际性能还不错。

3)CLU STERPOW

前面讨论了在节点分布均匀的情况下,COM POW算法具有较好的性能,但是,一个相对孤立的节点会导致所有的节点使用很大的发射功率,所以在节点分布不均匀的情况下,它的缺点是明显的。针对这种缺点,改进了COM POW协议,提出了CLU STERPO W协议[25]。它的基本思想是简单地假设一组离散的发射功率值,如1、10、100mW。在每个功率值处,簇都是形成的,而且对于每个功率值都有单独的路由表。如果用最小功率就能保证到达目的节点,那么就发送数据,一旦数据进入了包含目的节点的最小功率簇后,功率值就会被降低。在CLU STERPO W中,分簇是隐含的,且无须任何簇首节点,分簇通过给定功率层的可达性来实现,分簇的层次由功率的层次数来实现,分簇是动态的、分布的。

对较大的初始发射功率进行替换是很有用的。为了实现这个目标,在相关文献中也描述了隧道式CLU STERPOW协议。在这种情况下,为了避免无限地路由循环,必须将用于以最小功率进行路由的中间节点的地址也装入数据分组中。

5 其他一些启发式算法

还有一些其他的拓扑控制算法,并不是严格地符合利用骨干节点/支配集计算或分簇原理的,它们都是通过打开或关闭某些节点来影响图的拓扑结构。显然,源节点和数据汇聚节点总是活动的。

1)基于地理位置的拓扑算法(GA F)

%

3131

%

第10期卞永钊,等:无线传感器网络中的拓扑控制X u等人在文献[20]中提出了基于地理位置的拓扑算法,它的思想是将区域分成非常小的矩形,使每个矩形中的节点都能与相邻矩形中的节点进行通信。如果某些节点满足某些条件,那么这些节点从网络的高层(如路由层)来看可以看做是等价的。当一个节点休眠时,可以激活它的等价节点来替代。

假设节点都知道它们自己的位置,所以这些节点能很容易地构成这样的等效矩形,并在它们自己的矩形中确定节点。这些节点之间互相合作确定休眠模式,按顺序参加路由协议。X u等人证明了使用这种方案,A d hoc路由协议的能量效率能被提高40%~60%。

2)S T E M算法

在GA F(或其他有等价节点概念的方法)的基础上,可以加入稀疏拓扑和能量管理(sparse topo l ogy and energy m anage m ent)协议[26]。

STE M是节点唤醒算法,在STE M算法中,节点需要采用一种简单而迅速的节点唤醒方式,保证网络通信的畅通和较小的延迟。该算法又包括两种不同的机制,即STE M B和STE M T。它使节点在整个生命周期中大多数时间内处于睡眠状态。节点的睡眠周期、部署密度以及网络的传输延迟之间有着密切的关系。GAF关闭节点,但是却保持网络的转发容量;虚拟唤醒信道的STE M机制提高了能量效率,却也增大了路径建立的延迟。Schurgers等人[26]建议将这两种方法结合起来,即把STE M 算法应用于GA F算法中等价的节点集合之中。

3)可变的自适应拓扑算法(ASCE NT)

加州大学洛杉矶分校的C erpa等人[27]提出了一种着重于保证数据通路畅通的A SCENT算法。保留一定数量的节点作为路由节点,其余节点转入休眠状态,但是节点不仅根据附近节点的通信量来确定是否成为活动节点,还要考虑丢包率指标。如果某个节点发现丢包严重,就向邻节点发出求救信息;收到求救信息的节点主动成为工作节点,帮助邻节点转发数据包。但是,ASCENT并不能保证网络的连通性,因为它只是通过丢包率来判断连通性的。事实上,当网络不连通时,它是无法检测和修复的。A SCENT也不能保证能量的均匀消耗。

节点可以关闭自己,但是必须周期性地进入被动状态来监听帮助请求。对网络性能的监测依赖于拓扑控制,这是AS CENT算法区别于其他算法的地方,但是,它有大量需要优化的参数。

4)在传感器覆盖率的基础上关闭节点

与传统的A d ho c网络不同的是,对W S N来说,只保证网络的连通性是不够的。W S N的主要任务是感知和测量它周围的环境。为了完成这项任务,无论是否需要连通性(可能是弱连通的),观测区域都必须被足够多的节点覆盖。通常,W S N 的感测覆盖率问题是一个很难解决的问题。

T ian等人[28]指出要关闭节点,就必须保证节点的感测覆盖区域会由其他节点覆盖。只有这样的节点才有资格休眠一段时间。

假设节点知道它们的位置和它们的感测区域,在与它们的邻节点交换信息后(如在循环的开始),节点确定它自己的感测区域是否被它的邻节点所覆盖,这只是一个简单的地理问题。如果是,节点就声明它可以休眠,并通知它的邻节点,然后进入休眠状态。

如果所有可以休眠的节点同时进入休眠状态并立即关闭自己,就有出现盲点的危险。如果两个邻节点均可以休眠,根据假设,它们认为另一个节点会保持活动(在另一边剩余的未覆盖区域会由其他更远的节点覆盖),就会发生这种情况。为了避免这种情况,休眠资格的通告是用通用的随机补偿算法进行随机延迟的。当节点接收到这样的信息时,它从它的邻节点列表中将这个很快要进入休眠状态的节点删除,并重新评估它自己的休眠资格。

这个算法基于节点是冗余部署这一事实的;否则不可能有节点可以休眠。这是一个简单而有效的方法,并且考虑了W S N的实际特性。

6 存在的问题及进一步需要研究的内容

上面总结了当前无线传感器网络拓扑控制研究中最具代表性的工作,同时也指出了存在的问题。

1)拓扑控制定义问题

现在对拓扑控制还没有一个清晰的定义,在文献[29]中, P.Santi提出了一个非正式的定义:拓扑控制是为了生成一个具有某种属性(如连通性)的网络,协调网络中的节点决定它们传输范围的一种技术,同时能够减少节点的能量消耗和(或)增加网络的容量。作者区分了一般的节点节能技术、节点功率控制技术和拓扑控制技术的区别,同时又认为成簇技术是控制网络拓扑的一种手段,因为成簇过程中节点的发射功率是固定的,所以成簇技术并不是一种拓扑控制技术。现在大多数人认为拓扑控制技术是在保证一定的网络属性(如连通性、覆盖性等)的前提下,以延长网络生存时间为目标,采用各种技术使网络形成一个优化的网络拓扑,功率控制和层次型网络控制都是手段。但是如何衡量是优化的网络呢?度量网络的性能指标是什么?目前平面网络的功率控制以及层次型网络控制的研究一般都是进行的,不同的应用可能有不同的优化目标,性能指标也不同,不太可能给出一个通用的定义。

2)拓扑控制在协议栈中的位置

拓扑控制与协议栈的其他层关系密切,与物理层、链路层、网络层和传输层交互作用。由于无线传感器网络中的协议栈中的各层之间的界限也已经模糊,那么拓扑控制到底位于哪一层?传统认为[29]拓扑控制位于M AC层之上、路由层之下,它与路由层、M AC层之间的关系最为密切;但是也有人认为拓扑控制分散在各层[30],所有这些都给协议栈设计带来了困难。因此拓扑控制与MA C、路由、数据融合、数据存储以及数据传输等其他方面结合的研究极大拓宽了拓扑控制的研究领域。

3)缺乏对拓扑控制算法的有效度量

拓扑控制要提高网络的各种性能,包括覆盖质量、能量消耗、连通质量、干扰、延时、鲁棒性等。但是目前还没有对这些性能的有效度量的方法。一个实用的拓扑控制技术其实应该综合考虑这些性能指标,但到目前为止还没有这样的研究。有人提出了网络生存周期,但是网络生存周期没有一个统一的定义,实际上网络生存周期是一个综合的抽象的性能指标。如何有效地度量网络的性能,也就是如何有效度量控制算法的性能,这些也是拓扑控制要研究的内容。

由此看来,无线传感器网络中的拓扑控制还有很多问题需要研究,这些问题构成了拓扑控制研究的内容,这些研究内容

%

3132

%计算机应用研究 第25卷之间又是相互制约、密不可分的。

7 结束语

本文简要地描述了无线传感器网络拓扑控制的研究现状以及其中存在的一些问题。现在拓扑控制研究的发展趋势是以实际应用为背景,多种机制结合使用,强调网络拓扑控制的自适应性和鲁棒性,在保证网络连通性和覆盖度的前提下,提高网络的通信效率,最大限度地节省能量来延长整个网络的生存时间。但是目前的研究还普遍存在着模型过于理想化,对网络性能的综合考虑比较少,研究结果缺乏足够的说服力,没有考虑实际应用中的困难。拓扑控制还有许多问题有待进一步研究,特别是要根据实际应用情况探索更加实用的拓扑控制技术。以实际应用为背景、多种机制相结合、综合考虑网络各种性能将是拓扑控制研究的发展趋势。

参考文献:

[1]AKY I LD I Z I F,SU W,SANKARAS UBRA M AN I AS Y,e t a l.A sur

vey on sensor net work s[J].I EEE C o mm unications Magaz ine,

2002,40(8):102 114.

[2]THA IM T,W ANG F,D U D Z.C overage prob l e m s i n w ireless sensor

net w orks:des i gn s and ana l ysis[J].I nt ernati o nal Journal of Sensor Net works,2008,3(3):191 200.

[3]GUP TA P,K UM AR P R.The capaci ty of w ireless n et w ork s[J].

I EEE Trans on I nf or m ation Theory,2000,46(2):388 404.

[4]BETTSTETTER C.On t h em i n i m u m node d egree and connecti v i ty of

a w i rel es s mu ltihop net w ork[M].Los A l a m it os:I EEE Co m puter So

ci ety P ress,2002:80 91.

[5]L I X i ang yang,W AN Peng j un,WANG Yu,et al.Fau lt t o l eran t de

ploy m en t and t opol ogy con trol i n w i reles s net work s[C]//Proc of t h e 4th ACM Sy m posi um on M obil e A d hoc Net w ork i ng and C o m pu ti ng.

Ne w York:ACM Press,2003:117 128.

[6]SANT I P,BLOUGH D M.The critical trans m itti ng range f or conn ec

ti vit y i n s parse w i rel ess Ad hoc net w ork s[J].I EEE Trans onM obile Computi n g,2003,2(1):25 39.

[7]KUBISCH M,KARL H,WOLISZ A,et a l.D istri buted al gori thm s for

trans m is s i on pow er con trol i n w ireless sen s or n et w ork s[C]//Proc of IEEE W ireless C o mm un i cati on s and N et w or k ing(W CNC).N e w York:

IEEE Press,2003:558 563.

[8]L I U Ji le,i L I Bao chun.D i stri bu ted t opol ogy contro l i n w i rel ess sen

sor net works w it h asy mm etric li nks[C]//Proc of I EEE G l obeco m W ireless Co mmun ications Sy m pos i um.San Fran ci sco:[s.n.],2003.

[9]ROYER E M,M ELL I AR SM I TH PM,M OSER L E.An an al ysis of t h e

op ti m u m node dens it y f or Ad hocm ob ile n et w ork s[C]//Proc of I EEE In t ernational Con ference on C o mm un i cati on s.H elsi nk:i[s.n.],

2001:857 861.

[10]CRUZ R L,SANTHANAM A V.Opti m a l rou ti ng,link schedu li ng

and pow er control i n m ulti hop w ireless n et w ork s[C]//P roc of t h e 22nd Annual Joi n t Con ference on I EEE C o m pu ter and Co mmun ica ti ons Societies.N e w Yor k:I EEE P ress,2003:702 711.

[11]L IN i ng,HOU J C,SHA L.Des i gn and anal ys i s of an M ST bas ed to

pol ogy contro l al gori thm[J].I EEE Trans on W ireless Co mmuni ca ti o ns,2005,4(3):1195 1206.

[12]KARP B,KUNG H T.GPSR:greedy peri m eter stat eless rou ti ng for

w ireless net w orks[C]//Proc of t he6t h I n tern ati on al Conference on M ob ile C o mpu ti ng and Net w ork i ng.N e w Y ork:ACM Press,2000:

243 254.[13]L I N i ng,HOU J C.Topol ogy con trol i n heterogen eous w irel ess net

work s:proble m s and sol u ti ons[C]//Proc of I EEE C on f eren ce on

C o mpu ter C o mmun icati on s.N e w Y ork:I EEE Pres s,2004:232 243.

[14]NARAYANAS W A M Y S,KAWADI A V,SREENI VAS R S,et a l.

Po w er con trol i n A d hoc net work s:t heory,arch itect u re,al gorit hm and i m p le m entati on of the CO M PO W protoco l[C]//Proc ofEu rop ean W ireless C onference.2002:156 162.

[15]BLOUGH D M,LEONC I N IM,RESTA G,e t al.The K n ei gh proto

col for s y mm etri c t opol ogy con trol i n Ad hoc n et w ork s[C]//Proc of the4th ACM In t ernational S y mpos i um on M ob ile Ad hoc N et w orking and C o mpu ti ng.N e w York:ACM Press,2003.

[16]GUBA S,KHULLER S.Approxi m ation al gori thm s f or connected

do m inati ng s ets[J].A l g orit h m ica,1998,20(4):374 387.

[17]DAS B,BHARGHAVAN V.Rou ti ng i n Ad hoc net w ork s using m i n i

m um connected do m i nati ng set[C]//Proc of Internati onalC on f eren ce on C o mm un i cati on(I CC).1997:376 380.

[18]DEB B,B HATNAGAR S,NATH B.A topology d i scovery al gorit hm

for sensor net works w it h app lications to n et w ork m anage m ent,DCS TR 441[R].Co m den,N J:Ru t gers Un ivers it y,2001.

[19]HE I NZELMAN W R,C HANDRASAN A,BALAKR I SHNAN H.An

app licati on s pecific protoco l arch i tecture f or w ireless m i cro s en s or net work s[J].I E EE Trans on W ir e l e ss Co mmunications,2002,1

(4):660 670.

[20]XU Ya,HE I DE M ANN J,ESTRI N D.Geography i n f or m ed energy

con servati on for Ad hoc rou ting[C]//Proc of the7th Annual Interna ti onal C onferen ce on M ob il e Co m pu ti ng and Net work i ng.Ne w York: ACM Press,2001:70 84.

[21]SANTI P,SI M ON J.S il ence is go l den w ith probab ility:m ai n t a i n i ng a

conn ect ed backbone i n w i rel ess sensor net w orks[C]//Proc of the1st Eu ropean W ork s hop on W ireless Sen s or Net works.B erli n:Sp ri nger, 2004:106 121.

[22]YOUN IS O,FA HMY S.HEED:a hybri d,energy effici en t,distri bu

ted cl u steri ng approach f or Ad hoc sensor net w orks[J].I E EE T r ans on Mobil e Co m puting,2004,3(4):660 669.

[23]K W ON T J,GERLA M.C l usteri ng w i th po w er con trol[C]//P roc of

the4th I EEE M ilitary Co mm un ications Con ference.Atl an tic C ity:

IEEE Press,1999:1424 1428.

[24]C H I ASSERI N I C F,CH L AM TAC I,M ONT I P,et al.Energy effi cient

des i gn of w ireless Ad hoc net w ork s[C]//P roc of the2nd IFI P N et work i ng Con ference.London:Spri ng V erlag,2002:376 386. [25]KAWADI A V,K UM AR P R.Po w er con trol and cl usteri ng i n Ad hoc

net w orks[C]//Proc of t h e22nd Ammual Joi n t C on f eren ce on I EEE

C o mpu ter and C o mm un i cati on s Societi es.N e w York:I EEE Press,

2003:459 469.

[26]SCHURGERS C,TS I ATS IS V,GANER I W AL S,e t a l.Topology

manage m ent f or sensor net w orks:exp l oiti ng laten cy and dens it y[C]// Proc of the3rd ACM Internati onal Sy m pos i um on M ob ile Ad hocN et work i ng&C olll pu ti ng.N e w Yor k:AC M Pres s,2002:135 145. [27]CERPA A,ESTR I N D.ASCENT:adapti ve self confi gu ri ng sensor

net w orks topol ogies[J].I EEE Trans on Mob ile Computing,2004, 3:272 285.

[28]TI AN D,i GEORGANAS N D.A coverage preservi ng node schedu

li ng sche m e for l arge w i rel ess sensor n et w ork s[C]//Proc of t he1st ACM W orkshop on W irel ess S ensor Net w orks and App licati ons.Ne w York:ACM Press,2002:32 41.

[29]SANTI P.Topology control i n w i reles s A d hoc and sensor net w orks

[J].ACM Co mputing Surveys,2005,37(2):1 194.

[30]KAWAD I A V,KUM AR P R.A cauti onary perspecti ve on cross l ayer

des i gn[J].I EEE W ireless Communicati o ns,2005,12(1):3 11.

%

3133

%

第10期卞永钊,等:无线传感器网络中的拓扑控制