邵开丽，付 辉

(黄河科技学院，河南郑州 450063)



能耗均衡的无线传感器网络多Sink节点部署优化方法

邵开丽，付 辉

(黄河科技学院，河南郑州 450063)

针对传感器网络中单Sink节点存在近距离传感器节点过早死亡、传输路径单一、传输延迟及节点失效等问题，提出了一种综合考虑网络布局和网络能耗的多Sink节点部署优化新方法。首先，为缩短Sink节点到传感器节点的传输距离，建立了加权距离最小化模型；同时，为均衡网络能耗，建立了无线传感器网络能耗最小化模型。然后，根据所建立多Sink节点部署优化模型的特点，使用加权系数将多目标模型单目标化，并设计了上升启发式算法进行求解。实验结果表明，提出的多Sink节点部署优化方法既能保证网络布局最优，又进一步均衡了网络能量消耗，有助于延长无线传感器网络的生命周期。

无线传感器网络；多Sink节点；布局优化；多目标模型

0 引言

随着微电子机械系统(Micro-Electro-Mechanical System，MEMS)的发展，低成本、低能耗、多功能的无线传感器及其网络得到广泛应用[1]，涉及军事传感、交通监控、视频监控、工业和制造业自动化等领域[2-3]。无线传感器网络(Wireless sensor networks，WSNs)由大量体积微小的节点设备组成，该节点设备集成一个或多个传感器、数据处理单元、短距离无线通信模块和供电电源，可实现信息采集、存储、计算、通信等功能[4]。然而，WSNs节点受固定电源的限制，其能量和计算资源严重受限。因此，如何高效利用网络电源，最大限度延长网络生命周期，成为WSNs研究的关键及热点。近年来，很多专家和学者致力于网络中的节点设备、网络协议、节点布局、数据处理、电池等进行深入研究，在方法和技术上取得了一定成果。本文拟以WSNs中多Sink节点的布局为研究对象，旨在通过优化节点布局有效提高网络生命周期。

Sink节点也称汇聚节点或网关节点，连接WSNs与外网并实现通信。目前，国内外学者针对多Sink节点的布局问题，研究其对网络寿命的影响已有部分成果。文献[5-6]运用线性规划模型研究多Sink节点部署的最佳位置，并确定了WSNs中的最优路由信息流量路径，能有效提高网络的寿命和保证能量的均衡性。文献[7]提出一种基于基因表达式编程(Gene Expression Programming，GEP)的多sink节点部署策略和一种GEP-MSN算法，达到了延长网络生存周期和降低响应时间的目的。文献[8]采用最短路径和矩阵位置方法部署最佳多Sink节点，实验结果显示这种基于约束的部署算法与KSP 和KDP算法相比，更能充分发挥WSNs的潜能。文献[9]提出一种基于能量水平的多Sink节点传感器网络路由算法，与最小能量消耗路由算法相比，更能有效延长WSNs的寿命。

针对WSNs中单Sink节点存在近距离传感器节点过早死亡、传输路径单一、传输延迟及节点失效等问题，本文主要研究多Sink的部署策略，提出一种综合考虑网络布局和网络能耗的多Sink节点部署优化新方法。该方法通过建立多Sink节点布局优化多目标模型，同时实现两个优化目标：一是实现各传感器节点到Sink节点的总加权距离最小化，二是实现WSNs网络能耗最小化。根据所建立模型的特点，本文首先使用加权系数将多目标模型单目标化，并结合设计的上升启发式算法进行求解，得到多Sink节点最优仿真部署方案，最后在仿真实验中分析和验证了多Sink节点布局优化模型和上升启发式算法的有效性。实验结果表明，与传统只考虑距离的节点部署策略相比，本文提出的多Sink节点部署优化方法综合考虑了距离和网络能耗两个目标，既能保证网络布局最优，又进一步均衡了网络能量消耗，有助于延长WSNs生命周期。

1 多Sink节点布局模型

1．1 问题描述

