In the matter of detecting clone attacks, we bring in a novel solution called Single Stage Memory Random Walk with Network Division (SSRAND) to circumvent the problems of simple random walk as exploited by both RAND and RAWL protocols. SSRAND combines the single stage memory random walk with network division for clone detection and simulation results verify that it not only reduces the communication and memory costs but also ensures high security of witness nodes with increased detection probability of clones. © 2014 IEEE.