无人机辅助物联网传感器网络飞行路径优化

⃝=⃝可在www.sciencedirect.com在线获取ScienceDirectICT Express 2（2016）140www.elsevier.com/locate/icte无人机辅助物联网传感器网络飞行路径优化Sang-Jo YooYu，Jae-hyun Park，Su-hee Kim，Anish Shrestha韩国仁川仁荷大学信息通信工程系接收日期：2016年7月28日;接受日期：2016年2016年8月24日在线发布摘要在本文中，我们提出了一个最佳的飞行路径无人机辅助物联网传感器网络使用位置感知的多层信息地图，考虑不同的效用函数的基础上的传感器密度，能量消耗，飞行时间，飞行风险水平。利用遗传算法实现多目标效用函数的加权和最大化。仿真结果表明，在满足约束条件的前提下，通过调整权值可以得到最优解点。c2016韩国通信信息科学研究所。出版社：Elsevier B.V. 这是一篇基于CC BY-NC-ND许可证的开放获取文章（http：//creativecommons.org/licenses/by-nc-nd/4. 0/）。关键词：无人机;最优航迹;效用函数;遗传算法1. 介绍连接几乎所有事物的愿景已经导致了被称为物联网（IoT）的新范例的概念，其中整个周围环境（如环境、建筑物和景观）可以由传感器密切监测。物联网传感器网络可以应用于民用和军事行动，如搜索和破坏/救援，智能运输，野火监测，灾害管理，边境安全等。物联网传感器网络需要在巨大的空间上部署大量的传感器，包括远程区域和人类无法访问的区域。在这种情况下，收集传感器数据成为一项艰巨的任务。无人驾驶飞行器（UAV）已经成为解决这些问题的一个务实的解决方案。无人机是一种非常快速地收集传感数据的手段， 成本效益的方法[1]。它补充了现有的技术，适合卫星和地面方法之间。然而，从基于物联网的传感器网络中的每个传感器收集数据是困难的，因为它生成大量的感测数据*通讯作者。电子邮件地址：sjyoo@inha.ac.kr（S.- J. Yoo），parkjh8547@naver.com（J.-H. Park），katrina429@naver.com（S.- H.Kim），apshrestha@inha.ac.kr（A. Shrestha）。同行评审由韩国通信信息科学研究所负责。本文是题为《互联网中的ICT融合》特刊的一部分。由Yacine Ghamri-Doubang，Yeong Min Jang，Daeye-Kim，HossamHassanein和JaeSeung Song客座编辑。并且要求UAV遵循长的路线，导致高能量消耗、较长的延迟和暴露于危险环境。因此，本文重点研究了无人机辅助物联网传感器网络中的飞行路径优化问题。本文利用位置相关多层信息地图，设计了基于传感器密度、能量、飞行时间和风险的多效用函数，以寻找无人机的最优航路。在预先定义的最大延迟和能量以及禁止区域的约束下，使用遗传算法（GA）的多目标效用函数的总体加权和最大化本文的其余部分组织如下。在第2节中，我们对拟议的计划进行了详细解释。性能评价见第3节。最后，在第4节中得出结论。2. 建议计划2.1. 系统模型我们考虑J种类型的传感器，每个具有不同的感测值，以随机或确定性的方式部署在区域（R）内，该区域被划分为N个小单元（Ci），使得i 1，2，. . .、N.每个单元的传感器密度也被认为是不同的。这些小区被分类为禁止小区、飞行小区和感测信息收集（SIG）小区。无人机不得进入禁飞区（CP）。它停留在SIG单元（Cs）中以收集数据，并在飞行单元（Cf）上方飞行以遵循定义的路径。http://dx.doi.org/10.1016/j.icte.2016.08.0052405-9595/c2016韩国通信信息科学研究所。Elsevier B. V.的出版服务。这是CC BY-NC-ND许可证下的开放获取文章（http：//creativecommons.org/licenses/by-nc-nd/4. 0/）。S.- J. Yoo等人/ICT Express 2（2016）140141我我我F−F我i、jJ我我FFFFF12Nf（ k）i、j2我2Jv我我我Nf（k）k11k−1一个完整的飞行路径由一组SIG单元和飞行单元组成。SIG小区的集合被表示为因为每个小区具有不同的无线信道条件。因此，对于一个多媒体应用程序，所需的分组传输次数是Ssense={Cs，Cs，. . . ，C s}，（1）错误的数据包传输可以写为1 2Nsp1其中，CS是第i个SIG信元，Ns是SIG信元的数量。类似地，飞行单元的集合包括飞行单元的若干子集，并且被表示为Sfly=S1 ， S2 ， ...， SNs ， SNs+1 ，（2）Ni=1−pe，（7）其中Pe是小区i中的分组错误概率。此外，对于每个单元i，在给定时间单元期间的飞行风险被定义为ri。我们假设所有需要的信息都是可用的以多层信息地图的形式。其中，Sk是位于第（k-1）个SIG单元到第k个SIG单元之间的飞行单元的集合，其可以表示为Sk=<$Cf （ k ） ， Cf （ k ） ， . . . ， Cf （ k ）≠.（三）2.3. 飞行单元路由连续SIG信元之间的飞行信元路由根据使用“A星“的最短路径来确定。算法用于计算最短集合Sk的基数 表示为 Nf（ k）个细胞，路径确定为Cf（k）=Cs，Cf（k）=Cs. C f（1）是起始单元格。f（ i）=g（ i）+h（ i）（8）其中g（ i）是从起始小区到2.2. 能量模型能量主要用于三种活动，即通信、飞行和感知。我们将发送和接收感测信息所需的能量称为通信能量。通信能量可以根据传感器的类型而不同为了简单起见，我们假设所有类型的传感器消耗相同的能量，用ec表示。另一方面，飞行能量依赖于位置。我们将单位时间内速度为v的飞行能量记为ef，小区i的飞行能量权重由Wf表示。每个单元的飞行能量权重可以基于单元的地形而不同。因此，从单元i到j的飞行能量（由ef表示）应该基于它们的位置来表示。它可以用Eq表示。（4）如果相邻单元水平地或垂直地定位，并且使用Eq.（5）如果相邻的细胞位于对角，如下所ef=1wf+1wfefdc，（4）任意小区i，并且h（ i）是从小区i到目的地的估计成本。A星算法由两个数组组成，称为封闭列表和开放列表数组。起始单元格保存在父单元格中，其相邻单元格（禁止的单元格除外）保存在打开列表中。开放列表中的每个单元格的启发式函数值使用Eq. （八）、最小值保存在封闭列表数组中。选定的单元格被声明为父单元格，其相邻单元格（关闭列表和禁止列表中的单元格除外）被添加到打开列表中。我们可以检查哪条路由更好，如果开放列表已经有任何邻居，则选择最佳路由如果前一个单元格的g（ i）值较小，则使用同一个这个过程一直持续到我们到达目的地。最后，使用父单元跟踪路线并选择最短路径。2.4. 效用函数在这一节中，我们定义了几个效用函数来表示多目标效用的加权和功能我们考虑四个主要参数来设计实用程序ef =0.01f+1fef2dc（五）功能，即感知、能量、时间和风险，i、 j2wi2wjv，定义如下。(1) 传感实用程序其中dc是两个单元之间的距离UAV必须在小区上方停留一定时间段，以便从SIG小区内的若干传感器收集感测信息。这样做所消耗的能量称为滞留能量。单元格i中的停留能量可以如下获得：es=esteNpnj，（6）j=1其中es是单元中单位时间的停留能量，nj是单元i中类型j传感器节点的数量，te是单个感测分组交换时间，并且Np是在单元i中成功传送感测分组所需的传输次数。此外，分组错误概率也在每个142S.- J. Yoo等人/ICT Express 2（2016）140简体中文 =U，（10）其中n i 是小区i中的类型j传感器节点的数量，vj是传感器类型j的信息值。整体U（9）第一个条件：小区i中的感测效用取决于传感器节点的数量及其对应的信息值，其可以被写为JSJJ我我j=1j传感效用函数可以表示为NSS S我i=1其中NS是SIG小区的总数。S.- J. Yoo等人/ICT Express 2（2016）140143+、KFU =−U ，（13）==+JU =−U。（十五）=JU =−U 。（二十六）=UFT。F（（1）thI+K我我我k=1KUCE= ec teNnKi，i+1i+1UFR.（阿勒特K我呆K(2) 能源公用事业作为 解释 在 的 先前 区段， 能量而如果单元（i1）位于对角线上，我们将其称为情况2。然后，飞行时间可以获得为：在三个不同的任务中消耗。因此，我们为每个任务定义相应的效用函数如下：a. 飞行能源公用事业来自第（k-1）个SIG单元的飞行能量效用tifj（k）=Dc案例1v二维c、案例2.v（十八）到第k个SIG信元的距离可以如下所示表示N（ k）−1UFE=efi，i+1（k）、（11）总飞行时间效用可以如下获得：N+1Kk=1i=1，<$Cif（k）<$ Sf其中N kb. 停留时间效用k-第i个SIG小区中的停留时间效用可以是SIG信元到第k个SIG信元，并且efi， i+1（一）飞行表示为J能量从Cif（k）单元到集合Sf的Cf1（k）单元。的UST= t eN pn j。（二十）=航线的总飞行效用可写为NsU FE= −U FE。（十二）J1总停留时间效用可以表示为NSB.驻留能源公用事业停留能量效用是UAV在收集给定小区处的感测数据时保持稳定所它可以作为Ns瑟瑟我i=1其中，USE是在以下条件下的停留能量效用函数第i个SIG信元，这与（6）相同。C. 通信能源公用事业第i个SIG小区处的通信能量效用由下式给出：J1最后，总时间效用可以通过加上（19）和（21）U TU FTU ST.（二十二）(4) 风险效用风险效用考虑了飞行中的无人机可能暴露于危险和不确定性。风险效用取决于飞行和停留单元格效用，如下所a. 飞行单元风险实用程序从一个单元到下一个单元的飞行单元风险效用由下式给出：f−1普吉我我我UF R=N（ k）tffi=1（k）1r（k）+F1名rf（k）， （二十三）j=1总体通信能量效用可以如下获得：NSC E C E我其中ri（k）是集合S f的Ci（k）单元的风险。的总的飞行单元风险效用由下式给出：NS+1Kk=1I1最后，总的能量效用可以通过将等式（12）、（13）和（15）作为b. 驻留单元格风险实用程序给出了第i个SIG小区中的停留小区风险效用通过U E=U FE+U SE+U CE。（十六）USR=rsteNpJ.J..（二十五）(3) Time实用程序无人机所花费的总时间取决于飞行和停留时间。因此，我们设计了两个独立的效用函数，定义如下。a. 飞行时间效用从一个单元到另一个单元的飞行时间效用可以表示为Nf（k）−1我我我总j=1单元格风险效用由下式给出：NSSR SR我I1总风险效用可以通过加上（21）（26）作为U R=U FR+ U SR。（二十七）√我U FT =−）是来自（UST= −UST。.（十四）2我2U FR=−F144S.- J. Yoo等人/ICT Express 2（2016）140KωsU+ωTU+ωRUUFT=fi，i+1（k）、（17）（5）总效用总效用函数最终可以由Fi=1f f每个效用函数的加权和为其中ti，i+1（k）是从Ci（k）到Ci+1（k）（k）F=sE T Rfi， i+1其中ω，ω，ω和ω是效用权重，根据单元格（i+1）的位置而不同。S E T R因此，将有两种情况。我们把细胞称为（i+1）与情况1相同，如果其水平或垂直地定位，传感、能量、时间和风险，使得0 <ωs≤1，且ωE+ωT+ωR= 1。集合Sk的单元格。应该指出，tf的值+（1−ωs）（ωEU），（二十八）S.- J. Yoo等人/ICT Express 2（2016）140145=−=-==-=图1.一、遗传算法在该方案中的实现流程图图二. 提出的染色体结构。2.5. 遗传算法图1中的流程图描绘了GA的实现，以最大化在等式1中制定的多目标函数（28）无人机最佳飞行路径[2我们考虑三个主要的限制。首先，总的端到端飞行时间不应超过阈值时间限制Tlimt。第二，无人机的总能量消耗不应大于最大能量限制Elimt。最后，无人机不应在禁飞区上空飞行。最初，候选解决方案的种群形式为 染色体的初始化。每条染色体由感受细胞和飞行细胞组成，如图所示。 二、飞行细胞的选择是以最短路径连接两个相应的SIG细胞。（28）基于所选择的染色体中的飞行和SIG细胞。利用轮盘赌选择方案，选择一些最好的染色体作为中间群体。‘Order 1 crossover’ is applied to ‘cell id’ with probability 通过以概率P m翻转每个后代的SIG指示值来具有较低适应值的先前种群的一部分被新的随机解替换重复该过程，直到不满足停止标准。3. 绩效评估我们使用GA的适应度函数来评估效用值的集合当它满足停止条件时，我们选择图三.在所提出的方案中，不同ω s值的总效用函数。见图4。比较所提出的方案中不同的效用函数。具有最大效用值的路由路径。该计划用MATLAB实现。模拟中使用的变量在表1中给出。图3显示了不同ωs值和ωe0。3，ωr0。4和ωt0. 3.我们可以观察到，总效用随着迭代次数的增加而增加，并在一定次数的迭代后饱和。增加感测效用的权重增加了总效用，但是UAV必须访问更多的SIG小区，这需要更长的时间和更多的能量。图图4显示了ωs0时的个体效用。5和0.7和ωe0。3，ωr0. 4，ωt0。3.据观察，如预期的那样，感测效用随着ωs的增加而提高。然而，ωs的增加降低了总重量，即，（1ωs），分配给其余的效用函数。ωs的增加降低了能量、时间和风险效用，从而增加了成本。可以通过调整相应的权重来提高特定的个体效用。4. 结论提出了一种基于遗传算法的无人机辅助物联网传感器网络飞行路径优化方案。在我们提出的方法中，传感器场的每个单元根据其环境特征（例如禁区）来表征，146S.- J. Yoo等人/ICT Express 2（2016）140×表1模拟参数。参数值地图尺寸10 10人口50迭代次数13084号染色体长度交叉率0.05突变率0.01禁区（3、1）、（8、1）、（10、1）、（5、2）、（10、2）、（7、5）、（8、5）、（9，5），（10，5），（2，7），（3，7），（4，7），（5，7），（3，8），（4，8），（5，8），（6，8）信道条件、传感器部署统计信息和风险级别。通过建立多目标效用函数，得到了飞行单元和SIG单元的最优路径。仿真结果表明，该方法能够在满足约束条件的情况下得到期望的最优路径。致谢这项研究得到了基础科学研究计划的支持，该计划由韩国科学，信息通信技术和未来规划部资助的韩国国家研究基金会（NRF-2014 R1 A2 A2 A01002013）资助。本研究 得 到 了 韩 国 科 学 、 信 息 通 信 技 术 和 未 来 规 划 部（MSIP）ITRC（信息技术研究中心）支持计划（IITP-2016-H8501-16-1019）的支持。由IITP（信息通信技术促进研究所）监督。引用[1] I. Bekmezci，O.K. Sahingoz，S. Temel，Flying Ad-HocNetworks（FANNAPOLIS）：a survey，Ad Hoc Netw. 11（3）（2013）1254-1270。[2] P. Guo，X. Wang，Y. Han，The enhanced genetic algorithms for theoptimization design，in：Proc. 国际会议生物医学工程 和信息学，2010年，pp. 2990-2994年。[3] W.A. Chang，R.S.李明，遗传算法求解最短路径问题的一种新方法。Comput. 6（6）（2002）566-579。[4] W.J. 徐圣熙好吧J.H.Ahn，S.康湾Moon，一种高效的硬件最短路径搜索引擎的A-star算法的架构，在：Proc. International JointConf. on INC，IMS and IDC，2009，pp. 1499 -1502年。