Method and apparatus for an ad-hoc wireless communications system

• US 8,315,271 B2
• Filed: 03/23/2005
• Issued: 11/20/2012
• Est. Priority Date: 03/26/2004
• Status: Active Grant

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Qualcomm, Inc.
• Inventors: Nanda, Sanjiv, Walton, Jay Rodney
• Primary Examiner(s): SAMS, MATTHEW C
• Application Number:
  US11/088,382
• Publication Number:
  US 20060227801A1
• Time in Patent Office: 2,799 Days
• Field of Search: 370/278, 370/282, 370/322, 370/348, 370/450, 370/453, 370/461, 370/445
• US Class Current: 370/450
• CPC Class Codes: H04L 47/15 in relation to multipoint traffic arrangements for broadcast or multicast in data networks H04L12/18
• CPC Class Codes: H04L 47/70 Admission control; Resource allocation
• CPC Class Codes: H04W 72/04 Wireless resource allocation

Abstract

An IBSS that allows token passing for round-robin service of QoS flows is disclosed (an RRBSS). The RRBSS permits low-latency, reduced contention, distributed scheduling useful in any ad hoc network, but particularly suitable for high data rates. Distributed scheduled access is provided for flows through a round-robin token passing service discipline. STAs follow a round-robin order, or list, and are able to communicate with round-robin transmit opportunities during a defined period. Each STA in the list transmits a respective token to transfer access to the shared medium to the next STA in the RR List. The sequence is terminated with an end token. STAs maintain station identifiers and list updates are maintained with a sequence identifier. Techniques are disclosed to add and remove STAs to the sequence; establish connectivity lists (receive and forward), and maintain other sequence parameters such as bandwidth management and TXOP duration. Various other aspects are also disclosed.

Claims

1. An apparatus comprising:

a memory for storing a sequence list;

a receiver for receiving a first signal indicating transfer of control of a shared medium from a first remote station with an associated station identifier in the sequence list; and

a transmitter for transmitting on the shared medium subsequent to receiving the signal, and for transmitting a second signal indicating transfer of control of the shared medium to a second remote station with an associated station identifier in the sequence list subsequent to expiration of a time allotment for control of the shared medium,

wherein the second signal comprises a token selected from a plurality of token messages and wherein the selected token comprises the sequence list,

wherein the second remote station receives the token, selects a station identifier for a monitoring station and transmits an add message comprising a new sequence list, the new sequence list comprising the station identifier for the monitoring station,

wherein the add message is transmitted subsequent to transmission by a third remote station of a token indicating the end to a period of transmissions associated with the sequence list, when the transmission from the third station is received and decoded by the station transmitting the add message.

2. The apparatus of claim 1, wherein:

the receiver further receives one or more signals from one or more remote stations, and further comprising;

a message decoder for decoding messages received from one or more remote stations;

a processor for;

selecting a station identifier for association with the apparatus;

extracting the sequence list from a message decoded in the message decoder and storing the sequence list in the memory;

generating and updating a receive connectivity list indicating remote stations on the sequence list from which signals may be received and messages decoded, and storing the receive connectivity list in the memory;

generating and updating a forward connectivity list indicating remote stations on the sequence list at which signals transmitted with the transmitter may be received and decoded, and storing the forward connectivity list in the memory; and

receiving from the message decoder and conditionally updating a sequence identifier associated with the sequence list, and storing the sequence identifier in the memory; and

a message generator for generating a token message for indicating transfer of control and delivering the token message to the transmitter for transmission.

3. A method of sharing a common medium comprising:

forming a sequence list comprising one or more station identifiers; and

transmitting a token from a first station to a second station, in accordance with the sequence list, to pass control of the common medium from the first station to the second station, wherein transmitting the token comprises transmitting a token selected from a plurality of token messages and wherein the selected token comprises the sequence list,

wherein the second station receives the token, selects a station identifier for a monitoring station and transmits an add message comprising a new sequence list, the new sequence list comprising the station identifier for the monitoring station,

wherein the add message is transmitted subsequent to transmission by a third remote station of a token indicating the end to a period of transmissions associated with the sequence list, when the transmission from the third station is received and decoded by the station transmitting the add message.

4. The method of claim 3, wherein the plurality of token messages comprising a first token message and a second token message, the first token message shorter than the second token message.

5. The method of claim 4, wherein the first token message comprises:

a first station identifier associated with the first station transferring control; and

a second station identifier associated with the second station receiving control, the second station identifier subsequent to the first station identifier in the sequence list.

6. The message of claim 5, wherein the first token message further comprises a third station identifier associated with a third station, the third station identifier the last station identifier in the sequence list.

