Cited By
View all- Shi LWang H(2017)The complexity of problems in wireless communicationTelecommunications Systems10.1007/s11235-016-0243-665:3(419-427)Online publication date: 1-Jul-2017
A mobility model for studying wireless communication and the complexity of problems in the model
Abstract
Wireless communication has become omnipresent in the world and enables users to have an unprecedented ability to communicate any time and any place. In this article, we propose a mobility model for studying wireless communication. The model incorporates elements such as users, access points, and obstacles so that it faithfully mimics the real environment. Interesting problems that have practical applications are posed and solved. More specifically, we study the complexity of three problems in a grid. The source reachability problem (SRP) models a situation in which we want to determine whether two access points can communicate at a certain time in a mobile environment. When users are involved in this situation, we call this problem the user communication problem (UCP). We show that SRP can be solved in O(max{d,t}m2) time, where d is the number of obstacles, t is the time bound in the statement of the problem, and m is the number of access points; we show that UCP can be solved in O(max{d,t}m4) time. The third problem called the user communication, limited source access problem (UCLSAP) studies a situation where we want to determine whether two users can communicate uninterruptedly during the duration of the model while considering battery-time limits of the access points. In contrast to the first two problems, we demonstrate that UCLSAP is intractable, unless P = NP. In conclusion, we briefly discuss the extension of our model to three dimensions and provide a list of open problems. © 2012 Wiley Periodicals, Inc. NETWORKS, 2012 © 2012 Wiley Periodicals, Inc.
References
[1]
S. Ahmed, G. C. Karmakara, and J. Kamruzzaman, An environment-aware mobility model for wireless ad hoc network, Comput Networks 54 (2010), 1470–1489.
[2]
A. S. Ahluwalia and E. H. Modiano, On the complexity and distributed construction of energy-efficient broadcast trees in wireless ad hoc networks, IEEE Trans Wireless Commun 4 (2005), 2136–2147.
[3]
M. Cagalj, J. P. Hubaux, and C. Enz, Minimum-energy broadcast in all-wireless networks: NP-completeness and distribution issues, International Conference on Mobile Computing and Networking, Proceedings of the 8th Annual International Conference on Mobile Computing and Networking, Atlanta, GA, September 23–28, 2002, pp. 172–182.
[4]
D. R. Choffnes and F. E. Bustamante, An integrated mobility and traffic model for vehicular wireless networks, International Conference on Mobile Computing and Networking, Proceedings of the 2nd ACM International Workshop on Vehicular Ad Hoc Networks, Cologne, Germany, September 2, 2005, pp. 69–78.
[5]
Y. Dong, W. K. Hon, D. K. Y. Yau, and J. C. Chin, Distance Reduction in Mobile Wireless Communication: Lower Bound Analysis and Practical Attainment, IEEE Trans Mobile Comput 8 (2009), 276–287.
[6]
P. Goransson and R. Greenlaw, Secure roaming in 802.11 networks, Elsevier Science and Technical Book Group, Newnes Press, Boston, 2007.
[7]
R. Greenlaw, H. James Hoover, and W. Larry Ruzzo, Limits to parallel computation: P -completeness theory, Oxford University Press, New York, 1995.
[8]
G.H. Hardy, Ramanujan: Twelve lectures on subjects suggested by his life and work, 3rd edition, New York, Chelsea, 1999, pp. 67.
[9]
D. Hilbert and S. Cohn-Vossen, Geometry and the imagination, Chelsea, New York, 1999, pp. 33–35.
[10]
A. Itai, C. H. Papadimitriou, and J. L. Szwarcfiter, Hamilton paths in grid graphs, SIAM J Comput 11 (1982), 676–686.
[11]
A. Jardosh, E. M. Belding-Royer, S. Barbara, K. C. Almeroth, S. Barbara, and S. Suri, Towards realistic mobility models for mobile ad hoc networks, International Conference on Mobile Computing and Networking, Proceedings of the 9th Annual International Conference on Mobile Computing and Networking, San Diego, CA, September 1419, 2003, pp. 217–229.
[12]
B. Krishnamachari, S. Wicker, R. Bjar, and C. Fernndez, On the complexity of distributed self-configuration in wireless networks, Telecommun Syst 22 (2003), 33–59.
[13]
T. Liu and P. Bahl, Mobility modeling, location tracking, and trajectory prediction in wireless ATM networks, IEEE J Select Areas Commun 16 (1998), 922–936.
[14]
M. K. Marina, S. R. Das, and A. P. Subramanian, A topology control approach for utilizing multiple channels in multi-radio wireless mesh networks, Comput Networks 54 (2010), 241–256.
[15]
A. B. McDonald and T. F. Znati, A mobility based framework for adaptive clustering in wireless ad-hoc networks, IEEE J Select Areas Commun 17 (1999), 1466–1486.
[16]
S. Meguerdichian, F. Koushanfar, M. Potkonjak, and M. B. Srivastava, Coverage Problems in Wireless Ad-Hoc Sensor Networks, IEEE Conf Comput Commun 3 (2001), 1380–1387.
[17]
S. Murthy and J. J. Garcia-Luna-Aceves, An efficient routing protocol for wireless networks, Mobile Networks Appl 1 (1996), 183–197.
[18]
F. G. Nocetti, J. S. Gonzalez, and I. Stojmenovic, Connectivity based k-hop clustering in wireless networks, Telecommun Syst 22 (2003), 205–220.
[19]
V. D. Park and M. S. Corson, A highly adaptive distributed routing algorithm for mobile wireless networks, Proceedings of the 16th Annual Joint Conference of the IEEE Computer and Communications Societies, Driving the Information Revolution, Kobe, Japan, April 712, 1997.
[20]
G. Pei, M. Gerla, X. Hong, and C. C. Chiang, Wireless hierarchical routing protocol with group mobility (WHIRL), Proc IEEE Wireless Commun Networking Conf 3 (1999), 1538–1542.
[21]
L. Ramachandran, M. Kapoor, A. Sarkar, and A. Aggarwal, Clustering algorithms for wireless ad hoc networks, Workshop on Discrete Algorithms and Methods for MOBILE Computing and Communications, Proceedings of the 4th International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications, Boston, MA, August 11, 2000, pp. 54–63.
[22]
A. D. Sarwate and A. G. Dimakis, The impact of mobility on gossip algorithms, IEEE Trans Inf Theory (in press).
[23]
S. D. Servetto and G. Barreneche, Constrained random walks on random graphs: Routing algorithms for large scale wireless sensor networks, Proceedings of the 1st ACM International Workshop on Wireless Sensor Networks and Applications, Atlanta, GA, September 28, 2002, pp. 12–21.
[24]
U. Varshney and R. Vetter, Emerging mobile and wireless networks, Commun ACM 43 (2000), 73–81.
[25]
Y. Wang, Topology control for wireless sensor networks, Signals and Communication Technology, Wireless Sensor Networks and Applications, Springer, New York, 2008, pp. 113–147.
[26]
G. Xing, T. Wang, W. Jia, and M. Li, Rendezvous design algorithms for wireless sensor networks with a mobile base station, International Symposium on Mobile Ad Hoc Networking & Computing Archive, Proceedings of the 9th ACM International Symposium on Mobile Ad Hoc Networking and Computing, Hong Kong, China, May 2630, 2008, pp. 231–240.
[27]
Y. Zhang, J. M. Nga, and C. P. Lowa, A distributed group mobility adaptive clustering algorithm for mobile ad hoc networks, Comput Commun 32 (2009), 189–202.
- A mobility model for studying wireless communication and the complexity of problems in the model
Recommendations
Mobility management across hybrid wireless networks: Trends and challenges
Future generation wireless networks are envisioned to be a combination of diverse but complementary access technologies. Internetworking these types of networks will provide mobile users with ubiquitous connectivity across a wide range of networking ...
Mobility management in wireless ATM networks
Mobile ATM offers a common wired network infrastructure to support mobility of wireless terminals, independent of the wireless access protocol. In addition, it allows seamless migration to future wireless broadband services, such as wireless ATM, by ...
Secure universal mobility for wireless internet
WMASH '04: Proceedings of the 2nd ACM international workshop on Wireless mobile applications and services on WLAN hotspotsThe advent of the mobile wireless Internet has created the need for seamless and secure communication over heterogeneous access networks such as IEEE 802.11, WCDMA, cdma2000, and GPRS. An enterprise user desires to be reachable while outside one's ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Publisher
Wiley-Interscience
United States
Publication History
Published: 01 May 2012
Author Tags
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 30 Dec 2024
Other Metrics
Citations
Cited By
View all- Shi LWang H(2017)The complexity of problems in wireless communicationTelecommunications Systems10.1007/s11235-016-0243-665:3(419-427)Online publication date: 1-Jul-2017