System and method for forming, maintaining and dynamic reconfigurable routing in an ad-hoc network

• US 20040008691A1
• Filed: 06/05/2002
• Published: 01/15/2004
• Est. Priority Date: 06/05/2002
• Status: Active Grant

• Current Assignee: Cooper Technologies Company (Eaton Corporation PLC.)
• Original Assignee: EKA Systems Incorporated (Eaton Corporation PLC.)
• Inventors: Winter, Timothy Clark, Anand, Minakshisundaran B., Chakravarthi, Prakash R.
• Granted Patent: US 7,035,207 B2
• Time in Patent Office: Days
• US Class Current: 370/395.31
• CPC Class Codes: H04L 45/122 by minimising distances, e.g. by selecting a route with minimum of number of hops
• CPC Class Codes: H04L 45/54 Organization of routing tables
• CPC Class Codes: H04W 4/24 Accounting or billing
• CPC Class Codes: H04W 40/00 Communication routing or communication path finding
• CPC Class Codes: H04W 40/08 based on transmission power
• CPC Class Codes: H04W 40/10 based on available power or energy
• CPC Class Codes: H04W 40/12 based on transmission quality or channel quality
• CPC Class Codes: H04W 40/24 Connectivity information management, e.g. connectivity discovery or connectivity update
• CPC Class Codes: H04W 40/246 Connectivity information discovery
• CPC Class Codes: H04W 40/248 Connectivity information update
• 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: 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 network comprises a plurality of network nodes. Each network node has a unique node identifier within the context of the network and stores a table of nodes. The table of nodes includes at least one table entry. The table entry includes three fields—a destination node field, a next node field and a cost field. The destination field is a unique node identifier corresponding to another node in the network. The next node is a unique node identifier corresponding to the next node in the communication path to the destination node. The cost field is the cost associated with communication with the network node. When a node is added to the network, it detects the presence of adjacent nodes. The new node obtains the table of nodes stored in each adjacent node and uses the information contained in the node tables to updates its own node table, thereby obtaining information for communicating with every other node in the network. Each of the adjacent nodes obtains information related to communicating with the new node, adjusts its own table of nodes accordingly, and sends update information to nodes adjacent to it to propagate knowledge of the new node. Changes in the network are propagated between network nodes by periodic exchange and updating of node tables. Updating can be performed at a pre-determined time and/or in response to a change in the network.

Claims

1. A network, comprising a plurality of network nodes, each network node adapted to detect the presence of an adjacent network node that is added to the network, wherein each network node stores a cost to communicate with each other node in the network through at least one communication path to each other node in the network.

2. The network recited in claim 1, wherein the presence of the adjacent network node added to the network is propagated throughout the plurality of network nodes.

3. The network recited in claim 1, wherein each network node comprises a table, the table comprising a destination node indicating a possible destination node in the network, a next node indicating an adjacent network node with which to communicate to reach the destination node and a cost, indicating the cost to communicate with the destination node.

4. The network recited in claim 3, wherein periodically one or more of the plurality of network nodes updates its table by communicating with its adjacent nodes to obtain information in the tables contained in the adjacent nodes.

5. The network recited in claim 3, wherein whenever a table in a network node is modified, the network node with the modified table communicates with its adjacent network nodes to pass it modified table to its adjacent network nodes.

6. A network node for use in a network, comprising:

a memory for storing an address of a destination node, an address of a next node and a cost for communicating with the destination node through the next node from the network node;

means for detecting the presence of an adjacent node when a new node is added to the network within communication range of the network node; and

means for transmitting contents of the memory to the adjacent node when the adjacent node is detected.

7. The network node recited in claim 6, further comprising:

means for obtaining contents of an adjacent node memory when the network node is added to the network; and

means for updating the memory with the obtained contents of the adjacent node memory, wherein the contents of the adjacent node memory comprise at least one address of a destination node, at least one address of a next node and at least one cost.

8. The network node recited in claim 7, wherein the means for updating the memory comprises:

means for calculating a cost of communicating from the network node to the adjacent node; and

