# Topologi control in wireles ad hoc and sensor network - Santi P.

ISBN-10 0-470-09453-2

**Download**(direct link)

**:**

**48**> 49 50 51 52 53 54 .. 122 >> Next

Similar definitions can be given for distance and hop spanners.

Figure 8.1 The graph (a) is the maxpower graph G, where the edges are labeled with their length. The subgraph G' of the maxpower graph obtained by removing edge (u, v) is reported in (b). The power stretch factor of G' is 1 (we assume a = 4), since edge (u, v) is energy inefficient, and the alternative path {u, w, v} is used also in the maxpower graph. The distance stretch factor of G' is = 1-46. The hop stretch factor is 2, because the

pG, = max

pc(pmr,G')

G

G'

(a)

(b)

minimum-hop path connecting nodes u and v in G' is the two-hops path {u, w, v}.

ENERGY-EFFICIENT COMMUNICATION TOPOLOGIES

89

In general, we would like to identify a subgraph G' (also called routing graph in the following) of the maxpower graph G that has a low power stretch factor (possibly, a power spanner of G), and which is significantly sparser than the original graph. This routing graph can be seen as the input to the routing protocol, which computes the routes between nodes considering only the links in G'. Given the power spanning property, we have the guarantee that the power needed to communicate along these routes is ‘almost minimal’. The advantage of using G' instead of G is that the routing overhead (which is mainly due to the limited flooding of control messages in the route discovery phase1) is reduced if G' is considerably sparser than G.

Note that in this approach to the topology control problem it is implicitly assumed that a node changes the transmit power on a per-packet basis: when node u has to send a packet to node v, it sets the transmit power level to the minimum value needed to reach the next node in the route to v. Thus, according to the taxonomy introduced in Chapter 3, we can classify the results presented in this section as per-packet topology control.

Besides being a sparse2 power spanner, other desirable features of the routing graph have been identified. In particular, the node degree in the constructed topology should be upper bounded by a constant. Note that the fact that G' is sparse guarantees that the average, and not the maximum, node degree in the graph is constant. Having an upper bound on the maximum node degree is desirable to avoid bottlenecks in the communication graph. If the routing graph is used in conjunction with a geographic routing protocol (such as the protocols presented in (Bose et al. 2001; Karp and Kung 2000; Khun et al. 2003)), then planarity is a fundamental property to guarantee message delivery. Finally, and most importantly, the routing graph should be constructed in a localized and fully distributed fashion. In other words, any node u in the network should be able to compute its local view of G' (i.e. the edges of G' incident in it) on the basis of only the information regarding nodes that are immediate (or, at most, two-hops) neighbors of u in the maxpower graph.

Summarizing, the routing graph G' should

- be a power spanner of the maxpower graph;

- be sparse;

- have bounded node degree;

- be planar;

- be easily computable in a fully distributed and localized fashion.

Several routing graphs that satisfy some or all of the requirements above have been proposed in the literature. Most of them are based on subgraphs of G that are known to be good distance spanners. In fact, it can be easily seen that if a certain routing graph G' is a distance spanner of graph G, then it is also a power spanner of G (note that the reverse implication in general is not true). Thus, the considerable body of research devoted to distance spanners in computational geometry can be used to design good routing graphs (Goodman and O’Rourke 1997).

1This is true for reactive routing protocols, which are known to perform very well in ad hoc/sensor networks.

2We recall that, in graph theoretic terms, a graph on n nodes is sparse if the number of edges in it is O(n) (see Appendix A).

90

ENERGY-EFFICIENT COMMUNICATION TOPOLOGIES

Table 8.1 Distance stretch factor, power stretch factor, average and maximum node degree of different proximity graphs

Distance Power Avg. Degree Max. Degree

RNG GG n — 1 4jrV2n —4 3 n — 1 1 O(1) O(1) n — 1 n — 1

RDT 1+2^ 0VM" O(1) &(n)

YGc 1 1 O(1) n — 1

l-2sinf 1 —(2smf)“

In particular, the following graphs (for a definition of these graphs see Appendix A) borrowed from computational geometry have been used to build good routing graphs for ad hoc networks: the Relative Neighborhood Graph (RNG), the Gabriel Graph (GG), the Delaunay Triangulation (DT), and the Yao Graph of parameter c (YGc). These graphs are called proximity graphs, since the set of links incident in any node u of the computed graph can be calculated on the basis of the position of the neighbor nodes in the maxpower graph. Thus, proximity graphs can be constructed in a fully distributed and localized way.

The following relationships between proximity graphs have been proven (Goodman and O’Rourke 1997; Li et al. 2002): for any set of points N, RNG(N) c GG(N), and RNG(N) c YGc(N), for any c > 6. Furthermore, MST(N) is contained in RNG(N), GG(N), DT(N), and YGc(N), for any c > 6. The distance and power spanning ratios of these graphs are summarized in Table 8.1, along with the average and maximum node degree. In the table, RDT is the restricted Delaunay Triangulation, where the edges exceeding the nodes’ maximum transmitting range are removed (see (Gao et al. 2001)).

**48**> 49 50 51 52 53 54 .. 122 >> Next