一种面向无线多媒体传感器网络的分布式图像压缩算法

基金项目：国家自然科学基金(60573141、60773041)；国家高技术研究发展计划(“863”计划)资助项目(2006AA01Z219、2007AA01Z404、2007AA01Z478)

    本文在低功耗自适应集簇分层型协议(LEACH)的基础上提出了一种无线多媒体传感器网络的分簇方法。选取能量较大的节点做簇头，周围与之一跳可达的节点加入该簇头，剩余节点仍按照以上方法成簇。如果某一个簇头的节点数超过上限值，则对该簇进行分割。

    在按照以上方法成簇的网络中实行分布式图像压缩算法。分布式图像压缩算法把一幅图像的压缩任务分配给其他节点，在能量受限的多媒体传感器网络中能高效率的进行图像压缩。

    由于单个节点的处理能力有限，集中式压缩会使图像采集节点的能量很快耗尽，而分布式压缩提高了节点耗能的均衡性，从而延长了整个网络的生存时间。

1 相关算法研究介绍
    文献[1]给出了LEACH协议的思想，该协议是低能量自适应分簇路由协议，采用随机选举簇头的方式避免簇头过分消耗能量，但频繁簇头选取引发的通信量耗费了能量。文献[2]是对LEACH协议进行改进，在选取簇头时加入了能量和分布位置等约束条件，提高了网络的性能。文献[3]中的PEGASIS协议和文献[4]中的TEEN协议都是层次路由协议，也是在LEACH协议基础上的改进。文献[5]提出一种能量自适应的簇首选择机制，但是上面的几种分簇算法都不能很好地适应多媒体传感器网络巨大的数据量。文献[6]提出了传感器网络中的快速傅立叶变换(FFT)图像压缩算法。文献[7]使用小波变换来修正传感器数据解决每个传感器节点只观测一个象素点的问题，该方法的重点在于传感器之间的协作处理。文献[8]提出了一种基于能量的分布式图像压缩方案，在特殊的链式网络环境中利用离散小波变换进行图像压缩，提高了网络生存时间。但是这种链式网络过于理想化，没有广泛的应用性。

    本文在对LEACH协议进行有效改进的基础上，提出了一种分布式JPEG图像压缩算法，该算法将采集到数据分块转发给簇内节点，簇内节点将压缩好数据传给簇头，能够更好地均衡网络中各节点的能量消耗，延长网络的生存时间，并且通过实验仿真证实了该算法的有效性。

2 算法描述

2.1 簇的建立
    (1)LEACH协议
    虽然LEACH算法为一种经典的分簇算法，但是此协议簇头的选择完全依赖于簇形成时期节点形成的随机数，对其余参数(比如剩余能量、分布位置)并没有加以考虑，从而导致缺陷。

    (2)改进算法
    在无线多媒体传感器网络中，由于要处理和传输的数据量很大，若采用LEACH协议分簇，它的自身缺陷将大大减少了网络的寿命。针对LEACH协议的缺陷，提出了以下改进：

• 针对能量的改进。选取能量较多节点为簇头，将节点的剩余能量作为选择簇头的一个重要衡量标准，使剩余能量较多的节点成为簇头。
• 针对节点地理分布不均的改进。每个节点根据能量大小都有机会竞选簇头，保证所有簇头能覆盖整个网络。
• 针对负载均衡度进行的优化。由于节点地理分布不均，簇头负载的簇内节点数量必然不同，导致簇头的负载不均衡。若要提高负载均衡度，可以在簇内节点数大于平均数的网络中重新选取几个簇头，将原来的网络分割成几个网络，以达到簇头负载均衡的目的。
  

    (3)改进后算法的实施步骤
    在边长为r 的方形区域内随机撒播N 个节点，设簇头覆盖半径R，每个簇内的最大节点个数为n。所有节点根据剩余能量从大到小进行排序，得到一个{1,2,…,N }中的序号i。

    所有节点同时开始倒计时i 个时间单位，以此来竞选簇头。倒计时结束时向周围节点发送撤消消息包，以声明其簇头身份。若某节点倒计时未结束，且收到撤销消息包，则停止倒计时，该节点也不再参与竞争簇头。收到簇头信号的节点向簇头发送加入信号。已经加入到某簇头的节点，即使收到其他簇头的消息包，也不会加入到其他簇头。

    执行完以上步骤，除了有限的几个孤立节点，其他节点都能加入临近的簇头。不过有些簇头管理的节点可能过多，造成簇头负载不平均，以下步骤将对节点过多的簇进行分割，在簇内根据能量大小再选出几个簇头，使能量消耗尽量平均。

    簇头计算簇内节点数。假设某个簇内的节点数为S，若S >n，则簇头向簇内节点发送分割消息包，并再选出
