Wireless discovery using a reduced traffic load process

Traffic load over a wireless medium due to wireless access point discovery is reduced. The wireless stations and wireless access points support wireless discovery using a reduced traffic load process. The reduced traffic load process includes providing aggregated short probe responses.

BACKGROUND

Wireless Local Area Networks (WLAN) are very easy to set up and use, and have accordingly become very popular. WLANs connect computer networks via radio transmissions instead of traditional phone lines or cables. Benefits of these systems go well beyond getting rid of all the cables and wires. Campus networks can grow geographically larger while still retaining all their efficiency and speed. Additionally, cost savings can be realized when third-party circuit switched phone service are no longer needed, saving the cost of line rental and equipment upkeep. Finally, flexibility in campus network design increases significantly for the networking professional, while the network accessibility and usefulness increases for the individual users.

Wireless networks generally include multiple access points for wireless connectivity to multiple mobile stations. Such connectivity allows a mobile station to communicate with any number of types of devices within a network, for instance, a mainframe, a server, a networked printer, another mobile station, and the like. Mobile stations determine which network to join by scanning for available access points (AP). However, the scanning for available access points can cause a heavy load on the wireless medium.

DETAILED DESCRIPTION

A broadcast domain is a network that connects devices that are capable of sending and receiving broadcast frames to and from one another. This domain is also referred to as a Layer 2 network. APs (Access Points) that are in the same broadcast domain and configured with the same service set identifier (SSID) are said to be in the same roaming domain. When in a roaming domain, a roaming user can maintain application connectivity within the roaming domain as long as its Layer 3 network address is maintained. However, when the user begins to roam across domains, more processes than just finding a new AP to communicate with are needed. The client has to perform a Layer 2 roam, including AP discovery, before beginning a Layer 3 roam.

Applications that are continuously running on mobile devices benefit from the high data rates of the IEEE 802.11 interface. Further, mobile users are constantly entering and leaving the coverage area of an existing extended service set (ESS). A mobile device performs a discovery process each time link setup is initiated, regardless of whether the mobile device is requesting an initial link setup of the mobile device. This calls for efficient mechanisms that scale with a high number of users simultaneously entering an ESS.

According to the IEEE 802.11 WLAN standard, active scanning is a procedure used by a STA (Station) to discover an AP by transmitting a probe request and decoding the shared wireless medium (WM) in an attempt to decode a response. Excessive air-time occupancy has been seen as a major drawback for using active scanning in a high-density Wi-Fi device environment. Thus, in a highly loaded WM, the active scanning procedure has the possibility to heavily load the WM due to both single and multiple probe requests. A single probe request may cause multiple probe responses from one or more APs. Each multiple probe request originating from a different STA calls for its own separate probe response without a method to unify the probe responses in a controlled, non-probabilistic manner. Moreover, active scanning occupies much air-time proportionally to the number of STAs multiplied by the number of the replying APs. Passive scanning doesn't cause air-time occupancy. However, passive scanning takes longer to discover a desired AP, resulting in a longer delay and higher power consumption, as the STAs have to wait for a cyclically transmitted message (e.g., a beacon, short beacon or the like).

FIG. 1illustrates roaming across roaming domains in a wireless system100according to an embodiment. InFIG. 1, a network110includes two subnet routers, i.e., subnet A router120and subnet B router122. Subnet A router120and Subnet B router122are coupled to a first Layer 2 switch130and second Layer 2 switch132, respectively. A first access point (AP)140is coupled to the first Layer 2 switch130and a second AP142is coupled to the second Layer 2 switch132. The first AP140is associated with roaming domain A150and the second AP142is associated with roaming domain B152. A roaming user160is shown currently located within roaming domain A150and using STA170. However, the roaming user160moves from AP140on Subnet A router120to AP142on Subnet B router122. As a result, the client must change its Layer 3 network address to maintain Layer 3 connectivity on Subnet B.

An access process involves three steps: access point and network discovery, authentication and association. In the IEEE 802.11 standard, a wireless station (STA)170becomes aware of the existence of a Basic Service Set (BSS) through channel scanning. Channel scanning schemes contain two groups of methods: 1) STA passively seeking (i.e., receiving only in attempt to correctly decode) beacon transmissions from an access point (AP), and 2) STA actively probing (i.e., transmitting and attempting to decode response within a defined time) for the existence of an AP through a probe request/response exchange.

