A lower bound on range-free node localization algorithms

Wireless sensor networks have been used in proposed solutions to many important practical problems. A very important problem in many wireless sensor networks is localization, or the determination of geographical locations of the sensor nodes. In this work, we study the problem of range-free localization-or computing locations based only on the neighborhood information of nodes. These algorithms typically assume that a fraction of the sensor nodes (called seeds) know their location at all times, by using GPS or other means. Other nodes compute their locations by exchanging information with their neighbors. A lower bound on the expected maximum achievable accuracy of range-free localization algorithms was presented in Nagpal et al., 2003. This bound has been widely quoted in the literature and has been extended by Hu and Evans, 2004. In this paper, we show that the previous argument used is incorrect and prove a correct lower bound. We compare our analytical results with measurements from simulation experiments. Finally, we discuss why bounds obtained using this argument may not be tight and how better bounds may be proved.