Throughput-Optimal Broadcast in Wireless Networks with
Dynamic Topology
Abhishek Sinha

Leandros Tassiulas

Eytan Modiano

Laboratory for Information and
Decision Systems
MIT

Electrical Engg. and Yale
Institute of Network Science
Yale University

Laboratory for Information and
Decision Systems
MIT

arXiv:1604.00576v1 [] 3 Apr 2016

sinhaa@mit.edu

leandros.tassiulas@yale.edu

ABSTRACT
We consider the problem of throughput-optimal broadcasting in time-varying wireless networks, whose underlying topology is restricted to Directed Acyclic Graphs (DAG). Previous broadcast algorithms route packets along spanning trees.
In large networks with time-varying connectivities, these
trees are difficult to compute and maintain. In this paper
we propose a new online throughput-optimal broadcast algorithm which makes packet-by-packet scheduling and routing decisions, obviating the need for maintaining any global
topological structures, such as spanning-trees. Our algorithm relies on system-state information for making transmission decisions and hence, may be thought of as a generalization of the well-known back-pressure algorithm which
makes point-to-point unicast transmission decisions based
on queue-length information, without requiring knowledge
of end-to-end paths. Technically, the back-pressure algorithm is derived by stochastically stabilizing the networkqueues. However, because of packet-duplications associated
with broadcast, the work-conservation principle is violated
and queuing processes are difficult to define in the broadcast
problem. To address this fundamental issue, we identify certain state-variables which behave like virtual queues in the
broadcast setting. By stochastically stabilizing these virtual queues, we devise a throughput-optimal broadcast policy. We also derive new characterizations of the broadcastcapacity of time-varying wireless DAGs and derive an efficient algorithm to compute the capacity exactly under certain assumptions, and a poly-time approximation algorithm
for computing the capacity under less restrictive assumptions.

1.

INTRODUCTION

The problem of efficiently disseminating packets, arriving
at a source node, to a subset of nodes in a network, is known
as the Multicast problem. In the special case when the packets are to be distributed among all nodes, the corresponding
problem is referred to as the Broadcast problem. Multicast-

ACM ISBN 978-1-4503-2138-9.
DOI: 10.1145/1235

modiano@mit.edu

ing and broadcasting is considered to be a fundamental network functionality, which enjoys numerous practical applications ranging from military communications [16], disaster
management using mobile adhoc networks (MANET) [9], to
streaming services for live web television [24] etc.
There exists a substantial body of literature addressing different aspects of this problem in various networking settings.
An extensive survey of various multicast routing protocols
for MANET is provided in [12]. The authors of [8] consider
the problem of minimum latency broadcast of a finite set of
messages in MANET. This problem is shown to be NP-hard.
To address this issue, several approximation algorithms are
proposed in [11], all of which rely on construction of certain network-wide broadcast-trees. Cross-layer solutions for
multi-hop multicasting in wireless network are given in [29]
and [10]. These algorithms involve network coding, which introduces additional complexity and exacerbates end-to-end
delay. The authors of [21] propose a multicast scheduling
and routing protocol which balances load among a set of
pre-computed spanning trees, which are challenging to compute and maintain in a scalable fashion. The authors of [26]
propose a local control algorithm for broadcasting in a wireless network for the so called scheduling-free model, in which
an oracle is assumed to make interference-free scheduling
decisions. This assumption, as noted by the authors themselves, is not practically viable.
In this paper we build upon the recent work of [23] and consider the problem of throughput-optimal broadcasting in a
wireless network with time-varying connectivity. Throughout the paper, the overall network-topology will be restricted
to a directed acyclic graph (DAG). We first characterize the
broadcast-capacity of time-varying wireless networks and
propose an exact and an approximation algorithm to compute it efficiently. Then we propose a dynamic link-activation
and packet-scheduling algorithm that, unlike any previous
algorithms, obviates the need to maintain any global topological structures, such as spanning trees, yet achieves the
capacity. In addition to throughput-optimality, the proposed algorithm enjoys the attractive property of in-order
packet-delivery, which makes it particularly useful in various
online applications, e.g. VoIP and live multimedia communication [4]. Our algorithm is model-oblivious in the sense that
its operation does not rely on detailed statistics of the random arrival or network-connectivity processes. We also show
that the throughput-optimality of our algorithm is retained
when the control decisions are made using locally available
and possibly imperfect, state information.
Notwithstanding the vast literature on the general topic of

broadcasting, to the best of our knowledge, this is the first
work addressing throughput-optimal broadcasting in timevarying wireless networks with store and forward routing.
Our main technical contributions are the following:
• We define the broadcast-capacity for wireless networks
with time-varying connectivity and characterize it mathematically and algorithmically. We show that broadcastcapacity of time-varying wireless directed acyclic networks can be computed efficiently under some assumptions. We also derive a tight-bound for the capacity
for a general setting and utilize it to derive an efficient
approximation algorithm to compute it.
• We propose a throughput-optimal dynamic routing and
scheduling algorithm for broadcasting in a wireless DAGs
with time-varying connectivity. This algorithm is of
Max-Weight type and uses the idea of in-order delivery to simplify its operation. To the best of our knowledge, this is the first throughput-optimal dynamic algorithm proposed for the broadcast problem in wireless
networks.
• We extend our algorithm to the setting when the nodes
have access to infrequent state updates. We show
that the throughput-optimality of our algorithm is preserved even when the rate of inter-node communication
is made arbitrarily small.
• We illustrate our theoretical findings through illustrative numerical simulations.
The rest of the paper is organized as follows. Section 2
introduces the wireless network model. Section 3 defines
and characterizes the broadcast capacity of a wireless DAG.
It also provides an exact and an approximation algorithm
to compute the broadcast-capacity. Section 4 describes our
capacity-achieving broadcast algorithm for DAG networks.
Section 5 extends the algorithm to the setting of broadcasting with imperfect state information. Section 6 provides numerical simulation results to illustrate our theoretical findings. Finally, in section 7 we summarize our results and
conclude the paper.

2.

NETWORK MODEL

link (i, j) is activated.
Let r ∈ V be the source node. At slot t, A(t) packets arrive
at the source. The arrivals, A(t), are i.i.d. over slots with
mean E(A(t)) = λ. Our problem is to efficiently disseminate
the packets to all nodes in the network.

