United States Patent
`Jaszewski et al.
`
`19
`
`USOO5933420A
`Patent Number:
`Date of Patent:
`
`11
`45)
`
`5,933,420
`Aug. 3, 1999
`
`54 METHOD AND APPARATUS FOR
`ASSIGNING SPECTRUM OF A WIRELESS
`LOCALAREA NETWORK
`
`75 Inventors: Gary M. Jaszewski, Los Gatos; David
`A. Fisher, Menlo Park; Richard C.
`Chambers, Cupertino, all of Calif.
`73 Assignee: 3Com Corporation, Santa Clara, Calif.
`
`Appl. No.: 08/640,184
`21
`22 Filed:
`Apr. 30, 1996
`(51) Int. Cl." ........................................................ H04J 1/02
`52 U.S. Cl. ............................................. 370/329; 370/343
`58 Field of Search ..................................... 455/446, 447;
`370/343, 310,328, 329, 330, 332, 338,
`342, 431, 480, 464
`
`56)
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`5,285,494 2/1994 Sprecher et al. .......................... 379/59
`OTHER PUBLICATIONS
`Chuang, J. C. -I., “Autonomous adaptive frequency assign
`ment for TDMA portable radio systems.” IEEE Transactions
`on Vehicular Technology, vol. 40, Iss. 3, p. 627-35, Aug.
`1991.
`Proxim, “Migrating Wireless LANs to 802.11” (No known
`publication date).
`Proxim, “Selecting a Wireles LAN Technology” (No known
`publication date).
`Proxim, “The Range LAN2 Site Survey Tool” (No known
`publication date).
`
`Proxim, “What is a Wireless LAN'?" (No known publication
`date).
`Proxim, Home Page, Mar. 1, 1996.
`Proxim, RangeLAN2/7500 Access Point (No known publi
`cation date).
`Proxim, RangeLAN2/7200 PCMCIA (No known publica
`tion date).
`Proxim, Building Wireless Backbones and Wireless LANs
`with Range LAN2 and Range LINK (No known publication
`date).
`Primary Examiner Huy D. Vu
`Attorney, Agent, or Firm-Kent R. Richardson; Wilson,
`Sosini, Goodrich & Rosati
`57
`ABSTRACT
`One embodiment of the invention includes assigning chan
`nels to a Set of access points coupled to a network. The
`network includes a Set of wireleSS network nodes. Each
`access point communicates, using one of the channels, to a
`Subset of the wireleSS network nodes. Each channel corre
`sponds to a different frequency range in the electromagnetic
`Spectrum. The embodiment includes the following Steps. At
`least a first access point of the Set of access points transmits
`a plurality of messages. A measure of interference between
`access points communicating on a first channel is deter
`mined from the plurality of messages. A Second Set of
`channel assignments, that results in a lower amount of
`interference between access points communicating on the
`first channel, is determined. The Second Set of channel
`assignments is assigned to the Set of acceSS points. Thus,
`non-interfering frequency assignments for the access points
`can be determined.
`
`15 Claims, 4 Drawing Sheets
`
`Network Manager
`
`O
`
`Wired Network
`f00
`
`
`
`"Where are you'
`Message 150
`(Channel 1)
`
`Access Point 1 11
`Present Channel: 3
`(New Channel: 3)
`
`Me",
`(Channel 7)
`
`Access Point 4 114
`Present Channel: 7
`(New Channel: 7)
`
`"I on here'
`Message 165
`(Channel 4)
`
`
`
`Access Point 3 15
`Present Channel: 4
`(New Channel: 5)
`
`
`
`
`
`
`
`
`
`
`
`
`
`'I am here'
`Message 162
`(Channel 3)
`
`Access Point 2 12
`Present Channel: 3
`(New Channel: 1)
`
`war
`
`- 120
`
`
`
`Interference
`Source
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Network Node
`
`Ex. 1014 / Page 1 of 11
`ERICSSON v. UNILOC
`
`

`

`U.S. Patent
`U.S. Patent
`
`Aug. 3, 1999
`Aug. 3, 1999
`
`Sheet 1 of 4
`Sheet 1 of 4
`
`5,933,420
`5,933,420
`
`
`
`WLyjUlogsseooy
`
`
`
`ZLijeuupugjueseld
`
`(Z:}euuoy)AN)
`
`79}abossay
`
`(ZJeuuy)
`
`WT=La
`
`
`
`
`
`Ex. 1014 / Page 2 of 11
`ERICSSON v. UNILOC
`
`(G:J@uUDy)MAN)OPONOMENy:J@uUDY)
`
`UESeldepONLOMIENGi
`
`€yulogssaooy
`ALye
`
`
`
`|
`
`
`
`
`
`L°Old@DON4JOM}ON
`
`201~~a)10k
`
`OU18}1HNY,oy,=S5\SSWy=Cy
`
`9C
`
`YJOMJONP24!M
`
`Oot
`
`
`
`JeBpuny,44OMJON
`
`OLE
`
`“>
`
`wnok24D3J9UM,,
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Qs,ebpssay
`
`‘ou04g)\AA79,ebossay(|494WOJ,
`
`
`
`SsevoVaceouaed021”|HL|}UlOg
`Ssesoy1(¢jauudy))
`“TaUUDUNMeGhOSpUlOg
`
`(|:jauuoysNaN)§:jauuDyjUuEseld
`
`
`90U9J9}13}U]
`
`901N0S
`
`Ex. 1014 / Page 2 of 11
`ERICSSON v. UNILOC
`
`
`
`
`
`

`

