Critical Nodes Detection in IoT-Based Cyber-Physical Systems: Applications, Methods, and Challenges

Critical Nodes Detection in IoT-Based Cyber-Physical Systems: Applications, Methods, and Challenges

Onur Ugurlu, Nusin Akram, Vahid Khalilpour Akram
DOI: 10.4018/978-1-7998-4186-9.ch012
(Individual Chapters)
No Current Special Offers


The new generation of fast, small, and energy-efficient devices that can connect to the internet are already used for different purposes in healthcare, smart homes, smart cities, industrial automation, and entertainment. One of the main requirements in all kinds of cyber-physical systems is a reliable communication platform. In a wired or wireless network, losing some special nodes may disconnect the communication paths between other nodes. Generally, these nodes, which are called critical nodes, have many undesired effects on the network. The authors focus on three different problems. The first problem is finding the nodes whose removal minimizes the pairwise connectivity in the residual network. The second problem is finding the nodes whose removal maximizes the number of connected components. Finally, the third problem is finding the nodes whose removal minimizes the size of the largest connected component. All three problems are NP-Complete, and the authors provide a brief survey about the existing approximated algorithms for these problems.
Chapter Preview


Internet of Things (IoT) is one the fastest growing and most promising technologies that already have influenced the daily life of most people in different areas. Especially with the emerging of smartphones, people can easily connect to remote devices and control them using their phones. Intelligent homes that automatically control temperature, lights, doors, security, and entertainment facilities is an example of IoT based systems (Zielonka, 2020). The number and diversity of furniture that connects to the internet are growing day by day. Most of the recently produced refrigerators, washing machines, coffeemakers, sound systems, televisions, air conditioning systems, and dishwashers allow their users to control them over the Internet or local network. Intelligent greenhouses (Castañeda-Miranda, 2020), autonomous vehicles (Minovski, 2020), smart manufacturing systems (Tran, 2021), intelligent transportation systems (Lin, 2020), and indoor or outdoor tracking systems (Adardour, 2021) are some other applications areas of IoT.

The recent advances in hardware and electronic technologies have led to the production of small, fast, and energy-efficient devices that can store a large amount of data, precisely sense different events, perform heavy computation, and communicate over different channels such as WiFi, Bluetooth, and 5G technologies. Generally, these devices may run embedded programs to complete the given tasks. They support different communication ports so the users can use them inside other smart things or directly connect them over available ports. The available devices for IoT may connect to the Internet over cabled networks, wireless networks, or multi-hop networks. In this way, we may establish IoT networks almost everywhere, even in harsh environments such as forests or mountains.

One of the most essential requirements in IoT-based systems is communication. Generally, IoT-based systems consist of many different nodes for various tasks such as sensing the events or quantities, processing the gathered data, storing the information, and performing some mechanical tasks such as opening a door or rotating a valve. Most of these tasks are completed by remote nodes which are controlled over the Internet or a communication platform. Based on the application type and available infrastructure, different platforms can be used for establishing the connection between the nodes or end-users. For example, in intelligent home controlling systems, the IoT nodes can connect to the Internet over a local area network or WiFi platform. In a public transportation system or in an outdoor tracking system (for example, tracking cargo packets), the nodes may use 4G or 5G cellular network to communicate with the controlling center. In this way, the users may track the real-time location of the next bus or their cargo. As another example, in a forest fire controlling system, the nodes may use multi-hop ad-hoc connections to cover a wide area and send their gathered data to the controlling center. In this system, each node should send its collected data to the next node until they reach the base station which is connected to the Internet.

Key Terms in this Chapter

Distributed System: A set of independent nodes with local memory and processor that can communicate over a communication platform.

Critical Nodes: A node whose failure reduce the fault tolerance or destroys the connectivity of the network.

Fault Tolerance: Tolerating the failure of nodes or links in a network while keeping the network functionality.

Routing: The process of finding a communication path between two nodes in a network.

Bottleneck: A subset of nodes or links that slow down the traffic flow in the network.

Connected Component: A set of nodes in a partitioned graph that have at least one path to each other.

Internet of Things: A set of devices that can communicate over the internet to perform some tasks.

Complete Chapter List

Search this Book: