基于移動Agent的JPEG2000分布式編碼算法研究

劉志興 張 菁 卓 力

(北京工業大學信號與信息處理研究室 北京 100124)

1 引言

無線傳感器網絡(Wireless Sensor Network，WSN)綜合了傳感器技術、嵌入式計算技術、現代網絡及無線通信技術、分布式信息處理技術等多個學科領域，是目前的一個前沿研究熱點領域[1]。在節點能量有限的WSN 網絡中，為了降低網絡流量，必須對大量的圖像視頻數據進行高效的壓縮。JPEG2000是新一代靜態圖像壓縮標準，較之JPEG標準具有更好的編碼性能[2]。JPEG2000核心算法是離散小波變換(Discrete Wavelet Transform，DWT)，最佳截斷的嵌入式碼塊編碼(Embedded Block Coding with Optimal Truncation,EBCOT)[3]，其算法復雜度高、運算量大。

在網絡節點能量有限的WSN環境中，采用集中式JPEG2000算法處理海量的圖像數據會造成單個節點能量迅速耗盡，難以保持系統長期穩定的運行。因此，需要采用一種分布式的處理技術來實現JPEG2000算法，也就是說，由多個網絡節點協同編碼，使得每個節點只承擔相應的小部分計算量，從而將網絡能耗均衡化。

移動Agent的研究起源于人工智能領域，是一種新興的分布式計算技術，能夠對收集數據進行分析處理，并減輕數據傳輸、存儲的負載。通過在不同節點間引入移動Agent進行數據采集、傳輸，可以有效降低節點間的數據傳輸量，節約節點的能耗。

近年來，許多研究者對移動Agent和分布式處理技術進行了研究。Xu等[4]針對WSN中的目標跟蹤，設計了一種基于預測的移動Agent動態遷移模型，提高了移動Agent的遷移效率，極大地減少了WSN中的數據通信，降低了能耗。Wu等[5]在多跳無線網絡環境中綜合考慮系統能耗和圖像質量提出了兩種分布式小波分解的JPEG2000編碼方法(基于行、列分解方法和圖像分片方法)，并且從總能耗和系統壽命兩個方面與傳統的集中式小波分解方法做了比較。實驗結果表明這兩種方法都能有效均衡系統能耗，延長系統壽命。但在低比特率下，圖像分片的方法會造成圖像的碼塊效應及嚴重的重建圖像失真。

本文借鑒Wu的基于行、列分解的分布式DWT方法[5]，通過引入移動Agent技術，實現了一種JPEG2000分布式編碼算法。首先對JPEG2000中計算量大的小波分解采用分布式處理，以均衡節點能耗；然后將移動Agent技術應用于分布式算法中的碼率控制環節，在網絡節點間進行編碼信息的采集與傳輸。實驗結果表明，本文算法在WSN環境中可以保證編碼后的圖像質量沒有下降，并能有效均衡系統能耗、延長網絡生命周期達3倍。

2 基于移動Agent的JPEG2000編碼結構

本文面向能量有限的無線傳感器網絡環境，實現了一種基于移動Agent的JPEG2000的分布式編碼，編碼框圖如圖1所示。JPEG2000編碼過程包括：預處理、離散小波變換(DWT)、量化和最優截斷嵌入式碼塊編碼(EBCOT)。其中EBCOT可分為2級(Two Tiers)：Tier-1編碼和 Tier-2編碼。Tier-1編碼為塊編碼(Block Coding)，包括位平面編碼和自適應二值算術編碼，對每個編碼塊進行嵌入式編碼，得到嵌入式的壓縮碼流。Tier-2編碼為碼流組織，由壓縮后率失真優化(Post-Compression Rate-Distortion Optimization，PCRDO)算法對所有碼塊的嵌入式壓縮碼流進行最優截斷，對截斷后的碼流進行重組得到輸出的JPEG2000碼流[2]。

根據WSN網絡的具體特點，本文從兩個方面對原有的、集中式JPEG2000編碼算法進行了改進。一方面，用分布式離散小波變換取代傳統的離散小波變換，另一方面，采用基于移動Agent的PCRDO算法取代原有的PCRDO算法對碼流進行截斷。接下來詳細介紹這兩個部分的具體實現方法。

圖1 基于移動Agent的JPEG2000的分布式編碼框圖

3 分布式DWT算法

借鑒文獻[5]中的思路，本文基于分層的無線傳感器網絡結構，實現了一種分布式的小波變換，具體實現過程如圖2所示。

