CoMesh: Fully-Decentralized Control for Sense-Trigger-Actuate Routines in Edge Meshes

Commercial edge deployments with Internet of Things (IoT) devices are rapidly growing in size and density. There are over 10 B IoT devices today, expected to exceed 25 B by 2030 (J., 2021). For instance, smart buildings account for 1.26 B devices, and the smart building IoT sector is forecast to grow to 2.5 B devices by 2027, and comprise a $90+ B market (Memoori, 2022). Other emerging areas for edge IoT deployment include smart farms with robots and sensors (Vasisht et al., 2017; Ryu et al., 2015; Gan and Lee, 2018; Chandra and Collis, 2021; Sivakumar et al., 2021), battlefield deployments (Liu et al., 2022; Feng et al., 2020; Shahid et al., 2021), performance arenas (Fox et al., 2019; Turchet et al., 2018), and even indoor spaces such as warehouses (Fatima et al., 2022; Wang et al., 2022) and large marketplaces (Lampropoulos et al., 2019; Lin et al., 2016) with growing markets (Research, 2022; Aarti and Vineet, 2022; Future, 2022).

In such physically distributed settings, it is commonplace today to build mesh networks among the IoT and edge devices. Mesh networks can be robust, resilient, and allow easy “scale out” by adding and removing devices, without requiring a central operating unit (or hub) which may be overloaded and prolong latencies. Some devices may be “smart” devices capable of compute and storage (both small-scale), while other devices may be “simple” devices. Mesh networks are today being built using Wifi, Zigbee, Bluetooth, LoRa, etc. (K. et al., 2021; Guo et al., 2022; Li et al., 2022). Industrial mesh networks using IEEE 802.15.4, WirelessHart (Song et al., 2008), or IEC (ISO Central Secretary, 2016) are becoming common. There is rich literature at the networking layer, e.g., on how to build, configure, and route inside mesh networks (Akyildiz and Wang, 2005; Yang et al., 2005).

Sitting above the mesh network is the control plane—this needs to execute three kinds of actions: Sense-Trigger-Actuate (or STA). The control plane needs to sense: continuously collect measurements from multiple devices. Applications specify predicates, which are arbitrary Boolean clauses involving multiple device readings. When a predicate is satisfied, the control plane needs to trigger programmed series of actions that touch many devices. Third, because some of these actions may be long-running (e.g., mechanical movements, repetitive actions, or time-based actions such as water sprinklers), the control plane needs to initiate and monitor actuation of these commands (at multiple devices), while satisfying the challenging goal of maintaining consistency (Ahsan et al., 2021).

At a smaller scale, this STA abstraction exists in smart homes. The most popular programmatic abstraction for STA in smart homes, which is also applicable in edge meshes, is a routine. A routine is a sequence of commands that touches multiple devices, wherein each command executes an action on only one device. Multiple routines may be active at any given time, while many more remain dormant, waiting to be triggered. A routine may be triggered either based on sensor values, or at particular times, (or a combination thereof), or manually. Routines are offered today by Amazon Alexa (Amazon Alexa, 2014), Google Home (Google Home, 2016), Samsung SmartThings (Samsung Smart Things, 2012), and others. For instance, one routine at an office building may be triggered every week day at 9 pm, switching on security cameras, switching on specific external lights, and locking the outside doors. Another routine might be triggered by a combination of sensors and time, e.g., if the building temperature drops below 45 F between 11 pm and 6 am, take emergency actions to prevent bursting of pipes, and send notifications to facilities staff. During the day multiple routines may run continuously, e.g., some raising and lowering shades on the exterior of the building in order to regulate sunlight flowing into the building as a function of temperature, while other routines change interior lighting in different rooms and corridors as a function of occupancy, etc. Routines may be triggered either by humans (on demand) or automatically.

In a smart home the small number of devices, and the physically proximate nature of the home, means that a single central hub (e.g., an Alexa unit or a Google Home unit) can be used to execute all the three S-T-A categories of actions in the control plane. However, in commercial IoT deployments, the central hub approach becomes untenable as these deployments span large areas, involve many tens or hundreds of devices or more, and routines (active+dormant) numbering in several tens to a few hundred. In fact, a centralized hub may even be infeasible to even set up in really large areas like smart farms and battlefields. Hence mesh networks are growing in popularity for such settings.

Where it is possible to set up, the central hub may be overwhelmed very quickly by S-T-A traffic. For the setting with routines that we described, with a (say) 1 second fidelity for monitoring devices that trigger routines, monitoring just 500 devices in a building involves the home hub exchanging messages every 2 ms; even using AWS IoT’s liberal (suggested) 30 s ping frequency (AWS, 2022) means the central hub exchanges messages every 40 ms.

Distributed support for STA needs to be local, without needing a connection to the cloud. Central hubs in use today are themselves unreliable (Moore et al., 2020), and almost always connect to the cloud which itself may suffer outages (Grothaus, 2019). No mechanisms exist today to coordinate multiple local hubs for the specific STA workload of routines running over large edge meshes.

