Comparison between Maximal Independent Sets and Maximal Cliques Models to Calculate the Capacity of Multihop Wireless Networks

Citation

Heal M & Li J (2020) Comparison between Maximal Independent Sets and Maximal Cliques Models to Calculate the Capacity of Multihop Wireless Networks. In: Arai K & Bhatia R (eds.) Advances in Information and Communication. FICC 2019. Lecture Notes in Networks and Systems, 70. FICC 2019: Future of Information and Communication Conference, San Francisco, CA, USA, 14.03.2019-15.03.2019. Cham, Switzerland: Springer International Publishing Company, pp. 603-615. https://doi.org/10.1007/978-3-030-12385-7_44

Abstract
In this work we compare two models to calculate the capacity of multihop wireless networks. The first model utilizes the maximal independent sets of the conflict graph. The problem in that model is formulated as a linear program. The second model in our comparison utilizes the maximal cliques of the conflict graph using integer programming. We see the second model is much more efficient in calculating the capacity for larger networks. We make no assumption on the interference models and we only model it by assuming a conflict matrix. First, we prove there is a periodic schedule for the flow, by using that we formulate our integer programming model to attain maximum capacity for the network. We consider one source of data and one destination i.e. a single commodity network.

Keywords
Maximal independent set; Maximal clique; Linear programming; Binary programming; Maximum throughput

Journal
Lecture Notes in Networks and Systems; Advances in Information and Communication