# Continuum Modeling and Control of Large Nonuniform Wireless Networks via Nonlinear Partial Differential Equations

Authors: Yang Zhang; Edwin K. P. Chong; Jan Hannig; Donald Estep
Journal: Abstract and Applied Analysis
 (2013)

---

## Abstract

We introduce a continuum modeling method to approximate a class of large wireless networks by nonlinear partial differential equations (PDEs). This method is based on the convergence of a sequence of underlying Markov chains of the network indexed byN, the number of nodes in the network. As N goes to infinity, the sequence converges to a continuum limit, which is the solution of a certain nonlinear PDE. We first describe PDE models for networks with uniformly located nodes and then generalize to networks with nonuniformly located, and possibly mobile, nodes. Based on the PDE models, we develop a method to control the transmissions in nonuniform networks so that the continuum limit is invariant under perturbations in node locations. This enables the networks to maintain stable global characteristics in the presence of varying node locations.


---

## Body

## 1. Introduction

This paper is concerned with modeling and control of large stochastic networks via nonlinear partial differential equations (PDEs). Recently, we introduced a continuum modeling method for large wireless networks modeled by a certain class of Markov chains. We start with a family of networks indexed byN, the number of nodes, and a related sequence of Markov chains. Under appropriate conditions, the sequence of Markov chains converges in a certain sense to a continuum limit, which is the solution of a nonlinear PDE, as N goes to infinity. Therefore we can use the limiting PDE to approximate the large network [1–5]. This result assumed uniform networks, that is, networks with immobile and uniformly located nodes. Moreover, the model assumes that the nodes have a fixed transmission range in the sense that they communicate (exchange data and interfere) only with their immediate neighbors.The work in this paper builds on the above method. We consider nonuniform networks, that is, networks with nonuniformly located and possibly mobile nodes. We also consider nodes with more general transmission ranges; that is, they may communicate with neighbors further away than immediate ones. For such networks, a natural problem would be to find their continuum limits (the limiting PDEs). A less obvious but more interesting problem concerns the control of nonuniform networks. For example, suppose that a uniform network with certain transmissions achieves a steady state that is desirable in terms of global traffic distribution (e.g., load is well balanced over the network). Further suppose that we want the network to maintain such global characteristics if the nodes are no longer at their original uniform locations. Then the problem is to control the transmissions in the network such that its continuum limit remains invariant.We address these problems as follows. First, we present a more general network model than that in the existing results [1, 2] and derive its limiting PDEs in the setting of uniform node locations. This generalization is necessary for the discussion of the control of nonuniform networks later. Second, through transformation between uniform and nonuniform node locations, we derive limiting PDEs for nonuniform networks. Finally, by comparing the limiting PDEs of corresponding uniform and nonuniform networks, we develop a method to control the transmissions of nonuniform networks so that the continuum limit is invariant under node locations. In other words, we can maintain a stable global characteristic for nonuniform networks.The remainder of the paper is organized as follows. First, to describe and contextualize our contribution in this paper, we provide in Section2 the existing results on continuum modeling of uniform networks. Next, we present the main results of the paper in Section 3; in Section 3.1, we introduce a more general network model and derive its limiting PDEs; in Section 3.2, we derive limiting PDEs for nonuniform and possibly mobile networks; and in Section 3.3, we present a control method for nonuniform networks so that the continuum limit is invariant under node locations. Then we present some numerical examples in Section 4 and conclude the paper in Section 5.


## 2. Existing Results on Continuum Modeling of Stochastic Networks

This section is devoted to reviewing our continuum modeling method [1, 2] for stochastic networks whose nodes are uniformly located and have a fixed transmission range. The study of nonuniform networks in this paper builds on this result. We first describe the network model and then present the result on the convergence of its underlying Markov chain to its continuum limit, which is the solution of a limiting PDE. We discuss some related literature on stochastic network modeling at the end of this section.We will generalize this modeling method to uniform networks with more general transmission ranges in Section3.1 and to nonuniform networks in Section 3.2.


### 2.1. Network Model

Consider a compact, convex Euclidean domain𝒟⊂ℝJ representing a spatial region, with dimension J. In practice, J is typically either 1 or 2. However, our analysis in this paper applies to general J, though our examples are for J=1,2. Next, consider N points VN={vN(1),…,vN(N)} in 𝒟 that form a uniform grid. We refer to these points as grid points and denote the distance between any two neighboring grid points by dsN.Now consider a network ofN wireless sensor nodes over 𝒟, where the nodes are labeled by n=1,…,N. By a uniform network we mean that node n is located at the grid point vN(n)∈VN, where n=1,…,N. We focus on uniform networks in this section.The sensor nodes generate, according to a probability distribution, data messages that need to be communicated to thedestination nodes located on the boundary of 𝒟, which represent specialized devices that collect the sensor data. The sensor nodes also serve as relays for routing messages to the destination nodes. Each sensor node has the capacity to store messages in a queue and is capable of either transmitting or receiving messages to or from its immediate neighbors. In other words, it has a fixed 1-step transmission range. (We will generalize to further steps of transmission range later in Section 3.1.) At each time instant k=0,1,…, each sensor node probabilistically decides to be a transmitter or receiver, but not both. This simplified rule of transmission allows for a relatively simple representation. We illustrate such a uniform network over a two-dimensional (2D) domain in Figure 1(a).(a) An illustration of a uniform wireless sensor network over a 2D domain. Destination nodes are located at the far edge. We show the possible path of a message originating from a node located in the left-front region. (b) An illustration of the collision protocol: reception at a node fails when one of its other neighbors transmits (regardless of the intended receiver). (c) An illustration of the time evolution of the queues in the 1D network model.
(a)
(b)
(c)In this network, communication between nodes is interference limited because all nodes share the same wireless channel. We assume a simple collision protocol: a transmission from a transmitter to an immediate neighboring receiver is successful if and only if none of the other immediate neighbors of the receiver is a transmitter, as illustrated in Figure1(b). This is the case presented in [1]. (Later, in Section 3.1, when we consider further transmission ranges, interference will occur between not only immediate neighbors, but also neighbors further apart.) In a successful transmission, one message is transmitted from the transmitter to the receiver.We assume that the probability that a node decides to be a transmitter is a function of its normalized queue length (normalized by an “averaging” parameterM). That is, at time k, node n decides to be a transmitter with probability W(n,XN,M(k,n)/M), where XN,M(k,n) is the queue length of node n at time k, and W is a given function.The queue lengthsXN,M(k)=[XN,M(k,1),…,XN,M(k,N)]⊤∈ℝN (the superscript ⊤ represents transpose) form a Markov chain whose evolution is given by
(1)XN,M(k+1)=XN,M(k)+FN(XN,M(k)M,UN(k)).Here, theUN(k) are i.i.d. random vectors that do not depend on the state XN,M(k), and FN is a given function. As a concrete example, below we present the expression of (1) for a particular network.For the sake of explanation, we simplify the problem further and consider a 1D domain (2D networks will be treated in the next section). Here,N sensor nodes are uniformly located in an interval 𝒟⊂ℝ and labeled by n=1,…,N. The destination nodes are located on the boundary of 𝒟, labeled by n=0 and n=N+1.We assume that if noden is a transmitter at a certain time instant, it randomly chooses to transmit one message to the right or the left immediate neighbor with probability Pr(n) and Pl(n), respectively, where Pr(n)+Pl(n)≤1. In contrast to strict equality, the inequality here allows for a more general stochastic model of transmission: after a sensor node randomly decides to transmit over the wireless channel, there is still a positive probability that the message is not transferred to its intended receiver (what might be called an “outage”).The special destination nodes at the boundaries of the domain do not have queues; they simply receive any message transmitted to them and never themselves transmit anything. We illustrate the time evolution of the queues in the network in Figure1(c).For the particular network introduced above, we have the following expression forUN(k) in (1)
(2)UN(k)=[(k,1),…,Q(k,N),T(k,1),…,T(k,N),G(k,1),…,G(k,N)]⊤,
which is a random vector comprising independent random variables: Q(k,n) are uniform random variables on [0,1] used to determine if the node is a transmitter or not; T(k,n) are ternary random variables used to determine the direction in which a message is passed, which take values R, L, and S (representing transmitting to the right, the left, and neither, resp.) with probabilities Pr(n), Pl(n), and 1-(Pr(n)+Pl(n)), respectively; and G(k,n) are the number of messages generated at node n at time k. We model G(k,n) by independent Poisson random variables with mean g(n) and call g(n) the incoming traffic to the network.For a genericx=[x1,…,xN]⊤∈ℝN, the nth component of FN(x,UN(k)), where n=1,…,N, is
(3)1+G(k,n)ifQ(k,xn-1)<W(n-1,xn-1),T(k,n-1)=R,Q(k,xn)>W(n,xn),Q(k,xn+1)>W(n+1,xn+1);orQ(k,xn+1)<W(n+1,xn+1),T(k,n+1)=L,Q(k,xn)>W(n,xn),Q(k,xn-1)>W(n-1,xn-1)-1+G(k,n)ifQ(k,xn)<W(n,xn),T(k,n)=L,Q(k,xn-1)>W(n-1,xn-1),Q(k,xn-2)>W(n-2,xn-2);orQ(k,xn)<W(n,xn),T(k,n)=R,Q(k,xn+1)>W(n+1,xn+1),Q(k,xn+2)>W(n+2,xn+2)G(k,n)otherwise,
where xn with n≤0 or n≥N+1 are defined to be zero, and W is the function that specifies the probability that a node decides to be a transmitter, as defined earlier. Here, the three possible values of FN correspond to the three events that, at time k, node n successfully receives one message, successfully transmits one message, and does neither of the above, respectively. The inequalities and equations on the right describe conditions under which these three events occur: for example, Q(k,xn-1)<W(n-1,xn-1) corresponds to the choice of node n-1 to be a transmitter at time k, T(k,n-1)=R corresponds to its choice to transmit to the right, and so on.We assume thatW(n,y)=min(1,y). (We will use this assumption throughout the paper.) Under this assumption, the probability that a node is a transmitter increases linearly with its queue length, up to a maximum value of 1 when the normalized queue length exceeds 1. In general, we would naturally adopt a W function that is increasing in the queue length, so that nodes with more data are more likely to transmit. Here, we assume this function to be linear purely for the sake of simplicity. We could have used a more complicated increasing function. However, doing so complicates the derivation of the resulting PDE and does not serve any insightful purpose.


### 2.2. Continuum Limit of the Markov Chain

Next, we present in Theorem2 a result on the convergence of the Markov chain (1) to its continuum limit, which is the solution of a PDE. Based on this theorem, we can approximate the network introduced above by the limiting PDE. We stress that this theorem is not limited to the particular network model above but holds for uniform networks in a more general setting, which we will introduce later in Section 3.1.The Markov chain model (1) is related to a deterministic difference equation. We set
(4)fN(x)=EFN(x,UN(k)),x∈ℝN,
and define xN,M(k)=[xN,M(k,1),…,xN,M(k,N)]⊤∈ℝN by
(5)xN,M(k+1)=xN,M(k)+1MfN(xN,M(k)),xN,M(0)=XN,M(0)Ma.s.
(“a.s.” is short for “almost surely”).Example 1.
For the 1D 1-step network model in Section2.1, it follows from (3) (with the particular choice of W(n,y)=min(1,y)) that, for x=[x1,…,xN]⊤∈[0,1]N, the nth component of fN(x) in its corresponding deterministic difference equation (5), where n=1,…,N, is (after some tedious algebra, as described in [3])
(6)(1-xn)[Pr(n-1)xn-1(1-xn+1)+Pl(n+1)xn+1(1-xn-1)]-xn[Pr(n)(1-xn+1)(1-xn+2)+Pl(n)(1-xn-1)(1-xn-2)]+g(n),
where xn with n≤0 or n≥N+1 are defined to be zero.We now construct the PDE whose solution describes the limiting behavior of the Markov chain.For any continuous functionw:𝒟→ℝ, let yN be the vector in ℝN composed of the values of w at the grid points vN(n); that is, yN=[w(vN(1)),…,w(vN(N))]⊤. Given a point s∈𝒟, we let {sN}⊂𝒟 be any sequence of grid points sN∈VN such that as N→∞, sN→s. Let fN(yN,sN) be the component of the vector fN(yN) corresponding to the location sN; that is, if sN=vN(n)∈VN, then fN(yN,sN) is the nth component of fN(yN).Assume that there exists a functionf such that as N→∞, given s in the interior of 𝒟, for any sequence of grid points sN→s,
(7)fN(yN,sN)dsN2⟶f(sN,w(sN),∇w(sN),∇2w(sN)).
Here, ∇iw represents all the ith order derivatives of w, where i=1,2. These assumptions are technical conditions on the asymptotic behavior of the sequence of functions {fN} that insure that fN(yN,sN) is asymptotically close to an expression that looks like the right-hand side of a time-dependent PDE. Such conditions are familiar in the context of PDE limits of Brownian motion. Checking these conditions often amounts to a simple algebraic exercise.Assume that there exists a unique functionz:[0,T]×𝒟→ℝ that solves the limiting PDE
(8)z˙(t,s)=f(s,z(t,s),∇z(t,s),∇2z(t,s)),
with boundary condition z(t,s)=0 and initial condition z(0,s)=z0(s). Throughout the paper we assume that XN,M(0,n)/M=z0(vN(n)) a.s. for each n. We call XN,M(0) the initial state of the network.Establishing existence and uniqueness for the resulting nonlinear models is a difficult problem in theoretical analysis of partial differential equations in general. The techniques are heavily dependent on the particular form off. Therefore, as is common with numerical analysis, we assume that this has been established. Below, limiting PDE of the network is a nonlinear diffusion-convection problem. Existence and uniqueness for such problems for “small” data and short times can be established under general conditions. Key ingredients are coercivity, which will hold as long as z is bounded away from 1, and diffusion dominance, which will also hold as long as z is bounded above.We now present a convergence theorem from [1], which states that the Markov chain XN,M(k) converges uniformly to the solution z of its limiting PDE, as N→∞ and M→∞ in a dependent way. By this we mean that we set M to be a function of N, written MN, such that MN→∞ as N→∞. Then we can treat XN,M as sequences of the single index N, written XN. We apply such changes of notation throughout the rest of the paper wheneverM is treated as a function of N. Define the time step
(9)dtN=dsN2MN
and the total number of time steps KN=⌊T/dtN⌋.Theorem 2.
Almost surely, there exist a sequence{γN}, c0<∞, N0, and M^1<M^2<M^3,…, such that as N→∞, γN→0, and for each N≥N0 and each MN≥M^N,
(10)maxk=0,…,KNn=1,…,N|XN(k,n)MN-z(kdtN,vN(n))|<c0γN.Hence we can approximate the Markov chain by its continuum limit, the limiting PDE solution, and the accuracy of the approximation increases withN.Example 3.
As a concrete example, we now construct the limiting PDE for the 1D 1-step network model in Section2.1. To satisfy the conditions on fN introduced above, we make further assumptions to the network model. We assume that there are functions pr and pl from 𝒟 to ℝ such that
(11)Pr(n)=pr(vN(n)),Pl(n)=pl(vN(n));
and further that
(12)pr(s)=12+cr(s)dsN,pl(s)=12+cl(s)dsN,
where cr and cl are functions from 𝒟 to ℝ. Let c=cl-cr. We call c the convection.
In order to guarantee that the number of messages entering the system from outside over finite time intervals remains finite throughout the limiting process, we set the incoming traffic(13)g(n)=Mgp(vN(n))dtN.
We call gp the incoming traffic function. Assume that cl,cr, and gp are in 𝒞1.
By these assumptions, it follows from (6) that the limiting PDE (8) for the 1D 1-step network is as follows:
(14)z˙=12∂∂s((1-z)(1+3z)∂z∂s)+∂∂s(cz(1-z)2)+gp,
with boundary condition z=0. The detailed derivation for this PDE was presented in [3].This is a nonlinear diffusion-convection PDE. Note that the computations needed to obtain this require tedious but elementary algebraic manipulations. For this purpose, we found it helpful to use the symbolic tools in Matlab. A comparison of this PDE and the simulation of the corresponding network is provide in Section4.1.1.


### 2.3. The Related Literature

The modeling and analysis of stochastic networks is a large field of research and much of the previous contributions share goals with our continuum modeling method.The analysis for establishing our continuum modeling result used Kushner’s ordinary differential equation (ODE) method [6], which is closely related to the line of research called stochastic approximation. This line of research was started by Robbins and Monro [7] and Kiefer and Wolfowitz [8] in the early 1950s and widely used in many areas (see, e.g., [9, 10], for surveys). These results do not study the “large-system” limit in the same sense as our method, and the limits of the system they study are ODEs instead of PDEs. Markov chains modeling’s various systems have also been shown by other endeavors to converge to ODEs [11, 12], abstract Cauchy problems [13], or other stochastic processes [6, 14]. These results use methods different from Kushner’s but share with it the principle idea in weak convergence theory [6, 14, 15].There are a variety of other analysis methods for large systems taking completely different approaches. For example, the well-cited work of Gupta and Kumar [16], followed by many others (e.g., [17, 18]), derives scaling laws of network performance parameters (e.g., throughput); many efforts based on mean field theory [19–22] or on the theory of large deviations [23–25] study the limit of the so-called empirical (or occupancy) measure or distribution. These approaches differ from our work because they do not study the spatiotemporal characteristics of the system.There do exist numerous continuum models in a wide spectrum of areas that formulate spatiotemporal phenomena (e.g., [26–29]), many of which use PDEs. All these works differ from our continuum limit method both by the properties of the system being studied and the analytic approaches. In addition, most of them study distributions of limiting processes that are random, while our limiting functions themselves are deterministic.There is a vast literature on the convergence of a large variety of network models different from ours, to fluid and diffusion limits [30–35]. Unlike our work, this field of research focuses primarily on networks with a fixed number of nodes.There are well-established mathematical tools to solve PDEs, which include analytical methods, such as the method of characteristics, integral transforms [36], and asymptotic methods [37], and numerical methods such as the finite element method [38] and the finite difference method [39]. The continuum model allows us to use these tools to greatly reduce computation time. The limiting PDEs for the networks in this paper can be solved by computer software packages in Matlab or Comsol that use numerical methods.