无线传感器网络中，能耗、时延和可靠性是度量QOS的重要指标。基此，研究多Sink节点的布局及优化问题，有利于减少传感器节点到Sink节点的距离，即有效缩短了信息传输时延；而且，多Sink节点传感器网络拓展了传感器节点到Sink节点的信息通信路径，有利于均衡网络能耗和保证信息可靠性。因此，本文在对多Sink节点布局时，采用经典选址模型P-中位问题(p-median problems)对多Sink节点布局进行优化，使传感器节点到所有Sink节点的加权距离最小；同时，为了使整个网络能量消耗最少，建立了网络能量最小化模型，以最大化延长网络生命周期。

1．2 网络结构模型

无线传感器网络结构模型采用如图1所示的网络结构。其中，传感器节点随机分布在监测区域，将采集的监测信息无线传输到布局最优的Sink节点，对信息进行处理后通过Internet/GPRS/3G等网络上传至监控中心。与传感器节点相比，Sink节点连接外网的前置机或数据服务器，具有持续电源和更强的数据处理能力。

图1 无线传感器网络多Sink节点网络结构

1．3 布局优化模型

文献[10]中采用PMP模型对WSNs中的多Sink节点进行部署，仿真结果表明，该方法与随机布局方案相比进一步降低了网络能量消耗，有效延长了网络寿命。然而，WSNs更关注能量优先，不能仅考虑传统选址中注重的路径最优。因此，研究多Sink节点布局优化时，应该把节点能量消耗及网络能量均衡使用放在第一位。本文研究WSNs多Sink节点的部署时，同时兼顾了路径最优和网络能量消耗最少两项指标，并基于此建立了相应的最小化目标函数，提出一种有效的多Sink节点布局优化模型及方法。

1.3.1 多Sink节点布局目标

假设可以用S={se1,se2,L,seN}(|S|=N)和R={si1,si2,L,siP}(|R|=P)表示网络中的传感器节点集合和Sink节点集合，V=S∪R，用E表示网络中两个节点之间的通信边，则监测区域布设的WSNs可以用有向图G(V,E)来表示。若网络中Sink节点候选位置集合为Q={L1,L2,L,LM}(|Q|=M)，为了使Sink节点到各传感器节点的总加权距离最小，将WSNs多Sink节点布局目标Obj1表示为目标函数式(1)。目标函数中的参数定义详见表1。

表1 WSNs多Sink节点布局目标参数

定义的决策变量Xj和Yij描述如下：

可以建立的多Sink节点布局目标函数Obj1的数学模型表示为：

(1)

(2)

(3)

Yij-Xj≤0 ∀i∈S，j∈Q

(4)

Yij=0，1 ∀i∈S，j∈Q

(5)

Xj=0,1 ∀j∈Q

(6)

目标函数式(1)是多Sink节点布局目标函数Obj1的数学模型，使各传感器节点到Sink节点的总加权距离最小化；约束式(2)是保证每个传感器节点只能将发送的请求数上传到最近的一个Sink节点；约束式(3)是保证网络中的Sink节点数量为预置的 个；约束式(4)是保证传感器节点只能被建立的Sink节点服务；约束式(5)和(6)是目标函数中所有决策变量的0-1约束。

1.3.2 网络能耗目标

在WSNs中，传感器节点负责把采集的数据经过一跳或多跳上传到Sink节点，并通过外网(Internet/GPRS/3G等)上传至监控中心。由于多Sink节点适用于大规模、高可靠性的网络，网络传感器节点密度及距离都较大，因此采用分层的多跳分簇路由协议，簇头兼具中继和数据融合的作用，Sink节点融合转发簇头或最近传感器节点数据至上层网络。假设每个传感器节点在固定的时间内发送li(i=1,2,L,N)位数据，则每轮传感器节点传输数据消耗的能量为：

(7)

每轮传感器节点接收li位数据消耗的能量为：

Eri=liEelec

(8)

式中：N为网络中的传感器节点数量；Eelec为接收或发送单位数据的无线电路损耗能量；d0和d分别为距离门限和各传感器到簇头或Sink节点间距离；eft与emp为自由空间功率放大系数和多径衰落功率放大系数[11]。

假设网络中簇头节点个数为K，m为簇内传感器节点数目，则每轮簇头消耗的能量包括接收簇内节点数据时消耗能量，数据融合时消耗能量，以及发送融合后数据所消耗能量的总和，即：

