Amotz Bar-Noy
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.
- Abutaleb, A., Li, V.O.K.: Location update optimization in personal communication systems. Wireless Networks, Vol. 3(3) (1997) 205-216 Google Scholar
Digital Library
- 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-1385Google ScholarCross Ref
- Awduche, D.O., Gaylord, A., Ganz, A.: On Resource Discovery in Distributed Systems with Mobile Hosts. MOBICOM'96 (1996) Google ScholarDigital Library
- Bar-Noy, A.: Quantum Directories --- a Search Engine for Mobile Users. A manuscript.Google Scholar
- Bar-Noy, A., Kessler, I., Sidi, M.: Mobile Users: To Update or not to Update? Wireless Networks journal, Vol. 1 (1995) 175186 Google ScholarDigital Library
- Bar-Noy, A., Kessler, I.: Tracking Mobile Users in Wireless Networks. IEEE Transactions on Information Theory, Vol. 39 (1993) 1877-1886Google ScholarDigital Library
- Bar-Noy, A., Malewicz, G.: Establishing Wireless Conference Calls. Manuscript, AT&T proprietary (2001)Google Scholar
- 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-337Google Scholar
- Du, D.-Z., Hwang, F.K.: Combinatorial Group Testing and Its Applications (2nd Edition). World Scientific, Series on Applied Mathematics Vol. 12 (1999)Google Scholar
- EIA/TIA: Cellular radio-telecommunications intersystem operations. EIA/TIA Technical Report IS-41 Revision C (1995)Google Scholar
- ETSI/TC: Mobile application part (MAP) specification, version 4.8.0. Technical Report, Recommendation GSM 09.02 (1994)Google Scholar
- Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman and Company, New York (1979) Google ScholarDigital Library
- Goodman, D., Krishnan, P., Sugla., B.: Minimizing Queuing Delays and Number of Messages in Mobile Phone Location. ACM/Baltzer J. on Mobile Networks and Applications, Vol. 1(1) (1996) 39-48 Google ScholarDigital Library
- Hardy, G.H., Littlewood, J.E., Pólya, G.: Inequalities. Cambridge University Press (1964)Google Scholar
- Koopmans, T.C., Beckermann, M.J.: Assignment problems and the location of economic activities. Econometrica, Vol. 25 (1957) 53-76Google ScholarCross Ref
- Kostrikin, A.I., Manin, Yu.I.: Linear Algebra and Geometry. Gordon & Breach Science Pub (1989)Google Scholar
- 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 Google ScholarDigital Library
- Madhavapeddy, S., Basu, K., Roberts, A.: Adaptive Paging Algorithms for Cellular Systems. Wireless Information Networks: Architecture, Resource Management and Mobile Data (1996) 83-101 Google ScholarDigital Library
- Rose, C., Yates, R.: Minimizing The Average Cost of Paging Under Delay Constraints. ACM Journal of Wireless Networks, Vol. 1(2) (1995) 211-219 Google ScholarDigital Library
- Stoer, J., Witzgall, Ch.: Convexity and Optimization in Finite Dimensions. Springer-Verlag (1970)Google Scholar
- Stone, L.D.: Theory of Optimal Search. Academic Press, 1975Google Scholar
- Establishing wireless conference calls under delay constraints
Recommendations
Establishing wireless conference calls under delay constraints
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 ...
A PTAS for delay minimization in establishing wireless conference calls
A prevailing feature of mobile telephony systems is that the location of a mobile user may be unknown. Therefore, when the system has to establish a call between users, it may need to search (or page) all the cells that it suspects the users may be ...
A PTAS for delay minimization in establishing wireless conference calls
WAOA'04: Proceedings of the Second international conference on Approximation and Online AlgorithmsA prevailing feature of mobile telephony systems is that the location of a mobile user 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 may be ...
Comments