8.2 Impact of Transmission Rate and Forwarding Strategy on OR Performance
In this section, we discuss the factors that affect the one-hop performance in terms of throughput and delay of OR. These factors include rate and forwarding strategy, which further includes candidate selection, prioritization and coordination.
The impacts of transmission rate on the performance of opportunistic routing are twofold. On the one hand, different rates achieve different transmission ranges, which lead to different neighborhood diversity. Explicitly, high-rate causes short transmission range, then in one hop, there are few neighbors around the sender, which presents low neighborhood diversity. Low-rate is likely to have long transmission range, therefore achieves high neighborhood diversity. So from the diversity point of view, low rate may be better. On the other hand, although low rate brings the benefit of larger one-hop distance, which results in higher neighborhood diversity and fewer hop counts to reach the destination, it is still possible to achieve a low effective end-to-end throughput or high delay because it needs more time to transmit a packet at lower rate. So it is nontrivial to decide which rate is indeed better.
Besides the inherent rate-distance, rate-diversity and rate-hop tradeoffs, which affect the performance of opportunistic routing, the forwarding strategy will also have an impact on the performance. That is, for a given transmission rate, different candidate forwarding sets, relay priority assignments, and candidate coordinations will all affect the OR performance.
In the following subsections, we will examine the impact of transmission rate and forwarding strategy on the one-hop performance of opportunistic routing, which leads us to the design of an efficient local rate adaptation and candidate selection scheme. First we will analyze the one-hop packet forwarding time introduced by opportunistic routing.
8.2.1 One-Hop Packet Forwarding Time of Opportunistic Routing
We define the one-hop packet forwarding time cost by the ith candidate as the period from the time when the sender is going to transmit the packet to the time when the ith candidate becomes the actual forwarder. Although the one-hop packet forwarding time varies for different MAC protocols, for any protocol, it can be divided into two parts. One part is introduced from the sender and the other part is introduced from the candidate coordination, which are defined as follows:
- Ts: the sender delay, which can be further divided into three parts: channel contention delay (Tc), data transmission time (Td) and propagation delay (Tp):
For a contention-based MAC protocol (like 802.11), Tc is the time needed for the sender to acquire the channel before it transmits the data packet, which includes the backoff time and Distributed Interframe Space (DIFS). Td is equal to protocol header transmission time (Th) plus data payload transmission time (Tpl), which is
where Th is determined by physical layer preamble and MAC header transmitting time, and Tpl is decided by the data payload length Lpl and the data transmission rate. The payload may be transmitted at different rates.
Tp is the time for the signal propagating from the sender to the candidates, which can be ignored when electromagnetic wave is transmitted in the air.
- Tf(i): the ith forwarding candidate coordination delay which is the time needed for the ith candidate to acknowledge the sender and suppress other potential forwarders. Note that Tf(i) is an increasing function of i, since the lower priority forwarding candidates always need to wait and confirm that no higher priority candidates have relayed the packet before it takes its turn to relay the packet. For the protocol we introduced in Section 8.1, Tf(i) = i × TSIFS + TACK, where TACK is the ACK transmission time.
Thus, the total medium time needed for a packet forwarding from the sender to the ith forwarding candidate is
8.2.2 Impact of Transmission Rate
We examine the impact of transmission rate on the one-hop throughput of OR by using two examples. In one example transmission at higher rate is better, while in the other example lower rate achieves higher throughput. The one-hop throughput is defined as bit-meters successfully delivered per second with unit bmps. The one-hop delay per bit-meter is the inverse of the throughput. So higher throughput implies lower delay in this context.
Assume the data payload Lpl = 1000 bytes, TSIFS = 10 μs, TACK = 192 μs, Th = 200 μs, and the sender delay only includes the data transmission time (Td). According to Equations (8.2), (8.3), (8.4) and the MAC protocol we discussed in Section 8.1, 
. In Figure 8.2, assume at each rate, the neighbor closer to the destination is assigned higher relay priority. Suppose S sends out N packets. Then when Rj = 11mbps, there are Lpl(300 · 0.7N + 200 · 0.95 · 0.3N) = 2.136N megabit-meters are delivered, and the corresponding total packet forwarding time is (t1 · 0.7N + t2 · 0.3N) = 1132.27N μs. So the one-hop throughput is 1.886G bmps. Similarly, the one-hop throughput at 5.5 mbps is 1.651G bmps, which is smaller than the throughput at 11 mbps. That is, in this example, although lower rate introduces more spacial diversity (more neighbors), this benefit does not make up the cost on the longer medium time. Now let's assume the neighbor s3 is removed from Figure 8.2 for each rate. Then the one-hop throughput is 1.60G bmps and 1.49G bmps at 5.5 mbps and 11 mbps, respectively. So transmitting at lower rate is better than higher rate in this case, because the extra spacial diversity brought by lower rate does help to improve the packet advancement but only introduce moderate extra packet forwarding time.
Figure 8.2 Different transmission rates result in different next-hop neighbor sets. Reproduced by permission of © 2009 IEEE.
8.2.3 Impact of Forwarding Strategy
We have seen that multirate capability has an impact on throughput and delay. Other than this factor, for any given rate, different candidate prioritization also results in different throughput and delay in opportunistic routing. Still using the example in Figure 8.2 at a rate of 5.5 mbps, if we assign s2 the highest priority, then s1, then s3, the one-hop throughput is 1.306G bmps, which is lower than that achieved by assigning higher priority to the candidate closer to the destination. Actually, it has been proved in (Zeng et al. 2007) that giving candidates closer to the destination higher priorities achieves maximum expected packet advancement (EPA).
8.2.4 Impact of Candidate Coordination
The coordination delay is another key factor affecting the packet forwarding time and one-hop throughput. When this delay is much larger than the sender delay, then it would be better to retransmit the packet instead of waiting for other forwarding candidates to relay the packet in order to save the packet forwarding time. When this delay is negligible, we should involve all the available next-hop neighbors into opportunistic forwarding because any extra candidates would help to improve the relay reliability but without introducing any extra delay. We should also give candidates closer to the destination higher relay priorities, since larger advancement candidates should always try first in order to maximize the EPA. If they fail to relay the packet, the lower-priority candidates could instantaneously relay the correctly received packet without having to wait. The coordination delay therefore has a great impact on throughput. Since we use the compressed slotted acknowledgement, which introduces a small coordination delay among candidates, it would be better to give candidates closer to the destination higher relay priorities.
In the compressed slotted acknowledgement mechanism, ACK plays two roles: one is to acknowledge the sender of data reception, the other is to suppress other candidates from forwarding duplicated packets. We discuss the reliability of this mechanism according to these two ACK roles. Firstly, following the collision-avoidance rule, each node should sense the channel to be clear for at least DIFS before transmission. Since the ith-priority candidate broadcasts the ACK with a short delay (i × TSIFS, which is usually shorter than DIFS in our scheme) after successful packet reception, the ACK is unlikely to collide with other transmissions at the sender side. The empirical results in (Sang et al. 2007) also confirm that ACK can be received by the sender with high probability. Furthermore, since the ACK is transmitted at the basic rate (1 mbps), the ACK link from the candidate to the sender should be more reliable than the data link from the sender to the candidate. So when the candidate correctly receives the data packet from the sender, the ACK can usually be correctly received by the sender with high probability. Secondly, since all the forwarding candidates are in the data transmission range of the sender, the longest possible distance between any two candidates is twice that of the data transmission range. Typically, carrier sensing range is around double the data transmission range. So any two forwarding candidates will be in the carrier sensing range of each other. Then lower prioritized candidates should be able to detect a transmission appearing in the channel if a higher prioritized candidate does send out an ACK. A false positive could occur when a lower priority candidate senses a transmission emergence but it is from other transmission source. In this case, the lower priority candidate would drop its received packet. If all the lower priority candidates that have received the packet correctly believe there is a higher priority candidate that has received the packet but actually there is not, no ACK would be sent back to the sender, then the sender would retransmit the packet. However, the probability of other transmissions emerging in the short coordination period (multiple SIFS) and suppressing all the potential forwarding candidates should be relatively low.