`U.S. Patent
`
`Aug. 3, 1999
`
`Sheet 2 of 4
`
`5,933,420
`
`210
`
`
`
`All
`Access Points
`Processed for A
`Channels?
`
`212
`Transmit "Where are you' Message
`
`
`
`214
`
`
`
`each 'I am here'
`Message Received
`
`
`
`Store the Received Signal Strength
`
`216
`
`230
`
`250
`
`220
`
`240
`
`260
`
`FIG. 2
`
`Ex. 1014 / Page 3 of 11
`ERICSSON v. UNILOC
`
`

`

`U.S. Patent
`U.S. Patent
`
`Aug. 3, 1999
`Aug. 3, 1999
`
`Sheet 3 of 4
`Sheet 3 of 4
`
`5,933,420
`5,933,420
`
`
`PL|DD07]
`lsg]oue|VsTo8(90].
`py}UlO”dPEEEtt
`4oqubien©quiog
`DDO|pool
`
`
`
`
`
`
`
`49440)"JDeN
`
`
`
`
`
`ohk
`
`
`
`248
`
`ºg
`
`! Gº
`
`SS900Y8/991
`
`JoquBian
`
`8/90]
`
`ELE
`
`sseo0y
`
` vey9]0wanuea|VsToPeonped}91|}UOD|391]}U0D||SUD
`
`
`
`
`
`| G || 57 || Z | 58 || ? || I || %,
`
`|0907]
`
`HL
`
`Joqublan
`
`@]q0|
`
`LS
`
`4oqublaN
`
`3/qb]
`
`D907]
`
`|ouBIS
`
`4y}6ual4S
`
`sseooy
`
`f}Ulod
`
`&
`
`8 "$) I „H
`
`Ex. 1014 / Page 4 of 11
`ERICSSON v. UNILOC
`
`Ex. 1014 / Page 4 of 11
`ERICSSON v. UNILOC
`
`
`
`
`

`

`U.S. Patent
`
`Aug. 3, 1999
`
`Sheet 4 of 4
`
`5,933,420
`
`Neor
`Conflict
`Indicotor
`428
`
`Proximity
`Indicator
`425
`
`Other Indicator
`429
`
`Recommended
`Channel
`423
`D-3
`
`Direct Conflict Indicator
`427
`Access Point
`Current
`Identifier
`Chonnel
`420
`Frequency Assignment \
`\
`A-N
`/
`I
`-YNYCurrenN Proximity / Recomended
`r
`NS Access Point 1
`1
`1E
`S. Access Point 2
`3
`S. Access Point 3
`5
`NS Access Point 4
`7
`Status
`
`
`
`
`
`
`
`
`
`also
`
`
`
`
`
`
`
`
`
`
`
`400
`Channel Assignment
`Display
`
`Channel Assignment
`Display
`(After Channel Reassignment)
`400
`
`
`
`Frequency Assignment
`
`Proximity Indicator
`(Showing Reduced Conflicts)
`426
`
`^
`Proximity
`
`y
`
`Recommended
`
`2 7 .
`
`2 3
`2 5
`
`FIG. 4
`
`Ex. 1014 / Page 5 of 11
`ERICSSON v. UNILOC
`
`

`

`1
`METHOD AND APPARATUS FOR
`ASSIGNING SPECTRUM OF A WIRELESS
`LOCALAREANETWORK
`
`5,933,420
`
`THE BACKGROUND OF THE INVENTION
`1. The Field of the Invention
`This invention relates to the field of wireless local area
`networks (LANs). In particular, the invention relates to
`assigning spectrum to acceSS points in a wireleSS LAN.
`2. A Description of the Related Art
`Computer networkS Supply data and Services to the com
`puters and devices connected to the network. Traditionally,
`the connection to the network has been through a wired
`medium Such as coaxial cable, fiber optics, twisted pair, etc.
`However, there are a number of applications that benefit
`from a completely, or partially, mobile computer (or other
`device). Such computers connect to the network using
`wireleSS communications. WireleSS communications rely on
`data transferS using radio transmitters and receivers.
`A wireleSS LAN includes access points and wireleSS
`network nodes. The access points connect wireleSS network
`nodes to the wired part of the LAN or to some other wireless
`part of the LAN. An access point communicates, using
`wireleSS communications, with the wireleSS network nodes
`in that access point's communications area. Thus, an acceSS
`point maintains a number of Simultaneous wireleSS commu
`nications links with a number of wireleSS network nodes.
`The access points and the wireleSS network nodes include
`transceivers (transmitters and receivers) to establish and
`maintain the wireleSS communications links. The transceiv
`erS transmit and receive signals in the electromagnetic
`spectrum, for example, in the infrared spectrum, at 902 MHz
`or at 2.4 GHz.
`The acceSS points typically Support multiple channels.
`This allows two or more access points, communicating on
`different channels, to have overlapping coverage areas.
`Different channels can be Supported by access points in
`different ways. For example, ProXim, Inc. Supplies a wire
`less LAN product line called RangelLAN2TM. The Range
`LAN2 uses frequency hopping spread spectrum communi
`cations. A RangeLAN2 transmitter hops from frequency to
`frequency while transmitting to a receiver. Different chan
`nels are Supported by different, orthogonal, hopping
`Sequences. Another technique is called direct Sequence
`spread spectrum (DSSS) communications. DSSS breaks the
`electromagnetic spectrum into a number of Sub-bands. Each
`Sub-band corresponds to a different channel.
`One of the problems with DSSS communications, or any
`communications technique where a channel corresponds to
`a specific part of Spectrum, is that acceSS points with
`overlapping coverage areas need to be assigned to different
`channels. If access points with overlapping coverage areas
`are not assigned to different channels, then the transmissions
`will interfere with each other. This leads to a need to assign
`different channels to the acceSS points that have overlapping
`cOVerage areas.
`To adjust for changes in the wireleSS communications
`environment, new access points may be added or acceSS
`points may need to be moved. This may change the over
`lapping areas of the access points, possibly causing Some
`access points to interfere with other access points. Thus,
`what is needed is a method and apparatus for displaying the
`amount of interference between access points and for gen
`erating a new set of channel assignments for the acceSS
`points that will reduce, or eliminate, the interference of the
`acceSS points.
`
`15
`
`25
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`2
`A SUMMARY OF THE INVENTION
`A method and apparatus for maintaining non-interfering
`frequency assignments of wireleSS-based computer network
`ing products is described.
`One embodiment of the invention includes assigning
`channels to a set of access points coupled to a network. The
`network includes a Set of wireleSS network nodes. Each
`access point communicates, using one of the channels, to a
`Subset of the wireleSS network nodes. Each channel corre
`sponds to a different frequency range in the electromagnetic
`Spectrum. The embodiment includes the following Steps. At
`least a first access point of the Set of access points transmits
`a plurality of messages. A measure of interference between
`access points communicating on a first channel is deter
`mined from the plurality of messages. A Second Set of
`channel assignments, that results in a lower amount of
`interference between access points communicating on the
`first channel, is determined. The Second Set of channel
`assignments is assigned to the Set of acceSS points. Thus,
`non-interfering frequency assignments for the access points
`can be determined.
`In one embodiment, each acceSS points transmits a mes
`Sage requesting all the acceSS points that detect the message
`to reply. Each acceSS point measures the Strengths of the
`reply messages to determine the radio proximity of that
`access point's neighbors. The reply messages indicate to
`what degree other access points are directly interfering with
`a given acceSS points wireleSS communications, by com
`municating on the same channel as that access point. The
`reply messages also indicate which neighbors are transmit
`ting on channels that are near the channel being used by an
`access point. The reply messages also indicate which neigh
`bors can be detected by an access point but are assigned to
`channels that neither directly or nearly interfere. In one
`embodiment, the radio proximity information is tabulated by
`a network manager. The table indicates to what degree each
`access point is directly conflicting with any neighboring
`access points, given that acceSS points present channel
`assignment. The table also indicates near conflicts
`(neighbors communicating on near channels) and other
`Signals detected for each access point.
`In one embodiment, the radio proximity information is
`processed to reduce or eliminate direct conflicts and near
`conflicts; thereby, Significantly improving the wireleSS com
`munications of the network. In one embodiment, an iterative
`process is used to find better channel assignments by com
`paring any possible new channel assignments with the
`previous best (lowest amount of direct and/or near conflict)
`channel assignments.
`In one embodiment, the new channel assignments are then
`displayed to the user with the radio proximities shown
`graphically. The user can then change any of these new
`assignments before the new assignments are transmitted to
`the access points.
`Although many details have been included in the descrip
`tion and the figures, the invention is defined by the Scope of
`the claims. Only limitations found in those claims apply to
`the invention.
`
`A BRIEF DESCRIPTION OF THE DRAWINGS
`The figures illustrate the invention by way of example,
`and not limitation. Like references indicate Similar elements.
`FIG. 1 illustrates a wireless local area network (LAN)
`determining the channel assignments for the access points in
`the LAN.
`
`Ex. 1014 / Page 6 of 11
`ERICSSON v. UNILOC
`
`

