无线监测网络部署在灾害监测与预警、生态监测、建筑结构健康监测、文化遗产保护等野外环境大规模监测场景中, 持续获取各种应用所需要的数据, 成为社会生活不可或缺的重要部分.野外环境复杂的通信条件和一定规模的监测覆盖要求, 使得保证长期且有效的数据收集成为一个监测网络成败的关键.

利用无线传感网络, 部署大量数据转发节点, 进行自组织传输网络构建, 形成数据传输通道, 成为较为常见的数据收集方法^[1], 其核心是:数据感知节点将采集到的数据经过一跳或者多跳中转节点传递给Sink节点, Sink节点通过3G或者卫星接入, 从而将数据返回监测中心.其关键挑战在于:当节点在野外部署时间过长时, 就会出现能量空洞问题^[2], Sink节点周围转发节点会过早地进入死亡状态, 导致数据采集失败.更为严重的是:为了保证可靠传输, 需要在大规模区域保证一定的覆盖, 从而导致需要大量的数据转发节点.传感网节点有效通信距离在50m左右, 成本150元, 如果覆盖20km²范围的野外遗址保护区, 且要保证覆盖率在90%以上, 仅通信节点就需要约5 000个, 费用在76万元左右^[3], 如此巨大的部署成本和代价, 难以在大规模监测场景中应用.

对此, 利用移动Sink节点进行数据收集, 成为了一个相对有效的解决方案.常见的思路是:将Sink节点放置在可移动小车上, 通过车的移动收集数据感知节点所采集的数据.

这种方法可以很好地解决能量空洞问题^[4], 但在诸多真实场景下难以实用.车的移动依赖完善的道路, 大部分野外监测在缺乏道路的无人区, 移动小车缺乏移动的条件, 我们称之为Sink移动范围受限.

最近兴起的无人机(UAV)技术成为Sink节点移动数据收集的有效解决方案^[5-7].无人机搭载Sink作为移动数据收集节点, 根据路径规划进行移动数据收集, 我们将这种方法称为基于无人机的数据收集方法.目前, 已经开始在农作物监测、灾后救援等方面展开初步应用^[8-10].其本质是用无人机的飞行代替了中间数据转发节点, 避免了过大的部署代价和成本以及能量空洞问题.同时, 这种方法将数据收集和数据采集分离在不同的空间维度展开, 也避免了“Sink移动受限问题”.因此, 利用基于无人机的数据收集方法成为大规模区域监测数据收集的有效手段.由于无人机主要收集的是感知节点已经采集并存储了一段时间的数据, 这些数据的实时性无法得到保证.因此, 无人机数据收集系统无法应用在实时性要求较高的应用中, 如火灾监控、防盗监控等.

现有的无人机由于能量有限导致飞行时间和里程受限, 如何在有限的能量下最大程度地收集数据, 成为目前研究的热点.一个解决思路是在监测区域内部署多个无人机进行协同工作^{[6, 11]}, 但是成本高, 协同工作更带来了额外的复杂度.另一个思路是建立路径优化模型, 使无人机沿最短路径访问每一个需要收集数据的采集点, 在有限的能量情况下, 尽可能多地收集数据.此类研究主要聚焦于如何在有限时间让数据收集数量最大, 而忽略了采集到的数据质量优化问题.采集到数据冗余性和相似度高使得数据价值低, 难以对整个部署区域数据进行有效表征, 数据收集失去了既定的意义.

如何利用无人机最少的能量付出在监测区域获取最大的数据价值, 其难点在于数据价值是针对不同应用的主观评价, 而位于不同地理位置的节点获取的数据价值如何比较, 目前缺乏统一的标准.我们发现, 数据相似节点的数据价值存在的相似性.在此基础上, 我们提出了一种数据收集方法——OnValueGet, 利用关键性代表节点的数据, 最大程度地近似代表整个监测区域的数据, 从而在能量约束下获得最大数据价值.其核心思想在于:从分析感知数据的时空相似性入手, 确定数据价值较高的感知节点, 本文称为数据关键节点, 在应用的误差范围内, 它们采集的数据可以近似表示全部网络感知节点采集的数据.无人机以数据关键节点为数据采集的核心目标, 在能量有限的情况下, 根据遇到的障碍物和节点感知到数据的异常与否, 动态地规划数据收集路线, 从而使收集到的数据具有最大价值, 显著提升数据收集的能效比.

1 相关工作

以文献[12-18]为代表的静态数据收集方法中, 主要使用数据中转节点建立自组织网络, 把数据传输到基站.核心在于通过最小化网络通信开销以及良好的能量负载平衡方法, 最大化网络生命周期, 保证数据可靠收集.

动态数据收集方法可以有效地避免能量空洞问题, 但主要面临数据延迟的挑战.当感知节点移动^[19]时, 研究通过选择高概率与Sink通信的下一跳节点, 保证低能耗和延迟.当Sink节点移动^{[4, 20]}时, 研究者侧重于如何离线规划好移动Sink节点数据收集路径保证低延迟, 如Shah^[21], 或者在线如何动态地规划Sink节点的数据收集路径保证低延迟.

基于无人机的数据收集方法^[5-7]本质上可以视作基于移动Sink节点的数据收集方法的特定实例, 因此, 其可以避免能量空洞问题.空中飞行不用依赖道路, 因此也避免了Sink移动受限问题.无人机数据收集有两种典型的工作方式:一种是在无人机上搭载数据感知节点, 让无人机在监测区域内航行并采集数据; 另一种是在无人机上搭载Sink节点, 飞行收集地面感知节点获取的数据.两种不同的工作方式对应两种不同的数据收集网络: FANET(flying ad-hoc network)^[7]和FGNET(flyingand ground networkd)^{[5, 6]}.前者不依赖于地面节点的部署, 具有较强的灵活性, 但是系统实现难度较大, 因此难以实用; 而后者更具有实用性, 成为目前数据收集方法的主流, 研究的焦点在于能耗、延迟和传输质量.

由于无人机的能量受限, 现有的无人机大都由电池供电, 航行时间有限, 难以有效地在大规模区域进行数据收集.如何在线地规划无人机数据收集的路线, 使得无人机在能量约束下获得最大数据量, 成为研究的热点.

