异构多跳无线传感器网络容错性拓扑控制算法

刘兴川，吴振锋，赵克俭

（中国电子科技集团公司第二十八研究所，江苏南京210007）

异构多跳无线传感器网络容错性拓扑控制算法

刘兴川，吴振锋，赵克俭

（中国电子科技集团公司第二十八研究所，江苏南京210007）

异构无线传感器网络（heterogeneous wireless sensor works，HWSN）能有效降低数据转发延迟、网络能量消耗，是一种更现实的网络模型，基于HWSN的k容错性拓扑控制是一类NP-难问题。在综合分析HWSN网络模型的基础上，本文设计了简化网络图构建方法，通过构造有序邻集来约束节点的最大发射功率，以网络总功耗与容错性双优化为目标，实现了一个k容错性分布式拓扑控制算法（k-fault-tolerant distributed topology control，k-FTDTC）。实验结果表明，相比分布式拓扑控制（distributed adaptive topology control，DATC）方法，k-FTDTC算法有效降低了网络总功耗和最大发射功率，且具有较好的容错性和较低算法复杂度。

异构无线传感器网络；拓扑控制；有序邻集；容错性

0 引 言

异构无线传感器网络（heterogeneous wireless sensor networks，HWSN）是指由多种不同类型的传感器节点构成的网络，传感器节点的异构性主要表现在：计算能力异构、通信能力异构以及节点能量异构［1－2］。无线传感器网络（wireless sensor network，WSN）早期的拓扑控制研究主要集中在同构WSN，即网络中所有传感器节点具有相同的软硬件能力，被随机部署在监测区域，地位平等，开展能量最优化研究［3－5］。然而在实际环境中，传感器节点通常承担不同的角色功能，甚至具有不同的资源配置以适应多样化的应用需求。此外，即使是同构的WSN，由于节点感知任务的不同所造成的能耗不同，也促使初始能量相同的网络逐渐演变成多级能量异构网络。可见，HWSN是一种更现实的网络模型，最近的研究成果［6－8］也表明，相比同构网络架构，HWSN有效降低了监测数据转发延迟、网络能量消耗，具有更优的网络性能。

本文研究的HWSN是由两类传感器节点组成：一类是资源受限随机部署的传感器节点，称为普通节点（common node，CN），用于感知监测异常事件；一类是高能力定点部署的超级节点（super node，SN），组成骨干网络，完成数据融合和快速转发等任务，如图1所示。CN节点通过多跳方式与SN节点进行通信，由于复杂恶劣环境的影响，经常导致CN节点间通信链路失效，再加上CN节点能量受限，如何在保证网络具有容错性的基础上最优化网络能量消耗成为HWSN拓扑控制亟需解决的一个难题。

图1 异构无线传感器网络模型

针对上述问题，文献［9－11］利用同构网络中已有的研究成果，提出了通过构造网络的k点连通图建立容错性拓扑，即网络中任意两个节点之间都至少存在k条不相交的路径，当任意k－1个节点或链路发生故障时，网络仍然保持连通，该方法可有效提高网络容错性，但是由于任意节点都要保持k条不相交的路径，因此导致整个网络能耗随其容错能力的提升成倍增加。文献［12－13］证明了k点连通图构建是一个NP-难问题，需要对该问题进行简化，求其次优解，同时分别提出了两种集中式近似求解算法，但是对于节点数据众多的WSN而言，集中式拓扑控制算法并不利于网络规模的扩展。随后，文献［14－15］针对HWSN容错性拓扑控制，基于节点剩余能量，以最小化网络总功耗为目标，提出k点连通图的分布式近似求解算法。但是在多跳网络中节点剩余能量多少并不能准确反映节点剩余生命周期的长短，需要综合考虑节点的剩余能量和能量消耗速度，同时这些方法也没有对节点的最大发射功率进行控制，因此导致网络中节点能量消耗不均衡。

