Enhancing The Lifetime Of Wireless Sensor Network By Using The Minimum Energy Scheduling Algorithms

Enhancing The Lifetime Of Wireless Sensor Network By Using The Minimum Energy Scheduling Algorithms

Ramanan.S. V1 , Mrs. K. Jaynthi2

1PG Scholar, 2 Associate Professor,

Department of Electronics and Communication Engineering SNS College of Technology

Abstract In this project we use MES algorithm is mainly favorable for dynamic link scheduling and network protocol designs in energy-constrained wireless sensor networks. Before that, we implement a novel scheduling method named Backbone Scheduling using Virtual nodes which schedules multiple overlapped backbones so that the network energy consumption is evenly distributed among all sensor nodes. In this way, the energy of all of the sensor nodes in the network is fully utilized, which in turn prolongs the network lifetime. Here the data is only forwarded by the backbone sensor nodes and other sensor nodes turn off the radios saves energy. The Energy Consumption is balanced by rotating the multiple backbones. Approximation algorithms are used for solving the MLVNS problems. MES significantly reduces the energy consumption compared to the original MaxWeight algorithm. In addition, we analytically show that the MES algorithm is essentially energy optimal in the sense that the average energy expenditure of the MES algorithm can be pushed arbitrarily close to the global minimum solution

Index Terms – Wireless sensor networks, Backbone Scheduling using Virtual nodes, MLVNS Problem, Energy Consumption, Network Lifetime

I INTRODUCTION

