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.\)
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Greenlaw, R., Kantabutra, S., & Longani, P. (2012). A mobility model for studying wireless communication and the complexity of problems in the model. Networks, 59(3), 320–330.
Čagalj, M., Hubaux, J. P., & Enz, C. (2002). Minimum-energy broadcast in all-wireless networks: NP-completeness and distribution issues. In Proceedings of the 8th annual international conference on mobile computing and networking (pp. 172–182). New York: ACM.
Taneja, S., & Kush, A. (2010). A survey of routing protocols in mobile ad hoc networks. International Journal of Innovation, Management and Technology, 1(3), 279.
Ahmed, S., Karmakar, G. C., & Kamruzzaman, J. (2010). An environment-aware mobility model for wireless ad hoc network. Computer Networks, 54(9), 1470–1489.
Zarifneshat, M., & Khadivi, P. (2013). Using mobile node speed changes for movement direction change prediction in a realistic category of mobility models. Journal of Network and Computer Applications, 36(3), 1078–1090.
Rhee, I., Shin, M., Hong, S., Lee, K., Kim, S. J., & Chong, S. (2011). On the Levy-walk nature of human mobility. IEEE/ACM Transactions on Networking, 19(3), 630–643.
Moscibroda, T., & Wattenhofer, R. (2006). The complexity of connectivity in wireless networks. In INFOCOM.
Andrews, M., & Dinitz, M. (2009). Maximizing capacity in arbitrary wireless networks in the SINR model: Complexity and game theory. In INFOCOM 2009 (pp. 1332–1340). Los Alamitos, CA: IEEE.
Meguerdichian, S., Koushanfar, F., Qu, G., & Potkonjak, M. (2001). Exposure in wireless ad-hoc sensor networks. In Proceedings of the 7th annual international conference on mobile computing and networking (pp. 139–150). New York: ACM.
Li, P., Guo, S., Hu, J., & Sarker, R. (2014). Lifetime optimization for reliable broadcast and multicast in wireless ad hoc networks. Wireless Communications and Mobile Computing, 14(2), 221–231.
Ren, S., Yi, P., Hong, D., Wu, Y., & Zhu, T. (2014). Distributed construction of connected dominating sets optimized by minimum-weight spanning tree in wireless ad-hoc sensor networks. In 2014 IEEE 17th international conference on computational science and engineering (CSE) (pp. 901–908).
Ramachandran, L., Kapoor, M., Sarkar, A., & Aggarwal, A. (2000). Clustering algorithms for wireless ad hoc networks. In Proceedings of the 4th international workshop on discrete algorithms and methods for mobile computing and communications (pp. 54–63). New York: ACM.
Dong, Y., Hon, W. K., Yau, D. K. Y., & Chin, J. C. (2009). Distance reduction in mobile wireless communication: Lower bound analysis and practical attainment. IEEE Transactions on Mobile Computing, 8(2), 276–287.
Cerulli, R., Gentili, M., & Raiconi, A. (2014). Maximizing lifetime and handling reliability in wireless sensor networks. Networks, 64(4), 321–338.
Ao, W. C., Cheng, S. M., & Chen, K. C. (2012). Connectivity of multiple cooperative cognitive radio ad hoc networks. IEEE Journal on Selected Areas in Communications, 30(2), 263–270.
Khabbazian, M., Durocher, S., Haghnegahdar, A., & Kuhn, F. (2015). Bounding interference in wireless ad hoc networks with nodes in random position. IEEE/ACM Transactions on Networking, 23(4), 1078–1091.
Rosati, S., Krużelecki, K., & Traynard, L. (2013). Speed-aware routing for UAV ad-hoc networks. In 2013 IEEE Globecom workshops (GC Wkshps) (pp. 1367–1373).
Rosati, S., Krużelecki, K., Heitz, G., Floreano, D., & Rimoldi, B. (2016). Dynamic routing for flying ad hoc networks. IEEE Transactions on Vehicular Technology, 65(3), 1690–1700.
Clausen, T., & Jacquet, P. (2003). Optimized link state routing protocol (OLSR) (No. RFC 3626).
Clausen, T., Dearlove, C., Jacquet, P., & Herberg, U. (2014). The optimized link state routing protocol version 2 (No. RFC 7181).
Dinits, E. A. (1970). Algorithm of solution to problem of maximum flow in network with power estimates. Doklady Akademii Nauk SSSR, 194(4), 754.
Korte, B., & Vygen, J. (2012). Combinatorial optimization: Theory and algorithms. Berlin: Springer.
Acknowledgments
The Project 91338102 is supported by National Natural Science Foundation of China.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Shi, L., Wang, H. The complexity of problems in wireless communication. Telecommun Syst 65, 419–427 (2017). https://doi.org/10.1007/s11235-016-0243-6
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11235-016-0243-6