Managing interoperation in multi-organization MANETs by dynamic gateway assignment

Interoperation in MANETs is an important issue in many operational situations, because of the growing number of heterogeneous MANETs with different standards, technologies and adminstrative management. To enable interoperation, gateways are often deployed for protocol translation, inter-MANET routing, and management policy enforcement among these heterogeneous MANETs. To optimize gateway deployment, we consider the gateway functionalities to be enabled or disabled dynamically in response to the changing network topology. In this paper, we offer mechanisms to select the minimal subset of enabled gateways among the deployed gateways to ensure the interoperation among the MANETs. To this aim, we formulate a novel graph optimization problem, called Minimal Gateway Assignment Problem, and prove that it is NP-hard. Nonetheless, we provide efficient algorithms to solve this problem with varying degrees of complexity and coordination. First, we provide a centralized polynomial-time algorithm that is 2-approximable, and a distributed algorithm. Second, by simulation, we show that our centralized and distributed algorithms can perform close to the optimal. We also report an interesting result that cooperation is the key factor to produce optimal outcomes - a simple algorithm with tight cooperation among MANETs gives much better outcomes than a smart algorithm with loose cooperation.