Robotic Message Ferrying for Wireless Networks using Coarse-Grained
Backpressure Control
Shangxing Wang
Dept. of Electrical Engineering,
University of Southern California,
Los Angeles, CA
Email: shangxiw@usc.edu
Andrea Gasparri
Department of Engineering
Roma Tre University
Rome, Italy
Email: gasparri@dia.uniroma3.it
Bhaskar Krishnamachari
Dept. of Electrical Engineering,
University of Southern California,
Los Angeles, CA
Email: bkrishna@usc.edu
Abstract—We formulate the problem of robots ferrying mes-
sages between statically-placed source and sink pairs that they
can communicate with wirelessly. We ﬁrst analyze the capacity
region for this problem under both ideal (arbitrarily high velocity,
long scheduling periods) and realistic conditions. We indicate
how robots could be scheduled optimally to satisfy any arrival
rate in the capacity region, given prior knowledge about arrival
rates. We ﬁnd that if the number of robots allocated grows
proportionally with the number of source-sink pairs, then the
capacity of the network scales as Θ(1), similar to what was
shown previously by Grossglauser and Tse for uncontrolled
mobility; however, in contrast to that prior result, we also ﬁnd
that with controlled mobility this constant capacity scaling can
be obtained while ensuring ﬁnite delay. We then consider the
setting where the arrival rates are unknown and present a coarse-
grained backpressure message ferrying algorithm (CBMF) for it.
In CBMF, the robots are matched to sources and sinks once
every epoch to maximize a queue-differential-based weight. The
matching controls both motion and transmission for each robot:
if a robot is matched to a source, it moves towards that source
and collects data from it; and if it is matched to a sink, it moves
towards that sink and transmits data to it. We show through
analysis and simulations the conditions under which CBMF can
stabilize the network. We show that the maximum achievable
stable throughput with this policy tends to the ideal capacity as
the schedule duration and robot velocity increase.
I.
INTRODUCTION
Since the work by Tse and Grossglauser [1], it has been
known that the use of delay tolerant mobile communications
can dramatically increase the capacity of wireless networks by
providing ideal constant throughput scaling with network size
at the expense of delay. However, nearly all the work to date
has focused on message ferrying in intermittently connected
mobile networks where the mobility is either unpredictable,
or predictable but uncontrollable. With the rapidly growing
interest in multi-robot systems, we are entering an era where
the position of network elements can be explicitly controlled
in order to improve communication performance.
This paper explores the fundamental limits of robotically
controlled message ferrying in a wireless network. We consider
a setting in which a set of K pairs of static wireless nodes act
as sources and sinks that communicate not directly with each
other (possibly because they are located far from each other
and hence cannot communicate with each other at sufﬁciently
high rates) but through a set of N controllable robots. We
assume that there is a centralized control plane (which, because
it collects only queue state information about all network
entities, can be relatively inexpensively created either using
infrastructure such as cellular / WiFi, or through a low-rate
multi-hopping mesh overlay).
We mathematically characterize the capacity region of this
system, considering both ideal (arbitrarily large) and realistic
(ﬁnite) settings with respect to robot mobility and scheduling
durations. This analysis shows that with N = 2K robots the
system could be made to operate at full capacity (effectively at
the same throughput as if all sources and sinks were adjacent
to each other). We indicate how any trafﬁc that is within
the capacity region of this network can be served stably if
the data arrival rates are known to the scheduler. We then
consider how to schedule the robots when the arrival rates are
not known a priori. For this case, we propose and evaluate
a queue-backpressure based algorithm for message ferrying
that is coarse-grained in the sense that robot motion and
relaying decisions are made once every ﬁxed-duration epoch.
We show that as the epoch duration and velocity of robots both
increase, the throughput performance of this algorithm rapidly
approaches that of the ideal case.
II.
PROBLEM FORMULATION
There are K pairs of static source and destination nodes
located at arbitrary locations. Let the source for the ith ﬂow
be denoted as src(i), and the destination or sink for that ﬂow
be denoted as sink(i). Source i receives packets at a constant
rate denoted by λi.
There are N ≤2K mobile robotic nodes that act as
message ferries, i.e. when they talk to a source node, they
can collect packets from it, and when they talk to a sink node,
they can transmit packets to it. Furthermore, for simplicity, we
assume that the static nodes do not communicate directly with
each other, but rather only through the mobile robots.
Time is divided into discrete time steps of unit duration.
The locations of the sources and sinks for ﬂow i are denoted
by xsrc(i) and xsink(i) respectively, and the location of robot
j at time t is denoted as xj(t). Let the distance between a
source for ﬂow i and a robot j be denoted as d(xsrc(i), xj(t))
(similarly for the sink). When in motion, the robotic nodes
move with a uniform velocity v directly to the destination
(there are no obstacles), so that if robot j is moving towards
the source for ﬂow i, its position xj(t) is updated so that it
moves along the vector between its previous position and the
source location to be at the following distance:
d(xsrc(i), xj(t + 1)) = max{d(xsrc(i), xj(t)) −v, 0}
(1)
arXiv:1308.2923v1  [cs.NI]  13 Aug 2013
source	  1 
sink	  1 
source	  2 
sink	  2 
robot	  3 
robot	  4 
robot	  2 
robot	  1 
ﬂow	  1 
ﬂow	  2 
Fig. 1.
A network containing 2 pairs of source and sink nodes and 4 robots
We assume that the rate at which a source for ﬂow i
can transmit to a robot j, denoted by Rsrc(i),j(t) is always
strictly positive, and decreases monotonically with the distance
between them, and similarly for the rate at which a robot j can
transmit to the sink for ﬂow i, denoted by Rj,sink(i)(t). We
assume that when the robot is at a location of a particular
source or sink, (i.e., the distance between them is 0), the
corresponding throughput between the mobile robot and that
source or sink is Rmax
The queue at the source for ﬂow i is denoted as Qsrc(i). It
is assumed that there is no queue at the sinks as they directly
consume all packets intended for them. Each robot j maintains
a separate queue for each ﬂow i, labelled Qi
j. Figure 1 shows
an illustration of this system with K = 2 ﬂows and N = 4
robots.
Every T time steps there is a new epoch. At the start of
each epoch, it is assumed that the information about queue
states of all source and sink nodes as well as all queues at each
of the robots is made available to a centralized scheduler. At
that time this centralized scheduler can use this information
to match each robot to either a source or sink. The matching
is represented by an allocation matrix A such that A(i, j) is
0 if the robot j is not allocated to either source or sink for
ﬂow i, 1 if it is allocated to src(i), and −1 if it is allocated
to sink(i). When a robot is allocated to a given source (or
sink), for the rest of that epoch it moves closer to that node
until it reaches its position. At all time steps of that epoch that
robot will communicate exclusively with that source (or sink)
to pick up (or drop, in case of the sink) any available packets
between the corresponding queues at a rate depending on its
current distance to that node.
If a robot j is communicating with src(i) at time t, the
update equations for the corresponding queue of the robot and
the source queue will be as follows:
np(t) = min{Rsrc(i),j(t), Qsrc(i)(t)}
Qi
j(t + 1) = Qi
j(t + 1) + np(t)
Qsrc(i)(t + 1) = Qsrc(i)(t + 1) −np(t) + λi
.
(2)
Similarly, if the robot j is communicating with sink(i) at
time t, the queue update equation for the robot’s corresponding
queue will be:
np(t) = min{Rj,sink(i)(t), Qi
j(t)}
Qi
j(t + 1) = Qi
j(t + 1) −np(t)
.
(3)
III.
CAPACITY ANALYSIS
We deﬁne an open region Λ of arrival rates as follows:
Λ =
(
λ|0 ≤λi < Rmax,
∀i,
K
X
i=1
λi < Rmax N
2
)
. (4)
We shall show that this arrival rate region Λ can be served
by a convex combination of conﬁgurations in which robots are
allocated to serve distinct ﬂows. Let ˜Γ be a ﬁnite set of vectors
deﬁned as:
˜Γ =
(
γ|γi = ai Rmax
2
,
∀i, ai ∈{0, 1, 2},
K
X
i=1
ai ≤N
)
.
(5)
For each element of this set ˜Γ, the corresponding integer
vector a corresponds to a “basis” allocation of robots to
distinct sources and sinks that can service each ﬂow at rate γi.
Speciﬁcally, ai refers to the number of robots allocated to serve
ﬂow i. If ai = 1, this means exactly one robot is allocated to
ﬂow i, and can serve this ﬂow maximally by spending half its
time near the source and half the time near the sink (ignoring
for now the time spent in transit), yielding a maximum service
rate of γi = Rmax/2. If two robots are allocated to a ﬂow i, we
have that ai = 2, in which case two robots take turns spending
time at the source and sink of the ﬂow respectively for half the
time each, yielding a net rate of γi = Rmax. The constraints
on ai ensure that the total number of robots allocated does not
exceed the available number N.
Let us refer to the convex hull of ˜Γ as H(˜Γ) or, for
readability, simply H.
Lemma 1: H ⊃Λ
Proof: First, note that the convex hull of ˜Γ can be written
as follows:
H =
(
γ|γi = ai Rmax
2
, ai ∈[0, 2]
∀i,
K
X
i=1
ai ≤N
)
. (6)
In other words, the convex hull of the set ˜Γ is obtained by
allowing ai to vary continuously. Now using the relationship
ai =
2γi
Rmax
, we can re-express H as follows:
H =
(
γ| 2γi
Rmax
∈[0, 2] ∀i,
K
X
i=1
2γi
Rmax
≤N
)
=
(
γ|0 ≤γi ≤Rmax ∀i,
K
X
i=1
γi ≤RmaxN
2
)
⊃Λ
.
Each basis allocation corresponding to the elements of
˜Γ can actually be expressed as two distinct but symmetric
allocations of robots to sources/sinks over two successive
epochs. For the ith ﬂow, if ai = 0, there is no robot allocated
to either the source or sink in either of these two epochs; if
ai = 1, a particular robot is assigned to be at the source at
the ﬁrst epoch and at the sink at the second epoch; if ai = 2,
two robots are assigned (call them R1 and R2) such that R1
is at the source at the ﬁrst epoch and at the sink at the second
epoch while R2 is at the sink at the ﬁrst epoch and at the
source at the second epoch.
The set H describes all possible robot service rates that can
be obtained by a convex combination of these basis allocations.
Consider a rate vector γ ∈H. Since it lies in the convex
hull of the set ˜Γ it can be described in terms of a vector
of convex coefﬁcients α each of whose elements corresponds
to a basis allocation of robots. We can therefore1 identify ni
such that ni/P
i
ni = αi. The given rate vector γ can then be
scheduled by allocating ni epochs each for the two parts of
the ith basis allocation. And after a total of P
i
2ni epochs, the
whole schedule can be repeated. This schedule will provide
the desired service rate vector γ.
Thus far the schedules have been derived under the assump-
tion of instantaneous robot movements. Now we consider the
effect of transit time. It is possible to choose T or v to be
sufﬁciently large to bound the fraction of time spent in transit
by ϵ, i.e.
d
vT < ϵ. Thus even while taking into account time
wasted in transit, we can scale either time period of the epochs
T or the velocity v so as to provide a service rate vector γ′
that is arbitrarily close to any ideal service rate γ in the sense
that γi −γ′
i < ϵ ∀i.
We now state one of our main results:
Theorem 1: Λ is the achievable capacity region of the
network.
Proof: By construction, H represents the boundary of all
feasible robot service rates, and as we have discussed time
spent in transit can be accounted for by increasing T or v so
that any arrival rate that is in the interior of H can be served.
Since in lemma 1, we have already shown that Λ ⊂H, any
arrival rate in Λ can be stably served.
Furthermore, H represents the closure of the open set Λ.
Thus any arrival rate vector that is a bounded distance outside
of Λ cannot be served stably (as it would also be outside of
H).
Together, these imply that Λ is the achieveable capacity
region of the network.
A. An Example
Figure 2 shows the capacity region when K = 2, N = 3.
The labels such as (x, y) are given to the basis allocations
on the Pareto boundary to denote that they can be achieved
by allocating an integer number of robots x to ﬂow 1 and y
to ﬂow 2. Note in particular that the point (Rmax, Rmax) is
outside the region in this case because the only way to serve
that rate is to allocate two robots full time to each of the two
ﬂows, and we have only 3 robots. The vertices on the boundary
1Here, for ease of exposition, we are assuming that αi is rational, otherwise
it can be approximated by an arbitrarily close rational number which will not
affect the overall result.
Fig. 2.
Capacity region for a problem with 3 robots and 2 ﬂows
of the region, which represent basis allocations, are all in the
set ˜Γ; the convex hull of ˜Γ completely describes the region.
B. Θ(1) Capacity Scaling with Controlled Mobility
In [1], Grossglauser and Tse ﬁrst showed that in a network
with uncontrolled mobility, under certain mixing conditions,
a total capacity of Θ(1) could be achieved by using one
intermediate relay node. Our modeling in this paper shows
that the total capacity region scales linearly with the number
of robotic relays. Therefore, when the number of robots is
linear in the number of ﬂows, the per-pair network capacity
will be Θ(1) here as well.
There are a few minor differences between the model in this
paper and what is considered in [1], however these differences
are not consequential, as they affect only constants in the
asymptotic scaling:
•
In [1] it is assumed that all nodes are mobile. In our
setting, ﬁrst note that if the source and sink nodes
were controllably mobile, then they could each be
simply paired up directly and moved arbitrarily close
to each other, and we would achieve Θ(1) scaling
without even needing the controllable relays. Even if
the source and sink were randomly moving, if they
do so within a bounded region in such a way that the
controllable robots could always locate and move to
them within a ﬁnite time, our results would be remain
unaffected.
•
In [1] it is assumed that each source/sink node is a
source for one ﬂow and a sink for another. Making
the same assumption in our model for the static nodes
would merely double the number of ﬂows, and would
result only in a constant factor difference.
•
For ease of exposition and analysis, in our work we
have assumed that robots do not interfere with each
other at any time. However, for deriving the capacity
region, it sufﬁces to assume that the robots do not
interfere with each other whenever they are arbitrarily
close to the source/sink they are communicating with.
This is consonant with the modeling and result in [1]
that when nodes are sufﬁciently close to each other
they may communicate without experiencing interfer-
ence from any number of other distant transmitters.
Finally, in [1], the Θ(1) capacity is obtained at the cost
of average delay increasing with the size of the network. In
stark contrast, in our formulation, as we discuss below, it is
still possible to obtain a constant fraction of the full capacity
(hence still maintaining the Θ(1) capacity scaling) even while
keeping the delay bounded.
C. Capacity Region under ﬁnite velocity and epoch duration
The analysis thus far assumes that either the velocity
of the robot or the epoch duration can be chosen to be
arbitrarily large. Next, motivated by practical considerations
we consider the case when v and T are ﬁnite. In particular,
the restriction of T to be ﬁnite is useful for two reasons: a)
it ﬁxes the overhead of scheduling and b) it can be used
to enforce a deterministic upper bound on delay (the time
between generation and delivery of a given packet). As may
be expected, these constraints reduce the capacity region.
The fraction of time spent in transit, is bounded by
d
vT ,
where d is the maximum distance between the static nodes. We
assume that
d
vT < 1, which implies that a robot can always
reach its destination (source or sink) within an epoch.
This directly yields the following inner-bound on the
capacity region when v and T are ﬁnite and ﬁxed:
ΛIB(v, T) =

