面向边缘云环境的可聚合广义重复数据删除技术研究

《IEICE Transactions on Communications》：Aggregable generalized deduplication

本文针对边缘云环境中物联网设备上传海量数据时存在的计算复杂度高和冗余消除不足的问题，提出了可聚合广义重复数据删除（AGD）新方法。研究人员通过部分提取压缩流数据、构建共享字典和个体字典等关键技术，实现了无需解码的GD流聚合。结果表明AGD显著降低了边缘节点的计算复杂度，同时压缩率优于传统方法，为物联网数据高效传输提供了创新解决方案。

　　

在物联网（IoT）技术飞速发展的今天，数以亿计的传感器、智能仪表等设备每时每刻都在产生海量数据。这些数据通过边缘节点上传至云平台进行处理和存储，形成了典型的边缘-云环境架构。然而，这种架构面临两个突出挑战：一是海量数据传输对网络带宽的巨大压力；二是边缘节点资源有限，难以承担复杂的计算任务。

为了缓解这些挑战，数据压缩技术成为关键解决方案。广义重复数据删除（GD）作为一种新兴的压缩技术，通过编码理论方法将数据块分割为基值（base）和偏差（deviation），能够有效消除数据中的冗余信息。与传统去重技术相比，GD具有更高的压缩效率。然而，在边缘云环境中应用GD面临一个棘手问题：边缘节点需要先解码来自各个叶子节点的GD压缩流，聚合原始数据后重新编码为单个GD压缩流。这一“解码-聚合-重新编码”过程涉及底层线性码的复杂数学运算，计算复杂度极高，严重制约了GD在资源受限的边缘节点上的实际应用。

针对这一瓶颈问题，Riki AOSHIMA等研究人员在《IEICE Transactions on Communications》上发表了题为“Aggregable Generalized Deduplication”的研究论文，提出了一种创新的可聚合广义重复数据删除（AGD）方法。该方法使边缘节点能够直接将多个GD压缩数据流聚合为单个AGD流，无需进行复杂的解码和重新编码操作。

研究人员采用了三个关键技术方法：一是从压缩流中部分提取数据，避免完全解码操作；二是构建共享字典消除跨叶子节点的冗余，同时为每个叶子节点创建个体字典消除节点内冗余；三是设计用于共享字典和个体字典的嵌套分隔符。研究通过理论复杂度分析和基于里德-所罗门码（Reed-Solomon code）的计算机仿真，评估了AGD的性能。

计算复杂度分析

理论研究显示，传统方法的计算复杂度为(2a+2b+4c)T，而AGD₀（无个体字典的AGD）和AGD的计算复杂度分别为(a+b+4c)T和(a+b+6c)T。虽然AGD需要更多的字典查找操作，但关键的编解码操作（a和b）远多于查找操作（c）。数值估计表明，在典型参数下（如n=63，k=57），传统方法需要约8k(n-k)+4次查找表（LUT）查找，而AGD仅需4k(n-k)+6次，计算效率显著提升。

压缩率性能

仿真实验使用里德-所罗门码（RS）作为GD的底层线性码，参数包括(15,11)、(31,26)和(63,57)，数据来源于真实物联网数据集。结果表明，AGD₀与传统方法压缩率相同，但均优于分离的GD流。更重要的是，AGD（含个体字典）在所有参数设置下均优于AGD₀。以RS(31,26)为例，AGD₀比分离GD流压缩率至少提高5.40%，而AGD又比AGD₀至少提高1.34%。在共享字典大小为32768、个体字典大小为32时，AGD相比分离GD流压缩率最大提升达9.94%。

内存使用分析

传统方法在边缘节点的总内存估计为nM_leaf+M_ord，AGD₀为nM_leaf+M_all，而AGD为nM_leaf+M_all+nM_idv。AGD虽然使用了更多字典，但通过合理的字典大小管理，可在压缩率和内存使用间取得平衡。

本研究提出的AGD方法成功解决了边缘云环境中GD流聚合的高计算复杂度问题。通过理论分析和实验验证，AGD不仅显著降低了边缘节点的计算负担，还提高了压缩效率，特别适用于资源受限的物联网环境。该方法为边缘计算中的数据压缩传输提供了创新解决方案，对促进物联网大规模应用具有重要意义。未来工作可进一步优化字典管理策略，探索更适合物联网数据特征的线性码设计，以提升AGD在多样化应用场景中的适应性。