Program for ascertaining a dynamic attribute of a system Number:7,155,169 from the United States Patent and Trademark Office (PTO) owispatent The performance and ease of management of wireless communications environments is improved by a mechanism that enables access points (APs) to perform automatic channel selection. A wireless network can therefore include multiple APs, each of which will automatically choose a channel such that channel usage is optimized. Furthermore, APs can perform automatic power adjustment so that multiple APs can operate on the same channel while minimizing interference with each other. Wireless stations are load balanced across APs so that user bandwidth is optimized. A movement detection scheme provides seamless roaming of stations between APs.<H ascertaining, attribute, Program, for, asc, 7155169.html, Patent, pto, 7155169

Title: Program for ascertaining a dynamic attribute of a system

Abstract: The performance and ease of management of wireless communications environments is improved by a mechanism that enables access points (APs) to perform automatic channel selection. A wireless network can therefore include multiple APs, each of which will automatically choose a channel such that channel usage is optimized. Furthermore, APs can perform automatic power adjustment so that multiple APs can operate on the same channel while minimizing interference with each other. Wireless stations are load balanced across APs so that user bandwidth is optimized. A movement detection scheme provides seamless roaming of stations between APs.

Patent Number: 7,155,169 Issued on 12/26/2006 to Hawe

Inventors: Hawe; William (Hollis, NH)
Assignee: Autocell Laboratories, Inc. (Acton, MA)

Appl. No.: 10/781,013

Filed: February 18, 2004

Current U.S. Class: 455/67.11 ; 455/441; 455/446

Current International Class: H04B 17/00 (20060101)

Field of Search: 455/67.11,446,441

References Cited [Referenced By]

U.S. Patent Documents


5493694	February 1996	Vlcek et al.
5606727	February 1997	Ueda
5963848	October 1999	D'Avello
6111867	August 2000	Mann et al.
6198924	March 2001	Ishii et al.
6208629	March 2001	Jaszewski et al.
6215779	April 2001	Bender
6266537	July 2001	Kashitani et al.
6332007	December 2001	Sasaki
6522881	February 2003	Feder
6560462	May 2003	Ravi et al.
6574474	June 2003	Nielsen
6574477	June 2003	Rathunde
6636737	October 2003	Hills
6732163	May 2004	Halasz
6738599	May 2004	Black
6741863	May 2004	Chiang et al.
6760748	July 2004	Hakim
6795407	September 2004	Chesson
6870815	March 2005	McFarland et al.
2002/0042268	April 2002	Cotanis
2002/0060995	May 2002	Cervello et al.
2002/0141375	October 2002	Choi
2002/0176437	November 2002	Busch et al.
2002/0193113	December 2002	Shibutani
2003/0002456	January 2003	Soomro et al.
2003/0022686	January 2003	Soomro et al.
2003/0207699	November 2003	Shpak
2004/0054767	March 2004	Karaoguz et al.
2004/0137915	July 2004	Diener et al.
2004/0166849	August 2004	Hawe

Other References

IEEE, Wireless LAN Mediumj Access Control (MAC) and Physical Layer (PHY) specifications, Standard 802.11, 1999 edition, Reference No. ISO/IEC 8802-11:1999(E), 528 Pages. no month listed. cited by other .
Michael Barr, "Toward a Smaller Java", Embedded.com, Jun. 14, 2002, pp. 1-9. cited by other .
Moustafa Youssef, "Handling Samples Correlation in the Horus System", IEEE INFOCOM 2004, no month listed. cited by other .
Kin K. Leung, "Integrated Link Adaptation and Power Control for Wireless IP Networks", AT&T Labs--research, Jan. 19, 2000. cited by other .
Ana Zapater et al., "Development and Implementation of a Bluetooth Networking Infrastructure for the a Notebook--University Scenario", Institute of Communications Engineering, University of Hannover, May 13, 2003. cited by other .
Walter Klotz, "Graph Coloring Algorithms", 1999, no month listed. cited by other .
Brent N. Chun et al., "Market-based Proportional esource Sharing for Clusters", University of California at Berkeley computer Science Division, Sep. 1999. cited by other .
The Four Color Theorem, Web page, author(s) unknown, updated Nov. 13, 1995. cited by other.

Primary Examiner: Feild; Joseph
Assistant Examiner: Holliday; Jaime
Attorney, Agent or Firm: McGuinness & Manaras LLP

Claims

I claim:

1. A program product for ascertaining a dynamic attribute of a wireless communications system, the program product comprising a computer readable medium having embodied therein a computer program for storing data, the computer program comprising: logic for selecting a variable, the value of which is related to the dynamic attribute to be ascertained; logic for ascertaining the standard deviation around the true mean of the variable; logic for choosing an allowable range for the true mean; logic for choosing a confidence interval; logic for calculating the number N.sub.1 of samples of the variable that need to be taken so that the confidence interval of the calculated variable is less than the allowable range; logic for setting a sliding window to collect N.sub.1 samples of the variable as a short term average; logic for calculating the number N.sub.2 of samples of the variable that need to be taken to minimize the confidence interval of the calculated variable to a pre-determined amount; logic for collecting at least N.sub.2 samples of the variable as a long term average; logic for calculating the absolute difference between the long term average and the short term average; logic operable so that, if the difference is greater than the allowable range, indicating that the dynamic system attribute has been positively identified; logic operable so that, if the difference is less than the allowable range, continuing to add to the number samples of the variable for the long term average and continuing to update the sliding window for the short term average.

2. The program product of claim 1 wherein the system is a wireless network and wherein the system characteristic is whether a user of the wireless network is moving, or has moved.

3. The program product of claim 2 wherein the variable is signal strength received by the wireless user.

