## Abstract

The throughput of delay-sensitive traffic in a Rayleigh fading network is studied by adopting a scaling limit approach. The case of the study is that of a pair of nodes establishing a data stream that has routing priority over all the remaining traffic in the network. For every delay constraint, upper and lower bounds on the achievable information rate between the two endpoints of the stream are obtained as the network size grows. The analysis concerns *decentralized schemes*, in the sense that all nodes make next-hop decisions based only on *local* information, namely their channel strength to other nodes in the network and the position of the destination node. This is particularly important in a fading scenario, where the channel strength varies with time and hence pre-computing routes can be of little help. Natural applications are remote surveillance using sensor networks and communication in emergency scenarios.

## 1. Introduction

Wireless networks present a number of challenges unseen in their wired counterparts. First, since the wireless channel is a shared medium, simultaneous transmissions may interfere with each other and the rate at which any two nodes can directly communicate depends on the amount of interference at the receiver. Further, the channel strength depends on the loss due to the propagation of the signal in space, and also varies in time due to multipath fading. A practical strategy for communication in this scenario is multi-hop routing, wherein the nodes cooperate by buffering and forwarding each others' data packets. Channel-state estimation is performed at each hop along the route and packets are sent at a certain rate that depends on the current channel conditions.

In this context, we formulate the following problem. Consider a wireless fading network in which a set of sources is communicating to their respective destinations. Now suppose a single source–destination pair wants to exchange some *delay-sensitive* information. Hence, data exchanged between this pair of nodes are given priority over other network traffic. For example, such a situation can arise whenever a ‘critical’ event requires a real-time data link between two nodes in the network. We ask: what is the maximum rate of communication that such a pair can achieve for any given delay constraint?

While addressing the above question, we consider only *decentralized* routing schemes, which means that all nodes make next-hop decisions based only on *local* information, namely their channel strength to other nodes in the network and the position of the destination node. This is particularly important in a fading scenario, where the channel strength varies with time and hence pre-computing routes can be of little help. Furthermore, since we are interested in the throughput scaling limit for large networks, maintaining a global knowledge of connectivity at each node in the network is clearly an impossible task.

Intuitively, to achieve a smaller delay, packets of the high-priority stream need to be routed along longer hops that, due to a higher path loss, restrict the data rate that can be supported, and our main contribution is to precisely characterize this trade-off. In doing so, we explicitly take into account interference and the time that packets are queued at the intermediate nodes along the multi-hop path, before reaching the destination. We show that the throughput is proportional to a power law of the ratio between the delay and the system's size, whose exponent depends on the channel propagation loss.

One of the main difficulties that we face in our analysis is the presence of fading that makes the network connectivity change from time to time. Our approach is to consider the network as a sequence of random graphs, each corresponding to a given time slot and defined by the set of links that can support a given information rate in that slot. We then consider the problem of navigating through this sequence of random graphs using only local knowledge at each node of the graph topology. We then use some graph properties that arise with high probability as the network size grows, to derive the corresponding throughput scaling laws for the high-priority traffic stream.

We now want to say a few words on the related literature. On the one hand, our work is reminiscent of that of navigation in small-world graphs and long-range percolation models. Typically, in these models, the network links are dynamically added at random to each node visited during the navigation process and the objective is to reach a destination node with the fewest number of hops possible (see Kleinberg 2000; Sharma & Mazumdar 2005; Franceschetti & Meester 2006; Ganesh & Draief 2006). On the other hand, our wireless communication context is very different from these works. More directly related are the works that characterize the trade-off between throughput and delay in wireless networks. Most of these were inspired by the results in Grossglauser & Tse (2002) and are concerned with the mobility of the nodes in the network (see Neely & Modiano 2005; Gamal *et al*. 2006*a*,*b*; Sharma *et al*. 2006; Ying *et al*. 2007). Furthermore, they all consider *dense* networks, in which a growing number of nodes are distributed over a fixed area and there is no notion of priority traffic or fading. In the present work, we address the problem of priority traffic when the channel is subject to random fading, and focus on *extended* networks where a fixed density of nodes is placed over a growing area and the nodes do not move. We remark that even if the nodes are fixed, fading can still arise owing to mobile objects in the environment. A similar problem has been analysed in Gelenbe (2007), where the average packet travel time in a wireless network is computed for a model that includes the effect of packet losses and subsequent retransmissions. A significant difference between Gelenbe (2007) and our work is that while the former considers the case where packet size and hop length are fixed, we consider a model where smaller packets can be transmitted over longer hops and hence delay can be reduced at the cost of lower transmission rate.

