O'Reilly logo

Multihop Wireless Networks: Opportunistic Routing by Ming Li, Wenjing Lou, Kai Zeng

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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 ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required