5. Computational Results

The algorithms for FBS and ModBIP are implemented in C++, and the IP formulation in Sect. 2.2 is solved by ILOG OPL Studio 3.7 and CPLEX 9.0. All computations are performed on an Intel Xeon 2.00 GHz PC with 1 GB of memory.

In all experiments, the nodes are distributed randomly in a 10 10 grid, and the channel loss component a is equal to 4. In order to test to impact of the tightness of the delay bounds, we generate uniformly distributed delays U(1, [log ₂ N]) and U(1, N - 1). Each node is selected as a destination node with probability p = 0.5, 0.75 or 1 where p = 1 corresponds to broadcasting instances. For each combination of parameters, 50 problem instances are generated randomly for N = 10, 20, 30, 40, 50. For small problem instances with N = 10 and N = 20, we compare the performances of FBS and ModBIP against the optimal solution. For larger problems, the heuristics are benchmarked against each other. After preliminary experiments, the filter, beam and child widths in FBS are set to f = 0.3 N, b = 0.2 N and c = 0.1 N, respectively.

In each cell of Table 1, the number in the first row is the number of optimal solutions obtained, and the numbers in parentheses are the average and maximum optimality gaps, respectively.