Building Robust Nomadic Wireless Mesh Networks using Directional Antennas

Recently, wireless mesh technology has been used for military applications and fast recovery networks, refered to as nomadic wireless mesh networks (NWMNs). In such systems wireless routers, termed nodes, are mounted on top of vehicles or vessels, which may change their location according to application needs and the nodes are required to establish a reliable wireless mesh network. For improving network performance, some ven- dors use directional antennas and the mesh topology comprises of point-to-point connections between adjacent nodes. The number of point-to-point connections of a node is upper-bounded by the number of directional radios it has, which is typically a small constant. This raises the need to build robust (i.e., two- node/edge-connected) mesh networks with bounded node degree, regardless of node locations. In this paper, we present simple schemes for sonstructing such efficient and robust wireless mesh networks with provably small constant degree bounds. Our extensive simulations show our schemes build robust and efficient topologies for various settings with node degree bounded by 4 and small hop-count distances between nodes and gateways.