measure time delays or signal strengths of incoming messages and determine the relative

location of their neighbors.

7.1.5 Broadcast Message Content

The broadcast message sent by the source, or retransmitted, may contain the broadcast

message only. In addition, it may contain a variety of information needed for proper func-

tioning of the broadcast protocol, such as the information previously listed for “hello”

messages, message plus one/two bits, or a list of forwarding neighbors, informing them

whether or not to retransmit the message.

The performance of broadcast protocols can be measured by a variety of metrics. A

commonly used metric is the number of message retransmissions (or the total power used

in the case of broadcasting with adjusted transmission radii) with respect to the number of

nodes (alternatively, rebroadcast savings, a complementary measure, can be used). The

next important metric is reachability, or the ratio of nodes connected to the source that re-

ceived the broadcast message. Time delay or latency is sometimes used, which is the time

needed for the last node to receive the broadcast message initiated at the source. Note that

retransmissions at MAC layer are normally deferred, to avoid message collisions. Some

authors consider as an alternative a more restricted indicator, whether or not the path from

source to any node is always following a shortest path. This measure may be important if

used as part of the routing scheme, since route paths are created during the broadcast

process.

Intelligent and scalable broadcasting and activity-scheduling solutions are based on the

concept of dominating sets. Clusterheads and gateway nodes in a cluster structure define

such a set, and were the first “intelligent” flooding solutions proposed in the literature.

However, the node mobility either worsens the quality of the structure dramatically, or

otherwise causes a chain reaction (local changes in the structure could trigger global up-

209

7.2 CLUSTERING-BASED FLOODING

dates). Localized connected dominating set concepts, proposed recently, avoid such chain

reactions and produce similar or better rebroadcast savings. Their maintenance does not

require any communication overhead in addition to maintaining positions of neighboring

nodes, or information about two-hop neighbors. One such concept is based on covering all

two-hop neighbors by a minimal set of one-hop neighbors. The other is based on creating

a fixed dominating set, in which nodes that do not have two unconnected neighbors and

nodes that are “covered” by one or two neighbors (each neighbor of a covered node is

neighbor of one of nodes that cover it) are eliminated. Neighbor elimination has also been

applied (solely or in conjunction with other concepts), whereby nodes give up retransmit-

ting if they are not aware of any neighbor that did not already receive the same message.

This chapter will survey known techniques based on dominating sets, and will discuss

their advantages and drawbacks.

Ad hoc networks are best modeled by the unit graphs constructed in the following way.

Two nodes A and B are neighbors if and only if the distance between them is at most R,

where R is the transmission radius, and is equal for all nodes. This model is widely used

(most protocols in this chapter use it), although many solutions surveyed here are valid in

more general models as well.

The remaining sections describe known scalable broadcasting techniques, and compare

their performance. Most presented schemes are very recent, developed in the last few

years, and the reference list is comprehensive in order to provide fairness to all contribut-

ing authors. Sections 7.2“7.6 describe network layer broadcasting schemes using omnidi-

rectional antennas. Section 7.7 discusses the MAC layer for the one-to-all model. Section

7.8 discusses activity scheduling and power-aware broadcasting schemes. Section 7.9

deals with broadcasting based on the use of narrow angular-beam directional antennas.

Section 7.10 describes localized schemes for broadcasting with adjusted transmission

radii. The Conclusion section provides a table with a summary of broadcasting schemes

for the one-to-all communication model, following the presented taxonomy.

7.2 CLUSTERING-BASED FLOODING

The distributed clustering algorithm [16, 17] is initiated at all nodes whose ID is lowest

among all their neighbors (locally lowest ID nodes). All nodes are initially undecided. If

all neighbors of node A that have lower ID sent their cluster decisions and none declared

itself a clusterhead (CH), node A decides to create its own cluster and broadcasts such de-

cision and its ID as cluster ID. If a node receives a message from a neighbor that an-

nounced itself as CH, it will send a message (to all its neighbors) declaring itself a non-

CH node, to enable more clusters to be created (note that two CHs are not direct neighbors

in the algorithm). Thus, each node broadcasts its clustering decision after all its neighbors

with lower IDs have already done so. Non-CH nodes that hear two or more CHs will de-

clare themselves as gateway nodes. A sophisticated maintenance procedure for cluster

formation when nodes move is described in [17]. To minimize the number of clusters, [18]

proposed to apply node degree as the primary key in clusterhead decisions. Nodes with

more neighbors are more likely to become clusterheads. In case of ties, lower ID nodes

have the advantage. The scheme [11] does not apply degree as the primary key, but instead

reduces the number of gateway nodes. After the clustering process is completed, each CH

contacts neighboring CHs (up to three hops away) in order to eliminate some gateway

