8.4 Heuristic Candidate Selection Algorithm

A straightforward way to get the optimal Rj and images/c08_I0040.gif to maximize the OEOT is to try all the ordered subsets of images/c08_I0041.gif 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, images/c08_I0042.gif. Lemma 8.1 guides us to design the heuristic algorithm.


Lemma 8.1 For given Rj and images/c08_I0043.gif, define images/c08_I0044.gif as one feasible candidate set that achieves the maximum OEOT by selecting ...

Get Multihop Wireless Networks: Opportunistic Routing now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.