无线传感执行器网络中多源容错拓扑控制算法研究*

杨明霞,毕宏博,柴国飞

(衢州学院电气与信息工程学院,衢州 324000)

无线传感执行器网络中多源容错拓扑控制算法研究*

杨明霞*,毕宏博,柴国飞

(衢州学院电气与信息工程学院,衢州 324000)

拓扑控制是延长无线传感器网络生命时间的关键技术。针对异构网络的复杂性,提出了基于功率控制的分布式多源容错拓扑控制算法MSFT。在由大量计算、能量受限的传感器节点和少量性能较优的执行器节点组成的异构无线传感执行器网络模型中,算法保证任意传感器节点与执行器节点之间至少存在k条不相交路径同时选择权值较优节点使路径总功耗尽可能少,这样当任意k-1个节点失效时并不影响网络的连通性。理论分析证明算法能以O(n)的时间和消息代价构造网络拓扑,仿真实验进一步证实算法的有效性。

无线传感执行器网络;异构;容错;拓扑控制;功率控制

无线传感器网络WSNs(Wireless Sensor Networks)由大量价格低廉的微型传感器节点自组织组成,广泛应用于对象跟踪、环境监测、灾害预防等领域[1]。节点的能量有限且通常不可重复补充,因此节能是无线传感器网络需要考虑的重要问题[2]。拓扑控制是保证网络连通、平衡节点能耗,增加运行时间的高效可行技术,它通常包括拓扑构建与拓扑维护两个过程[3]。拓扑构建用于减少网络链路以节约能量,当节点失效或当前拓扑已经不再最优时运行拓扑维护重构网络。然而,重构网络需要消耗大量的能量,同时节点通常部署在战场、森林等环境恶劣地区,极易出现链路断裂、硬件错误等问题,因此构造容错性好、可靠性高的拓扑已经成为了关键[4]。另一方面当前研究往往过于理想化,即假设各个传感器节点的性能完全相同,与实际严重脱节。文献[5]指出异构WSNs可以分为计算异构、链路异构和能量异构,同时如果节点能够部署合适的话,将极大改善网络的收发速率并能将网络运行时间提升五倍,因此必须考虑节点的异构。

为了研究异构网络的性能,近年来在WSNs基础上引入若干执行器节点衍生出了一种称为无线传感执行器网络[6](WSANs)的新型网络模型。WSANs将网络节点分为性能受限的传感器节点(Sensor)和能量充足、具有较强计算和通信能力的执行器节点(Actor)。Actor由于价格昂贵其数量通常远远小于Sensor。Sensor以多跳的方式将采集的数据向Actor发送。当数据到达Actor后,Actor将Sensor采集的数据进行融合后发向外部网络。因此,可以将执行器节点集当成多个Sink节点部署在网络中,将数据传输过程分为Sensor-Sensor,Sensor-Actor和Actor-Actor 3种不同层次,并最终发向外部网络。Actor-Actor之间的链路由于由性能较高的节点组成因而较为稳定,而Sensor-Sensor和Sensor-Actor则极易由于Sensor的失效而造成网络的瘫痪。

本文在WSANs的基础上研究容错拓扑控制算法,提出了MSFT(Multiple Source Fault-Tolerant Algorithm)用于保证网络中任意Sensor节点至少存在k条到达Actor的不相交路径,如果网络是k连通的,那么任意k-1个节点的失效不会导致网络中断,同时提高了网络的路由灵活性。

1 相关工作

拓扑控制算法主要分为功率控制和睡眠调度两种类型。睡眠调度[7-9]将网络节点分为骨干节点和非骨干节点,骨干节点一直处于活跃状态并负责监听与转发数据,而非骨干节点只有在数据需要发送时才会苏醒,其他时候处于休眠以节省能量。由于其不是本文主要研究内容,在此不作详细叙述。功率控制通过调节网络节点的发送功率,在满足网络连通覆盖度的前提下,均衡节点的邻居节点数目,剔除节点间不必要的通信链路,形成一个数据转发的优化网络结构,达到优化网络生命时间的目的。当前,已经有很多学者对功率控制算法进行研究。

