US5682382A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Scalable, self-organizing packet radio network having decentralized channel management providing collision-free packet transfer
Assignee: Massachusetts Institute of Technology
•
Filing: 1995-09-05
•
Granted: 1997-10-28
•
Expires: 2015-09-05
Abstract
Abstract A scalable, self-organizing packet radio network providing decentralized collision-free packet transfer is disclosed having spread-spectrum transmitters and receivers for eliminating contention from background noise, spread-spectrum receivers with multiple tracking and despreading channels for eliminating contention from multiple transmitters contending for the same receiver at the same time, and a processor implemented scheduling technique for eliminating contention arising both from self-contention and from comparatively-high power transmissions of neighboring stations. In the preferred embodiments, the processor implemented scheduling technique randomly provides a unique schedule of transmit and receive opportunities for each station. In accord therewith, each station obliges itself to listen and publishes the unique schedule of each station to every neighboring station. To avoid self-contention, a packet is transmitted to an intended station at a time that corresponds to the first available listening opportunity thereof that is long enough to receive the packet. To avoid contention arising from comparatively-high power transmissions of neighboring stations, a packet is transmitted to an intended station at a time that corresponds to the first available transmit opportunity thereof that does not overlap with the receive windows of any neighboring station. In the preferred embodiments, a processor implemented power control technique is disclosed which so varies transmitter power as to provide a fixed level of power at any intended recipient station. In the preferred embodiments, minimum energy routing is employed for specifying intended stations for multi-hop packet transfer. In the presently preferred embodiments, the random generation at each station of its unique schedule is implemented by a pseudo-random schedule generator common to all stations and by a pseudo-random clock unique to each station. In the presently preferred embodiment, neighboring stations periodically exchange rendezvous packets that include information representative of each station's pseudo-random clock, transmitted power and station identity.
Inventors
- 👤 Timothy Jason Shepard
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-08 03:56
CPC Classifications
H; H04; H04W; H04W52/00; H04W52/04; H04W52/38; H04W52/46; H04W74/00; H04W74/04; H04W48/00; H04W48/08; H04W72/00; H04W72/12; H04W84/00; H04W84/18
Claims Analysis
Total Claims: 26
Claim 1
Independent Claim
185 words
A scalable, self-organizing packet radio network station providing decentralized collision-free packet transfer between stations, comprising: first means for eliminating at each station packet loss from contention appearing as background noise that arises from all of the stations that may be on the network at any given time; and second means for eliminating at each station packet loss caused by its own transmitter contending with, at its own receiver, receptions of packets from one or more neighboring stations; wherein said second means includes a processor implemented first scheduling technique; and wherein the processor implemented first scheduling technique (i) generates at each station a schedule of transmit opportunities and receive opportunities during which it obliges itself to listen, which schedule is unique to each station and asynchronous with that of other stations, (ii) publishes its unique schedule to the other neighboring stations, (iii) compares its unique schedule of transmit and receive opportunities with that of a neighboring station intended to receive the transmission to determine when packets may be transferred thereto during a receive opportunity thereof without collision and (iv) transmits its packets thereto at such times.
Claim 2
Dependent Claim
185 words
A scalable, self-organizing packet radio network station providing decentralized collision-free packet transfer between stations, comprising: first means for eliminating at each station packet loss from contention appearing as background noise that arises from all of the stations that may be on the network at any given time; and second means for eliminating at each station packet loss caused by its own transmitter contending with, at its own receiver, receptions of packets from one or more neighboring stations; wherein said second means includes a processor implemented first scheduling technique; and wherein the processor implemented first scheduling technique (i) generates at each station a schedule of transmit opportunities and receive opportunities during which it obliges itself to listen, which schedule is unique to each station and asynchronous with that of other stations, (ii) publishes its unique schedule to the other neighboring stations, (iii) compares its unique schedule of transmit and receive opportunities with that of a neighboring station intended to receive the transmission to determine when packets may be transferred thereto during a receive opportunity thereof without collision and (iv) transmits its packets thereto at such times.
Claim 3
Dependent Claim
29 words
The invention of claim 1, further including third means for eliminating at each station packet loss due to interference from comparatively-high power transmission of one or more neighboring stations.
Claim 4
Dependent Claim
37 words
The invention of claim 1, wherein said first means includes a spread-spectrum transmitter providing a spread-spectrum processing gain selected to be greater than the average background signal-to-noise ratio of all stations that may be on the network.
Claim 5
Dependent Claim
13 words
The invention of claim 3, wherein the spread-spectrum transmitter implements direct sequence coding.
Claim 6
Dependent Claim
99 words
The invention of claim 1, wherein the generation at each station is implemented by a pseudo-random schedule generator common to all stations and by a pseudo-randomly initialized clock unique to each station, wherein each station periodically exchanges rendezvous packets with neighboring stations that include information representative of each station's unique clock, and wherein the comparison at each station of its unique schedule of transmit and receive opportunities with that of the intended recipient station is implemented by generating at each station the unique schedule of transmit and receive opportunities of the intended recipient station from that station's unique clock.
Claim 7
Dependent Claim
19 words
The invention of claim 5, wherein the random generation is implemented by a binary-valued function of a clock reading.
Claim 8
Dependent Claim
18 words
The invention of claim 6, wherein the information representative of each station's unique clock is its clock reading.
Claim 9
Dependent Claim
22 words
The invention of claim 6, wherein each station's unique schedule of transmit and receive opportunities has equal length transmit and receive opportunities.
Claim 10
Dependent Claim
17 words
The invention of claim 8, wherein each transmit opportunity is divided into a plurality of transmit subslots.
Claim 11
Dependent Claim
18 words
The invention of claim 9, wherein each subslot is made equal in length to the maximum packet length.
Claim 12
Dependent Claim
16 words
The invention of claim 2, wherein said third means includes a processor implemented second scheduling technique.
Claim 13
Dependent Claim
137 words
The invention of claim 11, wherein the processor implemented second scheduling technique (i) generates at each station a schedule of transmit opportunities and receive opportunities during which it obliges itself to listen, which schedule is unique to each station and asynchronous with that of other stations (ii) publishes its unique schedule to other neighboring stations, (iii) compares its schedule of transmit and receive opportunities with that of an intended neighboring station and with those of one or more other neighboring stations to determine when a transmit opportunity first arises that does not overlap with any receive opportunity of the one or more neighboring stations so that packets may be transferred to the intended neighboring station without causing collision at one or the other neighboring stations and (iv) transmits its packets to the intended station at such times.
Claim 14
Dependent Claim
116 words
The invention of claim 12, wherein the generation at each station is implemented by a pseudo-random schedule generator common to all stations and by a pseudo-random clock unique to each station, wherein each station periodically exchanges rendezvous packets with neighboring stations that include information representative of each station's unique clock, and wherein the comparison at each station of its unique schedule of transmit and receive opportunities with that of the intended recipient station and with those of the one or more neighbor stations is implemented by generating at each station the unique schedule of transmit and receive opportunities of the intended recipient station and of the one or more neighbor stations from those station's unique clock.
Claim 15
Dependent Claim
19 words
The invention of claim 13, wherein the random generation is implemented by a binary-valued function of a clock reading.
Claim 16
Dependent Claim
18 words
The invention of claim 14, wherein the information representative of each station's unique clock is its clock reading.
Claim 17
Dependent Claim
22 words
The invention of claim 13, wherein each station's unique schedule of transmit and receive opportunities has equal length transmit and receive opportunities.
Claim 18
Dependent Claim
17 words
The invention of claim 16, wherein each transmit opportunity is divided into a plurality of transmit subslots.
Claim 19
Dependent Claim
18 words
The invention of claim 17, wherein each subslot is made equal in length to the maximum packet length.
Claim 20
Dependent Claim
17 words
The invention of claim 6, wherein the binary-valued function of a clock reading utilizes a hash function.
Claim 21
Dependent Claim
17 words
The invention of claim 14, wherein the binary-valued function of a clock reading utilizes a hash function.
Claim 22
Dependent Claim
36 words
The invention of claim 1, further including fourth means for eliminating at each station packet loss caused by multiple other neighboring stations that may be sending generally simultaneously with a given station at a given time.
Claim 23
Dependent Claim
11 words
The invention of claim 1, wherein said generation is random generation.
Claim 24
Dependent Claim
112 words
A self-organizing packet radio network station providing decentralized packet transfer between stations, comprising: a processor; and a processor implemented first scheduling technique which (i) generates at each station a schedule of transmit opportunities and receive opportunities during which it obliges itself to listen, which schedule is unique to each station and asynchronous with that of other stations, (ii) publishes its unique schedule to the other neighboring stations, (iii) compares its unique schedule of transmit and receive opportunities with that of a neighboring station intended to receive the transmission to determine when packets may be transferred thereto during a receive opportunity thereof without collision and (iv) transmits its packets thereto at such times.
Claim 25
Dependent Claim
112 words
A self-organizing packet radio network station providing decentralized packet transfer between stations, comprising: a processor; and a processor implemented first scheduling technique which (i) generates at each station a schedule of transmit opportunities and receive opportunities during which it obliges itself to listen, which schedule is unique to each station and asynchronous with that of other stations, (ii) publishes its unique schedule to the other neighboring stations, (iii) compares its unique schedule of transmit and receive opportunities with that of a neighboring station intended to receive the transmission to determine when packets may be transferred thereto during a receive opportunity thereof without collision and (iv) transmits its packets thereto at such times.
Claim 26
Dependent Claim
19 words
The invention of claim 21, wherein said fourth means includes a spread-spectrum receiver having multiple tacking and despreading channels.
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) | 2000-10-27 | 2001-04-28 | 2001-10-28 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2004-10-27 | 2005-04-28 | 2005-10-28 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2008-10-27 | 2009-04-28 | 2009-10-28 | $7700.00 | Window Closed / Lapsed |