Energy And Cost Effective Routing Protocol For Wireless Sensor Network

Energy And Cost Effective Routing Protocol For Wireless Sensor Network

S.Taruna

Computer Science Department Banasthali Vidyapith

Jaipur, India

Sakshi Shringi

Information Technology Department Banasthali Vidyapith

Jaipur, India

Abstract

Wireless Sensor network consists of large number of small sensor nodes which can communicate over wireless links. The sensor nodes are short-lived and unreliable which leads to the main design issue of maintaining long system lifetime as well as maintaining sufficient sensing coverage and reliability. To increase the lifetime and Quality of Service (QoS) various routing protocols were proposed in order to maintain full sensing coverage.

In this paper we propose an algorithm for randomly deployed wireless sensor network. The proposed algorithm increases the working time of full coverage in a given network. The main idea of this paper is to combine coverage preservation and energy balancing into routing protocols. The proposed scheme is cost effective. We have performed MATLAB simulations to analyze the results and to compare our scheme with other benchmark protocols. The expected output is 85%-90% extra lifetime and energy preservation.

Keywords- LEACH, Cost, Coverage, Energy-aware and Coverage-preserving Hierarchical Routing (ECHR)

1. Introduction

   Wireless Sensor Networks (WSNs) consist of tiny sensor nodes that, in turn, consist of microprocessor, memory, transceiver, and power supply. In order to realize the existing and potential applications for WSNs, advanced and extremely efficient communication and routing protocols are required.

   Routing protocols of all Wireless Sensor networks, regardless of the application, must try to maximize the network life time and minimize the energy consumption of overall network. For these reasons, the energy consumption parameter has higher priority than other factors. [1]

   WSN have a great deal of research attention due to their wide range of applications which includes environment monitoring, object tracking, traffic control, scientific observing, traffic control, industrial sensing and diagnostics (e.g., factory, appliances), critical infrastructure protection (e.g., power grids, water distribution, waste disposal), and situational awareness for battlefield applications [2].

   The first step in deploying these wireless sensor networks is to determine, with respect to application- specific performance criteria, (i) in the case that the sensors are static, where to deploy or activate them; and

   (ii) in the case that (a subset of) the sensors are mobile, how to plan the trajectory of the mobile sensors. These two cases are collectively termed as the coverage problem in wireless sensor networks.

   There are usually two deployment modes in wireless sensor networks. On the one hand, if the cost of the sensors is high and deployment with a large number of sensors is not feasible, a small number of sensors are deployed in several preselected locations in the area. In this case, the most important issue is sensor placement

   • where to place the sensors in order to fulfil certain performance criteria. On the other hand, if inexpensive sensors with a limited battery life are available, they are usually deployed with high density (up to 20 nodes=m3 [3]). The most important issue in this case is density control how to control the density and relative locations of active sensors at any time so that they properly cover the monitoring area. (Another relevant issue is how to rotate the role of active sensors among all the sensors so as to prolong the network lifetime [4].)

     One of the most active research fields in wireless sensor networks is that of coverage. Coverage is

     usually interpreted as how well a sensor network will monitor a field of interest. It can be thought of as a measure of quality of service.

     The coverage usually involves two basic sides

     • How to evaluate the coverage performance when sensor nodes are deployed in a monitoring region.

     • How to improve the coverage performance when wireless sensor network cannot effectively satisfy application requirements.

   In this paper, we analyze the performance of energy- aware coverage-preserving protocol in respect of network lifetime, energy dissipated, coverage ratio and cost. We compare our proposed scheme to LEACH. The performance analysis of proposed scheme is evaluated in MATLAB [5]

   The remaining paper is organized as follows: Section 2 describes the related work. Section 3 describes the proposed system. Section 4 describes simulation setup and results. Conclusions are drawn in section 5.

2. Related Works

   Most of the previous routing protocols that have been proposed were designed to prolong the lifetime of the network [6] and [7]. However, if the network fails to maintain full coverage, there is no use of sensor network. The routing protocols were proposed to increase lifetime of the network and to enhance the Quality of Service (QoS) [8]. In order to decrease the energy consumption of radio transmission, a Low- Energy Adaptive Clustering Hierarchy (LEACH) routing protocol was proposed by W. R. Heinzelman et al. [9] which minimizes energy dissipation in sensor networks.

   LEACH is a very well known hierarchical routing algorithm for sensor networks. It makes clusters of the sensor nodes based on the received signal strength. The 5% of the total number of nodes becomes the cluster head and act as router to the sink. Transmission will only be done by cluster head. Therefore, the energy consumption of sensor node can be highly reduced by preventing it from transmitting the sensing data to the base station (BS) directly.

   In addition, Tasi [10] proposed a coverage preserving routing protocol, which was enhanced from LEACH protocol. This protocol is known as LEACH Coverage- U protocol. It calculates the overlap sensing areas of all sensor nodes, and then uses this feature to select cluster head.

   Hence, in this study, we present an Energy-aware and Coverage-preserving Hierarchical Routing (referred as ECHR) protocol. This protocol helps to increase the duration of maintaining the full sensing coverage in a WSN. The proposed ECHR protocol will always choose one of the overlapping nodes to be the cluster head in each round. We will also apply the energy- aware hierarchical routing mechanism to find out an optimal route for the data measured by each node.

   Comparing with other benchmark protocols, the ECHR protocol can effectively prolong the duration of maintaining full sensing coverage in a WSN.

