一种无线传感网的Sink节点移动路径规划算法研究*

陈友荣,陆思一,任条娟,,杨海波

(1.浙江树人大学信息科技学院,杭州 310015;2. 常州大学信息科学与工程学院,江苏 常州 213164)

一种无线传感网的Sink节点移动路径规划算法研究*

陈友荣1,2*,陆思一2,任条娟1,2,杨海波1

(1.浙江树人大学信息科技学院,杭州 310015;2. 常州大学信息科学与工程学院,江苏 常州 213164)

为寻找传感节点均匀分布时Sink节点的最优移动路径和最大网络生存时间,提出一种无线传感网的Sink节点移动路径规划算法(MPOA)。在MPOA算法中,将Sink节点的数据收集范围分解成多个圆环,将监测区域分解成多个网格。根据Sink节点的停留位置和多跳通信方式,采用数学公式表示每一个网格的单位节点能耗,从而获得Sink节点移动的网络生存时间优化模型。采用修正的混合粒子群算法求解该优化模型,获得网络生存时间、Sink节点的停留位置和移动路径的最优方案。仿真结果表明:MPOA算法可寻找到Sink节点的最优移动路径,从而平衡网络能耗,提高网络生存时间。在一定的条件下,MPOA算法比Circle,Rect和Rand算法更优。

无线传感网;移动Sink节点;路径规划;粒子群算法

无线传感网WSNs(Wireless Sensor Networks)由空间分布的自主传感节点和Sink节点组成,可协同监测温度、声音、振动、压力、运动等物理和环境参数,在战场监控、战场损伤评估、工业过程监控、机器运行状况监控、家庭自动化、交通监控等军事、工业和民用领域上具有较大的应用价值和市场潜力[1-2]。

在无线传感网中,能量效率是无线传感网的最重要问题之一。由于传感节点的电池能量有限而且其电池更换需要花费较多的时间和精力,因此无线传感网需要在无人干预下自行运行足够长的时间。但是在静态Sink节点的无线传感网中,由于多跳路由具有热点且数据流量集中,靠近Sink节点的传感节点消耗较多的能量且失效较早。这个问题被称为无线传感网的热点问题[3]。热点问题可恶化无线传感网的网络连接和生存时间,甚至使无线传感网不能正常工作。为克服热点问题,很多学者研究Sink节点的移动。移动Sink节点可提供负载均衡,让其周围的热点发生变化且出现在网络的各个区域,这有助于实现统一的能量消耗,从而延长网络生存时间。

在Sink节点移动的无线传感网中,需要确定Sink节点的停留位置和移动路径,因此Sink节点的移动路径选择问题是其急需解决的问题之一。目前,相关路径选择算法的研究取得一定的成果。文献[4]考虑飞行器作为Sink节点,移动收集传感节点的存储数据。根据其移动特性重构基于TSP(traveling salesman problem)算法的移动路径,并根据数据收集时间调整路径,使其数据传输时延最小。但是该算法没有考虑传感节点的能耗和网络生存时间的优化问题。有些学者考虑Sink节点的单跳数据收集,研究Sink节点的移动路径选择算法。如文献[5]基于传感节点的位置信息,采用范围约束分簇算法确定每一个簇头的位置,即Sink节点的停留位置,利用TSP算法寻找遍历所有停留位置的路径。文献[6]建立权衡网络生存时间和Sink节点移动路程的优化模型,采用遗传算法求解该优化模型,获得可将传感节点分成多个簇的停留位置和移动路径。文献[7]根据节点的位置等信息,建立Sink节点移动单跳收集数据下的网络生存时间优化模型,并构建决策树求解该优化模型,获得Sink节点的移动路径。文献[8]将监测区域分解成多个三角形,获得经过三角形的3个顶点的圆。每一个圆心作为Sink节点的停留位置。Sink节点采用贪婪算法确定下一个停留位置。但是由于Sink节点的单跳数据收集范围有限,为保证能收集到所有传感节点的数据,其移动路径较长且数据传输时延较大。另一些学者考虑Sink节点的多跳数据收集,研究相关Sink节点的移动路径选择算法。如文献[9]建立优先级高且移动距离不小于阈值的虚拟点集合,采用TSP算法求解能遍历该集合内所有虚拟点的最短路径。文献[10]将监测区域分成多个大小相同的圆盘。计算每一个圆盘内Sink节点的停留位置,采用量子遗传算法获得最短移动路径。文献[11]利用分簇技术将传感节点分成通信半径相同的簇,选择剩余能量相对充足的传感节点作为簇头。根据簇头的位置,利用TSP算法构建一条尽可能短的移动路径。文献[12]选择权值较高的传感节点作为RP点(Rendezvous Point),建立点集合,寻找能访问所有RP点且不超过最大数据传输时延的路径。文献[13]考虑传感节点网格分布和邻居传感节点的剩余能量变化,提出一种Sink节点移动的分布式启发算法,寻找其停留位置。但是在文献[9-13]中,假设所有传感节点都能获知自身位置坐标。为保证定位精度,需要安装GPS或北斗定位模块,这增加了节点能耗和系统硬件成本。且Sink节点在路径选择前需要获知传感节点的位置、能量等信息。文献[14]提出圆形移动路径(CIRCLES),但是该算法只考虑传感节点的定位,没有考虑Sink节点的数据收集。

