Distributed Scheduling Algorithms for Optimizing
Information Freshness in Wireless Networks

arXiv:1803.06469v1 [cs.IT] 17 Mar 2018

Rajat Talak, Sertac Karaman, and Eytan Modiano

Abstract—Age of Information (AoI), measures the time elapsed
since the last received information packet was generated at the
source. We consider the problem of AoI minimization for singlehop flows in a wireless network, under pairwise interference constraints and time varying channel. We consider simple, yet broad,
class of distributed scheduling policies, in which a transmission
is attempted over each link with a certain attempt probability.
We obtain an interesting relation between the optimal attempt
probability and the optimal AoI of the link, and its neighboring
links. We then show that the optimal attempt probabilities can
be computed by solving a convex optimization problem, which
can be done distributively.

I. I NTRODUCTION
Timely delivery of information updates is gaining increasing
relevance with the advent of technologies such as autonomous
flying vehicles, internet of things, and other cyber physical
systems. In autonomous flying vehicles, for example, timely
exchange of position, velocity, and other control information
can improve network safety [1], [2].
Packet delay, the traditionally used measure, accounts for
the average time taken for a packet to reach the destination
node, but does not measure the ‘information lag’ at the destination node, especially when the information update generation
can be controlled [3]–[5]. For example, if two packets carry
the same information, and one arrives early at the destination,
then there is no need in accounting for the delay in reception
of the second packet.
Age of information (AoI), a newly proposed metric [3], [6],
is defined to be the time elapsed since the last received information update was generated at the source node. AoI, upon
reception of a new update packet drops to the time elapsed
since generation of the packet, and grows linearly otherwise.
AoI, therefore, more accurately captures the ‘information lag’
at the destination node.
AoI has been analyzed for various queueing models [3], [7]–
[11], but very little attention has been paid to AoI minimization
in wireless networks. A problem of scheduling finitely many
update packets under physical interference constraints was
shown to be NP-hard in [12]. Age for a broadcast network,
where only a single link can be activated at any time, was
studied in [13]–[15]. Some preliminary analysis of age for
a slotted ALOHA like random access was done in [16],
The authors are with the Laboratory for Information and Decision Systems
(LIDS) at the Massachusetts Institute of Technology (MIT), Cambridge, MA.
{talak, sertac, modiano}@mit.edu
Submitted to SPAWC 2018.
This work was supported by NSF Grants AST-1547331, CNS-1713725, and
CNS-1701964, and by Army Research Office (ARO) grant number W911NF17-1-0508.

while multi-hop networks have been considered in [5], [17].
More recent work includes [4], [18], [19], which propose
centralized scheduling policies for AoI minimization, under
general interference constraints and time varying channels.
In a wireless network, it is not always possible to implement
centralized schemes. In this paper, we consider a simple, yet
broad, class of distributed scheduling policies for wireless
networks, in which each link attempts transmission with a
certain probability. We consider time varying channel and a
pairwise interference model, in which each link interferes with
a specified set of links in the network.
We first derive an interesting relation between the optimal
attempt probability, and the optimal age of the given link
and the interfering links. We then characterize the optimal
distributed policy πD , as a solution to a convex optimization
problem. We further show that this convex problem can be
solved distributively.
II. S YSTEM M ODEL
We model a wireless communication network as a graph
G = (V, E), where V is the set of nodes and E is the set of
directed communication links between the nodes. Each link
e ∈ E is associated with a source-destination pair. Time is
slotted, with the duration of each slot set equal to the time
it takes to transmit a single update packet. For simplicity, we
normalize the slot duration to unity.
Transmission of update packets cannot occur simultaneously
over all links due to wireless interference constraints [20]. For
each link e ∈ E, there is a subset of links Ne ⊂ E, that
interfere with link e, i.e., if link e and a link l ∈ Ne attempt
simultaneous transmission, then the transmission over link e
fails due to interference. We call this the pairwise interference
model. Popular models such as 1-hop and 2-hop interference
models [20] are special cases of this model.
Channel uncertainty can also lead to failure in reception
of update packets. We consider a two state channel process
Se (t) ∈ {0, 1} for all time t and links e. Channel state Se (t) =
1 implies that link e’s channel is ON at time t, and a noninterfering transmission over e is successfully received. When
Se (t) = 0, even a non-interfering transmission over link e fails
due to bad channel conditions. We assume the channel process
{Se (t)}t,e to be independent and identically distributed (i.i.d.)
across time t, and only independent across links e. We let
γe = Pr (Se (t) = 1) denote the channel success probability
for link e. We consider the case when the channel statistics,
namely γe for all e ∈ E, are known but the current channel
state Se (t) cannot be observed.

