查看文章

We propose a family of structures, namely, k-localized minimum spanning tree (LMST/sub k/) for topology control and broadcasting in wireless ad hoc networks. We give an efficient localized method to construct LMST/sub k/ using only O(n) messages under the local-broadcast communication model, i.e., the signal sent by each node would be received by all nodes within the node's transmission range. We also analytically prove that the node degree of the structure LMST/sub k/ is at most 6, LMST/sub k/ is connected and planar and, more importantly, the total edge length of the LMST/sub k/ is within a constant factor of that of the minimum spanning tree when k/spl ges/2 (called low weighted hereafter). We then propose another low weighted structure, called Incident MST and RNG Graph (IMRG), that can be locally constructed using at most 13n messages under the local broadcast communication model. Test results …