111111
`
`1111111111111111111111111111111111111111111111111111111111111
`US007 4 77 624 B2
`
`c12) United States Patent
`Gan et al.
`
`(10) Patent No.:
`(45) Date of Patent:
`
`US 7,477,624 B2
`*Jan. 13,2009
`
`(54) APPROACH FOR MANAGING THE USE OF
`COMMUNICATIONS CHANNELS BASED ON
`PERFORMANCE
`
`(75)
`
`Inventors: Hongbing Gan, Carlton North (AU);
`Bijan Treister, Kew (AU); Efstratios
`Skafidas, Coburg (AU)
`
`4,780,885 A
`5,317,568 A
`5,323,447 A
`5,394,433 A
`5,418,839 A
`5,541,954 A
`
`10/1988 Paul eta!.
`5/1994 Bixbyet a!.
`6/1994 Gillis et al.
`2/1995 Bantz eta!.
`5/1995 Knuth eta!.
`7/1996 Emi
`
`(Continued)
`
`(73) Assignee: Bandspeed, Inc., Austin, TX (US)
`
`FOREIGN PATENT DOCUMENTS
`
`( *) Notice:
`
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 189 days.
`
`GB
`
`2 401 512 A1
`
`1112004
`
`(Continued)
`
`OTHER PUBLICATIONS
`
`This patent is subject to a terminal dis(cid:173)
`claimer.
`
`Lawrey et a!., Adaptive Frequency Hopping for Multiuser OFDM,
`pp. 1-5, ICICS'99.*
`
`(21) Appl. No.: 11/397,443
`
`(22) Filed:
`
`Apr. 3, 2006
`
`(65)
`
`Prior Publication Data
`
`(Continued)
`
`Primary Examiner-Frank Duong
`(7 4) Attorney, Agent, or Firm-Hickman Palermo Truong &
`BeckerLLP
`
`US 2006/0176850 AI
`
`Aug. 10, 2006
`
`(57)
`
`ABSTRACT
`
`Related U.S. Application Data
`
`(63) Continuation of application No. 09/948,488, filed on
`Sep. 6, 2001, now Pat. No. 7,027,418.
`
`(60) Provisional application No. 60/264,594, filed on Jan.
`25,2001.
`
`(51)
`
`Int. Cl.
`(2006.01)
`H04Q 7100
`(52) U.S. Cl. ...................................................... 370/329
`(58) Field of Classification Search .......... 370/328-339
`See application file for complete search history.
`
`(56)
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`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 communications
`network. The participants communicate over the set of chan(cid:173)
`nels, such as by using a frequency hopping protocol. When a
`specified time expires or monitoring of the performance of the
`channel set identifies poor performance of the set of channels,
`the participant selects another set of channels for use in com(cid:173)
`munications based on additional performance testing. By
`selecting channels based on the initial performance testing
`and performance monitoring, the communications network
`adaptively avoids channels with poor performance.
`
`4,716,573 A
`
`12/1987 Bergstrom et al.
`
`29 Claims, 11 Drawing Sheets
`
`COMMUNICATIONS NETWORK2Ul!
`
`MASTER211l
`
`I MEMORY 2121
`I TRANSCEIVER
`I
`
`SLAVE22Q
`
`1
`
`222
`
`I MEMORY
`I PROCESSC~ I
`
`I TRANSCEIV:.I
`
`PROCESSO~ I
`
`211il
`I
`I MEMORY ml
`
`SLAVEZ3i
`
`PROCESSO~ I
`
`I
`
`I TRANSCEIVE~ I
`
`Marvell Semiconductor, Inc.
`MediaTek Inc.
`MediaTek USA, Inc.
`Exh. 1001
`IPR of U.S. Pat. No. 7,477,624
`
`0001
`
`

`

