We establish that the two-dimensional ray tracing problem with thin lenses and plane mirrors is Turing-complete, thereby resolving an open question posed by Reif et al. in 1994 as to whether three-dimensional space is necessary for computational universality in optical systems. To this end, we consider the standard approximation of reflection and refraction, namely the ABCD model for paraxial optics, which describes ray propagation through lenses (refraction) via a 2 × 2 matrix, combined with the geometric reflection model for plane mirrors. In the absence of mirrors, two-dimensional ray tracing using any combination of lenses in this ABCD matrix model can be described by a single 2 × 2 matrix–vector product, where the matrix has real entries and determinant 1. Conversely, we show that any such matrix with determinant 1 can be represented as a composition of exactly three appropriately spaced thin lenses. When mirrors are combined with lenses, the ray tracing problem can be described by a flowchart using only two variables, which establishes Turing computability for rational-valued inputs, spaces and matrix entries. Building on this observation, we present a construction of ray tracing that simulates a reversible Turing machine. We begin with a restricted version of the reversible flowchart problem, in which only two variables and certain linear functions are permitted. We prove that this restricted variant is Turing-complete. We then show that such a flowchart admits a geometric realization using lenses and mirrors in our model, thereby establishing the main result: Turing-completeness of the two-dimensional ray tracing problem with ABCD-model lenses and mirrors.

We introduce and investigate the computational complexity of a novel physical problem known as the Pinball Wizard problem. It involves an idealized pinball moving through a maze composed of one-way gates (outswing doors), plane walls, parabolic walls, moving plane walls, and bumpers that cause acceleration or deceleration. Given the initial position and velocity of the pinball, the task is to decide whether it will hit a specified target point. By simulating a two-stack pushdown automaton, we show that the problem is Turing-complete - even in two-dimensional space. In our construction, each step of the automaton corresponds to a constant number of reflections. Thus, deciding the Pinball Wizard problem is at least as hard as the Halting problem. Furthermore, our construction allows bumpers to be replaced with moving walls. In this case, even a ball moving at constant speed - a so-called ray particle - can be used, demonstrating that the Ray Particle Tracing problem is also Turing-complete.

This contribution considers the problem of robust target localization using the possibly unreliable hybrid received signal strength and time-of-arrival measurements, in the Internet of Things (IoT) context. Traditional positioning approaches relying on either extra a priori error information for robustification or the computationally intensive convex programming techniques for optimization do not fit well into the IoT applications with limited computing resources. Such concerns, however, will jeopardize the straightforward applicability of many ready-made solutions to the IoT positioning services if left untreated. In this article, the problem is resolved in a different manner. We adopt here a Geman–McClure like loss function, which is much less sensitive to the biased sensor observations, in order to statistically robustify the$\ell _{2}$-sapce-based location estimator. A computationally attractive iterative message passing algorithm is then developed to conduct efficient optimization. Simulation results demonstrate the performance superiority of the proposed scheme over its competitors in various localization environments.

Elliptic target positioning from the bistatic ranges (BRs), as an emerging localization scheme, has recently gained considerable traction for its diverse applications in multistatic systems such as radar, sonar, and wireless sensor networks. This contribution extends the work of previous research on the low-rank property of the BR matrix (Xiong, “Denoising of bistatic ranges for elliptic positioning,” IEEE Geosci. Remote Sens. Lett., vol. 20, pp. 1–3, 2023, Art. no. 3500503) to the brand new use case of robust elliptic positioning in the presence of missing data. Due to the structures of the outlier-inducing errors when embodied in the BR matrix, many of the off-the-shelf low-rank matrix completion (LRMC) solutions cannot be applied. We address this challenge by formulating the problem of outlier-resistant BR matrix recovery as constrained minimization of an ℓ2,1-norm based loss function, and devising an algorithm based on alternating direction method of multipliers to efficiently solve the resultant LRMC. Simulations are conducted to demonstrate the efficacy of the developed robust elliptic positioning technique in various localization scenarios.

We consider large scale Peer-to-Peer Sensor Networks, which try to calculate and distribute the mean value of all sensor inputs. For this we design, simulate and evaluate distributed approximation algorithms which reduce the number of messages. The main difference of these algorithms is the underlying communication protocol which all use the random call model, where in discrete round model each node can call a random sensor node with uniform probability.The amount of data exchanged between sensor nodes and used in the calculation process affects the accuracy of the aggregation results leading to a trade-off situation. The key idea of our algorithms is to limit the sample size using the Finite Population Correction (FPC) method and collect the data using a distribution aggregation using Push-Pull Sampling, Pull Sampling, and Push Sampling communication protocols. It turns out that all methods show exponential improvement of Mean Squared Error (MSE) with the number of messages and rounds.

