An Efficient Asynchronous Probing Scheme (EAPS) is proposed to solve issues of the low discovery radio and high probing energy cost for Delay Tolerant Mobility Sensor Network (DTMSN). By analyzing nodes contact properties in the Random Way-Point (RWP) mobility model, EAPS gives a reasonable regional plan based on a slotted-wakeup schedule of coprime cycle pairs. Optimal coprime cycle pairs are selected in these different regions to improve the discovery radio and reduce energy cost. Comparing with past asynchronous probing schemes, simulation results show that EAPS has higher discovery ratio and lower discovery delay with a low energy cost.