APs140,142periodically broadcast beacon frames through available channels. Beacon frames may include the information associated with an AP140,142, such as maximum transmit power, and the channels to be used for the regulatory domain. Stations170, which may be referred to as client devices, scan surrounding wireless networks to locate a compatible network. Active scanning or passive scanning may be used. Active scanning occurs when an STA170transmits a probe request and waits for a probe response from an AP (Access Point) which was able to decode and comply with the information enclosed in the probe request. In contrast, passive scanning occurs when an STA170attempts decoding of the shared WM (Wireless Medium) in an attempt to decode a broadcast message, e.g., a beacon, a measurement pilot or a probe response. As a result, while active scanning is optimized for power, passive scanning provides tower WM occupancy. Passive scanning network (NW) discovery can be achieved by decoding probe response and measurement pilot messages.

FIG. 2illustrates active scanning200wherein the SSID of the probe request is set to null to discover an AP having the strongest signal according to an embodiment. The STA210prepares a list of channels and broadcasts a probe request frame on each of them to scan wireless networks. InFIG. 2, two probe requests220,222are shown with a first probe request220being correctly decoded by AP1230and a second probe request222being received by AP2232. APs that receive a probe request send a probe response. InFIG. 2, AP2232sends a probe response240to the STA210. The STA210associates with the AP with the strongest signal. This active scanning200enables an STA210to know the AP identity and its operational parameters (e.g., AP load, PHY and MAC capabilities).

FIG. 3shows active scanning300wherein the probe request carries a specified SSID according to an embodiment. The client310unicasts a probe request320to AP1330containing the specified SSID. When AP1330receives the probe request320, AP1330sends a probe response340to the client310. This active scanning300enables a client310to identify existence of the specified wireless network, i.e., AP1330, in its current location and channel conditions.

FIG. 4illustrates passive scanning400according to an embodiment. InFIG. 4, AP1410broadcasts a beacon420that is received by clients within range, e.g., Client1430and Client2440. Passive scanning is used by clients430,440to discover surrounding wireless networks by listening to the beacon frames periodically sent by AP1410, or by another AP. Clients430,440prepare a list of channels and listen to beacons on each of these channels.

However, active scanning occupies much air-time proportionally to the number of STAs. Real conditions are much more severe because the responding AP is not the only AP sending and receiving data using the WM. Passive scanning doesn't cause air-time occupancy, but takes a longer time to discover a desired AP.

FIG. 5illustrates probe responses to multiple probe requests being sent using a single probe response in a wireless system500according to an embodiment. InFIG. 5, a plurality of wireless nodes may include a plurality of wireless access points (AP) AP1520, AP2522and a plurality of wireless stations STA1510, STA2512, STA3514. AP1520and AP2522include an antenna523,524, respectively, for receiving and transmitting wireless signals. STA1510and STA2512each send a probe request530,532to AP1520. AP1520responds to the probe requests530,532by unifying probe responses into a single probe response540. However, unifying probe responses to a single probe response540is susceptible to the scheduling of probe requests because the probe response is supposed to appear within a narrow transmission window. This narrow window needs to comply with the scheduling window of each and every one of the Probe Requests answered by the probe response.

FIG. 6shows the receive window600for a probe response according to an embodiment. InFIG. 6, a scanning station STA610is shown sending a probe request frame620according to an embodiment. Scanning STA610moves to a particular channel and then waits until a Probe Delay timer expires. Scanning STA610then senses the medium for the absence of transmissions by other STAs for a minimum of distributed coordination function (DCF) interframe space (DIFS) time period612. The DIFS time period612is used by transmitting devices to transmit data exchange frames and management frames. Management frames include such frames as probe request frames620and probe response frames632,642used for communications handshakes between a mobile station, e.g., scanning STA610, and an access point, e.g., responder1630and responder2640. If the medium remains idle during the DIFS time period612, the scanning STA610picks a backoff interval in the range of (0, CW), where CW denotes a contention window614. CW614is initially set to be a preset minimum contention window size, CWmin, and doubled each time a retransmission occurs, until it reaches the preset maximum contention window. A short interframe space (SIFS)616is employed when a transmitting device, e.g., scanning STA610, has seized a channel on the wireless medium and needs to keep the channel for the duration of the frame exchange procedure to be performed. One example is the acknowledgement procedure where the acknowledgment frame650(or “ACK frame”) transmission duration is preserved by the originator of the preceding frame.

