Page 1

arXiv:1204.4465v1 [cs.NI] 19 Apr 2012

Providing End-to-End Delay Guarantees for Multi-hop Wireless Sensor

Networks over Unreliable Channels

I-Hong Hou

Computer Engineering and System Group & Department of ECE

Texas A&M University

College Station, TX, USA

ihou@tamu.edu

Abstract—Wireless sensor networks have been increas-

ingly used for real-time surveillance over large areas.

In such applications, it is important to support end-to-

end delay constraints for packet deliveries even when

the corresponding flows require multi-hop transmissions.

In addition to delay constraints, each flow of real-time

surveillance may require some guarantees on throughput

of packets that meet the delay constraints. Further, as wire-

less sensor networks are usually deployed in challenging

environments, it is important to specifically consider the

effects of unreliable wireless transmissions.

In this paper, we study the problem of providing end-

to-end delay guarantees for multi-hop wireless networks.

We propose a model that jointly considers the end-to-end

delay constraints and throughput requirements of flows,

the need for multi-hop transmissions, and the unreliable

nature of wireless transmissions. We develop a frame-

work for designing feasibility-optimal policies. We then

demonstrate the utility of this framework by considering

two types of systems: one where sensors are equipped

with full-duplex radios, and the other where sensors

are equipped with half-duplex radios. When sensors are

equipped with full-duplex radios, we propose an online

distributed scheduling policy and proves the policy is

feasibility-optimal. We also provide a heuristic for systems

where sensors are equipped with half-duplex radios. We

show that this heuristic is still feasibility-optimal for some

topologies.

Keywords-Wireless sensor networks; end-to-end dead-

line; real-time communications

I. INTRODUCTION

The advance of wireless sensor networks provides an

appealing solution for real-time surveillance. In real-

time surveillance, wireless sensors generate flows of

surveillance data and deliver them to a sink, which

makes control decisions based on the data. Examples

of such applications have been demonstrated in many

previous work, such as [1]–[3].

A major challenge for real-time surveillance is to pro-

vide end-to-end delay guarantees for packet deliveries.

This material is based upon work partially supported by NSF

under Contracts CNS-1035378, CCF-0939370, CNS-1035340, and

CNS-0905397, USARO under Contract Nos. W911NF-08-1-0238 and

W-911-NF-0710287, and AFOSR under Contract FA9550-09-0121.

Designing scheduling policies that provide end-to-end

delay guarantees is difficult due to two reasons. As

wireless sensor networks may be deployed over a large

area, some flows may require multi-hop transmissions

to reach the sink. Further, wireless sensor networks are

usually deployed in challenging environments, such as

battlefields, forests, or underwater. Within these envi-

ronment, it may be impossible to ensure that all wireless

transmissions can be successfully received. Thus, a de-

sirable policy needs to explicitly address the unreliable

nature of wireless transmissions.

In this paper, we aim to address the above difficulties.

We measure the performance of each surveillance flow

by its timely-throughput, defined as the throughput of

packets that are delivered to the sink on time. We then

propose a model that characterizes the hard per-packet

end-to-end delay constraints and timely-throughput re-

quirements of flows, the routing protocol for multi-

hop transmissions, and the unreliable wireless channels.

This model also considers both scenarios where sensors

are equipped with full-duplex radios and half-duplex

ones.

Based on the model, we establish a general frame-

work for designing scheduling policies. We prove a suf-

ficient condition for a scheduling policy to be feasibility-

optimal, that is, to be able to fulfill all timely-throughput

requirements as long as they are feasible. We show that,

based on this condition, there is a dynamic program-

ming approach for designing policies for various types

of systems.

We then consider designing online, tractable, and

distributed scheduling policies. We propose a policy for

systems where sensors are equipped with full-duplex

radios. We prove that the proposed policy is feasibility-

optimal. We also propose a simple heuristic for systems

where sensors are equipped with half-duplex radios,

and show that it is feasibility-optimal among certain

topologies.

In addition to theoretical studies, we also provide

simulation results. We compare our proposed policies

against other policies. Simulation results show that our

proposed policies achieve significantly better perfor-

mance than others.

The rest of the paper is organized as follows. Sec-

tion II summarizes existing work on providing end-to-

end delay guarantees. Section III formally introduces

our analytical model. Section IV establishes a frame-

work for designing feasibility-optimal policies. Based

on the framework, Section V proposes a feasibility-

optimal policy for systems where sensors are equipped

with full-duplex radios. Section VI proposes a heuris-

tic for systems where sensors are equipped with half-

duplex radios, and proves that the heuristic is feasibility-

optimal for some topologies. Section VII demonstrates

our simulation results. Finally, Section VIII concludes

this paper.

II. RELATED WORK

Providing end-to-end delay guarantees have been an

important research topic for various systems. Jayachan-

dran and Abdelzaher [4] have studied this problem

for distributed real-time systems where a job needs to

traverse a number of processors before it is completed,

and have provided a worst-case analysis for end-to-

end delays. Hong, Chantem, and Hu [5] have consid-

ered a similar problem and approached it by assigning

local deadlines for each processor. Li and Eryilmaz

[6] have proposed a scheduling policy that aims to

meet per-packet delay bounds and timely-throughput

requirements of flows in wireline networks. However,

no performance guarantees were provided for their

scheduling policy. Rodoplu et al [7] have studied the

problem of estimating end-to-end delay over multi-hop

wireless networks. Li et al [8] have proposed using

expected end-to-end delay for selecting path in wireless

mesh networks. The expected end-to-end delay takes

both queuing delay and delay caused by unsuccessful

wireless transmissions. However, their work only aims at

minimizing the average end-to-end delays, and cannot

provide guarantees on per-packet delays. Jayachandran

and Andrews [9] have applied a coordinated EDF sched-