圖2 分層無線網絡結構的分布式小波變換

本文采用文獻[6]的WSN分層網絡結構，數據以多跳方式進行傳輸，網絡節點被劃分為多個簇群，每一簇群由一個簇頭節點(如H1，H2，H3，H4)以及多個子節點(如簇群1中的P11，P12，P13，P14等)組成。本文通過一種競爭規則選取簇群中具有較大能量的節點作為簇頭節點，該簇頭節點負責數據的分配、傳遞和接收。假設在WSN中，每一級小波分解由一簇中的4個子節點共同完成，則節點間的信息交互過程如下：

(1)傳感器節點S發送控制命令給第1級簇頭節點H1，H1將相鄰的4個節點集合起來形成P1子節點集(P11，P12，P13，P14)。

(2)傳感器節點S將采集到的圖像按行分為4塊，如圖3所示(圖3中R1，R2，R3，R4)。并將這些行數據塊傳送給4個子節點(P11，P12，P13，P14)，每個子節點逐行進行1維小波變換(1D-DWT)。

圖 3 按行和列分塊的分布式小波變換

(3)子節點P11，P12，P13，P14將變換完的小波系數(X1，X2，X3，X4)傳遞回到H1節點。H1按照原圖像中的行排列順序重組圖像，得到低頻分量L和高頻分量H。

(4)H1再將圖像按列分4塊(圖3中Y1，Y2，Y3，Y4)，分別傳遞給子節點P11，P12，P13，P14，每個節點逐列進行1維小波變換。

(5)P11，P12，P13，P14將變換后的小波系數(C1，C2，C3，C4)傳遞給第2級簇頭節點H2，H2按照原圖像的列排列順序重組圖像，得到（LL，LH，HL，HH）4個小波子帶。這樣，即完成了1級小波變換。

(6)H2選取1級小波變換的LL子帶，按照上述的1級小波分解方式傳遞給第2級簇節點群中的子節點P21，P22，P23，P24，實現2級小波變換，得到2級小波變換系數。

(7)H2對1級小波變換后的LH1，HL1，HH1高頻子帶進行量化以及嵌入式熵編碼。

(8)同理，P21，P22，P23，P24節點將數據傳遞給第3級簇頭節點H3，由H3對2級小波變換后的LH2，HL2，HH2高頻子帶進行量化及嵌入式熵編碼。

依此類推，直到完成所需的小波分解級數。由于后幾級小波變換的圖像數據量很小，其能耗很少。因此，可以由簇頭節點H4獨立完成后幾級小波變換、各子帶的量化及嵌入式熵編碼過程。

4 基于移動Agent的PCRDO算法

4.1 JPEG2000中的PCRDO算法

JPEG2000中，各碼塊在Tier-1階段分別獨立進行編碼，而在Tier-2階段，PCRDO算法用于對Tier-1階段的編碼碼流進行最優截斷。PCRDO算法是基于率失真理論提出來的，用于實現碼率的最優化控制，其數學表達式如下：

其中N表示小波分解后子帶的數目(由公式N=3?p+1計算得到，p表示小波分解級數)；Lmax為目標碼率；ni表示第i個小波子帶的截斷點數目；和表示截斷點n(i=1,2,…, n)的碼率和失真。從式ii(1)可以看出，PCRDO算法的基本思想是根據每個小波子帶的編碼率失真特性，確定每個子帶的最優截斷點(i=1,2,…,N)，在所有子帶截斷碼率之和小于目標碼率Lmax的情況下，使得整幅圖像編碼后的失真D達到最小。這是一個約束條件下的最優化問題。利用拉格朗日乘子(Lagrange Multiplier)法，可以將此問題轉化為無約束的最優化問題，引入拉格朗日乘子λ，得到

根據拉格朗日乘子法，在給定λ的情況下，使式(2)中M達到最小，同時也滿足式的截斷點一定也是式(1)的最優解[3]。這樣搜索各子帶的最優截斷點的過程就簡化為求解L'(λ)=Lmax的最優率失真斜率λ*的過程。由于ni對應的是離散的采樣點，因此可以采用二分法來搜索λ*值。

4.2 基于移動Agent機制的PCRDO算法

在WSN中，數據傳輸會耗費大量的能量，與文獻[5]中傳輸所有壓縮碼流的方式不同，本文利用移動Agent靈活的遷移能力，只對各小波子帶的編碼率失真數據信息進行采集、處理，這樣避免了大量無用信息的傳輸，從而降低節點之間的數據通信量。

