Resumen

La difusión es una función fundamental para la divulgación de mensajes en redes inalámbricas multi-salto. El problema de Difusión de Transmisiones Mínimas (MTB, por sus siglas en inglés) tiene como objetivo encontrar un horario de difusión con el menor número de transmisiones. Trabajos previos sobre MTB en redes con ciclos de trabajo han explotado una suposición rígida de que los nodos solo tienen un intervalo de tiempo activo por ciclo de trabajo. En este artículo, investigamos el problema MTB en redes con ciclos de trabajo donde los nodos tienen permitidos intervalos de tiempo activos arbitrarios por ciclo de trabajo (problema MTBDCA). En primer lugar, se demuestra que es NP-duro e -inaproximable, donde es el grado máximo en la red. En segundo lugar, se propone un grafo auxiliar para integrar los intervalos de tiempo activos de los nodos en la red y se propone un problema de cobertura novedoso para explotar los múltiples intervalos de tiempo activos de los nodos para la programación

• Materias:Dispositivos móviles Programación centralizada Redes heterogéneas Cooperación de retransmisión Antenas inteligentes
• Subjects:Mobile devices Centralized scheduling Heterogeneous networks Relay cooperation Smart antennas
• Palabras claves:Radiodifusión; Redes inalámbricas multihop; Problema MTB; Redes con ciclo de trabajo; Ranuras de tiempo activas; Algoritmo de aproximación
• Keywords:Broadcasting; Multihop wireless networks; MTB problem; Duty-cycled networks; Active time slots; Approximation algorithm