A method and apparatus may be used to perform efficient network transitions. One or more of Probe Request frames that an AP may receive or process as valid may be modified by including a transmit power for the Probe Request frame. A Probe Request frame may be transmitted at less than full power. BSS transitions may be enhanced by indicating reasons for the transition, security information, or quality of service (QoS) information. Overhead associated with tracking long-sleeping STAs may be managed through the use of multiple values for a maximum idle period in a BSS.