Whitepaper: On the Connectivity of Mesh Networks
Range Is Everything.
Imagine that we need to provide mesh-based communications in a three-by-three mile area. This could be a disaster zone, a small suburban town seeking alternate communications, a military deployment or a large group of hikers. Assume that mesh connectivity is provided by hopping through both user-owned and“pure relay” devices – we will refer to them collectively also as nodes.
For the network to be useful, the nodes need to be connected. By connected, we mean that every node should be able to communicate with every other node via some number of hops. Connectivity is of paramount importance – if you are isolated, or part of a small cluster cut off from the rest of the network, your mesh device is useless. It is clear that the more nodes you place, the better your chances of connectivity. But what is the minimum number of nodes in the area needed to make the mesh network connected?
For each RF technology and associated range, what is the cost of coverage, i.e., connecting a given area?”
The answer depends on the communication range of the device, which in turn depends upon RF technology. In the last decade or so, WiFi-direct has emerged as the technology of choice for license-free, carrier-free mobile wireless communications. It is not surprising then, that a vast majority of peer-to-peer mesh networking solutions have adopted WiFi or WiFi-direct for inter-device communications. But WiFi is not the only choice — other options include LTE-direct and long-range technologies.
Each technology provides a different tradeoff between range, data rate and cost. This brings up a related question: For each RF technology and associated range, what is the cost of coverage, i.e., connecting a given area? This is especially pertinent in light of blockchain-based protocols that are being proposed to incentivize mesh network participation. Most of these projects explicitly or implicitly base their efforts on a particular technology (WiFi being the most popular). Do their choices make sense in terms of connectivity potential and cost — are their “coins” of any value?
Using graph-theoretic models and simulations, we have analyzed the connectivity of a mesh network as a function of the number of nodes, for WiFi-direct, LTE-direct and goTenna. Here are our findings:
Figure 1 (above) shows the connectivity for WiFi-direct based network with 50 randomly placed nodes in a three-by-three mile area, based on a simulation. We used a range of 200 m for WiFi-direct, which is likely optimistic. The result is disastrous — we mostly get singletons, and a handful of very small clusters with three nodes or fewer.
Figure 2 (above) shows the connectivity for WiFi-direct based network with 500 nodes. Surely this should be enough?! Unfortunately, the improvement is only marginal. We do get clusters of 10-15 nodes, but overall this is not a network you can usefully deploy. And as Figure 3 (below) shows, bringing the number of nodes up to 1,000 nodes doesn’t solve the problem either.
At this point, it’s becoming clear that WiFi range is limited enough to be largely useless. Recently, and possibly because of this limitation of WiFi, LTE-direct has been garnering attention. LTE-direct allows two smartphones with LTE service to connect directly without going through a cell tower.
Figure 4 (a)-(c) (below) shows the connectivity for LTE-direct based network with 50, 250 and 500 nodes respectively. At 50 nodes the situation is not much better than WiFi, and even with 250 nodes the network remains disconnected! Even when we see connectivity at 500 nodes, a few are dangerously close to being isolated. Further, the “diameter” of this network is 13, meaning that some messages may have to go as many as 13 hops before they reach their destination. At $500 each, the cost of 500 smartphones to cover a three-by-three mile area would be about $250,000.
goTenna Mesh’s range is three times greater than that of an LTE-direct device, yet it reduces the number of nodes required to achieve robust connectivity by a factor of 20!”
WiFi-direct and LTE-direct use the same “hardware” — the smartphone — for both the mesh router and the application platform. An alternate design, pioneered by goTenna, is to decouple the two functions. In the goTenna system, the smartphone pairs with a dedicated small, light, low-power, low-cost device that forms a mesh network with other such devices. The goTenna device has a range measured in miles, depending upon terrain. Using the most conservative estimate of 1 mile range, how many nodes would be required to cover a three-by-three mile area?
Figure 5 (below) shows the connectivity for a goTenna network (using range of one mile) using just 25 nodes. Not only is the network connected, but the connectivity is robust — every node can reach every other node via at least two disjoint paths! Further, the diameter of the network in the figure is only four hops.
Table 1 (below) summarizes the above information, along with a cost estimate for covering the three-by-three mile area with each technology at $500 per smartphone, and $80 per goTenna Mesh device. For the goTenna numbers, we assume that each node consists of a goTenna device plus a smartphone (although goTenna Mesh can operate as an unpaired relay). The WiFi numbers assume that equipment is newly provisioned, whereas in reality users may already have smartphones with WiFi-direct, and to a lesser extent, LTE-direct. On the other hand, population distribution tends to be highly clustered rather than uniformly random, and therefore not conducive to connectivity without additional relays. Thus, the table represents only a high-level, ballpark comparison. Nonetheless, it is clear from the magnitude of the cost difference that long-range, low-cost technologies such as goTenna handily win when it comes to overall cost of coverage.
| Range | Nodes needed for connectivity | Overall equipment cost | |
|---|---|---|---|
| WiFi Direct | 200m | > 1000 | > $500,000 |
| LTE Direct | 500m | ~ 500 | ~ $250,000 |
| goTenna | 1 mile (1600m) | < 25 | < $14,500 |
It is not surprising that a higher range implies fewer nodes for coverage. What is remarkable, however, is the outsized impact of range in terms of nodes and cost. goTenna Mesh’s range is three times greater than that of an LTE-direct device, yet it reduces the number of nodes required to achieve robust connectivity by a factor of 20! WiFi devices, whose range is about 12 percent of goTenna Mesh devices, require 40 times as many nodes to reach connectivity.
But wait, you might say, don’t WiFi and LTE have higher data rates? Indeed, they do. However, when building out a mesh network, connectivity is more important. After all, if you are not connected, what good does a high data rate do?
Analyzing the various options, it turns out that range has a non-linear and outsized impact on connectivity.”
Mesh networks suffer from what we call a “zero-start” problem — users need connectivity to participate in a network, but achieving connectivity requires participating users. Only with ranges on the order of goTenna devices can one hope to solve the zero-start problem. Once we “bootstrap” connectivity, organic growth of the network may well provide enough nodes to reduce range and increase bit rate.
Connectivity, and its relationship to node-density, has been and is a topic of much theoretical research in academia. An interesting aspect that has emerged is that as you increase range (or number of nodes), connectivity happens suddenly. Just below a critical threshold of range, for instance, the network is still heavily fragmented. But with just a small increase, it is connected!
Amazingly, this phenomenon is shown to be connected to a field in probability theory called percolation theory that studies the conditions under which liquid (e.g water) poured on a porous material (e.g. ground coffee) can actually flow. Diving into this, however, is beyond the scope of this article (though I plan to write about it in this very publication soon).
In summary, pervasive decentralized off-grid communications requires coverage via connected mesh networks. The connectivity of a mesh network depends on the number of nodes deployed and the device range — which in turn depend on the RF technology used. Analyzing the various options, it turns out that range has a non-linear and outsized impact on connectivity. WiFi-direct and, to a lesser extent LTE-direct are insufficient to provide cost-effective connectivity. On the other hand, the ranges offered by and goTenna Mesh appear to be necessary and sufficient — in combination with incentivized deployment — to realize the vision of decentralized off-grid communications.
Imagine that we need to provide mesh-based communications in a three-by-three mile area. This could be a disaster zone, a small suburban town seeking alternate communications, a military deployment or a large group of hikers. Assume that mesh connectivity is provided by hopping through both user-owned and“pure relay” devices – we will refer to them collectively also as nodes.
For the network to be useful, the nodes need to be connected. By connected, we mean that every node should be able to communicate with every other node via some number of hops. Connectivity is of paramount importance – if you are isolated, or part of a small cluster cut off from the rest of the network, your mesh device is useless. It is clear that the more nodes you place, the better your chances of connectivity. But what is the minimum number of nodes in the area needed to make the mesh network connected?
For each RF technology and associated range, what is the cost of coverage, i.e., connecting a given area?”
The answer depends on the communication range of the device, which in turn depends upon RF technology. In the last decade or so, WiFi-direct has emerged as the technology of choice for license-free, carrier-free mobile wireless communications. It is not surprising then, that a vast majority of peer-to-peer mesh networking solutions have adopted WiFi or WiFi-direct for inter-device communications. But WiFi is not the only choice — other options include LTE-direct and long-range technologies.
Each technology provides a different tradeoff between range, data rate and cost. This brings up a related question: For each RF technology and associated range, what is the cost of coverage, i.e., connecting a given area? This is especially pertinent in light of blockchain-based protocols that are being proposed to incentivize mesh network participation. Most of these projects explicitly or implicitly base their efforts on a particular technology (WiFi being the most popular). Do their choices make sense in terms of connectivity potential and cost — are their “coins” of any value?
Using graph-theoretic models and simulations, we have analyzed the connectivity of a mesh network as a function of the number of nodes, for WiFi-direct, LTE-direct and goTenna. Here are our findings:
Figure 1 (above) shows the connectivity for WiFi-direct based network with 50 randomly placed nodes in a three-by-three mile area, based on a simulation. We used a range of 200 m for WiFi-direct, which is likely optimistic. The result is disastrous — we mostly get singletons, and a handful of very small clusters with three nodes or fewer.
Figure 2 (above) shows the connectivity for WiFi-direct based network with 500 nodes. Surely this should be enough?! Unfortunately, the improvement is only marginal. We do get clusters of 10-15 nodes, but overall this is not a network you can usefully deploy. And as Figure 3 (below) shows, bringing the number of nodes up to 1,000 nodes doesn’t solve the problem either.
At this point, it’s becoming clear that WiFi range is limited enough to be largely useless. Recently, and possibly because of this limitation of WiFi, LTE-direct has been garnering attention. LTE-direct allows two smartphones with LTE service to connect directly without going through a cell tower.
Figure 4 (a)-(c) (below) shows the connectivity for LTE-direct based network with 50, 250 and 500 nodes respectively. At 50 nodes the situation is not much better than WiFi, and even with 250 nodes the network remains disconnected! Even when we see connectivity at 500 nodes, a few are dangerously close to being isolated. Further, the “diameter” of this network is 13, meaning that some messages may have to go as many as 13 hops before they reach their destination. At $500 each, the cost of 500 smartphones to cover a three-by-three mile area would be about $250,000.
goTenna Mesh’s range is three times greater than that of an LTE-direct device, yet it reduces the number of nodes required to achieve robust connectivity by a factor of 20!”
WiFi-direct and LTE-direct use the same “hardware” — the smartphone — for both the mesh router and the application platform. An alternate design, pioneered by goTenna, is to decouple the two functions. In the goTenna system, the smartphone pairs with a dedicated small, light, low-power, low-cost device that forms a mesh network with other such devices. The goTenna device has a range measured in miles, depending upon terrain. Using the most conservative estimate of 1 mile range, how many nodes would be required to cover a three-by-three mile area?
Figure 5 (below) shows the connectivity for a goTenna network (using range of one mile) using just 25 nodes. Not only is the network connected, but the connectivity is robust — every node can reach every other node via at least two disjoint paths! Further, the diameter of the network in the figure is only four hops.
Table 1 (below) summarizes the above information, along with a cost estimate for covering the three-by-three mile area with each technology at $500 per smartphone, and $80 per goTenna Mesh device. For the goTenna numbers, we assume that each node consists of a goTenna device plus a smartphone (although goTenna Mesh can operate as an unpaired relay). The WiFi numbers assume that equipment is newly provisioned, whereas in reality users may already have smartphones with WiFi-direct, and to a lesser extent, LTE-direct. On the other hand, population distribution tends to be highly clustered rather than uniformly random, and therefore not conducive to connectivity without additional relays. Thus, the table represents only a high-level, ballpark comparison. Nonetheless, it is clear from the magnitude of the cost difference that long-range, low-cost technologies such as goTenna handily win when it comes to overall cost of coverage.
| Range | Nodes needed for connectivity | Overall equipment cost | |
|---|---|---|---|
| WiFi Direct | 200m | > 1000 | > $500,000 |
| LTE Direct | 500m | ~ 500 | ~ $250,000 |
| goTenna | 1 mile (1600m) | < 25 | < $14,500 |
It is not surprising that a higher range implies fewer nodes for coverage. What is remarkable, however, is the outsized impact of range in terms of nodes and cost. goTenna Mesh’s range is three times greater than that of an LTE-direct device, yet it reduces the number of nodes required to achieve robust connectivity by a factor of 20! WiFi devices, whose range is about 12 percent of goTenna Mesh devices, require 40 times as many nodes to reach connectivity.
But wait, you might say, don’t WiFi and LTE have higher data rates? Indeed, they do. However, when building out a mesh network, connectivity is more important. After all, if you are not connected, what good does a high data rate do?
Analyzing the various options, it turns out that range has a non-linear and outsized impact on connectivity.”
Mesh networks suffer from what we call a “zero-start” problem — users need connectivity to participate in a network, but achieving connectivity requires participating users. Only with ranges on the order of goTenna devices can one hope to solve the zero-start problem. Once we “bootstrap” connectivity, organic growth of the network may well provide enough nodes to reduce range and increase bit rate.
Connectivity, and its relationship to node-density, has been and is a topic of much theoretical research in academia. An interesting aspect that has emerged is that as you increase range (or number of nodes), connectivity happens suddenly. Just below a critical threshold of range, for instance, the network is still heavily fragmented. But with just a small increase, it is connected!
Amazingly, this phenomenon is shown to be connected to a field in probability theory called percolation theory that studies the conditions under which liquid (e.g water) poured on a porous material (e.g. ground coffee) can actually flow. Diving into this, however, is beyond the scope of this article (though I plan to write about it in this very publication soon).
In summary, pervasive decentralized off-grid communications requires coverage via connected mesh networks. The connectivity of a mesh network depends on the number of nodes deployed and the device range — which in turn depend on the RF technology used. Analyzing the various options, it turns out that range has a non-linear and outsized impact on connectivity. WiFi-direct and, to a lesser extent LTE-direct are insufficient to provide cost-effective connectivity. On the other hand, the ranges offered goTenna Mesh appear to be necessary and sufficient — in combination with incentivized deployment — to realize the vision of decentralized off-grid communications.
Visualization: Nodes & Range
The overall connectivity of a network depends on the how many nodes are in it, and what each node’s range is. To achieve full connectivity with wifi devices — which have a range of about 200 meters (0.12 miles) — requires a network with many nodes. This can get expensive! On the other hand, a network of goTenna devices, whose range can be one mile or more, can be fully connected despite having far fewer nodes.
This interactive tool helps you visualize the relationship between node density, range and connectivity. The dots below represent individual nodes in a 3×3 mile area. Whenever two nodes are within range of one another, a line forms to indicate a potential connection. Use the sliders to add or remove nodes from the network and adjust their range. Which one makes a healthier network?
Visualization by Jarvis Johnson for In The Mesh.
Comments