1. wireless sensor network is a collection of nodes organized in a network. Each node consists of one or more microcontrollers, CPUs or DSP chips, a memory and a RF transceiver, a power source such as batteries and accommodates various sensors and actuators

   .

   Wireless sensor networks are Ad-hoc networks which contain a set of nodes which have limited computational power and limited power resources. As the energy resources are limited in the sensor node so full utilization of the resources with minimum energy remains main consideration when a wireless sensor network application is designed.

   Among the functional components of a sensor node, the radio consumes a major portion of the energy . Various techniques are proposed to minimize its energy consumption. One of it is Backbone Scheduling using Virtual Nodes. [1].

   Fig.1 Block diagram of Sensor node

   The usage of sensor networks is rapidly growing due to their small size and easily deployment. It means that we can easily expand and shrink such network, so sensor networks are more flexible as compare to the other wired networks. Due to this flexible nature such network has many applications in various fields. Object tracking is such one of the most important application of sensor network. Other applications are Security Surveillance and Building inspections.

   II CHALLENGES OF WIRELESS SENSOR NETWORKS

   A Network lifetime

   As sensor nodes are battery-operated, protocols must be energy-efficient to maximize system life time. System

   life time can be measured such as the time until half of the nodes die or by application-directed metrics, such as when the network stops providing the application with the desired information about the phenomena [4].

   B Fault Tolerance

   Some sensor nodes may fail or be blocked due to lack of power, have physical damage or environmental interference. The failure of sensor nodes should not affect the overall task of the sensor network. This is the reliability or fault tolerance issue. Fault tolerance is the ability to sustain sensor network functionalities without any interruption due to sensor node failures.

   C Power Consumption

   The wireless sensor node, being a microelectronic device, can only be equipped with a limited power source. In some application scenarios, replenishment of power resources might be impossible. Sensor node lifetime, therefore, shows a strong dependence on battery lifetime. The malfunctioning of few nodes can cause significant topological changes and might require rerouting of packets and re- organization of the network. Hence, power conservation and power management take on additional importance [2]. It is for these reasons that researchers are currently focusing on the design of power aware protocols and algorithms for sensor networks. In sensor networks, power efficiency is an important performance metric, directly influencing the network lifetime. Application specific protocols can be designed by appropriately trading off other performance metrics such as delay and throughput with power efficiency. The main task of a sensor node in a sensor field is to detect events, perform quick local data processing, and then transmit the data. Power consumption can hence be divided into three domains: sensing, communication, and data processing.

   III BACKBONE SCHEDULING USING VIRTUAL NODES

   Backbone Scheduling is a novel sleep scheduling technique.VBS is designed for WSNs has redundant sensor nodes. BS forms multiple overlapped backbones using Virtual nodes which work alternatively to prolong the network lifetime. In BS, Virtual sensor nodes alone communicate and the other nodes will be rest state, to save energy. Energy Consumption is balanced and minimized by rotation of virtual nodes which fully utilizes the energy and achieves a longer network

   lifetime compared to the existing techniques. The scheduling problem of BS is formulated as the Maximum Lifetime Virtual Node Scheduling (MLVNS) problem-costs solution.

   A Formation of Virtual Back Bone

   Virtual Backbones are formed connecting the nodes. Connected Dominating Set (CDS) algorithms to construct such backbones [3],[11]. A single virtual backbone does not prolong the network lifetime. An intuitive idea is to construct multiple disjointed CDSs and let them work alternatively.

   Fig. 2 Virtual Backbone Network

   IV MODEL AND ASSUMPTIONS:

   Sensor nodes are randomly placed in the field and are immobile thereafter. A battery is the only energy source of the sensor nodes. There is a sink in the network, (Node 0 in Fig 2) which is always active and has a maximum power supply. All sensor nodes have an identical communication range (links are bidirectional). The power consumption of a sensor node is comprised of three parts: sensing, computing, and communication. For a typical sensor node, the communication is the most power-consuming part and may even dominate the energy consumption. Therefore, it only considers the scheduling of the radio. Sensor nodes are duty-cycled and have the same working cycle [8]. At the beginning of each round, a Virtual node is selected to work in duty-cycling. Nodes that are not in the backbone will turn off their radios. The lifetime of a sensor node is the time span from when it starts working to when its energy is fully utilised. The lifetime of a network is the minimum lifetime of all of the sensors in the network. Because backbones rotate after each round, the lifetime is counted in rounds.

   V MAXIMUM LIFETIME VIRTUAL NODE SCHEDULING PROBLEM AND ITS NP HARDNESS

   The lifetime of a schedule is the lifetime of the network using this schedule to turn on and off the radio of the sensor nodes. The objective of the MLVNS problem is to find that schedule that achieves the highest network lifetime. Note that the Virtual can be overlapped. The MLVNS problem is NP-hard.

   In order to find the optimal schedule, we formulate the Maximum Lifetime Virtual Node Scheduling problem. Its definition is as follows. A schedule in BS is a set of Virtual nodes working sequentially in each round. Formally, we need to ind a set of backbones, consider for example B = {B1, B2 . . . Bp}, and each backbone Bi works for Ti rounds. A schedule is, therefore, represented by a set of tuples, {<B1, T1> . . . <Bp, Tp>}, such as the amount of energy consumed by any sensor node in the network at he end of the life time does not exceed its initial value.

   VI CENTRALIZED APPROXIMATION MINIMUM ENERGY ALGORITHMS FOR THE MLVNS PROBLEM

   Because the MLVNS problem is NP-hard, we focus on designing approximation algorithms [1]. First centralized approximation algorithm is based on a new concept called Transition Schedule Algorithm (TSA). A TSA is used to model a schedule in a WSN. The time scale is generally represented by horizontal axis counted in rounds. In each round, possible states are listed vertically, which are represented by ellipses. The number of possible states for each round is equal to the number of backbones. Each state contains a backbone and the corresponding energy levels . The state and the backbone have a one-to-one mapping. An initial state is placed at round 0 and is connected with all states in the first round to represent a starting point.Fig 3 represents the implementation of TSA using Animated window Unidirected transition edges connect states in one round to those in the next round. No backward edges are allowed. Each edge represents the time elapse of 1 round. Since energy is used in each round, each edge also represents the consumption of energy. Backbone consume a fixed amount of energy in each round, all edges represent the same amount of energy consumption. The residual energy of all nodes is obtained by subtracting this value from the starting state of each transition edge. No transition is allowed if the energy of any sensor node of a state is depleted. It is clear that a directed path from the initial state corresponds to a schedule. Thus, the MLVNS problem is thus to find the longest path in the TSA.

   Fig .3 Transition Scheduling Algorithm

   The length of the horizontal direction of an TSA is the maximum number of rounds that the network can run without depleting the energy of any sensor node, which is denoted as C. Given a network with a fixed topology and a finite amount of initial energy in each sensor node, the maximum round number is derived by dividing the sum of the initial energy of all nodes by the minimum amount of energy consumed in each round. It is necessary to enumerate all possible backbones of the network in order to find the optimal solution. However, this is an exponential time operation, which is intractable. Instead, a polynomial number of backbones are constructed in our algorithm. In order to obtain better results, more backbones should be constructed. Each sensor node consumes a fixed amount of energy in each round when working as a backbone node. A virtual node that corresponds to a sensor node as a node that contains energy.

   Fig .4 Network Animator Window

   The original node is called the ancestor. The virtual nodes of the same ancestor form a virtual group. Virtual nodes in the same virtual group are indexed. Two virtual groups are neighbors if their ancestors are neighbors in the original graph. The virtual nodes that have the same indexes are connected. A virtual node is

   isolated if it does not connect with any virtual node of other virtual groups round. A VSG preserves the connectivity of the original graph. The reason to use this approach is that it will be biased toward nodes with more energy. Nodes with more energy will cause isolated virtual nodes. In this way, the CDS construction algorithm is forced to pick virtual nodes with more energy.

   VII THE DISTRIBUTED IMPLEMENTATION OF ENERGY SCHEDULING

   A distributed implementation of VBS called Frequentative Replacement Algorithm (FRA) [1]. FRA lets each backbone sensor node find local replacement nodes to form a new CDS that preserves the connectivity of the network. Each sensor node of the backbone sensor only needs local information to do this. Execution time, in each round, a backbone node that decides to switch its status collects or updates the information of its h-hop neighbors to find replacement nodes. The time used to perform these operations should be minimized. Quality of the results, generally, more information (higher h) yields better results, which achieves a longer lifetime. However, it increases the message overhead and prolongs the execution time.

   Fig. 5 Network Lifetime Graph

   These two issues are contradictory. Various algorithms are available in the literature, and they should be investigated carefully to choose the most appropriate one. First, topology information does not need updating because sensor nodes are static. Second, energy consumption can be estimated according to the working statuses of sensor nodes. These two techniques avoid the costly message exchange of the FRA. If all backbone nodes start the replacement simultaneously, many sensor nodes may contend the shared channel, which causes packet collision and loss. This situation

   may cause an increased execution time and more energy consumption. Backbone nodes with lower energy supplies are more eager to switch statuses, which helps balance the energy consumption of sensor nodes.

   VIII CONTRIBUTION OF MES TO SENSOR NETWORK

   By using the Minimum Energy Scheduling the advantages are follows. MES algorithm is more favorable for dynamic link scheduling and network protocol designs in energy-constrained wireless networks. Significantly reduces the energy consumption compared to the original MaxWeight algorithm. The energy efficiency attained by the MES algorithm incurs no loss of throughput-optimality. MES supports Scalability Depending on the application, the number of nodes used may exceed hundreds (Refer Fig 4) and MES supports it.

   IX PERFORMANCE MEASUREMENT

   We use simulations [Fig 7 ] to evaluate the performance of VBS.

   Fig. 6 Result in Trace File

   The proposed algorithms are implemented in a network simulator. The simulator implemented the CDS construction algorithms that are used in this paper and has been used in previous work. We present the results of the network lifetime(Fig 5) and the energy balance(Fig 9). The packet transmission of data using the above algorithm also plotted(Fig 6).The networks are modelled as graphs. From the above figure the general parameters such as Packet Reception, Throughput, Energy consumption and Jitter can be calculated using the algorithms.

   Fig. 7 Packet Transmission

   Sensor modes are randomly placed in a square area. The sink is placed at the centre of the area. All sensor nodes have the same transmission range. The number of sensor nodes is varied to model different network densities and scales. We assume that the sensor nodes in the backbone consume 1 unit of energy per round.

   The exhaustive search for the optimal network lifetime is too time-consuming, even for small networks of 10 to

   20 nodes; therefore, the optimal values are not presented. All results are obtained by averaging the results of 100 runs in random graphs with the same settings

   .

   Fig. 8 Block Diagram of Ns2

   energy and imbalanced initial energy.senor nodes are employed in 500*500 area. The transmission range is fixed to 250 so that all of the networks generated are fully connected. The number of nodes in the network range from 10 to 100 with step of 10.Since the area of networks fixed the settings vary the density of the nodes.

