HM Medical Clinic

 

Bao.mobihoc03.dvi

Topology Management in Ad Hoc Networks ∗
J.J. Garcia-Luna-Aceves Computer Science Department Computer Engineering Department University of California University of California Santa Cruz, CA 95064 Santa Cruz, CA 95064 The efficiency of a communication network depends not only The topology of an ad hoc network plays a key role in the on its control protocols, but also on its topology. We propose performance of the control algorithms used in the network a distributed topology management algorithm that constructs for such purposes as scheduling of transmissions, routing, and maintains a backbone topology based on a minimal and broadcasting. In many cases, several network links are dominating set (MDS) of the network. According to this not needed for establishing efficient sharing of the channel algorithm, each node determines the membership in the among neighboring nodes or the routing of data packets.
MDS for itself and its one-hop neighbors based on two-hop Weeding out redundant and unnecessary topology informa- neighbor information that is disseminated among neighbor- tion is usually called topology control or topology manage- ing nodes. The algorithm then ensures that the members ment. Topology management has been effectively applied of the MDS are connected into a connected dominating set in ad hoc networks to supplement routing control protocols, (CDS), which can be used to form the backbone infrastruc- such as CEDAR [24, 25], and to schedule efficient channel ture of the communication network for such purposes as access to propagate broadcast data [10].
routing. The correctness of the algorithm is proven, and There are two approaches to topology management in ad the efficiency is compared with other topology management hoc networks—power control and hierarchical topology or- heuristics using simulations. Our algorithm shows better ganization. Power control mechanisms adjust the power on behavior and higher stability in ad hoc networks than prior a per-node basis, so that one-hop neighbor connectivity is balanced and overall network connectivity is ensured [15,20, 26]. Li et al. [18] proved that network connectivity is Categories and Subject Descriptors
minimally maintained as long as the decreased power levelkeeps at least one neighbor remaining connected at every C.2.1 [Network Architecture and Design]: Wireless
2π/3 to 5π/6 angular separation. Ramanathan et al. [22] communication—ad hoc networks; C.2.1 [Network Archi-
proposed to incrementally adjust nodes' power levels so as tecture and Design]: Network topology—topology control
to keep network connectivity at each step. However, exceptfor the early work by Takagi and Kleinrock [26], topologies derived from power-control schemes often result in unidi-rectional links that create harmful interference due to the different transmission ranges among one-hop neighbors [21].
The dependencies on volatile information in mobile net- works, such as node locations [15], signal strength or angular Ad hoc networks, minimum dominating set, connected dom- positions [18] also contribute to the instability of topology control algorithms based on power control. Furthermore,some distributed implementations of these algorithms can hardly improve the throughput of mobile networks [22].
This work was supported in part by the Advanced Tech- In this paper, we focus on hierarchical topology control, nology Office of the Defense Advanced Research Projects with which a subset of the network nodes is selected to serve Agency (DARPA) under grant No. DAAD19-01-C-0026, bythe U.S. Air Force/OSR under grant No. F49620-00-1-0330, as the network backbone over which essential network con- and by the Office of Naval Research (ONR) under grant trol functions are supported (e.g., [17]). This approach to topology control is often called clustering, and consist of se-lecting a set of clusterheads in a way that every node is as-sociated with a clusterhead, and clusterheads are connectedwith one another directly or by means of gateways, so that Permission to make digital or hard copies of all or part of this work for the union of gateways and clusterheads constitute a con- personal or classroom use is granted without fee provided that copies are nected backbone. Once elected, the clusterheads and the not made or distributed for profit or commercial advantage and that copies gateways help reduce the complexity of maintaining topol- bear this notice and the full citation on the first page. To copy otherwise, to ogy information, and can simplify such essential functions as republish, to post on servers or to redistribute to lists, requires prior specificpermission and/or a fee.
routing, bandwidth allocation, channel access, power control MobiHoc'03, June 1–3, 2003, Annapolis, Maryland, USA.
or virtual-circuit support. For clustering to be effective, the Copyright 2003 ACM 1-58113-684-6/03/0006 .$5.00.
links and nodes that are part of the backbone (i.e., cluster- ID algorithm performs better than the clusterhead election
heads, gateways, and the links that connect them) must be algorithms based on node degrees in terms of clusterhead close to minimum and must also be connected.
stability in ad hoc networks.
Ideally, topology control based on clustering would se- Basu et al. [7] suggested to use the mean received-signal lect a minimum and sufficient number of links to serve as strength variations as the metric in clusterhead elections, the communication backbone of the network, while reducing which favors relatively stationary nodes to become the clus- network maintenance and control overhead. In graph the- terheads. We refer to this approach as MOBIC.
ory, the minimum dominating set problem and the relevant Cluster formation simplifies topology maintenance in ad minimum connected dominating set (MCDS) problem best hoc networks.
However, it has a negative effect on the describe the clustering approach to topology control.
clusterheads, because a clusterhead drains its energy more The dominating set problem in graph theory consists of quickly than a normal node. Therefore, a clusterhead elec- finding a subset of nodes with the following property: each tion algorithm must also consider load balancing of the clus- node is either in the dominating set, or is adjacent to a node terhead role to avoid node or network failure. Except for in the dominating set. The members of the dominating set Lowest ID, the aforementioned election algorithms inher-
are often called clusterheads, whereas the other nodes with- ently provide clusterhead load balancing in mobile networks.
out special functionalities are called hosts.
To improve Lowest ID, Amis et al. [2] provided clusterhead
of computing the minimum dominating set is known to be load balancing, which we call Load Balance, by running a
NP-hard [1, 12] even when the complete network topology virtual identifier (VID) and a budget counter at each node.
is available. In ad hoc networks, the difficulty of acquir- Load Balance uses the VID for elections, and the budget
ing complete network topology makes it impossible to com- for the clusterhead term, thus posing equal opportunity for pute the "minimum" dominating sets. Instead, a minimal each node to become a clusterhead.
dominating set (MDS) is usually pursued based on various However, all the existing heuristics have addressed only heuristics that can guarantee a local minimum election of some aspects of characteristics in ad hoc networks, such as the dominators in a polynomial number of steps.
load-balancing, mobility, or algorithmic convergence, while The MCDS problem consists of obtaining a minimum sub- ignoring the others.
set of nodes in the original graph, such that the nodes com- Clustering algorithms that build clusters within d hops pose a dominating set of the graph, and the induced sub- from the clusterhead (called d-clustering) have also been graph of an MCDS has the same number of connected com- proposed [1, 17, 23]. However, d-clustering requires flooding ponents as the original graph.
Although attractive, the in search of clusterheads [1], thus obviates the purpose of the MCDS is a well-known NP-complete problem in graph the- topology management for efficiency. In this paper, we only ory. Accordingly, sub-optimum solutions must be used to consider clustering approaches in which a host is always one approximate the optimum solution. In this paper, we re- hop away from a clusterhead.
fer to a sub-optimum solution of the MCDS problem as a We introduce a novel approach to the solution of the con- connected dominating set (CDS).
nected dominating set election problem, which we call topol- In the heuristics that have been proposed in the past, and ogy management by priority ordering or TMPO. Our ap-
which we summarize in the following paragraphs, the se- proach uses the neighbor-aware contention resolution (NCR) lected clusterheads are equivalent to a minimal dominating algorithm [5] to provide fast convergence and load-balancing set (MDS), and the selected gateways are chosen in such a with regard to the battery life and mobility of mobile nodes.
way that the union of gateways and clusterheads forms the Based on NCR, TMPO assigns randomized priorities to
mobile stations, and elects a minimal dominating set (MDS) Clusterheads can be elected via non-deterministic negoti- and the connected dominating set (CDS) of an ad hoc net- ations or by applying deterministic criteria. Negotiations re- work according to these priorities.
In doing so, TMPO
quire multiple incremental steps, and may incur an election requires only two-hop neighbor information for the MDS jitter during the process, because of the lack of consensus elections. The dynamic priorities assigned to nodes are de- about the nodes being elected as the clusterheads. Exam- rived from the node identifiers and their "willingness" to ples of this approach are the "core" extraction algorithm participate in the backbone formations. The willingness of [25] and the spanning-tree algorithm [14]. SPAN [8] allows a node is a function of the mobility and battery life of the a node to delay the announcement of becoming a clusterhead node. The integrated consideration of mobility, battery life for random amounts of time to attempt to attain minimum and deterministic node priorities makes TMPO one of the
conflicts between clusterheads in its one-hop neighborhood.
best performing heuristics for topology management in ad In contrast, deterministic criteria can determine the clus- hoc networks.
terheads in a single round. Different heuristics have been The rest of the paper is organized as follows. Section 2 used to form clusters and to elect clusterheads. Several ap- describes the network topology assumptions made in this pa- proaches [1, 3, 11, 13, 19] utilized the node identifiers to elect per. Section 3 specifies the minimal dominating set (MDS) the clusterhead within one or multiple hops. For simplicity, election algorithm based on node priorities. Section 4 de- we refer to this approach as Lowest ID in our comparative
scribes the algorithm that extends the MDS into a con- analysis. Banerjee and Khuller [4] assigned a weight value nected dominating set (CDS) of an ad hoc network. Sec- to each node for clusterhead election, which is essentially tion 5 proves the correctness of these MDS and CDS elec- the same as Lowest ID.
tion algorithms. Section 6 analyzes the average size of the The node degree is another commonly used heuristic in elected MDS using a probabilistic model. Section 7 com- which nodes with higher degrees are more likely to become pares TMPO with other CDS computation algorithms us-
clusterheads [14, 16, 25]. We refer to this approach as Max
ing simulations. Section 8 summarizes the paper and its key Chiang et al. [9] have shown that the Lowest
NETWORK ASSUMPTIONS AND
around and the quality of links changes frequently. Hence, nodes should be allowed to make MDS membership deci-sions based on local information.
Second, because in an This work assumes that an ad hoc network comprises a MDS every node is one hop away from a clusterhead, the group of mobile nodes communicating through a common local information needed at any node needs to include only broadcast channel using omni-directional antennas with the nodes that are one and two hops away from the node it- same transmission range. The topology of an ad hoc network self. Third, having too many clusterheads around the same is thus presented by an undirected graph G = (V, E), where set of nodes does not lead to an MDS. Hence, to attain a V is the set of network nodes, and E ⊆ V × V is the set of selection of nodes to the MDS without negotiation, nodes links between nodes. The existence of a link (u, v) ∈ E also should rank one another using the two-hop neighborhood means (v, u) ∈ E, and that nodes u and v are within the information they need.
packet-reception range of each other, in which case u and v Based on the above, the approach adopted in TMPO
are called one-hop neighbors of each other. The set of one- consists of each node communicating to its neighbors infor- hop neighbors of a node i is denoted by N1i. Two nodes that mation about all its one-hop neighbors. Using this infor- are not connected but share at least one common one-hop mation, each node computes a priority for each node in its neighbor are called two-hop neighbor of each other.
two-hop neighborhood, such that no two nodes can have the Each node has one unique identifier, and all transmis- same priority at the same instant of time. A node then de- sions are omnidirectional with the same transmission range.
cides to become a clusterhead if either one of the following Time is slotted, and synchronization among nodes exists to criteria are satisfied: the time-slot boundary. The current time t is defined by thecorresponding time slot number, starting from a consensus 1. The node has the highest priority in its one-hop neigh- temporal point in the past. In addition, a reliable neighbor protocol is assumed to enable the quick update of two-hopneighbor information at each node. Bao and Garcia-Luna- 2. The node has the highest priority in the one-hop neigh- Aceves [6] have proposed approaches for acquiring and syn- borhood of one of its one-hop neighbors.
chronizing two-hop neighbor information.
For convenience, the notation and terminology used in the rest of this paper are summarized in Table 1.
Table 1: Notation
The minimal dominating set.
The connected dominating set.
A member of the MDS in a network.
A node that connects clusterheads to form the CDS of the network.
A node that extends the reach of a cluster- Figure 1: Two cases that enable node
head to form the CDS.
i becoming a
A regular client of a network.
The set of one-hop neighbors of node i.
Figure 1 illustrates the two criteria that make node i a Node priority recomputation interval.
clusterhead. In Figure 1 (a), node i has the highest priority Time slot offset of node i for priority re- among its one-hop neighbors. In Figure 1 (b), node i has The priority of node i.
the highest priority among node b's one-hop neighbors. The The type of node i, which is one of cluster- number next to each node is the sample priority at a partic- head, host, gateway and doorway.
ular moment. For convenience, we represent node priorities The clusterhead elected by node i.
using fractional numbers over the range [0, 1) throughout A set of clusterheads or doorways thatnode i connects to form the CDS.
this paper. The algorithms can be easily converted to inte-ger operations in practice. We discuss the computation of The energy level of node i.
node priorities in the following sections.
The speed of node i in terms of meters persecond.
Components of Node Priorities
The willingness value of node i.
Given that clusterheads provide the backbone for a num- ber of network control functions, their energy consumptionis more pronounced than that of ordinary hosts. Low-energynodes must try to avoid serving as clusterheads to save en-ergy. However, to balance the load of serving as cluster- MINIMAL DOMINATING SET
heads, every node should take the responsibility of servingas a clusterhead for some period of time with some likeli- Clusterhead Election Approach
hood. Furthermore, node mobility has to be considered in Our approach to establishing a minimal dominating set clusterhead elections, so that the MDS experiences the least (MDS) is based on three key observations. First, using ne- structural changes over time.
gotiations among nodes to establish which nodes should be To take into account the mobility and energy levels of in the MDS incurs substantial overhead when nodes move nodes in their election as members of the MDS, we define the two-hop neighbor information needed to assign node pri- Clusterhead Election Algorithm
orities as consisting of three components: (a) the identifiers As stated before, time is slotted, and the time parameter of the node's neighbors, (b) the present time, and (c) a "will- is represented by the current time-slot number. Node priori- ingness" value assigned to a node as a function of its mobility ties are computed using a pseudo-random number generator and energy level.
based on the node identifiers, their willingness values, and We denote the willingness value of node i by Wi, the speed the current time.
of node i by a scalar si ∈ (0, ∞) in terms of meters per The priorities of nodes change periodically to trigger clus- second, and the remaining energy on node i as Ei ∈ [0, 1).
terhead re-elections aimed at distributing the role of cluster- The willingness Wi = f(si, Ei) is a function that should be heads among nodes. The recomputation period is denoted defined according to the following criteria: by T and is a multiple of time slots and is the same for allnodes in the network.
1. To enhance survivability, each node should have the The priority of each node is recomputed asynchronously responsibility of serve as a clusterhead with some non- using a time-slot offset so as to avoid synchronous sudden zero probability determined by its willingness value.
loss of the old network states. Eq. (2) is used at each nodei to compute locally its time-slot offset, which is denoted by 2. To help with the stability of the MDS and the fre- quency with which clusterhead elections must take place,the willingness value of a node should remain constantas long as the variation of the speed and energy level i.off = bHash(i) · T c of the node do not exceed some threshold values.
where the function Hash(x) is a pseudo-random number gen-erator that produces a uniformly distributed random num- 3. To avoid electing clusterheads that quickly lose con- ber over range [0, 1) based on the input bit-stream x. The nectivity with their neighbors after being elected, the floor operation gives an integer offset.
willingness value of a node should decrease drastically The recomputation of the priority of a node happens when- after the mobility of the node exceeds a given value.
ever the current time slot is a multiple of the recomputationperiod T plus the time-slot offset of the node, i.e., when 4. To prolong the battery life of a node, its willingness the current time is t = kT + i.off, and k = 0, 1, · · · . At value should decrease drastically after the remaining that time slot, the priority of node i, denoted by i.prio, is energy of the node drops below as given level.
recomputed according to the following formula: There are many possible functions that can be used to compute the willingness value of a node while adhering to i.prio = Hash(k ⊕ i) · Wi ⊕ i the above criteria. Our approach is given by Eq. (1).
where the function Hash is the same as the one defined forEq. (2), and the sign "⊕" is designated to carry out the bit-concatenation operation on its operands, and has lower order than other operations. The last concatenation with where the constants 0.9 and 2 in Eq. (1) eliminate the bound- i in the final result is included to distinguish the priorities ary conditions in the logarithmic operations. The logarith- of different nodes. Once computed, the priority of a node mic operations on the speed and the remaining energy val- remains the same during the entire recomputation period T .
ues render higher willingness values in the high energy and Because each node knows the node identifiers of its two- low speed field, while giving close to zero values in the low- hop neighborhood, node i can determine locally which other energy and high-speed region. Figure 2 illustrates the effect nodes must recompute their priorities during the same time of the two factors on the willingness values.
slot from Eq. (equation:startuptime). Because the willing-ness values are reported by nodes in its two-hop neighbor-hood, node i uses Eq. (equation:priority) to compute its Willingness value own priority and the priorities of all nodes in its two-hopneighborhood that must recompute their priorities. Because Eq. (equation:priority) renders different priority values for different node identifiers, only one node can be selected to have the highest priority during the time slot when node i must recompute its priority. Once nodes have consistent two-hop neighborhood information, if node i decides that it must become a clusterhead, its neighbors do too, because the nodes run the same algorithms using the same informa- The algorithms for determining the clusterhead status of node i are described in Figures 3 – 4 using C-style pseudo Speed (meter/second) Function Init in Figure 3 initializes the data structures
at node i. For simplicity, the energy level and speed remain Figure 2: The willingness function based on speed
constant until the beginning of the next recomputation pe- and remaining energy.
riod. The willingness value of node i is computed according
to Eq. (1) and the nodal type is initialized to Host (Init
/* Initialize */ are separated by three hops and there are no other cluster- heads between them, a node with the highest priority on the shortest paths between the two clusterheads is elected as a i.workfor = ∅; doorway, and is added to the CDS. Therefore, the addition Wi = 2log2(Ei∗0.9) log2(si+2); of a doorway brings the connected components in which the i.type = Host; two clusterheads reside one hop closer.
In the second step, if two clusterheads or one clusterhead /* Recompute priorities. */ and one doorway node are only two hops away and there for (j ∈ N1i ∪ ( k∈N1 N1k)) {
are no other clusterheads between them, one of the nodes if (t ≡ 0)
between them with the highest priority becomes a gateway j.prio = Hash(j) · Wj ⊕ j; to connect clusterhead to clusterhead or doorway to cluster- else if (t − j.off mod T ≡ 0)
head. After these steps, the CDS is formed. Figures 5 – 6 j.prio = Hash( t−j.off ⊕ specify the two steps, and the function TMPO in Figure 7
j) · Wj ⊕ j; combines all the topology management algorithms.
} /* End of Init. */
if (i.type ≡ Clusterhead)
Figure 3: TMPO function for initialization.
for (j ∈ N 1
i and j.type ≡ Clusterhead) {
lines 2-3). Node i also computes the priority for each two- for (k ∈ N 1
i and k 6= j
and k.type 6= Clusterhead) {
hop neighbor according to the recomputation period of the for (n ∈ N 1
neighbor (Init lines 4-9).
k , n.type≡Clusterhead and n 6∈ N 1
j ) { /* Case (a) in Figure 8. */ if (∃m ∈ N 1
i , {j, n} ⊆ N 1 for (j ∈ N1i ∪ {i}) {
j.ch = j; for (m ∈ N 1
i ) { /* Case (b) or (c) in Figure 8. */ /* Find j's clusterhead. */ if (n ∈ N 1
for (k ∈ N1
m and ((m.type ≡ Clusterhead) or
(∃p ∈ N 1 m, p.type ≡ Clusterhead))) if (k.prio > j.ch.prio)
j.ch = k; if (j.ch ≡ i)
for (m ∈ N 1
n) { /* Case (d) in Figure 8. */ type = Clusterhead; if ((m.prio > i.prio) or
(∃p ∈ N 1 } /* End of isClusterhead. */
m, p.prio > i.prio)) Figure 4: TMPO function for electing a clusterhead.
i.type = Doorway; i.workfor = i.workfor ∪{j, n}; Function isClusterhead in Figure 4 elects the cluster-
head of a node i, which is indicated by the field i.ch in the 21 } /* j */ neighbor data structure.
} /* End of isDoorway. */
If node i becomes a clusterhead after computing the MDS using function isClusterhead, its clusterhead-type attribute
needs to be propagated to its two-hop neighbors for further
Figure 5: TMPO function for electing a doorway.
Function isDoorway in Figure 5 determines whether node
CONNECTED DOMINATING SET
i can become a doorway for other clusterheads. To decidewhether node i becomes a doorway for clusterhead n and j, CDS Election
node i needs to assert that Because the maximum distance from a clusterhead in the 1. Clusterheads n and j are not two hops away (isDoor-
minimal dominating set (MDS) to the closest clusterhead way lines 3-7 illustrated by case (a) in Figure 8).
is three, which we prove in Theorem 2, we can derive the 2. There is no other clusterhead m on the shortest path CDS of a network by adding some nodes to the MDS, such between clusterhead n and j (isDoorway lines 8-11
that clusterheads within two or three hops are connected.
illustrated by case (b) and (c) in Figure 8).
Two other types of nodes, called doorways and gateways,are elected to derive the CDS based only on the priorities of 3. There is no other node m with higher priority than the neighbors with two hops from each node.
node i on the three-hop path between clusterhead n The CDS of a network topology is constructed in two and j (isDoorway lines 12-16 illustrated by case (d)
In the first step, if two clusterheads in the MDS in Figure 8).
if (i.type ∈ {Clusterhead, Doorway})
for (j ∈ N 1
and j.type ∈ {Clusterhead, Doorway}) {
for (k ∈ N 1
i and k 6= j and k 6∈ N 1
j and
k.type ∈ {Clusterhead, Doorway} and
(k.type 6≡ Doorway or
j.type 6≡ Doorway) { Figure 8: Four cases that may disable node i from
if (∃n ∈ N 1
k , n 6= i and
becoming a doorway
(/* Case (a) in Figure 9. */ n.type ∈ {Clusterhead, Doorway} or
/* Case (b) in Figure 9. */ n.prio > i.prio)) i.type = Gateway; i.workfor = i.workfor ∪{j, k}; 18 } /* j */ } /* End of isGateway. */
Figure 9: Two cases that disable node i from be-
coming a gateway.
Figure 6: TMPO function for electing a gateway.
are propagated only to one-hop neighbors, while the sta-tus changes from/to clusterheads are required to propagate within two hops, so as to inform other nodes when construct-ing the CDS. It is the responsibility of a neighbor protocol to i.oldType = i.type; propagate the changes in node types to the one- and two-hop neighbors in time.
The backbone topology is constructed by using links be- /* i's status changes? */ tween the elected clusterheads, doorways and gateways present in the original network topology according to the following type 6= i.oldType) } /* End of TMPO. */
R1: All links between clusterheads are kept in the back- bone topology.
Figure 7: TMPO description
R2: The one-hop links from doorways and gateways to the nodes in their respective sets workfor are kept in thebackbone topology. Some nodes in the workfor set If the three assertions are satisfied, node i becomes a door- may be outside of the one-hop neighborhood for door- way (isDoorway line 17). The attribute i.workfor is the
ways, and there are no links from the doorways to these set of clusterheads that make node i become a doorway (is-
Doorway line 18). A doorway needs to notify its one-hop
neighbors about its current status for gateway elections.
The links of the original network topology between gate- Function isGateway in Figure 6 determines whether node
ways or between doorways are not kept in the CDS. Door- i becomes a gateway to connect two clusterheads or one clus- ways are alway attached to a clusterhead on one end and terhead and another doorway, k and j (isGateway lines 3-
a gateway on the other end. Gateways are alway attached 8). According to Figure 9, if there is another clusterhead with clusterheads or doorways.
or doorway between node k and j (isGateway line 10), or
Figure 10 illustrates the backbone topology construction there is another node with higher priority than node i be- process using TMPO in four steps on a network graph gen-
tween node k and node j (isGateway line 11), node i cannot
erated by randomly placing 100 nodes over a 1000×1000 become a gateway. Otherwise, node i becomes a gateway, square meter area. The radio reception range is 200 meters and the attribute i.workfor is the set of nodes that make i for all nodes. In Figure 10 (a), every node is a host and net- become a gateway (isGateway lines 13-16).
work connectivity is very dense in some parts of the network, Function TMPO is called after every neighbor informa-
which increases the overhead of network control functions.
tion update or when the recomputation period of a neighbor In Figure 10 (b), clusterheads are elected, but are discon- starts. After calling TMPO, if node i changes its role be-
nected from each other. Hosts are attached to their cor- tween clusterhead, doorway, gateway and host, then node responding clusterheads in their one-hop neighborhood. In i needs to propagate its new status to its neighbors. Note Figure 10 (c), gateways are elected. Without adding door- that the status changes to and from doorway and gateway ways for extending the coverage of clusterheads, we see that The original network topology The minimal dominating set (MDS) the network for connectivity and data forwarding purposes among hosts and routers. The number of active nodes can be dramatically smaller than the total number of nodes in the network. The CDS of an ad hoc network provides the back- bone of the network for this purpose, where clusterheads are responsible for receiving or delivering data packets to hosts under their dominance, while gateways and doorways forward data packet between clusterheads for which they Another application for the CDS problem consists of car- rying out reliable broadcasts in ad hoc networks, such thateach message from a source node reaches every other net- Addition of gateways alone Addition of doorways and gateways (CDS) work node reliably. Without proper control, broadcast mes- sages may incur very high overhead as each node is exposed to multiple copies of the same message. Utilizing the CDS in the network, only clusterheads need to broadcast, while the intermediate doorways and gateways relay the message between gateways and can use more reliable mechanisms to Energy consumption by nodes in an ad hoc network is due to the data flows generated or forwarded by each node, Figure 10: A network topology control example.
as well as the signaling overhead of network control proto-cols. In a network with a flat network topology management,nodes can consume large amounts of energy by maintaining adding gateways alone cannot guarantee the connectivity of routing information exchanges with every neighbor.
the backbone topology. Once the doorways are added af- To balance energy consumption as well as to maintain net- ter the clusterheads election in Figure 10 (d), gateways are work connectivity, TMPO elects a backbone of routers (the
again inserted, and the CDS is formed over the original net- CDS) to serve the network routing functionalities based on work topology using the CDS construction rules.
their energy levels and mobility. Only clusterheads, door- The stability of the backbone topology is an important ways and gateways need to stay awake continuously. Hosts goal in TMPO, and is achieved by the following mecha-
that are not serving data forwarding can be put in sleep- nisms. First, the period of willingness adjustment is long ing mode so as to conserve energy and prolong the network to allow enough time to adjust to clusterhead changes. Sec- lifetime. Routers in the CDS buffer information for sleeping ond, the willingness value is directly related with the speed hosts until they wake up and receive the packets. If a back- of nodes. Fast moving nodes get fewer chances to become bone router becomes a host and the buffered data are not a clusterhead than slowly moving or static nodes, thus de- delivered to the destination host yet, the backbone router creasing the possibility of topology changes due to mobility.
can keep holding the data and deliver or delegate them later.
Third, the willingness value is also related to the remainingenergy of the node, so that the clusterhead role is sustained longer and fewer topology changes happen. Forth, except forclusterheads, doorways and gateways are not put in the rout- Theorem 1. The set of clusterheads elected by the algo- ing tables built over the CDS, but only provide links between rithm is a dominating set. clusterheads. When doorways or gateways fail, there can be Proof: By the definition of a dominating set, a node is
other hosts taking over the role, without any routing up- either a dominator itself, or is a one-hop neighbor of a dom- dates. The transient period between clusterhead connection inator. Because a node either has the highest priority among re-establishment is equal to the delay of the neighbor pro- its one-hop neighbors such that it becomes a dominator it- tocol propagating one-hop neighbor updates. Lastly, nodes self, or has a neighbor with the highest priority among the change their priorities asynchronously, thus avoiding syn- one-hop neighbors of the node, which elects the neighbor as a chronization problems from clusterhead changes and routing dominator, the network always has a dominating set elected after function isClusterhead is called at each node.
Application of Topology Management
Theorem 2. In a dominating set, the maximum distance to another closest clusterhead from any clusterhead is three. The CDS obtained from TMPO reduces the topology
information at each node with just enough links to main-tain network connectivity. Previous research has gone down Proof: We prove the theorem by contradiction. Assume
this path using different topology control algorithms, and that the maximum distance from a clusterhead a to the applied the derived backbone topology to efficient data for- closest clusterhead e is four, as illustrated in Figure 11, ac- warding or the provision of QoS services [25, 8].
cording to Theorem 1, node c must have been covered by aclusterhead f, which is one hop closer to a than e, thus con- Efficient Routing tradicting the assumption that e is the closest clusterhead Routing information requires only enough active nodes in to a.
PERFORMANCE ANALYSIS OF TMPO
CLUSTERHEAD ELECTION
Guha and Khuller [14] and Jia et al. [16] evaluated the performance of algorithms for constructing dominating setsbased on the performance ratio, which is the approximate Figure 11: The maximum distance between the clos-
ratio of the cost of a solution derived from an algorithm to the optimal one. In contrast, we evaluate the performance
of TMPO by the percentage of nodes being elected as clus-
Theorem 3. Two clusterheads that are within three hops from each other are connected by a path in the CDS. Despite the fact that TMPO actually provides a node-
weighted MDS election algorithm based on the willingness Proof: There are three cases to consider for the proof ac-
parameter, the performance of the specified algorithm can cording to the number of hops between the two clusterheads.
be evaluated regardless of such weights. Therefore, we con-sider the case in which all nodes have the same willingness 1. The two clusterheads are one hop away. In this case, to become a clusterhead, that is, Wi = 1, ∀i ∈ V . Further- they are directly connected according to rule R1 in the more, we analyze the probability of a node being elected as a clusterhead with the simplifying assumptions that all nodes 2. The two clusterheads are two hops away. In this case, have the same effective transmission range r to communi- one of the intermediate nodes between the clusterheads cate with each other, and that the network is created by either is a clusterhead itself, or becomes a gateway uniformly placing an infinite number of nodes on an infinite according to the isGateway algorithm. Because the
2-dimensional plane with average node density ρ.
link between gateway and clusterhead is kept in the With the above assumptions, the number of nodes within backbone topology by rule R2, the two clusterheads an area of size S is a random variable following a Poisson are connected in the CDS.
distribution as given in Eq. (4).
3. The two clusterheads are three hops away.
case, if there is any clusterhead on the shortest paths p(k, S) = between the two clusterheads, then the connectivity problem is converted to the previous two cases. Oth-erwise, one of the nodes on the shortest paths has Because node priorities are evenly distributed over (0, 1] to become a doorway according to function isDoor-
according to Eq. (3), nodes have equal chances to become way. Because the doorway is treated like a clusterhead
clusterheads using TMPO. That is, the probability of a
when electing gateways (function isGateway), one of
node winning over k other contenders is the nodes between the newly elected doorway and the For convenience, the variable T (N) and U(N) are intro- other clusterhead must become a gateway. Because duced to denote two probabilities when the number of con- the link between the doorway and the clusterhead for tenders k follows a Poisson distribution with mean N. T (N) which it works is kept in the backbone topology as well denotes the probability of a node winning among its con- as the links from the elected gateway to the doorway tenders. Because the number of contenders follows a Poisson and the clusterhead (rule R2), the path between the distribution with mean N and all nodes have equal chances two clusterheads is preserved in the backbone topol- of winning, the probability T (N) equals ogy. That is, the two clusterheads are still connectedvia clusterheads, doorways or gateways in the CDS. 2 eN − 1 − N T (N) = Theorem 4. After TMPO terminates, the CDS has the
k + 1 k! same number of connected components as the original graph. Note that k starts from 1 in the expression for T (N), becausea node with no contenders does not win at all. U(N) is the Proof: We prove that any pair of clusterheads that are
probability that a node has at least one contender, which is connected in the original graph is still connected via a path simply 1 − e−N .
in the CDS after TMPO terminates.
In addition, N1 is introduced to denote the average num- Suppose that the two clusterheads are v0 and vn, and the ber of one-hop neighbors of a node, which according to the path between them is p = v0 · v1 · v2 · · · vn−1 · vn in the assumptions we have made equals original graph. For the endpoints of any link vi · vi+1 onthe path p, where i = 0, 1, · · · , n − 1, there exist one or two N1 = ρπr clusterheads that cover node vi and vi+1. For the case ofone clusterhead, the clusterheads of vi and vi+1 are trivially As mentioned before, a node i becomes a clusterhead if connected. For the case of two clusterheads, the distance either of the following two conditions holds: between the clusterheads is less than three. From Theorem3, it follows that the two clusterheads are still connected in 1. Node i has the highest priority among its one-hop the backbone topology. Therefore, there is a path between v0 and vn that is composed of clusterheads of the nodes onthe path p and other clusterheads, doorways or gateways 2. Node i does not have the highest priority in its one- that connect them. That is, v0 and vn are still connected in hop neighbors, but has the highest priority among the one-hop neighbors of one of i's own one-hop neighbors.
For the first condition, the probability is: probability of node i becoming a clusterhead is thus: pch = p1 + (1 − p1) · p4 e−N1 · N1 − 1 1 − U(N1) · T (N1) + e−N1 For the second condition to be satisfied, it must be true [U(A(t)) − T (A(t))]2tdt . that node i has a one-hop neighbor with higher priority, while node i also has the highest priority around one of its Nodes are homogeneous in the randomly generated net- one-hop neighbors. Many situations can render node i as work with regard to their priority generations and one-hop the clusterhead in this case. Therefore, we have to consider neighbor information. Therefore, the probability of becom- the lower bound of the probability that node i becomes a ing a clusterhead is also the same for all nodes. Given an clusterhead by considering only a single one-hop neighbor j area with N nodes in an infinitely large network with uni- that makes node i a clusterhead. Under this simplification, form node density, the expected size of the MDS in the area the geometric relation between node i and node j is shown in Figure 12, and the distance between them is denoted bytr.
MDSN = N · pch . To validate the result in Eq. (5) with the performance of function isClusterhead, we randomly created a number
of networks by placing 100 nodes onto a 1000×1000 square
meter plane. The opposite sides of the square are seamed
together so as to emulate the infinite plane. All nodes havethe same transmission range, which increases from 1 to 400 meters in the individual experiment setting so as to evaluate
the performance of TMPO at different node densities.
A near-optimum MDS election is also carried out for com- Figure 12: Clusterhead election.
parison purposes in the same network topology. The near-
optimum election algorithm is based on the aforementioned
Max Degree algorithm, eliminating redundant clusterheads
Accordingly, we need to compute the probability of node i having the highest priority within the one-hop neighbors ofnode j, and the probability of node i having lower priority Comparisons between analysis and simulation Performance Ratio in the portion of its one-hop neighborhood outside of node MDS in TMPO vs. analysis j's coverage (the shaded area in Figure 12).
Near−optimum vs. analysis Denote the number of nodes in the shaded area by A(t).
A(t) = 2ρr − a(t) , Performance ratio Number of clusterhead where a(t) = arccos t − t . Therefore, the prob- Transmission range (m) Transmission range (m) ability of node i having a lower priority than the nodes inthe shaded area is Figure 13: Comparison between theoretical analyses
= U(A(t)) − T (A(t)) . Because we ran the experiments in different network sce- narios for many times, and recomputed the MDS at each In addition, node i should have the highest priority among experiment setting, we achieve the average performances of node j's one-hop neighborhood, of which the probability is: both algorithms. The analytical results and the results from the experiments of TMPO and the near-optimum MDS al-
N1 − 1 gorithm are shown in Figure 13. As the results in the left · T (N1) + e−N1 . portion of Figure 13 illustrate, the number of elected clus-terheads drops quickly as the node transmission range in- Because the probability density function of parameter t is creases, because clusterheads have larger and larger cover- p(t) = 2t, the probability that node i becomes a clusterhead can be obtained by multiplying the above two probabilities The performance ratios of TMPO vs.
and integrating over the range t ∈ (0, 1]: model, and the near-optimum MDS algorithm vs. the an-alytical model are shown in the right portion of Figure 13.
N1 − 1 It appears that the near-optimum MDS algorithm performs p2 · p3 · 2tdt = · T (N1) + e−N1 close to the lower-bound of the MDS, while the performance of TMPO digresses when the node transmission range in-
[U(A(t)) − T (A(t))]2tdt . creases. The performance ratio between TMPO and the
analytical results offsets from 1 by as far as 48%, and is due Because the two conditions are mutually exclusive, the to the simplifications made in our analytical model.
In TMPO, the node priority recomputation period is one
We compare the performance of TMPO with the opti-
mum topology management algorithm and four other topol- Different types of nodes consume energy at different rates.
ogy management algorithms based on different heuristics us- We ignore the energy consumed due to local computations, ing simulations. To establish a fair comparison among these but assume that the energy consumption rate is only depen- algorithms, some MDS stability optimizations and cluster- dent on the type of the node. A host consumes 0.6% of the head negotiation procedures presented in the original papers total energy per minute in these algorithms, a clusterhead are omitted. The algorithms differ from one another only in consumes 3%, and a doorway or a gateway consumes 2.4%.
the clusterhead election process, and use the same proce- Every node starts with an energy level of 1 at the beginning dure to connect clusterheads using doorways and gateways of each simulation.
to form the CDS, which does not need negotiation packets The algorithms are compared using six different metrics, and actually improves the performance of the original algo- and the results are shown in Figures 14-16: rithms based on other heuristics. The following five schemes
are compared with TMPO:
Speed Limit=5 meter/second Speed Limit=50 meter/second OPTIMUM: This is a near-optimum approach that
uses global topology information, the MDS is con- MOBICLoad Balance structed by selecting nodes with the highest degree one by one until all nodes outside the MDS are cov- ered by the MDS. Individual nodes with low degree in the MDS are inspected and eliminated from the MDSif the node and its dominated nodes are covered by other clusterheads in the MDS.
Transmission Range (meter) Transmission Range (meter) (a) Simulation duration.
• Lowest ID [1, 3, 11, 13, 19]: In this approach, the
Speed Limit=5 meter/second Speed Limit=50 meter/second node identifier is used to elect MDS members. A node is elected into the MDS if it has the lowest identifier in the one-hop neighborhood of itself or one of its one-hop MOBICLoad Balance • Max Degree [14, 16, 25]: In this approach, a node
Avg Energy Leftover Avg Energy Leftover is elected into the MDS if it has the highest degree inthe one-hop neighborhood of itself or one of its one-hop Transmission Range (meter) Transmission Range (meter) Speed Limit=5 meter/second Speed Limit=50 meter/second • MOBIC [7]: In this approach, each node computes a
mobility metric based on the received-signal strength variations from its one-hop neighbors. A node becomes a clusterhead if it has the lowest mobility metric in the one-hop neighborhood of itself or one of its one-hop Energy Std Deviation Energy Std Deviation • Load Balance [2]: This approach is similar to Low-
est ID except that it is based on a virtual identifier
Transmission Range (meter) Transmission Range (meter) (VID) assigned to each node. The VID of a node in- (b) The mean energy left and its standard deviation.
creases every time slot if the node is a host, or remainsconstant if the node is a clusterhead. Each clusterhead Figure 14: Simulation duration and energy left.
runs a budget that decreases every time slot. A clus-terhead resets its VID to 0 and returns to host status The simulations stop once any node runs out of energy in when the budget runs out, thus providing load balanc- the network. The simulation duration (Figure 14(a)) mea- ing between network nodes.
sures the load balancing capability of the heuristics to pro-long the system lifetime by rotating the clusterhead roles The simulations are carried out in ad hoc networks gen- between network nodes. MOBIC and Lowest ID perform
erated over a 1000×1000 square meter area with 100 nodes the worst, because the clusterheads are mostly fixed over moving in random directions at random speeds. In order certain nodes throughout the simulations. In Lowest ID,
to simulate infinite plane, the opposite sides of the area is the fact that the node with the lowest identifier is always in seamed together so that the simulation plane forms a torus.
the MDS terminates the simulations in fixed time. TMPO
To mobility scenarios are simulated, of which the speed is is one of the best heuristics.
selected from 0 to 5 meters/second in low mobility scenar- The mean and the standard deviation of the energy left ios, or from 0 to 50 meters/second in high mobility scenar- per node when the simulation is over (Figure 14 (b)) indi- ios. In each mobility scenario, the radio transmission range cate the load balancing capability of the heuristics. After is set at different values in each simulation, chosen from each simulation, TMPO leaves the network nodes with the
100 to 500 meters, so as to demonstrate the effects of the least energy and the lowest standard deviation because of one-hop neighborhood density in the clusterhead elections.
its energy-awareness when selecting the MDS, while Low-
est ID performs the worst because it always has nodes that
of mobility.
The cluster membership change rates align are always or never elected to the MDS. The curves peak at to the clusterhead change rates of the examined heuristics.
transmission range 300- or 350-meter because the two-hop TMPO, Lowest ID and Load Balance still perform the
neighborhood of each node begins to overlap in the oppo- best in both high and low mobility scenarios.
site directions on the plain, which renders less clusterheadsand more opportunities to rotate clusterhead roles for some Speed Limit=5 meter/second Speed Limit=50 meter/second Speed Limit=5 meter/second Speed Limit=50 meter/second Max DegreeMOBICLoad Balance Transmission Range (meter) Transmission Range (meter) Avg Clusterhead Number Avg Clusterhead Number Figure 16: Combined evaluations.
Transmission Range (meter) Transmission Range (meter) (a) Average number of clusterheads.
Given the above metrics, it is not easy to see the ad- vantages of different heuristics. The combined metric (Fig- Speed Limit=5 meter/second Speed Limit=50 meter/second ure 16) is the product of the average energy, its standard deviation, the average number of clusterheads, the cluster-head change rate and the cluster membership change rate of the respective simulations. Although it is meaningless to simply multiply several independent metrics, the prod- uct fairly compares the overall performance if the individ- Lowest IDMax Degree ual metrics are equally important. The lower the combined MOBICLoad Balance metric of a heuristic, the better the heuristic performs in Clusterhead Change (per second) Clusterhead Change (per second) terms of the clusterhead load-balancing capability and the Transmission Range (meter) Transmission Range (meter) MDS/CDS stability. As shown in Figure 16, TMPO per-
(b) Clusterhead change rate.
forms near, if not always, the best among all heuristics in
both low mobility and high mobility scenarios. Load bal-
Speed Limit=5 meter/second Speed Limit=50 meter/second ance is the second best in general. The simulations favored
Load balance, because it assumes that all nodes start with
the same energy level [2], which is the setup of the simula-
Overall, when the mobility increases from 5 meter/second to 50 meters per second, TMPO shows better load balanc-
Lowest IDMax Degree ing capability (Figure 14) and higher topology maintenance MOBICLoad Balance stability (Figure 16).
Cluster Membership Change (per second) Cluster Membership Change (per second) Transmission Range (meter) Transmission Range (meter) (c) Cluster membership change rate.
We have presented TMPO, a novel energy-aware topol-
Figure 15: Statistics about clusterheads.
ogy management approach based on dynamic node priorities
in ad hoc networks. TMPO consists of two parts that im-
The average number of clusterheads (Figure 15 (a)) is plement the MDS and CDS elections, respectively. TMPO
measured each time slot when clusterhead recomputation builds a stable and energy-aware CDS from the MDS to sim- happens. As Figure 15 (a) shows, all heuristics perform al- plify the topology information for sufficient network connec- most identically, which suggests that the MDS cardinality tivity and efficient data communication. Compared to five can hardly prove the advantage of topology management prior heuristics of MDS and CDS elections in ad hoc net- algorithms. It is the topology stability and load-balancing works, TMPO offers four key advantages. First, TMPO
features of the algorithms that make the difference.
obtains the MDS and CDS of the network without any nego- The clusterhead change rate (Figure 15 (b)) measures the tiation stage; only two-hop neighbor information is needed.
stability of the MDS in a mobile network. TMPO, Low-
Second, TMPO allows nodes in the network to periodi-
est ID and Load Balance are the best performing, be-
cally recompute their priorities, so as to balance the cluster- cause they depend on relatively static attributes for cluster- head role and prolong the battery life of each node. Third, head election, such as node identifiers and priorities which TMPO introduces the willingness value of a node, which
change less frequently than node locations. OPTIMUM,
decides the probability of the node being elected into the Max Degree and MOBIC perform the worst because the
MDS according to the battery life and mobility of the node.
MDS elections depend on the volatile mobility and network Fourth, TMPO introduces doorway concept for the CDS
topology of ad hoc networks.
in addition to the well-known gateway and clusterhead con- The cluster membership change rate (Figure 15 (c)) mea- sures the stability of network connections in the presence A key contribution of this work consists of converting the static attributes of a node, such as node identifier, into a NP-completeness. Freeman, Oxford, UK, 1979.
dynamic control mechanism that incorporates the three key [13] M. Gerla and J.T.C. Tsai. Multicluster, mobile, factors for topology management in ad hoc networks — the multimedia radio network. Wireless Networks, nodal battery life, mobility, and load balancing. Although existing proposals have addressed all these aspects, TMPO
[14] S. Guha and S. Khuller. Approximation algorithms for constitutes a more comprehensive approach.
connected dominating sets. Algorithmica, 20, unique in that the election of the MDS is locally determined, (no.4):374–87, Apr. 1998. Springer-Verlag.
without the need for any negotiation phase.
[15] L. Hu. Topology control for multihop packet radio networks. IEEE Transactions on Communications, 41(10):1474–81, Oct. 1993.
[1] A. Amis, R. Prakash, T. Vuong, and D.T. Huynh.
[16] L. Jia, R. Rajaraman, and T. Suel. An Efficient MaxMin D-Cluster Formation in Wireless Ad Hoc Distributed Algorithm for Constructing Small Networks. In Proceedings of IEEE Conference on Dominating Sets. In Twentieth ACM Symposium on Computer Communications (INFOCOM), Mar. 1999.
Principles of Distributed Computing PODC'01, [2] A.D. Amis and R. Prakash. Load-balancing clusters in Newport, Rhode Island, Aug. 26-29 2001.
wireless ad hoc networks. In Proceedings 3rd IEEE [17] P. Krishna, N. Vaidya, M. Chatterjee, and Symposium on Application-Specific Systems and D. Pradhan. A cluster-based approach for routing in Software Engineering Technology, pages 25–32, Los dynamic networks. ACM SIGCOMM Computer Alamitos, CA, Mar. 24-25 2000.
Communication Review, pages 49–65, Apr. 1997.
[3] D.J. Baker and A. Ephremides. The architectural [18] L. Li, V. Bahl, Y.M. Wang, and R. Wattenhofer.
organization of a mobile radio network via a Distributed Topology Control for Power Efficient distributed algorithm. IEEE Transactions on Operation in Multihop Wireless Ad Hoc Networks. In Communications, COM-29(11):1694–701, Nov. 1981.
Proceedings of IEEE Conference on Computer [4] S. Banerjee and S. Khuller. A Clustering Scheme for Communications (INFOCOM), Apr. 2001.
Hierarchical Control in Multi-hop Wireless Networks.
[19] C.R. Lin and M. Gerla. Adaptive Clustering for In Proceedings of IEEE Conference on Computer Mobile Wireless Networks. IEEE Journal on Selected Communications (INFOCOM), Anchorage, Alaska, Areas in Communications, 15(7):1265–75, Sep. 1997.
[20] S. Narayanaswamy, V. Kawadia, R. S. Sreenivas, and [5] L. Bao and J.J. Garcia-Luna-Aceves. A New P. R. Kumar. Power Control in Ad-Hoc Networks: Approach to Channel Access Scheduling for Ad Hoc Theory, Architecture, Algorithm and Implementation Networks. In Proc. ACM Seventh Annual of the COMPOW Protocol. In Proceedings of the International Conference on Mobile Computing and European Wireless Conference – Next Generation networking, Rome, Italy, Jul. 16-21 2001.
Wireless Networks: Technologies, Protocols, Services [6] L. Bao and J.J. Garcia-Luna-Aceves. Transmission and Applications, pages 156–162, Florence, Italy, Feb.
Scheduling in Ad Hoc Networks with Directional Antennas. In Proc. ACM Eighth Annual International [21] R. Prakash. Unidirectional links prove costly in Conference on Mobile Computing and networking, Wireless Ad-Hoc Networks. In Proceedings of the Atlanta, Georgia, USA, Sep. 23-28 2002.
Discrete Algorithms and Methods for Mobile [7] P. Basu, N. Khan, and T. D.C. Little. A Mobility Computing and Communications - DialM, Seattle, Based Metric for Clustering in Mobile Ad Hoc WA, Aug. 20 1999.
Networks. In International Workshop on Wireless [22] R. Ramanathan and R. Rosales-Hain. Topology Networks and Mobile Computing (WNMC2001), Control of Multihop Wireless Networks using Scottsdale, Arizona, Apr. 16-19 2001.
Transmit Power Adjustment. In Proceedings of IEEE [8] B. Chen, K. Jamieson, H. Balakrishnan, and Conference on Computer Communications R. Morris. Span: an Energy-Efficient Coordination (INFOCOM), page N.A. IEEE, Mar. 26-30 2000.
Algorithm for Topology Maintenance in Ad Hoc [23] R. Ramanathan and M. Steenstrup.
Wireless Networks. In Proc. 7th ACM MOBICOM, Hierarchically-organized, multihop mobile wireless Rome, Italy, Jul. 2001.
networks for quality-of-service support. Mobile [9] C.C. Chiang, H.K. Wu, W. Liu, and M. Gerla.
Networks and Applications, 3(1):101–19, 1998.
Routing in clustered multihop, mobile wireless [24] P. Sinha, R. Sivakumar, and V. Bharghavan.
networks with fading channel. In IEEE Singapore Enhancing ad hoc routing with dynamic virtual International Conference on Networks SICON'97, infrastructures. In Proceedings of IEEE Conference on pages 197–211, Singapore, Apr. 14-17 1997.
Computer Communications (INFOCOM), pages [10] T. Clausen, P. Jacquet, A. Laouiti, P. Muhlethaler, 1763–72, Anchorage, AK, USA, Apr. 22-26 2001.
a. Qayyum, and L. Viennot. Optimized Link State [25] R. Sivakumar, P. Sinha, and V. Bharghavan. CEDAR: Routing Protocol. In IEEE INMIC, Pakistan, 2001.
a core-extraction distributed ad hoc routing [11] A. Ephremides, J. E. Wieselthier, and D. J. Baker. A algorithm. IEEE Journal on Selected Areas in design concept for reliable mobile radio networks with Communications, 17(8):1454–65, Aug. 1999.
frequency hopping signaling. Proc. of IEEE, [26] H. Takagi and L. Kleinrock. Optimal transmission 75(1):56–73, Jan. 1987.
ranges for randomly distributed packet radio [12] M.R. Garey and D.S. Johnson. Computers and terminals. IEEE Transactions on Communications, intractability. A guide to the theory of 32(3):246–57, Mar. 1984.

Source: https://ccrg.soe.ucsc.edu/publications/bao.mobihoc03.pdf