Distributed Image Compression Algorithm in Wireless Multimedia Sensor Networks

This work was funded by the National Natural Science Foundation of China under Grant No. 60573141 and 60773041, and the National High Technology Research and Development Program of China (“863” Program) under Grant No. 2006AA01Z219, 2007AA01Z404 and 2007AA01Z478.

 
    The Wireless Multimedia Sensor Network (WMSN) is a distributed sensor network consisting of a group of multimedia sensor nodes that have the capabilities of computation, storage, and communication. In such a network, the multimedia sensors at the nodes first sense ambient multimedia information (e.g. audio, video, image and numerical values) and send them to the information convergence center via multi-hop relays. Then, the convergence center analyzes the collected data. In this way, the network achieves effective and all-round environment monitoring.

    However, image sensor nodes suffer problems such as heavy data traffic, and limited energy and computation capability. As a result, image compression methods are often adopted to reduce energy consumption arising from communications. Image compression, however,  involves heavy computation, causing the image capture node to exhaust its energy quickly and the receiving node to take a long time to receive the images.

    This paper proposes a clustering approach for WMSNs based on Low-Energy Adaptive Clustering Hierarchy (LEACH) protocol. Using this approach, a node with high energy is selected as the cluster head, and the nodes at one-hop distance from the head join the cluster. The rest nodes are clustered in the same way. If the number of nodes in a cluster exceeds the threshold, the cluster will be split further.

    This paper also introduces a distributed image compression algorithm for networks with nodes clustered using the above approach. By assigning image compression tasks to nodes other than the image capture node, this algorithm can achieve efficient image compression in a multimedia sensor network with limited energy. Moreover, in centralized compression method, the energy of the image capture node is quickly spent due to the limited processing capability of a single node. With the distributed compression method, energy consumption of all nodes is balanced, thus prolonging the life of the entire network.

1 Introduction to Related Algorithms
Reference [1] proposes LEACH protocol, which utilizes randomized rotation of cluster heads to avoid them overconsuming energy. However, frequent selection of cluster heads leads to increased energy consumption for communications. Reference [2] suggests an arithmetic which improves LEACH protocol by introducing constraints such as energy and distribution location when choosing cluster heads. This improves network performance. The Power-Efficient Gathering in Sensor Information System (PEGASIS) protocol in Reference [3] and Threshold Sensitive Energy Efficient sensor Network (TEEN) protocol in Reference [4] are hierarchical routing protocols, and are also improved versions of LEACH. Reference [5] proposes an energy adaptive cluster head selection mechanism. All the above clustering protocols cannot satisfy the huge data traffic of multimedia sensor networks.

    Reference [6] suggests Fast Fourier Transform (FFT) image compression algorithm for sensor networks. Discrete Cosine Transform (DCT) in this paper is similar to FFT, but it divides an image into several data blocks and exploits the buffer of each node to easily implement distributed compression. So it is more suitable for multimedia sensor networks. Reference [7] uses wavelets to decorrelate sensor data in order to solve the problem of each sensor node only observing one pixel. The key to this method is cooperative processing between sensors. Reference [8] proposes an energy-based distributed image compression scheme, where Discrete Wavelet Transform (DWT) is used to compress images in the special link network environment, thereby prolonging the network’s life. But the link network is too ideal to be widely applied.

    Taking LEACH as a basis, this paper proposes a distributed Joint Photographic Experts Group (JPEG) image compression algorithm. In this algorithm, the image capture node divides the collected data into blocks and forwards them to nodes in the same cluster for compression. Then, the compressed data is sent to the cluster head. In this way, the algorithm balances energy consumption among all network nodes and prolongs the network’s life. Simulations have proven this algorithm is effective.

2 Clustering and Compression Algorithms

2.1 Cluster Setup
    (1) LEACH
    LEACH is a classic clustering protocol. It chooses cluster heads based on a random number of nodes during the cluster set-up stage and does not take into account other parameters, such as the remaining energy and distribution location. Hence, it has the following defects:

• As the initial energy and remaining energy of the node is not considered, if a node with low energy is selected as the cluster head, its energy may be exhausted earlier than expected.
• In the node-dense areas, there may be many cluster heads, while in the areas with fewer nodes, there may be fewer cluster heads or even no cluster heads. As a result, some nodes may be outside any cluster, and the network will be incomplete.
• The cluster setup mechanism cannot guarantee the number of nodes managed by all cluster heads will be the same or similar. Therefore, the cluster head with more nodes may use up its energy earlier than others, thus leading to network paralysis.

    (2) Improved Algorithm
    In WMSNs, there is a huge amount of data to be processed and transmitted. If LEACH protocol is used for clustering, the lifet of the network will be dramatically shortened due to above-mentioned defects. To remedy these defects, the following improvements are suggested:

