Energy Efficient Multi-Hop Polling in Clusters of Two-Layered Heterogeneous Sensor Networks

In this paper we study two-layered heterogeneous sensor networks where two types of nodes are deployed in the network: basic sensor nodes and cluster head nodes. Basic sensor nodes are simple and inexpensive, while cluster head nodes are much powerful and much richer in energy. A cluster head node organizes the basic sensor nodes around it into a cluster. A basic sensor node does data collections and sends the data packets when polled by the cluster head. By introducing hierarchy, such a two-layered heterogeneous sensor network has better scalability than homogeneous sensor networks. It also has a smaller overall cost since networking functionalities are shifted from sensors to the cluster head. It also has a longer life time, as sensors send packets only when polled by the cluster head and less energy is consumed in collisions and idle listening. This type of network will be ideally suited for applications such as environmental monitoring. In this paper, we focus on finding energy efficient and collision-free polling schedules in the multi-hop cluster. To reduce energy consumption in idle listening, a schedule is optimal if it uses minimum time. We show that the problem of finding an optimal schedule is NPhard, and then give a fast on-line algorithm. We also consider dividing a cluster into sectors to further reduce the idle listening time of sensors. We conducted simulations on the NS-2 simulator, and the results show that our polling scheme can reduce the active time of sensors by a significant amount while sustaining 100% throughput.