Granted Patent B1

US 8,175,016 · App. 10/804,190 · Granted May 8, 2012

Assignees: Verizon Corporate Services Group Inc.; Raytheon BBN Technologies Corp.

Abstract

Claims (115)

1. A method for minimizing an energy cost within a wireless network having a plurality of nodes, including a plurality of transmitting nodes and a plurality of receiving nodes, comprising:

determining an energy cost of a gathering of data from a plurality of nodes u to a single node v, wherein the energy cost includes at least an overhearing cost, the overhearing cost consisting of an unnecessary expenditure of energy by unintended receiving nodes receiving redundant information;

adjusting a transmission power assignment of a transmitting node; and

repeating the determining and adjusting to reduce a total energy cost,

wherein determining the energy cost further comprises determining a directed minimum-cost in-arborescence rooted at node v; and

wherein determining the directed minimum-cost in-arborescence comprises:

constructing a directed graph of the network, wherein the weight of each edge in the graph corresponds to the energy cost;

reversing the direction of each edge in the graph;

reversing the sign of the weight for each edge in the graph;

removing all incoming edges from node v;

determining the maximum-cost out-arborescence rooted at node v;

reversing the direction of each edge in the arborescence; and

reversing the sign of the weight for each edge in the arborescence.

2. A method for minimizing an energy cost within a wireless network having a plurality of nodes, including a plurality of transmitting nodes and a plurality of receiving nodes, comprising:

determining an energy cost of a gathering of data from a plurality of nodes u to a single node v, wherein the energy cost includes at least an overhearing cost, the overhearing cost consisting of an unnecessary expenditure of energy by nodes receiving that data that are not required to transmit that data to node v;

adjusting a transmission power assignment of a transmitting node; and

repeating the determining and adjusting to reduce a total energy cost.

3. The method of claim 2 , wherein determining the energy cost further comprises determining a directed minimum-cost in-arborescence rooted at node v.

4. The method of claim 3 , wherein determining a directed minimum-cost in-arborescence comprises finding an arborescence such that outdegree(v)=0 and for each node u, outdegree(u)=1.

5. The method of claim 3 , wherein determining a directed minimum-cost in-arborescence comprises:

constructing a directed graph of the network, wherein the weight of each edge in the graph corresponds to the energy cost;

reversing the direction of each edge in the graph;

reversing the sign of the weight for each edge in the graph;

removing all incoming edges from node v;

determining the maximum-cost out-arborescence rooted at node v;

reversing the direction of each edge in the arborescence; and

reversing the sign of the weight for each edge in the arborescence.

6. A method for minimizing an energy cost within a wireless network having a plurality of nodes, including a plurality of transmitting nodes and a plurality of receiving nodes, comprising:

determining an energy cost of a dissemination of data from a single node to a plurality of nodes, wherein the energy cost includes at least an overhearing cost, the overhearing cost consisting of an unnecessary expenditure of energy by nodes receiving the transmitted data redundantly;

adjusting a transmission power assignment of a transmitting node; and

repeating the determining and adjusting to reduce a total energy cost.

7. The method of claim 6 , wherein determining the energy cost comprises constructing an initial broadcast tree.

8. The method of claim 7 , wherein constructing an initial broadcast tree comprises constructing a Minimum Energy Spanning Tree (MEST).

9. The method of claim 7 , wherein adjusting a transmission power assignment comprises:

increasing a transmission power assignment for one node in the initial broadcast tree; and

excluding another node from the initial broadcast tree; and

repeating the increasing and excluding stages until no node can be excluded from the broadcast tree without leaving some node unreachable by any transmitting node.

10. The method of claim 6 , wherein adjusting a transmission power assignment comprises performing the Embedded Wireless Multicast Advantage (EWMA) algorithm.

11. The method of claim 1 , 2 , or 6 , wherein the energy cost further includes at least one of: a transmission energy cost; a reception energy cost; and an idle energy cost.

12. The method of claim 1 , 2 , or 6 , wherein the wireless network is a sensor network.

13. A computer-readable medium capable of configuring a user device to perform a method for minimizing an energy cost within a wireless network having a plurality of nodes, including a plurality of transmitting nodes and a plurality of receiving nodes, the method comprising:

determining an energy cost of a gathering of data from a plurality of nodes u to a single node v, wherein the energy cost includes at least an overhearing cost, the overhearing cost consisting of an unnecessary expenditure of energy by unintended receiving nodes receiving redundant information;

adjusting a transmission power assignment of a transmitting node; and

repeating the determining and adjusting to reduce a total energy cost

wherein determining the energy cost further comprises determining a directed minimum-cost in-arborescence rooted at node v; and

wherein determining the directed minimum-cost in-arborescence comprises:

constructing a directed graph of the network, wherein the weight of each edge in the graph corresponds to the energy cost;

reversing the direction of each edge in the graph;

reversing the sign of the weight for each edge in the graph;

removing all incoming edges from node v;

determining the maximum-cost out-arborescence rooted at node v;

reversing the direction of each edge in the arborescence; and

reversing the sign of the weight for each edge in the arborescence.

14. A computer-readable medium capable of configuring a user device to perform a method for minimizing an energy cost within a wireless network having a plurality of nodes, including a plurality of transmitting nodes and a plurality of receiving nodes, the method comprising:

determining an energy cost of a gathering of data from a plurality of nodes u to a single node v, wherein the energy cost includes at least an overhearing cost, the overhearing cost consisting of an unnecessary expenditure of energy by nodes receiving that data that are not required to transmit that data to node v;

adjusting a transmission power assignment of a transmitting node; and

