Audio annotation is a crucial, yet time-consuming process, mostly due to the effort it takes human listeners to label sound data. We present an automated system for audio annotation that leverages a camera, a microphone and an off-the-shelf computer vision model to detect objects on a video track and label the corresponding audio track. The labeled audio data is then used to train a deep learning model, which enables a microphone based system to detect objects correctly without the need for a camera. To prove the concept, we developed a simple traffic monitoring system, taking advantage of the YOLOv8 model to annotate the audio data automatically and developing a ResNet-12 model to match road sounds to vehicle types, e.g., cars and motorcycles. Our automated solution achieves a 26x improvement in labeling speed compared to the manual approach. The resulting audio model for vehicle sounds achieves 0.91 precision and 0.9 recall. The proposed system is also able to count vehicles with less than 5% error. The generic methodology for automated audio annotation using off-the-shelf computer vision models extends naturally to a broad range of use cases for example in surveillance, wildlife protection or industrial monitoring.

Current state-of-the-art in speed measurement technologies includes magnetic inductive loop detectors, Doppler radar, infrared sensors, and laser sensors. Many of these systems rely on intrusive methods that require intricate installation and maintenance processes that hinder traffic while leading to high acquisition and maintenance costs. Speed measurement from monocular videos appears as an alternative in this context. However, most of these systems present as a drawback the requirement of camera calibration - a fundamental step to convert the vehicle speed from pixels per frame to some real-world unit of measurement (e.g. km/h). Considering that, we propose a speed measurement system based on monocular cameras with no need for calibration. Our proposed system was trained from a synthetic data set containing 12,290 instances of vehicle speeds. We extract the motion information of the vehicles that pass in a specific region of the image by using dense optical flow, using it as input to a regressor based on a customized VGG-16 network. The performance of our method was evaluated over the Luvizon's data set, which contains real-world scenarios with 7,766 vehicle speeds, ground-truthed by a high precision system based on properly calibrated and approved inductive loop detectors. Our proposed system was able to measure 85.4% of the speed instances within an error range of [-3, + 2] km/h, which is ideally defined by the regulatory authorities in several countries. Our proposed system does not rely on any distance measurements in the real world as input, eliminating the need for camera calibration.

Smart cities aim to improve the citizens' quality of life by leveraging information about urban scale processes extracted from heterogeneous data sources collected on citywide deployments. The Internet-of-Things (IoT) is, thus, the enabler of smart city technologies at urban scale. In this paper, we present PortoLivingLab, a multisource sensing infrastructure that leverages IoT technology to achieve city-scale sensing of four phenomena: weather, environment, public transport, and people flows. To sense these processes on a city scale, we deployed a vehicular network with over 600 vehicles and 19 static environmental sensors. We also developed an easily reconfigurable crowdsensing platform and carried out several crowdsensing campaigns with more than 600 participants. The data is collected in a common backend and stored using similar spatio-temporal data models to simplify sharing and joint analysis for the characterization of urban dynamics. We describe the architecture and composing elements of PortoLivingLab, highlighting the IoT technologies, and challenges faced. We present several proof-of-concept use cases (e.g., passenger flows from WiFi connections) that provide new insights into different components of an evolving and moving city. Finally, we lay out the future lines of work that will strive for finding hidden phenomena by leveraging data from the three complementary platforms.

Private communication detection (PCD) is a traffic-analysis technique whereby an ordinary user of a communication network exploits side channels in end-point devices to observe the busy/idle activity status of targeted users. Correlations of users' activity status allows collection of communication records that reveal private relationships. PCD techniques have been demonstrated for a number of communication technologies, such as Wi-Fi and VoIP, and their effectiveness shown even when the communication network is private; i.e., it provides content confidentiality, flow anonymity, and user pseudonymity. In this paper, we present a mathematical model of PCD that captures the activity status of two targets in a private VoIP network, including the probing process of an attacker that aims to breach their communication anonymity. Using this model, we a) develop fundamental bounds on PCD accuracy; b) measure the anonymity leakage in terms of the amount of call record information obtained in an attack; and c) provide performance guarantees and compare the efficacy of different PCD countermeasures, such as resource randomization and use of firewalls.

Vehicular networks have the potential to improve road safety using Dedicated Short Range Communications (DSRC) technology, but substantial investment in roadside units (RSUs) is required. DSRC can be simultaneously used for safety and non-safety applications. If local governments share RSUs deployed for safety or smart streetlights with other kinds of service providers, then the respective costs can also be shared, thereby reducing costs for the government. We estimate that government could save about one fifth the nationwide cost of safety RSUs in the U.S. if they are shared with Internet service providers. We also estimate an increase in social welfare from sharing. The prices that maximize government savings and social welfare may differ. However, we find that maximizing government savings results in near-optimal social welfare.

We address the problem of localization in vehicular ad hoc networks. Our goal is to leverage vehicle communications and smartphone sensors to improve the overall localization performance. Assuming vehicles are equipped with the IEEE 802.11p wireless interfaces, we employ a two-stage Bayesian filter to track the vehicle's position: an unscented Kalman filter for heading estimation using smartphone inertial sensors, and a particle filter that fuses vehicle-to-vehicle signal strength measurements received from mobile anchors whose positions are uncertain, with velocity, GPS position, and map information. Our model leads to a robust localization system and is able to provide useful position information even in the absence of GPS data. We evaluate the algorithm performance using real-world measurements collected from four communicating vehicles in an urban scenario, and considering different combinations of location information sources.

Vehicular mesh networks can be used to carry Internet data traffic for mobile users. We use data from a real vehicular network that is operating in Portugal to estimate the relationship between network throughput and offered load of Internet traffic, quantity of vehicles, quantity of infrastructure and the use of Request-to-Send/Clear-to- Send (RTS/CTS) handshaking. We show that achievable throughput remains close to its maximum even for high levels of offered load per vehicle or high density of vehicles, so congestion control mechanisms in mesh networks can effectively prevent throughput from collapsing as these factors increase over time. This achievable throughput can be increased with the deployment of additional roadside infrastructure that serves as a gateway to the Internet, although the throughput gain per gateway decreases as more are added. Deploying these gateways is cost-effective, i.e. economic benefits of the resulting throughput exceed costs of infrastructure, when vehicle density is sufficiently high. We also find that use of RTS/CTS decreases achievable throughput in this scenario.

We examine the side-channel information leakage in first-come-first-serve (FCFS) packet schedulers. In this setup, an attacker aims to learn the packet arrival pattern of a private user that shares a FCFS packet scheduler with him, using the queuing delay information of his own packets. Under an information-theoretic metric for information leakage, we identify the optimal non-adaptive strategy for a given average probe rate of the attacker and report upto 1000% increase in information leakage compared to the attack strategy analyzed in the literature with the same average probe rate. The search for optimal strategies is reduced to linear programming, implying that the discovery of such strategies is in the domain of a real-world attacker.

A large-scale urban sensing platform, composed of multiple Data Collection Units (DCUs) equipped with sensor hardware scattered accross the city, allows pervasive monitoring of environmental parameters. Gathering sensor data from a number of disparate locations at a backend server can be supported by delay-tolerant services provided by existing vehicular networks. Our real-world sensing platform takes advantage of an existing vehicular network with more than 400 vehicles equipped with On-Board Units (OBUs). A purposely-developed implementation of a delay tolerant service is installed in all elements involved in the communication flow, from DCUs to the backend server. In this demo, we showcase the full end-to-end data flow with the actual equipment being used in our real-world deployment. Data produced at a DCU is collected by an OBU installed in a vehicle and delivered to a Road-Side Unit (RSU), which then forwards the data to the backend server.

