We study the time complexity of data collection in sensor networks. A simple mathematical model for sensor networks regarded as lines, multi-lines and trees is defined and corresponding optimal schedules are provided. A lower bound of data collection time on general graph networks is also derived. Furthermore, we discuss the data collection problem where each node can transmit arbitrary hops per time slot. An optimal schedule is derived where each node can transmit 2 hops. We also prove the schedule is nearly optimal if each node can transmit k (k > 2) hops (with constant error).
展开▼