A Identificação por radiofrequência (Radio Frequency Identification - RFID) tem revolucionado a forma de identificar objetos, sendo usada desde aplicações de controle de estoques até o processo automatizado de pagamentos. Sua ampla aceitação e aplicabilidade tem estimulado pesquisadores a criar cada vez mais aplicações. Um problema chave da RFID são as colisões que ocorrem na identificação por meio dos protocolos de acesso múltiplo. Como, na prática, um leitor precisa identificar várias etiquetas em sua área de cobertura, algumas etiquetas podem responder ao mesmo tempo o que gera colisões e desperdício de recursos. Por este motivo, torna-se de grande valor um estudo abrangente sobre como melhorar a identificação das etiquetas de modo a reduzir o número de colisões. Além disso, aspectos como consumo de energia e tempo necessário para identificação também devem ser levados em consideração, uma vez que a utilização cada vez maior de dispositivos alimentados à bateria tem sido observada na prática. Esta tese investiga a categoria de protocolos anticolisão denominada Frame Slotted Aloha - FSA, pois é a categoria que possui maior potencial de utilização prática em sistemas RFID. Além disso, as diferentes métricas de análise de desempenho são também analisadas e categorizadas, uma vez que identificou-se que um conjunto de métricas devem ser observadas com o intuito de realizarem-se comparações justas com as propostas da literatura. Descobriu-se que a maioria das propostas não levam em consideração os aspectos chave de tempo e energia, assim como a característica de ser fácil de implementar e baixa complexidade. Esta tese propõe quatro algoritmos que visam diminuir o consumo de energia e o tempo do processo de identificação das etiquetas mantendo-se as características de baixa complexidade e similaridade com o padrão atual EpcGlobal Classe 1 Geração 2 (C1G2). O primeiro mecanismo visa diminuir a quantidade de respostas desnecessárias em cenários de localização e rastreamento. Os demais consistem em três propostas de algoritmos anticolisão para sistemas RFID. Os dois primeiros diferem na forma como o tamanho inicial de quadro é definido e como as colisões são tratadas, representando evoluções progressivas em direção a um melhor desempenho. O terceiro considera a ocorrência do efeito captura, o que traz a necessidade de mudanças no funcionamento do algoritmo anterior. Resultados de simulação mostram que os quatro mecanismos podem melhorar propostas existentes sem aumento de complexidade, resultando consequentemente em diminuição de recursos desperdiçados. Além disso também foram desenvolvidos dois softwares de apoio aos mecanismos propostos: nsRFIDsim e jRFIDsim. O primeiro trata-se de um módulo para o simulador ns-2 que simula um sistema RFID passivo. O segundo implementa uma proposta de benchmark para avaliação de desempenho de algoritmos anticolisão para RFID, visando fornecer para a comunidade científica uma forma padronizada de avaliar este tipo de algoritmo. / The Radio Frequency Identification - RFID has revolutionized the way objects are identified, being used in several areas, from inventory control applications to automated payment process. Its wide acceptance and applicability has stimulated researchers to create more and more new applications. One RFID key problem is the collisions on identification by means of multiple access protocols. Since generally, a reader needs to identify multiple tags in its coverage area, some tags tend to reply at the same time which can cause collision and waste of resources. For this reason a comprehensive study on how to improve the identification of tags in order to reduce the number of collisions becomes important. Additionally, issues such as energy consumption and time required for identification must also be taken into consideration, since an increasing use of battery-powered devices has been observed in practice. This thesis investigates the category of anti-collision protocols called Frame Slotted Aloha - FSA, as it is the category that has the greatest potential for practical use in RFID systems. Further analysis of the different performance metrics are also analyzed and categorized, since it was identified that a set of metrics must be observed in order to carry out up fair comparisons with the proposals found on the literature. It was found that most of the proposals do not consider the key aspects of time and energy as well as the characteristic of being easy to implement and having low complexity. This thesis proposes four algorithms aimed at reducing the consumption of energy and the time to identify the tags while maintaining the characteristics of low complexity and similarity to the current standard EPCglobal Class 1 Generation 2 (C1G2). The first mechanism aims to decrease the unnecessary answers in locating and tracking scenarios. The other ones consist of three proposals for anti-collision algorithms for RFID systems. They differ in how the initial size is defined and how collisions are resolved, representing progressive evolutions toward a better performance. The third one considers the occurrence of the capture effect, which brings the need for changes in the previous algorithm operation. Simulation results show that the four mechanisms can improve existing proposals without increasing complexity, resulting in consequent energy savings. In addition we have also developed two softwares to evaluate the proposed mechanisms: nsRFIDsim and jRFIDsim. The former is a module for the ns-2 simulator that simulates a passive RFID system. The second one implements a proposal for benchmark performance evaluation of anti-collision algorithms for RFID in order to provide to the scientific community a standardized way to assess this type of algorithm.

