无线传感器网络中能量高效的基站位置优选算法

唐伟，郭伟

（电子科技大学 通信抗干扰技术国家级重点实验室，四川 成都 611731）

1 引言

无线传感器网络（WSN, wireless sensor networks）具有广泛的应用范围，例如目标跟踪、环境监测、工业控制等[1]。该类网络通常由一组传感器节点和基站构成，且具有数据中心性质，即传感器节点所收集的数据通过多跳方式汇集至基站，基站负责处理数据，并将数据传递至外网进行分析决策。节能路由算法一直都是该类网络研究中的重点之一，目前已经有了不少相关研究[2～7]。然而，现有的研究中往往都假定基站位于网络场景的几何中心或者随机分布于网络中。本文假设传感器节点的位置已经由应用需求所确定，而基站可以在一定空间范围内布设。从路由的角度上看，最小网络总能耗路由结构是一棵以基站为根的最短路径树（SPT, shortest path tree），其中各链路长度是在该链路上传递单位比特数据的能耗。基站位置的优选问题可以被归结为一类非线性规划问题，且问题的目标函数非光滑且非凸。对于此类问题，数学上通常采用的方法包括迭代下降算法以及启发式搜索算法寻找问题的近似解。典型的迭代下降算法包括内点法、有效集法、依赖域法等[8]，对于非凸规划问题，算法只能收敛到局部最优解，且解的性能受初始点选择影响很大。启发式搜索算法包括基因算法、粒子群优化（PSO, partical swarm optimization）算法等[9,10]，该类算法的计算复杂度较高，算法解的稳定度也难以保证。由于没有考虑问题自身的特点，直接采用这些通用算法往往导致算法效率低、精度差、不稳定等问题。本文的研究从问题自身的特点入手，为问题设计简单有效的算法。首先对目标函数分段光滑凸性质进行研究，提出并分析了最短路径树剖分的概念；然后，设计了3种启发式算法（单点迭代下降、节点深度搜索以及多点迭代下降算法）。最后，通过仿真实验验证了所提算法的性能，并与PSO算法的结果作了对比分析，表明所提算法能够有效地接近或收敛于问题的最优解，且具有较好的稳定性。

本文组织如下。第2节介绍系统模型，并提出能量高效的基站位置优选问题；第3节分析目标函数分段光滑凸性质，并定义最短路径树剖分；第 4节研究二维空间中最短路径树剖分单元的结构；第5节提出3种启发式算法；第6节通过仿真验证了所提算法性能；第7节是结束语。

2 能量高效的基站位置优选问题

2.1 系统模型

设无线传感器网络位于一个凸区域 A ⊆ℜn中，基站位于区域A中的某点 ps。当节点i与节点j通信时，发送单位比特所需的最小发射能耗与链路距离的平方成正比[11]。

其中，εamp是发射功率增益（单位为J/bit/m2）， dij是节点i与 j之间的距离（单位为m）。为分析方便，假设每个传感器节点都有足够的最大发射功率能够将区域A覆盖。网络可以被建模为一个有向连通图G(˜, E)，其中，表示传感器节点集合V与基站集合{s}的并集，E表示链路的集合令节点i的邻居集合为传感器节点i的数据收集速率为Ri（单位为bit/s）。

2.2 能量高效的基站位置优选问题

令链路(i,j)∈E上的网络数据流为fij（单位为bit/s），对于任意传感器节点iV∈，网络中出入该节点的数据流守恒，于是有约束

节点i的能耗可以被表示为

故而，网络总能耗可以被表示为

称网络流fij的系数为链路(i,j)的能耗系数。

本文提出能量高效的基站位置优选问题：求解基站位置点 ps及网络流 f={ fij}，使得网络总能耗Cnet最小，可以被表示为如下非线性规划[12]问题：

问题(4)的约束域是由网络流 f所属的多面体与基站位置ps所属的凸区域A的笛卡尔乘积空间，因而是一个凸区域。然而，问题的目标函数是非光滑的非凸，这为问题的求解带来了很大困难。

