Relay placement for minimizing congestion in wireless backbone networks

Wireless optical networks are being increasingly used in the backbone of hierarchical ad hoc networks. We consider the problem of minimizing the congestion in wireless optical (FSO) backbone networks by placing controllable relay nodes. We propose algorithms for placement of relays in the network under node interface constraints. The interfaces at each backbone node are limited, thus limiting the number of neighbors a node can have. We come up with algorithms to formulate the problem as a constrained knapsack problem, and propose algorithms to solve it. We use the mathematical technique of rollout to achieve better performance than the heuristics. We show by simulations that our algorithms significantly outperform some greedy algorithms, and a small number of relay nodes (when placed using our algorithms) can lead to a significant reduction in the congestion in the network