1 Introduction

The first electronic computers to ever be built were very expensive, very large, consumed large amounts of power, and were thus only accessible to a very small minority of people. However as time progressed, computers became cheaper, smaller, and faster and thus became increasingly common among electronic hobbyists. What has however lagged behind this progress, is the proliferation of communication systems deployed by electronic hobbyists. Indeed, it requires much more collaboration between people when building a communication network compared to that required for electronic hobbyists to build their own computers. There are also technical barriers to the proliferation of P2P based communication systems. The TCP/IP Internet suite was designed with the mindset that, all computer networks could be trusted to be safe from hackers, would provide end-to-end connectivity, and would transmit and receive packets at a relatively low latency. The insecurity of the plaintext TCP/IP stack is well known and protocols such as TLS, SSH, and VPNs have been created to address these issues. There has been, however, little progress made on addressing the issues of a lack of end-to-end connectivity and high packet transmission latencies in ad-hoc computer networks. While the security issues affecting ad-hoc P2P networks have been mitigated to an acceptable level, general purpose ad-hoc networking on a large scale has failed to enter the mainstream due to the unaddressed issues of intermittent connectivity and high latency. Ad-hoc networking has however enjoyed more success for more specific applications, which are more tolerant to latency and intermittent connectivity [1]. Fortunately, many of today’s communication applications are delay tolerant. Email, text messaging, and photo messaging are popular methods of delay tolerant communication. As a result of the ever-decreasing cost of computer hardware, the proliferation of free and open-source software (FOSS) and the variety of delay tolerant communication mediums in use today, it is reasonable to believe that with the correct networking protocols, ad-hoc mesh networking could enjoy a lot more popularity and thus electronic hobbyists will be able to play an important role in establishing inexpensive and reliable communication systems. Our paper presents a P2P network protocol designed for exchanging text messages between connected users. We will describe how our protocol can be made delay-tolerant and how it can potentially exploit the mobility of users to aid in the process of message routing.

The rest of this paper is organized as follows. Section 2 presents the motivation for this work. The related work is discussed in Section 3. The proposed solution is introduced in Section 4. The prototype implementation is presented in Section 5, with evaluation results discussed in Section 6. Section 7 concludes the paper and presents ideas for future work.

2 Motivation

There are several limitations of existing solutions, including reliability, privacy, and cost.

2.1 Reliability

Centralized services have the problem of having a single, or very few, points of failure. When the cellular network goes down, nobody can communicate. Often times, this happens when the communication infrastructure is needed the most, such as immediately following a disaster. Designing an alternate network with fault tolerance in mind could allow messages to pass even though part of the network has failed. The network should be designed to be rapidly deployable and self-configuring. In the wake of a disaster, nodes simply need to be connected to a power source, such as a battery, and be in-range of at least one other network node in order to communicate. Nodes are small and many can be placed in a backpack during the deployment process.

2.2 Confidentiality and integrity of messages

All end-nodes (devices which interact directly with users such as mobile phones, tablets, and laptops) on our mesh network are identified by a cryptographic identifier, their public key fingerprint. This serves two purposes – to verify that the data really did originate from said node and was not tampered with in transit, as well as to encrypt messages being sent to a node so that they cannot be read by anyone other than the desired recipient. Unlike traditional cellphone infrastructure, encryption keys are only known to the users and not the network administrators. Although many cryptosystems, such as PGP, can be used over any kind of network, including a traditional cellular network, many find them difficult to use. The clients for this network make secure communication, specifically public key exchange very user-friendly; in our prototype to add a buddy the user simply clicks on their buddy’s name in the list of people on the network and verifies that their PGP fingerprint is identical to the one which they exchanged in real life. As discussed later in the paper, our goal is to add support for other, more modern encryption schemes such as Signal to be used instead of PGP.

2.3 Cost

Although there are many free IM Apps and web services, these all rely on an Internet connection. Our application however, must work whenever there is no Internet connection. In many places this is not a concern as cellular phone service is available. Although deploying a cellular network is expensive, the per-user cost is affordable to many because a large amount of people also use the service. There are however, many places where it would not be profitable to build a commercial cellular phone network and thus there is no connectivity at those places. This mesh-network, however, can be built with inexpensive off-the-shelf hardware, by many people without the need for a telecommunications company to invest a large amount of money into a network that would not be profitable to them.

2.4 Protocol extensibility

