Mobile computing brings new challenges and requirements for checkpointing and recovery protocol. Existing checkpointing-only schemes can not guarantee the independent recovery through creating global consistent checkpoints. Message logging schemes based on mobile-MSS-mobile communication that exchanges messages among mobile hosts may incur large contention on the wireless network and high latency for message transmission relative to the direct mobile host to mobile host (m-m) communication. This paper presents a novel recovery protocol for m-m communication, in which two key problems, message order and duplicate message, are effectively solved. A proof of the protocol correctness is also given. Finally, simulation results indicate that the performance of the proposed approach is better than that of the traditional approaches in terms of fail-free and recovery overhead.