# Detection of Intelligent Intruders in Wireless Sensor Networks
## 3 Intrusion Algorithms
### Flood-Fill Intrusion Algorithm  
The pinball algorithm simply avoids collisions by bouncing off nearby sensors detected within its sensing range \(I_{rs}\). It does not estimate the cost to the destination for each state or efficiently store-and-update environment information with backtracking costs. In other words, while a pinball intruder can efficiently avoid sensor detection, it may become stuck or time-out inside the WSN FoI, _i.e._, it may not be able to reach the destination in a timely manner. In most WSN applications, an intruder's primary goal is to safely traverse the WSN FoI and to arrive at its destination within a certain time. Hence, we propose a flood-fill intrusion algorithm that integrates environment learning, map building, updating, backtracking and path replanning for detection avoidance and timely destination arrival. Different from the traditional flood-fill algorithms for maze-solving problems that require full prior knowledge of the environment, our proposed flood-fill algorithm assumes no prior knowledge of the WSN FoI. Instead, the flood-fill algorithm involves dividing the WSN FoI into a virtual \(m*m\) grid map, and all cells in the map are initially \"empty\", which represents no prior knowledge of the WSN FoI, as illustrated in Figure 3. The algorithm attempts to update the status of the cells by measuring and updating the WSN FoI status in terms of \"safe\" or \"unsafe\" and utilizes the learning information to direct the next move, until reaching the destination or experiencing a time-out. To start the algorithm, the intruder will choose a start position on the left extended periphery and a target position on the right extended periphery and will restrict all movements to the virtual grid, _i.e._, move from the center of one cell to the next one. On each move, as illustrated in Figure 3, the intruder must check its adjacent cells and update the cell values in the map to represent their sensing coverage status and the status of \"visits\". To be specific:  
* If a cell \(c_{i}\) is fully or partially covered by a detected sensor within \(r_{s}\), then the cell receives a value of \(-1\). Assume \(c(x_{i},y_{i})\) and \(s(x_{j},y_{j})\) are the locations of the cell \(c_{i}\), and the detected sensor \(s_{j}\). Cell \(c_{i}\) will be considered as \"unsafe\" and receive a value of \(-1\) if \(\sqrt{(x_{i}-x_{j})^{2}+(y_{i}-y_{j})^{2}}<r_{s}+\sqrt{2}/2\). Otherwise, cell \(c_{i}\) is considered \"safe\" and receives a value of zero. * For a safe cell with a value of zero, the value will be incremented by one each time the intruder visits it. For instance, a cell with a value of three means the cell is visited by the intruder three times. This is because the intruder might have to backtrack under certain conditions. During traversal, while the intruder has not reached its target position or experienced a time-out and when it comes to make a move, it will check all cells adjacent to it to see which one is should head to next. More specifically:  
* If a cell adjacent to the intruder has not been visited by the intruder before, it will check to see its coverage status first. Once the intruder has checked all adjacent cells, the intruder will proceed in the direction of the cell with the lowest value. * If multiple cells have the same value, the intruder will decide which direction to move based on the distance from each cell to its target position. For example, if the intruder needs to travel six units along the \(x\)-axis and three units along \(y\)-axis to reach its target position, it will first attempt to travel along the \(x\)-axis. * If that cell is not amongst those with the lowest value, then the intruder will go clockwise, checking the other cells for the lowest value, and will travel along the direction of the first lowest value cell it finds. Before the intruder leaves a cell, it will increment the value of that cell by one. The pseudocode of the flood-fill intrusion algorithm is shown in Algorithm 2.