Description

FIELD OF THE INVENTION

The invention relates generally to wireless networks, and more particularly to wireless network configuration and power level adjustment for network performance optimization.

BACKGROUND OF THE INVENTION

The proliferation of laptop and hand-held portable computers has produced a concomitant need for robust, reliable, and high performance wireless networks to maximize the mobility advantages of these devices and increase the ease of construction and management of these wireless networks. Current wireless networks, such as IEEE 802.11b, 802.11a, 802.11g, (etc) networks, are subject to certain limitations that can limit a mobile user's network performance and reliability. For instance, only a very limited number of radio channels are available. In the current state of the art, wireless access points cannot effectively share the same channel in the same area because of radio and control protocol interference. So, bandwidth over a given area is limited by the number of non-overlapping channels available. Also, current wireless networks require manual site engineering to control the placement of access points and channel distribution between access points, raising the cost and complexity of the wireless network installation process. Furthermore, user roaming between wireless access points is inconsistent. Once associated with an access point, a user will tend to remain associated with that access point even if another access point is capable of providing higher performance for the user. It would be desirable to provide wireless networking solutions which overcome the above described inadequacies and shortcomings of current wireless networks.

SUMMARY OF THE INVENTION

In accordance with the principles of the invention, various apparatus, methods, and computer program products are provided to improve the performance and ease of management of wireless communications environments. For example, a mechanism is provided to enable access points (APs) to perform automatic channel selection. A wireless network can therefore include multiple APs, each of which will automatically choose a channel such that channel usage is optimized. Furthermore, APs can perform automatic power adjustment so that multiple APs can operate on the same channel while minimizing interference with each other. Further aspects of the invention are used to cause load balancing of stations across APs so that user bandwidth is optimized. Novel movement detection schemes provide seamless roaming of stations between APs. These and further aspects of the invention enable the provision of automatically configurable, high performance wireless communications environments.

BRIEF DESCRIPTION OF THE DRAWINGS

FIG. 1 shows a wireless communications environment in which wireless users interact with other networked devices via an access point (AP).

FIG. 2 shows a wireless network in which wireless user devices, or stations (STAs), access the wireless network via an access point and share the available network bandwidth.

FIG. 3 shows a wireless network wherein the stations access the network via two separate access points.

FIG. 4 is a flow diagram representing how an AP builds a channel map for use in an automatic channel selection scheme.

FIG. 5 is a flow diagram representing an automatic channel selection method.

FIG. 6 is a representation of a table kept by APs for use in an alternate channel selection scheme.

FIG. 7 is a flow diagram representing an alternate automatic channel selection scheme.

FIGS. 8A and 8B are flow diagrams representing a preferred embodiment of an automatic channel selection scheme.

FIG. 9 is a representation of a Scan Table kept by APs for use in the automatic channel selection scheme of FIG. 8.

FIG. 10 is a representation of a Channel Map kept by APs for use in the automatic channel selection scheme of FIG. 8.

FIG. 11 is a representation of a Triplet Channel Map kept by APs for use in the automatic channel selection scheme of FIG. 8.

FIG. 12 is a representation of a Claim APs table kept by APs for use in the automatic channel selection scheme of FIG. 8.

FIG. 13 is a flow diagram showing how an AP builds an AP KnownAPs table.

FIG. 14 is an example of an AP KnownAPs table maintained by an AP, and used for power adjustment.

FIG. 15 is a flow diagram representing the process by which an AP builds an AP AssociatedSTA table, for use in load balancing.

FIG. 16 is an example of an AP AssociatedSTA table.

FIG. 17 is a block diagram representing a general mechanism by which an AP adjusts its transmit power backoff.

FIGS. 18A and 18B are block diagrams representing a preferred embodiment of the transmit power backoff mechanism of FIG. 13.

FIG. 19 is a table showing expected standard errors related to number of power level samples.

FIG. 20 is a flow diagram representing the process by which an AP adjusts its transmit power backoff during STA movement.

FIG. 21 is a flow diagram representing an AP auction process, used for load balancing of STAs across APs.

FIG. 22 is a flow diagram representing the AP's handling of bids during the auction.

FIG. 23 is a flow diagram representing the STA initialization process.

FIG. 24 is a flow diagram representing a general mechanism by which a STA in a wireless communications environment canvasses channels.

FIG. 25 is a flow diagram representing the preferred embodiment of FIG. 20 as implemented in an 802.11 wireless networking environment.

FIG. 26 is an example of a STA Known APs table, used by STAs for power adjustment and load balancing.

FIG. 27 is a flow diagram representing the process by which the STA Known APs table is built by a STA.

FIG. 28 is a flow diagram representing the STA power adjustment process.

FIG. 29 is a flow diagram representing the STA Bidding process.

FIG. 30 is a flow diagram representing the process by which a STA calculates corrected distances for use in determining whether to bid for an AP.

FIG. 31 is an example of a distance_to_rate table for use in an 802.11 wireless networking environment.

FIG. 32 is an example of a rate_to_load table for use in an 802.11 wireless networking environment.

FIGS. 33A and 33B are flow diagram representing the STA Bidding process in more detail.

FIG. 34 is a flow diagram representing the process by which a STA detects its own movement.

FIG. 35 is a block diagram showing the software architectures of APs and STAs.

FIG. 36 is a more detailed block diagram of the software architecture of an AP implementing the invention in an 802.11 wireless networking environment.

FIG. 37 is a more detailed block diagram of the software architecture of a STA implementing the invention in an 802.11 wireless networking environment.

FIG. 38 represents the encoding of a DRCP (Dynamic Radio Control Protocol) message in an 802.11 beacon frame.

