8.4 Heuristic Candidate Selection Algorithm

A straightforward way to get the optimal Rj and to maximize the OEOT is to try all the ordered subsets of for each Rj, which runs in O(keN!) time, where k is the number of different rates, e is the base of natural logarithm, and N is the largest number of neighbors at all rates. It is, however, not feasible when N is large. In this section, we propose a heuristic algorithm to obtain a solution approaching the optimum.

As there is a finite number of transmission rates, a natural approach is to decompose the optimization problem into two parts. First, we find the optimal solution for each Rj; then, we pick the maximum one among them. So we only need to discuss how to find the solution approaching the optimum for a given rate, Rj, and the corresponding available next-hop neighbor set, . Lemma 8.1 guides us to design the heuristic algorithm.

Lemma 8.1 For given Rj and , define as one feasible candidate set that achieves the maximum OEOT by selecting r nodes, then r (), , s.t. .

Proof. We prove this Lemma by contradiction. Assume r (), we could find a feasible , s.t. . Then from that , we can obtain a new ordered set by substituting the lowest-priority candidate in as the node in . According to Equation (8.5) and from the fact that achieves the maximum OEOT by selecting 1 node, we can derive that the OEOT of the new set is larger than that of the . It is a contradiction, so the assumption is false, then the Lemma is true.

Lemma 8.1 basically indicates that, for a given Rj and , the candidate achieving the maximum OEOT by selecting 1 node from is contained in the candidate set achieving the maximum OEOT by selecting more nodes from .

Actually, the numerator of OEOT is the EPA defined in Zeng et al. (2007). The EPA has three nice properties: priority rule, containing property and concavity, as we demonstrated in Chapter 2.

The concavity property indicates that involving more forwarding candidates will increase EPA but the gained EPA becomes marginal when we keep doing so. It was shown in Zeng et al. (2007) that the maximum EPA hardly increases at all when the number of forwarding candidates is larger than four. Furthermore, involving more forwarding candidates may increase the probability of false positives, that is, lower priority candidates are more likely to be falsely suppressed by other transmissions in the network. So in our algorithm design, we set a maximum allowable forwarding candidate number, rmax.

Now we examine the denominator of the OEOT in Equation (8.5). For the compressed slotted ACK mechanism, the denominator can be further simplified as , where Ts(j) is the delay at the sender side when the data packet is transmitted at rate Rj. The third part of this summation is the expected time introduced by candidate coordination, which is upper bounded by r · TSIFS. As TSIFS Ts(j) + TACK and r is a small number, the denominator can be seen as a constant at a fixed rate Rj. So maximizing the OEOT is equivalent to maximizing its numerator, EPA.

Therefore, according to the three properties and the analysis above, we propose a heuristic greedy algorithm, which finds the transmission rate and the corresponding forwarding candidates approaching the maximum OEOT. This heuristic algorithm FindMOEOT is described in Algorithm 8.1, where the input is the multirates, Rj's, the corresponding 's and the maximum allowable forwarding candidate number rmax, and the output is the selected rate R* and forwarding candidate set . For each rate Rj, this algorithm first finds the set with one candidate that maximizes the OEOT, then it augments the current by one more candidate in each iteration (line 6). Whenever adding a new candidate, it calculates the OEOT (line 7), then updates the when finding a new set achieving higher OEOT than the existing one. Note that, according to Lemma 8.1, when the final returned set contains no more than 2 nodes, it is indeed the global optimum. Otherwise, it is an approximate optimal solution. An interesting finding is that this algorithm almost certainly returns the global optimal solution even when the returned set contains more than two candidates.

Algorithm 8.1 FindMOEOT('s, Rj's, rmax)

 1: R* ← 0;  ← ∅; OEOT* ← 0;

 2: for each  do

 3:      ← ∅; OEOTm ← 0;  ←  − ;

 4:     while ( ≠ ∅ && || < rmax) do

 5:        for each node sn ∈  do

 6:             ←  Insert sn into  according to Relay Priority Rule;

 7:            Get OEOT on  according to Equation (8.5);

 8:            if (OEOT > OEOTm) then
 9:               OEOTm ← OEOT;  ← 

10:           end if
11:       end for
12:         ←  − ;

13:     end while
14:     if (OEOTm > OEOT*) then
15:        R* ← Rj;  ← ; EOT* ← EOTm;

16:     end if
17: end for
18: return R*, );