Maximizing the Lifetime of Wireless Sensor Networks using Scheduling Transition Algorithm

Maximizing the Lifetime of Wireless Sensor Networks using Scheduling Transition Algorithm

1. Santhosh Kumar N (M.E), 2. Karthik V (M.E.)

1. Communication systems, Department of ECE, Sri Krishna College of Engg. and tech Coimbatore, India

2. Assistant professor, Department of ECE, Sri Krishna College of Engg. and tech Coimbatore, India

Abstract Wireless Sensor Networks (WSNs) are key for the applications that involve long-term and low-cost monitoring and actuating. In these applications such as battle field ,security surveillance, the sensor nodes use batteries as the sole energy source, thus the energy efficiency becomes critical issue. We observe that many WSN applications require sensor nodes to achieve fault tolerance and Quality of Service (QoS) of the sensing. where the same redundancy may not be necessary for multihop communication because of the traffic conditions and the stable wireless links. here we present a novel sleep- scheduling technique called Backbone Scheduling (BS). BS is designed for WSNs has redundant sensor nodes. BS forms multiple overlapped backbones which work alternatively in order to prolong the network lifetime. In BS, traffic is only forwarded by backbone sensor nodes and the rest of the sensor nodes turn off their radios to save energy. The particular rotation of multiple backbones makes sure that the energy consumptions of all sensor nodes is equally balanced, which is fully utilizes the energy and achieves a effectively better network lifetime compared to the existing techniques. The scheduling problem of BS is formulated as the Maximum Lifetime Backbone Scheduling (MLBS) problem. Since the MLBS is NP-hard, we propose approximation algorithm based on the Schedule Transition algorithm (STA). Theoretical analyses and simulation studies verify that BS is superior to the existing techniques.

Keywords Wireless sensor networks (WSNs), backbone scheduling, sleep scheduling, energy-delay tradeoff, connected dominating set, complexity analysis.

