基于汇聚点的数据采集优化方案

直接接触数据采集具有节约能量的巨大优势。但是，由于汇聚节点移动速率较低，因而它大大提高了数据采集延迟。基于汇聚点的数据采集用于实现能耗与时间延迟之间的折中。传感器以多跳通信的方式，向称为汇聚点（RP）的传感器子集发送测量数据。汇聚节点在网络内移动，并从遇到的RP处获取数据。RP的应用支持汇聚节点一次采集大量数据，而不需要移动较长距离，因而大大降低了数据采集延迟。相关的研究主要集中在RP选择上。需要注意的是，由于RP是静态的，向RP的数据分发过程等价于向静态汇聚节点分发数据的过程，后者在传统静态WSN中已经得到广泛研究。

1.根据固定轨迹来选择RP

参考文献（Kansal et al.，2004）提出使用直线汇聚节点路径来进行数据采集。在初始化阶段，当汇聚节点沿着直线移动时，它广播一条信标消息。该消息包含一个的跳数域，用于表示它已经访问的跳数。当且仅当消息中的跳数小于存储的跳数时，每个接收节点重播该消息。在重播之前，接收节点将跳数增加。汇聚节点也记忆发送消息给它的节点。初始化阶段之后，构建了许多树，每棵树的树根是汇聚节点路径上的一个节点，每个节点恰好属于一棵这样的树。

每棵树的根看做是一个RP。随后，传感器沿着指向它们所在树的根节点的上行路径发送测量结果。当汇聚节点移动时，RP将自身数据与从树成员处接收的数据，一起发送给汇聚节点。两种运动控制算法可用于调整汇聚节点速率，以提高受控数据的数量。在停止采集数据（Stop to Collect Data，SCD）算法中，汇聚节点在发现传感器等待传输数据的位置停一段时间。在其他算法中，汇聚节点在数据传输成功率较低的区域慢速移动，在数据丢失严重的区域短暂停顿。

参考文献（Jea et al.，2005）考虑了多汇聚节点的场景。感知区域被划分为面积相等的区域，每个区域中有一个汇聚节点。然后，在每个区域内运行单汇聚节点算法。随机传感器分布可能会导致汇聚节点路径上的负荷失衡（即传感器分配）。负荷均衡算法可用于确保为每个汇聚节点路径分配数量相等的传感器。该算法可通过所选的汇聚节点来执行。通常假定汇聚节点能够相互通信，这样它们能够交换传感器分配信息。

参考文献（Xing et al.，2008）考虑了仅支持汇聚节点沿着固定轨迹移动的情况。作者假定传感器具有相当的传输范围，且进行密集部署。在这种网络中，沿多跳路径的消息传输总能耗与发送方和接收方之间的欧氏距离成正比。同时，在每个传感器节点处使用数据融合。目标是沿着汇聚节点轨迹选择RP，使得连接源到RP的边的总长度最小。

针对固定轨迹，人们提出了一种基于MST的汇聚点设计算法（RD-FT）。在这种算法中，提出了欧氏环中MST的最优集MST_sT，它能够将所有源连接到汇聚节点轨迹（sT）。最优集中的每个单独MST不一定涉及所有数据源。之所以说它是最优集，是因为其成员MST的长度总和是最小的。MST_sT中的每个MST满足如下两个条件：

1）它的根要么在汇聚节点起点、终点、转折点，要么位于数据源在sT上的投影点上；

2）对于它所包含的任意数据源来说，树路径到根的长度小于它到sT上其他任意点的距离。图6-6给出了点X和Y之间的7个数据源、1个sT（曲折线）。在该实例中，MST_ζ包含5个MST，其根节点分别在sT上的A、B、C、D、E处。需要注意的是，节点6与节点7相连，而不是与sT上最近的E点相连，因为链路6—7比链路6—E短（因而在这种方式中，局部MST较短）。

图6-6 针对固定轨迹的汇聚点设计

在数据采集的实践中，MST_sT集是最优报告树的近似。因此，RD-FT算法将这些树的根节点作为RP。它采取Kruskal算法（Kruskal，1956）（稍微进行了修改）来寻找MST_sT。当MST_sT构建完毕后，即可找到RP。然后，执行器（汇聚节点）访问路线可以简化为仅通过包含这些点的轨迹的一部分。例如，在图6-6中，汇聚节点将仅访问A与E之间的部分。

2.使用报告树来选择RP

参考文献（Xing et al.，2007，2008）研究了基于报告树的RP选择问题，限制条件为数据采集时限D。必须从数据报告树中合理选择汇聚点，使得RP的汇聚节点访问路径不超过汇聚节点在时间D内能够访问的最大距离L。(www.xing528.com)

在参考文献（Xing et al.，2007）中，作者考虑了一种预定义报告树，其根节点位于静态基站BS处。在这种树中，被多个数据报告树共享的节点称为连接节点。假定源节点位置和连接节点位置已知，且节点密集部署。这样，报告树可以近似用根节点在BS、由多个源节点和连接节点构成的几何树TR来表示。TR边上的任意点可以充当RP。文献对受限和不受限汇聚节点移动性都进行了研究。文献提出了一种使用约束路径的汇聚点规划贪婪算法（RP-CP），主要解决TR上汇聚节点移动性受限问题。为每个TR边分配一个权重，它等于根节点位于上端（指向树根的那一端）的子树中的源数目。根据树边的权重，对其进行递减排序。使用约束路径的汇聚点规划在不生成循环的前提下，贪婪地将具有最大权重的边，添加到边集W（最初是空集）中，使得W中边的总长度不超过L/2。下一个未选边的一部分将包含在W中，以确保其边长总和恰好为L/2。最终的W是一棵连通子树，且W中的节点是RP。汇聚节点按照预先确定的次序遍历W，导致访问路径长度恰好为L。文献证明，当汇聚节点路径在TR上受限时，W预先确定的访问路径是一种最优的访问路径。

