In this paper we use two Recursive Least Squares (RLS) estimation methods to solve the cooperative localization problem based on Wi-Fi received signal strength measurements between pairs of nodes in a network that can establish communication links. A link can be between an anchor node and a non-anchor node or between a pair of non-anchor nodes. It is the latter piece of information that makes cooperation possible and this problem different from multilateration. We evaluate the performance of Newton-Raphson and Gauss-Newton RLS methods and show that cooperation can offer significant gains in performance over multilateration, which does not use cooperation.

Causality is a basic concept in system theory. In this paper we introduce the notions of causal and non-causal indoor localization. A non-causal localization system uses future signal and sensor measurements, in addition to past and present ones, to estimate the location of a person or an object at the present time. We provide example use cases where non-causal localization could prove useful.The main contribution of the paper is the development of an indoor localization system based on Wi-Fi fingerprinting and the Viterbi Algorithm that could be used in both causal and non-causal modes. Our proposed method finds the best "path" in a building matching a time series of Wi-Fi scan results made by the mobile device carried by the person to be located over a period of time. Our system improves localization accuracy by using the knowledge of building floor plans and the fact that humans do not move faster than a certain speed.We evaluate the performance of the causal and non-causal versions of our system and compare them against the basic WiFi fingerprinting localization system based on the KNN algorithm in an office building. Our empirical results show that both the causal and non-causal versions of our system outperform the basic fingerprinting system, with the non-causal version yielding significantly higher accuracy than the basic fingerprinting system.

NIST carried out comprehensive testing in five large buildings to compare the accuracies of Fused Location Provider (FLP) Application Programming Interface (API) for Android phones and Core Location running on iPhones. The testing was done under various mobility modes using the performance metrics provided in the international standard ISO/IEC 18305. This paper presents the results of these evaluations for horizontal, vertical, and 3D errors. Even though in some cases and respects Core Location is better than FLP, it can be said that overall FLP has better accuracy than Core Location, at least in the buildings we used for testing. While Core Location consistently provides location estimates at a fast rate, FLP provides location estimates at a slower rate and sometimes it does not provide elevation information. The paper also compares the accuracy of FLP with that of the best Android app that won the PerfLoc Prize Competition organized by NIST for development of Android indoor localization apps.

This paper describes the structure of the PerfLoc Prize Competition organized by the US National Institute of Standards and Technology (NIST). The Competition consisted of collecting an extensive repository of smartphone data, releasing the data to researchers across the world to develop smartphone indoor localization algorithms, allowing them to evaluate the performance of their algorithms using a NIST web portal, and rigorous, live testing of the Android apps implementing the best algorithms at NIST. The paper presents detailed performance analysis of the algorithms developed by the top 10 participants as well as the Android indoor localization app that won the first prize in PerfLoc. It also provides a comparison of PerfLoc with other ongoing, annual indoor localization competitions.

Traffic lights (TLs) are used to control traffic at road intersections. Typically, the TL control mechanism on the road operates according to a fixed periodic schedule to change the light (red/yellow/green). A different schedule may be employed at late night or early morning hours. Such fixed light control does not react to changing traffic conditions, and is unaware of (unresponsive to) congestion. In this paper, we propose a novel framework dynamic TL control (DTLC) at road intersections. DTLC relies on a sensor network to collect traffic data and includes novel protocols to handle congestion and facilitate more efficient traffic flow. The proposed low-overhead algorithms are practical to employ in live traffic flow scenarios. Through analysis and simulations, we demonstrate the benefits of DTLC in optimizing traffic flow metrics, such as traffic throughput, vehicle waiting time, and waiting line length. This paper is a step toward employing smart TLs, which are part of the future envisioned "Smart City."

This paper describes a major effort to collect smartphone data useful for indoor localization. Data has been collected with four Android phones according to numerous scenarios in each of four large buildings. The data includes time-stamped traces of various environmental, position, and motion sensors available on a smartphone, Wi-Fi and cellular signal strengths, and GPS fixes, whenever available. Quantitative evidence is presented to validate the collected data and attest to its quality. This unique, extensive data repository is made available to the R&D community through the PerfLoc web portal to facilitate development of smartphone indoor localization apps and to enable performance evaluation of such apps according to the ISO/IEC 18305 international standard in the near future.

