`US 7,280,580 Bl
`(10) Patent No.:
`(12)
`Haartsen
`(45) Date of Patent:
`Oct. 9, 2007
`
`
`US007280580B1
`
`(54) HOP SEQUENCE ADAPTATIONIN 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 ofthis
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 0 days.
`
`(21) Appl. No.: 09/418,562
`
`(22)
`
`Filed:
`
`Oct. 15, 1999
`
`(51)
`Int. Cl.
`(2006.01)
`HOo4B 100
`375/138: 375/132
`(2) US. Cl
`375/200
`Fi ld f Clue;ficati —S weeh.
`58
`(58)
`Fie 378720513Ol33.a55/450,AGA: 370/338,
`poe °
`370(333. 330
`°
`lication
`file
`f
`let
`h hist
`?
`Se application
`Mile
`TOF COMPICHE Seared
`DISTOFY.
`References Cited
`
`(56)
`
`S
`
`U.S. PATENT DOCUMENTS
`4.023.103 A
`5/1977 Malm
`4,476,566 A * 10/1984 Dent voces 375/132
`4,606,040 A
`8/1986 David et al.
`4,716,573 A * 12/1987 Bergstrom et al.
`.......... 375/132
`
`4,780,885 A * 10/1988 Paul et al. wi . 375/267
`5,307,348 A .
`4/1994 Buchholz et al.
`2oe40g ‘
`Sood aus ctal sereeeeeeecases 455/464
`5515369 A
`5/1996 ae ae Tet al
`5,619,493 A
`4/1997 Ritz et al.
`5,737,358 A
`4/1998 Ritz et al.
`A
`5,809,059
`9/1998 Souissi et al.
`
`
`11/1998 Li
`5,832,026 A
`12/1998 Deutsch
`5,848,095 A
`2/1999 Nago
`5,870,391 A
`4/1999 Satyanarayana
`5,898,733 A
`6,480,721 B1* 11/2002 Sydon et al. ow. 455/464
`FOREIGN PATENT DOCUMENTS
`
`0182762 Al
`EP
`WO099/0967 1
`WO
`W099/19993
`wo
`* cited by examiner
`
`5/1986
`2/1999
`4/1999
`
`.
`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 comprisesa set of forbidden
`hop channels and a remaining set ofallowable hop channels.
`Selection involves
`selecting a hop channel
`from the
`sequenceas a function of a present phase. Ifthe selected hop
`channel is an allowable hop channel, then the selected hop
`channel is used for communication during the present phase.
`P
`P
`If the selected hop
`channelis 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-
`stitute hop channelis 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 wheneverthe original sequence calls for an allow-
`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
`
`905
`
`907
`
`Ex. 1008 / Page 1 of 29
`ERICSSON v. UNILOC
`
`909
`
`
`
`PRESENT HOP
`
`CHANNEL ALLOWABLE?
`
`NO
`
`INDEX=MOD(CLOCK,N2)+BASE VALUE L
`
`PRESENT HOP CHANNEL=TABLE(INDEX)
`
`
`
`Y
`
`USE PRESENT HOP CHANNEL
`
`K
`
`Ex. 1008 / Page 1 of 29
`ERICSSON v. UNILOC
`
`
`
`U.S. Patent
`
`Oct. 9, 2007
`
`Sheet 1 of 15
`
`US 7,280,580 B1
`
`
`
`24802¥f/Freq(MHz)
`
`tH
`
`FIGURE1
`
`Ex. 1008 / Page 2 of 29
`ERICSSON v. UNILOC
`
`Ex. 1008 / Page 2 of 29
`ERICSSON v. UNILOC
`
`
`
`U.S. Patent
`
`Oct. 9, 2007
`
`Sheet 2 of 15
`
`US 7,280,580 B1
`
`
`
`(zHW)baiyFerosyz
`
`8Lbz
`
`907SOPZHOPZOPTze[0fhe
`
`‘ s
`
`(Qea4
`
`Ex. 1008 / Page 3 of 29
`ERICSSON v. UNILOC
`
`
`
`(ZHW)basytiseose
`BLYZ
`
`QOLSOTPOPEcopewrelOhr
`
`é
`
`(B®)A/a
`
`Ex. 1008 / Page 3 of 29
`ERICSSON v. UNILOC
`
`
`
`
`Oct. 9, 2007
`
`Sheet 3 of 15
`
`US 7,280,580 B1
`
`U.S. Patent
`
`
`(ZHW)basy|3/cogayeLICOpe?sozyorecorezoeIP
`
`
`TTTTT
`
`
`
`
`(ZHW)baryi3peosveSipeOveYZSOPZPORTOrewee142
`SHITTPTTT
`
`(o)¢“9/4
`
`(VEPIs
`
`Ex. 1008 / Page 4 of 29
`ERICSSON v. UNILOC
`
`Ex. 1008 / Page 4 of 29
`ERICSSON v. UNILOC
`
`
`
`U.S. Patent
`
`Oct. 9, 2007
`
`Sheet 4 of 15
`
`US 7,280,580 B1
`
`
`
`10)D9[98ssamppe
`
`oseyd
`
`aseyd
`
`)of,
`
`C42”22/24)(Pp9
`
`C49Y17%)
`(7),9d
`
`Ex. 1008 / Page 5 of 29
`ERICSSON v. UNILOC
`
`Ex. 1008 / Page 5 of 29
`ERICSSON v. UNILOC
`
`
`
`
`
`
`U.S. Patent
`
`Oct. 9, 2007
`
`Sheet 5 of 15
`
`US 7,280,580 B1
`
`S—
`
`~
`
`9of als g
`5D
`5
`"a
`cy
`ey
`<
`E
`
`WY
`
`fs
`=
`C
`=,
`fr,
`
`Nw
`\
`
`ogP
`
`y
`
`S00
`
`Ex. 1008 / Page6 of 29
`ERICSSON v. UNILOC
`
`Ex. 1008 / Page 6 of 29
`ERICSSON v. UNILOC
`
`
`
`U.S. Patent
`
`Oct. 9, 2007
`
`Sheet 6 of 15
`
`US 7,280,580 B1
`
`ou
`
`o— L
`
`o03
`
`G
`yz
`\ 8
`vs
`
`CARLIGESToSEAVOIDED
`HOP
`
`AX
`
` (address)
`HopBELECTIOA
`
`Ex. 1008 / Page 7 of 29
`ERICSSON v. UNILOC
`
`6=o
`
`Ex. 1008 / Page 7 of 29
`ERICSSON v. UNILOC
`
`
`
`U.S. Patent
`
`Oct. 9, 2007
`
`Sheet 7 of 15
`
`US 7,280,580 B1
`
`“OLSTvitl7111Ol68LOSbPETTaiTTIOT|£
`oho4ytSion
`
`4‘9/4
`
`/04,
`Std
`
`Ex. 1008 / Page 8 of 29
`ERICSSON v. UNILOC
`
`Ex. 1008 / Page 8 of 29
`ERICSSON v. UNILOC
`
`
`
`
`Oct. 9, 2007
`
`Sheet 8 of 15
`
`U.S. Patent
`
`US 7,280,580 B1
`
`
`
`YNoneP/"eofLIPSAEODixsqe
`IM!ceoSTIAT|STICTIIT
`
`HVOW|OH
`
`Ex. 1008 / Page 9 of 29
`ERICSSON v. UNILOC
`
`Ex. 1008 / Page 9 of 29
`ERICSSON v. UNILOC
`
`
`
`U.S. Patent
`
`Oct. 9, 2007
`
`Sheet 9 of 15
`
`US 7,280,580 B1
`
`DETERMINE PRESET HOP
`CHANNEL AS FUNCTION OF PHASE
`
`
`
`PRESENT HOP
`
`CHANNEL ALLOWABLE2
`
`901
`
`905
`
`
`
`INDEX=MOD(CLOCK,N2)+BASE VALUE 907
`PRESENT HOP CHANNEL=TABLE(INDEX) 909
`
`
`
`
`
`
`USE PRESENT HOP CHANNEL
`
`FIG. 9
`
`Ex. 1008 / Page 10 of 29
`ERICSSON v. UNILOC
`
`Ex. 1008 / Page 10 of 29
`ERICSSON v. UNILOC
`
`
`
`U.S. Patent
`
`Oct. 9, 2007
`
`Sheet 10 of 15
`
`US 7,280,580 B1
`
`1001
`
`HOP CHANNEL
`
`FORBIDDEN
`INDICATOR
`
`N1
`z oO mxOOnNODOoaAWD=
`
`FIG. 10
`
`Ex. 1008 / Page 11 of 29
`ERICSSON v. UNILOC
`
`Ex. 1008 / Page 11 of 29
`ERICSSON v. UNILOC
`
`
`
`U.S. Patent
`
`Oct. 9, 2007
`
`Sheet 11 of 15
`
`US 7,280,580 B1
`
`N2 = NUMBER OF ALLOWABLE
`HOPS
`
`1101
`
`1103
`
`
`ORBIDDEN INDICATOR(PHASE)= 07
`
`YES
`
`
`
`1107
`
`UPDATE
`PHASE
`
`1105
`
`PRESENT HOP CHANNEL=
`HOP CHANNEL(PHASE)
`
`NO
`
`OFFSET = MOD (CLOCK,N2)
`
`INDEX = 1
`
`1109
`
`1111
`
`NO
`
`
`
`1113
`
`
`
`FORBIDDEN INDICATOR (INDEX) = 0?
`
`
`
`YES
`
`1117
`
`INDEX = INDEX+1
`
`1115
`
`NO
`
`OFFSET=OFFSET-1
`INDEX = INDEX+1
`
`1119
`
`YES
`
`PRESENT HOP CHANNEL = HOP CHANNEL(INDEX)
`
`1121
`
`FIG. 11
`
`Ex. 1008 / Page 12 of 29
`ERICSSON v. UNILOC
`
`Ex. 1008 / Page 12 of 29
`ERICSSON v. UNILOC
`
`
`
`U.S. Patent
`
`Oct. 9, 2007
`
`Sheet 12 of 15
`
`US 7,280,580 B1
`
`1201 7}
`
`( 1003
`
`HOP CHANNEL
`
`( 100°
`
`FORBIDDEN
`INDICATOR
`
`N1
`= Oo mM<OONOOFWN=
`
`( 1203
`
`GAP COUNT
`
`FIG. 12
`
`Ex. 1008 / Page 13 of 29
`ERICSSON v. UNILOC
`
`Ex. 1008 / Page 13 of 29
`ERICSSON v. UNILOC
`
`
`
`U.S. Patent
`
`Oct. 9, 2007
`
`Sheet 13 of 15
`
`US 7,280,580 B1
`
`1307
`
`UPDATE
`PHASE
`
`N2 = NUMBER OF ALLOWABLE
`HOPS
`
`1303
`
`
`
`
`
`YES
`
`1305
`
`
`
`ORBIDDEN INDICATOR (PHASE)= 0%
`
`PRESENT HOP CHANNEL=
`HOP CHANNEL(PHASE)
`
`NO
`
`
`
`1301
`
`1309
`
`1311
`
`NO
`
`OFFSET = MOD (CLOCK,N2) + 1
`
`LAST GAP COUNT =0
`
`YES
`
`GAP COUNT(OFFSET+LAST GAP COUNT)
`= LAST GAP COUNT?
`
`
`
`HOP CHANNEL(OFFSET+LAST GAP COUNT)
`
`PRESENT HOP CHANNEL=
`
`1315
`
`1317
`
`LAST GAP COUNT=
`GAP COUNT(OFFSET + LAST GAP COUNT)
`
`FIG. 13
`
`Ex. 1008 / Page 14 of 29
`ERICSSON v. UNILOC
`
`Ex. 1008 / Page 14 of 29
`ERICSSON v. UNILOC
`
`
`
`
`
`
`
`
`
`SIf)1——————OUISYISWOMII|AS[RUTSLIO
`
`U.S. Patent
`
`LO"ODFatSeat
`
`
`
`
`
`av?-3JPHjNh)SohI~AyusptJ9)seur
`
`Oct. 9, 2007
`
`Sheet 14 of 15
`
`US 7,280,580 B1
`
`NTOap>ife|_|Aor
`
`vmeT
`
`ZNIN¥s91
`
`falB/at
`
`Ex. 1008 / Page 15 of 29
`ERICSSON v. UNILOC
`
`eee eee mw nw wee ee fem Tae eee en Beet ewes enewu
`
`Ex. 1008 / Page 15 of 29
`ERICSSON v. UNILOC
`
`
`
`
`U.S. Patent
`
`
`
`Eos))o.5/
`
`Oct. 9, 2007
`
`
`
`“"€9CHLSSOLTT0€F687IL9§$EhTOZVE
`
`PUWANDAS
`
`yeursio(“)5!94
`Ht
`
`
`
`Sheet 15 of 15
`
`US 7,280,580 B1
`
`“""€9SCPISSOLITOF68TIL9DEVELTT
`
`DWANVDASOSiAaYPpea
`
`Ex. 1008 / Page 16 of 29
`ERICSSON v. UNILOC
`
`Ex. 1008 / Page 16 of 29
`ERICSSON v. UNILOC
`
`
`
`US 7,280,580 B1
`
`1
`HOP SEQUENCE ADAPTATIONIN A
`FREQUENCY-HOPPING COMMUNICATIONS
`SYSTEM
`
`BACKGROUND
`
`The invention relates to communication systems where
`transmitter and receiver make use of a hop sequence to
`remain in contact. Moreparticularly, 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-
`tered widespread use of radio communications in consumer
`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 communications
`(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
`into many devices. This will reduce the number of cables
`currently used. For instance,
`radio communication 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 communications will require
`an unlicensed band with sufficient capacity to allow for high
`data rate transmissions. A suitable band is the Industrial
`
`30
`
`40
`
`45
`
`55
`
`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 Communications Commission
`(FCC)in the United States currently requires radio equip-
`ment operating in the 2.4 GHz band to apply some form of
`spectrum spreading technique when the transmit power
`exceeds about 0 dBm. Spread spectrum communication
`techniques, which have been aroundsince the days of World
`WarII, are of interest in today’s commercial applications
`because they provide robustness against interference, and
`allow for multiple signals to occupy the sameradio bandat
`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-
`tional data stream to be transmitted is impressed upon a
`muchhigherrate 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-
`mational data stream or channel
`is allocated a unique
`
`2
`signature sequence. At the receiver, the same unique signa-
`ture sequence is used to recover the underlying informa-
`tional data stream signal.
`In frequency hopping systems, the spreading is achieved
`by transmitting the informational data stream over ever-
`changing radio frequencies. For each communication, the
`particular frequencies used by both the transmitter and
`receiver are determined by a predefined frequency hop
`sequence. The use of frequency hoppingis attractive for the
`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-
`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. Thelatter is optimized
`by applying fast frequency hopping in combination with a
`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-
`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 sequenceis 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
`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,
`reference is madeto U.S. patent application Ser. No. 08/932,
`911, filed on Sep. 18, 1997 in the nameof 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 nameofJ. C. Haartsen and entitled “Method
`and Apparatus for the Generation of Frequency Hopping
`Sequences,” which is hereby incorporated herein by refer-
`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
`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
`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 communications intended for local connectivity
`between consumer applications require the use of a free and
`unlicensed band. As mentioned before, the ISM band at 2.45
`GHz is a suitable band because it
`is available globally
`(althoughthe specific part of the ISM band that may be used
`
`Ex. 1008 / Page 17 of 29
`ERICSSON v. UNILOC
`
`Ex. 1008 / Page 17 of 29
`ERICSSON v. UNILOC
`
`
`
`US 7,280,580 B1
`
`3
`maydiffer per country or continent). Because nolicense is
`needed, more applications that use radios in these bands are
`emerging. Applications range from low-power baby moni-
`tors and garage door openers, to high-powerradio 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,
`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-
`mission scheme or an error-correction scheme. However,
`performance can be improved if the FH channel can avoid
`those hop frequencies associated with heavy interference. In
`particular,
`if there are narrowband interference sources
`(“jammers”) that continuously occupy one or more hop
`channels (so-called continuous-wave or CW jammers), the
`throughput of the piconet channel can especially be
`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-
`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 nameof J. C. Haartsen and entitled “Resource Manage-
`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
`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
`sequencesuchthat one or more hop frequencies are removed
`from the sequence. However, hop removal must be adapt-
`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
`one or more hop frequencies.
`In conventional systems like FH systems based on the
`TEEE 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-
`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-
`volatile memory. When a new channel
`is established, a
`sequence is selected that preferably interferes as little as
`possible with already established hopping channels in the
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`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
`sequences in the Bluetooth system. The sequence selected is
`based on 28 bits in the master identity. As a result, 200(1.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 0 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 numberof 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
`
`USS. patent application Ser. No. 08/950,068. Adapting the
`FH sequencesto avoid certain hop frequenciesis nottrivial,
`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-
`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
`timeslots. 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 B1, B2, B3,
`and so on. If, for example, channel B3 is foundto 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 B1, B2, C3, B4, B5 and so
`on. This strategy has a numberof drawbacks. To begin with,
`it requires changes to the hop sequence generator. Moreover,
`becausethe 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 channelis
`selected. However,
`this strategy can’t guarantee that an
`acceptable substitute channel will always be found without
`prestoring an overwhelming numberof hopping sequences.
`U.S. Pat. No. 5,515,369, which issued to Flammer,III et
`al. on May7, 1996 discloses a method for frequency sharing
`and frequency punchout in a frequency hopping communi-
`cations network. Bad channels are eliminated by meansof 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.
`USS. Pat. No. 5,619,493, which issuedto 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-
`ping sequenceis derived from a first hopping sequence by
`selecting frequencies from the first set in their sequential
`order, skipping a first decimation numberof frequencies in
`the sequence, and repeating this process on the remaining
`
`Ex. 1008 / Page 18 of 29
`ERICSSON v. UNILOC
`
`Ex. 1008 / Page 18 of 29
`ERICSSON v. UNILOC
`
`
`
`US 7,280,580 B1
`
`5
`frequencies in the first sequence in their remaining order.
`Other hop sequencesare similarly derived by using different
`decimation numbers.
`
`USS. Pat. No. 5,809,059, which issued to Souissiet al. on
`Sep. 15, 1998, discloses a method and apparatus for spread
`spectrum channel assignment. The technique includes com-
`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.
`
`USS. 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
`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-
`dance with a so-called low-speed skip law for a transmitting-
`receiving station in the stand-by mode. The high-speed skip
`law consists of the use of each of the channels during a time
`T,,, while the low-speed skip law governs the changes of the
`listening channels employed during NxT,,, each correspond-
`ing to a center channel of a sequence of N channels of the
`high-speed skip law.
`USS. 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 includesan electronic
`clock that provides timing pulses for activating a pseudo-
`random sequence generator at the frequency hoppingrate,
`and meansthat 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
`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-
`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
`be able to adapt hop sequences dynamically, and to apply
`this adaptation to any existing hop selection scheme or
`existing hop sequence.
`
`SUMMARY
`
`In accordance with the present invention, a hop channelis
`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. 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-
`nication during the present phase. If the selected hop channel
`is a forbidden hop channel, then a time-varying parameteris
`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
`strategy, the resultant hopping sequence is identical to the
`original hopping sequence whenever the original sequence
`
`10
`
`15
`
`20
`
`25
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`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.
`the time-varying
`In another aspect of the invention,
`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-
`
`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-
`nels comprises forming an index value from the time-
`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,
`
`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 VALUErepresents an index value of the
`first allowable hop channelin 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-
`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 maybea 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
`wraps around to the start of the sequence of hop channels
`wheni is greater than the numberof 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 channelin the sequence
`of hop channels, determining whether the hop channelis an
`allowable hop channel; and stopping when an ith allowable
`hop channel has been identified in the sequence of hop
`channels.
`
`the technique
`In yet another aspect of the invention,
`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
`
`Ex. 1008 / Page 19 of 29
`ERICSSON v. UNILOC
`
`Ex. 1008 / Page 19 of 29
`ERICSSON v. UNILOC
`
`
`
`US 7,280,580 B1
`
`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 channelas the substitute hop channelif 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).
`
`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 hopis selected. When an allowed hop is selected,
`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 makeit desirable to
`avoid use of that hop channel, at least until the interference
`subsides. It may also be the case that one or more hop
`channels are known to be “reserved” for use by another
`system, so that a present system can avoid experiencing
`interference by avoiding these channels. Similarly, a nearby
`The objects and advantages of the invention will be
`system may be required to provide a high priority/high
`understood by reading the following detailed description in
`quality service via one or more hop channels. In this case, a
`conjunction with the drawings in which:
`present system can avoid causing interference on these
`FIG. 1 is a graph depicting an exemplary hop carrier
`channels (and thereby avoid disturbing the nearby system)
`definition in the ISM band;
`by avoiding the use of these hop channels. These are but
`FIGS. 2(a) and 2(6) are graphs depicting examples of hop
`mere examples of reasons why one or more hop channels
`carrier definitions in the ISM bandin caseof three individual
`may be denoted as “forbidden” hop channels. Those having
`narrowband interferers;
`ordinary skill in the art will recognize that other reasons
`FIGS. 3(a) and 3(6) are graphs depicting examples of hop
`exist as well, and all such reasons are considered within the
`carrier definitions in the ISM band in case of a single
`scope of the invention. It will also be recognized that the
`widebandinterferer;
`designation of a hop channelas alternatively “forbidden” or
`FIGS. 4(a) and 4(6) illustrate a hop carrier selection
`“allowed” need not be static, but can instead be determined
`technique that utilizes a pre-stored sequence;
`and changed dynamically. For example, an allowed hop
`FIG. 5 is a block diagram of an exemplary hop carrier
`channel may become “forbidden” in response to the detec-
`selector for the case of on-the-fly sequence generation;
`tion of interference on that hop channel, and may later be
`FIG.6 is a block diagram illustrating the general concept
`again designated as “allowed” when it is detected that the
`of a hop avoidance schemein accordance with the invention;
`interference has sufficiently abated.
`FIG.7 is a diagram of a hop sequence havingatotal of N1
`In another aspect of the invention, for each phase value
`hop channels;
`associated with a forbidden hop, the transformation of the
`FIG.8 is a block dia