Abstract
In this work, we present a path-planning method for the Mobile Data Collector (MDC) in a wireless sensor network (WSN). In our method, a tour for the MDC is generated such that the latency of delivering data to the sink is reduced. We show that the TSP tour covers all the nodes of the WSN. However, the latency for the TSP tour may be prohibitively high for delay-sensitive real-time WSNs. We reduce the latency by shortening the given TSP tour using a method called Linear Shortcut. We observe that the MDC need not visit the exact location of the node. It only need to be in the proximity of the node as required by the transmission radius. We present an algorithm that iteratively shortens tour-length and hence, reduces the latency. We term the resulting tour as Tight Label Covering (TLC) tour. Experimental results show that TLC tour reduces latency by a significant margin.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Akyildiz, I.F., Su, W., Sankarasubramaniam, Y., Cayirci, E.: Wireless sensor networks: a survey. Comput. Netw. 38(4), 393–422 (2002)
Rajagopalan, R., Varshney, P.K.: Data-aggregation techniques in sensor networks: a survey. IEEE Communications Surveys Tutorials 8(4), 48–63 (2006)
Di Francesco, M., Das, S.K., Anastasi, G.: Data collection in wireless sensor networks with mobile elements: A survey. ACM Transaction on Sensor Networks 8, 7:1–7:31 (2011)
Zhao, W., Ammar, M.H.: Message ferrying: Proactive routing in highly-partitioned wireless ad hoc networks. In: Proceedings of the The Ninth IEEE Workshop on Future Trends of Distributed Computing Systems, FTDCS 2003, pp. 308–314. IEEE Computer Society, Washington, DC (2003)
Shah, R.C., Roy, S., Jain, S., Brunette, W.: Data mules: Modeling a three-tier architecture for sparse sensor networks. In: IEEE SNPA Workshop, pp. 30–41 (2003)
Zhao, W., Ammar, M., Zegura, E.: A message ferrying approach for data delivery in sparse mobile ad hoc networks. In: Proceedings of the 5th ACM International Symposium on Mobile ad Hoc Networking and Computing, MobiHoc 2004, pp. 187–198. ACM, New York (2004)
Jun, H., Zhao, W., Ammar, M.H., Zegura, E.W., Lee, C.: Trading latency for energy in wireless ad hoc networks using message ferrying. In: Proceedings of the Third IEEE International Conference on Pervasive Computing and Communications Workshops, PERCOMW 2005, pp. 220–225. IEEE Computer Society, Washington, DC (2005)
Wang, Z.M., Basagni, S., Melachrinoudis, E., Petrioli, C.: Exploiting sink mobility for maximizing sensor networks lifetime. In: Proceedings of the 38th Annual Hawaii International Conference on System Sciences - Volume 09, HICSS 2005, p. 287.1. IEEE Computer Society, Washington, DC (2005)
Rao, J., Wu, T., Biswas, S.: Network-assisted sink navigation protocols for data harvesting in sensor networks. In: WCNC 2008, IEEE Wireless Communications & Networking Conference, Las Vegas, Nevada, USA, March 31-April 3. Conference Proceedings, pp. 2887–2892. IEEE (2008)
Conti, M., Pelusi, L., Passarella, A., Anastasi, G.: Mobile-relay Forwarding in Opportunistic Network. In: Adaptation and Cross Layer Design in Wireless Networks. CRC Press (2008)
Ma, M., Yang, Y.: Sencar: An energy-efficient data gathering mechanism for large-scale multihop sensor networks. IEEE Transaction on Parallel and Distributed System 18, 1476–1488 (2007)
Sugihara, R., Gupta, R.K.: Improving the data delivery latency in sensor networks with controlled mobility. In: 4th IEEE International Conference on Distributed Computing in Sensor Systems, pp. 386–399. Springer, Heidelberg (2008)
Sugihara, R., Gupta, R.K.: Path planning of data mules in sensor networks. ACM Transaction on Senson Networks 8(1), 1:1–1:27 (2011)
Yuan, Y., Peng, Y.: Racetrack: an approximation algorithm for the mobile sink routing problem. In: Nikolaidis, I., Wu, K. (eds.) ADHOC-NOW 2010. LNCS, vol. 6288, pp. 135–148. Springer, Heidelberg (2010)
Bhadauria, D., Tekdas, O., Isler, V.: Robotic data mules for collecting data over sparse sensor fields. J. Field Robot. 28(3), 388–404 (2011)
Huang, P., Xiao, L., Soltani, S., Mutka, M., Xi, N.: The evolution of mac protocols in wireless sensor networks: A survey. IEEE Communications Surveys Tutorials PP(99), 1–20 (2012)
Castalia wsn simulator framwork for omnet++, http://www.castelia.org
Concorde tsp solver, http://www.tsp.gatech.edu/concorde.html
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Rahman, M.S., Naznin, M. (2013). Shortening the Tour-Length of a Mobile Data Collector in the WSN by the Method of Linear Shortcut. In: Ishikawa, Y., Li, J., Wang, W., Zhang, R., Zhang, W. (eds) Web Technologies and Applications. APWeb 2013. Lecture Notes in Computer Science, vol 7808. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-37401-2_66
Download citation
DOI: https://doi.org/10.1007/978-3-642-37401-2_66
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-37400-5
Online ISBN: 978-3-642-37401-2
eBook Packages: Computer ScienceComputer Science (R0)