文献[8-13]可寻找到Sink节点的若干个停留位置,获得其移动路径,从而达到节约传感节点能耗,提高网络生存时间的目的。但是这些移动路径是否具有已经达到最大提高网络生存时间的效果,仍需要进一步研究,而且很多移动路径需要传感节点的位置、能量等信息。因此在上述文献的基础上,提出了一种无线传感网的Sink节点移动路径规划算法MPOA(Movement Path Optimization Algorithm of Sink Node for Wireless Sensor Networks)。MPOA算法不需要获知传感节点的位置、能量等信息,只考虑传感节点均匀分布和Sink节点的多跳数据收集,研究Sink节点的移动对整个监测区域能耗分布的影响。将Sink节点的数据收集范围分解成多个圆环和内圆,外层圆环内传感节点只发送给其邻居内层圆环或邻居内圆。根据上述多跳数据收集的特点,提出了Sink节点移动的网络生存时间优化模型。采用修正的混合粒子群算法求解该优化模型,获得最优方案——Sink节点的移动路径、停留位置和网络生存时间。该算法可寻找到一条最大化网络生存时间的移动路径,并为其他移动路径选择算法提供参考。

1 算法原理

在MPOA算法中,假设:无线传感网的长方形监测区域内存在多个传感节点和1个Sink节点。当存在多个Sink节点时,将监测区域分成与Sink节点数量相同的子区域,每一个Sink节点负责其中一个子区域,则多个Sink节点的数据收集问题转换成多个单一Sink节点的数据收集问题;监测区域内传感节点均匀分布;Sink节点可移动到监测区域的任一位置;所有传感节点的能量有限,且具有统一的通信范围、初始节点能量等特点,是同构的传感节点。虽然Sink节点的能量也有限,但是可通过人工方式进行更换。

如图1所示,Sink节点停留在某一个位置时,采用多跳通信的方式收集以自身位置为圆心和以d为半径的圆内传感节点的数据,即其数据收集范围是一个圆形。将该圆分成一个半径为r的内圆和厚度均为r的n-1个圆环,其中n=d/r,且d远大于r。外层圆环内传感节点只转发给其邻居内层圆环或内圆内传感节点。根据上述的假设,当Sink节点的位置固定且传感节点随机均匀分布时,Sink节点数据收集范围内传感节点能耗也基本确定。为方便计算分布在监测区域内某一个位置的传感节点能耗,如图2所示,将方形监测区域分成大小相同的矩形网格,按照从左到右,从上到下的原则对每一个网格进行编码,并计算每一个网格中心的位置坐标。当Sink节点沿着某一个路径移动时,根据每一个网格中心的位置,计算所有网格的单位节点能耗,其中网格的单位节点能耗定义为当Sink节点沿着某一个路径移动且传感节点在该网格中心上时,传感节点转发其他传感节点数据和发送自身传感节点数据的单位时间能耗,则可获得整个监测区域内单位节点能耗的分布情况、单位节点能耗最大的网格和网络生存时间。

图1 Sink节点的数据收集

图2 监测区域的网格划分

但是MPOA算法仍需要解决以下二个问题:一是当Sink节点沿着某个路径移动时,如何运用数据公式表达每一个网格的单位节点能耗和网络生存时间,建立网络生存时间的优化模型。二是如何采用修正的混合粒子群算法求解该优化模型,获得Sink节点的最优移动路径。这二个问题的具体解决如下。