uler for wireless networks and obtained asymptotic

bounds on end-to-end delays. Li et al [10] have used

network calculus to analyze and derive upper-bound

for end-to-end delays. Li, Li, and Mohapatra [11] have

proposed a distributed policy for scheduling packets

with end-to-end delay guarantees. However, their work

lacks theoretical guarantees on performance.

There has also been a lot of work that considers end-

to-end delay guarantees for wireless sensor networks.

Jiang, Ravindran, and Cho [12] have studied the real-

time capacity of wireless sensor networks. They ap-

proach this problem by decomposing end-to-end delays

into per-hop delays, and then study the probability for

meeting each per-hop delay independently. Wang et al

[13] have used a similar decomposition approach and

studied the problem of energy saving while providing

end-to-end delay guarantees. Such decomposition ap-

proach inevitably leads to suboptimal solutions. Chipara

et al [14] have proposed a protocol for scheduling real-

time flows by taking interference among sensors into ac-

count. Wang et al [15] have investigated the distribution

of end-to-end delay in wireless sensor networks. Wang

et al [16] have formulated the problem of providing

end-to-end delay guarantees as an optimization prob-

lem, and have proposed a heuristic for obtaining sub-

optimal solutions. Li, Shenoy, and Ramamritham [17]

have aimed at providing end-to-end delay guarantees

by exploiting spatial reuse.

III. SYSTEM MODEL

In this section, we present our model for multi-hop

wireless sensor networks with end-to-end delay con-

straints. Our model extends a model proposed in [18],

which only considers the delay constraints of packets

and unreliability of wireless transmissions in a one-hop

scenario.

Consider a sensor network with a set N of wireless

sensors. One of the sensors play the role of the sink.

Sensors may generate surveillance data that need to

be delivered to the sink in a timely manner, and they

may relay data that are generated by other sensors. We

assume that a routing tree has been constructed by some

routing protocol for the sensor network. There has been

a lot of work on constructing routing trees for wireless

sensor networks, and [19] provides a survey of these

routing protocols. In the routing tree, the sink is the

root, and hence we use r to represent the sink. When

a sensor n has a data packet, either one generated by

itself or one that is forwarded to it from other sensors,

it may forward the data to its parent, denoted by h(n),

in the routing tree. Figure 1 shows an example of such

a sensor network. A data packet is said to be delivered

if it reaches the sink. A sensor may generate multiple

flows of data. For example, one sensor may generate

data on both temperature and humidity. We denote the

set of flows in the wireless sensor network by F, and

n(f) as the sensor that generates data of flow f.

We assume that time is slotted and numbered by

t = 1, 2,.... The length of a time slot is set to be the

time needed for a sensor to transmit one data packet.

Time slots are further grouped into intervals, where

each interval consists of T consecutive time slots in

(kT, (k + 1)T], for some k. At the beginning of each

interval, each flow in F obtains some surveillance data

and generates a data packet. We say that a the data

packet of flow f is generated at the τth

f

time slot in

each interval, so as to account for the latency caused

by sensing and data processing. We assume that all

Figure 1: An example of the system consists of 10

sensors. In the example, we have h(1) = h(2) = r,

h(3) = h(4) = 1, h(5) = 2, etc.

data packets are delay-constrained, and data packets

generated in one interval need to be delivered to the

sink before the end of the interval. If a data packet is

not delivered before the end of the interval, the packet

is no longer useful for the sink. In this case, we say

that the packet expires, and drop the packet from the

system. Thus, we can guarantee that all data received

by the sink have delays no larger than T time slots.

We consider both cases when sensors are equipped

with full-duplex radios and when they are equipped

with half-duplex radios. When sensors are equipped

with full-duplex radios, they can transmit and receive

data packets simultaneously. We also assume that the

transmissions of different sensors do not interfere with

each other by, for example, allocating different sensors

on different subcarriers in an orthogonal frequency-

division multiple access (OFDMA) system. A system

where sensors are equipped with full-duplex radios is

called a full-duplex system.

The assumptions made for full-duplex systems may

exceed current hardware limitations of wireless sensor

network. Thus, we also consider systems where sensors

are equipped with half-duplex radios. In such systems,

sensors cannot transmit and receive data packets si-

multaneously. That is, when a sensor n transmits, its

parent h(n) cannot transmit, or the transmission by

n encounters a collision and the transmission fails.

Moreover, we assume that a sensor can receive at most

one transmission in a time slot. That is, if we have

sensors n and m with h(n) = h(m), then at most one

of them can transmit in a time slot. Finally, we assume

that different transmissions do not interfere with each

other except the two cases discussed above. This can be

done by, for example, scheduling transmissions that may

interfere with each other in different channels. A system

where radios are equipped with half-duplex radios is

called a half-duplex system.

We consider the unreliable nature of wireless trans-

missions. To be more specific, we say that when a

sensor n transmits a data packet to its parent, h(n),

h(n) correctly receives the packet with probability pn.

We also assume that, by implementing ACKs, the sensor

n has feedback information on whether its transmission

is correctly received by h(n), and it can retransmit the

same packet in the case that a previous transmission

fails.

As wireless transmissions are unreliable, it may be

impossible to deliver all data packets to the sink on

time. Instead, each flow f requires a portion qf of

packets to be delivered on time. That is, let ef (k) be

the indicator function that the data packet of flow f in

the kth interval is delivered to the sink on time. Each

flow f then requires that, with probability one,

lim inf

K→∞

∑K

k=1 ef (k)

K

≥ qf .

We call

∑K

k=1 ef (k)

K

as the timely-throughput of flow

f up to interval K, and qf as the timely-throughput

requirement on flow f.

In this paper, we aim to design scheduling policies

that fulfills timely-throughput requirements of all flows

as long as they are strictly feasible. These terms are

