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

• 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
• ISSN: 1022-0038; 1572-8196
• DOI: 10.1023/A:1019193615693

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]