.
`
`Unlted States Patent [19]
`Bantz et al.
`
`[54] BROADCAST-INITIATED BIPARTITE
`
`FRAME MULTl-ACCESS PROTOCOL
`
`[75] Invemors: David R Bantzi Chappaqua~ N'Y‘I
`.Robert T. Cato, Raleigh. NC;
`Chis-chi Huang, Yorktown Heights,
`NY‘
`{73] Assignee: International Business Machines
`Corporation, Armonk, NY.
`
`[2]] Appl' No': 718525
`[22] Filed:
`Jun. 21, 1991
`[51] Int. Cl.-‘ ............................................. .. H04K 9/00
`[52] us. Cl. ...................................................... .. 375/1
`[58] Field of Search .......................................... .. 375/ l
`.
`References cued
`US. PATENT DOCUMENTS
`
`[56]
`
`4.271.523 7/l98l Gable ............................... ,. 37l/57.l
`4.783.799 ll/1988 Maass ............................... .. 455/261
`
`llllllllllllllllllllllIlllllllllIllllllllllllllllllllllllllllllllllllllllll
`[ll] Patent Number:
`5,123,029
`[45] Date of Patent:
`Jun. 16, 1992
`
`USOO5l23029A
`
`,
`
`_
`
`_
`
`_
`
`4.841.527 6/1989 Raychaudhurietal. ............. .. 375/1
`Primary Examiner-Salvatore Cangralost
`Attorney. Agent. or Firm—-Whitham 8: Marhoefer
`_
`ABSTRACT
`[57]
`A hybrid of controlled access and random access
`Schemes using frequency hopping Spread spectrum
`communication techniques is implemented in an indoor
`digital data radio communication system between mo
`bile stations and a computer system. A hop in the fre
`quency hopping spread spectrum communication sys
`‘em is subdivided in” ‘W0 imervals 5° ‘ha‘ dim-‘em
`medimccess PYO‘OCOIS can be used in each “mm!
`The Protocol uses a centralized comm} Scheme in one
`interval and a decentralized scheme in the other, and
`the intervals may be varied depending on the load of the
`system.
`
`14 Claims, 5 Drawing Sheets
`
`@ TRANSHIT FROM
`TRANSMIT DUEUE
`RECElVE
`ACKNOWLEDGEMENT
`
`X2 HESS.
`RECEIVED
`
`PHASE C
`
`Jiso
`
`YES
`SET PHASE TDC
`SET TIMER TD C DURATION
`SET SLDTTlMER T0 RANDOM
`MULTIPLE OF SLOT WlDlH
`
`/is4
`TRANSMIT FROM
`TRANSMIT OUEUE
`RECEIVE
`ACKNOWLEDGEMENT
`
`HOP PROCESSING -- 50m
`
`ST. JUDE 1014
`
`1
`
`

`

`US. Patent
`
`June 16, 1992
`
`Sheet 1 of 5
`
`5,123,029
`
`JMOBILE STATION l0, l2, l4 0R I6
`
`W
`
`5/355
`/
`48
`
`l/
`
`(44
`
`TRANSCEIVER
`ADAPTERS
`
`TRANSCEIVER
`42
`
`40
`
`38
`
`3s
`TRANSCEWER /
`ADAPTERS
`
`F|G.|A
`
`/BASE smnou 26OR28
`
`4s
`/
`
`son
`"ARE
`
`___
`
`32
`
`// C3o
`LAN
`x /LAN ADAPTERS /
`lg/ 34
`’
`
`SERVER
`
`2
`
`

`

`US. Patent
`
`June 16, 1992
`
`Sheet 2 of 5
`
`5,123,029
`
`F|G.Z
`/50
`
`USER APPUCATIONS 12_
`
`OPERATING SYSTEM Q
`
`COMMUNICATIONS MANAGER
`
`/74
`
`DEVICE
`
`DRIVER
`
`/76
`
`MICROPROCESSOR SYSTEM
`62)
`60/ INTERFACE
`MlCRO~
`CONTROLLER
`64 T
`TmERS
`
`PROGRAM
`STORAGE
`
`66'- 68‘1
`DATA
`STORAGE
`
`BUS INTERFACE 52
`
`__/
`
`/56
`
`54
`
`T
`
`5B
`J RF
`TRANS._
`CEIVER
`
`'"TER-
`FACE
`
`/36 OR 44
`
`FIG}
`T;
`c
`x2
`B
`XI
`6
`|---l--| ---------------- —-|--l ------------------- --|.-.|
`
`“I H I F
`
`T'
`
`‘|~*
`
`e n
`
`BI
`
`F IG.3A
`x2
`
`82
`
`in i
`
`T2
`
`c
`
`3
`
`

`

`US. Patent
`
`June 16, 1992
`
`Sheet 3 of 5
`
`5,123,029
`
`( INITIALIZE )
`
`TALLY MESSAGES
`FOR Bl _ 82 AND T:
`
`COMPARE NO. / s4
`MESSAGES
`
`86
`CHECK NO. MESS. /
`IN
`AN .
`TR SOUEUE
`
`CHECK REPORTED /B8
`DELAYS FROM
`MOBILE STATIONS
`
`ANY
`ADJUSTMENT
`CRITERIA
`-
`MET
`
`FIG/4B
`
`H G . 4 A
`
`RESET TALLY
`92
`/ COUNTERS
`AND PERIOD
`TIMER
`
`94
`
`CHANGE
`a l
`
`no
`
`98
`
`CHANGE
`a2
`no
`
`I02
`
`ADJUST a1
`SUBINTERVAL
`
`Too\
`ADJUST a2
`SUBINTERVAL
`
`YES
`
`l04\
`ADJUST c
`lNTERVAL
`
`4
`
`

`

`US. Patent
`
`June 16, 1992
`
`Sheet 4 of 5
`
`PHASE BI
`
`FIGSA
`
`( INITIALIZE )
`
`SET PHASE TO BI
`SET TIMER FOR BI
`DURATION
`BROADCAST XI
`
`TRANSMIT FROM
`
`PHASE B2
`
`SET PHASE TO B2
`SET TIMER FOR B2
`DURATION
`r—————4
`RECEIVE FROM
`RECEIVE gUEUE
`TRANS IT
`ACKNOWLEDGEMENT
`
`RECEIVE FROM
`RECEIVE OUEUE
`TRANSMIT
`ACKNOWLEDGEMENT
`
`PROCESSING
`
`_ 60 TO PHASE an
`
`5
`
`

`

`US. Patent
`
`June 16, 1992
`
`Sheet 5 of s
`
`I
`
`5,123,029
`
`FIG-6A
`
`PHASE Bl
`
`Q)
`
`1144
`TRANSMIT FROM
`TRANSMIT OUEUE
`RECEIVE
`ACKNOW LEOGEMENT
`
`( INITIALIZE )
`
`/"30
`
`WAIT FOR
`XI MESSAGE
`J
`SET PHASE TOBI /'32
`SET mm TO Bl
`DURATION
`
`/'34
`
`RECEIVE mom
`RECEIVE OUEUE
`TRANSMIT
`
`ACKNOWLEDGEMENT
`
`SET PHASE T0 B2 /|3a
`SET mm T0 82
`ounnnou
`I40
`'
`SET SLOT TIMER T0 /
`BEGINNING OF
`ALLOCATED SLOT
`
`SET PHASE TOC
`SET TIMER TO C DURATION
`SET SLOTTIMER TO RANDOM
`MULTIPLE OF SLOT WIDTH
`
`SLOT
`TIMER
`EXPIRED
`YES
`TRANSMIT FROM
`TRAN3EMCIETWOEUEUE
`ACKNOWLEDGEMENT
`
`A54
`
`'55
`
`PHASE
`mm
`EXPIRED
`
`H558
`
`Isa
`YES /
`HOP PROCESSING "" PHggE BI
`
`:50
`
`6
`
`

