Path selection and power management in mesh networks

• US 8,014,329 B2
• Filed: 12/14/2007
• Issued: 09/06/2011
• Est. Priority Date: 07/03/2007
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Gong, Xiaohong
• Primary Examiner(s): Moore; Ian N
• Assistant Examiner(s): Huynh; Dung B
• Application Number:
  US11/956,750
• Publication Number:
  US 20090010190A1
• Time in Patent Office: 1,362 Days
• Field of Search: 370/311
• US Class Current: 370/311
• CPC Class Codes: H04L 45/26 Route discovery packet
• CPC Class Codes: H04W 40/005 Routing actions in the presence of nodes in sleep or doze mode
• CPC Class Codes: H04W 40/22 using selective relaying for reaching a BTS [Base Transceiver Station] or an access point
• CPC Class Codes: Y02D 30/70 in wireless communication networks

Abstract

A two-phased path selection process for wireless mesh networks that promotes stability and power management. If, during a first route discovery phase, a route cannot be found without waking up battery-powered nodes in a wireless mesh network, the source node will wake up battery-powered nodes in the mesh during a second route discovery phase.

Claims

1. A method performed by an apparatus comprising:

maintaining power state information for one or more neighboring wireless mesh nodes,

wherein the power state information for each of the neighboring wireless mesh nodes comprises whether the wireless mesh node is a battery-powered device, whether the wireless mesh node is in a power save state, and whether the wireless mesh node is in a critical battery state;

receiving a path request message from a first wireless mesh node, wherein the path request message identifies a source node and a destination node;

propagating the path request message to selected ones of the one or more neighboring wireless mesh nodes based on the power state information corresponding to the one or more neighboring wireless mesh nodes, by;

propagating the path request message to first ones of the one or more neighboring wireless mesh nodes that are not in the power save state;

if a valid route is not yet found between the source node and the destination node, then;

waking up second ones of the one or more neighboring wireless mesh nodes that are in the power save state and are outlet powered;

propagating the path request message to the second ones of the one or more neighboring wireless mesh nodes; and

if a valid route is not yet found between the source node and the destination node, then;

waking up third ones of the one or more neighboring wireless mesh nodes that are in the power save state and are battery powered and are not in the critical battery state; and

propagating the path request message to the third ones of the one or more neighboring wireless mesh nodes.

2. The method of claim 1 wherein propagating the path request message comprises

broadcasting the path request message;

and

selectively unicasting the path request message to neighboring wireless mesh nodes in a power save state.

3. The method of claim 1 wherein propagating the path request message comprises

broadcasting the path request message;

and

responsive to a wake-up indication in the path request message, selectively unicasting the path request message to neighboring wireless mesh nodes in a power save state, if the neighboring wireless mesh nodes in the power save state are not in a critical battery state;

responsive to absence of a wake-up indication in the path request message, selectively unicasting the path request message to neighboring wireless mesh nodes in a power save state, if the neighboring wireless mesh nodes in the power save state are not battery-powered; and

unicasting the path request message to a neighboring wireless mesh node if the neighboring wireless mesh node is the destination node identified in the path request message.

4. The method of claim 1 further comprising adding a wireless mesh node identifier to the path request message.

5. The method of claim 1 wherein the path request message comprises a hop count value, and wherein the method further comprises incrementing the hop count value of the path request message prior to propagating the path request message.

6. The method of claim 1 further comprising

determining, responsive to the path request message, whether a valid path to the destination node exists;

and

transmitting a unicast path response message to the source node identified in the path request message.

7. The method of claim 1 further comprising

monitoring state of a battery power supply;

notifying one or more peer wireless mesh nodes of a critical battery state when the state of the battery power supply enters a threshold condition; and

entering a power save state.

8. An apparatus comprising:

one or more wireless network interfaces;

a memory;

one or more processors;

a wireless mesh access point module comprising computer-readable instructions operative to cause the one or more processors to;

