Heuristic algorithm for finding maximal breach path in wireless sensor network with omnidirectional sensors

摘要

Barrier coverage is one of the most crucial issues for quality of service in wireless sensor networks (WSN) and it has been recently emerged as a premier research topic. The barrier coverage can guarantee intrusion detection when mobile objects are entering into the boundary of a sensor field or penetrate into sensor field. There are several penetration paths such as breach, support, exposure and detection. This paper is interested in the maximal breach path, which is specific for a penetrating intruder's safety that corresponds to the worst case coverage. Having known the MBP, network designers could improve the coverage of the networks and maximize the effectiveness of the system. Moreover, MBP provides fundamental background to develop intrusive detection and border surveillance applications. Therefore, in this paper we presents an innovative polynomial time algorithm for computing the MBP for a given sensor network named DBS. The simulation results show that the aforementioned algorithm significantly outperforms an existed one named Megerian's in term of both computational time and consummation.