This paper presents CoMesh (Control Mesh), the first system for monitoring and management of routines (like those available via Amazon Alexa, Google Home, Samsung SmartThings, etc.) over edge meshes. CoMesh is naturally fully-decentralized and contains local distributed protocols running among available smart devices (other simple devices unable to run compute or memory, may also co-exist)—only a small fraction of devices need to be smart for CoMesh to work. CoMesh relies on neither a cloud nor on a local central hub.

CoMesh has to tackle four major challenges: (1) fully-decentralized monitoring, triggering, and actuation of routines, (2) load-balance work across both devices and time, (3) tolerate simultaneous failures of multiple devices, and (4) have load that is aware of the physical layout of devices. We propose a building block called a k-group, which is a dynamically selected subgroup of smart devices. This allows us to break the STA workload into fine granularities, by assigning a separate k-group for sensing each device (or a group thereof), and one k-group for triggering and actuating each routine. CoMesh’s k-groups use a combination of spatial load balancing and temporal load balancing: a) each k-group is selected via consistent hashing, and b) migrated periodically. The migration spreads the load of “heavy” subgroups (e.g., k-groups assigned to devices whose readings vary significantly, or k-groups assigned to frequently triggered routines) over the system. Within each k-group, we eschew using internet-based coordination systems like Zookeeper (Hunt et al., 2010) which may be expensive, and instead we carefully design fast and cheap versions of coordination techniques including agreement via quorums, leader election, and responding to failures of subgroup leader or members. Specifically, to tolerate $f$ failures, it suffices for each subgroup to contain $(2f+1)$ members.

To make proactive k-group migrations cheap, CoMesh uses zero-message exchange protocols—“zero-message” means that any node can (in the fast path), without exchanging any messages, calculate the current subgroup for any other given device or routine. In large spaces it is important keep communication local for latency and energy reasons—CoMesh adapts ideas from the space of locality-sensitive hashing (LSH) (Datar et al., 2004) to IoT and smart space settings, so that sub-group selections are in the locality of the monitored device(s), and yet retain the benefits of zero-message exchange mechanisms.

Underneath CoMesh we require: i) any mesh routing algorithm, and ii) a weakly consistent membership protocol for mesh networks (e.g., Medley (Yang et al., 2022)).

The contributions of this paper are:

• •

  We present CoMesh, the first local and fully-decentralized system for routine monitoring and management over edge meshes intended for sense-trigger-actuate scenarios.

• •

  CoMesh proposes a building block called k-groups, which help load-balance sensing, triggering and actuation work over devices. k-groups are selected using zero-message mechanisms and locality sensitive hashing, and within k-groups are running fast and cheap protocols for coordination and election.

• •

  We analyze and theoretically prove safety, liveness, and progress of CoMesh’s mechanisms.

• •

  We perform large-scale simulations as well as smaller-scale Raspberry Pi-4 deployment experiments.

We assume a crash-recovery model: IoT devices may fail (crash) at any time, and then recover at a later time. We do not target Byzantine (malicious) and leave them to future work. As is traditional in fault-tolerant literature, we assume that only up to $f$ simultaneous crash failures occur in the system. The value of $f$ can be calculated from the deployment settings. For instance, buildings contain power domains, each connected to a power breaker. A common failure mode is an entire power domain going out, thus making all the devices inside that domain fail. Thus one rule of thumb is to set $f$ to the number of smart devices in the largest power domain inside the building. Because a building contains many power domains, $f$ remains much smaller than $N$, the total number of devices in the building.

We assume a subset of devices ($>3$) are smart devices, equipped with (small) memory and computation capability—other simple (non-smart) IoT devices may also co-exist in the system. Smart devices may include any combination of IoT devices capable of arbitrary compute, Raspberry Pis, home hubs, handheld devices, etc. We assume non-smart devices can only receive and process commands, and respond to queries for status, but they cannot run any computation.

Since IoT devices are typically fixed early in the operation of a building, we assume that the locations of all devices are known by the smart devices ¹¹1Device motion can be treated as a failure event, followed by recovery event at its new location.. We assume smart devices’ clocks are synchronized (although CoMesh works with loose synchronization).

Smart devices communicate via a wireless network that is lossy. For generality, we assume the existence of a wireless ad-hoc routing protocol among smart devices (Dijkstra, 1959; Perkins et al., 2003; Johnson and Maltz, 1996). We assume any smart device can send a command to any IoT device. Finally, CoMesh is built atop a weakly-consistent membership service like Medley (Yang et al., 2022), which helps maintain a full membership list (of all IoT device IDs that are alive) at each smart device. Medley provides $O(1)$ detection time of failure and recovery events. Table 1 summarizes key terms, and Fig. 1 shows an example setting.