## 2.1. Network Model

Consider a compact, convex Euclidean domain𝒟⊂ℝJ representing a spatial region, with dimension J. In practice, J is typically either 1 or 2. However, our analysis in this paper applies to general J, though our examples are for J=1,2. Next, consider N points VN={vN(1),…,vN(N)} in 𝒟 that form a uniform grid. We refer to these points as grid points and denote the distance between any two neighboring grid points by dsN.Now consider a network ofN wireless sensor nodes over 𝒟, where the nodes are labeled by n=1,…,N. By a uniform network we mean that node n is located at the grid point vN(n)∈VN, where n=1,…,N. We focus on uniform networks in this section.The sensor nodes generate, according to a probability distribution, data messages that need to be communicated to thedestination nodes located on the boundary of 𝒟, which represent specialized devices that collect the sensor data. The sensor nodes also serve as relays for routing messages to the destination nodes. Each sensor node has the capacity to store messages in a queue and is capable of either transmitting or receiving messages to or from its immediate neighbors. In other words, it has a fixed 1-step transmission range. (We will generalize to further steps of transmission range later in Section 3.1.) At each time instant k=0,1,…, each sensor node probabilistically decides to be a transmitter or receiver, but not both. This simplified rule of transmission allows for a relatively simple representation. We illustrate such a uniform network over a two-dimensional (2D) domain in Figure 1(a).(a) An illustration of a uniform wireless sensor network over a 2D domain. Destination nodes are located at the far edge. We show the possible path of a message originating from a node located in the left-front region. (b) An illustration of the collision protocol: reception at a node fails when one of its other neighbors transmits (regardless of the intended receiver). (c) An illustration of the time evolution of the queues in the 1D network model.
(a)
(b)
(c)In this network, communication between nodes is interference limited because all nodes share the same wireless channel. We assume a simple collision protocol: a transmission from a transmitter to an immediate neighboring receiver is successful if and only if none of the other immediate neighbors of the receiver is a transmitter, as illustrated in Figure1(b). This is the case presented in [1]. (Later, in Section 3.1, when we consider further transmission ranges, interference will occur between not only immediate neighbors, but also neighbors further apart.) In a successful transmission, one message is transmitted from the transmitter to the receiver.We assume that the probability that a node decides to be a transmitter is a function of its normalized queue length (normalized by an “averaging” parameterM). That is, at time k, node n decides to be a transmitter with probability W(n,XN,M(k,n)/M), where XN,M(k,n) is the queue length of node n at time k, and W is a given function.The queue lengthsXN,M(k)=[XN,M(k,1),…,XN,M(k,N)]⊤∈ℝN (the superscript ⊤ represents transpose) form a Markov chain whose evolution is given by
(1)XN,M(k+1)=XN,M(k)+FN(XN,M(k)M,UN(k)).Here, theUN(k) are i.i.d. random vectors that do not depend on the state XN,M(k), and FN is a given function. As a concrete example, below we present the expression of (1) for a particular network.For the sake of explanation, we simplify the problem further and consider a 1D domain (2D networks will be treated in the next section). Here,N sensor nodes are uniformly located in an interval 𝒟⊂ℝ and labeled by n=1,…,N. The destination nodes are located on the boundary of 𝒟, labeled by n=0 and n=N+1.We assume that if noden is a transmitter at a certain time instant, it randomly chooses to transmit one message to the right or the left immediate neighbor with probability Pr(n) and Pl(n), respectively, where Pr(n)+Pl(n)≤1. In contrast to strict equality, the inequality here allows for a more general stochastic model of transmission: after a sensor node randomly decides to transmit over the wireless channel, there is still a positive probability that the message is not transferred to its intended receiver (what might be called an “outage”).The special destination nodes at the boundaries of the domain do not have queues; they simply receive any message transmitted to them and never themselves transmit anything. We illustrate the time evolution of the queues in the network in Figure1(c).For the particular network introduced above, we have the following expression forUN(k) in (1)
(2)UN(k)=[(k,1),…,Q(k,N),T(k,1),…,T(k,N),G(k,1),…,G(k,N)]⊤,
which is a random vector comprising independent random variables: Q(k,n) are uniform random variables on [0,1] used to determine if the node is a transmitter or not; T(k,n) are ternary random variables used to determine the direction in which a message is passed, which take values R, L, and S (representing transmitting to the right, the left, and neither, resp.) with probabilities Pr(n), Pl(n), and 1-(Pr(n)+Pl(n)), respectively; and G(k,n) are the number of messages generated at node n at time k. We model G(k,n) by independent Poisson random variables with mean g(n) and call g(n) the incoming traffic to the network.For a genericx=[x1,…,xN]⊤∈ℝN, the nth component of FN(x,UN(k)), where n=1,…,N, is
(3)1+G(k,n)ifQ(k,xn-1)<W(n-1,xn-1),T(k,n-1)=R,Q(k,xn)>W(n,xn),Q(k,xn+1)>W(n+1,xn+1);orQ(k,xn+1)<W(n+1,xn+1),T(k,n+1)=L,Q(k,xn)>W(n,xn),Q(k,xn-1)>W(n-1,xn-1)-1+G(k,n)ifQ(k,xn)<W(n,xn),T(k,n)=L,Q(k,xn-1)>W(n-1,xn-1),Q(k,xn-2)>W(n-2,xn-2);orQ(k,xn)<W(n,xn),T(k,n)=R,Q(k,xn+1)>W(n+1,xn+1),Q(k,xn+2)>W(n+2,xn+2)G(k,n)otherwise,
where xn with n≤0 or n≥N+1 are defined to be zero, and W is the function that specifies the probability that a node decides to be a transmitter, as defined earlier. Here, the three possible values of FN correspond to the three events that, at time k, node n successfully receives one message, successfully transmits one message, and does neither of the above, respectively. The inequalities and equations on the right describe conditions under which these three events occur: for example, Q(k,xn-1)<W(n-1,xn-1) corresponds to the choice of node n-1 to be a transmitter at time k, T(k,n-1)=R corresponds to its choice to transmit to the right, and so on.We assume thatW(n,y)=min(1,y). (We will use this assumption throughout the paper.) Under this assumption, the probability that a node is a transmitter increases linearly with its queue length, up to a maximum value of 1 when the normalized queue length exceeds 1. In general, we would naturally adopt a W function that is increasing in the queue length, so that nodes with more data are more likely to transmit. Here, we assume this function to be linear purely for the sake of simplicity. We could have used a more complicated increasing function. However, doing so complicates the derivation of the resulting PDE and does not serve any insightful purpose.


## 2.2. Continuum Limit of the Markov Chain

Next, we present in Theorem2 a result on the convergence of the Markov chain (1) to its continuum limit, which is the solution of a PDE. Based on this theorem, we can approximate the network introduced above by the limiting PDE. We stress that this theorem is not limited to the particular network model above but holds for uniform networks in a more general setting, which we will introduce later in Section 3.1.The Markov chain model (1) is related to a deterministic difference equation. We set
(4)fN(x)=EFN(x,UN(k)),x∈ℝN,
and define xN,M(k)=[xN,M(k,1),…,xN,M(k,N)]⊤∈ℝN by
(5)xN,M(k+1)=xN,M(k)+1MfN(xN,M(k)),xN,M(0)=XN,M(0)Ma.s.
(“a.s.” is short for “almost surely”).Example 1.
For the 1D 1-step network model in Section2.1, it follows from (3) (with the particular choice of W(n,y)=min(1,y)) that, for x=[x1,…,xN]⊤∈[0,1]N, the nth component of fN(x) in its corresponding deterministic difference equation (5), where n=1,…,N, is (after some tedious algebra, as described in [3])
(6)(1-xn)[Pr(n-1)xn-1(1-xn+1)+Pl(n+1)xn+1(1-xn-1)]-xn[Pr(n)(1-xn+1)(1-xn+2)+Pl(n)(1-xn-1)(1-xn-2)]+g(n),
where xn with n≤0 or n≥N+1 are defined to be zero.We now construct the PDE whose solution describes the limiting behavior of the Markov chain.For any continuous functionw:𝒟→ℝ, let yN be the vector in ℝN composed of the values of w at the grid points vN(n); that is, yN=[w(vN(1)),…,w(vN(N))]⊤. Given a point s∈𝒟, we let {sN}⊂𝒟 be any sequence of grid points sN∈VN such that as N→∞, sN→s. Let fN(yN,sN) be the component of the vector fN(yN) corresponding to the location sN; that is, if sN=vN(n)∈VN, then fN(yN,sN) is the nth component of fN(yN).Assume that there exists a functionf such that as N→∞, given s in the interior of 𝒟, for any sequence of grid points sN→s,
(7)fN(yN,sN)dsN2⟶f(sN,w(sN),∇w(sN),∇2w(sN)).
Here, ∇iw represents all the ith order derivatives of w, where i=1,2. These assumptions are technical conditions on the asymptotic behavior of the sequence of functions {fN} that insure that fN(yN,sN) is asymptotically close to an expression that looks like the right-hand side of a time-dependent PDE. Such conditions are familiar in the context of PDE limits of Brownian motion. Checking these conditions often amounts to a simple algebraic exercise.Assume that there exists a unique functionz:[0,T]×𝒟→ℝ that solves the limiting PDE
(8)z˙(t,s)=f(s,z(t,s),∇z(t,s),∇2z(t,s)),
with boundary condition z(t,s)=0 and initial condition z(0,s)=z0(s). Throughout the paper we assume that XN,M(0,n)/M=z0(vN(n)) a.s. for each n. We call XN,M(0) the initial state of the network.Establishing existence and uniqueness for the resulting nonlinear models is a difficult problem in theoretical analysis of partial differential equations in general. The techniques are heavily dependent on the particular form off. Therefore, as is common with numerical analysis, we assume that this has been established. Below, limiting PDE of the network is a nonlinear diffusion-convection problem. Existence and uniqueness for such problems for “small” data and short times can be established under general conditions. Key ingredients are coercivity, which will hold as long as z is bounded away from 1, and diffusion dominance, which will also hold as long as z is bounded above.We now present a convergence theorem from [1], which states that the Markov chain XN,M(k) converges uniformly to the solution z of its limiting PDE, as N→∞ and M→∞ in a dependent way. By this we mean that we set M to be a function of N, written MN, such that MN→∞ as N→∞. Then we can treat XN,M as sequences of the single index N, written XN. We apply such changes of notation throughout the rest of the paper wheneverM is treated as a function of N. Define the time step
(9)dtN=dsN2MN
and the total number of time steps KN=⌊T/dtN⌋.Theorem 2.
Almost surely, there exist a sequence{γN}, c0<∞, N0, and M^1<M^2<M^3,…, such that as N→∞, γN→0, and for each N≥N0 and each MN≥M^N,
(10)maxk=0,…,KNn=1,…,N|XN(k,n)MN-z(kdtN,vN(n))|<c0γN.Hence we can approximate the Markov chain by its continuum limit, the limiting PDE solution, and the accuracy of the approximation increases withN.Example 3.
As a concrete example, we now construct the limiting PDE for the 1D 1-step network model in Section2.1. To satisfy the conditions on fN introduced above, we make further assumptions to the network model. We assume that there are functions pr and pl from 𝒟 to ℝ such that
(11)Pr(n)=pr(vN(n)),Pl(n)=pl(vN(n));
and further that
(12)pr(s)=12+cr(s)dsN,pl(s)=12+cl(s)dsN,
where cr and cl are functions from 𝒟 to ℝ. Let c=cl-cr. We call c the convection.
In order to guarantee that the number of messages entering the system from outside over finite time intervals remains finite throughout the limiting process, we set the incoming traffic(13)g(n)=Mgp(vN(n))dtN.
We call gp the incoming traffic function. Assume that cl,cr, and gp are in 𝒞1.
By these assumptions, it follows from (6) that the limiting PDE (8) for the 1D 1-step network is as follows:
(14)z˙=12∂∂s((1-z)(1+3z)∂z∂s)+∂∂s(cz(1-z)2)+gp,
with boundary condition z=0. The detailed derivation for this PDE was presented in [3].This is a nonlinear diffusion-convection PDE. Note that the computations needed to obtain this require tedious but elementary algebraic manipulations. For this purpose, we found it helpful to use the symbolic tools in Matlab. A comparison of this PDE and the simulation of the corresponding network is provide in Section4.1.1.


## 2.3. The Related Literature

The modeling and analysis of stochastic networks is a large field of research and much of the previous contributions share goals with our continuum modeling method.The analysis for establishing our continuum modeling result used Kushner’s ordinary differential equation (ODE) method [6], which is closely related to the line of research called stochastic approximation. This line of research was started by Robbins and Monro [7] and Kiefer and Wolfowitz [8] in the early 1950s and widely used in many areas (see, e.g., [9, 10], for surveys). These results do not study the “large-system” limit in the same sense as our method, and the limits of the system they study are ODEs instead of PDEs. Markov chains modeling’s various systems have also been shown by other endeavors to converge to ODEs [11, 12], abstract Cauchy problems [13], or other stochastic processes [6, 14]. These results use methods different from Kushner’s but share with it the principle idea in weak convergence theory [6, 14, 15].There are a variety of other analysis methods for large systems taking completely different approaches. For example, the well-cited work of Gupta and Kumar [16], followed by many others (e.g., [17, 18]), derives scaling laws of network performance parameters (e.g., throughput); many efforts based on mean field theory [19–22] or on the theory of large deviations [23–25] study the limit of the so-called empirical (or occupancy) measure or distribution. These approaches differ from our work because they do not study the spatiotemporal characteristics of the system.There do exist numerous continuum models in a wide spectrum of areas that formulate spatiotemporal phenomena (e.g., [26–29]), many of which use PDEs. All these works differ from our continuum limit method both by the properties of the system being studied and the analytic approaches. In addition, most of them study distributions of limiting processes that are random, while our limiting functions themselves are deterministic.There is a vast literature on the convergence of a large variety of network models different from ours, to fluid and diffusion limits [30–35]. Unlike our work, this field of research focuses primarily on networks with a fixed number of nodes.There are well-established mathematical tools to solve PDEs, which include analytical methods, such as the method of characteristics, integral transforms [36], and asymptotic methods [37], and numerical methods such as the finite element method [38] and the finite difference method [39]. The continuum model allows us to use these tools to greatly reduce computation time. The limiting PDEs for the networks in this paper can be solved by computer software packages in Matlab or Comsol that use numerical methods.


## 3. Main Results

### 3.1. Continuum Models of Uniform Networks

We introduced the wireless sensor network model in a simple setting in Section2.1. In this subsection, we consider uniform networks in a more general setting where the network nodes have more general transmission ranges and derive their limiting PDEs. Such generalization is necessary for the control of nonuniform networks to be possible (explained in Section 3.3.1). We consider nonuniform networks in Section 3.2.


#### 3.1.1. A More General Network Model

Recall that in Section2.1 we introduced 1-step networks where the sensor nodes communicate (exchange data and interfere) with their immediate neighbors. We now consider L-step networks where the nodes communicate with their communicating neighbors, which can be further away than the immediate ones. To be specific, at each time instant, a transmitter tries to transmit a message to one of its communicating neighbors; a receiver may receive a message from one of its communicating neighbors. Interference also occurs among communicating neighbors: a transmission from a transmitter to a receiver (one of the communicating neighbors of the transmitter) is successful if and only if none of the other communicating neighbors of the receiver is a transmitter.For anL-step network, we call the positive integer L its communication range and assume that it determines the communicating neighbors as follows.In a 1DL-step network of N nodes, communicating neighbors of the node at s∈VN⊂ℝ are the nodes at s±ldsN, where 1≤l≤L.In 2D networks, we consider two types of communicating neighbors. In a 2-DL-step network of N nodes, for a node at s=(s1,s2)∈VN⊂ℝ2, its communicating neighbors are the nodes at
(15)(s1±l1dsN,s2±l2dsN),
where(i)
for Type I networks,0≤l1,l2≤L,l1+l2>0, and l1l2=0;(ii)
for Type II networks,0≤l1,l2≤L and l1+l2>0. We illustrate the two types of definition of communicating neighbors for 2-D 1-step networks in Figure 2.The two types of communicating neighbors of 2D 1-step networks. The nodes pointed by the arrows are the communicating neighbors of the node in the center. The labels on the arrows are probabilities of transmitting to the pointed communicating neighbors.
(a)
(b)We assume the use of directional antennas and power control to accommodate such routing schemes. Here we consider two types of communicating neighbors because they may correspond to two types of routing schemes, and one may be a better model than the other for networks with different design choices. For example, a Type-II network may offer higher rate in propagating information to the destination nodes at the boundaries but at the same time may require more complex directional antennas and power control to implement.Next we derive the limiting PDEs for this more general network model.


#### 3.1.2. Limiting PDEs for Uniform Networks

The network model above can again be written as (1), for which Theorem 2 still holds.We assume that if, at timek, node n is a transmitter, it randomly chooses to transmit a message to its ith communicating neighbor with probability Pi(k,n), where the possible values of i depend on the number of its communicating neighbors. Note that here Pi depends on k, that is, is time variant, which generalizes the case in Section 2.1. Correspondingly, we now assume that
(16)Pi(k,n)=pi(kdtN,vN(n));
that
(17)pi(t,s)=bi(t,s)+ci(t,s)dsN,
where bi and ci are 𝒞1 functions from [0,T]×𝒟 to ℝ. We call pi the direction function. We have assumed above that the probabilities Pi of the direction of transmission are the values of the continuous functions pi at the grid points, respectively. This may correspond to stochastic routing schemes where nodes in close vicinity behave similarly based on some local information that they share or to those with an underlying network-wide directional configuration that are continuous in space, designed to relay messages to destination nodes at known locations.For aJD L-step network, let λ(J,L) be the number of the communicating neighbors of its nodes that are away from the boundaries. We have that
(18)λ(J,L):={2LJ,forType-Inetworks;(1+2L)J-1,forType-IInetworks.We assume that the communicating neighbors of each node are indexed according only to theirrelative locations with respect to the node. For example, if we call the left immediate neighbor of any node its 1st neighbor, then the left immediate neighbor of all nodes must be their 1st neighbor, respectively. That is, for a node at vN(n), if we denote by vN(n,i) the location of its ith communicating neighbor, then vN(n)-vN(n,i) depends on i, but not on n.We present below the limiting PDE in the sense of Theorem2 for an arbitrary J-D L-step network with both Type-I and II communicating neighbors. The PDE is derived in a way similar to that of (14) for the 1-D 1-step network in Section 2, which involves writing down the expression of the corresponding Markov chain (1) and then the difference equation (5), except that we now have to consider transmission to and interference from more neighbors instead of only the two immediate ones, requiring more arduous, but still elementary, algebraic manipulation. We omit the algebraic details here.Let{e1,…,eJ} be the standard basis of ℝJ; that is, ej is the element of ℝJ with the jth entry being 1 and other entries 0. Define
(19)b(j)=∑iλ(J,L)‍((vN(n,i)-vN(n))⊤ej)2bi2,c(j)=∑iλ(J,L)‍(vN(n,i)-vN(n))⊤ejci.
Then the limiting PDE for a J-D L-step network is
(20)z˙=∑j=1J‍(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)∂sj2+∂∂sj(c(j)z(1-z)λ(J,L)))+gp,
with boundary condition z(t,s)=0. This general PDE works for both Type-I and II communicating neighbors, provided that λ(J,L) is calculated with (18) accordingly. We will present some concrete examples of the PDEs and the corresponding network models in Section 4.1.


### 3.2. Continuum Models of Nonuniform Networks

In this subsection we extend the continuum models to nonuniform and mobile networks. First we introduce the transformation function, which is the mapping between the node locations of uniform and nonuniform networks. Then, through the transformation function, we derive the continuum limits of nonuniform and mobile networks with given trajectories and transmissions. We consider the domain𝒟⊂ℝJ and a fixed time interval [0,T].


#### 3.2.1. Location Transformation Function

For networks with the design of uniform node placement, there may be small perturbations to the uniform grid because of imperfect implementation or landscape limitation; some sensor networks may have nodes with moderate mobility. The study of nonuniform networks here is motivated by the need for modeling these networks. Again we assume the use of directional antennas and power control to preserve the neighborhood structure in the nonuniform or mobile networks.Consider a nonuniform and possibly mobile network withN nodes indexed by n=1,…,N over 𝒟. The nodes no longer are located at the grid points VN and possibly change their locations at each time step k.We denote byv~N(k,n) the location of node n of the nonuniform network at time k. Let v~N(k)= [v~N(k,1),…,v~N(k,N)] and V~N=[v~N(0),…,v~N(KN)]. Assume that there exists a smooth transformation functionϕ(t,s):[0,T]×𝒟→𝒟 such that, for each k and n,
(21)v~N(k,n)=ϕ(kdtN,vN(n)),
and, for each to, ϕ(to,·) is bijective. Hence ϕ is the mapping between the nonuniform node locations and uniform grid points.Note that, for mobile networks, by assuming thatϕ(to,·) is bijective for each to, we focus on a subset of all possible node movements, which simplifies the problem. This restricts the mobility of nodes but is still a reasonable model in many practical scenarios, for example, in sensor networks where each node collects environmental data from its designated area and moves in a small neighborhood of, instead of arbitrarily far away from, their original locations.Sinceϕ(to,·) is bijective, its inverse with respect to s exists and we denote it by η:[0,T]×𝒟→𝒟; that is, for each t and s,
(22)η(t,ϕ(t,s))=s.
Throughout the paper we assume fixed nodes on the boundary; that is, ϕ(t,s)=s for s on the boundary of 𝒟.ForgivenN and V~N, a transformation function ϕ can be constructed using some interpolation scheme. Note that ϕ is not unique because of the freedom we have in choosing different schemes. Let ϕj and ηj be the jth components of ϕ and η, respectively, where j=1,…,J. For the rest of the paper, we assume that for i≠j,
(23)∂ϕj∂si=0.
Then equivalently, for i≠j, (∂ηj/∂si)=0. This assumption can be achieved by choosing a proper interpolation scheme, and it simplifies the analysis below.On the other hand, agivenϕ, by (21), specifies a sequence {V~N} of nonuniform node locations indexed by N. We study the continuum limit of a sequence of nonuniform networks associated with such {V~N}; that is, for each N, the N-node nonuniform network has node locations V~N.


#### 3.2.2. Continuum Limits of Mirroring Networks

For anN-node network (uniform or nonuniform), we define its transmission-interference rule to be (i)
the probability that nodem sends a message to node n at time k;(ii)
the fact of whether nodesm and n interfere at time k,form,n=1,…,N and k=0,1,…,KN. The transmission-interference rule specifies how the nodes in a network interact with each other at each time step. At each time step, each node chooses to be a transmitter with a certain probability; if it chooses to be a transmitter, it then chooses one of its communicating neighbors to send a message to. The first component of this definition is determined by the probabilities of the above choices of all the nodes at all the time steps. The second component of this definition is determined by the neighborhood structure of the network at each time step; that is, which nodes are the communicating neighbors of each node (so that they interfere with it) at each time step.For eachN, write XN=[XN(0),…,XN(KN)]. Then we can describe a network during [0,T] entirely by its states XN. Define the network behavior of a network XN to be the combination of its initial state XN(0), transmission-interference rule, and incoming traffic g(n). Two sequences {XN} and {X~N} of networks indexed by the number N of nodes, with different node locations in general, are said to mirror each other if, for each N, XN and X~N have the same network behavior. We state in the following theorem the relationship between the continuum limits of mirroring networks.Theorem 4.
Suppose that a sequence{X~N} of networks has node locations specified by a given transformation function ϕ with inverse η. If {X~N} mirrors a sequence {XN} of uniform networks, then {XN} converges to a function q(t,s) on [0,T]×𝒟 in the sense of Theorem 2 if and only if {X~N} converges to
(24)u(t,s):=q(t,η(t,s)),
in the sense that almost surely there exist a sequence {γN}, c0<∞, N0, and M^1<M^2<M^3,…, such that as N→∞, γN→0, and for each N≥N0 and each MN≥M^N,
(25)maxk=0,…,KNn=1,…,N|X~N(k,n)MN-u(kdtN,v~N(k,n))|<c0γN,
where v~N(k,n) is the location of node n at time k in X~N.Proof.
“⇒”: Since {XN} and {X~N} mirror each other, they would converge to the same continuum limit on a uniform grid. Therefore, by Theorem 2, almost surely, there exist a sequence {γN}, c0<∞, N0, and M^1<M^2<M^3,…, such that as N→∞, γN→0, and for each N≥N0 and each MN≥M^N,
(26)maxk=0,…,KNn=1,…,N|X~N(k,n)MN-q(kdtN,vN(n))|<c0γN.
We note that
(27)q(kdtN,vN(n))=u(kdtN,ϕ(kdtN,vN(n)))=u(kdtN,v~N(k,n)),
where the first equality follows from (22) and (24), and the second from (21). Then (26) is equivalent to (25).
“⇐”: Done analogously in the opposite direction.


#### 3.2.3. Sensitivity of Uniform Continuum Models to Location Perturbation

In networks with nodes not necessarily at, but close to, the uniform grid points, we can useuniform continuum models to approximate nonuniform networks, that is, treat them as uniform while deriving limiting PDEs. Then a certain approximation error arises from ignoring nonuniformity. If we treat such nonuniformities as perturbations to the uniform models, the above theorem enables us to analyze the error sensitivity of these models with respect to such perturbation.Consider a sequence{X~N} of nonuniform networks with node locations specified by the transformation function ϕ with inverse η. Suppose that we ignore the nonuniformity and approximate {X~N} by the continuum limit q of the sequence {XN} of uniform networks that mirrors {X~N}. We now characterize the maximum approximation error
(28)εN:=maxk=0,…,KNn=1,…,N|X~N(k,n)MN-q(kdtN,v~N(k,n))|
by ϕ in the following proposition.Proposition 5.
Almost surely, there exist a sequence{γN}, c0,c1<∞, N0, and M^1<M^2<M^3,…, such that as N→∞, γN→0, and for each N≥N0 and each MN≥M^N,
(29)εN≤c0γN+sup(t,s)|qs(t,s)|sup(t,s)|η(t,s)-s|+c1sup(t,s)(η(t,s)-s)2.Proof.
We have, from the triangle inequality, that(30)εN≤maxk,n(|X~N(k,n)MN-u(kdtN,v~N(k,n))|+|u(kdtN,v~N(k,n))-q(kdtN,v~N(k,n))X~N(k,n)MN|)≤maxk,n|X~N(k,n)MN-u(kdtN,v~N(k,n))|+sup(t,s)∈[0,T]×𝒟|u(t,s)-q(t,s)|,
where u is defined by (24).
By Theorem4, almost surely, there exist a sequence {γN}, c0<∞, N0, and M^1<M^2<M^3,…, such that as N→∞, γN→0, and for each N≥N0 and each MN≥M^N, the first term above is smaller than c0γN.
The second term represents the error caused by location perturbation. By (24) and Taylor’s theorem, there exists c1<∞ such that
(31)u(t,s)-q(t,s)=q(t,η(t,s))-q(t,s)≤qs(t,s)(η(t,s)-s)+c1(η(t,s)-s)2.
Therefore we have that
(32)sup(t,s)|u(t,s)-q(t,s)|≤sup(t,s)|qs(t,s)|sup(t,s)|η(t,s)-s|+c1sup(t,s)(η(t,s)-s)2.
By (30) this completes the proof.This proposition states that, for fixedq and for N and MN sufficiently large, εN is dominated by the supremum location perturbation sup(t,s)|η(t,s)-s|, when it is close to 0. We note that by definition sup(t,s)|η(t,s)-s|=sup(t,s)|ϕ(t,s)-s|. In the case where X~N are uniform; that is, η(t,s)=ϕ(t,s)=s, the last two terms on the right-hand side of (29) vanish.


#### 3.2.4. Limiting PDEs for Nonuniform Networks

Consider a sequence{X~N} of networks with given network behavior and with node locations specified by a given transformation function ϕ with inverse η. If a sequence {XN} of uniform networks mirrors {X~N}, from this given network behavior, we can find the continuum limit q of {XN} by constructing its limiting PDE as in Section 3.1.2. Suppose that this PDE has the form
(33)q˙(t,s)=Q(s,q(t,s),∂q∂sj(t,s),∂2q∂sj2(t,s)),
with initial condition q(0,s)=q0(s), where j=1,…,J, t∈[0,T], and s=(s1,…,sJ)∈𝒟. By Theorem 4, we have that the continuum limit u(t,s) of {X~N} satisfies (24).However, in general, we can only solve (33) numerically instead of analytically. In fact, all the limiting PDEs in this paper are solved by software using numerical methods. In this case we cannot find the closed-form expression of u from q using (24). Instead, we derive a PDE that u satisfies so that we can solve it numerically.Suppose thatu(t,s) solves the PDE
(34)u˙(t,s)=Γ(s,u(t,s),∂u∂sj(t,s),∂2u∂sj2(t,s)),
with initial condition u(0,s)=u0(s), where j=1,…,J and (t,s)∈[0,T]×𝒟. We now find Γ from the known PDE (33).By (23), (24), and the chain rule,
(35)∂u∂sj(t,s)=∂ηj∂sj(t,s)∂q∂sj(t,η(t,s)).
By (23), the product rule, and the chain rule,
(36)∂2u∂sj2(t,s)=∂2ηj∂sj2(t,s)∂q∂sj(t,η(t,s))+(∂ηj∂sj(t,s))2∂2q∂sj2(t,η(t,s)).
Note that, without assumption (23), the expression of the derivatives above would be much more complex. Then by (24), (33), and (34) we have
(37)Γ(s,u(t,s),∂u∂sj(t,s),∂2u∂sj2(t,s))=Q((∂2ηj/∂sj2)(t,s)(∂u/∂sj)(t,s)((∂ηj/∂sj)(t,s))3η(t,s),u(t,s),(∂u/∂sj)(t,s)(∂ηj/∂sj)(t,s),(∂2u/∂sj2)(t,s)((∂ηj/∂sj)(t,s))2,-(∂2ηj/∂sj2)(t,s)(∂u/∂sj)(t,s)((∂ηj/∂sj)(t,s))3),
where u0(s)=q0(η(0,s)). Hence we find the limiting PDE (34) of {X~N}.We present a concrete numerical example of the nonuniform network and its continuum limit later in Section4.2.


### 3.3. Control of Nonuniform Networks

The global characteristic of the network is determined by the transmission-interference rule defined in Section3.2.2 and is described by its limiting PDE. The transmission-interference rule depends entirely on the transmission range L and the probabilities Pi, which in turn by (16) depends on the direction function pi. On the other hand, L and pi also determine the limiting PDE of a sequence of networks. Therefore we can control the transmission-interference rule to obtain the desired limiting PDE, and hence the desired global characteristic of the network, by changing L and pi.For uniform networks, this procedure is straightforward becauseL and pi relate directly to the form and coefficients of the limiting PDE. For example, for the 1D 1-step network in Section 2.2 with limiting PDE (14), increasing the convection c results in a greater bias of the PDE solution to the left side of the domain. (A numerical example of this network is provided in Section 4.1.1.)We now study this kind of control for nonuniform and possibly mobile networks. For such networks, we have to take into account the varying node locations in order to still achieve certain global characteristics. The goal is to develop a control method so that the continuum limit is invariant under node locations and mobility, that is, remains the same as a reference, which is the continuum limit of the sequence of corresponding uniform networks with a certain transmission-interference rule. We then say the sequence has a location-invariant continuum limit.We illustrate this idea in Figure3. The plus signs in both figures represent the queues of a certain uniform network at a certain time. The solid lines in both figures represent the continuum limit (the limiting PDE solution) of the same uniform network at the same time. Thus they resemble each other. On the left, the diamonds represent the queues of a nonuniform network with the same transmission-interference rule as the uniform network, but no longer resembling the continuum limit because of the changes in node locations. On the right, the circles represent the queues of a second nonuniform network with the same node locations as the first nonuniform network, but under some control over its transmission-interference rule, therefore resembling the continuum limit of the uniform network. In other words, location invariance in the second nonuniform network has been achieved by network control. Apparently, for this particular network, such a control scheme has to be able to direct more (and the right amount of) data traffic to the right-hand side. In what follows, we describe how this can be done by properly increasing the probabilities of the nodes transmitting to the right through the use of the limiting PDEs.An illustration of control of nonuniform networks. On thex-axis, the × marks are the uniform grid, and the Δ marks are the nonuniform node locations.
(a)
(b)Throughout the paper we assume no control over node location or motion.


#### 3.3.1. Transmission-Interference Rule for Location Invariance

