Suppose a fire breaks out in an elderly care center: wouldn't it be nice if the firefighters can whip out their PDA's and check how many people are left in the building and where in the building they are? Or think of the relative peace and quiet you as a passenger would experience in Schiphol if no more of those "will mr. X hurry to gate D11, we will proceed to offload your luggage" messages keep ringing out because it was known that mr X was still windowshopping in wing A and sent a text message telling him to start moving to gate D11 (and think of the amount of work it would save Schiphol personnel).

Tracking and Tracing, or localization, is perceived to be one of the main area's of application for wireless sensor networks. Because it is hard to track human beings with just a wireless sensor network deployed in the area (what sensors would you use to identify hundreds of persons at the same time?), the usual approach is to assume that the targets to be tracked actually carry a node with them. This may seem to be a bold assumption, but think of the amount of personal possessions you already carry with you: wallet, phone, pda, laptop, elderly people carry an alarm button. Each of these are larger than a single wireless sensor node, so the assumption is not as bold as it may seem. So tracking and tracing people then becomes a matter of determining the location of the node the person carries in the deployed network.
There are roughly three popular classes of methods for doing this: a dedicated sensor, radio signal qualities and network communication patterns.

• The most straightforward way to determine the location of a node would be to outfit it with a GPS-device. This would, however also be the most energy-consuming solution, and, moreover, one that would not work indoors.
  
• Measuring qualities of a radio signal is a second method. In a wireless sensor network, nodes communicate with each other using a rather short range radio. The idea is that if node A measures qualities of the radio signal it receives from node B (qualities such as signal strength, travel time), and node A knows how the distance traveled by the radio signal influences the qualities of the radio signal, node A can infer the distance between node A node B. If three nodes do this with the signal emitted by a target node, a technique called triangulation can be used to determine the exact position of the target node. Problematic with this approach is that it is typically very hard to reliably measure these qualities of a radio signal. Also, it is practically unfeasible to know how these qualities are affected during flight time of the radio signal.
  
• The third method is to use communication patterns in the network to measure distances between nodes. The assumption is that one can adopt some model for the propagation of radio signals through the environment, and thus for the reception of signals from node A by node B. Well-known models are the unit-disc model, where there is a fixed radius around a node where its radio signal is perfectly received while outside of the radius there is no chance the signal is received; and the stochastic model, where the chance of receiving a signal decreases with distance. Using this assumption, one can let nodes compare their neighborhoods (the set of nodes a node can or has communicated with): more similarity in neighborhood indicates a smaller distance. Alternatively, nodes can count the amount of packets they receive from other nodes and estimate what chance they have of receiving a packet from other nodes, and then use the radio model to determine the distance between itself and other nodes. The former technique is exploited in for instance the NIDES algorithm, the latter we have used and experimented with at Almende.
  
• A fourth option, which is less popular as it currently is futuristic, would be to use input from non-dedicated sensors to determine whether nodes are close to each other or not. For instance, nodes that are close would "hear" the same door slam, and both measure a decrease in temperature when the window is opened. This is an option that is on Almende's wishlist.
  

For one week, a network of thirteen nodes gathered packet reception ratio's from every other node in the network. Additionally, one mobile node moved around in the environment. The goal was to be able, after the experiment, to deduce from the data where the mobile node was at what time and, additionally, to see if it was possible to reconstruct the topology of the network from the data. In the first image, the packet reception ratio's of all static nodes from the mobile node are plotted for a period of twelve hours. One can clearly see five distinct patterns, that correspond to the moments and places the mobile node was moved. The second image is an attempt to reconstruct the network topology by loading the packet reception data into INQ, an algorithm normally used to generate images of social networks. Though the result is not 100% correct, some major clusters can still be seen, which makes the result at least hopeful regarding the ad-hocness of the attempt. For a rendition of all data of the entire experiment, check this demo!


Packet Reception Ratio's of packets from the mobile node to the static nodes.


Rendition of the network topology based on the inter-node packet reception ratio's.