LMA[10]是一种基于节点度的功率控制算法,初始时每个节点以相同功率广播LifeMsg消息,邻居节点收到消息后回复LifeAckMsg给发送方。发送方对收到的回复进行统计,如果其值在预先设定的最小与最大阈值之间则算法结束;否则,调整发送功率直到节点度到达阈值。LMN[11]是LMA的改进,在回复LifeAckMsg时,将最新的邻居节点数量添加到消息包,并通过计算自身的平均邻域邻居节点数判断是否在阈值范围内。这类算法利用局部信息能够达到一定程度的优化,但是依赖于初始阈值的设定,同时难以保证网络的全连通。NNPC[11]采用了近邻算法评估网络节点的密度并计算相应的最优发送功率,摆脱了初始阈值的约束,节点根据最优发送功率发送数据并提高了网络生命时间。但是,该算法需要保存网络的全局拓扑信息,因此是一种集中式算法而且只适用于较小规模的网络。

文献[12]指出物理层、MAC层及网络层之间存在相互影响、相互制约的关系。物理层的发射功率和传输速率影响了MAC层的接入控制和网络层的路由选择;MAC层限制了信源的带宽和分组延迟,从而影响了网络层的路由选择。因此,将期望节点度、连通因子和干扰竞争节点数等信息进行融合,建立了博弈模型并提出一种能耗均衡的可靠拓扑博弈算法EBRGA。算法分为邻居节点发现、博弈执行和功率确定3个阶段。在邻居节点发现阶段,各个节点通过信息交换建立邻居节点列表,并在博弈执行过程中通过该列表比较节点信息选择不同发射功率对网络状况造成的影响,并最终在功率确定阶段确定最大化自身收益的发射功率。算法能够保证网络的连通,但是没有考虑到节点剩余能量对发送功率产生的影响,如果节点剩余能量较低同时又具有较大的传输半径,那么网络可能会由于部分节点的能量耗尽而提前死亡[13]。同时,博弈过程的时间因素也是一个值得考虑的问题。

文献[19]面向异构网络,基于反向连通支配集树,研究一种低信息复杂度的分布式拓扑构建算法。基于最小连通支配集进行虚拟骨干的构建,从而优化连通支配集的规模和通信功耗,在保证连通性的同时关闭网络冗余节点以降低能耗。文献[20]提出一种面向节能和容错的分布式拓扑控制算法,在连通支配集建立后,选择容错度大的节点作为备份节点,在数据收集过程中对支配节点的能耗进行均衡。

2 模型与问题描述

2.1 网络模型

无线传感执行器网络由M个执行器节点和N个传感器节点组成,Actor静止均匀分布在L×L的正方形区域内,它们负责将收到的传感器节点数据发送到外部网络,Sensor则在区域内随机进行部署。假设Sensor的能量和通信半径异构并且有限,Actor的能量可以无限大。本文中仅仅考虑Sensor-Sensor和Sensor-Actor之间的通信,而忽略Actor将采集的数据发向外部网络的过程。用G=(V,E)表示该网络模型,其中V表示图中的节点,由v1,v2,…,vN,vN+1,vN+2,…,vN+M组成。其中,前N个节点表示传感器节点集而后面M个节点表示执行器节点。E是图G中节点V组成的链路集合。各个节点具有唯一的ID,节点之间通过信息交换获得一跳范围内的邻居信息而无须配置GPS等定位装置以获取地理位置。

2.2 问题描述

为了更好地描述本文研究的问题,首先给出以下定义:

定义1不相交路径

假设节点u和v之间的任意两条路径分别为p1=(u,w11,w12,…,w1m,v)和p2=(u,w21,w22,…,w2n,v),如果链路p1和p2中的节点除了首尾的端点u和v外,其他中间节点均不相同,则称p1和p2是两条不相交的链路。

定义2k连通网络

无线传感器网络是k连通的当且仅当网络中所有传感器节点均存在k条通向执行器节点的不相交路径。

定义3节点的初始功率设定

节点剩余能量充足时可覆盖的范围较大,当剩余能量较少时,为了避免能量消耗过快,节点需要减小功率以缩小传输范围,当功率减少到最低发射功率时则不再改变。初始时,ni的剩余能量为E(ni),定义式(1)作为节点ni的初始功率,其中Pmax,Pmin,Emax,Emin分别表示节点的最大、最小可调功率和最大、最小能量。

(1)

定义4节点之间的传输功率

