Energy Efficient Distributed Hash Table Based Routing In Mobile Wsn

Download Full-Text PDF Cite this Publication

Text Only Version

Energy Efficient Distributed Hash Table Based Routing In Mobile Wsn

S. Gayathri, (PG Scholar) Dept of Computer science and Engg

K.L.N College of Engineering Pottapalayam, India

M. Raghini, ((AP(Sr.Gr)) Dept of Computer Science and Engg

K.L.N College of Engineering Pottapalayam, India

Abstract Wireless sensor networks (WSN) contains resource constrained characteristics in terms of limited storage capacity and limited energy. Energy consumption is the major resource in WSN. For that reason, need to implement energy efficient routing protocol in WSN. Routing is one of the most important problems in mobile WSN. The proposed work is called hierarchical Distributed Hash Table (DHT) based routing protocol for mobile WSN with mobile sensor nodes and static sink. This protocol is energy efficient and reliable routing protocol. The protocol uses the deputy cluster head (DCH) to curtail the re-clustering time and energy necessities. The procedure of joining and leaving the cluster members to or from clusters are handled by this protocol. It also handles the cluster head leave operation from the cluster. Simulation results show that DHT based routing protocol provide more network lifetime and throughput than the E2R2 protocol. It requires less average communication energy compared to E2R2 protocol.

KeywordsMobile WSN; DHT based routing; PEGASIS algorithm; CH panel; energy efficiency; reliability.


    Wireless sensor network considered as real time embedded system deployed in a particular region to sense various types of environmental parameters such as temperature, gas, humidity pressure, etc. The huge applications of WSN like habitant monitoring, surveillances, forest fire detection, transport monitoring etc. have created a lot of interest among the researcher community in recent past [1]. Typically, WSNs are densely deployed in perilous places where battery recharge or replacement is nearly impossible and human monitoring scheme is highly risky. These sensor nodes sense the data and forward towards a resourceful sink. Depending on the application type, the sink is placed either far away from the sensor field or within the sensor field. Designing energy efficient and reliable routing protocols for mobile significant WSN applications such as battlefield inspection, health monitoring and wildlife monitoring is a great challenge due to the frequent change of the network topology. Cluster-based routing protocols are measured as more energy efficient since in these protocols, cluster head produce finite valuable information from a large amount of raw sensed data by member nodes in a cluster and transmit this specific valuable information to the sink [2].

    The sensor nodes are economical, disposable, and predictable to last awaiting their energy drains out. Therefore, energy is a very restricted source for a WSN system, and it needs to be managed in a best fashion. Reliable and successful packet delivery at the sink is preferred. Energy efficiency is an important quality of any application of WSN [3]. Routing of data in WSN is an important task, and considerable amount of energy can be saved if routing can be carried out delicately. Routing is an issue linked to the network layer of the protocol stack of WSN. In multi-hop communication, the most important issue may be the selection of the intermediate nodes in the route. The intermediate nodes are to be selected in such a way that the energy requirement is minimized. At the same time, the packets are to be delivered at the sink reliably and successfully [4].

    Hierarchical routing is considered to be an energy- efficient and scalable approach. There are several hierarchical routing protocols proposed for WSN [5][9]. All these routing protocols are not fit to hold mobility of the sensor nodes. Some routing protocols to hold mobility in ad hoc networks, but this protocol not supports the WSN setup [9]. WSN have the different features and the unique constraints than the ad hoc networks. Moreover, the WSN applications have diverse sets of necessities [9]. Mobile sensor nodes are moving from one location to another, so the routing process is challenging problem in WSN.

    The major goal of the DHT based routing protocol is to achieve energy efficiency and to provide connectivity to the nodes. The objective behind the routing is that the data packets need to move in the course of proper routes in spite of node mobility and in occurrence of consequent link failures or error in the route. The DHT based routing protocol can handle the high mobility sensor nodes. The DHT based routing protocol handles the cluster member leave and joins operation from/to clusters. The protocol used the PEGASIS clustering algorithm used to reduce the number of dead nodes and energy requirements compared to LEACH protocol.


A narrative energy efficient scheme is proposed for mobile WSN. The proposed protocol, which is called hierarchical DHT based routing, it offers fault tolerance by generating multiple energy efficient routes. They are also

needed to accommodate and handle efficiently nodes failure. This hierarchical organization is practical to optimize the energy utilization by condensing data passage in cluster heads and performing large routing hops.

  1. Clustering Algorithm

    The sensor nodes are randomly deployed over a geographic region. After that clusters are formed based on the PEGASIS clustering algorithm [10]. The PEGASIS algorithm is worked based on the each and every node transmit data packet to its close neighbors until reaches the data packet to the sink. PEGASIS clustering algorithm is a chain based protocol. Using the greedy algorithm the chains are computed by the sink and transmit it to all the sensor nodes. PEGASIS algorithm will share the energy load equally to the entire sensor nodes in the network. The nodes are planned to construct a chain, which can either be talented by the sensor nodes themselves using a greedy algorithm starting from some node. The proposed protocol consists of cluster head panel. The CH panel contains one CH and two Deputy Cluster Head (DCH) nodes [11].

  2. CH Selection

    After the cluster formation, the sink selects the set of nodes to construct the CH panel from each cluster.CH panel contains three nodes which are CH and DCH nodes. CH panel nodes are elected based on the cumulative credit point (CCP) calculated from the three parameters, namely, residual energy level of the node, degree of the node (i.e., the number of neighbors), and mobility level of the node (i.e., speed range of the sensor node). Highest CCP value node is elected as CH node and remaining nodes are act as DCH nodes. CH node need to have the higher residual energy (balance energy), more number of neighbors and low mobility (speed range of the sensor nodes). In static WSN cumulative credit point calculation method was discussed in [12] to select CH and DCH. The cluster set up valid for a particular time interval that can be specified at the time of implementation. The cumulative credit point is calculated by the algorithm. CCP algorithm is executed by the sink for each cluster in the field.

    The CH node used to collect the data packet from its member. CH aggregates the collected data packet and forwards the data packet to the sink by using single hop or multi-hop fashion. This part of data packet forwarding will take place according to the communication pattern or the route distributed by the sink. According to the communication pattern data forwarding takes place. The communication pattern is distributed by the sink.

    I the node failure or link failure occur in the route of CH-sink, CH may ask the help of any one of the DCH nodes to forward the data packets towards the sink. The two DCH nodes are used to keep up the connectivity inside the clusters. This is the reason for selecting two DCH nodes.

  3. Distributed Hash Table (DHT)

    DHT is a trendy decentralized distributed system. The main benefit of DHT is its efficient lookup service. Data in DHT is organized into (key, value) pairs. The DHT system

    uses the nodes unique identifier (UID) as the key value. CH and DCH maintain the DHT. DHT contains the information of nodes UID and respective node information. A node distributes their UID to the neighbors nodes. Using this UID any one node can get the particular nodes information from the CH-DHT. Sink, may also get the any nodes information from the CH-DHT using the UID.

  4. Unique Identifier Assignment

    Sink assigns a unique identifier to each and every cluster head. For example 1,2,3, etc. CH generates a random number and it can be append with CH unique identifier and this identifier is assigned to a Cluster Member (CM) and DCH nodes. For example CH generates a random number 16 then it will append to CHs unique identifier 1 and get (116) which is unique identifier of cluster member. While CH generating random number it checks the random number of other cluster member, if the random number is assigned to some other nodes it will generate new random number. So, it can easily identify the particular CM belongs to which cluster. These unique identifiers are valid for a particular time interval. Fig.1 depicts the unique identifier assignment of CH and CM.

    Once the unique identifier assigning of the nodes is complete, the hashing of nodes based on these unique identifier takes place. DHT uses the unique identifier as the key value. Each and every cluster head and DCH maintains DHT. Using this unique identifier, cluster members residual energy, mobility information, location information and neighbors list informations are stored in the CH-DHT and DCH-DHT. DCH collect this information from the cluster member and sent to the CH. Based on the DHT information CH generates multiple path for routing. This routing strategy saves energy in cluster member without causing bottlenecks in cluster heads. DCH send the list of all keys to the sink. Therefore, sink can be able to lookup the information of cluster members from CH-DHT or DCH-DHT.

  5. Cluster Member Joining Operation

    If a new node wants to join the DHT system, it sends a join message to an existing node. This message will be forwarded from a node to another until reaching the node cluster head. Fig. 2 depicts, N1 sends the join request message to the nearest neighbor until it reaches the CH. CH generates a unique identifier and key that will sent to the node N1. N1 sends the residual energy, mobility information, location information and neighbors list informations to the CH. CH updates the DHT with the new cluster member information.

    identifier is revoked from the CH and it is assigned to DCH.

    Fig. 3. Cluster member leave operation.


    Fig. 1. Unique identifier assignment.

    Fig. 2. Cluster member join operation.

  6. Cluster Member Leave Operation

    If a cluster member wants to leave from the DHT system, it sends a leave message to the CH. Fig. 3 depicts, N1 sends the leave request message to the CH. CH delete the information of N1 from the DHT and N1s unique identifier, may be assigned to some other new joining nodes.

  7. CH Leave Operation

    Due to the node mobility, the CH node drops the connectivity to its cluster member nodes. This process affects the throughput level at the sink in terms of data packet delivery to the sink. In that circumstance, the CH wants to leave from cluster. So, CH sends the leave request message to the sink. Sink inform the CH to surrender the charge of cluster headship. The sink may give the cluster head job to one of the two DCHs. This arrangement saves the considerable amount of time and cost of selection procedure of CH. In Fig. 4 shows the CHs unique

    CH DCH

    Fig. 4. Cluster headship gets shifted to DCH.

  8. CH-Sink Network Creation

    The CH and DCH update their location information with the sink; the DCH nodes send the cluster members key to the sink. Using this key sink can collect the cluster members information. Based on this information sink computes more number multi-hop routes for each of the CH node. By taking into consideration the CH nodes only, the routes are generated. A graph H is constructed by using the CH nodes in the field of sensor nodes. Graph H shows the connectivity among the CH nodes. Based on the CH nodes radio ranges and the geographic locations the links are generated by using graph H. Then the sink generates multiple spanning tree [10] based routes for each of the CH-sink itself. The root of the spanning tree is BS. By considering each CH, the sink generates a detach pool of multi-hop routes. Each CH node gets the energy efficient route from the sink.

  9. Energy expenditure of a route

Let consider route R in (1). Route R contains m edges.

So the total number of node involved in the route is m+1.

R = {a, b, c, , g, h}.


Consider above route R, here a is a source node and h is a destination node.

The total energy expenditure of a route is calculated by using the sum of energy expenditures of the edges in the route. Energy expenditure is depends on the sum of transmission and reception expenditure.

Then, the total energy expenditure involved in R can be calculated by using as (2) and (3).


EER = [ ETx (k, da,b) + ERx(k) ] + [ETx(k, db,c) + ERx(k)

]+. + [ ETx(k, dg,h) + ERx(k) ].


EER = [ETx(k, da,b) + ETx(k, db,c) + .. + ETx (k, dg,h)]+ n × ERx(k).


Energy expenditure for transmitting a data packet of size k bit between two nodes being separated and the distance between the nodes is d unit. It is expressed in (4).

Energy expenditure for receiving a data packet of size k bit between two nodes. It is expressed in (5).

ETx(k, d) = k(Eelec + amp × d).


ERx(k) = k × Eelec.


Where path loss exponent; Eelec denotes the energy consumption caused by digital coding, modulation, filtering, and spreading of the signal; and amp is the energy consumed by the transmitter power amplifier.

The route is valid only for a particular time interval T. After this time interval T, the sink sends the alternate route to the CH. This technique avoids the failure of intermediate node.

The condition for selecting a multi-hop route:

A multi-hop route must acquire less energy expenditure than a direct route.

Consider the nodes x, y and z. Node x is a source node, y is a relay node or intermediate node and z is a destination node. Node x wants to transmit the data packet to node z. The aim is node x transmit the data packets to node z with the minimum energy requirements. The position of node z is (a, b).

If the following condition is true then only node y acts as a relay or intermediate node. Otherwise direct transmission takes place.

Rx->y = {(a, b)|Ex->y->(a, b) < Ex->(a, b)}.

Here, R indicates need of relay, and E indicates energy requirement. Now, the obtainable equation can be interpreted as follows: The energy requirements of transmitting the data packet to the source node x to destination node z with the help of relay node y require less energy compared to direct transmission of node x to node z, where y is located at (a, b).

The sensor nodes are act as active state or dormant state. Some sensor nodes are programmed for dormant state (low-power state). If a node in low-power state, it does not perform sensing and relaying activities. This process can be opted when the observation of two sensor nodes are in very close proximity. There is a very high chace of they sense the similar and redundant data from its surrounding environment. On the basis of the location information and proximity of the nodes, the CH schedules the some sensor nodes into low-power state. In that way the coverage area of the network does not get affected. Again, at later some time, the node will get state transition from its low-power state to the active state as informed by the CH.

The sink dispense the time-division multiple access (TDMA)- based medium access time slot to the CH and DCH nodes from the each cluster. This process enables the communication with the sink. So that different CH nodes use different frequency bands so the communication is done by simultaneously. The CH nodes dispense the TDMA-based medium access slot to their cluster members, to enable the communication with the cluster head. So that different cluster member (CM) nodes use different frequency bands so the communication is done by simultaneously.


Fig. 5. Average communication energy

The above Fig. 5 depicts the DHT based routing protocol requires less communication energy compared to E2R2 protocol. If the area of the network is increased, then the average communication energy also increased. This is

because of the fact that long-distance communication requires more energy expenditure than the short-distance communication.

It has been observed in the below Fig.6 if the data rate is increased, then the throughput is decreased for both the DHT based routing and E2R2 protocols. Although, the DHT based routing protocol outperforms the E2R2 protocol in terms of throughput.

Fig. 6. Throughput

Fig.7 depicts the DHT based routing protocol outperforms E2R2 in terms of lifetime. If the data rate is increased, then the lifetime is decreased in both the proposed and E2R2 protocols. In the higher data rate, the nodes need to handle more number of data packets. So the nodes are loss the more energy. Thus, more energy expenditures acquire, and this leads to reduced lifetime.

Fig. 7. Lifetime


The DHT based routing protocol is hierarchical and cluster based protocol; it maintains CH-DHT and DCH- DHT. The protocol contains CH panel. CH panel contains one CH node, and the CH node is helped by two DCH nodes. DCH nodes are also called cluster management nodes. Cluster member and CH leave operation and cluster member join operation can be done with the help of DHT. The DHT based routing protocol outperforms E2R2 in terms

of lifetime and throughput. The protocol achieves the fault tolerance by providing multiple links. The DHT based routing protocol requires less communication energy compared to E2R2 protocol. The protocol is useful when the sensor nodes are in mobile and sink is in static like health monitoring of animals and plants, animals can have sensors attached to them in order to track their movements for feeding habits, migration patterns or other research purposes, environment mapping or surveillance and event mapping applications. This protocol can manage the highly dynamic sensor nodes.


  1. Amal N. Al-Karaki, Ahmed E. Kamal, Routing Techniques In Wireless Sensor Networks: A Survey, IEEE Wireless Communications, Volume:11, Issue: 6, 26- 28, December 2004.

  2. W. R. Heinzelman, A. Chandrakasan, and H. Balakrishnan, Energy- efficient communication protocol for wireless microsensor networks, in Proc. IEEE Comput. Soc. 33rd Annu. Hawaii Int. Conf. Syst. Sci. (HICSS), Jan. 2000, pp. 110.

  3. W. Heinzelman, A. Chandrakasan, and H. Balakrishnan, Energy- efficient communication protocol for wireless microsensor networks, in Proc. 33rd Annu. HICSS, 2000, pp. 110.

  4. S. Abarna,N. Arumugam Performance Comparison of Various Energy Aware Protocols for WSN Applications PG Scholar, Department of ECE National Engineering College Kovilpatti, Tamil Nadu, India IJIREC Volume 1, Issue 9, December 2014, PP 1-8.

  5. K. Latif, M. Jaffar, N. Javaid, M. N. Saqib, U. Qasim, Z. A. Khan$ ¨ performance Analysis of Hierarchical Routing Protocols in WirelessSensor Networks.

  6. Aarti Jain and B. V. Ramana Reddy, A Novel Method of Modeling Wireless Sensor Network Using Fuzzy Graph and Energy Efficient Fuzzy Based k-Hop Clustering Algorithm Springer – Wireless Personal Communications, vol 82, pp. 157-181, 2015.

  7. Aziz MAHBOUB, Mounir ARIOUA, El Mokhtar EN-NAIMI, and Imad Ez-Zazi, Multiple zonal approach for clustered wireless sensor Networks, 2nd International Conference on Electrical and Information Technologies ICEIT, 2016.

  8. D. Ganesan, R. Govindan, S. Shenker, and D. Estrin, Highly- resilient,energy-efficient multipath routing in wireless sensor networks, ACMSIGMOBILE Mobile Computer Communication Revised, vol. 5, no. 4, pp. 1024,Oct. 2001.

  9. D. Yi and H. Yang, HEER A delay-aware and energy-efficient routing protocol for wireless sensor networks, Elsevier – Computer Networks, Vol. 104, pp.155 173, 2016.

  10. S. Lindsey and C. S. Raghavendra, PEGASIS: Power-efficient gathering in sensor information systems, in Proc. IEEE Aerosp. Conf., 2002, pp. 11251130.

  11. Hiren Kumar Deva Sarma, Rajib Mall, Avijit Kar, E2R2:Energy- Efficient and Reliable Routing for Mobile Wireless Sensor Networks, in IEEE systems journal,vol.10, no.2, pp. 604-616, June 2016.

  12. H. K. Deva Sarma, A. Kar, and R. Mall, A cross layer based energy efficient routing protocol for wireless sensor networks, presented at the Indo-US Workshop System Systems Engineering, IIT, Kanpur, India, Oct. 2628, 2009, pp. 18.

13] Ghofrane Fersi, Wassef Louati and Maher Ben Jemaa, Distributed Hash table-based routing and data management in wireless sensor networks: a survey, in Springer Wireless Networks Journal, vol.19, pp.219-236, 2013.

  1. Seungjae Shin, Uichin Lee, Falko Dressler and Hyunsoo Yoon, Motion-MiX DHT for Wireless Mobile Networks, in IEEE Transaction on Mobile Computing, vol. 15, No. 12, December (2016).

  2. Aline Carneiro Viana , Marcelo Dias de Amorim , Serge Fdida, and Jose´ Ferreira de Rezende, Self-organization in spontaneous networks: the approach of DHT-based routing protocols, in Ad Hoc Networks, Vol. 3, pp. 589-606, 2005.

Leave a Reply

Your email address will not be published. Required fields are marked *