基于移动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.