A Identificação por radiofrequência (Radio Frequency Identification - RFID) tem revolucionado a forma de identificar objetos, sendo usada desde aplicações de controle de estoques até o processo automatizado de pagamentos. Sua ampla aceitação e aplicabilidade tem estimulado pesquisadores a criar cada vez mais aplicações. Um problema chave da RFID são as colisões que ocorrem na identificação por meio dos protocolos de acesso múltiplo. Como, na prática, um leitor precisa identificar várias etiquetas em sua área de cobertura, algumas etiquetas podem responder ao mesmo tempo o que gera colisões e desperdício de recursos. Por este motivo, torna-se de grande valor um estudo abrangente sobre como melhorar a identificação das etiquetas de modo a reduzir o número de colisões. Além disso, aspectos como consumo de energia e tempo necessário para identificação também devem ser levados em consideração, uma vez que a utilização cada vez maior de dispositivos alimentados à bateria tem sido observada na prática. Esta tese investiga a categoria de protocolos anticolisão denominada Frame Slotted Aloha - FSA, pois é a categoria que possui maior potencial de utilização prática em sistemas RFID. Além disso, as diferentes métricas de análise de desempenho são também analisadas e categorizadas, uma vez que identificou-se que um conjunto de métricas devem ser observadas com o intuito de realizarem-se comparações justas com as propostas da literatura. Descobriu-se que a maioria das propostas não levam em consideração os aspectos chave de tempo e energia, assim como a característica de ser fácil de implementar e baixa complexidade. Esta tese propõe quatro algoritmos que visam diminuir o consumo de energia e o tempo do processo de identificação das etiquetas mantendo-se as características de baixa complexidade e similaridade com o padrão atual EpcGlobal Classe 1 Geração 2 (C1G2). O primeiro mecanismo visa diminuir a quantidade de respostas desnecessárias em cenários de localização e rastreamento. Os demais consistem em três propostas de algoritmos anticolisão para sistemas RFID. Os dois primeiros diferem na forma como o tamanho inicial de quadro é definido e como as colisões são tratadas, representando evoluções progressivas em direção a um melhor desempenho. O terceiro considera a ocorrência do efeito captura, o que traz a necessidade de mudanças no funcionamento do algoritmo anterior. Resultados de simulação mostram que os quatro mecanismos podem melhorar propostas existentes sem aumento de complexidade, resultando consequentemente em diminuição de recursos desperdiçados. Além disso também foram desenvolvidos dois softwares de apoio aos mecanismos propostos: nsRFIDsim e jRFIDsim. O primeiro trata-se de um módulo para o simulador ns-2 que simula um sistema RFID passivo. O segundo implementa uma proposta de benchmark para avaliação de desempenho de algoritmos anticolisão para RFID, visando fornecer para a comunidade científica uma forma padronizada de avaliar este tipo de algoritmo. / The Radio Frequency Identification - RFID has revolutionized the way objects are identified, being used in several areas, from inventory control applications to automated payment process. Its wide acceptance and applicability has stimulated researchers to create more and more new applications. One RFID key problem is the collisions on identification by means of multiple access protocols. Since generally, a reader needs to identify multiple tags in its coverage area, some tags tend to reply at the same time which can cause collision and waste of resources. For this reason a comprehensive study on how to improve the identification of tags in order to reduce the number of collisions becomes important. Additionally, issues such as energy consumption and time required for identification must also be taken into consideration, since an increasing use of battery-powered devices has been observed in practice. This thesis investigates the category of anti-collision protocols called Frame Slotted Aloha - FSA, as it is the category that has the greatest potential for practical use in RFID systems. Further analysis of the different performance metrics are also analyzed and categorized, since it was identified that a set of metrics must be observed in order to carry out up fair comparisons with the proposals found on the literature. It was found that most of the proposals do not consider the key aspects of time and energy as well as the characteristic of being easy to implement and having low complexity. This thesis proposes four algorithms aimed at reducing the consumption of energy and the time to identify the tags while maintaining the characteristics of low complexity and similarity to the current standard EPCglobal Class 1 Generation 2 (C1G2). The first mechanism aims to decrease the unnecessary answers in locating and tracking scenarios. The other ones consist of three proposals for anti-collision algorithms for RFID systems. They differ in how the initial size is defined and how collisions are resolved, representing progressive evolutions toward a better performance. The third one considers the occurrence of the capture effect, which brings the need for changes in the previous algorithm operation. Simulation results show that the four mechanisms can improve existing proposals without increasing complexity, resulting in consequent energy savings. In addition we have also developed two softwares to evaluate the proposed mechanisms: nsRFIDsim and jRFIDsim. The former is a module for the ns-2 simulator that simulates a passive RFID system. The second one implements a proposal for benchmark performance evaluation of anti-collision algorithms for RFID in order to provide to the scientific community a standardized way to assess this type of algorithm.

