异构无线传感器网络中基于CDS树的拓扑控制方法*

马晨明,王万良,洪 榛

(1.浙江工业大学信息工程学院,杭州 310023;2.浙江工业大学计算机科学与技术学院,杭州 310023;3.浙江理工大学机械与自动控制学院,杭州 310018)



异构无线传感器网络中基于CDS树的拓扑控制方法*

马晨明1,王万良2*,洪 榛3

(1.浙江工业大学信息工程学院,杭州 310023;2.浙江工业大学计算机科学与技术学院,杭州 310023;3.浙江理工大学机械与自动控制学院,杭州 310018)

拓扑控制是无线传感器网络中节约能量、延长网络生命的关键技术。针对现有拓扑控制方法主要集中在同构网络中作为拓扑构建或拓扑维护单独研究的问题,提出了包含两个过程的异构网络分布式拓扑控制算法A3M。拓扑构建基于最小连通支配集构建虚拟骨干树,在保证连通性的同时关闭网络冗余节点以降低能耗;拓扑维护对网络性能进行评估,当现有网络性能严重下降时,改变拓扑以保障网络的稳定运行。理论分析和仿真实验证实算法能够以较小的时间和消息代价减少拓扑构建能耗并延长网络时间。

异构无线传感器网络;拓扑控制;A3M算法;拓扑构建;拓扑维护;最小连通支配集

无线传感器网络由传感器节点自组织形成[1],节点能量受限且通常不易补充,因此如何节省能量成为研究无线传感器网络的重要问题。拓扑控制[2]是保证全网连通、平衡节点能耗,增加运行时间的高效可行技术,它包括拓扑构建与拓扑维护两个过程[3]。拓扑构建用于关闭网络冗余节点,减少节点之间的链路通信;拓扑维护用于优化网络拓扑平衡节点之间的能耗。当前研究使用最小连通支配集MCDS(Minimum Connected Dominating Set)构造虚拟骨干树作为延长网络生命的主要拓扑构建方法[4],它将网络节点分为活跃节点和普通节点。活跃节点负责监听并转发数据,而普通节点进入休眠以节约能量。然而,求解MCDS是典型的NP-hard问题,因此已经有大量学者对该问题进行了研究。

文献[5]提出了令牌流技术对MCDS问题进行数学建模,以最小网络分发的令牌数作为目标函数,求解完毕后各个持有令牌的节点组成的集合即为MCDS。文献[6]对文献[5]进行了改进,在目标函数中引入节点的剩余能量作为约束条件,从而优化了网络的时间。上述算法依靠全局拓扑一般能够得到较小的MCDS,然而,求解过程中需要节点之间的大量通信作为代价,同时求解的时间和空间复杂度较高,不适合冗余部署的密集型网络。

EECDS[7]采用最大独立集技术构造连通支配集,初始时所有节点状态为White,算法选择一个初始节点s广播Black消息;邻域状态为White的节点收到消息后,改变状态为Grey并广播Grey消息;Grey节点邻域内的White节点收到该消息后,将权值广播出去并启动超时竞争成为Black节点;如果White节点在超时内收到了Black节点的Invite消息则成为Black节点并继续广播Black消息。算法由内向外覆盖网络,直到所有的黑色节点构成一个彼此互不相连的最大独立集。第二阶段同样从s开始广播Blue消息;状态为Grey的节点,更新权值并重新广播消息竞争成为连通节点,如果在超时内收到Black节点的Invite消息则成为连接节点。最终,所有Black节点和连接节点构成连通支配集。Kim在文献[8]中指出EECDS在连通节点的过程中会存在死锁的问题,需要在执行中增加一个处理条件。然而,EECDS产生的MCDS可能过大,文献[9-10]利用剪枝缩小MCDS规模,即首先生成一个未经优化的MCDS,然后使用修剪规则去掉冗余节点。

