基于满Steiner树问题的水下无线传感器网络拓扑愈合算法研究

刘林峰，刘业

（1. 南京邮电大学 计算机学院，江苏 南京 210003；2.中国科学技术大学 苏州研究院，江苏 苏州 215123）

1 引言

地球表面71%被人迹罕至的水域（海洋、湖泊、河流）覆盖，出于科学探索、资源开采、污染监控、战术监视或海岸线保护等种种目的，人类对监测这些水域一直有着极大的兴趣。在无线传感器网络[1～3]（WSN, wireless sensor network）被应用之前，水下数据的感知和收集工作一般通过有线网络来完成，这种方式代价高昂并且需要大量工程技术辅助。适合水下环境的大量传感器节点协同工作，它们随机分布于监测水域，并通过基于声通信的无线方式自组织构成水下无线传感器网络[4～6]（UWSN, underwater wireless sensor network），不仅部署代价相对低廉，而且其分布式结构能够在水下监测应用中展现出更高的灵活度。然而，水下传感器网络的设计也面临着多方面的约束和挑战，主要表现在链接时延明显且多变、节点能量有限、带宽较低、误码率高等。此外，水下传感器节点极易受到各类外力（如海浪和海风扰动、水下生物触动等）影响发生位置迁移，甚至可能因此遭受毁坏，从而导致网络拓扑变化频繁、局部网络失效概率增高，如何愈合局部失效拓扑已成为该领域的研究热点之一。

部署于水域场景的水下传感器网络中应有4种节点类型：底面节点、浮游节点、自移动节点（AUV,autonomous underwater vehicle）[7]和汇聚节点，其中底面节点铺设于水域底面，由于水域底面地形异常复杂，可能会遭遇障碍地势而形成通信孤岛，该类节点受水域底面摩擦力影响所以位置迁移幅度较小，浮游节点依靠浮力装置悬浮在水中（悬浮深度与水域盐度、浮力装置属性相关），该类节点受外力扰动而位移的幅度较大，但发生位移待稳定后仍将处于相同悬浮深度的横切平面上，自移动节点具备自主的移动能力，能够按照某种策略进行位移，承担改善网络结构和自愈失效拓扑的重要作用。

在传统WSN中，由于一般不考虑自移动节点的存在，故通常采用调大节点功率的方式来愈合失效拓扑，该方式无法改变任何节点的位置，因此愈合过程很难改善拓扑性质，并极有可能造成拓扑性质恶化。水下传感器网络中的AUV节点具备移动能力，能够按照特定策略迁移至指定位置替代失效节点并承担其原角色，由该类节点进行的拓扑愈合不仅能够使得全局拓扑恢复连通性，还能通过改变节点原有位置的方式来改善全局拓扑，从而具有更高的实用性。目前关于水下传感器网络的拓扑愈合研究较为薄弱，多侧重于AUV节点设计或节点协作策略的研究，如文献[8]设计的Odyssey-class AUV能够到达水域的任意深度，可以修复失效的局部拓扑；文献[9]提出了一种节点间协作控制的网络管理模式，增强了网络的健壮性和自适应程度，能够有效地应对节点失效情况。然而，AUV节点迁移至何处才能达到拓扑愈合和拓扑优化的双重目标，该问题尚未见深入研究，尤其对于时延较大的水下环境，AUV节点迁移策略的研究将有助于全局拓扑优化、网络传输时延降低、能耗效率的提升，因此研究该问题很有必要。本文将针对时延敏感类水下应用（如水域战术监视、污染监控等），采用 AUV节点迁移修复拓扑的策略，提出一种能够降低传输时延和提高能耗效率的拓扑愈合算法。

2 网络模型及问题描述

2.1 模型构建

