Timed automata were introduced by R. Alur and D. Dill as an operational model of real-time systems. In their simplest form timed automata extend classical finite automata, having only finitely many control states, by clock variables ranging over the non-negative real numbers (continuous time). Constraints on the values of the clock variables serve as guards of the transitions and as invariants in the control states. Timed automata can be combined into networks by using parallel composition and restriction operators of process algebras like CCS or CSP. One of the most important results on timed automata is that it is decidable whether a given control state is reachable. This led to the development of several tools for the automatic verification of behavioural properties of timed automata. Here we shall present in more detail the tool UPPAAL.

Timed automata

Timed automata engage in transitions from locations to locations when certain timing conditions are satisfied. These transitions either perform input and output actions on channels that will synchronise with other timed automata working in parallel or they perform internal actions that are invisible from the outside.

As a first contact with timed automata let us look at an example.

Example 4.1 (Light controller)

We wish to model a light controller with the following behaviour. Initially, the light is off. When the switch is pressed once, the light goes on (into a dim mode). If the switch is pressed twice quickly the light gets bright. Otherwise, if the switch is pressed only after a while the light goes off again.

What is a real-time system?

This book is about the design of certain kinds of reactive systems. A reactive system interacts with its environment by reacting to inputs from the environment with certain outputs. Usually, a reactive system is not supposed to stop but should be continuously ready for such interactions. In the real world there are plenty of reactive systems around. A vending machine for drinks should be continuously ready for interacting with its customers. When a customer inputs suitable coins and selects “coffee” the vending machine should output a cup of hot coffee. A traffic light should continuously be ready to react when a pedestrian pushes the button indicating the wish to cross the street. A cash machine of a bank should continuously be ready to react to customers' desire for extracting money from their bank account.

Reactive systems are seen in contrast to transformational systems, which are supposed to compute a single input–output transformation that satisfies a certain relation and then terminate. For example, such a system could input two matrices and compute its product.

We wish to design reactive systems that interact in a well-defined relation to the real, physical time. A real-time system is a reactive system which, for certain inputs, has to compute the corresponding outputs within given time bounds. An example of a real-time system is an airbag. When a car is forced into an emergency braking its airbag has to unfold within 300 milliseconds to protect the passenger's head. Thus there is a tight upper time bound for the reaction. However, there is also a lower time bound of 100 milliseconds.

In this chapter, some of the recent interesting research work related to UWB ranging and positioning are briefly reviewed. The purpose of the chapter is not to describe these studies in detail, but rather to point out specific recent references that may yield further research.

Development of accurate ranging/positioning algorithms

As discussed in the previous chapters, ranging and localization via UWB radios have been investigated extensively in the literature. While CRLB and ZZLB provide lower bounds on the ranging/localization accuracy, low-complexity and efficient estimators that approach these bounds in practical scenarios are still needed.

There are numerous recent research studies that aim at improving UWB ranging/localization accuracy. One research direction is joint estimation of range and location. In [170], it is shown that a two-step approach that uses independent decisions in ranging and localization steps is asymptotically optimal at high SNRs. However, it requires perfect estimates of delays, attenuations, and pulse shapes related to the received multipath components (MPCs) in order to construct an optimum correlation template at the receiver, which is very difficult to achieve in practice. Without perfect a-priori information of the channel parameters, such a two-step method returns unreliable TOA estimates during the ranging step. Since the measurements are separately performed at each reference node, without a constraint that all the measurements correspond to the location of the same mobile terminal, such approaches are suboptimal [137]. A better approach would be to make least commitment, where intermediate information is preserved and propagated till the end [393]. In other words, the received channel responses should not be discarded until a final decision regarding the target node location is made.

Wireless channel models carry significant importance for gaining insight into designing physical layer systems and selecting certain system parameters. For instance, in an IRUWB system, a design engineer might need to know how much apart to transmit two sequential pulses in order to avoid inter-frame interference at the receiver, or how likely the first arriving signal component contains the highest energy among all signal components for accurate ranging. Answers to such questions can be obtained either directly from channel measurements conducted in an environment of interest, or from statistical models derived from channel measurement campaigns.

