Computers & Operations Research

(

)

–

www.elsevier.com/locate/dsw

Exact algorithms for the minimum power symmetric connectivity problem in wireless networks R. Montemanni∗ , L.M. Gambardella Istituto Dalle Molle di Studi sull’Intelligenza Articiale (IDSIA), Galleria 2, CH-6928 Manno-Lugano, Switzerland

Abstract In this paper we consider the problem of assigning transmission powers to the nodes of a wireless network in such a way that all the nodes are connected by bidirectional links and the total power consumption is minimized. Two mixed integer programming formulations are presented together with some new valid inequalities for the polytopes associated. A preprocessing technique and two exact algorithms based on the formulations previously introduced are also proposed. Comprehensive computational results, which show the e+ectiveness of the new valid inequalities and of the preprocessing technique are presented. The experiments also show that the exact approaches we propose outperform more complex methods recently appeared in the literature. ? 2004 Elsevier Ltd. All rights reserved. Keywords: Telecommunications; Wireless networks; Integer programming

1. Introduction For a given set of nodes, the minimum power symmetric connectivity (MPSC) problem is to assign transmission powers to the nodes of the network in such a way that all the nodes are connected and the total power consumption over the network is minimized. It is assumed that no power expenditure is involved in reception/processing activities, and that there is no mobility.

The work was partially supported by the Future & Emerging Technologies unit of the European Commission through Project “BISON: Biology-Inspired techniques for Self Organization in dynamic Networks”(IST-2001-38923). ∗ Corresponding author. Tel.: +41-91-610-8671; fax: +41-91-610-8661. E-mail address: [email protected] (R. Montemanni). 0305-0548/$ - see front matter ? 2004 Elsevier Ltd. All rights reserved. doi:10.1016/j.cor.2004.04.017

ARTICLE IN PRESS 2

R. Montemanni, L.M. Gambardella / Computers & Operations Research

(

)

–

Fig. 1. Communication model.

Unlike in wired networks, where a transmission from i to m generally reaches only node m, in wireless networks with omnidirectional antennae—the case considered in this paper—it is possible to reach several nodes with a single transmission. In the example of Fig. 1 nodes j and k receive the signal originated from node i and directed to node m because j and k are closer to i than m, i.e. they are within the transmission range of a communication from i to m. This property is used to minimize the total transmission power required to connect all the nodes of the network. Saving energy is a very important issue in wireless networks since devices are usually equipped with batteries. Another good reason to keep transmission ranges small is that this limits the interference over the network. As in Althaus et al. [1], the model discussed in this paper assumes the complete knowledge of pair-wise distances between the nodes and that a communication link is established only if both nodes have transmission range at least as big as the distance between them. This last assumption is justiIed by technical reasons. MPSC has been proven to be NP-hard in Clementi et al. [2]. A branch and cut algorithm based on a new integer programming formulation is proposed in Althaus et al. [1]. Some mixed integer programming formulations for an optimization problem similar to MPSC, where a host has to broadcast a message to all the other nodes, and the bidirectionality constraint for the links is relaxed, are presented in Das et al. [3]. Di+erent heuristic approaches for the same problem are proposed in Wieselthier et al. [4], where some constructing algorithms are described, in Marks II et al. [5], where an evolutionary approach using genetic algorithms is presented together with methods for generating initial solutions, and in Das et al. [6], where an ant colony system approach is described. In this paper we present two new mixed integer programming formulations for the MPSC problem and some new valid inequalities for the polytopes associated. We also present a new preprocessing rule and two new exact algorithms. Comprehensive computational results show the e+ectiveness of the new valid inequalities and of the new preprocessing techniques. Other experiments show that the new algorithms we propose outperform exact methods recently presented in the literature. In Section 2 the problem is formally described, while in Section 3 two mixed integer programming formulations and a set of valid inequalities for the polytopes associated are described. Section 4 is devoted to the description of a new preprocessing procedure, while in Section 5 two exact algorithms, strongly based on integer programming, are proposed. Computational results are presented in Section 6, while Section 7 is devoted to conclusions.