本文提出的基于移動Agent的PCRDO算法參見圖2，以5級小波分解結構為例，具體的實現步驟如下：

(1)在最后一級簇頭節點H4處創建移動Agent。

(2)對移動Agent進行路徑設定。根據一種合理的路由方式[7]，從最后一級小波變換的簇頭節點H4開始，逐級遷移到H3，H2，在每個節點處收集相應的小波子帶各碼塊編碼碼率R和率失真斜率λ。在保存第1級小波高頻子帶LH1，HL1，HH1的簇頭H2處進行數據融合，得到全部的編碼率失真信息。

(3)在H2處執行改進后的PCRDO算法的代碼，得出最優率失真斜率*λ。(4)通過移動Agent將此最優率失真斜率*λ按照原路徑反向傳送回各級簇頭節點。根據最優率失真斜率，各級簇頭節點對壓縮碼流進行，截斷碼流，獲得截斷碼流。

(5)依照H2-H4簇頭的次序，將各個簇頭處的截斷碼流分別傳送到匯聚節點，最后，在匯聚節點處對包頭信息進行Tag Tree編碼，打包、重組得到最后的輸出碼流。

5 實驗結果分析

為了驗證所提算法的有效性，本文分別對圖像重建質量，分布式小波變換傳輸數據量，算法能耗以及無線傳感器網絡工作壽命進行了對比分析。實驗中采用的計算機配置如下：Pentium IV 3.00 GHz CPU, 1 G內存，Windows XP操作系統，VC++6.0編程。

5.1 圖像質量實驗結果

圖4所示的為不同碼率下，分別采用本文的JPEG2000分布式算法與傳統的集中式JPEG2000算法對Lena圖像進行編碼后的重建質量對比結果。其中，小波變換級數為5。

圖4 不同碼率下兩種算法圖像重建質量對比結果

由圖4可以看出，兩種算法的圖像重建質量基本相當，這表明采用本文提出的分布式JPEG2000編碼算法不會造成圖像重建質量的下降。

5.2 算法能耗對比

本文將網絡的壽命定義為WSN中任意一節點能量耗盡的時間，這樣，對網絡中能耗最大節點做能耗對比分析也可以客觀反映網絡壽命的長短。

本節首先介紹WSN節點能耗計算方法，然后將傳統的集中式方法與本文所提出的基于移動Agent的分布式JPEG2000編碼算法的能耗進行對比分析。

5.2.1 WSN節點能耗計算方法 WSN中節點能耗E由節點計算能耗EC和數據交互能耗EE(包括數據發送能耗ET和數據接收能耗ER)組成，即下面分別分析節點處的計算能耗和數據交互能耗。

(1)節點計算能耗 節點計算能耗EC是節點處單位信息(比特)計算能耗eC與數據量SC的乘積：

在JPEG2000編碼中，由于PCRDO算法的二分法求解過程能耗非常小，與DWT以及量化、熵編碼過程相比，其能耗可以忽略不計。因此，編碼過程的計算能耗主要集中在DWT和量化、熵編碼環節，節點處的計算能耗EC也可用式(5)表示為

其中EDWT表示節點處DWT計算所需能耗，EENC表示節點處進行量化和熵編碼所需的能耗；eDWT表示圖像中每個圖像像素點經過1級DWT(2次1DDWT)每比特數據的平均計算能耗(對于灰度圖像，每個像素點包括8個比特)，SDWT表示圖像像素點經過DWT的總比特數(圖像長度×寬度×8)；eENC表示圖像經過量化和熵編碼每比特數據的平均計算能耗，SENC表示圖像經過量化和熵編碼的總比特數。以StrongARM SA-1100作為WSN中的網絡節點為例，測量得到：eDWT≈220 nJ/bit，eENC≈20 nJ/bit[6]。

(2)數據交互能耗 WSN中數據交互能耗包括數據發送能耗ET和數據接收能耗ER，二者的計算公式分別為

其中eT表示節點發送信息和信息傳輸過程的單位信息能耗，eR表示節點接收數據過程的單位信息能耗；e1和e2分別表示節點在發送和接收信息過程中的單位信息能耗，其值均取為50 nJ/bit；e'表示單位信息傳送過程中由于信號保持而在單位面積(m2)耗損的能量，在密集型布設的WSN中，其值取為100 pJ/bit/m2；ST，SR分別表示發送和接受的數據量；d表示信息的傳輸距離，通常取d=10 m。

5.2.2 傳統集中式JPEG2000編碼方法的節點能耗

