Title :
AAA: Asynchronous Adaptive Algorithm to solve Max-Flow Problem in wireless sensor networks
Author :
Homayounnejad, S. ; Bagheri, A. ; Ghebleh, A.
Author_Institution :
CEIT, Amirkabir Univ. of Technol., Tehran, Iran
Abstract :
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(n2) time and O(n2 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.
Keywords :
computational complexity; mobile computing; wireless sensor networks; AAA; asynchronous adaptive algorithm; control messages; distributed algorithms; initial gradient; initial values; location-aware wireless sensor networks; max-flow problem; message complexities; push-relabel algorithm; self-stabilizing version; Algorithm design and analysis; Complexity theory; Distributed algorithms; Euclidean distance; Waste materials; Wireless communication; Wireless sensor networks;
Conference_Titel :
MIPRO, 2011 Proceedings of the 34th International Convention
Conference_Location :
Opatija
Print_ISBN :
978-1-4577-0996-8