Energy Efficient Leader Election and Congestion Aware Protocol for Wireless Sensor Networks

Energy Efficient Leader Election and Congestion Aware Protocol for Wireless Sensor Networks

Meera Jadhav

Department of Computer Science & Engineering, NMIT-Bangalore-560056, VTU (INDIA)

Abstract Cluster-based architectures are one of the most practical solutions in order to cope with the requirements of large-scale wireless sensor networks (WSNs). Cluster-head election problem is one of the basic Quality of Service (QOS) requirements of WSNs, yet this problem has not been sufficiently explored in the context of cluster-based sensor networks. It is not known how to elect the best candidates for the cluster head roles. We check the cluster-head election problem and congestion management problem in CBEEC protocol. The results were obtained using Network Simulator- 2(ns2).

Keywords Wireless Sensor Networks, Cluster Protocol, Congestion Aware, Energy Efficiency, Cluster-head selection, Information Routing.

1. INTRODUCTION

   Wireless Sensor Networks can offer unique benefits and versatility with respect to low-power and low-cost rapid deployment for many applications. The nodes in WSN are deployed in remotely which do not require human supervision. The nodes in WSNs are usually battery oriented sensing devices with limited energy resources and replacing or replenishing the batteries is usually not an option. Thus energy efficiency is one of the most important issues and designing power-efficient protocols is critical for prolonging the lifetime. The latest developments are time critical, low cost, long battery life, and low data rate wireless applications have led to work on WSNs. These WSNs have been considered for work in certain applications with limited power, reliable data transfer, short communication range, and reasonably low cost such as industrial monitoring and control, home automation and security, and automotive sensing applications [2]. Specific functions can be obtained through cooperation between these nodes functions such as sensing, communicating, tracking, and alerting [3]. These functions make these wireless sensors very useful for monitoring natural phenomena, environmental changes, controlling security, estimating traffic flows, monitoring military application, and tracking friendly forces in the battlefields. WSNs have inherent and unique characteristics compared with traditional networks [1, 2]. These networks have many limitations such as computing power, storage space, communication range, energy supply and etc. Nodes have limited primary energy sources and in most of applications they are not rechargeable, therefore energy consumption is the most important factor in routing process for wireless sensor networks. The energy present in the nodes is consumed due to sensors sensing the information, processing information and communicating with other nodes.

   Communications are the main element in energy consumption. Routing protocol directly affects communications volume; therefore energy aware routing protocols are very effective in decreasing energy consumption [4].

   A wireless sensor network (WSNs) consists of spatially distributed autonomous sensors to monitor physical or environmental conditions, such as temperature, sound, pressure etc to cooperatively pass their data through the network to a main location. The WSN is built of "nodes" number may vary from a few to several hundreds or even thousands of nodes. Each node is connected to one or many sensors.

   A sensor network consists of a large number of nodes which are deployed densely and are placed closely for the phenomenon to be monitored. Each of these nodes collects data and its main purpose is to route this information back to a sink. The network must possess self-organizing capabilities since the positions of individual nodes are not predetermined. Nodes in sensor network cooperation among themself to disseminate the information gathered from the environment which is the dominant feature for this type of network.

   A sensor node working depends on the algorithm used. The sensor nodes are typically expected to operate with batteries and are often deployed to not-easily-accessible or hostile environment, sometimes in large quantities. It can be difficult or impossible to replace the batteries of the sensor nodes. On the other hand, sink is typically rich in energy. Since the sensor energy is the most precious resource in the WSN, efficient utilization of the energy to prolong the network lifetime has been the focus of much of the research on the WSNs.

   Routing protocols which only consider energy as their parameter is not efficient. In addition to energy efficiency, we need to consider other parameters to make routing protocol more efficient. Depending on the applications, different parameters should be considered. Among all one of the most important parameter is congestion management. Occurrence of congestion leads to increasing packet loss and network energy consumption. There is different reason for congestion occurring in wireless networks; firstly, due to limited storage capacity in relay nodes. Whenever a node receives packets more than its capacity, congestion will occur. Secondly, due to the shared wireless link, congestion occurs for similar reasons in wireless sensor networks [5].

   The different ways to manage congestion in WSN are divided into two groups: congestion avoidance and congestion control. In congestion avoidance we focus on avoiding congestion from happening and in congestion control we remove congestion when it has occurred. Wireless sensor networks lack in resources, so avoiding congestion rather than controlling congestion is more reasonable.

