<<

. 81
( 87 .)



>>

19. R. K. Ahuja and J. B. Orlin, “Inverse Optimization,” Operations Research, 49, 771“783, 2001.
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

<<

. 81
( 87 .)



>>