Traffic control at road intersections is based on traffic lights (TLs). The control mechanism typically used for traffic lights operates based on a periodic schedule to change the light (red/yellow/green). In many cases, a different schedule is used in late night/early morning hours. This fixed control mechanism does not adequately account for changing traffic conditions, and is unaware of/unresponsive to congestion. In this work, we propose a framework for dynamic traffic light control at intersections. The framework relies on a simple sensor network to collect traffic data and includes novel protocols for traffic flow control to handle congestion and facilitate flow. We show that our proposed algorithms have low overhead and are practical to employ in live traffic flow scenarios. Through extensive simulations, we demonstrate the benefits of our framework in optimizing traffic flow metrics, such as traffic throughput, average vehicle waiting time, and vehicle waiting line length.

Factory and process automation systems are increasingly employing information and communications technologies to facilitate data sharing and analysis in integrated control operations. Wireless connections provide flexible access to a variety of field instruments and reduce network installation and maintenance costs. This serves as an incentive for the adoption of industrial wireless networks based on standards such as the WirelessHART and ISA100.11a in factory control systems. However, process control systems vary greatly and have diverse wireless networking requirements in different applications. These requirements include deterministic transmissions in the shared wireless bandwidth, low-cost operation, long-term durability, and high reliability in the harsh radio propagation environment. It is an open question whether a generic wireless technology would meet the requirements of industrial process control. In this paper, we propose a novel simulation framework for performance evaluation of wireless networks in factory and process automation systems. We select a typical process control plant model, specifically the Tennessee Eastman Challenge (TE) Model, and define the interfaces between the process simulator and the wireless network simulator. We develop a model of the protocol stack of the WirelessHART specification in the OMNET++ simulation engine as a typical industrial wireless network. We present simulation results that validate the prospect of using WirelessHART in the TE plant, and we evaluate the impact of various wireless network configurations on the plant operation. Given its modular design, the proposed simulation framework can be easily used to evaluate the performance of other industrial wireless networks in conjunction with a variety of process control systems.

Mandated by the 2006 United States Miner Act, reliable two-way communications in mines has drawn the interest of network engineers in recent years. Critical to the design of these systems is an accurate channel propagation model. Given the elementary geometry seen in most tunnels, models that approximate them as a rectangular waveguide have been developed. These models are extremely accurate in vehicular tunnels because - since the tunnel is typically cast from concrete - the cross section is uniform throughout and the surface roughness is negligible. Mines, however, do not conform to these two conditions. In this paper, we extend the waveguide model to tunnels with varying cross section and measurable surface roughness. The effectiveness of the proposed model is validated through in-house field measurements collected in a vehicular tunnel and in a coal mine. We show that while the original model performs well in the former, it falters in the latter. The extended model, however, predicts reliably in the mine as well.

Network coding has been proved as an effective way to enhance the throughput of the multihop wireless ad hoc networks in both unicast and multicast traffics. However, in a random network topology with non-coding-aware routing protocols, the performance enhancement may be limited because the packet routing scheme does not take advantage of the possibility of network coding. In this paper, we propose a Backbone ROuting with Network Coding (BRONC) scheme over a multihop wireless network, which combines the benefits of both backbone routing and network coding techniques. With backbone-based routing, all packets are forced to be transmitted over a constructed backbone. Because of the characteristics of bi-directional traffic flow and pre-specified routes in backbone routing, the possibility of coding packets at intermediate nodes can be substantially increased, and thus the benefit of network coding is fully exploited. Simulation results show that BRONC improves the coding opportunity significantly, and it outperforms the existing opportunistic coding schemes in terms of throughput, packet delivery ratio and transmission overhead.

