23-02-2013, 04:41 PM
Equilibria in Topology Control Games for Ad Hoc Networks
Equilibria in Topology.pdf (Size: 254.75 KB / Downloads: 29)
ABSTRACT
We study topology control problems in ad hoc networks,
where network nodes get to choose their power levels in order
to ensure desired connectivity properties. Unlike most
other work on this topic, we assume that the network nodes
are owned by different entities, whose only goal is to maximize
their own utility that they get out of the network
without considering the overall performance of the network.
Game theory is the appropriate tool to study such selfish
nodes: we define several topology control games in which
the nodes need to choose power levels in order to connect
to other nodes in the network to reach their communication
partners while at the same time minimizing their costs. We
study Nash equilibria and show that – among the games we
define – these can only be guaranteed to exist if all network
nodes are required to be connected to all other nodes (we call
this the Strong Connectivity Game). We give asymptotically
tight bounds for the worst case quality of a Nash
equilibrium in the Strong Connectivity Game and we
improve these bounds for randomly distributed nodes.
INTRODUCTION
Unlike traditional, fixed wireline networks, the next generation
communication networks are likely to be ad hoc, or
hybrid (i.e., a combination of ad hoc and wireline) networks.
An ad hoc network consists of an arbitrary distribution of
radios in some geographical location. One important feature
of ad hoc networks is that nodes can move, and so the
network changes dynamically. Earliest examples of ad hoc
networks were in military applications (e.g. [8]). Recent advances
in the commercialization of intelligent radio devices
are likely to lead to the wide-spread emergence of ad hoc or
hybrid networks [13].
Depending on its power level, on the nature of environmental
interference, and on natural features, a node in an ad
hoc network can reach all nodes in a certain range. To send
a message to some far away node, the sending node must
rely on intermediate nodes to forward the message. We consider
scenarios where no fixed infrastructure is present and
it is left to the nodes to choose their power levels to enable
efficient communication. Once the radii (power levels) of
the nodes are fixed, a digraph G(V,E) can be abstracted
out in the following manner: V is the set of nodes, and edge
e = (u, v) is present in E if node v is within the power range
of node u; such a graph is called the transmission graph
[14]. Efficient communication requires that the transmission
graph satisfy certain properties such as connectivity,
energy-efficiency and robustness. The area of topology control
deals with choosing the radii such that the transmission
graph has the desired properties; see [14] for a survey.
The Strong Connectivity Game
In this section, we show that any instance of the Strong
Connectivity Game has a pure Nash equilibrium. We
prove an upper bound on the cost of all Nash equilibria and
show with an example, that this upper bound is tight. We
further present an algorithm that finds a Nash equilibrium
for any given instance. We then show how our local improvement
algorithm combined with an algorithm given in
[10] yields a Nash equilibrium with no more than twice the
optimum cost. All results in this section also hold for non-
Euclidean instances where the triangle inequality is satisfied.
The Connectivity Game
In this section, we show that, unlike the Strong Connectivity
Game, the general Connectivity Game need
not have pure Nash equilibria, not even approximate ones.
We also prove that determining whether a game instance has
a pure Nash equilibrium is NP-complete by proposing a reduction
from Monotone 2-in-3-Three-Satisfiability.
Figure 2 shows a game instance without pure Nash equilibrium.
The instance consists of three sources s1, s2, s3 and
three sinks t1, t2, t3; The sources form an equilateral triangle
with edge length 1; vertices s1, t1, s2 form an isosceles
triangle with t1 being at distance 2 from both s1 and s2;
similarly vertices s2, t2, s3 and vertices s3, t3, s1 form isosceles
triangles.
THE REACHABILITY GAME
In this section, we show that the Reachability Game
need not have a pure Nash equilibrium, even for a 1-dimensional
instance. The simple example of Figure 3 is one
such instance. Multiple vertices are located at the same
point (e.g. points 1, 3, 4) in this figure. This is only for the
purpose of keeping the example simple; the colocated points
can be perturbed slightly to be located very close to each
other.
CONCLUSIONS AND OPENPROBLEMS
We consider two topology control games arising in ad hoc
networks in the presence of selfish, non-cooperative agents
in this paper and study the existence of Nash equilibria,
their quality and algorithms for computing them. Our work
motivates further game theoretic study of protocols for ad
hoc networks. Some of the interesting open questions are
the following.