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

(1.中國海洋大學(xué) 計算機科學(xué)系，山東 青島266100；2.中國海洋大學(xué) 信息工程中心，山東 青島266071)

電力線載波通信是利用已有的電力線路進行數(shù)據(jù)傳輸?shù)囊环N通信方式，無需專門架設(shè)通信基礎(chǔ)設(shè)施并且具有相當廣泛的網(wǎng)絡(luò)分布，因此，電力線載波通信是一種非常經(jīng)濟的通信方式。然而，由于電力線載波通信存在著一些技術(shù)難題，如傳輸信道間歇噪聲大、阻抗隨負載變化大、信號衰減大等問題[1]，使得目前電力線載波通信僅在自動抄表系統(tǒng)（AMRS）的應(yīng)用上得到了比較好的發(fā)展。

自動抄表系統(tǒng)要求能夠穩(wěn)定準確地抄到每個表，然而由于電力網(wǎng)絡(luò)的分布電容、分布電感、負載性質(zhì)、負載阻抗值、噪聲等都是動態(tài)的，而非恒定的，然而一個設(shè)計定型的系統(tǒng)產(chǎn)品,其調(diào)制/解調(diào)制式、工作頻率、發(fā)送功率、信道參數(shù)、通信效果等通常都是不變的,這就導(dǎo)致了抄表系統(tǒng)不能保證在各種環(huán)境下都可以可靠地運行，因此產(chǎn)生了一系列技術(shù)難題[2]。

使用擴頻通信技術(shù)來避免電力線的強干擾、強衰減等缺陷，然而擴頻導(dǎo)致了通信速率的大大降低，這使得窄帶通信的傳輸速率只是寬帶的幾百分之一，這在一定程度上限制了擴頻通信的廣泛應(yīng)用[3]。

將數(shù)據(jù)壓縮技術(shù)引入到電力抄表系統(tǒng)可以提高通信速率、降低誤碼率，從而使電力線載波抄表系統(tǒng)更加穩(wěn)定。

1數(shù)據(jù)壓縮原理

數(shù)據(jù)壓縮實際上也是一種編碼，如果壓縮是有效的，那么編碼后的數(shù)據(jù)比原始數(shù)據(jù)占用的存儲空間小。數(shù)據(jù)壓縮根據(jù)信息論的基本概念分為無損壓縮和有損壓縮，本文討論的是無損壓縮。數(shù)據(jù)之所以能被壓縮是因為它存在某種規(guī)律或者結(jié)構(gòu)，從信息論角度來看就是數(shù)據(jù)中存在冗余信息，而數(shù)據(jù)壓縮就是要去除數(shù)據(jù)中的冗余信息。

關(guān)于數(shù)據(jù)壓縮有很多算法，針對不同特點的數(shù)據(jù)選擇不同的壓縮算法從而達到最優(yōu)的壓縮效果。LZ77是一種通用的順序數(shù)據(jù)壓縮算法，它不需要知道數(shù)據(jù)本身的一些特性，對于任何數(shù)據(jù)都可以進行壓縮[4]，思路簡單，自從J.Ziv和 A.Lempel于1977年提出該算法之后很快得到了廣泛應(yīng)用。

1.1通用壓縮算法LZ77

LZ77通過引入滑動窗口（sliding-window），在字符流上順序滑動sliding-window，從而實現(xiàn)字符流的壓縮。以圖1中數(shù)據(jù)為例，LZ77算法將從左至右滑動slidingwindow對其進行壓縮表示，sliding-window分為兩個部分：search buffer（搜索緩沖區(qū),大小為 7，編號從 0開始）和 look-ahead buffer（向前查找緩沖區(qū)，大小為 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所示。

該算法簡單易行，有較高的執(zhí)行效率，然而很容易發(fā)現(xiàn)它存在的一些問題。于是接下來的幾年里出現(xiàn)了很多LZ77的改進算法，如不限制窗口長度的LZR算法、引入Huffman編碼的LZH算法以及改進search buffer數(shù)據(jù)結(jié)構(gòu)和三元組表示的LZSS算法[5]等。

1.2電力線通信報文壓縮算法設(shè)計

針對電力線通信報文W，以下壓縮方案來自于LZSS壓縮算法思想：

(1)首先將報文W從左至右，每7 bit組成一個字節(jié)，字節(jié)的最高位置0，低7位來自W；

(2)如 果 W[i…j]=W[k…l]，i＜k，則 以 兩 個 字 節(jié) B0B1替換 W[k…l]。

