Abstract: Concerning the high computational complexity and communication overhead of message passing-based localization methods, a self-localization algorithm with low complexity and communication overhead is proposed for wireless networks with mobile sensors. To decrease the communication overhead, all the messages were restrained to be Gaussian functions. Consequently, only the means and variances need to be transmitted in the network, and variational message passing (VMP) algorithm is employed to reduce computational complexity for it is suitable for exponential models. Firstly, location prediction is performed according to historical trajectories and the a-priori distributions of the sensors’ positions are obtained. Then, the marginal a-posteriori distributions of the positions are iteratively calculated by using the VMP message update rules on factor graphs. During the messages update, the non-Gaussian beliefs caused by nonlinear ranging model were approximated to Gaussian probability distribution function (pdf) by expanding the nonlinear terms with second-order Taylor series. Finally, the positions of the sensors can be estimated based on maximum a posteriori estimation. Simulation results show that the performance of the proposed algorithm is close to sum-product algorithm over a wireless network (SPAWN) with much lower communication overhead and computational complexity.