Made available in DSpace on 2015-05-14T12:36:49Z (GMT). No. of bitstreams: 1 arquivototal.pdf: 3512497 bytes, checksum: 22606000aee179c4fa5e12daeebccb2c (MD5) Previous issue date: 2014-02-03 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / The development of algorithms oriented to robotic systems, in simulation environments, supports the identification and prediction of many problems before their tests in real environments. However, there is still not a process to ensure that an algorithm evaluated in a simulation platform will similarly work when migrated to real robots. The interference of several factors, such as engine and sensors properties, as well as the lack of a methodology that supports the interaction simulation/reality is considered as one of the main problems in this transition, so that there is a large conceptual development gap between real and simulated environments. This work aims to contribute with the formalization of a conceptual model to assist in the transition process, in which it is possible to highlight the peculiarities that require further attention from developers.. For that end, as a case study, it was developed an anti-collision algorithm, which involves several characteristics of a robotic system. Its implementation was carried out in both Unity3D simulator and real robots developed in the Arduino platform. The results were obtained and compared by a quantitative analysis of graphs using MATLAB. All necessary changes were classified and evaluated, raising up an initial idea of the transition model, which formalizes the main particulars of the project / O desenvolvimento de algoritmos voltados para sistemas robóticos, em ambientes de simulação, auxilia na identificação e antecipação de muitos problemas antes mesmo de serem testados em ambientes reais. Porém, nada garante que um algoritmo avaliado em uma plataforma de simulação funcione quando migrado para robôs reais. A interferência de diversos fatores, como propriedades dos motores e sensores, bem como a falta de uma metodologia necessária para interação simulação/realidade, se caracteriza como um dos principais problemas desta transição, de modo que, existe um grande gap conceitual entre o desenvolvimento para ambientes reais e simulados. Este trabalho tem o objetivo de contribuir com a formalização de um modelo conceitual que auxilie no processo de transição, no qual é possível destacar as peculiaridades que carecem de uma maior atenção por parte dos desenvolvedores. Para isso, como estudo de casos, foi desenvolvido um algoritmo de anticolisão, que engloba diversas características de um sistema robótico, sendo realizada sua implementação tanto no simulador Unity3D, quanto em robôs reais desenvolvidos na plataforma Arduino. Os resultados foram obtidos e comparados através de uma análise quantitativa de gráficos originados pelo MATLAB. Todas as alterações necessárias foram classificadas e avaliadas, de forma que possamos ter uma ideia do modelo de transição inicial, o qual formalize as principais particularidades do projeto