个簇头。簇内节点收到该分割消息包继续倒计时，倒计时结束时向簇内其他节点发射撤消指令，并声明其簇头身份。若某节点倒计时未结束，且收到簇内节点发出的撤销信号，则停止倒计时，该节点也不再参与竞争簇头。收到簇头信号的节点向簇头发送加入信号。如果该簇头内的节点数小于  ，则取消其簇头身份，执行以上步骤，根据倒计时的次序再选一个簇头。若簇内节点个数大于，簇头根据节点加入信号的强弱，由远至近排除簇内节点，使节点数为。已经成簇的簇头和成员节点不再参与下一轮簇头竞争，也不再加入其他的簇头。将剩余节点重复执行以上步骤，直至选出J 个簇头。由于原始簇头对网络中的所有节点是可达的，簇内的剩余节点加入开始的簇头。如果最后会出现几个孤立节点，而且覆盖半径内有簇头节点，则令其加入到临近的簇头。

2.2 图像的分布式压缩
    (1)JPEG图像压缩算法
    JPEG压缩技术十分优秀，它用有损压缩方式去除冗余的图像数据，在获得极高的压缩率的同时能展现十分丰富生动的图像。所以本文将JPEG图像压缩技术引入到多媒体传感器网络中，以提高整个网络的性能。
JPEG图像压缩的流程如下，图像传感器采集到的象素数据首先分割成8×8的数据块，每个数据块分别进行二维离散余弦变换(DCT)以转换到频域。变换后低频分量集中在左上角，高频分量集中在右下角。因为人眼对低频分量比较敏感，所以可以通过一个量化矩阵把高频分量变为零，以达到压缩的目的。之后通过熵编码把数据整合成有限的几个比特位。

    由于无线多媒体网络中节点的能量是受限的，若图像采集节点进行JPEG图像压缩，则其能量很快耗尽，影响网络的寿命。所以提出分布式图像压缩，将原始图像分块，分别送到各个空闲节点进行压缩，虽然增加了数据传输的能耗，但可以减轻图像采集节点的负担，使各个节点的能耗均衡化，提高了网络的生存时间。

    (2)多媒体传感器网络中的分布式JPEG图像压缩
    按照前文所述的多媒体传感器网络的成簇算法成簇的网络拓扑如图1所示。假定某一时刻只有节点s采集图像，簇内其他节点将剩余能量{е1,е2,е3,…,еm}(设簇内除图像采集节点和簇头节点外的节点个数为m)汇报给s。s根据剩余能量大小生成一个概率 ，该概率与剩余能量成正比。s节点将采集到的图像分成8×8的数据块，每个数据块都加入该数据块在整个图像中的位置信息，便于接收节点还原图像，每个象素点用8 bit表示。图像采集节点根据概率向簇内节点转发数据块，如果目的节点有一条可达，则直接向该节点发送数据，否则通过簇头节点转发。收到数据的节点就进行JPEG编码，处理好的数据返回给簇头节点，由于每个压缩好的数据包都包含位置信息，所以簇头节点不进行数据整合，以节省能量。簇头节点选择路由转发给接收节点，图像在接收节点进行数据融合。

    根据文献[9]提出的短距离通信模型，两节点间距离为d ，通信能量消耗与d 成正比。
发送1 bit数据消耗的能量为：

    其中εе为电路消耗的能量，εα为信号放大器的耗能参数，d 是发送节点和接收节点间的通信距离，2≤α≤4是路径损耗系数。

    假设簇内与s一跳可达的节点个数为k，l 1,l  2,…,lk为s与其一跳可达节点的距离，d 1,d 2,…,dm为簇内节点到簇头的距离，d s为图像采集节点到簇头的距离，dc为簇头与下一跳节点的距离，η1,η2,…,ηm为s发送给各个节点数据的概率。设M 为图像的比特数，g 为图像的压缩比，W为源节点采集图像的能量消耗，C为压缩每比特的能量消耗。则图像采集节点s的耗能为：

簇内的一个节点的耗能为：
Ei =(εе+C )Mηi +(εе+εе+
             εαliα)Mηi ig      (1≤i≤m)    (4)
簇头节点的耗能为：

而集中式压缩(即图像采集节点采集完图像就进行压缩，然后传送给簇头)的图像采集节点能量消耗为：
CentS =W +MC +(εе+εαdsα)Mg    (6)
集中式压缩的簇头节点的能量消耗为：

3 仿真结果
    用矩阵实验室(MATLAB)生成一个节点分布图，节点随机分布在(x =0,y =0)与(x =100,y =100)的区域内。每个节点的能量在0.3J 到0.7J 间随机分布。图像采集节点在非簇头中随机选取。

    假设节点总数N =150，每个簇内的最大节点个数为10，两个节点的最大通信距离(比例长度)为20，则节点的成簇的结果如图2所示。

