On properties of read and write sets in the Awerbuch-Peleg scheme for tracking mobile users

An important issue in the design of a wireless network is the scheme used for tracking the locations of its mobile users. A formal scheme for efficient location tracking proposed by Awerbuch and Peleg uses a locality-preserving distributed directory server whose construction is based on the graph-th...

Full description

Saved in:
Bibliographic Details
Published in:Wireless networks 2000-07, Vol.6 (3), p.235-247
Main Authors: Weerakoon, Ishan P, Wijesinha, Alexander L, Sidhu, Deepinder P
Format: Article
Language:English
Subjects:
Communication
Communications networks
Costs
Design
Directories
Mobile communications networks
Performance evaluation
Studies
Tracking
User profiles
Wireless networks
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:An important issue in the design of a wireless network is the scheme used for tracking the locations of its mobile users. A formal scheme for efficient location tracking proposed by Awerbuch and Peleg uses a locality-preserving distributed directory server whose construction is based on the graph-theoretic notion of a regional matching. Although this scheme has been theoretically shown to have low worst-case communication complexity, its implementation behavior is not known. We have implemented the Awerbuch-Peleg scheme in order to evaluate its performance and practicality. This paper, which stems from our implementation, examines properties of the read and write sets that are a key component of the hierarchical directories used in the scheme. We are particularly interested in read set size since it directly influences the scheme's communication cost and performance. Our experimental results indicate that read set sizes in randomly-generated networks are much smaller than the theoretical bound. We derive some analytical results that help explain this behavior. In particular, we establish tight constant bounds for read set size in linear, grid and uniform degree balanced tree networks that are independent of the number of network nodes. [PUBLICATION ABSTRACT]
ISSN:1022-0038
1572-8196
DOI:10.1023/A:1019193615693