`US 7,477,624 B2
`Page 2
`
`U.S. PATENT DOCUMENTS
`
`1111996 West
`5,574,979 A
`7/1997 Tayloe
`5,649,291 A
`5,726,978 A * 3/1998 F rodigh et a!. .............. 370/252
`5,774,808 A
`6/1998 Sarkioja et al.
`7/1998 Kang eta!.
`5,781,861 A
`5,844,522 A
`12/1998 Sheffer et a!.
`5,873,036 A
`2/1999 Vucetic
`4/1999 Karlsson et a!.
`5,898,928 A
`5,956,642 A
`9/1999 Larsson et a!.
`6,009,332 A
`12/1999 Haartsen
`6,169,761 B1
`112001 Marcoccia et a!.
`6,240,126 B1
`5/2001 Ohashi eta!.
`6,549,784 B1
`4/2003 Kostic eta!.
`6,601,101 B1
`7/2003 Lee et al.
`6,633,761 B1
`10/2003 Singhal et a!.
`6,650,872 B1
`1112003 Karlsson
`6,687,239 B1
`2/2004 Koprivica
`6,694,147 B1
`2/2004 Viswanath et al.
`6,700,875 B1
`3/2004 Schroeder et al.
`6,704,346 B1
`3/2004 Mansfield
`6/2004 Wang et al.
`6,745,034 B2
`6,751,249 B1
`6/2004 Cannon eta!.
`6,760,317 B1
`7/2004 Honkanen et a!.
`7,027,418 B2 * 4/2006 Gan eta!. ................... 370/329
`2002/0122462 A1
`9/2002 Batra eta!.
`2005/0020271 A1
`112005 Fukuda et al.
`2005/0223115 A1
`10/2005 Hanson eta!.
`
`FOREIGN PATENT DOCUMENTS
`
`wo
`wo
`
`WO 96/34468 A1
`wo 00/60896
`
`10/1996
`10/2000
`
`WO
`
`1/2001
`WO 01103379 A1
`OTHER PUBLICATIONS
`Zander, J. PHd and G. Malmgren MSc, IEEE Proc.-Commun., vol.
`142, No.2, Apr. 1995, entitled "Adaptive frequency hopping in HF
`communications", (pp. 99-105).
`Fifth International Symposium on Signal Processing and its Appli(cid:173)
`cations, ISSPA '99 Brisbane, Australia, Aug. 22-25, 1999, entitled
`"Multiuser OFDM", by E. Lawrey, (pp. 761-764).
`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 (WPANs), Sep. 2000, XP 00220853, 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 (WPAN s ), Oct. 20, 2000
`XP002220854, pp. 1-39.
`Johnsson, HiperLAN/2-The Broadband Radio Transmission Tech(cid:173)
`nology Operating in the 5 GHz Frequency Band, pp. 1-22 1999.
`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, 2004.
`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 V2 WPAN, pp. 1-28, Nov. 2000, downloaded at
`http:/ I grouper.ieee.org/ groups/802/ 15/pub/2000/N ovOO/
`00367rOP802-15_ TG2-Adaptive-Frequency -Hopping.ppt.
`The International Bureau ofWIPO, "Notification Concerning Trans(cid:173)
`mittal of Copy of Internaitonal Preliminary Report on Patentability
`(Chapter 1 of the Patent Cooperation Treaty" International applica(cid:173)
`tion No. PCT/US2006/027206, received Jan. 31, 2008, 7 pages.
`Claims, International application No. PCT/US2006/027206, 6 pages.
`* cited by examiner
`
`0002
`
`

`

`U.S. Patent
`
`Jan. 13, 2009
`
`Sheet 1 of 11
`
`US 7,477,624 B2
`
`100 I
`
`DETERMINE PERFORMANCE OF
`COMMUNICATIONS CHANNELS
`11Q
`
`SELECT A SET OF COMMUNICATIONS
`CHANNELS
`ill
`
`REDETERMINE PERFORMANCE OF
`COMMUNICATIONS CHANNELS
`1.18
`
`SELECT A NEW SET OF
`COMMUNICATIONS CHANNELS
`122
`
`FIG. 1A
`
`0003
`
`

