4.3 Rate and Candidate Selection Schemes

How to select the transmission rates and forwarding strategy for each node efficiently so that the network capacity can be globally optimized is still an open research issue. We have shown the example in Figure 4.3 that nodes transmitting at a lower rate may lead to a higher end-to-end throughput than when nodes are transmitting at a higher rate. Then, what criteria should node a follow to select transmission rate, forwarding candidates and candidate priority to approach the capacity? It is nontrivial to answer this question. Towards the development of distributed and localized OR protocol that maximize the capacity, in this section, we propose two rate and candidate selection schemes, one is enlightened by least-cost opportunistic routing (LCOR) as proposed in Dubois-Ferriere et al. (2007), and the other is inspired by geographic opportunistic routing (GOR) (Fussler et al. 2003; Zeng et al. 2007a,b,c; Zorzi and Rao 2003).

4.3.1 Least Medium Time Opportunistic Routing

In traditional routing, the medium time metric (MTM) (Awerbuch et al. 2006) and expected transmission time (ETT) (Draves et al. 2004) have shown to be good metrics to achieve high throughput. For OR, we define the opportunistic ETT (OETT) as the expected transmission time to send a packet from ni to any node in its forwarding candidate set .

4.11

where Lpkt is the packet length, Ri is the data transmission rate at node ni, and is the probability of at least one candidate in correctly receiving the packet sent by ni:

4.12

Note that this metric actually generalizes the unicast ETT, that is, for , the OETT reduces to the unicast ETT.

Denote by Di the expected medium time (EMT) to reach the destination nd from a node ni. Assume that ni's forwarding candidates are prioritized according to their expected medium time , such that . Then we define the remaining EMT to the destination nd when node ni chooses the forwarding candidate set as follows:

4.13

where .

is the probability of candidate receiving the packet correctly but all the higher priority candidates do not. That is, it is the probability of becoming the actual forwarder. So the summation is the expected remaining medium time needed for a packet to travel to the destination for one transmission from node ni. is the expected transmission count ni needs to make in order to deliver the packet to one of its forwarding candidates.

Note that like the OETT, the EMT generalizes the single-path case: when , it simply becomes the delay from the next hop to the destination. We should also notice that any two different transmitters, ni and nj, even if , may have different EMTs, since this EMT is affected by the delivery probabilities from the transmitter to its each forwarding candidate. In other words, the remaining EMT from a forwarding candidate set to the destination depends not only on the candidate set itself, but also on the predecessor node of this set.

We now define the least EMT of node ni to the destination nd in a multirate scenario:

4.14

where is the neighboring node set of node ni when ni transmits at rate Rj, is the corresponding forwarding candidate set.

Equation (4.14) represents the steady state of the least medium time OR (LMTOR), that selects the forwarding candidates and transmission rate for each node to achieve the minimum end-to-end EMT.

Multirate Bellman–Ford Based Algorithm

A distributed algorithm running like Bellman–Ford can solve the LMTOR problem. That is, in one iteration, each node ni updates its value , where k is the iteration index. This is the estimated EMT from ni to the destination at the kth iteration; it converges toward Di. , . One iteration step consists of updating the estimated EMT to the destination from each node:

4.15

where is the remaining EMT computed using the costs () from the previous iteration.

At each step, according to Lemma 2.6 described in Section 2.3.3, we do not need to enumerate all the possible to find the optimal forwarding candidate and transmission rate that achieve . For each node ni, at rate Rj, suppose there are r neighbors denoted as 1, 2,…, r and sorted as , we only need to test the candidate sets in the form of 〈1〉, 〈1, 2〉, …, 〈1, 2, …, r〉. For each rate, we select an optimal candidate set that maximizes the , then the final optimal set should be the one in the optimal sets that achieves the maximum of these maximums. The algorithm terminates when: . Like the proof in Dubois-Ferriere et al. (2007), this algorithm converges after at most N iterations, where N = |V| is the number of nodes in the network. The complexity of this algorithm is O(|V||E|log|V| + |V||E||J|).

The pseudo-code of this algorithm (Laufer et al. 2010) is presented in Algorithm 4.1, which is the extension of the single rate Bellman–Ford-based algorithm described in Section 2.3.5. The in the algorithm is the OETT defined in Equation (4.11). The is the remaining EMT defined in Equation (4.13).

Algorithm 4.1 Multirate Bellman–Ford-based Shortest Anypath Algorithm

  Input: G, nd
  for each node ni ∈ V do
    Di ← ∞
     ← ∅

    Ti ← NIL
    for j ← 1 to J do
         ← ∞

         ← ∅

    end for
  end for
  Dd ← 0
  for t ← 1 to |V| − 1 do
     for each node ni ∈ V do
        Q ← GET-NEIGHBORS(ni)
        while Q ≠ ∅ do
           nk ← EXTRACT-MIN(Q)
           for j ← 1 to J do
                ←  ∪ {nk}

               if  > Dk then

                  ← di + D 

                  ← 

                 if Di >  then

                    Di ← 

                     ← 

                    Ti ← j
                 end if
               end if
           end for
        end while
     end for
  end for

Multirate Dijkstra-Based Algorithm

