  We study a heterogeneous two-tier wireless sensor network in which N
heterogeneous access points (APs) collect sensing data from densely distributed
sensors and then forward the data to M heterogeneous fusion centers (FCs). This
heterogeneous node deployment problem is modeled as an optimization problem
with the total power consumption of the network as its cost function. The
necessary conditions of the optimal AP and FC node deployment are explored in
this paper. We provide a variation of Voronoi Diagram as the optimal cell
partition for this network and show that each AP should be placed between its
connected FC and the geometric center of its cell partition. In addition, we
propose a heterogeneous two-tier Lloyd algorithm to optimize the node
deployment. Furthermore, we study the sensor deployment when the communication
range is limited for sensors and APs. Simulation results show that our proposed
algorithms outperform the existing clustering methods like Minimum Energy
Routing, Agglomerative Clustering, Divisive Clustering, Particle Swarm
Optimization, Relay Node placement in Double-tiered Wireless Sensor Networks,
and Improved Relay Node Placement, on average.
