Fast bandwidth allocation policies for persistent data ferrying

The persistent data ferrying problem has a naturally cascaded structure between vehicle and communication dynamics, allowing the bandwidth optimization to be encapsulated within a path planning optimization problem. This work analyzes policies that solve the inner bandwidth allocation problem quickly. Given a path and properties about the communication environment, the bandwidth allocation problem is formulated as a binary integer linear program. We show that it becomes equivalent to a knapsack problem. We theoretically analyze the performance of several bandwidth allocation policies in terms of computation effort and throughput of the solution. The performance characteristics are then validated through simulation, showing that the greedy knapsack solution achieves within 99% of the optimal allocation in less than 2% of the computation time. The quickness of this policy reduces the computational complexity needed to solve the full data ferry problem.