为了解决无人机能量受限, 研究者们常常引入多无人机进行相互协同的完成任务^[22].例如, Ahmed等人^{[5, 6]}提出将簇头节点与无人机通信时间的分配问题抽象成一个势博弈(potential game)问题, 通过簇头节点之间的博弈, 既保证了节点之间的公平性和网络能量的高效, 又保证了整个网络在数据收集的过程中能效最大化.文献[23]提出了一种多无人机相互协同采集图像信息进行目标定位的方法.文献[24]利用多无人机相互协同工作完成了对未知环境探测的任务.此类方法可以解决由于无人机能量受限而引起的数据缺失问题, 但成本开销巨大, 而且大都假设周围环境对无人机的影响很小甚至没有^{[5, 6, 11, 23, 24]}, 真实场景不存在.

针对基于无人机的数据收集方法所带来的延迟问题, 在文献[11]中, 由Gu等人提出了一种集数据采集和收集为一体的数据收集方法.他们分别研究了在Karam^[25]模型中数据收集延迟和数据信息延迟问题, 最终提出了一种基于层次的多飞行器相互协作的数据收集方法.文献[26]提出一种DC-Collection算法, 不仅能够均衡各节点的能量消耗, 延长网络生命周期, 而且能够缩短移动数据收集器收集数据行走的路径长度, 从而缩短数据收集延迟.在文献[27]中, 作者提出了一种基于相对距离感知的动态数据传输方法RDAD(relative distance-aware data delivery scheme), 有效地降低了数据传输延迟.文献[28]提出了一种旅行动态决策算法SOFCOM, 使用详尽的搜索技术来计算全局最优决策序列, 从而达到减少延迟的目的.

目前, 由于广泛存在的各种无线信号, 使得利用卫星或者4G网络进行通信的无人机信号极易受到干扰, 导致传输质量下降.针对这个问题, 国内外的研究者从视频编码、空间频谱检测和信道状态的估计等多方面展开了深入的研究.文献[29]通过选择适合当前网络带宽的视频编码比特率, 保证实时连续的视频传输.文献[30]提出了一种分布式的移动算法, 使无人机群在空间和频率未知的情况下收集信道感知的指标, 如感测相关距离等, 以最大限度地提高检测精度.文献[31]在给定的最小信噪比内, 控制器控制无人机在可能的最大传输距离内盘旋, 通过观察SNR的变化情况, 让无人机飞到最适合的SNR地方进行数据的收集, 从而保证数据传输质量.

以上研究极大地提升了无人机数据收集的效率和性能, 但是针对收集到的数据的价值特性考虑不足.在一个既定的监测区域中, 现有研究只考虑到数据沿何种收集线路获取较好的数量、质量或者延迟, 但是没有考虑到收集的数据价值特性.换言之, 收集到的数据冗余度过大, 或者相似度过高, 对于应用而言, 并不能真正解决问题.例如, 在一个草原监测中, 一部分区域温湿度变化很大, 一部分区域温湿度变化不大, 如果根据延迟方法和能量方法, 取回的数据可能恰恰是温湿度变化不大的部分, 那么对于应用而言, 则丧失了有效的数据价值.

2 基于数据关键节点的数据收集方法OnValueGet

本节具体介绍基于数据关键节点的数据收集方法OnValueGet的基本思想以及具体实现过程.

2.1 OnValueGet框架

OnValueGet的核心在于进行数据关键节点选择, 并在此基础上动态规划数据收集路径.OnValueGet整体框架如图 1所示.

针对无人机如何利用有限的能量收集更有价值的数据问题, OnValueGet从分析感知数据的时空相关性入手, 提出数据关键节点的概念, 并设计了数据关键节点选择算法(data-critical nodes selection algorithm, 简称DcNS).OnValueGet将选出的数据关键节点作为UAV数据收集的主要目标, 并根据遇到的障碍物和节点感知到数据的异常与否情况, 利用Greedy算法动态地规划UAV的航行路线.使得UAV在网络区域内收集少量可以近似代表全网监测数据的数据关键节点数据.在保证采集数据价值的情况下, 减少了UAV数据收集过程中的任务量, 实现在能量约束的情况下最大限度地提升所收集数据的价值.

2.2 数据关键节点相关概念

定义1(感知数据序列).对于任意数据感知节点n_i, 将其在[t, t+α]时间段内采集的带有时序意义的数字序列{d_{i, t}, d_{i, t+1}, …, d_{i, t+α}}称为n_i在[t, t+α]上的感知数据序列.并将其记为$l_{i}^{t, t+\alpha } $, 其中, d_{i, t+j}表示节点n_i在时刻t+j, 0≤j≤α时采集的数据.

定义2(数据相似节点).在时间段[t, t+α]上, 数据感知节点n_i和n_j之间是否相似, 是根据在时间段[t, t+α]上, 节点n_i和n_j所采集的数据序列$ l_{i}^{t, t+\alpha } $和$ l_{j}^{t, t+\alpha } $之间的相似度来判断.若数据序列$ l_{i}^{t, t+\alpha } $和$ l_{j}^{t, t+\alpha }$之间的相似度在给定的阈值范围内, 则称节点n_i和n_j相似, 记为Sim(n_i, n_j).

定义3(数据关键节点).在监测网络的感知节点N中选择节点集合N_x, 若N_x满足以下3个条件, 则称N_x中的元素为数据关键节点.第一, 对于网络中节点∀n_a∈N-N_x, ∃n_b∈N_x与节点n_a相似; 第二, 当N_x中的所有节点在处于一条直线时, 保证相距最远的两个节点之间的距离(关键长度)最小; 当N_x中的所有节点没有处于一条直线时, 当保证由N_x中所有节点所对应的最小外接矩形的面积(关键面积)最小; 第三, 对于任何满足条件1和条件2的节点集合N_x'={N_x1, N_x2, …, N_xm}, 从中选择出元素数目最少的集合min(|N_x1|, |N_x2|, …, |N_xm|)作为数据关键节点集合N_x.关键长度和关键面积的物理意义在于使得采集数据相似的节点在地理位置上尽可能地聚集在一起, 从而有效地减少UAV的飞行距离.

