802.11 MESH ARCHITECTURE

• US 20070248065A1
• Filed: 04/17/2007
• Published: 10/25/2007
• 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: Goel, Sandesh, Banerjea, Raja
• Granted Patent: US 8,738,013 B2
• Time in Patent Office: Days
• US Class Current: 370/338
• 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 comprises a forwarding table and a mesh routing module. The forwarding table stores direct and reverse entries, each including a destination address, a next hop address, and a metric. The metric of the direct entries corresponds to a route from the wireless network device to the destination address. The metric of the reverse entries corresponds to a route from the destination address to the wireless network device. The mesh routing module wirelessly receives route discovery packets and creates corresponding entries in the forwarding table.

Claims

1. A wireless network device comprising:

a forwarding table that stores direct and reverse entries each including a destination address, a next hop address, and a metric, wherein said metric of said direct entries corresponds to a route from said wireless network device to said destination address, and wherein said metric of said reverse entries corresponds to a route from said destination address to said wireless network device; and

a mesh routing module that wirelessly receives route discovery packets and that creates corresponding entries in said forwarding table.

2. The wireless network device of claim 1 wherein said mesh routing module wirelessly receives a first route discovery packet including a metric and a source address from a second wireless network device and creates a reverse entry in said forwarding table, wherein said next hop address of said reverse entry is set to an address of said second wireless network device, said destination address of said reverse entry is set to said source address of said first route discovery packet, and said metric of said reverse entry is set to said metric of said first route discovery packet.

3. The wireless network device of claim 2 wherein said mesh routing module wirelessly receives a route reply packet including a reply destination address, identifies ones of said reverse entries that have said reply destination address, and transmits said route reply packet to said next hop address of a selected one of said identified reverse entries.

4. The wireless network device of claim 3 wherein said mesh routing module selects said selected one of said identified reverse entries based upon said metrics of said identified reverse entries.

5. The wireless network device of claim 3 wherein said reverse entries each include a sequence number, and wherein said mesh routing module sets said sequence number of said reverse entry to a sequence number received in said first route discovery packet.

6. The wireless network device of claim 5 wherein said route reply packet includes a reply sequence number, and wherein said mesh routing module chooses ones of said identified reverse entries that have said reply sequence number and selects one of said chosen reverse entries based upon said metrics of said chosen reverse entries.

7. The wireless network device of claim 1 wherein said mesh routing module receives a route request for a requested destination address, identifies ones of said direct entries that have said requested destination address, and selectively responds to said route request with said next hop address of a selected one of said identified direct entries.

8. The wireless network device of claim 7 wherein said mesh routing module selects said selected one of said identified direct entries based upon said metrics of said identified direct entries.

9. The wireless network device of claim 7 wherein said direct entries of said forwarding table include an expiration indicator, and wherein said mesh routing module selects said selected one of said identified direct entries based upon said expiration indicators of said identified direct entries.

10. The wireless network device of claim 1 wherein said mesh routing module transmits a route discovery packet including a cumulative metric to a second wireless network device, determines said cumulative metric based upon a received metric and a link metric, and determines said link metric based upon a state of charge of said wireless network device and a transmission parameter of said route discovery packet.

11. The wireless network device of claim 10 wherein said link metric increases as said state of charge decreases.

12. The wireless network device of claim 10 wherein said transmission parameter comprises energy used to transmit said route discovery packet.

13. The wireless network device of claim 12 wherein said link metric is proportional to said energy used and inversely related to said state of charge.

14. The wireless network device of claim 12 wherein said mesh routing module transmits said route discovery packet using increasing amounts of energy.

15. A method for a wireless network device, comprising:

wirelessly receiving route discovery packets; and

storing direct and reverse entries in a forwarding table based upon said route discovery packets, each of said entries including a destination address, a next hop address, and a metric, wherein said metric of said direct entries corresponds to a route from said wireless network device to said destination address, and wherein said metric of said reverse entries corresponds to a route from said destination address to said wireless network device.

16. The method of claim 15 further comprising:

receiving a first route discovery packet including a metric and a source address from a first wireless network device; and

creating a reverse entry in said forwarding table, wherein said next hop address of said reverse entry is set to an address of said first wireless network device, said destination address of said reverse entry is set to said source address of said first route discovery packet, and said metric of said reverse entry is set to said metric of said first route discovery packet.

17. The method of claim 16 further comprising:

receiving a route reply packet including a reply destination address wirelessly;

identifying ones of said reverse entries that have said reply destination address; and

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

18. The method of claim 17 wherein said selected one of said identified reverse entries is selected based upon said metrics of said identified reverse entries.

19. The method of claim 17 wherein said reverse entries each include a sequence number, and further comprising setting said sequence number of said reverse entry to a sequence number received in said first route discovery packet.

20. The method of claim 19 wherein said route reply packet includes a reply sequence number, and further comprising:

choosing ones of said identified reverse entries that have said reply sequence number; and

selecting one of said chosen reverse entries based upon said metrics of said chosen reverse entries.

21. The method of claim 15 further comprising:

receiving a route request for a requested destination address;

identifying ones of said direct entries that have said requested destination address; and

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

22. The method of claim 21 wherein said selected one of said identified direct entries is selected based upon said metrics of said identified direct entries.

23. The method of claim 21 wherein said direct entries of said forwarding table include an expiration indicator, and wherein said selected one of said identified direct entries is selected based upon said expiration indicators of said identified direct entries.

24. The method of claim 15 further comprising:

receiving a first route discovery packet including a metric;

determining a link metric based upon a state of charge of said wireless network device and a transmission parameter of a second route discovery packet;

determining a cumulative metric based upon a received metric and said link metric; and

transmitting said second route discovery packet wirelessly to a first wireless network device, said second route discovery packet including said cumulative metric.

25. The method of claim 24 wherein said link metric increases as said state of charge decreases.

26. The method of claim 24 wherein said transmission parameter comprises energy used to transmit said second route discovery packet.

27. The method of claim 26 wherein said link metric is proportional to said energy used and inversely related to said state of charge.

28. The method of claim 26 further comprising transmitting said second route discovery packet using increasing amounts of energy.