在实际应用场景中浮游节点和底面节点一般都扮演数据感知、采集和传输的角色，因此本文将该2种节点归为水下传感器节点。假定有S个汇聚节点、N个水下传感器节点和M个自移动节点随机均匀散布于监测水域，其中水下传感器节点携带有限能量的电池。水下传感器节点能够感知并发送监测所得数据，同时根据网络拓扑为当前传输辖域内的邻居节点提供报文接收和转发服务，随着数据流量的经由，节点的无线收发能耗和通信模块的闲时开销使得电池能量不断降低。初始工作状态时水下传感器网络由水下传感器节点保持全局连通，随后节点可能由于能量耗尽、外力作用等复杂因素而导致失效，就需要自移动节点来愈合拓扑。

抽象水下传感器网络拓扑为一个权重图G(V,E)，其中 V、E分别表示节点、链接的集合，V={n0, …, nS-1, nS, …, nS+N-1, nS+N, …, nS+N+M-1}，n0, …, nS-1表示汇聚节点，nS, …, nS+N-1表示N个水下传感器节点，nS+N, …, nS+N+M-1表示M个自移动节点；标记节点 ni的邻居集合为 Neighbor(ni)，数量为N(ni)；失效节点记作nf，替代该节点的自移动节点记作nAUV；对于任意i∈[S, S+N+M-1]，节点ni的当前能量记作e(ni)，节点ni的当前覆盖半径记作radius(ni)，所有节点拥有相同的最大传输范围R；节点ni的最大覆盖区域可以表示为cover(ni)={ nj| d(i,j)≤R and nj∈IR2}；定义网络连通函数connectivity(G)∶ G(V,E)→X，X为布尔逻辑数集合。若节点ni和nj之间存在通信链接则记作(i,j)∈E，链接(i,j)的距离记作 d(i,j)，其上时延记作 delay(i,j)，delay(i,j)[10]表示为式（1）所示形式。

其中，L表示数据分组大小，B表示数据传输率，Vp为水下声波传输速率。链接(i,j)上的能耗记作cost(i,j)如式（2）所示。

其中，ω为常系数，α为能量衰减指数，当在恶劣通信环境中或有障碍物时较大，据实验统计数据一般有α≥2。为便于模型的分析和描述，本文还给出如下假设：

假设 1 传感器节点的天线以全方位广播方式进行通信，且通信链接具有对称性；

假设 2 水下传感器网络的部署获得定位系统（如GPS）的辅助, 每个节点均获知自己及其邻居的地理位置；

假设 3 汇聚节点能量为+∞，自移动节点因位置移动发生的能耗忽略不计；

假设 4 节点发生失效前水下传感器网络拓扑已经为近似最优结构；

假设5 M＜＜N，因代价较高所以水下传感器网络中可供部署的自移动节点数量一般认为很少；

假设6 水下传感器网络的生命期[11]定义为在传感器网络系统的流量路由过程中，最先因电池能量耗尽而失效的节点生命期。

2.2 问题描述

当有节点发生失效后，拓扑结构可能不再满足全局连通性，此时应由自移动节点替代已失效的节点，与失效节点的单跳邻居连接，从而实现拓扑的重新愈合。水下传感器网络拓扑控制中时延和能耗是2个应予以首要关注的因素，因此当AUV节点愈合拓扑时也必须考虑这2个因素。就该问题而言，扮演替代角色的自移动节点的位置选取至关重要，自移动节点的迁移行为不仅能够恢复受损拓扑，更能改善受损拓扑的时延和能耗特性，故不应简单地让AUV节点迁移至失效节点位置，而应重新权衡并选取更为合适的位置，因此水下传感器网络拓扑愈合问题可归结为最优化网络拓扑的AUV节点位置选取问题。然而最优化全局拓扑需要网络尺度上的拓扑信息交互，这对于水下传感器网络而言是难以承受和异常复杂的。因水下传感器网络属于一种自组织网络，自组织理论[12]观点认为全局优化目标可以通过局部优化的叠加来实现（如基于局部视角的拓扑控制算法 LMST[13]），从而该问题可以近似地简化为通过选择AUV节点迁移位置来优化局部失效拓扑。位置选取问题可以映射到斯坦纳最小树(SMT, Steiner minimum tree)[14]问题，SMT问题寻求若干个Steiner点，使得与给定节点相连后能够生成最小连通网络。结合水下环境特点和水下传感器网络的设计目标，AUV节点的迁移位置选取需要考虑3项目标：恢复受损拓扑的连通性，愈合后局部拓扑的通信时延较小，愈合后局部拓扑的通信能耗较低。此外，由于水下传感器网络中汇聚节点是数据接收的终点，据定理1可知接近汇聚节点的传感器节点承担较多的通信负载，因此，AUV节点还应当偏向迁移至接近汇聚节点的位置，以分流部分通信负载，实现网络系统负载均衡的目的。这在 SMT问题中可以通过设置权重参数方式来进行调节，即赋予距汇聚节点近的邻居节点较高权重。

