# Secure Localization in the Presence of Colluders in WSNs
## 3 Background, Models and Assumptions  
Let \(\mathcal{K}\) be the complete set of location-known sensor nodes in a WSN. These nodes know their position in the system beforehand. They may be an _anchor_ node (e.g., nodes that were manually configured by operators of the system) or may use a GPS for self-positioning [32; 33] or may have their location computed a priori. Conversely, let \(\mathcal{U}\) be the set of location-unknown sensor nodes that will try to determine their own position in the system by collaborating with other nodes within their communication range. We assume that all the sensor nodes are deployed on a two-dimensional plane. Sensor nodes \(\mathcal{K}\) are assumed to be either truth-tellers (i.e., never intentionally provide false information to neighbours); or _liars_[16] that can intentionally lie about their location in the system. In the presence of liars, exact boundaries about the exact number of location-known neighbours required to correctly conduct the location process exist [16]. For instance, results reported in [27; 28; 29] provide different boundaries with regard to the exact adversary models and robustness of the process. The higher the robustness, the lower number of liars that might be handled by the localization process. The following boundary provides an example under worst case adversaries and highest robustness level:\[\binom{|\mathcal{N}|}{3}>2\left(\binom{\ell}{3}+\binom{|\mathcal{N}|-\ell}{1}\cdot \binom{\ell}{2}+\binom{|\mathcal{N}|-\ell}{2}\cdot\binom{\ell}{1}\right) \tag{1}\]  
where \(|\mathcal{N}|\) is the number of neighbouring nodes of a location-unknown node conducting the process, out of which exactly \(\ell\) nodes are liars. According to the previous function, seven nodes are required in case the number of liars is exactly one (cf. [29] for further details); 11 nodes in the case of two liars; 16 nodes in case of three liars; and so on. Now, in order to address collusion, let \(\mathcal{C}\subset\mathcal{K}\) denote a set of _colluders_ that jointly perpetrate an attack. A location-known node \(C_{i}\in\mathcal{C}\) is not only a _liar_ (i.e., inasmuch as it systematically reports a fake location to other sensor nodes in the network) but can also send out other false information, such as fake lists about its neighbouring nodes. We emphasize, once more, that the presence of such colluders in a WSN invalidates existing solutions for secure localization. **Definition 1**. : _Sensors A and B have bi-directional communication if both A is in B's communication range and A is in B's communication range, as illustrated in Figure 1a. They have no communication if neither A nor B is in the communication range of the other, as illustrated in Figure 1b. They have single direction communication if either only A is in B's communication range or vice versa, as illustrated in Figure 1c._  
We propose an algorithm to allow a sensor \(A\) to obtain its own position in the system and detect colluders that are within its bi-directional communication range despite the presence of these colluders. Such detection requires understanding the nature of threats (jeopardizing the accuracy of the localization process) originating from colluders. Clearly, reducing communications between sensor nodes limits the likelihood of such threats succeeding. Consequently, in our proposed algorithm, the only messages we allow between sensor nodes consist in their coordinates and a series of verification lists (hereafter denotes as _cross-check lists_ or _CCLs_ for short). We do assume periodic exchanges between neighbours (e.g., to exchange routing data) are secured and cannot be attacked. Every node is identified by its coordinates. Authentication (via identity theft) and data integrity may be compromised in a colluding attack. It is important to note that our proposed solution does not rely on any form of authentication nor cryptography. Our solution identifies three categories of colluders. All attacks we consider depend on a corrupted _CCL_ being sent.