There are various channel modeling techniques (e.g. ray tracing and statistical modeling) [93–96] and channel sounding methods (e.g. time-domain vs. frequency domain) [97, 98], which have been studied extensively in the literature. The focus of this chapter is not those well-known channel modeling techniques, but mainly the UWB channel models recently proposed and their interpretations for positioning applications.

Many UWB channel modeling campaigns have been performed within the past few years, mainly due to emerging UWB standards (e.g. multiband OFDM-UWB, IEEE 802.15.4a, and IEEE 802.15.3c) [96, 97, 99–101]. Although channel statistics and models of various frequency bands are publicly available, many of those do not explicitly include ranging-related statistics. Therefore, one of the aims of this chapter is to investigate UWB channel models from a range estimation perspective.

Designing a wireless system typically involves the steps illustrated in Fig. 3.1. First, application requirements need to be explored. Low attenuation at low frequencies makes through-the-wall communications and tracking applications attractive, but it is difficult to adopt sub-GHz UWB systems due to coexistence issues with existing narrowband systems.

As discussed in the previous chapter, the position of a mobile node in a wireless network can be estimated based on AOA, RSS, TOA, and/or TDOA of received signals. Due to their large bandwidths, UWB signals have very high time resolution, hence individual multipath components (MPCs) can be resolved at the receiver. While AOA, TOA, and TDOA approaches all benefit from this high resolution, AOA-based implementations have high complexity. Therefore, positioning based on TOA (or TDOA) estimation is the method of choice in UWB-based positioning systems [196] as opposed to AOA or RSS (which has low ranging accuracy)-based approaches. Therefore, the emphasis of this chapter is on time-based UWB ranging techniques.

The chapter is organized as follows. In Section 5.1, the time-based positioning problem is briefly re-visited and importance of accurate ranging for precise positioning is emphasized. The error sources in time-based ranging are discussed in Section 5.2. In Section 5.3, the time-based ranging problem is formulated and models for various transceiver types are studied. Section 5.4 reviews fundamental limits on the accuracy of time-based ranging, Section 5.5 investigates maximum likelihood (ML)-based techniques, and Section 5.6 presents alternative low-complexity ranging algorithms for UWB systems.

Time-based positioning

Consider a wireless network in which there are Nm reference nodes (RNs). The ith RN is located at (xi, yi), and a target node (TN) at position (x, y).

Commonly, an ultra-wideband (UWB) signal is defined to be a signal with a fractional bandwidth of larger than 20% or an absolute bandwidth of at least 500 MHz. The main feature of UWB signals is that they occupy a much wider frequency band than conventional signals; hence, they need to share the existing spectrum with incumbent systems. Therefore, certain regulations are imposed on systems transmitting UWB signals. In this chapter, after a detailed description of UWB signals, various regulatory rules on UWB systems in different parts of the world are investigated. Then, emerging UWB standards for wireless personal area network (WPAN) applications are studied.

Definition of UWB

Although Guglielmo Marconi's spark gap radio transmitters were sending UWB signals across the Atlantic Ocean in 1901, the rigorous investigation of UWB systems was stimulated by the studies on impulse response characterization of microwave networks in the 1960s [63, 64]. Instead of the conventional swept-frequency response characterization, a linear-time-invariant (LTI) system was characterized by its response to an impulse in the time domain. After employing impulses to characterize behavior of various systems, it was also realized that such impulses could also be used in radar and communications systems [65]. The first UWB communications patent was issued in 1973 to Gerald F. Ross on transmission and reception of baseband pulse signals [66].

Early names for UWB technology include baseband, carrier-free, non-sinusoidal and impulse. The term UWB was coined by the US Department of Defense in the late 1980s. A UWB signal is characterized by its very large bandwidth compared to the conventional narrowband systems.

