Avoiding mesh path discovery in wireless mesh networks

• US 8,094,637 B1
• Filed: 05/13/2009
• Issued: 01/10/2012
• Est. Priority Date: 12/01/2008
• Status: Active Grant

• Current Assignee: NXP USA, Inc. (NXP Semiconductors NV)
• Original Assignee: Marvell International Limited (Marvell Technology Group Limited)
• Inventors: Goel, Sandesh, Shukla, Ashish Kumar
• Primary Examiner(s): Kizou, Hassan
• Assistant Examiner(s): MAGLO, EMMANUEL K
• Application Number:
  US12/464,958
• Time in Patent Office: 972 Days
• Field of Search: 370/252, 370/253, 370/254, 370/338, 370/351, 370/328, 370/329, 370/238
• US Class Current: 370/338
• CPC Class Codes: H04L 45/122 by minimising distances, e.g. by selecting a route with minimum of number of hops
• CPC Class Codes: H04W 40/12 based on transmission quality or channel quality
• CPC Class Codes: H04W 40/246 Connectivity information discovery

Abstract

Apparatus having corresponding methods comprise: a mesh path module adapted to select a mesh path between a first mesh point in a mesh network and a second mesh point in the mesh network, wherein the mesh path module comprises a neighbor discovery module adapted to determine whether the second mesh point is one hop from the first mesh point, a one-hop mesh path module adapted to select a one-hop mesh path between the first mesh point and the second mesh point when the second mesh point is one hop from the first mesh point, and a multi-hop mesh path module adapted to discover a multi-hop mesh path between the first mesh point and the second mesh point only when it is determined that the second mesh point is not one hop from the first mesh point.

Claims

1. An apparatus configured to operate in a first mesh point, the apparatus comprising:

a memory; and

a mesh path module configured to (i) receive a frame to be transmitted from the first mesh point with destination to a second mesh point, (ii) determine whether a mesh path from the first mesh point to the second mesh point is stored in the memory, and (iii) select a mesh path in a mesh network between the first mesh point and the second mesh point in the mesh network, wherein the mesh path module comprises

a neighbor discovery module configured to determine whether the second mesh point is one hop from the first mesh point (i) when a mesh path between the first mesh point and the second mesh point is not stored in the memory and (ii) prior to mesh discovery for a mesh path between the first mesh point and the second mesh point being performed,

a one-hop mesh path module configured to select a one-hop mesh path between the first mesh point and the second mesh point when (i) the second mesh point is one hop from the first mesh point and (ii) a mesh path between the first mesh point and the second mesh point is not stored in the memory, and

a multi-hop mesh path module configured to discover a multi-hop mesh path between the first mesh point and the second mesh point only when the second mesh point is not one hop from the first mesh point.

2. The apparatus of claim 1, wherein the neighbor discovery module is configured to determine whether the second mesh point is one hop from the first mesh point according to at least one of:

a neighbor discovery protocol;

or

a history of mesh paths found by the mesh path module.

3. The apparatus of claim 1, wherein:

the mesh path module further comprises a path loss module configured to measure a path loss of the one-hop mesh path between the first mesh point and the second mesh point; and

the multi-hop mesh path module is further configured to discover a multi-hop mesh path between the first mesh point and the second mesh point when the path loss of the one-hop mesh path exceeds a predetermined threshold.

4. The apparatus of claim 1, wherein:

the mesh path module further comprises a path loss module configured to measure a one-hop path loss of the multi-hop mesh path between the first mesh point and the second mesh point; and

the one-hop mesh path module is further configured to select a one-hop mesh path between the first mesh point and the second mesh point when the one-hop path loss of the multi-hop mesh path decreases to a value less than a predetermined threshold.

5. The apparatus of claim 1, further comprising a forwarding module configured to forward frames according to an entry for the second mesh point in a forwarding table, wherein:

the frames are (i) received by the first mesh point and (ii) addressed to the second mesh point; and

the mesh path module is further configured to generate the entry for the second mesh point in the forwarding table in order to establish the one-hop mesh path from the first mesh point to the second mesh point.

6. The apparatus of claim 5, further comprising a path lifetime module configured to determine when a path lifetime ends for the entry,

wherein the neighbor discovery module is further configured to determine whether the second mesh point is one hop from the first mesh point in response to the path lifetime for the entry ending.

7. A wireless device comprising the first mesh point of claim 1.

8. The apparatus of claim 1, wherein:

the neighbor discovery module is configured to determine whether the second mesh point is one hop from the first mesh point using at least one of neighborhood discovery or path histories; and

the multi-hop mesh path module is configured to discover a multi-hop mesh path between the first mesh point and the second mesh point using multi-point mesh discovery.

9. The apparatus of claim 1, further comprising a media access device, wherein the media access device comprises:

the mesh path module; and

a forwarding module comprising the memory.

10. The apparatus of claim 5, wherein the neighbor discovery module is further configured to determine whether the second mesh point is one hop from the first mesh point when (i) the first mesh point receives one of the frames addressed to the second mesh point and (ii) no entry for the second mesh point exists in the forwarding table.

11. The apparatus of claim 8, wherein when using neighborhood discovery, the neighbor discovery module is configured to determine whether the second mesh point is one hop from the first mesh point based on received beacons and probe responses.

12. A method for finding a mesh path between a first mesh point in a mesh network and a second mesh point in the mesh network, the method comprising:

at the first mesh point

receiving a frame to be transmitted from the first mesh point with destination to the second mesh point,

determining whether a mesh path from the first mesh point to the second mesh point is stored in a memory,

determining whether the second mesh point is one hop from the first mesh point (i) when a mesh path between the first mesh point and the second mesh point is not stored in the memory and (ii) prior to mesh discovery for a mesh path between the first mesh point and the second mesh point being performed,

establishing a one-hop mesh path between the first mesh point and the second mesh point when (i) the second mesh point is one hop from the first mesh point and (ii) a mesh path between the first mesh point and the second mesh point is not stored in the memory, and

discovering a multi-hop mesh path between the first mesh point and the second mesh point only when the second mesh point is not one hop from the first mesh point.

13. The method of claim 12, further comprising determining whether the second mesh point is one hop from the first mesh point according to at least one of:

a neighbor discovery protocol; and

a history of mesh paths found by the method.

14. The method of claim 12, further comprising:

measuring a path loss of the one-hop mesh path between the first mesh point and the second mesh point; and

discovering a multi-hop mesh path between the first mesh point and the second mesh point when the path loss of the one-hop mesh path exceeds a predetermined threshold.

15. The method of claim 12, further comprising:

measuring a one-hop path loss of the multi-hop mesh path between the first mesh point and the second mesh point; and

selecting a one-hop mesh path between the first mesh point and the second mesh point when the one-hop path loss of the multi-hop mesh path decreases to a value less than a predetermined threshold.

16. The method of claim 12, further comprising forwarding frames received by the first mesh point and addressed to the second mesh point according to an entry for the second mesh point in a forwarding table,

wherein establishing the one-hop mesh path between the first mesh point and the second mesh point comprises generating the entry for the second mesh point in the forwarding table.

17. The method of claim 16, further comprising:

determining when a path lifetime ends for the entry; and

determining when the second mesh point is one hop from the first mesh point in response to the path lifetime for the entry ending.

18. The method of claim 16, further comprising determining whether the second mesh point is one hop from the first mesh point when (i) the first mesh point receives one of the frames addressed to the second mesh point and (ii) no entry for the second mesh point exists in the forwarding table.