Wireless Sensor and Actuator Networks: Algorithms and Protocols for Scalable Coordination and Data Communication

2.9 RNG AND LMST

The next section on minimal energy broadcasting is based on some geometric structures. These structures will be described in this section. Basic familiarity with minimal spanning tree (MST) is assumed. Minimal spanning tree for a weighted graph with n nodes is a minimal connected graph containing these n nodes as vertices. Minimal spanning tree is a tree since otherwise the longest edge in any cycle can be removed without affecting connectivity. This observation is used in Kruskal's algorithm (Kruskal, 1956) to construct MST. All edges are sorted in increasing order, and considered for inclusion in MST in that order. The candidate edge is included in MST if it does not create a cycle in an already constructed portion of the MST.

Relative neighborhood graph (RNG) and localized minimal spanning tree (LMST) are two well-known planar graphs that are utilized in various topology constructions. A planar graph is a graph, which can be drawn on the plane in such a way that the edges intersect only at their end points. Figure 2.19 gives examples of an RNG and an LMST and illustrates also planar graphs. All nondashed edges form RNG while bold edges form LMST. The dashed edges are remaining edges in UDG. The edge (1, 4) belongs to RNG while it does not belong to LMST since the edge is not in MST of the one-hop subgraph of nodes 1 (will be explained next).

An edge uv is in RNG (first defined in Toussaint (1980)) if it is not the longest edge in any triangle uvw where w is ...