Cactus Graph Design: A Solution for Eliminating Double Counting in Decentralized Sensor Networks

Double counting, or data incest, is a data fusion problem that arises in networks when members (sensors) of a decentralized network are tasked to make estimates based on shared signals. Unknowingly counting the same signals multiple times, due to an inability to keep track of the peer-to-peer signal propagation paths, the network members obtain wrong estimates of the environment, while unnecessarily overusing the network’s time and energy resources. Indeed, energy spent to propagate a signal is at a premium for many real sensor networks, especially in passive surveillance environments, e.g., at sea or in the Arctic. This article proposes a practical communication protocol that avoids double counting by using networks of a topology known as cactus graph topology. We present exact and heuristic cactus network design methods to minimize energy expenditure in disseminating signals. In addition to centralized graph structure traversal algorithms, a decentralized algorithm is presented that is a self-organizing, lightweight cactus network design approach that any placed sensors can adopt at the stage of establishing network-wide communication. The suboptimal, low-computational-expense solutions found with the developed heuristic and decentralized algorithms compare well to the optimal solutions on several test problem instances.