传感器网络中继节点扩展部署的优化算法研究

曾斌，魏军，姚路

（海军工程大学 信息管理研究室，湖北 武汉 430030）

1 引言

近年来传感器网络作为一种新兴技术得到较大发展，在军事侦察、环境监测、目标跟踪、灾难救援等方向显示了很大的应用价值。它是一种由大规模、低成本、能量受限的微型传感节点部署形成的网络。传感器网络的部署方式一般包括随机性部署（由飞机随机抛洒）和确定性部署（人员或车辆定点安装）2种。

由于传感节点的轻型电池很难被替换和充电，因此网络的能量消耗是无线传感器网络一个很重要的指标。带来能耗的一个重要原因是无线通信，源节点和目标节点的通信距离越远，能耗越大。以LEACH为代表的分簇路由协议在网络运行时通过形成层次化结构，周期性地选择当前能耗较低的节点充当簇头即最上层中继节点，从而达到负载均衡和降低能耗的目的。但这种方式在簇的形成及变动过程中需要不少的传输开销[1]，而且从普通节点到簇头同样需要考虑利用中继节点进行转发。

为此提出部署中继节点来降低簇头能耗，中继节点可以由一般传感节点担任，也可采用功能和能源更强大的硬件，它的主要功能就是转发远距离传感节点之间的数据，负责传输的数据流量及频度远超过一般传感节点，所以它的能耗速度会大于其他节点，由此可见作为网络生命周期的瓶颈，中继节点的部署位置非常关键，合理的部署可以明显减少传感节点的传输能耗，从而提高整个网络的生命周期。现有的方法是在网络部署前，以提高网络生命周期或覆盖率为目标函数，采用规划算法等技术优化传感节点和中继节点的部署数量和位置。但它的缺点是当网络运行时，如果传感数据的流量发生变化，可能造成某些中继节点能耗突然加大，这时这种初始部署方案可能失去预想的效果，需要进行后续部署。

但周期性后续部署需要人工或抛洒装备到指定位置安装新节点，存在开销大和实时性弱的问题，而且同样需要给出添加的节点位置。因此很有必要设计一种中继节点扩展部署方法对以上2种方式进行补充，在初始部署时，采用成本较低的网络节点实现中继功能。在网络运行过程中，如果中继节点发生超载时，无须成簇结构的支持，综合考虑节点位置、带宽及能耗等限制因素，通过本文算法选择合适的新增中继节点部署区域，如果该区域存在负载轻的传感节点或冗余的后备中继节点，则由其接管过载流量，否则也能够为后续部署时指明中继点安装位置，从而达到平衡中继节点负载的目的。

中继节点的扩展部署问题包括3个方面。①带宽受限问题。如果选择普通节点作为补充中继节点，由于功率有限，转发的流量不能超过带宽限制，而现有研究主要集中在能量受限上，对带宽受限研究甚少[2]。②节点定位问题。位置选择需要结合节点定位信息才有实际意义，由于传感器尺寸小，计算资源和能量资源极大受限，现有的许多定位技术（如GPS）很难直接使用，例如对于部署在复杂环境（如海洋、山地、战场环境）的传感节点。为了提高精度，往往需要在网络中传播多个锚节点（anchor）的定位数据，再利用诸如多维定标算法等技术把多维测量数据映射到二维或三维空间，这种方式涉及矩阵浮点运算，计算量大，误差也较大，需要尽可能避免[3]。③处理能力受限问题。由于传感节点计算能力有限，所以算法的复杂度不能太高。

根据已有的文献，现有中继节点的研究主要集中在解决预先部署问题，而对中继节点扩展部署的研究不够深入。而预先部署假设数据流量稳定，但在网络运行过程中，作为网络流量瓶颈和网关，如果数据流量发生变化，某些中继节点需要转发的数据负载较重，这时不做调整可能会导致严重的网络拥塞及分组丢失，甚至会过早消耗完能量而死亡，引起整个网络瘫痪。而成簇路由协议主要考虑层次结构中顶层中继节点（簇头）的负载平衡，开销较大。为此，针对中继节点的特点，提出了一个中继节点在线扩展部署算法，对中继节点进行负载平衡，即当现有某中继节点过载后，选择合适位置新增中继点，共同转发过载的数据流量，这样降低了作为网络瓶颈的中继节点的能耗速度，从而延长整个网络的生命周期。该算法面对第一个问题，在优化算法的约束条件中加入带宽限制（见3.2节）进行优化。对于第2个问题，直接利用锚节点的定位测量数据，避开开销大的降维计算，把传感节点看做是由d个锚节点构成的d维欧氏空间的节点，以传输距离作为衡量能量消耗的性能指标，计算出以各个传感节点为中心的d维信号传输球面的相交区域，从中搜索适合的候选中继节点位置，传输球面的半径为传感节点到中继节点的距离。算法最坏情况下的计算复杂度为O(md+1)，其中，m为将要指派给新增中继节点转发数据的传感节点数量，并进一步提出了优化方法，可以在大多数情况下把计算复杂度降为 O(m)，以解决传感节点处理能力受限问题。

