Skip to main content
SpringerLink
Log in

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

  • Conference paper
  • First Online:
Book cover Advances in Information and Communication (FICC 2019)

Part of the book series: Lecture Notes in Networks and Systems ((LNNS,volume 70))

Included in the following conference series:

  • 1501 Accesses

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.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution
Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 169.00
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 219.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

References

  1. Franceschetti, M., Dousse, O., David, N., Thiran, P.: Closing the gap in the capacity of wireless networks via percolation theory. IEEE Trans. Inf. Theory 53(3), 1009–1018 (2007)

    Article  MathSciNet  Google Scholar 

  2. Gupta, P., Kumar, P.R.: The capacity of wireless networks. IEEE Trans. Inf. theory 46(2), 388–404 (2000)

    Article  MathSciNet  Google Scholar 

  3. Hou, Y., Li, M., Zeng, K.: Throughput optimization in multi-hop wireless networks with reconfigurable antennas. In: 2017 International Conference on Computing, Networking and Communications (ICNC), pp. 620–626. IEEE (2017)

    Google Scholar 

  4. Hu, C., Wang, X., Yang, Z., Zhang, J., Xu, Y., Gao, X.: A geometry study on the capacity of wireless networks via percolation. IEEE Trans. Commun. 58(10), 2916–2925 (2010)

    Article  Google Scholar 

  5. Jain, K., Padhye, J., Padmanabhan, V.N., Qiu, L.: Impact of interference on multi-hop wireless network performance. Wirel. Netw. 11(4), 471–487 (2005)

    Article  Google Scholar 

  6. Keshavarz-Haddad, A., Ribeiro, V., Riedi, R.: Broadcast capacity in multihop wireless networks. In: Proceedings of the 12th Annual International Conference on Mobile Computing and Networking, pp. 239–250. ACM (2006)

    Google Scholar 

  7. Kodialam, M., Nandagopal, T.: Characterizing achievable rates in multi-hop wireless networks: the joint routing and scheduling problem. In: Proceedings of the 9th Annual International Conference on Mobile Computing and Networking, pp. 42–54. ACM (2003)

    Google Scholar 

  8. Kumar, V., Marathe, M.V., Parthasarathy, S., Srinivasan, A.: Algorithmic aspects of capacity in wireless networks. In: ACM SIGMETRICS Performance Evaluation Review, vol. 33, pp. 133–144. ACM (2005)

    Google Scholar 

  9. Li, X.Y.: Multicast capacity of wireless ad hoc networks. IEEE/ACM Trans. Networking (TON) 17(3), 950–961 (2009)

    Article  Google Scholar 

  10. Li, X.Y., Zhao, J., Wu, Y.W., Tang, S.J., Xu, X.H., Mao, X.F.: Broadcast capacity for wireless ad hoc networks. In: 5th IEEE International Conference on Mobile Ad Hoc and Sensor Systems, 2008. MASS 2008, pp. 114–123. IEEE (2008)

    Google Scholar 

  11. Lu, N., Shen, X.S.: Scaling laws for throughput capacity and delay in wireless networks—a survey. IEEE Commun. Surv. Tutorials 16(2), 642–657 (2014)

    Article  Google Scholar 

  12. Peraki, C., Servetto, S.D.: On the maximum stable throughput problem in random networks with directional antennas. In: Proceedings of the 4th ACM International Symposium on Mobile Ad Hoc Networking & Computing, pp. 76–87. ACM (2003)

    Google Scholar 

  13. Sadjadpour, H.R., Wang, Z., et al.: The capacity of wireless ad hoc networks with multi-packet reception. IEEE Trans. Commun. 58(2) (2010)

    Article  Google Scholar 

  14. Shakkottai, S., Liu, X., Srikant, R.: The multicast capacity of large multihop wireless networks. IEEE/ACM Trans. Networking (TON) 18(6), 1691–1700 (2010)

    Article  Google Scholar 

  15. Wan, P.J., Frieder, O., Jia, X., Yao, F., Xu, X., Tang, S.: Wireless Link Scheduling Under Physical Interference Model. IEEE (2011)

    Google Scholar 

  16. Wang, Z., Sadjadpour, H., Garcia-Luna-Aceves, J.J.: The capacity and energy efficiency of wireless ad hoc networks with multi-packet reception. In: Proceedings of the 9th ACM International Symposium on Mobile Ad Hoc Networking and Computing, pp. 179–188. ACM (2008)

    Google Scholar 

  17. Yi, S., Pei, Y., Kalyanaraman, S.: On the capacity improvement of ad hoc wireless networks using directional antennas. In: Proceedings of the 4th ACM International Symposium on Mobile Ad Hoc Networking & Computing, pp. 108–116. ACM (2003)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computing Science and Mathematics, University of Stirling, Stirling, UK

    Maher Heal & Jingpeng Li

Authors
  1. Maher Heal
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Jingpeng Li
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Maher Heal .

Editor information

Editors and Affiliations

  1. Faculty of Science and Engineering, Saga University, Saga, Japan

    Kohei Arai

  2. The Science and Information (SAI) Organization, Bradford, UK

    Rahul Bhatia

Rights and permissions

Reprints and permissions

Copyright information

© 2020 Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

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, vol 70. Springer, Cham. https://doi.org/10.1007/978-3-030-12385-7_44

Download citation

Publish with us

Policies and ethics

Search

Navigation