本文采用式(2)的计算传输功率,假设任意节点ni和nj之间的距离为dis(ni,nj),则ni和nj之间进行通信需要的最小功率为P(ni,nj)。ni和nj能够通信当且仅当ni和nj的各自传输功率P(ni)和P(nj)均大于P(ni,nj)。

P(ni,nj)=dis(ni,nj)α

(2)

定义5通信链路权值

消息传输失败的概率随着传输距离的增加而不断变大,同时传输距离的增加将导致节点消耗的功率增大。另一方面,如果传输链路中存在能量水平较低的节点,那么网络可能会由于个别节点的能量耗尽而提前死亡。本文定义式(3)～(6)用于衡量通信链路优劣,其中Emin(ni,mj)和Pmax(ni,nj)分别表示当前路径(ni,ni+1,ni+2,…,ni+p,mj)中所有路径中间节点的最小能量和相邻节点一跳路径中功耗最大值。当链路的权值相等时比较一跳路径中需要的功耗最大值Pmax,如果还相等则比较ID。

Emin(ni,mj)=min{E(nk)},nk∈[ni,ni+1,…,ni+p]

(3)

Pmax(ni,mj)=max{P(nk,nk+1)},
k∈[i,i+1,…,i+p]

(4)

(5)

(6)

定义6k-ATC问题

本文研究无线传感执行器网络的k连接问题,同时使得优化后的网络拓扑链路总功率最小。假设网络由传感器节点N={v1,v2,…,vN}和执行器节点M={vN+1,vN+2,…,vN+M}组成且N∩M=Φ。对于网络中任意节点v∈V都至少存在k条能够到达执行器节点集合M的不相交路径,同时使得这些路径的通信链路权值之和最小。定义目标函数为:

(7)

3 MSFT算法描述

MSFT算法从各个执行器节点以最大功率广播PathInfo(ID,hops)消息开始,其中hops主要用于控制执行器节点的可覆盖范围,传感器节点每收到一次信息需要将对应的hops减1,hops越大表示信息被转发的次数越多,当hops等于0时信息停止转发;一跳邻域的邻居节点u收到消息后,通过信号强度RSSI估计与执行器节点m之间的距离并计算通信需要消耗的功率,然后在本地保存一个列表PathList(Path(m,u),E(u),P(m,u),Pmax,W(v,m)),其中向量Path(m,u)用于保存u与执行器节点之间的路径,E(u)表示当前链路中所有节点的最小能量,P(m,u),Pmax分别表示当前链路总功耗和单跳最大功耗,W(v,m)表示链路权值。一般来说此时节点只有一条可达执行器节点的路径,因此需要向邻域转发PathInfo(Path(m,u),E(u),P(m,u),Pmax,hops)并启动一个定时器timer以搜集其他路径集合。

在超时时间中,节点收到消息后按照之前方法计算与发送者u之间通信需要消耗的功率P(u,v),同时对信息包进行解析,更新路径为Path(m,u,v)并累加总功耗P(v,m)=P(u,v)+P(u,m),接着将节点能量与链路最小能量Emin进行比较,如果当前节点能量小于Emin则更新最小能量并计算路径权值W(m,v),然后存储到列表PathList中。

超时结束后,当前节点对PathList列表中存储的路径按照权值大小进行排序,记为NPathList。为了保证网络的容错性,需要确保k条到达执行器节点的连通路径并将该路径集合记为K-Connective-Path。初始时K-Connective-Path为空,将NPathList中权值最小的路径添加到K-Connective-Path中并将其从NPathList中删除,然后对NPathList开始进行遍历。如果当前路径Path(m,w1,w2,…,v)与K-Connective-Path中的路径不相交,则将其从NPathList删除并添加到K-Connective-Path列表中;否则,在NPathList中删除该路径并继续遍历下一条记录。在判断不相交路径的过程中,假设当前比较的NPathList和K-Connective-Path列表路径记录分别为pn(m,wn1,wn2,…,v)和pk(m,wk1,wk2,…,v),首先分别对路径pn和pk中节点按照ID进行排序,然后用两个指针分别指向排序后的路径列表进行遍历,如果路径中存在除自身节点或执行器节点之外其他ID相等的节点,则证明两条路径相交,否则将pn添加到列表中。

