`
`(12)
`
`United States Patent
`Gan et al.
`
`(10) Patent N0.:
`(45) Date of Patent:
`
`US 7,027,418 B2
`Apr. 11, 2006
`
`(54) APPROACH FOR SELECTING
`COMMUNICATIONS CHANNELS BASED ON
`PERFORMANCE
`
`(75) Inventors: Hongbing Gan, Carlton North (AU);
`Bijan Treister, KeW (AU); Efstratios
`ska?das’ Coburg (AU)
`_
`_
`(73) Asslgneei Bandspeed, 1119-, AHSIIH, TX (Us)
`
`( * ) Notice:
`
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 768 days.
`
`(21) Appl- No: 09/948,488
`
`(22) Filed;
`
`sep_ 6, 2001
`
`(65)
`
`Prior Publication Data
`US 2002/0136268 A1
`Sep. 26, 2002
`
`-
`-
`t Dt
`RltdU.S.A 1
`PP lea Ion a a
`e a 6
`(60) Provisional application No. 60/264,594, ?led on Jan.
`25, 2001.
`
`(51) Int. Cl.
`(200601)
`H04Q 7/00
`(52) US. Cl. ..................... .. 370/329; 375/132; 455/450
`(58) Field of Classi?cation Search
`370/328i334
`370/431 436 437 4 6 4
`375/132i136f
`’
`’
`4’50/4’50 451 452 1 452 2’
`See application ?le for Complete s’earcl’l hist'oliy
`'
`'
`
`(56)
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`4,716,573 A 12/1987 Bergstrom et a1.
`4,780,885 A * 10/1988 Paul et a1. ................ .. 375/267
`5,323,447 A
`6/1994 Gillis et a1.
`5,394,433 A *
`2/1995 Bantz et a1. .............. .. 375/132
`5,418,839 A
`5/1995 Knuth et a1.
`5,541,954 A
`7/1996 Emi
`5,574,979 A 11/1996 West
`5,649,291 A
`7/1997 Tayloe
`
`3/1998 Frodigh et a1. ........... .. 370/252
`5,726,978 A *
`6/1998 Sifkioja et a1~
`5,774,308 A
`7/1998 Kang et a1.
`5,781,861 A
`5,844,522 A 12/1998 Sheifer et a1.
`i
`guclenc
`t l
`5’956’642 A
`9/1999 Lar Sson e a'
`,
`,
`arsson et a1.
`6,009,332 A 12/1999 Haartsen
`6,169,761 B1
`1/2001 Marcoccia et a1.
`6,240,126 B1 *
`5/2001 Ohashi et a1. ............ .. 375/132
`6,549,784 B1* 4/2003 Kostic e161. ............. .. 455/501
`6,650,372 B1
`11/2003 Karlsson
`6,687,239 B1 *
`2/2004 Koprivica ................. .. 370/341
`(Continued)
`
`OTHER PUBLICATIONS
`
`Johnsson, HiperLAN/2-The Broadband Radio Transmission
`Technology Operating in the 5 GHZ Frequency Band, pp.
`1-22, 1999*
`
`(Continued)
`
`Primar ExamineriFrank Duon
`y
`g
`(74) Attorney, Agent, or F irmiHickman Palermo Truong &
`Becker, LLP
`
`(57)
`
`ABSTRACT
`
`An approach for selecting sets of communications channels
`involves determining the Pejl'folmance of Communications
`channels. A set of channels 1s selected based on the results
`of performance testing and speci?ed criteria. The participant
`generates data that identi?es the selected set of channels and
`provides that data to other participants of the communica
`tions network. The participants communicate over the set of
`channels, such as by using a frequency hopping protocol.
`When a speci?ed time expires or monitoring of the perfor
`mance of the channel set identi?es poor performance of the
`set of channels, the participant selects another set of chan
`nels for use in communications based on additional perfor
`mance testing. By selecting channels based on the initial
`performance testing and performance monitoring, the com
`munications network adaptively avoids channels With poor
`performance.
`
`128 Claims, 11 Drawing Sheets
`
`100 /
`
`DETERMINE PERFORMANCE OF
`COMMUNICATIONS CHANNELS
`11.0
`
`SELECT A SET OF COMMUNICATIONS
`CHANNELS
`1.1.4.
`
`I
`
`REDETERMINE PERFORMANCE OF
`COMMUNICATIONS CHANNELS
`1.1.8
`
`SELECT A NEW SET OF
`COMMUNICATIONS CHANNELS
`122
`
`Page 1
`
`Qualcomm Inc.
`Exhibit 1019
`IPR2015-00314
`
`
`
`US 7,027,418 B2
`Page 2
`
`US. PATENT DOCUMENTS
`
`6,694,147 B1* 2/2004 Viswanath et a1. ....... .. 455/517
`6,700,875 B1
`3/2004 Schroeder et al.
`6,704,346 B1* 3/2004 Mans?eld ................. .. 375/136
`6,745,034 B1
`6/2004 Wang et a1.
`6,760,317 B1
`7/2004 Honkanen et al.
`2002/0122462 A1*
`9/2002 Batra et al. ............... .. 375/132
`
`OTHER PUBLICATIONS
`Zander, Adaptive Frequency Hopping in HF communica
`tions, IEEE, pp. 99-105, 1995*
`Lawrey et al.n Adaptive Frequency Hopping for Multiuser
`OFDM, pp. 1-5, ICICS’99.*
`Gan et al, Adaptive Frequency Hopping Implementation
`Proposals for IEEE 802.15.1/2 WPAN, pp. 1-28, Nov. 2000,
`downloaded at http://grouper.ieee.org/groups/802/15/pub/
`2000/NoV00/003 67r0P802-15iTG2-AdaptiVe-Frequency
`Hopping.ppt.*
`Walter L. Davis, “A MAC Layer submission for the High
`Rate 802.153 Standard,” Project: IEEE P802.15 Working
`
`Group for Wireless Personal Area Networks (WPANs), Sep.
`2000, XP 002220853, pp. 1-57.
`Jeyhan KaraoguZ, “Multi-Rate QAM Physical Layer (8-40
`Mbps) Proposal for High Rate WPAN,” Project: IEEE
`P802.15 Working Group for Wireless Personal Area
`Networks (WPANs), Oct. 20, 2000, XP002220854, pp. 1-39.
`IEE Proc.-Commun., VOl. 142, No. 2, Apr. 1995, entitled
`“Adaptive frequency hopping in HF communications”, by J.
`Zander, PhD and G. Malmgren, MSc, (pp. 99-105).
`Fifth International Symposium on Signal Processing and its
`Applications, ISSPA ’99 Brisbane, Australia, Aug. 22-25,
`1999, entitled “Multiuser OFDM”, by E. Lawrey, (pp.
`761-764).
`European Patent Of?ce, “Communication pursuant to
`Article 96(2) EPC,” Jun. 22, 2004, 5 pages.
`“Clean Version of Amended Claims for Response to Of?cial
`Comm. From Patent Examiner,” EPO Patent Application
`No. 027091701, pp. 1-15.
`
`* cited by examiner
`
`Page 2
`
`
`
`U.S. Patent
`
`Apr. 11,2006
`
`Sheet 1 or 11
`
`US 7,027,418 B2
`
`100 /
`
`DETERMINE PERFORMANCE OF
`COMMUNICATIONS CHANNELS
`
`SELECT A SET OF COMMUNICATIONS
`CHANNELS
`LIA
`
`REDETERMINE PERFORMANCE OF
`COMMUNICATIONS CHANNELS
`LLB
`
`SELECT A NEW SET OF
`COMMUNICATIONS CHANNELS
`122
`
`FIG. 1A
`
`Page 3
`
`
`
`U.S. Patent
`
`Apr. 11,2006
`
`Sheet 2 0f 11
`
`US 7,027,418 B2
`
`SELECT A NEW SET OF
`COMMUNICATIONS CHANNELS
`1.42
`
`GENERATE NEW DATA THAT
`IDENTIFIES THE NEW SET OF
`COMMUNICATIONS CHANNELS
`14.4
`
`PROVIDE THE NEW
`IDENTIFICATION DATA TO THE
`PARTICIPANT
`1A6
`
`COMMUNICATE WITH THE
`PARTICIPANT OVER THE NEW SET
`OF COMMUNICATIONS CHANNELS
`
`DETERMINE PERFORMANCE
`DATA OF COMMUNICATIONS
`CHANNELS
`13-0
`
`SELECT A SET OF
`COMMUNICATIONS CHANNELS
`132
`
`GENERATE CHANNEL
`IDENTIFICATION DATA THAT
`IDENTIFIES THE SET OF
`COMMUNICATIONS CHANNELS
`13A
`
`PROVIDE THE CHANNEL
`IDENTIFICATION DATA TO THE
`PARTICIPANT
`13-6
`
`COMMUNICATE WITH THE
`PARTICIPANT OVER THE SET OF
`COMMUNICATIONS CHANNELS
`13.8
`
`REDETERMINE THE
`PERFORMANCE OF THE
`COMMUNICATIONS CHANNELS
`
`FIG. 1B
`
`Page 4
`
`
`
`U.S. Patent
`
`Apr. 11,2006
`
`Sheet 3 0f 11
`
`US 7,027,418 B2
`
`COMMUNICATIONS NETWORK 20.0
`
`MASTER 21.0
`
`MEMORY
`212
`
`PROCESSOR
`214
`
`TRANSCEIVER
`
`2.1.6
`
`SLAVE 229
`
`MEMORY
`222
`
`PROCESSOR
`22.4.
`
`TRANSCEIVER
`225
`
`SLAVE 23.0
`
`MEMORY
`232
`
`PROCESSOR
`23.4.
`
`TRANSCEIVER
`23.6
`
`FIG. 2
`
`Page 5
`
`
`
`U.S. Patent
`
`Apr. 11,2006
`
`Sheet 4 or 11
`
`US 7,027,418 B2
`
`an
`
`mm 6E
`
`Page 6
`
`
`
`QMU
`
`t
`
`5WMmm
`
`US 7,027,418 B2
`
`m:ms_<m_m_n_m:m_s_<m_E£m_>_$Em2o<n_
`
`
`
`
`
`
`
`tzaozxzaozxzaozx8>_mom_¢%_m%<>m_,m_$,m,_»,_%vm__n_mnoE8moE8loE855no32
`
`
`
`
`
`
`
`
`
`
`
`Aanananmanan
`
`Eam_zz<Io88mF5255$dzzéo88
`
`
`
`E15moom:2_.E,aSous:o<9><n_@a<n_zaozx
`
`mzmxomozaoo§3mms:xvmmemzEma:m:ms_<mmn_
`
`
`
`gm9%amamdam
`
`e.6_n_
`
`pm4/.08m2o<n_EHmsfim
`
`Page 7
`
`Page 7
`
`
`
`U.S. Patent
`
`Apr. 11,2006
`
`Sheet 6 0f 11
`
`US 7,027,418 B2
`
`Page 8
`
`
`
`U.S. Patent
`
`Apr. 11,2006
`
`Sheet 7 of 11
`
`US 7,027,418 B2
`
`
`
`
`
`amm.m_zz<_._oQOOG..._O59:
`
`QOOO
`
`ab._m_zz<_._o
`
`
`
`.\1n._«m:m__.mmw1,1,_/J,.mzz<Io::<um_o_
`Illklil\4\\cz_mm_m8<Emmsmmm_
`{“l"A’|!'l"\
`
`\oz_mmmmoo<
`
`an
`
`
`
`dzmmxzO_._.om_.m_w
`
`Q3
`
`/|.:|IuI1.‘J1{Il|l.\
`
`
`
`_._._.=smmiomm
`
`
`
`w._m_zz<Io::E.”a
`
`3%._mzz<_._o
`
`Safimg
`
`
`
`awn.m_zz<Io
`
`baimo
`
`
`
`ommm.m_zz<Io
`
`_..S<..._m_Q
`
`
`
`Tcmmm._m_zz<Io
`
`::<”m_o
`
`
`
`cmmm.mzz<_._o
`
`._.._D<n_mn_
`
`mm.6_u_
`
`Page 9
`
`Page 9
`
`
`
`
`
`
`U.S. Patent
`
`Apr. 11,2006
`
`Sheet 8 0f 11
`
`US 7,027,418 B2
`
`MASTER 610
`
`SLAvES 612
`
`r A \ r A \
`
`TEST NEB OF
`SEND MASTER TEST
`PACKET TD SLAvES —> RECEWED MASTER
`52g
`TEST PACKET 52.4
`
`\
`
`SEND SLAvE TEST
`TEST NEB OF
`RECE'VED SLAVE <1 PACKET TO MASTER
`TEST PACKET
`532,
`525
`
`CLASSIFY CHANNELS
`AS "BAD" CR "GOOD"
`Q35
`
`A
`RECEIVE GOOD
`SEND GOOD CHANNEL
`PACKET TO SLAVES PM CHANNEL PACKET
`WITH TIMEOUT 5A9
`5A4
`
`DEFAULT
`g'fNNEl-s
`
`SEND
`RECE|vE
`ACKNOWLEDGMENTS N_ ACKNOWLEDGEMENT TO
`FROM SLAvES
`MASTER
`6512
`
`GOTO
`BLOCK
`
`554
`
`FIG. 6A
`
`)
`
`Page 10
`
`
`
`U.S. Patent
`
`Apr. 11,2006
`
`Sheet 9 0f 11
`
`US 7,027,418 B2
`
`sLAvEs 612
`/\_
`
`\I
`
`MASTER 610
`A
`
`f
`
`GO TO
`BLOCK
`e40
`
`‘I f
`
`FROM
`BLOCK
`652
`
`HAS A
`POSITIVE
`N0 ACKNOWLEDGEMENT
`BEEN RECEIvED
`PR
`ALL
`Silt/“ES,
`55A '
`
`AFTER EXPIRATION OF
`TIMEOUT, HOP OvER
`GOOD CHANNELS
`INSTEAD OF DEFAULT FH
`CHANNELS 555
`
`\
`
`DEFAULT
`CHANNELS
`s14
`
`)
`
`\
`
`MONITOR CHANNEL PERFORMANCE OF
`GOOD CHANNEL SET
`5112
`
`¢---—‘
`
`(1) THE GCUT EXPIRED? OR
`(2) GOOD CHANNELS BECOME BAD? OR
`(3) NUMBER OF GOOD CHANNELS
`DROPPED BELOW
`THRESHOLD?
`555
`
`GOOD
`CHANNELS
`616
`
`FIG. 6B
`
`Page 11
`
`
`
`U.S. Patent
`
`Apr. 11,2006
`
`Sheet 10 0f 11
`
`US 7,027,418 B2
`
`MASTER 610
`A
`
`f
`
`SLAVES 612
`A
`
`‘1
`
`\ (T
`FROM
`BLOCK
`655
`
`RECENE "SW‘TCH BACK“
`sEND SLAVES A COMMAND TO
`__> SWITCH BACK TO DEFAULT __, MESSAGE WITH TIMEOUT
`CHANNELS" WITH TIMEOUT
`51A
`6111
`
`II
`SEND
`RECEIVE
`ACKNOWLEDGEMENTS + ACKNOWLEDGEMENT
`FROM SLAVES
`To MASTER
`6-32
`5.75
`
`HASA
`POSITIVE
`ACKNOWLEDGEMENT
`BEEN RECEIVED
`FROM ALL
`SLAVES?
`
`“55
`
`AFTER EXPIRATION OF
`TIMEOUT, HOP OVER
`DEFAULT CHANNELS
`599
`I
`REDETERMINE CHANNEL
`PERFORMANCE BY
`TESTING CHANNELS
`(E.G. RETURN TO STEP 620)
`59.4
`
`FIG. 6C
`
`GOOD
`CHANNELS
`616
`
`#JEFAULT
`
`CHANNELS
`614
`
`Page 12
`
`
`
`U.S. Patent
`
`Apr. 11,2006
`
`Sheet 11 or 11
`
`US 7,027,418 B2
`
`. _ _ _ _ _
`
`_
`
`E0252 “ HEEZ
`
`39 ‘ 292923228 mowwwooE
`
`lg _
`
`EZEE “
`
`_ _
`
`_ N3
`
`1 Q5
`
`_ a wow
`
`an
`
`mowmno
`
`405.200
`
`F GE
`
`Page 13
`
`
`
`US 7,027,418 B2
`
`1
`APPROACH FOR SELECTING
`COMMUNICATIONS CHANNELS BASED ON
`PERFORMANCE
`
`RELATED APPLICATIONS
`
`This application claims domestic priority from prior U.S.
`Provisional Patent Application Ser. No. 60/264,594, filed on
`Jan. 25, 2001, titled "ADAPTIVE FREQUENCY HOP(cid:173)
`PING-A COEXISTENCE MECHANISM FOR A FRE(cid:173)
`QUENCY HOPPING COMMUNICATION SYSTEM TO
`COEXIST WITH NON-FREQUENCY-HOPPING COM(cid:173)
`MUNICATION SYSTEMS SHARING THE SAME FRE(cid:173)
`QUENCY BAND," naming as inventors Hongbing Gan,
`Bijan Treister, and Efstratios Skafidas, the entire disclosure
`of which is hereby incorporated by reference for all purposes
`as if fully set forth herein.
`
`FIELD OF THE INVENTION
`
`The present invention generally relates to communica(cid:173)
`tions systems, and more particularly to selecting sets of
`communications channels based on channel performance.
`
`BACKGROUND OF THE INVENTION
`
`A communications network is any system or mechanism
`that provides for the exchange of information or data
`between participants. As used herein, the term "participant"
`refers to a device or mechanism that communicates with
`other devices or mechanisms. In some communications
`network arrangements, one of the participants is designated
`as a master participant, or simply as the "master." The
`master generally initiates and controls communications with
`the other participants, which are conventionally referred to
`as slave participants, or simply as "slaves." Masters may
`also be assigned other functions to perform. Although a
`master participant typically performs additional functions
`than the other participants, any participant is capable of
`performing these functions if elected as the master partici- 40
`pant.
`A frequency hopping (FH) protocol is an approach for
`wireless communications in a communications network that
`uses a frequency hopping signal transmission technique in
`which information or data is transmitted over a set of 45
`frequencies in a communications frequency band. A fre(cid:173)
`quency hopping communications system is a system that
`uses a FH protocol. The order in which the communications
`network hops among the set of frequencies is known as the
`hopping sequence.
`In contrast to FH systems, a non-frequency hopping
`(NFH) system is simply a communications system whose
`carrier does not hop over a set of frequencies. A typical NFH
`system may occupy a portion of the communications fre(cid:173)
`quency band corresponding to several frequencies used by
`an FH system.
`With the FH approach, the frequency band is broken up
`into separate frequencies, often referred to as "channels."
`The FH system transmits data on one channel, hops to the
`next channel in the hopping sequence to transmit more data,
`and continues by transmitting data on subsequent channels
`in the hopping sequence. The switching of frequencies may
`occur many times each second. The use of an FH protocol
`helps to reduce problems with interference from other
`communications systems and other interference sources. 65
`Frequency hopping also helps with fading of transmissions
`and power consumption and also provides security for the
`
`2
`transmission so that others may not intercept the data being
`transmitted because others do not know the hopping
`sequence. An example of a frequency hopping protocol is
`the Institute of Electrical and Electronics Engineers (IEEE)
`802.15.1 Wireless Personal Area Network Standard, which
`is based on the Bluetooth™ wireless personal area network
`(WPAN) technology from the Bluetooth Special Interest
`Group. The BLUETOOTH trademarks are owned by Blue(cid:173)
`tooth SIG, Inc., U.S.A. The Bluetooth protocol uses 79
`10 individual randomly chosen frequency channels numbered
`from 0 to 78 and changes the frequencies 1600 times per
`second. Examples ofNFH systems include the IEEE 802.11
`b Wireless Local Area Network (WLAN) and the IEEE
`802.15.3 next-generation WPAN, both of which operate in
`15 the 2.4 GHz Industrial, Scientific, Medical (ISM) band,
`which is an unlicensed portion of the radio spectrun1 that
`may be used in most countries by anyone without a license.
`An FH communications system may be either point-to(cid:173)
`point, meaning that communications paths are provided
`20 from one participant to another participant, or point-to(cid:173)
`multipoint, meaning that communications paths are pro(cid:173)
`vided from one participant to multiple participants.
`Typically one device of the network, such as the master,
`determines the hopping sequence that will be used by all
`25 participants of the network. The other participants of the
`network, such as slaves, are time synchronized with the
`master to maintain communications with the master. For
`example, the Bluetooth and IEEE 802.15.1 frequency hop(cid:173)
`ping protocols are point-to-multipoint systems in which the
`30 frequency hopping sequence is determined by the physical
`address of the master and the phase of hopping is determined
`by the master's clock. The "physical address" of the master
`is a unique identifier, such as a media access control (MAC)
`address, that identifies the device anywhere in the world on
`35 a network.
`Some FH communications system are configured such
`that certain devices transmit at specified times or timeslots.
`For example, slaves may respond to the master at assigned
`timeslots. As another example, in a Bluetooth FH commu(cid:173)
`nications system, the master may transmit at even-numbered
`timeslots on the hopping sequence and the slaves listen at
`those regular intervals. The master will address one slave (or
`all slaves in a "broadcast" mode), and the addressed slave
`returns back to the master at the next odd-numbered
`timeslot.
`A preamble, which is known to all the participants of the
`FH network, is used to identify the network and for the
`slaves to synchronize with the master. For example, in
`Bluetooth and IEEE 802.15.1, the known preamble is called
`50 the "channel access code."
`One problem with frequency hopping communications
`systems is that coexistence problems arise between the FH
`communications system and NFH communications systems
`that operate in the same frequency band. While the FH
`55 communications system hops over the entire frequency
`band, the NFH communications systems occupy separate
`parts of the frequency band. When the FH communications
`system hops over part of the frequency band occupied by an
`NFH communications system, there may be interference
`60 between the systems. Although the use of a FH protocol
`helps to lessen the interference problem because not all of
`the FH channels will interfere with other communications
`systems, there nevertheless remains interference on those
`channels that coincide with the NFH communications sys(cid:173)
`tems. An example of the interference situation is the coex(cid:173)
`istence problem between the frequency hopping IEEE
`802.15.1 WPAN and the non-frequency hopping IEEE
`
`Page 14
`
`
`
`US 7,027,418 B2
`
`3
`802.11b Wireless Local Area Network (WLAN) because
`both share the 2.4 GHz ISM band.
`Further, because of the dynamic nature of interference due
`to the use of devices at different times and locations,
`eventually all FH channels will experience some degree of
`interference at some time. Interference may change depend(cid:173)
`ing on when the communications systems use the band and
`the relative locations of the participants of each system to
`participants of another system. Because the participants may
`be mobile, interference may vary depending on the move(cid:173)
`ments of the participants of one system relative to the
`locations of participants of other systems. In addition, inter(cid:173)
`ference may arise from other sources, such as some con(cid:173)
`sumer appliances like microwave ovens, resulting in a
`degradation of performance of the FH communications 15
`system.
`Interference results in data transmission errors, such as an
`increase in the bit error rate (BER) or the loss of data
`packets, resulting in reduced transmission quality and per(cid:173)
`formance and the need to retransmit the data.
`One approach for managing the coexistence problem is to
`increase the power used in the transmissions so that the other
`interfering system have less of an impact on the system
`transmitting at the increased power. However, this increased
`power approach drains batteries used by the participants,
`and thus the required power increase may be impractical.
`Also, the increased power approach only benefits the system
`using the increased power and results in a bigger interfer(cid:173)
`ence impact on other systems.
`Another approach for managing the coexistence problem
`is to skip a "bad" channel that suffers from interference, such
`as by moving onto the next channel in the sequence or by
`jumping to another randomly selected channel. However,
`this skipping approach does not necessarily avoid other bad
`channels because the next channel used may also have an 35
`interference problem. Also, known "bad" and "good" chan(cid:173)
`nels may change over time due to the transient nature of
`some types of interference.
`Based on the need for wireless communications and the
`limitations of conventional approaches, an approach for
`managing interference in communications system, such as
`the coexistence problem between frequency hopping com(cid:173)
`munications systems and non-frequency hopping commu(cid:173)
`nications systems, that does not suffer from the limitations
`of the prior approaches is highly desirable.
`
`SUMMARY OF THE INVENTION
`
`Techniques are provided for selecting sets of communi(cid:173)
`cations channels based on channel performance. According 50
`to one aspect of the invention, a method selects communi(cid:173)
`cations channels for a communications system. A set of
`communications channels is selected based on the perfor(cid:173)
`mance of the communications channels and channel selec(cid:173)
`tion criteria. Then another set of communications channels
`is selected based on a later performance of the communi(cid:173)
`cations channels and the channel selection criteria.
`According to another aspect of the invention, a method is
`provided for communicating with a participant. A set of
`communications channels is selected based on the perfor(cid:173)
`mance of the communications channels and a performance
`criterion. Identification data that identifies the set of com(cid:173)
`munications channels is generated and provided to the
`participant. The set of communications channels is used for
`communicating with the participant according to a fre-
`quency hopping protocol. According to other aspects,
`another set of communications channels is selected in a
`
`65
`
`4
`similar manner when a specified criterion is satisfied, includ(cid:173)
`ing but not limited to, after expiration of a specified length
`of time, when the performance of at least one of the channels
`in the set of channels satisfies another performance criterion,
`or when a specified number of the set of channels satisfies
`yet another performance criterion.
`According to one aspect of the invention, a communica(cid:173)
`tions device is used in a network that communicates via a
`frequency hopping protocol. The communications device
`10 includes a memory that has identification data that identifies
`a set of communications channels that is selected based on
`channel performance and a performance criterion. The com(cid:173)
`munications device includes a transceiver that is communi(cid:173)
`catively coupled to the memory and that is configured to
`transmit and receive, based on the identification data, over
`the set of channels, according to a frequency hopping
`protocol. The communications device includes a processor
`for generating a measurement of channel performance based
`on receiving a packet from another device and transmitting
`20 another packet to the other device that contains data indi(cid:173)
`eating the measurement of channel performance.
`According to another aspect, another communications
`device is used in a network that communicates via a fre(cid:173)
`quency hopping protocol. The communications device
`25 includes a memory for storing sequences of instructions and
`a processor communicatively coupled to the memory. When
`the processor executes the instructions, the instructions
`cause the processor to determine the performance of com(cid:173)
`munications channels and then select a set of channels based
`30 on the performance and a performance criterion. The pro(cid:173)
`cessor generates and stores in the memory data that identi(cid:173)
`fies the set of channels and transmits the data to another
`communications device. The communications device
`includes a transceiver that is communicatively coupled to
`the memory and that is configured to transmit and receive,
`based on the data, over the set of channels according to a
`frequency hopping protocol.
`According to another aspect of the invention, a commu(cid:173)
`nications channel selector apparatus is provided. The appa-
`40 ratus is configured to determine channel performance at one
`time and select based on that performance a set of channels
`based on channel selection criteria. The apparatus is con(cid:173)
`figured to then determine the channel performance at a later
`time and select another set of channels based on that latter
`45 performance and the channel selection criteria.
`According to other aspects, the invention encompasses a
`system, a computer-readable medium, and a carrier wave
`configured to carry out the foregoing functions.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`The present invention is depicted by way of example, and
`not by way oflimitation, in the figures of the accompanying
`drawings and in which like reference numerals refer to
`55 similar elements and in which:
`FIG. lA is a flow diagram that depicts an approach for
`selecting sets of communications channels based on channel
`performance, according to an embodiment of the invention;
`FIG. lB is a flow diagram that depicts an approach for
`60 communicating with a participant using a set of good
`channels, selected according to an embodiment of the inven-
`tion;
`FIG. 2 is a block diagram that depicts a communications
`network, according to an embodiment of the invention;
`FIG. 3A is a block diagram that depicts an example format
`of a standard packet, according to an embodiment of the
`invention;
`
`Page 15
`
`
`
`US 7,027,418 B2
`
`5
`FIG. 3B is a block diagram that depicts a master test
`packet that is sent by a master to slaves to test channel
`performance, according to an embodiment of the invention;
`FIG. 3C is a block diagram that depicts a slave test packet
`that is sent by a slave to a master to provide channel
`performance measurements and to test channel performance,
`according to an embodiment of the invention;
`FIG. 4 is a block diagram that depicts a good channel
`packet sent by a master to slaves to identify a set of selected
`channels, according to an embodiment of the invention;
`FIG. SA is a block diagram that depicts the loading of a
`set of channels into a channel register, according to an
`embodiment of the invention;
`FIG. SB is a block diagram that depicts the replacement
`of bad channels with good channels in a default set of 15
`channels in a channel register, according to an embodiment
`of the invention;
`FIGS. 6A, 6B, and 6C are flow diagrams that depict
`example message sequencing for implementing adaptive
`frequency hopping, according to an embodiment of the 20
`invention; and
`FIG. 7 is a block diagram that depicts a computer system
`upon which embodiments of the invention may be imple(cid:173)
`mented.
`
`10
`
`DETAILED DESCRIPTION OF THE
`INVENTION
`
`6
`FIG. lA is a flow diagram that depicts an approach for
`selecting sets of communications channels based on channel
`performance, according to an embodiment of the invention.
`In block 110, the performance of a set of available commu(cid:173)
`nications channels is determined. For example, for a com(cid:173)
`munications system that uses 100 channels, some or all of
`the 100 channels may be tested to determine channel per(cid:173)
`formance. Other systems using the same frequency band
`may interfere with several of the 100 channels.
`In block 114, a set of communications channels to be used
`is selected based on the channel performance determined in
`block 110, one or more performance criteria, and one or
`more selection criteria. For example, a communications
`system may experience interference on channels 3 through
`5 from one communications system and on channels 50
`through 54 from another communications system. The chan-
`nel testing may indicate a high bit error rate (BER) on those
`channels. Channels may be classified by comparing the test
`results to the performance criteria. For example, the perfor(cid:173)
`mance criteria may be a specified value, or a specified
`threshold. If the BER for a channel exceeds the specified
`threshold, the channel is classified as "good," whereas
`channels with a BER that does not exceed the specified
`threshold are classified as "bad." The reason why a bad
`25 channel's performance does exceed the specified threshold
`may be due to a variety of reasons, including but not limited
`to, the channel being used by another communications
`system or noise from other interference sources, such as
`m1crowave ovens.
`After classifying the performance of the channels, a set of
`channels is selected based on the selection criteria. For
`example, the selection criteria may be to select the good
`channels but not the bad channels. Thus, by selecting the set
`of good communications channels, the communications
`system performing the channel selection may avoid inter(cid:173)
`ference present on the bad channels.
`Although this example describes the use of a particular
`type of performance criteria to classifY channels and par-
`40 ticular type of selection criteria to select from the classified
`channels, other approaches may be used to select a set of
`channels. For example, channels may be selected based on
`comparing performance results to one or more criteria
`without first classifYing the channels. Also, other criteria
`may be used, for example, that particular channels are, or are
`not, to be selected regardless of the test results.
`In block 118, the performance of the communications
`channels is determined again by additional testing. This
`additional testing may be initiated according to a specified
`schedule, such as the expiration of specified time period, or
`the additional testing may be initiated as a result of moni-
`toring and detecting new interference among the selected set
`of channels, such as from another communications system
`that previously did not cause interference. For example, in
`55 the communications system example above, the additional
`testing may be performed over some or all of the original
`100 channels.
`In block 122, a new set of communications channels is
`selected based on the channel performance determined in
`60 block 118 in a manner similar to that of block 114 above. For
`example, the new set of channels may be based on selecting
`channels that are good when the additional testing of block
`118 is performed. The new set of channels may be different
`than the good channels selected in block 112 because new
`interference typically may be present from other systems
`that were not being used at the time of the first testing of
`block 110 or that were not in sufficient proximity at the time
`
`45
`
`An approach for selecting sets of communications chan(cid:173)
`nels based on channel performance is described. In the 30
`following description, for the purposes of explanation,
`numerous specific details are set forth in order to provide a
`thorough understanding of the present invention. It will be
`apparent, however, that the present invention may be prac(cid:173)
`ticed without these specific details. In other instances, well- 35
`known structures and devices are depicted in block diagram
`form in order to avoid urmecessarily obscuring the present
`invention.
`In the following description, various embodiments of the
`invention are described in the following sections:
`I. OVERVIEW
`II. TESTING CHANNEL PERFORMANCE
`A. Special Test Packets
`B. Received Signal Strength Indicator (RSSI)
`C. Preamble Correlation
`D. Header Error Check (HEC)
`E. Cyclic Redundancy Check (CRC)
`F. Packet Loss Ratio (PLR)
`G. Forward Error Correction (FEC)
`H. Other Channel Performance Testing Considerations 50
`III. CHANNEL CLASSIFICATION
`IV. COMMUNICATING SELECTED CHANNELS TO
`PARTICIPANTS
`V. IMPLEMENTING ADAPTIVE FREQUENCY HOP(cid:173)
`PING
`VI. MONITORING CHANNELS
`VII. MESSAGE SEQUENCING AND EXAMPLE
`IMPLEMENTATION
`VIII. IMPLEMENTATION MECHANISMS
`I. Overview
`A novel approach for managing network communications
`generally involves selecting sets of communications chan(cid:173)
`nels based on channel performance. An initial set of chan(cid:173)
`nels is selected based on one or more selection criteria at the
`start-up of the communications network. Additional sets of
`channels are then periodically selected to adaptively avoid
`interference.
`
`65
`
`Page 16
`
`
`
`US 7,027,418 B2
`
`7
`of the first testing of block 110 to cause sufficient interfer(cid:173)
`ence to result in the channels being classified as bad.
`According to other aspects of the invention, the determi(cid:173)
`nation and re-determination of channel performance
`depicted by blocks 110 and 118 may be performed by a
`different entity or device than the selection of the channels
`depicted in blocks 114 and 122. In general, each step may be
`performed by a different entity, and a particular entity may
`perform any number of the steps of a particular embodiment
`of the invention.
`The determination of channel performance and the selec(cid:173)
`tion of a new set of communications channels depicted by
`blocks 118 and 122, respectively, may be repeated based on
`the same types of reasons as discussed above for block 118.
`As a result, the method depicted in FIG. 1A may adaptively
`avoid interference, even if the interference changes over
`time, by periodically retesting channel performance and
`selecting new sets of communications channels to avoid
`using channels with unacceptable performance.
`This approach avoids interference, such as from the 20
`coexistence problem between different communications sys(cid:173)
`tems that use the same part of a communications band, by
`testing performance of communications channels to deter(cid:173)
`mine a set of channels that have acceptable performance
`according to one or more performance criteria.
`By using this novel approach to adaptively select sets of
`communications channels based on channel performance at
`various times, interference problems are reduced and trans(cid:173)
`mission performance is improved for both the communica(cid:173)
`tions system that selects a set of communications channels 30
`to use and other interfering communications systems. Also,
`by reducing interference, the power level r