Quickly joining Wi-Fi networks using neighboring access points

One embodiment of the present invention provides a device for joining a known Wi-Fi network. During operation, the device performs a scanning operation during a scanning process to find a known access point of a WLAN for the device to join. Next, if the scanning operation finds an access point, the device determines whether the access point neighbors a known access point. If so, the device attempts to associate with the known access point by performing a scanning operation on the specific channel associated with the known access point.

BACKGROUND

Related Art

Smartphone applications, such as email clients and web browsers, often require an available Internet connection as soon as the user launches the application on the device. Such applications then use the connection to access web pages, email, and other online content. Smartphones generally use a cellular or Wi-Fi® connection to access the Internet. Moreover, applications typically prioritize Wi-Fi connections over cellular connections because Wi-Fi is often cheaper and faster than cellular connectivity. Thus, users benefit when applications automatically connect to Wi-Fi as often as possible.

Implementing this behavior in a device, however, introduces a unique problem, particularly when the device is waking up from sleep mode. When a smartphone device wakes up, the device takes time to establish a Wi-Fi connection with a known access point. This process may take up to six seconds. Such a delay may cause applications to report connectivity issues, which degrades the user experience.

An additional side effect of this delay occurs when the device gives up on Wi-Fi and falls back to a cellular connection. Switching back to a Wi-Fi connection when one finally appears is not seamless. Because the device has already established a socket for the application, the device cannot simply hand off the application midway from a cellular connection to Wi-Fi. As a result, the switch to back to Wi-Fi is often disruptive, resulting in a further degradation of the user experience.

SUMMARY

One embodiment of the present invention provides a device for joining a known Wi-Fi network. During operation, the device performs a scanning operation during a scanning process to find a known access point of a WLAN for the device to join, where a known access point is an access point that was previously stored in a database in the device. Next, if the scanning operation finds an access point, the device determines whether the access point is a discovered neighbor, wherein a discovered neighbor is an access point that neighbors a known access point and was previously stored in the database. If so, the device attempts to associate with the known access point by performing a scanning operation on the specific channel associated with the known access point.

DETAILED DESCRIPTION

Overview

Embodiments of the present invention use opportunistic scanning and optimized channel prioritization strategies to reduce the amount of latency experienced when a Wi-Fi enabled device connects to a Wi-Fi network. As a result, device applications are able to access online content sooner. Note that the term Wi-Fi may refer to IEEE 802.11, which is a set of standards developed for wireless local area network (WLAN) technology.

In some cases, embodiments of the present invention offer various advantages. Users may be able to use smartphone applications that require an Internet connection with less delay after waking their phone. For example, rather than having to wait six seconds before using an email client or a web browsing application, the user may check their email or browse the web in far less time after the smartphone screen turns back on. Typically, the six-second delay itself consists of two components. The first component comprises the time needed to scan a maximum of 35 Wi-Fi channels in 2.4 and 5.0 GHz bands. The second component comprises the connection establishment process once the device finds the Wi-Fi access point on the correct channel. The first component often makes up the majority of the six-second delay. Because access points only send out beacon frames once every 110 ms, passively scanning a channel for that access point may take up to 110 ms. Thus, scanning 35 channels would take nearly four seconds.

In some cases, embodiments of the present invention may also prevent situations where a Wi-Fi-enabled device degrades the user experience by falling back to a cellular connection. If a device is not able to secure a Wi-Fi connection for an application within a certain period after waking up, the device falls back to a cellular connection. Because Wi-Fi connections are cheaper and faster than cellular connections, the user may want to switch back to a Wi-Fi connection as soon as possible. However, the device cannot seamlessly hand off this connection from cellular to Wi-Fi because the application has already established a socket. Thus, the inevitable disruption caused by the switch back to Wi-Fi further degrades the user's experience. Embodiments of the present invention may prevent this scenario by reducing the amount of time needed to establish a Wi-Fi connection after waking up a device. A faster Wi-Fi connection process may translate to fewer fallbacks to a cellular connection, thus improving the user's experience.

One embodiment of the present invention provides a device for joining a known Wi-Fi network. During operation, the device performs a scanning operation during a scanning process to find a known access point for the device to join. Note that performing a scanning operation involves scanning a Wi-Fi channel. Also, note that scanning may refer to passive scanning, where the device passively listens to the channel for beacon frames from access points in range, or active scanning, where the device emits probe request frames and listens for probe response frames from access points in range. Next, if the scanning operation finds an access point, the device determines whether the access point neighbors a known access point. If so, the device attempts to associate with the known access point by performing a scanning operation on the specific channel associated with the known access point. Note that a known access point is an access point that was previously associated with the device. Also, note that an access point neighbors another access point if the device may discover the former while associated with the latter. Finally, note that embodiments of the present invention may exist as control logic that is coupled to an integrated circuit. Handsets may include this integrated circuit as a component along with other components such as a radio transceiver and an antenna.