formally defined as follows:

Definition 1: A system is said to be fulfilled

by some scheduling policy if, under this policy,

lim infK→∞

∑K

k=1 ef (k)

K

≥ qf with probability one, for

all flow f ∈ F.

Definition 2: A system, either a full-duplex system

or a half-duplex one, is feasible if there exists some

scheduling policy that fulfills it.

Definition 3: A system, either a full-duplex system or

a half-duplex one, is strictly feasible if qf > 0 for all flows

f, and there exists some ǫ > 0 such that the system

is still feasible when each flow f requires a timely-

throughput of (1 + ǫ)qf .

Definition 4: A scheduling policy is feasibility-optimal

for full-duplex system, or half-duplex system, if it fulfills

all strictly feasible full-duplex systems, or all strictly

feasible half-duplex systems, respectively.

We limit our discussions on strictly feasible systems

only to simplify the proof of Theorem 1 in the following

section. As ǫ can be arbitrarily small, this limitation is

not restrictive.

IV. A FRAMEWORK FOR SCHEDULING POLICIES

In this section, we describe a sufficient condition

for a policy to be feasibility-optimal. We then show

a dynamic program approach that derives feasibility-

optimal policies by employing this sufficient condition.

This condition is based on the concept of debt:

Definition 5: The debt of f in the Kth interval is

defined as df (K) := Kqf − ∑K

k=1 ef (k), where ef (k) is

the indicator function that the packet for f in interval

k is delivered on time.

It is easy to show that a system is fulfilled under some

scheduling policy if and only if lim supK→∞

df (K)

K

≤ 0.

Based on the concept of debt, we establish a sufficient

condition for a policy to be feasibility-optimal for full-

duplex systems or half-duplex systems. The condition

is similar to the one introduced in [20], which only

considers one-hop transmissions, and is based on the

following theorem:

Lemma 1 (Telescoping Lemma): Let L(k) be a non-

negative Lyapunov function depending only on Fk,

which denotes the set of all events in the system in the

first k intervals, i.e., L(k) is adapted to Fk. Suppose

there exist positive constants B > 0, δ > 0, and a

stochastic process f(k) also adapted to Fk, such that:

E[L(k + 1) − L(k)|Fk] ≤ B − δE[f(k)|Fk],

(1)

then lim supK→∞

1

K ∑K−1

k=0 E[f(k)] ≤ B/δ, where E[x]

is the expected value of x.

Theorem 1: A scheduling policy is feasibility-optimal

for full-duplex system, or half-duplex system, if, given

df (k), it maximizes

∑

f∈F

df (k)+E[ef (k + 1)]

in the (k + 1)th interval, for all k, where x+

:=

max{x, 0}, for all full-duplex systems, or half-duplex

systems, respectively.

Proof: Consider a strictly feasible system where flow

f requires a timely-throughput of qf > 0. There exists

some ǫ > 0 such that this system is fulfilled by some

stationary randomized scheduling policy, η0, when each

flow f requires a timely-throughput of (1 + ǫ)qf . Thus,

under η0, we have E[ef (k)] ≥ (1 + ǫ)qf .

Define a Lyapunov function L(k) := 1

2 ∑f (df (k)+)2.

Since df (k + 1) = df (k) + qf − ef (k + 1), we have

L(k + 1) =

1

2

∑

f∈F

(df (k + 1)+)2

≤

1

2

∑

f∈F

(df (k)+ + qf − ef (k + 1))2

=

1

2

∑

f∈F

(df (k)+)2 + ∑

f∈F

df (k)+(qf − ef (k + 1))

+ ∑

f∈F

(qf − ef (k + 1))2

≤L(k) + ∑

f∈F

df (k)+(qf − ef (k + 1)) + B,

(2)

for some constant B, as qf and ef (k + 1) are both

bounded by 1, for all f.

As E[ef (k + 1)] ≥ (1 + ǫ)qf under η0, for all f, we

have, under η0,

E[∑

f∈F

df (k)+(qf − ef (k + 1))|Fk]

= ∑

f∈F

df (k)+(qf − E[ef (k + 1)])

= ∑

f∈F

df (k)+qf − ∑

f∈F

df (k)+E[ef (k + 1)]

≤ − ǫ ∑

f∈F

df (k)+qf .

(3)

Let

ηmax

be

the

policy

that maximizes

∑f∈F df (k)+E[ef (k + 1)]. Under ηmax, we also

have

E[∑

f∈F

df (k)+(qf − ef (k + 1))|Fk] ≤ −ǫ ∑

f∈F

df (k)+qf .

Thus, by Eq. (2), we have, under ηmax,

E[L(k + 1) − L(k)|Fk]

≤E[∑

f∈F

df (k)+(qf − ef (k + 1))|Fk] + B

≤B − ǫ ∑

f∈F

df (k)+qf .

Thus, by Lemma 1, we have

lim sup

K→∞

1

K

K

∑

k=1

∑

f∈F

E[df (k)+qf ] ≤ B/ǫ.

(4)

Finally, Lemma 4 in [20] shows that Eq. (4) implies that

lim supK→∞(df (K)+

K

)=0, for all f, and this system is

fulfilled by ηmax. Thus, ηmax is feasibility-optimal.

A. A Dynamic Programming Approach for Scheduling

Policies

We now introduce a dynamic programming approach

for designing scheduling policies that aims at maximiz-

ing ∑f∈F df (k)+E[ef (k+1)] in the (k+1)th interval by

making scheduling decisions for each time slot within

the interval. We first describe the system evolution

within an interval by a Markov decision process. In the

tth time slot within the interval, we represent the state

of the system by t and the position of the packet of

each flow. We denote the position of the packet of flow

f by cf (t), where cf (t) = n if n has the packet and

can transmit it in the tth time slot, and cf (t) = φ if

