A method includes receiving from a core network entity a paging message including a permanent user identity of a user for a specific user equipment, and determining, using the permanent user identity, a set of small cells to which the paging message should be sent based on a small cell last visited by the specific user equipment and small cells that are neighbors to the last-visited small cell. The paging message, without the permanent user identity, is sent to the determined set of small cells. Another method includes, responsive to determining a paging message for a specific user equipment is to be communicated toward the specific user equipment, determining whether a gateway can receive paging messages comprising a permanent user identity and a temporary user identity, and responsive thereto, sending the paging message for the specific user equipment to the gateway. Apparatus and computer program products are also disclosed.