Network-coded cooperative communication (NC-CC) has been proposed and evaluated as a powerful technology that can provide a better quality of service in the next-generation wireless systems, e.g., D2D communications. Previous contributions have focused on performance evaluation of NC-CC scenarios rather than searching for optimal policies that can minimize the total cost of reliable packet transmission. We break from this trend by initially analyzing the optimal design of NC-CC for a wireless network with one source, two receivers, and half-duplex erasure channels. The problem is modeled as a special case of Markov decision process (MDP), which is called stochastic shortest path (SSP), and is solved for any field size, arbitrary number of packets, and arbitrary erasure probabilities of the channels. The proposed MDP solution results in an optimal transmission policy per time slot, and we use it to design near-optimal heuristics for packet transmission in a network of one source and N ≥ 2 receivers. We also present numerical results that illustrate the performance of the proposed heuristics under a variety of scenarios. To complete our analysis, our heuristics are implemented in Aalborg University's Raspberry Pi testbed and compared with random linear network coding (RLNC) broadcast in terms of completion time, total number of required transmissions, and percentage of delivered generations. Our measurements show that enabling cooperation only among pairs of devices can decrease the completion time by up to 4.75 times, while delivering 100% of the 10000 generations transmitted, as compared to RLNC broadcast delivering only 88% of them in our tests.

The articles in this special issue focus on fundamental approaches to network coding in wireless communications systems. Wireless communication network providers are constantly striving for more efficient and reliable service provision to billions of customers across the globe. As such, there exist great opportunities in the research and development of advanced network coding techniques in emerging wireless communication systems and applications for further improving network capacity and performance. Arguably, bandwidth-hungry applications,such as multimedia, are to benefit the most from the many advantages that wireless network coding can offer, particularly higher throughputs, lower delays, and better scalability. Wireless network coding has a great potential to be applied at the physical layer, harnessing inherent interference in the wireless channel for more spectral efficiency. It can significantly enhance the performance of relay-based, device-to-device, and cooperative communication techniques in current and future wireless systems.

The experience of daily stress among bus drivers has shown to affect physical and psychological health, and can impact driving behavior and overall road safety. Although previous research consistently supports these findings, little attention has been dedicated to the design of a stress detection method able to synchronize physiological and psychological stress responses of public bus drivers in their day-to-day routine work. To overcome this limitation, we propose a mobile sensing approach to detect georeferenced stress responses and facilitate memory recall of the stressful situations. Data were collected among public bus drivers in the city of Porto, Portugal (145 h, 36 bus drivers, +2300 km), and results supported the validation of our approach among this population and allowed us to determine specific stressor categories within certain areas of the city. Furthermore, data collected throughout the city allowed us to produce a citywide “stress map” that can be used for spotting areas in need of local authority intervention. The enriching findings suggest that our system can be a promising tool to support applied occupational health interventions for public bus drivers and guide authorities' interventions to improve these aspects in “future” cities.

The design of the communication protocols in wireless sensor networks (WSNs) often neglects several key characteristics of the sensor's hardware, while assuming that the number of transmitted bits is the dominating factor behind the system's energy consumption. A closer look at the hardware specifications of common sensors reveals, however, that other equally important culprits exist, such as the reception and processing energy. Hence, there is a need for a more complete hardware abstraction of a sensor node to reduce effectively the total energy consumption of the network by designing energy-efficient protocols that use such an abstraction, as well as mechanisms to optimize a communication protocol in terms of energy consumption. The problem is modeled for different feedback-based techniques, where sensors are connected to a base station, either directly or through relays. We show that for four example platforms, the use of relays may decrease up to 4.5 times the total energy consumption when the protocol and the hardware are carefully matched. We conclude that: 1) the energy budget for a communication protocol varies significantly on different sensor platforms; and 2) the protocols can be judiciously adapted to the underlying hardware. The results are cross-validated using real-life measurements.

There are now 1 billion vehicles in the world waiting to be connected to the Internet. At the same time, vehicular communication technologies have matured to a point in which massive deployment is both possible and feasible. One option for deployment is to wait for car manufacturers to embed DSRC/WAVE interfaces inside their latest models. However, since only 9% of the world's fleet is new every year, this would result in a time span of up to 20 years until 90% of the vehicles are finally connected. Another option is to rely entirely on cellular communications, such as GPRS, EDGE, 3G and LTE. This cellular only approach is impractical due to the capital expenses required for telecom operators to meet the demands of the impending tsunami of mobile data (expected to grow 1800% until 2016). Clearly, there is need for a low-cost wireless networking solution that can be placed in any vehicle and offers reliable connectivity, improved quality of experience and higher safety for drivers and passengers. This solution, we will argue, is vehicular mesh networking.

Consumer demand for high-quality video over wireless networks is increasing at fast pace. The resulting technical challenges are particularly stringent in crowded spaces, where the density of users far exceeds the ability to deploy cellular base stations or WiFi infrastructure in a cost effective way. To address this problem, we present a reliable and scalable live streaming solution based on wireless multicast with real-time network coding. At the core of our approach is a timely delivery scheme that uses a minimum amount of feedback from the receivers to generate coded repair packets that are simultaneously useful to a large number of users. Our protocol, which we implemented and tested in a real-world wireless testbed, differs from traditional wireless unicast and multicast schemes in that (a) the feedback messages of the users are treated jointly and (b) the repair mechanism considers both the playout deadlines of individual packets and the list of packets already received by the clients. In comparison with a standard video approach that sends an MPEG-2 encoded stream over 802.11 unicast links, our solution offers real-time guarantees for all users commensurate with the link quality and an 11x improvement in terms of bandwidth usage. A commercial version of the proposed solution shows a strong increase in the number of clients that can access video streams simultaneously over a single WiFi hotspot.

In this paper, we investigate the optimal design of cooperative network-coded strategies for a three-node wireless network with time-varying half-duplex erasure channels. To this end, we formulate the problem of minimizing the total cost of transmitting M packets from source to two receivers as a Markov decision process (MDP). The actions of the MDP model include the source and the type of transmission to be used in a given time slot given perfect knowledge of the system state. The cost of packet transmission is defined such that it can incorporate the difference between broadcast and unicast transmissions, e.g., in terms of the rate of packet transmission or the energy consumption. A comprehensive analysis of the MDP solution is carried out under different network conditions to extract optimal rules of packet transmission. Inspired by the extracted rules, we propose two near-optimal heuristics that are suitable for practical systems. We use two wireless channel models to analyze the performance of the proposed heuristics in practical wireless networks, namely; an infrastructure-to-vehicle communication in a highway scenario considering Rayleigh fading; and real packet loss measurements for WiFi using Aalborg University's Raspberry Pi testbed. We compare our results with random linear network coding broadcasting schemes showing that our heuristics can provide up to 2 × gains in completion time and up to 4 × gains in terms of reliably serviced data packets.