(9)

式中：Eda为簇头融合单位数据时消耗能量；ε为簇头融合后的总数据量传输到Sink节点所消耗的eftd2或empd4能量。

故为使多Sink节点传感网能耗最小化，建立的多Sink节点网络能耗目标Obj2的数学模型为：

(10)

2 多Sink节点部署优化方法实现

2.1 化为单目标

(11)

2.2 部署优化方法的实现

在对WSNs的多Sink节点布局优化模型实现过程中，采用上升启发式算法[12]对式(1)、式(9)和式(10)的最优目标值进行求解，求解过程描述如下。

输入：初始化所有参数。

(1)设置Sink节点数量P值，目标权重系数w值；

(2)求解P个Sink节点的初始目标值，并将P个节点位置设置为初始最优方案。即从候选M个Sink节点位置中随机选取P个节点位置，计算集合P的目标值Obj3，初始最优方案设置为OL1×P={L1,L2,L,Lt},t∈P，并设置迭代次数最大值gmax值；

(3) forg=1∶1∶gmax

(4)从候选 个Sink节点位置中随机选取节点位置i和j(i∈P,j∉P)，将i和j交换，组成新的集合P′；

(10)end if

(11)end for

输出：最优目标Obj3和集合P对应的最优Sink节点位置。

3 仿真实验与分析

3．1 实验参数设置

3．2 布局计算结果

图2 WSNs多Sink节点最优布局

图3 Sink节点布局寻优过程中解的变化

3．3 Sink节点数量与最优布局的关系

在实际应用场景中，Sink节点数量可根据网络规模、数据精度及传输时延等要求做出适当调整，因此，本文分析了当Sink节点数量P从1到10变化时对最优布局的影响，且预置Sink节点数量 发生变化时，最优布置方案也会发生变化。实验结果表明，当 从1到10增加时，网络最小加权距离逐步减小，如图4所示。这种现象与文献[10]中所得到的结果相吻合。在此基础上，本文从WSNs网络生命周期考虑，进一步分析了多Sink节点数量与网络能耗值的关系，如图5所示。

图4 Sink节点数量与最小加权距离的关系

图5 Sink节点数量与网络能耗的关系

在图5中，随着Sink节点数量的增加，网络能耗值整体上呈现出逐步减少的趋势，但个别P值对应的能耗值有所增加，呈现出与最小加权距离不同步的结果。产生这种现象的原因是：由于本文中WSNs的路由协议采用Leach协议，该协议是一种带有族头选举的分层、多跳路由协议，其簇头的选举是变化的，会导致个别P值对应的多Sink节点的网络能耗会出现一定偏差。这种不同步的结果说明，在考虑WSNs多Sink节点布局优化时，除了要考虑加权距离最小化外，还必须考虑Sink节点数量与网络能耗值的关系。

图6综合了最小加权距离与网络能耗，描述了P从1到10变化时Sink节点数量与多目标最优值的关系。表2详细列出了多Sink节点数量的最优布局方案。从该表中数据可以看出，仅考虑单目标(最小加权距离或最小网络能耗)的多Sink节点布局方案，与同时考虑两个目标的优化方案存在一定的差异性。多目标的布局方案兼具了加权距离和网络能量消耗，要优于单目标的布局方案，更适用于WSNs实际应用场景。

图6 Sink节点数量与多目标最优值的关系

