# US 2008/0304422 A1 · Methods and devices for providing robust nomadic wireless mesh networks using directional antennas

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

- Number: US 2008/0304422 A1
- Document ID: US20080304422A1
- Status: Published application
- Kind: A1
- Application number: 11/808,413
- Filed: 2007-06-08
- Published: 2008-12-11
- Earliest claimed: 2007-06-08
- Assignees: Alcatel-Lucent USA Inc.
- Inventors: Yigal Bejerano; Qunfeng Dong
- Web page: https://patentgrep.com/patent/US20080304422A1

## CPC

- H04W 28/06: Optimizing {the usage of the radio link}, e.g. header compression, information sizing {, discarding information (system modifying transmission characteristic according to link quality by modifying frame length H04L1/0007; dynamic adaptation of the packet size for flow control or congestion control H04L47/365)}
- H04L 45/26: {Route discovery packet}
- H04L 45/48: Routing tree calculation
- H04W 28/04: Error control
- H04W 64/00: Locating users or terminals {or network equipment} for network management purposes, e.g. mobility management
- H04W: WIRELESS COMMUNICATION NETWORKS (broadcast communication H04H; communication systems using wireless links for non-selective communication, e.g. wireless extensions H04M1/72)
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## Abstract

The number of directional antennas and associated radios needed to ensure a nomadic wireless mesh network (NWMN) remains operational in the event of node or link failures, while minimizing delay and other unwanted effects, may be determined using novel methods and devices. Such a determination may reduce the number of antennas and radios a service or network provider normally uses, thus reducing its costs.

## Claims

### Claim 1

A method for computing the topology of a wireless mesh network to preserve network connectivity comprising:
computing a DFS tree from a unit disk subgraph representing nodes in the network;
identifying nested backlinks in the computed tree;
iteratively removing nested backlinks from the tree until there are none remaining, wherein the links that remain preserve network connectivity in the event of a link failure;
performing a backlink shifting operation on some of the links to further remove links; and
performing a tree-edge removal operation on some links to further remove links, wherein the links that remain after the backlink shifting and tree-edge removal operations preserve network connectivity in the vent of a node or link failure.

### Claim 2 (depends on 1)

The method as in claim 1 further comprising iteratively adding links to minimize an average hop count distance while preventing an increase in the maximal node degree.

### Claim 3

A device for computing the topology of a wireless mesh network to preserve network connectivity, the device operable to:
compute a DFS tree from a unit disk subgraph representing nodes in the network;
identify nested backlinks in the computed tree;
iteratively remove nested backlinks from the tree until there are none remaining, wherein the links that remain preserve network connectivity in the event of a link failure;
perform a backlink shifting operation on some of the links to further remove links; and
perform a tree-edge removal operation on some links to further remove links, wherein the links that remain after the backlink shifting and tree-edge removal operations preserve network connectivity in the event of a node or link failure.

### Claim 4 (depends on 3)

The device as in claim 3 further operable to iteratively add links to minimize an average hop count distance while preventing an increase in the maximal node degree.

### Claim 5

A robust, wireless mesh network comprising:
a plurality of quasi-static routers,
wherein each router is connected to at least ten directional antennas to preserve network connectivity in the network in the event of a link failure.

### Claim 6 (depends on 5)

The network as in claim 5 wherein each router is connected to at least six directional antennas to preserve network connectivity in the event of a node or link failure.

### Claim 7 (depends on 5)

The network in claim 5 wherein the network comprises a nomadic wireless mesh network.

### Claim 8 (depends on 5)

The network in claim 5 wherein each router is part of a ship or vehicle.

### Claim 9

A method for computing the topology of a wireless mesh network to ensure the network remains operational in the event of a link or node failure comprising:
computing a graph representing nodes in the network;
iteratively removing some links from the graph such that the links that remain ensure that the operation of the network will be maintained in the event of a link failure;
performing a backlink shifting operation on some of the links to further remove links; and
performing a tree-edge removal operation on some links to further remove links, wherein the links that remain after the backlink shifting and tree-edge removal operations ensure that the operation of the network will be maintained in the event of a node or link failure.

### Claim 10 (depends on 9)

The method as in claim 9 further comprising iteratively adding links to improve a network's delay and loss rate performance.

### Claim 11 (depends on 9)

The method as in claim 9 wherein the network comprises a nomadic wireless mesh network.

### Claim 12 (depends on 9)

The method as in claim 9 further comprising configuring a plurality of quasi-static routers based on the links that remain, wherein each router is connected to at least ten directional antennas to preserve network connectivity in the network in the event of a link failure.

### Claim 13 (depends on 12)

The method as in claim 12 wherein each router is connected to at least six directional antennas to preserve network connectivity in the event of a node or link failure.

### Claim 14 (depends on 12)

The method as in claim 12 wherein each router is part of a ship or vehicle.