A3[11]采用生成树构造连通支配集,Active节点广播Hello消息搜集邻居节点信息,邻居节点收到消息后计算剩余能量和信号强度并回复一个父亲认知消息给上层Active节点;父节点收到回复后对子节点进行排序,最终将节点等待时间列表广播给邻域子节点;等待时间结束后,子节点成为活跃节点并继续在下一跳节点中搜索活跃节点。A3能够得到较小的连通支配集规模,但是在构建过程中每一个Active节点均需要向邻居节点广播一个排序后的等待时间列表,当节点规模较大时这将使得发送的消息包将非常大,严重影响网络的能效性[12]。A3G[13]对这方面进行了改进,其采用了逆向构建CDS树的过程减少了部分通信开销,降低了传输包的大小,但是算法的时间和空间复杂度还是较高。

EB-MCDS[14]将节点度和剩余能量作为节点的权值,优先选择权值较大的节点成为活跃节点,但是算法在构造MCDS的过程中需要搜集二跳邻域的节点信息,使得算法的信息复杂度达到了O(nΔ),因而只能应用在规模较小的网络中。

以上研究均假设区域内的节点性能完全相同,这与实际网络严重脱节。文献[15]指出异构WSNs可以分为计算异构、链路异构和能量异构,即网络中可以存在不同计算能力、通信能力以及能量水平的节点。同时,拓扑维护对于网络生存时间同样产生重要影响,在恶劣环境下节点可能由于突发情况而失效,这就需要算法能够动态重构网络。文献[16]将拓扑控制与拓扑维护进行区分,并指出选择合适的拓扑维护策略将大大增加网络的生命时间。为了使得研究更加贴近现实,本文考虑网络中节点的通信半径和能量水平存在异构的情况下,提出了一种带有拓扑维护机制的拓扑控制方法A3M,算法不仅以最小化连通支配集的数量作为主要目标,而且以较低的时间和消息复杂度最小化拓扑构建能耗,当网络不再最优时,触发拓扑维护对网络重构,这一过程不断循环直至运行结束。

1 模型与A3G算法概述

1.1 网络模型和问题描述

我们用图G(V,E)表示异构无线传感器网络模型,其中V表示N个传感器节点集合{v1,v2,…,vN},E是由V中节点组成的通信链路集合,假设节点的最大通信半径CTRmax(Critical Transmitting Range[17])可以不同,节点vi和vj之间存在链路当且仅当vi和vj相互处于对方的通信半径内,即(vi,vj)∈E当且仅当d(vi,vj)≤min{Ri,Rj},其中d(vi,vj)表示节点vi与vj之间的欧式距离,min{Ri,Rj}为节点vi和vj的较小通信半径。节点静止部署在M×M的二维平面内,基站(Sink)部署在区域的中心位置(M/2,M/2),各个节点具有唯一的ID且能量可以异构,同时节点之间不需要使用GPS或其他定位算法获得位置信息以节约能量。

下面对本文提出的拓扑控制算法A3M在异构网络中所求解的问题进行描述。假设节点集合V存在子集DS(DS⊆V),对于网络中其他任意节点u(u∈V-DS),如果在节点u的通信半径Ru内至少存在一个DS中的节点v(v∈DS)且其通信半径Rv≥d(u,v),则将DS中节点组成的集合称为支配集。如果DS是连通的则DS为连通支配集。最小化生成的连通支配集中的数量即为算法所求解的异构网络中的最小连通支配集问题。

1.2 A3G算法

下面对A3G的性能进行分析,算法主要分为邻居节点发现,邻居信息交换和节点竞争3个过程:

①邻居节点发现:Sink节点以最大功率广播Hello信息,邻域内节点收到信息后计算权值并继续广播Hello信息直到遍历所有节点;该过程中,算法的时间和信息复杂度均为O(n)。

②邻居信息交换:在邻居节点发现阶段,当子节点收到父节点发送的Hello信息时,将向父节点回复一个包含节点ID和权值的信息。父节点收到信息后将其存储以备在节点竞争时使用。该过程算法的信息复杂度为O(n);由于节点需要对邻域内节点的权值进行排序,算法的时间复杂度为O(nlogn)。

