Methods and apparatuses for routing data in a personal area network

• US 7,564,842 B2
• Filed: 07/01/2004
• Issued: 07/21/2009
• Est. Priority Date: 07/02/2003
• Status: Active Grant

• Current Assignee: ARRIS Enterprises LLC (CommScope Holding Company, Inc.), Intel Corporation, Mitsubishi Electric Research Laboratories, Inc. (Mitsubishi Electric Corporation), NXP B.V. (NXP Semiconductors NV), Samsung Electronics Co. Ltd.
• Original Assignee: Intel Corporation, Mitsubishi Electric Research Laboratories, Inc. (Mitsubishi Electric Corporation), Motorola, Inc. (Motorola Solutions, Inc.), NXP B.V. (NXP Semiconductors NV), Samsung Electronics Co. Ltd.
• Inventors: Sahinoglu, Zafer, Hu, Xuhui, Allen, Vernon Anthony, Orlik, Philip V., Liu, Yong, Chhabra, Jasmeet, Smith, Zachary, Callaway, Jr., Edgar Herbert, Jamieson, Phil, Kling, Ralph M., Lee, Myung J., Hester, Lance Eric, Rudland, Phil, Zhu, Chunhui, Krishnamurthy, Lakshman
• Primary Examiner(s): Sefcheck, Gregory B
• Assistant Examiner(s): Churnet, Dargaye H
• Application Number:
  US10/882,808
• Publication Number:
  US 20050135379A1
• Time in Patent Office: 1,846 Days
• Field of Search: None
• US Class Current: 370/389
• CPC Class Codes: H04L 45/48 Routing tree calculation
• CPC Class Codes: H04L 45/52 Multiprotocol routers
• CPC Class Codes: H04W 40/02 Communication route or path selection, e.g. power-based or shortest path routing
• CPC Class Codes: H04W 40/24 Connectivity information management, e.g. connectivity discovery or connectivity update
• CPC Class Codes: H04W 52/02 Power saving arrangements in wired systems H04L12/12; signaling of mobile application services, e.g. low battery notifications H04W4/20
• CPC Class Codes: H04W 52/0216 using a pre-established activity schedule, e.g. traffic indication frame
• CPC Class Codes: H04W 84/10 Small scale networks; Flat hierarchical networks
• CPC Class Codes: Y02D 30/70 in wireless communication networks

Abstract

The disclosure is a routing method for data in a personal area network. The personal area network includes a plurality of nodes. The method includes receiving a frame at a node, determining whether the node contains a routing table entry for the frame destination, and when the node contains a routing table entry, determining a route for the frame based on a first routing protocol. The method further includes, when the node does not contain a routing table entry for the frame destination, determining whether a route should be discovered for the frame destination, and when a route should not be discovered, determining a route for the frame based on a second routing protocol.

Claims

1. A communication protocol for a personal area network, said protocol comprising the steps of:

receiving a frame at a node;

selecting a routing protocol based on content of said frame and on resources of said node, wherein selecting said routing protocol further comprises the steps of;

evaluating a destination address of the frame to determine whether said frame is to be broadcast;

when said destination address is a broadcast address, broadcasting said frame;

when said destination address is a non-broadcast address, determining whether a routing table entry exists for the destination address;

when a routing table entry exists for the destination address, determining a route for said frame based on a table-based routing protocol; and

when a routing table entry does not exist for the destination of said frame, evaluating a route discovery flag in said content of said frame and evaluating the resources of said node to determine a route for said frame; and

routing said frame according to the selected routing protocol.

2. The communication protocol of claim 1, wherein said resources comprise at least one of memory capacity and power capacity.

3. The communication protocol of claim 1, wherein said communication protocol further comprises the steps of:

initiating a route discovery process based on a route discovery procedure when said route discovery flag is in a first state and said node has sufficient resources available for route discovery, and determining a route for said frame based on a tree-based protocol if route discovery flag is evaluated to be in a second state or said node has insufficient resources.

4. The communication protocol of claim 3, wherein said route discovery procedure comprises the steps of:

determining whether said node has routing capacity;

determining whether the frame was received along a valid tree path;

determining whether a source address of said frame is stored within said node;

determining a destination address of said frame; and

when said node is determined to have routing capacity, said source address of said frame is not stored within said node, and said node is not the destination of said frame,