the packet of f is yet to be generated, as the packet

of flow f will not be generated until the τth

f

time slot

in the interval. The evolution of cf (t + 1) can then be

described as follows: cf (t + 1) = n(f) when t +1= τf ,

where n(f) is the sensor that generates the packet

of f; cf (t + 1) = h(cf (t)) with probability pcf (t) if

cf (t) transmits the packet of f in the tth time slot,

where h(cf (t)) is the parent of cf (t) in the routing tree

and pcf (t) is the channel reliability between cf (t) and

h(cf (t)); and cf (t + 1) = cf (t), otherwise.

We say that the interval ends when t = T + 1.

Thus, the packet of f is delivered, and ef (k +1)=1,

if cf (T + 1) = r. Let V (t, {cf (t)}) be the value of

∑f∈F df (k)+E[ef (k+1)] when the state of the system is

represented by {cf (t)} at the tth time slot under some

policy. By Theorem 1, a policy is feasibility-optimal if

it maximizes V (1, {cf (1)}), where {cf (1)} is the state

of the system at the beginning of the interval. Let

V max(t, {cf (t)}) be the maximum value of V (t, {cf (t)}).

We then have the recursive relation: V max(t, {cf (t)}) =

maxa∈A(t,{cf (t)}) E[V max(t + 1, {cf (t + 1)})], where

A(t, {cf (t)}) is the set of possible schedule decisions

under the current state. Hence V max(t, {cf (t)}) can

be obtained by dynamic programming. Moreover, a

policy that makes its schedule decisions by choosing

arg maxa∈A(t,{cf (t)}) E[V max(t + 1, {cf (t + 1)})] for all

states is feasibility-optimal.

While we can derive feasibility-optimal policies from

the above approach, this approach may require high

computation overhead, as the number of states for the

system is as large as (T + 1)(|N| + 1)|F |. In the fol-

lowing sections, we demonstrate that there is a simple

online policy for full-duplex systems. We also introduce

a heuristic for half-duplex system and show that the

heuristic is feasibility-optimal under some restrictions.

V. AN ONLINE SCHEDULING POLICY FOR FULL-DUPLEX

SYSTEMS

We now introduce an online scheduling policy for full-

duplex systems. The policy is very simple: in each time

slot, a sensor n picks the flow that has the largest debt

among those that it currently holds their packets, and

transmits its packet. In other words, in each time slot t

of the (k + 1)th interval, n schedules the packet from

arg maxf:cf (t)=n df (k). We call this policy the Greedy

Forwarder. In addition to low complexity, this policy

is also distributed and does not require a centralized

scheduler. Moreover, as we establish below, this simple

policy is indeed feasibility-optimal.

Theorem 2: The Greedy Forwarder is feasibility-

optimal.

Proof: By Theorem 1, we can show that the Greedy

Forwarder is feasibility-optimal by showing that it maxi-

mizes ∑f∈F df (k)+E[ef (k+1)]. To show this, we prove

the following two claims by induction on the size of the

network,|N|:

1) The

Greedy

Forwarder

maximizes

∑f∈F df (k)+E[ef (k + 1)].

2) Suppose a sensor generates packets from flow

f1,f2,..., where df1 (k) ≥ df2 (k) ≥ .... Also

assume that this sensor generates packets at time

t1 ≤ t2 ≤ ... , and the sensor has control over

which flow among {f1,f2,...} is to generate pack-

ets at time t1,t2,..., respectively. Then, with all

other conditions fixed, by selecting f1 to generate

its packet at times t1, f2 to generate its packet at

time t2, etc, ∑f∈F df (k)+E[ef (k+1)] for the whole

system is maximized.

We first discuss the case when |N| = 1, in which

the sink r is the only sensor in the system. As there is

only one sensor in the system, there are no scheduling

decisions to be made, and hence Claim (1) holds.

Moreover, a packet of flow f is delivered, and hence

ef (k +1) = 1, if it is generated before the Tth time

slot. Thus, Claim (2) holds as ∑f∈F df (k)+E[ef (k + 1)]

is maximized by generating packets in decrement order

of their debts.

Assume that both Claim (1) and Claim (2) hold

for all networks with size |N| = M. We now show

that these two claims also hold for all networks with

|N| = M + 1. We pick a leaf node, denoted by n0, in

the routing tree. We assume that n0 generates packets

for flows f1,f2,..., with df1 (k) ≥ df2 (k) ≥ ... , at

times t1 ≤ t2 ≤ ..., and n0 has control over which

flows among {f1,f2,... } is to generate packets at times

t1,t2,... , respectively. We also assume that n0 uses a

work-conserving policy, i.e., it always schedules a trans-

mission as long as it holds a packet1. Under this policy,

n0 successfully transmits packets at times t1 ≤ t2 ≤ ... .

We note that t1, t2,... are random variables whose

distributions are determined by the channel reliability

1Obviously, a policy cannot lose its optimality by making more

transmissions. Thus, this assumption is not restrictive.

between n0 and h(n0). Moreover, we have ti ≥ ti, for

all i, as it is impossible to successfully transmit i packets

before at least the same amount of packets are gener-

ated. Note that t1, t2,... are not influenced by the order

of packet generations and scheduling decisions, as each

transmission made by n0 is successful with probability

pn0 , regardless which packet is being transmitted.

Given t1, t2,... , n0 can effectively determine which

packets are to be successfully transmitted at times

t1, t2,... , by choosing the order of packet generations

and scheduling decisions. The only restriction for n0 is

that the packet from a flow f cannot be transmitted

before it is generated. If the packet from a flow f is

successfully transmitted by n0 at time t, h(n0) receives

the packet at time t and can transmit the packet starting

at time t + 1. Thus, this system is equivalent to one

with n0 removed, making the size of the network to

be M, and packets from flows f1,f2,... are generated

at sensor h(n0) at times t1 + 1, t2 + 1,.... By the

induction hypothesis on this system with M sensors,

∑f∈F df (k)+E[ef (k + 1)] is maximized if the packet

from flow fi is generated at time ti + 1, for all i. As n0

can make this happen by choosing flow fi to generate a

packet at time ti and follow the Greedy Forwarder, both

Claim (1) and Claim (2) hold when n0 is included in

the system with size M + 1.

By induction on |N|, we have that both claims hold

for all systems, and hence the Greedy Forwarder is

feasibility-optimal.

We close this section by discussing some imple-

mentation issues of the Greedy Forwarder. As noted

above, under the Greedy Forwarder, every sensor makes

scheduling decisions solely based on the packets it

holds. Still, the Greedy Forwarder requires each sensor

to have the knowledge of debts for all flows in the

current interval. In practice, this may be impractical. In

particular, for a large network, sensors that are far away

from the sink can only obtain delayed information on

debts of flows. However, as we will show in Section VII,

when sensors apply the Greedy Forwarder with delayed

information on debts, the resulting performance can still

be optimal. This is because, as the net change of debt,

|df (k + 1) − df (k)|, is bounded, the difference between

the delayed information on debt and the actual current

debt is also bounded for all flows. Therefore, a sensor

that only has delayed information on debts will make

similar scheduling decisions as one that has information

on the current values of debts.

VI. A HEURISTIC FOR HALF-DUPLEX SYSTEMS

In this section, we propose a policy for half-duplex

systems and show that this policy is feasibility-optimal

for some particular scenarios.

Recall that there are two important limitations for

half-duplex systems. First, as a sensor cannot transmit

and receive simultaneously, a sensor n cannot transmit

when its parent, h(n), is also transmitting. Second, a

sensor can only receive one packet at a time, and hence

two sensors n and m with h(n) = h(m) cannot transmit

simultaneously. To address theses challenges, we pro-

pose a policy, namely, the Closest Sensor First Policy. We

first define dn(t) := maxf:cf (t)=n df (k). In other words,

dn(t) is the largest debt of flows that n holds at the tth

time slot. If the sensor n does not hold any packets,

dn(t) is defined to be −∞. The Closest Sensor First

Policy can be described iteratively as follows: First, we

examine all sensors that are one-hop away from the root

r, that is, we examine all sensors such that h(n) = r.

We then schedule the sensor with the largest dn(t) to

transmit, and the sensor transmits the packet from the

flow with the largest debt. Next, we examine sensors

that are two-hop away from the root, that is, sensors

with h(h(n)) = r. If h(n) is scheduled to transmit in the

first step, then n cannot transmit. Otherwise, a sensor

n is scheduled to transmit the packet from the flow

with the largest debt if dn(t) is the largest among all

sensors m with h(m) = h(n). In the above procedure,

ties are broken arbitrarily, and we carry the procedure

iteratively.

In summary, a sensor n who is g-hop away from the

root is scheduled in the gth iteration if: (i) h(n) is

not scheduled in the previous iteration, and (ii) dn(t)

is the largest among all m with h(m) = h(n). Fig. 2

shows an example that illustrates the Closest Sensor

First Policy. In the example, we number sensors by their

respective dn(t). Thus, we have dn(t) = n. In the first

iteration, sensor 5 is scheduled as d5(t) > d3(t). In the

second iteration, sensor 2 is scheduled as d2(t) > d1(t).

Note that sensor 4 cannot be scheduled as its parent,

sensor 5, has already been scheduled. Finally, in the

third iteration, sensor 7 and sensor 9 are scheduled.

Next, we show that the Closest Sensor First Policy

is feasibility-optimal if all flows are generated by the

same sensor n0, i.e., n(f) = n0, for all f, and each flow

generates a packet at the beginning of the interval, i.e.,

τf = 1, for all f. In such a system, only sensors on

the path between n0 and r are involved in forwarding

messages. Thus, we call such a system as a path-topology

system.

Theorem 3: The Closest Sensor First Policy is

feasibility-optimal for path-topology systems.

Proof: By Theorem 1, we can show that the Clos-

est Sensor First Policy is feasibility-optimal for path-

topology systems by establishing that this policy maxi-

mizes ∑f∈F df (k)+E[ef (k+1)] in the (k+1)th interval.

Let γn[v] be the number of transmissions that sensor

n needs to make to successfully transmit v packets to

Figure 2: An example that illustrates the Closest Sensor

First policy.

its parent. Note that this does not imply that sensor n

successfully transmits v packets at the γn[v]th time slot

in the interval, as there are time slots that sensor n

is not scheduled due to the constraints of half-duplex

systems. We also note that (γn[v] − γn[v − 1]) is a geo-

metric random variable with mean 1/pn, as the channel

reliability between n and h(n) is pn. In practice, the

values of {γn[v]} cannot be obtained at the beginning

of the interval. We will show that, even when the values

of γn[v] are given for all n and v, there is no policy

that can achieve larger ∑f∈F df (k)+ef (k + 1) than the

Closest Sensor First Policy, and hence than the Closest

Sensor First Policy maximizes ∑f∈F df (k)+E[ef (k+1)].

We order flows so that df1 (k) ≥ df2 (k) ≥ ... . Let

η and η∗ be the Closest Sensor First Policy and an-

other policy that maximizes ∑f∈F df (k)+E[ef (k + 1)],

respectively. Further, let θfi

and θ∗

fi

be the times that

the packet from flow fi is delivered under η and η∗,

respectively. If the packet from flow fi is not delivered

on time under η, or η∗, we set θfi , or θ∗

fi, to be T + 1.

Thus, under η, or η∗, we have efi (k+1) = 1(θfi < T +1),