Submitted by Geyciane Santos (geyciane_thamires@hotmail.com) on 2015-11-23T21:24:44Z No. of bitstreams: 1 Dissertação - Walfredo da Costa Lucena Filho.pdf: 2083187 bytes, checksum: 72f63311dba60bbea7ef2d5cc474c601 (MD5) / Approved for entry into archive by Divisão de Documentação/BC Biblioteca Central (ddbc@ufam.edu.br) on 2015-11-30T19:51:08Z (GMT) No. of bitstreams: 1 Dissertação - Walfredo da Costa Lucena Filho.pdf: 2083187 bytes, checksum: 72f63311dba60bbea7ef2d5cc474c601 (MD5) / Approved for entry into archive by Divisão de Documentação/BC Biblioteca Central (ddbc@ufam.edu.br) on 2015-11-30T19:55:39Z (GMT) No. of bitstreams: 1 Dissertação - Walfredo da Costa Lucena Filho.pdf: 2083187 bytes, checksum: 72f63311dba60bbea7ef2d5cc474c601 (MD5) / Made available in DSpace on 2015-11-30T19:55:40Z (GMT). No. of bitstreams: 1 Dissertação - Walfredo da Costa Lucena Filho.pdf: 2083187 bytes, checksum: 72f63311dba60bbea7ef2d5cc474c601 (MD5) Previous issue date: 2015-08-03 / FAPEAM - Fundação de Amparo à Pesquisa do Estado do Amazonas / An RFID system is typically composed of a reader and a set of tags. An anti-collision algorithm is necessary to avoid collision between tags that respond simultaneously to a reader. The most widely used anti-collision algorithm is DFSA (Dynamic Framed Slotted ALOHA) due to its simplicity and low computational cost. In DFSA algorithms, the optimal TDMA (Time Division Multiple Access) frame size must be equal to the number of unread tags. If the exact number of tags is unknown, the DFSA algorithm needs a tag estimator to get closer to the optimal performance. Currently, applications have required the identification of large numbers of tags, which causes an increase in collisions and hence the degradation in performance of the traditional algorithms DFSA. This work proposes a power control mechanism to estimate the number of tags for radio frequency identification networks (RFID). The mechanism divides the interrogation zone into subgroups of tags and then RSSI (Received Signal Strength Indicator) measurements estimate the number of tags in a subarea. The mechanism is simulated and evaluated using a simulator developed in C/C++ language. In this study, we compare the number of slots and identification time, with ideal DFSA algorithm and Q algorithm EPCglobal standard. Simulation results shows the proposed mechanism provides 99% performance of ideal DFSA in dense networks, where there are many tags. Regarding the Q algorithm, we can see the improvement in performance of 6.5%. It is also important to highlight the lower energy consumption of the reader comparing to ideal DFSA is 63%. / Um sistema de identificação por rádio frequência (RFID) é composto basicamente de um leitor e etiquetas. Para que o processo de identificação das etiquetas seja bem sucedido, é necessário um algoritmo anticolisão a fim de evitar colisões entre etiquetas que respondem simultaneamente à interrogação do leitor. O algoritmo anticolisão mais usado é o DFSA (Dynamic Framed Slotted ALOHA) devido à sua simplicidade e baixo custo computacional. Em algoritmos probabilísticos, tal como o DFSA, o tamanho ótimo do quadro TDMA (Time Division Multiple Access) utilizado para leitura das etiquetas deve ser igual à quantidade de etiquetas não lidas. Uma vez que no processo de leitura, normalmente não se sabe a quantidade exata de etiquetas, o algoritmo DFSA faz uso de um estimador para obter um desempenho mais próximo do ideal. Atualmente, as aplicações têm demandado a identificação de grandes quantidades de etiquetas, o que ocasiona um aumento das colisões e, consequentemente, a degradação no desempenho dos algoritmos DFSA tradicionais. Este trabalho propõe um mecanismo de controle de potência para estimar a quantidade de etiquetas em redes de identificação por rádio frequência (RFID). O mecanismo baseia-se na divisão da área de interrogação em subáreas e, consequentemente, subgrupos de etiquetas. Tal divisão é utilizada para realizar medições de RSSI (Received Signal Strength Indicator) e, assim, estimar a quantidade de etiquetas por subárea. O mecanismo é simulado e avaliado utilizando um simulador próprio desenvolvido em linguagem C/C++. Neste estudo, comparam-se os resultados de quantidade de slots e tempo de identificação das etiquetas, com os obtidos a partir da utilização dos algoritmos DFSA ideal e algoritmo padrão Q da norma EPCglobal. A partir dos resultados da simulação, é possível perceber que o mecanismo proposto apresenta desempenho 99% do DFSA ideal em redes densas, onde há grande quantidade de etiquetas. Em relação ao algoritmo Q, percebe-se a melhoria de 6,5% no desempenho. É importante ressaltar também a redução no consumo de energia do leitor em torno de 63% em relação ao DFSA ideal.