A coverage-preserving node scheduling scheme for large wireless sensor networks

A Coverage-Preserving Node Scheduling Scheme for

Large Wireless Sensor Networks

Di Tian

Multimedia Communications Research Laboratory

University of Ottawa 800 King Edward Avenue 1-613-5625800x2146

Nicolas D. Georganas

Multimedia Communications Research Laboratory

University of Ottawa 800 king Edward Avenue 1-613-5625800x6225

dtian@site.uottawa.ca

ABSTRACT

In wireless sensor networks that consist of a large number of low-power, short-lived, unreliable sensors, one of the main design challenges is to obtain long system lifetime, as well as maintain sufficient sensing coverage and reliability. In this paper, we propose a node-scheduling scheme, which can reduce system overall energy consumption, therefore increasing system lifetime, by turning off some redundant nodes. Our coverage-based off-duty eligibility rule and backoff-based node-scheduling scheme guarantees that the original sensing coverage is maintained after turning off redundant nodes. We implement our proposed scheme in NS-2 as an extension of the LEACH protocol. We compare the energy consumption of LEACH with and without the extension and analyze the effectiveness of our scheme in terms of energy saving. Simulation results show that our scheme can preserve the system coverage to the maximum extent. In addition, after the node-scheduling scheme turns off some nodes, certain redundancy is still guaranteed, which we believe can provide enough sensing reliability in many applications.

georganas@discover.uottawa.cal

Keywords

Coverage, Node Scheduling, Wireless Sensor Networks.

1. INTRODUCTION

Recently, the idea of wireless sensor networks has attracted a great deal of research attention due to wide-ranged potential applications that will be enabled by wireless sensor networks, such as battlefield surveillance, machine failure diagnosis, biological detection, home security, smart spaces, inventory tracking, etc. [1-4]. A wireless sensor network consists of tiny sensing devices, deployed in a region of interest. Each device has processing and wireless communication capabilities, which enable it to gather information from the environment and to generate and deliver report messages to the remote base station (remote user). The base station aggregates and analyzes the report messages received and decides whether there is an unusual or concerned event occurrence in the deployed area. Considering the limited capabilities and vulnerable nature of an individual sensor, a wireless sensor network has a large number of sensors deployed in high density (high up to 20nodes/m3 [5]) and thus redundancy can be exploited to increase data accuracy and system reliability. In wireless sensor networks, energy source provided for sensors is usually battery power, which has not yet reached the stage for sensors to operate for a long time without recharging. Moreover, sensors are often intended to be deployed in remote or hostile environment, such as a battlefield or desert; it is undesirable or impossible to recharge or replace the battery power of all the sensors. However, long system lifetime is expected by many monitoring applications. The system lifetime, which is measured by the time until all nodes have been drained out of their battery power or the network no longer provides an acceptable event detection ratio, directly affects network usefulness. Therefore, energy efficient design for extending system lifetime without sacrificing system reliability is one important challenge to the design of a large wireless sensor network.

Categories and Subject Descriptors

F.2.2 [Nonnumerical Algorithms and Problems]: Geometrical problems and computations – Routing and layout, network problems.

General Terms

Algorithms, Measurement, Performance, Reliability, Experimentation, Theory.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee.

Conference ’00, Month 1-2, 2000, City, State.

This work was supported in part by the iSENSE Project, Communications and Information Technology Ontario (CITO), a Center of Excellence.

In wireless sensor networks, all nodes share common sensing tasks. This implies that not all sensors are required to perform the sensing task during the whole system lifetime. Turning off some nodes does not affect the overall system function as long as there are enough working nodes to assure it. Therefore, if we can schedule sensors to work alternatively, the system lifetime can be prolonged correspondingly; i.e. the system lifetime is prolonged by exploiting redundancy. In this work, we present a novel node-scheduling scheme, which is used to configure node work status and schedule the sensor on-duty time in large sensor networks. Our design has been driven by the following requirements: first, because it is inconvenient or impossible to manually configure sensors after they have been deployed in hostile or remote working environments, self-configuration is mandated. Second, the design has to be fully distributed and localized, because a centralized algorithm needs global synchronization overhead and is not scalable to large-populated networks. Third, the algorithm should allow as many nodes as possible to be turned off in most of the time. At the same time, it should preserve the initial sensing coverage with minimum “sensing hole”, or “blind points”. It is ideal if the working nodes can cover the same monitored area as the original one. Fourth, the scheduling scheme should be able to maintain the system reliability, i.e., certain redundancy is still needed.

In the proposed approach, each node in the network autonomously and periodically makes decisions on whether to turn on or turn off itself only using local neighbor information. To preserve sensing coverage, a node decides to turn it off when it discovers that its neighbors (sponsors) can help it to monitor its whole working area. To avoid blind point, which may appear when two neighboring nodes expect each other’s sponsoring, a backoff-based scheme is introduced to let each node delay its decision with a random period of time. In this work, we implement the proposed scheme as an extension of the existing data gathering protocol, LEACH [10]. We compare the energy consumption with and without the extension and analyze the effectiveness of our algorithm in terms of energy saving. Our simulation results show that the system lifetime in the extended LEACH can be prolonged in the energy model inherited from LEACH, without reducing the overall sensing coverage, as well as maintaining certain system reliability.

