# US 2022/0046516 A1 · System and Method for Independent Dominating Set (IDS) Based Routing in Mobile AD Hoc Networks (MANET)

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2022/0046516 A1
- Document ID: US20220046516A1
- Status: Published application
- Kind: A1
- Application number: 16/987,671
- Filed: 2020-08-07
- Published: 2022-02-10
- Earliest claimed: 2020-08-07
- Assignees: Rockwell Collins, Inc.
- Applicants: Rockwell Collins, Inc.
- Inventors: Tj T. Kwon; Ray L. Cross; James A. Stevens
- Web page: https://patentgrep.com/patent/US20220046516A1

## CPC

- H04W 40/32: for defining a routing cluster membership
- H04W 40/026: {Route selection considering the moving speed of individual devices}
- H04W 40/24: Connectivity information management, e.g. connectivity discovery or connectivity update
- H04W 40/246: {Connectivity information discovery}
- H04W 40/248: {Connectivity information update}
- H04W 40/30: for proactive routing
- H04W 40/38: adapting due to varying relative distances between nodes
- H04W 76/40: for selective distribution or broadcast
- H04W 84/18: Self-organising networks, e.g. ad-hoc networks or sensor networks
- H04W: WIRELESS COMMUNICATION NETWORKS (broadcast communication H04H; communication systems using wireless links for non-selective communication, e.g. wireless extensions H04M1/72)

## Abstract

A communications node of a multi-node communications network is disclosed. In embodiments, the communications node includes a communications interface and controller. The controller transitions the clustering status of the communications node to a clusterhead node status. The clusterhead node identifies a cluster of neighboring nodes with which it is in communication by transmitting hello messages identifying the clusterhead node and its status but omitting a one-hop neighbor list. The clusterhead node refines link discovery to the nodes of the multi-node communications network by flooding the network (e.g., via its cluster of neighboring nodes) with routing status messages, which network nodes not part of the dominating set of clusterhead nodes are restricted from sending.

## Claims

### Claim 1

A communications node of a multi-node communications network, the communications node comprising:
a communications interface;
and
a controller communicatively coupled to the communications interface, the controller configured to:
designate a clustering status of the communications node as a clusterhead node status;
identify a cluster of one or more neighbor communications nodes communicatively coupled with the communications node by transmitting, via the communications interface, one or more hello messages, each hello message including 1) a unique node identifier corresponding to the communications node and 2) the clustering status;
determining at least one routing status associated with a route from the communications node to one or more additional communications nodes of the multi-node communications network by transmitting, via the communications interface, at least one routing status message to the one or more additional communications nodes via the cluster of one or more neighbor communications nodes.

### Claim 2 (depends on 1)

The communications node of claim 1, wherein:
the communications node has an initial clustering status selected from the clusterhead node status, a gateway node status, a noncritical node status, and a clusterhead-ready node status;
and
the controller is configured to designate the clustering status of the communications node as a clusterhead node status by transitioning the clustering status from the initial clustering status.

### Claim 3 (depends on 1)

The communications node of claim 1, wherein the controller is configured to designate the clustering status of the communications node as a node status selected from:
a gateway node status;
and
a noncritical node status.

### Claim 4 (depends on 3)

The communications node of claim 3, wherein the controller is configured to designate the clustering status of the communications node based on one or more passive clustering procedures.

### Claim 5 (depends on 1)

The communications node of claim 1, wherein the controller is configured to transmit the one or more hello messages to the one or more additional communications nodes according to one or more packet broadcasting procedures.

### Claim 6 (depends on 1)

The communications node of claim 1, wherein each hello message indicates only the communications node via the unique node identifier and excludes a local list of one or more neighbors communicatively coupled with the communications node.

### Claim 7 (depends on 1)

The communications node of claim 1, wherein the at least one routing status message is selected from:
a link status advertisement (LSA) including link information associated with the one or more neighbor communications nodes;
and
a distance vector distribution (DVD) message according to one or more routing protocols, the DVD message including link information associated with the one or more additional communications nodes.

### Claim 8

A method for independent dominating set (IDS) based ad hoc network routing within a set of communications nodes, comprising:
designating, from within a plurality of communications nodes of a multi-node communications network, a dominating set of one or more clusterhead nodes associated with a clusterhead node status;
identifying, via a clusterhead node of the dominating set, a cluster of one or more neighbor nodes communicatively coupled to the clusterhead node by transmitting one or more hello messages uniquely identifying the clusterhead node and the clusterhead node status, the one or more hello messages omitting a neighbor list;
determining at least one link status associated with a route from the clusterhead node to the plurality of communications nodes by transmitting, via the clusterhead node, at least one routing status message to the plurality of communications nodes via the cluster of one or more neighbor nodes.

### Claim 9 (depends on 8)

The method of claim 8, wherein designating, from within a plurality of communications nodes of a multi-node communications network, an independent dominating set of one or more clusterhead nodes associated with a clusterhead node status includes:
transitioning a node status of the clusterhead node to the clusterhead node status from an initial node status selected from a gateway node status and a noncritical node status.

### Claim 10 (depends on 8)

The method of claim 8, wherein designating, from within a plurality of communications nodes of a multi-node communications network, a dominating set of one or more clusterhead nodes associated with a clusterhead node status includes:
transitioning a node status of at least one communications node to the clusterhead node status according to one or more passive clustering procedures.

### Claim 11 (depends on 8)

The method of claim 8, wherein determining at least one link status associated with a route from the clusterhead node to the plurality of communications nodes by transmitting, via the clusterhead node, at least one routing status message to the plurality of communications nodes via the cluster of one or more neighbor nodes includes:
transmitting, via the clusterhead node, at least one routing status message to the plurality of communications nodes via the cluster of one or more neighbor nodes according to one or more packet broadcasting procedures.

### Claim 12 (depends on 8)

The method of claim 8, wherein determining at least one link status associated with a route from the clusterhead node to the plurality of communications nodes by transmitting, via the clusterhead node, at least one routing status message to the plurality of communications nodes via the cluster of one or more neighbor nodes includes:
transmitting, via the clusterhead node, at least one link status advertisement (LSA) to the plurality of communications nodes via the cluster of one or more neighbor nodes, the LSA including link information associated with the cluster of one or more neighbor nodes.

### Claim 13 (depends on 8)

The method of claim 8, wherein determining at least one link status associated with a route from the clusterhead node to the plurality of communications nodes by transmitting, via the clusterhead node, at least one routing status message to the plurality of communications nodes via the cluster of one or more neighbor nodes includes:
transmitting, via the clusterhead node, at least one distance vector distribution (DVD) message according to one or more routing protocols, the DVD message including link information associated with each of the plurality of communications nodes.

### Claim 14 (depends on 8)

The method of claim 8, further comprising:
transitioning the clusterhead node status of the clusterhead node to a node status selected from a gateway node status and a noncritical node status.
