电力线窄带通信报文压缩算法研究

刘 萌 ，丁香乾 ，侯军伟 ，王 锐

(1.中国海洋大学 计算机科学系，山东 青岛266100；2.中国海洋大学 信息工程中心，山东 青岛266071)

电力线载波通信是利用已有的电力线路进行数据传输的一种通信方式，无需专门架设通信基础设施并且具有相当广泛的网络分布，因此，电力线载波通信是一种非常经济的通信方式。然而，由于电力线载波通信存在着一些技术难题，如传输信道间歇噪声大、阻抗随负载变化大、信号衰减大等问题[1]，使得目前电力线载波通信仅在自动抄表系统（AMRS）的应用上得到了比较好的发展。

自动抄表系统要求能够稳定准确地抄到每个表，然而由于电力网络的分布电容、分布电感、负载性质、负载阻抗值、噪声等都是动态的，而非恒定的，然而一个设计定型的系统产品,其调制/解调制式、工作频率、发送功率、信道参数、通信效果等通常都是不变的,这就导致了抄表系统不能保证在各种环境下都可以可靠地运行，因此产生了一系列技术难题[2]。

使用扩频通信技术来避免电力线的强干扰、强衰减等缺陷，然而扩频导致了通信速率的大大降低，这使得窄带通信的传输速率只是宽带的几百分之一，这在一定程度上限制了扩频通信的广泛应用[3]。

将数据压缩技术引入到电力抄表系统可以提高通信速率、降低误码率，从而使电力线载波抄表系统更加稳定。

1数据压缩原理

数据压缩实际上也是一种编码，如果压缩是有效的，那么编码后的数据比原始数据占用的存储空间小。数据压缩根据信息论的基本概念分为无损压缩和有损压缩，本文讨论的是无损压缩。数据之所以能被压缩是因为它存在某种规律或者结构，从信息论角度来看就是数据中存在冗余信息，而数据压缩就是要去除数据中的冗余信息。

关于数据压缩有很多算法，针对不同特点的数据选择不同的压缩算法从而达到最优的压缩效果。LZ77是一种通用的顺序数据压缩算法，它不需要知道数据本身的一些特性，对于任何数据都可以进行压缩[4]，思路简单，自从J.Ziv和 A.Lempel于1977年提出该算法之后很快得到了广泛应用。

1.1通用压缩算法LZ77

LZ77通过引入滑动窗口（sliding-window），在字符流上顺序滑动sliding-window，从而实现字符流的压缩。以图1中数据为例，LZ77算法将从左至右滑动slidingwindow对其进行压缩表示，sliding-window分为两个部分：search buffer（搜索缓冲区,大小为 7，编号从 0开始）和 look-ahead buffer（向前查找缓冲区，大小为 5），A=“abcbbacde”是滑动窗口滑过的字符串，B=“bbadeaa…”是等待被压缩的字符串。当前即将被压缩的位置为B中的第一个字符—b，算法将在search buffer里面搜索B中从该位置向后的最长匹配并将其用一个三元组(position，length，next symbol)简略表示(其中 position表示被压缩字符串在search buffer里面最长匹配的起始位置，length表示该匹配的长度，next symbol表示 look-ahead buffer中第一个不被匹配的字符)。那么，当前从b开始的“bbad”将被压缩表示为（1，3，d），然后滑动窗口向右滑过 4个字符，下一次压缩从e处开始，如图2所示。

该算法简单易行，有较高的执行效率，然而很容易发现它存在的一些问题。于是接下来的几年里出现了很多LZ77的改进算法，如不限制窗口长度的LZR算法、引入Huffman编码的LZH算法以及改进search buffer数据结构和三元组表示的LZSS算法[5]等。

1.2电力线通信报文压缩算法设计

针对电力线通信报文W，以下压缩方案来自于LZSS压缩算法思想：

(1)首先将报文W从左至右，每7 bit组成一个字节，字节的最高位置0，低7位来自W；