3 最短路径树剖分

3.1 系统模型

为了简便起见，将问题(4)的目标函数表示为基站位置 ps与网络流 f的函数 C ( ps,f ) =Cnet。根据式(1)和式(3)，问题的目标函数随着节点间距的增加而增大。于是，本文给出如下定理以简化问题。

定理1 基站的最优位置 ps必然在传感器节点集合的凸包上。

其中， gk(x)是仿射函数。对于位于凸包之外的点 s1，必然存在至少一个 k0(1 ≤ k0≤ K )，使得gk0(s1) ＞ 0 。于是，令超平面则点 s1位于超平面ħ的一侧，而所有传感器节点位于该超平面的另一侧或其上。

如图1所示，点a是任意一个传感器节点，点 s2是点s1在超平面ħ上的垂足。在Δas2s1中，∠as2s1≥π/4，因而得到as1＞as2。将基站选择在凸包外的点 s1时，总存在凸包上的一个点 s2，使得当基站位于该点时，基站与任意传感器节点之间的距离都更小。

图1 基站不同位置与传感器节点间距的关系

根据式(1)和式(3)，网络总能耗随着基站与传感器节点间距的增加而增加。于是，基站在点 s2时网络总能耗更小。由点 s1选择的任意性知，使得网络总能耗最小的基站必然在凸包上。

3.2 目标函数的分段光滑凸性质

从问题(4)的形式上看，将基站位置sp固定，问题就化为一个带约束的线性规划问题；而将网络流f固定，问题就化为一个无约束的二次规划问题。基于这样的观察，本文提出如下定理。

定理2 问题(4)的目标函数是一个分段函数，且每个分段是定义在多面体上的二次函数。

证明 当基站位于点 ps时，使网络总能耗最小的网络流 f对应于以基站为根的最短路径树T。令Hi={hi}表示所有从节点i到基站s的路径集合，ℓ(hi)表示该路径中各段链路能耗系数之和，即注意到

于是， ℓ (hi)是 ps的二次函数，且对应二次项系数为εamp。令表示从节点i到基站s在最短路径树中的路径，有于是，当且仅当基站位置满足如下条件时，网络最短路径树保持不变。

当基站位于每个这样的多面体上时，网络最短路径树不变，故而网络流f也保持不变，于是网络总能耗是关于基站位置ps的二次函数。

推论1 对任意网络流f，基站的最优位置ps的各坐标分量满足

对于固定的网络流f，基站的最优位置 ps使得函数(ps)=C (ps,f )最小。由于各传感器节点的坐标都是常数，而关于ps取值范围的约束已被去除，故函数(ps)是关于点ps的二次函数。令：

即得式(7)。

根据推论1，在目标函数每个分段内应用式(7)，就能得到对应于任意网络流的基站最佳位置。

3.3 最短路径树剖分

根据定理 2，只需在目标函数的各分段上运用推论1的结论，就能获得问题(4)的全部局部最优解，从而获得全局最优解。通过式(6)，可将n维空间剖分为若干区域。由此，本文给出如下定义。

定义1 定义最短路径树剖分单元为

在定理2的证明中，从节点i出发到基站s的全部路径的集合 Hi中的元素个数为其中，P ( i, j)表示从j个元素中选取i个元素的排列数，直接通过式(6)计算目标函数各分段的复杂度太高。

定理 3 当且仅当基站位置 ps满足如下条件时，网络最短路径树T保持不变

证明 对于任意路径 hi，表示为有

4 二维空间中SPT剖分单元的结构

首先，在二维空间中，式(11)可以被表示为一组二维线性不等式：

其中，αi是一个二维列向量，βi是一个常数。其边界为如下线性方程对应的解：

该边界方程的解可以被表示为单个参变量it的形式：

其中，A为-π/2单位旋转变换矩阵

于是，Aαi是αi的正交补空间中的一组基。

然后，确定参数ti的取值范围，就能够得到对应SPT剖分单元在式(14)上的一条边界。对于其他任意二维线性不等式：

