Chess – Gossiping to Optimality #SWI2006

Analysis and optimization of message delivery in wireless sensor networks

Chess is a company of about 160 employees, with locations in Haarlem and Best, that offers products, solutions and services in the field of electronics, IT-applications and embedded software. One of the projects of Chess has to do with ‘wireless sensor networks’. Suppose that a
country wants to detect forest fires as soon as possible. They want to place a lot of devices with a sensor throughout the forest. Of course, these devices should be small, cheap, and wireless (so they work on a battery, and therefore have a limited capacity).

The devices check the temperature at given times and registrate this in their cache memory. There is communication between devices by means of the ‘Gossip protocol’: In every round, each device in the network acts as ‘active peer’ once. An active peer broadcasts its
cache to its neighbours. Also, the neighbours send the contents of their cache memory. The receiving node stores the data in a ‘receiver cache’ of size c. When receiving data from more than one node, the data is merged into the ‘receiver cache’ by overwriting the double elements
and deleting the oldest elements. To create space in the cache memory at the end of each exchange, each device that has received elements will delete elements that were already present. Then delete the oldest items until c elements are left in the cache. The devices may additionally delete messages that are older than time T. The messages are spread over the network and reach a base station in the end. Base stations never act as ‘active peer’ but can be chosen as a neighbour of active peers. The base station collects the information for further processing.

Main Issue: Timely delivery of messages to the base station

What is the chance that a message will reach a base station? And more importantly: can we analyse the number of rounds it takes for a message to reach a base station (the ‘latency’). The simulation of the ‘Gossip protocol’ looks good, but there is no mathematical analysis. One can imagine that if Chess is held responsible for a failure in the transfer, they want to be sure that it will really work. What is the relation between the redundancy and the success probability? Is an optimization possible given the power capacity of the devices and a limited
number of devices?

Side Issue 1: Already processed messages

When a message has reached a base station, it can still be sent around in the network by other devices. This is of course unnecessary. How long will the message stay in the network after it has reached the base station?

Side Issue 2: Comparison with an optimal model

How much worse does the Gossip protocol do in comparison with the ideal protocol, where every message is delivered only once to the base station by the optimal route? This ideal protocol is not reachable, because of capacity and security constraints, but a comparison
would establish an upper bound on what optimisation of the Gossip protocol may cost