System and method for wireless mesh networking

• US 7,653,010 B2
• Filed: 06/02/2004
• Issued: 01/26/2010
• Est. Priority Date: 06/03/2003
• Status: Active Grant

• Current Assignee: Sentec Ltd. (Xylem, Inc.)
• Original Assignee: Casient Limited
• Inventors: Shakespeare, Simon, Storkey, Matthew, Ensor, Tim, Colby, Edward
• Primary Examiner(s): Pham; Brenda
• Application Number:
  US10/559,076
• Publication Number:
  US 20060245360A1
• Time in Patent Office: 2,064 Days
• Field of Search: 370/248, 370/252, 370/255, 370/256, 370/351, 370/386, 370/389, 370/392, 370/395.3, 370/395.32, 370/395.54, 370/400
• US Class Current: 370/255
• CPC Class Codes: H04L 2101/604 Address structures or formats
• CPC Class Codes: H04L 45/48 Routing tree calculation
• CPC Class Codes: H04L 61/50 Address allocation
• 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 40/30 for proactive routing
• CPC Class Codes: H04W 8/26 Network addressing or numbering for mobility support
• CPC Class Codes: Y02D 30/70 in wireless communication networks

Abstract

According to an embodiment of the invention, there is disclosed a method of operating a wireless mesh network. The method comprises: seeding the network from a first node; allocating a network address to each member node of the network to form a tree-like structure of the nodes, such that the network address is reversibly derived from the network address of the member node from which it is derived in the tree-like structure; and mapping out cross-branch network connections between nodes that are determined not to be immediate neighbour nodes according to the addresses of the tree-like structure. Further related system embodiments are also disclosed.

Claims

1. A method of operating a wireless mesh network including a plurality of nodes, each node comprising a processor, the method comprising:

seeding the network from a first node;

allocating a network address to each member node of the network to form a tree-like structure of nodes, such that the network address is reversibly derived from the network address of the member node from which it is derived in the tree-like structure; and

mapping out cross-branch network connections between nodes that are determined not to be immediate neighbour nodes according to the addresses of the tree-like structure,

wherein cross-branch network connections are formed by;

(1) each node of the network periodically transmitting a discovery message; and

(ii) when a second member node receives the discovery message, forming a cross-branch network connection between the second member node and a node that sent the discovery message.

2. The method according to claim 1, wherein each node of the network responds to the same predetermined maximum number of requests to join the network from other potential member nodes.

3. The method according to claim 1, wherein each network address for each new node of the network is derived from a network address of a member node that responds to the new node'"'"'s request to join the network.

4. The method according to any one of claims 1 through 3, further comprising re-allocating the network addresses of the nodes of the network such that no node of the network has a network connection with another node of the network that is in a generation of the tree-like structure that differs by more than one generation.

5. The method according to claim 4, further comprising determining a minimum number of nodes through which a message must be passed to be transferred from a source node to a destination node.

6. The method according to claim 5, wherein the method comprises:

determining a minimum number of nodes through which a message must be passed to be transferred from each neighbouring node of a source node to a destination node; and

transferring the message from the source node to a neighbour node that has the smallest such minimum number of nodes.

7. The method according to claim 1, wherein the network comprises both battery-powered and mains-powered nodes, and wherein the method further comprises:

operating at least one battery-powered node in a dormant state for at least a portion of time; and

using a mains-powered node, associated with the at least one battery-powered node, to hold incoming information directed to the associated battery-powered node, until the battery-powered device becomes active again.

8. The method according to claim 7, further comprising preferentially routing messages via the mains-powered nodes.

9. The method according to claim 1, wherein a single synchronization node of the network periodically transmits time synchronization messages throughout the network.

10. The method according to claim 1, wherein each node of the network maintains a record of a time offset between its own time standard and that of each of its neighbouring nodes.

11. The method according to claim 1, further comprising connecting at least one member node of the network to a computer device using a management interface.

12. The method according to claim 11, wherein the computer device gathers information about the status of the network using the management interface.

13. The method according to claim 11, wherein the computer device issues instructions to at least one node of the network using the management interface.

14. The method according to claim 13, further comprising issuing instructions from the computer device to at least one node of the network, using the management interface, to group at least two nodes of the network, such that the grouped nodes store network addresses of fellow grouped nodes, and transmit a message to the fellow grouped nodes upon receipt of an external stimulus.

15. The method according to claim 14, wherein at least one node of the grouped nodes is capable of re-transmitting a message to all other member nodes of the grouped nodes.

16. The method according to claim 1, wherein at least one node of the network communicates with a device that is capable of converting messages from the network into a form suitable for transmission via an alternative protocol.

17. The method according to claim 16, wherein the alternative protocol is at least one of:

Ethernet, the 802.11 Standard, HyperLAN, TCP/IP, GSM, GPRS, EDGE, or UMTS.

18. The method according to claim 1, wherein each node of the network comprises a wireless transceiver, a microprocessor, and an external device.

19. The method according to claim 18, wherein the external device comprises a sensor, an actuator, or a general computing device.

20. The method according to claim 18, wherein the external device comprises a building lighting device.

21. The method according to claim 18, wherein each node comprises components selected from at least one of:

(i) a generic ISM band transceiver and a low power microprocessor;

(ii) a device conforming to the Bluetooth standard 802.15.1

(iii) a device conforming to the ZigBee standard 802.15.4; and

(iv) a device conforming to the WiFi standard 802.11.

22. A wireless network, the network comprising:

a plurality of member nodes arranged in a tree-like structure seeded from a first node, wherein each member node is allocated a network address that is reversibly derived from the network address of the member node from which it is derived in the tree-like structure; and

at least one cross-branch connection between nodes of the network that are not immediate neighbour nodes according to the network addresses of the tree-like structure,

wherein cross-branch network connections are formed by;

(1) each node of the network periodically transmitting a discovery message; and

(ii) when a second member node receives the discovery message, forming a cross-branch network connection between the second member node and a node that sent the discovery message.