ARTICLE IN PRESS R. Montemanni, L.M. Gambardella / Computers & Operations Research

(

)

–

3

2. Problem description In order to represent the problem in mathematical terms, a model for signal propagation has to be selected. We adopt the model presented in Rappaport [7]. Signal power falls as 1=d , where d is the distance from the transmitter to the receiver and is a environment-dependent coeKcient, typically between 2 and 4 (we will set = 4). Under this model, and adopting the usual convention (see, for example, Althaus et al. [1]) that every node has the same transmission eKciency and the same detection sensitivity threshold, the power requirement for supporting a link from node i to node j, separated by a distance dij , is then given by pij = (dij ) + ;

(1)

where is a constant representing the energy required to set up and maintain a communication (see Heinzelman et al. [8]). This constant depends on the hardware equipping the nodes, and is independent from the transmission distance (we will set = 0). Using the model described above, power requirements are symmetric, i.e. pij = pji . It is important to notice that the theoretical results presented in this paper remain valid also in case di+erent signal propagation models are adopted. MPSC can be formally described as follows: Given the set V of the nodes of the network, a range assignment is a function r : V → R+ . A bidirectional link between nodes i and j is said to be established under the range assignment r if r(i) ¿ pij and r(j) ¿ pij . Let now B(r) denote the set of all bidirectional links established under the range assignment r. MPSC is the problem of Inding a range assignment r minimizing i∈V r(i), subject to the constraint that the graph (V; B(r)) is connected. As suggested in Althaus et al. [1], a graph theoretical description of MPSC can be given as follows: Let G = (V; E; p) be a weighted, undirected complete graph, where V is the set of vertices corresponding to the set of nodes of the network and E is the set of edges containing all the possible pairs {i; j}, with i; j ∈ V , i = j. A cost pij is associated with each edge {i; j}. It corresponds to the power requirement deIned by Eq. (1). For a node i and a spanning tree T of G, let {i; iT } be the maximum cost edge incident to i in T , i.e. {i; iT } ∈ T and piiT ¿ pij ∀{i; j} ∈ T . The power cost of a spanning tree T is then c(T ) = i∈V piiT . Since a spanning tree is contained in any connected graph, MPSC can be described as the problem of Inding the spanning tree T with minimum power cost c(T ). This observation will be used in Section 3 for the mixed integer programming formulations presented there.

3. Mixed integer programming formulations A weighted, directed, complete graph G =(V; A; p) is derived from G by deIning A={(i; j)|i; j ∈ V }, i.e. for each edge in E there are the respective two arcs in A, and a dummy arc (i; i) with pii = 0 is inserted for each i ∈ V . pij is deIned by Eq. (1) when i = j. In the example of Fig. 2, where for sack of simplicity power is not proportional to distance, a directed graph is derived from an undirected one.

ARTICLE IN PRESS 4

R. Montemanni, L.M. Gambardella / Computers & Operations Research

(

)

–

Fig. 2. Example of directed graph G derived from undirected graph G.

In order to describe the new mathematical formulations, we need the following deInition: Denition 1. Given (i; j) ∈ A, we deIne the ancestor of (i; j) as i if pij = mink ∈V {pik }; aij = arg maxk ∈V {pik |pik ¡ pij } otherwise:

(2)

According to this deInition, (i; aij ) is the arc originated in node i with the highest cost such that piaij ¡ pij . 1 In case an ancestor does not exist for arc (i; j), vertex i is returned, i.e. the dummy arc (i; i) is addressed. In the example of Fig. 1, arc (i; k) is the ancestor of arc (i; m), (i; j) is the ancestor of (i; k) and the dummy arc (i; i) is returned as the ancestor of (i; j). The two formulations are based on an incremental mechanism over the variables representing transmission powers. The costs associated with these variable in the objective functions (4) and (11) will be given by the following formula: cij = pij − piaij ∀(i; j) ∈ A

