Method, system, node, computer program product and communication packet for communicating information in an ad-hoc hierarchically addressed communication network

• US 20060034191A1
• Filed: 08/16/2004
• Published: 02/16/2006
• Est. Priority Date: 08/16/2004
• Status: Active Grant

• Current Assignee: Renesas Electronics Corporation
• Original Assignee: Renesas Technology Corporation (Renesas Electronics Corporation)
• Inventors: Sahinoglu, Zafer, Ding, Gang
• Granted Patent: US 7,573,835 B2
• Time in Patent Office: Days
• US Class Current: 370/254
• CPC Class Codes: H04L 45/32 Flooding denial of service attacks H04L63/1458
• CPC Class Codes: H04W 40/00 Communication routing or communication path finding
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks

Abstract

A method of communicating information in a communication network with a plurality of hierarchically addressed nodes includes receiving communication packets identifying 1-hop neighbor node addresses, a number of on-tree neighbors of neighbor nodes transmitting the received packets, and forwarding node addresses of forwarding nodes from which information in the received packets are to be rebroadcast. Further, the method includes identifying each 1-hop neighbor node which should be a forwarding node based on stored addresses and numbers of on-tree neighbors, and producing and transmitting a rebroadcast packet including addresses of forwarding nodes. A communication network system, a communication node in a communication network, and a computer program product include similar features. Communication packets embodied in an electromagnetic wave includes an address, a number of on-tree neighbors of neighbor nodes, and forwarding nodes from which the packets are to be rebroadcast.

Claims

1. A method of communicating information in a communication network including a plurality of hierarchically addressed nodes, comprising:

(a) receiving at a current node communication packets transmitted from 1-hop neighbor nodes within a communication range of the current node, said communication packets identifying (1) 1-hop neighbor node addresses of the respective 1-hop neighbor nodes transmitting the packets, (2) a number defining how many on-tree neighbor nodes have a child or parent hierarchical relationship with the respective 1-hop neighbor nodes transmitting the packets, and (3) forwarding node addresses of forwarding nodes from which the received packets are to be rebroadcast;

(b) storing said 1-hop neighbor node addresses and said number of on-tree neighbor nodes;

(c) when a received packet at the current node identifies the current node as a forwarding node which should rebroadcast the received packet, identifying based on the stored 1-hop neighbor addresses and the stored number of on-tree neighbor nodes, each 1-hop neighbor node which should be a forwarding node instructed to rebroadcast information included in a communication packet received from the current node;

(d) producing at the current node a rebroadcast communication packet including information to be rebroadcast, an address of the current node, and addresses of forwarding nodes identified in step (c) when the received packet at the current node identifies the current node as a forwarding node which should rebroadcast the received information; and

(e) transmitting from the current node the rebroadcast communication packet produced in step (d).

2. The method of claim 1, further comprising:

producing at the current node a communication packet identifying a number defining how many 1-hop neighbor nodes have a child or parent hierarchical relationship with the current node; and

transmitting the communication packet identifying the defined number of 1-hop neighbor nodes having a child or parent hierarchical relationship with the current node.

3. The method of claim 1, wherein step (a) comprises:

(a-1) receiving at the current node non-directed communication packets from 1-hop neighbor nodes, including information intended to be received by each node in the plurality of hierarchically addressed nodes, said 1-hop neighbor addresses of the respective 1-hop neighbor nodes transmitting the non-directed packets, and said forwarding node addresses of forwarding nodes from which the information in received non-directed packets are to be rebroadcast; and

(a-2) receiving at the current node directed communication packets including information intended to be received by a subset of nodes in the plurality of hierarchically addressed nodes, said 1-hop neighbor addresses of the respective 1-hop neighbor nodes transmitting the directed packets, and said number defining how many on-tree neighbor nodes have a child or parent hierarchical relationship with the respective 1-hop neighbor nodes transmitting the packets.

4. The method of claim 3, further comprising:

storing a broadcast indication for the respective 1-hop neighbor nodes transmitting the non-directed packets,

wherein the identifying in step (c) is further based on the stored broadcast indication for each 1-hop neighbor node.

5. The method of claim 1, further comprising:

identifying on-tree neighbor nodes having a hierarchical parent or child relationship with each 1-hop neighbor node; and

determining, for each 1-hop neighbor node and each identified on-tree neighbor node, a hierarchical level indicating a number of nodes between a respective node and a root node,

wherein the identifying in step (c) is further based on the determined hierarchical level.

6. The method of claim 5, wherein the step of identifying on-tree neighbor nodes further comprises:

excluding 1-hop neighbor nodes of the current node from the identified on-tree neighbor nodes considered in the determining in step (c).

7. The method of claim 5, wherein step (c) comprises:

(c-1) identifying a 1-hop neighbor node as a forwarding node if the 1-hop neighbor node is a parent node of an identified on-tree neighbor node;

(c-2) excluding the parent node and other child nodes of the 1-hop neighbor node identified in step (c-1) from the identified on-tree neighbor nodes considered in the determining step (c).

8. The method of claim 5, wherein step (c) comprises:

(c-1) identifying a 1-hop neighbor node as a forwarding node if the 1-hop neighbor node is a child node of an identified on-tree neighbor node and the identified on-tree neighbor node is not a 1-hop neighbor node of the current node.

9. The method of claim 2, wherein step (a) comprises:

(a-1) receiving at the current node non-directed communication packets from 1-hop neighbor nodes, including information intended to be received by each node in the plurality of hierarchically addressed nodes, said 1-hop neighbor addresses of the respective 1-hop neighbor nodes transmitting the non-directed packets, and said forwarding node addresses of forwarding nodes from which the information in received non-directed packets are to be rebroadcast; and

(a-2) receiving at the current node directed communication packets including information intended to be received by a subset of nodes in the plurality of hierarchically addressed nodes, said 1-hop neighbor addresses of the respective 1-hop neighbor nodes transmitting the directed packets, and said number defining how many on-tree neighbor nodes have a child or parent hierarchical relationship with the respective 1-hop neighbor nodes transmitting the packets.