or efi (k + 1) = 1(θ∗

fi < T + 1), respectively.

By the design of the Closest Sensor First Policy, we

have θf1

≤ θf2

≤ .... Suppose there exists some i

so that θ∗

fi

> θ∗

fi+1

under η∗. We can modify η∗ so

that whenever it schedules the packet from flow fi,

it schedules the packet from flow fi+1 instead, and

vice versa. Under this modification, the packet of fi

is delivered on the (θ∗

fi+1 )th time slot, and the packet

of fi+1 is delivered on the (θ∗

fi )th time slot. If both

θ∗

fiand θ∗

fi+1are smaller than T + 1, both packets are

still delivered on time after this modification, and hence

the value of ∑f∈F df (k)+ef (k + 1) is not influenced. If

both θ∗

fi and θ∗

fi+1 are larger than T, neither packets are

delivered on time after this modification, and the value

of ∑f∈F df (k)+ef (k + 1) is not influenced. However, if

θ∗

fi > T ≥ θ∗

fi+1, the packet of fi is delivered on time

and the packet of fi+1 is not after the modification, and

the value of ∑f∈F df (k)+ef (k+1) will not decrease, as

dfi (k) ≥ dfi+1 (k), with the modification. In sum, the

value of ∑f∈F df (k)+ef (k + 1) will not decrease with

the modification. Thus, we can repeat this procedure

until θ∗

f1

≤ θ∗

f2

≤ ... without decreasing the value of

∑f∈F df (k)+ef (k + 1).

From now on, we assume that θ∗

f1 ≤ θ∗

f2 ≤ ... under

η∗. We claim that, under this assumption, θfi ≤ θ∗

fi

for

all i. We prove this claim by induction on the number

of flows. When there is only one flow in the system, the

Closest Sensor First Policy schedules a transmission for

flow 1 in every time slot, and hence θf1 ≤ θ∗

f1 .

Assume that θfi ≤ θ∗

fifor all i when the system has

I flows. We now consider the case when the system

has I + 1 flows. Under the Closest Sensor First Policy,

whether the packet of a flow fi with i ≤ I is scheduled is

not influenced by whether the flow fI+1 is present in the

system. Thus, the value of θfi is the same as in the case

when the system only has I flows, for all i ≤ I. We then

have θfi ≤ θ∗

fi for all i ≤ I by the induction hypothesis.

Therefore, we only need to prove that θfI+1

≤ θ∗

fI+1

.

If θ∗

fI+1

= T + 1, i.e., the packet of flow fI+1 is not

delivered on time under η∗, then θfI+1 ≤ θ∗

fI+1 holds.

Consider the case θ∗

fI+1 ≤ T. Suppose that, under η∗,

there is some time during the interval when the packet

from flow fi+1 is closer to the root than the packet from

flow fi, for some i. Pick i′ to be the smallest number

so that the packet from flow fi′+1 is closer to the root

than the packet from flow fi′

at some time t during

the interval. Now we can pick t1 to be the largest time

before t such that the packet from flow fi′+1 and that

from flow fi′ are held by the same sensor. Such t1 exists

as both packets are held by the sensor that generates all

packets at the beginning of the interval. We then pick t2

to be the smallest time after t such that both packets are

held by the same sensor. Such t2 exists as we assume

that the packet from flow fi′

is delivered earlier than

the packet from flow fi′+1. Thus, in any time slot in

(t1,t2), the packet from flow fi′+1 is always closer to

the root than that from flow fi′ . Now, we can modify

η∗ for time slots in [t1,t2] so that when it schedules

i′, it schedules i′ + 1 instead, and vice versa. After this

modification, the packet from flow fi′ is always closer

to the root than that from flow fi′+1 during (t1,t2).

Further, this modification does not influence θf for any

flow f. We repeat this modification until such i′ does

not exist. From now on, we can assume that, at any

point of time, the packet from flow fi is not closer to

the root than the packet from flow fj if j<i.

We prove that θfI+1

≤ θ∗

fI+1

by contradiction. Note

that after the packet of flow fI is delivered, η, or η∗,

needs to schedule the packet of flow fI+1 an addition

number of (θfI+1 − θfI ), or (θ∗

fI+1 − θ∗

fI ), times before it

is delivered, respectively. By the induction hypothesis,

θfI ≤ θ∗

fI. Therefore, if θfI+1 > θ∗

fI+1, we have θfI+1 −

θfI > θ∗

fI+1 −θ∗

fI, and, under η∗, there are times that the

packet from flow fI+1 is scheduled while it would not

be schedule under η. We call these times the inversion

times and denote them by t1 < t2 < ··· < tM . We

assume that, among all policies that deliver packets at

times θ∗

f1 ,θ∗

f2 ,... , η∗ is one that has the smallest number

of inversion times. Moreover, among those policies that

have the smallest number of inversion times, η∗ is one

that maximizes tM .

At time tM , the sensor cfI+1 (tM ) holds the packet

from flow fI+1 and schedules it under η∗, while

cfI+1 (tM ) would not schedule this packet under η. There

are two possibilities: first, the sensor cfI+1 (tM ) holds

another packet, and η would schedule it; and second,

under η, the sensor cfI+1 (tM ) would not transmit, as

its parent, h(cfI+1 (tM )), would be scheduled for trans-

mission. In the first case, under η∗, the transmission of

fI+1 cannot be successful. Otherwise, at time tM + 1,

the packet of fI+1 is closer to the root than the other

packet that cfI+1 (tM ) holds, and violates our previ-

ous assumption. Thus, for this case, we can modify

η∗ so that cfI+1 (tM ) schedules the other packet, and

this modification will not influence the deliver times

of packets. In this case, there are no inversion times

at and after time tM after the modification. As this

modification does not create new inversion times, we

obtain a policy that has a smaller number of inversion

