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

ISBN-10 0-470-09453-2

**Download**(direct link)

**:**

**68**> 69 70 71 72 73 74 .. 122 >> Next

k is the target number of neighbors (input parameter)

Pmax is the maximum node transmit power

N(u) is the neighbor set of node u

KN(u) is the k-closest neighbor set of node u

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

1. Initialization

N(u) = 0 KN(u) = 0

2a. ID broadcast

send message (u, Pmax) at transmit power Pmax

2b. Neighbors detection

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

estimate distance to v and store this information

3. Wait for stabilization time

4. Compute the k-closest neighbors list

order the nodes in N(u) according to the estimated distance KN(u) = first k nodes in N(u) - (all the nodes if \N(u)\ < k)

5a. Neighbor list broadcast

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

5b. Neighbor lists reception

upon receiving message (v, KN(v)) from node v store this information

6. Wait for stabilization time

7. Symmetric neighbor list computation

for each v e KN(u) do

if u e KN(v) then KN(u) = KN(u) - {v}

8. Transmit power computation

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

Figure 12.4 The KNeigh protocol.

NEIGHBOR-BASED TOPOLOGY CONTROL

137

Algorithm KNeigh - Optimization Stage:

(algorithm for node u)

KN(u) is the symmetric k-closest neighbor set of node u for each v e KN(u), P(u, v) is the minimum transmit power needed to reach v P(u, v), for each v e KN(u), is included in the message sent at step 5a. of KNeigh p(u) is the final (broadcast) transmit power of node u

1. Initialization

Sort nodes in KN(u) for increasing value of P(u, v) let v1,..., vh, with h < k, be the resulting ordering

2. Energy-inefficient edge removal

for i = 1 to h do

check whether 3vj, with j < i, such that P(u, vj) + P(vj, vi) < P(u, vi) (note that P(vj, vi) has been received by u together with the list KN(vj) sent by node vj )

if yes, remove vi from KN(u), and set P(u, vi) to P(u, vj) + P(vj, vi)

3. Transmit power computation

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

Figure 12.5 The optimization stage of the KNeigh protocol.

Blough et al. also presented an optimization stage that can be applied at the end of KNeigh. The philosophy of this optimization is the same as in CBTC, that is, to remove energy-inefficient links from the final topology. The optimization stage, which is reported in Figure 12.5, can be executed locally at each node with no further message exchange. The idea is very simple: edge (u, vi) is removed from the final topology if and only if there exists a third node vj that is a symmetric neighbor of both u and vi, such that sending a message along the two-hop path {u, vj, vi} is more energy efficient than the direct communication from u to vi. Note that only edges that are part of a ‘triangle’ are removed, that is, this optimization does not reduce network connectivity. Furthermore, given that nodes u, vj and vi are symmetric neighbors, and all of them execute the same optimization protocol, node u removes node vi from KN(u) if and only if node vi removes node u from KN(vi), that is, the optimization stage preserves symmetry.

The authors of (Blough et al. 2003b) evaluated the average-case performance of KNeigh through simulation, comparing it with the case of no topology control (i.e. the network topology is the maxpower communication graph) and with CBTC. In case of KNeigh and CBTC, Blough et al. compared the protocols both with and without the final optimization phase implemented. The metrics considered to evaluate the performance of the protocols were (i) the average (broadcast) transmit power level of the nodes in the final topology, which is a measure of the energy efficiency of the protocols; and (ii) the average physical node

138

NEIGHBOR-BASED TOPOLOGY CONTROL

degree, which is a measure of the expected interference. The simulation results show that KNeigh after optimization is about 20% more energy efficient than CBTC after optimization. If optimizations are not implemented, the gap in favor of KNeigh is even larger. As for the average physical node degree, KNeigh without optimization performs much better than CBTC without optimization, while the two protocols have essentially the same performance if optimizations are implemented.

A final simulation-based investigation reported in (Blough et al. 2003b) concerns the effect of errors in distance estimation on KNeigh’s performance. The authors considered realistic error models for both RSSI- and ToA-based techniques, and evaluated the impact of errors on the connectivity of the final topology. The simulation results show that errors in distance estimation have a very limited impact on the network topology, especially in case the relatively accurate ToA-based distance estimation technique is used. In other words, by setting k as in Table 12.1, the topology generated by KNeigh is connected w.h.p. even if the distance estimation is relatively imprecise.

12.2.2 Discussion

The KNeigh protocol enjoys several nice features: it is very simple, it is based on relatively ‘low-quality’ information (distance between nodes), it is lightweight (only 2n messages are exchanged in the network), and it generates a topology with a nontrivial upper bound on the physical node degree, which, as we have seen, is fundamental to maintain a relatively low level of interference in the network. However, contrary to all the topology control protocols presented so far, KNeigh does not preserve network connectivity in the worst case. Unfortunately, as we have discussed in Section 9.3, there is no way of guaranteeing connectivity in the worst case and limited physical node degree at the same time. So, if the emphasis is on limiting the physical node degree as it is in KNeigh, guaranteeing connectivity w.h.p. is, in a sense, the best one can hope for.

**68**> 69 70 71 72 73 74 .. 122 >> Next