Continuum Modeling and Control of Large Nonuniform Networks

Continuum Modeling and Control of
Large Nonuniform Networks
The 49th Annual Allerton Conference on
Communication, Control, and Computing, 2011
Yang Zhang (Colorado State University)
Edwin K. P. Chong (Colorado State University)
Jan Hannig (University of North Carolina)
Don Estep (Colorado State University)
2011 Allerton (Monticello, IL) September 30, 2011 1 / 25

Continuum Modeling and Control of Large Nonuniform Networks Background
Continuum Modeling of Large Networks
Network model:
◮ random processes
◮ discrete time and space indices: k = 1, 2, . . . and n = 1, 2, . . ., N
Traditional method: Monte Carlo simulation
For very large networks: computationally expensive
Continuum limit:
◮ deterministic solutions of partial differential equations (PDEs)
◮ continuous time and space variables: t ∈ [0, T] and s ∈ D ⊂ RJ
Approximate networks by PDEs.
Solving PDEs with well-developed tools: on computer in seconds

Continuum Modeling and Control of Large Nonuniform Networks Network Model
Wireless Sensor Network
Sensor nodes: generate data messages and relay them to
destination nodes at boundary.
All nodes have message queues.
For now, nodes only communicate with immediate neighbors. (Will
consider further communication range later.)
Nodes transmit or receive at each time step.
Nodes share same wireless channel: transmission is successful
only when all other neighbors of receiver are silent.

Quantities of Interest
For now, N nodes uniformly placed at VN = [vN(1), . . . , vN(N)] over
D ⊂ RJ. (Will consider nonuniform networks later.)
ds: distance between neighboring nodes.
Interested in calculating message queue lengths at nodes.
XN(k, n): queue length of node n at time k;
XN(k) = [XN(k, 1), . . . , XN(k, N)] ∈ RN.
Assume node queue length never exceeds maximum queue
length M.
Time step:
dt = ds2
/M.
Incoming trafﬁc G(k, n): number of messages generated at node n
at time k; G(k, n) ∼ Poisson(g(n) := Mgp(vN(n))dt).

Transmission
Let the probability that node n tries to transmit at time k be
XN(k, n)/M: nodes transmit with probability proportional to queue
length.
Pl(k, n): probability of node n transmitting to lth neighbor at time k
Assume
Pl(k, n) = pl(kdt, vN (n)) pl(t, s) : [0, T] × D → R.
pl(t, s) = bl(t, s) + cl(t, s)ds.
bl: diffusion; cl: convection.

Continuum Modeling and Control of Large Nonuniform Networks Continuum Model
Basic Result of Continuum Modeling
Stochastic difference equation of XN(k):
XN(k + 1) = XN(k) + FN(XN(k)/M, U(k)).
Deﬁne fN(x) = EFN(x, U(k)), x ∈ RN.
As N → ∞, fN/ds2 → f in some sense; and z solves PDE
∂z
∂t
(s, t) = f s, z(t, s),
∂z
∂sj
(t, s),
∂2z
∂s2
j
(t, s) , j = 1, . . . , J.
Seq. of networks {XN(k)} indexed by N converges to continuum limit z:
Theorem
Under some conditions, as N and M go to ∞ in a dependent way
(M → ∞ as N → ∞),
max
k,n
XN(k, n)
M
− z(kdt, vN (n)) → 0

2-D Network Example: Stochastic Difference Equation
XN(k + 1) = XN(k) + FN(XN(k)/M, U(k)).
XN(k + 1, i, j) − XN(k, i, j) =



