Grid Based Energy Efficient Multipath Routing Protocol In Wireless Sensor Network Using Fuzzy Approach

Grid Based Energy Efficient Multipath Routing Protocol In Wireless Sensor Network Using Fuzzy Approach

Sherin Joy C

Department of Information Technology, Karunya University,

Coimbatore, Tamil Nadu, India

AbstractWireless Sensor Networks is one of the prominent communication network in recent technologies. In WSN, data is being gathered and disseminated in real time as well as in non- real time basis. One of the major issues in the wireless sensor networks is the energy efficiency. When the node transmits data from one node to another to reach the destination it would lose its energy and it may not able to transmit data. Energy efficiency helps to increase the network lifetime by saving the nodes energy. This paper introduces a new energy saver/balancer routing protocol which enables an efficient QoS requirement for the users. The basic OoS requirements are energy efficiency and end to end delay. Fuzzy set approach helps to bring out better representation of energy efficiency among the nodes in WSN. Grid based multipath routing helps to find out the minimum end to end delay between the source and the sink node. Energy aware routing protocol considers both energy balancing and energy saving.

Keywords Wireless Sensor network, Routing protocol, energy saver, fuzzy set approach

1. INTRODUCTION

   Recent advances in wireless sensor networks [11] have led to many new routing protocols specifically designed for sensor networks where energy awareness is an essential design issue. In general, packet routing algorithms are used to exchange messages with sensor nodes that are outside of a particular radio range. This is different to sensors that are within radio range where packets can be transmitted using a single hop. Furthermore, one hop sensor networks are not recommended in most applications due to the energy cost of long range transmissions. Thus came into existence the multi- hop where the data packets are transmitted from source to destination through many intermediate nodes or routers. Nowadays many routing protocols uses multi-hopping pattern where it needs less energy cost of short range transmissions.

   The routing techniques in WSN have the common objective of trying to extend the lifetime of the sensor network while not compromising data delivery. There are many ways to classify the routing protocols based on the network structure. Almost all of the routing protocols in WSN can be classified as network structure and based on protocol operations. The network structure can be further classified as data-centric, hierarchical and location based [9].

   In data-centric routing all nodes are typically assigned equal roles or functionality. The sink sends queries to remote areas

   and waits for data from the sensors located in the selected area. With the help of queries the data is being requested therefore attribute based naming is necessary to specify the properties of data. The first data-centric protocol is named as SPIN, which eliminates redundant data and save energy through data negotiation between nodes in sensor network. The two classical mechanisms to relay data in sensor networks without the need for any routing algorithms and topology maintenance is gossiping and flooding.

   In hierarchical-based routing, each nodes have their own roles and responsibilities in the network. Nodes with higher energy is used to process the data and send them and nodes with lower energy are used to sense the environment. Therefore hierarchy of low and high energy nodes are created. The creation of clusters and assigning special tasks to cluster heads can affect the scalability, lifetime, and energy efficiency. Hierarchical routing is two-layer routing where one layer is used to select cluster heads and the other for routing. Low energy adaptive clustering hierarchy (LEACH) is one of the most popular hierarchy routing algorithms for sensor networks.

   In location-based routing sensor nodes positions are exploited to route data in the network. Most of the routing protocols for sensor networks require location information for sensor nodes. Based on the location information the distance between two particular nodes can be calculated, in order to estimate the energy consumption. The location can also be found by the help of GPS tracking, since the nodes are spatially deployed over an area location information can be utilized in routing data in an energy efficient way.

   Moreover these protocols are classified into multipath- based, query-based, negotiation-based, coherent based and QoS based routing techniques [8] depending on protocol operation with design trade-offs between energy and communication overhead savings. This paper addresses to design an energy balancer routing protocol for hierarchical based wireless sensor network. The proposed protocol mainly considers about energy balancing and energy saving of the nodes in the network. The energy saver/balancer routing protocols helps to save energy of the nodes so that the network lifetime can be increased. The optimal path for the transmission is based upon the energy level and the hop count.

   The rest of the paper is organized as follows, in section 2, we discuss about the related work, in section 3, we introduce the fuzzy set technique, in section 4, and we present our proposed methodology, and then we show the details and result of the simulation in section 5 and 6, finally in section 7 we conclude our paper.