Consider a sequence{X~N} of nonuniform networks whose node locations are specified by a given transformation function ϕ with inverse η and a sequence {X^N} of uniform networks with given transmission-interference rule and continuum limit u. We want to control the transmission-interference rule of {X~N} so that it also converges to u, that is, obtains the location-invariant continuum limit.Again we do not assume a known closed-form expression ofu. Instead, assume that u(t,s) solves (34), except that Γ is now given.Define(38)q(t,s)=u(t,ϕ(t,s)).Suppose that a sequence{XN} of uniform networks has continuum limit q(t,s). By Theorem 4, for {X~N} to converge to this desired u(t,s), it suffices that {X~N} mirrors {XN}. Therefore all we have to do is to specify the transmission-interference rule of {XN} to {X~N}. Next we find this transmission-interference rule.Suppose thatq(t,s) solves (33), except that Q is now unknown. Again using the product rule and the chain rule as we did in Section 3.2.4, by (33), (34), and (38), we have that
(39)Q(s,q(t,s),∂q∂sj(t,s),∂2q∂sj2(t,s))=Γ((∂2ηj/∂sj2)(t,s)(∂u/∂sj)(t,s)((∂ηj/∂sj)(t,s))3ϕ(t,s),q(t,s),(∂q/∂sj)(t,s)(∂ϕj/∂sj)(t,s),(∂2q/∂sj2)(t,s)((∂ϕj/∂sj)(t,s))2-(∂2ϕj/∂sj2)(t,s)(∂q/∂sj)(t,s)((∂ϕj/∂sj)(t,s))3),
and q0(s)=u0(ϕ(0,s)), where j=1,…,J.Sinceq(t,s) is the continuum limit of a sequence of uniform networks, (33) must be a case of (20), the general limiting PDE. Therefore we can replace the left-hand side of (39) by the right-hand side of (20) and get
(40)∑j=1J‍(b(j)(t,s)∂∂sj(∂z∂sj(1+(λ(J,L)+1)z(t,s))×(1-z(t,s))(λ(J,L)-1)∂z∂sj(t,s))+2(1-z(t,s))(λ(J,L)-1)∂z∂sj(t,s)∂b(j)∂sj(t,s)+z(t,s)(1-z(t,s))λ(J,L)∂2b(j)∂sj2(t,s)+∂∂sj(c(j)(t,s)z(t,s)(1-z(t,s))λ(J,L)))+gp(t,s).=Γ(ϕ(t,s),q(t,s),(∂q/∂sj)(t,s)(∂ϕj/∂sj)(t,s),(∂2q/∂sj2)(t,s)((∂ϕj/∂sj)(t,s))2-(∂2ϕj/∂sj2)(t,s)(∂q/∂sj)(t,s)((∂ϕj/∂sj)(t,s))3).
We call this the comparison equation. If we can solve it for L, pl, and gp, our goal is accomplished because they determine the network behavior, which includes the transmission-interference rule, for each N-node uniform network in the mirroring sequence {XN}. If we assign the same transmission-interference rule to {X~N}, then it has the location-invariant continuum limit u(t,s).We note a constraint for (40): by (16), for each i, pi has to be sufficiently small such that, for each k and n,
(41)Pi(k,n)∈[0,1],∑i‍Pi(k,n)∈[0,1].
In turn by (17), bi and ci have to be sufficiently small for (41) to hold. By further observing (18) and (19), it follows that the transmission range L has to be sufficiently large. For this reason, it is necessary to generalize from 1-step to L-step transmission range, as we did in Section 3.1. Note that with this constraint, (40) is still underdetermined. Such freedom gives us a class of transmission-interference rules to assign to {X~N} instead of just one.One way to solve (40) is this. Suppose that we have chosen L sufficiently large. Since (34) is now given, we know the numerical form of u and in turn that of q by (38). For fixed to, we put q(to,s) in (40). For each j, if we fix b(j)(to,s), then we can solve (40), which is now an ordinary differential equation (ODE), for c(j)(to,s). Similarly, fixing c(j)(to,s) makes (40) an ODE that we can solve for b(j)(to,s). Then by (19) we can further choose bi and ci and further determine pi by (17). Thus we have found Pi by (16), which together with L determines the transmission-interference rule.


#### 3.3.2. Distributed Control Using Local Information

The control method presented above is centralized in the sense that it requires knowledge of the transformation functionϕ over 𝒟. This assumes that each node knows the location of all other nodes. However, this is generally not the case in practice, especially for networks without a central control unit. In this subsection we present a distributed version of our control method, where only the locations of nearby nodes are needed for each node to determine its transmission-interference rule. We can do this because all the information needed to solve the comparison equation (40) can be approximated locally at each node.The derivatives ofϕ in (40) can be approximated from the locations of neighboring nodes using a certain finite difference method. For example, in the 1-D case, we can use the following approximation:
(42)∂ϕ∂s(t,s)≈ϕ(kdtN,vN(n+1))-ϕ(kdtN,vN(n-1))2dsN=v~N(k,n+1)-v~N(k,n-1)2dsN,wheret=kdtN and s∈[vN(n-1),vN(n+1)). Note that we can also use the location information of further neighbors to get a more accurate approximation of ∂ϕ/∂s. The trade-off between locality and accuracy can be flexibly adjusted.The ODE forb(j) or c(j) can also be solved based on local information using numerical procedures such as Euler’s method [40].We present two concrete examples of network control in 1D and 2D case, in Sections4.3.1 and 4.3.2, respectively.


## 3.1. Continuum Models of Uniform Networks

We introduced the wireless sensor network model in a simple setting in Section2.1. In this subsection, we consider uniform networks in a more general setting where the network nodes have more general transmission ranges and derive their limiting PDEs. Such generalization is necessary for the control of nonuniform networks to be possible (explained in Section 3.3.1). We consider nonuniform networks in Section 3.2.


### 3.1.1. A More General Network Model

Recall that in Section2.1 we introduced 1-step networks where the sensor nodes communicate (exchange data and interfere) with their immediate neighbors. We now consider L-step networks where the nodes communicate with their communicating neighbors, which can be further away than the immediate ones. To be specific, at each time instant, a transmitter tries to transmit a message to one of its communicating neighbors; a receiver may receive a message from one of its communicating neighbors. Interference also occurs among communicating neighbors: a transmission from a transmitter to a receiver (one of the communicating neighbors of the transmitter) is successful if and only if none of the other communicating neighbors of the receiver is a transmitter.For anL-step network, we call the positive integer L its communication range and assume that it determines the communicating neighbors as follows.In a 1DL-step network of N nodes, communicating neighbors of the node at s∈VN⊂ℝ are the nodes at s±ldsN, where 1≤l≤L.In 2D networks, we consider two types of communicating neighbors. In a 2-DL-step network of N nodes, for a node at s=(s1,s2)∈VN⊂ℝ2, its communicating neighbors are the nodes at
(15)(s1±l1dsN,s2±l2dsN),
where(i)
for Type I networks,0≤l1,l2≤L,l1+l2>0, and l1l2=0;(ii)
for Type II networks,0≤l1,l2≤L and l1+l2>0. We illustrate the two types of definition of communicating neighbors for 2-D 1-step networks in Figure 2.The two types of communicating neighbors of 2D 1-step networks. The nodes pointed by the arrows are the communicating neighbors of the node in the center. The labels on the arrows are probabilities of transmitting to the pointed communicating neighbors.
(a)
(b)We assume the use of directional antennas and power control to accommodate such routing schemes. Here we consider two types of communicating neighbors because they may correspond to two types of routing schemes, and one may be a better model than the other for networks with different design choices. For example, a Type-II network may offer higher rate in propagating information to the destination nodes at the boundaries but at the same time may require more complex directional antennas and power control to implement.Next we derive the limiting PDEs for this more general network model.


### 3.1.2. Limiting PDEs for Uniform Networks

The network model above can again be written as (1), for which Theorem 2 still holds.We assume that if, at timek, node n is a transmitter, it randomly chooses to transmit a message to its ith communicating neighbor with probability Pi(k,n), where the possible values of i depend on the number of its communicating neighbors. Note that here Pi depends on k, that is, is time variant, which generalizes the case in Section 2.1. Correspondingly, we now assume that
(16)Pi(k,n)=pi(kdtN,vN(n));
that
(17)pi(t,s)=bi(t,s)+ci(t,s)dsN,
where bi and ci are 𝒞1 functions from [0,T]×𝒟 to ℝ. We call pi the direction function. We have assumed above that the probabilities Pi of the direction of transmission are the values of the continuous functions pi at the grid points, respectively. This may correspond to stochastic routing schemes where nodes in close vicinity behave similarly based on some local information that they share or to those with an underlying network-wide directional configuration that are continuous in space, designed to relay messages to destination nodes at known locations.For aJD L-step network, let λ(J,L) be the number of the communicating neighbors of its nodes that are away from the boundaries. We have that
(18)λ(J,L):={2LJ,forType-Inetworks;(1+2L)J-1,forType-IInetworks.We assume that the communicating neighbors of each node are indexed according only to theirrelative locations with respect to the node. For example, if we call the left immediate neighbor of any node its 1st neighbor, then the left immediate neighbor of all nodes must be their 1st neighbor, respectively. That is, for a node at vN(n), if we denote by vN(n,i) the location of its ith communicating neighbor, then vN(n)-vN(n,i) depends on i, but not on n.We present below the limiting PDE in the sense of Theorem2 for an arbitrary J-D L-step network with both Type-I and II communicating neighbors. The PDE is derived in a way similar to that of (14) for the 1-D 1-step network in Section 2, which involves writing down the expression of the corresponding Markov chain (1) and then the difference equation (5), except that we now have to consider transmission to and interference from more neighbors instead of only the two immediate ones, requiring more arduous, but still elementary, algebraic manipulation. We omit the algebraic details here.Let{e1,…,eJ} be the standard basis of ℝJ; that is, ej is the element of ℝJ with the jth entry being 1 and other entries 0. Define
(19)b(j)=∑iλ(J,L)‍((vN(n,i)-vN(n))⊤ej)2bi2,c(j)=∑iλ(J,L)‍(vN(n,i)-vN(n))⊤ejci.
Then the limiting PDE for a J-D L-step network is
(20)z˙=∑j=1J‍(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)∂sj2+∂∂sj(c(j)z(1-z)λ(J,L)))+gp,
with boundary condition z(t,s)=0. This general PDE works for both Type-I and II communicating neighbors, provided that λ(J,L) is calculated with (18) accordingly. We will present some concrete examples of the PDEs and the corresponding network models in Section 4.1.


## 3.1.1. A More General Network Model

Recall that in Section2.1 we introduced 1-step networks where the sensor nodes communicate (exchange data and interfere) with their immediate neighbors. We now consider L-step networks where the nodes communicate with their communicating neighbors, which can be further away than the immediate ones. To be specific, at each time instant, a transmitter tries to transmit a message to one of its communicating neighbors; a receiver may receive a message from one of its communicating neighbors. Interference also occurs among communicating neighbors: a transmission from a transmitter to a receiver (one of the communicating neighbors of the transmitter) is successful if and only if none of the other communicating neighbors of the receiver is a transmitter.For anL-step network, we call the positive integer L its communication range and assume that it determines the communicating neighbors as follows.In a 1DL-step network of N nodes, communicating neighbors of the node at s∈VN⊂ℝ are the nodes at s±ldsN, where 1≤l≤L.In 2D networks, we consider two types of communicating neighbors. In a 2-DL-step network of N nodes, for a node at s=(s1,s2)∈VN⊂ℝ2, its communicating neighbors are the nodes at
(15)(s1±l1dsN,s2±l2dsN),
where(i)
for Type I networks,0≤l1,l2≤L,l1+l2>0, and l1l2=0;(ii)
for Type II networks,0≤l1,l2≤L and l1+l2>0. We illustrate the two types of definition of communicating neighbors for 2-D 1-step networks in Figure 2.The two types of communicating neighbors of 2D 1-step networks. The nodes pointed by the arrows are the communicating neighbors of the node in the center. The labels on the arrows are probabilities of transmitting to the pointed communicating neighbors.
(a)
(b)We assume the use of directional antennas and power control to accommodate such routing schemes. Here we consider two types of communicating neighbors because they may correspond to two types of routing schemes, and one may be a better model than the other for networks with different design choices. For example, a Type-II network may offer higher rate in propagating information to the destination nodes at the boundaries but at the same time may require more complex directional antennas and power control to implement.Next we derive the limiting PDEs for this more general network model.


## 3.1.2. Limiting PDEs for Uniform Networks

The network model above can again be written as (1), for which Theorem 2 still holds.We assume that if, at timek, node n is a transmitter, it randomly chooses to transmit a message to its ith communicating neighbor with probability Pi(k,n), where the possible values of i depend on the number of its communicating neighbors. Note that here Pi depends on k, that is, is time variant, which generalizes the case in Section 2.1. Correspondingly, we now assume that
(16)Pi(k,n)=pi(kdtN,vN(n));
that
(17)pi(t,s)=bi(t,s)+ci(t,s)dsN,
where bi and ci are 𝒞1 functions from [0,T]×𝒟 to ℝ. We call pi the direction function. We have assumed above that the probabilities Pi of the direction of transmission are the values of the continuous functions pi at the grid points, respectively. This may correspond to stochastic routing schemes where nodes in close vicinity behave similarly based on some local information that they share or to those with an underlying network-wide directional configuration that are continuous in space, designed to relay messages to destination nodes at known locations.For aJD L-step network, let λ(J,L) be the number of the communicating neighbors of its nodes that are away from the boundaries. We have that
(18)λ(J,L):={2LJ,forType-Inetworks;(1+2L)J-1,forType-IInetworks.We assume that the communicating neighbors of each node are indexed according only to theirrelative locations with respect to the node. For example, if we call the left immediate neighbor of any node its 1st neighbor, then the left immediate neighbor of all nodes must be their 1st neighbor, respectively. That is, for a node at vN(n), if we denote by vN(n,i) the location of its ith communicating neighbor, then vN(n)-vN(n,i) depends on i, but not on n.We present below the limiting PDE in the sense of Theorem2 for an arbitrary J-D L-step network with both Type-I and II communicating neighbors. The PDE is derived in a way similar to that of (14) for the 1-D 1-step network in Section 2, which involves writing down the expression of the corresponding Markov chain (1) and then the difference equation (5), except that we now have to consider transmission to and interference from more neighbors instead of only the two immediate ones, requiring more arduous, but still elementary, algebraic manipulation. We omit the algebraic details here.Let{e1,…,eJ} be the standard basis of ℝJ; that is, ej is the element of ℝJ with the jth entry being 1 and other entries 0. Define
(19)b(j)=∑iλ(J,L)‍((vN(n,i)-vN(n))⊤ej)2bi2,c(j)=∑iλ(J,L)‍(vN(n,i)-vN(n))⊤ejci.
Then the limiting PDE for a J-D L-step network is
(20)z˙=∑j=1J‍(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)∂sj2+∂∂sj(c(j)z(1-z)λ(J,L)))+gp,
with boundary condition z(t,s)=0. This general PDE works for both Type-I and II communicating neighbors, provided that λ(J,L) is calculated with (18) accordingly. We will present some concrete examples of the PDEs and the corresponding network models in Section 4.1.


## 3.2. Continuum Models of Nonuniform Networks

In this subsection we extend the continuum models to nonuniform and mobile networks. First we introduce the transformation function, which is the mapping between the node locations of uniform and nonuniform networks. Then, through the transformation function, we derive the continuum limits of nonuniform and mobile networks with given trajectories and transmissions. We consider the domain𝒟⊂ℝJ and a fixed time interval [0,T].


### 3.2.1. Location Transformation Function

For networks with the design of uniform node placement, there may be small perturbations to the uniform grid because of imperfect implementation or landscape limitation; some sensor networks may have nodes with moderate mobility. The study of nonuniform networks here is motivated by the need for modeling these networks. Again we assume the use of directional antennas and power control to preserve the neighborhood structure in the nonuniform or mobile networks.Consider a nonuniform and possibly mobile network withN nodes indexed by n=1,…,N over 𝒟. The nodes no longer are located at the grid points VN and possibly change their locations at each time step k.We denote byv~N(k,n) the location of node n of the nonuniform network at time k. Let v~N(k)= [v~N(k,1),…,v~N(k,N)] and V~N=[v~N(0),…,v~N(KN)]. Assume that there exists a smooth transformation functionϕ(t,s):[0,T]×𝒟→𝒟 such that, for each k and n,
(21)v~N(k,n)=ϕ(kdtN,vN(n)),
and, for each to, ϕ(to,·) is bijective. Hence ϕ is the mapping between the nonuniform node locations and uniform grid points.Note that, for mobile networks, by assuming thatϕ(to,·) is bijective for each to, we focus on a subset of all possible node movements, which simplifies the problem. This restricts the mobility of nodes but is still a reasonable model in many practical scenarios, for example, in sensor networks where each node collects environmental data from its designated area and moves in a small neighborhood of, instead of arbitrarily far away from, their original locations.Sinceϕ(to,·) is bijective, its inverse with respect to s exists and we denote it by η:[0,T]×𝒟→𝒟; that is, for each t and s,
(22)η(t,ϕ(t,s))=s.
Throughout the paper we assume fixed nodes on the boundary; that is, ϕ(t,s)=s for s on the boundary of 𝒟.ForgivenN and V~N, a transformation function ϕ can be constructed using some interpolation scheme. Note that ϕ is not unique because of the freedom we have in choosing different schemes. Let ϕj and ηj be the jth components of ϕ and η, respectively, where j=1,…,J. For the rest of the paper, we assume that for i≠j,
(23)∂ϕj∂si=0.
Then equivalently, for i≠j, (∂ηj/∂si)=0. This assumption can be achieved by choosing a proper interpolation scheme, and it simplifies the analysis below.On the other hand, agivenϕ, by (21), specifies a sequence {V~N} of nonuniform node locations indexed by N. We study the continuum limit of a sequence of nonuniform networks associated with such {V~N}; that is, for each N, the N-node nonuniform network has node locations V~N.


### 3.2.2. Continuum Limits of Mirroring Networks

