无线传感器网络数据收集的多无人机调度算法研究

张俊琪

（四川大学计算机学院，成都610065）

0 引言

目前，物联网技术已取得巨大发展。物联网设备例如无线传感器被广泛应用于智慧城市、智能交通、森林火灾检测，军用、民用领域的监控等。其中，在智慧城市的应用场景中，我们可以在城市的若干交通要道部署传感器设备，这些传感器设备可以实时监控路段情况，并且分析数据，进而可以规划出合理的路径从而避免交通事故。在森林火灾监测的应用场景中，我们可以在森林的关键位置部署若干传感器，这些传感器可以实时监控森林关键点的温度、湿度情况，一旦温度和湿度达到临界值，那么启用报警处理，通知相关工作人员及时处理，避免森林大火。

在有一定规模的无线传感器所构成的网络中，每一个传感器采用电池供电的方式，由于传感器电池容量有限，因此及时为传感器进行充电是传感器网络持续工作的重要措施。传统的方法有两种，第一是无线传感器能够采集周围环境的能量，例如太阳能充电。但是此方法对周围的环境有严格的要求，例如太阳光照强度在一天之内早晚比较低，在雨天、阴天太阳光也比较少。因此，此方法采集到的能量很不稳定。第二是部署一个或者多个移动充电设备去给无线传感器网络中节点充电[3]，此法能有效解决前者能量不稳定且过度依赖环境的问题。

传感器具有一定的储存和计算能力，可以收集周围环境一定范围内的数据，例如温度、湿度、风速、气体含量、地表元素含量等。在传统的无线传感器网络中，传感器感知周围环境的数据，并且采取“多跳”的方式，将数据不断传给下一跳传感器，最终传向基站，然后基站进行后续的数据处理和分析。然而传统的“多跳”的方式存在很大的缺点。一是处于不同位置的传感器节点的数据转发负载分布不均衡导致能量消耗不均衡。靠近基站的节点的转发次数更加频繁，往往会消耗更多的能量，这些节点也会更快的死亡，造成传感器网不能正常工作。二是如果网络规模比较大，边缘传感器所收集数据传到基站所耗费的时间往往很大，不利于实时数据的监控分析。

无人机具有廉价、低能耗、易部署的特点，因此，我们可以考虑将无人机应用于无线传感器网络的工作中。无人机主要应用于运输物品、目标跟踪、数据收集，以及无线充电[1-2]。

近年来，为了解决传统传感器网络中存在的问题，现阶段有采取移动基站去收集传感器网络数据的方式。但是，可移动基站往往只能在地面上移动，无法规避地面上的障碍物如河流、山川、悬崖等。也有一些工作采取部署单无人机去收集传感器网络的数据，但是一个无人机很难应对大型传感器网络。

本文采取部署多无人机的方式去收集无线传感器网络的数据。本文涉及到两种场景，第一种是无邻域的场景，就是无人机必须靠近每一个无线传感器才能接收到数据；另一种场景是有邻域的情况，就是无人机只需要落入距离以无线传感器为中心，一定距离为半径的圆形邻域内，即可收集到传感器的数据。其中第一种场景适用于打卡式传感器，即无人机携带的ID 卡必须接触无线传感器的读卡器，才能进行数据传输。第二种情况适用于无人机或者传感器可以利用信道进行数据传输，无人机只需要在距离无线传感器一定距离范围内即可完成数据传输。为了保证数据的实时性以及考虑满足无人机最大飞行时间的要求，我们部署的每一个无人机的总飞行时间不得超过一个规定的时间。

在如下场景中，见图1，部署了两架无人机搜集一定范围内的无线传感器的数据。由于无人机覆盖范围比较大，因此在考虑邻域的情况下，可以同时收集一定范围内的传感器数据。

图1

下面对比有邻域和无邻域两种情况下无人机收集传感器网络数据，见图2。由此可以看出，在考虑有邻域时，无人机不需要靠近传感器（传感器B）就可以收集到传感器数据，因此相比传感器A，无人机飞行距离大大降低，可以节约更多的时间从而收集其他更多无线传感器节点的数据。

图2

1 预备知识

1.1 网络模型