The scanning STA610accesses a medium and transmits a probe request frame620. Upon listening to the probe request frame620of the scanning STA610, a responder1630transmits a probe response frame632to the scanning STA610and a responder2640transmits a probe response frame642to the scanning STA610. Here, responder1630and responder2640may be an AP. The probe response frame632of the responder1630is transmitted based on the DCF rule of IEEE 802.11 standard. Accordingly, the probe response frame632is transmitted through the process of contention window614.

Min_Probe_Response_Time660is a minimum response time. If a correct frame (e.g., other response) has been received before the minimum response time lapses, responses are awaited until Max_Probe_Response_Time670expires. If not, a scanning STA610may change channels when a short probe response is not received during the set response time. When a scanning STA610receives a probe response, the scanning STA610may act on a reference provided therein. InFIG. 6, for example, if no other probe response is received until the Max_Probe_Response_Time670expires for the two probe response frames642,632, the scanning STA610determines that there are two APs in the channel based on receipt of the two probe response frames632,642. However, extending the receive window by the Min_Probe_response_Time660and Max_Probe_Response_Time670is limited due to a negative effect over the mobile device containing the scanning STA610.

The wireless stations and wireless access points according to embodiments described herein are configured to support wireless discovery using a reduced traffic load process. The reduced traffic load process includes providing aggregated short probe responses.

FIG. 7illustrates the use of short probe response aggregation700according to an embodiment. InFIG. 7, a probe request710is responded by multiple APs, AP1720, AP2730, each using its own short probe responses722,732. The short probe responses722,732, e.g., measurement pilots, short beacon or FILS (Fast Initial Link Setup) discovery frame, may be used to point to nearest beacon740,750, respectively, or to more distant beacons depending on the discretion of the APs, AP1720, AP2730. The short probe responses722,732provide the timer synchronization function (TSF) clock, the target beacon transmission time (TBTT) and the beacon interval that provides the scheduling information on not only the nearest beacon740to be transmitted, but also to future instances of the beacon. The short probe responses722,732provide only information pertinent to a STA for performing link setup with an access point while reducing traffic overhead to the wireless medium. The information770only includes partial information of the AP capabilities and attributes772, scheduling information and/or reference to full wireless AP capabilities774, and an indication of the correct decoding of the probe request776. The scheduling information and/or reference to full wireless AP capabilities774may include multiple instances of the probe responses providing full AP capabilities provided in a schedule. A decision on the reference to the scheduling of the full AP capabilities may be derived from any combination of the entity of the STA performing the probe request, AP filtering information, the preferences of the STA enclosed in the probe request and the number of STAs attempting active scanning at a given time interval to reduce the maximum number of STAs with an outstanding association procedure. The response windows778,779for the short probe responses722,732are shorter than the response window used for a full AP capabilities message as the short probe responses722,732can be constructed in advanced or dynamic fields within it (e.g., the Timing Synchronization Field (TFS)). The short probe response722,732may be unicast, multicast or broadcast or may use OUI (Organizational Unique Identifiers), i.e., special MAC allocated address. The short probe responses722,732may also indicate the correct reception of probe requests710by referring to it. AP1720and AP2730responding with the short probe responses722,732use the current virtual and/or physical CSMA/CA to contend on resources to transmit the short probe responses722,732.

Thus, the probe request710is responded to by transmitting short probe responses722,732by AP1720and AP2730, respectively, to indicate the link coverage and correct reception of the probe request710. The short probe responses722,732may be an ACK like message, a beacon, a short beacon or a measurement pilot, or a FILS Discovery Frame (FD) to reduce the associated WM usage. In addition, the short probe responses722,732include the scheduling information of a message providing the complete information of AP1720and AP2730, respectively, i.e., scheduling information of beacons740,750, respectively and their associated scheduling cycle with a certain accuracy. Beacons740,750providing the complete information may be full beacons, mini beacons, measurement pilots or FD frame. The short probe responses722,732may additionally include the scheduling of repeated full information message transmission thereby increasing the decoding resiliency of complete information and enabling smart scheduling of multiple channel message decoding using future instances of the full message transmission rather than the nearest.

