Rollout Algorithms for Integrated Topology Control and Routing in Wireless Optical Backbone Networks

摘要

The authors consider a wireless backbone network with free space optical point-to-point links. Such a network could form a backbone for either a cellular or hierarchical ad hoc network. Each backbone node has a limited number of transceivers with which to establish links to neighbors. Given estimated aggregate traffic demands between source and destination backbone nodes, they consider the problem of topology control and routing -- determining which links to set up and which routes to establish to maximize the throughput. While the problem may be formulated as an integer linear program, its solution is computationally prohibitive. Consequently, they use the mathematical technique of rollout to develop effective heuristic algorithms. Through simulation experiments, the authors show that the performance of the rollout algorithms they derive is clearly superior to that of the initial heuristic algorithms on which they are based. For simulation experiments on a 50-node network, the rollout algorithms provided as much as a 12% improvement in throughput and 70% reduction in blocked demands compared with the heuristic algorithms from which they were derived.