In the WiMAX End-to-End Network Architecture, the mobile station (MS) performs Access Service Network (ASN) anchored mobility to lower the handoff latency when it moves between base stations (BSs) and ASNs. However, the ASN anchored mobility will induce a heavy load on the ASN gateway (ASN-GW). Thus, relocating anchor ASN-GW for the MS is needed. It is a challenge for system designers to decide when to perform ASN-GW relocation, how many MSs should be relocated and which MSs should perform relocation. In the paper, we propose an average residence time based (ART-based) ASN-GW relocation algorithm to determine an appropriate time and to select a set of MSs to relocate their anchor ASN-GWs. The simulation results show that the ART-based ASN-GW relocation algorithm can reduce and steady the loads of ASN-GWs and decrease the number of relocations.