• Taking energy into consideration. The remaining energy of the node becomes an important criterion in choosing the cluster head. The node with high remaining energy should be chosen as the cluster head.
• Improvement on uneven geographical distribution of nodes. Depending on the energy, each node has a chance to be selected as the cluster head, ensuring enough cluster heads to cover the entire network.
• Optimization of load balance: When the nodes are not evenly distributed geographically, the number of nodes under a cluster head is sure to be different from that of another cluster head. As a consequence, the loads of all cluster heads will be unbalanced. To balance the loads, new cluster heads can be chosen from a cluster with more nodes than average to split the cluster into several clusters.

    (3) Implementation of Improved Algorithm
    Suppose N  nodes are randomly spread in a square zone of r × r, the coverage radius of the cluster head is R, and the node threshold for each cluster is n . First, all nodes are sorted according to their remaining energy in ascending order, giving a node set: {1, 2, …, N }.

    Then, all nodes simultaneously count down a time unit of i , during which all nodes are contenders for cluster heads. When the countdown finishes, the cluster heads send a cancel message to the surrounding nodes, claiming their status as cluster heads. If the node’s countdown fails to terminate but the node receives the cancel message, it will stop the countdown and not contend for the cluster head again. The nodes receiving the cancel message send signals to the cluster heads, indicating they have joined the clusters. However, the nodes that have already been in a cluster will not join other clusters even when they receive a message from other cluster heads.

    With the above steps executed, all nodes except limited isolated nodes will have joined cluster heads close to them. However, in clusters set up in this way, some cluster heads may be expected to manage excessive nodes, resulting in load unbalance. In this case, the following steps must be taken to split these clusters. That is to say, several more cluster heads must be chosen from these clusters based on the nodes’energy so as to balance energy consumption.

    The splitting of clusters with excessive nodes can proceed as follows: First, the cluster head calculates the number of nodes within its cluster. Assuming the number of nodes within a cluster is S and S is greater than the threshold n, the cluster head sends a split message to all nodes in the cluster and  cluster heads will be chosen. Upon receiving the message, each node begins the countdown. Similarly, when the countdown finishes, cluster heads send a cancel message to other nodes, claiming their status as cluster heads. If the countdown fails to terminate at a node but the node receives the cancel message, it will stop the countdown and will not contend for the cluster head again. The nodes receiving the cancel message send signals to the cluster heads, indicating they have joined the clusters. If the number of nodes in a new cluster is less than
, the cluster head will be denied its status, and another cluster head will be chosen by repeating the above steps. If the number of nodes in the new cluster
is greater than  , the cluster head will observe the signal strengths of the joined nodes and expel the nodes with weak signals, starting with the weakest one, until its nodes are exactly  .

    The cluster head and its member nodes will neither contend for cluster heads in the next round nor join other clusters. The remaining nodes will repeat the above steps until J cluster heads are chosen.

    As the original cluster head can reach all nodes in the network, the nodes left after all cluster heads have been chosen will join the original cluster head. If some nodes are isolated but there are cluster heads within their coverage radius, they will join the cluster heads that are closest to them.

2.2 Distributed Image Compression
    (1) JPEG Compression Algorithm
JPEG compression technique performs excellently. It removes  redundant image data by means of lossy compression, thus achieving a high compression ratio while at the same time presenting vivid images. This paper introduces JPEG compression method in multimedia sensor networks, as a way of improving the performance of the entire network.

    The JPEG compression process is as follows: The pixels captured by an image sensor are first split into 8 × 8 blocks and each block is converted to a frequency-domain representation by using a two-dimensional DCT. After conversion, the low frequency components are located in the top-left corner, while the high frequency components are in the bottom-right corner. Because the human eye is sensitive to low frequency components, high frequency components can be rounded to zero with a quantization matrix in order to achieve compression. Finally, the data is integrated into limited bits with entropy coding.

    As the energy of nodes in the WMSNs is limited, if the image capture node implements JPEG compression, its energy will soon be spent and the network’s life will be shortened.

Therefore, distributed image compression algorithm is proposed here to split an original image into blocks, which are sent to idle nodes for compression. In this way, the load of the image capture node is lessened even though energy consumption for data transmission may increase. This enables energy consumption of all nodes to be balanced and the network life to be prolonged.

    (2) Distributed JPEG Compression in Multimedia Sensor Networks
    Figure 1 shows the network topology clustered with the above clustering algorithm for multimedia sensor networks. Suppose only Node s is capturing images at any one moment, while other nodes in the same cluster are reporting their remaining energy {е 1, е 2,
е 3, …, е m }(assuming there are m nodes in the cluster with the exception of the image capture node and cluster head) to s. First, s generates a probability  for each node based on the node’s energy, which is proportional to  the remaining energy. Then, Node s splits the captured image into 8 × 8 blocks and includes the location information of each block in the original image in order to ease image reduction. Each pixel is represented by 8 bits. Next, Node s sends the blocks to other nodes in the same cluster according to their probabilities. If there is a route to a destination node, it sends a block directly to that node; otherwise, it will send the block to the cluster head, which in turn forwards it to the destination node. Next, the nodes receiving blocks edit JPEG coding and return the processed blocks to the cluster head. As each compressed block contains location information, the cluster head is not required to integrate the blocks; hence, energy is saved. Finally, the cluster head selects a route for forwarding the processed blocks to the receiving node, where the image will be converged.

    In the short distance communication model proposed in Reference [9], the distance between two nodes is denoted as d  and energy consumed in communication is proportional to d.

    The energy consumed to send 1 bit of data is:

    The energy consumed to receive 1 bit data is:

    Where εе is the energy consumed in the path, εα is the energy consumption parameter of the signal amplifier, d  is the communication distance between the transmitting node and receiving node, and α (2 ≤ α ≤ 4) is the path loss coefficient.

    Suppose the cluster has k  nodes situated at one-hop distance from Node s, l1, l2 , …, lk  are the linear distances of these nodes to Node s; d1, d2, …, dm  are distances from the cluster nodes to the cluster head; ds  is the distance from the image capture node (i.e. Node s ) to the cluster head; dc is the distance from the cluster head to a next-hop node; and η1, η 2, …, ηm are probabilities where Node s sends the data to the cluster nodes. Let M  be the bits of the image, g  be the image’s compression ratio, W  be the energy consumed by the source node to capture the image, and C  be the energy consumed to compress each bit. The energy consumption of the image capture node s is:

    The energy consumption of any node in the cluster other than the cluster head and Node s is:

