Building Robust Wireless Mesh Networks Using Directional Antennas: How Many Radios are Enough?

Abstract

Recently, wireless mesh technology has been used for military applications and fast recovery networks, referred to as nomadic wireless mesh networks (NWMNs). In such systems, wireless routers, termed nodes, are mounted on top of vehicles or vessels. The vessels may change their location according to application needs and the nodes are required to establish a broadband and reliable wireless mesh network. For improving network performance, some vendors use directional antennas and the mesh topology comprises of point-to-point connections between adjacent nodes. Consequently, the number of point-to-point connections of a node is upperbounded by the number of directional radios (and antennas) that it has, which is typically a small constant. This raises the need to build robust (i.e., two-node/edgeconnected) mesh networks with bounded node degree, regardless of node locations. This paper is the first to present practical solutions with provable properties for constructing efficient and robust wireless mesh networks using directional antennas. First, we formulate the design problem to be theoretically equivalent to the construction of bounded degree two-connected mesh topologies. Then, we present elegant schemes for constructing such solutions with small constant degree bounds. Finally, our extensive simulations show that our schemes find robust and efficient topologies for practical settings with node degree bounded by 4, while preserving small hop-count distance between nodes and gateways.