2. Energy Consumption

Each sensor node is assigned an initial energy drawn uniformly from [50; 100] Because the lifetime is determined by the node with the minimum energy, the achieved lifetime when all nodes work is nearly halved, as shown in the line labeled original. The lifetimes of all schemes in the assessment decrease drastically. However, our proposed schemes still achieve much longer lifetimes. The lifetime increases with network density because CDSs in denser networks are smaller and tend to be disjoint. Algorihms are run for a network of 100 sensor nodes and residual of energy of all sensor nodes are recorded at the lifetime.The Energy consumption is generally based on the transmission data and also based on delay and jitter.

Fig 9 Energy Consumption

A Network Lifetime:

The result of the network lifetime[Fig. 5] is achieved by our proposal algorithms. Here we use identical initial

X CONCLUSION AND FUTURE ENHANCEMENT

A.Conclusion

WSNs require energy-efficient communication to be able to work for a long period of time without human intervention. In this paper, a combined backbone- scheduling and duty-cycling method called Backbone scheduling is presented.It improves upon state-of-the- art techniques by taking advantage of the redundancy in WSNs. We formulate the MLVNS problem to find the optimal schedule and prove its NP-hardness. Two centralized approximation algorithms with different complexities and performances are presented. Additionally, we design FRA, an efficient distributed implementation of VBS.

