ńňđ. 40 |

47. G. Calinescu, â€śComputing 2-Hop Neighborhoods in Ad Hoc Wireless Networks,â€ť submitted for

publication.

48. J. Gao, L. J. Guibas, J. Hershburger, L. Zhang, and A. Zhu, â€śGeometric Spanner for Routing in

Mobile Networks,â€ť in Proceedings of the 2nd ACM Symposium on Mobile Ad Hoc Networking

and Computing (MobiHoc 01), 2001.

49. X.-Y. Li and Y. Wang, â€śLocalized Construction of Bounded Degree Planar Spanner for Wireless

Ad Hoc Networks,â€ť submitted for publication.

50. J. Monks, V. Bharghavan, and W.-M Hwu, â€śTransmission Power Control for Aultiple Ac-

cess Wireless Packet Networks,â€ť in IEEE Conference on Local Computer Networks (LCN),

2000.

51. M. Sanchez, P. Manzoni, and Z. Haas, â€śDetermination of Critical Transmission Range in Ad-

Hoc Networks,â€ť in Multiaccess, Mobility and Teletraffic for Wireless Communications

(MMTâ€™99), 1999.

52. M. Faloutsos and M. Molle, â€śCreating Otimal Distributed Algorithms for Minimum Spanning

Trees,â€ť Tech. Rep. Technical Report CSRI-327 (also submitted in WDAG â€™95), 1995.

53. R. Gallager, P. Humblet, and P. Spira, â€śA Distributed Algorithm for Minimumweight Spanning

Trees,â€ť ACM Transactions on Programming Languages and Systems, 5, 1, 66â€“77, 1983.

54. J. A. Garay, S. Kutten, and D. Peleg, â€śA Sub-Linear Time Distributed Algorithm for Minimum-

Weight Spanning Trees,â€ť in Symposium on Theory of Computing, 1993, pp. 659â€“668.

55. L. Kirousis, E. Kranakis, D. Krizanc, and A. Pelc, â€śPower Consumption in Packet Radio Net-

works,â€ť in Symposium on Theoretical Aspects of Computer Science (STACS) â€™97, 1997.

56. A. E. F. Clementi, P. Penna, and R. Silvestri, â€śOn the Power Assignment Problem in Radio Net-

works,â€ť 2000.

57. A. Clementi, P. Penna, and R. Silvestri, â€śThe Power Range Assignment Problem in Radio Net-

works on the Plane,â€ť in XVII Symposium on Theoretical Aspects of Computer Science

(STACSâ€™00), LNCS(1770), pp. 651â€“660, 2000.

58. A. Clementi, P. Penna, and R. Silvestri, â€śHardness Results for the Power Range Assignment

Problem in Packet Radio Networks,â€ť in II International Workshop on Approximation Algorithms

for Combinatorial Optimization Problems (RANDOM/APPROXâ€™99), LNCS(1671), pp.

197â€“208, 1999.

ď›µ

59. G. Calinescu, I. Mandoiu, and A. Zelikovsky, â€śSymmetric Connectivity with Minimum Power

Consumption in Radio Networks,â€ť in IFIP-TCS, 2002, To appear.

60. P. Bose, A. Brodnik, S Carlsson, E. D. Demaine, R. Fleischer, A. Lopez-Ortiz, P. Morin, and J. I.

Munro, â€śOnline Routing in Convex Subdivisions,â€ť in International Symposium on Algorithms

and Computation, pp. 47â€“59, 2002.

61. P. Bose and P. Morin, â€śOnline Routing in Triangulations,â€ť in Proc. of the 10th Annual Interna-

tional Symposium on Algorithms and Computation ISAAC, 1999.

202 TOPOLOGY CONTROL IN WIRELESS AD HOC NETWORKS

62. I. Stojmenovic and X. Lin, â€śLoop-Free Hybrid Single-Path/Flooding Routing aAgorithms with

guaranteed delivery for Wireless Networks,â€ť IEEE Transactions on Parallel and Distributed

Systems, 12, 10, 2001.

63. S. Basagni, I. Chlamtac, V. R. Syrotiuk, and B. A. Woodward, â€śA Distance Routing Effect Algo-

rithm for Mobility (DREAM),â€ť in Proceedings of ACM/IEEE MobiComâ€™98, 1998.

64. Z. Haas and B. Liang, â€śAd-hoc Mobility Management with Uniform Quorum Systems,â€ť

IEEE/ACM Transactions on Networking, 7, 2, pp. 228â€“240, 1999.

65. I. Stojmenovic, â€śA Routing Strategy and Quorum Based Location Update Scheme for Ad Hoc

Wireless Networks,â€ť Tech. Rep. TR-99-09, Computer Science, SITE, University of Ottawa,