综上所述，文献［9－15］研究的问题与本文相似，目标都是在保证网络具有k容错性的基础上，最小化网络总功耗。本文与上述工作的不同之处主要体现在：①在HWSN中，感知数据从CN节点发送到SN节点，因此在任意两个节点之间都保持k条不相交的路径是没有必要的，重要的是使每一个CN节点存在k条不相交的路径可达SN节点。基于上述思想，本文设计的目标函数是保证任意CN节点与SN节点集都存在k条不相交的路径，在此基础上最小化网络总功耗。②综合分析异构多跳WSN的特点，设计简化图方法来对HWSN网络模型进行优化，以降低算法求解复杂度；通过构造CN节点的有序邻集来控制节点的最大发射功率，以最小化网络总功耗与能量均衡双优化为目标，实现k容错性分布式拓扑控制（k-fault-tolerant distributed topology control，k-FTDTC）算法，提高网络健壮性。③基于仿真实验，对本文提出的k-FTDTC算法性能进行了详实的评估，同时与经典的分布式拓扑控制（distributed adaptive topology control，DATC）算法［15］进行性能比较，以验证本文算法的有效性。

1 网络模型与问题描述

式中，Pr表示接收功率；λ为电磁波长；d0为参考距离，一般为1m，d是发射天线与接收天线之间的距离；n是路径损耗系数；G1，G2分别是发射天线增益和接收天线增益。

根据上述假设，CN节点和SN节点共同构成一个连通的网络，可抽象为一个无向加权网络图G＝（V，E，ω），其中点集V包含N个CN节点和M个SN节点，即V＝｛n1，n2，…，nN＋1，…，nN＋M｝，前N个为CN节点，后M个为SN节点。E为边集，定义为E＝｛（ni，nj）｜dist（ni，nj）≤Dmax｝，其中dist（·）为欧式距离函数。ω为对应E中每条边的权值集合。下面给出用到的几个定义：

定义1 边的权重：用ω（ni，nj）表示，定义为节点ni与nj间通信所需的最小发射功率，具体值可以通过式（1）计算。

定义2 可达邻集：用F（ni）表示，定义为节点ni以最大传输距离Dmax进行通信，所能到达的节点集合，即F（ni）＝｛nj｜nj∈V，（ni，nj）∈E｝。

定义3 节点的功率：用P（ni）表示，定义为P（ni）＝

1.1 网络模型

本文讨论的HWSN网络模型如图1所示，包括N个CN节点和M个SN节点，其中M≪N。其中，CN节点随机分布，能量受限，具有短的通信能力和低的数据速率，主要任务是实时感知监测目标的信息，周期性地将感知数据通过多跳方式传送给附近的SN节点，其主要的能耗来自于数据的无线收发。相比CN节点，SN节点具有更多能量、更强的计算存储能力、更长的通信距离和更高的数据速率，SN节点间形成骨干网络，主要负责对CN节点的感知数据进行融合处理、判决计算，实时可靠地将结果转发给监测中心。SN节点的应用不仅延长了整个网络生命周期，还降低了端到端的数据传输延迟，因此，该结构在实际中被广泛研究和应用［16－17］。上述模型满足以下假设条件：

（1）CN节点随机密集部署，具有相同的软硬件，初始能量相同且为Einit，通信距离可调节，最大通信距离为Dmax；

（2）SN节点为高能力节点，定点部署，初始能量定义为Einit（1＋K），其中K表示SN节点能量是CN节点能量的倍数；

（3）CN节点间、CN节点与SN节点间的通信链路是本文拓扑控制研究的重点，而由于SN节点为定点部署且为高能力节点，本文认为SN节点间通信链路是固定可靠的，不属于本文拓扑控制关注的重点。

（4）CN节点与SN节点分布在二维平面上，形成一个静态连通性网络，链路具有对称性，每个节点具有唯一ID，节点间通信满足文献［18］提出的无线信道模型，即max｛nj｜（ni，nj）∈E｝ω（ni，nj）。

