1

Dynamic Network Control for Confidential
Multi-hop Communications

arXiv:1301.1002v2 [cs.IT] 14 Sep 2015

Yunus Sarikaya, C. Emre Koksal, Ozgur Ercetin

Abstract—We consider the problem of resource allocation
and control of multihop networks in which multiple sourcedestination pairs communicate confidential messages, to be kept
confidential from the intermediate nodes. We pose the problem as
that of network utility maximization, into which confidentiality
is incorporated as an additional quality of service constraint.
We develop a simple, and yet provably optimal dynamic control
algorithm that combines flow control, routing and end-to-end
secrecy-encoding. In order to achieve confidentiality, our scheme
exploits multipath diversity and temporal diversity due to channel
variability. Our end-to-end dynamic encoding scheme encodes
confidential messages across multiple packets, to be combined at
the ultimate destination for recovery. We first develop an optimal
dynamic policy for the case in which the number of blocks across
which secrecy encoding is performed is asymptotically large.
Next, we consider encoding across a finite number of packets,
which eliminates the possibility of achieving perfect secrecy. For
this case, we develop a dynamic policy to choose the encoding
rates for each message, based on the instantaneous channel
state information, queue states and secrecy outage requirements.
By numerical analysis, we observe that the proposed scheme
approaches the optimal rates asymptotically with increasing
block size. Finally, we address the consequences of practical
implementation issues such as infrequent queue updates and
de-centralized scheduling. We demonstrate the efficacy of our
policies by numerical studies under various network conditions.

I. I NTRODUCTION
In some scenarios (e.g., tactical, financial, medical), confidentiality of communicated information between the nodes
is necessary, so that data intended to (or originated from) a
node is not shared by any other node. Even in scenarios in
which confidentiality is not necessary, it may be dangerous to
assume that nodes will always remain uncompromised. Keeping different nodes’ information confidential can be viewed as
a precaution to avoid a captured node from gaining access to
information from other uncaptured nodes.
In this paper, we consider wireless networks in which
messages are carried between the source destination pairs cooperatively in a multi-hop fashion via intermediate nodes. In a
multihop network, as data packets are transferred, intermediate
nodes obtain all or part of the information through directly
forwarding data packets or overhearing the transmission of
Preliminary version of this paper appeared in Intl. Symposium on Modeling
and Optimization in Mobile, Ad Hoc, and Wireless Networks, May 2013.
This work was supported in part by European Commission under Marie
Curie IRSES grant PIRSES-GA-2010-269132 AGILENet.
Y.Sarikaya (email: sarikaya@su.sabanciuniv.edu) and O. Ercetin (email:
oercetin@sabanciuniv.edu) are with the Department of Electronics Engineering, Faculty of Engineering and Natural Sciences, Sabanci University, 34956
Istanbul, Turkey.
C. E. Koksal (koksal@ece.osu.edu) is with the Department of Electrical
and Computer Engineering at The Ohio State University, Columbus, OH.

1
2

s1

d1

3

s2
(a) Diamond Network
Fig. 1.

4

d2

(b) A multi-hop network.

Network Models

nearby nodes. This poses a clear problem when transferring
confidential messages. In this paper, we build efficient algorithms for confidential multiuser communication over multihop
wireless networks without the source-destination pairs having
to share any secret key a priori. The metric we use to measure
the confidentiality is the mutual information leakage rate to the
relay nodes, i.e., the equivocation rate. We require this rate to
be arbitrarily small with high probability and impose this in
the resource allocation problem via an additional constraint.
To provide the basic intuition behind our approaches and
how the source nodes can achieve confidentiality from the
relay nodes, consider the following simple example of a
diamond network given in Fig. 1a. Let the source node have
a single bit of information to be transmitted to the destination
node, with perfect secrecy (with 0 mutual information leaked)
from the relay nodes 1 and 2. The issue is that, the source
cannot transmit this bit directly over one of the possible
paths (through 1 or 2), since either 1 or 2 would obtain it,
violating the confidentiality constraint. This problem can be
solved by adding random noise (i.e., randomization bit) on the
information bit, and sending the noise and the noise corrupted
message over different paths, which can then be combined at
the destination. The details of the process is as follows:
(1) Let b denote the information bit. The source generates a
noise bit N at random, with P (N = 0) = P (N = 1) = 21 .
(2) Source node transmits N to relay 1 and b ⊕ N to relay 2.
Then, the relay nodes forward these bits to the destination.
(3) Destination node reconstructs the original bit by a simple
xor operation: b = N ⊕ (b ⊕ N).
Note that with the information available to the relay nodes,
there is no way that they can make an educated guess about
the information bit, since they have zero mutual information:
I(b; N) = I(b; N ⊕ b) = 0. Full confidentiality is achieved here
at the expense of halving of the data rate, i.e., for each
information bit the source has, the network has to carry two

2

bits to the destination.1 Furthermore, one can see that the
existence of multiple paths from the source to the destination
is crucial to achieve perfect secrecy. However, a source cannot
route confidential information arbitrarily over the relay nodes.
Hiding information from the other nodes can be made possible
by a careful design of end-to-end coding, data routing on top
of other network mechanisms, flow control and scheduling in
order for an efficient resource utilization. Clearly, the example
is highly simplistic and ignores many important issues, which
we explicitly consider in this paper. In particular:
(a) To achieve confidentiality, one needs to encode blocks
of information across multiple packets. We develop a novel
adaptive end-to-end encoding scheme, that takes certain observations from the network and chooses the appropriate code
rate to maintain confidentiality for each block of data.
(b) In a multihop network, each node possibly overhears the
transmission of a packet multiple times as it is transmitted
over multiple hops. We take into account such accumulation
of information over multiple transmissions. Thus, we need to
go beyond the scenario given in Fig. 1a, in which the paths are
disjoint and each intermediate node has only one path crossing.
(c) We combine a variety of strategies developed in the
context of information theoretic secrecy with basic networking
mechanisms such as flow control and routing. Such a unifying
framework is non-existent in the literature as it pertains
to multihop information transmission. For that purpose, we
model the entire problem as that of a network utility maximization, in which confidentiality is incorporated as an additional
constraint and develop the associated dynamic flow control,
routing, and scheduling mechanisms.
(d) We take into account wireless channel variations in our
scheduling and routing policies as well as end-to-end encoding
scheme for confidentiality. For that purpose, we assume that
transmitters have perfect instantaneous channel state information (CSI) of their own channels.
Attacker model: Each attacker is capable of tapping into all
the information transmitted and received by a single intermediate node. Attackers are not capable of changing the content
of the information the node forwards, nor do they inject phantom messages into the network. In our model, intermediate
nodes are entities, compliant with network operations as they
properly execute algorithms, but the messages need to be kept
confidential from them.
We address the problem in two parts. In the first part, we
ignore the delay issue and consider the possibility of encoding
across multiple blocks of information in order to maximize the
confidential data throughput. For any given encoding rate (not
necessarily optimized for the network conditions), we provide
a dynamic network control scheme that achieves a utility, close
to the maximum achievable utility (for that particular encoding
rate), subject to perfect secrecy constraint.
1 It can be proved that this scheme achieves the secrecy capacity of the
diamond network, i.e., there exists no other scheme with which one can
achieve a rate higher than 1 bit/channel use with perfect secrecy from the
relay nodes. In general in a network with m parallel and independent paths,
ith path with capacity identical to Ci , the secrecy capacity is identical to
Cs = ∑m
i=1 Ci − maxi≤m Ci , hence the sum rate minus the rate along the best
relay.

The problem of network control with confidential messages
has been studied (as shall be discussed in the next section),
in the past for the single-hop setting. The main additional
challenges involved in generalizing this problem to multihop
networks are dynamic end-to-end encoding and multipath
routing. Standard dynamic control algorithms give control decisions in each time slot independently by assuming time-scale
separation, i.e., independent transmissions of subsequent slots
[1]. The confidential message is encoded across many blocks,
which implies that the time-scale involved in physical-layer
resource allocation cannot be decomposed from the time scales
involved in network-layer resource allocation, eliminating the
time-scale separation assumption of standard dynamic control
algorithms. A similar problem was previously addressed in
[2], where the users leave (arrive) the system, e.g., whenever
their queues empty (has one packet arrival). However, the
network makes a control decision only at the slot boundaries,
delaying the network response for at most one slot duration.
On the other hand, in our system, due to the encoding of the
confidential messages into many blocks, the network decisions
made at every slot become dependent with each other. This
poses new and fairly different challenges in addressing the
separation of time scales. Here, in order to design a crosslayer dynamic control algorithm, source needs to keep track
of the rate of information obtained by each intermediate node
during the transmission of encoded confidential message, and
this information is required to be quantified over each time slot
independently. In addition, the existing schemes for wireless
multihop networks are not concerned with how information
ought to be spatially distributed in the network [3], [4].
Additional “virtual” queues need to be maintained to keep
track of the leaked information to other nodes in the network to
make sure that information from the source node is sufficiently
spatially distributed in the network. Hence, unlike the standard
multihop dynamic algorithm where the objective is to only
increase end-to-end flow rates, in our problem, increasing the
flow rate and keeping confidentiality of the messages appear
as two conflicting objectives.
In the second part, we consider practical delay requirements
for each user, which eliminates the possibility of encoding
over an arbitrarily long block. Due to finite codewords, subsequent blocks associated with a given secrecy-encoded message
cannot be decoupled. Also, the network mechanism cannot
react to an undesirably large rate of accumulation at a given
node at a time scale faster than the number of blocks across
which the message is encoded. For the same reason, achieving
perfect secrecy for all confidential messages is not possible.
Consequently, we define the notion of secrecy outage, and
impose a probabilistic constraint on the probability that a
message experiences a secrecy outage. We develop a dynamic
policy to choose the encoding rates for each message, based
on the instantaneous channel state information, queue states
and secrecy outage requirements. We demonstrate that our
proposed scheme approaches the maximum achievable rates
asymptotically, with increasing block size.
Finally, we investigate some practical implementation issues. In particular, we consider the case where queue length
information is exchanged among the nodes not at every block

3

