<<

. 32
( 87 .)



>>

context of satellite networks. In [27], the term was reused, but meant physical topology
control. Both techniques can be used for controlling the set of links seen by routing. The
techniques are orthogonal and, thus, one can employ both physical and routing topology
control to control the topology at two levels. In this chapter, we study only physical topol-
ogy control. Unless explicitly mentioned, the term “topology control” will mean physical
topology control.
In the next subsection, we shall discuss topology control based on power adjustment.
The basic problem here is how to pick the right range for each node to balance connectiv-
ity, energy, and spatial reuse. Following that, we shall discuss topology control based on
antenna beam pointing. The issue here is less about which nodes to pick4 as how to form
neighbors when one or both have to beamform toward the other.

4
This is because, in this case, acquiring distant nodes as neighbors does not impact the spatial reuse nearly as
much since transmissions are directional.
158 ANTENNA BEAMFORMING AND POWER CONTROL FOR AD HOC NETWORKS


5.4.1 Power-Based Topology Control
The generalized problem of power-based5 topology control (recall that we are considering
only physical topology control in this chapter) is as follows [29, 27]: Given an ad hoc net-
work, determine and adaptively adjust the transmit power of each node in the network so
as to meet a given minimization objective and adhere to a given connectivity constraint.
The above is a generalized definition and subsumes a number of specific problems de-
pending upon what is considered for the minimization objective and the connectivity con-
straint. Possibilities include:

Minimization objectives. Maximum power, average power, maximum degree, aver-
age degree, maximum diameter, and so on.
Connectivity constraints. Connectivity, biconnectivity, and so on.

An example of a specific topology control problem is one of dynamically adjusting
transmit powers such that the maximum power used is minimized while keeping the net-
work biconnected. This was first studied in [27]. Clearly, a number of other combinations
are possible.
There is a further dimension to the problem relating to the dynamism of topology con-
trol. That is, just as many other distributed control problems, one can consider the static
version of the problem or consider the dynamic version. In the static version, global topo-
logical information is available, the computation is “one-time” only, and it can use a cen-
tralized solution. In the dynamic version, only local information is available, the computa-
tion is continuous, and it typically requires a distributed algorithm. Although the dynamic
version is more useful for mobile ad hoc networks, a study of the static version provides
valuable insight, is useful to define the upper bound on performance, has some applicabil-
ity to stationary ad hoc networks such as commercial mesh-based broadband wireless so-
lutions, and is simple to understand.
In this subsection, we first examine the static version of the problem and examine
some algorithmic issues. We then consider the dynamic version and survey some decen-
tralized and distributed approaches.

5.4.1.1 Static Topology Control. We first introduce some terminology that will
make the subsequent discussion less ambiguous.
First, an ad hoc network is represented as M = (N, L), where N is a set of nodes and L :
N (Z0+, Z0+) is a set of coordinates on the plane denoting the locations of the nodes.
The least-power function (d) gives the minimum power needed to communicate over
a distance of d. The function (d) is dependent upon the propagation loss and the receiver
sensitivity, and essentially maps from range to power (see [27] for details).
Using these, a graph-theoretic representation is used as follows. Given a multihop
wireless network M = (N, L), a transmit power function p, and a least-power function ,
the induced graph is represented as G = (V, E), where V is a set of vertices corresponding
to nodes in N, and E is a set of undirected6 edges such that (u, v) E if and only if p(u)
[d(u, v)], and p(v) [d(u, v)].

5
In the remainder of this section, we shall omit “power based”; the term will be implied.
6
An alternate and arguably superior representation would use directed edges to include unidirectional communi-
cation links. Note that we do not assume bidirectionality; we simply ignore unidirectional links. Using unidirec-
tional links in an efficient manner requires sophisticated control protocols at several layers and is a subject of
current research.
159
5.4 NEIGHBOR DISCOVERY: TOPOLOGY CONTROL


We use standard graph-theoretic terminology from [30]. In particular, a graph is said to
be k-vertex/edge connected if and only if there are k vertex/edge-disjoint paths between
every pair of vertices. Note that if a graph is k-vertex connected, then it is also k-edge con-
nected, but the converse is not true. For this reason, and because vertex connectivity is im-
portant for resilience to node failures and hotspots, we shall consider only vertex connec-
tivity. We shall omit the word “vertex” for brevity. Thus, if k is 1, the graph is connected,
and if k is 2, it is biconnected. The degree of a vertex is the number of edges incident on
that vertex. We only consider undirected graphs, that is, all edge relations on vertex pairs
are symmetric.
Let us now consider a specific topology control problem, namely the one considered in
[27]. In this problem, the constraint is 1-connectivity, and the objective is minimization of
maximum power. This is stated formally below.