2. RELATED WORK

   In order to enhance the network lifetime, network is partitioned into smaller clusters and each cluster is monitored and controlled by a node which is called as Cluster-Head (CH). The role of cluster-head is to monitor all the activities of the nodes in a cluster. Cluster-heads can communicate directly with the base station (BS). Other nodes of the cluster send the data, which they have sensed from the environment to the CH. CHs first aggregate the data from the multiple sensor nodes, and then finally send it directly to the BS [6]. The cluster-head are selected based on a distributed algorithm for each round. To avoid the congestion, congestion is divided in to two traffic types namely: high priority and low priority. It selects a special area in network which is called con-zone. The nodes which are placed in con-zone forward only high priority traffic and other network nodes forward other traffics. Reference [7] proposes two algorithms: CAR and MCAR. CAR is a network-layer solution to provide differentiated service in congested sensor networks. CAR also prevents severe degradation of service to low priority data by utilizing uncongested parts of the network. MCAR is primarily a MAC-layer mechanism used in conjunction with routing to provide mobile and light weight con-zones to address sensor networks with mobile high priority data sources and/or busty high priority traffic.

   The proposed CBEEC algorithm assumes that all nodes receive the messages broadcasted by the nodes which are elected as cluster heads. On one hand, if a node is not reachable by a cluster head it assumes that the number of clusters heads is not sufficient, and elects those nodes to be cluster-head. In a network the number of clusters and cluster- head will be identified dynamically. The congestion in the network will differ from time to time. Routing in the network has been divided into Inter-cluster routing and Intra-cluster routing.

3. PROPOSED PROTOCOL/h4>

The CBEEC protocol is divided into three phases (i) Network clustering (ii) Creating routing tree (iii) Data forwarding. In the first phase which is network clustering phase, network nodes are partitioned into different clusters. During this phase cluster nodes information are delivered to cluster head. In creating routing tree phase, a limited routing tree path will be created. During this phase a routing table is created for each of nodes in the cluster. In data transmission phase, packets are forwarded using relay nodes routing table.

Routing table is updated whenever the node moves from the range of one cluster head to the range of another cluster-head. After the cluster are formed. Cluster members sent the sensed data to CH directly or use relay nodes. The choice of the relay nodes depends if that node is having more connectivity. Only the nodes which have more number of children connected to it that node is selected as a relay node. By doing so the chances of sending the data to CH is more and chances of dropping the packets is less. CH receives the data sent from the cluster members, aggregate the data and send the aggregated data to the sink. CH will sent the aggregated data to the sink directly, if it cannot send the data directly it makes used of other cluster-head. In some cases when two cluster-head cannot communicate with each other they make use of gateway nodes. Gateway nodes sent the data which is received from other cluster-head to sink.