定义4 网络图G总的功耗：用P（G）表示，为图G中各节点功率之和，即

定义5 k点连通SN节点集：任意CN节点即∀ni∈V且i≤N，存在k条不相交的路径到达SN节点集，即任意k－1个CN节点或链路出现故障时，网络仍保持连通，即CN节点的感知数据能通过SN节点传送到监控中心。

1.2 问题描述及简化

基于上述异构多跳网络模型，k-FTDTC算法的目标是：①通过调节CN节点的功率，使每个CN节点与SN节点集间存在k条不相交的路径；②优化CN节点的最大发射功率，并使所有CN节点功耗之和最小，即

结合k-FTDTC问题描述，本文将网络图G＝（V，E，ω）进行简化求解，简化规则如下：

（1）用一个根节点取代M个SN节点，形成的新点集为V1＝｛n1，n2，…，nN，root｝，这是因为研究表明SN节点间的通信链路是可靠的［17］。

（2）节点之间的边保持不变，若同一个CN节点与两个或两个以上的SN节点相连，则仅保留边权值最小的那条边。这是因为k-FTDTC的目标是使CN节点与SN连通并最小化CN节点发射功率。

（3）边的权重保持不变。

利用上述规则设计算法1将网络图G＝（V，E，ω）转化为简化图G1＝（V1，E1，ω1），简化图伪代码如表1所示。

表1 简化图G1构建算法伪代码

定义6 简化图k点连通root节点：任意CN节点即∀ni∈V且i≤N，存在k条不相交的路径到达根节点root，则称简化图k点连通root节点。

根据定义7可以获得定理1。

定理1 异构多跳WSN是k点连通SN节点当且仅当对应的简化图是k点连通root节点。

证明 （1）必要性。由于异构多跳WSN是k点连通SN节点，即∀ni∈V且i≤N的节点，都存在k条不相交的路径到达SN节点集。用根节点root取代每条路径上的SN节点，即获得任意CN节点即∀ni∈V且i≤N与根节点root之间的k条不相交的路径，即简化图G1是k点连通root节点。

（2）充分性。如果简化图G1是k点连通root节点，则表明对于任意CN节点即∀ni∈V且i≤N，存在k条不相交的路径到达root节点。因此，对于图G1中到根节点的任意路径｛ni0，ni1，…，nim，root｝，都可以通过用一个SN节点即nk，k＞N，取代根节点root，而获得等价路径｛ni0，ni1，…，nim，nk｝，使（nim，nk）∈E，ω（nim，nk）＝ω1（nim，root），从而获得∀ni∈V且i≤N与SN节点集之间的k条不相交的路径，即图G是k点连通SN节点。图2表示k＝3时，图G与其简化图G1的关系。

图2 图G与其简化图G1间的关系

如果节点数很多时，基于简化图的k-FTDTC问题仍然是NP-难问题［19］，很难计算最优解，因此本文基于简化图G1提出一种分布式近似算法来进行求解。

2 容错性分布式拓扑控制算法设计

本文设计的k-FTDTC算法用到的参数定义如下：

flagi∶flagi为1表示节点ni确定了其最终发射功率，否则flagi为0；

di：简化图G1中节点ni当前的通信半径；

P（Dmax）：节点在最大通信距离下的发射功率；

F（ni）＿list：节点以P（Dmax）进行通信时，节点ni的邻居列表，包含邻居节点ID及节点间的接收信号强度，即F（ni）＿list＝｛F（ni）＿list＿ID，F（ni）＿list＿RSS｝；

G1（ni）＝（Vni，Eni）：节点ni的局部拓扑，其中

F1（ni）：节点ni在通信半径为di时的邻集，F1（ni）＝｛nj｜dist（ni，nj）≤di｝；

F2（ni）：在图G1（ni）中与节点nik点连通且不在其邻集F1（ni）中的节点集合，F2（ni）＝｛nj｜di＜dist（ni，nj）≤Dmax，且ni，nj在G1（ni）是k点连通｝；

