135 Comparison of Routing Protocols in Wireless Sensor Networks Samira Yessad Laboratory of Modelling and Optimization of Systems (LAMOS), Faculty of Exact Sciences, University of Bejaia- 06000 Bejaia - Algeria sam yes06@yahoo.fr Louiza Bouallouche-Medjkoune Laboratory of Modelling and Optimization of Systems (LAMOS), Faculty of Exact Sciences, University of Bejaia- 06000 Bejaia - Algeria louiza medjkoune@yahoo.fr Djamil Aı̈ssani Laboratory of Modelling and Optimization of Systems (LAMOS), Faculty of Exact Sciences, University of Bejaia- 06000 Bejaia - Algeria lamos bejaia@hotmail.com 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. Wireless Sensor Network; Flat routing protocol; Network lifetime; Load Balancing; SENSIM; OMNET++ 1. INTRODUCTION when the network is considered nonfunctional. When a network should be considered nonfunctional is, however, A Wireless sensor network (WSN) is composed of a large application-specific. It can be, for example, the instant number of sensor nodes deployed in an ad hoc manner. when the first sensor dies, a percentage of sensors die, Each sensor node senses phenomena in the environment the network partitions, or the loss of coverage occurs. The in which it is deployed, performs a local processing network layer has already received an important attention on the sensed data, and then transmits it to a sink. in this field. Thus, routing protocols have been proposed WSNs have been used in many application domains such to enhance the network lifetime. Most of them are based as intelligent houses, intelligent agriculture, battlefield on finding the optimal multi-hop route considering the surveillance, integrated patient monitoring, environment residual energy of forwarding nodes. This can exhausting monitoring, chemical/biological detection and other the energy of some nodes more than others. So, these commercial applications (3). As sensor nodes are battery- solutions minimize the average of the consumed energy powered and are uneasy, if not impossible to recharge, the without really enhancing the network lifetime. energy efficiency is a critical design concern in WSNs. This implies minimizing energy of calculation, sensing In (15), we have proposed a multi-path routing protocol and communication tasks. But, especially minimizing (FEAR for Fair Energy Aware Routing) where each sensor communications as, radio transmission is expensive in node uses multiple paths to route its data to the sink. Our terms of energy (3). protocol is based on two ideas. The first idea proposed in the work of (13) (Energy Aware Routing, EAR) consists In the literature, some contributions minimize the average to save multiple sub-optimal paths indeed of one optimal of consumed energy over time and others enhance path. In addition, path selection is based on a given network lifetime. According to (6), network lifetime probability assigned to each path. The second idea, which is time span from the deployment to the instant 136 is our new idea is to add a parameter to calculate the protocols, especially flat-based routing, that we present in probability use of a forwarding node to route data to the what follows. sink. This parameter is the number of forwarding tables to which the forwarding node belongs. In our protocol, SPIN ”Sensor Information Protocol for Negotiation” (8) the route for forwarding data is chosen according to a is among the early work to pursue a data-centric routing probability which counts in addition to the residual energy mechanism. It represents an improvement of flooding and the energy of the communication as in EAR, the and gossiping of (7) using negotiation and adaptation to number of the paths including the forwarding node. This available resources. SPIN uses three types of messages: is intended to use nodes forwarding data for many nodes ADV: when a node has data to send, it notifies its less than ones that forward for few nodes and to create neighbors by using this message with a meta-data. REQ: some kind of fairness in the loss of energy between sensor a node sends this message if it wishes to receive a data in nodes and improve the network lifetime. We have noticed response to ADV message. DATA: this message contains in FEAR, that, if a unique route of a given source node the data with a header containing the metadata. The is used equally by other source nodes, the source node protocol Directed Diffusion proposed in (9) is a protocol can be isolated quickly. To counter this problem, we have reference in the field of Data centric routing. Directed already ameliorated FEAR in (16). We have proposed Diffusion differs from SPIN in terms of the on demand BEER for Balanced Energy Efficient Routing. BEER adds data querying mechanism it has. This protocol consists a new parameter to the calculation of the route probability. mainly of two phases. In the first phase the sink broadcasts The latter depends on the parameter N sent in NFTM messages of interest. Indeed, the sink requests service by messages and on the number of routes in forwarding tables sending the interest to the whole network. The interest of nodes receiving NFTM with N > 1. This parameter represents a task to be performed by the network and can reduces the probability use of nodes belonging to a unique be designed for one or more nodes. The second phase route of a source node. In the two previous works, we shows the reaction of a node upon receipt of an interest. have evaluated FEAR and BEER and have compared First, node checks whether it is affected by this message, them to EAR by simulation. In this paper, we evaluate then it records the identity of the node sender of the and compare the three protocols through a mathematical interest in order to construct the gradient of routes leading model. Obtained results, as simulation results, show the to the sink. If the node is not intended by the interest, it impact of our solutions on balancing energy consumption continues to spread to all neighbors. Once the message between sensor nodes. arrived at the destination, the route to the sink is then well established and the target node chooses this route The rest of this paper is organized as follows. In section to send the information. Rumor Routing (5) is a variant 2, related work in this area is outlined. In section 3, of Directed Diffusion, intended primarily for applications we present FEAR and BEER. In section 4, we describe where the geographic routing criteria are not applicable. the analytical model of EAR, FEAR and BEER and we This protocol uses a long-lived packet named agent, which give numerical results. In section5, we analyze simulation is generated by a node detecting an event. The agent results. The paper concludes in section 6. 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 2. RELATED WORK Diffusion, since, there will be nodes that know the route to the event and respond to the request. There is a flood of In sensor networks, several routing approaches have events and flood of requests. Authors in (12) proposed a been proposed, giving rise to several classifications. slightly modified version of the Directed Diffusion, called These approaches can be distinguished according to ”Gradient-Based Routing”. In this protocol, packets are (2)(? )nd Al-Karaki04 as follows: depending on the forwarded on a path with largest gradient, where gradient network structure, we find flat-based routing, hierarchical- is the difference between the minimum hops separating based routing, and location-based routing, Furthermore, the node from the sink and the minimum hops separating depending on the protocol operation these protocols its neighbor from the sink. can be classified into multipath-based, query-based, negotiation-based, QoS-based, or coherent-based routing All the above presented protocols don’t consider load techniques. According to (14), routing protocols are balancing as is the case in our proposed protocols FEAR divided into the following seven classes: Location-based (15) and BEER (16). Protocols, Data-centric Protocols, Hierarchical Protocols, Mobility-based Protocols, Multipath-based Protocols, Another improvement of Directed Diffusion is proposed Heterogeneity-based Protocols and QoS-based protocols. in (13), EAR is a reactive protocol, and initiated by the destination. This protocol have been detailed in our early To minimize energy consumption and maximize the WSN work (15), since our improvement is based primarily on lifetime, routing protocols have been proposed in the it. Another routing protocol called SEER ”Simple Energy literature. Our study focused on a subset of all these Efficient Routing protocol” is proposed in (11), it uses a 137 flat structure and a simple method for choosing an optimal node i establishes a set of the neighbors j sending route to the sink based on the distance between the source an FTM message containing the identifier i as and the sink and the residual energy of forwarding nodes. following: An improvement of SEER protocol is proposed in (1), where, authors use learning automata concept to ensure N F = {j|i ∈ F T M (j)} (3) a fair tradeoffs between energy balancing and optimal distance. The protocol, named BEAR, aims to improve Once all FTM messages are received by node i, SEER in energy balancing and network lifetime. it calculates the variable N that represents the cardinality of the set N F : 3. FEAR AND BEER DESIGN N = |N F | (4) In this section, we present FEAR and BEER protocols. Hence, the node i inserts the variable N in These protocols aim to improve the WSN lifetime by an NFTM message (Number Forwarding Table ensuring a fair energy wasting of all sensor nodes of the Message) that it sends to its neighbors as response network. to FTM messages. To reduce the protocol overhead, nodes finding N equal to 1 don’t sent the NFTM 3.1. FEAR message, and the node having a neighbor node in its forwarding table that have not sent the NFTM FEAR is based on two main ideas. The first idea is message notes that it is the only one to use it that each node maintains multiple routes with different as relay. Receiving this last message, a node can probabilities use. This idea is that of EAR protocol. The calculate probabilities Pji assigned to each node i second idea consists to count the number of nodes using of the forwarding table. This probability depends on the same neighbor node for the routing and considers that the path cost (Costji ) and the number of nodes that number in the calculation of the probability of each route. use this path (Ni ), using the following formula: As EAR, our protocol has three phases: 1/Costji × Ni Pji = P (5) • Setup phase: A route request message containing k∈F Tj 1/Costjk × Nk a cost variable initialized to 0 (Cost = 0) is broadcasted by the sink. Each node receiving this Where, F Tj is the forwarding table of node j. message broadcasts it to its neighbors. But before, The last step in this phase is the broadcast it calculates the cost of the communication with the of the route request message by node j until neighbor who has sent back the message and adds it it reaches source nodes. Nevertheless, the route to the whole cost of the path to the sink. Thus, if a request message is updated by each node before node i sends a route request message to its neighbor broadcast it. The value of the Cost field of the j; this last calculates the cost metric Cji using the message is replaced by the average cost of reaching following formula: the destination through the neighbors nodes of β the forwarding table which is calculated with the Cji = eα ji Rj (1) formula: Where, eji is the power required for the communi- X costj = Pjk Costjk (6) cation between nodes i and j, and Rj is the residual k∈F Tj 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 • Data Communication phase: In this phase, source combination of the above. When Cji is calculated, nodes and intermediates ones choose randomly a the node j adds it to the cost variable sent by i neighbor to route data using probabilities calculated (costi ) to have the cost of the whole path to the sink earlier. through the node i (costji ): • Route maintenance: Localized flooding is per- costji = costi + Cji (2) formed infrequently from destination to source to keep all the paths alive. Once all route request messages are received, the node j adds each Neighboring node i, if costji 3.2. BEER is optimal, to its forwarding table. The identifiers of all these nodes are broadcasted in an FTM BEER is different from FEAR only in the calculation of (Forwarding Table Message) message. Each node probabilities. So, BEER operates as explained previously, receiving FTM messages, counts the number of but, when a node j receives NFTM message with Ni FTM messages containing its identifier. So, each 138 variable, it calculates probabilities as follows: Figure 1: Network model 1/Costji × Ti Pji = P (7) k∈F Tj 1/Costjk × Tk  Ni If Ni = 1 With Ti = Ni × nbchemin If Ni > 1 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: N(j−1)(i+2) , ..., and N(j−1)(k) with respectively the • Our sensor network is composed of M sensor nodes following probabilities: PN(j−1)(i) Nji , PN(j−1)(i+1) Nji , scattered in a field of interest in flat manner, that PN(j−1)(i+2) Nji ,..., and PN(j−1)(k) Nji . means, all sensor nodes play the same role in the network. Then, we can calculate the energy consumed by the node • There is k source nodes that send the sensed data as follows: in the environment to the sink. The network can be E = PN(j−1)(i) Nji ∗ (Er + Et ) + divided into levels of k nodes each one (the first level L1 is the one composed of source nodes), and PN(j−1)(i+1) Nji ∗ (Er + Et ) + ... + we assume that the ith node of the j th level (Lj ) PN(j−1)(k) Nji ∗ (Er + Et ) (8) noted Nji has i forwarding nodes in the next level Lj+1 (see Figure 1). This assumption will allow us Where Er and Et are respectively the energy required for to have different values for the variables N and T of reception and transmission of data by the node Nji . FEAR and BEER and have the maximum possible cases for our analysis. In EAR protocol, we calculate E as follows: • There is one sink to gather the sensed data by sensor nodes.  E = (Er + Et ) ∗ • Nodes and sink are not mobile. 1 CostN(j−1)(i) Nji • The sensor node is not rechargeable. P 1 + m|Njm ∈F TN(j−1)(i) CostN(j−1)(i) Njm 1 • There is no method to get location information of CostN(j−1)(i+1) Nji sensor nodes. P 1 +. m|Njm ∈F TN(j−1)(i+1) CostN(j−1)(i+1) Njm 1 • The network application can be either query driven, CostN(j−1)(k) Nji  event driven, time driven or the hybridization of the .. + P 1 (9) m|Njm ∈F TN(j−1)(k) CostN(j−1)(k) Njm three. Let’s calculate the energy consumed E by a given node To simplify the calculation of E, we assume that the cost Nji in our network model to route data to the sink. Node of all nodes in the network is the same and it is equal to Nji can route data sent by nodes N(j−1)(i) , N(j−1)(i+1) , 139 C. So E can be written as: In BEER protocol, we calculate E as follow:  1 1  C C E = (Er + Et ) ∗ E = (Er + Et ) ∗ + + ... + i ∗ C1 (i + 1) ∗ C1 1  1 C CostN(j−1)(i) Nji ∗(TNji ) (10) + (k) ∗ C1 1 P m|Njm ∈ CostN N ∗(TN ) (j−1)(i) jm jm 1 1 1 F TN(j−1)(i) = (Er + Et ) ∗ + + ... + (11) 1 i i+1 k CostN(j−1)(i+1) Nji ∗(TNjm ) k + .. X 1 P 1 = (Er + Et ) ∗ (12) m|Njm ∈ CostN(j−1)(i+1) Njm ∗(TNjm ) m=i m F TN(j−1)(i+1) 1  CostN(j−1)(k) Nji ∗(TNjm ) In FEAR protocol, we calculate E as follows: +P (17) 1 m|Njm ∈ CostN ∗(TNjm ) (j−1)(k) Njm  F TN(j−1)(k) E = (Er + Et ) ∗ 1 Similarly, we assume that the cost of all nodes in the CostN(j−1)(i) Nji ∗(NNji ) network is the same and it is equal to C and we find: P 1 + m|Njm ∈ CostN  (j−1)(i) Njm ∗(NNjm ) F TN(j−1)(i) E = (Er + Et ) ∗ 1 CostN(j−1)(i+1) Nji ∗(NNji ) 1 + .. C∗(k−i+1)∗i 1 + P m|Njm ∈ 1 1 1 C∗(k)∗(i) + C∗(k−1)∗(i) + ... + C∗(k−i+1)∗(i) CostN(j−1)(i+1) Njm ∗(NNjm ) F TN(j−1)(i+1) 1 1  C∗(k−i+1)∗(i+1) CostN(j−1)(k) Nji ∗(NNji ) + +P (13) 1 1 1 1 C∗k∗(i+1) + C∗(k−1)∗(i+1) + ... + C∗(k−i)∗(i+1) m|Njm ∈ CostN ∗(NNjm ) (j−1)(k) Njm 1 F TN(j−1)(k)  C∗(k−i+1)∗k ... + 1 1 1 (18) Assuming as above, that the cost of all nodes in the C∗k∗k + C∗(k−1)∗k + ... + C∗(1) network is the same and it is equal to C. We find E as:  = (Er + Et ) ∗  E = (Er + Et ) ∗ 1 1 k−i+1 k−i+1 1 1 1 + 1 1 1 + 1 k + k−1 + ... + k−i+1 k + k−1 + ... + k−i C∗(k−i+1) 1 1 1 + 1  C∗(k) + C∗(k−1) + ... + C∗(k−i+1) k−i+1 ... + 1 1 (19) 1 k + k−1 + ... + k C∗(k−i+1) 1 1 1 + ... +   C∗k + C∗(k−1) + ... + C∗(k−i) 1 (Er + Et ) ∗ k−i+1 Pk 1 Pk 1 1 + 1 + ...    1    m=k−i+1 m m=k−i m   C∗(k−i+1)  1 1 1 (14) E= + (Pk 1 1 )+k) , for i < k C∗k + C∗(k−1) + ... + C∗(1)   m=2 m     1  1  (Er + Et ) ∗ ( k , for i = k  k−i+1  1 (Er + Et ) ∗ 1 P = 1 1 + )+1 m=2 m∗k k + k−1 + ... + k−i+1 (20) 1 k−i+1 1 1 1 + ... + k + k−1 + ... + k−i 4.2. Numerical results 1  k−i+1 As the aim of the three protocols is to consume the energy 1 1 (15) k + k−1 + ... + 1 of sensor nodes in a fair manner to enhance the network lifetime, the standard deviation is an interesting metric to  1 1 = (Er + Et ) ∗ Pk + calculate and to present how far node’s energy are spread k−i+1 1 m=k−i+1 m  out from each other. According to the earlier equations, 1 1 we have calculated the energy for k = 1 to k = 10 and for Pk 1 + ... + Pk 1 (16) m=k−i m m=1 m 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 140 Table 1: Simulation parameters Figure 2: Comparison of standard deviation with increase in sensor’s density for EAR, FEAR and BEER Parameter Value Transmit current 25 mA Receive current 8 mA Idle current 0.001 mA CPU active current 8 mA Radio radius 1.5 sensor.channel radius 6 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 Figure 2 confirm results of the two earlier works ((15) network lifetime and energy variance that can show that and (16)). The standard deviation is lower in BEER and there is no a great difference between the remaining greater in EAR. That means that in BEER the energy energy of nodes. The energy variance metric calculates of all nodes in the network are close to the average how far node’s energy are spread out from each other. energy in contrast to EAR and FEAR where there is a The topology is made of 10 sensor nodes (SensorN ode0 large difference between the energy of the nodes and the to SensorN ode9 ) of which two nodes are source nodes average energy. These results show that EAR uses some (SensorN ode0 and SensorN ode1 ) and one sink node nodes more than others for routing data from source nodes (SB). to the sink, thing that is avoided in FEAR and even more in BEER. These results confirm that FEAR and BEER In this simulation scenario, we have use a simple MAC use forwarding nodes in an equitable manner to balance protocol which is defined in the implementation of energy consumption between sensor nodes and thus avoid EAR in the sensor simulator framework of omnet++, the network partitioning. 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 5. SIMULATION AND ANALYSIS 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 Figure 3: Wireless sensor network topology In the present paper, we consider the network lifetime as the time till the first node runs out of energy. To measure We evaluate and compare EAR, FEAR and BEER the network lifetime, we run simulation eight times with performances by simulation using SENSIM simulator eight different seeds as presented in Table 2 with FEAR, (sensor simulator framework for OMNeT++) (17) BEER and EAR protocols. Obtained results are presented developed at The Sensor Networking Laboratory at in the graph of Figure 5. This figure shows that BEER 141 Table 2: Seed configurations Configuration Seed Value 1 11111 2 21111 3 21311 4 21318 5 41318 6 413185 7 5236937 8 5331928 enhances significantly the network lifetime comparing with EAR and FEAR. 6. CONCLUSION Figure 4: Energy variance over simulation time 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. Figure 5: Network lifetime for EAR, FEAR and BEER [2]Akkaya, K. and Younis, M. (2005) A survey on routing protocols for wireless sensor networks. Ad Hoc Networks, 3, 325–349. [3]Akyildiz, I.F. Su, W. Sankarasubramaniam, Y. and Cayici, E. (2002) A survey on sensor networks. IEEE Communications Magazine, 40, 102–114. 142 [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 Communi- cations 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. Bouallouche- Medjkoune, L. and Aı̈ssani, D. (2012) Balanced Energy Efficient routing protocol for WSN. International Con- ference on Communications and information Technology ICCIT’12, Hammamet, Tunisia, juin 2012, 326–330. [17]http://csc.lsu.edu/sensor web/simulator.html.