λ|0 ≤λi < Rmax(1 −d
vT ),
∀i,
K
X
i=1
λi < Rmax(1 −
d
vT ) N
2
.
(7)
Remark 1: Any arrival rate in the inner-bound region can
still be achieved while scheduling them this way. As the
inner bound is only a constant factor away from the full
capacity region, this shows that a capacity scaling of Θ(1)
can be achieved with controllable mobility even while keeping
average delay to be bounded. This is in contrast to what
happens with opportunistic mobility [1] where a constant
capacity scaling is obtained at the cost of unbounded delay.
Note further that when the number of robots N = 2K, it is
possible to schedule the robots for each ﬂow in alternate cycles
so that even the worst case delay is bounded deterministically
by 2T.
IV.
COARSE-GRAINED BACKPRESSURE CONTROL
From the previous discussion, we know that if the arrival
rate of each ﬂow is known, and within the ideal capacity region
of the system, the epoch duration and a service schedule for the
robots can be designed in such a way that the rate is served in
a stable manner (maintaining the average size of each queue to
be bounded). We consider now the case when the arrival rates
are within the capacity region but not known to the scheduling
algorithm, and the v and T parameters are kept ﬁxed. Is it still
possible to schedule the movement and communications of the
robots in such a way that all queues remain stable?
The answer to this question turns out to be yes, using the
notion of Backpressure scheduling ﬁrst proposed by Tassiulas
and Ephremides [2]. We propose an algorithm for scheduling
message ferrying robots that achieves throughput-optimal per-
formance for ﬁnite v and T parameters, which we refer to as
coarse-grained backpressure-based message ferrying (CBMF).
The CBMF algorithm works as follows.
At the beginning of each epoch:
•
compute the weights wsrc(i),j = (Qsrc(i) −Qi
j) and
wsink(i),j = (Qi
j).
•
If the allocation A(i, j) = 1, denote wi,j = wsrc(i),j.
If A(i, j) = −1, denote wi,j = wsink(i),j. Else, if
A(i, j) = 0, wi,j = 0.
•
Find
the
allocation
A
that
maximizes
P
i,j |A(i, j)|wi,j(A(i, j)) subject to the following
three constraints:
(1)
P
i |A(i, j)| = 1,
(2)
P
j I{A(i, j) = 1} ≤1,
(3)
P
j I{A(i, j) = −1} ≤1.
The ﬁrst constraint ensures that each robot is allocated
to exactly one source or sink. The second constraint
(I{} represents the indicator function) ensures that
no source is allocated more than one robot, while the
third constraint ensures that no sink is allocated more
than one robot.
Theorem 2: For any arrival rate that is strictly within
ΛIB(v, T), the CBMF algorithm ensures that all source and
robot queues are stable (always bounded by a ﬁnite value).
Proof: The proof essentially follows the treatment in [?].
Since the arrival rate is strictly interior in ΛIB(v, T), we
can make some simple assumptions. We ignore data transmit-
ted when robots are moving. And at the beginning of each
epoch, once the robots are allocated, they move instantly to
their destinations(sources or sinks) and remain static with a
constant transmission rate as R′
max = Rmax(1 −
d
vT ).
Let bij(t) denote whether robot j is allocated to src(i) or
not. bij(t) = 1 means robot j is allocated to src(i); bij(t) =
0 means robot j is not allocated to src(i). Similarly, cij(t)
denotes whether robot j is allocated to sink(i) or not. cij(t) =
1 means robot j is allocated to sink(i), and cij(t) = 0 means
robot j is not allocated to sink(i). Then we have Rsrc(i),j(t) =
bij(t)R′
max and Rj,sink(i)(t) = cij(t)R′
max.
The queue backlog at source i, ∀i ∈{1, ..., K}, is updated
as follows
Qsrc(i)(t+1)=max

