Transactions Papers - Device Placement for Heterogeneous Wireless Sensor Networks: Minimum Cost with Lifetime Constraints

Device placement is a fundamental factor in determining the coverage, connectivity, cost and lifetime of a wireless sensor network (WSN). In this paper, we explore the problem of relay node placement in heterogeneous WSN. We formulate a generalized node placement optimization problem aimed at minimizing the network cost with constraints on lifetime and connectivity. Depending on the constraints, two representative scenarios of this problem are described. We characterize the first problem, where relay nodes are not energy constrained, as a minimum set covering problem. We further consider a more challenging scenario, where all nodes are energy limited. As an optimal solution to this problem is difficult to obtain, a two-phase approach is proposed, in which locally optimal design decisions are taken. The placement of the first phase relay nodes (FPRN), which are directly connected to sensor nodes (SN), is modeled as a minimum set covering problem. To ensure the relaying of the traffic from the FPRN to the base station, three heuristic schemes are proposed to place the second phase relay nodes (SPRN). Furthermore, a lower bound on the minimum number of SPRN required for connectivity is provided. The efficiency of our proposals is investigated by numerical examples.