Method and apparatus for low-power AP-assisted fast wireless roaming using optimized neighbor graphs

An embodiment of the present invention provides a method, comprising using optimized neighbor graphs for low-power access point assisted fast wireless roaming by a wireless station (STA) operating in a wireless network.

BACKGROUND

Quality of Service (QoS) of applications such as, but not limited to, voice over Internet Protocol (VoIP), video conferencing etc. in enterprise wireless local area networks (WLAN) depend on seamless fast transitions. This is true whether they are between different access points (APs) belonging to same PHY technology (e.g. ‘a’‘a’, or, ‘b’‘b’), or to newer usages requiring inter-PHY (e.g. ‘a’ band‘n’, or, ‘b’‘n’) transitions. Very little design attention has been given to the inter-PHY transitions and thus, a strong need exists for methods and apparatus for improved inter-PHY transitions to enable fast wireless roaming in wireless networks.

It will be appreciated that for simplicity and clarity of illustration, elements illustrated in the figures have not necessarily been drawn to scale. For example, the dimensions of some of the elements are exaggerated relative to other elements for clarity. Further, where considered appropriate, reference numerals have been repeated among the figures to indicate corresponding or analogous elements.

DETAILED DESCRIPTION

Some portions of the detailed description that follows are presented in terms of algorithms and symbolic representations of operations on data bits or binary digital signals within a computer memory. These algorithmic descriptions and representations may be the techniques used by those skilled in the data processing arts to convey the substance of their work to others skilled in the art. In some embodiments, such algorithms and data processing may include analog processing at baseband frequencies, intermediate-frequencies (IF), or radio-frequencies (RF) implemented at least in part in hardware, in software, or in a combination thereof, although the scope of the invention is not limited in this respect.

Unless specifically stated otherwise, as apparent from the following discussions, it is appreciated that throughout the specification discussions utilizing terms such as processing, computing, calculating, determining, or the like, refer to the action or processes of a computer or computing system, or similar electronic computing device, that manipulate or transform data represented as physical, such as electronic, quantities within the registers or memories of the computing system into other data similarly represented as physical quantities within the memories, registers or other such information storage, transmission or display devices of the computing system.

In the following description and claims, the terms coupled and connected, along with their derivatives, may be used. In particular embodiments, connected may be used to indicate that two or more elements are in direct physical or electrical contact with each other. Coupled may mean that two or more elements are in direct physical or electrical contact. However, coupled may also mean that two or more elements may not be in direct contact with each other, but yet may still cooperate or interact with each other.

It should be understood that embodiments of the present invention may be used in a variety of applications. Although the present invention is not limited in this respect, the circuits disclosed herein may be used in many apparatuses such as in the transmitters and receivers of a radio system. Radio systems intended to be included within the scope of the present invention include, by way of example only, wireless local area networks (WLAN) devices and wireless wide area network (WWAN) devices including wireless network interface devices and network interface cards (NICs), base stations, access points (APs), gateways, bridges, hubs, cellular radiotelephone communication systems, satellite communication systems, two-way radio communication systems, one-way pagers, two-way pagers, personal communication systems (PCS), personal computers (PCs), personal digital assistants (PDAs), sensor networks, personal area networks (PANs) and the like, although the scope of the invention is not limited in this respect.

Types of wireless communication systems intended to be within the scope of the present invention include, although not limited to, Wireless Local Area Network (WLAN), Wireless Wide Area Network (WWAN), Code Division Multiple Access (CDMA) cellular radiotelephone communication systems, Global System for Mobile Communications (GSM) cellular radiotelephone systems, North American Digital Cellular (NADC) cellular radiotelephone systems, Time Division Multiple Access (TDMA) systems, Extended-TDMA (E-TDMA) cellular radiotelephone systems, third generation (3G) systems like Wide-band CDMA (WCDMA), CDMA-2000, and the like, although the scope of the invention is not limited in this respect.

Referring now toFIG. 1, a wireless local area network communication system in accordance with one embodiment of the present invention will be discussed. In the WLAN communications system100shown inFIG. 1, a mobile unit110(also referred to herein as a wireless station (STA) or “client”) may include a wireless transceiver112to couple to an antenna118and to a processor114to provide baseband and media access control (MAC) processing functions. Processor114in one embodiment may comprise a single processor, or alternatively may comprise a baseband processor and an applications processor, although the scope of the invention is not limited in this respect. Processor114may couple to a memory116which may include volatile memory such as DRAM, non-volatile memory such as flash memory, or alternatively may include other types of storage such as a hard disk drive, although the scope of the invention is not limited in this respect. Some portion or all of memory116may be included on the same integrated circuit as processor114, or alternatively some portion or all of memory116may be disposed on an integrated circuit or other medium, for example a hard disk drive, that is external to the integrated circuit of processor114, although the scope of the invention is not limited in this respect. Mobile unit110may communicate with access point122via wireless communication link132, where access point122may include at least one antenna120. In an alternative embodiment, access point122and optionally mobile unit110may include two or more antennas. Access point122may couple with network130so that mobile unit110may communicate with network130, including devices coupled to network130, by communicating with access point122via wireless communication link132. Network130may include a public network such as a telephone network or the Internet, or alternatively network130may include a private network such as an intranet, or a combination of a public and a private network, although the scope of the invention is not limited in this respect. Communication between mobile unit110and access point122may be implemented via a wireless local area network (WLAN), for example a network compliant with a an Institute of Electrical and Electronics Engineers (IEEE) standard such as IEEE 802.11a, IEEE 802.11b, IEEE 802.11g, IEEE 802.11n, HiperLAN-II, and so on, although the scope of the invention is not limited in this respect. In another embodiment, communication between mobile unit110and access point122may be at least partially implemented via a cellular communication network compliant with a 3GPP standard, although the scope of the invention is not limited in this respect.

