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-