creating a table entry for said source address within said node, calculating a path cost to the destination address, and unicasting said frame towards said destination address.

5. The communication protocol of claim 4, wherein said calculating a path cost to the destination address comprises:

adding a link cost from a previous node that transmitted said frame to a path cost stored in said frame.

6. The communication protocol of claim 4, wherein said node is determined to have routing capacity, said source address of said frame is not stored within said node, and said node is the destination address of said frame, said route discovery procedure further comprising issuing a route reply frame to a source of said frame.

7. The communication protocol of claim 4, wherein said node is determined to have routing capacity, and the source address of said frame is stored within said node, said route discovery procedure further comprises the steps of:

comparing a path cost stored in the frame with a table path cost stored within said node;

when said path cost stored in the frame is greater than said table path cost, discarding said frame; and

when said path cost stored in the frame is less than said table path cost and said node is the destination address of said frame, replacing a table path stored within said node with a path stored in said frame and issuing a route reply frame to the source address of said frame.

8. The communication protocol of claim 7, wherein the path cost stored in the frame is less than said table path cost and wherein said node is not the destination address of said frame, said route discovery procedure further comprises the steps of:

replacing the table path stored within said node with the path stored in said frame and unicasting said frame towards said destination address.

9. The communication protocol of claim 4, wherein said node is determined not to have routing capacity and wherein said frame is not received along said valid tree path, said route discovery procedure further comprising discarding said frame.

10. The communication protocol of claim 4, wherein said node is determined not to have routing capacity, said frame is received along a valid tree path, and said node is not the destination address of said frame, said route discovery procedure further comprising the steps of:

calculating a path cost to the destination address and unicasting said frame towards said destination address.

11. The communication protocol of claim 4, wherein said node is determined not to have routing capacity, said frame is received along a valid tree path and said node is the destination address of said frame, said route discovery procedure further comprising issuing a route reply frame to a source of said frame.

12. The communication protocol of claim 3, wherein said frame is a route reply frame, said route discovery procedure comprises the steps of:

determining whether said node has routing capacity;

determining whether a source address of said route reply frame is stored within said node;

determining a destination address of said at least one route reply frame; and

when said node is determined not to have routing capacity and said node is not destination of said route reply frame, updating a path cost in said route reply frame and forwarding said route reply frame.

13. The communication protocol of claim 12, wherein when said node is determined not to have routing capacity and said node is the destination of said route request frame;

wherein when said node is determined to have routing capacity, said node is the destination of said route reply frame, and source address of said route reply frame is not stored within said node;

or wherein when said node is determined to have routing capacity, said node is not the destination of said route reply frame, and source address of said route reply frame is not stored within said node;

said route discovery procedure further comprises discarding said route reply frame.

14. The communication protocol of claim 12, wherein when said node is determined to have routing capacity, said node is not destination of said route reply frame, and source address of said route reply frame is stored within said node;

said route discovery procedure further comprising the steps of;

comparing said path cost in said route reply frame with a table path cost stored within said node; and

when said path cost in said route reply frame is greater than said table path cost, discarding the route reply frame.

15. The communication protocol of claim 14, wherein said path cost in said route reply frame is less than said table path cost, said route discovery procedure further comprising the steps of:

replacing a routing table hop field address in said node with an address of a node, that forwarded said route reply frame;

replacing a forward residual cost in said node with a value stored in said route reply frame;

updating said path cost in said route reply frame; and

forwarding said route reply frame.

16. The communication protocol of claim 12, wherein said node is determined to have routing capacity, said node is destination of said route request frame, and source address of said route request frame is stored within said node;

said route discovery procedure further comprising the steps of;

determining whether a status field of a routing table entry is active; and

when said status field of the routing table entry is not active, changing said status field of routing table entry to active and replacing table path cost in said node with path cost in route reply frame.

17. The communication protocol of claim 16, wherein the status field of the routing table entry is active, said route discovery procedure further comprising the steps:

comparing said path cost in route reply frame with table path cost in said node; and

when said path cost in said route reply frame is greater than table path cost in said node, discarding said route reply frame.

18. The communication protocol of claim 17, wherein when said path cost in route request frame is less than table path cost in said node, said route discovery procedure further comprising the steps of:

replacing said table path cost in said node with said path cost in said route reply frame; and

replacing said table next hop field address in said node with a next hop address stored in said route reply frame.

