AAA: Asynchronous Adaptive Algorithm to solve Max-Flow Problem in wireless sensor networks

In this paper we propose a push-relabel algorithm to solve the Max-Flow Problem (MFP) in location-aware wireless sensor networks (WSNs). This algorithm is based on the push-relabel method and uses the location of nodes and their radio ranges to make an initial gradient in the network by assigning initial values to the height of the nodes. We prove the correctness of the algorithm which finds max-flow in O(n²) time and O(n² m) message complexities, in which n and m are the number of nodes and links respectively. Furthermore, a self-stabilizing version of the algorithm has been proposed which adapts the max-flow to the network changes. Simulation results show that this algorithm improves existing distributed algorithms significantly and reduces the number of control messages around 32% in compare with generic push-relabel algorithm.