基于内部凸包骨架的多分区连通恢复算法

he connectivity of wireless Mesh network is the premise of its smooth operation as a whole. However, due to the instability of the Mesh node itself or the external interference damage, the network is very likely to appear multiple key cut point failure and form multiple disconnected partitions. Aiming at the problem of multi-partition connectivity recovery for large-scale node failure, this paper first proposes an evaluation criterion of network balance according to node degree, mean square error of node degree, coverage rate, number of representative nodes in each partition, and average hop count between partitions. Then a multi-partition relay node placement algorithm (InnerHull based Relay Node Placement algorithm, InnerHull) based on Inner convex Hull skeleton is proposed, which uses relay deployment to restore connectivity. The goal is to balance the recovery cost (the number of relay nodes) and the connection quality (the average node degree, the average hop count between partitions, and the coverage rate per relay node) of the network. The algorithm constructs the minimum envelope rectangle according to the geometric convex hull of the point set, generates internal grid points by adjustable parameters, and then uses the grid points inside the convex hull of the node set to construct the internal polygonal convex hull backbone, and connects the isolated partitions to the internal convex hull backbone to complete the connectivity recovery. Simulation results show that compared with the comparison algorithms, the proposed algorithm has a better balance between network recovery cost and network quality.