1. INTRODUCTION

   The Wireless Sensor Networks (WSNs), an key technology for various applications which involve long-term and low- cost monitoring, such as battlefield , building inspection, security inspection, etc. In WSN, the battery is the sole energy source . Sensor nodes are allowed to work on batteries for several months to a few years without replacing. Thus, the energy efficiency becomes a critical issue . Among the functional components of a sensor node radio consumes a major portion of the energy. However Various techniques are proposed to minimize its energy consumption. here, we focus on Backbone Scheduling (BS), which dynamically turns off the radio of the sensor nodes to save energy. Backbone Scheduling lets a fraction of some of the sensor nodes in the network to turn on their radio to forward the messages, which forms a backbone; the rest of the sensor nodes in the network turn off their radio to save energy.

   technique does not affect communication quality because of redundancy. because of redundancy, we mean that some sensor nodes turn off theirradio in a WSN does not affect the connectivity of the WSN.Thus redundancy results in more than the available necessary wireless links. Thus it is possible to construct communication backbones to save energy. we use Connected Dominating Set (CDS) algorithms to construct such backbones.a single backbone does not prolong the network lifetime. An intuitive idea is to construct a multiple disjointed CDSs and let them work alternatively. This approach has been studied in and is formulated as a Connected Dominating Partition (CDP). Fig. 1 shows an example of two disjoint backbones. here we propose Virtual Backbone Scheduling (BS), a novel algorithm that enables fine grained sleep scheduling. BS schedules multiple backbones so that the network energy consumption is evenly distributed to all sensor nodes in the network. In this way, the energy of all of the sensor nodes in the network is fully utilized, which in turn prolongs the network lifetime. Thus The figures shows a WSN of five sensor nodes and one sink. The stack beside each node in the network represents its initial energy. Assuming that all sensor nodes consumes a 1 unit of energy per unit of time, each sensor node can continuously work for 3 units. Since only one disjointed CDS, which is{sink; 0; 1}, {sink; 0; 3}, or {sink; 1; 3}, can be constructed the network lifetime is 3 units of time. where BS schedules {sink; 0; 1} to work for 1, {sink; 0; 3} for 1, and {sink; 1; 3} for 2 units of time, which achieves a total network lifetime of totally 4 units of time. The backbones are over lapping . This example demonstrates that the scheduling on a finer granularity can exploit the redundancy in the available network and achieve a longer network lifetime than the CDP-based approach. Nowadays, Duty- Cycling (DC) has become an integral technique for WSNs. BS combines BS with DC by letting backbone sensor nodes work in a duty cycle. Fig. 3 gives the duty cycle produced by BS of the two backbones in Fig. 1. In order to find the optimal schedule that maximizes the network lifetime by using BS, we are formulating the Maximum Lifetime Backbone Scheduling (MLBS) problem. We prove that it is usually NP-hard. We present two centralized approximate algorithms to the MLBS problem. We design a distributed implementation of BS. We usually demonstrate, through extensive analyses and simulations, that our proposed solutions periodically increases the network lifetime compared to the existing approaches. Our contributions in this paper are as follows

   • We propose BS, a combined backbone scheduling and duty-cycling method for WSNs with the redundancy. BS employs a fine-grained sleep scheduling method, significantly prolongs the network lifetime. We formulate the MLBS and prove its NP-hardness;

     Fig. 1. An example of rotating two disjoint backbones in a (duty-cycled) WSN. The sink has an unconstraint energy supply and is implicitly included in all backbones.

   • We design two centralized approximate algorithms and a functional implementation of BS.

     Fig. 2. A simple network consisting of five sensor nodes and a sink, where each sensor node has 3 units of energy. 1 unit of energy is consumed per unit of time. This graph only has one disjoint CDS formed by {sink; 0; 1},

     {sink; 0; 3}, or {sink; 1; 3}. The network lifetime is 3 units of time using the CDP approach.

   • We conduct extensive analyses and execution studies to check the performance of BS.

   The rest of the paper is organized as follows. Section II presents the construction of CDS and Section III network model and problem definition. Section IV presents a scheduling transition algorithm-based approximation algorithm, section V performance evalution finally section VI concludes the paper.

