唐 玲，曹 莉，乐英高，熊鹏文

(1.四川理工学院 自动化与电子信息学院，四川 自贡 643000； 2. 南昌大学 信息工程学院，南昌 330031)



基于路径优化策略的物联网感知层数据收集研究*

唐 玲1，曹 莉1，乐英高1，熊鹏文2

(1.四川理工学院 自动化与电子信息学院，四川 自贡 643000； 2. 南昌大学 信息工程学院，南昌 330031)

针对物联网感知层移动无线传感器网络在数据收集过程中节点能量有限、能耗不均衡和存在不可靠性、时延较长等问题，经过数学推导和理论证明这是一个典型多目标优化问题。文章将优化目标规约为时延受限下的能耗最小化和可靠性最大化问题，提出基于改进萤火虫算法优化移动无线传感器网络移动Sink路径优化机制，该算法充分利用移动Sink的存储空间充裕、能量充足和计算能力强的优势，保证网络的连通性，提高网络通信效率。通过仿真对比分析，与随机移动方法、蚁群算法和粒子群算法对比，簇头节点能耗均衡性减少了40%、52%和56%，可靠性提高了13%、8%和7%，时延减低了92.9%、82.8%和56.4%，提出的算法均衡了节点能耗，满足网络服务质量，提高网络可靠性。

物联网；路径优化；萤火虫算法；可靠性

0 引言

近年来，物联网技术得到广泛研究者的关注和深入发展，在智能物流、智能医疗、工业5.0、智能工农业等领域得到快速地应用[1]。物联网感知层无线传感器网络数据感知收集技术是实现物联网各种功能的底层关键技术，受到专家学者的广泛重视[2-3]。由于随机部署、环境复杂、节点资源有限等情况下，单路径路由数据传输方式容易造成网络能耗的不均衡，采用移动Sink进行数据收集，可以极大地减少数据的多跳传输，同时缩短节点与移动Sink之间的传输距离，节省节点能量消耗，提高网络可靠性。Sink节点移动路径优化设计不仅考虑数据传输路径的长度，还要考虑节省能量和网络能量均衡等问题，考虑能耗、可靠性与延时之间存在折衷[4]。移动无线传感器网络路径优化是一个典型多目标优化问题。

针对上述问题，将优化目标规约为时延受限下的能耗最小化和可靠性最大化问题，提出改进萤火虫算法优化MWSN移动路径，以构建高抗毁性的网络拓扑，减少数据传输链路长度，均衡能量消耗，确保移动无线传感器网络的鲁棒性和可用性。

1 移动Sink路径优化问题研究

1.1 系统模型

物联网感知层移动无线传感器网络分簇数据收集过程中，我们考虑一个移动Sink情况下的数据收集场景如图1所示。在分簇场景中，将检测的区域进行层次划分。分为两层，底层主要由普通传感器节点组成，主要工作就是进行数据收集；上层主要由分簇的簇头节点组成，簇头的任务是负责收据汇集和分配任务。簇头对簇内成员节点进行任务分配，簇内成员节点对采集到的数据传送给簇头，簇头首先进行数据融合，当移动的Sink移动到簇头的通信范围后，再转发给移动的Sink[5]。

本文移动Sink的数据收集过程都是基于LEACH分簇基础上展开研究，簇头会根据数据收集轮询次数的变化分簇区间也实时变化。移动Sink不需知道普通节点所在位置，移动Sink只在意簇头节点收集的数据。

图1 基于移动Sink的数据收集分簇场景

1.2 路径优化问题描述

本文针对物联网感知层移动无线传感器网络中的移动Sink移动路径优化问题进行以下定义：

定义1：最小能耗移动路径。在物联网感知层移动无线传感器网络数据收集过程中，为了满足时延、能耗和网络可靠性等约束条件下，使得收集到的数据从分簇簇头节点传送到移动Sink节点的总能耗最小和总路径长度最短的Sink移动路径。

定义2：最短路径的移动路径 。定义为移动Sink对监测区域所有簇头节点进行数据收集的最短移动路径长度。