For anN-node network (uniform or nonuniform), we define its transmission-interference rule to be (i)
the probability that nodem sends a message to node n at time k;(ii)
the fact of whether nodesm and n interfere at time k,form,n=1,…,N and k=0,1,…,KN. The transmission-interference rule specifies how the nodes in a network interact with each other at each time step. At each time step, each node chooses to be a transmitter with a certain probability; if it chooses to be a transmitter, it then chooses one of its communicating neighbors to send a message to. The first component of this definition is determined by the probabilities of the above choices of all the nodes at all the time steps. The second component of this definition is determined by the neighborhood structure of the network at each time step; that is, which nodes are the communicating neighbors of each node (so that they interfere with it) at each time step.For eachN, write XN=[XN(0),…,XN(KN)]. Then we can describe a network during [0,T] entirely by its states XN. Define the network behavior of a network XN to be the combination of its initial state XN(0), transmission-interference rule, and incoming traffic g(n). Two sequences {XN} and {X~N} of networks indexed by the number N of nodes, with different node locations in general, are said to mirror each other if, for each N, XN and X~N have the same network behavior. We state in the following theorem the relationship between the continuum limits of mirroring networks.Theorem 4.
Suppose that a sequence{X~N} of networks has node locations specified by a given transformation function ϕ with inverse η. If {X~N} mirrors a sequence {XN} of uniform networks, then {XN} converges to a function q(t,s) on [0,T]×𝒟 in the sense of Theorem 2 if and only if {X~N} converges to
(24)u(t,s):=q(t,η(t,s)),
in the sense that almost surely there exist a sequence {γN}, c0<∞, N0, and M^1<M^2<M^3,…, such that as N→∞, γN→0, and for each N≥N0 and each MN≥M^N,
(25)maxk=0,…,KNn=1,…,N|X~N(k,n)MN-u(kdtN,v~N(k,n))|<c0γN,
where v~N(k,n) is the location of node n at time k in X~N.Proof.
“⇒”: Since {XN} and {X~N} mirror each other, they would converge to the same continuum limit on a uniform grid. Therefore, by Theorem 2, almost surely, there exist a sequence {γN}, c0<∞, N0, and M^1<M^2<M^3,…, such that as N→∞, γN→0, and for each N≥N0 and each MN≥M^N,
(26)maxk=0,…,KNn=1,…,N|X~N(k,n)MN-q(kdtN,vN(n))|<c0γN.
We note that
(27)q(kdtN,vN(n))=u(kdtN,ϕ(kdtN,vN(n)))=u(kdtN,v~N(k,n)),
where the first equality follows from (22) and (24), and the second from (21). Then (26) is equivalent to (25).
“⇐”: Done analogously in the opposite direction.


### 3.2.3. Sensitivity of Uniform Continuum Models to Location Perturbation

In networks with nodes not necessarily at, but close to, the uniform grid points, we can useuniform continuum models to approximate nonuniform networks, that is, treat them as uniform while deriving limiting PDEs. Then a certain approximation error arises from ignoring nonuniformity. If we treat such nonuniformities as perturbations to the uniform models, the above theorem enables us to analyze the error sensitivity of these models with respect to such perturbation.Consider a sequence{X~N} of nonuniform networks with node locations specified by the transformation function ϕ with inverse η. Suppose that we ignore the nonuniformity and approximate {X~N} by the continuum limit q of the sequence {XN} of uniform networks that mirrors {X~N}. We now characterize the maximum approximation error
(28)εN:=maxk=0,…,KNn=1,…,N|X~N(k,n)MN-q(kdtN,v~N(k,n))|
by ϕ in the following proposition.Proposition 5.
Almost surely, there exist a sequence{γN}, c0,c1<∞, N0, and M^1<M^2<M^3,…, such that as N→∞, γN→0, and for each N≥N0 and each MN≥M^N,
(29)εN≤c0γN+sup(t,s)|qs(t,s)|sup(t,s)|η(t,s)-s|+c1sup(t,s)(η(t,s)-s)2.Proof.
We have, from the triangle inequality, that(30)εN≤maxk,n(|X~N(k,n)MN-u(kdtN,v~N(k,n))|+|u(kdtN,v~N(k,n))-q(kdtN,v~N(k,n))X~N(k,n)MN|)≤maxk,n|X~N(k,n)MN-u(kdtN,v~N(k,n))|+sup(t,s)∈[0,T]×𝒟|u(t,s)-q(t,s)|,
where u is defined by (24).
By Theorem4, almost surely, there exist a sequence {γN}, c0<∞, N0, and M^1<M^2<M^3,…, such that as N→∞, γN→0, and for each N≥N0 and each MN≥M^N, the first term above is smaller than c0γN.
The second term represents the error caused by location perturbation. By (24) and Taylor’s theorem, there exists c1<∞ such that
(31)u(t,s)-q(t,s)=q(t,η(t,s))-q(t,s)≤qs(t,s)(η(t,s)-s)+c1(η(t,s)-s)2.
Therefore we have that
(32)sup(t,s)|u(t,s)-q(t,s)|≤sup(t,s)|qs(t,s)|sup(t,s)|η(t,s)-s|+c1sup(t,s)(η(t,s)-s)2.
By (30) this completes the proof.This proposition states that, for fixedq and for N and MN sufficiently large, εN is dominated by the supremum location perturbation sup(t,s)|η(t,s)-s|, when it is close to 0. We note that by definition sup(t,s)|η(t,s)-s|=sup(t,s)|ϕ(t,s)-s|. In the case where X~N are uniform; that is, η(t,s)=ϕ(t,s)=s, the last two terms on the right-hand side of (29) vanish.


### 3.2.4. Limiting PDEs for Nonuniform Networks

Consider a sequence{X~N} of networks with given network behavior and with node locations specified by a given transformation function ϕ with inverse η. If a sequence {XN} of uniform networks mirrors {X~N}, from this given network behavior, we can find the continuum limit q of {XN} by constructing its limiting PDE as in Section 3.1.2. Suppose that this PDE has the form
(33)q˙(t,s)=Q(s,q(t,s),∂q∂sj(t,s),∂2q∂sj2(t,s)),
with initial condition q(0,s)=q0(s), where j=1,…,J, t∈[0,T], and s=(s1,…,sJ)∈𝒟. By Theorem 4, we have that the continuum limit u(t,s) of {X~N} satisfies (24).However, in general, we can only solve (33) numerically instead of analytically. In fact, all the limiting PDEs in this paper are solved by software using numerical methods. In this case we cannot find the closed-form expression of u from q using (24). Instead, we derive a PDE that u satisfies so that we can solve it numerically.Suppose thatu(t,s) solves the PDE
(34)u˙(t,s)=Γ(s,u(t,s),∂u∂sj(t,s),∂2u∂sj2(t,s)),
with initial condition u(0,s)=u0(s), where j=1,…,J and (t,s)∈[0,T]×𝒟. We now find Γ from the known PDE (33).By (23), (24), and the chain rule,
(35)∂u∂sj(t,s)=∂ηj∂sj(t,s)∂q∂sj(t,η(t,s)).
By (23), the product rule, and the chain rule,
(36)∂2u∂sj2(t,s)=∂2ηj∂sj2(t,s)∂q∂sj(t,η(t,s))+(∂ηj∂sj(t,s))2∂2q∂sj2(t,η(t,s)).
Note that, without assumption (23), the expression of the derivatives above would be much more complex. Then by (24), (33), and (34) we have
(37)Γ(s,u(t,s),∂u∂sj(t,s),∂2u∂sj2(t,s))=Q((∂2ηj/∂sj2)(t,s)(∂u/∂sj)(t,s)((∂ηj/∂sj)(t,s))3η(t,s),u(t,s),(∂u/∂sj)(t,s)(∂ηj/∂sj)(t,s),(∂2u/∂sj2)(t,s)((∂ηj/∂sj)(t,s))2,-(∂2ηj/∂sj2)(t,s)(∂u/∂sj)(t,s)((∂ηj/∂sj)(t,s))3),
where u0(s)=q0(η(0,s)). Hence we find the limiting PDE (34) of {X~N}.We present a concrete numerical example of the nonuniform network and its continuum limit later in Section4.2.


## 3.2.1. Location Transformation Function

For networks with the design of uniform node placement, there may be small perturbations to the uniform grid because of imperfect implementation or landscape limitation; some sensor networks may have nodes with moderate mobility. The study of nonuniform networks here is motivated by the need for modeling these networks. Again we assume the use of directional antennas and power control to preserve the neighborhood structure in the nonuniform or mobile networks.Consider a nonuniform and possibly mobile network withN nodes indexed by n=1,…,N over 𝒟. The nodes no longer are located at the grid points VN and possibly change their locations at each time step k.We denote byv~N(k,n) the location of node n of the nonuniform network at time k. Let v~N(k)= [v~N(k,1),…,v~N(k,N)] and V~N=[v~N(0),…,v~N(KN)]. Assume that there exists a smooth transformation functionϕ(t,s):[0,T]×𝒟→𝒟 such that, for each k and n,
(21)v~N(k,n)=ϕ(kdtN,vN(n)),
and, for each to, ϕ(to,·) is bijective. Hence ϕ is the mapping between the nonuniform node locations and uniform grid points.Note that, for mobile networks, by assuming thatϕ(to,·) is bijective for each to, we focus on a subset of all possible node movements, which simplifies the problem. This restricts the mobility of nodes but is still a reasonable model in many practical scenarios, for example, in sensor networks where each node collects environmental data from its designated area and moves in a small neighborhood of, instead of arbitrarily far away from, their original locations.Sinceϕ(to,·) is bijective, its inverse with respect to s exists and we denote it by η:[0,T]×𝒟→𝒟; that is, for each t and s,
(22)η(t,ϕ(t,s))=s.
Throughout the paper we assume fixed nodes on the boundary; that is, ϕ(t,s)=s for s on the boundary of 𝒟.ForgivenN and V~N, a transformation function ϕ can be constructed using some interpolation scheme. Note that ϕ is not unique because of the freedom we have in choosing different schemes. Let ϕj and ηj be the jth components of ϕ and η, respectively, where j=1,…,J. For the rest of the paper, we assume that for i≠j,
(23)∂ϕj∂si=0.
Then equivalently, for i≠j, (∂ηj/∂si)=0. This assumption can be achieved by choosing a proper interpolation scheme, and it simplifies the analysis below.On the other hand, agivenϕ, by (21), specifies a sequence {V~N} of nonuniform node locations indexed by N. We study the continuum limit of a sequence of nonuniform networks associated with such {V~N}; that is, for each N, the N-node nonuniform network has node locations V~N.


## 3.2.2. Continuum Limits of Mirroring Networks

For anN-node network (uniform or nonuniform), we define its transmission-interference rule to be (i)
the probability that nodem sends a message to node n at time k;(ii)
the fact of whether nodesm and n interfere at time k,form,n=1,…,N and k=0,1,…,KN. The transmission-interference rule specifies how the nodes in a network interact with each other at each time step. At each time step, each node chooses to be a transmitter with a certain probability; if it chooses to be a transmitter, it then chooses one of its communicating neighbors to send a message to. The first component of this definition is determined by the probabilities of the above choices of all the nodes at all the time steps. The second component of this definition is determined by the neighborhood structure of the network at each time step; that is, which nodes are the communicating neighbors of each node (so that they interfere with it) at each time step.For eachN, write XN=[XN(0),…,XN(KN)]. Then we can describe a network during [0,T] entirely by its states XN. Define the network behavior of a network XN to be the combination of its initial state XN(0), transmission-interference rule, and incoming traffic g(n). Two sequences {XN} and {X~N} of networks indexed by the number N of nodes, with different node locations in general, are said to mirror each other if, for each N, XN and X~N have the same network behavior. We state in the following theorem the relationship between the continuum limits of mirroring networks.Theorem 4.
Suppose that a sequence{X~N} of networks has node locations specified by a given transformation function ϕ with inverse η. If {X~N} mirrors a sequence {XN} of uniform networks, then {XN} converges to a function q(t,s) on [0,T]×𝒟 in the sense of Theorem 2 if and only if {X~N} converges to
(24)u(t,s):=q(t,η(t,s)),
in the sense that almost surely there exist a sequence {γN}, c0<∞, N0, and M^1<M^2<M^3,…, such that as N→∞, γN→0, and for each N≥N0 and each MN≥M^N,
(25)maxk=0,…,KNn=1,…,N|X~N(k,n)MN-u(kdtN,v~N(k,n))|<c0γN,
where v~N(k,n) is the location of node n at time k in X~N.Proof.
“⇒”: Since {XN} and {X~N} mirror each other, they would converge to the same continuum limit on a uniform grid. Therefore, by Theorem 2, almost surely, there exist a sequence {γN}, c0<∞, N0, and M^1<M^2<M^3,…, such that as N→∞, γN→0, and for each N≥N0 and each MN≥M^N,
(26)maxk=0,…,KNn=1,…,N|X~N(k,n)MN-q(kdtN,vN(n))|<c0γN.
We note that
(27)q(kdtN,vN(n))=u(kdtN,ϕ(kdtN,vN(n)))=u(kdtN,v~N(k,n)),
where the first equality follows from (22) and (24), and the second from (21). Then (26) is equivalent to (25).
“⇐”: Done analogously in the opposite direction.


## 3.2.3. Sensitivity of Uniform Continuum Models to Location Perturbation

In networks with nodes not necessarily at, but close to, the uniform grid points, we can useuniform continuum models to approximate nonuniform networks, that is, treat them as uniform while deriving limiting PDEs. Then a certain approximation error arises from ignoring nonuniformity. If we treat such nonuniformities as perturbations to the uniform models, the above theorem enables us to analyze the error sensitivity of these models with respect to such perturbation.Consider a sequence{X~N} of nonuniform networks with node locations specified by the transformation function ϕ with inverse η. Suppose that we ignore the nonuniformity and approximate {X~N} by the continuum limit q of the sequence {XN} of uniform networks that mirrors {X~N}. We now characterize the maximum approximation error
(28)εN:=maxk=0,…,KNn=1,…,N|X~N(k,n)MN-q(kdtN,v~N(k,n))|
by ϕ in the following proposition.Proposition 5.
Almost surely, there exist a sequence{γN}, c0,c1<∞, N0, and M^1<M^2<M^3,…, such that as N→∞, γN→0, and for each N≥N0 and each MN≥M^N,
(29)εN≤c0γN+sup(t,s)|qs(t,s)|sup(t,s)|η(t,s)-s|+c1sup(t,s)(η(t,s)-s)2.Proof.
We have, from the triangle inequality, that(30)εN≤maxk,n(|X~N(k,n)MN-u(kdtN,v~N(k,n))|+|u(kdtN,v~N(k,n))-q(kdtN,v~N(k,n))X~N(k,n)MN|)≤maxk,n|X~N(k,n)MN-u(kdtN,v~N(k,n))|+sup(t,s)∈[0,T]×𝒟|u(t,s)-q(t,s)|,
where u is defined by (24).
By Theorem4, almost surely, there exist a sequence {γN}, c0<∞, N0, and M^1<M^2<M^3,…, such that as N→∞, γN→0, and for each N≥N0 and each MN≥M^N, the first term above is smaller than c0γN.
The second term represents the error caused by location perturbation. By (24) and Taylor’s theorem, there exists c1<∞ such that
(31)u(t,s)-q(t,s)=q(t,η(t,s))-q(t,s)≤qs(t,s)(η(t,s)-s)+c1(η(t,s)-s)2.
Therefore we have that
(32)sup(t,s)|u(t,s)-q(t,s)|≤sup(t,s)|qs(t,s)|sup(t,s)|η(t,s)-s|+c1sup(t,s)(η(t,s)-s)2.
By (30) this completes the proof.This proposition states that, for fixedq and for N and MN sufficiently large, εN is dominated by the supremum location perturbation sup(t,s)|η(t,s)-s|, when it is close to 0. We note that by definition sup(t,s)|η(t,s)-s|=sup(t,s)|ϕ(t,s)-s|. In the case where X~N are uniform; that is, η(t,s)=ϕ(t,s)=s, the last two terms on the right-hand side of (29) vanish.


## 3.2.4. Limiting PDEs for Nonuniform Networks

Consider a sequence{X~N} of networks with given network behavior and with node locations specified by a given transformation function ϕ with inverse η. If a sequence {XN} of uniform networks mirrors {X~N}, from this given network behavior, we can find the continuum limit q of {XN} by constructing its limiting PDE as in Section 3.1.2. Suppose that this PDE has the form
(33)q˙(t,s)=Q(s,q(t,s),∂q∂sj(t,s),∂2q∂sj2(t,s)),
with initial condition q(0,s)=q0(s), where j=1,…,J, t∈[0,T], and s=(s1,…,sJ)∈𝒟. By Theorem 4, we have that the continuum limit u(t,s) of {X~N} satisfies (24).However, in general, we can only solve (33) numerically instead of analytically. In fact, all the limiting PDEs in this paper are solved by software using numerical methods. In this case we cannot find the closed-form expression of u from q using (24). Instead, we derive a PDE that u satisfies so that we can solve it numerically.Suppose thatu(t,s) solves the PDE
(34)u˙(t,s)=Γ(s,u(t,s),∂u∂sj(t,s),∂2u∂sj2(t,s)),
with initial condition u(0,s)=u0(s), where j=1,…,J and (t,s)∈[0,T]×𝒟. We now find Γ from the known PDE (33).By (23), (24), and the chain rule,
(35)∂u∂sj(t,s)=∂ηj∂sj(t,s)∂q∂sj(t,η(t,s)).
By (23), the product rule, and the chain rule,
(36)∂2u∂sj2(t,s)=∂2ηj∂sj2(t,s)∂q∂sj(t,η(t,s))+(∂ηj∂sj(t,s))2∂2q∂sj2(t,η(t,s)).
Note that, without assumption (23), the expression of the derivatives above would be much more complex. Then by (24), (33), and (34) we have
(37)Γ(s,u(t,s),∂u∂sj(t,s),∂2u∂sj2(t,s))=Q((∂2ηj/∂sj2)(t,s)(∂u/∂sj)(t,s)((∂ηj/∂sj)(t,s))3η(t,s),u(t,s),(∂u/∂sj)(t,s)(∂ηj/∂sj)(t,s),(∂2u/∂sj2)(t,s)((∂ηj/∂sj)(t,s))2,-(∂2ηj/∂sj2)(t,s)(∂u/∂sj)(t,s)((∂ηj/∂sj)(t,s))3),
where u0(s)=q0(η(0,s)). Hence we find the limiting PDE (34) of {X~N}.We present a concrete numerical example of the nonuniform network and its continuum limit later in Section4.2.