10. The method of claim 9, further comprising:

storing a broadcast indication for the respective 1-hop neighbor nodes transmitting the non-directed packets,

wherein the identifying in step (c) is further based on the stored broadcast indication for each 1-hop neighbor node.

11. The method of claim 2, further comprising:

identifying on-tree neighbor nodes having a hierarchical parent or child relationship with each 1-hop neighbor node; and

determining, for each 1-hop neighbor node and each identified on-tree neighbor node, a hierarchical level indicating a number of nodes between a respective node and a root node,

wherein the identifying in step (c) is further based on the determined hierarchical level.

12. The method of claim 11, wherein the step of identifying on-tree nodes further comprises:

excluding 1-hop neighbor nodes of the current node from the identified on-tree neighbor nodes considered in the determining in step (c).

13. The method of claim 11, wherein step (c) comprises:

(c-1) identifying a 1-hop neighbor node as a forwarding node if the 1-hop neighbor node is a parent node of an identified on-tree neighbor node;

(c-2) excluding the parent node and other child nodes of the 1-hop neighbor node identified in step (c-1) from the identified on-tree neighbor nodes considered in the determining step (c).

14. The method of claim 11, wherein step (c) comprises:

(c-1) identifying a 1-hop neighbor node as a forwarding node if the 1-hop neighbor node is a child node of an identified on-tree neighbor node and the identified on-tree neighbor node is not a 1-hop neighbor node of the current node.

15. The method of claim 3, further comprising:

identifying on-tree neighbor nodes having a hierarchical parent or child relationship with each 1-hop neighbor node; and

determining, for each 1-hop neighbor node and each identified on-tree neighbor node, a hierarchical level indicating a number of nodes between a respective node and a root node,

wherein the identifying in step (c) is further based on the determined hierarchical level.

16. The method of claim 15, wherein the step of identifying on-tree nodes further comprises:

excluding 1-hop neighbor nodes of the current node from the identified on-tree neighbor nodes considered in the determining in step (c).

17. The method of claim 15, wherein step (c) comprises:

(c-1) identifying a 1-hop neighbor node as a forwarding node if the 1-hop neighbor node is a parent node of an identified on-tree neighbor node;

(c-2) excluding the parent node and other child nodes of the 1-hop neighbor node identified in step (c-1) from the identified on-tree neighbor nodes considered in the determining step (c).

18. The method of claim 15, wherein step (c) comprises:

(c-1) identifying a 1-hop neighbor node as a forwarding node if the 1-hop neighbor node is a child node of an identified on-tree neighbor node and the identified on-tree neighbor node is not a 1-hop neighbor node of the current node.

19. The method of claim 4, further comprising:

identifying on-tree neighbor nodes having a hierarchical parent or child relationship with each 1-hop neighbor node; and

determining, for each 1-hop neighbor node and each identified on-tree neighbor node, a hierarchical level indicating a number of nodes between a respective node and a root node,

wherein the identifying in step (c) is further based on the determined hierarchical level.

20. The method of claim 19, wherein the step of identifying on-tree nodes further comprises:

excluding 1-hop neighbor nodes of the current node from the identified on-tree neighbor nodes considered in the determining in step (c).

21. The method of claim 19, wherein step (c) comprises:

(c-1) identifying a 1-hop neighbor node as a forwarding node if the 1-hop neighbor node is a parent node of an identified on-tree neighbor node;

(c-2) excluding the parent node and other child nodes of the 1-hop neighbor node identified in step (c-1) from the identified on-tree neighbor nodes considered in the determining step (c).

22. The method of claim 19, wherein step (c) comprises:

(c-1) identifying a 1-hop neighbor node as a forwarding node if the 1-hop neighbor node is a child node of an identified on-tree neighbor node and the identified on-tree neighbor node is not a 1-hop neighbor node of the current node.

23. The method of claim 9, further comprising:

identifying on-tree neighbor nodes having a hierarchical parent or child relationship with each 1-hop neighbor node; and

determining, for each 1-hop neighbor node and each identified on-tree neighbor node, a hierarchical level indicating a number of nodes between a respective node and a root node,

wherein the identifying in step (c) is further based on the determined hierarchical level.

24. The method of claim 23, wherein the step of identifying on-tree nodes further comprises:

excluding 1-hop neighbor nodes of the current node from the identified on-tree neighbor nodes considered in the determining in step (c).

25. The method of claim 23, wherein step (c) comprises:

(c-1) identifying a 1-hop neighbor node as a forwarding node if the 1-hop neighbor node is a parent node of an identified on-tree neighbor node;

(c-2) excluding the parent node and other child nodes of the 1-hop neighbor node identified in step (c-1) from the identified on-tree neighbor nodes considered in the determining step (c).

26. The method of claim 23, wherein step (c) comprises:

(c-1) identifying a 1-hop neighbor node as a forwarding node if the 1-hop neighbor node is a child node of an identified on-tree neighbor node and the identified on-tree neighbor node is not a 1-hop neighbor node of the current node.

27. The method of claim 10, further comprising:

identifying on-tree neighbor nodes having a hierarchical parent or child relationship with each 1-hop neighbor node; and

determining, for each 1-hop neighbor node and each identified on-tree neighbor node, a hierarchical level indicating a number of nodes between a respective node and a root node,

wherein the identifying in step (c) is further based on the determined hierarchical level.

28. The method of claim 27, wherein the step of identifying on-tree nodes further comprises:

excluding 1-hop neighbor nodes of the current node from the identified on-tree neighbor nodes considered in the determining in step (c).

29. The method of claim 27, wherein step (c) comprises:

(c-1) identifying a 1-hop neighbor node as a forwarding node if the 1-hop neighbor node is a parent node of an identified on-tree neighbor node;

(c-2) excluding the parent node and other child nodes of the 1-hop neighbor node identified in step (c-1) from the identified on-tree neighbor nodes considered in the determining step (c).

30. The method of claim 27, wherein step (c) comprises:

(c-1) identifying a 1-hop neighbor node as a forwarding node if the 1-hop neighbor node is a child node of an identified on-tree neighbor node and the identified on-tree neighbor node is not a 1-hop neighbor node of the current node.

31. A communication network system comprising:

a plurality of hierarchically addressed nodes, each of said nodes including

a receiving section configured to receive at a current node communication packets transmitted from 1-hop neighbor nodes within a communication range of the current node, said communication packets identifying (1) 1-hop neighbor node addresses of the respective 1-hop neighbor nodes transmitting the packets, (2) a number defining how many on-tree neighbor nodes have a child or parent hierarchical relationship with the respective 1-hop neighbor nodes transmitting the packets, and (3) forwarding node addresses of forwarding nodes from which the received packets are to be rebroadcast,

a storing section configured to store said 1-hop neighbor node addresses and said number of on-tree neighbor nodes,

an identifying section, when a received packet at the current node identifies the current node as a forwarding node which should rebroadcast the received packet, configured to identify based on the stored 1-hop neighbor node addresses and the stored number of on-tree neighbor nodes, each 1-hop neighbor node which should be a forwarding node instructed to rebroadcast a communication packet received from the current node,

a producing section configured to produce at the current node a rebroadcast communication packet including information to be rebroadcast, an address of the current node, and addresses of forwarding nodes identified in the identifying section when the received packet at the current node identifies the current node as a forwarding node which should rebroadcast the received information, and

a transmitting section configured to transmit the rebroadcast communication packet produced by the producing section.

32. The communication network system of claim 31, wherein each of said nodes further comprises:

a producing section configured to produce at the current node a communication packet identifying a number defining how many 1-hop neighbor nodes have a child or parent hierarchical relationship with the current node; and

a transmitting section configured to transmit the communication packet identifying the defined number of 1-hop neighbor nodes having a child or parent hierarchical relationship with the current node.

33. The communication network system of claim 31, wherein the receiving section comprises:

a non-directed receiving section configured to receive at the current node non-directed communication packets from 1-hop neighbor nodes, including information intended to be received by each node in the plurality of hierarchically addressed nodes, said 1-hop neighbor addresses of the respective 1-hop neighbor nodes transmitting the broadcast packets, and said forwarding node addresses of forwarding nodes from which information in the received non-directed packets are to be rebroadcast; and

a directed receiving section configured to receive at the current node directed communication packets including information intended to be received by a subset of nodes in the plurality of hierarchically addressed nodes, said 1-hop neighbor addresses of the respective 1-hop neighbor nodes transmitting the directed packets, and said number defining how many on-tree neighbor nodes have a child or parent hierarchical relationship with the respective 1-hop neighbor nodes transmitting the packets.

34. The communication network system of claim 33, wherein each of said nodes further comprises:

a storing section configured to store a broadcast indication for the respective 1-hop neighbor nodes transmitting the broadcast packets,

wherein the identifying in the identifying section is further based on the stored broadcast indication for each 1-hop neighbor node.

35. The communication network system of claim 31, wherein each of said nodes further comprises:

an identifying on-tree neighbor nodes section configured to identify on-tree neighbor nodes having a hierarchical parent or child relationship with each 1-hop neighbor node; and

a determining section configured, for each 1-hop neighbor node and each identified on-tree neighbor node, to determine a hierarchical level indicating a number of nodes between a respective node and a root node,

wherein the identifying in the identifying section is further based on the determined hierarchical level.

36. The communication network system of claim 35, wherein the identifying on-tree neighbor nodes section further comprises:

an excluding 1-hop neighbor nodes section configured to exclude 1-hop neighbor nodes of the current node from the identified on-tree neighbor nodes considered in the identifying of the identifying section.

37. The communication network system of claim 35, wherein the identifying section comprises:

an parent node identifying section configured to identify a 1-hop neighbor node as a forwarding node if the 1-hop neighbor node is a parent node of an identified on-tree neighbor node;

an excluding parent and other child nodes section configured to exclude the parent node and other child nodes of the 1-hop neighbor node identified in the parent identifying section from the identified on-tree neighbor nodes considered in the identifying in the identifying section.

38. The communication network system of claim 35, wherein the identifying section comprises:

a child identifying section configured to identify a 1-hop neighbor node as a forwarding node if the 1-hop neighbor node is a child node of an identified on-tree neighbor node and the identified on-tree neighbor node is not a 1-hop neighbor node of the current node.

39. The communication network system of claim 32, wherein the receiving section comprises:

a non-directed receiving section configured to receive at the current node non-directed communication packets from 1-hop neighbor nodes, including information intended to be received by each node in the plurality of hierarchically addressed nodes, said 1-hop neighbor addresses of the respective 1-hop neighbor nodes transmitting the broadcast packets, and said forwarding node addresses of forwarding nodes from which information in the received non-directed packets are to be rebroadcast; and

a directed receiving section configured to receive at the current node directed communication packets including information intended to be received by a subset of nodes in the plurality of hierarchically addressed nodes, said 1-hop neighbor addresses of the respective 1-hop neighbor nodes transmitting the directed packets, and said number defining how many on-tree neighbor nodes have a child or parent hierarchical relationship with the respective 1-hop neighbor nodes transmitting the packets.

40. The communication network system of claim 39, wherein each of said nodes further comprises:

a storing section configured to store a broadcast indication for the respective 1-hop neighbor nodes transmitting the broadcast packets,

wherein the identifying in the identifying section is further based on the stored broadcast indication for each 1-hop neighbor node.

41. The communication network system of claim 32, wherein each of said nodes further comprises:

an identifying on-tree neighbor nodes section configured to identify on-tree neighbor nodes having a hierarchical parent or child relationship with each 1-hop neighbor node; and

a determining section configured, for each 1-hop neighbor node and each identified on-tree neighbor node, to determine a hierarchical level indicating a number of nodes between a respective node and a root node,

wherein the identifying in the identifying section is further based on the determined hierarchical level.

42. The communication network system of claim 41, wherein the identifying on-tree neighbor nodes section further comprises:

