20. E. W. Dijkstra, “A Note on Two Problems in Connexion with Graphs,” Numerische Mathemat-

ick, 1, 269“271, 1959.

21. R. Bellman, “On a Routing Problem,” Quart. Appl. Math., 16, 87“90, 1958.

22. R. W. Ford, “Algorithm 97: Shortest Path,” Communications of the ACM, 5, 345, 1962.

23. E. F. Moore, “Shortest Path through a Maze,” in Proceedings of the International Symposium

on the Theory of Switching, Part III, Harvard University, Cambridge, MA, pp. 285“292, 1959.

24. D. Burton, “On the Inverse Shortest Path Problem,” Doctoral Dissertation, Facult©s Universi-

taires Notre-Dame de la Paix de Namur, Facult© des Sciences, D©partment de Math©matique,

1993.

25. D. Goldfarb and A. Idnani, “A Numerically Stable Dual Method for Solving Strictly Convex

Quadratic Programs,” Mathematical Programming, 27, 1“33, 1983.

26. A. Faragó A. Szentesi, and B. Szviatovszki, “Inverse Optimization in High Speed Networks,” to

appear in Discrete Applied Mathematics, special issue on Combinatorial and Algorithmic As-

pects of Telecommunications.

27. CPLEX Interactive Optimizer, ILOG, Inc. http://www.ilog.com

28. V. Chvátal, Linear Programming, W.H. Freeman and Company, New York, 1983.

29. Wireless and Mobility Extensions to ns-2. Carnegie Mellon University, Monarch (Mobile Net-

working Architectures) Project. http://www.monarch.cs.cmu.edu

CHAPTER 16

ALGORITHMIC CHALLENGES

IN AD HOC NETWORKS

ANDRÁS FARAG“

In this chapter, we review a number of algorithmic problems, primarily motivated by ad

hoc networks, especially by routing protocols in these networks. We show that the amaz-

ing diversity of possible route metrics, each with its own justifiable motivation, can be in-

corporated into a unified mathematical framework. A number of unsolved algorithmic

problems are presented in connection with route metrics, as well as other path-related

problems, such as mobile paths in mobile graphs, the inverse shortest-path problem and

finding large route systems. Overall, we would like to convince the reader that ad hoc net-

working provides many interesting challenges not only for practical implementation, but

also for the more theoretical side of algorithm development and analysis.

16.1 INTRODUCTION

Ad hoc networks present a rich set of new challenges for algorithm development. Our

goal in this chapter is to review a selected set of such problems, showing that ad hoc net-

working (and, for that matter, networking in general) can contribute a fertilizing effect to

the research on algorithms.

Since it would be impossible to provide an exhausitve description of all ad hoc network

related algorithm design issues in a single chapter, we used the following principles in the

selection and presentation:

We focus on ad hoc networking motivated issues that can be formalized as algorith-

mic problems on graphs. Since this is still more than what can be addressed in a

Supported in part by NSF Grants ANI-0105985 and ANI-0220001.

427

Mobile Ad Hoc Networking. Edited by Basagni, Conti, Giordano, and Stojmenovic.

ISBN 0-471-37313-3 © 2004 Institute of Electrical and Electronics Engineers, Inc.

428 ALGORITHMIC CHALLENGES IN AD HOC NETWORKS

chapter, we specifically selected the area of path problems in graphs. The reason for

focusing on graphs is that they are perhaps the best-known structures in the field of

discrete algorithms and at least the questions can be understood without too much

background. The reason for selecting path problems is that this is related to routing

in networks, which is a very rich area of algorithmic issues.

Since we are interested in this chapter in core algorithmic issues, rather than practi-

cal implementations, therefore, we aim at exhibiting the essence of each question in

a mathematically meaningful way. Even though the ultimate motivation is practical

ad hoc networking, in the models we “peel off ” various layers of practical issues

that are piled on the core algorithmic problem. This approach sometimes allows us

to generalize the question, following its own intrinsic logics, yielding some interest-

ing unsolved problems.

Our main interest is in those problems that offer some chance for an efficient solu-

tion, at least under some restrictions, but, at the same time, they are not fully solved

yet. That is, we try to walk in the narrow region that separates the “plane” of solved

problems from the “sky high muountains” of hopelessly difficult tasks.

The reader is assumed to be familiar with the basic concepts of graph theory and algo-

rithms, including NP-completeness.1

16.2 A FRESH LOOK AT SHORTEST PATHS

An amazing variety of ad hoc routing protocols exists (see e.g., [16, 19, 21] and refer-

ences therein). No matter how different they may be, however, in every routing protocol it

is a key common task to find a “good” path between a source and a destination node.

But which path is good enough? If we have a path metric (such as hop count, expected

delay, expected lifetime, etc.), then, naturally, it is desirable to find a path that is optimal