times than η∗, which contradicts our assumption in

the last paragraph. Now consider the second case, that

is, the sensor cfI+1 (tM ) would not be scheduled by η

because η would schedule its parent for transmission.

As tM is the largest inversion time, there will be a

time after tM such that h(cfI+1 (tM )) is scheduled to

transmit a packet, and the packet from flow fI+1 is not

scheduled. We call this time t′. At time t′, either sensor

cfI+1 (tM ) or h(cfI+1 (tM )) holds the packet from flow

fI+1. We can modify the schedule so that h(cfI+1 (tM ))

is scheduled for transmission at time tM , instead of

cfI+1 (tM ), and the packet from flow fI+1 is scheduled

for transmission at time t′. Note that, by our previous

assumption, the packet from flow fI+1 is not closer

to the sink than any other packets. In other words,

every sensor that is farther from the sink than the one

holds the packet from flow fI+1 does not hold any

packets. Therefore, this modification will not violate any

interference constraints of the half-duplex system. This

modification does not influence the delivery times of

packets and does not increase the number of inversion

times. Moreover, after applying the modification, the

largest inversion time becomes t′, which contradicts

our assumption that η∗ maximizes the largest inversion

time.

In summary, we have established that θfi

≤ θ∗

fi

for

all flows when there are I + 1 flows in the system. By

induction, we have θfi ≤ θ∗

fi

for all flows, for all path-

topology systems. Therefore, the Closest Sensor First

Policy is feasibility-optimal for path-topology systems.

VII. SIMULATION RESULTS

In this section, we present our simulation results. We

adopt the simulation settings in [17], where each flow

generates one packet every 20 ms, and it takes 2 ms

for a sensor to make a transmission. Thus, we set the

duration of a time slot to be 2 ms, and each interval

consists of 10 time slots.

We consider the network topology as shown in Fig. 1.

For each sensor n, its channel reliability, pn, is randomly

selected within [0.4, 0.9]. We assume that each of sensor

3, sensor 5, sensor 6, sensor 7, sensor 8, and sensor

9 generates two flows. Therefore, there are a total

number of 12 flows in the system. To better illustrate

our simulation results, we assume that for each of these

sensors, one flow requires a timely-throughput of α, and

the other requires a timely-throughput of β. We define

the timely-throughput region of a policy to be the region

consists of all (α, β) that can be fulfilled by the policy.

We can then evaluate the performance of a policy by its

timely-throughput region.

For all scenarios, we conduct the simulation for 3000

intervals, i.e., one minute in the simulation environ-

ment. A system is said to be fulfilled if, by the end of

the simulation, the debts are less than 90 for all flows,

which means the actual timely-throughput that a flow

has is at least (qf − 0.03).

We consider both the full-duplex system and half-

duplex system. For the full-duplex system, we compare

our proposed policy, the Greedy Forwarder, against two

other policies. We consider a policy where each sensor

randomly chooses a packet that it holds to transmit

in each time slot. The policy is called the Random

policy. We also consider another policy where sensors

give priorities to flows with higher timely-throughput

requirements, and break ties randomly. The policy is

called the Static Priority policy.

The simulation results for the full-duplex system

is shown in Fig. 3. The Greedy Forwarder achieves

the largest timely-throughput region, as it is indeed

feasibility-optimal. The performance of the Static Pri-

ority policy is close to optimal when either α is much

larger than β, or vice versa, as it gives higher priorities

to flows with larger timely-throughput requirements.

On the other hand, the Static Priority policy inevitably

starves flows with smaller timely-throughput require-

ments. Thus, it results in poor performance when α is

Figure 3: Simulation results for the full-duplex system.

Figure 4: Simulation results for systems where sensors

only have delayed information on debts.

close to β. The performance of the Random policy is

also far from optimal, as it does not take the timely-

throughput requirements of flows into account.

We also investigate the influence on the Greedy For-

warder when sensors only have delayed information

on debts of flows. We assume that all sensors other

than the sink update their information on debts every

λ intervals, and we call λ the update period. When a

sensor n updates its information, it notifies its children

in the routing tree the information on debts that it

currently has, and receives an updated information from

its parent. Thus, for a sensor that is g-hop away from

the sink, the information on debts that it has may be

λ × g intervals old. We consider three scenarios: one

where all sensors have knowledge of the current debts

of flows, one where the update period is 100 intervals,

i.e., 2 seconds, and one where the update period is

200 intervals. Simulation results are presented in Fig.

4. It can be shown that even when sensors update their

information on debts as infrequent as once every four

seconds, the performance of the Greedy Forwarder is

still close to optimal.

Next we consider the half-duplex system. We consider

Figure 5: Simulation results for the half-duplex system.

a policy that, in each time slot, randomly selects a

maximal set of sensors who can transmit simultaneously

among those that hold some packets. Each selected

sensor then randomly selects a packet to transmit. We

call this policy the Random policy. We also consider

a policy that first sorts all undelivered packets in de-

scending order of the timely-throughput requirements

of their associated flows. The policy then greedily selects

a maximal subset of packets so that they can be trans-

mitted simultaneously. This policy is called the Static

Priority policy. Finally, we consider the Closest Sensor

First policy.

The simulation results of the half-duplex system is

shown in Fig. 5. The Closest Sensor First policy achieves

the largest timely-throughput region. A somewhat sur-

prising result is that both the Random policy and the

Static Priority policy have very poor performance. The

Rand policy fails to fulfill the system even when we

set (α, β) = (0, 0.05), and hence its timely-throughput

region does not appear in Fig. 5. The reason for this

behavior is because there are interference constraints

for half-duplex systems, which limit the number of

sensors that can transmit simultaneously. Thus, it is

important to take the network topologies into account

in order to deliver packets on time.

Finally, we consider a half-duplex path-topology sys-

tem with six sensors and six flows, as depicted in

Fig. 6. All six flows are generated by sensor 5. Three

of the flows require a timely-throughput of α, while

the other three flows require a timely-throughput of

β. The simulation results are shown in Fig. 7. The

Closest Sensor First policy achieves the largest timely-

throughput region. Moreover, both the Static Priority

policy and the Random policy fail to fulfill the system

even when we set (α, β) = (0, 0.05).

VIII. CONCLUDING REMARKS

We have investigated the problem of providing hard

per-packet delay guarantees for multi-hop wireless sen-

Figure 6: The network topology for the half-duplex

path-topology system.

Figure 7: Simulation results for the half-duplex path-

topology system.

sor networks. We have proposed an analytical model

that jointly considers the hard delay guarantees of

packets, the multi-hop routing tree of the network,

the timely-throughput requirements of flows, and the

unreliable nature of wireless transmissions. The model

can be applied for both full-duplex systems and half-

duplex systems. We have then introduced a framework

for designing feasibility-optimal scheduling policies for

different types of systems. Based on this framework, we

have proposed a distributed scheduling policy for full-

duplex systems and proved that this policy is feasibility-

optimal. We have also proposed a heuristic for half-

duplex systems. We have proved that this heuristic is

feasibility-optimal for all path-topology systems. Simu-

lation results have suggested that our proposed policies

achieve much better performance than other policies.

REFERENCES

[1] I. Stoianov, L. Nachman, S. Madden, and T. Tokmouline,

“Pipenet: A wireless sensor network for pipeline moni-

toring,” in Proc. of ACM IPSN, pp. 264–273, 2007.

[2] S. Oh, P. Chen, M. Manzo, and S. Sastry, “Instrumenting

wireless sensor networks for real-time surveillance,” in

Proc. of IEEE ICRA, pp. 3128–3133, 2006.

[3] X. Zhu, S. Han, P.-C. Huang, A. K. Mok, and D. Chen,

“Mbstar : A real-time communication protocol for wire-

less body area networks,” in Proc. of ECRTS, pp. 57–66,

2011.

[4] P. Jayachandran and T. Abdelzaher, “Transforming dis-

tributed acyclic systems into equivalent uniprocessors

under preemptive and non-preemptive scheduling,” in

Proc. of ECRTS, pp. 233–242, 2008.

[5] S. Hong, T. Chantem, and X. S. Hu, “Meeting end-to-

end deadlines through distributed local deadline assign-

ments,” in Proc. of IEEE RTSS, pp. 183–192, 2011.

[6] R. Li and A. Eryilmaz, “Scheduling for end-to-end

deadline-constrained traffic with reliability requirements

in multi-hop networks,” in Proc. of IEEE INFOCOM,

pp. 3065–3073, 2011.

[7] V. Rodoplu, S. Vadvalkar, A. A. Gohari, and J. J. Shynk,

“Empirical modeling and estimation of end-to-end voip

delay over mobile multi-hop wireless networks,” in Proc.

of IEEE Globecom, 2010.

[8] H. Li, Y. Cheng, C. Zhou, and W. Zhuang, “Minimizing

end-to-end delay: A novel routing metric for multi-radio

wireless mesh networks,” in Proc. of IEEE INFOCOM,

pp. 46–54, 2009.

[9] P. Jayachandran and M. Andrews, “Minimizing end-to-

end delay in wireless networks using a coordinated edf

schedule,” in Proc. of IEEE INFOCOM, 2010.

[10] H. Li, X. Liu, W. He, J. Li, and W. Dou, “End-to-end delay

analysis in wireless network coding: A network calculus-

based approach,” in Proc. of IEEE ICDCS, pp. 47–56,

2011.

[11] J. Li, Z. Li, and P. Mohapatra, “Adaptive per hop dif-

ferentiation for end-to-end delay assurance in multihop

wireless networks,” Ad Hoc Networks, vol. 7, Aug. 2009.

[12] B. Jiang, B. Ravindran, and H. Cho, “On real-time ca-

pacity of event-driven data-gathering sensor networks,”

in Proc. of ACM MobiQuitous, 2009.

[13] X. Wang, X. Wang, G. Xing, and Y. Yao, “Dynamic duty

cycle control for end-to-end delay guarantees in wireless

sensor networks,” in Proc. of IEEE IWQoS, 2010.

[14] O. Chipara, C. Wu, C. Lu, and W. Griswold,

“Interference-aware real-time flow scheduling for

wireless sensor networks,” in Proc. of ECRTS, pp. 67–77,

2011.

[15] Y. Wang, M. C. Vuran, and S. Goddard, “Cross-layer

analysis of the end-to-end delay distribution in wireless

sensor networks,” in Proc. of IEEE RTSS, pp. 138–147,

2009.

[16] Q. Wang, P. Fan, D. O. Wu, and K. B. Letaief, “End-to-end

delay constrained routing and scheduling for wireless

sensor networks,” in Proc. of IEEE ICC, 2011.

[17] H. Li, P. Shenoy, and K. Ramamritham, “Scheduling

messages with deadlines in multi-hop real-time sensor

networks,” in Proc. of IEEE RTAS, pp. 415 – 425, 2005.

[18] I.-H. Hou, V. Borkar, and P. R. Kumar, “A theory of QoS

for wireless,” in Proc. of INFOCOM, pp. 486–494, 2009.

[19] J. Al-Karaki and A. Kamal, “Routing techniques in wire-

less sensor networks: a survey,” IEEE Wireless Communi-

cations, vol. 11, pp. 6–28, Dec. 2004.

[20] I.-H. Hou and P. R. Kumar, “Scheduling heterogeneous

real-time traffic over fading wireless channels,” in Proc.

of IEEE INFOCOM, 2010.