2.1 Notations and Nomenclature:
All vectors in this paper are assumed to be column vectors.
For any set X ⊂ Rk , its convex-hull is denoted by conv(X ).
Let U, V \ U be a disjoint partition of the set of vertices
V of the graph G, such that the source r ∈ U and U ( V .
Such a partition is called a proper-partition. To each proper
partition corresponding to the set U , associate the propercut vector u ∈ Rm , defined as follows:
ui,j

= ci,j
= 0

if i ∈ U, j ∈ V \ U
otherwise

(1)

Denote the special, single-node proper-cuts by Uj ≡ V \ {j},
and the corresponding cut-vectors by uj , ∀j ∈ V \ {r}. The
set of all proper-cut vectors in the graph G is denoted by U.
The in-neighbours of a node j is defined as the set of all
nodes i ∈ V such that there is a directed edge (i, j) ∈ E. It
is denoted by the set ∂ in (j), i.e.,
∂ in (j) = {i ∈ V : (i, j) ∈ E}

(2)

Similarly, we define the out-neighbours of a node j as follows

∂ out (j) = i ∈ V : (j, i) ∈ E
(3)

For any two vectors x and y in Rm , define the componentwise product z ≡ x ⊙ y to be a vector in Rm such that
zi = xi yi , 1 ≤ i ≤ m.
For any set S ⊂ Rm and any vector v ∈ Rm , v⊙S, denotes
the set of vectors obtained as the component-wise product
of the vector v and the elements of the set S, i.e.,

v ⊙ S = y ∈ Rm : y = v ⊙ s, s ∈ S
(4)
Also, the usual dot product between two vectors x, y ∈
Rm is defined as,
x·y =

m
X

x i yi

i=1

2.2 Model of Time-varying Wireless Connectivity

First we describe the basic wireless network model without time-variation. Subsequently, we will incorporate timevariation in the basic model. A static wireless network is
modeled by a directed graph G = (V, E, c, M), where V is
the set of nodes, E is the set of directed point-to-point links1 ,
the vector c = (cij ) denotes capacities of the edges when
the corresponding links are activated and M ⊂ {0, 1}|E|
is the set of incidence-vectors corresponding to all feasible
link-activations complying with the interference-constraints.
The structure of the activation-set M depends on the interference model, e.g., under the primary or node-exclusive interference model [14], M corresponds to the set of all matchings on the graph G. There are a total of |V | = n nodes and
|E| = m edges in the network. Time is slotted and at timeslot t, any subset of links complying with the underlying
interference-constraint may be activated. At most cij packets can be transmitted in a slot from node i to node j, when

Now we incorporate time-variation into our basic framework described above. In a wireless network, the channelSINRs vary with time because of random fading, shadowing
and mobility [27]. To model this, we consider a simple ONOFF model where an individual link can be in one of the
two states, namely ON and OFF. In an OFF state, the capacity of a link is zero 2 . Thus at a given time, the network
can be in any one configuration, out of the set of all possible
network configurations Ξ. Each element σ ∈ Ξ corresponds
to a sub-graph G(V, Eσ ) ⊂ G(V, E), with Eσ ⊂ E, denoting
the set of links that are ON. At a given time-slot t, one of
the configuration σ(t) ∈ Ξ is realized. The configuration at
time t is represented by the vector σ(t) ∈ {0, 1}|E| , where
(
1, if e ∈ Eσ(t)
σ(e, t) =
0, otherwise.

1
We assume all transmit and receiving antennas to be directed and hence all transmissions to be point-to-point [3].

2
Generalization of the ON-OFF model, to multi-level discretization of link-capacity is straight-forward.

At a given time-slot t, the network controller may activate
a set of non-interfering links that are ON.
The network-configuration process {σ(t)}t≥1 evolves in discretetime according to a stationary ergodic process with the stationary distribution {p(σ)}σ∈Ξ [13], where
X
p(σ) = 1, p(σ) > 0, ∀σ ∈ Ξ
(5)
σ∈Ξ

Since the underlying physical processes responsible for
time-variation are often spatially-correlated [1], [19], the distribution of the link-states is assumed to follow an arbitrary
joint-distribution. The detailed parameters of this process
depend on the ambient physical environment, which is often difficult to measure. In particular, it is unrealistic to
assume that the broadcast-algorithm has knowledge of the
parameters of the process σ(t). Fortunately, our proposed
dynamic throughput-optimal broadcast algorithm does not
require the statistical characterization of the configurationprocess σ(t) or its stationary-distribution p(σ). This makes
our algorithm robust and suitable for use in time-varying
wireless networks.

3.

DEFINITION AND CHARACTERIZATION
OF BROADCAST CAPACITY

Intuitively, a network supports a broadcast rate λ if there
exists a scheduling policy under which all network nodes
receive distinct packets at rate λ. The broadcast-capacity
of a network is the maximally supportable broadcast rate
by any policy. Formally, we consider a class Π of scheduling
policies where each policy π ∈ Π consists of a sequence of
actions {πt }t≥1 , executed at every slot t. Each action πt
consists of two operations:
• The scheduler observes the current network-configuration
σ(t) and activates a subset of links by choosing a feasible activation vector s(t) ∈ Mσ(t) . Here Mσ denotes
the set of all feasible link-activation vectors in the subgraph G(V, Eσ ), complying with the underlying interference constraints. As an example, under the primary
interference constraint, Mσ is given by the set of all
matchings [6] of the sub-graph G(V, Eσ ).
Analytically, elements from the set Mσ will be denoted by their corresponding |E|-dimensional binary
incidence-vectors, whose component corresponding to
edge e is identically zero if e ∈
/ Eσ .
• Each node i forwards a subset of packets (possibly
empty) to node j over an activated link (i, j) ∈ σ(t),
subject to the link capacity constraint. The class Π
includes policies that may use all past and future information, and may forward any subset of packets over
a link, subject to the link-capacity constraint.
To formally introduce the notion of broadcast capacity,
we define the random variable Riπ (T ) to be the number of
distinct packets received by node i ∈ V up to time T , under
a policy π ∈ Π. The time average lim inf T →∞ Riπ (T )/T is
the rate of packet-reception at node i.
Definition 1. A policy π ∈ Π is called a “broadcast policy of rate λ” if all nodes receive distinct packets at rate λ,
i.e.,
1
min lim inf Riπ (T ) = λ,
i∈V T →∞ T

w.p. 1

(6)

where λ is the packet arrival rate at the source node r.
Definition 2. The broadcast capacity λ∗ of a network is
defined to be the supremum of all arrival rates λ, for which
there exists a broadcast policy π ∈ Π of rate λ.
In the following subsection, we derive an upper-bound on
broadcast-capacity, which immediately follows from the previous definition.

3.1 An Upper-bound on Broadcast Capacity
Consider a policy π ∈ Π that achieves a broadcast rate of
at least λ∗ − ǫ, for an ǫ > 0. Such a policy π exists due to
the definition of the broadcast capacity λ∗ in Definition 2.
Now consider any proper-cut U of the network G. By
definition of a proper-cut, there exists a node i ∈
/ U . Let
sπ (t, σ(t)) = (sπe (t), e ∈ E) be the link-activation vector
chosen by policy π in slot t, upon observing the currentconfiguration σ(t). The maximum number of packets that
can be transmitted across the cut U in slot t is upperbounded by the total capacity P
of all activated links across
the cut-set U , which is given by e∈EU ce sπe (t, σ(t)). Hence,
the number of distinct packets received by node i by time T
is upper-bounded by the total available capacity across the
cut U up to time T , subject to link-activation decisions of
the policy π. In other words, we have
Riπ (T ) ≤

T
X
X

ce sπe (t, σ(t)) = u ·

T
X

sπ (t, σ(t))

(7)

t=1

t=1 e∈EU

i.e.,
Riπ (T )
≤u·
T




T
1 X π
s (t, σ(t)) ,
T t=1

where the cut-vector u ∈ Rm , corresponds to the cut-set U ,
as in Eqn.(1). It follows that,
λ∗ − ǫ

(a)

≤
≤

Rjπ (T )
Rπ (T )
≤ lim inf i
T →∞
j∈V T →∞
T
T
 X

T
1
lim inf u ·
sπ (t, σ(t)) ,
T →∞
T t=1

min lim inf

(8)

where (a) follows from the fact that π is a broadcast policy
of rate at least λ∗ − ǫ. Since the above inequality holds for
all proper-cuts u, we have

 X
T
1
sπ (t, σ(t))
(9)
λ∗ − ǫ ≤ min lim inf u ·
u∈U T →∞
T t=1

The following technical lemma will prove to be useful for
deriving an upper-bound on the broadcast-capacity.
Lemma 1. For any policy π ∈ Π, and any propercut vector u, there exists a collection of vectors βσπ ∈

conv(Mσ ) σ∈Ξ , such that, the following holds w.p. 1

T
1 X π
s (t, σ(t))
T →∞
T t=1
X

= min u ·
p(σ)βσπ

min lim inf u ·
u∈U



u∈U

σ∈Ξ

The above lemma essentially replaces the minimum cutset bound of an arbitrary activations in (9), by the minimum
cut-set bound of a stationary randomized activation, which
is easier to handle. Combining Lemma 1 with Eqn. (9), we
conclude that for the policy π ∈ Π, there exists a collection
of vectors {βσπ ∈ conv(Mσ )}σ∈Ξ such that
X

λ∗ − ǫ ≤ min u ·
(10)
p(σ)βσπ
u∈U

σ∈Ξ


Maximizing the RHS of Eqn. (10) over all vectors βσ ∈
conv(Mσ ), σ ∈ Ξ and letting ǫ ց 0, we have the following
universal upper-bound on the broadcast capacity λ∗
X

∗
λ ≤
max
min u ·
(11)
p(σ)βσ
βσ ∈conv(Mσ ) u∈U

σ∈Ξ

Specializing the above bound for single-node cuts of the form
Uj = (V \ {j}) → {j}, ∀j ∈ V \ {r}, we have the following
upper-bound

X
(12)
p(σ)βσ
λ∗ ≤
max
min uj ·
βσ ∈conv(Mσ ) j∈V \{r}

σ∈Ξ

It will be shown in Section 4 that in a DAG, our throughputoptimal policy π ∗ achieves a broadcast-rate equal to the RHS
of the bound (12). Thus we have the following theorem

Theorem 3.1. The broadcast-capacity λ∗DAG of a
time-varying wireless DAG is given by:
X

λ∗DAG =
max
min uj ·
p(σ)βσ (13)
βσ ∈conv(Mσ ),σ∈Ξ j∈V \{r}

σ∈Ξ

The above theorem shows that for computing the broadcastcapacity of a wireless DAG, taking minimum over the singlenode cut-sets {uj , j ∈ V \ {r}} suffice (c.f. Eqn. (11)).

3.2 An Illustrative Example of Capacity Computation
In this section, we work out a simple example to illustrate
the previous results.

Configuration σ4
Figure 1: A Wireless Network and its four possible
configurations
transmitted over a link if it is ON. Moreover, since the links
are assumed to be point-to-point, even if both the links ra
and rb are ON at a slot t (i.e., σ(t) = σ3 ), a packet can be
transmitted over one of the links only. Hence, the sets of
feasible activations are given as follows:
 
 
0
1
},
}, Mσ2 = {
Mσ 1 = {
1
0
   
1
0
,
}, Mσ4 = φ.
Mσ 3 = {
0
1
Here the first coordinate corresponds to activating the edge
ra and the second coordinate corresponds to activating the
edge rb.
To illustrate the effect of link-correlations on broadcastcapacity, we consider three different joint-distributions p(σ),
all of them having the following marginal
1
2
1
p(rb = ON) = p(rb = OFF) =
2

p(ra = ON) = p(ra = OFF) =

Case 1: Zero correlations.
In this case, the links ra and rb are ON w.p.
dently at every slot, i.e.,
p(σi ) = 1/4,

Configuration σ1

indepen-

i = 1, 2, 3, 4

(14)

It can be easily seen that the broadcast capacity, as given
in Eqn. (13), is achieved when in configurations σ1 and σ2 ,
the edges ra and rb are activated w.p. 1 respectively and in
the configuration σ3 the edges ra and rb are activated with
probability 12 and 12 . In other words, an optimal activation
schedule of a corresponding stationary randomized policy is
given as follows:
βσ∗1 = 1

Wireless network

1
2

′
0 , βσ∗2 = 0

1 ′
2

′
1
1 , βσ∗3 =
2

The optimal broadcast capacity can be computed from Eqn.
(13) to be λ∗ = 14 + 0 + 14 × 21 = 38 .

Case 2: Positive correlations.
In this case, assume that the edges ra and rb are positively
correlated, i.e., we have
Configuration σ2

Configuration σ3

Consider the simple wireless network shown in Figure (1),
with node r being the source. The possible network configurations σi , i = 1, 2, 3, 4 are also shown. One packet can be

p(σ1 ) = p(σ2 ) = 0; p(σ3 ) = p(σ4 ) =

1
2

Then it is clear that half of the slots are wasted when both
the links are OFF (i.e., in the configuration σ4 ). When
the network is in configuration σ3 , an optimal randomized

activation is to choose one of the two links uniformly at
random and send packets over it. Thus
1
1 ′
βσ∗3 =
2
2
The optimal broadcast-capacity, computed from Eqn. (13)
is λ∗ = 14 .

Case 3: Negative correlations.
In this case, we assume that the edges ra and rb are negatively correlated, i.e., we have
1
; p(σ3 ) = p(σ4 ) = 0
2
It is easy to see that in this case, a capacity-achieving activation strategy is to send packets over the link whichever
is ON. The broadcast-capacity in this case is λ∗ = 21 , the
highest among the above three cases.
In this example, with an arbitrary joint distribution of networkconfigurations {p(σi ), i = 1, 2, 3, 4}, it is a matter of simple
∗
calculation to obtain the optimal activations βσ
in Eqn.
i
(13). However it is clear that for an arbitrary network with
arbitrary activations M and configuration sets Ξ, evaluating (13) is non-trivial. In the following section we study this
problem under some simplifying assumptions.
p(σ1 ) = p(σ2 ) =

3.3 Efficient Computation of Broadcast Capacity
In this section we study the problem of efficient computation of the Broadcast Capacity λ∗ of a wireless DAG, given
by Eqn. (13). In particular, we show that when the number
of possible network configurations |Ξ|(n) grows polynomially
with n (the number of nodes in the network), there exists
a strongly polynomial-time algorithm to compute λ∗ under
the primary-interference constraint. Polynomially-bounded
network-configurations arise, for example, when the set Ξ(n)
consists of all subgraphs of the graph G with at most d number of edges, for some fixed integer d. In this case |Ξ(n)| can
be bounded as follows
!
d
X
m
= O(n2d ),
|Ξ|(n) ≤
k
k=0

2

where m(= O(n )) is the number of edges in the graph G.

Theorem 3.2 (Efficient Computation of λ∗ ).
Suppose that there exists a polynomial q(n) such that,
for a wireless DAG network G with n nodes, the number
of possible network configurations |Ξ|(n) is bounded
polynomially in n, i.e., |Ξ|(n) = O(q(n)). Then, there
exists a strongly poly − time algorithm to compute the
broadcast-capacity of the network under the primary
interference constraints.

Although only polynomially many network configurations
are allowed, we emphasize that Theorem (3.2) is highly nontrivial. This is because, each network-configuration σ ∈ Ξ itself contains exponentially many possible activations (matchings). The key combinatorial result that leads to Theorem
(3.2) is the existence of an efficient separator oracle for the
matching-polytope for any arbitrary graph [22]. We first

reduce the problem of broadcast-capacity computation of a
DAG to an LP with exponentially many constraints. Then
invoking the above separator oracle, we show that this LP
can be solved in strongly polynomial-time.
Proof. See Appendix 9.1.

3.4 Simple Bounds on λ∗
Using Theorem (3.2) we can, in principle, compute the
broadcast-capacity λ∗ of a wireless DAG with polynomially many network configurations. However, the complexity of the exact computation of λ∗ grows substantially with
the number of the possible configurations |Ξ|(n). Moreover,
Theorem (3.2) does not apply when |Ξ|(n) can no longer
be bounded by a polynomial in n. A simple example of
exponentially large |Ξ|(n) is when a link e is ON w.p. pe
independently at every slot, for all e ∈ E.
To address this issue, we obtain bounds on λ∗ , whose computational complexity is independent of the size of |Ξ|. These
bounds are conveniently expressed in terms of the broadcastcapacity of the static network G(V, E) without time-variation,
i.e. when |Ξ| = 1 and Eσ = E, σ ∈ Ξ. Let us denote the
broadcast-capacity of the static network by λ∗stat . Specializing Eqn. (13) to this case, we obtain
λ∗stat =

max

min uj · β.

β∈conv(M) j∈V \{r}

(15)

Using Theorem (3.2), λ∗stat can be computed in poly-time
under the primary-interference constraint.
Now consider an arbitrary joint distribution p(σ) such that
each link is ON uniformly with probability p, i.e.,
X
p(σ) = p, ∀e ∈ E.
(16)
σ∈Ξ:σ(e)=1

We have the following bounds:

Lemma 2

(Bounds on Broadcast Capacity).
pλ∗stat ≤ λ∗ ≤ λ∗stat .

Proof. See Appendix 9.3.
Generalization of the above Lemma to the setting, where
the links are ON with non-uniform probabilities, may also
be obtained in a similar fashion.
Note that, in our example 3.2 the bounds in Lemma 2 are
tight. In particular, here the value of the parameter p = 21 ,
the lower-bound is attained in case (2) and the upper-bound
is attained in case (3).
The above lemma immediately leads to the following corollary:

Corollary 3.3. (Approximation-algorithm for
computing λ∗ ). Assume that, under the stationary
distribution p(σ), probability that any link is ON is p,
uniformly for all links. Then, there exists a poly-time
p-approximation algorithm to compute the broadcastcapacity λ∗ of a DAG, under the primary-interference
constraints.

Proof. See Appendix 9.4.
In the following section, we are concerned with designing
a dynamic and throughput-optimal broadcast policy for a
time-varying wireless DAG network.

4.

THROUGHPUT-OPTIMAL BROADCAST
POLICY FOR WIRELESS DAGS

The classical approach of solving the throughput-optimal
broadcast problem in the case of a static, wired network is
to compute a set of edge-disjoint spanning trees of maximum cardinality (by invoking Edmonds’ tree-packing theorem [20]) and then routing the incoming packets to all nodes
via these pre-computed trees [21]. In the time-varying wireless setting that we consider here, because of frequent and
random changes in topology, routing packets over a fixed set
of spanning trees is no-longer optimal. In particular, part
of the network might become disconnected from time-totime, and it is not clear how to select an optimal set of trees
to disseminate packets. The problem becomes even more
complicated when the underlying statistical model of the
network-connectivity process (in particular, the stationary
distribution {p(σ), σ ∈ Ξ}) is unknown, which is often the
case in mobile adhoc networks. Furthermore, wireless interference constraints add another layer of complexity, rendering the optimal dynamic broadcasting problem in wireless
networks extremely challenging.
In this section we propose an online, dynamic, throughputoptimal broadcast policy for time-varying wireless DAG networks, that does not need to compute or maintain any global
topological structures, such as spanning trees. Interestingly,
we show that the broadcast-algorithm that was proposed
in [23] for static wireless network, generalizes well to the
time-varying case. As in [23], our algorithm also enjoys the
attractive feature of in-order packet delivery. The key difference between the algorithm in [23] and our dynamic algorithm is in link-scheduling. In particular, in our algorithm,
the activation sets are chosen based on current networkconfiguration σ(t).

4.1 Throughput-Optimal Broadcast Policy π ∗
All policies π ∈ Π, that we consider in this paper, comprise
of the following two sub-modules which are executed at every
time-slot t:
• π(A) (Activation-module): activates a subset of links,
subject to the interference constraint and the current
network-configuration σ(t).
• π(S) (Packet-Scheduling module): schedules a subset of packets over the activated links.
Following the treatment in [23], we first restrict our attention
to a sub-space Πin−order , in which the broadcast-algorithm
is required to follow the so-called in-order delivery property,
defined as follows
in−order

Definition 3 (Policy-space Π
[23]). A policy
π belongs to the space Πin−order if all incoming packets are
serially indexed as {1, 2, 3, . . .} according to their order of arrival at the source r and a node can receive a packet p at time
t, if and only if it has received the packets {1, 2, , . . . , p − 1}
by the time t.

As a consequence of the in-order delivery, the state of received packets in the network at time-slot t may be succinctly represented by the n-dimensional vector R(t), where
Ri (t) denotes the index of the latest packet received by node
i by time t. We emphasize that this succinct network-state
representation by the vector R(t) is valid only under the action of policies in the space Πin−order . This compact representation of the packet-state results in substantial simplification of the overall state-space description. This is because,
to completely specify the current packet-configurations in
the network in the general policy-space Π, we need to specify the identity of each individual packets that are received
by different nodes.
To exploit the special structure that a directed acyclic graph
offers, it would be useful to constrain the packet-scheduler
π(S) further to the following policy-space Π∗ ⊂ Πin−order .
Definition 4 (Policy-space Π∗ ⊂ Πin−order [23]). A
broadcast policy π belongs to the space Π∗ if π ∈ Πin−order
and π satisfies the additional constraint that a packet p can
be received by a node j at time t if all in-neighbours of the
node j have received the packet p by the time t.
The above definition is further illustrated in Figure 2. The
variables Xj (t) and i∗t (j) appearing in the Figure are defined
subsequently in Eqn. (19).
It is easy to see that for all policies π ∈ Π∗ , the packet
Ra (t) = 18
Rj (t) = 10
Rb (t) = 15 Rc (t) = 14

Figure 2: Under a policy π ∈ Π∗ , the set of packets available for transmission to node j at slot t is {11, 12, 13, 14},
which are available at all in-neighbors of node j. The
in-neighbor of j inducing the smallest packet deficit is
i∗t (j) = c, and Xj (t) = 4.

scheduler π(S) is completely specified. Hence, to specify a
policy in the space Π∗ , we need to define the activationmodule π(A) only.
Towards this end, let µij (t) denote the rate (in packets per
slot) allocated to the edge (i, j) in the slot t by a policy
π ∈ Π∗ , for all (i, j) ∈ E. Note that, the allocated rate µ(t)
is constrained by the current network configuration σ(t) at
slot t. In other words, we have
µ(t) ∈ c ⊙ Mσ(t) , ∀t

(17)

This implies that, under any randomized activation
Eµ(t) ∈ c ⊙ conv(Mσ(t) ), ∀t

(18)

In the following lemma, we show that for all policies π ∈ Π∗ ,
certain state-variables X(t), derived from the state-vector
R(t), satisfy so-called Lindley recursion [15] of queuing theory. Hence these variables may be thought of as virtual
queues. This technical result will play a central role in deriving a Max-Weight type throughput-optimal policy π ∗ , which
is obtained by stochastically stabilizing these virtual-queues.

For each j ∈ V \ {r}, define
Xj (t) = min

Ri (t) − Rj (t)

i∈∂ in (j)

i∗t (j) = arg min

i∈∂ in (j)




Ri (t) − Rj (t) ,

(19)
(20)

where in Eqn. (20), ties are broken lexicographically. The
variable Xj (t) denotes the minimum packet deficit of node
j with respect to any of its in-neighbours. Hence, from the
definition of the policy-space Π∗ , it is clear that Xj (t) is the
maximum number of packets that a node j can receive from
its in-neighbours at time t, under any policy in Π∗ .
The following lemma proves a “queuing-dynamics” of the
variables Xj (t), under any policy π ∈ Π∗ .

Lemma 3
have

([23]). Under all policies in π ∈ Π∗ , we


Xj (t + 1) ≤ Xj (t) −
+

X

µkj (t)

k∈∂ in (j)

X

+

µmi∗t (j) (t)

account the time-variation of network configurations, which
is the focus of this paper.
To describe π ∗ (A), we first define the node-set
Kj (t) = {m ∈ ∂ out (j) : j = i∗t (m)}

where the variables
are defined earlier in Eqn. (20).
The activation-module π (A) is described in Algorithm 1.
The resulting policy in the space Π∗ with the activationmodule π ∗ (A) is called π ∗ .
Note that, in steps (1) and (2) above, the computation
Algorithm 1 A Throughput-optimal Activation Module
π ∗ (A)
1: To each link (i, j) ∈ E, assign a weight as follows:
(
P
Xj (t) − k∈Kj (t) Xk (t), if σ(i,j) (t) = 1
(23)
Wij (t) =
0,
o.w.
2: Select an activation s∗ (t) ∈ Mσ(t) as follows:

s∗ (t) ∈ arg max s · c ⊙ W (t)
s∈Mσ(t)

(21)

m∈∂ in (i∗
t (j))


Lemma (3) shows that the variables Xj (t), j ∈ V \ {r}
∗
satisfy Lindley recursions in the policy-space Π . Interestingly, unlike the corresponding unicast problem [25], there
is no “physical queue” in the system.
Continuing correspondence with the unicast problem, the
next lemma shows that any activation module π(A) that
“stabilizes” the virtual queues X(t) for all arrival rates λ <
λ∗ , constitutes a throughput optimal broadcast-policy for a
wireless DAG network.

Lemma 4. Suppose that, the underlying topology of
the wireless network is a DAG. If under the action of
a broadcast policy π ∈ Π∗ , for all arrival rates λ < λ∗ ,
the virtual queue process {X(t)}∞
0 is rate-stable, i.e.,
X
1
lim sup
Xj (T ) = 0, w.p. 1,
T →∞ T
j6=r

then π is a throughput-optimal broadcast policy for the
DAG network.

Proof. See Appendix (9.5).
Equipped with Lemma (4), we now set out to derive a dynamic activation-module π ∗ (A) to stabilize the virtual-queue
∗
process {X(t)}∞
0 for all arrival rates λ < λ . Formally, the
∗
structure of the module π (A) is given by a mapping of the
following form:
π ∗ (A) : (X(t), σ(t)) → Mσ(t)
Thus, the module π ∗ (A) is stationary and dynamic as it
depends on the current value of the state-variables and the
network-configuration only. This activation-module is different from the policy described in [23] as the latter is meant
for static wireless networks and hence, does not take into

(22)

i∗t (m)
∗

(24)

3: Allocate rates on the links as follows:
µ∗ (t) = c ⊙ s∗ (t)

(25)

of link-weights and link-activations depend explicitly on the
current network-configuration σ(t). As anticipated, in the
following lemma, we show that the activation-module π ∗ (A)
stochastically stabilizes the virtual-queue process {X(t)}∞
0 .

Lemma 5. For all arrival rates λ < λ∗ , under the action of the policy π ∗ in a DAG, the virtual-queue process
{X(t)}∞
0 is rate-stable, i.e.,
1 X
Xj (T ) = 0, w.p. 1
lim sup
T →∞ T
j6=r

The proof of this lemma is centered around a Lyapunovdrift argument [18]. Its complete proof is provided in Appendix (9.6).
Combining the lemmas (4) and (5), we immediately obtain
the main result of this section

Theorem 4.1. The policy π ∗ is a throughput-optimal
broadcast policy in a time-varying wireless DAG network.

5. THROUGHPUT-OPTIMAL BROADCASTING WITH INFREQUENT INTER-NODE
COMMUNICATION
In practical mobile wireless networks, it is unrealistic to
assume knowledge of network-wide packet-state information
by every node at every slot. This is especially true in the case
of time-varying wireless networks, where network-connectivity

changes frequently. In this section we extend the main results of section 4 by considering the setting where the nodes
make control decisions with imperfect packet-state information that they currently possess. We will show that the dynamic broadcast-policy π ∗ retains its throughput-optimality
even in this challenging scenario.

State-Update Model.
We assume that two nodes i and j can mutually update
their knowledge of the set of packets received by the other
node, only at those slots with positive probability, when
the corresponding wireless-link (i, j) is in ON state. Otherwise, it continues working with the outdated packet stateinformation. Throughout this section, we assume that the
nodes have perfect information about the current networkconfiguration σ(t).
Suppose that, the latest time prior to time t when packetstate update was made across the link (i, j) is t − T(i,j) (t).
Here T(i,j) (t) is a random variable, supported on the set
of non-negative integers. Assume for simplicity, that the
network configuration process {σ(t)}∞
0 evolves according to
a finite-state, positive recurrent Markov-Chain, with the
stationary distribution {p(σ) > 0, σ ∈ Ξ}. With this assumption, T(i,j) (t) is related to the first-passage time in the
finite-state positive recurrent chain {σ(t)}∞
0 . Using standard theory
P [7], it can be shown that the random variable
T (t) ≡
(i,j)∈E T(i,j) (t) has bounded expectation for all
time t .

Analysis of π ∗ with Imperfect Packet-State Information.
Consider running the policy π ∗ , where each node j now
computes the weights Wij′ (t), given by Eqn.(23), of the incoming links (i, j) ∈ E, based on the latest packet-state
information available to it. In particular, for each of its
in-neighbour i ∈ ∂ in (j), the node j possess the following
information of the number of packets received by node i:
Ri′ (t) = Ri (t − T(ij) (t))

(26)
′

Now, if the packet-scheduler module π (S) of a broadcastpolicy π ′ takes scheduling decision based on the imperfect
state-information R′ (t) (instead of the true state R(t)), it
still retains the following useful property:

Lemma 6. π ′ ∈ Π∗ .

Figure 3: A 3 × 3 grid network.
Wij′ (t), used by policy π ′ and the true link-weights Wij (t),
as follows

Lemma 7. There exists a finite constant C such that,
the expected weight Wij′ (t) of the link (ij), locally computed by the node j using the random update process,
differs from the true link-weight Wij (t) by at most C,
i.e.
|EWij′ (t) − Wij (t)| ≤ C

(27)

The expectation above is taken with respect to the random packet-state update process.

Proof. See Appendix (9.8)
From lemma (7) it follows that the policy π ′ , in which
link-weights are computed using imperfect packet-state information is also a throughput-optimal broadcast policy for
a wireless DAG. Its proof is very similar to the proof of Theorem (4.1). However, since the policy π ′ makes scheduling
decision using W ′ (t), instead of W (t), we need to appropriately bound the differences in drift using the Lemma (7).
The technical details are provided in Appendix (9.9).

Theorem 5.1. The policy π ′ is a throughput-optimal
broadcast algorithm in a time-varying wireless DAG.

Proof. See Appendix (9.7).
The above lemma states that the policy π ′ inherits the inorder delivery property and the in-neighbour packet delivery
constraint of the policy-space Π∗ .
From Eqn. (23) it follows that, computation of linkweights {Wij (t), i ∈ ∂ in (j)} by node j requires packet-state
information of the nodes that are located within 2-hops from
the node j. Thus, it is natural to expect that with an ergodic state-update process, the weights Wij′ (t), computed
from the imperfect packet-state information, will not differ
too much from the true weights Wij (t), on the average. Indeed, we can bound the difference between the link-weights

6. NUMERICAL SIMULATION
We numerically simulate the performance of the proposed
dynamic broadcast-policy on the 3 × 3 grid network, shown
in Figure 3. All links are assumed to be of unit capacity.
Wireless link activations are subject to primary interference
constraints, i.e., at every slot, we may activate a subset of
links which form a Matching [28] of the underlying topology.
External packets arrive at the source node r according to a
Poisson process of rate λ packets per slot. The following
proposition shows that, the broadcast capacity λ∗stat of the
static 3 × 3 wireless grid (i.e., when all links are ON with
probability 1 at every slot) is 25 .

7. CONCLUSION
Proposition 6.1. The broadcast-capacity λ∗stat of
the static 3 × 3 wireless grid-network in Figure 3 is 25 .

′

Average Broadcast-Delay Dpπ (λ)

See Appendix (9.10) for the proof.
In our numerical simulation, the time-variation of the network is modeled as follows: link-states are assumed to evolving in an i.i.d. fashion; each link is ON with probability p at
every slot, independent of everything else. Here 0 < p ≤ 1 is
the connectivity-parameter of the network. Thus, for p = 1
we recover the static network model of [23]. We also assume
that the nodes have imperfect packet-state information as in
Section 5. Hence, two nodes i and j can directly exchange
packet state-information, only when the link (i, j) (if any)
is ON.
′
The average broadcast-delay Dpπ (λ) is plotted in Figure 4
as a function of the packet arrival rate λ. The broadcastdelay of a packet is defined as the number of slots the packet
takes to reach all nodes in the network after its arrival. Because of the throughput-optimality of the policy π ′ (Theorem (5.1)), the broadcast-capacity λ∗ (p) of the network, for
a given value of p, may be empirically evaluated from the
′
λ-intercept of vertical asymptote of the Dpπ (λ) − λ curve.
As evident from the plot, for p = 1, the proposed dynamic
algorithm achieves all broadcast rates below λ∗stat = 25 = 0.4.
This shows the throughput-optimality of the algorithm π ′ .
It is evident from the Figure 4 that the broadcast capacity λ∗ (p) is non-decreasing in the connectivity-parameter p,
i.e., λ∗ (p1 ) ≥ λ∗ (p2 ) for p1 ≥ p2 . We observe that, with
i.i.d. connectivity, the capacity bounds given in Lemma (2)
are not tight, in general. Hence the lower-bound of pλ∗stat
is a pessimistic estimate of the actual broadcast capacity
′
λ∗ (p) of the DAG. The plot also reveals that, Dpπ (λ) is nondecreasing in λ for a fixed p and non-increasing in p for a
fixed λ, as expected.

p = 0.4

p = 0.6
p=1

Packet Arrival Rate λ
′

Figure 4: Plot of average broadcast-delay Dpπ (λ), as
a function of the packet arrival rates λ. The underlying wireless network is the 3 × 3 grid, shown in
Figure 3, with primary interference constraints.

In this paper we studied the problem of throughput-optimal
broadcasting in wireless directed acyclic networks with pointto-point links and time-varying connectivity. We characterized the broadcast-capacity of such networks and derived efficient algorithms for computing it, both exactly and approximately. Next, we proposed a throughput-optimal broadcast
policy for such networks. This algorithm does not require
any spanning tree to be maintained and operates based on
local information, which is updated sporadically. The algorithm is robust and does not require statistics of the arrival
or the connectivity process, thus making it useful for mobile
wireless networks. The theoretical results are supplemented
with illustrative numerical simulations. Future work would
be to remove the restriction of the directed acyclic topology.
It would also be interesting design broadcast algorithms for
wireless networks with point-to-multi-point links.

8. REFERENCES
[1] P. Agrawal and N. Patwari. Correlated link shadow
fading in multi-hop wireless networks. Wireless
Communications, IEEE Transactions on,
8(8):4024–4036, 2009.
[2] D. Bertsimas and J. N. Tsitsiklis. Introduction to
linear optimization, volume 6. Athena Scientific
Belmont, MA, 1997.
[3] A. Beygelzimer, A. Kershenbaum, K.-W. Lee, and
V. Pappas. The benefits of directional antennas in
heterogeneouswireless ad-hoc networks. In Mobile Ad
Hoc and Sensor Systems. MASS 2008. 5th IEEE
International Conference on, pages 442–449. IEEE.
[4] Y. Chu, S. Rao, S. Seshan, and H. Zhang. Enabling
conferencing applications on the internet using an
overlay muilticast architecture. ACM SIGCOMM
computer communication review, 31(4):55–67, 2001.
[5] S. Dasgupta, C. H. Papadimitriou, and U. Vazirani.
Algorithms. McGraw-Hill, Inc., 2006.
[6] R. Diestel. Graph theory. Grad. Texts in Math, 2005.
[7] R. G. Gallager. Discrete stochastic processes, volume
321. Springer Science & Business Media, 2012.
[8] R. Gandhi, S. Parthasarathy, and A. Mishra.
Minimizing broadcast latency and redundancy in ad
hoc networks. In Proceedings of the 4th ACM
international symposium on Mobile ad hoc networking
& computing, pages 222–232. ACM, 2003.
[9] M. Ge, S. V. Krishnamurthy, and M. Faloutsos.
Overlay multicasting for ad hoc networks. In
Proceedings of Third Annual Mediterranean Ad Hoc
Networking Workshop, 2004.
[10] T. Ho and H. Viswanathan. Dynamic algorithms for
multicast with intra-session network coding. In Proc.
43rd Annual Allerton Conference on Communication,
Control, and Computing, 2005.
[11] S. C. Huang, P.-J. Wan, X. Jia, H. Du, and W. Shang.
Minimum-latency broadcast scheduling in wireless ad
hoc networks. In 26th IEEE INFOCOM 2007.
[12] L. Junhai, Y. Danxia, X. Liu, and F. Mingyu. A
survey of multicast routing protocols for mobile
ad-hoc networks. Communications Surveys Tutorials,
IEEE, 11(1):78–91, First 2009.
[13] A. Kamthe, M. A. Carreira-Perpiñán, and A. E.
Cerpa. Improving wireless link simulation using

[14]

[15]

[16]

[17]
[18]

[19]

[20]
[21]

[22]
[23]

[24]

[25]

[26]
[27]
[28]
[29]

9.

multilevel markov models. ACM Trans. Sen. Netw.,
10(1):17:1–17:28, Dec. 2013.
X. Lin, N. Shroff, and R. Srikant. A tutorial on
cross-layer optimization in wireless networks. Selected
Areas in Communications, IEEE Journal on,
24(8):1452–1463, Aug 2006.
D. V. Lindley. The theory of queues with a single
server. In Mathematical Proceedings of the Cambridge
Philosophical Society, volume 48, pages 277–289.
Cambridge Univ Press, 1952.
J. Macker, J. Klinker, and M. Corson. Reliable
multicast data delivery for military networking. In
Military Communications Conference, 1996. MILCOM
’96, Conference Proceedings, IEEE, volume 2, pages
399–403 vol.2, Oct 1996.
J. Matoušek. Lectures on discrete geometry, volume
108. Springer New York, 2002.
M. J. Neely. Stochastic network optimization with
application to communication and queueing systems.
Synthesis Lectures on Communication Networks,
3(1):1–211, 2010.
N. Patwari and P. Agrawal. Effects of correlated
shadowing: Connectivity, localization, and rf
tomography. In Information Processing in Sensor
Networks, 2008. IPSN’08. International Conference
on, pages 82–93. IEEE, 2008.
R. Rustin. Combinatorial Algorithms. Algorithmics
Press, 1973.
S. Sarkar and L. Tassiulas. A framework for routing
and congestion control for multicast information flows.
Information Theory, IEEE Transactions on,
48(10):2690–2708, 2002.
A. Schrijver. Combinatorial optimization: polyhedra
and efficiency, volume 24. Springer, 2003.
A. Sinha, G. Paschos, C. ping Li, and E. Modiano.
Throughput-optimal broadcast on directed acyclic
graphs. In Computer Communications (INFOCOM),
2015 IEEE Conference on, pages 1248–1256.
D. Smith. Ip tv bandwidth demand: Multicast and
channel surfing. In INFOCOM 2007. 26th IEEE
International Conference on Computer
Communications. IEEE, pages 2546–2550, May 2007.
L. Tassiulas and A. Ephremides. Stability properties
of constrained queueing systems and scheduling
policies for maximum throughput in multihop radio
networks. Automatic Control, IEEE Transactions on,
37(12):1936–1948, 1992.
D. Towsley and A. Twigg. Rate-optimal decentralized
broadcasting: the wireless case, 2008.
D. Tse and P. Viswanath. Fundamentals of wireless
communication. Cambridge university press, 2005.
D. B. West et al. Introduction to graph theory,
volume 2. Prentice hall Upper Saddle River, 2001.
J. Yuan, Z. Li, W. Yu, and B. Li. A cross-layer
optimization framework for multihop multicast in
wireless mesh networks. Selected Areas in
Communications, IEEE Journal on, 24(11), 2006.

APPENDIX

9.1 Proof of Theorem 3.2

Under the primary interference constraint, the set of feasible activations of the graphs are matchings [28]. To solve for
the optimal broadcast capacity in a time-varying network,
first we recast Eqn. (13) as an LP. Although this LP has
exponentially many constraints, using a well-known separation oracle for matchings, we show how to solve this LP in
strongly-polynomial time via the ellipsoid algorithm [2].
′

For a subset of edges E ′ ⊂ E, let χE be the incidence
′
vector, where χE (e) = 1 if e ∈ E ′ and is zero otherwise.
Let
Pmatching (G(V, E)) =
convexhull({χM |M is a matching in G(V, E)})
We have the following classical result by Edmonds [22].
Theorem 9.1. The set Pmatching (G(V, E)) is characterized by the set of all β ∈ R|E| such that :
X

βe

≥ 0

∀e ∈ E

βe

≤ 1

∀v ∈ V

βe

≤

(28)

e∈∂ in (v)∪∂ out (v)

X

e∈E[U ]

|U | − 1
;
2

U ⊂ V, |U | odd

Here E[U ] is the set of edge with both end points in U.
Thus, following Eqn. (13), the broadcast capacity of a
DAG can be obtained by the following LP :
max λ

(29)

Subject to,
λ ≤

X

e∈∂ in (v)

βσ

∈

ce

X

σ∈Ξ


p(σ)βσ,e , ∀v ∈ V \ {r} (30)

Pmatching (G(V, Eσ )),

∀σ ∈ Ξ

(31)

The constraint corresponding to σ ∈ Ξ in (31) refers to the
set of linear constraints given in Eqn.(28) corresponding to
the graph G(V, Eσ ), for each σ ∈ Ξ.
Invoking the equivalence of optimization and separation due
to the ellipsoid algorithm [2], it follows that the LP (29) is
solvable in poly-time, if there exists an efficient separatororacle for the set of constraints (30) and (31). With our
assumption of polynomially many network configurations
|Ξ|(n), there are only linearly many constraints (n − 1, to be
precise) in (30) with polynomially many variables in each
constraint. Thus the set of constraints (30) can be separated efficiently. Next we invoke a classic result from the
combinatorial-optimization literature which shows the existence of efficient separators for the matching polytopes.
Theorem 9.2. [22] There exists a strongly poly-time
algorithm, that given G = (V, E) and β : E → R|E|
determines if β satisfies (28) or outputs an inequality
from (9.1) that is violated by β.

Hence, there exists an efficient separator for each of the
constraints in (9.1). Since there are only polynomially many
network configurations, this directly leads to Theorem 3.2.

9.2 Proof of Lemma 1

Eqn. (37), (38) and Eqn. (38), we have

Proof. Fix a time T . For each configuration σ ∈ Ξ, let
σ
be the index of the time-slots up to time T such
{tσ,i }Ti=1
that σ(t) = σ. Clearly we have,
X
Tσ = T
(32)

u∈U T ր∞

=

min

u∈U

σ∈Ξ

=

Hence, we can rewrite
Tσ
T
X Tσ 1 X
1 X π
sπ (tσ,i , σ)
s (t, σ(t)) =
T t=1
T
T
σ
i=1
σ∈Ξ

u·

Since the process σ(t) is stationary ergodic, we have

lim

Tσ
= p(σ), ∀σ ∈ Ξ, w.p. 1
T

min lim inf u ·

u∈U T ր∞

=

min

u∈U

X

1
T

T
X

s (t, σ(t))

t=1

p(σ) lim inf u ·
T →∞

σ∈Ξ

(36)

Let an optimal solution to Eqn. (13) be obtained at

Ξ . Then from Eqn. (39), it follows that
X
p(σ)βσ∗ ∈ conv(M)


Tσ
1 X π
s (tσ,i , σ) ,
Tσ i=1

w.p. 1

= min
u∈U

σ∈Ξ

(37)

∈

π
p(σ) lim u · ζσ,T
σk
k→∞

π
p(σ) lim inf u · ζσ,T
.
σ
Tσ →∞

π
lim ζσ,T
= βσπ ,
σk

∀σ ∈ Ξ

Where βσπ ∈ Mσ , since Mσ is closed. Hence combining

p(σ)βσ∗

σ∈Ξ

max



min uj · β

β∈conv(M) j∈V \{r}

This proves the upper-bound.

9.3.2 Proof of the Lower-bound
Since Mσ ⊂ M, the expression for the broadcast-capacity
(13) may be re-written as follows:
X
X

p(σ)βσ (e)1(e ∈ σ)
λ∗ = max min
ce
e∈∂ in (j)

σ∈Ξ

∗

Let β ∈ M be the optimal activation, achieving the RHS
of (15). Hence we can lower-bound λ∗ as follows
X
X

p(σ)1(e ∈ σ)
λ∗ ≥
min
ce β ∗ (e)
j∈V \{r}

e∈∂ in (j)

p min

j∈V \{r}

X

σ∈Ξ

ce β ∗ (e)

e∈∂ in (j)

=

p min uj · β ∗

(b)

pλ∗stat

=

(38)

X

λ∗ ≤ λ∗stat

βσ ∈M j∈V \{r}

Let us denote
k→∞

(39)
βσ∗ , σ

Using Eqn. (15), this shows that

=

X

min uj ·

≤

(a)

σ∈Ξ

w.p.1

∀σ ∈ Ξ

βσ ∈conv(Mσ ) j∈V \{r}

Since s (tσ,i , σ) ∈ Mσ for all i ≥ 1, convexity of the set Mσ
π
∈ Mσ for all Tσ ≥ 1. Since the set Mσ
implies that ζσ,T
σ
is closed and bounded (and hence, compact) any sequence
in Mσ has a converging sub-sequence. Consider any set of
π
}
, σ ∈ Ξ such that, it
converging sub-sequences {ζσ,T
σk k≥1
achieves the following

u∈U



βσ ∈ conv(Mσ ) =⇒ βσ ∈ conv(M)

max

π

min

σ∈Ξ

Mσ ⊂ M,



Tσ
1 X π
=
s (tσ,i , σ)
Tσ i=1

X

p(σ)βσπ

σ∈Ξ

Since p(σ) > 0, ∀σ ∈ Ξ, the above implies that Tσ ր
∞ as T ր ∞∀σ, w.p.1. In the rest of the proof we will
concentrate on a typical sample path {σ(t)}t≥1 having the
above property.
π
}
For each σ ∈ Ξ, define the sequence {ζσ,T
σ Tσ ≥1
π
ζσ,T
σ

u∈U

X

Hence we have,

π



min u ·

Proof. 9.3.1 Proof of the Upper-bound
Note that, for all σ ∈ Ξ, we have Eσ ⊂ E. Hence, it
follows that

(35)

Hence from Eqn. (34) we have,


σ∈Ξ

This in turn implies that

Using countability of Ξ and invoking the union bound, we
can strengthen the above conclusion as follows
T →∞

p(σ)u · βσπ

9.3 Proof of Lemma 2

 X


Tσ
T
Tσ
1 X π
1 X π
s (t, σ(t)) =
u·
s (tσ,i , σ) (34)
T t=1
T
Tσ i=1
σ∈Ξ
Tσ
= p(σ), w.p. 1 ∀σ ∈ Ξ
lim
T →∞ T

X


T
1 X π
s (t, σ(t))
T t=1

(33)

Hence,




min lim inf u ·

j∈V \{r}

Equality (a) follows from the assumption (16) and equality
(b) follows from the characterization (15). This proves the
lower-bound.

9.4 Proof of Corollary 3.3
∗

Consider the optimal randomized-activation vector β ∈
M, corresponding to the stationary graph G(V, E) (15). By
Theorem (3.2), β ∗ can be computed in poly-time under the
primary interference constraint. Note that, by Caratheodory’s
theorem [17], the support of β ∗ may be bounded by |E|.
Hence it follows that λ∗stat (15) may also be computed in
poly-time.
From the proof of Lemma (2), it follows that by randomly activating β ∗ (i.e., βσ (e) = β ∗ (e)1(e ∈ σ), ∀σ ∈ Ξ) we obtain
a broadcast-rate equal to pλ∗stat where λ∗stat is shown to be
an upper-bound to the broadcast capacity λ∗ in Lemma (2).
Hence it follows that pλ∗stat constitutes a p-approximation
to the broadcast capacity λ∗ , which can be computed in
poly-time.

Since
P the variables Xi (t)’s are non-negative, we have
j6=r Xj (t). Thus, for each node j

Pk−1
i=1

Xui (t) ≤

T −1
T −1
1 X
1 X
1
1 X
A(t) −
A(t).
Xj (T ) ≤ Rj (T ) ≤
T t=0
T
T
T t=0
j6=r

Taking limit as T → ∞ and using the strong law of large
numbers for the arrival process and Eqn. (40), we have
Rj (T )
= λ, ∀j.
T
This concludes the proof.
lim

w.p. 1

T →∞

9.6 Proof of Lemma (5)
We begin with a preliminary lemma.
Lemma 8. If we have

9.5 Proof of Lemma (4)
Assume that under the policy π ∈ Π∗ , the virtual queues
Xj (t) are rate stable i.e., limT →∞ Xj (T )/T = 0, a.s. for all
j. Applying union-bound, it follows that,
P
j6=r Xj (T )
= 0,
w.p. 1
(40)
lim
T →∞
T
Now consider any node j 6= r in the network. We can
construct a simple path p(r = uk → uk−1 . . . → u1 = j)
from the source node r to the node j by running the following Path construction algorithm on the underlying graph
G(V, E).

Q(t + 1) ≤ (Q(t) − µ(t))+ + A(t)

(42)

+

where all the variables are non-negative and (x) = max{x, 0},
then
Q2 (t + 1) − Q2 (t) ≤ µ2 (t) + A2 (t) + 2Q(t)(A(t) − µ(t)).
Proof. Squaring both sides of Eqn. (42) yields,
Q2 (t + 1)
≤ (Q(t) − µ(t))+

2

+ A2 (t) + 2A(t)(Q(t) − µ(t))+

≤ (Q(t) − µ(t))2 + A2 (t) + 2A(t)Q(t),
2

where we use the fact that x2 ≥ (x+ ) , Q(t) ≥ 0, and µ(t) ≥
0. Rearranging the above inequality finishes the proof.

Algorithm 2 r → j Path Construction Algorithm
Require: DAG G(V, E), node j ∈ V
1: i ← 1
2: ui ← j
3: while ui 6= r do
4:
ui+1 ← i∗t (ui );
5:
i← i+1
6: end while

Applying Lemma 8 to the dynamics (21) of Xj (t) yields, for
each node j 6= r,
Xj2 (t + 1) − Xj2 (t) ≤ B(t) +
X
X

2Xj (t)
µkj (t) ,
µmi∗t (t) −
m∈V

At time t, the algorithm chooses the parent of a node ui in
the path p as the one that has the least relative packet deficit
as compared to ui (i.e. ui+1 = i∗t (ui )). Since the underlying
graph G(V, E) is a connected DAG (i.e., there is a path from
the source to every other node in the network), the above
path construction algorithm always terminates with a path
p(r → j). Note that the output path of the algorithm varies
with time.
The number of distinct packets received by node j up to
time T can be written as a telescoping sum of relative packet
deficits along the path p, i.e.,

=



−

= −

i=1

Xui (T ) +

T
−1
X

X

 X

µmi∗t (t)

(45)

E[µij (t) | X(t), σ(t)] Xj (t)

(46)

Xj (t)E

m∈V

µkj (t) | X(t), σ(t)

k∈V

Xui (T ) + Rr (T )

k−1
X

X
j6=r

= B|V | − 2

i=1

(a)

∆(X(t)|σ(t)) , E[L(X(t + 1) − L(X(t)) | X(t), σ(t)]


X
Xj2 (t + 1) − Xj2 (t) | X(t), σ(t)

= E

Rui (T ) − Rui+1 (T ) + Ruk (T )

i=1

=−

where B(t) ≤ c2max + max{a2 (t), c2max } ≤ (a2 (t) + 2c2max ),
a(t) is the number of exogenous packet arrivals in a slot,
and cmax , maxe∈E ce is the maximum capacity of the links.
We assume the arrival process a(t) has bounded second moments; thus, there exists a finite constant B > 0 such that
E[B(t)] ≤ E a2 (t) + 2c2max < B.
the quadratic Lyapunov function L(X(t)) =
PWe define
2
j6=r Xj (t). From (43), the one-slot Lyapunov drift ∆(X(t)),
conditioned on the current network-configuration σ(t) yields

≤ B|V | + 2

k−1
X

(44)

k∈V

j6=r

Rj (T ) = Ru1 (T )
k−1
X

(43)

X



(i,j)∈E

A(t),

t=0

where the equality (a) follows the observation that
Xui (T ) = Qui+1 ui (T ) = Rui+1 (T ) − Rui (T ).

(41)

−

X

Xk (t)

k∈Kj (t)

= B|V | − 2

X



(i,j)∈E

Wij (t)E[µij (t) | X(t), σ(t)]

(47)

The broadcast-policy π ∗ is chosen to minimize the upperbound of conditional-drift, given on the right-hand side of
(47) among all policies in Π∗ .
Next, we construct a randomized scheduling policy π RAND ∈
∗
∗
Π . Let βσ
∈ conv(Mσ ) be the part of an optimal solution corresponding to σ(t) ≡ σ given by Eqn. 11. From
Caratheodory’s theorem [17], there exist at most (|E| + 1)
link-activation vectors sk ∈
σ and the associated nonPM
|E|+1
negative scalars {ασk } with k=1 ασk = 1, such that
|E|+1

βσ∗

=

X

ασk sσk .

(48)

k=1

Define the average (unconditional) activation vector
X
p(σ)βσ∗
β∗ =

Note that this stationary randomized policy π RAND operates independently of the state of received packets in the
network, i.e., X(t). However it depends on the current
network-configuration σ(t). Since each network node j is
relabelled as vl for some l, from (53) we have, for each node
j 6= r, the total expected incoming transmission rate to the
node j under the policy π RAND , averaged over all network
states σ satisfies
RAND

X

E[µπij

X

(t) | X(t)] =

RAND

E[µπij

(t)]

i:(i,j)∈E

i:(i,j)∈E

X

= ql

ce βe∗

e∈EUv

l

l
.
=λ+ǫ
|V |

(49)

σ∈Ξ

(54)

Hence, from Eqn. (11) we have,
λ∗ ≤

min

U : a proper cut

X

ce βe∗ .

(50)

e∈EU

Suppose that the exogenous packet arrival rate λ is strictly
less than the broadcast capacity λ∗ . There exists an ǫ > 0
such that λ + ǫ ≤ λ∗ . From (50), we have
X
λ+ǫ≤
min
ce βe∗ .
(51)
U : a proper cut

e∈EU

For any network node v 6= r, consider the proper cuts Uv =
V \ {v}. Specializing the bound in (51) to these cuts, we
have
X
λ+ǫ ≤
ce βe∗ , ∀v 6= r.
(52)

Equation (54) shows that the randomized policy π RAND provides each network node j 6= r with the total expected incoming rate strictly larger than the packet arrival rate λ via
proper random link activations conditioned on the current
network configuration. According to our notational convention, we have
RAND

X

E[µπir

(t) | X(t)] = E[

X

RAND

µπir

(t)] = λ.

i:(i,r)∈E

i:(i,r)∈E

(55)
From (54) and (55), if node i appears before node j in the
aforementioned topological ordering, i.e., i = vli < vlj = j
for some li < lj , then

e∈EUv

Since the underlying network topology G = (V, E) is a DAG,
there exists a topological ordering of the network nodes so
that: (i) the nodes can be labelled serially as {v1 , . . . , v|V | },
where v1 = r is the source node with no in-neighbours and
v|V | has no outgoing neighbours and (ii) all edges in E are
directed from vi → vj , i < j [5]; From (52), we define
ql ∈ [0, 1] for each node vl such that
X
l
ql
ce βe∗ = λ + ǫ
, l = 2, . . . , |V |.
(53)
|V
|
e∈E
Uv
l

Consider the randomized broadcast policy π RAND ∈ Π∗
working as follows:
Stationary Randomized Policy π RAND :
(i) If the observed network-configuration at slot t is
σ(t) = σ, the policy π RAND selects 3 the feasible activation set sσk with probability ασk ;
(ii) For each incoming selected link e = (·, vl ) to node
vl such that se (t) = 1, the link e is activated independently with probability ql ;
(iii) Activated links (note, not necessarily all the selected links) are used to forward packets, subject to the
constraints that define the policy class Π∗ (i.e., in-order
packet delivery and that a network node is only allowed
to receive packets that have been received by all of its
in-neighbors).

X

RAND

E[µπki

X

RAND

E[µπkj

(t)]

k:(k,j)∈E

k:(k,i)∈E

≤−

(t)] −

ǫ
.
|V |

(56)

The above inequality will be used to show the throughput
optimality of the policy π ∗ .
The drift inequality (45) holds for any policy π ∈ Π∗ . The
broadcast policy π ∗ observes the states (X(t), σ(t)) and and
seek to greedily minimize the upper-bound of drift (47) at
every slot. Comparing the actions taken by the policy π ∗
with those by the randomized policy π RAND in slot t in (45),
we have
∗

∆π (X(t)|σ(t))
X  π∗
E µij (t) | X(t), σ(t)]Wij (t)
≤ B|V | − 2

(57)

(i,j)∈E

≤ B|V | − 2

X

(i,j)∈E
(∗)

= B|V | − 2

X

 RAND
E µπij
(t) | X(t), σ(t)]Wij (t)

(i,j)∈E

 RAND
E µπij
(t) | σ(t)]Wij (t)

Taking Expectation of both sides w.r.t.

(58)

the stationary-

i.e.,

process σ(t) and rearranging, we have
∗

∆π (X(t))

(59)
X

≤ B|V | − 2

E

(i,j)∈E

≤ B|V | + 2

X



Xj (t)

j6=r

Xj (t) − cmax ET ≤ EXj′ (t) ≤ Xj (t)

X

m∈V

2ǫ X
Xj (t).
≤ B|V | −
|V |

Where the expectation is with respect to the random update

fashion, since every in πRAND  X  πRAND  process at the node j. In a similar
neighbour i of a node k ∈ ∂ out (j), is at most 2-hop away
E µkj
(t)
E µmi∗t (t) −
from the node j, we have
k∈V
(60)

Ri (t) − T cmax ≤ Ri′ (t) ≤ Ri (t)

j6=r

Note that i∗t = arg mini∈In(j) Qij (t) for a given node j. Since
node i∗t is an in-neighbour of node j, i∗t must lie before j in
any topological ordering of the DAG. Hence, the last inequality of (60) follows directly from (56). Taking expectation in (60) with respect to X(t), we have




2ǫ
E L(X(t + 1)) − E L(X(t)) ≤ B|V | −
E||X(t)||1 ,
|V |

where || · ||1 is the ℓ1 -norm of a vector. Summing the above
inequality over t = 0, 1, 2, . . . T − 1 yields
T −1
2ǫ X
E L(X(T )) − E L(X(0)) ≤ B|V |T −
E||X(t)||1 .
|V | t=0





(64)

RAND
µπij
(t)]Wij (t)





