Comparison of Routing Protocols in Wireless Sensor Networks

Abstract

Several routing protocols have been proposed to maximize the sensor networks lifetime. However, most of these solutions try to find an energy efficient path and don't account for energy consumption balancing in sensor network. This usually leads to network partitioning. The aim of this paper is to evaluate, analyze and compare three routing protocols (EAR, FEAR and BEER) that balance energy consumption, through a mathematical model and simulations. Obtained results show that FEAR enables fair energy efficient use and enhances the sensor network lifetime more than EAR. BEER outperforms the two protocols and balances energy consumption between sensor nodes better than FEAR and EAR.

1. INTRODUCTION

A Wireless sensor network (WSN) is composed of a large number of sensor nodes deployed in an ad hoc manner. Each sensor node senses phenomena in the environment in which it is deployed, performs a local processing on the sensed data, and then transmits it to a sink. WSNs have been used in many application domains such as intelligent houses, intelligent agriculture, battlefield surveillance, integrated patient monitoring, environment monitoring, chemical/biological detection and other commercial applications (3). As sensor nodes are batterypowered and are uneasy, if not impossible to recharge, the energy efficiency is a critical design concern in WSNs. This implies minimizing energy of calculation, sensing and communication tasks. But, especially minimizing communications as, radio transmission is expensive in terms of energy (3).

In the literature, some contributions minimize the average of consumed energy over time and others enhance network lifetime. According to ( 6 ), network lifetime is time span from the deployment to the instant when the network is considered nonfunctional. When a network should be considered nonfunctional is, however, application-specific. It can be, for example, the instant when the first sensor dies, a percentage of sensors die, the network partitions, or the loss of coverage occurs. The network layer has already received an important attention in this field. Thus, routing protocols have been proposed to enhance the network lifetime. Most of them are based on finding the optimal multi-hop route considering the residual energy of forwarding nodes. This can exhausting the energy of some nodes more than others. So, these solutions minimize the average of the consumed energy without really enhancing the network lifetime. In ( 15 ), we have proposed a multi-path routing protocol (FEAR for Fair Energy Aware Routing) where each sensor node uses multiple paths to route its data to the sink. Our protocol is based on two ideas. The first idea proposed in the work of ( 13 ) (Energy Aware Routing, EAR) consists to save multiple sub-optimal paths indeed of one optimal path. In addition, path selection is based on a given probability assigned to each path. The second idea, which is our new idea is to add a parameter to calculate the probability use of a forwarding node to route data to the sink. This parameter is the number of forwarding tables to which the forwarding node belongs. In our protocol, the route for forwarding data is chosen according to a probability which counts in addition to the residual energy and the energy of the communication as in EAR, the number of the paths including the forwarding node. This is intended to use nodes forwarding data for many nodes less than ones that forward for few nodes and to create some kind of fairness in the loss of energy between sensor nodes and improve the network lifetime. We have noticed in FEAR, that, if a unique route of a given source node is used equally by other source nodes, the source node can be isolated quickly. To counter this problem, we have already ameliorated FEAR in ( 16 ). We have proposed BEER for Balanced Energy Efficient Routing. BEER adds a new parameter to the calculation of the route probability. The latter depends on the parameter N sent in NFTM messages and on the number of routes in forwarding tables of nodes receiving NFTM with N > 1. This parameter reduces the probability use of nodes belonging to a unique route of a source node. In the two previous works, we have evaluated FEAR and BEER and have compared them to EAR by simulation. In this paper, we evaluate and compare the three protocols through a mathematical model. Obtained results, as simulation results, show the impact of our solutions on balancing energy consumption between sensor nodes.

The rest of this paper is organized as follows. In section 2, related work in this area is outlined. In section 3, we present FEAR and BEER. In section 4, we describe the analytical model of EAR, FEAR and BEER and we give numerical results. In section5, we analyze simulation results. The paper concludes in section 6.

2. RELATED WORK

In sensor networks, several routing approaches have been proposed, giving rise to several classifications. These approaches can be distinguished according to (2)(? )nd Al-Karaki04 as follows: depending on the network structure, we find flat-based routing, hierarchicalbased routing, and location-based routing, Furthermore, depending on the protocol operation these protocols can be classified into multipath-based, query-based, negotiation-based, QoS-based, or coherent-based routing techniques. According to ( 14 ), routing protocols are divided into the following seven classes: Location-based Protocols, Data-centric Protocols, Hierarchical Protocols, Mobility-based Protocols, Multipath-based Protocols, Heterogeneity-based Protocols and QoS-based protocols. To minimize energy consumption and maximize the WSN lifetime, routing protocols have been proposed in the literature. Our study focused on a subset of all these protocols, especially flat-based routing, that we present in what follows.

