于志博，孔祥雪，裴金金

(天津大学 电气与自动化工程学院，天津 300072)



移动Sink的传感器网络路径优化策略

于志博，孔祥雪，裴金金

(天津大学 电气与自动化工程学院，天津 300072)

在无线传感器网络(WSNs)中引入移动Sink可以避免网络拥塞和能量空洞并降低网络能耗，但由于移动速度的限制导致时延较大。针对这一问题，提出了时延约束下的移动Sink路径优化策略，根据时延和网络能耗之间的关系设计了可调节的节点权重，通过模拟退火遗传算法得到最优节点权重，并依据此权重通过迭代得到汇聚节点和最佳移动路径。仿真结果表明:该策略能保证在满足时延约束的前提下降低网络能耗，且收敛速度快。

无线传感器网络； 移动Sink； 节点权重； 模拟退火遗传算法； 路径优化

0 引 言

在无线传感器网络(wireless sensor networks，WSNs)中，如何降低能耗是该领域研究重点。设计高效节能的软硬件和通信协议在一定程度上降低了能耗[1,2]，但不能改变由于Sink位置固定导致的网络拥塞和能量空洞问题。

采用移动Sink不仅避免了上述问题，还极大提高了网络生存时间[3]，但会产生较大时延。为了取得能耗与时延的折中，文献[4,5]通过限制每个节点数据转发跳数选择汇聚节点并通过汇聚节点建立路径。文献[4]在最短路径树上从最远叶节点开始迭代地寻找满足跳数要求的汇聚节点，而文献[5]从根节点开始根据跳数寻找汇聚节点，再根据汇聚节点之间及与其他节点间的拓扑关系调整汇聚节点的位置和个数。文献[6,7]从全网范围内考虑所有节点距离各自所属汇聚节点的总跳数，使得满足时延条件下总跳数最少。文献[6]建立最小连通支配集作为汇聚节点的候选节点，再根据候选节点权重进行删减直到满足时延要求。文献[7]则根据节点权重从所有节点中选择汇聚节点，直到达到时延要求。

时延和网络能耗是基于移动Sink的WSNs重要性能指标。鉴于此，本文研究了满足时延约束下网络能耗最小的移动Sink路径优化策略。根据能耗和时延的关系建立了优化模型，并设计了可调节的节点权重，通过模拟退火遗传算法(simulated annealing genetic algorithm，SAGA)寻找最优节点权重，提出了基于SAGA权重的路径优化(SAGA weight-based path optimization，SWPO)算法得到Sink移动路径。该策略能有效降低网络能耗，且收敛速度快。

1 网络模型

本文考虑由一个移动Sink和n个传感器节点组成的WSNs，节点通信半径为R，网络是全连通的，允许时延为t。汇聚节点由网络周期性地选取，并缓存普通节点传输的数据。Sink以恒定速度v从监测区域边缘出发，依次访问汇聚节点收集数据，并最终返回起点，该过程称为一轮。该网络可用图G=(S,B)表示。其中S={si}为节点集合，B={(si,sj)|D(si,sj)≤R}为通信链路集合，D(si,sj)为两节点间欧式距离。H={hi}为汇聚节点集合，且H⊆S。图1为基于移动Sink的WSNs示意图。在基于移动Sink的WSNs中，要综合考虑网络能耗与时延。本文目标是满足数据时延的前提下，实现网络能耗的最小化。

图1 基于移动Sink的WSNs示意图Fig 1 Illustration of mobile sink-based WSNs

最大数据时延是Sink访问所有汇聚节点所需的时间。路径越长，时延就越大。对于给定的时延t，满足

(1)

式中 hs为起点。

传输能耗占网络能耗比重很大，故本文仅考虑传输能耗。节点si单轮中采集的数据量为p，该数据传输至汇聚节点并由Sink收集过程中所有节点能耗为

Eci=cip(et+er)+pet

(2)

式中 ci为si到其所属汇聚节点的跳数，节点通过最短路由方式将数据传输给距自己跳数最少的汇聚节点，et和er分别表示发送和接收1 bit数据的能耗。单轮中所有节点数据最终被Sink收集过程中全网能耗为