The Dijkstra-based algorithm proposed in Section 2.3.4 can also be extended to the multirate case. Algorithm 4.2 presents this algorithm that is proposed in (Laufer et al. 2010).

The idea of Algorithm 4.2 is that each node ni ∈ V has an independent cost estimate when the node is transmitting at each rate Rj (1 ≤ j ≤ J). The minimum of these estimates is kept as Di, the expected medium time (cost) from this node to the destination. At each round of the while loop, the node with the minimum cost from Q is settled. At the first round, the destination node will be extracted. In the subsequent each round, suppose nk is extracted. For each ingress edge ni → nk in the edge set, for every rate Rj, if the cost is larger than the cost (Dk) from the settled node nk to the destination, node nk is added to the forwarding candidate set . The cost is then updated accordingly. If the new cost is lower than the node cost Di, Di is updated as well as the forwarding candidate set and transmission rate Ti to reflect the new minimum.

Algorithm 4.2 Multirate Bellman-Ford-Based Shortest Anypath Algorithm

  Input: G, nd
  for each node ni ∈ V do
     Di ← ∞
      ← ∅

     Ti ← NIL
     for j ← 1 to J do
         ← ∞

         ← ∅

     end for
  end for
  Dd ← 0
   ← ∅

  Q ← V
  while Q ≠ ∅ do
     nk ← EXTRACT-MIN(Q)
      ∪ nk

     for each ingress edge ni → nk do
        for j ← 1 to J do
             ←  ∪ {nk}

            if  > Dk then

                ← di + D

                ← 

               if Di >  then

                 Di ← 

                  ← 

                 Ti ← j
               end if
            end if
        end for
     end for
  end while

Although these two algorithms can find the optimal candidate set and transmission rate to minimize the expected medium time (delay) of multirate opportunistic routing, they either need to know the global network information (Dijkstra-based algorithm), or exchange cost information among node iteratively (Bellman–Ford-based algorithm). In a very large-scale network, these algorithms can still introduce a lot of overheads. We propose another local rate and candidate selection scheme by leveraging on the node's location information as in GOR. Each node only needs to know its neighborhood information and does not need to propagate any cost information. The complexity of the candidate selection procedure can be reduced to linear.

4.3.2 Per-Hop Greedy: Most Advancement per Unit Time

A local metric: Expected Advancement Rate. The location information is available to the nodes in many applications of multihop wireless networks, such as sensor networks for monitoring and tracking purposes (Zorzi and Rao 2003) and vehicular networks (Fussler et al. 2003). Geographic opportunistic routing has been proposed as an efficient routing scheme in such networks. In GOR, nodes are aware of the location of itself, its one-hop neighbors, and the destination. A packet is forwarded to neighbor nodes that are geographically closer to the destination. In Chapter 2, we proposed a local metric, expected packet advancement (EPA) for GOR to achieve efficient packet forwarding. EPA for GOR is a generalization of EPA for traditional geographic routing (Lee et al. 2005; Seada et al. 2004). It represents the expected packet advancement achieved by opportunistic routing in one transmission without considering the transmission rate. In this chapter, we extend it into a bandwidth adjusted metric, expected advancement rate (EAR), by taking into consideration various transmission rates.

We define the EAR as follows:

4.16

The physical meaning of EAR is the expected bit advancement per second towards the destination when the packet is forwarded according to the opportunistic routing procedure introduced in Section 8.1.

The definition of EAR is the rate Ri multiplying the EPA proposed in (Zeng et al. 2007b). According to the proved relay priority rule for EPA in Section 2.2.2, we have the following theorem for EAR:

Theorem 4.1 (Relay priority rule) For a given transmission rate at ni and , the maximum EAR can only be achieved by giving the candidates closer to the destination higher relay priorities.

This theorem indicates how to prioritize the forwarding candidates when a transmission rate and the forwarding candidate set are given. From the definition of EAR, it is also not difficult to find that adding more neighboring nodes with positive advancement into the existing forwarding candidate set will lead to a larger EAR. Therefore, we conclude that an OR strategy that includes all the neighboring nodes with positive advancement into the forwarding candidate set and gives candidates with larger advancement higher relay priorities will lead to the maximum EAR for a given rate.

Then a straightforward way to find the best rate is: for node ni, at each transmission rate Rm (1 ≤ m ≤ J), we calculate the largest EAR according to the above conclusion, then we pick the rate that yields the maximum EAR. This would be the local optimal transmission rate and the corresponding forwarding candidate set. Note that for a node ni, it is possible that no neighboring nodes are closer to the destination than itself. In this case we need some mechanism like face routing (Karp and Kung 2000) to contour the packet around the void. However, solving the communication voids problem is beyond the scope of this chapter.

Note that the above discussion does not take protocol overheads into consideration. As we have shown in (Zeng et al. 2007a, b, c), including as many as possible nodes might not be the optimal strategy when overheads, such as the time used to coordinate the relay contention at MAC layer, are taken into consideration. To consider the protocol overhead, the EAR can be extended to the metric EOT (expected one-hop throughput), which we will study in Chapter 8. However, in this chapter, as our goal is on studying the end-to-end throughput bound of OR, we apply EAR as the local metric, which is the upper bound of the packet advancement rate that can be made by any GOR.