FIG. 39 represents the encoding of a DRCP message in an 802.11 data frame.

FIG. 40 is a table summarizing the DRCP messages used in the various aspects of the invention.

FIG. 41 is a table describing the various fields used in DRCP messages.

FIG. 42 is a diagram of the message format of a DRCP Preclaim message.

FIG. 43 is a diagram of the message format of a DRCP Claim message.

FIG. 44 is a diagram of the message format of a DRCP Announce message.

FIG. 45 is a diagram of the message format of a DRCP Bid message.

FIG. 46 is a diagram of the message format of a DRCP Accept message.

FIG. 47 is a diagram of the message format of a DRCP Registration Request message.

FIG. 48 is a diagram of the message format of a DRCP Registration Acknowledge message.

FIG. 49 is a graph showing discrete measurements of received power over time from the perspective of a wireless network user.

FIG. 50 is a graph showing discrete measurements of received power over time from the perspective of a wireless network user, and showing the estimated average received power for the user within a 99% confidence interval.

FIG. 51 is a graph similar to FIG. 3 showing two different estimated average received power measurements for small sample sizes and their 99% confidence intervals.

FIG. 52 is a graph showing two different estimated average received power measurements and their 99% confidence intervals, one for a large sample size and one for a small sample size.

FIG. 53 is a graph showing a long term average measurement and a short term average measurement with 99% confidence interval, the comparison showing that it can be determined that a user has moved.

FIG. 54 is a table showing the number of samples that need to be taken in order to cause the long term average confidence interval range to converge toward zero.

FIG. 55 is a flow diagram of the general operation of the method of the invention.

FIG. 56 is a block diagram of an embodiment of a wireless network in which the invention is deployed, wherein an AP ascertains that a user has moved.

FIG. 57 is a block diagram of an alternate embodiment of the invention, wherein a user ascertains that the user has moved.

FIG. 58 is a block diagram of one embodiment of the invention employing ring buffers.

FIG. 59 is a block diagram of an alternate embodiment of the invention employing batched means.

DETAILED DESCRIPTION OF EXEMPLARY EMBODIMENTS

In accordance with the present invention, a fully automatic control system is provided for wireless communications environments. Referring to FIG. 1, a typical wireless communications environment 10 includes access devices 12 (one shown) that interface between a wired communications medium 14 and wireless devices 16 to provide network access to the wireless devices 16. Wireless devices 16 can thus communicate with wired devices 18 and with each other via the access device 12. These access devices 12 are referred to by various names depending upon the wireless architecture employed, and are herein referred to as "access points" or "APs". The wireless devices 16 also have various architecture dependent names and are herein referred to as "stations" or STAs. A wireless communications capable device may be an AP, or a STA, or both.

Various types of wireless communications environments 10 exist. Wireless communications environments include for example wireless data networks and wireless I/O channels. An example of a wireless data network is described in "IEEE Standard for Information technology--Telecommunications and information exchange between systems--Local and metropolitan area networks--Specific requirements--Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) specifications--Amendment 1: High-speed Physical Layer in the 5 GHz band", incorporated herein by reference(hereinafter "802.11"). Furthermore, various different 802.11 "modes" are defined. For example, in IEEE 802.11 compatible wireless networks, wireless devices may be arranged in an "infrastructure mode", whereby the network is configured such that STAs 16 communicate with other network devices via an AP 12, as shown in FIG. 1. 802.11 compatible devices may also be arranged in "ad-hoc" mode, whereby all the STAs 16 are within transmission range and can communicate directly with each other. Furthermore, wireless "mesh" technologies exist, whereby each wireless device acts as both an AP and a STA. Wireless I/O channels can be used to provide I/O communications, for example, between servers and storage devices via the "Bluetooth" Standard, or between home entertainment audio and video components, or between wireless telephone handsets and base stations. The various aspects of the invention apply to generally to wireless networking architectures, including those used in wide area networks, metropolitan area networks, enterprise networks, and home networks, and wireless I/O channel architectures, as they exist now and as they are developed.

According to aspects of the invention, an arbitrary number of wireless access points (APs) can be placed in arbitrary positions, and all APs and STAs will automatically configure themselves for optimal channel usage, power levels, and STA/AP associations. So, in a wireless networking environment, channel usage is optimized while interference between APs is minimized. Wireless devices such as wireless enabled laptops or hand-held computing devices or Internet protocol telephones, are transparently and seamlessly distributed between APs such that network performance is optimized from the perspective of the user of the wireless device. And, in a wireless I/O channel environment that might be employed for example in a home, audio, video, and other appliances may be moved without performance degradation, and channel usage for each appliance may be optimized so that the appliances do not interfere with each other.

In order to expedite the understanding of the invention, certain examples will be described as they apply to the relatively well known 802.11 wireless LAN architecture, with the understanding that the principles of the invention apply more generally to any wireless communications environment. A preferred implementation of the inventive principles will then be described as embodied in an 802.11 wireless network

