Mobile-Health (M-Health) system is a growing field that enables physicians to monitor remote patients’ health status and facilitates the sharing of medical records among medical service providers. Most existing schemes mainly focus on security and privacy. However, these schemes may not work well in M-Health scenarios. For instance, the system may consume lots of time for an intended user equipment (UE) to verify a large number of signatures sequentially. To reduce the computational overhead of intended UE, we propose a batch verification scheme using distributed computing in the improved secure data transmission protocol based on D2D (SDTP). In this paper, when the NM is not available, this case still guarantees normal communication process by applying back-up solution. In addition, if a signature is disputed, the malicious user can be traced by NM or by Shamir’s (t,n) secret share scheme from the disputed signature. Besides, we give a specific D2D communication establishment process. Performance analysis and evaluation further prove to be effective for proposed scheme with regard to its privacy, security, availability, computation complexity, and communication cost.