③节点竞争过程:从叶节点开始,节点从候选列表中选择权值最大的节点作为活跃节点,记为S。节点S在邻域内广播Sleep信息并向存储列表中权值最大的父节点发送骨干确认信息。邻居节点收到信息后设置一个超时timer,如果timer内没有收到其他节点的确认消息,那么它将进入休眠模式;否则,继续向上层竞争直到Sink节点。这一过程中节点将发送2n的信息,同时算法的时间复杂度为O(n)。

综上所述,在最坏情况下,A3G的时间和信息复杂度分别为O(nlogn)和O(4n)。同时,A3G只适用于同构网络,没有考虑到节点之间的异构,当节点能量降低而不再适合作为骨干时,也没有对拓扑维护过程进行深入研究。针对以上问题,本文从拓扑构建与拓扑维护两个方面对网络进行优化。

2 A3M算法

2.1 拓扑构建

A3M将拓扑构建分为邻居节点发现、邻居节点竞争以及未覆盖节点发现3个过程。初始时,网络中节点的状态为Initial;算法结束后,节点状态将变成Active或Sleep。算法执行过程如下:

①邻居节点发现

在同构网络中,节点u收到邻域内节点v的消息后,即可以确定u,v处于通信半径内,v同样可以接收到u广播的消息。本文考虑网络中节点的通信半径存在异构的情况,因此需要两轮的Hello信息交换确定邻域内节点。我们令Nr(u)表示节点u能够收到的发送节点ID集合,初始时Nr(u)为空。在第一轮信息交换中,节点u将收到的节点ID存储到Nr(u),并在第二轮消息交换中广播出去。当节点u收到节点v的Nr(v)后,通过判断当前节点u是否在Nr(v)中即可以确认节点u,v是否可以进行通信。

②邻居节点竞争

节点竞争从Sink开始,广播Dominate消息并改变节点状态为Active。状态为Initial的节点u收到节点v发送的信息后,将检查v是否在邻域N(u),如果v是邻居节点则计算适应度fitness并启动与之成反比的定时器timer1竞争成为活跃节点。同时,将状态改变为Candidate并广播Candidate信息表示节点成为候选节点。邻域节点w收到Candidate消息判断u是否在N(w)内,如果是邻居节点则更新未覆盖节点集合uncover(w)=N(w){v};否则,忽略该消息。

timer1内节点u收到N(u)内节点v的Dominate消息,即表示邻居节点具有更好的fitness,节点u将状态改变为Sleep Candidate并重置新的超时timer2。

③未覆盖节点发现

状态为Sleep Candidate的节点u等待时间timer2后,将查找uncover(u)是否还有未被覆盖节点,如果存在则节点u改变为Active并广播Check Message;否则,将状态改变为Sleep并进入睡眠模式。状态为Sleep Candidate邻居节点v收到该消息,则重置timer2以增加等待时间,确保节点只有在必需时才成为活跃节点。

图1 A3M拓扑构建运行实例

图1为A3M拓扑构建算法的具体运行实例。图1(a)中节点E虽然在活跃节点A的通信范围内,但是A不能收到E发送的信息,因此E不是A的邻居节点;图1(b)中邻域节点B成功竞争为活跃节点,而节点D进入Sleep Candidate;图1(d)中超时timer2结束,节点D由于邻域内存在未覆盖的节点G而成为活跃节点,节点C进入休眠状态;最终形成拓扑如图1(f)。

2.2 拓扑维护

拓扑维护是恢复、轮换、再生成拓扑的过程,通常根据时间或能量等条件定义不同的维护策略,网络中节点在拓扑构建后将启动拓扑维护过程。如果节点的剩余能量小于阈值,节点将向基站发送Reconstruction Message(sendID,gatewayID,SinkID)请求网络重建,并更新当前节点的阈值,其中sendID表示发送节点ID,gatewayID表示下一跳节点ID,SinkID表示基站的ID。

Reconstruction Message沿着gatewayID向基站发送,如果当前节点ID不等于SinkID,节点继续选择合适的gatewayID进行转发;否则,表示信息到达基站。Sink节点对当前网络状态评估后将Decision Message(flag,time)沿着MCDS对全网进行广播,其中flag表示是否重构网络,time表示等待重构的时延。活跃节点将收到的Decision Message向普通节点转发,并在time后重构拓扑。

