Chess – Node Counting in Wireless Ad-hoc Networks #SWI2011

A defining characteristic of wireless ad hoc networks is their dynamic behavior. In practice, it is not uncommon to find that the topology of even a small network deployed in a controlled environment changes from one moment to the next, without apparent changes to the layout of the nodes. This behavior stems from the inherent unreliability of wireless communication. The wireless nodes we consider are simple devices that communicate by broadcasting messages into the air. Nearby nodes may receive these messages, but the reception is not guaranteed as there may be problems in the communication, such as interference or collisions. For nodes that are too far apart, the signal may just be too weak to allow for a message to be received. As a result, nodes may receive messages from a (possibly large) set of neighbors over time, with some nodes being heard from more often than others. The problem we propose is the discovery of the properties of the network by individual nodes.