Topology Discovery Using Binary Connectivity Information

Discover Topology Using Connectivities A distributed coordinate-free topology aware algorithm called Triangular Mesh Self-organized self- Healing (3MeSH) is introduced to detect boundaries of coverage holes using connectivity information, and recover such holes by activating the minimum number of redundant nodes using a distributed iterative process. A routing hole can be detected in almost the same way as a coverage hole, therefore routing holes, jamming holes, sink/black holes and worm holes may also be detected or avoided using exactly the same algorithm (3MeSH). A probabilistic model is also introduced to calculate the probability of triangulation for any position in a randomly deployed sensor network given the node density. Another mathematical model is introduced to calculate the mean size of holes. Based on these models, the expected number of holes and the probability of complete coverage are formulated for a sensor network with any node density and target area.