Two location algorithm (TLA) considers two location areas (LAs) to track the location of a mobile station (MS). The TLA significantly outperforms the single location algorithm when the call-to-mobility ratio (CMR) is low (i.e., the user moves more frequently than to receive calls). However, because of the paging cost for the users moving back to the previously visited LA, the performance of the TLA degrades when the CMR is high. To reduce those paging cost, we propose the new algorithm called TLA with call information (TLAC). In TLAC, we use the location information of the MS within the setup message when the MS originates a call in the previously visited LA. Through the setup message, the system can know the exact location of the MS without the additional location registration operation, and the paging cost for the arriving calls in the visited LA can be reduced. An analytical model is proposed to compare the TLAC and previous TLA protocol. Our study indicates that the TLAC always guarantees better performance than the TLA. We also observe that the TLAC is much better than the TLA when the CMR is high.