Tracking mobile users in wireless communications networks

Abstract

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 works 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 lastly reported. We first show that for an arbitrary topology of the cellular network (represented by the interference 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 interference graph. In particular, we present an optimal solution for ring graphs and a near optimal solution for grid graphs, when the cost of being a reporting center is the same for all vertices. When different vertices may have different such costs, we present an optimal solution for tree graphs and a simple approximation algorithm for arbitrary graphs.