1Improving the Latency of 802.11 hand-offs usingNeighbor GraphsMinho Shin, Arunesh Mishra, William A. Arbaugh{mhshin, arunesh, waa}@cs.umd.eduDepartment of Computer ScienceUniversity of MarylandCollege Park, Maryland 20742, USAAbstract—The 802.11 IEEE Standard has enabled low cost andeffective wireless LAN services (WLAN). With the sales and de-ployment of WLAN based networks exploding, many people be-lieve that they will become the fourth generation cellular system(4G) or a major portion of it. However, the small cell size ofWLAN creates frequent hand-offs for mobile users. If the latencyof these hand-offs is high, as previous studies have shown, then theusers of synchronous multimedia applications such as voice overIP (VoIP) will experience excessive jitter. The dominating factorin WLAN hand-offshas beenshown to be the discovery of the can-didate set of next access points. In this paper, we describe the useof a novel and efficient discovery method using neighbor graphsand non-overlap graphs. Our method reduces the total number ofprobed channels as well as the total time spent waiting on eachchannel. Our implementation results show that this approach re-duces the overall probe time significantly when compared to otherapproaches. Furthermore, simulation results show that the effec-tivenessof our method improves as the number of non-overlappingchannels increases, such as in the 5 GHz band used by the IEEE802.11a standard.I. INTRODUCTIONThe 802.11 IEEE Standard [1] enables low cost and effec-tive wireless LAN services. The unlicensed and free spectrum(2.4GHz in 802.11b/g and 5GHz in 802.11a) used by 802.11networks permits the deployment of high speed (11Mbps in802.11b and up to 54 Mbps for 802.11g/a)by organizations [2].Furthermore, the major laptop and handheld computer vendorsare quickly integrating WLAN devices into their equipment.This rapid adoption makes many people believethat 802.11 willbecome the fourth generation cellular system (4G) or a majorportion of it. In fact, WLANs in public areas such as airports,hotels, universities [3] [4] and shopping centers [5] havealreadybeen successfully deployed. To meet this lofty goal of becom-ing the next generation cellular system, the hand-offs that occurwhen a user is mobile must be efficient.The small cell size in WLAN creates frequent hand-offs po-tentially causing delays or disruption of communications if thelatency of the hand-off is high. A major component of the hand-off process is identifying the new best available access point(AP) and associating to that AP (layer-2 hand-off). When IPconnectivity is used, the additional process of layer-3 hand-offmust also be completed [6].Mobility and voice communications are the driving forcesin current cellular networks, and the efficiency of both areparamount to the success of a new generation of cellular ser-vice. Due to the high bandwidth provided by 802.11 networks,Voice over IP (VoIP) is the logical choice for providing voiceservice. VoIP, however, requires a maximum end-to-end delayof 50ms [7][8]. Unfortunately, previous studies have shownthat the majority of WLANs cannot complete the layer- 2 hand-off process in 100 ms [9] [6] [10]. One study [9] found that theobserved layer 2 hand-off latencies are from 60ms to 400ms(252ms on average) depending on the vendorsof wireless cardsand access points, and that the probe phase (the discovery ofnext AP) is a dominating factor in layer 2 hand-off latency, ac-counting for more than 90% of the overall cost [9].In active scanning1, the probing latency is affected signifi-cantly by two parameters: the probe count and the probe-waittime[9]. The probe count equals the numberof channels probedby the station and the probe-wait time is the time spent by thestation waiting for probe responses probed access points. Inthis paper, a station is a 802.11 mobile device, following theconvention in IEEE standard. Since the 802.11 IEEE Stan-dard does not specify a method for probing channels, wirelessvendors use their own, usually proprietary, algorithms basedon heuristics [9]. We categorize these proprietary algorithmsas Full-Scanning and Observed-Scanning. Full-scanning is abrute force algorithm that probes all the legitimate channels (11channels in US [11]). Observed-scanning, on the other hand,limits probes to a subset of legitimate channels observedby pre-vious probings [12]. The main benefit of observed-scanningover full-scanning is more easily seen by understanding howchannel management usually occurs. In the U.S., there arethree non-overlapping or independent channels (1, 6, and 11).The exclusive use of these channels prevents interference be-tween adjacent channels. Thus in a network using only thenon-overlappingchannels, observed-scanning needs to probe atmost three channels instead of 11. Observed-scanning, how-ever, does not work well when the number of non-overlappingchannels is high as in the 802.11a standard which has 12 non-overlapping channels.1In this paper, we consider only active scanning, where the station broad-casts probe-request messages on interested channels. The alternative method,passive scanning may also be used for improving handoff latency by listeningto beacons during idle time. But when AP discovery is required, there is noguarantee that the station can get the list of APs on time.2In this paper, we propose two innovative and efficient layer-2 hand-off schemes, NG algorithm and NG-pruning algo-rithm. The NG algorithm uses the neighbor graph data struc-ture (NG) [13]. The NG-pruning algorithm further improvesthe discovery process by also using the non-overlap graph datastructure.The neighbor graph is a data structure that abstracts the hand-off relationships between access points. An access point, AP1has a handoff relationship with AP2(from AP1to AP2) if andonly if a station can hand-off from AP1to AP2. AP2is thensaid to be a neighbor of AP1. The neighbor graph captures thefollowing information :1) The set of channelson which neighborAPs are operating.2) The set of neighbor APs on each of such channels.Using the above information, the station can avoid probingunnecessary channels and spending time waiting for responsesfrom non-existing APs.The non-overlap graph is a data structure that abstracts thenon-overlappingrelationships between APs. Two APs are non-overlappingif and only if a mobile station cannot communicatewith both of them with acceptable link quality. When two APsare non-overlapping, a probe response from one of