Elliptic positioning (EP) has been a topic of lively interest to localization practitioners owing to widespread adoption of the bistatic configuration in many location-enabling technologies nowadays. This letter addresses the problem of non-Gaussian error mitigation in EP, by formulating it as joint estimation of target position coordinates and a balancing parameter (BP) for the bias errors. An alternating minimization algorithm is put forward to break the original formulation down into a conventional weighted nonlinear least squares (WNLS) location estimator and a closed-form BP-update step. With its objective being properly decomposed, the WNLS subproblem is converted into the difference-of-convex programming framework, to which an efficient iterative solution based on the concave-convex procedure is applicable. Simulation results demonstrate that the proposed error-reduced EP approach can outperform a number of existing methods in terms of localization accuracy.

In this article, a direction of arrival (DOA) based estimation method is proposed for the localization of acoustic gas leakage sources indoors, with the use of a microphone array. Since the narrowband signal assumption for the uniform circular array (UCA)-MUSIC and ESPRIT methods are not applicable to the case of gas leakage sources, different approaches including the incoherent, coherent, and frequency-domain frequency-invariant beamformer ones are leveraged and optimized for the signal shape considered. The proposed method is evaluated with real-world experimental results obtained with a gas pistol resembling a leakage. The evaluation using experimental data demonstrates that coherent subspace (CSS)-MUSIC is ahead of other methods in the error metrics.

This paper proposes two efficient and easy-to-use error mitigation solutions to the problem of three-dimensional (3-D) angle-of-arrival (AOA) source localization in the mixed line-of-sight (LOS) and non-line-of-sight (NLOS) indoor environments. A weighted linear least squares estimator is derived first for the LOS AOA components in terms of the direction vectors of arrival, albeit in a sub-optimal manner. Next, data selection exploiting the sum of squared residuals is carried out to discard the error-prone NLOS connections. In so doing, the first approach is constituted and more accurate closed-form location estimates can be obtained. The second method applies a simulated annealing stochastic framework to realize the robust ℓ1-minimization criterion, which therefore falls into the methodology of statistical robustification. Computer simulations and ultrasonic onsite experiments are conducted to evaluate the performance of the two proposed methods, demonstrating their outstanding positioning results in the respective scenarios.

We revisit herein the problem of time-difference-of-arrival (TDOA) based localization under the mixed line-of-sight/non-line-of-sight propagation conditions. Adopting the strategy of statistically robustifying the non-outlier-resistantl2loss, we formulate it as the minimization of a possibly non-differentiable generalized robust cost function, which is rooted in the analog locally competitive algorithm (LCA) for sparse approximation. We then present a Lagrange programming neural network to address the optimization formulation, with the non-differentiability issues being handled by grafting thereon the LCA concept of internal state dynamics. Compared with the existing algorithms, our approach is computationally less expensive, less reliant on the use of a priori error information, and observed to be capable of producing higher localization accuracy.

Secret sharing is the well-known problem of splitting a secret into multiple shares, which are distributed to shareholders. When enough or the correct combination of shareholders work together the secret can be restored. We introduce two new types of shares to the secret sharing scheme of Shamir. Crucial shares are always needed for the reconstruction of the secret, whereas mutual redundant shares only help once in reconstructing the secret. Further, we extend the idea of crucial and redundant shares to a compartmented secret sharing scheme. The scheme, which is based on Shamir's, allows distributing the secret to different compartments, that hold shareholders themselves. In each compartment, another secret sharing scheme can be applied. Using the modifications the overall complexity of general access structures realized through compartmented secret sharing schemes can be reduced. This improves the computational complexity. Also, the number of shares can be reduced and some complex access structures can be realized with ideal amount and size of shares.

When using Online Social Networks, users often share information with different social groups. When considering the backgrounds of the groups there is often no or little intersection within the members. This means that a user who shares information often has to share it with all members of all groups. It can be problematic that the user cannot decide which group sees which information. Our approach, therefore, allows users to decide for every bit of information who can access it. Further, protected circles can be created, where users can share information within. In contrast to other approaches, shared information and circles are encrypted in order to keep them secret from the social network provider. The necessary keys can be distributed via proxies.

We introduce Cyclone codes which are rateless erasure resilient codes. They combine Pair codes with Luby Transform (LT) codes by computing a code symbol from a random set of data symbols using bitwise XOR and cyclic shift operations. The number of data symbols is chosen according to the Robust Soliton distribution. XOR and cyclic shift operations establish a unitary commutative ring if data symbols have a length of p - 1 bits, for some prime number p. We consider the graph given by code symbols combining two data symbols. If n/2 such random pairs are given for n data symbols, then a giant component appears, which can be resolved in linear time. We can extend Cyclone codes to data symbols of arbitrary even length, provided the Goldbach conjecture holds. Applying results for this giant component, it follows that Cyclone codes have the same encoding and decoding time complexity as LT codes, while the overhead is upper-bounded by those of LT codes. Simulations indicate that Cyclone codes significantly decreases the overhead of extra coding symbols.