## 3.3. Control of Nonuniform Networks

The global characteristic of the network is determined by the transmission-interference rule defined in Section3.2.2 and is described by its limiting PDE. The transmission-interference rule depends entirely on the transmission range L and the probabilities Pi, which in turn by (16) depends on the direction function pi. On the other hand, L and pi also determine the limiting PDE of a sequence of networks. Therefore we can control the transmission-interference rule to obtain the desired limiting PDE, and hence the desired global characteristic of the network, by changing L and pi.For uniform networks, this procedure is straightforward becauseL and pi relate directly to the form and coefficients of the limiting PDE. For example, for the 1D 1-step network in Section 2.2 with limiting PDE (14), increasing the convection c results in a greater bias of the PDE solution to the left side of the domain. (A numerical example of this network is provided in Section 4.1.1.)We now study this kind of control for nonuniform and possibly mobile networks. For such networks, we have to take into account the varying node locations in order to still achieve certain global characteristics. The goal is to develop a control method so that the continuum limit is invariant under node locations and mobility, that is, remains the same as a reference, which is the continuum limit of the sequence of corresponding uniform networks with a certain transmission-interference rule. We then say the sequence has a location-invariant continuum limit.We illustrate this idea in Figure3. The plus signs in both figures represent the queues of a certain uniform network at a certain time. The solid lines in both figures represent the continuum limit (the limiting PDE solution) of the same uniform network at the same time. Thus they resemble each other. On the left, the diamonds represent the queues of a nonuniform network with the same transmission-interference rule as the uniform network, but no longer resembling the continuum limit because of the changes in node locations. On the right, the circles represent the queues of a second nonuniform network with the same node locations as the first nonuniform network, but under some control over its transmission-interference rule, therefore resembling the continuum limit of the uniform network. In other words, location invariance in the second nonuniform network has been achieved by network control. Apparently, for this particular network, such a control scheme has to be able to direct more (and the right amount of) data traffic to the right-hand side. In what follows, we describe how this can be done by properly increasing the probabilities of the nodes transmitting to the right through the use of the limiting PDEs.An illustration of control of nonuniform networks. On thex-axis, the × marks are the uniform grid, and the Δ marks are the nonuniform node locations.
(a)
(b)Throughout the paper we assume no control over node location or motion.


### 3.3.1. Transmission-Interference Rule for Location Invariance

Consider a sequence{X~N} of nonuniform networks whose node locations are specified by a given transformation function ϕ with inverse η and a sequence {X^N} of uniform networks with given transmission-interference rule and continuum limit u. We want to control the transmission-interference rule of {X~N} so that it also converges to u, that is, obtains the location-invariant continuum limit.Again we do not assume a known closed-form expression ofu. Instead, assume that u(t,s) solves (34), except that Γ is now given.Define(38)q(t,s)=u(t,ϕ(t,s)).Suppose that a sequence{XN} of uniform networks has continuum limit q(t,s). By Theorem 4, for {X~N} to converge to this desired u(t,s), it suffices that {X~N} mirrors {XN}. Therefore all we have to do is to specify the transmission-interference rule of {XN} to {X~N}. Next we find this transmission-interference rule.Suppose thatq(t,s) solves (33), except that Q is now unknown. Again using the product rule and the chain rule as we did in Section 3.2.4, by (33), (34), and (38), we have that
(39)Q(s,q(t,s),∂q∂sj(t,s),∂2q∂sj2(t,s))=Γ((∂2ηj/∂sj2)(t,s)(∂u/∂sj)(t,s)((∂ηj/∂sj)(t,s))3ϕ(t,s),q(t,s),(∂q/∂sj)(t,s)(∂ϕj/∂sj)(t,s),(∂2q/∂sj2)(t,s)((∂ϕj/∂sj)(t,s))2-(∂2ϕj/∂sj2)(t,s)(∂q/∂sj)(t,s)((∂ϕj/∂sj)(t,s))3),
and q0(s)=u0(ϕ(0,s)), where j=1,…,J.Sinceq(t,s) is the continuum limit of a sequence of uniform networks, (33) must be a case of (20), the general limiting PDE. Therefore we can replace the left-hand side of (39) by the right-hand side of (20) and get
(40)∑j=1J‍(b(j)(t,s)∂∂sj(∂z∂sj(1+(λ(J,L)+1)z(t,s))×(1-z(t,s))(λ(J,L)-1)∂z∂sj(t,s))+2(1-z(t,s))(λ(J,L)-1)∂z∂sj(t,s)∂b(j)∂sj(t,s)+z(t,s)(1-z(t,s))λ(J,L)∂2b(j)∂sj2(t,s)+∂∂sj(c(j)(t,s)z(t,s)(1-z(t,s))λ(J,L)))+gp(t,s).=Γ(ϕ(t,s),q(t,s),(∂q/∂sj)(t,s)(∂ϕj/∂sj)(t,s),(∂2q/∂sj2)(t,s)((∂ϕj/∂sj)(t,s))2-(∂2ϕj/∂sj2)(t,s)(∂q/∂sj)(t,s)((∂ϕj/∂sj)(t,s))3).
We call this the comparison equation. If we can solve it for L, pl, and gp, our goal is accomplished because they determine the network behavior, which includes the transmission-interference rule, for each N-node uniform network in the mirroring sequence {XN}. If we assign the same transmission-interference rule to {X~N}, then it has the location-invariant continuum limit u(t,s).We note a constraint for (40): by (16), for each i, pi has to be sufficiently small such that, for each k and n,
(41)Pi(k,n)∈[0,1],∑i‍Pi(k,n)∈[0,1].
In turn by (17), bi and ci have to be sufficiently small for (41) to hold. By further observing (18) and (19), it follows that the transmission range L has to be sufficiently large. For this reason, it is necessary to generalize from 1-step to L-step transmission range, as we did in Section 3.1. Note that with this constraint, (40) is still underdetermined. Such freedom gives us a class of transmission-interference rules to assign to {X~N} instead of just one.One way to solve (40) is this. Suppose that we have chosen L sufficiently large. Since (34) is now given, we know the numerical form of u and in turn that of q by (38). For fixed to, we put q(to,s) in (40). For each j, if we fix b(j)(to,s), then we can solve (40), which is now an ordinary differential equation (ODE), for c(j)(to,s). Similarly, fixing c(j)(to,s) makes (40) an ODE that we can solve for b(j)(to,s). Then by (19) we can further choose bi and ci and further determine pi by (17). Thus we have found Pi by (16), which together with L determines the transmission-interference rule.


### 3.3.2. Distributed Control Using Local Information

The control method presented above is centralized in the sense that it requires knowledge of the transformation functionϕ over 𝒟. This assumes that each node knows the location of all other nodes. However, this is generally not the case in practice, especially for networks without a central control unit. In this subsection we present a distributed version of our control method, where only the locations of nearby nodes are needed for each node to determine its transmission-interference rule. We can do this because all the information needed to solve the comparison equation (40) can be approximated locally at each node.The derivatives ofϕ in (40) can be approximated from the locations of neighboring nodes using a certain finite difference method. For example, in the 1-D case, we can use the following approximation:
(42)∂ϕ∂s(t,s)≈ϕ(kdtN,vN(n+1))-ϕ(kdtN,vN(n-1))2dsN=v~N(k,n+1)-v~N(k,n-1)2dsN,wheret=kdtN and s∈[vN(n-1),vN(n+1)). Note that we can also use the location information of further neighbors to get a more accurate approximation of ∂ϕ/∂s. The trade-off between locality and accuracy can be flexibly adjusted.The ODE forb(j) or c(j) can also be solved based on local information using numerical procedures such as Euler’s method [40].We present two concrete examples of network control in 1D and 2D case, in Sections4.3.1 and 4.3.2, respectively.


## 3.3.1. Transmission-Interference Rule for Location Invariance

Consider a sequence{X~N} of nonuniform networks whose node locations are specified by a given transformation function ϕ with inverse η and a sequence {X^N} of uniform networks with given transmission-interference rule and continuum limit u. We want to control the transmission-interference rule of {X~N} so that it also converges to u, that is, obtains the location-invariant continuum limit.Again we do not assume a known closed-form expression ofu. Instead, assume that u(t,s) solves (34), except that Γ is now given.Define(38)q(t,s)=u(t,ϕ(t,s)).Suppose that a sequence{XN} of uniform networks has continuum limit q(t,s). By Theorem 4, for {X~N} to converge to this desired u(t,s), it suffices that {X~N} mirrors {XN}. Therefore all we have to do is to specify the transmission-interference rule of {XN} to {X~N}. Next we find this transmission-interference rule.Suppose thatq(t,s) solves (33), except that Q is now unknown. Again using the product rule and the chain rule as we did in Section 3.2.4, by (33), (34), and (38), we have that
(39)Q(s,q(t,s),∂q∂sj(t,s),∂2q∂sj2(t,s))=Γ((∂2ηj/∂sj2)(t,s)(∂u/∂sj)(t,s)((∂ηj/∂sj)(t,s))3ϕ(t,s),q(t,s),(∂q/∂sj)(t,s)(∂ϕj/∂sj)(t,s),(∂2q/∂sj2)(t,s)((∂ϕj/∂sj)(t,s))2-(∂2ϕj/∂sj2)(t,s)(∂q/∂sj)(t,s)((∂ϕj/∂sj)(t,s))3),
and q0(s)=u0(ϕ(0,s)), where j=1,…,J.Sinceq(t,s) is the continuum limit of a sequence of uniform networks, (33) must be a case of (20), the general limiting PDE. Therefore we can replace the left-hand side of (39) by the right-hand side of (20) and get
(40)∑j=1J‍(b(j)(t,s)∂∂sj(∂z∂sj(1+(λ(J,L)+1)z(t,s))×(1-z(t,s))(λ(J,L)-1)∂z∂sj(t,s))+2(1-z(t,s))(λ(J,L)-1)∂z∂sj(t,s)∂b(j)∂sj(t,s)+z(t,s)(1-z(t,s))λ(J,L)∂2b(j)∂sj2(t,s)+∂∂sj(c(j)(t,s)z(t,s)(1-z(t,s))λ(J,L)))+gp(t,s).=Γ(ϕ(t,s),q(t,s),(∂q/∂sj)(t,s)(∂ϕj/∂sj)(t,s),(∂2q/∂sj2)(t,s)((∂ϕj/∂sj)(t,s))2-(∂2ϕj/∂sj2)(t,s)(∂q/∂sj)(t,s)((∂ϕj/∂sj)(t,s))3).
We call this the comparison equation. If we can solve it for L, pl, and gp, our goal is accomplished because they determine the network behavior, which includes the transmission-interference rule, for each N-node uniform network in the mirroring sequence {XN}. If we assign the same transmission-interference rule to {X~N}, then it has the location-invariant continuum limit u(t,s).We note a constraint for (40): by (16), for each i, pi has to be sufficiently small such that, for each k and n,
(41)Pi(k,n)∈[0,1],∑i‍Pi(k,n)∈[0,1].
In turn by (17), bi and ci have to be sufficiently small for (41) to hold. By further observing (18) and (19), it follows that the transmission range L has to be sufficiently large. For this reason, it is necessary to generalize from 1-step to L-step transmission range, as we did in Section 3.1. Note that with this constraint, (40) is still underdetermined. Such freedom gives us a class of transmission-interference rules to assign to {X~N} instead of just one.One way to solve (40) is this. Suppose that we have chosen L sufficiently large. Since (34) is now given, we know the numerical form of u and in turn that of q by (38). For fixed to, we put q(to,s) in (40). For each j, if we fix b(j)(to,s), then we can solve (40), which is now an ordinary differential equation (ODE), for c(j)(to,s). Similarly, fixing c(j)(to,s) makes (40) an ODE that we can solve for b(j)(to,s). Then by (19) we can further choose bi and ci and further determine pi by (17). Thus we have found Pi by (16), which together with L determines the transmission-interference rule.


## 3.3.2. Distributed Control Using Local Information

The control method presented above is centralized in the sense that it requires knowledge of the transformation functionϕ over 𝒟. This assumes that each node knows the location of all other nodes. However, this is generally not the case in practice, especially for networks without a central control unit. In this subsection we present a distributed version of our control method, where only the locations of nearby nodes are needed for each node to determine its transmission-interference rule. We can do this because all the information needed to solve the comparison equation (40) can be approximated locally at each node.The derivatives ofϕ in (40) can be approximated from the locations of neighboring nodes using a certain finite difference method. For example, in the 1-D case, we can use the following approximation:
(42)∂ϕ∂s(t,s)≈ϕ(kdtN,vN(n+1))-ϕ(kdtN,vN(n-1))2dsN=v~N(k,n+1)-v~N(k,n-1)2dsN,wheret=kdtN and s∈[vN(n-1),vN(n+1)). Note that we can also use the location information of further neighbors to get a more accurate approximation of ∂ϕ/∂s. The trade-off between locality and accuracy can be flexibly adjusted.The ODE forb(j) or c(j) can also be solved based on local information using numerical procedures such as Euler’s method [40].We present two concrete examples of network control in 1D and 2D case, in Sections4.3.1 and 4.3.2, respectively.


## 4. Numerical Examples

We now present numerical examples for continuum model of uniform networks, continuum model of nonuniform networks, and control of nonuniform networks in Sections4.1, 4.2, and 4.3, respectively.


### 4.1. Examples of Uniform Networks

#### 4.1.1. 1D Example

We discussed the 1D 1-step network as a running example through Section2 and derived its limiting PDE (14). We now run Monte Carlo simulation for such a network and compare the simulation result with the limiting PDE solution. (Simulations and PDEs presented in this paper are run and solved using Matlab.) We set the spatial domain 𝒟=[-1,1]. We set the number of nodes N=50 and the normalizing parameter M=5000. We set the initial condition of the limiting PDE z0(s)=r1e-s2, where r1>0 is a constant, so that initially the nodes in the middle have messages to transmit, while those near the boundaries have very few. We set the incoming traffic function gp(s)=r2e-s2, where r2>0 is a constant determining the total load of the network, so that the nodes in the middle generate more messages than those near the boundaries. We set the diffusion function b=1/2 and the convection function c=2, so that each node transmits to the left with a higher probability than to the right; that is, more data traffic in the network is routed to the left. In Figure 4, we show the PDE solution and the simulation result at time t=1s, where the x-axis denotes the node location and y-axis denotes the normalized queue length. As we can see, the PDE well resembles the network.Figure 4
The Monte Carlo simulation and the PDE solution of a 1D 1-step network.


#### 4.1.2. 2D Examples

