Methods and systems for determining a set of costs of routes in a network

• US 20050073962A1
• Filed: 09/30/2004
• Published: 04/07/2005
• Est. Priority Date: 10/03/2003
• Status: Active Grant

• Current Assignee: BAE Systems Information and Electronic Systems Integration Incorporated (BAE Systems Plc)
• Original Assignee: Alphatech, Inc.
• Inventors: Zabele, Steven, Keaton, Mark
• Granted Patent: US 7,391,742 B2
• Time in Patent Office: Days
• US Class Current: 370/254
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/121 by minimising delays
• CPC Class Codes: H04L 45/124 using a combination of metrics
• CPC Class Codes: H04L 45/125 based on throughput or bandwidth
• CPC Class Codes: H04L 45/14 Routing performance; Theoretical aspects
• 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/248 Connectivity information update
• CPC Class Codes: H04W 40/28 for reactive routing
• CPC Class Codes: Y02D 30/70 in wireless communication networks

Abstract

Described are methods, systems, and processor program products for determining a set of costs of routes in a network, including providing a model of the network, optimizing the model for maximum network lifetime, updating the model using at least one constraint based on the maximum network lifetime, optimizing the updated model for minimum network latency, modifying the updated model using a constraint based on the minimum network latency, and, optimizing the modified updated model by balancing the network across multiple pathways to provide costs of routes in the network.

Claims

1. A method for determining a set of costs of routes in a network, the method comprising:

providing a model of the network,

optimizing the model for maximum network lifetime,

updating the model using at least one constraint based on the maximum network lifetime,

optimizing the updated model for minimum network latency,

modifying the updated model using at least one constraint based on the minimum network latency, and,

optimizing the modified updated model by balancing the network across multiple pathways to provide the costs.

2. A method according to claim 1, where providing a model comprises specifying at least one constraint based on the energy of nodes in the network.

3. A method according to claim 1, where providing a model comprises specifying at least one constraint based on the initial battery energy of nodes in the network.

4. A method according to claim 1, where providing a model comprises specifying at least one constraint based on available node communications capacity for nodes in the network.

5. A method according to claim 1, where optimizing the model for maximum network lifetime includes determining a maximum network lifetime.

6. A method according to claim 5, where updating the model using at least one constraint based on the maximum network lifetime includes:

constraining the model based on a percentage of the maximum network lifetime, the percentage between zero and one-hundred.

7. A method according to claim 1, where optimizing the updated model for minimum network latency comprises determining a minimum number of relays to communicate information between network nodes based on the maximum network lifetime.

8. A method according to claim 7, where modifying the updated model using at least one constraint based on the minimum network latency includes:

constraining the updated model based on a percentage of the amount of information, the percentage between zero and one-hundred.

9. A method according to claim 7, where modifying the updated model using at least one constraint based on the minimum network latency includes:

constraining the updated model based on a multiplier of the number of relays.

10. A method according to claim 1, where optimizing the modified updated model by balancing the network across multiple pathways includes optimizing using quadratic programming.

19. A method according to claim 5, where modifying the updated model using at least one constraint based on the maximum network lifetime includes:

constraining the updated model based on a percentage of the maximum network lifetime, the percentage between zero and one-hundred.

11. A method for determining a set of costs of routes in a network, the method comprising:

providing a model of the network,

optimizing the model for minimum network latency,

updating the model using at least one constraint based on the minimum network latency,

optimizing the updated model for maximum network lifetime,

modifying the updated model using at least one constraint based on the maximum network lifetime, and,

optimizing the modified updated model by balancing the network across multiple pathways to provide the costs.

12. A method according to claim 11, where providing a model comprises specifying at least one constraint based on the energy of nodes in the network.

13. A method according to claim 11, where providing a model comprises specifying at least one constraint based on the initial battery energy of nodes in the network.

14. A method according to claim 11, where providing a model comprises specifying at least one constraint based on available node communications capacity for nodes in the network.

15. A method according to claim 11, where optimizing the model for minimum network latency comprises determining a minimum number of relays to communicate information between network nodes.

16. A method according to claim 15, where updating the model includes:

constraining the model based on a percentage of the amount of information, the percentage between zero and one-hundred.

17. A method according to claim 15, where updating the model includes:

constraining the model based on a multiplier of the number of relays.

18. A method according to claim 11, where optimizing the updated model for maximum network lifetime includes determining a maximum network lifetime.

20. A method according to claim 11, where optimizing the modified updated model by balancing the network across multiple pathways includes optimizing using quadratic programming.

21. A processor program product disposed on a processor readable medium, and having instructions for causing at least one processor to:

optimize a model of a network for maximum network lifetime,

update the model using at least one constraint based on the maximum network lifetime,

optimize the updated model for minimum network latency,

modify the updated model using at least one constraint based on the minimum network latency, and,

optimize the modified updated model by balancing the network across multiple pathways to provide the costs.

22. A processor program product according to claim 21, where the model comprises at least one constraint based on the energy of nodes in the network.

23. A processor program product according to claim 21, where the model comprises at least one constraint based on the initial battery energy of nodes in the network.

24. A processor program product according to claim 21, where the model comprises specifying at least one constraint based on available node communications capacity for nodes in the network.

25. A processor program product according to claim 21, where the instructions to optimize the model for maximum network lifetime include instructions to determine a maximum network lifetime.

26. A processor program product according to claim 25, where the instructions to update the model using at least one constraint based on the maximum network lifetime include instructions to:

constrain the model based on a percentage of the maximum network lifetime, the percentage between zero and one-hundred.

27. A processor program product according to claim 21, where instructions to optimize the updated model for minimum network latency comprises instructions to determine a minimum number of relays to communicate information between network nodes based on the maximum network lifetime.

28. A processor program product according to claim 27, where the instructions to modify the updated model using at least one constraint based on the minimum network latency include instructions to:

constrain the updated model based on a percentage of the amount of information, the percentage between zero and one-hundred.

29. A processor program product according to claim 27, where the instructions to modify the updated model using at least one constraint based on the minimum network latency include instructions to:

constrain the updated model based on a multiplier of the number of relays.

30. A processor program product according to claim 21, where the instructions to optimize the modified updated model by balancing the network across multiple pathways include instructions to optimize using quadratic programming.

31. A processor program product disposed on a processor readable medium, and having instructions for causing at least one processor to:

optimize a model of a network for minimum network latency,

update the model using at least one constraint based on the minimum network latency,

optimize the updated model for maximum network lifetime,

modify the updated model using at least one constraint based on the maximum network lifetime, and,

optimize the modified updated model by balancing the network across multiple pathways to provide the costs.

32. A method for computing a set of costs of routes in a network, the method comprising:

constructing a list of selected nodes that includes nodes for which an optimal route to a core node is identified, associating therewith a nexthop to reach the core node and a cost to reach the core node through the nexthop,

constructing a list of available nodes which have been selected and have neighbors which have not been selected,

for each of the available nodes, identifying an available node and computing a cost of each unselected neighbor to reach the core node through the identified available node,

selecting the identified available node and unselected neighbor having the lowest cost,

generating alternative nexthops by constructing a list of selected neighbors having a cost to reach the core through the identified available node, the cost within a threshold,

removing the identified available node from the available node list if the identified available node has unselected neighbors,

adding the unselected neighbor having the lowest cost to the available node list if said neighbor node has unselected neighbors, and,

returning to identifying an available node until the available node list is empty.