Scalable, self-organizing packet radio network having decentralized channel management providing collision-free packet transfer

• US 5,682,382 A
• Filed: 09/05/1995
• Issued: 10/28/1997
• Est. Priority Date: 09/05/1995
• Status: Expired due to Fees

• Current Assignee: Massachusetts Institute of Technology
• Original Assignee: Massachusetts Institute of Technology
• Inventors: Shepard, Timothy Jason
• Primary Examiner(s): Chin, Wellington
• Assistant Examiner(s): Hyun, Soon D.
• Application Number:
  US08/523,715
• Time in Patent Office: 784 Days
• Field of Search: 370/85.2, 370/94.1, 370/18, 370/94.2, 370/94.3, 370/310, 370/320, 370/321, 370/335, 370/349, 370/913, 370/441, 370/348, 375/205, 375/206, 375/208, 375/200, 375/203
• US Class Current: 370/342
• CPC Class Codes: H04W 48/08 Access restriction or access information delivery, e.g. discovery data delivery signalling during connection H04W76/00
• CPC Class Codes: H04W 52/46 in multi hop networks, e.g. wireless relay networks
• CPC Class Codes: H04W 72/12 Wireless traffic scheduling
• CPC Class Codes: H04W 74/04 Scheduled access hybrid access H04W74/02
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks

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.

Claims

1. 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.

2. 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.

3. 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.

4. The invention of claim 3, wherein the spread-spectrum transmitter implements direct sequence coding.

5. 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.

6. The invention of claim 5, wherein the random generation is implemented by a binary-valued function of a clock reading.

7. The invention of claim 6, wherein the information representative of each station'"'"'s unique clock is its clock reading.

8. The invention of claim 6, wherein each station'"'"'s unique schedule of transmit and receive opportunities has equal length transmit and receive opportunities.

9. The invention of claim 8, wherein each transmit opportunity is divided into a plurality of transmit subslots.

10. The invention of claim 9, wherein each subslot is made equal in length to the maximum packet length.

11. The invention of claim 2, wherein said third means includes a processor implemented second scheduling technique.

12. 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.

13. 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.

14. The invention of claim 13, wherein the random generation is implemented by a binary-valued function of a clock reading.

15. The invention of claim 14, wherein the information representative of each station'"'"'s unique clock is its clock reading.

16. The invention of claim 13, wherein each station'"'"'s unique schedule of transmit and receive opportunities has equal length transmit and receive opportunities.

17. The invention of claim 16, wherein each transmit opportunity is divided into a plurality of transmit subslots.

18. The invention of claim 17, wherein each subslot is made equal in length to the maximum packet length.

19. The invention of claim 6, wherein the binary-valued function of a clock reading utilizes a hash function.

20. The invention of claim 14, wherein the binary-valued function of a clock reading utilizes a hash function.

21. 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.

22. The invention of claim 1, wherein said generation is random generation.

24. The invention of claim 21, wherein said fourth means includes a spread-spectrum receiver having multiple tacking and despreading channels.

23. 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.