The traditional approach to measure the efficiency of a (static) coverage task is the ratio of the intersection of the areas covered by sensors, to the total free space in the environment. Here we address the dynamic coverage problem, which requires all areas of free space in the environment to be covered by sensors in as short a time as possible. We introduce a frequency coverage metric that measures the frequency of every-point coverage, and propose a decentralized algorithm that utilizes locally available information about the environment to address this problem. Our algorithm produces exploratory, patrol-like behavior. Robots deploy communication beacons into the environment to mark previously visited areas. These nodes act as local signposts for robots which subsequently return to their vicinity. By deploying such (stationary) nodes into the environment robots can make local decisions about their motion strategy. We analyze the proposed algorithm and compare it with a baseline approach - a modified version of a static coverage algorithm described in our previous work.