Abstract
A usual way to collect data in a Wireless Sensor Network (WSN) is by the support of a special agent, called data mule, that moves between sensor nodes and performs all communication between them. In this work, the focus is on the construction of the route that the data mule must follow to serve all nodes in the WSN. This paper deals with the case when the data mule does not have a global view of the network, i.e., a prior knowledge of the network as a whole. Thus, at each node, the data mule makes a decision about the next node to be visited based only on a limited local knowledge of the WSN. Considering this realist scenario, two locality sensitive algorithms are proposed. These algorithms differ by the criterion of choice of the next visited node, while the first one uses a simpler greedy choice, the second one uses the geometric concept of convex hull. They were executed in instances of the literature and their results were compared both in terms of route length and in number of sent messages as well. Some theoretical results, a mathematical formulation, and some lower bounds for the global view scenario are also proposed, in order to provide some parameters to evaluate the quality of the solutions given by the proposed algorithms. The obtained results show that the proposed algorithms give good solutions in a reasonable time when compared with the optimal solutions and lower bounds.
The authors acknowledges the support from CAPES, CNPq and FAPERJ.
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
Similar content being viewed by others
Notes
- 1.
LEMON – Library for Efficient Modeling and Optimization in Networks, available on https://lemon.cs.elte.hu.
References
Bin Tariq, M.M., Ammar, M., Zegura, E.: Message ferry route design for sparse ad hoc networks with mobile nodes. In: Proceedings of the 7th ACM International Symposium on Mobile Ad Hoc Networking and Computing. MobiHoc 2006, pp. 37–48. ACM, New York (2006)
Cormen, T.H., Stein, C., Rivest, R.L., Leiserson, C.E.: Introduction to Algorithms, 2nd edn. McGraw-Hill Higher Education, New York (2001)
Islam, K., Akl, S.G., Meijer, H.: A constant factor localized algorithm for computing connected dominating sets in wireless sensor networks. In: 14th IEEE International Conference on Parallel and Distributed Systems. ICPADS 2008, pp. 559–566. IEEE (2008)
Jang, H.C., Lien, Y.N., Tsai, T.C.: Rescue information system for earthquake disasters based on MANET emergency communication platform. In: Proceedings of the 2009 International Conference on Wireless Communications and Mobile Computing: Connecting the World Wirelessly, IWCMC 2009, pp. 623–627. ACM, New York (2009)
Mennell, W.K.: Heuristics for solving three routing problems: close-enough traveling salesman problem, close-enough vehicle routing problem, sequence-dependent team orienteering problem. Ph.D. thesis, University of Maryland (College Park, Md.), College Park, Maryland, USA (2009)
Puccinelli, D., Haenggi, M.: Wireless sensor networks: applications and challenges of ubiquitous sensing. IEEE Circuits Syst. Mag. 5, 2005 (2005)
Sahin, C.S., et al.: Uniform distribution of mobile agents using genetic algorithms for military applications in MANETs. In: 2008 Military Communications Conference. MILCOM 2008, pp. 1–7. IEEE (2008)
Sharma, S., Bansal, R.K., Bansal, S.: Issues and challenges in wireless sensor networks. In: 2013 International Conference on Machine Intelligence and Research Advancement (ICMIRA), pp. 58–62. IEEE (2013)
Stojmenovic, I., Seddigh, M., Zunic, J.: Dominating sets and neighbor elimination-based broadcasting algorithms in wireless networks. IEEE Trans. Parallel Distrib. Syst. 13(1), 14–25 (2002)
Sugihara, R., Gupta, R.K.: Path planning of data mules in sensor networks. ACM Trans. Sens. Netw. 8(1), 1:1–1:27 (2011)
Zhao, W., Ammar, M.: Message ferrying: proactive routing in highly-partitioned wireless ad hoc networks. In: 2003 Proceedings of the Ninth IEEE Workshop on Future Trends of Distributed Computing Systems. FTDCS 2003, pp. 308–314 (2003)
Zhao, W., Ammar, M., Zegura, E.: Controlling the mobility of multiple data transport ferries in a delay-tolerant network. In: Proceedings IEEE 24th Annual Joint Conference of the IEEE Computer and Communications Societies, vol. 2, pp. 1407–1418. IEEE (2005)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2019 Springer Nature Switzerland AG
About this paper
Cite this paper
Munhoz, P.L.A. et al. (2019). Locality Sensitive Algotrithms for Data Mule Routing Problem. In: Du, DZ., Li, L., Sun, X., Zhang, J. (eds) Algorithmic Aspects in Information and Management. AAIM 2019. Lecture Notes in Computer Science(), vol 11640. Springer, Cham. https://doi.org/10.1007/978-3-030-27195-4_22
Download citation
DOI: https://doi.org/10.1007/978-3-030-27195-4_22
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-27194-7
Online ISBN: 978-3-030-27195-4
eBook Packages: Computer ScienceComputer Science (R0)