本文第2节讨论相关工作；第3节给出了问题定义，并证明了算法所需的数学定律；第4节描述了中继部署算法；第5节讨论了算法的复杂性并提出了优化方法；第6节给出了仿真实验结果及分析；第7节为结束语。

2 相关工作

利用中继节点提高网络性能是目前传感器网络领域的研究热点之一。中继节点通过事先设计的布放位置来优化网络拓扑结构，从而达到提高网络性能的目的。根据中继节点和传感节点的传输距离不同，解决方法也不同，当前主要方式是以中继节点作为路由路径上的网关或转发站，建立面向连接或生命周期的目标优化函数，通过部署平面或层次化网络结构进行求解。而且对中继节点的能力要求也不一样，在平面网络结构中中继节点可以用普通传感节点代替，而在层次化网络结构中作为传感节点的网关，中继节点的传输半径要高于一般传感节点。平面网络结构中传感节点可以转发其他节点的数据，但在多层中继部署的网络结构中，传感节点只能把数据发送给中继节点或基站，不能转发其他节点消息。而设计兼有平面结构和分簇结构优点的新型数据传输模式，是目前很重要的研究方向[4]，这也是本文研究的努力方向。

文献[5]把中继节点部署问题分割为2个NP难问题:网络维护问题和网络修复问题。为了解决网络维护问题，以Fiedler值作为网络连接度指标，以中继节点的位置坐标作为决策变量，通过构造分层的半正定规划函数来进行求解，但网络规模受到限制，仿真实验在 50个传感节点左右才能取得较好效果。在此基础上提出了一个自适应的启发算法来求解网络修复问题，改变中继节点位置来提高网络连接度，但中继节点的移动需要消耗大量能量，以牺牲能量来提高连接度的办法值得商榷。为了进一步降低能耗，提出了一个“加权最小能量路由”算法来平衡传感节点和中继节点之间的负载，这需要对网络路由协议进行修改。从文中可以发现中继节点的再部署及负载平衡对降低能耗具有重要的影响。

文献[6]通过 Vorinoi图把传感区域分区（即Voronoi单元），以Voronoi单元的交集作为中继节点候选位置，并提出一个选择算法最小化所需中继节点的数量，该方法仅用于随机部署，而且没有考虑中继节点过载问题。文献[7]把布放区域划分为等大小的单元网格，把优化问题转换为选择可以放置中继节点的单元格，并通过启发算法求解最少的候选单元格来优化中继节点的数量。文献[8]和文献[9]针对确定性部署问题，寻找最少数量的中继节点以满足网络生命周期和连接度的要求，该问题等效于最小覆盖集问题，针对该NP难问题，提出了一个回归算法计算次优解。与文献[6]类似，该算法首先求解传感节点传输区域的交集，并把中继节点放置在拥有较多数量传感节点的交集中，以此来最大化中继节点能够服务的传感节点数量。文献[6～8]给笔者的启发是通过搜索传感节点传输区域的交集，可以简化候选中继节点部署区域的优化选择过程。

文献[10]对影响中继节点负载平衡的相关因素进行了分析，发现如果能够控制节点间传输距离，通过最短路径法即可取得较好的负载平衡，并提出了一个基于中心度的能量控制策略。文献[11]把中继节点部署问题转换为一个欧氏 Steiner最小树问题（ESMT），并提出了一个考虑能量平衡的混合算法求解。从文献[10,11]可以发现中继节点能量平衡的重要性，减少传感节点和中继节点之间的传输距离对降低能耗具有较大作用。

以上文献关注于对中继节点的预先部署，当网络运行过程中流量发生改变，导致中继节点能耗变化时，预先部署则需要调整。现有研究主要集中在采用移动节点方式进行扩展部署[12]，但这种方式中继节点的成本较高，能量消耗大。在层次网络结构中，簇头可以看作中继节点的最上层，分簇路由协议为了平衡簇头负载作了大量研究，例如文献[13]提出采用多簇头方式共同承担簇头任务，但簇的形成和维护需要消耗大量能量。文献[14]为了解决传感器网络的流量拥塞问题，提出了一种动态的中继节点部署机制来调整路由，首先识别出拥塞区域，然后添加新的中继节点绕开拥塞区域，但如前文所述，传感器网络中直接添加新的节点开销太大，而本文重点考虑利用现有冗余节点或负载较轻节点来作为新的中继节点。CODA算法提出了一种拥塞发现及控制算法[15]，它的拥塞发现机制可以发现过载区域及节点，但它是通过抑制源节点发送数据来实施拥塞控制，而本文是通过增加新的中继节点进行负载平衡来减轻拥塞。本文算法适用于平面和层次网络结构，可以利用现有负载较轻节点作为新的中继节点来减轻超载中继节点的能耗，并进一步提供了对多维定标的支持。

3 问题描述

在多维定标环境下传感器网络中的每一个传感节点都可用d维欧氏空间中的顶点表示，这样欧氏空间中两点之间的距离可以表达维传感节点之间的传输距离。为此需要定义传感节点−中继节点的指派规则来表示传感数据的转发关系:为了减小能耗，中继节点的位置应该尽可能靠近传感节点群，传感节点选择传输距离内最近的中继节点转发数据[16,17]。每个中继节点存在自己的“责任区”，责任区内传感节点s距中继节点r的距离要小于s与其他中继节点的距离。采用“就近指派”规则的原因有3条。

