Rollout Algorithms for Integrated Topology Control and Routing in Wireless Optical Backbone Networks
Abstract
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.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jan 01, 2003
- Accession Number
- ADA438507
Entities
People
- Abhishek Kashyap
- Kwangil Lee
- Mark Shayman
Organizations
- University of Maryland