Breadth-first search tree integrated vertex cover algorithms for link monitoring and routing in wireless sensor networks

Wireless sensor networks (WSNs) are infrastructureless networks of tiny sensor motes which can sense from the environment and can transmit the sensed data through wireless communication. Generally, the transmission ranges of sensor nodes are limited and obstacles are present in the sensing area, so multi-hop communication by utilizing routing protocols is of utmost importance. Since the wireless transmission is prone to vulnerabilities such as eavesdropping and spoofing, monitoring the network traffic by secure points is a critical mission. In this paper, we propose breadth-first search tree (BFST) based vertex cover (VC) algorithms for routing and link monitoring in WSNs. BFST provides a shortest hop routing tree for WSNs and VC is a set of nodes for covering edges (communication links) of the network where it perfectly fits for network traffic monitoring. Unlike most existing algorithms which find minimal VC in a separate procedure, the proposed algorithms construct VC during the BFST establishment phase which leads to lower energy consumption for routing and link monitoring operations. We analyze the correctness proof of the algorithms along with the time, message, space, and bit complexities. We implement the proposed algorithms with their counterparts on a testbed of IRIS motes to evaluate their performances. We find through extensive evaluations from the IRIS testbed experiments and TinyOS simulations that the proposed algorithms find smaller VC sets with up to 3.1 times lower energy consumption than the existing distributed algorithms.