定义4(节点覆盖范围).假设网络中数据关键节点的集合是N_x, N_x={cn₁, cn₂, …, cn_m}, 对于每个数据关键节点cn_i, 设与其相似的节点所组成的集合为S_i(节点自身与自身之间也存在相似关系), 设$ S_{i}^{sub} $为S_i的子集, 即$ S_{i}^{sub}\subseteq {{S}_{i}} $.如果∀cn_j∈N_x, ∀cn_k∈N_x, $ S_{j}^{sub}\cap S_{k}^{sub}=\varnothing $, 并且$S_{1}^{sub}\cup S_{2}^{sub}\cup ...\cup S_{m}^{sub}=N, $其中, N表示所有数据感知节点的集合.此时, 将$ S_{i}^{sub} $称为数据关键节点cn_i的节点覆盖范围.

定义5(数据价值).数据价值是每个数据感知节点所具有的属性, 具体表示由其采集的数据在具体应用中的使用价值决定.本文中假设:在正常状况下, 所有感知节点所采集的数据具有相同的使用价值, 为了简便起见将其设为1.因此, 对于数据关键节点cn_k, 如果所对应的节点覆盖范围为Γ, 则其数据价值为|Γ|.

定义6(应用误差ε). ε指应用可以接受的数据误差.假设应用误差ε=a, 当最终收集到的数据关键节点cn_i在时间段[t, t+α]内采集的数据序列$ l_{i}^{t, t+a} $与其覆盖范围$ S_{i}^{sub} $内所有感知节点采集到的数据序列$ l=\{l_{j}^{t, t+a}, l_{k}^{t, t+a}, ..., l_{n}^{t, t+a}\} $相差在[-a, a]之间时, 应用都是可以接受的.ε是根据应用要求设定.

2.3 数据相似节点判断方法

感知节点采集数据的价值是OnValueGet方法实现的重要依据.我们利用数据相似度作为数据价值的评估依据, 即数据相似、数据价值相似.由数据价值的定义可以得出, 数据关键节点的价值等于其覆盖范围内所有节点的价值之和.

因此, OnValueGet核心在于找到可以近似表示整个监测网络中感知节点采集数据的数据关键节点.根据数据关键节点的定义可知:要判断某一节点是否为数据关键节点, 必须求出该节点与其他节点之间的相似度.计算节点之间的相似度, 在本质上可以归结为计算两个节点采集的数据相似度.数据相似度的计算可以进一步分解为两个数据序列之间距离的求解(两个数据序列之间的距离越大, 相似性越小)和相似度阈值设定问题.

本文先对数据序列之间的距离问题进行讨论, 公式(2.1)是求解两个节点n_i和n_j的数据序列$ l_{t, t+\lambda \times \theta }^{i} $和$ l_{t, t+\lambda \times \theta }^{j}$之间距离最直接的方法:

$ dis_{t, t+\lambda \times \theta }^{i, j}=|{{d}_{i, t}}-{{d}_{j, t}}|+|{{d}_{i, t+\theta }}-{{d}_{j, t+\theta }}|+...+|{{d}_{i, t+\lambda \times \theta }}-{{d}_{j, t+\lambda \times \theta }}| $

(2.1)

但是公式(2.1)方法的缺陷在于要求节点n_i和n_j必须保证数据采集严格同步, 或者同时采集, 或是同时不采集.这种情况在真实网络环境中很难保证.原因在于无线信号受到影响的不确定性和节点真实采集周期的不固定性^{[32, 33]}.图 2显示了具有相同采集周期的不同节点, 每天采集数据的数量统计情况.从图 2中可以明显地看出:不同节点在同一段时间内采集到的数据数量是不同的; 而即使是同一个节点, 在不同的时间段内采集数据数量也会有所不同.

针对如何有效地计算数据序列$ l_{t, t+\lambda \times \theta }^{i}$和$ l_{t, t+\lambda \times \theta }^{j} $之间距离的问题, 通过分析发现, 类似于数据序列长度不同而导致难以有效计算两者之间距离的问题也出现在语音识别领域.对于同一个单词, 不同的人发音的长短以及音调的高低往往是不同的, 即使是同一个人, 对同一个单词的两次发音, 其音调高低以及发音长短也往往是不同的.认识到语音识别问题和数据序列距离计算问题的相同之处, 我们借鉴语音识别领域应用非常广泛的DTW (dynamic time warping)算法^[34]来解决两个长度不一样数据序列之间的距离计算问题.

利用DTW设计的数据序列之间距离计算方法描述如下.

假设有两个数据序列A={a(1), a(2), …, a(k)}, B={b(1), b(2), …, b(m)}, 序列A和序列B的维度分别是k和m, 为了不失一般性, 令k≠m, 对于它们每一维的元素可以有两种形态:一种是a(i)和b(i)是简单的数字, 也可以将其看成是维度为1的序列; 另一种就是a(i)和b(i)都是维度不为1的序列, 并且|a(i)|=|b(i)|, 即, 必须保证a(i)和b(i)的维度是相同的.运用DTW算法计算这两个不同维度序列之间的距离可以分两步来进行.

第1步:计算序列A每一个维度与序列B每一个维度之间的距离, 最终可以形成一个k×m维的矩阵, 记为C_{A, B}, C_{A, B}中第i行第j列的元素表示序列A中第i维元素与B中第j维元素之间的欧氏距离, 即:C_{A, B}(i, j)=|a(i)b(j)|;

第2步:设置一个与C_{A, B}同维度的空矩阵R_{A, B}.然后, 按照公式(2.2)扩展R_{A, B}矩阵, 最终, 矩阵R_{A, B}右下角的值即为序列A, B之间的距离, 即:dis^{A, B}=R_{A, B}(k, m):