1.1 优化模型的建立

令Sink节点的当前停留位置坐标为(xs,ys),网格中心i的位置坐标为(xi,yi)和监测区域的长和宽为(Lx,Ly),则经过Sink节点和网格中心i的直线方程为

(1)

Sink节点到网格中心i的有向射线与监测区域的边界交点为(fx(xs,ys,xi,yi),fy(xs,ys,xi,yi)),即(xc,yc)。假设监测区域为长方形,则边界交点坐标的计算方法如下:

当xs=xi且ys=yi时,则两点重合,令yi=yi+0.1,则xc=xi,yc=Ly。

当xs=xi且ys>yi时,则xc=xi,yc=0;

当xs=xi且ys

当xs>xi且ys=yi时,则xc=0,yc=yi;

当xs

当xs≠xi且ys≠yi时,则需要判断该点出现在哪个三角形内。如图3所示,如果xsxi,yi≤ysxi/xs时,则(xi,yi)在三角形2内,将yc=0代入式(1),可得xc=-yi(xs-xi)/(ys-yi)+xi,yc=0。如果xs(ys-Ly)(xi-Lx)/(xs-Lx)+L或xs>xi,yi>(ys-Ly)xi/xs+Ly时,则点(xi,yi)在三角形4内,可得xc=(Ly-yi)(xs-xi)/(ys-yi)+xi,yc=Ly。如果xs>xi,ys(xi)/xs≤yi≤(ys-Ly)xi/xs+Ly时,则点(xi,yi)在三角形1内,可得xc=0,yc=-xi(ys-yi)/(xs-xi)+yi。

图3 边界交点的计算

根据直线与监测区域的边界交点和Sink节点的多跳数据收集方式,计算边界交点(xc,yc)经过网格中心i到Sink节点的最大跳数Ni,max为

(2)

式中:⎣x」表示大于或等于x的最小整数。计算网格中心i所在位置到Sink节点的跳数Ni为

(3)

Sink节点停留在某一个位置时,网格中心i的单位节点能耗由接收和发送该位置到边界交点区域内传感节点的单位时间能耗和该位置上发送自身数据的单位时间能耗组成,即为

(4)

式中:((Ni,maxr)2-π(Nir)2)ρ表示自身传感节点所在圆环到最外层圆环的传感节点个数,[π(Nir)2-π(Nir-r)2]ρ表示自身传感节点所在圆环的传感节点个数,ρ表示传感节点的密度,Si表示传感节点的感知数据速率,Er表示传感节点接收单位bit数据的能耗,ε表示传感节点发送单位bit数据的能耗系数。由式(4)可知,网格中心i的单位节点能耗与传感节点的密度无关。

当Sink节点沿着某一路径P=[p1,p2,…,pm]移动且在m个停留位置上收集传感节点的数据时,该移动路径下网格中心i的总单位节点能耗,即该网格的单位节点能耗为

(5)

则网络生存时间为

T=min(Einital/Ei),∀i∈V

(6)

式中:V表示所有网格中心集合,Einital表示初始能耗。根据上述分析,考虑Sink节点移动距离和停留位置个数有限,建立网络生存时间的优化模型。

(7)

式中:num(P)表示移动路径P的停留位置个数,NP表示允许的最大停留位置个数,Lenth(P)表示移动路径P的路程,LP表示允许的最大移动路程。

1.2 模型的求解

标准粒子群算法虽然可以求解优化模型(7),且操作简单,但是随着迭代次数的不断增加,有可能收敛到局部最优解。混合粒子群算法摒弃了传统粒子群算法中的通过跟踪极值更新粒子群的方法,而是引入遗传算法的交叉和变异操作,可较好的搜索最优解。因此采用修正的混合粒子群算法求解优化模型(7)。但是在模型求解过程中,如果盲目寻找Sink节点的停留位置,则仍容易陷入局部最优解,很难寻找到Sink节点的全局最优位置。因此,需要考虑Sink节点的停留位置选择规则。