(3)

cij is equal to the power required to establish a transmission from nodes i to node j (pij ) minus the power required by nodes i to reach node aij (piaij ). In Fig. 3 the costs arising from the example of Fig. 1 are depicted. As far as we are aware, this incremental mechanism has never been used before within mathematical models for the MPSC problem. 3.1. Formulation MPSC1 The mixed integer programming formulation described in this section is inspired by those presented in Das et al. [3]. It is based on a network Now model (see Magnanti and Wolsey [9]). 1 For sack of simplicity, we have considered the (usual) case where ∀i ∈ V @k; l ∈ V s:t: pik = pil . In case this is not true, the following formula, which breaks ties, has to be used in place of Eq. (2): i if pij = mink∈V {pik }; i (pik ¡ pij ∧ (@l ∈ V s:t: pik = pil ∧ l ¿ k)) aj = otherwise: arg maxk∈V pik | ∨(pij = pij ∧ (@l ∈ V s:t: pik = pil ∧ j ¿ l ¿ k))

ARTICLE IN PRESS R. Montemanni, L.M. Gambardella / Computers & Operations Research

(

)

–

5

Fig. 3. Costs for the mathematical formulations. cij is the power required to reach j from i, while cik is the additional power required to reach k when j is already reached from i. Analogously, cim is the additional power required to reach node m from i while k is already reached.

A node s is elected as the source of the Now, and one unit of Now is sent from s to every other node. In formulation MPSC1 variable the node s from which to broadcast is the root of the spanning tree, and one unit of Now is sent from s to every other node. Variable xij (with i = j) represents the Now on arc (i; j). Variable yij (with i = j) is 1 when node i has a transmission power which allows it to reach node j, yij = 0 otherwise.

cij yij ; (4) (MPSC1) Min (i; j)∈A

s:t:

yij 6 yiaij

∀(i; j) ∈ A; aij = i;

xij 6 (|V | − 1)yij

(5)

∀(i; j) ∈ A;

∀(i; j) ∈ A;

|V | − 1 xij − xki = −1 (i; j)∈A (k; i)∈A

(6)

xij 6 (|V | − 1)yji

xij ∈ R

∀(i; j) ∈ A;

yij ∈ {0; 1}

∀(i; j) ∈ A:

(7) if i = s otherwise

∀i ∈ V;

(8) (9) (10)

Constraints (5) realize the incremental mechanism by forcing the variables associated with arc (i; aij ) to assume value 1 when the variable associated with arc (i; j) has value 1, i.e. the arcs originated in the same node are activated in increasing order of p. Inequalities (6) and (7) connect the Now variables x to y variables. Eq. (8) deIne the Now problem, while (9) and (10) are domain deInition constraints. We refer the interested reader to Magnanti and Wolsey [9] for a more detailed description of the spanning tree formulation behind the formulation presented above. 3.2. Formulation MPSC2 In the novel formulation MPSC2 a spanning tree is deIned by z variables. Variable zij is 1 if edge {i; j} is on the spanning tree, zij = 0 otherwise. Variable yij (with i = j) is 1 when node i has

ARTICLE IN PRESS 6

R. Montemanni, L.M. Gambardella / Computers & Operations Research

a transmission power which allows it to reach node j, yij = 0 otherwise.

(MPSC2) Min cij yij ;

(

)

–

(11)

(i; j)∈A

s:t:

∀(i; j) ∈ A; aij = i;

yij 6 yiaij

(12)

zij 6 yij

∀{i; j} ∈ E;

(13)

zij 6 yji

∀{i; j} ∈ E;

(14)

zij ¿ 1

∀S ⊂ V;

(15)

{i; j}∈E; i∈S; j ∈V \S

zij ∈ {0; 1}

∀{i; j} ∈ E;

(16)

