The complexity of problems in wireless communication

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.