<<

. 42
( 87 .)



>>

inant pruning (DP), but it also introduces some overhead when the broadcast packet pig-
gybacks the two-hop neighborhood information. PDP, without using the piggybacking
technique, directly extracts the neighbors of the common neighbors of both sender and re-
ceiver from the receiver™s neighbor set within two hops. In Figure 7.2, suppose I is the
sender and F is the receiver, then the two-hop neighbor set for I includes D, E, F, G, H, I, J,
and L and the two-hop neighbor set for F includes B, D, E, F, G, H, I, J, and L. The cover-
age set for F is reduced to B based on both TDP and PDP. If F is the sender and E is the re-
ceiver, D can be pruned from E™s coverage area using TDP, but not for PDP since the link
between D and G is not included in E™s two-hop neighborhood information. Simulation
results in [31] show that the PDP algorithm avoids the extra cost of the TDP algorithm in-
troduced by piggybacking two-hop neighborhood information with the broadcast packet,
but achieves almost the same performance improvement.
Note that a pruning approach that is based on neighbor position rather than two-hop
neighbor set can also be used [22]. In Figure 7.2, once F determines that the distance be-
tween its neighbor G and the incoming node I is less than the transmission radius, there is
no need to cover G. However, neighbor position alone is not sufficient to detect neighbors
of common neighbors as in PDP. Therefore, neighbor position information only is weaker
than information of the neighbor set within two hops.
The extended pruning methods perform well in the average case. However, they do not
have a good approximation ratio (the worst-case ratio of selected forward set size with re-
spect to the minimum connected dominating set), especially in a dense network. Wu and
Lou [8] propose to extend the pruning method to the cluster network. The extended prun-
ing method is applied to the cluster graph consisting of clusterheads only. Basically, the
notion of the cluster graph converts any dense graph to a sparse one to guarantee a con-
stant approximation ratio. The 2.5-hop coverage model is used and it is shown in [8] that
the resultant cluster graph is a connected directed graph if the original graph is connected.
The authors refer to a version with a localized maintenance property (applying the vari-
antin [20]). However, this may create an excessive number of clusters; thus, cluster-based
214 BROADCASTING AND ACTIVITIY SCHEDULING IN AD HOC NETWORKS