$ {{R}_{A, B}}(i, j)=\min \left\{ \begin{array}{*{35}{l}} {{R}_{A, B}}(i-1, j)+{{C}_{A, B}}(i, j) \\ {{R}_{A, B}}(i-1, j-1)+{{C}_{A, B}}(i, j) \\ {{R}_{A, B}}(i, j-1)+{{C}_{A, B}}(i, j) \\ \end{array} \right. $

(2.2)

从上文的描述可知, OnValueGet利用DTW算法解决了数据序列之间的距离计算问题.接下来讨论相似度阈值的设定问题, 即:当数据序列之间的距离在多少范围内, OnValueGet判断两个节点是相似的.相似度阈值的设定直接影响着节点相似与否的判断, 从而影响数据关键节点的选择以及UAV节点最终采集到的数据价值.在本文中, 我们通过以下的证明分析给出适当的相似度阈值.

假设在时间段[t, t+α]内, 数据感知节点总共有H个采集周期(每个采集周期内采集一个数据).设β表示在时间段[t, t+α]内的每个采集周期内, 节点n_k和节点n_j采集到的数据之差的绝对值所构成的集合:

$ \beta =\left\{ {{\beta }_{1}}, {{\beta }_{2}}, \ldots, {{\beta }_{H}} \right\} $

(2.3)

$ {{\beta }_{i}}=|{{d}_{j, \Delta {{t}_{i}}}}-{{d}_{k, \vartriangle {{t}_{i}}}}| $

(2.4)

$ dis_{t, t+\alpha }^{k, j}=\sum\limits_{{{\beta }_{i}}\in \beta }{{{\beta }_{i}}}\le \varepsilon \times \max (|l_{t, t+\alpha }^{k}|, |l_{t, t+\alpha }^{j}|)=\varepsilon \times H $

(2.5)

假设β中小于ε的元素集合为β_Z, 大于等于ε的元素集合为β_Q, |β_Z|/|β_Q|=μ/ν.

定理1.当μ/ν存在, 且$ \mu /\nu \to \max (|l_{t, t+\alpha }^{k}|, |l_{t, t+\alpha }^{j}|) $, 或μ/ν不存在时, 若数据序列$ l_{t, t+\alpha }^{k} $和$ l_{t, t+\alpha }^{j}$之间的距离小于等于$ \varepsilon \times \max (|l_{t, t+\alpha }^{k}|, |l_{t, t+\alpha }^{j}|) $, 即$ dis_{t, t+\alpha }^{k, j}\le \varepsilon \times \max (|l_{t, t+\alpha }^{k}|, |l_{t, t+\alpha }^{j}|) $则节点n_k和节点n_j在[t, t+α]上是相似的; 当μ/ν存在, 且$ \mu /\nu \ll \max (|l_{t, t+\alpha }^{k}|, |l_{t, t+\alpha }^{j}|) $时, 若$ dis_{t, t+\alpha }^{k, j}\le \nu \varepsilon \times \max (|l_{t, t+\alpha }^{k}|, |l_{t, t+\alpha }^{j}|)/(\mu +\nu ) $, 则称节点n_k和节点n_j相似, 记为Sim(n_k, n_j).

证明:当|β_Q|=0时, 则β中的所有元素都小于ε.在物理意义上表示在时间段[t, t+α]内的任意采集周期Δt_i内, 节点n_k和节点n_j采集的数据${{d}_{k, \Delta {{t}_{i}}}} $和${{d}_{j, \Delta {{t}_{i}}}} $, 它们之间的相差都在应用误差范围内, 即$ |{{d}_{j, \Delta {{t}_{i}}}}-{{d}_{k, \Delta {{t}_{i}}}}|<\varepsilon $, 因此在任意时刻, 节点n_k采集的数据都与节点n_j采集的数据相似, 所以Sim(n_k, n_j).

当|β_Z|≫|β_Q|时, 则β中的几乎所有元素都小于ε.在物理意义上表示在时间段[t, t+α]中存在s个采集周期{Δt_r1, Δt_r2, …, Δt_rs}, 节点n_k和节点n_j在这些采集周期内采集的数据$ \{{{d}_{k, \Delta {{t}_{r1}}}}, {{d}_{k, \Delta {{t}_{r2}}}}, ..., {{d}_{k, \Delta {{t}_{rs}}}}\} $和$ \{{{d}_{j, \Delta {{t}_{r1}}}}, {{d}_{j, \Delta {{t}_{r2}}}}, ..., {{d}_{j, \Delta {{t}_{rs}}}}\} $, 它们之间相差都大于给定的应用误差, 即$ |{{d}_{k, \Delta {{t}_{rx}}}}-{{d}_{j, \Delta {{t}_{rx}}}}|>\varepsilon, 1\le x\le s $, 但由于s→0, 所以在这种情况下, 我们也认为节点n_k采集的数据与节点n_j采集的数据相似, 所以Sim(n_k, n_j).

当|β_Z|≪|β_Q|时, 则β中的几乎所有元素都大于等于ε.假设β中所有小于ε的元素之和为|β_small, 则有:

$ \mathop {\lim }\limits_{|{\beta _Q}| \to H} {\kern 1pt} \frac{{\varepsilon \times H - {\beta _{small}}}}{{|{\beta _Q}|}} - \varepsilon = 0 $

(2.6)

公式(2.6)的物理意义在于, 此时虽然β中的几乎所有元素都大于等于ε, 但是β中元素与ε相差趋近于0, 即β_i-ε→0, β_i∈β.在这种情况下, 我们也认为节点n_k采集的数据与节点n_j采集的数据相似, 所以Sim(n_k, n_j).

当|β_Q|与|β_Z|相当时, 可分两种情况分别讨论.

● 若β_Z与β_Q中的元素与ε之差都趋近于0, 即两个数据序列之间的相似性稳定, 在这种情况下, 我们认为n_k采集的数据与n_j采集的数据相似, 所以Sim(n_k, n_j);

● 若β_Z与β_Q中的元素与ε相差极大, 即$ \sum\limits_{{{\beta }_{i}}\in {{\beta }_{Z}}}{{{\beta }_{i}}}\approx 0 $, 那么$ \sum\limits_{{{\beta }_{j}}\in {{\beta }_{Q}}}{{{\beta }_{j}}}\approx H\varepsilon $, E(β_j)≈ε(μ+ν)/ν.此时, 虽然两个数据序列的整体误差均值仍为ε, 但是β_Q集合中几乎νH/μ+ν个数据的误差均值为远大于应用误差ε.我们认为两个数据序列之间的相似性不稳定, 此时应将相似度阈值设置为$ \nu \varepsilon \times \max (|l_{t, t+\alpha }^{k}|, |l_{t, t+\alpha }^{j}|)/(\mu +\nu ) $, 即:当$ dis_{t, t+\alpha }^{k, j}\le \nu \varepsilon \times \max (|l_{t, t+\alpha }^{k}|, |l_{t, t+\alpha }^{j}|)/(\mu +\nu ) $时, 我们认为Sim(n_k, n_j).

因此, 如果在时间段[t, t+α]内, 节点n_k和节点n_j的采集周期是完全同步的, 而且两者都没有丢失数据, 并且数据序列$l_{t, t+\alpha }^{k} $和$ l_{t, t+\alpha }^{j} $之间的距离小于ε×H, 则节点n_k和节点n_j是相似的, 即Sim(n_k, n_j).

如果在时间段[t, t+α]内, 节点n_k和节点n_j的采集周期没有完全同步, 或者出现了丢失数据的情况, 则利用DTW算法将维度较短的向量进行了拉伸, 然后与维度较长的向量进行距离求解, 得出$ l_{t, t+\alpha }^{k} $和$ l_{t, t+\alpha }^{j} $之间的距离.因此, 同理可以得到:如果数据序列$l_{t, t+\alpha }^{k} $和$ l_{t, t+\alpha }^{j} $之间的距离小于$ \varepsilon \times \max (|l_{t, t+\alpha }^{k}|, |l_{t, t+\alpha }^{j}|) $, 则节点n_k和节点n_j是相似的, 记作Sim(n_k, n_j).证毕.

2.4 数据关键节点选择方法DcNS

第2.3节讨论了判断节点相似的方法与阈值的设定, 接下来我们要在此基础上找出的数据采集的核心目标点:数据关键节点.其难点在于如何从给定的网络节点中, 快速准确地找出符合数据关键节点要求的节点集合.我们通过对问题的分析, 提出了基于贪心策略的数据关键节点选择方法.

根据数据关键节点的定义, 数据关键节点的选择问题可描述为:假设整个网络是一个无向图G=(V, E), 网络中的感知节点是图G中的顶点集合V.如果通过对感知数据分析得知, 在应用的误差要求下, 节点u和v相似, 则两个顶点之间存在边e=(u, v), e∈E; 反之则不存在边.我们将图G称为全网节点的相似关系图.如何从网络中所有的数据感知节点中选择出数据关键节点, 可以理解为在V中找到一个节点集合N_x, 使得网络中剩余的任意一个顶点u∈V-N_x至少有一个邻居顶点v∈N_x, 同时保证N_x中的顶点数目最少, 并且N_x中的顶点所对应的关键长度或者关键面积最小.

定理2.网络中数据关键节点的选择问题是NP-hard.

证明:由于图论中最小支配集问题是典型的NP-hard^[35]问题, 因此只要能将最小支配集问题等价转换成数据关键节点选择问题的一个特例, 我们就可以证明数据关键节点选择问题是NP-hard问题.下面我们通过一个多项式时间的规约来证明.

首先, 给定无向图图G=(V, E), 将图G作为数据关键节点选择问题的一个实例.其中, V表示网络中所有的感知节点, E表示任意两个节点之间的边.若两节点之间有边, 则表示两节点相似.然后, 构造一个拓扑结构与G相同的无向图G'=(V', E'), 并将其作为最小支配集问题的一个实例.

我们从V中找出元素个数最少的节点集合N_x, 使得对于V-N_x中任意一个点u, 集合N_x中存在一点v, 使得Sim(n_k, n_j).也就是说, 对于V中的任意一个点u, 要么在集合N_x中, 要么与集合N_x中的点v相似.当不要求N_x中的节点对应的关键长度或关键面积最小时, 从V中要找的节点集合N_x与从V'中要找出所有支配集中顶点个数最少的支配集${{{N}'}_{x}} $是相同的.因此, 数据关键节点选择问题是NP-hard问题.证毕.