假定移动Sink在每次轮询工作进行数据收集过程中，移动Sink进行数据收集的初始位置为C0，移动Sink的运动速度为V，数据收集的总的最大时延为D，那么移动Sink的最大移动路径长度为L=V×D，如果假定J和Q=(qi)分别是簇头节点集合和对应的数量集合，N表示需要进行数据迁移的节点总的集合，根据前面描述的场景模型，对监测区域进行数据收集移动Sink的总的能耗为：

(1)

(2)

(3)

(4)

s.t.TSP(SV)≤L

(5)

2 改进萤火虫算法

2007年英国著名大学剑桥大学的X.S. Yang博士针对萤火虫的趋光性和寻找食物过程中的群体智能行为进行抽象，建立了萤火虫数据模型，提出了一种新的基于群体智能优化算法的元启发式智能算法—萤火虫算法(glowworm swarm optimization, GSO)[6-7]。该算法在旅行商问题、智能优化调度问题、复杂的组合优化等问题有着特别的优点，求解速度更快、耗时最少，在实际工程应用中也解决了许多复杂工程问题[8]。萤火虫算法主要由以下四个群体工作来完成寻找食物的过程，分别是萤火虫种群的初始化、荧光素更新、标记当前萤火虫位置和萤火虫决策域更新。

假定在萤火虫算法中，第i只萤火虫的初始位置为xi(k)和当前的荧光素值为li(k)，当前的函数目标值为f(xi(k))。初始时，萤火虫算法以目标优化函数作为决策范围的初始值，之后决策范围会随下面的计算公式(1)进行更新。

(6)

Mi(k)的计算方式具体由算式(7)来确定：

(7)

萤火虫算法中，萤火虫根据周围荧光素值l的大小来决定它的运动方向，在第k次迭代计算过程中，萤火虫向荧光值更高的方向运动的概率用pij(k)表示，其计算公式如式(8)所示：

(8)

萤火虫i搜索更高的荧光素值之后，运动到新的位置由式(9)计算得到：

(9)

式中，S表示当前萤火虫的运动步长。

(10)

其中,xgbest为全局最优的位置。

当萤火虫i在搜索食物过程中运动到新的位置后，根据式(11)对当前萤火虫的荧光值重新计算并更新：

li(k)=(1-λ)li(k-1)+ωf(xi(k))

(11)

式中，参数li(k)表示第k次的计算迭代过程中，萤火虫i当前对应的荧光素值；其中参数λ∈(0,1)，它具体表示荧光素的挥发系数；参数ω表示荧光素的更新速率，是个常量。

萤火虫算法在初期的搜索能力较弱，而在迭代后期算法解在最优解附近震荡，容易陷入局部最优。为了克服这些问题，对改算法进行改进，使它能避免陷入局部最优和较快的逼近最优解，从数学上证明和解决与优化问题相关的理论问题。提出改进萤火虫优化移动无线传感器网络移动路径优化算法，得到优化的动态拓扑结构，改善网络连通性，降低节点收发信息能，减少信息在网络中传输次数，避免网络拥塞，提高网络的吞吐量、可靠性、可扩展性和鲁棒性。

随着环境的变化，高校对内部审计的需求增加，内部审计在强化管理、防范风险、促进学校事业目标的实现上功不可没。然而，“重监督轻服务”、“重业务轻管理”现象依然存在，高校内部审计转型的研究和关注越来越多。

3 算法过程描述与过程分析

本文提出的改进GSO在移动无线传感器网络移动Sink数据收集路径规划应用中，主要分为4步，详细描述如下：

(1)针对监测区域中的传感器节点，它们组网采用经典LEACH[10]分层次分簇算法，根据节点通信能力和剩余能量挑选簇头，当簇头挑选完成以后，簇头只有自己所在区域中的节点数据信息(节点位置、簇成员节点数量和对应的剩余能量)，簇头之间的信息需经过簇头间的信息交流，从而得到整个网络的信息，同时簇头节点接受数据收集任务。

(2)对监测网络区域进行划分。通过簇头之间的数据交流之后，每个簇头保存自己周边簇头节点的信息，通过计算与周围簇头节点通信总的代价，以及在能耗和最短移动路径约束条件计算通信距离和通信能耗等，根据通信代价的大小进行网络分区，最后在每个分簇区域中确定一个停留位置，以保证数据收集的能耗均衡性。