yij ∈ {0; 1}

∀(i; j) ∈ A:

(17)

Constraints (12) realize the incremental mechanism by forcing the variables associated with arc (i; aij ) to assume value 1 when the variable associated with arc (i; j) has value 1, i.e. the arcs originated in the same node are activated in increasing order of p. Inequalities (13) and (14) connect the spanning tree variables z to y variables. Eq. (15) state that all the vertices have to be mutually connected in the subgraph induced by z variables, while (16) and (17) are domain deInition constraints. 3.3. New valid inequalities The meaning of y variables is the same in formulations MPSC1 and MPSC2. For this reason it is possible to deIne structural inequalities, based on y variables, which are valid for both the formulations. The new constraints will be used to strengthen formulations MPSC1 and MPB2. In Section 6 we will present an experimental study which shows that the computational times required to solve the two integer programs are drastically reduced when these new constraints are added to them. In the remainder of this section we will refer to the subgraph of G deIned by the y variables with value 1 as Gy . Formally, Gy = (V; Ay ), where Ay = {(i; j) ∈ A|yij = 1 in the solution of MPSC}. Theorem 1 (Connectivity inequalities): The set of inequalities yij = 1

∀(i; j) ∈ A s:t: aij = i

(18)

is valid for formulations MPSC1 and MPSC2. Proof. In order to have the graph Gy connected, each node must be able to communicate with at least one other node. Then its transmission power must be suKcient to reach at least the node which is closest to it, i.e. yiaij = 1.

ARTICLE IN PRESS R. Montemanni, L.M. Gambardella / Computers & Operations Research

(

)

–

7

Theorem 2 (Bidirectional inequalities 1). The set of inequalities yaij i ¿ yiaij − yij ∀(i; j) ∈ A s:t: aij = i

(19)

is valid for formulations MPSC1 and MPSC2. Proof. If yij = 1 then yiaij = 1 because of inequalities (5) and consequently in this case the constraint does not give any new contribution. If yij = 0 and yiaij = 0 then again the constraint does not give any new contribution. If yij = 0 and yiaij = 1 then the transmission power of node i is set to reach node aij and nothing more. The only reason for node i to reach node aij and nothing more is the existence of a bidirectional link on edge {i; aij } in Gy . Consequently yaij i must be equal to 1, as stated by the constraint. Theorem 3 (Bidirectional inequalities 2). The set of inequalities yji ¿ yij ∀(i; j) ∈ A s:t: @(i; k) ∈ A; aik = j

(20)

is valid for formulations MPSC1 and MPSC2. Proof. If yij = 0 the constraint does not give any new contribution. If yij = 1 then the transmission power of node i is set in such a way to reach node j, which is the farthest node from i in G. The only reason for node i to reach node j is the existence of a bidirectional link on edge {i; j} in Gy . Consequently yji must be equal to 1, as stated by the constraint. Theorem 4 (Tree inequality): The inequality

yij ¿ 2(|V | − 1)

(21)

(i; j)∈A

is valid for formulations MPSC1 and MPSC2. Proof. In order to be strongly connected, the directed graph Gy must have at least 2(|V | − 1) arcs, as stated by constraint (21). Theorem 5 (Strong connectivity inequalities): The set of inequalities

yji ¿ 1 ∀i ∈ V

(22)

j ∈V s:t: ( j; i)∈A

is valid for formulations MPSC1 and MPSC2. Proof. Each node must be in the transmission range of at least one other node in order to have the graph Gy strongly connected. Denition 2. Ga = (V; Aa ) is the subgraph of the complete graph G such that Aa = {(i; j)| aij = i}. Notice that |Aa | = |V | by deInition.

ARTICLE IN PRESS 8

R. Montemanni, L.M. Gambardella / Computers & Operations Research

(

)

–

Denition 3. Ri = {j ∈ V | j can be reached from i in Ga }. Theorem 6 (Reachability inequalities 1): The set of inequalities

