Abstract:
A method and system for distributed roaming in a wireless mesh network are disclosed. Cells are able to track and predict a users movement throughout the network. The user&#39;s roaming profile is forwarded to predicted future cells before the user actually enters those cells. When the user enters a new cell, roaming is completed without communication to any other cells. Thus, handoff time is reduced and users may more seamlessly move throughout the network coverage area.

Description:
[0001]     The present application claims the benefit of and priority to U.S. Provisional Patent Application No. 60/630,267 entitled “Distributed Roaming Services For Mobile Users on Wireless Mesh Networks,” filed on Nov. 24, 2004, which is incorporated herein by reference. 
     
    
     FIELD OF THE INVENTION  
       [0002]     The field of the invention relates generally to wireless networks and more particularly to a method and system for distributed roaming services tailored for wireless mesh networks.  
       BACKGROUND  
       [0003]     Many wireless mesh networks have the following characteristics in common: highly dynamic, autonomous, peer-to-peer, multi-hop, limited bandwidth and computing power, etc. Wireless mesh networks are highly dynamic for two reasons. First, the routers themselves may move (e.g. in mobile or hybrid wireless mesh networks), generating quick response times to topological changes. Second, even if the routers themselves do not move (e.g. in fixed wireless mesh networks), the radio link qualities can change very quickly because of interference, geographical and environmental factors. Traditional routing protocols (e.g. OSPF, RIP), designed for wired infrastructures, cannot handle such quick changes in signal strength. Many of the ad hoc routing protocols (e.g. AODV) lack the ability to flexibly adapt to radio link quality changes.  
         [0004]     Wireless networks are becoming increasingly common in peoples&#39; lives. The most popular wireless networks to date are mobile phone networks. Such networks are typically broken down into a number of “cells,” as indicated by the term “cellular phone networks.” Each cell has a set of antennae that send and receive signals to and from cell phone users. Communication lines interconnect the cells to form a cellular network. A commonly-used communication line is a fiber optic line, though alternatives are widely accepted in the field.  
         [0005]     In a cellular network, when a user moves from one cell to another, their mobile phone call can continue communication only if a connection to one or more antennae is maintained. The process of transferring a user&#39;s connection from one cell to the next is called “roaming.” Roaming is essential to enable a user to stay connected while moving across different cells without dropping calls.  
         [0006]     Cellular networks are traditionally not built as “mesh,” but in some form of hierarchical topological. (e.g. a tree topology, or a set of trees) A mesh, on the other hand, is a network where every cell is virtually connected to every other cell in the network. An example of a mesh is a grid map or the Internet. A wireless mesh network consists of cells interconnected by wireless backhaul such that each cell is in virtual communication with every other cell. Wireless mesh networks can also have gateways connected to wired networks. With the popularity of IEEE 802.11 wireless devices, wireless mesh networks have become increasingly popular. An 802.11 mesh network can incorporate inexpensive and relatively low powered 802.11 devices (access points, routers, etc) to form a high throughput and reliable distributed network. The advantages of such a network are analogous to those in distributed PC networks, which generate enormous computing power beyond that obtained with independent PC&#39;s.  
         [0007]     Roaming is the process by which a user switches between cells in a wireless mesh network. In a large wireless mesh network capable of handling Voice-Over-IP (VoIP) traffic, a roaming solution needs to be scalable, reliable, and provide fast handoff between different cells. Such a roaming solution should scale to at least thousands of network cells, though the limit for future applications is unpredictable. The key to scalability is lower roaming overhead, reducing the burden on the system at each handoff. The wireless mesh network should also be resilient to cell failures in a way similar to the Internet. This resiliency requires the network to take full advantage of the connectivity across the entire mesh. At present, the latency needs to be less than 50 ms to be undetectable to VoIP users.  
         [0008]     Existing roaming solutions fall short of these requirements. Roaming solutions in mobile cellular networks cannot be applied because they require hierarchical tree-like topologies. A recent proposal termed “micro-mobility” utilizes solutions such as the Cellular IP and Hawaii protocols derived from cellular phone networks. Micro-mobility solutions are typically designed for a strictly hierarchical network. A hierarchical network introduces bottlenecks due to poor load balancing and is vulnerable to cell failure, among other problems. The main weakness of hierarchical networks, though, is the lack of scalability. Hierarchical networks require significant cache and exchange state information storage among duplicative cells in the system. The amount of information exchanged and maintained grows exponentially with the size of the network and with the amount of roaming activities among users. Thus, such a hierarchical network is not scalable, and becomes impracticable as the number of cells increases.  
         [0009]     Another prominent solution (and IEEE standard) on IP networks is called Mobile IP, created by the Internet Engineering Task Force. Mobile IP is scalable, but can suffer from long handoff latency due to the way it forwards data to a mobile user. Optimization techniques to reduce handoff latency require changes on client software, which could be a serious impediment to user adoption.  
         [0010]     Prior wireless mesh networks enable a user to switch between mesh routers. When a user device senses that a stronger signal is available than the one currently being used to access the network, a roaming process enables the device to switch to the stronger signal. To roam, the device must contact a cell, sometimes called a home agent, that contains the user&#39;s roaming profile. A home agent is typically a server, and resides somewhere within the entire network. To contact the home agent, the user device may have to travel long paths through a multitude of cells. Further, each time the user roams, the home agent must be contacted. This introduces long delays and signal degradation from the users end.  
       SUMMARY  
       [0011]     A method and system for distributed roaming in a wireless mesh network are disclosed. In one embodiment, a user&#39;s roaming profile is obtained from the permanent home agent prior to the user entering a new cell. The network is able to track a users movement across cells, and to predict the users next movement. The roaming profile is forwarded to one or more cells prior to the users movement into one of those cells. Once the user enters a new cell, the new cell completes the roaming process in communication with the old cell. This handoff is much quicker than communicating with the Permanent Home Agent.  
         [0012]     The above and other preferred features, including various novel details of implementation and combination of elements, will now be more particularly described with reference to the accompanying drawings and pointed out in the claims. It will be understood that the particular methods and systems described herein are shown by way of illustration only and not as limitations. As will be understood by those skilled in the art, the principles and features described herein may be employed in various and numerous embodiments without departing from the scope of the invention.  
     
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0013]     The accompanying drawings illustrate the preferred embodiment of the presently disclosed invention. Together with the Summary above and the Detailed Description of the Preferred Embodiment below, the drawings serve to explain and teach the principles of the present invention.  
         [0014]      FIG. 1  illustrates a block diagram of an exemplary wireless mesh network according to one embodiment of the present disclosure;  
         [0015]      FIG. 2  illustrates a block diagram of an exemplary wireless router according to one embodiment of the present disclosure;  
         [0016]      FIG. 3  illustrates roaming according to the present disclosure; and  
         [0017]      FIG. 4  is a flow chart of an exemplary process for roaming according to one embodiment of the present disclosure.  
     
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT  
       [0018]     In the following description, for purposes of explanation, specific nomenclature is set forth to provide a thorough understanding of the various inventive concepts disclosed herein. However, it will be apparent to one skilled in the art that these specific details are not required in order to practice the various inventive concepts disclosed herein.  
         [0019]     Some portions of the detailed descriptions that follow are presented in terms of wireless networks and computer systems. These wireless network descriptions and representations are the means used by those skilled in the wireless networking arts to most effectively convey the substance of their work to others skilled in the art. A wireless network is here, and generally, conceived to be a system for communications among two or more systems using radio waves as a transmission medium. Usually, though not necessarily, the information communicated between systems takes the form of packets of information. Furthermore, for reasons of common usage, the components of the packets are referred to as bits, values, elements, symbols, characters, terms, numbers, or the like.  
         [0020]     The present invention relates to an apparatus for performing the operations herein. This apparatus may be specially constructed for the required purposes, or it may comprise a general-purpose system selectively activated or reconfigured by a program stored in the system. Such a program may be stored in a computer readable storage medium, such as a disk drive, optical disk drive, CD-ROM, magnetic-optical disk drive, read-only memory, random access memory, EPROM, EEPROM, magnetic or optical cards, or any other type of media suitable for storing electronic instructions and coupled to a system bus.  
         [0021]     The methods presented herein are not inherently related to any particular system 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 required method steps. The required structure for a variety of these systems will appear from the description below. In addition, the present invention is 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.  
         [0022]     The present method and system for distributed roaming services includes an adaptive, distributed, proactive roaming solution designed for wireless mesh networks.  FIG. 1  illustrates an exemplary wireless mesh network according to one embodiment of the present invention. The mesh network  100  may be part of a wireless network and operate on a region such as neighborhood  110 . According to one embodiment, the neighborhood  110  is divided into a number of individual cells  120 , wherein each cell  120  includes none, one, or more than one subscriber  130  to the wireless mesh network  100 . A cell  120  may or may not encompass a subscriber  130  because a particular cell may be situated such that no subscribers  130  happen to be located within its area at any given moment. The network also contains one or more permanent home agents  160  for each user, which assist in roaming when the user roams from one cell into a new cell  120 .  
         [0023]     The physical boundaries of each cell  120  are only representational of a typical network. Each cell  120  is not necessarily the same size or shape as any other cell  120 , though each cell  120  is in communication with each of the cells  120  neighboring it. Thus, each particular cell  120  must have an overlapping border with all of its neighboring cells  120 .  
         [0024]     According to one embodiment, a subscriber  130  is a computer system authorized to access the wireless network  100 . A subscriber  130  must be situated within the network coverage area, and may be located anywhere within the area, such as: within a home, a car, an office, etc.  
         [0025]     In addition to a mesh network, it is to be appreciated that other systems employing the various teachings herein may also be used to practice the various aspects of the present invention, and as such are considered to be within its full scope.  
         [0026]     Each cell  120  includes at least one mesh router  140  that may be either fixed or mobile. A mesh router  140  communicates with exemplary subscribers  130 . According to one embodiment, the subscribers  130  have a subscriber account with the service provider to access mesh network  100  through a mesh router  140 . These subscribers  130  may include, for example, a wireless personal digital assistant (PDA), a wireless local area network (LAN) router, or a wireless laptop. Such devices with wireless network capabilities are well-known in the art, and are widely available at a number of consumer retailers. Although a wireless PDA, a wireless LAN router, and a wireless laptop are described, any device with wireless capability may be a subscriber.  
         [0027]     Mesh routers  140  can also serve as gateways to the Internet. According to one embodiment, mesh router/gateway  140  has at least one network interface, such as an ethernet controller, that is in communication with the Internet. This communication is via a communications link such as ethernet. In a mesh network  100 , multiple gateways may exist.  
         [0028]     The mesh network topology of  FIG. 1  may also include a network management server  150 . Network management server  150  may be connected to a mesh router  140  to access the Internet. According to one embodiment, the network management server  160  designates the channel assignments of all mesh routers  140  in the mesh network.  
         [0029]      FIG. 2  illustrates a block diagram of an exemplary mesh router  200  according to one embodiment of the present invention. In addition to accessing the wireless network, a mesh router  200  also allows subscribers to set up their own local area networks. Wireless router  200  may be a Wi-Fi router, as is well-known in the art and available at a number of consumer retailers. The mesh router  200  has a processor  210  connected to a power supply  220 , random access memory (RAM) module  230 , Ethernet controller  240 , and 802.11 controller  250 . The Ethernet controller  240  allows the processor  210  to communicate with Ethernet port(s)  260 . The 802.11 controller  250  allows the processor  210  to communicate with the 802.11 antennae  270 . RAM module  230  stores a routing table  231  used to route packets to and from mesh router  200 .  
         [0030]      FIG. 3  illustrates roaming according to the present disclosure where a user travels from old cell  310  to new cell  320 . Roaming occurs each time a user travels between different mesh router coverage areas.  FIG. 3  depicts the scenario where each cell  300  has one mesh router. However, a cell may have more than one mesh router. This discussion therefore applies equally to situations where a user travels within a single cell but between different mesh routers within that cell.  
         [0031]     A user may travel anywhere within the entire network coverage area, consisting of a multitude of cells  300 . Each time the user moves from an old cell  310  to a new cell  320 , the user device must roam. Instead of communicating each time with the dedicated permanent home agent  330 , according to one embodiment, a proxy home agent is used. While the user is in the old cell  310 , the old cell  310  requests portions of the user&#39;s roaming profile from the permanent home agent  330 . In this fashion, the old cell  310  becomes a proxy home agent because it contains information necessary for roaming, such as: authentication, user name, session id, password, etc.  
         [0032]     In  FIG. 3 , a mesh router  350  in old cell  310  has signal coverage area  315 , and a mesh router  360  in new cell  320  has signal coverage area  325 . When the user travels from old cell  310  to new cell  320 , there is a period of time where the user resides in the overlap area  340 . When the user is in this area, the client is seen by the routers in both old cell  310  and new cell  320 . The router  350  in new cell  320  pre-fetches the roaming profile information from the Proxy Home Agent, old cell  310 . This information is sufficient to complete roaming for the user if it leaves the overlap zone  340  and enters new cell  320 . Once the user enters new cell  320 , the new cell  320  requests portions of the roaming profile from permanent home agent  330  in preparation for the next roaming process, which is repeated when the user enters another overlap zone  340 .  
         [0033]     Roaming is initiated by a user device once it senses a stronger signal is available. This will occur only if a user enters new cell  320 . Thus, if a user enters the overlap area  340  between two cells  300  but does not enter a new cell  320 , roaming is never completed. According to one embodiment, new cell  320  may receive the roaming profile from old cell  310 .  
         [0034]      FIG. 3  depicts the overlap  340  between a single old cell  310  and a single new cell  320 . The teachings herein also apply where there is an overlap area containing more than two cells  300 . In the case that a user enters an overlap area of more than two cells  300 , the roaming profile is transferred from old cell  310  to all of the new cells  320 . Thus, regardless of which cell  320  the user enters, that new cell  320  will have the necessary roaming profile needed to complete roaming.  
         [0035]      FIG. 4  is a flow chart of an exemplary process for roaming according to one embodiment of the present disclosure. The chart walks through the steps required to handoff a user from an old cell A  310  to a new cell B  320 . The router in cell A  310  retrieves the user&#39;s roaming profile from the permanent home agent while the user is still in cell A  310  ( 400 ). Once that information is received, the router in cell A  310  becomes the proxy home agent. When a user enters the overlap area between old cell A  310  and new cell B  320 , each of the cells identify the user and the proxy home agent ( 410 ). The router in old cell A  310  transfers the user&#39;s roaming profile to the router in new cell B  320  in preparation for roaming ( 420 ) if the user leaves the overlap area between the cells and enters new cell B  320  ( 430 ). Once the user enters new cell B  320 , the router in new cell  320  B performs the roaming steps of connecting with the user device and releases the devices from old cell A  310  ( 44 ). Because the router in new cell B  320  already received the roaming profile from the proxy home agent, the router in new cell B  320  completes roaming without any communication to the permanent home agent. Once roaming is completed, the user communicates via new cell B  320 .  
         [0036]     Although the figure depicts a linear progression for a single roaming occurrence, the steps of  FIG. 4  are repeated each time a user enters a new cell.  
         [0037]     This disclosure has the benefit of tracking a user across different cells. Once a user enters a new cell, that new cell receives roaming profile information from the permanent home agent and it then becomes the proxy home agent. In this manner, it prepares for transfer of the roaming profile to any new cell that the user may travel into. The proxy home agent thus tracks the user, and changes at each roaming step. The proxy home agent is always in a neighboring cell to the present location of the user, and communication time between proxy home agent and any new cell is always a minimum.  
         [0038]     Each node in the network interfaces with layer  2  (or L 2 , i.e., Link and MAC layer), and layer  3  (or L 3 , i.e., IP layer). The present wireless mesh network may be compatible with IEEE/IETR standards on 802.11 f (IAPP), according to one embodiment. The interface to L 2  roaming (e.g., IEEE 802.11f) serves as the trigger for mobility events without intervention of client software. The distributed fashion of home agents, plus the ability to incrementally perform functions such as differential authentication, switching to new radio channel, and routing updates, make the fast handoff possible.  
         [0039]     Yet another feature of the present method and system is multi-level roaming. Multi-level roaming involves operations across OSI layer  2  (Link Layer/MAC), and layer  3  (IP). In one embodiment, local roaming among nodes on the same IP subnet is done on layer  2 . This has the advantages of fast roaming because all functions are on the same L 2  and does not involve L 3  (IP) layer.  
         [0040]     The present method and system has a number of benefits over typical roaming solutions in mesh networks. Because roaming is completed with communication between neighboring cells, or one hop, handoff latency is significantly reduced. Handoff time for VoIP traffic is below 50 ms. According to one embodiment, the system requires no change to a user&#39;s device. The present mesh network roaming system is also scalable because of the minimum amount of information transferred long distances during roaming.  
         [0041]     While the preferred embodiments of the invention have been described herein, it will be understood that those skilled in the art, both now and in the future, may make various improvements and enhancements which fall within the scope of the claims that follow. These claims should be construed to maintain the proper protection of the invention described herein.