A method includes transmitting a paging request message to a plurality of asynchronous base stations (102a-g) where a paging message is sent within its respective cell at any time within a given paging interval (202). The method continues by receiving notification that paged mobile station (106) has responded to a paging message. The page cancelling message indicates to the base stations do not need to send the paging message within their respective cells during the current paging interval and that the paging process is cancelled.