JCSE, vol. 4, no. 2, pp.173-187, 2010

DOI:

Three Effective Top-Down Clustering Algorithms for Location Database Systems

Kwang-Jo Lee, Sung-Bong Yang
Department of Computer Science, Yonsei University, Korea

Abstract: Recent technological advances in mobile communication systems have made explosive growth inthe number of mobile device users worldwide. One of the most important issues in designing amobile computing system is location management of users. The hierarchical systems had beenproposed to solve the scalability problem in location management. The scalability problemoccurs when there are too many users for a mobile system to handle, as the system is likely toreact slow or even get down due to late updates of the location databases. In this paper, wepropose a top-down clustering algorithm for hierarchical location database systems in a wirelessnetwork. A hierarchical location database system employs a tree structure. The proposedalgorithm uses a top-down approach and utilizes the number of visits to each cell made by theusers along with the movement information between a pair of adjacent cells. We then presenta modified algorithm by incorporating the exhaustive method when there remain a few levelsof the tree to be processed. We also propose a capacity constraint top-down clustering algorithmfor more realistic environments where a database has a capacity limit. By the capacity of adatabase we mean the maximum number of mobile device users in the cells that can be handledby the database. This algorithm reduces a number of databases used for the system andimproves the update performance. The experimental results show that the proposed, top-down,modified top-down, and capacity constraint top-down clustering algorithms reduce the updatecost by 17.0%, 18.0%, 24.1%, the update time by about 43.0%, 39.0%, 42.3%, respectively. Thecapacity constraint algorithm reduces the average number of databases used for the system by23.9% over other algorithms.

Keyword: No keyword

Full Paper:   136 Downloads, 3986 View