Cumulative route metrics for wireless mesh network routing

• US 9,479,428 B2
• Filed: 05/23/2014
• Issued: 10/25/2016
• Est. Priority Date: 04/24/2006
• Status: Active Grant

• Current Assignee: Marvell Asia Pte Limited (Marvell Technology Group Limited)
• Original Assignee: Marvell World Trade Limited (Marvell Technology Group Limited)
• Inventors: Banerjea, Raja, Goel, Sandesh
• Primary Examiner(s): MEHRA, INDER P
• Application Number:
  US14/286,320
• Publication Number:
  US 20140269393A1
• Time in Patent Office: 886 Days
• Field of Search: 455/115.1, 455/127.1, 455/83, 455/450, 455/41.2, 455/426.2, 455/445, 370/252, 370/254, 370/338, 370/235, 370/255, 370/331, 370/351, 370/356
• US Class Current: 1/1
• CPC Class Codes: H04L 45/26 Route discovery packet
• CPC Class Codes: H04L 45/54 Organization of routing tables
• CPC Class Codes: H04W 40/10 based on available power or energy
• CPC Class Codes: H04W 40/246 Connectivity information discovery
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks
• CPC Class Codes: Y02D 30/70 in wireless communication networks

Abstract

A wireless network device includes a physical layer module configured to send and receive packets wirelessly. The wireless network device includes a mesh routing module configured to receive a first packet from a second wireless network device via the physical layer module. The first packet includes a metric and a source address. The mesh routing module is further configured to determine a cumulative metric based on (i) the metric from the first packet and (ii) a link metric. The mesh routing module is further configured to transmit a second packet to a third wireless network device via the physical layer module. The second packet includes the cumulative metric. The mesh routing module is further configured to determine the link metric based on (i) a state of charge of a power supply of the wireless network device and (ii) a transmission parameter of the second packet.

Claims

1. A wireless network device comprising:

a physical layer module configured to send and receive packets wirelessly; and

a mesh routing module configured to

receive a first packet from a second wireless network device via the physical layer module, wherein the first packet includes a metric and a source address,

determine a cumulative metric based on (i) the metric from the first packet and (ii) a link metric,

transmit a second packet to a third wireless network device via the physical layer module, wherein the second packet includes the cumulative metric, and

determine the link metric based on (i) a state of charge of a power supply of the wireless network device and (ii) a transmission parameter of the second packet.

2. The wireless network device of claim 1, wherein the power supply comprises a battery.

3. The wireless network device of claim 1, wherein the link metric increases as the state of charge decreases.

4. The wireless network device of claim 1, wherein the transmission parameter comprises energy used to transmit the second packet.

5. The wireless network device of claim 4, wherein the link metric is (i) proportional to the energy used and (ii) inversely related to the state of charge.

6. The wireless network device of claim 4, wherein:

the mesh routing module is configured to successively transmit the second packet using increasing amounts of energy; and

the cumulative metric is updated for each successive transmission to reflect the increasing amounts of energy.

7. The wireless network device of claim 1, further comprising a forwarding table configured to store entries, wherein:

each of the entries includes a destination address, a next hop address, and a metric;

the entries include direct entries and reverse entries;

each of the direct entries includes a metric corresponding to a direct route, the direct route being from the wireless network device to the destination address; and

each of the reverse entries includes a metric corresponding to a reverse route, the reverse route being from the destination address to the wireless network device.

8. The wireless network device of claim 7, wherein:

the mesh routing module creates a first reverse entry in the forwarding table based on the first packet;

the next hop address of the first reverse entry is set to an address of the second wireless network device;

the destination address of the first reverse entry is set to the source address of the first packet; and

the metric of the first reverse entry is set to the metric of the first packet.

9. The wireless network device of claim 7, wherein the mesh routing module is configured to:

receive a route reply packet via the physical layer module, wherein the route reply packet includes a reply destination address;

identify ones of the reverse entries that correspond to the reply destination address; and

transmit the route reply packet to the next hop address of a selected one of the identified reverse entries.

