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

• US 7,596,152 B2
• Filed: 12/07/2004
• Issued: 09/29/2009
• Est. Priority Date: 12/07/2004
• Status: Expired due to Fees

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Chhabra, Jasmeet, Yarvis, Mark, Kushalnagar, Nandakishore
• Primary Examiner(s): NGUYEN, HANH N
• Application Number:
  US11/006,843
• Publication Number:
  US 20060120303A1
• Time in Patent Office: 1,757 Days
• Field of Search: 370/335, 370/310, 370/311, 370/312, 370/324, 370/328, 370/408, 370/350, 370/351, 370/465, 370/321, 370/329, 370/331, 455/41.2, 455/41.7, 455/450, 455/452.1, 455/553.1, 455/556.2, 340/539.22, 340/539.11
• US Class Current: 370/503
• 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;

wherein said hierarchical muting comprises a sink node capable of sending periodic route updates, which propagate through a network to regular nodes;

wherein said cluster formation comprises a set of nodes that deliver data to said sink node 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 node according to a routing metric;

wherein said clusters formed by routing are utilized to coordinate sleep/wake schedules and a node knows the identity of said cluster to which it belongs;

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, said cluster head records said cluster head'"'"'s address in this field before forwarding route updates to said cluster head'"'"'s neighbors; and

wherein when a route update is received by a regular node that identifies the best route to said sink node 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.

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

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

4. The apparatus of claim 2, 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 be sent to said next hop.

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

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

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

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

9. 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.

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

11. The apparatus of claim 10, wherein cluster wake periods are independent and overlap.

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

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

14. The apparatus of claim 13, 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.

15. 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;

using a sink node capable of sending periodic route updates in said hierarchical routing to provide for propagation through a network to regular nodes;

delivering data to said sink node 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 node according to a routing metric;

utilizing said clusters formed by routing to coordinate sleep/wake schedules and to enable a node to know the identity of said cluster to which it belongs; and

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 said cluster head'"'"'s address in this field before forwarding the route updates to said cluster head'"'"'s neighbors; and

receiving a route update by a regular node and identifying the best route to said sink node 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.

16. The apparatus of claim 15, further comprising allowing said regular nodes to select a “

best”

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

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

18. The method of claim 16, 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.

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

20. The method of claim 19, further comprising advertising a favorable metric in route update by said regular node to said cluster beads that are far from said sink node thereby attracting neighbors to establish routes though said cluster head.

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

22. The method of claim 21, further comprising encapsulating packets from said underlying mesh network as flow over said backbone.

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

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

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

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

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

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