Developing Challenges of Multi-Hop Mesh Telephony on Android

If you are reading this blog, you probably know that the Serval Project is all about making mesh telephony practical, so that people can communicate anywhere, any time.

For regular Android software development, it is often practical to use the Android emulator to reduce the time between updating source code and seeing the effect of the change.

For Serval, this isn't really an option, because we work below the Android API layer, and much of the software development challenge is related to making the WiFi chipsets do what we want.  We also have a fair amount of native code to do the mesh routing and telephony functions.  In fact, we currently have an entire distribution of Asterisk in the Serval Mesh software, which must be decompressed and installed when the Serval Mesh APK is installed or updated.

Together, these contribute to an update process that can take several minutes to between modifying a line of code and seeing it on an Android device, especially on the low-cost devices that are our primary targets, and when using the debug option in eclipse.

Those minutes add up over time, and so I decided to minimise the install time as much as possible, and also address another problem with developing our software, that is detecting when you have an actual multi-hop network.

To reduce the install time, I started looking at the Asterisk installation to see what we could safely throw out.  I managed to get rid of about half of the loadable modules, several utilities and all of the speech files that Asterisk comes bundled with.  This reduced the size of the APK by a little over 1MB, down to just under 5MB, and cut down the install time by about 15%.  Further savings came from removing unused audio codecs in our SIPDroid-derived SIP client, saving another 0.4MB, and getting the whole thing down to less than 4.5MB and installing about 25% faster than previously.

The bulk of the remaining time is about evenly split between installing Asterisk and testing that the WiFi control works properly.  For development, it probably makes sense to separate out the Asterisk installation from the other files we need to deploy on installation, as we really don't modify the Asterisk files between builds.  This shouldn't be too hard to do, but I have run out of time tonight.

Also, for our target handsets, we really don't need to test the WiFi control every time we update, so we should be able to set a flag to tell the software that we are in development mode, and just assume that the WiFi control works.  This now works by checking if a file called /sdcard/serval/developer-mode/fast-wifi exists, and if so, bypassing those tests, and thus saving about 15 seconds.

So over all the minimum time from hitting "run" in Eclipse to getting the software ready has been reduced from 85 seconds down to 48 seconds (without debugging).

The over significant development convenience task I have worked on in the last few days is one that is probably of more general interest.  The peer list now shows the number of hops to each of the nodes that your phone knows about, as shown in the image below.  This was produced by having two phones at opposite ends of my house, and having the phone shown here with me out on the street.

Each row of the peer list now shows the telephone number, e.g., 5550344, the batman link score, e.g., 243, the ping time to the peer, e.g., 19 milli-seconds, and either "direct" for nodes we can reach directly, or the number of hops to reach the node, e.g., 2 hop.

Importantly for debugging, this displays doesn't ask BATMAN how far to the node in question, but actually enquires of the time-to-live (TTL) field in the IP header, and thus returns the true distance from your phone to the phone in question (the return path might be a different length, though).

Actually, because of limitations with the Java UDP programming interface, the TTL field is read by the Serval DNA daemon (which is written in C), and included in the returned UDP packet to the requesting client.

This means that we can just look at the interface on the screen (and so can all of you who have been asking us for this feature) and see what is happening to routes, instead of having to connect to the phone with a USB cable and enter all sorts of commands to ask BATMAN and the operating system what might be happening.

So all in all we now have a slightly faster and easier development process, that I am sure will more than save the couple of person days of effort that they took to develop, and thus enable us to work faster instead of harder.

Shopping Serval Style

We are currently preparing to provide the latest Serval mesh telephony technology for use in a disaster response training exercise with a major relief agency in late February 2012 -- about two months from now.  In that time we need to not only get our prototype Field Communications Unit (FCU) kit together, but also finish some software development that is key for making the technology useful for the relief agency.  You can watch a demo of one of the features we are working on in the video below, where I send a photo from one phone to another, without infrastructure.  This is the same technology we have used to send an SMS more than 10,000km without infrastructure.