2. CONSTRUCTION OF CDS

   The algorithm first finds a CDS and then prunecertain redundant nodes in the CDS. The initial CDS Uconsists of all nodes in the WSN which have at least two non-adjacentneighbors. A node u in U is considered as locally redundantif it has either a neighbor in the U with larger ID whichdominates all other neighbors of u in the network, or two adjacentredundant nodes from U. This algorithm applies only towireless networks whose unit-disk graph is usually not acomplete graph. the approximation factor of this algorithmremains unspecified. Obviously, the MCDS of any

   wirelessad hoc network whose unit-disk graph is not a complete graphconsists of at least two nodes. On contrary, any CDScontains atmost n nodes.Thus, the approximation factor of the abovealgorithmis at most n n where n is the number of

   2

   nodes.Next,we show that the approximation factor of the abovealgorithm is exactly n .

   2

   Fig. 3. Combining BS and DC to further prolong the network lifetime.

   This means that the above algorithmdoes perform extremely poor over certain instances.When n is even, we consider the instance illustratedin Figure 4(a). These nodes are evenly distributed over thetwo horizontal sides of a unit- square. in which Each node has exactlym neighbors, one in the opposite horizontal side and the restin the same horizontal side. Any MCDS consists of a pair ofnodes lying in a vertical segment. the CDS outputby the algorithm in consists of all nodes. usually for eachnode u, the unique neighbor lying in the opposite horizontalside is not adjacent to all other neighbors of u in the network. Theinitial CDS U consists of all the available nodes. no singleneighbor of the node u can dominate all other neighbors of u.Furthermore, if a pair of neighbors of u are usually adjacent, theymust be lie in the same horizontal side as u; and thereforeneither of node is adjacent to the unique neighbor of u lyingin the opposite horizontal side. So no other node is locallyredundant. Consequently the output CDS still consists of allnodes.

   u*

   (a) (b)

   Fig.4. instance for which the CDS output consists of all nodes but the MCDS consists of only two nodes.

   When n is odd, we consider the instance illustrated inFigure4(b). The node with the largest ID in the particular network,which is denoted by u* , is the center of the left vertical side of a unit-square, and all other n-1 nodes are

   u

   evenly distributed. The two nodes at the left two corners of the unitsquare forms the MCDS. On the other hand, the CDS output by the algorithm. In fact, following the same argument as in the even case, all other nodes other than u* are in the

   part and may even dominate the energy consumption. Therefore, we only consider the scheduling of the radio. Sensor nodes are duty-cycled and have the same duty cycle. We define T continuous cycles as a round, where T _ 1.where

   initial CDS U. The node

   * is also in the initial CDS U as well.

   T is a tunable parameter. At the beginning of each round, a

   Since u* is not adjacent to the two nodes at the right corners of the unit-square, all the nodes other than u* are not locally redundant. The u* itself is also not locally redundant. Therefore, the output CDS still consists of all nodes.

   The implementation of the above algorithm given in runs in two phases. In the first phase, each node will first broadcasts to its neighbors the entire set of its neighbors, and after receiving this adjacency information from all neighbors it declares itself as a dominator if and only if it has two nonadjacent neighbors. These dominators form the initial CDS. In the second phase, a dominator declares itself as a dominatee if it is locally redundant. Note a dominator can find whether it is locally redundant from the adjacency information of all its neighbors.the total message complexity is o(n) and

   the time complexity at each node is o(2 ) . A more accurate

   backbone is selected to work in duty-cycle. Nodes that are not in the backbone will turn off their radios.thereforeThe 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 available lifetime of all of the sensors in the network. Because backbones rotate after each round, lifetimeiscounted in rounds. We also assume that the traffic load inthe network is light. This assumption implies that thecontentions and the interference of the wireless channel arelight too. Additionally, because we assume that sensor nodesare static,thus the route failure is rare . Actually, recent workshows that the delivery ratio of a WSN in a real-world indoorenvironment can be as high as 99 percent in acontinuous operation of four weeks to a few months without replacing. Based on thesearguments, we will not consider the loss of the controlpackets in the design.

   message complexity is

   ()(m)

   where m is the number of

   edges in the graph, as each edge contributes two messages in the first phase. The o(2 ) time complexity, however, is not correct. In fact, in order to decide whether it is locally redundant in the second phase, a node u in the initial CDS may have to examine as many as o(2 ) pairs of neighbors, and for

   each pair of neighbors, as much as o() time may be taken to find out whether such pair of neighbors in which together dominates all other neighbors of u. Therefore, the time complexity at each node may be as high as o(3 ) , instead of

   B. The Maximum Lifetime Backbone Scheduling Problem and its NP-Hardness

   In order to find the optimal scheduling, we formulate the Maximum Lifetime Backbone Scheduling problem. Its definition is as follows. A schedule in BS is a set of backbones working sequentially in every round. Formally, we need to find a set of backbones, 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 }, that satisfy the following constraints:

   o(2 )

   . Note that m and can be as many as

   o(n2 )

   and

   • Connectivity. All

     Bi B

     is a connected subgraph

     o(n) respectively. Thus, the message complexity and the time

     of the network, and all other nodes are, at most, 1-

     complexity of the distributed algorithm are

     o(n2 )

     and

     hop away from a node in

     Bi . In other words, they

     o(n3 )

     respectively. The instances shown in Figure 3 do

     are CDSs of the network.

   • Energy constraints. The amount of energy consumed

   require such complexities

