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

ISBN-10 0-470-09453-2

**Download**(direct link)

**:**

**56**> 57 58 59 60 61 62 .. 122 >> Next

Cu,v = Cost(v) + S(u, v)a + cr.

Then, node u computes the minimum energy cost of sending a message to the master node as

Cost(u) = min Cu,v,

veN(u)

and broadcasts the message Cost(u) at maximum power. The calculation of Cost(u) is repeated each time a new cost message is received, and a new cost message is broadcast by u each time Cost(u) is updated. After a finite number of iterations, the algorithm stabilizes (see (Lynch 1996)). The neighbor of u that is the next hop in the minimum-energy path to the master node is the parent of u in the energy-optimal reverse spanning tree Topt. After all the nodes in the network have computed their cost and thus determined their minimum cost neighbor link, the construction of the optimal topology Topt is complete. Note that Topt is built in a top-down fashion: the first links that stabilize are those connecting the master node with its immediate neighbors; then, stabilization propagates downward in the reverse tree.

10.1.4 Discussion

The R&M protocol presented in this section has the nice feature of building a topology that optimizes a certain energy-efficient topology problem, namely, MinEnergyAllToOne. However, the computation of the optimal topology requires global information exchange (Phase 2 of the protocol), causing a certain message overhead.

Given its features (building an energy-efficient topology for communicating with a master node, but with rather high message overhead), the R&M protocol can be successfully used in many WSN application scenarios, where mostly stationary network nodes must send their data to a gateway node. In this case, the network topology is typically built at the beginning of the network lifetime, and constructing an energy-efficient topology (even if this comes at the expense of a relatively high message overhead) is a primary design concern.

It is interesting to note that the reverse version of MinEnergyAllToOne, that is, the energy-efficient broadcast problem, is NP-hard. The reason for this gap in computational complexity is due to the fact that, in the energy-efficient broadcast problem, the nodes use the so-called wireless advantage, that is, the fact that the message sent by a node can be received by all the nodes within its range, and computing the best way of using the ‘wireless advantage’ is NP-hard. On the other hand, in the MinEnergyAllToOne problem, the goal is to find the most efficient way of communicating with the master node, that is, the ‘wireless advantage’ is not useful in this case. Then, to solve the problem, it is sufficient to find the most energy-efficient path from any node to the master node, which can be done in polynomial time.

A final observation concerns one of the potential disadvantages of the R&M protocol, that is, the fact that it relies on an explicit radio signal propagation model that is used to compute the enclosure graph and Topt. A consequence of this fact is that the topology generated by R&M might be different from the optimal one if the actual channel conditions are different from those predicted by the channel model used to compute Topt.

110

LOCATION-BASED TOPOLOGY CONTROL

10.2 The LMST Protocol

In Chapters 7 and 8, we have seen that the MST enjoys several nice features: it preserves connectivity, it is extremely sparse, and it is a ^-approximation (for some constant h > 0) of the optimal solution to the RA, to the WSRA, and to the energy-efficient broadcast problem. The drawback of this topology is that its computation requires the exchange of global information. To circumvent this problem, Li et al. introduced the LMST (Local MST) protocol (Li et al. 2003), which computes a local approximation of the MST.

10.2.1 Protocol description

The LMST protocol is composed of three phases: information exchange, topology construction, and determination of transmit power, and an optional optimization phase: construction of topology with bidirectional links.

In the protocol specification, it is assumed that all the nodes have the same maximum transmit power and that the wireless medium is symmetric.1 We also adopt the conventional definition of maxpower graph, that is, the graph G = (N, E) obtained when all the nodes transmit at maximum power.

Definition 10.2.1 (Visible neighbors) The visible neighbors of node u e N are all the one-hop neighbors of u in the maxpower graph G = (N, E). Formally,

VNu = {v e N\(u, v) e E}U {u}.

Information exchange. In the first phase of the protocol, each node sends its ID and location to all nodes in the visible neighborhood. This can be accomplished by sending a beacon message at maximum transmit power.

Topology construction. Once all the beacon messages of the visible neighbors have been received, each node constructs its local MST by applying the classical Prim’s algorithm (Prim 1957). The link weight used to build the MST is its length (Euclidean distance). This choice is compatible with any path loss model, as the power cost of link (u, v) is proportional to S(u, v)a, with a > 1. So, the MST that results using any path loss model as the weight function is the same one that is built using the Euclidean distance.

**56**> 57 58 59 60 61 62 .. 122 >> Next