As shown inFIG. 7, multiple short probe responses722,732may be pointed to the same full message, thereby reducing the WM occupancy. AP1720and AP2730may also use this scheme to prioritize the entry of certain STAs over other STAs by pointing to nearby or distant full message respectively. Due to the use of short probe responses722,732, which include minimal information and can be pre-constructed, the receive window of the STA702following the probe request710may be shortened, thereby improving the PWR consumption during the NW discovery phase.

FIG. 8is a flowchart for mixed active and passive scanning800according to an embodiment. A mixture of STAs performing passive and active scanning is provided using a set of predefined roles, for example, by having STAs draw dice using pre-defined probability characteristics. InFIG. 8, the scanning procedure is initiated at operation810. The scanning procedure allows the STA to select probability function parameters at operation820. The STA may be scanning for the first time and setting probability function parameters accordingly, or, if not for the first time, the STA may reset its probability function parameters. In addition, the probability function behavior may be fixed so that the behavior is independent of the past history. Thus, the probability function parameters may be set depending on whether this is the first scanning since power up or whether other scanning has been performed in the near past. Thus, the setting of the probability function parameters may be based on a random probability distribution that is biased according to the pre-defined probability characteristics.

The STA draws dice at operation830with the results being based on the probability function parameters and selects the scanning type indicated. The result of the draw dictates whether the STA attempts NW discovery using an active scanning procedure or a passive scanning procedure. The probability characteristics may be fixed or variable. Further, the probability of selecting active or passive scanning may be dependent on events. Such events may be based on frames received by the STA over the WM in a given time interval. The probability function may also include a bias increasing the probability of passive or active scanning procedure selection.

The STA performs scanning according to the indicated scanning type at operation840. At operation850, a determination is made as to whether the scanning is complete. If the scanning is complete (operation852), i.e., an adequate AP for association is found, the STA performs an association procedure at operation860. The process is then terminated operation870. Otherwise (operation854), the STA updates the probability function parameters at operation880, i.e., updates the scanning parameters, and then returns (operation882) to operation830to draw dice again, and according to the scanning type, performs the scanning attempt again, e.g., minimal duration between successive active scanning attempts.

FIG. 9is a flowchart900for updating the probability function parameters according to an embodiment. InFIG. 9, the updating of the scanning parameters is initiated at operation910. The latest parameter values are retrieved at operation920. The events of the last scanning are retrieved at operation930. A determination is made whether a threshold has been crossed at operation940. If the threshold has been crossed (operation942), the parameters are set as default values at operation950. Otherwise (operation944), the scanning parameters are updated according to the events of the last scan and past scans at operation960. The process then returns to the mixed scanning procedure to draw dice at operation970. As a default value, previous parameters may be overridden so that a STA may select active or passive scanning at its own discretion upon detection of certain predetermined conditions. For example, a predetermined condition may include performing wireless access discovery for emergency services such as 911 services, or in response to other network events.

The update of the scanning parameters may be used to level the active and passive scanning and to identify and subside the WM occupancy effect of active scanning in some situations where the WM is loaded. The updates may be dependent on one or more events in any combination. Such events may include the duration from loss of the recent association; the level of WM occupancy or traffic measured over the shared channel by an AP or STA; the number of AP identified in the last scanning procedure either via beacons, probe response, measurement pilots, and/or mini beacons; the number of probe requests identified in given time interval; and an indication by a received frame in the frame header for a specific type of scanning allowed or disallowed. The probability function may also be defined such that it leans towards passive or active scanning, i.e., be modified to include a bias. The probability function may also come into action, i.e., be used or overridden, in some situations depending on the events identified over the WM. e.g., no AP being identified for a predetermined duration.

FIG. 10illustrates a block diagram of an example machine1000upon which any one or more of the techniques (e.g., methodologies) discussed herein may perform. In alternative embodiments, the machine1000may operate in a standalone mode or may be connected (e.g., networked) to other machines in a network mode. In a networked deployment, the machine1000may operate in the capacity of a server machine, a client machine, or both in server-client network environments. In an example, the machine1000may act as a peer machine in peer-to-peer (P2P) (or other distributed) network environment. In another example, the machine1000may acts as a client (STA) or an AP during a link setup when domain crossing occurs.

The machine1000may further be a personal computer (PC), a tablet PC, a set-top box (STB), a Personal Digital Assistant (PDA), a mobile telephone, a web appliance, a network router, switch or bridge, or any machine capable of executing instructions (sequential or otherwise) that specify actions to be taken by that machine.