文献提出了一种贪婪的启发式算法（RP-UG，采用基于效用的贪婪启发式汇聚点规划），主要用于移动自由的汇聚节点。RP-UG算法在TR中添加了虚拟节点，使得每条树边不超过预定义值L₀。该算法是以迭代形式实现的。在每次迭代中，将TR中具有最大效用的节点包含在RP列表中（该列表最初仅包含BS）。RP的效用定义为通过在汇聚节点访问路径上添加节点后节省的网络能量与访问路径增加的长度之比。RP访问路径长度可采用TSP算法进行计算。增加节点会导致列表中RP的效用发生变化。所有效用变成0的RP立即会从列表中删除。如果达到最大访问路径，或者所有源节点都包含在列表中，则RP-UG算法终止。否则，启动新迭代，以寻找更多的RP。通过调整L₀值，算法可以实现解决方案质量与计算复杂性之间的理想折中。

Steiner最小树（Steiner Minimum Tree，SMT）（Hwang et al.，1992）是一棵具有最短长度、连接给定点集的树。它与MST的区别在于它可能包含称为Steiner点的额外中间点，主要用于缩短树的长度。针对欧几里得Steiner问题，每个Steiner点必须具有3个夹角为2π/3的入射边。图6-7给出了一种SMT。在这种树中，圆形节点是给定点，方形节点是Steiner点。一般而言，SMT构建是NP完全问题，在实践中常用启发式算法。由于SMT总长度最短，当使用报告树来选择RP时，它会导致指向汇聚节点的数据分发总能耗最优，该最优值也可用作数据源的最优TSP访问路径下限。

图6-7 Steiner最小树（SMT）

根据上面的分析，作者在参考文献（Xing et al.，2008）中，针对可变轨迹，提出了一种基于SMT的汇聚点设计算法，假定节点密集分布，源位置已知，汇聚节点移动自由。RD-VT的原理是使用SMT作为报告树，且将RP限制在SMT节点范围内，使得RP形成一棵子树，且汇聚节点访问RP的路径长度不超过L，而SMT剩余边的总长度最小。在RD-VT中，数据源的SMT使用任意数据源作为根节点进行构建。以预定次序访问SMT时距离可达L/2，受访树节点可以充当RP。在下一棵树边上，可以将树访问路径长度递归扩展到L和TSP访问路径长度之差的一半，直至所选RP的TSP访问路径充分接近L为止。最后子树上的预定树访问路径定义为汇聚节点访问路径，源沿着SMT向RP发送数据。图6-7给出了根据RD-VT计算出来的汇聚节点访问路径。在该图中，白色圆代表数据源，黑色圆代表SMT的根。

3.使用分簇来选择RP

通过整合多种现有算法，参考文献（Rao and Biswas，2008）提出了一种基于移动汇聚节点的通用数据采集框架。在该框架中，构建了一个最小k跳支配集。支配集中的所有节点称为导航代理（Navigation Agent，NA）。两个相邻NA之间至少相距k+1跳，最多相距2k+1跳。通过调整参数k，框架从直接接触数据采集，通过基于汇聚点的数据采集，迁移到基于传统静态汇聚节点的数据采集。

每个NA构造一个具有最少跳数的树，根节点为自身，然后扩展到2k+1跳数的深度。在树构建过程中，它识别邻近NA，同时构建指向它们的最短路径。沿着最优路径的节点称为中间导航者（Intermediate Navigator，IN）。它们可用于引导移动汇聚节点在RP之间移动。根节点为NA的树将用于后续数据分发。汇聚点和IN一起构成一个连通覆盖图。可采用分布式蚁群优化TSP算法（Bonabeau et al.，1999）沿着覆盖图，为汇聚节点寻找NA的TSP访问路径。当找到TSP访问路径后，NA知道访问路径中的下一个NA。

每个NA定期发送问候消息。汇聚节点从任意位置开始移动，试图通过监听问候消息，找到一个本地NA。一旦找到第一个NA，则它根据接收信号的到达方向（Direction of Arrival，DOA），向NA移动。之后，它同样根据那些节点信号的DOA绕过IN，开始沿着NA的TSP访问路线前进。DOA的使用支持方案在无任何位置信息的情况下开展工作。

NA的单跳邻居称为指定网关（Designated Gateway，DG）。与汇聚节点访问路径不相邻的源，使用在IN节点识别过程中构建的、以其所在NA为根节点的树，向根节点发送数据。在向根传送数据的过程中，数据在最近DG处停止发送，并将数据缓存在该DG处。从这个意义上讲，DG实际上就是RP。在DG而不是在NA上缓存数据的好处是双重的。它节省了消息传输成本，因而通过缩短一跳数据通信路径降低了能耗；它避免了在NA处大量累积存储负荷。虽然汇聚节点有自己的TSP访问路径，但是它从遇到的NA及其DG处获取数据。

从上面的描述，我们可以看出，通过调整k值，可以实现数据采集延迟和能量消耗达到理想的平衡状态。当k=1时，汇聚节点访问每个节点的通信范围，因而框架变成了一种直接接触数据采集方案。当k=k_max（显而易见，k_max就是网络规模n）时，网络中仅存在一个NA，它可以支配其他所有网络节点。在这种情况下，一旦汇聚节点到达唯一的NA，它停止移动，从而演变为静态汇聚节点场景。