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 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 m 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 heuristic is an e/(e−1)-approximation solution.