ykl ¿ 1 ∀i ∈ V

(23)

(k;l)∈A s:t: k ∈Ri ;l∈V \Ri

is valid for formulations MPSC1 and MPSC2. Proof. Since graph Gy must be strongly connected, it must be possible to reach every node j starting from each node i. This implies that at least one arc must exist between the nodes which is possible to reach from i in Ga (i.e. Ri ) and the other nodes of the graph (i.e. V \ Ri ). Denition 4. Qi = {j ∈ V | i can be reached from j in Ga }. Theorem 7 (Reachability inequalities 2): The set of inequalities

ykl ¿ 1 ∀i ∈ V

(24)

(k;l)∈A s:t: k ∈Qi ;l∈V \Qi

is valid for formulations MPSC1 and MPSC2. Proof. Since graph Gy must be strongly connected, it must be possible to reach every node i from every other node j of the graph. This means that at least one arc must exist between the nodes which cannot reach i in Ga (i.e. V \ Qi ) and the other nodes of the graph (i.e. Qi ). 3.3.1. Dominance rules The following theorem states that when inequalities (18) are used, a simpliIed version of inequality (21), with a smaller number of non-zero elements, can be adopted. Theorem 8. The inequality

yij ¿ |V | − 2

(25)

(i; j)∈A s:t: aij =i

is valid for formulations MPSC1 and MPSC2 and, if used together with inequalities (18), is equivalent to inequality (21). Proof. Since inequalities (18) force exactly one y variable to be equal to 1 for each i ∈ V , the y variables set to 1 by inequalities (18) are |V | in total. This observation, used within inequality (21), leads to inequality (25), which is consequently valid and equivalent to constraint (21) when used together with inequalities (18). A dominance of inequalities (18), (19) and (20) used together, on inequalities (18) and (22) used together is deIned in the following theorem. Theorem 9. If inequalities (18) are in use, inequalities (22) are dominated by inequalities (19) and (20).

ARTICLE IN PRESS R. Montemanni, L.M. Gambardella / Computers & Operations Research

(

)

–

9

Proof. Inequalities (18) imply that for each i ∈ V there exists at least one k ∈ V such that yik = 1, while inequalities (19) force the Irst variable yaij i such that yij = 0 and yiaij = 1 to assume value 1. This forces constraints (22) to be satisIed for each i ∈ V where ∃k ∈ V for which yik = 0, since yaik i will be 1 because of inequalities (19). If yik = 1 ∀k ∈ V then inequalities (20) guarantee that constraint (22) is satisIed also for i. Theorem 10 states that inequalities (22) can be left out when inequalities (18), (19) and (20) are used together. 4. Preprocessing procedure The results described in this section are used to delete some arcs of graph G and consequently to reduce the number of variables of formulations MPSC1 and MPSC2. We suppose an heuristic solution for the problem, heu, is available, and its cost is cost(heu). All the variables that, if active, would induce a cost higher than cost(heu) can be deleted from the problem. Theorem 10. If the following inequality holds

pij + pji + pkl ¿ cost(heu)

(26)

k ∈V \{i; j }; akl =k

then arc (i; j) can be deleted from A. Proof. Using the same intuition at the basis of the proofs of Theorems 2 and 3, we have that if pij is the power of node i in a solution, this means that the power of node j must be greater than or equal to pji (i.e. arc (j; i) must be in the solution), because otherwise there would be no reason for node i to reach node j. The left-hand side of inequality (26) represents then a lower bound for the total power required in order to maintain the network connected in case node i transmits to a power which allows it to reach node j and nothing farther. For this reason, if inequality (26) holds, arc (i; j) can be deleted from A. It is important to notice that once arc (i; j) is deleted from A, the value of the ancestor of node k, with aik = j, has to be updated to aij . 5. Exact algorithms 5.1. Exact algorithm EX 1 EX 1 solves directly MPSC1R , which is formulation MPSC1 (see Section 3.1) reinforced with the inequalities (18), (19), (20), (23), (24) and (25). These inequalities have been chosen on the basis of the experimental results which will be presented in Section 6.1.