but every K > 1 blocks in order to reduce the control overhead.
We show that our proposed algorithm still achieves asymptotic
optimality but with longer average queue lengths. Another
important practical limitation is the unavailability of a centralized scheduler. Hence, we propose a distributed scheduling
algorithm, and investigate its performance via simulations,
since the optimality can no longer be guaranteed.
II. R ELATED W ORK
Since the pioneering work of Wyner [5], there has been
a wide interest on the variations of the wiretap channel and
how to provide secrecy in various multiuser and network
information theoretic scenarios, mainly under the single hop
setting. To give a few examples on the single hop setting,
in [6], [7], opportunistic secrecy was introduced, which allows
for the exploitation of channel variations due to fading to
achieve secrecy, even when the eavesdropper has a higher
average signal-to-noise ratio (SNR). Achieving delay-limited
secrecy and outage capacity of the wiretap channel were
studied in [8]. The use of multiple antennas for secrecy
under a variety of assumptions has been considered in [9],
[10]. Multiuser communication with secrecy using cooperative
jamming and relaying in the presence of eavesdropper was
studied in [11].
In the multihop setting, [12], [13] studies the secrecy
capacity scaling problem. Exploitation of path diversity in
order to achieve secrecy from external eavesdroppers is studied
in [14] and for secrecy via mobility in [15]. In [16] a method
is given that modifies any given linear network code into a
new code that is secure requiring a large field size. Later, [17]
generalized and simplified the method in [16], and showed
that the problem of making a linear network code secure is
equivalent to the problem of finding a linear code with certain
generalized distance properties. Along the same lines, [18]
investigates secure communication over wireline networks
where a node can observe one of an arbitrarily selected
collection of secure link sets. In [19], a different notion of
security referred to as packet-level security is used, where it
is sufficient that the eavesdropper does not correctly decode
the message, i.e., it does not guarantee full equivocation. In
addition, [19] assumes availability of private secure channels
between source and destination nodes that are not accessible
to the eavesdropper, but are more costly. The objective is to
minimize the use of private channels subject to a required
level of security in order to understand the trade-off between
the security level and the cost incurred by security.
Despite the significant progress in information theoretic
secrecy, most of the work has focused on physical layer
techniques. There has been only a few studies on wireless network control and protocol design with secrecy/confidentiality
as a constraint on the transmitted information. Therefore,
our understanding of the interplay between the confidentiality
requirements and the critical functionalities of wireless networks, such as scheduling, routing, and congestion control
remains limited. There are a few number of works on secure
multi-hop communications. In [20], a particular wireless relay
network called the fan network is studied, where the signal

sent by a source node can be heard by all relays via different
outputs of a broadcast channel. All the relay nodes are then
connected to the destination via a perfect channel by which
destination can obtain received signal from all relays without
a delay. [21] considers the secret communication between a
pair of source and destination nodes in a wireless network
with authenticated relays, and derives achievable secure rates
for deterministic and Gaussian channels.
Recently, in [22], we have investigated the cross-layer
resource allocation problem with confidentiality in a cellular
wireless network, where users transmit information to the base
station, confidentially from the other users. In this paper, we
consider a general multi-hop network topology and develop
dynamic network control algorithms to jointly determine the
end-to-end encoding rates, scheduling and routing.
III. S YSTEM M ODEL
We consider a multi-hop wireless network with M sourcedestination node pairs communicating with each other via intermediate relay nodes. Let S and D be the sets of information
ingress and egress nodes in the network, respectively. There
is no direct connection between the nodes in S and D, and
messages from a source node to the intended destination node
are relayed by intermediate nodes in the network. Let E be the
set of intermediate nodes which are untrusted and/or prone to
be compromised by an external attacker, i.e., E denotes the set
of eavesdroppers among intermediate nodes. Note that we may
have some trusted intermediate nodes in the network. Thus, the
set of all intermediate nodes may not be the same as the set
of eavesdroppers, E. For ease of exposition, we consider a set
of logical links, L, connecting the nodes in the network, i.e.,
nodes i and j can communicate only if link (i, j) ∈ L.
Each source node in S aims to keep its information confidential from the nodes in the set of E. To that end, a source
node precodes its message, divides it into multiple pieces, and
sends separate pieces over different paths to the destination.
Henceforth, none of the intermediate relay nodes in the set of
E will accumulate sufficient amount of information to decode
the confidential message, even in part.
We assume every channel to be i.i.d. block fading, with a
block size of N1 channel uses (physical-layer symbols) where
N1 is sufficiently large to allow for invoking random coding
arguments with arbitrarily low error probability. We denote the
instantaneous achievable rate of the channel between nodes i
and j in block t by Ri j (t), where Ri j (t) is the maximum mutual
information between the output symbols of node i and input
symbols of node j. We assume that the nodes are capable of
obtaining perfect instantaneous CSI. Even though our results
are general for all channel state distributions, in numerical
evaluations, we use Gaussian channels, as will be described
in Section VIII.
We assume the wireless transceivers to operate in a half
duplex fashion, i.e., a node cannot transmit and receive simultaneously. Hence, two links sharing a common ingress or
egress node cannot be active simultaneously. We define a set of
links that can transmit simultaneously as a set of concurrently
active links indexed by v. Also, let V be the collection of
all sets of concurrently active links. Set V depends on the

4

