DOC

Raie Ramadan-38.doc

By Pedro Hall,2014-11-07 07:51
12 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