電力線窄帶通信報文壓縮算法研究

劉 萌 ，丁香乾 ，侯軍偉 ，王 銳

(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.