A method in a mobile station (STA) configured to associate to an access point (AP) is described. The method includes determining an identifiable random medium access control (MAC) address (IRMA), associating to the AP and transmitting the IRMA to the AP during the association. The method also includes using the IRMA as the transmitter address (TA) a next time the STA begins to associate to the AP, where the IRMA is usable by the AP to identify the STA prior to a next association, determining a new IRMA, and transmitting the new IRMA to the AP during the next association. One or more additional associations to the AP are performed at least by transmitting at least a corresponding IRMA to the AP and indicating that the corresponding IRMA is a TA of the STA.