选择监测区域长和宽均为200 m,网格数量为20×20个。如图4所示,当Sink节点停留在监测区域的中心位置(100 m,100 m)时,监测区域的单位节点能耗呈山峰状分布,即Sink节点停留位置周围网格的单位节点能耗较高,并随着到Sink节点停留位置的距离增加,网格的单位节点能耗变小。如果Sink节点的停留位置集中在监测区域的几个相邻位置时,则其周围的网格单位节点能耗较大,网络生存时间较小,因此Sink节点的停留位置应围绕监测区域的中心位置,出现在监测区域的各个方向,从而降低网格单位节点能耗和提高网格生存时间。

图4 Sink节点停留在网格中心位置时的单位节点能耗分布图

当Sink节点的停留位置个数为NP时,根据角度将监测区域分成NP个子区域,每一个子区域内只能出现一个Sink节点的停留位置。如图5所示,将监测区域分成8个三角形子区域,每一个三角形中顶点为监测区域中心位置的角度数相同。修正混合粒子群算法的基本原理如下。

图5 Sink节点停留位置选择的子区域划分图

1.2.1 个体编码

优化模型中要求Sink节点的停留位置个数不超过最大值NP,且Sink节点的停留位置较多时,平衡网格单位节点能耗的效果较好,因此选择NP×2维数组表示Sink节点的移动位置。依次经过该数据中每个元素,则可构成Sink节点的移动路径,即粒子P=[p1,p2,…,pNp]。

1.2.2 适应度值

根据每一个粒子的移动路径,采用式(8)计算粒子适应度值。粒子的适应度表示Sink节点按照该粒子方案移动时的网络生存时间。网络生存时间越高,粒子适应度值越高,其移动方案越好。

(8)

1.2.3 交叉操作

粒子通过与个体极值粒子和群体极值粒子进行交叉操作,更新自身粒子。随机产生交叉位(c1,c2),1≤c1

1.2.4 变异操作

产生一个[0 1]区间内均匀分布的随机数。当该随机数小于变异因子b1时,该粒子发生变异,计算粒子中元素到监测区域中心位置的平均距离dave,对粒子中每一个元素进行以下变异操作:产生一个[0 1]区间内均匀分布的随机数,当该随机数小于变异因子b2时,在该元素所在的子区域内,产生到监测区域中心位置距离在区间[0.6dave,1.4dave]内均匀分布的随机位置,替换原来元素。

1.2.5 路径修正操作

当粒子的移动路径长度超过允许的最大移动路程LP时,采用式(9)和式(10)修正该粒子。

Px=(Px-Lx/2)LP/Lenth(P)+Lx/2

(9)

Py=(Py-Ly/2)LP/Lenth(P)+Ly/2

(10)

式中:Px表示移动路径P中所有元素的横坐标,Py表示移动路径P中所有元素的纵坐标。Lx和Ly分别表示监测区域的长和宽。

图6 MPOA算法的工作流程图

2 算法实现

如图6所示,MPOA算法的具体实现步骤如下:

步骤1 初始化算法的各种参数:迭代次数初值m1=1,当前粒子m2=1,监测区域的长Lx和宽Ly,圆环厚度r,网格数量,允许的最大停留位置个数Np,允许的最大移动路程LP,变异因子b1和b2,最大迭代次数M1,粒子个数M2等;

步骤2 初始化粒子群。将监测区域分成NP个子区域,并重复执行M2次以下操作可获得初始粒子群:在每一个子区域内随机产生一个Sink节点的停留位置,构成具有Np个停留位置的粒子。当该粒子的移动路径长度超过允许的最大移动路程LP时,通过式(9)和式(10)执行路径修正操作;

步骤3 依次选择粒子m2中元素,循环执行以下操作计算每一个网格的单位节点能耗:根据网格中心位置和元素位置,计算最大跳数Ni,max,通过式(4)计算该网格的单位节点能耗。通过式(8)获得网络生存时间,与历史极值比较,更新个体极值粒子和全局极值粒子。m2=m2+1。如果m2大于M2,则可获得每一个粒子的适应度值,获得个体极值和全局极值,m2=1,跳到步骤4,否则重新跳到步骤3;

步骤4 粒子m2分别与个体极值粒子和全局极值粒子进行交叉和变异操作;

步骤5 当该粒子的移动路径长度超过允许的最大移动路程LP时,通过式(9)和(10)执行路径修正操作。m2=m2+1,如果m2大于M2,则跳到步骤4,否则跳到步骤6;