其中：B1=i；B0的最高位置 1，其余 7位為二進制的j-i+1數(shù)值表示。

例如，對于圖3(a)中的原始報文，附加標志位進行重組后形成報文如圖3(b)所示，進行壓縮后的報文如圖3(c)，其中，B0的最高位為 1表示接下來兩個字節(jié)代表了一個壓縮表示，B0的后7位等于3代表壓縮了3個字節(jié)，B1=0代表壓縮匹配位置是從第0位開始的。

以上算法打破了字符串結(jié)構(gòu)，在每個字節(jié)內(nèi)附加一個標志位（flag）來標識該字節(jié)是否被壓縮表示，這樣大大降低了單個字符也用三元組表示而造成的浪費。

2算法改進

利用電力線通信報文低速率、短報文（長度不超過256 B）的特點，可以充分挖掘某種壓縮算法(LZ77)的潛力。

2.1壓縮粒度

針對短報文，如果想盡可能地挖掘它的結(jié)構(gòu)模式就要在更小的粒度級別上進行壓縮。由于比特串只有0和1組成，重復(fù)串不限于起始結(jié)尾于字節(jié)，其更有可能出現(xiàn)重復(fù)的模式，因此相比較字節(jié)級別在位級的壓縮應(yīng)該更有效。如圖4所示，字節(jié)級表示的字符流B1和B2中重復(fù)子串為“bb”，而在比特表示的字符流 b1和 b2中重復(fù)子串的長度達到 33 bit，超過了 2 B，擴展了可壓縮的范圍。

2.2改進數(shù)據(jù)結(jié)構(gòu)

由于電力線通信報文長度短，可壓縮空間較小，以上壓縮算法可能會造成壓縮后的報文比壓縮前更長。對于大小為n個字節(jié)的報文來說，不管壓縮與否，首先要附加n/7個字節(jié)來標識每個字符是否壓縮，因此，只有能夠壓縮大于n/7個字節(jié)才能對報文進行壓縮，否則該壓縮將沒有意義。

在此，再次改進壓縮報文的數(shù)據(jù)結(jié)構(gòu)來降低這種額外開銷，使得對于未被壓縮的字節(jié)不增加額外信息。為了實現(xiàn)這一目標，就要將標識位所表達的信息集中表示，這樣在壓縮后的報文開頭用一個字節(jié)用來表示壓縮信息：用一個字節(jié)表示壓縮表示計數(shù) c（0～255），用來表達該報文一共被壓縮了幾處（最多可壓縮255處）。接下來的信息為壓縮后的報文信息：壓縮報文塊 k（ik，jk，lk），其中 ik：壓縮位置 ；jk：原始報文位置；lk：匹配 長度 。每個壓縮表示用4 B存儲，其中前11位表示當前壓縮位置ik，中間11位表示匹配原始報文位置jk，后10位表示匹配長度lk。再接下來的信息為不能進行壓縮表示的余留報文數(shù)據(jù)，對于最后不足一個字節(jié)的報文補零湊夠整字節(jié)。改進的數(shù)據(jù)結(jié)構(gòu)如表1所示。

表1 改進的數(shù)據(jù)結(jié)構(gòu)

例如，對于圖5(a)中的原始報文數(shù)據(jù)，進行兩處壓縮后如圖5(b)所示（為了方便說明改進的數(shù)據(jù)結(jié)構(gòu)，本例中使用的原始報文按照以上編碼方式編碼后形成的壓縮后報文比原始報文更長，而在實際壓縮算法設(shè)計時不會出現(xiàn)這種情況）。

改進后的數(shù)據(jù)結(jié)構(gòu)與之前的數(shù)據(jù)結(jié)構(gòu)在算法性能上的比較如表2所示。

對于第一種數(shù)據(jù)結(jié)構(gòu)的額外開銷壓縮與未壓縮報文均攤從而造成不必要的浪費，第二種數(shù)據(jù)結(jié)構(gòu)的額外開銷雖然均用在了被壓縮的報文上沒有造成浪費，但是這種結(jié)構(gòu)縮小了能夠進行壓縮的范圍，兩種數(shù)據(jù)結(jié)構(gòu)各有利弊，應(yīng)根據(jù)實際情況權(quán)衡選擇。

表2 兩種數(shù)據(jù)結(jié)構(gòu)的比較（假設(shè)位級壓縮）

2.3放松算法時間復(fù)雜度限制——最優(yōu)化問題