Vehicle-to-Vehicle (V2V) communication is a core technology for enabling safety and non-safety applications in next generation intelligent transportation systems. Due to relatively low heights of the antennas, V2V communication is often influenced by topographic features, man-made structures, and other vehicles located between the communicating vehicles. On highways, it was shown experimentally that vehicles can obstruct the line of sight (LOS) communication up to 50 percent of the time; furthermore, a single obstructing vehicle can reduce the power at the receiver by more than 20 dB. Based on both experimental measurements and simulations performed using a validated channel model, we show that the elevated position of antennas on tall vehicles improves communication performance. Tall vehicles can significantly increase the effective communication range, with an improvement of up to 50 percent in certain scenarios. Using these findings, we propose a new V2V relaying scheme called tall vehicle relaying (TVR) that takes advantage of better channel characteristics provided by tall vehicles. TVR distinguishes between tall and short vehicles and, where appropriate, chooses tall vehicles as next hop relays. We investigate TVR's system-level performance through a combination of link-level experiments and system-level simulations and show that it outperforms existing techniques.

Many wireless applications require a propagation model that describes the attenuation of the transmitted signal as a function of the distance between devices. Such channel models are derived commonly from signal strength measurements, and assume that the true distances between wireless terminals are known. In practice, however, the true distances may be unavailable or difficult to obtain, for instance in mobile scenarios or in the absence of line-of-sight. These conditions typically occur in forested environments, urban areas, etc. This paper addresses the problem of path loss model parameter estimation in presence of erroneous distance measurements, such as the ones derived from the GPS positions. We provide a model for the uncertainties, and study the impact of distance errors on the estimation of a log-distance channel model. Our main conclusion is that the path loss model can be estimated with a reasonable accuracy from unreliable distances, provided that the measurements are taken at distances beyond a few standard deviations of the GPS positioning error. In case the maximum communication range does not allow such large distances, we provide a method to correct the erroneous channel model. Real-world measurements are used in order to validate our approach.

The execution of an agent's complex activities, comprising sequences of simpler actions, sometimes leads to the clash of conflicting functions that must be optimized. These functions represent satisfaction, short-term as well as long-term objectives, costs and individual preferences. The way that these functions are weighted is usually unknown even to the decision maker. But if we were able to understand the individual motivations and compare such motivations among individuals, then we would be able to actively change the environment so as to increase satisfaction and/or improve performance. In this work, we approach the problem of providing highlevel and intelligible descriptions of the motivations of an agent, based on observations of such an agent during the fulfillment of a series of complex activities (called sequential decisions in our work). A novel algorithm for the analysis of observational records is proposed. We also present a methodology that allows researchers to converge towards a summary description of an agent's behaviors, through the minimization of an error measure between the current description and the observed behaviors. This work was validated using not only a synthetic dataset representing the motivations of a passenger in a public transportation network, but also real taxi drivers' behaviors from their trips in an urban network. Our results show that our method is not only useful, but also performs much better than the previous methods, in terms of accuracy, efficiency and scalability.

We consider the performance of network coding for a wireless cooperative network in which a source wants to transmit M data packets to two receivers. We assume that receivers can share their received packets with each other or simply wait to receive the packets from the source. The problem of finding an optimum packet transmission policy that minimizes the completion time in such a network is solved by modeling the problem as a Markov Decision Process (MDP). Our analysis is useful for a series of network coding and forwarding schemes with or without feedback. Our results show that the optimal network coding solution in terms of completion time, outperforms broadcasting with network coding by a factor of 2.13 and outperforms forwarding mechanisms by a factor of 6.1. Beyond computing the optimal completion time, we identify the critical decision policies derived from the MDP solution.

We present a collision-free jammer selection policy for enhanced wireless secrecy. Jammers, selected from the neighbors of a source, are friendly in the sense that they are willing to help the source to transmit securely by causing interference/collisions to possible eavesdroppers. The proposed jammer selection policy results in the selection of the largest number of jammers that do not cause collisions among themselves. This enables jammers to assist the source to transmit securely by causing interference to eavesdroppers, while sending their own traffic into the network.

We propose a probabilistic key distribution protocol for vehicular network that alleviates the burden of traditional public-key infrastructures. Roadside units act as trusted nodes and are used for secret-sharing among vehicles in their vicinity. Secure communication is immediately possible between these vehicles with high probability. Our performance evaluation, which uses both analysis and simulation, shows that high reliability and short dissemination time can be achieved with low complexity.

Recent accomplishments in physical-layer security research have shown that channel coding for secrecy can be effectively combined with security at other layers, such as cryptography at the application layer, in order to provide a significant security enhancement to communication systems. The goal of this previous work was to inhibit the passive eavesdropper in the wiretap channel model by encoding the ciphertext using nonsystematic low-density parity-check (LDPC) codes prior to transmission and by exploiting the advantage of feedback for legitimate parties. The net result was propagation of a single packet erasure to the detriment of the entire message. The security enhancement was characterized assuming statistically independent packet erasure channels (PECs) for the legitimate receiver and the eavesdropper. In this paper, we go beyond these results by addressing correlated erasure events across the two channels in a wiretap feedback framework. The intuitive notion that high correlation across channels reduces secrecy is shown through the complete characterization of the correlated channel scenario. Furthermore, it is shown that security improvements are still achievable in the face of positive correlation by means of judicious physical-layer design, even when the eavesdropper has a better channel than the legitimate receiver.

We present a jamming protocol for secrecy-enhanced wireless networks in which otherwise silent devices are selected as jammers to cause interference to potential eavesdroppers. This cooperative protocol includes several jammer selection policies that lead to different levels of secrecy-energy tradeoffs. Our results show that there is some advantage over selecting well-connected jammers and there is a need for a minimum number of jammers for the energy cost of jamming to payoff.

We present an improved decoding algorithm for joint turbo decoding and physical-layer network coding. Instead of decoding the individual (binary) messages separately at the relay, the proposed algorithm, from the superimposed faded signals, yields an XOR estimate of the sent messages. Moreover, we introduce a softening of the XOR values to improve the overall performance. Simulation results show that this simple idea yields gains up to 4.5 dB in a Rayleigh fading channel model when compared to a similar scheme.

ABSTRACT The vision towards the Network of the Future cannot be separated from the fact that today's networks, and networking services are subject to sophisticated and very effective attacks. When these attacks first appeared, spoofing and distributed denial‐of‐service attacks were treated as apocalypse for networking. Now, they are considered moderate damage, whereas more sophisticated and inconspicuous attacks, such as botnets activities, might have greater and far reaching impact. As the Internet is expanding to mobile phones and ‘smart dust’ and as its social coverage is liberalized towards the realization of ubiquitous computing (with communication), the concerns on security and privacy have become deeper and the problems more challenging than ever. Re‐designing the Internet as the Network of the Future is self‐motivating for researchers, and security and privacy cannot be provided again as separate, external, add‐on, solutions. In this paper, we discuss the security and privacy challenges of the Network of the Future and try to delimit the solutions space on the basis of emerging techniques. We also review methods that help the quantification of security and privacy in an effort to provide a more systematic and quantitative treatment of the area in the future. Copyright © 2011 John Wiley & Sons, Ltd.