2. RELATED WORK

   Ying-Hong Wang et.al [1] proposed a routing protocol named Hierarchy-Based Multipath Routing Protocol (HMRP). It is a layered network where there is multipath routes to the sink node through some forwarding nodes. This protocol is suitable for small or large sensing area, since the communication overhead in sensor nodes is very low. Each node will determine their candidate parent nodes to transmit the sensed data to the sink. By using these candidate parents, the sensor node can reply the data through different path every time. This protocol enables forwarding nodes to aggregate all received packets during a short period time and transmit only one aggregated packet to the following node. . The data aggregation mechanism involves in every nodes apart from the leaf nodes which reduces the energy consumption in the networks. This protocol increases the lifetime of network than clustering or tree based protocol. Main advantages of HMRP are, it minimizes the path loading of system by distributing energy consumption. It doesnt maintain whole path information, it just maintain candidate information table. It supports multiple sink positions

   Bashir Yahya et.al [2] proposed a multipath routing protocol called robust and energy efficient multipath routing protocol (REER). The main objective of this paper is to predict the best next hop through path construction phase with the help of residual energy, available buffer size of the node and Signal to Noise ratio. There are two methods of traffic allocation. First it involves single path to transfer data message. If link (path) cost falls below threshold, then it switches to next alternative path. Second involves splitting up the transmitted message into number of segments of equal size. This segments are XOR, based forward error correction codes and transmitted along multiple path simultaneously. Multipath routing along with forward error correction technology are used to recover from node failures without invoking network wide flooding for path discovery. In a sensor network this concept is important because flooding will reduces network lifetime. Using HELLO and RREQ message the path is established betweenthe sink node and the source node. Then KEEPALIVE message is transmitted periodically to keep multiple paths alive. Sink node initiates the path discovery phase.

   Kee-Young Shin et.al [3] proposed an event driven routing protocol called Reliable Energy Aware Routing Protocol (REAR). It mainly works on the real sensor network platform and supports multipath routes. It allows each sensor node to confirm the success of data transmission to the destination sensor node by providing DATA-ACK oriented packet transmission. It considers residual energy capacity of each sensor node for establishing reliable routing paths from source to destination. The source node broadcast a request

   message of multipath route to find the route to the destination. The node receives this message would check its current energy level and forwards it to the next suitable node. Nodes with more energy will forward this message quicker than with low energy. Hence nodes with higher energy will be chosen in terms of energy efficiency during the construction of routing path from source to destination. This helps in increasing the lifetime of the network by choosing the alternative path from source to destination when the first paths energy value reaches a threshold. Thus it has a resilient data transmission.

   Omar Banimelhem et.al [4] proposed grid based multipath with congestion avoidance routing protocol (GMCAR) in wireless sensor network. It is a QoS based routing protocol mainly based on the guaranteed end to end delay. It divides the sensor field into grids and each grid consists of sensor nodes and one master node. Master nodes helps in gathering data from non-master nodes in the same grid.

   Then it may relay the gathered data to other master nodes to reach the sink node. Multiple diagonal paths are considered to connect the master node and the sink node and it is stored in the routing table as routing entries of that node. Routing decisions are mainly considered on the basis of the grid densities and the hop count. It also maintains the congestion avoidance where the congested areas are free for transmission when the congestion occurs. This protocol helps in energy efficiency and helps in extending network lifetime, improving network throughput and minimizing the delay.

3. INTRODUCTION TO FUZZY SET TECHNIQUE Fuzzy set were introduced by Lotfi A Zadeh in the year

   1965. It was an extension of the classical notion of set. The definition of a fuzzy set then, from Zadeh's paper is:

   Let X be a space of points, with a generic element of X denoted by x. Thus X ={x}.

   A fuzzy set A in X is characterized by a membership function fA(x)which associates with each point in X a real number in the interval [0,1], with the values

   of fA(x) at x representing the "grade of membership" of x in A. Thus, the nearer the value of fA(x) to unity, the higher the grade of membership of x in A [5].

   The value of 0 is represented as FALSE and 1 as TRUE. The fuzzy set is useful for modeling uncertainty. Thus fuzzy set is defined in terms of a membership function which is a mapping from the universal set U to the interval [0, 1][10].