本文提出的k-FTDTC算法基本思想是：通过信息交换，建立节点ni的邻居节点信息列表，并通过节点间的RSS进行排序，获得有序邻集F（ni）＿list；然后基于有序邻集F（ni）＿list分别计算获得和，由于任意节点ni若存在k条不相交的路径到达根节点root，则节点ni的发射功率最小能到达其k个邻居节点，因此定义节点ni的初始发射功率为；最后根据有序邻集，不断增加节点ni的发射功率Pi，使F（ni）＿list＿ID＝F1（ni）∪F2（ni），即F（ni）＿list中的任意节点nj属于F1（ni）∪F2（ni）。满足以上条件的发射功率Pi即为节点ni的最终发射功率，在保证任意节点k连通到根节点基础上，通过降低节点的发射功率，来优化网络能量消耗。

k-FTDTC算法具体包括3个部分：构建有序邻集，Pmini与计算和k连通构建。

2.1 构建有序邻集

网络中的所有节点依次以最大发射功率广播Hello消息，消息中包括节点ID。任意收到Hello的节点nj回复Response消息，Response消息中包括接收到的节点的ID以及其自身的ID。当节点ni接收到包含其自身ID的Response消息时，判定节点nj是否已在F（ni）＿list列表中。若不存在，则将节点nj的ID，以及节点和nj间的RSS存储于节点ni的邻集F（ni）＿list列表中，否则不做任何处理。最后对节点ni的邻集按照节点间的RSS非递增方式进行排序，获得有序邻集F（ni）＿list。

任意节点ni若存在k条不相交的路径到达根节点root，则节点ni的最小发射功率应能到达其邻集F（ni）＿list中最近的k个节点，因此节点ni保持k点连通的发射功率将会在和之间。CN节点的最大发射功率P（Dmax）通常已知，有序邻集F（ni）＿list列表中存储了节点ni接收到其邻居节点的信号强度，因此基于有序邻集F（ni）＿list，可以计算得到节点ni的和。计算公式如下：

式中，F（ni）＿list＿RSS［k］表示节点ni接收到距其第k远邻居节点的信号强度；｜F（ni）＿list｜表示列表中节点的数目。

2.3 k连通构建

k-FTDTC算法中k连通构建的基本思想是：任选一个节点ni，定义其初始发射功率为，根据有序邻集，在，］逐次增加节点ni发射功率，使其邻居节点F1（ni）逐个增加，当满足F（ni）＿list＿ID＝＝F1（ni）∪F2（ni）时，即获得ni的最佳发射功率，并向其邻居节点进行广播。

对于任意节点ni，基于上述思想进行k连通构建，确定其最佳发射功率，最多需要｜F（ni）＿list＿ID｜－k轮。在每一轮中，节点通过广播获得其一跳范围内节点的拓扑关系，同时节点ni利用有序邻集可自适应地获得其发射功率Pi每次调整的增幅Δp，Δp利用式（4）计算获得，从而保证每轮中至少有一个节点加入到F1（ni）中，提高了k连通构建的效率。

其中每一轮后，k的值进行自增，因此可知k值自增的次数与k连通构建进行的轮次一致。

本文设计的k-FTDTC算法的伪代码如表2所示。

表2 k－FTDTC算法伪代码

下面通过定理2对本文提出的k-FTDTC算法有效性进行证明。

定理2 若G1是k点连通root节点，则通过k-FTDTC算法对每个CN节点的发射功率进行优化分配后，G1仍是k点连通到root节点。

证明 由于G1是k点连通root节点，因此对于G1中任意节点nv，存在k条不相交的路径到达root节点，不失一般性，定义这k条不相交的路径为：r1，r2，…，rk。若定义任意节点ni的发射功率是通过k-FTDTC算法调整后获得的，其有序邻集为F（ni）＿list，假设nj是其有序邻集中的任意节点，若能证明节点ni的发射功率经调整后，被删除的任意边（ni，nj）不影响节点nv与节点k点连通性，则证明了本文所提出的k-FTDTC算法的有效性。