(3)

式中 c为所有节点到其所属汇聚节点的总跳数。

(4)

由式(3)可得，全网能耗取决于c。故时延约束下的网络能耗最小化问题等价于时延受限的最小跳数问题(minimum hop counts under the delay constrains，MHCDC)，即从S中选取一组节点加入到H中，满足Sink遍历H中节点并返回的路径长度少于规定时延内的距离，并使得总跳数最小，如式(5)所示

(5)

2 算法设计

2.1 节点权重

由于在MHCDC问题中需要最小化总跳数，并限制路径长度。本文定义节点si的权重如式(6)所示

(6)

式中 c(H)和LTSP(H)分别为汇聚节点集为H时的总跳数和最短路径长度。分子表示si加入到H中总跳数的减少量，减少量越多，si被选为汇聚节点的机会越大；分母表示si加入到H中路径长度的增加量，增加量越少，si被选为汇聚节点的概率越大。u ∈(0,1)为调节因子，负责调节路径长度增加量与总跳数减少量的影响程度，使节点权重发生变化，根据权重得到的汇聚节点及对应的路径和网络能耗会改变。

2.2 基于u值的权重优化

考虑到u值变化会改变路径长度增加量和总跳数减少量的影响程度，采用SAGA对权重的u值进行优化，以获得优化的Sink路径。优化过程中，将SA法作为GA求解过程中的个体替换策略，实现全局最优，同时收敛速度较快。步骤如下：

1)初始化：初始化GA种群数目、遗传代数、变异概率及SA初始温度、终止温度和每个温度下迭代次数等；

2)随机产生初始种群：对种群中的每个个体进行二进制编码；

3)将每个种群中的个体带入式(6)中，并得到每个个体对应的汇聚节点、路径及网络能耗，并计算适应度；

4)进行交叉、变异操作；

5)使用SA对个体进行选择操作；

6)判断是否达到最大代数，若满足，则结束；若不满足，则将步骤(5)得到的个体重新进行步骤(3)操作。

2.3 基于SAGA权重的路径优化算法

本文采用Floyd Warshall算法求取路由，得到总跳数c。为求取最短路径，采用文献[8]中方法求解TSP问题。首先，所有节点根据最优u值和式(6)计算各自权重。然后，将权重最大的节点加入到H中。随着H中节点变化，S中节点的权重也会变化，更新S中所有节点权重，再将权重最大的节点加入到H中，不断迭代，直到满足式(1)结束。最后得到最小网络能耗下的汇聚节点和路径。

3 仿真分析

为考察算法性能，对本文提出的SWPO算法进行性能分析，并与基于效用的贪心算法来选择CP节点(utility-based greedy heuristic for choosing collection point,CPUG)算法[7]进行了比较。在仿真实验中，200个节点随机部署在200 m×200 m区域内，节点初始电量为500 J，通信半径为30 m，Sink速度为1 m/s，每轮从每个节点收集30 kbit数据，时延上限为5 min。采用文献[6]的能耗模型。

3.1 时延上限对网络能耗的影响

时延上限会限制移动路径的长度，进而影响汇聚节点的选择，导致所有节点到其所属汇聚节点跳数和发生变化。当移动速度不变时，随着时延上限的增加，Sink可移动的路径长度增加，所有节点到其所属汇聚节点跳数和减少，从而网络能耗降低。从图2可以看出:两种算法随着时延上限的增加网络能耗降低，并且SWPO算法性能优于CPUG。

图2 时延上限与网络能耗的关系Fig 2 Relationship between delay bound and energy consumption of network

3.2 移动速度对网络能耗的影响

随着Sink移动速度的增加，在规定的时延要求下，可移动的路径长度增加，所有节点到其所属汇聚节点跳数和减少，从而网络能耗降低。图3给出了不同移动速度下网络能耗的变化。两种算法的网络能耗均随着Sink速度的增加而降低，且SWPO算法性能优于CPUG。

图3 移动速度与网络能耗的关系Fig 3 Relationship between moving speed and energy consumption of network

3.3 节点数量对网络能耗的影响