SPIN ”Sensor Information Protocol for Negotiation” ( 8 ) is among the early work to pursue a data-centric routing mechanism. It represents an improvement of flooding and gossiping of ( 7 ) using negotiation and adaptation to available resources. SPIN uses three types of messages: ADV: when a node has data to send, it notifies its neighbors by using this message with a meta-data. REQ: a node sends this message if it wishes to receive a data in response to ADV message. DATA: this message contains the data with a header containing the metadata. The protocol Directed Diffusion proposed in ( 9 ) is a protocol reference in the field of Data centric routing. Directed Diffusion differs from SPIN in terms of the on demand data querying mechanism it has. This protocol consists mainly of two phases. In the first phase the sink broadcasts messages of interest. Indeed, the sink requests service by sending the interest to the whole network. The interest represents a task to be performed by the network and can be designed for one or more nodes. The second phase shows the reaction of a node upon receipt of an interest. First, node checks whether it is affected by this message, then it records the identity of the node sender of the interest in order to construct the gradient of routes leading to the sink. If the node is not intended by the interest, it continues to spread to all neighbors. Once the message arrived at the destination, the route to the sink is then well established and the target node chooses this route to send the information. Rumor Routing ( 5 ) is a variant of Directed Diffusion, intended primarily for applications where the geographic routing criteria are not applicable. This protocol uses a long-lived packet named agent, which is generated by a node detecting an event. The agent travels the network to inform the distant nodes about local events. When a node generates a request for an event, it does not flood the whole network as in Directed Diffusion, since, there will be nodes that know the route to the event and respond to the request. There is a flood of events and flood of requests. Authors in ( 12 ) proposed a slightly modified version of the Directed Diffusion, called ”Gradient-Based Routing”. In this protocol, packets are forwarded on a path with largest gradient, where gradient is the difference between the minimum hops separating the node from the sink and the minimum hops separating its neighbor from the sink.

All the above presented protocols don’t consider load balancing as is the case in our proposed protocols FEAR ( 15 ) and BEER ( 16 ).

Another improvement of Directed Diffusion is proposed in ( 13 ), EAR is a reactive protocol, and initiated by the destination. This protocol have been detailed in our early work ( 15 ), since our improvement is based primarily on it. Another routing protocol called SEER ”Simple Energy Efficient Routing protocol” is proposed in ( 11 ), it uses a flat structure and a simple method for choosing an optimal route to the sink based on the distance between the source and the sink and the residual energy of forwarding nodes. An improvement of SEER protocol is proposed in (1), where, authors use learning automata concept to ensure a fair tradeoffs between energy balancing and optimal distance. The protocol, named BEAR, aims to improve SEER in energy balancing and network lifetime.

3. FEAR AND BEER DESIGN

In this section, we present FEAR and BEER protocols. These protocols aim to improve the WSN lifetime by ensuring a fair energy wasting of all sensor nodes of the network. 3.1. FEAR FEAR is based on two main ideas. The first idea is that each node maintains multiple routes with different probabilities use. This idea is that of EAR protocol. The second idea consists to count the number of nodes using the same neighbor node for the routing and considers that number in the calculation of the probability of each route. As EAR, our protocol has three phases: • Setup phase: A route request message containing a cost variable initialized to 0 (Cost = 0) is broadcasted by the sink. Each node receiving this message broadcasts it to its neighbors. But before, it calculates the cost of the communication with the neighbor who has sent back the message and adds it to the whole cost of the path to the sink. Thus, if a node i sends a route request message to its neighbor j; this last calculates the cost metric Cji using the following formula:

