Koster A., Munoz X. Graphs and Algorithms in Communication Networks
Подождите немного. Документ загружается.
416 L. Carr-Motyckova et al.
Clustering presents one of the approaches to decrease power consumption in ad
hoc networks. In Section 16.4 an overview of different approaches to clustering in
ad hoc networks is presented. We review a new bandwidth-constrained clustering
algorithm that minimizes communication overhead, while still producing relatively
large and stable clusters.
In Section 16.3 we presented the case of energy-aware scatternet formation that
is used for routing in Bluetooth networks. The algorithm requires more traffic over-
head compared to algorithms that do not take the power consumption into account.
On the other hand, the algorithm distributes the data traffic as evenly as possible
among all nodes in the network.
In Section 16.5 several localization algorithms are presented. For all these sec-
tions, good strategies and algorithms are presented. The consideration of the com-
bination of the above problems remains open; also, a nice theoretical background is
missing.
References
1. Amis, A. D., Prakash, R.: Load-balancing clusters in wireless ad hoc networks. In: Pro-
ceedings 3rd IEEE Symposium on Application-Specific Systems and Software Engineering
Technology, pp. 25–32 (2000)
2. Amis, A. D., Prakash, R., P, T. H., Dung, V., Huynh, T.: Max-min d-cluster formation in
wireless ad hoc networks. In: Proceedings of IEEE INFOCOM, pp. 32–41 (2000)
3. Bandyopadhyay, S., Coyle, E.: An energy efficient hierarchical clustering algorithm for wire-
less sensor networks. In: Proceedings of IEEE INFOCOM, vol. 3, pp. 1713–1723 (2003)
4. Burkhart, M., von Rickenbach, P., Wattenhofer, R., Zollinger, A.: Does topology control re-
duce interference? In: MobiHoc ’04: Proceedings of the 5th ACM international symposium
on Mobile ad hoc networking and computing, pp. 9–19. ACM, New York, NY, USA (2004).
DOI http://doi.acm.org/10.1145/989459.989462
5. Buschmann, C., Pfisterer, D., Fischer, S.: Estimating distances using neighborhood intersec-
tion. In: Proceedings of 11th IEEE International Conference on Emerging Technologies and
Factory Automation, ETFA, pp. 314–321 (2006)
6. C.Buschmann, H.Hellbr
¨
uck, S.Fischer, A.Kr
¨
oller, Fekete, S.: Radio propagation-aware dis-
tance estimation based on neighborhood comparison. In: European Workshop on Sensor Net-
works, Lecture Notes in Computer Science, vol. 4373, pp. 325–340 (2007)
7. Fekete, S., Kr
¨
oller, A., Buschmann, C., Fischer, S.: Geometric distance estimation for sensor
networks and unit disk graphs. In: J. Gudmundsson, R. Klein, G. Narasimhan, M. Smid,
A. Wolff (eds.) Geometric Networks and Metric Space Embeddings, no. 06481 in Dagstuhl
Seminar Proceedings (2007)
8. Gabriel, K. R., Sokal, R. R.: A new statistical approach to geographic variation analysis. Sys-
tematic Zoology 18, 259–278 (1969)
9. Gao, J., Guibas, L. J., Hershberger, J., Zhang, L., Zhu, A.: Discrete mobile centers. In: Discrete
and Computational Geometry, pp. 188–196. ACM Press (2001)
10. Gerla, M., chieh Tsai, J. T.: Multicluster, mobile, multimedia radio network. Journal of Wire-
less Networks 1, 255–265 (1995)
11. Hac, A.: Wireless sensor network designs. John Wiley & Sons, Ltd (2003)
12. Hu, L.: Topology control for multihop packet radio networks. IEEE Trans. on Communica-
tions 41(10), 1474–1481 (1993)
13. Iannone, L., Khalili, R., Salamatian, K., Fdida, S.: Cross-layer routing in wireless mesh net-
works. In: Proc. ISWCS, pp. 319–323 (2004)
16 Topology Control and Routing in Ad Hoc Networks 417
14. Johansson, T., Carr-Motyckova, L.: Bandwidth-constrained clustering in ad hoc networks. In:
Proceedings of the Third Annual Mediterranean Ad Hoc Networking Workshop, pp. 379–385
(2004)
15. Johansson, T., Carr-Motyckova, L.: Energy-aware on-demand scatternet formation and rout-
ing. In: Proceedings of the 3rd International Workshop on Localized Communication and
Topology Protocols for Ad hoc Networks: LOCAN 2007 (2007)
16. Johansson, T., Carr-Moty
ˇ
ckov
´
a, L.: Reducing interference in ad hoc networks through topol-
ogy control. In: DIALM-POMC ’05: Proceedings of the 2005 joint workshop on Foun-
dations of mobile computing, pp. 17–23. ACM, New York, NY, USA (2005). DOI http:
//doi.acm.org/10.1145/1080810.1080815
17. Kar, K., Kodialam, M., Lakshman, T. V., Tassiuals, L.: Routing for network capacity maxi-
mization in energy constrained ad hoc networks. In: INFOCOM 2003. Twenty-Second An-
nual Joint Conference of the IEEE Computer and Communications Societies. IEEE, vol. 1,
pp. 673–681 (2003)
18. Kawadia, V., Kumar, P. R.: Power control and clustering in ad hoc networks. In: Proc. IEEE
Infocom, pp. 459–469 (2003)
19. Kr
¨
oller, A.: Algorithms for topology-aware sensor networks. Ph.D. thesis, TU Braunschweig
(2008)
20. Li, Q., Aslam, J., Rus, D.: Online power-aware routing in wireless ad-hoc networks. In: In
MOBICOM, pp. 97–107 (2001)
21. yang Li, X., Stojmenovic, I., Wang, Y.: Partial delaunay triangulation and degree limited lo-
calized bluetooth scatternet formation. In: in IEEE Transactions on Parallel and Distributed
Systems, pp. 17–32 (2003)
22. Lin, C. R., Gerla, M.: Adaptive clustering for mobile wireless networks. IEEE Journal on
Selected Areas in Communications 15, 1265–1275 (1997)
23. Mcdonald, A. B., Znati, T.: A mobility based framework for adaptive clustering in wireless
ad-hoc networks. IEEE Journal on Selected Areas in Communications 17, 1466–1487 (1999)
24. Moaveni-Nejad, K., Li, X. Y.: Low-interference topology control for wireless ad hoc networks.
In: ACM Wireless Networks, pp. 41–64. IEEE Press (2005)
25. Nadeem, T., Banerjee, S., Misra, A., Agrawala, A.: Energy-efficient reliable paths for on-
demand routing protocols. In: Sixth IFIP IEEE International Conference on Mobile and Wire-
less Communication Networks (2004)
26. Navarra, A., Tofani, A.: Distributed localization strategies for sensor networks. In: 4th IEEE
International Conference on Mobile Ad hoc and Sensor Systems (MASS), pp. 1–3 (2007)
27. Ramanathan, R., Rosales-Hain, R.: Topology control of multihop wireless networks using
transmit power adjustment. In: INFOCOM 2000. Nineteenth Annual Joint Conference of the
IEEE Computer and Communications Societies, pp. 404–413. IEEE (2000)
28. von Rickenbach, P., Schmid, S., Wattenhofer, R., Zollinger, A.: A robust interference model
for wireless ad-hoc networks. In: IPDPS ’05: Proceedings of the 19th IEEE International Par-
allel and Distributed Processing Symposium (IPDPS’05) - Workshop 12, p. 239.1. IEEE Com-
puter Society, Washington, DC, USA (2005). DOI http://dx.doi.org/10.1109/IPDPS.2005.65
29. Rodoplu, V., Meng, T. H.: Minimum energy mobile wireless networks. IEEE Journal on
Selected Areas in Communications 17, 1333–1344 (1999)
30. Ryu, J., S. H.Song, Cho, D.: New clustering schemes for energy conservation in two-tiered
mobile ad hoc networks. In: IEEE transactions on vehicular technology, vol. 51, pp. 1661–
1668 (2002)
31. S.Banerjee, Khuller, S.: A clustering scheme for hierarchical control in multi-hop wireless
networks. Tech. Rep. CS-TR 4103, University of Maryland, College Park (2000)
32. Schneider, J., Wattenhofer, R.: A log-star distributed maximal independent set algorithm for
growth-bounded graphs. In: PODC ’08: Proceedings of the twenty-seventh ACM symposium
on Principles of distributed computing, pp. 35–44. ACM, New York, NY, USA (2008). DOI
http://doi.acm.org/10.1145/1400751.1400758
33. Wang, K., long Xu, Y., liang Chen, G., feng Wu, Y.: Power-aware on-demand routing pro-
tocol for MANET. In: ICDCSW ’04: Proceedings of the 24th International Conference on
418 L. Carr-Motyckova et al.
Distributed Computing Systems Workshops - W7: EC (ICDCSW’04), pp. 723–728. IEEE
Computer Society, Washington, DC, USA (2004)
34. Wattenhofer, R., Zollinger, A.: XTC: A practical topology control algorithm for ad-hoc net-
works. In: Proc. of the 4 th Int. Workshop on Algorithms for Wireless, Mobile, Ad Hoc and
Sensor Networks (WMAN (2004)
35. Xu, Y., Bien, S., Mori, Y., Heidemann, J., Estrin, D.: Topology control protocols to conserve
energy in wireless ad hoc networks. Tech. rep., Center for Embedded Networked Computing
Technical Report 6 (2003)
36. Y.Liu, M. J.Lee, T. N.Saadawi: A bluetooth scatternet route structure for multihop ad hoc
networks. IEEE Journal on Selected Areas in Communications 21, 229–239 (2003)
37. Zaruba, G. V., Basagni, S., Chlamtac, I.: Bluetrees-scatternet formation to enable bluetooth
based ad hoc networks. Communications, 2001. ICC 2001. IEEE International Conference on
1, 273–277 (2001)
38. Zhao, F., Guibas, L.: Wireless sensor networks: an information processing approach. Morgan
Kaufmann (2004)
Index
(l,k)-routing, 265
1+1 protection, 139, 140
1:1 protection, 140
3-coloring, 296
ABC, 338
ad hoc network, 55, 401–416
adaptive broadcast consumption, 338
add/drop multiplexer, 63, 73
adjacent-channel interference, 49, 286, 293
ADM, 63
administrative weight, 201, 203, 204, 235
aggregated
node-link formulation, 99, 207, 208, 230
traffic flow, 35, 207
algorithm, 2
approximation, 23, 71–72, 75, 77, 271,
338–342, 351–352, 372–373
branch-and-bound, 19
branch-and-cut, 21, 111, 202, 207
branch-and-cut-and-price, 22
branch-and-price, 22
deterministic, 11
distributed, 9, 318–319
efficient, 2
exact, 14
greedy, 23
local search, 24, 42, 50
randomized, 11, 319–323, 378–400
algorithmic game theory, 243
all-optical network
communication game, 260
ant colony optimization, 24
AOLS, 121, 122
AP, 286–287
AP location problem, 289, 292
API, 405
approximation algorithm, 23, 71–72, 75, 77,
271, 338–342, 351–352, 372–373
approximation ratio, 23
approximation scheme, 24
APX, 23
arborescence, 7
root, 7
artificial neural network, 24
AS, 199
ASTN, 79
ATM, 79, 200
autonomous system, 199, 201
availability, 156
average path interference, 405
backup path, 31, 138
bandwidth utilization, 206
Bellman property, 212
Benders’ decomposition, 207
best response walk, 245
big-M, 230
coefficients, 234
models, 205
binary variable, 13
BIP, 338
Bluetooth, 407
piconet, 407
scatternet, 407
branch-and-bound algorithm, 19, 226
branch-and-cut algorithm, 21, 202, 207, 209,
221
branch-and-cut-and-price algorithm, 22
branch-and-price algorithm, 22
broadcast incremental power, 338
broadcasting, 311
radio network, 311
broadcasting schedule, 313
420 Index
broadcasting sequence, 312
cellular phone network, 46, 49
centralized system, 9
channel, 49
channel assignment problem, 46, 284, 289,
293–298
chromatic number, 48, 362
circuit
undirected graph, 6
clique, 6
Clos network, 22
clustering, 403, 411–412
Cmax-WGP, 361
co-channel interference, 47, 49, 293
collision, 287, 359
collision avoidance, 378–400
collision detection, 314
collision-as-silence, 314
combinatorial algorithm, 23
combinatorial optimization problem, 8
commodity, 33, 99
communication complexity, 9
communication game, 260
communication radius, 359
competitive ratio, 10
completion time, 361
complexity class, 11
component, 6
computational complexity, 11
APX, 23
APX-hard, 24
NP, 11
NP-complete, 12
NP-hard, 12
NPO, 23
P, 1 1
conditional wakeup, 315
congestion, 266
congestion game
graphical linear, 257
congestion game, 246, 259
connected graph, 6
connection, 138
connectivity, 29
edge, 6
vertex, 6
constraint
adjacent-channel interference, 50
assignment, 50
budget, 52
capacity, 32, 34, 39, 52, 224
link, 188
logical link, 100
node, 100
physical link, 100
co-channel interference, 50
conflict, 208, 209, 225, 226
conflict-eliminating, 218
connectivity, 28
coverage, 51, 52
flow conservation, 32, 34, 38, 100, 187
linear, 234
link diversification, 100
node diversification, 100
routing, 229
shortest path, 217
shortest path routing, 230
subflow uniformity, 188
contention sets, 284
contention window, 379
convex hull, 14
convex optimization problem, 24
convex set, 4
coordination mechanism, 250
CoS, 183
cost function smoothing algorithm, 42
randomized, 44
cost sharing game, 246
graphical Shapley, 257
multicast, 260
cost sharing method, 251
egalitarian, 252
egalitarian-path-proportional, 252
path-proportional, 252
Shapley value, 252
coverage planning, 284
critical radius, 367
critical region, 367
cross-layer optimization, 87
CSMA-CA, 287–289, 378–400
cut, 33, 106
cutting plane, 20, 207, 225
connectivity cuts, 108
cutset inequalities, 106
flow cutset inequalities, 107
cycle
directed graph, 7
undirected graph, 6
cycle property, 213
D-LSP, 190
data gathering problem, 358
data throughput, 284
De Bruijn graph, 22
decision problem, 11
decision variable, 13
dedicated protection, 140
Index 421
demand
point-to-point, 34
demand volume, 203, 204
design theory, 76
deterministic effective computing system, 11
DiffServ, 181
digraph, 6
cycle, 7
path, 7
strongly connected, 7
Dijkstra’s algorithm, 23, 30
Dijkstra-Prim algorithm, 26
dilation, 266
directed acyclic graph, 7
directed cycle, 7
directed graph, 6
directed links, 203
DISCNET, 225
discrete mathematics, 2
disjoint connecting paths problem, 37
distributed algorithm, 9, 318–319
distributed computing, 3
distributed system, 9
down-link, 49
DSATUR heuristic, 50
dynamic column generation, 18, 36
dynamic programming, 23
ECMP, 204
edge connectivity, 6
efficient algorithm, 2
ELS, 121, 122
energy-efficient routing, 407
equal cost multi-path, 204
Erlang fixed point, 167
exact algorithm, 14
extreme ray, 215
facility location problem, 52, 284
fading, 359
fairness, 252, 397–399
FAP, 46
FDMA, 46
Fibonacci heap, 27
flow, 32
ECMP, 204, 229
negative, 215
positive, 215
flow conservation, 32, 187
flow time, 361
Fmax-WGP, 361
forest, 27, 28
forwarding table, 201, 232
FPQ, 194
frequency assignment problem, 46, 293, 294
minimum blocking, 49
minimum interference, 49
minimum span, 48
Fsum-WGP, 361
full-duplex, 270, 358
function, 4
G-WiN, 227
game theory, 242
gathering problem, 358
general network planning problem, 41
generating function, 383–384
genetic algorithm, 24, 223
gigabit ethernet, 200
global backup path, 139
global optimal solution, 24
GMPLS, 79
gossiping, 330
radio network, 330
gradient method, 164
graph, 4
bipartite, 5
circuit, 6
complement, 5
component, 6
connected, 6
cycle, 6
directed, 6
path, 5
spanner, 38
spanning tree, 6
minimum cost, 26
tree, 6
undirected, 4
graph theory, 2, 22
greedy algorithm, 23, 27
grooming, 64, 66, 97
bidirectional ring, 77
cross-layer optimization, 87
directed path, 76
dynamic grooming, 83
engineering, 86
multilayer, 78
multilayer mesh network, 79
resilience, 85
unidirectional ring, 76
grooming factor, 65, 66
grooming ratio, 66
GSM, 46, 49
half-duplex, 270, 358
Hamiltonian cycle, 29
hashing tables, 223
422 Index
heuristic, 24
constructive, 24
local search, 24
hexagonal network, 274
hitting set, 352
hop-count weight system, 204
hyperbolic integer programming, 296–298
IEEE 802.11, 285–289
IGP, 201
IMBM, 338
incidence vector, 13
incomplete information, 257
independent set, 6
maximum weighted, 8
induced matching, 364
integer flow problem, 37
integer linear program, 18, 98–101, 128–131,
150–151, 207–211, 221, 234, 292–294,
297–298
integer linear programming
branch-and-bound, 19
branch-and-cut, 21
branch-and-price, 22
complete description, 21
cutting plane, 20, 105, 207, 225
heuristics, 103
linear relaxation, 19
preprocessing, 101
separation algorithm, 21
valid inequality, 20
interconnection network, 22
interference, 47, 284, 293, 359, 404, 411
adjacent-channel, 49, 286, 293
co-channel, 47, 49, 293
interference graph, 47
interference radius, 359
interior gateway protocol, 201
interior point method, 17
intermediate system to intermediate system,
201
internet protocol, 199, 236
inverse shortest path problem, 202, 205, 206,
209, 211, 234
IP, 79, 180, 199
ISP, 206
iterative maximum-branch minimization, 338
Jain index, 397–399
k-colorable induced subgraph, 49
Kautz graph, 22
kissing number, 339
Kleinrock delay function, 231
Kruskal’s algorithm, 27
label
considering routing, 126
definition of, 119
forwarding using, 120
label merging, 123
label space definition, 120
label stacking, 124
label stripping, 122
MERLIN groups, 123
MPLS, 121
operations, 120
scalability problems
in AOLS, 122
in ELS, 122
with RSVP-TE, 121
stack, 120
label space, 120
scopes of, 120
label switched path, 120
Lagrangian relaxation, 235
lazy scheduling, 403
LER, 182
light termination equipment, 66, 70
lightpath, 97
linear program, 15
linear programming
dynamic column generation, 18
formulation, 210
Fourier-Motzkin elimination, 16
interior point methods, 17
Simplex method, 16
techniques, 209
linear relaxation, 19, 210, 211, 220, 221, 226
link
logical link, 96
physical link, 96
link capacities, 203
fixed, 232, 234
link metric, 203
link utilization, 206
link weight optimization
with a commercial MIP solver, 214
link weights
are strictly positive, 203, 213
equal to 1, 204
fixed, 235
link weights optimization
with a B&C method, 221
LISE, 404
list coloring problem, 48
list-T-coloring problem, 48
load balancing game, 246
Index 423
local optimal solution, 24
local path, 140
local search algorithm, 24, 42, 50
localization, 402, 412–415
low interference spanner establisher, 404
MAC, 379
MANET, 401
mass-spring system, 414
master program, 18
matching, 6, 8
mathematical optimization, 2
mathematical optimization problem, 8, 13
max-flow min-cut theorem, 33
maximum flow, 33
maximum link utilization, 205, 207, 208, 230
MEBR, 337
medium access control, 287
medium contention, 287, 293
meshed network topology, 29
metaheuristic, 24
minimum k-partition problem, 49, 294
minimum cost flow problem, 31
minimum energy broadcast routing, 335
minimum spanning tree, 26, 338
mixed-integer linear program, see integer
linear program
mixed-integer program, see integer linear
program
mixed-integer rounding, 106
Mobile Ad Hoc Network, 401
MPLS, 64, 79, 96, 180, 201
MPLS-TE, 121
MST, 26, 338
multi-commodity connectivity, 147
multi-commodity flow, 34
flow relaxation, 223
integer flow problem, 37
multicast routing problem, 38
network flow problem, 215
non-bifurcated flow problem, 37
unsplittable flow problem, 37
unsplittable routing, 206
multi-interface network
cost minimization, 335
multi-protocol label switching, 64, 201
multicast routing problem, 38
multilayer network, 79, 96
multiple demand matrices, 223
Nash dynamics graph, 245
Nash equilibrium, 243
second order, 260
neighborhood, 222
network
congestion, 164
cut, 33
flow, 32
loss model, 164
multilayer, 96
optical burst switching, 164
optical network, 97
wireless, 378–400
network coverage problem, 50
network design, 250
mesh, 96
multilayer, 96
topology, 25
tree, 25
network design problem, 38, 41
network efficiency, 284
network extension problem, 42
network flow, 29
network layer
logical layer, 96
physical layer, 96
network loading problem, 38
network planning problem, 38, 41
network routing, 29, 41
network topology design, 25
non-bifurcated flow problem, 37
non-cooperative networks, 242
non-deterministic machine, 11
nonlinear optimization model, 9, 164, 298–300
nonlinear programming, 24
nonnegative
integer values, 206
nonzero flows, 231
NP, 11
NP-complete, 12
NP-hard, 12, 210, 221, 233
NPO, 23
number of collisions, 383–392
objective, 13
oblivious algorithm, 268, 313
radio network, 313
OBS, 164, 180
OFDM, 46
off-line routing, 267
omnidirectional antennas, 358
on-demand algorithm, 408
online call admission, 30
online optimization, 10
online routing, 268
open shortest path first, 201
open source, 222
optical burst switching, 164
424 Index
optical network, 53
optical network design, 40
optimal power assignment, 337
optimistic price of anarchy, 73
OSPF, 201
overlap graphs, 284
overlapping channels, 286
P, 1 1
packet routing, 265
paging problem, 10
first-in-first-out algorithm, 10
last-in-first-out algorithm, 10
least-recently-used algorithm, 10
longest-forward-distance algorithm, 10
parameter, 4
path
directed graph, 7
undirected graph, 5
path protection, 139
PDH, 79
permutation routing, 269
Petersen graph, 4
piconet, 407
plane grid, 271
point-to-point demand, 34
polyhedral combinatorics, 20, 105
polyhedron, 14
polynomial-time approximation scheme, 24
polynomial-time reducible, 12
polytope, 14
potential game, 245
price of anarchy, 72, 244, 247
price of stability, 244, 248
pricing problem, 18
primary path, 31
probability of collision, 385
problem reduction, 12
protection
1+1 dedicated path protection, 31, 97
dedicated, 140
failure dependent, 141
shared, 140
shortcut span, 152
PTAS, 24
QoS, 181, 194
radio network, 311, 378–400
ad hoc, 318
broadcasting, 311
collision, 312
collision detection, 314
collision-as-silence, 314
gossiping, 330
mobile, 329
oblivious algorithm, 313
UDG, 315
wakeup mode, 315
conditional, 315
spontaneous, 315
wakeup problem, 330
radio resource utilization, 284
randomized algorithm, 319–323
randomized cost smoothing algorithm, 44
range control, 402
recovery, 138
protection, 138
restoration, 138
resilience, 85
resource removal, 250
restoration
local-to-egress, 140
Riemann integral, 387
routing
with label space usage constraints, 126
metric, 200
multi-path, 164
of IP packets, 199
protocol, 29
routing patterns
(undirected) shortest path, 233
inconsistent, 212
invalid, 207, 235
with unique shortest paths, 205
routing protocol, 29, 200, 201, 210
RSVP-TE, 121
SBPP, 39
scatternet, 407
SCIP, 103
SDH, 66, 79, 96, 200
selective family, 314, 324
selfish users, 250
semidefinite programming, 49
sensor, 402
sensor network, 412
separability, 252
separation algorithm, 21
set, 3
convex, 4
set covering problem, 51
Shapley value, 247, 252
shared protection, 140
shared risk group, 143
shortest path
inverse problem, 205
unsplittable routing, 206
Index 425
shortest cycle problem, 31
shortest path
dynamic updates of, 225
inverse problem, 202, 206, 209, 211, 234
multiple, 205, 223
successive, 31
unique, 202, 203, 205, 213, 234
unsplittable routing, 213, 225, 226, 231,
233, 235
shortest path graph, 209
shortest path problem, 27, 30, 36, 39
weight-constrained, 36
shortest path routing
problems, 200, 202, 221, 235
protocols, 199, 201
shortest path traffic engineering problem, 203,
205
shortest path tree, 201, 338
shortest weight-constrained path problem, 36
Simplex method, 16
simulated annealing, 24, 224, 235
single backup path protection, 39
sink node, 358
SNDlib, 40, 110
social function, 244
SONET, 66, 200
spanner, 38, 404
spanner packing problem, 38
spanning tree, 6
bounded degree, 27
minimum, 26, 338
split property, 213
spontaneous wakeup, 315
SPT, 338
SRG, 143
stability, 252
stable set, 6
Stackelberg strategy, 250
Steiner tree
minimum cost, 27
packing problem, 38
SteinLIB, 28
STEP, 203, 205
strategic game, 243
strong budget balance, 252
strongly connected digraph, 7
subflow uniformity, 188
subgraph, 5
induced, 5
subset sum problem, 12
successive shortest path, 31
survivability, 138, 206
Suurballe’s problem, 31
switching network, 22
T-coloring problem, 48
tabu search, 24, 223, 235
taxes or tolls, 250
time complexity, 9
time of arrival, 414
ToA, 414
topology control, 402, 404–406
topology design, 25
totally unimodular matrix, 33
TOTEM, 222, 223, 227
tournament, 378–400
traffic
demand, 201, 203
engineering, 200, 205, 236
routing, 200, 202, 204, 230
splitting, 208, 227
traffic engineering, 86, 236
traffic grooming, 53, 64, 66
bidirectional ring, 77
cross-layer optimization, 87
directed path, 76
dynamic grooming, 83
engineering, 86
multilayer, 78
multilayer mesh network, 79
resilience, 85
unidirectional ring, 76
traffic grooming problem, 66
transit property, 212, 213
transitive tournament, 70
traveling salesman problem, 24, 29
tree
undirected graph, 6
tree networks
design, 25
two-layer network design problem, 96
two-phase approach, 207
undirected graph, 4
unidirectional antennas, 358
unit disk graph, 315, 327
unobtainable cycles, 211
unsplittable flow problem, 37
unsplittable multi-commodity flow routing,
206
unsplittable shortest path routing, 206, 213,
225, 226, 231, 233, 235
up-link, 49
valid inequality, 20, 105, 219, 220
facet-defining, 20, 107
violated, 20
variable
aggregated flow, 35, 225