Power management for a network utilizing a vertex/edge graph technique

• US 7,203,850 B2
• Filed: 01/20/2004
• Issued: 04/10/2007
• Est. Priority Date: 01/20/2004
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Yao, Richard Yuqi, Guo, Zihua, Zhu, Wenwu, Wang, Xin
• Primary Examiner(s): Cao; Chun
• Assistant Examiner(s): SURYAWANSHI, SURESH
• Application Number:
  US10/760,914
• Publication Number:
  US 20050182975A1
• Time in Patent Office: 1,176 Days
• Field of Search: 713/300, 713/310, 713/320, 370/311, 370/312, 340/7.38
• US Class Current: 713/300
• CPC Class Codes: H04L 12/12 Arrangements for remote connection or disconnection of substations or of equipment thereof
• CPC Class Codes: H04L 41/00 Arrangements for maintenance, administration or management of data switching networks, e.g. of packet switching networks
• CPC Class Codes: H04W 28/10 Flow control between communication endpoints
• CPC Class Codes: H04W 52/0216 using a pre-established activity schedule, e.g. traffic indication frame
• CPC Class Codes: H04W 52/0219 where the power saving management affects multiple terminals
• 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 power management technique for a network including a plurality of computing devices. The power management technique includes identifying an order in which one or more devices of the plurality of computing devices can transmit data within the prescribed time period. In one aspect, the number of wakeups are reduced for the computing devices within the network by increasing a number of adjacent channel time allocation periods within a prescribed time period that share a common computing device. In one aspect, the network can be based on Time Division Multiple Access (TDMA).

Claims

1. A method for power management of a network including a plurality of computing devices, the method comprising:

identifing an order of flows between one or more computing devices within a prescribed time period; and

reducing a number of wakeups for at least one computing device by increasing a number of adjacent flows that share a computing device, the reducing comprising;

deriving a vertex/edge graph in which a vertex of the vertex/edge graph represents a computing device and an edge of the vertex/edge graph represents data communications between a pair of computing devices;

selecting a first edge that extends between two associated vertices, the two associated vertices have a reduced degree compared to any other pair of associated vertices;

removing the first edge;

selecting a subsequent neighbor edge to the first edge, and removing the subsequent edge; and

removing the subsequent edge, wherein the order that the first edge and any subsequent edge are removed corresponds to the order of the flows within the network.

2. The method of claim 1, wherein the reduced degree of the edge indicates that one of the associated vertices has the same or lower degree of any vertex in the graph, and the other associated vertex of the edge has a lower degree than any other vertex that is a neighbor of one vertex that has the same or lower degree of any vertex in the graph.

3. A method for power management of a network including a plurality of computing devices, comprising:

identifying an order of flows between one or more computing devices within a rescribed time period;

reducing a number of wakeups for at least one computing device by increasing a number of adjacent flows that share a computing device; and

wherein data communications between multiple computing devices within the network can be represented graphically as including a number of vertices and a number of edges.

4. The method of claim 3, wherein the reducing a number of wakeups for the one or more devices is performed by scheduling the order of computing devices within each time frame based on a reduced degree searching computation.

5. The method of claim 3, wherein the network includes a local area network (LAN).

6. The method of claim 3, wherein the network includes a wireless personal area network (WPAN).

7. The method of claim 3, wherein the network complies with the IEEE 802.15.3 standard.

8. The method of claim 3, wherein the network includes a wireless network.

9. A method for power management of a network including a plurality of computing devices, the method comprising:

identifying an order of flows between one or more computing devices within a prescribed time period;

reducing a number of wakeups for at least one computing device by increasing a number of adjacent flows that share a computing device; and

generating a vertex/edge graph, wherein the network includes a number of edges that extend between different vertices within the vertex/edge graph, and further comprising associating the edges to the flows.

10. A method of power management for a time division multiple access (TDMA) network, comprising:

deriving a vertex/edge graph representing the TDMA network in which a vertex of the vertex/edge graph represents a computing device and an edge of the vertex/edge graph represents a request for data communications between a pair of computing devices;

selecting a first edge has a pair of associated first vertices, the pair of associated first vertices have the same or lower order of any pair of associated vertices of any edge within the vertex/edge graph;

removing the selected first edge from the vertex/edge graph;

selecting a second edge that is a neighbor to the first edge which has two associated second vertices, the associated second vertices have the same or lower degree of any pair of associated vertices of any neighbor edge to the first edge within the vertex/edge graph; and

