Fault Tolerance in Strongly Minimum Energy Topology with MLD: A Distributed, Energy Efficient yet Simple Protocol

• Ivan Oliveira Nunes UFMG
• Luiz Filipe M. Vieira UFMG
• Antonio A. F. Loureiro UFMG

DOI: https://doi.org/10.5753/wtf.2015.22937

Resumo

Wireless Sensor Networks (WSN) have been the subject of extensive research due to their wide range of applications. A sensor node should have the longest lifetime possible, since we need to build a system that performs its functions effectively and, at the same time, spends the least amount of energy, allowing the battery to last longer. One of the functions that consumes more energy in a WSN is the wireless data transmission. In this context, it becomes interesting to determine a setting of transmission powers for the network sensor nodes so the network remains connected while nodes’ transmission powers remain minimum. The problem of minimizing the total energy consumption in a network is known in the literature as Strongly Minimum Energy Topology (SMET) and its decision version is known to be an NP-Complete problem. In this work, we evaluate the cost of adding fault tolerance through redundant paths to the SMET Minimum Spanning Tree (MST) topology, creating a redundant MST, a non-practical fault tolerant baseline algorithm. Next, we propose a practical redundant algorithm, Minimum Link Degree (MLD), which does not need any localization information and can be implemented in a distributed fashion. Our results show that the MLD topology is a promising approach, performing better than the redundant MST with respect to number of survived nodes’ faults.

Referências

Ahuja, R. K., Magnanti, T. L., and Orlin, J. B. (1988). Network flows. Technical report, DTIC Document.

Arora, A., Dutta, P., Bapat, S., Kulathumani, V., Zhang, H., Naik, V., Mittal, V., Cao, H., Demirbas, M., Gouda, M., et al. (2004). A line in the sand: a wireless sensor network for target detection, classification, and tracking. Computer Networks, 46(5):605–634.

Boonsawat, V., Ekchamanonta, J., Bumrungkhet, K., and Kittipiyakul, S. (2010). Xbee wireless sensor networks for temperature monitoring. In the second conference on application research and development (ECTI-CARD 2010), Chon Buri, Thailand.

Cheng, M. X., Cardei, M., Sun, J., Cheng, X., Wang, L., Xu, Y., and Du, D.-Z. (2004). Topology control of ad hoc wireless networks for energy efficiency. Computers, IEEE Transactions on, 53(12):1629–1635.

Cheng, X., Narahari, B., Simha, R., Cheng, M. X., and Liu, D. (2003). Strong minimum energy topology in wireless sensor networks: Np-completeness and heuristics. Mobile Computing, IEEE Transactions on, 2(3):248–256.

EDC Group (2008). Sinalgo-simulator for network algorithms - http://www.disco.ethz.ch/projects/sinalgo/.

Faloutsos, M. and Molle, M. (1995). Optimal distributed algorithm for minimum spanning trees revisited. In Proceedings of the fourteenth annual ACM symposium on Principles of distributed computing, pages 231–237. ACM.

Gutierrez, J. A., Naeve, M., Callaway, E., Bourgeois, M., Mitter, V., and Heile, B. (2001). Ieee 802.15. 4: a developing standard for low-power low-cost wireless personal area networks. network, IEEE, 15(5):12–19.

He, T., Krishnamurthy, S., Stankovic, J. A., Abdelzaher, T., Luo, L., Stoleru, R., Yan, T., Gu, L., Hui, J., and Krogh, B. (2004). Energy-efficient surveillance system using wireless sensor networks. In Proceedings of the 2nd international conference on Mobile systems, applications, and services, pages 270–283. ACM.

LaMarca, A., Brunette, W., Koizumi, D., Lease, M., Sigurdsson, S. B., Sikorski, K., Fox, D., and Borriello, G. (2002). Making sensor networks practical with robots. In Pervasive Computing, pages 152–166. Springer.

Lee, J.-S., Su, Y.-W., and Shen, C.-C. (2007). A comparative study of wireless protocols: Bluetooth, uwb, zigbee, and wi-fi. In Industrial Electronics Society, 2007. IECON 2007. 33rd Annual Conference of the IEEE, pages 46–51. IEEE.

Mainwaring, A., Culler, D., Polastre, J., Szewczyk, R., and Anderson, J. (2002). Wireless sensor networks for habitat monitoring. In Proceedings of the 1st ACM international workshop on Wireless sensor networks and applications, pages 88–97. ACM.

Min, R., Bhardwaj, M., Cho, S.-H., Ickes, N., Shih, E., Sinha, A., Wang, A., and Chandrakasan, A. (2002). Energy-centric enabling technologies for wireless sensor networks. IEEE wireless communications, 9(4):28–39.

Nunes, I. O., Martinello, M., and Loureiro, A. A. F. (2015). Designing a low cost home wsn for remote energy monitoring and eletronic devices control. In Proceedings of the Brazilian Symposium on Computer Networks and Distributed Systems - Workshop on Communications of Critical Embedded Systems’ 2015. SBC.

Pottie, G. J. and Kaiser, W. J. (2000). Wireless integrated network sensors. Communications of the ACM, 43(5):51–58.

Sibley, G. T., Rahimi, M. H., and Sukhatme, G. (2002). Robomote: A tiny mobile robot platform for large-scale ad-hoc sensor networks. In Robotics and Automation, 2002. Proceedings. ICRA’02. IEEE International Conference on, volume 2, pages 1143–1148. IEEE.

Silva, F., Braga, T. R., Ruiz, L. B., and Nogueira, J. M. S. (2004). Tecnologia de nós sensores sem fio. Controle & Instrumentação, 92:76–87.

Vieira, M. A. M., Coelho, C. N., da Silva Jr, D. C., and da Mata, J. M. (2003). Survey on wireless sensor network devices. In Emerging Technologies and Factory Automation, 2003. Proceedings. ETFA’03. IEEE Conference, volume 1, pages 537–544. IEEE.

Wattenhofer, R., Li, L., Bahl, P., and Wang, Y.-M. (2001). Distributed topology control for power efficient operation in multihop wireless ad hoc networks. In INFOCOM 2001. Twentieth Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings. IEEE, volume 3, pages 1388–1397. IEEE.

Xue, F. and Kumar, P. R. (2004). The number of neighbors needed for connectivity of wireless networks. Wireless networks, 10(2):169–181.

Yan, Z., Chang, Y., Jiang, H., and Shen, Z. (2013). Fault-tolerance in wireless ad hoc networks: bi-connectivity through movement of removable nodes. Wireless Communications and Mobile Computing, 13(12):1095–1110.

Ye, M., Li, C., Chen, G., and Wu, J. (2005). Eecs: an energy efficient clustering scheme in wireless sensor networks. In Performance, Computing, and Communications Conference, 2005. IPCCC 2005. 24th IEEE International, pages 535–540. IEEE.

Yu, B., Xu, L., and Li, Y. (2012). Bluetooth low energy (ble) based mobile electrocardiogram monitoring system. In Information and Automation (ICIA), 2012 International Conference on, pages 763–767. IEEE.

Zhao, Q. and Gurusamy, M. (2008). Lifetime maximization for connected target coverage in wireless sensor networks. IEEE/ACM Transactions on Networking (TON), 16(6):1378–1391.