传感器网络中基于一致性容差的聚合技术研究

程文静

摘 要 在传感器网络中，通信成本占据了主导地位。因此，如何在满足数据质量的前提下尽可能地减少数据传输是降低能耗的有效途径。本文介绍了一种利用用户对传感器读数变化的容忍度来减少“微变化”数据的传输，还可以在并非所有传感器读数都能在给定的时间限制内在网络中传播时保证一定的数据质量。

关键词 传感器网络;时间一致性;网络聚合

1网络聚合模型

传感器网络中的查询是连续的，会周期性地产生新的结果。初始时，基站接收一个查询，然后转发到最近的传感器节点。此节点将负责将查询分发到网络上并收集结果。TAG[1]（TinyDB的聚合服务）在普通的SQL查询中引入了新的子句EPOCH DURATION i。参数i是时间周期，它指定了用户需要的新结果的到达速率。也就是说，对间隔每一个时间周期i，用户都期望网络对提出的连续查询产生一个新的答案。而在本文介绍的基于时间的一致性容差的网络聚合方案中，引入了VALUES WITHIN tct子句来表示一致性容忍度。

执行网络聚合的方式取决于查询的属性和聚合谓词。具体来说，group by查询中的属性列表将同一个属性值的查询结果分为一组。这些组的数目等于属性列表不同值的个数。来自两个不同传感器的两个读数只有属于同一组时才会被聚合。聚合函数决定了部分聚合的结构和部分聚合过程。例如，对于聚合函数SUM来说，传感器生成的部分聚合只包括通过该传感器转发的所有读数的总和。但是，如果聚合函数为AVERAGE，则每个路由传感器生成的部分聚合包括所有的读数之和读数的个数。最终，根传感器将使用总和和个数来计算每个组的平均值，然后将其转发到基站以进行进一步的处理和转发。

对于路由，我们使用一般的定向扩散方式，其目的是构建一棵路由树，并在此过程中给其中每个传感器指定一个父节点。例如传感器c希望把一条消息广播给全网，那么它先把这条消息发送给它的父节点，然后再继续向下传播。为了构建路由树，需要为每个传感器i分配一个级别Li和一个父节点Pi。在初始状态下对于所有节点来说，Li=∞，Pi=0。启动查询的根节点会将自己的级别Lroot设置为0。各个节点通过交换查询消息以构建路由树。这样的消息头包含两个字段：ids和Ls。ids是发送消息的源节点的标识符，Ls是该源节点的级别值（即Li）。当某个子节点接收到查询消息且其当前级别为∞时，它会将收听到的这个节点设置为其父节点，并将自己的级别设置为Ls+1。该过程将持续下去，直到网络中的每个节点都收到查询消息的副本，并被分配一个级别和一个父节点。

对于到达根节点只有单一路径的路由树来说，在节点上如何实现同步传输，对于高效的网络聚合至关重要。父节点必须持续等待，直到听到从其所有子节点报告的读数后才能报告自己的读数。因此，父节点p能够将其子节点报告的部分聚集结果与其自身的读数相结合。然后节点p可以发送一条消息，包含了在根植于p的子树上采样的所有值的部分聚合结果。

TAG中的同步是通过让父节点在报告自己的读数之前等待一定的时间间隔来完成的。具体来说，TAG将一个查询周期细分为较短的时间片，时间片数等于路由树的最大深度d，每个时间片的长度为（EPOCH DURATION）/d，其中EPOCH DURATION为一个周期的时长。在一个时间片内，父节点将处于活动状态，并从其子节点接收消息。在下一个时间片内，其子节点将处于空闲状态，而父节点仍处于活动状态，并向其上一级节点传输部分聚合的结果。父传感器将在随后的时间片内（即当它完成接收和传输其子树中的部分聚合数据后）会变进入空闲状态。

本文介绍的方案可以和任何同步方法结合工作。在本文中，我们将使用TAG方法实现同步。此方法的优点是保证了查询结果在每一个时间片内都能被传递，并且确保了每一个传感器消耗最少能量。能够实现消耗的能量最小化是因为每一个传感器在一个周期中只需要在两个时间片内处于活跃状态：一是当它从其孩子接收信息时，二是当它向上一级节点传送部分结果时，在其他时刻，该节点都处于空闲状态。

2基于一致性容差的网络聚合方案

