Establishing wireless conference calls under delay constraints

ABSTRACT

A prevailing feature of mobile telephony systems is that the cell where a mobile user is located may be unknown. Therefore when the system is to establish a call between users it may need to search, or page, all the cells that it suspects the users are located in, to find the cells where the users currently reside. The search consumes expensive wireless links and so it is desirable to develop search techniques that page as few cells as possible.We consider cellular systems with c cells and m mobile users roaming among the cells. The location of the users is uncertain as given by probability distribution vectors. Whenever the system needs to find specific users, it conducts a search operation lasting some number of rounds (the delay constraint). In each round the system may check an arbitrary subset of cells to see which users are located there. In this setting the problem of finding one user with minimum expected number of cells searched is known to be solved optimally in polynomial time.In this paper we address the problem of finding several users with the same optimization goal. This task is motivated by the problem of establishing a conference call between mobile users. We first show that the problem is NP-hard. Then we prove that a natural and simple heuristic is a e/e-1 approximation solution.

REFERENCES

• 1: Ahmed Abutaleb , Victor O.K. Li, Location update optimization in personal communication systems, Wireless Networks, v.3 n.3, p.205-216, 1997 [doi>10.1023/A:1019157217684 ]
• 2: Akyildiz, I.F., McNair, J., Ho, J.S.M., Uzunalioglu, H., Wang, W.: Mobility Management in Next Generation Wireless Systems. IEEE Proceedings Journal, Vol. 87(8) (1999) 1347-1385
• 3: Daniel O. Awduche , Arthur Gaylord , Aura Ganz, On resource discovery in distributed systems with mobile hosts, Proceedings of the 2nd annual international conference on Mobile computing and networking, p.50-55, November 1996, Rye, New York, United States [doi>10.1145/236387.236403]
• 4: Bar-Noy, A.: Quantum Directories --- a Search Engine for Mobile Users. A manuscript.
• 5: Amotz Bar-Noy , Ilan Kessler , Moshe Sidi, Mobile users: to update or not to update?, Wireless Networks, v.1 n.2, p.175-185, 1995 [doi>10.1007/BF01202540]
• 6: Bar-Noy, A., Kessler, I.: Tracking Mobile Users in Wireless Networks. IEEE Transactions on Information Theory, Vol. 39 (1993) 1877-1886
• 7: Bar-Noy, A., Malewicz, G.: Establishing Wireless Conference Calls. Manuscript, AT&T proprietary (2001)
• 8: Burkard, R.E., Cela, E., Pardalos, P.M., Pitsoulis L.S.: The Quadratic Assignment Problem. In Handbook of Combinatorial Optimization (D.-Z. Du and P.M. Pardalos, eds.), Vol. 2, Kluwer Academic Publishers (1998) 241-337
• 9: Du, D.-Z., Hwang, F.K.: Combinatorial Group Testing and Its Applications (2nd Edition). World Scientific, Series on Applied Mathematics Vol. 12 (1999)
• 10: EIA/TIA: Cellular radio-telecommunications intersystem operations. EIA/TIA Technical Report IS-41 Revision C (1995)
• 11: ETSI/TC: Mobile application part (MAP) specification, version 4.8.0. Technical Report, Recommendation GSM 09.02 (1994)
• 12: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 13: David Goodman , P. Krishnan , Binay Sugla, Minimizing queuing delays and number of messages in mobile phone location, Mobile Networks and Applications, v.1 n.1, p.39-48, Aug. 1996 [doi>10.1007/BF01342730]
• 14: Hardy, G.H., Littlewood, J.E., Pólya, G.: Inequalities. Cambridge University Press (1964)
• 15: Koopmans, T.C., Beckermann, M.J.: Assignment problems and the location of economic activities. Econometrica, Vol. 25 (1957) 53-76
• 16: Kostrikin, A.I., Manin, Yu.I.: Linear Algebra and Geometry. Gordon & Breach Science Pub (1989)
• 17: Liu, T., Bahl, P., Chlamtac, I.: Mobility Modeling, Location Tracking, and Trajectory Prediction in Wireless ATM Networks. IEEE Journal on Special Areas in Communications, Special Issue on Wireless Access Broadband Networks, Vol. 16(6) (1998) 922-936
• 18: Seshu Madhavapeddy , Kalyan Basu , Allison Roberts, Adaptive paging algorithms for cellular systems, Wireless information networks: architecture, resource management, and mobile data, Kluwer Academic Publishers, Norwell, MA, 1996
• 19: Christopher Rose , Roy Yates, Minimizing the average cost of paging under delay constraints, Wireless Networks, v.1 n.2, p.211-219, 1995 [doi>10.1007/BF01202543]
• 20: Stoer, J., Witzgall, Ch.: Convexity and Optimization in Finite Dimensions. Springer-Verlag (1970)
• 21: Stone, L.D.: Theory of Optimal Search. Academic Press, 1975

INDEX TERMS

Keywords:
NP-hardness, approximation algorithms, conference call, convex optimization, location management, terminal paging