AI Chat Paper
Note: Please note that the following content is generated by AMiner AI. SciOpen does not take any responsibility related to this content.
{{lang === 'zh_CN' ? '文章概述' : 'Summary'}}
{{lang === 'en_US' ? '中' : 'Eng'}}
Chat more with AI
PDF (2.3 MB)
Collect
Submit Manuscript AI Chat Paper
Show Outline
Outline
Show full outline
Hide outline
Outline
Show full outline
Hide outline
Open Access

DAWN: A Density Adaptive Routing for Deadline-Based Data Collection in Vehicular Delay Tolerant Networks

Department of Electronic Engineering, Tsinghua University, Beijing 100084, China
Ming Hsieh Department of Electrical Engineering, University of Southern California, Los Angeles, CA 90089, USA
Show Author Information

Abstract

Vehicular Delay Tolerant Networks (DTN) use moving vehicles to sample and relay sensory data for urban areas, making it a promising low-cost solution for the urban sensing and infotainment applications. However, routing in the DTN in real vehicle fleet is a great challenge due to uneven and fluctuant node density caused by vehicle mobility patterns. Moreover, the high vehicle density in urban areas makes the wireless channel capacity an impactful factor to network performance. In this paper, we propose a local capacity constrained density adaptive routing algorithm for large scale vehicular DTN in urban areas which targets to increase the packet delivery ratio within deadline, namely Density Adaptive routing With Node deadline awareness (DAWN). DAWN enables the mobile nodes awareness of their neighbor density, to which the nodes’ transmission manners are adapted so as to better utilize the limited capacity and increase the data delivery probability within delay constraint based only on local information. Through simulations on Manhattan Grid Mobility Model and the real GPS traces of 4960 taxi cabs for 30 days in the Beijing city, DAWN is demonstrated to outperform other classical DTN routing schemes in performance of delivery ratio and coverage within delay constraint. These simulations suggest that DAWN is practically useful for the vehicular DTN in urban areas.

References

[1]
Z. Zhang, Routing in intermittently connected mobile ad hoc networks and delay tolerant networks: Overview and challenges, IEEE Communication Surveys and Tutorials, vol. 8, no. 1, pp. 24-37, 2006.
[2]
J. Burgess, B. Gallagher, D. Jensen, and B. Levine, Maxprop: Routing for vehicle-based disruption-tolerant networking, in Proc. IEEE INFOCOM, Barcelona, Spain, 2006, pp. 1-11.
[3]
T. Spyropoulos, K. Psounis, and C. Raghavendra, Efficient routing in intermittently connected mobile networks: The multi-copy case, IEEE/ACM Trans. Networking, vol. 16, no. 1, pp. 77-90, 2008.
[4]
Z. Jin, J. Wang, S. Zhang, and Y. Shu, Epidemic-based controlled flooding and adaptive multicast for delay tolerant networks, in Proc. 7th International Conference on Ubiquitous Intelligence and Computing and 7th International Conference on Autonomic and Trusted Computing (UIC/ATC), Xi’an, China, 2010, pp. 191-194.
[5]
M. Mcmahon and S. Farrell, Delay- and disruption-tolerant networking, IEEE Internet Computing, vol. 13, no. 6, pp. 82-87, 2009.
[6]
H. Zhu, X. Lin, R. Lu, X. Shen, D. Xing, and Z. Cao, An opportunistic batch bundle authentication scheme for energy constrained DTNs, in Proc. IEEE INFOCOM, Shanghai, China, 2010, pp. 1-9.
[7]
B. J. Choi and X. S. Shen, Adaptive asynchronous sleep scheduling protocols for delay tolerant networks, IEEE Trans. Mobile Computing, vol. 10, no. 9, pp. 1-9, 2011.
[8]
W. Wang, M. Motani, and V. Srinivasan, Opportunistic energy-efficient contact probing in delay-tolerant applications, IEEE/ACM Trans. Networking, vol. 17, no. 5, pp. 1592-1605, 2009.
[9]
H. Hartenstain and K. P. Laberteaux, A tutorial survey on vehicular ad hoc networks, IEEE Communication Magazine, vol. 46, no. 6, pp. 164-171, 2008.
[10]
A. Campbell, S. B. Eisenman, N. Lane, E. Miluzzo, and R. A. Peterson, People centric urban sensing, in Proc. 2nd annual international workshop on Wireless Internet, Boston, USA, 2006.
[11]
J. Zhao and G. Gao, VADD: Vehicular-assisted data delivery in vehicular ad hoc networks, IEEE Trans. Vehicular Technology, vol. 57, no. 3, pp. 1910-1922, 2008.
[12]
Y. Toor, P. Muhlethaler, and A. Laouiti, Vehicular ad hoc networks: Applications and related technical issues, IEEE Communication Surveys and Tutorials, vol. 10, no. 3, pp. 74-88, 2008.
[13]
Beijing Taxi Trajectory Datasets, http://sensor.ee.tsinghua.edu.cn, 2011.
[14]
A. Vahdat and D. Becher, Epidemic routing for partially connected ad hoc networks, in Tech. Rep. CS-200006, Dept. Computer Science, Duke University, Durham, USA, 2000.
[15]
A. Balasubramanian, B. Neil, and A. Venkataramani, DTN routing as a resource allocation problem, in Proc. SIGCOMM’07, Kyoto, Japan, 2007, pp. 373-384.
[16]
T. Spyropoulos, K. Psounis, and C. S. Raghavendra, Spray and wait: An efficient routing scheme for intermittently connected mobile networks, in Proc. 2005 ACM SIGCOMM workshop on Delay-tolerant networking, Philadelphia, USA, 2005, pp. 252-259.
[17]
A. Lindgren, A. Doria, and O. Schelen, Probabilistic routing in intermittently connected networks, ACM SIGMOBILE Mobile Computing and Communications Review, vol. 7, no. 3, pp. 19-20, 2003.
[18]
M. Musolesi, S. Hailes, and C. Mascolo, Adaptive routing for intermittently connected mobile ad hoc networks, in Proc. 6th IEEE International Symposium on a World of Wireless Mobile and Multimedia Networks, Taormina, Italy, 2005, pp. 183-189.
[19]
C. Shen, G. Borkar, S. Rajagopalan, and C. Jarkaeo, Interrogation-based relay routing for ad hoc satellite networks, in Proc. IEEE Global Telecommunications Conference, Taipei, China, 2002, pp. 2920-2924.
[20]
B. Burns, O. Brock, and B. N. Levine, MV routing and capacity building in disruption tolerant networks, in Proc. IEEE INFOCOM, Miami, USA, 2005, pp. 398-408.
[21]
K. Tan, Q. Zhang, and W. Zhu, Shortest path routing in partially connected ad hoc networks, in Proc. IEEE Global Telecommunications Conference, San Francisco, USA, 2003, pp. 1038-1042.
[22]
E. Jones, L. Li, J. K. Schmidtke, and P. A. S. Ward, Practical routing for delay tolerant networks, in Proc. 2005 ACM SIGCOMM workshop on Delay-tolerant networking, Philadelphia, USA, 2005, pp. 237-243.
[23]
L. Tassiulas and A. Ephremides, Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks, IEEE Trans. Automatic Control, vol. 37, no. 12, pp. 1936-1948, 1992.
[24]
M. Alresaini, M. Sathiamoorthy, B. Krishnamachari, and M. J. Neely, Backpressure with Adaptive Redundancy (BWAR), in Proc. IEEE INFOCOM, Orlando, USA, 2012, pp. 2300-2308.
[25]
A. Jindal and K. Psounis, Contention-aware performance analysis of mobility-assisted routing, IEEE Trans. Mobile Computing, vol. 8, no. 2, pp. 145-161, 2009.
[26]
P. Tournoux, J. Leguay, and F. Benbadis, Density-aware routing in highly dynamic DTNs: the rollernet case, IEEE Trans. Mobile Computing, vol. 10, no. 12, pp. 1755-1768, 2011.
[27]
S. Eichler, Performance evaluation of the IEEE 802.11p wave communication standard, in Proc. IEEE 66th Vehicular Technology Conference, Baltimore, USA, 2007, pp. 2199-2203.
[28]
P. Fauchald and T. Tveraa, Using first-passage time in the analysis of area-restricted search and habitat selection, Ecology, vol. 84, no. 2, pp. 282-288, 2003.
[29]
R. Metzler and J. Klafter, The restaurant at the end of the random walk: recent developments in the description of anomalous transport by fractional dynamics, Journal of Physics A: Mathematical and General, vol. 37, no. 31, pp. R161-R208, 2004.
Tsinghua Science and Technology
Pages 230-241
Cite this article:
Fu Q, Krishnamachari B, Zhang L. DAWN: A Density Adaptive Routing for Deadline-Based Data Collection in Vehicular Delay Tolerant Networks. Tsinghua Science and Technology, 2013, 18(3): 230-241. https://doi.org/10.1109/TST.2013.6522582

570

Views

15

Downloads

13

Crossref

N/A

Web of Science

16

Scopus

0

CSCD

Altmetrics

Received: 24 March 2013
Accepted: 17 April 2013
Published: 03 June 2013
© The author(s) 2013
Return