Qsrc(i)(t) −(bi1(t) + ... + biN(t))R′
max, 0
	
+λi.
(8)
The queue backlog at robot j for ﬂow i, ∀i ∈1, ..., K and
j ∈1, ..., N, is given by
Qi
j(t + 1)=max
n
Qi
j(t) −cij(t)R′
max, 0
o
+min

Qsrc(i)(t), bij(t)R′
max
	
.
(9)
Deﬁne the queue backlog vector of this system as
Θ(t)=(Qsrc(1)(t), ..., Qsrc(K)(t), Q1
1(t), ..., QK
1 (t), ..., Q1
N(t), ..., QK
N (t)).
(10)
And the Lyapunov function as
L(Θ(t)) = 1
2


K
X
i=1
Qsrc(i)(t)2 +
K
X
i=1
N
X
j=1
Qi
j(t)2

.
(11)
Then ,
L(Θ(t + 1))−L(Θ(t))
=1
2
( K
X
i=1

Qsrc(i)(t + 1)2 −Qsrc(i)(t)2
)
+1
2



K
X
i=1
N
X
j=1

Qi
j(t + 1)2 −Qi
j(t)2



⩽
K
X
i=1
(
N
P
j=1
bij(t)R′
max)2 + λ2
i
2
+
K
X
i=1
N
X
j=1
(cij(t)R′
max)2 + (bij(t)R′
max)2
2
+
K
X
i=1
Qsrc(i)(t)