`

`U.S. Patent
`
`Jan.l3,2009
`
`Sheet 2 of 11
`
`US 7,4 77,624 B2
`
`SELECT A NEW SET OF
`COMMUNICATIONS CHANNELS
`142
`
`GENERATE NEW DATA THAT
`IDENTIFIES THE NEW SET OF
`COMMUNICATIONS CHANNELS
`.144
`
`PROVIDE THE NEW
`IDENTIFICATION DATA TO THE
`14£.
`PARTICIPANT
`
`COMMUNICATE WITH THE
`PARTICIPANT OVER THE NEW SET
`OF COMMUNICATIONS CHANNELS
`.1!6
`
`DETERMINE PERFORMANCE
`DATA OF COMMUNICATIONS
`CHANNELS
`I
`SELECT A SET OF
`COMMUNICATIONS CHANNELS
`132
`
`I
`GENERATE CHANNEL
`IDENTIFICATION DATA THAT
`IDENTIFIES THE SET OF
`COMMUNICATIONS CHANNELS
`1M
`
`I
`PROVIDE THE CHANNEL
`IDENTIFICATION DATA TO THE
`13fi
`PARTICIPANT
`I
`COMMUNICATE WITH THE
`PARTICIPANT OVER THE SET OF
`COMMUNICATIONS CHANNELS
`.138
`
`I
`
`REDETERMINE THE
`PERFORMANCE OF THE
`COMMUNICATIONS CHANNELS
`14.0.
`
`I
`
`FIG. 1 B
`
`0004
`
`

`

`U.S. Patent
`
`Jan. 13,2009
`
`Sheet 3 of 11
`
`US 7,477,624 B2
`
`COMMUNICATIONS NETWORK 200
`
`MASTER 2.1..0.
`
`I MEMORY 21.21
`I TRANSCEIVER
`
`PROCESSOR
`ill
`
`216. I
`
`SLAVE22Jl
`
`SLAVE ill
`
`I MEMORY 222.1
`
`I MEMORY .2321
`
`PROCESSOR
`2.24
`
`TRANSCEIVER
`.22fi
`
`PROCESSOR
`.2.34
`
`TRANSCEIVER
`23fi
`
`FIG. 2
`
`0005
`
`

