Abstract:
A method is described comprising: defining a base station congestion condition; detecting that the congestion condition is met with respect to a first base station and allocating a wireless device to an alternate base station instead of the first base station in response to the congestion condition being met, as long as RSSI measured from the alternate base station is above a predetermined alternate base station threshold (“ABT”) value.

Description:
BACKGROUND 
     1. Field of the Invention 
     This invention relates generally to the field of wireless network protocols and processes. More particularly, the invention relates to an apparatus and method for reducing congestion on a wireless network. 
     2. Description of the Related Art 
     A variety of wireless data processing devices currently exist including standard cellular phones, cellular phones equipped with data processing capabilities, wireless personal digital assistants (“PDAs”) such as the Palm® VIIx handheld, and, more recently, corporate wireless messaging devices such as the Blackberry™ wireless pager developed by Research In Motion (“RIM”).™ 
     In operation, some of these wireless devices will attempt to lock on to a base station from which it receives the highest signal strength, commonly referred to as the Received Signal Strength Indication (“RSSI”). Referring to  FIG. 1 , the wireless device  120  will periodically evaluate the RSSI received from each of a plurality of surrounding base stations  110 - 112  and will generally select the base station having the highest RSSI value. Accordingly, a device in motion (e.g., in a car during a user&#39;s daily commute) will tend to jump from one base station to another based on the continually changing RSSI values. For example, if base station  110  is close to the user&#39;s home, the user&#39;s wireless device  120  may initially lock on to that base station  110  when the user leaves for work, based on the strength of the RSSI value (identified as “RSSI  1 ”). As the user commutes to work, however, the wireless device  120  may jump to a new base station  112  as the RSSI value received from that base station  112  (identified as RSSI  3 ) become greater than the initial RSSI value by some pre-defined margin. 
     Because each wireless device is programmed to select a base station based on RSSI, certain powerful ‘wide-area’ base stations located in highly populated areas may tend to become overloaded (e.g., such as those located near the intersection of several major freeways or high-rise office buildings). This can be so despite the addition of dedicated ‘campus’ bases, which don&#39;t always attract the localised devices they are meant to serve, due to their lower output power. This problem is graphically illustrated in  FIG. 2  which shows three coverage areas  210 ,  220 , and  230  associated with three base stations  211 ,  221 , and  231 , respectively. Area  240  falls within the coverage areas of all three base stations. However, if RSSI values within area  240  measured from base station  231  are higher than RSSI values measured from the other two base stations  211  and  221 , then wireless devices will tend to select base station  231  from within area  240 . If area  240  is significantly more populated than surrounding areas, this may cause base station  231  to become overloaded. In this situation, it would be desirable to reallocate a certain number of devices to the alternate base stations  211  and  221 . 
     Accordingly, what is needed is an improved base station selection algorithm for a wireless device. What is also needed is a selection algorithm which will factor in variables other than RSSI when making base station selection decisions (e.g., such as the current load on each base station). 
     SUMMARY  
     A method is described comprising: defining a base station congestion condition; detecting that the congestion condition is met with respect to a first base station and allocating a wireless device to an alternate base station instead of the first base station in response to the congestion condition being met, as long as RSSI measured from the alternate base station is above a predetermined alternate base station threshold (“ABT”) value. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       A better understanding of the present invention can be obtained from the following detailed description in conjunction with the following drawings, in which: 
         FIG. 1  illustrates base station roaming techniques based on RSSI values. 
         FIG. 2  illustrates a coverage area serviced by three different base stations on a wireless network. 
         FIG. 3  illustrates a wireless device architecture according to one embodiment of the invention. 
         FIG. 4  illustrates base station selection logic according to one embodiment of the invention. 
         FIG. 5  illustrates a base station selection process according to one embodiment of the invention. 
     
    
    
     DETAILED DESCRIPTION  
     In the following description, for the purposes of explanation, numerous specific details are set forth in order to provide a thorough understanding of the present invention. It will be apparent, however, to one skilled in the art that the present invention may be practiced without some of these specific details. In other instances, well-known structures and devices are shown in block diagram form to avoid obscuring the underlying principles of the present invention. 
     An Exemplary Device Architecture 
     An exemplary wireless device architecture  300  on which embodiments of the invention are implemented is illustrated in  FIG. 3 . As illustrated, this embodiment is comprised generally of a Host subsystem  301  and an RF subsystem  302  which communicate via an interface  330 . The Host subsystem  301  is comprised of a Host processor and memory  335  for executing program code and operating on data. For example, in one embodiment, the processor and memory  335  are responsible for running the wireless device&#39;s operating system, user interface and/or any applicators installed on the device. In one embodiment, the Host processor is comprised of an ARM® core micro-controller (e.g., such as the L7210 from Linkup Systems which uses an ARM720T core). However, various other processors may be employed while still complying with the underlying principles of the invention. One embodiment of the Host subsystem  301  may also include a non-volatile memory (not shown), such as an EEPROM or Flash memory, for storing program code and data when the device is powered off. 
     As indicated in  FIG. 3 , the Host subsystem  301  may also include a power supply/charger unit  340  and various I/O and/or user interface elements  350  (e.g., an LCD display, a keypad, a USB port, an IrDA port, to name a few). 
     The RF subsystem  302  is responsible for transmitting and receiving data over the wireless network  271 . Accordingly, one embodiment of the RF subsystem  302  is comprised of a baseband processor and memory  320  for implementing a particular network protocol supported by the network  271  (e.g., such as the Mobitex protocol). In one embodiment, the baseband processor  320  is comprised of base station selection logic for implementing the advanced base station selection techniques described herein. In one embodiment, the baseband processor core is the Z183 micro-controller manufactured by Zilog, Inc. However, the underlying principles of the invention are not limited to any particular baseband processor. In addition, although illustrated above as a dual processor system, the underlying principles of the invention may also be implemented on a single processor architecture. The data pump  325  of one embodiment encodes/decode the transmitted/received signal according to the particular modulation techniques employed by the radio transceiver  310 . 
     Embodiments of the Invention 
     In one embodiment of the invention, the base station selection logic  321  evaluates the approximate traffic load on the base station it is operating on in addition to the RSSI of the surrounding bases when determining which base station to select. As illustrated in  FIG. 4 , in one embodiment, the base station selection logic is comprised of congestion detection logic  410  to evaluate and identify congestion conditions, and anti-congestion logic  420  to employ the anti-congestion techniques described herein. This embodiment will be described with reference to the base station selection process outlined in  FIG. 5 . 
     At  500 , the congestion detection logic  410  evaluates base station usage data  405  to determine whether a particular base station is congested. In one embodiment, “congestion” is declared when the number of wireless devices serviced by a particular base station averaged over a period of time exceeds a predetermined threshold value. Various techniques may be employed to detect probable congestion including determining (or at least approximating) the amount or volume of traffic in either direction to or from the base, traffic routing delays or the number of wireless devices for which there is pending traffic on a base station. In a Mobitex network, for example, wireless devices maintain network contact by periodically listening for a synchronization packet which (among other things) contains a variable referred to as “TrafNum” which indicates the number of wireless devices operating in Battery Savings mode which the base intends to send packets to within the next cycle (e.g., 10 seconds). In one embodiment, a base station is considered “congested” if the Trafnum value is above a specified threshold. Alternatively, in one embodiment, if the average TrafNum value, averaged over the last ‘z’ TrafNum values received, exceeds a specified value, ‘y,’ the congestion detection logic  410  indicates a congestion condition. Various alternate criteria for defining a congestion condition may be employed while still complying with the underlying principles of the invention. 
     The congestion detection logic  410  notifies the anti-congestion logic  420  of a detected congestion condition if one exists (determined at  505 ). In response, the anti-congestion logic  420  attempts to locate an alternate base station having an RSSI value above some minimum threshold value, referred to herein as the “Alternate Base Threshold” or “ABT.” At  510 , one or more prospective alternate base stations are identified. In one embodiment, the initial prospective alternate base station is the one with the strongest initial RSSI value. At  515 , the anti-congestion logic  420  initializes the ABT value. In one embodiment, the initial ABT value is 49 dBuV; however, the principles of the invention are not limited to any particular initial or subsequent ABT values. 
     One purpose of the ABT is to ensure that devices with the best alternate neighbors roam off the congested base before devices that have poorer neighbors. For example, given the option, it would be preferred that a device with a neighbor whose RSSI is 45 dBuV roams off the congested base to that neighbor before a device whose best neighbor is only 35 dBuV. It also ensures that devices remain on the congested base if that is the only workable base they can see and/or they have very poor neighbors. This keeps the fleet as optimally distributed as possible and prevents excess roaming. 
     At  520 , the anti-congestion logic  420  compares the ABT with the RSSI value read from the prospective base station. In one embodiment, if the RSSI of the prospective base station exceeds the ABT, the wireless device roams to that base station (at  530 ). In one embodiment, the wireless device switches to the new base station after a random timeout between immediately and 75% of the time until when the wireless device is next scheduled to receive a synchronization packet (known as “SVP6” on a Mobitex network). Switching to the new base station only after a random timeout prevents a significant number of wireless devices from switching to the new base station at the exact same moment and potentially overloading the new base station. 
     In one embodiment, the wireless device cancels the anti-congestion roam if it happened to be addressed in the Traffic or Mail Lists of the last synchronization packet it received, or if the Host subsystem has data for the RF subsystem to send to the network. In other words, only when the device would have otherwise entered and stayed in standby mode does it schedule the anti-congestion roam. 
     In one embodiment, if the RSSI of the prospective base station does not exceed the ABT (determined at  520 ), then the anti-congestion logic  420  decreases the ABT by a specified amount (at  525 ). In one embodiment, the anti-congestion logic  420  initially decrements the ABT relatively quickly (e.g., each time the wireless device receives a synchronization packet), because it is not likely that many devices will have neighbors with extremely high RSSI. Once the ABT reaches certain specified values, the anti-congestion logic  420  then decrements the ABT at intervals further and further apart. As the ABT gets lower and lower more and more devices will find themselves with neighbors whose RSSI exceeds the ABT. Slowing down the lowering of ABT prevents a mass exodus of the congested base and allows time for the system to settle down gracefully. 
     For example, in one embodiment, the anti-congestion logic  420  decreases the ABT by 1 at each synchronization point from 49 dBuV until it reaches 45 dBuV. When the ABT reaches 45 dBuV the anti-congestion logic  420  decrements it every ‘a’ minutes until it reaches 40 dBuV. When the ABT reaches 40 dBuV the anti-congestion logic  420  decrements it every ‘b’ minutes until it reaches 35 dBuV. When the ABT reaches 35 dBuV the anti-congestion logic  420  decrements it every ‘c’ minutes until it reaches 30 dBuV (and so on). In one embodiment, the ABT is not reduced below 30 dBuV. 
     In one embodiment, if the wireless device roams to the prospective base station (at  530 ), the congested base station is added to a “Congestion List” maintained on the wireless device (e.g., stored in the baseband processor memory). The wireless device will not attempt to roam to any channel which is on the Congestion List, during either normal or quick channel monitoring. Maintaining a Congestion List in this manner will prevent large groups of devices from continually jumping back and forth between congested and not-congested base stations. 
     List maintenance may be performed to ensure that the Congestion List is up-to-date. For example, in one embodiment, a base station entry remains in the congestion list for as long as its channel is detectable by the wireless device (i.e., as long as it is present in the “Neighbor List” of available surrounding bases (sent by the network to the wireless device). Once the wireless device receives a Neighbor List without that channel, the channel is to remain in the Congestion List for a further ‘t’ minutes. If the ‘t’ minutes expires and the channel is still absent from the congestion List, it is removed from the Congestion List. If the channel reappears in the Neighbor List while the ‘t’ minute timer is running, the timer is cancelled and not re-started until the channel disappears from the Neighbor List again. In one embodiment, the Congestion List is preserved across power cycles. It is cleared after two full passes of all channels during quick channel monitoring (the Mobitex term for looking for bases while out of coverage). 
     The purpose of linking the Neighbor List to the Congestion List as described above is to prevent a channel from remaining off limits when that would not be appropriate. For spectrum efficiency, base station channels (frequencies) are reused in different geographical areas. If the device travels far enough away from the neighborhood containing the congested base, the device may find itself in an area using the same channel as that of the congested base. If that channel was not removed from the Congestion List the device would be uneccessarily restricting it&#39;s available coverage options. 
     One embodiment of the Congestion List allows up to 4 entries. In one embodiment, if the list is full the oldest entry is overwritten. 
     When average number of devices (identified by “TrafNum” on a Mobitex network) falls below the predetermined threshold value, ‘x’ the anti-congestion algorithm is disabled. 
     In one embodiment, if any UPFREQ FBI values in the Neighbor List are non-zero, the algorithm is disabled. That is, in this embodiment, Priority Roaming (a feature of Mobitex) and Anti-Congestion Roaming are mutually exclusive. 
     Embodiments of the invention may include various steps as set forth above. The steps may be embodied in machine-executable instructions. The instructions can be used to cause a general-purpose or special-purpose processor to perform certain steps. Alternatively, these steps may be performed by specific hardware components that contain hardwired logic for performing the steps, or by any combination of programmed computer components and custom hardware components. 
     Elements of the present invention may also be provided as a machine-readable medium for storing the machine-executable instructions. The machine-readable medium may include, but is not limited to, floppy diskettes, optical disks, CD-ROMs, and magneto-optical disks, ROMs, RAMs, EPROMs, EEPROMs, magnetic or optical cards, propagation media or other type of media/machine-readable medium suitable for storing electronic instructions. For example, the present invention may be downloaded as a computer program which may be transferred from a remote computer (e.g., a server) to a requesting computer (e.g., a client) by way of data signals embodied in a carrier wave or other propagation medium via a communication link (e.g., a modem or network connection). 
     Throughout the foregoing description, for the purposes of explanation, numerous specific details were set forth in order to provide a thorough understanding of the invention. It will be apparent, however, to one skilled in the art that the invention may be practiced without some of these specific details. For example, while described above in the context of the Mobitex protocol, the underlying principles of the invention may be implemented on virtually any wireless network. 
     It is also important to note that the apparatus and method described herein may be implemented in environments other than a physical integrated circuit (“IC”). For example, the circuitry may be incorporated into a format or machine-readable medium for use within a software tool for designing a semiconductor IC. Examples of such formats and/or media include, but are not limited to, computer readable media having a VHSIC Hardware Description Language (“VHDL”) description, a Register Transfer Level (“RTL”) netlist, and/or a GDSII description with suitable information corresponding to the described apparatus and method. 
     Accordingly, the scope and spirit of the invention should be judged in terms of the claims which follow.