<<

. 84
( 87 .)



>>

Open Problem 7. Provide (a preferably simple) characterization of the path systems that
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

<<

. 84
( 87 .)



>>