We recently presented T-ROME a cross-layer routing protocol for wake-up receivers, along with a Markov chain based framework to model and analyze wake-up receiver based routing protocols. Using this analytical framework, we present here a modification to T-ROME that omits several messages but does not change the basic behavior of T-ROME. We analyze the performance of the modified algorithm and show that the modifications significantly reduce communication energy, time and overhead, especially in noisy environments. Furthermore we present a technique to prevent disconnected network nodes in cases where parent nodes die but preceding parent nodes are alive and in wake-up range.

The reliability of an indoor localization system is often limited by the capability of the systems of distinguishing the line-of-sight signals in environments with multipath. Besides, estimating the height of the target can be challenging due to dilution of precision (DOP) and non line of sight (NLOS) situations. However, the reflections can be used to infer information about the scenario. We present a novel approach which exploits the ground reflections to reduce the error in three dimensional localization and detect reliably the line-of-sight signals. The presented approach uses the geometry of the reflections as the model of the RANSAC method. In this model, ground reflections and line of sight signals can be found just solving a quadratic equation, which reduces the computational power required compared to other approaches. The positions are estimated using local optimization algorithms. In real experiments, the median error in the height estimation was reduced from 25 cm to 4.2 cm.

In this paper we present a novel indoor localization approach based on measuring the time of flight (TOF) of ultrasound signal reflections in human bodies and walls. This is a stand off detection approach, it does not require the user to carry any wireless device. Only a static co-located speaker and microphone pair is used. The speaker sends a chirp, which is reflected to the environment. Then, the microphone receives the chirp and the reflections, measuring the reception times. Subsequently, the position of the target is estimated by the line of sight signal and the second reflections from 2 walls. Fast normalized correlation is used to estimate the timestamps of the received signals. The human being reflections are detected by subtracting the correlated signal in consecutive intervals, exploiting the fact that even a static human being moves slightly due to his breathing. Besides, we use a polynomial approximation of the reflections to increase the accuracy of this process. The choice among the remaining peaks is done by minimizing the error of the geometrical equations involved. When the target is moving continuously, an unscented Kalman filter is used to predict the most reliable peaks and estimate the position of the target. Real measurements show the capability of the proposed approach of localizing a person standing still with a median error of 0.15m and a moving human being with a median error of 0.08m and a standard deviation of 0.13 m.

Indoor localization based on time difference of arrival (TDOA) has been recently a promising field of study. We consider the previously unsolved problem of locating a moving target receiver by using unsynchronized stationary beacons without requirement of manual calibration. Thus, the received signals and their time of arrival (TOA) have to be assigned to a beacon. Besides, in order to automatically calibrate the system it is required to estimate the time offsets between the senders, their positions and the initial receiver position. We present an approach to estimate all the variables of the scenario using the gradient descent and the Gauss-Newton method, two local optimization algorithms which use the derivative of a system of hyperbolic error equations. Besides, we present an ultrasound transmission system approach which fulfils the requirements of this scenario, being robust against multipath and estimating the reception time with high accuracy. In order to avoid interference by echoes the packet size is reduced by using two frequencies in Orthogonal Frequency Division Multiplex (OFDM). Further, the transmission system enables distinction of the beacons, as the ultrasound signals are used both for localization and for information transmission. The simulations show the local optimization algorithms are capable of estimating the positions of the beacons, receivers and offsets. They require only a rough knowledge of the sender positions. Further, real experiments show that the timestamps are measured with a standard deviation of only 1.19 μs for a SNR of 10 dB, which corresponds to standard deviation of about 0.4 mm for the distance measurement.

For evaluating RDF queries in Peer-to-Peer (P2P) based RDF data stores, the location of a RDF triple in the network must be attainable from a triple pattern in the given query. An existing strategy, used by state-of-the-art distributed RDF data stores, to fulfill this requirement is to store triples at three locations that each triple can be found by the subject, predicate, and object identifier. A major drawback of this strategy is the issue of load-balancing caused by the fact that the frequency of subject, predicate, and object occurrences in triples is not uniformly distributed. While the majority of URIs and literals occur very rarely some occur very frequently (e.g., peer responsible for 'rdf:type' is subjected to a very high storage load). In addition, this skewed RDF triples distribution among network peers also leads to an unfair query processing load distribution and long query processing time. To cope with hotspots caused by unfair data load distribution, we propose an optimized routing index scheme where triples are indexed on the combination of their subject, predicate and object components. This paper will also show how can we exploit this novel index scheme to achieve a better distribution of query processing load and faster query response time by bundling computation resources and bandwidth of peers with parallelism.

