<<

. 41
( 87 .)



>>

wireless network by communication with a satellite network. Alternatively, nodes may
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-

<<

. 41
( 87 .)



>>