Balanceamento de Carga em Redes de Sensores Sem Fio baseado em Sistemas Multiagentes: DSA vs. LA-DCOP vs. Swarm-GAP
Resumo
Várias técnicas têm sido empregadas para buscar a extensão da vida útil de uma Rede de Sensores Sem Fio dado que a alimentação por baterias limita sua aplicabilidade. Uma das formas de conseguir isso é o emprego do balanceamento de carga dos serviços a serem realizados pela rede entre os nodos que a compõe. Este artigo avalia o emprego de algoritmos de alocação de tarefas em Sistemas Multiagentes, apresentados na literatura recente, para obter o balanceamento de carga mencionado. Foram experimentados os algoritmos DSA, LA-DCOP e Swarm-GAP, sempre comparados com a não utilização de balanceamento. Os resultados obtidos mostraram que, apesar de um alto consumo de bateria para a comunicação entre os agentes, a eficiência da rede permaneceu igual a não utilização do balanceamento de carga. Assim, o emprego dos algoritmos experimentados é promissor, mas para sua maior eficiência é preciso que o custo de comunicação seja bastante reduzido.
Referências
AbdelSalam, H. and Olariu, S. (2011). Toward efficient task management in wireless sensor networks. Computers, IEEE Transactions on, 60(11):1638–1651.
Boffo, F., Jr., P. R. F., and Bazzan, A. L. C. (2007). A comparison of algorithms for task allocation in robocup rescue. In Proceedings of the 5th European Workshop on Multiagent Systems. To appear.
Bonabeau, E., Theraulaz, G., and Dorigo, M. (1999). Swarm Intelligence: From Natural to Artificial Systems. Oxford University Press, New York, USA.
Braun, T., Siegel, H., and Maciejewski, A. (2002). Static mapping heuristics for tasks with dependencies, priorities, deadlines, and multiple versions in heterogeneous environments. In Parallel and Distributed Processing Symposium., Proceedings International, IPDPS 2002, Abstracts and CD-ROM, pages 8 pp–.
Caliskanelli, I., Harbin, J., Indrusiak, L. S., Mitchell, P., Polack, F., and Chesmore, D. (2013). Bioinspired load balancing in large-scale wsns using pheromone signalling. International Journal of Distributed Sensor Networks, 2013.
Ferreira, Jr., P. R., dos Santos, F., Bazzan, A. L. C., Epstein, D., and Waskow, S. J. (2010). Robocup rescue as multiagent task allocation among teams: experiments with task interdependencies. 20(3):421–443.
Ferreira Jr., P. R., Boffo, F., and Bazzan, A. L. C. (2007). A swarm based approximated algorithm to the extended generalized assignment problem (E-GAP). In Proceedings of the 6th International Joint Conference on Autonomous Agents And Multiagent Systems (AAMAS), pages 1231–1233.
Ferreira Jr., P. R., Boffo, F., and Bazzan, A. L. C. (2008). Using Swarm-GAP for distributed task allocation in complex scenarios. In Jamali, N., Scerri, P., and Sugawara, T., editors, Massively Multiagent Systems, Lecture Notes in Artificial Intelligence. Springer Verlag, Berlin. To appear.
Lesser, V., Ortiz, C. L., and Tambe, M. (2003). Distributed sensor networks: A multiagent perspective, volume 9. Springer.
Martello, S. and Toth, P. (1990). Knapsack problems: algorithms and computer implementations. John Wiley & Sons, Inc.
Martinovic, G., Budin, L., and Hocenski, Z. (2003). Static-dynamic mapping in heterogeneous computing environment. In Virtual Environments, Human-Computer Interfaces and Measurement Systems, 2003. VECIMS ’03. 2003 IEEE International Symposium on, pages 32–37.
Nwana, H. S., Lee, L. C., and Jennings, N. R. (1996). Coordination in software agent systems. The British Telecom Technical Journal, 14(4):79–88.
Pathak, A. and Prasanna, V. (2010). Energy-efficient task mapping for data-driven sensor network macroprogramming. Computers, IEEE Transactions on, 59(7):955–968.
Scerri, P., Farinelli, A., Okamoto, S., and Tambe, M. (2005). Allocating tasks in extreme teams. In Proceedings of the 4th International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS, pages 727–734, New York. ACM Press.
Shivle, S., Siegel, H. J., Maciejewski, A. A., Sugavanam, P., Banka, T., Castain, R., Chindam, K., Dussinger, S., Pichumani, P., Satyasekaran, P., Saylor, W., Sendek, D., Sousa, J., Sridharan, J., and Velazco, J. (2006). Static allocation of resources to communicating subtasks in a heterogeneous ad hoc grid environment. J. Parallel Distrib. Comput., 66(4):600–611.
Theraulaz, G., Bonabeau, E., and Deneubourg, J. (1998). Response threshold reinforcement and division of labour in insect societies. Royal Society of London Series B - Biological Sciences, 265:327–332.
Uney, M. and Cetin, M. (2007). Graphical model-based approaches to target tracking in sensor networks: An overview of some recent work and challenges. In Image and Signal Processing and Analysis, 2007. ISPA 2007. 5th International Symposium on, pages 492–497.
Zeng, Z., Liu, A., Li, D., and Long, J. (2008). A highly efficient dag task scheduling algorithm for wireless sensor networks. In Young Computer Scientists, 2008. ICYCS 2008. The 9th International Conference for, pages 570–575.
Zhang, W. and Wittenburg, L. (2002). Distributed breakout revisited. In Proceedings of the 18th National Conference on Artificial Intelligence, pages 352–357. Menlo Park, CA: American Association for Artificial Intelligence.
Boffo, F., Jr., P. R. F., and Bazzan, A. L. C. (2007). A comparison of algorithms for task allocation in robocup rescue. In Proceedings of the 5th European Workshop on Multiagent Systems. To appear.
Bonabeau, E., Theraulaz, G., and Dorigo, M. (1999). Swarm Intelligence: From Natural to Artificial Systems. Oxford University Press, New York, USA.
Braun, T., Siegel, H., and Maciejewski, A. (2002). Static mapping heuristics for tasks with dependencies, priorities, deadlines, and multiple versions in heterogeneous environments. In Parallel and Distributed Processing Symposium., Proceedings International, IPDPS 2002, Abstracts and CD-ROM, pages 8 pp–.
Caliskanelli, I., Harbin, J., Indrusiak, L. S., Mitchell, P., Polack, F., and Chesmore, D. (2013). Bioinspired load balancing in large-scale wsns using pheromone signalling. International Journal of Distributed Sensor Networks, 2013.
Ferreira, Jr., P. R., dos Santos, F., Bazzan, A. L. C., Epstein, D., and Waskow, S. J. (2010). Robocup rescue as multiagent task allocation among teams: experiments with task interdependencies. 20(3):421–443.
Ferreira Jr., P. R., Boffo, F., and Bazzan, A. L. C. (2007). A swarm based approximated algorithm to the extended generalized assignment problem (E-GAP). In Proceedings of the 6th International Joint Conference on Autonomous Agents And Multiagent Systems (AAMAS), pages 1231–1233.
Ferreira Jr., P. R., Boffo, F., and Bazzan, A. L. C. (2008). Using Swarm-GAP for distributed task allocation in complex scenarios. In Jamali, N., Scerri, P., and Sugawara, T., editors, Massively Multiagent Systems, Lecture Notes in Artificial Intelligence. Springer Verlag, Berlin. To appear.
Lesser, V., Ortiz, C. L., and Tambe, M. (2003). Distributed sensor networks: A multiagent perspective, volume 9. Springer.
Martello, S. and Toth, P. (1990). Knapsack problems: algorithms and computer implementations. John Wiley & Sons, Inc.
Martinovic, G., Budin, L., and Hocenski, Z. (2003). Static-dynamic mapping in heterogeneous computing environment. In Virtual Environments, Human-Computer Interfaces and Measurement Systems, 2003. VECIMS ’03. 2003 IEEE International Symposium on, pages 32–37.
Nwana, H. S., Lee, L. C., and Jennings, N. R. (1996). Coordination in software agent systems. The British Telecom Technical Journal, 14(4):79–88.
Pathak, A. and Prasanna, V. (2010). Energy-efficient task mapping for data-driven sensor network macroprogramming. Computers, IEEE Transactions on, 59(7):955–968.
Scerri, P., Farinelli, A., Okamoto, S., and Tambe, M. (2005). Allocating tasks in extreme teams. In Proceedings of the 4th International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS, pages 727–734, New York. ACM Press.
Shivle, S., Siegel, H. J., Maciejewski, A. A., Sugavanam, P., Banka, T., Castain, R., Chindam, K., Dussinger, S., Pichumani, P., Satyasekaran, P., Saylor, W., Sendek, D., Sousa, J., Sridharan, J., and Velazco, J. (2006). Static allocation of resources to communicating subtasks in a heterogeneous ad hoc grid environment. J. Parallel Distrib. Comput., 66(4):600–611.
Theraulaz, G., Bonabeau, E., and Deneubourg, J. (1998). Response threshold reinforcement and division of labour in insect societies. Royal Society of London Series B - Biological Sciences, 265:327–332.
Uney, M. and Cetin, M. (2007). Graphical model-based approaches to target tracking in sensor networks: An overview of some recent work and challenges. In Image and Signal Processing and Analysis, 2007. ISPA 2007. 5th International Symposium on, pages 492–497.
Zeng, Z., Liu, A., Li, D., and Long, J. (2008). A highly efficient dag task scheduling algorithm for wireless sensor networks. In Young Computer Scientists, 2008. ICYCS 2008. The 9th International Conference for, pages 570–575.
Zhang, W. and Wittenburg, L. (2002). Distributed breakout revisited. In Proceedings of the 18th National Conference on Artificial Intelligence, pages 352–357. Menlo Park, CA: American Association for Artificial Intelligence.
Publicado
28/05/2014
Como Citar
FERREIRA JR., Paulo R.; LEMKE, Alexandre; GIESEL, Marcelo; AFONSO, Paulo A.; BRISOLARA, Lisane B..
Balanceamento de Carga em Redes de Sensores Sem Fio baseado em Sistemas Multiagentes: DSA vs. LA-DCOP vs. Swarm-GAP. In: WORKSHOP-ESCOLA DE SISTEMAS DE AGENTES, SEUS AMBIENTES E APLICAÇÕES (WESAAC), 8. , 2014, Porto Alegre/RS.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2014
.
p. 91-101.
ISSN 2326-5434.
