A Hybrid Approach to Optimize Node Placements in Hierarchical Heterogeneous Networks

In this paper, we address the problem of node placement in a hierarchical heterogeneous wireless sensor network. We consider a two-tiered wireless sensor network where the resource constrained lite nodes (LNs) are used for sensing the environment and high-end sophisticated nodes (SNs) are added to aggregate and forward data. We intend to place minimum number of SNs to handle the traffic generated by LNs and ensure that the SNs form a connected network. We formulate the node placement problem as an optimization problem and use three different algorithms to solve it; namely, binary integer linear programming (BILP), greedy algorithm (GREEDY) and genetic algorithm (GA). We also propose a hybrid approach (HYBRID) combining BILP, GREEDY and GA to improve results. It was found through simulations that GA performed better for random LN deployment. However, using HYBRID, results comparable to original GA could be obtained in only 11.46 % of the time required for the original GA. We support the results with statistical tests.