On the hardware side, we have ordered 50 Huawei IDEOS X1 phones for AUD$71.10 each -- pretty cheap for a fully featured Android smart phone, complete with digital compass, GPS, accelerometers, a capacitive screen and enough CPU and RAM to meet our needs. These phones are network locked, but that doesn't worry us as we won't ever be putting a SIM card in them, because they will be used solely as mesh communications devices.

It turns out that buying 50 phones at a time is an interesting exercise.  People want to know that you are not planning to resell them or export them.  Some shops will even try to limit you to buying five or less at a time.  Those tactics are legal in some places, but not here in sunny South Australia, where we have an excellent Fair Trading Act that correctly classifies such terms of trade as discriminatory, or in some cases as tantamount to bait-and-switch.

In fact, until quite recently the South Australian consumer protection and gambling laws were so strong that cereal-packet competitions could not require a South Australian resident to purchase a product to participate in a trade promotion lottery, because it would be considered gambling, i.e., pay for chance to win.  So when I was growing up it was quite common to see terms and conditions looking quite normal, and then have sections specially for South Australians, that would often say something along the lines of:

"10. To enter, cut the bar code from a packet of XYZ and include it in your entry as proof-of-purchase.  Residents of South Australia are permitted to submit a hand drawn facsimile of the proof-of-purchase.

...

17. Only one entry per household per day.  Residents of South Australia may enter more than once per day."

There were certainly occasions in my childhood when we would go to the effort of getting the coloured pencils out to draw a barcode by hand to get the chance to win a prize.  I think we sometimes did it just because we could.  Sadly, with the introduction of poker machines (Australia has fully 21% of the worlds poker or slot machines --- a statistic that is disturbing given that Australia has only about 1% of the developed-world population) and the general liberalisation of gambling in South Australia the situation has changed, and I believe we have lost our little parochialism.

Anyway, I digress.

After the difficulties I encountered initially in sourcing 50 mobile phones, I eventually went to our local post office to see if they would order me 50, since they had the model I wanted in their catalog.  Not only were they willing to order them (I promised to pay up-front, since it was a large purchase), they also kindly sliced 10% off the price.  So I now have a box of 44 phones in my lounge room, with the remaining 6 on back order:

At this price, the phones don't come with SD cards, which we do need for the Serval Rhizome software to do anything useful, as store-and-forward requires somewhere to store!  So I hunted around, and after some luke-warm experiences with suppliers either being unwilling to give me a decent price for what is clearly a wholesale quantity, or failing to stock enough, I tried OfficeWorks.  They had enough in stock, but were charging $16 for 4GB cards, which I had quotes from other local stores for $7.  So I loaded my basket with 50 memory cards, and proceeded to try their price-matching policy:

However, the large price difference and quantity did trigger concern from their store manager.  He was very friendly and amiable, but did point out that to get the price matched, I had to find a local supplier with the quantity I wanted actually in stock.  But that wasn't easy to arrange, as most of the cheaper suppliers only had a few on hand.  There is of course a silliness in their rule, as I could have bought them in small batches such that each batch was small enough that the cheaper shop held sufficient stock.  But in the end I did manage to find a cheap supplier on eBay who had plenty in stock at $5.80 a piece for SANDisk 4GB class 4 microSD memory cards.  Now we just have to see if they will arrive.

So that covered the phones and memory cards.  The next challenge was to come up with a way to easily charge 50 phones.  Not only did it need to work in my home, but it also had to have the potential to work in a real disaster zone, and one which might not be in Australia.  Having enough power boards to plug 50 little USB charger bricks was not an attractive option, especially since I need to fit all of this into my 23kg luggage limit when I fly, and 50 phones alone are not that light.