Finally, our protocol should be designed so that it can be adapted to a wide variety of future use cases. Today’s mobile applications which allow “offline chat” often do not work with different “offline chat” applications and are designed only for Android and iOS devices communicating with each other over Bluetooth or Wi-Fi Direct. Our solution is designed so that it can be made to work on a wide variety of hardware including inexpensive hardware with wireless capabilities such as the Raspberry Pi or the ESP8266 Wi-Fi microcontroller. It is our goal, that users of our protocol are able to build upon it thus creating new applications that enhance the functionality of a mesh network. For example, future users may use our protocol for creating nodes which can backhaul long distance traffic across overlay networks such as the Internet. Another future use case could be a social network of users collaborating to route messages between isolated mesh network partitions.

3 Related work

While many mesh networking projects exist, mainstream general-purpose mesh networking is not yet a reality. While commonly used networking protocols such as the TCP/IP stack run well over high-speed and always connected cables and switches, these same protocols often suffer greatly when subjected to the latency, interference, and intermittency of wireless ad-hoc communications. More specific applications of wireless ad-hoc networks have been successful such as using vehicular ad-hoc networks (VANETS) for communication of warning about the road and traffic conditions [1]. These types of applications do not require an end-to-end connected and low latency connection and therefore are not subject to many of the problems of ad-hoc wireless networks which have kept general-purpose mesh networks from entering the mainstream.

CJDNS is a project which attempts to bring mesh networking to the mainstream by allowing for the protocol to scale to a large network. Instead of each node knowing about every other node on the network, each CJDNS node is only responsible for knowing about, and being able to connect to, nodes which are physically close as well as nodes which are close by in address space [2]. If each node has this information, then packets can be sent from one part of the network to another without each node storing a copy of the entire routing table. This allows CJDNS to scale.

A simpler project that has been popular among Wi-Fi enthusiasts is B.A.T.M.A.N (Better Approach to Mobile Ad-Hoc Networking). This is already available in Linux through the batman-adv kernel module. This provides the operating system with a virtual interface which can transmit and receive link layer packets from any node on the mesh network. The network becomes aware of nodes when each node periodically sends out a broadcast message which is relayed to all nodes on the network. Every node on the network is aware of every other node on the network but they do not know the complete route to every other node [3]. While this does allow for some scalability, it removes the possibility for an end user to pick the best route to a destination node based on their own statistical routing performance information, for example routing around a malicious node (See 4.6 Security). Reliability in a small network is more important than scalability therefore our network will use source routing.

While the above-mentioned projects are suitable for transmitting lower level network packets over a relatively low-latency, end-to-end connected mesh network, they do not inherently allow users to exchange text messages. Tox is a project which aims to allow users to send encrypted messages as well as participate in encrypted calls and video chats over an Internet Protocol (IP) based network without needing a centralized server [4]. Due to the lack of need for a centralized server, Tox can be deployed on a network isolated from the Internet, such as a small B.A.T.M.A.N or CJDNS network.

FireChat is mobile app for Android and iOS that has gained popularity due to its ability to “chat offline”. FireChat creates a network of everybody in a wireless mesh allowing users to communicate without needing an Internet connection or a mobile data plan. This app has the ability to chat in public chat rooms, private chat rooms, or private one-to-one chats. It has also mesh functionality for communicating with users beyond the local vicinity [5]. FireChat’s protocol is proprietary.

Looking at all these existing solutions, summarized in the table below (Table 1), we have come to the conclusion that our mesh network must be able to send and receive encrypted and signed messages, use source routing and provide a complete solution for text based communication. Scalability is not the first priority as the mesh network is primarily intended for small, isolated, ad-hoc networks. The network should, however, be easily deployable and the software should be intuitive to unfamiliar users. Due to the fact that application-specific mesh networks have been historically more successful than general-purpose mesh networks [1], we will only use TCP/IP for data transmission between neighbouring nodes and all other data transmission will be done with our own mesh network protocol. With these goals in mind we present our solution.

Table 1 Pros and cons of related projects
Full size table

4 Proposed solution

Given the problems related to general purpose, layered network stack, mesh networking [1], it is justified to deviate from the traditional layered network stack model, with the lower layers running the more general purpose services to a model where the layers are more blurred together [6]. For example, when communicating over a TCP stream the application does not determine how the packets will be routed. In the context of a mobile ad-hoc network where nodes are not always reliable it could be advantageous for a user to pick the path (or at least part of the path) through which the message will be routed through. For example, the end user who knows the operators of the nodes along the message transmission path will choose routing nodes which are known to be stable. In addition, if there is not a direct path between two users, the sending user can exploit the knowledge of the social network to send the message to a user who will likely be able to forward the message to the intended recipient. This is similar to the idea of predictive prefetching [7] where content is fetched before it is needed because it is known to likely be needed in the near future and there is a reliable connection now which may not exist when the data is needed.