Definition 5.4.1 Problem: Connected MinMax Power (C-MMP). Given an M = (N, L),
and a least-power function , find a per-node minimal assignment of transmit powers p :
Z+, such that the induced graph of (M, , p) is connected, and MAXu N[p(u)] is a
N
minimum.

An algorithm, called CONNECT, for this problem is given below. It is a simple
“greedy” algorithm, similar to the minimum cost-spanning-tree algorithm. It works by it-
eratively merging connected components until there is just one. Initially, each node is its
own component. Node pairs are selected in nondecreasing order of their mutual distance.
If the nodes are in different components, then the transmit power of each is increased to be
able to just reach the other. This is done until the network is connected. The description
assumes for simplicity that network connectivity can be achieved without exceeding the
maximum possible transmission powers. However, the algorithm can be easily modified
to return a failure indication if this is not true.

Algorithm CONNECT
Input: (1) Multihop wireless network M = (N, L) (2) Least-power function
Output: Power levels p for each node that induces a connected graph
begin
1. sort node pairs in non-decreasing order of mutual distance
2. initialize |N| clusters, one per node
3. for each (u, v) in sorted order do
4. if cluster(u) cluster(v)
5. p(u) = p(v) = (distance(u, v))
6. merge cluster(u) with cluster(v)
7. if number of clusters is 1
then end
8. perNodeMinimalize(M, , p, 1)
end

Although this produces a minimum maximum power, it leaves some scope for reduc-
ing the powers of some nodes without affecting the connectivity. Line 8 in algorithm
CONNECT is a procedure that exploits the presence of “side-effect edges” to minimize
the power of each node, resulting in a reduced average power. The details of this proce-
dure can be found in [27].
(a)




(b)

Figure 5.8. (a) Uncontrolled network topology. (b) Connected topology using the C-MMP solu-
tion.
161
5.4 NEIGHBOR DISCOVERY: TOPOLOGY CONTROL




(c)
Figure 5.8. (c) Biconnected topology using B-MMP solution.




This algorithm is provably optimal [27]. Algorithms for related problems”for exam-
ple, the Biconnected Minimum Maximum Power (B-MMP), the Connected Minimum Av-
erage Power (C-MAP), and the Connected Minimum Maximum Degree (C-MMD)”are
of a similar flavor. Algorithms for these problems are given in [29]. However, unlike the
C-MMP, not all of them are amenable to optimal solutions. The algorithm for B-MMP is
provably optimal [27], but C-MAP has been proven to be NP-complete in a variety of set-
tings [31, 32], making it highly unlikely that there is a polynomial-time optimal solution.
The topology resulting from a solution for the C-MMP and the B-MMP problem on a
network of 40 nodes spread out with a density of 2 nodes/sq mile is shown in Figure 5.8.
The uncontrolled network (a) is too dense, whereas the connected network (b) has some
congestion hot spots. The biconnected network (c) visually appears to provide the right
balance, and, indeed, simulations in [27] show that it provides the best performance
among the three.
The algorithmic aspects of topology control are studied thoroughly in [33]. There a
general approach leading to an optimum polynomial“time algorithm is presented for min-
imizing maximum power for a class of graph properties called monotone properties. A
property P is monotone if the property continues to hold even when the powers assigned
to some nodes are increased while the powers assigned to other nodes remain unchanged.
For example, k connectivity is monotone. Thus, the paper generalizes the results of [27] to
162 ANTENNA BEAMFORMING AND POWER CONTROL FOR AD HOC NETWORKS


hold for any k-connectivity constraint. They also give an approximation algorithm for the
C-MAP problem that has a constant times“optimum performance guarantee.

Dynamic Topology Control. For dynamic networks, there are two approaches to doing
topology control:

1. Fully Distributed. Nodes only know local information. All nodes execute the same
(distributed) algorithm to produce the result.
2. Decentralized. All nodes have the global topology information through a flooded
exchange, and run the same algorithm to produce the same result, after which each
node uses the part of the result that pertains to itself. This is similar to the way the
traditional link-state routing protocol works.