定理 1 在节点均匀分布的情况下，层次较低的节点可能承担的流量负载期望值较大。

证明 考虑汇聚节点唯一或多个[15]的情况，S=1时和S＞＞1时层次划分示意如图1所示，k表示节点所处的层次。

图1 水下传感器网络层次划分

不妨设水下传感器网络部署于 A×A的方形区域，采用节点可能需要提供直接转发或间接转发服务的节点数作为衡量负载期望值的指标，一般情况下可以视作第k层节点为第k+1及更高层节点提供转发服务。下面分别针对S=1和S＞＞1情况进行讨论。

1) 当S=1时，第k层节点所需承担负载的节点数期望值E(k)表示为式（3）所示。

2) 当S＞＞1时，第k层节点所需承担负载的节点数期望值E(k)表示为式（4）所示。

无论式（3）或式（4）中，k较小时E(k)较大，因此定理1得证。

连通性是传感器网络的获取并传输数据的基本要求，由于水下声通信的特性，水下传感器网络中传输时延和能耗要明显高于陆地部署的传感器网络，故本文将连通性、传输时延、传输能耗作为问题求解的主要目标。当理想情况下，所有节点的L、B和Vp都为相同的固定值，水下传感器网络拓扑失效的愈合目标obj可表述为如下目标：

目标1 connectivity(G)=1

目标2

目标3

目标2～目标3中ak、bk表示SMT中链接的权重，nu表示失效节点nf的邻居节点，k表示nu所属的层数。根据定理 1结论权重系数的设置应满足ak+1≤ak≤ak-1，bk+1≤bk≤bk-1。依据水下传感器网络的真实部署特点，水下传感器网络的拓扑愈合问题是一种特殊的SMT问题，主要表现在如下约束：

约束1 传统SMT问题只具有一个最小网络目标，而本研究中需兼顾时延和能耗2种因素，并且Neighbor(nf)在优化后均为SMT的叶节点，从而该问题演化为一种携带多目标的满Steiner树[16]；

约束2 广义上的SMT可能会选取多个Steiner点作为网络连接者，但是据假设5可知水下传感器网络中AUV数量极少，故在单次愈合拓扑时仅考虑使用一个AUV的情况；

约束3 为满足网络连通目标，AUV必须位于nf邻居的覆盖交集区域内。

综上分析，水下传感器网络拓扑愈合问题的一般形式化描述可归结为问题1。

问题 1 给定水下传感器网络拓扑对应的无向图 G(V,E)和一个可行的优化目标 obj，当出现节点nf发生失效后，由一个 AUV节点迁移至位置Pmove∩∈cover(nu)（其中nu∈Neighbor(nf)），使得Neighbor(nf)∪nf生成一棵满 Steiner树，并且该满Steiner树能符合目标1～目标3。

3 问题转化及近似算法

3.1 问题转化

