Wireless communication network and routing method

• US 8,537,719 B2
• Filed: 11/11/2009
• Issued: 09/17/2013
• Est. Priority Date: 12/29/2008
• Status: Active Grant

• Current Assignee: Industrial Technology Research Institute
• Original Assignee: Industrial Technology Research Institute
• Inventors: Chang, Shu-Hsin, Liu, Pin-Chuan, Yao, Chih-Yuan, Tsai, Wei-Lun
• Primary Examiner(s): Lee, Jae Y
• Assistant Examiner(s): GUADALUPE CRUZ, AIXA AMYR
• Application Number:
  US12/616,394
• Publication Number:
  US 20100165885A1
• Time in Patent Office: 1,406 Days
• Field of Search: None
• US Class Current: 370/256
• CPC Class Codes: H04L 45/26 Route discovery packet
• CPC Class Codes: H04L 45/48 Routing tree calculation
• CPC Class Codes: H04L 45/488 using root node determination
• CPC Class Codes: H04W 40/02 Communication route or path selection, e.g. power-based or shortest path routing

Abstract

A wireless communication network, including a destination node, a first node transmitting a first routing message, wherein the first node has a first routing table including a first entry for the destination node, and the first entry includes a first list field for child node(s). The network further includes a second node generating and transmitting a second routing message according to the first routing message, wherein the second routing message includes a second parent node field, and the second parent node field is marked as the first node that transmitted the first routing message. The first node further receives the second routing message and stores a first mark in the first list field for child node(s) of the first entry after determining that the second parent node field of the second routing message is marked as the first node, and the first mark denotes the second node.

Claims

1. A wireless communication network, comprising:

a destination node, wherein a destination identifying information corresponds to the destination node;

a first node transmitting a first routing message, wherein a first identifying information corresponds to the first node,

wherein the first node has a first routing table, the first routing table including a first entry corresponding to the destination node, the first entry including a first child node field,

wherein the first routing message includes at least a first relay field and a first destination node field, and the first relay field is marked to include the first identifying information and the first destination node field is marked to include the destination identifying information;

a second node having a second routing table, wherein a second identifying information corresponds to the second node,

wherein the second routing table includes a second entry corresponding to the destination node, the second entry including a second nexthop field and a second child node field,

wherein the second node receives the first routing message, marks the second nexthop field to include the first identifying information, and generates and transmits a second routing message according to the first routing message,

further wherein the second routing message includes a second parent node field, a second relay field, and a second destination node field, and the second parent node field is marked to include the first identifying information, the second relay field is marked to include the second identifying information and the second destination node field is marked to include the destination identifying information,

further wherein the first node receives the second routing message, and after determining that the first identifying information is included in the second parent node field, stores a first mark in the first child node field, wherein the first mark represents the second identifying information, that corresponds to the second node, that is marked in the second relay field; and

a third node having a third routing table, wherein a third identifying information corresponds to the third node,

wherein the third routing table includes a third entry corresponding to the destination node, the third entry including a third nexthop field and a third child node field,

further wherein the third node receives the second routing message, and marks the third nexthop field to include the second identifying information marked by the second relay field.

2. The wireless communication network as claimed in claim 1, wherein the destination node is the first node.

3. The wireless communication network as claimed in claim 1, wherein

the third node generates and transmits a third routing message in accordance with the second routing message, and the third routing message includes a third parent node field, a third relay field, and a third destination node field,

the third parent node field is marked to include the second identifying information marked in the second relay field, and the third relay field is marked to include the third identifying information,

the third destination node field is marked to include the destination identifying information,

the second node further receives the third routing message, and determines that the third parent node field is marked as the second identifying information and then stores a second mark in the second child node field, wherein the second mark represents the third identifying information marked in the third relay field.

4. The wireless communication network as claimed in claim 3, further comprising a fourth node transmitting a fourth routing message, wherein a fourth identifying information corresponds to the fourth node, wherein the fourth node has a fourth routing table, the fourth routing table including a fourth entry corresponding to the destination node, the fourth entry including a fourth child node field.

5. The wireless communication network as claimed in claim 4, wherein the fourth node transmits the fourth routing message and the fourth routing message includes the fourth identifying information,

wherein the third node further receives the fourth routing message, and generates and transmits a fifth routing message according to the fourth routing message, the fifth routing message being received by the second node and the fourth node, and

wherein the fifth routing message includes a fifth parent node field, the fifth parent node field is marked to include, based upon the fourth routing message, the fourth identifying information.

6. The wireless communication network as claimed in claim 5, wherein the fourth node determines from the fifth routing message that the fifth parent node field includes the fourth identifying information, and then stores a fourth mark in the fourth child node field, wherein the fourth mark represents the third identifying information.

7. The wireless communication network as claimed in claim 5, wherein the second node determines from the fifth routing message that the fifth parent node field does not include the second identifying information, and then the second mark representing the third identifying information stored in the second child node field is cleared.

