Topology control

Last updated

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 new 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.

Contents

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.

Topology construction and maintenance

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.

Topology construction algorithms

There are many ways to perform topology construction:

Federated Wireless is an American-based wireless communications company headquartered in Arlington County, Virginia. The company is "commercializing CBRS spectrum for 4G and 5G wireless systems".

Some examples of topology construction algorithms are:

Tx range-based

Gabriel graph

In mathematics and computational geometry, the Gabriel graph of a set of points in the Euclidean plane expresses one notion of proximity or nearness of those points. Formally, it is the graph with vertex set in which any points and are adjacent precisely if they are distinct, i.e. , and the closed disc of which line segment is a diameter contains no other elements of . Gabriel graphs naturally generalize to higher dimensions, with the empty disks replaced by empty closed balls. Gabriel graphs are named after K. Ruben Gabriel, who introduced them in a paper with Robert R. Sokal in 1969.

Relative neighborhood graph undirected graph used in computational geometry

In computational geometry, the relative neighborhood graph (RNG) is an undirected graph defined on a set of points in the Euclidean plane by connecting two points p and q by an edge whenever there does not exist a third point r that is closer to both p and q than they are to each other. This graph was proposed by Godfried Toussaint in 1980 as a way of defining a structure from a set of points that would match human perceptions of the shape of the set.

Voronoi diagram Type of plane partition

In mathematics, a Voronoi diagram is a partitioning of a plane into regions based on distance to points in a specific subset of the plane. That set of points is specified beforehand, and for each seed there is a corresponding region consisting of all points closer to that seed than to any other. These regions are called Voronoi cells. The Voronoi diagram of a set of points is dual to its Delaunay triangulation.

Hierarchical

Graphical examples

Topology maintenance algorithms

In the same manner as topology construction, there are many ways to perform topology maintenance:


Some examples of topology maintenance algorithms are:

Global

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.

Local

This protocol, based on the Dynamic Source Routing (DSR) routing algorithm, recreates the paths of disconnected nodes when a node fails.

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.

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.

Further reading

Many books and papers have been written in the topic:

Simulation of topology control

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.

Related Research Articles

Network topology arrangement of the various elements of a computer network; topological structure of a network and may be depicted physically or logically

Network topology is the arrangement of the elements of a communication network. Network topology can be used to define or describe the arrangement of various types of telecommunication networks, including command and control radio networks, industrial fieldbusses and computer networks.

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

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.

Wireless mesh network network topology

A wireless mesh network (WMN) is a communications network made up of radio nodes organized in a mesh topology. It is also a form of wireless ad hoc network.

Mesh networking type of computer network

A mesh network is a local 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 from/to clients. This lack of dependency on one node allows for every node to participate in the relay of information. Mesh networks dynamically self-organize and self-configure, which can reduce installation overhead. The ability to self-configure enables dynamic distribution of workloads, particularly in the event that a few nodes should fail. This in turn contributes to fault-tolerance and reduced maintenance costs.

Optimized Link State Routing Protocol

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 network (WSN) refers to a group of spatially dispersed and dedicated sensors for monitoring and recording the physical conditions of the environment and organizing the collected data at a central location. WSNs measure environmental conditions like temperature, sound, pollution levels, humidity, wind, and so on.

In computer network research, network simulation is a technique whereby a software program models the behavior of a network by calculating the interaction between the different network entities. Most simulators use discrete event simulation - the modeling of systems in which state variables change at discrete points in time. The behavior of the network and the various applications and services it supports can then be observed in a test lab; various attributes of the environment can also be modified in a controlled manner to assess how the network / protocols would behave under different conditions.

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.

A wireless ad hoc network (WANET) or Mobile ad hoc network (MANET) is a decentralised 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 managed (infrastructure) 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.

B.A.T.M.A.N. routing protocol

The Better Approach To Mobile Adhoc Networking (B.A.T.M.A.N.) is a routing protocol for multi-hop mobile ad hoc networks which is under development by the German "Freifunk" community and intended to replace the Optimized Link State Routing Protocol (OLSR).

Geographic routing routing methodology for wireless networks

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. and 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.

MRMP is a power-aware multicast protocol designed for large-scale mobile ad hoc networks, in which nodes may be with high mobility.

OCARI wireless communication protocol

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):

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.

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.

Sensor Media Access Control(S-MAC) is a network protocol for sensor networks. Sensor networks consist of tiny, wirelessly communicating computers, which are deployed in large numbers in an area to network independently and as long as monitor their surroundings in group work with sensors, to their energy reserves are depleted. A special form of ad hoc network, they make entirely different demands on a network protocol and therefore require specially for them developed network protocols. Sensor Media Access Control specifies in detail how the nodes of a sensor network exchange data, controls the Media Access Control (MAC) to access the shared communication medium of the network, regulates the structure of the network topology, and provides a method for synchronizing.

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.

References

  1. , Local Minimal Spanning Tree
  2. , Iterative Minimum Spanning Tree
  3. [ permanent dead link ], KNEIGH
  4. "Archived copy" (PDF). Archived from the original (PDF) on 2007-07-05. Retrieved 2009-04-30.CS1 maint: archived copy as title (link), XTC
  5. , COMPOW , Hi
  6. , A3: A topology construction protocol for WSN
  7. , EECDS
  8. , CDS-Rule K
  9. , HEED
  10. 1 2 Topology Control by Labrador and Wightman, Topology Control in Wireless Sensor Networks
  11. 1 2 , Atarraya, a simulator for topology control in wireless sensor networks
  12. Topology Control by Santi, Topology Control in Wireless Ad Hoc and Sensor Networks
  13. Protocols and Architectures for Wireless Sensor Networks by Holger Karl and Andreas Willig, Protocols and Architectures for Wireless Sensor Networks
  14. Q. Guan, F.R. Yu, S. Jiang, and V.C.M. Leung, “Capacity-Optimized Topology Control for MANETs with Cooperative Communications,” IEEE Trans. Wireless Comm., vol. 10, no. 7, pp. 2162-2170, July 2011.