7. The message of claim 6, wherein the first token message further comprises a bandwidth management field.

8. The method of claim 4, wherein the second token message comprises:

a station identifier associated with the second station receiving control; and

the sequence list comprising station identifiers associated with a plurality of stations for sequentially accessing the common medium.

9. The message of claim 8, wherein the second token message further comprises a connectivity vector field.

10. The method of claim 3, wherein the first station transmitting on the shared medium during a sequence period is rotated during successive sequence periods.

11. The method of claim 3, wherein the forming a sequence list comprises:

earning access to the common medium;

selecting a first station identifier;

forming the sequence list with the first station identifier;

transmitting a token comprising the first station identifier;

monitoring the common medium for one or more add messages from one or more remote stations, each add message comprising a second station identifier associated with the respective remote stations; and

adding one or more second station identifiers to the sequence list.

12. The method of claim 11, further comprising:

accessing the common medium following a first delay, the first delay shorter than one or more second delays associated with one or more alternate common medium access types;

transmitting a beacon; and

transmitting a token comprising the sequence list to a next remote station, the next remote station associated with a next station identifier on the sequence list.

13. The method of claim 3, further comprising:

transmitting a token from a first station comprising a receive connectivity list associated with that station, the receive connectivity list indicating receive capability from stations associated with station identifiers in the sequence list;

receiving the token at one or more second remote stations; and

updating the forward connectivity list to indicate forward connectivity with the first station in each second remote station capable of decoding the token, and for which receive capability of the respective second station is indicated in the receive connectivity list of the first station.

14. The method of claim 3, further comprising:

monitoring at a first station signal transmissions from one or more second stations; and

updating a receive connectivity list to indicate receive capability for each second station from which signal transmissions are received and decoded.

15. The method of claim 3, further comprising:

updating a sequence identifier when the sequence list is modified; and

transmitting a token comprising the sequence identifier and the modified sequence list.

16. The method of claim 15, further comprising:

receiving a series of one or more tokens at a third station, each token comprising a sequence identifier;

transmitting a token comprising the sequence list when the sequence identifier included in one of the one or more tokens is updated.

17. The method of claim 3, wherein the sequence identifier is updated when a station is added to the sequence list.

18. The method of claim 3, wherein the sequence identifier is updated when a station is removed from the sequence list.

19. The method of claim 3, wherein the sequence identifier is updated when the order of station identifiers in the sequence list is changed, other than a predefined periodic sequence list reordering.

20. The method of claim 19, wherein a predefined periodic sequence list reordering comprises shifting the station identifiers in the list one position toward the end of the list, and moving the last station identifier to the first position in the list.

21. The method of claim 19, wherein a predefined periodic sequence list reordering comprises a random shuffling of the order of station identifiers in the sequence list.

22. The method of claim 3, further comprising:

transmitting a token from a third station to a fourth station, the token comprising the sequence list modified to indicate a predefined value, other than the third station identifier, in the position associated with the third station in the sequence list;

removing the station identifier associated with the third station from the sequence list subsequent to receiving the transmitted token.

23. The method of claim 3, further comprising:

monitoring transmissions from one or more remote stations; and

removing the station identifier associated with one of the one or more remote stations when the respective remote station fails to utilize a transmission opportunity within a predetermined time period.

24. The method of claim 23, wherein the removing comprises transmitting a token comprising the sequence list modified to indicate a predefined value, other than the respective station identifier, in the sequence list in the position associated with the remote station failing to utilize the transmission opportunity.

25. The method of claim 3, further comprising:

monitoring transmissions from the one or more remote stations indicated in the sequence list, wherein the sequence list comprises one or more station identifiers associated with the one or more remote stations.

26. The method of claim 25, wherein the add message is transmitted subsequent to a period of the transmissions associated with the sequence list.

27. A method comprising:

transmitting a token from a first station with access to a shared medium to a second station according to a list of one or more stations sharing the shared medium in sequence,

wherein transmitting the token comprises transmitting a token selected from a plurality of token messages and wherein the selected token comprises the sequence list; and

transferring control of the shared access to the second station after the token is transmitted,

wherein the second station receives the token, selects a station identifier for a monitoring station and transmits an add message comprising a new sequence list, the new sequence list comprising the station identifier for the monitoring station,

wherein the add message is transmitted subsequent to transmission by a third remote station of a token indicating the end to a period of transmissions associated with the sequence list, when the transmission from the third station is received and decoded by the station transmitting the add message.

28. The method of claim 27, wherein the token is a message comprising the list of one or more stations sharing the shared medium in sequence.