maintain, in the memory, power state information for one or more neighboring wireless mesh nodes, wherein the power state information for each of the neighboring wireless mesh nodes comprises whether the wireless mesh node is a battery-powered device, whether the wireless mesh node is in a power save state, and whether the wireless mesh node is in a critical battery state;

receive a path request message from a first wireless mesh node, wherein the path request message identifies a source node and a destination node;

propagate the path request message to selected ones of the one or more neighboring wireless mesh nodes based on the power state information corresponding to the one or more neighboring wireless mesh nodes, by;

propagating the path request message to first ones of the one or more neighboring wireless mesh nodes that are not in the power save state;

if a valid route is not yet found between the source node and the destination node, then;

waking up second ones of the one or more neighboring wireless mesh nodes that are in the power save state and are outlet powered;

propagating the path request message to the second ones of the one or more neighboring wireless mesh nodes; and

if a valid route is not yet found between the source node and the destination node, then;

waking up third ones of the one or more neighboring wireless mesh nodes that are in the power save state and are battery powered and are not in the critical battery state; and

propagating the path request message to the third ones of the one or more neighboring wireless mesh nodes.

9. The apparatus of claim 8 wherein the wireless mesh access point module further comprises computer-readable instructions for propagating the path request message operable to cause the one or more processors to

broadcast the path request message;

and

selectively unicast the path request message to neighboring wireless mesh nodes in a power save state.

10. The apparatus of claim 8 wherein the wireless mesh access point module further comprises computer-readable instructions for propagating the path request message operable to cause the one or more processors to

broadcast the path request message;

and

responsive to a wake-up indication in the path request message, selectively unicast the path request message to neighboring wireless mesh nodes in a power save state, if the neighboring wireless mesh nodes in the power save state are not in a critical battery state;

responsive to absence of a wake-up indication in the path request message, selectively unicast the path request message to neighboring wireless mesh nodes in a power save state, if the neighboring wireless mesh nodes in the power save state are not battery-powered; and

unicast the path request message to a neighboring wireless mesh node if the neighboring wireless mesh node is the destination node identified in the path request message.

11. The apparatus of claim 8 wherein the wireless mesh access point module further comprises computer-readable instructions for propagating the path request message operable to cause the one or more processors to add a mesh node identifier to the path request message.

12. The apparatus of claim 8 wherein the path request message comprises a hop count value, and wherein the wireless mesh access point module further comprises computer-readable instructions operable to cause the one or more processes to increment the hop count value of the path request message prior to propagating the path request message.

13. The apparatus of claim 8 wherein the wireless mesh access point module further comprises computer-readable instructions operable to cause the one or more processes to

determine, responsive to the path request message, whether a valid path to the destination node exists;

and

transmit a unicast path response message to the source node identified in the path request message.

14. The apparatus of claim 8 further comprising a battery power supply;

and wherein the wireless mesh access point module further comprises computer-readable instructions operable to cause the one or more processes to

monitor state of the battery power supply;

notify one or more peer wireless mesh nodes of a critical battery state when the state of the battery power supply enters a threshold condition; and

enter a power save state.

15. One or more computer-readable non-transitory storage media embodying software operable when executed by one or more computer systems to:

maintain power state information for one or more neighboring wireless mesh nodes, wherein the power state information for each of the neighboring wireless mesh nodes comprises whether the wireless mesh node is a battery-powered device, whether the wireless mesh node is in a power save state, and whether the wireless mesh node is in a critical battery state;

receive a path request message from a first wireless mesh node, wherein the path request message identifies a source node and a destination node;

propagate the path request message to selected ones of the one or more neighboring wireless mesh nodes based on the power state information corresponding to the one or more neighboring wireless mesh nodes, by;

propagating the path request message to first ones of the one or more neighboring wireless mesh nodes that are not in the power save state;

if a valid route is not yet found between the source node and the destination node, then;