We consider 2-D 1-step networks with the two types of communicating neighbors separately (as illustrated in Figure2).Type I Communicating Neighbors. For 2D 1-step networks of Type I communicating neighbors, we define the probabilities Pi of transmitting to the 4 communicating neighbors as in Figure 2. This is the same as the 2D network studied in [1].The limiting PDE for this network is as follows:(43)z˙=∑j=12‍(b(j)∂∂sj((1+5z)(1-z)3∂z∂sj)+2(1-z)3∂z∂sj∂b(j)∂sj+z(1-z)4∂2b(j)∂sj2+∂∂sj(c(j)z(1-z)4))+gp,
where b(1)=(b1+b2)/2, b(2)=(b3+b4)/2, c(1)=c1-c2, c(2)=c3-c4, and (s1,s2)∈𝒟. (As mentioned in Section 3.1.2, we omit the detailed algebraic derivation.)We consider such a network over the spatial domainD=[-1,1]×[-1,1]. We set the number of nodes N=80×80 and the normalizing parameter M=803. We set the initial condition
(44)z0(s)=r1e-4((s1+0.65)2+(s2+0.75)2)+r2e-3((s1-0.75)2+(s2-0.85)2)+r3e-2((s1-0.75)2+(s2+0.75)2)+r4e-3((s1+0.85)2+(s2-0.75)2),
where the constants r1,…,r4>0, so that initially the nodes near (-0.65,-0.75), (0.75,0.85), (0.75,-0.75), and (-0.85,0.75) have more messages to transmit than those far away from these points. We set the incoming traffic function
(45)z0(s)=r5e-4((s1+0.65)2+(s2+0.75)2)+r6e-3((s1-0.75)2+(s2-0.85)2)+r7e-2((s1-0.75)2+(s2+0.75)2)+r8e-3((s1+0.85)2+(s2-0.75)2),
where the constants r5,…,r8>0, so that the nodes near (-0.65,-0.75), (0.75,0.85), (0.75,-0.75), and (-0.85,0.75) generate more messages to transmit than those far away from these points. This may correspond to four information sources at these four points that generate different rate of data traffic. Set the diffusion functions bi=1/4, where i=1,…,4, and the convection functions c1=0, c2=1, c3=0.1, and c4=-0.1. Hence b(1)=b(2)=1/4, c(1)=-1, and c(2)=0.2, so that more data traffic in the network is routed to the south and the east. In Figure 5, we show the contour of the PDE solution and the simulation result at t=0.1s. We can again see the resemblance.The Monte Carlo simulation and the PDE solution of a 2D 1-step network of Type I communicating neighbors.
(a)
(b)Type II Communicating Neighbors. For 2-D 1-step networks of Type II communicating neighbors, we define the probabilities Pi of transmitting to the 8 communicating neighbors as in Figure 2. The limiting PDE is as follows:
(46)z˙=∑j=12‍(b(j)∂∂sj((1+9z)(1-z)7∂z∂sj)+2(1-z)7∂z∂sj∂b(j)∂sj+z(1-z)8∂2b(j)∂sj2+∂∂sj(c(j)z(1-z)8))+gp,
where b(1)=∑l=1,2,5,…,8‍(bl/2), b(2)=∑l=3,4,5,…,8‍(bl/2), c(1)=c1-c2+c5-c7+c6-c8, and c(2)=c3-  c4+  c5-c6+c7-c8.Again the spatial domainD=[-1,1]×[-1,1]. We set the number of nodes N=80×80 and the normalizing parameter M=803. We set the initial condition
(47)z0(s)=r1e-4((s1+0.55)2+(s2+0.55)2)+r2e(s1-0.55)2+(s2-0.55)2,
where the constants r1,r2>0, so that initially the nodes near (-0.55,-0.55) and (0.55,0.55) have more messages to transmit than those far away from these two points. We set the incoming incoming traffic function
(48)gp(s)=r3e-4((s1+0.55)2+(s2+0.55)2)+r4e(s1-0.55)2+(s2-0.55)2,
where the constants r3,r4>0, so that the nodes near (-0.55,-0.55) and (0.55,0.55) generate more messages to transmit than those far away from these two points. This may correspond to two information sources at these two points that generate different rates of data traffic. In Figure 6, we show the contours of the PDE solution and the simulation results with the diffusion functions bi=1/8, for i=1,…,8, and convection functions c1=1, c2=2, c3=3, c4=4, c5=-1, c6=-2, c7=-3, and c8=-4. Hence b(1)=b(1)=3/8, c(1)=3, and c(2)=1, so that more data traffic in the network is routed to the west and the south.The Monte Carlo simulation and the PDE solution of a 2D 1-step network of Type II communicating neighbors.
(a)
(b)The reader can verify that the two PDEs (43) and (46) above are special cases of (20).


### 4.2. Example of Nonuniform Network

We illustrate a 2-D nonuniform networkX~N, its continuum limit u(t,s), and the continuum limit q(t,s) of its mirroring uniform network in Figure 7. The spatial domain D=[-1,1]×[-1,1]. We assume that the mirroring uniform network is a 2D 1-step network of Type-I communicating neighbors. Therefore q satisfies the limiting PDE (43). For the mirroring uniform network, we set the initial condition q0(s)=l1e-(s12+s22), and incoming traffic gp(s)=l2e-(s12+s22) where the constants l1,l2>0; we set the diffusion functions bi=1/4 and the convection functions ci=0, for i=1,…,4. The inverse transformation function here is set to be ηj(s)=(sj+1)2/2-1 for j=1,2. (Notice that this satisfies (23)) Therefore the continuum limit u of the nonuniform network X~N is u(t,s)=q(t,η(s)).A nonuniform network, its limiting PDE solution, and the limiting PDE solution of its mirroring uniform network.
(a)
(b)
(c)


### 4.3. Examples of Control of Nonuniform Networks

#### 4.3.1. 1D Example

Let the domain𝒟=[-1,1]. Let u(t,s) be the continuum limit of a sequence {X^N} of 1-D 1-step uniform networks with transmission range L^=1, the diffusion function b^=1/2, the convection function c^=0, and a given incoming traffic function g^p for all (t,s)∈[0,T]×𝒟. A given transformation function ϕ specifies the node locations of a sequence {X~N} of nonuniform networks. We show how to find the transmission-interference rule for {X~N} to converge to u(t,s). As the continuum limit of this particular 1-D 1-step network, u(t,s) solves the PDE
(49)u˙=∂∂s(12(1-u)(1+3u)∂u∂s)+gp,
with boundary condition u(t,s)=0 and initial condition u(0,s)=u0(s). This is a special case of (14).In this caseλ(J,L)=2L. Let θ=1/(2(∂ϕ/∂s)2). Then the comparison equation (40) becomes
(50)b(1)∂∂s((1+(2L+1)q)(1-q)(2L-1)∂q∂s)+2(1-q)(2L-1)∂q∂s∂b(1)∂s+q(1-q)2L∂2∂s2b(1)+∂∂s(c(1)q(1-q)2L)+g^p=θ(1-q)(1+3q)∂2q∂s2+2(1-3q)θ(∂q∂s)2+12(1-q)(1+3q)∂θ∂s∂q∂s+gp(ϕ),
where q is the continuum limit of the mirroring sequence {XN} of {X~N}.We assume thatg^p(s)=gp(ϕ(t,s)), which corresponds to the assumption that the continuum limit of the incoming traffic is invariant under node locations and mobility. This assumption is feasible in a large class of networks where traffic load depends directly on actual physical location. For example, in a wireless sensor network that detects environmental events such as a forest fire, the event-triggered data traffic depends on the distribution of heat rather than the node locations.Suppose that we set(51)b(1)=θ.
Since q is known to be the solution of (49), (50) has now become a first-order linear ODE for c(1).We can use Euler’s method to solve this ODE based on local information. For fixedto, suppose the ODE is written in the form Φ(to,s,c(1))=dc(1)/ds. We first choose c(1)(to,s(1)) such that Pi(ko,1) satisfies (41), where to=kodtN. Then we can approximate c(j)(to,s(n)) by c^(to,n), where c^(to,1)=c(j)(to,s(1)), and c^(to,n+1)=c^(to,n)+Φ(to,s(n),c^(to,n))dsN, for n=1,…,N.With this givenϕ, the transmission range L of the mobile network has to be greater or equal to 2 for (41) to hold. We choose L=2. Then any bi,ci, where i=1,2, that satisfy (50) and (51) will give us the desired transmission-interference rule of networks in {XN} and, hence, that of {X~N}.We simulate a 51-node controlled mobile networkX~N in the sequence {X~N} that mirrors {XN}, whose node locations are specified by this given ϕ. In Figure 8, we compare the simulation result with the continuum limit of {X^N}, at t=1s. We set the initial condition z0(s)=r1e-s2 and the incoming traffic function gp(s)=r2e-s2, where the constants r1,r2>0. As we can see, the global characteristic of X~N resembles u(t,s), the continuum limit of {X^N}.Figure 8
The comparison of the 1D controlled network and the location-invariant continuum limit att=1s. On the x-axis, the × marks are the uniform grid, and the Δ marks are the nonuniform node locations.


#### 4.3.2. 2D Example

Let the domain𝒟=[-1,1]×[-1,1]. Let u(t,s) be the continuum limit of a sequence {X^N} of 2-D 1-step uniform networks of Type-II communicating neighbors with transmission range L^=1, the diffusion functions b^i(t,s)=1/8, for i=1,…,8, the convection functions c^(j)=0, for j=1,2, and given incoming traffic function g^p for all (t,s)∈[0,T]×𝒟. Again denote the given transformation function that specifies the node locations of {X~N} by ϕ(t,s).As the continuum limit of this particular 1D 1-step network,u(t,s) solves the PDE
(52)u˙=38∑j=12‍∂∂sj((1+9u)(1-u)7∂u∂sj)+g^p,
with boundary condition u(t,s)=0 and initial condition u(0,s)=u0(s). This is a special case of (46).Letθj=1/(2(∂ϕj/∂sj)2). Then the comparison equation (40) becomes
(53)∑j=12‍(b(j)∂∂s((1+(λ(2,L)+1)q)(1-q)(λ(2,L)-1)∂q∂s)+2(1-q)(λ(2,L)-1)∂q∂s∂b^j∂sj+q(1-q)λ(2,L)∂2b(j)∂s2+∂∂s(c(j)q(1-q)λ(2,L)))+g^p=∑j=12‍(34(1-q)7(1+9q)θj∂2q∂xj2+38(1-q)7(1+9q)∂θj∂xj∂q∂xj+32(1-36q)(1-q)6θj(∂q∂xj)2)+gp(ϕ),
where q is the continuum limit of the mirroring sequence {XN} of {X~N}. Assume that g^p(t,s)= gp(ϕ(t,s)) and
(54)b(j)=θj.
Since q is known to be the solution of (52), we have two first-order linear ODEs of c(j), where j=1,2.For this givenϕ, L=2 is sufficient for (41) to hold. Then any bi,ci,l=1,2 that satisfy (53) and (54) will give us the desired transmission-interference rule for {XN} and, hence, {X~N}.We simulate a(100×100)-node controlled mobile network X~N in the sequence {X~N} that mirrors {XN}, whose node locations are specified by ϕ. In Figure 9, we compare the simulation result with the continuum limit of {X^N}, at t=1s. We set the initial condition
(55)z0(s)=r1e-4((s1+0.6)2+(s2+0.6)2)+r2e-3((s1-0.6)2+(s2-0.6)2)
and the incoming traffic function
(56)gp(s)=r3e-4((s1+0.6)2+(s2+0.6)2)+r4e-3((s1-0.6)2+(s2-0.6)2),
where the constants r1,…,r4>0. Again, the global characteristic of X~N resembles u(t,s), the continuum limit of {X^N}.The comparison of the 2D controlled network and the location-invariant continuum limit att=1s.
(a)
(b)


## 4.1. Examples of Uniform Networks

### 4.1.1. 1D Example

We discussed the 1D 1-step network as a running example through Section2 and derived its limiting PDE (14). We now run Monte Carlo simulation for such a network and compare the simulation result with the limiting PDE solution. (Simulations and PDEs presented in this paper are run and solved using Matlab.) We set the spatial domain 𝒟=[-1,1]. We set the number of nodes N=50 and the normalizing parameter M=5000. We set the initial condition of the limiting PDE z0(s)=r1e-s2, where r1>0 is a constant, so that initially the nodes in the middle have messages to transmit, while those near the boundaries have very few. We set the incoming traffic function gp(s)=r2e-s2, where r2>0 is a constant determining the total load of the network, so that the nodes in the middle generate more messages than those near the boundaries. We set the diffusion function b=1/2 and the convection function c=2, so that each node transmits to the left with a higher probability than to the right; that is, more data traffic in the network is routed to the left. In Figure 4, we show the PDE solution and the simulation result at time t=1s, where the x-axis denotes the node location and y-axis denotes the normalized queue length. As we can see, the PDE well resembles the network.Figure 4
The Monte Carlo simulation and the PDE solution of a 1D 1-step network.


### 4.1.2. 2D Examples

We consider 2-D 1-step networks with the two types of communicating neighbors separately (as illustrated in Figure2).Type I Communicating Neighbors. For 2D 1-step networks of Type I communicating neighbors, we define the probabilities Pi of transmitting to the 4 communicating neighbors as in Figure 2. This is the same as the 2D network studied in [1].The limiting PDE for this network is as follows:(43)z˙=∑j=12‍(b(j)∂∂sj((1+5z)(1-z)3∂z∂sj)+2(1-z)3∂z∂sj∂b(j)∂sj+z(1-z)4∂2b(j)∂sj2+∂∂sj(c(j)z(1-z)4))+gp,
where b(1)=(b1+b2)/2, b(2)=(b3+b4)/2, c(1)=c1-c2, c(2)=c3-c4, and (s1,s2)∈𝒟. (As mentioned in Section 3.1.2, we omit the detailed algebraic derivation.)We consider such a network over the spatial domainD=[-1,1]×[-1,1]. We set the number of nodes N=80×80 and the normalizing parameter M=803. We set the initial condition
(44)z0(s)=r1e-4((s1+0.65)2+(s2+0.75)2)+r2e-3((s1-0.75)2+(s2-0.85)2)+r3e-2((s1-0.75)2+(s2+0.75)2)+r4e-3((s1+0.85)2+(s2-0.75)2),
where the constants r1,…,r4>0, so that initially the nodes near (-0.65,-0.75), (0.75,0.85), (0.75,-0.75), and (-0.85,0.75) have more messages to transmit than those far away from these points. We set the incoming traffic function
(45)z0(s)=r5e-4((s1+0.65)2+(s2+0.75)2)+r6e-3((s1-0.75)2+(s2-0.85)2)+r7e-2((s1-0.75)2+(s2+0.75)2)+r8e-3((s1+0.85)2+(s2-0.75)2),
where the constants r5,…,r8>0, so that the nodes near (-0.65,-0.75), (0.75,0.85), (0.75,-0.75), and (-0.85,0.75) generate more messages to transmit than those far away from these points. This may correspond to four information sources at these four points that generate different rate of data traffic. Set the diffusion functions bi=1/4, where i=1,…,4, and the convection functions c1=0, c2=1, c3=0.1, and c4=-0.1. Hence b(1)=b(2)=1/4, c(1)=-1, and c(2)=0.2, so that more data traffic in the network is routed to the south and the east. In Figure 5, we show the contour of the PDE solution and the simulation result at t=0.1s. We can again see the resemblance.The Monte Carlo simulation and the PDE solution of a 2D 1-step network of Type I communicating neighbors.
(a)
(b)Type II Communicating Neighbors. For 2-D 1-step networks of Type II communicating neighbors, we define the probabilities Pi of transmitting to the 8 communicating neighbors as in Figure 2. The limiting PDE is as follows:
(46)z˙=∑j=12‍(b(j)∂∂sj((1+9z)(1-z)7∂z∂sj)+2(1-z)7∂z∂sj∂b(j)∂sj+z(1-z)8∂2b(j)∂sj2+∂∂sj(c(j)z(1-z)8))+gp,
where b(1)=∑l=1,2,5,…,8‍(bl/2), b(2)=∑l=3,4,5,…,8‍(bl/2), c(1)=c1-c2+c5-c7+c6-c8, and c(2)=c3-  c4+  c5-c6+c7-c8.Again the spatial domainD=[-1,1]×[-1,1]. We set the number of nodes N=80×80 and the normalizing parameter M=803. We set the initial condition
(47)z0(s)=r1e-4((s1+0.55)2+(s2+0.55)2)+r2e(s1-0.55)2+(s2-0.55)2,
where the constants r1,r2>0, so that initially the nodes near (-0.55,-0.55) and (0.55,0.55) have more messages to transmit than those far away from these two points. We set the incoming incoming traffic function
(48)gp(s)=r3e-4((s1+0.55)2+(s2+0.55)2)+r4e(s1-0.55)2+(s2-0.55)2,
where the constants r3,r4>0, so that the nodes near (-0.55,-0.55) and (0.55,0.55) generate more messages to transmit than those far away from these two points. This may correspond to two information sources at these two points that generate different rates of data traffic. In Figure 6, we show the contours of the PDE solution and the simulation results with the diffusion functions bi=1/8, for i=1,…,8, and convection functions c1=1, c2=2, c3=3, c4=4, c5=-1, c6=-2, c7=-3, and c8=-4. Hence b(1)=b(1)=3/8, c(1)=3, and c(2)=1, so that more data traffic in the network is routed to the west and the south.The Monte Carlo simulation and the PDE solution of a 2D 1-step network of Type II communicating neighbors.
(a)
(b)The reader can verify that the two PDEs (43) and (46) above are special cases of (20).


## 4.1.1. 1D Example

We discussed the 1D 1-step network as a running example through Section2 and derived its limiting PDE (14). We now run Monte Carlo simulation for such a network and compare the simulation result with the limiting PDE solution. (Simulations and PDEs presented in this paper are run and solved using Matlab.) We set the spatial domain 𝒟=[-1,1]. We set the number of nodes N=50 and the normalizing parameter M=5000. We set the initial condition of the limiting PDE z0(s)=r1e-s2, where r1>0 is a constant, so that initially the nodes in the middle have messages to transmit, while those near the boundaries have very few. We set the incoming traffic function gp(s)=r2e-s2, where r2>0 is a constant determining the total load of the network, so that the nodes in the middle generate more messages than those near the boundaries. We set the diffusion function b=1/2 and the convection function c=2, so that each node transmits to the left with a higher probability than to the right; that is, more data traffic in the network is routed to the left. In Figure 4, we show the PDE solution and the simulation result at time t=1s, where the x-axis denotes the node location and y-axis denotes the normalized queue length. As we can see, the PDE well resembles the network.Figure 4
The Monte Carlo simulation and the PDE solution of a 1D 1-step network.


## 4.1.2. 2D Examples