为了证明上述论断，分以下两种情况进行证明：

（1）被删除的边（ni，nj）不属于r1，r2，…，rk中的任何一条路径：由于边（ni，nj）的删除并不影响路径r1，r2，…，rk，因此节点nv与root节点仍然k点连通性。

（2）被删除的边（ni，nj）属于r1，r2，…，rk中某一条路径：不失一般性，假设被删除的边（ni，nj）属于路径rk，下面证明若k－1个节点被删除后，nv与root节点间仍存在可达路径。如果k－1个节点不是同时分别属于路径r1，r2，…，rk－1，则在r1，r2，…，rk－1路径中至少存在一条路径使nv与root节点可达，因此重点是证明被删除的k－1个节点分别属于路径r1，r2，…，rk－1时，nv与root节点仍存一条路径可达。由于被删除的k－1个节点分别属于路径r1，r2，…，rk－1，则通过路径rk节点nv与节点ni仍然相通，定义节点nv与ni之间路径为r1k；同时节点nj与root节点也是相通的，定义节点nj与root之间路径为；根据k-FTDTC算法，节点ni与nj是k连通的，即存在k路径相通，因此即使删除的k－1个节点属于该k条相通路径，但节点ni与nj仍存在至少一条路径连通，假设为。路径、、构成了节点nv与root间的一条连通路径，即rk＝＋＋。根据k点相通定义，节点nv与root节点为k点连通。

上述证明从理论上保证了每个CN节点利用k-FTDTC算法进行发射功率优化分配后，G1仍是k点连通到root节点。

3 仿真分析

采用MATLAB对算法进行仿真，并与经典的分布式拓扑控制算法DATC进行比较，以验证k-FTDTC算法的性能。DATC算法是分布式拓扑控制算法，该方法在每个节点位置已知的前提下，以最小化网络总功耗为目标，对节点发射功率进行调整以保证网络是k点连通的。由于DATC算法是通过构造有向图进行拓扑控制，因此算法相对复杂；其次该方法要求所有节点知道自身位置信息，适用性受限；最后该方法并没有对节点的最大发射功率进行有效约束，因此存在网络能量均衡问题。

本文主要采用3项性能指标对上述两种算法进行评价：①网络总功耗，即网络中每个CN节点发射功率之和；②最大发射功率，即经过拓扑控制后，所有节点中最大的发射功率，主要用来衡量网络节点间能量均衡和网络生命周期；③计算复杂度：HWSN进行拓扑控制，节点功率优化过程中，算法执行基本运算的数量。

3.1 仿真场景和参数设置

N节点随机部署在500m×500m的方形平面区域内，SN节点在预先设置的位置上部署，相邻节点间的通信满足式（1）定义的无线信道模型，算法仿真重复次数为100。具体的参数定义如表3所示。

表3 实验仿真参数

3.2 性能比较与分析

图3为依次改变网络中CN节点总数，当网络容错度k分别为2和4时，DATC算法和本文设计的k-FTDTC算法的网络总功耗比较。可以发现k-FTDTC算法的网络总功耗明显小于经典的DATC算法，这是因为k-FTDTC算法不仅以最小化网络总功耗为目标，还基于节点的有序邻集对节点的最大发射功率进行有效约束，因此节点功率优化效果更好。当网络容错度k从2增加到4时，整个网络总功耗也在增加，可见网络容错度的提高是以牺牲一定的网络能量为代价的。然而当网络容错度为4时，增加传感器节点数目，网络总功耗反而少量降低，这是因为容错度的提高意味着节点间链路的增加，对于链路密集的网络，虽然传感器节点数目的增加增大了网络总功耗，但是由于节点间距离的缩短也降低了节点的发射功率。

