Efficient Routing in the CityMesh Decentralized Fallback Wireless Network

Abstract

As modern communication systems increasingly rely on centralized network infrastructure, they become more vulnerable to disruptions caused by disasters, failures, or cyberattacks. To address this risk, CityMesh proposes a decentralized fallback wireless network that leverages existing Wi-Fi devices, such as access points (APs), in buildings to maintain essential connectivity during outages. However, achieving scalable and reliable message delivery in such a network, without introducing excessive overhead, poses significant challenges. This thesis presents a new routing protocol for CityMesh, designed to operate efficiently at city scale. We first identify the limitations of traditional shortest-path source routing in CityMesh’s context, including the use of unreliable links and overhead from redundant transmissions. To address these issues, we introduce a safer path selection metric that prioritizes link reliability, a waypoint-based routing compression scheme, and a conduit mechanism to increase robustness to local failures. Our protocol further supports compact routing tables through a grid-based addressing scheme, enabling constant-size packet headers and scalable routing decisions. Additionally, we propose a suppression strategy to reduce unnecessary transmissions both between and within buildings. Finally, we extend our approach to reconnect disconnected network segments by formulating a relay placement strategy based on map data and geometric heuristics. Additionally, to reconnect fragmented network segments, we develop a practical relay placement algorithm by leveraging on the convex hull optimization and re-using global map knowledge, which ensures fast relay point computation in feasible locations such as roads and bridges. Simulations across 20 global cities show that our routing protocol achieves up to 2× higher packet delivery rates and reduces transmission overhead by up to 28× compared to GPSR under high packet loss and realistic localization error. The routing table footprint sampled across 4 randomly selected cities shows on average under 2 KB memory usage per device. Our fast relay placement algorithm also demonstrates only a small number of relays are needed to achieve full network connectivity for most of the cities, which validates CityMesh’s core premise that existing urban Wi-Fi infrastructure is sufficient to support a robust, scalable decentralized fallback network with minimal augmentation.