Degree-bounded minimum spanning tree for unit disk graph

Degree-bounded minimum spanning tree (DBMST) has been widely used in many applications of wireless sensor networks, such as data aggregation, topology control, etc. However, before construction of DBMST, it is NP-hard to determine whether or not there is a degree-k spanning tree for an arbitrary graph, where k is 3 or 4. The wireless sensor network is usually modeled by a unit disk graph (UDG), where two vertices are connected in UDG G(R) if their Euclidean distance is not more than a given constant R in the field. The previous works have predicated the necessary conditions for the existence of DBMST on UDG. Given that sub-graphs G(R/2) and can keep connected, there exist degree-3 or degree-4 spanning trees for UDG G(R). In this paper, we design two algorithms to construct the degree-3 and degree-4 spanning trees for UDG respectively. The more relaxed conditions are explored for the existence of DBMST for unit disk graphs according to the proposed algorithms. That is, given that sub-graphs G(R/1.81) and keep connected, the existence of degree-3 and degree-4 spanning trees is guaranteed for UDG G(R). The theoretical analyses show that the performances of constructed degree-3 and degree-4 spanning trees are at most and times as that of minimum spanning tree (MST) respectively, where α≥2 is a constant. The simulation results show the high efficiency of two proposed algorithms. For example, total link weights of degree-3 and degree 4 spanning trees are about 1.05 and 1.01 times as that of MST where α is 2.