﻿Minimizing Interference in Ad Hoc and Sensor Networks
Thomas Moscibroda
Computer Engineering and
Networks Laboratory, ETH Zurich
8092 Zurich, Switzerland
moscitho@tik.ee.ethz.ch
Roger Wattenhofer
Computer Engineering and
Networks Laboratory, ETH Zurich
8092 Zurich, Switzerland
wattenhofer@tik.ee.ethz.ch
ABSTRACT
Reducing interference is one of the main challenges in wireless
communication, and particularly in ad hoc networks.
The amount of interference experienced by a node v corresponds
to the number of other nodes whose transmission
range covers v. At the cost of communication links
being dropped, interference can be reduced by decreasing
the node’s transmission power. In this paper, we study the
problem of minimizing the average interference while still
maintaining desired network properties, such as connectivity,
point-to-point connections, or multicast trees. In particular,
we present a greedy algorithm that computes an
O(log n) approximation to the interference problem with
connectivity requirement, where n is the number of nodes
in the network. We then show the algorithm to be asymptotically
optimal by proving a corresponding Ω(log n) lower
bound that holds even in a more restricted interference model.
Finally, we show how the algorithm can be generalized towards
solving the interference problem for network properties
that can be formulated as a 0-1 proper function.
Categories and Subject Descriptors
F.2.2 [Analysis of Algorithms and Problem Complexity]:
Nonnumerical Algorithms and Problems—computations
on discrete structures;
G.2.2 [Discrete Mathematics]: Graph Theory—graph algorithms;
G.2.2 [Discrete Mathematics]: Graph Theory—network
problems
General Terms
Algorithms, Theory
Keywords
ad hoc networks, sensor networks, interference, approximation,
primal-dual algorithms
Permission to make digital or hard copies of all or part of this work for
personal or classroom use is granted without fee provided that copies are
not made or distributed for profit or commercial advantage and that copies
bear this notice and the full citation on the first page. To copy otherwise, to
republish, to post on servers or to redistribute to lists, requires prior specific
permission and/or a fee.
DIALM-POMC’05, September 2, 2005, Cologne, Germany.
Copyright 2005 ACM 1-59593-092-2/05/0009 ...$5.00.
1. INTRODUCTION AND RELATED WORK
The advent of wireless communication in almost all aspects
of daily life has not only spawned a multi-billion dollar
market, but has also changed people’s lifestyle. While
heterogenous cellular networks have become omnipresent, a
novel, complementing network paradigm has been rapidly
emerging in recent years. Ad hoc and sensor networks consist
of autonomous devices that can communicate via shortrange
radio, without any a-priori built-in infrastructure. If
two nodes are not within mutual transmission range, they
communicate through intermediate nodes relaying their message.
In view of the great potential of ad hoc and sensor networks
in a variety of application scenarios such as disaster
relief, community mesh networks, monitoring and surveillance,
or data gathering, it is not surprising that there has
been a flurry of research activity in the field.
One of the main challenges in both models of wireless
communication is interference. Informally speaking, a node
a may interfere with another node b if a’s interference range
unintentionally covers b. Consequently, the amount of interference
that b experiences is the number of such nodes
a. In frequency division multiplexing cellular network, reducing
the amount of interference results in fewer channels
which, in turn, can be exploited to increase the bandwidth
per frequency channel. In systems using code division multiplexing,
small interference helps in reducing coding overhead.
In the context of ad hoc and sensor networks, there
is an additional motivation for keeping interference low. In
these networks consisting of battery-driven devices, energy
is typically scarce and the frugal usage of it is critical in order
to prolong system operability and network lifetime. In
addition to enhancing throughput, minimizing interference
may help in lowering node energy dissipation by reducing
the number of collisions (or the amount of energy spent in
an effort of avoiding them) and consequently retransmissions
on the media access layer.
Interference can be reduced by having nodes send with less
transmission power. The area covered by the smaller transmission
range will contain fewer nodes, yielding less interference.
On the other hand, reducing the transmission range
has the consequence of communication links being dropped.
However, there is surely a limit to how much the transmission
power can be decreased. In ad hoc networks, if the
node’s transmission ranges become too small and too many
links are abandoned, the network may become disconnected.
Hence, transmission ranges must be assigned to nodes in
such a way that the desired global network properties are
maintained.The most basic network property that we seek to maintain
is connectivity. That is, we want the transmission ranges to
be large enough such that there exists a communication path
between all pairs of nodes in the network. However, more
elaborate network properties such as multicast connectivity,
spanning subgraphs with limited stretch factor, or simultaneous
point-to-point connections between pairs of nodes are
not only conceivable, but practically relevant. Obviously,
there exists a trade-off between interference reduction on
the one hand and the maintenance of these properties on the
other hand. This allows us to formulate a clear-cut combinatorial
optimization problem for each property of the form:
assign transmission ranges to nodes such that the resulting
communication graph satisfies the network property, and the
induced interference is minimized.
In the ad hoc network community, much effort has been
invested in finding network structures having desirable properties
such as sparseness or low node-degree, e.g. [17, 14,
12, 13, 9]. Most protocols adopt structures from the field of
computational geometry, focusing on preserving energy efficient
paths or computing planar subgraphs in order to facilitate
routing [1]. Yet, in spite of its practical importance,
there has been virtually no algorithmic work dealing with interference
reduction explicitly. Instead, it has been assumed
that the above mentioned traditional network structures
(which guarantee sparseness and low node-degree) also help
in confining interference. By disproving this long-standing
conjecture, a recent paper by Burkhart et al [2] has changed
the focus in the wireless networking community towards an
explicit study of interference in ad hoc radio networks [7, 16,
18]. The work of [2] is of practical nature and verifies the
efficiency of the proposed solution by means of simulation.
A recent algorithmic work is [18] in which the problem of
minimizing the maximum interference is studied. For the
special case when the nodes are located on the Euclidean
line, [18] presents an O( 4√ n) approximation algorithm. For
a different, less robust link-based definition of interference,
the work of [16] presents optimal or approximate solutions
of interference reduction. As for the node-based definition
studied in this paper, [16] proposes a heuristic, but without
providing analytic approximation guarantees.
The reason why interference problems are difficult to track
in practice and challenging from a theoretical point of view
is their somewhat counter-intuitive behavior. Consider for
instance the simple network shown in Figure 1 consisting of
nodes a1, . . . , an on a line [18].
1 2 4 8 16
01 01
01
01
01
01
000000000000000000000000000000000000
111111111111111111111111111111111111 0000000000
1111111111
01
01
a a
1 2
01
a
3
01
a
4
Figure 1: Example with nodes ai being located at
position pos(ai) = 2 i , i = 1, . . . , n.
Surprisingly, connecting the network in the obvious and
intuitive way (each node connects to its left and right neighbor)
produces a catastrophic result. Specifically, connecting
the network linearly leads to linear interference, meaning
that on average every node is disturbed by n/2 other nodes.
In contrast, our approximation algorithm proposed in Section
3 yields an asymptotically optimal solution in which the
average interference experienced by nodes is in Θ( √ n).
01
a
5
01
a
6
Moreover, it is intriguing that all commonly used structures
such as the minimum spanning tree, shortest path
trees, or relative neighborhood graphs produce the same
linear list solution. In fact, any solution that includes the
nearest neighbor forest is asymptotically worst possible. The
downright failure of all these orthodox geometric/graph theoretical
structures highlights the need for a different structuring
of the communication graph in order to reduce interference
explicitly. Ideally, such a structure for reducing
interference combines the conflicting characteristics of both
clustering (only few nodes have long transmission range)
and traditional approaches seeking sparseness and low nodedegrees.
Informally, the algorithm we present in Section 3
constructs such a hybrid structure, reconciling the two conflicting
aims.
In the literature on ad hoc networks, it is sometimes assumed
that the coverage area of omnidirectional antennas
form a clear-cut disk. Unfortunately, practical measurements
show that modeling the coverage area by disks is far
from realistic. In addition to inaccuracies of the antenna
itself, the presence of obstacles to the propagation of electromagnetic
signals can result in coverage areas that hardly
resemble disks. In this paper, we therefore study the interference
problem in a more general model.
We start out with the general interference problem which
we model as a network property Φ and a point-set S = A∪P
consisting of active nodes A and passive nodes P . Modeling
the scenario exhibited in cellular networks or heterogenous
two-tier ad hoc networks, nodes in set A need to maintain
property Φ in the network, while interference is exhibited at
nodes in P . For each transmission range chosen by a node
a ∈ A, there is a (monotonously increasing) set of nodes
R that it covers. The interference of a node p ∈ P is the
number of nodes a ∈ A whose transmission range includes
p. The average interference of a solution is the sum over all
these interferences, divided by the number of passive nodes.
While modeling signal propagation by clear-cut disks is
too idealistic, resorting to an abstract graph model in its full
generality may be overly pessimistic. An intermediate model
that we choose to study is therefore the metric case in which
the transmission range corresponds to a distance, and a node
interferes with all nodes being inside its transmission range.
Besides this distinction between the non-metric and metric
model, we additionally study another, orthogonal variant of
the problem, the so-called ad hoc model. In these models,
there is only one kind of node which experiences interference
and is both responsible for maintaining network properties.
Surprisingly, we prove in this paper that from an approximation
point of view, the general graph model and the metric
model are equally hard. Specifically, for the basic connectivity
property, we prove that a greedy algorithm achieves an
approximation ratio of O(log n) in the general interference
problem formulation. We then establish that this bound is
asymptotically tight by presenting an Ω(log n) approximation
lower bound that holds even in the restricted ad hoc
metric case. Finally, we also show how various other network
properties can be solved. These include properties that
can be modelled as 0-1 proper functions [8].
In fact, the upper bounds of some of the interference problems
studied in this paper have been obtained earlier in an
entirely different context. Particularly, the authors of [3, 4]
study the problem of reducing the total amount of energy
spent by the nodes in wireless ad hoc networks, while keep-ing connectivity properties. By transforming the network
instances of [3, 4] properly, their greedy algorithms can also
be used to obtain O(log n) approximation ratios for the basic
connectivity interference problem [3], as well as some of
its generalizations [4]. Therefore, these nice and elegant algorithms
for energy reduction were the first asymptotically
optimal solutions for the interference problem. In this paper,
however, we formulate and analyze the algorithms directly in
the interference model which yields a proof that is different
from [3, 4]. Additionally, our result on 0-1 proper functions
is strictly more general than the connectivity requirements
studied in [3, 4] and hence, is a true generalization of their
result.
The remainder of the paper is organized as follows. In
Section 2, we formally introduce the different models and
problem formulations. Section 3 presents the greedy algorithm
for the connectivity case. Tightness of this upper
bound is shown in subsequent Section 4 in which we present
the corresponding approximation hardness result. Section 5
generalizes the greedy algorithm to other network properties
before Section 6 concludes the paper.
2. MODELS AND DEFINITIONS
Interference problems as studied in this paper model the
situation in which a set of entities (such as nodes in a wireless
multi-hop network) need to satisfy a certain global property
Φ. We call these entities active. On the other hand, there
are passive entities that experience interference caused by
active nodes trying to fulfill property Φ. Passive entities
may or may not correspond directly to active entities. An
algorithm for the interference problem needs to assign large
enough transmission ranges to active nodes such that Φ is
fulfilled, while keeping the interference at passive nodes as
small as possible.
Metric Interference Model
General Interference Model
Ad Hoc Metric Model
Ad Hoc Interference Model
Figure 2: Relationship between interference models.
We can state the general interference problem as a tuple
(S, Φ), where S = A ∪ P is a set of nodes representing the
network entities. A corresponds to the set of active nodes
and P contains the passive nodes in the network graph. The
different transmission ranges of an active node a ∈ A are
denoted by a set R a consisting of a monotonous sequence
of inclusion sets, i.e., R a = {R a 0, R a 1, . . . , R a ka
} for ka ∈ N+ 0 ,
such that for every i and for every s ∈ S, it holds that
R s i ⊆ S and R s i−1 ⊂ R s i . For every a ∈ A, we define R a 0 to
be the empty set. Informally, R a i is the set of all (passive
and active) nodes that are disturbed/reached if a sends at
transmission level i. A power assignment r is a mapping
r : A → N + where r(a) ≤ ka for all active nodes a ∈ A.
Given a mapping r of transmission ranges to active nodes,
we can construct the resulting graph RG(A, r). In this graph,
the vertex set corresponds to the points in A; there is an
edge between two vertices a1, a2 ∈ A if and only if these
nodes are in mutual transmission range. Formally, we define
RG(A, r) = (VRG, ERG) as VRG = A and
ERG = {(a1, a2) | a1 ∈ R a2
r(a2) ∧ a2 ∈ R a1
r(a1) }.
Note that an edge between a1 and a2 exists in the resulting
graph if and only if both nodes set their transmission range to
a sufficiently high value. We call a resulting graph RG(A, r)
valid for property Φ, if and only if it satisfies property Φ.
In addition to the active nodes to which a is capable of
connecting, the set R a i contains all passive nodes that experience
interference if r(a) = i. The interference χ(p)
experienced by a passive node p ∈ P is defined as
χ(p) = |{a ∈ A | p ∈ R a
r(a)}|.
On the other hand, we say that an active node a transmitting
at power level i causes an interference of t a i , where
t a i = |R a i ∩ P |. The interference problem consists of having
the active nodes fulfill property Φ, while minimizing the
average interference experienced at passive nodes.
Model 1. In the general interference problem, we are
given a tuple (S, Φ), where S = A ∪ P is a finite set of
active and passive nodes and Φ is the property the resulting
graph is required to fulfil. We need to find a power assignment
r such that the resulting graph RG(A, r) is valid for Φ
and the average interference 1
|P |
∑
p∈P
χ(p) is minimized.
Depending on the specific application at hand, various
sub-classes of the average interference problem may be of interest.
The ad hoc interference model captures the scenario
in which there is only one kind of entity in the network, i.e.,
the set of active and passive nodes is equal.
Model 2. In the ad hoc interference problem, the set of
active and passive nodes is equal, i.e., A = P .
In the metric version of the problem, we assume points
s ∈ S to be located in a metric space (S, µ). We slightly
change the problem definition in the way that the power
assignment r maps every active node to a real value, r :
A → R + . As in [3, 4], this real value represents a node’s
transmission range. In other words, a node a ∈ A interferes
with all nodes b ∈ B whose distance to a is at most r(a). It
is clear that at the cost of a less intuitive definition, metric
interference problems could also be stated using the notion
of inclusions sets in the same way as in the general case.
Model 3. In the metric interference problem, we consider
the triple (M, Φ), where M is a finite metric space
M = (A ∪ P, µ) and Φ is the property the resulting graph is
required to fulfill. A power assignment is a function r : A →
R + of active nodes to a real value. The sets R a d are defined
as R a d = {s ′ | s ′ ∈ S, µ(a, s ′ ) ≤ d}, where d = r(a) denotes
the transmission range assigned to a.
Model 4. The ad hoc metric interference problem is a
special metric interference problem in which the set of active
and passive nodes is equal, i.e., A = P .
The relationship between the different models is shown in
Figure 2. We conclude the section with a simple Lemma
that is implicitly used throughout the paper. It says that
the total amount of interference experienced at passive nodes
p ∈ P can equivalently be measured as the amount of interference
caused by active nodes a ∈ A.Lemma 2.1. Consider an instance of the interference problem.
For any given power assignment r, it holds that
1 ∑
χ(p) =
|P |
1 ∑
t
|P |
a
r(a).
p∈P
a∈A
Proof. The proof follows from
∑
χ(p) = ∑
|{a ∈ A|p ∈ R a
r(a)}| = ∑
p∈P
p∈P
a∈A
|R a
r(a)|.
3. APPROXIMATION ALGORITHM
In this section, we present a greedy algorithm that achieves
an O(log n) approximation ratio, the same guarantee that
can be achieved by the greedy algorithms given in [3, 4].
Our solution differs in the sense that it is directly formulated
and analyzed in the interference model.
Many of the algorithmic challenges faced in designing approximation
algorithms for interference problems stem from
the fact that an edge in the resulting graph exists only if
both nodes set their transmission range to a sufficiently large
value. This leads to situations in which an edge (a1, a2) may
be cheap (interference-wise) at node a1, but costly at node
a2. Another peculiar aspect is that establishing an edge between
two nodes (a1, a2) may potentially be free of charge
if both nodes have an edge that requires higher transmission
range (this is because we demand the interference sets
R a i to be inclusion sets). Similarly, setting up an edge can
be free of charge at one node, but expensive at the other.
The combination of these characteristics render interference
problems difficult to tackle in practice and appealing for
theoretical study.
In this section, we consider the most basic graph property,
i.e., we want the resulting graph to satisfy connectivity.
Specifically, we propose a polynomial time approximation algorithm
for the general interference problem that we show
to be asymptotically optimal in Section 4.
3.1 Algorithm
Starting from a minimal, invalid power assignment, Algorithm
1 proceeds greedily and connects in every step the
most cost-efficient star of nodes in the network by appropriately
increasing the transmission ranges of the nodes in the
star. The algorithm thus increases transmission ranges of
stars until there remains only a single connected component
in the resulting graph.
Let a star B consist of a center node and one or more leaf
nodes. B denotes the set of all stars B ⊆ A. Given a power
assignment ri, a star is active if all its nodes (including
the center) are mutually disconnected in RG(A, ri), i.e., for
all pairs of nodes a1, a2 ∈ B, a1 and a2 are in different
connected components in RG(A, ri). Further, we need the
following two definitions. Let fa(a ′ ) denote the smallest k
such that a ′
∈ R a k, and let ga(ℓ) be the smallest k such
that t a k = |R a k| ≥ ℓ. That is, fa(a ′ ) denotes the minimal
transmission range which enables a to reach a ′ , and ga(ℓ) is
the smallest transmission range such that a interferes with
at least ℓ other nodes. If for two nodes a, a ′ ∈ A, there does
not exist any k such that a ′
∈ R a k, then fa(a ′ ) = ∞ and
t a
fa(a ′) = ∞. For a star B, the induced power assignment ˆrB
denotes the minimal power assignment for which all nodes
a ′ ∈ B have an edge to B’s center a in RG(A, ˆrB). Formally,
for a star B with center a, the induced power assignment for
node a ′ is defined as
ˆrB(a ′ ⎧
⎨ fa
) =
⎩
′(a)
, a′ ∈ B \ {a}
maxa∗∈B\{a} fa(a ∗ ) , a ′ = a.
0 , a ′ /∈ B.
Given a power assignment ri, we define the cost of a star B
as cost(B) = ∑
a∈B
cost(a) where
{
a
tˆr , t
B(a)
a
ˆr > t
B(a) a
ri(a) cost(a) =
0 , t a
ˆr B(a) ≤ t a
r i(a).
Intuitively, the cost of a star measures the amount of additional
interference created by connecting the nodes of the
star by edges, given the current power assignment ri. Particularly,
cost(a ′ ) of a leaf node a ′ is 0, if ri(a ′ ) is already
large enough such that the center node ac is in R a′
r(a ′), i.e.,
if the transmission range of a ′ does not need to be increased
in order to reach ac. If, on the other hand, the transmission
range of a node a ′
needs to be increased in order to
connect a star, cost(a ′ ) is the full interference created by
t a′
ˆr B(a ′ )
(not merely the incremental cost that comes from
increasing ri(a ′ ) to ˆrB(a ′ )). Algorithm 1 chooses in every
round the active star with minimal cost efficiency, and (minimally)
increases the transmission ranges of the nodes such
that all leaf nodes are connected to the star’s center by an
edge.
Algorithm 1 Greedy Algorithm
1: i = 0;
2: forall a ∈ A do r0(a) := 0;
3: while RG(A, ri) is not valid do
4: Bi := {B ∈ B | B is active};
5: ˜ Bi := argmin B∈Bi (cost(B)/|B|);
6: forall a ∈ ˜ Bi do ri+1(a) := max{ˆr ˜ Bi
(a), ri(a)};
7: forall a /∈ ˜ Bi do ri+1(a) := ri(a);
8: i := i + 1;
9: end while
Theorem 3.1. Algorithm 1 runs in polynomial time and
produces a valid power assignment rALG.
Proof. Correctness follows directly from the stop criterion
of the while loop. As for runtime, observe that one
greedy-step can be implemented in polynomial time in spite
of there being an exponential number of stars B ∈ Bi. For
a given center-node a ∈ A, we compute cost(a ′ ) for every
a ′ ∈ A as the cost of connecting a ′ to a. Let a ′ 1, a ′ 2, . . . a ′ k be
an ordering of a ′ ∈ A \ {a} such that cost(a ′ 1) ≤ cost(a ′ 2) ≤
. . . ≤ cost(a ′ k). The set of leaf nodes of the most cost efficient
star B (i.e., the star minimizing cost(B)/|B|) centered
at a is of the form {a ′ 1, a ′ 2, . . . a ′ i}, for some 1 ≤ i ≤ k. For a
given center-node, it is therefore possible to choose its minimal
cost star in polynomial time. Consequently, we can find
the global minimum cost star ˜ Bi by repeating the process
for all a ∈ A. Finally, note that the number of iterations is
at most |A|.
Before moving on to proving the algorithm’s approximation
ratio, we would like to add a remark on some practical
issues related to the above algorithm. In physical reality,
a node’s interference range exceeds its transmission range.Therefore, a node may experience interference from a transmitting
node even though it is located outside this node’s
transmission range. Our algorithm can easily be extended
to handle this case. All that needs to be done is to adjust
the definition of ga(ℓ). Specifically, it denotes the smallest
transmission range such that at least ℓ other nodes are located
within a’s interference range. The remainder of the
algorithm as well as its analysis remains the same.
3.2 Analysis
The analysis makes use of an integer linear program (ILP)
formulation of the interference problem. Let T denote the
set of all power assignments r, and let Tinv ⊆ T be the set
of all invalid assignments. A pair (a, ka) denotes a specific
power level at node a. We define the border of a given power
assignment r as δ(r) = {(a, k) | a ∈ A, k ∈ R a , k > r(a)}.
That is, the border of r contains all power assignment pairs
(a, k) that would denote an increase of the transmission
range at a as compared to assignment r. Using these definitions,
the interference problem can be captured as the
following covering integer linear program.
min
∑
s.t.
a∈A,k∈R a
∑
a∈A,k∈R a
(a,k)∈δ(r)
xa,kt a k
xa,k ≥ 1 , ∀r ∈ Tinv (1)
xa,k ∈ {0, 1} , ∀a ∈ A, k ∈ R a .
For each power level (a, k), the variable xa,k is set to 1 if
a’s transmission range is set to k, and to 0 otherwise. By
Lemma 2.1, minimizing the objective function will result in
a minimal total interference. The optimal average interference
is then obtained by dividing the optimal value by |P |.
The inequality constraint (1) guarantees that for every invalid
power assignment r ∈ Tinv, at least one node in its
border must increase its power level. It can be shown that
condition (1) is both sufficient and necessary to identify a
valid power assignment r that yields a connected resulting
graph RG(A, r). In the relaxed version of the above program’s
dual, there is a variable αr for each invalid power
assignment r ∈ Tinv.
max
∑
s.t.
r∈T inv
∑
r:(a,k)∈δ(r)
αr
αr ≤ t a k , ∀a ∈ A, k ∈ R a
αr ≥ 0 , ∀r ∈ Tinv.
The following key lemma relates the cost of the star picked
in each iteration of the greedy procedure to χ(rOP T ), the
cost incurred by the optimal valid power assignment.
Lemma 3.2. Let rOP T
be the optimal valid power assignment
and let χ(rOP T ) the interference incurred by rOP T .
Further, let λi denote the number of connected components
in RG(A, ri). For every iteration i of Algorithm 1, it holds
that
cost( ˜ Bi) · λi−1
| ˜ Bi|
≤ χ(rOP T ).
Proof. We use the dual linear program to prove the
claim. Specifically, we show that in every iteration i, we
can distribute the cost of cost( ˜ Bi)/| ˜ Bi| to dual variables αr
corresponding to each of the λi−1 connected components in
RG(A, ri−1). Specifically, we can do so in a way that the
assignment constitutes a feasible dual solution. By the laws
of LP duality, the objective value of a dual feasible solution
is a lower bound on χ(rOP T ), a fact which will allow us to
derive the claimed approximation ratio.
Let C be one of the λi−1 connected components that exist
in RG(A, ri−1). For each C, we define a series r c 1, . . . , r c m
of m = ⌈cost( ˜ Bi)/| ˜ Bi|⌉ different invalid power assignments
r c j ∈ Tinv as
r c ⎧
⎨ ga(j) − 1
j(a) := mina
⎩
′ ∈C fa(a ′ ) − 1
∞
, a ∈ C
, a ∈ Γj(C)
, else
where Γj(C) denotes the set of nodes a ∈ A \ C for which
there exists an a ′ ∈ C such that j > t a′
The dual
fa ′ (a).
variable αrc j
assigned to power assignment rc j is defined as
αr c j
:=
{
1 , j < m
− (m − 1) , j = m.
cost( ˜ B i)
| ˜ B i|
Note that with this definition of αrc, the sum of dual vari-
j
ables at each connected component C is exactly
m∑
j=1
αr c j
= cost( ˜ Bi)
| ˜ . (2)
Bi|
The total amount of dual variables assigned to invalid power
assignments r c j ∈ Tinv in iteration i is therefore given by
λi−1 · cost( ˜ Bi)/| ˜ Bi|.
We claim that the dual solution thus assigned in every
iteration of Algorithm 1 is feasible. Assume for contradiction
that there exists a power level (a, k) with a ∈ A
and k ∈ R a
∑
for which the dual condition is violated, i.e.,
r:(a,k)∈δ(r) αr > tak. Assume further that a is in connected
component C. We distinguish two cases, depending
on whether t a k is larger or smaller than cost( ˜ Bi)/| ˜ Bi|.
In the first case, t a k < cost( ˜ Bi)/| ˜ Bi|. We first show that
the sum of the dual variables assigned to power assignments
r c j (i.e., assignments corresponding to component C) is at
most t a k. By the definition of r c j and its border δ(r c j), it
holds that (a, k) ∈ δ(r c j) if and only if ga(j)−1 < k. Because
ga(j) is the smallest k ′ such that j ≤ t a
k ′, there are exactly tak
power assignments r c j for which (a, k) ∈ δ(r c j). Because for
each of these t a k assignments r c j, the dual variable αr c j
≤ 1,
it follows that the sum of dual variables assigned to power
assignments r c j is at most t a k.
To conclude the argument in the first case, we now show
that power assignment (a, k) is not in the border of any r c′
j ,
for any C ′
̸= C. Assume for contradiction that there is
a connected component C ′ and some j for which (a, k) ∈
δ(r c′
j ). By definition of Γj(C), this is the case only if there
exists a node a ′ ∈ C ′ for which j > t a′
fa ′ (a) and thus m −1 ≥
t a′
fa ′ (a) holds. In words, there must be a node a ′ /∈ C for
which the number of nodes it interferes with at transmission
level fa ′(a) is less than j. Now, consider the star B∗consisting of nodes a and a ′ . The cost of this star can be
upper bounded by
cost(B ∗ ) ≤ t a k + t a′
fa ′ (a) < cost( ˜ Bi)
| ˜ + ta′ fa ′ (a)
Bi|
≤
cost( ˜ Bi)
| ˜ Bi| + m − 1 ≤ 2cost( ˜ Bi)
| ˜ .
Bi|
The cost efficiency of star B ∗ is less than that of ˜ Bi and
therefore, Algorithm 1 would have picked star B ∗ instead
of ˜ Bi, yielding the contradiction which proves that (a, k) /∈
δ(r c′
j ) for all C ′ ̸= C.
For the second case, assume that t a k ≥ cost( ˜ Bi)/| ˜ Bi|. Unlike
in the first case, (a, k) may also be in the border of power
assignments r c′
j for some connected components C ′
̸= C.
Let C be the set of all components C ′ for which there exists
a power assignments r c′
j such that (a, k) ∈ δ(r c′
j ). Further,
for a component C ′ , let â denote the node a ′ ∈ C ′ that
minimizes t a′
fa ′ (a), i.e., â ∈ C ′ is the node that can reach a
with minimal interference. By the definition of r c′
j , (a, k) is
only in r c′
j
if j > t â
f â(a). Consequently, for j = 1, . . . , t â
f â(a),
(a, k) /∈ r c′
j . Because the total amount of dual variable assigned
to power assignments associated with component C ′
is exactly cost( ˜ Bi)/| ˜ Bi| by (2), the sum of the dual variables
for which a ∈ δ(r c′
j ) is
α
r c ′
j
∑
rc′ j :(a,k)∈δ(rc′
j )
αrc ′
j
= cost( ˜ B)
| ˜ B|
Summing up over all C ′ ∈ C yields
∑
r:(a,k)∈δ(r)
αr = |C| · cost( ˜ B)
| ˜ B|
− tâ f â(a).
− ∑
C ′ ∈C
t â
f â(a).
By assumption, the left hand side is strictly larger than t a k
which means that
∑
C ′ ∈C tâ f â(a) + t a k
|C|
< cost( ˜ B)
| ˜ . (3)
B|
Consider the star B ∗ consisting of a and all nodes â for C ′ ∈
C. The cost efficiency of cost(B ∗ )/|B ∗ | is upper bounded by
the left hand side of the Inequality (3). This contradicts
Algorithm 1 choosing star ˜ B in iteration i. This concludes
the proof of Lemma 3.2.
Given Lemma 3.2, it is now straightforward to derive the
main theorem using a proof technique used for instance in
[11] and subsequently in [10].
Theorem 3.3. Let rALG and rOP T be the power assignments
obtained by Algorithm 1 and by an optimal algorithm,
respectively. Further, χ(rALG) and χ(rOP T ) denote their
respective average interferences. It holds that χ(rALG) ≤
O(log n) · χ(rOP T ).
Proof. By the definition of Algorithm 1, it follows that
the number of connected components λi is at most
λi = λi−1 − | ˜ Bi| + 1
≤
Lemma 3.2
λi−1 − cost( ˜ Bi) · λi−1
+ 1
χ(rOP T )
(
1 − cost( ˜ )
Bi)
.
2χ(rOP T )
≤ λi−1 ·
Assume that Algorithm 1 requires w iterations.
λ0 = |A| and λw−1 ≥ 2, it follows that
2 ≤ λw−1 ≤ |A|
w−1
∏
ℓ=1
(
1 − cost( ˜ )
Bℓ)
2χ(rOP T )
Because
By taking the logarithm on both sides, this simplifies to
w−1
∑
(
ln 2 ≤ ln |A| + 1 − cost( ˜ )
Bℓ)
2χ(rOP T )
≤
ℓ=1
w−1
∑ cost(
ln |A| −
˜ Bℓ)
2χ(rOP T ) .
ℓ=1
By rearranging the above expression, we therefore obtain
the following upper bound,
w−1
∑
cost( ˜ Bℓ) ≤ 2χ(rOP T )(ln |A| − ln 2).
ℓ=1
Finally, observe that the total interference created by Algorithm
1, χ(rALG) is at most ∑w−1
ℓ=1 cost( ˜ Bℓ), because whenever
the transmission range of a node a ∈ A is increased,
cost( ˜ Bℓ) accounts for (at least) the entire cost of this increase.
The cost of the last iteration, ˜ Bw, is at most χ(rOP T )
and the theorem thus follows.
In Section 5, we will show how a similar algorithmic approach
can also help in solving the interference problem for
various other network properties Φ.
4. LOWER BOUND
In this section, we establish a tight Ω(log n) approximation
lower bound for the average interference problem even
in its most restricted model, the ad hoc metric model. Corresponding
lower bounds for the more general interference
models follow as a straightforward corollary. This implies
that from an approximation point of view, all models introduced
in Section 2 are asymptotically equally hard.
Theorem 4.1. Consider the ad hoc metric interference
problem with property Φ being the connectivity of nodes S,
n = |S|. There is no approximation algorithm having an
approximation ratio better than Ω(log n), unless it holds that
NP ∈ DT IME(n log log n ).
Proof. The proof makes use of a reduction to the set
cover problem that preserves the approximation. Consider
a set cover instance Is consisting of a collection S of subsets
of a finite set E of elements. Let n and m denote the number
of elements and sets, respectively. A solution to Is is a subset
S ′ ⊆ S such that every element e ∈ E is at least in one set
S ∈ S ′ . Let OP Ts be an optimal solution to Is, i.e., one
that covers all elements with as few sets as possible.0
3ε
01
01
2ε
2
2+1.5ε
01
01 01
01
01
01
01
1 01
01
11110000 11110000
00000000
11111111
01
00000000
11111111
00000000
11111111
01
00000000
11111111
00000000
11111111
00000000
11111111
1
00000000
11111111
00000000
11111111
00000000
11111111
00000000
11111111
00000000
11111111
00000000
11111111
00000000
11111111
00000000
11111111
00000000
11111111
00000000
11111111
00000000
11111111
2ε
00000000
11111111
00000000
11111111
00000000
11111111
00000000
11111111
00000000
11111111
00000000
11111111
00000000
11111111
00000000
11111111
00000000
11111111
00000000
11111111 4ε
00000000
11111111
00000000
11111111
00000000
11111111
01
01
01
01
01
01
ε
2ε
4
01
01
01
01
01
01
01
01
01
01
01
01
01
0000 11110000 01
11110000 01
01
01
01
01
01
01
01
v
Figure 3: The lower bound instance Iint for the set
cover instance S1 = {b}, S2 = {a, c}, S3 = {b, c}, S4 =
{a, d}, S5 = {d}, and S6 = {c, d} over the universe E =
{a, b, c, d}.
Given Is, we define an instance Iint of the interference
problem consisting of n + m + k1 + k2 + 2 nodes, where k1 is
to be defined later and k2 = k1 + m + n + 1. The node-set
A (which is equivalent to P ) of Iint is partitioned into six
clusters, two of which contain only a single node (see Figure
3 for an example). Clusters C1 and C2 consist of k1 and k2
nodes, respectively. For every set S ∈ S of Is, we add one
node to cluster CS, and for every element e ∈ E, there is a
node in cluster CE. For a node a1 ∈ CS, let S(a1) denote
the set S ∈ S that a1 represents. Similarly, e(a2) is the
element e ∈ E corresponding to node a2 in Iint. Finally, we
denote the two remaining nodes by v1 and v2.
Considering the ad hoc metric version of the interference
problem, we need to define the distance-function d that,
along with the set of nodes S, defines the metric space. The
distance between two nodes a1, a2 ∈ A is defined as
⎧
2ɛ , a1 = v1, a2 ∈ C1
4ɛ , a1, a2 ∈ C1
3ɛ , a1 ∈ C1, a2 ∈ CS
⎪⎨
2ɛ , a1, a2 ∈ CS
2 , a1 ∈ CS, a2 ∈ CE,
d(a1, a2) =
e(a2) ∈ S(a2)
4 , a1, a2 ∈ CE
2 +
⎪⎩
3ɛ
, a1 ∈ CE, a2 ∈ C2
2
2ɛ , a1, a2 ∈ C2
ɛ , a1 = v2, a2 ∈ C2
v 2
for an arbitrarily small ɛ. All other distances follow from
symmetry or are induced by the shortest path metric. Specifically,
notice that the distance between two nodes a1 ∈ CE
and a2 ∈ CS for which e(a1) /∈ S(a2) is 2 + 2ɛ. Finally, let
OP Tint be the optimal solution to the instance Iint of the
interference problem, and let χ(OP Tint) denote the average
interference incurred by OP Tint.
It has been shown in [15, 6] that set cover cannot be approximated
better than ln n, unless NP ∈ DT IME(n log log n ).
01
01
C1
S
E
C2
Hence, we merely need to show that the following two implications
hold
|OP Ts| ≤ α =⇒ χ(OP Tint) ≤ β
|OP Ts| > ln n · α =⇒ χ(OP Tint) > O(log n) · β
in order to prove the Ω(log n) lower bound. Moreover, inspecting
the proof of Feige’s hardness result on set cover,
it can be observed that the bound holds even for instances
having |S| ≤ |E|, e.g. [5, 6]. This allows us to use inequality
ln(m + n) ≤ ln n + c, for a small constant c.
We begin by showing that any solution Qint to the interference
problem in Iint can be transformed into a solution to
the underlying set-cover instance Is. Consider such a solution
Qint. Every element-node ai ∈ CE must be connected
to the rest of the graph. In the following lemma, we claim
that we can transform ALGint into a solution ALG ′ int in
which the ranges of all but one element-node is set to distance
2 without increasing interference. That is, each such
element-node reaches all set-elements to which it belongs,
but no other nodes.
Lemma 4.2. Given a solution Qint, we can obtain in polynomial
time a transformed solution Q ′ int in which all but one
ai ∈ CE is assigned transmission range r(ai) < 2+3ɛ/2, and
χ(Q ′ int) ≤ χ(Qint).
Proof. Consider a solution Qint in which more than one
node ai ∈ CE has transmission range at least 2+3ɛ/2. Every
such node covers all nodes aj ∈ C2, causing an interference
of k2 at these nodes. We transform Qint into a solution Q ′ int
as follows: For all but one ae ∈ CE with r(ae) > 2 + 3ɛ/2,
choose an as ∈ CS such that e(ae) ∈ S(as) and set r(as) := 2
and r(ae) = 2. By doing so, the interference caused by each
ae is reduced by k2. On the other hand, setting r(as) := 2
increases the interference by at most 1+k1+n+|S(as)| ≤ k2
by the definition of k2. Clearly, Q ′ int remains connected and
hence χ(Q ′ int) ≤ χ(Qint).
In the following, we given an upper bound on the optimal
interference χ(OP Tint) by relating it to the optimal solution
OP Ts of the original set cover instance.
Lemma 4.3. Given a set cover instance Is having an optimal
solution OP Ts of size αOP T . The optimal average
interference χ(OP Tint) in the corresponding interference instance
Iint is bounded by
χ(OP Tint) ≤ 5n + 5m + 2nm + m 2 + 2 + k1(7 + αOP T ).
Proof. For the proof, we construct a power assignment
r that yields a valid resulting graph RG(A, r). The interference
of r is an upper bound on χ(OP Tint). The following
power assignment r yields a valid resulting graph for Iint:
r(v1) = 2ɛ, r(v2) = ɛ,
r(â1) = 3ɛ, ∀a1 ∈ C1 \ {â1} : r(a1) = 2ɛ,
r(â2) = 2 + 3ɛ/2,
∀a2 ∈ C2 \ {â2} : r(a2) = ɛ,
r(âE) = 2 + 3ɛ/2,
∀aE ∈ CE \ {âe} : r(ae) = 2,
{
2ɛ , S(aS) /∈ OP Ts
∀aS ∈ CS :
2 , S(aS) ∈ OP Ts
where â1, â2, and âE are a single node from each C1, C2,
and CE, respectively. To see that the resulting graph isconnected, observe that there is an edge between all nodes
in C1, C2 and v1, v2, respectively. Furthermore, set-nodes
are linked as a linked list. The longer transmission range
of â1 enables this node to set up a link to any aS ∈ CS
which occurs in the optimal solution OP Ts, thus connecting
clusters C1 and CS. Because all nodes aS with S(aS) ∈
OP Ts set their transmission range to 2, RG(A, r) contains
an edge between each such set and the element it covers,
i.e., for every as having S(aS) ∈ OP Ts and every ae with
e(ae) ∈ S(aS), (as, ae) ∈ ERG. Particularly, this means that
all elements are connected. Finally, the connector nodes â2,
and âE ensure that cluster C2 is connected to one elementnode,
and consequently to the rest of RG(A, r).
Let ξC denote the total interference caused by nodes in
set C. Because OP Tint is the power assignment resulting
in the least possible interference, the interference of assignment
r provides an upper bound on OP Tint. Thus, counting
the interferences exhibited with assignment r, we can upper
bound OP Tint as
OP Tint ≤ ξv1
+ ξv2
+ ξC1
+ ξC2
+ ξCS + ξCE ≤ k1 + k2 + (2k1 − 1 + m) +
+ (2k2 − 1 + n) + ξC S
+ ξC E
≤ 3k1 + 3k2 − 2 + n + m +
+ ξC S
+ k2 + nm
≤ 3k1 + 4k2 − 2 + n + m + nm +
+ m 2 + k1αOP T + nαOP T
< 5n + 5m + 2nm + m 2 + 2 +
+ k1(7 + αOP T ).
The third inequality follows from ξ{â E } ≤ m + k2 as well
as from ξC E \{â E} ≤ (n − 1)m, because every element can
clearly be in at most m sets. Since every set-nodes (regardless
of whether it is in OP Ts) covers all other set-nodes, and
because all nodes aS with S(aS) ∈ OP Ts additionally interfere
with all nodes in C1 ∪ {v1} and possibly as many as n
elements, the fourth inequality holds. Because OP Tint is the
power assignment resulting in the least possible interference,
the claim follows.
Having obtained a bound for the first part of the reduction,
we will now consider the implication |OP Ts| >
ln n · α ⇒ χ(OP Tint) > O(log n) · β.
Lemma 4.4. Given a set cover instance Is having an optimal
solution OP Ts of size at least ln n · αOP T . The optimal
average interference χ(OP Tint) in the corresponding
interference instance Iint is lower bounded by χ(OP Tint) ≥
k1 ln n · αOP T .
Proof. Consider the optimal solution OP Tint to instance
Iint. Applying the transformation of Lemma 4.2 to OP Tint,
we obtain an optimal solution OP T ′ int in which all but one
ae ∈ CE are assigned range r(ae) < 2 + 3ɛ/2. Observe that
an element-node ae can only be connected to set-nodes as
for which e(ae) ∈ S(as), and only if r(as) ≥ 2. On the other
hand, every set-node with r(as) ≥ 2 interferes with all k1
nodes in C1.
Because by assumption at least ln n · αOP T
such sets are needed to cover all elements, χ(OP T ′ int) is at
least k1 ln n · αOP T .
Having established both upper (Lemma 4.4) and lower
(Lemma 4.3) bounds, we can now conclude the proof of Theorem
4.1. Specifically, when defining k1 := 5m+5n+2nm+
m 2 + 2, the inapproximability factor δ boils down to the expression
δ
≥
≥
k1 ln n · αOP T
5m + 5n + 2mn + m 2 + 2 + k1(7 + αOP T )
ln n · αOP T
8 + αOP T
≥
ln n
. (4)
8
To conclude the proof, it remains to establish a relationship
between n and |A|,
|A| = n + m + k1 + k2 + 2
= 12m + 12n + 4nm + 2m 2 + 7
< 16(m + n) 2 + 7
and hence, ln |A| < 2 ln(n+m)+c < 2 ln(n)+c ′ , for constants
c and c ′ . Plugging this into Inequality (4) concludes the
proof of Theorem 4.1.
Having proved the lower bound for the metric ad hoc
model, i.e., most restricted interference model, the following
corollary is straightforward.
Corollary 4.5. There is no algorithm that approximates
the general interference problem better than Ω(log n), unless
NP ∈ DT IME(n log log n ).
5. GENERALIZATION
The approach presented in Section 3 is not limited to
solving the interference problem with regard to the basic
connectivity problem. The algorithm can be generalized to
handle various other network-design problems. In particular,
we consider problems that can be formulated as special
cut-covering problems. A function f : 2 A → {0, 1} is called
a 0-1 proper function if it satisfies the following properties
[8]:
• f(A) = 0
• f(C) = f(A \ C) for all C ⊆ A
• if C and C ′ are disjoint, then
f(C) = f(C ′ ) = 0 ⇒ f(C ∪ C ′ ) = 0
As explained in [8], the class of network design problems
which can be formulated by 0-1 proper functions is particularly
rich, encompassing problems such as the shortest
path problem, connectivity, point-to-point connection problems,
generalized Steiner tree problems (which includes the
practically important case of multicast connectivity), T-join
problems, and many others. As mentioned in the introduction,
the work of [4] presents an O(log n) approximation
algorithm to a variety of generalizations of the basic interference
problem. However, the class of problems modelled
using point-to-point requirements [4] is a proper subset of
the problems that can be formulated by 0-1 proper functions
(i.e., the opposite is not true). Hence, our result is a true
generalization of the approximation result obtained in [4].
In order to solve the interference problems for properties
Φ that can be modelled as 0-1 proper functions, we adjust
Algorithm 1 as follows. Consider the set of connected components
C in an iteration i. A component C ∈ C is called
active if f(C) = 1. At each iteration, the adjusted algorithm
considers only active components and tries to connect them
in the most cost-efficient way. Particularly, let a star B be
a set of active components centered at a node a.Consider a path p = (a0, a1, . . . , aℓ) from a = a0 to an
active component C with aℓ ∈ C. The cost of p is defined
as cost(p) = ∑ℓ
j=1
cost(aj), where for j = 1, . . . , ℓ, cost(aj)
is given by
{ {
max t
cost(aj) =
aj
fa (a
j j−1) , ta }
j
fa (a
, θ(aj) = 1
j j+1)
0 , θ(aj) = 0.
where the indicator variable θ(aj) is defined as
⎧ {
⎨ 1 , max t
θ(aj) =
⎩
aj
fa (a
j j−1) , ta }
j
fa (a
j j+1)
}
0 , max
{
t a j
fa j
(a j−1) , ta j
fa j
(a j+1)
> t a j
r i(a j )
≤ t a j
r i(a j ) .
Note that this definition is a generalization of the definition
of cost(a) in Section 3, where each node a ′
∈ B is
simply a path of length 1. The cost of an active connected
component cost(C, a) with regard to a node a is the cost of
the lightest path pC from a to a node a ′ ∈ C (This path
can be computed in polynomial time using an adaptation of
a shortest path algorithm). If a ∈ C, then cost(C, a) = 0.
Finally, the cost of B centered at a is
cost(B) = 1
⎛
⎝
|B|
∑
cost(C, a) + max t a
⎞
⎠
fa(a1) .
C∈B
∀C∈B:
a1∈p C
The last term denotes the cost of node a in order to connect
to all first nodes a1 of the different paths.
With these adjusted definitions, the greedy step again consists
of choosing the star B ∈ B with minimum cost efficiency
cost(B)/|B| in each iteration. That is, all active components
in the picked star are connected by raising the transmission
powers of all nodes in the elected paths to the minimum
required values. Let a terminal be a node a ∈ A for which
f({a}) = 1. We can prove that the adjusted generalized
algorithm exhibits the following properties.
Theorem 5.1. Consider a network property Φ that can be
formulated as a 0-1 proper function. The adjusted version
of Algorithm 1 runs in polynomial time and produces a valid
power assignment for property Φ. Further, the algorithm
computes an O(log k) approximation, where k is the number
of terminals.
Proof. By the 0-1 proper function properties, it follows
that there cannot be one single active connected component
during the course of the algorithm’s execution. The number
of active components being reduced by at least one in every
iteration, the algorithm terminates leaving only inactive
components. The proof of the approximation ratio follows
exactly along the lines of the proof of Theorem 3.3.
6. CONCLUSION
We believe that interference in wireless networks (and
particularly so in ad hoc and sensor networks) will be a
major issue in the future that ought to be of interest to
both practitioners and theoreticians alike. There are many
paths for future research. The study of more complex network
properties that need to be maintained is clearly one
of them. Of most notable practical relevance appear to
be fault-tolerant structures such as k-edge/node connected
subgraphs (as pointed out in [4]) and, in hindsight of routing
applications, subgraphs having bounded (hop or energy)
stretch. It will also be interesting to see how well the interference
problem can be approximated in metric spaces with
restricted geometry, such as doubling metrics. The lower
bound metric in Section 4 is not restricted, leaving open the
possibility of sublogarithmic or even constant approximation
algorithms in these cases.
7. ACKNOWLEDGEMENTS
We would like to thank Pascal von Rickenbach and Aaron
Zollinger for many fruitful discussions.
8. REFERENCES
[1] P. Bose, P. Morin, I. Stojmenovic, and J. Urrutia.
Routing with Guaranteed Delivery in Ad Hoc Wireless
Networks. In Proceedings of the 3 rd International
Workshop on Discrete Algorithms and Methods for
Mobile Computing and Communications (DIALM),
pages 48–55, 1999.
[2] M. Burkhart, P. von Rickenbach, R. Wattenhofer, and
A. Zollinger. Does Topology Control Reduce
Interference. In Proc. of the 5 th ACM Int. Symposium
on Mobile Ad Hoc Networking and Computing
(MobiHoc), 2004.
[3] G. Calinescu, S. Kapoor, A. Olshevsky, and
A. Zelikovsky. Network Lifetime and Power
Assignment in Ad Hoc Wireless Networks. In
Proceedings of 11 th European Symposium on
Algorithms (ESA), pages 114–126, 2003.
[4] I. Caragiannis, C. Kaklamanis, and P. Kanellopolous.
Energy-Efficient Wireless Network Design. To appear
in Theory of Computing Systems, 2005.
[5] M. Chlebík and J. Chlebíková. Approximation
Hardness of Dominating Set Problems. In Proceedings
of 12 th European Symposium on Algorithms (ESA),
pages 192–203, 2004.
[6] U. Feige. A Threshold of ln n for Approximating Set
Cover. Journal of the ACM, 45(4):634–652, 1998.
[7] M. Fussen, R. Wattenhofer, and A. Zollinger.
Interference Arises at the Receiver. In Proceedings of
Int. Conference on Wireless Networks,
Communications, and Mobile Computing
(WIRELESSCOM), 2005.
[8] M. X. Goemans and D. P. Williamson. A General
Approximation Technique for Constrained Forest
Problems. SIAM Journal of Computing,
24(2):296–317, 1995.
[9] L. Jia, R. Rajaraman, and C. Scheideler. On Local
Algorithms for Topology Control and Routing in Ad
Hoc Networks. In Proc. 15 th Symposium on Parallel
Algorithms and Architectures (SPAA), pages 220–229,
2003.
[10] P. Klein and R. Ravi. A Nearly Best-Possible
Approximation Algorithm for Node-Weighted Steiner
Trees. Journal of Algorithms, 19(1):104–115, 1995.
[11] F. T. Leighton and S. Rao. An Approximate
Max-Flow Min-Cut Theorem for Uniform
Multicommodity Flow Problems with Applications to
Approximation Algorithms. In Proceedings of the 29 th
IEEE Symposium on the Foundations of Computer
Science (FOCS), pages 422–431, 1988.
[12] L. Li, J. Y. Halpern, P. Bahl, Y.-M. Wang, and
R. Wattenhofer. Analysis of a Cone-Based Distributed
Topology Control Algorithm for Wireless Multi-HopNetworks. In Proc. 20 th Symp. on Principles of
Distributed Computing (PODC), pages 264–273, 2001.
[13] N. Li, J. Hou, and L. Sha. Design and Analysis of an
MST-based Topology Control Algorithm. In
Proceedings of INFOCOM, pages 1702–1712, 2003.
[14] X.-Y. Li, G. Calinescu, and P.-J. Wan. Distributed
Construction of Planar Spanner and Routing for Ad
Hoc Networks. In Proceedings of INFOCOM, 2002.
[15] C. Lund and M. Yannakakis. On the Hardness of
Approximating Minimization Problems. Journal of the
ACM, 41(5).
[16] K. Moaveni-Nejad and X. Y. Li. Low-Interference
Topology Control for Wireless Ad Hoc Networks. In
Proceedings of the 2 nd IEEE Conference on Sensor
and Ad Hoc Communications and Networks
(SECON), 2005.
[17] R. Ramanathan and R. Hain. Topology Control of
Multihop Wireless Networks using Transmit Power
Adjustment. In Proceedings of INFOCOM, pages
404–413, 2000.
[18] P. von Rickenbach, S. Schmid, R. Wattenhofer, and
A. Zollinger. A Robust Interference Model for
Wireless Ad Hoc Networks. In Proc. 5 th IEEE
International Workshop on Algorithms for Wireless,
Mobile, Ad-Hoc and Sensor Networks (WMAN), 2005.