Designing hierarchical sensor networks with mobile data collectors

In this paper we have investigated the design of a multi-tier architecture for sensor networks that includes higher-powered relay nodes, and a mobile data collector (MDC). We have presented a new Integer Linear Program to determine a placement scheme for the relay nodes that (i) ensures that each sensor node can communicate with at least one relay node, using as few relay nodes as possible, and (ii) computes a “shortest length” trajectory of the MDC. We have also investigated, using a new heuristic for the Traveling Salesman Problem with Neighborhood (TSPN), the possibility of further reducing the MDC trajectory length by finding, for each relay node, a suitable point in its neighborhood to be visited by the MDC, while guaranteeing some feasible network lifetime.