We use Ue (t) to denote scheduling decisions at time t, for
each link e. Ue (t) = 1 when link e attempts transmissions
in slot t, and Ue (t) = 0 otherwise. Thus, a successful
transmission occurs over link e if and only if a transmission
is attempted on link e, the link e’s channel is ON, and
no transmission is attempted over links e0 ∈ Ne . This is
equivalent to
Y
(1 − Ue0 (t)) = 1.
Ûe (t) , Se (t)Ue (t)
(1)
e0 ∈Ne

A. Age of Information
AoI of a network is a function of AoI of each sourcedestination pair. Thus, we define age Ae (t) for each link, to
be the time since the last received update was generated. We
assume source nodes to be active sources, i.e., it can generates
a fresh update packet before every transmission.
When all sources are active, the age Ae (t), is equal to
the time elapsed since the last successful transmission over
e. Thus, the evolution of age Ae (t) can be written as

Ae (t) + 1 if Ûe (t) = 0
Ae (t + 1) =
,
(2)
1
if Ûe (t) = 1
for all e ∈ E. We define average age for link e to be
Aave
e = lim sup
T →∞

T
1X
Ae (t),
T t=1

(3)

whenever the limit exists. We define the peak age to be the
average of all the age peaks:
Ape

Ne (T )
X
1
Ae (Te (i)),
= lim sup
T →∞ Ne (T ) i=1

(4)

where Te (i) denote the ith instance of successful transmission
over link e, i.e., the ith instance when Ûe (t) = 1, and Ne (T )
is the number of successful transmissions over link e until
time T . We define average and peak AoI of the network to be
a weighted sum of link AoI:
X
X
Aave =
we Aave
and Ap =
we Ape .
(5)
e ,
e∈E

e∈E

Our objective is to design distributed scheduling policies
that minimize the network average and peak age.
B. Distributed Stationary Policies
We focus our attention on policies in which scheduling
decisions are made by the source of each link e, and not
by a centralized scheduler. In particular, we consider policies
in which each link e attempts transmission with probability
pe > 0, independent across links and slots. We refer to these
policies as the distributed stationary policies.
The probability that a non-interferingQtransmission is attempted over link e is given by fe = pe e0 ∈Ne (1 − pe0 ). We
will refer to fe as the link activation frequency of link e, and
use f = (fe )e∈E to denote the link activation frequency vector.

Fig. 1. Example of two interfering links, 1 and 2. The yellow region is FD .
Also shown is the set of feasible link activation frequencies for centralized
schedule: F = {(f1 , f2 ) | f1 + f2 ≤ 1 and fi ≥ 0}.

The space of all link activation frequencies f , attainable using
distributed stationary policies, is given by

Y
FD = f ∈ R|E| | fe = pe
(1 − pe0 )
e0 ∈Ne


and 0 ≤ pe ≤ 1 ∀ e ∈ E . (6)
Figure 1 shows the set of feasible link activation frequencies
for distributed policies for the two interfering link example.
Also, shown is the set of all link activation frequencies F
attainable using a centralized scheduler. It can be seen that
the set FD is non-convex, and strictly smaller than F. The
gap between these two sets indicates the price one has to pay
in resorting to distributed scheduling.
III. O PTIMAL P OLICY
In this section, we characterize an age optimal policy, and
propose an implementation that requires only local information. We first show that for any distributed stationary policy,
the peak and average age are equal, and can be written as a
simple convex function in link activation frequencies fe .
Lemma 1: For any distributed stationary policy, the
average and peak age is given by
X we
Aave = Ap =
,
(7)
γe fe
e∈E
Q
where fe = pe e0 ∈Ne (1 − pe0 ) is the link activation
frequency of link e.
Proof: A similar result was proved in [4] which considered a class of centralized policies, that are not necessarily
stationary. Here, we provide a proof for distributed stationary
policies.
Consider a link e. Then, under any distributed stationary
policy, the event that link e is successfully activated in slot
t is independent and identically distributed across slots, with
success probability of γe fe . Thus, the time since last activation