OnValueGet对于数据关键节点的选择, 可以分为3个步骤.

第1步.根据节点之间的相似性构造全网节点的相似性关系图;

第2步.找出网络中所有的最小支配集;

第3步.在这些最小支配集中找出关键面积最小的作为数据关键节点.

从上文中我们可以看出:数据关键节点求解问题最核心的部分是从一个无向图中找出其所有的最小支配集, 即LMDS问题.而到目前为止, 对于LMDS问题最优的精确求解算法, 其时间复杂度为O(2^0.78n)^[36].为了UAV能够高效地完成数据关键节点的数据收集工作, 必须寻求其他方法来选择数据关键节点.针对上述问题, 本文在文献[37]所给出的解法基础上提出了数据关键节点的选择算法DcNS, 见算法1.

算法1.数据关键节点选择算法DcNS.

Input:

●   D_pre:网络中感知节点采集历史数据;

●   $ {{P}_{n*}} $:网络中所有节点的位置;

●   ε:应用误差;

Output:数据关键节点集合.

1:   dtw(D_pre, ε)→Sim_graph

2:   cnodeset={}

3:   While Sim_graph.|V| > 0

4:     for all v∈Sim_graph.V do

5:       $ Si{{m}_{graph}}[v].worth=\frac{Si{{m}_{graph}}[v].|neibor|}{dis(Si{{m}_{graph}}[v], cnodeset)} $

6:     end for

7:     cn=findmaxworthnode()

8:   cs.cnode=cn

9:     cs.coverage=Sim_graph[cn].neibor

10:     cnodeset.push_back(cs)

11:     Sim_graph.V-=Sim_graph[cn]

12:     Sim_graph.V-=Sim_graph[cn].neibor

13: end while

14: Returncnodeset

DcNS算法的主要输入有:网络中所有感知节点所采集的历史数据集D_pre、网络中所有感知节点的地理位置$ {{P}_{n*}} $以及应用的误差要求ε.算法的输出是网络中数据关键节点的集合以及每个数据关键节点所对应的节点覆盖范围.

