DISTRIBUTED HIERARCHICAL SCHEDULING IN AN AD HOC NETWORK

• US 20110223952A1
• Filed: 09/15/2010
• Published: 09/15/2011
• Est. Priority Date: 01/29/2004
• Status: Active Grant

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Qualcomm, Inc.
• Inventors: Walton, J. Rodney, Nanda, Sanjiv
• Granted Patent: US 8,903,440 B2
• Time in Patent Office: Days
• 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 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. A method of operating a parent mesh station within an ad-hoc mesh network, comprising:

determining a first set of mesh stations that belong to the ad-hoc mesh network, wherein wireless transmissions from each of the first set of mesh stations is expected to directly interfere with wireless transmissions from the parent mesh station;

determining, for each of the first set of mesh stations, a second set of mesh stations that belong to the ad-hoc mesh network, wherein wireless transmissions from each of the second set of mesh stations is expected to directly interfere with wireless transmissions from the associated mesh station of the first set of mesh stations; and

selectively constraining communications associated with a given mesh station among the first set of mesh stations based on a transmission schedule that includes one or more previously scheduled transmissions or receptions associated with the parent mesh station, the first set of mesh stations and/or the second set of mesh stations.

2. The method of claim 1, wherein the transmission schedule includes a given scheduled transmission to at least one of the first set of mesh stations.

3. The method of claim 2, wherein the selectively constraining step constrains transmissions from the parent mesh station so as not to interfere with the given scheduled transmission.

4. The method of claim 1, wherein the transmission schedule includes a given scheduled transmission from at least one of the first set of mesh stations.

5. The method of claim 4, wherein the selectively constraining step constrains a receive schedule at the parent mesh station so as not to interfere with the given scheduled transmission.

6. The method of claim 1, wherein the transmission schedule includes a given scheduled transmission to one of the mesh stations among the second set of mesh stations for the given mesh station.

7. The method of claim 6, wherein the selectively constraining step constrains transmissions from the given mesh station so as not to interfere with the given scheduled transmission.

8. The method of claim 1, wherein the transmission schedule includes a given scheduled transmission to the given mesh station from one of the mesh stations among the second set of mesh stations for the given mesh station.

9. The method of claim 8, wherein the selectively constraining step constrains a receive schedule at the given mesh station so as not to interfere with the given scheduled transmission.

10. The method of claim 1, further comprising:

monitoring beacon signals from the first set of mesh stations,

wherein the transmission schedule is determined from the monitored beacon signals.

11. A parent mesh station within an ad-hoc mesh network, comprising:

means for determining a first set of mesh stations that belong to the ad-hoc mesh network, wherein wireless transmissions from each of the first set of mesh stations are expected to directly interfere with wireless transmissions from the parent mesh station;

means for determining, for each of the first set of mesh stations, a second set of mesh stations that belong to the ad-hoc mesh network, wherein wireless transmissions from each of the second set of mesh stations are expected to directly interfere with wireless transmissions from the associated mesh station of the first set of mesh stations; and

means for selectively constraining communications associated with a given mesh station among the first set of mesh stations.

12. A parent mesh station within an ad-hoc mesh network, comprising:

logic configured to determine a first set of mesh stations that belong to the ad-hoc mesh network, wherein wireless transmissions from each of the first set of mesh stations are expected to directly interfere with wireless transmissions from the parent mesh station;

logic configured to determine, for each of the first set of mesh stations, a second set of mesh stations that belong to the ad-hoc mesh network, wherein wireless transmissions from each of the second set of mesh stations are expected to directly interfere with wireless transmissions from the associated mesh station of the first set of mesh stations; and

logic configured to selectively constrain communications associated with a given mesh station among the first set of mesh stations.

13. A non-transitory computer-readable storage medium containing instructions stored thereon, which, when executed by a parent mesh station within an ad-hoc mesh network, cause the parent mesh station to perform operations, the instructions comprising:

program code to determine a first set of mesh stations that belong to the ad-hoc mesh network, wherein wireless transmissions from each of the first set of mesh stations are expected to directly interfere with wireless transmissions from the parent mesh station;

program code to determine, for each of the first set of mesh stations, a second set of mesh stations that belong to the ad-hoc mesh network, wherein wireless transmissions from each of the second set of mesh stations are expected to directly interfere with wireless transmissions from the associated mesh station of the first set of mesh stations; and

program code to selectively constrain communications associated with a given mesh station among the first set of mesh stations.

14. A method of operating a mesh station within an ad-hoc mesh network, comprising:

generating an interference list field comprising a list of one or more interfering remote stations;

generating a transmit allocation field comprising one or more allocations for transmission, on a shared medium, by one or more child remote stations;

generating a receive allocation field comprising one or more allocations for receiving, on the shared medium, by the one or more child remote stations; and

forming a message including the interference list field, the transmit allocation field and the receive allocation field.

15. The method of claim 14, wherein the message further comprises a superframe identification field.

16. The method of claim 14, wherein the message further comprises a contention period field.

