Getting the grind size of coffee just right is crucial to extracting the flavor to brew that perfect cup. But while much attention has been paid to the relationship between taste and grind size, few people tend to ruminate on the relationship between grind size and the time it takes to brew the coffee — or if it will brew at all. In this article, we take a very informal and intuitive look at percolation theory and its evolution, its fascinating connection to mesh network connectivity¹, and the insights it gives us into tradeoffs in mesh networks.

Percolation was first studied by British mathematicians Broadbent and Hammersely in 1957. They considered the generalized problem of liquid flowing through porous material, and modeled it using a lattice network of nodes (which they called sites). Links (called bonds) between adjacent nodes could either be “closed” or “open” depending upon whether liquid could make it from one node to another. They then asked the question: suppose a fraction of bonds, chosen randomly, are open; then, how likely is it that there is a path of open bonds across the lattice — in other words, how likely is it that the liquid will flow through the material?

The figure below shows three lattices, each with a different fraction of open bonds. An open bond between two nodes is represented using a thick line and a closed bond is represented using a thin line². In the leftmost figure, only 10% of bonds are open, and there is no path across the lattice. In the rightmost figure, 70% of the bonds are open and there are plenty of paths across the lattice. In the middle figure, 50% of the bonds are open and there is just one path from top to bottom. 

The three lattices,  from right to left, could represent increasingly finely ground coffee — the finer the grind, the harder it is for it to percolate, which is why Vietnamese style coffee uses tightly placed plates for maximum pressure and takes 20 minutes to brew!

What the researchers showed mathematically was surprising and fascinating: in an infinite³ lattice, as you increase the fraction of open bonds, the odds of an infinite connected path stays at near-zero for a while and then very quickly jumps to 100% (see adjoining figure, which shows the probability). That is, the network transitions from no connectivity to full connectivity abruptly. In coffee terms, this means the transition from “no flow” to “full flow” occurs abruptly, not gradually.

The point of transition in a 2-D square lattice turns out to be at p=½ (50% of bonds open) as shown in the figure, and called the percolation threshold. Recall from the earlier example that at 50% open bonds we just about made connectivity across the lattice. The percolation threshold can change with the lattice dimension and shape (e.g. hexagonal).

It was soon observed that this phenomena occurs in several natural contexts: forest fires, boiling an egg, disease spread, etc. Such a phenomenon is said to percolate or have a phase transition. It has since then become a well-studied research topic in math and physics.

What does this have to do with wireless mesh networks? Enter continuum percolation.

Continuum percolation, pioneered by E.N. Gilbert from Bell Labs in 1961, extends the lattice model to a random placement of disks of some radius r in an infinite plane area and asks a similar question: for a given density of disks, what is the relation between r and the likelihood of an infinite cluster of touching disks? The adjoining figure shows this model, with the largest touching-disk cluster in red.

It turns out that the thresholding phenomena observed in the lattice model holds here as well. That is, there exists a threshold disk radius r below which an almost-connected network is very unlikely and above which it is very likely — in other words transitioning abruptly in a manner similar to the lattice model.

Now let us look at this picture carefully. Imagine that the center of each disk represents a wireless mesh device, and the disk radius r represents its transmission range. Then the above could well model the connectivity of mesh networks, except for the fact that for two nodes to be able to directly communicate, it is not sufficient for their signals to touch: each node’s signal should reach the other node. In other words, we need for the disks to enclose the neighboring node. But this is a straightforward scaling-by-2 operation that subsequent researchers showed doesn’t affect the key result.

Which is that wireless mesh network connectivity percolates – just like coffee!

Does all this math and the results based on “infinities” actually translate to finite real-world networks? Yes, it does. It has been verified over and over in the past several decades, but to get some more specific insights, we ran our own simulations of 50 randomly placed nodes within a 3×3 mile area. We increased the range of each node incrementally from 0.1 to 1.2 miles and studied the probability of the resulting mesh network being connected.

As is quite clear from the adjoining figure, there is a sudden transition. Wireless mesh network connectivity “percolates”. That is, it is subject to the same underlying phenomena as coffee brewing, forest fires, and more!

The fact that mesh connectivity percolates and is subject to abrupt rather than gradual change has important implications. It means that the sensitivity of mesh connectivity to transmission range is not uniform — it is highly sensitive in some scenarios, and not at all in others. For example, consider the points marked A,B,C in the figure. Given a choice between A (range 0.6 miles) and B (range 0.9 miles), the extra 0.3 miles is well worth it as it dramatically increases connectivity probability. On the other hand, one might want to choose B over C (range 1.2 miles) since the extra 0.3 miles has pretty much no effect on connectivity, and choosing C may give us a higher bitrate and/or require lower cost/power since these parameters are locked in a tradeoff.

We can also turn the question around and ask: Suppose we want a 95% chance of being connected; how many randomly placed nodes would we need in a 3×3 mile area to achieve that? Our results show that as you decrease the range (left to right on the x axis), you need more nodes to relay and connect the network. The “percolation effect” in this view manifests itself as a sharp increase in the required size around (below) the 0.3 mile range.

There are currently many apps that run on your smartphone and use peer-to-peer WiFi/Bluetooth to form a mesh network. Recently, one such app called Bridgefy has been in the news for helping connect the Hong Kong protestors privately without using infrastructure. Unfortunately though, since WiFi range is about 0.1-0.2 miles at best, upwards of 4000 randomly placed nodes are needed to connect a 3×3 mile area with such apps. On the other hand, the goTenna device with a range of about 1 mile can reduce the number of nodes by two orders of magnitude by taking advantage of the non-linearity in the relationship.

One may argue, and rightfully so, that the inferences above are based on a specific scenario. Nonetheless, stepping back and looking at the big picture, insights from percolation theory and our simulations tell us that for any given scenario, compromising on range could make us literally “fall off a cliff” (like from point B to A in the figure)! We do not want to mess with connectivity, and therefore should look to maximize range. This is what goTenna does, and as a result has been spectacularly popular with customers for whom mesh connectivity is, not surprisingly, of paramount importance.

Percolation theory, applicable to a diverse range of natural phenomena from liquid percolation to forest fire spreading, teaches us that sudden transitions of connectivity are a fundamental part of mesh networks. In particular, we cannot underestimate the value of device transmission range. Understanding this allows us to better design, tradeoff and deploy mesh networks.

Now it’s time to percolate that perfect cup of mocha!

¹This article is a sequel of sorts to my earlier article on range and connectivity
²Note that the presence of a link allows liquid to go through, hence it represents “open”.
³This is quite typical — the mathematics is a lot more tractable when considering infinite structures — but as we shall see, the main results hold for large finite structures.