由于重构拓扑通常需要消耗大量的时间和能量,为了避免由于少量节点的失效引起全网的变动,Sink可以预先在拓扑构建中生成并存储若干能够覆盖网络但彼此不相交的MCDS集合,这些集合可能并非最优,但是能够快速执行轮换,我们称之为网络的静态拓扑维护。如果在时间T内,Sink节点收到多个节点的Reconstruction请求,则证明当前网络已经并非最优,需要动态重构网络。

2.3 适应度函数

考虑网络的异构性同时最小化MCDS的数量,本文将节点相对剩余能量、节点之间的距离、节点的通信半径以及在拓扑维护中被选择为活跃节点的次数作为适应度函数的参数,具体公式如下:

(1)

其中,ω1,ω2,ω3,ω4表示对应的权值,在初期进行设定。Eu表示节点u的剩余能量,N(u)表示一跳邻居节点,当节点剩余能量在邻域范围内最大时则越有可能成为活跃节点;d、Ru、Rmax分别表示当前节点与上层活跃节点之间的距离、当前节点的通信半径以及节点的最大通信半径,均可以由接收到信号的强度RSSI获得;ActiveNum表示节点在拓扑维护中被选举为骨干的次数,Rounds则表示当前已经进行的拓扑维护次数,即节点被选择为活跃节点的次数越多则其适应度函数值越小。

3 性能分析

定理1如果初始WSNs是连通的,那么通过A3M拓扑构建算法形成的CDS也是连通的。

证明使用反证法进行证明,假设拓扑构建后形成的CDS是非连通的,那么至少存在一个状态为Initial的节点。算法从Sink节点起由内向外覆盖网络,Initial节点首先被标记为Candidate,其中fitness较大且邻域内存在未覆盖节点的节点在timer1后成为Active;而fitness较小的Candidate节点将在timer2后确认是否有需要覆盖的节点,并最终将状态转换为Sleep或Active。最终,所有节点被标记为Active或Sleep。如果存在状态为Initial的节点,说明初始的WSNs是非连通的,这与假设不符,得证。

定理2A3M拓扑构建算法的信息和时间复杂度均为O(n)。

证明在异构网络中邻居节点的发现过程需要两轮的信息交换确定邻域内的节点,算法复杂度为O(2)。邻居节点竞争过程中,Initial节点收到父节点的Dominate消息后将回复O(1)的信息。如果节点的fitness在邻域内最大将在timer1后发送O(1)的消息;否则,在超时timer2后检查邻域内是否存在尚未覆盖的节点,如果存在则发送O(1)的消息包反之进入休眠状态。状态为Active的节点将发送O(2)的信息,而Sleep节点最多发送O(1)的消息。在最坏情况下,算法在异构网络中的信息复杂度为O(4n)。同时,如果节点部署在同构网络中,由于在邻居发现过程中仅仅需要一轮的信息交换,算法在最坏情况下的信息复杂度为O(3n)。此外,节点的计算不需要排序和发送大数据量的消息包,并且操作均能在常数时间内完成,因此算法的时间复杂度为O(n)。

定理3当节点能量达到阈值时,A3M拓扑维护过程的信息和时间复杂度均为O(n)。

证明网络运行一段时间后,当节点的剩余能量小于阈值时,节点将以O(1)时间构建Reconstruction Message并向Sink节点发送重构网络请求。消息沿着MCDS向基站传递,最坏情况下,该消息包将转发O(n)到达基站。Sink节点根据当前网络状况将执行的拓扑维护策略和时延封装在Decision Message,并沿着拓扑反向转发,因此拓扑维护发送的消息最多不会超过2n,其消息复杂度为O(n)。由于节点的消息发送和转发操作均能在常数时间O(1)内完成,因此整个拓扑维护过程的时间复杂度也为O(n)。

4 仿真实验及分析

4.1 实验环境及参数设置

