Maximum entropy principle-based algorithm for simultaneous resource location and multihop routing in multiagent networks

This paper presents a framework that develops algorithms for solving combined locational and multihop routing optimization problems. The objective is to determine resource node locations in a multiagent network and to specify the multihop routes from each agent to a common destination through a network of resource nodes that minimize total communication cost. These problems are computationally complex (NP-hard) where the cost functions are riddled with multiple minima. Algorithms based on Maximum Entropy Principle, which guarantee local minima and are heuristically designed to seek the global minimum are presented. These algorithms accommodate practical constraints on resource nodes as well as on the routing network architectures. Simulation results show that the multihop routes and resource locations allocated by these algorithms achieve lower costs (as low as 47 percent) than those algorithms where resource locational optimization is done without multihop routing or where the locational and routing optimization objectives are separated. The enabling feature of these algorithms is accommodating problems with resource constraints which is demonstrated through simulations.