关于无线传感器网络数据压缩研究综述

脑图暂时地址：https://twilight-fanyi.gitee.io/mind-map/

1. 介绍

近年来，随着电子设备的不断发展，大家可能都意识到了自己身边都多了一些可以联网的智能电子设备，智慧农业，智慧交通等也不断地发展，应用到相应地场景中；有关无线传感器网络的研究也越来越多，越来越多的人也逐渐意识到无线传感器网络的无限适用性。例如，传感器网络可用于环境监测、生境检测、结构检测、设备诊断、灾害管理和应急响应等情况下收集数据。

但是无线传感器网络（WSNs）在应用的时候有一些资源的限制：有限的电源供应、通信带宽、处理速度和内存空间。最大限度地利用这些资源的一种可能的方法是对传感器是数据进行数据压缩。

通常情况下，处理数据比在无线介质中传输数据消耗的能量要少很多，因此在传输数据前采用数据压缩可以有效的降低传感器节点的总功耗。然而，现有的大部分压缩算法对于处理能力非常弱的传感器节点实在是过于庞大，以及每个传感器节点都受到了电力等资源的限制。所以，怎么在传感器节点这种资源限制非常大的情况下并设计我们的压缩算法是最主要的问题。

2. 分析能量在无线介质中的能量消耗

从功耗上看，无线传感器节点的运行可分为 传感、处理、传输三部分。在这三种操作中，已知能耗最大的任务是数据传输，每个传感器节点约 80% 的功耗用于数据传输。

因此，如果我们能通过数据压缩使数据的大小最小化，就会减少传输功率。另一方面，通过数据压缩，将需要更强大的处理能力来执行压缩算法。 为了减少的总功耗，必须减少传输和处理的总功耗。将 “a” 位的数据字符串压缩为 “b” 位的数据字符串所消耗的功耗，其中 a>b 。

实验① 发送数据所消耗的能量实验

这个实验室通过执行一个简单的32位加法指令，发送1位来采集功耗数据。

结果表明，发送一个 bit 的数据大约消耗 0.4µJ 的能量，执行一条加法指令只消耗 0.86nJ 的能量。通过无线电媒体传输一个 bit 的功耗至少是执行一个额外指令的 480倍。

所以如果通过压缩操作从原始数据位串中删除一个以上的位（相当于 480条 加法指令），将减少传感器节点的总功耗。

实验② 文本及网页数据应用各种无损数据压缩的总功耗

这个实验测试的压缩算法有 bzip2 (BWT 算法), compress (LZE 算法), LZO (LZ77), PPMd (PPM) 和 zlib (LZ77).

上表显示了各个算法删除一个 bit 所需的指令数。每个数据压缩算法的指令数量都远远小于 480条 指令，因此当这些算法被应用时，预计将比简单地传输一个数据串消耗更少的总能量。

实验结果表明，对于大多数压缩算法，在传输数据前压缩数据可以减少总功耗。然而在某些情况下，应用数据压缩会增加总功耗，这是由于在压缩执行期间访问内存。访问内存在能量消耗方面是昂贵的。

结论

在无线介质中传输数据前采用数据压缩是降低能耗的有效方法。然而，选择一种数据压缩算法是至关重要的，它在执行期间需要较少的内存访问。

3. 数据压缩技术

① 排序编码

作为数据漏斗路由的一部分，引入了按顺序编码的数据压缩方案。压缩方案如下：

① 将数据从感兴趣区域（Interested region）中的传感器节点传递到收集器节点，如图一所示。在数据漏斗路由中，一些传感器节点作为数据汇聚节点工作。

例如:节点 A、节点 B、节点 D 为数据汇聚节点。在汇聚节点上，将其他节点收集到的传感数据进行组合，并将聚合后的数据发送给其父节点。在图 3 的节点 D 处，节点 E 收集的数据与节点 D 本身收集的数据相结合。

② 然后，将聚合的数据传输到节点 B。

在该算法中，当在一个聚合节点上合并数据时，会删除一些数据。为了在聚合数据中包含丢失数据的信息，利用了数据包的顺序。

例如 N1、N2、N3、N4 四个节点把数据发送到聚合节点（Na）。每个节点的数据取值为 0 ~ 5 之间的任意整数。如果我们决定放弃 N4 的数据，并通过从其他3 个节点(N1、N2 和 N3)订购数据包来表示 N4 的数据，那么就有 3 个节点!= 6 种可能的排序。因此，通过使用三个数据包的排列，可以将 N4 的数据值包含在一个聚合包中，而不实际包含 N4 的数据包。排列与数据值的可能组合如下图所示。

结论

1. 优点 该数据压缩方法压缩比比较低，算法简单，有可能应用在无线传感器网络上。
2. 缺陷 使用该方案的一个困难是，由于没有有效的算法将排列映射到数据值，因此它需要一个映射表。随着聚集的传感器节点的增加，表的大小呈指数增长。

