Neighbor location discovery with directional antennas in a mesh network

• US 20060215624A1
• Filed: 03/28/2005
• Published: 09/28/2006
• Est. Priority Date: 03/28/2005
• Status: Active Grant

• Current Assignee: Zhigu Holdings Limited
• Original Assignee: Microsoft Corporation
• Inventors: Bahl, Paramvir, Adya, Atul, Padhye, Jitendra D., Wolman, Alastair
• Granted Patent: US 7,664,054 B2
• Time in Patent Office: Days
• US Class Current: 370/338
• CPC Class Codes: H04W 8/005 Discovery of network devices, e.g. terminals
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks

Abstract

Disclosed is a Neighbor Location Discovery Protocol (NLDP) that determines the relative locations of the nodes in a mesh network. In one embodiment, NLDP can be implemented for an ad-hoc wireless network where the nodes are equipped with directional antennas and are not able to use GPS. While NLDP relies on nodes having at least two RF transceivers, it offers significant advantages over previously proposed protocols that employ only one RF transceiver. In NLDP antenna hardware is simple, easy to implement, and readily available. Further, NLDP exploits the host node'"'"'s ability to operate simultaneously over non-overlapping channels to quickly converge on the neighbor'"'"'s location. NLDP is limited by the range of the control channel, which operates in a omni-directional fashion. However, by choosing a low frequency band, high power, and low data rate, the range of the control channel can be increased to match the range on the data channel.

Claims

1. A method for discovering relative neighbor locations in a mesh network, the method comprising:

joining the mesh network by a new network node;

broadcasting, over a control channel, a general discovery request message by the new network node;

receiving the general discovery request message at a second network node in the mesh network;

replying to the general discovery request message broadcasted by the new node by sending an acknowledgement message from the second network node to the new network node over the control channel;

receiving the acknowledgement message at the new network node and creating a corresponding entry in a neighbor location table;

broadcasting, over a data channel via the data channel'"'"'s antenna, a directional general discovery request message by the new node, in a direction corresponding to a current direction of the antenna;

receiving the directional general discovery request message at the second network node;

replying to the directional general discovery request message broadcasted by the new node by sending a second acknowledgement message from the second network node to the new network node over the control channel; and

receiving the second acknowledgement message at the new network node and updating the corresponding entry in the neighbor location table.

2. The method of claim 1 further comprising:

waiting, by the new node, for a period of time after broadcasting the general discovery request message; and

re-broadcasting, over the control channel, the general discovery request message by the new network node if no acknowledgement messages are received at the new node during the period of time.

3. The method of claim 2 further comprising repeating the waiting and the re-broadcasting for a specified number of iterations before terminating the discovery of relative neighbor locations.

4. The method of claim 2 further comprising discarding, by the new node, any acknowledgement messages having a sequence number matching a sequence number of an earlier general discovery request message received by the new node after the waiting.

5. The method of claim 1 further comprising:

waiting, by the new node, for a period of time after broadcasting the directional general discovery request message;

steering the antenna to a next direction;

incrementing a sequence number of the directional general discovery request message;

broadcasting, over the data channel via the data channel'"'"'s antenna, a directional general discovery request message by the new node, in a direction corresponding to the current direction of the antenna;

receiving the directional general discovery request message at the second network node;

replying to the directional general discovery request message broadcasted by the new node by sending a second acknowledgement message from the second network node to the new network node over the control channel; and

receiving the second acknowledgement message at the new network node and updating the corresponding entry in the neighbor location table.

6. The method of claim 5 wherein the waiting, by the new node, for a period of time after broadcasting the directional general discovery request message, the steering the antenna to the next direction, the incrementing a sequence number of the directional general discovery request message, the broadcasting, over the data channel via the data channel'"'"'s antenna, a directional general discovery request message by the new node, in a direction corresponding to the current direction of the antenna, the receiving the directional general discovery request message at the second network node, the replying to the directional general discovery request message broadcasted by the new node by sending a second acknowledgement message from the second network node to the new network node over the control channel, and the receiving the second acknowledgement message at the new network node and updating the corresponding entry in the neighbor location table is repeated until a complete rotation of the antenna is achieved.

7. The method of claim 1 further comprising:

checking a neighbor location table on the second network node for an entry corresponding to the new network node;

creating an entry corresponding to the new network node in the second network node'"'"'s neighbor location table if an entry corresponding to the new network node does not exist;

waiting until there is a lull in traffic between the new network node and the second network node;

