Optimization of a database hierarchy for mobility tracking in a personal communications network

The concept of personal communications is based on the ability of mobile users to maintain communication with a wireline network (such as the public switched telephone network) by means of a wireless link. Each user has a unique name (or personal number), and calls are routed to a person rather than to a stationary telephone. In order to set up such a call, the wireline network has to determine the current location of the user and route the call accordingly. Keeping track of a mobile user requires updates at databases within the network, and call routing requires accesses at these databases. In order to reduce the update and access load on each database, a message routing scheme based on a hierarchy of databases is proposed. We consider the problem of how to assign databases in this hierarchy so as to minimize the total rate at which accesses and updates occur, given estimates of mobility and calling rates between cells, and subject to a constraint on the access and update rates for each database. We show that an optimal hierarchy can be computed using a dynamic programming algorithm.