Tracking Mobile Users in Wireless Communications Networks

Tracking strategies for mobile wireless networks are studied. We assume a cellular architecture where base stations that are interconnected by a wired network communicate with mobile units via wireless links. Previous work focused on the cost of utilizing the wired links for management of directories. In this paper, the issue considered is the cost of utilizing the wireless links for the actual tracking of mobile users. We propose a novel tracking strategy in which a subset of all base stations is selected and designated as reporting centers. Mobile users transmit update messages only upon entering cells of reporting centers, while every search for a mobile user is restricted to the vicinity of the reporting center to which the user last reported. We show that for an arbitrary topology of the cellular network (represented by the mobility graph), finding an optimal set of reporting centers is an NP-complete problem. We then present optimal and near optimal solutions for important special cases of the mobility graph. For the case in which the cost of being a reporting center is the same for all vertices, we present an optimal solution for ring graphs and near optimal solutions for various types of grid graphs (one of which corresponds to the common topology of hexagonal cells). For the case in which different vertices may have different costs, we present an optimal solution for tree graphs and a simple approximation algorithm for arbitrary graphs. © 1993 IEEE