Uma estratégia baseada em medida de centralidade para instalação de pontos de disseminação em VANETs

• Douglas L. L. Moura UFAL
• Raquel S. Cabral UFAL
• Thiago B. M. Sales UFAL
• André L. L. Aquino UFAL

DOI: https://doi.org/10.5753/sbcup.2017.3308

Resumo

As redes veiculares possuem uma topologia intrinsecamente dinâmica, tornando-se necessária a instalação de pontos de disseminação como complemento à comunicação realizada apenas entre os véıculos. Neste trabalho apresentamos uma abordagem baseada em algoritmos genéticos e medidas de centralidade para o problema da máxima cobertura com tempo de contato (MCTTP) em redes veiculares. A abordagem considera a instalação de um número limitado de pontos de disseminação para permitir a propagação de informação maximizando a cobertura de véıculos. A utilização da medida de centralidade permitiu a redução do espaço de busca do algoritmo genético, tornando-o mais eficiente. A solução foi aplicada a um cenário urbano real com uma alta densidade de véıculos que se deslocam ao longo do tempo. Os resultados obtidos foram comparados com outras duas abordagens da literatura. Considerando um tempo mínimo de contato, os resultados encontrados sugerem um aumento significativo na cobertura dos véıculos, 1.06% e 3.78% quando comparados aos resultados obtidos por outras soluções.

Referências

Al-Sultan, S., Al-Doori, M. M., Al-Bayatti, A. H., and Zedan, H. (2014). A comprehensive survey on vehicular Ad Hoc network. JNCA, 37(1):380–392.

Aslam, B., Amjad, F., and Zou, C. C. (2012). Optimal roadside units placement in urban areas for vehicular networks. Proceedings - ISCC, 1:423–429.

Ben Brahim, M., Drira, W., and Filali, F. (2015). Roadside units placement within city-scaled area in vehicular ad-hoc networks. ICCVE, pages 1010–1016.

Blondel, V. D., Guillaume, J.-L., Lambiotte, R., and Lefebvre, E. (2008). Fast unfolding of communities in large networks. JSTAT, 10008(10):6.

Brandes, U. (2001). A faster algorithm for betweenness centrality. Journal of Mathematical Sociology, 25:163–177.

Cavalcante, E. S., Aquino, A. L., Pappa, G. L., and a.F. Loureiro, A. (2012). Roadside unit deployment for information dissemination in a VANET. GECCO, page 27.

Chi, J., Do, S., and Park, S. (2016). Traffic flow-based roadside unit allocation strategy for VANET. BigComp, pages 245–250.

Cumbal, R., Palacios, H., and Hincapié, R. (2016). Optimum Deployment of RSU for efficient communications multi-hop from vehicle to infrastructure on VANET. COLCOM.

Fortunato, S. (2010). Community detection in graphs. Physics Reports, 486(3-5):75–174.

Hochbaum, D. S. (1997). Approximation Algorithms for NP-hard Problems. PWS Publishing Co., Boston, MA, USA.

Khuller, S., Moss, A., and (Seffi)Naor, J. (1999). The budgeted maximum coverage problem. Inf. Process. Lett., 70(1):39–45.

Liang, Y., Liu, H., and Rajan, D. (2012). Optimal placement and configuration of roadside units in vehicular networks. IEEE Vehicular Technology Conference.

Meguerdichian, S., Koushanfar, F., Potkonjak, M., and Srivastava, M. B. (2001). Coverage problems in wireless ad-hoc sensor networks. IEEE INFOCOM, 3:1380–1387.

Newman, M. E. J. (2004). Analysis of weighted networks. Physical Review E - Statistical, Nonlinear, and Soft Matter Physics, 70(5 2).

Silva, C. M., Aquino, A. L., and Jr., W. M. (2015). Deployment of roadside units based on partial mobility information. Computer Communications, 60:28–39.

Silva, C. M., Aquino, A. L. L., and Meira, W. (2014). Design of roadside infrastructure for information dissemination in vehicular networks. NOMS.

Trullols, O., Fiore, M., Casetti, C., Chiasserini, C., and Ordinas, J. B. (2010). Planning roadside infrastructure for information dissemination in intelligent transportation systems. Computer Communications, 33(4):432–442.

Xiong, Y., Ma, J., Wang, W., and Tu, D. (2013). RoadGate: Mobility-centric roadside units deployment for vehicular networks. IJDSN, 2013.