步骤6m1=m1+1,如果m1大于M1,则结束算法,输出最优移动路径和最大网络生存时间,否则跳到步骤3。

循环执行关键步骤3～6,则可获得优化模型(7)的一个最优解,即Sink节点的最优停留位置和移动路径,从而达到提高网络生存时间的目的。

分析MPOA算法的时间复杂性。如图6所示,MPOA算法主要是M1M2个粒子进行适应度计算、交叉操作和变异操作。每一个粒子都需要根据其位置元素,计算每一个网格的单位节点能耗,即每一个粒子计算的时间复杂度是Θ(NpNgrid),其中Ngrid表示划分的网格数量。因此MPOA算法的时间复杂度是Θ(M1M2NpNgrid)。虽然MPOA算法采用混合粒子群算法,其时间复杂度相对较高,但是MPOA算法只需要在Sink节点部署前进行一次计算,且可事先通过计算机完成,再将最优移动方案通过无线、串口等方式传输给Sink节点,因此MPOA算法对时间复杂度的要求不高。

3 算法仿真

3.1 仿真参数选择

根据上述算法分析,在算法仿真中,采用MATLAB2014a仿真软件,选择以下参数计算Sink节点的移动路径和网络生存时间:监测区域的长和宽均为200 m,变异因子b1为0.5,变异因子b2为0.5,粒子个数为40,迭代次数为100,传感节点的感知数据速率Si为1 000 bit/s,传感节点接收单位bit数据的能耗Er为50×10-9J/bit,传感节点发送单位bit数据的能耗系数ε为100×10-12J/(bit·m2),初始能量Einital为1 000 J,网格大小为20×20。

3.2 仿真结果分析

选择圆环厚度r集合{10 m,20 m,30 m,40 m,50 m},Sink节点的停留位置个数num(P)集合{4,8,12,16,20}和移动路程Lenth(P)集合{100 m,200 m,300 m,400 m,500 m,600 m}中任一元素,计算网络生存时间最优值和其移动路径,并以某一参数的仿真结果为例说明MPOA算法的性能特点。

首先,分析MPOA算法的性能特点。选择迭代次数200,r=10 m,num(P)=12,Lenth(P)=400 m和3.1节内其他参数,计算每次迭代的网络生存时间,获得MPOA算法的收敛图(图7)、Sink节点的移动路径图(图8)和网格的单位节点能耗图(图9)。如图7所示,当迭代次数小于80时,MPOA算法根据与最优极值粒子的交叉和变异、路径修正等操作,不断寻找最优值,其网络生存时间不断增加。当迭代次数大于80时,MPOA算法寻找到最优值,其网络生存时间收敛于最优值,因此MPOA算法是收敛的。

图7 MPOA算法的收敛图

如图8所示,Sink节点的移动路径围绕监测区域的中心位置(100 m,100 m),在每一个方向上寻找到一个较优的停留位置,形成类似圆的移动路径。该移动路径分散在监测区域的各个方向,达到平衡网络负载和提高网络生存时间的效果。

图8 Sink节点的移动路径图

图9 网格的单位节点能耗图

当Sink节点沿着如图8所示的移动路径移动收集传感节点的数据时,MPOA算法计算Sink节点在每一个停留位置时每一个网格的单位节点能耗,累加每一个网格的12个单位节点能耗,获得单位节点能耗图(图9)。如图9所示,Sink节点移动路径内网格单位节点能耗基本相同,呈圆柱状分布。该能耗分布没有出现某个网络单位节点能耗异常突出的情况,可平衡网格单位节点能耗,从而提高了网络生存时间。

其次,以固定常数的移动路程或Sink节点的停留位置个数为例,分析另一参数对网络生存时间的影响。选择Sink节点的停留位置个数为12和3.1节中仿真参数,计算网络生存时间,获得仿真结果(图10)。如图10所示,当移动路程为100 m,200 m和300 m时,不管r的取值,其网络生存时间随着移动路程的增加而增加。当移动路程为400 m时,与移动路程为300 m的网络生存时间比较,除了r=40 m时,其他网络生存时间增加。当移动路程为500 m和600 m时,与移动路程为400 m的网络生存时间比较,r=10 m,20 m和40 m时的网络生存时间略微增加,r=30 m时的网络生存时间略微减少,r=50 m时的网络生存时间起伏,即其网络生存时间在某一个参数值间起伏变化。总之,当移动路程较少时,其网络生存时间随着移动路程的增加而增加。当移动路程大于阈值时,随着r的增加,其网络生存时间在某一个值上下起伏。这是因为,当移动路程较少时,Sink节点靠近监测区域的中心位置移动,限制了Sink节点移动的优势,当移动路程增加时,扩大了其移动范围,较好平衡网格单位节点能耗,因此提高了网络生存时间。当移动路程达到一个阈值后,随着移动路程的增加,Sink节点的停留位置有可能出现在监测区域的边界和4个顶点周围,这提高了网格单位节点能耗,降低了网络生存时间。因此合理的移动路程可较好提高网络生存时间。