broadcasting solutions appear to be far from optimal localized solutions for dynamic ad
hoc networks.
The adaptation of multihop relaying presented in [32] improves performance in the fol-
lowing manner. The broadcasting node transmits a list of its neighbors at the time of
broadcast packet transmission, not as part of any “Hello” message. Two-hop neighbor
knowledge is used to determine which neighbors also received the broadcast packet in the
same transmission, and these nodes are already covered and are removed from the neigh-
bor graph used to choose the next-hop relaying nodes. Finally, if a broadcast message is
received from a node that is not listed as a neighbor, the message is retransmitted, to deal
with high mobility issues. In connected dominating set based broadcast algorithm [33],
sender node establishes priorities between forwarding nodes, and each forwarding node
should eliminate from the consideration not only neighbors of the sender node, but also
neighbors of each relaying node with higher priority.
Sun and Lai [29, 34, 35], and Calinescu, Mandoiu, Wan, and Zelikovsky [28] presented
heuristics that aimed at covering the whole area where two-hop neighbors could be locat-
ed by a minimal set of one-hop neighbors, and analyzed the performance of their
schemes. The problem is equivalent to selecting a minimal set of disks that still cover the
same area as the area covered by all disks centered in neighboring points. Their forward-
ing sets contain, on average, more nodes than the one based on set cover heuristics [30],
since the forwarding sets are given larger areas to cover, and no two-hop information is
used. Thus, only one-hop position information is used. The solutions are based on the no-
tion of curved convex hulls, and have sophisticated details that are beyond the scope of
this chapter. Each forwarding node in the variants discussed in [29, 28] includes a for-
warding set as part of the message. In the variant discussed in [34, 35], this is avoided by
transferring the overhead to hello messages, which contain the position of the sender and
the list of its neighbors (without position information). The two-hop neighbor information
and one-hop position information are used to calculate the local cover set of the sender™s
node at the receiver™s node.
Sisodia, Manoj, and Murthy [36] propose to select forward nodes based on the notion
of stability. A weight function that indicates the temporal stability and spatial stability of a
node™s neighbors is used as the criterion in the selection process.
The lightweight and efficient network-wide broadcast protocol by Sucec and Marsic
[37] relies on two-hop neighbor knowledge obtained from “Hello” packets. Each node de-
cides to rebroadcast based on knowledge of which of its other one- and two-hop neighbors
are expected to rebroadcast. Neighbors with a high degree of knowledge have higher pri-
ority to rebroadcast. Since a node relies on its higher-priority neighbors to rebroadcast, it
can proactively compute if all of its lower-priority neighbors will receive those rebroad-
casts; if not, the node rebroadcasts.
Rogers [38] proposed a GPS screening-angle technique in which the nodes make the
forwarding decision based on the angle between the previous node itself and the next
node. If the angle is greater than a threshold value, the message is forwarded to the corre-
sponding neighbor; otherwise, it is not forwarded. Stojmenovic and Seddigh [39] de-
scribed a method in which each node retransmits the message if and only if it has at least
one neighbor further from the source than itself. It will do so also in the case in which a
closer neighbor to the source remains silent. The two techniques [38, 39] are not reliable.
Boukerche [40] proposed to replace the flooding method in the route discovery phase of
the DSR routing algorithm, in which the message is forwarded to each neighbor of any
node receiving it, with the GPS screening-angle technique [38] or further-neighbor
215
7.5 SOURCE-INDEPENDENT DOMINATING SETS


scheme [39]. It was shown in [40] that occasional failure to discover the destination still
causes fewer problems in routing than the extensive overhead of “blind” flooding method
that can easily congest the network.


7.5 SOURCE-INDEPENDENT DOMINATING SETS

Most methods presented in the previous section include a forwarding set of neighbors as
part of the message. They therefore have message overhead, and the set of retransmitting
nodes depends on the source node. The approach presented in this section does not require
inclusion of the forwarding set in the message, and has a fixed set of retransmitting nodes,
regardless of source choice. Its maintenance does not require more communication over-
head, and it offers competitive performance (enhanced with neighbor elimination; see the
next section) according to experiments in [22].
Nodes that belong to a (fixed, source-independent) dominating set will be called inter-
nal nodes (of course, a different definition for the dominating set leads to a different set of
internal nodes). It is desirable, in the context of broadcasting, to create a dominating set
with minimal possible ratio of internal nodes. Wu and Li [24] proposed a simple and effi-
cient distributed algorithm for calculating a connected dominating set in ad hoc wireless
networks. They introduced the concept of an intermediate node. A node A is an intermedi-
ate node if there exist two neighbors, B and C, of A that are not direct neighbors them-
selves (see Figure 7.3). For example, nodes C and K in Figure 7.3 are not intermediate
nodes, while the other nodes are. The concept is simple, but not many nodes are eliminat-
ed from the dominating set. If a graph were complete, the definition might be modified to
select the highest key node as the default dominating set, although no retransmission is
needed for reliable broadcast.
Wu and Li [24] also introduced two rules that considerably reduce the number of inter-
nal nodes in the network. Rule 1 [24] is as follows. Consider two intermediate neighbor-
ing nodes v and u. If every neighbor of v is also a neighbor of u, and id(v) < id(u), then
node v is not an intergateway node. We may also say that node v is “covered” by node u.
Observe that retransmission by v, in this case, is covered by retransmission of u, since any
node that might receive the message from v will receive it instead from u. Stojmenovic et



K
C

J

A D G
L



F
B I

E H

Figure 7.3. Nodes C and K are not intermediate; nodes A, B, and H are not intergateway nodes.
216 BROADCASTING AND ACTIVITIY SCHEDULING IN AD HOC NETWORKS


