`US007280580Bl
`
`c12) United States Patent
`Haartsen
`
`(10) Patent No.:
`(45) Date of Patent:
`
`US 7,280,580 Bl
`Oct. 9, 2007
`
`(54) HOP SEQUENCE ADAPTATION IN A
`FREQUENCY-HOPPING COMMUNICATIONS
`SYSTEM
`
`(75)
`
`Inventor: Jacobus C. Haartsen, Hardenberg (NL)
`
`(73) Assignee: Telefonaktlebolaget LM Ericsson
`(publ.), Stockholm (SE)
`
`( *) Notice:
`
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by O days.
`
`(21) Appl. No.: 09/418,562
`
`(22) Filed:
`
`Oct. 15, 1999
`
`(51)
`
`Int. Cl.
`H04B 1100
`(2006.01)
`(52) U.S. Cl. ....................................... 375/138; 375/132
`(58) Field of Classification Search ................ 375/200,
`375/202, 130-153, 267; 455/450, 464; 370/338,
`370/333, 330
`See application file for complete search history.
`
`(56)
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`4,023,103 A
`4,476,566 A *
`4,606,040 A
`4,716,573 A *
`4,780,885 A *
`5,307,348 A
`5,323,447 A *
`5,408,496 A
`5,515,369 A
`5,619,493 A
`5,737,358 A
`5,809,059 A
`
`5/1977 Malm
`10/1984 Dent .......................... 375/132
`8/1986 David et al.
`12/1987 Bergstrom et al. .......... 375/132
`10/1988 Paul et al.
`.................. 375/267
`4/ 1994 Buchholz et al.
`6/1994 Gillis et al. ................. 455/464
`4/1995 Ritz et al.
`5/1996 Flammer, III et al.
`4/1997 Ritz et al.
`4/1998 Ritz et al.
`9/ 1998 Souissi et al.
`
`5,832,026 A
`5,848,095 A
`5,870,391 A
`5,898,733 A
`6,480,721 Bl *
`FOREIGN PATENT DOCUMENTS
`
`11/1998 Li
`12/1998 Deutsch
`2/1999 Nago
`4/ 1999 Satyanarayana
`11/2002 Sydon et al.
`............... 455/464
`
`EP
`WO
`WO
`
`0182762 Al
`WO99/09671
`WO99/19993
`
`5/1986
`2/1999
`4/1999
`
`* cited by examiner
`
`Primary Examiner----Curtis Odom
`(74) Attorney, Agent, or Firm-Potomac Patent Group
`PLLC
`
`(57)
`
`ABSTRACT
`
`A hop channel is selected for use in a channel hopping
`communication system that includes a sequence of hop
`channels, wherein the sequence comprises a set of forbidden
`hop channels and a remaining set of allowable hop channels.
`Selection involves selecting a hop channel from the
`sequence as a function of a present phase. If the selected hop
`channel is an allowable hop channel, then the selected hop
`channel is used for communication during the present phase.
`If the selected hop channel is a forbidden hop channel, then
`a time-varying parameter is used to select a substitute hop
`channel from the set of allowable hop channels. The sub(cid:173)
`stitute hop channel is then used for communication during
`the present phase. The time-varying parameter may, for
`example, be a clock value. With this strategy, the resultant
`hopping sequence is identical to the original hopping
`sequence whenever the original sequence calls for an allow(cid:173)
`able hop channel. In all other cases, a substitute hop channel
`is dynamically selected from the set of allowable hop
`channels.
`
`42 Claims, 15 Drawing Sheets
`
`DETERMINE PRESET HOP
`CHANNEL AS FUNCTION OF PHASE
`
`901
`
`YES
`
`903
`
`INDEX=MOD(CLOCK,N2)+BASE VALUE
`
`PRESENT HOP CHANNEL=TABLE(INDEX)
`
`USE PRESENT HOP CHANNEL
`
`905
`
`907
`
`909
`
`Page 1 of 29
`
`
`
`U.S. Patent
`U.S. Patent
`
`Oct. 9, 2007
`Oct. 9, 2007
`
`Sheet 1 0f 15
`Sheet 1 of 15
`
`US 7,280,580 Bl
`US 7,280,580 B1
`
`
`
`24802K?!Freq(MHz)
`
`-~
`
`~
`t'C
`E - - - -....... ~
`
`ooéy‘WJ-iilm—flLj—I—LLF--‘-MH
`
`I
`I
`I
`I
`I
`
`~-----i
`E--------1
`
`FIGUREI
`
`Page 2 of 29
`
`Page 2 of 29
`
`
`
`U.S. Patent
`U.S. Patent
`
`Oct. 9, 2007
`Oct. 9, 2007
`
`Sheet 2 of 15
`Sheet 2 of 15
`
`US 7,280,580 Bl
`US 7,280,580 B1
`
`0
`~ - -..... ey
`N
`
`I
`I
`I
`I
`I
`
`~
`Cd
`'-'
`~
`'
`\_b
`.......... w_
`
`3%0E
`
`I
`I
`I
`I
`I
`
`ByM.(Eu
`
`
`
`~
`.,.0
`'-'
`~
`'
`\.6
`\l
`
`8%£3.j«N23:09E£3“.83as.“
`«N13:gm5?.
`a:SE3a8%8355°
`
`!
`@
`
`N
`
`~ N
`
`C"l
`
`~
`N
`
`8%a:3x8%SE3&6
`
`V'I
`
`I
`~
`ij
`
`N
`
`C"l
`
`~
`~
`
`<i)
`':t-
`""i,
`
`..
`• ..
`
`ij
`
`~ -C)
`
`~
`C"g
`
`...
`...
`
`Page 3 of 29
`
`Page 3 of 29
`
`
`
`U.S. Patent
`U.S. Patent
`
`Oct. 9, 2007
`9m
`
`Sheet 3 of 15
`M3m
`
`US 7,280,580 Bl
`1B0
`7.,
`
`~---.. ~
`
`0
`
`m0%cam,«NEEFEE3%.2348%.kc}.«sag8E238%SN5%
`
`43.....A;
`
`I
`I
`I
`I
`I
`
`r"..._
`
`~
`('{') .
`'.§
`....__
`\..L
`
`-.\,,
`
`~ " ~ ~
`" ,J
`~
`')
`~ N
`i
`ij
`N
`
`~
`.. ~
`...
`'
`
`0
`~---►~
`
`fl.6masmEu
`
`m«N12»DEE$523¢v§w838:3%3a8:8xEmu
`
`I
`I
`I
`I
`I ~
`-0
`~
`IY)
`
`'-U
`......._
`~ \.l
`
`~
`"(
`
`~
`~ N
`~ N
`!
`ij
`
`N
`
`~ -~
`
`' ~
`'
`'
`
`Page 4 of 29
`
`Page 4 of 29
`
`
`
`r
`
`103
`I
`
`qo l I SequenceX
`phase -+I address selector h I 124051
`1 2455 1
`1 2478 1
`·~
`
`_,,L/o I
`
`phase
`
`address selector
`
`f 2424 I
`~- .... ·---
`
`I
`I
`I
`I
`I
`I
`I
`I
`
`I
`I
`I
`I
`I
`I
`I
`I
`
`-------'
`I 2407 I
`
`I Sequence Y
`I 2405 I
`I 24SS I
`I 24241
`
`2412
`
`r------
`
`I
`I
`I
`I
`I
`I
`I
`I
`I
`:
`I
`I
`1
`!_ ______ •
`I
`
`I 24071
`n,_ 1(6)
`
`/""'
`
`t/ 0 3
`
`e •
`
`00
`•
`~
`~
`~
`
`~ = ~
`
`0
`(') ...
`
`~\,Ci
`N
`0
`0
`-....J
`
`('D
`('D
`
`.i;...
`
`rJJ =(cid:173)
`.....
`0 ....
`....
`
`Ul
`
`d r.,;_
`-....l
`'N
`00 = tit
`00 = = "'""'
`
`1 246s 1
`
`~/6. t/(OL)
`C Plf.10/( 4-~-r ")
`
`( f ~ I e:> IL A-IZ ~)
`
`Page 5 of 29
`
`
`
`U.S. Patent
`U.S. Patent
`
`Oct. 9, 2007
`Oct. 9, 2007
`
`Sheet 5 0f 15
`Sheet 5 of 15
`
`US 7,280,580 Bl
`US 7,280,580 B1
`
`8‘
`a:
`
`.........._
`\
`
`~
`V)
`
`.j
`C)“5&0
`t\
`·c
`t'(
`0
`ao
`~
`as
`g
`'=
`.5
`'E
`"O
`~
`~
`a
`5*
`e
`5
`
`~
`«L\
`\'(
`W
`
`Cl)
`r.l!I
`(d
`
`phase
`~
`
`(f
`
`600w"3A
`~\
`
`r.l'J
`C'->
`
`tr)
`In
`
`E
`~
`D
`~
`O
`0
`H
`~
`LL
`~
`
`Page 6 of 29
`
`Page 6 of 29
`
`
`
`U.S. Patent
`U.S. Patent
`
`Oct. 9, 2007
`Oct. 9, 2007
`
`Sheet 6 of 15
`Sheet 6 of 15
`
`US 7,280,580 Bl
`US 7,280,580 B1
`
`mwGQXSm3:
`
`Qmegtbvflat?
`
`,-....
`r,J
`rlJ
`d)
`
`j
`
`.
`\G
`....._
`\-l
`
`Page 7 of 29
`
`@8693 EFUQNQwqot
`
`"-""
`
`-
`...__
`~
`Q
`~ ~
`\J
`Q 41
`c~
`:t ef\
`
`Moo—o
`
`Page 7 of 29
`
`
`
`
`US 7,280,580 Bl
`
`'-l>
`
`\l
`
`U.S. Patent
`
`Oct. 9, 2007
`
`Sheet 7 of 15
`
`I~~ ,~
`
`•
`'
`'
`
`....-4
`
`...-1
`
`...-4
`
`...-1
`
`• •
`.
`•
`..
`,
`~
`~~ \0
`~~ ~
`~;:r ~
`~~ M
`
`("1,1
`...-1
`
`"':::t:-~
`\j ""
`.....
`.-\
`-\
`~~ 0
`~ 0-,..
`°'
`~~ co
`t'-
`
`M
`
`~
`
`fffi~
`~ tfijN
`~\
`.. .
`~
`V)
`1
`
`~
`
`~
`
`C'r)
`
`~
`
`('-
`
`Page 8 of 29
`
`
`
`U.S. Patent
`U.S. Patent
`
`Oct. 9, 2007
`Oct. 9, 2007
`
`Sheet 8 of 15
`Sheet 8 of 15
`
`US 7,280,580 Bl
`US 7,280,580 B1
`
`. "
`'
`~~ -
`~ ~
`~~
`~~
`~J
`'f-1
`!::' ~
`
`\\
`
`3:33$13N4.23
`
`fivu‘v‘xu“0%
`
`'
`'
`
`«2.x,w\\\q\m¢vhdM\Vmw.fiu§H
`
`Page 9 of 29
`
`~~
`~~
`~~
`~~
`~'v,
`~ri
`\J~
`~
`
`Page 9 of 29
`
`
`
`
`U.S. Patent
`
`Oct. 9, 2007
`
`Sheet 9 of 15
`
`US 7,280,580 Bl
`
`DETERMINE PRESET HOP
`CHANNEL AS FUNCTION OF PHASE
`
`901
`
`YES
`
`903
`
`NO
`
`INDEX=MOD(CLOCK,N2)+8ASE VALUE
`
`PRESENT HOP CHANNEL=TABLE(INDEX)
`
`USE PRESENT HOP CHANNEL
`
`905
`
`907
`
`909
`
`FIG. 9
`
`Page 10 of 29
`
`
`
`U.S. Patent
`
`Oct. 9, 2007
`
`Sheet 10 of 15
`
`US 7,280,580 Bl
`
`1001 ~
`
`(1003
`
`(1005
`
`IND EX HOP CHANNEL
`1
`HC 1
`2
`HC2
`3
`HC 3
`4
`HC4
`5
`HC5
`6
`HC6
`7
`HC7
`8
`HC8
`HC9·
`9
`.
`.
`.
`N1
`
`.
`.
`.
`HC N1
`
`FORBIDDEN
`INDICATOR
`0
`0
`1
`1
`0
`0
`1
`0
`0
`
`0
`
`FIG. 10
`
`Page 11 of 29
`
`
`
`U.S. Patent
`
`Oct. 9, 2007
`
`Sheet 11 of 15
`
`US 7,280,580 Bl
`
`N2 = NUMBER OF ALLOWABLE
`HOPS
`
`1101
`
`1107
`
`UPDATE
`PHASE
`
`YES
`
`1105
`
`PRESENT HOP CHANNEL =
`HOP CHANNEL (PHASE)
`
`NO
`
`OFFSET= MOD (CLOCK,N2)
`
`INDEX= 1
`
`1109
`
`1111
`
`NO
`
`INDEX= INDEX+1
`
`1115
`
`NO
`
`OFFSET=OFFSET-1
`INDEX = INDEX+1
`
`1119
`
`YES
`
`1121
`
`PRESENT HOP CHANNEL = HOP CHANNEL(INDEX)
`
`FIG. 11
`
`Page 12 of 29
`
`
`
`U.S. Patent
`
`Oct. 9, 2007
`
`Sheet 12 of 15
`
`US 7,280,580 Bl
`
`1201 ~
`
`(1003
`
`1005
`
`(
`
`(1203
`
`IND EX HOP CHANNEL
`1
`HC 1
`2
`HC2
`3
`HC3
`4
`HC4
`5
`HC5
`6
`HC6
`7
`HC7
`8
`HC8
`9
`HC9
`
`FORBIDDEN
`INDICATOR
`0
`0
`1
`1
`0
`0
`1
`0
`0
`
`N1
`
`HC N1
`
`0
`
`GAP COUNT
`a
`0
`1
`2
`2
`2
`3
`3
`3
`.
`
`.
`3
`
`FIG. 12
`
`Page 13 of 29
`
`
`
`U.S. Patent
`
`Oct. 9, 2007
`
`Sheet 13 of 15
`
`US 7,280,580 Bl
`
`N2 = NUMBER OF ALLOWABLE
`HOPS
`
`1301
`
`1307
`
`UPDATE
`PHASE
`
`YES
`
`1305
`
`PRESENT HOP CHANNEL =
`HOP CHANNEL (PHASE)
`
`NO
`
`OFFSET= MOD (CLOCK,N2) + 1
`
`LAST GAP COUNT= 0
`
`1309
`
`1311
`
`YES
`
`PRESENT HOP CHANNEL=
`HOP CHANNEL(OFFSET +LAST GAP COUNT)
`
`1315
`
`1317
`
`LAST GAP COUNT =
`GAP COUNT(OFFSET + LAST GAP COUNT)
`
`FIG. 13
`
`Page 14 of 29
`
`
`
`--~~~-~~!~-~-~-~~~E.~~-----------------------------------------------------; 1'(13 / '~
`! /
`master identity-1'1° 3
`(t(I I '---'Jt--t, P
`A_O
`1 r _,..
`(3. rn
`II I
`::r..ut>, C.,B"5
`LI
`/7 Q 'l'
`..-------.i
`- , c..-t, l/,v
`/'-f O
`0
`0
`0
`1
`
`28
`
`I , - '
`
`/
`
`•• - ,
`
`~LAx 17
`
`2
`
`0
`
`,,-,,110/
`master CLK 1 ,
`27
`
`._
`
`MAS
`
`Z'
`
`e •
`
`00
`•
`~
`~
`~
`
`~ = ~
`
`0
`
`(') ...
`
`~\,Ci
`N
`0
`0
`-....J
`
`('D
`('D
`
`.i;...
`
`rJJ =(cid:173)
`.....
`....
`0 ....
`....
`
`Ul
`
`SEL
`-i---
`
`7
`
`.1
`
`OU
`
`11f _/ i i i
`
`reset NJ N2
`
`f-(~, 11/
`
`4
`
`I
`78
`
`1
`
`1
`
`0
`
`1
`
`2
`
`2
`
`1
`
`3
`
`0
`
`1
`
`c=b~d=J
`--------~-------~
`
`hop
`
`avoid M
`
`d r.,;_
`
`-....l
`'N
`00 = tit
`00 = = "'""'
`
`Page 15 of 29
`
`
`
`Fir;,. ,s(q.)
`
`original
`F,-1-
`s ET &l( e ltJCef
`
`11111'1111111111/1 I I
`32 2 62 43 5 6 71 28 9 30 11 10 55 14 5 63 ....
`
`0
`(') ...
`
`~\,Ci
`N
`0
`0
`-....J
`
`1~0(
`
`ts'03
`
`e •
`
`00
`•
`~
`~
`~
`
`~ = ~
`
`Ftb. ;s{p)
`
`R.1:i/1 sCD
`r- 1-I-
`St5' ro..u~,Jc~
`
`u
`
`32 2 73 43 6 6 71 28 9 30 11 10 55 14 25 63 ....
`
`('D
`('D
`
`rJJ =(cid:173)
`.....
`....
`Ul
`0 ....
`....
`
`Ul
`
`d r.,;_
`-....l
`'N
`00 = tit
`00 = = """"
`
`Page 16 of 29
`
`
`
`US 7,280,580 Bl
`
`1
`HOP SEQUENCE ADAPTATION IN A
`FREQUENCY-HOPPING COMMUNICATIONS
`SYSTEM
`
`BACKGROUND
`
`30
`
`2
`signature sequence. At the receiver, the same unique signa(cid:173)
`ture sequence is used to recover the underlying informa(cid:173)
`tional data stream signal.
`In frequency hopping systems, the spreading is achieved
`5 by transmitting the informational data stream over ever(cid:173)
`changing radio frequencies. For each connnunication, the
`particular frequencies used by both the transmitter and
`receiver are determined by a predefined frequency hop
`sequence. The use of frequency hopping is attractive for the
`10 radio applications mentioned above because it more readily
`allows the use of cost effective radios.
`A system called Bluetooth was recently introduced to
`provide pervasive connectivity especially between portable
`devices like mobile phones, laptops, personal digital assis(cid:173)
`tants (PDAs), and other nomadic devices. This system
`applies frequency hopping to enable the construction of
`low-power, low-cost radios with a small footprint. The
`system supports both data and voice. The latter is optimized
`by applying fast frequency hopping in combination with a
`20 robust voice coding. The fast frequency hopping has a
`nominal rate of 800 hops per second (hops/s) through the
`entire 2.4 GHz ISM band. Devices based on the Bluetooth
`system concept can create so called piconets, which com-
`prise a master device and one or more slave devices con(cid:173)
`nected via the FH piconet channel. The FH sequence used
`for the piconet channel is completely determined by the
`address or identity of the device acting as the master. The
`system clock of the master device determines the phase in
`the hopping sequence (i.e., the designation of which one of
`the possible hops in the sequence is the "current" hop). In the
`Bluetooth system, each device has a free-running system
`clock. Each of the slave devices adds a corresponding time
`offset to its clock that enables it to become aligned with the
`clock of the master device. By using the master address to
`35 select the proper hopping sequence and by using the time
`offset to align to the master clock, each slave device keeps
`in hop synchrony to the master device; that is, master and
`slave devices remain in contact by hopping synchronously to
`the same hop frequency or hop carrier. For more details,
`40 reference is made to U.S. patent application Ser. No. 08/932,
`911, filed on Sep. 18, 1997 in the name of J.C. Haartsen and
`entitled "Frequency Hopping Piconets in an Uncoordinated
`Wireless Multi-user System," which is hereby incorporated
`herein by reference in its entirety.
`The hop sequences used in the Bluetooth system are
`generated through a hop selection mechanism as described
`in U.S. patent application Ser. No. 08/950,068, filed on Oct.
`24, 1997 in the name of J.C. Haartsen and entitled "Method
`and Apparatus for the Generation of Frequency Hopping
`50 Sequences," which is hereby incorporated herein by refer(cid:173)
`ence in its entirety. With this method, hop carriers are
`generated "on the fly". The mechanism has no inherent
`memory: address and clock information instantaneously
`determine the sequence and phase and therefore directly
`55 determine the desired hop carrier. The advantages of such a
`selection scheme are numerous. By changing address and
`clock, a device can jump from one FH piconet channel
`controlled by one address/clock combination to another
`piconet controlled by another address/clock combination. In
`60 this regard, reference is also made to the aforementioned
`application U.S. Ser. No. 08/932,911 describing FH piconets
`in an uncoordinated wireless multi-user system.
`Radio connnunications intended for local connectivity
`between consumer applications require the use of a free and
`65 unlicensed band. As mentioned before, the ISM band at 2.45
`GHz is a suitable band because it is available globally
`(although the specific part of the ISM band that may be used
`
`The invention relates to connnunication systems where
`transmitter and receiver make use of a hop sequence to
`remain in contact. More particularly, the invention relates to
`techniques for dynamically skipping certain hops of the hop
`sequence.
`In the last several decades, progress in radio and Very
`Large Scale Integrated circuit (VLSI) technology has fos(cid:173)
`tered widespread use of radio connnunications in consumer 15
`applications. Portable devices, such as mobile radios, can
`now be produced having acceptable cost, size and power
`consumption.
`Although wireless technology is today focused mainly on
`voice connnunications ( e.g., with respect to handheld
`radios), this field will likely expand in the near future to
`provide greater information flow to and from other types of
`nomadic devices and fixed devices. More specifically, it is
`likely that further advances in technology will provide very
`inexpensive radio equipment that can easily be integrated 25
`into many devices. This will reduce the number of cables
`currently used. For instance, radio connnunication can
`eliminate or reduce the number of cables used to connect
`master devices ( e.g., personal computers) with their respec-
`tive peripherals ( e.g., printers).
`The aforementioned radio connnunications will require
`an unlicensed band with sufficient capacity to allow for high
`data rate transmissions. A suitable band is the Industrial
`Scientific and Medical (ISM) band at 2.45 GHz, which is
`globally available. The band provides 83.5 MHz of radio
`spectrum.
`To allow different radio networks to share the same radio
`medium without coordination, signal spreading is usually
`applied. In fact, the Federal Connnunications Connnission
`(FCC) in the United States currently requires radio equip(cid:173)
`ment operating in the 2.4 GHz band to apply some form of
`spectrum spreading technique when the transmit power
`exceeds about O dBm. Spread spectrum connnunication
`techniques, which have been around since the days of World 45
`War II, are of interest in today's connnercial applications
`because they provide robustness against interference, and
`allow for multiple signals to occupy the same radio band at
`the same time.
`Spreading can either be at the symbol level by applying
`direct-sequence (DS) spread spectrum techniques or at the
`channel level by applying frequency hopping (FH) spread
`spectrum techniques. In DS spread spectrum, the informa(cid:173)
`tional data stream to be transmitted is impressed upon a
`much higher rate data stream known as a signature sequence.
`Typically, the signature sequence data are binary, thereby
`providing a bit stream. One way to generate this signature
`sequence is with a pseudo-noise (PN) process that appears
`random, but can be replicated by an authorized receiver. The
`informational data stream and the high bit rate signature
`sequence stream are combined to generate a stream of
`so-called "chips" by multiplying the two bit streams
`together, assuming the binary values of the two bit streams
`are represented by +1 or -1. This combination of the higher
`bit rate signal with the lower bit rate data stream is called
`spreading the informational data stream signal. Each infor(cid:173)
`mational data stream or channel is allocated a unique
`
`Page 17 of 29
`
`
`
`US 7,280,580 Bl
`
`10
`
`35
`
`3
`may differ per country or continent). Because no license is
`needed, more applications that use radios in these bands are
`emerging. Applications range from low-power baby moni(cid:173)
`tors and garage door openers, to high-power radio frequency
`(RF) identification (ID) and Wireless Local Area Network
`(LAN) systems. For a wireless system such as Bluetooth,
`these other users are experienced as interferers. Frequency
`hopping provides a certain level of immunity against these
`interferers: when a Bluetooth connection lands on a hop
`carrier already in use by another radio system, it may
`experience interference for the duration of the hop dwell
`time. However, since the Bluetooth radio hops at a nominal
`rate of 800 hops/s, the dwell time is only 1.25 milliseconds
`(ms) after which the radio will hop to another channel. Since
`the range over which the radio is hopping is 80 MHz wide, 15
`the probability that the next hop is also occupied is rather
`small. Data protocols at a higher layer level can deal with
`distorted information, for example by applying a retrans(cid:173)
`mission scheme or an error-correction scheme. However,
`performance can be improved if the FH channel can avoid 20
`those hop frequencies associated with heavy interference. In
`particular, if there are narrowband interference sources
`(')annners") that continuously occupy one or more hop
`channels (so-called continuous-wave or CW jammers), the
`throughput of the piconet channel can especially be 25
`improved if both the hopping transmitter and the receiver
`can skip the interfered hop frequencies and instead hop to a
`clean hop carrier. Skipping certain hops may also be ben(cid:173)
`eficial in those instances in which a certain band in the
`spectrum is reserved for high-rate links, which do not
`tolerate interference. Frequency hopping Bluetooth devices
`within range of such high-rate links could prioritize these
`links by avoiding hopping into the reserved band. An
`advanced system that makes use of both a hopping channel
`for low-rate services and a dynamically selected semi-fixed
`channel for high-rate services is described in U.S. patent
`application Ser. No. 09/385,024, filed on Aug. 30, 1999 in
`the name of J.C. Haartsen and entitled "Resource Manage(cid:173)
`ment in Uncoordinated Frequency Hopping System", which
`is hereby incorporated herein by reference in its entirety.
`Another situation in which adapting the hop sequence
`may be beneficial is the one in which a fast hopper and a
`slow hopper share the same spectrum. The fast hopper may
`then remove the hop carrier out of his FH sequence that
`corresponds to the hop carrier the slow hopper currently 45
`occupies. When the slow hopper hops to the next hop
`channel, the fast hopper must adapt its FH sequence.
`Skipping certain hop frequencies means changing the hop
`sequence such that one or more hop frequencies are removed
`from the sequence. However, hop removal must be adapt- 50
`able because the interference cannot be predicted (the band
`is unlicensed and any radio can make use of it) and may vary
`over time (for example, the band to avoid may be based on
`dynamic channel selection). That is, the hop sequences
`should be capable of dynamic adaptation in order to avoid 55
`one or more hop frequencies.
`In conventional systems like FH systems based on the
`IEEE 802.11 Wireless LAN (WLAN) standard, a restricted
`number of hopping sequences has been defined. In each
`sequence, each hop carrier is only visited once. Conse- 60
`quently, with 79 hop frequencies defined in this standard, the
`sequence length is only 79. These sequences are fixed,
`limited in size, limited in number, and can simply be stored
`as a list in a Read Only Memory (ROM) or other non(cid:173)
`volatile memory. When a new channel is established, a 65
`sequence is selected that preferably interferes as little as
`possible with already established hopping channels in the
`
`4
`same or adjacent areas. Since the sequences are stored,
`off-line processing can simply be carried out for example to
`remove one or more frequencies from the sequence.
`In contrast, there are a large number of possible FH
`5 sequences in the Bluetooth system. The sequence selected is
`based on 28 bits in the master identity. As a result, 2oo(i.e.,
`2 raised to the 28th power) or 268,435,456 different hop
`sequences are defined. In addition, the length of each
`sequence is determined by the master clock which counts
`from O to 2'27-1 at a rate of 1600 increments per second.
`The clock value wraps around back to zero after about 23.3
`hours.
`The number of possible sequences and the size of each
`sequence make it impossible to store the Bluetooth FH
`sequences and process them off-line. Instead, a selection
`mechanism is used as described in the above-referenced
`U.S. patent application Ser. No. 08/950,068. Adapting the
`FH sequences to avoid certain hop frequencies is not trivial,
`especially if there is also a requirement to preserve the
`feature whereby switching between different FH channels is
`performed by merely replacing the address and clock infor(cid:173)
`mation.
`Conventional techniques are inadequate for this purpose.
`For example, U.S. Pat. No. 5,848,095, which issued to
`Deutsch on Dec. 8, 1998, discloses a system and method for
`adaptive hopping, whereby frequencies are selected for
`substitution in a frequency hopping system by reference to
`30 time slots. In the exemplary embodiment, all units have four
`frequency hopping sequences allocated to them, designated
`A, B, C and D. A unit may, for example, be in a talking mode
`in which it uses group B to hop from channels Bl, B2, B3,
`and so on. If, for example, channel B3 is found to interfere,
`the channel would be "marked" as bad, and channel C3
`would substitute for channel B3. The result would be a
`hopping sequence consisting of Bl, B2, C3, B4, BS and so
`on. This strategy has a number of drawbacks. To begin with,
`it requires changes to the hop sequence generator. Moreover,
`40 because the strategy involves selecting a substitute channel
`from another hopping sequence, there is no guarantee that
`the selected substitute will be a suitable channel. For
`example, in the above-illustrated case, there is no certainty
`that the substitute channel C3 is usable. In such cases, this
`document describes making yet another selection from
`another group ( e.g., selecting channel D3 from group D) and
`repeating this operation until a suitable substitute channel is
`selected. However, this strategy can't guarantee that an
`acceptable substitute channel will always be found without
`prestoring an overwhelming number of hopping sequences.
`U.S. Pat. No. 5,515,369, which issued to Flammer, III et
`al. on May 7, 1996 discloses a method for frequency sharing
`and frequency punchout in a frequency hopping communi(cid:173)
`cations network. Bad channels are eliminated by means of a
`punchout mask. Having eliminated bad channels, a seed
`value is used to generate a randomly ordered channel
`hopping sequence from the remaining good channels.
`U.S. Pat. No. 5,619,493, which issued to Ritz et al. on Apr.
`8, 1997, discloses a spread-spectrum frequency-hopping
`radio telephone system with voice activation. A set of N
`carrier frequencies are reused in adjacent communications
`sites to provide more than N minimally cross-correlated
`frequency-hopping communication channels. A second hop(cid:173)
`ping sequence is derived from a first hopping sequence by
`selecting frequencies from the first set in their sequential
`order, skipping a first decimation number of frequencies in
`the sequence, and repeating this process on the remaining
`
`Page 18 of 29
`
`
`
`US 7,280,580 Bl
`
`6
`calls for an allowable hop channel. In all other cases, a
`substitute hop channel is dynamically selected from the set
`of allowable hop channels.
`In another aspect of the invention, the time-varying
`5 parameter may be a clock value. In some embodiments, the
`time-varying parameter and the present phase may be
`derived from a same clock value. In alternative embodi(cid:173)
`ments, the time-varying parameter may be a random value
`or a pseudo-random value.
`In yet another aspect of the invention, hop selection
`further comprises forming a sequence of allowable hop
`channels from the set of allowable hop channels. In this case,
`the operation of using a time-varying parameter to select a
`substitute hop channel from the set of allowable hop chan(cid:173)
`nels comprises forming an index value from the time(cid:173)
`varying parameter; using the index value to select one of the
`allowable hop channels from the sequence of allowable hop
`channels; and using the selected allowable hop channel as
`the substitute hop channel.
`In still another aspect of the invention, the operation of
`forming the index value from the time-varying parameter
`comprises determining the expression:
`
`index value~mod(time-varying parameter, N2)+
`BASE VALUE,
`
`25
`
`10
`
`5
`frequencies in the first sequence in their remaining order.
`Other hop sequences are similarly derived by using different
`decimation numbers.
`U.S. Pat. No. 5,809,059, which issued to Souissi et al. on
`Sep. 15, 1998, discloses a method and apparatus for spread
`spectrum channel assignment. The technique includes com(cid:173)
`puting average noise and interference levels for different
`sequences of channels, and then selecting that one of the
`sequences of channels having the lowest average noise and
`interference level for a next transmission of information.
`U.S. Pat. No. 4,606,040, which issued to David et al. on
`Aug. 12, 1986, discloses a transmitting-receiving station for
`a system for transmitting data by frequency hopping. In
`order to facilitate synchronization between two units when
`one is in a standby mode, a code generator defines the use 15
`of a plurality of channels in accordance with a so-called
`high-speed skip law for a transmitting-receiving station in
`either of the transmitting or receiving modes, and in accor(cid:173)
`dance with a so-called low-speed skip law for a transmitting(cid:173)
`receiving station in the stand-by mode. The high-speed skip 20
`law consists of the use of each of the channels during a time
`TP, while the low-speed skip law governs the changes of the
`listening channels employed during NxTP, each correspond(cid:173)
`ing to a center channel of a sequence of N channels of the
`high-speed skip law.
`U.S. Pat. No. 4,023,103, which issued to Malm on May
`10, 1977, discloses a synchronizer for synchronizing a
`frequency hopping receiver with a companion frequency
`hopping transmitter. The synchronizer includes an electronic
`clock that provides timing pulses for activating a pseudo- 30
`random sequence generator at the frequency hopping rate,
`and means that cause the clock to skip one activating pulse
`every N successive frequency hopping periods, until a
`frequency hopping local signal and a frequency hopping
`signal from the companion receiver are out of sync by less 35
`than one frequency hopping period.
`Each of the above-cited documents discloses a technique
`for skipping certain hops that has drawbacks, including the
`fact that each requires changes to the hop sequence genera- 40
`tor.
`There is therefore a need for methods and apparatuses for
`removing specific hop frequencies from an arbitrary hopping
`sequence. There is also a need for accomplishing this
`without requiring off-line processing. It is also desirable to 45
`be able to adapt hop sequences dynamically, and to apply
`this adaptation to any existing hop selection scheme or
`existing hop sequence.
`
`where mod G,k) denotes j modulo k, N2 is the number of
`allowable hop channels in the sequence of allowable chop
`channels and BASE VALUE represents an index value of the
`first allowable hop channel in the sequence of allowable hop
`channels.
`In yet another aspect of the invention, the operation of
`using a time-varying parameter to select a substitute hop
`channel from the set of allowable hop channels comprises
`determining an index value, i, as a function of the time(cid:173)
`varying parameter; designating one of the allowable hop
`channels in the sequence of hop channels as a first hop
`channel; starting at the first hop channel, processing the
`sequence of hop channels to determine an ith allowable hop
`channel in the sequence of hop channels; and selecting the
`ith allowable hop channel for use as the substitute hop
`channel.
`In some embodiments, the first hop channel may be the
`first hop channel in the sequence of hop channels. In
`alternative embodiments, the first hop channel may be a first
`hop channel after a last forbidden hop channel in the
`sequence of hop channels. In this case, the operation of
`processing the sequence of hop channels to determine an ith
`allowable hop channel in the sequence of hop channels
`50 wraps around to the start of the sequence of hop channels
`when i is greater than the number of hop channels following
`the last forbidden hop channel in the sequence of hop
`channels.
`In still another aspect of the invention, the operation of
`processing the sequence of hop channels to determine an ith
`allowable hop channel in the sequence of hop channels may
`alternatively comprise, starting at the first hop channel and
`continuing with each successive hop channel in the sequence
`of hop channels, determining whether the hop channel is an
`allowable hop channel; and stopping when an ith allowable
`hop channel has been identified in the sequence of hop
`channels.
`In yet another aspect of the invention, the technique
`further comprises determining a gap count for each of the
`hop channels in the sequence of hop channels, wherein the
`gap count represents how many forbidden hop channels are
`in the sequence of hop channels from the first hop channel
`
`SUMMARY
`
`In accordance with the present invention, a hop channel is
`selected for use in a channel hopping communication system
`that includes a sequence of hop channels, wherein the
`sequence comprises a set of forbidden hop channels and a 55
`remaining set of allowable hop channels. In accordance with
`one aspect of the invention, selection involves selecting a
`hop channel from the sequence as a function of a present
`phase. If the selected hop channel is an allowable hop
`channel, then the selected hop channel is used for commu- 60
`nication during the present phase. If the selected hop channel
`is a forbidden hop channel, then a time-varying parameter is
`used to select a substitute hop channel from the set of
`allowable hop channels. The substitute hop channel is then
`used for communication during the present phase. With this 65
`strategy, the resultant hopping sequence is identical to the
`original hopping sequence whenever the original sequence
`
`Page 19 of 29
`
`
`
`US 7,280,580 Bl
`
`7
`up to and including said each of the hop channels. In these
`embodiments, the operation of processing the sequence of
`hop channels to determine an ith allowable hop channel in
`the sequence of hop channels comprises (a) using the index
`value plus a previous gap count to select one of the hop
`channels from the sequence of hop channels; and (b) using
`the selected hop channel as the substitute hop channel if the
`selected hop channel is associated with a present gap count
`that is equal to the previous gap count, otherwise setting the
`previous gap count equal to the present gap count and
`repeating operations (a) and (b ).
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`8
`selection mechanism visits a "forbidden" hop, an offset may
`be temporarily added to the phase such that an allowed hop
`is instead selected. The offset is only applied when a
`forbidden hop is selected. When an allowed hop is selected,
`5 no adjustment is made. As used throughout this disclosure,
`the term "forbidden" refers to a hop channel that should be
`avoided during communication for any of a number of
`reasons. For example, the detection of a substantial amount
`of interference on a hop channel may make it desirable to
`10 avo