λi −
N
X
j=1
bij(t)R′
max)


+
K
X
i=1
N
X
j=1
Qi
j(bij(t) −cij(t))R′
max.
(12)
where the inequality comes from equations (8) and (9), and
max {Q −b, 0} + a ⩽Q2 + a2 + b2 + 2Q(a −b).
(13)
max {Q1 −c, 0} + min {Q2, b} ⩽max {Q1 −c, 0} + b.
(14)
Deﬁne the conditional Lyapunov drift as
△(Θ(t)) = E {L(Θ(t + 1)) −L(Θ(t))|Θ(t)} .
(15)
Since
∀i
∈
{1, ..., K}
and
∀j
∈
{1, ..., N},
bij(t)R′
max ⩽Rmax, cij(t)R′
max ⩽R′
max and the arrival
rates are ﬁnite, the ﬁrst two terms on the left-hand-side of
inequality (15) can be upper bounded by a ﬁnite constant B.
Thus,
△(Θ(t))
⩽B +
K
X
i=1
Qsrc(i)(t)λi
−
K
X
i=1
N
X
j=1
E
n
(Qsrc(i)(t)−Qi
j(t))bij(t)R′
max+Qi
j(t)cij(t)R′
max|Θ(t)
o
.
(16)
Applying the CBMF algorithm to allocate robots, the
last term on the right-hand-side can be maximized, thus the
conditional drift can be minimized. Let b∗
ij(t) and c∗
ij(t) be
any other robot allocation policy, then we have
△(Θ(t))
⩽B +
K
X
i=1
Qsrc(i)(t)λi
−
K
X
i=1
N
X
j=1
E
n
(Qsrc(i)(t)−Qi
j(t))b∗
ij(t)R′
max+Qi
j(t)c∗
ij(t)R′
max|Θ(t)
o
⩽B−
K
X
i=1
Qsrc(i)(t)
 
