Virtual Backbone Scheduling For Balancing Energy Efficiency In Wireless Sensor Networks

Virtual Backbone Scheduling For Balancing Energy Efficiency In Wireless Sensor Networks

Shalini C. R Nirmala.S

M Tech 4th sem. CSE Professor,Dept. Of CSE

AMC Engg. College. AMC Engg. College Bangalore, India Bangalore, India

Abstract- Wireless Sensor Networks (WSNs) are key for various applications that involve long-term to monitor physical or environmental conditions such as temperature, sound, vibration, pressure, motion or pollutants and to cooperatively pass their data through the network to a main location. In these applications, sensor nodes use batteries as the sole energy source. Therefore, energy efficiency becomes critical. To meet this challenge, this paper proposes, a novel sleep-scheduling technique called Virtual Backbone Scheduling (VBS). In contrast to earlier MAC protocols designed for general-purpose networks.VBS is designed for WSNs has redundant sensor nodes. VBS forms multiple overlapped backbones which work alternatively to prolong the network lifetime. In VBS, traffic is only forwarded by backbone sensor nodes, and the rest of the sensor nodes turn off their radios to save energy.

KeywordsWireless sensor networks (WSNs), backbone scheduling, sleep scheduling, virtual backbone, energy-delay tradeoff,

1. INTRODUCTION

   A wireless sensor network (WSN) consists of spatially distributed autonomous sensors to monitor physical or environmental conditions such as temperature, sound, vibration, pressure, motion or pollutants and to cooperatively pass their data through the network to a main location. The more modern networks are bi-directional also enabling control of sensor activity. The development of wireless sensor networks was motivated by military applications such as battlefield surveillance. Today such networks are used in many industrial and consumer applications such as industrial process monitoring and control, machine health monitoring and so on. The WSN is built of "nodes" from a few to several hundreds or even thousands where each node is connected to one (or sometimes several) sensors. Each such sensor network node has typically several parts: a radio transceiver with an internal antenna or connection to an external antenna, a microcontroller, an electronic circuit for interfacing with the sensors and an energy source usually a battery or an embedded form of energy harvesting. In most WSNs, the battery is the sole energy source of the sensor node. Sensor nodes are expected to work on batteries for several months to a few years without replenishing. Thus, energy efficiency becomes a critical issue in WSNs. Among the functional components of a sensor node, the radio consumes a major portion of the energy [1]. Various techniques are proposed to

   minimize its energy consumption. To meet this challenge, this paper proposes Virtual Backbone Scheduling for energy saving and increased network lifetime makes use of the combination of an energy-effective virtual backbone construction together with a robust, simple, stateless routing scheme for data delivery. BS lets a fraction of some of the sensor nodes in the network in a WSN turn on their radio to forward messages, which forms a backbone; the rest of the sensor nodes turn off their radio to save energy. This technique does not affect communication quality because WSNs have redundancy.

   By redundancy, we mean that turning off the radio of some sensor nodes in a WSN does not affect the connectivity of the network. This redundancy results in more than necessary wireless links. Thus, it is possible to construct communication backbones to save energy.VBS 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.

   In order to find the optimal schedule that maximizes the network lifetime by using VBS, we formulate the Maximum Lifetime Backbone Scheduling (MLBS) problem. This is NP- hard. It presents two centralized approximation algorithms to the MLBS problem. This demonstrate, through extensive analyses and simulations, that our proposed solutions significantly prolong the network lifetime compared to the existing approach. The contributions in this paper are as follows:

   • The VBS is, a combined backbone scheduling and duty-cycling method for WSNs with redundancy. VBS employs a fine-grained sleep-scheduling method, which significantly prolongs the network lifetime. the formulation is the MLBS problem and prove its NP- hardness;

   • It designs two centralized approximation algorithms and a distributed implementation of VBS.

2. RELATED WORK

   2.1 DUTY-CYCLING MAC PROTOCOLS

   Duty-cycling is built into most of the existing MAC protocols. S-MAC [2] introduced the idea of duty-cycling and scheduled sleeping into the MAC protocol. Sensor nodes follow a periodic active/sleep cycle, and the sensor nodes that are close to each other synchronize their active cycles together to reduce transmission delay. Sleep scheduling techniques can be classified into two categories: synchronous [3] and asynchronous [4] Synchronous scheduling is more complicated, but offers lower communication delay. In synchronous scheduling, sensor nodes know their neighbours wakeup times and try to find schedules that can minimize energy consumption and communication delays. For example, in S-MAC [2], sensor nodes overlap their active time with their neighbours in order to reduce the waiting time to transfer messages. On the contrary, in asynchronous scheduling, sensor nodes choose schedules independently, knowing nothing about their neighbours.

   As a result, in asynchronous scheduling, a sender needs to send a persistent preamble to notify the receiver (sender- initiated), or receivers broadcast a notification to all of their neighbors to solicit potential senders (receiver-initiated) As for the theoretical aspects of the sleep scheduling problem, it has been proven in [3] that the problem of finding the sleep schedule with the minimum end to- end delay is, in general, NP-Hard. However, optimal scheduling can be found in polynomial time for tree and ring networks. The energy-delay trade-off in tree shaped WSNs has been studied. In five wakeup patterns used in previous works are summarized. All of the methods introduced above use homogeneous scheduling, which does not consider the redundancy in the network.