Sink节点数量布局目标能耗目标(10-6)多目标(10-6)Obj*1节点位置Obj*1节点位置Obj*3节点位置117821(10.9,10.0)1502(3.7,3.4)78742(11.5,8.3)212920(14.1,17.1),(9.3,7.6)1407(13.9,6.0),(18.3,10.7)49898(11.3,14.1),(5.8,2.9)39952(4.1,4.5),(12.9,7.8),(14.2,17.5)1228(11.6,9.8),(0.4,11.3),(16.8,16.5)66667(2.3.16,9.8),(10.9,9.0),(16.8,16.5)47572(15.3,17.5),(4.7,3.3),(2.6,16.6),(13.0,8.2)1285(8.1,10.3),(7.4,5.5),(9.0,4.3),(3.7,3.4)96109(15.8,11.9),(7.9,5.9),(2.5,16.5),(16.7,16.5)56456(14.8,17.4),(2.1,17.1),(14.2,7.1),(5.2,4.0)(9.8,9.5)1049(7.6,10.2),(17.2,1.1),(2.7,18.3),(3.7,3.4),(16.8,16.5)153121(16.0,19.7),(0.9,16.8),(12.0,8.9),(3.7,3.4),(16.7,16.5)65816(2.1,17.8),(15.6,10.5),(4.7,3.3),(14.2,6.3),(9.8,9.5),(15.2,17.2)1163(5.8,2.9),(17.2,1.1),(3.1,7.2),(13.7,8.1),(3.7,3.4),(10.3,4.6)98364(2.6,15.4),(7.8,1.4),(15.0,16.1),(13.7,8.1),(3.7,3.4),(10.3,4.6)75327(15.4,10.6),(19.1,18.8),(10.3,10.8),(14.2,18.0),(13.6,6.2),(5.2,3.5),(2.3,16.9)1045(2.3,15.0),(6.5,19.3),(17.0,2.4),(18.1,9.8),(13.4,12.3),(3.7,3.4),(2.8,5.0)94790(14.0,9.7),(16.0,19.7),(17.0,2.4),(9.8,9.5),(0.9,13.5),(3.7,3.4),(2.9,16.6)84723(13.7,17.4),(5.3,3.1),(10.9,9.4),(14.8,10.4),(1.3,1.7),(13.5,5.4),(2.2,18.0),(19.0,18.8)1181(6.3,8.1),(5.1,5.0),(18.4,0.9),(18.1,9.7),(0.2,6.2),(5.5,0.7),(2.7,5.0),(7.8,10.9)78026(13.6,17.9),(5.1,5.0),(11.513.3),(18.0,17.6),(16.6,10.7),(13.0,4.2),(2.9,16.6),(7.8,10.9)94552(19.3,19.4),(8.3,8.9),(7.1,17.5),(1.0,1.8),(15.0,17.0),(13.6,6.1),(0.9,17.5),(15.0,10.0),(4.4,4.0)1083(6.3,8.1),(5.1,4.9),(9.9,4.2),(7.4,4.6),(17.2,6.6),(4.6,17.1),(2.8,16.5),(15.0,11.7),(12.0,3.3)186616(14.1,3.5),(5.2,5.0),(11.5,13.3),(18.1,9.8),(12.8,16.6),(19.5,15.3),(2.9,16.5),(10.5,7.9),(12.0,3.4)103750(1.6,16.0),(9.7,9.4),(7.1,17.5),(14.0,7.0),(13.2,0.8),(13.5,17.9),(18.9,17.5),(1.3,1.7),(15.4,10.8),(4.4,4.0)1017(14.1,3.5),(8.2,10.7),(6.5,19.3),(19.9,15.4),(19.6,6.2),(14.0,7.2),(2.8,16.5),(10.5,7.7),(15.0,11.7),(14.6,15.1)327556(6.3,8.1),(10.9,9.0),(6.5,19.3),(18.4,19.9),(17.2,6.6),(5.5,0.7),(2.9,16.5),(10.5,7.8),(15.0,11.7),(14.6,15.1)

3．4 Sink节点数量与目标权重的关系

表3描述了目标权重系数变化对多Sink节点布局的影响。其中，Sink节点数量P=2，权重系数w值从0．1～0．9。从表中可以看出，权重系数w变化时，Sink节点多目标最优方案也相应变化。当w增加时，最小加权距离在总目标中的比重增加；相反，则网络能耗目标的比重增加。实际应用时，可根据WSNs的应用场景适当调整目标权重系数，得到更满意的多Sink节点部署方案，从而扩大本论文所提出部署方法的适用范围。

表3 W值变化对多Sink节点布局的影响

4 结论

本文通过分析WSNs的特点及单Sink节点传感器网络存在的问题，研究WSNs多Sink节点最佳部署策略，提出了一种能耗均衡的多Sink节点部署优化方法。与传统多Sink节点布局不同，本文建立的布局优化模型综合考虑了距离和网络能耗两个指标，并结合上升启发式算法实现了多sink节点的仿真布局。实验数据分析和结果表明，本文提出的多Sink节点部署模型及其部署优化方法，与只考虑单目标(最小加权距离或最小网络能耗)的多Sink节点布局方案相比，部署方案存在一定的差异性，为WSNs多Sink节点部署策略提供了一种参考方案。

