1.6 System Model and Assumptions

We consider a multi hop wireless network with N nodes arbitrarily located on a plane. Each node ni (1 ≤ i ≤ N) can transmit a packet at J different rates R1, R2, …, RJ. We say there is a usable directed link lij from node ni to nj, when the packet reception ratio (PRR), denoted as pij, from ni to nj is larger than a non-negligible positive threshold ptd. The PRR we consider is an average value of the link quality in a long timescale (e.g. in tens of seconds). There exist several link-quality measurement mechanisms (Couto et al. 2003; Kim and Shin 2006) to obtain the PRR on each link. We assume that there is no power control scheme and the PRR on each link for each rate is given. We define the effective transmission range Lm at rate Rm (1 ≤ m ≤ J) as the sender-receiver distance at which the PRR equals ptd.

The basic module of opportunistic routing is illustrated in Figure 1.1. Assume node ni is forwarding a packet to a remote sink/destination nd. We denote the set of nodes within the effective transmission range of node ni as the neighboring node set (e.g., all the five nodes around ni in Figure 1.1). Note that, for different transmission rates, the corresponding effective transmission ranges are different, then we have different neighboring node sets of node ni, and the PRR on the same link lij may be different at different rates. We define the set (e.g., in Figure 1.1) as forwarding candidate set, which is a subset of and includes r nodes selected to be involved in the local opportunistic forwarding based on a particular selection strategy. is an ordered set, where the order of the elements corresponds to their priority in relaying a received packet.

Figure 1.1 Node ni is forwarding a packet to a remote destination nd with a forwarding candidate set at some transmission rate. Reproduced by permission of © 2008 IEEE.

For GOR, we assume each node is aware of the location information1 of itself, its one-hop neighbors and the destination. Given a transmitter ni, one of its forwarding candidates , and the destination nd, we define the packet advancement in Equation (1.1), which is the Euclidean distance between the transmitter and destination subtracting the Euclidean distance between the candidate and the destination. This definition represents the advancement in distance made toward the destination when forwards the packet sent by ni.

1.1

For GOR, because we are only interested in the neighbors that give positive advancement to the destination, we denote the set of those neighbors as , the available next-hop node set.

Opportunistic routing works by the sender node ns forwarding the packet to the nodes in its forwarding candidate set . One of the candidate nodes continues the forwarding based on their relay priorities–if the first node in the set has received the packet successfully it forwards the packet towards the destination while all other nodes suppress duplicate forwarding. Otherwise, the second node in the set is arranged to forward the packet if it has received the packet correctly. Otherwise the third node, the fourth node, and so forth. A forwarding candidate will forward the message only when all the nodes with higher priorities fail to do so. When no forwarding candidate has successfully received the packet, the sender will retransmit the packet if retransmission is enabled. The sender will drop the packet when the number of retransmissions exceeds the limit. The forwarding reiterates until the packet is delivered to the destination. Several MAC protocols have been proposed in Biswas and Morris (2005); Fussler et al. (2003); Zorzi and Rao (2003a); Zubow et al. (2007) to coordinate the forwarding candidates and ensure the relay priority among them. In this book, for all the analysis, we assume the relay priority can be perfectly realized. So there is no duplicate packet forwarding due to imperfect candidate coordination. We will show in Chapter 6 that it is a realistic assumption when our proposed candidate coordination scheme is used.

For capacity analysis in Chapters 4 and 5, we assume that packet transmissions at the individual nodes can be finely controlled and carefully scheduled by an omniscient and omnipotent central entity. So here we do not concern ourselves with issues such as MAC contention or coordination overhead that may be unavoidable in a distributed network. This is a very commonly used assumption for such theoretical studies (Jain et al. 2003; Zhai and Fang 2006a).

1 The node location information can be obtained by prior configuration, by the Global Positioning System (GPS) receiver, or through some sensor self-configuring localization mechanisms as in Bulusu et al. (2000); Savvides et al. (2001).