Block Combination Selection Scheme for Neighbor Discovery Protocol

A neighbor discovery protocol (NDP) is one of the critical research subjects in wireless sensor networks (WSNs) for efficient energy management of sensor nodes. A block design concept can be applied to find a neighbor discovery schedule that guarantees at least one common active slot between any pair of sensor nodes. However, the block design -- based solutions in the literature are not flexible enough because, due to the lack of a general block design scheme, only a limited set of block designs is available for some duty cycles. In this paper, a new approach for the block construction that can easily generate a set of neighbor discovery schedules with a diverse set of duty cycles is introduced. Moreover, we propose a block combination selection scheme (BCS) to choose a near-optimal block combination among the set of candidate schedules. The BCS algorithm first generates set of the candidate block combinations whose duty cycle is similar to the desired duty cycle. Then, from the set of candidates, BCS picks a block combination which has the minimum duty cycle and latency product. In this simulation study, we evaluate the performance of the BCS algorithm and compare it to the performance of other NDPs, such as Random, U-Connect, Disco, and Quorum with a target duty cycle. According to our simulation results, the BCS algorithm always picks the best block combination from the set. If the desired duty cycle is 1%, the block combination selected by BCS performs up to 56.29% better than other NDPs in terms of worst-case latency. In terms of energy consumption, the BCS algorithm performs is 58.8% better than other NDPs.