Abstract: For problems that current coal mine personnel positioning system adopts region positioning method, and cannot directly determine exact location and movement direction of underground personnel, an algorithm based on tree structure was proposed, which uses topological relations to calculate track that underground personnel may walk. The algorithm defines a topology model with point and segment, segment and segment as well as segment and point. Based on the model, tree structure is built and personnel walking track is got by its hierarchy traversal. In the calculation process, the algorithm uses real-time status information of receiver to preclude impact of non-working receiver and substations automatically, and ensures tracking accuracy.