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

ISBN-10 0-470-09453-2

**Download**(direct link)

**:**

**42**> 43 44 45 46 47 48 .. 122 >> Next

'An algorithm for finding the CTR in O(n log n) time in one-dimensional networks is the following. First, order all the nodes according to their spatial coordinate. The CTR for connectivity is the largest among the distances between consecutive nodes in the order.

76

THE RANGE ASSIGNMENT PROBLEM

Algorithm OptimalIdRA:

1. Initialization

1.1 Let RAi be the range assignment such that RAi(u1) = &(u\, ui),

and RAi(uj) = 0 otherwise

1.2 for i = 2, ... ,n do Opt(([ui}, 0), ut) = RAi

2. Step k:

2.1 Assume we know Opt(([u\,..., uk}, Ei,k), ui), for any 1 < i < k and k < l < n

2.2 for any j, m such that 1 < j < k + 1 < m < n

2.3 consider all possible values of RA(uk+1) (there are k + 2 such values)

2.4 for each such value r, find an assignment RA in Opt(({ui,uk}, Ej'k+{), uk+1, (uk+i, r))

2.5 if RA has cost lower than that of the current range assignment for j, m,

store RA (new current minimum)

2.6 at the end of step k, we know a range assignment in Opt(({ui,..., uk+i}, Ei,k+i), ui), for any 1 < i < k + 1 < l < n

3. after step n, an optimal assignment is one in Opt(([u\,..., un}, 0), un)

Figure 7.2 Algorithm for finding the optimal range assignment in one-dimensional networks.

7.3 The RA Problem in Two- and Three-dimensional Networks

In the previous section, we have analyzed the RA problem for one-dimensional networks, outlining the considerable increase in computational complexity with respect to the case of solving the simpler CTR problem. The increase in computational complexity becomes even larger in case of two- and three-dimensional networks, as stated by the following theorem.

Theorem 7.3.1 Solving the RA problem in two- and three-dimensional networks is NP-hard.

The NP-hardness of finding the optimal solution to RA in three-dimensional networks has been proved in (Kirousis et al. 2000). Later on, Clementi et al. proved that the problem remains NP-hard in case of two-dimensional networks also (Clementi et al. 1999).

Although solving RA in two- and three-dimensional networks is hard, an approximation of the optimal solution can be easily computed by constructing an MST on the nodes. The construction of the range assignment is as follows:

Let N = [u\,..., un} be a set of points (nodes) in the two- or three-dimensional space.

1. Construct an undirected weighted complete graph G = (N, E), where the weight of edge (ui, uj) e E is S(ui, uj)a.

2. Find a minimum weight spanning tree T of G.

3. Define range assignment RAT, with RAT(ui) = maxj\(ui,uj)ˆT S(ui, uj).

THE RANGE ASSIGNMENT PROBLEM

77

RAj (mj) = 2

RAT (m2) = 8

RAj (M3) = 5 RAj (M4) = 4 RAj (M5) = 8 RAj (Mg) = 3 RAt (M7) = 5 RAt (Mg) = 5

RAj (mc) = 2

RAt (mjo)= 2

Figure 7.3 Minimum spanning tree T on the set of nodes, and corresponding range assignment RAT.

An example of minimum spanning tree T, and the corresponding range assignment RAT, are depicted in Figure 7.3.

The algorithm for constructing RAT has O(n2) running time (the time complexity of building the MST on the n nodes), and produces a 2-approximation of the optimal solution.

Theorem 7.3.2 (Kirousis et al. 2000) Let N be a set of points (nodes) in the two- or threedimensional space, and let RAT be the range assignment defined as above. Let RA be an optimal range assignment for the RA problem. Then

Proof. The proof is composed of two steps. First, we prove that c(RA) is greater than the cost c(T) of the minimum spanning tree T. Then, we prove that c(RAT) < 2c(T).

1. c(RA) > c(T) ___

Starting from any optimal assignment RA for N, we can build a spanning tree for the complete undirected graph G by choosing any node u e N, and constructing a shortest path destination tree rooted at u, with all edges directed toward the root, representing minimum weight paths from any node to the root node. Given the shortest path destination tree, the corresponding spanning tree T' is obtained by changing the directed edges in the shortest path tree to the corresponding undirected edges in G. Since each of the n — 1 nodes other than the root must be assigned a range that is at least sufficient to establish the edges in the shortest path destination tree, we have c(RA) > c(T'). The strict inequality follows from the fact that RA assigns a strictly positive range to the root node u (this is necessary for strong connectivity), which is not accounted for in c(T'). In turn, c(T') is at least as large as the cost c(T) of the minimum spanning tree.

c(RAT) < 2c(RA).

78

THE RANGE ASSIGNMENT PROBLEM

2. c(RAT) < 2c(T)

The inequality follows by observing that, during the construction of RAT, each edge of T can be chosen as the ‘longest’ edge (i.e. as the transmitting range) at most by two nodes (the endpoints of the edge).

7.4 The Symmetric Versions of the Problem

In the RA problem we are interested in establishing a strongly connected communication graph. Since nodes in general have different transmitting ranges, unidirectional links might occur, and they can even be essential for ensuring strong connectivity.

**42**> 43 44 45 46 47 48 .. 122 >> Next