an excluding 1-hop neighbor nodes section configured to exclude 1-hop neighbor nodes of the current node from the identified on-tree neighbor nodes considered in the identifying of the identifying section.

43. The communication network system of claim 41, wherein the identifying section comprises:

an parent node identifying section configured to identify a 1-hop neighbor node as a forwarding node if the 1-hop neighbor node is a parent node of an identified on-tree neighbor node;

an excluding parent and other child nodes section configured to exclude the parent node and other child nodes of the 1-hop neighbor node identified in the parent identifying section from the identified on-tree neighbor nodes considered in the identifying in the identifying section.

44. The communication network system of claim 41, wherein the identifying section comprises:

a child identifying section configured to identify a 1-hop neighbor node as a forwarding node if the 1-hop neighbor node is a child node of an identified on-tree neighbor node and the identified on-tree neighbor node is not a 1-hop neighbor node of the current node.

45. The communication network system of claim 33, wherein each of said nodes further comprises:

an identifying on-tree neighbor nodes section configured to identify on-tree neighbor nodes having a hierarchical parent or child relationship with each 1-hop neighbor node; and

a determining section configured, for each 1-hop neighbor node and each identified on-tree neighbor node, to determine a hierarchical level indicating a number of nodes between a respective node and a root node,

wherein the identifying in the identifying section is further based on the determined hierarchical level.

46. The communication network system of claim 45, wherein the identifying on-tree neighbor nodes section further comprises:

an excluding 1-hop neighbor nodes section configured to exclude 1-hop neighbor nodes of the current node from the identified on-tree neighbor nodes considered in the identifying of the identifying section.

47. The communication network system of claim 45, wherein the identifying section comprises:

an parent node identifying section configured to identify a 1-hop neighbor node as a forwarding node if the 1-hop neighbor node is a parent node of an identified on-tree neighbor node;

an excluding parent and other child nodes section configured to exclude the parent node and other child nodes of the 1-hop neighbor node identified in the parent identifying section from the identified on-tree neighbor nodes considered in the identifying in the identifying section.

48. The communication network system of claim 45, wherein the identifying section comprises:

a child identifying section configured to identify a 1-hop neighbor node as a forwarding node if the 1-hop neighbor node is a child node of an identified on-tree neighbor node and the identified on-tree neighbor node is not a 1-hop neighbor node of the current node.

49. The communication network system of claim 34, wherein each of said nodes further comprises:

an identifying on-tree neighbor nodes section configured to identify on-tree neighbor nodes having a hierarchical parent or child relationship with each 1-hop neighbor node; and

a determining section configured, for each 1-hop neighbor node and each identified on-tree neighbor node, to determine a hierarchical level indicating a number of nodes between a respective node and a root node,

wherein the identifying in the identifying section is further based on the determined hierarchical level.

50. The communication network system of claim 49, wherein the identifying on-tree neighbor nodes section further comprises:

an excluding 1-hop neighbor nodes section configured to exclude 1-hop neighbor nodes of the current node from the identified on-tree neighbor nodes considered in the identifying of the identifying section

51. The communication network system of claim 49, wherein the identifying section comprises:

an parent node identifying section configured to identify a 1-hop neighbor node as a forwarding node if the 1-hop neighbor node is a parent node of an identified on-tree neighbor node;

an excluding parent and other child nodes section configured to exclude the parent node and other child nodes of the 1-hop neighbor node identified in the parent identifying section from the identified on-tree neighbor nodes considered in the identifying in the identifying section.

52. The communication network system of claim 49, wherein the identifying section comprises:

a child identifying section configured to identify a 1-hop neighbor node as a forwarding node if the 1-hop neighbor node is a child node of an identified on-tree neighbor node and the identified on-tree neighbor node is not a 1-hop neighbor node of the current node.

53. The communication network system of claim 39, wherein each of said nodes further comprises:

an identifying on-tree neighbor nodes section configured to identify on-tree neighbor nodes having a hierarchical parent or child relationship with each 1-hop neighbor node; and

a determining section configured, for each 1-hop neighbor node and each identified on-tree neighbor node, to determine a hierarchical level indicating a number of nodes between a respective node and a root node,

wherein the identifying in the identifying section is further based on the determined hierarchical level.

54. The communication network system of claim 53, wherein the identifying on-tree neighbor nodes section further comprises:

an excluding 1-hop neighbor nodes section configured to exclude 1-hop neighbor nodes of the current node from the identified on-tree neighbor nodes considered in the identifying of the identifying section.

55. The communication network system of claim 53, wherein the identifying section comprises:

an parent node identifying section configured to identify a 1-hop neighbor node as a forwarding node if the 1-hop neighbor node is a parent node of an identified on-tree neighbor node;

an excluding parent and other child nodes section configured to exclude the parent node and other child nodes of the 1-hop neighbor node identified in the parent identifying section from the identified on-tree neighbor nodes considered in the identifying in the identifying section.

56. The communication network system of claim 53, wherein the identifying section comprises:

a child identifying section configured to identify a 1-hop neighbor node as a forwarding node if the 1-hop neighbor node is a child node of an identified on-tree neighbor node and the identified on-tree neighbor node is not a 1-hop neighbor node of the current node.

57. The communication network system of claim 40, wherein each of said nodes further comprises:

an identifying on-tree neighbor nodes section configured to identify on-tree neighbor nodes having a hierarchical parent or child relationship with each 1-hop neighbor node; and

a determining section configured, for each 1-hop neighbor node and each identified on-tree neighbor node, to determine a hierarchical level indicating a number of nodes between a respective node and a root node,

wherein the identifying in the identifying section is further based on the determined hierarchical level.

58. The communication network system of claim 57, wherein the identifying on-tree neighbor nodes section further comprises:

an excluding 1-hop neighbor nodes section configured to exclude 1-hop neighbor nodes of the current node from the identified on-tree neighbor nodes considered in the identifying of the identifying section.

59. The communication network system of claim 57, wherein the identifying section comprises:

