Critique paper on wireless network research paper
For P eer R
eview
IEEE TRANSACTIONS ON WIRELESS COMMUNICATIONS, VOL. XX, NO. Y, MONTH 2013 1
OPS: Opportunistic Pipeline Scheduling in Long-strip Wireless Sensor Networks with
Unreliable Links Peng Guo, Kui Zhang and Nirvana Meratnia
Abstract —Being deployed in narrow but quite long area, strip wireless sensor network (SWSNs) have drawn much attention in applications such as coal mines, pipeline and structure monitoring. One of unique characteristics of SWSNs is the large hop counts, which leads to long end-to-end delivery delay in low-duty-cycle SWSNs. To reduce the delay, pipeline scheduling is a promising technique, which assigns sensor nodes sequential active time slots along the data forwarding path. However, pipeline scheduling is prone to failure when communication links are unreliable. In this paper, we propose an opportunistic pipeline scheduling algorithm (OPS) for SWSNs, based on the observation that sensor nodes in SWSNs can overhear data transmissions passing by them. OPS exploits nodes outside the data forwarding path to opportunistically provide links when transmission failure happens, and hence maintains the pipeline forwarding instead of retransmission in the next duty cycle. Theoretical calculation shows that the expectation delay of OPS is always smaller than that of existing methods when the link quality is < 100%. Both extensive simulations and experiments are conducted. The results verify that the end-to-end delivery delay of OPS is usually less than 30% of that of existing methods, while the energy cost is almost the same.
Index Terms —Strip wireless sensor networks (SWSNs), End-to-end delivery delay, Scheduling, Opportunistic transmission.
✦
1 INTRODUCTION
Wireless Sensor Networks (WSNs) can be leveraged to support a broad range of applications from habitat mon- itoring to structure health monitoring and protection, helping to reduce the deployment cost and provide real- time data collection. In some applications, the physical area monitored by a WSN is in a shape of a narrow yet quite long strip. An example application is gas monitoring in coal mines where tunnels are only several meters wide but tens of kilometers long [1], [2]. Other applications include monitoring rivers and pipelines, which have the same shape and geographical extent as coal mine tunnels. We call this kind of WSNs as strip WSNs (SWSNs). Being deployed along the long monitoring area as shown in Fig. 1, SWSNs usually have over tens of hop counts.
In order to ensure long-term operation, sensor nodes in SWSNs usually operate at a very low-duty-cycle (e.g., 1% or less), implying that the sensor nodes sleep most of the time and stay active for only a short duration in each duty cycle. Under such circumstance, when a sender node needs to deliver a packet, it always has to wait for a certain period of time until its destination node becomes active, thus resulting in sleep latency. The sleep latency in SWSNs with large hop counts usually leads to a very
Peng Guo (e-mail: guopeng@mail.hust.edu.cn) is with the Department of Electronics and Information Engineering, Huazhong University of Science and Technology, Wuhan, 430074, China. Kui Zhang (e-mail: truelykyle@gmail.com) is with Department of Computer Science, University of Twente, Netherlands. Nirvana Meratnia (e-mail: N.Meratnia@utwente.nl) is with Department of Computer Science, University of Twente, Netherlands.
Sink
Fig. 1: A typical Strip WSN with unreliable links.
long end-to-end delivery delay. For example, a typical sleep latency of 0.5s within each hop can lead to the end- to-end delay of over tens of seconds in SWSNs, which cannot be tolerant in many delay-sensitive applications, such as coal mine monitoring.
To reduce the delivery delay, lots of delay-efficient scheduling schemes [3]–[5] have been proposed. Howev- er, generally speaking, the average end-to-end delivery delay with these schemes is approximately proportional to the product of the hop counts and duty cycle length, which is still too large in large scale of SWSNs. In order to essentially shorten the delivery delay due to sleep latency, reducing the gap between adjacent nodes’ wakeup time is a key issue. If a receiver node wakes up immediately when the sender node has just obtained a packet, the sender node can send the packet directly to the receiver without any latency. This idea has previous- ly been described in [6]–[8], with being given different names such as staggered wake-up [6], streamlined wake-up [7], and ladder wake-up [8]. In this paper, we use the name of pipeline scheduling adopted in [9].
Though pipeline scheduling can achieve minimum de- livery delay in low-duty-cycle WSNs, its performance becomes poor when being applied in unreliable com- munication environments. An example about this is
Page 26 of 36IEEE Transactions on Wireless Communications
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60
For P eer R
eview
IEEE TRANSACTIONS ON WIRELESS COMMUNICATIONS, VOL. XX, NO. Y, MONTH 2013 2
Forward di
Duty cycle T
Forward di+1
fail retransmit di+1 Node A
Node B
NodeC
Time slot τ
Receive data & send ACK Send data & receive
D
D
D D
D D
D D
D
D
D D
D
D D
D
D
Active time
2τ T+2τ
D
Fig. 2: Traditional pipeline scheduling on unreliable links.
illustrated in Fig. 2. Node A, B and C work in the duty-cycle way and wake up one after another. Node A needs to delivery packets to C via B. When there is no transmission failure, the delivery delay is minimum 2τ, where τ is the size of time slot. However, if A fails to transmit the packet to B in the duty cycle, it has to retransmit the packet in the next duty cycle, resulting in the delay of T + 2τ.
To enhance the pipeline scheduling in unreliable com- munication environments, recently [9] proposed the multi-pipeline scheduling algorithm, which employs multi- ple parent nodes in each layer on the data delivery path to establish multiple pipeline schedules. When trans- mission failure happens, the sender node has multiple chances to retransmit the packet in the current duty cycle instead of the next duty cycle, thus reducing the delivery delay due to sleep latency. However, the performance of the multi-pipeline scheduling algorithm much depends on the number of parent nodes in each layer.
In this paper, we propose an opportunistic pipeline scheduling (OPS) algorithm for low-duty-cycle SWSNs with unreliable links. OPS provides more retransmission chances for sensor nodes than the multi-pipeline schedul- ing algorithm in [9], while does not require more active time or transmissions of sensor nodes in view of a given amount of packets to be transmitted. Moreover, OPS does not strictly require multiple parent nodes in each layer as the multi-pipeline scheduling requires.
The design of OPS is based on the following two motivations. First, we observe that sensor nodes in SWSNs can overhear data transmissions passing by them due to the feature of the narrow SWSNs area. For instance, when a sender node transmits a packet to the receiver node, another node near the receiver may hear the transmission. With checking whether there is an acknowledgement sent back from the receiver, the overhearing node can get to know the transmission result, and will substitute the receiver to forward the packet if the transmission fails. Thus, the time wasted for waiting the sender to retransmit the packet in the next duty cycle can be saved. It’s easy to implement the overhearing, as we can just schedule the overhearing node with the same active time as the receiver and set the node to receive all packets no matter if it is the destination or not.
Another motivation depends on such a fact. When enlarging the gap between adjacent nodes’ wakeup time in Fig. 2, the sender node A will have multiple chances to retransmit the packet to the receiver B in the current duty cycle before the destination node C wakes up, thus avoiding retransmissions in the next duty cycle. Based on this fact, if node B receives the packet early in the gap before node C wakes up, B can consider to send the packet to another node closer to C. Then, the node can help to deliver the packet to C with higher success probability when C wakes up.
Based on the ideas introduced above, we design the proposed OPS scheduling and give the theoretical per- formance calculation as well as the optimization. Con- tributions of the paper include:
• Based on the unique feature of packet transmissions in SWSNs, we propose a novel opportunistic pipeline scheduling OPS to reduce the data delivery delay in low-duty-cycle SWSNs with unreliable links.
• We implement OPS on a SWSN with 20 TelosB nodes, and demonstrate its high efficiency in terms of low end-to-end data delivery delay in practical environment.
The remainder of the paper is organized as follows. In Section 2, we briefly review the related works. Section 3 describes the models in detail. Section 6 gives the design overview of the proposed scheme, then the details of the scheme is presented in Section 5. Simulations and experiments are described in Section 6 and Section 7, respectively, followed by the conclusions in Section 8.
2 RELATED WORKS Duty-cycle is a usual way for sensor nodes to save energy [11]. In [12], the authors conducted some com- parisons on the data delivery delay of the classic synchronous scheduling schemes and asynchronous scheduling schemes, showing that, in average, at least half of the duty cycle time is needed to transmit a packet among adjacent nodes.
In [3], authors proposed an asynchronous wake-up schedule to reduce the end-to-end latency, in which each sensor node has several choices to send packet to its neighbors that wake up at different time in a duty cycle. Hence, the average delay among each hop can be reduced to a fraction of the duty cycle. However, the total delay still increases proportionally to the product of hop counts and duty cycle length. In [4], a delay-efficient MAC scheme is proposed, in which sensor nodes wake up at the appropriate time according to the demand of their sender nodes. However, the demand can be delivered only in the short duration of nodes’ active time in each duty cycle. Hence, the hops of transmission demanded in each duty cycle are limited.
In [6]–[8], [13], the authors discussed the wake-up schedule according to an established directional data traffic path. All nodes wake up when their sender n- odes have just gotten the data packets, and go to sleep
Page 27 of 36 IEEE Transactions on Wireless Communications
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60
For P eer R
eview
IEEE TRANSACTIONS ON WIRELESS COMMUNICATIONS, VOL. XX, NO. Y, MONTH 2013 3
as soon as they transmit the packets to their receiver nodes. Hence, the data packets can be delivered step by step without any waiting and the delivery delay can be essentially eliminated. We name this kind of scheduling method as pipeline scheduling in this paper. Though the pipeline scheduling has good performance on delay, it is not efficient under unreliable communication environments. Sensor nodes taking the pipeline scheduling usually have to retransmit packets after a whole of duty cycle when failure happens.
Recently, using opportunistic routing for data delivery in duty-cycle WSNs has received attention [5], [14], [15]. By combining scheduling and routing for the da- ta delivery, these works can reduce the data delivery delay. However, as these works are usually based on asynchronous wake-up, the average data transmission delay between each hop is still a fraction of the duty cycle, and the total delivery delay in SWSNs with large hop counts is still very long.
The newest related work is the multi-pipeline scheduling proposed in [9], which utilizes multiple parent nodes on the delivery path to set multiple pipeline schedules for the data delivery. However, in the multi-pipeline scheduling, each failure during the data forwarding will induce one decrement of pipelines until a retransmission in next duty cycle. In this paper, we’ll make extensive comparisons between the multi-pipeline scheduling and the proposed OPS.
3 MODEL AND A SSUMPTIONS Before introducing the proposed OPS scheduling, we describe the traffic model and duty-cycle model for SWSNs. After that, assumptions made in our design will be described.
3.1 Models
Suppose M sensor nodes are randomly deployed in a strip area where the width is far smaller than nodes’ transmission range. Sensor nodes are connected with each other and form a connected network, i.e., a SWS- N. To enhance the robustness of the network, usually multiple routes exist in SWSNs for data collection so as to avoid the disconnection of networks due to the unavailability of some node, as shown in Fig. 1.
We consider the traffic pattern of data collection in the SWSN, which is the major traffic pattern utilized in the applications such as event detection, periodic sampling and etc. We suppose the traffic in the SWSN is low, and each event detection result or sampling data can be recorded with just several bytes. Our goal is to minimized the average end-to-end packet delivery delay in the SWSN.
We suppose sensor nodes work in a low-duty-cycle mode with periodically alternating active state and dor- mant state. Nodes in active state can transmit packets or sense, and receive packets from neighbors. Sensor nodes change their states according to their wakeup schedules.
Gap of wakeup time Slot (data+ACK+guard)
{7, 2}
{7, 4}
{7, 6}
Fig. 3: The duty-cycle model.
Each schedule is periodic with the same period T , i.e., the duty cycle. The active time of each sensor node is fixed in the schedule. We assume that each node maintains a local schedule table recording the times when its neighbors are in active state.
The duty cycle T can be divided into a number of time units τ, i.e.,T = L ∗ τ. Usually, L ≫ 1. τ is approximate to a round-trip transmission time (includ- ing data transmission, ACK and a guard interval). For example, to transmit a packet with the size of 125 bytes and obtain the ACK by using the radio chip CC2420, τ can be less than 5ms. Each sensor node selects one or several consecutive time units as its wakeup time slot. The size of the time slot depends on traffic load carried on the sensor node. In view of delivery latency, we are mainly concerned with the wakup time in a sensor node’s schedule. Therefore, we use {T, ti} to represent the schedule of node ni, where ti denotes the wakeup time unit of ni. An example for the duty-cycle model is shown in Fig. 3.
3.2 Assumptions
We make following assumptions in our design:
• Links are unreliable and a transmission may not be successful depending on the link quality.
• Each sensor node knows its wake-up schedule and the schedules of its neighbors. This can be im- plemented by allowing the sensor nodes exchange information locally during the network initialization phase.
• Each node knows the link quality between itself and its neighbors. This can be implemented by applying existing mechanisms such as the four-bit link estimation [16] and STLE [17].
• Sensor nodes are locally synchronized so that they know when to send packets to their neighbors ac- cording to their wake-up schedules. Local synchro- nization can be achieved by using a time stamping technique, as described in FTSP [18], which achieves an accuracy of 2.24µs with the cost of exchanging a few bytes of packets among neighboring nodes every 15 minutes. Since τ is typically several ms for the radio chip Chipcon CC2420, the accuracy of 2.24µs is sufficient.
Page 28 of 36IEEE Transactions on Wireless Communications
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60
For P eer R
eview
IEEE TRANSACTIONS ON WIRELESS COMMUNICATIONS, VOL. XX, NO. Y, MONTH 2013 4
A B
C
D E S
{T, i} {T, i+2}
{T, i+4}
A B
C
D E S
(c) Multi-pipeline scheme (d) The proposed OPS scheme
{T, i} {T, i+1}
{T, i+3}
{T, i+2}
{T, i+4}
A B
C
D E S
A B
C
D E S
{T, i+2} {T, i+4}
{T, i} {T, i+1}
{T, i+2}
{T, i+3}
{T, i+4}
(a) Network topology (b) Traditional pipeline scheme
Fig. 4: A typical example for three scheduling schemes.
4 DESIGN OVERVIEW
In this section, we use a typical example to illustrate the main idea of the proposed OPS scheduling scheme. For contradistinction, we also illustrate related scheduling schemes with this example.
Fig. 4 shows a simple SWSN. In traditional pipeline scheduling algorithm [6]–[8], [13], usually a data collec- tion tree is given and nodes on each path in the tree wake up one by one with a gap of one time slot, as shown in Fig. 4 (b) where there are two forwarding paths A → B → C → S and D → E → F → S. The schedules of nodes are pipelined as {T, 1} → {T, 2} → {T, 3} and {T, 4} → {T, 5} → {T, 6}, respectively. These schedules can achieve minimum data collection delay when no transmission failure happens. However, if node A fails to send the packet to B at {T, 2}, it has to wait for T time to retransmit the packet.
In the multi-pipeline scheduling algorithm, packet can be switched between the two parallel pipelines on the forwarding paths as shown in Fig. 4 (c), thus mitigating the influence of broken pipeline. For instance, when node A fails to transmit packet to node B at {T, 2}, node A can transmit the packet to D immediately at {T, 3}, and the packet will be forwarded along the pipeline D → E → S.
In our proposed OPS scheme, since nodes in SWSNs are deployed in a strip area, we consider one main forwarding path in the SWSN for the data collection, as shown in Fig. 4 (d) where node A, B, C and S form the main forwarding path. Nodes outside the path, e.g., node D and E, send their packets just to nearby nodes on the path. Intuitively, data collection in this way should be energy-efficient, as the traffic in SWSNs is supposed to be low and sensor nodes on the main path can aggregate their local data.
To schedule nodes on the main forwarding path, we employ an expanded pipeline scheduling scheme with en- larging the gap between adjacent nodes’ wakeup time in traditional pipeline scheduling. For instance, in Fig. 4 (d), nodes A, B and C are scheduled at {T, i}, {T, i + 2} and {T, i + 5}, respectively. They wake up one after another, which is similar to the traditional pipeline scheduling,
while the gaps between their wakeup time are larger than those in traditional pipeline scheduling. For some nodes outside the path, e.g., node D and E, they are scheduled at the same time slots as their nearby nodes on the path, so as to provide opportunistic links to enhance the pipeline forwarding on the path. There might be some other nodes deployed in SWSN in practice. We schedule them at other time slots for local data gathering without collisions. The scheduling detail is ignored in this paper, as it is less related to the end-to-end data delivery delay.
We use four typical cases of packet delivery in OPS to introduce the basic idea of OPS. The cases are shown in Fig. 5. We explain these cases as follows.
• Case 1: In the first duty cycle, node A transmits packet di to node B at {T, i + 2}. Suppose B suc- cessfully receives the packet. Then, node B goes to sleep immediately and wakes up again at {T, i + 4} to transmit di to node C who just wakes up.
• Case 2: In the second duty cycle, node A transmits packet di+1 to node B still at {T, i+2}. However, this transmission fails. Then, node B will keep listening and node A can retransmit di+1 to B at {T, i + 3}. Suppose node B successfully receives di+1 at {T, i+ 3}. Then, B can forward di+1 to node C at {T, i+4}.
• Case 3: In the third duty cycle, node A fails to transmit packet di+2 to node B at {T, i+2}. Also, A fails to retransmit the packet at {T, i + 3}. However, another node E, which is close to node B and is scheduled to overhear node B, successfully receives di+2 at {T, i+3}. Hence, node E substitutes node B to forward di+2 to node C at {T, i + 4}. (Technical details about the substitution are explained later.)
• Case 4: In the fourth duty cycle, node A successfully transmits packet di+3 to node B at {T, i + 2}. Since node C has not waked up now, instead of going to sleep at {T, i + 3}, node B sends the packet to node F which is located between node B and C. Node F then will help to send di+3 to node C at {T, i + 4} with higher success probability.
From case 1 and 2, due to the expanded pipeline scheduling, nodes A succeeds to transmit packet di+1 without retransmission in the next duty cycle, though there is transmission failure. To more clearly show the improvement, we suppose that the link quality between node A and B is 0.7, the length of duty cycle T is 1s and the size of time slots equals to τ = 5ms. Since node A has two chances to transmit the packet to B in the duty cycle before node C wakes up. Hence, the probability of successful packet delivery between A and B in one duty cycle can increase to be 1 − (1 − 0.7)2 = 0.91. This increment is achieved at a cost of only a small extra delay τ = 5ms in the ideal case. However, the probability of retransmission in next duty cycle can be remarkably decreased.
From case 3 and 4, nodes E and F , which are outside the main forwarding path, can opportunistically provide
Page 29 of 36 IEEE Transactions on Wireless Communications
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60
For P eer R
eview
IEEE TRANSACTIONS ON WIRELESS COMMUNICATIONS, VOL. XX, NO. Y, MONTH 2013 5
Forward di
Node A
Node B
Node C
(1) No failure
Forward di+1
Node D
Forward di+2 Forward di+3
Node E
(2) Fail twice but still succeed
in current duty cycle
(3) Totally fail but another
node helps to forward
(4) Succeed early and
send to a relay node
{T, i+2}
{T, i+4} {T, i+4}
{T, i+2}
Fig. 5: Design of the proposed OPS scheduling.
additional links for the pipelined forwarding on the path, thus effectively enhancing the pipeline scheduling in the unreliable communication environments. Partic- ularly, to more clearly show the improvement of case 3, we suppose that the link quality between node A and D is 0.6. Then, the probability of successful packet delivery between A and B or E in one duty cycle is 1 − (1 − 0.7)2(1 − 0.6)2 = 0.986. Note that, this improve- ment does not require further extra delay in the ideal case.
Compared with the multi-pipeline scheduling scheme, the proposed OPS has the same delay ({T, i+4}−{T, i}) on ideal link. However, i) the sender nodes in OPS have multiple retransmission chances in a duty cycle, while the retransmission chances in multi-pipeline scheduling depends on the number of receivers for the sender; ii) attributing to overhearing, every another receiver for a sender node in OPS will double the reception chances in a duty cycle, as illustrated in case 3; iii) some other kind of receiver node can even help to improve the link quality, as illustrated in case 4. Furthermore, in view of a given amount of packets to be delivered, OPS does not consume more energy than existing approaches, which will be analyzed in next section.
5 THE PROPOSED OPS SCHEDULING In this section, we present the proposed OPS scheduling in details. First, we give the definition of the forwarding path and the nodes providing opportunistic links in OPS. Then, we introduce scheduling algorithms for sensor nodes in SWSN, and the energy consumption analysis. Finally, the optimization of OPS, including the optimal forwarding path selection and the optimal time slot assignment, is conducted.
5.1 Definitions
We define the forwarding path as a connected route on which sensor nodes can cover the whole SWSN. Suppose Γ is the set of nodes on a forwarding path. pi,i+1 denotes the link quality for link ni → ni+1, and
ni-1 ni ni+1 ni+2
ni-1 f
ni-1 r ni
r ni+1
r
ni f
ni+1 f
ni+2 f
Fig. 6: Opportunistic transmission links.
C(ni, ni+1, ni+2) denotes the route quality for the route ni → ni+1 → ni+2, which equals to pi,i+1 ∗ pi+1,i+2. We define opportunistic forwarding nodes and opportunistic relaying nodes, which provide two kinds of opportunistic links for the forwarding path, as follows.
Definition 1: Consider a segment of the forwarding path ni → ni+1 → ni+2, node nfi+1 is an opportunis- tic forwarding node for node ni+1, which satisfies: (1) n f i+1 /∈ Γ; (2) n
f i+1 = argmax{C(ni, x, ni+2) : x ∈
N(ni) ⋂ N(ni+1)
⋂ N(ni+2)}, where N(ni) represents the
set of neighboring nodes of ni. Definition 2: Consider a segment of the forwarding path
ni → ni+1 → ni+2, node nri+1 is an opportunistic relaying node for node ni+1, which satisfies: (1) n
r i+1 /∈ Γ; (2) nri+1 =
argmax{C(ni+1, x, ni+2) : x ∈ N(ni+1) ⋂ N(ni+2)}.
Fig. 6 illustrates all possible data forwarding links in SWSN. Note that, not all sensor nodes on the forward- ing path have their opportunistic forwarding nodes and opportunistic relaying nodes. The existence of these nodes depends on the deployment of the SWSN. From Fig. 6, a sensor node on the forwarding path may get a packet from its sender node on the path or its sender node’s opportunistic forwarding node or opportunistic relaying node, depending on the random results of wireless transmis- sions. In addition, the sensor node on the path may forward the packet to its receiver node on the path or its receiver’s opportunistic forwarding node or the opportunistic relaying node of itself.
5.2 Scheduling of nodes with OPS
For convenience, we call the destination node of a sender as the sender’s parent node, and the destination node of
Page 30 of 36IEEE Transactions on Wireless Communications
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60
For P eer R
eview
IEEE TRANSACTIONS ON WIRELESS COMMUNICATIONS, VOL. XX, NO. Y, MONTH 2013 6
parent node as the sender’s grandparent node. After the initialization of OPS, each node on the forwarding path, e.g., ni, will have its active time slot ({T, i}), its parent node ni+1’s active slot ({T, j}) and its grandparent node ni+2’s active slot ({T, k}). The node nfi and nri , if there are, will also have {T, i}, {T, j} and {T, k}.
Algorithm 1 describes the scheduling of a node ni on the forwarding path. The node ni on the path will periodically wake up at its active time slot to receive the coming packet, and transmit packet (if it has) to ni+1 at ni+1’s active slot. Particularly, in ni’s reception duration (i.e., ni’s active slots), if ni does not detect packet trans- mission, it sends a short N-ACK to opportunistic relaying node nri (if there is) to notice the latter to go to sleep, and it also then goes to sleep. If ni detects there is packet transmission in its active time but fails to receive the packet, it will not return ACK, and will keep listening to the channel for packet retransmission till ni+1 is going to be active. If ni successfully receives a packet in its active time but ni+1 has not been active, then ni will send the packet to nri (if there is). In ni’s transmission duration (i.e., ni+1’s active slots), if ni has already successfully send the packet to nri in current cycle, ni will not transmit the packet any more. Otherwise, ni will keep transmitting the packet in its transmission duration until it receives an ACK from ni+1.
Algorithm 1 Scheduling for node ni on forwarding path
1: STATE=FREE 2: while time ∈ [{T, i}, {T, j}) do 3: Listen to the channel 4: if Detect a packet then 5: if Receive the packet then 6: Send back ACK 7: STATE=BUSY 8: if time={T, j − 1} then 9: if ∃nri then
10: Send the packet to nri 11: STATE=FREE 12: end if 13: Go to sleep and BREAK 14: end if 15: end if 16: Go on listening to the channel 17: else 18: Send N-ACK to nri 19: Go on sleep and BREAK 20: end if 21: time++ 22: end while 23: while time ∈ [{T, j}, {T, k}) do 24: if STATE=BUSY then 25: Send packet to ni+1 26: if Receive ACK then 27: STATE=FREE 28: end if 29: end if 30: time++ 31: end while
Algorithm 2 describes scheduling of opportunistic for- warding node n
f i of node ni. When n
f i is assigned with
Algorithm 2 Scheduling for node n f i
1: STATE=FREE 2: while time ∈ [{T, i}, {T, j} − ǫ) do 3: Listen to the channel 4: if Detect a packet then 5: if Receive the packet then 6: STATE=BUSY 7: end if 8: if Receive ACK then 9: STATE=FREE
10: Go to sleep and BREAK 11: end if 12: else 13: Go on sleep and BREAK 14: end if 15: time++ 16: end while 17: while time ∈ [{T, j} − ǫ, {T, k}) do 18: if STATE=BUSY then 19: Send ACK to ni 20: Send packet to ni+1 21: if Receive ACK then 22: STATE=FREE 23: end if 24: end if 25: time++ 26: end while
Algorithm 3 Scheduling for node nri
1: STATE=FREE 2: while time ∈ [{T, i}, {T, j}) do 3: Listen to the channel 4: if Receive N-ACK from ni then 5: Go to sleep and BREAK 6: end if 7: if Receive a packet from ni then 8: STATE=BUSY 9: Send ACK to ni
10: Go to sleep and BREAK 11: end if 12: time++ 13: end while 14: while time ∈ [{T, j}, {T, k}) do 15: if STATE=BUSY then 16: Send packet to ni+1 17: if Receive ACK then 18: STATE=FREE 19: end if 20: end if 21: time++ 22: end while
active time slots of ni and ni+1, it will periodically wake up at ni’s active time slot to overhear the air-in packet. If it receives the packet but does not receive the ACK sent by ni, it will send ACK to ni in the guard interval (indicated as ǫ in Algorithm 2) in {T, j}, and then send the packet to ni+1 at ni+1’s active slot.
Algorithm 3 describes scheduling of opportunistic relay- ing node nri of node ni. When n
r i is assigned with active
time slots of ni and ni+1, it will periodically wake up at ni’s active time slot to receive the possible packet. If it receives N-ACK from ni, which indicates there is no packet transmission in the current duty cycle, nri will
Page 31 of 36 IEEE Transactions on Wireless Communications
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60
For P eer R
eview
IEEE TRANSACTIONS ON WIRELESS COMMUNICATIONS, VOL. XX, NO. Y, MONTH 2013 7
Shortest path
0.4
0.8 0.8
ni nj
nk
Fig. 7: Example for the optimal forwarding path.
go to sleep immediately to save the idle listening time. If nri receives packet from ni, it sends back ACK to ni immediately and transmits the packet to ni+1 at ni+1’s active slot.
According to Algorithm 1, 2, when opportunistic for- warding node provides extra link to help forward the overheard packet, it does not bring collision to the link on the forwarding path. Since the opportunistic forwarding node is scheduled at the same active slots as the node on the forwarding path, the overhearing does not bring extra energy consumption of the sender. In addition, the larger gap between adjacent nodes’ wakeup slots set in OPS also will not increase the energy consumption of the receiver, because the receiver waking up at its wakeup slot will go to sleep immediately after it receives the packet or detects there is no packet transmission in the channel. Only when there is transmission failure, the sender and receiver nodes will increase their active time in that duty cycle. However, the increment of the active time is efficiently utilized for packet retransmission, and hence does not increase the energy consumption in view of a given packet transmission task.
According to Algorithm 1, 3, opportunistic relaying node also does not bring collision to the link on the forwarding path. For the energy consumption of opportunistic relay- ing node, as the the corresponding node on the forward- ing path may additionally send packet to it and asks it to relay the packet on a better link, this additional transmis- sion leads to extra energy consumption, compared with existing related works. However, this extra transmission on better link helps to reduce retransmissions, thus mitigating the extra energy consumption. In next section, we’ll compare the overall energy consumption of OPS with that of existing related works.
5.3 Optimization of the OPS scheduling
To optimize the proposed OPS scheduling, we need to select the optimal forwarding path in the SWSN and compute the optimal gaps between the wakeup times of adjacent nodes on the path. Note that, the optimal forwarding path may not be the shortest path in the SWSN. For an example illustrated in Figure 7, in which node ni and node nj are on the shortest path while node nk is outside the path in the SWSN. The link qualities between these three nodes are 80%, 80% and 40%, respectively. It is easy to obtain the optimal gap 9τ between node ni and nj’s wakeup time to achieve the minimum expectation delay of data delivery on link ni → nj (refer to Equation 2 below), which is about
n1 n2 n3 n4
n2 r n3
r
n2 f
n3 f
n4 f
Layer 1 Layer 2 Layer 3 Layer 4
p1,2
p1,2-f
p2,2-r p2-r,3
p2,3
p2,3-f
p2-f,3
Fig. 8: Data forwarding between layers.
55ms (T = 1s and τ = 5ms). However, if choosing the link ni → nk → nj as part of the forwarding path and setting the gaps between node ni, nk and nj to be 3τ, the total expectation delay of data delivery on link ni → nk → nj is only 46ms. Therefore, we need to select the optimal forwarding path according to the total expectation delay. Meanwhile, the opportunistic links should also be counted in during the selection.
Suppose that node ni is on a selected forwarding path. We call the set of node ni and n
f i as layer i. Fig. 8
shows the data delivery routes at the beginning of the forwarding path. The link quality between node n1 and n2 is denoted by p1,2 and the link quality between node n1 and n
f 2 is denoted by p1,2−f . Other link quality can
be denoted in a similar way. Assume the gap between node n1 and n2’s wakeup time is k1,2 ∗ τ, where k1,2 is an integer, and k1,2 ∗ τ ≤ T . The successful delivery probability between layer 1 and layer 2 within one duty cycle is:
P1,2 = 1 − (1 − p1,2) k1,2 ∗ (1 − p1,2−f )
k1,2 (1)
Hence, the expectation of delivery delay between layer 1 and layer 2 can be calculated as:
E[D1,2] = ∞∑
m=0
P1,2(1 − P1,2) m (mT + τ)
= (1 − P1,2) ∗ T
P1,2 + k1,2 ∗ τ
(2)
Thus, with Equation 1 and 2, it is easy to compute the optimal gap k1,2 ∗ τ to minimize E[D1,2].
We further compute the optimal k2,3 for layer 2 and layer 3. The probability that node nr2 relays the packet arriving at layer 2 is:
p r 2 =
k1,2∑
m=1
p1,2 ∗ (1 − p1,2) m−1
∗ [1 − (1 − p2,2−r) k1,2−m] (3)
Hence, the probability that node n2 forwards the packet in layer 2 is 1 − (1 − p1,2)k1,2 − pr2, and the probability that node n
f 2 forwards the packet in layer 2
is (1−p1,2)k1,2 ∗[1−(1−p1,2−f)k1,2]. Thus, the equivalent link quality for link n2 → n3, link n2 → nr2 → n3 and link n
f 2 → n3 is:
p e 2,3 =p2−r,3 ∗ p
r 2 + p2,3 ∗ [1 − (1 − p1,2)
k1,2 − p r 2]
+ p2−f,3 ∗ (1 − p1,2) k1,2 ∗ [1 − (1 − p1,2−f )
k1,2 ] (4)
Page 32 of 36IEEE Transactions on Wireless Communications
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60
For P eer R
eview
IEEE TRANSACTIONS ON WIRELESS COMMUNICATIONS, VOL. XX, NO. Y, MONTH 2013 8
0
100
200
300
400
500
600
700
0.6 0.65 0.7 0.75 0.8 0.85 0.9 0.95 1
E xp
e ct
a tio
n D
e la
y (m
s)
Link Quality
OPS Single pipeline
Multi-pipeline with m=2 Multi-pipeline with m=4 Multi-pipeline with m=6
(a)
0
20
40
60
80
100
120
140
160
180
200
0.6 0.65 0.7 0.75 0.8 0.85 0.9 0.95 1 E
xp e
ct a
tio n
D e
la y
(m s)
Link Quality
OPS Multi-pipeline with m=2 Multi-pipeline with m=4 Multi-pipeline with m=6
(b)
Fig. 9: Theoretical comparison on the expectation delay.
Combined with the link n2 → nf3 , the delivery prob- ability between layer 2 and layer 3 within a duty cycle is:
P2,3 = 1 − (1 − p e 2,3)
k2,3 ∗ (1 − p2,3−f ) k2,3 (5)
Hence, similar to above, the expectation delay E[D2,3] of data delivery between layer 2 and layer 3 can be computed. Through minimizing E[D2,3], the optimal gap k2,3 ∗ τ can be obtained.
Based on the calculation results, the optimal forward- ing path can be founded as follows. Suppose Pi is a forwarding path that covers the SWSN, and denote it as:
Pi = {l (i) 1 , l
(i) 2 , . . . , l
(i) Hi
} (6)
Where Hi is the length of Pi, and l (i) j is the j
th link. Based on the calculation method above, we can obtain the minimum expectation delay on each link in Pi.
Denote D (i) j is the minimum expectation delay for link
l (i) j
. We define Si as the total expectation delay of Pi:
Si =
Hi∑
j=1
D (i) j (7)
Therefore, the optimal forwarding path is the forward- ing path with the minimum Si.
Finding the optimal forwarding path in the SWSN can be done through a flooding in the network. We simply describe the process as follows. The sensor node s, which is furthest to the sink, makes a flooding in the SWSN. During the flooding, each node records its current Si to s and broadcasts the record. When a sensor node receives a packet, it will update its record if the new Si is smaller.
To theoretically compare the performance of OPS and the multi-pipeline scheduling as well as the traditional pipeline scheduling, we further calculate their expecta- tion delivery delay within one hop. For simpleness, we suppose the link qualities of pipeline link, multi- pipeline links and opportunistic links are all the same with the value p. Referring to Equation 2, we can get the expectation delay of traditional pipeline scheduling and multi-pipeline scheduling which is 1−p
p ∗ T + τ and
(1−p)m
1−(1−p)m ∗ T + mτ, respectively, where m is the number
of parent nodes in multi-pipeline scheduling. Suppose only one opportunistic forwarding node is exploited in OPS. Hence, based on Equation 1 and 2, we can get the
minimum expectation delay of OPS which is (1−p)2k
1−(1−p)2k ∗
T + kτ, where k = ⌊ ln(1− T τ ∗ln(1−p)−
√ (1− T
τ ∗ln(1−p))2−1)
2 ln(1−p) ⌋ is
the optimal number of time units in the gap between the wakeup time. Set T = 1s, τ = 5ms, the expectation delay of the three methods can be illustrated with Fig. 9.
From Fig. 9, the worse the link quality is, the larger the expectation delay of the traditional pipeline scheduling (denoted as single pipeline in the figure) and the multi- pipeline scheduling will be. However, the expectation de- lay of OPS usually keeps very small even when the link quality is 0.6. In addition, when increasing the number of parent nodes m in the multi-pipeline scheduling, the expectation delay will decrease as expected. While, when m = 6, the delay will become larger in the case that the link quality is more than 0.68.
6 SIMULATIONS 6.1 Simulation Setup
We use a randomly-generated strip network in an area with the width no more than 15m to evaluate the OPS method. In the simulations, the network size varies from 100 nodes to 1000 nodes. The links between those nodes are wireless path loss channels combined with shadow- ing effects as in [19], where the beginning transmission range and the end transmission range of sensor nodes are 11.3m and 32.4m.
For the data collection, we assume the size of packets initiated by nodes is small and the local data can be aggregated into one packet. Hence, we measure the data collection delay as the time elapsed from a packet being sent out by the sensor node furthest to the sink until the packet reaches the sink, i.e., the end-to-end data delivery delay. Due to the imperfection of the links, the data delivery delay exhibits some inherent randomness and can be considered a random variable. Here we propose to use the average delivery delay as a measurement of network performance. Each simulation result is based on 10 network topologies. For each topology, each node sends 100 packets to the sink with a low rate of one packet per 15s.
In addition, we measure the energy consumption by the total number of transmissions for a single packet sent by the node furthest to the sink. The receiver-side energy is consumed by packet reception and idle listening, where the former depends on the number of packet transmissions and the latter depends on the idle listening time of sensor nodes in each duty cycle. According to the analysis in Section 5.2, sensor nodes with OPS have little additional idle listening time, compared with traditional pipeline scheduling. As for the additional transmissions of opportunistic relaying nodes in OPS, the energy consump- tion can be measured with the times of transmissions. Therefore, we use only the sender-side energy as the
Page 33 of 36 IEEE Transactions on Wireless Communications
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60
For P eer R
eview
IEEE TRANSACTIONS ON WIRELESS COMMUNICATIONS, VOL. XX, NO. Y, MONTH 2013 9
performance metric for the total energy consumption, when comparing OPS with existing methods.
6.2 Baseline: Typical Existing Schemes
We compare the performance of OPS with two typical existing methods. One is the common method in [6]–[8], i.e., the traditional pipeline scheduling method (denoted as single pipeline). For fair comparison, we improve the method with assumptions that a shortest path with the highest quality has been established in the SWSN and all nodes outside the path are scheduled at other time slots to send packets to the nodes on the path without collisions. Another typical existing method to be compared with is the multi-pipeline scheduling method in [9] (denoted as multi-pipeline) which makes use of multiple parent nodes in the network scheduled with multiple pipeline schedules.
6.3 Performance Comparison
This section compares the performance of OPS with the two typical existing methods.
6.3.1 Different Duty Cycles
We first evaluate the performance in networks with different duty cycles. In this simulation, 100 nodes are randomly deployed in 15m ∗ 300m field.
Fig. 10 (a) and (b) show the average delivery delay and energy cost of OPS method, single pipeline and multi- pipeline method. In Fig. 10 (a), the average delivery delay of the multi-pipeline method is only 50% of that of single pipeline when the duty cycle is low. It can be seen that, multiple transmission chances can effectively enhance the performance of the pipeline forwarding. Moreover, the average delivery delay of OPS is further far less than that of the multi-pipeline method. This is because OPS provides more transmission links than the multi-pipeline method. Meanwhile, OPS sets larger gap between adjacent nodes with multiple slots in which multiple transmission chances are allowed. While, the number of transmission chances provided by the multi- pipeline method is restricted by the number of parents in each layer. On the other hand, OPS also utilizes the potential parents in each layer in the SWSN to oppor- tunistically help retransmit packet, effectively reducing the failure cases in the duty cycle.
As shown in Fig. 10 (b), the energy costs of the single pipeline method and the multi-pipeline method are almost the same. This is because the number of transmissions of these methods is mainly determined by the link quality. In the OPS method, as the opportunistic forwarding nodes forward packets that are received through overhearing the transmissions of nodes on the forwarding path, some of the retransmissions are avoided. Hence, the number of transmission in OPS method is a bit lower than that in the single pipeline method and the multi-pipeline method.
Fig. 13: Deployment with 20 TelosB nodes.
0
100
200
300
400
500
600
1 2 3 4 5
A ve
ra g
e D
e la
y / T
im e
U n
its
Duty Cycle (s)
OPS Multi-pipeline
Fig. 14: Average delay.
6.3.2 Different Network sizes and Densities We also evaluate the performance of our design in dif- ferent network settings as shown in Fig. 11 and Fig. 12. For different network size from 60 to 140, the length of the area changes from 180m to 420m to keep a similar density. For different network densities, the network size is fixed at 100 while the length of the area changes from 200m to 450m.
As illustrated in Fig. 11, the average delivery delay and energy consumption increases with the network size. This is as expected. Again, OPS outperforms the single pipeline method and the multi-pipeline method. In most time, the average delivery delay of OPS is even less than 20% of that of the other two methods. For different network densities as shown in Fig. 12, the average delivery delay increases with the length of area. This is because larger length of area leads to longer distance between neighboring nodes, thus resulting in worse link quality. Note that, when setting the length of the area to be 200m, the average delivery delay of the multi-pipeline method becomes close to that of OPS. This is because the density in this case is high enough that the multi-pipeline method has enough parents in each layer to ensure more successful transmissions in the duty cycle.
7 EXPERIMENTS To show the performance of OPS in real communica- tion environment, we deployed 20 TelosB nodes in the corridor of our office building, as shown in Fig. 13 and Fig. 15. For convenience of the deployment, we set the minimum transmission power of each node to be 3µW . Hence, the maximum transmission range of sensor nodes is about 1m, when putting the nodes on the ground. In the deployment, most sensor nodes have two parents in each layer, except for three nodes. We utilize this deployment to compare the performance of the proposed OPS method with the multi-pipeline method proposed in [9]. The dashed arrows in OPS method in Fig. 15 are the opportunistic links provided by the opportunistic forwarding nodes. Here, we do not employ the opportunistic relaying nodes in the deployment for the sake of distinct comparisons between the two methods.
We set the wakeup schedules for the nodes according to OPS and the multi-pipeline method. The figures in Fig. 15 denote the time slot at which the sensor node periodically wakes up in each duty cycle. For the sake of simplicity, we fixed the wakeup-time gap 2τ for each
Page 34 of 36IEEE Transactions on Wireless Communications
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60
For P eer R
eview
IEEE TRANSACTIONS ON WIRELESS COMMUNICATIONS, VOL. XX, NO. Y, MONTH 2013 10
0
500
1000
1500
2000
2500
3000
0 0.05 0.1 0.15 0.2
A v e
ra g
e D
e la
y / T
im e
U n
it s
Duty Cycle
OPS Multi-pipeline
Single pipeline
(a) Delay vs. Duty Cycle
0
20
40
60
80
100
0 0.05 0.1 0.15 0.2
N u
m b
e r
o f T
ra n
s m
is s io
n s
Duty Cycle
OPS Multi-pipeline
Single pipeline
(b) Energy vs. Duty Cycle
Fig. 10: Duty Cycle
0
200
400
600
800
60 80 100 120 140
A v e
ra g
e D
e la
y / T
im e
U n
it s
Network Size
OPS Multi-pipeline
Single pipeline
(a) Delay vs. Network Size
0
20
40
60
80
100
60 80 100 120 140
N u
m b
e r
o f T
ra n
s m
is s io
n s
Network Size
OPS Multi-pipeline
Single pipeline
(b) Energy vs. Network Size
Fig. 11: Network Size
0
300
600
900
1200
200 250 300 350 400
A v e
ra g
e D
e la
y / T
im e
U n
it s
Length of Area (m)
OPS Multi-pipeline
Single pipeline
(a) Delay vs. Density
0
20
40
60
80
100
200 250 300 350 400
N u
m b
e r
o f T
ra n
s m
is s io
n s
Length of Area (m)
OPS Multi-pipeline
Single pipeline
(b) Energy vs. Density
Fig. 12: Network Density
2 4 6 7 9 11 12 14 16 17 19 20
3 5 8 10 13 15 18
1
3 5 7 9 11 13 15 17 19 21 23 25
3 5 9 11 15 17 21
1
Multi-pipeline:
OPS method:
S
S
D
D
Fig. 15: Topology of the deployment.
layer in OPS. The size of the time slot is τ = 6ms. The length of the duty cycle is set to be 1s, 2s, 3s, 4s, 5s, respectively. The node S delivers 50 packets to node D with an interval 10s. Node D records the delivery delay of each packet received.
Fig. 14 shows the results of the average delivery delay with the two methods, i.e., OPS and the multi-pipeline method. It can be seen that, OPS usually outperforms the multi-pipeline method. When the duty cycle increases, the predominance becomes more distinct. Even when T = 1s, the average delivery delay with OPS is about 30% of that with the multi-pipeline method. To get insight into the results, we can see that, each node in Fig. 15 with the multi-pipeline method has only one or two chances in each duty cycle to deliver the packet, while each node on the forwarding path in OPS has two chances to deliver to packet and one additional chance to opportunistically forward the packet.
8 CONCLUSIONS
The large hop counts in SWSNs with unreliable links usually cause long end-to-end data delivery delay. Pipeline scheduling is much suitable to resolve the prob- lem, while its performance is seriously deteriorated in unreliable communication environments. In this paper, we propose a novel opportunistic pipeline scheduling (OPS) specially for SWSNs with unreliable links. OPS sets opti- mal gap between adjacent nodes’ wakeup time to allow multiple retransmissions in the duty cycle, while mini- mizing the expectation delivery delay. In addition, OPS effectively employs nodes outside the forwarding path in SWSNs to opportunistically provide extra links, which helps forward the packets that fails to be delivered on the forwarding path. We conduct extensive simulations and in-door experiments to show that OPS significantly outperforms the existing methods in terms of end-to-end delivery delay while it consumes the similar amount of energy.
Page 35 of 36 IEEE Transactions on Wireless Communications
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60
For P eer R
eview
IEEE TRANSACTIONS ON WIRELESS COMMUNICATIONS, VOL. XX, NO. Y, MONTH 2013 11
REFERENCES [1] Chang Wen Chen, Yu Wang, Chain-Type Wireless Sensor Network
for Monitoring Long Range Infrastructures: Architecture and Protocols, International Journal of Distributed Sensor Networks, Vol. 4, No. 4, 2008, pp. 287-314.
[2] Peng Guo, Tao Jiang and Kui Zhang. Novel Energy-Efficient Miner Monitoring System with Duty-Cycled Wireless Sensor Networks. Inter- national Journal of Distributed Sensor Networks, 2012.
[3] Vasanthi, N.A., S. Annadurai, AWS: asynchronous wakeup schedule to minimize latency in wireless sensor networks, in Proceedings of SUTC, Taichung, Taiwan, Jun. 2006, pp. 144-151.
[4] Yanjun Sun, Shu Du, Omer Gurewitz, David B. Johnson, DW-MAC: a low latency, energy efficient demand-wakeup MAC protocol for wireless sensor networks, in Proceedings of MobiHoc, Hong Kong, China, 2008, pp. 53-62.
[5] Shuo Guo, Yu Gu, Bo Jiang and Tian He, Opportunistic Flooding in Low-Duty-Cycle Wireless Sensor Networks with Unreliable Links, in Proceedings of MobiCom, Beijing, China, Sept. 2009, pp. 133-144.
[6] Lu G, Krishnamachari B, Raghavendra C., An adaptive energy- efficient and low-latency MAC for data gathering in wireless sensor networks, in Proceedings of IPDPS, Santa Fe, New Mexico, Apr. 2004, pp. 224-230.
[7] Q. Cao, T. F. Abdelzaher, T. He, and J. A. Stankovic, Towards Optimal Sleep Scheduling in Sensor Networks for Rare Event Detection, in Proceedings of IPSN, UCLA, Los Angeles, California, USA, Apr. 2005, pp. 20- 27.
[8] Abtin Keshavarzian, Huang Lee, Lakshmi Venkatraman, Wakeup Scheduling in Wireless Sensor Networks, in Proceedings of MobiHoc, Florence, Italy, May 2006, pp. 322-333.
[9] Yongle Cao, Shuo Guo and Tian He, Robust Multi-Pipeline Schedul- ing in Low-Duty-Cycle Wireless Sensor Networks, in Proceeding of INFOCOM, Orlando, USA, Mar. 2012.
[10] Peng Guo, Tao Jiang Qian Zhang, and Kui Zhang, Sleep Schedul- ing for Critical Event Monitoring in Wireless Sensor Networks, IEEE Transactions on Parallel and Distributed System. Vol. 23, No. 2, 2012, 345-352.
[11] Ye W, Heidemann J, Estrin D., An Energy-Efficient MAC Protocol for Wireless Sensor Networks, in Proceedings of INFOCOM, New York, USA, Jun. 2002, pp. 567-576.
[12] Tae Rim Park and Myung Lee, Power Saving Algorithms for Wireless Sensor Networks on IEEE 802.15.4, IEEE communication magazine, Vol. 46, No. 6, 2008, pp.148-155.
[13] Vasanthi, N.A., S. Annadurai, Energy Efficient Sleep Schedule for Achieving Minimum Latency in Query based Sensor Networks, in Proceedings of SUTC, Taichung, Taiwan, Jun. 2006, pp. 214-219.
[14] R. M. Sanjit Biswas, ExOR: Opportunistic Multi-Hop Routing for Wireless Networks, in Proceedings of SIGCOMM, Philadelphia, PA, USA, Oct. 2005, pp. 133-144.
[15] Q. Cao, T. Abdelzaher, T. He and R. Kravets. Cluster-Based For- warding for Reliable End-to-End Delivery in Wireless Sensor Networks, in Proceedings of INFOCOM, Anchorage, Alaska, USA, May 2007, pp. 1928-1936.
[16] Rodrigo Fonseca, Omprakash Gnawali, Kyle Jamieson and Philip Levis, Four Bit Wireless Link Estimation, in Proceedings of HotNets, Atlanta, GA, USA, Nov. 2007.
[17] Alexander Becher, Olaf Landisiedel and Klaus Wehrle, Towards Short-Term Wireless Link Quality Estimation, in Proceedings of Em- Nets, Chalottesville, USA, June 2008.
[18] G. S. M. Maroti, B. Kusy and A. Ledeczi, The Flooding Time Synchronization Protocol, in Proceedings of SenSys, Baltimore, Mary- land, USA, Nov. 2004, pp. 39-49.
[19] M. Zuniga04 and B. Krishnamachari, Analyzing the Transitional Region in Low Power Wireless Links, in Proceedings of SECON, Santa, Clara, USA, Oct. 2004, pp. 517-526.
Page 36 of 36IEEE Transactions on Wireless Communications
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60