nodes, and use only essential gateway nodes to preserve overall connectivity. In Figure

210 BROADCASTING AND ACTIVITIY SCHEDULING IN AD HOC NETWORKS

7.1, nodes B and F in the first round create clusters. Then nodes J and C create two more

clusters. Nodes A, D, E, and G are gateway nodes. If optimization [11] is applied (based

on a spanning-tree maintenance), node A can be eliminated. A clustering-based algorithm

is also reported in [19]. It does not depend on any spanning tree, and each node requires

knowledge of its single-hop neighbors, and a constant number of two-hop and three-hop

neighbors. The construction is fully localized. The maintenance is also localized using an

approach similar to that in [20] and outlined below.

Blind flooding has been replaced in [1, 21] by a method in which each CH and gateway

node in a clustered wireless network forwards the message exactly once. CHs and gateway

nodes together form a connected dominating set. When their scheme is applied, 8 out of

12 nodes need to retransmit the message in Figure 7.1 (or 7 if node A is eliminated). The

experiments in [22] gave surprisingly stable ratios of nodes in clustering-based dominat-

ing sets, with respect to number of nodes in the network and average node degrees. About

65% of nodes in lowest-ID-based and 52% of nodes in degree-based cluster structures be-

long to the dominating set. The maintenance of cluster structure, however, requires exces-

sive communication overhead due to the “chain effect” caused by mobility [23, 24]. Al-

though the lowest-ID or highest-node-degree cluster algorithms are localized (with

delayed decisions), they has no localized maintenance properties. To achieve localized

maintenance, the cluster maintenance can use a different algorithm to make the update a

localized one [20]: once the cluster is constructed, a non-CH will never challenge the cur-

rent CH. If a CH moves into an existing cluster, one of the CHs will give up its role of CH

based on some predefined priority. The localized maintenance is preserved, at the price of

increasing number of clusters with node mobility.

Gerla, Kwon, and Pei [23] proposed a combined clustering and broadcasting algorithm

that has no communication overhead for either maintaining cluster structure or updating

neighborhood information. In their passive clustering algorithm, the cluster structure is

updated with existing traffic by adding two bits to each ongoing message. The source S of

a broadcasting task will transmit the message to all its neighbors. S will declare itself a

CH (for the timeout period that is a parameter in the method) if it has no neighboring ac-

tive CH. Upon receiving the message, each node A will declare itself a CH using the same

K

C

J

A

G

D

L

F

I

B

H

E

Figure 7.1. Four clusters B, C, F, and J with three or four gateway nodes.

211

7.3 PROBABILISTIC, COUNTER, AND LOCATION BASED SCHEMES

criterion as the source S. Otherwise, A will check the ratio of neighboring CHs and neigh-

boring gateway nodes and declare itself a gateway if that ratio is above a certain threshold,

which is also a parameter of the method. If A decides to be a gateway, it will retransmit the

message. Otherwise A decides to be an ordinary node and does not retransmit the mes-

sage. The method is not reliable (there are pathological cases of poor delivery ratio) and

has global parameters.

To reduce overhead in constructing a connected dominating set among clusterheads,

Wu and Lou [8] recently proposed the 2.5-hop coverage, instead of the traditional three-

hop coverage (i.e., CHs within three hops) to ensure CH connectivity and full coverage.

Instead of using a three-hop coverage area (i.e., CHs within three hops), each CH just cov-

ers the CHs that have members (including CHs) within two hops. In Figure 7.1, suppose

the network is partitioned to four clusters B (with member E), C (with members A and D),

and F (with members G, H, and I), and J (with members K and L). The coverage area of F

includes C (which is three hops away) since C™s member D is two hops away. The coverage

area of B does not include J because none of J™s members are within two hops.

7.3 PROBABILISTIC, COUNTER, AND LOCATION BASED SCHEMES

Ni, Tseng, Chen, and Sheu [25] studied the broadcast storm problem. A straightforward

broadcasting by flooding is usually very costly and will result in serious redundancy, con-

tention, and collision. They identified this broadcast storm problem by showing how seri-

ous it is through analyses and simulations. Several schemes (probabilistic, counter-based,

distance-based, location-based, and cluster-based) to reduce redundant rebroadcasts and

differentiate timing of rebroadcasts to alleviate this problem are proposed in [25]. These

schemes achieve a high percentage of delivery rate with low number of retransmissions.

However, they are not reliable. In the probabilistic scheme [25], each node rebroadcasts

the first copy of a received message with a given probability p. In the counter-based

scheme [25], each node rebroadcasts the message if and only if it received the message

from less than C neighbors. In the distance-based scheme [25], the message is retransmit-

ted if and only if the distance to each neighbor that already retransmitted the message is

>D. In the location-based scheme [25], the message is retransmitted if and only if the ad-