means for adding the cost to each cost obtained from the adjacent node; and

means for storing the cost in the memory.

9. A method for building a network by adding network nodes to a network, comprising the steps of:

providing a unique identifier for a network node to be added to the network;

storing the unique identifier in the network node to add to the network; and

storing a network table in the network node, the network table comprising a plurality of entries, each entry having an address of a destination node, the address of the destination node being a unique identifier corresponding to the destination node, an address of a next node, the address of the next node being a unique identifier corresponding to an adjacent node to the network node being added to the network and a cost value, the cost value being the cost of communicating with the destination node from the network node.

10. The method for building a network recited in claim 9, further comprising the step of storing an identifier of an adjacent node as the address of the destination node and the address of the next node for at least one entry in the network table.

11. The method recited in claim 9, further comprising the steps of:

placing the network node to be added to the network within a communicable distance of at least one other network node already in the network;

communicating with the adjacent nodes to update the table to facilitate communicating with other nodes in the network.

12. A method for building a network comprising a plurality of network nodes, comprising the steps of:

(a) associating a unique identifier with a network node;

(b) storing the unique identifier of the network node in the network node so that it can be accessed by other network nodes that are added to the network;

(c) creating a network table in the network node, the network node having a plurality of entries, each entry adapted to store a destination node address corresponding to a unique identifier associated with a destination node with which the network node can communicate, a next node address corresponding to a unique identifier associated with an adjacent node that is in a communication path from the network node to the destination node and a cost value corresponding to a cost for the network node to communicate with the destination node;

(d) placing the network node in a network of other network nodes;

(e) detecting an adjacent network node;

(f) obtaining an adjacent network node entry from a table in an adjacent network node; and

(g) creating a new entry in the table of the network node network using the information in the entry obtained from the adjacent network node, wherein the destination node address of the new entry is the unique identifier associated with the destination node of the adjacent network node entry, the next node address of the new entry is the unique identifier of the adjacent network node and the cost value is the sum of the cost value in the adjacent node entry and the cost of communicating with the adjacent network node.

13. The method recited in claim 12, further comprising the step of repeating steps (f) and (g) for each adjacent network node.

14. The method recited in claim 12, further comprising the step of repeating steps (f) and (g) for each adjacent network node for every node in the network.

15. The method recited in claim 12, further comprising the step of repeating steps (f) and (g) at pre-determined times.

16. The method recited in claim 12, further comprising the step of repeating steps (f) and (g) periodically.

17. The method recited in claim 12, further comprising the step of repeating steps (f) and (g) at pre-determined times for each adjacent network node for every network node in the network.

18. The method recited in claim 12, further comprising the step of repeating steps (f) and (g) periodically for each adjacent network node for every network node in the network.

19. The method recited in claim 12, further comprising the step of storing the unique identifier of the adjacent network node as the destination node address and next node address for at least one entry in the table.

20. A network for optimizing communications, comprising:

a plurality of network nodes each network node having a network table comprising an entry for each other node in the network, each entry comprising a first unique identifier associated with a destination node in the network, a second unique identifier associated with an adjacent node in the network that is in the communication path of the destination node and a cost element corresponding to a cost associated with communicating from the network node in which the table is stored to the destination node; and

means for determining a minimum cost of communicating with a destination node using the cost element thereby optimizing communications in the network.

21. The network recited in claim 20, wherein at least one cost element is determined on the basis of a bit error rate associated with communicating between the network node in which the table is stored and the destination node.

22. The network recited in claim 20, wherein at least one cost element is determined on the basis of a received signal strength associated with communicating between the network node in which the table is stored and the destination node.

23. The network recited in claim 20, wherein at least one cost element is determined on the basis of a required transmission power associated with communicating between the network node in which the table is stored and the destination node.

24. The network recited in claim 20, wherein at least one cost element is determined on the basis of a number of retries required to establish a communication path between the network node in which the table is stored and the destination node.

25. The network recited in claim 20, wherein at least one cost element is determined on the basis of a time required to establish a communication path between the network node in which the table is stored and the destination node