On Sleep-wakeup Scheduling of Non-penetrable Barrier-coverage of Wireless Sensors

Abstract—This paper identifies a new security problem of existing scheduling algorithms for barrier-coverage of sensors, which never considered before. A barrier-cover of wireless sensors is a subset of sensors seamlessly spanning between two opposite sides such that no intruder can move from one side to the other without being detected. The goal of the scheduling algorithms is to find a sleep-wakeup schedule of sensors such that the time to protect an area of interest using a series of alternating barrier-covers can be maximized. We introduce a new security problem which may exist when two barrier-covers, whose covered areas are not completely disjoint, alternate. We show how an intruder can utilize a set of points, namely “barrier-breaches”, to penetrate the alternating barrier-covers. We also propose two remedies for this problem for existing scheduling algorithms. Our analysis shows that depending on the input graph, one of our approaches works better than the other. Given that such scheduling algorithms only need to run during the initialization phase of a sensor network, we suggest to apply both approaches and pick the better schedule rather than relying solely on the approach which works well on average. Index Terms—Barrier coverage, wireless sensor network, max-imum lifetime, scheduling, network security, barrier-breach I