[1] AKYILDIZ I F, SU W, SANKARASUBRAMANIAM Y, et al． Wireless sensor networks: a survey． Computer Networks, 2002, 38(4): 393-422．

[2] CHONG C Y, KUMAR S P． Sensor networks: evolution, opportunities, and challenges． Proceedings of the IEEE, 2003, 91(8): 1247-1256．

[3] YOUNIS M, AKKAYA K． Strategies and techniques for node placement in wireless sensor networks: A survey． Ad Hoc Networks, 2008, 6(4): 621-655．

[4] SLIJEPCEVIC S, POTKONJAK M． Power efficient organization of wireless sensor networks． Communications, 2001． ICC 2001． IEEE International Conference on． IEEE, Helsinki, 2001．

[5] KIM H, SEOK Y, CHOI N, et al． Optimal multi-sink positioning and energy-efficient routing in wireless sensor networks． Berlin: Springer Berlin Heidelberg, 2005: 264-274．

[6] HAEYONG K, TAEKYOUNG K, PYEONGSOO M． Multiple sink positioning and routing to maximize the lifetime of sensor networks． IEICE transactions on communications, 2008, 91(11): 3499-3506．

[7] DAI S, TANG C, QIAO S, et al． Optimal multiple sink nodes deployment in wireless sensor networks based on gene expression programming． 2010 ICCSN’10 Second International Conference on IEEE, Chengdu, 2010．

[8] FLATHAGEN J, KURE Q, ENGELSTAD P E． Constrained-based multiple sink placement for wireless sensor networks． 2011 IEEE 8th International Conference on IEEE, Valencia, 2011．

[9] 吴中博，樊小泊，陈红． 基于能量水平的多Sink节点传感器网络路由算法． 计算机研究与发展，2008，45(1): 41-46．

[10] 罗玎玎，赵海，尹震宇，等． WSNs 中基于 PMP 的多 SINK 节点布局研究与实现． 小型微型计算机系统，2007，28(6): 979-982．

[11] HEINZELMAN W R, CHANDRAKASAN A, BALAKRISHNAN H． Energy-efficient communication protocol for wireless microsensor networks． Proceedings of the 33rd annual Hawaii international conference on． IEEE, Hawaii, 2000．

[12] TEITZ M B, BART P． Heuristic methods for estimating the generalized vertex median of a weighted graph． Operations research, 1968, 16(5): 955-961．

Novel Optimal Deployment Method of Multiple Sink Nodes in WSNs for Balanced Energy Consumption

SHAO Kai-li, FU Hui

(College of HUANGHE Science & Technology，Zhengzhou 450063，China)

Wireless sensor network (WSNs) with a single sink node has some disadvantages of the quickness of consuming energy on the critical path, the singleness of routing algorithm, and the invalidation of the sink node. To solve these problems, a novel multi-objective programming approach for multiple sink nodes in WSNs was developed in this paper. In our approach, multiple sink nodes were not only deployed，but energy consumption was also considered as the uncertain parameters. Our multi-objective model attempted to minimize the weighted distance from sensor nodes to sink nodes, at the same time to balance WSNs energy consumption through minimizing the objective of consuming energy. Considering the global evaluation of two objectives, a compromise programming model was formulated and solved to obtain a non-dominating compromise solution with ascent algorithm. Experiment results show that the proposed approach can keep both optimal deployment of multi-sink nodes and balance of energy consumption in WSNs, which can prolong the lifetime of the network.

WSNs;multiple sink nodes; optimal deployment; multi-objective model

郑州市科技攻关计划项目(20120473)

2015-05-30 收修改稿日期：2015-07-27

TP393

A

1002-1841(2015)09-0106-05

邵开丽(1976—)，讲师，硕士，研究方向为物联网技术。 E-mail：sklemail@163．com 付辉(1982—)，讲师，硕士，研究方向为计算机应用。 E-mail：iefh@163．com