111111
`
`1111111111111111111111111111111111111111111111111111111111111
`US007027418B2
`
`c12) United States Patent
`Gan et al.
`
`(10) Patent No.:
`(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
`Skafidas, Coburg (AU)
`
`(73) Assignee: Bandspeed, Inc., Austin, 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 Al
`
`Sep. 26, 2002
`
`Related U.S. Application Data
`
`(60) Provisional application No. 60/264,594, filed on Jan.
`25, 2001.
`
`(51)
`
`Int. Cl.
`H04Q 7100
`(2006.01)
`(52) U.S. Cl. ....................... 370/329; 375/132; 455/450
`(58) Field of Classification Search ........ 370/328-334,
`370/431, 436, 437, 464, 465; 375/132-136;
`450/450, 451, 452.1, 452.2
`See application file for complete search history.
`
`(56)
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`4,716,573 A
`4,780,885 A *
`5,323,447 A
`5,394,433 A *
`5,418,839 A
`5,541,954 A
`5,574,979 A
`5,649,291 A
`
`12/1987 Bergstrom eta!.
`10/1988 Paul eta!. .................. 375/267
`6/1994 Gillis et a!.
`2/1995 Bantz eta!. ................ 375/132
`5/1995 Knuth eta!.
`7/1996 Emi
`11/1996 West
`7 I 1997 Tayloe
`
`5,726,978 A *
`5,774,808 A
`5,781,861 A
`5,844,522 A
`5,873,036 A
`5,898,928 A
`5,956,642 A
`6,009,332 A
`6,169,761 B1
`6,240,126 B1 *
`6,549,784 B1 *
`6,650,872 B1
`6,687,239 B1 *
`
`............. 370/252
`
`3/1998 Frodigh et a!.
`6/1998 Siirkioja et a!.
`7/1998 Kang eta!.
`12/1998 Sheffer et a!.
`2/1999 Vucetic
`4/1999 Karlsson et a!.
`9/1999 Larsson et a!.
`12/1999 Haartsen
`112001 Marcoccia et a!.
`5/2001 Ohashi eta!. .............. 375/132
`4/2003 Kostic eta!. ............... 455/501
`11/2003 Karlsson
`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)
`
`Primary Examiner-Frank Duong
`(7 4) Attorney, Agent, or Firm-Hickman Palermo Truong &
`Becker, LLP
`
`(57)
`
`ABSTRACT
`
`An approach for selecting sets of communications channels
`involves determining the performance of communications
`channels. A set of channels is selected based on the results
`of performance testing and specified criteria. The participant
`generates data that identifies the selected set of channels and
`provides that data to other participants of the communica(cid:173)
`tions network. The participants communicate over the set of
`channels, such as by using a frequency hopping protocol.
`When a specified time expires or monitoring of the perfor(cid:173)
`mance of the channel set identifies poor performance of the
`set of channels, the participant selects another set of chan(cid:173)
`nels for use in communications based on additional perfor(cid:173)
`mance testing. By selecting channels based on the initial
`performance testing and performance monitoring, the com(cid:173)
`munications network adaptively avoids channels with poor
`performance.
`
`128 Claims, 11 Drawing Sheets
`
`100
`
`I
`
`0001
`
`Marvell Semiconductor, Inc.
`MediaTek Inc.
`MediaTek USA, Inc.
`Exh. 1015
`IPR of U.S. Pat. No. 7,477,624
`
`

