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.17
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.
[1], Local Minimal Spanning Tree http://www.cs.princeton.edu/~chazelle/pubs/mstapprox.pdf ↩
[2], Iterative Minimum Spanning Tree http://portal.acm.org/citation.cfm?id=1371333 ↩
[3][permanent dead link], KNEIGH http://dienst.isti.cnr.it/Dienst/UI/2.0/Describe/ercim.cnr.iit/2003-TR-09?tiposearch=cnr&langver= ↩
"Archived copy" (PDF). Archived from the original (PDF) on 2007-07-05. Retrieved 2009-04-30.{{cite web}}: CS1 maint: archived copy as title (link), XTC https://web.archive.org/web/20070705211948/http://www.dcg.ethz.ch/publications/wman04.pdf ↩
[4], COMPOW , Hi http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.28.8586 ↩
[5], A3: A topology construction protocol for WSN https://ieeexplore.ieee.org/document/4697849/;jsessionid=DA08F2BC69EB47E1596923CB1E880CCB?arnumber=4697849 ↩
[6], EECDS http://portal.acm.org/citation.cfm?id=1143709 ↩
[7], CDS-Rule K http://portal.acm.org/citation.cfm?id=1159231 ↩
[8], HEED https://ieeexplore.ieee.org/document/1347100/;jsessionid=62C51A3A5F009E9FD64BFDD4B8317A7F?tp=&arnumber=1347100&isnumber=29662 ↩
Topology Control by Labrador and Wightman, Topology Control in Wireless Sensor Networks https://www.amazon.com/dp/1402095848 ↩
[9], Atarraya, a simulator for topology control in wireless sensor networks http://www.cse.usf.edu/~labrador/Atarraya/ ↩
J. Pan, Y. Hou, L. Cai, Y. Shi, and X. Shen, Topology control for wireless sensor networks, Proc. ACM Int'l Conf. on Mobile Comp. and Netw. (MobiCom'03), pp. 286--299, San Diego, California, USA, Sept. 14--19, 2003. https://dl.acm.org/doi/10.1145/938985.939015 ↩
Topology Control by Santi, Topology Control in Wireless Ad Hoc and Sensor Networks https://www.amazon.com/dp/0470094532 ↩
Protocols and Architectures for Wireless Sensor Networks by Holger Karl and Andreas Willig, Protocols and Architectures for Wireless Sensor Networks https://www.amazon.com/dp/0470519231 ↩
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. https://ieeexplore.ieee.org/document/5898377/;jsessionid=499AC4A5F0FC649AFD985D3E4F17CA8B?arnumber=5898377 ↩