Apparatus, system and method capable of low duty cycle hierarchical AD HOC networks

• US 20060120303A1
• Filed: 12/07/2004
• Published: 06/08/2006
• Est. Priority Date: 12/07/2004
• Status: Active Grant

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Chhabra, Jasmeet, Yarvis, Mark, Kushalnagar, Nandakishore
• Granted Patent: US 7,596,152 B2
• Time in Patent Office: Days
• US Class Current: 370/254
• CPC Class Codes: H04L 12/12 Arrangements for remote connection or disconnection of substations or of equipment thereof
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 45/12 Shortest path evaluation
• CPC Class Codes: H04W 40/02 Communication route or path selection, e.g. power-based or shortest path routing
• CPC Class Codes: H04W 52/0216 using a pre-established activity schedule, e.g. traffic indication frame
• CPC Class Codes: H04W 72/12 Wireless traffic scheduling
• 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

An embodiment of the present invention provides an apparatus, comprising a transceiver capable of dynamic cluster-based sleep/wake scheduling using hierarchical routing, cluster formation, and sleep-wake synchronization. The hierarchical routing may comprise a sink node capable of sending periodic route updates, which may propagate through a network to regular nodes and the route updates may include metrics allowing the regular nodes to select a “best” path to the sink node. The metrics may include hop count or end-to-end reliability and the regular node may track a next hop which optimizes the metric; and packets originating or forwarded by the regular node to the sink node may be sent to the next hop. Further, the route updates may propagate across a backbone network to cluster heads.

Claims

1. An apparatus, comprising:

a transceiver capable of dynamic cluster-based sleep/wake scheduling using hierarchical routing, cluster formation, and sleep-wake synchronization.

2. The apparatus of claim 1, wherein said hierarchical routing comprises a sink node capable of sending periodic route updates, which will propagate through a network to regular nodes.

3. The apparatus of claim 2, wherein said route updates include metrics allowing said regular nodes to select a best path to said sink node.

4. The apparatus of claim 3, wherein said metrics include hop count or end-to-end reliability.

5. The apparatus of claim 3, wherein said regular node tracks a next hop which optimizes said metric and packets originating or forwarded by said regular node to said sink node will be sent to said next hop.

6. The apparatus of claim 2, wherein said route updates propagate across a backbone network to cluster heads.

7. The apparatus of claim 6, wherein said cluster heads that are far from said sink node advertise a favorable metric in their route update thereby attracting neighbors to establish routes through said cluster head.

8. The apparatus of claim 6, wherein said routing in the backbone network is integrated with an underlying mesh network or independent.

9. The apparatus of claim 8, wherein packets from said underlying mesh network are encapsulated as they flow over said backbone.

10. The apparatus of claim 2, wherein said cluster formation comprises a set of nodes that deliver data to said sink through the same cluster head with a routing protocol which allows each node to select a cluster that provides the optimal path of data delivery to said sink according to a routing metric.

11. The apparatus of claim 10, wherein said clusters formed by routing are utilized to coordinate sleep/wake schedules and said node knows the identity of said cluster to which it belongs.

12. The apparatus of claim 11, wherein a field that specifies the cluster head through which the route update flows is added to the route update generated by the routing protocol and when a route update is received by the cluster head, it records its address in this field before forwarding route updates to its neighbors.

13. The apparatus of claim 12, wherein when a route update is received by a regular node that identifies the best route to said sink using a distance-vector protocol, the node records the cluster head'"'"'s address with each cluster being uniquely identified by the cluster head'"'"'s address along with the next hop and metric associated with the best route.

14. The apparatus of claim 1, wherein all nodes in said cluster formation sleep and wake together thereby enabling any node wishing to send data to said sink to send packets over one or more hops to said cluster head without latency or buffering required when a node along the path is asleep.

15. The apparatus of claim 1, wherein said cluster formation'"'"'s sleep/wake cycle is controlled by a cluster head of said cluster formation.

16. The apparatus of claim 15, wherein cluster wake periods are independent and may overlap.

17. The apparatus of claim 1, wherein when said cluster formation is asleep, cluster heads queue data packets destined for nodes in the cluster.

18. The apparatus of claim 17, wherein the wake period is divided into:

a guard band at the start of the wake period;

cluster head forwarding of packets that were queued for the cluster members during the sleep period;

an the active communication phase; and