ditional area that can be covered if the node rebroadcasts the message (divided by the area

of the circle with transmission radius) is greater than the threshold A. A simplified version

of the method is to rebroadcast the message if the node is not located inside the convex

hull of neighboring nodes that already retransmitted the message. In the cluster-based

scheme, the lowest-ID clustering algorithm [17] is applied, and one of the above four

methods is then applied on CHs and gateway nodes. All described methods are not reli-

able, and the experimental data [25, 22] indicate low saved rebroadcasts for high reacha-

bility.

Sasson, Cavin, and Schiper [26] observe that probabilistic flooding [25] in random unit

graphs behaves differently for low- and high-density networks. For low-density networks,

the success rate varies linearly with probability, making the method inefficient. For high

average degrees, there exists an ideal value of probability, and the success rate drops when

it is increased or decreased. Beyond an ideal value, packet collisions become more fre-

quent and network performance degrades.

Cartigny and Simplot [27] described a distance-based method without using position

information. The distance between two neighboring nodes is measured by a formula that

212 BROADCASTING AND ACTIVITIY SCHEDULING IN AD HOC NETWORKS

depends on the number of common neighbors. The broadcast message is piggybacked

with a list of one-hop neighbors. Neighbor elimination (see Section 7.6) is also used to

enhance the performance. The method is suitable for highly mobile environments, since

“hello” message content is minimized.

7.4 SOURCE-DEPENDENT DOMINATING SETS

We shall now present methods that are reliable and fully localized. That is, node mobility

impacts only local structure. This section deals with methods in which the selection of

forwarding nodes depends on the source of the broadcasting task.

Several authors [14, 15, 28, 29] proposed independently reliable broadcasting schemes

in which the sending node selects adjacent nodes that should relay the packet to complete

the broadcast. The IDs of selected adjacent nodes are recorded in the packet as a forward

list. An adjacent node that is requested to relay the packet again determines the forward

list. This process is iterated until broadcast is completed. The methods differ in details on

how a node determines its forward list.

The multipoint relaying method, discussed in detail by Qayyum, Viennot, and Laouiti

[15], and dominant pruning method, proposed by Lim and Kim [14], are both based on

a heuristic that selects a minimal-sized subset of neighbors of a given node S that will

“cover” all two hop neighbors of S. A node is called “covered” if it received (directly or

via retransmissions by other nodes) the message originating at S. Relay points of S are

one-hop neighbors of S that cover all two-hop neighbors of S. That is, after all relay

points of S retransmit the message, all two-hop neighbors of S will receive it. The goal

is to minimize the number of relay points of S. The computation of a multipoint relay

set with minimal size is a NP-complete problem, as proven in [14, 15]. A heuristic al-

gorithm, called the greedy-set cover algorithm, is proposed in [30]. This algorithm re-

peats selecting node B in which the number of neighbor nodes that are not covered yet

is maximized. Consider the network in Figure 7.2, with node F being the source of

K

C

J

A

G

D

L

F

B I

H

E

Figure 7.2. Selecting forwarding neighbors: G, E, and I for node F, D, and J for G, and B for E.

213

7.4 SOURCE-DEPENDENT DOMINATING SETS

broadcasting or a relay node. Its one-hop neighbors are E, G, H, and I, and its two-hop

neighbors are B, D, J, and L. E covers only B, G covers D and J, I covers L, and H does

not cover any two-hop neighbor. In the first round, node G is selected to forward the

packet. Nodes L and B are still not covered. Nodes B and I must be selected to cover

them, whereas node H does not need to be in the list. Thus, the forwarding set for node

F is {G, E, I}. Each of them then selects its own forward list. They can optimize the se-

lection by ignoring nodes covered by other nodes in the forward list, if they are aware of

their neighbors. Node G, for instance, considers one-hop neighbors D and J to forward

to B, C, and K (it learns that its two-hop neighbor L is covered by I), and must select

both. Node I will not select any forwarding node, whereas node E will select B to cov-

er A and D. In total, 7 out of 12 nodes will rebroadcast. The performance evaluation in

[22] gave a quite stable ratio with respect to average graph degree of medium density,

with 59“64% of nodes in the dominating set.

Lou and Wu [31] discuss two extended dominant pruning methods: total dominant

pruning (TDP) and partial dominant pruning (PDP), both using one-hop neighbors to cov-

er two-hop neighbors. TDP requires that the sender piggyback information about its one-

hop and two-hop neighbor sets (simply called neighbor set within two hops) along with

the broadcast packet. With this information, the receiver can prune all the nodes in the

sender™s neighbor set within two hops from the receiver™s neighbor set that is within two

hops. Apparently, TDP will generate a smaller forward node set than Lim and Kim™s dom-