(2)如 果 W[i…j]=W[k…l]，i＜k，则 以 两 个 字 节 B0B1替换 W[k…l]。

其中：B1=i；B0的最高位置 1，其余 7位为二进制的j-i+1数值表示。

例如，对于图3(a)中的原始报文，附加标志位进行重组后形成报文如图3(b)所示，进行压缩后的报文如图3(c)，其中，B0的最高位为 1表示接下来两个字节代表了一个压缩表示，B0的后7位等于3代表压缩了3个字节，B1=0代表压缩匹配位置是从第0位开始的。

以上算法打破了字符串结构，在每个字节内附加一个标志位（flag）来标识该字节是否被压缩表示，这样大大降低了单个字符也用三元组表示而造成的浪费。

2算法改进

利用电力线通信报文低速率、短报文（长度不超过256 B）的特点，可以充分挖掘某种压缩算法(LZ77)的潜力。

2.1压缩粒度

针对短报文，如果想尽可能地挖掘它的结构模式就要在更小的粒度级别上进行压缩。由于比特串只有0和1组成，重复串不限于起始结尾于字节，其更有可能出现重复的模式，因此相比较字节级别在位级的压缩应该更有效。如图4所示，字节级表示的字符流B1和B2中重复子串为“bb”，而在比特表示的字符流 b1和 b2中重复子串的长度达到 33 bit，超过了 2 B，扩展了可压缩的范围。

2.2改进数据结构

由于电力线通信报文长度短，可压缩空间较小，以上压缩算法可能会造成压缩后的报文比压缩前更长。对于大小为n个字节的报文来说，不管压缩与否，首先要附加n/7个字节来标识每个字符是否压缩，因此，只有能够压缩大于n/7个字节才能对报文进行压缩，否则该压缩将没有意义。

在此，再次改进压缩报文的数据结构来降低这种额外开销，使得对于未被压缩的字节不增加额外信息。为了实现这一目标，就要将标识位所表达的信息集中表示，这样在压缩后的报文开头用一个字节用来表示压缩信息：用一个字节表示压缩表示计数 c（0～255），用来表达该报文一共被压缩了几处（最多可压缩255处）。接下来的信息为压缩后的报文信息：压缩报文块 k（ik，jk，lk），其中 ik：压缩位置 ；jk：原始报文位置；lk：匹配 长度 。每个压缩表示用4 B存储，其中前11位表示当前压缩位置ik，中间11位表示匹配原始报文位置jk，后10位表示匹配长度lk。再接下来的信息为不能进行压缩表示的余留报文数据，对于最后不足一个字节的报文补零凑够整字节。改进的数据结构如表1所示。

表1 改进的数据结构

例如，对于图5(a)中的原始报文数据，进行两处压缩后如图5(b)所示（为了方便说明改进的数据结构，本例中使用的原始报文按照以上编码方式编码后形成的压缩后报文比原始报文更长，而在实际压缩算法设计时不会出现这种情况）。

改进后的数据结构与之前的数据结构在算法性能上的比较如表2所示。

对于第一种数据结构的额外开销压缩与未压缩报文均摊从而造成不必要的浪费，第二种数据结构的额外开销虽然均用在了被压缩的报文上没有造成浪费，但是这种结构缩小了能够进行压缩的范围，两种数据结构各有利弊，应根据实际情况权衡选择。

表2 两种数据结构的比较（假设位级压缩）

2.3放松算法时间复杂度限制——最优化问题

在电力线通信中，由于报文传输速率低，用于传输的时间远远多于在本地处理报文所需要的时间，同样由于电力线通信报文属于短报文，算法输入规模小。基于以上两种报文特点，也可以放松对算法时间复杂度的限制，充分挖掘LZ77算法的潜力，尽量将报文压缩至最短，从而最大程度地提高报文的传输速率。

