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