Internet of things (IoT) envisions a network of billions of devices having various hardware and software capabilities communicating through internet infrastructure to achieve common goals. Wireless sensor networks (WSNs) having hundreds or even thousands of sensor nodes are positioned at the communication layer of IoT. In this study, the authors work on the connectivity estimation approaches for IoT-enabled WSNs. They describe the main ideas and explain the operations of connectivity estimation algorithms in this chapter. They categorize the studied algorithms into two divisions as 1-connectivity estimation algorithms (special case for k=1) and k-connectivity estimation algorithms (the generalized version of the connectivity estimation problem). Within the scope of 1-connectivity estimation algorithms, they dissect the exact algorithms for bridge and cut vertex detection. They investigate various algorithmic ideas for k connectivity estimation approaches by illustrating their operations on sample networks. They also discuss possible future studies related to the connectivity estimation problem in IoT.
Top1. Introduction
Internet of Things (IoT) will include billions of computational devices communicating through Internet infrastructure (Xu, 2014) (Giri, 2017) (Lee, 2017) (Rehman, 2017) (Balaji, 2019) (Yugha, 2020). A robust network for IoT must deal with the malfunctions without losing its connectivity. Robust networks are one of the important requirements in Internet of Things (IoT) because they provide a reliable infrastructure for communication of other devices. The nodes (vertices) in IoT systems are usually connected to each other over wireless channels and communicate by message passing. Hence failures in relay nodes can destroy the data transmission paths among nodes and waste many active resources. So, the underlying communication infrastructure of a reliable IoT should be able to tolerate the failures and keep the connectivity of active nodes.
Wireless sensor networks (WSNs) compose of motes which have the abilities of sensing from the environment and transmission of the collected data in a wireless manner (Akyildiz, 2002) (Arampatzis, 2005) (Paradis, 2007) (Alemdar, 2010) (Rawat, 2014) (Jino Ramson, 2017). WSNs are crucial technologies for IoT and positioned at the communication layer. WSNs can be used in various practical scenarios such as smart cities, healthcare, military surveillance, target tracking and habitat monitoring. Generally, WSNs include at least one special node called the sink in which the data is collected. An example WSN modeled with a graph is given in Figure 1. In this network model, there are 14 sensor nodes, and the ID of each node is written inside it. The vertex set V={0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13}. Transmission ranges are depicted as dashed circles. Possible communication channels (edges) between nodes are drawn with solid lines. The edge set E={(0,4), (0,12), (1,10), (2,5), (2,9), (2,13), (3,7), (3,8), (5,11), (5,12), (5,13), (6,8), (6,11), (6,12), (7,10), (8,13), (9,10), (11,12), (11,13)}.
A WSN is connected if at least one communication path between every pair of nodes is present. Since WSNs are designed to operate in a distributed manner, maintaining network connectivity is of utmost importance to achieve common application goals by transmitting messages between nodes. If a vertex’s removal partitions the communication network into disjoint segments, we call this vertex as cut vertex (articulation point). Identifying cut vertices are very important for wireless networks to expose their connectivity properties and vulnerable parts. In Figure 1, nodes 10 and 12 are cut vertices as removal of them partitions the network into 2 disjoint segments. If we remove node 10 from the network, the first connected component will include only node 1 and the second connected component will consist of other remaining nodes. Similarly, if we remove node 12 from the graph in Figure 1, the first segment will include nodes 0 and 4, and the other segment will consist of other remaining nodes. A bridge is an edge whose removal partitions the communication network into disjoint segments. In Figure 1, the edge (1,10) is a bridge which connects node 1 to the rest of network. Detections of bridges and cut vertices are crucial operations to investigate the link robustness of a WSN (Dagdeviren, 2013) (Akram, 2013) (Dagdeviren, 2014) (Dagdeviren 2016).
Connectivity is an essential requirement for many WSN applications belonging to various domains. For example, in a target tracking application utilized for military surveillance, the trajectory of the target can be monitored in a real time manner, if the sensor nodes are connected to the sink node. The monitoring nodes should send their sensed data in a timely manner to provide latest trajectory data of the target. If the connectivity of a network is corrupted, then ensuring data transfer from the sensor nodes is not possible. WSNs designed to operate in harsh environment such as mines, volcanic areas and rainforests may face with node faults. A failed node may completely stop the execution or it may transmit unwanted signals to the network. In order to reach a correct global decision, the nodes should execute consensus protocols where the network connectivity is an indispensable requirement. Hence, estimation and maintaining connectivity is of utmost importance in many practical scenarios.