  We study the network localization problem, i.e., the problem of determining
node positions of a wireless sensor network modeled as a unit disk graph. In an
arbitrarily deployed network, positions of all nodes of the network may not be
uniquely determined. It is known that even if the network corresponds to a
unique solution, no polynomial-time algorithm can solve this problem in the
worst case, unless RP = NP. So we are interested in algorithms that efficiently
localize the network partially. A widely used technique that can efficiently
localize a uniquely localizable portion of the network is trilateration:
starting from three anchors (nodes with known positions), nodes having at least
three localized neighbors are sequentially localized. However, the performance
of trilateration can substantially differ for different choices of the initial
three anchors. In this paper, we propose a distributed localization scheme with
a theoretical characterization of nodes that are guaranteed to be localized. In
particular, our proposed distributed algorithm starts localization from a
strongly interior node and provided that the subgraph induced by the strongly
interior nodes is connected, it localizes all nodes of the network except some
boundary nodes and isolated weakly interior nodes.
