US5978382A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Adaptive random access protocol and fixed search tree expansion resolution for multiple station networks
Assignee: Zenith Electronics LLC
•
Filing: 1996-12-27
•
Granted: 1999-11-02
•
Expires: 2016-12-27
Abstract
Abstract A communication system has a plurality of stations which communicate data in a data frame having a plurality of slots, wherein the plurality of slots are new message minislots NMS, expansion minislots EMS, and data slots DS. A master station determines a range parameter R which is based upon a number of slave stations transmitting reservation requests in a data frame. The master station also determines a slot parameter MAP according to a number of reservation requests in a queue waiting to be processed by the master station. The slot parameter MAP defines the new message minislots, the expansion minislots, and the data slots in an upstream data frame. The master station transmits the range parameter R and the slot parameter MAP to a plurality of slave stations. Each slave station independently determines a random transmission parameter RN. Each slave station transmits to the master station (i) a new reservation request in a new message minislot if its random transmission parameter RN corresponds to a new message minislot, (ii) an old reservation request in an expansion minislot if assigned an expansion minislot in the slot parameter MAP, and (iii) data in a data slot if assigned a data slot by the master station.
Inventors
- 👤 Richard W. Citta
- 👤 Jingsong Xia
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-05 07:02
CPC Classifications
H; H04; H04N; H04N7/00; H04N7/16; H04N7/173; H04N7/17309; H04B; H04B3/00; H04B3/02; H04B3/36; H04B3/38; H04H; H04H60/00; H04H60/76; H04H60/81; H04H60/93; H04H60/96; H04H60/97; H04J; H04J3/00; H04J3/16; H04J3/1694; H04M; H04M11/00; H04M7/00; H04M7/006
Claims Analysis
Total Claims: 48
Claim 1
Independent Claim
167 words
A station comprising: a receiver arranged to receive a downstream data frame having a range parameter R and a parameter MAP, wherein the parameter MAP defines a number of new message minislots NMS, a number of expansion slots EMS, and a number of data slots DS in a next upstream data frame; a transmission parameter generator arranged to generate a transmission parameter RN, wherein the transmission parameter RN is constrained by the range parameter R; and, a transmitter arranged to transmit a reservation request in a new message minislot of the next upstream data frame if the transmission parameter RN bears a predetermined relationship to the new message minislot, to re-transmit a reservation request in an expansion minislot of the next upstream data frame if the station had transmitted a reservation request in a minislot which was in a previous upstream data frame and which was expanded in the next upstream data frame, and to transmit data in a data slot, if any, reserved to the station.
Claim 2
Dependent Claim
167 words
A station comprising: a receiver arranged to receive a downstream data frame having a range parameter R and a parameter MAP, wherein the parameter MAP defines a number of new message minislots NMS, a number of expansion slots EMS, and a number of data slots DS in a next upstream data frame; a transmission parameter generator arranged to generate a transmission parameter RN, wherein the transmission parameter RN is constrained by the range parameter R; and, a transmitter arranged to transmit a reservation request in a new message minislot of the next upstream data frame if the transmission parameter RN bears a predetermined relationship to the new message minislot, to re-transmit a reservation request in an expansion minislot of the next upstream data frame if the station had transmitted a reservation request in a minislot which was in a previous upstream data frame and which was expanded in the next upstream data frame, and to transmit data in a data slot, if any, reserved to the station.
Claim 3
Dependent Claim
25 words
The station of claim 1 wherein the next upstream data frame has S slots, wherein a slot is divided into m minislots, and wherein S=(NMS+EMS)/m+DS.
Claim 4
Dependent Claim
25 words
The station of claim 1 wherein the transmitter transmits a new reservation request only if the transmission parameter RN corresponds to a new message minislot.
Claim 5
Dependent Claim
14 words
The station of claim 1 wherein the transmission parameter RN is a random number.
Claim 6
Dependent Claim
39 words
The station of claim 1 wherein the transmitter comprises: a random slot selector arranged to randomly select one of the expansion minislots; and, a reservation request inserter arranged to insert a reservation request in the randomly selected expansion minislot.
Claim 7
Dependent Claim
17 words
The station of claim 1 wherein the next upstream data frame has MS(n+1) minislots, and wherein MS(n+1)=NMS(n+1)+EMS(n+1).
Claim 8
Dependent Claim
132 words
The station of claim 6 wherein: if DS(n)<DQ(n)<αDS (n), ##EQU12## wherein MS is the number of minislots in a data frame at discrete time n+1 and corresponds to the parameter MAP, wherein DS(n) is the number of data slots in a data frame at discrete time n, wherein DQ(n) is the number of reservation requests waiting to be processed at discrete time n, wherein α is a constant, wherein M is the number of minislots in steady state, wherein S is the number of slots in a data frame, wherein k is a number corresponding to an average number of data slots reserved by reservation requests, and wherein m is the number of minislots into which a slot of a data frame may be subdivided; if DQ(n)<DS(n), MS(n+1)=m(S-DQ(n)); and, if DQ(n)>αDS(n), ##EQU13##
Claim 9
Dependent Claim
26 words
The station of claim 1 wherein the expansion minislots EMS are minislots which are expanded from contention minislots according to a fixed search tree expansion procedure.
Claim 10
Dependent Claim
134 words
A station for transmitting data in slots of upstream data messages over a communication medium comprising: a) a receiver arranged to receive a downstream data message, wherein the downstream data message includes a slot parameter, and wherein the slot parameter indicates new message slots and expansion slots within which reservation requests may be transmitted; b) a first slot selector arranged to select one of the expansion slots; c) a second slot selector arranged to select, on at least a pseudorandom basis, one of the new message slots; and, d) an inserter arranged to insert a previously transmitted reservation request in the selected one of the expansion slots of a designated future upstream message and to insert a new reservation request in the selected one of the new message slots of a future upstream message.
Claim 11
Dependent Claim
134 words
A station for transmitting data in slots of upstream data messages over a communication medium comprising: a) a receiver arranged to receive a downstream data message, wherein the downstream data message includes a slot parameter, and wherein the slot parameter indicates new message slots and expansion slots within which reservation requests may be transmitted; b) a first slot selector arranged to select one of the expansion slots; c) a second slot selector arranged to select, on at least a pseudorandom basis, one of the new message slots; and, d) an inserter arranged to insert a previously transmitted reservation request in the selected one of the expansion slots of a designated future upstream message and to insert a new reservation request in the selected one of the new message slots of a future upstream message.
Claim 12
Dependent Claim
49 words
The station of claim 9 wherein an upstream data message has S slots, wherein S is dependent upon NS and ES, wherein NS designates a number of new message slots in the upstream data message, and wherein ES designates a number of expansion slots in the upstream data message.
Claim 13
Dependent Claim
58 words
The station of claim 9 wherein the downstream data message contains a range parameter R, wherein the second slot selector generates a transmission parameter RN constrained by the range parameter R, and wherein the inserter inserts a reservation request in a new message slot if the transmission parameter RN bears a predetermined relationship to a new message slot.
Claim 14
Dependent Claim
14 words
The station of claim 11 wherein the transmission parameter RN is a random number.
Claim 15
Dependent Claim
36 words
The station of claim 9 wherein the first slot selector randomly selects the selected one of the expansion slots and wherein the inserter inserts the reservation request in the randomly selected one of the expansion slots.
Claim 16
Dependent Claim
93 words
The station of claim 9 wherein an upstream data message has S slots, wherein an upstream data message has NS new message slots, wherein an upstream data message has ES expansion slots, wherein CS=NS+ES, wherein: if DS<DQ<αDS, ##EQU14## wherein DS=S-CS, wherein DQ is the number of reservation requests waiting to be processed in a reservation request queue, wherein α is a constant, wherein M is the number of CS in steady state, and wherein k is the average number of data slots reserved by reservation requests; if DQ<DS, CS=S-DQ; and, if DQ>αDS, ##EQU15##
Claim 17
Dependent Claim
25 words
The station of claim 9 wherein the expansion slots are slots which are expanded from contention slots according to a fixed search tree expansion procedure.
Claim 18
Independent Claim
106 words
A method of transmitting data in slots of upstream data messages comprising the following steps: a) receiving a downstream data message, wherein the downstream data message includes a range parameter R and a slot parameter, and wherein the slot parameter indicates new message slots and expansion slots in which reservation requests may be transmitted; b) selecting one of the expansion slots; c) selecting one of the new message slots according to the range parameter R; d) inserting a previously transmitted reservation request in the selected one of the expansion slots; and, e) inserting a new reservation request in the selected one of the new message slots.
Claim 19
Independent Claim
106 words
A method of transmitting data in slots of upstream data messages comprising the following steps: a) receiving a downstream data message, wherein the downstream data message includes a range parameter R and a slot parameter, and wherein the slot parameter indicates new message slots and expansion slots in which reservation requests may be transmitted; b) selecting one of the expansion slots; c) selecting one of the new message slots according to the range parameter R; d) inserting a previously transmitted reservation request in the selected one of the expansion slots; and, e) inserting a new reservation request in the selected one of the new message slots.
Claim 20
Dependent Claim
38 words
The method of claim 16 wherein the step c) comprises the steps of: generating a transmission parameter RN constrained by the range parameter R; and, if N falls within the new message slots, selecting new message slot N.
Claim 21
Dependent Claim
14 words
The method of claim 17 wherein the transmission parameter RN is a random number.
Claim 22
Dependent Claim
22 words
The method of claim 16 wherein the step b) comprises the step of randomly selecting the selected one of the expansion slots.
Claim 23
Dependent Claim
52 words
The method of claim 16 wherein an upstream data message has S slots, wherein NS is the number of new message slots in the upstream data message, wherein ES is the number of expansion slots in the upstream data message, wherein the upstream data message has DS data slots, and wherein S=NS+ES+DS.
Claim 24
Dependent Claim
99 words
The method of claim 16 wherein an upstream data message has S slots, wherein NS is the number of new message slots in the upstream data message, wherein ES is the number of expansion slots in the upstream data message, wherein CS=NS+ES, wherein: if DS<DQ<αDS, ##EQU16## wherein DQ is the number of reservation requests waiting to be processed in a reservation request queue, wherein α is a constant, wherein M is the number of CS in steady state, and wherein k is the average number of data slots reserved by reservation requests; if DQ<DS, CS=S-DQ; and, if DQ>αDS, ##EQU17##
Claim 25
Dependent Claim
25 words
The method of claim 16 wherein the expansion slots are slots which are expanded from contention slots according to a fixed search tree expansion procedure.
Claim 26
Dependent Claim
133 words
A station for transmitting and receiving data over a communication medium comprising: a) slot expanding means for expanding slots, which are in a data message received by the station and which experienced collisions, to expansion slots according to a search tree expansion procedure; b) slot parameter determining means for determining a slot parameter defining a future upstream data message, wherein the slot parameter indicates (i) new message slots within which new reservation requests may be transmitted to the station, and (ii) the expansion slots; c) range parameter determining means for determining a range parameter R useful in determining whether new reservation requests may be transmitted to the station; and, d) inserting means for inserting the slot parameter and the range parameter R in a downstream data message for communication over the communication medium.
Claim 27
Dependent Claim
133 words
A station for transmitting and receiving data over a communication medium comprising: a) slot expanding means for expanding slots, which are in a data message received by the station and which experienced collisions, to expansion slots according to a search tree expansion procedure; b) slot parameter determining means for determining a slot parameter defining a future upstream data message, wherein the slot parameter indicates (i) new message slots within which new reservation requests may be transmitted to the station, and (ii) the expansion slots; c) range parameter determining means for determining a range parameter R useful in determining whether new reservation requests may be transmitted to the station; and, d) inserting means for inserting the slot parameter and the range parameter R in a downstream data message for communication over the communication medium.
Claim 28
Dependent Claim
42 words
The station of claim 23 wherein an upstream data message has S slots, wherein an upstream data message has DS data slots, wherein an upstream data frame has ES expansion slots, and wherein an upstream data frame has NS new message slots.
Claim 29
Dependent Claim
66 words
The station of claim 24 wherein: if DS<DQ<αDS, ##EQU18## wherein CS=NS+ES, wherein S=CS+DS, wherein DQ is the number of reservation requests waiting to be processed in a reservation request queue, wherein α is a constant, wherein M is the number of CS in steady state, and wherein k is the average number of data slots reserved by reservation requests; if DQ<DS, CS=S-DQ; and, if DQ>αDS, ##EQU19##
Claim 30
Dependent Claim
38 words
The station of claim 23 wherein the slot expanding means expands slots, which are in a data message received by the station and which experienced collisions, to expansion slots ES according to a fixed search tree expansion procedure.
Claim 31
Dependent Claim
131 words
The station of claim 23 wherein the range parameter determining means determines the range parameter R according to the following equation: where n indicates a current frame just received by the station, n+1 indicates a next upstream data frame to be received by the station, R(n+1) is a range parameter for the next upstream data frame n+1, R(n) is a range parameter for the upstream data frame n just received, N represents a number of active other stations, NS(n+1) is a number of new message slots in the next upstream data frame n+1, NS(n) is a number of new message slots in the upstream data frame n just received, COL(n) is a parameter COL based upon the upstream data frame n just received, and e is 2.718281828 . . . .
Claim 32
Dependent Claim
72 words
The station of claim 27 wherein the number of active stations is determined by the following equation: ##EQU20## wherein N is the number of active stations, wherein NS is a total number of new message slots in the upstream data frame n just received, and wherein SUC is a number of new message slots in the upstream data frame n just received which include data but in which collisions did not occur.
Claim 33
Dependent Claim
78 words
The station of claim 27 wherein the number of active stations is determined from a lookup table generally corresponding to the following equation: ##EQU21## wherein N is the number of active stations, wherein NS is a total number of new message slots in the upstream data frame n just received, and wherein SUC is a number of new message slots in the upstream data frame n just received which include data but in which collisions did not occur.
Claim 34
Dependent Claim
69 words
The station of claim 27 wherein the number of active stations is determined by the following equation: ##EQU22## wherein N is the number of active stations, wherein NS is a total number of new message slots in the upstream data frame n just received, and wherein COL is a number of new message slots which are in the upstream data frame n just received and in which collisions occurred.
Claim 35
Dependent Claim
75 words
The station of claim 29 wherein the number of active stations is determined from a lookup table generally corresponding to the following equation: ##EQU23## wherein N is the number of active stations, wherein NS is a total number of new message slots in the upstream data frame n just received, and wherein COL is a number of new message slots which are in the upstream data frame n just received and in which collisions occurred.
Claim 36
Dependent Claim
25 words
The station of claim 23 wherein the expansion slots are slots which are expanded from contention slots according to a fixed search tree expansion procedure.
Claim 37
Dependent Claim
198 words
A station comprising: a receiver arranged to receive first and second downstream messages, wherein the first downstream message defines a first upstream message having new message slots, expansion slots, and data slots, and wherein the second downstream message defines a second upstream message having new message slots and an address determining whether the station may transmit a reservation request in one of the new message slots of the second upstream message; and, a transmitter, wherein the transmitter, in response to the first downstream message, transmits a reservation request in a new message slot of the first upstream message if the station determines to do so, re-transmits a reservation request in an expansion slot of the first upstream message if the station had transmitted a reservation request in a slot which was in a previous upstream message and which was expanded in the first upstream message, and transmits data in a data slot, if any, reserved to the station and wherein the transmitter, in response to the second downstream message, transmits a reservation request in a new message slot of the second upstream message if the address in the second downstream message corresponds to an address of the station.
Claim 38
Dependent Claim
198 words
A station comprising: a receiver arranged to receive first and second downstream messages, wherein the first downstream message defines a first upstream message having new message slots, expansion slots, and data slots, and wherein the second downstream message defines a second upstream message having new message slots and an address determining whether the station may transmit a reservation request in one of the new message slots of the second upstream message; and, a transmitter, wherein the transmitter, in response to the first downstream message, transmits a reservation request in a new message slot of the first upstream message if the station determines to do so, re-transmits a reservation request in an expansion slot of the first upstream message if the station had transmitted a reservation request in a slot which was in a previous upstream message and which was expanded in the first upstream message, and transmits data in a data slot, if any, reserved to the station and wherein the transmitter, in response to the second downstream message, transmits a reservation request in a new message slot of the second upstream message if the address in the second downstream message corresponds to an address of the station.
Claim 39
Dependent Claim
22 words
The station of claim 33 wherein the station is a subset of all stations receiving an address in the second upstream message.
Claim 40
Dependent Claim
17 words
The station of claim 33 wherein the address in the second upstream message is a group address.
Claim 41
Dependent Claim
23 words
The station of claim 35 wherein the station is a subset of all stations receiving the group address in the second upstream message.
Claim 42
Dependent Claim
25 words
The station of claim 33 wherein the expansion slots are slots which are expanded from contention slots according to a fixed search tree expansion procedure.
Claim 43
Dependent Claim
116 words
A station comprising: a receiver arranged to receive a downstream data frame having a contention range parameter R, wherein the contention range parameter R has one of at least two possible priority values; a transmission parameter generator arranged to generate a transmission parameter RN depending upon the priority of data to be transmitted by the station, wherein the transmission parameter RN is constrained by the contention range parameter R; and, a transmitter arranged to transmit a reservation request in a slot of a next upstream data frame if the transmission parameter RN corresponds to the slot in the next upstream data frame and if the reservation request relates to data corresponding to the transmission parameter RN.
Claim 44
Dependent Claim
116 words
A station comprising: a receiver arranged to receive a downstream data frame having a contention range parameter R, wherein the contention range parameter R has one of at least two possible priority values; a transmission parameter generator arranged to generate a transmission parameter RN depending upon the priority of data to be transmitted by the station, wherein the transmission parameter RN is constrained by the contention range parameter R; and, a transmitter arranged to transmit a reservation request in a slot of a next upstream data frame if the transmission parameter RN corresponds to the slot in the next upstream data frame and if the reservation request relates to data corresponding to the transmission parameter RN.
Claim 45
Dependent Claim
218 words
The station of claim 38 wherein: the receiver receives a downstream data frame having a first contention range parameter R H and a second contention range parameter R L , wherein the first contention range parameter R H is a high priority value, and wherein the second contention range parameter R L is a low priority value; the transmission parameter generator generates a first transmission parameter RN H if the station has high priority data to transmit and generates a second transmission parameter RN L if the station has low priority data to transmit, wherein the first transmission parameter RN H is constrained by the first contention range parameter R H and wherein the second transmission parameter RN L is constrained by the second contention range parameter R L ; and, the transmitter transmits a first reservation request in a slot of a next upstream data frame if the first transmission parameter RN H corresponds to the slot in the next upstream data frame and if the first reservation request relates to high priority data, and transmits a second reservation request in a slot of a next upstream data frame if the second transmission parameter RN L corresponds to the slot in the next upstream data frame and if the second reservation request relates to low priority data.
Claim 46
Dependent Claim
31 words
The station of claim 1 wherein the transmitter re-transmits a reservation request in an expansion minislot expanded from a minislot in which the transmitter had previously transmitted the re-transmitted reservation request.
Claim 47
Dependent Claim
27 words
The station of claim 9 wherein the selected expansion slot is expanded from a slot into which the inserter had previously inserted the previously transmitted reservation request.
Claim 48
Dependent Claim
26 words
The method of claim 16 wherein the selected expansion slot is expanded from a slot into which the previously transmitted reservation request had been previously inserted.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-11-01 | 2003-05-03 | 2003-11-02 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-11-01 | 2007-05-03 | 2007-11-02 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-11-01 | 2011-05-03 | 2011-11-02 | $7700.00 | Window Closed / Lapsed |