The complexity of problems in wireless communication

Lingsheng Shi () and Huandong Wang ()
Additional contact information
Lingsheng Shi: Tsinghua University
Huandong Wang: Tsinghua University

Telecommunication Systems: Modelling, Analysis, Design and Management, 2017, vol. 65, issue 3, No 7, 419-427

Abstract: Abstract Ad hoc networks become increasingly important in our life, for their advantages without relying on existing infrastructures and for their ability to be fast implemented, especially in the aspects of rescue after disasters and military. However, since every node in an ad hoc network can move freely, we are confronted with many new problems when compared with cellular networks and WiFi, such as the change of connectivity between nodes and signal interference and blockage by obstacles. Thus, it is important to understand solutions and complexities of various programming problems in ad hoc networks. In this paper, based on an existing mobility model for ad hoc networks, we study solutions and complexities of a series of problems proposed by Greenlaw, Kantabutra, and Longani, including the multiusers simultaneous communication problem (MUSCP), the longer communication problem (LCP), the obstacle removal problem (ORP) and the user communication, limited number of sources problem (UCLNSP). For MUSCP and LCP, we provide efficient algorithms to solve them and prove that they are P problems. On the other hand, for ORP and UCLNSP, by applying reduction from the set covering decision problem, we prove that they are NP-complete, and thus, they are intractable, unless $$P=NP.$$ P = N P .

Keywords: Ad hoc network; Algorithm; Complexity; Wireless mobile communication (search for similar items in EconPapers)
Date: 2017
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s11235-016-0243-6 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:telsys:v:65:y:2017:i:3:d:10.1007_s11235-016-0243-6

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/11235

DOI: 10.1007/s11235-016-0243-6

Access Statistics for this article

Telecommunication Systems: Modelling, Analysis, Design and Management is currently edited by Muhammad Khan

More articles in Telecommunication Systems: Modelling, Analysis, Design and Management from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().