(3)移动Sink在每个监测区域确定停留位置。移动Sink每到一个监测区间中的地方，就会向周边进行广播信息，簇头收到信息后将簇内汇总的信息发送给移动Sink，移动Sink将收集到的信息进行存储和记录，为下一轮进行数据收集进行服务。

(4)移动Sink的移动路径优化。Sink节点根据之前收集到的簇头数据信息(簇头剩余能量和位置坐标信息)，确定自己的停留点，之后采用本文提出的改进萤火虫算法对移动路径进行优化，主要包括了初始值编码、荧光素更新、位置更新、计算适应度值和最好的决策更新。群体智能算法萤火虫算法对移动Sink的初始位置要求不高，计算也较简单，从而使移动Sink数据收集最大化、能量消耗最小化和网络高可靠性的运行。

在萤火虫算法中，它的重点就是吸引度的计算，每个萤火虫的位置代表寻优函数的一个解，萤火虫的发光亮度取决于寻优函数，函数值越好，亮度越强。亮度弱的萤火虫会被亮度强的萤火虫吸引，向其移动。随着算法的迭代，萤火虫会不断向比自己更亮的萤火虫靠近，最终大多数萤火虫会聚集在最亮的位置附近，即找到最优解。改进GSO在移动Sink路径规划工作流程图如图2所示。

图2 改进GSO在移动Sink路径规划工作流程

4 算法仿真与结果分析

本文采用Matlab仿真软件对我们提出的物联网感知层移动无线传感器网络移动Sink路径优化研究。对仿真环境参数设置如下:在500×500m2方形监测区域中，移动Sink以5m/s的速度向监测区域所有簇头节点直线运动进行收集感知数据。本文将提出的算法与随机移动方法[11]、蚁群算法[12]和粒子群算法[13]对比，分别从死亡节点个数、簇头产生个数、网络传输时延、Sink接收数据包个数和网络可靠性等五个指标进行衡量算法性能。在本仿真环境中，传感器节点感知数据、接收数据和传送数据的能耗计算公式如下：

ES=l·εs

(12)

EN-R=l·εr

(13)

(14)

式(14)中，l为发送数据包数据长度，单位是bit，l=4000bit，控制包长度ctrPaclength=200bit，其它参数为εs=60×10-9J/bit，εr=135×10-9J/bit，Eelect=45×10-9J/bit，普通空间传输参数ξfs=10×10-12J/bit/m2，多径传输参数ξmp=0.0013×10-12J/bit/m4。数据传输阈值d0=87m，传感器节点初始能量E0=1J。仿真环境参数设置如表1所示。为了算法仿真的准确性，我们得到的仿真结果为平均运行100次的仿真结果。

表1 仿真环境参数设置

(1)死亡节点个数对比

网络中传感器节点个数随仿真时间轮询次数的变化，我们这里主要针对随着轮询次数的变化，对四种算法的网络中死亡节点个数进行对比，算法对比结果如图3所示。

图3 四种算法死亡节点个数对比

从图3可以看出，随着轮询次数的增加，四种算法的网络传感器节点的能耗逐渐增加，死亡节点的个数也随之上升，在20～150轮次时，死亡节点个数上升幅度较快，在150～300轮次时死亡节点个数上升缓慢，这里主要原因是节点个数总共300随着中间节点死亡节点个数较多，后面的节点数量较少，节点死亡个数达到一个暂时的平衡。从四种算法的网络死亡节点个数来看，随机移动算法的节点死亡个数最快也最多，蚁群ACO算法较多，粒子群PSO算法较少，我们提出的算法最少。

(2)簇头产生个数对比

簇头产生个数是反应网络总体能耗大小的重要参数之一，簇头节点个数相对越多，网络越均衡，网络的能耗也越少。四种算法的簇头产生个数对比如图4所示。

图4 四种算法簇头产生个数对比