Network coding is a promising technology that can effectively improve the efficiency and capacity of multihop wireless networks by exploiting the broadcast nature of the wireless medium. However, current packet routing schemes do not take advantage of the network coding, and the benefits of network coding have not been fully utilized. To improve the performance gain of network coding, in this paper, we apply network coding over a wireless backbone and investigate the performance of this approach from a theoretical perspective. Our analysis shows that, compared to network coding over ad hoc networks with traditional routing schemes, network coding over the backbone structure exhibits significant advantages. This is because all packets are transmitted over the constructed backbone with pre-specified routes, and consequently the opportunity for coding packets at intermediate nodes can be substantially improved. To further enhance the performance, we also present an optimized link scheduling protocol for network coding over a wireless backbone. The performance results show that with proposed approach, the coding gain can achieve the theoretical bound in some scenarios.

This paper describes a wireless mesh network testbed for research in rapid deployment and auto-configuration of mesh nodes. Motivated by the needs of first responders and military personnel arriving to an incident area, we developed and tested an automated deployment algorithm that indicates when a mesh node needs to be deployed as the coverage area grows. Conventional radios can experience severe coverage limitations inside structures such as hi-rise buildings, subterranean buildings, caves, and underground mines. The approach examined here is to deploy wireless relays that extend coverage through multihop communication using a deployment algorithm that employs physical layer measurements. A flexible platform based on IEEE 802.11 radios has been implemented and tested in a subterranean laboratory complex where conventional public safety radios have no coverage. Applications tested include two-way voice, data, and location information. This paper describes the testbed, presents experimental results, and recommends areas for further study and development in rapidly-deployable multihop networks.

In this paper, we propose a backbone construction scheme over heterogeneous ad hoc networks, where the network nodes have different characteristics such as communication capacity, processing power and energy resource. Most of the wireless backbone construction techniques focus on minimizing the number of backbone nodes. In our proposed scheme, we not only minimize the backbone size, but also take the characteristics of nodes into account when building a backbone. In the scheme, the more capable nodes have higher probability to serve as backbone nodes and provide a wireless highway over which end-to-end communication can take place. The proposed scheme includes two major steps, which can be solved by formulating as a Dominating Set (DS) problem and a Steiner Tree Problem with Minimum Number of Sterner Points (STP-MSP) respectively. We focus on the two subproblems and present a number of polynomial time approximation algorithms. Simulation results show that the proposed scheme achieves higher average backbone node performance, while has approximately the same backbone size comparing with other schemes.

Vehicular ad hoc networking is an important component of Intelligent Transportation Systems. The main benefit of vehicular ad hoc network (VANET) communication is seen in active safety systems that increase passenger safety by exchanging warning messages between vehicles. Other applications and private services are also permitted in order to lower the cost and to encourage VANET deployment and adoption. Dedicated Short Range Communications (DSRC) is a key enabling technology for VANET applications and services. There are many challenges that must be addressed before VANETs can be successfully deployed. Among these challenges is designing of security mechanisms to secure VANETs against abuse, and designing of efficient medium access control (MAC) protocols so that safety related and other application messages can be timely and reliably disseminated through VANETs. In this paper we propose a secure MAC protocol for VANETs, with different message priorities for different types of applications to access DSRC channels. Our simulations and analysis show that the proposed MAC protocol can provide secure communications while guarantee the reliability and latency requirements of safety related DSRC applications for VANETs.

Vehicular ad hoc networks (VANETs) are important components of Intelligent Transportation Systems. The main benefit of VANET communication is seen in active safety systems that increase passenger safety by exchanging warning messages between vehicles. Other applications and private services are also permitted in order to lower the cost and to encourage VANET deployment and adoption. Security is one of the major challenges that must be addressed before VANETs can be successfully deployed. Another crucial issue is support of different applications and services in VANETs. In this paper we propose a secure and application-oriented network design framework for VANETs. We consider both security requirements of the communications and other requirements of potential VANET applications and services. The proposed framework consists of two basic components: an application-aware control scheme and a unified routing scheme. We also study a number of key enabling technologies that are important to a practical VANET. Our study provides a guideline for the design of a more secure and practical VANET.

