Recent advances in wireless communication and global positioning technologies have led to increasing interest in location dependent information services. As mobile users move between locations utilising such services, their access patterns not only exhibit temporal locality, but also spatial locality. Traditional cache replacement policies were designed to deal with temporal locality, as a result, they are inefficient location dependent services. In this paper, a mobility-aware algorithm called MARS+ is proposed to detect regular client movement patterns and provides information to improve cache performance. Test results show that MARS+ improves clients' cache hit ratio by more than 16% compared to existing policies.