While the projects described in the Related Work section, with the exception of FireChat, require a low latency, end-to-end network connection, our protocol is designed to be adaptable for unreliable ad-hoc networks. Unlike FireChat, our protocol is designed with extensibility in mind so that users of it may find new applications of it which improve the mesh network. Therefore, due to the lack of an open source solution for communication through unreliable ad-hoc networks designed for a wide variety of inexpensive hardware with end-user extensibility in mind, we feel justified in proposing our own solution.

4.1 Assumptions

Throughout the whole life cycle of the network, it can be assumed that there is no accessible communications infrastructure other than the mesh-network itself. This makes the network suitable for deployment in developing countries or in areas stricken by disaster. In order to ensure security of communication, it is necessary to exchange public key fingerprints. Therefore, it is ideal that all parties on the network who wish to communicate are able to meet in person, or through a trusted common friend, are able to exchange an alpha-numeric string representing their public key fingerprint, similar to what is done in the Signal Messaging App with Safety Numbers [8]. For those who are not able to meet in person, a probabilistic estimate of the trustworthiness of the authenticity of a key can be established using a web-of-trust [9].

4.2 Protocol architecture

The network will consist of three types of nodes; repeater nodes, gateway nodes and end nodes (Fig. 1). Repeater nodes are headless and simply extend the mesh-network to places where the wireless signal could not otherwise reach. Gateway nodes can also act as repeater nodes however, they do another important task – they allow any Wi-Fi capable device to connect to the mesh-network. This is what allows a device such as a smartphone which can only connect to an infrastructure mode Wi-Fi network to send and receive messages on the network. These types of nodes are typically low cost microcomputers such as the Raspberry Pi. The third type of node on this network is the end node, which is the device that the end user is using. Although this device could connect ad-hoc mode and forward packets, the primary use of this node is user interaction. These nodes are typically smartphones, tablets or laptops. The program executed on these devices is simply an HTML webpage and the protocol is handled in JavaScript. All nodes on the network identify themselves by their Node ID which is static and should be a cryptographic fingerprint which can be used to prove the identity of the node. IP addresses are only used for communication between neighbors (analogous to MAC addresses in Ethernet) and therefore only neighbors need to be concerned about IP address changes or conflicts.

Fig. 1
figure 1

A network consisting of 1 repeater node, 2 gateway nodes and 2 end nodes. This allows the laptop to communicate with the smartphone

Full size image

4.3 Protocol data types

Our protocol is based on JSON encoded packets. We define seven packet types; text-message, net-advertise, get-neighbours, multi-hop, neighbour-list, pgp-keyblock, and key-request. Packets are recognized by any program handling them by reading the “type” field in the JSON object.

A text-message packet carries an encrypted text message in its “payload” field from a source, “src” to a destination, “dst”.

A net-advertise packet signals a node’s presence to its neighbours. It tells a neighbour that the node “src” can be reached at the IP address of the connecting peer.

A get-neighbours packet is used to ask a node for its list of neighbours. This means that node “src” wants to see who are the neighbours of node “dst”. The node being queried then replies with a neighbour-list packet containing the neighbour list in its “payload” and sends it to destination “dst” from its own source address, “src”.

Packets can also be routed with a route that was statically defined at their origin. The packet to be routed is placed inside the “payload” of a multi-hop packet, the “src” and “dst” fields of the inner packet are respectively copied to the “src” and “dst” fields of the multi-hop packet. The “routing_path” field of the multi-hop packet is then set to a list containing the nodes which the packet must pass through with the first element being the destination node ID and the last element being the source node ID.

The last two types of packets are only understood by end nodes and they are pgp-keyblock and key-request. When a node transmits a key-request packet from itself, “src”, to a destination, “dst”, the node receiving this packet replies with a pgp-keyblock packet carrying the public key for the queried node in its “payload”. The name pgp-keyblock was chosen as our prototype used an implementation of PGP for ensuring the authenticity, integrity, and confidentiality of messages on the network. The use of PGP, however, is not a requirement for our protocol and future implementations are planned to support the more modern Signal protocol.

Our mesh-network’s types of packets and their roles are summarized in Table 2.

Table 2 Specification of the protocol – key-request is not specified as it is very simple
Full size table

