Power-Aware Multi-Send in Wireless Networks

Abstract

We study offline routing and scheduling in geometric wireless networks under the wireless broadcast advantage (WBA). Each receiver can accept at most k messages per slot, and the objective is lexicographic: minimizing the total energy and scheduling length (makespan). The model isolates routing and synchronization before adding full SINR interference and fading. We evaluate a practical three-approach portfolio: sender-centric local improvement, shortest-path routing, and direct transmission, all scheduled by a feasible greedy baseline. The main structural result is negative: every receiver-greedy non-idling scheduler may incur an $\Omega(|V|)$ energy overhead even on essentially optimal routing, since it cannot deliberately synchronize transmissions across time. Our analysis gives explicit energy polynomial bounds for all three approaches, route-aware schedule-length bounds for the local and shortest approaches, and exact makespan optimality for direct transmission. Experiments on random and structured instances illustrate the behavior of the portfolio, show when sender-side aggregation beats shortest-path routing, and demonstrate that a simple timeout-based waiting rule at aggregation hubs can recover a substantial part of the lost batching gain.1