ARTICLE IN PRESS 10

R. Montemanni, L.M. Gambardella / Computers & Operations Research

(

)

–

5.2. Exact algorithm EX 2 EX 2 is based on formulation MPSC2R , which is formulation MPSC2 (see Section 3.2) reinforced with the inequalities (18), (19), (20), (23), (24) and (25). These inequalities have been chosen on the basis of the experimental results which will be presented in Section 6.1. The idea at the basis of the method is that it is very diKcult to deal directly with constraints (15) of formulation MPSC2R in case of large problems. For this reason some techniques which leave some of these constraints out have to be considered. In this section we present an iterative approach which in the beginning does not consider any constraint (15), and adds them step by step in case they are violated. In order to speed up the approach, the following inequality should also be added to the initial integer program.

zij ¿ |V | − 1: (27) {i; j}∈E

Inequality (27) forces the number of active z variables to be at least |V | − 1 (this condition is necessary in order to have a spanning tree) already at the very Irst iterations of the algorithm. The integer program IP, deIned as MPSC2R without constraints (15) but with inequality (27), is solved and the values of the z variables in the solution are examined. If the edges corresponding to variables with value 1 form a spanning tree then the problem has been solved to optimality, otherwise constraints (28), described below, are added to the integer program and the process is repeated. At the end of each iteration, if edges corresponding to z variables with value 1 in the last solution generate a set CC of connected components, with |CC| ¿ 1, then the following inequalities are added to the formulation:

zij ¿ 1 ∀C ∈ CC (28) {i; j}∈E; i∈C; j ∈V \C

Inequalities (28) force z variables to connect the (elsewhere disjoint) connected components of CC. Algorithm EX 2 is summarized in Fig. 4, where a pseudo-code is presented.

Fig. 4. A pseudo-code for the exact algorithm EX 2.

ARTICLE IN PRESS R. Montemanni, L.M. Gambardella / Computers & Operations Research

(

)

–

11

6. Computational results Computational tests have been carried out on problems randomly generated as described in Althaus et al. [1]. For each problem of size |V | generated, |V | points (nodes) have been chosen uniformly at random from a grid of size 10000 × 10000. A SUNW Ultra-30 machine has been used for the tests, and ILOG CPLEX 2 6.0 has been adopted to solve integer programs. 6.1. New valid inequalities Table 1 shows how the lower bounds for the optimal solution costs of MPSC1 provided by LR(MPSC1), the linear relaxation of MPSC1, improves very much when the new valid inequalities presented in Section 3.3 are added to the linear relaxation itself. Each row of the table shows the ratios between the solution cost of the reinforced linear relaxation and the solution cost of the integer program MPSC1. In Table 1 we consider problems with |V | = 10 and |V | = 20. Ten instances are generated and solved for each of these values and average results are presented. The results in Table 1 are very promising. The valid inequalities presented in Section 3.3 are capable of an average improvement in the lower bound provided by LR(MPSC1) from 0.26 to 0.91 for problems with |V | = 10 and from 0.21 to 0.78 for problems with |V | = 20. Another interesting information which emerges from Table 1 is that the quality of the estimates incrementally increases when new valid inequalities are added. This suggests that the constraints described in Section 3.3 describe di+erent structural characteristics of the polytope of MPSC1. Table 1 Average improvements to the linear program LR(MPSC1) Extra inequalities

(Cost LR/Cost IP)

considered

|V | = 10

|V | = 20

none (18) (19)+(20) (21) (23) (24) (23)+(24) (18)+(19)+(20) (18)+(25) (18)+(23)+(24) (18)+(23)+(24)+(25) (18)+(19)+(20)+(25) (18)+(19)+(20)+(23)+(24) (18)+(19)+(20)+(23)+(24)+(25)