4.4 Protocol transport

All three types of nodes send and receive the same types of JSON encoded packets. This is because all three types of nodes do some similar activities such as lookup neighbors. These packets are transmitted from repeater-to-repeater, and from repeater-to-gateway via TCP socket. Transmission from gateway to end node is done via WebSocket. The reason why all packets are routed at application-level is two-fold. The first reason is that end-nodes have their Node ID which corresponds to a user’s identity on the network (like an email address) and not the identity of the device (like an IP address). The second reason is so that gateway and repeater nodes can simply run a server application which leverages the existing TCP/IP stack. For example, TCP/IP can already be sent over Wi-Fi, Ethernet, VPN, or PPP/SLIP (serial) to name a few. Therefore writing a server with a TCP/IP interface means that this mesh network will work automatically over any of the previously mentioned transports. The operating system’s TCP/IP stack also handles lower level details such as maximum IP packet size and error correction which greatly simplifies our work for moving our mesh-network’s packets between neighbors.

4.5 Protocol operation

The operation of our protocol is recursive in nature in that from the perspective of a given end user, that given end node can be represented as a root node of a tree. The recursive algorithm then begins by finding the immediate neighbors for the end node, then their immediate neighbors, then the immediate neighbors of those neighbors, and so forth building a higher level of the tree each time. Therefore, the number of get-neighbors requests sent by an end node is equal to the number of nodes which our end node knows about minus the number of nodes at the highest level of its map. During this network discovery process, the end node also requests the public key for each discovered node. This is so that the end node may verify the identity of other nodes and be able to ensure the confidentiality, authenticity, and integrity of messages exchanged with them.

In realistic mesh networks, following this process would almost certainly result in loops in the generated network graph thus disqualifying the graph from being a tree structure. The simplest approach to keeping the graph as a tree structure is to disregard any information about a given node being a neighbor of another node if the given node is already on the graph and thus already has a parent (neighbor) node. With the network graph kept as a tree structure, finding the path to any node on the network simply requires recursively finding parents of parents for the destination node until the algorithm has reached the root node.

The above described approach of simply disregarding parent neighbor information of nodes already on the graph, is not a robust approach as it will omit redundant routes thus resulting is a less reliable mesh network. Therefore, for more reliable network connectivity, the end node should build a complete map of all known neighbor connections and assign an equal weight to each edge in the graph. To then transform this map into a tree structure where it can be used for finding routes, the end node should employ Dijkstra’s algorithm. In many realistic mesh networks, there will be multiple shortest paths to a given destination end node. The end node should use all the different paths for different messages and the path which statistically has the best performance should be assigned the lowest weight. In future work, the end node may share this routing information with their trusted contacts so that the best routes through the mesh network may be discovered and the probability of denial of service attacks such as the Black Hole attack will be lowered.

When any node (gateway, repeater, end) is connected to neighbors on a mesh network it periodically sends out network-advertise messages. This is to alert neighbors of this node’s presence so that when they are queried with a get-neighbors request, they will reply with this node in its neighbor list thus placing the node on the mesh network map.

The operation of the protocol can be expressed using the following pseudocode algorithm, followed by a walkthrough of an example network setup showing details of the operations.

figure c
  1. 1.

    Neighboring nodes must have already established some form of TCP/IP communication. The most common case is that neighboring nodes are connected to the same ad-hoc Wi-Fi network and have discovered each other over some form of UDP broadcast messaging. Alternatively, a network between two or more neighboring nodes may be setup manually.

  2. 2.

    Each node must now advertise itself to its neighbors. To do so each node sends a net-advertise packet to all neighbors. After this, all nodes on the network will know the Node IDs of their neighbors and a local IP address that they will use to communicate with them (Fig. 2).

  3. 3.

    The end nodes may now map the network and attempt to discover other users on the network which they wish to communicate with. Each end node asks the gateway node which it is directly connected to for its list of neighbors by sending a get-neighbours packet to it and waiting for a reply. Once the reply arrives, the end node finds neighbors of neighbors by sending a get-neighbours packet wrapped in a multi-hop packet to each neighbor of neighbor until the end node has mapped out as much of the network as they would like (Fig. 3).

  4. 4.

    Throughout the network mapping process, the end node tries to download the public key for each node and verify it against the node ID which is supposed to be the public key fingerprint. The name associated with the public key is displayed under a list of network nodes. This is so that when a user adds a chat contact, they may verify that the public key fingerprint matches the one that they exchanged face-to-face or through a web-of-trust.

  5. 5.

    To send a message from one end node to another end node, the sending node searches through its list of known nodes for the recipient. The sending node then follows our recursive algorithm finding parent nodes of parent nodes for the recipient and a multi-hop path is built from source to destination. This multi-hop path is used as the “routing_path” for a multi-hop packet which will carry a text-message packet carrying the encrypted message data the user wishes to send. This encrypted data is the plaintext message signed with the sender’s private key and encrypted with the recipient’s public key. Once the multi-hop packet arrives at the destination end node, after following its predefined route, the text-message packet is extracted and is decrypted with the recipient’s private key and verified with the sender’s public key. If the message is successfully verified, the message is displayed on the end node.