The rest of this paper is organized as follows: section 2 reviews the related work in the literature. In section 3, we introduce the details of the proposed scheme. Section 4 discusses implementation details and presents the simulation results. Section 5 concludes the paper.

2. RELATED WORK

Minimizing energy consumption and maximizing the system lifetime has been a major design goal for wireless sensor networks. In the last few years, researchers are actively exploring advanced power conservation approaches for wireless sensor networks. On

the one hand, device manufacturers have been striving for low power consumption in their products. In [6-7], low power transceiver architectures and low power signal processing systems are discussed separately. In [8], an energy-scavenging technique, which enables self-powered nodes using energy extracted from the environment, is presented. In [9], a low power data converter, signal processing, RF communication circuits are integrated into one chip. On the other hand, protocol designers are seeking an energy efficient communication architecture, which involves all levels from the physical layer to the application layer [4]. For instance, directed diffusion [11] and LEACH [10] are two typical data communication protocols proposed for wireless sensor networks. In directed diffusion, routes (called gradients) that link sources of interesting data to sinks are formed when interest is disseminated throughout the network. When the source has data of interest, it sends the data along the gradient paths back to the sinks. Energy is saved by reinforcement-based adaptation to the empirically best path, caching and in-network data aggregation. LEACH is a clustering-based protocol that utilizes a randomized rotation of a local cluster-head to evenly distribute the energy load among sensors in the network. It also uses localized coordination to enable scalability and robustness for dynamic networks and incorporates data fusion into the routing protocols to achieve energy conservation. Our work is dedicated to scheduling nodes by using application knowledge (i.e., it belongs to one branch of application layer protocols according to the categories in [4]) and does not address the data communication problem. It can be implemented as the extension of any energy efficient data communication protocol in wireless sensor networks.

In [12], a probing-based density control algorithm is proposed to ensure long-lived, robust sensing coverage by leveraging unconstrained network scale. In this protocol, only a subset of nodes are maintained in working mode to ensure desired sensing coverage, and other redundant nodes are allowed to fall asleep most of the time. Working nodes continue working until they run out of their energy or are destroyed. A sleeping node wakes up occasionally to probe its local neighborhood and starts working only if there is no working node within its probing range. Geometry knowledge is used to derive the relationship between probing range and redundancy. In this algorithm, desired redundancy can be obtained by choosing the corresponding probing range. However, this derivation is based on the assumption that all the nodes have exactly the same sensing range. It is hard to find a relationship between probing range and desired redundancy, if nodes have different sensing ranges. Furthermore, the probing-based off-duty eligibility rule can not ensure the original sensing coverage and blind points may appear after turning off some nodes, which is verified in our experiment.

In [13], Chen et al. proposed an algorithm to turn off nodes based on the necessity for neighbor connectivity. They intend to reduce the system energy consumption without significantly diminishing the connectivity of the network. In [14], Xu et al. proposed a scheme in which energy is conserved by letting nodes turn off

their communication unit when they are not involved into sending, forwarding or receiving data phase. Also, node density is leveraged to increase the time that communication unit is powered off. In [15], an algorithm, called Geographical Adaptive Fidelity (GAF) was proposed, which uses geographic location information to divide the area into fixed square grids. Within each grid, it keeps only one node staying awake to forward packets. These three node-scheduling schemes turn off nodes from communication perspective without considering the system’s sensing coverage. In fact, in wireless sensor networks, the main role of each node is sensing. Unusual event could happen at any time at any place. Therefore, if we only turn off nodes, which are not participating in

data forwarding, certain areas in the deploying area may become “blind points”. Important events may not be detected [12]. Besides diminishing the number of active nodes, there are other network topology control techniques, which also intend to increase power efficiency and extend network lifetime. [16-18] produces a minimum-energy communication subnetwork by adjusting transmission power. The subnetwork is computed distributedly at each node using local neighbor location information [16-17] or directional information [18]. Instead of controlling the transmission power level, node-scheduling schemes power off some redundant nodes in the network and therefore can achieve further energy conservation.

i

(e)

(a)

S

(j)IS(i)

(b)

Sj→iandθj→i

(c)

φj→

i

(d)

Sj→iUSk→i

j∈N(i)

USj→i S(i)

Figure 1: Sponsored Coverage Calculation-Basic Model

3. NODE SELF-SCHEDULING ALGORITHM

Generally, the node-scheduling problem is composed of two sub-problems. First, what is the rule that each node should follow to determine whether it should turn itself off or not? Second, when should nodes make such decision? In this section, we will describe our node-scheduling scheme in these two aspects, respectively.

the neighbors whose distance from the current node is equal to or less than the sensing range r as shown in definition 1.

Definition 1: Neighbor. The neighbor set of node i is defined as

N(i)={n∈ |d(i,j)≤r,n≠i} where is node set in the deployment region, d(i,j) denotes the distance between node i and node j.

Thus, for node i, the off-duty eligibility rule can be expressed as US(j) S(i)j∈N(i)

, i.e., the union of its neighbors’ sensing areas is a

superset of node i’s sensing area. The expression is equivalent to . By observation, we know that the

crescent-shaped intersection S(j)IS(i) in Figure 1(a) includes a

j∈N(i)

3.1 Coverage-based Off-duty Eligibility Rule

3.1.1 Sponsored Coverage Calculation – basic model

As discussed above, the main objective of this algorithm is to minimize the number of working nodes, as well as maintain the original sensing coverage. To achieve this goal, we calculate each node’s sensing area and then compare it with its neighbors’. If the whole sensing area of a node is fully embraced by the union set of its neighbors’, i.e. neighboring nodes can cover the current node’s sensing area, this node can be turned off without reducing the system overall sensing coverage.

In this section, we will describe how a node determines that its neighbors can cover its sensing area given their location information. To simplify the problem, we assume that all nodes have the same sensing range and each node knows its sensing range r. In the later discussion, we will show how to modify this simplified model if nodes have different sensing ranges. A node’s sensing area is a circle centered at this node with radius r, if all nodes lie on a 2-dimensional plane. The scheme we will describe is also applicable to a 3-dimensional space. We denote node i’s sensing area as S(i). To facilitate the calculation, we only consider

U(S(j)IS(i)) S(i)

sector as illustrated in Figure 1(b). Although the area of the sector is smaller than that of the crescent, it is much easier to calculate the area of the sector rather than that of the crescent, because the area of a sector can be represented by its central angle accurately and uniting two sectors is equivalent to merging two central angles. Therefore, although node j can cover a crescent-shaped region within node i’s sensing area (Figure 1(a) shadow region), node i will only “admit” that node j can help it monitor a sector-shaped region (Figure 1(b) shadow region) if node i is turned off. To help the further description, we define this sector as a sponsored sector.

Definition 2: Sponsored sector. Suppose nodes i and j are neighbors, and both sensing areas S(i) and S(j) touch at point P1 and P2. As illustrated in Figure 1(b), the sector, bounded by radius NiP1, radius NiP2 and inner arc P1P2, is defined as the sponsored sector by node j to node i, and is denoted as Sj→i. The central

angle of the sector is denoted as θj→i. The direction of node j referred to node i is denoted as φj→i.

Lemma 1: If USj→i S(i), then U(S(i)IS(j)) S(i).

j∈N(i)

j∈N(i)

Proof:Q(S(i)IS(j)) Sj→i

∴U(S(i)IS(j))

j∈N(i) USj∈N(i)

j >i

∴j∈UN(i)

(S(i)IS(j)) S(i).

Lemma 1 ensures that investigating whether the neighbors can cover the current node’s sensing area is equivalent to checking whether the union of sponsored sectors (called sponsored coverage) contains the current node’s sensing area, which in turn, is equivalent to calculating whether the union of central angles can cover the whole 360o as illustrated in Figure 1(e).

If the conditionUN(i)

Sj→i S(i) is satisfied, we call the

j∈neighboring nodes are off-duty sponsors of node i.

From geometry calculation, the central angle is given as

θ arccos d(i,j) . Since 0<d(i,j)≤r, it is easy to

j→i=2 2 r

know that the range of the central angle is 120o≤θoj→i<180. Obviously, a node must have at least three neighbors to get a

chance to be turned off.

3.1.2 Sponsored Coverage Calculation – extension model

In the initial discussion, we assume that each node has the same sensing range r, and each node knows its geographical location. In this part, we will extend the basic model and provide solution for the cases that nodes can obtain neighboring nodes’ directional information from incoming signals or nodes have different sensing ranges.

A. Exploiting direction information

In this case, we still assume that every node has the same sensing range. As illustrated in the Figure 1(b-d), in order to merge two central angles, we need to calculate the magnitude and the direction of each central angle (i.e. θj→iand

φj→i

) first. It is easy to get

that θ

d(i,j) and j→i

=2 arccos

2 r φ y yi .

j >i=arctg j

xj

xi

Obviously, node location information is needed for calculating the actual values of

θj→i

and

φj→i

. However, we have known that the

range of θ

j→i is [120o

,180o

). If we take the lower bound, 120°,

as the safe value, it is not necessary to calculate the actual value for

θj→i

. Now, the problem is how to know

φj→i

. Techniques to

estimate direction, i.e. φj→i

from incoming signals have already been discussed in the IEEE antennas and propagation community as the Angle-Of Arrival (AOA) problem. This can be

accomplished by using more than one directional antenna, as mentioned in [11]. If the radio communication unit in a sensor node has such directional information estimation capability, the above model can still be used by simply taking θ

j→i as 120°, even without knowing node location information. In [12], Ye et al. believe that availability of directional information from directional antennas is not currently practical in wireless sensor networks. We don’t intend to discuss the availability problem here and just present this extended model, as one possible solution.