0.26 0.60 0.26 0.35 0.33 0.34 0.38 0.82 0.63 0.71 0.71 0.84 0.91 0.91

0.21 0.48 0.21 0.32 0.31 0.31 0.38 0.63 0.52 0.63 0.64 0.65 0.78 0.78

2

http://www.cplex.com.

ARTICLE IN PRESS 12

R. Montemanni, L.M. Gambardella / Computers & Operations Research

(

)

–

Table 2 Average solving times (s) for some reinforced versions of formulation MPSC1 Extra inequalities

Comp. time (s)

considered

|V | = 10

|V | = 20

none (18) (19)+(20) (21) (23) (24) (23)+(24) (18)+(19)+(20) (18)+(25) (18)+(23)+(24) (18)+(23)+(24)+(25) (18)+(19)+(20)+(25) (18)+(19)+(20)+(23)+(24) (18)+(19)+(20)+(23)+(24)+(25)

20.97 5.12 4.99 34.06 20.92 18.04 16.26 0.36 7.19 4.14 6.36 0.37 0.17 0.15

8615.32 — 1050.37 — — — 7918.93 — — — 411.15 78.59 — 4.49

In Table 2 we present the computation times necessary to solve the integer program MPSC1 when some of the valid inequalities presented in Section 3.3 are added to it. Averages over 10 runs for problems with |V | = 10 and |V | = 20 are presented. In the column |V | = 20 only some signiIcant entries are reported. The results presented in Table 2 are interesting because di+erent combination of families of inequalities lead to very di+erent computation times. The introduction of some inequalities (e.g. (21)) leads to average computation times which are longer than those obtained by solving the original integer program without reinforcements (row none), but on the other hand, the best results are achieved when all the new inequalities are added to MPSC1 (last row). This conIrms the indication already given by Table 1 about the mutual complementarity of the new inequalities we propose. Using all of these constraints the average computation times are reduced by a factor of 140 for problems with |V | = 10 and by a factor of 1919 for problems with |V | = 20. Since the role of y variables—the only ones involved in the new valid inequalities—is the same in both formulations MPSC1 and MPSC2, it is reasonable to expect that the results presented in this section are valid also for MPSC2. 6.2. Preprocessing procedure In order to apply the preprocessing procedure described in Section 4, a heuristic solution to the problem has to be available. For this purpose we use one of the simplest algorithms available, MST , which works by calculating the Minimum Spanning Tree (see Prim [10]) on the weighted graph with costs deIned by Eq. (1), and by assigning the power of each transmitter i to piiT , as described near the end of Section 2. It is worth to notice that if better algorithms (see, for example, Althaus et al. [1]) have had been adopted, also the preprocessing technique would have produced better results than those reported in the remainder of this section.

ARTICLE IN PRESS R. Montemanni, L.M. Gambardella / Computers & Operations Research

(

)

–

13

Table 3 Average percentage of arcs deleted |V |

10

15

20

25

30

35

40

45

50

Arcs deleted (%)

57.556

63.781

66.526

70.393

72.464

74.647

76.106

77.568

78.688

Table 4 Average computation times (s) Algorithms

Althaus et al. [1] EX 1 Preprocessing + EX 1 Preprocessing + EX 2

|V | 10

15

20

25

30

35

40

2.144 0.192 0.078 0.052

18.176 0.736 0.289 0.196

71.040 8.576 0.715 0.601

188.480 33.152 4.924 2.181

643.200 221.408 28.908 13.481

2278.400 1246.304 87.357 28.172

15120.000 9886.080 583.541 79.544

In Table 3 we present, for di+erent values of |V |, the average percentage of arcs deleted by the preprocessing procedure over 50 runs. Table 3 suggests that the preprocessing technique we propose dramatically simpliIes problems. In particular it is interesting to observe how the percentage of deleted arcs considerably increases when the number of nodes increases. This means that, when dimensions increase, the extra complexity induced by extra nodes is partially mitigated by the eKciency increase of the preprocessing technique. The computation time required by the preprocessing technique was always negligible (i.e. in the order of a few seconds for the biggest problems).