② 流水线式网络压缩

这里讨论了流水线式网络压缩方案。其基本思想是用高数据传输延迟换取低传输能耗。收集到的传感器数据在聚合节点的缓冲区中存储一段时间。在此期间，将数据包合并成一个数据包，消除数据包中的冗余，使数据传输最小化。

结论

1. 优点： 这种简单压缩方案的一个优点是，可以将共享前缀系统用于节点 id 和时间戳。通过这样做，可以实现更多的数据压缩。 数据压缩的效率取决于共享前缀的长度。如果我们可以设置一个很长的共享前缀，并且测量值具有共性，压缩比就会增加。
2. 缺陷： 然而，测量的传感器值没有相似之处。即使设置一个很长的共享前缀，也会降低网络内流水线压缩的效率。 此外，如果我们要合并大量的数据包，那么就需要一个大的数据缓冲区来临时存储这些数据包。由于传感器节点的内存空间有限，因此没有足够的缓冲区空间可用。

③ 低复杂度视频压缩

这里引入了低复杂度的视频压缩方案。由于目前的视频编码技术大多是利用运动估计和补偿来设计的，因此需要较高的计算能力，而传感器节点通常不具备这种能力。因此，该方法是基于块变化检测算法和 JPEG 数据压缩的。

上图给出了图像数据处理流程的框图。该算法是专门针对无线视频监控系统而设计的。该方法将每个视频帧划分为小块，每个块包含 8 个 8(64)像素。为了降低计算复杂度，在每一帧中只考虑块的子集(本例中为所有的白色块)。此外，在每个块中，将检查像素子集(分配的像素数目)的变化，如图 7 所示。分配给像素的数字表示像素的重要性(1 =最重要，3 =最不重要)。

结论

实验结果表明，该算法处理后的图像质量与MPEG-2 处理后的图像质量相当，同时实现了一定的节能。

④ 分布式压缩

分布式压缩方案背后的基本思想是使用一个边信息来编码一个源信息。

例如，存在两个源 (X 和 Y)，如图 4 所示。它们是相关的离散字母独立同分布的。由于在传感器网络中，传感器节点密集分布在一个传感器领域，因此这种关联条件很容易满足。然后，X 可以按照其条件熵的理论速率 H(X|Y)压缩，而编码器 1 不访问 Y。条件熵可以表示为

然后，解码器在陪集中选择一个与 Y 发送的码向量值最接近的码向量。

下面是分布式压缩的一个简单示例。有两个(X 和 Y) 3 位数据集。X 和 Y 之间的汉明距离不大于 1 位。如果编码器 2 和解码器都知道 Y, X 可以压缩为 2 位。那么如果 Y 只有解码器知道，那么 X 的压缩率会发生什么变化呢?

在分布式压缩方案中，由于解码器知道 Y 和 X 与Y 的距离只有 1 个汉明距离，所以区分 X=111 和 X=000是不有效的。同理，X=001 和 110,X=010 和 101,X=011和 110 不需要区分。这两个 X 值的集合被分组为 4 个成本，并分配 4 个不同的二进制索引号:

如果 X=010, Y=110，解码器接收到的 Y=110 是来自Y 的边信息，X=10 是来自 X 的部分信息。那么在解码器处，由于 110 与 110 的汉明距离为 2，所以在coset 2 中选择 X=010。无论 X 是否知道 Y, X 仍然可以将 3 位的信息压缩成 2 位。

结论

分布式压缩方案不仅可以应用于如上述例子所示的离散源，也可以应用于连续源。此外，它可以用于无损和有损压缩方案。 例如，一个 8 级量化器可以形成 4 个伴随集。值得注意的是，每个陪集中的两个编码向量被分组，以便它们彼此之间可以有最大可能的距离。

4. 总结

近年来，人们对无线传感器网络的应用领域进行了广泛的讨论。未来随着技术的发展，无线传感器网络的应用领域将比现在更加广泛。人们将比现在更容易得到它们。然而，在这些日子到来之际，传感器网络的实际应用仍然存在许多障碍需要克服。其中一个障碍是无线节点资源有限。

本文已处理五种不同类型的数据压缩方案：排序编码、流水线网络压缩、JPEG200、低复杂度视频压缩、分布式压缩。尽管这些压缩方案仍处于开发阶段，但实验结果表明，它们的压缩率和功率降低方式相当令人深刻。它们是无线传感器节点资源约束的一种可行方法。

引用

[1] Kimura N , Latifi S . A survey on data compression in wireless sensor networks[C]// International Conference on Information Technology: Coding and Computing (ITCC’05) - Volume II. IEEE, 2005.