A Prediction Algorithm based on Markov Chains for finding the Minimum Cost Path in a Mobile WSNs

  • Germán A. Montoya Systems and Computing Engineering Department Universidad de Los Andes, Bogotá, Colombia
  • Yezid Donoso Universidad de los Andes

Abstract

In this paper we propose the usage of a prediction technique based on Markov Chains to predict nodes positions with the aim of obtain short paths at minimum energy consumption. Specifically, the valuable information from the mobility prediction method is provided to our distributed routing algorithm in order to take the best network decisions considering future states of network resources. In this sense, in each network node, the mobility method employed is based on a Markov model to forecast future RSSI states of neighboring nodes for determining if they will be farther or closer within the next steps. The approach is evaluated considering different algorithms such as: Distance algorithm, Distance Away algorithm and Random algorithm. In addition, with the aim of performing comparisons against optimal values, we present a mathematical optimization model for finding the minimum cost path between a source and a destination node considering all network nodes are mobile. This paper is an extended variant of [8].

Author Biographies

Germán A. Montoya, Systems and Computing Engineering Department Universidad de Los Andes, Bogotá, Colombia
Systems and Computing Engineering Department Universidad de Los Andes, Bogotá, Colombia
Yezid Donoso, Universidad de los Andes
Associate Professor Director of the postgraduate program in Information Security

References

[1] Ahmed A. A. (2013); An enhanced real-time routing protocol with load distribution for mobile wireless sensor networks, Computer Networks, 57, 2013.
https://doi.org/10.1016/j.comnet.2013.02.003

[2] Ahmed A. A. (2007); Real-Time Wireless Sensor Networks, University of Virginia, 2007.

[3] Akyildiz, I. F.; Vuran, M. C. (2010); Wireless Sensor Networks, Vol. 4, John Wiley & Sons, Hoboken, 2010.

[4] Buchli, B.; Sutton, F.; Beutel, J. (2012); GPS-Equipped Wireless Sensor Network Node for High-Accuracy Positioning Applications, Wireless Sensor Networks Lecture Notes in Computer Science, Springer, 7158, 179-195, 2012.

[5] De Araujo, G. M.; J. Kaiser, J.; Becker, L. B. (2012); An Optimized Markov Model to Predict Link Quality in Mobile Wireless Sensor Networks, Computers and Communications, 307-312, 2012.

[6] De Araujo, G. M.; J. Kaiser, J.; Becker, L. B. (2014), Genetic Machine Learning Approach for Link Quality Prediction in Mobile Wireless Sensor Networks, Cooperative Robots and Sensor Networks, 1-14, 2014.

[7] Li, S.; Ma, X.; Wang, X.; Tan, M. (2011); Energy-efficient multipath routing in wireless sensor network considering wireless interference, Journal of Control Theory and Applications, 9(1), 127-132, 2011.
https://doi.org/10.1007/s11768-011-0263-4

[8] Montoya, G. A.; Donoso, Y. (2018); A Prediction Algorithm based on Markov Chains for finding the Minimum Cost Path in a Mobile Wireless Sensor Network, Proceedings of the 7th International Conference on Computers Communications and Control, IEEE, 169 - 175, 2018.

[9] Torkestani, J. A. (2012); Mobility prediction in mobile wireless networks. Journal of Network and Computer Applications, 35(5), 1633-1645, 2012.
https://doi.org/10.1016/j.jnca.2012.03.008

[10] Zheng, J.; Jamalipour, A. (2009); Wireless Sensor Networks: A Networking Perspective, Wiley, 2009.

[11] [Online] A Community Resource for Archiving Wireless Data At Dartmouth. http://crawdad.org/.
Published
2019-02-14
How to Cite
MONTOYA, Germán A.; DONOSO, Yezid. A Prediction Algorithm based on Markov Chains for finding the Minimum Cost Path in a Mobile WSNs. INTERNATIONAL JOURNAL OF COMPUTERS COMMUNICATIONS & CONTROL, [S.l.], v. 14, n. 1, p. 39-55, feb. 2019. ISSN 1841-9844. Available at: <http://univagora.ro/jour/index.php/ijccc/article/view/3487>. Date accessed: 16 july 2020. doi: https://doi.org/10.15837/ijccc.2019.1.3487.

Keywords

Markov model, RSSI, MWSN