The following aspects of the invention contribute to its advantages, and each will be described in detail below. 1. AP Initialization: In many wireless communications environments, multiple frequencies ("channels") are available for use by APs. For example, in accordance with 802.11b and 802.11g, 3 non-overlapping channels are available. In accordance with IEEE 802.11a, 13 non-overlapping channels are available. In an environment where multiple APs are employed, it will be seen that it is advantageous for the APs to use different channels to optimize performance and minimize interference. In accordance with the invention, APs perform automatic channel selection. Where multiple APs are distributed in a given area, the APs execute a distributed protocol to pick channels for each AP. APs close to each other use non-overlapping channels. 1. AP Optimization: a. Power Adjustment: When the number of APs in a wireless communications environment exceeds the number of non-overlapping channels, APs and STAs adjust their power such that APs and STAs on the same channel can co-exist in an area without interference. For APs using the same channel, APs continually re-adjust their power levels based on environmental factors such as signal strength changes due to movement of doors, people, background noise floor, and the like, so that the users' optimal bandwidth is maintained without undue interference. a. Auction: APs keep track of various parameters for STAs that are associated with them, and STAs will roam between APs for load balancing purposes, which can help to maximize performance over a group of STAs. 1. STA initialization: STAs associate with an initial AP. Invention enabled STAs turn on functions that allow them to receive messages from invention enabled APs. 1. STA optimization: a. Channel Canvassing: In order to further optimize performance, STAs periodically canvass the other channels in the band in which the STA is operating to see if a "better" AP is present. To ascertain whether another AP is "better", various parameters are considered, such as signal strength and load factors, to be further described. a. Bidding: If a better AP is found, a STA enters a bidding process to try to cause the STA to roam to the better AP. Load balancing is thereby achieved. In addition, the bidding process accommodates STA movement by causing the STA to associate to a better AP after it has moved closer to the better AP. a. Power Adjustment: STAs perform power adjustment such that they can maintain throughput to and from their currently associated AP while minimizing the interference with nearby wireless devices that may be using the same channel. a. Movement Detection: STAs perform movement detection so that the bidding process can be turned off while a STA is moving, and then turned back on when the STA has stopped moving. When turned back on, a "better" AP may turn up and thus the STA will bid for it. 1. Software Architecture a. The above functionality is advantageously implemented in APs and STAs in a modular manner for ease of transfer between platforms. a. The above functionality is described in detail as it is implemented in a preferred 802.11 network embodiment. 1. Movement Detection statistical analysis: A novel scheme for highly accurate and computationally efficient detection of a change in an attribute subject to high noise variation is described, and applied to detection of the movement of wireless STAs.

Since exemplary examples will refer to the 802.11 networking environment, the following information provides relevant context, while understandably not limiting the invention to 802.11 environments.

In an 802.11 network, APs periodically send frames called "Beacons". STAs listen for Beacons. When an unassociated STA (i.e. a STA that is not yet able to communicate on the wireless network) hears Beacons at what it deems to be a reasonable power level, it can attempt to authenticate with the AP sending the Beacons, and then associate with that AP. Once authenticated and associated, the STA is able to send data frames to other STAs on the wireless network via the AP.

More particularly, APs and STAs send and respond to three different types of frames, known as Class 1 Frames, Class 2 Frames, and Class 3 Frames. Class 1 Frames include control frames and management frames, and can be sent regardless of whether a STA is authenticated and associated with an AP. A Beacon is a type of Class 1 frame. Class 2 Frames are sent only once a STA is authenticated, and include for example association request/response messages. Class 3 Frames can be sent only if associated, and include data frames.

In order to maximize user bandwidth and throughput, the invention automatically optimizes the operation of multiple APs for a given wireless communications environment. In accordance with the exemplary IEEE 802.11a networking standard, 13 non-overlapping frequencies are available for use by the APs. Each AP is capable of transmitting and receiving data at a maximum rate of 54 Mbps. The actual rate at which data is transmitted and received between an AP and a STA depends upon many factors, including the distance between the AP and the STA, the structures located between the AP and the STA, and the environmental interference occurring on the particular frequency. One skilled in the art will realize that the invention is not limited by the maximum data rates of current wireless technology, nor is it limited by currently understood radio frequency attenuation factors. The principles of the invention will continue to be applicable as wireless technology evolves.

Consider an area such as the wireless network shown in FIG. 2, wherein 8 users (shown as STAs 16), which may be mobile laptops, PDAs, and the like, share a space including a single AP 12 operating on one of the 13 available 802.11a frequencies, denoted "f1". The 8 users 16 share the bandwidth provided by the AP 12. If all 8 users 16 are located close enough to the AP such that the AP provides a 54 Mb bit maximum data rate, then all 8 users 16 share the AP's bandwidth such that each user maintains 6.75 Mb throughput on average. (The invention contemplates the fact that data traffic is bursty and that a user in the present example may attain 54 Mb throughput for a short interval, but for purposes of simplicity, the average throughput over time for a given user is discussed.)

Now, referring to FIG. 3, a second AP 12 has been added in the area. The second AP 12 operates on a different one of the 13 frequencies, denoted "f2", such that the two APs 12 do not interfere, nor do their associated STAs 16. As shown, 4 of the 8 users have roamed to the second AP 12. Now each user maintains 13.5 Mb throughput on average. Addition of further APs on different frequencies further increases user average throughput.

In accordance with the invention, a Dynamic Radio Control Protocol (DRCP) provides a mechanism for an arbitrary collection of STAs and APs to automatically control the frequency and power of their radios in order to extend the properties exemplified in FIG. 2 to maximize overall system performance. DRCP messages are passed between APs and APs, as well as between APs and STAs to implement this functionality. Eight types of messages are used: DRCP Preclaim, DRCP Claim, DRCP Announce, DRCP Bid, DRCP Accept, DRCP Registration Request, and DRCP Registration Acknowledge.

DRCP Preclaim and Claim messages are exchanged between APs during AP initialization, and are used to aid automatic channel selection in accordance with the invention. DRCP Announce messages are sent by APs and received by STAs during STA optimization. These Announce messages inform invention-enabled STAs of available invention-enabled APs to which they may choose to associate, and provide information about APs that STAs can use to aid a decision as to whether to request to roam to another AP. DRCP Bid messages are sent by STAs to APs during STA optimization. These messages inform invention-enabled APs of invention-enabled STAs that are requesting association to the APs. DRCP Accept messages are sent by APs to STAs in response to DRCP Bid messages. These messages inform a STA that it may associate with the AP it is requesting to associate with. DRCP registration request and acknowledge messages are exchanged by invention-enabled APs and STAs to indicate to each that the other is DRCP capable.

The DRCP protocol employing these messages will first be described as used in a generic wireless communications environment. The detailed implementation of each of these messages will then be further described in terms of a preferred embodiment in an 802.11 environment.

The aspects of the invention are now described as they apply to AP initialization and optimization, and then as they apply to STA initialization and optimization. It is noted that, though many of the inventive aspects described herein with regard to STAs and APs are advantageous when implemented, they are not required to be implemented in a wireless communications environment. Performance advantages are achieved when only the APs, or only the STAs, or both implement one or more of the various aspects of the invention.

1. AP Initialization

During AP initialization, APs perform automatic channel selection. In accordance with the channel selection aspect of the invention, APs located in the same wireless network automatically select channels for operation such that they do not interfere with nearby APs. The invention contemplates that different bands of frequencies are available, for example based on 802.11 version and the country in which the network is deployed. According to a preferred embodiment, APs attempt to select a channel, in each band in which the AP is equipped to operate, which is least likely to interfere with other APs that are already deployed. APs also quarantine channels in accordance with rules associated with regulatory domains (Europe, etc.) so they don't interfere with other wireless applications (radar, etc.). In the event that one AP selects a free channel, and another AP selects the same free channel at the same time (i.e. a channel selection "Collision"), the APs' media access control (MAC) addresses are used as a tie breaker. If the other AP is a standard AP that does not include the improvements associated with the current invention, then the invention-enabled AP will direct its own radio to the "next best" channel. The AP repeats the channel selection phase for each band of frequencies.

More particularly, referring to FIG. 4, before a newly added AP 12 starts to "Beacon" (i.e. broadcast management packets to other APs and STAs), the AP 12 first examines a list of RF bands supported by the AP 12, and the list of channels supported and not quarantined by the radio which implements the Physical Layer (PHY) for each RF band. The AP 12 then selects a channel in each band according to the following algorithm:

For each band:

Scan Intervals occur periodically. During a Scan Interval (step 20), the AP 12 passively scans all channels which the AP supports within the band (step 22). The AP 12 gathers a list of active APs 12, the channels on which they are operating, and the power at which the beacons from each AP 12 was heard. This information is used to build a table called a channel map 24 (step 26), which contains a list of all APs 12 heard from, the channel on which they were heard, and the signal strength at which they were heard. There is a separate channel map 24 for each band. The AP 12 sorts the channel map to produce a list of APs 12 in ascending order of power level (step 28).

Referring to FIG. 5, a channel is now selected by the AP 12 as follows. First, the AP 12 peruses the channel map (step 30), and if there is a channel on which no AP 12 is operating (i.e. signal strength=0) (step 32), then the AP 12 selects that channel (step 34). Otherwise, the AP 12 peruses the list for the channel transmitting the weakest signal (step 36). The AP 12 now enters a time interval referred to as the "claiming period" (step 38).

If the AP 12 selected a channel having the weakest signal strength, the AP 12 notes the channel-ID of the channel that it has selected, the received power level on the channel, and the AP-ID of the AP that generated that power level (step 40). It will use the power level value as a baseline against which to detect increases in received power on its selected channel. If the AP 12 selected an empty channel, the baseline power level will be the AP's noise floor.

The AP 12 then advertises its intention to use the selected channel by periodically transmitting DRCP Claim messages during the claiming period (step 42). Claim messages are transmitted at full power. During this claiming period, the AP 12 receives all Beacons, DRCP Claim messages, and DRCP Announce messages transmitted on the currently chosen channel (step 44) and uses the information contained therein to build an "Other APs" table 46 (FIG. 6, FIG. 5 step 48). For each Beacon it receives, the AP 12 notes the AP-ID and the received power level in the Other APs table 46. For each Claim or Announce message it receives, the AP 12 notes the AP-ID of the AP that sent the message, the received power level, and the transmit power backoff (TP backoff) in the Other APs table 46. The TP Backoff value indicates how far from maximum power the sending AP's radio has been turned down, and will be explained in more detail in the AP Power Adjustment section. The AP 12 also marks the entry for that AP-ID as being DRCP capable. A normalized received power value is calculated by adding the TP Backoff value to the received power value. The normalized received power value equalizes the AP power levels for comparison purposes. When the AP 12 receives a Beacon or DRCP message from an AP for which it already has an entry, it updates the entry and stores the received power and TP_backoff values as a list.

If another AP 12 starts to radiate significant energy on the selected channel, one of two events must have occurred. The new AP 12 is either not running DRCP, or a conflict has occurred with another DRCP-active AP, where a race condition has caused the other DRCP-active AP to select the same channel at the same time. This is called a Channel Selection Collision (CSC).

At the end of the claim period (step 50), the AP 12 stops sending Claim messages and evaluates the information it has collected, its CSC data, to determine if a CSC has occurred. It looks to see if the received power in any entry is greater than the baseline power level it recorded for the channel (step 52). If so, it looks to see if the received power is exceeded in at least half of the power level values for the entry (step 54). If so, the AP 12 checks to see whether the AP in the entry is DRCP capable (step 56).

If the other AP is not DRCP active, the AP 12 defers to the non-DRCP-active AP and starts the entire channel selection process over again.

If the other AP is DRCP-active, then a CSC is assumed to have occurred. When a CSC has occurred, the MAC address of the other AP is compared to the MAC Address of this AP 12. If the MAC address of this AP 12 is numerically higher than the observed MAC address (step 58), this AP 12 starts the channel selection process over again.

If at the end of the claiming period, the AP has succeeded in claiming the selected channel, it begins running on the channel. The AP starts beaconing, begins sending DRCP Announce messages, and prepares to enter the Optimization stage in order to run its Auction and Power Adjustment functions (step 60).

A variation on the channel selection process of FIG. 5 can be employed to improve channel selection coverage when several APs 12 are powered on all at once. Referring to FIG. 7, each AP, upon power-up, sends a claim message on a first channel chosen from the channel map--for purposes of example designated channel 1 (steps 62, 64). All APs scan all channels. All APs scanning on channel 1 will hear each other's claim messages. During the claiming period, an AP will ascertain whether channel 1 is in fact available for use by it. Accordingly, the AP listens for other DRCP Claim messages on the same channel, which would indicate that another invention-enabled AP is trying to use the same channel (step 66). The AP 12 keeps track of the number of different APs it hears (based on AP IDs the claim messages received) and the average signal strength of claim messages from each AP. The AP 12 builds an adjacency vector (adjacency count, adjacency power total) (step 68). Adjacency count represents the number of APs heard on the channel. Adjacency power total represents the sum of the average power levels for each AP heard. Each AP sends its adjacency vector to all the other APs in its claim messages step 70. If a DRCP claim message is received (step 72), in this case on channel 1, the AP 12 first compares its adjacency count with the adjacency count received in the claim message (step 74). If the AP 12's adjacency count is higher than that received in the claim message, this probably indicates that the AP 12 is closer to the center of the network. The AP 12 therefore continues to claim the channel during the claim period. If the AP's adjacency count is the same as the adjacency count received in the claim message (step 76), the AP 12 then compares its own adjacency total power to the adjacency total power value received in the claim message. If the AP 12's own adjacency total power is higher than that received in the claim message (step 78), this may also indicate that the AP 12 is closer to the center of the network, and therefore the AP 12 continues to send claim messages on the channel. If the AP 12's own adjacency total power is the same as that received (step 80), then the AP 12 performs the previously described MAC address test step 82). If the AP 12 finds that its own adjacency count or adjacency power are lower than any received in claim messages, or that in the event of a tie on these values that its MAC address is higher, it ceases to send claim messages on the channel and returns to peruse the channel map (step 84). Otherwise, the AP 12 continues to send claim messages including its adjacency vector (step 70). If, at the end of the claiming period (step 86), the AP 12's adjacencies are greater than other AP's adjacencies, the AP 12 has won the channel and proceeds to the AP optimization phase (step 88). According to this method, the APs closest to the center of a multi-AP network obtain the first channel assignments and subsequent channels are assigned to the other APs.

Referring to FIGS. 8A and 8B, a preferred embodiment of the automatic channel selection algorithm is shown. For each band:

Scan Intervals occur periodically. During a Scan Interval (step 100), the AP 12 scans all channels which the AP supports within the band, receiving Beacons and Announce messages (step 102). The information received in the Beacon and Announce messages is used to build a table called the "Scan table" (step 104). An example of a Scan table 106 is shown in FIG. 9. The Scan table 106 includes an entry for each AP 12 from which a Beacon or Announce message has been received. For each entry, there is stored the AP-ID and the channel on which that AP 12 was heard. Also stored is a "rxPowerRunningTotal" value that represents the sum of the signal strengths of each message received from that AP 12. Also stored is a "rxPowerSampleCount" value that represents the number of messages received from the AP 12. A DRCP flag is set if an Announce message has been received from the AP 12. The entryAge entry is incremented every time the channel is scanned. The "rxPowerAvg" is calculated during a Preclaim interval as will be further described.

As the scan progresses, the rxPowerSampleCount values in the Scan table 106 are monitored, and if any one of them exceeds a threshold, herein labeled "threshold1" (step 108), the AP 12 proceeds to step 110 to build a channel map. In addition, if any entryAge value in the table exceeds a certain threshold "threshold2" (step 112), the AP 12 will proceed to step 110. Also, if the number of scans completed exceeds a certain threshold "threshold3" (step 114), the AP 12 will proceed to step 110. Otherwise the AP 12 continues scanning and updating the Scan table 106.

An example of a preferred channel map 116 is shown in FIG. 10. The channel map 116 contains an entry for each channel ID. To build the channel map, the AP 12 peruses the Scan table 106 and calculates the "rxPowerAvg" value for each entry, as: RxPowerAvg[I]=Scan table[i].rxPowerRunningTotal/Scan table[i]rxPowerSamplecount;

For each channel, the AP-ID with the highest rxPowerAvg value is entered in the channel map 116. The AP's rxPowerAvg value is entered into the channel map 116 as the highestPwrlevel parameter.

In certain network implementations, it is undesirable to locate two operating APs 12 within a certain distance of each other, because doing so does not increase network performance and may reduce it. So, according to a preferred option, once the channel map has been assembled, the AP 12 checks the channel map to see if any of the highestPwrlevel values in the map exceed a certain threshold power level (step 118). The threshold power level is chosen to indicate that the AP 12 is located too close to another AP. If any highestPwrlevel exceeds the threshold power level, the AP 12 is placed in "Standby mode" (step 120). The AP 12 in Standby mode waits for a period of time herein referred to as "Standby Interval" before returning to start another scan interval (step 122).