assumed interference model. 2 For example, consider a sample
multi-hop network as shown in Fig. 1b with node-exclusive
interference model. Examples of sets of concurrently active
links include {(s1 , 1), (s2 , 4), (2, d1 )}, {(s1 , 1), (s2 , 4), (2, d2 )},
{(s1 , 2), (1, d1 ), (4, d2 )}, and {(s2 , 3), (1, d1 ), (4, d2 )}. At the
beginning of every block, the scheduler chooses a particular set
of concurrently active links. We use indicator variable Iv (t) to
represent the scheduler decision, where Iv (t) is one if set v is
scheduled for transmission in block t, and it is zero otherwise.
By definition, ∑v∈V Iv (t) ≤ 1 for all t > 0.
There are M different flows in the network, one for each
source-destination node pair. Each flow in the network is
identified by the index of its ingress node, and thus, the
network flow problem considered in this work can be modeled
as a multi-commodity flow problem. Let Iisj (t) be an indicator
function taking a value of 1, if link (i, j) carries commodity
s in block t. Hence, the total flow rate of commodity s over
link (i, j) in block t is:
(
Ri j (t), if (i, j) ∈ v, Iv (t) = 1, Iisj (t) = 1
s
µi j (t) =
. (1)
0,
otherwise

at source node s maps each confidential message ws ∈ Ws of
conf
size NRs bits to a codeword that has a length of NRs bits.
Thus, we refer to Rconf
as the confidential information injection
s
rate. Here, N represents the number of channel uses for the
entire session, rather than the number of channel uses, source
s is actively transmitting.3
Let the vector of symbols received by node k be Ysk .
We define perfect secrecy of message Ws as the following
constraint to be satisfied:
1
(2)
I(Ws , Ysk ) ≤ ε ,
N
for all k ∈ E for any given ε > 0.
In this paper, we focus on ergodic strategies, i.e., for all
(i, j) ∈ L and s ∈ S,
1 Ns s
lim
∑ µi j (t) = µ̄isj
Ns →∞ Ns
t=1

Due to broadcast nature of wireless communications, transmissions are overheard by unintended receivers. At every
transmission, overhearing neighboring nodes and the node
which receives information from the active link accumulate
information for each commodity s. Let k be a node overhearing a transmission of commodity s over link (i, j), i.e.,
there is a link (i, k) ∈ L. Then, whenever node k is not
active transmitting or receiving, i.e., no link originating or
terminating at node k is scheduled, it accumulates no larger
than fks,i (t) = min(Rik (t), max j6=i µisj (t)) bits of information
over block t over link (i, j), since overhearing information
cannot exceed the actual transmitted information. In Sections
V and VI, we assume that Ri j (t) is available causally at the
centralized scheduler. In the subsequent section, we relax this
assumption, and propose a distributed algorithm, i.e., nodes
determine the scheduling decision by only using their local
information.

since Ri j (t) is i.i.d. and µisj (t) is ergodic. In the following theorem, we provide the rate at which the Wyner encoder ought
to choose the encoding parameters for a given scheduling and
routing strategy.
Theorem 1: Given an ergodic joint scheduling and routing
policy confidential information injection rate achieving perfect
secrecy can be lower bounded as:
f
Rcon
≥ ∑ µ̄sis − max f¯js ,
(3)
s

IV. E ND - TO -E ND C ONFIDENTIAL E NCODING R ATES
In this section, we describe our secrecy encoding strategy
and provide an achievable confidential data rate, i.e., secrecy
rate for a given source-destination pair, when the sequence of
scheduling and routing decisions are given. We consider the
system operation over Ns blocks, which corresponds to a total
of N = N1 Ns channel uses. We will focus on the rate of secure
data transmitted by the source node and the amount of mutual
information leaked to each intermediate node by Ns blocks to
analyze the secrecy rate.
Our secrecy encoding strategy is motivated by Wyner encoding [5] to provide confidentiality, which basically inserts
a randomization message to the actual message to achieve
NRs
equivocation. Let C(Rs , Rconf
s , N) be a Wyner code of size 2
codewords, generated to convey a confidential message set
conf
Ws ∈ {1, . . . , 2NRs }. In Wyner coding, a (stochastic) encoder
2 We assume ∪
v∈V v to contain at least one path connecting any given sourcedestination pair.

for some µ̄isj ≥ 0, with probability 1. Hence, we also have for
all nodes k ∈ E and s ∈ S
1 Ns
lim
∑ ∑ fks,i (t) = f¯ks
Ns →∞ Ns
t=1 i6=k

(s,i)∈L

∀ j∈E

for each source-destination pair (s, d), as Ns → ∞.
The proof of this theorem is given in Appendix A. Note that,
the special case of Theorem 1 that holds for deterministic
channels was given in [20].
Two immediate observations one can make based on Theorem 1 are the following: First, Wyner encoder encapsulates
f
secret information of NRcon
bits into a block of NRs , which
s
are injected by the source into the network. Thus, we have:
1 Ns
∑ ∑ µsis (t) = ∑ µ̄sis .
Ns →∞ Ns
t=1 (s,i)∈L
(s,i)∈L

Rs ≤ lim

(4)

Consequently, Theorem 1 implies that, for a given joint routing
and scheduling strategy, rate

f
Rcon
≥ min Rs − f¯js
s
j∈E

can be achieved. Second, if there exists a node j ∈ E through
which all possible paths between a given source s and its
con f
destination are passing, then Rs = 0 for that source s, since
s
f¯j is identical to ∑(s,i)∈L µ̄sis for node j. This underlines the
necessity of the existence of multiple paths between a sourcedestination pair in order to achieve a non-zero confidential
data rate.
3 Thus, one should view the number of channel uses N in Wyner encoder
conf
notation C(Rs ,Rs ,N) as a parameter that specifies the number of bits,
conf
NRs , at the input and the number of bits, NRs , at the output of the encoder as
opposed to the number of channel uses that the source transmits the message.

5

Before finalizing this section, there are two important notes
we would like to make. Firstly, the theorem provides a rate
of encoding for which perfect secrecy can be achieved by an
appropriate choice of secrecy encoding for a given routing
and scheduling policy. It does not imply that an end-to-end
con f
confidential information rate of Rs
is achievable. For that,
it is important to design routing and scheduling mechanisms
that keeps all the queues in the network stable and at the
same time deliver all the packets to the destination reliably.
We will show how to achieve this in the next section. Secondly,
the rate provided in Theorem 1 is achieved as the number of
blocks Ns → ∞. This implies that, encoding for confidentiality
is done across an infinitely-long sequence of blocks.4 The
network mechanisms we provide in the next section achieve
maximum achievable rate of confidential information, also
over infinitely many blocks. Following that, we incorporate
a more practical constraint of encoding over a finite number
of blocks, imposing a hard limit on the decoding delay.
V. M ULTIHOP N ETWORK C ONTROL
C ONFIDENTIALITY

WITH

In the previous section, we provided the set of secrecy
encoding rates that enables confidentiality of information
transmitted by the source. However, we were not concerned
with whether the packets reach the destination or not and
the mechanisms that make it happen. In this section, our
objective is to develop a stationary control policy giving
joint scheduling and routing decisions that achieves end-toend confidential transmission of information. To that end, we
state a network utility maximization problem and provide
a scheme that maximizes aggregate network utility while
achieving perfect secrecy over infinitely many blocks. We
develop our solution based on the following assumptions:
A1. We consider the large block size asymptotics, i.e., secrecy encoding is across Ns → ∞ blocks.
A2. There is a centralized scheduler with the perfect knowledge of instantaneous CSI of all channels.
A3. The secrecy encoding rate is fixed: source node s uses
the C(2NRs , 2N αs Rs , N) encoder. Thus, the confidential
f
information injection rate is Rcon
= αs Rs . These rates
s
con f
{Rs , s ∈ S}, lie in the region of rates for which perfect
secrecy is achievable, as specified in Theorem 1.
Assumption A1. allows our developed mechanisms to react
to an undesirably large rate of accumulation at a given node at
a time scale faster than the number of blocks across which the
message is encoded. Assumption A2. can be achieved by nodes
sending their CSI to the centralized scheduler at the expense
of increased control overhead. Assumption A3. states that the
a priori encoding rate of the message may not maximize the
confidential throughput of the source node.
Next, we develop a dynamic algorithm taking as input
the queue lengths and the accumulated information at the
intermediate nodes, and gives as output the scheduled node
and the admitted confidential flows in to the queues of the
sources.
4 The

number of blocks need to be large enough for sufficient averaging of
the variations in the channels.

Let Us (x) be utility obtained by source s when the confidential transmission rate is x bits/channel use. We assume
that Us (·) is a continuously differentiable, increasing and
strictly concave function. There is an infinite backlog at the
transport layer, which contains the secrecy-encoded messages.
In each block, source node s determines the amount of encoded
information admitted to its queue at the network level. Let
As (t) be the amount of traffic injected into the queue of source
s at block t, and xs = limNs →∞ N1s ∑t As (t) be the long term
arrival rate. Furthermore, let Qs (t) denote the queue size at
ingress node s. Each intermediate node keeps a separate queue
Qsi (t) for each commodity s.
Definition 1: The queues at ingress or intermediate nodes
are called strongly stable if:
lim sup
T →∞

1
T

T

∑ E [Qs (t)] < ∞ and

t=0

lim sup
T →∞

1
T

T

∑ E [Qsi (t)] < ∞.

t=0

Our objective is to support a traffic demand that achieves
long term confidential rates maximizing the sum of utilities of
the sources while satisfying the strong stability of the queues.
The arrival rate, xs includes both the confidential and
randomization bits. Hence, for the arrival rate of xs , the
confidential information rate is αs xs , and source s attains a
long term expected utility of Us (αs xs ). Recall that the rate
of information obtained by any intermediate node in the set
of E should not exceed the randomization rate, (1 − αs )xs , to
ensure perfect secrecy. Hence, the optimization problem can
be defined as follows:

∑ Us (αs xs )

max

(5)

As (t),Iv (t),Iisj (t) s∈S

s.t. xs ≤

∑

µ̄sis , ∀s ∈ S

(6)

{i|(s,i)∈L}
µ̄isj −
µ̄ sji ≥ 0, ∀
{ j|(i, j)∈L}
{i|( j,i)∈L}
f¯sj ≤ (1 − αs )xs , ∀s ∈ S, ∀ j ∈ E,

∑

∑

i∈
/ S, D

(7)
(8)

Constraint (6) ensures the stability of the queues at the
source nodes; Constraint (7) is the flow conservation constraint
at the intermediate nodes; and Constraint (8) is the confidentiality constraint, implying that the requirement in (2) is met.
To solve the optimization problem (5)-(8), we employ a
cross-layer dynamic control algorithm based on the stochastic
network optimization framework developed in [1]. This framework allows the solution of a long-term stochastic optimization
problem without requiring the explicit characterization of the
achievable rate regions.5
The queue evolution equation for each queue can be stated
as follows:"
#
+

Qs (t + 1) = Qs (t) −

∑

µsis (t)

∑

µisj (t)

+ As (t),

{i|(s,i)∈L}

Qsi (t + 1)

=

"

Qsi (t) −

{ j|(i, j)∈L}

#+

+

∑

µ sji (t), ∀i 6= S, D,

{ j|( j,i)∈L}

where [.]+ denotes the projection of the term to [0, +∞). To
meet Constraint (8), we maintain a virtual queue:
5 Note that, while we know that the arrival rates lie in the region of rates
for perfect secrecy (Theorem 1), we do not know the achievable end-to-end
rates with confidentiality.

6

"

Z sj (t + 1) = Z sj (t) + ∑ f s,i
j (t) − (1 − αs )As (t)
i6= j

#+

VI. C ONFIDENTIAL M ULTIHOP N ETWORK C ONTROL
A F INITE D ECODING D ELAY C ONSTRAINT
.

(9)

Strong stability of this queue ensures that the constraint is
satisfied [1], i.e., perfect secrecy is achieved in our case. Note
that to perform the update in (9), nodes need to have access
to instantaneous CSI of all neighboring nodes.
Control Algorithm 1 (with Perfect CSI): The algorithm
executes the following steps in each block t:
(1) Flow control: For some H > 0, each source s injects
As (t) bits into its queues, where
(

As (t) = argmax HUs (αs A) − Qs (t)A +
A

∑

Z sj (t)(1 − αs )A

j∈E

)

.

(2) Scheduling: In each block, t, the scheduler chooses the
set of links v if Iv (t) = 1 and flow s on the link (i, j) ∈ v
if Iisj (t) = 1, where
(s,v) = argmax
s∈S,v∈V

(

∑

(i, j)∈v

(Qsi (t) − Qsj (t)) µisj (t) −

∑ ∑ Z sj (t) f js,i (t)

j∈E i6= j

)

.

Optimality of Control Algorithm: Now, we show that our
proposed dynamic control algorithm can achieve a performance arbitrarily close to the optimal solution while keeping
the queue backlogs bounded.
Theorem 2: If Ri j (t) < ∞ for all (i, j) links and for all t
blocks, then control algorithm satisfies:
lim inf
t→∞

lim sup
t→∞

lim sup
t→∞

1 t−1
B
∑ E [Us (τ )] > U ∗ − H
t τ∑
=0 s∈S
1 t−1
B + H(Ū −U ∗ )
E [Qs (τ )] 6
∑
∑
t τ =0 s∈S
ε1

1 t−1
B + H(Ū −U ∗ )
E [Qsi (τ )] 6
∑
∑
∑
t τ =0 s∈S i∈S,D
ε2
/

where B, ε1 , ε2 are positive constants, U ∗ is the optimal aggregate utility, i.e., the solution of (5-8), and Ū is the maximum
possible instantaneous aggregate utility.
The proof of Theorem 2 is given in Appendix B. This
theorem shows that it is possible to get arbitrarily close to the
optimal utility by choosing H sufficiently large at the expense
of proportionally increased average queue sizes. However,
since all queues remain bounded, the destination is receiving
packets at the rate as they are injected at the source as Ns → ∞.
To finalize this section, we note that, while we count
on the secrecy encoding rates to lie in the region specified
in Theorem 1, we do not claim any rate in that region is
satisfied by our scheme. In fact, we do not specify the set of
achievable rates for our problem. However, we show that, our
scheme achieves the maximum achievable region of end-toend rates. The main significance of the algorithm presented in
this section is that, it can be considered as a benchmark against
which all other algorithms developed with one or more of the
assumptions A1.-A3. relaxed can be compared.

WITH

In Section V, we propose a dynamic control algorithm
associated with end-to-end secrecy encoding, where messages
are encoded over infinitely many blocks. Hence, the decoding
delay of confidential message may be infinitely long. In
this section, we consider a more practical case by removing
Assumption A1., i.e., there is a hard constraint on the number
of blocks a given confidential message is encoded, Ns < ∞.
The entire data including actual confidential bits and the
randomization bits sent by source s is Ns Rs , where Rs is
defined as before. We assume that the length of the message
Ns Rs is determined a priori based on the required end-toend delay between the source and destination nodes. We also
remove Assumption A3., where end-to-end confidential data
con f
rate may not be in general equal to Rs .
Unlike the infinite-block case, since a message is encoded
across a finite number of blocks, subsequent packets associated
with a given secrecy encoded message cannot be decoupled.
Therefore, achieving perfect secrecy for all messages is not
possible. Hence, we define the notion of secrecy outage. We
say that a secrecy outage event occurs, when the confidential
message is intercepted by any intermediate node, i.e., the
perfect secrecy constraint (2) is violated. Secrecy outages can
be completely avoided in the infinite-block scenario, since the
network mechanisms can react to an undesirably large rate
of accumulation at a given node at a time scale faster than
the number of blocks across which the message is encoded.
However, here, the reaction time may be too slow and the
accumulated information at a node may already exceed the
threshold for perfect secrecy. Consequently, rather than perfect
secrecy, we impose a constraint on the event that a message
experiences a secrecy outage. In particular, we assume that,
each source has the knowledge of the amount of accumulated
information at the intermediate nodes for its messages, so it
can identify (but not necessarily avoid) the occurrence of the
event of secrecy outage.On the other hand, unlike the infiniteblock case, each of the messages encoded across finite number
of blocks, k, can be encoded with a different confidential rate
k,con f
Rs
, determined based on the history of prior messages
experiencing secrecy outages. Thus, a scheme can adaptively
vary its confidential data rate to improve the performance.
As in Section V, our objective is to maximize the aggregate
long-term confidential utility of K source-destination pairs. Let
p
xs be the average rate of confidential messages injected into
k,con f
the queue of the source node s, pout
) be the longs (Rs
term average of secrecy outages of the message k of source
k,con f
node s when encoded with confidentiality rate Rs
, and γs
be the maximum allowable portion of actual confidential bits
experiencing secrecy outage. We consider the solution of the
following optimization problem:

k,con f

Rs

max

f
s. t. xsp ≤ R̄con
s

R̄out
s

∑ U(xsp)

(10)

,Iv (t),I jis (t) s∈S

≤

f
γs R̄con
s

(11)
(12)

7
infinite backlog

confidential packet queue
p

Q (t)
s

if Ps (t)=0

p

Ps (t)

k,priv

Ns R s

A (t)
s

Flow Control

Fig. 2.

(
Ns Rs
i+
Ps (t + 1) = h
Ps (t) − ∑i|(s,i)∈L µsis (t)

partial packet queue

End−to−end Encoding

Queues in a source node used for Control Algorithm 2.

∑

µ̄isj −

{ j|(i, j)∈L}

∑

µ̄isj ≥ 0,

(13)

k,con f
f
R̄con
= limK→∞ K1 ∑K
s
k=1 Rs
k,con f out k,con f
1
K
ps (Rs
).
limK→∞ K ∑k=1 Rs

and

R̄out
s

=

Constraint (11) ensures that the long-term service rate is
larger than the long-term arrival rate; Constraint (12) ensures
that the portion of the actual confidential bits experiencing
secrecy outage is lower than γs ; and Constraint (13) is for the
flow conservation at intermediate nodes.
Once again, we employ a cross-layer dynamic control algorithm based on the stochastic network optimization framework
to solve the optimization problem (10-13). Clearly, in this
problem, since the message is encoded across a finite number
of blocks, a control decision given in a time slot depends on
the decisions of the same message given in the subsequent
time slots. Thus, the optimality of dynamic control algorithms
cannot be claimed. In the following, we develop a sub-optimal
solution which performs scheduling by treating the messages
as if they are infinite length messages, but at the same time
chooses confidential encoding rates of individual messages by
keeping account of information experiencing secrecy outages.
The source node s has two separate queues operating at
two different time scales as illustrated in Fig. 2. The first
queue stores the confidential information that has been neither
secrecy-encoded nor transmitted in previous blocks. Let Qsp (t)
denote the length of the confidential information queue at
block t. In every block t, Asp (t) confidential bits are admitted
into the queue, where xsp is the long term average rate of
admitted confidential bits. Departures from this queue occur
only when a new secrecy-encoded message is created. Let
ks (t) be the number of secrecy-encoded messages created by
block t. The ks (t)th confidential message is encoded with
k (t),con f
rate Rs s
, so the actual confidential bits in the message
k (t),con f
is Ns Rs s
whereas the complete length of the encoded
message including the randomization bits is always Ns Rs
for every secrecy-encoded message. Once a new confidential
message is created, it is admitted to the second queue, which
stores the bits of partially transmitted confidential message
ks (t). Let Ps (t) denote the size of this partial message queue
at block t. The departures from this queue may occur at
any block t depending on the outcome of the scheduling and
routing decisions. A new secrecy-encoded message is admitted
to the queue only when the partial message queue has emptied,
i.e., Ps (t) = 0. Hence, ks (t + 1) = ks (t) + 1, if Ps (t) = 0. The
evolution of the states of the queues at each source s can be
stated as:
=

i
k (t+1),con f +

Qsp (t) − Ns Rs s

Qsp (t) + Asp (t),

.

At every intermediate node, there is a queue for each source
s. Let Qsi (t) denote the size of the queue at intermediate node
j for source s. Then, we have
"
#+
Qsi (t + 1) = Qsi (t) −

∑

µisj (t)

+

j|(i, j)∈L

∑

µ sji (t).

j|( j,i)∈L

In order to determine the occurrence of secrecy outages,
each source keeps track of the accumulated information at each
intermediate node (we address this issue in the next section).
Let Zis (t) be the number of bits that must be accumulated by
intermediate node i to decode the ks (t)th confidential message
of source s at block t. Note that a secrecy outage occurs in
ks (t)th message, if Zis (t) = 0 for any intermediate node i.

(Rs − Rsks (t+1),con f )Ns
if Ps (t) = 0
i+
.
Zis (t + 1) = h s
s,
j
 Zi (t) − ∑ j6=i fi (t)
otherwise

The constraint in (12) can be represented by a virtual queue,
which keeps account of confidential information experiencing
f
secrecy outages. Hence, there is only an arrival of Rk,con
if
s
kth message has undergone secrecy outage.

h
i+
 Ysk + Rsk,con f − γs Rsk,con f
if outage in kth message
k+1
i+
= h
Ys
k,con
f
 Yk −γ R
if no outage in kth message
s s
s

+ Asp (t)

if Ps (t) = 0,
otherwise

,

.

Arrivals and departures to this virtual queue are the number
of the confidential bits undergoing secrecy outage and the
number of confidential bits allowed to undergo outage as
given by the outage constraint, respectively. The state of the
virtual queue at any given point is an indicator of the amount
by which we have exceeded the allowable secrecy outage
constraint. Thus, the larger the state of this queue, the more
conservative our dynamic algorithm has to get toward meeting
these constraints, i.e., it encodes the message with less amount
k (t),conf
of confidential information, Rs s
in ks (t)th message.
Control Algorithm 2 (with Finite Encoding Block):
For each source s:
(1) End-to-end Encoding: At every generation of new confidential message, i.e., Ps (t) = 0, let ks (t + 1) = ks (t) + 1,
and determine end-to-end confidential encoding rate:
n
o
k (t)
k (t+1),con f
γ
(r)
−
r
Rs s
= argmax Qsp (t)r − Ys s rpout
s
s
r

(2) Flow control: At each block t, for some H > 0, each
source s injects Asp (t) confidential bits into its queues

Asp (t) = argmax HUs (a) − Qsp (t)a .
a

(3) Scheduling: At each block, t , the scheduler chooses
the set of links e if Iv (t) = 1 and flow s on the link
(i, j) ∈ v if Iisj (t) = 1, where
(s, e) = argmax
s∈S,v∈V

(h

otherwise

{i|(i, j)∈L}

where

Qsp (t + 1)

if Ps (t) = 0

+

∑

(i, j)∈v



(

Rs

∑

Q p (t) + Ps (t) − Qsi (t)
k (t),con f s
Rs s

(s,i)∈v

Qsi (t) − Qsj (t)



µisj (t) −

∑∑

j∈E i6= j

Z sj (t) f s,i
j (t)

)

!

µsis (t)

8

k (t),con f

and Qsp (t) is multiplied by Rs /Rs s
in order to
normalize it to the size of other queues in the network.
Note that the long-term average of secrecy outages pout
s (R)
can only be calculated if the scheduling decisions are known
a priori. Since this is not the case, we use an estimate
of secrecy outage probability as discussed in Section VIII.
Note that, pout
s (R) is an increasing function of R, since as
R increases, each confidential message is encoded with less
randomization rate, and an intermediate node may intercept
the confidential message with higher probability. Thus, the
k (t),con f
end-to-end encoding rate, Rs s
increases as the length
of confidential information queue, Qsp (t), increases but it
k (t)
decreases as the length of the virtual queue, Ys s , increases.
Finally, we would like to re-iterate that, Control Algorithm 2
does not guarantee obtaining the optimal solution of (10) - (13)
due to the dependance of decisions between subsequent blocks.
We verify by extensive numerical analysis that its performance
is still close to the optimal in a variety of scenarios.
VII. R EDUCING

OVERHEAD AND D ISTRIBUTED
I MPLEMENTATION
The algorithms presented in the Section V and VI solve
constrained optimization problems in a centralized fashion.
The centralized algorithms provide an upper bound on the
network performance, which can be used a benchmark to evaluate the performance of distributed algorithms. In this section,
we design algorithms relaxing the assumptions necessary for
Control Algorithm 1, where the instantaneous queue length
information is not available and/or a centralized scheduler is
absent in the network. Note that the flow control portions of
the algorithms provided in the previous sections were already
distributed, i.e, each node decides its admitted flow by only
local information. Thus, they remain the same as given in
Section V, in the rest of the sequel.
THE

A. Infrequent Queue Length Updates
In this section, we consider the setup described in Section V,
and relax the assumption of the availability of the queue
state information of each node at every point in time. Indeed,
scheduling requires a significant overhead due to control
traffic carrying the queue length information across the entire
network. To reduce this overhead, we consider transmission
of queue length information not in every slot, but once every
K slots. Let Q̂s (t) and Q̂si (t) denote the estimates of the queue
lengths at source s and at node i for commodity s, respectively,
at time t. Furthermore, let Ẑis (t) denote the estimate of the
virtual queue at node i used for the accumulated information
about commodity s. In particular, these estimates are the last
updates of the queue lengths, prior to time t, received by the
scheduler. Further, suppose that at each time slot, the scheduler
gives the routing decision according to the solution of the
following equation:
)
(
(s, v) = argmax
s∈S,v∈V

∑

(Q̂si (t) − Q̂sj (t))µisj (t) −

(i, j)∈v

∑ ∑ Ẑ sj (t) f s,i
j (t)

.

Theorem 3: If Ri j (t) < ∞ for all (i, j) links and for all t
blocks, then control algorithm satisfies:
lim inf
t→∞

lim sup
t→∞

lim sup
t→∞

1 t−1
B + B′ (K − 1)
E [Us (τ )] > U ∗ −
∑
∑
t τ =0 s∈S
H
1 t−1
B + B′ (K − 1) + H(Ū −U ∗ )
E [Qs (τ )] 6
∑
∑
t τ =0 s∈S
ε1′

1 t−1
B + B′ (K − 1) + H(Ū −U ∗ )
E [Qsi (τ )] 6
∑
∑
∑
t τ =0 s∈S i∈S,D
ε2′
/

where B, B′ , ε1′ , ε2′ are positive constants, U ∗ is the optimal
aggregate utility, i.e., the solution of (5-8), and Ū is the
maximum possible instantaneous aggregate utility.
The proof of Theorem 3 is given in Appendix C. This
theorem shows that it is still possible to get arbitrarily close to
the optimal utility by choosing H sufficiently large. However,
the lack of availability of timely queue state information
negatively affects the performance bounds. In particular, for a
given value of H, the bound on the achieved utility decreases
by a factor, proportional to K. Likewise, the upper bounds
on the queue sizes increase by a factor, proportional to K.
Although similar results were obtained in [23] and [24] as
well, here we show that confidentiality is still achieved with
the the infrequent periodic update of the queue lengths.
B. Distributed Implementation
In the previous section, we dealt with the issue of reducing the overhead of the centralized scheduling. Here, we
seek a distributed algorithm where each node participates in
scheduling using only local information: We assume that the
nodes have information of the instantaneous CSI only between
themselves and their neighbors, and only of the queue lengths
of their neighbors.
The scheduling problem of the control algorithms designed
in the previous sections can be reduced to a maximum
weighted matching problem, which is polynomial time solvable, but requires a centralized implementation.6 Each node
needs to notify the central node of its weight and local connectivity information such that the central node can reconstruct the
network topology. A few distributed approximation algorithms
exist for the maximum weighted matching problem, e.g., [25]
and [26]. Here, we make use of the distributed scheduling
algorithm presented in [26], where the maximum weighted
matching is obtained sequentially. Let a link that has been
chosen to be in the matching be called a matched link. Nodes
that are not related to any matched link are called free. A
matching request is transmitted to enquire the possibility to
choose the link with a neighbor as a matched link. A matched
reply is sent to confirm that the link with a neighbor is
matched. A node sends a drop message to inform its neighbors
that it is not free anymore. Algorithm 3 gives the details of
the distributed scheduling algorithm.
At the beginning of each slot, node i does not have information about which of its neighbors will transmit in that

j∈E i6= j

Next, we show that the performance attained by a system
where queue lengths are updated infrequently is again arbitrarily close to the optimal solution.

6 A matching in a graph is a subset of links, no two of which share a
common node. The weight of a matching is the total weight of all its links.
A maximum weighted matching in a graph is a matching whose weight is
maximized over all matchings of the graph.

9

Algorithm 3 Distributed Scheduling Algorithm
Each node i carries out the following steps over each block t:
1) Calculate weight Wisj (t) = (Qsi (t) − Qsj (t))Ri j (t) −
∑k∈E Zks (t)Rik (t) for each link pair (i, j). Ties are broken
randomly.
2) Find node j∗ such that Wisj∗ (t) is maximized over all links
(i, j) with free neighbors j. If having received a matching
request from j∗ , then link (i, j) is a matched link. Node i
sends a matched reply to j∗ and a drop message to all other
free neighbors. Otherwise, node i sends a matching request to
node j∗ .
3) Upon receiving a matching request from neighbor j, if j =
j∗ , then link (i, j) is a matched link. Node i sends a matched
reply to node j and a drop message to all other free neighbors.
If j 6= j∗ , node i just stores the received message.
4) Upon receiving a matched reply from neighbor j, node i
knows link (i, j) is a matched link, and sends a drop message
to all other free neighbors.
5) Upon receiving a drop message from neighbor j, node i
knows that j is in a matched link, and excludes j from its set
of free neighbors.
6) If node i is in a matched link or has no free neighbors, no
further action is taken. Otherwise, it repeats steps 2) through
5).
7) Matched links are allowed to transmit, i.e., if link (i, j) is
a matched link, node i transmits data to node j.

