Topology mapping algorithm for 2D and 3D Wireless Sensor Networks based on maximum likelihood estimation

Automation of many sensor network protocols requires maps indicating sensor locations. Physical coordinate based maps capture the physical layout including voids and shapes, but obtaining the required distance values is often not feasible or economical. Alternative is to use topological maps based only on connectivity Information. Due to lack of physical distances, they are not faithful representatives of the physical layout. Here we present Maximum Likelihood-Topology Maps (ML-TM) that provide a more accurate physical representation, by using the probability of signal reception, an easily measurable parameter that is sensitive to the distance. Approach is illustrated using a mobile robot that listens to signals transmitted by sensor nodes and maps the packet reception probability to a coordinate system using a signal receiving probability function. ML-TM is an intermediate map between exact physical maps and hop- based topology coordinates. Results show that ML-TM algorithm generates maps for various network shapes with voids/obstacles in different environmental conditions with an error less than 7%. Performance of the algorithm in 3D sensor networks is also illustrated.