以上过程不断重复直到当前K-Connective-Path列表已经存在k条路径或循环正常结束。节点向外广播一个PathInfo(Path(m,vk),Emin,P(m,vk),Pmax)信息,消息中存储的分别是列表中当前存在的可达路径、对应路径中的最小能量集合以及功耗列表信息。如果当前K-Connective-Path列表中的记录数小于k,则说明当前距离执行器节点m最小跳数的有效路径少于k,则节点需要继续等待其他节点(跳数略大)的广播信息直到路径数达到k。

当网络中所有节点均已存储了k条可达路径,则算法开始第2阶段的标记工作。节点u根据本地K-Connective-Path列表中存储的路径获得k条可达路径的上一邻居节点集合为{v1,v2,…,vk},则节点u将列表集合添加到必需的邻居节点集合Required中并删除冗余链路集合N1(u)-{v1,v2,…,vk},调整功率为到达{v1,v2,…,vk}中最远节点的功率,然后在邻域内逆向广播一个Notify(ID(u),{v1,v2,…,vk})消息。假设节点vi收到该信息后,则解析消息并将发送节点ID与k条可达路径的邻居节点集合为{v1,v2,…,vk}合并,然后调整最大功率并继续上述过程直到Notify消息到达执行器节点,算法终止。

图1 MSFT算法具体运行实例

图1给出了MSFT算法的具体运行实例,其中1(0.8),2(0.6),3(0.8),4(0.7)表示传感器节点,5(10),6(10),7(10)表示执行器节点,括号中数值表示节点的初始能量,链路上的数值表示通信链路功耗。初始时,假设各执行器节点分别发送PathInfo(hops=2)消息,各传感器节点收到路径消息后最终形成排序后的PathList列表如图1(b)-(e)所示,黑色加粗记录表示不相交路径,图1(f)给出了各个节点调整功率后的最终拓扑。

4 性能分析

定理1假设初始网络中各传感器节点与执行器节点是k连通的,那么通过MSFT形成的最终拓扑仍然是k连通的。

证明假设节点u和v之间的链路(u,v)被删除。MSFT算法为了节省能量在保证k条通路后会调整节点功率为Required集合的最大值,即说明v不在u的Required集合中。因为初始网络是k连通的,Required集合确保了至少存在k条通向执行器节点的链路,因此删除链路v并不影响网络的连通性,否则u并不会删除链路(u,v),所以通过MSFT形成的最终拓扑仍然与各执行器节点k连通。

定理2MSFT的时间和信息复杂度均为O(n)。

证明节点计算路径功耗并转发消息均能在常数时间内完成,因此该部分时间复杂度为O(1)。超时timer结束后,节点需要对存储的所有可达执行器节点的有效路径列表PathList进行排序,因此需要O(plogp)的时间,其中p表示节点在超时timer内收到的路径集合数,假设节点邻域存在Δ个邻居节点,则p在最坏情况下等于kΔ。在得到k条不相交路径列表K-Connective-Path的过程中,需要比较NPathList与K-Connective-Path列表中的每一条记录的路径相交性,因此需要O(k2hlogh)的时间复杂度,其中h表示距离执行器节点的跳数。在邻域节点的标记过程中,节点以O(Δ)的时间生成k条可达路径的上层邻居节点集合为{v1,v2,…,vk},该过程中算法的时间复杂度为O(Δ),因为k,h均为常数,因此MSFT总的时间复杂度为O(n)。同时,网络节点为了搜集k条到达执行器节点的可达路径,在最坏情况下需要将本地消息包转发k次;而在标记邻居节点的过程中,每一个节点均需要广播一次Notify消息,因此所有节点最坏需要发送k+1次的消息,算法的消息复杂度为O(n)。

5 仿真实验及分析

5.1 实验环境及参数设置

为了验证算法的性能,本文在基于网络事件驱动的仿真平台Atarraya[21]上进行实验。节点随机部署在200×200的区域内,假设所有节点的初始能量异构分布在范围[0.5,1]中,传输距离设置在范围[5,35]之间对应最小和最大功率范围[25,1225],这里不考虑执行器节点之间的数据传输,并保证生成的拓扑满足k-ATC。选择与算法DATC(h=1)和DATC(h=2)进行对比,实验结果取自运行20次后的平均值,具体参数如表1所示。

表1 仿真参数

5.2 实验结果分析