In some embodiments of the present invention, when the device is associated with a given access point, the device stores the given access point in a database. Note that associating with a given access point for the first time and storing that access point in a database makes that access point a “known access point.” Also, note that storing the given access point in a database may include writing that access point to persistent storage.

In some embodiments of the present invention, while the device is associated with the given access point, the device opportunistically scans for access points that neighbor the given access point. The device then stores any discovered neighbor in the database.

In some embodiments of the present invention, when storing the given access point in the database, the device stores the given access point's service set identifier (SSID), basic service set identification (BSSID), channel, and the time the device last associated with the given access point. Note that the device may forego storing the SSID and rely solely upon the BSSID as the primary means to uniquely identify the given access point. Also, note that the device may include other attributes related to the given access point such as the security key or the received signal strength indication (RSSI).

In some embodiments of the present invention, when storing the discovered neighbor in the database, the device stores the discovered neighbor's BSSID, channel, a reference to the given access point which is neighbored by the discovered neighbor, and the number of times the discovered neighbor was found while the device was associated with the given access point. Note that the device may include other attributes related to the discovered neighbor such as the discovered neighbor's SSID, RSSI, and discovery date. Also, note that the device may use the given access point's BSSID or SSID as a reference to the given access point that is neighbored by the discovered neighbor.

In some embodiments of the present invention, the scanning process has the device scan all channels sequentially. For example, the device may start the scan at channel six. The scan continues through each consecutive channel up to the highest channel. Then, the scan wraps around and scans from channel one back up to channel five. If the device discovers a known access point, the device breaks off the scan and immediately associates with the known access point. If the device discovers a neighbor, the device: (1) retrieves the known access point neighbored by the discovered neighbor, (2) retrieves the channel used by the known access point, which may or may not be consecutive to the previously scanned channel, and (3) scans the channel. If, by scanning that channel, the device finds the known access point, the device immediately associates with that access point and ends the scanning process. Otherwise, the device continues the sequential scan.

In some embodiments of the present invention, the scanning process has the device scan the channels in three stages. During the first stage, the device scans the channel used by the known access point that was most recently associated with the device. During the second stage, the device scans the remaining channels used by the n most recently associated known access points. During the final stage, the device scans all remaining channels. Note that the remaining channels in the second stage may or may not include the channel scanned in the first stage. Also, note that the remaining channels in the third stage may or may not include the channels scanned in the first and second stages.

In some embodiments of the present invention, while the device is associated with the given access point, opportunistically scanning for access points that neighbor the given access point involves the following. When the device is not transferring data, the device listens on channels for any beacon sent by access points that neighbor the given access point. Note that opportunistic scanning is scanning done while the device (1) is associated with an access point but (2) is not transferring data. Also, note that this scanning may be active or passive scanning. For example, a user wakes up a smartphone to check email. The smartphone subsequently associates with an access point, giving the smartphone's email client Internet access. After the email client finishes downloading the email, the smartphone stops transferring data. Because the connection is idle, the smartphone may scan for neighboring access points without disrupting data transfers.

In some embodiments of the present invention, the device does the following to determine whether the access point neighbors a known access point. The device searches the database for a discovered neighbor whose BSSID matches the access point's BSSID. If the device finds a discovered neighbor, the device determines whether the discovered neighbor possesses a sufficient confidence level. Note that the device may match the access point to a discovered neighbor by SSID rather than by BSSID.

In some embodiments of the present invention, to determine whether a discovered neighbor possesses a sufficient confidence level, the device determines whether the number of times the device found the discovered neighbor is greater than a threshold value. Note that the device may use numerous factors in determining a discovered neighbor's confidence level. Factors may include, but are not limited to, the neighbor's RSSI level at discovery. For example, if a discovered neighbor's RSSI level is always low during discovery, the device may assign a lower confidence level to the discovered neighbor.

In some embodiments of the present invention, the device does the following to associate with the known access point. First, the device retrieves the discovered neighbor's reference to the known access point from the database. The device then uses the reference to retrieve the specific channel used by the known access point from the database. Next, the device scans that channel. Finally, if the device does not find the known access point on that specific channel right away, the device continues to scan that specific channel more frequently than the other channels while the scanning process continues.

Computing Environment

FIG. 1illustrates the computing environment100of a device user110in accordance with an embodiment of the present invention. Computing environment100includes a number of computer systems, which may include any type of computer system based on a microprocessor, a mainframe computer, a digital signal processor, a portable computing device, a personal organizer, a device controller, or a smartphone. More specifically, referring toFIG. 1, computing environment100includes user110, client120, database130, locations140-142, known access points150-153, and neighboring access points160-163.

