Throughput characterization of node-based scheduling in multihop wireless networks
Bo Ji, Yu Sang · 2016
Maximum Vertex-weighted Matching (MVM) is an important link scheduling algorithm for multihop wireless networks. Under certain assumptions, it has been shown that if the underlying network graph is bipartite, MVM not only maximizes the throughput in settings with continuous packet arrivals, but also minimizes the evacuation time (i.e., time to drain all the initial packets) in settings without future packet arrivals. Further, even if the network graph is arbitrary, MVM achieves the best known performance guarantee for the evacuation time among existing online link scheduling algorithms. Also, it empirically exhibits close-to-optimal throughput performance and good delay performance. However, in an arbitrary network graph the throughput performance of MVM has not been well understood. To that end, in this paper we aim to carry out a systematic study of the throughput performance of MVM, assuming single-hop flows and the node-exclusive interference model. Inspired by the celebrated Gallai-Edmonds structure theorem, we introduce a novel topological notion, called the Gallai-Edmonds decomposition factor, and rigorously prove that the efficiency ratio of MVM is no smaller than the Gallai-Edmonds decomposition factor of the network graph. Further, we show that if the smallest size of an odd cycle in a graph is 2m + 1 for a positive integer m, then the Gallai-Edmonds decomposition factor is equal to 2m/(2m + 1). This implies that the Gallai-Edmonds decomposition factor is at least 2/3 for an arbitrary graph and is equal to 1 for bipartite graphs. Having these results, the throughput performance of MVM can be well characterized.