1. Network Clustering

   In network clustering phase the network nodes are partitioned into various clusters. During the clustering phase, a node is called as cluster head will be elected for each cluster [10]. At the end of this phase, information about all of the nodes which belong to that cluster is delivered to cluster head. Each node in cluster sends its own information to the sink directly. It is important to know that, this phase is done once; therefore direct communication between cluster nodes and the cluster head is negligible [5].This clustering information is updated whenever the network node moves from the range of one cluster-head to another. The routing table which is an event driven will be updated. In CBEEC algorithm, it is a self-organizing, dynamic clustering method that divides the network dynamically on a number of a priori fixed clusters. Each cluster has one cluster-head. Here we use two-level heterogeneous networks, in which there are two types of sensor nodes: the advanced nodes and normal nodes. Depending on the energy level that is present in each node. Let the E0 initial energy of the normal nodes and, f the fraction of the advanced nodes, which own a times more energy than the normal ones. Thus there are f.N advanced nodes equipped with initial energy of (1+a) E0 and (1-f) N normal nodes with initial energy E0 [6]. Where N is the energy of the normal nodes & f is the energy of advance node which has more energy than the normal nodes.

   E total =N (1-f) E0+Nf (1+a) E0.

   1. Setup Phase

      Every transmission round, each node n uses the Formula

      Where p is the predetermined percentage of cluster heads (e.g., p = 0.05), r is the current round and G is the set of nodes that have not been cluster heads in the last 1/p rounds. Using this threshold, each node will be a cluster head at some round within 1/p rounds. After 1/p rounds, all nodes are once again eligible to become cluster heads. The elected node plays the role of cluster-head for 67th transitions based on paper [4].

      Algorithm for Setup Phase and Steady Phase:

      In Setup phase:

      Step 1.CN=>r

      Step 2.If r<T (n) then, CH=CN else Go to step 1

      Step 3.CH=>G: id (CH), join-adv Step 4. A (i) ->CH (j): id (A(i)),

      Id (CH (j)), join_req Step 5.CH (j) ->A (i): id (CH (j)),

      < t (i),id(A(i))>

      In Steady Phase:

      Step 1.A (i) ->CH (j): id (A(i)),

      id (CH (j)), info

      Step 2.Ch->BS:id(CH),id(BS),

      aggr_info

      Terms abbreviations used in clustering algorithm:

      • CN: Candidate node to become the CH

      • r: random variable(0<r<1)

      • T (n): threshold value

      • ->unicast

        =>broadcast

      • CH: Cluster Head

      • BS: Base Station

      • G: all nodes in the network

      • Id: identification number of a node

      • Join_adv: advertisement to join the cluster

      • A: normal node

      • Join_adv: request to join the cluster.

      • T: time_slot to send the sensed data.

        to calculate the value and choose a random number between 0 and 1. Threshold is calculated based on the cluster-head formula. The threshold value lies between 0-1. Candidate nodes to become a cluster head select a random number between 0 and 1. If chosen number is less than threshold value, then candidate node is the CH. The elected cluster-head will play the role of cluster-head based on [7]. CH node broadcast an advertisement message containing its id to all nodes in the network. Nodes in the communication range of that particular cluster-head send a join request to the selected CH based on the signal strength. Receiving this message, the not cluster head nodes belong to the cluster which the energy to join is minimum among all selected cluster-heads. The node can

        determine the needed energy to transmit to the cluster head based on the received signal strong. High the signal strength the closer the CH is located. Once the nodes decide to which cluster it belongs, they inform the cluster-head transmitting a join-request message to it, using CSMA/CA MAC protocol. A header, the node ID and the cluster-head ID, forms this message, which is a short one. This message size grants to reduce the time channel access and the transmission energy cost [7].

   2. Steady-State Phase

      Once the clusters are established, the nodes transmit their data messages towards the cluster-head. Within the cluster, the communication uses TDMA, as described in the set up phase. When the cluster-head receives all the nodes data, it performs its compression, to form a new message that sent to the base station. The network function is divided into cycles, each cycle lasts for m transmission rounds. Then, selected nodes for cluster-heads play this role for m consecutive transmission rounds. It is so difficult to determine analytically the parameter m, because the nodes deployment is random and the cluster-heads position is also stochastic, then we determine this optimal value based on simulation [7].

      Network function is divided into cycles and each cycle lasts for m transmission rounds. The node which is elected has cluster-heads play this role for m consecutive transmission rounds. It is so difficult to determine analytically the parameter m, because of the random deployment of the nodes and the cluster-heads position is also stochastic, then we determine this optimal value based on simulation [7].