Fig. 2
figure 2

Pi_1 joins the network and sends a net-advertise packet to its neighbors asking to join the network

Full size image
Fig. 3
figure 3

Pi_1 begins mapping the network. Get-neighbours packet is sent to Pi_5 (1) and neighbour-list is returned (2). A multi-hop packet is used to send a get-neighbours packet to Pi_8 (3,4,5). The returned neighbour-list packet is sent back to Pi_1 via multi-hop packet (6,7,8)

Full size image

4.6 Security

Security is a major priority for the mesh network. To ensure that messages are read by nobody except the intended recipient they are encrypted with the recipient’s public key. Messages are also signed with the sender’s private key to ensure that the message actually originated from the sender and not somebody impersonating the sender. This encryption works end-to-end so that even if a node in the network was deployed by someone malicious, they could not read the messages. Lastly, in order for the communication between two users to be secure, the public keys must be exchanged without any tampering or spoofing. In this setup, the public keys may be verified to be legitimate by face-to-face verification of the fingerprint with the owner of the key. To facilitate this, the users may verify the alpha-numeric string representation for the key fingerprint or use a QR code representation of the key fingerprint. If users are unable to meet face-to-face, existing methods for a PGP web-of-trust may be used for obtaining a probabilistic estimate of a key’s legitimacy. Thus, our infrastructure is able to provide the following cryptographic guarantees; user authentication, message authentication and integrity, and message confidentiality.

Although PGP, the cryptographic scheme used in the prototype of our protocol, is considered by some to be an outdated standard, it is still heavily used for many tasks which require integrity, authenticity, and confidentiality. Software packages for Linux distributions such as Debian and Ubuntu use PGP for signing packages to prove that they are legitimate thus preventing man-in-the-middle (MITM) malware attacks. Git supports the use of PGP for signing commits to a software repository thus proving that a change to the codebase can only have come from an authorized developer. Large databases of PGP keys, such as Keybase.io, are available which can be leveraged for ensuring the security of the communication between users on our mesh network.

PGP however does lack modern encryption features such as perfect forward secrecy, where past communications cannot be decrypted even if a user’s master encryption keys are compromised. For reasons such as this, if users on the mesh network wish to use a different type of encryption system, future work will include the support of alternate encryption schemes such as the popular Signal protocol.

For the network to be secure, it must also be resistant to malicious users who aim to disrupt network activity by causing a Denial of Service (DoS) attack. A common type of DoS attack in an ad-hoc network is a black hole attack. This is when a routing node intentionally drops packets which it claims that it can relay. For example, a repeater node could lie to a get-neighbours request so that an end-node believes that this repeater node is connected to another node, which in reality it is not. To mitigate this attack, gateway nodes and repeater nodes must reply to get-neighbours requests with a cryptographically signed proof that both parties are indeed neighbors. This however does not prevent the possibility of a node dropping packets which are supposed to be relayed to a legitimate neighbor. If this happens, the end-node wishing to send a message must use its map to find a different route to the recipient node. Each end-node should keep track of working routes and broken routes, and share them with their trusted buddies list. This way, a web-of-trust can be built which will favor routing packets over nodes known to be good and avoid nodes which are known to be malicious.

4.7 End node mobility

