转发 | 轻翻那些永垂不朽的诗篇 第六章 无线传感器网络数据压缩（全文完）
前期回顾
第一章：数据压缩理论缘起——摩斯密码开创编码领域先河，信息熵用数学语言阐明了概率与信息冗余度的关系
第二章：Huffman码——用生活中的烹饪视角解析Huffman编码过程
第三章：小波系数图像压缩编码——小波系数的各类编码方案大比拼第四章：
第五章：计算机视觉中的女神 —— Lenna——带你走进女神
本期看点
无线传感器网络数据压缩——实践是检验真理的唯一标准
第六章 无线传感器网络数据压缩
近年来，随着电子设备的不断发展，大家可能都意识到了自己身边都多了一些可以联网的智能电子设备，智慧农业，智慧交通等也不断地发展，应用到相应地场景中；有关无线传感器网络的研究也越来越多，越来越多的人也逐渐意识到无线传感器网络的无限适用性。例如，传感器网络可用于环境监测、生境检测、结构检测、设备诊断、灾害管理和应急响应等情况下收集数据。
但是无线传感器网络（WSNs）在应用的时候有一些资源的限制：有限的电源供应、通信带宽、处理速度和内存空间。最大限度地利用这些资源的一种可能的方法是对传感器的数据进行数据压缩。
通常情况下，处理数据比在无线介质中传输数据消耗的能量要少很多，因此在传输数据前采用数据压缩可以有效的降低传感器节点的总功耗。++然而，现有的大部分压缩算法对于处理能力非常弱的传感器节点实在是过于庞大，以及每个传感器节点都受到了电力等资源的限制。所以，怎么在传感器节点这种资源限制非常大的情况下并设计我们的压缩算法是最主要的问题。
6.1 分析能量在无线介质中的能量消耗
从功耗上看，无线传感器节点的运行可分为 传感、处理和传输三部分。在这三种操作中，已知能耗最大的任务是数据传输。每个传感器节点约 80% 的功耗用于数据传输。
因此，如果我们能通过数据压缩使数据的大小最小化，就会减少传输功率。然而，另一方面，通过数据压缩，将需要更强大的处理能力来执行压缩算法。为了减少的总功耗，必须减少传输和处理的总功耗。将 “a” 位的数据字符串压缩为 “b” 位的数据字符串所消耗的功耗，其中 a>b 。
6.1.1 实验① 发送数据所消耗的能量实验
这个实验室通过执行一个简单的32位加法指令，发送1位来采集功耗数据。
结果表明，发送 1个 bit 的数据大约消耗 0.4µJ 的能量，执行一条加法指令只想消耗 0.86nJ 的能量。通过无线电媒体传输一个 bit 的功耗至少是执行一个额外指令的 480倍。
所以如果通过压缩操作从原始数据位串中删除一个以上的位（相当于 480条 加法指令），将减少传感器节点的总功耗。
6.1.2 实验② 文本及网页数据应用各种无损数据压缩的总功耗
这个实验测试的压缩算法有 bzip2 (BWT 算法), compress (LZE 算法), LZO (LZ77), PPMd (PPM) 和 zlib (LZ77).
实验结果表明，对于大多数压缩算法，在传输数据前压缩数据可以减少总功耗。然而在某些情况下，应用数据压缩会增加总功耗，这是由于在压缩执行期间访问内存。访问内存在能量消耗方面是昂贵的。
实验结论：在无线介质中传输数据前采用数据压缩是降低能耗的有效方法。然而，选择一种数据压缩算法是至关重要的，它在执行期间需要较少的内存访问。
6.2 数据压缩技术
6.2.1 ① 排序编码
作为数据漏斗路由的一部分，引入了按顺序编码的数据压缩方案。压缩方案如下：
将数据从感兴趣区域（Interested region）中的传感器节点传递到收集器节点，如图一所示。在数据漏斗路由中，一些传感器节点作为数据汇聚节点工作。
例如:节点 A、节点 B、节点 D 为数据汇聚节点。在汇聚节点上，将其他节点收集到的传感数据进行组合，并将聚合后的数据发送给其父节点。在图 3 的节点 D 处，节点 E 收集的数据与节点 D 本身收集的数据相结合。
然后，将聚合的数据传输到节点 B
结论：
- 该数据压缩方法压缩比比较低，算法简单，有可能应用在无线传感器网络上。
- 使用该方案的一个困难是，由于没有有效的算法将排列映射到数据值，因此它需要一个映射表。随着聚集的传感器节点的增加，表的大小呈指数增长。
6.2.2 ② 流水线式网络压缩
这里讨论了流水线式网络压缩方案。其基本思想是用高数据传输延迟换取低传输能耗。收集到的传感器数据在聚合节点的缓冲区中存储一段时间。在此期间，将数据包合并成一个数据包，消除数据包中的冗余，使数据传输最小化。
优点：
这种简单压缩方案的一个优点是，可以将共享前缀系统用于节点 id 和时间戳。通过这样做，可以实现更多的数据压缩。
数据压缩的效率取决于共享前缀的长度。如果我们可以设置一个很长的共享前缀，并且测量值具有共性，压缩比就会增加。
缺陷：
然而，测量的传感器值没有相似之处。即使设置一个很长的共享前缀，也会降低网络内流水线压缩的效率。
此外，如果我们要合并大量的数据包，那么就需要一个大的数据缓冲区来临时存储这些数据包。由于传感器节点的内存空间有限，因此没有足够的缓冲区空间可用。
6.2.3 ③ 低复杂度视频压缩
这里引入了低复杂度的视频压缩方案。由于目前的视频编码技术大多是利用运动估计和补偿来设计的，因此需要较高的计算能力，而传感器节点通常不具备这种能力。因此，该方法是基于块变化检测算法和 JPEG 数据压缩的。
上图给出了图像数据处理流程的框图。该算法是专门针对无线视频监控系统而设计的。该方法将每个视频帧划分为小块，每个块包含 8 个 8(64)像素。为了降低计算复杂度，在每一帧中只考虑块的子集(本例中为所有的白色块)。此外，在每个块中，将检查像素子集(分配的像素数目)的变化，如图 7 所示。分配给像素的数字表示像素的重要性(1 =最重要，3 =最不重要)。
实验结果表明，该算法处理后的图像质量与MPEG-2 处理后的图像质量相当，同时实现了一定的节能。
6.2.4 ④ 分布式压缩
分布式压缩方案背后的基本思想是使用一个边信息来编码一个源信息。然后，解码器在陪集中选择一个与 Y 发送的码向量值最接近的码向量。
分布式压缩方案不仅可以应用于如上述例子所示的离散源，也可以应用于连续源。此外，它可以用于无损和有损压缩方案。
6.3 总结
近年来，人们对无线传感器网络的应用领域进行了广泛的讨论。未来随着技术的发展，无线传感器网络的应用领域将比现在更加广泛。人们将比现在更容易得到它们。然而，在这些日子到来之际，传感器网络的实际应用仍然存在许多障碍需要克服。其中一个障碍是无线节点资源有限。
本文介绍了5种不同类型的数据压缩方案：排序编码、流水线网络压缩、JPEG2000、低复杂度视频压缩和分布式压缩。尽管这些压缩方案仍处于开发阶段，但实验结果表明，它们的压缩率和功率降低方式相当令人深刻。它们是无线传感器节点资源约束的一种可行方法。
全文缩略语汇总
| 缩写 | 英文 | 中文 |
| AC | Alternating Current | 交流 |
| ASWDR | Adaptively Scanned Wavelet Difference Reduction | 自适应扫描小波差约简 |
| ATM | Asynchronous Transfer Mode | 异步传输模式 |
| CR | Compression Ratio | 压缩比 |
| CREW | Compression with Reversible Embedded Wavelets | 可逆嵌入小波压缩 |
| DC | Direct Current | 直流 |
| DCT | Discrete Cosine Transform | 离散余弦变换 |
| DWT | Discrete Wavelet Transform | 离散小波变换 |
| EBCOT | Embedded Block Coding with Optimised Truncation | 优化截断的嵌入式块 |
| EPWIC | Embedded Predictive Wavelet Image Coder | 嵌入式预测小波图像 |
| EZW | Embedded Zerotree Wavelets | 嵌入式零树小波 |
| GW | Geometric Wavelet | 几何小波 |
| HVS | Human Visual System | 人类视觉系统 |
| JPEG | Joint Photographic Experts Group | 联合图像专家组 |
| LIP | List of Insignificant Pixels | 不重要像素列表 |
| LIS | List of Insignificant Sets | 不重要集合列表 |
| LSP | List of Significant Pixels | 重要像素列表 |
| MSE | Mean Square Error | 均方误差 |
| PSNR | Peak SignaN-to-noise Ratio | 峰值信噪比 |
| ROI | Region Of Interest | 感兴趣区域 |
| SFQ | Space Frequency Quantization | 空频量化 |
| SPECK | Set Partitioned Embedded bloCK | 设置分区嵌入式块 |
| SPIHT | SetPartitioning in Hierarchical Trees | 多级树集合分裂 |
| SR | Stack Run | 堆栈运行 |
| VQ | Vector Quantization | 向量量化 |
| WDR | Wavelet Difference Reduction | 小波差约简 |
| WMSN | Wireless Multimedia Sensor Network | 无线多媒体传感器网络 |
| WSN | Wireless Sensor Networks | 无线传感器网络 |
前期回顾
第一章：数据压缩理论缘起——摩斯密码开创编码领域先河，信息熵用数学语言阐明了概率与信息冗余度的关系
第二章：Huffman码——用生活中的烹饪视角解析Huffman编码过程
后期预告
第四章 第二代图片压缩技术——8大压缩算法的大比拼
第五章：计算机视觉中的女神 —— Lenna——带你走进女神
第六章：无线传感器网络数据压缩——实践是检验真理的唯一标准
ELT.ZIP是谁？
ELT<=>Elite(精英)，.ZIP为压缩格式，ELT.ZIP即压缩精英。
成员：
上海工程技术大学大二在校生
合肥师范学院大二在校生
清华大学大二在校生
成都信息工程大学大一在校生
黑龙江大学大一在校生
山东大学大三在校生
ELT.ZIP是来自6个地方的同学，在OpenHarmony成长计划啃论文俱乐部里，与来自华为、软通动力、润和软件、拓维信息、深开鸿等公司的高手一起，学习、研究、切磋操作系统技术…
技术DNA
数据压缩的历史
图片来源：https://visual.ly/community/Infographics/computers/history-data-compression
ELT.ZIP（III部压缩算法）技术地图
智慧场景
参考文献
[1] Vitter, Scott J . Design and analysis of dynamic Huffman codes[J]. Journal of the Acm, 1987, 34(4):825-845.
https://dl.acm.org/doi/10.1145/31846.42227
[2] Peng J , Kim C S , Kuo C C J . Technologies for 3D mesh compression: A survey[J]. Journal of Visual Communication & Image Representation, 2005, 16(6):688-733.
http://mcl.usc.edu/wp-content/uploads/2014/01/200503-Technologies-for-3D-triangular-mesh-compression-a-survey.pdf
[3] Holtz K . The evolution of lossless data compression techniques[C]// Wescon/93 Conference Record. IEEE, 1993.
https://ieeexplore.ieee.org/document/488424
[4] 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.
[5] Sudhakar R , Karthiga M R , Jayaraman S . Image compression using coding of wavelet coefficients–a survey[J]. A Survey”, ICGST-GVIP Journal, Volume (5), Issue, 2005(6):25-38.
https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.463.1615&rep=rep1&type=pdf
[6] Li W C , Ang L M , Seng K P . Survey of image compression algorithms in wireless sensor networks[C]// International Symposium on Information Technology. 2008.
[7] Hamming R W . Coding and information theory (2. ed.)[M]. DBLP, 1986.
https://dblp.org/rec/books/daglib/0068879.html
[8] 高锐智, 华成英. 汉字字形结构式压缩方法的研究和实现[J]. 计算机科学, 2003, 30(005):78-81.
https://www.jsjkx.com/CN/article/openArticlePDF.jsp?id=15270
[9] Zhang C N , Wu X . A hybrid approach of wavelet packet and directional decomposition for image compression[J]. Wiley Subscription Services, Inc. A Wiley Company, 2002, 12(2):51-55.
https://ieeexplore.ieee.org/document/808039
[10] Kunt, M, Ikonomopoulos, et al. Second-generation image-coding techniques[J]. Proceedings of the IEEE, 1985.
https://dl.acm.org/doi/abs/10.1145/248621.248622
写在最后：
OpenHarmony 成长计划—“啃论文俱乐部”（以下简称“啃论文俱乐部”）是在 2022年 1 月 11 日的一次日常活动中诞生的。截至 3 月 31 日，啃论文俱乐部已有 87 名师生和企业导师参与，目前共有十二个技术方向并行探索，每个方向都有专业的技术老师带领同学们通过啃综述论文制定技术地图，按“降龙十八掌”的学习方法编排技术开发内容，并通过专业推广培养高校开发者成为软件技术学术级人才。
啃论文俱乐部的宗旨是希望同学们在开源活动中得到软件技术能力提升、得到技术写作能力提升、得到讲解技术能力提升。大学一年级新生〇门槛参与，已有俱乐部来自多所高校的大一同学写出高居榜首的技术文章。
如今，搜索“啃论文”，人们不禁想到、而且看到的都是我们——OpenHarmony 成长计划—“啃论文俱乐部”的产出。
OpenHarmony开源与开发者成长计划—“啃论文俱乐部”学习资料合集
1）入门资料：啃论文可以有怎样的体验
https://docs.qq.com/slide/DY0RXWElBTVlHaXhi?u=4e311e072cbf4f93968e09c44294987d
2）操作办法：怎么从啃论文到开源提交以及深度技术文章输出https://docs.qq.com/slide/DY05kbGtsYVFmcUhU
3）企业/学校/老师/学生为什么要参与 & 啃论文俱乐部的运营办法https://docs.qq.com/slide/DY2JkS2ZEb2FWckhq
4）往期啃论文俱乐部同学分享会精彩回顾：
同学分享会No1.成长计划啃论文分享会纪要（2022/02/18） https://docs.qq.com/doc/DY2RZZmVNU2hTQlFY
同学分享会No.2 成长计划啃论文分享会纪要（2022/03/11） https://docs.qq.com/doc/DUkJ5c2NRd2FRZkhF
同学们分享会No.3 成长计划啃论文分享会纪要（2022/03/25）
https://docs.qq.com/doc/DUm5pUEF3ck1VcG92?u=4e311e072cbf4f93968e09c44294987d
现在，你是不是也热血沸腾，摩拳擦掌地准备加入这个俱乐部呢？当然欢迎啦！啃论文俱乐部向任何对开源技术感兴趣的大学生开发者敞开大门。
后续，我们会在服务中心公众号陆续分享一些 OpenHarmony 开源与开发者成长计划—“啃论文俱乐部”学习心得体会和总结资料。记得呼朋引伴来看哦。
扫码添加 OpenHarmony 高校小助手，加入“啃论文俱乐部”微信群