An Energy Efficient Routing Algorithm based on Data Compression in LEACH-C

An Energy Efficient Routing Algorithm based on Data Compression in LEACH-C

1. Swathi (PG Scholar)

   Department of Electronics and Communication Engineering

   Bannari Amman Institute of Technology Sathyamangalam, India

2. Kirubakaran (Asst.Prof-Sr. Grade) Department of Electronics and Communication

   Engineering

   Bannari Amman Institute of Technology Sathyamangalam, India

   Dr. S. Valarmathy( Prof & Head)

   Department of Electronics and Communication Engineering Bannari Amman Institute oof Technology Sathyamangalam, India

   AbstractA wireless sensor network is made up of spatially distributed autonomous sensors to monitor physical or environmental conditions. The sensor nodes cooperatively pass on their data to a main location which in turn are deployed in large numbers depending upon the application where it is used In modern days the process is bidirectional where the sensor activity can be monitored. The longevity in network lifetime is necessary as they have limited battery power which is to be used efficiently. This has led to new horizons upon energy saving and reduced power consumption among sensor nodes. Thus an energy efficient routing algorithm has been proposed using data compression in the LEACH-C protocol. Lempel-Ziv-Welch (LZW) data compression has been used for compressing data based on LEACH-C protocol.

   KeywordsWSN, LEACH, LEACH-C, Network lifetime, LZW compression.

   1. INTRODUCTION

      Wireless Sensor Networks are tiny sensor nodes with the main purpose of sensing, computation and communication about physical and environmental activities which in turn is used in wide range of applications such as civilian, healthcare, habitat monitoring etc., in our day to day life. WSNs are battery operated sensing devices where replenishing the batteries is impossible and hence an energy saving method has to be employed to save power.

      Routing is an important concept in sensor networks as they deal with the process of data dissemination and data gathering after which the shortest possible and efficient path to reach the destination is chosen. In WSNs routing may be divided into flat routing and hierarchical routing [1]. In flat routing, nodes are similar in carrying out tasks which proves to be a disadvantage when it comes to a larger environment. In flat routing the energy in wasted at times of data processing and thus the limited bandwidth which is allocated has not been used efficiently

      C. Kamalanathan(Asst.Prof-Sr.Grade) Department of Electronics and Communication Engineering

      Bannari Amman Institute of Technology Sathyamangalam, India

      In hierarchical routing nodes are dissimilar in the tasks which they carry out. Thus in terms of energy they prove to be efficient when compared to flat routing as they utilize the bandwidth efficiently. [2],[3]. Clustering technique has been introduced in which there is a Cluster Head (CH) and the respective cluster members. Nodes with less energy are chosen as cluster members and that with high energy are chosen are cluster heads which then carry out the sensing process.

      The paper is organized as follows: Section II provides an overview of the LEACH and LEACH-C protocol and their comparison. In Section III the problem statement has been discussed . Section IV an overview of LZW data compression technique which is employed based on LEACH-C is given . Section V provides the simulation results. Finally we conclude the paper in Section VI.

   2. CLUSTER BASED ROUTING PROTOCOLS

      1. CLUSTERING

         A WSN consists of hundreds or thousands of nodes deployed based on the application with a centralized Base Station (BS). Clustering based protocols prove to be efficient as these protocols unlike others partition the area into smaller regions. Each region has its Cluster Head (CH) and the cluster members (CM). Hence energy has been efficiently used and does not waste the allocated bandwidth.

         Cluster-based routing is mainly two-stage routing method, where the first stage is used to clustering and selecting cluster head for each cluster. Cluster head performs data aggregation and fusion to decrease transmitted packets. The second stage is used to sense and route data, but, most techniques in

         cluster-based routing focused on the first stage which is who and when to send or aggregate the data, channel allocation etc.

      2. LEACH

         The LEACH protocol (Low-energy Adaptive Clustering Hierarchy) presented by Heinzelman et al. partitions the nodes into clusters and in each cluster a dedicated node, the cluster head, is responsible for creating and maintaining a TDMA schedule; all the other nodes of a cluster are member nodes. To all member nodes, TDMA slots are assigned, which can be used to exchange data between the member and the cluster head; there is no peer-to-peer communication. With the exception of their time slots, the members can spend their time in sleep state. The cluster head aggregates the data of its members and transmits it to the sink node or to other nodes for further relaying.[4]. Since the sink is often far away, the cluster head must spend significant energy for this transmission.

         The protocol is organized in rounds and each round is subdivided into a setup phase and a steady-state phase . The setup phase starts with the self-election of nodes to cluster heads. In the advertisement phase, the cluster heads inform their neighbourhood with an advertisement packet. The cluster heads contend for the medium using a CSMA protocol with no further provision against the hidden-terminal problem[5].. The non cluster head nodes pick the advertisement packet with the strongest received signal strength. In the following cluster-setup phase, the members inform their cluster head (join), again using a CSMA protocol. After the cluster setup-phase, the cluster head knows the number of members and their identifiers.

         It constructs a TDMA schedule, picks a CDMA code randomly, and broadcasts this information in the broadcast schedule sub-phase. After this, the TDMA steady-state phase begins. Because of collisions of advertisement or join packets, the protocol cannot guarantee that each non cluster head node belongs to a cluster[6]. However, it can guarantee that nodes belong to at most one cluster. The cluster head is switched on during the whole round and the member nodes have to be switched on during the setup phase and occasionally in the steady-state phase, according to their position in the clusters TDMA schedule. LEACH would not be able to cover large geographical areas of some square miles or more, because a cluster head two miles away from the sink likely does not have enough energy to reach the sink at all, not to mention achieving a low BER. If it can be arranged that a cluster head can use other cluster heads for forwarding, this limitation can be mitigated.

         Figure 1. Organization of LEACH

      3. LEACH-C

      LEACH-C (LEACH-Centralized), a protocol that uses a centralized clustering algorithm and the same steady-state protocol as LEACH (e.g., nodes send their data to the cluster-head, and the cluster head aggregates the data and sends the aggregate signal to the base station). During the set-up phase of LEACH-C, each node sends information about its current location and energy level to the base station. The base station runs an optimization algorithm to determine the clusters for that round. The clusters formed by the base station will in general be better than those formed using the distributed algorithm[7]..

      However, LEACH-C requires that each node transmit information about itslocation to the base station at the beginning of each round. This information may be obtained by using a global positioning system (GPS) receiver that is activated at the beginning of each round to get the nodes current location.

   3. PROBLEM STATEMENT

      A sensor node is a tiny device that includes three basic components: a sensing subsystem for data acquisition from the physical surrounding environment, a processing subsystem for local data processing and storage, and a wireless communication subsystem for data transmission. In addition, a power source supplies the energy needed by the device to perform the programmed task. This power source often consists of a battery with a limited energy budget. In addition, it could be impossible or inconvenient to recharge the battery, because nodes may be deployed in a hostile or unpractical environment[5]. On the other hand, the sensor network should have a lifetime long enough to fulfill the application requirements. In many cases a lifetime in the order of several months, or even years, may be required. Thus, the design of Energy-saving routing algorithm is very important to prolong the life time of the sensor node.

   4. PROPOSED SYSTEM

      1. LEACH-C- BASE STATION CLUSTER FORMATION

         During the set-up phase of LEACH-C, each node sends information about its current location and energy level to the base station. The base station runs an optimization algorithm to determine the clusters for that round. The clusters formed by the base station will in general be better than those formed using the distributed algorithm. However, LEACH-C requires that each node transmit information about its location to the base station at the beginning of each round[6],[7]. This information may be obtained by using a global positioning system (GPS) receiver that is activated at the beginning of each round to get the nodes current location. The life time of the cluster head is increased due to the randomized rotation of the cluster. Based on the energy level the cluster head is selected. The sensor node with higher energy is converted as the cluster head.

         Figure 2. Cluster head selection based on energy level

      2. IMPLEMENTATION OF LZW(LEMPEL-ZIV-WELCH) COMPRESSION IN LEACH-C

         LempelZivWelch (LZW) is a universal lossless data compression algorithm . The algorithm is simple to implement, and has the potential for very high throughput in hardware implementations. It was the algorithm of the widely used Unix file compression utility compress, and is used in the GIF image format. A particular LZW compression algorithm takes each input sequence of bits of a given length (for example,

         12 bits) and creates an entry in a table (sometimes called a "dictionary" or "codebook") for that particular bit pattern, consisting of the pattern itself and a shorter code.

         Figure 3. LZW Compression

         As input is read, any pattern that has been read before results in the substitution of the shorter code, effectively compressing the total amount of input to something smaller. Unlike earlier approaches, known as LZ77 and LZ78, the LZW algorithm does include the look-up table of codes as part of the compressed file. The decoding program that un-compresses the file is able to build the table itself by using the algorithm as it processes the encoded input.

         1. Encoding

            • Initialize the dictionary to contain all strings of length one

            • Find the longest string W in the dictionary that matches the current input

            • Emit the dictionary index for W to output and remove W from the input

            • Add W followed by the next symbol in the input to the dictionary

            • Go to Step 2

              A dictionary is initialized to contain the single- character strings corresponding to all the possible input characters (and nothing else except the clear and stop codes if they're being used). The algorithm works by scanning through the input string for successively longer substrings until it finds one that is not in the dictionary. When such a string is found, the index for the string without the last character (i.e., the longest substring that is in the dictionary) is retrieved from the dictionary and sent to output, and the new string (including the last character) is added to the dictionary with the next available code. The last input character is then used as the next starting point to scan for substrings.

         2. Decoding

      The decoding algorithm works by reading a value from the encoded input and outputting the corresponding string from the initialized dictionary. In order to rebuild the dictionary in the same way as it was built during encoding, it also obtains the next value from the input and adds to the dictionary the concatenation of the current string and the first character of the string obtained by decoding the next input value, or the first character of the string just output if the next value cannot be decoded (If the next value is unknown to the decoder, then it must be the value that will be added to the dictionary this iteration, and so its first character must be the same as the first character of the current string being sent to decoded output). The decoder then proceeds to the next input value (which was already read in as the "next value" in the previous pass) and repeats the process until there is no more input, at which point the final input value is decoded without any more additions to the dictionary.

   5. SIMULATION AND RESULTS

      The simulation is carried out using NS-2 tool. The cluster heads are selected based on LEACH-C protocol after which randomized rotation of cluster heads take place. Data compression is done by entering data to nodes. Compression takes place at the respective cluster heads. Decompression is done at the base station.

      1. PERFORMANCE OF LEACH AND LEACH-C

         The LEACH and LEACH-C performance are conducted on the parameter of the time and energy. The time is given in the x-axis and the energy is given in the y-axis.

         Figure 4. Comparison based on Energy

         In the Figure 4. the Energy level of the leach and leach-c protocol as been displayed with respect to time. In the initial state both are at the same energy level. In case of leach they perform a poor clustering set up during a given round thus energy level decreases drastically but in case of the leach-c protocol they perform centralized clustering algorithm and also randomized rotation of the cluster head so energy is reduced gradually. Thus LEACH-C consumes less amount of energy.

      2. PERFORMANCE OF COMPRESSED AND UNCOMPRESSED DATA

      The time is given in the x-axis and the energy is given in the y-axis. In the Fig 5 the data is transferred without compression it consumes large amount energy but When the data is transferred with compression they consume only less amount of energy

      Figure 5. Energy of Compressed and Uncompressed data

   6. CONCLUSION

The sensor node selects their cluster head based on their energy level. The sensor node with higher energy is represented as the cluster head .Implementing LEACH-C protocol, the life time of the cluster head has been increased (cluster head performs randomized rotation based on the energy level) and by using data compression technique only less amount of energy has been consumed during the transmission of the data thus the energy is saved and life time of the sensor node has been increased.

REFERENCES

1. Y. Yu, V.K. Prasanna, and B. Krishnamachari, Information Processing and Routing in Wireless Sensor Networks, chapter 1, World Scientific Pub Co Inc, 2006.

2. A.M. Zungeru, L. Ang, and K.P. Seng, Classical and swarm intelligence based routing protocols for wireless sensor networks: A survey and comparison, Journal of Network and Computer Applications, vol. 35, no. 5, pp. 15081536, September 2012.

3. M.C. Arboleda and N. Nasser, Compaison of clustering algorithms and protocols for wireless sensor networks, in Canadian Conference on Electrical and Computer Engineering, CCECE 06.

4. W.R. Heinzelman, A. Chandrakasan, and H. Balakrishnan, Energy-efficient communication protocol for wireless microsensor networks, in Proceedings of the 33rd Annual Hawaii International Conference on System Sciences.

5. O. Younis and S. Fahmy, Heed: a hybrid, energy efficient, distributed clustering approach for ad hoc sensor networks, IEEE Transactions on Mobile Computing, 2004.

6. M. Chatterjee, S.K. Das, and D. Turgut, WCA: A Weighted Clustering Algorithm for M obile Ad Hoc Networks, ClusterComputing, pp. 193-204, 2002.

7. M . J. Handy, M . Haase, D. Timmermann, Low energy adaptive clustering hierarchy with deterministic cluster-head selection [C], Proceedings of IEEE International Workshop on Mobile and Wireless, Communications Networks, 2002, 368- 372

8. Jian Xu, Dandan Qin A new LEACH-Based Routing Clustering Protocol in WSN, Journal of information & computational Science (2013), 6005-6011, http://www.joics.com.