In this paper, we propose a paging scheme considering local environment and moving patterns of mobile hosts on HMIPv6. The proposed paging scheme can adaptively construct a paging domain according to handoff probability of mobile hosts and local environment, and process a paging based on handoff probability stage by stage. For analysis of the proposed paging scheme, we simulate our scheme in two different experiment environments: an open environment like a square and a restricted environment like downtown. In experiment results, the proposed scheme shows superior performance to that of compared scheme all over. Particularly, in case of high call request rate and a restricted environment, the proposed scheme shows better performance.