Abstract:
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.

Description:
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.
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       The subject matter regarded as the invention is particularly pointed out and distinctly claimed in the concluding portion of the specification. The invention, however, both as to organization and method of operation, together with objects, features, and advantages thereof, may best be understood by reference to the following detailed description when read with the accompanying drawings in which: 
         FIG. 1  is a diagram of a wireless local area network communication system in accordance with one embodiment of the present invention; 
         FIGS. 2A and 2B  depict an 802.11r over-the-DS Fast Transition in a robust secure network (RSN); 
         FIG. 3 . illustrates a typical neighbor graph of an Enterprise wireless local area network (WLAN); 
         FIG. 4  shows an enhanced Institute for Electronic and Electrical Engineers (IEEE) 802.11k neighbor report request frame format of embodiments of the present invention; 
         FIG. 5  depicts an enhanced IEEE 802.11k neighbor report response frame format of embodiments of the present invention; 
         FIG. 6  depicts WLAN AP element contents of embodiments of the present invention; and 
         FIGS. 7A and 7B  show an enhanced 802.11r over-the-DS Fast Transition in the RSN of embodiments of the present invention. 
     
    
    
     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 
     In the following detailed description, numerous specific details are set forth in order to provide a thorough understanding of the invention. However, it will be understood by those skilled in the art that the present invention may be practiced without these specific details. In other instances, well-known methods, procedures, components and circuits have not been described in detail so as not to obscure the present invention. 
     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. 
     An algorithm is here, and generally, considered to be a self-consistent sequence of acts or operations leading to a desired result. These include physical manipulations of physical quantities. Usually, though not necessarily, these quantities take the form of electrical or magnetic signals capable of being stored, transferred, combined, compared, and otherwise manipulated. It has proven convenient at times, principally for reasons of common usage, to refer to these signals as bits, values, elements, symbols, characters, terms, numbers or the like. It should be understood, however, that all of these and similar terms are to be associated with the appropriate physical quantities and are merely convenient labels applied to these quantities. 
     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. 
     Embodiments of the present invention may include apparatuses for performing the operations herein. This apparatus may be specially constructed for the desired purposes, or it may comprise a general purpose computing device selectively activated or reconfigured by a program stored in the device. Such a program may be stored on a storage medium, such as, but is not limited to, any type of disk including floppy disks, optical disks, CD-ROMs, magnetic-optical disks, read-only memories (ROMs), random access memories (RAMs), electrically programmable read-only memories (EPROMs), electrically erasable and programmable read only memories (EEPROMs), flash memory, magnetic or optical cards, or any other type of media suitable for storing electronic instructions, and capable of being coupled to a system bus for a computing device. 
     The processes and displays presented herein are not inherently related to any particular computing device or other apparatus. Various general purpose systems may be used with programs in accordance with the teachings herein, or it may prove convenient to construct a more specialized apparatus to perform the desired method. The desired structure for a variety of these systems will appear from the description below. In addition, embodiments of the present invention are not described with reference to any particular programming language. It will be appreciated that a variety of programming languages may be used to implement the teachings of the invention as described herein. 
     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 to  FIG. 1 , a wireless local area network communication system in accordance with one embodiment of the present invention will be discussed. In the WLAN communications system  100  shown in  FIG. 1 , a mobile unit  110  (also referred to herein as a wireless station (STA) or “client”) may include a wireless transceiver  112  to couple to an antenna  118  and to a processor  114  to provide baseband and media access control (MAC) processing functions. Processor  114  in 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. Processor  114  may couple to a memory  116  which 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 memory  116  may be included on the same integrated circuit as processor  114 , or alternatively some portion or all of memory  116  may be disposed on an integrated circuit or other medium, for example a hard disk drive, that is external to the integrated circuit of processor  114 , although the scope of the invention is not limited in this respect. Mobile unit  110  may communicate with access point  122  via wireless communication link  132 , where access point  122  may include at least one antenna  120 . In an alternative embodiment, access point  122  and optionally mobile unit  110  may include two or more antennas. Access point  122  may couple with network  130  so that mobile unit  110  may communicate with network  130 , including devices coupled to network  130 , by communicating with access point  122  via wireless communication link  132 . Network  130  may include a public network such as a telephone network or the Internet, or alternatively network  130  may 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 unit  110  and access point  122  may 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 unit  110  and access point  122  may 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 at  FIGS. 2A and 2B , generally shown as  200 , 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 client  210  and AP  220 . 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 AP  250  through the current AP  240 , and the 11r-authentication response is transmitted back to the client  230  through the current AP  240 ;  2 . Rather than in data frames, both 11r-authentication request and response are encapsulated in action frames; 3. Client  230  communicates 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 in  FIGS. 2A and 2B  is insufficient, because every time when roaming to the target AP  220  and  250 , the client  210  and  230  needs to exchange 11r-authentication messages (11r-authentication request and 11r-authentication response) with the target AP  220  and  250  so 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 at  FIG. 3 , shown generally as  300 , 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&#39;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 AP 8   310 , by using the current 802.11k Neighbor Report mechanism, the client can only get AP 5   320 , AP 7   330  and AP 12   340  to 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 in  FIG. 3  through the enhanced 802.11k neighbor report mechanism. 
       FIG. 4  at  400  shows the proposed frame format for the enhanced 802.11k neighbor report request of an embodiment of the present invention. MAC header is illustrated at  410  and Action details at  420 . 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. 5  at  500  illustrates the proposed frame format for the enhanced 802.11k neighbor report response of embodiments of the present invention. MAC header is illustrated at  510  and Action details at  520 . 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. 6  at  600  shows 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 as  700  depict the enhanced seamless fast transition mechanism of embodiments of the present invention. It works as follows: 
     1. When the client  710  enters the WLAN for the first time, it will perform full scanning to find an AP  720  and perform initial 802.11r association with it so as to connect with the WLAN. 
     2. Once the client  710  successfully associates with some AP  720 , it will ask the associated AP  720  for its measured and maintained neighbor AP  730  topology graph. The present invention enables a client to use its location information to request a list of neighbor AP map. 
     3. Client  710  then performs 11r-authentication exchange (first 2 messages only), with all those 802.11r neighbor APs  730  and 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 client  740  will select out the best candidate based on the current neighbor AP  750  graph from associated AP. The AP selection algorithm will give preference to candidate APs with which the Client  740  has 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&#39;s PTK will be invalidated. 
     7. Client will request a fresh neighbor AP  770  graph measured and maintained by the newly associated AP  760 . When the client  740  gets the new neighbor AP  770  list, 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&#39;s hysteresis algorithm, the Client  740  will 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. 
     While certain features of the invention have been illustrated and described herein, many modifications, substitutions, changes, and equivalents may occur to those skilled in the art. It is, therefore, to be understood that the appended claims are intended to cover all such modifications and changes as fall within the true spirit of the invention.