B. Different sensing range

In this case, nodes have different sensing ranges, which may be caused by two reasons. First, nodes have different initial sensing ranges. Second, a node’s sensing range is changed during its lifetime. For instance, the power level may have an impact on the sensing range. Node i’s and its neighbor node j’s current sensing range are denoted as ri and rj respectively. There are many different cases how the nodes and their neighbors are located. For instance, Figure 2 presents four of them. In order to still be able using central angles to calculate sponsored coverage, here, we only

consider two cases as shown in Figure 3 (a-b).

(a)S(j)

S(i)

(b)S(j) S(i)

(c)

(S(j)IS(i)) Sj >i

(d)Sj >i

(S(j)IS(i))

Figure 2: layout of neighboring nodes-Extended Model (2)

(a)S(j)

S(i)

(b)S(j)IS(i) Sj >i

Figure 3: two considered cases-Extended Model (2) Case 1: node j’s sensing area completely contains node i’s sensing area, which happens whenever ri+d(i,j)≤rj holds. In this case, node i can be turned off without further calculation. Case 2: The sensing areas of both nodes touch at two points, and the intersection area includes a sector centralized at node i. This case happens whenever both d(i,j)≤rjand ri rj≤d(i,j) are true. In this case, the central angle is

θ

(

d(i,j)2+r22

=2 θ=2 arccos

i rjj→i

) 2 r

i d(i,j)

In summary, when nodes have different sensing ranges, a node’s neighbor set definition is modified as

N(i)={n∈ |(d(i,j)≤rj∧ri rj≤d(i,j)() ∨ri+d(i,j)≤rj),n≠i}

Obviously, the basic model described previously is a special case of this extension when ri=rj=r.

3.2 Node Scheduling Scheme Based On Eligibility Rule

In our scheduling scheme, the operation is divided into rounds. Each round begins with a self-scheduling phase, followed by a sensing phase. In the self-scheduling phase, nodes investigate the off-duty eligibility rule described in the previous section. Eligible nodes turn off their communication unit and sensing unit to save energy. Non-eligible nodes perform sensing tasks during the sensing phase. To minimize the energy consumed in the self-scheduling phase, the sensing phase should be long compared to the self-scheduling phase. How on-duty nodes collect data and communicate is the issue of the data gathering protocols and is out of the scope of this paper.

The self-scheduling phase consists of two steps. First, each node advertises its position and listens to advertisement messages from other nodes to obtain neighboring nodes’ position information. Second, each node calculates a neighbor sponsoring sensing area, compares it with its own and decides whether it is eligible for off-duty or not. The details of these two steps are introduced as follows.

3.2.1 Neighbor Information Obtaining Step

To obtain neighbor node information, a simple approach is that each node broadcasts a Position Advertisement Message (PAM), which contains node ID and its current location, at the beginning of each round. Because only neighbors within a node’s sensing range are considered in the eligibility rule, in order to minimize energy consumption, each node transmits PAM with the minimum power as long as it reaches its sensing range. Such transmission power control scheme ensures that only nodes within the transmitter’s sensing range can receive its PAM. If nodes have different sensing ranges, PAM should also include the current sensing range of the transmitter as well.

3.2.2 Back-off Based Self-scheduling Step

After finishing the collection of neighbor information, each node evaluates its eligibility for turning off by calculating the sponsored coverage, as described in the previous section. However, if all nodes make decisions simultaneously, blind points may appear, as shown in Figure 4. Node 1 finds its sensing area can be covered by node 2,3 and 4. According to the off-duty eligibility rule, node 1 turns itself off. While at the same time, node 4 also find its sensing area can be covered by node 1,5 and 6. Believing node 1 will keep working, node 4 turns itself off too. Thus, a blind point occurs after turning off both node 1 and node 4, as in Figure 4(d).

(a) original sensing(b) node 1 turns itselfarea covered byoff by the on-duty

node1-6

eligibility rule

(c) node 4 turns itselfoff by the on-duty(d) blind point appears

eligibility rule

Figure 4: Blind Point Occurrence

To avoid such a problem, we introduce a back-off scheme. We let each node start its determination after a random back-off time period Td and broadcast a Status Advertisement Message (SAM) to announce its status, if it is eligible for turning off. Neighboring nodes receiving a SAM will delete the sender’s information from their neighbor lists. Thus, the nodes that have a longer backoff delay will not consider the nodes that have decided to be turned off before.

Assuming W is the size of random back-off time choice, the probability of node 1 and node 4 selecting the same random number is 1/W. Although a large W can reduce the probability to a sufficient small value, there is still a chance that node 1 and node 4 could select the same random number. To avoid a blind point further, we let each node wait for a short period time Tw after sending the SAM out, if it is eligible for turning off, instead of turning off its communication unit immediately. This ready-to-off period should be enough for node 1 to receive SAM from node 4, or vice verse.

If one SAM is received during the ready-to-off period and the transmitter is one of its off-duty sponsors, the node will re-investigate its off-duty eligibility. If the eligibility doesn’t hold any more, the node returns it status from ready-to-off to on-duty. Otherwise, the node turns itself off after Tw. The nodes, which have decided to serve as on-duty ones, don’t re-evaluate their off-duty eligibility once the decision has been made. The status transition graph is shown in Figure 5.

coming

Figure 5: FSM for self-scheduling phase

4. PERFORMANCE EVALUATION AND SIMULATION

In this section, we present some experimental and simulation results as the performance evaluation of our algorithm.

4.1 Performance Evaluation of the eligibility rule

First, we evaluate the performance of coverage-based off-duty eligibility rule by experimental results.

4.1.1 Comparison with probing-based off-duty eligibility rule

In [12], another rule is proposed to determine if a node can turn itself off or not. The basic idea is: if the node detects that there is a working node within its probing range, it will turn itself off. The probing range is a configurable parameter corresponding to redundancy desired by the user. This probing-based off-duty eligibility rule is simple, and does not need node geographical location. However, it cannot preserve the original sensing coverage. Furthermore, it relies on the assumption that every node has the exactly same sensing range to keep the relationship between probing range and desired redundancy.

To compare it with our coverage-based off-duty eligibility rule, we carry out some experiments in static networks. We deploy 100 nodes in a square space (50m by 50m). Nodes’ x- and y-coordinates are set randomly. Each node has a sensing range of 10 meters and knows who are its neighbors and where the neighbors

are located. We let each node decide whether to turn it off or not in a random sequence. The decision of each node is visible to all the other nodes. The nodes, which make decisions later, cannot “see” the nodes that have been turned off before. After all nodes have make decisions, the number of off duty nodes is counted and the current sensing coverage by on-duty nodes is compared with the original one where all nodes are active. To calculate sensing coverage, we divide the space into 1m×1m unit cells. We assume an event occurs in each cell, with the event source located at the center of the cell. We investigate how many original nodes and how many on-duty nodes can detect every event. If an event cannot be detected by any on-duty node, but is within the range of the original sensing coverage, we call the event source cell a “blind point”. The occurrence of blind points means that the corresponding off-duty eligibility rule cannot preserve the original sensing coverage. We also compute the average sensing degree before and after turning off nodes. Table 1 shows the experimental results when we apply the coverage-based and probing-based [12] off-duty eligibility rules in 100 random topologies, respectively. As we can see, by applying our coverage-based off-duty eligibility rule, 53 nodes can be turned off on the average. The sensing degree is reduced from 10 to 4. No blind point appears in any topology after turning off some nodes. The probing-based off-duty eligibility rule makes almost the same number of nodes be turned off as ours when the probing range is set as 4 meters. However, blind points appear in 26 topologies in that case. Another observation is that larger probing range results in more nodes being turned off and more sensing coverage being reduced when the probing-based off-duty eligibility rule is used.

Table 1: Comparison of two off-duty eligibility rules

Eligibility Rules Proposed

Probing range N/A 3 4

[12]

5 6 7

Number of off-duty nodes

53 38 54 66 71 81

Original sensing degree 10 10 10 10 10 10

Obtained Sensing Degree

4 6 4 2 2 1

Number of topologies with blind points

0 13 26 68 91 100

Average number of blind points per

topology

N/A <1 2 8 35 102

4.1.2 On-duty node number vs. node density

We change node density by varying the sensing range from 6 to 13 and the deployed node number from 100 to 300 in the same 50m×50m deployed area. Figure 6 shows a 3D surface plot of the off-duty node number in different sensing range and deployed node number. From it, we can see that increasing the number of the original deployed nodes and increasing the sensing range will result in more nodes being turned off, which is consistent with our expectation.

Figure 6: off-duty node number vs. node density However, on-duty node number doesn’t remain constant over different deployed node number when the sensing range and the deployed area are fixed. Instead, it increases as the deployed node number increases as illustrated in Figure 7. This is due to the increasing of edge nodes (located at the boundary of the deployed area). According to our off-duty eligibility rule, edge nodes have no chance to be turned off because all the other nodes are located on one side of the edge nodes. Intuitively, increasing edge nodes will increase the on-duty node number, however, experimental result shows that our coverage based off-duty eligibility rule still effectively limits the on-duty node number. When the deployed node number is increased from 100 to 300, the number of on-duty node only increases about 30%.

4.1.3 Sensing Coverage vs. node density

We also investigate the change of obtained sensing degree over node density. As shown in Figure 8, although the range of the initial sensing degree is varied from 3 to 48, the obtained sensing degree is almost stable at 3 or 4 after turning off some nodes. Therefore, the coverage-based off-duty eligibility rule also effectively controls the network redundancy.

