NDLI: Paging Mobile Users Efficiently and Optimally

Content Provider	IEEE Xplore Digital Library
Author	Bar-Noy, A. Yi Feng Golin, M.J.
Copyright Year	2007
Description	Author affiliation: Brooklyn Coll., Brooklyn (Bar-Noy, A.)
Abstract	A mobile user is roaming in a zone composed of N cells in a cellular network system. When a call to the mobile user arrives, the system pages the mobile user in these cells since it never reports its location unless it leaves the zone. The N cells are associated with a probability vector $(p_{1},$ $...,p_{N})$ where $p_{i}$ is the probability that the mobile user resides in the ith cell and all the probabilities are independent. A delay constraint paging strategy must find the mobile user within D (1 les D les N) paging rounds; in each round a subset of the N cells is paged. The goal is to minimize the expected number of paged cells until the mobile user is found. Solutions based on dynamic programming that yield optimal strategies are known. The running time of the known implementations is $Theta(N^{2}D).$ Our first contribution is to improve the running time to Theta(ND) by proving that the dynamic programming recursive formulation satisfies the Monge property, permitting us to use various dynamic programming speedup techniques. A Theta(N) heuristic solution is also known. Our second contribution is a heuristic whose running time is Theta(N log D). Our heuristic outperforms the known heuristic while running faster for D << N. We compare the non-optimal heuristics with the optimal solution demonstrating the tradeoff between optimality and running time efficiency of various solutions.
Starting Page	1910
Ending Page	1918
File Size	230085
Page Count	9
File Format	PDF
ISBN	1424410479
ISSN	0743166X
DOI	10.1109/INFCOM.2007.222
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2007-05-06
Publisher Place	Spain
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Paging strategies Bandwidth Dynamic programming Mobile computing Computer science Land mobile radio cellular systems Delay Roaming Communications Society Computer networks
Content Type	Text
Resource Type	Article
Subject	Computer Science Electrical and Electronic Engineering

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in