A preliminary approach to near-optimal multi-hop capacitated network design using grouping-dandelion encoded heuristics

摘要

In this paper we outline a novel global heuristic tool to deal with a combination of the Capacitated P-Median (CPMP) and the Capacitated Minimum Spanning Tree (CMST) problems. This preliminary approach provides an efficient (in terms of power consumption due to emission or signal interferences) traffic-flow design for a setup consisting of a number of spatially distributed nodes transmitting information to a common destination or sink node. Our proposal relies on gathering the information from the whole network through a fixed number of cluster heads or concentrators (CPMP), and then on routing the clustered traffic through these selected cluster-heads taking into account the accumulated capacity constraints (i.e. by seeking a capacitated minimum spanning tree). The proposed heuristic scheme is evaluated over nine synthetic scenarios of increasing complexity, from where it is concluded that by sequentially applying grouping- and dandelion-encoded stochastic optimization techniques, capacity-compliant minimum spanning trees can be generated. These preliminary results pave the way for future research aimed at adapting the proposed heuristics to resource-constrained wireless communication scenarios (e.g. cognitive radio), as well as at evaluating alternative procedures not necessarily based on a sequential treatment of the aforementioned problems.