Routing-Aware Clustering Algorithms for Two-Tiered Sensor Networks

In hierarchical two-tiered sensor networks, higher-powered relay nodes can be used as cluster heads for designing scalable sensor networks. It has been shown that, in such networks, the assignment of sensor nodes to clusters plays an important role in determining the lifetime of the network. In this paper, we have proposed two routing-aware, distributed algorithms for assigning sensor nodes to clusters in two-tiered networks. The first heuristic assumes that all relay nodes, acting as cluster heads, send their data directly to the base station. The second heuristic relaxes this assumption and is to be used with any network where each relay node uses a multihop route to send its data to the base station. Unlike conventional clustering algorithms, our approaches take into consideration the routing scheme used by the relay nodes, and attempt to balance the energy dissipation of the nodes. We have compared the results of our distributed approaches with the optimal solutions obtained using an integer linear program (ILP) formulation, as well as existing techniques, based on heuristics. The results indicate that our approaches, on average, can produce results that are close to the optimal solutions and consistently outperform existing heuristics.