5.2 System Model and Opportunistic Routing Primer

We consider a multihop wireless network with N nodes. Each node ni (1 ≤ i ≤ N) is equipped with one or more wireless interface cards, referred to as radios in this work. Denote the number of radios in each node ni as ti (i = 1…N). Assume K orthogonal channels are available in the network without any interchannel interference. We consider the system with channel-switching capability, such that a radio can dynamically switch across different channels. We assume there is no performance gain to assigning the same channel to the different radios on the same node (i.e. we do not consider MIMO). For simplicity, we assume each node ni transmits at the same data rate Ri among all its radios and channels. However, our model can be easily extended to the multirate case. We also assume half-duplex on each radio-that is, a radio cannot transmit and receive packets at the same time. This is usually true in practice. There is a unified transmission range and interference range for the whole network. The transmission range and interference range are largely dependent on the transmission power, which is fixed in our model. Typically, the interference range is larger than the transmission range. Two nodes, ni and nj, can communicate with each other if the Euclidean distance between them is less than the transmission range and they are operated on the same channel. Due to the unreliability of the wireless links, a packet reception ratio (PRR) is associated with each transmission link. In this chapter, we assume that the link quality on each channel is independent and can be obtained by the existing measurement schemes (Aguayo et al. 2004; Kim and Shin 2006). In order to analyze the throughput bound, we assume that packet transmission/forwarding at an individual node and radio/channel allocation can be perfectly scheduled by an omniscient and omnipotent central entity. Thus, we do not concern ourselves with issues such as MAC contention or coordination overheads that may be unavoidable in a distributed network. This is a very commonly used assumption for theoretical studies (Jain et al. 2003; Zeng et al. 2008; Zhai and Fang 2006).

5.2.1 Opportunistic Routing Primer

Different from TR, OR basically runs in such a way that, for each local packet forwarding, a set of next-hop forwarding candidates are selected at the network layer and one of them is chosen as the actual relay at the MAC layer according to their instantaneous availability and reachability at the time of transmission. Using Figure 5.1 as an example, the one-hop neighbor set of a transmitter ni is , which consists of nodes that operate on the same channel as node ni and are in its transmission range. A subset of is selected as the forwarding candidate set of ni. We name as an opportunistic module.

Figure 5.1 An example of opportunistic module , where . Reproduced by permission of © 2010 IEEE.

To avoid packet duplication, only one of the forwarding candidates becomes the actual forwarder of each packet. There is a forwarding priority among these forwarding candidates to decide which should forward the packet if multiple forwarding candidates correctly receive the same packet. We use to represent the forwarding priority among the forwarding candidate, such that indicates has higher forwarding priority than .

To send a packet from the source ns to a destination nd, OR works by the source ns sending the packet to the receivers in its forwarding candidate set . One of the candidate nodes continues the forwarding based on their relay priorities. If the first-priority node in the set has received the packet successfully, it forwards the packet towards the destination while all other nodes suppress themselves from duplicate forwarding. Otherwise, the second-priority node in the set is arranged to forward the packet if it has received the packet correctly. Otherwise the third-priority node, the fourth-priority node, etc. A forwarding candidate will forward the packet only when all the other candidates with higher priorities failed to do so.

Several MAC protocols (Biswas and Morris 2005; Fussler et al. 2003; Zorzi and Rao 2003) have been proposed to ensure the relay priority among the candidates. For example, in Biswas and Morris (2005) a batch map is used to indicate the packets known to have been received by higher priority candidates, thus prohibiting the lower priority candidates from relaying duplicate copies of the packets. Only when none of the forwarding candidates has successfully received the packet will the sender retransmit the packet if retransmission is enabled. The forwarding reiterates until the packet is delivered to the destination nd.