When the range of single-hop wireless communication is limited by distance or harsh radio propagation conditions, relays can be used to extend the communication range through multihop relaying. This paper targets the need in certain scenarios for rapid deployment of these relays when little or nothing is known in advance about a given environment and its propagation characteristics. Applications include first responders entering a large building during an emergency, search and rescue robots maneuvering a disaster sight, and coal miners working underground. The common element motivatingthis work is the need to maintain communications in an environment where single-hop communication is typically inadequate. This paper investigates the feasibility of the automated deployment of a multihop network. A deployment procedure is proposed that employs real-time link measurements and takes into account the physical layer characteristics of a mobile multipath fading environment and the radio in use. A prototype system is implemented based on 900 MHz TinyOS motes supporting low-speed data applications including text messaging, sensor data and RFID-assisted localization. Results of deployments in a hi-rise office building are presented.

This paper presents the empirical results and analysis of a link variability study for an indoor, stationary 802.11 network subject to external interference. The objective is to characterize the relationships between the packet loss rate on a link and the transmitter-receiver distance, the SNR as reported by the 802.11 card, and time. Experimental results confirm that distance is not predictive of link reliability. Furthermore, attempting to estimate the packet loss rate by counting missing packets can lead to large estimation errors and latency for estimation parameters of practical interest. We find, however, that the SNR measurements reported by today's 802.11 cards can, under certain circumstances, be reliably predictive of the packet loss rate. These results suggest that SNR-based link assessment can provide for more rapid and accurate measurement of link reliability, but they point to the need for improved SNR measurements and models to adequately predict link quality in environments with significant external interference

This paper describes an approach for relaying in multihop networks that adapts to the time-varying channel and exploits spatial diversity to mitigate multipath fading. Ignored in some performance analyses, fading arises from multipath propagation and causes fluctuations in the signal strength in mo- bile networks, adversely affecting communication performance. Our approach uses limited cross-layer interactions between the physical, link and routing layers to provide adaptivity to both large and small-scale channel effects and to achieve spatial diversity gain without the use of multiple antennas. The routing layer uses long-term measurements of link quality in the form of the average signal-to-noise ratio (SNR) to opportunistically select next-hop relays on a hop-by-hop basis. Small-scale variations are overcome at the MAC layer through efficient multicast polling of multiple next-hop candidate relays prior to data transmission. A performance analysis for networks employing geographic routing and an IEEE 802.11-based MAC (i) demonstrates significant improvements in network capacity and end-to-end delay achieved with these channel-adaptive techniques in Rayleigh and Ricean fading environments, (ii) shows that most of the small-scale diversity gain is obtained through the use of only two next-hop relay choices, and (iii) assesses the practical limit of the short- term adaptive component in terms of maximum node velocity.

A multisector antenna based access point (AP) network architecture with omni-directional mobile nodes (MNs) is proposed. We investigate the effect of hidden nodes and power control on the system performance, and compare the performance of the proposed network architecture with that of an omni-directional AP/MNs network architecture in terms of throughput, delay, probability of collision, and power consumption per throughput. The data throughput in the multisector antenna based AP network architecture with power control (PC) is approximately 5.65 and 6.59 times higher than for the conventional omni-directional AP network architecture with PC and without PC, respectively, at an aggregate offered load of 1.0 (2.0 Mbps). The peak data throughput of the proposed network architecture with PC is approximately 1.9 (3.8 Mbps) for an aggregate offered load of about 2.1 (4.2 Mbps). Furthermore, the power consumption of MNs per throughput in the proposed network architecture with PC is only 1.02% and 2.25% of those of the omni-directional AP network architecture without PC and with PC, respectively, at an aggregate offered load of 1.0 (2.0 Mbps). The proposed network architecture with PC yields a significant improvement in system throughput and power saving in comparison with the conventional omni-directional AP/MNs network architecture.

This paper proposes a fast handoff scheme for a mobile station using packet data service through the CDMA 2000 network. When a mobile station hands off to a cell in which the Packet Data Serving Node (PDSN) is different from that of the previous cell, the CDMA 2000 system performs two stages of handoff in series, a cellular handoff followed by a Mobile IP (MIP) handoff. We propose a fast handoff scheme that reduces signaling latency and user data loss during a handoff. This improvement is achieved by having the source PDSN buffer the user data packets during the handoff procedure and the MIP handoff started concurrently with the cellular. The proposed fast handoff scheme is compatible with the existing protocols, and the two proposed modifications are transparent to mobile stations with the standard Mobile IP and Mobile IP route optimization protocols.

