Thursday, July 1, 2010

Unique address for wireless sensors

When designing wireless sensors any sensible communications protocol will feature a device address so that multiple instances of the setup can exist in the same space.

So how do you ensure that wireless devices have a unique address? One approach is to embed a fixed serial number in every device (much like the 48 bit WiFi or Bluetooth MAC address). This requires that each device is programmed with the number at manufacture time.

Another other approach is to use a random number generator to assign an address when the device is configured. For consumer devices is normally involves pressing an associate button on the sensor device for a few seconds.

It is not possible for a CPU to generate a genuine random number without outside help. Fortunately there is a workaround, which utilizes one of the best sources of randomness there ever existed: a human.

My approach (which I suspect is common, but I cannot find any references to it) is to generate a random number when the device is associated using the duration of the associate button press as the source of the random number.

The idea is to time the duration of the button press with as much resolution as possible (eg in microseconds). Then take this duration modulo the size of your address space and you have a pretty good random number.

For example, let’s assume we can time the button press with ┬Ás precision and that we are looking for a random 16 bit address (ie a number between 0 and 65535). The clock will cycle through this entire address space in just under 66ms – less than the time that a typical human will take to press a button.

Let's look at some real data. I rigged a micro switch on a pin on the Arduino and wrote a simple timing loop. I pressed the micro switch about 1000 times in succession.

You can see that the typical micro switch press lasted about 100ms +/- 50ms. As the experiment progressed I started getting bored so you will notice a slight decrease in button press duration as impatience set in. A histogram view of this data looks like this:

A normal distribution as one would expect. Now if we take these time values modulo 2^16 (65536) we have a distribution that looks like this:

Nicely spread across the entire address space, with a slight bias in the 30000 - 60000 region, but good enough.

No comments: