Mechanism for Automatic Network Formation and Medium Access Coordination

• US 20080198829A1
• Filed: 01/18/2007
• Published: 08/21/2008
• Est. Priority Date: 01/18/2007
• Status: Active Grant

• Current Assignee: Leidos, Inc. (Leidos Holdings, Inc.)
• Original Assignee: Science Applications International Corporation
• Inventors: Cheng, Ana M., Riviere, Norbert J.
• Granted Patent: US 8,045,505 B2
• Time in Patent Office: Days
• US Class Current: 370/342
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies
• CPC Class Codes: H04W 72/044 based on the type of the allocated resource
• CPC Class Codes: H04W 72/0446 Resources in time domain, e.g. slots or frames
• CPC Class Codes: H04W 72/046 the resource being in the space domain, e.g. beams
• CPC Class Codes: H04W 72/52 based on load
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks

Abstract

The invention provides a set of mechanisms by which a wireless mobile mesh node equipped with a directional antenna may self form and self adapt its steady-state communications schedule. A link establishment handshake is carried out over an ongoing subtemplate-based discovery scan. During time not reserved for steady-state communications with previously discovered neighbors, nodes continue to search for an establish links with new neighbors. Initial and subsequent bandwidth allocation protocols may be utilized to allow peer nodes to coordinate communication opportunities between the peer nodes without impacting or having knowledge about reservations for communications with other peers. The link establishment and initial bandwidth allocation protocols may be piggy-backed for readily establishing an initial steady-state schedule with a peer upon link establishment without impact on previous steady state reservations by other nodes or on ongoing link establishment attempts elsewhere.

Claims

1. A method for achieving a self-forming directional mobile mesh network, the method comprising:

(a) randomly selecting transmission by a node;

(b) pointing a directional antenna of the node;

(c) transmitting a link establishment request from the node;

(d) receiving a link establishment receipt; and

(e) updating a steady-state schedule of the node.

2. The method of claim 1, wherein the pointing the directional antenna of the node is based on a function of frame of day.

3. The method of claim 1, wherein the link establishment request transmitted by the node identifies future reception frames.

4. The method of claim 1, wherein step (d) further includes receiving a bandwidth allocation request.

5. The method of claim 4, wherein the bandwidth allocation request is piggy-backed onto the link establishment response.

6. The method of claim 1, wherein the steady-state schedule for all nodes comprise a fixed length schedule.

7. The method of claim 6, wherein the fixed length schedule comprises a balanced interleaved schedule.

8. The method of claim 1, wherein the link establishment response is received from a second node.

9. The method of claim 8, wherein third and fourth nodes are simultaneously communicating with each other during steps (a) through (e).

10. The method of claim 1 further including

(f) monitoring link loads;

and

(g) adjusting bandwidth allocations based on the monitored link loads.

11. A method of forming a directional mobile mesh network, the method comprising:

(a) randomly selecting reception by a node;

(b) receiving a link establishment request through an omni-directional antenna of the node;

(c) transmitting a link establishment response; and

(d) updating a steady-state schedule of the node.

12. The method of claim 11, wherein the link establishment response includes future reception frames.

13. The method of claim 11, wherein step (c) further includes transmitting an initial bandwidth allocation.

14. The method of claim 13, wherein the initial bandwidth allocation request is piggy-backed onto the link establishment response.

15. The method of claim 11, wherein the steady-state schedule comprises a fixed length schedule.

16. The method of claim 15, wherein the fixed length schedule comprises a balanced interleaved schedule.

17. The method of claim 11, wherein the link establishment response is received from a second node.

18. The method of claim 17, wherein other nodes are simultaneously communicating with each other during steps (a) through (d).

19. The method of claim 11 further including:

(e) monitoring link loads; and

(f) adjusting bandwidth allocations based on the monitored link loads.

20. A computer-readable medium having computer-executable instructions for performing steps comprising:

(a) randomly selecting transmission by a node;

(b) pointing a directional antenna of the node;

(c) transmitting a link establishment request from the node;

(d) receiving a link establishment response; and

(e) updating steady-state schedules of the node.

21. The computer-readable medium of claim 20, wherein step (d) further includes receiving an initial bandwidth allocation request.

22. The computer-readable medium of claim 20, wherein the initial bandwidth allocation request is piggy-backed with the link establishment receipt.

23. The computer-readable medium of claim 20, wherein the steady-state schedules for the node comprise a fixed length schedule.

24. The computer-readable medium of claim 20 further including

(f) monitoring link loads;

and

(g) adjusting bandwidth allocations based on the monitored link loads.

25. A node comprising:

a directional antenna;

storage medium; and

a processor coupled to the storage medium and programmed with computer-executable instructions to perform the steps comprising;

(a) randomly selecting transmission by a node;

(b) pointing the directional antenna of the node;

(c) transmitting a link establishment request from the node;

(d) receiving a link establishment response; and

(e) updating steady-state schedules of the node.

26. The node of claim 25, wherein the directional antenna provides sectorized reception.

27. The node of claim 25, further including an omni directional antenna.

28. The method of claim 25, wherein step (d) further includes receiving a bandwidth allocation request.

29. The method of claim 28, wherein the bandwidth allocation request is piggy-backed onto the link establishment response.

30. The method of claim 25 further including

(f) monitoring link loads;

and

(g) adjusting bandwidth allocations based on the monitored link loads.