原文：A Survey on Data Compression in Wireless Sensor Networks ---- from： Naoto Kimura and Shahram Latifi
譯文：關于無線傳感網絡的資料壓縮調查
原文和譯文可以到我的資源下載下傳，我的下載下傳。
關于無線傳感網絡的資料壓縮調查
摘 要:無線傳感網絡(WSNs)的資源是受限制的：有限的能量支援，通信的帶寬，處理的速度以及記憶體空間。最大限度的利用這些資源的一種可能的方式是将傳輸資料進行壓縮。通常情況下，在無線媒體中處理資料消耗的電力比傳輸資料要少，是以，在傳送資料之前對傳感器節點進行資料壓縮以減少總功耗是有效的。然而，現有的壓縮算法并不适用于傳感器節點,因為它們的資源是受限的。是以，本文介紹了一些被專門設計的用于無線傳感網絡的壓縮算法：通過指令的編碼，流水線網絡壓縮，低複雜性的視訊壓縮和分布式壓縮。
1. 引言
由于快速發展的半導體制造技術，電子裝置變得更小，更便宜，操作所需的能量一年比一年少。無線傳感網絡是得益于該技術進步的領域之一。近年來，大量關于無線傳感網絡的研究已經開始進行，并且人們已經意識到它無限的适用性。比如說，無線傳感網絡可以用于不同環境下的資料收集，就像環境監測、行為監測、監視、結構監測、裝置診斷、災害管理和應急響應。然而，無線傳感網絡的技術相對還不成熟，在它變得更實用之前仍然需要更多大量的研究和開發。
無線傳感器網絡的基本配置是在傳感器領域部署大量的傳感器節點。所有節點通過射頻、紅外線、或其他無線媒體連接配接。資料的收集通過周遊無線網絡中的所有節點實作。為了實作無線傳感網絡，點對點網絡技術被廣泛應用以便允許任何兩個節點之間的直接通信。如果兩個裝置之間不能直接通信，那麼在此之間的其他節點将會在源節點和目标節點之間發送資料包。這被稱為多點跳躍傳輸路由。由于他們的點對點通信模式，不需要一個控制網絡構成的中心節點（類似于一個蜂窩系統的基站）。因為無線傳感網絡沒有了固定的基礎設施，建造一個網絡更加廉價。網絡中節點在增加和移除更為容易。另一方面，由于節點可以随意地添加和删除，無線傳感網絡的網絡拓撲可能會徹底改變。來自傳感節點的資料通過彙點被收集。彙點可以通過網絡或衛星與區域網路外的世界連接配接。傳感節點會在傳感領域消失，是以傳感器節點的位置不能預先确定。本文讨論的傳感器将配備至少一個電源、傳感裝置、處理單元（使得資料可以在傳感器單元中處理）和收發單元。
就像之前所說，希望每個傳感節點的尺寸變小。為了達到這個要求，每個傳感器元件的尺寸比如能量源，處理單元和儲存單元的元件都必須要小。許多傳感節點也會被部署到很難通路的位置。實作比如在部署的傳感器節點上更換電池等維護操作是不實際的。由于以上原因，無線傳感網絡，或者更具體地說是每個傳感節點是受資源限制的。受限于的電能支援，通信的帶寬，處理的速度以及存儲空間。是以，目前有許多緻力于如何使有限傳感資源達到最大化的研究已經進行。
傳感網絡的資源使用率研究之一是資料壓縮。研究者們尋求壓縮傳感資料的最佳方式。通過這些做法，由于在不同節點上處理和傳送資料可以減少能量的消耗進而擴充了他們在傳感網絡上的生存時間。通過減小資料的大小的方式，收發資料需要減少帶寬。資料壓縮式是一個利用資源有限的無線傳感網絡的有效方法。
本文的其餘結構如下：在下一個章節，我會闡述無線媒體中資料壓縮和傳送的能量消耗。一些專門設計的無線傳感網絡方案會在章節3表述。最後，章節4是總結。
2. 無線媒體能量消耗的分析
在能量消耗方面，無線傳感節點的操作可以分為3個部分：感覺、處理和傳輸。在這3部分中，最消耗能量的任務是資料傳輸。每個傳感器中大約80%的電能用于資料傳輸。是以如果我們可以通過壓縮減少資料量，那麼就可以減少傳輸的功耗。但從另一方面看，應用資料壓縮會使處理需要更多能量來實作壓縮算法。為了減少總功耗，傳輸和處理資料的總功耗必須減小。壓縮字元串“a”到“b”
（a>b）所消耗的能量必須小于傳輸“a-b”字元串所消耗的能量。
在參考文獻5中，呈現了一個關于在無線通信中通過資料壓縮和資料傳輸的能量消耗的研究。在他們的實驗中，康柏個人伺服器（康柏iPAQ的研究版本）代替無線傳感節點收集資料，是以他們的實驗結果可能不能完全适用于無線傳感網絡。但是，這仍然在資料處理和傳輸的能量消耗方面給出了重要的見解。
第一個試驗是收集執行一個簡單的32位加法指令和傳輸一個位所消耗的電能資料。結果表明大約0.4微焦的能量用于發送單一的一個位的資料。其中0.86納焦能量用于加法指令。無線傳輸媒體中傳輸一位所耗能量相當于執行480次加法指令。結果表明，如果通過應用壓縮操作從原始資料位字元串移除超過一位,它接受指令相當于480加法指令，，這将通過傳感器節點減少所耗能量。
實際的資料壓縮算法遠比一系列的加法指令複雜，是以下一個實驗顯示通過應用各種現有的用于web頁面和文本的無損資料壓縮所消耗的總功。這個實驗進行的測試壓縮算法是bzip2 (BWT算法)，壓縮 (LZE算法)，LZO (LZ77)，PPMd (PPM)和zlib(LZ77)。表1顯示了移除一個位所需的指令數量。每個資料壓縮算法的指令數比480要少得多，是以使用這些算法時，比簡單傳輸資料消耗的總功要小。根據實驗結果，對于大多數壓縮算法，在傳輸資料前進行壓縮可以減少總功。但是，在某些情況中也會增加能量的消耗。這是由于執行壓縮時通路了記憶體。通路記憶體是能量消耗的重大因素。是以，實驗結果指明在無線媒體傳輸前壓縮資料可以有效減少大量功耗，關鍵在于選擇一個在壓縮資料時盡量不需要通路記憶體的算法。
3. 資料壓縮技術
在之前的章節研究中介紹了發送資料消耗的能量比處理資料多，在無線媒體傳輸之前縮小資料量能夠有效的減少總功的消耗。是以，采用資料壓縮算法對于無線傳感網絡是有益的。
一個問題是大多數現有的資料壓縮算法不适用于無線傳感網絡。其中一個原因是算法的大小。比如說，bzip2的大小是219KB ，LZO 是220KB。傳感器節點的指令記憶體大小目前可用的隻有128MB。另一個原因是處理器的速度。傳感器節點的處理器速度隻有4MHz。另一方面，如今計算機的處理速度大概是3GHz。是以必須位傳感網絡設計一個低複雜性并且資料量小的壓縮算法。在這一節中，會介紹一些無線傳感網絡的資料壓縮方案。
3.1 編碼排序
在參考文獻7中，介紹了作為資料彙集路由的資料壓縮的編碼。這個壓縮方案如下。首先，資料從傳感器節點感興趣的地區通過，到一個彙點節點（設定如圖1所示）。在資料彙集路由中，一些傳感器節點像資料彙集節點一樣工作。例如，節點A、B、D是資料彙點節點。通過與其他節點組合收集傳感資料，聚合資料發送給它的父節點。在圖3的節點D，通過節點E與收集資料節點D結合再收集資料。然後彙集資料傳輸到節點B。
該算法中，當資料與彙點節點結合時，一些資料被丢棄。為了包含彙集資料中丢棄資料的資訊，利用了資料包的順序。比如說，4個節點 (N1，N2，N3和
N4)發送資料到一個彙點節點(Na)。每一節點的資料值可以是0-5任何一個整數。如果我們把資料從N4丢棄通過其他3個節點的資料包從N4傳輸，就有3! = 6 種
可能的排序。是以，通過使用3個資料包的排列，N4的資料值可以被包含到彙點包中而沒有完全包含N4的資料包。可能的組合排列和資料值如表2所示。
一般情況下，我們假設傳感器節點的總數是n（每個節點有不同的節點ID），m是節點發送資料包至一個彙點節點的數量，k是可能範圍的資料值，l是在彙點節點丢棄的傳感器節點的數量。ID可能的組合數量可以表示為
。因為每個l節點可以搭載k值間的任何可能資料值，共有kl可能的資料值組合。當結合可能的ID和資料值，共有
種可能值。這個值的組合能表達為(m−l)!種排列。是以，下面的不等式是成立的。
（1）
從理論上講，當n =27，k = 24，m = 100，大約44%的資料包可以應用編碼排序删除彙點節點。因為這種方法具有良好的壓縮比和簡單的算法，它可用于無線傳感網絡。困難之一是利用這個方案，由于沒有有效的算法映射排列資料值，是以需要一個映射表。随着傳感器彙點節點數量的增加，表的大小呈指數增長。
3.2 流水線網内壓縮
文獻6中讨論了流水線網内壓縮。基本的想法是用高資料傳輸延遲降低傳輸能源消耗。在一個彙點節點存儲緩沖的收集傳感器資料區需要一些持續時間。在那段時間，資料包被組合到一個包，和減少的資料包一起被删除，以最大限度減少資料傳輸。
比如說，每個資料包有一下形式：<measured value, node ID, timestamp>。然後，壓縮資料封包有以下形式：<shared prefix, suffix list, node IDlist, timestamp list>。“共享字首”是最重要的部分，是所有測量值在聯合資料包的共同點。共享字首的長度可以根據使用者對資料相似性的認識改變。如果預計的測量值接近對方，字首值的長度可以設定相對較長。“字尾清單”是測量值清單不包括共享字首的部分。“節點ID清單”是一組節點辨別符，“時間戳清單”是清單的時間戳。壓縮方案如圖4所示。在此圖中，三個節點發送資料包到壓縮節點。在壓縮節點，三個資料包被壓縮成一個包。在本例中，共享字首的長度被設定為3。在這個例子中，所有位的數量從37減少到33。
這個簡單的壓縮方案的一個優點是，共享字首系統可以用于節點ID和時間戳。通過這樣的做法，可以實作更多的資料壓縮。資料壓縮的效率取決于共享字首的長度。如果我們可以設定一個長的共享字首和一個有共性的測量值，壓縮比就會增加。然而，沒有相似的測量傳感值，即使我們可以設定一個長的共享字首，網絡壓縮流水線的效率也會降低。此外，如果我們結合大量的資料包，就會大于資料緩沖區需要的臨時存儲包。因為一個傳感器節點隻有一個有限大小的記憶體空間，将沒有足夠的緩沖空間可用。
3.3 低複雜性視訊壓縮
文獻8介紹的低複雜性視訊壓縮。因為目前的視訊編碼技術主要設計利用運動估計和補償，它将需要一個高計算功率，那麼傳感器節點通常不配備。是以，該方法是基于塊的變化檢測算法和JPEG資料壓縮。圖3展示了一個塊的圖像數
據處理流。該算法是專門為無線視訊監控系統設計的。在這個方法中，每個視訊幀被分成小塊，每個塊包含8×8(64)像素。為了減少計算複雜度，隻有一部分的塊（所有空白塊在這種情況下）在幀中被考慮。此外，在每一塊像素子集中（号碼配置設定像素）檢查他們的變化，如圖7所示。配置設定給像素的數量表明像素的重要性（1 =最重要和3 =最不重要）。
該算法如下：第一步，一塊“1”指定像素與參考幀的像素。如果兩個像素的差異(Di)大于一個門檻值(M)，初值為零計數器(P)增加了1。兩個像素的最大差別是存儲U，如果P比一個敏感性參數(S)大，就由一個使用者設定，可以用一個1到3的整數，塊标記為一個活躍的塊，掃描程式移動到下一個塊。如果在檢查所有“1”的像素後P ≤ S，平均差異(A)可以被計算。如果A<N并且U<M，N是另外一個門檻值且N<M，處理下一個塊。否則，開始檢查“2”的算法指定像素在同一塊。
“2”和“3”在同一塊指定像素，過程與執行“1”配置設定像素相同。不同的是，在檢查所有像素後，如果A>N且U>M，塊被标記為一個活躍的塊，程式移動到下一個塊為“2”指定像素。為“3”配置設定像素在檢查所有像素後，如果(A>N 且 U>M)或者(A<N,U>M, 且P>S)，塊标記為活躍塊。
在檢查一個幀内的一組空白塊之後，非掃描塊(在圖7中的黑色塊)被檢查。如果一個非掃描塊至少與兩個活動塊相鄰，非掃描塊被标記為活動。
最後，所有的标記塊被編碼成JPEG格式并在無線傳感器網絡中傳輸。同時，活動塊被傳輸給參考幀緩沖區用于更新資料參考幀。
實驗結果表明，通過此算法處理的圖像品質與通過算法mpeg-2處理的非常類似盡管這種算法實作了一定的節能效果。
3.4 分布式壓縮
通過[9][4]的介紹，分布式壓縮方案的基本思想是使用邊資訊編碼源資訊。例如，如圖4中存在兩個資料源(X,Y)。他們是相關的和離散的字母獨立同分布的。因為在傳感器網絡中，傳感器節點将密集分布在傳感器範圍内，這種相關性條件可以很容易得到滿足。然後，X可以以條件熵的理論利率進行壓縮，H(X | Y)，沒有編碼器1通路Y[3]。條件熵可以表示為
（8）
一般的分布式壓縮方案是首先編碼疊合組，其源資料X的矢量。在一個相同的資料集中的任何兩個矢量的距離必須足夠大。一個索引值被配置設定給每個資料集。當資料傳輸到一個解碼器，源X隻發送一個這個矢量所屬的資料集的索引值。源Y發送一個矢量作為邊資訊。譯碼器查找資料集，這個資料集具與收到的X具有相同的索引。然後，譯碼器選擇一個矢量，在這個集合中，它具有一個與由Y發送的矢量最接近的值。
分布式壓縮的一個簡單例子如下。有兩個(X和Y)3位的資料集。X和Y之間的漢明距離不超過一位。如果兩個編碼器和譯碼器都知道Y，X可以被壓縮到2位。然而，如果Y隻對解碼器已知，X的壓縮率将會是多少呢？根據分布式壓縮方案，因為譯碼器知道Y和X距離Y隻有一個漢明距離，區分X =111還是X = 000的效果是不佳的。相同的原因，X = 001和110，X = 010和101，X = 011和110不需要互相差別。這些兩個X值的組被分為4 資料集、配置設定4不同的二進制索引号：
資料集1 = (000, 111) : 00
資料集 2 = (001, 110) : 01
資料集 3 = (010, 101) : 10
資料集 4 = (011, 100) : 11
如果X = 010，Y = 110，譯碼器将收到的Y = 110作為來自Y的邊資訊，X = 10作為一個來自X局部資訊。然後在解碼器中，資料集2 中的X = 010被選中因為110和110距離2個哈明距離。無論X是否 知道Y，X仍然可以将3位資訊壓縮到2位。
通過上面例子，分布式壓縮方案不僅可以應用于離散的資料源，也可以應用于連續的資料源。同時，它可以用于無損壓縮和有損壓縮方案。例如， 4個資料集可以由一個8級量化器形成。值得注意的是：每個資料集中的兩個矢量是被分組的，這樣他們彼此可以有最大可能的距離。
4. 結論
在目前社會中，人們正在讨論WSNs的廣泛的應用領域。在未來随着技術的進步WSNs的應用領域将比現在更為廣泛。對人們來說，他們将比現在更為有用。然而，在那些實作之前，在傳感器網絡的實際使用中仍然存在許多困難需要克服。困難之一是無線節點的資源有限。本文中，提出了五個不同類型的資料壓縮方案---通過指令編碼、流水線網内壓縮、JPEG200、低壓縮低複雜度的視訊壓縮和分布式壓縮。盡管這些壓縮方案仍處于開發階段，實驗結果表明，其壓縮率和節電性能相當驚人。他們是一個用以減少無線傳感器節點資源限制的可能的方法。
參考文獻
[1] I. F. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci, “Asurvey on sensor networks,”
IEEE Communications Magazine, Volume: 40 Issue: 8, pp. 102-114,August 2002
[2] D. Culler, D. Estrin, and M. Srivastava, “Guest Editors’Introduction: Overview of Sensor Network,” Computer, Volume: 37 Issue: 8, pp.41-49, August 2004
[3] D. Slepian and J. K. Wolf, “Noiseless Coding of CorrelatedInformation Sources,” IEEE Trans. on Information Theory, Volume: IT-19, pp.471-480, July 1973.
[4] J. Kusuma, L. Doherty, and K. Ramchandran, “DistributedCompression for Sensor Networks,” In Proceedings of 2001 InternationalConference on Image Processing, October 2001.
[5] Kenneth Barr and Krste Asanovic, “Energy Aware Lossless DataCompression,” In First International Conference on Mobile Systems,Applications, and Services, May 2003.
[6] T. Arici, B. Gedik, Y. Altunbasak, and L. Liu, “PINCO: aPipelined In-Network Compression Scheme for Data Collection in Wireless SensorNetworks,” In Proceedings of 12th International Conference on ComputerCommunications and Networks, October 2003.
[7] D. Petrovic, R. C. Shah, K. Ramchandran, and J. Rabaey, “DataFunneling: Routing with Aggregation and Compression for Wireless SensorNetworks,” In Proceedings of First IEEE International Workshop on SensorNetwork Protocols and Applications, May 2003.
[8] E. Magli, M. Mancin, and L Merello, “Low-Complexity VideoCompression for Wireless Sensor Networks,” In Proceedings of 2003 InternationalConference on Multimedia and Expo, July 2003.
[9] S. S. Pradhan, J. Kusuma, and K Ramchandran, “DistributedCompression in a Dense Microsensor Network,” IEEE Signal Processing Magazine,Volume: 19, Issue: 2, pp. 51-60,
March 2002.
[10] MICA Wireless Measurement System http://www.xbow.com/Products/Product_pdf_files/Wireless_pdf/MICA.pdf