图2 网络成簇的仿真结果

    从图2中可以看出，节点密集的地方簇头多，节点稀疏的地方簇头少，但基本能保证每个节点都能加入邻近的簇头。每个簇头管理的节点数都小于上限值，降低了簇头的负担。

    取节点总数N＝300，每个簇内的最大节点个数n =10。对集中式和分布式图像压缩的网络生存时间的仿真(同样参数的情况下重复执行了50次)，仿真结果如图3所示。

    从图3中可以看出分布式压缩的网络生存时间明显优于集中式。由于节点是随机撒播，节点的成簇状况变化比较大，造成了分布式压缩的网络生存时间有一定的起伏。

    集中式压缩的网络生存时间(开始采集图像到第一个节点能量耗尽的时间内网络采集传输图像的总次数)在100上下波动，因为集中式压缩图像采集节点消耗大量的能量，簇头节点消耗很少的能量，因此不管簇内有多少节点，采集图像次数多的节点决定网络的生存时间。

    图4是只对分布式图像压缩的网络生存时间进行仿真。总节点个数N依次取300、450、600和750。簇内的最大节点个数从1取到50。

    从图中可以看出总节点个数越多，网络生存时间越长。由于图像采集节点是随机选取的，总节点个数越多，簇的个数就越多，会有更多的簇分担图像的采集和压缩的任务，延长了网络的生存时间。分布式压缩的网络生存时间随簇内节点的最大个数的增大而减小。由于簇头节点要进行大量的数据转发，所以簇内节点过多，簇头的能量会很快耗尽。当簇内最大节点个数为5～15时，网络生存时间比较大。

4 结束语
    本文分析了LEACH算法，针对节点能量分布和簇头管理的节点个数的不均衡，提出了一种在无线多媒体网络中的改进算法。并在该成簇算法形成的网络中提出一种分布式图像压缩算法。图像采集节点通过把压缩任务分配给簇内其他节点来平衡各个节点的能量消耗。仿真结果表明分布式图像压缩的网络生存时间比集中式有很大的提高。

    本算法适应节点初始能量不均匀和节点分布不均匀的无线多媒体传感器网络，有一定的实用性。

5 参考文献
[1] HEINZELMAN W R, CHANDRAKASAN A, BALAKRISHNAN H. Energy-efficient communication protocol for wireless micro sensor networks[C]//Proceeding of the 33rd Annual Hawaii International Conference on System Sciences(HICSS'00),Jan 4-7,2000, Maui, HI,USA. Los Alamitos, CA,USA: IEEE Computer Society, 2000:10p.
[2] 杜向党, 李亦洋, 石秀华. 无线传感器网络基于类的簇头选择算法改进[J]. 传感技术学报, 2008,21(7):1202-1206.
[3] LINDSEY S, RAGHAYENDRA C S. PEGASIS: Power efficient gathering in sensor information systems[C]//Proceedings of the IEEE Aerospace Conference:Vol 3, Mar 9-16, 2002, Big Sky, MT, USA. Los Alamitos, CA,USA: IEEE Computer Society, 2002:1125-1130.
[4] MANJESHWAR A, AGRAWAL D P. TEEN: A protocol for enhanced efficiency in wireless sensor networks[C]//Proceedings of the 15th International Parallel and Distributed Processing Symposium(IPDPS’01),Apr 23-27,2001, San Francisco, CA,USA. Los Alamitos, CA,USA: IEEE Computer Society, 2001:2009-2015.
[5] 梁英, 曾鹏, 于海斌. 无线传感器网络中一种能量自适应的簇首选择机制[J]. 信息与控制, 2006,35(2):141-146.
[6] CHIASSERINI C F, RAO R R. On the concept of distributed digital signal processing in wireless sensor networks[C]//Proceedings of Military Communicationa Conference(MILCOM’02), Vol 1,Oct 7-10,Anaheim,CA,USA. Piscataway,NJ,USA:IEEE, 2002:260-264.
[7] SERVETTO S D. Sensing lena–massively distributed compression of sensor images[C]//Proceedings of IEEE International Conference on Image Processing (ICIP’03):Vol 1,Sep 14-17,2003,Barcelona, Spain. Piscataway, NJ,USA: IEEE, 2003:613-616.
[8] WU Huaming, ABOUZEID A A. Energy efficient distributed image compression in resource- constrained multihop wireless networks[J].Computer Communications, 2005,28(14):1658-1668.
[9] YOUNIS O, FAHMY S. HeeD:A hybrid,energy-efficient,distributed clustering approach for ad-hoc sensor networks[J]. IEEE Transactions on Mobile Computing , 2004,3(4):660-669.

收稿日期：2009-06-17

[摘要] 因为多媒体数据的高带宽要求，要传输传感器节点采集到的原始数据将会消耗大量的资源。文章提出了一种分布式图像压缩算法，该算法通过把压缩任务分配给其他节点来解决在能量受限的节点上处理能力不足的问题。此外，该算法把压缩任务分配给其他空闲节点能很好的延长网络的生存时间。

[关键词] 分布式压缩；无线多媒体传感器网络；网络生存时间

[Abstract] Because of the high bandwidth demands of multimedia date, the transmission of raw data collected at sensor nodes will consume a large amount of resources. Distributed image compression is proposed as a means to overcome the computation and energy limitation of individual nodes by sharing the processing of tasks. It has the additional benefit of prolonging the overall lifetime of the network by distributing the computational load among otherwise idle processors.

[Keywords] distributed compression; wireless multimedia sensor networks; network lifetime