Wireless Sensor Networks (WSNs) are recently used in monitoring applications. One of the most important challenges in WSNs is determining the operational mode of sensors, decreasing the energy consumption while the connectivity requirements and the special properties are satisfied. This problem is an NP-hard one and is a time–consuming progress. In this study, an improved version of quadrivalent quantum-inspired gravitational search algorithm as a new metaheuristic, well suitable for quadrivalent problems is proposed using Not Q-Gate to optimize the performance of the WSN. Beside, to enhance the speed and the accuracy of the algorithm more, we used a parallelizing technique using Open-MP. Parallelizing this algorithm on mentioned problem is useful from four aspects; 1 - accelerate the speed of the algorithm, 2 - improving the quality of solutions by letting the increasing the population size, 3 - The possibility of using the algorithm, in larger-scale WSNs and 4 - power affectivity of the base station using multicore processors. To validate the performance of our proposed approach, a comparison between this approach and the previous methods is performed. Our experiments verified that the proposed method can effectively improve the performance more than 2.25 times and the speedup faster than 4 times on an 8-core CPU.