al. [22] proposed to replace node IDs with a record key = (degree, x, y), where degree is
the number of neighbors of a node (and is the primary key in the comparison), and x and y
are its two coordinates in the plane (and serve as secondary and ternary keys). It signifi-
cantly reduces the size of the dominating set. Using such keys, consider example in Figure
7.3. Note that node J is forced by node K, for whom it is the only neighbor, to be in the
dominating set for all possible definitions of dominating sets that do not include node K
in it. Nodes A and B are covered by node D, node H is covered by node F, and node L is
covered by node G. The remaining six nodes are intergateway nodes, and are shown as
squares in Figure 7.3.
Next, let the gateway nodes be those intergateway nodes that are not eliminated by
Rule 2 [24], defined as follows. Assume that u, v, and w are three intergateway nodes that
are mutual neighbors. If each neighbor of v is a neighbor of u or w, where u and w are two
connected neighbors of v, and v has the lowest id among the three, then v can be eliminat-
ed from the list of gateway nodes. Stojmenovic et al. [22] again proposed to use the above-
defined key instead of id. The reason for the elimination of v is that any node that can ben-
efit from retransmission by v will receive the same message instead from either u or w. All
intergateway nodes in Figure 7.3 remain gateway nodes. Node E is “covered” by D and F,
but D and F are not connected themselves. Although all neighbors of node I are neighbors
of either F or G, it does not have lowest id (in this example, the x coordinate serves as id).
If id is changed appropriately, node I may become covered. This suggests that further im-
provements to the gateway definition might be possible, but the enhancement may require
informing neighbors about dominating set status. In the current definition, nodes may de-
cide their own dominating set status without any message exchange, but cannot decide the
same for their neighbors.
Stojmenovic et al. [22] observed that covering by one or two nodes may be done by any
nodes, not only (inter)gateway ones, leading to the same decision about dominating set
status. These neighbors, if not themselves (inter)gateway nodes, will be transitively fur-
ther covered [eventually by (inter)gageway nodes]. The consequence of this observation
[22] is that neighbors do not need to exchange their (inter)gateway status in order to make
their own decisions, and therefore the decisions can be made without any message ex-
changed between neighbors. In our judgment, this is, together with the quality of the
structure itself, the most desirable property of a topology construction and maintenance
algorithm.
If location information of neighboring nodes is available, each node can determine
whether or not it is an intermediate, intergateway, or gateway node in O(k3) computation
time (where k is the number of its neighbors), without any message exchanged with its
neighbors for that purpose. Otherwise, the maintenance of internal node status requires
the knowledge of neighbors for each neighbor. Experiments in [22] indicate that the per-
centage of gateway nodes decreases from 60% to 45% when average graph degree in-
creases from 4 to 10.
Dai and Wu [41] proposed several enhancements to the definition of internal nodes. In
[41], they generalize one- and two-neighbor coverage of a node to k-neighbor coverage,
with fixed and variable k. The case of variable k is even computationally less expensive
than two-node coverage. In this definition, each node A considers the subgraph of its
neighboring nodes with higher keys than A, and constructs connected components in the
subgraph (depth-first search can be used for this task). If there exists one connected com-
ponent so that each neighbor of A is a neighbor of at least one node from the component,
then node A is not a gateway node. Note that the test can be further simplified by observ-
217
7.6 NEIGHBOR ELIMINATION


