A novel approach to OSPF-area design for large wireless ad-hoc networks

To build ad-hoc networks with hundreds or even thousands of nodes, the network must be split into relatively independent layer 3 clusters. There are currently no general approaches or methodologies for the creation of domains that take into account the following important engineering constraints: balanced domains, minimal inter-domain traffic, robust network design. Moreover, there is also no contribution that specifically addresses the problem of area formation for OSPF-based ad hoc networks. By assuming that the creation of layer 3 clusters is done after layer 2 topology management has set local radio parameters, we have re-formulated the problem at hand in a graph theoretic framework and found a strong connection between the problem of area design and a classical problem in graph theory, the graph partitioning (GP) problem. The limitation of GP algorithms (GPAs) is that they are OSPF-agnostic and, therefore, are not capable of solving the problem of robust backbone network (Area 0) design. We here propose a two-step approach for OSPF area design: the first step consists of an efficient GPA that will create areas (including a rough Area 0 design), and the second step consists of ad-hoc heuristics that are able to ameliorate the Area 0 design as well as factoring in OSPF specific metrics.