Análisis de Planificaciones para redes Acústicas Submarinas de Sensores con Topología Lineal

Análisis de Planificaciones para redes Acústicas Submarinas de Sensores con Topología Lineal. Luque-Nieto, Miguel A.1,*, Moreno-Roldán, José M. 1, Poncela, Javier 1 y Otero, Pablo 1 1 Universidad de Málaga, E.T.S. Ingeniería de Telecomunicación. Boulevar de Louis Pasteur nº 35, Campus de Teatinos s/n. CP.29010. Málaga. Direcciones electrónicas: [email protected] (M.A.Luque), [email protected] (J.M.Moreno), [email protected] (J.Poncela), [email protected]s(P.Otero). * Autor Principal y responsable del trabajo; Dirección electrónica: [email protected](MA.Luque) Abstract: En este artículo, se aborda el análisis y mejora de rendimiento de una red submarina lineal formada por un array de nodos sensores y un solo nodo recolector de datos (Gateway) en un extremo. Usando un esquema de transmisiones TDMA en la red, se logra una operación sencilla sin contención del medio y de bajo consumo energético, pero por el contrario, se degrada el rendimiento en la entrega de datos al Gateway. Aprovechando el alto retardo del medio marino, es posible solapar diferentes transmisiones en el tiempo evitando colisiones. Se aporta un mecanismo de planificación óptima libre de colisiones, basado en repetir patrones de estado que cumplan las restricciones para evitar colisiones sobre un conjunto reducido de nodos, y que consigue aumentar el rendimiento de la red lineal, mostrando medidas del throughput que se puede llegar a alcanzar. Keywords: USN; S-TDMA; Comunicaciones submarinas; Protocolos de comunicaciones. 1. Introducción Muchas son las aplicaciones que en la actualidad tienen las redes de sensores inalámbricas (WSN) en general [1], y las submarinas (USN/UASN) en particular [2][3]. Dentro de las áreas de actuación relevantes de las USN, destacan las medioambientales y las militares, entre otras. Algunos ejemplos de aplicaciones medioambientales, son el estudio y seguimiento de migraciones de especies, la detección precoz de catástrofes (tsunamis, inundaciones…), la detección de contaminantes (plumas de río), o el seguimiento de la evolución del clima (temperatura del mar, salinidad, corrientes oceánicas…). Ya en el ámbito militar, las USN realizan sobre todo vigilancia de IV Congreso Nacional de I+D en Defensa y Seguridad,2016 navíos, especialmente submarinos. Cabe destacar que la primera experiencia militar de vigilancia acústica de submarinos se remonta a 1950, en el que la marina norteamericana comenzó a desplegar una red de hidrófonos sobre boyas flotantes en los océanos Pacífico y Atlántico, llamada SOSUS [4] (Sound Surveillance System) que permitía localizar submarinos soviéticos por triangulación a cientos de kilómetros. Las redes USN han recibido gran atención en los últimos años, tanto en el ámbito de la investigación y mejora de técnicas y protocolos en las comunicaciones [5], como en la realización y análisis de experiencias reales en el mar [6]. Debido a que el medio marino es compartido por todos los nodos de la red, la implementación de la capa de acceso al medio (MAC) recibe especial importancia y es determinante en las prestaciones de las comunicaciones entre nodos. Dentro de las técnicas MAC que se emplean en estas redes, predominan dos familias de protocolos: los de acceso por contienda (i), y los que realizan planificación de transmisiones (ii). En (i), el nodo debe competir con los demás nodos para ganar el acceso al medio. Algunos protocolos importantes por contienda son Aloha [7], de acceso aleatorio, o Slotted FAMA [8], que usa negociación con el resto de nodos. Por otro lado, en (ii) la red impone unas reglas para transmitir que respetan todos los nodos. Según la naturaleza de las reglas establecidas, existen tres grandes categorías de protocolos: FDMA (acceso por bandas de frecuencia distintas), CDMA (acceso por código) y TDMA (acceso por ranuras de tiempo). Si bien existen implementaciones de las tres técnicas, TDMA ha demostrado ser muy eficiente y simple: solo requiere que cada nodo conozca en qué intervalo de tiempo debe transmitir. Esta información se la proporciona la planificación establecida, que sigue un patrón fijo y periódico. Como ejemplo el protocolo Stump [9] usa TDMA de forma eficiente. Dos son los principales problemas que presentan las redes TDMA: sincronizar todos los nodos, y tener un bajo valor de throughput. Respeto al sincronismo, hay suficientes técnicas que se pueden emplear [5]. Con relación al aumento del throughput, la técnica S-TDMA [10] realiza un reúso espacial de transmisiones, permitiendo que varios nodos suficientemente alejados entre sí, solapen sus transmisiones sin interferencias. Una mejora adicional, sería aprovechar el alto retardo del canal acústico para solapar transmisiones. Por el efecto de la superposición de ondas, al hacer viajar dos ondas acústicas en direcciones opuestas, o “cruce en vuelo” [11], cada una sigue su curso tras interaccionar una con la otra. Aprovechando este efecto, se puede lograr una mejora apreciable en el throughput al permitir transmisiones de nodos adyacentes con ciertas restricciones que eviten la colisión de ondas en los nodos receptores. El objetivo de este artículo es buscar el máximo throughput posible en una red de sensores lineal con operación TDMA aprovechando el principio de superposición de ondas, sin que se produzcan colisiones. Para ello, en la sección 2, se hace una descripción de la topología y operación dentro de la red. En la sección 3, se propone la planificación óptima de transmisiones. En la sección 4, se aportan resultados comparativos del throughput obtenido mediante diferentes esquemas de planificación, entre ellas la óptima propuesta. 2. Topología de red y operación En la Figura 1, puede verse la topología de la red analizada. En ella, se tienen N-1 nodos equipados con sensores, y un nodo especial recolector de datos (Gateway). Estos nodos están dispuestos a igual distancia d unos de otros para tener una cobertura homogénea de la zona de interés. Existen diferentes alternativas para que el Gateway envíe los datos monitorizados por los nodos a un centro de proceso en tierra. Una de las más sencillas sería mediante un enlace radio desde una boya marítima que está conectada por cable al Gateway. Análisis de Planificaciones para redes Acústicas Submarinas de Sensores con Topología Lineal N N-1 N-2 dN-3 ... 1 d d (d) Gateway N-1 nodos sensores (d) Estación proceso terrestre Radio Radio Boya (mar) Figura 1. Topología de una red de sensores lineal con N nodos equidistantes entre sí a distancia d. Envío de datos desde una boya conectada por cable al Gateway. 2.1. Modelo de red La red de sensores tiene encaminamiento estático, con rutas dirigidas hacia el Gateway. El direccionamiento es multihop, es decir, cada nodo envía a su compañero adyacente en sentido hacia el Gateway. De esta forma, existen dos tipos de datos: los propios generados por los sensores de un nodo, y los reenviados procedentes de otros nodos que pasan por él. Por este hecho, en general los nodos más cercanos al Gateway tendrán una carga mayor de tráfico que los más alejados del Gateway. Por otro lado, el funcionamiento de los modem acústicos se asume half-duplex y es omnidireccional, por lo que un nodo no puede transmitir y recibir simultáneamente. Esto hace que la planificación de transmisiones deba evitar las colisiones de datos, es decir, que no se produzca recepción de más de una transmisión a la vez. Si se asume que el tiempo de transmisión de datos es tD, y el de propagación entre dos nodos adyacentes es tP, la Figura 2 muestra un escenario de 3 nodos intermedios de la red y cómo se produce colisión cuando dos nodos alternos transmiten simultáneamente, impidiendo que el nodo n pueda recibir del nodo n+1. n+1 n n-1 ...... tD 0 tP t tD+tP¡Colisión! a) n+1 n n-1 ... tD 0 t tD+tP(Rx) (Rx) ... b) Figura 2. (a) Las colisiones se producen con transmisiones de nodos alternos. (b) Se permite que nodos adyacentes transmitan simultáneamente sin colisión (principio de superposición). Sin embargo, debido al principio de superposición y al largo retardo de propagación tP, es posible la recepción correcta de dos transmisiones simultáneas de nodos adyacentes, como puede verse en la Figura 2b. 2.2. Planificación de transmisiones En las redes de sensores, para funciones de comunicación, se pueden considerar tres estados posibles para los nodos: transmisión, recepción o libre. En los estados de transmisión/recepción, el nodo realiza la comunicación de datos, mientras que el estado libre puede ser usado para colocar al nodo en bajo consumo, aumentando así su autonomía energética. Para redes TDMA, se requiere IV Congreso Nacional de I+D en Defensa y Seguridad,2016 establecer el orden de transmisiones (y recepciones) de cada nodo para poder operar eficientemente en el tiempo. De esta forma, una planificación será el conjunto de transmisiones/recepciones de los nodos que tienen lugar en cada intervalo de tiempo. Por otro lado, una planificación será más eficiente a medida que consiga tener un mayor número de transmisiones (o recepciones) en el mismo período de tiempo, o dicho de otra forma, un mayor valor de throughput. Aquella planificación que logre un mayor valor de throughput se considera óptima, y se puede demostrar que toda planificación óptima tiene un período de repetición de intervalos [11]. Puesto que el interés de esta comunicación se centra en buscar la planificación óptima para una red lineal, existirá un número de intervalos que llamaremos 𝑁0 que conforman el período de repetición. A esa estructura periódica también se le llama trama en la literatura especializada. La medida clásica de la eficiencia de la red vendrá determinada por el throughput. Una forma de medirlo será cuantificar la fracción de tiempo en que cualquier nodo de la red recibe datos respecto al tiempo total observado [11]. Para incrementar esta magnitud todo lo posible, se asume que el tiempo de transmisión de datos 𝑡𝐷 iguala al tiempo de propagación 𝑡𝑃, es decir, que un nodo termina de transmitir en el preciso instante en que los datos comienzan a ser recibidos por el nodo adyacente. Esto lleva a que la duración de cada intervalo de transmisión sea igual al tiempo necesario para que la onda acústica recorra una distancia 𝑑. Bajo esta condición ideal sin tiempos de espera, el throughput se define como, 𝑆=∑𝑅𝑘·𝑡𝐷 𝑁0 𝑘=1 𝑁0·𝑡𝑃|𝑡𝐷=𝑡𝑃=1 𝑁0∑𝑅𝑘 𝑁0 𝑘=1 (1) siendo: 𝑁0 : número de intervalos que forman una trama (período de planificación); 𝑡𝐷,𝑡𝑃 : duración de una transmisión y tiempo de propagación, respectivamente; 𝑅𝑘 : número de recepciones en el intervalo de tiempo k. 3. Planificación óptima Una forma de obtener la planificación óptima, es considerar el problema como una decisión secuencial intervalo a intervalo, y usar alguna técnica de programación dinámica [11] que logre maximizar el throughput. Esto es, a partir de la asignación de los tres posibles estados de cualquier nodo sensor (Tx/Rx/Libre) en el primer intervalo, añadir la mejor asignación de estados posible para el siguiente intervalo. Para ello, se puede evaluar qué asignación de estados maximiza alguna función objetivo, en este caso el throughput. Una vez se haya seleccionado la mejor asignación de estados, pasará a ser el último intervalo de la planificación parcial encontrada hasta el intervalo actual considerado. La técnica puede terminar cuando se haya encontrado una repetición en la secuencia de estados, es decir, identificar la trama y con ello, el período de la planificación óptima (𝑁0). Sin embargo, estas técnicas hacen inviable su aplicación para redes con gran número de nodos, y se tornan impracticables, recurriendo a algún algoritmo aproximado [11]. Una forma de representar visualmente una planificación, es hacerlo mediante un diagrama 2D que presente los nodos (por columnas), el estado en que se encuentra cada nodo (Tx: transmisión, Rx: recepción, Vacío: libre) en los diferentes intervalos de tiempo (cada fila es un intervalo). Como ejemplo, se ha representado en la Figura 3 dos ejemplos de planificación para una red lineal de 8 nodos. Se puede observar como la trama en la Figura 3a tiene un período de 6 intervalos de tiempo, mientras la mostrada en la Figura 3b tiene un período de 8 intervalos. Si se mide el throughput de Análisis de Planificaciones para redes Acústicas Submarinas de Sensores con Topología Lineal cada planificación, la más eficiente resulta ser la que tiene 𝑁0=8 (𝑆=74 ⁄ =1′75) frente a la de período 𝑁0=6 (𝑆=76 ⁄ ≈1′16). En el caso general, para una red lineal de N nodos, se sigue cumpliendo este comportamiento, y el throughput aplicando (1) a cada planificación resulta ser: Planificación con 𝑁0 =8: ∑𝑅𝑘 𝑁0 𝑘=1 =2·(𝑁−1), 𝑆=2·(𝑁−1) 8=𝑁−1 4 (2) Planificación con 𝑁0=6: ∑𝑅𝑘 𝑁0 𝑘=1 =𝑁−1, 𝑆=𝑁−1 6 (3) Tx Tx Rx Rx 1 Rx Tx Tx 8 7 6 5 1 Tx 4 3 2 Rx Rx Tx Tx Rx Rx Tx Tx Tx Rx Rx T R A M A 8 7 6 5 4 3 2 1 N O D O S I N T E R V A L O S D E T I E M P O 2 3 4 5 6 7 8 (…) a) Tx Tx Rx Rx 1 Tx Tx Rx Rx Tx Tx 8 7 6 5 1 4 Tx 3 Tx 2 Tx Rx Rx Rx Rx Rx Tx Tx Tx Rx Rx Rx Tx Tx Tx Rx Rx Rx T R A M A 8 7 6 5 4 3 2 1 N O D O S I N T E R V A L O S D E T I E M P O 2 3 4 5 6 7 8 9 10 Tx Tx Rx Rx Tx Tx Rx Rx (…) b) Figura 3. Ejemplos de planificación para red lineal de 8 nodos, con diferentes períodos de trama (𝑵𝟎): (a) 𝑵𝟎 =6 intervalos de tiempo, (b) 𝑵𝟎=8 intervalos de tiempo. Se muestra la onda propagada en sentido contrario (línea discontinua) para comprobar que no existen colisiones. 4. Resultados y discusión En este trabajo, se ha optado por buscar la planificación óptima mediante un método más sencillo que programación dinámica: a través de la geometría. Para ello, se propone primero un patrón de estados sin colisión de 3 nodos  3 intervalos, que tenga las máximas transmisiones y recepciones posibles, pero además que cumpla que al repetir el patrón por el dominio 2D intervalos-nodos, se mantiene una solución viable para toda la red e intervalos considerados. Para aprovechar un alto throughput, las repeticiones de patrón deben tratar de solaparse siempre que sea posible, por ejemplo, ocupando estados libres de otra repetición del patrón. 4.1. Solución óptima El patrón usado para encontrar la solución óptima, está reflejado en la Figura 4a. En él se observa que no existen colisiones. La planificación óptima obtenida al repetir el patrón de forma superpuesta entre repeticiones, es la mostrada en la Figura 4b, dando lugar a una trama de período 4 intervalos de tiempo. Se puede comprobar que la solución hallada es óptima porque los únicos nodos con estados libres quedan siempre en los extremos de la red por ser condiciones de contorno: el nodo 1 (Gateway) no puede nunca transmitir (solo recibe o libre) y al contrario pasa con el nodo N (solo IV Congreso Nacional de I+D en Defensa y Seguridad,2016 transmite o libre). Al no poderse encontrar un patrón más completo de transmisiones y recepciones, necesariamente este será el óptimo. Esta solución óptima no depende del número de nodos N para esta geometría lineal, que es el caso de estudio. Para corroborarlo se ha comprobado mediante combinatoria (usando permutaciones de los estados en cada intervalo) si existe otra planificación óptima y se llegado a la conclusión que esta es la más eficiente. 4.2. Throughput normalizado Para comparar cuál de las tres planificaciones vistas (período 𝑁0= 6, 8 ó 4 (óptima)) es más eficiente, se representa en la Figura 5 el valor de throughput normalizado (S respecto al nº nodos N) definido según (1) para diferentes tamaños de red. Tx Rx 1 Rx 3 Tx n+1 n n-1 k-1 k k+1 INTERVALOS NODOS a) 1 Tx Rx Rx Tx 8 7 Tx 5 1 Tx 4 Rx 3 Rx 2 Rx Tx Rx Rx Tx Tx Tx Rx Rx Rx Tx Tx Tx Tx Rx Rx Rx Tx Tx Rx Tx Rx Rx Tx Tx Rx Rx Rx Tx Tx Rx Rx Tx T R A M A 8 7 6 5 4 3 2 1 N O D O S I N T E R V A L O S D E T I E M P O 2 3 4 5 6 7 8 Tx Tx Tx Tx Rx Rx Rx Tx Tx Tx Tx Rx b) Figura 4. Patrón de estados (a) y planificación óptima (b) de la red de sensores lineal. Figura 5. Valor de throughput normalizado para las planificaciones 𝑵𝟎= 6, 8 ó 4 (óptima). Análisis de Planificaciones para redes Acústicas Submarinas de Sensores con Topología Lineal A la vista de los resultados de la Figura 5, se puede comprobar como la planificación óptima obtenida (período 𝑁0= 4) consigue el mayor rendimiento en la red lineal de los 3 casos considerados. 5. Conclusiones El problema de la mejora de rendimiento en las redes de sensores TDMA sigue vigente hoy en día [12][13]. Aunque padece el problema del sincronismo en los nodos de la red, tiene la gran ventaja de ser una técnica muy eficiente en cuanto a energía consumida, dotando a estas redes de alta autonomía y bajo coste de mantenimiento. Por ello, existe gran interés en mejorar el rendimiento de este tipo de redes multihop, su punto más débil frente a otras alternativas como CDMA o FDMA. En esta comunicación, aprovechando el principio de superposición de ondas en el medio acuático, y el largo retardo que sufren las ondas acústicas, se ha logrado mediante un procedimiento heurístico geométrico sencillo, encontrar una planificación óptima para una red lineal multihop que maximiza el throughput. Se ha aportado un estudio comparativo con otras planificaciones válidas, destacando su mejora de rendimiento. Agradecimientos Este trabajo ha sido financiado con ayuda de la Universidad de Málaga (Campus de Excelencia Internacional Andalucía Tech). Referencias 1. Akyldiz I.F, Vuran M.C. Wireless sensor networks. John Wiley & Sons; 2010. 2. Xiao, Y.(ed.). Underwater acoustic sensor networks. CRC Press; 2010. 3. Felemban E, Shaikh F.K, et al. Underwater Sensor Network Applications: A Comprehensive Survey. Int. Journal of Distributed Sensor Networks. 2015; Article ID 896832, 14 págs. Doi:10.1155/2015/896832. 4. Whitman E.C. SOSUS: The 'Secret Weapon' of Undersea Surveillance, Undersea Warfare. Winter 2005; 7(2). 5. Chen K. et al. A survey on MAC protocols for underwater wireless sensor networks. IEEE Communications Surveys & Tutorials; 2014; 16(3): 1433-1447. 6. Goetz M, Nissen I, Otnes R, Van Walree P. Performance analysis of underwater network protocols within international sea trial. Proc. OCEANS'15 MTS/IEEE (Genova); 2015; pp.17; 18-21 May; DOI: 10.1109/OCEANS-Genova.2015.7271400. 7. Chirdchoo N, Soh W, and Chua K.C. ALOHA-based MAC Protocols with Collision Avoidance for Underwater Acoustic Networks. IEEE Conference on Computer Communications (INFOCOM); 2007; pp.2271-2275, 6-12 May; Anchorage (Alaska). 8. Molins M, and Stojanovic M. Slotted FAMA: A MAC Protocol for Underwater Acoustic Networks. Proc. OCEANS’06 MTS/IEEE (Singapore); 2006; 16-19 May; DOI: 10.1109/OCEANSAP.2006.4393832. 9. Kredo K, Djukic P, and Mohapatra P. STUMP: Exploiting Position Diversity in the Staggered TDMA Underwater MAC Protocol. Proc. IEEE Conference on Computer Communications (INFOCOM); 2009; pp.2961-2965, 19-25 Apr; Rio de Janeiro (Brazil). 10. Luque-Nieto M.A, Moreno-Roldán J.M, Poncela J, and Otero P. Optimal Fair Scheduling in S-TDMA Sensor Networks for Monitoring River Plumes. Journal of Sensors (Ed. Hindawi); 2016; Article ID 8671516, 6 pages. DOI: 10.1155/2016/8671516. IV Congreso Nacional de I+D en Defensa y Seguridad,2016 11. Chitre M, Motani M, and Shahabudeen S. Throughput of networks with large propagation delays. IEEE Journal of Oceanic Engineering; 2012; 37(4): 645-658. 12. Seung-Hyun O. An Adaptive Slot TDMA MAC Protocol for Underwater Sensor Networks. Int. Journal of Multimedia and Ubiquitous Engineering; 2016; 11(4): 223-232. DOI: 10.14257/ijmue.2016.11.4.23. 13. Yun C, and Lim Y.K. GSR-TDMA: A Geometric Spatial Reuse-Time Division Multiple Access MAC Protocol for Multihop Underwater Acoustic Sensor Networks. Journal of Sensors (Ed. Hindawi); 2016; Article ID 6024610, 14 pages. DOI:10.1155/2016/6024610.