Note: Descriptions are shown in the official language in which they were submitted.
CA 02506121 1996-10-01
1
PREEMPTIVE ROAMING IN A CELLULAR LOCAL
AREA WIRELESS NETWORK
This is a division of copending Canadian Patent
Application Serial No. 2,186,923 that was filed on
October 1, 1996.
BACKGROUND OF THE INVENTION
Field of the Invention
The invention relates generally to preemptive
roaming among cells in a cellular network. In particular
the invention relates to a local area wireless network
including a plurality of mobile units and a plurality of
access points.
2. Description of the Related Art
Wireless local area networks (LAN'S) are used in
business applications such as inventory, price
verification mark-down, portable point of sale, order
entry, shipping, receiving and package tracking. Such
systems are often proprietary systems wherein the
operator carries a mobile unit such as a hand-held
CA 02506121 1996-10-01
2
computer communicating with a house computer via one of
a plurality of access points connected to the house
computer and to one another, each access point
interacting with the house computer to create a wireless
cell.
In order to achieve inter-operability of the various
proprietary systems a draft standard IEEE 802.11 has been
proposed (the IEEE 802.11 draft specification is
available for public inspection).
The draft standard includes features such as 1Mbps
and 2Mbps data rates, carrier sense multiple
access/collision avoidance (CSMA/CA), a power-save mode
for battery-operated mobile stations, seamless roaming in
a full cellular network, high throughput operation,
diverse antenna systems designed to eliminate "dead
spots", and an easy interface to existing network
infrastructures.
The term "roaming" relates to the scanning by each
mobile unit of all access points to identify and
associate with an eligible access point. Roaming between
cells provides great flexibility and is particularly
advantageous in locations that are difficult to wire, for
simple relocation of work stations, and for portable work
stations. The IEEE 802.11 protocols supports either
direct-sequence or frequency-hopping spread-spectrum
systems, as well as infrared communications. Each access
point executes a unique hopping pattern across 79 non-
overlapping frequencies at a rate of one hop every 100
milliseconds, 66 hopping patterns being specified in the
IEEE 802.11 draft standard and being selected to minimise
the possibility of interference.' Frequency hopping
spread-spectrum systems are preferred by the majority of
users as they allow increased capacity and decreased
interference.
CA 02506121 1996-10-01
3
Although the IEEE 802.11 draft specification
provides the basic packet types which can enable roaming
it does not actually set the roaming algorithm.
According to the draft specification the mobile unit
determines the access point with which it will associate
and the access point must accept the mobile unit unless
it is defective or certain alarm conditions exist, such
as memory full. There is, however, no suggestion of how,
or by what criteria, other than those mentioned above,
the mobile unit might select an appropriate access point,
or the optimum access point.
US 5,276,680 relates to a communication system
including a plurality of portable units and a plurality
of controllers wired to a network. Each portable unit
polls all of the controllers to establish whether it can
associate with any controller and receives a response
from any controller having less than a predetermined
number of portable units already associated therewith.
SUMMARY OF THE INVENTION
1. Objects of the Invention
It is an object of the present invention to provide
a communication system allowing improved selection by a
mobile unit of an access point for association.
It is a further object of the present invention to
provide a communication system allowing selection by a
mobile unit of an access point to provide optimum
operation of the system.
It is a further object of the present invention to
provide a communication system providing information
concerning the physical location of a mobile unit.
It is a further object of the present invention to
provide a communication system adapted to prevent mobile
CA 02506121 2009-10-26
4
units from being taken outside a given physical area.
2. Features of the Invention
Certain exemplary embodiments can provide a data
communications network, comprising: a) a plurality of
stationary access points operatively connected to a host, a
plurality of mobile units, each of the mobile units using
frequency hopping spread spectrum radio frequency
communications, one of the mobile units including a
transmitter for broadcasting a probe packet to all of the
access points in a predetermined range from said one of the
mobile units that is broadcasting the probe packet, b) said
access points within said range including respective
receivers for detecting the probe packet being broadcast,
and for responsively sending probe response packets back to
said one of the mobile units, c) a selector for selecting a
most eligible one of the access points from the plurality
of the access points on the basis of received signal
quality at said one of the mobile units and loading factor
at each of the access points, d) a physical area within
which all mobile units are kept, said area having an exit
adjacent which one of the access points is located.
Accordingly, a simple and reliable arrangement is
provided enabling preemptive roaming and optimum selection
of an access point for association with a mobile unit.
Each mobile unit may select a group of eligible access
points and select the most eligible access point from that
group. The received access point signal quality may be
represented by the received signal strength indication
(RSSI) . The loading factor may be defined by the number of
mobile units associated with a given access point. The
cellular communications network may comprise a 1Mbps
frequency-hopping spread-spectrum wireless LAN conforming
to the IEEE 802.11 draft specification.
CA 02506121 2009-10-26
4a
Each mobile unit may send out a probe message packet
to all access points wherein the probe packet has no
destination address but a mobile unit specific source
address. The probe packet may include an identification
CA 02506121 1996-10-01
of the access point with which the mobile unit is
currently associated. Each access point that detects the
probe packet may send a probe response packet containing
the following information:
5 access point address;
access point frequency hopping pattern;
access point present channel;
time remaining in present channel;
loading factor.
The mobile unit may carry out its selection on the basis
of the signal quality of, and information contained in
the received probe response packets or the access point
signal quality may be determined from a beacon signal
sent by the access point independently of a probe
response packet.
Each mobile unit may store the RSSI value for each
access point and calculate an average value over a
predetermined period, and RSSI values outside a
predetermined range may be omitted from the averaging
calculation.
Each mobile unit may carry out a full scan of all
available frequency channels on power-up and thereafter
at regular intervals. The full scan may be carried out
at approximately thirty second intervals. Each mobile
unit may carry out a partial scan of known access points
at regular intervals more frequently than a full scan is
carried out, for example at approximately five second
intervals.
Each mobile unit not associated with an access point
may identify on scanning all access points with signal
quality equal to or above a threshold value and select
for association the access point having the lowest
loading factor; when two or more access points have an
equal lowest loading factor the access point having the
CA 02506121 1996-10-01
6
highest RSSI value may be selected. The threshold value
may be set at six counts below the highest detected RSSI
value.
A mobile unit associated with an access point and
experiencing an unacceptably low communication level may
roam excluding the current access point from selection.
The unacceptably low communication level may be achieved
when more than 50% retries, CRC errors or missed beacons
are experienced. The excluded access point may be re-
included for selection when its RSSI value has increased
by a predetermined limit. If no eligible access points
are identified for re-association the mobile unit may
continue to associate with the current access point.
A mobile unit associated with an access point and
achieving a satisfactory level of communication may make
a scanning decision at predetermined intervals. A
satisfactory communication level may be achieved when 50%
or less retries, CRC errors or missed beacons are
experienced. An eligible group may be selected
comprising all access points with signal quality above a
predetermined threshold, the group including the current
access point when its signal quality is above a further
predetermined threshold, and the access point may be
selected having the lowest loading factor; access points
having a loading factor of more than a given proportion
of the current access point loading factor may be
excluded and where two or more access points have the
same loading factor, the access point having the highest
signal quality may be selected. The eligible group
threshold value may be six counts below the highest
received RSSI value, the current access point further
threshold value may be eleven counts below that RSSI
value, and access points having a loading factor of more
than 75% of the current access point loading factor may
CA 02506121 1996-10-01
7
be excluded.
Each mobile unit may carry out a partial scan of
known access points at predetermined intervals and may
carry out the roaming decision immediately after the
partial scan.
The communications network may be included in one of
an inventory, price verification, mark-down, portable
point of sale, order entry, shipping, receiving and
package tracking systems.
According to the invention there is further provided
a mobile unit for use in a cellular communications
network comprising a plurality of access points, the
mobile unit including a communications system for
association with an access point and a selection system
for scanning all access points, selecting a group of
eligible access points for association and selecting from
that group a most eligible access point, selection being
carried out according to the following criteria:
a received access point signal quality; and
loading factor.
According to the invention there is further provided
a cellular communications network comprising a plurality
of mobile units and a plurality of access points, the
mobile unit being arranged to roam and associate with a
selected access point, the mobile unit including a
selection system for selecting a group of eligible access
points for association and selecting from that group the
most eligible access point, selection being carried out
according to the following criteria:
received access point signal quality; and
loading factor.
According to the invention there is further provided
a method of operation of a cellular communications
network, the network including a plurality of access
CA 02506121 1996-10-01
8
points in communication with each other and a plurality of
mobile units wherein:
each mobile unit scans for and associates with the
most eligible access point at predetermined intervals, each
mobile unit selecting a group of eligible access points,
and from that group, selecting the most eligible access
point according to the following criteria:
received access point signal quality; and
loading factor.
According to the invention there is yet further
provided a data communications network including a
plurality of stationary access points and a plurality of
mobile units wherein:
each mobile unit scans for and selects as eligible
access point for association therewith on the basis of
received access point signal quality and loading factor at
the access point and wherein:
a physical area is defined within which all mobile
units must be kept and access points are provided adjacent
the or each exit point from the physical area.
The access point at the exit point may include a
directional (horn) antenna providing a strong signal in the
vicinity of the exit point.
In accordance with other aspects of the present
invention there is provided a data communications
network including a plurality of stationary access
points operatively connected to a host and a
plurality of mobile units, said network comprising: a)
each of the mobile units using frequency hopping spread
spectrum radio frequency communications, and
CA 02506121 1996-10-01
8a
including a transmitter for broadcasting a probe
packet to all of the access points in a predetermined
range from one of the mobile units that is
broadcasting the probe packet, b) said access points
within said range including respective receivers for
detecting the probe packet being broadcast, and for
responsively sending probe response packets back to
said one of the mobile units, and c) a selector in
each of the mobile units to select a most eligible
one of the access points from said probe response
packets, and to associate said one of the mobile
units with the most eligible one of the access points
at predetermined intervals, the most eligible one of
the access points being selected according to
received signal quality at said one of the mobile
units, and a loading factor at each of the stationary
access points.
In accordance with another aspect of the present
invention there is provided a method of operating a
cellular communications network including a plurality
of access points in communication with each other and
operatively connected to a host, and a plurality of
mobile units, comprising the steps of: a)
broadcasting a probe packet to all of the access
points in a predetermined range from one of the
mobile units that is broadcasting the probe packet,
each of the mobile units using frequency hopping
spread spectrum radio frequency communications; b)
detecting the probe packet being broadcast, and
responsively sending probe response packets from the
access points within said range back to said one of
the mobile units; c) minimizing interference among
CA 02506121 1996-10-01
8b
the probe response packets; d) scanning the plurality
of the access points at predetermined intervals; and
e) selecting a group of eligible ones of the access
points from the plurality of the access points, by
selecting a most eligible one of the access points
from the group according to received signal quality
at said one of the mobile units and loading factor.
In accordance with yet another aspect of the
present invention there is provided a data
communications network, comprising: a) a plurality of
stationary access points operatively connected to a
host, a plurality of mobile units, each of the mobile
using frequency hopping spread spectrum radio
frequency communications, one of the mobile units
including a transmitter for broadcasting a probe
packet to all of the access points in a predetermined
range from said one of the mobile units that is
broadcasting the probe packet, b) said access points
within said range including respective receivers for
detecting the probe packet being broadcast, and for
responsively sending probe response packets back to
said one of the mobile units, c) a selector for
selecting a most eligible one of the access points
from the plurality of the access points on the basis
of received signal quality at said one of the mobile
units and loading factor at each of the access
points, and d) a physical area within which all the
mobile units are kept, said area having an exit
adjacent which one of the access points is located.
CA 02506121 1996-10-01
8c
The novel features which are considered as
characteristic of the invention are set forth in
particular in the appended claims. The invention
itself, however, both as to its construction and its
method of operation, together with additional objects
and advantages thereof, will best be understood from
the following description of a specific embodiment,
when read in conjunction with the accompanying
drawings. It is to be under.stood that the invention
may be carried into practice in a number of ways, and
the described embodiment is not intended to be
limiting.
CA 02506121 1996-10-01
9
BRIEF DESCRIPTION OF THE DRAWING(S)
Fig. 1 is a schematic illustration showing the
communication system of the present invention in
operation;
Fig. 2a is a block diagram illustrating the steps
carried out by a mobile unit during the roaming process;
Fig. 2b is a flow chart illustrating the steps
carried out by a mobile unit for selection of the most
eligible access point;
Fig. 3 shows a probe response message typically sent
by an access point according to the present invention;
and
Fig. 4 is a schematic illustration showing a further
embodiment of the communication system of the present
invention.
DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT
Referring to Fig. 1 one application of a cellular
wireless communication system is in the field of
inventorying. One or more operators 1 each carry a
mobile unit 2, such as a portable computer. Information
concerning the items 3 to be inventoried is entered into
the mobile unit 2, for example by scanning bar code
symbols on the items 3. In order to communicate the
information obtained to a backbone house computer 4 a
plurality of access points 5 are provided each connected
to the house computer 4 and one to another, each access
point 5 together with the backbone house computer 4
forming a cell. Depending on the location of the
operator 1 it is desirable that the mobile unit should
select the optimum access point; in addition, if
conditions change, for example if the operator 1 changes
position, it is desirable that the mobile unit 2 should,
if necessary, re-associate with a new access point if the
CA 02506121 1996-10-01
current access point 5 does not allow a satisfactory
performance or the new access point offers an improved
performance. The mobile unit 2 and access points 5 are
arranged for wireless communication at radio frequencies,
5 for example, 2.4GHz in the industrial scientific medical
(ISM) band. The steps carried out by a mobile unit 2
which is not currently associated to an access point in
selecting an access point are shown in Figs. 2a and 2b.
As shown in the block diagram of Fig. 2a the mobile unit
10 (MU) firstly sends out a probe packet (6) to all access
points (AP). The probe packet, contains the mobile unit
source address but has no destination address and hence
any access point that detects the probe packet must send
a response. Accordingly, the probe packet is detected by
all access points within range (7) and each of those
access points sends out a probe response packet (8)
The form of the probe response packet is shown in
Fig. 3. The information contained therein includes the
access point address, the hopping pattern, the present
channel, time left in the present channel, the loading
factor (discussed in more detail below) and any other
timing information that may be required. Returning to
Fig. 2a the mobile unit associates with the most eligible
access point based on the probe response packets that it
receives.
Referring to Fig. 2b the mobile unit selects the
most eligible access point in the following manner:
As each probe packet response (PPR) is received (10)
the signal quality of the response is measured by
determining the received signal strength indication
(RSSI) (11). For reference, RSSI values generally vary
from 25 to 60, with good communications experienced above
approximately 35. In practice, rather than relying on a
single instantaneous value, the RSSI information for each
CA 02506121 1996-10-01
11
access point is placed in a table in the memory of the
mobile unit and is updated each time a probe response
packet is received from that access point. In order to
minimise fluctuation the RSSI value for each access point
in the table is averaged over a predetermined number of
responses. It has been found that large variations in
the RSSI values for a given access point have been
recorded even when measured by a stationary mobile unit,
varying by as much as 15 counts over one minute, and in
order to reduce the range of values and minimise "slow
thrashing" (when "thrashing", a mobile unit associates
with a first access point, then roams to a second access
point after a short period of time and then further
access points in a random manner without any long
attachment to a single access point and "slow thrashing"
may be interpreted accordingly) the averaging calculation
may include the step of discarding values outside a given
range, for example ten or more counts below the average
RSSI value.
Once the RSSI values have been calculated, an
"eligible group" of access points is selected (12),
including all access points having an RSSI value no more
than six counts below the best detected RSSI value. From
that group the access point having the lowest load factor
(LF) is determined (13,14). The load factor is a measure
of how many mobile units are currently associated with a
given access point; in the present case the load factor
is represented by a simple numerical value representing
the exact number of associated mobile units. The access
point thus selected is the most eligible access point and
the mobile unit then selects that access point for
association. If more than one access points within the
eligible group exhibit the same load factor then, of
those, the access point having the highest RSSI value is
CA 02506121 1996-10-01
12
selected as the most eligible access point and the mobile
unit associates with that access point.
The mobile units are programmed to carry out an
update probe at predetermined intervals. In the present
embodiment each mobile unit carries out a full scan,
probing all seventy nine channels, upon power up and
every thirty seconds. Full scans last approximately
looms. In addition partial scans, covering known access
points, are performed every five seconds. The probe
response packet transmitted by an access point contains
all necessary synchronisation information for a mobile
unit to latch on to the current channel of the access
point and follow the hopping pattern at any stage. In
an alternative arrangement the RSSI value for the access
point is calculated not from the strength of the probe
response signal but from the strength of the "beacon
packet" issued by the access'po'int. Each access point
issues a beacon packet every 100 milliseconds containing,
in addition to other information, timing information
similar to that contained in the probe response packet.
A slightly different approach- is taken where a
mobile unit is currently associated with an access point
but at a communication level that is unsatisfactory. An
unsatisfactory communication level may be identified, for
example, when more than fifty per cent retries, cyclic
redundancy code (CRC) errors or missed beacons are
detected. In that case the mobile unit will re-associate
using the steps illustrated in Figs. 2a and 2b except
that the access point with which the mobile unit was
experiencing poor communications will be excluded from
the eligible group of access points (see step (12) of
Fig. 2b). The in-eligible access point can, however, in
due course be re-admitted to the eligible group after a
succession of acceptable RSSI values have been observed.
CA 02506121 1996-10-01
13
It should be noted that a mobile unit experiencing poor
communication will re-associate only if an eligible
access point is identified.
In cases where a mobile unit is not experiencing an
unsatisfactory communications level (as defined above) it
makes a roaming decision every five seconds after a
partial scan. Once again the steps described above with
reference to Fig. 2b are carried out, but with the
following modifications:
1. The current access point is included in the
eligible group if its RSSI value is no more
than eleven counts below the best RSSI value.
2. When choosing the access point having the
lowest loading factor in the group, access
points having a loading factor which is more
than 75% of the loading factor of the current
access point loading factor are excluded.
The additional steps enable the mobile unit to avoid
"frivolous roaming" that is to say, re-association with
new access points when the current access point is in
fact satisfactory.
The system thus allows preemptive roaming providing
for dynamic load balancing, that is, a mobile unit may
re-associate with a new access point although it is not
experiencing poor communications with a current access
point, but the newer access point will offer considerably
improved communications. The possibility of a mobile
unit losing contact with an access point altogether and
experiencing periods where it is not communicating with
any access points, may thus be avoided.
In addition, the system has been improved by
adjusting the sensitivity so that a mobile unit will not
tend to roam from a current associated access point to
another at the rate that it would otherwise, where the
CA 02506121 1996-10-01
14
signal strengths of various access points are similar in
magnitude. Accordingly, greater stability is achieved.
In a further modification the probe packet may
include an identification of the access point that the
mobile unit is currently associated with for example, the
BSS ID. Such an arrangement would be more reliable than
the messages passed between access points relaying re-
association events.
A further embodiment of the invention is shown in
Fig. 4. In some cases it may be desirable to provide
information concerning the physical location of a mobile
unit. For example the information may be provided to a
system administrator 20 who may take action based on the
information. Alternatively the house computer 4 may take
action automatically on the basis of certain information.
For example, mobile units are often used in stock
exchanges by traders for receiving orders and executing
trades, as it is illegal to execute trades outside the
building. In order, therefore, to determine whether a
mobile unit is being removed from the building, access
points 5 are provided adjacent each exit door 21. Each
access point 5 is equipped with a directional (horn)
antenna 22 designed to provide a strong signal over a
narrow pattern in the vicinity of and covering the whole
of the doorway. According to the roaming operation of
the mobile units discussed above, any mobile unit will
associate with an access point having high signal quality
and which is lightly loaded and hence any mobile unit
passing an access point 5 over an exit door 21 (when a
mobile unit is being taken through the door) will
associate with that access point. Once the system has
detected that a mobile unit has associated with an access
point over an exit door 21 the necessary steps can be
taken by a house computer. For example an alert can be
CA 02506121 1996-10-01
sounded which may in addition disable operation of the
mobile unit. It is, of course, possible to identify
which exit door the mobile unit was being taken through
by identifying the physical location of the associated
5 access point.
In the embodiment shown in Fig. 4 a cellular
communications network is in use in a self-checkout
retail system where wireless mobile units are provided to
customers for the purpose of scanning their own
10 purchases, for example, using bar code symbols. In that
case an access point 5 provided over an exit 21 could be
used to alert the store management 20 that a scanner was
leaving the premises and to sound an alarm at the door.
Without further analysis, the foregoing will so
15 fully reveal the gist of the present invention that
others can readily adapt it for various applications
without omitting features that, from the standpoint of
prior art, fairly constitute essential characteristics of
the generical or specific aspects of this invention and,
therefore, such adaptions should and are intended to be
comprehended without the meaning and range of equivalence
of the following claims.