The energy consumption of the cluster head is:

    In the case of centralized compression, where the image capture node compresses an image immediately after image capture and then sends the compressed image to the cluster head, the energy consumption of the image capture node s is:

    And the energy consumption of the cluster head is:

3 Simulation Results
Matrix Laboratory (MATLAB) is used to generate a node distribution diagram, where nodes are randomly distributed in the area between (x =0, y =0) and (x =100, y =100) and the energy at each node is random, ranging from 0.3J  to 0.7J . The image capture node is randomly selected out of the non-cluster-head nodes.

    Assuming the total number of nodes N  is 150, the node threshold for each cluster is 10 and the maximum communication distance between any two nodes is 20. The clustering of these nodes may look like Figure 2.

    From Figure 2, we can see that the number of cluster heads is directly proportional to the density of nodes, that is, there are more cluster heads in the node-dense areas than node-sparse areas, but every node can join a cluster head. Moreover, the number of nodes managed by each cluster head is less than the threshold, so the loads of cluster heads are reduced.
To compare network life spans (the total times the network captures and transmits images until the energy of the first node is comsumed) in the case of centralized and distributed image compression respectively, 50 simulations were performed under the same conditions: The total number of nodes N was 300, and the node threshold for each cluster was 10. The simulation results are shown in Figure 3.

    Figure 3 demonstrates the life of the network which adopts distributed compression is obviously longer than that using centralized compression. As the nodes are randomly spread, the clustering of nodes varies considerably, causing the network life to fluctuate widely.
In contrast, the life of the network using centralized compression  fluctuates only around 100. The reason is that in centralized compression, the image capture node consumes a large amount of energy while the cluster head consumes less energy. As a result, no matter how many nodes are in the cluster, the life of the entire network is determined by the node that captures the most images.

    Figure 4 shows the life spans of a network adopting distributed image compression under different conditions: The total numbers of nodes are 300, 450, 600 and 750 respectively, and the node threshold for each cluster ranges from 1 to 50.

    As shown in Figure 4, the greater the number of  nodes, the longer the network life is. More nodes mean more clusters. Accordingly, more nodes or clusters share the image capture and compression tasks, thus the life span is prolonged. On the other hand, the network life is shortened as the node threshold for each cluster increases. Because one function of the cluster head is to forward data to the nodes in its cluster, the greater the number of nodes in the cluster, the sooner the energy of the cluster head is consumed. Simulations show that network life is the longest when the node threshold for each cluster ranges from 5 to 15.

4 Conclusions
This paper analyzes LEACH protocol and proposes an improved protocol for wireless multimedia networks. This improved protocol is designed to satisfy the scenarios where the energy of each node differs and the number of nodes varies from one cluster head to another. Moreover, it introduces a distributed image compression algorithm for the networks clustered with the above improved protocol. In the compression algorithm, energy consumption balance is achieved with the image capture node assigning compression tasks to other nodes in the same cluster. Simulation results show that distributed image compression significantly extends  network life compared with centralized image compression.

    The compression algorithm is applicable to WMSNs where the initial energy and locations of nodes are randomly distributed.

References
[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 Alamos, CA, USA: IEEE Computer Society, 2000: 10p.
[2] 杜向党, 李亦洋, 石秀华. 无线传感器网络基于类的簇头选择算法改进[J]. 传感技术学报, 2008, 21(7):
1202-1206. DU Xiangdang, LI Yiyang, SHI Xiuhua. Improved arithmetic in choice of head-note based on clustering of WSN [J]. Chinese Journal of Sensors and Actuators, 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. LIANG Ying, ZENG Peng, YU Haibin. Energy adaptive cluster-head selection for wireless sensor networks [J]. Information and Control, 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.

[Abstract] Because of the high bandwidth demands of multimedia data, the transmission of raw data collected at sensor nodes consumes a large amount of resources. Distributed image compression is proposed as a means of overcoming the computation and energy limitation of individual nodes by sharing the processing of tasks. In addition, it prolongs the overall lifetime of the network by assigning compression tasks to idle nodes.