repeating the determining and adjusting to reduce a total energy cost.

15. The computer-readable medium of claim 14 , wherein determining the energy cost further comprises determining a directed minimum-cost in-arborescence rooted at node v.

16. The computer-readable medium of claim 15 , wherein determining a directed minimum-cost in-arborescence comprises finding an arborescence such that outdegree(v)=0 and for each node u, outdegree(u)=1.

17. The computer-readable medium of claim 15 , wherein determining a directed minimum-cost in-arborescence comprises:

constructing a directed graph of the network, wherein the weight of each edge in the graph corresponds to the energy cost;

reversing the direction of each edge in the graph;

reversing the sign of the weight for each edge in the graph;

removing all incoming edges from node v;

determining the maximum-cost out-arborescence rooted at node v;

reversing the direction of each edge in the arborescence; and

reversing the sign of the weight for each edge in the arborescence.

18. A computer-readable medium capable of configuring a user device to perform a method for minimizing an energy cost within a wireless network having a plurality of nodes, including a plurality of transmitting nodes and a plurality of receiving nodes, the method comprising:

determining an energy cost of a dissemination of data from a single node to a plurality of nodes, wherein the energy cost includes at least an overhearing cost, the overhearing cost consisting of an unnecessary expenditure of energy by nodes receiving the transmitted data redundantly;

adjusting a transmission power assignment of a transmitting node; and

repeating the determining and adjusting to reduce a total energy cost.

19. The computer-readable medium of claim 18 , wherein determining the energy cost comprises constructing an initial broadcast tree.

20. The computer-readable medium of claim 19 , wherein constructing an initial broadcast tree comprises constructing a Minimum Energy Spanning Tree (MEST).

21. The computer-readable medium of claim 18 , wherein adjusting a transmission power assignment comprises:

increasing a transmission power assignment for one node in the initial broadcast tree; and

excluding another node from the initial broadcast tree; and

repeating the increasing and excluding stages until no node can be excluded from the broadcast tree without leaving some node unreachable by any transmitting node.

22. The computer-readable medium of claim 18 , wherein adjusting a transmission power assignment comprises performing the Embedded Wireless Multicast Advantage (EWMA) algorithm.

23. The computer-readable medium of claim 13 , 14 , or 18 , wherein the energy cost further includes at least one of: a transmission energy cost; a reception energy cost; and an idle energy cost.

24. A system for minimizing an energy cost within a wireless network having a plurality of nodes, including a plurality of transmitting nodes and a plurality of receiving nodes, the system comprising:

a processor configured to:

determine an energy cost, wherein the energy cost includes at least an overhearing cost, the overhearing cost consisting of an unnecessary expenditure of energy by unintended receiving nodes receiving redundant information;

adjust a transmission power assignment of a transmitting node; and

repeat the determining and adjusting to reduce a total energy cost.

25. A system for minimizing an energy cost within a wireless network having a plurality of nodes, including a plurality of transmitting nodes and a plurality of receiving nodes, the system comprising:

a processor configured to:

determine an energy cost, wherein the energy cost includes at least an overhearing cost, the overhearing cost consisting of an unnecessary expenditure of energy by unintended receiving nodes receiving redundant information;

adjust a transmission power assignment of a transmitting node; and

repeat the determining and adjusting to reduce a total energy cost,

wherein the processor is further configured to determine the energy cost of a gathering of data from a plurality of nodes u to a single node v.

26. The system of claim 25 , wherein the processor is further configured to determine a directed minimum-cost in-arborescence rooted at node v.

27. The system of claim 26 , wherein the processor is further configured to find an arborescence such that outdegree(v)=0 and for each node u, outdegree(u)=1.

28. The system of claim 26 , wherein the processor is further configured to:

construct a directed graph of the network, wherein the weight of each edge in the graph corresponds to the energy cost;

reverse the direction of each edge in the graph;

reverse the sign of the weight for each edge in the graph;

remove all incoming edges from node v;

determine the maximum-cost out-arborescence rooted at node v;

reverse the direction of each edge in the arborescence; and

reverse the sign of the weight for each edge in the arborescence.

29. A system for minimizing an energy cost within a wireless network having a plurality of nodes, including a plurality of transmitting nodes and a plurality of receiving nodes, the system comprising:

a processor configured to:

determine an energy cost, wherein the energy cost includes at least an overhearing cost, the overhearing cost consisting of an unnecessary expenditure of energy by unintended receiving nodes receiving redundant information;

adjust a transmission power assignment of a transmitting node; and

repeat the determining and adjusting to reduce a total energy cost,

wherein the processor is further configured to determine the energy cost of a dissemination of data from a single node to a plurality of nodes.

30. The system of claim 29 , wherein the processor is further configured to construct an initial broadcast tree.

31. The system of claim 30 , wherein the processor is further configured to construct a Minimum Energy Spanning Tree (MEST).

32. The system of claim 29 , wherein the processor is further configured to:

increase a transmission power assignment for one node in the initial broadcast tree; and

exclude another node from the initial broadcast tree; and

repeat the increasing and excluding stages until no node can be excluded from the broadcast tree without leaving some node unreachable by any transmitting node.

33. The system of claim 29 , wherein the processor is further configured to perform the Embedded Wireless Multicast Advantage (EWMA) algorithm.

34. The system of claim 24 , 25 , or 29 , wherein the energy cost further includes at least one of: a transmission energy cost; a reception energy cost; and an idle energy cost.

35. The system of claim 24 , 25 , or 29 , wherein the wireless network is a sensor network.

Assignments (8)