Embodiments of the present invention provide design and protocol enhancements to those defined in the IEEE-80211r-2008 standard, although the present invention is not limited in this respect or to any particular standard. These standard protocols are highly inefficient, because every time when roaming to the target AP, the client (also may be referred to herein as wireless station (STA) or mobile unit) needs to exchange 11r-authentication messages with the target AP so as to re-calculate PTK. This may cost on some APs (although not limited in this respect) a few milliseconds which is accountable for seamless Fast Transition. Existing methods of transition require a client to scan every single time that it needs to roam. This is bad for transition time and also very bad for device power. Embodiments of the present invention enable lower power consumption by mobile units during roam time and speed up roam-time by reducing time taken by clients to scan and select a new AP.

When the client is associated with the AP, and when it gets a neighbor graph from that AP, then, it does not need to perform scans. Not having to perform scans has very good power benefits and also eliminates scan-time which is a wasted time for transitions.

Although not limited in this respect, embodiments of the present invention enable the use of pre-derived PTK for re-association when roaming happens, thus the present invention can save on some APs for example, but not limited to, a few, such as, 15˜20 milliseconds, for exchanging 11r-authentication messages. Further, both the enhanced Neighbor Report messages and 11r-authentication with neighbor APs so as to get PTK in advance will not affect the secure communication between the client and the associated AP, thus will not block the normal data traffic between the client and the associated AP.

Although embodiments of the present invention may be described in terms of the Institute for Electronic and Electrical Engineers (IEEE) 802.11 standard, it is understood that the present invention is not limited to 802.11 and may be used also in additional wireless technologies such as, but not limited to, 802.16 and 802.21.

802.11r is an amendment to the 802.11 standard to permit continuous connectivity to wireless devices in motion, with fast and secure handoffs from one AP to another managed in a seamless manner. Embodiments of the present invention provide an enhanced seamless fast transition mechanism over and above that described in the IEEE 802.11r standard, which is also applicable to inter-PHY technology handoffs.

Looking now atFIGS. 2A and 2B, generally shown as200, are illustrations of the current mechanism of 802.11r over-the-DS fast transition in the RSN, and works as follows:

1. In the fast BSS transition mechanism, the fast BSS transition protocol needs the initial information exchange during the first association between client210and AP220. Such initial exchange is referred to as the fast basic service set (BSS) transition initial mobility domain association protocol.

2. Subsequent reassociations to APs within the same Mobility Domain (A mobility domain is defined as the set of BSSs that are within the same extended service set (ESS) and support the fast BSS transition protocol) may perform the fast BSS Transition protocol.

It is noted that that: 1. The 11r-authentication request is transmitted to the target AP250through the current AP240, and the 11r-authentication response is transmitted back to the client230through the current AP240;2. Rather than in data frames, both 11r-authentication request and response are encapsulated in action frames; 3. Client230communicates with APs through the enterprise wireless LAN, while APs communicate with each other through the enterprise wired LAN.

However, the 80211r Fast Transition process shown inFIGS. 2A and 2Bis insufficient, because every time when roaming to the target AP220and250, the client210and230needs to exchange 11r-authentication messages (11r-authentication request and 11r-authentication response) with the target AP220and250so as to re-calculate PTK. And, as mentioned above, this may cost several milliseconds during critical roam-time, which may impact voice calls during Fast Transition, which have a sub 50 msec L2 roaming budget. Therefore, reducing this latency is of utmost importance for secure and seamless Fast Transition.

Looking now atFIG. 3, shown generally as300, is an illustration of the typical neighbor graph of the enterprise WLAN deployment of an embodiment of the present invention. The neighbor graph is depicted by using the measurement results of each AP in the enterprise WLAN. The neighbor graph could be dynamically changed due to the change of the enterprise environments, e.g. Channel re-assignment of APs by the WLAN Controller. The IEEE 802.11k group has defined mechanisms for clients to report such measurements in enterprise WLAN, and most APs support this, as well. So, the present invention may facilitate 802.11r Fast Transition by using the results of such kind of measurement. Measurements derived by actively asking for the current AP's neighbors and performing 11r-authentication with those neighbors so as to derive PTK in advance. However, by using the current 802.11k Neighbor Report mechanism, the client can only get a limited number of APs to perform 11r-authentication in advance. E.g., if the client is currently associated with AP8310, by using the current 802.11k Neighbor Report mechanism, the client can only get AP5320, AP7330and AP12340to perform 11r-authentication exchange in advance. This is not good when a client is moving around, as the client needs to get multiple neighbor reports and then do 11r-authentications.

