Relative localization for wireless sensor networks with linear topology

Sensors can be deployed along a road or a bridge to form a wireless sensor network with a linear topology where nodes have a spatial ordering. This spatial characteristic indicates relative locations for nodes and facilitates such functions as object tracking and monitoring in the network. We attempt to derive this ordering with RSSI (Received Signal Strength Indicator) as the only input, which does not require attaching extra hardware to the sensor nodes. This requires a method for translating RSSI into spatial constraints. There are two candidate methods in the literature. The first method uses connectivity information among the nodes to calculate their relative locations. But analysis of real-world trace data indicates that it does not work well in reality. The second method assumes that closer nodes receive higher RSSI. However, we have proved that the relative localization problem is actually NP-hard under such an assumption. Fortunately, the problem turns out to be efficiently solvable if we adopt a new observation slightly different from the above-mentioned closer-higher RSSI assumption. This observation that the closest node always receives the highest RSSI is verified by the analytical results of the same real-world trace data. We then propose a spatial ordering method based on the observation, and evaluate it through various field experiments. Results show that the proposed method achieves an accuracy of over 99%99%.