an parent node identifying section configured to identify a 1-hop neighbor node as a forwarding node if the 1-hop neighbor node is a parent node of an identified on-tree neighbor node;

an excluding parent and other child nodes section configured to exclude the parent node and other child nodes of the 1-hop neighbor node identified in the parent identifying section from the identified on-tree neighbor nodes considered in the identifying in the identifying section.

60. The method of claim 57, wherein the identifying section comprises:

a child identifying section configured to identify a 1-hop neighbor node as a forwarding node if the 1-hop neighbor node is a child node of an identified on-tree neighbor node and the identified on-tree neighbor node is not a 1-hop neighbor node of the current node.

61. A node in a communication network that includes a plurality of hierarchically addressed nodes, said node having a current node address and configured to be within a communication range of 1-hop neighbor nodes and in a hierarchical relationship with a number of respective on-tree parent and child nodes and configured to rebroadcast a received packet identifying the current node address as a forwarding node, said node comprising:

a receiving section configured to receive communication packets identifying (1) 1-hop neighbor node addresses of respective 1-hop neighbor nodes transmitting the packets, (2) a number defining how many on-tree neighbor nodes have a child or parent hierarchical relationship with the respective 1-hop neighbor nodes transmitting the packets, and (3) forwarding node addresses of forwarding nodes from which the received packets are to be rebroadcast;

a storing section configured to store said 1-hop neighbor addresses and said number of on-tree neighbor nodes;

an identifying section configured to identify, based on the stored 1-hop neighbor addresses and the stored number of on-tree neighbor nodes, each 1-hop neighbor node which should be a forwarding node instructed to rebroadcast information included in a received communication packet;

a producing section configured to produce a rebroadcast communication packet including information to be rebroadcast, the current node address, and addresses of forwarding nodes identified in the identifying section when the received packet identifies the current node address as a forwarding node which should rebroadcast the received information; and

a transmitting section configured to transmit the produced rebroadcast communication packet.

62. The node of claim 61, wherein the rebroadcast producing section comprises:

a directed producing section configured to produce a directed rebroadcast communication packet identifying the number of respective on-tree parent and child node.

63. The node of claim 61, wherein the receiving section comprises:

a non-directed receiving section configured to receive non-directed communication packets from 1-hop neighbor nodes, including information intended to be received by each node in the plurality of hierarchically addressed nodes, said 1-hop neighbor addresses of the respective 1-hop neighbor nodes transmitting the non-directed packets, and said forwarding node addresses of forwarding nodes from which the information in received non-directed packets are to be rebroadcast; and

a directed receiving section configured to receive directed communication packets including information intended to be received by a subset of nodes in the plurality of hierarchically addressed nodes, said 1-hop neighbor addresses of the respective 1-hop neighbor nodes transmitting the directed packets, and said number defining how many on-tree neighbor nodes have a child or parent hierarchical relationship with the respective 1-hop neighbor nodes transmitting the packets.

64. The node of claim 63 further comprising:

a storing section configured to store a broadcast indication for the respective 1-hop neighbor nodes transmitting the non-directed packets,

wherein the identifying in the identifying section is further based on the stored broadcast indication for each 1-hop neighbor node.

65. The node of claim 61 further comprising:

an identifying on-tree neighbor nodes section configured to identify on-tree neighbor nodes having a hierarchical parent or child relationship with each 1-hop neighbor node; and

a determining section configured, for each 1-hop neighbor node and each identified on-tree neighbor node, to determine a hierarchical level indicating a number of nodes between a respective node and a root node,

wherein the identifying in the identifying section is further based on the determined hierarchical level.

66. The node of claim 65, wherein the identifying on-tree neighbor nodes section further comprises:

an excluding 1-hop neighbor nodes section configured to exclude 1-hop neighbor nodes within the communication range from the identified on-tree neighbor nodes considered in the identifying of the identifying section.

67. The node of claim 65, wherein the identifying section comprises:

a parent and other child nodes identifying section configured to identify a 1-hop neighbor node within the communication range as a forwarding node if the 1-hop neighbor node is a parent node of an identified on-tree neighbor node;

an excluding parent and other child nodes section configured to exclude the parent node and other child nodes of the 1-hop neighbor node identified in the parent identifying section from the identified on-tree neighbor nodes considered in the identifying in the identifying section.

68. The node of claim 65, wherein the identifying section comprises:

a child identifying section configured to identify a 1-hop neighbor node as a forwarding node if the 1-hop neighbor node is a child node of an identified on-tree neighbor node and the identified on-tree neighbor node is not a 1-hop neighbor node within the communication range.

69. The node of claim 62, wherein the receiving section comprises:

a non-directed receiving section configured to receive non-directed communication packets from 1-hop neighbor nodes, including information intended to be received by each node in the plurality of hierarchically addressed nodes, said 1-hop neighbor addresses of the respective 1-hop neighbor nodes transmitting the non-directed packets, and said forwarding node addresses of forwarding nodes from which the information in received non-directed packets are to be rebroadcast; and

a directed receiving section configured to receive directed communication packets including information intended to be received by a subset of nodes in the plurality of hierarchically addressed nodes, said 1-hop neighbor addresses of the respective 1-hop neighbor nodes transmitting the directed packets, and said number defining how many on-tree neighbor nodes have a child or parent hierarchical relationship with the respective 1-hop neighbor nodes transmitting the packets.

70. The node of claim 69 further comprising:

a storing section configured to store a broadcast indication for the respective 1-hop neighbor nodes transmitting the non-directed packets,

wherein the identifying in the identifying section is further based on the stored broadcast indication for each 1-hop neighbor node.

71. The node of claim 62 further comprising:

an identifying on-tree neighbor nodes section configured to identify on-tree neighbor nodes having a hierarchical parent or child relationship with each 1-hop neighbor node; and

a determining section configured, for each 1-hop neighbor node and each identified on-tree neighbor node, to determine a hierarchical level indicating a number of nodes between a respective node and a root node,

wherein the identifying in the identifying section is further based on the determined hierarchical level.

72. The node of claim 71, wherein the identifying on-tree neighbor nodes section further comprises:

an excluding 1-hop neighbor nodes section configured to exclude the 1-hop neighbor nodes within the communication range from the identified on-tree neighbor nodes considered in the identifying of the identifying section.

73. The node of claim 71, wherein the identifying section comprises:

a parent and other child nodes identifying section configured to identify a 1-hop neighbor node within the communication range as a forwarding node if the 1-hop neighbor node is a parent node of an identified on-tree neighbor node;

an excluding parent and other child nodes section configured to exclude the parent node and other child nodes of the 1-hop neighbor node identified in the parent identifying section from the identified on-tree neighbor nodes considered in the identifying in the identifying section.

74. The node of claim 71, wherein the identifying section comprises:

a child identifying section configured to identify a 1-hop neighbor node as a forwarding node if the 1-hop neighbor node is a child node of an identified on-tree neighbor node and the identified on-tree neighbor node is not a 1-hop neighbor node within the communication range.

75. The node of claim 63 further comprising:

an identifying on-tree neighbor nodes section configured to identify on-tree neighbor nodes having a hierarchical parent or child relationship with each 1-hop neighbor node; and

a determining section configured, for each 1-hop neighbor node and each identified on-tree neighbor node, to determine a hierarchical level indicating a number of nodes between a respective node and a root node,

wherein the identifying in the identifying section is further based on the determined hierarchical level.

76. The node of claim 75, wherein the identifying on-tree neighbor nodes section further comprises:

an excluding 1-hop neighbor nodes section configured to exclude the 1-hop neighbor nodes within the communication range from the identified on-tree neighbor nodes considered in the identifying of the identifying section.

77. The node of claim 75, wherein the identifying section comprises:

a parent and other child nodes identifying section configured to identify a 1-hop neighbor node within the communication range as a forwarding node if the 1-hop neighbor node is a parent node of an identified on-tree neighbor node;

an excluding parent and other child nodes section configured to exclude the parent node and other child nodes of the 1-hop neighbor node identified in the parent identifying section from the identified on-tree neighbor nodes considered in the identifying in the identifying section.

78. The node of claim 75, wherein the identifying section comprises:

a child identifying section configured to identify a 1-hop neighbor node as a forwarding node if the 1-hop neighbor node is a child node of an identified on-tree neighbor node and the identified on-tree neighbor node is not a 1-hop neighbor node within the communication range.

79. The node of claim 64 further comprising:

an identifying on-tree neighbor nodes section configured to identify on-tree neighbor nodes having a hierarchical parent or child relationship with each 1-hop neighbor node; and

a determining section configured, for each 1-hop neighbor node and each identified on-tree neighbor node, to determine a hierarchical level indicating a number of nodes between a respective node and a root node,

wherein the identifying in the identifying section is further based on the determined hierarchical level.

80. The node of claim 79, wherein the identifying on-tree neighbor nodes section further comprises:

an excluding 1-hop neighbor nodes section configured to exclude 1-hop neighbor nodes within the communication range from the identified on-tree neighbor nodes considered in the identifying of the identifying section.

81. The node of claim 79, wherein the identifying section comprises:

a parent and other child nodes identifying section configured to identify a 1-hop neighbor node within the communication range as a forwarding node if the 1-hop neighbor node is a parent node of an identified on-tree neighbor node;

an excluding parent and other child nodes section configured to exclude the parent node and other child nodes of the 1-hop neighbor node identified in the parent identifying section from the identified on-tree neighbor nodes considered in the identifying in the identifying section.

82. The node of claim 79, wherein the identifying section comprises:

a child identifying section configured to identify a 1-hop neighbor node as a forwarding node if the 1-hop neighbor node is a child node of an identified on-tree neighbor node and the identified on-tree neighbor node is not a 1-hop neighbor node within the communication range.

83. The node of claim 69 further comprising:

an identifying on-tree neighbor nodes section configured to identify on-tree neighbor nodes having a hierarchical parent or child relationship with each 1-hop neighbor node; and

a determining section configured, for each 1-hop neighbor node and each identified on-tree neighbor node, to determine a hierarchical level indicating a number of nodes between a respective node and a root node,

wherein the identifying in the identifying section is further based on the determined hierarchical level.

84. The node of claim 83, wherein the identifying on-tree neighbor nodes section further comprises:

an excluding 1-hop neighbor nodes section configured to exclude the 1-hop neighbor nodes within the communication range from the identified on-tree neighbor nodes considered in the identifying of the identifying section.

85. The node of claim 83, wherein the identifying section comprises:

a parent and other child nodes identifying section configured to identify a 1-hop neighbor node within the communication range as a forwarding node if the 1-hop neighbor node is a parent node of an identified on-tree neighbor node;

an excluding parent and other child nodes section configured to exclude the parent node and other child nodes of the 1-hop neighbor node identified in the parent identifying section from the identified on-tree neighbor nodes considered in the identifying in the identifying section.

86. The node of claim 83, wherein the identifying section comprises:

a child identifying section configured to identify a 1-hop neighbor node as a forwarding node if the 1-hop neighbor node is a child node of an identified on-tree neighbor node and the identified on-tree neighbor node is not a 1-hop neighbor node within the communication range.

87. The node of claim 70 further comprising:

an identifying on-tree neighbor nodes section configured to identify on-tree neighbor nodes having a hierarchical parent or child relationship with each 1-hop neighbor node; and

a determining section configured, for each 1-hop neighbor node and each identified on-tree neighbor node to determine a hierarchical level indicating a number of nodes between a respective node and a root node,

wherein the identifying in the identifying section is further based on the determined hierarchical level.

88. The node of claim 87, wherein the identifying on-tree neighbor nodes section further comprises:

an excluding 1-hop neighbor nodes section configured to exclude the 1-hop neighbor nodes within the communication range from the identified on-tree neighbor nodes considered in the identifying of the identifying section.

89. The node of claim 87, wherein the identifying section comprises:

a parent and other child nodes identifying section configured to identify a 1-hop neighbor node within the communication range as a forwarding node if the 1-hop neighbor node is a parent node of an identified on-tree neighbor node;

