Telematic device with multiple subscriber identity modules (SIMs). The telematic device may execute software that, when establishing a new connection, executes a battery-saving algorithm. The algorithm may comprise, in each of one or more iterations, attempting to connect to a wireless communication network via a cellular communications interface using a SIM profile. When the attempt fails, the algorithm determines whether or not the telematic device is being powered by a battery. When the telematic device is not being powered by the battery, a retry interval is adjusted according to a first back-off scheme. On the other hand, when the telematic device is being powered by the battery, the retry interval is adjusted according to a second back-off scheme (e.g., which is more aggressive than the first back-off scheme to conserve the battery). The algorithm then waits for a duration indicated by the retry interval before the next iteration.