Average Case Network Lifetime on an Interval with Adjustable Sensing Ranges

Given n sensors on an interval, each of which is equipped with an adjustable sensing radius and a unit battery charge that drains in inverse linear proportion to its radius, what schedule will maximize the lifetime of a network that covers the entire interval? Trivially, any reasonable algorithm is at least a 2-approximation for this Sensor Strip Cover problem, so we focus on developing an efficient algorithm that maximizes the expected network lifetime under a random uniform model of sensor distribution. We demonstrate one such algorithm that achieves an expected network lifetime within 12 % of the theoretical maximum. Most of the algorithms that we consider come from a particular family of RoundRobin coverage, in which sensors take turns covering predefined areas until their battery runs out.