满Steiner树问题难以对多目标进行优化，为了综合考虑目标2和目标3，本文提出一种描述节点ni和nj间时延和能耗的综合权值参数w(i,j)，给出其元素w(i,j)启发式的定义，如式（5）所示。

其中，β、γ为预设指数，权值 w(i,j)由 delay(i,j)和cost(i,j)2部分决定，由于 delay(i,j)和 cost(i,j)都与d(i,j)相关，且 L、B都为常量，故最终近似作w(i,j)∝d(i,j)δ（δ≥1）。此时问题1可以转化为问题2。

问题2 节点nf发生失效后，由一个AUV节点迁移至位置Pmove∩∈cover(nu)（其中nu∈Neighbor(nf)），使得ckw(u,AUV)最小，其中ck+1≤ck≤ck-1，k表示nu所属层数。

定理2 问题2是个NP-hard问题。

证明 满 Steiner树问题已被证明是一个 NP-完全问题[17]，问题2可以视作满Steiner树问题的一种特例，因此易证问题1也是一个NP-完全问题。

3.2 近似算法

为解决问题 2，本文设计了一种水下传感器网络拓扑愈合算法 TRA(topology recovery algorithm of underwater sensor network)。TRA算法的主要思想是：首先为所有 nu∈Neighbor(nf)在∩cover(nu)域内映射到各自的最优 Steiner位置（记作Steiner(nu)），再对各Steiner点使用质心量算方法获得近似最优解 Pmove。TRA算法具体按照如下步骤1～步骤5进行。

步骤1 当nf失效后，判断nu∈Neighbor(nf)之间是否能够恢复连通，如能则采用TCS-CA算法[18]恢复连通性，否则转至步骤2。

步骤2 计算∩cover(nu)（如图2（a）所示阴影部分区域），若∩cover(nu)域为一个点，令AUV节点迁移至nf，否则转至步骤3。

步骤3 依据式（6）从nf的邻居节点分别映射至交集区域（如图 2（b）所示），令映射点所属层次与邻居节点一致，转至步骤4。

Steiner(nu) = { P| P∈∩cover(nu) & min(w(u,P))} (6)其中，w(u,P)表示节点nu与位置P间的权值。

图2 TRA算法

步骤 4 赋予较低层次邻居的映射点以较高的权重参数，采用质心量算方法计算近似最优位置Pmove，Pmove的表达式如式（7）所示。将 AUV节点移至Pmove，转至步骤5。

其中，du表示邻居nu所对应映射点的权值，nu所属层数越小则权值越大，并对权值进行了归一化处理，即令根据步骤 1～步骤 4描述，有定理3成立。

定理3 Pmove必在∩cover(nu)域内。

证明 ∩cover(nu)是 N(nf)个半径为 R 圆的交集，Steiner位置都位于∩cover(nu)域的边界，按照逆时针（或顺时针）顺序连接各Steiner位置，生成的多边形为凸多边形，可以证明每个内角均小于π。角度大小由连续3个点位置决定，因此该结论可以分以下3种情况进行讨论。

情况1 连续的3点在同一圆弧上，此时该角必小于π。

情况2 3点位于2条不同圆弧上。不妨设点A、B位于同一圆弧，点 C位于另一圆弧，假设∠ABC≥π，如图3（a）所示。此时显然有|CO|＞R，根据∩cover(nu)定义可知应有|CO|≤R，故不可能出现∠ABC≥π。

图3 凸多边形的内角生成情况

情况3 3点位于3条不同圆弧上。如图3（b）所示，假定A、B分别位于2条圆弧，则根据∩cover(nu)定义和多边形生成顺序可知点C必定位于图中阴影区域，BC’为圆弧在 B点处切线，因此有∠ABC＜∠ABC’＜π。

