Mechanism for automatic network formation and medium access coordination

• US 9,247,580 B2
• Filed: 03/12/2013
• Issued: 01/26/2016
• Est. Priority Date: 01/18/2007
• Status: Active Grant

• Current Assignee: Leidos, Inc. (Leidos Holdings, Inc.)
• Original Assignee: Leidos, Inc. (Leidos Holdings, Inc.)
• Inventors: Cheng, Ana M., Riviere, Norbert J.
• Primary Examiner(s): AJIBADE AKONAI, OLUMIDE
• Application Number:
  US13/795,725
• Publication Number:
  US 20130188524A1
• Time in Patent Office: 1,050 Days
• Field of Search: 455/434, 455/450, 455/515, 455/41.2, 455/69, 370/310, 370/328, 370/329, 370/330, 370/338, 370/431, 370/252, 370/254
• US Class Current: 1/1
• 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 comprising:

randomly selecting to transmit based on a randomized choice between transmitting and receiving;

transmitting a link establishment request from a node in response to the selection to transmit;

receiving a link establishment response at the node; and

updating a steady-state schedule of the node for communication in a mesh network.

2. The method of claim 1, further comprising pointing a directional antenna to a bearing based on a function shared with other nodes of the mesh network, wherein the transmitting is from the directional antenna.

3. The method of claim 2, further comprising determining the bearing based on a time of day.

4. The method of claim 1, wherein the link establishment request transmitted by the node identifies future available response frames.

5. The method of claim 1, further comprising:

in response to the receiving of the link establishment response, transmitting a bandwidth allocation response which reserves particular frames of the steady-state schedule from among unreserved idle frames for steady-state communication with a second node.

6. The method of claim 1, wherein the steady-state schedule indicates reserved communication opportunities of the node, and wherein the updating of the steady-state schedule is based on communication links between the node and other neighboring nodes in the mesh network and based on the link establishment response.

7. A method comprising:

pointing a directional antenna of a node to a bearing synchronized with one or more other bearings of one or more other nodes of a mesh network;

transmitting a link establishment request from the directional antenna;

receiving a link establishment response; and

updating a steady-state schedule of the node for communication in the mesh network.

8. The method of claim 7, further comprising:

selecting the bearing based on a time reference shared with the one or more other nodes of the mesh network.

9. The method of claim 7, wherein the steady-state schedule indicates reserved communication opportunities of the node, and wherein the updating of the steady-state schedule is based on communication links between the node and neighboring nodes in the mesh network and based on the link establishment response.

10. A method comprising:

determining a bearing;

randomly selecting, based on a randomized choice, between transmitting from a node and receiving at the node a communication to establish a link in a mesh network with one or more other nodes;

if transmitting the communication is selected, then transmitting the communication from a directional antenna of the node in a direction of the bearing; and

if receiving the communication is selected, then listening by the node for the communication from the one or more other nodes.

11. The method of claim 10, further comprising:

determining a time for the transmitting or the receiving of the communication, wherein the bearing is the same for the node and the one or more other nodes at the determined time.

12. The method of claim 11, further comprising:

updating the bearing to a new bearing according to a predetermined scan order.

13. The method of claim 12, wherein the predetermined scan order for updating the bearing depends on a time of day.

14. A non-transitory computer-readable medium having computer-executable instructions stored thereon, that when executed by a processor, cause an apparatus containing the processor to:

randomly select to transmit based on a randomized choice between transmitting and receiving;

transmit a link establishment request from the apparatus in response to the selection to transmit;

receive a link establishment response at the apparatus; and

update a steady-state schedule of the apparatus for communication with one or more nodes in a mesh network.

15. The non-transitory computer-readable medium of claim 14, wherein the computer-executable instructions, when executed by the processor, further cause the apparatus to:

point a directional antenna to a bearing based on a function shared with the one or more nodes in the mesh network, wherein the transmitting is from the directional antenna.

16. The non-transitory computer-readable medium of claim 14, wherein the link establishment request transmitted by the apparatus identifies future available response frames.

17. The non-transitory computer-readable medium of claim 14, wherein the computer-executable instructions, when executed by the processor, further cause the apparatus to:

in response to receiving the link establishment response, transmit a bandwidth allocation response which reserves particular frames of the steady-state schedule from among unreserved idle frames for steady-state communication with one of the one or more nodes.

18. The non-transitory computer-readable medium of claim 14, wherein the steady-state schedule indicates reserved communication opportunities of the apparatus, and wherein the updating of the steady-state schedule is based on communication links between the apparatus and neighboring nodes in the mesh network and based on the link establishment response.

19. An apparatus comprising:

one or more antennae;

a processor; and

one or more memory having computer-executable instructions stored thereon, that when executed by the processor, cause the apparatus to;

randomly select to transmit based on a randomized choice between transmitting and receiving;

transmit a link establishment request from the one or more antennae in response to the selection to transmit;

receive a link establishment response on the one or more antennae; and

update a steady-state schedule of the apparatus for communication in a mesh network.

20. The apparatus of claim 19, wherein the one or more antennae provide sectorized reception.