摘要
近年来，物联网相关技术飞速发展，物联网也被广泛应用于环境监测，智慧城市，目标跟踪等多个场景中。在物联网应用场景中，如何高效收集物联网设备的数据一直是研究的热点问题。在网络规模较大的物联网中，通常需要部署大量用以监测并转发数据的物联网设备，而这会带来昂贵的部署成本。并且，如果在极端环境（如：发生自然灾害的区域，火山等）中部署的物联网设备来获取周围环境的信息，收集设备获取的信息是极其困难的。利用低成本，高移动便捷性的无人机（UnmannedAerialVehicles,UAVs），物联网设备的数据采集工作可以由无人机直接飞往各物联网设备的位置完成，而这将大大减少用以转发数据而需要的物联网设备数量，能在一定程度上降低物联网设备部署的成本。同时，地面上的无线通讯信号会因为各种障碍物而发生散射，进而导致信号的迅速衰减。而位于空中的无人机拥有广阔的无线通讯范围，避免了此类无线信号衰减过快的问题。 在传统物联网数据收集的研究中，通常使用部署一个或多个移动基站的方式。移动基站可以直接移动到各个物联网设备的位置进行数据收集，这也能减少用以转发数据的物联网设备的数量，从而节约部署成本。但移动基站难以跨越河流，悬崖等障碍，同时不利于极端环境下的工作。于此同时，移动基站运行于地面上，移动基站和物联网设备之间的无线信号会因障碍物而发生散射，造成信号衰减迅速。也有部分文献研究部署一个或者多个无人机进行物联网网络的数据收集，但是这些文献的目标在于最小化能耗，最大化数据收集量，最小化无人机飞行距离等方面，而关于最小化无人机数量的研究非常少。最小化无人机数量的问题类似于最小圈覆盖问题，而目前的最小圈覆盖问题的研究中提出算法的近似比还能进一步提升，即在同样的条件下还可以部署更少数量的无人机。最小化无人机数量的问题也类似于现有部分文献中研究的有邻域旅行商问题（TravellingSalesmanProblemwithNeighborhoods,TSPN），但这些文献优化的目标是最小化无人机的飞行距离。 与现有的研究不同，本文考虑了一个使用最少数量的无人机并且找到它们数据收集路径的问题。本文关注的重点在于最小化无人机的数量，而不是最小化无人机的飞行距离。为了确保所收集数据的低延迟性，文中给研究的问题设定了一个严格的要求，即每个无人机飞行所花费的总时间（包括无人机飞行时间和无人机数据收集时间）必须不大于给定的最大数据收集延迟，例如：20分钟。否则，收集到的数据就会失去时效性，例如：用以监测森林火灾隐患和PM2.5含量的物联网应用中，延迟的数据往往不利于的灾害防治。考虑了实际应用场景的需求，本文研究了无邻域和有邻域两种情况下的无人机最小数量部署问题。其中，无邻域的情况针对物联网设备数据传输范围较短的应用，要求无人机需要飞到每个物联网设备的位置才能收集数据。有邻域的情况针对物联网设备数据传输范围较长的应用，即只要无人机和物联网设备的欧氏距离不大于给定的无线传输范围，无人机就可以收集数据。本文针对无邻域和有邻域两种情况下的物联网网络进行了建模，提出了无邻域和有邻域两种情况下的无人机最小数量部署问题，并证明了该问题是NP-hard问题，无法在多项式时间内找到最优解。对于无邻域无人机最小数量部署问题，本文提出了一种新颖的近似比为4的算法approAlgNoNei，该算法改进了目前为止具有最佳近似比为447的算法。即，本文提出的算法可以得到更少数量的无人机。对于有邻域无人机最小数量部署问题，本文首次提出了常数因子的近似算法approAlgNei。 此外，本文通过大量实验评估了所提出算法的性能。针对无邻域无人机最小数量部署问题，本文将所提出的近似算法approAlgNoNei与算法BTCAlg，算法MCCPAlg1和算法MCCPAlg2进行对比。实验结果显示，算法approAlgNoNei得到的所部署无人机的数量比其它三个算法少11%至19%。针对有邻域无人机最小数量部署问题，本文将所提出的算法approAlgNei与未考虑邻域的算法BTCAlg，算法MCCPAlg1，算法MCCPAlg2和算法approAlgNoNei，以及考虑邻域的算法minMaxNei进行对比。实验结果显示，考虑邻域的算法所得到的无人机数量大大小于未考虑邻域的算法所得到的无人机数量。同时，算法approAlgNei所得到的无人机数量比算法minMaxNei所得到的无人机数量少14.5%至18%。
NETL