System and method for implementing mesh network communications using a mesh network protocol

• US 9,942,824 B2
• Filed: 11/17/2016
• Issued: 04/10/2018
• Est. Priority Date: 09/04/2008
• Status: Active Grant

• Current Assignee: Trilliant Networks Incorporated
• Original Assignee: Trilliant Networks Incorporated
• Inventors: Veillette, Michel
• Primary Examiner(s): Pezzlo, John
• Application Number:
  US15/354,506
• Publication Number:
  US 20170070941A1
• Time in Patent Office: 509 Days
• Field of Search: 370252, 370389, 370282, 370406
• CPC Class Codes: H04L 45/20 Hop count for routing purposes, e.g. TTL
• CPC Class Codes: H04L 45/34 Source routing
• CPC Class Codes: H04L 45/42 Centralised routing
• CPC Class Codes: H04L 45/44 Distributed routing
• CPC Class Codes: H04L 45/48 Routing tree calculation
• CPC Class Codes: H04L 45/52 Multiprotocol routers
• CPC Class Codes: H04L 45/72 Routing based on the source address
• CPC Class Codes: H04L 63/123 received data contents, e.g. message integrity
• CPC Class Codes: H04W 40/005 Routing actions in the presence of nodes in sleep or doze mode
• CPC Class Codes: H04W 40/02 Communication route or path selection, e.g. power-based or shortest path routing
• CPC Class Codes: H04W 40/12 based on transmission quality or channel quality
• CPC Class Codes: H04W 40/22 using selective relaying for reaching a BTS [Base Transceiver Station] or an access point
• CPC Class Codes: H04W 40/246 Connectivity information discovery
• CPC Class Codes: H04W 40/28 for reactive routing
• CPC Class Codes: H04W 48/18 Selecting a network or a communication service
• CPC Class Codes: H04W 8/02 Processing of mobility data, e.g. registration information at HLR [Home Location Register] or VLR [Visitor Location Register]; Transfer of mobility data, e.g. between HLR, VLR or external networks
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks
• CPC Class Codes: Y02D 30/70 in wireless communication networks

Abstract

A process for routing data frames from a first node to a second node within a network is provided. The process includes: a tree routing sub-process, a source routing sub-process, a temporary routing sub-process and a mesh routing sub-process, wherein the particular sub-process for routing a data frame from the first node the second nodes is selected in accordance with the following logic executed on a processor: if the data frame has a source route header the source routing sub-process is selected; if there is an entry for the target address in a temporary routing table, the temporary routing sub-process is selected; if the second node is a coordinator node, the tree routing sub-process is selected; if the second node is not a coordinator node, the mesh routing sub-process is selected.

Claims

1. A process for routing data frames from a first node to a second node within a network, the process including:

a tree routing sub-process, a source routing sub-process, a temporary routing sub-process and a mesh routing sub-process, wherein the mesh routing sub-process comprises;

accessing a first route table at the first node to determine a first interim node address from the route based on the second node address;

sending the data frame from the first node to a first interim node in the route using the first interim node address from the route;

accessing a second route table at the first interim node to determine a second interim node address from the route based on the second node address;

sending the data frame from the first interim node to the second interim node address;

if the first interim node is unable to send the data frame to the second interim node address, broadcasting a route error message and deleting a second interim node address; and

receiving an error message at the first node if the data frame does not reach the second node,

and wherein the particular sub-process for routing a data frame from the first node the second node is selected in accordance with the following logic executed on a processor;

if the data frame has a source route header the source routing sub-process is selected;

if there is an entry for the target address in a temporary routing table, the temporary routing sub-process is selected;

if the second node is a coordinator node, the tree routing sub-process is selected;

if the second node is not a coordinator node, the mesh routing sub-process is selected.

2. The process according to claim 1, wherein the tree routing sub-process comprises:

accessing by the first node a neighborhood table to determine a route to the coordinator;

selecting by the first node a neighbor with a preferred parent flag;

transmitting the data frame to a first parent neighbor with the preferred parent flag;

if transmission to the first parent neighbor does not succeed, selecting a next parent neighbor from the neighborhood table with a hop-count value less than the hop-count value of the first node until the transmission succeeds;

if transmission does not succeed via a neighbor having a hop-count value less than the hop-count value of the first node, selecting a sibling neighbor from the neighborhood table for transmission to the second node, wherein a sibling neighbor has a hop-count value that is equal to the hop-count value of the first node.

3. The process according to claim 2, wherein the tree routing sub-process further comprises within the step of selecting a next parent neighbor from the neighborhood table with a hop-count value less than the hop-count value of the first node until the transmission succeeds:

ordering next parent neighbors according to a preferred route ratio value as follows;

Preferred Route Ratio=Min LQI class<

<

12|(15−

Number of Hops)<

<

8|Avg LQI

where Min LQI class is the minimum of all LQI class for each hop between the first node and the coordinator node through this next parent neighbor, and

Avg LQI is the average of the LQI value of each hop between the first node and the coordinator node through this next parent neighbor;

for all the possible routes with the best min LQI class, selecting the next parent neighbors with the least number of hops; and

select the next parent neighbor with the best Avg LQI.

4. The process according to claim 1, wherein the source routing sub-process comprises:

following a known route from the first node to the second node, the known route being embedded in a header of the data frame in the form of a list of node addresses located along the known route from the first node to the second node, wherein each node located along a route path from the first node to the second node forwards the data frame to the next node address located on the list after the current node'"'"'s address;

wherein the known route to the second node is determined by

(i) sending by the first node a route request frame to the second node with a trace route flag set or

(ii) sending by the first node a route establishment request frame to the coordinator requesting a route to the second node.