Relay Node Selection in Randomly Deployed Homogeneous Clustered Wireless Sensor Networks

Extended network life is one of the fundamental objectives in the design of wireless sensor network systems. Clustering protocols help in achieving this objective in an efficient and scalable manner by organizing nodes into small hierarchical groups. In single hop clustering protocols, assumptions are made about direct communication from the cluster heads to the base station. Such assumptions seem strong for realistic situation as the cluster head may have limited radio transmission range in some cases. Relay nodes could be used to leverage additional energy saving through multi-hop transmissions. Moreover, for a randomly deployed homogeneous network, placement of either relays or cluster heads at predetermined locations poses challenges including mobility, location awareness and energy provisioning. In this paper we propose a three-tier architecture for randomly deployed wireless sensor networks without making any assumptions about mobility and placement of nodes at desired locations. We also propose and evaluate heuristic based algorithms for relay node selection. Simulation results demonstrate significant gains in network life time by using the proposed algorithms.