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.
Lately, topology control algorithms have been divided into two subproblems: topology construction, in charge of the initial reduction, and topology maintenance, in charge of the maintenance of the reduced topology so that characteristics like connectivity and coverage are preserved.
This is the first stage of a topology control protocol. Once the initial topology is deployed, specially when the location of the nodes is random, the administrator has no control over the design of the network; for example, some areas may be very dense, showing a high number of redundant nodes, which will increase the number of message collisions and will provide several copies of the same information from similarly located nodes. However, the administrator has control over some parameters of the network: transmission power of the nodes, state of the nodes (active or sleeping), role of the nodes (Clusterhead, gateway, regular), etc. By modifying these parameters, the topology of the network can change.
Upon the same time a topology is reduced and the network starts serving its purpose, the selected nodes start spending energy: Reduced topology starts losing its "optimality as soon as full network activity evolves. After some time being active, some nodes will start to run out of energy. Especially in wireless sensor networks with multihopping, intensive packet forwarding causes nodes that are closer to the sink to spend higher amounts of energy than nodes that are farther away. Topology control has to be executed periodically in order to preserve the desired properties such as connectivity, coverage, density.
There are many ways to perform topology construction:
Some examples of topology construction algorithms are:
In the same manner as topology construction, there are many ways to perform topology maintenance:
Some examples of topology maintenance algorithms are:
Periodically, wake up all inactive nodes, reset the existing reduced topology in the network and apply a topology construction protocol.
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.
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.
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. [10] In Atarraya, [11] 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.
Many books and papers have been written in the topic:
There are many networking simulation tools, however there is one specifically designed for testing, design and teaching topology control algorithms: Atarraya. [11]
Atarraya is an event-driven simulator developed in Java that present a new framework for designing and testing topology control algorithms. It is an open source application, distributed under the GNU V.3 license. It was developed by Pedro Wightman, a Ph.D. candidate at University of South Florida, with the collaboration of Dr. Miguel Labrador. A paper with the detailed description of the simulator was presented in SIMUTools 2009. The paper can be found in this link.
Link-state routing protocols are one of the two main classes of routing protocols used in packet switching networks for computer communications, the other being distance-vector routing protocols. Examples of link-state routing protocols include Open Shortest Path First (OSPF) and Intermediate System to Intermediate System (IS-IS).
Zigbee is an IEEE 802.15.4-based specification for a suite of high-level communication protocols used to create personal area networks with small, low-power digital radios, such as for home automation, medical device data collection, and other low-power low-bandwidth needs, designed for small scale projects which need wireless connection. Hence, Zigbee is a low-power, low data rate, and close proximity wireless ad hoc network.
A wireless mesh network (WMN) is a communications network made up of radio nodes organized in a mesh topology. It can also be a form of wireless ad hoc network.
A mesh network is a local area network topology in which the infrastructure nodes connect directly, dynamically and non-hierarchically to as many other nodes as possible and cooperate with one another to efficiently route data to and from clients.
The Optimized Link State Routing Protocol (OLSR) is an IP routing protocol optimized for mobile ad hoc networks, which can also be used on other wireless ad hoc networks. OLSR is a proactive link-state routing protocol, which uses hello and topology control (TC) messages to discover and then disseminate link state information throughout the mobile ad hoc network. Individual nodes use this topology information to compute next hop destinations for all nodes in the network using shortest hop forwarding paths.
Wireless sensor networks (WSNs) refer to networks of spatially dispersed and dedicated sensors that monitor and record the physical conditions of the environment and forward the collected data to a central location. WSNs can measure environmental conditions such as temperature, sound, pollution levels, humidity and wind.
Dynamic Source Routing (DSR) is a routing protocol for wireless mesh networks. It is similar to AODV in that it forms a route on-demand when a transmitting node requests one. However, it uses source routing instead of relying on the routing table at each intermediate device.
Destination-Sequenced Distance-Vector Routing (DSDV) is a table-driven routing scheme for ad hoc mobile networks based on the Bellman–Ford algorithm. It was developed by C. Perkins and P.Bhagwat in 1994. The main contribution of the algorithm was to solve the routing loop problem. Each entry in the routing table contains a sequence number, the sequence numbers are generally even if a link is present; else, an odd number is used. The number is generated by the destination, and the emitter needs to send out the next update with this number. Routing information is distributed between nodes by sending full dumps infrequently and smaller incremental updates more frequently.
Flooding is used in computer networks routing algorithm in which every incoming packet is sent through every outgoing link except the one it arrived on.
A wireless ad hoc network (WANET) or mobile ad hoc network (MANET) is a decentralized type of wireless network. The network is ad hoc because it does not rely on a pre-existing infrastructure, such as routers in wired networks or access points in wireless networks. Instead, each node participates in routing by forwarding data for other nodes, so the determination of which nodes forward data is made dynamically on the basis of network connectivity and the routing algorithm in use.
Geographic routing is a routing principle that relies on geographic position information. It is mainly proposed for wireless networks and based on the idea that the source sends a message to the geographic location of the destination instead of using the network address. In the area of packet radio networks, the idea of using position information for routing was first proposed in the 1980s for interconnection networks. Geographic routing requires that each node can determine its own location and that the source is aware of the location of the destination. With this information, a message can be routed to the destination without knowledge of the network topology or a prior route discovery.
In multi-hop networks, Adaptive Quality of Service routing protocols have become increasingly popular and have numerous applications. One application in which it may be useful is in Mobile ad hoc networking (MANET).
OCARI is a low-rate wireless personal area networks (LR-WPAN) communication protocol that derives from the IEEE 802.15.4 standard. It was developed by the following consortium during the OCARI project that is funded by the French National Research Agency (ANR):
IEEE 802.11s is a wireless local area network (WLAN) standard and an IEEE 802.11 amendment for mesh networking, defining how wireless devices can interconnect to create a wireless LAN mesh network, which may be used for relatively fixed topologies and wireless ad hoc networks. The IEEE 802.11s task group drew upon volunteers from university and industry to provide specifications and possible design solutions for wireless mesh networking. As a standard, the document was iterated and revised many times prior to finalization.
MyriaNed is a wireless sensor network (WSN) platform developed by DevLab. It uses an epidemic communication style based on standard radio broadcasting. This approach reflects the way humans interact, which is called gossiping. Messages are sent periodically and received by adjoining neighbours. Each message is repeated and duplicated towards all nodes that span the network; it spreads like a virus.
EraMobile -Epidemic-based Reliable and Adaptive Multicast for Mobile ad hoc networks is a bio-inspired reliable multicast protocol targeting mission critical ad hoc networks. EraMobile supports group applications that require high reliability and low overhead with loose delivery time constraints. The protocol aims to deliver multicast data with maximum reliability and minimal network overhead under adverse network conditions. EraMobile adopts an epidemic-based approach, which uses gossip messages, to cope with dynamic topology changes due to the mobility of network nodes. EraMobile's epidemic mechanism does not require maintaining any tree- or mesh-like structure for multicast operation. It requires neither a global nor a partial view of the network, nor does it require information about neighboring nodes and group members. The lack of a central structure for multicast lowers the network overhead by eliminating redundant data transmissions. EraMobile contains a simple adaptivity mechanism which tunes the frequency of control packages based on the node density in the network. This adaptivity mechanism helps the delivery of data reliably in both sparse networks -in which network connectivity is prone to interruptions- and dense networks -in which congestion is likely because of shared wireless medium-.
A mobile wireless sensor network (MWSN) can simply be defined as a wireless sensor network (WSN) in which the sensor nodes are mobile. MWSNs are a smaller, emerging field of research in contrast to their well-established predecessor. MWSNs are much more versatile than static sensor networks as they can be deployed in any scenario and cope with rapid topology changes. However, many of their applications are similar, such as environment monitoring or surveillance. Commonly, the nodes consist of a radio transceiver and a microcontroller powered by a battery, as well as some kind of sensor for detecting light, heat, humidity, temperature, etc.
Zebra Media Access Control (Z-MAC) is a network protocol for wireless sensor networks. It controls how a Media Access Control (MAC) accesses a common communication medium of a network.
In graph theory, LASCNN is a Localized Algorithm for Segregation of Critical/Non-critical Nodes The algorithm works on the principle of distinguishing between critical and non-critical nodes for network connectivity based on limited topology information. The algorithm finds the critical nodes with partial information within a few hops.
{{cite web}}: CS1 maint: archived copy as title (link), XTC