or at least nearly optimal with respect to the given path metric. Nevertheless, this core al-

gorithmic task is often overshadowed by a multitude of other aspects. When addressing

routing protocols, we usually talk about a number of features, such as how the protocol

can be proactive or reactive, source-initiated or table-driven, link state or distance vector,

flat or hierarchical, and so on. This is not surprising, since in an ad hoc routing protocol

one typically has to find/maintain/update routes in a distributed way. In any case, howev-

er, we still have the common, fundamental graph problem of finding a path according to

some route metric that is either given explicitely or defined implicitely by the protocol de-

tails. This fundamental task of path finding is the one at which we take a fresh look in this

section.

One may immediately ask: does the finding of a (static) shortest path present any seri-

ous algorithmic challenge? After all, it is among the most basic algorithmic tasks in graph

theory and was very well solved in the 1950s.2 Well, our answer is: it all depends on the

1

We use the usual distinction between NP-complete and NP-hard, since most of the optimization tasks ask for

more than a yes/no answer and, therefore, they cannot fall directly in the complexity class NP. A task Q is NP-

hard if an NP-complete problem can be polynomially reduced to it (and, therefore, all NP-complete problems

can be polynomially reduced to it), but Q itself is not necessarily in the class NP.

2

Dijkstra™s algorithm appeared in 1959 [9]. Bellman published the precursor of the Bellman“Ford algorithm in

1958 [4].

429

16.2 A FRESH LOOK AT SHORTEST PATHS

path metric. Let us exhibit below a few examples of path metrics among which quite a few

apparently give rise to harder tasks than the conventional shortest-path problem, yet they

still have a natural motivation. In each example, we search for a simple path between two

given nodes u and v (simple means that no repeated edges or nodes are allowed on the

path; this will be required everywhere throughout this chapter). A path between nodes u

and v is called a u“v path, but we often just call it a path if no ambiguity arises. A path is

regarded as a set of links (edges in the graph theoretic terminology).

16.2.1 Examples of Path Problems

Most reliable delay constrained path. For each link, a delay value and a reliability

value are known. The end-to-end delay is the sum of the link delays along the path,

whereas the path reliability is the product of the link reliabilities. Find the most reli-

able path among those that obey a given end-to-end delay bound.

Least vulnerable path. Certain sets E1, E2, . . . , Ek of links are specified that are

threatened by some attack or jamming. The links in any given set Ei are likely to fail

together. Find a path that intersects with the smallest number of the given link sets.

Minimum exposure path. Given a subset of the nodes that are in danger of attack or

jamming, find a path that is the farthest from these nodes, that is, the smallest oc-

curing hop distance between a path node and an endangered node is maximum. This

path can be viewed as minimally exposed to the attack or jamming. Another variant

is when the sum of these distances is to be maximized.

Maximum data volume path. A capacity value (in bit/s) is given for each link. We

also have an estimated lifetime for each link (the expected time until node move-

ment makes the link disappear). Find a path on which the maximum expected num-

ber of bits can be sent before the path has to be updated.

Path with maximum number of round trips. A delay value is known for each link, as

well as the estimated lifetime of the link. The lifetime of a path is the minimum of

its link lifetimes. Find a path such that the ratio of its lifetime versus its end-to-end

delay is the largest. That is, if links are assumed to be bidirectional and the delay is

the same in both directions, then this path can have the maximum number of round

trips during its lifetime.

Minimum energy path. For each node, two energy values are given: one that is con-

sumed by transmitting a packet and another (typically smaller) value that is con-

sumed when receiving a packet. Find a path such that the total enery consumed for

the end-to-end delivery of a packet is minimum. The total energy takes into account

every transmission and reception of the packet in the network, including receptions

by neighbors that are not the intended recipients, but waste energy by overhearing

the packet.

Maximum battery lifetime path. In addition to the setting of the minimum energy

path, now each node has a given energy budget that is consumed by the transmis-

sion/reception of packets. Find a path that can deliver the largest number of packets

before any node runs out of energy, if the considered nodes are the ones that are di-

rectly affected by the path (i.e., the nodes on the path and their neighbors).

Path with minimum error propagation. Let P be a u“v path. A set L of other links

(L P = 0) is called a backup set for P if, for any link e P, if e is removed from

/

the graph, then there is still a path between u and v in (P “ {e}) L. In other words,

430 ALGORITHMIC CHALLENGES IN AD HOC NETWORKS

if any given link on path P fails, then we can still find a replacement path using ex-

tra links only from the backup set L. Task: find a path P with the smallest backup

set. This path has minimum potential negative influence on the rest of the network,

in the sense that it uses the smallest set of extra links to get rerouted if any link on

the path fails.

Path with smallest delay sensitivity. Assume a delay value is known for each link.

