The invention provides a vehicle pseudonym replacement method, device and computer-readable storage medium. The method includes that when the vehicle enters the vehicle-mounted self-organizing network, a trusted third party registers the vehicle to obtain a pseudonym and a certificate; the trusted third party registers the base station and the roadside unit to obtain a public key and a private key, and the base station calculates an effective The public key of the base station; when the vehicle enters the signal coverage of the roadside unit, the vehicle and the roadside unit confirm each other's legitimacy; the vehicle applies to the base station through the roadside unit, and obtains a valid pseudonym, certificate and Base station key; if the vehicle is in a driving state, the vehicle will periodically broadcast basic security messages, and pseudonyms will be replaced according to the driving state of nearby vehicles. In this way, without the participation of RSU, the legal pseudonym certificate can be independently calculated through cooperation with the surrounding vehicles; the vehicle can independently judge the conditions of pseudonym change, and enhance the security of the subsequent pseudonym replacement protocol.