仿真实验将A3M与A3、A3G、EECDS、CDS-Rule-K[10]4个算法进行比较,实验采用文献[18]中的能耗模型并用基于网络事件驱动的仿真软件Atarraya[19]进行评估,实验结果取自随机生成的20个拓扑实例分别运行20次后的平均值,考虑到A3算法需要传输所有邻居节点排序后的等待时间列表,我们将该消息包的大小设为100 Byte,其他消息包的大小设为40 Byte,其他实验参数如表1所示。

仿真实验从拓扑控制与拓扑维护两个方面对算法进行评估,拓扑构建考虑生成的活跃节点个数、信息的发送数量以及能量消耗比率3个方面的性能,并定义能耗比率为网络中节点消耗的能量与初始能量的比值;拓扑维护则评估A3M在无拓扑维护、静态拓扑维护、动态拓扑维护3种不同策略下的网络运行时间。

4.2 实验结果分析

本节对实验结果进行分析,实验1在保持节点数量不变的基础上调整临界传输范围CTR改变节点度。如图2所示,A3M产生的活跃节点数要少于其他算法的结果,这说明A3M执行后能够获得更接近最优值的解。随着传输半径的增大,各算法产生的活跃节点数都逐渐减少,这是由于临界传输范围的增加造成任意节点可通信范围的增加,即节点度的增加使得单位活跃节点可支配的节点增多,因此最终需要的活跃节点数相比原来有所减少。

图2 实验1改变节点度时的活跃节点数

图3与图4分别显示了各个算法在拓扑构建过程中发送的消息数和能耗比率情况,EECDS和CDS-Rule-K在确认一个节点成为活跃节点时需要在节点之间交换大量的消息以做出决定,因此其发送的消息总量远远多于其他3种算法,而实验显示A3M所需要交互的消息数量最少,这是因为理论分析可知算法在最坏情况下仅仅需要发送4n的消息数量。同时从文献[18]中的能耗模型中可知,节点的能量消耗与节点发送和接收消息的数据比特成正比,因此交互的消息数量越多所需要传输的比特就越多,这样所产生的能耗自然也就增加了,这也是A3M在拓扑构建中消耗能量最少的原因。随着节点度的增加A3M消耗的能量有所增加但基本稳定,其能耗相比A3G和A3算法分别平均减少了20.3%和33.1%。

图3 实验1改变节点度时的发送消息数

图4 实验1改变节点度时的能耗比率

实验2通过改变节点的数量来比较各类算法的性能。图5～图7显示,节点密度的改变并不影响A3M以较少的信息、能耗代价获得比A3G、A3、EECDS、CDS-Rule-K更少的活跃节点集。当网络由50个节点组成时,A3M算法平均需要19.2个节点以连通网络,相当于38.4%的节点将成为活跃节点,这一数据随着网络节点的增加而减少,当在250个节点的网络中A3M算法仅仅需要9.8%的活跃节点数。A3M算法能够获得较小活跃节点数的原因主要在于其在邻居节点发现阶段获得了局部拓扑的所有节点信息,然后通过本文定义的适应度函数优先选择性能较优的节点成为活跃节点,因而需要的活跃节点数较少。同时,我们发现随着节点数量的增加产生的活跃节点数并不是一直增长,这是可以理解的,因为活跃节点达到一定数量时即可覆盖整个网络,此时继续增加节点数并不会引起活跃节点的持续增加。

图5 实验2改变节点数量时的活跃节点数

图6 实验2改变节点数量时的发送消息数

图7 实验2改变节点数量时的能耗比率