Because many of the end nodes are mobile (phones, tablets, laptops) the gateway node which they connect to may change quite often. Because each end-node stores a map of its view of the network, the end-node simply needs to find the gateway node which it is now connected to and calculate a route from that node to the end-node which it wishes to send a text message to. This means that an end-node can move to another nearby gateway node without remapping the entire network. Because IP addresses are only used to communicate between neighbors, a mobile end-node need not worry about being assigned a new IP address by the DHCP server of its new gateway node as all other nodes on the network identify this end-node by its node ID (public key fingerprint) and not its IP address. As soon as an end-node switches to a different gateway node it should notify every end-node in its buddy’s list so that they may update their maps and be able to send a text message to the user who has just switched gateway nodes. Should two mobile end-users switch gateway nodes at the same time (or effectively at the same time because of propagation delays) the notification of gateway change will fail and both end-node’s maps will not be updated. If either one of these nodes tries to send a text message, it will fail. To resolve this situation, the sending end-node must remap part of the network. Starting at the nearest gateway of the recipient end-node’s previous gateway and moving out to further away gateways, the sending node asks for its neighbours while always updating its map. If it finds the recipient end-node then the text-message may be sent. If it does not find the recipient end-node, then the recipient end-node (if not offline) has switched to a gateway which does not appear on the map of the sending node. The sending node must then expand its map of the network until it finds the recipient end-node.

4.8 Opportunistic communications

As previously mentioned, one of the advantages of breaking away from the stacked network layer model is that applications can be created which communicate with each other even if only a high latency, intermittent channel is available. This implies that in future works, opportunistic routing may be implemented for routing messages between users on separate isolated networks. This could be implemented as follows.

Network maps of other disconnected networks can be shared with a given end node. If this end node then wishes to send a message to an end node on the disconnected network it only needs to be able to inject this message, carried by a multi-hop packet, to any node on the recipient’s network. This is an advantage as a node which frequently moves between the two isolated network partitions may be asked to route messages, thus exploiting mobility for opportunistic communications. Mobile end nodes which move between various isolated network partitions may, if enabled, carry messages between the isolated gateway nodes indicating which gateway nodes are likely to come into indirect contact with other isolated gateway nodes via mobile end nodes which have chosen to assist in opportunistic routing. Users then wishing to send a message to a user on an isolated network partition may then use the probabilistic data stored on the gateway nodes to find the best effort path for opportunistically routing the message [10].

The research contribution of our work is that we have described and created a proof-of-concept demonstrating the possibility of a decentralized rapidly deployable mesh network for text based communication between users. We have shown that it is possible to build this functionality into an extensible protocol which will support future goals such as opportunistic routing of messages for connecting otherwise disconnected mesh networks.

To summarize, in terms of work already accomplished, this paper has the following research contributions as these areas of work, to the best of our knowledge, have not been investigated in the related work:

  • Development of an application specific protocol for text messaging over a wide variety of physical transports (not just Wi-Fi Direct and Bluetooth)

  • Development of an application specific protocol for text messaging designed for a mesh network of inexpensive devices, particularly the Raspberry Pi.

  • Development of an application specific protocol for text messaging which inherently supports user authentication, message authentication, and message confidentiality (FireChat lacks user authentication, Tox relies on general purpose underlying TCP/IP network).

In terms of future work goals, future research contributions will be:

  • Use of social network knowledge for delay tolerant forwarding of messages.

  • Use of social network knowledge for improving scalability of mesh networks.

  • Use of trusted messaging contacts for building a web-of-trust to discover reliable routes through a mesh network.

5 Prototype

The purpose of our prototype is to demonstrate that our protocol is a viable option for text based communication, on an ad-hoc rapidly deployable network of inexpensive hardware. Our prototype is not yet a complete solution, but instead provides insight into the feasibility of our protocol by working in common situations. In future works, more features such as efficient hand-off methods for mobile end-nodes and opportunistic routing for messages across disconnected mesh networks will be implemented and tested.