Dividing the above by 2T ǫ/|V | and using L(X(t)) ≥ 0, we
have
T −1
1 X
B|V |2
|V | E[L(X(0))]
E||X(t)||1 ≤
+
T t=0
2ǫ
2T ǫ

Rk (t) − T cmax ≤ Rk′ (t) ≤ Rk (t)
It follows that for all i ∈ ∂ in (k)
(Ri (t) − Rk (t)) − T cmax

≤
≤

Ri′ (t) − Rk′ (t)
(Ri (t) − Rk (t)) + T cmax

Hence,
Xk (t) − T cmax ≤ Xk′ (t) ≤ Xk (t) + T cmax
Again taking expectation w.r.t. the random packet-state
update process,
Xk (t) − cmax ET ≤ EXk′ (t) ≤ Xk (t) + cmax ET

(65)

Combining Eqns (64) and (65) using Linearity of expectation
and using Eqn. (23) we have

Taking a lim sup of both sides yields
T −1
B|V |2
1 XX
E[Xj (t)] ≤
T t=0 j6=r
2ǫ

Also,

(61)

−ncmax ET + Wij (t) ≤ EWij′ (t) ≤ Wij (t) + ncmax ET

which implies that all virtual-queues Xj (t) are strongly stable [18]. Strong stability of Xj (t) implies that all virtual
queues Xj (t) are rate stable [18, Theorem 2.8].

Thus the lemma (7) follows with C ≡ ncmax ET < ∞.

9.7 Proof of Lemma (6)

To prove throughput-optimality of TheoremP
(5.1), we work
with the same Lyapunov function L(X(t)) = j6=r Xj2 (t) as
in Theorem (4.1) and follow the same steps until Eqn. (47)
to obtain the following upper-bound on conditional drift

lim sup
T →∞

Proof. Recall the definition of the policy-space Π∗ . For
every node i, since Ri (t) is a non-decreasing function of t, if
a packet p is allowed to be transmitted to a node j at time
slot t, by the policy π ′ , it is certainly allowed to be transmitted by the policy π. This is because Ri′ (t) ≤ Ri (t), ∀j ∈
∂ out (i) and hence outdated state-information may only prevent transmission of a packet p at a time t, which would
otherwise be allowed by the policy π ∗ . As a result, the policy π ′ can never transmit a packet to node j which is not
present at all in-neighbours of the node j. This shows that
π ′ ∈ Π∗ .

9.8 Proof of Lemma (7)

9.9 Proof of Theorem (5.1)

′

∆π (X(t)|X(t), X ′ (t), σ(t))
X
′
Wij (t)E(µπij (t)|X(t), X ′ (t), σ(t))
≤ B|V | − 2
(i,j)∈E

(66)

Since the policy π ′ makes scheduling decision based on the
locally computed weights Wij′ (t), by the definition of the policy π ′ , we have for any policy π ∈ Π:

Consider the packet-state update process at node j. Since
the capacity of the links are bounded by cmax , from Eqn.
(26) and the fact that Ri (t) is non-decreasing, we have
Ri (t) − T cmax ≤

Ri′ (t)

in

≤ Ri (t), ∀i ∈ ∂ (j)

(62)

(63)

′

Wij′ (t)E(µπij (t)|X(t), X ′ (t), σ(t))

(i,j)∈E

≥

Hence, from Eq. (19), it follows that
Xj (t) − T cmax ≤ Xj′ (t) ≤ Xj (t)

X

X

Wij′ (t)E(µπij (t)|X(t), X ′ (t), σ(t))

(67)

(i,j)∈E

Taking expectation of both sides w.r.t. the random update
process X ′ (t), conditioned on the true network state X(t)

and the network configuration σ(t), we have
X
π′
Wij (t)E(µij
(t)|X(t), σ(t))
Cn2 cmax /2 +

Since the above holds for any stationary randomized policy
π, we conclude
λ∗stat ≤

(i,j)∈E

(a)

≥

′

2
5

(69)



X

EWij′ (t)E(µπij (t)|X(t), σ(t))