19. The communication protocol of claim 1, wherein said node is one of a network coordinator node, a fully functional node, or a reduced function node.

20. The communication protocol of claim 1, wherein said personal area network is one of a tree, star, or hybrid topology network.

21. The communication protocol of claim 1, wherein the evaluating the resources of said node comprises determining whether said node is one of a network coordinator node, a fully functional node, or a reduced function node.

22. The communication protocol of claim 1, wherein said table-based routing protocol comprises an ad hoc on demand distance vector routing protocol.

23. A system for communicating within a personal area network, said system comprising:

at least one source node for transmitting a frame;

at least one first intermediate node for advancing the frame to at least one of a second intermediate node and a destination node, wherein said first intermediate node is configured to;

receive the frame;

select a routing protocol based on content of said frame and on resources of said first intermediate node, wherein selecting said routing protocol the first intermediate node is further configured to;

evaluate a destination address of the frame to determine whether said frame is to be broadcast;

when said destination address is a broadcast address, broadcast said frame;

when said destination address is a non-broadcast address, determine whether a routing table entry exists for the destination address;

when a routing table entry exists for the destination address, determine a route for said frame based on a table-based routing protocol; and

when a routing table entry does not exist for the destination of said frame, evaluate a route discovery flag in said content of said frame and evaluate the resources of said first intermediate node to determine a route for said frame; and

route said frame according to the selected routing protocol;

and said at least one destination node.

24. The system of claim 23, wherein said first intermediate node is further configured to:

initiate a route discovery process based on a route discovery procedure when said route discovery flag is in a first state and said node has sufficient resources available for route discovery, and determine a route for said frame based on a tree-based protocol if route discovery flag is evaluated to be in a second state or said node has insufficient resources.

25. The system of claim 23, wherein when said first intermediate node is one of a network coordinator node, a fully functional node, or a reduced function node.

26. The system of claim 23, wherein said personal area network is one of a tree, star, or hybrid topology network.

27. The system of claim 23, wherein the evaluating the resources of said first intermediate node comprises determining whether the first intermediate node is one of a network coordinator node, a fully functional node, or a reduced function node.

28. The system of claim 23, wherein said resources comprise at least one of memory capacity and power capacity.

29. The system of claim 23, wherein said table-based routing protocol comprises an ad hoc on demand distance vector routing protocol.

30. A communication node within a personal area network comprising:

means for receiving a frame;

means for selecting a routing protocol based on content of said frame and on resources of said node, wherein the means for selecting said routing protocol further comprises;

means for evaluating a destination address of the frame to determine whether said frame is to be broadcast;

when said destination address is a broadcast address, means for broadcasting said frame;

when said destination address is a non-broadcast address, means for determining whether a routing table entry exists for the destination address;

when a routing table entry exists for the destination address, means for determining a route for said frame based on a table-based routing protocol; and

when a routing table entry does not exist for the destination of said frame, means for evaluating a route discovery flag in said content of said frame and means for evaluating the resources of said node to determine a route for said frame;

and means for routing said frame according to the selected routing protocol.

31. The communication node of claim 30, wherein said resources comprise at least one of memory capacity and power capacity.

32. The communication node of claim 30, wherein said table-based routing protocol comprises an ad hoc on demand distance vector routing protocol.

33. The communication node of claim 30, wherein said communication node further comprises:

means for initiating a route discovery process based on a route discovery procedure when said route discovery flag is in a first state and said node has sufficient resources available for route discovery, and means for determining a route for said frame based on a tree-based protocol if route discovery flag is evaluated to be in a second state or said node has insufficient resources.

34. The communication node of claim 33, wherein said communication node further comprises:

means for determining whether said node has routing capacity;

means for determining whether the frame was received along a valid tree path;

means for determining whether a source address of said frame is stored within said node;

means for determining a destination address of said frame; and

when said node is determined to have routing capacity, said source address of said frame is not stored within said node, and said node is not the destination of said frame,

means for creating a table entry for said source address within said node, means for calculating a path cost to the destination address, and means for unicasting said frame towards said destination address.

35. The communication node of claim 34, wherein said calculating a path cost to the destination address comprises:

means for adding a link cost from a previous node that transmitted said frame to a path cost stored in said frame.

36. The communication node of claim 34, wherein said node is determined to have routing capacity, said source address of said frame is not stored within said node, and said node is the destination address of said frame, said node further comprising a means for issuing a route reply frame to a source of said frame.