要求找到ti，使xi对于任意 j都满足式(17)。于是，将式(15)代入式(17)，得

记此时ti所对应的取值区间为Tij，且令：

则Tij可以被表示为

其中，当 μij=0时，LIi对应半平面的边界与LIj对应半平面的边界平行。此时，当νij＞0时，LIi对应半平面包含在 L Ij对应半平面中；当νij=0时，LIi对应半平面与 L Ij对应半平面重合；当νij＜0时，LIi对应半平面包含 L Ij对应半平面。故 ti的取值范围为

如果Ti≠∅，那么对应SPT剖分单元的一条边是LIi对应半平面的边界上的一条线段或一个点。如果Ti=∅，表示对应SPT剖分单元是LIi对应的半平面内部的一个区域，SPT剖分单元的边不与该半平面边界相交。通过跨越SPT剖分单元边界，就能对相邻SPT剖分单元进行遍历。

5 基站最优位置的启发式算法

5.1 单点迭代下降

本文设计了单点迭代下降（SPRD，single-point recursive descendent）算法。令基站初始位置为，通过Dijkstra算法[14]计算网络最短路径树，得到对应的网络流 f(0)。通过式(1)得到对应于网络流 f(0)的最优基站位置。重复以上步骤，直到基站位置不变。对于第k和 k + 1 次迭代，如果与属于同一个SPT剖分单元，由于SPT剖分单元内最优网络流具有不变性，根据推论 1，那么对任意k′＞k，都有又因为SPT剖分单元的总数有限，算法能够在有限步骤内收敛。算法收敛时迭代次数k的值称为迭代深度。

5.2 节点深度搜索

证明 当基站位于 pi时，由于基站与节点i位于同一点上，任意节点通过节点i将数据转发到基站与直接将数据传给基站时的能耗是相同的。于是，令节点集合即将数据直接发送给基站s或者节点i的节点集合。注意到≥ 2 ，于是 Vi≠∅。从 Vi中任选m≤个节点，令这些节点的数据直接传给基站，而 Vi中的其他节点的数据经节点i转发给基站，而原最短路径树中的其余链路不变，所得到的依然是一棵最短路径树。由此可知，每个位置 pi都位于某些 SPT剖分单元的交界。

根据定理 4，本文设计节点深度搜索（NDS，nodal depth search）算法。对于网络中每个节点iV∈，可以通过点ip搜索相交于该点的非退化SPT剖分单元。对这些剖分单元计算对应网络流的最优基站位置以及对应该基站位置的网络总能耗，可以得到基站最优位置的一个近似解，称此时的搜索深度为1。当搜索深度为k时，可以对所有已搜索剖分单元的相邻剖分单元做进一步搜索，其中的最优解作为搜索深度为 1k+ 时算法的解。记搜索深度为n的NDS算法为NDS-n。由于对于给定的有向图，其生成树的数量是有限的[15]。于是，当阶数足够大时，算法能够遍历其中所有剖分单元，因而能够在有限步骤内收敛到全局最优解。

5.3 多点迭代下降算法

将SPRD与NDS算法相比较，可以发现SPRD算法采用了深度优先的搜索方法，沿着目标函数下降的方向搜索SPT剖分单元；而NDS算法采用了广度优先的搜索方法，对每个节点周围的SPT剖分单元逐层遍历。SPRD算法性能决定于初始点的选择；而NDS算法收敛速率缓慢。本文将以上2种算法的优点加以综合，由此设计了多点迭代下降（MPRD，multiple-point recursive descendent）算法。算法分为 2个步骤，首先采用 NDS-n算法获得深度为n的SPT剖分单元，以这些SPT剖分单元中的任意点作为初始点进行SPRD算法，并选择最好的结果作为基站最优位置的近似。对应于深度n的MPRD算法记为MPRD-n算法。定义MPRD算法的迭代深度为其中SPRD算法步骤的迭代深度。

6 仿真实验