1+G(k,i,j)
M
, with probability
(1 − XN(k, i, j))
×[Pw(k, i − 1, j)XN (k, i − 1, j))(1 − XN(k, i + 1, j))(1 − XN(k, i, j + 1))(1 − XN(k, i, j − 1))
+Pe(k, i + 1, j)XN(k, i + 1, j)(1 − XN(k, i − 1, j))(1 − XN(k, i, j + 1))(1 − XN(k, i, j − 1))
+Pn(k, i, j − 1)XN (k, i, j − 1)(1 − XN(k, i + 1, j))(1 − XN(k, i − 1, j))(1 − XN(k, i, j + 1))
+Ps(k, i, j + 1)XN(k, i, j + 1)(1 − XN(k, i + 1, j))(1 − XN(k, i − 1, j))(1 − XN(k, i, j − 1))]
−1+G(k,i,j)
M
, with probability
XN(k, i, j)
×[Pw(k, i, j)(1 − XN(k, i − 1, j))(1 − XN(k, i − 1, j + 1))(1 − XN(k, i − 1, j − 1))(1 − XN(k, i − 2, j))
+Pe(k, i, j)(1 − XN(k, i + 1, j))(1 − XN(k, i + 1, j + 1))(1 − XN(k, i + 1, j − 1))(1 − XN(k, i + 2, j))
+Ps(k, i, j)(1 − XN(k, i, j − 1))(1 − XN(k, i + 1, j − 1))(1 − XN(k, i − 1, j − 1))(1 − XN(k, i, j − 2))
+Pn(k, i, j)(1 − XN(k, i, j + 1))(1 − XN(k, i + 1, j + 1))(1 − XN(k, i − 1, j + 1))(1 − XN(k, i, j + 2))]
G(k,i,j)
M
, otherwise

2-D Network Example: Monte Carlo Simulation Result

2-D Network Example: PDE
∂z
∂t
(t, x, y) =∇ ·
1
4
(1 − z(t, x, y))3
(1 + 5z(t, x, y))∇z(t, x, y)
+
cw(t, x, y) − ce(t, x, y)
cs(t, x, y) − cn(t, x, y)
z(t, x, y)(1 − z(t, x, y))4
+ u(x, y)

2-D Network Example: PDE Solution

2-D Network Example: Monte Carlo Simulation Result

Continuum Modeling and Control of Large Nonuniform Networks General Uniform PDE
General Transmission Range
Only talked about communication and interference between
immediate neighbors.
Transmission range L: a node at s = (s1, . . . , sJ) only
communicates with nodes at s = (s1 + l1ds, . . . , s1 + lJdsJ),
l1, . . . , lJ ≤ L.
P1 P2
P3 P4
1D network with L = 2.
Corresponding change in range of interference: interfering
neighbors of receiver not necessarily immediate.

Continuum Modeling and Control of Large Nonuniform Networks General Uniform PDE
General Uniform PDE
General uniform PDE for J-dimensional uniform network with
transmission range L:
˙z =
J
j=1
b(j) ∂
∂sj
(1 + (λ(J,L) + 1)z)(1 − z)(λ(J,L)−1) ∂z
∂sj
+ 2(1 − z)(λ(J,L)−1) ∂z
∂sj
∂b(j)
∂sj
+ z(1 − z)λ(J,L)
∂2b(j)
∂s2
j
+
∂
∂sj
c(j)
z(1 − z)λ(J,L) + gp,
where λ(J,L) := (1 + 2L)J − 1, b(j) =
λ(J,L)
l
̺2
jlbl
2 , and c(j) =
λ(J,L)
l ̺jlcl,
where {e1, . . . , eJ} is the natural basis of RJ and
̺jl = (vN(n, l) − vN(n))T (ej).

Continuum Modeling and Control of Large Nonuniform Networks Continuum Model of Nonuniform Networks
Transformation Function of Nonuniform Networks
Only talked about uniform networks.
Consider nonuniform (mobile) network with N nodes over D.
˜vN(k, n): location of node n at time k in nonuniform network.
Transformation function φ(t, s) of nonuniform network maps
uniform node locations into nonuniform ones:
˜vN(k, n) = φ(kdt, vN(n)).
φ characterizes node locations of nonuniform network.

Continuum Limits of Mirroring Networks
Network behavior of a certain network, for all possible m, n and k:
◮ probability that node m sends to node n at time k;
◮ whether node m and n interfere.
Two seq.’s of networks indexed by N are said to mirror each other
if, for each N, the N-node networks in both seq.’s have the same
network behavior (assume same initial state and incoming trafﬁc).
Theorem (Mirroring Networks Theorem)
Let A be a seq. of uniform networks. Suppose seq. B mirrors A and
has transformation function φ. Then A → q(t, s) iff
B → u(t, s) =: q(t, θ(t, s)).
(θ: inverse of φ w.r.t space variable s, i.e., θ(t, φ(t, s)) = s.)