1999.

66. K. N. Amouris, S. Papavassiliou, and M. Li, â€śA Position Based Multi-Zone Routing Protocol

for Wide Area Mobile Ad-Hoc Networks,â€ť in Proceedings of 49th IEEE Vehicular Technology

Conference, pp. 1365â€“1369, 1999.

67. E. Kranakis, H. Singh, and J. Urrutia, â€śCompass Routing on Geometric Networks,â€ť in Proceed-

ings of 11 th Canadian Conference on Computational Geometry, pp. 51â€“54, 1999.

68. P. Morin, Online Routing in Geometric Graphs, Ph.D. thesis, Carleton University School of

Computer Science, 2001.

69. P. Bose and P. Morin, â€śCompetitive Online Routing in Geometric Graphs,â€ť in Proceedings of

the VIII International Colloquium on Structural Information and Communication Complexity

(SIROCCO 2001), pp. 35â€“44, 1999.

70. X.-Y. Li, Y. Wang and O. Frieder, â€śLocalized Routing for Wireless Ad Hoc Networks,â€ť 2003,

IEEE ICC 2003, to appear.

71. M. Penrose, â€śThe Longest Edge of the Random Minimal Spanning Tree,â€ť Annals of Applied

Probability, 7, 340â€“361, 1997.

72. P. Gupta and P. R. Kumar, â€śCritical Power for Asymptotic Connectivity in Wireless Networks,â€ť

in Stochastic Analysis, Control, Optimization and Applications: A Volume in Honor of W. H.

Fleming, W. M. McEneaney, G. Yin, and Q. Zhang (eds.), 1998.

73. X.-Y. Li, Y. Wang, P.-J. Wan and C.-W. Yi, â€śFault Tolerant Deployment and Topology Control in

Wireless Networks,â€ť in 2003 ACM MobiHoc, 2003.

74. M. Penrose, â€śOn k-Connectivity for a Geometric Random Graph,â€ť Random Structures and Al-

gorithms, 15, 145â€“164, 1999.

75. B. BollobĂˇs, Random Graphs, Cambridge University Press, 2001.

76. H. Dette and N. Henze, â€śSome Peculiar Boundary Phenomena for Extremes of rth Nearest

Neighbor Links,â€ť Statistics & Probability Letters, 10, 381â€“390, 1990.

77. M. Penrose, â€śExtremes for the Minimal Spanning Tree on Normally Distributed Points,â€ť Ad-

vances in Applied Probability, 30, 628â€“639, 1998.

78. M. Penrose, â€śA Strong Law for the Longest Edge of the Minimal Spanning Tree,â€ť Annals of

Probability, 27, 246â€“260, 1999.

79. C. Bettstetter, â€śOn the Minimum Node Degree and Connectivity of a Wireless Multihop Net-

work,â€ť in 3rd ACM International Symposium on Mobile Ad Hoc Networking and Computing

(MobiHocâ€™02), June 2002.

80. D. M. Blough, M. Leoncini, G. Resta, and P. Santi, â€śOn the Symmetric Range Assignment

Problem in Wireless Ad Hoc Networks,â€ť in Proceedings of 2nd IFIP International Conference

on Theoretical Computer Science, 2002.

81. C. Cooper and A. Frieze, â€śOn the Connectivity of Random k-th Nearest Neighbour Graphs,â€ť

Combinatorics, Probability and Computing, 4, 343â€“362, 1995.

82. M. Grossglauser and D. Tse, â€śMobility Increases the Capacity of Ad-Hoc Wireless Networks,â€ť

in INFOCOMM, 2001, vol. 3, pp. 1360â€“1369.

203

REFERENCES

83. P. Gupta and P. Kumar, â€śCapacity of Wireless Networks,â€ť Techincal Report, University of Illi-

nois, Urbanaâ€“Champaign, 1999.

84. O. D. Patrick, â€śConnectivity in Ad-Hoc and Hybrid Networks,â€ť in IEEE INFOCOM, 2002.

85. P. Santi and D. M. Blough, â€śAn Evaluation of Connectivity in Mobile Wireless Ad Hoc Net-

works,â€ť in Proceedings of IEEE DSN, pp. 89â€“98, 2002.

86. F. Xue and P. R. Kumar, â€śThe Number of Neighbors Needed for Connectivity of Wireless Net-

works,â€ť submitted to Wireless Networks.

87. P. Hall, â€śDistribution of Size, Structure and Number of Vacant Regions in a High-Intensity Mo-

saic,â€ť Z. Warsch. verw, Gebiete 70, 237â€“261, 1985.

88. T. Lukovszki, â€śNew Results of Fault Tolerant Geometric Spanners,â€ť in Workshop on Algorithms