CoMesh’s protocols rely on its subgroup formation and maintenance. CoMesh uses these subgroups to sense-trigger-actuate routines and devices (described in following sections). We describe subgroup formation in this section.

CoMesh’s subgroups are called k-groups, signifying our goal of keeping a $k$-group’s size to be around (a small value) $k$. $k$ is a globally configured variable. To tolerate $f$ system-wide failures, we set $k=(2f+1)$. We present $k$-group selection (Sec. 3.1), election (Sec. 3.2), quorums (Sec. 3.3), temporal migration (Sec. 3.4), failure response (Sec. 3.5), and locality (Sec. 3.6).

We now describe how sense-trigger-actuation management of routines and devices builds atop the $k$-groupsof Section 3.

We formally analyze CoMesh’s properties. For brevity, we intuitively summarize our findings first. Then we state the formal theorems. The proofs can be found in Appendix A.

• $\bullet$

  Inheritance: When a k-group changes, the state held by the old leader and new leader are identical.

• $\bullet$

  Safety: No two routines that touch an overlapping set of devices, are allowed to execute simultaneously.

• $\bullet$

  Liveness: No routines deadlock.

• $\bullet$

  Progress: Every routine makes progress.

• $\bullet$

  We also calculate the (probabilistic) availability of the system when more than $f$ devices fail.

We now state the key results.

Practically, this scales. Fig. 3(a) shows that as $F$ rises, CoMesh availability drops as expected but still stays above 50% when $F{}$ grows up to 9$\times f$. Fig. 3(b) shows that in order to reach high availability ($p=50\%,90\%,99\%$), the required $F$ value drops very slow—this indicates scalability with the number of groups.

To perform large-scale experiments with 100s of nodes on CoMesh, as well as to measure its internal behavior, we wrote a custom simulator. Higher-fidelity simulators like NS3 have known scalability issues beyond a couple of hundred nodes. We measure both: i) user-facing metrics, e.g., latency to start routines, load balancing, etc., and ii) microbenchmarks of $k$-group operations.

Our simulator models network contention by scaling down network bandwidth based on density: specifically sending bandwidth from node $A$ to node $B$ is set to the default node bandwidth divided by number of 1-hop neighbors of $A$. We set default node bandwidth (Table 3) conservatively based on bandwidth numbers reported via user complaints on online forums about IoT devices (McNally, 2022; rpi, 2019). Latency on each hop is fixed to 1 time unit, as we assume that transmission radii are small. Ad-hoc routing is based on Dijkstra’s shortest paths.

We use three different network topologies: 3D grid, random, and clustered. We ensure the graph is connected. CoMesh was configured with topology-aware LSHMix (Sec. 3.6). Table 3 shows default parameters.

We implemented CoMesh in the Raspberry Pi (RPi) 4 environment. Our implementation contains 12.5K lines of Java code. Our deployments are on RPi 4 model B, possessing 2GB of LPDDR4 RAM and a Broadcom BCM2711 quad-core CPU of 1.5GHz Cortex-A72 cores. While Section 6 showed larger-scale simulation results, our goal with RPi’s is to benchmark the behavior of CoMesh’s core mechanism, i.e., k-groups, on a small number of real devices.

We deployed 11 RPi 4 devices in our lab, forming different mesh topologies. To attenuate RPi’s strong signal and create the mesh topology, we consistently wrap each device in aluminum foil to reduce transmission power to the lowest setting, 15dBm (Ahsan et al., 2021). While CoMesh works with any ad-hoc routing protocol, for concreteness we use OLSR routing (OLSR.org, 2021) due to its standardization in Pi 4s.

We configure CoMesh to use underneath it the open-source implementation of the Medley (Yang et al., 2022) membership protocol. CoMesh is configured to use $k$-groups with $k=3$, and monitors devices every second. To avoid cold start biases, we start measurements 10 s after CoMesh is initialized. Each data point involves at least 5 trial runs with different seeds. Epochs change every 60 s. Different routines may be triggered simultaneously. The same routine may be triggered multiple times, but never within less than 10 s of its own previous invocation. We use SLA locking (Sec.4.2.1).

We implement two Pi topologies shown in Fig. 10: (i) a 4 $\times$ 4 2D Grid-like topology and (ii) an L-shaped Line (modeling the outline of one floor of our office building). Each covers an area of 4 meters $\times$ 4 meters. The Line topology’s diameter is higher than Grid’s.

We have presented the CoMesh system that manages routines in a smart space (building, home, or campus) in a fully-decentralized way, without relying on any central components. Analysis of CoMesh’s techniques show that it achieves continuity (inheritance), safety, liveness, and progress. Our implementation and simulation of CoMesh under various topologies show that it scales well with increasing number of devices into the hundreds, and with larger values of $f$ (number of failures). CoMesh also balances load effectively, both over smart devices and over time. CoMesh opens the door for realizing self-managing versions of today’s smart space systems. Future directions include building central-distributed hybrid management systems, accounting for heterogeneity of smart devices, and energy considerations.