Verifiable Multilateration Based on Ultra-Sonic Distance Bounding

My bachelor project was a venture into positioning in wireless networks. The supervisor on the project was Srdjan Capkun. Srdjan had developed an algorithm that would securely determine the position of a wireless device. The idea were to use this to implement access control on the wireless network. If you physical were inside a building you were allowed to associate with the wireless network. If you moved into a specific room you could get access to the server and printer there, and so on.

The idea was to have bay stations that did distance bounding calculations with radio waves and ultrasound. These bay stations would be placed strategically inside the building employing secure positioning. As bay stations we used Mica2 Crickets from Crossbow.

Our setup had the Crickets connected by serial cable to a number of Compaq IPAQs running a Linux distribution. The combo was placed around the building and the IPAQs wirelessly communicated the Crickets distance bounding to a sink. The sink then did the Verifiable Multilateration and displayed the location of devices inside the building. Remember that this was done before there existed sensors that communicate wirelessly themselves, and the IPAQ was thus a necessary complication to the setup.

We implemented the entire program in C and NesC which is an extension to the C designed with TinyOS in mind. The graphical user interface was done in GTK+, which I later on wowed never to touch again. Our program were impressively accurate. We could pinpoint devices with only a few centimeters error. The setup were of cause a proof of concept and would not fair particular well in a real world situation – but it does a fine job of demonstrating the the applications of secure positioning.

As kind of an easter egg we implemented a Tic-Tac-Toe game using the position of devices. So moving the devices around inside the covered area, were equivalent of moving pieces in a Tic-Tac-Toe game. We imagined that beside providing the building with a more secure wireless connection, the employees could spend the coffee break playing lifesize games with their laptops

The project was fun to develop, and was the first larger project I have done in C. Also it is the first projects where the day before the deadline everybody started to panic – well that came out wrong – it is the first project where the day before the deadline everybody started to panic because they could not think of anything that needed attention. Everything were simply done the day before the deadline, and that spooked us quite a bit.