slot. Thus, it considers as leaked information to all its free
neighbors while computing weights of its links, even if some
of those neighbors may transmit in the following iteration.7
However, when all matched links are set, node i overhears
the surrounding transmissions, and updates the virtual queues
related to the overheard information of its neighbors, i.e.,
Z sj (t). In Section VIII, we demonstrate that the proposed
distributed scheduling algorithm results in a small degradation
in the overall performance.
VIII. N UMERICAL R ESULTS
The channels between nodes are modeled as iid Rayleigh
fading Gaussian channels. The noise normalized transmit
power is taken as constant and identical to P = 1 in every
block and for all nodes. Let the power gain of the channel
between nodes i and j be hi j (t) at block t. Then, as N1 → ∞,
Ri j (t) = log(1 + Phi j (t)). The power gains of the channels are
exponentially distributed, where the means of the link are as
given in Table I. We consider a logarithmic utility function,
Us (t) = κ + log(Asp (t)), where Asp (t) is the confidential information admitted in block t.8 Note that, Asp (t) = αs As (t) for the
control algorithm presented in Section V. We take κ = 3 and
H = 100 in all experiments.
In Fig. 3a-3b, we investigate the performance of Control
Algorithm 1, when all intermediate nodes are considered as
eavesdroppers, i.e., {1, 2, 3, 4} ∈ E. For the network depicted in
7 As we consider a node-exclusive interference model, nodes cannot transmit
and receive information at the same time.
8 We utilize logarithmic utility function to provide proportional fairness.