10. The wireless network device of claim 9, wherein the mesh routing module is configured to select the selected one of the identified reverse entries based on the stored metrics of the identified reverse entries.

11. The wireless network device of claim 9, wherein each of the reverse entries includes a sequence number associated with the destination address.

12. The wireless network device of claim 11, wherein:

the route reply packet includes a reply sequence number;

the mesh routing module is configured to choose ones of the identified reverse entries having the reply sequence number; and

the mesh routing module is configured to select one of the chosen reverse entries based on the stored metrics of the chosen reverse entries.

13. The wireless network device of claim 7, wherein the mesh routing module is configured to:

receive a route request for a requested destination address;

identify ones of the direct entries having the requested destination address; and

respond to the route request with the next hop address of a selected one of the identified direct entries.

14. The wireless network device of claim 13, wherein the mesh routing module is configured to select the selected one of the identified direct entries based on the metrics of the identified direct entries.

15. The wireless network device of claim 13, wherein:

each of the direct entries of the forwarding table includes an expiration indicator; and

the mesh routing module is configured to select the selected one of the identified direct entries based on the expiration indicators of the identified direct entries.

16. A method of operating a wireless network device, the method comprising:

sending and receiving packets wirelessly, including receiving a first packet from a second wireless network device, wherein the first packet includes a metric and a source address;

determining a cumulative metric based on (i) the metric from the first packet and (ii) a link metric;

transmitting a second packet to a third wireless network device, wherein the second packet includes the cumulative metric; and

determining the link metric based on (i) a state of charge of a power supply of the wireless network device and (ii) a transmission parameter of the second packet.

17. The method of claim 16, wherein the power supply comprises a battery.

18. The method of claim 16, wherein the link metric increases as the state of charge decreases.

19. The method of claim 16, wherein the transmission parameter comprises energy used to transmit the second packet.

20. The method of claim 19, wherein the link metric is (i) proportional to the energy used and (ii) inversely related to the state of charge.

21. The method of claim 19, further comprising:

successively transmitting the second packet using increasing amounts of energy; and

updating the cumulative metric for each successive transmission to reflect the increasing amounts of energy.

22. The method of claim 16, further comprising storing entries in a forwarding table, wherein:

each of the entries includes a destination address, a next hop address, and a metric;

the entries include direct entries and reverse entries;

each of the direct entries includes a metric corresponding to a direct route, the direct route being from the wireless network device to the destination address; and

each of the reverse entries includes a metric corresponding to a reverse route, the reverse route being from the destination address to the wireless network device.

23. The method of claim 22, further comprising creating a first reverse entry in the forwarding table based on the first packet, wherein:

the next hop address of the first reverse entry is set to an address of the second wireless network device;

the destination address of the first reverse entry is s to the source address of the first packet; and

the metric of the first reverse entry is set to the metric of the first packet.

24. The method of claim 22, further comprising:

receiving a route reply packet including a reply destination address;

identifying ones of the reverse entries that correspond to the reply destination address; and

transmitting the route reply packet to the next hop address of a selected one of the identified reverse entries.

25. The method of claim 24, further comprising selecting the selected one of the identified reverse entries based on the stored metrics of the identified reverse entries.

26. The method of claim 24, wherein each of the reverse entries includes a sequence number associated with the destination address.

27. The method of claim 26, wherein:

the route reply packet includes a reply sequence number; and

the method further comprises (i) choosing ones of the identified reverse entries having the reply sequence number, and (ii) selecting one of the chosen reverse entries based on the stored metrics of the chosen reverse entries.

28. The method of claim 22, further comprising:

receiving a route request for a requested destination address;

identifying ones of the direct entries having the requested destination address; and

responding to the route request with the next hop address of a selected one of the identified direct entries.

29. The method of claim 28, further comprising selecting the selected one of the identified direct entries based on the metrics of the identified direct entries.

30. The method of claim 28, wherein:

each of the direct entries of the forwarding table includes an expiration indicator; and

the method further comprises selecting the selected one of the identified direct entries based on the expiration indicators of the identified direct entries.