图3 网络总功耗比较

图4为DATC算法和本文设计的k-FTDTC算法的最大发射功率比较。可以发现基于节点有序邻集的k-FTDTC算法能够有效降低节点的最大发射功率，使节点间能量消耗更加均衡。并且，随着网络中传感器节点数目的不断增加，k-FTDTC算法对最大发射功率优化更为显著，能够有效延长大规模HWSN的网络生命周期。

图4 最大发射功率比较

图5为DATC算法和本文设计的k-FTDTC算法的计算复杂度比较。可以发现，不同传感器节点规模与不同容错度下，k-FTDTC算法的计算复杂度明显低于DATC算法。这是因为DATC算法是通过构造有向图进行拓扑控制，而本文设计的k-FTDTC算法是基于无向简化图，有效降低了算法的复杂度，使k-FTDTC算法更适合在计算能力受限的CN节点上运行。

图5 计算复杂度比较

5 结 论

在WSN中，除普通的CN节点外，通过有计划地部署少量能量丰富、通信能力强的SN节点，组成转发骨干网，可以有效增强网络连通性、降低数据转发延迟、提高网络可扩展性。基于上述异构无线传感器网络的容错性拓扑控制是一类NP-难问题，本文基于构建的HWSN网络模型提出了简化网络图构建方法，将NP-难问题进行简化，进行形式化描述。然后，通过构造节点的有序邻集来约束其发射功率，在保证网络k容错性的基础上最小化网络总功耗，提出了一个k容错性分布式拓扑控制算法。实验结果表明，本文所提k-FTDTC算法，相比经典的DATC算法，网络总功耗、节点的最大发射功率以及算法计算复杂度明显降低，从而验证了算法的有效性。

［1］Guidoni D L，Mini R A F，Loureiro A A F.On the design of resilient heterogeneous wireless sensor networks based on small world concepts［J］.Computer Networks，2010，54（8）：1266－1281.

［2］Yin R R，Liu B，Li Y Q，et al.Research on the fault-tolerant topology in energy heterogeneous wireless sensor networks［J］.Journal of Electronics ＆Information Technology，2012，34（9）：2180－2186.（尹荣荣，刘彬，李雅倩，等.能量异构无线传感器网络容错拓扑研究［J］.电子与信息学报，2012，34（9）：2180－2186.）

［3］Hajiaghayi M，Nicole I，Vahab S M.Power optimization in fault-tolerant topology control algorithms for wireless multi-hop networks［J］.IEEE Trans.on Networking，2007，15（6）：1345－1358.

［4］Rajiv M，Chittaranjan M.Rotation of CDS via connected domatic partition in Ad Hoc sensor networks［J］.IEEE Trans.on Mobile Computing，2009，8（4）：488－499.

［5］Zhao Y X，Wu J，Li F，et al.VBS：maximum lifetime sleep scheduling for wireless sensor networks using virtual backbones［C］∥Proc.of the IEEE INFOCOM，2010：71－75.

［6］Qi X Q，Ma S，Zheng G Z.Topology evolution of wireless sensor networks based on adaptive free-scale networks［J］.Journal of Information and Computational Science，2011，8（3）：467－475.

［7］Rossi K，Choong S H.Fault tolerant virtual backbone for minimum temperature in vivo sensor network［C］∥Proc.of the IEEE International Conference on Communications，2012：3394－3398.

［8］Renato E N，Celso C R，Christophe D.Optimal solutions for fault-tolerant topology control in wireless Ad Hoc networks［J］.IEEE Trans.on Wireless Communications，2009，8（12）：5970－5981.

［9］Calinescu G，Wan P J.Range assignment for biconnectivity and k-edge connectivity in wireless ad hoc networks［J］.Mobile Network Applications，2006，11（2）：121－128.

［10］Dai F，Wu J.On constructing k-connected k-dominating set in wireless Ad Hoc and sensor networks［J］.IEEE Trans.on Parallel and Distributed Systems，2006，66（7）：947－958.