E
( N
X
j=1
b∗
ij(t)R′
max|Θ(t)
)
−λi
!
−
K
X
i=1
N
X
j=1
Qi
j(t)E
 c∗
ij(t) −b∗
ij(t)

R′
max|Θ(t)
	
.
(17)
In order to upper bound the terms on the right-hand-side,
let us ﬁrst consider the following problem: given an arrival
rate vector λ = (λ1, ..., λK) ∈ΛIB(v, T) a priori, we want
to design an S-only (depends only on the channel states)
algorithm to
ﬁnd
ϵ > 0
s.t.
λi + ϵ ⩽E



N
X
j=1
b∗
ij(t)R′
max



∀i ∈{1, ..., K},
E

b∗
ij(t)R′
max
	
+ ϵ ⩽E

c∗
ij(t)R′
max
	
,
∀i ∈{1, ..., K}
and
∀j ∈{1, ..., N}.
(18)
The S-only algorithm to achieve any given arrival rates
which are strictly interior to the capacity region is designed as
follows:
Since λ = (λ1, ..., λK) ∈H/∂H, we can ﬁnd a vector
ϵ = (ϵ1, ..., ϵK) such that λ′ = (λ1 + ϵ1, ..., λK + ϵK) ∈∂H.
Let ϵmax = min{ϵ1, ..., ϵK}, and since λ is strictly interior in
H, we have ϵmax > 0.
Since λ′′ = (λ1 + ϵmax, ..., λK + ϵmax) ∈H, it can be
represented as a convex combination of basis allocations. To be
speciﬁc, in a network containing K ﬂows and N robots, there
are M (depends on K and N, and is ﬁnite) basis allocations in
total. Let [λl1, ..., λlK]T , ∀l ∈{1, ..., M} denote the capacity
the lth allocation can provide. Let α = (α1, ..., αM) be the
allocation vector of the convex coefﬁcients. And we have
α1[λ11, ..., λ1K]T + ... + αM[λM1, ..., λMK]T
=[λ1 + ϵmax, ..., λK + ϵmax]T .
(19)
Let us identify integers nl satisfying
nl
M
P
i=1
ni
= αl, ∀l ∈
{1, ..., M}. Then the arrival rate vector λ′′ can be served
by ﬁrst allocating nl epochs for the lth basis allocation, and
allocating the next nl epochs for the same lth basis allocation
but exchanging the robots locations, ∀l ∈{1, ..., M}. And after
a total of 2
M
P
l=1
nl epochs, repeat the whole process.
Since the served rate λ′′ is ϵmax greater than the original
given rate λ, we can change the above scheduling scheme by
adding a few more epochs to each 2 P
l
nl epochs period, which
still supports the given input rate. During these additional
epochs, we can evenly allocate one robot at each sink to help
deliver data. In this way we can make sure there exists an
ϵ′ > 0 such that
λi + ϵ′ ⩽E
( N
X
j=1
b∗
ij(t)R′
max
)
, ∀i ∈{1, ..., K},
E

