Undoubtedly, GSM is the most important standard of the worldwide wireless communication in recent periods. The authentication protocol is the main component of the GSM architecture. However, there are several drawbacks found in the existing authentication protocol of GSM, such as bandwidth consumption between VLR and HLR, storage overhead in VLR, and the property that VLR cannot be authenticated. Nowadays, many authentication protocols are proposed to improve these drawbacks. Among them, Hwang et al's protocol [C.C. Lee, M.S. Hwang, W.P. Yang, Extension of authentication protocol for GSM, IEE Proceedings of Communication, 150(2) (2003) 91-95 [1]], proposed in 2003, can solve the above drawbacks. However, authenticating VLR is just executed at the first time, which MS joins into a new visiting VLR to ask for communication service. In this paper, we propose an improvement to modify Hwang et al's protocol such that mutual authentication between VLR and MS is ensured at anytime while MS sends an authentication request. In addition, we also propose a brand-new authentication protocol which can not only solve those drawbacks but also make the authentication more efficient.