`

`~ = N
`
`N
`0'1
`"'-....l
`-....l
`~
`-....l
`rJl
`d
`
`I
`I
`
`....
`....
`0 .....
`
`ill
`
`312
`
`3IQ
`
`PREAMBLE
`
`KNOWN
`COPY OF
`
`PREAMBLE
`
`KNOWN
`COPY OF
`
`PREAMBLE
`
`KNOWN
`COPY OF
`
`3fifi
`
`HEADER
`PAYLOAD
`
`.36A
`
`HEADER
`PACKET
`
`.340_
`
`PREAMBLE
`
`KNOWN
`
`FIG. 38
`
`.....
`rFJ =(cid:173)
`
`('D
`('D
`
`.j;o.
`
`\0
`0
`0
`N
`~(H
`
`:= ....
`
`;(cid:173)
`
`~ = ~
`
`~
`~
`~
`•
`00
`~
`
`no
`
`PAYLOAD
`
`MASTER TEST PACKET 360 ~
`
`FIG. 3A
`
`32Q
`
`HEADER
`PACKET
`
`.31Q
`
`PREAMBLE
`
`KNOWN
`
`STANDARD PACKET 300 ~
`
`0006
`
`

`

`~ = N
`
`N
`0..,
`-....l
`-....l
`~
`-....l
`rJl
`d
`
`....
`....
`0 .....
`Ul
`.....
`rFJ =(cid:173)
`
`('D
`('D
`
`~
`
`~ := ....
`
`\0
`0
`0
`N
`~(H
`
`~ = ~
`
`~
`~
`~
`•
`00
`~
`
`4.60.
`
`CRC
`
`.450.
`
`CODING SCHEME)
`
`(WITH 1/3 FEC OR OTHER
`GOOD CHANNEL DATA
`
`MO.
`
`(X TIME SLOTS)
`
`TIMEOUT
`
`43.0.
`HEADER
`PAYLOAD
`
`42Q
`
`HEADER
`PACKET
`
`41Q
`PREAMBLE
`
`KNOWN
`
`GOOD CHANNEL PACKET 400~
`
`FIG. 4
`
`.3M
`PREAMBLE
`
`KNOWN
`COPY OF
`
`.392
`PREAMBLE
`
`KNOWN
`COPY OF
`
`.300
`PREAMBLE
`
`KNOWN
`COPY OF
`
`.388
`
`PACKET
`RECEIVED
`
`NEB OF LAST
`
`.38..6.
`
`HEADER
`PAYLOAD
`
`384
`
`HEADER
`PACKET
`
`.3.4.0.
`
`PREAMBLE
`
`KNOWN
`
`SLAVE TEST PACKET 380 ~
`
`FIG. 3C
`
`0007
`
`

`

`~ = N
`
`N
`0..,
`-....l
`-....l
`~
`-....l
`rJl
`d
`
`....
`....
`0 .....
`0\
`.....
`rFJ =(cid:173)
`
`('D
`('D
`
`~
`
`~ := ....
`
`\0
`0
`0
`N
`~(H
`
`~
`~
`~
`•
`00
`~
`
`~ = ~
`
`~LOADING572
`
`CHANNELS 5lQ
`TABLE OF GOOD
`
`I
`
`FIG. SA
`
`CHANNEL 552n
`1 YYn LV ADDRESS 554n
`GOOD
`CHANNEL 552n~ Cn-1 I YYn-1 I lr ADDRESS 554n-1
`GOOD
`
`-ll
`
`Cn
`
`I YY3
`
`CHANNEL 552c -h. I C3
`I V"ADDRESS 554c
`GOOD
`CHANNEL 552b -h I c2 I YY2 1 rADDREss ss4b
`I lr"ADDRESS 554a
`
`I YY1
`
`GOOD
`CHANNEL552a--h1 C1
`GOOD
`
`ADDRESS 524n
`
`XXn
`
`Dn
`
`ADDRESS 524n-1
`
`XXn-1
`
`Dn-1
`
`CHANNEL 522n
`DEFAULT
`CHANNEL 522n-1
`DEFAULT
`
`ADDRESS 524c
`
`ADDRESS 524b
`
`XX3
`
`XX2
`
`D3
`
`D2
`
`D1
`
`CHANNEL 522c
`DEFAULT
`CHANNEL 522b
`DEFAULT
`CHANNEL 522a
`DEFAULT
`
`.5.5Q
`
`GOOD CHANNELS
`REGISTER WITH
`
`ADDRESSING 514
`
`ADDRESSING 512
`
`.51Q
`
`SELECTION KERNEL
`
`52Q
`
`DEFAULT CHANNELS
`
`REGISTER WITH
`
`0008
`
`

`

`~ = N
`
`N
`0..,
`---1
`---1
`~
`---1
`rJl
`d
`
`....
`....
`0 .....
`......:J
`.....
`rFJ =(cid:173)
`
`('D
`('D
`
`~
`
`~ := ....
`
`\0
`0
`0
`N
`~(H
`
`CHANNEL.5lfin
`
`GOOD
`
`. .......
`
`CHANNEL ilik
`
`GOOD
`
`/
`
`,
`
`ADDRESSING
`
`532
`
`/
`
`./
`
`./
`
`/
`
`/
`
`/
`
`J
`1
`
`'----~--
`522n-1 IS BAD
`
`I DEFAULT CHANNEL 1
`,.------·--
`
`--
`ADDRESSING
`
`534
`
`TABLE OF GOOD CHANNELS.5IQ
`
`I DEFAULT CHANNEL ~ • ~
`
`-~ I ./ \
`
`-
`
`-
`
`-
`
`-
`
`r--
`
`........
`
`CHANNEL5Na
`
`GOOD
`t
`
`I
`I
`
`I
`
`/
`
`-
`
`-
`
`-
`
`-T
`
`-
`
`\. -
`
`522b IS BAD
`
`FIG. 58
`
`'ADDRESS 524n
`
`ADDRESS 524n-1
`
`XXn -
`
`I-
`
`XXn-1
`
`"\. Dn
`
`\ Dn-1
`
`CHANNEL 522n
`DEFAULT
`
`CHANNEL 522n
`DEFAULT
`
`'ADDRESS 524c
`
`'ADDRESS 524b
`
`'ADDRESS 524a
`
`XX3 -
`XX2 -
`
`.
`
`\. 03
`
`02
`
`\
`
`I-
`
`~ 01 ~ XX1
`
`/
`
`CHANNEL 522c
`DEFAULT
`CHANNEL 522b
`DEFAULT
`CHANNEL 522a
`DEFAULT
`
`~ = ~
`
`~
`~
`~
`•
`00
`~
`
`li1Q
`
`SELECTION KERNEL
`
`530
`
`ADDRESSING
`
`\,.._,
`
`\. _______ /
`I DEFAULT CHANNEL 1
`
`522a IS GOOD
`
`1
`
`~-------
`
`-
`
`-
`
`- /
`DEFAULT CHANNELS
`
`520
`
`/
`
`REGISTER WITH
`
`0009
`
`

`

`U.S. Patent
`
`Jan.l3,2009
`
`Sheet 8 of 11
`
`US 7,4 77,624 B2
`
`SLAVES 612
`MASTER 610
`~------~------~ ~------~------~
`SEND MASTER TEST
`TEST NEB OF
`PACKET TO SLAVES
`RECEIVED MASTER
`TEST PACKET .624.
`.620.
`
`----.
`
`TEST NEB OF
`RECEIVED SLAVE +
`TEST PACKET .6.32
`
`SEND SLAVE TEST
`PACKET TO MASTER
`.62.8.
`
`•
`
`CLASSIFY CHANNELS
`AS "BAD" OR "GOOD"
`£3fi
`
`DEFAULT
`CHANNELS
`614
`
`RECEIVE GOOD
`CHANNEL PACKET
`Q44
`
`+
`
`SEND
`~ ACKNOWLEDGEMENTTO
`....
`64.a
`MASTER
`
`SEND GOOD CHANNEL
`PACKET TO SLAVES
`WITH TIMEOUT .64Q
`
`.. ..
`
`+
`
`RECEIVE
`ACKNOWLEDGMENTS
`FROM SLAVES fi52
`
`GOTO
`I BLOCK
`.6M
`
`)
`
`FIG. 6A
`
`0010
`
`

`

`U.S. Patent
`
`Jan.l3,2009
`
`Sheet 9 of 11
`
`US 7,4 77,624 B2
`
`SLAVES 612
`MASTER 610
`------~------
`------~------
`'\ r
`"
`r
`
`YES
`
`AFTER EXPIRATION OF
`TIMEOUT, HOP OVER
`GOOD CHANNELS
`INSTEAD OF DEFAULT FH
`CHANNELS .6.58_
`
`MONITOR CHANNEL PERFORMANCE OF
`GOOD CHANNEL SET
`.662
`
`DEFAULT
`CHANNELS
`614
`
`GOOD
`CHANNELS
`616
`
`FIG. 68
`
`0011
`
`

`

`U.S. Patent
`
`Jan. 13,2009
`
`Sheet 10 of 11
`
`US 7,477,624 B2
`
`MASTER 610
`-------~-------
`r
`"'
`
`SLAVES 612
`------~------
`r
`~
`
`SEND SLAVES A COMMAND TO
`"SWITCH BACK TO DEFAULT
`CHANNELS" WITH TIMEOUT
`filQ
`
`RECEIVE "SWITCH BACK"
`MESSAGE WITH TIMEOUT
`ill
`
`RECEIVE
`ACKNOWLEDGEMENTS
`FROM SLAVES
`.682
`
`SEND
`ACKNOWLEDGEMENT
`TO MASTER
`.6I8.
`
`NO
`
`FIG. 6C
`
`AFTER EXPIRATION OF
`TIMEOUT, HOP OVER
`DEFAULT CHANNELS
`.600
`
`REDETERMINE CHANNEL
`PERFORMANCE BY
`TESTING CHANNELS
`(E.G. RETURN TO STEP 620)
`.6.9.4
`
`GOOD
`CHANNELS
`616
`
`DEFAULT
`CHANNELS
`614
`
`0012
`
`

`

`~ = N
`
`N
`0..,
`-....l
`-....l
`~
`-....l
`rJl
`d
`
`....
`....
`0 .....
`....
`....
`.....
`rFJ =(cid:173)
`
`('D
`('D
`
`ill
`
`HOST
`
`~
`
`~ := ....
`
`\0
`0
`0
`N
`~(H
`
`ill. ~J
`
`I COMMUNICATION
`
`INTERFACE
`
`PROCESSOR I
`
`IQ4
`
`1Q2
`
`BUS
`
`~ = ~
`
`~
`~
`~
`•
`00
`~
`
`13Q
`SERVER
`
`l1Q
`
`DEVICE
`STORAGE
`
`N8
`
`ROM
`
`lQfi
`
`MEMORY
`
`MAIN
`
`-----------------------l
`
`FIG. 7
`
`1.1£
`
`CONTROL
`CURSOR
`
`ill
`INPUT DEVICE
`
`I12
`
`DISPLAY
`
`0013
`
`

`

`US 7,477,624 B2
`
`1
`APPROACH FOR MANAGING THE USE OF
`COMMUNICATIONS CHANNELS BASED ON
`PERFORMANCE
`
`PRIORITY CLAIMS AND RELATED
`APPLICATIONS
`
`2
`other functions to perform. Although a master participant
`typically performs additional functions than the other partici(cid:173)
`pants, any participant is capable of performing these func(cid:173)
`tions if elected as the master participant.
`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 offrequen(cid:173)
`cies in a communications frequency band. A frequency hop-
`10 ping 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 offrequencies. A typical NFH system
`may occupy a portion of the communications frequency 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 cham1els in the
`hopping sequence. The switching of frequencies may occur
`25 many times each second. The use of an FH protocol helps to
`reduce problems with interference from other communica(cid:173)
`tions systems and other interference sources. Frequency hop(cid:173)
`ping also helps with fading of transmissions and power con(cid:173)
`sumption and also provides security for the transmission so
`30 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
`35 the Bluetooth™ wireless personal area network (WPAN)
`technology from the Bluetooth Special Interest Group. The
`BLUE TOOTH trademarks are owned by Bluetooth SIG, Inc.,
`U.S.A. The Bluetooth protocol uses 79 individual randomly
`chosen frequency channels numbered from 0 to 78 and
`40 changes the frequencies 1600 times per second. Examples of
`NFH 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 the 2.4 GHz Industrial,
`Scientific, Medical (ISM) band, which is an unlicensed por-
`45 tion of the radio spectrum 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 from
`one participant to another participant, or point-to-multipoint,
`50 meaning that communications paths are provided 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
`participants of the network. The other participants of the
`55 network, such as slaves, are time synchronized with the mas(cid:173)
`terto maintain communications with the master. For example,
`the Bluetooth and IEEE 802.15.1 frequency hopping proto(cid:173)
`cols are point-to-multipoint systems in which the frequency
`hopping sequence is determined by the physical address of
`60 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 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
`
`This application claims domestic priority under 35 U.S.C.
`§120 as a continuation of U.S. non-provisional application
`Ser. No. 09/948,488, filed Sep. 6, 2001, now U.S. Pat. No.
`7,027,418, entitled "APPROACH FOR SELECTING COM(cid:173)
`MUNICATIONS CHANNELS BASED ON PERFOR(cid:173)
`MANCE," naming Hongbing Gan, Bijan Treister, and Efstra(cid:173)
`tios Skafidas as inventors, which in tum claims domestic
`priority from prior U.S. Provisional Patent Application Ser. 15
`No. 60/264,594, filed on Jan. 25, 2001, titled "ADAPTIVE
`FREQUENCY HOPPING-A COEXISTENCE MECHA(cid:173)
`NISM FOR A FREQUENCY HOPPING COMMUNICA(cid:173)
`TIONSYSTEMTOCOEXISTWITHNON-FREQUENCY(cid:173)
`HOPPING COMMUNICATION SYSTEMS SHARING 20
`THE SAME FREQUENCY BAND," naming as inventors
`Hongbing Gan, Bijan Treister, and Efstratios Skafidas, the
`entire disclosures ofboth of which is hereby incorporated by
`reference for all purposes as if fully set forth herein.
`This application is related to: (1) co-pending non-provi(cid:173)
`sional application Ser. No. 10/052,019, filed Jan. 16, 2002,
`entitled "APPROACH FOR MANAGING COMMUNICA(cid:173)
`TIONS CHANNELS BASED ON PERFORMANCE AND
`TRANSFERRING FUNCTIONS BETWEEN PARTICI(cid:173)
`PANTS IN A COMMUNICATIONS ARRANGEMENT,"
`naming Bijan Treister, Hongbing Gan, and Efstratios Skafi(cid:173)
`das as inventors, (2) co-pending non-provisional application
`Ser. No. 09/948,499,
`filed Sep. 6, 2001, entitled
`"APPROACH FOR MANAGING COMMUNICATIONS
`CHANNELS BASED ON PERFORMANCE," naming Bijan
`Treister, Hong bing Gan, and Efstratios Skafidas as inventors,
`and (3) co-pending non-provisional application Ser. No.
`09/939,105, filedAug. 24,2001, entitled "APPROACH FOR
`TRANSFERRING FUNCTIONS BETWEEN PARTICI(cid:173)
`PANTS IN A COMMUNICATIONS ARRANGEMENT,"
`naming Bijan Treister, Hongbing Gan, and Efstratios Skafi(cid:173)
`das as inventors.
`
`FIELD OF THE INVENTION
`
`The present invention generally relates to communications
`systems, and more particularly to managing the use of com(cid:173)
`munications cham1els based on channel performance.
`
`BACKGROUND
`
`The approaches described in this section are approaches
`that could be pursued, but not necessarily approaches that
`have been previously conceived or pursued. Therefore, unless
`otherwise indicated, the approaches described in this section
`are not prior art to the claims in this application and are not
`admitted to be prior art by inclusion in this section.
`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 arrange(cid:173)
`ments, one of the participants is designated as a master par(cid:173)
`ticipant, or simply as the "master." The master generally
`initiates and controls communications with the other partici- 65
`pants, which are conventionally referred to as slave partici(cid:173)
`pants, or simply as "slaves." Masters may also be assigned
`
`0014
`
`

`

`US 7,477,624 B2
`
`3
`timeslots. As another example, in a Bluetooth FH communi(cid:173)
`cations 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, inB!uetoothand
`IEEE 802.15.1, the known preamble is called the "channel 10
`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 com- 15
`munications 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 com(cid:173)
`munications system, there may be interference between the 20
`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 neverthe(cid:173)
`less remains interference on those channels that coincide with
`the NFH communications systems. An example of the inter- 25
`ference situation is the coexistence problem between the fre(cid:173)
`quency hopping IEEE 802.15.1 WPAN and the non-fre(cid:173)
`quency hopping IEEE 802.11 b Wireless Local Area Network
`(WLAN) because both share the 2.4 GHz ISM band.
`Further, because of the dynamic nature of interference due 30
`to the use of devices at different times and locations, eventu(cid:173)
`ally all FH channels will experience some degree of interfer(cid:173)
`ence at some time. Interference may change depending on
`when the communications systems use the band and the rela(cid:173)
`tive locations of the participants of each system to partici- 35
`pants of another system. Because the participants may be
`mobile, interference may vary depending on the movements
`of the participants of one system relative to the locations of
`participants of other systems. In addition, interference may
`arise from other sources, such as some consumer appliances 40
`like microwave ovens, resulting in a degradation of perfor(cid:173)
`mance of the FH communications 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 performance 45
`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 trans(cid:173)
`mitting 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 interference 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 jump(cid:173)
`ing to another randomly selected channel. However, this skip(cid:173)
`ping approach does not necessarily avoid other bad channels
`because the next channel used may also have an interference
`problem. Also, known "bad" and "good" channels 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 man(cid:173)
`aging interference in communications system, such as the
`
`4
`coexistence problem between frequency hopping communi(cid:173)
`cations systems and non-frequency hopping communications
`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 communica(cid:173)
`tions channels based on channel performance. According to
`one aspect of the invention, a method selects communications
`channels for a communications system. A set of communica-
`tions channels is selected based on the performance of the
`communications channels and channel selection criteria.
`Then another set of communications channels is selected
`based on a later performance of the communications 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 com(cid:173)
`munications channels is selected based on the performance of
`the communications channels and a performance criterion.
`Identification data that identifies the set of communications
`channels is generated and provided to the participant. The set
`of communications channels is used for communicating with
`the participant according to a frequency hopping protocol.
`According to other aspects, another set of communications
`channels is selected in a similar manner when a specified
`criterion is satisfied, including but not limited to, after expi(cid:173)
`ration 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-
`tions device is used in a network that communicates via a
`frequency hopping protocol. The communications device
`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 gener(cid:173)
`ating a measurement of channel performance based on receiv(cid:173)
`ing a packet from another device and transmitting another
`packet to the other device that contains data indicating the
`measurement of channel performance.
`According to another aspect, another communications
`device is used in a network that communicates via a frequency
`hopping protocol. The communications device includes a
`50 memory for storing sequences of instructions and a processor
`communicatively coupled to the memory. When the proces(cid:173)
`sor executes the instructions, the instructions cause the pro(cid:173)
`cessor to determine the performance of communications
`channels and then select a set of channels based on the per-
`55 formance and a performance criterion. The processor gener(cid:173)
`ates and stores in the memory data that identifies 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
`60 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 communi(cid:173)
`cations channel selector apparatus is provided. The apparatus
`is configured to determine channel performance at one time
`65 and select based on that performance a set of channels based
`on channel selection criteria. The apparatus is configured to
`then determine the channel performance at a later time and
`
`0015
`
`

`

`US 7,477,624 B2
`
`5
`select another set of channels based on that latter 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
`
`6
`E. Cyclic Rednndancy Check (CRC)
`F. Packet Loss Ratio (PLR)
`G. Forward Error Correction (FEC)
`H. Other Channel Performance Testing Considerations
`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
`
`The present invention is depicted by way of example, and
`not by way oflimitation, in the figures of the accompanying 10
`drawings and in which like reference numerals refer to 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; 15
`FIG. lB is a flow diagram that depicts an approach for
`commnnicating with a participant using a set of good chan(cid:173)
`nels, selected according to an embodiment of the invention;
`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;
`FIG. 3B is a block diagram that depicts a master test packet
`that is sent by a master to slaves to test channel performance, 25
`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 perfor(cid:173)
`mance 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 embodi- 35
`ment of the invention;
`FIG. SB is a block diagram that depicts the replacement of
`bad channels with good channels in a default set of 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 fre(cid:173)
`quency hopping, according to an embodiment of the inven(cid:173)
`tion; and
`FIG. 7 is a block diagram that depicts a computer system
`upon which embodiments of the invention may be imple(cid:173)
`mented.
`
`DETAILED DESCRIPTION
`
`An approach for selecting sets of communications chan(cid:173)
`nels based on channel performance is described. In the fol(cid:173)
`lowing description, for the purposes of explanation, numer(cid:173)
`ous specific details are set forth in order to provide a thorough
`understanding of the present invention. It will be apparent, 55
`however, that the present invention may be practiced without
`these specific details. In other instances, well-known struc(cid:173)
`tures 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 60
`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)
`
`A novel approach for managing network communications
`generally involves selecting sets of communications channels
`based on channel performance. An initial set of channels is
`20 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 interfer(cid:173)
`ence.
`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.
`In block 110, the performance of a set of available commu(cid:173)
`nications channels is determined. For example, for a commu(cid:173)
`nications system that uses 100 channels, some or all of the
`30 100 channels may be tested to determine channel perfor(cid:173)
`mance. Other systems using the same frequency band may
`interfere with several of the 1 00 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 commnnications system
`may experience interference on channels 3 through 5 from
`one communications system and on channels 50 through 54
`from another commnnications system. The channel testing
`40 may ind