For ease of exposition, we will first analyse the case in which nodes are regularly placed on a grid. The case in which the nodes are randomly distributed in space according to a Poisson point process is amenable to a similar analysis and is addressed at the end of the paper.

The remainder of the paper is organized as follows. In §2, we introduce our network model. We illustrate the problem and define some notation in §3. The main results are presented and discussed in §4. Section 5 contains all proofs. The Poisson network model is discussed in §6. Finally, in §7 we draw conclusions.

## 2. Network model

Consider an *n*×*n* grid, with nodes at . Define the distance between any two nodes *a, b* as the Manhattan distance . Assume that time is divided into slots of unit duration and nodes communicate over a wireless channel of unit bandwidth. For medium access, consider a decentralized strategy where in each slot every node in the network independently and with probability *p* decides to transmit a packet to its intended destination. All nodes transmit at power *P*. If node *i* transmits to node *j* in slot *v*, the instantaneous signal to interference plus noise ratio (SINR) at *j* is given bywhere is the path loss between *i* and *j*; *N* is the thermal noise power; is the interference at node *j* in slot *v*; and *h*(*i*, *j*)^{v} is the (random) fading coefficient between nodes *i* and *j* in slot *v*. We consider a Rayleigh fading model such that in any time slot *v*, the probability density function (pdf) of *h*(*i*, *j*)^{v} is given byThe fading coefficients are assumed to be independent across both space and time. This means that in every slot *v*, *h*(*i*, *j*)^{v} and *h*(*k*, *l*)^{v} are independent for all *i*≠*k* or *j*≠*l*, and for all *i* and *j*, *h*(*i*, *j*)^{v} remains constant for a certain number of time slots, called the coherence time of the channel, and then changes in an independent fashion. The following two cases are considered.

Coherence time=1 slot. This is the

*fast-fading*scenario.Coherence time≫1 slot. This is the

*slow-fading*scenario.

We now describe how information is communicated across the network. If a source *s* wants to transmit a message to a target *t*, it does so by using a multi-hop scheme. The message is divided into packets, all of the same (finite) size and in each slot a node can transmit a single packet to a chosen destination. The coding is point to point, i.e. in any slot a sender transmits information to only one receiver, and similarly any receiver while decoding messages from a sender considers all other signals as noise. The transmission of a packet from a node *i* to *j* in a slot *v* is successful if and only if the number of information bits in the packet is less than , where *R*(.) denotes the maximum number of bits that two nodes can directly communicate to each other in a slot of unit duration, for a given SINR. We assume that *R*(.) is an increasing continuous function. Its precise form may depend on the specific coding–decoding strategy, modulation and bit error rate requirement. For example, if the slot duration is long enough, there exist codes for transmission over the additive white Gaussian noise channel, which perform very close to capacity and *R*(SINR) is of the form log(1+SINR). Further, we assume that the packet size is kept constant across transmissions and the relays only forward the packets on links that can support the required rate, i.e. the SINR at the corresponding receiver is high enough.