This paper presents a technique for deblurring noisy images. It includes two processing blocks, one for denoising and another for blind image restoration. The denoising step is based on the theories of singular value decomposition and compression-based filtering. The deblurring step is based on a double-regularization technique. Experimental results show that the combination of these techniques is quite effective in restoring severely blurred and noise-corrupted images, without prior knowledge of either the noise or image characteristics.

This paper presents a new criterion for near-lossless image compression and compares it with the more familiar maximum pixel error criterion in terms of compression performance and coded image subjective quality. In this new framework we compress an image in such a way that at each pixel the total error between the original and the coded images over a W/spl times/W window around the pixel does not exceed /spl epsiv/ in magnitude. The new criterion's main advantage is that it preserves image brightness and color. The compression scheme used in this work is similar to a trellis-searched scheme proposed by Ke and Marcellin (1995) in that our scheme is also a predictive, context-based scheme. However, the search for all optimal paths, representing a set of reconstruction values for an image row that satisfies the error criterion and yields the minimum bit rate, has to be done in a planar directed graph instead of a trellis. We show that this framework is also applicable to a joint image filtering and compression scenario. We present simulation results showing the performance of the new error criterion and compare it with the maximum pixel error criterion.

An N-level scalar quantization system for continuous alphabet i.i.d. sources with a pre- and post-filter as suggested by Popat and Zeger (see IEEE Trans. Commun., vol.40, no.11, p.1670, 1992) is considered. The idea is that the pre-filter changes the distribution of the source to approximately Gaussian, which is then quantized by a Lloyd-Max (1960, 1982) quantizer for Gaussian random variables. For many sources, the overall system outperforms one that directly quantizes the sources. We propose an iterative algorithm for designing the optimum filters, to minimize the overall mean squared error between the input and output of the quantization system. It is found experimentally that the design algorithm always converges very rapidly to a solution where the optimum pre- and post-filters are all pass filters. We prove the convergence of the design algorithm for the N=2 case, and conjecture that convergence to the same solution always holds for any N.

This paper presents a near-lossless image compression system where the coded image is within some prespecified maximum error of the original image at each and every pixel. The system is predictive and codes the image one row at a time. The encoder uses the Viterbi algorithm to choose among all admissible reproductions for the given image row the one that can be described with the fewest number of bits. In this paper we present a version of the system which employs run-length and Huffman coding to describe the reproductions for an image row. In addition, the system uses context modeling to further reduce the bit rate. Experimental results are presented showing the performance of the system on the large set of images provided by the ISO/IEC ITC Standards Committee.

A subband decomposition using wavelet filters has become an effective basis for image compression. The use of a ladder structure for the subband filtering provides a fast implementation and allows the system to be useful at video rates. A system is proposed that provides good quality video for moderate motion, roughly common intermediate format-f 0-t (CIF-) sized images at bit rates under 500 kb/s, and for teleconferencing scenes at bit rates from 180 kb/s to below 128 kb/s (basic rate ISDN). The system uses subband coding, a modified version of H.261, and entropy-constrained quantization to achieve the desired bit rate and image quality.

It is shown that the generalized BFOS algorithm is not optimal when it is used to design fixed-rate pruned tree-structured vector quantizers (PTSVQ). A simple modification is made in the algorithm which makes it optimal. However, experimental results show little difference between the rate-distortion curves generated with the original algorithm and the one proposed in the present paper. An asymptotic analysis is presented which shows how the two algorithms prune the TSVQ and explains why their results are so similar. The analysis also shows that in designing fixed-rate variable-depth TSVQs one can get as good a rate-distortion performance with a greedy TSVQ growing algorithm as with the optimal pruning of a large tree.>

