Abstract: Many features of the wireless ad hoc networks (WAHNs) like resource limitation, multi-hop communication, dynamic topology and lack of infrastructure make them very attractive and rise many challenging optimization problems. In this study, we propose original preprocessing techniques applied to the Minimum Power Multicasting (MPM) problem in WAHNs in order to reduce the size of the instances and, consequently, the time required to solve them. The experimental results prove that these reduction procedures, based on the graph model representation, are a promising way of speeding up a possible solution method for the MPM problem already developed in the literature.
INTRODUCTION
Wireless networks are a special kind of networks in which the traditional cable links of the wired networks are replaced by radio links. There are infrastructured wireless networks and ad hoc wireless networks (Oliveira and Pardalos, 2005; Wieselthier et al., 2002). Wireless ad hoc networking is truly one of the most challenging and evolving research areas in both theory and practice (Resende and Pardalos, 2006), but still more thorough theoretical investigations are required.
A Wireless Ad Hoc Network (WAHN) is an autonomous system consisting of mobile hosts connected by a shared wireless channel. Thus, the devices of the WAHNs (called nodes) communicate with each other through a radio channel (called link), without the use of any fixed infrastructure or centralized administration. The major advantages of the WAHNs, like rapid deployment, robustness, independence of infrastructure, flexibility and support for mobility, make them very attractive and useful in several civil or military fields. The wide range of their applications includes emergency search-and-rescue operations, data acquisition operations in areas where natural disasters have destroyed the existing infrastructure, decision making in battlefield environment, video-conferencing, Internet access, exchange of information in buildings or trains, etc.
Unlike in wired networks, where a transmission from i to j generally reaches only node j, in wireless networks with omnidirectional antennas it is possible to reach several nodes with a single transmission without any additional cost. Indeed, if node i is assigned a transmission power to reach directly node j (single-hop communication), then all the nodes within this transmission range are also reached by the signal. This feature is known as Wireless Multicast Advantage (WMA) property (Wieselthier et al., 2001). Moreover, a terminal can communicate indirectly with another node located out of its transmission range in a multi-hop fashion, using intermediate devices (acting as routers) that relay the data packets from the source of the messages to the destination nodes. In other words, a terminal is not only responsible for sending and receiving its own data, but it possibly forwards the traffic of other terminals.
The communications are performed consuming energy and, since the devices are usually powered by batteries, energy saving is a fundamental issue in this kind of networks. Therefore, by optimizing the transmission powers assigned to the nodes for routing the messages, the waste of energy is reduced and the interference over the network is limited. In this way, also the quality of the communication is improved.
Many contributions have focused on the solution of the MPM problem (Wieselthier et al., 2001, 2002; Das et al., 2003; Guo and Yang, 2006; Leggieri et al., 2008; Bauer et al., 2008). In particular, in this study we start from the results contained by Leggieri et al. (2008) and we apply our preprocessing procedures in order to reduce the computational time required to solve the instances.In this manuscript, we present a mathematical model for the MPM problem, we propose graph-based reduction techniques, we provide the results of our computational experiments and we compare them with those obtained by Leggieri et al. (2008).
MULTICAST COMMUNICATION MODEL
The multicast problem consists in connecting a specified node (called source) with a set of nodes (called destinations) with the possibility of using other devices of the network as relay nodes (routers). We consider here static WAHNs, that is, the terminals of the network are supposed to be stationary at the moment of the transmission. Furthermore, we assume that no power expenditure is involved in signal reception/processing activities. The interference problem is also omitted.
For a given network topology with a specified source node, the Minimum Power Multicasting (MPM) problem consists in assigning transmission powers to the devices of the network such that the connection between the source and all the destinations is guaranteed and the total energy consumption is minimized.
The MPM problem is a generalization of the well-known Minimum Power Broadcasting (MPB) problem (Das et al., 2003; Montemanni and Gambardella, 2004), since the last one is obtained when the set of the destinations coincides with all of the nodes of the network (except the source). Both the MPM and the MPB problems are NP-hard and hence are difficult to solve to optimality (Clementi et al., 2001).
The MPM problem can be modelled in terms of a graph, by considering the devices of the WAHN as nodes and the transmission links as arcs.
Let G(V, A) be a directed complete graph, where the set of nodes V represents
the set of devices of the network and the set of directed arcs A represents
the transmission links between the nodes, i.e., all the possible pairs (i, j),
with i, j ε V, i
By the assumption of static network, the distances dij between any two nodes i and j can be easily computed (therefore they are considered known a priori). With every arc (i, j) ε A is associated a cost pij representing the minimum quantity of power necessary to establish a direct communication from node i to node j. According to the commonly used simple signal propagation model of Rappaport (1996), the transmission power pij is proportional to a power of the distance dij, i.e., pij = (dij)k where k (typically in the range between 2 and 5) is an environment-dependent exponent.
PREPROCESSING TECHNIQUES
The MPM problem in WAHNs can be formulated in terms of mixed, integer or 0-1 linear program, where the objective function is the sum of the powers assigned to the nodes and the constraints guarantee the connection between the source and each destination. Therefore, several logical processing procedures known in literature (Guignard et al., 2005) can be applied to this problem.
In general, the preprocessing techniques consist in manipulating a formulation of a given mixed integer program in order to decrease the overall time required for its solution. These procedures reduce the feasible region in such a way that at least one of the optimal solutions remains feasible. It is common to use different preprocessing techniques before effectively starting to solve the problems. The preprocessing significantly modifies a given problem’s formulation, by eliminating and substituting variables and constraints and even by changing the coefficients of the constraints and of the objective function. The programs solve the reduced formulation usually faster than the original one, providing the same optimal solution.
The commonly used logical preprocessing techniques proposed by Guignard et al. (2005) include: inconsistent constraints identification, redundant constraints elimination, variables' bounds strengthening, coefficients improvement, probing, etc.
In particular, MPM problem can be formulated as a Set Covering problem (Leggieri et al., 2008), allowing to use not only the general preprocessing techniques valid for all the integer or (0-1) problems, but also those specific for the Set Covering problem: dominated rows and columns elimination rules, Lagrangian cost based fixing, lifting/projection methods, etc. (Balas et al., 1991; Nemhauser and Wolsey, 1988).
Besides these preprocessing techniques, in the sequel we will introduce several
original rules which permit to reduce the size of the instances of the MPM problem,
based on its graph model representation. These procedures are applicable also
in the general case in which there is no symmetry between the transmission powers
(i.e., pij
The main goal of these preprocessing rules is the elimination of arcs (and possibly, of nodes) from the MPM problem's underlying graph.
A first arc elimination procedure is based on the observation, arising from the MPM problem definition, that the source transmits the message to the destinations and it does not have to receive the signal back.
Preprocessing rule 1: All the arcs entering the source node, that is, arcs having the form (i, s) for any i ε V, will be eliminated from the set A.
There will be eliminated exactly as many arcs as the incoming degree of node s.
Given a heuristic h for the MPM problem (for instance, one of the three multicasting versions of the Broadcast Incremental Power (BIP) algorithm proposed by Wieselthier et al. (2002)), we denote by c(h) its cost.
Preprocessing rule 2: If there is a transmission power pij such that pij>c(h), then the arc (i, j) will be eliminated from the set A.
Consider now a non-destination node j (different from the source) and the minimal power required for reaching directly this node by any other node of the network. If this power exceeds the maximal power required for a direct transmission from the source to all the destinations or the cost of a heuristic then, since we want to minimize the total power, node j will never act as a router in any optimal solution and hence:
Preprocessing rule 3: Let j
then eliminate node j from the set V and all its incident arcs from the set A.
Moreover, if the power required to reach a non-destination node j (different from the source) from a node kεV exceeds the maximal power necessary for a direct transmission from k to all of the destination nodes of the network then, for the same minimization arguments as before, the arc (k, j) can be eliminated.
Preprocessing rule 4: Let j
then the arc (k, j) will be eliminated from the set A.
Now we propose further techniques obtained by considering the minimum paths between nodes with powers as weights. Using the Dijkstra algorithm (Dijkstra, 1959), we can define P(i, j) as the set of the arcs of the shortest path from i to j having cost c(P(i,j)).
Preprocessing rule 5: Let j
then eliminate node j from the set V and all its incident arcs from the set A.
A generalization of the Preprocessing rule 4 is:
Preprocessing rule 6: Let j
then the arc (k, j) will be eliminated from the set A.
Let k be a non-destination node, different from the source. Assume that the
power required for a direct transmission from a node i (i
Preprocessing rule 7: Let k
| pik+pkj>pij |
is satisfied for every i ε V \{j, k}, then eliminate the arc (k, j) from the set A.
We notice that whenever we eliminate a node, we can eliminate all its incident arcs. Since
is the number of the arcs of a directed complete graph with k nodes, we have that:
Remark: If l is the number of nodes eliminated during the reduction procedures, then the number of arcs incident to them and eliminated is exactly
Obviously, all the above preprocessing techniques are iteratively applied in order to get all the possible nodes/arcs eliminations in the graph related to the MPM problem, causing a drastic and rapid reduction of the size of the instances and, consequently, a shorter CPU time required for their solution.
In order to better illustrate how the preprocessing rules perform, in the sequel, for sake of simplicity, we construct a numerical example in which powers are independent from the Euclidean distances.
Example: Consider the directed complete graph with V:={1,2,3,4,5,6} and D:={3,4}. Let s be node 5. Let P be the 6x6 symmetric cost matrix whose entries denote the transmission powers between nodes, defined by:
The cost of the heuristic computed using a multicasting version of BIP algorithm is equal to 63.
Applying the preprocessing rules, we observe that arcs (1,5), (2,5), (3,5), (4,5), (6,5) are eliminated by Preprocessing rule 1, as they are all incoming to the source.
Arcs (1,6), (2,4), (2,6), (3,5), (3,6), (4,2), (4,5), (4,6), (5,3), (5,4), (5,6), (6,1), (6,2), (6,3), (6,4), (6,5) have associated costs greater than 63, hence they are eliminated by Preprocessing rule 2.
Preprocessing rule 3 allows to eliminate node 6 and all its incident arcs;
indeed, 6 ∪ {5} = {3,4,5} and all its incident arcs; indeed, 6
Arcs eliminated by Preprocessing rule 4 are (3,1), (4,1), (3,2), (4,2), (6,2), (1,6), (2,6), (3,6), (4,6). For example, since arc (3,1) verifies
it can be erased. Similar considerations hold for the rest of the arcs.
With Preprocessing rule 5, nodes 2 and 6 and all their incident arcs are eliminated. Indeed, 2 ∪ {5}, node 3 is the closest destination to node 2 and 64 = c(P(5,2)∪P(2,3))>c(h) = 63. Concerning node 6, 6 ∪{5} and 87 = c(P(5,6))> c(h) = 63.
Arcs eliminated by Preprocessing rule 6 are (5,6), (3,1), (4,1), (3,2), (4,2), (6,2), (1,6), (2,6), (3,6), (4,6). Considering for example arc (5,6), we have that
and thus it can be eliminated. Analogously, it is easy to verify that the other arcs can be eliminated as well.
| Fig. 1: | Reduced graph after applying preprocessing rules |
Finally, with Preprocessing rule 7, arc (6,1) can be eliminated, since 6
We observe that there are nodes/arcs eliminated by different preprocessing rules. In this example the overall number of eliminated arcs is 25, which represents the 83.33% of the total number of arcs. The resulting reduced graph is depicted in Fig. 1. Despite nodes 2 and 6 have been eliminated, they are still reported as isolated nodes in order to illustrate the initial topology of the network .
RESULTS
This study extends the work that is described in Leggieri et al. (2008), following the line of investigation proposed there: developing a specialized preprocessing approach in order to speed up the solution method II.
We have implemented in C the proposed preprocessing techniques and the obtained procedure has been included in the existing code used in Leggieri et al. (2008). The codes had been run on an Opteron 246 machine with 2 GB RAM memory. Moreover, Cplex 10.2 has been used to solve all the obtained integer linear programming problems.
We performed our experiments on a set of test problems proposed in Leggieri et al. (2008) where the nodes are randomly generated (uniformly on a grid of size 10000x10000) and the source and the destinations of the network are selected in a random way among them. The test problems present a varying number of nodes (up to 100) and of destinations. For each problem 10 different instances have been generated. It is commonly used in literature to set to 2 the environment-dependent exponent k which allows us to determine the power values from the distances.
| Table 1: | Comparison of the solution methods with and without preprocessing |
| Bold values show the best average computational time | |
The solution process terminates when either a solution is found or the maximum solution time, set to 3600 sec, is reached.
We want to evaluate the advantage of introducing our new preprocessing procedure in the existing implementation of the solution method II. Therefore, we compare in Table 1 the average execution times T (in seconds) and the average number of iterations It (required to solve the instances) obtained by using our new version, indicated by Algorithm with preprocessing, with those obtained by running the solution method II of Leggieri et al. (2008), indicated by Algorithm without preprocessing. T and It are average values over all the solved instances of each problem.
Moreover, we consider the percentage A% of arcs eliminated during our preprocessing procedure applied to the graph, and also the rate T% of improvement (if any) of the solution time obtained by using the preprocessing procedure. We indicate with NS% the percentage of the instances not solved within the time limit.
In order to compute the cost of a heuristic for the solution of the MPM problem, we implemented a multicasting version of the BIP algorithm proposed by Wieselthier et al. (2002).
In Table 1 we highlight with a bold character the best average computational time among the solving methods.
As expected, if the size of the problem is small (n = 5), preprocessing the graph does not affect consistently the CPU time, but for networks with more than 10 nodes, it appears very convenient, in terms of solution time, to preprocess the graph. Indeed, we observe that in this case the average solution times are significantly improved. Furthermore, for the problem with n = 100 and m = 5, preprocessing the graph allows us to solve 60% of the instances instead of the 40% achieved by using only method II. In this case, the improvement rate T% has been approximated from below by fixing to 3600 sec the solution time for the two unsolved instances using method II, while solved by applying the preprocessing rules.
The overall execution time is reduced in average of about 38.42% and the number of iterations is almost always less than or equal to that of the Algorithm without preprocessing. We also notice that, even when the number of iterations is the same in the two approaches, the CPU time for the Algorithm with preprocessing is always reduced. Moreover, from the experimental results, we observed that, for a small value of m, the Preprocessing rules 5 and 6 eliminate much more nodes/arcs than the other procedures. Although only few arcs are eliminated by using Preprocessing rule 7, in certain cases and for problems with more than 30 nodes, this reduction highly reduce both the execution time and the number of iterations. Finally, the CPU results are enhanced when the percentage A% of eliminated arcs is considerable (in this case the goal of the preprocessing is achieved). The smallest percentage A% of eliminated arcs is obtained for the broadcasting version of each problem (when m = n-1), but this is explained by the fact that all of our proposed techniques, except Preprocessing rules 1 and 2, are related to non-destination nodes.
CONCLUSIONS
Our goal was to present efficient preprocessing techniques that reduce the size of the instances in order to obtain a corresponding adjacency matrix of smaller dimension, used as input data in the implementation of the Set Covering formulation developed for the MPM problem in Leggieri et al. (2008). For this reason we have proposed preprocessing rules based on the underlying graph network representation.
Our experimental study was realized by using randomly generated test problems as in Leggieri et al. (2008), with number of nodes varying from 5 to 100. The presented results show that our preprocessing procedure improves the performances obtained in Leggieri et al. (2008), since the total solution time is significantly reduced.Possible improvements may include the investigation of more sophisticated graph reduction techniques.