3. NETWORK MODEL AND ASSUMPTIONS Sensors are randomly placed in the field. There is only

   one sink in the network, which is always working and has an infinite power supply. The links between sensors are undirected. VBS works with duty- cycling. That define

   T(T 1) continuous cycles as a round. VBS rotates backbones at the end of each round. A nodes lifetime is the time span from when it starts working to when its energy is depleted. Network lifetime is the minimum lifetime of all the sensors in the network. A schedule in VBS is a set of backbones that working sequentially. It is represented by a set of tuples where Ti is the working time of backbone Bi. The goal is to find a schedule with maximum network lifetime

   The lifetime of a sensor node is the time span from when it starts working to when its energy is depleted. 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. The assumption is that the traffic load in the network is light. This assumption implies that the contention and the interference of the wireles channel are light too. Additionally, because the sensor nodes are static, route failure is rare too.

4. VIRTUAL SCHEDULING GRAPH (VSG)

   In this section, we aim to design a heuristic with less complexity than the STG-based algorithm. In STG, the energy and structure of the WSN are modeled separately. In this section, we propose a new concept called Virtual Scheduling Graph that can model the energy and structure together, which facilitates an elegant greedy algorithm. In a VSG, a sensor node in the original network graph is converted into multiple virtual nodes, which are connected in such a way that their degrees represent the energy of the corresponding sensor node. A schedule can be obtained by applying any CDS construction algorithm on the VSG.

   4.1 The Definition of VSG

   As stated before, each sensor node consumes a fixed amount of energy " in each round when working as a backbone node. We define a virtual node that corresponds to a sensor node as a node that contains " energy. The original node is called the ancestor. An ancestor of Er energy is divided into {Er÷} virtual nodes. 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. The following VSG rules where V 0 and V are the sets of vertexes, and L0 and L are the sets of edges: In a VSG, each ancestor is replaced by a clique of virtual nodes. The size of the clique corresponds to the energy of the ancestor. Nodes of two neighboring virtual groups are connected with an increasing index order until one groups virtual nodes are all connected. Suppose that two virtual groups have m and n virtual nodes, respectively. The priority of a virtual node is a tuple of its degree and ID, where the ID is its ancestors ID plus the virtual node index (e.g., A0, A1, A2).

   Algorithm 1 VSG based VBS

   1: S {}

   2: Construct the VSG Gs(V ,E) of G(V,E) 3: repeat

   4: Construct a CDS C in VSG using rules 1 & 2 5: Construct the PMCDS C from C

   6: Remove the highest indexed VNs of the ancestors whose VN is in C from Gs(V ,E)

   7: Apply the VSG rules to eliminate edges between virtual groups of different sizes.

   8: Find the corresponding CDS Ci of C in G

   9: Append (Ci, Ti) to S

   10: until Any ancestors VNs are all eliminated from

   Gs(V,E)

   11: return S

5. CONCLUSION

The new scheduling method for WSNs called Virtual Backbone Scheduling. VBS combines virtual backbone and sleep scheduling, which achieves longer lifetimes for WSNs over existing methods. A combined backbone-scheduling and duty-cycling method called VBS. VBS improves upon state- of-the-art techniques by taking advantage of the redundancy in WSNs. This virtual backbone scheduling can increase the energy efficiency of wireless sensor networks.

REFERENCES

1. V. Shnayder, M. Hempstead, B.-r. Chen, G.W. Allen, and M. Welsh, Simulating the Power Consumption of Large-Scale Sensor Network Applications, pp. 188-200, 2004.

2. W. Ye, J. Heidemann, and D. Estrin. An energy- efficient mac protocol for wireless sensor networks. In Proc. of IEEE Infocom02, pages 15671576, 2002.

3. G. Lu, B. Krishnamachari, and C. S. Raghavendra. An adaptive energy-efficient and low-latency mac for data gathering in wireless sensor networks. In Proc. IEEE IPDPS04, pages 224235, 2004.

4. J. Wu and F. Dai. A generic broadcast protocol in ad hoc networks based on self-pruning. In Proc. of IEEE IPDPS03, pages 2941, 2003.