3. NETWORK MODEL AND PROBLEM DEFINITION

   In this section, we discuss the network model and the assumptions. We then define the MLBS problem and prove its NP-hardness.

   1. Model and Assumptions

      We must have the following assumptions about the WSNs that we consider. Sensor nodes are randomly placed in the field and are immobile thereafter. A battery is the sole energy source. There is only one sink in the network, which it is always active and has an infinite power supply. All sensor nodes have an identical communication range (links are bidirectional). The power consumption of aeach sensor node is comprised of three parts: sensing, computing, and radio. in a typical sensor node, the radio is the most power-consuming

      by any of the sensor node in the network at the end of the lifetime the network does not exceed its initial value.

      The lifetime of a schedule is usually the lifetime of the network using this schedule we want to turn on and off the radio of the sensor nodes. The objective of the MLBS problem is to find that schedule that achieves the maximum networklifetime.The MLBS problem is NP- hard.

      1. A SCHEDULING ALGORITHM BASED APPROXIMATION ALGORITHM

         Our first centralized algorithm isbased on a new concept called Scheduling Transition algorithm(STA). A STA is used to model a schedule in a WSN. Fig. 5gives an example. As shown in theabove figure, where the horizontal axisrepresents the time scale, counted in rounds. In every round,possible states are listed vertically they are represented

         byellipses. The number of possible states for each round isequal to the number of backbones.in which Each state contains abackbone and the corresponding energy levels. The state and the backbone have a one-to-onemapping. An initial state is placed at round 0 and isstarting point.Unidirected

         V IE

         C n

         Because n is in

         (1)

         O(V ) and is a constant, C is in

         O(IE)

         transition edges connect sttes inone round to those in the next round. No the backward edges areallowed. Each edge represents the time elapse of 1 round.Since energy is used in each of the round, each edge alsorepresents the consumption of energy. We also assume that thesensor nodes in the backbone network consume a fixed amount ofenergies in each round; all the edges represent the same amountof energy consumption. The residual energy of all nodes isobtained by subtracting each of these values from the starting state ofeach transition edge. No transition is allowed if the energy ofany sensor node of a state is depleted.that It is clear that adirected

         .Usually, the capacity of the batteries is limited, so e cantreat IE as a constant; C then becomes a constant too.

   2. Energy Level

   i

   The reason behind the introducing concept of energy level inorder to facilitate clean criteria for the search in the SA. Wedefine the energy level _ of a WSN of V sensor nodes as atuple of all of the residual energy values of all of the sensornodes in the WSN. Suppose that each sensor node vi

   path from the initial state corresponding to a schedule.Thus,

   in aWSN has E r i units of residual energy, then the energy

   the MLBS problem is thus to find the longest path inthe STA

   levelof this network is E r , E r ,….., E r .

   1 2 V

   We further define the (lessthan) relation between

   twoenergy levels as follows: two energy levels, 1 and 2

   ,satisfy

   , only if, for each i {1,2,…, v}

   and

   1 2

   i 1 i

   E r1 ; E r 2

   there is

   E r1 E r 2 .

   i i

   1 2 if 1 2 , and there is at least one I such that

   Fig. 5. The illustration of a SA. The initial state is attached is a common starting point for the scheduling.

   A. Time Span of an STA

   The length of the horizontal direction of an STA isthe maximum number of available rounds that the network can runwithout depleting the energy of any of the particular sensor node, which isdenoted as C. Given a network with a fixed topology and afinite amount of initial energy in each sensor node, themaximum round number is usually derived by dividing the sum ofthe initial energy of all nodes in the network by the minimum amount ofenergy consumed in each round.

   First, we assume that each backbone node consumes afixed amount of energy _ in each corresponding round. Because the MCDS isthe lower bound of the number of sensor nodes in aCDSof theWSN, the number of sensor nodes in any backbone is largerthan that of theMCDS.Suppose that the size of theMCDSis n,then the minimum energy consumption in

   each round is atleast n. Denote IE as the initial energy

   of the sensor node inthe network. Then, the total amountof

   E r1E r 2 .

   i i

   An energy level is zero if at least one element must be as zero. Zeroenergy levels are less than any nonzero levels, and must indicatethe end of the available network lifetime.thusThe terminating state of anypath in the STA contains a zero energy level.where The energylevel of the initial state of the SA is formed by the initialenergy of all of the sensor nodes in the WSN.

   1. The STA-Based Algorithm

      The approximate algorithm is based on the dynamic programming. Its pseudocode is listed in Algorithm 1. The search starts from the initial state. After a backbone transition, the states energy levels are computed from those of the starting state of the transition. Each state keeps the larger energy levels. A path terminates when its associated energy level is zero. When all paths terminate, the longest path is found.

      Algorithm 1.STA-based algorithm

      1. 1.IntCUR_ROU ND=0; 2.Repeat

         1. For each state Sdo

         2. Get the associated energy level of S;

         3. Prune the resultant energy levels using the min()

            function;

            energy that can be usedis

            V IE , where V is the number of

         4. Select the energy level with maximal minimum energy value.

            sensor nodes in thenetwork. The maximum round number C is given by 1

         5. Set Ss energy level to the energy level with the maximum summation amoung the resultant energy

            levels;

      2. 8.End for

   1. CUR_ROUND=CUR_ROUND+1;

   2. Until all the energy levels of the states in CUR_ROUND are zero:

   3. Return the schedule represented by the path ending in

   CUR_ROUND

   Fig. 6. The corresponding VSG (right) of a network of three sensor nodes (left). The virtual nodes of different ancestors are connected with an increasing index order. As a result, virtual node 2 of sensor node B is isolated because it has more energy and cannot be connected to the virtual nodes of A or C.

   1. PERFORMANCE EVALUATION

      We use simulations to evaluate the performance of BS.that The proposed algorithms are implemented in a customized 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 and the energy balance of the network. The simulation results of the message delivery delay and the microscopic behaviors of ILR are in Section 6 of the online supplementary file.

      The networks are modeled as unit disk graphs. Sensor modes are randomly placed in a particular square area. The sink is placed at the center of the network. All sensor nodes have the same transmission range in the network. The number of sensor nodes is varied to model different network density and scale. We assume that the sensor nodes in the backbone consume 1 unit of energy per round.

      We compare BS with the CDP-based method . We use Rules 1 and 2 and Rule K to construct a backbones. The exhaustive search for the optimal network lifetime is too time- consuming for small networks of 10 to 20 nodes.therefore, the optimal values are not presented. for All results are obtained by averaging the results of 100 runs in random graphs with the same settings.

      Fig. 7. Lifetime of networks with uniformly distributed initial energy in the interval [50 J; 100 J], using MP together with Rules 1 and 2 and Rule K

      A. Network Lifetime

      In this section, we present the results of the network lifetime achieved by algorithms. Two configurations are used: identical initial energy and imbalanced initial energy. Sensor nodes are deployed in a 500 _ 500 area. The transmission range is fixed to 250 so that all of the networks generated are fully connected with the network. The number of nodes in the network ranges from 10 to 100 with a step . Since the area of the network is usually fixed, these settings vary the density of the sensor nodes.

      fig. 7 presents the results in networks with uniformly distributed initial energy level. Each sensor node is assigned an initial energy drawn uniformly from[50; 100].therefore the lifetime is determined by the node with the minimum energy,therefore 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 decreases periodically. However, our proposed schemes still achieve much longer network lifetimes. The lifetime increases with network density because CDSs in denser networks are smaller and tend to be disjoint.

   2. CONCLUSION

WSNs require energy-efficient communication to be able to work for a long period of time without human intervention. In this paper, we present a combined backbonescheduling and duty-cycling method called BS. BS improves upon state-of-the-art techniques by taking advantage of the redundancy in WSNs. We formulate the MLBS problem to find the optimal schedule and prove its NP-hardness. centralized approximation algorithms with different Complexities and performances are presented. We also conduct extensive theoretical analyses and simulation studies to verify the performance of BS

1. 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.

2. 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.

3. W. Ye, J. Heidemann, and D. Estrin, An EnergyEfficient MAC Protocol for Wireless Sensor Networks, Proc. IEEE INFOCOM, pp. 1567-1576, 2002.

4. 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.

5. 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.

6. 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.