Minimum number oriented relay node deployment algorithm in two-tiered WSN

Abstract

Aiming at minimizing the number of relay nodes distributed in the sensing area while keeping the feasible communication with at least one relay node for every sensor node, two algorithms (i.e. the integral linear programming optimal algorithm and the heuristic algorithm) were proposed. First, the integral linear programming optimal algorithm was designed to find the best region of deploying rela nodes within candidate regions through integer linear program-ming. In the large-scale wireless sensor network, the heuristic algorithm was proposed that found the best deployment re-gion through iteratively updating the deployment area luding the most relay nodes. Finally, simulation results show that the two proposed algorithms can minimize the number of relay nodes needed with the guarantee of serving all sensor nodes.

Keywords

• relay nodes
• deployment algorithm
• integer linear programming
• heur ic algorithm
• node coverage