B Future Enhancement

In Future we have an idea to implement Marking Process method for constructing the CDS.We also have an idea to implement an algorithm using slot reuse concept to provide conflict free scheduling. The slot reuse concept significantly reduces the end-to-end latency without a penalty in the energy efficiency.

Numerical studies are under process regarding random and grid backbone topologies. As per the studies the above algorithm mainly achieves the high power efficiency, zero conflict reduces end to end delay and overall energy usage.

REFERENCES

1. Yaxiong Zho , Jie Wu, Feng Li and Sanglu Lu, On Maximizing the Lifetime of Wireless Sensor Networks Using VirtualBackbone Scheduling

   IEEE Transactions On Parallel And Distributed Systems, Vol. 23, No. 8, August 2012

2. V. Shnayder, M. Hempstead, B.-r. Chen, G.W. Allen, and M.Welsh, Simulating the Power Consumption of Large-Scale Sensor Network Applications, Proc. Second Intl Conf. Embedded Networked Sensor Systems (SenSys 04), pp. 188-200, 2004.

3. C. Misra and R. Mandal, Rotation of CDS via Connected Domatic Partition in Ad Hoc Sensor Networks, IEEE Trans. Mobile Computing, vol. 8, no. 4, pp. 488-499, Apr. 2009.

4. W. Ye, J. Heidemann, and D. Estrin, An Energy- Efficient MAC Protocol for Wireless Sensor

   Networks, Proc. IEEE INFOCOM, pp. 1567-1576, 2002.

5. Q. Cao, T. Abdelzaher, T. He, and J. Stankovic, Towards Optimal Sleep Scheduling in Sensor Networks for Rare-Event Detection, Proc. ACM Fourth Intl Symp. Information Processing in Sensor Networks (IPSN 05), pp. 20-27, 2005.

6. A. Keshavarzian, H. Lee, and L. Venkatraman, Wakeup Scheduling in Wireless Sensor Networks, Proc. Seventh ACM Intl Symp. Mobile Ad Hoc Networking and Computing (MobiHoc 06), pp. 322- 333, 2006.

7. R. Cohen and B. Kapchits, An Optimal Wake-Up Scheduling Algorithm for Minimizing Energy Consumption while Limiting Maximum Delay in a Mesh Sensor Network, IEEE/ACM Trans.Networking, vol. 17, no. 2, pp. 570-581, Apr. 2009.

8. Y. Li, W. Ye, and J. Heidemann, Energy and Latency Control in Low Duty Cycle MAC Protocols, Proc. IEEE Wireless Comm. And Networking Conf. (WCNC 05), pp. 676-682, 2005.

9. J.W. Hui and D.E. Culler, IP is Dead, Long Live IP for Wireless Sensor Networks, Proc. Sixth ACM Conf. Embedded Network Sensor Systems (SenSys 08), pp. 15-28, 2008.

10. L. Doherty, W. Lindsay, and J. Simon, Channel- Specific Wireless Sensor Network Path Data, Proc. Intl Conf. Computer Comm. And Networks (ICCCN 07), pp. 89-94, 2007.

11. F. Dai and J. Wu, An Extended Localized Algorithm for Connected Dominating Set Formation in Ad Hoc Wireless Networks, IEEE Trans. Parallel Distributed Systems, vol. 15, no. 10, pp. 908-920, Oct. 2004