The paper presents several algorithms for designing fixed- and variable-depth decision trees for searching vector quantizer (VQ) codebooks. Two applications of such are explored. First, given a source vector, a tree can be used to find the closest codevector in the VQ codebook with many fewer arithmetic operations than the usual "full search." This decrease in complexity comes at the expense of an increase in auxiliary table storage. Second, the tree can be used as the first stage of fine-coarse vector quantization, which yields further savings in complexity at the cost of somewhat more storage and a small increase in distortion. The design methods involve incrementally growing trees with a variety of node splitting criteria and, subsequently, optimally pruning trees on the basis of performance functionals such as distortion, storage, and computational complexity. The pruning is done with the BFOS algorithm, which optimally trades one performance functional with another, and with an extension of the BFOS algorithm wherein one performance measure is traded with a combination of two others. The results of applying these methods to i.i.d. Gaussian, Gauss-Markov, and sampled speech sources at encoding rates of one and two bits per source sample demonstrate the tradeoffs achievable amongst time (complexity), memory (storage), and distortion.>

A combination of trellis coded quantization (TCQ) and its vector alphabet generalization TCVQ is used to code the coefficients resulting from a biorthogonal wavelet transform in an image. TCVQ is a vector trellis coder with fixed rate, very good rate-distortion performance, and yet reasonable implementation complexity. The experimental results show that the Lena image can be coded by this coding system at the rate of 0.265 bpp to yield a peak signal-to-noise ratio (PSNR) of about 29 dB. This PSNR is about 3 dB larger than that obtained by a coding system of the same rate that uses VQ to obtain the wavelet transform coefficients. Naturally, the performance of the TCQ/TCVQ wavelet transform coder can be improved if entropy-coded TCQ and TCVQ coders are employed.>

A vector generalization of trellis coded quantization (TCQ), called trellis coded vector quantization (TCVQ), and experimental results showing its performance for an i.i.d. Gaussian source are presented. For a given rate, TCVQ yields a lower distortion that TCQ at the cost of an increase in implementation complexity. In addition, TCVQ allows fractional rates, which TCQ does not.>

The authors describe a multilayer connection control architecture for broadband communications. A graph framework is introduced to describe network layers of network design, path configurations, dynamic call routing, burst switching, and asynchronous transfer mode (ATM) cell switching. These hierarchical layers of switching are performed at decreasing time scales, respectively. Switching at the higher layer is performed to reduce blocking at the next smaller time scale. A layered notion of equivalent bandwidth for satisfying layered grade-of-service parameters is introduced for making connections at these time scales. The authors then focus on the path configuration layer. Two path setup methods, namely, physical and virtual path setup, are described. Mathematical programs minimizing path bandwidth usage subject to meeting grade-of-service requirements are formulated for both methods. The relative merits of these methods are compared. In one example, physical path setup is shown to require roughly 50% more bandwidth than virtual path setup.>

The performance of a lattice-based fast vector quantization (VQ) method, which yields rate-distortion performance to that of an optimal VQ, is analyzed. The method, which is a special case of fine-coarse vector quantization (FCVQ), uses the cascade of a fine lattice quantizer and a coarse optimal VQ to encode a given source vector. The second stage is implemented in the form of a lookup table, which needs to be stored at the encoder. The arithmetic complexity of this method is essentially that of lattice VQ. Its distortion can be made arbitrarily close to that of an optimal VQ, provided sufficient storage for the table is available. It is shown that the distortion of lattice-based FCVQ is larger than that of full search quantization by an amount that decreases as the square of the diameter of the lattice cells, and it provides exact formulas for the asymptotic constant of proportionality in terms of the properties of the lattice, coarse codebook, and source density. It is shown that the excess distortion asymptotically equals that of the fine quantizer. Simulation results indicate how small the lattice cells must be in order for the asymptotic formulas to be applicable.>

Several incremental algorithms are presented for designing fixed length decision trees for searching the codebook of a vector quantizer (VQ). These trees are then used as the basis for a two-stage VQ, wherein the first stage is a high-rate, structured VQ with a fast quantization algorithm and the second stage is a low-rate optimal VQ. The mean square error and complexity of the resulting two-stage VQs are presented for i.i.d. Gaussian and speech sources, and are compared with both TSVQ and previous tree based two-stage VQ designs.>