Biologically-Inspired Construction of Connected k-Hop Dominating Sets in Wireless Sensor Networks

Connected k-hop dominating sets (CkDS) have various applications in wireless sensor networks. They are for example used to alleviate the broadcast storm problem or to achieve an adjustable amount of area coverage while maintaining connectivity. In this paper, we propose a novel protocol for the construction of CkDS in wireless sensor networks drawing inspiration from the flight behavior of ovipositing Pieris rapae, which has several properties that are beneficial for our artificial system. Our protocol is self-organizing since a global-level pattern, the CkDS, emerges solely from numerous lower-level interactions specified by rules executed using only local information, without reference to the global pattern. It consists of two intertwined behavior blocks, which are both essentially based on random walks: the first is responsible for the construction of a k-hop dominating set, while the second connects the existing fragments of dominating nodes to a connected k-hop dominating set. We conducted extensive simulations to evaluate the efficiency as well as other properties, such as scalability, of our protocol and to compare it to a recently proposed state-of-the-art CkDS construction protocol.