HyungJune Lee
ABSTRACT
In this paper, we present a routing scheme that exploits knowledge about the behavior of mobile sinks within a network of data sources to minimize energy consumption and network congestion. For delay-tolerant network applications, we propose to route data not to the sink directly, but to send it instead to a relay node along an announced or predicted path of the mobile node that is close to the data source. The relay node will stash the information until the mobile node passes by and picks up the data. We use linear programming to find optimal relay nodes that minimize the number of necessary transmissions while guaranteeing robustness against link and node failures, as well as trajectory uncertainty.
We show that this technique can drastically reduce the number of transmissions necessary to deliver data to mobile sinks. We derive mobility and association models from real-world data traces and evaluate our data stashing technique in simulations. We examine the influence of uncertainty in the trajectory prediction on the performance and robustness of the routing scheme.
- TinyOS 2.1.0. http://www.tinyos.net/tinyos-2.1.0/.Google Scholar
- A. Agrawal and S. K. Khaitan. A new heuristic for multiple sequence alignment. In Proceedings of the IEEE International Conference Electro/Information Technology, 2008.Google ScholarCross Ref
- D. Ashbrook and T. Starner. Using gps to learn significant locations and predict movement across multiple users. Personal and Ubiquitous Computing, Jan 2003. Google ScholarDigital Library
- N. Banerjee, M. D. Corner, D. Towsley, and B. N. Levine. Relays, base stations, and meshes: enhancing mobile networks with infrastructure. In MobiCom '08: Proceedings of the 14th ACM international conference on Mobile computing and networking, pages 81--91, New York, NY, USA, 2008. ACM. Google ScholarDigital Library
- M. Bayir, M. Demirbas, and N. Eagle. Mobility profiler: A framework for discovering mobile user profiles (technical report version). cse.buffalo.edu, 2008.Google Scholar
- A. Chakrabarti, A. Sabharwal, and B. Aazhang. Using predictable observer mobility for power efficient design of sensor networks. In IPSN '03: Proceedings of the 2nd International Workshop on Information Processing in Sensor Networks, Palo Alto, CA, USA, 2003. Google ScholarDigital Library
- J.-H. Chang and L. Tassiulas. Maximum lifetime routing in wireless sensor networks. IEEE/ACM Trans. Netw., 12(4):609--619, 2004. Google ScholarDigital Library
- D. S. J. De Couto, D. Aguayo, J. Bicket, and R. Morris. A high-throughput path metric for multi-hop wireless routing. In MobiCom '03: Proceedings of the 9th annual international conference on Mobile computing and networking, pages 134--146, New York, NY, USA, 2003. ACM. Google ScholarDigital Library
- J. Froehlich and J. Krumm. Route prediction from trip observations. SAE SP, Jan 2008.Google ScholarCross Ref
- S. Gandham, M. Dawande, R. Prakash, and Subbarayan. Energy efficient schemes for wireless sensor networks with multiple mobile base stations. In GlobeCom '03: Proceedings of the Global Communications Conference, San Francisco, CA, USA, 2003.Google ScholarCross Ref
- J. Ghosh, M. Beal, H. Ngo, and C. Qiao. On profiling mobility and predicting locations of campus-wide wireless network users. Technical Report: State University of New York at Buffalo, Jan 2005.Google Scholar
- O. Gnawali, R. Fonseca, K. Jamieson, D. Moss, and P. Levis. Collection Tree Protocol. In Proceedings of the 7th ACM Conference on Embedded Networked Sensor Systems (SenSys'09), November 2009. Google ScholarDigital Library
- A. Goldsmith. Wireless Communications. Cambridge University Press, New York, NY, USA, 2005. Google ScholarDigital Library
- D. Johnson, D. Maltz, and J. Broch. DSR: The dynamic source routing protocol for multihop wireless ad hoc networks. In Ad Hoc Networking, 2001. Google ScholarDigital Library
- S. Johnson. Hierarchical clustering schemes. Psychometrika, 32(3):241--254, September 1967.Google ScholarCross Ref
- H. S. Kim, T. F. Abdelzaher, and W. H. Kwon. Minimum-energy asynchronous dissemination to mobile sinks in wireless sensor networks. In SenSys '03: Proceedings of the 1st international conference on Embedded networked sensor systems, pages 193--204, New York, NY, USA, 2003. ACM. Google ScholarDigital Library
- D. Kotz, T. Henderson, and I. Abyzov. CRAWDAD data set dartmouth/campus (v. 2004-12-18). Downloaded from http://www.crawdad.org/dartmouth/campus, Dec. 2004.Google Scholar
- J. Krumm. Real time destination prediction based on efficient routes. Society of Automotive Engineers (SAE) 2006 World Congress, Jan 2006.Google ScholarCross Ref
- B. Kusy, H. Lee, M. Wicke, N. Milosavljevic, and L. Guibas. Predictive qos routing to mobile sinks in wireless sensor networks. In IPSN '09: Proceedings of the 2009 International Conference on Information Processing in Sensor Networks, pages 109--120, Washington, DC, USA, 2009. IEEE Computer Society. Google ScholarDigital Library
- K. Laasonen. Clustering and prediction of mobile user routes from cellular data. LECTURE NOTES IN COMPUTER SCIENCE, Jan 2005.Google Scholar
- K. Laasonen, M. Raento, and H. Toivonen. Adaptive on-device location recognition. LECTURE NOTES IN COMPUTER SCIENCE, Jan 2004.Google Scholar
- H. Lee, A. Cerpa, and P. Levis. Improving wireless simulation through noise modeling. In IPSN '07: Proceedings of the 6th international conference on Information processing in sensor networks, pages 21--30, New York, NY, USA, 2007. ACM Press. Google ScholarDigital Library
- P. Levis, N. Lee, M. Welsh, and D. Culler. TOSSIM: Simulating large wireless sensor networks of tinyos motes. In Proceedings of the First ACM Conference on Embedded Networked Sensor Systems (SenSys), 2003. Google ScholarDigital Library
- Y. Li, J. Harms, and R. Holte. Optimal traffic-oblivious energy-aware routing for multihop wireless networks. In INFOCOM '06: Proceedings of the 26th Conference on Computer Communications, Barcelona, Spain, 2006.Google ScholarCross Ref
- L. Liao, D. Fox, and H. Kautz. Extracting places and activities from gps traces using hierarchical conditional random fields. The International Journal of Robotics Research, Jan 2007. Google ScholarDigital Library
- L. Liao, D. Patterson, D. Fox, and H. Kautz. Learning and inferring transportation routines. Artificial Intelligence, Jan 2007. Google ScholarDigital Library
- L. Lin, N. B. Shroff, and R. Srikant. Asymptotically optimal energy-aware routing for multihop wireless networks with renewable energy sources. IEEE/ACM Trans. Netw., 15(5):1021--1034, 2007. Google ScholarDigital Library
- J. Luo and J.-P. Hubaux. Joint mobility and routing for lifetime elongation in wireless sensor networks. In INFOCOM '05: Proceedings of the 25th Conference on Computer Communications, Miami, FL, USA, 2005.Google Scholar
- J. Luo, J. Panchard, M. Piorkowski, M. Grossglauser, and J.-P. Hubaux. Mobiroute: Routing towards a mobile sink for improving lifetime in sensor networks. In DCOSS '06: Proceedings of the International Conference on Distributed Computing in Sensor Systems, San Francisco, CA, USA, 2006. Google ScholarDigital Library
- Y. Mao, F. Wang, L. Qiu, S. S. Lam, and J. M. Smith. S4: Small state and small stretch routing protocol for large wireless sensor networks. In 4th Symposium on Networked Systems Design and Implementation (NSDI 2007), 2007. Google ScholarDigital Library
- C. Notredame. Recent progress in multiple sequence alignment: a survey. Pharmacogenomics, 3(1):131--144, January 2002.Google ScholarCross Ref
- P. Nurmi and J. Koolwaaij. Identifying meaningful locations. Mobile and Ubiquitous Systems: Networking & Services, 2006 Third Annual International Conference on, pages 1--8, Jul 2006.Google Scholar
- C. E. Perkins, E. M. Belding-Royer, and S. Das. Ad hoc on demand distance vector (AODV) routing. IETF Internet draft, draft-ietf-manet-aodv-09.txt, November 2001 (Work in Progress). Google ScholarDigital Library
- R. C. Shah, S. Roy, S. Jain, and W. Brunette. Data mules: Modeling a three-tier architecture for sparse sensor networks. In IEEE SNPA Workshop, pages 30--41, 2003.Google ScholarCross Ref
- T. F. Smith and M. S. Waterman. Identification of common molecular subsequences. Journal of Molecular Biology, 147(1):195--197, March 1981.Google ScholarCross Ref
- L. Song, U. Deshpande, U. Kozat, D. Kotz, and R. Jain. Predictability of wlan mobility and its effects on bandwidth provisioning. INFOCOM 2006. 25th IEEE International Conference on Computer Communications. Proceedings, pages 1--13, Apr 2006.Google ScholarCross Ref
- L. Song, D. Kotz, R. Jain, and X. He. Evaluating location predictors with extensive wi-fi mobility data. INFOCOM 2004. Twenty-third AnnualJoint Conference of the IEEE Computer and Communications Societies, 2:1414--1424 vol.2, Feb 2004.Google ScholarCross Ref
- J. D. Thompson, D. G. Higgins, and T. J. Gibson. Clustal w: improving the sensitivity of progressive multiple sequence alignment through sequence weighting, position-specific gap penalties and weight matrix choice. Nucleic Acids Res, 22(22):4673--4680, November 1994.Google ScholarCross Ref
- L. Wang and T. Jiang. On the complexity of multiple sequence alignment. Journal of Computational Biology, 1(4):337--348, 1994.Google ScholarCross Ref
- R. Wohlers, N. Trigoni, R. Zhang, and S. Ellwood. Twinroute: Energy-efficient data collection in fixed sensor networks with mobile sinks. In MDM '09: Proceedings of the 2009 Tenth International Conference on Mobile Data Management: Systems, Services and Middleware, pages 192--201, Washington, DC, USA, 2009. IEEE Computer Society. Google ScholarDigital Library
- F. Ye, H. Luo, J. Cheng, S. Lu, and L. Zhang. A two-tier data dissemination model for large-scale wireless sensor networks. In MobiCom '02: Proceedings of the 8th annual international conference on Mobile computing and networking, pages 148--159, New York, NY, USA, 2002. ACM. Google ScholarDigital Library
- J. Yin, Q. Yang, D. Shen, and Z.-N. Li. Activity recognition via user-trace segmentation. Transactions on Sensor Networks (TOSN), 4(4), Aug 2008. Google ScholarDigital Library
Index Terms
- Data stashing: energy-efficient information delivery to mobile sinks through trajectory prediction
Recommendations
Mobility pattern based routing algorithm for delay/disruption tolerant networks
ruSMART/NEW2AN'10: Proceedings of the Third conference on Smart Spaces and next generation wired, and 10th international conference on Wireless networkingDelay/Disruption Tolerant Networks (DTN) can support data transmission under the challenging network conditions. And one of the most important protocol components for DTN is a routing protocol to improve the performance of transmission delay and ...
Comparison of On-Demand Routing Protocols
AMS '10: Proceedings of the 2010 Fourth Asia International Conference on Mathematical/Analytical Modelling and Computer SimulationRouting in MANET is very important issue as dynamic topology of MANET makes routing very difficult. In this paper we are comparing two on-demand routing protocol namely Ad hoc on demand distance vector (AODV) and Dynamic source routing (DSR) protocol. ...
Reliable data transmission in mobile ad hoc sensor networks
In this paper, we introduce a new routing scheme for mobile ad hoc sensor networks, which effectively transports the information from source to sink by curbing the energy requirements, both at node and system level. The proposed approach, termed as ...
Comments