`

`1
`
`BROADCAST-INITIATED BIPARTITE FRAME
`MULTI-ACCESS PROTOCOL
`
`5
`
`CROSS-REFERENCE TO RELATED
`APPLICATION
`The invention disclosed in this application is related
`in subject matter to that disclose Patent Application
`Ser. No. 07/605,285 ?led Oct. 29, 1990, by Kadathur S
`Natarajan for “Methods for Polling Mobile Users in a
`Multiple Cell Wireless Network" and assigned to a
`common assignee The disclosure of Application Ser.
`No. 07/605,285 is incorporated herein by reference.
`
`5,123,029
`2
`latency for channel access. best satis?ed by periodic
`guaranteed access to the channel.
`Ef?cient radio channel usage is the basic requirement
`for a practical indoor radio data network. The different
`types of traf?c from various data terminals are usually
`bursty in nature and not predictable. Random access
`schemes are known for their short response time when
`channel load is light. When channel load increases,
`random access schemes become inef?cient and may be
`unstable. On the other hand, controlled access schemes,
`such as polling, achieve much better channel use ef?
`ciency when loads are heavy. However, polling
`schemes suffer from overhead as the polling cycle has
`to be reduced to meet response time requirements.
`A protocol for indoor digital data radio systems
`therefore should have the following characteristics:
`1) short access time if the channel is lightly loaded,
`2) good channel utilization if the channel is heavily
`loaded,
`3) unconditionally stable,
`4) simple to implement, and
`5) matched well to typical traf?c patterns, where
`most traf?c is outbound from a base station attached to
`a LAN to the mobile stations.
`One form of indoor data radio uses a transmission
`technique known as “spread spectrum“, authorized by
`the US Federal Communications Commission (FCC)
`in its regulations. part 15.247, for use in certain fre
`quency bands without user license. Spread spectrum
`communications offer several advantages including low
`density power spectra and interference rejection. There
`are several types of spread spectrum systems including
`direct sequence digital systems, frequency hopping sys
`tems, time hopping systems, pulsed frequency modu
`lated (or chirp) systems, and various hybrids. Ofthese,
`the direct sequence digital systems and the frequency
`hopping systems are perhaps the more widely imple
`mented. In a direct sequence digital system, a fast pseu~
`dorandom code generator is used to modulate slower
`digital data which. in turn, modulates a carrier. In a
`frequency hopping system, a coherent local oscillator is
`made to jump from one frequency to another under the
`in?uence of a pseudorandom code generator.
`The subject invention may be implemented using
`either direct sequence digital or frequency hopping
`types of spread spectrum communications systems. A
`description of these and other types of spread spectrum
`communications systems may be found, for example, in
`Spread Spectrum Systems, 2nd Ed., by Robert C. Dixon,
`John Wiley & Sons (1984), and Spread Spectrum Com
`munications, Vol. II. by M. K. Simon et al., Computer
`Science Press (1985).
`
`40
`
`BACKGROUND OF THE INVENTION
`1. Field of the Invention
`The present invention generally relates to indoor
`digital data radio communication between a plurality of
`stations for the purpose of communicating among the
`stations and accessing various resources attached to the
`stations In the speci?cally disclosed environment, a
`plurality of mobile stations communicate with one or
`more ?xed base stations attached to a computer system,
`such as a local area network. More particularly, the
`invention relates to a system in which the base station
`exercises control over access to the radio channel by
`periodically broadcasting messages that demarcate
`?xed intervals of time, called “frames". Furthermore,
`such messages subdivide frames in a variable manner so
`30
`as to allow ?exible allocation of time to three modes of
`use of the channel: base station-to-remote transmission,
`?xed time-slotted allocation of time to various remote
`stations. and an interval in which remote station may
`access the channel using various contention mecha
`nisms.
`2. Description of the Prior Art
`It is very often the case that indoor data radio systems
`are installed for the purpose of permitting communica
`tions between mobile stations and applications and data
`residing in the computer system ofa business enterprise.
`For example, the business enterprise may include a
`warehouse storing a diverse inventory. Mobile stations
`in the form of hand held computers and radio transceiv
`ers having bar code readers are used to check the quan
`tities of inventoried products. and the data thus col
`lected is transmitted to a base station for input to the
`computer system.
`A typical structure has mobile stations communicat
`ing to a ?xed station acting as a gateway or bridge
`between the radio environment and a conventional
`local area network (LAN). The ?xed station relays
`messages to other LAN-attached resources. Communi
`cations are rarely directly between mobile stations;
`rather, messages are exchanged with applications resid
`ing in ?xed nodes. In this structure, it is natural to add
`55
`certain radio system management functions to those of
`the gateway, including coordination of the mobile sta
`tions. access to the common radio channel. This aug
`mented gateway is referred to herein as a base station.
`In indoor digital data radio systems, a key problem is
`providing ef?cient access to the channel, as that chan
`nel is limited in capacity and shared by all its users.
`Static channel allocation means, such as frequency divi
`sion multiplex (FDM) or ?xed time division multiplex
`(T DM), are inef?cient for many forms of computer-to
`computer traf?c, known to be bursty in nature, while
`other services (e.g., speech transmission, control appli
`cations, etc.) require a ?xed upper bound on maximum
`
`60
`
`65
`
`SUMMARY OF THE INVENTION
`It is therefore an object of the present invention to
`provide a protocol for channel access in a digital data
`radio system which reduces response time when traffic
`load is light and increases channel use ef?ciency when
`traffic load is intense.
`Other objectives of the invention include the support
`of traf?c with latency constraints, the ability to con?g
`ure a system in different applications with different
`characteristics, and the ability to guarantee “fairness"
`under heavy load.
`According to the invention, there is provided a hy
`brid of controlled access and random access schemes
`using spread spectrum communication techniques.
`
`7
`
`

`

`3
`More speci?cally, a frame is subdivided into two inter
`vals so that different media-access protocols can be used
`in each interval. While in principle any protocol could
`be used in the two intervals, a preferred embodiment of
`the protocol uses a centralized control scheme in one
`internal and a decentralized scheme in the other. The
`relative duration of the intervals may be varied to ac
`commodate varying load Conditions.
`A preferred embodiment of the invention is imple
`mented using a frequency hopping spread spectrum
`communication system. In the frequency hopping
`spread spectrum system, the carrier frequency of the
`transmitter changes at intervals of time, remaining con
`stant between those instants. The period of constant
`frequency is called a "hop", and it is only during these
`hops that messages may be exchanged. Because the
`hops are of finite duration, they impose a structure on
`the use ofthe radio channel; that is, no transmission may
`occur across a hop boundary. Hops therefore impose a
`framing structure on time.
`The invention provides “transparent connectivity“
`between client and server programs, in that neither
`program need be aware of the presence of the wireless
`link. The “con?guration" objective of the invention is
`accomplished by setting the boundary between inter
`vals at system configuration time. Thus. in a multiple
`dumb-terminal application. the base station could be set
`to poll only. while in a portable PC (personal computer)
`application. the base station could be set to only allow
`contention access. The “fairness“ objective of the in
`vention is achieved by shifting from contention to pol
`ling or allocation as the load increases. thus guarantee
`ing that no remote station ever gets "locked out“ even
`though a particular remote station might be a weaker
`contender than others.
`
`5
`
`35
`
`30
`
`5,123,029
`4
`Referring now to the drawings. and more particu
`larly to FIG. 1, there is shown an indoor radio system
`allowing communication between a plurality of mobile
`stations 10, 12. 14. and 16 and applications and data
`residing in a computing system. The computing system
`typically includes a server 18. with attached monitor 20
`and keyboard 22. ofa local area network (LAN), gener
`ally indicated by reference numeral 24. having a plural
`ity of attached workstations or personal computers (not
`shown for simplicity). Also attached to the LAN are
`one or more gateways 26 and 28 with which the mobile
`stations 10. 12, 14, and 16 communicate. These gate
`ways, referred to as base stations. are augmented ac
`cording to the invention to provide certain radio system
`management functions which coordinate the mobile
`stations‘ access to the common radio channel. Commu
`nications between mobile stations is supported via relay
`through the base stations 26 and 28.
`As shown in more detail in FIG. 1A, a base station 26
`or 28, which may be a conventional microcomputer, has
`a LAN adapter 30 inserted in a bus slot and connected
`to LAN cabling 32. The server 18, typically also a con—
`ventional microcomputer and including one or more
`direct access storage devices (DASDs) such as hard
`disks (not shown), also has a LAN adapter 34 inserted in
`a bus slot and connected to LAN cabling 32. The LAN
`adapters 30 and 34 and the LAN cabling 32 together
`with LAN software constitute the LAN 24. The LAN
`24 is of conventional design and does not form part of
`the invention. The base station 26 or 28 also has an RF
`transceiver adapter 36 implemented as a printed circuit
`card which is inserted in a bus slot of the base station.
`The transceiver adapter 36 includes a spread spectrum
`transceiver of conventional design. The transceiver
`adapter 36 has an antenna 38 by which a radio link 40 is
`established with one or more remote or mobile stations,
`10. 12. 14. or 16. The mobile station may itselfbe a hand
`held or lap top computer of conventional design and,
`like the base station, it is provided with an antenna 42
`and a transceiver adapter 44, also implemented as a
`printed circuit card which is inserted in a bus slot of the
`computer. The transceiver adapter 44, like transceiver
`adapter 36, includes a spread spectrum transceiver of
`similar design. The base station and the mobile stations
`are further provided with software. generally indicated
`by reference numerals 46 and 48, respectively, which
`support their respective transceiver adapters.
`FIG. 2 shows the radio system common to both the
`mobile stations and the base stations of FIG. 1. The
`radio system includes a transceiver adapter 36 or 44
`connected to the computer 50 via the computer’s bus
`interface 52. The transceiver section is itself divided
`into an RF transceiver 54, which may be a commer
`cially available spread spectrum transceiver, and a dedi
`cated microprocessor system 56 which controls the
`transceiver via an interface 58. The microprocessor
`system 56 further includes a system interface 60 which
`interfaces the transceiver section to the computer sec
`tion 50. The microprocessor system includes a dedi
`cated microprocessor 62 containing high-resolution
`time interval determination hardware or “timers” typi
`cal of real-time microprocessor systems.
`Microprocessor 62 is connected by a memory bus 64
`to program storage 66 and data storage 68 as well as to
`interfaces 58 and 60 providing attachment to bus inter
`face 52 and RF transceiver 54, respectively. Program
`storage 66 is typically read only memory (ROM), while
`data storage 68 is static or dynamic random access
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`The foregoing and other objects, aspects and advan
`tages will be better understood from the following de
`tailed description of a preferred embodiment of the
`invention with reference to the drawings, in which:
`FIG. 1 is a pictorial diagram showing an indoor radio
`digital data communication system of the type in which
`the invention is implemented;
`FIG. 1A is a block diagram of the system shown in
`FIG. 1 illustrating the basic components of a mobile
`station and a base station;
`FIG. 2 is a block diagram ofthe radio system used in
`the implementation of a preferred embodiment of the
`invention;
`FIG. 3 is a data framing diagram showing the proto
`col implemented by the preferred embodiment of the
`invention;
`FIG. 3A is a data framing diagram showing a modifi
`cation of the basic protocol illustrated in FIG. 3;
`FIGS. 4A and 4B, taken together, are a ?ow diagram
`of the logic of the process by which the base station
`adjusts intervals as a function of traffic load and other
`factors;
`FIGS. 5A and 5B, taken together, are a flow diagram
`of the logic of the protocol processing by a base station;
`and
`FIGS. 6A and 6B, taken together, are a flow diagram
`of the logic of the protocol processing by a mobile
`station.
`
`DETAILED DESCRIPTION OF A PREFERRED
`EMBODIMENT OF THE INVENTION
`
`60
`
`65
`
`8
`
`

`

`5
`
`35
`
`40
`
`5
`memory (SRAM or DRAM). Packets received or to be
`sent are held in data storage 68 and communicated to or
`from the RF transceiver 54 via interface 58 under con
`trol of serial channels and a direct memory access
`(DMA) controller (not shown) which is part of the
`microprocessor 62. The function of these serial channels
`is to encapsulate data and control information in an
`HDLC (high-level data link control) packet structure
`and provide the packet in serial form to the RF trans
`ceiver 54. For more information on the HDLC packet
`structure, see, for example, Mischa Schwartz, Telecom
`munication Networks.‘ Protocols, Modeling and Analysis,
`Addison-Wesley (1988).
`When a packet is received through the RF trans
`ceiver 54, the serial channels check the packet destina
`tion address, check for errors, and deserialize the packet
`to data storage 68. The serial channels must have the
`capability to recognize a speci?c adaptor address as
`well as a broadcast address. Speci?c microprocessors
`with appropriate serial channel and timer facilities in
`clude the Motorola 68302 and the National HPC464OOE
`microprocessors.
`The computer 50 runs an operating system 70 which
`supports one or more user application programs 72. The
`operating system 70 may include a communications
`manager 74, or the communications manager 74 may
`itself be an application program installed on the com
`puter. In either case, the communications manager 74
`controls a device driver 76 via the operating system 70.
`The device driver 76. in turn, communicates with the
`transceiver adapter 36 or 44 via bus interface 52.
`FIG. 3 shows the protocol implemented by the inven
`tion. While the protocol is equally applicable to radio
`frequency (RF), infrared (IR), or wired transmission
`systems with broadcast capability. and to either conven
`tional or spread-spectrum modulation techniques, slow
`frequency-hopped spread spectrum radio systems have
`a natural affinity for the protocol since those systems
`share a structure to time with the protocol. However,
`the invention has been implemented using direct se
`quence spread spectrum systems which may be readily
`adapted to the protocol.
`With reference to FIG. 3, there are five intervals
`de?ning a “hop". The ?rst (and last) interval, G, is the
`interval during which the transmitter carrier frequency
`is changing. Note that the G interval is needed only for
`frequency hopping systems. This interval has a duration
`H. The next interval, X1, is the interval during which
`the base station broadcasts a special message to all the
`mobile stations identifying the beginning of the follow
`ing, or B, interval. The B interval is the interval during
`which, by convention, only the base station may initiate
`transmission and mobile stations may respond only
`when required by the message protocol. For example,
`the mobile station may acknowledge a message out
`bound from the base or may respond when polled. The
`B interval has a duration T1. The B interval is followed,
`in turn, by the X2 interval which is the interval during
`which the base station broadcasts a special message to
`all the mobile stations identifying the end of the B inter
`val and, by implication, the beginning of the C interval.
`The message also conveys the length of the C interval
`and, optionally, the length of the B interval as well.
`The X; broadcast message is not strictly necessary.
`Information about the entire hop structure can be con
`veyed in the X1 interval. The X; message is included to
`support operation of simplified remote stations capable
`
`5,123,029
`6
`of only contention-mode operation. These stations wait
`for the X2 message and contend subsequently.
`The C interval is the interval during which any sta
`tion, including (or optionally excluding) the base sta
`tion. may contend for the channel and transmit a mes
`sage without the consent of the base station. For exam
`ple. a CSMA/CA (carrier sense multiple access with
`collision avoidance) protocol may be used in this inter
`val. The C interval is approximately of duration T2.
`If a mobile station sends a message and receives an
`acknowledgement, it can assume the message has been
`received correctly. If not, it will contend again. There is
`a guard interval at the end of the C interval during
`which a mobile station with a particular message may
`not transmit. If Tm;g is the time to transmit a particular
`message and Tad,- is the time to transmit an acknowl
`edgement and Tnmamundis the time between the end of
`a transmission of a message and the initiation of the
`transmission of an acknowledgement, then the guard
`interval is Tm5g+Ta(k+Tmrnamund. Note that because
`Tmsg is a function of the length of the message to be
`transmitted, the guard interval may be different for
`different mobile stations having a message to send. The
`guard interval is not wasted; rather, messages and ac
`knowledgements are sent and received right up to the
`end of the C interval.
`By varying the time T2, the base station can expand
`or contract the contention interval. If the system is very
`lightly loaded and most of the traffic is inbound to the
`base station, it is advantageous to mobile response time
`to lengthen the time period T1. Conversely, if the sys
`tem is heavily loaded and most of the traffic is out
`bound, the time period T; should be minimized. The
`time period T; should not be reduced to zero, however,
`as it is the only mechanism by which a newly activated
`mobile station can register itself to the base station.
`Additionally, a further subdivision of the B interval,
`in which remote-to‘base traffic is carried in allocated
`time slots, may be made as shown in FIG. 3A. In FIG.
`3A, the B interval is subdivided into B1 and B2 subinter
`vals, and the B1 subinterval is, in turn, subdivided into a
`plurality of time slots, each time slot being allocated to
`a specific remote station. Requests for an allocated slot
`may be made by a remote station in response to a poll
`during the B1 subinterval, or the requests may be made
`during the C interval. Once con?rmed by a message
`from the base station, slot allocation guarantees that the
`remote station can transmit to the base station during its
`allocated time slot.
`By varying the boundary between the B2 subinterval
`and the C interval, the suitability of the system to differ
`ent types of traffic can be adjusted. As the traffic load
`for steady, predictable traffic (e.g., real-time audio and
`video) increases, the boundary can be moved to
`lengthen the B2 subinterval and shorten the C interval,
`thereby increasing the number of allocatable time slots.
`Conversely, as the traffic becomes less predictable, the
`boundary can be moved to lengthen the C interval,
`providing greater bandwidth for contention-based traf
`?c.
`From FIG. 3, it will be appreciated that the “hop" is
`divided into to two subdivisions, one of which supports
`a controlled access scheme and the other of which sup
`ports a random access scheme. The invention may oper
`ate in any one of three modes: one in which only the X1
`message is sent, one in which only the X2 message is
`sent, and one in which both are sent.
`
`45
`
`50
`
`55
`
`65
`
`9
`
`

`

`7
`In the case where only the X1 message is sent. the X1
`message constitutes the header section of a frame. It
`identi?es the start of the information frame, carries a
`unique identi?cation of the base station. identi?es the
`frequency hopping pattern. and de?nes the length ofthe
`B and C intervals. Optionally the X1 message also
`carries general broadcasting and system control infor
`mation.
`In operation, each mobile station waits for the X1
`message. When received, a mobile station sets an inter
`nal timer for T1 and for Ti+T1 so that it knows when
`the contention interval begins and when to schedule its
`next frequency change. Broadcast reception of mes
`sages is not guaranteed, only likely. Radio conditions
`may be such that a particular mobile station does not
`hear the broadcast message X1. Because a mobile station
`cannot transmit autonomously without ?rst hearing the
`X1 message and letting T1 elapse, it will remain quiet for
`the entire frame. Alternatively. if the mobile station is
`polled by the base station during interval B, it may
`respond, but in no case can it contend in the C interval.
`It must remember T1+T; from the last frame so that it
`knows when to hop, and it will listen in the next frame
`for the X1 message. If no Xi message is heard for a
`number of consecutive frames, the mobile station must
`assume that it has lost hop synchronization with the rest
`of the system and enter a synchronization acquisition
`mode.
`Each frame time period oflength T=T1+T3 can also
`be a frequency hopping period for implementation
`under FCC regulation part 15. A ?xed length oftime T
`is recommended but not necessary. A ?xed length of
`time T is especially useful in the following cases:
`I) When several frequency hopping patterns are used
`in overlapped operation in a multicell radio system. a
`?xed length of time T makes interference separation
`much more feasible. In this case, the frequency hopping
`pattern information in the header section can be used to
`identify the hopping sequence for a mobile terminal to
`follow.
`2) If all radios in a system are hopping with the same
`pattern. a ?xed length of time T permits different cells
`to hop in synchronism but at different phases of the
`hopping pattern. This eliminates interference between
`cells.
`A tradeoff needs to be made in selecting the length of
`time T. A large time T makes the system overhead
`smaller. and a small time T makes the system response
`time smaller.
`Instead ofthe Xi message, the system can transmit the
`X; message only. The content ofthe X1 message can be
`similar to that of the X1 message except that mobile
`stations receiving the X3 message can immediately
`begin contention. This may be an advantage in some
`applications.
`For the case of transmitting the X2 message only, '
`suppose the base station polls a mobile station near the
`end of the B interval, and the mobile station responds
`with a lengthy message. (Generally, the protocol must
`prohibit these responses from being too lengthy.) It may
`be that the response is active even as the period T]
`expires. With only Xi messages, this may be a problem,
`but with X; messages, the base station can then originate
`the X1 message as soon as the response is complete,
`making sure to include a shortened T3 period in the X3
`message. The effect will be to diminish the contention
`interval for one hop‘s duration.
`
`5,123,029
`8
`In the third mode of operation. both X1 and X3 mes
`sages can be used to simplify the implementation of the
`mobile station and to provide redundancy. The X; mes
`sage would then signal the beginning of the B interval,
`and the X3 massage. the C interval.
`In a speci?c implementation of the invention, the X1
`message only was used. An advantage of the X; mes
`sage over the X3 message is that the time of occurrence
`of the X1 message is known to .the mobile stations
`which, in order to save power, may power down their
`receivers until the time the X1 message is expected. This
`also reduces susceptibility to spurious reception of X
`type messages. The combination of X1 and X3 messages
`is the safest and simplest to implement at the mobile
`stations. X; messages only can provide some simplicity
`for contention-only mobiles.
`The dynamic adjustment of the relative durations of
`the B and C intervals depending on the load of the
`system is an important aspect of the subject invention.
`Since all messages involve the base station, the base
`station can recorded the relative traffic intensity (num
`ber of messages) in each of the B and C intervals. The
`recording is typically done by keeping running tallies of
`the number of messages in each interval over a prede
`termined time period. At the end of the time period, the
`base station evaluates the tallies accumulated for each
`interval and, based on this information and other related
`factors, makes a decision as to whether the length of
`each interval is to be varied.
`As a speci?c example, consider the modi?ed protocol
`shown in FIG. 3A. Ifthe number of messages from the
`base station to the mobile stations is large. the base
`station may choose to lengthen the B1 subinterval and
`correspondingly shorten the B1 subinterval and C inter
`valv Conversely, ifthe C interval is heavily utilized and
`the mobile stations have little demand for allocated
`slots, the C interval can be lengthened at the expense of
`the B; subinterval.
`Since the length of the B1 interval need only be suffi
`cient to exhaust the base station‘s transmit queue for a
`particular frame, the base station may dynamically vary
`the length of this subinterval for each frame. The base
`station must estimate the length of the B1 subinterval at
`the time the X1 message is broadcast. This estimate is
`based on the number and length of the messages in the
`transmit queue at the start of the frame.
`Other measures of traffic may also be taken into con
`sideration by the base station. For example, a decision to
`lengthen the B2 subinterval would most effectively be
`made on the basis of the number of outstanding slot
`allocation requests made by mobile stations. In addition,
`mobile stations may monitor the delay experienced in
`attempting to use the C interval (or the collisions they
`experience) and report this information to the base sta
`tion either in response to periodic requests from the base
`station for status or as a ?eld in the packet itself. Alter
`natively, the base station can determine the average
`transmit queue lengths for itself and all the active
`remotes. The queue lengths for the remote stations can
`be determined by periodic reporting or by including
`queue lengths in all packets transmitted to the base
`station.
`FIGS. 4A and 4B, taken together, are a ?ow diagram
`showing the logic of the adjustment of the proportions
`of the lengths of the B; and B3 subintervals and the C
`interval. Source code in an appropriate computer lan
`guage, such as C, Pascal or BASIC, supported by the
`base station computer can be written from the flow
`
`20
`
`45
`
`50
`
`55
`
`65
`
`10
`
`

`

`0
`
`20
`
`25
`
`9
`diagram by a computer programmer skilled in the par
`ticular computer language used.
`Referring now to FIG. 4A, the process begins by a
`routine process of system initialization during which
`tally counters for the B1 and B3 subintervals and the C
`interval are set to zero and a period counter is preset to
`a predetermined time period. Then, in function block
`80. the tally counters are advanced for messages during
`eac