{'fraction_non_alphanumeric': 0.029301075268817204, 'fraction_numerical': 0.002150537634408602, 'mean_word_length': 5.328231292517007, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
‘ Ripples ’ : A Message-Efficient , Distributed Clustering Algorithm for Wireless Sensor and Actor Networks

Reducing sizes and increasing capabilities of wireless communication devices as well as electronic and electromechanical systems have made it possible to not only continuously monitor a physical phenomenon by staying very close to or even inside it, but also to quickly and autonomously perform the required action upon sensing an event. Distributed, largescale networks that exhibit this capability are Wireless Sensor and Actor Networks (WSAN). Like wireless sensor networks (WSN), WSAN consist of dense deployment of large number of small, low-cost and low-power sensor nodes and additionally contain few powerful and resource-rich actor nodes. WSAN need to address issues pertaining to energy conservation and unattended, untethered operation present in WSN and additionally face challenges due to heterogeneity of nodes and realtime requirements of the applications. Lifetime of sensor nodes determines lifetime of the network and is crucial for the sensing capability. Among the important techniques proposed for prolonging the network lifetime by exploiting redundant deployment is using hierarchical architecture or clustering. However, the primary drawback of hierarchical control is the control message overhead; it is essential that the overhead does not dominate the network operations cost. The clustering algorithm should also scale to the network sizes and the nodes that are awake at any point in time must preserve the desired sensing coverage of the entire network utilizing the redundant deployment. Also, it has been shown that in sensor networks, a fundamental tradeoff exists between energy and latency for data delivery [1]. If clustering should lead to efficient MAC and Routing protocols it could effectively address the real-time requirements posed by WSAN. The principle contributions of this paper are as follows. We propose ‘Ripples’, an extremely lightweight scalable clustering algorithm for clustering in WSN. Inspired by the cellular infrastructure model, ‘Ripples’ produces clusters of bounded geographic size (given a certain node distribution density this guarantees a bound on the number of nodes in a cluster as well), handles perturbations in the network locally in space and in time. The novelty of the algorithm lies in its deterministic operation to optimally exploit the redundant deployment and produce balanced clusters while retaining the desired sensing coverage with minimum possible control overhead. Extensive simulation has been conducted and results are presented. We compare the performance of ‘Ripples’ against ‘Rapid’ and ‘Persistent’ [2]. These two algorithms achieve order of magnitude saving in terms of messages exchanged compare to the classical ‘Expanding Ring’ algorithm [3]. Of the two, ‘Rapid’ achieves better message efficiency at the cost of producing worst-case cluster sizes smaller than required. ‘Persistent’ produces clusters of desired size but is costlier. We demonstrate that ‘Ripples’ uses as less as 50% of messages compared to ‘Rapid’ to produce clusters of desired sizes, like ‘Persistent’. The clustering approach used in ‘Ripples’ is similar to the one proposed in ‘GS’ [4]. We compare the control overheads of ‘Ripples’ with that of ‘GS’, and prove that the overheads for ‘Ripples’ are as less as 25% of those for ‘GS’. A sub-module ‘Bind’ has been outlined that associated the clusters to their nearest actor nodes; this is required for real-time response. ‘Bind’ works along with ‘Ripples’ and creates data tables that can be used by the data dissemination algorithm, medium access and routing protocols for efficient operation.