4. PROPOSED METHODOLOGY

   GMR using fuzzy approach is a reactive protocol whereby the routes to the destination from the source are found on demand basis. Most of the energy efficient protocols are mainly energy conserving and they do not consider about the energy balancing. They considers the shortest path from the

   source to the destination to minimize the energy consumption. But it may not works well in the case of energy balancing.

   This paper designs an energy saver routing protocol for grid based Wireless Sensor Networks to balance and to save the energy consumption by the help of fuzzy set technique.

   The main idea of developing an efficient wireless sensor network by dividing them into grids. For each particular grid area, a representative node acts as the leader to transmit the data to other nodes. The leader node however, does not do any aggregation or fusion. Inside each grid, one of the sensor nodes is selected as master node which has the responsibility to deliver data generated by any nodes in that grid and to route data from other master nodes in the neighbor grids. The routing table of master node has multiple diagonal paths that may connect themselves to the sink node and stored as routing entries of that node.

   In grid based multipath routing the nodes are deployed in randomly in sensor field. The physical network is divided into logical grid network in which each grid consists of various nodes deployed or none maybe. The sink node is one called base station node which is stationary and may located anywhere in the network. The other nodes in the grid are also stationary. The sensor nodes may collect data from the sensor field and may transmit them to the sink node which is the destination node. The path through which the data is transmitted from the source node to the destination node may consists of variable intermediate nodes thus multi hopping technique is employed. The nodes must have sufficient energy to transmit the data from one node to another node in their communication range. If the energy of the nodes drained out in the selective path, then alternative path must be chosen on spot and there shouldnt be any communication failure between source node and the destination node. This concept is called grid based multipathing.

   It consists of four phases:

   • Grid formation

   • Neighbor discovery

   • Forwarding data

   • Energy update

   1. Grid formation phase

      The sensor network is divided into logically squared shaped grids of predefined size. The nodes are deployed randomly as mentioned above. Global positioning system is used to determine the location of each nodes in the grid. If grid contains single node, it becomes master node else node with highest ID is selected as master node. After election every master node broadcast its status to other nodes in that grid and reply by sending their IDs back to the master node to get connectivity between nodes of same grid. The maximum grid size should be where R is the radio range of the sensor and G is the grid size.

      For the grid formation, make 4×4 grid with 50 number of nodes and one sink node. Each node is placed in the grid with the specified values of X and Y co-ordinates.

   2. Neighbor discovery

      The first step includes the neighbor node estimation where the each nodes finds its neighboring nodes in that network. The neighboring nodes can be within the grid or outside the grid. The Sink node initializes the network by flooding the network with a broadcast message. Every node that receives the initial broadcast packet, makes an entry in to its Neighbor Table including Neighbor ID, Energy Level and Hop Count. These nodes resends the packet to other nodes with necessary changes such as (1) it increments the Hop Count field, (2) it changes the Source Address field to its address and (3) it changes the Energy Level field to its energy level. Every node in the network retransmits the broadcast message only once, to all of its neighbors.

      2 3 4

      5	6	7	8
      9	10	11	12
      13	14	15	16

      Fig. 1. Example of Grid Sensor Network

      When the initial broadcast message has been flooded through the network, each node knows hop count and energy level of its neighbors. The Sink node periodically sends a broadcast message through the network; so that nodes add new neighbors joined the network to the Neighbor Table and remove neighbors that have failed to be an active member of the network.

   3. Forwarding data

      The second step which includes is actual fuzzy set technique. When a node observes an event, it iniiates a routing process. One of the most challenges in the reactive protocols is how to select the next hop. However, in this work we propose a new scenario to solve it. It consists of two fuzzy sets; A and B.

      A is the fuzzy set of all neighbors energy levels:

      It may find the residual energy set of each nodes.

      1. has a membership function, mA(ei ) which can be defined as below:

         (1)

         where is a control parameter to limit energy factor in [0,1] interval and ei is energy level of (i)th neighbor. Let be obtained from the following formula

         then (2)

         Simulation Parameter	Value
         Topology Size	200 x 200 m2
         Number of sensors	50
         Deployment type	Random/uniform
         Number of grids	16
         Grid size	50 x 50 m2
         Radio range	142m
         Data packet size	1000 bytes
         Traffic type	Constant bit rate
         MAC protocol	802.11
         Mobility	None
         Simulation time	20, 40, 60, 80, 100 sec

         Where is energy threshold and A ( -cut) is used to remove the neighbors with unacceptable energy level.

      2. is the fuzzy set of all neighbors hop counts with membership function mB(hi).

         (i)

         (3)

         Where n is the number of neighbors, and hi is hop count of

         th neighbor and Maxhop is the longest possible path.

         Now, we define following decision maker equation:

         However, the neighbor with maximum amount of C is selected as the next hop.

   4. Energy Update

   The final step includes to set the source node. The routes for all the nodes are calculated statically. It is able to find the possible path from the source node to the destination node. Thus the total energy available for each nodes in that path is calculated. Depends upon it find the optimal path which results in the largest value of energy levels. After the transmission of data from source node to the destination node it may update the energy level, so that the next transmission can be better without draining much of the energy. All the neighbors of the sender node receive the forwarded data packet via the overhearing technique. Then, they update the energy level of sender node in their "Neighbor Table" by the piggybacking technique. Nodes might be used by more than one neighbor for routing, in this case the energy value stored in the "Neighbor Tables" of both the node's neighbors will be completely accurate by the overhearing technique.

5. SIMULATION

   The simulation environment models a grid based sensor network with 50 nodes deployed randomly or uniformly over an area of 200 x 200 m2. The sensor nodes and the sink node are equipped with GPS devices thus it may enable them to find their location in the case of random deployment.

   The simulator which is used for this simulation is NS2 [6][7]. NS2 is an open-source event-driven simulator tool. It contains modules for various network components such as routing, transport layer protocol, application, etc. To monitor network performance, researchers can simply use an easy-to- use scripting language to configure a network, and observe results generated by NS2.

   The complete set of the parameters that are used in the simulation are given in the table 1.

   Table 1: Simulation Settings

6. RESULTS

   The simulation results shows the comparison of Grid based energy efficient multipath routing protocol using fuzzy approach with the protocol proposed in [4] as it is a grid based routing protocol.

   Figure 2 shows the total power consumption during different points of simulation time. The figure illustrates that the proposed protocol conserves less energy than the other protocol.

   Fig. 2. The proposed protocol energy performance

   Figure 3 shows the performance of throughput which varies with the simulation time. Throughput is calculated mainly based on the channel capacity. Greater the capacity greater is the value of the throughput. According to the simulations the proposed protocol has greater throughput than the other protocol.

   Fig. 3. Average throughput comparison

   Figure 4 shows the packet delivery ratio which is calculated through different points of simulation time. Packet delivery ratio is one which shows ratio of packets being delivered to the destination. The figure clears us that the proposed routing protocol has greater pdr ratio.

   Fig. 4. Delivery ratio comparison

7. CONCLUSION

Energy efficiency is one of the main factor taken into account to establish a good routing protocol. Energy being very scarce, saving the battery of each sensor node should be the criteria. Criteria must lie in balancing nodes energy consumption and prolonging networks life span. It must also aim at good stability and extensibility. This paper proposes a new energy saver routing protocol named grid based energy efficient multipath routing protocol using fuzzy approach. The proposed method is simulated and compared with GMCAR. Results shows that the proposed protocol consumes less energy than the GMCAR.

REFERENCES

1. Ying-Hong Wang, Chih-Hsiao Tsai and Hung-Jen Mao. HMRP: Hierarchy-Based Multipath Routing Protocol for Wireless Sensor Networks. (2006) Tamkang Journal of Science and Engineering, Vol. 9, No 3.

2. Kee-Young Shin, Junkeun Song, JinWon Kim, Misun Yu, and Pyeong Soo Mah. Reliable Energy Aware Routing Protocol (REAR), Feb. 12-14, 2007 ICACT2007.ISBN 978-89-5519-131-8 93560.

3. B Yahya, J Ben-Othman.REER: Robust and Energy Efficient Multipath Routing Protocol for Wireless Sensor Networks. IEEE Conference, 2009. GLOBECOM 2009 .

4. Omar Banimelhem, Damer Khasawneh GMCAR: Grid based multipath with congestion avoidance routing protocol in wireless sensor network Science Direct-April 2012 1346-1361.

5. Fuzzy sets, Information and Controls 338-353 1965.

6. Introduction to network simulator NS2 by marc gresis tutorial.

7. Introduction to network simulator NS2 by teerawat issariyakul ekram hossain springer 2009, ISBN: 978-0-387-71759-3.

8. G.Kalpana Dr.T.Bhuvaneswari A Survey on Energy Efficient Routing Protocols for Wireless Sensor Networks, 2nd National Conference on Information and Communication Technology (NCICT) 2011 Proceedings published in International Journal of Computer Applications® (IJCA).

9. Jamal N. Al-Karaki Ahmed E. Kamal Routing Techniques in Wireless Sensor Networks: A Survey.

10. H.J Zimmermann, Fuzzy set Theory and its Applications, third ed. Kluwer Academics Publishers, Boston , MA. 1996 .

11. K. Sohraby, D.Minoli and T.Znati. Wireless Sensor Network, Technology, Protocols and Applications. John Wiley & Sons, New Jersey, Canada,2007 Pages 10-23.