The delay sensitivity S of a u“v path P is the maximum increase in the end-to-end

delay if a link fails on P and the path is replaced by a minimum delay path from the

rest of the graph, that is, using the edges E “ {e}. Formally, it is

S = max min {delay(P ) | P E “ {e}, P is a u“v path} “ delay(P)

eP P

Tasks: (1) Find a path with minimum delay sensitivity. (2) Restricting the search to

minimum delay paths only, find a path among them with smallest delay sensitivity.

(3) Find a path with minimum delay sensitivity among the paths that satisfy a given

delay bound (which can be higher than the minimum delay).

Optimal multifrequency path. Modern hardware can make the nodes capable of flex-

ibly switching between different radio frequency bands. Lower frequency links have

lower speed and higher delay, but can bridge over longer distance, resulting in

longer expected lifetime in a mobile ad hoc network. Switching a packet from one

frequency band to another, however, requires extra processing. We also know a de-

lay value for each link. Find a path with minimum total delay, where the total delay

includes the link delays and a processing delay for frequency change along the path.

The situation can be modeled by assigning weights and colors to the links (weights

represent delay and colors represent the different frequency bands). In terms of this

representation, we are looking for a path for which a linear combination of the path

weight and the number of color changes along the path is minimum.

Combinations. The above objectives can be combined in many different ways. For ex-

ample, find a minimum energy path that obeys delay and reliability constraints in a

multifrequency environment.

Multiple paths. All problems can be extended to the case in which multiple paths are

to be found. For example, find disjoint paths between the same end nodes, such that

they both obey a constraint on one or more relevant parameters (such as delay, ener-

gy, reliability, delay sensitivity, expected lifetime, etc.).

These examples show that even simple static pathfinding is not always easy. For in-

stance, the most reliable delay-constrained path is equivalent to another task known as the

shortest weight-constrained path problem in which we search for a minimum weight path

under the constraint that it obeys a given upper bound in another weighting. This task is

known to be NP-hard [13] (and its decision version is NP-complete). Yet, a number of

positive results are known for it. For example, it is solvable in pseudopolynomial time

[13], that is, by an algorithm that has a polynomial running time in terms of the size of the

weights, but not in terms of the number of bits that define the weights. (The size can be

exponentially large compared to the number of bits.) The algorithm presented in [13] for

this task runs in O[n5b log(nb)] time, where n is the number of nodes and b is the size of

the largest weight. Thus, this algorithm becomes exponential if the weights are exponen-

tially large, but works in polynomial time for polynomially bounded weights. There is also

431

16.3 A UNIFIED REPRESENTATION OF PATH METRICS

good news for the general case, too. Even with arbitrary weights, there is a fully polyno-

mial time-approximation scheme (FPTAS) for this problem [12, 17]. An FPTAS is an al-

gorithm that receives an error parameter in addition to the original input. It runs in poly-

nomial time in terms of the input size and of 1/ and produces a solution that is within 1 +

times of the optimum (minimum) value.3

16.3 A UNIFIED REPRESENTATION OF PATH METRICS

Having seen a sample of the diversity of possible path metrics, each with its own motiva-

tion, one may naturally arrive at the question: is it possible to somehow capture all this in

a unified framework? Below, we show that such a unification is indeed possible and we

also present some initial results in this direction. It can be developed both for directed and

undirected graphs in essentially the same way.

To define a general path metric, let us consider a family F of subsets of the edge set.

This family may contain the same set with arbitrary multiplicity. We define the path met-

ric as the number of sets in F that intersect with the path (counted with multiplicity). Re-

call that the path is meant as a set of its edges. After the formal definition, we show some

examples and prove the interesting fact that essentially any path metric, no matter how so-

phisticated, can be represented in this relatively simple way.

Definition 1 (F-measure or F-metric). Let P be a path. Given a family F of sets of edges

F

in the graph, the F-measure (or F-metric) of the path P is defined as the number of edge

sets H F that have nonempty intersection with P. The sets are counted with multiplicity.

Formally, the F-measure of P, denoted by F(P), is defined as

F(P) = m(H)

H P 0,H F

/

where m(H) is the multiplicity of the set H in F. A path with minimum F-metric is called

an F-shortest path.

Remark: There is nothing that would prevent the replacemant of integer mutliplicities

by real weights. The results below carry over to this more general case as well. Neverthe-

less, in this introductory presentation, we stay with the combinatorial setting of integer

multiplicities.

Before proceeding further, let us review a few simple examples. They may help the

reader to get some feeling for the F-measure.

Example 1: Shortest Path. Let F contain each edge (as a singleton set), with multiplic-

ity 1. Then F(P) is precisely the number of edges in P, that is, the hop metric. More

generally, if the multiplicity of edge ei in F is some integer wi, then F(P) is the

weight of the path under the weighting given by the wi values.

3