随着网络节点数量的增加，由于路径长度没有变化，汇聚节点所属的节点数量增加，全网传输总跳数增加，导致网络能耗增加。图4反映了两种算法下网络能耗均随着节点数量的增加而增加，且SWPO算法性能优于CPUG。

图4 节点数量与网络能耗的关系Fig 4 Relationship between number of nodes and energy consumption of networks

3.4 SAGA与GA对比

由图5可以看出使用本文SAGA求解，在30代已经稳定在最优解，而使用GA求解，在38代时获得稳定最优解。这是由于本文在SAGA中，使用SA替代GA中的选择操作，实现全局快速寻优，收敛速度较快。

图5 遗传代数与网络能耗的关系Fig 5 Relationship between genetic algebra and energy consumption of networks

4 结 论

本文研究了基于移动Sink的传感器网络时延受限的路径优化策略，并提出了SWPO算法。根据数据时延和网络能耗的关系设计了可调节的节点权重，采用SAGA算法得到最优的节点权重，根据该权重得到汇聚节点，从而得到网络能耗最小的移动路径。仿真结果表明，该算法能有效地选择汇聚节点，规划移动路径，降低网络能耗，且收敛速度快。

[1] Tang Lei,Sun Yanjun,Gurewitz O,et al.PW-MAC:An energy-efficient predictive-wakeup MAC protocol for wireless sensor networks[C]∥IEEE INFOCOM 2011 Proceedings,Shanghai,China:IEEE,2011:1305-1313.

[2] Mikhaylov K,Tervonen J.Optimization of microcontroller hardware parameters for wireless sensor networks node power consumption and lifetime improvement[C]∥2010 International Congress on Ultra Modern Telecommunications and Control Systems and Workshops (ICUMT),Moscow,Russia:IEEE,2010:1150-1156.

[3] Salarian H,Chin K W,Naghdy F.An energy-efficient mobile-sink path selection strategy for wireless sensor networks[J].IEEE Transactions on Vehicular Technology,2014,63(5):2407-2419.

[4] Zhao Miao,Yang Yuanyuan.Bounded relay hop mobile data ga-thering in wireless sensor networks[J].IEEE Transactions on Computers,2012,61(2):265-277.[5] Chowdhury S,Giri C.Data collection point based mobile data gathering scheme with relay hop constraint[C]∥2013 International Conference on Advances in Computing,Communications and Informatics(ICACCI),Mysore,India:IEEE,2013:282-287.

[6] 丁 杰,刘丹谱.移动Sink环境下的无线传感器网络数据收集节能算法[J].北京邮电大学学报,2013,36(5):51-55.

[7] 张希伟,沈 琳,蒋益峰.移动协助传感器网络中Sink的路径优化策略[J].通信学报,2013,34(2):85-93.

[8] Cormen T H,Leiserson C E,Rivest R L,et al.Introduction to algorithms[M].3rd ed.Cambridge,America:The MIT Press,2009:404-405.

Mobile sink-based path optimization strategy in wireless sensor networks

YU Zhi-bo,KONG Xiang-xue,PEI Jin-jin

(School of Electrical Engineering and Automation,Tianjin University,Tianjin 300072,China)

Introducing mobile sink in wireless sensor networks(WSNs)can avoid network congestion and energy hole and reduce energy consumption of network,but it lead to large delay because of limitation of moving speed.Aiming at this problem,path optimization strategy of mobile sink under delay constrains is proposed.Adjustable node weight is designed according to relationship between delay and energy consumption of network.The optimal node weight is obtained through simulated annealing genetic algorithm.The sink nodes and the optimal moving path are acquired through iteration procedure based on the optimal node weight.Simulation results show that the strategy can reduce energy consumption network and have fast convergence under the premise of meeting delay constrains.

wireless sensor networks(WSNs);mobile sink;node weight;simulated annealing genetic algorithm;path optimization

10.13873/J.1000—9787(2016)11—0044—03

2016—01—04

TP 393

A

1000—9787(2016)11—0044—03

于志博(1990-)，男，满族，河北秦皇岛人，硕士研究生，研究方向为无线传感器网络。