Machine-to-machine (M2M) communication is one of the critical technologies of the industrial Internet of Things (IoT), which consists of sensors, actuators at the edge, and servers. In order to solve the security and availability problems regarding communication between edge devices with constrained resources and servers in M2M communication, in this study we proposed an authentication and session establishment protocol based on physical unclonable functions (PUFs). The scheme does not require clock synchronization among the devices, and it circumvents the situation where the authentication phase has to use a high computational overhead fuzzy extractor due to PUF noise. The protocol contains two message interactions, which provide strong security and availability while being lightweight. The security modelling is based on CPN Tools, which verifies security attributes and attack resistance in the authentication phase. After considering the design of the fuzzy extractor and scalability, the proposed scheme significantly reduces the computational overhead by more than 93.83% in the authentication phase compared with other schemes using PUFs. Meanwhile, under the guarantee of availability, the communication overhead is maintained at a balanced and reasonable level, at least 19.67% lower than the solution using XOR, hashing, or an elliptic curve.