an excluding parent and other child nodes section configured to exclude the parent node and other child nodes of the 1-hop neighbor node identified in the parent identifying section from the identified on-tree neighbor nodes considered in the identifying in the identifying section.

90. The node of claim 87, wherein the identifying section comprises:

a child identifying section configured to identify a 1-hop neighbor node as a forwarding node if the 1-hop neighbor node is a child node of an identified on-tree neighbor node and the identified on-tree neighbor node is not a 1-hop neighbor node within the communication range.

91. A computer program product storing computer program instructions which when executed by a computer cause the computer to perform the following steps:

(a) receiving at a current node communication packets transmitted from 1-hop neighbor nodes within a communication range of the current node, said communication packets identifying (1) 1-hop neighbor node addresses of the respective 1-hop neighbor nodes transmitting the packets, (2) a number defining how many on-tree neighbor nodes have a child or parent hierarchical relationship with the respective 1-hop neighbor nodes transmitting the packets, and (3) forwarding node addresses of forwarding nodes from which the received packets are to be rebroadcast;

(b) storing said 1-hop neighbor node addresses and said number of on-tree neighbor nodes;

(c) when a received packet at the current node identifies the current node as a forwarding node which should rebroadcast the received packet, identifying based on the stored 1-hop neighbor addresses and the stored number of on-tree neighbor nodes, each 1-hop neighbor node which should be a forwarding node instructed to rebroadcast information included in a communication packet received from the current node;

(d) producing at the current node a rebroadcast communication packet including information to be rebroadcast, an address of the current node, and addresses of forwarding nodes identified in step (c) when the received packet at the current node identifies the current node as a forwarding node which should rebroadcast the received information; and

(e) transmitting from the current node the rebroadcast communication packet produced in step (d).

92. The computer program product of claim 91, further comprising:

producing at the current node a communication packet identifying a number defining how many 1-hop neighbor nodes have a child or parent hierarchical relationship with the current node; and

transmitting the communication packet identifying the defined number of 1-hop neighbor nodes having a child or parent hierarchical relationship with the current node.

93. The computer program product of claim 91, wherein step (a) comprises:

(a-1) receiving at the current node non-directed communication packets from 1-hop neighbor nodes, including information intended to be received by each node in the plurality of hierarchically addressed nodes, said 1-hop neighbor addresses of the respective 1-hop neighbor nodes transmitting the non-directed packets, and said forwarding node addresses of forwarding nodes from which the information in received non-directed packets are to be rebroadcast; and

(a-2) receiving at the current node directed communication packets including information intended to be received by a subset of nodes in the plurality of hierarchically addressed nodes, said 1-hop neighbor addresses of the respective 1-hop neighbor nodes transmitting the directed packets, and said number defining how many on-tree neighbor nodes have a child or parent hierarchical relationship with the respective 1-hop neighbor nodes transmitting the packets.

94. The computer program product of claim 93, further comprising:

storing a broadcast indication for the respective 1-hop neighbor nodes transmitting the non-directed packets,

wherein the identifying in step (c) is further based on the stored broadcast indication for each 1-hop neighbor node.

95. The computer program product of claim 91, further comprising:

identifying on-tree neighbor nodes having a hierarchical parent or child relationship with each 1-hop neighbor node; and

determining, for each 1-hop neighbor node and each identified on-tree neighbor node, a hierarchical level indicating a number of nodes between a respective node and a root node,

wherein the identifying in step (c) is further based on the determined hierarchical level.

96. The computer program product of claim 95, wherein the step of identifying on-tree neighbor nodes further comprises:

excluding 1-hop neighbor nodes of the current node from the identified on-tree neighbor nodes considered in the determining in step (c).

97. The computer program product of claim 95, wherein step (c) comprises:

(c-1) identifying a 1-hop neighbor node as a forwarding node if the 1-hop neighbor node is a parent node of an identified on-tree neighbor node;

(c-2) excluding the parent node and other child nodes of the 1-hop neighbor node identified in step (c-1) from the identified on-tree neighbor nodes considered in the determining step (c).

98. The computer program product of claim 95, wherein step (c) comprises:

(c-1) identifying a 1-hop neighbor node as a forwarding node if the 1-hop neighbor node is a child node of an identified on-tree neighbor node and the identified on-tree neighbor node is not a 1-hop neighbor node of the current node.

99. The computer program product of claim 92, wherein step (a) comprises:

(a-1) receiving at the current node non-directed communication packets from 1-hop neighbor nodes, including information intended to be received by each node in the plurality of hierarchically addressed nodes, said 1-hop neighbor addresses of the respective 1-hop neighbor nodes transmitting the non-directed packets, and said forwarding node addresses of forwarding nodes from which the information in received non-directed packets are to be rebroadcast; and

(a-2) receiving at the current node directed communication packets including information intended to be received by a subset of nodes in the plurality of hierarchically addressed nodes, said 1-hop neighbor addresses of the respective 1-hop neighbor nodes transmitting the directed packets, and said number defining how many on-tree neighbor nodes have a child or parent hierarchical relationship with the respective 1-hop neighbor nodes transmitting the packets.

100. The computer program product of claim 99, further comprising:

storing a broadcast indication for the respective 1-hop neighbor nodes transmitting the non-directed packets,

wherein the identifying in step (c) is further based on the stored broadcast indication for each 1-hop neighbor node.

101. The computer program product of claim 92, further comprising:

identifying on-tree neighbor nodes having a hierarchical parent or child relationship with each 1-hop neighbor node; and

determining, for each 1-hop neighbor node and each identified on-tree neighbor node, a hierarchical level indicating a number of nodes between a respective node and a root node,

wherein the identifying in step (c) is further based on the determined hierarchical level.

103. The computer program product of claim 101, wherein step (c) comprises:

(c-1) identifying a 1-hop neighbor node as a forwarding node if the 1-hop neighbor node is a parent node of an identified on-tree neighbor node;

