Timely data delivery in a realistic bus network
Timely data delivery in a realistic bus network
复制标题
DOI：
10.1109/infcom.2011.5935201
复制
发表时间：
2011-04
期刊：
影响因子：
--
通讯作者：
Utku Günay Acer;Paolo Giaccone;David Hay;Giovanni Neglia;Saed Tarapiah
中科院分区：
文献类型：
--
作者：
Utku Günay Acer;Paolo Giaccone;David Hay;Giovanni Neglia;Saed Tarapiah
启用WiFi的公交车和车站可以形成大都市延迟容忍网络的骨干，该网络利用附近的通信、车站处的临时存储以及可预测的公交车移动性来传递非实时信息。本文研究了在给定的截止日期内，如何将数据从源路由到目的地，以使数据的投递概率最大化。我们假设知道公交时刻表，但我们考虑到由于道路交通状况或乘客上下车的随机性，影响公交车的流动性。我们提出了一个简单的随机模型，公交车到达车站，在一个大型的城市网络中收集的真实生活中的痕迹的研究支持。一个简洁的图形表示这个模型允许我们设计一个最佳的（根据我们的模型）单副本路由算法，然后将其扩展到允许相同数据的多个副本的情况。通过广泛的模拟研究，我们比较了最优路由算法与其他三种方法：最小化我们的图的预期遍历时间，最小化一个数据包可以旅行的跳数，以及最近提出的基于总线频率的启发式。我们的最优算法优于所有这些算法，但大多数时候，它本质上减少到最小化预期的遍历时间。对于接近预期交付时间的最后期限值，多副本扩展只需要10个副本就可以达到几乎昂贵的泛洪方法的性能。
WiFi-enabled buses and stops may form the backbone of a metropolitan delay tolerant network, that exploits nearby communications, temporary storage at stops, and predictable bus mobility to deliver non-real time information. This paper studies the problem of how to route data from its source to its destination in order to maximize the delivery probability by a given deadline. We assume to know the bus schedule, but we take into account that randomness, due to road traffic conditions or passengers boarding and alighting, affects bus mobility. We propose a simple stochastic model for bus arrivals at stops, supported by a study of real-life traces collected in a large urban network. A succinct graph representation of this model allows us to devise an optimal (under our model) single-copy routing algorithm and then extend it to cases where several copies of the same data are permitted. Through an extensive simulation study, we compare the optimal routing algorithm with three other approaches: minimizing the expected traversal time over our graph, minimizing the number of hops a packet can travel, and a recently-proposed heuristic based on bus frequencies. Our optimal algorithm outperforms all of them, but most of the times it essentially reduces to minimizing the expected traversal time. For values of deadlines close to the expected delivery time, the multi-copy extension requires only 10 copies to reach almost the performance of the costly flooding approach.