The efficiency of routing algorithms in ad-hoc networks is measured by delay, throughput, and energy. Here, we focus on routing algorithms optimizing energy consumption while providing small routing delay. For this, we exploit the sender beamforming gain in the line-of-sight path-loss model, where multiple nodes (each with a single antenna) cooperate for beamforming and the routing algorithms provide distributed self-synchronization. While direct point-to-point communication over distance d in the line-of-sight model needs transmission power Θ(d2), and multi-hop power needs power Θ(d) and delay Θ(d), we can reduce the power to Θ(√d) or Θ(log d) depending on the geometry. We present three algorithms with different trade-offs. The first algorithm is designed for grid nodes in the plane and has a point-to-point delay of Θ(log d) and overall power consumption of Θ(√d). The second algorithm for the same geometry decreases the delay to Θ(1 over ε log log d) with power Θ((√d)1+ε) for ε > 0. The third algorithm requires a three-dimensional grid network and achieves a delay of Θ(log d) and reduces the energy needed by all nodes to Θ(log d).

Localization based on the time difference of arrival (TDoA) has turned out to be a promising approach for indoor environments, especially in combination with innovative self-calibrating TDoA algorithms that eliminate the need to measure the positions of reference receivers. We consider the previously unsolved problem of locating a moving target receiver by discrete signals from stationary beacons at unknown locations. We assume that the beacons are small and inexpensive and they require no further communication, i.e. they are unsynchronized. They only emit short discrete signals at regular intervals, of which we assume that they can be distinguished. The moving target travels on an unknown trajectory, receiving signals from the beacons and calculating the TDoA of the signals. First, we discuss adaptions of two TDoA algorithms by which the senders can be located from unknown signals. Second, we propose two novel approaches based on probabilistic state estimation to enable robust localization of the mobile receiver using the discrete arrival times, once the senders have been located. The probabilistic algorithms use the particle filter and the unscented Kalman filter to estimate the position and velocity of the target, as well as the unknown synchronization offsets of the senders. We provide a motion model and a sensor model for which we take into account that the signals of the beacons are received as singles, each at a different time. We verify the feasibility and robustness of our approach in extensive simulations, where we analyze the reliability of localization and compare both algorithms.

We consider n wireless ad hoc network nodes with one antenna each and equidistantly placed on a line. The transmission power of each node is just large enough to reach its next neighbor. For this setting we show that a message can be broadcasted to all nodes in time O(log n) without increasing each node's transmission power. Our algorithm needs O(log n) messages and consumes a total energy which is only a constant factor larger than the standard approach where nodes sequentially transmit the broadcast message to their next neighbors. We obtain this by synchronizing the nodes on the fly and using MIMO (multiple input multiple output) techniques.

In this paper, we present a novel smartphone indoor localization system. The smartphone user is localized with small effort, affordable equipment and with high accuracy in indoor areas. The system uses commercially available smartphones generating high pitched acoustic chirp signals beyond the audible range. The chirp signals are received by sound receivers which identify the specific sound produced from each smartphone. The receivers are connected to a WiFi network, such that they synchronize their clocks and exchange the time differences of arrival (TDoA) of the received chirps. In this way, using an iterative multilateration algorithm, the location of the smartphones can be calculated and the receiver positions are calibrated automatically. For generating the specific sound signals from the smartphone and for user navigation an Android software application was developed. The user interface is simple and is invoked by starting the software application, which automatically connects to a server and receives an ID using the internet connection of the smartphone. Furthermore, the user is assigned specific parameters, such that several devices can be distinguished by the appearance of the chirps. The position of the user is displayed on the smartphone in context of the environment, with a map and surrounding items. In the presented work we have verified our system in a real-world scenario. We compared our trajectory of a pedestrian carrying smartphone to the reference positions. We could locate the smartphones with error margin of 30 cm. a centimeter margin of error.

Localization based on time differences of arrival (TDOA) has turned out to be a promising approach when neither receiver positions nor the positions of signal origins are known a priori. In this paper, we consider calibration-free tracking of a mobile beacon using TDOA, i.e., the positions of the receivers are not given. We propose a probabilistic formulation using a particle filter to simultaneously localize the signal beacon and the receivers. Our method is robust against measurement outliers and incorrect initialization. This is achieved through a probabilistic sensor model for TDOA data which explicitly considers the measurement uncertainty and takes into account disproportional errors caused by measurement outliers. For the reliable initialization of the particle filter, we apply an iterative optimization approach to multiple subsets of TDOA data, where the best solution is implicitly selected by appropriate weighing of the sensor model. We verify the robustness of our approach in extensive experiments in a spacious indoor environment by an ultrasound beacon moving on various trajectories. We demonstrate that our approach ensures a proper initialization of the particle filter and provides accurate position estimates for the signal beacon and the receivers even in case of measurement outliers. Compared to position references of an optical motion capture system we achieve mean position errors below 5 centimeters.

