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

ISBN-10 0-470-09453-2

**Download**(direct link)

**:**

**70**> 71 72 73 74 75 76 .. 122 >> Next

FN(u) is the neighbor set of node u in the final topology

p(u) is the final (broadcast) transmit power of node u

1. Initialization

N(u) = 0 DN(u) = 0 FN(u) = 0

2a. ID broadcast

send message (u, Pmax) at maximum transmit power Pmax

2b. Neighbors detection

upon receiving message (v, Pmax) from node v N(u) = N(u) U {v}

determine the received signal strength and store this information

3. Exchange ordered neighbors list

after all the messages from neighbors have been received order nodes in N(u) according to the received signal strength

3a. send message (u, N(u)) at maximum transmit power Pmax

3b. upon receiving ordered neighbors list (v, N(v)) from node v, store this information

4. Determine final neighbor set

after the ordered neighbor lists from all the nodes in N(u) have been received for each v e N(u), in decreasing order of link quality if (3w e DN(u) U FN(u) such that w -<v u) then DN(u) = DN(u) U {v} otherwise FN(u) = FN(u) U {v}

5. Transmit power computation

p(u) = minimum power level needed to reach the farthest node in FN(u)

Figure 12.6 The XTC protocol.

NEIGHBOR-BASED TOPOLOGY CONTROL

141

with a RSSI register) and orders its neighbor set accordingly. So, exchanging n messages overall (every node sends one message at maximum power) is sufficient to compute the neighbors order.

Once the neighbor set has been computed and ordered, every node broadcasts the ordered neighbor list at maximum power (this also requires sending n messages overall).

The final step of XTC, that is, the computation of the final topology, can be done locally at each node, with no further message exchange. To compute the network topology, node u considers its neighbors in decreasing order of link quality: when considering a certain neighbor v, it checks whether there exists a node w with w <u v (i.e. with better link quality) such that w <v u. Note that this check can be done locally at node u, which knows v’s neighbor order (because v is a neighbor of u). If the above condition is satisfied, edge (u, v) is discarded; otherwise it is included in the set FN(u), which contains the neighbors of u in the constructed network topology. After all the nodes in N(u) have been processed, set FN(u) is the u’s local view of the network topology produced by XTC, which we call Gxtc.

12.3.2 Protocol analysis

In (Wattenhofer and Zollinger 2004), Wattenhofer and Zollinger investigate the properties of the GXTC graph in two different settings. First, they consider the more general setting in which -< is an arbitrary link quality-based order; then, they consider a quite idealized setting in which the link quality-based order coincides with the distance-based order (as discussed above, this might happen if, for instance, the environment is flat and unobstructed), and proves additional properties of the GXTC graph.

Let us start with the more general setting in which the measure used to determine link quality is arbitrary. The first property considered by Wattenhofer and Zollinger is symmetry: in particular, they show that the neighbor relation induced by GXTC is symmetric:

Theorem 12.3.1 (Wattenhofer and Zollinger 2004) Let G = (N, E) be the maxpower communication graph, and let GXtc = (N, EXTC) be the topology computed by the XTC protocol, that is, edge (u, v) e EXTC if and only if v e FN(u) at the end ofXTC’s execution. The GXTC graph is symmetric, that is, edge (u, v) e GXTC if and only if (v, u) e GXTC. Equivalently, at the end ofXTC’s execution v e FN(u) if and only if u e FN(v).

Proof. Assume for the sake of contradiction that v e FN(u), but u e DN(v). Since u e DN(v), there exists node w e N(v), with w <v u, such that w <u v. Let us now consider the time at which node u processes neighbor v; since w <u v, this implies that w has already been processed by u, that is, w e DN(u) U FN(u) when u processes v. In turn, this implies that when the condition on node v is checked, v must be inserted in DN(u); in fact, node w is such that w e DN(u) U FN(u), and w <v u. This contradicts the initial assumption that v e FN(u), and the theorem is proven.

Note that, contrary to the case of CBTC in which the symmetry of the final topology is enforced by adding the reverse edge in the unidirectional links (or by removing all the unidirectional links), in XTC it is the neighbor relation itself that is symmetric, so adding or removing unidirectional links is not needed.

The following theorem proves that XTC preserves connectivity in the worst case.

142

NEIGHBOR-BASED TOPOLOGY CONTROL

Theorem 12.3.2 (Wattenhofer and Zollinger 2004) Let G = (N, E) be the maxpower communication graph, and let GXTC = (N, EXTC) be the topology computed by the XTC protocol. GXTC is connected if and only if G is connected.

Proof. Proving the ‘only if’ part is immediate since GXTC is a subgraph of G.

To prove the reverse implication, assume for the sake of contradiction that G is connected, but GXTC is not connected. This implies that there exists at least one node pair that is connected in G but is not connected in GXTC. Among all such pairs, consider the pair u, v of minimum cost, where the cost of pair u, v is given by the cost (in terms of link quality) of the minimum path between u and v in G. To break possible ties, we consider the lexicographical order of the node IDs. Since u, v is the ‘disconnected’ pair in GXTC of minimum cost, it follows that u and v are one-hop neighbors in G. Otherwise, there exist nodes w, z in the minimum path connecting u and v in G such that nodes w and z are disconnected in GXTC, and the cost of w, z is strictly less than the cost of u, v - contradiction. Since (u, v) e G, it follows that v e N(u), and that v is included in DN(u) when it is processed by node u (in fact, edge (u, v) is not in GXTC). In turn, this implies that there exists node w, with w e N(u), such that w <v u, that is, node w is also a neighbor of node v. It is immediate to see that we must have w e FN(u) (and w e FN(v)), since otherwise u, v would not be the pair of minimum cost that is connected in G and disconnected in GXTC. This leads to a contradiction since (u,w) e EXTC and (w, v) e EXTC implies that u and v are connected in GXTC, contrary to our initial assumption.

**70**> 71 72 73 74 75 76 .. 122 >> Next