Abstract
A mathematical-plus-conceptual framework is presented for studying problems such as the following. One wants to deploy an n-node multi-channel wireless network N in an environment that is inaccessible for repair and/or that contains malicious adversaries. (Example: One wants to “harden” a facility—say, a control base or organizational headquarters or hospital or computation center—against “destructive incidents” such as attacks by malicious adversaries or accidents of nature.) Given a (finite) set Ω of topologies that one wants to be able to “overlay” on (the surviving portion of) network N, one wants to design N to be Ω-robust, in the following very strong sense. Even if any set of m ≪ n nodes is disabled, one still wants all of the surviving n - m nodes to be able to organize themselves (logically, in the manner of an overlay network) into any topology T ∈ Ω that has ≤ n-m nodes. A mathematical model for multi-channel wireless networks is presented and is used to develop a scalable, deterministic strategy for designing networks that are Ω-robust, for a very broad class of sets Ω. The strategy is illustrated for the simple case when Ω is the set of all paths of lengths ≤ n. The resulting path-robust networks: (a) are within a factor of 2 of optimal in complexity, as measured by the number of node-channel access points; (b) enable power-efficient communication, in that a node's logical neighbors in the overlay path are its physically nearest nodes in the surviving portion of N. It is suggested how the model and approach can extend to a much richer variety of topologies.