Maximal Network Lifetime Scheduling Algorithms for Roadside Sensor Networks: Fid-Bau Portal

Maximal Network Lifetime Scheduling Algorithms for Roadside Sensor Networks

Wan, Xili / Ji, Tingxiang / Guan, Xinjie / Ye, Feng / Li, Yifeng

Roadside sensor networks have been shown its promising application on road surveillance, especially for the roads in the wild which demand a low-cost surveillance method. For a sensor network powered by battery-driven sensors, it is essential to maximize its network lifetime while guaranteeing the coverage requirement for surveillance. Previous work has studied this optimization problem and proposed an optimal sensor scheduling algorithm with the maximum lifetime under the assumption that the road can be abstracted to a line. This assumption simplified the problem but is not practical. We study the maximum network lifetime scheduling problem by abstracting the road to a two-dimensional rectangle rather than a one-dimensional line. Moreover, this problem is transformed into a maximum network flow problem by constructing an auxiliary graph. Then two efficient polynomial algorithms are proposed based on flow decomposition techniques and heuristics methods. Simulation are done to further show the performance of the developed algorithms.