Wireless communications are becoming an integral part of our daily lives. Satellite communications, cellular networks, wireless local area networks (WLANs), and wireless sensor networks (WSNs) are only a few of the wireless technologies that we use every day. They make our daily lives easier by keeping us connected anywhere, anytime.

Since more and more devices are going wireless every day, it is essential that future wireless technologies can coexist with each other. Ultra-wideband (UWB) is a promising solution to this problem which became popular after the Federal Communications Commission (FCC) in the USA allowed the unlicensed use of UWB devices in February 2002 subject to emission constraints. Due to its unlicensed operation and low-power transmission, UWB can coexist with other wireless devices, and its low-cost, low-power transceiver circuitry makes it a good candidate for short- to medium-range wireless systems such as WSNs and wireless personal area networks (WPANs).

One of the most promising aspects of UWB radios are their potential for high-precision localization. Due to their large bandwidths, UWB receivers can resolve individual multipath components (MPCs); therefore, they are capable of accurately estimating the arrival time of the first signal path. This implies that the distance between a wireless transmitter and a receiver can be accurately determined, yielding high localization accuracy.

Such unique aspects of UWB make it an attractive technology for diverse communications, ranging, and radar applications such as robotics, emergency support, intelligent ambient sensing, health-care, asset tracking, and medical imaging (see Fig. 1.1).

This chapter discusses three special topics related to ranging. First, techniques to mitigate various types of interference are presented. Second, carrier sensing methods that can be used to improve ranging performance for IEEE 802.15.4a networks are briefly reviewed. Finally, an overview of mechanisms that provide privacy and security for ranging signals and range information is given.

In this chapter, it is assumed that ranging is performed via frames that consist of preamble, start of frame delimiter (SFD), physical layer header (PHR) and payload, and also that the preamble is used for ranging (similar to the IEEE 802.15.4a systems studied in the previous chapter). Frames with longer preambles provide a higher processing gain for ranging due to improved SNR and lead to better ranging accuracy. This is because at high SNRs, detection of the direct path signal is easier. On the other hand, employing a longer preamble induces a drawback that the preamble becomes more vulnerable to interference and jamming attacks. In case that acquisition of a frame fails, the frame needs to be retransmitted.

Interference can be detrimental to ranging accuracy, even if it does not cause acquisition failure. At times the leading signal path gets buried under interference, so that it may be quite difficult to determine its arrival time. Remember from Chapter 6 that performance of ranging protocols is very sensitive to timing. This mandates rapid handling of all ranging related transmissions. If retransmissions of ranging frames were scheduled with high priority, regular data traffic would be penalized, and throughput and latency for the data traffic would degrade. Furthermore, each retransmission may potentially interfere with transmission of peer devices in the same network.

Ability to locate assets and people will be driving not only emerging location-based services, but also mobile advertising, and safety and security applications. Cellular subscribers are increasingly using their handsets already as mapping and navigation tools. Location-aware vehicle-to-vehicle communication networks are being researched widely to increase traffic safety and efficiency. Asset management in warehouses, and equipment and personnel localization/tracking in hospitals are among other location-based applications that address vast markets. It is a fact that application space for localization technologies is very diverse, and performance requirements of such applications vary to a great extent.

The Global Positioning System (GPS) requires communication with at least four GPS satellites, and offers location accuracy of several meters. It is used mainly for outdoor location-based applications, because its accuracy can degrade significantly in indoor scenarios. Wireless local area network (WLAN) technology has recently become a candidate technology for indoor localization, but the location accuracy it offers is poor, and also high power consumption of WLAN terminals is an issue for power-sensitive mobile applications. Ultra-wideband technologies (UWB) promise to overcome power consumption and accuracy limitations of both GPS and WLAN, and are more suitable for indoor location-based applications.

The Federal Communications Commission (FCC) and European Commission (EC) regulate certain frequency bands for UWB systems. These have prompted worldwide research and development efforts on UWB. Another consequence was development of international wireless communication standards that adopt UWB technology such as IEEE 802.15.4a WPAN and IEEE 802.15.3c WPAN.