TABLE I
M EAN CHANNEL GAINS
(s1 , 1)
6
(1, d1 )
6

(s1 , 2)
8
(2, d1 )
8

(s1 , 3)
10
(3, d1 )
10

(s2 , 2)
4
(2, d2 )
4

(s2 , 3)
8
(3, d2 )
8

(s2 , 4)
6
(4, d2 )
6

Fig. 1b, we numerically obtain the encoding rate, αs∗ , resulting
in the maximum long-term total utility for source s. For the
above set of values, we obtain α1∗ = 0.55 and α2∗ = 0.509,
which corresponds to optimal long-term average arrival rates
x∗1 = 1.8 and x∗2 = 1.85, respectively. In the experiments, we
fix α2 = α2∗ and vary the value of α1 to analyze the effect
of αs on the confidential data rates and total utility. From
Fig. 3a, we first notice that, long-term confidential data rate
of source s1 increases with increasing α1 , since source s1
sends a larger amount of confidential information for each
encoded message. It is interesting to note that long-term
confidential data rate of source s2 increases initially with
increasing α1 . This is because, for low α1 values, in order
to provide fairness between the sources, source s1 admits
more packets to its queue (e.g., x1 = 1.96, when α1 = 0.3),
increasing its queue size. As a result, scheduling decisions are
dictated by the stability constraint of source s1 ’s queue, and
thus, the long-term arrival rate of source s2 is lower when α1 is
smaller (e.g., x2 = 1.78 when α1 = 0.3). However, when α1 is
high, satisfying the perfect secrecy dominates the scheduling
decisions, and source s1 divides its transmission over the paths
more equally at the expense of lower long-term arrival rates,
x1 and x2 . Fig. 3b depicts the relationship between α1 and the
long-term total utility. As expected, the total utility increases
with increasing α1 until α1 = α1∗ . As α1 increases, there is a
gain due to incorporating more confidential information into
each encoded message of source s1 . However, when α1 is high,
long-term arrival rates of both sources decrease as discussed
previously. Thus, when α1 > α1∗ , the loss due to decrease in
x1 and x2 dominates the gain due to increasing α1 .
Next, in Fig. 4a-4b, we conducted the same analysis, when
the number of eavesdroppers among all intermediate nodes is
2, i.e., the cardinality of set E is 2. We run simulations for
all such possible sets of E, i.e., {1, 4} ∈ E or {2, 3} ∈ E, and
the results in Fig. 4a-4b are the average of the rates obtained
for each possible set of E. We obtain the average encoding
rates as α1∗ = 0.775 and α2∗ = 0.77, which corresponds to
long-term average arrival rates x∗1 = 1.96 and x∗2 = 1.95,
respectively. Again, we fix α2 = α2∗ and vary the value of α1
to analyze the effect of αs on the confidential data rates and
total utility. Comparing Fig. 4a-4b and Fig. 3a-3b, we note that
the long-term confidential data rate increases as the number of
eavesdroppers among the intermediate nodes decreases. This
is because there are paths without eavesdroppers which can
be facilitated to encapsulate more confidential information
in each encoded message. Lastly, we investigate the same
scenario with no attackers in the network. In this scenario,
Control Algorithm 1 simply corresponds to the backpressure
algorithm, since we can send the confidential information
without encoding, i.e., with α1∗ = 1 and α2∗ = 1, and with the
arrival rates x1 = 1.98 and x1 = 1.92.
We next analyze the performance of Control Algorithm

10

2

Long−Term Confidential Data Rate (αsxs)

1.05
1

1.9

0.95

Long−Term Utility

0.9

0.85
0.8

0.75

Control Algorithm1 (User 1)
Control Algorithm1 (User 2)
Optimal (User 1)
Optimal (User 2)

0.7

0.65

1.8
1.7

Control Algorithm 1
Optimal

1.6
1.5
1.4

0.6

0.55
0.3

0.35

0.4

0.45

α

0.5

0.55

0.6

1.3
0.3

0.65

0.35

0.4

0.45

1

0.6

0.65

(b) α1 vs Long-term Total Utility

3
1.5
2.9

1.45
1.4

Long−Term Utility

s s

Long−Term Confidential Data Rate (α x )

1.55

1.35
1.3
Control Algorithm 1 (User 1)
Control Algorithm 1 (User 2)
Optimal (User 1)
Optimal (User 2)

1.25
1.2

2.8
Control Algorithm 1
Optimal

2.7
2.6
2.5
2.4

1.15
0.55

0.6

0.65

0.7

α

0.75

0.8

0.85

0.9

1

2.3
0.5

0.55

0.6

0.65

0.7

α

0.75

0.8

0.85

0.9

1

(a) α1 vs Long-Term Confidential Data Rate (αs xs )

(b) α1 vs Long-term Total Utility

Performance evaluation of Control Algorithm 1 presented in Section V, when the number of eavesdroppers among all intermediate nodes are two.
1

s1

d1

2
3

s2
Fig. 5.

0.55

Performance evaluation of Control Algorithm 1 presented in Section V, when all intermediate nodes are eavesdroppers.

1.1
0.5

Fig. 4.

0.5

1

(a) α1 vs Long-Term Confidential Data Rate (αs xs )
Fig. 3.

α

d2
4

A multi-hop network with two available paths.

2 with varying number of available paths. In particular, we
investigated those networks with two and three paths, as given
in Fig. 5 and Fig. 1b, respectively. Note that in the network
in Fig. 5, nodes s1 and s2 do not have a communication
link to nodes 3 and 2. For the network in Fig. 5, we use
the main channel gains given in Table I except (s1 , 3), (s2 , 2)
and (3, d1 ), (2, d2 ) which have zero mean channel gains. In
2
numerical experiments, we use (RR )2 as the estimate of pout
s (R)
s
for 0 < R < Rs . In Fig. 6a, the effect of increasing Ns Rs on the
long-term confidential data rate, xsp , is shown. We first take the
secrecy outage parameter, γs = 0.01, for all users. Fig. 6a depicts that when Ns Rs = 50, the long-term confidential data rate
is reduced by approximately 50%, compared to the optimal
rates obtained for Ns → ∞.9 However, the confidential data rate
increases with increasing Ns Rs , and it gets close to the optimal
confidential data rates, αs∗ x∗s , when Ns Rs is large enough, i.e.,
Ns Rs = 5000. This is due to fact that when the transmission
of a message takes smaller number of blocks, the portion of
k,con f
confidential bits inserted into the codeword, Rs
/Rs , gets
9 If the average rate in a block t is 0.5 bits/channel use, the message is
approximately transmitted in 100 blocks.

