Semi-Markovian State Estimation and Policy Optimization for Energy Efficient Mobile Sensing

User context monitoring onmobile devices benefits end-users by providing information support to various kinds of mobile applications. A pervasive question, however, is how the sen-sors on the mobile device could be scheduled energy effi-ciently without sacrificing too much detection accuracy. In this paper, we formulate the user state sensing problem as the intermittent sampling of a semi-Markov process, a model that provides general and flexible capturing of realistic data. Assuming sensors make perfect detections, we propose (a) a semi-Markovian state estimation mechanism that selects the most likely user state while observations are missing, and (b) a semi-Markov optimal sensing policy u∗s which min-imizes the expected state estimation error while maintain-ing a given energy budget. Their performance are shown to significantly outperform Markovian algorithms [29] on simulated two-state processes and real user state traces. Fi-nally, we propose a novel client-server based energy efficient mobile sensing system architecture that automatically learns user dynamics and computes user-specific optimal sensing policy for mobile devices. A system prototype aiming to rec-ognize basic human activity is implemented on Nokia N95 smartphones and desktop computers. We demonstrate the performance benchmark of u∗s through a set of experiments, and show that it improves the estimation accuracy by 27.8% and 48.6 % over Markov-optimal policy and uniform sam-pling, respectively. 1