1) 大部分路由协议采用该规则，传输能耗受传输距离的影响最大，距离越远，能耗越大。

2) 简化中继节点与传感节点之间的关系，便于找出初始的最优布置区域。

3) 系统容错性强，当某个中继节点失效退出网络后，传感节点可自动选择次近的中继节点。

当然某些复杂的路由协议定义的指派关系也比较复杂，但本文的算法只需做相应改动即可适应。为了简化起见，本文的指派规则为就近指派。为了延长网络生命周期，中继节点需要避免超负载工作。当某个中继节点超负载时，在它附近选择一个新的中继节点来承担过重的负载。按照就近指派规则，超载工作的中继节点上部分信息将转交新的中继节点发送，本文主要研究如何选择合适部署位置的节点作为补充的新中继点。

3.1 理论背景

中继节点部署问题可被转换为欧氏空间中的集合问题，其中，中继节点和传感节点都表示为顶点，通过节点间相互约束关系可计算出包含候选中继节点位置的空间区域。

d维空间ℝd中任意2点x，y间传输距离为dist(x, y) =。d维闭合球体Br(p)（半径r≥0，中心点为p）定义为Br(p)={x:dist(x, p)≤r}。ℝ1中闭合球体为线段，ℝ2中闭合球体为一个圆盘。

ℝd中(d−1)维球面Sr(p)（半径r≥0，中心点为p）定义为Sr(p)={x:dist(x,p)=r}。二维球面为三维空间的普通球面或单点，一维球面为一个圆或单点，0维球面就是直线上的2个点或单点，ℝd中(d−1)维球面也被称为超球面。d维球体集合{Bi:i=1,…,n}把空间划分为区域，所以区域可被定义为，每个区域都包含有自己的边界。为了表示传感节点的数据负载，给每一个球体Bi定义了一个属性−权重W(Bi)。因此区域 A =Bi的权重为包含它的所有球体权重的总和，即 W( R ) =∑ W( Bi)。

本文中传感节点的传输范围以球体表示，节点位置用特征点表示，传输的数据负载以权重表示。例如图1中4个二维球体，权重分别为2、4、8和16，把整个空间划分成 10个区域，图中黑点为特征点，即多个球面的相交点或部署点。下面介绍本文需要用到的3个定理。

图1 传输球面示例，A的区域划分

定理1 如果dℝ(d＞1)中至少2个不同球面的相交区非空，则该相交区为一个k维球面(k＜d−1)。

证明 可由文献17的定理3.6直接得证。

定理2 如果S为d个(d−1)维球面的非空相交区，则其中有(d−1)个球面的相交区仍为S，否则S为0维球面。

证明 设S1，…，Sn为(d＞1)维球面，根据定理1，S1和 S2的相交区为 S1（S1和 S2相同），或者为一个低维球面 S1'（维度小于 d−1）。如果为前者，可以去掉S1，则定理成立。对于后者，进一步考虑S1'和S3的相交区，同理可以去掉S3，或者得到一个维度低于S1'的球面S2'，如果在前面d−1步不去掉任何一个球面，最后Sd-1'=S的维度为零。

定理3 设A为一组球体B划分的区域集合，对应B的球面集合为U，对于A中的任意一个区域a，存在一个U的相交区，它被a所包含，否则该相交区为零维球面且必有一点在a内。

证明 设U的相交区集合为S，对于a∈A，设sa为S中与a有相交点的最小维度球面。下面采用反证法进行证明，如果sa的维度大于0，则sa⊂a。如果该命题非真，即可找到一个区域 a∈A，使得sa⊄a。这意味着sa球面中至少一个点在a内，同时又至少有一个点在a外，这表明Sa与a的边界相交，而a的边界被定义为a与U中球面的相交区，换句话说，sa与U中某球面的相交区上有一点在区域a的边界上。根据定理 1，该相交区为一个维度低于sa的球面，这与sa为最小维度的假设矛盾，所以定理得证。

3.2 问题描述

传感器网络中包含2类节点:传感节点和中继节点。每一个传感节点指派一个中继节点。中继节点可为多个传感节点提供服务。传感节点和中继节点都存在于dℝ空间中，传感节点之间的距离可以通过多个锚节点测量得出。

传感节点—中继节点的指派规则为就近分配，换作计算几何学的术语，即中继节点为处于它的Voronoi区域的所有传感节点提供转发服务。节点n的Voronoi区域由离n的距离相较空间中其他节点更近的节点构成。

传感节点在传输数据时需要通过中继节点转发，传感器网络中每个节点在单位时间内能够转发的数据有限，该限度即为它的容量（带宽）。传感节点的传输数据量和中继节点的容量在本文中以正实数表示，一个中继节点所分配的传感节点传输数据量不能超过它的当前容量。

假设某中继节点rol过载，需要加入一个新的节点rad接管部分指派给rol的传感节点。因此问题转换为计算 rad的位置坐标，使其能够接管合适数量的传感节点，即 rad需要满足以下 2个带宽受限的约束条件:

1) rad转发的总数据流量不能超过它当前的最大容量；