sending, by the second network node, a targeted discovery request message on the control channel to the new network node;

sending, by the second network node, a directional targeted discovery request message on the data channel to the new network node if transmission of the targeted discovery request is successful;

receiving the directional targeted discovery request message at the new network node;

replying to the directional targeted discovery request message sent by the second node by sending an acknowledgement message from the new network node to the second network node over the control channel; and

receiving the acknowledgement message at the second network node and updating the corresponding entry in the neighbor location table.

8. The method of claim 1 wherein the neighbor location table contains an entry for each neighbor discovered comprising a direction antenna pattern for the neighbor.

9. A computer-readable medium having computer-executable instructions for performing the steps recited in claim 1.

10. A method for discovering relative neighbor locations in a mesh network, the method comprising:

joining the mesh network by a new network node;

broadcasting, over a control channel, a general discovery request message by the new network node;

receiving the general discovery request message at a second network node in the mesh network;

replying to the general discovery request message broadcasted by the new node by sending an acknowledgement message from the second network node to the new network node over the control channel;

receiving the acknowledgement message at the new network node and creating a corresponding entry in a neighbor location table;

broadcasting, over a data channel via the data channel'"'"'s antenna, a directional general discovery request message by the new node, in a direction corresponding to a current direction of the antenna;

receiving the directional general discovery request message at the second network node;

holding an antenna direction constant at the second network node until a round completion message is received at the second network node from the new network node;

replying to the directional general discovery request message broadcasted by the new node by sending a second acknowledgement message from the second network node to the new network node over the control channel; and

receiving the second acknowledgement message at the new network node and updating the corresponding entry in the neighbor location table.

11. The method of claim 10 further comprising:

waiting, by the new node, for a period of time after broadcasting the general discovery request message; and

re-broadcasting, over the control channel, the general discovery request message by the new network node if no acknowledgement messages are received at the new node during the period of time.

12. The method of claim 11 further comprising repeating the waiting and the re-broadcasting for a specified number of iterations before terminating the discovery of relative neighbor locations.

13. The method of claim 11 further comprising discarding, by the new node, any acknowledgement messages having a sequence number matching a sequence number of an earlier general discovery request message received by the new node after the waiting.

14. The method of claim 10 further comprising:

waiting, by the new node, for a period of time after broadcasting the directional general discovery request message;

steering the antenna to a next direction;

incrementing a sequence number of the directional general discovery request message;

broadcasting, over the data channel via the data channel'"'"'s antenna, a directional general discovery request message by the new node, in a direction corresponding to the current direction of the antenna;

receiving the directional general discovery request message at the second network node;

replying to the directional general discovery request message broadcasted by the new node by sending a second acknowledgement message from the second network node to the new network node over the control channel; and

receiving the second acknowledgement message at the new network node and updating the corresponding entry in the neighbor location table.

15. The method of claim 14 wherein the waiting, by the new node, for a period of time after broadcasting the directional general discovery request message, the steering the antenna to the next direction, the incrementing a sequence number of the directional general discovery request message, the broadcasting, over the data channel via the data channel'"'"'s antenna, a directional general discovery request message by the new node, in a direction corresponding to the current direction of the antenna, the receiving the directional general discovery request message at the second network node, the replying to the directional general discovery request message broadcasted by the new node by sending a second acknowledgement message from the second network node to the new network node over the control channel, and the receiving the second acknowledgement message at the new network node and updating the corresponding entry in the neighbor location table is repeated until a complete rotation of the antenna is achieved.

16. The method of claim 10 further comprising:

checking a neighbor location table on the second network node for an entry corresponding to the new network node;

creating an entry corresponding to the new network node in the second network node'"'"'s neighbor location table if an entry corresponding to the new network node does not exist;

waiting until there is a lull in traffic between the new network node and the second network node;

sending, by the second network node, a targeted discovery request message on the control channel to the new network node;

sending, by the second network node, a directional targeted discovery request message on the data channel to the new network node if transmission of the targeted discovery request is successful;

receiving the directional targeted discovery request message at the new network node;

replying to the directional targeted discovery request message sent by the second node by sending an acknowledgement message from the new network node to the second network node over the control channel; and

receiving the acknowledgement message at the second network node and updating the corresponding entry in the neighbor location table.

17. The method of claim 10 wherein the neighbor location table contains an entry for each neighbor discovered comprising a send direction antenna pattern for the neighbor and a receive direction antenna pattern for the neighbor.

18. A computer-readable medium having computer-executable instructions for performing the steps recited in claim 10.