We consider 2-D 1-step networks with the two types of communicating neighbors separately (as illustrated in Figure2).Type I Communicating Neighbors. For 2D 1-step networks of Type I communicating neighbors, we define the probabilities Pi of transmitting to the 4 communicating neighbors as in Figure 2. This is the same as the 2D network studied in [1].The limiting PDE for this network is as follows:(43)z˙=∑j=12‍(b(j)∂∂sj((1+5z)(1-z)3∂z∂sj)+2(1-z)3∂z∂sj∂b(j)∂sj+z(1-z)4∂2b(j)∂sj2+∂∂sj(c(j)z(1-z)4))+gp,
where b(1)=(b1+b2)/2, b(2)=(b3+b4)/2, c(1)=c1-c2, c(2)=c3-c4, and (s1,s2)∈𝒟. (As mentioned in Section 3.1.2, we omit the detailed algebraic derivation.)We consider such a network over the spatial domainD=[-1,1]×[-1,1]. We set the number of nodes N=80×80 and the normalizing parameter M=803. We set the initial condition
(44)z0(s)=r1e-4((s1+0.65)2+(s2+0.75)2)+r2e-3((s1-0.75)2+(s2-0.85)2)+r3e-2((s1-0.75)2+(s2+0.75)2)+r4e-3((s1+0.85)2+(s2-0.75)2),
where the constants r1,…,r4>0, so that initially the nodes near (-0.65,-0.75), (0.75,0.85), (0.75,-0.75), and (-0.85,0.75) have more messages to transmit than those far away from these points. We set the incoming traffic function
(45)z0(s)=r5e-4((s1+0.65)2+(s2+0.75)2)+r6e-3((s1-0.75)2+(s2-0.85)2)+r7e-2((s1-0.75)2+(s2+0.75)2)+r8e-3((s1+0.85)2+(s2-0.75)2),
where the constants r5,…,r8>0, so that the nodes near (-0.65,-0.75), (0.75,0.85), (0.75,-0.75), and (-0.85,0.75) generate more messages to transmit than those far away from these points. This may correspond to four information sources at these four points that generate different rate of data traffic. Set the diffusion functions bi=1/4, where i=1,…,4, and the convection functions c1=0, c2=1, c3=0.1, and c4=-0.1. Hence b(1)=b(2)=1/4, c(1)=-1, and c(2)=0.2, so that more data traffic in the network is routed to the south and the east. In Figure 5, we show the contour of the PDE solution and the simulation result at t=0.1s. We can again see the resemblance.The Monte Carlo simulation and the PDE solution of a 2D 1-step network of Type I communicating neighbors.
(a)
(b)Type II Communicating Neighbors. For 2-D 1-step networks of Type II communicating neighbors, we define the probabilities Pi of transmitting to the 8 communicating neighbors as in Figure 2. The limiting PDE is as follows:
(46)z˙=∑j=12‍(b(j)∂∂sj((1+9z)(1-z)7∂z∂sj)+2(1-z)7∂z∂sj∂b(j)∂sj+z(1-z)8∂2b(j)∂sj2+∂∂sj(c(j)z(1-z)8))+gp,
where b(1)=∑l=1,2,5,…,8‍(bl/2), b(2)=∑l=3,4,5,…,8‍(bl/2), c(1)=c1-c2+c5-c7+c6-c8, and c(2)=c3-  c4+  c5-c6+c7-c8.Again the spatial domainD=[-1,1]×[-1,1]. We set the number of nodes N=80×80 and the normalizing parameter M=803. We set the initial condition
(47)z0(s)=r1e-4((s1+0.55)2+(s2+0.55)2)+r2e(s1-0.55)2+(s2-0.55)2,
where the constants r1,r2>0, so that initially the nodes near (-0.55,-0.55) and (0.55,0.55) have more messages to transmit than those far away from these two points. We set the incoming incoming traffic function
(48)gp(s)=r3e-4((s1+0.55)2+(s2+0.55)2)+r4e(s1-0.55)2+(s2-0.55)2,
where the constants r3,r4>0, so that the nodes near (-0.55,-0.55) and (0.55,0.55) generate more messages to transmit than those far away from these two points. This may correspond to two information sources at these two points that generate different rates of data traffic. In Figure 6, we show the contours of the PDE solution and the simulation results with the diffusion functions bi=1/8, for i=1,…,8, and convection functions c1=1, c2=2, c3=3, c4=4, c5=-1, c6=-2, c7=-3, and c8=-4. Hence b(1)=b(1)=3/8, c(1)=3, and c(2)=1, so that more data traffic in the network is routed to the west and the south.The Monte Carlo simulation and the PDE solution of a 2D 1-step network of Type II communicating neighbors.
(a)
(b)The reader can verify that the two PDEs (43) and (46) above are special cases of (20).


## 4.2. Example of Nonuniform Network

We illustrate a 2-D nonuniform networkX~N, its continuum limit u(t,s), and the continuum limit q(t,s) of its mirroring uniform network in Figure 7. The spatial domain D=[-1,1]×[-1,1]. We assume that the mirroring uniform network is a 2D 1-step network of Type-I communicating neighbors. Therefore q satisfies the limiting PDE (43). For the mirroring uniform network, we set the initial condition q0(s)=l1e-(s12+s22), and incoming traffic gp(s)=l2e-(s12+s22) where the constants l1,l2>0; we set the diffusion functions bi=1/4 and the convection functions ci=0, for i=1,…,4. The inverse transformation function here is set to be ηj(s)=(sj+1)2/2-1 for j=1,2. (Notice that this satisfies (23)) Therefore the continuum limit u of the nonuniform network X~N is u(t,s)=q(t,η(s)).A nonuniform network, its limiting PDE solution, and the limiting PDE solution of its mirroring uniform network.
(a)
(b)
(c)


## 4.3. Examples of Control of Nonuniform Networks

### 4.3.1. 1D Example

Let the domain𝒟=[-1,1]. Let u(t,s) be the continuum limit of a sequence {X^N} of 1-D 1-step uniform networks with transmission range L^=1, the diffusion function b^=1/2, the convection function c^=0, and a given incoming traffic function g^p for all (t,s)∈[0,T]×𝒟. A given transformation function ϕ specifies the node locations of a sequence {X~N} of nonuniform networks. We show how to find the transmission-interference rule for {X~N} to converge to u(t,s). As the continuum limit of this particular 1-D 1-step network, u(t,s) solves the PDE
(49)u˙=∂∂s(12(1-u)(1+3u)∂u∂s)+gp,
with boundary condition u(t,s)=0 and initial condition u(0,s)=u0(s). This is a special case of (14).In this caseλ(J,L)=2L. Let θ=1/(2(∂ϕ/∂s)2). Then the comparison equation (40) becomes
(50)b(1)∂∂s((1+(2L+1)q)(1-q)(2L-1)∂q∂s)+2(1-q)(2L-1)∂q∂s∂b(1)∂s+q(1-q)2L∂2∂s2b(1)+∂∂s(c(1)q(1-q)2L)+g^p=θ(1-q)(1+3q)∂2q∂s2+2(1-3q)θ(∂q∂s)2+12(1-q)(1+3q)∂θ∂s∂q∂s+gp(ϕ),
where q is the continuum limit of the mirroring sequence {XN} of {X~N}.We assume thatg^p(s)=gp(ϕ(t,s)), which corresponds to the assumption that the continuum limit of the incoming traffic is invariant under node locations and mobility. This assumption is feasible in a large class of networks where traffic load depends directly on actual physical location. For example, in a wireless sensor network that detects environmental events such as a forest fire, the event-triggered data traffic depends on the distribution of heat rather than the node locations.Suppose that we set(51)b(1)=θ.
Since q is known to be the solution of (49), (50) has now become a first-order linear ODE for c(1).We can use Euler’s method to solve this ODE based on local information. For fixedto, suppose the ODE is written in the form Φ(to,s,c(1))=dc(1)/ds. We first choose c(1)(to,s(1)) such that Pi(ko,1) satisfies (41), where to=kodtN. Then we can approximate c(j)(to,s(n)) by c^(to,n), where c^(to,1)=c(j)(to,s(1)), and c^(to,n+1)=c^(to,n)+Φ(to,s(n),c^(to,n))dsN, for n=1,…,N.With this givenϕ, the transmission range L of the mobile network has to be greater or equal to 2 for (41) to hold. We choose L=2. Then any bi,ci, where i=1,2, that satisfy (50) and (51) will give us the desired transmission-interference rule of networks in {XN} and, hence, that of {X~N}.We simulate a 51-node controlled mobile networkX~N in the sequence {X~N} that mirrors {XN}, whose node locations are specified by this given ϕ. In Figure 8, we compare the simulation result with the continuum limit of {X^N}, at t=1s. We set the initial condition z0(s)=r1e-s2 and the incoming traffic function gp(s)=r2e-s2, where the constants r1,r2>0. As we can see, the global characteristic of X~N resembles u(t,s), the continuum limit of {X^N}.Figure 8
The comparison of the 1D controlled network and the location-invariant continuum limit att=1s. On the x-axis, the × marks are the uniform grid, and the Δ marks are the nonuniform node locations.


### 4.3.2. 2D Example

Let the domain𝒟=[-1,1]×[-1,1]. Let u(t,s) be the continuum limit of a sequence {X^N} of 2-D 1-step uniform networks of Type-II communicating neighbors with transmission range L^=1, the diffusion functions b^i(t,s)=1/8, for i=1,…,8, the convection functions c^(j)=0, for j=1,2, and given incoming traffic function g^p for all (t,s)∈[0,T]×𝒟. Again denote the given transformation function that specifies the node locations of {X~N} by ϕ(t,s).As the continuum limit of this particular 1D 1-step network,u(t,s) solves the PDE
(52)u˙=38∑j=12‍∂∂sj((1+9u)(1-u)7∂u∂sj)+g^p,
with boundary condition u(t,s)=0 and initial condition u(0,s)=u0(s). This is a special case of (46).Letθj=1/(2(∂ϕj/∂sj)2). Then the comparison equation (40) becomes
(53)∑j=12‍(b(j)∂∂s((1+(λ(2,L)+1)q)(1-q)(λ(2,L)-1)∂q∂s)+2(1-q)(λ(2,L)-1)∂q∂s∂b^j∂sj+q(1-q)λ(2,L)∂2b(j)∂s2+∂∂s(c(j)q(1-q)λ(2,L)))+g^p=∑j=12‍(34(1-q)7(1+9q)θj∂2q∂xj2+38(1-q)7(1+9q)∂θj∂xj∂q∂xj+32(1-36q)(1-q)6θj(∂q∂xj)2)+gp(ϕ),
where q is the continuum limit of the mirroring sequence {XN} of {X~N}. Assume that g^p(t,s)= gp(ϕ(t,s)) and
(54)b(j)=θj.
Since q is known to be the solution of (52), we have two first-order linear ODEs of c(j), where j=1,2.For this givenϕ, L=2 is sufficient for (41) to hold. Then any bi,ci,l=1,2 that satisfy (53) and (54) will give us the desired transmission-interference rule for {XN} and, hence, {X~N}.We simulate a(100×100)-node controlled mobile network X~N in the sequence {X~N} that mirrors {XN}, whose node locations are specified by ϕ. In Figure 9, we compare the simulation result with the continuum limit of {X^N}, at t=1s. We set the initial condition
(55)z0(s)=r1e-4((s1+0.6)2+(s2+0.6)2)+r2e-3((s1-0.6)2+(s2-0.6)2)
and the incoming traffic function
(56)gp(s)=r3e-4((s1+0.6)2+(s2+0.6)2)+r4e-3((s1-0.6)2+(s2-0.6)2),
where the constants r1,…,r4>0. Again, the global characteristic of X~N resembles u(t,s), the continuum limit of {X^N}.The comparison of the 2D controlled network and the location-invariant continuum limit att=1s.
(a)
(b)


## 4.3.1. 1D Example

Let the domain𝒟=[-1,1]. Let u(t,s) be the continuum limit of a sequence {X^N} of 1-D 1-step uniform networks with transmission range L^=1, the diffusion function b^=1/2, the convection function c^=0, and a given incoming traffic function g^p for all (t,s)∈[0,T]×𝒟. A given transformation function ϕ specifies the node locations of a sequence {X~N} of nonuniform networks. We show how to find the transmission-interference rule for {X~N} to converge to u(t,s). As the continuum limit of this particular 1-D 1-step network, u(t,s) solves the PDE
(49)u˙=∂∂s(12(1-u)(1+3u)∂u∂s)+gp,
with boundary condition u(t,s)=0 and initial condition u(0,s)=u0(s). This is a special case of (14).In this caseλ(J,L)=2L. Let θ=1/(2(∂ϕ/∂s)2). Then the comparison equation (40) becomes
(50)b(1)∂∂s((1+(2L+1)q)(1-q)(2L-1)∂q∂s)+2(1-q)(2L-1)∂q∂s∂b(1)∂s+q(1-q)2L∂2∂s2b(1)+∂∂s(c(1)q(1-q)2L)+g^p=θ(1-q)(1+3q)∂2q∂s2+2(1-3q)θ(∂q∂s)2+12(1-q)(1+3q)∂θ∂s∂q∂s+gp(ϕ),
where q is the continuum limit of the mirroring sequence {XN} of {X~N}.We assume thatg^p(s)=gp(ϕ(t,s)), which corresponds to the assumption that the continuum limit of the incoming traffic is invariant under node locations and mobility. This assumption is feasible in a large class of networks where traffic load depends directly on actual physical location. For example, in a wireless sensor network that detects environmental events such as a forest fire, the event-triggered data traffic depends on the distribution of heat rather than the node locations.Suppose that we set(51)b(1)=θ.
Since q is known to be the solution of (49), (50) has now become a first-order linear ODE for c(1).We can use Euler’s method to solve this ODE based on local information. For fixedto, suppose the ODE is written in the form Φ(to,s,c(1))=dc(1)/ds. We first choose c(1)(to,s(1)) such that Pi(ko,1) satisfies (41), where to=kodtN. Then we can approximate c(j)(to,s(n)) by c^(to,n), where c^(to,1)=c(j)(to,s(1)), and c^(to,n+1)=c^(to,n)+Φ(to,s(n),c^(to,n))dsN, for n=1,…,N.With this givenϕ, the transmission range L of the mobile network has to be greater or equal to 2 for (41) to hold. We choose L=2. Then any bi,ci, where i=1,2, that satisfy (50) and (51) will give us the desired transmission-interference rule of networks in {XN} and, hence, that of {X~N}.We simulate a 51-node controlled mobile networkX~N in the sequence {X~N} that mirrors {XN}, whose node locations are specified by this given ϕ. In Figure 8, we compare the simulation result with the continuum limit of {X^N}, at t=1s. We set the initial condition z0(s)=r1e-s2 and the incoming traffic function gp(s)=r2e-s2, where the constants r1,r2>0. As we can see, the global characteristic of X~N resembles u(t,s), the continuum limit of {X^N}.Figure 8
The comparison of the 1D controlled network and the location-invariant continuum limit att=1s. On the x-axis, the × marks are the uniform grid, and the Δ marks are the nonuniform node locations.


## 4.3.2. 2D Example

Let the domain𝒟=[-1,1]×[-1,1]. Let u(t,s) be the continuum limit of a sequence {X^N} of 2-D 1-step uniform networks of Type-II communicating neighbors with transmission range L^=1, the diffusion functions b^i(t,s)=1/8, for i=1,…,8, the convection functions c^(j)=0, for j=1,2, and given incoming traffic function g^p for all (t,s)∈[0,T]×𝒟. Again denote the given transformation function that specifies the node locations of {X~N} by ϕ(t,s).As the continuum limit of this particular 1D 1-step network,u(t,s) solves the PDE
(52)u˙=38∑j=12‍∂∂sj((1+9u)(1-u)7∂u∂sj)+g^p,
with boundary condition u(t,s)=0 and initial condition u(0,s)=u0(s). This is a special case of (46).Letθj=1/(2(∂ϕj/∂sj)2). Then the comparison equation (40) becomes
(53)∑j=12‍(b(j)∂∂s((1+(λ(2,L)+1)q)(1-q)(λ(2,L)-1)∂q∂s)+2(1-q)(λ(2,L)-1)∂q∂s∂b^j∂sj+q(1-q)λ(2,L)∂2b(j)∂s2+∂∂s(c(j)q(1-q)λ(2,L)))+g^p=∑j=12‍(34(1-q)7(1+9q)θj∂2q∂xj2+38(1-q)7(1+9q)∂θj∂xj∂q∂xj+32(1-36q)(1-q)6θj(∂q∂xj)2)+gp(ϕ),
where q is the continuum limit of the mirroring sequence {XN} of {X~N}. Assume that g^p(t,s)= gp(ϕ(t,s)) and
(54)b(j)=θj.
Since q is known to be the solution of (52), we have two first-order linear ODEs of c(j), where j=1,2.For this givenϕ, L=2 is sufficient for (41) to hold. Then any bi,ci,l=1,2 that satisfy (53) and (54) will give us the desired transmission-interference rule for {XN} and, hence, {X~N}.We simulate a(100×100)-node controlled mobile network X~N in the sequence {X~N} that mirrors {XN}, whose node locations are specified by ϕ. In Figure 9, we compare the simulation result with the continuum limit of {X^N}, at t=1s. We set the initial condition
(55)z0(s)=r1e-4((s1+0.6)2+(s2+0.6)2)+r2e-3((s1-0.6)2+(s2-0.6)2)
and the incoming traffic function
(56)gp(s)=r3e-4((s1+0.6)2+(s2+0.6)2)+r4e-3((s1-0.6)2+(s2-0.6)2),
where the constants r1,…,r4>0. Again, the global characteristic of X~N resembles u(t,s), the continuum limit of {X^N}.The comparison of the 2D controlled network and the location-invariant continuum limit att=1s.
(a)
(b)


## 5. Conclusion

In this paper we study the modeling of nonuniform and possibly mobile networks via nonlinear PDEs and develop a distributed method to control their transmission-interference rules to maintain certain global characteristics. We demonstrate our method with a family of wireless sensor networks. Our method can be extended to other network models. The freedom in the control method mentioned in Section3.3 can also be further exploited to improve the network performance.



---

*Source: 262581-2013-04-16.xml*