removing the selected second edge from the vertex edge graph, wherein the sequence that the first edge and any subsequent edge are removed correlates to the order that corresponding computing devices will transmit corresponding data signals over the TDMA network.

11. The method of power management of claim 10, further comprising selecting a third edge that is a neighbor to the second edge which has two associated third vertices, the associated third vertices have the same or lower degree of any pair of associated vertices of any neighbor edge to the second edge within the vertex/edge graph, and wherein the order that each edge is removed correlates to the order that corresponding computing devices will transmit corresponding data signals over the TDMA network.

12. The method of claim 10, wherein the reduced degree of the first edge indicates that one of the associated vertices of the first edge has the same or lower degree of any vertex in the graph, and the other associated vertex of the first edge has a lower degree than any other vertex that is a neighbor of one vertex that has the same or lower degree of any vertex in the graph.

13. The method of power management of claim 10, wherein reducing the degree of both the first candidate vertex and the first neighbor vertex allows choosing the pair of vertices with the reduced combined degree.

14. The method of power management of claim 10, wherein reducing the degree of both the first candidate vertex and the first neighbor vertex allows choosing the pair of vertices with the reduced combined degree.

15. A tangible computer readable storage medium having computer readable instructions that when executed by a processor causes the processor to provide power management to a plurality of computing devices, by:

obtaining a sequence of one or more computing devices that can transmit data within the rescribed time period;

wherein the power management is provided by reducing a number of wakeups for the computing devices within the network which is performed by increasing a number of associated channel time allocation periods within a prescribed time period that share a common computing device; and

wherein the reducing the number of wakeups is performed by;

deriving a vertex/edge graph representing the network in which a vertex represents a computing device and an edge represents a request for data communications between a pair of computing devices;

selecting a first edge having a pair of associated first vertices, the pair of associated first vertices have or share the lowest degree of any pair of associated vertices in the vertex/edge graph;

removing the selected first edge;

selecting a second edge that was a neighbor to the removed first edge, the second edge having a pair of associated second vertices, the pair of associated second vertices is less than or equal to the degree of any associated pair of vertices of any neighbor to the removed first edge;

removing the selected second edge; and

wherein a sequence that the first edge, the second edge, and any subsequent selected edge is removed corresponds to the order that corresponding computing devices will transmit corresponding data signals over the network.

16. An apparatus, comprising:

a power management portion for a time division multiple access (TDMA) network, the TDMA network including a plurality of computing devices, wherein the power management portion reduces a number of wakeups for computing devices within the TDMA network by using;

means for deriving a vertex/edge graph representing the TDMA network in which a vertex represents a computing device and one edge that represents each request for data communications between a pair of computing devices;

means for selecting a first edge that at least shares the lowest degree of any edge in the vertex/edge graph;

means for removing the selected first edge;

means for selecting a neighbor edge that is a neighbor to the first edge, wherein they neighbor edge has or shares the lowest degree of any edge that is a neighbor to the first edge;

removing the neighbor edge; and

wherein the order that the first edge and the neighbor edge are removed corresponds to the order that corresponding computing devices will be permitted to use the TDMA network.

17. The apparatus of claim 16, wherein the means for selecting the lowest degree of the first edge indicates that one of the associated vertices of the first edge has the same or tower degree of any vertex in the graph, and the other associated vertex of the first edge has a lower degree than any other vertex that is a neighbor of one vertex that has the same or lower degree of any vertex in the graph.

18. The apparatus of claim 16, further comprising:

means for repeating the selecting the neighbor edge, and removing the neighbor edge.

19. The apparatus of claim 16, wherein the means for reducing the degree of the first edge allows choosing of associated vertices to the first edge that have a reduced combined degree.

20. The apparatus of claim 16, wherein the means for reducing the degree of the neighbor edge allows choosing of associated vertices to the neighbor edge that have a reduced combined degree.

21. An apparatus, comprising:

a power management portion for a time division multiple access network having a plurality of computing devices, wherein the power management portion reduces a number of wakeups for computing devices within the network by using;

a vertex/edge graph in which a vertex of the vertex/edge graph represents a computing device and an edge of the vertex/edge graph represents a request for data communications between a pair of computing devices;

a first edge having two associated first vertices, the two associated first vertices having a total degree that is equal to or less than the sum of the degrees of the any associated pair of vertices within the vertex/edge graph; and

wherein the power management portion considers the order that the first edge and any subsequent edges are removed as being related to the order that corresponding computing devices are allowed to use the network.