2. Creating Routing Tree Phase

   In this phase, a routing tree structure, for every node in that cluster a path to its cluster head is determined. Cluster head knows position of all nodes which are located in its cluster. Cluster head evaluates link cost between every two nodes located in their communication range [9]. For determining link cost, CBEEC protocol uses

   • CF0 (Communication Cost) = where c0 is a weighting constant and the parameter L equals to 2 which depends on the environment. This factor is the cost of the wireless transmission power, which is directly proportional to the distance raised to some power L. If the nodes are closer to the destination than faster they can transfer information.

   • CF1 (Energy stock) = this factor is the primary battery lifetime, which favours those nodes with have more energy [11]. The more energy the node contains, the better it is for routing. The more the energy the node has the longer it can transfer the data and longer timethe simulation can be extended.

   • CF2 (Sensing-state cost) = where c2 is a constant added when the node j is in a sensing state. This factor does not favour selecting sensing enabled nodes to serve as relays. It is preferred not to over- load these sensing nodes in order to keep functioning as long as possible.

   • CF3 (Error rate) = where f is a function of distance between nodes i and j and buffer size on node j (i.e. distij / buffer _ size). The links with high error rate will increase the cost function, thus will be avoided. Cluster head using nodes information, links cost and Dijkstra algorithm selects least cost route between every cluster member node and cluster head. Using Dijkstra algorithm, route selected between every node and cluster head is optimum and only one path is selected between each node and cluster head

   therefore the set of all routes has a tree structure called routing tree.

   Cluster head using nodes information, links cost and Dijkstra algorithm selects least cost route between every cluster node and cluster head. Using Dijkstra algorithm, route selected between every node and cluster head is optimum; and only one path is selected between each node and cluster head (only one optimal path is exist between each node and cluster head) therefore the set of all routes has a tree structure called routing tree. If a node uses selected least cost route for transmitting its traffic, network will consume least possible energy for its traffic. But, it is important to note here that, the least cost route is not always the best route. Cluster head evaluates all of the cluster nodes and then chooses nodes that have children more than most number of children. For all of neighbors of each selected nodes, proposed protocol determines the following two parameters.

   • Least cost route between node and sink (using one of its neighbors except former neighbor as next hop).

   • Number of children of new selected next hop neighbor [8].

   Then among the children of each node, the one which has a neighbour with fewer children than the most number of children and least cost route to sink will be selected. Then the selected child is modified and in future it will be the child of its new qualified neighbour. The intermediate node is selected based on the number of nodes its connected to. The more number of nodes it is connected to the chances of dropping the packet is reduced. In this way congestion is managed. In some situations, the child with appropriate conditions does not exist; therefore exceptionally a node with children more than the most number of children is accepted. Here a routing tree with appropriate structure is ready to make for each cluster. But only cluster heads know the routes and routing tree, because they made it by itself and other nodes do not participate in mentioned process. A path is selected between all the nodes to send the sensed data to cluster-head. Data are aggregate until the size of the packet is full. The packets are sent to sink by cluster-head. Sometimes the cluster-head partially aggregate the data and send to sink. This is because the size of packet is full. Cluster-head will not wait until all the cluster member sense the data and send to it. It will aggregate the data sent from few cluster members that have sensed the data at that time and send to the sink directly or via gateway nodes. To each node in the cluster a special record in routing table is considered for its best route to cluster head. In addition to best route, many paths which have lower costs in comparison to other paths are also selected to create routing table. For each of selected paths, a record is considered in routing table. Routing table has following fields: ID, residual energy, number of children, cost and average queue length. After constructing routing table, cluster-head directly sends each node routing table to it.

   It makes routing tree by considering the most number of children for its nodes. When the number of children in a routing tree is limited, traffic volumes which enter to the node are limited too. Therefore when an event is occurred, congestion occurrence probability will be decreased. Another parameter which affects the success in congestion management is the nodes awareness about their neighbors average queue length. In this situation when nodes want to select the next hop for their data, they consider their neighbors average queue length as a parameter in decision making. The node with lower average queue length rather than other nodes has higher hope to be selected as next hop.

3. Data Transmission Phase

At the end of the former phase, all the nodes have a routing table. As mentioned before, the proposed routing protocol considers two traffic types: high priority and low priority. The main goal of this phase is to determine next hop for each arrival packet at each node. In the rest of this section, the routing process which is done in each node when it receives packets with different priorities is discussed. When a node receives a high priority packet, it performs following steps:

1. If special record in node routing table is active, this record will be selected. Otherwise Step 2 will be done. (The only special record in node routing table belongs to least cost route)

2. Among the records which have average queue length lower than threshold , the n record with lowest cost field value will be selected. If all the records have average queue length more than threshold , Step 3 will be done.

3. Among the records, the one with the lowest cost field value will be selected.

Nodes routing table has to be updated periodically; otherwise they cannot play their role effectively. When a node residual energy becomes less than threshold , it broadcasts a message and informs its neighbors about its current condition. Neighbors receiving this message, update the sender nodes record in their routing table. The nodes should also inform their neighbors about their average queue length. To keep routing table update is necessary for proposed protocol. If routing table records not be updated, routing process cannot be efficient, because its information will be old. In other side, keeping routing table update is costly. For keeping routing table update, routing protocol should force nodes to send their current condition to its neighbors periodically.

1. PERFORMANCE EVALUATION

   Most of hierarchical routing protocols are composed of two main parts. The first part is routing intra clusters and the second part is routing inter clusters. The first parts role is more important. The number of cluster nodes in simulations is considered as to be between 25 and 100. The communication

   range is determined Based on number of nodes in cluster. Consider almost a 40*40 square for each cluster.

   The main aim is to increase the life time of wireless sensor network by formation of cluster which reduces the energy consumption & manage congestion. Clustering will decrease the number of nodes required to transfer the data to the base station. If less number of nodes are involved in transmission energy of the network will be saved. One of the main reasons for energy consumption in WSNs is due to sensing. Congestion also reduces the energy consumption in WSNs. The main is to avoid congestion and increase the life time of the network.

   For implementation Network Simulator-2(NS2) ns- allinone-2.34 version and ubuntu 10.04 version is used. The simulation graph is obtained using awk script. The number of nodes used in simulation may vary from 25 to 100. The number of nodes shown in Fig 1 is 50 nodes.

   Fig 1. Cluster-heads elected.

   Fig 2. Data transfer among sensor nodes.

   Fig 3. Sensor nodes die