smaller to satisfy the secrecy constraint. In addition, as the
Ns Rs increases, the dependance of the scheduling decisions
between subsequent packets associated with a given secrecyencoded message decreases, so i.i.d. approximation of control
algorithm presented in Section VI becomes more accurate. In
Fig. 6b, we investigate the end-to-end delay with increasing
Ns Rs . The end-to-end delay is the average number of slots used
to transmit an encoded confidential message from the source
to its destination. Note that even though long-term confidential
data rate increases with an increasing number of available
paths, it results in higher delay as depicted in Fig. 6b. The
reason is that with more paths we can encode the message with
more confidential information, but this may cause congestion
among the shared links. Finally, we investigate the effect of
secrecy outage parameter, γs = γ for all sources, on xsp . Fig. 6c
shows that when the secrecy outage constraint is relaxed, i.e.,
γ is increased, the long-term confidential data rate increases
for both networks. This result is expected, since sources can
insert more confidential information into the encoded message,
f
Rk,con
, with a higher secrecy outage parameter. Note that, the
s
optimal rate is obtained when there is no secrecy outages.
Thus, for γ ≥ 0.1 and γ ≥ 0.15, the long-term confidential
data rates exceed the optimal rates for the network in Fig. 1b
and 5, respectively.
Next, we analyze the performance of the algorithm presented in Section VII-A for the network depicted in Fig. 1b,
where the queue length information is periodically updated
(we refer to this policy as the Infrequent Update Algorithm).
We first analyze the effect of the periodic update parameter,
K, on the long-term confidential data rate when H is the same
for all experiments, i.e., H = 100. In addition, α1 and α2

11

0.9
0.85
Control Algorithm 2 (Three Path Case)
Optimal (Three Path Case)
Control Algorithm 2 (Two Path Case)
Optimal (Two Path Case)

0.8
0.75
0.7
0.65
0.6

Control Algorithm 2 (Three path Case)
Control Algorithm 2 (Two path Case)

2000

1500

1000

500

0.55
0.5

0

1000

2000

3000

4000

0

5000

0

1000

2000

(a) Ns Rs vs Long-Term Confidential Data Rate (xsp )

4000

1.1
1.05
1
0.95
0.9

0

0.1

0.2

γ

0.3

0.4

0.5

(c) γ vs Long-Term Confidential Data Rate (xsp )

(b) Ns Rs vs Delay (Average number of slots)

Performance evaluation of Control Algorithm 2 presented in Section VI.
Long−Term Confidential Data Rate (αsxs)

1
0.95
0.9
0.85
0.8
0.75

Infrequent UpdateAlgorithm (User 1)
Infrequent UpdateAlgorithm (User 2)
Control Algorithm (User 1)
Control Algorithm (User 2)

0.7
0.65
0.6

0

20

40

60

80

100

1.05

2

1

1.9

0.95
0.9
0.85
0.8
0.75
Control Algorithm 1 (User 1)
Control Algorithm 1 (User 2)
Distributed Algorithm (User 1)
Distributed Algorithm (User 2)

0.7
0.65

1.8
1.7
1.6

Control Algorithm 1
Distributed Algorithm

1.5
1.4

0.6
0.55
0.3

0.35

0.4

Queue Update Period (K)

0.45

α

0.5

0.55

1

0.6

(a) K vs Long-Term Confidential Data Rate (αs xs ) (b) α1 vs Long-Term Confidential Data Rate (αs xs )
Fig. 7.

1.15

0.85

5000

Control Algorithm 2 (Three Path Case)
Control Algorithm 2 (Two Path Case)
Optimal (Two Path Case)
Optimal (Three Path Case)

1.2

Long−Term Utility

Fig. 6.

3000

1.25

NsRs

NsRs

Long−Term Confidential Data Rate (αsxs)

Long−Term Confidential Data Rate (xps )

0.95

Delay (Average Number of Slots)

p

Long−Term Confidential Data Rate (xs )

2500
1

1.3
0.3

0.35

0.4

0.45

α1

0.5

0.55

0.6

(c) α1 vs Long-term Total Utility

Performance evaluation of queue update and distributed algorithms presented in Section VII.

are selected as 0.55 and 0.509, respectively. In Fig. 7a, we
observe that as expected, the confidential data rate decreases
with increasing K. This is due to fact that with a large K,
the algorithm cannot closely track the queue length values
which in turn deteriorates the performance of the scheduler.
We evaluate the effect of K on the average queue size, when
both infrequent update algorithm and Control Algorithm 1
converge to the optimal point fairly closely. To achieve nearoptimal performance, we set the value of H for different values
of K leading to optimal confidential data rates. In simulations,
we observed that with increasing K, we obtain larger average
queue sizes, i.e., larger delays, confirming theoretical results.
Finally, we analyze the performance of control algorithm
presented in Section VII-B, where distributed scheduling is
performed (We refer to this policy as Distributed Algorithm).
The results are shown in Fig. 7b and Fig. 7c. Here, we
select α2 = 0.509 and varies α1 . As expected, the longterm confidential data rates are smaller than those achieved
with centralized scheduling, since topology and queue length
information is not known globally, and the routing pattern
is changed due to distributed scheduling. Our simulation
results show that the degradation of performance of Control
Algorithm 1 with distributed scheduling is relatively small:
distributed scheduling results in a approximately 10% reduction in aggregate utility.
IX. C ONCLUSION
In this paper, we considered the problem of resource allocation in wireless multi-hop networks where sources have confidential information to be transmitted to their corresponding

destinations with the help of intermediate nodes over timevarying uplink channels. All intermediate nodes are considered as internal eavesdroppers from which the confidential
information needs to be protected. To provide confidentiality
in such setting, we propose encoding the message over long
blocks of information which are transmitted over different
paths. Then, we designed a dynamic control algorithm for a
given encoding rate and we prove that our algorithm achieves
utility arbitrarily close to the maximum achievable utility.
In this problem, we find out that increasing the flow rate
and keeping confidentiality is two conflicting objective unlike
standard dynamic algorithms, and the proposed algorithm also
considers spatial distribution of the flows over each path. Next,
we consider the system, where the messages are encoded over
finite number of blocks. For this system, transmissions of each
block of the same message are dependant with each other.
Thus, we propose a sub-optimal algorithm, and show that the
proposed algorithm approaches the optimal solution as the
number of blocks which the message are encoded, increases.
Finally, we deal with implementational issues of the proposed algorithms. First, we decrease overhead imposed by
the updates transmitted to the scheduler. For that purpose, we
design infrequent queue update algorithm, where users updates
their queue length information periodically. We show that this
algorithm again approaches the optimal solution in the expense
of increasing average queue lengths. Then, we investigate
distributed version of our dynamic control algorithms, where
the scheduler decision is given according to local information
available to each node. The simulation results illustrated that
the reduction in confidentiality rate due to usage of distributed

12

algorithm is relatively small.
R EFERENCES
[1] L. Georgiadis, M. J. Neely, and L. Tassiulas, “Resouce Allocation and
Cross-layer Control in Wireless Networks,” Foundations and Trends in
Networking, vol. 1, no. 1, pp. 1–144, 2006.
[2] X. Lin, N. B. Shroff, and R. Srikant, “On the Connection-Level Stability
of Congestion-Controlled Communication Networks,” IEEE Trans. Inf.
Theory, vol. 54, no. 5, pp. 2317–2338, May 2008.
[3] Y. Chen, R. Hwang, and Y. Lin, “Multipath qos routing with bandwidth
guarantee,” in Proc. IEEE Global Telecommunications Conf., vol. 4, San
Antonio, TX, Sep. 2001, pp. 2199–2203.
[4] X. Lin and N. B. Shroff, “Utility maximization for communication
networks with multipath routing,” IEEE Transactions on Automatic
Control, vol. 51, no. 5, pp. 766–781, May 2006.
[5] A. D. Wyner, “The wire-tap channel,” Bell Syst. Tech. J., vol. 54, no. 8,
pp. 1355–138, Oct. 1975.
[6] P. K. Gopala, L. Lai, and H. E. Gamal, “On the secrecy capacity of
fading channels,” IEEE Trans. Inf. Theory, vol. 54, no. 10, pp. 4687–
4698, Oct. 2008.
[7] Y. Liang, H. Poor, and S. Shamai, “Secure communication over fading
channels,” IEEE Trans. Inf. Theory, vol. 54, no. 6, pp. 2470–2492, June
2008.
[8] O. Gungor, J. Tan, C. E. Koksal, H. E. Gamal, and N. B. Shroff,
“Joint power and secret key queue management for delay limited
secure communication,” in Proc. IEEE Conf. Computer Communications
(Infocom), San Diego, CA, March 2010.
[9] A. Khisti and G. W. Wornel, “Secure transmissions with multiple
antennas: The misome wiretap channel,” IEEE Trans. Inf. Theory,
vol. 56, no. 7, pp. 3088–3014, July 2010.
[10] S. Shaffiee, N. Liu, and S. Ulukus, “Towards the secrecy capacity of
gaussian mimo wire-tap channel: The 2-2-1 channel,” IEEE Trans. Inf.
Theory, vol. 55, no. 9, pp. 4033–4039, Sept. 2009.
[11] L. Dong, Z. Han, A. P. Petropulu, and H. V. Poor, “Improving wireless
physical layer security via cooperating relays,” IEEE Trans. on Signal
Processing, vol. 58, no. 3, pp. 4033–4039, March 2010.
[12] O. O. Koyluoglu, C. E. Koksal, and H. E. Gamal, “On secrecy capacity
scaling in wireless networks,” IEEE Trans. Inform. Theory, vol. 58, no. 5,
pp. 3000–3015, May 2012.
[13] C. Capar, D. Goeckel, B. Liu, and D. Towsley, “Secret communication
in large wireless networks without eavesdropper location information,”
in Proc. IEEE Conf. Computer Communications (Infocom), Orlando, FL,
March 2012, pp. 1152–1160.
[14] A. Shamir, “How to share a secret,” Commun. ACM, vol. 22, no. 11,
pp. 612–613, Nov. 1979.
[15] W. Lou, W. Liu, and Y. Fang, “Spread: enhancing data confidentiality
in mobile ad hoc networks,” in Proc. IEEE Conf. Computer Communications (Infocom), Hong Kong, March 2004, pp. 2404–2413.
[16] N. Cai and R. Yeung, “Secure network coding,” in Proc. IEEE Int.
Symposium Inform. Theory, Lausanne, Switzerland, June 2002.
[17] J. Feldman, T. Malkin, R. Servedio, and C. Stein, “On the capacity
of secure network coding,” in Proc. Allerton Conf. on Communication,
Control, and Computing, Monticello, IL, Sep. 2004.
[18] T. Cui, T. Ho, and J. Kliewer, “On secure network coding with
nonuniform or restricted wiretap sets,” IEEE Trans. Inf. Theory, vol. 59,
no. 1, pp. 166–176, Jan. 2013.
[19] N. Abuzainab and A. Ephremides, “Secure Distributed Information
Exchange,” IEEE Trans. Inf. Theory, vol. 60, no. 2, pp. 1126–1135,
Feb. 2014.
[20] E. Peron, “Information-theoretic secrecy for wireless networks,” Ph.D.
dissertation, Ecole polytechnique federale de Lausanne(EPFL), Switzerland, 2009.
[21] E. Perron, S. Diggavi, and E. Telatar, “On cooperative wireless network
secrecy,” in Proc. IEEE Conf. Computer Communications (Infocom),
vol. 4, Rio de Janeiro, Brazil, Sep. 2009, pp. 1935–1943.
[22] C. E. Koksal, O. Ercetin, and Y. Sarikaya, “Control of wireless networks
with secrecy,” IEEE/ACM Trans. on Networking, vol. 21, no. 1, pp. 324–
337, Feb. 2013.
[23] A. Eryilmaz, R. Srikant, and J. R. Perkins, “Stable scheduling policies
for fading wireless channels,” IEEE Trans. Inf. Theory, vol. 13, no. 2,
pp. 411–424, Apr. 2005.
[24] C. Manikandan, S. Bhashyam, and R. Sundaresan, “Cross-layer scheduling with infrequent channel and queue measurements,” IEEE Trans. on
Wireless Communications, vol. 8, no. 12, pp. 5737–5742, Dec. 2009.