在DcNS算法的第1行中, 以历史数据D_pre为输入, 利用DTW算法计算节点采集数据序列之间的距离, 然后根据应用的误差要求判断节点之间是否相似, 进而构建全网节点的相似关系图Sim_graph.DcNS算法的第3行~第14行是求解数据关键节点的过程.在算法的第4行~第6行, DcNS根据公式(2.7)计算Sim_graph中每个节点相对应的价值(worth)属性.

$ Si{{m}_{graph}}[v].worth=\frac{Si{{m}_{graph}}[v].|neibor|}{dis(Si{{m}_{graph}}[v], cnodeset)} $

(2.7)

公式(2.7)的分子表示Sim_graph中节点Sim_graph[v]的邻居节点数目, 分母表示Sim_graph[v]与现有的数据关键节点集合cnodeset中节点距离的平均值.因此, 节点Sim_graph[v]的价值属性worth与其邻居节点的数目Sim_graph[v].|neibor|成正比, 与现有数据关键节点的距离dis(Sim_graph[v], cnodeset)成反比.算法第7行找出Sim_graph中worth属性最大的节点cn, 其最终目的是找出节点cs, 使得节点cs的数据价值最大, 并且与现有的数据关键节点距离最近; 然后, 将此节点加入到现有的数据关键节点集合cnodeset中, 并设置该数据关键节点cs的coverage属性为它所有的邻居节点(数据关键节点的coverage属性为其覆盖范围); 最后, 将节点cs及其相对应的邻居节点从顶点集合Sim_graph.V中删除.

下面根据DcNS算法执行的两个阶段详细分析DcNS算法的时间复杂度.DcNS算法选择数据关键节点的第1阶段是利用DTW算法, 构建全网节点的相似关系图.由于在构建相似关系图的过程中, 要判断每个节点与网络中其他节点之间是否相似, 因此其时间复杂度为O(n²), 假设节点对应的数据序列的平均长度为a, 则第1阶段整体的时间复杂度为O(a²×n²).DcNS算法的第2阶段是根据相似关系图选择数据关键节点, 其核心部分是对所有节点进行两次循环判断过程.因此, 第2阶段的时间复杂度为O(n²).因此, DcNS算法的时间复杂度为O(a²×n²).

假设全网节点相似性关系图Sim_graph中有N个顶点和M条边, 且最终由DcNS算法计算得出的数据关键节点的数目为κ, 由文献[37]中的结论可以得知, $ \kappa \le N+1-\sqrt{2M+1} $.因此, 如果将数据关键节点作为UAV数据收集的目标节点, 则UAV数据收集的任务量最少可以减少$ \sqrt{2M+1}-1. $

DcNS算法计算出的数据关键节点在网络运行过程中并不是固定不变的.由于数据关键节点是UAV进行数据收集的主要目标节点, 所以其会与UAV频繁地通信.因此, 如果数据关键节点一直固定不变, 则其能量会快速耗尽, 影响网络的生存周期以及UAV收集数据的可靠性.针对此问题, 本文提出的解决方法是:为数据关键节点设置一个能量阈值, 当其能量小于此阈值时, 则在其节点覆盖范围内找到与现有的数据关键节点平均距离最小的那个节点, 将其设定为新的数据关键节点.由于篇幅的限制, 本文不详细讨论该能量阈值的具体设置情况.

2.5 基于数据关键节点的无人机数据收集

选出m个可以近似表示整个监测网络中感知节点采集数据的数据关键节点N_x={cn₁, cn₂, …, cn_m}之后, OnValueGet将N_x={cn₁, cn₂, …, cn_m}中的节点作为数据收集的主要目标, 并根据数据关键节点的具体位置以及数据收集过程中可能出现的异常情况和障碍物情况, 动态地规划UAV的飞行路线.

为了便于描述UAV数据收集过程, 本文假设每个UAV都有一个数据收集任务队列DCTQ(data collection task queue), DCTQ={T₁, T₂, …, T_n}, 用来存储其当前状况下所有的数据收集任务.DCTQ中的每一个数据收集任务T_i∈DCTQ都由该任务对应的节点号Node_id和该节点对应的数据价值Node_worth两项组成, 即T_i={Node_id, Node_worth}.在UAV进行数据收集的初始阶段, 利用集合N_x={cn₁, cn₂, …, cn_m}中节点的节点号和其数据价值对DCTQ进行初始化.如果UAV完成了DCTQ中的某项任务, 则将此任务从DCTQ中删除.

针对监测网络中可能出现的不在数据关键节点监测范围内异常情况, OnValueGet根据数据平凡节点发送的异常感知数据请求ADCR(abnormal data collection requst)来进行异常数据的收集.数据平凡节点是网络中除去数据关键节点外的数据感知节点, 它并不是UAV进行数据收集的目标节点, 只有当其采集到异常数据的时候才有可能成为UAV的数据收集目标.数据平凡节点将采集到的数据暂存在自己的存储模块, 如果存储模块已满, 则使用FIFO方法进行替换.如果数据平凡节点采集的数据不在预先设定的正常范围内, 则标记这条数据为异常数据, 然后计算此时节点相应的数据价值, 接下来调大发射功率, 发送一个短小的控制报文, 即ADCR给UAV, 控制报文的内容包括节点号和节点此时对应的数据价值.当UAV收集到ADCR时, 将其存储在自己的DCTQ中.

本文将UAV从起始点出发到再次回到起始点记为一个工作周期w, UAV在一个工作周期内理论上最大的可用能量为E_w.设在一个工作周期内, 向UAV传输数据的所有数据感知节点的集合为l={n_j, n_k, …, n_m}, 所以在一个工作周期内UAV收集的所有数据, 其数据价值总和见公式(2.8):

$ V=\sum\limits_{{{n}_{i}}\in l}{v({{n}_{i}})} $

(2.8)

其中, v(n_i)表示节点n_i的数据价值.

综上所示, UAV数据收集的路径规划问题可表述为:在数据收集的过程中, 如何动态地选择DCTQ中数据收集任务执行的先后顺序, 保证其在一个工作周期内收集到的数据具有最大的数据价值, 而且在数据收集的过程中满足以下限制条件:网络中节点位置信息已知; UAV能量有限; 数据关键节点数据价值已知; 数据平凡节点数据价值未知.