The ability of tiny embedded devices to run large feature-rich programs is typically constrained by the amount of memory installed on such devices. Furthermore, the useful operation of these devices in wireless sensor applications is limited by their battery life. This paper presents a call stack redesign targeted at an efficient use of RAM storage and CPU cycles by a Java program running on a wireless sensor mote. Without compromising the application programs, our call stack redesign saves 30% of RAM, on average, evaluated over a large number of benchmarks. On the same set of bench-marks, our design also avoids frequent RAM allocations and deallocations, resulting in average 80% fewer memory operations and 23% faster program execution. These may be critical improvements for tiny embedded devices that are equipped with small amount of RAM and limited battery life. However, our call stack redesign is equally effective for any complex multi-threaded object oriented program developed for desktop computers. We describe the redesign, measure its performance and report the resulting savings in RAM and execution time for a wide variety of programs.

We consider the multi-robot exploration problem of an unknown n x n grid graph with oriented disjoint rectangular obstacles. All robots start at a given node and have to visit all nodes of the graph. The robots are unrestricted in their computational power and storage. In the local communication model the robots can exchange any information if they meet at the same node. In the global communication model all robots share the same knowledge.

We present an analytical approach for determining the signal-to-noise-ratio (SNR) of m multiple antennas in the line-of-sight case. The antennas are placed at random positions within a disc of given diameter d. We characterize the angular signal strength with three sectors: the main beam, the side beams and an area of white Gaussian noise. The SNR and the sector angles depend on d, m, and the wavelength λ. It turns out that for randomized antenna positions the analysis can be reduced to the analysis of a random geometric walk in two dimensions. The angle of the main beam is approximately λ/d with a SNR proportional to √m. For the side beams the SNR is proportional to sinc(2αd=λ) where α denotes the angle deviating from the target. The range of the side beams is limited to an approximate angle of λ/d√m. Beyond this angle we observe average white Gaussian noise.

We introduce the Read-Write-Coding-System (RWC), a very flexible class of linear block codes that generate efficient and flexible erasure codes for storage networks. In particular, given a message x of k symbols and a codeword y of n symbols, an RW code defines additional parameters k≤ r,w≤ n that offer enhanced possibilities to adjust the fault-tolerance capability of the code. More precisely, an RWC provides linear (n,r,d) -codes that have: (a) minimum (Hamming) distance d = n-r+1 for any two codewords, and (b) for any codeword y 1 there exists a codeword y 2 with distance of at most w . Furthermore, depending on the values r,w and the code alphabet, different block codes such as parity codes (e.g., RAID 4/5) or Reed-Solomon (RS) codes (if r = k and thus, w = n ) can be generated. In storage networks in which I/O accesses are very costly and redundancy is crucial, this flexibility has considerable advantages as r and w can optimally be adapted to read or write intensive applications; only w symbols must be updated if the message x changes completely, which is different from other codes that always need to rewrite y completely as x changes. In this article, we first state a tight lower bound and basic conditions for all RW codes. Furthermore, we introduce special RW codes in which all mentioned parameters are adjustable even online, that is, RW codes which are adaptive to changing demands. At last, we investigate the question for which choices of (k,r,w,n) a coding system exists over the binary alphabet F 2 = {0,1} and discuss how RW codes can be combined.

We present an approach for the localization of passive receiver nodes in a communication network. In our settings the positions of the nodes are unknown. The only source of information is the time when environmental sound or ultrasound signals are received. The discrete signals occur at unknown positions and times, but they can be distinguished. The clocks of the receivers are synchronized, so the time differences of arrival (TDOA) of the signals can be computed. The goal is to determine the relative positions of all receiver nodes and implicitly the positions and times of the environmental signals. Our novel approach, the Iterative Cone Alignment algorithm, solves iteratively a non-linear optimization problem of time differences of arrival (TDOA) by a physical spring-mass simulation. Here, our algorithm shows a smaller tendency to get stuck in local minima than a non-linear least-squares approach. The approach is tested in numerous simulations and in a real-world setting where we demonstrate and evaluate a tracking system for a moving ultrasound beacon without the need to initially calibrate the positions of the receivers. Using our approach we estimate the trajectory of a moving model train with a precision in the range of centimeters.

We consider an anchor-free, relative localization and synchronization problem where a set of n receiver nodes and m wireless signal sources are independently, uniformly, and randomly distributed in a disk in the plane. The signals can be distinguished and their capture times can be measured. At the beginning neither the positions of the signal sources and receivers are known nor the sending moments of the signals. Now each receiver captures each signal after its constant speed journey over the unknown distance between signal source and receiver position. Given these nm capture times the task is to compute the relative distances between all synchronized receivers. In a more generalized setting the receiver nodes have no synchronized clocks and need to be synchronized from the capture times of the stolen signals.

