DISTRIBUTED HIERARCHICAL SCHEDULING IN AN AD HOC NETWORK
First Claim
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.
1 Assignment
0 Petitions
Accused Products
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.
151 Citations
34 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10)
-
-
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. - View Dependent Claims (15, 16, 17)
-
-
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. - View Dependent Claims (21, 22, 23, 24)
-
-
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. - View Dependent Claims (26, 27, 28)
-
-
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.
-
Specification