所以，生成的多边形中所有内角均小于 π，该多边形为凸多边形。凸多边形内所有点构成的点集合是一个凸集，凸集具有如下性质[19]：设X为向量空间，集合S⊆X是凸集，当且仅当任意xi∈Set，yi≥0，及，i=1,2,…,n，有成立。据该性质及式（7），因 Steiner(nu)为多边形顶点，属于该凸多边形集合，故 Pmove必在凸多边形内部，定理3得证。

步骤5 AUV节点通过设置自身功率，以确保能与最远处的nf邻居进行通信，同时调整邻居节点功率大小以确保链接的双向性，从而全局连通性得以恢复。

根据TRA算法的伪代码描述，TRA算法的时间复杂度与失效节点的邻居数有关，一般而言，当水下传感器网络部署规模很大时，邻居数可视作log(N)。TRA算法的实现需要的额外代价与拓扑失效的具体情况相关，若单跳邻居能够通过扩大功率自愈，则最大代价为O((logN)2)；若无法直接愈合，则需要自移动节点修复拓扑，此时代价与邻居数相关，故TRA算法实现代价为log(N)。

4 实验分析

本文利用OMNeT++[20]平台设计了一个仿真程序，程序自上而下由应用层、路由层、拓扑控制和MAC层4个模块构成，其中路由层采用基于最短路的路由算法FA[21]，拓扑控制模块实现了LMST[13]和拓扑愈合算法TRA。实验环境如下：N个源节点随机均匀散布于600m×600m的正方形区域，S个汇聚节点均匀分布于水平面，源点初始能量为 e，以速率 v（服从正态分布 v～N(μ,σ2）获取到兴趣数据分组。当随机生成的节点位置无法满足连通则忽略并重新生成节点位置；不考虑AUV节点移动能耗，当 AUV节点迁移愈合网络后即视作能量为 e的普通节点；并且忽略节点接收报文及处理器的能耗。当水下传感器网络满足以下3个条件则终止本次仿真：出现失效节点；失效节点的邻居无法自愈拓扑连通性； AUV节点数量耗尽。用于和TRA算法比较的2种算法分别是：不采用拓扑愈合的策略，当节点出现失效生命期即终止，以下简称NONE算法；愈合拓扑时简单地把AUV节点移至nf，以下简称SIMPLE算法。实验结果均为500次的平均值，主要参数如表1所示。

4.1 实验1

本实验通过不断改变源节点数N（从100变化至500）的取值，观察自移动节点数M（分别为2，4，8，10）的变化对TRA算法所得到路径平均时延和单位时间节点平均消耗能量的影响，路径平均时延指所有源节点到汇聚节点发送数据分组过程中产生时延的均值，单位时间节点平均消耗能量指在整个网络生命期内单个节点传输数据所产生能耗的单位时间均值，变化曲线分别如图4（a）和图4（b）所示。从图4可以观察到以下3个现象：图4（a）表明随着源节点数增长（节点分布趋于密集）路径平均时延出现增长的趋势，这是因为当源节点更为密集时，源节点到汇聚节点的路径上每跳距离会相对减小，但总跳数会增加，而每跳都需计入时延，该因素占据主导作用，所以造成路径平均时延的增长；图4（b）显示随着源节点数增长单位时间节点平均消耗能量会呈现出逐渐下降趋势，这是由于节点分布密集使得每跳距离减小，而单跳距离减小能使能耗显著降低，因此节点进行传输或转发时所产生能耗也将降低；从图4还不难发现，当自移动节点数增加时，路径平均时延和节点平均能耗都会降低，这是因为当自移动节点数增加后，能对更多失效节点位置起到优化作用，从而将对全局拓扑改善起到更为明显的影响。

表1 实验参数

4.2 实验2

图4 源节点数和自移动节点数对时延和能耗的影响

图5 TRA与SIMPLE的平均路径时延比较

为了验证TRA算法中计算Pmove的必要性，本实验将比较TRA和SIMPLE算法的路径平均时延指标，曲线如图5所示。图5表明TRA算法中把AUV节点迁移到位置Pmove能够在一定程度上改善网络的时延指标，与SIMPLE相比最高处路径平均时延减小了0.15s，因此对于时延较为敏感的水下传感器网络应用是较为适用的。本实验还比较算法TRA与SIMPLE的单位时间节点平均消耗能量，如图6所示，图6反映了采用算法TRA所得到的单位时间节点平均能耗一直小于 SIMPLE，此外随着源节点数增长TRA和SIMPLE的差距在逐步缩小，这是因为随着N增大时M并未发生改变，即自移动节点数所占比重会逐渐下降，此时通过自移动节点迁移来改善全局拓扑的能力将会相对下降。

图6 节点平均能耗比较

4.3 实验3

本实验通过改变自移动节点数量和节点初始能量，观察网络生命期的变化情况，曲线如图7所示。图7印证了自移动节点数增多和节点初始能量的增大有助于网络生命期的增长。此外，3条曲线随着自移动节点数增长而生命期增幅呈现出逐步减小的趋势，这是因为自移动节点数在水下传感器网络中占据一定比例时，随着时间推移水下传感器网络中会出现越来越多的潜在失效节点（能量趋近于 0的节点），而自移动节点数是相对较小的，无法愈合所有的潜在局部失效拓扑，因此通过愈合拓扑来延长生命期的能力受到了制约。本实验还比较了TRA、NONE与SIMPLE 3种算法的网络生命期，如图8所示，图8说明以下2个现象：随着源节点数增长，3条曲线的网络生命期都呈现出上升势态，该现象可用实验1的结论来解释，因为当源节点增多时节点平均能耗会降低，所以网络生命期会增长； TRA和SIMPLE所获得网络生命期远高于未采用拓扑愈合策略的NONE算法，另外采用TRA所获生命期要高于SIMPLE，最高处当N=500时可达649s。

图7 自移动节点数对网络生命期的影响

图8 3种算法的网络生命期比较

5 结束语

本文设计了一种基于满 Steiner树问题的水下传感器网络拓扑愈合算法 TRA。TRA算法适用于时延敏感的水下无线传感器网络，并且在自移动节点的迁移位置选取过程中考虑了高效能耗问题。对于 TRA算法还有着以下几个方面的补充和考虑之处：水下环境一般认为是一种三维环境，TRA算法虽然是基于二维环境建模，但本文中若干结论（如定理3等）在三维环境依然成立，算法设计也很容易推广至三维环境；水下传感器网络是一个多模块组成的复杂系统，模块间的协同是一个不容忽视的重要问题，如何使得拓扑愈合与其他模块良好协作也是 TRA应继续改进的方向；此外，水下传感器网络通常部署于恶劣环境，因此很多理论上的假设前提未必能得到满足，例如节点的移动性以及节点的信号覆盖范围有可能为不规则图形，所以 TRA的设计还应有机结合应用场景和实际部署环境，这样才具有更高的实用价值。

[1] AKYILDIZ I F, SU W, SANKARASUBRAMANIAM Y, et al. Wireless sensor network∶ a survey [J]. Computer Networks, 2002, 38(4)∶393-422.

[2] ELSON J, ESTRIN D. Sensor Networks∶ a Bridge to the Physical World[M]. Norwell∶ Kluwer Academic Publishers, 2004. 3-20.

[3] 崔莉，鞠海玲，苗勇等. 无线传感器网络研究进展[J]. 计算机研究与发展, 2005, 42(1)∶163-174.CUI L, JU H L, MIAO Y, et al. Overview of wireless sensor networks[J]. Journal of Computer Research and Development, 2005,42(1)∶163-174.

[4] AKYILDIZ I F, POMPILI D, MELODIA T. Underwater acoustic sensor networks∶ research challenges[J]. Ad Hoc Networks, 2005, 3(3)∶257-279.

[5] AKYILDIZ I F, POMPILI D, MELODIA T. Challenges for efficient communication in underwater acoustic sensor networks[J]. ACM SIGBED Review, 2004, 1(2)∶ 3-8.

[6] HEIDEMANN J, YE W, WILLS J, et al. Research challenges and applications for underwater sensor networking[A]. Proc of the 1st ACM International Workshop on Underwater Networks[C]. New York,2006. 33-40.

[7] AKYILDIZ I F, POMPILI D, MELODIA T. State-of-the-art in protocol research for underwater acoustic sensor networks[A]. Proc of the 1st ACM International Workshop on Underwater Networks[C]. New York, 2006. 7-16.

[8] CHRYSSOSTOMIDIS C. AUV laboratory at MIT sea grant[EB/OL].http∶//auvlab.mit.edu/, 2009.

[9] PETER Ö, EDWARD F, NAOMI E L. Cooperative control of mobile sensor networks∶ adaptive gradient climbing in a distributed environment[J]. IEEE Transactions on Automatic Control, 2004, 49(8)∶1292-1302.

[10] IBRAHIM S, CUI J H, AMMAR R. Surface-level gateway deployment for underwater sensor networks[A]. Proc of Military Communications Conference 2007[C]. Sanfrancisco, CA, 2007. 1-7.

[11] CHANG J H, TASSIULAS L. Maximum lifetime routing in wireless sensor networks[J]. IEEE/ACM Transactions on Networking, 2004,12(4)∶ 609-619.

[12] 吴彤. 自组织方法论研究[M]. 北京：清华大学出版社, 2001.WU T. Self-Organizing Methodology[M]. Beijing∶ Tsinghua University Press, 2001.

[13] LI N, HOU J C, SHA L. Design and analysis of an MST-based topology control algorithm[A]. Proc of Twenty-Second Annual Joint Conference of the IEEE Computer and Communications Societies(INFORCOM 2003)[C]. Sanfrancisco, CA, 2003. 1702-1712.

[14] 越民义. 最小网络——斯坦纳树问题[M]. 上海∶ 上海科学技术出版社, 2006.YUE M Y. Minimum Network-Steiner Tree Problem[M]. Shanghai∶Shanghai Science and Technology Press, 2006.

[15] ALSALIH W, AKL S, HASSANEIN H. Placement of multiple mobile data collectors in underwater acoustic sensor networks[A]. Proc of IEEE International Conference on Communications, ICC 2008[C].Beijing, 2008. 19-23.

[16] BORCHERS A, DU D Z. The k-Steiner ratio in graphs[A]. Proc of the Twenty-Seventh Annual ACM Symposium on Theory of Computing[C]. Las Vegas, USA, 1995. 641-649.

[17] MARTINEZ F, PINA J, SOARES J. Algorithm for terminal Steiner trees[J]. Theoretical Computer Science, 2007, 389(1)∶ 133-142.

[18] 刘林峰, 吴家皋, 邹志强等. 面向节点失效问题的传感器网络拓扑自愈算法[J]. 东南大学学报（自然科学版），2009, 39(4)∶695-699.LIU L F, WU J G, ZOU Z Q, et al. Topology control self-cure algorithm aiming at node failure problem in wireless sensor networks[J].Journal of Southeast University(Natural Science Edition), 2009, 39(4)∶695-699.

[19] 徐玖平, 李军. 多目标决策的理论与方法[M]. 北京∶ 清华大学出版社, 2005.XU J P, LI J. Multi-Objective Decision Theory and Method[M]. Beijing∶ Tsinghua University Press, 2005.

[20] ANDRAS VARGA. OMNeT++ -discrete event simulation system user manual[EB/OL]. http∶//www.omnet.org/, 2008.

[21] CHANG J H, TASSIULAS L. Energy conserving routing in wireless ad-hoc networks[A]. Proc of IEEE INFOCOM [C]. Tel Aviv, Israel,2000. 22-31.