A Practical Algorithm for Network Topology Inference

When a network of robots or static sensors is emplaced in an environment, the spatial relationships between the sensing units must be inferred or computed for most key applications. In this paper we present a Monte Carlo expectation maximization algorithm for recovering the connectivity information (i. e. topological map) of a network using only detection events from deployed sensors. The technique is based on stochastically reconstructing samples of plausible agent trajectories allowing for the possibility of transitions to and from sources and sinks in the environment. We demonstrate robustness to sensor error and non-trivial patterns of agent motion. The result of the algorithm is a probabilistic model of the sensor network connectivity graph and the underlying traffic trends. We conclude with results from numerical simulations and an experiment conducted with a heterogeneous sensor network

Authors

• Dimitri Marinakis
• Gregory Dudek

Keywords

• Inference algorithms
• Network topology
• Robot sensing systems
• Computer networks
• Monte Carlo methods
• Event detection
• Robustness
• Telecommunication traffic
• Traffic control
• Numerical simulation
• Topology Inference
• Sensor Networks
• Connectivity Information
• Topological Map
• Trajectories Of Agents
• Robotic Network
• Time Delay
• Markov Chain
• Observational Data
• Transit Time
• Network Parameters
• Transition Probabilities
• Directed Graph
• Sensor Locations
• Number Of Agents
• Node Positions
• Parameter Update
• Real-world Conditions
• Environmental Agents
• Connectivity Parameters
• Mean Transit Time
• Traffic Patterns
• Single Trajectory
• Transition Edge
• Acceptance Probability