从以上的描述中可以分析得出, UAV数据收集的路径规划问题是一个Online Knapsack Problem, 这是一个NPC问题, 不存在有效的近似算法^[38].

为了解决此问题, 本文引入收集效益(collection gain, 简称CG).CG的物理意义为:UAV在当前状况下, 收集一个感知节点的数据所产生的直接投入产出比和最大间接投入产出比的数学期望之和.它反映了UAV的能量使用效率.因此, 如果一条数据收集任务的CG值越高, 则UAV执行该任务的优先级越高.

对于UAV的DCTQ中的第i条任务T_i而言, 其对应的收集效益可以根据公式(2.9)计算得到:

$ C{{G}_{i}}=(1-\partial )\frac{{{\mathbb{C}}_{i}}}{||{{P}_{UAV}}-{{P}_{{{n}_{i}}}}||}+{{(1-\partial )}^{2}}f_{\max }^{i} $

(2.9)

在公式(2.9)中, ∂表示在数据收集过程中数据平凡节点采集到异常数据的概率, ℂ_i表示T_i所对应的数据价值, P_UAV表示UAV的实时位置, $ {{P}_{{{n}_{i}}}}$表示T_i对应的数据感知节点n_i的位置.因此, $ {(1-\partial ){{\mathbb{C}}_{i}}}/{||{{P}_{UAV}}-{{P}_{{{n}_{i}}}}||}\;$表示UAV执行任务T_i的直接投入产出比的数学期望.函数$ f_{\max }^{i}$表示UAV执行完任务T_i后, UAV任务队列中所有任务投入产出比的最大值, $ {{(1-\partial )}^{2}}f_{\max }^{i} $表示UAV执行T_i的间接最大投入产出比的数学期望.因此, 公式(2.9)表示UAV执行某个数据收集任务时(收集某个节点的数据)所对应的收集效益.

根据收集效益, 本文采用贪心方法对UAV收集数据的路径进行规划, 使得UAV最终收集到尽可能大的数据价值.

3 仿真实验结果与分析 3.1 仿真环境与真实数据来源分析

本文所提出的OnValueGet方法主要关注于如何选择数据关键节点.因此, 我们假设MAC层数据碰撞问题可以得到较好的解决.我们利用MATLAB进行仿真实验数据分析.仿真实验的硬件环境为:处理器, Intel i5 2.8GHz; 内存, 8GB; 硬盘, 1TB; 软件环境为, Windows7 64bit, Mysql 5.5.

仿真实验使用的数据为真实采集的室外数据和室内数据.其中室外数据集是采用了2015年12月1日~ 2015年12月20日之间, 部署在榆林镇北台长城遗址内的41个数据感知节点所采集的长城遗址土壤内部15cm深度的温度值.数据采集的范围是-20℃~40℃之间, 部署图如图 3所示.

室内数据集是采用了2004年2月28日~2004年4月5日之间, 部署在Intel Berkeley Research实验室的54个数据感知节点所采集的周围环境中的温度、湿度、光照和自身的电压数据, 部署图如图 4所示.对于室内实验采集到的4种数据, 本文只利用节点采集的温度数据.由于在本文所选择的时间段内, 5号节点没有数据, 所以在进行实验时实际使用了其他53个节点的温度数据.

3.2 DcNS算法验证与分析

下面分别利用室外和室内数据集, 对本文提出的数据关键节点的选择算法DcNS的正确性进行验证.

图 3的部署图中标出了将应用误差设置为0.01时, 室外数据集所对应的数据关键节点及其相应的节点覆盖范围.图中正方形表示数据关键节点, 六边形表示数据平凡节点.相同的颜色背景节点表示在同一颜色背景的数据关键节点的覆盖范围内.从图 3中可以看到, 整个网络中有6个数据关键节点, 因此在无异常感知数据的情况下, 整个数据收集过程中的任务量将会减少85.37%.这6个数据关键节点中, 6号、34号、36号数据关键节点所对应的节点覆盖范围比较大, 分别是19, 12, 7, 占到了整个网络节点数目的92.67%.

对于6号数据关键节点所对应的节点覆盖范围, 它们在位置上正好位于太阳每天照射的地方, 因此这些地方的土壤温度都相对较高, 所以这些节点所采集的数据具有很大的相似性; 对于34号数据关键节点所对应的节点覆盖范围, 由于镇北台西墙地势较高, 东墙地势较低, 西墙的外侧和东墙的内侧基本都挡住了太阳, 而且墙体很厚, 所以在西墙的内侧和东墙的外侧采集的土壤温度值都比较低, 所以这些节点采集的数据具有巨大的相似性; 对于36号数据关键节点所对应的节点覆盖范围, 由于北墙的外侧是条路, 所以北墙外侧土壤的温度受外界影响较大与其他墙体都有一定的差别, 所以这些节点采集的数据具有巨大的相似性.

图 4的部署图中标出了将应用误差设为0.0001时, 室内数据集所对应的数据关键节点及其相应的节点覆盖范围.从图 4可以看出:共有7个数据关键节点, 45号数据关键节点的节点覆盖范围为42, 占到了整个网络节点总数的70.77%;其他数据关键节点的覆盖范围则零散地分布在监测区域的左下角和右上角.整体看来, 数据关键节点以及其对应的节点覆盖范围, 在地理分布上没有任何显著的特征.这是因为在室内环境下, 环境非常稳定, 并且室内的空气也是相互流通的, 因此几乎在各个地方空气温度值都是相同的, 数据之间基本都是相似的, 所以才会出现上述结果.

图 5是将应用误差ε分别设置为0.001, 0.002, 0.005, 0.01, 0.02, 0.05时, 室外数据集对应的数据关键节点的数目分布图.图 6是将应用误差ε分别设置为0.000 1, 0.000 2, 0.000 5, 0.001, 0.002, 0.005时, 室内数据集对应的数据关键节点的数目分布图.我们利用文献[11]中提出的Greedy算法和第2.4节提出的数据关键节点选择算法DcNS分别对节点数据集进行处理, 在不同的应用误差下选择数据关键节点, 并对关键节点的数量进行比较.