`

`5,933,420
`
`3
`FIG. 2 illustrates determining and assigning a new Set of
`channel assignments for the acceSS points in the LAN of
`FIG. 1.
`FIG. 3 illustrates the tables used to generate the new set
`of channel assignments.
`FIG. 4 illustrates a graphical user interface for displaying
`the levels of conflict between access points and for allowing
`a user to reassign channel assignments.
`THE DESCRIPTION
`
`15
`
`4
`by the access point 1 111 and the access point 2 112. One
`embodiment of the invention detects the interference
`between the two access points, notes the existence of the
`jamming from the interference Source 120, and generates a
`new set of channel assignments for the acceSS points that
`reduces the communications conflict due to the interference
`between the two acceSS points and the jamming. The com
`munications conflict includes a measure of the radio proX
`imity of access points that communicate on the Same, or a
`near, channel.
`AS noted, the invention also attempts to generate a Set of
`channel assignments that reduces the amount of near conflict
`between two or more access points. A near conflict occurs
`when overlapping acceSS points use channels that are near to
`each other in the electromagnetic Spectrum. For example, if
`the access point 1 111 uses channel three, out of eleven
`possible channels, and the acceSS point 2 112 uses channel
`four, then these two acceSS points are Said to be using two
`channels near each other. For better wireleSS communica
`tions performance, it is desirable to have the access points,
`in close radio proximity, use channels that are further apart
`than a Single channel. For example, it is more desirable that
`access point 2 112 use channel one or Some other channel
`further away from channel three in the electromagnetic
`Spectrum.
`Generally, to generate a new set of channel assignments,
`one embodiment of the invention first determines the
`amount of communications conflict with other Sources for
`each of the access points for their present channels. The
`amount of communications conflict indicates the amount of
`interference, from other radio transmitters, experienced by a
`given access point for a given channel. Next, the amount of
`communications conflict for all the access points is tabu
`lated. If possible, a new set of channel assignments is
`generated that results in a reduced amount of communica
`tions conflict. Finally, the new set of channel assignments
`are provided to the access points So that they can Switch
`channels. Thus, changes in the wireleSS communications
`environment can be compensated for by one embodiment of
`the invention.
`One of the first Steps in determining the amount of
`communications conflict is to learn the neighbor access
`points for each access point. Each access point transmits a
`“Where are you' message 150 on each channel. The mes
`Sage 150 includes an identifier (e.g., a network address of the
`access point, or Some unique identifier) of the transmitting
`access point. For example, the access point 1 111 transmits
`the message 150 on each channel.
`In one embodiment, the message 150 is transmitted at a
`higher power than normal transmissions to the wireleSS
`network nodes. This is because it is possible that two access
`points cannot normally detect each other's presence at
`nominal Signal output levels, but that a wireleSS network
`node, positioned to communicate with both access points,
`may be able to detect signals from both of those nodes. The
`message 150 includes an identifier identifying the source of
`the message 150.
`The access points that detect the message 150 then reply
`with an “I am here” message (e.g., the access point 2 112
`detected the message 150 and responds with an “I am here'
`message 162; Similarly a message 163 and a message 164
`are transmitted by the access point 3 113 and the access point
`4 114, respectively). The “I am here” message includes an
`identifier (e.g., a network address, or Some unique identifier)
`of the transmitting access point of the “I am here” message.
`The “I am here' message is transmitted on the channel used
`to receive the “Where are you' message. Optionally, the “I
`
`25
`
`A Wireless LAN
`FIG. 1 illustrates a wireless local area network (LAN)
`determining the channel assignments for the access points in
`the LAN. The LAN of FIG. 1 is illustrative only and is not
`the only network in which one embodiment of the invention
`operates.
`The wired network 100 includes: a wired media; a number
`of wireless access points (an access point 1 111, an access
`point 2112, an access point 3 113 and an access point 4114);
`and, a network manager 110. The wired media includes one
`or more of coaxial cable, twisted pair, fiber optics, and any
`other media that Support wired communications. In one
`embodiment, the wired media is replaced by a wireleSS
`communications network (e.g., RangeLINKTM from Proxim,
`Inc.). The access points communicate with the network
`manager 110 over the wired media.
`The network manager 110 includes a computer Such as an
`IBM compatible PC, a Sun workstation, a Macintosh
`computer, or a specialized network management device. In
`any case, the network manager 110 includes a memory for
`Storing information and a proceSS for accessing the infor
`mation and manipulating the information.
`The access points communicate with a number of wireless
`network nodes (e.g., a network node 101, a network node
`102, and a network node 103). Each access point and each
`wireleSS network node includes a transceiver. Each trans
`ceiver Supports wireleSS communications. One embodiment
`of the access point 2 112 is described in the U.S. patent
`application Ser. No. 08/394,378, filed Feb. 24, 1995.
`Each acceSS point communicates with its Set of wireleSS
`network nodes using a Specific channel. In the example of
`FIG. 1, the access point 2112 uses channel three, the acceSS
`point 1 111 also uses channel three, the access point 3 113
`uses channel four, and the acceSS point 4 114 uses channel
`SCWC.
`The following discussion relates to how the access point
`2112 communicates with the network node 101, the network
`node 102 and the network node 103. However, this discus
`Sion applies to any of the access points and any wireleSS
`network node. Importantly, the access point 2 112 commu
`50
`nicates with the network node 101, the network node 102
`and the network node 103, using a single channel (channel
`three). The channel corresponds to a specific portion of the
`electromagnetic Spectrum. In this example, the access point
`1 111 is also communicating on channel three. AS the
`network node 103 can detect messages from both the acceSS
`point 1111 and the access point 2112, the messages interfere
`with each other. The interference is undesirable.
`When a new access point is added to the wireleSS network,
`an access point is moved, or a Source of interference jams or
`degrades the quality of the communications from the acceSS
`point to the wireleSS network nodes, one or more acceSS
`points may have to change their channel. For example, in
`FIG. 1, assume that access point 1111 has been added to the
`network and that an interference Source 120 has begun
`jamming the communications channel used by the acceSS
`point 2112. Also assume that the same channel is being used
`
`35
`
`40
`
`45
`
`55
`
`60
`
`65
`
`Ex. 1014 / Page 7 of 11
`ERICSSON v. UNILOC
`
`

`

`5,933,420
`
`15
`
`25
`
`35
`
`40
`
`S
`am here' messages are Sent at the increased power level.
`This helps ensure that transmitting acceSS point of the
`“Where are you' message receives the “I am here” mes
`SageS.
`The transmitting access point of the “Where are you”
`message measures the received signal Strength of the “I am
`here' messages. Thus, each access point learns the Signal
`Strength of its neighbors.
`Optionally, each access point includes a device for detect
`ing interference on one or more channels. Each access point
`then also includes an amount of interference for each
`channel.
`The network manager 110 collects the received signal
`Strengths information to determine the amount of commu
`nications conflict among the access points using their
`present channel assignments. The network manager 110 then
`generates a set of new channel assignments that results in a
`reduced amount of communications conflict among the
`access points. In the example of FIG. 1, for the new channel
`assignments, the access point 2112 is assigned channel one,
`the access point 1 111 keeps channel three, the access point
`3 113 is assigned channel five, and the access point 4 114
`keeps channel seven. The network node 103 can now
`communicate with the access point 2 112 without interfer
`ence from the access point 1111.
`In one embodiment, the network manager 110 generates
`the Set of new channel assignments So that only a few acceSS
`points need change their channels. By minimizing the num
`ber of access points that need change their channel, any
`disruptions of communications between the acceSS points
`and the wireleSS network nodes are minimized.
`New Channel ASSignments
`FIG. 2 illustrates determining and assigning a new set of
`channel assignments for the acceSS points in the LAN of
`FIG. 1. First information is obtained about the neighboring
`access points and then the new set of channel assignments is
`generated and broadcast. Step 210 through Step 216 ensure
`that each acceSS point transmits a “Where are you' message
`150 and measures the signal strength of any received “I am
`here' messages. At Step 210, a test is made to determine
`whether each access point in the LAN has sent the “Where
`are you' messages. In one embodiment, the network man
`ager 110 Sends a message to each acceSS point, in turn, to
`execute Step 212 through Step 216. The network manager
`110 then performs step 220 through step 260.
`In one embodiment, prior to transmitting the “Where are
`you' messages 150, an access point halts communications
`with its wireless network nodes. This is because the “Where
`are you' messages 150 are transmitted for each channel. AS
`the network nodes are communicating with the access point
`on a specific channel, and the acceSS point needs to transmit
`messages on different channels, if the communications were
`not halted, the network nodes would lose contact with the
`access point as it Switched channels.
`At Step 212, a given acceSS point transmits a “Where are
`you' message 150 on a first channel. As noted above, the
`“Where are you' message 150 includes an identifier iden
`tifying the transmitting access point. For example, the
`message 150 from the access point 1 111 includes the
`address of the access point 1111. Step 212 is executed for
`each channel for each access point.
`In response to the “Where are you' message 150, any
`neighbor acceSS points that detect the message, respond with
`their own "I am here' message. For example, assume that
`the access point 1 111 transmits a “Where are you' message
`150 on channel three and only the access point 2 112 is
`communicating on channel three, then only the access point
`
`45
`
`50
`
`55
`
`60
`
`65
`
`6
`2 112 will transmit an “I am here” message (assuming that
`the access point 2112 detected the “Where are you' message
`150). While looping through step 210 through step 216, step
`212 is executed for each channel for the acceSS point 1 111,
`resulting in three “I am here” messages 162, 163 and 164
`being Sent by the other access points.
`At Step 214 and Step 216, the given acceSS point receives
`and processes any "I am here” messages from any neighbor
`access points. At Step 214, a test is made to ensure that all
`the received “I am here” messages are processed in response
`to a given “Where are you' message 150 on a given channel.
`In one embodiment, an acceSS point uses a timeout to
`determine if all of the “I am here” messages have been
`received. For example, when the access point 1 111 trans
`mits the “Where are you' message 150, the access point 1
`111 starts a counter. The access point 1 111 then begins
`processing any received “I am here' messages. The acceSS
`point 1 111 then Stops listening for "I am here' messages
`when the counter reaches a predetermined value (e.g., after
`thirty Seconds).
`At step 216, the transmitting access point of the “Where
`are you' message 150 tests the received signal Strength of
`the “I am here” messages on the given channel. The access
`point then Saves the received signal Strength, and the iden
`tifier of the sender of the “I am here” message, for each
`received "I am here” message. In one embodiment, the
`access point also Saves the channel used by the Sender of the
`“I am here” message. Each access point maintains a local
`neighbors table that holds this information.
`For example, as Step 214 and Step 216 are executed,
`during the step 210 through step 216 loop for each channel
`for the access point 1 111, the following information is
`Stored by the access point 1111: access point 2112 detected
`at Signal Strength eight on channel three; access point 3 113
`detected at Signal Strength two on channel four, and access
`point 4114 detected at Signal Strength five on channel Seven.
`Optionally, before, or after Step 212, a Step can be
`included for detecting any interference from outside Sources
`for a given channel of a given access point. For example, if
`the access point 2 112 detects interference on channels one
`through five as a result of the interference source 120, then
`this information is also Stored by the access point 2 112.
`During the generating of the new channel assignments, these
`jammed channels will be excluded as possible channels for
`the access point 2 112.
`After step 210 through step 216 have been completed for
`each channel for each access point, then Step 220 through
`step 260 are performed. At step 220, a conflict level table (or
`conflict table) is generated from all the local neighbors
`tables. The conflict table defines, for each access point, the
`present channel used, the amount of direct conflict, the
`amount of near conflict and the amount of the other signals
`detected. The amount of direct conflict corresponds to the
`total Signal Strength of “I am here' messages received by an
`access point on the present channel of that access point. The
`amount of near conflict corresponds to the total Signal
`Strength of “I am here” messages received by an access point
`on channels near to that access point's present channel. The
`amount of other Signals detected corresponds to the total
`Signal Strength of "I am here' messages received by an
`access point on channels that are neither the present channel
`nor the near channels.
`In one embodiment, before determining the total received
`Signal Strength, an average detected Signal Strength is first
`determined. The average detected Signal Strength corre
`sponds to the average of the received signal Strength of a first
`message from a first access point to a Second access point
`
`Ex. 1014 / Page 8 of 11
`ERICSSON v. UNILOC
`
`

`

`15
`
`7
`and the received Signal Strength of a Second message from
`the Second acceSS point to the first access point. For
`example, if the access point 1111 receives the “I am here”
`message 162, from acceSS point 2112, at a Signal Strength of
`eight, and the access point 2 112 receives an “I am here'
`message, from access point 1 111, at a Signal Strength of
`nine, then the average detected Signal Strength is eight and
`one half.
`At step 230, a new (or recommended) set of channel
`assignments are generated from the conflict table. The new
`Set of channel assignments results in a lower amount of
`conflict in the conflict table. In Some cases, a new set of
`channel assignments that result in a lower amount of conflict
`may not exist. In Such cases, the network administrator
`(LAN administrator, or some other user) is notified of this
`fact.
`A number of techniques are used in step 230 to determine
`an alternative set of channel assignments. For example, in
`one embodiment, the conflict table is Sorted, first on direct
`conflict values, then on near conflict values. Next, the acceSS
`point with the highest conflict value is assigned to a different
`channel. The conflict table is then recomputed to determine
`whether the new channel assignment results in no direct
`conflict for the access point. If not, then a different channel
`is Selected for the access point. The above Steps are repeated
`until a channel assignment for the acceSS point is found that
`results in no direct conflict. The new table is then resorted
`and the above StepS are repeated until all the access points
`have Zero direct conflict values. In one embodiment, the
`above Steps are repeated until the access points have a
`minimal amount of direct conflict. In one embodiment, after
`the direct conflicts are reduced, the channel assignments are
`altered to result in a lower amount of near conflict. In one
`embodiment, the channel assignments are altered to result in
`as few channel reassignments as possible while Still elimi
`nating all of the direct conflicts.
`In one embodiment, a number of conflict tables are
`created. Each conflict table includes only those access points
`that are within radio proximity (i.e., have a non-zero value
`for the direct conflict, near conflict or other signal detection)
`of at least one other access point in the table. Each table is
`then processed Separately to generate a new set of channel
`assignments for the access points in that table. Generating a
`number of conflict tables can greatly reduce the number of
`calculations that need to be performed to generate the new
`channel assignments. This is because determining the new
`channel assignments becomes Significantly more difficult for
`each additional access point in a table (i.e. the new channel
`assignments problem is greater than O(n)).
`In one embodiment, the Step 230 only generates a set of
`new channel assignments that results in no direct conflicts.
`This reduces the number of access points that will have to
`change their channel, thus, reducing the number of wireleSS
`network nodes that will have to change their channels and
`thereby reducing the impact on the network's performance.
`If the interference Sources are also included in the new
`channel assignment generation process, then a Set of avail
`able channels is first determined for each access point. The
`Set of available channels represents all the channels that are
`not being jammed by an interference Source 120 for a given
`access point. Note, that in one embodiment, the LAN
`60
`administrator can identify a set of unusable channels for an
`access point. This is particularly useful where the interfer
`ence source 120 is intermittent. For example, if the inter
`ference Source 120 was a microwave oven that jams chan
`nels three through five of the access point 1 111, then the
`LAN administrator can set the unusable channels for the
`access point 1 111 to be channels three through five.
`
`45
`
`50
`
`55
`
`65
`
`5,933,420
`
`25
`
`35
`
`40
`
`8
`At step 240, the conflict level information, from the
`conflict table, is displayed. In one embodiment, the conflict
`level information is displayed on the network manager's 110
`display as shown in FIG. 4.
`At step 250, the network administrator can modify the
`new channel assignments. This provides the network admin
`istrator with flexibility. A network administrator may wish a
`particular access point to be assigned to a particular channel,
`may know that a new access point will be added to the
`network and/or may want to reserve a channel for that access
`point, or for Some other reason change the new channel
`assignments.
`At step 260, the network manager 110 sends the new
`channel assignments to the access points. The access points
`that have new channels then transmit the new channel to
`their wireless network nodes. The wireless network nodes
`and the access points then begin communicating on the new
`channels. Optionally, step 240