Further, while only a single machine is illustrated, the term “machine” shall also be taken to include any collection of machines that individually or jointly execute a set (or multiple sets) of instructions to perform any one or more of the methodologies discussed herein, such as cloud computing, software as a service (SaaS), other computer cluster configurations. Examples as described herein may include, or may operate on, logic or a number of components, modules, or mechanisms. Modules are tangible entities (e.g., hardware) capable of performing specified operations and may be configured or arranged in a certain manner. In an example, circuits may be arranged (e.g., internally or with respect to external entities such as other circuits) in a specified manner as a module. In an example, the whole or part of one or more computer systems (e.g., a standalone, client or server computer system) or one or more hardware processors may be configured by firmware or software (e.g., instructions, an application portion, or an application) as a module that operates to perform specified operations. In an example, the software may reside on a machine-readable medium. In an example, the software, when executed by the underlying hardware of the module, causes the hardware to perform the specified operations.

Machine (e.g., computer system)1000may include a hardware processor1002(e.g., a central processing unit (CPU), a graphics processing unit (GPU), a hardware processor core, or any combination thereof), a main memory1004and a static memory1006, some or all of which may communicate with each other via an interlink (e.g., bus)1008. The machine1000may further include a display unit1010, an alphanumeric input device1012(e.g., a keyboard), and a user interface (UI) navigation device1014(e.g., a mouse). In an example, the display unit1010, input device1012and UI navigation device1014may be a touch screen display. The machine1000may additionally include a storage device (e.g., drive unit)1016, a signal generation device1018(e.g., a speaker), a network interface device1020, and one or more sensors1021, such as a global positioning system (GPS) sensor, compass, accelerometer, or other sensor. The machine1000may include an output controller1028, such as a serial (e.g., universal serial bus (USB), parallel, or other wired or wireless (e.g., infrared (IR)) connection to communicate or control one or more peripheral devices (e.g., a printer, card reader, etc.).

The storage device1016may include a machine-readable medium1022on which is stored one or more sets of data structures or instructions1024(e.g., software) embodying or utilized by any one or more of the techniques or functions described herein. The instructions1024may also reside, completely or at least partially, within the main memory1004, within static memory1006, or within the hardware processor1002during execution thereof by the machine1000. In an example, one or any combination of the hardware processor1002, the main memory1004, the static memory1006, or the storage device1016may constitute machine-readable media.

While the machine-readable medium1022is illustrated as a single medium, the term “machine readable medium” may include a single medium or multiple media (e.g., a centralized or distributed database, and/or associated caches and servers) that are configured to store the one or more instructions1024.

The instructions1024may further be configured for transmission and reception over a communications network1026using a transmission medium via the network interface device1020utilizing any one of a number of transfer protocols (e.g., frame relay, internet protocol (IP), transmission control protocol (TCP), user datagram protocol (UDP), hypertext transfer protocol (HTTP), etc.). Example communication networks may include a local area network (LAN), a wide area network (WAN), a packet data network (e.g. the Internet), mobile telephone networks (e.g., channel access methods including Code Division Multiple Access (CDMA), Time-division multiple access (TDMA), Frequency-division multiple access (FDMA), and Orthogonal Frequency Division Multiple Access (OFDMA); and cellular networks such as Global System for Mobile Communications (GSM), Universal Mobile Telecommunications System (UMTS), CDMA 2000 1x* standards and Long Term Evolution (LTE)); Plain Old Telephone (POTS) networks; and wireless data networks (e.g., Institute of Electrical and Electronics Engineers (IEEE) 802 family of standards including IEEE 802.11 standards (Wi-Fi®), IEEE 802.16 standards (WiMax®) and others) and peer-to-peer (P2P) networks; or other protocols now known or later developed.

For example, the network interface device1020may include one or more physical jacks (e.g., Ethernet, coaxial, or phone jacks) or one or more antennas to connect to the communications network1026. In an example, the network interface device1020may include a plurality of antennas to wirelessly communicate using at least one of single-input multiple-output (SIMO), multiple-input multiple-output (MIMO), or multiple-input single-output (MISO) techniques. The term “transmission medium” shall be taken to include any intangible medium that is capable of storing, encoding or carrying instructions for execution by the machine1000, and includes digital or analog communications signals or other intangible medium to facilitate communication of such software.