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

ISBN-10 0-470-09453-2

**Download**(direct link)

**:**

**50**> 51 52 53 54 55 56 .. 122 >> Next

Definition 8.2.1 (Broadcast stretch factor) Let G' be an arbitrary subgraph of the maxpower graph G = (N, E). The broadcast stretch factor of G' with respect to G, denoted as P&, is the maximum over all nodes of the ratio between the minimum-power broadcast tree in G' and in G. Formally,

pc(Tm™G')

P& = max . .

H ðñ(ÒÃ'°)

Definition 8.2.2 (Broadcast spanner) Let G = (N, E) be the maxpower graph, with |N| = n. A subgraph G' of G is said to be a broadcast spanner of G if pG' º O(\).

Similar to the case of unicast, the goal is to find sparse broadcast spanners of G that can be computed in a fully distributed and localized fashion. Unfortunately, this task turns out to be more difficult than in the case of unicast communication.

The main difficulty arises from the fact that the computing of the minimum-power broadcast tree rooted at a certain node is a NP-hard problem (Cagali et al. 2002; Liang 2002),

ENERGY-EFFICIENT COMMUNICATION TOPOLOGIES

93

under the hypothesis that the nodes can use a set of discrete power levels {Pi,, Pk}. So, directly computing the broadcast stretch factor of a certain subgraph G' of G is virtually impossible, since this would require solving a NP-hard problem.

Given this hardness result, several authors have presented heuristic solutions that approximate the optimal (but hard to compute) solution of the minimum-power broadcast tree problem. One popular such heuristic, which we present in the following, is the Broadcast Incremental Power (BIP) algorithm introduced in (Wieselthier et al. 2000).

The BIP algorithm, which is reported in Figure 8.4, is a variation of the well-known Prim’s algorithm for finding the MST. The algorithm starts by finding the node that the source node u can reach with minimum power cost. This node is added in the set C of covered nodes, that is, the nodes that have received the broadcast message. At the generic step i, BIP considers all the uncovered nodes and, for any such node v, calculates the incremental cost of adding v to the current spanning tree. The node v with minimum incremental cost is added to the set of covered nodes, and is now part of the spanning tree. This process is repeated until all the nodes in the network are covered.

In (Wan et al. 2002), Wan et al. showed that the approximation ratio of BIP is between y and 12. Then, a broadcast spanner of G can be constructed as follows: for any node u in G, apply the BIP algorithm to construct the broadcast tree Tu rooted at u. Let GBip = (JuˆN Tu, that is, link (u, v) is in Gbip if and only if it is contained in one of the broadcast trees computed by BIP. Given that BIP approximates the optimal solution (which is built on the maxpower graph) by a factor at most 12, it follows that, for any u e N, Gbip contains a

Algorithm BroadcastIncrementalPower:

u is the source node C is the set of currently covered nodes T is the current spanning tree N is the set of network nodes

1. Initialization

C = {u}

T = {u}

2. Repeat until C = N

for each node v e N — C, compute the incremental cost ic(v) of adding v to T let v be the node in A — C with minimal incremental cost

c = c UM

add v in the current spanning tree T

3. Termination

when C = N, T is a broadcast spanning tree rooted at u

Figure 8.4 BIP algorithm for constructing the broadcast tree.

94

ENERGY-EFFICIENT COMMUNICATION TOPOLOGIES

broadcast tree rooted at u of cost at most 0(1) times the cost of the optimal tree; that is, GBIP is a broadcast spanner of G. Unfortunately, graph GBIP in general is not sparse. Furthermore, BIP is a centralized algorithm that requires global knowledge (it requires knowing at least the set N of network nodes).

Another graph that can be used to construct broadcast spanners is the MST, which approximates the minimum-power broadcast tree by a factor between 6 and 12 (Wan et al. 2002). Unfortunately, the computation of the MST also requires global knowledge. In order to circumvent this problem, Li et al. (Li et al. 2004) have recently proposed a localized, fully distributed algorithm that constructs a local approximation of the MST. The algorithm, called LMST, requires exchanging 0(n) messages (although the hidden constant is larger than 225), and builds a 0(na-1) approximation of the energy-optimal broadcast tree. Thus, LMSTt cannot be used to compute a broadcast spanner of G.

Summarizing, the problem of designing a distributed and localized algorithm that can be used to build a broadcast spanner of G is still open.

Before ending this section, we want to outline the similarities between the range assignment problem discussed in Chapter 7 and the problem of energy-efficient broadcast. Suppose G is the maxpower graph on the set of points N. In the. RA problem, the goal is to find the energy-optimal range assignment that generates a connected communication graph. Suppose an arbitrary node u e N wants to broadcast a message m, and let RA be the optimal range assignment. A very simple broadcast scheme is flooding: node u transmits m at distance RA(u), and every other node v, upon receiving m for the first time, retransmits it at distance RA(v). It is immediately seen that after all nodes in N have transmitted the message once m has been broadcast throughout the network. Thus, the energy cost of RA is an upper bound to the power cost of any broadcast tree in G. We recall that the energy cost of the optimal range assignment (and of the optimal weakly symmetric range assignment) differs from the cost of the MST at most for a factor 2. Since the MST is a broadcast spanner of G, this implies that the communication graph generated by the optimal (weakly symmetric) range assignment is a broadcast spanner of G. Unfortunately, this does not help very much, since computing this graph in two and three-dimensional networks is NP-hard.

**50**> 51 52 53 54 55 56 .. 122 >> Next