Distributed hierarchical scheduling in an AD hoc network

• US 7,818,018 B2
• Filed: 01/26/2005
• Issued: 10/19/2010
• Est. Priority Date: 01/29/2004
• Status: Active Grant

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Qualcomm, Inc.
• Inventors: Walton, Jay Rodney, Nanda, Sanjiv
• Primary Examiner(s): FERGUSON, KEITH
• Application Number:
  US11/044,539
• Publication Number:
  US 20050192037A1
• Time in Patent Office: 2,092 Days
• Field of Search: 455/509, 455/507, 455/500, 455450-453, 455/422.1, 455/403, 455/426.1, 455/426.2, 455/550.1, 455/63.1, 455/445, 455/68, 455/70, 455/67.11, 455/517, 455/516, 455/65, 455/518, 455/519, 370/337, 370/338, 370/329, 370/328, 370/345, 370/349, 370/313, 370/312, 370/310, 370/404, 370/405, 370/406, 370/424, 370/460
• US Class Current: 455/509
• CPC Class Codes: H04W 72/20 Control channels or signalling for resource management
• CPC Class Codes: H04W 72/542 using measured or perceived quality
• 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

An ad hoc network with distributed hierarchical scheduling is disclosed. In one aspect, stations in a network mesh detect interfering neighbor stations and form interference lists. Stations transmit their interference lists. Scheduling stations schedule allocations for child stations in response to interference lists, received remote allocations, or a combination thereof. Coordination messages are transmitted including frame structure, allocations, and interference lists, among others. In another aspect, an ad hoc mesh network may be organized into a tree topology. In an example wireless backhaul network, this matches traffic flow. Distributed, hierarchical scheduling is provided where parents schedule communication with children while respecting already scheduled transmissions to/from interferers and to/from interferers of their respective children. Procedures to construct interference constraints for distributed, hierarchical scheduling are described, resulting in efficient scheduling and reuse in an ad hoc wireless network, without centralized scheduling. Various other aspects are also disclosed.

Claims

1. An apparatus comprising:

a receiver for receiving one or more signals from one or more remote devices;

a message decoder for decoding one or more first interference lists from coordination messages contained in the one or more received signals from the one or more remote devices; and

a memory for storing the one or more first interference lists and a second interference list comprising identifiers identifying each of the one or more remote devices, each of the one or more remote devices identified in the second interference list capable of transmitting or receiving signals that interfere with the apparatus.

2. The apparatus of claim 1, wherein the message decoder further decodes one or more remote scheduled allocations from the one or more coordination messages, and further comprising a scheduler for scheduling one or more allocations for one or more remote devices in accordance with the first and second interference lists and the one or more remote scheduled allocations.

3. The apparatus of claim 2, wherein the receiver receives information from a remote device during a scheduled allocation.

4. The apparatus of claim 2, wherein the scheduler constrains transmission allocation for the apparatus when a remote scheduled allocation is directed to a remote device identified in the second interference list.

5. The apparatus of claim 2, wherein the scheduler constrains reception allocation for the apparatus when a remote scheduled allocation is directed from a remote device identified in the second interference list.

6. The apparatus of claim 2, wherein the scheduler constrains transmission from a first remote device identified in the second interference list, and for which the apparatus provides scheduling, when a remote scheduled allocation is directed to a second remote device, the second remote device identified in the first interference list associated with the first remote device.

7. The apparatus of claim 2, wherein the scheduler constrains transmission to a first remote device identified in the second interference list, and for which the apparatus provides scheduling, when a remote scheduled allocation is directed from a second remote device, the second remote device identified in the first interference list associated with the first remote device.

8. The apparatus of claim 2, further comprising a message generator for generating a coordination message comprising one or more scheduled allocations.

9. The apparatus of claim 8, further comprising a transmitter for transmitting the coordination message.

10. The apparatus of claim 9, wherein the transmitter transmits information to a remote device during a scheduled allocation.

11. The apparatus of claim 9, wherein:

the receiver receives a signal from a parent remote device, the signal comprising a coordination message;

the message decoder decodes a transmit allocation, if any;

the message decoder decodes a receive allocation, if any;

the receiver receives information according to the receive allocation; and

the transmitter transmits information according to the transmit allocation.

12. The apparatus of claim 1, further comprising a detector for detecting a beacon in a received signal for identifying a remote device.

13. A method comprising:

detecting signals received from one or more remote stations, the detected signals received by a backbone mesh station (BMS);

identifying the one or more remote stations;

storing an identifier associated with each of the one or more remote stations in a first interference list, each of the one or more remote stations capable of transmitting or receiving signals that interfere with the BMS; and

transmitting the first interference list for reception by neighbor remote stations.

14. The method of claim 13, further comprising:

receiving one or more remote allocations;

receiving a second interference list from one or more remote stations; and

scheduling allocations of a shared resource in response to the one or more remote allocations, the second interference list, and the first interference list.

15. The method of claim 14, further comprising:

receiving one or more superframe parameters;

forming a coordination message comprising the one or more superframe parameters, the first interference list, and the scheduled allocations; and

transmitting the coordination message.

16. The method of claim 15, further comprising:

receiving a coordination message at a first station from a second station;

decoding an allocation from the coordination message; and

transmitting information from the first station to the second station in accordance with the decoded allocation.

17. The method of claim 15, further comprising:

receiving a coordination message at a first station from a second station;

decoding an allocation from the coordination message; and

receiving information at the first station from the second station in accordance with the decoded allocation.

18. The method of claim 13, further comprising:

forming a superframe indicated by one or more superframe parameters; and

transmitting the superframe parameters.

19. The method of claim 18, further comprising:

receiving one or more superframe parameters;

forming a coordination message comprising the one or more superframe parameters and the first interference list; and

transmitting the coordination message.

20. An apparatus comprising:

means for detecting signals received from one or more remote stations, the detected signals received by a backbone mesh station (BMS);

means for identifying the one or more remote stations;

means for storing an identifier associated with each of the one or more remote stations in a first interference list, each of the one or more remote stations capable of transmitting or receiving signals that interfere with the BMS; and

means for transmitting the first interference list for reception by neighbor remote stations.

21. The apparatus of claim 20, further comprising:

means for receiving one or more remote allocations;

means for receiving a second interference list from one or more remote stations; and

means for scheduling allocations of a shared resource in response to the one or more remote allocations, the second interference list, and the first interference list.

22. An apparatus comprising:

a receiver for receiving one or more signals from one or more remote devices;

a message for decoder decoding one or more first interference lists and one or more remote allocations from coordination messages contained in the one or more received signals from respective one or more remote devices; and

means for allocating a shared resource for receiving and transmitting by one or more remote devices based on the one or more first interference lists and the one or more remote allocations.

23. A computer readable storage medium, comprising:

code for causing at least one computer to detect signals received from one or more remote stations, the detected signals received by a backbone mesh station (BMS);

code for causing at least one computer to identify the one or more remote stations;

code for causing at least one computer to store an identifier associated with each of the one or more remote stations in a first interference list, each of the one or more remote stations capable of transmitting or receiving signals that interfere with the BMS; and

code for causing at least one computer to transmit the first interference list for reception by neighbor remote stations.

24. The computer readable storage medium of claim 23, further comprising:

code for causing at least one computer to receive one or more remote allocations;

code for causing at least one computer to receive a second interference list from one or more remote stations; and

code for causing at least one computer to schedule allocations of a shared resource in response to the one or more remote allocations, the second interference list, and the first interference list.