X

EWij′ (t)E(µπij (t)|X(t), σ(t))

r

a

b

r

a

b

X

Wij (t)E(µπij (t)|X(t), σ(t)) − Cn2 cmax /2

c

d

e

c

d

e

f

g

h

f

g

h

(i,j)∈E
(b)

≥

(i,j)∈E
(c)

≥

(i,j)∈E

(68)

Here the inequality (a) and (c) follows from Lemma (7) and
the fact that |E| ≤ n2 /2 and µij (t) ≤ cmax . Inequality (b)
follows from Eqn. (67). Thus from Eqn. (66) and (68), the
expected conditional drift of the Lyapunov function under
the policy π ′ , where the expectation is taken w.r.t. the random update and arrival process is upper-bounded as follows:
X
′
Wij (t)E[µπij (t) | X(t), σ(t)]
∆π (X(t)|X(t), σ(t)) ≤ B ′ − 2

Matching M1

(i,j)∈E

′

Matching M2

r

a

b

r

a

b

c

d

e

c

d

e

f

g

h

f

g

h

2

with the constant B ≡ B|V | + 2Cn cmax . Since the above
inequality holds for any policy π ∈ Π, we can follow the
exactly same steps in the proof of Theorem (4.1) by replacing
an arbitrary π by π RAND and showing that it has negative
drift.