6.3. Exact algorithms In Table 4 we present the average computation times required by the exact algorithms for di+erent values of V . Fifty instances are considered for each value of |V |. The results in the second column are those presented in Althaus et al. [1], obtained on an AMD Duron 600 MHz PC multiplied by a factor of 3.2 (as suggested in Dongarra [11]) in order to make them comparable with the other results of the table. Table 4 shows that the new exact algorithms we propose outperform the other methods. In particular it is important to observe that the gap between the computational times of these algorithms and those of the other methods tends to increase when the number of nodes considered increases. The comparison of the third and fourth rows of Table 4 also highlights the beneIt derived from the use of the preprocessing technique described in Section 4. The computational times of the algorithm EX 1 are improved up to 17 times (for |V | = 40) when this technique is used.

ARTICLE IN PRESS 14

R. Montemanni, L.M. Gambardella / Computers & Operations Research

(

)

–

7. Conclusion The minimum power symmetric connectivity problem in wireless network has been studied in this paper. Two new mixed integer programming formulations for the problem has been proposed together with some new valid inequalities for the corresponding polytopes. Two exact algorithm based on the new formulations were also presented together with a new preprocessing technique. Experimental results have been Inally presented. They show the e+ectiveness of the new valid inequalities and of the new preprocessing technique. A validation for the new exact algorithms is also given. They are proven to outperform methods recently appeared in the literature. References [1] Althaus E, CRalinescu C, MRandoiu II, Prasad S, Tchervenski N, Zelikovsky A. Power eKcient range assignment in ad-hoc wireless networks. In: Proceedings of the IEEE Wireless Communications and Networking Conference (WCNC’03), 2003. p. 1889–94. [2] Clementi A, Penna P, Silvestri R. On the power assignment problem in radio networks. Technical Report TR00-054, Electronic Colloquium on Computational Complexity (ECCC), 2000. [3] Das AK, Marks RJ, El-Sharkawi M, Arabshani P, Gray A. Minimum power broadcast trees for wireless networks: integer programming formulations. In: Proceedings of the IEEE INFOCOM 2003 Conference, 2003. [4] Wieselthier J, Nguyen G, Ephremides A. On the construction of energy-eKcient broadcast and multicast trees in wireless networks. In: Proceedings of the IEEE INFOCOM 2000 Conference, 2000. p. 585–94. [5] Marks II RJ, Das AK, El-Sharkawi M, Arabshani P, Gray A. Minimum power broadcast trees for wireless networks: optimizing using the viability lemma. In: Proceedings of the IEEE International Symposium on Circuits and Systems (ISCAS 2002), 2002. [6] Das AK, Marks II RJ, El-Sharkawi M, Arabshahi P, Gray A. The minimum power broadcast problem in wireless networks: an ant colony system approach. In: Proceedings of the IEEE Workshop on Wireless Communications and Networking, 2002. [7] Rappaport T. Wireless communications: principles and practices. Englewood Cli+s, NJ: Prentice-Hall; 1996. [8] Heinzelman WR, Sinha A, Wang A, Chandrakasan AP. Energy-scalable algorithms and protocols for wireless microsensor networks. In: Proceedings of the IEEE International conference on Acoustic, Speech, and Signal processing ICASSP, 2000. [9] Magnanti TL, Wolsey L. Optimal trees. In: M.O. Ball et al., editors. Network Models, Handbook in operations research and management science, vol. 7. North-Holland: 1995. p. 503–615. [10] Prim RC. Shortest connection networks and some generalizations. Bell System Technical Journal 1957;36:1389–401. [11] Dongarra JJ. Performance of various computers using standard linear algebra software in a fortran environment. Technical Report CS-89-85, University of Tennessee, October 2003.