(c-2) excluding the parent node and other child nodes of the 1-hop neighbor node identified in step (c-1) from the identified on-tree neighbor nodes considered in the determining step (c).

104. The computer program product of claim 101, wherein step (c) comprises:

(c-1) identifying a 1-hop neighbor node as a forwarding node if the 1-hop neighbor node is a child node of an identified on-tree neighbor node and the identified on-tree neighbor node is not a 1-hop neighbor node of the current node.

105. The computer program product of claim 93, further comprising:

identifying on-tree neighbor nodes having a hierarchical parent or child relationship with each 1-hop neighbor node; and

determining, for each 1-hop neighbor node and each identified on-tree neighbor node, a hierarchical level indicating a number of nodes between a respective node and a root node,

wherein the identifying in step (c) is further based on the determined hierarchical level.

106. The computer program product of claim 105, wherein the step of identifying on-tree nodes further comprises:

excluding 1-hop neighbor nodes of the current node from the identified on-tree neighbor nodes considered in the determining in step (c).

107. The computer program product of claim 105, wherein step (c) comprises:

(c-1) identifying a 1-hop neighbor node as a forwarding node if the 1-hop neighbor node is a parent node of an identified on-tree neighbor node;

(c-2) excluding the parent node and other child nodes of the 1-hop neighbor node identified in step (c-1) from the identified on-tree neighbor nodes considered in the determining step (c).

108. The computer program product of claim 105, wherein step (c) comprises:

(c-1) identifying a 1-hop neighbor node as a forwarding node if the 1-hop neighbor node is a child node of an identified on-tree neighbor node and the identified on-tree neighbor node is not a 1-hop neighbor node of the current node.

109. The computer program product of claim 94, further comprising:

identifying on-tree neighbor nodes having a hierarchical parent or child relationship with each 1-hop neighbor node; and

determining, for each 1-hop neighbor node and each identified on-tree neighbor node, a hierarchical level indicating a number of nodes between a respective node and a root node,

wherein the identifying in step (c) is further based on the determined hierarchical level.

110. The computer program product of claim 109, wherein the step of identifying on-tree nodes further comprises:

excluding 1-hop neighbor nodes of the current node from the identified on-tree neighbor nodes considered in the determining in step (c).

111. The computer program product of claim 109, wherein step (c) comprises:

(c-1) identifying a 1-hop neighbor node as a forwarding node if the 1-hop neighbor node is a parent node of an identified on-tree neighbor node;

(c-2) excluding the parent node and other child nodes of the 1-hop neighbor node identified in step (c-1) from the identified on-tree neighbor nodes considered in the determining step (c).

112. The computer program product of claim 109, wherein step (c) comprises:

(c-1) identifying a 1-hop neighbor node as a forwarding node if the 1-hop neighbor node is a child node of an identified on-tree neighbor node and the identified on-tree neighbor node is not a 1-hop neighbor node of the current node.

113. The computer program product of claim 99, further comprising:

identifying on-tree neighbor nodes having a hierarchical parent or child relationship with each 1-hop neighbor node; and

determining, for each 1-hop neighbor node and each identified on-tree neighbor node, a hierarchical level indicating a number of nodes between a respective node and a root node,

wherein the identifying in step (c) is further based on the determined hierarchical level.

114. The computer program product of claim 113, wherein the step of identifying on-tree nodes further comprises:

excluding 1-hop neighbor nodes of the current node from the identified on-tree neighbor nodes considered in the determining in step (c).

115. The computer program product of claim 113, wherein step (c) comprises:

(c-1) identifying a 1-hop neighbor node as a forwarding node if the 1-hop neighbor node is a parent node of an identified on-tree neighbor node;

(c-2) excluding the parent node and other child nodes of the 1-hop neighbor node identified in step (c-1) from the identified on-tree neighbor nodes considered in the determining step (c).

116. The computer program product of claim 113, wherein step (c) comprises:

(c-1) identifying a 1-hop neighbor node as a forwarding node if the 1-hop neighbor node is a child node of an identified on-tree neighbor node and the identified on-tree neighbor node is not a 1-hop neighbor node of the current node.

117. The computer program product of claim 100, further comprising:

identifying on-tree neighbor nodes having a hierarchical parent or child relationship with each 1-hop neighbor node; and

determining, for each 1-hop neighbor node and each identified on-tree neighbor node, a hierarchical level indicating a number of nodes between a respective node and a root node,

wherein the identifying in step (c) is further based on the determined hierarchical level.

118. The computer program product of claim 117, wherein the step of identifying on-tree nodes further comprises:

excluding 1-hop neighbor nodes of the current node from the identified on-tree neighbor nodes considered in the determining in step (c).

119. The computer program product of claim 117, wherein step (c) comprises:

(c-1) identifying a 1-hop neighbor node as a forwarding node if the 1-hop neighbor node is a parent node of an identified on-tree neighbor node;

(c-2) excluding the parent node and other child nodes of the 1-hop neighbor node identified in step (c-1) from the identified on-tree neighbor nodes considered in the determining step (c).

120. The computer program product of claim 117, wherein step (c) comprises:

(c-1) identifying a 1-hop neighbor node as a forwarding node if the 1-hop neighbor node is a child node of an identified on-tree neighbor node and the identified on-tree neighbor node is not a 1-hop neighbor node of the current node.

102. The computer program product of claim 1101, wherein the step of identifying on-tree nodes further comprises:

excluding 1-hop neighbor nodes of the current node from the identified on-tree neighbor nodes considered in the determining in step (c).

121. A communication packet embodied in an electromagnetic wave and configured to communicate information in a communication network that includes a plurality of hierarchically addressed nodes, said packet comprising:

an address of a transmitting node;

the information; and

a number of on-tree neighbor nodes having a child or parent relationship with the transmitting node.

122. A communication packet embodied in an electromagnetic wave and configured to communicate information in a communication network that includes a plurality of hierarchically addressed nodes, said packet comprising:

an address of a transmitting node;

the information; and

forwarding node addresses of forwarding nodes in the plurality of hierarchically addressed nodes from which the information is to be rebroadcast.