Routing method and wireless node for wireless mesh network

• US 10,250,503 B2
• Filed: 12/20/2016
• Issued: 04/02/2019
• Est. Priority Date: 11/02/2016
• Status: Active Grant

• Current Assignee: Industrial Technology Research Institute
• Original Assignee: Industrial Technology Research Institute
• Inventors: Chen, Chang-Hsien, Fang, Kuan-Jen, Chung, Yi-Cheng
• Primary Examiner(s): Young, Steve R
• Application Number:
  US15/384,334
• Publication Number:
  US 20180123957A1
• Time in Patent Office: 833 Days
• Field of Search: None
• CPC Class Codes: H04L 45/021 Ensuring consistency of routing table updates, e.g. by using epoch numbers
• CPC Class Codes: H04L 45/26 Route discovery packet
• CPC Class Codes: H04L 45/745 Address table lookup; Address filtering
• CPC Class Codes: H04W 40/12 based on transmission quality or channel quality
• CPC Class Codes: H04W 40/246 Connectivity information discovery
• CPC Class Codes: H04W 40/30 for proactive routing
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks
• CPC Class Codes: H04W 88/08 Access point devices

Abstract

A routing method for a wireless mesh network and a wireless node performing the method are provided. The method includes performing a route algorithm and finding available paths to reach a destination node, recording the available paths, a parent-child node relationship, and a link-state in a route table, and transmitting or transferring data by using an optimal path among the available paths. The method also includes selecting another available path as the optimal path when the optimal path is not operable, updating the route table, and notifying a parent wireless node. The method further includes performing a block route algorithm when receiving a node-added message for creating a block route table in a block where the newly-added node belongs, updating the route table according to the block route table for acquiring updated available paths, selecting one of the updated available paths as the optimal path, and notifying the parent wireless node.

Claims

1. A routing method for a wireless mesh network, the routing method being performed on a wireless node of a plurality of nodes of the wireless mesh network and comprising:

transmitting a control message packet for finding a plurality of available paths to reach a destination node of the plurality of nodes by performing a route algorithm to discover a topology of the wireless mesh network, and stopping performing the route algorithm after the plurality of available paths are found;

recording the available paths to reach the destination node, at least one parent-child node relationship corresponding to the available paths, and at least one link-state corresponding to the available paths in a route table;

using an optimal path among the available paths to transmit data or transfer data;

in response to the optimal path reaching the destination node being not operable, selecting another available path as the optimal path from the available paths, updating the route table, and notifying at least one parent wireless node on the optimal path of a node-deleted message;

in response to a node-added message being received from a newly-added node, relaying the node-added message and performing a block route algorithm for creating a block route table in a block to which the newly-added node belongs, updating the route table according to the block route table to acquire a plurality of updated available paths, selecting a path as the optimal path from the updated available paths, and notifying the at least one parent wireless node on the optimal path of the node-added message, wherein the block to which the newly-added node belongs is consist of the newly-added node and a part of the wireless mesh network and the part of the wireless mesh network comprises at least one adjacent node of the newly-added node in the wireless mesh network, and the wireless node is one of the at least one adjacent node; and

in response to the node-added message not being relayed from any wireless node in the block, not relaying the node-added message and not performing the block route algorithm.

2. The routing method as claimed in claim 1, wherein an optimized link state routing (OLSR) protocol is adopted in the route algorithm.

3. The routing method as claimed in claim 1, wherein the available paths are calculated based on an open shortest path first (OSPF) algorithm.

4. The routing method as claimed in claim 1, wherein the at least one link-state comprises at least one connection quality cost.

5. The routing method as claimed in claim 4, wherein when the optimal path of the available paths reaching the destination node is not operable, the step of selecting the another available path as the optimal path from the available paths comprises:

determining the another available path as the optimal path according to the at least one connection quality cost of the route table.

6. The routing method as claimed in claim 1, wherein the step of performing the block route algorithm for creating the block route table in the block to which the newly-added node belongs comprises:

loading from the route table the at least one link-state from each of the at least one adjacent node of the block to the destination node.

7. The routing method as claimed in claim 6, wherein the block route table comprises at least one newly-added available path from the block to the destination node and the at least one parent-child node relationship corresponding to the at least one newly-added available path.

8. The routing method as claimed in claim 1, wherein the node-added message and the node-deleted message comprise a message of at least one child wireless node of the wireless node.

17. A non-transitory computer-readable recording medium storing a program executable by a computer to complete the routing method claimed in claim 1.

9. A wireless node for a wireless mesh network, the wireless node comprising:

a transceiver for transmitting and receiving data; and

a processor coupled to the transceiver,

wherein the processor transmits a control message packet through the transceiver for finding a plurality of available paths to reach a destination node of a plurality of nodes of the wireless mesh network by performing a route algorithm to discover a topology of the wireless mesh network, and stops performing the route algorithm after the plurality of available paths are found,

wherein the processor records the available paths to reach the destination node, at least one parent-child node relationship corresponding to the available paths, and at least one link-state corresponding to the available paths in a route table, and transmitting the data or transferring the data by using an optimal path among the available paths,

in response to the optimal path reaching the destination node being not operable, the processor selects another available path as the optimal path from the available paths, updates the route table, and notifies at least one parent wireless node on the optimal path of a node-deleted message,

in response to receiving a node-added message being received from a newly-added node, the processor relays the node-added message and performs a block route algorithm to create a block route table in a block to which the newly-added node belongs, update the route table according to the block route table for acquiring a plurality updated available paths, select a path as the optimal path from the updated available paths, and notify the at least one parent wireless node on the optimal path of the node-added messag;

wherein the block to which the newly-added node belongs is consist of the newly added node and a part of the wireless mesh network and the part of the wireless mesh network comprises at least one adjacent node of the newly-added node in the wireless mesh network, and the wireless node is one of the at least one adjacent node, and

in response to the node-added message not being relayed from any wireless node in the block, not relaying the node-added message and not performing the block route algorithm.

10. The wireless node as claimed in claim 9, wherein the processor adopts an optimized link state routing (OLSR) protocol to perform the route algorithm.

11. The wireless node as claimed in claim 9, wherein the processor calculates the available paths based on an open shortest path first (OSPF) algorithm.

12. The wireless node as claimed in claim 9, wherein the at least one link-state comprises at least one connection quality cost.

13. The wireless node as claimed in claim 12, wherein when the optimal path of the available paths to the destination node is not operable, the processor determines the another available path as the optimal path according to the at least one connection quality cost of the route table.

14. The wireless node as claimed in claim 9, wherein when the block route algorithm is performed, the processor loads the at least one link-state from each of the at least one adjacent node of the block to the destination node from the route table.

15. The wireless node as claim in claim 14, wherein the block route table comprises at least one newly-added available path to the destination node from the block and at least one of the at least one parent-child node relationship corresponding to the at least one newly-added available path.

16. The wireless node as claimed in claim 9, wherein the node-added message and the node-deleted message comprise a message of at least one child wireless node of the wireless node.