a synchronization phase where said cluster heads send a synchronization beacon periodically.

19. The apparatus of claim 18, wherein said cluster head sends more than one synchronization beacons during the wake period either to ensure that all nodes receive the beacon, or to revise the wake period.

20. A method of lowering the duty cycle of hierarchical ad hoc networks, comprising:

using hierarchical routing, cluster formation, and sleep-wake synchronization to provide dynamic cluster-based sleep/wake scheduling.

21. The method of claim 20, further comprising using a sink node capable of sending periodic route updates in said hierarchical routing to provide for propagation through a network to regular nodes.

22. The method of claim 21, further comprising allowing said regular nodes to select a “

best”

path to said sink node by using route updates which include metrics.

23. The method of claim 22, further comprising using metrics that include hop count or end-to-end reliability.

24. The method of claim 22, further comprising tracking a next hop by said regular node which optimizes said metric and provides packets originating or forwarded by said regular node to said sink node to be sent to said next hop.

25. The method of claim 21, further comprising propagating said route updates across a backbone network to cluster heads.

26. The method of claim 25, further comprising advertising a favorable metric in their route update by said regular node to said cluster heads that are far from said sink node thereby attracting neighbors to establish routes through said cluster head.

27. The method of claim 25, further comprising integrating said routing in the backbone network with an underlying mesh network.

28. The method of claim 27, further comprising encapsulating packets from said underlying mesh network as they flow over said backbone.

29. The method of claim 21, further comprising delivering data to said sink by a set of nodes within said cluster formation through the same cluster head with a routing protocol which allows each node to select a cluster that provides the optimal path of data delivery to said sink according to a routing metric.

30. The method of claim 29, further comprising utilizing said clusters formed by routing to coordinate sleep/wake schedules and to enable said node to know the identity of said cluster to which it belongs.

31. The method of claim 30, further comprising adding to the route update generated by the routing protocol a field that specifies the cluster head through which the route update flows and when a route update is received by the cluster head, recording its address in this field before forwarding route updates to its neighbors.

32. The method of claim 31, further comprising receiving a route update by a regular node and identifying the best route to said sink by using a distance-vector protocol and along with the next hop and metric associated with the best route, recording by said node the cluster head'"'"'s address with each cluster being uniquely identified by the cluster head'"'"'s address.

33. The method of claim 20, enabling any node wishing to send data to said sink to send packets over one or more hops to said cluster head without latency or buffering when a node along the path is asleep by requiring all nodes in said cluster formation to sleep and wake together.

34. The method of claim 20, further comprising controlling by a cluster head of said cluster formation said cluster formation'"'"'s sleep/wake cycle.

35. The method of claim 34, further comprising allowing said cluster wake periods to be independent and to overlap.

36. The method of claim 20, further comprising, queuing, by said cluster heads, data packets destined for nodes in the cluster when said cluster formation is asleep.

37. The method of claim 36, further comprising dividing the wake period into:

a guard band at the start of the wake period;

cluster head forwarding of packets that were queued for the cluster members during the sleep period;

an active communication phase; and

a synchronization phase where said cluster heads send a synchronization beacon periodically.

38. The method of claim 37, further comprising sending, by said cluster head, more than one synchronization beacon during the wake period either to ensure that all nodes receive the beacon, or to revise the wake period.

39. An article, comprising:

a storage medium having stored thereon instructions, that, when executed by a computing platform results in;

controlling the lowering of the duty cycle of hierarchical ad hoc network by using hierarchical routing, cluster formation, and sleep-wake synchronization to provide dynamic cluster-based sleep/wake scheduling.

40. The article of claim 39, further comprising controlling the use of a sink node capable of sending periodic route updates in said hierarchical routing to provide for propagation through a network to regular nodes.

41. The article of claim 40, wherein said article allows said regular nodes to select a “

best”

path to said sink node by using route updates which include metrics.

42. A system capable of lowering the duty cycle of hierarchical ad hoc networks, comprising:

at least one cluster of nodes, said at least one cluster of nodes including at least one regular node and at least one cluster head in communication with an overlay network; and

at least one sink node in communication with said overlay network wherein said sink node is capable of sending periodic route updates.

43. The system of claim 42, wherein all of said nodes in said at least one cluster sleep and wake together.

44. The system of claim 43, wherein each of said at least one cluster'"'"'s sleep/wake cycle is controlled by said cluster head of that cluster.