1、 实 验 技 术 与 管 理 第 40 卷 第 2 期 2023 年 2 月 Experimental Technology and Management Vol.40 No.2 Feb.2023 收稿日期:2022-09-05 基金项目:南京交通职业技术学院重大课题（JZ210）；江苏省教育规划重点课题(K-b/2021/04)作者简介:吴昊（1973），男，江苏泰州，硕士，教授，研究方向为智能交通、计算机网络，fuisf_。引文格式:吴昊，张延年，柴永生.无线传感网络中一种移动信宿的路径规划算法J.实验技术与管理,2023,40(2):103-108.Cite this article:W
2、U H,ZHANG Y N,CHAI Y S.Path planning algorithm of mobile sink in wireless sensor networksJ.Experimental Technology and Management,2023,40(2):103-108.(in Chinese)ISSN 1002-4956 CN11-2034/T DOI:10.16791/ki.sjg.2023.02.017 无线传感网络中一种移动信宿的路径规划算法 吴 昊1，张延年1，柴永生2（1.南京交通职业技术学院 电子信息工程学院，江苏 南京 211188；2.江苏省教育考试
3、院，江苏 南京 210024）摘 要：采用移动信宿（mobile sink，MS）的无线传感网络（wireless sensor networks，WSNs）比静态信宿具有更好的数据收集性能，但是规划 MS 移动路径是一项挑战工作。为此，该文提出基于遍历点优化的移动信宿路径规划算法（path of mobile sink planning algorithm based on ergodic point，PSEP）。PSEP 算法依据节点位置、通信重叠区和可获取的数据量，将覆盖区划分多个面区，再从这些面区中寻找 MS 遍历点；获取这些遍历点后，再利用行商问题（travelling salesm
4、an problem，TSP）算法规划 MS 的路径。仿真结果表明，提出的 PSEP 算法提高了吞吐量，降低了数据收集时延。关键词：无线传感网络；移动信宿；遍历点；通信重叠区；行商问题 中图分类号：TP393 文献标识码：A 文章编号：1002-4956(2023)02-0103-06 Path planning algorithm of mobile sink in wireless sensor networks WU Hao1,ZHANG Yannian1,CHAI Yongsheng2(1.College of Electronic and Information Engineerin
5、g,Nanjing Vocational Institute of Transport Technology,Nanjing 211188,China;2.Jiangsu Education Examination Institute,Nanjing 210024,China)Abstract:Wireless sensor networks(WSNs)with mobile sink(MS)have better data collection performance than static sink.However,to plan path of MS is a challenge.The
6、refore,path of mobile sink planning algorithm based on ergodic point(PSEP)algorithm is proposed in this paper.In PSEP,the communication disks of the sensors divide the sensing field into faces by considering the sensors position,their communication overlaps and their data availability.The sets of MS
7、 ergodic points are selected from faces.The travelling salesman problem is used to get the path of MS by ordering the ergodic points.Simulation results show that the proposed PSEP algorithm outperforms existing works in terms of throughput,and data gathering delay.Key words:wireless sensor networks;
8、mobile sink;ergodic point;communication overlap;travelling salesman problem 随着对数据收集需求的加强，无线传感网络（wireless sensor networks，WSNs）1-2已广泛应用于多个领域，如康复医疗、智慧农业。WSNs 由多个微型传感节点组成，这些节点具有感测数据、处理数据和通信能力，其感测邻近环境数据，并将感测的数据传输至信宿。因此，收集数据是基于 WSNs 应用的关键。目前有两种收集数据方案：静态信宿和移动信宿（mobile sink，MS）。在静态信宿方案中，信宿固定于某特定位置。由于信宿不移动，
9、网络内节点需要通过多跳方式向信宿传输数据。在移动信宿方案中，信宿以特定路径或随机方式移动。当信宿移动至节点通信范围内，节点就直接向信宿传输数据3-4。相比于移动信宿的数据收集方案，静态信宿的数据收集方案可能会导致节点的能量消耗不均衡5-6。而移动信宿的数据收集方案平衡了网络内节点的能耗。104 实 验 技 术 与 管 理 然而，如何规划信宿的移动路径是一项挑战性工作7-8。合理规划 MS 路径，可使 MS 遍历到每个节点通信区域，并在该区域内某点位置收集该区域内的数据，进而提高了数据收集效率。将此点称为遍历点，如图 1所示。因此，MS 只需遍历这些遍历点，就可完成数据收集任务，MS 路径是由遍
10、历点构成。接下来，需要解决的问题是，采用何种顺序沿着遍历点移动，即路径规划问题。图 1 移动信宿收集数据示例 目前，研究人员对移动信宿路径的规划问题进行了大量研究。文献9提出基于蚁群优化算法（ant colony optimization，ACO）的信宿路径规划算法，其利用ACO 算法优化信宿路径。而文献10提出基于权重观察点的规划算法，通过选择最优的遍历点构建信宿的移动路径。类似地，文献11也提出基于粒子群的驻留 点 选 择 算 法（particle swarm optimization-based rendezvous point selection，PSO-RPS）。PSO-RPS 利用
11、PSO 规划路径，其依据数据时延和信息速率两项信息选择驻留点，再通过驻留点构成信宿移动路径。文献12提出基于遗传算法的移动 Sink 数据采集算法（genetic algorithm based on mobile sink data collecting,GMSDC）。GMSDC 算法利用遗传算法选择驻留点，再利用驻留点构建 MS 移动路径。但是 GMSDC 算法旨在缩短路径长度，并以最小化路径长度为目标函数。上述算法并没有在考虑到路径长度同时，最小化收集数据时延。为此，本文提出基于遍历点优化的移动信宿路径规划算法（path of mobile sink planning algorithm
12、 based on ergodic point，PSEP）。PSEP 算法充分考虑了节点通信区的覆盖重叠问题，并依据节点重叠区，将网络覆盖区划分为多个面区，再从面区中寻找 MS 遍历点。在寻找遍历点时，不仅考虑 MS 能收集每个节点的数据的约束条件，还考虑了收集的数据量。利用行商问题（travelling salesman problem，TSP）求解规划 MS 的路径，性能分析表明，提出的PSEP 算法提升了数据收集量，缩短了数据收集时延。1 系统模型 1.1 网络模型 在12ll的监测区域部署 n 个静态节点（以下简称为节点）和一个移动信宿。用12,nSs ss=表示 n个静态节点集。当
13、MS 移动至节点的通信范围内，节点就以固定速度率直接向 MS 传输数据。节点的通信区域为圆形，用rC表示 MS 和节点的通信半径。考虑到衰减以及噪声干扰，一个数据包可能需要经过重传才能传输至 MS。因此，引用变量表示传输数据包的成功率。此外，MS 知晓所有节点的位置，并且 MS 具有足够传输功率和存储数据容量。1.2 能量消耗模型 由于节点传输数据消耗了节点大部分能量，本文只考虑了节点在传输数据时所消耗的能量。令MDD()is表示节点is依据现有电量能够传输的数据量，其定义如式（1）所示：tREMDD()min DA,iiise=（1）式中：REi和DAi分别表示节点isS的剩余能量、所感测的
14、数据量；te表示传输单比特数据时所消耗的能量。依式（1）可知，MDD()is取tDA,RE/iie两者间的最小值。此外，t12reC=+，其中1、2分别表示传输电路、放大电路的功放因素；为路径衰减指数。因此，节点is传输MDD()is所消耗的能量为：()iE s=tMDD()ise。网络内中有 n 个节点，MS 收集这 n 个节点的感测数据所消耗的能量为Total1=()niiEE s=。将收集这 n 个节点的感测数据为一轮，则 MS 在每轮内消耗的能量为TotalE。2 PSEP 算法 2.1 重叠面区和孤立面区 将由 n 个节点覆盖的区域划分多个面区，这些面区是由节点通信区域交错形成，如图
15、 2 所示，图中有6 个节点，分别表示为012345,ss ssss，它们覆盖区域形成为 12 个面区,1,2,12if i=。从图 2 可知，这些面区可能由一个节点通信区域覆盖，也可能由 2 个或 者3个 节 点 通 信 区 域 覆 盖。例 如，面 区35681011,ffffff均由一个节点通信区域覆盖，它们分别为节点210345,ss ssss。吴 昊，等：无线传感网络中一种移动信宿的路径规划算法 105 图 2 面区划分示例 而面区012479,ffffff是由2个或3个节点通信区域覆盖。例如，面区1f是由节点2s、节点1s和节点0s3个通信区域共同覆盖。因此，引入重叠面区概念：将由2
16、个或多个节点通信区域共同覆盖的面区称为重叠面区。012479,ffffff就重叠面区。此外，注意到面区11f，其只由节点5s的通信区域覆盖，但是节点5s没有邻居节点。将此类面区称为孤立面区。2.2 候选面区的构建 PSEP 算法先构建候选面区，再从中筛选出最优的面区，并在这些面区中找出最优的遍历点。最后，利用这些遍历点，并结合 TSP13规划 MS 移动路径。2.2.1 通信区重叠的节点集和面区重叠节点集 通信区重叠的节点集：若节点is与其邻居节点的通信区发生重叠，则节点is和这些邻居节点构成通信区重叠的节点集CO()is。CO()()iiissN s=，其中()iN s表示与节点is通信区重叠的邻居节点集。如图 2 所示，节点0s和1s的邻居节点集分别为0123(),N ss ss=和102(s)(,)Nss=。节点0s和1s的通信 区 重 叠 的 节 点 集 分 别 为00123CO(),sss ss=和1012CO(),sss s=。面区重叠节点集：一个面区可能由 2 个或以上节点通信区共同覆盖。给定面区if，通信区覆盖此面区的节点构成面区重叠节点集CCG()if。以图 2 为例
