Conference Proceeding

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

Details

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

StatusPublished
Title of seriesLecture Notes in Networks and Systems
Number in series70
Publication date31/12/2020
Publication date online02/02/2019
URLhttp://hdl.handle.net/1893/30214
PublisherSpringer International Publishing Company
Place of publicationCham, Switzerland
ISSN2367-3370
eISSN2367-3389
ISSN of series2367-3370
ISBN9783030123840
eISBN9783030123857
ConferenceFICC 2019: Future of Information and Communication Conference
Conference locationSan Francisco, CA, USA
Dates