Finding Degree Constrained k-Cardinality Minimum Spanning Trees for Wireless Sensor Networks

摘要

In this paper, we consider the degree constrained k-cardinality minimum spanning tree network problem (k-DCMST). This problem arises as a combination of two classical optimization problems, namely the degree constrained and k-minimum spanning tree problems (Resp. DCMST and k-MST). Let G(V,E) be a connected undirected graph formed with vertex and edge sets V and E, respectively. The DCMST problem asks for a minimum spanning tree where each maximum vertex degree is limited to a certain constant d lower than the cardinality of V minus one whilst the k-MST asks for a minimum spanning sub-tree formed with к nodes chosen from set V. Consequently, the k-DCMST asks for a sub-tree formed with k vertices where each vertex has degree lower than or equal to d. This problem is mainly motivated from the domain of wireless sensor networks where connected backbone sub-tree topologies will be mandatorily required for future technologies in order to connect any network under the internet of things paradigm. Vertex degree constraints arise naturally in order to avoid overloaded nodes in the network. We propose two compact formulations for this problem. More precisely, a Miller-Tucker-Zemlin constrained version and a single flow based formulation that we further strengthen by using the Handshaking lemma and with valid inequalities adapted from the DCMST and dominating tree problems. Numerical results are given for complete and disk graph instances for different degree values. Our preliminary numerical results indicate that the flow based model allows one to obtain optimal solutions in less CPU time for most of the instances.