The ability of tiny embedded devices to run large and feature-rich Java programs is typically constrained by the amount of memory installed on those devices. Furthermore, the useful operation of such devices in a wireless sensor application is limited by their battery life. We propose a garbage collection (GC) scheme called Offline GC which alleviates both these limitations. Our approach defies the current practice in which an object may be deallocated only if it is unreachable. Offline GC allows freeing an object that is still reachable but is guaranteed not to be used again in the program. Furthermore, it may deallocate an object inside a function, a loop or a block where it is last used, even if that object is assigned to a global field. This leads to a larger amount of memory available to a program.

We present 3nuts, a self-stabilizing peer-to-peer (p2p) network supporting range queries and adapting the overlay structure to the underlying physical network. 3nuts combines concepts of structured and unstructured p2p networks to over-come their individual shortcomings while keeping their strengths. This is achieved by combining self maintaining random networks for robustness, a search tree to allow range queries, and DHTs for load balancing. Simple handshake operations with provable guarantees are used for maintenance and self-stabilization. Efficiency of load balancing, fast data access, and robustness are proven by rigorous analysis.

We present a smartphone application to localize a group of networking devices in a mobile environment without the need of any further infrastructure. Ambient sound signals are the only information source. Time marks are assigned to the recorded audio stream for distinctive audio events, out of which we evaluate the time differences of arrival (TDOA) between the devices. In contrast to common multilateration approaches we do not need any positional anchor points - neither any predefined smartphone positions nor the positions of the environmental sounds. As an application scenario we can localize arbitrary devices using only the random environmental noise peaks, e.g. in crowded areas like market places or concerts with the usual soundscape, or for thunderstorm tracking. Especially, our solution becomes useful when established positioning systems (e.g. GPS) are too imprecise or fail, as during indoor self-localization. We use a Wi-Fi connection to synchronize the clocks of the devices and to exchange time marks. In our experiments we evaluated the audio information and synchronized the devices up to an order of 0.1 ms. This results in a positioning precision in the order of 10 cm.

Partitioning is the dominant technique to transmit large files in peer-to-peer networks. A peer can redistribute each part immediately after its download. BitTorrent combines this approach with incentives for uploads and has thereby become the most successful peer-to-peer network. However, BitTorrent fails if files are unpopular and are distributed by irregularly participating peers. It is known that Network Coding always provides the optimal data distribution, referred as optimal performance. Yet, for encoding or decoding a single code block the whole file must be read and users are not willing to read O(n2) data blocks from hard disk for sending n message blocks. We call this the disk read/write complexity of an encoding.

BitTorrent and practical network coding are efficient methods for sharing files in a peer-to-peer network. Both face the problem to distribute a given file using peers with different and dynamic bandwidth and only temporal availability. For this, BitTorrent partitions the files and uses the upload and download of each peer. In addition to this, practical network coding uses a random linear combination of the parts. The original file can be decoded by a matrix operation as soon as enough linear combinations have been gathered at a peer. It is known that practical network coding optimizes the network flow in any peer-to-peer network, yet suffers from the cost of read/write disk operations for encoding and decoding. In this respect, BitTorrent is very efficient, yet falls behind because it has to face the coupon collector problem when distributing parts. We present paircoding as an alternative which is regarding file sharing at least as good as BitTorrent and shares nearly the same computational disk access complexity with BitTorrent. In some scenarios paircoding outperforms BitTorrent regarding network flow and performs as well as practical network coding. Paircoding distributes only a linear combination of two parts which alleviates the coupon collector problem of BitTorrent without the computational overhead of practical network coding. For analytical proofs of these statements we formalize file sharing in a peer-to-peer network in a round model and introduce a computational model which allows to compare the efficiency of the file sharing algorithms in a distributed environment. Since BitTorrent tries to overcome the coupon collector problem with various policies we face a family of BitTorrent systems. We show that for each BitTorrent policy there is a paircoding policy which is at least as good regarding file sharing quality.

Coverage holes are usually considered as harmful in wireless sensor networks. Many sensor deployment strategies and coverage recovery algorithms have been proposed to improve the sensing coverage and remove detected coverage holes. However, in many situations, full coverage can not be guaranteed or consistently maintained throughout the network lifetime. Moreover, in certain applications, full coverage is not possible or unnecessary. In this paper, we introduce SmartRing, a distributed target tracking strategy that utilizes the coverage holes in sparse network or network partition. Sensor nodes not only act as communication relays, but also take part in aiding path planning of pursuer robot. Sensors forming the ring of a coverage hole gather and provide target information to the pursuer. Once a target is detected, sensor mobility or activity is coordinated such that the pursuer benefits from the variable size of the coverage hole that act as a trap. We perform simulation study to evaluate how feasible and efficient the proposed strategy is running in different modes.

Modern peer-to-peer file sharing systems distribute large files among peers using block partitioning. Blocks can be redistributed by a peer even before the whole file is available which highly decreases the distribution time. All peer-to-peer networks face the problem of dynamic participation of the peers and dynamic bandwidth in the network. A leaving peer can cause an unrecoverable loss of blocks and obstruct further downloads of the file. Furthermore, the choice which block needs to be sent to which peer is a hard question. A random choice leads to the coupon collector problem which decreases the transmission rate. Filesharing networks like BitTorrent or Splitstream face such problems.

