Spanning Multi-Tree Algorithms for load balancing in multi-sink Wireless Sensor Networks with heterogeneous traffic generating nodes

Load balancing is a key technique to balance energy consumption, prolong network lifetime and reduce delays in Wireless Sensor Networks (WSNs). In this paper, a Spanning Multi-Tree (SMT) algorithm in multi-sink WSNs with heterogeneous traffic generating nodes is studied. In the SMT algorithm, multiple trees, each rooted from a sink, will be formed in order to cover all sensor nodes in the network for packet forwarding. A branch is a sub-tree parented by a node that is adjacent to a sink. Since every packet will need to pass by one of the sink-adjacent nodes (SANs) in order to reach the sink, it is crucial to balance the total traffic managed by each SAN in order to prolong the network lifetime. In this paper, three heuristic SMT algorithms, namely LargestTraffic-First (LTF), Smallest-Extendibility-First (SEF), and Smallest-Extendibility-First-Smallest-Potentiality-Second (SEF-SPS) are proposed to balance the traffic for each SAN. A simulation based on a scenario of paddy field monitoring with grid network topology and multiple sink nodes is carried out. Theoretical analysis and simulation results show that the proposed algorithms are able to achieve consistent load balancing over various node transmission rates and density.