Bioinspired Models of Network, Information, and Computing Systems. 4th International Conference, BIONETICS 2009, Avignon, France, December 9-11, 2009, Revised Selected Papers

Research Article

Minimum Expected *-Cast Time in DTNs

Download229 downloads
  • @INPROCEEDINGS{10.1007/978-3-642-12808-0_10,
        author={Andreea Picu and Thrasyvoulos Spyropoulos},
        title={Minimum Expected *-Cast Time in DTNs},
        proceedings={Bioinspired Models of Network, Information, and Computing Systems. 4th International Conference, BIONETICS 2009, Avignon, France, December 9-11, 2009, Revised Selected Papers},
        proceedings_a={BIONETICS},
        year={2012},
        month={5},
        keywords={DTN social network broadcast multicast anycast},
        doi={10.1007/978-3-642-12808-0_10}
    }
    
  • Andreea Picu
    Thrasyvoulos Spyropoulos
    Year: 2012
    Minimum Expected *-Cast Time in DTNs
    BIONETICS
    Springer
    DOI: 10.1007/978-3-642-12808-0_10
Andreea Picu1,*, Thrasyvoulos Spyropoulos1,*
  • 1: ETH Zürich
*Contact email: Picu@tik.ee.ethz.ch, Spyropoulos@tik.ee.ethz.ch

Abstract

Delay Tolerant Networks (DTNs) are wireless networks in which end-to-end connectivity is sporadic. Routing in DTNs uses past connectivity information to predict future node meeting opportunities. Recent research efforts consider the use of social network analysis (i.e., node communities, centralities etc.) for this forecast. However, most of these works focus on unicast. We believe that group communication is the natural basis of most applications envisioned for DTNs. To this end, we study constrained -cast (broad-, multi- and anycast) in DTNs. The constraint is on the number of copies of a message and the goal is to find the best relay nodes for those copies, that will provide a small delivery delay and a good coverage. After defining a solid probabilistic model for DTNs collecting social information, we prove a near-optimal policy for our constrained -cast problems that minimizes the expected delivery delay. We verify it through simulation on both real and synthetic mobility traces.