Matching M3

9.10 Proof of Proposition 6.1

r

Like many proofs in this paper, this proof also has a converse and an achievability part. In the converse part, we
obtain an upper bound of 25 for the broadcast capacity λ∗stat
of the stationary grid network (i.e. when all links are ON
w.p. 1). In the achievability part, we show that this upper
bound is tight.

Part (a): Proof of the Converse: λ∗stat ≤

b

fra ≥ λ, fab ≥ λ
Applying the primary interference constraint at node a, we
then obtain
fad ≤ 1 − 2λ
Because of symmetry in the network topology, we also have
fcd ≤ 1 − 2λ.
However, to achieve a broadcast capacity of λ, the total
allocated rate towards node d must be atleast λ. Hence we
have,

c

d

e

f

g

c

h

f

Matching M5

2
5

a

b
2
5

1
5

2
5

1
5

2
5

d

e

0
0

g

0
2
5

h

‘Time averaged’ Network

Figure 5: Some feasible activations of the 3 × 3 grid
network which are activated uniformly at random.
The components corresponding to each edge in the
resulting overall activation vector β is denoted by
the numbers alongside the edges.

Part (b): Proof of the Achievability: λ∗stat ≥ 25 :
As usual, the achievability proof will be constructive. Consider the following five activations (matchings) M1 , M2 , . . . , M5
of the underlying graph as shown in Figure 5. Now consider
a stationary policy π ∗ ∈ Π∗ that activates the matchings
M1 , . . . , M5 at each slot uniformly at random with probability 51 for each matching. The resulting ‘time-averaged’
graph is also shown in Figure 5. Using Theorem 3.1, it is
clear that λ∗stat ≥ 25 . Combining the above with the converse
result in Eqn. (69), we conclude that,
λ∗stat =

2
.
5

2
5

2
5

i.e.
λ≤

r

2
5

We have shown earlier that for the purpose of achieving
capacity, it is sufficient to restrict our attention to stationary
randomized policies only. Suppose a stationary randomized
policy π achieves a broadcast rate λ and it activates edge
e ∈ E at every slot with probability fe . Then for the nodes
a and b to receive distinct packets at rate λ, one requires

2(1 − 2λ) ≥ λ

a

Matching M4



2
5