2. CONCLUSION

   Fig 4. Graph of sent packets in bytes Vs time in seconds.

   Fig 5. Graph of Received packets in bytes Vs time in seconds.

   In the first graph, cluster-head ae elected based on the clustering algorithm. In second graph, sensor node sense data & transfer the sensed data to base station. In third graph, sensor nodes die because of drained energy. In next graph, send packets for both protocol is shown. The sent packets in CBEEC protocol is more when compared to other protocol. In fifth graph, received packets for both protocol is shown. The received packets in CBEEC protocol is more when compared to other protocol. We evaluate the number of lost packets due to congestion for two protocols. From the graph it infers that CBEEC protocol is more efficient when compared to other protocol. CBEEC will increase the lifetime of sensor network by decreasing the energy consumption and avoiding congestion.

   Number of packets received to cluster head in this algorithm is always more than other protocols. It manages congestion; it tries to reduce packet loss in nodes which are located in paths between nodes and the cluster head. Lower packet loss leads to more success in delivering packets to cluster head. As mentioned in former sections, we consider two types of traffic. Network nodes service traffics based on their priority. Both of the protocols try to deliver the best possible services to high priority traffic besides deliver suitable service to low priority traffic.

   In this paper, we presented a new hierarchical energy efficient routing protocol for sensor networks which considers congestion management based on paper [8]. Routing protocol divides network into many clusters, then using Dijkstra algorithm constructs a routing tree for each cluster. In routing tree, most number of children for cluster nodes is determined. Proposed protocol manages congestion, using routing tree, nodes neighbors average queue length and residual energy of nodes as parameters.

   The proposed CBEEC algorithm increase the lifetime of the network when compared to the most known clustering algorithms in this area. As future work, we will reconsider the probability of becoming cluster-head to increase yet the network lifetime. Proposed protocol considers only intra cluster routing; we are currently extending the protocol to perform routing inter clusters

3. REFERENCES

[1]. M. Tubaishat and S. Madria, Sensor networks: an overview, IEEE Potentials April/May, pp. 2023, 2003.

[2]. I. F. Akyildiz, W. Su, W. Sankarasubramaniam, and E.

Cayirci, A survey on sensor networks,

[3]. IEEE Commun- ication magazine, pp. 102114, 2002. [4]. R. Shorey, A. Ananda, and W. T. Ooi, Mobile, wireless, and sensor networks, 1st edition, IEEE Press, John Wiley & Sons, 2006.

[5]. Q. F. Jiang and Manivannan, Routing protocols for sensor networks, 1st IEEE Consumer Communications and Networking Conference, pp. 9398,2004.

[6]. Amir Hossein Mohajerzadeh, Mohammad Hossien Yaghmaee , Tree Based Energy and Congestion Aware

Routing Protocol for Wireless Sensor Networks, Wireless Sensor Network, 2010, February, 161-167.

(http://www.SciRP.org/journal/wsn/).

[7]. Ouadoudi Zytoune, Youssef Fakhri, Driss Aboutajdine A Novel Energy Aware Clustering Technique for Routing in Wireless Sensor Networks, Wireless Sensor Network, 2010, March, 233-238. http://www.SciRP.org/journal/wsn/).

[8]. M. I. Khan, W. N. Gansterer, and G. Haring, Congestion avoidance and energy efficient routing protocol for wireless sensor networks with a mobile sink, Journal of Networks,

Vol. 2, No. 6, pp. 4249, 2007

[9]. K. Akkaya and M. Younis, An energy aware QoS routing protocol for wireless sensor networks, ICDCS Workshop03, May 2003.

[10]. Ma Chaw Mon Thein, Thandar Thein "An Energy Efficient Cluster-Head Selection for Wireless Sensor Networks", International Conference on Intelligent Systems, Modeling and Simulation, IEEE 2009.

[11]. Jun Wang, Xuegang Zhu,Yong Cheng and Yongsheng Zhu A Distributed, Hybrid Energy-Efficient Clustering Protocol for Heterogeneous Wireless Sensor Network International Journal of Grid and Distributed Computing

Vol. 6, No. 4, August, 2013