在電力線通信中，由于報文傳輸速率低，用于傳輸?shù)臅r間遠遠多于在本地處理報文所需要的時間，同樣由于電力線通信報文屬于短報文，算法輸入規(guī)模小?；谝陨蟽煞N報文特點，也可以放松對算法時間復(fù)雜度的限制，充分挖掘LZ77算法的潛力，盡量將報文壓縮至最短，從而最大程度地提高報文的傳輸速率。

針對電力線通信短報文壓縮，結(jié)合LZ77算法順序滑動滑動窗口思想，很容易得出以下壓縮思路，即從第一個位置開始對每個位置i求其最長重復(fù)子串，如果有價值則對其進行壓縮表示，否則原樣輸出。這種思路簡單易行，但是不能實現(xiàn)對報文的充分壓縮，壓縮效果不是最優(yōu)。如果要挖掘LZ77算法在電力線通信報文壓縮問題上的極限，那么要采用下面的壓縮思路：

第一步：求出每個位置i為起點最長重復(fù)出現(xiàn)子串；

第二步：選擇合適的重復(fù)子串壓縮表示,以獲取最大的壓縮比。

其中，第一步的技術(shù)實現(xiàn)有兩種方式：滑動窗口以及后綴樹，滑動窗口結(jié)構(gòu)簡單易于實現(xiàn)，但是對于可變長度的滑動窗口來說，這種技術(shù)不利于進行重復(fù)子串的搜索，其復(fù)雜度為O(n2)。而如果用后綴樹技術(shù)，在對重復(fù)子串的搜索上可以將時間復(fù)雜度降低到O(n)，但是后綴樹的構(gòu)造比較復(fù)雜，并且將還會增加算法本身的復(fù)雜性，尤其在字節(jié)級別進行壓縮時需要構(gòu)造的后綴樹將非常復(fù)雜。

第二步也有兩種實現(xiàn)策略：

(1)選擇相互獨立子串，使壓縮比最高，數(shù)學(xué)模型如下：

給定[1…n]上的 m 個區(qū)間：[i1，j1][i2，j2]…[im，jm]

求：選 k 個獨立子區(qū)間：[h1，l1][h2，l2]…[hk，lk]

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

(2)在選擇合適的重復(fù)子串時不限制子串的獨立性，可以考慮對某些子串進行分解，數(shù)學(xué)模型如下：

給定[1…n]上的 m 個區(qū)間：[i1，j1][i2，j2]…[im，jm]

求：選 k 個獨立子區(qū)間：[h1，l1][h2，l2]…[hk，lk]

滿足[hi，li](1≤i≤k)是給定某子區(qū)間的子集

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

注：c為壓縮表示大小

這種壓縮思路打破了LZ77順序壓縮的思想，它不是隨著滑動窗口的順序滑動實時地進行數(shù)據(jù)壓縮而是在標記了每個位置起始的最長重復(fù)子序列之后在這些子序列中選擇一組最優(yōu)的壓縮組合，從而達到最大程度的壓縮。同時這種思路的兩種不同實現(xiàn)策略對報文的壓縮程度也有不同，經(jīng)過證明第二種策略較第一種策略對報文的壓縮程度更大。

3下一步工作

3.1證明上述改進算法第二步的第二種策略是否是NP完全問題

下面從上述策略中的最優(yōu)化問題導(dǎo)出如下判定問題：

Instance：I={I1，I2，…，Im}為區(qū) 間[1…n]上 的 m 個 interval的集合，常數(shù) 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]

接下來的任務(wù)就是要證明(或否證)以上問題是NP完全的。如果它是一個NP完全問題，那么我們就要退而求次來尋求解決該問題的近似算法。

3.2從信息論角度探索數(shù)據(jù)壓縮的極限

從信息論角度探索數(shù)據(jù)壓縮的極限，既然熵是消息包含信息量多少的度量，那么它就可以作為一個度量壓縮算法對消息進行壓縮的邊界或者尺度，用來界定最多可以將消息壓縮到什么程度。

[1]楊宗劍，馮娟.低壓電力線載波抄表系統(tǒng)現(xiàn)狀及發(fā)展[J].湖北電力，2008，32(5)：62-63，70.

[2]林其田.低壓電力線載波抄表系統(tǒng)[J].福建建設(shè)科技，2006(1)：52-54.

[3]王學(xué)偉，張蕊.電力線載波DS擴頻通信及數(shù)據(jù)壓縮[J].中國住宅設(shè)施，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.數(shù)據(jù)壓縮技術(shù)原理與范例[M].賈起東，譯.北京：科學(xué)出版社，1995.