Delegation forwarding

Abstract

Mobile opportunistic networks are characterized by unpre- dictable mobility, heterogeneity of contact rates and lack of global information. Successful delivery of messages at low costs and delays in such networks is thus challenging. Most forwarding algorithms avoid the cost associated with flood- ing the network by forwarding only to nodes that are likely to be good relays, using a quality metric associated with nodes. However it is non-trivial to decide whether an encountered node is a good relay at the moment of encounter. Thus the problem is in part one of online inference of the qual- ity distribution of nodes from sequential samples, and has connections to optimal stopping theory. Based on these ob- servations we develop a new strategy for forwarding, which we refer to as delegation forwarding. We analyse two variants of delegation forwarding and show that while naive forwarding to high contact rate nodes has cost linear in the population size, the cost of delegation for- warding is proportional to the square root of population size. We then study delegation forwarding with different metrics using real mobility traces and show that delegation forward- ing performs as well as previously proposed algorithms at much lower cost. In particular we show that the delegation scheme based on destination contact rate does particularly well.