can be exactly represented as shortest paths under some positive weighting. Is there a pure

graph theoretic characterization that is not based on linear programming?

16.7 ROUTE SYSTEMS

Viewing a route in isolation does not tell too much about its contribution to network per-

formance, since the network serves many sessions in parallel. It is a more difficult ques-

tion, however, how to find an entire route system among various nodes that is “good” in

any well-defined sense.

A typical problem in this context is to find routes that connect given node pairs, such

that available capacity (bandwidth) bounds are obeyed on the links. The task can be trans-

formed into a purely graph theoretic problem by replacing any edge i of capacity Ci by Ci

parallel edges (Ci is assumed to be an integer) and then the task becomes to search for

edge disjoint paths between given endpoints in the transformed graph.

This disjoint connecting paths problem, that is, to decide whether or not a given set

(s1, t1), . . . , (sk, tk) of terminator pairs can be connected via edge-disjoint paths P1, . . . ,

Pk such that Pi connects si with ti for each i, is one of the classical NP-complete problems

[11] that appeared in the sources of the NP-completess theory among the original prob-

lems of Karp [14]. It remains NP-complete both for the directed and undirected, as well as

the edge disjoint and vertex disjoint paths versions. The corresponding natural optimiza-

tion problem, when we are looking for the maximum number of terminator pairs that can

be connected by disjoint paths is NP-hard.

The restriction in disjoint connecting paths that we are looking for paths that connect

each source node with a dedicated destination is essential. If this is relaxed and we are sat-

isfied with edge-disjoint paths that connect each source si with some of destinations tj but

not necessarily with ti, then the problem becomes solvable with classical network flow

techniques. Thus, the prescribed matching of sources and destinations causes a dramatic

change in the problem complexity.5

Considerable research has been done on various decision and optimization versions of

the disjoint connecting paths problem in the discrete mathematical and theoretical com-

puter-science community, leading to a good number of deep theorems and approximations

with provable properties (see, e.g., [2, 3] and further references therein). Unfortunately,

most of the theoretical results are rather complex (to implement or even to understand),

yielding a situation in which practical applications hardly use anything other than the sim-

plest greedy heuristic, at least when fast solution is needed.

An additonal factor in ad hoc networks is that one cannot reasonably assume that each

node has full information about all the route requests in the entire network. Moreover, the

requests are not simultaneous. A model that attempts to capture this issue in an exact way

is on-line route search. In on-line route search algorithms, it is assumed that the route re-

quests are ordered in time and they come one by one. We have to find a route for each be-

fore receiving the next request. That is, we can only use past information; future requests

5

Interestingly, according to an old result, it becomes NP-complete if we require that just one of the sources is

connected to a dedicated destination; the rest is relaxed as above [5].

443

16.7 ROUTE SYSTEMS

are not known in advance, which is a natural assumption. Additionally, the information

that is available about the past may be restricted when chosing the next route.

The performance of such an on-line algorithm is measured by the so-called competitive

ratio. Let us consider, for example, the objective of selecting the routes such that the max-

imum link load (congestion) is minimized. In this context, an on-line algorithm is called

f(n)-competitive for some function f(n) of the network size n if it guarantees a solution in

which the maximum link load is asymptotically at most f(n) times higher than the value

that could be achieved by any algorithm, even by an optimal off-line one that knows the

whole request sequence in advance. Thus, the competitive ratio essentially tells us how

much we have to pay in performance degradation for not knowing the future in advance.

The best achievable competitive ratio in on-line route search is known to be f(n) =

O(log n), where n is the number of nodes [1, 18]. Interestingly, it can be realized by a sur-

prisingly simple algorithm, as follows.

The idea is that the weight of any given link is an exponential function of the current

load of the link. More precisely, let Ce be the capacity of link e and let Vi be the requested

capacity for the ith route request Ri. Let re(i “ 1) denote the relative load that has been ac-