Client120may include any node on a network including computational capability and a mechanism for joining a Wi-Fi network such as a smartphone, a PDA, a tablet computer, or a laptop computer.

User110may include an individual, a group of individuals, an organization, a group of organizations, a computing system, a group of computing systems, or any other entity that can interact with computing environment100.

Database130, which resides within client120, may include any type of system for storing data in non-volatile storage. This includes, but is not limited to, relational database management systems, text files, XML files and/or spreadsheets. This also includes, but is not limited to, systems based upon magnetic, optical, or magneto-optical storage devices, as well as storage devices based on flash memory and/or battery-backed up memory. Note that database130may be coupled to a server, to a client, or directly to a network.

Locations140-142may include any location in user110's commute where access points can be found including homes, train stations, proprietary businesses, libraries, and offices. Such access points may provide free public Wi-Fi, non-free public Wi-Fi, or Wi-Fi that is private only to user110.

Known access points150-153may include any access point that client120has previously associated with in the past. Some known access points may not require client120to remember a Wi-Fi protected access (WPA) key in order to rejoin because these known access points provide public unencrypted Wi-Fi. Other known access points may require client120to remember a WPA key in order to rejoin because these known access points provide only encrypted Wi-Fi.

Neighboring access points160-161are access points that client120can discover while associated with known access point150because neighboring access points160-161are all proximate to known access point150. However, neighboring access points160-161are also access points client120cannot join for reasons such as not having the correct WPA key.

Note that different embodiments of the present invention may use different system configurations, and are not limited to the system configuration illustrated in computing environment100.

System

FIG. 2illustrates a system200in accordance with an embodiment of the present invention. As illustrated inFIG. 1, system200may comprise client120, database130, access point150, or any combination thereof. System200may also include scanning mechanism202, association mechanism204, database mechanism206, confidence mechanism208, processor220, and memory222. Client120may use (1) scanning mechanism202to scan for known access points150-153and neighboring access points160-161, (2) association mechanism204to join one of the known access points150-153, and (3) database mechanism206to interface with database130. Furthermore, client120may use confidence mechanism208to determine how confident client120is regarding whether a neighboring access point, such as one of the neighboring access points160-161, actually neighbors a known access point, such as one of the known access points150-153.

Quickly Joining Wi-Fi Networks Using Neighbors

The next three figures explain how the client120uses neighboring access points to join a Wi-Fi network more quickly.FIG. 3presents a flow chart that illustrates how client120(1) searches for any nearby known access points to join and (2) records any neighboring access points discovered during these searches as user110moves from one location to another. Next,FIG. 4illustrates how client120divides the search for a known access point into three stages. Finally,FIG. 5explains how client120utilizes the discovered neighboring access points in each of these stages.

InFIG. 3, the device operates in two main phases: (1) while associated with a given access point, client120discovers neighbors, and (2) while not associated with any access point, client120searches for a known access point.

While client120is associated with a known access point, client120may store information about the known access point in database130(operation302). The database stores the known access point's SSID, BSSID, channel, and the time client120last associated with the given access point. For example, when user110is at location140and her smartphone client120associates with home access point150, database mechanism206stores several attributes of home access point150into an entry created in database130. First, database mechanism206stores “home_network” in the SSID attribute. Next, database mechanism206stores “01:23:45:67:89:ab” in the BSSID attribute. Next, database mechanism206stores “11” in the channel attribute. Finally, database mechanism206stores “8:00 AM, Jan. 4, 2010” in the attribute that represents the time client120last associated with home access point150.

While client120is associated with a known access point, scanning mechanism202opportunistically scans for neighboring access points that are in close proximity to the known access point (operation304). Database mechanism206stores a discovered neighbor's BSSID, the neighbor's channel, a reference to the known access point that the neighbor is proximate to, and the number of times client120discovered the neighbor while client120and the known access point were associated. For example, when user110is at location140and her smartphone client120is associated with home access point150, client120attempts to scan for other nearby access points while client120is not transferring data. In this example, client120discovers the following access points: home neighbor160and home neighbor161. Then, database mechanism206stores several attributes of home neighbor160into an entry created in database130. First, database mechanism206stores “01:23:45:67:89:ac” in the BSSID attribute. Next, database mechanism206stores “one” in the channel attribute. Next, database mechanism206stores the BSSID of home access point150(which is 01:23:45:67:89:ab) in the attribute that represents the known access point neighbored by home neighbor160. Finally, database mechanism206stores “15” in the confidence attribute because client120has found home neighbor16015 times in opportunistic scans while client120and home access point150were associated together.