`

`US 7,027,418 B2
`Page 2
`
`U.S. PATENT DOCUMENTS
`6,694,147 B1 *
`6,700,875 B1
`6,704,346 B1 *
`6,745,034 B1
`6,760,317 B1
`2002/0122462 A1 *
`
`2/2004 Viswanath et al.
`3/2004 Schroeder et a!.
`3/2004 Mansfield ................... 375/136
`6/2004 Wang et a!.
`7/2004 Honkanen eta!.
`9/2002 Batra et a!. ................. 375/132
`
`. ........ 455/517
`
`OTHER PUBLICATIONS
`
`Zander, Adaptive Frequency Hopping in HF communica(cid:173)
`tions, IEEE, pp. 99-105, 1995.*
`Lawrey et al.n Adaptive Frequency Hopping for Multiuser
`OFDM, pp. 1-5, ICICS'99.*
`Gan et a!, 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/00367rOP802-15_TG2-Adaptive-Frequency(cid:173)
`Hopping.ppt. *
`Walter L. Davis, "A MAC Layer submission for the High
`Rate 802.15.3 Standard," Project: IEEE P802.15 Working
`
`Group for Wireless Personal Area Networks (WPAN s ), 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.
`lEE 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 Office, "Communication pursuant to
`Article 96(2) EPC," Jun. 22, 2004, 5 pages.
`"Clean Version of Amended Claims for Response to Official
`Comm. From Patent Examiner," EPO Patent Application
`No. 02709170.1, pp. 1-15.
`
`* cited by examiner
`
`0002
`
`

`

`U.S. Patent
`
`Apr. 11, 2006
`
`Sheet 1 of 11
`
`US 7,027,418 B2
`
`100 I
`
`DETERMINE PERFORMANCE OF
`COMMUNICATIONS CHANNELS
`11Q
`
`SELECT A SET OF COMMUNICATIONS
`CHANNELS
`ill
`
`REDETERMINE PERFORMANCE OF
`COMMUNICATIONS CHANNELS
`.ill
`
`SELECT A NEW SET OF
`COMMUNICATIONS CHANNELS
`122
`
`FIG. 1A
`
`0003
`
`

`

`U.S. Patent
`
`Apr. 11, 2006
`
`Sheet 2 of 11
`
`US 7,027,418 B2
`
`SELECT A NEW SET OF
`COMMUNICATIONS CHANNELS
`142.
`
`GENERATE NEW DATA THAT
`IDENTIFIES THE NEW SET OF
`COMMUNICATIONS CHANNELS
`.1M
`
`PROVIDE THE NEW
`IDENTIFICATION DATA TO THE
`.1Afi
`PARTICIPANT
`
`COMMUNICATE WITH THE
`PARTICIPANT OVER THE NEW SET
`OF COMMUNICATIONS CHANNELS
`ill
`
`DETERMINE PERFORMANCE
`DATA OF COMMUNICATIONS
`13fi
`CHANNELS
`I
`SELECT A SET OF
`COMMUNICATIONS CHANNELS
`132.
`
`I
`GENERATE CHANNEL
`IDENTIFICATION DATA THAT
`IDENTIFIES THE SET OF
`COMMUNICATIONS CHANNELS
`.134
`
`I
`PROVIDE THE CHANNEL
`IDENTIFICATION DATA TO THE
`PARTICIPANT
`13Q
`I
`COMMUNICATE WITH THE
`PARTICIPANT OVER THE SET OF
`COMMUNICATIONS CHANNELS
`
`~
`
`I
`REDETERMINE THE
`PERFORMANCE OF THE
`COMMUNICATIONS CHANNELS
`14Q
`
`I
`
`FIG. 18
`
`0004
`
`

`

`U.S. Patent
`
`Apr. 11, 2006
`
`Sheet 3 of 11
`
`US 7,027,418 B2
`
`COMMUNICATIONS NETWORK 2.QQ
`
`MASTER210
`
`MEMORY
`2.12
`
`I TRANSCEIVER
`
`PROCESSOR
`ill
`216 I
`
`SLAVE220.
`
`SLAVE.23fl
`
`I MEMORY
`
`222
`
`1
`
`I MEMORY 232.1
`
`PROCESSOR
`m
`
`TRANSCEIVER
`.2.26
`
`PROCESSOR
`234.
`
`TRANSCEIVER
`236
`
`FIG. 2
`
`0005
`
`