cumulated on link e while routing the first i “ 1 requests, that is, the summed capacity of

the paths that have been routed through e before Ri, divided by the capacity of the link:

i“1

Vj

j=1

re(i “ 1) =

Ce

After having routed the first i “ 1 requests, the weight we of link e is updated according to

the following formula:

re(i“1) Vi/Ce

we = ( “ 1) (16.7)

where > 1 is a constant. Thus, the algorithm can be simply described as follows.

Algorithm On-line Route Search

Step 1 Initialization: set all link weights to 1; i := 1.

Step 2 Find a minimum-weight path between the given terminators of Ri, according

to the current weights.

Step 3 Recompute the weights according to Equation (16.7).

Step 4 If all requests are routed then stop, else i := i + 1, go to Step 2.

The above algorithm is proven to be O(log n)-competitive for a network of n nodes

[18]. Recall that it means the algorithm guarantees a routing in which the maximum link

load is (asymptotically) at most O(log n) times higher than the value which could be

achieved by any algorithm, even by an optimal off-line one that knows the whole request

sequence in advance.

It is a remarkable feature of the above algorithm that it uses only the aggregated rela-

tive load values of the links, but it does not require detailed information on the past route

requests. On the other hand, the algorithm allows that the link capacity may be exceeded

by the load, so the capacity is not viewed as a hard constraint. (We may assume that con-

444 ALGORITHMIC CHALLENGES IN AD HOC NETWORKS

nections can slow down their speed in such a case.) This, of course, can be easily avoided

if we modify the weights by setting the weight of saturated links to infinite. Unfortunate-

ly, however, this modification destroys the proof of the O(log n) competitive ratio.

It is interesting to note that even if we know the whole request sequence in advance, no

polynomial time algorithm is known (to the author™s knowledge) that would achieve a bet-

ter than O(log n) ratio to the optimum.

Open Problem 8. Is it possible to construct a similarly simple and efficient algorithm that

obeys link capacity constraints as hard limits, yet still has the same competitive ratio?

Open Problem 9. Although Algorithm On-line Route Search does not use the details of

past connections to lay out the next route, it still needs to know the relative load on each

link, which still requires global information about the network. Is it possible to achieve

similar preformance using less global information?

16.8 CONCLUSION

It is the author™s hope that this chapter will convince the reader that ad hoc networking

(and, of course, networking in general) can present a number of interesting, novel chal-

lenges for algorithm development and analysis. We only had space to address some select-

ed elements of a single area (routing). This was chosen because it perhaps offers the rich-

est set of challenges that are directly related to graph algorithms, and, therefore, it is the

easiest to follow and visualize. Nevertheless, we should not forget that the master prob-

lem, defying even any precise definition, is this: how do the various metrics, objectives,

algorithms, and other particular elements influence the overall network performance?

REFERENCES

1. J. Aspnes, Y. Azar, A. Fiat, S. Plotkin, and O. Waarts, “On-line Machine Scheduling with Appli-

cations to Load Balancing and Virtual Circuit Routing,” in ACM Symposium on Theory of Com-

puting (STOC™93), pp. 623“631, 1993.

2. G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, and M. Protasi,

Complexity and Approximation, Springer Verlag, New York, 1999.

3. A. Baveja and A. Srinivasan, “Approximation Algorithms for Disjoint Paths and Related Rout-

ing and Packing Problems,” Mathematics of Operations Research, 25, 2, pp. 255“280, 2000.

4. R. Bellman, “On a Routing Problem,” Quarterly of Applied Math., 16, 1, 87“90, 1958.

5. A. Faragó, “Algorithmic Problems in Graph Theory,” Conference of Program Designers, pp.

61“66, Eötrös University, Budapest, Hungary. 1985.

6. A. Faragó and V. R. Syrotiuk, “MERIT: A Unified Framework for Routing Protocol Assessment

