Finding the polygon hull in wireless sensor networks

Finding the border of a wireless sensor network (WSN) is one of the most important issues today. This border can be used, for example, to monitor a frontier or a secured place of sensitive sites of a country. One of the methods that can be useful for this kind of problems is Jarvis algorithm which has to be adapted to take account of connected nodes in a Euclidean graph. For this kind of networks, the complexity is reduced from O(nh) to O(kh2), where n is the number of sensors, k is the maximum number of neighbors of a sensor in the network and h is the number of sensors of the envelope. The application of this algorithm to WSNs allows in each iteration to determine the next boundary neighbor of the current node. The advantage of this procedure is that each node knows its neighbor in a single operation. Then, each boundary node will periodically send a message to its neighbor, which should respond. If a response is not received, a situation of failure or intrusion will be triggered and network restructuring will be launched to find a new border. In this work, we have shown that the application of this algorithm in the presence of sub-absorbent graphs can lead to an infinite loop situation. We have also shown how to overcome this situation and how the algorithm can be applied to the case of WSNs.