Resumen

El problema de la colocación de nodos de retransmisión en redes de sensores inalámbricos (WSN) tiene como objetivo desplegar el mínimo número de nodos de retransmisión en la red de forma que cada sensor pueda comunicarse con al menos un nodo de retransmisión. Cuando los nodos de retransmisión desplegados son homogéneos y sus rangos de comunicación son circulares, una forma de resolver el problema de colocación de nodos de retransmisión WSN es resolver primero el problema de cobertura geométrica mínima de disco (MGDC) y colocar los nodos de retransmisión en los centros de los discos de cobertura y luego, si es necesario, desplegar nodos de retransmisión adicionales para satisfacer el requisito de conexión de los nodos de retransmisión. Se sabe que el problema MGDC es NP-completo. Se propone un nuevo algoritmo de aproximación en tiempo lineal para el problema MGDC, que identifica los discos de cobertura utilizando la teselación de hexágonos regulares del plano con área acotada. El ratio de aproximación del algoritmo propuesto es ( 5 ϵ ), donde 0 < ϵ ≤ 15 . Los resultados experimentales muestran que el peor caso es raro, y en promedio el algoritmo propuesto utiliza menos de 1,7 veces los discos óptimos del problema MGDC. En los casos en los que es necesario un despliegue rápido, este estudio proporciona un algoritmo rápido de 7 aproximaciones que utiliza de media menos del doble del número óptimo de nodos de retransmisión de la simulación.

• Materias:Redes de sensores Sensores inalámbricos Sistema de sensores Sensor inteligente Sensores electroquímicos
• Subjects:Sensor networks Wireless sensors Sensor system Intelligent sensor Electrochemical sensors
• Palabras claves:nodos de relé, problema mgdc, problema de colocación de nodos de relé wsn, cobertura geométrica mínima de disco, algoritmo novedoso de aproximación en tiempo lineal, problema de colocación de nodos de relé, nodos de relé adicionales, teselación hexagonal regular, red inalámbrica de sensores, algoritmo
• Keywords:relay nodes, mgdc problem, wsn relay node placement problem, minimum geometric disk cover, novel linear time approximation algorithm, relay node placement problem, additional relay nodes, regular hexagon tessellation, wireless sensor network, algorithm