b∗
ij(t)R′
max
	
+ ϵ′ ⩽E

c∗
ij(t)R′
max
	
,
∀i ∈{1, ..., K} and ∀j ∈{1, ..., N}.
(20)
Take inequalities (20) into equation (17), we have
△(Θ(t)) ⩽B −ϵ′


K
X
i=1
Qsrc(i)(t) +
K
X
i=1
N
X
j=1
Qi
j(t)

. (21)
Taking iterated expectations, summing the telescoping se-
ries, and rearranging terms yields:
1
t
t−1
X
τ=0


K
X
i=1
E

Qsrc(i)(τ)
	
+
K
X
i=1
N
X
j=1
E

Qi
j(τ)
	


⩽B
ϵ′ + E{L(Θ(0))}
ϵ′t
.
(22)
Therefore,
lim
t→∞
1
t
t−1
X
τ=0


K
X
i=1
E

Qsrc(i)(τ)
	
+
K
X
i=1
N
X
j=1
E

Qi
j(τ)
	

⩽B
ϵ′ ,
(23)
which indicates that the system is strongly stable.
Remark 2: CBMF is provably stable for all arrival rates up
to the inner-bound. However, as v and T increase, the inner-
bound approaches the ideal capacity region.
V.
DELAY ANALYSIS FOR SINGLE-FLOW TWO-ROBOTS
Consider a system which contains one source S, one sink
D, and two robots R1, R2. Initially, their queue backlogs are
empty. The distance between source and sink is d. R1 is at the
same location as D, and R2 is at the same location as S. The
moving speeds of robots is v. The transmission rate function
is R(x).
Without loss of generality, we assume that after applying
CFBP at the beginning of the ﬁrst epoch, R1 (called receiving
robot) is allocated to S to receive data, and R2 (called
delivering robot) is allocated to D to deliver data. Thus, in the
ﬁrst epoch, R1 moves towards the source and keep receiving
data. Since R2 doesn’t have any data stored in its queue, it
just moves to the destination without delivering data. At the
end of this epoch, Qs = 0, QR1 = λT and QR2 = 0.
In the second epoch, after applying CFBP, R1 will be
allocated to the destination to deliver data, and R2 will
be allocated to the source to receive data. Applying CFBP
algorithm at the begging of each epoch, this whole process
repeats every two epochs in the ﬂowing epochs.
Since we focus on the stable state of the system in the
long run, we can ignore the ﬁrst epoch. What’s more, the
system evolves all the same in the following epochs except
for changing the roles of R1 and R2(In one epoch, one is the
receiving robot and the other is the delivering robot; In the
next epoch, the other way around.). Thus, we can analyze one
particular epoch instead. Let us focus on the second epoch. At
the beginning of this epoch, queues at source S and robot R2
are both empty, and queue at R1 is λT. According to the CFBP
algorithm, in the second epoch, robot R1 is the delivering robot
moving towards the sink and deliver data; and robot R2 is the
receiving robot moving towards the source to receive data.
Depending on different values of arrival rate λ, the system
evolves as one the following two cases.
Case 1: when arrival rate λ is small enough so that the
delivering robot R1 can deplete all its packets before reaching
the sink. Let’s t∗
1 be the time when the queue at R1 is empty.
Then, λT −
R t∗
1
0 R(d −vt)dt = 0, and t∗
1 ⩽
d
v. Note the
condition t∗
1 ⩽d
v also provides an upper bound ˆλmax for the
input rate in this case.
1) When 0 ⩽t1 ⩽t∗
1, the delivering robot R1 has data in
its backlog and keeps transmitting data to D. Thus, its queue
at time t1 is QR1(t1) = λT −
R t1
0 R(d −vt)dt. At the same
time, new data arrives at the source node S at rate λ, and
the receiving robot R2 keeps receiving data from S. The total
amount of data at S and R2 at t1 is Qs(t1) + QR2(t1) = λt1.
Thus, the total queue backlog in the system at t1 is
Qtot(t1) = Qs(t1)+QR1(t1)+QR2(t1) = λT−
Z t1
0
R(d−vt)dt+λt1.
(24)
2) When t∗
1 < t1 ⩽T, the delivering robot R1 has no data
to transmit, thus QR1(t1) = 0. The total amount of data at S
and R2 at t1 is still Qs(t1) + QR2(t1) = λt1. Thus, the total
queue backlog in the system at t1 is
Qtot(t1) = λt1.
(25)
By
deﬁnition,
the
time
average
total
queue
is
¯Qtot = 1
T
R T
0 Q(τ)dτ. Then, we have
¯Qtot = 1
T
(Z t∗
1
0

λT−
Z τ
0
R(d −vt)dt+λτ

dτ +
Z T
t∗
1
λτdτ
)
= λt∗
1 + λT
2 −1
T
Z t∗
1
0
Z τ
0
R(d −vt)dt