17. The method of claim 14, wherein the message further comprises a system identification field.

18. A mesh station within an ad-hoc mesh network, comprising:

means for generating an interference list field comprising a list of one or more interfering remote stations;

means for generating a transmit allocation field comprising one or more allocations for transmission, on a shared medium, by one or more child remote stations;

means for generating a receive allocation field comprising one or more allocations for receiving, on the shared medium, by the one or more child remote stations; and

means for forming a message including the interference list field, the transmit allocation field and the receive allocation field.

19. A mesh station within an ad-hoc mesh network, comprising:

logic configured to generate an interference list field comprising a list of one or more interfering remote stations;

logic configured to generate a transmit allocation field comprising one or more allocations for transmission, on a shared medium, by one or more child remote stations;

logic configured to generate a receive allocation field comprising one or more allocations for receiving, on the shared medium, by the one or more child remote stations; and

logic configured to form a message including the interference list field, the transmit allocation field and the receive allocation field.

20. A method of operating a mesh station within an ad-hoc mesh network, comprising:

establishing a superframe; and

transmitting a coordination message to one or more other mesh stations within the ad-hoc mesh network, the first coordination message identifying the superframe and instructing the one or more other mesh stations to transmit and/or receive in accordance with one or more allocations.

21. The method of claim 20, further comprising:

transmitting a beacon signal prior to transmitting the coordination message.

22. The method of claim 20, wherein the mesh station is associated with a first level in a hierarchy of levels in the ad-hoc mesh network and each of the one or more other mesh stations is associated with a second level in the hierarchy of levels in the ad-hoc mesh network, the first level being associated with a highest level indicative of a root level, and the second level being associated with a level lower than the first level.

23. The method of claim 20, wherein the mesh station is a root backhaul mesh station of the ad-hoc mesh network.

24. The method of claim 20, wherein establishing the superframe includes:

transmitting a period for the superframe and a start time for the superframe.

25. A method of operating a mesh station within an ad-hoc mesh network, comprising:

receiving a first coordination message from another mesh station within the ad-hoc mesh network, the first coordination message identifying a superframe and instructing the mesh station to transmit and/or receive in accordance with one or more first allocations; and

transmitting and/or receiving in accordance with the one or more first allocations.

26. The method of claim 25, further comprising:

transmitting a second coordination message, the second coordination message identifying the superframe, and instructing one or more other mesh stations to transmit and/or receive in accordance with one or more second allocations, the one or more second allocations configured to avoid conflicting with the one or more first allocations in the first coordination message.

27. The method of claim 26, wherein each of the one or more other mesh stations is a child to the mesh station.

28. The method of claim 26, wherein conflicting with the one or more first allocations in the first coordination message corresponds to the one or more first allocations and the one or more second allocations being scheduled such that interfering transmissions are in overlapping time periods.

29. A mesh station within an ad-hoc mesh network, comprising:

means for establishing a superframe; and

means for transmitting a coordination message to one or more other mesh stations within the ad-hoc mesh network, the first coordination message identifying the superframe and instructing the one or more other mesh stations to transmit and/or receive in accordance with one or more allocations.

30. A mesh station within an ad-hoc mesh network, comprising:

means for receiving a first coordination message from another mesh station within the ad-hoc mesh network, the first coordination message identifying a superframe and instructing the mesh station to transmit and/or receive in accordance with one or more first allocations; and

means for transmitting and/or receiving in accordance with the one or more first allocations.

31. A mesh station within an ad-hoc mesh network, comprising:

logic configured to establish a superframe; and

logic configured to transmit a coordination message to one or more other mesh stations within the ad-hoc mesh network, the first coordination message identifying the superframe and instructing the one or more other mesh stations to transmit and/or receive in accordance with one or more allocations.

32. A mesh station within an ad-hoc mesh network, comprising:

logic configured to receive a first coordination message from another mesh station within the ad-hoc mesh network, the first coordination message identifying a superframe and instructing the mesh station to transmit and/or receive in accordance with one or more first allocations; and

logic configured to transmit and/or receiving in accordance with the one or more first allocations.

33. A non-transitory computer-readable storage medium containing instructions stored thereon, which, when executed by a mesh station within an ad-hoc mesh network, cause the mesh station to perform operations, the instructions comprising:

program code to establish a superframe; and

program code to transmit a coordination message to one or more other mesh stations within the ad-hoc mesh network, the first coordination message identifying the superframe and instructing the one or more other mesh stations to transmit and/or receive in accordance with one or more allocations.

34. A non-transitory computer-readable storage medium containing instructions stored thereon, which, when executed by a mesh station within an ad-hoc mesh network, cause the mesh station to perform operations, the instructions comprising:

program code to receive a first coordination message from another mesh station within the ad-hoc mesh network, the first coordination message identifying a superframe and instructing the mesh station to transmit and/or receive in accordance with one or more first allocations; and

program code to transmit and/or receiving in accordance with the one or more first allocations.