05-05-2011, 10:05 AM
Abstract
The problem of searching for mobile users in cellular networks is addressed in this study. Previous studies addressing thisissue have focused on the problem of searching for a single user. The underlying assumption for this approach is that somestraightforward strategy of searching for multiple users can be easily derived from a single user search strategy. Unfortunately, thisassumption is violated very often in practice, and a direct extension of an optimal single-user (OSU) search scheme to multiple usersoften fails due to the inherent correlation and dependence among the movements of the mobile users. As shown in this study, theproblem of maximizing the expected rate of successful searches under delay and bandwidth constraints is NP-hard. When thepotential locations of different users overlap, the derivation of an optimal concurrent search for many independent users from a set ofOSU searches is NP-hard. Unfortunately, very often, the potential locations of different users overlap. In reality, a cellular network hasto serve many competing search requests sharing a limited bandwidth. Since the problem of maximizing the expected rate ofsuccessful searches under delay and bandwidth constraints is NP-hard, this study proposes a heuristic algorithm that is optimal formost probable cases, and its worst case runtime complexity is Oðnðlog n þ C logCÞÞ, where n is the number of mobile users that mustbe found, and C is the number of their potential locations. The approximation ratio of the proposed search algorithm is less than 2. Thatis, the expected number of searches is always less than twice the number of searches expected from an optimal search algorithm.Even under the worst case condition, the proposed method can potentially increase the expected rate of successful searches by100 percent in comparison to the existing search strategy currently used by cellular networks. Moreover, the proposed search strategyoutperforms a greedy search strategy that considers only the users’ location probabilities and ignores their deadline constraints.Under certain conditions, the expected rate of successful searches generated by the proposed method is twice the equivalent rategenerated by the greedy search strategy. In addition, the proposed search strategy outperforms a heuristic algorithm that searchesaround the user last known location.Index Terms—Location management, paging, mobile, multiple search, cellular networks.
INTRODUCTION
THE cellular communication technology has rapidlyexpanded during the last decade. Since 2003, thenumber of global mobile subscribers has exceeded thenumber of wired subscribers, and there are already morethan 1.4 billion mobile users all over the world. In wirednetworks, the users’ locations are fixed, while in cellularnetworks, a user can potentially be located anywhere withinthe system coverage area. Whenever there is a need to routean incoming call to a mobile user, the system has to find theexact location of this user in order to set up the call. Hence,at any given moment, a cellular network has to find manyindependent mobile users in order to route incoming callsto these users. The search for a single user is also known aspaging. The search for each mobile user is conducted underthe condition that the time duration from the arrival of thepage request until the search is over is bounded from aboveby a predefined constant, known as the search delaydeadline. Due to the limited network resources availablefor searching, the search for each user must be efficient yetfast in order to satisfy both bandwidth and delayconstraints. As the number of mobile users keeps growing,the rate of search requests handled by a cellular network increases very rapidly. It is expected that future cellularnetworks will have to face a growing number of searchrequests for mobile users and will have to utilize thewireless links associated with the search task moreefficiently.
1.1 Background and Related Work
The issue of tracking mobile users has been addressed bymany studies several ofwhich consider the problem of searching for a mobile user.However, the focus in these studies is on the problem ofsearching for a single user. This approach ignores a keyissue in the task of searching for mobile users: the allocationof a limited amount of network resources among manycompeting search requests. In [16], it was shown that whenthere is no search delay constraint, a sequential search for amobile user u in a nonincreasing order of the probability offinding u minimizes the expected number of locations thatmust be searched. Given a search delay deadline D and thesteady-state location distribution of a particular user u, adynamic programming method can be used to minimize theexpected number of searches for u [13], [16]. The first steptoward searching for many users was suggested in [18].However, the problem considered in this study is still theproblem of searching for a single user under the conditionthat at any given moment, there is a need to find manyusers. This approach ignores the main problem of searchingfor many users under bandwidth and delay constraints: thenetwork must select which user to search first at whichlocation. It was clearly demonstrated in [18] that underdifferent load conditions,
Download full report
http://ieeexplore.ieeeiel5/7755/4358975/...er=4453828
The problem of searching for mobile users in cellular networks is addressed in this study. Previous studies addressing thisissue have focused on the problem of searching for a single user. The underlying assumption for this approach is that somestraightforward strategy of searching for multiple users can be easily derived from a single user search strategy. Unfortunately, thisassumption is violated very often in practice, and a direct extension of an optimal single-user (OSU) search scheme to multiple usersoften fails due to the inherent correlation and dependence among the movements of the mobile users. As shown in this study, theproblem of maximizing the expected rate of successful searches under delay and bandwidth constraints is NP-hard. When thepotential locations of different users overlap, the derivation of an optimal concurrent search for many independent users from a set ofOSU searches is NP-hard. Unfortunately, very often, the potential locations of different users overlap. In reality, a cellular network hasto serve many competing search requests sharing a limited bandwidth. Since the problem of maximizing the expected rate ofsuccessful searches under delay and bandwidth constraints is NP-hard, this study proposes a heuristic algorithm that is optimal formost probable cases, and its worst case runtime complexity is Oðnðlog n þ C logCÞÞ, where n is the number of mobile users that mustbe found, and C is the number of their potential locations. The approximation ratio of the proposed search algorithm is less than 2. Thatis, the expected number of searches is always less than twice the number of searches expected from an optimal search algorithm.Even under the worst case condition, the proposed method can potentially increase the expected rate of successful searches by100 percent in comparison to the existing search strategy currently used by cellular networks. Moreover, the proposed search strategyoutperforms a greedy search strategy that considers only the users’ location probabilities and ignores their deadline constraints.Under certain conditions, the expected rate of successful searches generated by the proposed method is twice the equivalent rategenerated by the greedy search strategy. In addition, the proposed search strategy outperforms a heuristic algorithm that searchesaround the user last known location.Index Terms—Location management, paging, mobile, multiple search, cellular networks.
INTRODUCTION
THE cellular communication technology has rapidlyexpanded during the last decade. Since 2003, thenumber of global mobile subscribers has exceeded thenumber of wired subscribers, and there are already morethan 1.4 billion mobile users all over the world. In wirednetworks, the users’ locations are fixed, while in cellularnetworks, a user can potentially be located anywhere withinthe system coverage area. Whenever there is a need to routean incoming call to a mobile user, the system has to find theexact location of this user in order to set up the call. Hence,at any given moment, a cellular network has to find manyindependent mobile users in order to route incoming callsto these users. The search for a single user is also known aspaging. The search for each mobile user is conducted underthe condition that the time duration from the arrival of thepage request until the search is over is bounded from aboveby a predefined constant, known as the search delaydeadline. Due to the limited network resources availablefor searching, the search for each user must be efficient yetfast in order to satisfy both bandwidth and delayconstraints. As the number of mobile users keeps growing,the rate of search requests handled by a cellular network increases very rapidly. It is expected that future cellularnetworks will have to face a growing number of searchrequests for mobile users and will have to utilize thewireless links associated with the search task moreefficiently.
1.1 Background and Related Work
The issue of tracking mobile users has been addressed bymany studies several ofwhich consider the problem of searching for a mobile user.However, the focus in these studies is on the problem ofsearching for a single user. This approach ignores a keyissue in the task of searching for mobile users: the allocationof a limited amount of network resources among manycompeting search requests. In [16], it was shown that whenthere is no search delay constraint, a sequential search for amobile user u in a nonincreasing order of the probability offinding u minimizes the expected number of locations thatmust be searched. Given a search delay deadline D and thesteady-state location distribution of a particular user u, adynamic programming method can be used to minimize theexpected number of searches for u [13], [16]. The first steptoward searching for many users was suggested in [18].However, the problem considered in this study is still theproblem of searching for a single user under the conditionthat at any given moment, there is a need to find manyusers. This approach ignores the main problem of searchingfor many users under bandwidth and delay constraints: thenetwork must select which user to search first at whichlocation. It was clearly demonstrated in [18] that underdifferent load conditions,
Download full report
http://ieeexplore.ieeeiel5/7755/4358975/...er=4453828