The proliferation of wireless networks has led to a demand for providing bandwidth guarantees to mobile users that are comparable to the ones received by users in fixed networks. Error-prone communication links and user mobility make this a challenging task. In this paper, we propose a bandwidth allocation scheme for cellular networks that copes with user mobility. Our proposed scheme constructs, for each user, Hierarchical Clusters (HCs) which are tree-like structures having sub-clusters of cells as nodes. The HC of any user represents the cells that he is expected to visit during the lifetime of his call. Bandwidth is reserved in all cells of the HC thereby providing an estimation of future resource availability. Such estimates are used to determine the feasibility of admitting new calls. In constructing HCs, we use the velocity of the user and available data on user movement. Our scheme is adaptive since it works with any amount of available data. Results of simulations conducted are provided to demonstrate the performance obtained using our proposed scheme. ©2002 IEEE.