dτ.
(26)
And by Little’s Law, the time average delay of this system
is
¯D =
¯Qtot
λ
= t∗
1 + T
2 −1
λT
Z t∗
1
0
Z τ
0
R(d −vt)dt

dτ. (27)
Case 2: when arrival rate λ (ˆλmax < λ < λmax) is large
enough so that the delivering robot R1 cannot ﬁnish depleting
all its data during moving, i.e., it will keep downloading
data at rate Rmax while it reaches the destination. Let t∗
2
be the time when the queue backlog at R1 is empty. Then,
λT −
nR d
v
0 R(d −vt)dt + (t∗
2 −d
v)Rmax
o
= 0. Note t∗
2 ⩽T
also provides the upper bound capacity λmax for the stable
system. (where λmax = Ravg =
R d
v
0
R(d−vt)dt+(T −d
v )Rmax
T
)
1) When 0 ⩽t1 ⩽d
v, the delivering robot R1 keeps moving
towards D while transmitting data. Its queue backlog at t1 is
QR1(t1) = λT −
R t1
0 R(d −vt)dt. The queue at source S and
receiving robot R2 at time t1 is Qs(t1) + QR2(t1) = λt1.
Thus, the total queue backlog in the system at t1 is
Qtot(t1) = Qs(t1) + QR1(t1) + QR2(t1)
= λT −
Z t1
0
R(d −vt)dt + λt1.
(28)
2) When
d
v < t1 ⩽t∗
2, delivering robot R1 stays at the
same location with sink D and keeps delivering data at the
maximum rate Rmax. Then its queue at t1 is R1(t1) = λT −
R d
v
0 R(d −vt)dt −(t1 −d
v)Rmax. The queue at S and R2 is
Qs(t1) + QR2(t1) = λt1. Thus, the total queue backlog at t1
is
Qtot(t1) = λT −
Z
d
v
0
R(d−vt)dt−(t1−d
v )Rmax+λt1. (29)
3) When t∗
2 < t1 ⩽T, the delivering robot R1 has already
delivered all its data, thus QR1(t1) = 0. Besides, we still have
Qs(t1) + QR2(t1) = λt1. Thus, the total queue backlog is
Qtot(t1) = λt1.
(30)
Thus,
¯Qtot = 1
T {
Z
d
v
0

λT −
Z τ
0
R(d −vt)dt + λτ

dτ
+
Z t∗
2
d
v
(
λT −
Z
d
v
0
R(d −vt)dt −(τ −d
v )Rmax + λτ
)
dτ
+
Z T
t∗
2
λτdτ}
= λt∗
2 + λT
2 −1
T
Z
d
v
0
Z τ
0
R(d −vt)dt

dτ
−1
T (t∗
2 −d
v )
Z
d
v
0
R(d −vt)dt −Rmax
2T
(t∗
2 −d
v )2.
(31)
and
¯D =
¯Qtot
λ
= t∗
2 + T
2 −1
λT
Z
d
v
0
Z τ
0
R(d −vt)dt