The writing of this book was prompted by the fact that UWB is the most promising technology for indoor localization and tracking.

The previous chapter deals with detecting time of arrival of first signal path. Even though it is an essential and the very first step in TOA-based ranging and positioning systems, more need to be done to obtain range and position estimates. The TOA information makes sense only if the signal's time of transmission is known. Then, time of flight (TOF) of the signal can be easily computed. The TOF is directly proportional to the distance between a device that transmits the signal and the device that receives it. There are various protocols to transform any TOA information to a TOF and range estimate. Ranging protocols require actions to be taken at devices that are involved in ranging and positioning. The focus of this chapter is to study these protocols in detail.

The chapter consists of three parts. The first part provides an overview of communication protocol layers and explains functionalities of the service and management interfaces between adjacent layers. It is important to know what intra- and inter-device events take place for obtaining ranging information and how ranging-related information is passed from the physical layer to the upper layers for application's use. Interfaces play a key role in achieving this. A good example of an intra-device event is management of ranging signal parameters at the MAC sub-layer and then generation of the signal accordingly at the PHY. What constitutes an inter-device event is transmission and reception of ranging signals and ranging-related messages (e.g., time-stamps).

The second part takes a detailed look into well-known time-based ranging protocols and analyzes their advantages and drawbacks. There are numerous ranging protocols.

Benefits of Fixed-Mobile Convergence

Throughout this book we analyzed in great detail the technologies behind fixed wireless cellular mobile networks convergence. In doing this, we used the shortened term Fixed-Mobile Convergence (FMC). However, convergence has multiple facets and a long history of expectations, and sometimes marketing hype. The FMC term has been used since the early attempts to integrate voice and data through the convergence of telecommunication and data communications networks. Later, the term was used for the convergence of digitized services such as ISDN. The development of the new wave of land based wireless communications brought the convergence term back as the on-going process of integration of wireless networks and wired networks. Returning to the narrow definition adopted for this book, fixed wireless and cellular mobile networks convergence, we can summarize the goals and benefits of FMC as follows:

• Communications anytime, anywhere, using any wireless technology;

• Continuous communication and operation regardless of the network used;

• Convenience for the user with a single handset and telephone number;

• Improved cost/performance factors by automatic selection of the network with highest available bandwidth and lowest cost;

• High availability by having multiple networks that can be used for transmission;

• Flexibility in the network design by combining indoor and outdoor, and short range and long range communications;

• Support for fixed, nomadic and highly mobile users;

• Service portability across heterogeneous networks.

The achievement of these goals requires positive answers and solutions in the following areas:

• Economics of FMC with adequate Return on Investment;

• Standardization of transparent handover operations;

• Scalability of convergent architectures which is critical in urban and metropolitan areas;

• […]

Cellular Mobile Radio Communications Concepts

In the first chapter we provided an extensive introduction to wireless communications. Major aspects such as general models for wireless communications, architectural components, and networks classification were introduced. We have also discussed, mainly at the level of acronyms, many of the elements that constitute the complex world of wireless communications. This was done in the context of the even larger legacy wired world. Key to wireless communications is the wireless link established between transmitter and receiver. The type of this link will determine the kinds of wireless communications. In this section we will limit analysis to terrestrial mobile cellular radio networks that, in simple terms, are the radio links established between Mobile Stations (MS) such as handsets and the Basic Transmission Stations (BTS).

Initially, the approach to mobile radio was the same as that in radio or television broadcasting, where a BTS was placed at the highest point of the desired area to be covered. As the number of mobile users increased, congestion eventually occurred because of the limited available spectrum. To assure that frequencies can be reused across geographical regions, mobile communication uses the concept of individual micro cellular radio systems. The cells can be created by earth-based radio tower transmitters/receivers or by satellite footprints. Clusters of 7 terrestrial cells provide an area coverage and separation of commonly used groups of frequencies. The number of total channels supported, hence the network capacity, will be determined by the number of clusters that are implemented.