## 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

*gateway*s, 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

*N*1

*i*. 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 node

*i *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 =

*b*Hash(

*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 ∈ N*1

*i ∪ *(

*k∈N*1

*N*1

*k*))

*{*
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 ∈ N*1

*i ∪ {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 ∈ N*1

*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

*doorway*s and

*gateway*s,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,

*N*1 is introduced to denote the average num-
Suppose that the two clusterheads are

*v*0 and

*vn*, and the
ber of one-hop neighbors of a node, which according to the
path between them is

*p *=

*v*0

*· v*1

*· v*2

*· · · 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

*N*1 =

*ρπ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

*v*0 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,

*v*0 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 *=

*p*1 + (1

*− p*1)

*· p*4

*e−N*1

*·*
*N*1

*− *1
1

*− U*(

*N*1)

*· T *(

*N*1) +

*e−N*1
For the second condition to be satisfied, it must be true
[

*U*(

*A*(

*t*))

*− T *(

*A*(

*t*))]2

*tdt .*
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 by

*tr*.

* 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-

*N*1

*− *1
gorithm are shown in Figure 13. As the results in the left

*· T *(

*N*1) +

*e−N*1

*.*
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*) = 2

*t*, 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.

*N*1

*− *1
It appears that the near-optimum MDS algorithm performs

*p*2

*· p*3

*· *2

*tdt *=

*· T *(

*N*1) +

*e−N*1
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*))]2

*tdt .*
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

Focus on Life Science Compliance: The Evolution of Medical Affairs DepartmentsBy Krist Werling, Hol y Carnel , and Drew McCormick. McGuireWoods LLP, Chicago, IL This article addresses the evolution of medical variety of medical communications with prescribers, the provi- affairs departments and a variety of key issues that sion of grants to fund investigators studies, as well as various

CORNERSTONE RESEARCH FINANCIAL AND ECONOMIC CONSULTING AND EXPERT TESTIMONY The Economics of Irreparable Harm in Pharmaceutical Patent Litigation Rahul Guha, Cornerstone ResearchMaria Salgado, Cornerstone Research TABLE OF CONTENTS The Hatch-Waxman Act greatly simplifies the process of obtaining FDA approval for a generic drug. Under the Act, a generic company need only file an Abbreviated New Drug