liillll
`
`USO05610595A
`
`United States Patent
`
`[19]
`
`[11]
`
`Patent Number:
`
`5,610,595
`
`Garrabrant et al.
`
`[45] Date of Patent:
`
`Mar. 11, 1997
`
`[541
`
`[751
`
`[73]
`
`[9-1]
`
`[22]
`
`[63]
`
`[51]
`[52]
`
`[58]
`
`[56]
`
`PACKET RADIO COMMUNICATION
`SYSTEM PROTOCOL
`
`OTHER PUBLICATIONS
`
`Inventors: Gary W. Garrabrant, Bellevue; Jay C.
`Cho, Seattle; Joseph T. Savarese,
`Snohomish County, all of Wash.
`
`Assignees
`
`Intermec Corporation, Everett, Wash.
`
`App]. No.: 404,111
`
`Filed:
`
`Mar. 14, 1995
`
`Related U.S. Application Data
`
`Continuation of Ser. No. 804,319, Dec. 9, 1991, abandoned.
`
`Int. Cl.6 ....................................................... H04Q 1/00
`U.S. Cl.
`.................................. 340/825.52; 340/825.5;
`370/394; 370/913; 371/33
`Field of Search ....................... .. 340/825.52, 825.53,
`340/825.5; 370/60, 61, 94.1; 371/32, 33,
`60
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`4,060,220
`4,284,976
`4,703,475
`5,151,899
`
`12/1977 Metcalfe ................................. .. 370/60
`8/1981 Gable ......
`340/825.53
`
`10/1987 Dretzka
`.... .. 370/60
`9/1992 Thomas ................................ .. 370/94.1
`
`Fox, Terry L., “AX.25 Amateur Packet—Radio Linl<—Layer
`Protocol," Version 2.0, American Radio Relay League, Inc.,
`Oct. 1984.
`International Organization for Standardization, International
`Standard 4335, “Data communication—High—level data
`link control procedures——Consolidation of elements of pro-
`cedures,” Second edition—-1984, Dec. 15.
`
`Primary Examiner—Brian Zimmerman
`Attorney, Agent, or Firm—Seed and Berry LLP
`
`[57]
`
`ABSTRACT
`
`A method and apparatus for transmitting data in a packet
`radio communication system having data sources, destina—
`tions and intermediate repeaters. According to a packet
`protocol, a repeat count in the protocol is decremented each
`time a packet is retransmitted, until the repeat count reaches
`zero, at which time the packet is discarded. According to
`another packet protocol, a sequence index is used to prevent
`duplicate packets from being received by requiring that the
`sequence number fall within a sequence number window at
`each device, which is incremented each time a packet is
`received. The sequence number is also used to cause the
`retransmission of packets which are lost, at which time the
`sequence number windows in the devices which are aifected
`are reset to allow transmission of the lost packet.
`
`13 Claims, 9 Drawing Sheets
`
`72
`
`75
`
`73
`
`92
`
`95
`
`so
`
`82
`
`34
`
`74
`
`DESTINATION
`
`SOURCE
`
`SEQUENCE N0.
`
`REPEAT COUNT
`
`CONTROL
`
`INFORMATION
`
`90}
`
`VALID
`
`/40
`
`/44
`
`
`
`REJECTION
`WINDOW
`
`/42
`
`BROADCOM 1 O O 2
`
`

`
`U.S. Patent
`
`Mar. 11, 1997
`
`Sheet 1 of 9
`
`5,610,595
`
`/////2W
`
`5?
`
`22
`
`HOST
`
`COMPUTER
`
`30
`
`24
`
`Fig. I
`(PRIOR ART)
`
`Fig. 2
`(PRIOR ART)
`
`

`
`
`
`111913cI'S'fl
`
`Z
`
`5 F
`
`E
`
`U)
`
`=3
`3..\O
`
`s6s‘0I9‘s
`
` F13.
`
`722
`
`6‘
`
`84
`32
`so
`73
`76‘
`72
`7 °E5T'"AT'°“7
`
`74
`
`70 /( F1g. 3 (PRIOR ART)
`
`_
`
`72
`
`76
`
`78
`
`92
`
`96
`
`80
`
`82
`
`84
`
`74
`
`
`
`/(90
`
`-
`Hg. 4
`
`

`
`U.S. Patent
`
`Mar. 11, 1997
`
`Sheet 3 of 9
`
`.
`
`5,610,595
`
`

`
`U.S. Patent
`
`Mar. 11,1997
`
`Sheet 4 of 9
`
`5,610,595
`
`PACKET 0 IS
`
`(~ NO LONGER VALID
`0 1 23 4
`
`750
`
`752
`
`13
`17161514
`
`Fzg.
`
`75’
`
`FIELD OF MUTUAL
`
`COVERAGE; LOCATION
`OF REMOTE DEVICE
`mA
`
`786
`
`

`
`U.S. Patent
`
`Mar. 11, 1997
`
`Sheet 5 of 9
`
`5,610,595
`
`/60
`
`I74
`
`Fzg. 86’
`
`

`
` EVENT ff
`
`
`RPT1
`REPT.
`
`SE0.
`
`CONT. WINDOW
`
`SE0.
`
`0
`
`SABM
`
`19
`
`20
`
`0
`
`0
`
`04
`
`RFNC
`REPT.
`
`1
`
`CONT. WINDOW
`
`O0—I5
`
`00-15
`
`04-19
`
`6J09rraausL661‘H‘mmmama‘S’[1
`
`s6s‘0I9‘s
`
`
`
`CONT. WINDOW
`
`REPT.
`
`PCKT ORGN
`
`

`
`U.S. Patent
`
`Mar. 11, 1997
`
`Sheet 7 of 9
`
`5,610,595
`
`5.B
`A DEVICE LOCATED SAME
`DISTANCE FROM BRU
`
`202
`
`AS REPEATERS.
`
` 792
`
`I96
`
`5.3
`
`LOCATION or DEVICE
`
`IN FIELD or MUTUAL
`
`REPEATER COVERAGE
`
`-
`
`F13 11
`
`Z36
`
`

`
`U.S. Patent
`
`Mar. 11, 1997
`
`Sheet 8 of 9
`
`5,610,595
`
`270
`
`2/2
`
`278
`
`Z34
`
`
`
`252
`
`
`
` IS A
`YES
`CARRIER
`PRESENT
`?
`
`
`
`
`2.30
`
`GENERATE
`RANDOM DELAY
`BETWEEN
`1 AND 7 m8
`
`274
`
`
`
`REPEAT COUNT
`=0?
`
`
`
`
`
`
`
`
`DETERMINE
`DESTINATION
`ADDRESS
`
`
`
`
`
` DESTINATION
`
`UPDATE FIFO
`LIST WITH
`
`AND SOURCE
`
`225
`
`
`
`N0
`
`ARE
`DESTINATION
`AND SOURCE ON
`*
`FIFO LIST
`9
`
`
`
`226
`
`Fig. 12
`
`

`
`U.S. Patent
`
`Mar. 11, 1997
`
`Sheet 9 of 9
`
`5,610,595
`
`240
`
`242
`
`
`
`
`
`DISCARD
`PACKET
`
`C
`
`DETERMINE
`"WINDOW" OF
`
`ACCEPTABLE
`
`SEQUENCE INDICES
`
`244
`
`
`
`250
`
`Fig. 14
`
`

`
`5,610,595
`
`1
`PACKET RADIO COMMUNICATION
`SYSTEM PROTOCOL
`
`CROSS-REFERENCE TO RELATED
`APPLICATION
`
`This application is a continuation of U.S. patent applica-
`tion Ser. No. 07/804,319, filed Dec. 9, 1991, now aban-
`doned.
`
`10
`
`TECHNICAL FIELD
`
`The present invention relates to communication systems,
`and more particularly to a method and apparatus for con-
`trolling a packet radio communication system.
`
`BACKGROUND OF THE INVENTION
`
`Radio communication systems which transmit informa-
`tion between locations have recently been used in bar
`code-based information systems. Information systems that
`are based on bar codes typically include a base computer
`which serves as a storage location for information and as a
`source of commands which control the other components of
`the system. These information systems also include bar code
`readers which are used to collect bar code-based information
`and other components which cause the information and
`commands to be communicated between the base computer
`and the bar code readers. Typical applications for bar code-
`based infonnation systems are in inventory management and
`retail sales.
`
`In many bar code-based information systems, it is advan-
`tageous for the bar code readers to be mobile. In the past, this
`has been accomplished by providing the bar code readers
`with local memory and powering the readers by batteries. In
`operation, a mobile bar code reader of this type are used to
`collect information from bar codes, store this information in
`its memory and then physically connect the bar code reader
`to a hard-wired communication system which reads the bar
`code reader’s memory and transmits the stored information
`to the base computer. This mode of operation is both
`time-consurning and inconvenient.
`It also prevents the
`immediate transmission of the information to the base
`computer.
`One solution of this problem is to connect the mobile bar
`code readers to the base computer through a radio link. A
`particularly advantageous type of radio link is provided by
`a spread spectrum communication system, which allows
`reliable communication of information in an electromag-
`netically noisy environment without high radio frequency
`(RF) power levels. A spreadspectrum communication sys-
`tem is highly resistant
`to interference from other such
`systems, and allows transmission into areas which are not
`along a line-of-sight. Spread spectrum communication sys-
`tems have been described by R. A. Scholtz in “The Origins
`of Spread Spectrum Communications,”
`IEEE Trans.
`Comm, vol . COM-30, May 1982, pp. 822-854. One very
`useful form of spread spectrum communication system is
`based on the asynchronous transmission of “packets” of
`information between a source and a destination. In a bar
`code information system, a bar code reader" and the base
`computer can serve as either a source or a destination. If
`two—way communications are necessary between a bar code
`reader and the base computer, each unit will be both a source
`and a destination.
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`2
`A packet radio communication system allows communi-
`cation between each bar code reader and the base computer
`essentially whenever such communication is needed. After a
`communication link has been established between the bar
`code reader and the base computer, the information to be
`communicated is broken into small portions. These rela-
`tively small portions of information are sent from the source
`to the destination in discrete messages. One advantage of
`breaking the information into discrete messages is that, if
`one of the discrete messages is not received correctly, the
`destination can request a retransmission of that message
`without having to request a retransmission of more.
`The form of the discrete messages is a string of digital
`information, called a “frame.” The information in the frame
`is arranged in a sequence of “fields.” The contents of each
`field in a frame is established by a protocol, such as those
`prescribed in packet radio standards X.25, AX.25 and ALO-
`HANET, for example. The X.25 standard is described in ISO
`document 4335—“Data Communication—-High level data
`link control procedures. Consolidation of elements of pro-
`cedures,” second edition 1984. ALOHANET is described by
`Norman Abrarnson, in “Development of the ALOHANET,”
`IEEE Trans. on Info. Theory, Vol. IT—3l, No. 2, March 1985.
`Low power communication systems such as spread spec-
`trum packet radio systems have only a limited range. Typi-
`cally transmitters with output powers of one Watt have a
`range no greater than 500 feet. Accordingly, it is possible for
`a mobile bar code reader to move beyond a range where the
`base computer and the mobile bar code reader can commu-
`nicate reliably. In situations where this occurs, it has been
`found that one or more repeaters can be placed between the
`bar code reader and the base computer. These repeaters
`receive the information transmitted by the source and
`retransmit the information to the destination. In situations
`where longer range packet radio communications are desir-
`able, one or more repeaters can form a transmission path
`between the source and destination. One example of such a
`situation is where a mobile bar code reader is used in a very
`large warehouse for inventory control purposes.
`If a packet radio communication system uses a repeater,
`it is possible for a message transmitted by the repeater to be
`received by both the source and the destination. It is there-
`fore necessary to provide some means for the packet to be
`identified. In the protocols mentioned above, packet identi-
`fication includes addresses for the source and destination.
`Therefore, it is possible for a source to ignore a message
`which is repeated back to the source by recognizing that it
`was the source for the repeated message.
`The addition ofrepeaters to a packet radio communication
`system introduces further complications. If more than one
`repeater can receive a message transmitted by a source, more
`than one repeater will repeat the message. If the destination
`is within range of the multiple repeaters, it must be capable
`of determining that it has received more than one copy of the
`same message and ignoring all but one copy. Further, it is
`possible for a message which has already been received by
`one repeater to receive that same message subsequently
`from another repeater. It is therefore advantageous to pro-
`vide a protocol which will reduce the unnecessary repetition
`of messages in a packet radio communication system.
`There is a finite possibility that messages can be lost in a
`packet radio communication system. Packet radio commu-
`nications generally provide for confirmation of receipt of
`messages. In many systems, if a message is received incor-
`rectly, the message is regarded as lost and retransmitted.
`This requires that the retransmitted message must be prop-
`
`

`
`5,610,595
`
`3
`erly identified. It is therefore desirable to provide a protocol
`which will allow a lost message to be identified and a
`corresponding retransmitted message to be correctly placed
`in proper sequence in the information transmitted between
`the source and destination.
`
`SUMMARY OF THE INVENTION
`
`the present invention is a method for
`In one aspect,
`controlling a packet communication system, the communi-
`cation system including a source station, a destination sta-
`tion and one or more repeater stations adapted to repeat
`messages from the source station to the destination station.
`The method comprises the steps, at the source station, of (a)
`composing a message, the message including: (1) an address
`code of the destination station, (2) an address code of the
`source station, and (3) a sequence index indicating the
`sequence in which the message was composed at the source
`station; (b) storing the sequence index; and transmitting the
`message.
`
`In another aspect, the present invention is a method for
`controlling a packet communication system including a
`source station and a destination station. Each station has a
`unique address code, and the packet communication system
`is adapted to transmit messages from the source station to
`the destination station. The method comprises the steps of:
`at the source station: (a) composing a message, the message
`including: (1) the address code of the destination station, (2)
`the address code of the source station, and (3) a repeat count
`representative of a desired number of times the message is
`to be repeated by the system, and (4) a sequence index
`indicating the sequence in which the message was composed
`at the source station; and transmitting the message.
`In a further aspect
`the invention is an apparatus for
`controlling a packet communication system including a
`source station, a destination station and one or more repeater
`stations adapted to repeat messages from the source station
`to the destination station. The apparatus comprises, at the
`source station: electronic circuitry composing a message, the
`message including: (1) an address code of the destination
`station, (2) an address code of the source station, and (3) a
`sequence index indicating the sequence in which the mes-
`sage was composed at the source station. The apparatus
`further includes a memory storing the sequence index; and
`a transmitter transmitting the message.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`FIG. 1 is a schematic diagram of a radio communication
`system known in the prior art;
`FIG. 2 is a schematic diagram of a packet radio transmit-
`ter/receiver unit known in the prior art;
`FIG. 3 is diagram of the format of a frame defined in a
`protocol known in the prior art;
`FIG. 4 is diagram of the format of a frame defined
`according to the protocol of the present invention;
`FIG. 5 is a schematic diagram of the transmission of a
`message from a source to a destination through two repeat-
`ers having overlapping antenna coverage patterns;
`FIG. 6 is a schematic diagram of a configuration of
`source, destination and repeaters which may produce dupli-
`cate messages;
`FIG. 7A is a schematic diagram of a rejection window at
`a unit of the packet radio communication system of the
`present invention according to the protocol of the present
`invention, before the transmission of a message;
`
`10
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`4
`FIG. 7B is a schematic diagram of the rejection window
`of FIG. 7A after the transmission of a message;
`FIG. 8A is a schematic diagram of the rejection window
`of FIG. 7A before the rejection window is updated in
`response to the receipt of a “lost” message;
`FIG. 8B is a schematic diagram of a rejection window of
`FIG. 7A after the rejection window is updated in response to
`the receipt of a “lost” message;
`FIG. 9 is a schematic diagram of a configuration of a base
`and a repeater unit, showing the field of mutual coverage;
`FIG. 10 is a table of the transmitted frames and sequence
`and repeat counts of the three units shown in FIG. 9;
`FIG. 11 is a schematic diagram of a configuration of a
`base, two sources and two repeater units, illustrating the
`location of one source which results in mutual repeater
`coverage, and the location of a second source which is
`located the same distance from the destination as the repeat-
`ers;
`
`FIG. 12 is a flow chart of an algorithm which may be used
`to discard repeated packets;
`FIG. 13 is a schematic block diagram of a packet radio
`transrnitter/receiver; and
`FIG. 14 is a flow chart of an algorithm which may be used
`to discard lost packets.
`
`DETAILED DESCRIPTION OF THE
`INVENTION
`
`A schematic diagram of a radio communication system
`known in the prior art
`is shown in FIG. 1. The radio
`communication system 20 includes a host (or base) com-
`puter 22 which communicates with a base radio unit (BRU)
`24 through a link 26. Typically the link 26 is an electrical
`cable. The BRU 24 includes an antenna 28 for transmitting
`and receiving radio frequency (RF) electromagnetic signals.
`The radio communication system 20 also includes a remote
`unit 30, such as a mobile bar code reader, which is separated
`from the BRU 24. The remote unit 30 includes an antenna
`32, which is also for transmitting and receiving radio fre-
`quency (RF) signals. The BRU 24 and the remote unit 30
`include conventional electronic circuitry which permits
`them to communicate through the means of transmitted RF
`energy.
`
`A schematic block diagram of a packet radio transmitterl
`receiver unit 40 known in the prior art is shown in FIG. 2.
`The packet radio transmitter/receiver unit 40 (which could
`be either the BRU 24 or the remote unit 30 shown in FIG.
`1) includes an antenna 42 (corresponding to the antennas 28
`or 32 in FIG. 1) for transmitting and receiving RF energy.
`The antenna 42 is connected to a transmit/receive (TR)
`switch 44 which is operated according to control signals
`produced in a microprocessor 46 and transmitted to the TR
`switch 44 through a line 48. The TR switch 48 is placed in
`a receive mode if the transmitter/receiver unit 40 is trans-
`mitting receive RF energy through the antenna 42. The TR
`switch 44 is placed in a transmit mode if the transmitter/
`receiver unit 40 is expecting to transmit RF energy through
`the antenna 42. One form of the packet radio transmitterl
`receiver unit 40 is a 121 kb/s spread spectrum Proxim
`RXA—l00O.
`When it is desired that the transmitter/receiver unit 40 be
`prepared to receive messages, the TR switch 44 is placed in
`the receive mode with any RF energy it receives being
`transmitted to an RF modulator/demodulator (modem) 50
`through a bidirectional line 52. The modem 50 is controlled
`
`

`
`5,610,595
`
`5
`by the microprocessor 46 through a control line 54. In the
`receive mode, the modem 50 demodulates the RF energy
`received by the antenna 42 to produce a digital signal which
`is sent to the microprocessor 46 through a bidirectional bus
`56.
`When it is desired that the transmitter/receiver unit 40
`transmit one or more messages, the TR switch 44 is placed
`in the transmit mode. The microprocessor 46 determines the
`digital message to be sent and transmits the message to the
`modem 50 over the bidirectional bus 56. Upon receipt of an
`appropriate control signal over the control line 54 from the
`microprocessor 46, the modem 50 modulates an RF canier.
`The modulated RF carrier is transmitted through the TR
`switch 44 to the antenna 42.
`
`If the radio communication system is a spread spectrum
`system, modulation and demodulation of RF signals is
`generally chosen to be of one of two forms: direct sequence
`spread spectrum and frequency hopping spread spectrum.
`These two forms are described in “Spread Spectrum for
`Personal Communications,” Microwave Journal, September
`1991 and other standard reference texts cited therein. Further
`details are presented in the 1990 ARRL Handbook (espe-
`cially Chapter 19), published by American Radio Relay
`League, Newington, Conn., which is hereby incorporated by
`reference.
`
`The microprocessor 46 is programmed according to a
`program which is stored in aread-only memory (ROM) 60.
`The program stored in the ROM 60 is transmitted from the
`ROM 60 to a random-access memory (RAM) 62 through a
`data line 64 and a bidirectional data line 66. The conven-
`
`tional program in the RAM 62 causes the microprocessor 46
`to issue control signals, interpret digital messages received
`through the antenna 42 and prepare digital messages for
`transmission through the antenna 42.
`The program under which the microprocessor 46 operates
`is dependent upon the protocol under which the communi-
`cation system 20 (see FIG. 1) operates. The protocol (for
`example, AX.25, described in “AX.2S Amateur Packet-
`Radio Link-Layer Protocol,” published by the American
`Radio Relay League, Inc., Newington, Conn., which is
`incorporated herein by reference) assigns an address to
`every transrnitter/receiver unit in the communication sys-
`tem. It also defines controls, which are used to control the
`flow of information in the communication system.
`A diagram of the format of a frame 70 defined in a
`protocol known in the prior art is shown in FIG. 3. The frame
`70 includes binary information organized into several fields.
`These include flag fields 72 and 74, destination and source
`address fields 76 and 78, a control field 80, an information
`field 82, and a cyclic redundancy check (CRC) field 84. The
`flag fields 72 and 74, respectively, define the beginning and
`end of the frame 70 by a characteristic 8-bit binary sequence
`(“0ll1lll0”) which cannot appear elsewhere within the
`frame 70. The destination and source address fields 76 and
`78 are each one byte in length and respectively include the
`addresses of the destination and the source of a message. The
`control field 80 is also one byte in length and includes a
`binary number that corresponds to a control function asso-
`ciated with the frame. The control function can be either a
`command or a response. The information field 82 can have
`as many as 256 bytes of binary information. The CRC field
`84 is a 16-bit number that is calculated based on the binary
`data in the other portions of the frame 70, according to a
`cyclic redundancy check algorithm published by the ISO, in
`document ISO 3309 (which defines the high level data link
`control procedures, HDLC). When the frame 70 is received
`
`20
`
`25
`
`30
`
`35
`
`45
`
`50
`
`SS
`
`60
`
`65
`
`6
`at the destination, the algorithm is again performed on the
`data in the frame and the resulting number compared with
`that transmitted with the packet. If they are the same, it is
`assumed that the data in the frame are correct.
`
`There are several commands and responses which may
`appear in the control field 80. The commands are shown in
`the following table:
`
`Command
`SABM
`
`DISC
`STTM
`TEST
`UI
`I
`RR
`RNR
`XID
`
`-
`
`Purpose
`Establish Link
`Connection
`Remove Link Connection
`Topology Test
`Diagnostics
`Group Broadcast
`Exchange Information
`Flow
`Control
`Channel Searching
`
`' The responses are shown in the following table:
`
`Response
`
`Purpose
`
`UA
`DM
`TEST
`I
`RR
`RNR
`UI
`XID
`
`Acknowledge Commands
`Indicate Disconnected
`Return Diagnostics
`Exchange Information
`Flow
`Control
`Group Broadcast
`Channel Searching
`
`The corresponding commands and responses are given in
`the following table:
`
`Command
`SABM
`DISC
`STTM
`TEST
`UI
`I
`RR
`RNR
`XID
`
`Response
`UA
`DM
`TEST
`
`I
`R
`RNR
`XID
`
`In the present invention, the commands supported are:
`SABM, DISC, TEST, 1, RR and XID, while the responses
`suggested are UM, DM, TEST, 1, RR and XID.
`A diagram of the format of a frame 90 defined according
`to the protocol of the present invention is shown in FIG. 4.
`This protocol is a custom protocol having features from two
`similar protocols: the AX.25 Amateur Packet Radio Link
`Layer protocol and the HDLC protocol. Most of the fields of
`the frame 90 according to the protocol of the present
`invention are identical to those known in the prior art. They
`are given the same reference numbers as used for the
`corresponding features in FIG. 3. The two new fields in the
`frame 90 are the 5-bit sequence number field 92 and the 3-bit
`repeat count field 96. The sequence number field 92 records
`the sequence in which the source of the message represented
`by the frame 92 is originally produced. The sequence
`number (or count, or index) is used to prevent duplicate
`packets. The repeat count field 96 represents the number of
`remaining times which the message represented by the
`frame 94 will be repeated before being discarded. It is used
`to prevent packets from being repeated between one or more
`
`

`
`5,610,595
`
`7
`repeaters forever. This feature will be further explained
`below.
`
`The units of the packet radio communication system of
`the present
`invention can attain two additional
`states,
`beyond those known in the above-referenced protocols: the
`Fail state and the Search state. The Fail state supports
`sequence numbers. The sequence numbering scheme is
`similar to that used in ARPANET to support broadcast
`messages. It is necessary to eliminate multiple packet arrival
`which becomes possible with repeaters. The Fail state resyn-
`chronizes the sequence numbers in the case of lost synchro-
`nization. In this state,
`increasing retransmission timeout
`intervals also prevents one device in the communication
`system from swamping the network with packets by elimi-
`nating or controlling a hidden terminal problem.
`The Search state supports the ability of a radio frequency
`network controller (RFNC) to move between different fre-
`quencies. This is accomplished by broadcasting an XID
`(exchange ID) command.
`In response,
`the RFNC will
`respond to the device sending the XID command, informing
`the device of the correct frequency and address to use. After
`this is accomplished, the device next enters the Fail state to
`resynchronize sequence numbers.
`A schematic diagram of the transmission of a message
`from a mobile source 100 to a destination BRU 112 through
`first and second repeaters 104 and 108 having overlapping
`antenna coverage patterns is shown in FIG. 5. According to
`the present protocol, as many as six repeaters (giving seven
`hops) are allowed. The source 100 transmits a message with
`an antenna pattern schematically represented by the antenna
`coverage circle 102. It will be understood that the actual
`antenna coverage pattern is a complex function of the terrain
`and antenna placement, among other variables.
`In the
`present preferred embodiment, the radio network is accessed
`using a pure ALOHA standard, according to which devices
`simply transmit whenever they have something to send. If an
`acknowledgment is not received back, they retransmit, up to
`a predetermined number, until the transmission is acknowl-
`edged. The first repeater 104 is located within the antenna
`coverage circle 102 of the mobile source 100. Therefore, the
`first repeater 104 receives signals transmitted by the mobile
`source 100. The first repeater 104 transmits signals accord-
`ing to the antenna pattern schematically represented by the
`antenna coverage circle 106. The second repeater 108 is
`located within the antenna coverage circle 106. Therefore,
`the second repeater 108 receives signals transmitted by the
`first repeater 104. The second repeater 108 transmits signals
`according to the antenna pattern schematically represented
`by the antenna coverage circle 110. The BRU 112 is located
`within the antenna coverage circle 110. Therefore, the BRU
`112 receives signals transmitted by the second repeater 108.
`The antenna coverage circle 102 of the mobile source
`does not extend to the second repeater 108. Therefore, there
`is only a small probability that the second repeater 108 can
`receive signals directly from the mobile source 100 when at
`the positions shown in FIG. 5. Likewise, the antenna cov-
`erage circle 106 of the first repeater 104 does not extend to
`the BRU 112. Therefore, there is only a small probability
`that the BRU 112 can receive signals directly from the first
`repeater 104. Accordingly, signals that are transmitted from
`the source 100 to the BRU 112 are, with a high probability,
`sequentially relayed through the first and second repeaters
`104 and 108, respectively. This represents a straightforward
`situation where the route of a message from a source (the
`source 100) to a destination (the BRU 112) is easily ana-
`lyzed. Those skilled in the art will recognize that FIG. 5 also
`implies that transmissions from the BRU 112 to the source
`
`10
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`8
`100 will be relayed back .through the first and second
`repeaters 104 and 108. It should be noted that the repeaters
`104 and 108 can be stationary, or themselves mobile.
`A schematic diagram of a configuration of sources, des-
`tination and repeaters which may produce duplicate mes-
`sages is shown in FIG. 6. In this case, a mobile source 120
`is located within an antenna coverage circle 122 for a first
`repeater 124, an antenna coverage circle 126 for a second
`repeater 128 and an antenna coverage circle 130 for a BRU
`132. Accordingly, the BRU 132, the first repeater 124 and
`the second repeater 128 all receive the messages transmitted
`by the mobile source 120. Similarly, the first repeater 124
`and the second repeater 128 are located within the antenna
`coverage circle 130 for the BRU 132. Therefore, the BRU
`132 receives the messages subsequently transmitted by both
`the first repeater 124 and the second repeater 128, causing
`duplicate message packets. FIG. 6 represents the case where,
`without further means for distinguishing the three messages
`received by the BRU 132, the BRU 132 can equally well
`receive messages through three paths. One path is directly
`from the mobile source 120 to the BRU 132. Another path
`is through the first repeater 124 to the BRU 132, and the
`third path is from the second repeater 128 to the BRU 132.
`As in FIG. 5 above, those skilled in the art will recognize
`that FIG. 6 also means that transmissions from the BRU 132
`to the mobile source 120 can be transmitted directly and also
`relayed through the first and second repeaters 124 and 128.
`The situation shown in FIG. 5 does not require further
`information to determine the transmission path (given the
`necessary information concerning the relative positions of
`the mobile source 100 and repeaters 104 and 108 to the BRU
`112). However, the situation shown in FIG. 6 does. The
`geometry shown in FIG. 6 also allows for other possible
`transmission paths between the mobile source 120 and the
`BRU 132. One simple path is that from the mobile source
`120, through the first repeater 124, to the second repeater
`128, back to the first repeater 124, and then to the BRU 132.
`These multiple paths mean that, without further constraints
`on the transmission scheme,
`the BRU 132 will receive
`multiple copies of any message transmitted from the mobile
`source 120 to the BRU 132.
`The frame format shown in FIG. 4 contains information
`which can be used to reject all copies of any given messages
`transmitted from the mobile source 120 to the BRU 132,
`except the first message received by the BRU 132. This
`information is the repeat count field 96, shown in FIG. 4.
`The repeat count field 96 in the frame 90 for the message
`which is transmitted by the mobile source 120 is set to a
`predetermined number, representing the number of times
`which the message can be repeated before it is discarded by
`the radio packet communication system. Each time that the
`message is repeated by a repeater, the repeat count field 96
`of the message is decremented by one before being trans-
`mitted. When a repeater receives a message having a frame
`90 in which the repeat count field 96 has been decremented
`to zero, the repeater will not transmit the frame correspond-
`ing to the message. To accommodate the additional delays
`caused by repeaters, each device will calculate the required
`acknowledgment delay based on the number of repeaters set
`in the repeat count field 96. Forty milliseconds is added for
`each repeater, in the present embodiment.
`Another Fail mode for the packet radio communication
`system of the present invention is the generation of duplicate
`packets. This is shown in FIG. 6, where the message packet
`can be received through several links. One is the direct link
`from the mobile source 120 to the BRU 132. Two others are
`the once-relayed links from the mobile source 120 to the
`
`

`
`5,610,595
`
`9
`BRU 132 through the first repeater 124 or, alternatively,
`through the second repeater 128. The latter two messages
`can be discarded in favor of the directly received message by
`means of the sequence number field 92 (shown in FIG. 4).
`Each of the units in the packet radio communication system
`maintains a set of acceptable sequence numbers which
`designate which sequence numbers that particular unit will
`receive. All other messages will be discarded by that unit.
`FIG. 7A is a schematic diagram graphically illustrating a
`window used with the packet radio communication system
`of the present invention operating according to the protocol
`of the present invention, before the transmission of a mes-
`sage. The window has a circle 140 with sequence numbers
`on the circumference of the circle representing the possible
`values that can be contained in a set of possible sequence
`numbers. Preferably, the set of possible sequence numbers
`constitutes {O, .
`.
`.
`, 2N—1}, for some integer N. For ease of
`interpretation, the sequence numbers are considered modulo
`some integer base. If the set of possible sequence numbers
`constitutes {O,
`.
`.
`.
`, 2"—1},
`the integers are considered
`modulo 2”. Some predetermined fraction of the set of
`possible sequence numbers constitutes the set of sequence
`numbers in a “valid” window 142, and the set of remaining
`possible sequence numbers constitutes the set of sequence
`numbers in a “rejection” window 144. In the example shown
`in FIG. 7A, the set of seq