Cji= ejαi Rjβ (1) Where, eji is the power required for the communication between nodes i and j, and Rj is the residual energy of the node j normalized to its initial energy. The weighting factors α and β can be chosen to find the minimum energy path or the path with nodes having the maximum residual energy or the combination of the above. When Cji is calculated, the node j adds it to the cost variable sent by i (costi) to have the cost of the whole path to the sink through the node i (costji): costji = costi + Cji (2) Once all route request messages are received, the node j adds each Neighboring node i, if costji is optimal, to its forwarding table. The identifiers of all these nodes are broadcasted in an FTM (Forwarding Table Message) message. Each node receiving FTM messages, counts the number of FTM messages containing its identifier. So, each • Data Communication phase: In this phase, source nodes and intermediates ones choose randomly a neighbor to route data using probabilities calculated earlier. • Route maintenance: Localized flooding is performed infrequently from destination to source to keep all the paths alive. 3.2. BEER BEER is different from FEAR only in the calculation of probabilities. So, BEER operates as explained previously, but, when a node j receives NFTM message with Ni node i establishes a set of the neighbors j sending an FTM message containing the identifier i as following:

N F = {j|i ∈ F T M (j)} Once all FTM messages are received by node i, it calculates the variable N that represents the cardinality of the set N F :

N = |N F | Hence, the node i inserts the variable N in an NFTM message (Number Forwarding Table Message) that it sends to its neighbors as response to FTM messages. To reduce the protocol overhead, nodes finding N equal to 1 don’t sent the NFTM message, and the node having a neighbor node in its forwarding table that have not sent the NFTM message notes that it is the only one to use it as relay. Receiving this last message, a node can calculate probabilities Pji assigned to each node i of the forwarding table. This probability depends on the path cost (Costji) and the number of nodes that use this path (Ni), using the following formula: Pji = Pk∈F Tj 1/Costjk × Nk

1/Costji × Ni

Where, F Tj is the forwarding table of node j. The last step in this phase is the broadcast of the route request message by node j until it reaches source nodes. Nevertheless, the route request message is updated by each node before broadcast it. The value of the Cost field of the message is replaced by the average cost of reaching the destination through the neighbors nodes of the forwarding table which is calculated with the formula: costj =

PjkCostjk ( 6 ) X k∈F Tj (3) ( 4 ) ( 5 ) variable, it calculates probabilities as follows: Pji = Pk∈F Tj 1/Costjk × Tk

1/Costji × Ti

( 7 ) With Ti = Ni × nbchemNini IIff NNii => 11 Where, F Tj is the forwarding table of node j and nbchemin is the number of routes in the forwarding table of node j.

4. EVALUATION OF FEAR AND BEER

In this section, we propose a mathematical model and we analyze and compare FEAR, BEER and EAR through the latter.

4.1. Mathematical model

To simplify the calculation of energy consumption, we assume that we have a wireless sensor network with the following properties: • Our sensor network is composed of M sensor nodes scattered in a field of interest in flat manner, that means, all sensor nodes play the same role in the network. • There is k source nodes that send the sensed data in the environment to the sink. The network can be divided into levels of k nodes each one (the first level L1 is the one composed of source nodes), and we assume that the ith node of the jth level (Lj ) noted Nji has i forwarding nodes in the next level Lj+1 (see Figure 1). This assumption will allow us to have different values for the variables N and T of FEAR and BEER and have the maximum possible cases for our analysis. • There is one sink to gather the sensed data by sensor nodes. • Nodes and sink are not mobile. • The sensor node is not rechargeable. • There is no method to get location information of sensor nodes. • The network application can be either query driven, event driven, time driven or the hybridization of the three.

Let’s calculate the energy consumed E by a given node Nji in our network model to route data to the sink. Node Nji can route data sent by nodes N(j−1)(i), N(j−1)(i+1), N(j−1)(i+2) , ..., and N(j−1)(k) with respectively the following probabilities: PN(j−1)(i)Nji , PN(j−1)(i+1)Nji , PN(j−1)(i+2)Nji ,..., and PN(j−1)(k)Nji .

Then, we can calculate the energy consumed by the node as follows:

E =

PN(j−1)(i)Nji ∗ (Er + Et) + PN(j−1)(i+1)Nji ∗ (Er + Et) + ... + PN(j−1)(k)Nji ∗ (Er + Et) ( 8 ) Where Er and Et are respectively the energy required for reception and transmission of data by the node Nji. In EAR protocol, we calculate E as follows: E = (Er + Et) ∗

1

CostN(j−1)(i)Nji P P + + .. (17)

+ (18) + (19) Similarly, we assume that the cost of all nodes in the network is the same and it is equal to C and we find: E = (Er + Et) ∗ ... +

