INTEGER PROGRAMMING MODEL | Network Planning for IEEE 802.16j Relay Networks

Four sets of tests were performed with the basic variant of the problem to determine its sensitivity to different parameters.

In the first experiment, all three parameters were scaled—the number of candidate BSs, candidate RSs, and TPs. The number of BSs was varied and the numbers of RSs and TPs were three times and ten times this figure, respectively. Figure 1 shows how the time required finding a solution scales up. As it can be seen, the problem can be solved for up to 80 candidate BSs and 240 RSs with ease. Further, the results show that the problem complexity is scaling up quite rapidly. Indeed, further experiments were performed in which the number of candidate BSs was increased to 120 and the resulting execution mean time was under 30 min. The system is exhibiting scaling properties which are quite nonlinear, although some basic curve fitting has shown that for the available data set, the scaling is considerably less than exponential.

 
Figure 1: Calculation time when three parameters are scaled at the same time.

Figure 2 shows the calculation time when only the number of BSs is scaling. The number of RSs is set to 90 and the number of TPs is set to 300 in all tests.

 
Figure 2: Calculation time when only the number of BS is scaled.

A similar experiment was performed in which the number of RSs was scaled up and the number of BSs and TPs remained constant. Again it is clear that the system is scaling up linearly in this parameter (Figure 3). The number of BSs is set to 30 and the number of TPs is set 300 in all tests.

 
Figure 3: Calculation time when only the number of RS is scaled.

Finally, in this set of experiments, the sensitivity to the number of TPs was considered. The same characteristic is again observed: the system scales linearly as can be seen from Figure 4. The number of BSs is set to 30 and the number of RSs is set to 90 in all tests.

 
Figure 4 Calculation time when only the number of TP is scaled.

From the figures, it can be seen that this algorithm should suit small size network planning problems since the time cost is very short for small number of BSs. The time varies almost linearly if individual parameter is varying. For the problem sizes studied—which are typical for small metropolitan scenarios—the solution can be found quickly on typical desktop computers, e.g., under two minutes for problems with 50 candidate BS sites, and approximately ten minutes for problems with 100 candidate BS sites. The time cost for the planning could increase to one day long or a few days to plan a larger network, e.g., around 500 candidate sites, but it is still practicable.