O'Reilly logo

Wireless Sensor and Actuator Networks: Algorithms and Protocols for Scalable Coordination and Data Communication by Ivan Stojmenovic, Amiya Nayak

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

7.3 THE MINIMUM SPANNING TREE

MSTs are emblematic example of topological structures commonly used in communication networks. In a graph G = (V, E), an MST is a connected subset of the graph that contains all the vertices and minimizes the overall sum of its edge lengths (or more generally their weight). A well-known centralized algorithm to build such a structure is the Kruskal's algorithm, which mainly works as follows. All edges of E are sorted in the increasing weight order, and a new empty set E′ is created. For each edge e in the ordered set E, e is added to E′ if it does not create a loop in G′ = (V, E′). The resulting graph G′ is an MST of G.

The Figure 7.1 gives an example of MST that has been built over a random UDG. As usual, in wireless networks, the length of the edges was used as their weight. Note that if several edges have the same length, then several equivalent MSTs may exist, but this nondeterminism can be easily broken based on additional parameters (such as a comparison between nodes IDs).

An interesting fact about the MST is that its longest edge also corresponds to the optimal common transmission radius (i.e., the minimal radius such that network connectivity is preserved). This follows directly from Kruskal's algorithm, this edge being the last added edge in E′.

images

Figure 7.1 A minimum spanning tree on top of a random unit graph.

Considering a few related results, ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required