The programs for the end nodes were written in HTML5 with JavaScript and CSS. The desktop version used a modification of the Windows7 Start Menu by Taufik Nurrohman (http://cssdeck.com/labs/pure-css3-windows-7-start-menu) to create the user interface (Fig. 4) while the mobile interface was written completely from the ground up (Fig. 5). Both versions used sigma.js (http://sigmajs.org/) for graphing the network as well as alertify.js (http://fabien-d.github.io/alertify.js/) to provide aesthetically pleasing standard dialogs. Cryptographic operations are handled via the OpenPGP.js (http://openpgpjs.org/) library. Data is encrypted end-to-end so that the network need not be trusted. This decision was made to put the end user in charge of their privacy and security. Even though the end user, and not a network administrator, is in charge of their own privacy and security, efforts were made to make the cryptographic layer understandable to everyday users. To generate a PGP keypair the user simply needs to click on “Generate Identity” and they are given their key fingerprint in both text and QR code form. When adding a buddy, it is recommended that both parties verify PGP fingerprints in order to ensure secure communication. This can be done with either the text form or the QR code form of the PGP key fingerprint. The localStorage API was used to store PGP keys even after the browser is closed. These open web standards facilitate the deployment of this program onto a wide variety of platforms. The program for the repeater and gateway nodes was written in Java. Data packets, on all nodes, are JSON encoded objects which are handled natively in browser-based JavaScript on the end nodes. On the gateway and repeater nodes, the Java based server handles the packets using the json-simple library (https://code.google.com/p/json-simple/). Data is moved between the gateway and end nodes by translating between TCP sockets and WebSockets using the websockify (https://github.com/kanaka/websockify) program. This can be done due to the fact that it is the same type of object encoding (JSON) running on both programs. The startup script, along with the script which periodically broadcasts the node’s IP address for auto discovery, are written in BASH (UDP broadcasts are done with Socat). All repeater and gateway nodes were Raspberry Pi Model B’s running Raspbian Linux. The end nodes were HP Compaq tc4400 laptops, with one running Mozilla Firefox 30.0 and the other running Google Chromium 35.0. In both cases, the Raspberry Pis were connected to the laptops via Ethernet cable. The network was also tested with a Samsung Galaxy S (GT-I9100) running Google Chrome for Android. The phone was connected to the mesh-network by using a D-Link All-in-one Mobile Companion to connect the phone’s Wi-Fi to a gateway node.

Fig. 4
figure 4

The client running on a desktop browser. The right pane displaying users on the network

Full size image
Fig. 5
figure 5

The client is running on an Android mobile phone and a conversation is taking place with a user called “DesktopChrome”

Full size image

6 Evaluation and results

All our tests simply demonstrate our protocol’s performance without comparing it to the related work. The only program from the related work which could be comparable to our protocol, and thus would have a meaningful performance comparison is FireChat. The only area in which our protocol can be compared to FireChat is in terms of usability. Both our application and FireChat provide end users with graphical user interfaces (GUIs) allowing the network to be used by non-technical users. However, unlike FireChat, our user interface provides a map of the local mesh network. This information could be instrumental for network resilience purposes such as routing around a malicious node in a black hole attack (see 4.6 Security). Finally, unlike FireChat, our infrastructure allows communicating parties to verify public key fingerprints thus preventing man-in-the-middle (MITM) attacks from reading private messages. Despite these differences, FireChat still has goals similar to ours for enabling ad-hoc mesh networking. However due to the proprietary nature of FireChat, we were not able to test it on Raspberry Pi microcomputers and laptops as is the intended deployment target for our protocol. Therefore, we will only explain how our protocol performed during our tests, objectively.

The first test was performed on actual Raspberry Pi hardware, as is the target deployment platform, while the following three tests were performed on Docker containers, as it provides a simpler way for conducting a network protocol simulation, compared to physically deploying 36 Raspberry Pi mesh network nodes. During our simulations, our goal was to test not only the model of our protocol but the actual implementation as well. Network simulators such as CORE employ Linux containers (LXC) for simulating individual network nodes for the purpose of testing network software implementations [11], therefore using Docker, which builds upon the lower level LXC framework [12], provided a sound means for simulating our mesh network and greatly facilitated the process of container image building. The final test simulates the feasibility of the future work of opportunistic routing based on a Markov model of mobile users.

The first three tests begin with each end node having an empty network map. Both end users click on “Login”, or if they have not done so already, they first click on “Generate Identity”. After this, they click on “Network Tasks” then “Discover Nodes”. Each time they click on “Discover Nodes” a new level of the network is mapped. The end users continue doing this until the person who they wish to talk with appears in the “Add Buddy” list. Once this happens, each end user adds the other by clicking on “Add Buddy” and then their name. The end users then verify that the PGP fingerprint displayed matches the one which they previously exchanged. If it does, the users click “OK” and the person now appears in the “Chat” list. The user wishing to send a message now clicks on their buddy’s name from the “Chat” menu and a new chat session is started. The user types the message and clicks on the send button. The buddy’s reply will be displayed in red text in the chat window (Fig. 6).

Fig. 6
figure 6

An active conversation with a user named “Michael” using the client in a desktop browser

Full size image

6.1 Test 1

The first test consisted of deploying five Raspberry Pis throughout two connected buildings (Fig. 8). Two Raspberry Pis served as gateway nodes with one connected via Ethernet to a HP Compaq tc4400 running the desktop interface in Mozilla Firefox 30.0 while the other gateway node was connected to a D-Link All-in-one Mobile Companion which allowed a Samsung Galaxy S (GT-I9100) to run the mobile interface in Google Chrome for Android. The other three Raspberry Pis served as repeater nodes which extended the mesh across the building (Fig. 7). The test case was successful as it allowed messages to be sent between two connected buildings on our campus (Fig. 8).

Fig. 7
figure 7

Map of the network during the first test. This network contains 3 repeater nodes

Full size image
Fig. 8
figure 8

Map of the physical location of the nodes during the first test

Full size image

6.2 Test 2

The second test was conducted on network of 36 Docker containers interconnected in a 6 by 6 square fashion (Fig. 9). The web interfaces to gateway nodes 1 and 36 were exposed to localhost (on different ports) and the Firefox web browser was used to interact with the desktop web interface. The end result was that messages could successfully be sent from the 1st node to the 36th node.

Fig. 9
figure 9

View of the network from the web interface for a 6 × 6 square network

Full size image

6.3 Test 3

The third test was conducted on network of 36 Docker containers interconnected in a 36 by 1 linear fashion (Fig. 10). The web interfaces to gateway nodes 1 and 36 were exposed to localhost (on different ports) and the Firefox web browser was used to interact with the desktop web interface. The end result was that messages could successfully be sent from the 1st node to the 36th node.

Fig. 10
figure 10

View of the network from the web interface for a 1 × 36 linear network

Full size image

6.4 Test 4

The fourth test examined the scalability of the protocol. 100 messages were sent from each node to all other nodes in the network in a random order. The test was conducted on networks of Docker containers of sizes 2 × 2, 3 × 3, 4 × 4, 5 × 5, and 6 × 6. The test measured the time required for every node to receive at least one message from every other node on the network thus measuring the performance metric of time required to propagate at least one message from all nodes on the network to all other nodes on the network. We refer to this performance metric as “Message Penetration Time”. This performance figure gives an idea of how reliably and how quickly users from all parts of the network will be able to communicate with users on all parts of the network. Thus, a flatter curve implies better network scalability. In order to make the results of our simulation similar to those of an actual test in a wireless network, our testing configuration uses the iptables TEE routing chain for simulating interference from nearby transmitters as well as the Linux kernel’s tc traffic controller utility for limiting bandwidth between nodes to 1mbps and simulating a packet loss rate of 3%. The code for our wireless network simulation can be found on GitHub [13]. The result from our test shows that the network scales well up to 5 × 5 nodes and then performance significantly decreases at 6 × 6 nodes (Fig. 11).

Fig. 11
figure 11

Results of test 4

Full size image

6.5 Test 5

Although not yet integrated with the main program, opportunistic routing was simulated based on a Markov model of moving mobile users. Our model had 100 mobile users and 10 static nodes. Each mobile user moved probabilistically from static node to static node based on their randomly generated Markov model which describes the probability of transition from one static node to another static node at the beginning of any given timeframe. Our simulation ran for 5000 timeframes and gave the following results. The probability distribution of message delay for any given message was, approximately, normally distributed with the bulk of messages being received within 400 timeframes. The probability of successful message transmission (referred to as Opportunistic Network Discovery) increased sharply during the first 1000 timeframes and flattened out to, approximately, 75%. The results are represented graphically in Fig. 12. The code for this simulation can be found on GitHub [14].

Fig. 12
figure 12

Results of test 5

Full size image

It can be seen from the fourth test that scalability is a limiting factor for our network. While scalability is not the primary goal, improving it will result in more use cases for our network protocol and thus more adopters and therefore electronic hobbyists will play a larger role in building communication systems. In order to make the network more scalable, for future work, each node must not map the entire network. Instead, each node will only develop a detailed map of its local network neighborhood and higher level maps of nodes further away.

7 Conclusion & future work

In this paper, we have introduced a mesh-infrastructure demonstrating the possibility of making mobile devices communicate with rapidly deployable wireless infrastructure. We have developed a working prototype and evaluated it both on real hardware and on simulated networks of virtual hardware. Our evaluation results show the feasibility of a small-scale rapidly deployable wireless mesh network. For future work, we plan to; integrate opportunistic routing into the main program, conduct in-depth security auditing, as well as implement the following features into our prototype; show multiple routes to a node on the web and mobile application maps; give users a choice of encryption/authentication schemes to use including the modern Signal protocol; have each node keep track of data loss statistics; exploit the knowledge of social networks for building reliable routes, aiding in opportunistic routing, and mapping higher levels of the network for better scalability. With these features implemented in the prototype, we will conduct tests and simulations demonstrating the feasibility of the future work.