A Bounding Box Overlay for Competitive Routing in Hybrid Communication Networks

摘要: We present a new approach for competitive geometric routing in wireless ad hoc networks. design strategy that finds c-competitive paths positive constant c: i.e., which have length at most c times the of shortest path. It is well-known this cannot be achieved by online strategies only consider local neighborhood node their decisions [17]. The main difficulty uncovered regions within network, we denote as radio holes. Complex shapes holes, example zig-zag-shapes, make difficult: forwarded messages direction to destination might get stuck dead end or could routed along very long detours. To able find paths, additional knowledge about position and shape holes needed. In order gather efficiently, use hybrid network approach. This assumes can not just but also some cellular infrastructure, used underlying network. Communication via infrastructure incurs costs cell phone providers are involved. Therefore, compute actual data transmission takes place good aim computing an abstraction abstracted bounding boxes. advantage boxes hole number nodes per hole. prove suitable allows us case non-intersecting intersecting boxes, show simulations our significantly outperforms so far best Finally, pairwise