Topology control
≈ 4 min read
Names in other languages
- ItalianoControllo della topologia
- EnglishTopology control
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
Topology control is a technique used in distributed computing to alter the underlying network (modeled as a graph) to reduce the cost of distributed algorithms if run over the resulting graphs. It is a basic technique in distributed algorithms.
For instance, a (minimum) spanning tree is used as a backbone to reduce the cost of broadcast from O(m) to O(n), where m and n are the number of edges and vertices in the graph, respectively. The term "topology control" is used mostly by the wireless ad hoc and sensor networks research community.
The main aim of topology control in this domain is to save energy, reduce interference between nodes and extend lifetime of the network. However, recently the term has also been gaining traction with regards to control of the network structure of electric power systems.
Topology control is a technique used in distributed computing to alter the underlying network (modeled as a graph) to reduce the cost of distributed algorithms if run over the resulting graphs. It is a basic technique in distributed algorithms.
For instance, a (minimum) spanning tree is used as a backbone to reduce the cost of broadcast from O(m) to O(n), where m and n are the number of edges and vertices in the graph, respectively. The term "topology control" is used mostly by the wireless ad hoc and sensor networks research community.
The main aim of topology control in this domain is to save energy, reduce interference between nodes and extend lifetime of the network. However, recently the term has also been gaining traction with regards to control of the network structure of electric power systems.
Tx range-based
Geometry-based: Gabriel graph (GG), Relative neighborhood graph (RNG), Voronoi diagram Spanning Tree Based: LMST, iMST Direction Based: Yao graph and Nearest neighbor graph, Cone Based Topology Control (CBTC), Distributed RNG Neighbor based: KNeigh, XTC Routing based: COMPOW
Hierarchical
CDS-based: A3, EECDS, CDS-Rule K Cluster-based: Low Energy Adaptive Clustering Hierarchy (LEACH), HEED
Global
DGTRec (Dynamic Global Topology Recreation): Periodically, wake up all inactive nodes, reset the existing reduced topology in the network and apply a topology construction protocol. SGTRot (Static Global Topology Rotation): Initially, the topology construction protocol must create more than one reduced topology (hopefully as disjoint as possible).
Then, periodically, wake up all inactive nodes, and change the current active reduced topology to the next, like in a Christmas tree. HGTRotRec (Hybrid Global Topology Rotation and Recreation) Work as the SGTRot, but when the current active reduced topology detects a certain level of disconnection, reset the reduced topology and invoke the topology construction protocol to recreate that particular reduced topology.
Local
DL-DSR (Dynamic Local DSR-based TM) This protocol, based on the Dynamic Source Routing (DSR) routing algorithm, recreates the paths of disconnected nodes when a node fails. In all of the above protocols can be found in. In Atarraya, two version of each of these protocols are implemented with different triggers: one by time, and the other one by energy.
In addition, Atarraya allows the pairing of all the topology construction and topology maintenance protocols in order to test the optimal maintenance policy for a particular construction protocol; it is important to mention that many papers on topology construction have not performed any study on this regard.
Text derived from https://en.wikipedia.org/w/index.php?oldid=1315275614 under CC BY-SA 4.0; modifications have been made.