Optimal Relay Placement for WSN-Based Home Health Monitoring System

Due to the increasing need of health monitoring at home or in senior center, we study the optimal relay node placement problem for wireless sensor networks with data collection and localization requirements. The problem can be modeled as finding a minimum connected k-dominating set. We consider realistic indoor wireless environment and explicitly take into account the effect of obstacles to the radio coverage, instead of using idealistic disc radio model. We prove the problem is NP-hard and thus propose an efficient greedy method called optimal relay placement algorithm (ORPA) to derive the best network setup. Results show that by using the proposed method, the number of relays required can be significantly reduced in comparison to two baseline algorithms. The method presented would be also relevant to similar systems under other network connectivity and relay deployment criteria.