Scheduling Partition for Order Optimal Capacity in Large-Scale Wireless Networks

Abstract—The capacity scaling property specifies the change of network throughput when network size increases. It serves as an essential performance metric in large-scale wireless networks. Existing results have been obtained based on the assumption of using a globally planned link transmission schedule in the network, which is however not feasible in large wireless networks due to the scheduling complexity. The gap between the well-known capacity results and the infeasible assumption on link scheduling potentially undermines our understanding of the achievable network capacity. In this paper, we propose the scheduling partition methodology that decomposes a large network into small autonomous scheduling zones and implements a localized scheduling algorithm independently in each partition. We prove the sufficient and the necessary conditions for the scheduling partition approach to achieve the same order of capacity as the widely assumed global scheduling strategy. In comparison to the network dimension pn, scheduling partition size (r(n)) is sufficient to obtain the optimal capacity scaling, where r(n) is the node transmission radius and much smaller than pn. We finally propose a distributed partition protocol and a localized scheduling algorithm as our scheduling solution for maximum capacity in large wireless networks. Index Terms—Wireless multihop networks, capacity scaling, link scheduling, network decomposition, network design. F