Repositorio Institucional de Documentos

2013 29 Domenico Sicignano Analysis, evaluation and improvement of RT-WMP for realtime and QoS wireless communication: applications in confined environments Departamento Director/es Informática e Ingeniería de Sistemas Tardioli, Danilo Villarroel Salcedo, José Luis Director/es Tesis Doctoral Autor Repositorio de la Universidad de Zaragoza – Zaguan http://zaguan.unizar.es UNIVERSIDAD DE ZARAGOZA Departamento Director/es Domenico Sicignano ANALYSIS, EVALUATION AND IMPROVEMENT OF RT-WMP FOR REAL-TIME AND QOS WIRELESS COMMUNICATION: APPLICATIONS IN CONFINED ENVIRONMENTS Director/es Informática e Ingeniería de Sistemas Tardioli, Danilo Villarroel Salcedo, José Luis Tesis Doctoral Autor 2013 Repositorio de la Universidad de Zaragoza – Zaguan http://zaguan.unizar.es UNIVERSIDAD DE ZARAGOZA Departamento Director/es Director/es Tesis Doctoral Autor Repositorio de la Universidad de Zaragoza – Zaguan http://zaguan.unizar.es UNIVERSIDAD DE ZARAGOZA PhD Thesis Analysis, evaluation and improvement of RT-WMP for real-time and QoS wireless communication. Applications in confined environments Domenico Sicignano Supervisores: Jos´e Luis Villarroel Danilo Tardioli Grupo de Rob´otica, Percepci´on y Tiempo Real Departamento de Inform´atica e Ingenier´ıa de Sistemas Escuela de Ingenier´ıa y Arquitectura Universidad de Zaragoza Febrero 2013 PhD Thesis Analysis, evaluation and improvement of RT-WMP for real-time and QoS wireless communication. Applications in confined environments Domenico Sicignano Febrero 2013 Supervisores: Jos´e Luis Villarroel Danilo Tardioli Grupo de Rob´otica, Percepci´oon y Tiempo Real Departamento de Inform´atica e Ingenier´ıa de Sistemas Escuela de Ingenier´ıa y Arquitectura Universidad de Zaragoza PhD Thesis Analysis, evaluation and improvement of RT-WMP for real-time and QoS wireless communication. Applications in confined environments Domenico Sicignano Febrero 2013 Supervisors Jos´e Luis Villarroel Universidad de Zaragoza Danilo Tardioli Centro Universitario de Defensa Jury Luis Montano Universidad de Zaragoza Luis Almeida Universidade do Porto, Portugal Carlos Sag¨ues Universidad de Zaragoza Michael Gonzalez Harbour Universidad de Cantabria Marisol Garcia Universidad Carlos III de Madrid Resumen En los ultimos a˜nos, la innovaci´on tecnol´ogica, la caracter´ıstica de flexibilidad y el rapido despligue de las redes inal´ambricas, han favorecido la difusi´on de la redes m´oviles ad-hoc (MANETs), capaces de ofrecer servicios para tareas espec´ıficas entre nodos m´oviles. Los aspectos relacionados al dinamismo de la topolog´ıa m´ovil y el acceso a un medio compartido por naturaleza hacen que sea preciso enfrentarse a clases de problemas distintos de los relacionados con la redes cableadas, atrayendo de este modo el inter´es de la comunidad cientifica. La redes ad-hoc suelen soportar tr´afico con garant´ıa de servicio m´ınimo y la mayor parte de las propuestas presentes en literatura tratan de dar garant´ıas de ancho de banda o minimizar el retardo de los mensajes. Sin embargo hay situaciones en las que estas garantias no son suficientes. Este es el caso de los sistemas que requieren garantias mas fuertes en la entrega de los mensajes, como es el caso de los sistemas de tiempo real donde la p´erdida o el retraso de un solo mensaje puede provocar problemas graves. Otras aplicaciones como la videoconferencia, cada vez m´as extendidas, implican un trafico de datos con requisitos diferentes, como la calidad de servicio (QoS). Los requisitos de tiempo real y de QoS a˜naden nuevos retos al ya exigente servicio de comunicaci´on inal´ambrica entre estaciones m´oviles de una MANET. Adem´as, hay aplicaciones en las que hay que tener en cuenta algo m´as que el simple encaminamiento de los mensajes. Este es el caso de aplicaciones en entornos subterr´aneas, donde el conocimiento de la evoluci´on de propagaci´on de la se˜nal entre los diferentes nodos puede ser ´util para mejorar la calidad de servicio y mantener la conectividad en cada momento. A pesar de esto, dentro del amplio abanicos de propuestas presente en la literatura, existen un conjunto de limitaciones que van da el mero uso de protocolos simulados a propuestas que no tiene en cuenta de entornos no convencionales o que resultan aisladas desde el punto de vista de la integracion en sistemas complejos. En esta tesis doctoral, se propone un estudio completo sobre un plataforma inal´ambrica de tiempo real, utilizando el protocolo RT-WMP capaz de gestionar trafico multimedia al mismo tiempo y adaptado al entorno de trabajo. Se propone una extensi´on para el soporte a los datos con calidad de servicio sin limitar las caractaristicas temporales del protocolo b´asico. Y con el fin de tener en cuenta el efecto de la propagaci´on de la se˜nal, se caracteriza el entorno por medio de un conjunto de restricciones de conectividad. La soluci´on ha sido desarrollada vii y su validez ha sido demostrada extensamente en aplicaciones reales en entornos subterr´aneos, en redes malladas y aplicaciones roboticas. viii Abstract One of the consequences of the rapid extension and increasing flexibility of wireless networks in recent years has been the development of mobile ad-hoc networks (MANETs), able to offer services for specific tasks on mobile networks. The mobility and dynamic aspects of mobile network topology combined with the intrinsic requirement of shared media access involve a new set of challenges different from those faced by wired networks. In this context, MANETs have captured the attention of the research community. Ad-hoc networks usually support best-effort traffic, and several proposals have been put forward to provide minimum bandwidth guarantees or to minimize message delay. There are situations in which guaranteeing message delivery is not sufficient. This is the case of systems that rely on the guaranteed timely delivery of data, for example real-time systems where the loss or the late arrival of a single piece of data can provoke serious issues. Other applications such as video conferencing are becoming more widespread and the traffic involved has quite different requirements, for example the quality of service (QoS). Real-time and QoS requirements add difficulty to the already demanding problem of offering wireless communication among mobile stations belonging to a MANET. There are, however, applications in which guaranteeing a reliable network by improving the routing of messages may also be insufficient. This is the case of specific applications in underground areas, where the knowledge of the propagation evolution of the signal between the different nodes can be useful to improve the QoS and to maintain connectivity at all times. Despite the wide range of proposals in the literature, many of these have several limitations such as the mere use of simulated protocols, isolated proposal from integrated systems or ignoring the effects of environments which are unconventional. This PhD thesis offers a complete study of a real-time wireless framework using the RT-WMP protocol adapted to the environment and able to manage multimedia flows at the same time. The proposed QoS extension takes advantage of the bandwidth left free by the RT-WMP when it is not working in the worst-case situation. In order to take into account the effect of the signal propagation, the environment has been characterized by a set of connectivity constraints. The solution has been developed and extensively tested in real applications in underground environments involving mesh networks and robotics. ix Contents List of Figures xv List of Tables xix 1 Introduction 1 1.1 Real-Time communications considerations . . . . . . . . . . . . . . 2 1.2 Real-Time wired Communication Protocols . . . . . . . . . . . . . . 2 1.3 Real-Time Wireless Communication . . . . . . . . . . . . . . . . . . 3 1.4 Quality of Service considerations . . . . . . . . . . . . . . . . . . . 6 1.5 802.11 for Real Time Wireless applications? . . . . . . . . . . . . . 8 1.6 Goals and contributions . . . . . . . . . . . . . . . . . . . . . . . . 11 1.7 Structure of the Thesis . . . . . . . . . . . . . . . . . . . . . . . . . 12 2 RT-WMP Definition 15 2.1 RelatedWork .............................. 16 2.2 Overview................................. 18 2.3 FramesDefinition............................ 19 2.4 The Link Quality Matrix . . . . . . . . . . . . . . . . . . . . . . . . 20 2.5 Phases of the Protocol . . . . . . . . . . . . . . . . . . . . . . . . . 21 2.5.1 Priority Arbitration Phase . . . . . . . . . . . . . . . . . . . 21 2.5.2 Authorization Transmission Phase . . . . . . . . . . . . . . . 22 2.5.3 Message Transmission Phase . . . . . . . . . . . . . . . . . . 22 2.6 Mobility Management . . . . . . . . . . . . . . . . . . . . . . . . . 23 2.6.1 Link Quality Matrix (LQM) Updating . . . . . . . . . . . . 23 2.6.2 Maintaining a fresh LQM . . . . . . . . . . . . . . . . . . . 24 2.6.3 LQM Elements and Path Calculation . . . . . . . . . . . . . 24 2.6.4 LQM Initialization . . . . . . . . . . . . . . . . . . . . . . . 25 2.7 ErrorHandling ............................. 26 2.7.1 LQM Misalignment . . . . . . . . . . . . . . . . . . . . . . . 26 2.7.2 Node Failure or Node Loss . . . . . . . . . . . . . . . . . . . 27 2.7.3 Frame Duplication . . . . . . . . . . . . . . . . . . . . . . . 29 2.7.4 Frame Retransmission . . . . . . . . . . . . . . . . . . . . . 29 2.8 Conclusion................................ 30 xi Contents Contents 3 RT-WMP: Evaluation and Analysis 31 3.1 Real-TimeFeatures........................... 32 3.1.1 Phases Boundness . . . . . . . . . . . . . . . . . . . . . . . . 32 3.1.2 Timing and Bandwidth . . . . . . . . . . . . . . . . . . . . . 33 3.1.3 Theoretical Analysis . . . . . . . . . . . . . . . . . . . . . . 34 3.1.4 Testbed ............................. 38 3.1.5 Real-time Behavior . . . . . . . . . . . . . . . . . . . . . . . 41 3.1.6 Throughput and end-to-end delay . . . . . . . . . . . . . . . 43 3.1.7 Mobility management . . . . . . . . . . . . . . . . . . . . . . 47 3.2 RT-WMPvsOLSR........................... 48 3.2.1 The OLSR protocol . . . . . . . . . . . . . . . . . . . . . . . 49 3.2.2 Bandwidth............................ 50 3.2.3 Mobility............................. 51 3.2.4 Lessonlearned ......................... 52 3.3 Analysis of the protocol . . . . . . . . . . . . . . . . . . . . . . . . 53 3.3.1 RT-WMP as a state machine . . . . . . . . . . . . . . . . . 53 3.3.2 RT-WMP Processor Utilization . . . . . . . . . . . . . . . . 55 3.3.3 Evaluation under MaRTE OS . . . . . . . . . . . . . . . . . 57 3.3.4 Overhead and Blocking . . . . . . . . . . . . . . . . . . . . 58 3.3.5 Message Response Time . . . . . . . . . . . . . . . . . . . . 61 3.4 Conclusion................................ 62 4 RT-WMP Quality of Service Extension 65 4.1 RelatedWork.............................. 66 4.2 Overview................................. 67 4.2.1 Worst-case in RT-WMP . . . . . . . . . . . . . . . . . . . . 67 4.2.2 AvailableTime ......................... 68 4.2.3 QoS Extension Operations . . . . . . . . . . . . . . . . . . . 68 4.3 The RT-WMP QoS Extension Details . . . . . . . . . . . . . . . . 69 4.3.1 Frame Header Modification . . . . . . . . . . . . . . . . . . 69 4.3.2 Phases of the Protocol . . . . . . . . . . . . . . . . . . . . . 70 4.3.3 Message Priority Policy . . . . . . . . . . . . . . . . . . . . . 72 4.4 Flow Admission Control . . . . . . . . . . . . . . . . . . . . . . . . 73 4.4.1 Overview ............................ 73 4.4.2 Available Resource Estimation . . . . . . . . . . . . . . . . . 74 4.5 Evaluation ............................... 76 4.5.1 AvailableTime ......................... 76 4.5.2 RT-WMP Traffic Impact . . . . . . . . . . . . . . . . . . . . 78 4.5.3 Fairness ............................. 79 4.5.4 End-to-end Delay . . . . . . . . . . . . . . . . . . . . . . . . 79 4.5.5 Multi-hop Transmission . . . . . . . . . . . . . . . . . . . . 81 4.5.6 PDR Evaluation . . . . . . . . . . . . . . . . . . . . . . . . 81 4.6 Conclusions ............................... 81 xii Contents Contents 5 Underground Propagation Issues 83 5.1 Relatedwork .............................. 84 5.2 MANET in underground settings . . . . . . . . . . . . . . . . . . . 85 5.2.1 Link metrics consideration . . . . . . . . . . . . . . . . . . . 86 5.3 Environment - The Somport tunnel . . . . . . . . . . . . . . . . . . 86 5.3.1 RSSI and PDR relation . . . . . . . . . . . . . . . . . . . . . 87 5.3.2 Rate and Coverage Range . . . . . . . . . . . . . . . . . . . 87 5.3.3 Fading Analisys . . . . . . . . . . . . . . . . . . . . . . . . . 89 5.3.4 Delay Spread Measurement . . . . . . . . . . . . . . . . . . 91 5.4 Conclusions ............................... 92 6 Applications 95 6.1 Real-Time protocol in underground voice communication . . . . . . 96 6.1.1 Relatedworks ......................... 96 6.1.2 Specialization on the environment . . . . . . . . . . . . . . . 97 6.1.3 Evaluation............................ 99 6.1.4 Real experiment . . . . . . . . . . . . . . . . . . . . . . . . . 105 6.1.5 Conclusions ........................... 110 6.2 Robot teams for exploration in underground environments . . . . . 111 6.2.1 Relatedwork.......................... 112 6.2.2 Overview ............................ 112 6.2.3 Details of the plan . . . . . . . . . . . . . . . . . . . . . . . 113 6.2.4 Hardware and Software Architecture . . . . . . . . . . . . . 114 6.2.5 Communication Module . . . . . . . . . . . . . . . . . . . . 116 6.2.6 Navigation Module . . . . . . . . . . . . . . . . . . . . . . . 116 6.2.7 Localization Module . . . . . . . . . . . . . . . . . . . . . . 117 6.2.8 Supervisor Module . . . . . . . . . . . . . . . . . . . . . . . 118 6.2.9 System network configuration . . . . . . . . . . . . . . . . . 119 6.2.10 Results of the experiment . . . . . . . . . . . . . . . . . . . 122 6.2.11Conclusions ........................... 124 6.3 Signal based deployment planning for robot teams in fading environments................................. 126 6.3.1 Relatedwork .......................... 126 6.3.2 Deployment Planning . . . . . . . . . . . . . . . . . . . . . . 128 6.3.3 System Description . . . . . . . . . . . . . . . . . . . . . . . 134 6.3.4 Communication Module . . . . . . . . . . . . . . . . . . . . 136 6.3.5 Localization Module . . . . . . . . . . . . . . . . . . . . . . 137 6.3.6 Navigation Module . . . . . . . . . . . . . . . . . . . . . . . 138 6.3.7 Supervisor Module . . . . . . . . . . . . . . . . . . . . . . . 138 6.3.8 Experiments........................... 139 6.3.9 Conclusions ........................... 144 xiii Contents Contents 7 Conclusions 147 7.1 English.................................. 147 7.2 Espa˜nol ................................. 152 A Field experiments 157 A.1 Outdoor experiments . . . . . . . . . . . . . . . . . . . . . . . . . . 157 A.2 Underground Experiments - Somport Tunnel . . . . . . . . . . . . . 159 B 165 Bibliography 167 xiv List of Figures 1.1 Visual representation of a zone in which neither spatial reuse nor broadcast dissemination is possible. ...................... 10 2.1 A hypothetical situation described by the network graph and the corresponding LQM. The hops sequence of the protocol is also shown. 18 2.2 Frames of the protocol. Field size is expressed in bytes. . . . . . . . 19 2.3 Asymmetrical behavior of links. . . . . . . . . . . . . . . . . . . . . 26 2.4 Token duplication resolution mechanism. In case of message or authorization duplication the mechanism works in a similar way. . . . 27 3.1 Worst case PAP situation. . . . . . . . . . . . . . . . . . . . . . . . 32 3.2 Timing of the protocol. . . . . . . . . . . . . . . . . . . . . . . . . . 33 3.3 The 802.11 protocol timing. . . . . . . . . . . . . . . . . . . . . . . 34 3.4 Efficiency of a RT-WMP five-nodes completely connected network. . 36 3.5 Worst-case bandwidth offered by RT-WMP. . . . . . . . . . . . . . 37 3.6 Relative efficiency of RT-WMP compared with plain 802.11 protocol considering a completely connected network (a) and a network in which no spatial reuse is possible (b). . . . . . . . . . . . . . . . . . 40 3.7 Theoretical loop duration for a worst-case RT-WMP network. . . . 41 3.8 Mean end-to-end delay vs priority for a 7 nodes RT-WMP completely connectednetwork. ........................... 42 3.9 Mean end-to-end delay vs priority for a 7 nodes RT-WMP chain connectednetwork. ........................... 42 3.10 Mean end-to-end delay vs priority for a 7 nodes RT-WMP chain network.................................. 43 3.11 RT-WMP completely connected network Throughput and Etoe for different-size messages. . . . . . . . . . . . . . . . . . . . . . . . . . 44 3.12 RT-WMP chain network throughput and etoe for different-size messages. .................................. 45 3.13 RT-WMP worst case network throughput and etoe for different-size messages. ................................ 46 3.14 Scenario of the experiment. . . . . . . . . . . . . . . . . . . . . . . 47 3.15 Mobility management of the RT-WMP protocol. . . . . . . . . . . . 49 3.16 Rough bandwidth offered by RT-WMP and OLSR protocols. . . . . 51 xv List of Figures List of Figures 3.17 Mobility management of the OLSR protocol. . . . . . . . . . . . . . 52 3.18 RT-WMP state machine in each node. . . . . . . . . . . . . . . . . 54 3.19 CPU time spent for the RT-WMP sequences. . . . . . . . . . . . . . 56 3.20 RT-WMP CPU utilization vs network size. . . . . . . . . . . . . . . 57 3.21RT-WMPOverhead. .......................... 60 3.22 RT-WMP Max Blocking. . . . . . . . . . . . . . . . . . . . . . . . . 61 4.1 Time intervals used by the QoS Extension. . . . . . . . . . . . . . . 68 4.2 Frame for the RT-WMP with QoS extension. . . . . . . . . . . . . . 70 4.3 Resource estimation mechanism. . . . . . . . . . . . . . . . . . . . . 75 4.4 Time spent for the RT-WMP in real test compared to worst case for differenttopologies............................ 77 4.5 QoS Cumulative Throughput vs. protocol packet size. . . . . . . . . 78 4.6 QoS Cumulative Throughput vs. RT-WMP load percentile. . . . . . 79 4.7 Instantaneous Throughput of 5 flow of same class. . . . . . . . . . . 80 4.8 End-to-end delay for different class (a) and same-class (b) flows. . . 80 4.9 Delay and jitter vs hop count. . . . . . . . . . . . . . . . . . . . . . 81 4.10 PDR for different class (a) and same-class (b) flows. . . . . . . . . . 82 5.1 The Somport tunnel. . . . . . . . . . . . . . . . . . . . . . . . . . . 87 5.2 Empirical relation between RSSI and PDR measured. In (a), the variation for five different transmission rates. In (b), figure highlights the RSSI and Rate values that correspond to acceptable PDR level. 88 5.3 Coverage range for 6 Mbps and 54 Mbps data rate along tunnel. . . 89 5.4 Measured received power (dBm) along tunnel. . . . . . . . . . . . . 90 5.5 Wavelet of the signal versus the distance using the Morlet function. 90 5.6 Real signal and signal from the model. . . . . . . . . . . . . . . . . 91 5.7 Delay Spread values sensed from receiver. . . . . . . . . . . . . . . . 92 6.1 Theenvironment............................. 97 6.2 Alternative paths to reach the same node. . . . . . . . . . . . . . . 98 6.3 An illustration of mobility scheme. . . . . . . . . . . . . . . . . . . 99 6.4 Relation between voice data and inter-arrival time. . . . . . . . . . 101 6.5 Distribution (a) and raw data of Inter-Arrival Time (IAT) (b) for twosaturatedflows............................ 102 6.6 Distribution (a) and raw data of Inter-Arrival Time (IAT) (b) . . . 103 6.7 End-to-end delay distribution. . . . . . . . . . . . . . . . . . . . . . 104 6.8 RSSI and Prim based routing simulation. . . . . . . . . . . . . . . . 105 6.9 Identity of the last-hop sender. . . . . . . . . . . . . . . . . . . . . . 105 6.10 (a) Distribution and (b) raw data of Inter-Arrival Time (IAT) in the realexperiment.............................. 108 6.11 Distribution of end-to-end delays in the real experiment. . . . . . . 109 xvi Introduction 1.3. Real-Time Wireless Communication [Malcolm 95], [Le Lann 93], [Sobrinho 98]. Another type of solution is the Token-passing paradigm. This makes the access control deterministic allowing a single token owner node to access at once. The idea of token passing, first proposed by [Grow 82], is used in the IEEE 802.4 (Tokenbus network) [Damian 00], IEEE 802.5 (Token-ring network) [IEEE 97], and the Fiber Distributed Data Interface (FDDI) [FDD 98] standards, and in the TimedToken Protocol (TTP) [Malcolm 94], the Real-Time Ethernet Protocol (RETHER) [Venkatramani 94] and the RT-EP protocol [Mart´ınez 03] In the TDMA scheme, used in the MARZ [Schwarz 02], TTP/C [Kopetz 89] and FlexRay [Pop 06] protocols, each node transmits one after the other, each using its own time slot. However, there are applications where wiring is a major limitation. This is the case of mobile systems with real-time requirements. 1.3 Real-Time Wireless Communication The widespread use of wireless networks has been accompanied by a transfer of solutions for wired networks to the wireless medium. However, on the one hand, wireless networks are generally less reliable than wired ones, the probability of errors being much higher. This is due to the possibility of interference, reflections or simply to the distance between peers. Moreover, the fact that nodes are not able to listen to the channel while transmitting aggravates the problem of collision detection and resolution. The vast majority of wireless protocols rely on random backoff mechanisms that introduces a high degree of unpredictability into the Medium Access Control (MAC) layer. Challenges Wireless channel Contention The use of a common channel for nodes to communicate among themselves in a MANET introduces the problems of interference and channel contention. These can be avoided in various ways in a peer-to-peer communications network. One way is to use a system based on th Time Division Multiple Access (TDMA), where each node may transmit at a predefined time, attempting a global clock synchronization. This is difficult to achieve due to the lack of a central controller, the node mobility and the overhead involved. Another way is to use a different frequency band or spreading code as in Code Division Multiple Access (CDMA) for each node. This requires a mechanism that provides a distributed channel selection as well as channel information dissemination. An easier way is using a Token passing scheme in order to arbitrate the contention channel. The network generates a single token that permits only the node 3 1.3. Real-Time Wireless Communication Introduction currently holding it to transmit data. Indeed, most MANETs are based on the currently most popular wireless ad hoc networking technology 802.11x [IEEE 07]. The 802.11 MAC layer defines two mechanisms to coordinate the access to the medium: the Distributed Coordination Function (DCF) and the Point Coordination Function (PCF). The DCF scheme employs a Carrier-Sense Multiple Access with Collision Avoidance (CSMA/CA) mechanism, similar to the collision detection CSMA/CD used in wired Ethernet networks. Stations compete to gain the right to access the medium following a non-deterministic inter-frame-delay prioritisation. Because it is not possible to detect a collision in wireless networks, a collision is identified by means of the absence of the corresponding acknowledgement. So in practice, the CSMA/CA only tries to prevent collisions. With PCF, a point coordinator within the access point arbitrates which stations can transmit during any given period of time. The point coordinator polls the stations one at a time and if one station has some packet to transmit, it is authorized. During this time no other station can send anything. The point coordinator will then poll the next station and continues down the polling list. Thus, PCF is a contention-free protocol and enables stations to transmit data frames synchronously. However, channel access in PCF mode has the disadvantage of being centralized and seems to be implemented only in very few hardware devices. Hidden and Exposed node problems The well-understood hidden node and exposed node problems are an additional consequence of channel contention. Hidden node is the situation in which two independent emitters simultaneously send a frame to the same receiver. Exposed node is verified when two transmitters in the range of each other, try to send packets to two receivers that are out of range of each other. This may prevent sending packets. The Hidden and Exposed node effects are even more pronounced when we consider that nodes may interfere with transmissions outside their transmission range, since receivers are able to detect a signal at a much greater distance than that at which they can decode its information. Lack of centralized control One of main characteristics of a MANET is the absence of centralized control. It may be set up without planning and its members can change dynamically. As such, communications protocols which utilize only locally available state and operate in a completely distributed manner are preferred [Hanzo-II 07]. However, this generally increases an algorithm’s overhead and complexity, as network state information must be disseminated in an efficient way. Node mobility Node mobility means that any MANET entity may move completely randomly and independently. So mobility entails that topology information 4 Introduction 1.3. Real-Time Wireless Communication has a limited lifetime and must be updated frequently to allow data packets to be routed to their destinations. This characteristic could invalidate any link stability guarantees or hard packet delivery ratios [Qin 06]. So, as a general assumption for any routing protocol able to function properly, the topology changing rate must be less than or equal to the rate of state information propagation. Otherwise, routing will be inefficient or even fail completely because the information will always be stale. Limited device resources Although mobile devices are becoming more and more powerful and capable, it still holds true that they generally have less computational power, less memory, and a limited power supply compared to computers typically employed in wired networks. Limited resources have a major impact on the provision of QoS assurances, since low memory capacity limits the amount of QoS state that can be stored, necessitating more frequent updates which incurs greater overhead. Additionally, Real-Time and QoS routing generally implies a greater overhead than best-effort routing due to the extra information being disseminated. These factors may place an undue burden on a less-powerful processor and limit battery power supply. Signal Propagation and Environment Several studies have been made about signal propagation taking into account antenna polarization, operating frequency and characteristics of the environment. Propagation models are different depending on whether the wave is propagating in free space, indoors, in urban environments or in confined environments. Nevertheless, many valuable studies in the area of MANET have been carried out by computer simulations or experiments. Most of them do not consider the signal propagation or the propagation environment at all. However, in order to make optimal use of a MANET, it is desirable to have some knowledge of both characteristics because a solution for a certain environment may not work effectively in a different environment. This is especially true in applications carried out in confined environments such as tunnels or mines where success of the operation could depend on providing communications capability according to the environmental settings. Given all these issues, the scientific community is divided on the possibility of supporting real-time traffic via wireless communication. This is understandable considering that a single missed deadline can provoke a total system failure. However, no system is exempt from errors or problems. Even a very robust system can suffer from electrical or mechanical problems that can jeopardize its correct behavior. Real-time protocols rely on the fact that the probability of errors is below a certain reasonable threshold. Ethernet and real-time ethernet, for example, manage Bit Error Ratios (BER) of about 10−10. This means that a 100 Mbps saturated network suffers from an error each 100 seconds or for each 1.215 GB transferred. 5 1.4. Quality of Service considerations Introduction Thus, a common real-time system must be able to manage at least such a level of probability of error without ending in total failure. Obviously it is impossible to obtain such BERs in wireless communications (they are at least a couple of orders of magnitude apart), at least with the current technology. However, if a particular system can tolerate a higher probability of error then it is possible, in our opinion, to speak at least of firm real-time wireless communication. In cooperative robotics applications this is sometimes enough. Due to the autonomy of the nodes, infrequent deadline misses could be tolerable even if they degrade the quality of service of the system. In these applications robots, in fact, need to collaborate to achieve a common goal. Generally, sensors on the robots produce periodic updates that must be transmitted to other members of the team respecting time constraints to enable such collaboration to take place [Stankovic 04]. The strictness of the timing requirements depends on the specific application or system, but the loss of a single or multiple deadlines is not necessarily a great problem. Just to give an example, consider a team of mobile robots with the task of cooperatively building a map, such as in [Urcola 09]. The slave robots share their laser-range readings with the leader of the team to build a common and more complete view of the environment. Knowing the maximum end-to-end delay is critical to correctly position the readings in time and thus in the corresponding period of the control algorithm. The loss of a single reading is not critical since the leader can rely on the previous observations and avoid the updating of the map in a single control loop iteration without degrading the quality of the map very much. The example above also highlights that such real-time capability must be guaranteed not only in static but also in dynamic scenarios when considering mobile robotics applications. In other words, it is necessary to provide for mobility and multi-hop in order not to restrict the freedom of the team members. It is also necessary to provide support for message priority allowing for both task planning of the whole system and for carrying different flows of messages (consider for example control and supervision flows). 1.4 Quality of Service considerations In certain fields of application, the possibility of managing another type of traffic together with the real-time traffic could be useful. For example, some type of multimedia communication could be established while the real-time capabilities of the network are still guaranteed. Although multimedia flow has strict time requirements, it can not be treated as a real-time flow. It might therefore be a good idea to take into account these flows considering another constraints. Quality of service (QoS) is defined as the performance level of a service offered by the network to the user. The goal of QoS provisioning is to accomplish better delivery of the information carried by the network and better utilization of the 6 Introduction 1.4. Quality of Service considerations network resources [Reddy 06]. In the literature, the QoS challenge in ad hoc networks has been faced by trying to guarantee limited end-to-end delay and minimum bandwidth for specific flows. These requirements arise with delay sensitive applications such as video and audio streams. In a wireless environment, however, it is difficult to guarantee QoS given the unpredictability of the medium. Moreover, it is a major challenge to distinguish between frame losses due to collisions and congestions, or erroneous receptions because of a high bit error rate. The distributed scheme and the dependency on other stations to forward data frames in multihop communications further aggravate the problem. In order to specify QoS requirements, application protocols have to consider a set of metrics to define constraints. An application may typically request a particular QoS by specifying its requirements in terms of one or more of the metrics presented in the following list. These metrics, especially those measured at lower layers, are not of direct interest to the application layer. However, they all directly or indirectly affect the QoS of a data session. Network Layer Metrics Throughput It is the desired data throughput for the application. Most of Adhoc network routing technique using this metric/constraint. Delay The End-to-End Delay (E2E) represents the delay from source to destination experienced by a packet to be transmitted across a network. Multimedia traffic is delay-sensitive and live audio-visual communication requires that the endto-end delay be less than a certain value. Thus, audio/video applications usually define the maximum admitted E2E: the global value has to stay of less than some levels to ensure good interactivity between users [Chen 99]. Jitter Jitter is the measure of the variability over time of the latency across a network. In other words, it represents the variation in the delay of received packets in a flow, measured by comparing the interval when the packets were sent to the interval at which they were received. Jitter turns out to be an important QoS parameter in audio stream, which is strongly related to synchronization and packet buffering along the network [Wang 05]. Packet Delivery Ratio (PDR) The acceptable percentage of total packets delivered at the final destination node, which are sent by the transport or higher layer agent from the source node [Abdrabou 06]. PDR is one of the most popularly used metric for assessing a link’s quality and it could be used as a main determinant for rate selection decisions or routing. 7 1.5. 802.11 for Real Time Wireless applications? Introduction MOS Previous metrics can be measured quantitatively, but multimedia quality can require human interpretation even though a quality estimate can be made by automatic test systems. Mean Opinion Score (MOS) [ITU-T 99] provides a numerical indication of the perceived quality of received media after compression and/or transmission of multimedia (audio, voice telephony, or video). The MOS is expressed as a single number in the range 1 (lowest perceived quality) to 5 (highest perceived quality) and is generated by averaging the results of a set of standard and subjective tests. Link and Physical Layer Metrics SINR Signal to Interference plus Noise Ratio (SINR) represents the extent to which the power of the received signal exceeds the sum of noise plus interference at the receiver. Recent studies have considered SINR to be the most appropriate metric for quantifying the quality of a link. However, the instantaneous SINR value cannot be easily computed because commercial wireless cards do not report it during the reception of a packet [Vlavianos 08]. BER Bit Error Rate (BER) represents the ratio of bits with errors to the total number of bits that have been received over a given time period. In others words, BER measures the probability that a bit gets flipped, i.e. it is received in error. This is one of the most important measures of digital communication performance [Goldsmith 05]. However, measuring the BER is a non-trivial task and, in practice, no commercial card implements the BER measure. RSSI Receive Signal Strength Indication (RSSI) is a dimensionless quantity which represents the signal strength observed by the receiver during packet reception. Although RSSI is not considered as the best stand-alone metric because it does not capture the amount of destructive interference on links, it is easy to measure. Commercial cards provide the RSSI while receiving packets. Under certain conditions, this can be considered a promising metric [Srinivasan 06]. Link Stability Variations in the received signal strength and the asymmetrical behavior of links may provide a hint of the movement pattern of the connection peers and thus allow an estimation of a probable connection loss [Wang 06]. However, received signal strength is largely dependent on actual radio conditions. Due to fading effects these measurements are subject to large fluctuations. 1.5 802.11 for Real Time Wireless applications? As explained earlier, real-time communication is necessary in applications where shared information is time-sensitive, as for example applications involving robot 8 Introduction 1.5. 802.11 for Real Time Wireless applications? teams. Commercial wireless devices are based on IEEE 802.11 which has become the standard for wireless networking thanks to its wide diffusion. Its standardisation and the low price of the devices have been the key factors for its wide acceptance. However, the 802.11 protocol does not offer any facility to support the exchange of time-sensitive data in MANETs because it lacks deterministic behavior. It uses a random backoff mechanism for medium access and collision resolution. This makes the use of this solution impossible in real-time networks where all the phases of the communication are required to be time-bounded. Moreover, the protocol is not able to manage (natively) multi-hop peer-to-peer communication, and mobility is restricted to the collision domain shared by the members of the network. Random backoff Neither the backoff nor the RTS/CTS mechanisms eliminate the possibility of collision. In fact, two or more stations can choose the same backoff period and begin transmission at precisely the same moment. Moreover, the presence of random factors in transmission deferral implies timing indeterminism in information exchange. This factor can lead to situations such as the false blocking problem [Ray 03] that can completely jeopardize the operation of a wireless network. This precludes the use of the plain 802.11 protocol for real-time communication and demonstrates the need for a deterministic alternative. Multi-hop The 802.11 was intended primarily to grant wireless access to the internet by means of access points connected to the network infrastructure. In this configuration, all the stations must be able to communicate directly with the access point that distributes the frame acting as a bridge. The ad-hoc mode allows, instead, peer-topeer communication but, as stated earlier, does not support multi-hop. Stations in their respective communication range can communicate with each other but 802.11 does not provide any routing algorithm to propagate information among nodes which are far apart. This feature has to be implemented by means of upper layer routing protocols such as AODV [Perkins 03], DSDV [Perkins 94], etc. However, regardless of the overhead introduced by the routing protocol used, end-to-end bandwidth is highly dependent on network topology and the number of nodes in the network. In fact, according to [Sobrinho 99], a transmission can cause interference in a range larger than the communication range (almost twice the latter). Nodes within the carrier sensing range of a transmitting node can sense the carrier of the sender even if they can not hear the frame, and thus delay its transmission. According to our research, in relatively small wireless networks there can be situations where each node can only communicate with its predecessor and its successor, and carrier sensing does 9 1.5. 802.11 for Real Time Wireless applications? Introduction L P p θ d D = kd Figure 1.1: Visual representation of a zone in which neither spatial reuse nor broadcast dissemination is possible. not allow spatial reuse (i.e. only one node can transmit at a time). In short, sometimes neither spatial reuse nor broadcast dissemination is possible. Let us show an example: consider dto be the communication range of two nodes and D=kd the corresponding carrier sensing range (defined as the distance within which a node will detect an existing transmission with high probability by using the physical carrier sensing mechanism [Yang 05]), proportional to dby means of the constant k. Nodes within carrier sensing range of each other will not transmit at the same time since they consider the channel to be busy. Carrier sensing range is usually considered to be at least 2.2 times the communication range. The ns-2 simulator [NS2 11], for example, fixes by default the communication range at 250 m and the carrier sensing range at 550 m. Experimental results give even worse scenarios, especially for high rates [Anastasi 04]. In the light of this, if we impose the conditions (consider fig. 1.1):      L≤d P < D =kd p>d (1.1) Lbeing the distance between adjacent nodes, pbeing the minimum distance between each pair of non-adjacent nodes and Pthe maximum distance between each pair of nodes, we can find networks in which all the nodes are in the carrier sensing range of each other and each node can communicate only with its adjacent neighbors (single transmitter area, STA). Considering k= 2.2, for example, a network with nodes in twelve of the thirteen vertices of a regular tridecagon with edges L= 0.52dwould satisfy these conditions. Moreover, the greater the value of 10 Introduction 1.6. Goals and contributions k, the larger the STA. Since during the free movement of the nodes a topological configuration like the one described in the previous example could be achieved, this must be taken into account when designing a routing algorithm, especially a real-time one. In such a situation, the end-to-end bandwidth depends on the number of hops separating the sender from the receiver. The worst-case situation occurs when the source and the destination are n−1 hops away, nbeing the number of nodes in the network. In this case the available bandwidth of the 802.11 protocol can be expressed as: BWend to end =BWchannel (n−1) (1.2) In [Ng 07], through simulation and experimental results, the authors show that in a four node chain 11 Mbps network, end-to-end throughput can reach values close to 2 Mbps, whereas for a six node chain the result is approximately 1.2 Mbps, values that match the calculus above. In short, even though use of the 802.11 protocol is very widespread thanks to its notable characteristics such as its relatively high bandwidth, good communication range and the low cost of the devices, it does not constitute an option for realtime communication in robotics due to the lack of multi-hop support and the indeterminism that affects the MAC layer. 1.6 Goals and contributions As has been seen, developing a real-time MANETs and its application involves a set of challenges whose solution remains open. This PhD thesis addresses a set of problems related with the use of a real-time ad-hoc network applied in actual applications. The RT-WMP protocol, developed at the University of Zaragoza, is used in order to provide an effective network amongst nodes. At the time of writing, this protocol seems to be one of the few solutions that allows real-time characteristics to be guaranteed for wireless networks that has actually been implemented, to the best of our knowledge. No protocol with all of these features has appeared in the literature. Starting from the protocol definition, we make an in-depth evaluation and analysis of the protocol. The first contribution of this work is to characterize the protocol in terms of both theory and practice. This results a practical evaluation of a type which can scarcely be found in the literature given that most network evaluations are carried out in simulated environments. The second contribution involves meeting the requirements for multimedia flow support in addition to real-time support. This is possible offering QoS, together with real-time support, by means of developing an extension to the protocol. The 11 1.7. Structure of the Thesis Introduction extension capability offers the possibility of establishing voice and video links among mobile nodes without altering the worst-case characteristics of the RTWMP, taking advantage of the fact that the basic protocol works in worst-case situations in very few cases. The development of a real-time wireless protocol with QoS capability is of great interest in applications such as rescues in disaster scenarios involving humans. In this context, confined areas are of particular interest from the point of view of the difficulties of providing an efficient communication service. This stems from the fact that in environments such as tunnels or mines, common radio systems provide an ineffectual or at best a very limited communications capability. A third contribution of this thesis is towards to perform a study about some signal propagation aspects and a set of real measurement in this kind environments. This environment characterization is in view of perform real underground communication applications using MANETs. A third contribution of this thesis is the study of certain aspects of signal propagation and the provision of a set of real measurements in confined environments. This environment characterization is achieved through the application of real underground communication systems using MANETs. In fact, the latter contribution is the implementation of a set of field applications in confined settings where the protocol performance and effectiveness are demonstrated from the points of view of real-time characteristics, QoS capabilities and specialization to the specific environment. 1.7 Structure of the Thesis This thesis is organized as follows. In the next chapter the basic protocol RT-WMP and its characteristics are presented. Chapter 3 is dedicated to a thorough evaluation of the protocol, taking into account theoretical timing features, real measurements, mobility capabilities and a comparison with a general purpose protocol. The chapter also presents an analysis of the protocol considering the planning of tasks, compliance of timing requirements and overload. Chapter 4 details the QoS extension of the protocol that introduces a technique to allow the delivery of multimedia messages with few overheads and the management of variable priority messages without compromising the RT-WMP worst-case end-to-end delivery delay. Chapter 5 examines the possibility of applying the protocol in confined areas. A study is carried out and a set of real measurements obtained relating to the propagation of the wireless signal and the metrics used for the MANETs. The work is focused on so-called fading environments, providing an analysis of the signal propagation in order obtain the general characteristic parameters of this kind of environment. 12 RT-WMP Definition 2.3. Frames Definition authorization max_pri max_pri_id age lack nstat LQMres serial type src dst aut_src aut_dst prioritymsg_src msg_dst len message header (drop) token message 111111 11 121 1 1 1 2 0..M T U n n2-n nyr nyr n (bit) n (bit) Figure 2.2: Frames of the protocol. Field size is expressed in bytes. priority level of the MPM in the network and its owner amongst the set of nodes already reached by the token. The node which initiates the PAP states that the highest priority message in its own queue is the MPM in the whole network and stores this information in the token. Then it sends the token to another node, which checks the messages in its own queue. If the node verifies that it holds a message with a higher priority than the one carried by the token, it modifies the token data and continues the phase. The last node to receive the token, which knows the identity of the MPM holder, closes the PAP and initiates the ATP. In this phase, the node calculates a path to the MPM holder using the topology information shared amongst the members of the network (the Link Quality Matrix, see below) and sends an authorization message to the first node in the path. The latter will route the message to the second node in the path and so on, until the authorization reaches the MPM holder. This is when the MTP begins. The development of this phase is quite similar to the preceding one. The node that has received the authorization calculates the path to reach the destination, and sends the message to the first node of the path. The message follows the path and eventually reaches its destination. Phases repeat one after another i.e., when the MTP finishes, the node destination of the message initiates a new PAP an so on. When none of the nodes have a message to transmit, the authorization and message transmission phase are omitted and priority arbitration phases repeat continuously. The succession of events that can bring to the delivery of a message (a succession of PAP, ATP and MTP or PAP and MTP or even a single PAP if there are not messages to be send) are called loop. This can be seen also as the time lapse between two consecutive PAPs. 2.3 Frames Definition In figure 2.2 frames exchanged amongst nodes are presented. The frames have a common header and an extra part that is different for each frame type. In the header, the first byte (res) is reserved for communication between the network interface card (NIC) driver and the RT-WMP process. The serial field contains the serial number of the frame. This field is used in the error recovery mechanism 19 2.4. The Link Quality Matrix RT-WMP Definition (see sec. 2.7) together with the retries field (1 byte). The type field identifies the type of the frame (token, authorization, message or drop). The src and dst fields contain information about the source and the destination of the frame. In fact, in the RT-WMP, nodes are identified through a natural number between 0 and n−1 called the WMP address, nbeing the fixed number of the nodes in the network. When a node needs to send a frame (of any type), it fills the src and dst fields of the header with its WMP address and the WMP address of the destination node and broadcasts the frame. Since the radio channel is shared, all the neighbors of the sender hear the frame but only the destination processes it. The token frame adds the max pri and max pri id fields that carry the MPM priority level and the MPM holder WMP address. The age field is used to keep track of the oldest message amongst messages with the same priority level. The lack field is used for belated acknowledgement of the sender (see sec. 2.5.3). The nstat field is an array of nbytes. The value nstat[i] represents the status of the pinode that can be unreached, reached, lost and searched. Finally, the LQM field contains the LQM. The authorization frame adds the aut dst and aut src fields that carry the address of the destination node and of the source of the authorization to the common header and the nyr variable length field (1 bit for each one of the nodes in the network), also present in the message frame that is used to avoid infinite loops in authorization and message delivery (see sec. 2.7.1 for details). The message frame type holds the msg src and msg dst field that contain the WMP address of the source and of the message destination. The priority and len fields hold the priority and the length of the data carried by the frame as well. The field data contains the payload of the frame, which can have a length between 0 and MTU bytes. Finally, the drop frame is a simple header and is identified through the type field. 2.4 The Link Quality Matrix To describe the topology of the network, RT-WMP defines an extension of the network connectivity graph (as defined in [Facchinetti 05]) adding nonnegative values on the edges of the graph. These values are calculated as functions of the radio signal between pairs of nodes and are indicators of link quality between them. These values are represented in a matrix called the Link Quality Matrix (LQM), the elements of which lqmij[0, max lq] describe link quality between piand pjnodes (see figure 2.1). Each line LQMkdescribes the links of the pknode with its neighbors. Even if the links can be asymmetric (the radio signal received by piwhen pjtransmits can be different from the one received by pjwhen pitransmits), generally the differences are very small. In any case, at the moment of computing the path using these values, the protocol chooses the minimum value lqmij(min) between the two correspondent in the matrix (lqmij(min) = min(lqmij, lqmji). Consequently, at any moment the protocol is working with a symmetrical LQM. The nodes use this matrix to select which node to pass the token to and to take decisions on the best 20 RT-WMP Definition 2.5. Phases of the Protocol path to route a message from a source to a destination. All the nodes have a local copy of the LQM that is updated each time a frame is received. Besides, every node is responsible for updating its line of the LQM (both in the local copy and the shared copy) to inform the other nodes about local topology changes. 2.5 Phases of the Protocol In the following sections, we offer a detailed description of the three phases of the protocol. Let us suppose that all the nodes know the network topology (i.e. all the nodes have the same LQM) and that the network is connected. In these sections, we also presuppose that the nodes stay put and that communication is error free. These limitations will be treated in the sections 2.6 and 2.7 respectively. 2.5.1 Priority Arbitration Phase The first phase is the priority arbitration phase. When a pknode initiates the PAP, it creates a new token, copies its local LQM in the relevant field of the token and sets the nstat[i] to unreached ∀i∈[0, n −1] : i6=k. The value nstat[k] will be set instead to reached. This means that, in the current PAP, none of the nodes have been reached by the token yet, except the pknode. Afterwards, it checks the priority level of the highest priority message in its transmission queue and sets the max pri and max pri id fields with this value and its WMP address respectively. The age field is filled with the age of the message (i.e. the time that the message has spent in the queue up to that moment) expressed in milliseconds. In this way, the pknode is stating that it is the MPM holder. Then, it analyzes the LQM to know with which pbl node it shares the best link quality, and sends the token to it. When pbl receives the token, it sets the nstat[bl] to reached, updates the LQM token field with its local data and saves the matrix locally. It subsequently increases the value of the age field by a quantity equal to the duration of one token-pass hop, in order to update the age of the message that the token refers to. Then it looks for the value of the max pri field of the token and compares it with the priority level of the highest priority message in its queue. If it verifies that it holds a higher priority message, it modifies the max pri and max pri id fields. If it holds a message with the same priority, however, it checks the age field of the token. If the message is older than the one carried by the token, it updates the token as well. Subsequently, it chooses the node with which it shares the best link quality amongst the set of nodes not yet reached, and sends the token to it. If a node only listens to its predecessor (i.e. the node that passed the token to it), it can return the token to the predecessor after updating. This means that a node can receive the token several times during the same PAP. In that case it has the right to update the max pri and max pri id values. This behavior helps reduce the well-known priority inversion problem. The process is repeated until all the 21 2.5. Phases of the Protocol RT-WMP Definition nodes have been reached by the token (i.e. nstat[i] = reached ∀i). The last node to receive the token knows the MPM holder’s identity (which is contained in the max pri id field) and is responsible for sending it the authorization. This node ends the PAP and initiates the ATP. 2.5.2 Authorization Transmission Phase First of all, the node that starts the ATP calculates a path to reach the destination node. To do this, it applies the well known Dijkstra algorithm [Dijkstra 59] to a distance matrix derived from the LQM as described in section 2.6.3. The Dijkstra algorithm returns a path to the destination as a set P={pp1..ppm}of nodes. Then the node creates an authorization and fills the aut dest and aut src fields with the MPM holder address and its own address respectively, and sends the authorization to the first node of the path. When pp1receives the authorization, it looks at the aut dest field and if it contains its address, it ends the ATP and initiates the MTP. Otherwise, it calculates the P0={p0 p1..p0 p(m−1) }path, where p0 pk=pp(k+1) k<m. In other words, since the calculation is executed over the same LQM, the path calculated will be the same, except that the first hop has already taken place. Since all the nodes have the same topological information, recalculation of the path in each hop allows the saving of the bandwidth needed to propagate it. The node repeats the process just explained, routing the message to the next member of the path, leaving the aut dest field unchanged. 2.5.3 Message Transmission Phase When the MPM holder receives the authorization to transmit, it takes the highest priority message out from its transmission queue, creates a new message frame and places the data in the data field. It fills the msg src and msg dest fields with its address and with the destination address and calculates the path to the destination, just like in the ATP. Then it fills the priority and len fields with the message’s priority and data length and sends it to the first node that belongs to the path. When the latter receives the message, it checks the msg dest field. If it contains its address (i.e. if it is the destination) it pushes the message into the receiption queue and starts a new PAP. Otherwise, it repeats the computation of the path and repeats the process just explained, routing the message to the next member of the path and leaving the msg dest field unchanged. An explicit acknowledgment is not included because it would create too much overhead. However, if the message reaches the destination node, the latter introduces its WMP address in the lack field of the new token before initiating the new PAP. During this PAP, the token will reach the sender of the previous message, who can check if the message has been delivered or not by looking at the lack field. 22 RT-WMP Definition 2.6. Mobility Management 2.6 Mobility Management Topology can change frequently in MANETS. If nodes are moving, the radio signal and therefore link quality amongst them varies and these changes must be rapidly reflected in the global status of the network. Consequently, when a node discovers a change, it has to propagate this information as soon as possible. In RT-WMP this task is carried out by the token in the PAP phases. In fact, topological information travels with it in the LQM and is updated in each hop. 2.6.1 LQM Updating As explained earlier, each line LQMkof the LQM describes the links of the pknode with all the nodes of the network. Nodes can easily obtain information to fill the relevant line of the matrix. In fact, when a node sends a frame of any type, its neighbors - due to the broadcasting nature of the wireless medium - listen to the transmission and read the radio signal from the network layer to update its local LQM. These changes have to be reflected in the shared LQM as soon as possible, to allow the nodes to correctly calculate the paths in the ATP and MTP. Therefore, when a pknode receives a token, it updates the LQMkline of the LQM token field, saves the whole matrix locally to use it in the successive ATP and MTP, and then retransmits it. Since the LQM reaches all the nodes frequently, they have accurate and up-to-date information on the network’s (link-quality) topology. Consequently, if two nodes are moving away from each other, link quality will gradually fall until it reaches a value close to zero, after which the link is lost. This value is reflected in the LQM, and nodes, whenever possible, will avoid that link to route information when link quality is beneath a certain threshold. In any case, due to the technique used to update the LQM, the value 0 never would appear, and the last positive value would be maintained until an error were verified (see section 2.7). To avoid this behavior, a timeout on the validity of the values of the local LQM elements called LQM Element Validity Period (LEVP) has been introduced. If the pknode has a local LQM where lqmkl >0 but does not hear a transmission from node plwithin a certain timeout, then pksupposes that plis not near it yet, and sets that value to 0. In this way, in the successive PAPs other nodes will know that pkcan not communicate with planymore and avoid this link for subsequent paths computation. The frequency with which each node receives the token and thus update the LQM, depends on the number of nodes, on the maximum message size and on network rate. However, as it is easily to calculate, it hover around few centimeters for common rates and moderate speeds. However, there is an additional method to maintain the LQM up-to-date. When a node sends a token, all of its neighbors receive the frame. While the destination processes the frame and makes the appropriate decision, the other nodes update their local information on link quality with the sender, as explained earlier. Moreover, if the frame received contains a 23 2.6. Mobility Management RT-WMP Definition more recent LQM they can use it to update their own. 2.6.2 Maintaining a fresh LQM These techniques guarantee that LQM reflects the topology of the network well in the most part of the situations. However, there exist a particular configuration in which the quality of the information contained in the LQM can degrade fastly. Let consider a chain network p1..pnin which pastarts the PAP and pais always (or during a long period interval) the owner of the most priority message which destination is, in turn, pa. The PAP will develop as pa→pb. . . →pn, then pn will authorize itself and will send the message to pathrough the chain. In this configuration, the pnnode never has the possibility of sending its own view of the network (its LQM) and if it is moving, for example, the other nodes can not know the status of the links. To avoid this behavior a technique to force the execution of a worst-case PAP has been introduced in the protocol. When a node is not able to propagate its LQM during a configurable number of loops, it can request to force a worst-case PAP in which all the node have the opportunity of sending a token frame. In the example above, node pncan force a worst-case PAP, modifing the token frame when received: it states that node pbhas not been reached in the current PAP and send the token back to pn−1that propagate it back up to p2where the 2n−3-hops PAP ends. This technique does not alter the real-time behavior of the protocol since, as anticipated, the planner has always to take into account the worst-case duration of each one of the RT-WMP phases. 2.6.3 LQM Elements and Path Calculation As mentioned earlier, the lqmij elements of the LQM are functions of the radio signal links between nodes. To calculate them, we use the Received Signal Strength Indicator (RSSI) defined by the 802.11 protocol. The physical sublayer measures the energy observed at the antenna used to receive the current frame. Normally, 802.11 devices provide this value to the device driver. Besides, some card models provide information on noise as well. With these two parameters, we can estimate the Signal to Noise Ratio (SNR) for every frame received and estimate link quality between nodes, representing it with values in the [0, max lq] range that are then treated by means of configurable moving average or median filters to eliminate noise and spurious values reported in the RSSI measurement by the wireless network card. The calculation of the path in the ATP and MTP is based on these values. The links are divided in five categories (no link, bad link, average link, good link, stable link) with different weight, being the stable link the lightest and a matrix Mis calculated from the LQM applying this filter. After that, the worst links are eliminated if possible using a simple algorithm: 24 RT-WMP Definition 2.6. Mobility Management 1 WL = M.getWorstLink() 2 if WL == bad_link or WL == average_link 3 M.remove(WL) 4 else 5 exit 6 endif 7 if M.connected() 8 goto 1 9 else 10 M.restore(WL) 11 M.markChecked(WL) 12 end if Consider a connected network: the worst link WL is selected. If it is not a bad link nor an average link the algorith exits. On the contrary it is eliminated. If the network is still connected, the change is accepted and the algorithm restart. On the contrary the link is readmitted and the algorithm restart again. With this trivial piece of code, is possible to eliminate the worst links maintaining the network connected and selecting only the links that can give a certain guarantee on its reliability (if it is possible). After this filter, the Dijkstra algorithm for the single-source shortest path problem for directed graphs with nonnegative edge weights is applied to the graph represented by the matrix M. Computation time is not actually an issue (networks are usually small), since the Dijkstra algorithm has a O(V2) complexity, V being the number of vertices, whereas the implementation of the algorithm’s priority queue with a Fibonacci heap makes the time complexity O(E+V logV ), where E is the number of edges of the considered graph. 2.6.4 LQM Initialization When a RT-WMP network begins, the nodes do not have topological information. Therefore, an additional step to setup the initial LQM is required. This is an easy and bounded time process in which, however, real-time behavior is not guaranteed. When a node is started, first of all the values lqmij of the LQM are all set to lqminit ij =maxlq + 1. In this way, all the nodes consider that they are in a fully connected network. Then, all the nodes start to listen to the medium during a waiting period that depends on the WMP address of each one; the lower the WMP address, the shorter the period. If during this period they hear a protocol frame, it means that there already exists an active network. In this case nodes will be incorporated in it following the procedure specified in section 2.7.2. Otherwise, at the end of the shortest waiting period, the correspondent node wakes up and 25 2.7. Error Handling RT-WMP Definition 0 1000 2000 3000 4000 5000 6000 7000 8000 9000 −10 −5 0 5 10 Sample # ∆RSSI Figure 2.3: Asymmetrical behavior of links. starts a normal PAP. Since its LQM represents a fully connected network, it chooses one of the nodes (generally starting with the one with the lowest WMP address) and sends it the token. If that node is not in its communication range, the sender will not receive the implicit acknowledgement and, after timeout, resets the corresponding value of the LQM and sends the token to another node. The process repeats up to the moment in which the token is sent to a node that is effectively in the communication range of the sender. At this moment the receiver continues the PAP in the same way assuming, however, the LQM is partially updated by the first node. The propagation of the token continues in the same fashion up to the moment in which the nodes share a real LQM. The lack of implicit acknowledgement and the timeout on the validity of the LQM elements, in fact, will rule out inexistent links. As mentioned, the process has a bounded duration (equal to LEVP). However, it can be considered concluded when no lqminit ij values are present in the shared LQM. 2.7 Error Handling The RT-WMP provides The error recovery mechanisms of RT-WMP have been designed not to jeopardize real-time behavior of the protocol and to maintain the network temporization in the majority of possible situations of error. 2.7.1 LQM Misalignment Even if nodes receive the complete LQM frequently, sometimes a slight misalignment of the LQM can occur due to the fact that links are not usually completely 26 RT-WMP Definition 2.7. Error Handling 1 (1) 2 (2) 3 (3) 3 (4) 4 (4) 4 (5) 4 (6) Original token Duplicate token Drop frame n : token serial (n): time 3 p 1 p 4 p 2 p 5 p6 p Figure 2.4: Token duplication resolution mechanism. In case of message or authorization duplication the mechanism works in a similar way. symmetric. Figure 2.3 shows the raw difference between the RSSI (∆RSSI) registered by a pair of fixed nodes communicating with each other at a distance of about 150 m. After filtering, the difference is usually very small but it is not always negligible. This can lead to slightly different matrices in different nodes. If these differences cause a different categorization of the links in terms of weights within the LQM (see section 2.6.3, undesired behavior can take place during the routing. Let us consider the case in which pk,pa,pbcan hear each other and that pk has to send a message to a fourth node pcthat only paand pbcan hear. When pk computes the path, it considers that the best is, for example, pa,pk,pc. However, when the message reaches pa, the latter considers, due to a small misalignment of the LQMs among nodes, that the safer path is pb,pcand instead of passing the message directly to pc, it passes it back to pb. In the same way, pbcan consider, instead, that the safer path is pa,pk. In this situation, the paand pbnodes would pass the message to each other indefinitely. To avoid this situation, during both authorization and message delivery, when a node receives a frame, it sets its corresponding bit in the nyr field before propagating it. The receiving node applies the mask constituted by the string of bits to the LQM setting lqmij = 0 and lqmji = 0 being ithe local node and jthe node corresponding to the set bit. With the additional step just described, when pbreceives the message for the first time, it discards the possibility of sending the message back to paavoiding, in fact, the possibility of infinite loops and guaranteeing the upper bound of n−1 hops even in the event of misaligned LQMs. 2.7.2 Node Failure or Node Loss RT-WMP is quite robust in case of node failure. The implicit acknowledge technique used dispenses with the necessity of monitoring nodes to control the loss of the token. In fact, in common token-pass systems with explicit acknowledgement, when a node receives a token, it acknowledges the sender with a message. However, 27 2.7. Error Handling RT-WMP Definition if a node fails just after the acknowledgement, the token is lost and a technique to regenerate it is required. In RT-WMP, however, when a pknode sends a frame of any type, it listens to the channel for a timeout. The receiver plnode immediately processes the frame received and sends another frame to a third pmnode (that can be its predecessor as well). The first sender listens to such a frame as well and interprets it as an acknowledgement. This technique permits saving of bandwidth and eliminates the need for a monitor node. In any case, if the first sender does not hear the frame within timeout, it supposes that the plnode has failed or is out of its coverage range. In this case, the behavior depends on the phase that the protocol is in. If it is in the ATP or MTP, pkdiscards the frame and starts a new PAP. In fact, it is impossible to calculate another path since this could jeopardize the temporization of the network (see section 3.1.1). However, if it is in the PAP, pknode sets the nstat[l] field to reached, modifies the local LQM and the LQM carried by the token to exclude the plnode from the set of its neighbors (setting lqmkl = 0) and continues with the PAP, sending the token to another node. This solution excludes the plnode in the current PAP to preserve network temporization but not necessarily in the next PAP. In fact, it may be that there are other nodes which consider plto be their neighbor. If plhas not actually failed but, for instance, has moved away from pknode but not from another neighbor pm, the latter will reinsert plin the next PAP by simply passing it the token with no additional cost. If, however, the node is actually broken or has moved away from all the other nodes, in the next PAPs all its neighbors will try to pass the token to it one after another (one in each PAP) until plis isolated. When this occurs, the node that starts the next PAP marks this node as lost setting nstat(l) = lost +r where ris a number between 0 and n−1 and prdoes not belong to the set of lost nodes. Reinsertion of lost nodes. The number rrepresents the identity of the node that has to search for the lost node in the current PAP. Nodes, in fact, could reappear, but it is impossible to predict where. Consequently, nodes that still belong to the network organize themselves to search for the lost node one after another in the successive PAPs. When prnode receives the token, it looks at the nstat array. If one of the elements contains the value lost +r, (in this case nstat[l] = lost +r), it tries to send the token to pl. If the latter (implicitly) acknowledges the frame (i.e. passes the token to another node or back to pr), it is reinserted in the network with no additional cost. Otherwise, (i.e. plnode does not acknowledge) node prsets nstats(l) = searched +rand continues the PAP. None of the other nodes try to search for that node in the current PAP, since this would break the network temporization (see 3.1.1 for details). The node that starts the next PAP modifies the field nstats to nstats[l] = lost + ((r+ 1) mod n) if p(r+1) mod n node is not a lost node and continues the PAP. In this manner all the nodes not lost will search 28 RT-WMP: Evaluation and Analysis 3.1. Real-Time Features Figure 3.3 shows in a simplified form how data packets are transmitted in the 802.11 protocol. The TDAT A is the time needed to send the payload Land the additional data (preamble, etc.), TSIFS the Short InterFrame Space, TACK the time needed to send the acknowledgement, TDIF S the duration of the Distributed InterFrame Space and TBO the minimum backoff time mentioned in 2.1. The time T802.11 needed to send a frame is then: T802.11(L) = TDIF S +TBO +TDATA(L) + TSIF S +TACK (3.5) when the RTS/CTS mechanism is not used and: TRT S/CT S(L) = TDIF S +TBO +TRT S +TSIF S +TCT S+ TSIFS +TDATA(L) + TSIF S +TACK (3.6) The RT-WMP protocol does not need explicit acknowledgement (uses implicit) nor backoff mechanisms or RTS/CTS frames (the token passing technique used avoids the need for collision avoidance mechanisms) and the trasmission scheme of a single RT-WMP frame is simplified in this manner: TRT −W MP (L) = TDIF S +TDATA(L) (3.7) being Lthe length of each one of the frames to be sent. This approach guarantees a more efficient raw use of the available bandwidth. However RT-WMP is a three phases protocol and to deliver a data message needs to send several additional frames. The TRT−WMP should be thus written as: TRT −W MP (L) =hP AP ·[TDIF S +TDAT A(stoken)]+ hATP ·[TDIF S +TDATA(sauth)]+ hMT P ·[TDIF S +TDATA(smessage +L)] (3.8) being hPAP ,hAT P , and hMTP the number of hops of the correspondent frame in the PAP, ATP and MTP respectively, stoken,sauth and smessage the size of a token, authorization and message frame respectively. The values of all the mentioned 802.11 elements (TDIF S,TACK, etc.) depend on the network data rate and on the modulation technique used (see [Jun 03] for more details) but has a strong influence on the efficiency of the 802.11 networks defined as: =TMT R(3.9) 35 3.1. Real-Time Features RT-WMP: Evaluation and Analysis 64128 256 512 1024 2048 2412 0 10 20 30 40 50 60 70 80 90 100 Data Size (B) Efficiency (%) 1 Mbps (DSSS) 2 Mbps (DSSS) 5.5 Mbps (DSSS) 11 Mbps (DSSS) 6 Mbps (OFDM) 12 Mbps (OFDM) 24 Mbps (OFDM) 54 Mbps (OFDM) Figure 3.4: Efficiency of a RT-WMP five-nodes completely connected network. being TMT the Theoretical Maximum Throughput (TMT) and Rthe declared network rate introduced in [Jun 03]. Similarly the efficiency of RT-WMP depends on these parameters and additionaly on the network size since both hPAP ,hAT P ,hMTP and the size of stoken dependent on this parameter. A simple analysis can discover the behavior of the RTWMP protocol. Figure 3.4 shows the efficiency of a sample completely-connected five-nodes network as a function of the data rate. Adding further nodes to the network will not alter the shape of the graph but will provoke an increment on the convexity of the curves. In any way, as in standard 802.11 networks, the lower the rate the higher the efficiency. Once fixed a sample data rate of 6 Mbps (for being, in our opinion, the best compromise among bandwidth, efficiency and communication range) is it possible to provide concrete values for all RT-WMP characteristics. For this data rate the 802.11 protocol specifies: TDIF S = 34 while TDATA(L) = 20 + 4 ·22 + 8 ·(34 + L) 24 (µs) (3.10) Using this expression it is easy to calculate: 36 RT-WMP: Evaluation and Analysis 3.1. Real-Time Features 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 1 2 3 4 5 6 Number of Nodes Bandwidth (Mbps) 64 B 128 B 256 B 512 B 1024 B 2048 B Figure 3.5: Worst-case bandwidth offered by RT-WMP. ttoken(µs) = TDIF S +TDATA(stoken) = 34 + 20 + 4 ·22 + 8 ·(34 + stoken) 24 µs (3.11) tauth(µs) = TDIF S +TDAT A(sauth) = 34 + 20 + 4 ·22 + 8 ·(34 + sauth) 24 µs (3.12) tmsg(µs) = TDIFS +TDATA(stoken) = 34 + 20 + 4 ·22 + 8 ·(34 + smessage +L) 24 µs (3.13) These values allow the calculation of all the parameters defined in section 3.1.2. Table 3.1 shows the values for different number of nodes and frame size and network configuration. Figure 3.5.a and b show the theoretical maximum throughput for a completely connected network and a worst-case network respectively. Figure 3.6.a shows the relative efficience 802.11 rdefined, for a completely connected network, as: 802.11 r=TMTRT −W MP TMT802.11 (3.14) being TMTRT −W MP the TMT for a RT-WMP network and TMT802.11 the TMT for a standard 802.11 network. Finally figure 3.6.b shows the relative efficience RT S/CT S rdefined, for a worst case network, as: 802.11 r=TMTRT −W MP (wc) TMTRT S/CT S(n−1)−1(3.15) 37 3.1. Real-Time Features RT-WMP: Evaluation and Analysis being TMTRT −W MP (wc) the worst case TMT for a RT-WMP network and the term TMTRT S/CT S(n−1)−1the TMT for a standard 802.11 network using the RTS/CTS mechanism adapted for a nnodes network without spatial reuse. These two last graphs show how much the RT-WMP takes advantage of the available theoretical maximum bandwidth offered by the plain RT-WMP. The results are very interesting especially considering the worst-case situation which is that must be considered at planning time as explained before. The RT-WMP can in fact maintain efficiencies that are above 40% even for relatively big networks (up to 15 nodes). It is important to notice the results do not take into account any routing protocol that, however, must be used on top of the plain 802.11 to allow it to support multi-hop communication and that should add additional overhead. 3.1.4 Testbed The RT-WMP has been implemented to work in different platforms. It can work as a standalone user-space Linux program (the specific application can be linked with the RT-WMP core library), as a module of the Linux Kernel (it provides a set of APIs to communicate with it and also provides virtual interface to the user) and as a library for the real-time operating system MaRTE OS [Rivas 01]. Both the Linux and MaRTE OS implementations can use a dedicated wireless-card driver. This driver, called ath5k raw and developed by the Robotics Perception and Real-Time Group at the University of Zaragoza, is based on the ath5kLinux kernel driver and is compatible with most Atheros-chipset based cards. It allows communication between peers while avoiding the use of high layer protocols (such as IP or UDP) and also avoiding MAC layer frame retransmission. It is capable of returning the RSSI level of each received frame. To evaluate the real-world performance of the RT-WMP, we used the MaRTE OS implementation running on up to 10 nodes equipped with PC Engines ALIX.2D3 System Board with a 500 MHz AMD Geode LX800 CPU, 256 MB RAM and one Engenius EMP-8603 dual band Atheros-based wireless card node running the MaRTE OS version of the RT-WMP. An extra Linux machine was used to sniff the wireless medium, collect the information and analyze the results. Moreover, in the mobility management experiments, we used a MobileRobots’ Pioneer P3AT mobile robot equipped with an onboard Versalogic VSBC-8 PC board (Pentium III at 800 MHz) and an atheros based wireless card. The wireless card frequency was fixed at 5.2 GHz and the data rate at 6 Mbps in all the experiments. In all the experiments the collision domain was free of foreign network interference. The experiments were oriented to verifying and analyzing different aspects. In the following paragraphs the evaluation of the worst-case real-time behavior and throughput is presented. Moreover, the results of additional outdoor experiments are shown to demonstrate the efficient management of the mobility. 38 RT-WMP: Evaluation and Analysis 3.1. Real-Time Features 2 Nodes 3 Nodes 4 Nodes 5 Nodes 10 Nodes Size 64 512 1500 64 512 1500 64 512 1500 64 512 1500 64 512 1500 tt0.131 0.131 0.131 0.139 0.139 0.139 0.149 0.149 0.149 0.163 0.163 0.163 0.269 0.269 0.269 ta0.119 0.119 0.119 0.119 0.119 0.119 0.119 0.119 0.119 0.119 0.119 0.119 0.119 0.119 0.119 tm0.209 0.807 2.124 0.209 0.807 2.124 0.209 0.807 2.124 0.209 0.807 2.124 0.902 0.807 2.124 tpa(wc) 0.273 0.273 0.273 0.417 0.417 0.417 0.748 0.748 0.748 1.141 1.141 1.141 4.584 4.584 4.584 tat(wc) 0.177 0.119 0.177 0.238 0.238 0.238 0.357 0.357 0.357 0.476 0.476 0.476 1.071 1.071 1.071 tmt(wc) 0.209 0.807 2.124 0.419 1.614 4.248 0.629 2.421 6.373 0.838 3.228 8.497 1.887 7.263 19.119 tloop(wc) 0.459 1.057 2.374 1.074 2.269 4.903 1.734 3.526 7.478 2.455 4.845 10.114 7.542 12.918 24.774 ttoken(wc) 0.591 1.188 2.505 1.491 2.686 5.320 2.482 4.274 8.226 3.596 5.986 11.255 12.127 17.503 29.359 tete(wc) 0.919 2.114 4.748 2.148 4.538 9.807 3.468 7.052 14.957 4.911 9.690 20.229 15.08 25.837 49.549 Table 3.1: Theoretical timing delay (ms). 39 3.1. Real-Time Features RT-WMP: Evaluation and Analysis 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 10 20 30 40 50 60 70 80 90 100 Number of Nodes εr 802.11 64 B 128 B 256 B 512 B 1024 B 2048 B (a) 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 10 20 30 40 50 60 70 80 90 100 110 Number of Nodes εr RTS/CTS 64 B 128 B 256 B 512 B 1024 B 2048 B (b) Figure 3.6: Relative efficiency of RT-WMP compared with plain 802.11 protocol considering a completely connected network (a) and a network in which no spatial reuse is possible (b). 40 RT-WMP: Evaluation and Analysis 3.1. Real-Time Features 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 1 2 3 4 5 6x 104 Number of Nodes Loop duration (µs) 64 B 128 B 256 B 512 B 1024 B 2048 B Figure 3.7: Theoretical loop duration for a worst-case RT-WMP network. 3.1.5 Real-time Behavior A 7-node network was arranged in an indoor environment. Since the goal was to determine the worst-case behavior, we provided the nodes with a hard-coded fixed fake LQM to simulate a chain network. In this type of network, it is frequent to have worst-case loops. Priority In the first experiment we verified the priority-based message exchange mechanism. In the arranged network, saturated traffic with random destination and priority p (p∈[1,25], p ∈N) and fixed-size message (1024 B) was generated in all the nodes. The messages were generated with fixed frequency and the nodes had a queue of 25 messages. The wmpSniffer was used to sniff the medium and collect information about the messages exchanged among the nodes. The figures 3.8 and 3.9 show the mean end-to-end delay (from the moment in which the message is pushed in the queue until the delivery to the destination node) as a function of the message priority. Fairness In the second experiment we verified more specifically the fairness for same-priority messages. The importance of the fairness in multi-hop networks, with special attention paid to multi-hop flows, is shown in [Szott 09]. As in the previous experiment, saturated traffic was generated in all the nodes. However, this time all the messages had the same fixed priority. Figure 3.10 shows 41 3.1. Real-Time Features RT-WMP: Evaluation and Analysis 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 0 200 400 600 800 1000 Priority Delay [msec] NODE 1 NODE 2 NODE 3 NODE 4 NODE 5 NODE 6 NODE 7 Figure 3.8: Mean end-to-end delay vs priority for a 7 nodes RT-WMP completely connected network. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 0 200 400 600 800 1000 1200 1400 1600 Priority Delay [msec] NODE 1 NODE 2 NODE 3 NODE 4 NODE 5 NODE 6 NODE 7 Figure 3.9: Mean end-to-end delay vs priority for a 7 nodes RT-WMP chain connected network. 42 RT-WMP: Evaluation and Analysis 3.1. Real-Time Features 930 940 950 960 970 980 990 1000 0 500 1000 1500 2000 2500 Delay [msec] Occurrences Figure 3.10: Mean end-to-end delay vs priority for a 7 nodes RT-WMP chain network. the distribution of the delays for same-priority message for all the nodes. Again, it is possible to appreciate that all the messages suffer from a similar delay in all the nodes. The graph shows a normal distribution with a mean of 962 ms using a queue of 25 messages per node. Notice that the raw value of the end-to-end delay for both experiments depends on the queue size and is not comparable with the values obtained in the theoretical analysis. 3.1.6 Throughput and end-to-end delay To verify the real end-to-end throughput of the protocol we performed two types of experiments. Completely connected network In a first step, we arranged completely connected networks of 2 to 7 nodes. Saturated traffic with random priority and destination was generated in all the nodes. This traffic was sniffed by the wmpSniffer to measure the end-to-end delay of each message exchanged. The bandwidth was then calculated as: BW =P tPAP +tAT P +tMTP (3.16) Pbeing the payload of the message. The experiment was repeated for differentsize messages, from 256 to 1024 bytes. Figure 3.11 shows the results of the experiment both in terms of bandwidth and end-to-end delay. This time, the values do not take into account the time spent by the messages in the queue, i.e.they only 43 3.1. Real-Time Features RT-WMP: Evaluation and Analysis 2 3 4 5 6 7 0 5 10 15 Number of Nodes End to end delay [msec] 1024 B 512 B 256 B (a) 234567 0 500 1000 1500 2000 2500 3000 3500 Number of Nodes Throughput [Kbps] 1024 B 512 B 256 B (b) Figure 3.11: RT-WMP completely connected network Throughput and Etoe for different-size messages. represent the time lapse between the beginning of the PAP in which a specific message is to be delivered and the moment in which the latter reaches the destination node. This means that we are cutting off the blocking time. This aspect will be addressed later both in the real-time analysis and in the subsequent experiments. These values reflect the behavior of the RT-WMP in a hypothetical situation in which all the nodes can communicate with each other. In fact, this is not of great interest from the real-time point of view (as explained before, we always have to consider the worst-case in this type of system) but it is useful to give a rough idea of the maximum bandwidth that RT-WMP can offer if used as a normal multi-hop protocol. The results are similar to those obtained in the theoretical analysis even though a worse behavior can be observed due to the computation time that, as for the 802.11 protocol, was not considered. 44 RT-WMP: Evaluation and Analysis 3.2. RT-WMP vs OLSR 2 3 4 5 6 7 0 500 1000 1500 2000 2500 3000 3500 4000 4500 Number of Nodes Throughput [Kbps] RT−WMP OLSR tcint=5 hint=2 OLSR tcint=0.5 hint=0.1 OLSR tcint=0.05 hint=0.05 Figure 3.16: Rough bandwidth offered by RT-WMP and OLSR protocols. more efficient for medium access since the use of the token passing technique avoids the need for collision avoidance techniques, random backoff delays, MAC-layer acknowledgements and so on. Moreover, the use of IP and UDP layers in the case of OLSR (notice that it works over IP) adds extra overheads to the communication. 3.2.3 Mobility After testing the bandwidth, we were interested in comparing the mobility management of both protocols. We repeated the experiment described in section 3.1.7 for the OLSR protocol with the aim of comparing the results with those obtained for RT-WMP. The figures 3.17 show the results for OLSR. In contrast to the behavior of the RT-WMP, by design the OLSR protocol responds to changes in the topology only when there is some packet loss due to the fact mentioned previously that the link quality is estimated through the PDR. This fact is reflected in figures 3.17.a and 3.17.b. On the one hand, since the link level is not taken into account by the protocol for routing decisions, it is possible to observe that it goes below the limit of −65dBm on several occasions. On the other hand, the routing algorithm does not necessarily provide privilege to the communication with the closest node and this implies that many communication switches among different nodes. In figure 3.17.a, for example, it is possible to observe a large switch between node n1and n2at approximately x≈30m. Even more evident is the switching at x∈[75m, 90m] where three backbone nodes share the work of delivering the messages. These changes are cause and effect of the message losses shown in figure 3.17.b and that in the experiment reach the not negligible value of 5.34%, approximately 30 times more than the RT-WMP. Also the OLSR protocol suffered from long outages during node movement as already 51 3.2. RT-WMP vs OLSR RT-WMP: Evaluation and Analysis 0 10 20 30 40 50 60 70 80 90 100 0 2 4 6 8 10 12 14 16 18 Distance [m] # of lost messages 0 10 20 30 40 50 60 70 80 90 100 −85 −75 −65 −55 −45 −35 −25 Distance [m] RSSI [dBm] RSSI n1 n2 n3 n4 Figure 3.17: Mobility management of the OLSR protocol. highlighted by the experiments described in [Pojda 11]. Moreover, according to the data collected, approximately 0.65% of the messages reached the destination out-oforder. This is an additional problem that is particularly evident when the frequency of sending the messages rises. These limitations suggest that it is probably not a good idea to use such a protocol in scenarios that include mobility, especially if the loss of messages is an important issue (for example in firm real-time control). 3.2.4 Lesson learned The performance evaluation of RT-WMP has shown that it is able to support time sensitive applications even in the presence of mobility of the nodes. The comparison with a general purpose routing protocol showed, moreover, that this type of protocols can not easily be used for time-sensitive mobile applications due to the unpredictability of the end-to-end delay, to the absence of priority support and to the poor performance in terms of mobility management. On the other hand, to be used in a real real-time system a protocol must be analyzable. In the following sections we present an in-depth analysis that provides the user with the possibility of using such a protocol as a communication framework in distributed real-time systems. 52 RT-WMP: Evaluation and Analysis 3.3. Analysis of the protocol 3.3 Analysis of the protocol As has been anticipated, the hallmark of a real-time system is predictability. This feature is associated with the possibility of proving or verifying a priori that the system timing requirements are met in all circumstances. As a result, predictability involves several aspects to be taken into account especially as regards careful planning of tasks and resources,compliance of timing requirements and a controlled overload. Timing intervals are determined by the way the protocol works when it receives an external event (i.e. receiving a frame). Understanding the execution of a task in response to to this event can be helped by knowing the different protocol states and the interaction between them. For this reason, modeling by a finite state machine could be a simple and effective way to describe the dynamic behavior of the protocol. On the other hand, the compliance of timing requirements could be fulfilled knowing a priori the limitations of the protocol in terms of message transmission. Message packets are non preemptible, and therefore there is a bounded Worst case and Blocking time that have to be taken into account during the analysis. In addition, the token based approach makes the protocol dependent on the number of stations, so the additional overheads introduced also have to be considered in the analysis. As regards overload, the processor processing load due to the execution of the protocol has to be taken in account. The design of communication systems without Real Time requirements focuses on maximizing the throughput of the message and minimizing average delay [Tanenbaum 97]. Maximization of bandwidth might not have a high practical value if the communication overheads leave no CPU time to process the data. This aspect is even more significant in the case of embedded systems that generally have more limited processing capability. Bandwidths will decrease if protocol or application processing saturate the CPU, so processor utilization could be considered as important as other communication parameters. In the following section, we perform a real-time analysis of the RT-WMP protocol taking in account the previous issues through a similar methodology as that presented in [Mart´ınez 05] and [Liu 73]. 3.3.1 RT-WMP as a state machine In order to understand its functionality, each RT-WMP node can be described as afinite state machine (FSM). FSM provides a natural and well-understood way to describe the behavior of the protocol and to analyze the feasibility of transitions through the several states, for example by detecting abnormal network operations. Fig. 3.18 shows the states and the transitions between them. They are briefly described below: 53 3.3. Analysis of the protocol RT-WMP: Evaluation and Analysis RECEIVE EVALUATE_AUTH INTERPRET_RECEIVED INTERPRET_ACK EVALUATE_FOREIGN EVALUATE_TKN ENQUEUE_MSG EVALUATE_MSGCREATE_AUTH CREATE_MSG SEND_TKN NEW_TKN WAIT_ACK SEND_ATH SEND_MSG DECODE_RECEIVED DECODE_ACK DISCARD_TKN DISCARD_ATH DISCARD_MSG MSG received Foreign received ATH received Last node To forward To forward To forward To discard To discard To discard ACK received Start PAP MSG for me ATH for me Figure 3.18: RT-WMP state machine in each node. •RECEIV E: The information received is entered in the appropriate queue of the receiving station. •DECODE RECEIV ED: The node updates the LQM token field with its local data and saves the matrix locally. •INTERPRET RECEIV ED: The received frame is interpreted in order to know if it is a token, an authorization message or foreign. •ENQUEUE MSG: The received message is written into the reception queue. It then switches to the NEW TKN state. •NEW TKN: The node destination of the message initiates a new PAP phase. •EV ALUATE TKN: Updates the token if its own priority is higher and sends the token to the next station. It then switches to the Idle state. •EV ALUATE MSG: The node evaluates if it is the destination of the message. •CREATE MSG: After receiving the authorization, the node creates the message. 54 RT-WMP: Evaluation and Analysis 3.3. Analysis of the protocol •EV ALUATE ATH: The node checks if it is the authorization destination or not. It switches to the CREATE MSG or SEND AUTH state respectively. •CREATE ATH: The last node to receive the token, which knows the identity of the MPM holder, closes the PAP and initiates the ATP. Then it switches to the EVA AUTH state. •SEND TKN: The node sends the token and switches to the WAIT ACK state. •SEND ATH: The node sends the authorization and switches to the WAIT ACK state. •SEND MSG: The node sends the message and switches to the WAIT ACK state. •WAIT ACK: The station listens for the arrival of any packet. When a packet is received, a check is made to determine its type in the INTERP ACK state. •DISCARD: The node discards the foreign frame (token, authorization or messages) and switches to the RECEIVE state. •DECODE ACK: The node updates its state with the ack received. •INTERPRET ACK: The node switches to the EVA TKN, EVA AUTH, EVA MSG or EVA FOREIGN state if the frame received is a token, an authorization, a message or an alien traffic frame, respectively. •EV ALUATE FOREIGN: The node evaluates the alien message received. The validation of protocols specified in terms of interacting finite state components can be useful in order to obtain the relevant parameters for the different operations involved in the timing model. 3.3.2 RT-WMP Processor Utilization Let us consider the set Xof all possible states of the RT-WMP’s FSM. To respond to the reception of a frame, the FSM will go through a sequence of states xjX. If we consider Sto be the set of sequences of the FSM states we can define: si={x1, x2, ..., xn}, xjX, siS. (3.17) For example, when a node receives a token, in order to forward it to another node, the protocol executes the sequence of states stkn fwd: 55 3.3. Analysis of the protocol RT-WMP: Evaluation and Analysis Ci Tij int t Free time int int sj si sk delay Tjk Cj Figure 3.19: CPU time spent for the RT-WMP sequences. stkn fwd =RECEIV E →DECODE RECEIV ED →INTERPRET RECEIV ED →EV ALUATE TKN →SEND TKN →WAIT ACK (3.18) When the sequence ends, the protocol leaves the CPU until the next event that provokes a new sequence to be run. The utilization factor of a sequence U(S) is defined as the fraction of time spent by the CPU to execute a sequence taking into account the total amount of time in which the processor is free before executing another sequence. Consider Figure 3.19. The processor is occupied by the execution of the sequence sithat has a computation time Ciand then is free until the execution of the subsequent sequence sj. Defining the period Ti,j as the timespan between the triggering of two consecutive sequences siand sj, the utilization factor U(si) for the generic sequence si can be determined as: U(si) = Ci Ti,j ,(3.19) In other words, the expression U(si) is the percentage of the time that sequence siwill occupy the processor as a response to each frame reception. To reduce the processor occupation the protocol introduces a modulable delay before all send operations. It implies, as obvious, that the computation of the utilization factor of the sequences that include a transmission (like sequence sj in the figure), must avoid to take into account this delay when measuring the execution time Cj. Since we are interested in an upper bound in the processor utilization, we considered the worst-case i.e. the sequence that uses the most resources. Considering the maximum value obtained computing the U(si) for each sequence i, we define the worst-case achievable utilization as: 56 RT-WMP: Evaluation and Analysis 3.3. Analysis of the protocol 2 3 4 5 6 7 0 10 20 30 40 50 Number of Nodes Utilization [%] 2 ms delay 1 ms delay 0.5 ms delay Figure 3.20: RT-WMP CPU utilization vs network size. U=max Ci Ti,j .(3.20) This will be considered as the maximum CPU utilization for the RT-WMP protocol. 3.3.3 Evaluation under MaRTE OS Five nodes equipped with minimal embedded and dedicated hardware (100x160mm PcEngines ALIX3D3 board, battery powered), Atheros chipset-based wireless cards and running the MaRTE OS [Rivas 01] implementation of RT-WMP. Table 3.3 lists the parameter values used in the tests. Utilization Given that the protocol modifies medium access control, it is of interest to find out the protocol overhead added to the processor on which it is running. In order to compute the utilization factor U, times have been measured as in equation 3.20. As explained earlier, the protocol delay before transmission is a parameter introduced to control the use. We considered the impact of the network size on the utilization factor in a completely connected network. Measurements have been repeated for different delay values, 0.5, 1 and 2 msec, respectively. As can be seen in Figure 3.20, protocol delay positively affects the utilization because it leaves more free processing time. On the other hand, network size has a negative effect. This is because in a completely connected wireless network, a node receives all the frames 57 3.3. Analysis of the protocol RT-WMP: Evaluation and Analysis Sequence worst state Utilization RECEIVE INTERPRET_RECEIVED DECODE_RECEIVED EVALUATE_FOREIGN DISCARD TKN – ATH – MSG RECEIVE 20.2% Table 3.2: Main utilization result. in the air, including those that are not for the node in question. Thus, the best situation is a two node network where no discard messages occur. In fact, not completely connected networks are more frequent in real scenarios where packets have to travel on a multihop route to reach a node. The processor occupation can therefore be considered with reference to a value lower than the actual number of nodes in the network. This is the case for example of a network of 7 nodes in a chain where, to achieve maximum coverage in length, a node can only sense the previous node and the following one. As far as the measurement is concerned, we should consider the value of 3 nodes. The sequence with the maximum utilization is that involving the DISCARD state. This is mainly due to the frequency with which the sequence is repeated. In fact, in a completely connected network (as in the experiments) each node has to process each protocol frame in the channel, even those are not for the node in question and that will therefore be discarded. With respect to equation 3.20, Ti,j represents the most influential factor for computing the utilization. Its low values mean that the utilization increases. In addition, we have identified the execution of single state, i.e. the RECEIVE, that spends the time of the worst case sequence. This is due to the writing operation involved when a frame has been received. This is shown in Table 3.2 which considers the case of five nodes in a completely connected network that represents the worst case for this measurement. 3.3.4 Overhead and Blocking One way of performing a characterization of a communication network is the estimation of the protocol Overhead and message Blocking. In order to do this, let us first define the following main RT-WMP features: •Number of nodes (N) 58 RT-WMP: Evaluation and Analysis 3.3. Analysis of the protocol •Create a new token (CT): This operation is carried out to start a new PAP phase creating a token. •Evaluate token (ET): This operation involves checking the token received and modifying it before the retransmission. •Evaluate token and create Authorization (ETA): In the PAP phase, the last node checks the token, extracts the MPO node identity, and computes the path to reach the node that will be authorized. It then starts the ATP phase, sending the authorization. •Evaluate Authorization (EA): During the ATP phase, each node on the path checks the authorization and forwards it to the next node. •Evaluate Authorization and create Message (EAM): When the authorization reaches its destination, the node checks it and starts an MTP phase to send its highest priority message. •Evaluate Message (EM): During the MTP phase, each node on the path checks the received message and forwards it to the next node. •Evaluate Message Enqueue (EME): When the message reaches its destination, the node checks and enqueues it. •Protocol Delay (PD): This is a delay introduced before any SEND operation. •Header transmission (TH): This represents the time to send the header protocol bytes. •Interrupt routine (ISR): This is the code executed by the interrupt server whenever a frame is received. The duration of these periods is defined in the Appendix B. With these attributes, we can estimate the packet Overhead and the Max Blocking for the RT-WMP, as in [Mart´ınez 05]. •Overhead: It is the overhead caused by the protocol information that needs to be sent before each message. It is calculated as: Toverhead =CT |{z} 1 + (2N−4) ·ET | {z } 2 +ETA |{z} 3 + + (N−2) ·EA | {z } 4 +EAM |{z} 5 + (N−2) ·EM | {z } 6 + +TH |{z} 7 (3.21) 59 3.3. Analysis of the protocol RT-WMP: Evaluation and Analysis Token Authorization Message N e t w o r k N1 N2Nn-1 Nn Message on queue 2 1 3 4 2 2 4 4 5 66 6 7 4 Figure 3.21: RT-WMP Overhead. Figure 3.21 shows the worst case overhead case that can occur. In RT-WMP, this represents the time spent creating a new token and sending it (1), performing a complete circulation of the Token over the network (PAP phase can last up to 2N−4 hops) (2), creating the authorization and sending it (3), and performing a complete circulation of the authorization to the N1(ATP phase can last N−2) (4). Node N1evaluates the authorization and prepares the message (5) that is to be forwarded (6). Finally, the penultimate node Nn−1 evaluates the message and forwards it. We consider the cost of forwarding the message on the last hop, i.e. the protocol header message (7). •Non Preemptive Blocking: The blocking is caused by the non-preemptibility of message packets. Priority inversion occurs when a higher priority message is blocked by lower priority messages. If the lower priority message gains access first and then the higher priority message requests access to be sent, this is blocked until the lower priority message completes its loop. Thus, blocking is a form of priority inversion where a higher priority message must wait for the processing of a lower priority message. In RT-WMP, blocking represents a complete token and the authorization phase plus the blocking effect caused by the transmission of a lower priority packet. This is calculated as: BNP = (2N−5) ·ET | {z } 2 +ETA |{z} 3 + (N−2) ·EA | {z } 4 + +EAM |{z} 5 + (N−2) ·EM | {z } 6 +EME | {z } 7 + +CT |{z} 8 + (2N−4) ·ET | {z } 9 +EAM |{z} 10 (3.22) 60 RT-WMP Quality of Service Extension 4.2. Overview the adaptability to the network topology but the number of used channels increases. Some proposals are based on hybrid MAC Token CDMA policing mechanisms. Taheri and Scaglione’s [Taheri 02] proposal is based on a ring network where each token corresponds to a physical CDMA subchannel which is guaranteed to have a certain average rate and satisfies a probability of error bound by identifying two classes of service to give prority to QoS traffic. All these solutions, despite offering some degree of timing guarantees, have a quite different target than the solution proposed in this chapter, since the only objective is to offer QoS support without considering the real-time requirements. Currently, to the best of our knowledge, there is no protocol that allows the simultaneous transportation of real-time and QoS traffic. 4.2 Overview In real-time systems, planning must always be carried out considering the worst possible scenario. However, worst-case loops are unlikely to happen in practice and even with unfavorable network topologies they occur only in a small percentage of loops. The rationale behind this proposal is, therefore, to take advantage of the time considered at planning time but not actually used in the majority of situations. From the communication point of view in a distributed real-time system, this can be translated to the time interval between a concrete end-to-end delivery delay and the worstcase delivery delay. In other words, we are taking advantage of the fact that the worst case will take place in very few situations, using the time left to transport QoS data flows or best effort traffic. 4.2.1 Worst-case in RT-WMP RT-WMP protocol phases have a bounded duration (see section 3.1.1). As described by equation 3.3, the worst-case end-to-end delivery delay can be expressed as: tete(wc)=2·tloop(wc) (4.1) This value depends, in turn, on the network topology and on the position of the source and destination of any specific message. Worst-case loops are unlikely to happen in practice and even with unfavorable network topologies they occur only in a small percentage of loops. In other words, in the majority of cases the RT-WMP closes its loops in a time shorter than the worst-case one and in some cases (if the real-time traffic bandwidth usage is below one-hundred percent) the loop consists of the PAP only. The idea, therefore, consists of using, in any loop, the time slot between the real loop-duration and the worst case loop duration to send QoS information. In other words, we are forcing the protocol, when one or more QoS flows are present, to operate in the worst-case situation taking advantage 67 4.2. Overview RT-WMP Quality of Service Extension t t (wc) t jDj loop RT-WMP Loop Loop start Figure 4.1: Time intervals used by the QoS Extension. of the fact that it will take place in very few situations. So, real-time characteristic of the protocol is guaranteed. This scheme does not worsen, by design, the worst-case end-to-end so can be used in any real-time network to add QoS capabilities maintaining the same worstcase performances. 4.2.2 Available Time The available time in any loop depends on several factors such as the relative position of source and destination, the network topology and so on. The duration of the real RT-WMP loop tjis less than or equal to the worst-case loop tloop(wc). Figure 4.1 illustrates the situation. The available time Djcan be expressed as: Dj=tloop(wc)−tj(4.2) While the minimum value of Djis zero, the maximum corresponds to the situation in which the RT-WMP loop is only constituted by the PAP. In this case Dj=tloop(wc)−TP AP . 4.2.3 QoS Extension Operations To each node has been added a QoS transmission and reception queue (QTQ and QRQ respectively). Each QoS message has a deadline that is fixed by the application and that represents the time during the which the message is valid. This QoS extension, has three phases: an arbitration phase, a QoS Authorization Phase (QAP) and a QoS Message Phase (QMP) that can be repeated one after the other for a limited amount of time. The arbitration phase is carried out during the PAP while the QAP and QMP, are added to the basic protocol. In the arbitration phase all the nodes which have a QoS message waiting in the QTQ compete to gain the right to send it (during the PAP the token reaches all the nodes). One or more messages can be selected for transmission depending on their deadline and on the distance between the source and the destination nodes, as will be explained below. The address of the nodes owner of these messages 68 RT-WMP Quality of Service Extension 4.3. The RT-WMP QoS Extension Details are stored in the header of the frames. The first QAP starts when the standard MTP ends (or after the PAP if there is no real-time message to be sent). The node which ends the MTP (or the PAP), instead of restarting the successive PAP, sends an authorization to the owner of the first selected message (indicated in the header), using the same scheme used by the RT-WMP. The latter, then starts the QMP and sends the QoS message to the destination node that pushes the message into its QRQ. Successively, if the header specifies that there are other messages to be sent, it prepares an authorization and starts another QAP during which the message reaches the node owner of the selected message. This, in turn, sends its message during a further QMP and so on. As has been stated, the QAP and QMP are been repeated one after the other for a limited (and configurable) number of times, but in any case they stop when the worst-case loop time is reached. This behavior is obtained by loading a field of the header with the duration, expressed in milliseconds, of the worst-case loop and subtracting, in any frame-pass, the time spent on this action. When this value is lower than the time needed to execute the next frame-pass, the QAP or QMP ends and a normal PAP restarts. If the PAP has to restart during a QMP, the transported message is stored in the QTQ of an intermediate node to be able to compete for selection again in the successive PAP. The QoS extension implements eight flow priority classes where class zero corresponds to best-effort not-QoS traffic. Flows are served following their priority level. Audio flows, for example, usually have priority over ideo flows since audio information is more delay sensitive. The introduction of a flow in the protocol is regulated by the Flow Admision Control (FAC) that allows or denies access, taking into account the priority of the requesting flow and the available bandwidth estimatedby analysing the differece between the worst-case and the real loops durations within a certain time-window. 4.3 The RT-WMP QoS Extension Details In Real-Time distributed systems, bounded end-to-end delay and priority support are required for scheduling and time constraint guarantees. Since the plain RTWMP is a real-time protocol, each event/phase protocol has a bounded and known duration even in the presence of the majority of errors. Loops have, for example, an upper bound on their duration that can be easily calculated and that is used as a base to calculate the loop remaining time, as will be explained with more details below. 4.3.1 Frame Header Modification Figure 4.2 shows the RT-WMP frame with the fields that support the QoS extension. The qos rem field is a 2 byte field that is filled, at the beginning of any loop, with the duration, expressed in milliseconds of the worst-case RT-WMP loop. The 69 4.3. The RT-WMP QoS Extension Details RT-WMP Quality of Service Extension RT-WMP Frame qos_rem qos_dlqos_src qos_prio qos_dst ac_art ac_pri ac_lot 1 x n 12 12 2 x n1 x n1 x n Tail Header Figure 4.2: Frame for the RT-WMP with QoS extension. ac loop id,ac pri, and ac lot are service fields used by the access control system to estimate the available QoS bandwidth. The next fields are used to identify the selected messages. All of them are (compile-time) configurable size vectors. Their size is application and network-size dependent and represents the maximum number of QoS messages that can be selected (and potentially delivered) in any loop. The qos dl (2 bytes per message) contains the actual deadline of the packets (relative deadline to the actual moment) while the qos src and qos dst (1 byte per message) specify their source and destination. These last three fields are used to calculate the dynamic priority of the message that depends on the deadline and the distance between the source and destination of a message. The last qos pri field (1 byte per message) carries the priority class of the selected message. 4.3.2 Phases of the Protocol In this section a detailed description of the different phases of the protocol is presented including some implementation issues than condition the development of the protocol. The Message Selection Phase The first phase of the protocol takes place simultaneously with the PAP of the basic RT-WMP. In fact, in this phase the QoS extension does not alter the operations of the basic protocol (tokens are exchanged in the usual way). In this phase, the QoS messages to be transmitted in the successive phases are selected. In each node the QTQ contains all the QoS messages ordered by priority (see sec. 4.3.3). The node that starts the PAP analyses the QTQ. Above all, it discards the expired messages. It then obtains the class flow, the deadline and the destination of the nmost priority messages (nbeing the maximum number of QoS messages that can be delivered in any loop) and fills the correspondent fields of the token header. Moreover it calculates the worst-case loop duration and fills the field qos rem of the header with this value expressed in milliseconds. Successively the basic protocol is responsible for sending the token to another node. The node that receives the token processes the basic part of the token as usual. It then actualizes the values of qos rem and the qos dl subtracting the time spent in the last token70 RT-WMP Quality of Service Extension 4.3. The RT-WMP QoS Extension Details pass. It successively calculates the new priority for the messages referenced by the token. This step is necessary because the change in the deadline implies a change in priority. It then again discards expired messages and compares the nmost priority messages in the QTQ with those carried by the token. If figures out that owns one or more priority messages, and replaces the less priority with its own updating of the qos dl,qos src and the qos dst fields. In the same way, the process is repeated up to the moment in which the last node of the network is reached. At this moment the node starts the ATP and the MTP (if real-time messages have been selected to be sent). In these two phases, there is no participation of the QoS extension except for the fact that the qos dl field is decreased by the quantity corresponding to the time spent in any frame pass. The QoS Authorization Phase This phase starts after the conclusion of the MTP (if any) or the PAP or even after a QMP. The node that starts the QAP prepares an authorization as in the basic protocol (see [Tardioli 07]), fills the aut src with its address and aut dest with the first element of the qos dst vector, shifts by one the position of the qos dst,qos dl,qos pri and qos src vector elements (qos dl[0]=qos dl[1], qos src[0]=qos src[1], etc.) and sends the frame. The authorization is propagated using the same routing algorithm of the basic protocol (Dijkstra based algorithm) until it reaches the destination. In any hop, however, the qos dl and qos rem fields are actualized subtracting the duration of any frame-pass. If at some moment the qos rem field reaches a zero value (or a value that does not allow a further frame-pass), the QAP is immediately aborted and another PAP is started. The QoS Message Phase When a node receives a QoS Authorization, the QMP starts. It pops the most priority message from the QTQ and creates a new message frame placing data in the message field. It fills the src and dest fields with its address and with the destination address and calculates the path to the destination. Then it sends the message to the first member of the path as in the RT-WMP basic protocol. When the latter receives the message, it checks the msg dest field. If it is not the destination node (i.e. if it is an intermediate node), it verifies if there is enough remaining time to forward the message to the next node of the path (i.e. the value of qos rem is at least greater than the time needed for one message-hop). If this is the case, the node repeats the computation of the path and routes the message to the next member of the path, leaving the dest field unchanged. Otherwise, it pushes the message into the transmission QoS queue and starts a new PAP. In this case the message will compete to be selected for transmission again in the next PAP. If the message reaches the destination in a single loop, there is the chance of sending another QoS message. When the node receives the QoS message, it pushes 71 4.3. The RT-WMP QoS Extension Details RT-WMP Quality of Service Extension it into the QRQ. It then looks at the qos rem field. If it is assured that there is enough time to authorize another node and to allow at least one message-hop, it starts another QAP that, in turn, will cause another QMP and so on. 4.3.3 Message Priority Policy Packet Deadline Timing guarantees can be considered as a fundamental feature for MANETs able to support QoS applications. Applications such as voice communication, video-ondemand, video conferencing, and radio broadcasting require that the end-to-end delay be less than a certain value. Thus, each packet has to reach the destination within the specified deadline, after which it becomes useless. In a single-hop network the queueing delay is not too large. However, in the multi-hop scenario, the source and destination may be several hops away, and packets need to be forwarded by the intermediate nodes. As a result, delays can become quite large, especially due to the presence on the networks of packets with highter priority thereby making audio and video transmissions infeasible. In order to grant a good QoS level, each message has to be delivered before its deadline. Delay bounded service allows the protocol to know whether it is able to meet the deadlines or not. Any QoS packet has an associated deadline by which it must be delivered. If this is not possible, the packet must be discarded. Indeed, when deadline is met before the destination node, packet is useless for the audio/video and occupy network resources unnecessarily. This deadline value is only needed until the packet is either successfully transmitted or discarded. The mechanism to label and update the deadline on every QoS message is quite simple. Messages are labelled with their maximum admitted deadline, depending on the nature of message. Deadline values are usually 150 ms for voice and 400 ms for video traffic that correspond to maximum end-to-end delays admitted for multimedia traffic [Vlaovic 01]. When this parameter reaches the zero value, the message expires. So, during multi-hop transmission, this value has to be properly updated. Every node over the source-destination path updates packet deadlines taking into account the elapsed time and the transmission time of one-hop. Packet Scheduling The QoS extension implements a packet scheduler that assigns a dynamic priority to a packet taking into account the flow class, the deadline and the number of hops left to the destination, in this order. Above all, the scheduler sorts the packets according to their class flow. Messages in the same flow-class are sorted using the laxity that is a parameter that combines the deadline and the number of hops left to the destination as laxity =deadline/hopleft. Instead of transmitting packets in the FIFO order (as in the case of 802.11e) or EDF order, we prioritize the packets with respect to the laxity. In fact, in 802.11e 72 RT-WMP Quality of Service Extension 4.4. Flow Admission Control for example, a packet whose destination is one hop away has the same possibility of capturing the channel as a packet whose destination is several hops away. So, locally it does not take into consideration the number of hops a packet has to cross. However, the laxity gives us an estimate of how much delay the packet can tolerate at each hop. Hence, the packet with the lowest value of laxity is given the highest priority. If two packets have the same lowest value of laxity, we resolve the conflict by sending the packet which has more hops to travel. If the laxity value becomes zero, the packet is discarded since it is useless at the destination. 4.4 Flow Admission Control In Ad-hoc networks, distributing shared network resource between competing users has become one of the fundamental challenges. The limited bandwidth capacity makes it difficult to guarantee the QoS requirements in the presence of many flows. Therefore, it is necessary to have a good estimation of the bandwidth required by a flow. The more exact this estimation is, the more efficient the admission control would be. FAC is considered as an important component for the provision of QoS parameters. The aim of FAC is to limit the amount of traffic admitted into a network so that the QoS of the existing flows will not be degraded. Actually most of work to provide a FAC mechanism in MANETs is done for a MAC layer. Most of these are provided by APs and they are not suitable in a purely MANET, without infrastructure. Reference [Yan 08] presents an distribuited admission control mechanism based on finding a avalilable path during the routing establishment. In [Hung-Yu 06] the authors propose an interesting model-based approach that work trying to maintain the QoS metric of existing flows while maximizing the number of admitted calls. That scheme uses the nodes interference in order to evaluate the state of channel ocupancy. Another model-based approach is presented in [Zhang 06], where a distributed time allocation allows to balance the bandwidth amongst flows with a low computation complexity. In [Canales 07], authors propose a mechanism to evaluate the QoS demand based working on a routing algotithm and MAC layer to ajust the decision taking into account the scenario variabilty. The authors in [Yigitbasi 08] present a synchronous bandwith allocation scheme based on timed token protocol in a centralized control plane and limited to a token ring network. 4.4.1 Overview The available bandwidth for QoS flows is limited and depends on different factors such as real-time flow saturation, network topology and so on. Thus, it is important to control the admission of new QoS flows in a real-time network since if the available bandwidth is not enough, it is possible to jeopardize the correctness of the whole set of flows. As an example, consider the situation in which in the 73 4.4. Flow Admission Control RT-WMP Quality of Service Extension network there already exists a 15Kbps flow and the global available bandwidth for QoS flow is about 20 Kbps. If we try to introduce another 15 Kbps flow of the same class, the system will distribute the available bandwidth between the two flows lowering the rate of both to 10 Kbps discarding the messages that cannot be delivered within the deadline. It would not be enough for a correct streaming and both flows would be useless. FAC estimates and manages the available bandwidth. The idea is to compute if there exist enough bandwidth for a given new flow. The admission control works in accordance with the flow class. 4.4.2 Available Resource Estimation To estimate the available bandwidth for new QoS flows, the network is observed during a time window that contains several RT-WMP loops. We call this sliding window the Available Bandwidth Estimation Interval (ABEI). The width of the ABEI is configurable and a good choice is usually related to the hyperperiod of the underlying real-time distributed system. Over an ABEI the Global Remaining Time (GRT) is calculated as: GRT =X j:loopjABEI Dj.(4.3) The GRT represents the sum of all the remaining time Djthat is included in the ABEI. In other words, the GRT is a measure of the available time for QoS flows. Any QoS flow occupies a portion of this global available time. We call the sum of all the occupied portions Global Used Remaining Time (GURT) that can be expressed as: GURT =X j:loopjABEI,k[0..7] tdj(k) (4.4) tdj(k) being the time consumed by a kclass flow in a loop j(see Figure4.3). In a similar way it is possible to define the Global Available Remaining Time (GART) as GART =GRT −GURT. The GART represents the time still available subtracting the time occupied by already-active QoS flows. However, this access control scheme relies on flow classes, that is, higher priority flows can expel lower priority ones. In the light of this, the GART can be considered as the available time for the least-priority flow in the system at any moment. The available time for a given class flow is instead called the Available Remaining Time (ART). It can be expressed as: ART(c) = GRT −X j:loopjABEI,k≥c tdj(k) (4.5) cbeing the class of the flow that is requesting access. 74 RT-WMP Quality of Service Extension 4.4. Flow Admission Control GRT tRT-WMP Loop Loop start 43 8 2 6 5 t 4 3 6 8 2 GART GURT QoS flow - class5 Free time t 4 6 8 ART (4) GRT 3 2 ABEI Figure 4.3: Resource estimation mechanism. If a flow requests access to the system, the FAC calculates the ART for the class flow of the flow requesting access and estimates (using a heuristic) whether there is enough bandwidth to allow the access. Principle of Operations. When a node closes a PAP, it stores in a local vector the value of qos rem together with a timestamp. Next, it fills the ac lot field with the value of the qos rem field. Successively, when a QoS Message is delivered, if kis the class flow of the message, the receiver computes the time spent to deliver the last message with the formula: td(k) = ac lot −qos rem (4.6) The node stores td in a local vector together with the class of the message just received. Then it actualizes the value of the ac lot with the present value of qos rem and continues the operations with another QAP or a new PAP. The process is repeated in any loop and the nodes accumulate, but in a distributed fashion, all the information about message delivery times and remaining times. In fact, none of the nodes has a global view of the available time in the network. However, the sum of all the elements of the first vector of all the nodes represents the GRT and the sum of all the elements of the second vector represents just the time consumed by all the active flows in a specific moment (i.e. the GART). When a node needs to add a new flow into the network, it requests that it specify the class of the new flow in the ac pri field (that normally contains a negative value). In the successive PAP, all the nodes analyse their vectors with respect to the values stored in the ABEI window. Specifically they sum all the values of the first vector whose timestamp is contained in the ABEI and subtract all the values of the second vectors whose timestamp is contained in the ABEI and class is greater or equal to the one requesting the flow. The result of this computation is added to the values of the ac art field (that normally contains a 75 4.5. Evaluation RT-WMP Quality of Service Extension Parameter Values Scenario Channel rate 1 Mbps Number of nodes 6 Data Real-Time pkt 128-256-512 Byte QoS rate per flow 15 Kbps Constraints Deadline 150 ms Queues size 50 pkts Table 4.1: Parameters used in the real tests. null value). When the token has reached all the nodes, the qos art field contains the Available Remaining Time (ART) of the given class flow. Figure 4.3 shows the rationale behind the procedure. The global time left free by the protocol in an estimation interval is consumed by the time spent to deliver QoS messages of any class. However, when a message requires access, only higher classes messages are considered in order to calculate the ART for this class flow. When in the next PAP the token again reaches the requesting node, it analyses the value contained in ac art. Using a simple heuristic, the node decides if the requesting flow is admissible. If this is the case, it allows the application to begin the new stream. 4.5 Evaluation The aim of our experiments is to examine the impact of the proposed extension on the RT-WMP protocol. Several real tests have been made using an implementation of RT-WMP executed over the MaRTE OS [Rivas 01] real-time operating system. A total of six nodes equipped with Intel Pentium IV CPU at 2.5GHz, 2GB RAM and Ralink RT61 chipset-based wireless cards have been used. To evaluate the correctness, the performance and the behavior of the protocol extension, we have performed some real experiments. Table 4.1 lists the parameter values used in the tests. 4.5.1 Available Time Figure 4.4 shows the result. In figure 4.4.a we can observe that the connected topology leaves a mean of Dj = 61:75 ms available for QoS traffic considering a worst-case loop of about tloop(wc) = 78 ms, that is about 80time. Both the string and the star topology are quite demanding leaving a mean of about Dj = 30 ms (38). The proposed extension uses the available time Dj=tloop(wc)−tjto transmit the QoS traffic. An real experiment was carried out to evaluate the dependency of 76 Chapter 5 Underground Propagation Issues So far, we have presented the real-time and QoS characteristics of the RT-WMP protocol. As stated, protocol capability to route messages is based on reading the instantaneous quality of the link between nodes. This characteristic is essential in order to have a reliable view of the link status at the time of sending messages. However, this may not be enough especially in specific applications where the knowledge of the propagation evolution of the signal between the different nodes can be useful. This is the case of confined environments such as tunnels or mines. These areas are interesting from the point of view of communications given that normal radio systems can provide at best very limited communications capability. As a result, the problem of providing an effective communications system in hostile environments, both for exploitation and emergency situations, has been an important issue in recent decades, particularly after a series of unfortunate underground disasters and accidents. Therefore, to utilize the MANET effectively, it is desirable to adapt the solution taking into account its effects on the signal propagation depending on the environment settings. In order to provide radio coverage in long tunnels (railway, road or mines), the most commonly used systems are the so-called hybrid systems that combine wired and radiotransmission, like the Leaky Feeder (LF), and systems based on the natural propagation of radio-waves inside the tunnel. Due to the high cost of LF installations and the fact that they are susceptible to failures in disasters, the natural propagation system is preferred in many applications. If the carrier frequency is high enough such that the wavelength is much smaller than the crosssection dimensions of the tunnel, it behaves as a waveguide. In this case, the attenuation per unit length is low enough to allow communications over a range of several kilometers. In this chapter we make a contribution towards the use of MANETs in underground settings. Following an empirical study, a set of real measurements carried out to validate theoretical results is presented together with an analysis of some signal propagation issues. 83 5.1. Related work Underground Propagation Issues We consider the relation between the RSSI and the PDR, the transmission rate with respect to the area coverage, and the variation of the delay spread along the tunnel. We also show how the signal shape periodically exhibits slow and fastfadings corresponding to such environment. The collected data are evaluated in order to characterize the specific environment with a set of connectivity constraints with a view to implementing real underground communication applications that are presented in the next chapter. Part of this work will be published in the special issues on Robotic Communications and Collaboration in Complex Environments of the International Journal of Robotics Research (IJRR) [Rizzo 13]. 5.1 Related work Although many different communication systems for underground areas exist, the most commonly used are those based on the use of radiating cables, such as the LF system, or wireless systems. The Leaky Feeder cable is a hybrid system type. It is designed to allow the radio signal to “leak”, both into and out of the cable [Delogne 82]. The properties and advantages of the LF have been evaluated in several works, as in [Nakamura 96] [Dekker 96]. However, it is still susceptible to single cable cuts, when a collapse can occurs. Some studies began to question the robustness of traditional cable-based systems in terms of the tolerance of the communications components to harsh environmental conditions. For example, in [Einicke 97] the authors show how a solution based on Wireless Local Area Network (WLAN) can outperform a LF system in terms of the probability of maintaining communication when a disaster occurs. However, electromagnetic waves do not propagate in tunnels as in free space, even if Line-of-Sight (LoS) is maintained between emitter and receiver. Many researchers have started to investigate wave propagation in confined environments to discover the reason for this strange behavior of electromagnetic waves. Thus, several studies about propagation, channel characterization and measurements have been carried out in the last decade. In radio propagation modeling, two approaches are used: theoretical modeling and empirical modeling. Theoretical modeling is established by using either a modal approach or a geometrical optic approach. The modal approach poses some challenges in terms of its mathematical tractability. Tunnels are modeled as oversized imperfect waveguides. The received field is the sum of the fields consisting of a fundamental mode and a number of higher order modes, [Dudley 07, Sun 10]. This approach offers analytical expressions (i.e. solutions to Maxwell’s equations), but only rectangular and circular cross section cases have been solved. Moreover, since the shapes of galleries are not uniform and regular, the establishment of a general framework in theoretical modeling becomes even more 84 Underground Propagation Issues 5.2. MANET in underground settings complicated. In these cases, the geometrical optic approach can be adopted. This theory considers tunnel walls as reflecting planes. Propagation is achieved via a direct path and all possible reflected paths. The techniques proposed are Ray Launching [Hwang 98] and Ray Tracing [Seidel 94]. Neither technique can be used in the presence of curved surfaces, and a proposed solution is to tessellate geometries into multiple planar facets, as suggested in [Masson 09]. However, these methods could require overwhelming numerical calculations [Lienard 00]. Empirical modeling is based on extensive field measurements performed in the environment of interest. Collected data are evaluated in such a way that the statistical characterization of the radio propagation is obtained for that specific environment. Since empirical modeling characterizes the propagation statistically, the model obtained can be employed in similar environments. Due to the considerable effort, the difficulty of obtaining permissions and the safety issues involved, empirical approaches are not abundant in the literature. However, empirical approaches in underground mines have been attracting significant attention, and this has provided researchers with some opportunities to better characterize underground radio propagation channels. 5.2 MANET in underground settings As we have said, the LF based networks are very costly to deploy and maintain and, in addition, they lack standardization. Moreover, in an emergency scenario (a collapse or similar) the system could be damaged and become useless. Recently, wireless Ad-Hoc networks have been considered as an alternative solution [Yarkan 09] for providing communications in underground settings. They offer solutions to some of the fundamental challenges of all tethered communication systems such as easy maintenance (nodes can be installed, moved, removed and replaced easily), higher robustness against failures stemming from physical damage, mobility and low deployment costs. Therefore wireless systems using the 802.11 standard can offer a suitable way to interconnect nodes in underground mesh networks. Although several studies about EM wave propagation have shown the substantial difference between confined spaces and free-space propagation, most of the valuable studies in the area of MANET have been performed by computer simulations or indoor experiments only. Thus, the lack of extensive testbed experiments together with the lack of accuracy of theoretical models means that the performance and behavior of MANETs working in hostile environments is not well understood. This is particularly true in tunnels, where real measurements can help to adapt a system to the environment in which it is to operate. 85 5.3. Environment - The Somport tunnel Underground Propagation Issues 5.2.1 Link metrics consideration Link quality measurement and estimation are a critical part of almost every mobile network routing protocol. Several metrics are used for analyzing the quality of a wireless link, of which the most commonly used are the RSSI, SINR, PDR and the BER (see section 1.4). There is currently an open debate on which to use and why [Vlavianos 08, Wu 08] due to the fact that each metric represents a different characteristic. The conclusion is that there is no single metric to measure everything required, in order to establish the quality of a wireless link. Given that commercial hardware does not provide noise information while receiving packets but only an average estimation, it is quite hard to compute the SINR metric. On the other hand, the use of PDR involves substantial latency for link quality estimation [Souryal 06]. BER computation introduces significant overheads and is sensitive to bit sequences [Vlavianos 08]. Finally, RSSI does not capture the amount of destructive interference in links and it could lack accuracy at high transmission rates due to its being measured at the lowest rate (during the reception of a packetpreamble). Analyzing the validity of common assumptions with regard to each metric, it is apparent that each of them provides an estimation of the link quality over a period of time with limitations in terms of accuracy. No single metric on its own can be considered sufficient to accurately characterize the quality of a link. However, RSSI can be a promising metric when its value is above the sensitivity threshold [Srinivasan 06] and the application requirements in terms of transmission rate are not high [Holland 01]. Furthermore, the use of a token-passing protocol (as in our case, the RTWMP protocol) which prevents simultaneous transmissions, relieve the negative effect of interference in the measurement of this metric. PDR could depend on the packet size and the transmission rate. That said, however, the PDR can characterize the link quality if only a few types of packets are used and assuming that the transmission rate is fixed. Moreover, RSSI and PDR metrics are not independent of each other. For example while PDR does not measure power, it is correlated with RSSI at certain transmission speeds [Vlavianos 08]. These relations have been studied in order to identify appropriate combinations for determining the quality of a wireless link in an effective manner. 5.3 Environment - The Somport tunnel The Somport tunnel was selected as the location for carrying out the analysis and the majority of the experiments presented in this work. This is an old railway tunnel representative of long straight tunnels common in transport or mine ap86 Underground Propagation Issues 5.3. Environment - The Somport tunnel Figure 5.1: The Somport tunnel. plications. The 7.7 Km railway tunnel connects Spain with France through the central Pyrenees. It has a horseshoe-shape cross section, 6 meters high and 5.5 meters wide. The tunnel is straight but there is a change in slope at approximately 4 kilometers from the Spanish entrance, as can be observed in Figure 5.1. The walls are made of limestone, with relative permittivity r= 5 and relative conductivity σ= 0.01 S/m. The tunnel has some particular features, such as small vaults every 25 meters. These are 1 meter wide, 1.5 meters high, and 0.6 meters in depth. It also has 17 lateral galleries, of more than 100 meters each, of the same height as the tunnel. In the next section, we explain the metrics and the rate selected in order to measure and then analyze the communication signal propagated in the tunnel. 5.3.1 RSSI and PDR relation PDR tends to decrease for higher transmission rates, since higher rates are more vulnerable to external noise and interference. In order to validate that using the RT-WMP protocol, we consider an experiment in which, a node in our testbed takes turns in unicast traffic (in isolation) and another node records the RSSI values from the received packets. We conducted experiments with all possible fixed rates. Figure 5.2 presents a plot of the PDR versus the RSSI for five different rates from which we can observe the correlation between the two metrics. In particular, Figure 5.2.b highlights how at high bit rate transmission, a suitable PDR level is lead only of the node links that show stronger RSSI levels. This relation assumes importance when there is a need to ensure a certain level of QoS. For example, working at a rate of 54M, achieves a level of quality in terms of PDR which would not be attainable for modest values of signal intensity. In other terms, this correlation allows us to estimate a qualitative metric, the PDR, through the quantitative parameter RSSI. 5.3.2 Rate and Coverage Range Another aspect to take into account is the well known relation between the range and rate of WLANs. Notice that lower rate transmission schemes have greater transmission ranges than higher rate schemes [Rappaport 96, Holland 01]. This 87 5.3. Environment - The Somport tunnel Underground Propagation Issues 0 −73 −68 −65 −58 −53 −48 0 10 20 30 40 50 60 70 80 90 100 RSSI [dbm] PDR [%] 6M rate 12M rate 24M rate 36M rate 54M rate (a) 6 12 24 36 48 54 −73 −68 −63 −58 −53 −48 Rate [Mbps] RSSI [dBm] PDR > 98% (b) Figure 5.2: Empirical relation between RSSI and PDR measured. In (a), the variation for five different transmission rates. In (b), figure highlights the RSSI and Rate values that correspond to acceptable PDR level. is even more true in confined environments such as tunnels where, at the typical WLAN carrier frequency, the tunnel acts as a waveguide. In order to validate that relation, we conducted an experiment similar to the previous one but this time considering a node moving along the tunnel while recording the RSSI values from the received packets. We wanted to compare the coverage range for a 6 Mbps and a 54 Mbps data rate. Figure 5.3 shows the results which confirm the cited rate-coverage relation. By setting the same transmission power, in the 6 Mbps rate configuration, good RSSI values are obtained along more than 2 km away and practically no packets loss occur. Instead, the 54 Mbps rate schema already suffers a heavy packet loss from the first 200 meters. The conclusion is that in certain specific applications (such as rescue or exploration), maximizing bandwidth is not able to meet more strict requirements such 88 Underground Propagation Issues 5.3. Environment - The Somport tunnel 500 1000 1500 2000 2500 3000 −90 −80 −70 −60 −50 −40 −30 −20 Distance from transmitter [m] RSSI [dBm] 6M rate 54M rate Figure 5.3: Coverage range for 6 Mbps and 54 Mbps data rate along tunnel. as link quality and coverage range. Considering this, we fixed the operating rate in the testbeds presented in this work at 6 Mbps. 5.3.3 Fading Analisys Propagation in tunnels is affected by the multipath effect. The latter is the main factor responsible for strong fading phenomena that affect both the intensity and the quality of the signal that reaches a receiver. These phenomena have been studied by many authors. In [Lienard 98], the fading phenomena of tunnels are statistically analyzed. They are classified in short-term (also referred to as fastfadings) and long-term (slow-fadings), and three regions are established where fadings behave differently: 0 - 50 meters, 50 - 500 meters and beyond 500 meters from the emitter. The prediction of radio coverage levels is required to develop communication systems and optimize their deployment ensuring availability and robustness of the radio links. Several theoretical modeling approaches have been proposed, as stated in Section 5.1, and some experimental studies have been made to establish their accuracy. See, for example, [Masson 09] for ray optics theory or [Sun 10] for modal theory. It is clear that none of the techniques can predict with sufficient precision the position or magnitude of a fading. Thus, taking into account the fading phenomena effect, experiments performed in underground environments cannot be based only on a theoretical model. In order to study longitudinal variations of the signal, we performed a set of real measurements. The transmitter was placed 0.25 meters apart from the wall and 2 meters above the ground. One moving-receiver’ antenna was placed at a height of 1.80 meters and a distance of 0.60 meters from the tunnel axis. It was displaced from the transmitter position up to 2900 meters, maintaining the line-of-sight between them. The signal was sampled with a spatial period of 0.1 meters. The result is shown in Figure 5.4. 89 5.3. Environment - The Somport tunnel Underground Propagation Issues 0 500 1000 1500 2000 2500 3000 −90 −80 −70 −60 −50 −40 −30 −20 Distance [m] RSSI [dBm] Near Sector Far Sector 750 Figure 5.4: Measured received power (dBm) along tunnel. Distance from transmitter [m] Period 0 500 1000 1500 2000 2500 1 2 4 8 16 32 64 128 256 512 1024 1/64 1/32 1/16 1/8 1/4 1/2 1 2 4 8 16 32 64 Figure 5.5: Wavelet of the signal versus the distance using the Morlet function. As can be observed, two main sectors can be identified in the tunnel according to the signal behavior. The boundary between the sectors is at a point around 750 meters from the emitter. In the first sector (near sector) very fast fluctuations of the signal power (the fast-fadings) and the distance path loss dominate. In the second sector (far sector), the slow-fadings dominate instead. To analyze this different behavior, the wavelet of the signal as a function of the distance is presented in Figure 5.5. To calculate the wavelet, the signal series was padded by mirroring the ends in order to minimize the border effects. The wavelet shows that the behavior changes at 750 meters. In the near sector 90 Underground Propagation Issues 5.3. Environment - The Somport tunnel 0 500 1000 1500 2000 2500 3000 −90 −80 −70 −60 −50 −40 −30 −20 Distance [m] RSSI [dBm] Real signal Signal model Figure 5.6: Real signal and signal from the model. the spectral power is distributed along all spatial frequencies, including high frequency components. Nonetheless, in the far sector, the low frequency components are concentrated in a band around 512 meters of period. This band highlights the existence of slow-fadings. Besides, in this sector the fast-fadings exhibit a similar frequential behavior as in the near sector. As we can see, in the near sector, apart from the fast-fadings, the distance path loss dominates following a logarithmic decay in terms of power. In the far sector, the signal power exhibits a characteristic shape (see Figure 5.4) which evokes a typical Sinc function. Considering the real data, we tuned such a mathematical function to reflect a similar behavior for y(x) where y(x) = k· sin(π λ·x) x+c(5.1) λbeing the spatial period of the signal and kand ctuning parameters. A least squares optimization technique has been used to find the optimal parameters k,λ and cto fit the real data with the artificial curve. In Figure 5.6 the measured and the computed signals are shown. In this way we obtain an artificially designed signal that can be used as a model for simulating the real signal propagation. This could be useful when simulation or real testbed experiments (not in an actual fading environment) have to be performed. 5.3.4 Delay Spread Measurement The delay spread is used mainly in the characterization of wireless multipath channels. It can be interpreted as the difference between the time of arrival of the 91 5.4. Conclusions Underground Propagation Issues 0 500 1000 1500 2000 2500 3000 20 25 30 35 40 Distance [m] Delay Spread [ns] Figure 5.7: Delay Spread values sensed from receiver. earliest significant multipath component and the time of arrival of the latest multipath component. In [Nerguizian 05], extensive channel characterization is made by measurements of the delay spread and the coherence bandwidth in a mine. The results show that the channel does not follow a dual-slope relation with respect to the distance. Similar channel measurements are presented in [Benzakour 04], analyzing both 2.4 and 5.8 GHz. The results show that indoor multipath characteristics can strongly depend on the node separation and the dimensions of the gallery. In order to validate the results cited above, we performed a test to measure delay spread along the tunnel. The test is useful for obtaining information about the best places to locate the backbone nodes, avoiding zones affected by fading or interference. We measured the RMS delay spread using the YellowJacket Tablet Wi-Fi analyzer (Berkeley Varitronics Systems). The measurements were repeated every 25 meters over 3.2 km of the tunnel and the results are shown in Figure 5.7. As expected, the delay spread oscillates between 25 ns and 38 ns approximately, showing similar values to those calculated in experiments carried out in similar environments (see [Aikio 98] and [Lienard 99], for example) and slightly higher values than than the usual values of around 20 ns found in empty tunnels [Molisch 11]. 5.4 Conclusions Although there are several communication systems for underground mines, wireless communication attracts considerably more attention than the others. Recently, MANETs have been considered as an alternative solution for providing communication in these areas. However, the mere application of a protocol that does not take into account the signal propagation in this specific environment may not be enough in order to provide a reliable network. The contribution of this chapter lies in an empirical signal analysis carried out in a real environment, the old Somport railway tunnel connecting Spain and France 92 Applications 6.1. Real-Time protocol in underground voice communication Stable RT-WMP Link QoS Flow Unstable RT-WMP Link I) II) AB AB B B Figure 6.3: An illustration of mobility scheme. We decided, thus, to force the protocol to use backbone nodes for backbone communication and mobile nodes to link itself to the closest (in terms of link quality) backbone node. In order to achieve that, we reduced the topology of the network to a spanning tree where only the best links are selected or, more concretely, to a minimum spanning tree applying the Prim’s algorithm to the LQM [Tardioli 12b]. Figure 6.2.II shows the results of this process. The backbone topology of the network becomes a string and the node to communicate using the best possible link with the backbone. The rationale is that the nodes see the network as a tree whose branches are the best possible links. An example of how this new scheme works is given in Figure 6.3. As we can see in Figure 6.3.I, the link quality between nodes A and B enables a stable connection between the mobiles nodes (A and B) and the backbone node while the weak link are ruled out by the Prim’s algorithm. While B is moving across the tunnel (Figure 6.3.II), the protocol manages the link quality change allowing multi-hop re-routing across the network and guaranteeing a connection all the time. Since routing, as explained, is based on current and real signal quality, in some situations (even if this is not common) a mobile node can act as a bridge between two backbone nodes. 6.1.3 Evaluation The main experiment was performed in the Somport (see Section 5.3). The tunnel was closed to traffic, so we can assume the experiments were made in stationary conditions. Tests have been done along about 7.5 kilometers. Five nodes equipped with minimal embedded and dedicated hardware (100x160 mm PcEngines ALIX3D3 board, battery powered) and Atheros chipset-based wireless cards and running the MaRTE OS [?] implementation of RT-WMP, were distributed along the tunnel and used as backbone nodes. In addition, two laptop 99 6.1. Real-Time protocol in underground voice communication Applications computers running Linux OS were used as mobile nodes. The voice was sampled at 8 Khz and 16 bit per sample and was compressed using the speex [RFC5574 09] codec to obtain a full-duplex communication of 15 Kbps bandwidth for each flow. Each RT-WMP-QoS message contained four speex voice packets. The packets’ deadline was fixed to 150ms following the ITU-T recomendations [ITU-T 03]. Before performing the final test, however, we made a set of additional experiments to investigate the environment in which the experiment had to take place and chose the adequate parameters to obtain satisfactory results. The first test was about the measurement of RSSI and Delay Spread along the tunnel to obtain information about the best places where to put the backbone nodes avoiding zones affected by fading or interferences. The second set of tests have been performed to discover the best parameters to obtain a correct and effective voice communication in terms of packet aggregation (the number of voice data packet to be transmitted at a time) and reception queue size. Finally we verified the new routing algorithm in an indoor test. The next sections describe these preliminary test and its results. RSSI and Delay Spread Measurement As we stated in Chapter 5, tunnel acts as a waveguide with a cut-off frequency below which no effective propagation occurs. In this case we are above such a cutoff frequency and is thus possible to take advantage of this effect to obtain greater communication ranges than in open space. Using the measures defined in the Section 5.3.3 and Section 5.3.4 to evaluate the variation of the power sensed and the Delay Spread by a receiver, we consider the effect of the multipath and the fading. The mean radio-signal decreases with distance but the fading has a strong presence both in terms of RSSI and Delay Spread that oscillates between 25 ns and 38 ns aproximatively The RSSI is influenced also by the presence of lateral galleries that affect the received signal, producing a sharp fall in the signal intensity in correspondence of the mouths. On the other hand, the waveguide effect allows higher RSSI values along the tunnel than in open space. These aspects have been taken in account in the deployment operations since we wished to provide an efficient multi-hop coverage of the communication. The idea is to deploy backbone nodes in order to optimize the transmission in the tunnel taking advantage of one of the peaks that are visible in the Figure 5.4 and avoiding, instead, the Delay Spread peaks visible in the Figure 5.7. Parameters chosing To obtain a continuous flow without cuts or interruption, voice packet must be exchanged among mobile nodes with and adequate frequency and within its deadline. It means that if we are able to deliver a message each 50 ms, for instance, 100 Applications 6.1. Real-Time protocol in underground voice communication 20 ms IAT = 50 ms 30 ms Voice Data Silence Packet Arrival Figure 6.4: Relation between voice data and inter-arrival time. the packet must contain at least 50 ms of voice. On the contrary, if the packet contains insufficient data (e.g. 20 ms of voice) the listener will hear silence until the arrival of the subsequent packet (see Figure 6.4). We have, thus, to consider the Inter-Arrival Time (IAT) that the communication network is able to provide to decide how much voice data have to be transported within a single packet. We made a first indoor experiment to determine this. We arranged a seven nodes chain network (providing the nodes with a fake LQM) and saturated the network with two end-to-end QoS flows. Figure 6.5 presents both the distribution and the temporary shape of the IAT of the voice packet. The image shows three major peaks, the last of which around the 70 ms and a very small one at about 150 ms. It means that in general we must be able to send at least 70 ms of voice every 70 ms. Moreover the peaks tell us that in some rare circumstances we’ll receive packets 150 ms apart. Since the speex codec, in the configuration used in these experiments, generates data packets containing 20 ms of voice, we whould send: npackets =70 20= 4 (6.3) packets in each loop. On the other hand to absorbe sporadic high IATs, we should have a queue of: nqueue =150 20 = 8 (6.4) packets. This queue will introduce a delay of: delayqueue =nqueue ·20ms = 8 ·20ms = 160ms (6.5) that must be added to the mouth-to-hear end-to-end delay of the packets. This value is however assumable as guaranteed by the ITU-T recomendations [ITU-T 03]. We tested the goodness of these parameters with another indoor experiment, using two real voice flows (128 Kbps each one before compression, about 15 Kbps after speex compression). This time, a movement of one of the nodes (node 0) was simulated through the dynamic modification of the fake LQM. The RSSI provided to the nodes was calculated as a function of the simulated distance and perturbated with a 20% of noise to obtain a similar situation to the real. Moreover all the nodes 101 6.1. Real-Time protocol in underground voice communication Applications 0 2 4 6 8 10 12 14 16 x 104 0 50 100 150 200 250 300 350 400 450 Time (us) Occurrences (a) 0 200 400 600 800 1000 0 2 4 6 8 10 12 14 16 x 104 Sample # Time (us) (b) Figure 6.5: Distribution (a) and raw data of Inter-Arrival Time (IAT) (b) for two saturated flows. 102 Applications 6.1. Real-Time protocol in underground voice communication 0 2 4 6 8 10 12 14 16 18 x 104 0 200 400 600 800 1000 1200 Time (us) Occurrences (a) 0 1000 2000 3000 4000 5000 6000 7000 0 0.5 1 1.5 2 2.5 x 105 Time (us) Position (m) (b) Figure 6.6: Distribution (a) and raw data of Inter-Arrival Time (IAT) (b) . 103 6.1. Real-Time protocol in underground voice communication Applications 0 20 40 60 80 100 120 140 0 100 200 300 400 500 600 700 800 Time (ms) Occurrences Figure 6.7: End-to-end delay distribution. ignored all the frames that, in a real situation, would not have received due to the excessive distance. Figure 6.6 presents the results of the test. The histogram shows now several peaks which one most important is at about 70 ms. The plot shows that the distribution approximately constant along the whole experiment even if this graph give us the information that the peak at 130 ms in the previous figure corresponds principally to the first half of the experiment while the one at 42 ms to the second half. It is due to the reconfiguration of the network during the movement that promotes different delivery paths. On the other hand, the analisys of the end-to-end delay (see Figure 6.7) suggests that the packets honour its deadline since the most part of the packets are delivered in an interval between few milliseconds and 100 ms guaranteeing the correct playback of the voice at the destination node. As expected, no packets were delivered beyond its deadline (150 ms). RSSI and Prim Based Routing The same experiment gave us information about the effectiveness of the RSSI and Prim based routing. Figure 6.8 shows its behavior. The figure is referred to mobile node 0 and shows the identity of the last-hop sender (that is, the identity of the node that delivered the message to node 0) and the RSSI, considered as indicator of the link quality in this article, with which the first listens the latter (see figure 6.9). The two mobile nodes (0 and 6) start closely each other and to the node 5. Several frames are exchanged directly among the node 0 and node 6. Then, node 0 starts moving toward the other end of the backbone. The link quality with 104 Applications 6.1. Real-Time protocol in underground voice communication 0 1000 2000 3000 4000 5000 6000 7000 −95 −60 −35 Position (m) RSSI 0 1000 2000 3000 4000 5000 6000 7000 0 1 2 3 4 5 6 Node Id Figure 6.8: RSSI and Prim based routing simulation. 1 p3 p4 p 2 p5 p 0 p6 ptoken auth message last-hop 1 23 4 5 6 7 8 910 11 12 13 last-hop sender Figure 6.9: Identity of the last-hop sender. node 6 falls and node 0 begins to exchange frames with node 5 following the rules marked by the Prim’s algorithm. The same occurs with the subsequent nodes. As expected, the link quality with the sender is always maintained at acceptable values. The algorithm suffers from short oscillations in the switching point due to RSSI noise that are, however, completely assumible by the system. In some situation, moreover, node 0 acts as a bridge between adjacent nodes again due to the RSSI fluctuation. 6.1.4 Real experiment The real experiment consisted in the deployment of the cited five nodes. Table 6.1.a lists the parameter values used in the tests while table 6.1.b shows where the backbone nodes have been deployed along the tunnel in order to provide a suitable inter-backbone node RSSI value. The third node position, however, was chosen in the peak nearest to the tunnel 105 6.1. Real-Time protocol in underground voice communication Applications Parameter Values Scenario Frequency 2.412 GHz Channel rate 6 Mbps Tx Power 100 mW Data Pkt size 160 Byte QoS flow rate 15 Kbps Constraints Deadline 150 ms (a) Position [m] Nodes 1 - 2 ≈2000 Nodes 2 - 3 ≈2000 Nodes 3 - 4 ≈1200 Nodes 4 - 5 ≈1500 (b) Table 6.1: Parameters used in the real tests. Flow 1 Flow 2 PDR [%] 98.2 % 97.9% MOS >3.5>3.5 Table 6.2: Main testbed results. slope change. In this way we guaranteed the presence of LoS between each couple of nodes. Especially, the third node act as relay between the left-side and the right-side of the chain that have not LoS between them due to the change in slope. Two laptops running Linux OS were used as mobile nodes. The sampling of the voice signal was performed accesing directly the /dev/dsp device and compressing 320 byte of data (160 samples of 16 bit) to a 40 bytes speex packet (20 ms of voice). Packets were aggregated in groups of four and sent to the other mobile node and as in the laboratory experiment, the QoS extension was configured to transport up to two QoS messages in each protocol loop (see [Sicignano 10b] for details). One of the mobile nodes was maintained still at about 400 m apart from one of the backbone end while the other was moved, within a car, toward the other end of the backbone maintaining in any moment the voice link. The movement speed was about 40 km/h. The most notable parameters for evaluating voice transmission are the Packet Delivery Ratio (PDR), the end-to-end delay and the variance of the voice packet inter-arrival time (jitter). The following sections show the result of the experiments. PDR and MOS Table 6.2 lists the main results related to the characteristics of the voice transmission obtained in the real experiments when the two mobile nodes were communicating with each other. PDR is a measure of the percentage of packets that reach the destination (see Section 1.4). In our tests, we registered values around 98% 106 Applications 6.1. Real-Time protocol in underground voice communication during the whole duration of the test. With this level of PDR, speex audio codec guarantee a MOS greater than 3.5, which was approximately the MOS level that we achieved during the test. This value is considered fair (imperfections can be perceived but the sound remains clear). Delay and jitter The IAT in the real experiment (see Figure 6.10) is quite similar to the one obtained in the indoor experiment even if we can notice a little widening of the distribution due to the presence of a little percentage of discarded packet (about 2% as anticipated earlier). The analisys of the same parameter as a function of the time presents also a similar behavior but again in a wider range due to the fact the nodes that were not in a virtual chain but were free of communicating among them following the routing algorithm based on real link quality. Figure 6.11 shows the distribution of the end-to-end (from mouth-to-hear) delay obtained during the real experiment. Again, the shape is a little wider due to the movement of the node along the tunnel but conserve the behavior of the simulation experiments. The most part of packets were delivered within 100 ms of its creation, honouring comfortably its deadlines. RSSI and Prim Based Routing Figure 6.12, tries to illustrate the effectiveness of the Prim and RSSI based routing algorithm. As in figure 6.8, the red line shows which (backbone) node have delivered the message containing the voice data to the mobile node (node 0) and the link quality among them. As can be seen, at the beginning frames where directly exchanged between the mobile nodes 0 and 6 (due to the fact that they were close each other) or through node 5. When node 0 started to move towards the end of the backbone (node 1), the routing algorithm adapted itself to provide always a good delivery path. This is reflected by the fact that the last-hop was executed by different nodes during the movement along about 7.5 km of the tunnel. The graph shows, despite the high level of noise that is usual in RSSI measurement, the good work of the routing algorithm specially thanks to the introduction of the Prim algorithm. In fact, it promotes the exchange of data among the mobile nodes and the closest (from the link quality point of view) backbone node. As can be seen, the RSSI is maintained above the value of −60dBm. This value is considered high enough to guarantee a reliable link. Traffic Influence The most part of the experiments have been carried out in an empty tunnel in which the only vehicle involved was the one that transported the mobile node. However, to verify the influence of the traffic on the communication, we carried out an additional experiment simulating the presence of a light traffic. We positioned 107 6.1. Real-Time protocol in underground voice communication Applications 0 0.5 1 1.5 2 2.5 3 x 105 0 100 200 300 400 500 600 700 800 900 1000 Time (us) Occurrences (a) 0 1000 2000 3000 4000 5000 6000 7000 0 0.2 0.4 0.6 0.8 1 1.2 1.4 1.6 1.8 2 x 105 Time (us) Position(m) (b) Figure 6.10: (a) Distribution and (b) raw data of Inter-Arrival Time (IAT) in the real experiment. 108 Applications 6.2. Robot teams for exploration in underground environments NCM LOM COM SUM COM SUM BASE STATION MOBILE ROBOT GUI SPEEX CAMERA DRIVER SPEEX Figure 6.14: Modules and information flows. Hardware architecture For this experiment, we have used a team of robots composed of two Pioneer P3-AT robots (ActivMedia MobileRobots). Each robot is equipped with an on-board PC with a Pentium III processor at 800 MHz. Regarding the wireless communications, the robots have an Atheros 802.11 a/b/g wireless card in order to exchange information between them and the base station, and for monitoring the quality of the signal between them. Depending on the role that has the robot in the team, it will incorporate differents sensors. The only common sensor for all robots is the laser sensor. The robot incorporates a SICK LMS 2000 laser range finder. This sensor gives us the ability to configure their maximum range up to to 80 meters. This feature is very useful, since in the experimental environment we work with great distances. The robot that has to go inside the shelter incorporates a microphone and a speaker in order to establish a communication with the base station. It also has a camera (Unibrain Fire-i) to capture images. Finally, the base station consists of a laptop with an Intel Core 2 Duo 1.6 GHz processor and an Ubiquity 802.11 a/b/g wireless card. The base station also has a speaker and a microphone to communicate with the leader robot and the injured person and a joystick to control remotely the robots and the pan/tilt mechanism. Software architecture The software architecture was implemented over the onboard computers which run a Linux Debian with kernel 2.6.18. It has been designed and implemented in a modular solution replicated in each robot (figure 6.14): •The COM module provides multi-hop, real-time communication among robots and base station. It also measures the communication link qualities among 115 6.2. Robot teams for exploration in underground environments Applications robots and base station. Additionally it offers QoS communication between the lead robot and the base station. •The NCM module generates velocity commands for the robots, providing a safety navigation towards the goals assigned by the SUM. It uses the information of the robots’ sensors (odometry and laser) combined with the localization provided by the LOM module, in order to carry the navigation out. •The LOM module provides a global localization for the robots, using the information of the laser and odometry sensors and a pre-existent map. This localization information is also sent to the SUM module that exports it to the COM module that, in turn, send it through the network to the base station. •On the robot side, the SUM module is in charge of sending commands to the other modules (goals, emergency stops, resumes, etc.) and is also responsible for selecting the flow of information to send through the network (e.g. laser readings or voice). On the base-station side, it generates such commands, once requested by the operator through its GUI. The remaining modules (speex and camera driver) shown in the figure 6.14, are auxiliary modules used to access to the multimedia devices. 6.2.5 Communication Module As anticipated, the communication among the robots and between them and the base station must obey to a set of important conditions and characteristics. Above all, the network protocol must support multi-hop communication since is not possible a direct connection between the lead robot and the base station, due either to the excessive distance and to the absence of the line-of-sight between the two ends. On the other hand end-to-end delay must be known and bounded: joystick commands, for example, must reach the robot with few delay to allow a correct telemanipulation. We can say the same for the laser data that must be visualized frequently to give a useful visual feedback. Also, message prioritization is fundamental since, again, laser data must have priority over, for example, image data and joystick commands over laser to avoid dangerous delays in the control. Finally network must be able to support Quality of Service (Qos) traffic to allow the transport of voice. The RT-WMP and its QoS extension, described in Chapter4, offer all of these characteristics together. 6.2.6 Navigation Module The navigation module is composed of two layers. The low-level layer which is in charge of providing a safe navigation, and the high-level layer that provides 116 Applications 6.2. Robot teams for exploration in underground environments the tasks to the robot. Given a goal, the low-level layer is able to provide a safe navigation in order to reach it. This module ensures that, regardless of who assigns the goals (high-level layer or the operator at the base station), the robot can navigate safely to them. A new method called Nearness Diagram High Speed (NDHS) is carried out by the low-level navigation layer: it combines the ability of the obstacle avoidance method ND [Minguez 04] to navigate in dense environments with that to navigate at higher speeds when there are no obstacles nearby. In the figure 6.15 an outline of the technique used is shown. The second component is the high-level layer, which is in charge of assigning to each of the robots their target. These targets may change depending on the role of the robot and the phase of the experiment in which they are. Three navigationmodo exist. The first mode is to go to a target, sending to the low-level layer all the goals that come from the SUM layer. The second oneis the telemanipulationusing a jostick The third mode, tracking mode configuration, allows moving a chain of robots where each of them follow the preceding one when the leader moves. More details are present in [Tardioli 11]. ND Security zone ND-HS Obstacle_2 Obstacle_3 Obstacle_1 Robot Security zone Figure 6.15: Diagram of the security zones of the algorithm. 6.2.7 Localization Module The localization module provides the robot position using a two-dimensional map and information extracted from the laser readings. Starting from a map of points, it has been segmented offline and all the features have been stored in a segments-set that describes the environment. When online, the localization algorithm segments the laser sensor readings and tries to match the features obtained with the set of those representing the map. The laser sensor segmentation technique is based on a tracking-like algorithm combined with a validation gate used to classify the range readings into regions. These regions are successively splitted into segments, 117 6.2. Robot teams for exploration in underground environments Applications which approximate the environment seen by the robot, through a polygonal approximation technique. These observations are matched with the map features to decrease the location uncertaintity of the robot and then are combined with the predicted location that comes from encoders using an Extended Kalman Filter (see [Castellanos 99] for details). 6.2.8 Supervisor Module A pratical issue in a robotic surveillance experiments is the direct control of all the phases of the mission. The SUM module is the software component in charge of providing the supervision of the events that take place during the mission. The SUM has two different identities that resides in two different places: the robotside and the base-station-side. On one hand, the base-station-side is in charge of sending, through the COM, the command generated by the operator at the GUI. Such commands are: •Start, return and abort mission command: it initialyzes the formation to start the mission and to send the return command. It also allows to abort the mission if a problem occurs. •Goal selection: the GUI provides a point-and-click utility to select the a global goal in an easy way. •Telemanipulation control: By moving the joystick, a goal is assigned to the navigation algorithm as a function of the stick position for telemanipulation actions. •Pan-tilt control: it provides an interface to control the pan-tilt of the camera using a jostick. •Photo request: by pressing a button, there provides users a fast way to capture a single environmental image. •Laser readings request: the function requires the laser readings to a specific robot. •Voice communication request: this feature enables voice transmission between the base station and the last robot. All the commands are sent through the COM using the command flow and act directly on the robot-side SUM. Some of that are request-reply commands (e.g. photo request) while other only act on the correspondent module (e.g. telemanipulation control). Finally two of them, voice communication request and laser request, activate a service that offer laser views of a specific robot and voice link with the leader robot respectively. The GUI is in charge also of interpreting, visualizing or reproducing the input information flows (laser, photos, etc.) and offers: 118 Applications 6.2. Robot teams for exploration in underground environments Figure 6.16: Two snapshots of a laptop screen running the GUI in the base station. •Global map visualization: a global vision of the environment is offered in a main view to localize robots at all times. •Robot laser readings: the function shows the actual laser scanning in a specific view. •Photo visualization: the photo received from the selected robot (after a specific request) are visualized in a image view. •Voice record/play: encode/decode and replay voice from/to the leader robot. •Link quality check Operators can check constantly the link quality between robots and the base station. Two snapshot of the GUI are showed in figure 6.16. On the robot-side, the SUM is in charge of executing the commands sent by the operator activating the voice service or sending a goal to the NCM module, for example, when requested. It also sends autonomously the localization to the base station requesting it to the LOM. 6.2.9 System network configuration As anticipated, several flows of information both real-time and QoS were involved in the communication. Globally we used 6 real-time flows and 2 QoS flows. Specialization on the environment Although RT-WMP has been designed to support real-time communication giving support to any type of topology, in thes experiment considered here, most of the time the three nodes will constitute a chain network. We used this a priori information to improve the routing adding a Prim-algorithm based scheme in a similar way as we presented in Section 6.1.2. 119 6.2. Robot teams for exploration in underground environments Applications Name Size (B) Frequency (Hz) Priority Joystick 8 on-demand 5 Robot Control 8 on-demand 4 Pose 16 10 3 Laser 720 4 3 Pan-tilt 8 on-demand 2 Camera 1.5Kon-demand 1 Table 6.3: Real-time flows used in the system. Real-time flows Table 6.3 shows the characteristic of each flows. The most part of the flows are ondemand. Only the poses and the laser scans are updated with a constant frequency but, while the two robots update their poses simoultaneously (2 identical flows towards the base station) to allow a more useful visualization in the GUI, the activation of the latter flow is requested by the base station to reduce the bandwidth needed by this task. The robot control flow, originated from the SUM, is in charge of managing the robot in particular situations (for example an emergency stop) or to give specific commands to the robot (to force a relocalization, for example) or, again, to select which robot has to send its laser scan over the network. The joystick-command messages, also originated from the SUM are sent after a joystick movement and have the highest priority for the reasons discussed earlier. The camera-related flows (pan-tilt and images) are considered the less critical. Thus they have the less priority. Especially the image flow is the less priority of the system. In fact, even if the snapshot captured by the camera is resized and compressed to obtain a jpeg format, it normally has a size of about 3.5-4 KB (320 ×200 pixels, black and white format). Since the biggest message that the RT-WMP can manage is 1500 bytes, the image has to be split in three parts that are sent separately in different RT-WMP loops. If their priority would be high, it could delay more important flows like joystick commands. QoS flows The two QoS flows have identical requisites. The objective is to have good-quality full duplex communication with as less as possible mouth-to-ear delay. To obtain a continuous flow without cuts or interruption, voice packet must be exchanged among mobile nodes with and adequate frequency and within its deadline. It means that if the protocol is able to deliver a message each 50 ms, for example, such a message must contain at least 50 ms of voice. The worst-case Inter-Arrival Time (IAT) (see [Sicignano 11]) that the communication network is able to offer in a 3 node chain configuration is about 50 ms. Since that the speex codec [RFC5574 09] 120 Applications 6.2. Robot teams for exploration in underground environments (a) (b) (c) (d) Figure 6.17: Screenshots from real experiment. We can see the formation moves along the tunnel (a), how the last robot approaches (b) and explores the shelter (c) and finally formation coming back to initial point(d). used in the communication generates data packets containing 20 ms of voice each one, we need to send at least: nsamples =50 20= 3 (6.6) samples (60 ms of voice) in any loop. On the other hand to absorbe sporadic high-IATs, we set a reception queue qof 3 packets considering an IATmax of IATmax =qsize ·20ms ·nsamples = 3 ·20 ·3 = 180ms (6.7) The IATmax also represents the delay added by the queue to the mouth-to-hear end-to-end delay of the packets. This value is however assumable as guaranteed by the ITU-T recomendations [ITU-T 03]. On the other hand the packets’ deadline was fixed at 150 ms that correspond to maximum end-to-end delay admitted for multimedia traffic [Vlaovic 01]. 121 6.2. Robot teams for exploration in underground environments Applications R1 R1 R2 R2 R2 BS 300m 100m a) b) c) Refuge Tunnel Lateral Gallery Figure 6.18: Phases of the experiments (way out). 6.2.10 Results of the experiment In this section the results of the experiment described in section 6.2.2, successfully carried out in the Somport tunnel are presented. Figure 6.17 shows some moments of the experiment. Additional videos are available at [Multimedia 11]. The formation starts in its initial configuration close the base station. The start-mission command is sent through the GUI and the formation moves along tunnel maintaining a stable trajectory, how shown in figure 6.17a. Figure 6.17b shows how the last robot R2 approaches the shelter. The exploration of the shelter is instead showed in figure 6.17c. Finally, as a result of a command requested by the operator, the robots return to the base station (figure 6.17d). Communications The bandwidth consumed in static conditions by the real-time flows was about 25 kbps with peaks of 70 kbps when had to manage an image request. Considering that we configured the wireless device to a rate of 11 Mbps, the RT-WMP had no problem to manage this flow of data even in presence of QoS flows that occupied globally 30 kbps. On the other hand, it is interesting to analyze the quality of the links between the three nodes during the experiment. Figure 6.18 shows the relevant phases of the way out and figure 6.19, the link qualities in terms of Received Signal Strength Indicator (RSSI) between the base station (BS), the head robot (R2) and its follower (R1). At the beginning the three nodes are close each other and the signal among them is about 100% (figure 6.18.a). Then R1 and R2 start to move: the RSSI between them is more or less constant (despite the noise) and stays around 122 Applications 6.2. Robot teams for exploration in underground environments 0 300 600 900 1100 0 20 40 60 80 100 Time [s] RSSI BS − R1 BS − R2 R1 − R2 Turn Figure 6.19: RSSI among robots and base station during the way out. 90% (they are only few meters apart). However the signal between them and the base station starts to fall, as expected, due to the increasing distance. When the robots are close to the intersection point, R1 stops while R2 enters the lateral gallery (figure 6.18.b). Suddenly a strong link quality fall affects the link between BS and R2 due to the loss of the line of sight between them. Also the link quality between R1 and R2 suffer from a fall but it is smoother and stabilizes at about 30% even when the robot R2 enters and stay within the shelter (figure 6.18.c). On the contrary the link between BS and R1 remains in optimal values during the whole experiment thanks to the good propagation characteristics of the tunnel that, at the frequency used (2.4 GHz), acts like a waveguide. The connection between R2 and the base station has been maintained during the whole experiment (see Figure 6.19). The use of the Prim-based specialization helped to maintain a very low percentage of errors in terms of RT-WMP packet loss (about 1.12%) since nodes always used the best links to communicate. From the point of view of the QoS traffic, we have considered the quality perceived by the user or MOS (see Section 1.4). Voice communication obtained a MOS of 3.5 approximately that is considered fair (imperfection can be perceived but the sound remains clear), being the QoS PDR higher than 96% for both flows. The mouth-to-ear delay was completly aceptable and did not bother the interlocutors. The main communication results of the testbed are resumed in Table 6.4. Dynamic Figure 6.20 shows the velocities (linear and angular) of the lead robot during the way out. The linear speed was fixed at about 0.8 m/s. However it suffered from many oscillations due to the uneveness of the ground that was full of small stones 123 6.2. Robot teams for exploration in underground environments Applications 0 300 600 900 1100 −1 0 1 2 Velocity (m/s) 0 300 600 900 1100 −1 0 1 2 Time [s] Velocity (rad/s) Angular velocity Linear velocity Turn Room entrance Movements inside refuge Intersection Figure 6.20: Velocities of the lead robot during the way out and pot holes. The same irregularities provoked a frequent reorientation of the robot, also visible in the graph showing the angular velocity. The graph, moreover, shows clearly the moment in which the robot reaches the intersection point (arount point 620 s) and when it, after an abrupt turn, starts to travel toward the shelter in the lateral gallery. In this second stretch, the velocity was slightly higher thanks to the fact that the gallery is a little downhill. Once the robot reached the door, it reduced the speed to enter the shelter guided by the reactive navigation algorithm. When inside, the operator moved manually the robot causing visible changes in the linear and angular velocities. RT-WMP Flow 1 Flow 2 Pkt Loss 1.12% PDR [%] 96.11 % 96.9 % MOS ≥3.5≥3.5 Table 6.4: Main testbed results. 6.2.11 Conclusions In this work we presented the results of an experiment whose objective was to explore in a semi-autonomous manner an emergency shelter where a presumed injured person is waiting for assistence after an accident. During the experiment, carried out in the Somport tunnel, a team of two robots was sent toward the shelter situated in a lateral gallery of the tunnel about 400 meters apart, while a human operator supervised the operations in a base station by means of laser-scan and camera feedbacks. Once one of the robots arrived at the shelter the operator could move it using a joystick and interact vocally with the injured person. 124