A “zero overhead” distributed algorithm called Local Information No Topology
(LINT) is described in [27]. In LINT, a node is configured with three parameters”the
“desired” node degree dd, a high threshold on the node degree dh, and a low threshold dl.
Periodically, the node checks the number of active neighbors (degree) in its neighbor table
(built by the routing mechanism). If the degree is greater than dh, the node reduces its op-
erational power. If the degree is less than dl, the node increases its operational power. If
neither is true, no action is taken. The magnitude of the power change is a function of de-
sired degree dd and current degree d. In particular, the further apart d and dd are, the
greater is the magnitude of the change.
Although being extremely simple to implement, this algorithm does not guarantee con-
nectivity. Other more sophisticated distributed algorithms that guarantee connectivity
have been described, including those in [34, 35].
In [34], the concepts of a relay region and enclosure are used to select neighbors. A re-
lay region for a node pair (i, r) is the region such that, for any node j in that region, it is
more efficient for an i j transmission to be relayed through r than to be sent directly. An
enclosure for a node i is computed based on the relay regions of (i, n) for each neighbor n
of i. Intuitively, the enclosure is a region beyond which it is not power-efficient to have
neighbors. One of the key results is that if every node maintains communication links
with the nodes in its enclosure, the network is strongly connected. The authors provide a
distributed algorithm based on this that yields strong connectivity.
In [35], a cone-based distributed algorithm is described. A node continues to grow its
power until its neighbor set is big enough such that, for any cone with angle there is at
least one neighbor, or until the node hits the maximum allowable power. They provide
simulation results that outperform the algorithm in [34] in the scenarios studied.
The decentralized approach is inherently more overhead intensive, and less responsive
to changes. On the other hand, it allows for direct execution of the static algorithms. A de-
centralized topology-control algorithm is described in [29]. The execution of that algo-
rithm can be perceived as “punctuated equilibrium,” with events happening at globally
synchronized periodic intervals (only rough synchronization is required, as might be pro-
vided by a GPS clock). At these topology reformation moments (TRM), local state7 is
flooded, all nodes collect the individual local states to form the current snapshot of the
global topology, execute a heuristic (e.g., algorithm CONNECT), and use the result for it-
self as the new power. Until the next TRM, this new set of powers is used.

7
Two versions of “state” are described, one based on position, and another based on signal strength.
163
5.4 NEIGHBOR DISCOVERY: TOPOLOGY CONTROL


In [29], the decentralized solution to B-MMP (called GIFT, for “Global Information
Full Topology”) is compared with the Local Information No Topology (LINT) algorithm,
and to the performance when no topology control is employed. We reproduce those results
in Figure 5.9. All results reported here are for 60 nodes.
We note from Figure 5.9 that the decentralized algorithm yields the best throughput.
The throughput at density 14 is about 11% better than that of LINT, and about 71% better
than no topology control. However, the delay is also slightly higher, about 27% more than
LINT. The increased delay is a result of being less densely connected (giving rise to larger
number of hops between node pairs).
Although it appears wasteful, the decentralized approach exploits the fact that after the
powers are set the first time, one can have considerable intervals between resets; that is,
the TRMs can be fairly widely spaced apart. For instance, in the results discussed in the
above paragraph, a 20 second interval was used. With this, the decentralized approach
handily outperforms the LINT distributed algorithm for mobile networks, yet only uses
about 0.5% of the capacity of a 2 Mbps transceiver. Thus, this is a simple yet scalable ap-
proach for at least nonhighly mobile ad hoc network applications.


5.4.2 Topology Control Using Beamforming Antennas
Transmitter beamforming provides additional gain in the direction that the packet is sent.
Likewise, receiver beamforming provides additional gain in the direction from which a
packet is received. These additional gains typically provide a significant increase in the
range at which neighbors can be acquired. Moreover, which nodes can be neighbors de-
pends upon whether none, one, or both of the nodes beamform. Orthogonally, other mech-
anisms for increasing the processing gain along the direction of communication also in-
fluence the ability to form neighbors.
Conventional neighbor discovery techniques such as those in [36, 37] assume the pres-
ence of omnidirectional antennas, and are not sufficient to enable discovery of neighbors
with beamforming. Thus, one problem is: How do we discover neighbors using beam-
forming? While the problem is one of neighbor discovery, it is directly related to topology
control because differing capabilities in discovering neighbors leads to differences in the
way topology control can be effected.
Once neighbors have been discovered, they have to be “maintained.” Such mainte-
nance typically uses periodic transmissions of beacons, nonreceipt of which indicates
that the link has gone down. Unlike broadcast beaconing in omnidirectional networks,
where a single beacon suffices for all directions, we now may need multiple beacons:
one for each direction or neighbor.8 Thus, we are led to the next problem: How do we
pick and choose the potential neighbors so as to get the desired topology? This may be
thought of as a dynamic degree-constrained network design problem. Very little work
has been done on this, and, therefore, we only discuss the discovery problem in the re-
mainder of this subsection.
A neighbor relationship may be specified as bsbr, where bs is the beamform of the
sender, and br is the beamform of the receiver. We consider two possibilities for bs and
br: omni (O) and directional (D). Thus, we have four kinds of neighbors”OO, DO, DD,
and OD. This terminology was first used in [9]. The OO neighbors can be discovered us-

8
Note that we cannot use omnidirectional beacons because their range may be considerably less and cannot
reach the neighbors that have been acquired using beamforming.
164 ANTENNA BEAMFORMING AND POWER CONTROL FOR AD HOC NETWORKS


<<

. 32
( 87 .)



>>