We present TakaTuka, a tiny Java Virtual Machine (JVM) for wireless sensor motes. TakaTuka's preliminary version successfully runs on Crossbow's mica2 motes. Furthermore, TakaTuka also runs on Windows and Unix.

We consider the well-known vertex coloring problem: given a graph G, find a coloring of the vertices so that no two neighbors in G have the same color. It is trivial to see that every graph of maximum degree Delta can be colored with Delta + 1 colors, and distributed algorithms that find a (Delta + 1)-coloring in a logarithmic number of communication rounds, with high probability, are known since more than a decade. This is in general the best possible if only a constant number of bits can be sent along every edge in each round. In fact, we show that for the n-node cycle the bit complexity of the coloring problem is Omega(log n). More precisely, if only one bit can be sent along each edge in a round, then every distributed coloring algorithm (i.e., algorithms in which every node has the same initial state and initially only knows its own edges) needs at least Omega(log n) rounds, with high probability, to color the cycle, for any finite number of colors. But what if the edges have orientations, i.e., the end-points of an edge agree on its orientation (while bits may still flow in both directions)? Does this allow one to provide faster coloring algorithms? Interestingly, for the cycle in which all edges have the same orientation, we show that a simple randomized algorithm can achieve a 3-coloring with only O(radic(log n)) rounds of bit transmissions, with high probability (w.h.p.). This result is tight because we also show that the bit complexity of coloring an oriented cycle is Omega(radic(log n)), with high probability, no matter how many colors are allowed. The 3-coloring algorithm can be easily extended to provide a (Delta + 1)-coloring for all graphs of maximum degree Delta in O(radic(log n)) rounds of bit transmissions, w.h.p., if Delta is a constant, the edges are oriented, and the graph does not contain an oriented cycle of length less than radic(log n). Using more complex algorithms, we show how to obtain an O(Delta)-coloring for arbitrary oriented graphs of maximum degree Delta using essentially O(log Deltaradic(log n)) rounds of bit transmissions, w.h.p., provided that the graph does not contain an oriented cycle of length less than radic(log n)

The research interest in sensor nets is still growing because they simplify data acquisition in many applications. If hardware resources are very sparse, routing algorithms cannot use data gathering. However, if a large number of channels can be used, then parallel transmission can compensate this drawback. If the senders and receivers are not known in advance, then a control channel poses a bottleneck for communication. We present an oblivious MAC protocol, called the funnel protocol, where the channels are nearly optimally utilized in parallel. In this, senders and receivers choose for a polylogarithmic number of rounds (several sending attempts) a decreasing number of channels which are selected equiprobably. Then, we show that a previously presented approach using only one round and therefore one type of probability distribution is optimal up to some constant factor, and considerably worse than the funnel protocol. The protocol works with few resources if a sufficient number of channels is available. The funnel protocol is simple, elegant, and does not need to know the number of senders and receivers, thus being oblivious. On the bottom line we prove that small messages can be efficiently transmitted by the MAC layer in parallel without a control channel if more than one channel for communication can be used

We present a local random graph transformation for weakly connected multi-digraphs with regular out-degree which produces every such graph with equal probability. This operation, called Pointer-Push&Pull, changes only two neighboring edges. Such an operation is highly desirable for a peerto-peer network to establish and maintain well connected expander graphs as reliable and robust network backbone. The Pointer-Push&Pull operation can be used in parallel without central coordination and each operation involves only two peers which have to exchange two messages, each carrying the information of one edge only.We show that a series of random Pointer-Push&Pull operations eventually leads to a uniform probability distribution over all weakly connected out-regular multi-digraphs. Depending on the probabilities used in the operation this uniform probability distribution either refers to the set of all weakly connected out-regular multi-digraphs or to the set of all weakly connected out-regular edge-labeled multidigraphs. In multi-digraphs multiple edges or self-loops may occur. In an out-regular digraph each node has the same number of outgoing edges.For this, we investigate the Markov-Process defined by the Pointer-Push&Pull operation over the set of all weakly connected multi-digraphs. We show that a Pointer-Push&Pull operation -- although preserving weak connectivity only -- can reach every weakly connected multi-digraph. The main argument follows from the symmetry of the Markov-Process described by the Pointer-Push&Pull operation over the set of all weakly connected out-regular multi-digraphs.

We present k-Flipper, a graph transformation algorithm that transforms regular undirected graphs. Given a path of k+2 edges it interchanges the end vertices of the path. By definition this operation preserves regularity and connectivity. We show that every regular connected graph can be reached by a series of these operations for all k ¡Ý 1. We use a randomized version, called Random k-Flipper, in order to create random regular connected undirected graphs that may serve as a backbone for peer-to-peer networks. We prove for degree d¡Ê ¦¸(log n) that a series of O(dn) Random k-Flipper operations with k ∈ ¦¨(d2n2 log 1/¦Å) transforms any graph into an expander graph with high probability, i.e. 1-n-¦¨(1).

