Optimal base-station locations in two-tiered wireless sensor networks

Abstract—We consider generic two-tiered Wireless Sensor Networks (WSNs) consisting of sensor clusters deployed around strategic locations, and base-stations (BSs) whose locations are relatively flexible. Within a sensor cluster, there are many small sensor nodes (SNs) that capture, encode, and transmit relevant information from a designated area, and there is at least one application node (AN) that receives raw data from these SNs, creates a comprehensive local-view, and forwards the composite bit-stream toward a BS. This paper focuses on the topology control process for ANs and BSs, which constitute the upper tier of two-tiered WSNs. Since heterogeneous ANs are battery-powered and energy-constrained, their node lifetime directly affects the network lifetime of WSNs. By proposing algorithmic approaches to locate BSs optimally, we can maximize the topological network lifetime of WSNs deterministically, even when the initial energy provisioning for ANs is no longer always proportional to their average bit-stream rate. The obtained optimal BS locations are under different lifetime definitions according to the mission criticality of WSNs. By studying intrinsic properties of WSNs, we establish the upper and lower bounds of maximal topological lifetime, which enable a quick assessment of energy provisioning feasibility and topology control necessity. Numerical results are given to demonstrate the efficacy and optimality of the proposed topology control approaches designed for maximizing network lifetime of WSNs. Index Terms—Network topology, sensor networks, wireless communications, algorithm design, geometric algorithms.