. 43
( 87 .)


inating set definitions, it was able to improve the performance of all of them as an added
feature. For instance, if a gateway node (e.g., I in Figure 7.4) realizes that all its neighbors
are covered by previous transmissions, it will not rebroadcast. Further, in [22], it was
found that each noninternal node A will assign itself to a neighboring internal node B that
has the largest degree. In case of ties, use the lowest id among candidate neighbors. This
rule attaches more neighbors to higher-degree nodes, thus possibly “emptying” the as-
signed list of low-degree internal nodes. If both internal node status and neighbor-elimi-
nation schemes are applied, then the algorithm works as follows: When an internal node
receives a message, it retransmits the message if it has a noneliminated neighboring node
that is either a noninternal node assigned to it, or an internal node. Similar enhancements
can be made to multipoint relay, and all methods come from [25]. Better methods (like
gateway-dominating set) can be improved by about 1%, whereas others benefit up to 10%
in saved rebroadcasts.
Wu and Dai [46] described a scheme that can be viewed as a combination of a general-
ized internal-node-based dominating set [24] and neighbor elimination, generalized to
several last hops in the broadcast path. In that scheme, gateway nodes are defined on the
fly, and the status may depend on the source node. The subgraph consists of all k-hop
neighbors (for small k such as 1 or 2) of A with higher priority value (say, id), and all k-
hop neighboring nodes that have previously forwarded the message (if the routing history
up to certain number of hops is included in the packet). If there exists a connected compo-
nent of that subgraph so that any neighbor of A is a neighbor of at least one node from the

component then A is a nongateway node. A more generalized rule is also proposed in
[24]: A node A is nongateway node if every pair of its neighbors is connected via nodes
with either higher priority value or nodes that have forwarded the message.
Cartigny, Ingelrest, and Simplot [47] described a RNG relay subset scheme, in which a
node v retransmits the message received from u if v has an RNG (the concept is described
below) neighbor which is not covered by u™s transmission. The algorithm can be interpret-
ed as the neighbor-elimination method whereby each node immediately eliminates all its
non-RNG neighbors from its forward list. After this preliminary step, each node behaves
as in the neighbor-elimination scheme. Euclidean and neigborhood-based distances are


In this section, we shall discuss the broadcasting problem at the medium-access layer. The
design of a reliable broadcast method depends on the following three decisions [48]:

1. By whom are errors detected?
2. How are error messages signaled?
3. How are missing packets re-transmitted?

Decisions (1) and (2) are normally handled jointly.
In the sender-initiated approach, the sender is responsible for the error detection. Error
messages are signaled using ACK signals sent from each receiver. Missing data at a re-
ceiver is detected if the sender does not receive an ACK from the receiver. In this case,
missing packets are retransmitted from the source through a unicast. When several re-
ceivers have missing packets, the sender may decide to rebroadcast the missing packets to
all the receivers.
In the receiver-initiated approach, each receiver is responsible for the error detection.
Instead of acknowledging each broadcast packet, each receiver sends a NACK once it de-
tects a missing packet. Suppose broadcast packets are time stamped using a sequence
number; a missing packet can then be detected by a gap between sequence numbers of the
receiving packets.
When the sender-initiated approach is applied, only the sender (which keeps the histo-
ry of broadcast packets) is responsible for retransmitting the missing packet, and the cor-
responding retransmitting method is called sender-oriented. Note that when the sender re-
ceives ACK signals from all the receivers, the corresponding packet can be removed from
the history.
There are three ways to retransmit the missing packet when the receiver-initiated ap-
proach is used: sender-oriented, neighborhood-oriented, and fixed-neighborhood-orient-
ed. These methods differ by the locations of the copies of missing packets. These loca-
tions are also called copy sites; they include the sender. Note that when there are several
receivers that have the same missing packet, broadcast NACK signals will be sent to the
copy site(s). To ensure that at most one NACK is returned to the sender per packet trans-
mission, when a receiver detects a missing error, it waits a random period of time before
broadcasting a NACK to the sender and all other receivers. This process is called NACK
suppression since a receiver will cancel its broadcast if it receives a NACK that corre-
sponds to a packet it has missed. In the sender-oriented approach, senders can either uni-