Additionally, database mechanism206stores several attributes of home neighbor161into an entry created in database130. First, database mechanism206stores “01:23:45:67:89:ad” in the BSSID attribute. Next, database mechanism206stores “six” in the channel attribute. Next, database mechanism206stores the BSSID of home access point150(which is 01:23:45:67:89:ab) in the attribute that represents the known access point neighbored by home neighbor161. Finally, database mechanism206stores “19” in the confidence attribute because client120has found home neighbor16119 times in opportunistic scans while client120and home access point150were associated together.

Because Wi-Fi networks are limited in their range, when user110moves to another location, client120has to disassociate with the known access point (operation306). For example, when user110leaves her home140to go to work, client120eventually moves out of range of home access point150. Additionally, client120may disassociate with home access point150regardless of location when user110shuts down or reboots client120.

By the end of the day, client120has traveled to other locations including locations141-142. Association mechanism204has associated the client with other access points such as known access points151-153. Scanning mechanism202has discovered other neighbors such as neighboring access points162-163. Many of these other access points lie on channels that differ from the channel used by home access point150. Because user110was at location141before reaching location140, client120last associated with station access point151.

In the example above, when user110returns to location140and powers up client120(operation308), scanning mechanism202immediately engages in a scanning process to find any known access points (operation310).

If scanning mechanism202is able to find a known access point, such as home access point150, during the scanning process, association mechanism204associates client120with the known access point (operation312).

Three-Stage Scanning Process

FIG. 4presents a flow chart that illustrates three stages in the process for finding Wi-Fi networks to associate with in accordance with an embodiment of the present invention.

There are up to 35 channels to scan for known access points. Database130typically remembers all access points and neighbors discovered by scanning mechanism202. If database130does not contain any known access points (decision400), then the scanning process may not work until user110manually associates client120with an access point (terminator410).

The scanning process has three stages. In the first stage, scanning mechanism202scans the channel used by the known access point that client120was most recently associated with (operation420). If scanning mechanism202discovers a known access point (decision401), association mechanism204associates client120with the known access point (terminator412). If scanning mechanism202fails to discover a known access point or a neighbor in that channel (decision401), client120proceeds to the next stage of the scanning process.

In the second stage, scanning mechanism202scans the remaining channels used by the n most recently associated known access points (operation421). If scanning mechanism202discovers a known access point in one of the channels (decision402), association mechanism204associates client120with the known access point (terminator412). If scanning mechanism202fails to discover a known access point or a neighbor in those n channels (decision402), client120proceeds to the next stage of the scanning process.

In the third stage, scanning mechanism202scans all remaining channels that were not scanned in stages one and two (operation422). If scanning mechanism202discovers a known access point (decision403), association mechanism204associates client120with the known access point (terminator412). If scanning mechanism202fails to discover a known access point in the remaining channels (decision403), client120concludes that no known access points are in range and falls back to another type of connection. Later on, client120may re-attempt to join a Wi-Fi network with each subsequent attempt occurring at various time intervals (terminator411). Note that the longer the client goes without finding a Wi-Fi network, the less frequent the client's searches for a Wi-Fi network are. Conversely, if the client detects a Wi-Fi network after a long period without detecting any Wi-Fi networks, the client may search for Wi-Fi networks more frequently for a period.

How Found Access Points are Used

FIG. 5presents a flow chart illustrating how the device uses found access points during the scanning process in accordance with an embodiment of the present invention. In each of the three stages, as scanning mechanism202scans the stage-specific group of channels (operation520), if a known access point is found (decision501), the device immediately stops the scanning process and associates with the known access point (terminator510). No more channels are scanned. No more stages are executed.

On the other hand, if scanning mechanism202finds an unknown access point (decision502), database mechanism206searches database130to determine whether the unknown access point matches a discovered neighbor (decision503). If there is a match, confidence mechanism208determines whether the matching neighbor possesses a certain confidence level (decision504). To do so, confidence mechanism208retrieves the value of the confidence attribute (the number of times the neighbor has appeared while client120and a known access point were associated). If that value is higher than a threshold value, the device becomes confident that client120is in close proximity to a known access point and proceeds to scan the known access point's channel.

Database mechanism206first retrieves the known access point that is neighbored by the matching neighbor and then extracts the known access point's channel from that entry. Scanning mechanism202then scans that channel (operation521). If scanning mechanism202finds the known access point (decision505), association mechanism204associates client120with the known access point (terminator510) and terminates the scanning process. Even if scanning mechanism202does not find the known access point immediately, scanning mechanism202continues to scan the known access point's channel more frequently than the other channels as it continues the scanning process.