Continuum Limits of Nonuniform Networks
Goal: for seq. B of nonuniform networks with given network
behavior and transformation function φ, ﬁnd its continuum limit u.
By Mirroring Networks Theorem, if seq. A of uniform networks
mirrors B, then
“A → q(t, s)” ⇒ “B → u(t, s) =: q(t, θ(t, s))” (θ: inverse of φ).
Uniform A with given network behavior → Known uniform PDE:
˙q = Q s, q,
∂q
∂sj
,
∂2q
∂s2
j
.
By u(t, s) =: q(t, θ(t, s)) and chain rule, B → PDE:
˙u = Q


θ, u,
∂u
∂sj
∂θ
∂sj
,
∂2u
∂s2
j
∂θ
∂sj
2
−
∂2θ
∂s2
j
∂u
∂sj
∂θ
∂sj
3


 .

Continuum Modeling and Control of Large Nonuniform Networks Control of Nonuniform Networks
Network Control Based on Continuum Model
Network behavior depends on transmission range L and prob. Pl
of transmitting to each neighbor.
Pl(k, n) = pl(kdt, vN (n)), pl(t, s) = bl(t, s) + cl(t, s)ds.
General uniform PDE
˙z =
J
j=1
b
(j) ∂
∂sj
(1 + (λ(J,L) + 1)z)(1 − z)
(λ(J,L) −1) ∂z
∂sj
+ 2(1 − z)
λ(J,L)−1 ∂z
∂sj
∂b(j)
∂sj
+ z(1 − z)
λ(J,L)
∂2
b(j)
∂s2
j
+
∂
∂sj
c
(j)
z(1 − z)
λ(J,L) + gp,
⇒ Continuum limit also depends on L, bl, and cl.
——————————
For uniform networks:
Control network behavior.
⇑
Set L and bl and cl.
⇓
Control global characteristic (continuum limit) of network.

Network Control Based on Continuum Model – cont’d
For example, we can control a uniform network in order to achieve
a steady state with well-balanced trafﬁc load over the domain.
Now the nodes start to move, and we still want similar global
network characteristic.
How to control the nonuniform (mobile) network?

Control of Nonuniform Networks
Goal: for a seq. B of nonuniform (mobile) networks with given
transformation function φ, ﬁnd its network behavior s.t. B → given
continuum limit u that solves known PDE:
˙u = Γ s, u,
∂u
∂sj
,
∂2u
∂s2
j
.
By Mirroring Networks Theorem, if seq. A of uniform networks
converges to q(t, s) := u(t, φ(t, s)), then
“B mirrors A” ⇒ “B → u”.
New goal: ﬁnd network behavior of A (since B mirrors A).

Control of Nonuniform Networks – cont’d
By chain rule, q(t, s) = u(t, φ(t, s)), and ˙u = Γ s, u, ∂u
∂sj
, ∂2u
∂s2
j
, A →
PDE
˙q = Γ


φ, q,
∂q
∂sj
∂φ
∂sj
,
∂2q
∂s2
j
∂φ
∂sj
2
−
∂2φ
∂s2
j
∂q
∂sj
∂φ
∂sj
3


 .
Meanwhile, PDE of A of uniform networks should be a special
case of general uniform PDE presented before:
˙q =
J
j=1
b(j) ∂
∂sj
(1 + (λ(J,L) + 1)q)(1 − q)(λ(J,L)−1) ∂q
∂sj
+ 2(1 − q)(λ(J,L)−1) ∂q
∂sj
∂b(j)
∂sj
+ q(1 − q)λ(J,L)
∂2b(j)
∂s2
j
+
∂
∂sj
c(j)
q(1 − q)λ(J,L) + gp,

Control of Nonuniform Networks – cont’d
Combine two equations above and get the comparison equation:
Γ


φ, q,
∂q
∂sj
∂φ
∂sj
,
∂2
q
∂s2
j
∂φ
∂sj
2
−
∂2
φ
∂s2
j
∂q
∂sj
∂φ
∂sj
3


 =
J
j=1
b(j) ∂
∂sj
(1 + (λ(J,L) + 1)q)(1 − q)(λ(J,L)−1) ∂q
∂sj
+ 2(1 − q)(λ(J,L)−1) ∂q
∂sj
∂b(j)
∂sj
+ q(1 − q)λ(J,L)
∂2b(j)
∂s2
j
+
∂
∂sj
c(j)
q(1 − q)λ(J,L) + gp,
Solve comparison equation for L, bl and cl.
Find desired network behavior.
We show two examples.

