Optimal Tree Pruning for Location Update in Machine-to-Machine Communications

In this paper, we propose a novel energy-and-memory efficient location update scheme for wireless M2M communications. According to information theory, in comparison with periodically registering to the Machine-Type Communications (MTC) server, it is more efficient for a MTC device to perform location updates only when new nodes are added into the corresponding parsing tree. Based on the theory of random walks over trees, we propose optimally pruning the parsing tree to minimize the expected value of the sum of the memory cost and the energy cost for a MTC device. We use both analytical results and simulation results to justify the usage of the proposed scheme.