实验3对A3M算法的拓扑维护策略进行评估,节点每隔10个单位时间向Sink节点发送采集的数据,节点的能量阈值记为0.2 J,不考虑数据融合。如图8和图9所示,无论是在稀疏网络还是密集网络中,本文提出的拓扑维护策略将延长网络的运行时间。其中,静态拓扑维护策略所生成的连通支配集中的节点性能由最初决定,因此当网络运行一段时间后其所使用的连通支配集的性能可能已经并非最优,使得网络运行时间不如动态拓扑维护策略。图8中显示在稀疏网络中,静态拓扑维护策略在时间点16 679.2时开始陆续出现节点的死亡而导致通信覆盖率下降,而这一现象在动态拓扑维护中则发生在时间点23 252.7。相比稀疏网络,在密集网络中各个算法通信覆盖率的下降趋势有所减缓,从图9中发现动态拓扑维护策略直到时间点55 861.5时才开始出现通信覆盖率的下降,其相比无拓扑维护时的网络生命时间得到了明显的提高,而且下降趋势相对于稀疏网络而言更为平缓,这是因为当节点密度足够时个别节点的失效并不会显著影响网络的生存时间,及时运行网络的拓扑维护过程替换失效节点将极大改善网络的性能。

图8 实验3稀疏网络下A3M的覆盖率变化

图9 实验3密集网络下A3M的覆盖率变化

5 结束语

本文提出了一种异构网络中的基于CDS树的分布式拓扑控制方法A3M,算法从拓扑构建与拓扑维护两个方面对网络的能耗进行优化。在拓扑构建过程中,该算法不但减少了生成的活跃节点数量,而且降低了节点的时间和信息复杂度;当运行的网络不再高效时,利用拓扑维护策略重构网络拓扑以节约能量。理论分析和仿真实验进一步证实,无论是将节点部署在稀疏还是密集的环境下,A3M算法相比A3G、A3、EECDS、CDS-Rule-K 4种算法在性能上均有了显著的提高。应该指出,本文在实现拓扑维护过程中仅仅考虑基于节点能量的拓扑维护策略而没有考虑基于时间周期性轮换拓扑的策略,而如何将这2种维护策略进行结合也是今后需要进一步完善的地方。

[1] Yick J,Mukherjee B,Ghosal D.Wireless Sensor Network Survey[J].Computer Networks,2008,52(12):2292-2330.

[2]Aziz A A,Sekercioglu Y A,Fitzpatrick P,et al.A Survey on Distributed Topology Control Techniques for Extending the Lifetime of Battery Powered Wireless Sensor Networks[J].IEEE Communications Surveys and Tutorials,2013,15(1):121-144.

[3]Labrador M A,Wightman P M.Topology Control in Wireless Sensor Networks[M].Berlin:Springer,2009:61-68.

[4]Liu Z,Wang B W,Guo L J.A Survey on Connected Dominating Set Construction Algorithm for Wireless Sensor Networks[J].Information Technology,2010,9(6):1081-1092.

[5]Wightman P M,Fabregas A,Labrador M A.An Optimal Solution to the MCDS Problem for Topology Construction in Wireless Sensor Networks[C]//IEEE Latin-American Conference on Communi-cations(LATINCOM),Bogota,Columbia,2010:1-6.

[6]洪榛,俞立,张贵军,等.基于最小连通支配集的无线传感网拓扑构建研究[J].电子与信息学报,2012,34(8):2000-2006.

[7]Zeng Y Y,Jia X H,He Y X.Energy Efficient Distributed Connected Dominating Sets Construction in Wireless Sensor Networks[C]//International Conference on Wireless Communica-tions and Mobile Computing,Vancouver,Canada,2006:797-802.

[8]Kim D,Wu Y,Li Y,et al.Constructing Minimum Connected Dominating Sets with Bounded Diameters in Wireless Networks[J].IEEE Transactions on Parallel and Distributed Systems,2009,20(2):147-157.

[9]Das A,Mandal C,Reade C,et al.An Improved Greedy Construction of Minimum Connected Dominating Sets in Wireless Networks[C]//IEEE Wireless Communications and Networking Conference(WCNC),Cancun,Mexico,2011:790-795.

[10]Wu J,Cardei M,Dai F,et al.Extended Dominating Set and Its Applications in Ad Hoc Networks Using Cooperative Communication[J].IEEE Transactions on Parallel and Distributed Systems,2006,17(8):851-864.

[11]Wightman P M,Labrador M A.A3:A Topology Control Algorithm for Wireless Sensor Networks[C].//IEEE Global Telecommuni-cations Conference,New Orleans,USA,2008:1-6.