Figure 7: on-duty node number vs. deployed node number Figure 9-11 presents the same effectiveness but from the different view: the percentage of the deployed area that can be monitored by at least D on-duty nodes. We still divide the space into 1m×1m unit cells as mentioned in section 4.1.1. An event occurs in each cell, with the event source located at the center of the cell. We investigate the ratio of the cell number reached by at least D on-duty nodes to the total number of cells when sensing range is 8, 10 or 12 meters, respectively. As illustrated in the figures, most of the area, above 88%, can be covered by at least 3 on-duty nodes. Almost 100% cells can be reached by at least one on-duty node. And about 97% cells can be monitored by at least 2 on-duty nodes.

Furthermore, our experiments show that increasing the deployed node number and the sensing range leads to more coverage (D=1), because less sensing holes exist in the original network. In addition, the two curves (D=1, original D=1) are exactly the same in all the figures, which implies that the coverage-based off-duty eligibility rule completely preserves the original sensing coverage without any blind points.

In fact, the results presented in this section are relatively ideal compared to the real time simulation, because all deployed nodes are scheduled in the sequence, which means there are no cases when two nodes make off-duty decisions at exactly the same time. Second, the decision is visible to all the other nodes. However, in the real simulation, decision is announced by sending messages, which may be lost in the way. Third, each node has already known complete neighbor information. By using effective MAC protocol (collision avoidance), satisfying effect, which is very close to ideal one, can be achieved as shown in Figure 13.

Figure 8: sensing degree reduction vs. node density

Figure 10: coverage vs. deployed node number(r=8)

4.2 Simulation Results

In this section, we describe the implementation of our proposed node-scheduling scheme as an extension of LEACH [10]. Our main purpose is to analyze the energy efficiency of our proposed scheme by comparing the energy consumption with and without the extension.

4.2.1 Simulation Environment

We implement the proposed scheme as an extension of an existing data gathering protocol, LEACH [10]. Although the proposed scheme can be combined with any other data gathering protocols, we select LEACH because its NS-2 simulation code is available in the Internet [20] and it is one of the earliest and most famous communication protocols suitable for wireless sensor networks. Furthermore, it has a similar timeline as our proposed scheme. LEACH (Low-Energy Adaptive Clustering Hierarchy) is a clustering-based communication protocol proposed by the MIT LEACH project. In LEACH, nodes are organized into local clusters, with one node acting as the local base station or cluster-head. All the other nodes must transmit their data to the cluster heads, while the cluster-head nodes must receive data from all the cluster members, perform signal processing functions on the data (e.g., data aggregation), and then transmit data to the remote base station. Being a cluster head is much more energy-intensive than being a non-cluster-head node. In order to evenly distribute the

Figure 9: coverage vs. deployed node number(r=10)

Figure 11: coverage vs. deployed node number(r=12) energy load associated with a cluster-head and avoid draining the battery of any one sensor, cluster-head position is rotated randomly among all the nodes. The medium access protocol in LEACH is also chosen to reduce energy dissipation in non-cluster-head nodes. Since a cluster head node knows all the cluster members, it can act as a local control center and create a TDMA schedule that allocates timeslots for each cluster member. This allows the nodes to remain in the sleep state as long as possible. In addition, using a TDMA schedule for data transfer prevents intra-cluster collisions.

In LEACH, the operation is also divided into rounds, which are composed of a cluster set-up phase in which the clusters are formed, and a steady-state phase in which sensors collect data from the environment and transfer data to the cluster-heads and then to the base station.

To extend LEACH with our node-scheduling scheme, a straightforward way is to insert the self-scheduling phase of our scheme before the LEACH cluster set-up phase. At the beginning of each round, all the nodes self-determine whether to turn themselves off or not and off-duty nodes will not participate in the cluster forming and steady-state phase followed. The advantage of such timeline is that our node-scheduling scheme is embedded into the LEACH seamlessly without any modification

of its original workflow. The timeline of the implementation is illustrated in Figure 12.

Figure 12. Timeline of LEACH with extension

An issue of concern before our simulation is the impact of collisions to our algorithm, because collisions would cause data transmission failure, therefore, lost of neighboring information, and reduction of the off-duty node number. The LEACH protocol uses a new MAC protocol type, MacSensor, which is a combination of Carrier-Sense Multiple Access (CSMA), Time-Division Multiple Access (TDMA), and a simple model of Direct Sequence Spread Spectrum (DS-SS). DS-SS and TDMA schema are used after clusters have been formed, while in the cluster set-up phase, a non-persistent CSMA scheme is used, where nodes sense carrier first before transmission. If the carrier is currently busy, the node sets a random back-off time to try again. Since our node-scheduling scheme is inserted before the cluster set-up

phase, the CSMA scheme is inherited and used. Although this scheme cannot completely eliminate collisions, it does suppress collisions effectively in our simulation. As illustrated in Figure 13, where the average on-duty node numbers in 100-second real-time simulation of 5 random topologies are almost the same as the ideal values obtained in section 4.1.2. Therefore, in this work we do not address how contention affects our algorithm. This subject is expected to be one of our future works. Figure 13 also implies the correctness of our implementation.

Figure 13: On-duty node number in real-time simulation

4.2.2 Energy Consumption