考虑在一个传感网络中，有ns数量的传感器，以及基站r，随机均匀分布在网络中。将传感器网络简化为一个无向图G=(Vs∪{r},Es)，Vs∪{r}是节点的集合，其中Vs={v1,v2,…,vn}，n为传感器节点的个数，所有的结点都是同一种型号的无线传感器。Es为边的集合，任意两个节点u和v之间存在一条边(u,v),d(u,v)表示两节点之间的欧氏距离，用Di表示节点vi的数据量，由于无人机飞行速度远大于无线传感器的数据收集速度，因此我们可以假定在一次多无人机调度中所有传感器节点的所采集到的数据量保持不变，其中1 ≤i≤n，ρv表示无人机数据收集速率。节点i的坐标(xi,yi) ，通信邻域半径为R，若不考虑通信邻域，则R=0。

1.2 数据收集模型

图3

图4

1.3 问题定义

假设无人机的数量为K，无人机的停靠坐标为(x,y)，在不考虑邻域的情况下本问题可定义为：

其中公式（1）限制每个无人机所走的路径花费的时间不超过最大时间限制T0，公式（2）表示所有传感器必须被K个无人机所访问。

在考虑邻域的情况下本问题可定义为：

公式（5）表示无人机必须停靠在以(xi,yi)为圆心，以R为半径的圆形邻域内，此问题本质上是一个优化问题。

针对这两个场景下的问题，本文提出两个算法来解决。

2 算法描述

在算法一中，我们解决在没有考虑邻域的情况。设想问题中的无线传感网规模很大，如果对整个图进行迭代构造，在某些极端情况如网络分布不均匀，最后划分出来的数量可能并不是最优的，因此我们采用一种分区域处理的策略。基于此，我们先将完全图按照一定阈值τ进行图划分，切分所有边权重大于τ的边。为了使划分成若干子图的数量合理，令τ=α∙max{w(e1) ,w(e2),…,w(em)}，其中0<α<1，m为图中边的个数，w(ei)为边ei的权重，其中1 ≤i≤m。然后在每个子图中采用近似算法构建出若干TSP 路径，最后求得的总的路径数量即为所求的K。

在算法二中，为了利用我们算法一的成果，我们对初始的完全图进行修改得到G'，任意两个节点的距离等于初始距离减去邻域直径，即d'(u,v)=d( )u,v-2R，如果圆环相交则距离为0。然后在新的图G'中调用算法一，则最终求得的数量则为无人机的数量。

因为本问题是一个TSP 问题的特殊形式，因此本问题是一个NP 难问题，即难以找到多项式时间对问题进行求解。本文提出的两个算法均通过迭代的方式划分出无人机的最佳路径。

3 实验结果及其分析

本文在这一小节采取模拟仿真实验对提出的两个算法进行验证。在100m×100m的二维平面内随机均匀部署10-50 个传感器节点，无人机最大运行时间T0=30 min，邻域半径为10m，无人机速度为10m/s。

图中的实验数据是在相同数量的传感器节点和20个不同的网络拓扑结构中取得的平均值。所有的实验结果均运行在参数为3.6 GHz 的CPU 和16GB 内存的一台服务器上，实验程序运行语言为Python。

图5

实验结果可以看到，节点数量从10 增加到50 的过程中，随着需要访问的节点数增加，需要部署无人机的数量增大，在同一网络规模的条件下，考虑邻域的情况所需要部署的无人机数量明显小于不考虑邻域的情况下无人机的数量。因为考虑了邻域，无人机不需要靠近传感器节点，因此无人机飞行的距离减少，所耗费的能量也减少，大大减少了无人机数量。

我们继续探究系数α对实验结果的影响。见图6。

图6

实验结果可以看到，随着α不断增大，两种算法得到的无人机数量均是先减小在增加，特别当α取值接近0.5 时，两种算法得到的无人机数量最小。因为此时可以认为子图的数量划分比较均衡，不存在过多或者过少的情况，所以得到的无人机的数量是最优的。

4 结语

本文提出了在有邻域和无邻域两种情况下无人机最佳数量的路径规划算法，在模拟数据集上进行了仿真实验，并且对比了两种算法，发现有邻域情况下大大节省了无人机的数量。传统传感器网络数据收集采取多跳方式，移动基站收集的方式，以及单无人机的方式，本文采取了多无人机的方式，巧妙解决了传统传感器网络中数据收集的相关问题。未来工作可以考虑在三维的场景下进行无人机路径规划，使用不同的邻域半径，并且考虑节点的能耗问题。算法也可以继续改进，例如划分的标准更加量化准确，得到的子图数量也更加合理。