Average Case Network Lifetime on an Interval with Adjustable Sensing Ranges

作者：Bar Noy Amotz; Baumer Ben^*

来源：Algorithmica, 2015, 72(1): 148-166.

DOI：10.1007/s00453-013-9853-5

• Wireless sensor networks
• Adjustable range
• Restricted strip cover
• Lifetime
• Area coverage
• Barrier coverage

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.

• 出版日期2015-5