Next, we discuss how nodes decide their next hops while routing packets from the source to the target. We assume that all nodes are aware of the underlying grid structure of the network. Hence, the routing schemes that we study will be geographical in nature. Further, we restrict our attention to *decentralized* schemes. We define a decentralized scheme as one where any node, when it gets the message, decides its next hop only on the basis of *local* information, namely the channel strength to other nodes in the network and the position of the target *t*. In the schemes that we propose, it is assumed that this kind of local channel-state information is available to each node and explicitly take into account the time required by a node to find a suitable relay.

## 3. Problem statement

Randomly pick a source *s* and a target *t* among the nodes in the grid. Assume that the source generates a traffic stream that is delay sensitive and hence is given priority over the packets of other traffic in the network. More precisely, we assume that at any intermediate node, a queued packet of this high-priority stream is scheduled for transmission at least once in every slot, where is some constant. Note that this model differs from a relay network as described in Dousse *et al*. (2006), where all nodes cooperate to facilitate communication between only a single source and destination. In our case, other source–destination pairs (of lower priority) may also simultaneously communicate and potentially cause interference to the high-priority stream (figure 1). Similarly, we do not consider schemes that flood the network with packets of the high-priority stream since it adversely affects the communication of other data streams in the network.

Next, we define the throughput and delay for any routing scheme in the above setting. Consider a given routing scheme *Π*, used to convey the high-priority data from *s* to *t* in a grid of size *n*×*n*.

Denote the (random) number of bits successfully transferred by *Π* from *s* to *t* in *M* slots by . Then, scheme *Π* is said to achieve a throughput ifThe average packet delay for scheme *Π* is denoted by . This is measured by the average number of time slots that a packet takes to reach the destination after it leaves the source. Since each hop requires one time slot, this includes the number of hops that the packet makes before it reaches the destination and the number of time slots it is queued at intermediate nodes. Accordingly, denoting the (random) delay of packet *j* by , we defineIn this work, we focus on the scaling limit of the above quantities as the grid size *n* increases. We now present our main results and discuss them briefly.

## 4. Main results

*In both the fast- and slow-fading scenarios, for any* 0<*γ*<1 *and n large enough, the achievable throughput of any decentralized multi-hop scheme Π with average packet delay* *is bounded by**where K*_{1} *is a constant and α is the path loss exponent.*

*In both the fast- and slow-fading scenarios, for any* 0<*γ*<1 *and n large enough, there exists a decentralized scheme* *with average packet delay* *and achievable throughput**where K*_{2} *and K*_{3} *are constants and α is the path loss exponent*.

While the upper bound in theorem 4.1 holds for any decentralized multi-hop scheme with sub-linear average packet delay, the lower bound in theorem 4.2 is shown constructively by presenting a specific routing scheme that achieves the bound using only local channel-state information. The upper and lower bounds are almost tight, as they differ only by a logarithmic factor in the argument of the *R*(.) function.

