Anonymous communication methods, try to prevent traffic analysis attacks by hiding nodes' identities from outside observers. As a result, adversaries can not find any correlation between observed traffic patterns and nodes? real information. In this paper, we have introduced PseudoAODV protocol in which origin identifiers of nodes are replaced by randomly generated pseudonyms in Ad hoc On Demand Distance Vector (AODV) routing scheme. The main contribution of our protocol is improving AODV to provide sender/recipient and relationship anonymity with the least computational overhead. Simulation results shows the lower imposed overhead of our method in comparison with similar protocols.