图10 移动路程对网络生存时间的影响

图11 Sink节点的停留位置个数对网络生存时间的影响

选择移动路程400 m和3.1节中仿真参数,获得仿真结果图(图11)。如图11所示,当Sink节点的停留位置个数为4,8和12时,不管r的取值,随着停留位置个数的增加,网络生存时间增加。当Sink节点的停留位置个数为16和20时,其网络生存时间与Sink节点的停留位置个数12时的网络生存时间相差不大。这是因为,停留位置个数过少,平衡网络能耗的效果不理想,当停留位置个数达到一定的值后,其移动路径范围内的网格单位节点能耗基本相同,停留位置个数的增加反而略微提高或降低了网格的单位节点能耗,因此合理数量的停留位置个数可较好平衡网格单位节点能耗,提高网络生存时间。

最后,比较Circle[14],Rect,Rand和MPOA算法的网络生存时间。其中,Circle是以监测区域中心位置为圆心,周长为移动路程Lenth(P)的圆。Rect是以监测区域中心位置为中心点,周长为Lenth(P)的正方形。Rand是40个随机路径的网络生存时间平均值。根据上述分析,选择移动路程400 m和Sink节点的停留位置个数12,获得仿真结果图(图12)。如图12所示,MPOA算法的网络生存时间最优。当r值为10 m,20 m和30 m值,MPOA算法的网络生存时间略微大于Circle、Rect和Rand算法。当r值为40 m和50 m时,MPOA算法的网络生存时间明显提高,远大于其他算法。这是因为,当r值较少时,MPOA算法的最优移动路径类似圆,其网络生存时间略大于Circle算法,当r值较大时,多数网格到Sink节点的跳数是1～2跳,此时Circle和Rect算法中,周长为400 m的移动路径上部分停留位置到监测区域的边界小于r,此停留位置不能较好平衡网络能耗。Rand算法基本不考虑r值的变化,其移动路径较差。MPOA算法可根据r值自动寻找到最优路径,因此MPOA算法的网络生存时间大于Circle、Rect和Rand算法。

图12 网络生存时间比较图

4 总结

考虑均匀分布的传感节点和Sink节点的多跳数据收集,提出一种无线传感网的Sink节点移动路径规划算法。首先,该算法将Sink节点的数据收集范围分解成多个圆环和内圆,将监测区域分解成多个网格。其次,考虑Sink节点在某一个位置上停留,采用数学公式表示每一个网格的单位节点能耗,从而获得Sink节点移动下的网络生存时间优化模型。接着,采用混合粒子群算法求解该优化模型,获得网络生存时间最优值和其移动路径。最后给出算法的仿真参数,仿真说明MPOA算法的有效性,Sink节点的移动路程和停留位置个数对网格生存时间的影响,仿真比较Circle,Rect,Rand和MPOA算法的网络生存时间。

总之,当传感节点均匀分布时,MPOA算法只需要根据监测区域的形状,可寻找到Sink节点的最优移动路径,从而平衡网络能耗,提高网络生存时间。但是MPOA算法只是考虑传感节点均匀分布的情况,没有考虑传感节点存在空洞、泊松分布等非均匀分布情况,因此下一阶段目标是考虑传感节点存在空洞、泊松分布等非均匀分布情况,研究Sink节点移动的网络生存时间优化模型和Sink节点的最优移动路径。

[1] Zhu C S,Shu L,Hara T,et al. A Survey on Communication and Data Management Issues in Mobile Sensor Networks[J]. Wireless Communications and Mobile Computing,2014,14(1):19-36.