If no highestPwrlevel values are found to exceed the threshold power level, the AP proceeds to assemble a triplet channel map 124 (step 126). As shown in FIG. 11, the AP 12 sorts a channel map into triplets, for example, channels 1, 2 and 3, channels 2, and 4, channels 3, 4 and 5, etc. The power heard on each channel in the triplet is averaged into a triplet average. The list of triplets is sorted in ascending order, with the triplet with the lowest average power at the top of the list. The AP 12 starts at the top of the list and looks for the first triplet in which the power heard on the center channel of the triplet is less than or equal to the power heard on the two adjacent channels, and selects this channel (step 128). If no such triplet is available, the AP selects the channel with the lowest triplet average. In the example shown in FIG. 11, AP 12 chooses channel 3. This process advantageously minimizes interference between channels by selecting channels that do not tend to have high power adjacent channel usage.

The AP 12 then records the baseline power for the selected channel as the highestPwrlevel value for the channel, and records the AP-ID of the AP at that power level (step 130). A Preclaim Interval is now entered (step 132). During the Preclaim interval, the AP transmits Preclaim messages on the selected channel (step 134). The AP 12 also receives Beacon, Announce, and Preclaim messages on the channel (step 136). The AP 12 uses the received messages to update the Scan table (step 138). The AP 12 continues to update the Scan table until one of two Preclaim intervals expires. During the min Preclaim interval (step 140), the rxPowerSampleCount value for each AP-ID on the selected channel is checked to see if a minimum sample size threshold has been exceeded. If so, the Preclaiming interval ends and the AP proceeds to check to see whether too many APs are operating on the selected channel (step 142). Otherwise, the Preclaiming period extends until the end of the max Preclaim interval (step 144).

In some network environments, and in particular environments of limited area, the operation of too many APs on the same channel does not increase network performance and may cause a performance reduction. So, according to a preferred option, the AP checks to see if there are too many APs operating on the network (step 142). The number of different AP-IDs present in the Preclaim APs table is used to make this determination. If there are too many APs operating on the selected channel at a power level greater than a defined threshold, the AP 12 enters Standby mode

If there are not too many APs operating on the selected channel, the AP 12 calculates an "adjacency vector sum" (step 146). The adjacency vector sum is calculated over all APs on all channels as: Adjacency vector sum=sum(Preclaim APs[i].ReceivedPowerTotal/Preclaim APs[i].count) The adjacency vector sum is used as a tiebreaker if necessary during the Claiming interval, to be further described.

