Wireless Sensor Networks (WSNs) are vulnerable to clone attacks as they are deployed in hostile and unattended environtments. Also due to the lack of physical tamper-resistance, an adversary can easily capture and compromise sensor nodes and after replicating them, he inserts arbitrary number of clones into network. As a result the adversary is able to mount a wide variety of internal attacks. Several solutions have been proposed in the literature for the detection of these clones from which witness node based distributed solutions have shown satisfactory results. Random Walk (RAWL) is one of the witness node based distributed techniques in which witness nodes are randomly selected by initiating several random walks throughout the network. Although RAWL has achieved high security of witness nodes but in accomplishing high detection probability RAWL suffers from very high communication and memory overhead. In this paper we propose a novel enhancement in RAWL protocol aiming to decrease the communication and memory costs while keeping the detection probability high. Our simulation results show that this improvement in RAWL not only reduces the communication and memory costs but also ensures high security of witness node. © 2015 IEEE.