2) rad从rol接管的流量不能小于rol的过载流量。

有关过载节点和区域的发现及传播算法已有大量研究[14,15]，非本文研究重点，为简便起见，本文以流量阈值作为超载的判别准则。当然 rad增加的流量负载不仅包括从rol上接管的负载，也要考虑从其他中继节点接管的负载，由于rad的流量限制，该问题也可能无解。下面计算节点吞吐率（处理的总数据流量）与能耗率的关系。相距为r的2个节点收发kbit/s的数据所消耗的能量为

其中，δ为路径衰弱系数，α1、α2和 β为电路相关参数。对于第i个中继节点ri，它当前所转发的总数据流量与能耗率ERi之间满足下式:

kij为 ri到下一跳中继节点rj的流量。式(2)反映了中继节点所能处理的数据流量、传输距离及能耗率三者之间的关系，在传输距离一定的情况下，通过调整数据流量的分布，可以使得能耗率达到平衡。

为了更加清楚地描述问题，给出以下定义。每一个传感节点n的传输球体B(n)以n为中心，以n到所分派中继节点的距离为半径。节点n的球面为B(n)的边界。B(n)的权重代表 n的发送数据流量。定义A为整个部署区域所有传感节点的传输球体组成的空间集合，A(r)为分配给 r的传感节点传输球体组成的空间集合。因为A(r)为A的子集所组成，所以 A中任一个区域必然被 A(r)中的一个区域包含。A(r)和A中的任意一个区域都将具有一个权重属性。

如果A中某个区域的节点rad被选择作为中继节点，那么分配给rol的节点所产生的负载等于该区域的权重。如果属于 A(rol)的某个区域中产生一个新的中继节点，那么从rol上被接管的负载等于该区域的权重。因此，产生 rad的合适位置应该属于 A中权重小于rad带宽的某区域，同时也属于A(rol)中权重大于rol过载流量的某区域，这也是本算法的核心思想。

下面通过图示来说明。图1和图2为一个二维传感器网络，分别表示A和A(rol)的区域划分，它们包含2个中继节点rol和rad，带宽均为9（为了不失一般性，这里假设中继节点和传感节点能力相同），4个传感节点n1、n2、n3、n4，发送流量分别为2、4、8和16。其中，n1、n2、n3分配给rol，由其转发数据，n4分配给rad。图3(a)给出了A中所有区域及其附属权重，它包括10个区域（a1～a10），它们由 B(n1)至 B(n2)共 4 个传输球体的交叉区和互补区域组成。图2给出了由B(n1)、B(n2)和B(n3)（属于rol的节点传输球体）交叉建立的区域集合 A(rol)，其中 a2和 a6同时属于 A和 A(rol)。

示例中，因为n1、n2、n3的总流量为14，所以rol超载，过载流量为5。从问题约束条件1可知，rad新增负载不能超过其带宽，所以 rad适合的位置为 a1、a2、a3、a4和 a6，为了满足约束条件 2，即保证过载的流量能够从rol接管，从图2可以看出适合rad的位置应该为a6、a13和a14，所以应该在区域a4（a13的子集）和a6中的节点中挑选rad，从图2中可以看出n3节点最为合适。

图2 A(rol)的区域划分

4 中继节点扩展算法

本算法思路如下:设rol为超载中继节点，这时遍历A空间所有区域a（后文介绍优化方法）。如果A(rol)中有一区域aol包含a，则检查aol和a的权重是否满足得到有效解的2个条件，当发现有(aol, a)满足条件，则算法结束，新增节点 rad为 a中剩余能量最大的节点。判断 aol是否包含 a的算法比较简单，在4.2节将介绍如何在a中找到具有合适权重的区域。

算法的重点是如何高效地遍历A中所有区域，直接的做法是计算所有传感节点的子集，检查它们的传输球体是否相交形成交叉区。由于m个传感节点可以有2m个组合，这种方法属于指数复杂度，不具有可行性。

本文的方法是通过寻找A中的特征点集合来遍历A中区域。一旦找到特征点，求出包含它的区域是比较容易的，位于一个区域边界上的特征点可能同时位于其他区域内，如图1所示。本文的算法每次在至多d个传输球面的交叉区上选取特征点，由于网络中具有 O(nd)个交叉区，而每个交叉区至多选取2点，所以算法搜索的特征点数量为O(md)，其中，m为传感节点数量，这种方法可降低算法最坏情况下的复杂度。

4.1 算法流程

下面给出算法的流程。

扩展算法:计算新增中继节点的位置

算法输入参数中传感节点的多维坐标可以在网络启动前由已知坐标的锚节点把测量结果直接发送给中继节点，权重和过载流量需要根据当前传感节点的传输流量计算，具体方法见4.1节。算法主体为循环结构，循环开始从传感节点的S个集合中选择至多包含d个球面的子集Ŝ（第2行），如果Ŝ中所有球面被遍历，没有找到可行解则退出（第3行），否则计算Ŝ中所有球面的交叉区ŝ，由定理1可知ŝ为空或一个低维球面，如果ŝ非空，则继续（第4行），从ŝ中选择特征点构成N，由于零维球面至多包含2个顶点，因此集合N也至多包含2个元素（第6～9行），第11行开始子循环，遍历包含N中顶点的所有区域。在下面完备性证明中将说明本方法能够遍历A中每一个子集（遍历的所有N集合中包含了A内子集的特征点），搜索包含N内顶点的所有区域以及计算相应权重的方法见 4.2节，如果有一个区域满足带宽及过载条件，则该区域的传感节点可以作为新的中继节点。