cast to a receiver that needs the missing packet or broadcast to all the receivers. In the
neighborhood-oriented approach, the receiver that needs the missing packet searches its
neighborhood for a group member that keeps a copy of the missing packet. The search
process uses a TTL-based unicast process or TTL-based broadcast process. The search
space is either limited to the broadcast tree (which is now rooted at the receiver) or is
without limitation. In the fixed-neighborhood-oriented approach, the copy sites are fixed
to a subgroup or each receiver has a “buddy” to back up each other.
Mobility of mobile ad hoc networks adds complexity in achieving reliability. When a
host moves from one neighborhood to another, proper hand-off protocols are needed. For
example, when host U has just completed its forwarding process to its neighbor V, host W,
a neighbor of V, moves away from the neighborhood of V and enters the neighborhood of
U. To ensure that host W gets a copy of the packet, U needs to keep the copy for a while
and will reforward the packet (with a proper tag indicating that this is a reforwarding
packet) whenever a change in its neighborhood is detected.
In [31], Lou and Wu study two environments to handle mobility. In the “static” environ-
ment, mobile hosts are allowed to roam freely in the working space. However, the broadcast
process (including forward-node selection and the broadcast process itself) is done quickly
so that both one-hop and two-hop neighbor sets remain the same during the process for each
host. In addition, each host has updated and consistent one-hop and two-hop neighbor sets
when the broadcast process starts. Clearly, delivery of the broadcast packet is guaranteed as
long as the selected forward nodes cover all hosts. In the “dynamic” environment, the
broadcast process is still done quickly as in the static environment, so that both one-hop and
two-hop neighbor sets remain the same during the process for each host. However, a host
cannot update its one-hop and two-hop neighbor sets in a timely and consistent manner be-
cause mobile hosts are moving at a fast speed. Under this model, the broadcast delivery rate
is no longer 100%. A simulation result in [31] shows that the broadcast delivery rate still re-
mains high in an ad hoc network with slow- to moderate-speed mobile hosts (with respect
to the transmission range) using an ideal MAC layer without contention and collision. This
high delivery rate is partly due to the broadcast redundancy in selecting the forwarding
nodes. Therefore, although excessive broadcast redundancy is harmful and will cause the
broadcast storm problem, some degree of redundancy is useful for reliability purposes.
Hsu, Tseng, and Sheu [49] propose an efficient reliable broadcast protocol based on
end-to-end acknowledgment, that is, all acknowledgments will be sent back to the source
following the reverse of the broadcast tree. The tree is constructed redundantly”each
node has multiple parent nodes (one primary and several backups). However, if all parent
nodes are lost (due to the movement of hosts), flooding is needed to guarantee that all the
acknowledgments will eventually be sent to the source.
Pagani and Rossi [21] propose a two-level hierarchical scheme for reliable broadcast.
Two phases are used: scattering and gathering. In the scattering phase, the broadcast pack-
et is forwarded to all clusterheads, which, in turn, send it to their local members. In the
gathering phase, the acknowledgments are collected by each clusterhead and sent along
the broadcast tree, built on the clusterheads, back to the source.
In order to approach 100% reachability rate in an IEEE 802.11 environment, Stojmen-
ovic et al. [22] designed the RANA (Retransmission After Negative Acknowledgements)
broadcasting algorithm. When a node A re-transmits a message, and if a collision at re-
ceiving node B occurs before the sender is recognized, no retransmission request is issued.
If the collision occurred after recognizing the sender node A, but before receiving the full
message, B will send a negative acknowledgment to A, asking it to repeat the transmis-
sion. The reachability in [22] improved from over 94% to over 98%, but with a trade-off

(up to 10% more retransmissions). The hidden-terminal problem (two nonneighboring
nodes receiving a message simultaneously and rebroadcasting it to a common neighbor) is
the main obstacle to achieving 100% reliability in a network operating in IEEE 802.11
medium-access scheme.
Viswanath and Obraczka [50] proposed different heuristics to deal with broadcast reli-
ability in highly mobile environments. Based on local movement velocity, each node de-
cides between three modes for the broadcasting task. In scoped flooding [50], periodic
“hello” messages contain a one-hop neighbor list. If the receiving node™s neighbor list is a
subset of the transmitting node™s list, then it does not re-broadcast the packet. We note that
this is a special case of the neighbor-elimination scheme [14, 22, 45]. The plain flooding
mode is the same as blind flooding. In the hyperflooding mode, additional rebroadcasts
can be triggered upon receiving a packet from a new neighbor.