waking up second ones of the one or more neighboring wireless mesh nodes that are in the power save state and are outlet powered;

propagating the path request message to the second ones of the one or more neighboring wireless mesh nodes; and

if a valid route is not yet found between the source node and the destination node, then;

waking up third ones of the one or more neighboring wireless mesh nodes that are in the power save state and are battery powered and are not in the critical battery state; and

propagating the path request message to the third ones of the one or more neighboring wireless mesh nodes.

16. The media of claim 15 wherein, for propagating the path request message, the logic is further operable to

broadcast the path request message;

and

selectively unicast the path request message to neighboring wireless mesh nodes in a power save state.

17. The media of claim 15 wherein, for propagating the path request message, the media is further operable to

broadcast the path request message;

and

responsive to a wake-up indication in the path request message, selectively unicast the path request message to neighboring wireless mesh nodes in a power save state, if the neighboring wireless mesh nodes in the power save state are not in a critical battery state;

responsive to absence of a wake-up indication in the path request message, selectively unicast the path request message to neighboring wireless mesh nodes in a power save state, if the neighboring wireless mesh nodes in the power save state are not battery-powered; and

unicast the path request message to a neighboring wireless mesh node if the neighboring wireless mesh node is the destination node identified in the path request message.

18. The media of claim 15 wherein, for propagating the path request message, the media is further operable to add a mesh node identifier to the path request message.

19. The media of claim 15 wherein, for propagating the path request message, the media is further operable to increment the hop count value of the path request message prior to propagating the path request message.

20. The media of claim 15 wherein the media is further operable to

determine, responsive to the path request message, whether a valid path to the destination node exists;

and

transmit a unicast path response message to the source node identified in the path request message.

21. The media of claim 15 wherein the media is further operable to

monitor state of a battery power supply;

notify one or more peer wireless mesh nodes of a critical battery state when the state of the battery power supply enters a threshold condition; and

enter a power save state.

22. A system comprising:

a plurality of wireless mesh access points, wherein one or more of the plurality of wireless mesh access points comprise;

one or more wireless network interfaces;

a memory;

one or more processors;

a wireless mesh access point module comprising computer-readable instructions operative to cause the one or more processors to;

maintain, in the memory, power state information for one or more neighboring wireless mesh access points, wherein the power state information for each of the neighboring wireless mesh access points comprises whether the wireless mesh access point is a battery-powered device, whether the wireless mesh access point is in a power save state, and whether the wireless mesh access point is in a critical battery state;

receive a path request message from a first wireless mesh access point, wherein the path request message identifies a source node and a destination node;

propagate the path request message to selected ones of the one or more neighboring wireless mesh access points based on the power state information corresponding to the one or more neighboring wireless mesh access points, by;

propagating the path request message to first ones of the one or more neighboring wireless mesh nodes that are not in the power save state;

if a valid route is not yet found between the source node and the destination node, then;

waking up second ones of the one or more neighboring wireless mesh nodes that are in the power save state and are outlet powered;

propagating the path request message to the second ones of the one or more neighboring wireless mesh nodes; and

if a valid route is not yet found between the source node and the destination node, then;

 

waking up third ones of the one or more neighboring wireless mesh nodes that are in the power save state and are battery powered and are not in the critical battery state; and

 

propagating the path request message to the third ones of the one or more neighboring wireless mesh nodes;

broadcast one or more path discovery messages to one or more wireless mesh access points in a mesh network to discover routes to destination nodes, wherein the path discovery messages include a wake up indication that is cleared;

if no responses to the one or more path discovery messages are received that identify a valid route to a given destination node, broadcast one or more additional path discovery messages to the one or more wireless mesh access points in the mesh network, wherein the one or more additional path discovery messages include a wake up indication that is set to cause the neighboring wireless mesh access points to wake up one or more peer wireless mesh access points in a power save mode and propagate the path discovery messages to them.