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).

Plaaatje_Chess_problem_2006The 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 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 the 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 an optimalisation of the Gossip protocol may cost


Download scientific


Print this page


Chess – Gossiping to Optimality