第1组实验通过改变节点数量观察容错k=2时的各个算法产生的拓扑运行功率、节点的最大功率和消息发送数的情况。图2显示了当k=2时网络的最终拓扑的运行功耗情况。随着传感器节点密度的增加,各个算法的功耗均不断增加,同时发现MSFT算法相比DATC(h=1)和DATC(h=2)具有更好的性能,这是因为MSFT在选择k条不相交路径时能够获得距离执行器节点功耗更低的传输路径,而DATC(h=1)和DATC(h=2)由于将传输路径的选择限制在一跳邻域或二跳邻域导致了性能的下降。

图2 最终拓扑的运行功耗(k=2)

网络的生命时间不仅和消耗的总功率有关,还与网络中节点的能耗速度有关。如果个别节点能耗过大,那么形成网络拓扑将会由于部分节点的提前死亡而出现中断,这就需要尽可能地平衡网络中各个节点的能耗。图3显示了当k=2时的网络中所有节点的最大功率情况。当网络中节点的密度逐渐增加时,MSFT算法所需要的节点最大功率不断下降,这是由于MSFT能够在本地获得性能更好的不相交路径。同时,不管是DATC(h=1)还是DATC(h=2)都将由于部分节点的功耗过大导致网络提前死亡。

图3 网络节点的最大功率(k=2)

拓扑控制算法的好坏不仅与最终产生的网络拓扑的运行功耗有关,还与产生拓扑过程中的能耗有关,本文使用节点发送的消息数量近似衡量构建能耗。图4显示了各个算法发送的信息数量情况。之前实验显示DATC(h=2)相比DATC(h=1)在最终产生的拓扑运行功率以及节点的最大功率上性能更优,但是发现其需要发送的信息数量呈几何指数性增长,这是因为算法在获得不相交链路的过程中需要获得二跳邻域范围的节点信息,因此通信能耗极大并不适合在真实网络中应用。MSFT相比DATC(h=1)发送的信息数更少,因此在构建拓扑过程中将节省更多的能量。

图4 拓扑构建过程的信息发送数(k=2)

图5 最终拓扑的运行功耗(k=4)

第2组实验通过改变节点数量观察容错k=4时各个算法的性能。发现当k变大后无论节点密度如何各个算法的功率均有所增加,这是因为为了保证每个节点存在至少k条到达执行器节点的路径,随着k的增加更多的边集需要被维护,因此会导致功率的增加。同时当k增加时,需要发送的信息数也会相应的增加。与之前实验类似,无论是在最终产生的拓扑运行功率、节点的最大功率还是消息发送数,MSFT算法均具有较优的性能。

图6 网络节点的最大功率(k=4)

图7 拓扑构建过程的信息发送数(k=4)

6 总结

本文在由执行器节点和传感器节点组成的多源异构无线传感器网络中定义了k-ATC问题并提出了一种能量高效的容错拓扑控制算法MSFT。MSFT通过功率控制的方法确保每个传感器节点至少存在k条到达一个或多个执行器节点的不相交路径,然后将功率调整到与最远邻居节点通信所需要的功率以节约能量。因此,当网络中任意k-1个节点发生故障时,网络不会终止。同时,仿真实验证实,MSFT产生的最终运行拓扑功率相比同类算法DATC能够提高大约3倍的性能,因此适合应用在节点受到环境影响而频繁失效的恶劣网络环境。下一步的工作将主要考虑将MSFT算法在物理层和MAC层等不同层次进行跨层优化,同时可移动的执行器节点部署也是一个研究方向。

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

[2] Anastasi G,Conti M,Francesco M,et al. Energy Conservation in Wireless Sensor Networks:A Survey[J]. Ad Hoc Networks,2009,7(3):537-568.

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

[4] Liu H,Nayak A,Stojmenovic I. Fault-Tolerant Algorithms/Protocols in Wireless Sensor Networks[C]//Guide to Wireless Sensor Networks,2009:265-295.

[5] 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.

[6] 周雁,王福豹,黄亮,等. 无线传感器执行器网络综述[J]. 计算机科学,2012,39(10):21-25.

[7] 孙超,尹荣荣,郝晓辰,等. WSNs 中基于能量代价的最小权和支配集拓扑控制算法[J]. 电子与信息学报,2010,32(4):857-863.

[8] 孙超,尹荣荣,郝晓辰,等. 异构无线传感器网络支配集拓扑控制算法[J]. 软件学报,2011,22(9):2137-2148.

[9] Du H W,Wu W L,Ye Q,et al. CDS-Based Virtual Backbone Construction with Guaranteed Routing Cost in Wireless Sensor Networks[J]. IEEE Transactions on Parallel and Distributed Systems,2013,24(4):652-661.

[10] Kubisch M,Karl H,Wolisz A,et al. Distributed Algorithms for Transmission Power Control in Wireless Sensor Networks[C]//IEEE Wireless Communications and Networking Conference(WCNC),New York,USA,2003:16-20.

[11] 陈友荣,俞立,董齐芬,等. 基于近邻算法的无线传感器网络功率控制[J]. 浙江大学学报(工学版),2010,44(7):1321-1326.

[12] 郝晓辰,张亚晓,刘彬,等. 一种能耗均衡的传感器网络可靠拓扑博弈算法[J]. 软件学报,2011,22(增1):1-12.

[13] 陈友荣,任条娟,刘半藤,等. 基于最短路径树的分布式功率控制路由算法[J]. 传感技术学报,2012,25(8):1138-1146.

[14] Li N,Hou J C. Localized Fault-Tolerant Topology Control in Wireless Ad Hoc Networks[J]. IEEE Transactions on Parallel and Distributed Systems,2006,17(4):307-320.

[15] Miyao K,Nakayama H,Ansari N,et al. LTRT:An Efficient and Reliable Topology Control Algorithm for Ad-Hoc Networks[J]. IEEE Transactions on Wireless Communications,2009,8(12):6050-6058.

[16] Li N,Hou J C,Sha L. Design and Analysis of an MST-Based Topology Control Algorithm[C]//Twenty-Second Annual Joint Conference of the IEEE Computer and Communications Societies,San Francisco,USA,2003:1702-1712.

[17] Azzeddine R,Wang D. SFL:A Simple Fault-Tolerant Local Topology Control algorithm for sensor networks[C]//IEEE Conference on Industrial Electronics and Applications(ICIEA),Singapore,2012.

[18] Cardei M,Yang S,Wu J. Algorithms for Fault-Tolerant Topology in Heterogeneous Wireless Sensor Networks[J]. IEEE Transactions on Parallel and Distributed Systems,2008,19(4):545-558.

[19] 杨明霞,王万良,马晨明. 一种基于反向CDS树的异构WSNs拓扑构建方法[J]. 传感技术学报,2016,29(2):248-255.

[20] 杨明霞,王万良,马晨明. 面向节能和容错的异构WSNs数据收集算法[J]. 传感技术学报,2016,29(6):934-940.

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

杨明霞(1979-),女,博士,衢州学院讲师。主要研究方向为智能信息处理、无线传感器网络,ymx1228@163.com;

毕宏博(1984-),男,博士,讲师,目前研究方向为迭代学习控制,bihbo001@163.com;

柴国飞(1986-),男,博士,衢州学院讲师,主要研究方向为多智能体系统、无线传感器网络,guofei.chai@gmail.com。

MultipleSourceFault-TolerantTopologyControlMethodResearchinWirelessSensorandActorNetwork*

YANGMingxia*,BIHongbo,CHAIGuofei

(College of Electrical and Information Engineering,QuZhou University,Quzhou 324000,China)

Topology Control is a key strategy to extend the lifetime of wireless sensor networks. In the light of the complication in the heterogeneous network,a distributed multiple source fault-tolerant topology control algorithm MSFT based on power control is proposed. In the heterogeneous network model which is composed of a large number of sensor nodes with limited energy and computing capability,and several actors with unlimited energy resources,the algorithm ensure each sensor has at leastk-vertex disjoint paths to actors and choose node with better weight to minimal the total path power consumption. The resulting topologies can keep network connectivity even in case of thek-1 node failures. Theoretical analysis show MSFT is able to construct the topology with time and message complexity ofO(n)and simulation results confirm the effectiveness of the algorithm further.

wireless sensor and actor network;heterogeneous;fault tolerant;topology control;power control

TP393

A

1004-1699(2017)11-1740-07

项目来源:浙江省自然科学基金(LQ17F030005);衢州市科技计划项目(2016Y001,2016D005);衢州学院师资队伍建设基金(XNZQN201308);衢州学院人才培养科研启动项目(BSYJ201505)

2017-03-15修改日期2017-06-01

10.3969/j.issn.1004-1699.2017.11.021