is geometrically distributed with mean γe1fe . It turns out that
the peak and average age for link e are indeed equal to this
quantity, i.e.,
1
p
Aave
,
e = Ae =
γe fe
P
we
and therefore, the network age is
e∈E γe fe . The detailed
proof is given in Appendix A.
An immediate consequence of Lemma 1 is that both peak
and average age minimization problems, over the space of all
distributed stationary policies, can be written as
X we
Minimize
(8)
f ∈FD
γe fe
e∈E

Notice that, although the objective function is convex, the
constraint set FD is non-convex, see Figure 1. Furthermore,
obtaining optimal link activation frequencies f ∗ does not
suffice as the distributed policy is characterized by the attempt
probabilities pe . The optimal link attempt probabilities p∗ , that
solve (10), yield a distributed stationary policy, that is both
peak and average age optimal. We call this policy πD .
The following result characterizes the optimal link attempt
probabilities p∗ in terms of the optimal link age A∗e .
Theorem 1: The attempt probabilities p∗
∈ E), that solve (8), are given by

=

(p∗e |e

p∗e =

we A∗e

+

w A∗
Pe e

e0 :e∈Ne0

we0 A∗e0

,

(9)

−1

Q
is
for all e ∈ E, where A∗e = γe p∗e e0 ∈Ne (1 − p∗e0 )
the optimal peak/average age of link e.
Proof: Substituting FD , from (6), in (8) we get
X we
Minimize
γe fe
p∈[0,1]|E| ,f ∈R|E|
e∈E
Y
subject to
fe = pe
(1 − pe0 ) ∀ e ∈ E

However, Theorem 1 shows that the attempt probability
p∗e = P

A∗e

e0 ∈E

A∗e0

,

(13)

is both peak and average age optimal. This gives us a more
precise answer to the question posed in [16]. Our result,
however, holds under the more general pairwise interference
constraints, and non-equal weights we > 0.
A. Distributed Computation of πD
Although, Theorem 1 gives a characterization of the optimal
attempt probabilities, in terms of the optimal link age A∗e , it
does not provide for a simple method to computation.
We now provide for an alternate characterization of the
network age minimization problem (8). In particular, we show
that p∗ can be obtained by a simpler convex optimization
problem, than the one in (11). We will also see that this simpler
problem is akin to distributed computation of the policy πD .
Theorem 2: The age minimization problem (8) is
equivalent to the convex optimization problem:


!
X
X
λ
e
λe +
P
Maximize
λe0  H
λe ≥0
λe + e0 :e∈Ne0λe0
e∈E
e0 :e∈Ne0
 
X 
we
+
λe 1 + log
, G(λ),
λe
e∈E

(14)
 





1
where H (p) = p log p1 + (1 − p) log 1−p
is the
∗
entropy function. If λ is the optimal solution to this
problem, then the optimal attempt probabilities p∗ are
given by
λ∗
p∗e = ∗ P e
,
(15)
λe + e0 :e∈Ne0 λ∗e0

for all e ∈ E.
(10)

e0 ∈Ne

fe ≥ 0 for all e ∈ E
Now, substituting qe = 1 − pe , the optimization problem (10)
reduces to
X
w
Q e
Minimize
p≥0,q≥0
γe pe e0 ∈Ne qe0
(11)
e∈E
subject to pe + qe ≤ 1 ∀e ∈ E
This is a convex program in standard form, and can be solved
using KKT conditions to obtain Theorem 1. The details are
given in Appendix B.
Preliminary results on age optimization for a ALOHA type
network model were presented in [16] for a network in which
only one link can be activated at any given time. As a heuristic,
it was argued in [16] that the attempt rates should be
√
1/ γe
P
pe =
(12)
√ .
0
e0 ∈E 1/ γe

Proof: See Appendix C.
We first note that the variable λe is a proxy for the weighted
age we Ae of link e, and the solution λ∗e corresponds to optimal
weighted age we A∗e . This can also be intuited from (15), which
is same as (9).
The objective function G(λ) in (14) is a concave function;
since the problem is convex. Therefore, a simple projected
gradient ascent is guaranteed to converge to the optimal
λ∗ [21]. The gradient of the function G (λ) is given by
 

 X


we
θe
λe0
∂G (λ)
= log
+ log 1+
+
log 1 +
,
∂λe
λe
λe 0
θ e0
e :e∈∈Ne0

P

0
for all e ∈ E, where θe =
e0 :e∈Ne0 λe . Note that the
∂G(λ)
gradient ∂λe depends only on λe and λe0 , for e0 that are
‘extended neighbors’ of e. This space dependence of ∂G(λ)
∂λe
on λ makes the projected gradient descent algorithm akin to
distributed implementation.

We give the projected gradient descent algorithm for distributively computing policy πD in Algorithm 1. In it, we
divide time into frames, each frame of F ≥ 1 slots. For
simplicity, we assume symmetric interference, i.e., e interferes
with e0 if and only if e0 interferes with e which is same as the
condition Ne = {e0 ∈ E | e ∈ Ne0 } for all links e.
Link e, sets its attempt probability to pe (m), in frame
m ≥ 1. The source of link e tracks and updates two variables,
namely, λe (m) and θe (m). We use Π to denote the projection
on the set [, +∞), for a  > 0. As seen in Steps 5 and 7 in
Algorithm 1, variables λe (m) and θe (m) need to be exchanged
only between the neighboring links.
Algorithm 1 Distributed Computation of Policy πD
1: pe (m): attempt probability of link e, in frame m
2: λe (m), θe (m): dual variables, in frame m
3: Start: Set λe (0) = 1 and θe (0) = |Ne | for all e ∈ E. Set
pe (0) = 1/2 and m = 0.
4: for each frame m do
5:
Send: θe (m) to all e0 ∈ Ne
6:
Compute λe (m + 1):
"
(


we
λe (m + 1) ← Π λe (m) + ηm log
λe (m)



 )#
X
θe (m)
λe0 (m)
+ log 1 +
+
log 1 +
λe (m)
θe0 (m)
0
e ∈Ne

7:
8:

Send: λe (m + 1) to all e0 ∈ Ne
Update θe (m + 1):
X
θe (m + 1) ←
λe0 (m + 1)
e0 ∈Ne

9:

Update pe (m + 1):
pe (m + 1) ←

10:
11:

λe (m + 1)
λe (m + 1) + θe (m + 1)

m←m+1
end for

IV. C ONCLUSION
We considered age minimization in a wireless network, with
pairwise interference constraints, time varying channels, and
single-hop flows. We considered a simple class of distributed
scheduling policies, in which each link attempts transmission
with probability pe . We showed an interesting relationship
between the optimal attempt probability for a link, and the
optimal age of the link and it’s neighboring links. We then
showed that the optimal link attempt probabilities can be
obtained by solving a convex optimization problem, which
can be done distributively using the projected gradient ascent
algorithm.
R EFERENCES
[1] O. K. Sahingoz, “Networking models in flying ad-hoc networks
(FANETs): Concepts and challenges,” J. Intell. Robotics Syst., vol. 74,
pp. 513–527, Apr. 2014.

[2] R. Talak, S. Karaman, and E. Modiano, “Speed limits in autonomous
vehicular networks due to communication constraints,” in Proc. CDC,
pp. 4998–5003, Dec. 2016.
[3] S. Kaul, R. Yates, and M. Gruteser, “Real-time status: How often should
one update?,” in Proc. INFOCOM, pp. 2731–2735, Mar. 2012.
[4] R. Talak, S. Karaman, and E. Modiano, “Optimizing information freshness in wireless networks under general interference constraints,” in
submited to Mobihoc, Jun. 2018.
[5] R. Talak, S. Karaman, and E. Modiano, “Minimizing age-of-information
in multi-hop wireless networks,” in Proc. Allerton, Oct. 2017.
[6] S. Kaul, M. Gruteser, V. Rai, and J. Kenney, “Minimizing age of
information in vehicular networks,” in Proc. SECON, pp. 350–358, Jun.
2011.
[7] L. Huang and E. Modiano, “Optimizing age-of-information in a multiclass queueing system,” in Proc. ISIT, pp. 1681–1685, Jun. 2015.
[8] C. Kam, S. Kompella, and A. Ephremides, “Age of information under
random updates,” in Proc. ISIT, pp. 66–70, Jul. 2013.
[9] S. K. Kaul, R. D. Yates, and M. Gruteser, “Status updates through
queues,” in Proc. CISS, pp. 1–6, Mar. 2012.
[10] E. Najm and R. Nasser, “Age of information: The gamma awakening,”
in Proc. ISIT, pp. 2574–2578, Jul. 2016.
[11] M. Costa, M. Codreanu, and A. Ephremides, “Age of information with
packet management,” in Proc. ISIT, pp. 1583–1587, Jun. 2014.
[12] Q. He, D. Yuan, and A. Ephremides, “Optimizing freshness of information: On minimum age link scheduling in wireless systems,” in Proc.
WiOpt, pp. 1–8, May 2016.
[13] I. Kadota, E. Uysal-Biyikoglu, R. Singh, and E. Modiano, “Minimizing
the age of information in broadcast wireless networks,” in Proc. Allerton,
pp. 844–851, Sep. 2016.
[14] Y.-P. Hsu, E. Modiano, and L. Duan, “Age of information: Design and
analysis of optimal scheduling algorithms,” in Proc. ISIT, pp. 1–5, Jun.
2017.
[15] I. Kadota, A. Sinha, and E. Modiano, “Optimizing age of information
in wireless networks with throughput constraints,” in to appear in Proc.
INFOCOM, Apr. 2018.
[16] S. K. Kaul and R. D. Yates, “Status updates over unreliable multiaccess
channels,” ArXiv e-prints, May 2017.
[17] A. M. Bedewy, Y. Sun, and N. B. Shroff, “Age-optimal information
updates in multihop networks,” in Proc. ISIT, pp. 576–580, Jun. 2017.
[18] R. Talak, I. Kadota, S. Karaman, and E. Modiano, “Scheduling policies
for age minimization in wireless networks with unknown channel state,”
in submitted to ISIT, Jun. 2018.
[19] R. Talak, S. Karaman, and E. Modiano, “Optimizing age of information
in wireless networks with perfect channel state information,” in to
appear in Proc. WiOpt, May 2018.
[20] A. Kumar, D. Manjunath, and J. Kuri, Wireless Networking. Morgan
Kaufmann, 2008.
[21] S. Boyd and L. Vandenberghe, Convex Optimization. Cambridge
University Press, 2004.
[22] R. W. Wolff, Stochastic Modeling and the Theory of Queues. Prentice
Hall, 1 ed., 1989.

A PPENDIX
A. Proof of Lemma 1
Consider a distributed stationary policy with link activation
frequencies fe > 0 for each e ∈ E. For a link e, let Te (i)
be the ith instance when link e was successfully activated,
i.e., the ith instance when Ûe (t) = 1. Let Xe (i) = Te (i) −
Te (i−1) to be the ith inter-(successful) activation time for link
e. Since all the processes involved, namely Se (t) and Ue (t),
are i.i.d. across time
h t, Xe (i)i is geometrically distributed with
rate equal to P Ûe (t) = 1 = γe fe , i.e., P [Xe (i) = k] =
k−1

γe fe (1 − γe fe )
, for all k ∈ {1, 2, . . .}.
We now compute the average age Aave
e for link e. Note that
the age Ae (t) over slots t ∈ {Te (i)+1, . . . Te (i+1)} increases
PTe (i+1)
from 1 to Xe (i) in steps of 1. Therefore, t=T
Ae (t) =
e (i)+1

PXe (i)

m for all i. Then, using renewal theory [22], we can
derive the average age to be
PN PXe (i)
T
1X
ave
i=1
m=1 m
P
Ae (t) = lim
,
Ae = lim sup
m
N →∞
T →∞ T t=1
i=1 Xe (i)
PN 1
i=1 2 Xe (i) (Xe (i) + 1)
= lim
,
PN
N →∞
i=1 Xe (i)
1 E [Xe (i) (Xe (i) + 1)]
=
a.s..
(16)
2
E [Xe (i)]
m=1

1
Computing the moments of Xe (i) we get Aave
e = γe fe a.s..
For peak age, note that the ith peak is equal to the ith inter(successful) activation time Xe (i), i.e., Ae (Te (i)) = Xe (i).
Therefore, we have

Ape = lim sup
T →∞

N (t)
N
1 X
1 X
Ae (Te (i)) = lim
Xe (i),
N →∞ N
N (T ) i=1
i=1

which is equal to E [Xe (1)] =

1
γe fe

a.s.. This proves the result.

B. Proof of Theorem 1

This follows by first making the the substitution pe = ePe ,
qe = eQe , and fe = ehe , and then taking log in each of
the constraints. This is a standard technique in geometric
programming [21]. However, unlike geometric programming,
we don’t need to apply log function to the objective as it is
already convex, and also separable in variables he .
The problem (20) is convex [21], and satisfies slater’s
conditions. As a consequence, the duality gap is zero, and
the problem (20) is equivalent to its Lagrangian dual problem.
Define the Lagrangian function of the optimization problem (20) to be
X
X we

e−he +
νe log ePe + eQe
L (h, P, Q, λ, ν) =
γe
e∈E
e∈E
X
X

+
λe he − Pe −
Qe0 , (21)
e0 ∈Ne

e∈E

for λ ≥ 0 and ν ≥ 0. The dual problem for (20) is given by
Maximize g (λ, ν) ,

(22)

λ≥0,ν≥0

where g (λ, ν) is the dual objective function defines as

Consider the Lagrangian dual
X
X
w
Q e
L(p, q, λ) =
+
λe (pe + qe − 1) .
γe pe e0 ∈Ne qe0
e∈E
e∈E
(17)
The problem (11) satisfies Slater’s conditions, and thus, the
KKT conditions are both necessary and sufficient. Setting
partial derivatives of L with respect to pe and qe to zero,
we obtain
X
pe λe = we Ae , and qe λe =
we0 Ae0 ,
(18)
e0 :e∈Ne0

for all e ∈ E, where Ae = γe pe Q 10
is the age of
e ∈Ne qe0
link e. Equations (18) imply that λe cannot be zero. By
complementary slackness criteria we must have pe + qe = 1.
This, with (18), gives pe = we Ae +P w0 e Ae w 0 A 0 and λe =
e
e
e :e∈N 0
e
P
we Ae + e0 :e∈Ne0 we0 Ae0 . This proves the result.
C. Proof of Theorem 2
The age minimization problem, given in (10), can be written
as by substituting qe = 1 − pe :
X we
Minimize
f ≥0,p≥0,q≥0
γe fe
e∈E
Y
(19)
subject to
fe ≤ p e
qe0 ∀ e ∈ E
e0 ∈Ne

pe + qe ≤ 1 ∀ e ∈ E
Now, substituting Pe = log pe , Qe = log qe , and he = log fe ,
the problem reduces to
X we
Minimize
exp {−he }
h,P,Q
γe
e∈E
X
(20)
subject to he − Pe −
Qe0 ≤ 0 ∀ e ∈ E

g (λ, ν) =Minimize L (h, P, Q, λ, ν) .
h,P,Q

We will now show that the the optimization problem in
Theorem 2 is in fact the dual problem (22).
First note that the Lagrangian function L (h, P, Q, λ, ν) is
strictly convex in h, P, and Q [21]. Thus, first order conditions
∇h,P,Q L = 0 yield the optimal h, P, and Q. Setting these
partial derivatives to 0, we get
X
νe eQe
we −he
νe ePe
,
λe0 = Pe
, and λe =
e
,
λe = Pe
Q
Q
e
e
e +e
e +e
γe
e0 :e∈Ne0
(24)
for all e ∈ E. Adding and dividing the first two equations
in (24) also yields
!
X
λe
νe = λ e +
λe0 , and Pe − Qe = log P
,
0
e0 :e∈Ne0 λe
e0 :e∈Ne0
(25)
respectively, for all e. Substituting (24) and (25) in L, in (21),
we recover g(λ, µ) = G(λ), the objective function in (14),
and therefore, the dual problem (22) is same as the optimization problem in Theorem 2. This proves the first part.
We now show that if λ∗ is the solution to this problem,
then the optimal attempt probability is given by (15). Let f ∗ ,
p∗ , q∗ be the solution to (19), h∗ , P∗ , Q∗ be the solution
to (20), and λ∗ be the solution to the problem in Theorem 2.
Note
link e ∈ E, we must have fe∗ =
Q that,∗ for each
∗
∗
pe e0 ∈Ne qe and pe + qe∗ = 1; as otherwise the objective
function can be reduced by increasing fe∗ and/or p∗e . Since
∗
∗
∗
∗
p∗e = ePe and qe∗ = eQe , we have ePe + eQe = 1. Substituting
this in (24), and using (25), we obtain
λ∗e

∗

p∗e = ePe =

e0 ∈Ne

log (exp {Pe } + exp {Qe }) ≤ 0 ∀ e ∈ E

(23)

which proves the result.

λ∗e +

P

e0 :e∈Ne0

λ∗e0

,

(26)