ing that, in order to cover A, all neighbors with higher keys must be connected, that is,
there must be exactly one connected component.
A source-independent definition of dominating set in applications where the dominat-
ing-set status of each node must be communicated to its neighbors (this is the case in rout-
ing and activity scheduling applications) can be described as follows [42]. Each node A
initially calculates its dominating set status based on the original gateway node definition
[24]. Using some backoff mechanism, each gateway node decides when to transmit its de-
cision to its neighbors (nongateway nodes remain silent). While waiting, it may hear sev-
eral announcements from its gateway node neighbors. After each announcement, A reeval-
uates its gateway node decision. If the subgraph of all neighboring nodes with higher key
value or with announced gateway node decision is connected, and each neighbor of A is a
neighbor of at least one of these nodes, then A decides to withdraw from the dominating
set and never transmits such decision to neighbors.
A two-hop dominating-set concept, which can be further generalized to a k-hop domi-
nating-set concept, and can be viewed as a clustering scheme with localized maintenance
property, is proposed in [43]. It has the following properties: Two neighboring cluster-
heads can be at distance one or two; each node in a cluster is at distance one or two from
its clusterhead; and two clusters are, thus, connected if there exists a node that is neighbor
to both clusterheads, or the two clusterheads are directly linked. The structure is a general-
ization of Wu™s dominating-set concept [24]. We shall define similarly two-hop intermedi-
ate, intergateway, and gateway nodes as follows: A node X is two-hop intermediate if it has
two two-hop neighbors B and C that are not two-hop neighbors themselves. A two-hop in-
termediate node X is a two-hop intergateway if it has no two-hop neighbor Y such that
every two-hop neighbor of X is also a two-hop neighbor of Y, and key(X) < key(Y). The
value key(X) can be one of id(X), [degree(X), id(X)], or [energy-level(X), degree(X),
id(X)], that is, it can have primary, secondary, ternary, and so on keys. for comparisons. A
two-hop inter-gateway node X is a two-hop gateway if it has no two neighbors Y and Z
such that every two-hop neighbor of X is a two-hop neighbor of Y or Z, and key(X) <
key(Y), key(X) < key(Z). Adjih, Jacquet, and Viennot [44] proposed to combine multipoint
relay and dominating-set approaches. Each node computes its forwarding neighbor™s set
and transmits it to its neighbors. Each node then determines whether it belongs to a
“MPR-dominating set” if it either has the smallest ID in its neighborhood, or the node is a
forwarding neighbor of the neighbor with the smallest ID.


7.6 NEIGHBOR ELIMINATION

A neighbor-elimination scheme has been independently proposed in four papers [14, 22,
39, 45]. In this source-dependent scheme, a node does not need to rebroadcast a message
if all its neighbors have been covered by previous transmissions. In order to apply the
method, the same assumption as in the previous section is taken: either nodes learn geo-
graphic positions of their neighbors, or receive a list of neighbors from each of their
neighbors. After each received copy of the same message, the node eliminates from its re-
broadcast list neighbors that are assumed to receive correctly the same message. If the list
becomes empty before the node decides to rebroadcast, the rebroadcasting is canceled.
The neighbor-elimination scheme version from [45] uses two-hop neighbor information
instead of location of one-hop neighbors.
The method depends on the selected medium-access scheme. If IEEE 802.11 is used,
218 BROADCASTING AND ACTIVITIY SCHEDULING IN AD HOC NETWORKS


K
C

J

A D G
L



F
B I

E H

Figure 7.4. Retransmitting nodes (square shaped) in a neighbor-elimination method with source A.


Peng and Li [45] propose to let nodes with more neighbors rebroadcast earlier, so that
more nodes can be covered by one transmission, but experiments in [22] did not find sig-
nificant differences from the scheme in which nodes choose backoff times at random
within a fixed interval. Consider, for example, the network in Figure 7.4. Let us assume
that the order of retransmissions corresponds to the x-coordinate, that is, proceeds from
left to right. Node A is the source. Node B retransmits, followed by node C, which is not
aware that node D already received the message from B. Retransmissions from D, E, F, G,
and J then follow. Node I, for instance, does not retransmit since all its neighbors are cov-
ered by previous retransmissions from F and G. Note that there exist some additional re-
transmissions with respect to the gateway node set, but also some gateway nodes (e.g., I)
may not need to retransmit.
Although this neighbor-elimination scheme alone was not competitive with other dom-

<<

. 42
( 87 .)



>>