In this study, we consider zone-based registration (ZBR). In the ZBR, when a mobile station (MS) enters a new location area (LA), it registers its location. Among various types of ZBR, we focus on two zone-based registration with outgoing call (TZRC) that is an improved version of the two zone-based registration (TZR). In the TZR, an MS can store two LAs that it registers recently not to register when it crosses two LAs stored already. In general, TZR has better performance than single zone-based registration (SZR). However, since the TZR may increase paging cost, TZRC was proposed to decrease paging cost. Mathematical analysis is performed to obtain the exact performance of SZR, TZR, TZRC. From the numerical results for various circumstances, it is shown that TZRC outperforms TZR and SZR in most cases.