37. The communication node of claim 34, wherein said node is determined to have routing capacity, and the source address of said frame is stored within said node, said node further comprises:

means for comparing a path cost stored in the frame with a table path cost stored within said node;

when said path cost stored in the frame is greater than said table path cost, means for discarding said frame; and

when said path cost stored in the frame is less than said table path cost and said node is the destination address of said frame, means for replacing a table path stored within said node with a path stored in said frame and means for issuing a route reply frame to the source address of said frame.

38. The communication node of claim 37, wherein the path cost stored in the frame is less than said table path cost and wherein said node is not the destination address of said frame, said node further comprises:

means for replacing the table path stored within said node with the path stored in said frame and means for unicasting said frame towards said destination address.

39. The communication node of claim 34, wherein said node is determined not to have routing capacity and wherein said frame is not received along said valid tree path, said node further comprising a means for discarding said frame.

40. The communication node of claim 34, wherein said node is determined not to have routing capacity, said frame is received along a valid tree path, and said node is not the destination address of said frame, said node further comprising:

means for calculating a path cost to the destination address and means for unicasting said frame towards said destination address.

41. The communication node of claim 34, wherein said node is determined not to have routing capacity, said frame is received along a valid tree path and said node is the destination address of said frame, said node further comprising means for issuing a route reply frame to a source of said frame.

42. The communication node of claim 33, wherein said frame is a route reply frame, said node comprises:

means for determining whether said node has routing capacity;

means for determining whether a source address of said route reply frame is stored within said node;

means for determining a destination address of said at least one route reply frame; and

when said node is determined not to have routing capacity and said node is not destination of said route reply frame, means for updating a path cost in said route reply frame and means for forwarding said route reply frame.

43. The communication node of claim 42, wherein when said node is determined not to have routing capacity and said node is the destination of said route request frame;

wherein when said node is determined to have routing capacity, said node is the destination of said route reply frame, and source address of said route reply frame is not stored within said node;

or wherein when said node is determined to have routing capacity, said node is not the destination of said route reply frame, and source address of said route reply frame is not stored within said node;

said node further comprises a means for discarding said route reply frame.

44. The communication node of claim 42, wherein when said node is determined to have routing capacity, said node is not destination of said route reply frame, and source address of said route reply frame is stored within said node;

said node further comprising;

means for comparing said path cost in said route reply frame with a table path cost stored within said node; and

when said path cost in said route reply frame is greater than said table path cost, means for discarding the route reply frame.

45. The communication node of claim 44, wherein said path cost in said route reply frame is less than said table path cost, said node further comprising:

means for replacing a routing table hop field address in said node with an address of a node, that forwarded said route reply frame;

means for replacing a forward residual cost in said node with a value stored in said route reply frame;

means for updating said path cost in said route reply frame; and

means for forwarding said route reply frame.

46. The communication node of claim 42, wherein said node is determined to have routing capacity, said node is destination of said route request frame, and source address of said route request frame is stored within said node;

said node further comprising;

means for determining whether a status field of a routing table entry is active; and

when said status field of the routing table entry is not active, means for changing said status field of routing table entry to active and means for replacing table path cost in said node with path cost in route reply frame.

47. The communication node of claim 46, wherein the status field of the routing table entry is active, said node further comprising:

means for comparing said path cost in route reply frame with table path cost in said node; and

when said path cost in said route reply frame is greater than table path cost in said node, means for discarding said route reply frame.

48. The communication node of claim 47, wherein when said path cost in route request frame is less than table path cost in said node, said node further comprising:

means for replacing said table path cost in said node with said path cost in said route reply frame; and

means for replacing said table next hop field address in said node with a next hop address stored in said route reply frame.

49. The communication node of claim 30, wherein said node is one of a network coordinator node, a fully functional node, or a reduced function node.

50. The communication node of claim 30, wherein said personal area network is one of a tree, star, or hybrid topology network.

51. The communication node of claim 30, wherein the means for evaluating the resources of said node comprises a means to determine whether the node is one of a network coordinator node, a fully functional node, or a reduced function node.

52. The communication node of claim 30, wherein said resources comprise at least one of memory capacity and power capacity.

53. The communication node of claim 30, wherein said table-based routing protocol comprises an ad hoc on demand distance vector routing protocol.