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

ISBN-10 0-470-09453-2

**Download**(direct link)

**:**

**53**> 54 55 56 57 58 59 .. 122 >> Next

P Deg(u) =|{v e N : S(u, v) < max S(u, w)}|.

(u,w)eEP

It is easy to see that the logical degree is a lower bound to the physical degree.

To clarify the difference between logical and physical node degrees, let us consider the example shown in Figure 9.1. The figure reports a sample topology built by the CBTC protocol introduced in (Wattenhofer et al. 2001), which will be presented in detail in Chapter 11. After CBTC ’ s execution, node u has nodes v, w, x, y, z in its neighbor list, that is, it has logical degree 5. However, when u transmits a message to its furthest neighbor, node w, more than 5 nodes are within its radio range. Consider for instance node t; this node does not have a direct link to u in the constructed topology, because communicating along the two-hops path {t,v,u} is more energy efficient than the direct communication from t to u. Nevertheless, t is affected by u s transmission to node w, and it contributes to its physical degree. Note that the physical degree can be substantially higher than the logical degree: in the example of Figure 9.1, the logical degree of node u is 5, while its physical degree is 10.

The following theorem proves a fundamental trade-off between worst-case connectivity and physical node degree:

Theorem 9.3.3 Let G = (N, E) be the maxpower communication graph on node set N, and assume G is connected. Let P be any topology control protocol that preserves worst-case connectivity and let GP = (N, EP) be the topology generated by P. Then, there exists a node placement such that the maximum physical node degree in GP is n — 1, where n = |N|.

Proof. Consider the node placement represented in Figure 9.2: there is one faraway node (node v) and all the other nodes are very close to each other. Among these nodes, node u is the closest to node v. Since the maxpower graph G is connected, node u is within

DISTRIBUTED TOPOLOGY CONTROL: DESIGN GUIDELINES 101

Figure 9.1 Difference between logical and physical node degrees: node u has logical degree equal to 5 and physical degree equal to 10.

v

Figure 9.2 Example of node placement generating a topology in which at least one node has physical node degree equal to n - 1.

v’s maximum transmitting range and, given the standard assumptions of symmetric wireless medium and that all the nodes have the same maximum transmit power, node v also is within u’s maximum range. Since the nodes in the cluster are much closer to u than node v, and v is a neighbor of u in G, it follows that the physical degree of node u in the maxpower graph is n - 1. Let us now consider the topology GP = (N, EP) generated by a worst-case connectivity preserving topology control protocol P. Can we do any better than having at

102

DISTRIBUTED TOPOLOGY CONTROL: DESIGN GUIDELINES

least one node with physical degree equal to n — 1? The answer is clearly no: since GP must be strongly connected, at least one of the nodes in the cluster must have v within its transmitting range. Node u is the cluster node that is closer to node v: if node u has a connection to node v, its physical degree is n — 1 for the reasons described above. If another cluster node w = u has a connection to v, w’s range is larger than S(u, v), since u is the closest node to v, and every network node is within w’s range. It follows that, in order to preserve connectivity, at least one of the network nodes must have physical degree equal to n — 1, and the theorem is proven.

In other words, Theorem 9.3.3 states that if we want to ensure connectivity in the worst case, we must admit the possibility of having a ‘high interference node’, that is, a node whose communications affect all the remaining nodes in the network.

Another implication of Theorem 9.3.3 is that the gap between logical and physical node degrees can be very high in the worst case. In fact, as we will see in the following chapters, there exist topology control protocols that preserve worst-case connectivity and generate topologies with logical node degree bounded by a small constant (typically, 6). By Theorem 9.3.3, the physical node degree in these topologies can be as high as n — 1, implying that the gap between logical and physical node degrees in a communication graph can be as high as O(n).

10

Location-based Topology Control

In this chapter, we present two location-based distributed topology control protocols, the R&M protocol introduced in (Rodoplu and Meng 1999) and the LMST protocol presented in (Li et al. 2003).

As discussed in the previous chapter, this type of protocols relies on very accurate information (node locations), which is assumed to be somehow available to the nodes. The easiest way to satisfy this assumption is to equip every node in the network with low-power GPS receivers, which enable very accurate position estimation and loose synchronization with no message exchange between network nodes. This solution has a high cost in terms of hardware required on the nodes, but it entails no message overhead. An alternative solution is to use one of the many location estimation techniques introduced in the literature (see, for instance, (Niculescu and Nath 2003; Priyantha et al. 2000; Savvides et al. 2001)). These techniques usually assume that a subset of the network nodes (called the anchor nodes) is equipped with GPS receivers, and that nonanchor nodes can estimate their position by exchanging messages with the surrounding anchor nodes. In location estimation techniques, the reduced hardware cost due to the fact that only a subset of the nodes is GPS-equipped is traded off with the message overhead incurred to estimate node positions.

**53**> 54 55 56 57 58 59 .. 122 >> Next