Abstract: Aiming at the problem that wireless sensor networks are susceptible to severe environmental damage and the energy consumption of key nodes is fast after connectivity restoration, which leads to network disconnection, this paper proposes a network connectivity restoration (CRAST) algorithm based on Steiner tree and Tyson polygon. Firstly, the algorithm abstracts the divided node partitions into discrete points, enumerates all non-degenerate quads in the discrete point area, and then uses the quadrangular Steiner tree structure to deploy relay nodes to these non-degenerate quads so as to achieve connectivity restoration. Secondly, the algorithm constructs a Delaunay triangle network with key nodes, and uses the Delaunay triangle network to construct the Tyson polygon topology of the entire wireless sensor network. Finally, the algorithm deploys movable backup relay nodes at all vertices of the Tyson polygon, and moves the backup relay node to replace the damaged key node when the key node is damaged. The algorithm enables the sensor network to achieve connectivity recovery at the least cost, and has strong efficiency and robustness.

Key words: connectivity restoration, Steiner tree, Tyson polygon, standby node movement