29. The method of claim 27, wherein the token is a message comprising a sequence identifier.

30. The method of claim 27, wherein the token is a message comprising an identifier of the last station in a list of one or more stations sharing the shared medium in sequence.

31. The method of claim 27, wherein the second station is selected from the list as the station subsequent to the first station in the list.

32. The method of claim 27, wherein the token is transmitted subsequent to one or more data transmissions between the first station and one or more remote stations.

33. The method of claim 27, further comprising transmission by the second station to one or more remote stations subsequent to receiving the token.

34. The method of claim 33, further comprising transmission of a token indicating the end of a sequence.

35. The method of claim 27, further comprising reclaiming access to the shared medium with the first station if the second station fails to transmit on the shared medium within a predetermined time period subsequent to control transfer.

36. A basic service set (BSS) comprising:

a plurality of stations sharing access to a common medium; and

token-passing means for sequential service of flows from one or more of the plurality of stations according to a list comprising identifiers corresponding to the one or more of the plurality of stations,

wherein the token passing means is configured to select a token to pass from a plurality of token messages and wherein the selected token comprises the list,

wherein a receiving station receives the token, selects a station identifier for a monitoring station and transmits an add message comprising a new sequence list, the new sequence list comprising the station identifier for the monitoring station,

wherein the add message is transmitted subsequent to transmission by a third remote station of a token indicating the end to a period of transmissions associated with the sequence list, when the transmission from the third station is received and decoded by the station transmitting the add message.

37. In a wireless network, comprising one or more stations sharing a common medium, a method comprising:

accessing the medium in a series of time segments, the segments delineated by a first signal;

transmitting a second signal on the shared medium from a first station after a first delay following the transmission of the first signal, the first delay less than one or more second delays employed by one or more remote stations,

wherein first station transmits after the first delay based on the first station having a token for accessing the medium and wherein the one or more second delays is associated with one or more alternate common medium access types, the second signal comprising a token message for transferring control of the shared medium to a second station, wherein the token message comprises a list of one or more stations sharing the medium;

wherein a receiving station receives the token comprising a sequence list, selects a station identifier for a monitoring station and transmits an add message comprising a new sequence list, the new sequence list comprising the station identifier for the monitoring station,

wherein the add message is transmitted subsequent to transmission by a third remote station of a token indicating the end to a period of transmissions associated with the sequence list, when the transmission from the third station is received and decoded by the station transmitting the add message.

38. The method of claim 37, the second signal further comprising one or more transmissions between the first station and one or more third remote stations prior to token message transmission.

39. An apparatus comprising:

means for forming a sequence list comprising one or more station identifiers; and

means for transmitting a token from a first station to a second station, in accordance with the sequence list, to pass control of a common medium from the first station to the second station,

wherein the token transmitting means is configured to select a token from a plurality of token messages and wherein the selected token comprises the sequence list,

wherein the second station receives the token, selects a station identifier for a monitoring station and transmits an add message comprising a new sequence list, the new sequence list comprising the station identifier for the monitoring station,

wherein the add message is transmitted subsequent to transmission by a third remote station of a token indicating the end to a period of transmissions associated with the sequence list, when the transmission from the third station is received and decoded by the station transmitting the add message.

40. An apparatus comprising:

means for transmitting a token from a first station with access to a shared medium to a second station according to a list of one or more stations sharing the shared medium in sequence,

wherein the token transmitting means is configured to select a token from a plurality of token messages and wherein the selected token comprises the list of one or more stations; and

means for transferring control of the shared access to the second station after the token is transmitted,

wherein the second station receives the token, selects a station identifier for a monitoring station and transmits an add message comprising a new sequence list, the new sequence list comprising the station identifier for the monitoring station,

wherein the add message is transmitted subsequent to transmission by a third remote station of a token indicating the end to a period of transmissions associated with the sequence list, when the transmission from the third station is received and decoded by the station transmitting the add message.

41. Non-transitory computer readable media operable to perform:

forming a sequence list comprising one or more station identifiers; and

transmitting a token from a first station to a second station, in accordance with the sequence list, to pass control of a common medium from the first station to the second station,

wherein transmitting the token comprises transmitting a token selected from a plurality of token messages and wherein the selected token comprises the sequence list,

wherein the second station receives the token, selects a station identifier for a monitoring station and transmits an add message comprising a new sequence list, the new sequence list comprising the station identifier for the monitoring station,

wherein the add message is transmitted subsequent to transmission by a third remote station of a token indicating the end to a period of transmissions associated with the sequence list, when the transmission from the third station is received and decoded by the station transmitting the add message.