1 1 C1∗(k−i+1)∗i 1 + C∗(k)∗(i) + C∗(k−1)∗(i) + ... + C∗(k−i+1)∗(i)

1

C∗(k−i+1)∗(i+1) 1 1 1 C∗k∗(i+1) + C∗(k−1)∗(i+1) + ... + C∗(k−i)∗(i+1) 1

C∗(k−i+1)∗k 1 1 1

C∗k∗k + C∗(k−1)∗k + ... + C∗(1) = (Er + Et) ∗         E =       

1 1 k−i+1 k−i+1 k1 + k −11 + ... + k−1i+1 + k1 + k −11 + ... + k−1i 1 k−i+1 ... + k1 + k−1 + ... + k

1 (Er + Et) ∗ k−1i+1 Pkm=k1−i+1 m 1 1 + ... 1 + Pkm=k−i m 1 + (Pkm=2 m1 )+k) , for i < k

1 (Er + Et) ∗ (Pkm=2 m1∗k )+1 , for i = k (20)

4.2. Numerical results

As the aim of the three protocols is to consume the energy of sensor nodes in a fair manner to enhance the network lifetime, the standard deviation is an interesting metric to calculate and to present how far node’s energy are spread out from each other. According to the earlier equations, we have calculated the energy for k = 1 to k = 10 and for each value of k the i take values in the interval [1,k]. The Figure 2 shows the variation of standard deviation of the consumed energy of sensor nodes with different values of k in each protocol. Results as shown in the graph of Figure 2 confirm results of the two earlier works (( 15 ) and ( 16 )). The standard deviation is lower in BEER and greater in EAR. That means that in BEER the energy of all nodes in the network are close to the average energy in contrast to EAR and FEAR where there is a large difference between the energy of the nodes and the average energy. These results show that EAR uses some nodes more than others for routing data from source nodes to the sink, thing that is avoided in FEAR and even more in BEER. These results confirm that FEAR and BEER use forwarding nodes in an equitable manner to balance energy consumption between sensor nodes and thus avoid the network partitioning.

5. SIMULATION AND ANALYSIS

We evaluate and compare EAR, FEAR and BEER performances by simulation using SENSIM simulator (sensor simulator framework for OMNeT++) (17) developed at The Sensor Networking Laboratory at

Parameter

Transmit current

Receive current

Idle current

CPU active current

Radio radius

sensor.channel radius

Value 25 mA 8 mA Louisiana State University, under the topology shown in Figure 3 in terms of two metrics: network lifetime and energy variance. As the aim of our protocol is to consume nodes energy in a fair manner to enhance the network lifetime, we are interested, obviously, in the network lifetime and energy variance that can show that there is no a great difference between the remaining energy of nodes. The energy variance metric calculates how far node’s energy are spread out from each other. The topology is made of 10 sensor nodes (SensorN ode0 to SensorN ode9) of which two nodes are source nodes (SensorN ode0 and SensorN ode1) and one sink node (SB).

In this simulation scenario, we have use a simple MAC protocol which is defined in the implementation of EAR in the sensor simulator framework of omnet++, to avoid influencing the performance with a particular MAC algorithm. The three routing protocols use the same energy metrics for path selection. This was the metric function given in the previous section with α = 1 and β = 1. Other simulation parameters are given in Table 1.

5.1. Energy Variance

To measure the energy variance, we have run the simulation both with EAR, FEAR and BEER protocols. Obtained results are shown by the graph of figure 4. The graph presents the variation of the energy variance over simulation time.

The figure shows clearly that the energy variance is greater in EAR and FEAR, that means that in BEER the energy of all nodes in the network are close to the average energy in contrast to EAR and FEAR where the energy variance is very large thereby demonstrating the large difference between the energy of the nodes and the average energy.

5.2. Network Lifetime

In the present paper, we consider the network lifetime as the time till the first node runs out of energy. To measure the network lifetime, we run simulation eight times with eight different seeds as presented in Table 2 with FEAR, BEER and EAR protocols. Obtained results are presented in the graph of Figure 5. This figure shows that BEER

Configuration Seed Value 1 2

3 4 5 enhances significantly the network lifetime comparing with EAR and FEAR.

6. CONCLUSION

