Magnus Skjegstad

AR.Drone test flight #1

I bought an AR.Drone some time ago, but I haven’t been able to do any testing with it until now. Yesterday we did a short experiment to see if it could lift the mobile phones we used for the chat experiment.

In this picture the phone is taped to the side of the AR.Drone. The phone was running an Android app which took pictures at regular intervals and sent its current GPS position. The GPS coordinates and the images were then sent to a laptop. Here are two of the pictures taken by the phone.

We also recorded a video of the experiment. The AR.Drone did not seem to have any problems stabilizing itself with a mobile phone taped to its side.

Here’s some of the output from the test program on the laptop. It only shows the GPS coordinates in this screenshot.

(Video and images by Ketil Lund)

Experimenting with distributed chat

In this experiment we use a remote controlled airplane and an Android phone to carry data between two computers. The idea is that in environments where you are without a network connection you could still get a working network environment with the help of mobile nodes picking up messages in one area and delivering them in another. A typical scenario is for example rescue operations, where people may move in and out of a difficult to access rescue area and carry messages with them on their mobile phones. Although we focus on chat in this experiment, the real data carried could be anything you could store in a file, e.g. medical data from patients, information gathered from sensors in the environment, images etc.

The image above illustrates the scenario we use in the experiment. Bob and Alice are two users who are unable to communicate directly. Another user, Charlie, has been visiting Bob and is about to go over to Alice. As Bob is unable to reach Alice he delivers his messages to Charlie, who then proceeds to carry them over to Alice. This is the basic principle we evaluate in the experiment. Except Bob and Alice are laptops and Charlie is a cell phone attached to an airplane.

The client we use on the laptops is the same as I wrote for a paper I presented at MILCOM in November. It runs on top of a generic protocol and middleware for distributing content reliably in dynamic network environments, called Mist. In the paper we only evaluated its performance in a virtual environment, so after we finished the paper we thought it would be interesting to see if we could do a real experiment with the same software.

One of my co-authors on the paper, Espen Skjervold, had a remote controlled airplane we used to carry the mobile node. As the plane was small and light we had to find an Android phone that it was able to lift for longer time periods. The phone we ended up using was the Sony Ericsson Xperia x10 mini. According to the specifications it only weighs 88 grams. With the help of high quality electrical tape we taped the phone to the plane, as seen in the picture to the right.

On the Android phone we installed a very basic application which just starts the Mist middleware. It also regularly transmits the GPS coordinates of the phone. For the clients we used two Macbooks running the chat client I wrote for the paper. The clients generate random text strings from Lorem Ipsum every 10 seconds. The phone and the laptops were all configured to join the same ad-hoc wireless network.

The radio range of the laptops and the phone turned out to be much longer than we had anticipated. To reduce the radio range, we placed one of the nodes in the trunk of the car. We placed the other node behind a car at the other end of the parking lot. After some trial and error we managed to find a placement of the nodes which allowed the airplane to only be within the radio range of one laptop at the time.

The image below shows the airplane carrying messages between the two nodes. The nodes are never in contact with the airplane at the same time, so the messages have to be physically carried between the nodes by the Android-phone/airplane.

When the plane comes in contact with one of the nodes the Android-phone picks up any new messages and delivers old ones. The plane then moves out of radio range for while, before it comes in contact with the other node and repeats the process.

The plane we used was not very fast, so we weren’t able to reach the same speeds as we tested in the paper. But this small scale demonstration shows that the Mist middleware also works in real world experiments.

The Mist middleware will soon be released as open source.

A stand-alone Java Bloom filter

Some years ago I needed a Bloom filter implementation in Java. At the time, most implementations where either written for a special purpose or relied on other libraries. I decided to write my own Bloomfilter-class which did not depend on anything outside the standard JDK.

This post gives some examples of how the implementation can be used. If you want to go straight to the source code, it is available here. You can also download BloomFilter.java directly if you don’t need the whole project.

To create an empty Bloom filter, call the constructor with the required false positive probability and the number of elements you expect to add to the Bloom filter.

1
2
3
4
double p_fp = 0.1; // False positive probability
int n = 100; // Expected number of elements

BloomFilter<String> bf = new BloomFilter<String>(p_fp, n);

The constructor chooses a length and number of hash functions which will provide the given false positive probability (approximately). Note that if you insert more elements than the number of expected elements you specify, the actual false positive probability will rapidly increase.

There are several other constructors available which provide different levels of control of how the Bloom filter is initialized. You can also specify the Bloom filter parameters directly (bits per element, number of hash functions and number of elements).

After the Bloom filter has been created, new elements may be added using the add()-method.

1
bf.add("foo");

To check whether an element has been stored in the Bloom filter, use the contains()-method.

1
bf.contains("foo"); // returns true

Keep in mind that the accuracy of this method depends on the false positive probability. It will always return true for elements which have been added to the Bloom filter, but it may also return true for elements which have not been added. The accuracy can be estimated using the expectedFalsePositiveProbability()-method.

Put together, here is the full example.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
double p_fp = 0.1; // False positive probability
int n = 100; // Expected number of elements

BloomFilter<String> bf = new BloomFilter<String>(p_fp, n);

bf.add("foo");

if (bf.contains("foo")) { // Always returns true
    System.out.println("Bloom filter contains foo!");
    System.out.println("Probability of a false positive: " +
         bf.expectedFalsePositiveProbability());
}

if (bf.contains("bar")) { // Should return false, but could return true
    System.out.println("There was a false positive.");
}

The source code is currently hosted at GitHub.