Connectivity Optimization Problem in Vehicular Mobile Wireless Sensor Networks

Wireless Sensor Networks (WSNs) received much attention from researchers thanks to its wide range of applications. Among great number of factors to measure the quality of WSNs, connectivity is always considered as one of the most important criteria. Therefore, this paper extensively focuses on ensuring the connectivity of WSNs. This problem has been proved to be NP hard. Previous studies on this field mostly used a large number of static sensors leading to expensive network construction costs and the lack of flexibility necessary to expand the network. In order to overcome these disadvantages, the author proposes a new model that utilizes the combination of mobile sensors installed on the vehicles and static ones which connects system elements. The objective of this model is to minimize the number of sensors of the WSNs with connectivity constraints on mobile sensors. Our proposed algorithm obtains this objective by properly adopting K-means clustering algorithm and Kruskal algorithm which are reinforced by a heuristic method. The quality of this algorithm is measured by the experiment done on 27 instances which varies in 3 parameters. The results show that our algorithm provides good solutions which achieve 58.84% average reduction of needed sensors comparing with solutions derived from simple approach method.