MNP: Multihop network reprogramming service for sensor networks

Reprogramming of sensor networks is an important and challenging problem as it is often necessary to reprogram the sensors in place. In this paper we propose a multihop reprogramming service designed for Mica-2/XSM motes. One of the problems in reprogramming is the issue of message collision. To reduce the problem of collision and hidden terminal problem, we propose a sender selection algorithm that attempts to guarantee that in a neighborhood there is at most one source transmitting the program at a time. Further, our sender selection is greedy in that it tries to select the sender that is expected to have the most impact. We also use pipelining to enable fast data propagation. MNP is energy efficient because it reduces the active radio time of a sensor node by putting the node into "sleep" state when its neighbors are transmitting a segment that is not of interest. Finally, we argue that it is possible to tune our service according to the remaining battery level of a sensor i.e., it can be tuned so that the probability that a sensor is given the responsibility of transmitting the code is proportional to its remaining battery life.