很明显算法的解具有多样性特点，由于第2行Ŝ的选择和第9行N的选择具有一定随机性，因此每次执行可能产生不同的解，但这种多样性不影响本算法的正确性和完备性。

正确性证明:由于第 13行的约束性判别，所以第14行的p为正确的位置。

完备性证明:完备性指如果问题有解，算法一定能够找到它。为了证明本算法的完备性，首先需要证明当算法没有找到解退出时，A中的所有区域都被遍历到（11～15行）。设有区域a∈A，根据定理3会出现2种情况:①S中球面形成的交叉区被a包含；②该交叉区为零维球面，并与a有一个相交点。定理2进一步补充说明至多搜索d个球面的交叉区就可找到该解（第2行）。

设第4行的ŝ为定理3中的交叉区，这时存在2种情况:①ŝ为a所包含；②ŝ为零维球面且与a有一点相交。如果①成立，则不管5～9行选择何种顶点，a必会被11～15行的子循环找到，如果②成立，在11 ～15行中搜索了所有与ŝ有交点的区域。因此算法没有找到可行解退出时，可以肯定网络空间A内所有区域被搜索过，无可行解。

4.2 权重的计算

算法重点之一就是在A空间找到包含特征点v的所有区域并计算出权重。设包含v的所有区域集合为Av，B1为内部包含n的传输球体集合，B2为边界上包含v的传输球体集合，所以对于任意一个区域 a（a∈Av），它的权重为 W1+W2，W1为 B1中所有球体的权重之和，W2为B2中部分球体的权重之和。

举例说明如下，假设图1中v为n3和n4的交叉区中位于B(n2)内的点，因此Av包含了区域a3、a7、a8 和 a10，B1包含 B(n2)，B2包含 B(n3)和 B(n4)。可得 Av中 W1的值为传输球体 B(n2)的权重 4，B2中2个球体都包含区域a10，W2对应a10的值为24，它等于B(n3)和B(n4)的权重之和，而W2中对应a3、a7、a8的值同理可得分别为0、8和16。

W1和B1的计算与Av中特殊区域无关，可以比较容易的计算得出，而计算Av中W2的算法比较复杂，主要包含2个步骤。

1)设计了一个判别规则，搜索满足以下条件的B2的子集B3(B3⊂B2)，该条件为B3内所有球体包含某区域 a(a∈ Av)，且 a⊄ B2/B3。

2)为了避免遍历B2内所有子集组合，利用如下推论对搜索过程中B3的数量做了限制。

推论1 对于B3⊂B2，如果Av内存在区域a，a被B3中所有球体包含且位于B2/B3之外，当且仅当B3中所有球体的球心可通过一个包含点n的超面与(B2/B3)内球心分割。

证明 设 v附近有一点 v1，v1和 v位于以 n为球心的球体内的条件为:矢量(v, v1)和(v,n)之间夹角小于π/2。因此当且仅当B3内球体的球心包含v且与 v1位于(v,v1)正交超面的同一侧时，v1位于 B3内球体的交叉区域。

图3为图1中v点周围的详细图示，v为a3和a4的交叉区中位于B(n2)内的点。因为(v,v2)和(v,n3)的夹角小于 π/2，所以 v2位于 B(n3)内，同理 v2同时也位于B(n4)内。因为v2，n3和 n4位于超面 z2（z2正交于(v,v2)）的同一侧，所以v2位于a10（包含v）区域内。而v3在B(n4)内但在B(n3)外，(v,v3)和(v, n4)的夹角小于 π/2，但(v, v3)和(v, n3)的夹角大于π/2。同理，因为v3和n4位于z3（z3正交于(v,v3)）的同一侧，但和n3分别位于z3的两侧，所以v3在区域a8内。

图3 权重的计算示例

推论2 如果C为B2内所有球体球心的集合，搜索 Av内所有区域的问题可以进行简化查找分区问题，即查找把C划分为2个子集的分区，其中这2个子集可以被包含n的超面分割。

证明 假设C∪{v}包含至少d个线性无关点，C1为C的非空子集，可在C∪{v}内增加新的线性无关点，并把以它们为球心的球体权重设为 0，根据文献[19]的推论4.2可知，如果C1和CC1可被包含v的超面分割，则该超面包含v和C中至少d−1个点。这样在步骤1中不必计算Av内可能的组合，只需选择d−1个特征点即可。

5 算法分析及改进

在本节对算法的复杂度进行分析，并提出了相应的优化方法。

5.1 最坏情况下复杂度分析

