Sleep scheduling for geographically distributed network nodes

• US 7,876,721 B2
• Filed: 04/20/2007
• Issued: 01/25/2011
• Est. Priority Date: 04/20/2007
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Nath, Suman K.
• Primary Examiner(s): Pérez-Gutiérrez; Rafael
• Assistant Examiner(s): Miah; Liton
• Application Number:
  US11/738,306
• Publication Number:
  US 20080259875A1
• Time in Patent Office: 1,376 Days
• Field of Search: 370/318, 370/400, 370/401, 370/332, 455/343.1, 455/343.4
• US Class Current: 370/318
• CPC Class Codes: H04W 40/24 Connectivity information management, e.g. connectivity discovery or connectivity update
• 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: Y02D 30/70 in wireless communication networks

Abstract

Techniques for implementing sleep scheduling in a distributed network environment are described. The sleep scheduling attempts to optimize routing of communication among nodes of the distributed network, while still conserving energy by allowing nodes to occasionally transition to sleep mode. The sleep scheduling is performed as a function of the number of awake neighboring nodes.

Claims

1. A method comprising:

communicating among multiple nodes in a distributed sensor network; and

deriving a sleep schedule for the nodes based upon a threshold value indicative of an optimized geographic routing of communication among the nodes;

wherein the deriving comprises;

determining whether a given node with one or more immediate neighboring nodes, in a distributed sensor network, is part of a connected neighborhood;

keeping the given node active if the number of the immediate neighboring nodes is less than the threshold value; and

deactivating the given node, if the given node or one or more of the immediate neighboring nodes depend at least in part on the connected neighborhood;

deactivating the given node when;

at least one node in the immediate neighborhood of the given node has further neighboring nodes greater than the threshold value, the further neighboring nodes being member of the connected neighborhood; and

at least two nodes in the connected neighborhood are indirectly connected to each other through connecting nodes lying within an n-hop neighborhood of the given node, the connecting nodes having rank values less than the rank value of the given node.

2. The method of claim 1, wherein the determining comprises:

associating a rank value with each of the nodes;

communicating the rank value between the given node and the immediate neighboring nodes; and

associating the given node with the connected neighborhood, wherein the connected neighborhood comprises immediate neighboring nodes of rank value less than the rank value of the given node.

3. The method of claim 2, wherein the rank value is a randomly generated value.

4. The method of claim 1 comprising, deactivating the given node when:

at least one node in the immediate neighborhood of the given node has further neighboring nodes greater than the threshold value, the further neighboring nodes being member of the connected neighborhood; and

at least two nodes in the connected neighborhood are directly connected to each other.

5. The method of claim 4, wherein the further neighboring nodes are immediate neighbors to the immediate neighboring nodes.

6. The method of claim 1, wherein the connecting nodes lie within a two-hop neighborhood of the given node.

7. One or more computer readable media storing computer-executable instructions that, when executed, perform acts comprising:

associating an order with each node in a distributed network;

exchanging the order between a given node and its immediate neighboring nodes, such that the given node is aware of the orders of the immediate neighboring nodes; and

associating the given node with a collection set, wherein the collection set comprises immediate neighboring nodes of order less than the order of the given node;

constraining the given node to remain active, if the number of the immediate neighboring nodes is less than a predefined value; and

rendering the given node to inactive state, if the given node or one or more of the immediate neighboring nodes depend at least in part on the collection set;

instructions for rendering the given node to an inactive state when;

at least one node in the immediate neighborhood of the given node has further neighboring nodes greater than the predefined value, the further neighboring nodes being member of the collection set; and

at least two nodes in the collection set are indirectly connected to each other through intermediate nodes lying within an n-hop neighborhood of the given node, the intermediate nodes having orders less than the order of the given node.

8. The computer-readable media of claim 7, comprising instructions for rendering the given node to an inactive state when:

at least one node in the immediate neighborhood of the given node has further neighboring nodes greater than the predefined value, the further neighboring nodes being members of the collection set; and

at least two nodes in the collection set are directly connected to each other.

9. The computer-readable media of claim 8, wherein the further neighboring nodes and the immediate neighboring nodes are adjacent to each other.

10. The computer-readable media of claim 7, wherein the intermediate nodes lie within a two-hop neighborhood of the given node.

11. The computer-readable media of claim 7, wherein the orders for all nodes in the distributed network are generated randomly.

12. The computer-readable media of claim 7, wherein the predefined value is chosen on the basis of a sought geographic routing performance.

13. A system comprising:

a plurality of nodes communicating with one another, forming a distributed network; and

a scheduling module resident within each node, wherein the scheduling module;

determines whether a given node with one or more neighboring nodes, in a distributed network, is a part of a schedule set;

impels the given node to remain active if the number of neighboring nodes is less than a threshold value; and

deactivates the given node if the given node or one or more of the immediate neighboring nodes, depend at least in part on the schedule set;

wherein scheduling module deactivates the given node when;

at least one node in the immediate neighborhood of the given node has further neighboring nodes greater than the threshold value, the further neighboring nodes being member of the schedule set; and

at least two nodes in the schedule set are indirectly connected to each other through assisting nodes lying within an n-hop neighborhood of the given node, the assisting nodes having ranks less than the rank of the given node.

14. The system of claim 13, wherein scheduling module determines whether a given node with one or more neighboring nodes, in a distributed network, is a part of the schedule set by:

assigning a unique randomly generated rank to the nodes of the distributed network;

exchanging the rank between the given node and the immediate neighboring nodes, such that the given node is aware of the ranks of all the immediate neighboring nodes; and

associating the given node with the schedule set, wherein the schedule set comprises immediate neighboring nodes of ranks less than the rank of the given node.

15. The system of claim 13, wherein scheduling module deactivates the given node when:

at least one node in the immediate neighborhood of the given node has further neighboring nodes greater than the threshold value, the further neighboring nodes being member of the schedule set; and

at least two nodes in the schedule set are directly connected to each other.

16. The system of claim 13, wherein the assisting nodes lie within a two-hop neighborhood of the given node.