Power management of a network by increasing a number of adjacent flows that share a computing device

• US 7,702,932 B2
• Filed: 03/30/2007
• Issued: 04/20/2010
• Est. Priority Date: 01/20/2004
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Wang, Xin, Yao, Richard Yuqi, Guo, Zihua, Zhu, Wenwu
• Primary Examiner(s): Suryawanshi; Suresh K
• Application Number:
  US11/694,529
• Publication Number:
  US 20070168683A1
• Time in Patent Office: 1,117 Days
• Field of Search: 713/300
• 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 at least partially implemented by a computing device 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

wherein the adjacent flows are associated with channel time allocation periods within a prescribed period.

2. The method of claim 1, wherein the reducing a number of wakeups for the one or more devices is performed by:

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.

3. The method of claim 2, 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.

4. The method of claim 1, 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 1, wherein the network includes a local area network (LAN).

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

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

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

9. The method of claim 1, 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.

10. The method of claim 1, further comprising 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.

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

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 selecting a sequence of the flows that reduces the total number of computing device wakeups;

obtaining a sequence of one or more computing devices, based on the sequence of the flows, that can transmit data within the prescribed time period; and

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.

12. The computer readable storage media of claim 11, 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.

13. A method at least partially implemented by a computing device 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 selecting a sequence of the flows that reduces the total number of computing device wakeups; and

wherein the adjacent flows are associated with channel time allocation periods within a prescribed period;

wherein the flow represents the desired communication path between different computing devices.