Baixe o app para aproveitar ainda mais
Prévia do material em texto
Avaliac¸a˜o Comportamental em DoE do Protocolo PRoPHET em Redes Veiculares Tolerantes a Atrasos Jaqueline C. Sousa, Leonardo A. G. Silva, Pablo A.Vieira, Luciana M. Carvalho 1Sistemas de Informac¸a˜o Universidade Federal do Piauı´ (UFPI) - Picos, PI - Brasil. jaqueline.s.campelo@outlook.com, leosilvadrums100@gmail.com, pablolukan@hotmail.com,lmc.luciana@yahoo.com.br Abstract. Vehicular Networks are becoming increasingly common in mobile computing due to their potential use to solve everyday problems. These networks are made up of vehicles equipped with wireless communication devices. This work analyzes the performance of the Doe-structured PRoPHET protocol, ap- plying a combinatorial approach with different factors and levels, testing its message delivery averages in the vehicle-to-vehicle (V2V) architecture. The re- sults showed that the protocol can meet the needs of the possible alert applica- tions, if an adequate choice of node speed, packet size and buffer is made. Resumo. As Redes Veiculares esta˜o se tornando cada vez mais comuns na a´rea da computac¸a˜o mo´vel. A sua popularidade se da´ por conta da sua potencial utilizac¸a˜o na soluc¸a˜o de diversos problemas cotidianos. Essas redes sa˜o cons- tituı´das por veı´culos equipados com dispositivos de comunicac¸a˜o sem fio. Este trabalho analisa o desempenho do protocolo PRoPHET estruturado em DoE (Desing of Experiment), aplicando uma abordagem combinato´ria com fatores e nı´veis diferentes, testando suas me´dias de entrega de mensagens na arquite- tura V2V (Vehicle-to-vehicle). Os resultados mostraram que o protocolo pode atender as necessidades das possı´veis aplicac¸o˜es de alerta, se feita uma escolha adequada de velocidade dos no´s, tamanho dos pacotes e buffer. 1. Introduc¸a˜o A crescente necessidade de comunicac¸a˜o promove a busca por maneiras mais eficientes de realiza´-la . Com o desenvolvimento da tecnologia da informac¸a˜o, as redes de compu- tadores tornaram-se uma parte muito importante da comunicac¸a˜o moderna. Com o avanc¸o das pesquisas nessa a´rea, criou-se a rede mo´vel Ad Hoc (Mobile Ad Hoc Network - MANETs), que possibilita formar uma rede em a´reas onde na˜o ha´ uma infra-estrutura pre´-definida de comunicac¸o˜es, ocasionando melhorias na acessibilidade e mobilidade da rede [de Sousa and Soares 2015]. A partir das MANETs, surgiram as Redes Veiculares Ad hoc (Vehicular Ad Hoc Network - VANETs). As Redes Veiculares esta˜o ligadas diretamente a seguranc¸a no traˆnsito, auxiliando os condutores nas estradas. Elas tambe´m sa˜o usadas em sistemas de localizac¸a˜o, entretenimento e suporte ao socorro de vı´timas em locais de difı´cil acesso [de Sousa and Soares 2015]. Diariamente sa˜o noticiados inu´meros acidentes de traˆnsito, que na sua maioria poderiam ser evitados. Segundo dados do Portal Brasil, em 2016, ocorreram 20.994 aci- dentes graves em rodovias federais1. As VANETs podem prover aplicac¸o˜es que focam na seguranc¸a do condutor, e fornecem maior eficieˆncia do tra´fego dos veı´culos nas vias pu´blicas. Nesse cena´rio de comunicac¸a˜o veicular, este trabalho analisa o desempenho do protocolo PRoPHET (Probabilistic Routing Protocol using History of Encounters and Transitivity). Tal ana´lise e´ baseada em DoE (Desing of Experiment) e aplica uma aborda- gem combinato´ria com diferentes fatores e nı´veis a fim de identificar a correlac¸a˜o entre recursos e adversidades. Nossa proposta oferece um guideline para selec¸a˜o de paraˆmetros em simulac¸a˜o de VANETs. Um experimento planejado, ou seja, um DOE, e´ um teste, ou se´rie de testes, no qual sa˜o feitas mudanc¸as propositais em algumas varia´veis de entrada de um processo, de modo a podermos observar e identificar mudanc¸as correspondentes na resposta. O objeto de estudo pode ter uma ou mais caracterı´sticas de qualidade observa´veis. Algumas das varia´veis do processo de experimento sa˜o controla´veis, enquanto outras na˜o. Todas essas caracterı´sticas devem ser analisadas para o planejamento do experimento, incluindo ainda a especificac¸a˜o do objetivo do estudo. As redes veiculares necessitam de uma estrate´gia eficiente de disseminac¸a˜o de mensagens capaz de maximizar o nu´mero de veı´culos receptores, diminuir o tempo de en- trega da mensagem[Soares et al. 2013]. Diversos protocolos sa˜o utilizados nessas redes, neste trabalho adotamos o PRoPHET devido a` sua ampla adoc¸a˜o na literatura, apresen- tando resultados promissores. Em ana´lise, [Choudhary et al. 2016] concluı´ram que o custo de transmissa˜o mais baixo para a entrega de um pacote em termos de despesas gerais de rede e consumo de energia e´ conseguido pelo PRoPHET, pois este envia pacotes apenas para no´s confia´veis, ale´m disso, ele se mostrou o roteador mais adequado para a transfereˆncia de dados, cor- roborando nossa escolha. O PRoPHET sera´ avaliado atrave´s de simulac¸a˜o, onde a taxa de entrega na ar- quitetura V2V (Vehicle-to-vehicle) sera´ analisada. Tal ana´lise permite avaliar em quais situac¸o˜es o protocolo se comporta de forma negativa ou positiva para possı´veis envios de pacotes, a partir disso e´ possı´vel selecionar melhores me´tricas para utilizac¸a˜o de recursos para as VANETS. Este trabalho esta´ organizado como descrito a seguir. A Sec¸a˜o 2 apre- senta o Background, relacionando diversos aspectos das VANETS. Na Sec¸a˜o 3 os Traba- lhos Relacionados sa˜o apresentados. O Projeto e Descric¸a˜o do Ambiente de Simulac¸a˜o e´ explanado na Sec¸a˜o 4. As avaliac¸o˜es sa˜o discutidas na Sec¸a˜o 5 e, por fim, as concluso˜es sa˜o apresentadas. 2. Background Ao longo desta sec¸a˜o diversos aspectos relacionados a`s VANETs sa˜o apresentados, como suas dificuldades e tecnologias utilizadas em sua implementac¸a˜o, como esta˜o dispostas as suas estruturas e tambe´m os aspectos do protocolo PRoPHET. 1http://www.brasil.gov.br/defesa-e-seguranca/2017/02/mortes-em-rodovias-federais-cairam-6-8-em- 2016 2.1. Redes Veiculares: Estruturas e Implantac¸a˜o Os veı´culos sa˜o os principais componentes de uma rede veicular, os chamados no´s (termi- nais de comunicac¸a˜o). Estes possuem uma interface de comunicac¸a˜o sem fio para enviar, receber ou trocar informac¸o˜es [Wangham et al. 2014]. A arquitetura das redes veiculares define a forma como os no´s se organizam e se comunicam. Existem treˆs arquiteturas: o modo Ad hoc puro realiza comunicac¸a˜o apenas de veı´culo para veı´culo (V2V), e tem como principal vantagem o baixo custo por ser mais simples. Entretanto, a sua principal desvantagem esta´ na conectividade da rede, que depende da densidade e da mobilidade dos veı´culos. Ja´ o modo infraestruturado (V2I) e´ caracterizado pela comunicac¸a˜o entre veı´culos e infraestruturas localizadas nas margens das vias (Road Side Units - RSUs), e tem como vantagem uma alta conectividade da rede, pore´m o custo para implantac¸a˜o e manutenc¸a˜o das RSUs se torna elevado. O modo hı´brido, caracterizado pela existeˆncia dos dois tipos de comunicac¸o˜es – V2V e V2I – (Vehicle to Everything - V2X), busca obter o melhor das duas arquiteturas [Soares et al. ]. A Figura 1 apresenta essas treˆs arquiteturas. Figura 1. Esquema de comunicac¸a˜o em uma rede veicular [Wangham et al. 2014]. 2.2. Protocolo PRoPHET O PRoPHET e´ um protocolo de roteamento DTN (Delay Tolerant Netowork) com o obje- tivo de usar o conhecimento obtido de encontros anteriores com outros no´s para otimizar a entrega de pacotes [Patel and Shah 2016]. Podemos analisar seu funcionamento mais detalhadamente na Figura 2. Figura 2. Princı´pio de funcionamento do histo´rico de contatos entre no´s e da propriedade de transitividade do protocolo PRoPHET [Soares et al. 2013] O PROPHET e´ um protocolo de comunicac¸a˜o unicast (direc¸a˜o u´nica) para Redes Tolerantes a Atrasos. O protocolo PRoPHET (PP) usa o histo´rico de encontros entre no´s e transitividade para estimar a probabilidade de os no´s seencontrarem e explorar a mobilidade de alguns no´s para levar as mensagens ate´ mais perto dos seus destinos. A me´trica de previsibilidade de entrega e´ atualizada em cada contato entre no´s, e e´ utilizada para tomar deciso˜es de encaminhamento. Um no´ a apenas replica um agregado para um no´ b encontrado se a previsibilidade de entrega for superior em b. Tal abordagem visa tentar limitar a replicac¸a˜o excessiva de agregados [Soares et al. 2013]. 3. Trabalhos Relacionados Nesta sec¸a˜o, podemos analisar algumas caracterı´sticas acerca de trabalhos relacionados no contexto das VANETs. A Tabela 1 apresenta os crite´rios analisados, confrontando suas contribuic¸o˜es, diferenc¸as e semelhanc¸as com relac¸a˜o com presente trabalho. Tabela 1. Trabalhos Relacionados Trabalho (Ano) Principais Contribuic¸o˜es DoE (Desing of Experiments) [Sok et al. 2013] Avaliac¸a˜o da Versa˜o Diferente PRoPHET (DiPRoPHET) NA˜O [Ayub et al. 2014] Novo Protocolo de Roteamento Chamado DF NA˜O [Shinko et al. 2015] Investigar o Desempenho dos Protocolos First Contact, PRoPHET eSpray-and-Wait. NA˜O [Choudhary et al. 2016] Ana´lise do Impacto do Tamanho do Buffer NA˜O Nosso Estudo (2017) Ana´lise Combinato´ria Em DoE com Nı´veis e Paraˆmetros Diversos Na Investigac¸a˜o do Comportamento do PRoPHET SIM [Sok et al. 2013] realizaram uma avaliac¸a˜o de desempenho entre o PRoPHET tra- dicional e o DiPRoPHET, versa˜o modificada do PRoPHET tradicional proposto atrave´s de uma simulac¸a˜o NS2 (Network Simulator – 2). No artigo de [Ayub et al. 2014] foi proposto um protocolo de roteamento chamado DF (Delegated Forwarding) ++ que cal- cula o valor da qualidade do no´ com base no modelo probabilı´stico usado no proto- colo PRoPHET e encaminha a mensagem para o no´ atual pela computac¸a˜o adaptativa do espac¸o de buffer disponı´vel. No trabalho de [Shinko et al. 2015] investigou-se o desem- penho dos protocolos First Contact, PRoPHET e Spray-and-Wait em um cena´rio de en- caminhamento da Rede Veicular Tolerante a Atrasos (VDTN), os padro˜es de mobilidade dos veı´culos sa˜o gerados por SUMO (Simulac¸a˜o de Mobilidade Urbana) e como simula- dor de protocolo de comunicac¸a˜o foi usado o ONE (Ambiente de Rede Oportunı´stico). No trabalho de [Choudhary et al. 2016] analisaram o impacto do tamanho do buffer na probabilidade de entrega, nu´mero de rele´s e relac¸a˜o. O presente trabalho se destaca em relac¸a˜o aos trabalho correlatos devido ao uso do me´todo estatı´stico DoE. A grande contribuic¸a˜o do DoE esta´ na ana´lise combinato´ria que permite investigac¸a˜o mais profunda sobre nı´veis diferentes relacionados a paraˆmetros ou recursos diferentes que podem ser modificados. Isso possibilita um aperfeic¸oamento na criac¸a˜o e no desenvolvimento de novas me´tricas sobre o comportamento do protocolo PRoPHET ou outros protocolos VDTNs. 4. Descric¸a˜o dos Testes na Simulac¸a˜o e Avaliac¸a˜o Esta sec¸a˜o documenta o desempenho das estrate´gias de roteamento propostas em termos de taxa de entrega de mensagens (pacotes) no simulador ONE. Ele e´ capaz de gerar movi- mentos de no´s usando diferentes modelos de movimento, roteando mensagens entre no´s com va´rios algoritmos de roteamento DTN e tipos de remetente e receptor. O ONE trans- fere mensagens entre os no´s usando va´rios algoritmos DTN, ale´m de permitir visualizar a mobilidade e a passagem da mensagem em tempo real [Shinko et al. 2015]. A ana´lise combinato´ria foi realizada com 27 configurac¸o˜es de experimentos, ou seja, todos os fatores foram combinados entre si, na forma de (3x3x3), onde cada execuc¸a˜o se repetiu 30 vezes, visando obter mais confianc¸a nos experimentos, totalizando 810 repetic¸o˜es. Como escolha de fatores que influenciam no comportamento de uma rede vei- cular, foram escolhidos aqueles que sa˜o os mais comuns e desafiadores na a´rea de re- des veiculares tais sa˜o: velocidade dos no´s, tamanho do buffer dos no´s, e tamanho das mensagens (pacotes). Os demais paraˆmetros foram deixados em default, pois o arquivo de configurac¸a˜o do ONE conta com paraˆmetros pre´-configurados para testes prima´rios, como por exemplo, tempo de simulac¸a˜o em segundos, nu´meros de interface dos no´s, en- tre outros. Os nı´veis e fatores foram escolhidos com o objetivo de fazer uma ana´lise combi- nato´ria entre eles, observando qual a relac¸a˜o na entrega dos pacotes e perda dos pacotes. Esta´ disposta na Tabela 2 os nı´veis e os paraˆmentos em DoE para a realizac¸a˜o dos testes. Tabela 2. Design da Experieˆncia Fatores Nı´veis Velocidades Tamanhos de Buffers Tamanhos de Pacotes 10 km/h- 30 km/h 5 MB 150 Kb - 250 Kb 30 km/h- 40 km/h 15 MB 250 Kb - 450 Kb 40 km/h- 50 km/h 25 MB 450 Kb - 1 MB 4.1. Resultados Esta sec¸a˜o discute as avaliac¸o˜es e concluso˜es em relac¸a˜o aos resultados obtidos. Neste trabalho, o desempenho do protocolo e´ mensurado pela taxa de entrega, desse modo, quanto maior o nu´mero de pacotes entregues com sucesso, mais eficiente sera´ para um sistema veicular. Os dados esta˜o apresentados como me´dias ajustadas para cada nı´vel de avaliac¸a˜o. O nu´mero de mensagens criadas foram 362 em todas as execuc¸o˜es para serem enca- minhadas aos seus destinos. O numero de hosts emissores de mensagens iniciava-se com 40 (nu´mero mı´nimo padra˜o para o simulador ONE) e aumentava-se 5 hosts a cada execuc¸a˜o,para que fossem analisados de forma mais eficiente, tendo em vista algumas limitac¸o˜es do ONE, desse modo, segundo [Villares et al. 2013], estes resultados acabam sendo otimistas quando comparados a` situac¸o˜es reais. Na Figura 3 sa˜o mostrados os resultados relativos ao comportamento do protocolo com os fatores analisados. • Comportamento das Velocidades Figura 3. Gra´fico de Efeito No nı´vel 1 (velocidades pequenas entre 10 km/h e 30 km/h) a me´dia de mensagens entregues se manteve entre 175 e 176. Para o nı´vel 2 (velocidades de 30 km/h a 40 km/h) a me´dia de entrega se manteve entre 177 e 178. Ja´ o nı´vel 3 (velocidades entre 40 km/h e 50 km/h) a me´dia das entregas teve um aumento, variando entre 179 e 180. • Comportamento dos Buffers Para o nı´vel 1 (buffers pequenos de 5 MB) a me´dia de entrega de mensagens se manteve entre 177 e 178. Para o nı´vel 2 (buffers razoa´veis de 15 MB) as entregas foram as mais positivas entre 179 e 180. No nı´vel 3 (buffers grandes de 25 MB) as entregas se mantiveram insta´veis, entre 176 e 177. • Comportamento dos Pacotes No nı´vel 1 (pacotes pequenos entre 150 Kb e 250 Kb) obtivemos o melhor re- sultado nas entregas, permanecendo entre 179 e 180 mensagens. Para ambos nos nı´veis 2 (pacotes razoa´veis entre 250 kb e 450 kb) e nı´vel 3 (pacotes grandes entre 450 Kb e 1 MB) a taxa caiu de maneira semelhante, entre 175 e 176. Podemos notar que para todos os fatores do nı´vel 2, manteve-se uma instabilidade maior em relac¸a˜o aos outros nı´veis. O nı´vel 1 se mostrou melhor com relac¸a˜o ao tamanho dos pacotes. Ja´ o nı´vel 3 teve um bom resultado apenas para velocidades altas. Adequando as caracterı´sticas do nı´vel 1 ao nı´vel 2 e´ possivel estabelecer uma combinac¸a˜o satisfato´ria para o aumento da taxa de entrega. O tamanho do buffer razoa´vel, somado a tamanhos de pacotes pequenos e velocidades medianas influenciaram a instabilidade do nı´vel 2. Notamos que nı´vel 1 na˜o obteve desempenho melhor em relac¸a˜o ao nı´vel 2, pelo fato do tamanho do buffer ser pequeno. Quanto mais espac¸o de armazenamento para os agregados, mais chances ha´ de na˜o virem a ser descartados pelo estouro do buffer, um dos grandes problemas das redes veiculares, pore´m o tamanho dos pacotes tem influeˆncia direta na entrega das mensagens, quanto maiores os tamanhos dos pacotes, mais ira˜o lotar o buffer e maior sera´ sua de- mora em ser transmitido, caso na˜o sejam entregues, pois logo sa˜o descartados e a taxa diminui. Tal caracterı´sticas levou o nı´vel 3 a terum resultado insatisfato´rio comparado aos demais. Cabe ressaltar que a simulac¸a˜o foi realizada em um tempo equivalente a 3 horas de relo´gio para cada execuc¸a˜o em ambiente real urbano em um mapa ideˆntico ao da jaque Destacar cidade de Heisinki Capital da Finlaˆndia. Na Figura 4 mostramos os resultados a cerca da comparac¸a˜o entre os nı´veis e seu devidos fatores selecionados. Figura 4. Gra´fico de Interac¸a˜o Na Figura 4 (a), na interac¸a˜o dos nı´veis de velocidades e buffers notamos que a en- trega foi mais bem sucedida nos nı´veis 1 em que a velocidade e o buffers eram razoa´veis. Os casos medianos foram os de nı´veis 2, em que as velocidades sa˜o baixas e buffers pe- quenos, mantendo um crescimento constante na entrega das mensagens. Os piores casos foram os de nı´veis 3, com velocidades altas e tamanhos de buffers grandes. Possivelmente o tempo de contato foi o causador dessa caracterı´stica, pois se na˜o ha´ tempo suficiente para manter o enlace da troca de dados, as mensagens na˜o sera˜o passadas com sucesso pela rede. Na Figura 4 (b) esta´ a interac¸a˜o da velocidade com tamanho de pacote. Para os melhores casos esta˜o os de nı´veis 2, com velocidades e buffers razoa´veis, mantendo uma crescente e constante entrega de mensagens. Os casos intermedia´rios foram os nı´veis 1, com velocidades pequenas e pacotes pequenos. Os piores casos foram os de nı´veis 3 com velocidades e os pacotes maiores, tal caracterı´stica reafirma o que foi relatado anteriormente na ana´lise do gra´fico de efeito na Figura 3, o gra´fico de efeito demostrou que o tempo de contado influencia a entrega, e agora somado a tamanhos de pacotes grandes, a influeˆncia fica maior. Na interac¸a˜o do buffer e tamanho de pacote, na Figura 4 (a), os melhores casos foram para os de nı´veis 1, com velocidades pequenas e buffers pequenos, pore´m aceita´veis para o contexto das VANETs. Os casos intermedia´rios (nı´vel 2) foram com buffer e tamanho razoa´veis. Nos piores casos ficaram os de nı´veis 3, em que os tamanhos de buffer e pacotes sa˜o grandes. 5. Conclusa˜o Podemos concluir que os tamanhos dos pacotes influenciam diretamente na interac¸a˜o com o buffer caso o seu tamanho seja grande ele continuara´ negativando a entrega de pacotes. Como consequeˆncia a me´dia de entrega de mensagens na˜o tera´ aumento, faz-se necessa´rio pacotes com tamanhos um pouco reduzidos como os do nı´vel 2. Notamos tambe´m que tamanhos de pacotes grandes relacionadas a velocidades altas, teˆm influeˆncia negativa no uso do recurso do buffer, ou seja, expandir seu tamanho na˜o e´ a principal medida para aumentar a me´dia da entrega. As velocidades altas em um meio VDTN ocasionam um nu´mero maior de distaˆncias percorridas nas vias em menor tempo, isto influencia diretamente em que mais no´s sejam alcanc¸ados para o encaminhamento de pacotes, pore´m isso pode ocasionar pro- blemas na entrega de mensagens, pois quanto maiores sa˜o as velocidades, menos tempo de contato existira´ entre os no´s. Como o protocolo PRoPHET se baseia em nu´mero de contados entre os no´s, indiferentemente do tempo de contato entre eles, quanto maiores sa˜o as velocidades, menor e´ o tempo de contado entre os no´s, logo quanto maiores forem os pacotes mais difı´cil e´ sua transfereˆncia pela rede. A avaliac¸a˜o do me´todo estatistico DoE mostrou-se poderosa na ana´lise das carac- teristicas particulares a cada nı´vel submetido. Para trabalhos futuros pretendemos realizar novas ana´lise com outras varia´veis dependentes, como a lateˆncia ou Throughput, ale´m de executar uma avaliac¸a˜o do PRoPHET integrado a uma aplicac¸a˜o de emergeˆncia. Refereˆncias Ayub, Q., Zahid, M. S. M., Rashid, S., and Abdullah, A. H. (2014). Df++: An adaptive buffer-aware probabilistic delegation forwarding protocol for delay tolerant network. Cluster computing, 17(4):1465–1472. Choudhary, N., Mittal, K., Kota, K. D., Nagrath, P., and Aneja, S. (2016). Analyzing and designing energy efficient routing protocol in delay tolerant networks. CSI transactions on ICT, 4(2-4):285–291. de Sousa, R. S. and Soares, A. C. B. (2015). Estimativa e sinalizac¸ ao de congestiona- mentos de tra´fego atrave´s de redes veiculares v2v. Patel, D. and Shah, R. (2016). Improved prophet routing protocol in dtn. Shinko, I., Oda, T., Spaho, E., Kolici, V., Ikeda, M., and Barolli, L. (2015). A simulation system based on one and sumo simulators: Performance evaluation of first contact, prophet and spray-and-wait dtn protocols. In Broadband and Wireless Computing, Communication and Applications (BWCCA), 2015 10th International Conference on, pages 137–142. IEEE. Soares, R., Galeno, S., and Soares, A. Simulac¸a˜o de redes veiculares. Soares, V. N., Dias, J. A., Isento, J. N., and Rodrigues, J. J. (2013). Protocolos de en- caminhamento para redes veiculares com ligac¸o˜es intermitentes. In CRC 2012: 12a Confereˆncia sobre Redes de Computadores, pages 77–84. Sok, P., Tan, S., and Kim, K. (2013). Prophet routing protocol based on neighbor node distance using a community mobility model in delay tolerant networks. In High Per- formance Computing and Communications & 2013 IEEE International Conference on Embedded and Ubiquitous Computing (HPCC EUC), 2013 IEEE 10th International Conference on, pages 1233–1240. IEEE. Villares, T. L., Campos, C. A. V., and Viana, A. C. (2013). A influeˆncia de no´s especiais na entrega de mensagens nas redes tolerantes a atrasos e interrupc¸o˜es. WRA, 13:44–57. Wangham, M. S., Nogueira, M., Fernandes, C. P., Paviani, O., and da Silva, B. F. (2014). Seguranc¸a em redes veiculares: Inovac¸o˜es e direc¸o˜es futuras.
Compartilhar