This section evaluates the ability of our node-scheduling scheme to save energy, therefore, increase system lifetime by comparing the energy consumption per node in the original and extended LEACH. In terms of energy conservation, we cannot only evaluate the energy saving in the data-gathering phase, because node-scheduling itself also consumes energy in transmission of PAM and SAM messages as well as computation, which should not be ignored. If the cost of the node-scheduling phase dominates the

overall energy consumption in each round, it is better not to turn off nodes. In the original LEACH protocol, energy is mainly consumed in two parts: data transmission for clustering forming (Ec) and data gathering (Eg). While in the extended LEACH, extra energy is needed in node scheduling phase, which is denoted as Et’. Assuming the number of data gatherings in each round is Ng, then the energy dissipation of each round in the original LEACH is E = Ec + Ng × Eg, while the energy dissipation per round in the extend LEACH is E’ = Et’+ Ec’ + Ng × Eg’. As long as E’ < E, energy savings can be achieved by node-scheduling. In fact, the energy coefficients in E and E’ are affected by many factors: the size of sensing range, the length of report message, the number of data gatherings in each round, and the power consumption model, etc. Therefore the potential for energy saving is the combination effect of multiple factors.

In our simulation, we use the same energy parameters and radio model as discussed in [21], which indicates that the transmission energy consumption is

E(k,d)= 2

Eelec×k+εfriss

amp×k×d:d<dcrossover and the reception Tx E4

elec×k+εtwo

ray amp×k×d:d≥dcrossoverenergy consumption is ERx=Eelec×k, where Eelec is the energy consumed for the radio electronics, εfriss amp and εtwo ray amp for a power amplifier. Radio parameters are set asEelec = 50nJ/bit,

ε2

friss amp= 10pJ/bit/m,

εtwo ray amp= 0.0013pJ/bit/m4, dcrossover =

87m. We only consider the data aggregation, while ignore other processing energy consumption. The energy for performing data aggregation is 5nJ/bit/signal. Once a node is turned off, the energy it consumes is negligible. The simulation is carried out in a network with 100 nodes, each with a sensing range of 10 meters. Nodes are placed randomly in a rectangular region whose area is 50m×50m. The remote base station (or sink node) is located at the low left corner, i.e. origin point (0,0). The initial energy of all nodes is 2J. Each sensor sends a 2000-bit report message to the base station with a 0.5s time interval. The time duration of each round is 10 seconds.

Figure 14 illustrates the energy dissipation curve per node in the original LEACH and the extended LEACH in random network topology when Ng =20. The energy dissipation in the extended LEACH is slower than the original one.

Figures 15 and 16 show an increase of the system lifetime in the same simulation setting. Here we use two metrics to evaluate the system lifetime: the total number of nodes alive over time and the system sensing coverage over time (the ratio of the area monitored by on-duty nodes to the deployed region). As illustrated in Figure 15 and 16, although the extended LEACH does not outperform the original one in term of first node dead time, the number of nodes alive and the system sensing coverage drop more quickly in the original LEACH than in the extended one. In the result, it takes approximately 4378 seconds for the last node to die in the extended LEACH, while 1412 seconds in the original LEACH.

And it takes approximately 2055 seconds for the sensing coverage to drop 20% (reach 80%) in the extended LEACH, while 1285

Figure 14: Energy dissipation curve per node when =100,

=50m×50m, r=10m,Ng

=20

Figure 15: Sensing coverage over time when

=100,

=50m×50m, r=10m,Ng

=20

Figure 16: Number of nodes alive over time when =100,

=50m×50m, r=10m,Ng=20

seconds in the original one.

Figure 17: system lifetime vs. Ng when

=100,

=50m×50m, r=10m

Figure 18: system lifetime vs. node density when

=100,

=50m×50m, r=10m,Ng=20

Furthermore, we also change the number of data gatherings in each round from 4 to 20 with the increment of 4, and compare the time when system coverage drops below 80% in the original and extended LEACH. Figure 17 shows that the system lifetime with extended LEACH is always longer than, and is about 1.7 times of the original one.

Figure 18 plots the system lifetime as a function of node density. It can be seen that the system lifetime increases as the node density increases in extended LEACH. In contrast, the system time decreases as the node density increases in original LEACH.

5. CONCLUSIONS

In this paper, we proposed a coverage-preserving node-scheduling scheme, which can reduce energy consumption, therefore increase system lifetime, by turning off some redundant nodes. We presented a basic model for coverage-based off-duty eligibility rule

and then extend it to several different scenarios. This kind of off-duty eligibility rule guarantees that the original sensing coverage can be maintained to the extent possible. To further preserve sensing coverage in a real time environment, we introduce a back-off scheme in which nodes delay by a random time period, before investigating the eligibility rule, and wait for a short time, if they decide to turn off. Doing so prevents nodes sponsoring each other, therefore avoids blind points. Experimental results show that enough redundancy still remained although some nodes were turned off. We implemented this scheme as an extension to the LEACH protocol, which is an existing data communication protocol for wireless sensor networks. We compared the energy consumption in the original LEACH and the extended LEACH and analyzed the effectiveness of our scheme in terms of energy saving. Preliminary simulation results in the radio model and energy parameters proposed by the LEACH designer show the potential of such energy saving and system lifetime increase.

