I. Introduction
Machine-to-Machine (M2M) communications is a new service type identified by the Third-Generation Partnership Project (3GPP) for the Long Term Evolution (LTE) networks. It usually involves many Machine-Type Devices (MTDs) that can actuate, exchange and process data without human intervention, which has found wide applications in various domains such as smart city, Industry 4.0 and e-health [1]. With the explosive growth of the number of MTDs [2], however, the deluge of access requests generated by MTDs may easily lead to severe congestion with intolerably low chances of success. Therefore, how to efficiently facilitate the access of a massive number of MTDs has become a significant challenge for supporting M2M communications over LTE networks [3].