从图4中可以看出，随着仿真时间的增加，四种算法的簇头产生个数都在逐渐降低，降低幅度都不大。但可以明显看出，本文提出算法的簇头节点个数比其它三种要多得多，以150轮询次数为例，本文提出算法的簇头数量为18，PSO算法的簇头数量为8，ACO算法的簇头数量为5，随机移动的簇头数量为4，以25个簇头节点个数最佳为例，分别比这三种算法提高了40%、52%和56%。

(3)网络传输时延对比

网络传输时延反映算法性能优越性的重要指标，提出的算法与另外三种算法的网络数据传输时延对比如图5所示。

图5 四种算法网络传输时延对比

从图5中，随着仿真轮数的增加，四种算法的网络传输时延都在增加，但四种算法的数据传输时延增长幅度区别较大，随机移动传输时延波动幅度在1～9s左右波动，ACO算法波动幅度在0.5～5s左右，PSO算法传输时延波动幅度在0.1～2s，本文提出的GSO算法的传输时延幅度在0.1～1s左右。明显可以看出，随机移动传输时延最大，平均时延为6.8s，ACO算法传输时延较大，为2.8s，PSO算法传输时延较小，为1.1s，本文提出的算法时延最小，为0.48s，比另外三种算法的传输时延降低了92.9%、82.8%和56.4%，完全满足农业无线传感器网络应用中的数据传输时间的要求。

(4)Sink接收数据包个数对比

Sink接收数据包个数反应物联网感知层移动无线传感器网络数据收集多少的具体体现，是数据收集过程中一个重要参数，接收的数据包越多，说明算法的性能更优越。四种算法的Sink接收数据包个数对比如图6所示。

图6 四种算法Sink接收数据包个数对比

图6反映4种算法的Sink接收数据包个数对比，从图6中看出，随着仿真轮询次数的增加，随机移动、ACO算法和PSO算法的接收数据包数量相差不多，它们接收的数据包个数大约在2.5×104个，变化曲线也相差不大。其中的ACO算法和PSO算法的接收数据包数量更是相近，而本文提出的算法的数据包接收数量最多，数量在3.7×104个左右，远远超过其它三种算法，提高了超过50%以上。

(5)网络可靠性对比

网络可靠性是反应物联网感知层移动无线传感器网络数据收集的重要指标，是衡量提出算法性能的一项重要参数。网络的可靠性越高，说明网络工作越正常，收集到的数据也越可靠，四种算法的网络可靠性对比如图7所示。

图7 四种算法网络可靠性对比

同样地，随着网络轮询次数的增加，四种算法的网络可靠性随之下降，这个主要是因为网络的传感节点能量逐渐耗尽，网络的数据通信能量下降，网络的丢包率逐渐增加，导致网络可靠性逐渐下降。明显可以看出，四种算法的网络可靠性差别也较大，其中随机移动的可靠性最低，ACO算法和PSO算法的可靠性相差无几，本文提出的算法可靠性最好。以200轮次为例，随机移动的可靠性为0.52，ACO算法和PSO算法的可靠性为0.58，本文提出的算法的可靠性为0.65，比其它三种算法的可靠性分别提高13%、8%和7%。

5 结束语

移动无线传感器网络是物联网感知层目前比较热门的研究领域，还有许多关键问题亟需解决，其中本文研究的移动Sink的路径优化问题是其中一个热门研究问题，也是物联网感知层中的一个关键问题。本文针对物联网感知层移动无线传感器网络在数据收集过程中节点能量有限、能耗不均衡和存在不可靠性、时延较长等问题，提出一种新的基于改进萤火虫算法优化移动无线传感器网络移动Sink路径优化机制，保证网络的连通性，提高网络通信效率，均衡了节点能耗、解决传输过程中的容错性，满足网络服务质量，提高网络可靠性。本文的研究虽然提高了网络的性能，但存在网络的计算复杂度较高，网络的传输时延还是较大，接下来的工作是如何降低网络的计算复杂度和进一步降低网络的传输时延。

[1] Gubbi J, Buyya R, Marusic S, et al. Internet of Things (IoT): A vision, architectural elements, and future directions[J]. Future Generation Computer Systems, 2013, 29(7): 1645-1660.

