DOC

Raie Ramadan-38.doc

By Pedro Hall,2014-11-07 07:51
10 views 0
Raie Ramadan-38.doc

     1

    Scheduling in Stochastic Wireless Sensor Network: A Survey

    Hosam Rahhal Rabie Ramadan Samir I. Shaheen

    Cairo University ,Computer Al-Azhar University , Systems and Cairo University ,Computer

    Engineering Department Computers Department Engineering Department

    hosamrahhal@gmail.com Rabie.Ramadan@Guc.edu.eg sshaheen@ieee.org

    ; these sensors. Therefore, it is desirable to operate wireless

    sensors at a low duty cycle the fraction of time the sensor is Abstract Wireless Sensor Networks are formed by small

    on (e.g., have a sensor turned on /active for only 1% of the battery-powered devices that combine sensors, microprocessors,

    time). and radios used to communicate with each other enabling the

    However, alternating sensors between on and off (active monitoring and control of various physical systems.

    and sleep) states inevitably disrupts the network operation, Therefore, energy saving is one of the critical issues for sensor

    e.g., routing, coverage and connectivity. At the same time, networks. To do so, one common approach is to dynamically

    this process might not be synchronized between the sensor schedule sensors’ in work/sleep cycles. It is uncertain which

    nodes. Thus, a stochastic sensor networks (SWSN) are sensor nodes will be operating at any given time. This forms

    formed. The key concept of stochastic sensor networks is that what is called stochastic sensor network. This paper gives the

    each sensor node operates with a relatively small duty cycle reader the state of the art of the scheduling techniques and

    algorithms that are used with such network. which may be di;erent from that of other nodes. The duty

     cycles vary depending on various environmental and arti?cial

    Index Terms wireless sensor networks, stochastic sensor factors. Therefore, it is uncertain which sensor nodes will be network, sleep\awake up cycle, scheduling techniques. operating at any given time. The stochastic sensor networks have many features, when

    energy is limited; the capabilities of sensor nodes need to be 1. INTRODUCTION minimal but sucient. As it is envisioned that sensor networks

    will be embedded broadly in our living environment, high

    ?exibility of these networks is demanded in order to reduce the ecently, the rapid advances in processor, memory, and Rcost of maintenance [4-5]. Other two significant advantage radio technology have enabled the development of distributed exploited by the SWSNs are the utilization of the networks of small, inexpensive nodes that are capable of pre-deployment optimal traffic-flow estimate as well as the sensing, computing, and wireless communication. Wireless ability to utilize directivity of traffic flow given by the sensor networks (WSNs) are collections of a large amount of association process upon deployment of the network. Both of small devices equipped with integrated sensing and wireless

    these features will significantly reduce the excess traffic communication capabilities. They are considered as a special

    while retaining the zero-overhead routing [6]. case of ad hoc networks with reduced or no mobility [1].

    Sensor networks share some important characteristics with ad The rest of the paper is organized as follows. Section 2 hoc networks, for example they share the need for self-discusses the ON\OFF scheduling strategies, the advantages organization, wireless multi-hop operation, and time-and disadvantages of these strategies. Section 3 covered the variability in topology, connectedness and other network mathematical models which describe the ON\OFF scheduling parameters [2]. strategies. Section 4 presented the critical open problems in The sensor networks are expected to ?nd widespread use ON\OFF scheduling for stochastic wireless sensor network. in a variety of applications. Examples of such applications Finally we conclusion this paper by the summary of main include environmental monitoring - which involves points. monitoring air, soil and water, condition based maintenance, habitat monitoring (determining the plant 2. SCHEDULING STRATEGIES: and animal species population and behavior), seismic detection, military surveillance, inventory tracking, smart In the stochastic sensor network, every node alternates its spaces etc. [3]. However, these sensors are operated on battery state between ON and OFF states. There are many ON\OFF power, and energy is not always renewable due to cost, scheduling strategies that model this alternating. Existing environmental and form-size concerns. This places a hard,

    scheduling strategies for sensor networks could be classified stringent energy constraint on the deployment, the design of

    into three categories: the coordinated sleeping, the random the communication (routing) protocols, and the operation of

    sleeping, and on-demand mechanism. In coordinated sleeping

     mechanisms, sensor nodes communicate with each other to

     2

    adjust sleeping schedules, while in random sleeping

    mechanisms, sensors decide to enter sleeping mode randomly In addition to the previous two coordinated sleeping

    and independent of others [7]. In on-demand sleeping mechanisms, in [10], an optimal coordinated sleep was

    scheduling, out-band signaling is used to notify a specific proposed to guarantee abounded-delay sensing coverage and

    node to go to sleep in an on-demand manner. Table 1 maximize the network lifetime. A node can calculate its

    summarizes the scheduling strategies. wakeup time based on its neighbors’ schedules. This process

     is repeated in iterations and eventually all nodes can reach a

    local scheduling decision. Some other sleeping schemes Category Scheme Reference

    assume that the sensors are organized into clusters [11, 12, Coordinated The nodes adjust [8],[9],[10],[11],

    13]. Each cluster has a cluster head to manage the their sleeping [12],[13]

    communication between nearby nodes and the base station. schedule

    The advantages of this algorithm are guarantee abounded-Random No adjustment [16],[17],[18],[19]

    delay sensing coverage and maximize the network lifetime. between the nodes [20],[21],[22],[23]

    However, disadvantage of this algorithm that the node depend in the sleeping

    on its neighbors’ schedules to determine the wakeup time, so, schedule

    it need to be aware of its neighbor positions that mean, more On-demand The node go to [6],[20],[24],[25],

    load in network. sleep depend on [26], [27],[28]

     . the environment

    Nevertheless, in [14], the author proposed a sleep-requirements

    scheduling algorithm, called Linear Distance-based

    Scheduling (LDS) scheme for cluster-based high density The authors in [8] propose a coordinated sleeping

    sensor networks. The goal is to reduce energy consumption scheduling mechanism to avoid losing sensing coverage,

    while maintaining adequate sensing coverage capabilities. To which allows a sensor to shut down only if its sensing area is achieve this goal, the LDS scheme selects sensors farther completely covered by its neighbors. This is done through away from the cluster head to sleep with higher probabilities. checking the sponsored sectors according to the location and The rationale behind this scheme is based on the assumption sensing radius of other working neighbors. The advantages of that each sensor’s radio transceiver is capable of changing its this algorithm are reducing energy consumption, therefore transmission power in continuous steps to achieve different increase system lifetime, preserving the system coverage to

    transmission ranges; a farther away sensor needs more power the maximum extent. In addition, after the node-scheduling to communicate with the cluster head, and therefore, has scheme turns off some nodes, certain redundancy is still higher energy consumption. The LDS scheme only considers guaranteed, which can provide enough sensing reliability in static clusters. i.e., cluster heads are not changed once they many applications. However, disadvantage of this algorithm

    are selected. In summary, LDS selects sensors to sleep is blind points, which may appear when two neighboring

    according to their relative distances to the cluster head. It has nodes expect each other’s sponsoring; so , it needs additional

    the following major characteristics: (1) a sensor does not need scheme to avoid it.

    to know other sensors’ location information; (2) the scheme

    may cause uneven sensing coverage; in other words, a [9] presented another coordinated sleeping mechanism

    location farther away from the cluster head has less sensing where an optimal geographic density control (OGDC) scheme coverage than a location closer to the cluster header; (3) the was proposed to ensure 1-coverage and 1-connectivity. The scheme may cause uneven lifetime in the cluster, i.e., sensors basic idea of OGDC is to minimize the overlapping area of farther away from the cluster header live longer than sensors active sensors so that more sensors can be turned off. A closer to the cluster header. The advantages of this algorithm sensor is turned on only if it minimizes the overlapping area are reducing energy consumption, support different with the working sensors and covers a crossing point of two transmission ranges; the sensor does not need to know other active sensors. The advantages of this algorithm that OGDC

    sensors’ location information. However, disadvantage of this requires less working nodes to maintain coverage and

    mechanism is only considers static clusters. connectivity, reducing energy consumption, therefore increase

     system lifetime. However, this mechanism have many

    Balanced-energy Sleep Scheduling (BS) in [15] extends the disadvantages, If a packet sent from a neighbor is lost for any LDS scheme by evenly distributing the sensing and reason (transmission errors or collisions), a node is simply communication tasks among the non-head sensors so that not aware of the existence of that neighbor. Also, this their energy consumption is similar regardless of their mechanism assume many assumptions as each node is aware distance to the cluster-head. More speci?cally, the authors of its own position, the radio range is at least twice the derived a sleep probability function P(x) so that the total sensing range, all sensor nodes are time synchronized that not energy consumption of a sensor does not depend on x, the always available.

     3

    distance between the sensor and its cluster head. The other because it very density.

    aspects of BS are the same as LDS.

     Adaptive Fidelity Energy-Conserving Algorithm (AFECA) For random sleeping schemes, the author in [16] developed [20] is a sleep management scheme for ad hoc network that a mechanism called PEAS (Probing Environment and alternates the sleep and listen states of a node depending upon Adaptive Sensing) that can extend the lifetime of a high-the neighborhood density, nodes go to sleep for a random density sensor network in a harsh environment. PEAS amount of time. Upon wake-up, the nodes again listen for a conserves energy by separating all the working nodes by a certain time period to determine if they need to switch to minimum distance of c. To check if there is a working active state and maintain or improve the required level of neighbor nearby, each node broadcasts a message (probe) network connectivity. This scheme could be optimized for with a transmission range of c after sleeping for a random WSNs by making the decisions energy- aware. The period. The node will enter the on-duty mode only if it advantages of this algorithm are extending the network receives no replies from working neighbors; otherwise it will lifetime, improving energy consumption, supporting any stay in the off-duty mode. The advantages of this algorithm Sensor Placement, supporting Normal and High Sensor are extending the lifetime of a high-density sensor network in Density. However, disadvantage of this algorithm that the a harsh environment; it eliminates per-neighbor states, thus on/off scheduling for each node depend on listening of the removing the complexity to tracking each neighbor in a dense neighborhood, so, any error in listening cause incorrect deployment, reduced message exchanges. However, decisions, also, nodes need to remember the history disadvantage of this mechanism that each active node need to information when it wake up, supporting only Hierarchical send PROBE message and send back a REPLY message, so, Network Structure, not flat, for extremely non-uniform additional load can be add to network because it very density. topologies large latencies are possible.

    Another randomized sleeping scheme could be found in In the S-MAC scheme [21], energy consumption is reduced [17]. The authors proposed a Randomized Independent by allowing randomly-selected idle sensors to go into the Sleeping (RIS) mechanism which assumes that sensors are sleep mode. The traffic that is sent to these sleeping nodes is synchronized globally and time is divided into slots. At the temporarily stored at the neighboring active nodes. The beginning of each time slot, a sensor independently decides to sleeping sensors wake up periodically to retrieve the stored remain awake or enter sleeping mode with probability of p packets from their neighboring nodes. The advantages of this and 1 ? p, respectively. Therefore, the duration of on/off scheme are reducing energy consumption, also have good periods are geometrically distributed. The advantages of this scalability and collision avoidance capability, reducing algorithm are increasing the lifetime of the network by 1/p, overhearing and control overhead. However, disadvantage of supporting the normal and high Sensor Density. However, this scheme requires periodic synchronization among neigh- disadvantage of this mechanism is support only flat Network boring nodes to remedy their clock drift, for that it need Structure while the Hierarchical Network Structure is not techniques to make it robust to synchronization errors. support. T-MAC [22] is an extension of the S-MAC protocol which

     While in [18] a variation of RIS was proposed where each adaptively adjusts the sleep and the wake periods based on time slot is divided into two parts the ON period and the OFF estimated trac ?ow to increase the power savings and

    period. reduce delay.

    In addition, Span [19] is an energy efficient topology The asynchronous random sleeping (ARS) scheme coordination algorithm for adapting the connectivity proposed in [23], whereby sensors (i) do not need to configuration of an ad-hoc network, whereas the nodes synchronize with each other, and (ii) do not need to randomly decline to forward data and go to sleep, based on coordinate their sleeping schedules. In ARS the sensors wake estimated network density (in dense networks not all nodes up randomly and independent of others in each time slot. It are needed for connectivity). Note that SPAN cannot assumes that sensors are not synchronized and the offsets of con?gure a network to a speci?c degree of connectivity, but it the time slot between nodes are uniformed distributed. The will preserve the original connectivity of the network after advantages of this scheme are k-Coverage guarantee, turning off some redundant nodes. The advantages of this reducing energy consumption without significantly affecting algorithm are making the decisions on whether to sleep or the latency or connectivity of the network, improving in stay awake as coordinators depend on the local information, system lifetime. However, disadvantage of this scheme is improving communication latency, capacity, and network sensors wake up randomly and independent of others in each lifetime. However, disadvantage of this mechanism that each time slot, as result may be the conflict can be occur. node need to periodically broadcast HELLO message that

    contain the node’s status which result in high load in network The disadvantage with all of the randomized sleeping

     4

    schemes is that they cannot ensure complete coverage all the scheduling scheme for active and sleeping periods that is time, so it is important to investigate coverage characteristics based on the packet arrival pattern., it also present an arrival under different conditions. model which is targeted at application characterized by bursty

     arrival. The bursty arrival times are assumed to be distributed Adaptive Self-configuring sEnsor Network Topologies exponentially with different rates for the packet arrival intra-(ASCENT) [24] is an energy aware topology control burst and inter-burst. Based on this packet arrival model, it mechanism that dynamically adapts the participation of nodes introduces a Bursty Arrival Dependent Sleeping Scheduling in the network according to the demands of the application (BASS) scheme, in which each node dynamically and task. Nodes that are not required by the network (due to independently adjusts its wakeup rate. The advantages of this connection redundancies in a dense network) sleep until their Scheme that provide good solution for sensor network with participation is demanded explicitly for satisfying the bursty, it is useful for a wide range of applications application data requirements. ASCENT is energy adaptively characterized by bursty arrivals Arrival, saving the power, switches the operating states (sleep, passive, test and active) increasing the network life. However, there are two of a node based on the network needs. The advantages of this disadvantages with this Scheme. First, it is difficult to mechanism are energy saving, providing adequate instantaneously detect significant changes in the average connectivity, extending the systems life; ASCENT does not arrival rate. Second, if the wakeup rate is setting according to need any location aids, it supports all the Sensor Placement the average packet arrival rate, the delay constraint inter-(Grid, Uniform, Poisson,…etc). However, disadvantages of burst is usually difficult to meet, possibly violating the delay this mechanism that relevant to TDMA MACs only, while it constraint.

    not support to other MAC protocols, The ASCENT

    mechanism does not detect or repair network partitions of the In [20], network nodes are allowed to go to sleep according underlying raw topology, supporting only flat Network to routing information and information from the application Structure while the Hierarchical Network Structure is not layer. Where, the Basic Energy Conserving Algorithm support. (BECA) is proposed. In the BECA scheme, nodes switch

     among sleeping, idling, and active states to save energy. A A distributed algorithm for waking up special sensor nodes node alternates between the sleep state and the idling state if in a heterogeneous sensor network was proposed in [25]. The no traffic is present. An idling node goes into the active state sensor field is scattered with abundant low-powered sensing when it receives traffic from its application or from its nodes that have limited processing and communication neighbors. The advantages of this scheme are reducing the capabilities. Within the network, few high-powered tracker energy consumption, increasing network lifetime. However, nodes are randomly spread to provide in-network processing disadvantages of this scheme are increasing the latency; it and long distance communication functions. The tracker assumed that no routing requests are lost in transit. nodes are switched off initially, and are woken up by the

    sensor nodes, when an event is detected, for data processing In [27], a scheduling mechanism is proposed, which and forwarding. The primary issue addressed in [25] was the maximizes the sensors sleeping time while satisfying the design of a distributed algorithm that enables each sensor to optimal traffic distribution and network connectivity wake-up the optimal number of tracker nodes to meet the data requirements. The subset of nodes to relay sensor traffic is processing demands of the application. In spite of the basic called serving nodes, the serving nodes select their active scheme was designed for heterogeneous sensor networks, the period lengths according to the traffic volumes they are procedure formulated to determine the optimal set of tracker receiving and transmitting based on the optimal traffic nodes might be adopted in pure WSNs to estimate the optimal distribution, the active periods of the serving nodes are called set of active nodes for reliable connectivity. The advantages of their serving times. The advantages of this mechanism are this mechanism are simple and general enough to increasing the network lifetime, energy conservation, accommodate a wide range of sensing applications; it’s satisfying the optimal traffic distribution and connectivity more efficient and scalable than the distributed baseline reserving However, disadvantage of this scheme is The (flooding), the delay overhead of this algorithm is not very optimal traffic distribution is obtained based on the significant. However, disadvantages of this algorithm are not global information of network status as well as local support the event-driven sensor applications, waking up non-estimation, administrative overhead results from the suitable tracker nodes or employing more trackers than parameter estimation and distribution in the initialization necessary for a specific task, can lead to significant waste process.

    of network resources (e.g. energy).

     The authors in [6] formulate the wakeup scheduling as a BASS: an Adaptive Sleeping Scheme for Wireless Sensor graph-theoretical problem. They consider low trac network

    Network with Bursty Arrival is proposed in [26] where the with arbitrary communication ?ows and show that

     5 minimizing the end-to-end communication delay is general

    The first model depends on the Markov Chain; a Markov NP-hard. However, they present ecient heuristic methods to

    process allows modeling the uncertainty in many real-world ?nd the best schedules and prove the optimality of di;erent

    systems that evolve dynamically in time. The basic concepts wakeup patterns under speci?c conditions for special tree and of a Markov process are those of a state and transition. In ring topologies. The advantages of this mechanism are speci?c applications the modeling is to ?nd an adequate state minimizing the communication latency, providing energy description. The associated stochastic process has the efficiency, proved optimal solutions for two special cases: the Markovian property that the knowledge of the present state is tree and ring topologies. However, disadvantages of this sufficient to predict the future stochastic behaviour of the mechanism that assumed that there is very low traf?c within process. In discrete-time Markov processes, state transitions the sensor network, it require mechanism to provide time synchronization in the sensor network, the minimum delay ]. only occur at ?xed times [29

    path obtained may involve longer hops (more transmissions) than the minimum hop-count path on the original graph. Given N static sensors are deployed randomly in a two- dimensional ?eld. The sensing area of each sensor is assumed In [28] many of Sleep and Wakeup Strategies were a circle with radius r centered at the location of the sensor. proposed. In Battery-State-Based Sleep and Wakeup Strategy Each node has a sleep/wake cycle determined by local A sensor node switches to sleep mode if the normalized environmental conditions, which are not known to other battery capacity is below the threshold and it wakes up blownodes. At any given time, there is a probability, denoted P aagain when the battery state becomes higher than the that a node will be in its active state. Since each node is only

    awake for a fraction of the total time, the probability P athreshold . In the Queue-Based Sleep and Wakeup bhidenotes this fraction of time in the mean [30]. A Discrete Strategy the number of packets in the queue is used to Time Markov Chain (DTMC) with two states is used to determine whether a node should switch to sleep mode or not. model the scheduling of the sensor node's states. In this Specifically, if the number of packets in the queue is large, process, the future state of the process only depends on the the node has smaller chance to go to sleep mode. Channel current state of the process and not on its past history. The State-Based Sleep and Wakeup Strategy, in this strategy the random variable is defined for each node i = 1, .., N as Yichannel state of the transmitter is used to determine the sleep and the wakeup probability. In the Solar Radiation-Based the state of node i, i.e., if node i is awake (ON) at time t then

    ttSleep and Wakeup Strategy If the solar radiation is in low we have = 1; otherwise = 0. The data sink, however, YYiistate, the solar cell cannot produce enough energy to charge tis always awake, thus, = 1 for all t. For each node i = 1, Ythe battery in the sensor node. Therefore, the node goes to N1

    tsleep mode with probability P and wakes up with probability s. . ., N, we assume that evolves according to a Discrete Yi1.0 and P (0< P <1) when the solar radiation state is high wwtime Markov process with transition rate matrix, where Band low, respectively. And the finally Hybrid Strategy, in this i

    strategy, if the number of packets in the queue is zero, a 0001?)bbiisensor node will switch to sleep mode. The advantages of = B??i1011bbthese Strategies are increasing the network lifetime, reducing (,ii

    0110energy consumption, maximizing battery capacity. However, And > 0 and > 0 are the transition rates (the bbiidisadvantages of these Strategies are Data packets are stored probability) from OFF to ON, and from ON to OFF, in a finite queue which can buffer up to X packets. Since the respectively. queue size is finite, some of the incoming packets will be dropped upon their arrival if the queue is full, computing the threshold value may be not accurate, so, the fault in determining scheduling decision can occur.

     3. ON \ OFF SCHEDULING MODELS

    The previous section described different scheduling schemes. In this section, we review some of the scheduling models in stochastic sensor network. There are four models which are discrete time Markov chain, continuous time Markov chain, Figure 1: Discrete time Markov chain with two states Passion, and the exponential distribution model. 0110 Where, b=, b= etc ppii00103.1 DISCRETE TIME MARKOV CHAIN (DTMC) MODEL

     6

    process {X (t), t ? 0} by X(t) = the state of the system at time (Probability sensor is active) = or, and pppa0111t. (Probability sensor is sleep) = or ppps1000The process is taken to be right-continuous; that is, at the

     The mathematic expression [32] is: transition epochs the state of the system is taken as the state

    tjust after the transition. The process {X (t)} can be shown to (t+1) = or (t+1) = (if = 1) ppppYa01a11ibe a continuous-time Markov chain [29]. t(t+1) = or (t+1) = (if = 0), ppppYs10s00i

    Where still hold the truth: THE POISSON MODEL 3.3

     + = 1 pp0001There are several equivalent de?nitions of the Poisson + = 1. pp1110process. Our starting point is a sequence of XX,,....12 positive, independent random variables with a common 3.2 CONTINUOUS-TIME MARKOV CHAINS (CTMC) MODEL

    probability distribution. Think of as the time elapsed X n

    thth In the continuous-time analogue of discrete-time Markov nbetween the and occurrence of some (1)nchains the times between successive state transitions are not speci?c event in a probabilistic situation. Let deterministic, but exponentially distributed. However, the nstate transitions themselves are again governed by a (discrete-sXn,,,1,2,.... and s0?nk0time) Markov chain. 1k Equivalently, a continuous-time Markov chain can be Then is the epoch at which the nth event occurs. For Snrepresented by so-called in?nitesimal transition rates. This is

    each t ? 0, de?ne the random variable N(t) by N(t) = the in analogy with the’ -representation’ of the Poisson t

    largest integer n ? 0 for which ? t. The random variable Sprocess. The representation by in?nitesimal transition rates n

    leads naturally to the ?ow rate equation approach. A N(t) represents the number of events up to time t.To continuous-time stochastic process {X (t), t ? 0} with discrete characterize the distribution of the counting variable N(t) we state space I is said to be a continuous-time Markov chain if: use the well-known fact that the sum of k independent

    random variables with a common exponential distribution has pXtiXtiXt{()|(),...,(),,nnn001 an Erlang distribution. That is, ,,,PXtiXti{()|()}j1knnnn??11()tt , t0 :,?pSte{}1?For all and 0...:???tttiiiI,...,,?01nn01nnkj!0jJust as in the discrete-time case, the Markov property The Erlang (k, λ) distribution has the probability density expresses that the conditional distribution of a future state kkt??1 tek/(1)!given the present state and past states depends only on the

    The memoryless property of the Poisson process is present state and is independent of the past. In the following

    formatted as the following: For any t ? 0, the random variable we consider time-homogeneous Markov chains for which the

     has the same exponential distribution with mean 1/λ. That (transition probability P{X (t + u) = j | X (u) = i} is tindependent of u. We write: is,

     (t) = P{X (t + u) = j | X (u) = i}. PxijPxe{}1(:,? , x0 tAs an introduction to the modelling by a continuous-time Independently of t [31]. An example of this model is the Markov chain, let us construct the following Markov jump following: the model is a discrete-time, discrete-space model process. A stochastic system with a discrete state space i jump consisting of Q sensor nodes evenly laid out in a region from state to state according to the following rules: represented by a square grid. Each sensor node in the network Rule (a) If the system jumps to state i, it then stays in state i operates with a sleep/awake cycle. A sink node located at the for an exponentially distributed time with mean 1/νi center of the network sends out request packets, the sink node independently of how the system reached state i and how long can either be a continuously operating node or a regular it took to get there. Rule (b) If the system leaves state i, it sensor node which works with the sleep/awake mechanism. jumps to state j (j ? i) with probability Pij independently of The probability of each individual sensor node being awake is the duration of the stay in state i, where: determined independently by a Poisson model with mean λ P1iI?P = 1 for all ?ijijequal to the average number of sensor nodes awake in the ij~

    neighborhood, Na. An expression of λ can be written as Throughout this model the following assumption is made, in λ = Na = N × Pa, where N is the number of sensor nodes in a any ?nite time interval the number of jumps is ?nite with neighborhood and Pa is the probability for a node to be awake probability 1. De?ne now the continuous-time stochastic

     7

    at any time [30]. - Another unanswered question is how can we achieve

    the balance between energy saving and end-to-end

    delay during transmission. This is another field of 3.4 THE EXPONENTIAL DISTRIBUTION MODEL

    research where thousands of hundreds of sensors might be deployed in a given environment. Therefore, The exponential distribution is the continuous multi hop network will be formed. The question in approximation of the geometric distribution. It is used to such case, can scheduling be efficient to save sensors model the time between successive events, or the time energy and can it work with end to end transmission required to service an event. The exponential distribution has requirement. the property of have no memory, i.e., knowing the time that - During transmission, some nodes work as routers; the last event occured is in no way helpful in predicting when however, nodes on the packet forwarding path should the next event may occur. The Exponential Distribution is be awakened in advance. Therefore, there is a need for also named as the failure rate function, as it can be used to routing algorithm that consider the sleeping nodes model the failure rate in components [32]. The general and somehow wakeup the sleeping nodes along the formula for the probability density function of the exponential path. This is not easy due to the requirement of distribution is establishing a new path every time a node needs to 1??(x , , send. One may think that we can establish the path x0fxe,,())/once and let the nodes awake during the whole period

    of transmission. However, this might not be efficient where is the location parameter and is the scale in case if we need to balance the energy consumption

    in the network. parameter (the scale parameter is often referred to as which

    - Sensor networks could be classified into query based equals (). The case where = 0 and = 1 is called the 1/and reporting based network. The problem appears standard exponential distribution. The equation for the when a query based network is used. The sink(s) may standard exponential distribution is [33]: require to query specific node which usually occurs by

    flooding the query through the network. There is a x, for x0fxe()need to efficient interaction model between the

    scheduling scheme and query execution to guarantee An example of this model we will present the following

    the query answer. network model: The packets are generated in response to a

    - Another problem that faces any scheduling scheme is sensed phenomenon. Each node generates packets at rate λ the scheduling with multi-sink networks. How to packets/sec. We assume that time elapsed between the two manage the sleep and awake nodes with random successive packet generations at a node is exponentially request from each sink node is an open problem. distributed, although the analysis may be extended to - It is important to design a sensor network that can arbitrary packet generation processes. If the sensing operation support a wide range of applications and such a is prohibited in sleep state, no packet is generated during the network would have only one or a few generic sleep state. We use the following sleep model for the analysis. scheduling mechanisms that can be tailored to Each sensor node is either in active or sleep state. The time different applications. spent by a node in the active state is exponentially distributed - Currently, finding sleeping policies that optimize 1tradeoff between energy consumption, performance with mean (). While the time spent by a node in the sleep

    and tracking error is another open problem. s

    - The problem of finding more realistic sensing model 1state is exponentially distributed with mean (). The state and more realistic object movement models in case of Aa scheduling scheme is present is another challenge of a node is independent of the states of any other node in the the faces the sensor networks. In other words, finding network. The evolution of the states of a node may be a scheduling scheme that supports mobility is a hard represented as a Markov chain. In active state the nodes problem. perform sensing, receiving and transmission operations [34]. - Object localization using cooperation among all

    awake sensors at each time step might consume the 4. THE OPEN PROBLEMS IN SWSN sensors energy. An efficient method, there is a need

    for an elegant method to do so. In this section we present the open problems in the scheduling

     mechanisms that face stochastic wireless sensor network:

    5. CONCLUSION - Up to our knowledge, there is no accurate analysis to

    the case where sensors have heterogeneous wakeup In this paper, we explain the main concepts of the new form probabilities. This is important since sensor networks of the sensor network, which called Stochastic Wireless Sensor could be used in many of the critical application. Network and we survey the ON\OFF scheduling techniques

     8

    and discussion their advantages and disadvantages, ON \ OFF [16] F. Ye, G. Zhong, J. Cheng, S. Lu, and L Zhang, "PEAS:

    A robust energy conserving protocol for long-lived sensor scheduling MODELS, then we present the more critical open

    networks", 23rd International Conference on Distributed problem in ON\OFF scheduling.

    Computing Systems, 2003. Proceedings, 2003.

    [17] S. Kumar, T. H. Lai, AND J. Balogh, "On k-coverage in REFERENCES a mostly sleeping sensor network", the 10th annual [1] C. Cordeiro, D. Agrawal," AD HOC & SENSOR international conference on Mobile computing and NETWORKS: Theory and Applications", book Published by networking, 2004. World Scientific, 2006. [18] C. Gui and P. Mohapatra, "Power conservation and

    quality of surveillance in target tracking sensor networks", [2] A. Willig, "Wireless sensor networks: concept, challenges the 10th annual international conference on Mobile and approaches", Elektrotechnik &Informationstechnik, 2006.

    computing and networking, 2004. [3] A Bharathidasan, V. Ponduru, "Sensor Networks: An [19] B. Chen, K. Jamieson, H. Balakrishnan, R. Morris, Overview", Technical report, University of California, Davis. "Span: An Energy-Efficient Coordination Algorithm for 2002. Topology Maintenance in Ad Hoc Wireless Net-works", [4] J. Hill, R. Szewczyk, A. Woo, S. Hollar, D. Culler, and K. ACM Wireless Networks Journal, 2001. Pister, ―System architecture directions for networked [20] Y. Xu, J. Heidemann, D. Estrin, "Adaptive Energy-sensors,‖ Architectural Support for Programming Languages Conserving Routing For Multihop Ad Hoc Networks", and Operating Systems Journal ,2000. Research Report, USC/Information Sciences Institute, 2000. [5] S. Tilak, N. B. Abu-Ghazaleh, and W. Heinzelman, [21] W. Ye, J. Heidemann and D. Estrin, "An energy-efficient ―Infrastructure tradeo;s for sensor networks‖, 1st ACM MAC protocol for wireless sensor networks", 21st Conference international workshop on Wireless sensor networks and of the IEEE Computer and Communications Societies applications, 2002. (INFOCOM), 2002. [6] J. Wang, "Power Efficient Stochastic Wireless Networks", [22] T. Dam and K. Langendoen, ―An Adaptive Energy-PhD thesis, 2005. ecient MAC Protocol for Wireless Sensor Networks,‖, the [7] C. Hua, T. Yum "Asynchronous Random Sleeping for 1st international conference on Embedded networked sensor Sensor Networks", ACM Transactions on Sensor Networks systems, 2003. (TOSN), 2007. [23] H. Cunqing, P. Y. TAK-SHING," Asynchronous [8] D. Tian , N. Georganas, "A coverage-preserving node Random Sleeping for Sensor Networks", ACM Transactions scheduling scheme for large wireless sensor networks", 1st on Sensor Networks (TOSN), 2007. ACM international workshop on Wireless sensor networks [24] A. Cerpa, and D. ESTRIN, "ASCENT: Adaptive Self-and applications, 2002. configuring sEnsor Networks Topologies", IEEE [9] H. Zhang, J. Hou, "Maintaining sensing coverage and Transactions on Mobile Computing, 2004. connectivity in large sensor networks", International Journal [25] A. Spyropoulos, C. S. Raghavendra, V. K. Prasanna, "A of Ad Hoc and Sensor Wireless Networks, 2005. Distributed Algorithm for Waking-up in Heterogeneous [10] Q. Cao, T. Abdelzaher, T. He, AND J. Stankonic, Sensor Networks", Information Processing in Sensor "Towards optimal sleep scheduling in sensor networks for Networks (IPSN),2003. rare-event detection", the 4th international symposium on [26] W. Qin, J. Haas, " BASS: an Adaptive Sleeping Scheme Information processing in sensor networks, 2005. for Wireless Sensor Network with Bursty Arrival", [11] X.-Y. Li, P.-J. Wan, AND O. Frieder, "Coverage in international conference on Wireless communications and wireless ad hoc sensor networks", IEEE Transactions on mobile computing, 2006.. Computers, 2003. [27] G. Lu, N. Sadagopan, B. Krishnamachari, and A. Goel, [12] T. HE, S. Krishnamurthy, J Stankovic., T. Abdelzaher, ―Delay Ecient Sleep Scheduling in Wireless Sensor L. Luo, R. Stoleru, T. Yan, L. Gu, J. Hui AND B. Krogh, Networks,‖, Conference of the IEEE Computer and ―Energy-ef?cient surveillance system using wireless sensor

    Communications Societies, 2005. networks", the 2nd international conference on Mobile

    [28] N. Dusit, H. Ekram," Sleep and Wakeup Strategies in systems, applications, and services, 2004.

    Solar-Powered Wireless Sensor/Mesh Networks: Performance [13]. T. Moscibroda, R. Wattenhofer "Maximizing the

    Analysis and Optimization", IEEE Transactions on Mobile lifetime of dominating sets", Parallel and Distributed Computing, 2007. Processing Symposium, 19th IEEE International, 2005.

    [29] C. Henk, ―A First Course in Stochastic Models", ISBN [14] J. Deng, Y. S. Han, W. B. Heinzelman and P. K.

    0-471-49880-7 (acid-free paper)ISBN 0-471-49881-5 (pbk. Varshney, "Scheduling sleeping nodes in high density cluster-: acid-free paper),2003. based sensor networks", Mobile Networks and Applications [30] K. W. Pak, "A Communication Protocol for Stochastic Journal, 2005.

    Sensor Networks", Master Thesis, 2004. [15] J. Deng, Y. S. Han, W. B. Heinzelman and P. K.

    [31] G. Qi, ―Stochastic Modeling and Optimization of Varshney, "Balanced-energy sleep scheduling scheme for Resource Constrained Sensor Networks", PhD thesis, 2007. high density cluster-based sensor networks", IEEE Workshop

    on Applications and Services in Wireless Networks, 2005.

     9 [32] M. Attenborough," Mathematics for electrical engineering and computing", ISBN 07506855 X, book, 2003. [33]

    http://www.itl.nist.gov/div898/handbook/eda/section3/eda3667.htm.

    [34] N. Bisnik, "Stochastic and Information Theoretic Models for Design and Performance Evaluation of Mobile AD HOC and Sensor Networks", PhD thesis, 2007.

Report this document

For any questions or suggestions please email
cust-service@docsford.com