Skip to main content

Building Stronger Mobile Networks

Current cell phone networks are poorly set up – it is very clear why if we look at the graph theory behind them.  Also using graph theory we can understand how to create a faster, more reliable network, as explained in the CNET article, Unbreakable: Mesh networks are in your smartphone’s future.

Cell phone networks are currently set up so that each phone connects to a nearby cell tower, which is responsible for connections to the many devices in the area.  Thus, to send an SMS between person A and person B, who are sitting next to each other, the SMS must first go from person A to the cell tower, and then from the cell tower to person B (in reality, the message doesn’t get passed directly through the tower, but through the service provider’s own system first, then back out the tower – but this is an effective abstraction in this case).  This network layout does not use any type of triadic closures, as there exists an edge between person A and the tower, person B and the tower, but not between persons A and B. Further, if we extend this notion of our graph to more users, we see many mobile phones connecting to one tower.  If we add more towers, then the graph would be many users all connected to whichever tower is closest, and then the towers connected to some other central location providing the internet connection.  Thus, if one of the towers fails, all users connected to that tower are offline.  This is because each tower in this instance forms a local bridge, connecting the users connected to it with the internet.  The removal of any local bridge divides a graph into two components, in this case one with an internet connection and one without.  Further, as the article points out, if one user has a very good connection, and another nearby user does not, this network structure does not allow any easy sharing of network bandwidth.

The alternative network structure, dubbed a ‘Mesh network’ in the article, replaces the local bridges of the cell towers with multiple triadic closures between all of the users.  This way, nearby mobile phone users can have a direct connection between their phones, and in this way, at least one connection (most likely multiple) should exist between any two users, even if their not directly connected.  In this case, to send an SMS from person A to person B who are sitting next to each other, the SMS goes directly from person A to person B.  If person A wanted to send an SMS to his cousin who was living a few timezones away, the SMS would go from person A to, say, person B, then person C, and so on, until it reached person A’s cousin.  Further, if one user’s internet connection is broken, they can use the connection of the nearby users.  In terms of graphs, remove of one node from this network does not split the network into multiple components, as removing the tower does for the existing network.  Thus a mesh network is much more reliable due to its use of triadic closures between nodes and avoidance of local bridges which may easily fail.

One interesting application of this is in disaster relief, as cell phone service is often interrupted in the event of a hurricane or similar.  This type of network only depends on users still having access to their cell phones.  An Android app called ‘The Serval Mesh’ does exactly this, by connecting phones over local wifi or even directly between devices.


Leave a Reply

Blogging Calendar

September 2015