In ad hoc wireless networks, the limitation on the power of each host poses a unique chal-
lenge for power-aware design [51]. There has been an increasing focus on low-cost and re-
duced-node power consumption in ad hoc wireless networks. Even in standard networks
such as IEEE 802.11, requirements are included to sacrifice performance in favor of re-
duced power consumption. In order to prolong the life span of each node and, hence, the
network, power consumption should be minimized and balanced among nodes. Unfortu-
nately, nodes in the dominating set in general consume more energy in handling various
bypass traffic than nodes outside the set. Therefore, a static selection of dominating nodes
will result in a shorter life span for certain nodes, which in turn will result in a shorter life
span of the whole network.
Wu, Wu, and Stojmenovic [52] study dynamic selection of dominating nodes, also
called activity scheduling. Activity scheduling deals with the way to rotate the role of each
node among a set of given operation modes. For example, one set of operation modes is
sending, receiving, idle, and sleeping. Different modes have different energy consump-
tions. Activity scheduling judiciously assigns a mode to each node to save overall energy
consumption in the networks and/or to prolong life span of each individual node. Note
that saving overall energy consumption does not necessarily prolong the life span of a par-
ticular individual node. Specifically, they propose to save overall energy consumption by
allowing only dominating nodes (i.e., gateway nodes) to retransmit the broadcast packet.
In addition, in order to maximize the lifetime of all nodes, an activity scheduling method
is used that dynamically selects nodes to form a connected dominating set. Specifically, in
the selection process of a gateway node, preference is given to a node with a higher ener-
gy level. The effectiveness of the proposed method in prolonging the life span of the net-
work is confirmed through simulation. Source-dependent forwarding sets appear to be
more energy balanced. However, it was experimentally confirmed in [53] that the differ-
ence in energy consumption between an idle node and a transmitting node is not major,
whereas the major difference exists between the idle and sleep states of nodes. Therefore
the most energy efficient methods will select a static dominating set for a given round,
turning all remaining nodes to a sleep state. Depending on energy left, changes in activity
status for the next round will be made. The change can, therefore, be triggered by changes
of power status in addition to node mobility. From this point of view, internal node-based
dominating sets provide static selection for a given round and more energy efficiency than
the forwarding-set-based method, which requires all nodes to remain active in all the

rounds. In [67], the key for deciding dominating set status is a combination of remaining
energy and node degree.
Xu, Heidemann, and Estrin [54] discuss the following sensor sleep node schedule. The
trade-off between network lifetime and density for this cell-based schedule was investigat-
ed in [68]. The given two-dimensional space is partitioned into a set of squares (called
cells), such as any node within a square can directly communicate with any nodes in an
adjacent square. Therefore, one representative node from each cell is sufficient. To pro-
long the life span of each node, nodes in the cell are selected in an alternative fashion as a
representative. The adjacent squares form a two-dimensional grid and the broadcast
process becomes trivial. Note that the selected nodes in [54] make a dominating set, but
the size of it is far from optimal, and it also depends on the selected size of the squares.
On the other hand, the dominating-set concept used here has smaller size and is chosen
without using any parameter (the size of the square has to be carefully selected and propa-
gated with relative node positioning in the solution [54]).
The Span algorithm [55] selects some nodes as coordinators. These nodes form a dom-
inating set. A node becomes a coordinator if it discovers that two of its neighbors cannot
communicate with each other directly or through one or two existing coordinators. Also, a
node should withdraw if every pair of its neighbors can reach each other directly or via
some other coordinators (they can also withdraw if each pair of neighbors is connected
via possibly noncoordinating nodes, to provide the chance for other nodes to become co-
ordinators). Since coordinators are not necessarily neighbors, three-hop neighboring
topology knowledge is required. However, the energy and bandwidth required for mainte-
nance of three-hop neighborhood information is not taken into account in experiments
[55]. On the other hand, if the coordinators are restricted to be neighboring nodes, then the
dominating-set definition [55] becomes equivalent to the one given by Wu and Li [24]. In
addition, the protocol [55] relies heavily on proactive periodic beacons for synchroniza-
tion, even if there is no pending traffic or node movement. Recent research on energy con-
sumption [53] indicates that the use of such periodic beacons or “hello” messages is an
energy-expensive mechanism, because of significant start-up costs for sending short mes-
sages. Finally, Chen et al. [55] observed that the overhead required for coordination with
SPAN tends to “explode” with node density, and thus counterbalances the potential sav-
ings achieved by the increased density.
Feeney [56] described a power-saving protocol in which each station is awake a bit
over half the time, to ensure that awake periods of any two neighboring stations will over-
lap, allowing communication between them.
Tian and Georganas [57] considered a somewhat related problem, the area coverage, in
which sensors decide about their activity status to prolong network lifetime but still pro-
vide continued monitoring of the whole area assigned. In their solution, nodes observe
that their monitoring area is already covered by other active sensors, send a message an-
nouncing their withdrawal from monitoring status, and move to passive state. An alterna-
tive method [42] follows a dominating-set-based approach in which nodes instead an-
nounce their activity status by one added bit; the method is used for both area coverage or
dominating-set creation with reduced size of the forwarding node set.