针对电力线通信短报文压缩，结合LZ77算法顺序滑动滑动窗口思想，很容易得出以下压缩思路，即从第一个位置开始对每个位置i求其最长重复子串，如果有价值则对其进行压缩表示，否则原样输出。这种思路简单易行，但是不能实现对报文的充分压缩，压缩效果不是最优。如果要挖掘LZ77算法在电力线通信报文压缩问题上的极限，那么要采用下面的压缩思路：

第一步：求出每个位置i为起点最长重复出现子串；

第二步：选择合适的重复子串压缩表示,以获取最大的压缩比。

其中，第一步的技术实现有两种方式：滑动窗口以及后缀树，滑动窗口结构简单易于实现，但是对于可变长度的滑动窗口来说，这种技术不利于进行重复子串的搜索，其复杂度为O(n2)。而如果用后缀树技术，在对重复子串的搜索上可以将时间复杂度降低到O(n)，但是后缀树的构造比较复杂，并且将还会增加算法本身的复杂性，尤其在字节级别进行压缩时需要构造的后缀树将非常复杂。

第二步也有两种实现策略：

(1)选择相互独立子串，使压缩比最高，数学模型如下：

给定[1…n]上的 m 个区间：[i1，j1][i2，j2]…[im，jm]

求：选 k 个独立子区间：[h1，l1][h2，l2]…[hk，lk]

使得(l1-h1+1-c)+(l2-h2+1-c)+…+(lk-hk+1-c)达到最大。

(2)在选择合适的重复子串时不限制子串的独立性，可以考虑对某些子串进行分解，数学模型如下：

给定[1…n]上的 m 个区间：[i1，j1][i2，j2]…[im，jm]

求：选 k 个独立子区间：[h1，l1][h2，l2]…[hk，lk]

满足[hi，li](1≤i≤k)是给定某子区间的子集

使得(l1-h1+1-c)+(l2-h2+1-c)+…+(lk-hk+1-c)达到最大。

注：c为压缩表示大小

这种压缩思路打破了LZ77顺序压缩的思想，它不是随着滑动窗口的顺序滑动实时地进行数据压缩而是在标记了每个位置起始的最长重复子序列之后在这些子序列中选择一组最优的压缩组合，从而达到最大程度的压缩。同时这种思路的两种不同实现策略对报文的压缩程度也有不同，经过证明第二种策略较第一种策略对报文的压缩程度更大。

3下一步工作

3.1证明上述改进算法第二步的第二种策略是否是NP完全问题

下面从上述策略中的最优化问题导出如下判定问题：

Instance：I={I1，I2，…，Im}为区 间[1…n]上 的 m 个 interval的集合，常数 k，c；

Question：是否存在[1…n]上的独立 interval集 J={J1，J2，…，Jr}

满足：

(1)∀1≤i≤r，∃1≤j≤m，Ji⊆Ij且 Ji>c

其中：|Ji|=b-a+1，若 Ji=[a，b]

接下来的任务就是要证明(或否证)以上问题是NP完全的。如果它是一个NP完全问题，那么我们就要退而求次来寻求解决该问题的近似算法。

3.2从信息论角度探索数据压缩的极限

从信息论角度探索数据压缩的极限，既然熵是消息包含信息量多少的度量，那么它就可以作为一个度量压缩算法对消息进行压缩的边界或者尺度，用来界定最多可以将消息压缩到什么程度。

[1]杨宗剑，冯娟.低压电力线载波抄表系统现状及发展[J].湖北电力，2008，32(5)：62-63，70.

[2]林其田.低压电力线载波抄表系统[J].福建建设科技，2006(1)：52-54.

[3]王学伟，张蕊.电力线载波DS扩频通信及数据压缩[J].中国住宅设施，2008(08)：50-53.

[4]ZIV J，LEMPEL A.A universal algorithm for sequential data compression[J].IEEE Transactions on Information Theory，VOL.IT-23，NO.3，MAY 1977.

[5]NELSON M.数据压缩技术原理与范例[M].贾起东，译.北京：科学出版社，1995.