[25] S. Sanghavi, D. Shah, and A. Willsky, “Message-passing for maximum
weight independent set,” IEEE Trans. Inf. Theory, vol. 55, no. 11, pp.
4822–4834, Nov. 2009.
[26] J. Hoepman, “Simple distribute weighted matchings,” Oct. 2004, available at http://arxiv.org /abs/cs/0410047.
[27] A. E. Gamal and Y. Kim, Network Information Theory. Cambridge
University Press, 2011.

A PPENDIX A
P ROOF OF T HEOREM 1
The variant of Wyner encoding strategy we use is based
on random coding and binning [27]. First, let us describe
this strategy. To begin, node s generates 2N(Rs −δ ) random
binary sequences. Then, it assigns each random binary seconf
quence to one of 2NRs bins, so that each bin contains
conf
exactly 2N(Rs −Rs −δ ) binary sequences. We call the sequences
associated with a bin, the randomization sequences of that
bin. Each bin of source s is one-to-one
matched with a
conf
confidential message Ws ∈ {1, . . . , 2NRs } randomly and this
selection is revealed to the destination and all nodes before the
communication starts. Then, the stochastic encoder of node s
selects one of the randomization sequences associated with
each bin at random, independently and uniformly over all
randomization sequences associated with that bin. Whenever
a message is selected by node s, this particular randomization
message is used. This selection is not revealed to any of the
nodes nor to the destination.
Without loss of generality, we assume that the routes
between source and destination have p multi-paths and each
path may consist of a different number of hops. Let us denote
Hk as the number of hops along kth path. Let us denote the
randomization sequence of message Ws as Wsr for source s, and
denote the transmitted vector of channel symbols from node
s (1), . . . , X s (N )],
located at hop i along path k as Xsi,k = [Xi,k
i,k s
s
where Xi,k (t) represents the transmitted vector of N1 symbols
in block t at hop i along path k. Note that transmitted vectors
in the first hop only consists of transmission of the source
s. The received signal at intermediate relay node located at
s (1), . . . ,Y s (N )], where Y s (t)
hop i along path k is Ysi,k = [Yi,k
i,k s
i,k
represents the received vector of symbols at nodes of hop i
along path k in block t. Also, the received signal at overhearing
neighbor node j when a node at hop i along path k is transj,s
j,s
j,s
mitting, is Zi,k = [Zi,k (1), . . . , Zi,k (Ns )]. For notational conves
s
nience, let us define X = [X1,1 , . . . , XsH1 ,1 , . . . , Xs1,p , . . . , XsHp ,p ]

j,s
j,s
j,s
and Zj,s = [Zj,s
1,1 , . . . , ZH1 ,1 , . . . , Z1,p , . . . , ZHp ,p ] as transmitted
vector of symbols by all nodes and the total received signal
by the overhearing neighbor node j, respectively.
Next, we provide the equivocation analysis for a given joint
scheduling and routing decision. Note that, our objective is to
con f
find a value for Rs
for which perfect secrecy is achievable.
con f
To achieve perfect secrecy, we require Rs − Rs
to be lower
j,s
bounded by the conditional entropy H(Ws |Z ). For any given
intermediate node j, the following can be written for the
conditional entropy:

H(Ws |Zj,s ) = I(Ws ; Ys1,1 , . . . , Ys1,p |Zj,s ) + H(Ws |Zj,s , Ys1,1 , . . . , Ys1,p )
≥ I(Ws ; Ys1,1 , . . . , Ys1,p |Zj,s )

(14)

= I(Ws ,Wsr ; Ys1,1 , . . . , Ys1,p |Zj,s ) − I(Wsr ; Ys1,1 , . . . , Ys1,p |Zj,s ,Ws )
(15)

13

= I(Ws ,Wsr ; Ys1,1 , . . . , Ys1,p |Zj,s ) − H(Wsr |Zj,s ,Ws )
+ H(Wsr |Zj,s , Ys1,1 , . . . , Ys1,p ,Ws )
≥ I(Ws ,Wsr ; Ys1,1 , . . . , Ys1,p |Zj,s ) − H(Wsr |Zj,s ,Ws )
(16)
(17)
≥ I(Ws ,Wsr ; Ys1,1 , . . . , Ys1,p |Zj,s ) − N ε1
s s
s
j,s
s
s
s
j,s
r
= I(X ; Y1,1 , . . . , Y1,p |Z ) − I(X ; Y1,1 , . . . , Y1,p |Z ,Ws ,Ws ) − N ε1

The following lemma provides an upper bound on ∆(t).
Lemma 1:
∆(t) ≤ B − ∑ E Qs (t)
s∈S

−∑

(18)
≥ I(Xs ; Ys1,1 , . . . , Ys1,p |Zj,s ) − N(ε1 + ε2 )

(19)

= I(Xs ; Ys1,1 , . . . , Ys1,p , Zj,s ) − I(Xs ; Zj,s ) − N(ε1 + ε2 )

(20)

≥ I(Xs ; Ys1,1 , . . . , Ys1,p ) − I(Xs ; Zj,s ) − N(ε1 + ε2 )

(21)

≥ I(X

s

; Ys1,1 , . . . , Ys1,p ) −

p Hk

∑∑

j,s
I(Xsi,k ; Zi,k ) − N(ε1 + ε2 )

(22)

k=1 i=1
N2

≥

∑

t=1

"

s
s
I(Xs (t);Y1,k
(t), . . . ,Y1,p
(t)) −

∑

∑ I(Xi,ks (t); Zi,k (t))

k=1 i=1

− N(ε1 + ε2 )
"
≥N

p Hk

∑

j,s

#
(23)

µ̄sis − f¯sj − (ε1 + ε2 )

(s,i)∈L

#

(24)

with probability 1, for any positive (ε1 , ε2 ) doublet,
as N1 Ns → ∞. (15) is by the chain rule, (17) follows from the application of Fano’s equality, (18) follows from the chain rule and that (Ws ,Wsr ) ↔ (Xs ) ↔
(Ys1,1 , . . . , YsH1 ,1 , . . . , Ys1,p , . . . , YsHp ,p , Zj,s ) forms a Markov
chain, (19) holds since I(Xs ; Ys1,1 , . . . , Ys1,p |Zj,s ,Ws ,Wsr ) ≤ N ε2
as the transmitted symbols sequences Xs is determined
w.p.1 given (Zj,s ,Ws ,Wsr ) (with the routing history), and
(20) follows from the chain rule. (22) follows from the
definition of transmission across p path and multiple hops,
I(Xsi,k ; Ysl,m ) = 0 when i 6= l or k 6= m. Hence, I(Xs ; Zj,s ) ≤
Hk
p
I(Xsi,k ; Zj,s
∑k=1 ∑i=1
i,k ). (23) holds since the fading processes
are iid for a strategy that chooses the transmitted packets
injected by the source to be independent in different blocks,
and finally (24) follows from ergodicity.10 Noting that (24)
holds for any j and combining it with (4), completes the proof.

∑

The optimality of the algorithm can be shown by applying the Lyapunov optimization theorem [1]. We consider queue backlog vectors for commodity s as Q(t) =
(Q1 (t), . . . , QK (t)), Qs (t) = (Qs1 (t), . . . , Qsn (t)), and Zs (t) =
(Z1s (t), . . . , Zns (t)), where n is the number of intermediate relay
nodes in the network. Let L(Q(t), Qs (t), Zs (t)) be a quadratic
Lyapunov function of real and virtual queue backlogs for
commodity s defined as:
L(Q(t), Qs (t), Zs (t)) =

i
n h
1
Qs (t) + ∑ (Qsi (t))2 + (Zis (t))2 . (25)
∑
2 s∈S
i=1

Also consider the one-step expected Lyapunov drift, ∆(t)
for the Lyapunov function as:
∆(t) = E [L(Q(t + 1), Qs (t + 1), Zs (t + 1))
− L(Q(t), Qs (t), Zs (t))|Q(t), Qs (t), Zs (t)] . (26)
10 Since we are interested in an achievability scheme, it is sufficient to show
that the provided rate is achievable by any particular strategy.

"

−∑

As (t) −

∑

∑E

s∈S i∈E

Zis (t)

∑

µisj (t) −

j|(i, j)∈L

"

∑

µsis (t)

{i|(s,i)∈L}

E Qsi (t)

s∈S i∈S,D
/

!

µ sji (t)

i|(i, j)∈L

(1 − αs )As (t) + ∑

Qs (t)

s, j
fi (t)

j6=i

!

!

#

Qsi (t)

#

#

(27)

Zis (t)

,

where B > 0 is a constant.
Proof: Since the maximum transmission power is finite, in any interference-limited system transmission rates are
bounded. Let µis,max
be the maximum rate over link (i, j)
j
for commodity s, which depends on the channel states. Also
assume that the arrival rate is bounded, i.e., Amax
is the
s
maximum number of bits that may arrive in a block for each
source. By simple algebraic manipulations one can obtain a
bound for the difference (Qs (t + 1))2 − (Qs (t))2 and also for
other queues to obtain the result in (27).
Applying the above lemma, we can complete our proof. In
particular, Lyapunov Optimization Theorem [1] suggests that a
good control strategy is the one that minimizes the following:


∆U (t) = ∆(t) − HE ∑ (Us (t)) | (Q(t), Qs (t), Zs (t)) . (28)
s

By using (27) in the lemma, we obtain an upper bound for
(28), as follows:
"

∆ (k) < B − ∑ E Qs (t)
U

s∈S

−∑

∑

E

s∈S i∈S,D
/

−∑

∑E

s∈S i∈E

− HE

A PPENDIX B
P ROOF OF T HEOREM 2

"



"

"

Qsi (t)

Zis (t)

As (t) −

µisj (t) −

∑

{i|(s,i)∈L}

∑

j|(i, j)∈L

j6=i



!

Qsi (t)

µ sji (t)

i|(i, j)∈L

((1 − αs )As (t) + ∑

∑ Us ((1 − αs )As (t))
s

∑

µsis (t)

s, j
fi (t))

#

!

Zis (t)

Qsi (t)

#

#
(29)

It is easy to observe that our proposed dynamic network
control algorithm minimizes the right hand side of (29) by
rearranging the terms in (29).
If the arrival rates and the given encoding rate, αs , are in the
feasible region, it has been shown in [1] that there must exist
a stationary scheduling and rate control policy that chooses
the users and their transmission rates independent of queue
backlogs and only with respect to the channel statistics. In
particular, the optimal stationary policy can be found as the
solution of a deterministic policy if the channel statistics are
known a priori.
Let U ∗ be the optimal value of the objective function of
the problem (5-8) obtained by the aforementioned stationary
policy. Also let λs ∗ be optimal traffic arrival rates found as the
solution of the same problem. In particular, the optimal input
rate λs ∗ could in principle be achieved by the simple backlogindependent admission control algorithm of new arrival As (t)
for a given commodity s in block t independently with
probability ζs = λs ∗ /λs .

14

Also, since λs ∗ is in the achievable rate region, i.e., arrival
rates are strictly interior of the rate region, there must exist
a stationary scheduling and rate allocation policy that is
independent of queue backlogs and satisfies the following:

∑

µ̄sis ≥ λs ∗ + ε1

∑

µ̄isj

(30)

{i|(s,i)∈L}
j|(i, j)∈L

≥

∑

i|(i, j)∈L

RHS < B − ∑ ε1 E[Qs (t)] − ∑

∑

∑

"

K

−

∑∑ ∑

E

K

−

(32)

∑E

Qs (t + τ )

τ =1 s∈S

(31)

∑ ∑ ∑E

τ =1 s∈S i∈E
′

"

∑

As (t + τ ) −

µsis (t + τ )

Qs (t)

{i|(s,i)∈L}

∑

Qsi (t + τ )

∑

µisj (t + τ ) −

j|(i, j)∈L

j|( j,i)∈L

(1 − αs )As (t + τ ) + ∑

Zis (t + τ )

µ sji+τ (t)

fis, j (t + τ )

j6=i

!

!

Qsi (t)

ε2 E[Qsi (t)]

#

. In (35), we obtain a bound
where B′ =
2
for the K-step Lyapunov drift. We define one-step expected
Lyapunov drift as:
h
ˆ = E L(Q̂(t + 1), Q̂s (t + 1), Ẑs (t + 1))
∆(t)

i
− L(Q̂(t), Q̂s (t), Ẑs (t))|Q̂(t), Q̂s (t), Ẑs (t) .

This is exactly in the form of Lyapunov Optimization
Theorem given in [1], and hence, we can obtain bounds on
the performance of the proposed policy and the sizes of queue
backlogs as given in Theorem 2.

(36)

ˆ
Then, we obtain one-step
(35) as: #
" Lyapunov drift, ∆(t) from !

ˆ ≤ B + B′ (K − 1) − ∑ E Qs (t)
∆(t)

As (t) −

s∈S

−∑

−∑

s∈S i∈E

(35)

s,max 2
2
max((Amax
) )
s ) ,( µi j

∑

E

s∈S i∈S,D
/

s∈S i∈S,D
/
s
ε3 E[Zi (t)] − HU ∗ .

#

Zis (t)

+ BK + B K(K − 1),

Note that as we consider stationary and ergodic policies,
long-term averages in (30)-(32) correspond to expectations of
the same variables as in (29). Clearly, any stationary policy
should satisfy (29). Recall that our proposed policy minimizes
the right hand side (RHS) of (29), and hence, any other
stationary policy (including the optimal policy) has a higher
RHS value than the one attained by our policy. In particular,
the stationary policy that satisfies (30)-(32), and implements
aforementioned probabilistic admission control can be used to
obtain an upper bound for the RHS of our proposed policy.
Inserting (30)-(32) into (29), we obtain the following upper
bound for our policy:

−∑

K

∆ˆ K (t) ≤ − ∑

τ =1 s∈S i∈S,D
/

µ̄ sji + ε2

f¯is ≤ (1 − αs )λs ∗ + ε3 .

s∈S



s,max
) . Then we can
i.e., Q̂s (t) − Qs (t + τ ) ≤ τ max(Amax
s , µi j
rewrite (34) as: "
#
!

∑E

s∈S i∈E
′

"

"

Qsi (t)

Zis (t)

∑

j|(i, j)∈L

µsis (t)

Qs (t)

!

Qsi (t)

#

Zis (t)

#

{i|(s,i)∈L}

µisj (t) −

∑

µ sji (t)

j|( j,i)∈L

(1 − αs )As (t) + ∑

j6=i

= B (K − 1) + RHS of (26)

∑

s, j
fi (t)

!

(37)

ˆ
After obtaining bound on the ∆(t),
we can obtain bounds
on the performance of the proposed policy and the sizes of
queue backlogs as given in Theorem 3 by following the same
lines in Appendix B.

A PPENDIX C
P ROOF OF T HEOREM 3
For the proof, we follow the similar approach used in Appendix B, i.e., applying the Lyapunov optimization theorem.
However, here, we use K-slot Lyapunov drift instead of the
one-step expected Lyapunov drift. We again use quadratic Lyapunov function as in (25). Assume that nodes transmit its exact
queue values in every K slots, i.e., in . . . ,t − K,t,t + K, . . ..
Thus, Q̂(t) = Q̂(t + τ ) for 0 ≤ τ ≤ K. Consider the K-step
expected Lyapunov drift, ∆ˆ K (t) as:
h
∆ˆ K (t) = E L(Q̂(t + K), Q̂s (t + K), Ẑs (t + K))

i
− L(Q̂(t), Q̂s (t), Ẑs (t))|Q̂(t), Q̂s (t), Ẑs (t) .

(33)

Yunus Sarikaya received the BS, MS and PhD
degrees in telecommunications engineering from Sabanci University, Istanbul, Turkey, in 2006, 2008 and
2014, respectively.
Since 2015, he has been with the Electrical
and Computer Engineering Department at Monash
University, VIC, as an Senior Research Associate.
He was also a visiting scholar at The Ohio State
University, OH, USA. His research interests include
optimal control of wireless networks, stochastic optimization, and information theoretical security.

By using the result in Lemma 1. We bound K-step Lyapunov
drift as:
#
!
"
K

∆ˆ K (t) ≤ − ∑

∑E

τ =1 s∈S

K

−

∑∑ ∑

τ =1 s∈S i∈S,D
/
K

−

E

∑ ∑ ∑E

τ =1 s∈S i∈E

"

"

Q̂s (t)

Q̂si (t)

Ẑis (t)

As (t + τ ) −

∑

µsis (t + τ )

Q̂s (t)

{i|(s,i)∈L}

∑

j|(i, j)∈L

µisj (t + τ ) −

∑

µ sji+τ (t)

j|( j,i)∈L

(1 − αs )As (t + τ ) + ∑ fis, j (t + τ )
j6=i

!

!

#

Q̂si (t)
#

Ẑis (t) + BK,
(34)

Note that the difference of queue sizes
 in slot t and queue

s,max
sizes in slot t + τ is bounded by τ max(Amax
) ,
s , µi j

Ozgur Ercetin received the BS degree in electrical
and electronics engineering from the Middle East
Technical University, Ankara, Turkey, in 1995 and
the MS and PhD degrees in electrical engineering
from the University of Maryland, College Park, in
1998 and 2002, respectively. Since 2002, he has
been with the Faculty of Engineering and Natural
Sciences, Sabanci University, Istanbul. He was also
a visiting researcher at HRL Labs, Malibu, CA,
Docomo USA Labs, CA, and The Ohio State University, OH. His research interests are in the field
of computer and communication networks with emphasis on fundamental
mathematical models, architectures and protocols of wireless systems, and
stochastic optimization.

15

C. Emre Koksal Can Emre Koksal (S’96-M’03SM’13) received the B.S. degree in Electrical Engineering from the Middle East Technical University
in 1996, and the S.M. and Ph.D. degrees from
MIT in 1998 and 2002, respectively, in Electrical
Engineering and Computer Science. He was a Postdoctoral Fellow at MIT until 2004, and a Senior
Researcher at EPFL until 2006. Since then, he has
been with the Electrical and Computer Engineering
Department at Ohio State University, currently as
an Associate Professor. His general areas of interest
are wireless communication, communication networks, information theory,
stochastic processes, and financial economics.
He is the recipient of the National Science Foundation CAREER Award in
2011, the OSU College of Engineering Lumley Research Award in 2011, the
co-recipient of an HP Labs - Innovation Research Award in 2011, and a finalist
in Bell Labs Innovation Prize in 2014. The paper he co-authored was a best
student paper candidate in MOBICOM 2005. Currently, he is an Associate
Editor for IEEE Transactions on Information Theory, IEEE Transactions on
Wireless Communications, and Elsevier Computer Networks.

