Voronoi-Based Approach to Increase Connectivity and Coverage in Randomly Deployed Wireless Sensor Networks

Deployment of sensor nodes is a very critical issue in Wireless Sensor Network (WSN) because it can decrease the quality of service (QoS). Sensor nodes can be randomly deployed over large, hazardous, and inaccessible areas, which can generate redundancies through clusters, isolated nodes, and subnets, creating unmonitored holes in the region of interest (RoI). This deployment problem can be minimized with the use of mobile nodes, constituting a hybrid wireless sensor network (HWSN), to search and integrate nodes by expanding the connectivity frontier region in the direction of the biggest holes identified by the Voronoi Diagram in the RoI. This allows expanding coverage with the mobile node and create new connections with isolated nodes and subnets that are in the neighborhood. However, although several Voronoi Diagram-based approaches are found in the literature, they increase coverage without addressing network connectivity, the focus of this work. Thus, in this paper we propose and compare the Voronoi based algorithm (VBA) and the Voronoi Virtual Force Algorithm (VVFA) to expand the connectivity region of the WSN with random deployment. The results show that the Voronoi approach presented a better performance in a convex environment and similar performance in a non-convex environment concerning coverage and connectivity. The Virtual forces approach possibilities of avoiding obstacles but present a local minimum.