Boundary mapping and its application to geographic routing
Colin Lemmon · ResearchOnline - JCU (James Cook University) · 2023
Geographic routing is a self organizing, low overhead, distributed system for routing in ad-hoc wireless networks. Practical application of this approach is limited due to the lack of global information to deal with local minima at voids or the outer boundary. To address this problem, an improved geographic forwarding strategy Greedy-BoundedCompass was developed to reduce the instance of local minima. Greedy-BoundedCompass allows packets to move away from the destination without looping in situations where Greedy forwarding would fail. Greedy-BoundedCompass was applied to Greedy Perimeter State Routing (GPSR) to confirm its effectiveness as an alternate forwarding strategy. The Boundary Mapping Protocol (BMP) was then developed to detect local minima, and probe boundaries; handling branches, edge crossovers, detecting probe home, and boundary confirmation. Using BMP, a multi-strategy Boundary State Routing protocol (BSR) was developed which incorporated Greedy-BoundedCompass forwarding. BSR manages boundary exit points, path selection for boundary traversal, swapping of boundaries, and loop prevention with multimode strategies. In response to performance issues, a low resolution grid occupancy mapping system was developed as a replacement for BMP to address excessive probe overhead and memory requirements. Implementation, testing, and analysis of the improved geographic routing strategies were performed using a purpose built network simulator. Metrics used included path completion rate, route efficiency, control overhead, and memory requirements. Greedy-BoundedCompass reduced the number of local minima, improving the path completion rate of Greedy forwarding by 49.2% in sparse networks with a significant improvement in route efficiency of 8.9%. Greedy-BoundedCompass applied as a replacement for Greedy forwarding in GPSR also demonstrated a significant improvement in route efficiency. BSR then demonstrated a significant improvement in route efficiency over improved GPSR of 46.1% in sparse networks. The alternate low resolution grid occupancy mapping demonstrated a significant reduction in probe overhead and memory requirements compared to BMP. Greedy-BoundedCompass forwarding has application in existing geographic routing protocols. BSR along with the low resolution grid occupancy mapping system is a promising approach to geographic routing with minimal local information maintained for routing around local minima. Future research will focus on refining the proposed grid occupancy mapping system and dealing with mobility.