DISTRIBUTED HIERARCHICAL SCHEDULING IN AN AD HOC NETWORK

• US 20090059855A1
• Filed: 07/28/2008
• Published: 03/05/2009
• Est. Priority Date: 01/29/2004
• Status: Active Grant

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Qualcomm, Inc.
• Inventors: Walton, Jay Rodney, Nanda, Sanjiv
• Granted Patent: US 7,676,236 B2
• Time in Patent Office: Days
• US Class Current: 370/329
• 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. A message, operable for transmission by a mesh station, comprising:

an interference list field comprising a list of interfering remote stations;

a transmit allocation field comprising one or more allocations for transmission by a child remote station on a shared medium; and

a receive allocation field comprising one or more allocations for receiving by a child remote station on a shared medium.

2. The message of claim 1, further comprising a superframe identification field.

3. The message of claim 1, further comprising a contention period field.

4. The message of claim 1, further comprising a system identification field.

5. A mesh network comprising:

a first mesh station for;

establishing a superframe; and

transmitting a first coordination message, the first coordination message identifying the superframe and comprising one or more allocations; and

one or more second mesh stations for;

receiving the first coordination message; and

transmitting or receiving in accordance with the one or more allocations.

6. The mesh network of claim 5, wherein one or more of the second mesh stations further transmits a second coordination message, the second coordination message identifying the superframe, and comprising one or more second allocations, the second allocations determined to avoid conflicting with allocations in the first coordination message.

7. The mesh network of claim 6, further comprising one or more third mesh stations for receiving the second coordination message and for transmitting or receiving in accordance with one or more allocations contained in the second coordination message.