[2] 高洁,吴延红,白建侠,等. 无线传感器网络最小覆盖能量优化算法[J]. 传感技术学报,2016,29(9):1435-1440.

[3] Tunca C,Isik S,Donmez M Y,et al. Distributed Mobile Sink Routing for Wireless Sensor Networks:A Survey[J]. IEEE Communications Surveys and Tutorials,2014,16(2):877-897.

[4] Wichmann A,Korkmaz T. Smooth Path Construction and Ddjustment for Multiple Mobile Sinks in Wireless Sensor Networks[J]. Computer Communications,2015,72(72):93-106.

[5] Kumar A K,Sivalingam K M,Kumar A. On Reducing Delay in Mobile Data Collection Based Wireless Sensor Networks[J]. Wireless Network,2013,19(3):285-299.

[6] 王章权,陈友荣,尉理哲,等. 优化网络生存时间的Sink节点移动路径选择算法[J]. 传感技术学报,2014,27(3):80-87.

[7] Tashtarian F,Moghaddam M H Y,Sohraby K,et al. ODT:Optimal Deadline-Based Trajectory for Mobile Sinks in WSN:A Decision Tree and Dynamic Programming Approach[J]. Computer Networks,2015,77(2):128-143.

[8] Ghosh N,Banerjee I. An Energy-Efficient Path Determination Strategy for Mobile Data Collectors in Wireless Sensor Network[J]. Computers and Electrical Engineering,2015,48(10):417-435.

[9] 郜帅,张宏科. 时延受限传感器网络移动Sink路径选择方法研究[J]. 电子学报,2011,39(4):742-747.

[10] 郭剑,孙力娟,许文君,等. 基于移动Sink的无线传感器网络数据采集方案[J]. 通信学报,2012,33(9):176-184.

[11] 汪林云,刘文军. 无线传感器网络中带有移动汇点的能量高效的数据收集协议[J]. 传感技术学报,2012,25(5):678-682.

[12] 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.

[13] Lee K,Kim Y H,Kim H J,et al. A Myopic Mobile Sink Migration Strategy for Maximizing Lifetime of Wireless Sensor Networks[J]. Wireless Networks,2014,20(2):303-318.

[14] Huang R,Gergely V Z. Static Path Planning for Mobile Beacons to Localize Sensor Networks[C]//Proceedings of the Fifth Annual IEEE International Conference on Pervasive Computing and Communications Workshops. 2007:323-330.

StudyontheMovementPathOptimizationAlgorithmofSinkNodeforWirelessSensorNetworks*

CHENYourong1,2*,LUSiyi2,RENTiaojuan1,2,YANGHaibo1

(1.College of Information Science and Technology,Zhejiang Shuren University,Hangzhou 310015,China;2.School of Information Science and Engineering,Changzhou University,Changzhou Jiangsu 213164,China)

To find the optimal movement path of Sink node and maximum network lifetime when sensor nodes were uniformly distributed,movement path optimization algorithm(MPOA)of Sink node for mobile sensor networks was proposed. In the MPOA algorithm,data collection range of Sink node was divided into multiple rings,and the monitoring area was divided into multiple grids. According to positions of Sink node and multi-hop communication,unit node energy consumption of each grid was expressed by mathematical formula,and network lifetime optimization model with mobile Sink node was obtained. Modified hybrid particle swarm optimization algorithm was adopted to solve the optimization model. Optimal scheme of network lifetime,sojourn positions and movement path of Sink node was obtained. Simulation results show that MPOA algorithm can find the optimal movement path of Sink node,balance network energy consumption and prolong network lifetime. Under certain conditions,MPOA algorithm outperforms Circle,Rect and Rand algorithms.

mobile sensor networks;mobile Sink node;path optimization;particle swarm optimization

10.3969/j.issn.1004-1699.2017.12.025

项目来源:国家自然科学基金项目(61501403);浙江省自然科学基金项目(LY15F030004);浙江省公益性技术应用研究计划项目(2016C33038,LGF18F010005);浙江省重大科技专项计划项目(2015C01033)

2017-04-29修改日期2017-08-09

TP393

A

1004-1699(2017)12-1933-08

陈友荣(1982-),男,博士,浙江苍南人,浙江树人大学信息科技学院副教授,常州大学信息科学与工程学院硕士生导师,主要研究方向为无线传感网、物联网。