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

• US 7,391,742 B2
• Filed: 09/30/2004
• Issued: 06/24/2008
• Est. Priority Date: 10/03/2003
• Status: Expired due to Fees

• Current Assignee: BAE Systems Information and Electronic Systems Integration Incorporated (BAE Systems Plc)
• Original Assignee: BAE Systems Advanced Information Technologies, Inc. (BAE Systems Plc)
• Inventors: Zabele, Steven M., Keaton, Mark
• Primary Examiner(s): Vu, Huy D.
• Assistant Examiner(s): HAN, CLEMENCE S
• Application Number:
  US10/955,466
• Publication Number:
  US 20050073962A1
• Time in Patent Office: 1,363 Days
• Field of Search: None
• 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, wherein the network lifetime is a length of time until any network node'"'"'s energy source is completely exhausted,

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,

where optimizing the model for maximum network lifetime includes determining a maximum network lifetime.

2. A method according to claim 1, 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.

3. 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, wherein the network lifetime is a length of time until any network node'"'"'s energy source is completely exhausted,

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,

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.

4. A method according to claim 3, 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.

5. A method according to claim 3, 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.

6. 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, wherein the network lifetime is a length of time until any network node'"'"'s energy source is completely exhausted,

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,

where optimizing the modified updated model by balancing the network across multiple pathways includes optimizing using quadratic programming.

7. 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, wherein the network lifetime is a length of time until any network node'"'"'s energy source is completely exhausted,

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

where optimizing the model for minimum network latency comprises determining a minimum number of relays to communicate information between network nodes.

8. A method according to claim 7, where updating the model includes:

constraining the 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 updating the model includes:

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

10. 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, wherein the network lifetime is a length of time until any network node'"'"'s energy source is completely exhausted,

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

where optimizing the updated model for maximum network lifetime includes determining a maximum network lifetime.

11. A method according to claim 10, 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.

12. 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, wherein the network lifetime is a length of time until any network node'"'"'s energy source is completely exhausted,

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

where optimizing the modified updated model by balancing the network across multiple pathways includes optimizing using quadratic programming.

13. 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, wherein the network lifetime is a length of time until any network node'"'"'s energy source is completely exhausted,

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,

where the instructions to optimize the model for maximum network lifetime include instructions to determine a maximum network lifetime.

14. A processor program product according to claim 13, 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.

15. 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, wherein the network lifetime is a length of time until any network node'"'"'s energy source is completely exhausted,

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,

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.

16. A processor program product according to claim 15, 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.

17. A processor program product according to claim 15, 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.

18. 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, wherein the network lifetime is a length of time until any network node'"'"'s energy source is completely exhausted,

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,

where the instructions to optimize the modified updated model by balancing the network across multiple pathways include instructions to optimize using quadratic programming.

19. 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 no 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.