虽然现有技术在一定程度上实现了数据聚合，但是在大型的传感器网络中，大量节点周期性的发送数据仍然是一个巨大的能量消耗，会缩短传感器网络的寿命。但是在有些应用中，用户并不需要掌握每一个传感器每一次的具体读数，只有当读数变化超出一定的容忍范围时，才需要获取这个变化的数据。基于这样的情况，可以对常规的聚合方式进行改进，加入一个基于时间周期的数据一致性容差值来决定哪些数据需要经过路由树转发，以及如何合并或接收此转发数据。方案在查询规范中增加了一条新的SQL语句：VALUES WITHIN tct。参数tct被用户用来指定查询的时间一致性容差，它的值表示用户能够容忍的传感器值读数变化的程度。例如，如果用户指定tct=10%，则只有在当前传感器读数和上一次报告的有效读数相差在10%以上，传感器网络才会向其父节点报告。

3实验

图1显示了在每一个查询周期内两个系统之间的比较，其中一个系统采用了时间一致性容差方案，另一个没有。假设查询的目的是获取一栋楼中所有房间的总光照，查询每30秒进行一次，并将结果按楼层进行分组，在此设置tct的值为10%，即传感器只有在当前读数和上一次报告的读数之间差值在10%以上才需要向父节点再次报告读数。该查询语句如下：

在下圖中，圆表示节点，箭头表示从子节点到父节点的数据流。沿着连接线的表表示从子节点传送到父节点的值。连接到每个节点的方框表示节点上的当前状态。此当前状态包括其上一次报告的读数、其当前采样获取的读数和表示其子节点上次报告的数据的聚合结果的表组成。每个表下的成本号表示的是将此表从子节点发送到父节点的成本。成本被简单的表示为表的大小，因为只是用它来说明相对成本。例如，成本为4的表a是成本为2的表b的两倍大，因此传递a表数据的消息是传递b表消息的两倍大，从而导致两倍的传输成本。

图1表示了一个系统执行上面查詢的一个查询周期，首先忽略掉阴影标记，该图表示的是没有使用一致性容差方案的执行情况。其中每个读数都是从子节点发送到父节点，发送每条消息的成本表示在了每个节点的左上角。在这个网络中，向路由树上发送读数的总成本是14，或者说所有消息的大小之和是14。

考虑阴影标记的情况是使用了时间一致性容差方案。阴影部分表示的是不需要发送的消息部分，发送每条消息的成本由斜体字标识在了每个节点的右上角。例如，当节点4发送数据时，它首先检查新读数和旧数据的差值比例。由于新旧读数相差不超过10%，因此不会向其父节点发送任何内容。在下一个时间片中，节点2和节点3将其读数与上一个读数进行比较。由于两者相差超过10%，他们都将向父节点发送新的读数，并替换旧的读数。然后，节点1收集向它发来的所有读数，并检查自己的读数，结果发现与其以前的读数相差不超过10%。但是，由于节点1和节点2采样的数据属于同一个组，该组中节点2的值已经被发送到上一级。在这种情况下，为了确保该组中聚合值SUM的正确性，节点1必须将其新的读数累加到节点2的读数中。然后，节点1将所有这些新信息发送到基站以向用户报告。因此，第二个方案的总消耗是8。

在这个例子中可以看到，即使在只有四个节点的情况下，也可以节省大量的能量。对节点读数设置的10%的容差消除了来自节点4的整个传输。由于传感器网络的性质，能够在数据传输上节省大量的总成本。此外，对于节点4的所有上级节点1和3来说，由于它们都保存了节点4的旧值，同样不必再向上发送第3组的值。因此他们需要传输的信息量减少了，也节省了能源。

4结束语

以上的实验充分说明，在网络聚合中恰当地使用时间一致性容差方案可以有效地减少网络的传输成本，同时还可以在用户可以容忍的误差范围内尽可能地保证数据质量。由于在传感器网络中数据传输是能量消耗的最主要因素，因此该方案在节省网络能耗和降低数据质量这两者之间提供了一个较好的折中方案。

参考文献

[1] Madden S， Franklin M J， Hellerstein J M，et al. TAG：a Tiny AGgregation service for ad-hoc sensor networks[J].Acm Sigops Operating Systems Review，2002，36（S1）：131-146.