[12]Feeney L M,Nilsson M.Investigating the Energy Consumption of a Wireless Network Interface in an Ad Hoc Networking Environment[C]//Proceedings of Twentieth Annual Joint Conference of the IEEE Computer and Communications Societies(Infocom 2001),Anchorage,USA,2001:1548-1557.

[13]仇昌琪,肖明波.基于反向生成CDS树的无线传感器网络拓扑控制算法研究[J].传感技术学报,2012,25(12):1737-1742.

[14]凌飞,吴振华.能量均衡的最小连通支配集分布式算法[J].传感技术学报,2012,25(9):1316-1321.

[15]Yarvis M,Kushalnagar N,Singh H,et al.Exploiting Heterogeneity in Sensor Networks[C]//Proceedings of 24th Annual Joint Conference of the IEEE Computer and Communications Societies(IEEE Infocom),Miami,USA,2005:878-890.

[16]Wightman P M,Labrador M A.Topology Maintenance:Extending the Lifetime of Wireless Sensor Networks[J].IEEE Latin America Transactions,2010,8(4):469-475.

[17]Santi P.Topology Control in Wireless Ad hoc and Sensor Networks[M].England,John Wiley and Sons,2005:39-52.

[18]Heinzelman W B,Chandrakasan A P,Balakrishnan H.An Applica-tion-Specific Protocol Architecture for Wireless Microsensor Networks[J].IEEE Transactions on Wireless Communications,2002,1(4):660-670.

[19]Wightman P M,Labrador M A.Atarraya:A Simulation Tool to Teach and Research Topology Control Algorithms for Wireless Sensor Metworks[C]//Proceedings of 2nd International Conference on Simulation Tools and Techniques,Rome,Italy,2009:26-35.

马晨明(1983-),男,浙江杭州人,浙江工业大学信息学院博士研究生,主要研究方向为无线传感器网络拓扑控制;

王万良(1957-),男,江苏高邮人,博士生导师。国家级教学名师、享受国务院特殊政府津贴、浙江工业大学计算机科学与技术学院院长,研究方向为计算机自动化、无线网络;

洪榛(1983-),男,浙江台州人,博士。浙江理工大学机械与自动控制学院讲师,主要研究方向为无线传感器网络拓扑控制、智能交通、优化调度。在国内外重要期刊及会议上发表论文10余篇,申请发明专利10项(已授权3项),软件著作权30余项。

ATopologyControlMethodBasedonCDSTreeinHeterogeneousWirelessSensorNetwork*

MAChenming1,WANGWanliang2*,HONGZhen3

(1.College of Information Engineering,Zhejiang University of Technology,Hangzhou 310023,China;2.College of Computer Science and Technology,Zhejiang University of Technology,Hangzhou 310023,China;3.Faculty of Mechanical Engineering and Automation,Zhejiang Sci-Tech University,Hangzhou 310018,China)

Topology Control is a key strategy to save energy and extend the lifetime of wireless sensor networks.In view of the problem that existing topology control methods mainly focus on the homogeneous network to research on topology construction or topology maintenance separately,a distributed topology control algorithm A3M in the heterogeneous network is presented that contains both process.Topology construction is based on the Minimum Connected Dominating Set concept to construct the virtual backbone tree,which turns off redundant nodes to save energy while ensuring the network connectivity.Topology maintenance is related with the evaluation of the performance of the network,and changes the topology to maintain the stable operation of the network when the existing network performance degrades significantly.Theoretical analysis and simulation experiments confirm that our algorithm can reduce the energy consumption of topology construction and extend the network lifetime with low time and message complexity.

heterogeneous wireless sensor network;topology control;A3M algorithm;topology construction;topology maintenance;minimum connected dominating set

项目来源:国家自然科学基金项目(61304256,61379123);“十二五”国家科技支撑计划项目(2012BAD10B01);浙江省自然科学基金项目(LQ13F030013);浙江省教育厅项目(Y201327006)

2014-03-18修改日期:2014-05-08

10.3969/j.issn.1004-1699.2014.06.020

TP393

:A

:1004-1699(2014)06-0814-07