本文采用MATLAB对所提出的算法进行仿真。传感器节点随机分布于100 m × 1 00m 的矩形区域内，数据收集速率均匀随机分布于0～1bit/s的范围内。由于网络总能耗与εamp成正比例关系，为简便起见，设置 εamp= 1 J/bit/m2。

首先，演示10个传感器节点的场景。如图2所示，在XY平面上，10个编号的圆点表示传感器节点，在XY平面上粗色黑线所围成的区域表示这些传感器节点的凸包，垂直于XY平面的虚线的垂足对应于基站的最佳位置。从图中可以看到，基站的最佳位置是在上的，与定理1相符。XY平面经过SPT剖分，被划分为若干SPT剖分单元，在同一剖分单元内网络最短生成树的结构保持不变。相同灰度的剖分单元表示以其中的任意点为初始点，经过SPRD算法之后会收敛于同一点。从图中还可以看到，每个传感器节点都位于某些剖分单元的交界上，与定理4相符。图中的曲面表示目标函数的取值。曲面上粗线所围成的区域对应于目标函数在各SPT剖分单元中的取值。可以看到，在各剖分单元内，目标函数是光滑凸函数，与定理2相符。

图2 二维空间情形下目标函数的图像

接下来，本文通过仿真实验在节点数目为10～100个的网络场景下对 SPRD、MPRD、NDS以及FMINC算法的性能进行研究。其中，FMINC算法是采用 MATLAB提供的带约束非线性规划求解函数[16]计算获得的结果。

为对比算法性能，定义归一化网络总能耗Cnorm为算法所得网络总能耗与最优网络总能耗的相对差，用百分比表示，即

其中，Calg表示算法性能，Copt表示最优性能，该值通过NDS算法遍历SPT单元求解。

由于所涉及的算法数量较多，本文分别用图 3表示SPRD、NDS以及FMINC算法在不同网络规模下所得归一化网络总能耗，而用图4表示MPRD算法的性能。其中，SPRD及FMINC算法中基站位置初始点取值为

从图3中发现SPRD算法的性能较差，这是因为SPRD算法的性能与初始点的选取有很大关系，难以通过简单的方法获得一个对各场景都有很好效果的初始点。由于FMINC算法采用最速下降算法，只能收敛到初始点邻域内的局部最优，例如局限在一个SPT单元中，不像SPRD算法的迭代过程具有一定的搜索深度，因而FMINC算法的性能更差。对于 NDS算法，随着搜索深度的增加算法能够遍历更多的 SPT单元，因而性能也随之提升。NDS-40算法能够在所考虑的网络规模下收敛到最优解，并被用作式(22)中的Copt。

图3 各算法归一化网络总能耗的比较

从图4中不难看出，MPRD算法性能与最优性能非常接近。MPRD算法通过NDS算法对SPT剖分单元的搜索，为SPRD算法选取了行之有效的初始点集合。由于MPRD算法在NDS算法的广度优先搜索的基础上进行深度优先搜索，因而其性能明显优于SPRD算法和NDS算法。这是因为NDS算法是一种广度优先搜索算法，当节点数目增多时，节点周围的SPT剖分单元变得更加密集，因而往往需要更大的搜索深度才能获得较好的解。而MPRD算法通过结合深度优先搜索，可以得到更优的解。

图4 MPRD算法归一化网络总能耗的比较

图5所示为SPRD和MPRD算法收敛时所需的平均迭代深度。从图中可以看到，SPRD算法收敛时的迭代深度小于 MPRD算法，这是因为 MPRD算法具有更丰富的初始迭代点，能够在更加深广的范围内搜索最优解，随着搜索深度的增加，算法能够获得更好的解，这与图5中的结果是一致的。

图5 SPRD和MPRD算法收敛时的平均迭代深度

由于目前针对非线性非凸非光滑规划问题往往采用全局启发式搜索方法，本文也进行了对比。本文采用 PSO工具包[17]，其中粒子数量与节点数量相同，每个场景下独立运行20次算法，并对结果取均值。图6所示为PSO算法的归一化网络总能耗，其中误差线表示PSO算法所得的最大值。由于PSO算法的随机搜索性质，算法能够收敛到局部最优，但不能保证每次都获得全局最优解，所得到的解具有一定的随机性质。对比图4，不难看出MPRD算法性能较好且较稳定。