[2] 梁小晓, 曹莉, 韦崇岗,等. 物联网感知层传感节点故障诊断研究[J]. 组合机床与自动化加工技术, 2015 (3): 62-66.

[3] Miorandi D, Sicari S, De Pellegrini F, et al. Internet of things: Vision, applications and research challenges[J]. Ad Hoc Networks, 2012,10(7): 1497-1516.

[4] Yue Y, Li J, Fan H, et al. Optimization-Based Artificial Bee Colony Algorithm for Data Collection in Large-Scale Mobile Wireless Sensor Networks[J]. Journal of Sensors, 2016(4):1-12.

[5] 张希伟, 戴海鹏, 徐力杰, 等. 无线传感器网络中移动协助的数据收集策略[J]. 软件学报, 2013, 24(2): 198-214.

[6] Krishnanand K N, Ghose D. Glowworm swarm optimization for simultaneous capture of multiple local optima of multimodal functions[J]. Swarm intelligence, 2009, 3(2): 87-124.

[7] Liao W H, Kao Y, Li Y S. A sensor deployment approach using glowworm swarm optimization algorithm in wireless sensor networks[J]. Expert Systems with Applications, 2011,38(10): 12180-12188.

[8] 曾冰, 李明富, 张翼. 基于改进萤火虫算法的装配序列规划方法[J]. 计算机集成制造系统, 2014, 20(4): 799-806.

[9] 陈海东, 庄平, 夏建矿,等. 基于改进萤火虫算法的分布式电源优化配置[J]. 电力系统保护与控制, 2016,44 (1): 149-154.

[10] 陈晓娟, 王卓, 吴洁. 一种基于 LEACH 的改进 WSN 路由算法[J]. 传感技术学报, 2013,26(1): 116-121.

[11] 王方, 胡彧. 基于移动机器人的无线传感器网络数据收集方法[J]. 工矿自动化, 2013 (1): 91-95.

[12] 童孟军, 关华丞. 基于蚁群算法的能量均衡多路径路由算法的研究[J]. 传感技术学报, 2013, 26(3): 425-434.

[13] 彭大志, 王艳. 基于混合粒子群算法的无线传感器网络路由协议[J]. 测控技术, 2014, 33(7): 93-97.

(编辑 李秀敏)

Optimizing Path Selection for Data Collection of the Perception Layer of Internet of Things

TANG Ling1, CAO Li1, YUE Ying-gao1, XIONG Peng-wen2

(1. School of Automation and Electronic Information, Sichuan University of Science and Engineering，Zigong Sichuan 643000,China;2. School of Information Engineering, Nanchang University, Nanchang 330031,Chian)

In the process of data collection of the perception layer of the Internet of things, there are many problems, such as limited energy, unbalanced energy consumption, unreliability, and long delay, etc. It is proved that it is a typical multi-objective optimization problem through mathematical derivation and theory. In this paper, the problem of minimizing the energy consumption and maximizing the reliability under the delay-constrained optimization is proposed. The optimization of the mobile Sink path in the mobile wireless sensor network is proposed based on the improved firefly algorithm. The proposed algorithm makes full use of the advantages of abundant storage space of mobile Sink, abundant energy and computing power, which can ensure the connectivity of the network and improve the efficiency of network communication. Through simulation and comparative analysis, compared with the random migration method, ant colony algorithm and particle swarm optimization algorithm, the energy balance of cluster head nodes is reduced by 40%, 52% and 56%, the reliability is increased by 13%, 8% and 7%, the latency is reduced by 92.9%, 82.8% and 56.4%, respectively, the proposed algorithm balances the node energy consumption, satisfies the network service quality and improves the network reliability.

internet of things; path optimization; glowworm swarm optimization; reliability

1001-2265(2017)07-0137-05

10.13462/j.cnki.mmtamt.2017.07.033

2016-10-19；

2016-11-24

国家自然科学基金(61663027)；企业信息化与物联网测控技术四川省高校重点实验室项目(2014WYJ04)

唐玲(1976—)，女，四川富顺县人,四川理工学院副教授，硕士，研究方向为智能信息处理、物联网、电气工程方面研究，(E-mail)tara _hq@sina.com。

TH166;TG506

A