8. The wireless communication network as claimed in claim 1, wherein the first entry further comprises a first nexthop field, and after the first node receives an initial routing message, upon which the first routing message is based, from the destination node, the first nexthop field is marked to include the destination identifying information.

9. The wireless communication network as claimed in claim 3, wherein the destination node transmits the initial routing message when detecting a new node.

10. The wireless communication network as claimed in claim 1, wherein the second node further generates and transmits a fourth routing message, and the fourth routing message includes a fourth relay field and a fourth destination node field, wherein the third node further receives the fourth routing message, and based on the fourth relay field and the third child node field, determines whether to transmit a corresponding routing message according to the fourth routing message.

11. A routing method, comprising:

providing a destination node having a destination identifying information corresponding thereto, a first node having a first identifying information corresponding thereto, a second node having a second identifying information corresponding thereto and a third node having a third identifying information corresponding thereto,

wherein the first node has a first routing table, the first routing table including a first entry corresponding to the destination node, the first entry including a first child node field,

wherein the second node has a second routing table, the second routing table including a second entry corresponding to the destination node, the second entry including a second nexthop field and a second child node field,

wherein the third node has a third routing table, the third routing table including a third entry corresponding to the destination node, the third entry including a third nexthop field and a third child node field;

generating a first routing message by the first node, wherein the first routing message includes at east a first relay field and a first destination node field, and the first relay field is marked to include the first identifying information and the first destination node field is marked to include the destination identifying information;

transmitting the first routing message;

receiving the first routing message by the second node;

based on the first routing message, marking, by the second node, the second nexthop field to include the first identifying information in accordance with the first routing message;

based on the first routing message, generating a second routing message by the second node, wherein the second routing message includes a second parent node field, a second relay field, and a second destination node field, and the second parent node field is marked as the first identifying information, the second relay field is marked as the second identifying information and the second destination node field is marked as the destination identifying information;

transmitting the second routing message by the second node;

receiving the second routing message by the first node and the third node;

storing a first mark, by the first node, in the first child node field after determining that the second parent node field is marked as the first identifying information, wherein the first mark represents the second identifying information marked by the second relay field; and

based on the second routing message, marking, by the third node, the third nexthop field as the second identifying information marked by the second relay field.

12. The routing method as claimed in claim 11, wherein the destination node is the first node.

13. The routing method as claimed in claim 11, further comprising:

based on the second routing message, generating, by the third node, a third routing message,

wherein the third routing message includes a third parent node field, a third relay field, and a third destination node field, and

wherein the third parent node field is marked as the second identifying information that is transmitted in the second relay field of the second routing message, the third relay field is marked as the third identifying information and the third destination node field is marked as the destination identifying information;

transmitting the third routing message;

receiving the third routing message by the second node;

determining, by the second node, that the third parent field included in the third routing message is marked as the second identifying information; and

after the determining by the second node, storing a second mark in the second child node field, wherein the second mark represents the third identifying information marked by the third relay field.

14. The routing method as claimed in claim 13, further comprising:

providing a fourth node having fourth identifying information corresponding thereto and a fourth routing table, the fourth routing table including a fourth entry corresponding to the destination node, the fourth entry including a fourth child node field; and

transmitting a fourth routing message generated by the fourth node.

15. The routing method as claimed in claim 14, wherein the fourth routing message includes the fourth identifying information, the method further comprising:

receiving the fourth routing message by the third node;

generating a fifth routing message, by the third node, according to the fourth routing message, wherein the fifth routing message includes a fifth parent node field, the fifth parent node field being marked as the fourth identifying information in the fourth routing message;

transmitting the fifth routing message; and

receiving the fifth routing message by the second node and the fourth node.

16. The routing method as claimed in claim 15, further comprising:

determining, by the fourth node, from the received fifth routing message that the fifth parent node field is marked as the fourth identifying information; and

after the determining by the fourth node, storing, by the fourth node, a fourth mark in the fourth child node field, wherein the fourth mark represents the third identifying information.

17. The routing method as claimed in claim 15, further comprising:

determining, by the second node, that the fifth parent node field is not marked as the second identifying information; and

after the determining by the second node that the fifth parent node field is not marked as the second identifying information, the second mark representing the third identifying information in the second child node field is cleared.

18. The routing method as claimed in claim 11, wherein the first entry further includes a first nexthop field, the method further comprising:

transmitting an initial routing message from the destination node;

receiving the initial routing message by the first node; and

based on the initial routing message, marking, by the first node, the first nexthop field to include the destination identifying information.

19. The routing method as claimed in claim 18, further comprising:

providing a new node;

detecting, by the destination node, the new node; and

transmitting, by the destination node, an initial routing message when the new node is detected.

20. The routing method as claimed in claim 11, further comprising:

generating, by the second node, a fourth routing message that includes a fourth relay field and a fourth destination node field;

transmitting the fourth routing message; and

receiving the fourth routing message by the third node,

determining, by the third node, based upon the fourth relay field and the third child node field, whether to transmit a corresponding routing message according to the fourth routing message.