dτ
−
1
λT (t∗
2 −d
v )
Z
d
v
0
R(d −vt)dt −Rmax
2λT (t∗
2 −d
v )2.
(32)
VI.
SIMULATIONS
We ﬁrst present numerical simulation results for two ﬂows
and four robots. We use η = 2, C = 1, d1 = 25, d2 = 100, v
and T and λi are varied as shown in the ﬁgures. In ﬁgure 3
we see the average end-to-end delay (time taken for a packet
generated at the source to reach the sink; it is obtained by
measuring the average total queue size for each ﬂow in the
simulations and dividing by the arrival rate, as per Little’s
Theorem [3]) versus arrival rate for each ﬂow, plotted wherever
CBMF results in stable queues; we ﬁnd that we are able to
get converging, bounded delays (indicative of stability) even
beyond the inner-bound capacity line. Also marked on the
ﬁgure is the lower (inner) bound of capacity, for rates below
which CBMF is provably stable. We see that as the velocity
increases, so does the capacity, and at the same time the
delay decreases. Thus improvement in robot velocity beneﬁts
both throughput and delay performance of CBMF, as may
be expected. Figure 4, in which the velocity is kept constant
across curves but the epoch duration is varied, is somewhat
similar but with one striking difference, however, as the epoch
duration increases, so does the capacity; but at the same
time, the average delay also increases (for the same arrival
rates, so long stability is maintained). Thus, increasing the
scheduling epoch duration improves throughput but hurts delay
performance.
Second, we present numerical simulation results for delay
in one-ﬂow two-robots system. We use d = 10, T, v and λ are
varied as shown in Figure 5. As it is shown in Figure 5, the
simulation results match the theoretical results. We can reach
the same conclusion as before: increasing the scheduling epoch
duration improves throughput but hurts delay performance;
however, increasing robot velocities beneﬁts both throughput
and delay performance. Besides, in the Figure 5, delay seems
to be a linear function of the input rate λ. This can be shown
theoretically if we ignore the integral part of equation (27) or
equation (32).
VII.
CONCLUSIONS
This paper has addressed two fundamental questions in
robotic message ferrying for wireless networks: what is the
throughput capacity region of such systems? How can they
be scheduled to ensure stable operation, even without prior
knowledge of arrival rates? There are a number of open
directions suggested by the present work. The ﬁrst is to
improve the CBFM algorithm to support the entire capacity
region without delay inefﬁciency, possibly by adapting the
schedule length based on observed delay or by considering
ﬁner-grained motion control. Finally, we are interested in de-
veloping decentralized scheduling mechanisms that the robots
can implement in a distributed fashion.
REFERENCES
[1]
M. Grossglauser and D. Tse, “Mobility Increases the Capacity of Ad
Hoc Wireless Networks,” IEEE/ACM Trans. on Networking, vol 10, no
4, August 2002.
[2]
L. Tassiulas, A. Ephremides, “Stability properties of constrained queue-
ing systems and scheduling for maximum throughput in multihop radio
networks,” IEEE Transactions on Automatic Control, Vol. 37, No. 12,
pp. 1936-1949, December 1992.
[3]
A. Leon-Garcia, Probability and Random Processes for Electrical Engi-
neering, Addison-Wesley, 1993.
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0
50
100
150
200
250
Input rate λ1
Delay of flow 1
 
 
v=sqrt(2)
capacity inner bound=0.2030
v=4*sqrt(2)
campacity inner bound=0.5706
v=100*sqrt(2)
capacity inner bound=0.6882
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0
50
100
150
200
250
Input rate λ2
Delay of flow 2
 
 
v=sqrt(2)
capacity inner bound=0.5706
v=4*sqrt(2)
capacity inner bound=0.6625
v=100*sqrt(2)
capacity inner bound=0.6910
Fig. 3.
Delay of ﬂows 1 (left) and 2 (right) as we vary v for T = 100
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0
50
100
150
200
250
300
Input rate λ1
Delay of flow 1
 
 
T=25
capacity inner bound=0.2030
T=50
capacity inner bound=4481
T=300
capacity inner bound=6523
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0
50
100
150
200
250
300
Input rate λ2
Delay of flow 2
 
 
T=25
capacity inner bound=5706
T=50
capacity inner bound=6319
T=300
capacity inner bound=6829
Fig. 4.
Delay of ﬂows 1 (left) and 2 (right) as we vary T for v = 4 ∗
√
2
0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0
20
40
60
80
100
120
Input rate λ
Delay
 
 
T=10 in simulation
T=10 in theory
capacity inner bound=0.35
T=20 in simulation
T=20 in theory
capacity inner bound=0.52
T=100 in simulation
T=100 in theory
capacity inner bound=0.66
0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0
5
10
15
Input rate λ
Delay
 
 
v=2 in simulation
v=2 in theory
capacity inner bound=0.35
v=5 in simulation
v=5 in theory
capacity inner bound=0.55
v=10 in simulation
v=10 in theory
capacity inner bound=0.62
Fig. 5.
Delay of one-ﬂow two-robots as we vary T for v = 2 (left) and we vary v for T = 10 (right)
[4]
M. J. Neely, Stochastic Network Optimization with Application to Com-
munication and Queueing Systems, Morgan and Claypool, 2010.