What I have decided to do is to chop up a pile of USB leads and wire them up to some automotive 5v accessory power supplies that are commonly used to power portable DVD players and the like.  Apart from being the cheapest 5v high-current power supplies I could find (AUD$40 for 5A), they have the benefit of running on 12v, or in the case of some models, on 12v-24v, so that they can even work in a truck.  This means that in-vehicle mass-charging is possible when the power grid is off.  It also means that they can all be charged using a single cheap 13.8v power supply, which are also quite cheap; you could even use an old computer power-supply.  You can see my prototype here:

So now I just need to get back to writing the software that needs to go on these phones ...

TEDx Adelaide Talk Is Now On Youtube

As I mentioned in a previous post, I recently presented at TEDx Adelaide, which had the theme "On The Edge".  They have now put the videos up on YouTube, so here it is:

 

The bottom line? 

Just as MP3 files and digital music distribution has changed the market place for the recording industry, so to decentralised digital mobile communications is on the verge of similarly disrupting the mobile telecommunications industry, by similarly adding value to the everyday experience of many people. 

The question is, will the mobile carriers see the opportunities that change brings, or will they work against their own interests by failing to embrace the change?

Only time will tell.

Demonstrating the Serval Rhizome Store-and-Forward MeshMS SMS Service

(Please take a look at our crowd-funding campaign at igg.me/at/speakfreely.)

Update: We trialled Rhizome on a training exercise in New Zealand recently.  Follow the link to read the blog post about it.

SMS messages on a cellular network get delivered via the cell towers and message centre infrastructure.

On a mesh, it is possible for us to deliver messages to other phones that are reachable on the mesh at the same time.  This works great, and we have had this capability in the Serval BatPhone software for a while now.

However, it does have some limitations, in particular, if there is no link all the way from the sender to the receiver on the mesh at the instant the message is sent.  This is rather unfortunate, as we usually think of SMS as being the most reliable fall-back on a mobile communications network.

So we set about replicating this resilience by creating a store-and-forward SMS-like service on top of the Serval Rhizome mesh file distribution framework.  We call this MeshMS, for Mesh Message Service.

This service uses direct mesh links if they are available by making use of the existing SMS capability in the Serval BatPhone software.  However, if there is no direct link, then it uses a store-and-forward scheme, that asks any passing phones to copy the message and distribute it to other phones on the mesh, until it (hopefully) eventually reaches its intended destination.  The cartoon below shows how this works.

The man wishes to send the message "Prepare the Zeppelin" to his hench-person, but there is no direct mesh link at that time due to the challenging topology.  The message gets picked up (stored) by the compatible phone in the pram, without any action on the part of the woman.  The woman then keeps walking along, and eventually the phone in the pram is able to automatically deliver (forward) the message to the ultimate destination, whereupon the minion knows to ready his master's zeppelin, to do the weekly grocery shopping, one trusts. Of course, there could be many intermediate steps, instead of just the one shown here.

The great thing about this approach is that it doesn't require a complete path to the destination at the time of sending, but can propagate progressively across the mesh as it is able, and can make use of nodes that move between otherwise isolated mesh networks, creating an asynchronous link between them where it would not otherwise be possible.

While the delay in such a service is huge, the bandwidth is also great, as potentially gigabytes of data can be transferred between nodes.  One side use of this protocol that we intend to exploit is to provide an efficient means of distributing updates to the Serval software suite, so that field updates can occur without dependence on infrastructure, and with much greater aggregate bandwidth than any single-cast cellular or wireless approach.  In fact, this will even allow the update of software, maps and other resources during a disaster.

We have even demonstrated it to deliver an SMS message between South Africa and Australia, using nothing but compatible phones to carry the message more than 10,000km:

This feature has profound utility in allowing the exchange of messages, files, and all manner of data in what are otherwise very difficult settings.

It also provides the capabilities required to enable disadvantaged communities, perhaps in remote locations, war zones or informal settlements, to create their own infrastructure, carrier and cost-free SMS networks using compatible handsets, so that they can enjoy the benefits of digital communications that many of us take for granted.