We focus on the problem of secure distributed storage over multiple untrusted clouds or networks. Our main contribution is a low complexity scheme that relies on erasure coding techniques for achieving prescribed levels of confidentiality and reliability. Using matrices that have no singular square submatrices, we subject the original data to a linear transformation. The resulting coded symbols are then stored in different networks. This scheme allows users with access to a threshold number of networks to reconstruct perfectly the original data, while ensuring that eavesdroppers with access to any number of networks smaller than this threshold are unable to decode any of the original symbols. This holds even if the attackers are able to guess some of the missing symbols. We further quantify the achievable level of security, and analyze the complexity of the proposed scheme.

The ability to exchange secret information is critical to many commercial, governmental, and military networks. Information-theoretic security-widely accepted as the strictest notion of security-relies on channel coding techniques that exploit the inherent randomness of the propagation channels to strengthen the security of digital communications systems. Motivated by recent developments in the field, we aim to characterize the fundamental secrecy limits of wireless networks. The paper is comprised of two separate parts. In Part I, we define the intrinsically secure communications graph (iS-graph), a random graph which describes the connections that can be securely established over a large-scale network. We provide conclusive results for the local connectivity of the Poisson iS-graph, in terms of node degrees and isolation probabilities. We show how the secure connectivity of the network varies with the wireless propagation effects, the secrecy rate threshold of each link, and the noise powers of legitimate nodes and eavesdroppers. We then propose sectorized transmission and eavesdropper neutralization as viable strategies for improving the secure connectivity. Our results help clarify how the spatial density of eavesdroppers can compromise the intrinsic security of wireless networks. In Part II of the paper, we study the achievable secrecy rates and the effect of eavesdropper collusion.

In Part I of this paper, we introduced the intrinsically secure communications graph (iS-graph)-a random graph which describes the connections that can be established with strong secrecy over a large-scale network, in the presence of eavesdroppers. We focused on the local connectivity of the iS-graph, and proposed techniques to improve it. In this second part, we characterize the maximum secrecy rate (MSR) that can be achieved between a node and its neighbors. We then consider the scenario where the eavesdroppers are allowed to collude, i.e., exchange and combine information. We quantify exactly how eavesdropper collusion degrades the secrecy properties of the network, in comparison to a noncolluding scenario. Our analysis helps clarify how the presence of eavesdroppers can jeopardize the success of wireless physical-layer security.

A modular system architecture based on separate compression and network coding is known to be theoretically suboptimal for relevant classes of sensor networks with correlated sources. Motivated by this observation, we present a feasible solution for joint source and network coding with distortion constraints. By choosing encoders that are simple scalar index assignments, we are able to move the complexity to the destination decoder. Given the network topology and the correlation structure of the data, our algorithms solve the problem of finding encoder and decoder instances that minimize the mean square error of every sample. A proof-of-concept and the complexity analysis of the proposed algorithms underline the effectiveness of our factor graph approach. The presented schemes are shown to yield low-distortion estimates of the collected data even in scenarios where a modular solution would fail.

A thorough understanding of the communications channel between vehicles is essential for realistic modeling of Vehicular Ad Hoc Networks (VANETs) and the development of related technology and applications. The impact of vehicles as obstacles on vehicle-to-vehicle (V2V) communication has been largely neglected in VANET research, especially in simulations. Useful models accounting for vehicles as obstacles must satisfy a number of requirements, most notably accurate positioning, realistic mobility patterns, realistic propagation characteristics, and manageable complexity. We present a model that satisfies all of these requirements. Vehicles are modeled as physical obstacles affecting the V2V communication. The proposed model accounts for vehicles as three-dimensional obstacles and takes into account their impact on the LOS obstruction, received signal power, and the packet reception rate. We utilize two real world highway datasets collected via stereoscopic aerial photography to test our proposed model, and we confirm the importance of modeling the effects of obstructing vehicles through experimental measurements. Our results show considerable obstruction of LOS due to vehicles. By obstructing the LOS, vehicles induce significant attenuation and packet loss. The algorithm behind the proposed model allows for computationally efficient implementation in VANET simulators. It is also shown that by modeling the vehicles as obstacles, significant realism can be added to existing simulators with clear implications on the design of upper layer protocols.

We propose a secure scheme for wireless network coding, called the algebraic watchdog. By enabling nodes to detect malicious behaviors probabilistically and use overheard messages to police their downstream neighbors locally, the algebraic watchdog delivers a secure global self-checking network. Unlike traditional Byzantine detection protocols which are receiver-based, this protocol gives the senders an active role in checking the node downstream. The key idea is inspired by Marti et al.'s watchdog-pathrater, which attempts to detect and mitigate the effects of routing misbehavior. We first focus on a two-hop network. We present a graphical model to understand the inference process nodes execute to police their downstream neighbors; as well as to compute, analyze, and approximate the probabilities of misdetection and false detection. We also present an algebraic analysis of the performance using an hypothesis testing framework that provides exact formulae for probabilities of false detection and misdetection. We then extend the algebraic watchdog to a more general network setting, and propose a protocol in which we can establish trust in coded systems in a distributed manner. We develop a graphical model to detect the presence of an adversarial node downstream within a general multi-hop network. The structure of the graphical model (a trellis) lends itself to well-known algorithms (e.g. the Viterbi algorithm) which can compute the probabilities of misdetection and false detection. We show that as long as the min-cut is not dominated by the adversaries, upstream nodes can monitor downstream neighbors and allow reliable communication with certain probability. Finally, we present simulation results that support our analysis.

A fundamental understanding of the delay behavior of network coding is key towards its successful application in real-time applications with strict message deadlines. Previous contributions focused mostly on the average decoding delay, which although useful in various scenarios of interest is not sufficient for providing worst-case delay guarantees. To overcome this challenge, we investigate the entire delay distribution of random linear network coding for any field size and arbitrary number of encoded symbols (or generation size). By introducing a Markov chain model we are able to obtain a complete solution for the erasure broadcast channel with two receivers. A comparison with Automatic Repeat reQuest (ARQ) with perfect feedback, round robin scheduling and a class of fountain codes reveals that network coding on GF(24) offers the best delay performance for two receivers. We also conclude that GF(2) induces a heavy tail in the delay distribution, which implies that network coding based on XOR operations although simple to implement bears a relevant cost in terms of worst-case delay. For the case of three receivers, which is mathematically challenging, we propose a brute-force methodology that gives the delay distribution of network coding for small generations and field size up to GF(24).

The theory of network coding promises significant benefits in network performance, especially in lossy networks and in multicast and multipath scenarios. To realize these benefits in practice, we need to understand how coding across packets interacts with the acknowledgment (ACK)-based flow control mechanism that forms a central part of today's Internet protocols such as transmission control protocol (TCP). Current approaches such as rateless codes and batch-based coding are not compatible with TCP's retransmission and sliding-window mechanisms. In this paper, we propose a new mechanism called TCP/NC that incorporates network coding into TCP with only minor changes to the protocol stack, thereby allowing incremental deployment. In our scheme, the source transmits random linear combinations of packets currently in the congestion window. At the heart of our scheme is a new interpretation of ACKs-the sink acknowledges every degree of freedom (i.e., a linear combination that reveals one unit of new information) even if it does not reveal an original packet immediately. Thus, our new TCP ACK rule takes into account the network coding operations in the lower layer and enables a TCP-compatible sliding-window approach to network coding. Coding essentially masks losses from the congestion control algorithm and allows TCP/NC to react smoothly to losses, resulting in a novel and effective approach for congestion control over lossy networks such as wireless networks. An important feature of our solution is that it allows intermediate nodes to perform re-encoding of packets, which is known to provide significant throughput gains in lossy networks and multicast scenarios. Simulations show that our scheme, with or without re-encoding inside the network, achieves much higher throughput compared to TCP over lossy wireless links. We present a real-world implementation of this protocol that addresses the practical aspects of incorporating network coding and decoding with TCP's window management mechanism. We work with TCP-Reno, which is a widespread and practical variant of TCP. Our implementation significantly advances the goal of designing a deployable, general, TCP-compatible protocol that provides the benefits of network coding.