6. REFERENCES

[1]

D. Estrin, R. Govindan, J. Heidemann and S. Kumar, Next Century Challenges: Scalable Coordination in Sensor Networks, Proc. of ACM MobiCom’99, Washington, August 1999.

[2]

J. Kahn, R. Katz, and K. Pister, Next Century Challenges: Mobile Networking for Smart Dust, Proc. of ACM MobiCom’99, August 1999.

[3]

A. Cerpa, J. Elson, D. Estrin, L. Girod, M. Hamilton and J.Zhao, Habitat Monitoring: Application Driver for Wireless Communications Technology, 2001 ACM SIGCOMM Workshop on Data Communications In Latin America and the Caribbean, Costa Rica, April 2001 [4]

I.F.Akyildiz, W. Su, Y.Sankarasubramaniam, E.Cayirci, Wireless Sensor Networks: A Survey, Computer Networks, March 2002

[5]

E. Shih, S. Cho, N. Ickes, R. Min, A. Sinha, A. Wang, A.Chandrakasan, Physical Layer Driven Protocol and Algorithm Design for Energy-Efficient Wireless Sensor Networks, ACM SIGMOBILE Conference on Mobile Computing and Networking, July 2001, ROME, Italy [6]

A. Porret, T. Melly, C. C. Enz, and E. A.Vittoz, A Low-Power Low-Voltage Transceiver Architecture Suitable for Wireless Distributed Sensors Network, IEEE International Symposium on Ciruits and Systems’00, Geneva, 2000. [7]

M. J. Dong, K. Geoffrey Yung, and W. J. Kaiser, Low Power Signal Processing Architectures for Network Microsensors, 1997 International Symposium on Low Power Electronics and Design, Digest of Technical Papers (1997).

[8]

J.M. Rabaey, M. J. Ammer, J. L. da Silva ,D.P.S.Roundy, PicoRadio Supports Ad Hoc Ultra-Low Power Wireless Networking, IEEE Computer Magazine, July 2000.

[9]

G. Asada, M. Dong, T. S. Lin, F. Newberg, G. Pottie, W. J. Kaiser, Wireless Integrated Network Sensors: Low Powers Systems on a Chip, Proc of the 24th IEEE European Solid-State Circuits Conference, Elsevier, 1998. [10]

W.R.Heizelman, A.Chandrakasan, and H.Balakrishnan, Energy-Efficient Communication Protocol for Wireless Micro Sensor Networks, IEEE Proceedings of the Hawaii International Conference on System Sciences, January 2000.

[11]

C. Intanagonwiwat, R. Govindan and D. Estrin, Directed Diffusion: A scalable and Robust Communication Paradigm for Sensor Networks, ACM MOBICOM’00, 2000.

[12]

F. Ye, G. Zhong, S. Lu, L. Zhang, Energy Efficient Robust Sensing Coverage in Large Sensor Networks, Technical Report.

[13]

B. Chen, K. Jamieson, H. Balakrishnana, R. Morris, Span: An Energy-Efficient Coordination Algorithm for Topology Maintenance in Ad Hoc Wireless Networks, MOBICOM’01, 2001.

[14]

Y. Xu, J. Heidemann, D. Estrin, Adaptive Energy-Conserving Routing for Multihop Ad hoc Networks, Technical Report 527, USC/ISI, Oct.2000.

[15]

Y. Xu, J. Heidemann, D. Estrin, Geography-informed Energy Conservation for Ad Hoc Routing, MOBICOM’01, 2001.

[16]

C.Intagagonwiwat, R.Govindan, and D.Estrin, Directed Diffusion: A Salable and Robust Communication Paradigm for Sensor Networks, Proc. of the AMC Mobicom’00, Boston, MA, 2000.

[17]

V. Rodoplu and T.H.Meng, Minimum Energy Mobile Wireless Networks, IEEE JSAC, Vol. 17, No.8, August 1999.

[18]

L. Li, and J.Y.Halpern, Minimum-Energy Mobile Wireless Networks Revisited, IEEE International Conference on Communications ICC’01, Helsinki, Finland, June 2001. [19]

R. Wattenhofer, L.Li, P.Bahl, Y.-M.Wang, Distrbuted Topology Control for Power Efficient Operation in Multihop Wireless Ad Hoc Networks, Proc. of the Third Workshop on Mobile Multimedia Communications (MoMuC-3), Princeton, NJ, 1996.

[20]

W.Heinzelman, A.Chandrakasan, and H.Balakrishnan, uAMPS ns Code Extensions, http://www-mtl.mit.edu/research/icsystems/ uamps/leach.

[21]

W.Heinzelman, Application-Specific Protocol Architectures for Wireless Networks, PhD thesis, June 2000, MIT.

本文来源：https://www.bwwdw.com/article/rroe.html