Early Prototype of the Serval Mesh File Distribution System, the Rhizome Retriever

Romain one of our team has been working hard to get the Rhizome Retriever together as part of our work in supporting citizen journalism in a community in Nigeria, that I have blogged about previously.

They are already using our software in that community to make free mesh telephone calls, but from the outset the plan has been to enable them to be citizen journalists, and to share news and information in their community.

To enable this, we are making our Rhizome Retriever (Serval RR), which basically lets you pick files on your phone, and put them up on the mesh, from where they will be automatically distributed to other phones on the mesh.

Mass file distribution on a mesh is usually fraught with difficulties, not the least of which is that the available bandwidth on a mesh halves (or worse) for each extra hop that you try to traverse.

So you can often get decent bandwidth to nearby nodes, but poor or intermittent connection to more distant nodes.

Also, the more people trying to transfer things many hops across the network reduces the available bandwidth for everyone.

So we decided to make the Serval RR only ever send data one hop to the nearest neighbours.  They can then in turn send data to their neighbours later on at their convenience.

As a result, Serval RR can already distribute even relatively large files, certainly into the several mega-byte range, without great difficulty, and without making the network unusable for everyone else.

Here is a quick demo of the initial prototype of the Serval RR software in action:

The importance of communications during emergencies

Early 2011 saw the worst floods in Queensland, Australia in 40 years.

Not surprisingly, this placed significant stresses on response efforts, and for a variety of reasons, the Queensland Government has issued an interim report on the event and what responses should be made.

You can read the interim report here.

I have been reading through this from a telecommunications perspective, and found the following items:


2.24  Seqwater should give consideration to posting information about current and future releases on its website during flood events as one method of ensuring accurate and timely information is available to the public. 


This may seem like a small matter, but by making the information available somewhere where someone in the community could access it, and possibly disseminate it further, perhaps by word of mouth, or perhaps by feeding it into a crowd-source incident reporting system such as Ushahidi or the Serval Rhizome/Mapping combination, where it could be made available to others who need it.  Indeed, this process could be automated, providing a very valuable community service.  However, if the information is not shared in the first instance, then such broad and means of distribution will be troublesome to implement, and potentially disadvantage many.

In short, putting information out where the public can get to it, and make further use of it supports resilience.



5.21 The Queensland Fire and Rescue Service should ensure that rescue technicians on deployment are provided with individual radios, rather than sharing a communications pack


Presumably the sharing of communications packs is related to their cost and bulk.
Using off-the-shelf meshing mobile phones would allow all rescue technicians to have a personal means of communications that makes use of the shared communications pack, relaying traffic back through that resource.



5.29 The Queensland Fire and Rescue Service should consider isolating repeaters during a large scale emergency response. If this solution is found to be feasible, it should be implemented as protocol as soon as possible. If it is not, the Queensland Fire and Rescue Service should explore other solutions to the issue of the fire communications network being overloaded and firefighters resorting to localised networks during large scale emergency response situation.


This seems to be responding to the issue of excessive traffic being relayed across the region, congesting the system and preventing it being of effective use.  The Serval Mesh system has the potential to localise message delivery to the local teams that need it (whether or not they are locally based), and still retaining the ability to broadcast messages over the whole region when suitably addressed.

This is not a particular mode we had considered greatly in the past, so this is a helpful thing for us to discover.


7.2 Lockyer Valley Regional Council should investigate the feasibility of installing alarm-activating gauges in the creeks at Spring Bluff, Murphys Creek and other communities where communication systems are poor and there is a risk of rapid and unexpected water rise.


This is interesting for us to read, as we are already contemplating creating a very similar system for use in the Mekong River Basin on conjunction with a Lao doctoral student here in the department.  The characteristics of the system are having a local mesh broadcast an alarm to all mesh nodes when one or more mesh-equipped sensors indicates a high water level.

