الگوریتم به حداقل رساندن هزینه برای ردیابی موقعیت سریع در شبکه های بی سیم تلفن همراه

Location tracking is one of the most important issues in providing real-time applications over wireless networks due to its effect to quality of service (QoS), such as end-to-end delay, bandwidth utilization, and connection dropping probability. In this paper, we study cost minimization for locating mobile users under delay constraints in mobile wireless networks. Specifically, a new location tracking algorithm is developed to determine the position of mobile terminals under delay constraints, while minimizing the average locating cost based on a unimodal property. We demonstrate that the new algorithm not only results in minimum locating cost, but also has a lower computational complexity compared to existing algorithms. Furthermore, detailed searching procedures are discussed under both deterministic and statistic delay bounds. Numerical results for a variety of location probability distributions show that our algorithm compares favorably with existing algorithms.

The increasing demand for diverse mobile applications using public wireless networks has imposed many challenging issues because of the variations in mobile users’ positions from time to time [14]. In order to deliver services in wireless networks, fast location tracking is critical to offering real-time mobile services, such as voice over IP. In cellular wireless networks, location update and paging are two fundamental operations for locating a mobile terminal (MT). According to the latest specification on third generation wireless communication systems such as universal mobile telecommunication system (UMTS) [1], [9] and [23], location update depends on the design of location areas (LAs) and routing areas (RAs). Each LA consists of a group of cells, and mobile terminals send location update requests when they cross the boundary of two LAs. The RA is designed for packet switching domain, and each RA can be a subset of the location area. In other words, mobile terminals update their location information with the system based on location management mechanisms. On the opposite, paging is a process to locate MTs, which is performed by the system instead of end users [16] and [19]. The main challenge in locating MTs is to reduce the signaling cost under delay constraints. Therefore, the minimization of cost and delay caused by locating mobile objects has been studied extensively by researchers [2], [7], [11], [15], [16], [17], [20] and [24]. In future wireless networks, many applications of multimedia services have various quality of service (QoS) requirements, including delay, transmission rate, pricing models and so on. Among these parameters, delay is one of the most important metrics because it is directly related to the perceived QoS and is used to differentiate real-time and non-real-time applications. Therefore, traditional broadcast paging scheme used for telephony systems, in which polling messages are sent to every cell in the LA, is not appropriate for dual services in circuit-switched and packet-switched domains. Under this broadcast paging scheme, the paging delay is minimized since there is only one polling cycle required to find the called MT and all cells within the LA receive the paging request simultaneously, where a polling cycle is the round trip time from when a paging message is sent until the response is received. However, the cost of this paging scheme is high and the utilization of bandwidth is low since all cells in the LA are searched, which consumes a large amount of down-link radio resources for high mobility users. As the demand for wireless services such as emails, transactions, and web-browse grows rapidly, the signaling traffic caused by location tracking increases accordingly, which consumes limited available radio resources. To improve the efficiency of bandwidth utilization, we explore the optimization of location tracking cost under delay constraints, based on a time-varying probability distribution of user location [5], [13], [15] and [22]. The probability distribution of user location depends on many factors such as mobility model, calling pattern, and so on. Many tracking schemes are designed to predict cell location probabilities and to estimate the next location of a MT accurately [2], [3], [6], [8], [10] and [18]. In this paper, we focus on optimal partitioning of searching areas. The minimization of location tracking cost with delay constraints induces two fundamental problems: 1. Given the probability distribution and a deterministic delay bound, what is the minimum cost required to locate the target object? If there is such an optimal solution, how to design paging areas and how to proceed the searching procedure? What is the computation complexity for finding an optimal solution? 2. Given the probability distribution and a statistic delay constraint, what is the minimum cost required to locate the moving terminal? How can the statistic delay constraint be satisfied? These two problems are challenging because they require the optimal solution to achieve minimum cost under delay constraints, whereas the computation complexity must be taken into account. Previous efforts have addressed these problems to some extent. For example, in [4], [12] and [16], it is demonstrated that the minimum cost can be obtained if all cells are searched in a decreasing order of location probabilities in the absence of delay constraints. Similar results also show that the minimum cost can be achieved through dynamic programming. Since the number of ways to partition an N cell location area into DD paging areas is exponential in N, searching through all possible partitions is an unrealistic approach to finding a cost-minimum scheme. In [20], it is proved that three necessary conditions are required to achieve minimum cost given a deterministic delay bound, thus, reducing the computation complexity. It is required that all cells must be searched in a non-increasing order of their location probabilities. This important property makes it sufficient to search only O(ND-1)O(ND-1) partitions. Since it takes O(N) time to compute the paging cost corresponding to a given partition, the necessary condition of [20] immediately implies an O(ND)O(ND) time algorithm for computing an optimal paging scheme under delay bound DD. In this paper, we prove a unimodal property of two-step locating cost as a function of the corresponding 2-partition of the location area. This unimodal property enables us to find an optimal 2-partition in O(logN)O(logN) time, given O(NlogN)O(NlogN) preprocessing time. As a result, we have an O(NlogN+ND-2logN)O(NlogN+ND-2logN) time algorithm for computing a cost-minimum location tracking under delay constraint DD. Moreover, we investigate the cost minimization issue under statistic delay constraints. Based on the optimal algorithm developed for deterministic delay bound, we tackle this problem through a sequential matching algorithm. Considering multiple locating algorithms may cause failure in the searching process, we also analyze locating failure which is affected by the proposed algorithm. Throughout the paper, the proposed algorithms and procedure are illustrated in the context of cellular networks. However, they are applicable to other mobile communication systems as well. For example, a hot-spot system such as a wireless local area network (WLAN) may need to locate a laptop which sends requests of services so as to deliver data or video to this terminal. Meanwhile, the locating algorithm can be used to assist storing information in those proxy servers which are close to the requesting terminals. Especially, if mobile users change their positions after they send a web-browsing or message request, locating these terminals is mandatory, but the delay constraints are flexible for non-real-time applications. The rest of the paper is organized as follows. In Section 2, we formulate the problem of location tracking and discuss necessary conditions for cost minimization. In Section 3, we prove a unimodal property of two-step searching and use that property to design a fast cost-minimization algorithm subject to deterministic delay bounds. In Section 4, we present location tracking procedure under statistic delay bounds. We evaluate the performance of the proposed algorithm in terms of locating cost, delay, computation complexity, and searching failure in Section 5. We present numerical results over various location probability distributions in Section 6 and conclude the paper in Section 7.

We have presented a new algorithm for cost-minimization location tracking in mobile wireless networks. Based on a unimodal property of two-step locating cost as a function of the corresponding 2-partition of the location area, the new algorithm reduces the computation complexity significantly while achieving an optimal partition. In addition to the investigation of minimum cost searching problem under deterministic delay bound, we also addressed the searching problem under statistic delay constraints by using a sequential matching algorithm. Our simulation results show that the proposed algorithms are applicable to different location probability distributions. This is an important merit because uniform or Gaussian distributions of location probabilities are not present in real systems. As a matter of fact, these probabilities change over time and are irregularly distributed. By combining with location estimation algorithms, the proposed algorithms can easily be implemented in wireless systems.