从图 5和图 6中可以看出:无论是使用室外数据集还是室内数据集, 数据关键节点的数目都会随着应用误差的增加而减少.这是因为当应用误差增加的时候, 会促使更多的节点在同一时刻采集的数据在误差的范围内, 所以更多的节点将会在一个数据关键节点的节点覆盖范围内.

从实验结果可知, 通过Greedy算法处理节点数据得到的关键节点数量明显大于通过DcNS处理节点数据得到的关键节点数量.这是因为Greedy算法只是利用节点相似关系图找出与最多节点相似的节点作为数据关键节点, 而DcNS在此基础上将已存在的数据关键节点的位置作为新的限制条件, 使得新选择的数据关键节点的位置尽可能地靠近已经选择的数据关键节点, 同时也减少了数据关键节点的数量.又因为关键节点数量越多, UAV节点就需要采集更多任务节点的数据, UAV的数据采集任务就越大, Greedy算法对应的UAV任务量明显比DcNS对应的UAV任务量大.综上所述, 若采用DcNS来处理节点数据, 能够很好地减少关键节点数量, 从而减少UAV数据采集任务.

图 7、图 8分别是在使用室外数据集和室内数据集的环境中, 不同应用误差下, UAV收集所有节点数据花费时间和只收集关键节点数据花费时间的对比.根据现实环境中的情况, 本文假设UAV节点每航行一个单位长度耗费0.02个单位能量, 在航行的过程中, 总是以单位时间内(这里设定为1s)航行1.6个单位长度的速度匀速运行.且在UAV节点数据收集之前, 它已经获取了数据关键节点的所有信息以及网络中所有数据感知节点的地理位置.

因为应用误差只对关键节点个数有影响, 所以随着应用误差的增大, 关键节点个数变小, UAV完成数据收集任务航行的路径变短, 完成数据收集任务的时间也随之变少.而UAV收集所有节点数据的时间和应用误差是没有直接关系的, 所以不管应用误差如何变化, UAV收集所有节点数据花费的时间保持不变.

由图 7、图 8可以看出:室内数据集和室外数据集的仿真环境中, 无论应用误差如何变化, UAV收集所有节点数据花费时间总是远远大于只收集关键节点数据花费时间.在仿真实验中, 因为UAV以匀速飞行, 单位飞行长度和单位飞行时间内UAV耗费能量不变, UAV耗费能量和UAV飞行时间是呈正比关系.所以, UAV收集所有节点数据的能耗大于只收集关键节点数据的能耗.

图 9、图 10所示为在室外数据集和室内数据集环境中, 关键节点数量从1递增至10时, DcNS算法选择的数据关键节点采集的数据与数据关键节点覆盖范围内数据平凡节点采集的数据之间的平均误差变化(在此称为数据误差).可以看出:随着关键节点数量的增加, 数据误差会迅速变小, 最终保持在一个非常小的数量级上(室内数据误差在小数点后3位, 室外数据误差在小数点后两位).

因为数据关键节点是在给定的应用误差下对比网络内节点采集数据的相似性进行判断, 所以从结果可以看出, 数据关键节点采集的数据和其覆盖范围内的数据平凡节点采集的数据的平均误差在给定的应用误差范围内.虽然有个别数据的误差大于给定的应用误差, 从整体来看, 数据误差的分布较为稳定, 没有出现太大的波动.除此之外, 虽然相对于网络中所有的节点来说数据关键节点不能采集全部的信息, 但是收集数据关键节点采集的数据和所有平凡节点采集的数据之间的误差并不是很大, 这样就使得系统可以在给定的应用误差范围内有效的减少相似冗余的数据.

表 1是将应用误差分别设置为0.001, 0.002, 0.005, 0.01, 0.02, 0.05时, 数据关键节点选择算法的运行时间的变化情况.从表 1中可以看出:无论应用误差设置多少, 数据关键节点选择算法的运行时间不会有相关性的变化.在第2.4节中我们已经对算法的时间复杂度进行了分析, 结果表示:算法时间复杂度与待分析的数据量及节点数目有关, 与应用误差范围没有关系.

从本节的实验结果可知:应用误差要求与数据关键节点的数目以及关键面积大小有着密切的联系, 从而影响到UAV进行数据收集时的任务量和航行路径长度.因此, 选择合适的应用误差, 对于求解数据关键节点至关重要.通过对比可以得出:UVA节点收集数据关键节点采集的数据可以有效地减少采集时间, 进而减少采集能耗.同时, 数据关键节点采集的信息和其覆盖范围内所有节点采集的数据相比, 误差在允许的应用误差范围内.通过实验分析可以验证, OnValueGet数据收集方法可以有效地提高UVA节点收集数据的效能.

4 总结

面对目前无线监测网络中主要的数据收集方法在实际应用中严重受限的问题, 本文提出基于UAV的数据收集方法OnValueGet, 设计了基于数据关键节点的发现方法.实验结果表明:OnValueGet在应用规定的误差范围内有效地减少数据收集量, 从而减少数据收集能耗和时间.在UAV节点能量限制的情况下, 提高收集数据的总价值.但是, 数据关键节点的选择以感知节点采集的数据内容为主要依据, 忽略了节点位置信息所占的价值比重.因此, 研究数据关键节点为网络代表的方法在部分物联网应用(如位置服务应用)中存在很大的限制, 因此主要适用于位置信息已知的、以感知节点采集数据内容为主要目标的大规模物联网监测应用.

除此之外, 在真实场景应用中, 本文的许多工作还有进一步的提升空间.

● 首先, 本文利用感知数据在物理意义上的时空相关性以及周期变化性, 对传感网的历史数据进行了分析, 然后得出了网络中的数据关键节点.然而如何选取历史数据, 对于分析得到数据关键节点是非常重要的一部分.对此类数据集进行挑选的方法, 是下一步要进行的工作;

● 其次, 在对UAV节点进行数据收集的仿真过程中, 本文尽量去模拟UAV节点在真实环境中遇到的一些状况, 但是与真实情况相比还是有一些噪声需要进一步模拟, 所以最终的结果与真实环境可能还会有一定差距;

● 最后, 对于数据关键节点能量阈值的设置, 本文没有进行详细的讨论.因此, 关于数据关键节点能量阈值的设置以及更新方法, 需要在下一步工作中继续进行深入研究.