Hybrid Routing in Wireless Networks with Diverse Connectivity

Real world wireless networks usually have diverse connectivity characteristics. Although existing works have identified replication as the key to the successful design of routing protocols for these networks, the questions of when the replication should be used, by how much, and how to distribute packet copies are still not satisfactorily answered. In this paper, we investigate the above questions and present the design of the Hybrid Routing Protocol (HRP). We make a key observation that delay correlations can significantly impact performance improvements gained from packet replication. Thus, we propose a novel model to capture the correlations of inter-contact times among a group of nodes. HRP utilizes both direct delays feedback and the proposed model to estimate the replication gain, which is then fed into a novel regret-minimization algorithm to dynamically decide the amount of packet replication under unknown network conditions. We evaluate HRP through extensive simulations. We show that HRP achieves up to 3.5x delivery ratio improvement and up to 50% delay reduction, with comparable and even lower overhead than state-of-art routing protocols.