Clustering based load adaptive sleeping protocol for ad hoc networks

• US 20050117530A1
• Filed: 11/06/2003
• Published: 06/02/2005
• Est. Priority Date: 11/06/2003
• Status: Active Grant

• Current Assignee: RPX Corporation
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Abraham, Santosh P., Chuah, Mooi Choo
• Granted Patent: US 7,298,716 B2
• Time in Patent Office: Days
• US Class Current: 370/310
• 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, wherein said beacon intervals each comprise a plurality of time slots associated with groups of nodes in said cluster.

2. The sleeping protocol of claim 1, 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.

3. The sleeping protocol of claim 2, wherein said time slots are sequentially numbered zero to n.

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

5. The sleeping protocol of claim 4, 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.

6. The sleeping protocol of claim 5, 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.

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

8. A method of adapting a sleeping protocol of a node in a cluster of a node based on traffic patterns of said node, said method comprising:

sequentially transitioning between an awake state and a sleep state of operation;

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 time for each successive transition cycle, in an instance where no messages are receive during a previous transition cycle.

9. The method of claim 8, further comprising:

determining whether said node has been in an idle state greater than a predetermined threshold;

transitioning to said sleep state in an instance said predetermined threshold has been exceeded; and

transitioning to said awake state for a predefined time after said transitioning to a sleep state.

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

11. The method of claim 8, 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 time for each successive transition cycle, in an instance where said count exceeds said predetermined count threshold and no messages are receive during a previous transition cycle.

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

providing a beacon signal originating from a cluster-head of a cluster, said beacon signal comprising a plurality of sequential beacon intervals, wherein said beacon intervals each comprise a plurality of time slots associated with groups of nodes in said cluster.

13. The sleeping protocol of claim 12, 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.

14. The sleeping protocol of claim 13, wherein said time slots are sequentially numbered zero to n.

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

16. The sleeping protocol of claim 15, 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.

17. The sleeping protocol of claim 16, 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.

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

19. The method of claim 12, 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.

20. A method of synchronizing a node moving from a first cluster to a second cluster, 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 comprise 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, wherein said node

21. The method of claim 21, further comprising:

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

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

23. The method of claim 21, 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.

24. A method of transferring data from a first node to a second node, comprising:

transitioning 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 sends 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 node is in said awake mode.

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

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

27. The method of claim 24, further comprising:

determining whether said second node 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.

28. The method of claim 27, 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.

29. The method of claim 24, further comprising:

determining whether said second node 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.