3. The Proposed Energy-Aware Coverage- Preserving Algorithm

   To prolong the duration of full sensing coverage, we propose an Energy-aware and Coverage-preserving Hierarchical Routing (ECHR) protocol for randomly deployed WSNs. This protocol will maximize the working time of full coverage in a given WSN without considering deployment patterns of the sensor node. In this paper we will try to maximize the network lifetime and reduce the cost of network. MATLAB simulations will be performed to analyze and compare the performance of ECHR with other protocols. The expected output of simulation is up to 85-90% extra lifetime compared to other protocols.

   1. Assumptions

      In this paper, we assume that there are n sensor nodes randomly deployed in a L × L sensing field and the sensing field has m points of interest (termed as POI). The definition of POI (denoted as P1, P2,, Pm) and the related point coverage problem can be referred to the referenc [11].

      Some other assumptions made for the network model are:

      • The total number of nodes in the network is 500.

      • Base Station (BS) is located far away from the sensing area.

      • All the wireless sensor nodes and BS is stationary after deployment.

      • Nodes are dispersed in a 2-dimensional space and cannot be recharged after deployment.

      • All nodes can send the data to the BS.

      • All nodes are of the same specifications.

      • All nodes consume equal energy for transmission and reception.

      • All nodes are homogeneous and have same capabilities with unique IDs

      • Each node has power control ability which can be adjusted according to the transmission distance.

      • Each Sensor node has the same initial power.

      • In the first round, each node has a probability p of becoming the Cluster Head (CH).

      • Nodes are uniformly distributed in network.

   2. The Coverage Model

      Each sensor node has sensing range and location

      { , }, i [1, n]. The location of each POI is given by

      { , }, j [1, m]. We denote a coverage set of a sensor node by . The Coverage Ratio (K) of the network can be calculated by the following equation:

      apply the energy-aware hierarchy routing mechanism in order to determine an optimal route for packets generated by each node.

      According to the radio model described above, the transmission between a cluster head and the BS could consume huge amount of energy. In the ECHR protocol, the cluster head selection is based on uniform distribution.

      Therefore, the cluster head selection mechanism is essential. Clustering provides resource utilization and minimizes energy consumption in WSNs by reducing the number of sensor nodes that take part in long distance transmission [12] and [13]. Cluster based operation consists of several rounds. These involve cluster heads selection, cluster formation, and transmission of data to the base station.

      In our mechanism of cluster head selection the

      representative nodes will be selected as cluster heads

      K = ||CS 1 CS 2 CS n1 CSn ||

      m

      (1)

      based on the following equation:

      P (k successes in n rounds) = (3)

      If a node S1 runs out of energy, 1 in equation (1) will become an empty set.

   3. Energy-Aware Hierarchy Routing Mechanism

      • All sensing data of sensor nodes will be transmitted by multi-hop mechanism.

      • Each node uses the hop count of received information in a neighbour table.

      • Each sensor node knows which nodes are closer to the cluster head, and these nodes could be its parent node.

      • However, a node might have multiple parent nodes available for choosing.

      • We can calculate the parent node factor for the parent node by:

        Pf = (1/df) × REf (2)

        where is distance between the node and the parent node

      • As in equation (2), each node will calculate the parent node factor according to its parent nodes and all the values of neighbouring table.

      • Each node will now transmit the sensing data to its parent node.

   4. Cluster Head selection mechanism

      In our work, the cluster head selection mechanism is based on energy-balancing and coverage-preserving. This mechanism is used in the ECHR protocol. We also

      Where n= no. of rounds

      k= no. of success

      n-k = no. of failures

      p = probability of success in one round

      q = (1-p) = probability of failure in one round

      Equation 3 will select the cluster heads form the active sensor nodes. The cluster head will now aggregate the sensing data from the sensor nodes and send it to the base station.

   5. Flowchart of Proposed Algorithm

      The proposed algorithm includes various steps of implementation. The first step includes selection of cluster head. Cluster head is selected with the help of uniform distribution method.

      Each sensor node selects its parent node with the help of ECHR mechanism. Parent node receives sensing data from each sensor node.

      Cluster head aggregates data and send it to the Base station.

      Figure 1 shows the flowchart of proposed algorithm.

      Yes

      Start

      Selection of CHs form the active nodes with the help of cluster head selection mechanism

      Selection of CHs form the active nodes with the help of cluster head selection mechanism

      CH broadcasts a beacon message

      CH broadcasts a beacon message

      Each sensor node will choose its parent node with ECHR mechanism

      Each sensor node will choose its parent node with ECHR mechanism

      Parent node receives sensing data from each sensor node

      Parent node receives sensing data from each sensor node

      Each CH sends aggregated data to the Base Station

      Each CH sends aggregated data to the Base Station

      Is there active node?

      No

      End

      • S(i).Type=N

      • temp_rnd = i

      • {if (temp_rnd>m*n+1)

      • S(i).E=Eo /*initial energy Eo=0.5

      • */Plot normal nodes*/

        }

      • Exit the program

      • Exit the program

      • /*plot base station with following co- ordinates*/

        S(N+1).xd=0.5* Xm

        S(N+1).yd=0.5* Ym

      • // Coverage points

      • {for each round

      • s_range: Range of Sensor Node

      • set s_range

      • { for i =1 to n

      • theata equals to 0 to 2*pi

      • node co-ordinate x is assigned to XR(i)

      • node co-ordinate y is assigned to YR(i)

      • xp = 2*s_range*cos(theata)

      • yp = 2*s_range*sin(theata)

      • display the points

      • exit the program

        }

      • Extract first value from node co-ordinate x

      • Extract first value from node co-ordinate y

        Figure 1. Flowchart of Proposed Algorithm

   6. Pseudo Code

      • // Node deployment

      • N: no. of nodes

      • S: array to store the nodes location

      • XR: array to store values of X co-ordinates for N nodes

      • YR: array to store values of Y co-ordinates for N nodes

      • Xm = 200, Ym =200 /* Field Dimension*/

      • {for i=1 to N

      • XR (i) = random (1, 1)* Xm

      • YR (i) = random(1,1)* Ym

        }

      • /*Initially there are no cluster head*/

        • pts call circlepoints (x,y,2*s_range)

        • Extract values from second node to n node

        • x1 XR (i)

        • y1 YR (i)

        • pts call circlepoints (x1,y1,2*s_range)

        • Exit the program

        • {for each round

        • // Choosing Cluster Head

        • Threshold is set to (P / (1 P * (round % 1/P)))

        • {for each node

        • {if number of cluster <= 10 && energy of node > 0

        • Assign a random number

        • {if (random number < threshold value) && (the node has not been cluster head)

          • Node is Cluster head //assign node id to cluster head list

          • Increment cluster head count //a new cluster head has been added

          • Else go to the next node}

          • Else go to the next node}

            ETx (d,H) = k (Eelec + amp d )

            ERx (d,H) = HEelec

            [4]

            }

          • //Simulating Transmission and Reception

          • {if distance between node and cluster head is

            <= the transmission range

          • Transmission cost is ETx(l, d)=Eelec * l + Efs

            * l * d2

          • Reception cost is ERx(l)=Eelec * l

          • Subtract the transmission cost from the sending node

          • {if remaining energy <= 0

          • display node has died

          • exit the program

            }

          • Subtract the reception cost from the receiving node

          • {if remaining energy <= 0

          • display node has died

          • exit the program

            }

          • Return the sum of transmission cost and reception cost and calculate residual energy of each node

            }

          • } //rmax

4. Simulation Setup and Results

   1. Energy Model for communication

      We have used the first order radio model in this study [10]. The two parameters used in this model are,

      and . denotes the energy dissipations per bit by the transmitter or receiver circuits and is set to 50nJ/bit. denotes the energy dissipations per bit by the transmitter amplifier and is set to 0.1 nJ/bit/ .

      The energy consumption for transmitting/receiving H-bit data message for a given distance d is formulated by:

      where is the energy consumption for transmitting data denotes the energy dissipation by receiving data, and is the pass loss exponent. The pass loss exponent is set to 2 for the transmission from each node, and is set to 2.5 for the transmission from a cluster head to BS.

      Figure 2. Energy consumption model

   2. Simulation Parameters

      We have simulated the proposed model in MATLAB 7.0. We have compared the performance of the ECHR protocol with that of LEACH via numerical simulation.

      The simulation environment is a network with 500 nodes randomly distributed in an area of 200 × 2002 . This monitoring area consists of 500 POIs, and the BS is located at (100, 100). The initial energy of all nodes is assumed to be 0.05 joule, and the sensing range is set to be 10 m. Furthermore, the compression coefficient is set to 0.05, and the data packet size k is set to 2000 bits. Table 1 gives detail of simulation parameters used in our proposed scheme.

      Table 1. Simulation Parameters

      Parameters	Values
      Simulation Round	2000
      Network size	200*200
      Number of Nodes	500
      Node distribution	Nodes are uniformly distributed
      Control Packet size	500bits
      Data Packet size	2000bits
      Distance between BS and Sensor field	100-100m
      Initial energy of node	0.05 joule
      Point of interest	500
      Compression coefficient	0.05
      Energy dissipation	10*0.000000000001 Joule
      Energy for Transmission	50*0.000000000001 Joule
      Energy for Reception	50*0.000000000001 Joule
      Energy for data aggregation	5*0.000000000001 Joule

   3. Network Lifetime

      If a dead node occurs in early rounds of the algorithm, this may affect the life time of the network which may lead to early dead of all nodes. Table 2 shows the simulation results of the two schemes.

      Figure 3 concludes that in the proposed algorithm, first node dies later in the network.

      Table 2. Network Life Time (First Node dead)

      No. of Rounds	Round number when first node dies
      	LEACH	PROPOSED SCHEME
      100	52	0
      300	179	0
      600	367	0
      900	452	597
      1200	431	610
      1500	424	641
      1800	402	620
      2100	389	626

      Figure 3. Network life time (First node dead) v/s No. of rounds

   4. Network Lifetime showing number of nodes alive

      Network lifetime increases with the increase in nodes alive. Large number of dead nodes reduces life time of the network.

      Table 3 and Figure 4 shows the number of nodes alive in the network with increase in rounds.

      Table 3. Network lifetime with nodes alive in network

      No. of Rounds	Number of Alive Nodes
      	LEACH	Proposed Algorithm
      100	500	500
      300	460	500
      600	295	380
      900	135	230
      1200	120	190
      1500	75	150
      1800	65	105
      2100	25	85

      Figure 4. Network Life Time v/s number of rounds.

   5. Coverage Ratio

      Table 4 shows the values of coverage ratio for LEACH protocol and the proposed algorithm. Figure 5 concludes the results.

      The proposed algorithm is able to maintain 100% coverage ratio till 1700th round whereas LEACH protocol lose full coverage ratio at 900th round. Figure

      10 concludes that the proposed algorithm provides about 85-90% extra life time compared to LEACH protocol.

      Table 4. Coverage Ratio

      No. of Rounds	Coverage Ratio (%)
      	LEACH	Proposed Algorithm
      100	100	100
      300	100	100
      600	100	100
      900	100	100
      1200	75	97
      1500	55	92
      1800	20	60
      2100	0	0

      Figure 5. Coverage ratio v/s Number of rounds

   6. Energy dissipation

      Table 5 shows the comparison of average energy dissipation of the proposed scheme with LEACH protocol. Energy dissipated in the proposed scheme is less than LEACH. It shows our system is much more efficient then the existing LEACH protocol.

      Figure 6 depicts the graph of comparison of energy dissipated in proposed system.

      Table 5. Energy dissipation

      No. of Rounds	Energy dissipated
      	LEACH	Proposed Algorithm
      100	0.18	0.1
      300	0.29	0.2
      600	0.45	0.3
      900	0.6	0.4
      1200	0.79	0.6
      1500	0.96	0.71
      1800	0.92	0.90
      2100	0.90	0.90

      Figure 6. Energy dissipation v/s No. of rounds

   7. Cost

A cost metric has been defined for the network to show that the proposed scenario has less costing as compared to LEACH. We have computed the cost of the network in terms of energy.

The total energy of 500 nodes consumed in each round in thenetwork has been calculated which gives the average energy of the network consumed in each round until any node dies.

Mathematically, it is formulated as:

AvgCost=500 S (i) Eres(r) 500 S (i) Eres(r+1) [5]

Here, i is the total number of nodes in the network, r is the round number. Eres is the residual energy of any node. S is the array of 500 nodes in simulation. S(i).Eres is the residual energy of the i th node.

Table 6 and Figure 7 conclude that the cost of network is more in LEACH as compared to the proposed algorithm.

Table 6. Cost Metric

Figure 7. Cost v/s Simulation Run

=1 =1

6. Conclusion

The aim of this study is to prolong the duration for maintaining full sensing coverage. The main idea is to combine energy balancing and coverage-presenting mechanisms into routing protocol.

Simulation results show that the proposed ECHR protocol is able to prolong the duration of the network with 100% coverage ratio, which provides 85-90% extra lifetime comparing with LEACH protocol. We have also seen the effect of cost and concluded that the cost of network is more in LEACH as compared to the proposed algorithm. The average energy dissipated in proposed scheme is less than that of LEACH.

The proposed scheme is for the homogeneous network and we propose to extend our work for heterogeneous network in future. We will also try to evaluate the performance of the proposed system in aspects of transmission delay and throughput in future and compare our algorithm with other benchmark protocols

References

1. Ali Norouzi, Abdul Halim Zaim, March 2012. An Integrative Comparison of Energy Efficient Routing Protocols in Wireless Sensor Network, Wireless Sensor Network, 65-75 doi:10.4236/wsn.2012.43010 Published Online (http://www.SciRP.org/journal/wsn)

2. Wireless sensor network survey Jennifer Yick, Biswanath Mukherjee, Dipak Ghosal, Department of Computer Science, University of California, Davis, CA 95616, United States

3. E. Shih, S. Cho, N. Ickes, R. Min, A. Sinha, A. Wang, and A. Chandrakasan. Physical layer driven protocol and algorithm design for energy-efficient wireless sensor networks. In Proc. of ACM MobiCom01, Rome, Italy, July 2001.

4. F. Ye, G. Zhong, S. Lu, and L. Zhang. PEAS: A robust energy conserving protocol for long-lived sensor networks. The 23nd International Conference on Distributed Computing Systems (ICDCS), 2003.

5. Matlab Tutorial available at www.mathworks.com/academia/student…/tutorials/launc hpad.html

6. Lindsey, S., Raghavendra, C., Sivalingam, K.M., 2002.Data Gathering Algorithms in Sensor Networks Using Energy Metrics, IEEE Transactions on Parallel and Distributed System, vol. 13, no. 9, pp. 924-935.

7. Al-Karaki, J.N., Kamal, A.E., 2004. Routing techniques in wireless sensor networks: a survey, IEEE Wireless Communications, vol.11, no.6, pp. 6-28.

8. Mollanoori, M., Charkari, N.M., 2008. LAD: A Routing Algorithm to Prolong the Lifetime of Wireless Sensor Networks, In Institute of Electrical and Electronics Engineers, 2008 IEEE International Conference on Networking, Sensing and Control. Sanya, China April 6-8 2008. USA: New York, pp. 983-987

9. Heinzelman, W.B., Chandraksaan, A.P., Balakrishnan, H., 2002. An Application – Specific Protocol Architecture for Wireless Sensor Networks, IEEE Transactions on Wireless Communications, vol. 1, no. 4, pp. 660-670.

10. Tsai, Y.R., 2007. Coverage-Preserving Routing Protocols for Randomly Distributed Wireless Sensor Networks,IEEE Transactions on Wireless Communications, vol.6, no. 4, pp. 1240-1245. 56.

11. Cardei, M., Wu, J., 2005. Coverage in Wireless Sensor Networks, In Handbook of Sensor Networks, Ilyas, M., Mahgoub, I., CRC Press: New York, vol. 1, Chapter 19, pp. 1-12.

12. Y. He, W. S. Yoon and J. H. Kim, Multi-level Clustering Architecture for Wireless Sensor Networks, Information Technology Journal, Vol. 5, No. 1, 2006, pp. 188-191. doi:10.3923/itj.2006.188.191.

13. W. Liu and J. Yu, Energy Efficient Clustering and Routing Scheme for Wireless Sensor Networks, Proceeding of the IEEE International Conference on Intelligent Computing and Intelligent Systems, Shanghai, 20-22 November 2009, pp. 612-616. doi:10.1109/ICICISYS.2009.5358113.

Authors

S.Taruna is an active researcher in the field of communication and mobile network, currently working as Assistant Professor in Department of Computer Science at Banasthali University (Rajasthan), India. She has done M.Sc from Rajasthan University and PhD in Computer Science from Banasthali University (Rajasthan), India. She has presented many papers in National and International Conferences, published 7 papers in various journals and reviewer of various journals and conferences.

Sakshi Shringi received B.TECH degree in Information Technology from Rajasthan Technical University, Kota in 2011. She is pursuing her M.TECH degree in Information Technology from Banasthali University (Rajasthan). She has presented many papers in National and International Conferences. Her research interest includes computer network, wireless sensor and ad-hoc networks and virtualization.