Wireless sensor networks lifetime is a critical property which should be considered in routing protocols. However, most of proposed routing protocols in the literature focused on minimizing the energy consumption of each sensor node so that the mean of the consumed energy be reduced and do not balance the energy consumption in the network so that the network lifetime be enhanced. The purpose of this paper was to propose a mathematical model for our routing protocols for sensor networks (FEAR and BEER) that enhance the EAR protocol for maximizing the network lifetime. The idea behind these protocols is simple, but helps to avoid depleting the energy of some nodes more than others and thus to maximize the WSN lifetime. We have calculated the energy consumed by a node in routing task using the model and results show that BEER outperforms FEAR and EAR, and FEAR outperforms EAR in term of network lifetime. Theses results have been confirmed also by simulation.

We would like, in future work, improve our approach by using information that can be given by MAC layer to network layer. This information will help in reducing the protocol overhead and in enhancing the network lifetime.

7. REFERENCES

[1]Ahvar, E. and Fathy, M. (2010) BEAR: A Balanced Energy-Aware Routing Protocol for Wireless Sensor Networks. Wireless Sensor Network journal, 2, 793–800. [2]Akkaya, K. and Younis, M. (2005) A survey on routing protocols for wireless sensor networks. Ad Hoc Networks, 3, 325–349. [17]http://csc.lsu.edu/sensor web/simulator.html.

References

[4] Al-Karaki , J. N. and Kamal , A. E. ( 2004 ) Routing techniques in wireless sensor networks : A survey . IEEE Wireless Communication , 11 , 6 - 28 .

[5] Braginsky , D. and Estrin , D. ( 2002 ) Rumor Routing Algorithm for Sensor Networks . First Workshop on Sensor Networks and Applications (WSNA) , Atlanta, GA , October 2002 , 22 - 31 .

[6] Chen , Y. and Zhao , Q. ( 2005 ) On the Lifetime of Wireless Sensor Networks . IEEE Communications Letters , 9 , 976 - 978 .

[7] Hedetniemi , S. and Liestman A. ( 1988 ) survey of gossiping and broadcasting in communication networks . IEEE Networks , 18 , 319 - 349 .

[8] Heinzelman , W. R. Kulik , J. and Balakrishnan , H. ( 2002 ) Negotiation-based protocols for disseminating information in wireless sensor networks . Wireless Networks , 8 , 169 - 185 .

[9] Intanagonwiwat , C. Govindan , R. and Estrin , D. ( 2000 ) Directed diffusion: a scalable and robust communication paradigm for sensor networks . ACM MobiCom '00 , Boston, MA, 2000 , 56 - 67 .

[10] Jiang , Q. and Manivannan , D. ( 2004 ) Routing protocols for sensor networks . the First IEEE Consumer Communications and Networking Conference , Juin 2004 , 93 - 98 .

[11] Leuschner , C.J. and Hancke , G.P. ( 2007 ) SEER: A Simple New Routing Protocol for Wireless Sensor Networks . SA Computer Journal , 39 , 17 - 24 .

[12] Schurgers , C. and Srivastava , M. B. ( 2001 ) Energy efficient routing in wireless sensor networks . Military Communications Conference (MILCOM) on Communications for Network-Centric Operations : Creating the Information Force , IEEE, 357 - 361 .

[13] Shah , R. C. and Rabaey , J. ( 2002 ) Energy aware routing for low energy ad hoc sensor networks . IEEE Wireless Communications and Networking Conference (WCNC) , pp. 350 - 355 .

[14] Singh , S. K. Singh , M. P. and Singh , D. K. ( 2010 ) Routing Protocols in Wireless Sensor Networks - A Survey . International Journal of Computer science and engineering Survey (IJCSES) , 1 , 63 - 83 .

[15] Yessad , S. Bouallouche-Medjkoune , L. and A ¨ıssani, D. ( 2011 ) proposition and evaluation of a novel routing protocol for wireless sensor networks . International Workshop on Verification and Evaluation of Computer and Communication Systems VECoS'11 , Tunis , Tunisia, 15 - 16 September, 2011 , 1 - 9 . British Computer Society Ed.

[16] Yessad , S. Tazarart , N. Bakli , L. BoualloucheMedjkoune, L. and A ¨ıssani, D. ( 2012 ) Balanced Energy Efficient routing protocol for WSN . International Conference on Communications and information Technology ICCIT'12 , Hammamet , Tunisia, juin 2012 , 326 - 330 .