The objective of these tests can be divided into two parts. One is to obtain an understanding of the scalability of the problem formulation—the basic and the state space reduction model. More specifically, the objective was to understand if this problem formulation can be used to solve problems of realistic size. Given that it is, in principle, an NP-hard problem, it is important to understand the range of problems for which standard solution techniques are appropriate and the range of problems which require the development of heuristics which employ domain knowledge.
The second is to determine how the clustering approach compares with the more rudimentary approaches. The comparison was performed based on both the time taken to obtain a solution and the quality of the resulting solution; naturally, the former relates directly to the scalability characteristics of the approach and its applicability for realistic scenarios.
A number of tests were performed in which the number of BSs, RSs, and TPs were varied. All tests were done using a standard desktop computer—Centrino Duo 2.0 GHz, 1 GB Memory, Windows Vista. Twelve tests were performed each time and the mean execution time taken. As there was some variation in the results, the minimum and maximum execution times were removed and the mean taken over the remaining ten results.
Problems were generated at random. The locations of each of the BSs, RSs, and TPs were chosen randomly from an area of size 3 × 3 km. The (x, y) coordinates of each node were chosen by selecting two random variable from the distribution U(0, 3000). For each of the problems the same set of weight parameters were used: λ1 = 8, λ2 = 8, and λ3 = 20. However, it is worth noting that the values of these parameters have little impact on the time required to find solutions. In each of the problems, the BS cost was chosen at random and was three times the cost of the RS.
In all of the following tests, the branch and bound method found the optimal solution to the given problem. Figure 1 shows one possible result for planning a network with 20 candidate BSs, 60 candidate RSs, and 200 TPs. In the solution, 10 BSs are selected with 36 RSs