The AP 12 now enters the Claiming interval (step 148). During the Claiming interval, the AP 12 transmits Claim messages on the selected channel (step 150). Claim messages include the adjacency vector sum. The AP 12 also receives all Beacon, Announce, and Claim messages on the selected channel (step 152). The AP 12 uses the information contained in the received messages to build a "Claim APs table" 154 (step 156). An example of the Claim APs table is shown in FIG. 12. The Claim APs table 154 contains an entry for each AP-ID. The received power level of each message received from a given AP is stored in the Claim APs table 154 as a list of values (shown as column "ReceivedPowerlevel). Furthermore, for each Announce or Claim message received, a DRCP flag is set. The AP continues to update the Claim APs table until the end of the Claiming interval (step 158).

The AP 12 then evaluates the Claim APs table 154 (step 160) to ascertain whether any other APs were heard from. If no entries exist in the Claim APs table 154 (step 162), the AP 12 has "won" the selected channel. The AP 12 can then begin Beaconing and sending Announce messages on the channel (step 164). If the Claim APs table 154 includes one or more entries, then if the selected channel was empty at the beginning of the Claiming Interval (step 166), the AP 12 concedes the channel and returns to re-scan (step 100). Otherwise, if the channel was not empty, then if the ReceivedPowerlevel values for all entries in the table are less than the baseline level recorded during Preclaiming plus a threshold level (e.g. 2 db) (step 168), then the AP has won the channel (step 164). However, if the AP does find a ReceivedPowerlevel value that exceeds the baseline power level plus the threshold level, and that entry is associated with an AP-ID that was not the one recorded on the channel during the Preclaiming Interval, then the AP checks the entry's DRCP flag (step 170). If the DRCP flag indicates that the AP-ID associated with the entry is not DRCP capable, then the AP returns back to the scan interval to re-start the channel selection process. If the DRCP flag indicates that the AP-ID associated with the entry is DRCP capable, then the AP compares its adjacency vector with the adjacency vector received in the other AP's claim messages (step 172). If the AP's adjacency vector is less than the other AP's adjacency vector, the AP concedes the channel and returns to re-scan. If the AP's adjacency vector is not less than the other AP's adjacency vector, then the AP checks to see if the adjacency vectors are equal (step 174). If they are, the MAC addresses of the two APs are compared (step 176). If the AP's MAC address is greater than the other AP's MAC address, the AP has "won" the channel (step 164). Otherwise, the AP concedes the channel and returns to re-scan (step 100). One skilled in the art will realize that the MAC address comparison decision is arbitrary and can be made in the opposite manner.

1. AP Optimization

Once an AP is running on a channel, it continuously performs the following functions to optimize its configuration in the wireless LAN: Radio Power Adjustment. Each DRCP-enabled AP adjusts its power as appropriate, to accommodate the nearest AP operating on its channel while maintaing its connection to its farthest associated STA. The AP conveys a TP_backoff parameter in its Announce messages. The TP_backoff value provides an indication of how far the sending AP has turned its transmit radio down. This TP_backoff value is used by other APs to determine their own TP_backoff values. A STA that is associated to the AP can then adopt the communicated TP_backoff value to adjust its radio power, and can track this value as it changes. Auction. The AP runs the Auction process to accept new DRCP STAs for association, as appropriate, based on received DRCP Bid messages. These two functions are now described in terms of a preferred embodiment. 2.a. Radio Power Adjustment 2.a.1 AP Maintained Tables

In order to perform Radio Power Adjustment, the AP 12 maintains a number of tables. The tables include information received from other APs and STAs operating on the selected channel. This information is used to ascertain such things as power levels of other devices on the channel, and distances between devices on the channel, in order to control the AP's power level.

2.a.1.1 AP KnownAPs Table

Each AP 12 maintains a number of tables that it consults to perform power adjustment. One such table is the AP KnownAPs Table 200. As shown in FIG. 13, once initialized on a channel, an AP 12 receives Beacons and DRCP Announce messages from all other APs 12 operating within the range of its radio, on its channel (steps 202, 204, 206). The AP 12 uses these received messages to build the AP KnownAPs table 200. For each message it receives, the AP 12 checks to see if it has an entry in the AP knownAPs table for the AP-ID in the message (step 208). If found, the AP 12 updates the entry (step 210), otherwise it creates a new one (step 212), up to a maximum of Max_APs entries (step 214). The value of Max_AP is design dependent.

Referring to FIG. 14, the AP 12 stores the following fields in the corresponding AP knownAPs table 200 entries: AP-ID TP Backoff Max Power DRCP capable Age Normalized power Sample size Corrected power

The AP-ID, TP Backoff, and Max Power fields are extracted from each DRCP Announce and Hello message received. The TP Backoff value is stored as a list of values for each message received from each AP-ID. The sample size is the number of TP Backoff values received for each AP-ID.

Since Announce messages are only sent by DRCP-enabled APs, the AP 12 also marks the entry as DRCP-active. APs sending Beacons which contain no DRCP fields are not marked DRCP-active. For each message received, the AP adds the TP Backoff value to the received power level to determine a normalized received power level, as follows: normalized_power=avg(received_power+tp_backoff);

Accounting for the TP backoff in the normalized power level provides a value that is consistent and can be used for comparison with power level measurements from other APs.

Received beacons do not explicitly carry a TP backoff value, however, since beacons are always transmitted at full power they effectively carry a TP backoff value of zero. Thus, the AP 12 can update the AP KnownAPs table 200 based on a received Beacon. In this case the AP 12 stores the TP backoff value as zero, and sets the normalized power and the Max Power to the received power level value.

Additionally, the AP 12 keeps an Age for each entry. The Age is reset to zero, "0", each time a Beacon or DRCP Announce is received from the AP corresponding to the entry. Entries are aged as part of the AP Power Adjustment process.

2.a.1.2 AP AssociatedSTAs Table

APs 12 also continuously maintain a table of the STAs 16 that are associated with it--the AP AssociatedSTA table. Referring to FIG. 15, for every associated STA 16, the AP 12 monitors and collects signal strength information for data packets received (step 220). If an entry for the STA already exists in the AP AssociatedSTAs table (step 222), that entry is updated (step 224). Otherwise a new entry is created for the STA (step 226). The collected data is periodically analyzed by the AP for AP power adjustment purposes. In addition, whenever a DRCP-active STA 16 becomes associated with an AP 12, it sends a Registration Request message to the AP 12. Registration Request messages are sent by the STA 16 to the AP 12 periodically until a Registration Acknowledge message is received by the STA 16. Upon receipt of a Registration Request from an STA 16 (step 228), the AP 12 updates the entry in the AssociatedSTA Table and marks it as a DRCP-active STA (step 230) and sends a Registration Acknowledge message to the STA 16 (step 232).

As shown in FIG. 16, the AP 12's AP AssociatedSTA Table 240 maintains the following information about each STA: STA-ID--MAC Address of the Station Quiet-time--A value representative of the amount of time since data was last received from this STA DRCP-Active--defaults to false, set to true upon receipt of a Registration Request Distance--Distance (in Banzais, to be further described) to this STA, calculated based on signal strength information and TP Backoff Max Power--list of power values Power samples--number of power samples received Normalized_power Corrected_power sta_load_factor--The load of this STA on this AP, see section 4.c. 2.a.1.3 AP Power Adjustment

During the channel selection process, the AP 12 transmits at maximum power, that is, it uses a TP backoff value of zero. Once the AP 12 has successfully claimed a channel, it calculates a TP Backoff value and adjust its transmit power for data transmissions down, in accordance with this value to minimize same channel interference and maximize channel/bandwidth re-use. The calculation of the TP Backoff value is now further described.

Generally, with reference to FIG. 17, AP power adjustment is accomplished as follows: The AP 12 peruses its AP KnownAPs table (step 260). The AP 12 finds the AP in the table with the highest TP Backoff value. The AP 12 then sets its own Max TP backoff value to the highest TP Backoff value (step 262). This Max TP Backoff value, if used as the AP 12's TP Backoff value, would reduce the AP 12's transmit power to a level just below the range of the nearest AP operating on the same channel.

Once the Max TP backoff is calculated, the AP then scans the AssociatedSTA table to ascertain the distance to the farthest associated STA 16 (step 264). The distance to the farthest associated STA 16 is compared to the distance to the closest AP 12 operating on the same channel (step 266). If the distance to the farthest associated STA 16 is less than the distance to the closest AP 12, the AP's TP Backoff value is left at Max TP Backoff (step 268). If the distance to the farthest associated STA is greater than the distance to the closest AP operating on the same channel (step 266), then the Max TP backoff value is adjusted back down to accommodate this STA (step 270), and the AP's TP backoff is set to this adjusted value (step 272). This power adjustment is periodically repeated to account for changes in the AP KnownAPs table and the AP AssociatedSTAs tables change (step 274). Power adjustement may be repeated every second, for example, in an 802.11 environment.

In accordance with the preferred embodiment for use in a wireless data networking environment, as shown in FIGS. 18A and 18B, APs perform the above described power adjustment as follows. First, AP 12 checks to