假设锚节点的个数为 d，即网络部署空间的维度d为常数，下面逐行分析复杂度。尽管本文没有指明如何选择 Ŝ，但不难在常数时间执行完算法的第2行（例如可以对Ŝ中子集排序，然后按升序提取）。第4行需要计算Ŝ中各球面的交叉区ŝ，因为Ŝ的维度设置为 d，所以这一工作也可在常数时间执行。第5行和第6行的判断语句可以看做ŝ计算过程的一个子部分。第11 ～15行的执行时间也为常数。而计算权重 w和 wol的算法（4.2节给出）与(m+|B2|d)成线性比例关系，|B2|为 B2包含的球体数量，即为与N中某点相交的球体数量，这里m为计算 W1的开销，而计算W2的开销由计算 B2的交叉区组成。因为在第一次循环时对B2的计算结果可以存储，所以在后面循环中可以跳过B2中球面集合的计算。所以第11～15行的开销为O(m)，即一次循环的开销为O(m)，循环的次数由可能选取的Ŝ的数量决定，即从m元组中选取至多d元子集的次数，它的复杂度为 O(md)，所以最坏情况下算法复杂度为O(md+1)。

5.2 算法优化

因为部署传感器网络时，锚节点的数量不会很多，所以算法的复杂度取决与传感器的数量，所以考虑如何进一步减少算法中可计算的传感节点数量。

为了方便路由并减少能耗，新增的中继节点应该部署在超载节点附近。因此远离超载节点的传感节点不受新增节点的影响，在算法中可以不考虑这些节点。如果增加中继节点后，没有传感节点可以分派到该新增节点上，那就表明算法的这次部署无效，因此需要建立一个判别规则区分哪些为可忽略节点，这就需要在dℝ中限制新增节点的可部署区域。

推论3 设已分派给超载中继节点rol的传感节点s，它能够重新分派给新增中继节点rad的条件为dist(rol, rad)≤2g，g为rad的传输半径，或rad与最远分配节点之间的距离。

证明 假设新增中继节点后，rad从 rol上接管了传感节点s的流量，根据“就近指派”原则可得dist(s, rad)≤dist(s, rol)。根据g的定义可得dist(s,rol)≤g。根据三角不等式定律可得dist(rol), rad≤dist(s,rad)+dist(s, rol) ≤2dist(s, rol) ≤2g。

从推论3可以推出，如果中继节点和传感节点之间遵循就近指派原则，部署算法只需考虑与超载节点距离在g之内的传感节点，即中继节点的路由表中只需登记g范围之内的传感节点。当然对其他指派方式，也可按照类似方法加以限制。如果传感节点围绕中继节点均匀分布，部署算法需要考虑的节点数量与分派给中继节点的传感节点数量呈线性比例关系。进一步假设，如果网络中中继节点的数量随着传感节点数量线性增加，则部署算法在一次执行时需要计算的节点数量为常数。

6 实验分析

为了验证部署算法的可行性和有效性，在Qualnet网络仿真平台下设计了3种实验，为了提高实验结果的可信性，每次实验采用不同的随机种子重复 10次取其平均值显示。能量模型采用式(1)，参数设置参照了MICA系列传感器节点，其中，α1（发送或接收 1bit数据消耗的能量）设置为50nJ/bit，α2（对1bit数据发送放大器消耗的能量）设置为0.1nJ/bit/m2，β为50nJ/bit，δ设置为2，报文长度为512bit，传感节点传输半径r设置为30m，初始能量为6J，为了减少中继节点制造成本，初始能量为传感节点的2倍即12J，带宽为1.5Mbit/s，其他参数设置包括传输半径与传感节点相同。传感节点的数据采集率在[50kbit/s,100kbit/s]间均匀分布，每隔30s进行一次数据收集，部署区域为2000m×2000m，路由采用Dijkstra最短路径算法[20]。设定位服务由6个锚节点提供，在部署后把测量坐标发布给各中继节点。

为了避免偏向于某一种中继节点部署算法和中继节点−传感节点分配算法，按照在负载平衡问题上广泛应用的方法设置起始的网络部署态势，采用k-means算法对传感节点分簇，中继节点部署在算法生成的k个簇群的中心[21]。

第1种为扩展性实验，以测试当网络拓扑发生变化时算法的反应能力。实验共分100步，开始时先部署100个传感节点和1个中继节点，随后99步中每次增加100个传感节点，由于流量增加，超载节点运行部署算法增加新的中继节点，测量每次部署节点的运行时间。当传感节点达到 10000个时，每次随机减少一个中继节点，这时运行部署算法增加新节点以减轻超载节点的负载，并记录算法运行时间。假设中继节点最高负载带宽为L，设置过载阈值为0.25L，为了避免新增节点能耗率太高，每次可以被新增中继节点接管的流量设置为在[0.25L, 05L]之间均匀分布的随机数。从算法流程可以看出，从超载节点接管的流量大小是非常重要的。每当增加中继节点时，不仅运行部署会有一定的开销，改变路由信息也会增加开销。如果转接的流量设置过小，会造成超载节点反复过载，因此把从超载节点上转接的流量设置为25%以避免短时间内发生二次过载。另外为了限制分派给新增中继节点的传感节点数量，把新增节点的最大负载设置为超载节点负载的50%。

每次增加一个中继节点，随着网络规模的扩大，融合了5.2节所示优化方法的部署算法的运行时间如图4所示。从图4可见算法的运行时间与传感节点的数量呈线性关系。

图4 不同网络规模的算法时间开销