1-D Example
Want nonuniform B → PDE:
˙u = Γ s, u,
∂u
∂sj
,
∂2u
∂s2
j
=
∂
∂s
1
2
(1 − u)(1 + 3u)
∂u
∂s
+ gp.
Then uniform A with desired network behavior → PDE:
˙q = Γ


φ, q,
∂q
∂sj
∂φ
∂sj
,
∂2
q
∂s2
j
∂φ
∂sj
2
−
∂2
φ
∂s2
j
∂q
∂sj
∂φ
∂sj
3



=
(1 − q)(1 + 3q)
2 ∂φ
∂s
2
∂2q
∂s2
+
(1 − 3q)
∂φ
∂s
2
∂q
∂s
2
+
1
4
(1 − q)(1 + 3q)
∂
∂s



1
∂φ
∂s
2



∂q
∂s
+ gp(φ).
Solve the comparison PDE for L, bl, and cl:
b
∂
∂s
(1 + 5q)(1 − q)3 ∂q
∂s
+ 2(1 − q)3 ∂q
∂s
∂b
∂s
+ q(1 − q)4 ∂2b
∂s2
+
∂
∂s
(cq(1 − q)) + g′
p
=
(1 − q)(1 + 3q)
2 ∂φ
∂s
2
∂2q
∂s2
+
(1 − 3q)
∂φ
∂s
2
∂q
∂s
2
+
1
4
(1 − q)(1 + 3q)
∂
∂s



1
∂φ
∂s
2



∂q
∂s
+ gp(φ).

1-D Example: Simulation Result
−1 −0.5 0 0.5 1
0
0.01
0.02
0.03
0.04
0.05
◦ Nonuniform network —— Desired continuum limit

2-D Example
Want nonuniform B → PDE:
˙u = Γ

s, u,
∂u
∂sj
,
∂2
u
∂s2
j

 = ˙u =
3
8
2
j=1
∂
∂sj
(1 + 9u)(1 − u)
7 ∂u
∂sj
+ gp.
Then uniform A with desired network behavior → PDE:
˙q = Γ





φ, q,
∂q
∂sj
∂φ
∂sj
,
∂2q
∂s2
j
∂φ
∂sj
2
−
∂2φ
∂s2
j
∂q
∂sj
∂φ
∂sj
3





=
2
j=1





3
8
(1 − q)7
(1 + 9q)
∂φj
∂s
2
∂2
q
∂x2
j
+
3
16
(1 − q)
7
(1 + 9q)
∂
∂xj





1
∂φj
∂s
2





∂q
∂xj
+
3
4
(1 − 36q)(1 − q)6
∂φj
∂s
2
∂q
∂xj
2





+ gp(φ).
Solve the comparison PDE for L, bl, and cl:
2
j=1
b
(j) ∂
∂sj
(1 + 25q)(1 − q)
23 ∂q
∂sj
+ 2(1 − q)
23 ∂q
∂sj
∂b(j)
∂sj
+ q(1 − q)
24 ∂2
b(j)
∂s2
j
+
∂
∂sj
c
(j)
q(1 − q)
24
+ g
′
p
=
2
j=1





3
8
(1 − q)7
(1 + 9q)
∂φj
∂s
2
∂2
q
∂x2
j
+
3
16
(1 − q)
7
(1 + 9q)
∂
∂xj





1
∂φj
∂s
2





∂q
∂xj
+
3
4
(1 − 36q)(1 − q)6
∂φj
∂s
2
∂q
∂xj
2





+ gp(φ) (φj is the jth component of φ).

2-D Example: Simulation Result
−1 −0.5 0 0.5 1
−1
−0.5
0
0.5
1
−1 −0.5 0 0.5 1
−1
−0.5
0
0.5
1
1
2
3
4
5
6
7
x 10
−3
Nonuniform network Desired continuum limit

Continuum Modeling and Control of Large Nonuniform Networks

Recommended

More Related Content

What's hot (20)

Similar to Continuum Modeling and Control of Large Nonuniform Networks (20)

Recently uploaded (20)

Continuum Modeling and Control of Large Nonuniform Networks