Methods and devices for providing robust nomadic wireless mesh networks using directional antennas
View Patent ↗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.
1. A method for computing the topology of a wireless mesh network to preserve network connectivity comprising:
computing a depth first search (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 preserve network connectivity by further removing 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,
wherein the method is carried out using a controller device.
2. 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.
3. A device for computing the topology of a wireless mesh network to preserve network connectivity, the device comprising programmed hardware or a combination of hardware and software operable to:
compute a depth first search (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 preserve network connectivity by further removing 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.
4. 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.
5. 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 ensure that the operation of the network will be maintained by further removing 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,
wherein the method is carried out using a controller device.
6. The method as in claim 5 further comprising iteratively adding links to improve a network's delay and loss rate performance.
7. The method as in claim 5 wherein the network comprises a nomadic wireless mesh network.
8. The method as in claim 5 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.
9. The method as in claim 8 wherein each router is connected to at least six directional antennas to preserve network connectivity in the event of a node or link failure.
10. The method as in claim 8 wherein each router is part of a ship or vehicle.