Clustering based load adaptive sleeping protocol for ad hoc networks

• US 7,298,716 B2
• Filed: 11/06/2003
• Issued: 11/20/2007
• Est. Priority Date: 11/06/2003
• Status: Expired due to Fees

• Current Assignee: RPX Corporation
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Abraham, Santosh P., Chuah, Mooi Choo
• Primary Examiner(s): D'Agosta; Steve M.
• Application Number:
  US10/702,748
• Publication Number:
  US 20050117530A1
• Time in Patent Office: 1,475 Days
• Field of Search: 455/41.1, 455/41.2, 455/41.3, 455/553.1, 455/556.2, 455450-4521, 455/507, 370/329, 370/331, 370/338, 370/321
• US Class Current: 370/321
• CPC Class Codes: H04W 52/0232 according to average transmission signal activity
• 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 clustering based load adaptive sleeping protocol for ad hoc networks includes a plurality of nodes forming a cluster, where the nodes in the cluster are partitioned into n groups. This partitioning is performed based on the node ID (e.g. node_id modulo n). The cluster head transmits a beacon at fixed intervals. The beacon interval is divided into N slots, where N is a multiple of n. Node sleep/activation times are synchronized to the beacon interval slots. The node'"'"'s group number is used to determine the slots within a beacon interval that a node begins it s sleep cycle. Therefore, no additional signaling is required between nodes to indicate sleep patterns. The sleeping time of each node may be increased when extended periods of inactivity are detected according to an adaptive procedure.

Claims

1. A clustering based load adaptive sleeping protocol for ad hoc networks, comprising:

a beacon signal originating from a cluster-head of a cluster, said beacon signal comprising a plurality of sequential beacon intervals, said beacon intervals each comprises a plurality of time slots associated with groups of nodes in said cluster;

wherein said groups of nodes are defined by node_id modulo n, where node id represents a unique host identification of each node, and n is an integer representing a number of groups in said cluster;

wherein said time slots are sequentially numbered zero to n−

1;

wherein each said beacon interval comprises at least one sequence of time slots numbered zero to n−

1; and

wherein one of said n time slots represents an epoch when a node is in an awake state, and n−

1 time slots represent an epoch when said node is in a sleep state.

2. The sleeping protocol of claim 1, wherein each node is in an awake state during a time slot “

m”

corresponding to said node'"'"'s assigned group number such that m=n.

3. The sleeping protocol of claim 2, wherein said node is in said sleep state during time slots occurring at (m+1) inodulo n.

4. A method of adapting a sleeping protocol of a node based on traffic patterns of said node, said node being associated with a cluster having a plurality of groups of nodes including a cluster-head node for providing a beacon signal, said method comprising:

sequentially transitioning between an awake state and a sleep state of operation according to the beacon signal;

determining whether said node has received at least one message from another node for a plurality of transition cycles between said awake state and sleep state; and

extending said sleep state for each successive transition cycle, in an instance where no messages are received during a previous transition cycle, further comprising;

incrementing a counter each time said node cycles between said awake and asleep states of operation;

comparing said count to a predetermined count threshold; and

extending said sleep state for each successive transition cycle, in an instance where said count exceeds said predetermined count threshold and no messages are received during a previous transition cycle.

5. The method of claim 4, wherein said at least one message comprises at least one of a request to send (RTS) and a traffic indication map (TIM).

6. The method of claim 4, wherein said sequentially transitioning between said awake state and said sleep state of operation comprises:

providing said beacon signal with a plurality of sequential beacon intervals, wherein said beacon intervals each comprises a plurality of time slots associated with said plurality of groups of nodes in said cluster.

7. The sleeping protocol of claim 6, wherein said groups of nodes are defined by node_id modulo n, where node_id is a unique host identification of each node, and n is a number of groups formed in said cluster.

8. The sleeping protocol of claim 7, wherein said time slots are sequentially numbered zero to n−

1.

9. The sleeping protocol of claim 8, wherein each said beacon interval comprises at least one sequence of time slots numbered zero to n−

1.

10. The sleeping protocol of claim 9, wherein one of said n time slots represents an epoch when a node is in an awake state, and n−

1 time slots represent an epoch when said node is in a sleep state.

11. The sleeping protocol of claim 10, wherein each node is in an awake state during a time slot “

m”

corresponding to said node'"'"'s assigned group number such that m=n.

12. The sleeping protocol of claim 11, wherein said node is in said sleep state during time slots occurring at (m+1) modulo n.

13. The method of claim 6, further comprising:

counting said plurality of sequential beacon intervals; and

transitioning said node from an extended sleep state to an awake state, in an instance where said plurality of sequential beacon intervals exceeds a predetermined threshold.

14. A method of synchronizing a node moving from a first cluster to a second cluster, said node having a sleeping protocol, the method comprising:

receiving, during an awake state of operation, a first beacon signal originating from a first cluster-head respectively associated with said first cluster, said beacon signal comprising a plurality of sequential beacon intervals, wherein said beacon intervals each comprises a plurality of time slots associated with groups of nodes in said first cluster;

sequentially transitioning between an awake state and a sleep state of operation associated with said first beacon signal;

during a subsequent awake state of operation, receiving a second beacon signal originates from said second cluster;

recording information associated with said second beacon signal;

staying in said awake state for a period exceeding a beacon interval of said second beacon signal; and

synchronizing with said second beacon signal of said second cluster.

15. The method of claim 14, further comprising:

sequentially transitioning between an awake state and a sleep state of operation associated with said second beacon signal.

16. The method of claim 15, wherein said node is out of range for receiving said first beacon signal.

17. The method of claim 15, wherein said node returns to said sleeping state in an instance where said second beacon signal is not received during an awake state of operation.

18. A method of transferring data from a first node to a second node, at least one of the two nodes having a sleeping protocol, the method comprising:

transitioning said first node to an active state of operation;

setting a message count clock to zero;

sending a message from said first node to said second node;

in an instance where said second node does not send an acknowledgement message, repeating said message a number of times until a message sent threshold has been exceeded;

determining when said second node is in an awake mode; and

sending said message from said first node to said second node in an instance where said second node is in said awake mode.

19. The method of claim 18, wherein said message comprises a request to send (RTS) message and said acknowledgement message comprises a clear to send (CTS) message.

20. The method of claim 18, wherein said message is a traffic indication message (TIM).

21. The method of claim 18, further comprising:

determining whether said second node has changed from a first cluster to a second cluster; and

obtaining timing information for said second node in an instance where said second node changed clusters.

22. The method of claim 21, wherein said obtaining timing information comprises:

sending said timing information from a cluster-head associated with said second cluster to a cluster-head associated with said first cluster.

23. The method of claim 18, further comprising:

determining whether said second node has changed from a first cluster to a second cluster; and

obtaining routing information for said second node in an instance where said second node changed clusters.