`

`""""' 00 = N
`~
`-.....1
`"'--...1 = N
`
`rJl
`d
`
`....
`....
`0 .....
`
`.j;o.
`
`.....
`rFJ =(cid:173)
`
`('D
`('D
`
`0\
`0
`0
`N
`
`.... ~
`~ :-: ....
`
`~ = ~
`
`~
`~
`~
`•
`00
`
`e •
`
`.314
`
`PREAMBLE
`
`KNOWN
`COPY OF
`
`312.
`
`PREAMBLE
`
`KNOWN
`COPY OF
`
`.3ZQ
`
`PREAMBLE
`
`KNOWN
`COPY OF
`
`.36.6
`
`HEADER
`PAYLOAD
`
`.3.64.
`
`HEADER
`PACKET
`
`~
`
`PREAMBLE
`
`KNOWN
`
`FIG. 38
`
`330
`
`PAYLOAD
`
`MASTER TEST PACKET 360 ~
`
`FIG. 3A
`
`.320.
`
`~
`
`HEADER
`PACKET
`
`PREAMBLE
`
`KNOWN
`
`STANDARDPACKET300 ~
`
`0006
`
`

`

`""""' 00 = N
`"'--...1 = N
`
`~
`-.....1
`
`rJl
`d
`
`....
`....
`0 .....
`Ul
`.....
`rFJ =(cid:173)
`
`('D
`('D
`
`0\
`0
`0
`N
`
`.... ~
`'e :-: ....
`>
`
`~ = ~
`
`~
`~
`~
`•
`00
`
`e •
`
`I
`
`I
`
`I
`I
`I
`
`4fiQ
`
`CRC
`
`!5Q
`
`CODING SCHEME)
`
`(WITH 1/3 FEC OR OTHER
`GOOD CHANNEL DATA
`
`44Q
`
`(X TIME SLOTS)
`
`TIMEOUT
`
`A3Q
`HEADER
`PAYLOAD
`
`42!}
`
`HEADER
`PACKET
`
`41Q
`PREAMBLE
`
`KNOWN
`
`GOOD CHANNEL PACKET 400~
`
`FIG. 4
`
`I
`
`'
`
`I
`
`3M
`PREAMBLE
`
`KNOWN
`COPY OF
`
`~
`
`PREAMBLE
`
`KNOWN
`COPY OF
`
`.390
`PREAMBLE
`
`KNOWN
`COPY OF
`
`.3.88
`
`PACKET
`RECEIVED
`NEB OF LAST
`
`aaa
`HEADER
`PAYLOAD
`
`.3M
`
`HEADER
`PACKET
`
`.3.4Q
`
`PREAMBLE
`
`KNOWN
`
`SLAVE TEST PACKET 380 ~
`
`FIG. 3C
`
`0007
`
`

`

`""""' 00 = N
`"'--...1 = N
`
`~
`-.....1
`
`rJl
`d
`
`....
`....
`0 .....
`0\
`......
`rFJ =(cid:173)
`
`('D
`('D
`
`0\
`0
`0
`N
`
`.... ~
`'e :-: ....
`>
`
`~ = ~
`
`~
`~
`~
`•
`00
`
`e •
`
`CHANNELS5IQ ~ \LOADING572
`TABLE OF GOOD 1 ----------;z:--
`
`..a
`
`lr ADDRESS 554n
`
`lr ADDRESS 554n-1
`
`YYn
`
`YYn-1
`
`CHANNEL 552n
`GOOD
`CHANNEL 552n-1
`GOOD
`
`ADDRESS 524n
`
`XXn
`
`On
`
`FIG. SA
`
`f\._l
`
`I I XXn-1 tr-ADDRESS 524n-1
`
`ADDRESS 554c
`
`. .
`YY3
`
`I
`
`YY2
`
`I .t ADDRESS 554a
`
`YY1 VI
`
`~ I ~ ADDRESS554b
`
`.
`.
`. .
`c3
`C2
`
`I
`
`I
`
`CHANNEL 552c
`GOOD
`
`CHANNEL 552b
`GOOD
`
`CHANNEL 552a
`GOOD
`
`ADDRESS 524c
`
`ADDRESS524b
`
`ADDRESS 524a
`
`XX3
`
`XX2
`
`XX1
`
`CHANNEL 522c
`DEFAULT
`
`D2
`
`D1
`
`CHANNEL 522b
`DEFAULT
`
`CHANNEL 522a
`DEFAULT
`
`CHANNEL 522n
`DEFAULT
`CHANNEL 522n~l Dn-1
`DEFAULT
`.
`.
`.
`.
`D3
`
`.55{1
`
`GOOD CHANNELS
`REGISTER WITH
`
`ADDRESSING 514
`
`ADDRESSING 512
`
`REGISTER WITH
`
`DEFAULT CHANNELS
`
`.520
`
`.5.1Q
`
`SELECTION KERNEL
`
`0008
`
`

`

`""""' 00 = N
`~
`-.....1
`"'--...1 = N
`
`rJl
`d
`
`....
`....
`0 .....
`
`.j;o.
`
`.....
`rFJ =(cid:173)
`
`('D
`('D
`
`0\
`0
`0
`N
`
`.... ~
`~ :-: ....
`
`~ = ~
`
`~
`~
`~
`•
`00
`
`e •
`
`.314
`
`PREAMBLE
`
`KNOWN
`COPY OF
`
`312.
`
`PREAMBLE
`
`KNOWN
`COPY OF
`
`.3ZQ
`
`PREAMBLE
`
`KNOWN
`COPY OF
`
`.36.6
`
`HEADER
`PAYLOAD
`
`.3.64.
`
`HEADER
`PACKET
`
`~
`
`PREAMBLE
`
`KNOWN
`
`FIG. 38
`
`330
`
`PAYLOAD
`
`MASTER TEST PACKET 360 ~
`
`FIG. 3A
`
`.320.
`
`~
`
`HEADER
`PACKET
`
`PREAMBLE
`
`KNOWN
`
`STANDARDPACKET300 ~
`
`0009
`
`

`

`""""' 00 = N
`"'--...1 = N
`
`~
`-.....1
`
`rJl
`d
`
`....
`....
`0 .....
`Ul
`.....
`rFJ =(cid:173)
`
`('D
`('D
`
`0\
`0
`0
`N
`
`.... ~
`'e :-: ....
`>
`
`~ = ~
`
`~
`~
`~
`•
`00
`
`e •
`
`I
`
`I
`
`I
`I
`I
`
`4fiQ
`
`CRC
`
`!5Q
`
`CODING SCHEME)
`
`(WITH 1/3 FEC OR OTHER
`GOOD CHANNEL DATA
`
`44Q
`
`(X TIME SLOTS)
`
`TIMEOUT
`
`A3Q
`HEADER
`PAYLOAD
`
`42!}
`
`HEADER
`PACKET
`
`41Q
`PREAMBLE
`
`KNOWN
`
`GOOD CHANNEL PACKET 400~
`
`FIG. 4
`
`I
`
`'
`
`I
`
`3M
`PREAMBLE
`
`KNOWN
`COPY OF
`
`~
`
`PREAMBLE
`
`KNOWN
`COPY OF
`
`.390
`PREAMBLE
`
`KNOWN
`COPY OF
`
`.3.88
`
`PACKET
`RECEIVED
`NEB OF LAST
`
`aaa
`HEADER
`PAYLOAD
`
`.3M
`
`HEADER
`PACKET
`
`.3.4Q
`
`PREAMBLE
`
`KNOWN
`
`SLAVE TEST PACKET 380 ~
`
`FIG. 3C
`
`0010
`
`

`

`""""' 00 = N
`"'--...1 = N
`
`~
`-.....1
`
`rJl
`d
`
`....
`....
`0 .....
`0\
`......
`rFJ =(cid:173)
`
`('D
`('D
`
`0\
`0
`0
`N
`
`.... ~
`'e :-: ....
`>
`
`~ = ~
`
`~
`~
`~
`•
`00
`
`e •
`
`CHANNELS5IQ ~ \LOADING572
`TABLE OF GOOD 1 ----------;z:--
`
`..a
`
`lr ADDRESS 554n
`
`lr ADDRESS 554n-1
`
`YYn
`
`YYn-1
`
`CHANNEL 552n
`GOOD
`CHANNEL 552n-1
`GOOD
`
`ADDRESS 524n
`
`XXn
`
`On
`
`FIG. SA
`
`f\._l
`
`I I XXn-1 tr-ADDRESS 524n-1
`
`ADDRESS 554c
`
`. .
`YY3
`
`I
`
`YY2
`
`I .t ADDRESS 554a
`
`YY1 VI
`
`~ I ~ ADDRESS554b
`
`.
`.
`. .
`c3
`C2
`
`I
`
`I
`
`CHANNEL 552c
`GOOD
`
`CHANNEL 552b
`GOOD
`
`CHANNEL 552a
`GOOD
`
`ADDRESS 524c
`
`ADDRESS524b
`
`ADDRESS 524a
`
`XX3
`
`XX2
`
`XX1
`
`CHANNEL 522c
`DEFAULT
`
`D2
`
`D1
`
`CHANNEL 522b
`DEFAULT
`
`CHANNEL 522a
`DEFAULT
`
`CHANNEL 522n
`DEFAULT
`CHANNEL 522n~l Dn-1
`DEFAULT
`.
`.
`.
`.
`D3
`
`.55{1
`
`GOOD CHANNELS
`REGISTER WITH
`
`ADDRESSING 514
`
`ADDRESSING 512
`
`REGISTER WITH
`
`DEFAULT CHANNELS
`
`.520
`
`.5.1Q
`
`SELECTION KERNEL
`
`0011
`
`

`

`"""" 00 = N
`-....l = N
`
`~
`-....l
`
`rJl
`d
`
`....
`....
`0 .....
`-....l
`('D a
`rFJ =(cid:173)
`
`0\
`0
`0
`N
`
`.... ~
`'e :-: ....
`>
`
`~ = ~
`
`~
`~
`~
`•
`00
`
`e •
`
`........ CHANNEL.5I6n
`
`GOOD
`
`TABLE OF GOOD CHANNELS .5IQ
`········
`
`CHANNEL.5lfik
`
`GOOD
`~/
`/
`
`ADDRESSING
`~ ~ _ 522n-~S!AD _ j
`r DEFAULT CHANNEL I
`
`/ /
`
`/
`
`/
`
`/
`
`/
`
`532
`
`CHANNELfrlfia
`
`I ' GOOD
`
`I
`I
`
`~
`J
`r DEFAULT CHANNEL 1
`
`522b IS BAD
`
`---T -----
`
`ADDRESS 524c
`
`ADDRESS 524b
`
`ADDRESS 524a
`
`ADDRESSIN5--
`
`534
`
`530
`
`ADDRESSING
`
`~
`
`~-~ _ 522ai~GOOD _ J
`r DEFAULT CHANNEL I
`
`.hlQ
`
`SELECTION KERNEL
`
`FIG. 58
`
`ADDRESS 524n
`
`XXn -
`
`Dn
`
`-
`
`1'--
`
`CHANNEL 522n
`DEFAULT
`
`ADDRESS 524n-1
`
`I-
`
`XXn-1
`
`~ Dn-1
`
`...
`
`.
`.
`XX3 -
`XX2 -
`~~ D1 ~ XX1 -
`
`.
`.
`~~ D3
`
`~~ D2
`
`/
`
`/
`
`/---
`
`52Q
`
`DEFAULT CHANNELS
`
`REGISTER WITH
`
`CHANNEL 522n
`DEFAULT
`
`CHANNEL 522c
`DEFAULT
`CHANNEL 522b
`DEFAULT
`CHANNEL 522a
`DEFAULT
`
`0012
`
`

`

`U.S. Patent
`
`Apr. 11, 2006
`
`Sheet 8 of 11
`
`US 7,027,418 B2
`
`SLAVES 612
`MASTER 610
`........._
`r-
`........._
`r
`------~------
`------~------
`SEND MASTER TEST
`TEST NEB OF
`PACKETTOSLAVES ~
`RECEIVED MASTER
`TEST PACKET 624.
`62Q
`
`SEND SLAVE TEST
`TEST NEB OF
`RECEIVED SLAVE ~ PACKET TO MASTER
`TEST PACKET .632.
`.62.8
`
`DEFAULT
`CHANNELS
`614
`
`RECEIVE GOOD
`CHANNEL PACKET
`Q4A
`
`+
`
`SEND
`ACKNOWLEDGEMENT TO
`.64.8.
`MASTER
`
`+
`
`CLASSIFY CHANNELS
`AS 118AD 11 OR 11GOOD11
`632
`
`+
`
`SEND GOOD CHANNEL
`PACKET TO SLAVES
`WITH TIMEOUT £40
`
`.. ..
`
`RECEIVE
`ACKNOWLEDGMENTS
`FROM SLAVES .6.52
`
`....
`....
`
`GOTO
`BLOCK
`.654.
`
`)
`
`FIG. 6A
`
`0013
`
`

`

`U.S. Patent
`
`Apr. 11, 2006
`
`Sheet 9 of 11
`
`US 7,027,418 B2
`
`MASTER 610
`
`------~------
`
`r
`
`""
`
`SLAVES 612
`______ A _____ _
`""
`r
`
`AFTER EXPIRATION OF
`TIMEOUT, HOP OVER
`GOOD CHANNELS
`INSTEAD OF DEFAULT FH
`CHANNELS £sa
`
`MONITOR CHANNEL PERFORMANCE OF
`GOOD CHANNEL SET
`fi62.
`
`DEFAULT
`CHANNELS
`614
`
`GOOD
`CHANNELS
`616
`
`FIG. 68
`
`0014
`
`

`

`U.S. Patent
`
`Apr. 11, 2006
`
`Sheet 10 of 11
`
`US 7,027,418 B2
`
`MASTER 61 0
`-------~-------
`""'
`r
`
`SLAVES 612
`------~------
`'
`r
`
`SEND SLAVES A COMMAND TO
`"SWITCH BACK TO DEFAULT
`CHANNELS .. WITH TIMEOUT
`610
`
`RECEIVE 11SWITCH BACK''
`MESSAGE WITH TIMEOUT
`ill
`
`RECEIVE
`ACKNOWLEDGEMENTS
`FROM SLAVES
`£.82.
`
`SEND
`ACKNOWLEDGEMENT
`TO MASTER
`[l8_
`
`NO
`
`FIG. 6C
`
`AFTER EXPIRATION OF
`TIMEOUT, HOP OVER
`DEFAULT CHANNELS
`BOO
`
`REDETERMINE CHANNEL
`PERFORMANCE BY
`TESTING CHANNELS
`(E.G. RETURN TO STEP 620)
`~
`
`GOOD
`CHANNELS
`616
`
`DEFAULT
`CHANNELS
`614
`
`0015
`
`

`

`""""' 00 = N
`~
`-.....1
`"'--...1 = N
`
`rJl
`d
`
`....
`....
`0 .....
`....
`....
`.....
`rFJ =(cid:173)
`
`('D
`('D
`
`0\
`0
`0
`N
`
`.... ~
`~ :-: ....
`
`12.4
`
`HOST
`
`~ = ~
`
`~
`~
`~
`•
`00
`
`e •
`
`100
`
`118
`
`INTERFACE
`COMMUNICATION
`
`704
`PROCESSOR
`
`13.0.
`SERVER
`
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`-1
`
`1Q2
`
`BUS
`
`llil
`
`DEVICE
`STORAGE
`
`1.08
`
`ROM
`
`lUQ
`
`MEMORY
`
`MAIN
`
`-
`
`----
`
`-
`
`----
`
`-
`
`-
`
`-------
`
`-
`
`-
`
`-
`
`-
`
`-
`
`FIG. 7
`
`1.16
`
`CONTROL
`CURSOR
`
`714
`INPUT DEVICE
`
`I12
`
`DISPLAY
`
`0016
`
`

`

`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
`
`0017
`
`

`

`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
`commnnications channels is selected based on the perfor(cid:173)
`mance of the commnnications 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
`commnnications 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
`commnnicating with the participant according to a fre-
`quency hopping protocol. According to other aspects,
`another set of commnnications 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 commnnica(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 commnnications 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 commnnicatively 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 commnnications 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;
`
`0018
`
`

`

`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
`microwave 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 detectin