Having a broader network topology will ensure clients have done 11r-authentications with those APs, and that it does not need to get multiple neighbor reports, and then do 11r-auths. Thus, embodiments of the present invention enhance the current 802.11k Neighbor Report mechanism: instead of only getting a limited number of neighbor APs, the clients will get the entire WLAN AP network topology; in other words, the clients will get all those APs (except the current associated AP) that appears inFIG. 3through the enhanced 802.11k neighbor report mechanism.

FIG. 4at400shows the proposed frame format for the enhanced 802.11k neighbor report request of an embodiment of the present invention. MAC header is illustrated at410and Action details at420. It is noted that the Category should be configured to represent that this is a request to get the entire WLAN AP network topology and the SSID should also be configured so as to get those APs who belongs to the same ESS.

FIG. 5at500illustrates the proposed frame format for the enhanced 802.11k neighbor report response of embodiments of the present invention. MAC header is illustrated at510and Action details at520. In addition to configuring both the Category and the SSID, the WLAN AP elements should also be included in this response; and all of the returned WLAN APs should belong to the same ESS which is specified by the SSID.

FIG. 6at600shows a proposed format for the WLAN AP element of embodiments of the present invention. Note that:

1. Element ID should have the value that has not been used by any other existing elements;

2. Length should equal to 14, which is just the size of the left areas;

3. BSSID is the MAC Address of the AP;

4. AP Reachability represents whether this AP could be reached by the STA through Wireless;

5. Channel Number is the current working channel of this AP;

6. Measured RSSI is the measured RSSI value and client could use it to check the signal strength with this AP;

7. Station Count tells the number of stations that are currently associating with this AP;

8. Channel Utilization is an integer between 0 and 255, which is defined as the percentage of time that this QoS AP sensed the medium was busy;

9. Available Admission Capacity contains the remaining amount of medium time available via explicit admission control. It is helpful for a mobile station to select a QoS AP that is likely to accept future admission control requests. The WLAN AP element is very important for the client, as the clients need to evaluate both the QoS and the signal strength before determining the best candidate AP for 802.11r fast transition.

Important novel aspects of embodiments of the present invention provide that the Client may use this AP-topology map from the network to perform 802.11r-authentication exchange with multiple APs. This allows a Client to derive PTKs (session keys for encryption) ahead of its AP-selection decision, increase association chances, and eliminate scanning. Some embodiments of the present invention also provide that Clients use such “primed” APs as more viable roaming candidates.

Embodiments of the present invention also reduce the hysteresis effect (when a client ping-pong between same two APs) on users, improving performance. Further, wireless roaming data suggests that the present invention may greatly reduce roam scanning. Reducing roam time scanning is a big power-save opportunity for handheld and laptop clients, although the present invention is not limited in this respect. Data also shows that AP-assisted roams reduce the number of association failures when the client does not have to “guess” the best AP only on scan results. Scan results can get obsolete by the time a complete scan is completed (1-2 mins)—a person can walk across 3 APs in this time.

FIGS. 7A and 7B, shown generally as700depict the enhanced seamless fast transition mechanism of embodiments of the present invention. It works as follows:

1. When the client710enters the WLAN for the first time, it will perform full scanning to find an AP720and perform initial 802.11r association with it so as to connect with the WLAN.

2. Once the client710successfully associates with some AP720, it will ask the associated AP720for its measured and maintained neighbor AP730topology graph. The present invention enables a client to use its location information to request a list of neighbor AP map.

3. Client710then performs 11r-authentication exchange (first 2 messages only), with all those 802.11r neighbor APs730and derive PTK (session keys) in advance; These session keys will have a long duration for KeyLifetime as PTK lifetime is bound to EAP KeyLifetime.

4. Roaming Trigger: After some time, a roaming might be generated within the client (normally by low RSSI) when the client moves away from the associated AP.

5. AP Selection: The client740will select out the best candidate based on the current neighbor AP750graph from associated AP. The AP selection algorithm will give preference to candidate APs with which the Client740has derived PTK in advance.

6. Once the client successfully roams to the new AP, it will continue to maintain a graph of all APs with which it has pre-established PTKs. Only the previous AP's PTK will be invalidated.

7. Client will request a fresh neighbor AP770graph measured and maintained by the newly associated AP760. When the client740gets the new neighbor AP770list, it will perform 11r-authentication exchange and derive PTKs with all APs with which it does not already have a PTK established.

8. As an enhancement to the Client's hysteresis algorithm, the Client740will derive a new 11r-authentication and PTK with the last AP that it just left. This way if the client performs a ping-pong effect by roaming between 2 APs, then its adverse effects to users is minimized. The client will repeat step 2˜step 8 when new 11r roaming is triggered at a later time.