Distributed hole-bypassing protocol in WSNs with constant stretch and load balancing

Geographic routing has been widely used in wireless sensor networks because of its simplicity and efficiency resulting from its local and stateless nature. However, when subjected to routing holes (i.e., regions without sensor nodes that have communication capability), geographic routing suffers from the so-called local minimum phenomenon, where packets are stopped at the hole boundary. This local minimum phenomenon results in problems of load imbalance (i.e., a higher traffic intensity around the hole boundary) and routing path enlargement due to the long hole detour paths. Although several protocols have been proposed to address these issues, the load imbalance problem has not been solved thoroughly, and none of the existing protocols can solve both of these problems. In this article, we propose a distributed hole-bypassing routing protocol named ACOBA (Adaptive forbidden area-based COnstant stretch and load BAlancing), which can solve the load imbalance problem thoroughly while ensuring the constant stretch property of the routing path. Our theoretical analysis proves that the routing path stretch of the proposed protocol can be controlled to be as small as 1+ϵ (for any predefined ϵ > 0), and the simulation experiments show that our protocol strongly outperforms state-of-the-art protocols in terms of load balancing.