In Machine-To-Machine (M2M) communications, devices can automatically communicate with each other without any intervention by humans. However, LTE-A is primarily designed and optimized for Human-To-Human (H2H) communications. Even though LTE-A has defined Machine-Type Communications (MTC), several parts are still undefined or follow the existing H2H standards. Specifically, the existing paging mechanism in LTE-A will substantially increase the computational load and signaling overhead of the system when there are many M2M devices. Therefore, we propose an effective solution to mitigate this problem. Compared with the traditional paging mechanism defined in LTE-A, the proposed solution can save more energy for M2M devices, reduce signaling overhead and alleviate the network's load significantly.