In the sequel, we prove the above results. First, note that the results are intuitive: the average distance between the source and the target is of the order of *n* and if we cover it using *H* hops, then the delay will be at least *H* time slots and the average hop length along the path will be of the order of *n*/*H*. Owing to the path loss, the received signal power at each hop will be of the order of (*n*/*H*)^{−α}. A bound on the throughput of the type *R*((*n*/*H*)^{−α}) then follows. Despite the simplicity of this ‘back of the envelope’ calculation, we need quite a bit of work to make it rigorous. First, in addition to the path loss, we have to account for both the interference from other nodes in the network and for the random fading process. Second, in the computation of the delay, we have to consider not only the number of hops that the packet takes to reach its destination, but also the (random) amount of time spent in the queues at the intermediate nodes, and this time again depends on the fading process. Finally, in the case of theorem 4.2, we have to come up with a constructive strategy that discovers the route to the target using only local channel-state information at each node.

To overcome the above technical difficulties, we proceed as follows. We characterize the fading network in terms of a time sequence of random graphs, whose topology depends on the channel conditions. We compute bounds on the probability of existence of edges in these graphs and then use some of their structural properties to derive upper and lower bounds on the achievable throughput for any given delay constraint.

## 5. Throughput–delay trade-off

### (a) Network as a random graph

In this section, we model the fading network as a sequence of random graphs. For any *β*, let be the indicator random variable corresponding to the event that in slot *v*, node *i* can successfully communicate a packet of size *R*(*β*) bits to node *j*, i.e. . For any given *β*, consider the sequence of random graphs {*G*^{v}}, where for each *v*, the graph *G*^{v} is constructed with the nodes of the network as vertices and with edges between all *i, j* for which . Thus, is the indicator random variable for whether the edge between *i* and *j* is present in *G*^{v}. In the sequel, we denote by to keep the notation simple. We have,(5.1)where(5.2) is the indicator random variable for whether node *k* transmits in slot *v* and has a Bernoulli distribution with parameter *p*.

It is important to note at this point that the edges of *G*^{v} are not independent. To take care of these unwanted dependencies, starting from *G*^{v} we construct two other graphs in which the states of the edges are independent, and which dominate and are dominated, respectively, by the edges of the original graph *G*^{v}. We will then use these two graphs to derive bounds on our quantities of interest, namely the throughput and the delay.

We start by evaluating some bounds on the probability in (5.1). An upper bound trivially follows by substituting , yielding(5.3)On the other hand, we can find a corresponding lower bound by bounding the interference from above. Note that any node *j* in the grid has at most 4*a* other nodes at (Manhattan) distance *a* from itself, for all . To upper bound the interference, add fictitious nodes to the network so that for each *a*, *j* has *exactly* 4*a* nodes at distance *a*. Denote these nodes by and the corresponding fading coefficients to node *j* in slot *v* by . For fictitious nodes, we generate fading coefficients independently at random, according to the same distribution as the coefficients for the real nodes. We consider the case when all the nodes (real and fictitious) interfere with the communication between *i* and *j* in slot *v*. It then follows from (5.2) that(5.4)Substituting (5.4) into (5.1), we have(5.5)where(5.6)The derivation of (5.5) can be found in appendix A*a*.

Thus, we have computed upper and lower bounds on the probability of existence of edges in the random graph *G*^{v} corresponding to the fading network. For each *v*, we now construct two other graphs and with the same set of vertices, but with edges drawn independently with probability corresponding to the upper and lower bounds derived in (5.3) and (5.5), respectively. It is clear that while edges in *G*^{v} are not independent, *G*^{v} is stochastically dominated by the graph and dominates the graph , in both of which the edges are indeed independent. It follows that if we can find a path in then we can also find it in {*G*^{v}}, while if a path cannot be found by any decentralized algorithm in then it cannot be found in {*G*^{v}}.

Since, in order to transport a packet containing *R*(*β*) bits of information across the network, one needs to discover paths between the source and the destination in {*G*^{v}}, we can now exploit the independent structure of and to find bounds on the probability of existence of such paths and on the corresponding route discovery time. We begin by evaluating an upper bound on the achievable throughput for any given delay constraint. The upper bound holds for both slow and fast fading. Then, we analyse the rate-delay curves for specific schemes under the two fading scenarios and discuss how their performance compares with the upper bound.

### (b) Upper bound on throughput: theorem 4.1

Consider a decentralized scheme *Π* that routes packets from a randomly chosen source *s* to a randomly chosen target *t*. For a certain average delay constraint *D*(*n*), where *D*(*n*)=*O*(*n*^{γ}) for some 0<*γ*<1, assume that (*T*(*n*), *D*(*n*)) is achievable by scheme *Π*, i.e. *Π* achieves throughput *T*(*n*) with average packet delay . In the sequel, we denote *D*(*n*) by *D* for ease of exposition. We reason by contradiction and assume that(5.7)where *λ*_{γ} is a positive constant less than one (whose precise value will be specified later).

Note that in our model we have assumed that all source packets are required to be of the same size and the source can transmit at most one packet in a slot (assumed to be of unit duration). Hence, if a throughput of *T*(*n*) is achievable, then each source packet must contain at least *T*(*n*) bits. It then follows from (5.7) and the definition of the function *R*(.) that any intermediate node can relay packets successfully to only those receivers at which the instantaneous SINR is greater than or equal to the argument of the function *R*(.) in (5.7).

Consider a packet *j* and say it leaves the source in slot *v*_{0}. The packet is relayed from node to node until it finally reaches the target. Denote the slot in which the packet makes its *k*th hop by *v*_{k}. We denote by the event that1Let the packet be at node *i* at the beginning of slot *v*_{k}. Now, node *i* has at most 4*a* other nodes at distance *a* from itself. Then, by (5.3) withand the union bound, we have that(5.8)where is a constant. The proof of the last inequality can be found in appendix A. Further, note that (5.8) holds for all *k*≥1. Now, consider the event *E* defined as follows:By (5.8) and the union bound, we have(5.9)Since *D* is *O*(*n*^{γ}), we have *D*≤*Mn*^{γ} for *n* large enough, where *M* is some positive constant. Further, let . Using the value of *λ*_{γ} to evaluate *K*_{γ} and then substituting it in (5.9), we have that for *n* large enough,Next, let *F* denote the event that the randomly chosen source and target are at least a distance of *n*/4 apart. It is easy to verify that Pr(*F*)≥1/2 and thus that , where *E*^{c} denotes the complement of the event *E*. The maximum distance that can be covered in 4*D* hops if the event *E* does not occur is . Thus, denoting the number of hops needed by scheme *Π* to successfully carry a packet *j* from source *s* to target *t* as , we have that(5.10)Next, we consider the average packet delay for scheme *Π*. Denoting the delay of packet *j* by , we havewhere (*a*) is from the definition of ; (*b*) follows from the fact that each packet spends at least one time slot at every hop and hence the corresponding delay is at least as large as the number of hops; (*c*) from Fatou's lemma [Resnick 2001, corollary 5.3.2]; and (*d*) from (5.10). Thus, we have a contradiction since we started with the assumption that . The proof is now complete.

Finally, we remark that the above analysis holds for both the fast- and slow-fading scenarios.

Next, we analyse the rate-delay trade-off for particular schemes and compare them to the result derived in theorem 4.1. Here, we consider the fast- and slow-fading cases separately.

### (c) Lower bound on throughput: theorem 4.2

In this section, we consider two schemes, and , to route packets of the high-priority data from the source *s* to the target *t*, in both the fast- and slow-fading scenarios, respectively. We will show that the throughput for these schemes is almost order optimal (up to a logarithmic factor in the argument of the *R*(.) function), for any average packet delay constraint.

Consider a certain average delay constraint *D*, where *D*=*O*(*n*^{γ}) for some 0<*γ*<1. Perform a tessellation of the *n*×*n* box into square cells of side *n*/*λD*, where *λ* is a normalizing constant. For an illustration of this, see figure 2. The straight line joining *s* and *t* passes through at most *O*(*D*) cells. Hence, for any scheme that routes packets by forwarding them from cell to cell along this line, the number of hops that a packet takes before reaching the target is *O*(*D*). However, since the links in the network are susceptible to fading and we are only interested in decentralized schemes, route discovery causes further delay. In the sequel, we describe schemes that can deliver data from *s* to *t* such that the average packet delay is bounded by *D* and then evaluate the corresponding throughput.

Under both schemes, and , the source *s* generates packets according to a Bernoulli process, such that once in every slot, a packet of size bits is created independently and with probability *σ*. The packets can be forwarded successfully only on links for which the SINR at the receiver is greater than (*λD*/*n*)^{α}. Further, since the traffic stream from *s* to *t* is of higher priority, at every relay node, a queued packet of this stream will be scheduled for transmission at least once in every slot, where is some constant. Here, we make the additional assumption that the nodes in the network have infinite buffer capacity and so no packets are dropped. Next, we describe how packets are routed from the source *s* to the target *t* under the two fading scenarios.

#### (i) Fast fading

Let the number of cells that the straight line joining *s* and *t* passes through be *L*. Denote this sequence of cells by . Now, suppose a node *r*_{i} in *S*_{i} has a packet of the high-priority stream and needs to forward it. It *arbitrarily* chooses a node in *S*_{i+1}, say *r*_{i+1}. Node *r*_{i} waits until the channel between the two nodes becomes strong enough, i.e. the SINR at *r*_{i+1} is greater than (*λD*/*n*)^{α}, and then forwards the packet to *r*_{i+1}. Note that since the packets contain bits of information, this condition on the SINR is necessary to ensure that the transmission is successful. Once the packet is successfully received by *r*_{i+1}, it proceeds similarly. Thus, the packet eventually reaches the target *t* (figure 2). Next, we evaluate the throughput and average packet delay for this scheme, .

Denote the sequence of nodes, which acts as relays for the packets from *s* to *t* by , where *r*_{1}=*s* and *r*_{L}=*t*. Note that *L* can be at most 2*λD* and the Manhattan distance is bounded by 4*n*/*λ**D* for all *i*∈{1,2, …, *L*−1}. Next, for any graph *G* and a pair of vertices *a* and *b*, let *E*_{a,b}(*G*) denote the event that there exists an edge between *a* and *b* in *G*. Now, consider the sequence of graphs {*G*^{v}} constructed as in §5*a* with . Then, from the definition of {*G*^{v}} for any *v*, the event is equivalent to the event that . This implies that if *r*_{i} transmits a packet of size to *r*_{i+1} in slot *v*, it will be successfully received. For each *i*, we denote the event by to keep the notation simple.

Now, the events and are not independent for any slot *v* and *i*≠*j*. Instead, we consider the graph that is stochastically dominated by *G*^{v}. Recall that has the same set of vertices but has edges drawn independently with probability corresponding to the lower bound in (5.5). Thus, we have that and are independent events for any slot *v* and for all *i*≠*j*. Further, since the fading coefficients across slots are independent, we have that and are independent events for all *i*, *j*, *v*_{1}≠*v*_{2}. As we will see next, this independence allows us to model the relay nodes as a tandem queuing network. We first describe this queuing network and state some known results. We then discuss how our network maps to such a queuing system and will characterize the delay and throughput for our scheme . Before we proceed, note that for any slot *v*, we have by (5.5) that(5.11)where (*a*) follows from the fact that .

Now, consider a discrete-time system consisting of *L* nodes in tandem, denoted by and each with unlimited buffer capacity. The packet arrival process at *q*_{1} is Bernoulli with parameter *σ*′. Further, in every slot, each node (except *q*_{L}) serves a packet with probability *μ*′, independently of all others. Such a queuing system was studied in Hsu & Burke (1976) and it was shown that all the queues are stable and a stationary distribution exists if *σ*′<*μ*′. The average queuing delay at equilibrium is then given by(5.12)Also, the arrival process for node *q*_{L} at equilibrium was shown to be identical to the arrival process at *q*_{1} and hence is Bernoulli with parameter *σ*′.

Now, by virtue of the independence between edges in the graph , the relay nodes form a queuing system similar to the one considered above. However, recall that in the network at hand, the relay nodes do not transmit in every slot since they follow a probabilistic medium access protocol (in any slot, each node transmits with probability *p*) and even when they do, it is not necessarily a packet of the stream from *s* to *t* that is scheduled for transmission. Each relay node schedules a packet of the high-priority stream at least once in every slot. By (5.11), this packet is relayed successfully to the next hop with probability at least *p*.*μ*. On the other hand, the packet arrival process at the source *s* is assumed to be such that once in every slot, a packet is generated with probability *σ*. So, to ensure that the queues are stable, we setBy substituting *μ*′=*pμ* and *σ*′=*pμ*/2 in (5.12), we have that the average time that a packet of the high-priority stream spends at any relay node is at most slots. Let . Since the number of relay nodes is at most , the average packet delay from the source *s* to the target *t* for the scheme proposed above, is bounded above by *D*.

Next, we consider the throughput for the above scheme. By the results in Hsu & Burke (1976), we have that at equilibrium the packet arrival process at target *t* is identical to the arrival process at source *s*. Since each packet contains *R*((λ*D*/*n*)^{α}) bits of information, the throughput of the scheme is at leastwhere *K*_{2} and *K*_{3} are constants and (*a*) is true since .

#### (ii) Slow fading

As in the fast-fading scenario, packets of the high-priority stream are routed cell by cell along the straight line joining *s* and *t*. Denote the sequence of cells by and suppose that a certain node *r*_{i} in *S*_{i} has a packet of the stream and needs to forward it. Since the coherence time is much larger than the slot duration, multiple nodes may have to be polled before a suitable relay can be found. Under scheme , in every slot, *r*_{i} polls a new node in *S*_{i+1} until it finds a suitable relay so that it can forward the packet successfully. Note that how this scheme differs from , in which *r*_{i} picks a node *a priori* and then waits until the channel between the two is strong enough. Note also that in the present scheme, each relay can be used for the entire coherence time, after which there is a new realization of fading coefficients and hence the process has to be repeated. Once the packet has been successfully relayed to a node in *S*_{i+1}, it proceeds in the same way until the packet reaches cell *S*_{L−1}. The packet is then forwarded to a relay inside the region *S*_{γ}, which consists of all the nodes that are within a distance *n*^{(1−γ)/2} from *t*, and then finally to the target (figure 3). In the sequel, we show that with high probability (w.h.p), at each step of the scheme , a suitable relay node is found so that the packet can be forwarded successfully to the next cell and hence the scheme can route packets from the source *s* to the target *t*. We then analyse the average packet delay and throughput for .

Consider a node in *S*_{i}, *i*∈{1, …, *L*−2}, which is searching for a suitable relay in the next cell, *S*_{i+1}. It polls a new node in each slot until it finds a relay to which it can successfully forward a packet of the stream. Note that for *n* large enough, there are nodes in the next cell since *D* is *O*(*n*^{γ}). Further, the distance to each of them is at most 4*a*. Consider the event that such a relay is found in a particular slot *v*. As in the case of fast fading, this is equivalent to the existence of an edge in the random graph *G*^{v} corresponding to an SINR threshold . For each *i*, we denote this event by . Again, we instead consider since and are independent for *i*≠*j*. Then, using the bound derived in (5.11) and denoting by *Z*_{i} the event that a suitable relay is found in *S*_{i+1}, we have(5.13)Note that the above holds for all *i*∈{1, …, *L*−2}. To keep the notation simple, we rename the constants and .

Now, once the packet is inside *S*_{L−1}, it has to find a suitable relay among the nodes in *S*_{γ}. For *n* large enough, the number of nodes in *S*_{γ} is at least . Denoting the event that a suitable relay is found in *S*_{γ} by *Z*_{γ}, we have by (5.11) that(5.14)Suppose that the packet is forwarded to a node *r*_{γ} in *S*_{γ}. The distance between *r*_{γ} and the target *t* is at most . Denote the event that there is an edge between *r*_{γ} and *t* and hence the packet can be successfully relayed to the target, by *Z*_{t}. Then, by substituting and in (5.5) and (5.6), we have that(5.15)where (*a*) follows from *D*=*O*(*n*^{γ}). Thus, the packet is routed from the source *s* to the target *t* by the scheme . The scheme fails if any of the events , *Z*_{γ} or *Z*_{t} fails. Then, we have by (5.13), (5.14) and (5.15)Since *D* is *O*(*n*^{γ}), we have that as the grid size *n*→∞ and hence we conclude that the scheme is able to successfully route packets from the source to the target w.h.p. Next, we evaluate the delay and throughput for this scheme.

As in §5*c*(i), to evaluate the average delay and throughput of our scheme, we map the network to a tandem queuing network. The mapping is identical to the one described in §5*c*(i), with the difference being that for the slow-fading scenario, each node in the queuing network corresponds to a cell in the real network rather than individual relay nodes. Packets are queued in each cell, while the next hop is being searched by polling individual nodes in the next cell. Note that the lower bound on the probability of finding a suitable relay in a slot is the same as that evaluated in (5.11) for the fast-fading scenario. Hence, for any delay *D*, the throughput achieved by scheme in the fast-fading scenario is also achievable by the scheme in the slow-fading case.

Thus, we have shown that for the slow-fading scenario, there exists a decentralized scheme with throughput and average packet delay such that w.h.p,where *K*_{2} and *K*_{3} are constants.

## 6. Poisson networks

While the analysis in §§2–5 was restricted to the case where nodes are placed on a regular grid, similar arguments can be used to prove results for the case where nodes are distributed randomly according to a Poisson point process. In this section, we briefly describe the adaptation to this case and then state the results.

Consider a network with nodes distributed according to a Poisson point process of unit intensity, over the square , so that the average number of nodes is *n*^{2}. Define the distance between two nodes *a* and *b* as the Euclidean distance . Time is divided into slots of unit duration and nodes communicate with each other over a wireless channel of unit bandwidth. For wireless medium access, we consider a time division multiple access (TDMA) scheme. Assume that the square is divided into smaller cells of size *m*×*m*, where *m* is some constant and in every time slot, only one node in each cell is allowed to transmit. Note that this is different from the probabilistic scheme used in the grid scenario and requires synchronization within the smaller cells. By employing a TDMA scheme, we limit the interference at any given node and can thus compute lower bounds for the probability that two nodes can communicate in a given slot in the same way as was done in §5*a* (figure 4).

As in the case of regular networks in §2, if a node *i* transmits to node *j* in slot *v*, the SINR at *j* is given byand the two nodes can communicate at most bits in the slot. In this section, we consider the path loss function . The rest of our model is identical to the one described in §2. As before, we randomly pick a source *s* and target *t* and assume that some delay-sensitive data need to be routed from *s* to *t* and hence is given priority over other traffic in the network. More precisely, if packets of this stream are relayed via a node *j* in some cell *S*_{j}, then among the nodes in that cell, *j* is scheduled to transmit at least once in every slot, where is some constant. Furthermore, as in §5, at every intermediate relay, a queued packet of this stream will be served at least once in every transmission. The goal is to study decentralized schemes to carry this priority traffic from *s* to *t* and to precisely characterize the throughput–delay trade-off for such schemes. The results for the Poisson case are identical to those derived in §5 and the statements of theorems 4.1 and 4.2 hold here as well.

## 7. Conclusion and future work

In this work, we derived scaling laws for decentralized schemes that route delay-sensitive data in extended Rayleigh fading networks. The object of this study was the trade-off between throughput and delay in such a network. While the main results in this paper have been proved for the case of the grid (with Manhattan distance metric), the proofs extend readily to the case of randomly placed nodes (with Euclidean distance metric). Since the grid network sufficed for studying the main focus of this paper, we discussed it in detail.

We first derived an upper bound on the throughput achievable by any decentralized scheme for any given delay constraint, and then proposed specific schemes that are almost order optimal. Future work includes evaluating similar bounds for more general scenarios such as networks with multiple source–destination pairs and uniform or non-uniform traffic requirements.

## Footnotes

One contribution of 6 to a Special Feature ‘Stochastic networks: from theory to practice’.

↵Note that

*n*/32*D*may not be an integer. The result does not change if we explicitly take this into account. The same is true for all other proofs in this paper.- Received November 20, 2007.
- Accepted April 9, 2008.

- © 2008 The Royal Society