在网络中已部署10000个传感节点和100个中继节点后，随着网络结构的动态变化，算法的运行时间变化如图5所示。每个仿真步随机删除一个中继节点，由于剩余中继节点负载增大，部署算法进行运算增加一个新的中继节点减轻最大超载节点的负载。注意:新增中继节点的位置不一定在删除节点附近，与删除节点的位置没有关系。每个仿真步之间算法的运行时间都有变化，但总体上都以77ms为平均值上下浮动20ms，而77ms与图4中网络规模达到 10000个传感节点时的算法运行时间基本一致。

图5 不同网络结构的算法时间开销

第2种为比较性实验，为此设计了一个无优化扩展部署方案以便与本文的优化部署方案进行比较。在无优化部署方案中，新增中继节点的位置以超载节点为中心随机正态分布，这也可看做存在冗余部署时激活休眠节点的一种方式。设超载节点与分配给它的最远传感节点之间距离为g，把分布的方差设置为g×k，其中，k为适应因子，它根据起始部署方案的位置进行调节以适应超载节点的环境。当所有中继节点位置计算完毕后，每个采集轮次随机选择15%的传感节点，使其数据采集率增加为在[75kbit/s, 150kbit/s]间均匀分布，其余保持为初始值，观察网络性能的变化情况，其中过载阈值和最大转接负载阈值的设置和第1个实验相同。在这个实验中定义了3个性能指标。①能量利用率:在出现一个中继节点死亡时（消耗完所有能量），所有中继节点消耗的能量之和与初始能量之和的比值；②生命周期:在出现一个中继节点死亡时，仿真所进行的轮数；③中继节点负载方差:在出现一个中继节点死亡后，统计100个初始中继节点的负载变化标准方差。图6和图7分别比较了3种部署方案（本文的优化扩展部署方案、无优化扩展部署方案和仅仅初始部署）的能量利用率和生命周期，其中，中继节点的数量从10增加到100个。

图6 不同中继节点数量的归一化能量利用率

图7 不同中继节点数量的网络生命周期

从图6可以看出，无论在能量消耗还是生命周期指标上，2种扩展部署算法的性能与无扩展部署算法相比要高，这是由于当某个区域网络流量增加时，扩展算法可以把部分流量负载转接给其他节点，从而减少能耗。而优化扩展算法的性能比另外2种算法都占有明显优势，与无优化扩展算法相比，在能量利用率上平均高出5%到15%，在生命周期上平均延长8%到25%，并且随着网络规模的增大和中继节点数量的增多，优势更为明显，这时因为优化扩展算法具有良好的可扩展性，随着节点数量的增加，考虑的优化位置数量也会增加。对于无扩展部署的方案而言，能量利用率在中继节点数量为10到50个时有明显增加，随后变化开始缓慢，能量浪费较大。总体而言，能量利用率随着节点数量的增加逐渐达到一个饱和值，生命周期则随着节点数量增加线性增长。

图8表示了无扩展部署和优化扩展部署情况下中继节点的稳定性，可以看出在优化扩展部署下，随着中继节点的增加，其负载的标准方差基本为常数，而初始部署方案的递增曲线表明随着中继节点的增加，它们之间的负载变化逐渐增大。

图8 不同中继节点数量的负载标准方差

第3种为敏感性实验，主要测试算法对2个重要参数（overload和 reload）的敏感度，在测试值 overload的敏感度时，reload固定设置为0.75L，当测试最高转接流量reload时，overload固定为0.25L。

新增中继节点的接管负载阈值固定为 0.75L时，超载节点的过载阈值从0到0.7L之间增加时，算法运行时间和无可行解比例的变化如图9所示。

超载节点的过载阈值固定为中继节点最大带宽的0.25倍时，新增中继节点的接管负载从0.3倍到1倍之间增加时，算法运行时间和无可行解比例的变化如图10所示。从图9和图10可以看出，算法的开销及找到可行解的概率受overload和reload 2个阈值参数的影响较大，降低 overload和增加reload可以改进算法的性能。

图9 不同过载阈值时运行时间和无可行解率的变化

图10 不同接管负载阈值时运行时间和无可行解的改变

7 结束语

本文提出了一个在多维空间搜索新增中继节点合理位置的优化扩展部署算法。该算法在最坏情况下的时间复杂度为O(md)，其中，m为传感节点数量，d为传感器网络多维定标的维度，并进一步提出了一个优化方法，在大多数情况下可以把算法的复杂度降为m的线性函数。仿真实验的结果表明算法的时间复杂度基本上随传感节点数量呈线性增长，在一个包含1000个节点的传感器网络中部署中继节点所花的时间控制在90ms以内。如果允许牺牲一定的算法精度，通过进一步放松超载节点的过载阈值和新增节点的接管负载阈值，可以更大幅度地减少算法的时间开销，因此本文提出的扩展部署算法适用于计算受限的传感器节点。如果算法精度影响了新增节点平衡负载的能力，还可以通过算法的后续运行继续增加中继节点进行弥补。通过实验还可以看出扩展算法提高了网络的能量利用率，延长了生命周期。