图6 与PSO算法归一化网络总能耗的比较

7 结束语

无线传感器网络中，基站位置对网络总能耗有很大影响，因而研究基站位置的节能优选问题具有重要意义。由于问题在通常情况下是一类非光滑非凸规划问题，为设计有效的求解算法，本文针对问题的目标函数和约束条件的性质进行研究。通过分析，本文为二维空间中的情形提出了3种启发式算法，通过仿真实验验证了算法的有效性和收敛性。

[1] AKYILDIZ I F, SU W, SANKARASUBRAMANIAM Y, et al. A survey on sensor networks[J]. IEEE Communications Magazine, 2002,40(8)∶ 102-114.

[2] APPADWEDULA S, VEERAVALLI V V, JONES D L. Energy-efficient detection in sensor networks[J]. IEEE Journal on Selected Areas in Communications, 2005, 23(4)∶ 693-702.

[3] YANG Y, PRASSANA V K, KRISHNAMACHARI B. Energy minimization for real-time data gathering in wireless sensor networks[J].IEEE Transactions on Wireless Communications, 2006, 5(11)∶3087-3096.

[4] MING L, YUAN Z, JIANNONG C, et al. An energy-aware protocol for data gathering applications in wireless sensor networks[A]. IEEE International Conference on Communications (ICC’07)[C]. 2007.3629-3635.

[5] PANDANA C, LIU K J R. Robust connectivity-aware energy-efficient routing for wireless sensor networks[J]. IEEE Transactions on Wireless Communications, 2008, 7(10)∶ 3904-3916.

[6] LIU X, HAENGGI M. Toward quasiregular sensor networks∶ topology control algorithms for improved energy efficiency[J]. IEEE Transactions on Parallel and Distributed Systems, 2006, 17(9)∶ 975-986.

[7] AMMARI H M, DAS S K. Promoting heterogeneity, mobility, and energy-aware voronoi diagram in wireless sensor networks[J]. IEEE Transactions on Parallel and Distributed Systems, 2008, 19(7)∶995-1008.

[8] NOCEDAL J, WRIGHT S J. Numerical Optimization[M]. New York∶Springer-Verlag, 1999.

[9] SELVARAJAH K, KADIRKAMANATHAN V. Energy efficient sink node placement in sensor networks using particle swarm optimization[A]. The 5th International Workshop on Ant Colony Optimization and Swarm Intelligence (ANTS’06)[C]. Brussels, Belgium, 2006.510-511.

[10] LEE K Y, EL-SHARKAWI M A. Modern Heuristic Optimization Techniques[M]. Hoboken, New Jersey∶ John Wiley & Sons, 2008.

[11] KANNAN R, IYENGAR S S. Game-theoretic models for reliable path-length and energy-constrained routing with data aggregation in wireless sensor networks[J]. IEEE Journal on Selected Areas in Communications, 2004,22(6)∶ 1141-1150.

[12] LUENBERGER D, YE Y. Linear and Nonlinear Programming[M]. 3rd Ed. New York∶ Springer-Verlag, 2008.

[13] BOYD S, VANDENGERGHE L. Convex Optimization[M]. Cambridge University Press, 2009.

[14] DIJKSTRA E W. A note on two problems in connexion with graphs[J].Numerische Mathematik, 1959, 1∶ 269-271.

[15] GABOW H N, MYERS E W. Finding all spanning trees of directed and undirected graphs[J]. SIAM Journal on Computing, 1978, 7(3)∶280-287.

[16] YANG W Y, CAO W, CHUNG T-S, et al. Applied Numerical Methods using MATLAB[M]. Hokeben, New Jersey∶ John Wiley& Sons, 2005.

[17] SIGNH J. The particle swarm (PSO) toolbox for MATLAB[EB/OL].http∶//psotoolbox.sourceforge.net, 2009.