We shall now discuss the case of broadcasting in the one-to-one model, corresponding to
narrow-beam directional antennas. A broadcasting algorithm called SPIN for sending a

message from a node in a sensor network to all other nodes is described in [58]. Each
node that receives the datum (i.e., the message) that is being broadcast will forward a cor-
responding metadatum that has considerably shorter bit length (e.g., 16 bytes instead of
500) to all its neighbors. Sensor™s id, message id, or sensor™s location are examples. The
metadatum is thus flooded. The actual datum could be information that a particular sensor
collects. Neighboring nodes that did not yet receive the metadatum will reply with a re-
quest to get the actual datum. The node will respond by sending the actual datum to all
nodes that requested it. The power consumed by the SPIN protocol [58] is (n “ 1)E + 2E ,
where n is the number of nodes, e is the number of edges in the graph, and E and E are
mean powers consumed for sending long and short messages, respectively, along one hop.
In any broadcast scenario, the energy (n “ 1)E consumed is inevitable and is a lower
bound that needs to be utilized.
An improved broadcasting scheme is described in [59] and is based on the relative
neighborhood graph (RNG) concept [60] defined as follows. An edge (u, v) exists be-
tween vertices u and v if the distance between them, d(u, v), is not strictly the largest side
in any triangle uvw for every common neighbor w of u and v. In other words, w u,v:
d(u, v) max [d(u, w), d(v, w)]. Thus, for an edge (u, v) to be included, the intersection of
two circles centered at u and v and with diameter uv in Figure 7.5 (shaded area) should not
contain any vertex w from the set. In Figure 7.2, uv is not in RNG because of witness node
w. Figure 7.6 shows the RNG on a set of six nodes (in this case the RNG is a spanning
tree, which is not always the case).
Toussaint [60] proved several important properties of relative neighborhood graphs,
which are necessary for their application in the broadcasting task. RNG is a connected
planar graph. The planarity of the graph assures that it is a sparse graph. Each node has on
average about 2.5 neighbors independent of unit-graph density.
Thus, we will only try to optimize the number of short messages. In the flooding algo-
rithm [58], the number of short messages is equal to the total number of edges in the net-
work. A huge reduction in the short-message count can be obtained by applying concepts
of RNG graphs and dominating sets, as described in [59]. In the RNG-based broadcast,
starting from the source, the message is sent once over each edge of the RNG. Thus in-
stead of nd/2 messages in a complete unit graph with average density d, it is sent on about
1.25n edges, with a reduction factor of d/2.5 over the scheme [58]. The scheme, however,
requires the distance information between any two neighboring nodes, which can be ob-
tained from time-delay or signal-strength measurements. If that information is not avail-
able, Seddigh et al. [59] propose to apply the dominating-set concept that requires two-
hop neighbor information at each node. Since any node in the network has an internal


. 43
( 87 .)