in Mobile Ad Hoc Networks,” in Proceedings of 7th Annual International Conference on Mo-

bile Computing and Networking (Mobicom™2001), Rome, Italy, July 2001.

7. A. Faragó and V. R. Syrotiuk, “MERIT: A Scalable Approach for Protocol Assessment,” Invit-

ed paper, Mobile Networks and Applications (MONET), Special Issue on Mobile Ad Hoc Net-

works, in press.

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

Discrete Applied Mathematics, Special Issue on Combinatorial and Algorithmic Aspects of

Telecommunications, in press.

445

REFERENCES

9. E. W. Dijkstra, “A Note on Two Problems in Connection with Graphs,” Numerische Mathe-

matik, 1, 269“271, 1959.

10. S. Fortune, J. Hopcroft, and J. Wyllie, “The Directed Subgraph Homeomorphism Problem,”

Theoretical Computer Science, 10, 2, 111“121, 1989.

11. M. R. Garey and D. S. Johnson, Computers and Intractability, W. H. Freeman and Co., San

Francisco, 1983.

12. R. Hassin, “Approximation Schemes for the Restricted Shortest Path Problem,” Mathematics of

Operations Research, 17, 36“42, 1992.

13. J. M. Jaffe, “Algorithms for Finding Paths with Multiple Constraints,” Networks, 14, 95“116,

1984.

14. R. M. Karp, “Reducibility Among Combinatorial Problems,” in R. E. Miller and J. W. Thatcher

(Eds.), Complexity of Computer Computations, Plenum Press, New York, 1972.

15. C. Li, S. T. McCormick, and D. Simchi-Levi, “The Complexity of Finding Two Disjoint Paths

with Min-max Objective Function,” Disc. Appl. Math. 26, 105“115, 1990.

16. C. E. Perkins (Ed.), Ad Hoc Networks, Addison-Wesley, Reading, MA, 2001.

17. C. A. Phillips, “The Network Inhibition Problem,” in Proceedings of 25th Annual ACM Sympo-

sium on Theory of Computation (STOC™93), pp. 776“785, 1993.

18. S. Plotkin, “Competitive Routing of Virtual Circuits in ATM Networks,” IEEE Journal Selected

Areas in Communications, 13, 1128“1136, 1996.

19. E. M. Royer and C.-K. Toh, “A Review of Current Routing Protocols for Ad Hoc Mobile Wire-

less Networks,” IEEE Personal Communications, 46“55, April 1999.

20. A. Schrijver, Theory of Linear and Integer Programming, Wiley, New York, 1990.

21. C.-K. Toh, Ad Hoc Mobile Wireless Networks: Protocols and Systems, Prentice Hall, Upper

Saddle River, NJ, 2001.

INDEX

Acceptable-Power-to-Send (APTS), 152“153 Angular-beam directional antennas, broadcasting

Access delay, 393 schemes, 209

Access technology, 5“6 Angular group, beamforming antennas, 151

Acknowledgment (ACK), 145 Antenna beamforcing, medium-access control

Activations, 150 (MAC) modules:

Activity scheduling, 221“222 antenna concepts, 141“143

Ad Hoc On-Demand Distance Vector (AODV), benefits of, 139

23“26, 107, 269, 281“283, 295, 302, 343 directional MAC, 145“151

Ad Hoc On-Demand Multipath Distance Vector neighbor discovery, 141, 156“171

(AOMDV) routing protocol, 292 power-controlled MAC, 151“156

Ad hoc TCP (ATCP), 80 relevance of, 143“144

Ad Hoc Traffic Indication Map (ATIM), “smart” beamforming antennas, 143

IEEE802.11, 77“78 Antenna pattern, 142

Adaptive arrays, 143 Anti-messages, 398

Adaptive beamforming, 143, 150“151 Application program interfaces (APIs), 140

Adjusted transmission radii, broadcasting with, Area coverage, 222

