This note examines the problem of finding the position of a device through its relative distance to sensors in a sensor network when some sensors lie. Normally, when there are no faulty sensors, the device needs only to probe 3 nodes (which are not along the same line) to determine its location on a 2D plane, and only to probe 4 nodes (which are not along the same line or along the same plane) to determine its location in 3D space. However, when there are faulty sensors present that lie to the device, the device needs to probe more nodes to obtain correct position information.
In this note, we show that if the number of faulty sensors is N in the sensor network, then the device needs to probe at least 2N+1 sensors to eliminate the effect of the N faulty nodes. We define faulty sensors as ones that deliberately supply wrong distance information to the device in order to convince it of a position that is not the true position of the device. We assume that the faulty sensors may collaborate among themselves to lie in a concerted fashion.
This problem is similar to the “Byzantine General’s Problem” in the sense that the faulty nodes lie to the device, and they lie in a coordinated fashion. However, this problem is “easier” than Byzantine General’s problem because inherent properties of the positioning problem make it easy to detect disagreements between true nodes and faulty nodes. All true nodes must agree on the position of the device. The device only needs 3 or 4 true nodes to determine its location in 2D or 3D space (subject to the constraints that the nodes be not along the same line or along the same plane); but once that is determined, all other true nodes provide distance information that is consistent with the device position, and all faulty nodes provide distance information that is inconsistent. In other words, true nodes and faulty nodes must disagree.
In this problem, faulty nodes may agree among themselves. Thus, simply choosing 3 or 4 nodes to determine a location is not sufficient; all 3 or 4 nodes may belong to the set of faulty nodes. Rather, the device has to make sure that the 3 or 4 nodes it chosen are the true nodes, and the way to determine that is to confirm that the majority of the nodes agree with those 3 or 4 nodes. Since the assumption is that the majority of the nodes are true nodes, if the majority agree with those 3 or 4 nodes, those nodes must be true.
Observation 1. In a sensor network which consists of M+N nodes of which N are faulty and M are not faulty, as long as M > N, a device can determine its correct location.
Proof. Any set of nodes that consist of both faulty and non-faulty nodes will have distance data that are inconsistent. Hence, a device can easily detect whether any given set of nodes (assume the set is > 5 nodes) contain both true nodes and faulty nodes. The only set of M nodes that are consistent among themselves is the set of true nodes. Hence, as soon as the device finds a set of M nodes that are consistent among themselves, the device knows its true location.
In the case where the device doesn’t want to probe all of the nodes in a sensor network to determine its location, this observation says that as long as the device probes at least 2N+1 nodes, where N is the number of faulty nodes in the network, the device can determine its true location.
Algorithm. We propose a randomized algorithm to find the set of true nodes. The device randomly chooses 3 or 4 nodes (depending on whether it’s 2D space or 3D space) to determine a position. It then checks the distance information from the rest of nodes to see if they agree with those 3 or 4 nodes. If the majority of the nodes agree, then the device has the correct location. Otherwise, the device throws away these 3 or 4 nodes and randomly selects another set of 3 or 4 nodes. The process repeats until the device finds the 3 or 4 nodes that yield a position with which the majority of the nodes agree.
Since the algorithm only works if more than half of the nodes in the sensor network are true nodes, the expected number of tries until the device is successful is 8 for 2D space (to find 3 true nodes), and 16 for 3D space (to find 4 true nodes).
Generalization. In any problem where there are true players
and faulty players, as long as there is a way to detect whether a given set of
players consist of true players only or consists of both true and faulty
players, then the effect of the faulty players can always be eliminated as long
as the true players are the majority.
The proof in Observation 1 only depends on the fact that there is an
easy to determine whether any set consists of true players only.