We present two methods for weighted consistent hashing also known as weighted distributed hash tables. The first method, called Linear Method, combines the standard consistent hasing introduced by Karger et al. [9] with a linear weighted distance measure. By using node copies and different partitions of the hash space, the balance of this scheme approximates the fair weight relationship with high probability. The second method, called the Logarithmic Method, uses a logarithmic weighted distance between the peers and the data to find the corresponding node. For distributing one data element it provides perfect weighted balance. To provide this distribution for many data elements we use partitions to achieve a fair balance with high probability. These methods provide small fragmentation, which means that the hash space is divided into at most O (n log n) intervals. Furthermore, there is an efficient data structure that assigns data elements to the nodes in expected time O (log n). If small fragmentation is not an issue one can replace the use of partitions by a method we call double hash functions. This method needs O (n) for assigning elements to a node, yet it can be directly used for Storage Area Networks, where the number of nodes is small compared to participating nodes in Peer-to-Peer networks.

We investigate distributed algorithms for mobile ad hoc networks for moving radio stations with adjustable transmission power in a worst case scenario. We consider two models to find a reasonable restriction on the worst-case mobility. In the pedestrian model we assume a maximum speed vmax of the radio stations, while in the vehicular model we assume a maximum acceleration amax of the points.Our goal is to maintain persistent routes with nice communication network properties like hop distance, energy-consumption, congestion and number of interferences. A route is persistent, if we can guarantee that all edges of this route can be uphold for a given time span Δ, which is a parameter denoting the minimum time the mobile network needs to adopt changes, i.e. update routing tables, change directory entries, etc. This Δ can be used as the length of an update interval for a proactive routing scheme.We extend some known notions such as transmission range, interferences, spanner, power spanner and congestion to both mobility models and introduce a new parameter called crowdedness that states a lower bound on the number of radio interferences. Then we prove that a mobile spanner hosts a path system that polylogarithmically approximates the optimal congestion.We present distributed algorithms based on a grid clustering technique and a high-dimensional representation of the dynamical start situation which construct mobile spanners with low congestion, low interference number, low energy-consumption, and low degree. We measure the optimality of the output of our algorithm by comparing it with the optimal choice of persistent routes under the same circumstances with respect to pedestrian or vehicular worst-case movements. Finally, we present solutions for dynamic position information management under our mobility models.

We investigate the problem of path selection in radio networks for a given set of sites in two-dimensional space. For some given static point-to-point communication demand we define measures for congestion, energy consumption and dilation that take interferences between communication links into account.We show that energy optimal path selection for radio networks can be computed in polynomial time. Then, we introduce the diversity $g(V)$ of a set $V\subseteq \REAL^2$. It can be used to upperbound the number of interfering edges. For real-world applications it can be regarded as $\Theta(\log n)$. A main result of the paper is that a weak $c$-spanner construction as a communication network allows to approximate the congestion-optimal communication network by a factor of $O(g(V)^2)$.Furthermore, we show that there are vertex sets where only one of the performance parameters congestion, energy, and dilation can be optimized at a time. We show trade-offs lower bounding congestion $\times$ dilation and dilation $\times$ energy. For congestion and energy the situation is even worse. It is only possible to find a reasonable approximation for either congestion or energy minimization, while the other parameter is at least a polynomial factor worse than in the optimal network.

Investigates the class of epidemic algorithms that are commonly used for the lazy transmission of updates to distributed copies of a database. These algorithms use a simple randomized communication mechanism to ensure robustness. Suppose n players communicate in parallel rounds in each of which every player calls a randomly selected communication partner. In every round, players can generate rumors (updates) that are to be distributed among all players. Whenever communication is established between two players, each one must decide which of the rumors to transmit. The major problem is that players might not know which rumors their partners have already received. For example, a standard algorithm forwarding each rumor form the calling to the called players for /spl Theta/(ln n) rounds needs to transmit the rumor /spl Theta/(n ln n) times in order to ensure that every player finally receives the rumor with high probability. We investigate whether such a large communication overhead is inherent to epidemic algorithms. On the positive side, we show that the communication overhead can be reduced significantly. We give an algorithm using only O(n ln ln n) transmissions and O(ln n) rounds. In addition, we prove the robustness of this algorithm. On the negative side, we show that any address-oblivious algorithm needs to send /spl Omega/(n ln ln n) messages for each rumor, regardless of the number of rounds. Furthermore, we give a general lower bound showing that time and communication optimality cannot be achieved simultaneously using random phone calls, i.e. every algorithm that distributes a rumor in O(ln n) rounds needs /spl omega/(n) transmissions.