［11］Cohen R，Kapchits B.An optimal wake-up scheduling algorithm for minimizing energy consumption while limiting maximum delay in a mesh sensor networks［J］.IEEE Trans.on Networks，2009，17（2）：570－581.

［12］Li N，Hou J C.Localized fault-tolerant topology control in wireless ad hoc networks［J］.IEEE Trans.on Parallel and Distributed Systems，2006，17（4）：307－320.

［13］Thai M，Zhang N，Tiwari R.On approximation algorithms of k-connected m-dominating set in disk graphs［J］.Theoretical Computer Science，2007，35（8）：49－59.

［14］Cardei M，Yang S H，Wu J.Algorithms for fault-tolerant topology in heterogeneous wireless sensor networks［J］.IEEE Trans.on Parallel and Distributed Systems，2008，19（4）：545－558.

［15］Gui J S，Liu A F.A new distributed topology control algorithmbased on optimization of delay and energy in wireless networks［J］.Journal of Parallel and Distributed Computing，2012，72（8）：1032－1044.

［16］Luo X J，Yu H Q，Wang X.Energy-aware self-organisation algorithms with heterogeneous connectivity in wireless sensor networks［J］.International Journal of Systems Science，2013，44（10）：864－877.

［17］Xu Y J，Qi H C.A fault-tolerant topology control algorithm for heterogeneous wireless networks［C］∥Proc.of the International Conference on Computer Science ＆Education，2012：1106－1109.

［18］Andrew Y W.Lower power RF transceiver modeling and design for wireless microsensor networks［D］.Massachusetts：Massachusetts Institute of Technology，2005.

［19］Nishiyama H，Ngo T，Ansari N，et al.On minimizing the impact of mobility on topology control in mobile Ad Hoc networks［J］.IEEE Trans.on Wireless Communications，2012，11（3）：1158－1166.

Algorithm for fault-tolerant topology control in heterogeneous and multi-hop wireless sensor networks

LIU Xing-chuan，WU Zhen-feng，ZHAO Ke-jian
（The 28th Research Institute of China Electronics Technology Group Corporation，Nanjing 210007，China）

Heterogeneous wireless sensor networks（HWSN）is a more practical network model because of an improved network performance such as a shorter data-gathering delay and lower network energy consumption.The kfault-tolerant topology control is a kind of NP-hard problem in the HWSN.The paper designs an approach of constructing network reduced graphs based on comprehensive analysis on the network model of HWSN.And the k-fault-tolerant distributed topology control（k-FTDTC）algorithm is proposed based on the ordered reachable neighborhood which is used to restrict the maximum transmission power of the nodes，with the objective of minimizing the total power consumption and preserving k-vertex fault-tolerant property.The experimental results indicate that the k-FTDTC algorithm not only reduces the computational complexity and improves network robustness，but also reduces the total network power consumption and the maximum node power consumption，as compared with the distributed adaptive topology control（DATC）algorithm.

heterogeneous wireless sensor networks（HWST）；topology control；ordered reachable neighborhood；fault-tolerant

TP 393

A

10.3969／j.issn.1001-506X.2015.08.28

刘兴川（1982－），男，工程师，博士，主要研究方向为WSN容错性拓扑控制、节点定位、数据融合。

E-mail：liuxch06＠163.com

吴振锋（1975－），男，研究员，博士，主要研究方向为传感网集成应用技术。

E-mail：wuzhenf＠163.com

赵克俭（1964－），男，研究员，主要研究方向为传感网／物联网应用技术。

E-mail：zhaokej＠163.com

1001－506X201508－1902－07

网址：www.sys－ele.com

2014－09－09；

2014－10－30；网络优先出版日期：2014－11－21。

网络优先出版地址：http：／／www.cnki.net／kcms／detail／11.2422.TN.20141121.0956.012.html

江苏省青年科学基金（SBK2014042581）资助课题