因为超载中继节点拥有算法必须的数据，所以由它运行扩展部署算法较为合适。但当超载节点负载已达到最大限度或能量消耗已近底线时，尽管现有传感节点的微控制器计算能力已得到较大发展，但可能还是无法承担计算密集的任务。可以有2种办法来解决，一种是在中继节点负载达到其最大带宽的某一部分时提前运行扩展部署算法实施卸载；还有一种办法是超载节点把数据发送给其他中继节点由其代理运行。在4.1节中尽管算法采用的是集中式运行方式，但由于主循环内的迭代运算相互无关，所以算法也可以放到多个节点上并行运行。

[1]AZIM A, ISLAM M.Hybrid LEACH:a relay node based low energy adaptive clustering hierarchy for wireless sensor networks[A].Proceedings of the 2009 IEEE 9th International Conference on Communications[C], Kuala Lumpur Malaysia, 2009.911-916.

[2]DELIGIANNAKIS A, KOTIDIS Y, ROUSSOPOULOS N.Bandwidth-constrained queries in sensor networks[J].The VLDB Journal,2008, 17(3):443-467.

[3]COSTA J A, NEAL P, ALFRED O, et al.Distributed weighted- multidimensional scaling for node localization in sensor networks[J].ACM Transactions on Sensor Networks (TOSN), 2006, 2(1):39-64.

[4]沈波，张世永，钟亦平.无线传感器网络分簇路由协议[J].软件学报, 2006,17(7):1588-1600.SHEN B，ZHANG S Y，ZHONG Y P.Cluster-based routing protocols for wireless sensor networks[J].Journal of Software, 2006, 17(7):1588-1600.

[5]IBRAHIM A S, SEDDIK K G, LIU K J.Connectivity-aware network maintenance and repair via relays deployment[J].IEEE Transactions on Wireless Communications, 2009, 8(1):356-366

[6]LI J S, KAO C, KE J D.Voronoi-based relay placement scheme for wireless sensor networks[J].IET Communications, 2009, 3(4):530-538

[7]LEE S, YOUNIS M.Optimized relay placement to federate segments in wireless sensor networks[J].IEEE Journal on Selected Areas in Communications, 2010, 28(5):742-752

[8]TANG J, HAO B, SEN A.Relay node placement in large scale wireless sensor networks[J].Computer Communications, 2006, 29(2):490-501.

[9]MISRA S, HONG S D, XUE G, TANG J.Constrained relay node placement in wireless sensor networks:formulation and approximations[J].IEEE Transactions on Networking, 2010, 18(2):434-447.

[10]PATHAK P H, DUTTA R.Impact of power control on relay load balancing in wireless sensor networks[A].Proceedings of the Wireless Communications and Networking Conference (WCNC)[C].Sydney,Australia, 2010.1-6.

[11]WANG F, WANG D, LIU J C.Traffic-aware relay node deployment for data collection in wireless sensor networks[A].Proceedings of the 6th Annual IEEE Communications Society Conference on Sensor Mesh and Ad Hoc Communications and Networks[C].Rome, Italy,2009, 351-359.

[12]YANG Y Y, MIRELA I, et al.Improving network lifetime with mobile wireless sensor networks[J].Journal of Computer Communications, 2010, 33(4):409-419.

[13]郑增威，吴朝晖，林怀忠等.可靠传感网聚类路由算法研究[J].浙江大学学报.2005, 39(10):1461-1464.ZHENG Z W, WU Z H,LIN H Z, et al.Reliable clustering routing algorithm for wireless sensor networks[J].Journal of Zhejiang University(Engineering Science), 2005, 39(10):1461-1464.

[14]MENA J, KALOGERAKI V.Dynamic relay node placement in wireless sensor networks[A].Proceedings of the 2008 International Symposium on Applications and the Internet[C].Turku, Finland, 2008.25-35.

[15]WAN C Y, EISENMAN S B, CAMPBELL A T.CODA:congestion detection and avoidance in sensor networks[A].Proceedings.of First ACM Conference on Embedded Networked Sensor Systems (SenSys 2003)[C].Los Angeles, 2003.266-279.

[16]ERGEN S C, VARAIYA P.Optimal placement of relay nodes for energy efficiency in sensor networks[A].Proceedings of the IEEE International Conference on Communications[C].Istanbul, 2006.3473-3479.

[17]ZAFAR B, MIR Z H, SHAMS S M, et al.On improved relay nodes placement in two-tiered wireless sensor networks[A].Proceedings of the Military Communications Conference[C].Boston, MA, USA,2009.1-7.

[18]LI H B.Hyperbolic conformal geometry with clifford algebra[J].International Journal of Theoretical Physics, 2001, 40(1):81-94

[19]WAGNER U.On the number of corner cuts[J].Advances in Applied Mathematics.2002, 29(2):122-131

[20]BHATTACHARYA A, KUMAR A.Delay constrained optimal relay placement for planned wireless sensor networks[A].Proceedings of the 18th International Workshop on Quality of Service (IWQoS)[C].Beijing, China, 2010.1-9.

[21]PENG W, EDWARDS D.J.K-Means like minimum mean distance algorithm for wireless sensor[A].Proceedings of 20102nd International Conference on Computer Engineering and Technology (ICCET)[C].Chengdu, China, 2010.120-124.