Optimal Balancing of Satellite Queues in Packet Transmission to Ground Stations

摘要

Satellites collecting data store packets in queues and transmit these packets to ground stations within their view. In a given time step, a ground station may see several satellites, but can receive a packet from only one of them. A satellite can send each packet from its queue to a ground station in its view. We consider the problem of finding an assignment of satellites to ground stations that results in all ground stations receiving a packet while optimally balancing the sizes of remaining queues at satellites. We give a polynomial time algorithm for solving this problem which requires O((m + n)~3n) arithmetic operations, where m is the number of satellite queues and n is the number of ground stations.