對于集中式的JPEG2000編碼方法來說，圖像數據的采集與編碼均在源節點S處進行，優化截斷的JPEG2000壓縮碼流被逐級傳送至匯聚節點，因此能耗最大的節點為源節點S。根據上述的分析，節點S處的能耗ES如式(8)所示：

其中Si表示第i級DWT的數據量，I表示圖像大小(M×N像素)。

其中R為目標碼率。由于節點S無需接收數據，因此節點接收能耗=0。

綜上，以Lena標準測試圖像(512×512，8 bpp)為例，若目標碼率為R = 1 bpp，進行5級小波變換，代入式(8)可得節點S處的總能耗為：ES≈6.72×108(nJ)。

5.2.3 本文基于移動Agent分布式JPEG2000編碼算法的節點能耗 如前所述，采用本文提出的JPEG2000分布式實現算法，WSN中各節點完成的功能不同，其能耗也有很大差別。可以看出，采用本文提出的分布式算法，WSN中能耗較大的節點都集中在前兩級節點中，隨著級數的增大，節點能耗逐步降低。因此，本文只對前兩級節點的計算量以及總能耗進行對比分析。

同樣，以Lena標準測試圖像(512×512，8 bpp)為例。假設目標碼率為R = 1 bpp，進行5級小波變換，碼塊個數為m=64，每個碼塊中平均截斷點個數約為n=20。每個截斷點處率失真信息(碼字長度和率失真斜率均為4 byte)的數據量為2p=8 byte。本文算法中WSN各節點功能及其對應的計算量、總能耗對比結果如表1所示。

由表1中的節點總能耗對比可以看出，采用本文提出的JPEG2000分布式實現算法，WSN中能耗最大的節點是簇頭H2，其能耗為EH2≈2.38×108(nJ)，與傳統的集中式實現方法相比，本文算法節點最大能耗只占35.42%。因此網絡壽命可延長至原網絡壽命大約3倍。但是也需要指出的是，這種網絡工作壽命的延長是以增加網絡中的傳輸數據量為代價的。

表1 本文算法WSN各節點功能及其對應計算量(bit)、總能耗對比

6 結束語

本文通過引入移動Agent技術，實現了一種JPEG2000分布式編碼算法。首先對JPEG2000中計算量最大的小波分解模塊采用分布式處理，以均衡節點能耗；然后將移動Agent技術應用于分布式算法中的碼率控制環節，在網絡節點間進行編碼率失真信息的采集與傳輸，驗證了其應用在網絡節點處理能力、存儲能力和能量供應均有限的WSN網絡中的可行性。實驗結果表明，在圖像編碼性能不變的前提下，本文提出的算法可以有效地均衡WSN節點能耗，使得網絡壽命延長3倍。本文雖然證明了所提算法的優越性以及可行性，但仍有許多方面值得深入研究，比如WSN中分簇路由算法以及節點輪換機制，每一級小波變換需要多少節點協同工作使得能量利用率最高，WSN中傳輸過程中的誤碼問題，節點協同工作的同步問題等，這也是我們下一步的研究方向。

[1] Yick J, Mukherjee B, and Ghosal D. Wireless sensor network survey[J]. Computer Networks, 2008, 52 (12): 2292-2330.

[2] Skodras A, Christopoulos C, and Ebrhimi T. The JPEG 2000 still image compression standard[J]. Signal Processing Magazine, 2001, 18(5): 36-58.

[3] Taubman D. High performance scalable image compression with EBCOT[C]. IEEE Transactions on Image Processing,2000, 9(7): 1158-1170.

[4] Xu Ying-yue and Qi Hai-rong. Mobile agent migration modeling and design for target tracking in wireless sensor networks[J]. Ad hoc Networks, 2008, 6(1): 1-16.

[5] Wu Hua-ming and Abouzeid A A. Energy efficient distributed JPEG2000 image compression in multihop wireless networks[J]. Applications and Services in Wireless Networks, 2005, 28(14): 1658-1668.

[6] Halgamuge M N, Guru S M, and Jennings A. Energy efficient cluster formation in wireless sensor networks[C]. The 10th International Conference on Telecommunications, Papeete,French Polynesia, 2003: 1571-1576.

[7] Yin Gui-sheng, Yang Guang, and Yang Wu, et al.. An energy-efficient routing algorithm for wireless sensor networks[C]. Proceedings of the 2008 International Conference on Internet Computing in Science and Engineering, Harbin, China, 2008: 181-186.