In this paper, we discuss the ability of channel codes to enhance cryptographic secrecy. Toward that end, we present the secrecy metric of degrees of freedom in an attacker's knowledge of the cryptogram, which is similar to equivocation. Using this notion of secrecy, we show how a specific practical channel coding system can be used to hide information about the ciphertext, thus increasing the difficulty of cryptographic attacks. The system setup is the wiretap channel model where transmitted data traverse through independent packet erasure channels (PECs) with public feedback for authenticated automatic repeat-request (ARQ). The code design relies on puncturing nonsystematic low-density parity-check (LDPC) codes with the intent of inflicting an eavesdropper with stopping sets in the decoder. The design amplifies errors when stopping sets occur such that a receiver must guess all the channel-erased bits correctly to avoid an error rate of one half in the ciphertext. We extend previous results on the coding scheme by giving design criteria that reduce the effectiveness of a maximum-likelihood (ML) attack to that of a message-passing (MP) attack. We further extend security analysis to models with multiple receivers and collaborative attackers. Cryptographic security is even enhanced by the system when eavesdroppers have better channel quality than legitimate receivers.

This paper presents a coding scheme for the Gaussian wiretap channel based on low-density parity-check (LDPC) codes. The messages are transmitted over punctured bits to hide data from eavesdroppers. The proposed coding scheme is asymptotically effective in the sense that it yields a bit-error rate (BER) very close to 0.5 for an eavesdropper whose signal-to-noise ratio (SNR) is lower than the threshold SNRE, even if the eavesdropper has the ability to use a bitwise maximum a posteriori (MAP) decoder. Such codes also achieve high reliability for the friendly parties provided they have an SNR above a second threshold SNRB. It is shown how asymptotically optimized LDPC codes are designed with differential evolution where the goal is to achieve high reliability between friendly parties while keeping the security gap SNRB/SNREas small as possible to protect against passive eavesdroppers. The proposed coding scheme is encodable in linear time, applicable at finite block lengths, and can be combined with existing cryptographic schemes to deliver improved data security by taking advantage of the stochastic nature of many communication channels.

The 31 papers in this special issue focus on using the physical layer for securing the next generation of communication systems.

Inspired by recent results on information-theoretic security, we consider the transmission of confidential messages over wireless networks, in which the legitimate communication partners are aided by friendly jammers. We characterize the security level of a confined region in a quasi-static fading environment by computing the probability of secrecy outage in connection with two new measures of physical-layer security: the jamming coverage and the jamming efficiency. Our analysis for various jamming strategies based on different levels of channel state information provides insight into the design of optimal jamming configurations and shows that a single jammer is not sufficient to maximize both figures of merit simultaneously. Moreover, a single jammer requires full channel state information to provide security gains in the vicinity of the legitimate receiver.

Signal interference and packet collisions are typically viewed as negative factors that hinder wireless communication networks. When security is the primary concern, signal interference may actually be very helpful. Starting with a stochastic network model, we are able to show that packet collisions caused by jamming nodes can indeed be used effectively to attain new levels of secrecy in multiterminal wireless environments. To this effect, we propose a practical jamming protocol that uses the well-known request-to-send/clear-to-send (RTS/CTS) handshake of the IEEE 802.11 standard as a signaling scheme. Various jammer selection strategies are investigated depending on the position of source, destination, and jamming nodes. The goal is to cause as much interference as possible to eavesdroppers that are located in unknown positions, while limiting the interference observed by the legitimate receiver. To evaluate the performance of each strategy, we introduce and compute a measure for the secure throughput. Our results show that jamming can increase the levels of secrecy significantly albeit at a substantial cost in terms of energy efficiency.

We consider distributed storage over two untrusted networks, whereby coding is used as a means to achieve a prescribed level of confidentiality. The key idea is to exploit the algebraic structure of the Vandermonde matrix to mix the input blocks, before they are stored in different locations. The proposed scheme ensures that eavesdroppers with access to only one of the networks are unable to decode any symbol even if they are capable of guessing some of the missing blocks. Information-theoretic techniques allow us to quantify the achievable level of confidentiality. Moreover, the proposed approach is shown to offer low complexity and optimal rate.

Information-theoretic security--widely accepted as the strictest notion of security--relies on channel coding techniques that exploit the inherent randomness of propagation channels to strengthen the security of communications systems. Within this paradigm, we explore strategies to improve secure connectivity in a wireless network. We first consider the intrinsically secure communications graph (iS-graph), a convenient representation of the links that can be established with information-theoretic security on a large-scale network. We then propose and characterize two techniques--sectorized transmission and eavesdropper neutralization--which are shown to dramatically enhance the connectivity of the iS-graph.

We analyze the role of jamming as a means to increase the security of wireless systems. Specifically, we characterize the impact of cooperative/friendly jamming on the secrecy outage probability of a quasi-static wiretap fading channel. We introduce jamming coverage and jamming efficiency as security metrics, and evaluate the performance of three different jamming strategies that rely on various levels of channel state information. The analysis provides insight for the design of optimal jamming configurations and indicates that one jammer is not enough to maximize both metrics simultaneously.

Network coding allows nodes in a network to combine different packets using linear operations. In most instances, the encoding coefficients are chosen randomly and placed in the packet header. The ability to correct errors and erasures is critical, because a single malicious packet injected by a misbehaving node or the deletion of a single packet can corrupt multiple packets and jeopardize the entire information flow. Building on Rotter and Kschischang's theoretical work on subspace network codes, we propose a practical network coding protocol with in-built resilience against faults and active attacks. Also included is a low-complexity extended code construction for high-rate subspace Reed-Solomon like codes. The code maintains the distance properties that are key for error and erasure correction. Performance results show that throughput gains can be achieved with lower complexity and smaller field sizes.

Shannon defined channel capacity as the highest rate at which there exists a sequence of codes of block length n such that the error probability goes to zero as n goes to infinity. In this definition, it is implicit that the block length, which can be viewed as the number of available channel uses, is unlimited. This is not the case when the transmission power must be concentrated on a single transmission, most notably in military scenarios with adversarial conditions or delay-tolerant networks with random short encounters. A natural question arises: how much information can we transmit in a single use of the channel? We give a precise characterization of the one-shot capacity of discrete channels, defined as the maximum number of bits that can be transmitted in a single use of a channel with an error probability that does not exceed a prescribed value. This capacity definition is shown to be useful and significantly different from the zero-error problem statement.

