Artificial intelligence-augmented, ripple-diamond-chain shaped rateless routing in wireless mesh networks with multi-beam directional antennas

Patent metadata

Field	Value
Publication number	US-10142909-B2
Application number	US-201615292612-A
Country	US
Kind code	B2
Filing date	Oct 13, 2016
Priority date	Oct 13, 2015
Publication date	Nov 27, 2018
Grant date	Nov 27, 2018

Abstract

Disclosed herein are systems and methods directed to routing in the wireless mesh network (WMN) with multi-beam directional antennas (MBDAs). The disclosed systems and methods describe Ripple-Diamond-Chain (RDC) shaped routing, systematic link quality modeling and artificial intelligence (AI) augmented path link selection. In simulations, real-time video as well as other types of traffic types are used to validate the high-throughput, quality of service (QoS)-differentiated, multi-beam routing efficiency of the disclosed systems and methods, as well as the intelligent path determination in dynamic WMN environments.

First claim

What is claimed is:

1. A method of routing data between a source and a destination in a wireless mesh network (WMN), the method comprising:
defining a main path between the source and destination in the WMN, wherein the main path comprises a plurality of nodes in the WMN, each node configured to receive and transmit data, wherein at least one node is associated with a multi-beam directional antenna (MBDA);
defining one or more side paths of the main path, wherein the one or more side paths comprise a plurality of nodes in the WMN, each node configured to receive and transmit data;
routing data between the source and the destination through the main path and the one or more side paths, wherein at least a portion of the data being routed from the source to the destination diverges from the main path to at least one of the one or more side paths and converges from the at least one of the one or more side paths to the main path while being routed from the source to the destination; and
using a cumulative distribution function (CDF) metric to characterize a statistical distribution of feedback delays during the routing of the data between the source and the destination through the main path and the one or more side paths, a capture effect metric that is used to characterize a probability of an MBDA being associated with at least one node being captured, and a diamond transmission probability metric that is used to measure a probability of a node becoming part of the main path.

2. The method of claim 1 , wherein the at least a portion of the data being routed from the source to the destination diverging from the main path to the one or more side paths and converging from the side path to the main path while being routed from the source to the destination comprises the at least a portion of data being routed from at least one node having a first ripple identifier to a plurality of nodes having a second ripple identifier, and then from the plurality of nodes having the second ripple identifier to at least one node having a third ripple identifier.

3. The method of claim 1 , wherein the method further comprises a multi-beam-oriented transmission control scheme that is used to synchronize beam communication associated with the MBDA during the routing of the data between the source and the destination through the main path and the one or more side paths.

4. The method of claim 1 , wherein the method further comprises the CDF metric, the capture effect metric, and the diamond transmission probability metric being adjusted based on different quality-of-service (QoS) requirements associated with the data.

5. The method of claim 1 , wherein fuzzy logic (FL) is used to obtain a fused metric that comprises the CDF metric, the capture effect metric, and the diamond transmission probability metric, wherein the fused metric measures a dynamic node quality of at least one node, wherein the fused metric is used for a reward calculation in a reinforcement learning (RL)-based path search.

6. The method of claim 5 , wherein the FL further comprises a Simple Additive Weighting Method (SAW) that includes a decision matrix, and the decision matrix comprises weights that are adjusted based on different QoS requirements for the data.

7. The method of claim 1 , wherein online learning is used while routing data between the source and the destination through the main path and the one or more side paths, wherein the CDF metric is obtained through the online learning, and wherein the online learning algorithm comprises Gaussian approximation or Maximum-Likelihood (ML) estimation.

8. The method of claim 1 , wherein a neighbor table is associated with a node and the neighbor table contains information about one or more accessible one-hop and one or more two-hop neighbor nodes from the said node and one or more beam IDs through which the said node can reach one or more of the one-hop neighbor nodes and the two-hop neighbor nodes.

9. The method of claim 1 , wherein a Q-learning process is implemented for the routing of the data between the source and the destination in the WMN, said Q-learning process comprises a Markov decision process (MDP) process.

10. The method of claim 1 , wherein the routing of the data between the source and the destination in the WMN is determined by maximizing expected rewards of all the nodes and a Bellman equation is used to perform an online policy search based on one or more cumulative rewards of all the nodes.

11. A system for routing data between a source and a destination in a WMN, the system comprising:
a plurality of nodes, wherein a portion of the nodes are associated with an MBDA;
a processor configured to execute computer-implemented code;
wherein the processor executes the computer-implemented code to:
define a main path between the source and destination in the WMN, wherein the main path comprises a portion of the plurality of nodes in the WMN, each node configured to receive and transmit data;
define one or more side paths of the main path, wherein the one or more side paths comprise a portion of the plurality of nodes in the WMN, each node configured to receive and transmit data;
route data between the source and the destination through the main path and the one or more side paths, wherein at least a portion of the data being routed from the source to the destination diverges from the main path to at least one of the one or more side paths and converges from the at least one of the one or more side paths to the main path while being routed from the source to the destination; and
determine a cumulative distribution function (CDF) metric to characterize a statistical distribution of feedback delays during the routing of the data between the source and the destination through the main path and the one or more side paths, to determine a capture effect metric that is used to characterize a probability of an MBDA being associated with at least one node being captured, and to determine a diamond transmission probability metric that is used to measure a probability of a node becoming part of the main path.

12. The system of claim 11 , wherein the at least a portion of the data being routed from the source to the destination diverging from the main path to the one or more side paths and converging from the side path to the main path while being routed from the source to the destination comprises the at least a portion of data being routed from at least one node having a first ripple identifier to a plurality of nodes having a second ripple identifier, and then from the plurality of nodes having the second ripple identifier to at least one node having a third ripple identifier.

13. The system of claim 11 , wherein the system further comprises the processor executing the computer-implemented code to implement a multi-beam-oriented transmission control scheme that is used to synchronize beam communication associated with the MBDA during the routing of the data between the source and the destination through the main path and the one or more side paths.

14. The system of claim 11 , wherein the system further comprises the processor executing the computer-implemented code to adjust the CDF metric, the capture effect metric, and the diamond transmission probability metric based on different quality-of-service (QoS) requirements associated with the data.

15. The system of claim 11 , wherein the system further comprises the processor executing the computer-implemented code to implement fuzzy logic (FL) to obtain a fused metric that comprises the CDF metric, the capture effect metric, and the diamond transmission probability metric, whe

Assignees

• Univ Alabama
• San Diego State Univ Sdsu Foundation

Inventors

• Hu Fei
• Bao Ke
• Kumar Sunil

Classifications

• G06N7/01

  Probabilistic graphical models, e.g. probabilistic networks · CPC title

• H04W40/02

  Communication route or path selection, e.g. power-based or shortest path routing · CPC title

• H04L45/123

  Evaluation of link metrics (techniques for monitoring network metrics H04L43/08) · CPC title

• H04W40/38

  adapting due to varying relative distances between nodes · CPC title

• H04W40/06 Primary

  based on characteristics of available antennas · CPC title