It is possible that those sensors could be low-cost mobile telephones connected to a device such as the IOIO, creating a very simple and low-cost solution, provided the device can be powered, perhaps using a solar panel and modest storage battery, such as an old car battery no longer able to supply the peak load required to start a car, but more than sufficient for the couple of watts required to run a phone and sensor.

"SMS alerts are also not a reliable method of providing flood warnings in parts of Queensland which experience problems with telephone coverage. That difficulty is compounded during a flood, when telephone reception can be affected by flood related power outages and congested telecommunications networks."


This is precisely the kind of short coming with cellular networks that Serval has sought to find and create solutions for, that complement the existing infrastructure.  In particular, the ability of the Serval Rhizome mesh file/message distribution system to work asynchronously, and automatically share information carried in phones as they more from region to region has particular value in these sorts of situations.

Also, the ability place local calls on the mesh, and where possible, setup connections from the mesh to the outside world offers a significant capability that is otherwise a considerable liability in these situations.

The ability for Serval technology to allow the rapid setup of a local mobile telephone network, and then connect it to the global telecommunications network using the nearest functional mobile phone tower was demonstrated in Brisbane in late January 2011, just a couple of weeks after the flooding had subsided.

We did this by placing a phone running the Serval software at a high vantage point where it could communicate with the nearest functional mobile phone tower (we used a helium balloon, but a roof top, or even a long fishing pole gaffer taped to a car would suffice).  This then allowed the phones on the ground that were also running our software to relay calls out to the world.  Here is the video we took of us doing exactly this, and watching people use it:

More than we expected at the IEEE

If you have been reading this blog you will know that we sent Romana over to Okinawa to present our desire to see ad-hoc mode wifi improved, and also to consider how to use the baseband radio in mobile phones to support wifi on very low cost phones, and also to provide much longer range meshing using the ISM915/868 bands that offer very useful link budget advantages over the 2.4GHz band used by regular WiFi.

Well, we have been absolutely gobsmacked by the interest and positive response that Romana experienced at the meeting, and have the opportunity of taking up the baton to champion proposing these enhancements through the formal IEEE 802 standards process.

This is a great privilege, and also an opportunity that cannot be accepted without serious and solemn consideration, because it will basically require someone's effort, full time, for perhaps three years or more.

We are convinced that we want to, and that we should engage with this standards process, but just need to work out whether we have the resources to do it, without drawing all of our available resources away from progressing the development of the Serval mesh telephony software.

More news as we have it.

Opening Mobile Hardware

Over the last few years we have seen the impact and innovation that opening the software on smart phones has enabled.

The key is that the barrier to entry is now so low, that innovation can prosper without significant drag or hindrance.

So why don't we open the hardware on smart phones, by offering a "geek port" that some nice simple interfaces and a really cheap common connector, like a female .156" DIP header?

The port could have some analog and digital input and output lines, and maybe a serial interface or two, perhaps the common SPI interface, and a 3.3v power rail (that the phone can turn on and off to control power consumption).

Such a simple port would be trivial in cost to add to smart phone, probably costing less than $1 in marginal hardware cost, plus a once-of cost developing some nice APIs to access the port.

Creating such a simple interface would allow the creation of cheap dumb devices that can plug into the port.

Really boring stuff, like, say, a digital thermometer, an LED and sensor that can be used to collect pulse oximetry data, and relay it on an infrastructure-independent mesh network like servalproject.org, to a local care provider.  Or maybe it might be a cheap ultrasound transponder to allow mid-wives and maternal health workers to acquire cheap ultrasound imagery.

Each of these plug-ons could probably be made for $5 or less, and yet each has the potential to save many lives in the developing world, and save many billions of dollars in the developed world.

And that is just in one application domain.  Who knows what else people might come up with.

After all, no one anticipated the myriad applications that have been enabled by making smart phones programmable.

I reckon that for perhaps $100,000 it would be possible to get a phone designed and a small manufacture run of such phones to demonstrate the idea.  Anyone want to make a significant impact on the world?