224“226 ARIADNE, 333“335

A-GPS, 12 Asia, wireless technology development in, 6

Algorithmic challenges: Associativity-Based Routing (ABR), 23

F-shortest path, 435“436 Asymmetric neighbor links, MANETs, 260

inverse shortest path problem, 439“442 Asymmetric nodes, 279

mobile paths, 436“439 Asynchronous Connectionless (ACL), 61“62

path metrics, 431“434 Authenticated routing for ad hoc networks (ARAN)

route systems, 442“444 protocol, 294, 335“337

shortest paths, 428“442 Autoconfiguration, MANETs, 261

types of, 427“428

All-for-all service, 188 Balanced systems, host sources, 378

All-for-some service, 188 Bandwidth, 51, 276, 278

Aloha, 14 Basic Energy Conservation Algorithm (BECA), 312

AMROUTE protocol, 26 Battery Energy Efficient (BEE) protocol, 293, 323

Angle of arrival (AOA), 165 Battery-operated devices, 264

Angle-SINR table, 149 Battery power, 276

447

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

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

448 INDEX

Beacon signals/beaconing, 157, 163, 240 multi-hop relaying, 212“214, 217

Beamforming networks, 143 neighbor elimination, 212, 217“218, 221

Beam steering, 143, 150“151 power-aware, 221“222

Beamwidth, 143 probabilistic, 206, 211“212

BECA/AFECA, 312“313 quaziglobal, 207

Biconnected graph, 159 quazilocal, 207

Biconnected Minimum Maximum Power (B-MMP), reliability, 207“208, 219“221, 226

161, 163 RNG relay subset, 218

Bit error rates (BER), 383 screening angle, 214

BlueMesh protocol, 127, 131“134 taxonomy, 206, 225

BlueNet, 126“127 Broadcast scheduling, 150

Blueroot, defined, 125 Broadcast tree, 220

BlueStars, 126“130 Busy tones, 152“153

Bluetooth: Butlermatrix, 144

adaptation protocol layer, 64

Asynchronous Connectionless (ACL), 61“62 Cancellation, 398

Baseband layer, 61“63 Capture effects, 385

higher layers, 64 Carrier Sense Multiple Access-Collision Avoidance

link manager, 63“64 (CSMA/CA):

logical link control, 64 antenna beamforming, 144“149, 151“152

L2CAP, 64 applications, generally, 19“20, 53, 73, 86

networks, generally, 5“6, 15, 49, 303 directional, 147“149, 171

Piconet, 61“63 power-controlled, 151“153, 171

Profiles, 64 topology control, 165

RF layer, 60“61 Carrier-sense threshold, 380

Scatternet, 63, 117“136 Causality error, 397

security mechanisms, 349“351 CDMA networks/systems, 4“6, 52

Synchronous Connection Oriented (SCO), 61 cdma2000, 6

technological basics, 118“120,128 Cellular phones, 5

Bluetooth Topology Construction Protocol (BTCP), Certificate revocation, 346

123“124 CGSR protocol, 22, 24

BlueTrees, 127 Channel capacity, 393

Bordercasting, 287 Circular error probability (CEP), 239

Bouncing boundary, 377 Clear To Send (CTS) messages:

Boundary policy, simulations, 376“378 characteristics of, 20, 145

Bounded node degree, topology control: IEEE802.11 standards, 74“75, 294

characteristics of, 179“180 Closed systems, host sources, 378

high-degree Yao graph, 181“182 Clusterheads, in broadcasting schemes, 208, 210, 220

sink structure, 180 Clustering:

symmetric Yao graph, 181 in broadcasting, 209“211

YaoYao structure, 180“181, 198 passive, 210

Bounded power stretch factor, 179 in routing, 288“290

Broadcast, 25 CMMBCR, 321

Broadcasting: Coasting-forward, 398

adjusted transmission radii, 224 COFDM (Code ODFM), 54