DocumentCode :
548343
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
fYear :
2011
fDate :
23-27 May 2011
Firstpage :
440
Lastpage :
445
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;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
MIPRO, 2011 Proceedings of the 34th International Convention
Conference_Location :
Opatija
Print_ISBN :
978-1-4577-0996-8
Type :
conf
Filename :
5967097
Link To Document :
بازگشت