Joint Clustering and Optimal Cooperative Routing in Wireless Sensor Networks

Node cooperation is one unique feature distinguishing wireless sensor networks (WSNs) from traditional wireless cellular networks. In this paper, we investigate joint clustering and optimal cooperative routing, where neighboring nodes dynamically form coalitions and cooperatively transmit packets to the next hop destination. We show that the cooperative sensor network can be modeled as an edge-weighted graph, based on which minimum energy cooperative routing is characterized by using the standard shortest path algorithm. We then focus on energy-delay-constrained maximum throughput routing, which is known to be NP-hard. We study two interesting cases: (1) For the case where the delay can be expressed in terms of the number of hops, we use the bi-section method to find the maximum throughput routing; (2) For large scale networks where the end-to-end delay can be approximated as the product of the number of hops and the average one-hop delay, we present a polynomial time algorithm to find the maximum throughput routing. Our numerical results confirm that the energy efficient cooperative routing can enhance the performance of WSNs significantly.