Physical-layer security based on wiretap codes can be used to complement cryptographic applications at higher layers of the protocol stack. We assume a passive eavesdropper that has access to noise-corrupted codewords with erasures that are statistically independent to those of the legitimate communication partners. Our goal is to minimize the information leaked to the eavesdropper. In this paper we present a low-complexity coding scheme for channels with feedback, which employs extensive interleaving of carefully punctured LDPC codewords. The key idea is to ensure that every transmitted packet is crucial for successful decoding. This is achieved by ensuring that stopping-set bit combinations for coded blocks are distributed among different packets and by enforcing that retransmission requests be restricted to the friendly parties. A probabilistic analysis reveals that an eavesdropper who uses a message-passing decoding algorithm will experience catastrophic decoding failure with high probability. This encoder thus provides physical-layer secrecy which is both independent from, and complementary of, the cryptographic layer. The proposed scheme works even when an eavesdropper has a better channel than the legitimate receiver.

In our previous work (`An Algebraic Watchdog for Wireless Network Coding'), we proposed a new scheme in which nodes can detect malicious behaviors probabilistically, police their downstream neighbors locally using overheard messages; thus, provide a secure global self-checking network. As the first building block of such a system, we focused on a two-hop network, and presented a graphical model to understand the inference process by which nodes police their downstream neighbors and to compute the probabilities of misdetection and false detection. In this paper, we extend the Algebraic Watchdog to a more general network setting, and propose a protocol in which we can establish trust in coded systems in a distributed manner. We develop a graphical model to detect the presence of an adversarial node downstream within a general two-hop network. The structure of the graphical model (a trellis) lends itself to well-known algorithms, such as Viterbi algorithm, that can compute the probabilities of misdetection and false detection. Using this as a building block, we generalize our scheme to multi-hop networks. We show analytically that as long as the min-cut is not dominated by the Byzantine adversaries, upstream nodes can monitor downstream neighbors and allow reliable communication with certain probability. Finally, we present preliminary simulation results that support our analysis.

Random linear network coding can be used in peerto- peer networks to increase the efficiency of content distribution and distributed storage. However, these systems are particularly susceptible to Byzantine attacks. We quantify the impact of Byzantine attacks on the coded system by evaluating the probability that a receiver node fails to correctly recover a file. We show that even for a small probability of attack, the system fails with overwhelming probability. We then propose a novel signature scheme that allows packet-level Byzantine detection. This scheme allows one-hop containment of the contamination, and saves bandwidth by allowing nodes to detect and drop the contaminated packets. We compare the net cost of our signature scheme with various other Byzantine schemes, and show that when the probability of Byzantine attacks is high, our scheme is the most bandwidth efficient.

Emerging practical schemes indicate that algebraic mixing of different packets by means of random linear network coding can increase the throughput and robustness of streaming services over wireless networks. However, concerns with the security of wireless video, in particular when only some of the users are entitled to the highest quality, have uncovered the need for a network coding scheme capable of ensuring different levels of confidentiality under stringent complexity requirements. We show that the triple goal of hierarchical fidelity levels, robustness against wireless packet loss and efficient security can be achieved by exploiting the algebraic structure of network coding. The key idea is to limit the encryption operations to a critical set of network coding coefficients in combination with multi-resolution video coding. Our contributions include an information-theoretic security analysis of the proposed scheme, a basic system architecture for hierarchical wireless video with network coding and simulation results.

This paper presents a coding scheme for the Gaussian wiretap channel based on low-density parity-check (LDPC) codes. The messages are transmitted over punctured bits to hide data from eavesdroppers. It is shown that this method is asymptotically effective in the sense that it yields a BER very close to 0.5 for an eavesdropper whose SNR is lower than the threshold SNRE, even if the eavesdropper has the ability to use a bitwise MAP decoder. Such codes also achieve high reliability for the friendly parties provided they have an SNR above a second threshold SNRB. It is shown how asymptotically optimized LDPC codes can be designed with differential evolution where the goal is to achieve high reliability between friendly parties and security against a passive eavesdropper while keeping the security gap SNRB/SNREas small as possible. The proposed coding scheme is applicable at finite block lengths and can be combined with existing cryptographic schemes to deliver improved data security by taking advantage of the stochastic nature of many communication channels.

This paper studies probabilistic information dissemination in random networks. Consider the following scenario: A node intends to deliver a message to all other nodes in the network ("flooding"). It first transmits the message to all its neighboring nodes. Each node forwards a received message with some network-wide probability pf. A natural question arises: which forwarding probability pfshould each node use such that a flooded message is obtained by all nodes with high probability? In other words, what is the minimum pfto achieve a high global outreach probability? We first present a generic approach to estimate the probability for achieving global outreach. This approach is then employed in Erdos Renyi random graphs, where we derive an upper and a lower bound for the global outreach probability for given random network and flooding parameters. The analysis is complemented with simulation results showing the tightness of both bounds. As a final result, we take a system design perspective to show a number of parameter vectors leading to global outreach.

Motivated by streaming applications with stringent delay constraints, we consider the design of online network coding algorithms with timely delivery guarantees. Assuming that the sender is providing the same data to multiple receivers over independent packet erasure channels, we focus on the case of perfect feedback and heterogeneous erasure probabilities. Based on a general analytical framework for evaluating the decoding delay, we show that existing ARQ schemes fail to ensure that receivers with weak channels are able to recover from packet losses within reasonable time. To overcome this problem, we re-define the encoding rules in order to break the chains of linear combinations that cannot be decoded after one of the packets is lost. Our results show that sending uncoded packets at key times ensures that all the receivers are able to meet specific delay requirements with very high probability.

We propose a mechanism that incorporates network coding into TCP with only minor changes to the protocol stack, thereby allowing incremental deployment. In our scheme, the source transmits random linear combinations of packets currently in the congestion window. At the heart of our scheme is a new interpretation of ACKs - the sink acknowledges every degree of freedom (i.e., a linear combination that reveals one unit of new information) even if it does not reveal an original packet immediately. Such ACKs enable a TCP-compatible sliding-window approach to network coding. Our scheme has the nice property that packet losses are essentially masked from the congestion control algorithm. Our algorithm therefore reacts to packet drops in a smooth manner, resulting in a novel and effective approach for congestion control over networks involving lossy links such as wireless links. Our scheme also allows intermediate nodes to perform re-encoding of the data packets. Our simulations show that our algorithm, with or without re-encoding inside the network, achieves much higher throughput compared to TCP over lossy wireless links. We also establish the soundness and fairness properties of our algorithm. Finally, we present queuing analysis for the case of intermediate node re-encoding.

In this paper, we propose a scheme, called the algebraic watchdog for wireless network coding, in which nodes can detect malicious behaviors probabilistically, police their downstream neighbors locally using overheard messages, and, thus, provide a secure global self-checking network. Unlike traditional Byzantine detection protocols which are receiver-based, this protocol gives the senders an active role in checking the node downstream. This work is inspired by Marti et al.'s watchdog-pathrater, which attempts to detect and mitigate the effects of routing misbehavior. As the first building block of a such system, we focus on a two-hop network. We present a graphical model to understand the inference process nodes execute to police their downstream neighbors; as well as to compute, analyze, and approximate the probabilities of misdetection and false detection. In addition, we present an algebraic analysis of the performance using an hypothesis testing framework, that provides exact formulae for probabilities of false detection and misdetection.

We consider the impact of Byzantine attackers on peer-to-peer topologies for distributed storage using network coding. First, the problem is formulated as one of data flow in random evolving graphs, in which a data source and a data collector are connected to data keepers who may behave in a Byzantine fashion. We then derive analytical results for the probability of carrying out a successful distributed denial of service attack (that is, collecting contaminated information from the network), as well as the expected number of contaminated nodes at each timestep. Our results show that, even for a small number of Byzantine attackers in the network, the probability of collecting contaminated information is overwhelming, and that the dissemination of information by peers as opposed to a selected subset of nodes in the network increases the probability of contaminated information collection.

We consider the fundamental security limits of stochastic wireless networks in the presence of colluding eavesdroppers. By establishing a direct connection with the single-input multiple-output (SIMO) Gaussian wiretap channel, we are able to provide a complete characterization of the secrecy capacity for the case in which the eavesdroppers are scattered according to a spatial Poisson process. Our analysis, which includes the probabilities of existence and outage of secrecy capacity, helps clarify how the spatial density of eavesdroppers can jeopardize the success of wireless physical-layer security based on information-theoretic principles.

Emerging practical schemes indicate that algebraic mixing of different packets by means of random linear network coding can increase the throughput and robustness of streaming services over wireless networks. However, concerns with the security of streaming multimedia, in particular when only a subset of the users in the network is entitled to the highest quality, have uncovered the need for a network coding scheme capable of ensuring different levels of confidentiality under stringent complexity requirements. We consider schemes which exploit the algebraic structure of network coding to achieve the dual goal of hierarchical fidelity levels and efficient security. The key idea is to limit the encryption operations to the encoding vector, in combination with multi-resolution multimedia coding.

Motivated by the recent surge in vehicular ad-hoc network (VANET) research and the promise of high-impact applications such as safety, navigation and infotainment services, we consider the impact of mobility mis-modeling on the design and development of this class of distributed systems. Focusing on urban environments, we use a state-of-the-art car traffic simulator to extract some of the key connectivity metrics relevant for the design of a vehicle-to-vehicle traffic information system. We compare such metrics against those obtained from popular mobility models, such as the random waypoint model and the Manhattan mobility model. Our results reveal striking differences in the connectivity profile of the network, thus casting some doubt on the adequacy of simple mobility models for the development of future VANET protocols.

Focusing on large-scale vehicular ad-hoc networks (VANETs), we consider the interplay between single-hop channel models and large-scale network connectivity. Building on a realistic urban traffic simulator, we progressively increase the sophistication of the wireless link while evaluating the resulting connectivity profiles. Our results show that large-scale VANET connectivity, whose understanding is paramount towards the development of protocols and applications for this class of networks, is equally influenced by the choice of model and by the fine-tuning of its key parameters. Analyzing the distributions of both node degree and the duration of connection, we conclude that (a) as far as large-scale node degree behavior is concerned, a complex shadow fading environment is well approximated by a simpler and more tractable unit-disk model and, (b) unit-disk models allow longer connections than other models.

We consider the distributed source coding problem in which correlated data picked up by scattered sensors has to be encoded separately and transmitted to a common receiver, subject to a rate-distortion constraint. Although near-to-optimal solutions based on Turbo and LDPC codes exist for this problem, in most cases the proposed techniques do not scale to networks of hundreds of sensors. We present a scalable solution based on the following key elements: (a) distortion-optimized index assignments for low-complexity distributed quantization, (b) source-optimized hierarchical clustering based on the Kullback-Leibler distance and (c) sum-product decoding on specific factor graphs exploiting the correlation of the data.

Under the emerging network coding paradigm, intermediate nodes in the network are allowed not only to store and forward packets but also to process and mix different data flows. We propose a low-complexity cryptographic scheme that exploits the inherent security provided by random linear network coding and offers the advantage of reduced overhead in comparison to traditional end-to-end encryption of the entire data. Confidentiality is achieved by protecting (or "locking") the source coefficients required to decode the encoded data, without preventing intermediate nodes from running their standard network coding operations. Our scheme can be easily combined with existing techniques that counter active attacks.

Contemporary communication systems are based on modular architectures, where the role of the physical layer is essentially confined to error correction, whereas information security is typically dealt with at the upper layers of the protocol stack. We consider a security architecture that does exactly the opposite: information sequences are first converted to longer channel codewords which are then encrypted using a classical stream cipher. Although this approach requires longer encryption sequences, our analysis shows that the natural randomness of the noisy communication channel can be used effectively against known-plaintext attacks. We also address practical implementation issues in physical-layer encryption and discuss their impact on the system architecture and on the security performance.

Network coding is a highly efficient data dissemination mechanism for wireless networks. Since network coded information can only be recovered after delivering a sufficient number of coded packets, the resulting decoding delay can become problematic for delay-sensitive applications such as real-time media streaming. Motivated by this observation, we consider several algorithms that minimize the decoding delay and analyze their performance by means of simulation. The algorithms differ both in the required information about the state of the neighborspsila buffers and in the way this knowledge is used to decide which packets to combine through coding operations. Our results show that a greedy algorithm, whose encodings maximize the number of nodes at which a coded packet is immediately decodable significantly outperforms existing network coding protocols.

We consider the problem of secret key distribution in a sensor network with multiple scattered sensor nodes and a mobile device that can be used to bootstrap the network. Our main contribution is a set of secure protocols that rely on simple network coding operations to provide a robust and low-complexity solution for sharing secret keys among sensor nodes, including pairwise keys, cluster keys, key revocation, and mobile node authentication. Despite its role as a key enabler for this approach, the mobile node only has access to an encrypted version of the keys, providing information-theoretic security with respect to attacks focused on the mobile node. Our results include performance evaluation in terms of security metrics and a detailed analysis of resource utilization. The basic scheme was implemented and tested in a real-life sensor network testbed. We deem this class of network coding protocols to be particularly well suited for highly constrained dynamic systems such as wireless sensor networks.

This paper considers the transmission of confidential data over wireless channels. Based on an information-theoretic formulation of the problem, in which two legitimates partners communicate over a quasi-static fading channel and an eavesdropper observes their transmissions through a second independent quasi-static fading channel, the important role of fading is characterized in terms of average secure communication rates and outage probability. Based on the insights from this analysis, a practical secure communication protocol is developed, which uses a four-step procedure to ensure wireless information-theoretic security: (i) common randomness via opportunistic transmission, (ii) message reconciliation, (iii) common key generation via privacy amplification, and (iv) message protection with a secret key. A reconciliation procedure based on multilevel coding and optimized low-density parity-check (LDPC) codes is introduced, which allows to achieve communication rates close to the fundamental security limits in several relevant instances. Finally, a set of metrics for assessing average secure key generation rates is established, and it is shown that the protocol is effective in secure key renewal—even in the presence of imperfect channel state information.

We prove that the commitment capacity of the power-constrained Gaussian channel, i.e., the optimal rate at which this channel can be used for implementing commitment schemes, is infinite.

We consider the level of information security provided by random linear network coding in network scenarios in which all nodes comply with the communication protocols yet are assumed to be potential eavesdroppers (i.e. "nice but curious"). For this setup, which differs from wiretapping scenarios considered previously, we develop a natural algebraic security criterion, and prove several of its key properties. A preliminary analysis of the impact of network topology on the overall network coding security, in particular for complete directed acyclic graphs, is also included.

Motivated by the design of low-complexity distributed quantizers and iterative decoding algorithms that leverage the correlation in the data picked up by a large-scale sensor network, we address the problem of finding correlation preserving clusters. To construct a factor graph describing the statistical dependencies between sensor measurements, we develop a hierarchical clustering algorithm that minimizes the Kullback Leibler distance between known and approximated source statistics. Finally, we show how the clustering result can be exploited in the design of index assignments for distributed quantization and source-channel decoders of manageable complexity.

We consider bit commitment over additive white Gaussian noise channels. Our main result is that the maximum rate at which this class of channels can be used for implementing commitment protocols (the commitment capacity) is provably infinite, even under an average power constraint.

We consider the transmission of confidential data over wireless channels with multiple communicating parties. Based on an information-theoretic problem formulation in which two legitimate partners communicate over a quasi-static fading channel and an eavesdropper observes their transmissions through another independent quasi-static fading channel, we define the secrecy capacity in terms of outage probability and provide a complete characterization of the maximum transmission rate at which the eavesdropper is unable to decode any information. In sharp contrast with known results for Gaussian wiretap channels (without feedback), our contribution shows that in the presence of fading information-theoretic security is achievable even when the eavesdropper has a better average signal-to-noise ratio (SNR) than the legitimate receiver - fading thus turns out to be a friend and not a foe.

Recent results from statistical physics show that large classes of complex networks, both man-made and of natural origin, are characterized by high clustering properties yet strikingly short path lengths between pairs of nodes. Breaking with the traditional approach to these so called small worlds that relies mainly on graph parameters directly related to connectivity, we investigate the capacity of these networks from the perspective of network information flow. Our contribution includes upper and lower bounds for the capacity of standard and navigable small-world models based on added shortcuts, and the somewhat surprising result, that, with high probability, random rewiring does not alter the capacity of a small-world network.

We consider the problem of jointly decoding the correlated data picked up and transmitted by the nodes of a large-scale sensor network. Assuming that each sensor node uses a very simple encoder (a scalar quantizer and a modulator), we focus on decoding algorithms that exploit the correlation structure of the sensor data to produce the best possible estimates under the minimum mean-square error (MMSE) criterion. Our analysis shows that a standard implementation of the optimal MMSE decoder is unfeasible for large-scale sensor networks, because its complexity grows exponentially with the number of nodes in the network. Seeking a scalable alternative, we use factor graphs to obtain a simplified model for the correlation structure of the sensor data. This model allows us to use the sum-product decoding algorithm, whose complexity can be made to grow linearly with the size of the network. Considering large sensor networks with arbitrary topologies, we focus on factor trees and give an exact characterization of the decoding complexity, as well as mathematical tools for factorizing Gaussian sources and optimization algorithms for finding optimal factor trees under the Kullback-Leibler criterion.

Consider the following network communication setup, originating in a sensor networking application we refer to as the "sensor reachback" problem. We have a directed graph G=(V,E), where V={v/sub 0/v/sub 1/...v/sub n/} and E/spl sube/V/spl times/V. If (v/sub i/,v/sub j/)/spl isin/E, then node i can send messages to node j over a discrete memoryless channel (DMC) (X/sub ij/,p/sub ij/(y|x),Y/sub ij/), of capacity C/sub ij/. The channels are independent. Each node v/sub i/ gets to observe a source of information U/sub i/(i=0...M), with joint distribution p(U/sub 0/U/sub 1/...U/sub M/). Our goal is to solve an incast problem in G: nodes exchange messages with their neighbors, and after a finite number of communication rounds, one of the M+1 nodes (v/sub 0/ by convention) must have received enough information to reproduce the entire field of observations (U/sub 0/U/sub 1/...U/sub M/), with arbitrarily small probability of error. In this paper, we prove that such perfect reconstruction is possible if and only if H(U/sub s/ | U/sub S(c)/) < /spl Sigma//sub i/spl isin/S,j/spl isin/S(c)/ for all S/spl sube/{0...M},S/spl ne/O,0/spl isin/S(c). Our main finding is that in this setup, a general source/channel separation theorem holds, and that Shannon information behaves as a classical network flow, identical in nature to the flow of water in pipes. At first glance, it might seem surprising that separation holds in a fairly general network situation like the one we study. A closer look, however, reveals that the reason for this is that our model allows only for independent point-to-point channels between pairs of nodes, and not multiple-access and/or broadcast channels, for which separation is well known not to hold. This "information as flow" view provides an algorithmic interpretation for our results, among which perhaps the most important one is the optimality of implementing codes using a layered protocol stack.

Consider a directed graph, in which vertices represent sensor nodes, and edges represent a discrete memoryless channel of a given capacity over which two neighbors nodes can communicate. The channels are independent. Each node gets to observe one element of a set of discrete sources of information drawn i.i.d., according to some joint probability distribution. Our goal is to solve an incast problem in the given graph: nodes exchange messages with their neighbors, and after a finite number of communication rounds, one of the nodes (the data collector) must have received enough information to reproduce the entire set of observations, with arbitrarily small probability of error. In this paper, we give a complete characterization of the conditions on the sources and the channels under which such perfect reconstruction is possible. Close examination of our proof reveals that in this setup, Shannon information behaves as a classical flow, identical in nature to the flow of water in pipes. This "information as flow" view provides an algorithmic interpretation for our results, among which perhaps the most important one is the optimality of using a layered protocol stack

We consider the sensor reachback problem, in which a large number of sensor nodes are deployed on a field, and the goal is to reconstruct at a remote location the correlated data collected and transmitted by all the nodes. In this paper, we assume that each sensor node uses a very simple encoder (a scalar quantizer and a modulator) and focus on decoding algorithms that exploit the correlation structure of the sensor data to produce the best possible estimates under the minimum mean square error (MMSE) criterion. Our analysis shows that the optimal MMSE decoder is unfeasible for large scale sensor networks, because its complexity grows exponentially with the number of nodes in the network. Seeking a scalable alternative, we use factor graphs to obtain a simplified model for the correlation structure of the sensor data. This model allows us to use an iterative decoding algorithm whose complexity can be made to grow linearly with the size of the network.

Summary from only given as follows. In its original formulation, multiple description (MD) coding is a multiuser lossy source coding problem, in which three decoders get to observe encodings of a single source generated by two senders. In general, the rate delivered to each of the decoders is not the same and, based on this, it has been argued that MD codes would be suitable for use as joint source/channel codes in a standard point-to-point problem: low-rate decoders would be used when there is loss of data, and high-rate decoders would be used when more data is available at the receiver. We present an alternative view on the use of MD codes as joint source/channel codes. We show how a channel naturally associated with the standard joint source/channel coding problem based on MDs is a non-ergodic channel that bears little resemblance to packet channels (i.e., those for which MD codes have been proposed in practice) and we propose a simple modification to the MD setup that deals with this. We also consider the problem of designing suitable codes and we show how the associated decoding problem is essentially equivalent to the problem of sequencing DNA strands. The full paper is available from http://www.lnt.e-technik.tu-muenchen.de/mitarbeiter/barros/, http://www.ace.cornell.edu/-servetto/publications/.

We consider a scenario where a mobile user requests a high rate audio stream from the Internet via a wireless communications system. The congestion on the network and the instability of the wireless channel result in a loss of audio packets, which can impose a severe degradation on the high quality audio signal. To overcome this problem, we propose the use of multiple descriptions (MD). Our novel MD audio codec generates two complementary audio streams, which are sent in distinct packets to obtain the largest possible diversity gain. Preliminary simulation results support the flexibility and robustness of the proposed solution.