Abstract

This work describes techniques for throughput optimization in a hierarchical cooperative sensing architecture known as a mobile backbone network. We develop a novel technique based on mixed integer linear programming, which leads to a dramatic reduction in computation time compared to existing exact algorithms.Furthermore, we describe a new polynomial-time approximation algorithm for this problem. We also formulate natural extensions to the mobile backbone network problem and describe exact and approximate solutions for these extensions. Finally, we apply our algorithms to a cooperative exploration problem.