and Data Structures, pp. 193â€“204, 1999.

89. F. Kuhn, R. Wattenhofer, and A. Zollinger, â€śAsymptotically Optimal Geometric Mobile Ad-Hoc

Routing,â€ť in Proceedings of the 6th International Workshop on Discrete Algorithms and Meth-

ods for Mobile Computing and Communications (DIALM), 2002.

CHAPTER 7

BROADCASTING AND ACTIVITY

SCHEDULING IN AD HOC NETWORKS

IVAN STOJMENOVIC and JIE WU

7.1 INTRODUCTION

Wireless networks consist of static or mobile hosts (or nodes) that can communicate with

each other over wireless links without any static network interaction. Each mobile host

has the capability to communicate directly with other mobile hosts in its vicinity. They

can also forward packets destined for other nodes. Examples of such networks are ad hoc,

local area, packet radio, and sensor networks. They are used in disaster rescues and wire-

less conferences, on battlefields, in possibly remote or dangerous environments where

monitoring objects is required, for wireless Internet access, and so on.

In a broadcasting task, a source node sends the same message to all the nodes in the

network. In the one-to-all model, transmission by each node can reach all nodes that are

within radius distance from it, whereas in the one-to-one model, each transmission is di-

rected toward only one neighbor (using narrow-beam directional antennas or separate fre-

quencies for each node). In the literature, broadcasting has been studied mainly for the

one-to-all model, and most of this chapter is devoted to that model. The one-to-many

model can also be considered, in which fixed or variable angular-beam antennas can be

used to reach several neighbors at once.

Broadcasting is also frequently referred to in literature as flooding. Broadcasting appli-

cations include paging a particular host or sending an alarm signal. The broadcasting task

was sometimes studied in the context of address serving [1] in hierarchically clustered

packet radio networks. Flooding/broadcasting is also used for route discovery in source-

initiated, on-demand routing. Broadcasting can similarly be used in the context of an effi-

cient location-aware routing algorithm as follows. The source S may initiate a destination

205

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

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

206 BROADCASTING AND ACTIVITIY SCHEDULING IN AD HOC NETWORKS

search process by broadcasting a short message that contains the location of S, identity

(ID) of destination D, and some control bits. When the destination search message suc-

cessfully reaches D, D applies any location-based routing algorithm (e.g., [2] which guar-

antees delivery if the location of the destination, in this case S, is accurate) and reports

back to S with a short message containing its location. The source S can then again apply

the same routing algorithm [2] (or use the path created in the previous step by D if that

path was recorded in the process) to send the full message to D. Ho et al. [3] argued that

flooding can be a viable candidate for multicast and routing protocols in very dynamic ad

hoc networks.

Another application of broadcasting is in the sensor network. Recent advances in tech-

nology have made it possible to integrate microsensor, low-power signal processing, com-

putation, and low-cost wireless communication into a sensing device, such as one devel-

oped by the WINS project at UCLA [4]. Data broadcasting and gathering are important

functions supported in a sensor network to collect and disseminate critical information,

such as temperature, pressure, and noise level.

Geocasting is a form of broadcasting in which nodes that shall receive messages are re-

stricted to be inside a region. A simple solution to this problem is to route from the source

to a node inside the geo-casting region, and then apply broadcasting inside the region [5].

Solutions proposed in literature do not appear to be more efficient than this one, and we

will not survey them here. A survey is given in [6].

The traditional solution to the broadcasting problem is blind flooding, whereby each

node receiving the message will retransmit it to all its neighbors. The only â€śoptimizationâ€ť

applied to this solution is that nodes remember messages received for flooding, and do not

act when receiving repeated copies of the same message. However, blind flooding causes

unnecessary collisions and bandwidth waste, with many nodes not receiving the message

as a consequence.

Williams and Camp [7] classified the broadcast protocols into simple (blind) flooding,

probability-based, area-based, and neighbor-knowledge methods. In this chapter, area-

based methods are reclassified within other groups, whereas neighbor-knowledge methods

are divided into clustering-based, selecting forwarding neighbors, and internal-node-based

methods. We shall present here a comprehensive taxonomy of broadcasting schemes with

the one-to-all model in mind (the other models can similarly be considered). All schemes

can be classified following the taxonomy consisting of five categories: determinism, net-

work information, reliability, â€śhelloâ€ť message content, and broadcast message content. The

boldfaced terms are used in the summary table given in the conclusion section.

7.1.1 Determinism

A broadcast scheme may use probabilistic or deterministic protocols, based on whether

or not a random number selection was used to make decisions. The random-number usage

here is limited to the network layer decision; the underlying medium-access control

(MAC) protocol may still use random backoff counters, for example, in a network layer

deterministic scheme.

7.1.2 Network Information

The second classification is based on the type of state information used in the algorithm:

global or local. Note that the distinction between global and local is not clear-cut. Central-

207

7.1 INTRODUCTION

ized algorithms can be also applied in the distributed setting if a deciding node has full

global information for the network. Through several rounds of sequential information ex-

changes, global or partial global information can be assembled based on local information

only. However, sequential information propagation (also called chain reaction) could be

costly, and this can be measured in terms of rounds. Mobility adds another dimension of

complexity in measuring state information. The locality of maintenance can be used to

measure the adaptiveness of a protocol in the mobile environment. Wu and Lou [8] further

classified protocols based on neighbor-knowledge information: global, quasiglobal, qua-

silocal, and local. The global broadcast protocol, centralized or distributed, is based on

global state information. A survey of centralized broadcasting algorithms (using global

information) is given in [9], and they will not be covered in this chapter. The classical ap-

proximation algorithm by Guha and Khuller [10] for connected dominating sets is based

on global information. In quasiglobal broadcasting, a broadcast protocol is based on par-

tial global state information. For example, the approximation algorithm in [11] is based on

building a global spanning tree (a form of partial global state information) that is con-

structed in a sequence of sequential propagations. Recently, Chen and Liestman [12] pro-

posed a distributed formation of a weakly connected dominating set by iteratively expand-

ing and connecting fragments, similar to the distributed Kruskalâ€™s algorithm. In quasilocal

broadcasting, a distributed broadcast protocol is based on mainly local state information

and occasional partial global state information. Cluster networks are examples of this: al-

though clusters can be constructed locally most of the time, the chain reaction does occur

occasionally. In local broadcasting, a distributed broadcast protocol is based solely on lo-

cal state information. All protocols that select forward nodes locally (based on one-hop or

two-hop neighbor sets) belong to this category. It has been recognized that scalability in

wireless networks cannot be achieved by relying on solutions in which each node requires

global knowledge about the network. To achieve scalability, the concept of localized algo-

rithms was proposed. These algorithms, based on local knowledge, achieve a desired

global objective.

7.1.3 Reliability

Reliability is the ability of a broadcast protocol to reach all the nodes in the network. It

can be considered at the network layer or at the medium-access layer. We will classify pro-

tocols according to their network layer performance. That is, assuming that the MAC lay-

er is ideal (every message sent by a node reaches all its neighbors), a location update pro-

tocol provides accurate desired neighborhood information to all nodes, and the network is

connected, broadcast protocols can be reliable or unreliable. In a reliable protocol, every

node in the network is reached. The set of nodes that rebroadcast a message in a reliable

broadcasting scheme define a connected dominating set. A dominating set D(S) of a set S

is a set of nodes such that each node from S either belongs to D(S) or has a neighboring

node that belongs to D(S). It is easy to observe that all nodes will receive the message if it

is retransmitted only by nodes that belong to a connected dominating set. Connectivity

provides propagation through the whole network, whereas domination assures reachabili-

ty by all nodes. The broadcasting task can therefore be solved optimally by finding a con-

nected dominating set of minimal size. Optimality here is measured by the percentage of

saved retransmissions in a reliable broadcasting scheme. Unfortunately, the problem of

finding a connected dominating set of minimal size is NP-complete, even if a node has

global knowledge about the network [13â€“15]. Therefore one must apply heuristics to

208 BROADCASTING AND ACTIVITIY SCHEDULING IN AD HOC NETWORKS

flood intelligently. Note also that a protocol, such as blind flooding, that is reliable on the

network layer may be very unreliable at the MAC layer. Excess messages in any protocol

affect the node power and bandwidth available; thus, the main goal is to describe a reliable

broadcast protocol with minimal number of retransmissions, that is, to construct a con-

nected dominating set of minimal size. Note also that the MAC layer cannot guarantee

100% reliability due to the hidden-terminal problem (a node simultaneously receiving

messages from two other nodes that are not aware of each otherâ€™s transmission) and the

probabilistic nature of protocols used.

7.1.4 â€śHelloâ€ť Message Content

The broadcast schemes may require different neighborhood information, which is reflect-

ed in the contents of messages sent by nodes when they move, react to topological

changes, change activity status, or simply periodically send update messages. A common-

ly seen â€śhelloâ€ť message may contain, in addition to its own ID, its position, one bit for

dominating set status (one bit telling neighbors whether or not the node considers itself to

be in a dominating set), a list of one-hop neighbors, and its degree (number of its neigh-

bors). Other content is also possible, such as a list of one-hop neighbors with their posi-

tions, a list of two-hop neighbors, or even global network information. The Global Posi-

tion System (GPS) provides geographic location information (if required) to hosts in a

ńňđ. 40 |