Deploying Wireless Sensor Networks under Limited Mobility Constraints

In this paper, we study the issue of sensor network deployment using limited mobility sensors. By limited mobility, we mean that the maximum distance that sensors are capable of moving to is limited. Given an initial deployment of limited mobility sensors in a field clustered into multiple regions, our deployment problem is to determine a movement plan for the sensors to minimize the variance in number of sensors among the regions and simultaneously minimize the sensor movements. Our methodology to solve this problem is to transfer the nonlinear variance/movement minimization problem into a linear optimization problem through appropriate weight assignments to regions. In this methodology, the regions are assigned weights corresponding to the number of sensors needed. During sensor movements across regions, larger weight regions are given higher priority compared to smaller weight regions, while simultaneously ensuring a minimum number of sensor movements. Following the above methodology, we propose a set of algorithms to our deployment problem. Our first algorithm is the optimal maximum flow-based (OMF) centralized algorithm. Here, the optimal movement plan for sensors is obtained based on determining the minimum cost maximum weighted flow to the regions in the network. We then propose the simple peak-pit-based distributed (SPP) algorithm that uses local requests and responses for sensor movements. Using extensive simulations, we demonstrate the effectiveness of our algorithms from the perspective of variance minimization, number of sensor movements, and messaging overhead under different initial deployment scenarios.     

Distributed fault-tolerant classification in wireless sensor networks

Fault-tolerance and data fusion have been considered as two fundamental functions in wireless sensor networks. In this paper, we propose a novel approach for distributed multiclass classification using a fault-tolerant fusion rule for wireless sensor networks. Binary decisions from local sensors, possibly in the presence of faults, are forwarded to the fusion center that determines the final classification result. Classification fusion in our approach is implemented via error correcting codes to incorporate fault-tolerance capability. This new approach not only provides an improved fault-tolerance capability but also reduces computation time and memory requirements at the fusion center. Code matrix design is essential for the design of such systems. Two efficient code matrix design algorithms are proposed in this paper. The relative merits of both algorithms are also studied. We also develop sufficient conditions for asymptotic detection of the correct hypothesis by the proposed approach. Performance evaluation of the proposed approach in the presence of faults is provided. These results show significant improvement in fault-tolerance capability as compared with conventional parallel fusion networks.     

Adaptive cost efficient deployment strategy for homogeneous wireless camera sensors

Availability of low cost low power camera sensors is likely to make possible applications that may otherwise have been infeasible. In this paper we investigate a cost efficient camera sensor deployment strategy based on random deployment of homogeneous sensors to monitor and/or surveillance a region of interest. We assume that there are costs associated with the sensors as well as with the deployments and our goal is to minimize the total cost while satisfying the desired coverage requirement. We consider two cases which assume the sensing field is obstacle free or with obstacles, and we develop analytical methods to derive the expected coverage of a single sensor as well as the joint coverage for a given number of homogenous camera sensors. Following this we propose an adaptive sensor deployment strategy, which deploys different number of sensors in each iteration, based on our analytical method. We then evaluate the expected cost of our deployment strategy by deriving expressions for the number of deployments and the number of sensors deployed during each deployment as a function of the probability distributions of joint coverage by sensors. We carry out simulation studies to validate the analytical results. Simulation studies are also used to demonstrate that our deployment strategy leads to near optimal values of sensors and deployments and hence achieves the overall low cost.     

Performance Analysis and Code Design for Minimum Hamming Distance Fusion in Wireless Sensor Networks

Distributed classification fusion using error-correcting codes (DCFECC) has recently been proposed for wireless sensor networks operating in a harsh environment. It has been shown to have a considerably better capability against unexpected sensor faults than the optimal likelihood fusion. In this paper, we analyze the performance of a DCFECC code with minimum Hamming distance fusion. No assumption on identical distribution for local observations, as well as common marginal distribution for the additive noises of the wireless links, is made. In addition, sensors are allowed to employ their own local classification rules. Upper bounds on the probability of error that are valid for any finite number of sensors are derived based on large deviations technique. A necessary and sufficient condition under which the minimum Hamming distance fusion error vanishes as the number of sensors tends to infinity is also established. With the necessary and sufficient condition and the upper error bounds, the relation between the fault-tolerance capability of a DCFECC code and its pair-wise Hamming distances is characterized, and can be used together with any code search criterion in finding the code with the desired fault-tolerance capability. Based on the above results, we further propose a code search criterion of much less complexity than the minimum Hamming distance fusion error criterion adopted earlier by the authors. This makes the code construction with acceptable fault-tolerance capability for a network with over a hundred of sensors practical. Simulation results show that the code determined based on the new criterion of much less complexity performs almost identically to the best code that minimizes the minimum Hamming distance fusion error. Also simulated and discussed are the performance trends of the codes searched based on the new simpler criterion with respect to the network size and the number of hypotheses     

Iterative Decoding Convergence and Termination of Serially Concatenated Codes

In this paper, we demonstrate that the previously proposed arrangements of serially concatenated codes have extrinsic-information-transfer (EXIT) functions that intersect each other at points that are near but not at the (1, 1) point in the top-right-hand corner of the EXIT chart, which is typically associated with elevated error floors. We propose a novel arrangement having EXIT functions that do not intersect before the (1, 1) point, which is typically associated with approaching the maximum-likelihood (ML) bit-error-ratio (BER) performance. Our method employs an inner recursive code that is terminated using specifically designed termination sequences, which have a minimum Hamming distance of at least two between each other. Additionally, we provide optimal termination sequences for a range of inner code designs. Finally, we demonstrate that our novel approach can facilitate useful BER reductions in the challenging application scenario when employing short frame lengths on the order of 100 bits, which are typical in wireless sensor networks, for example.      

Push &; Pull: autonomous deployment of mobile sensors for a complete coverage

Mobile sensor networks are important for several strategic applications devoted to monitoring critical areas. In such hostile scenarios, sensors cannot be deployed manually and are either sent from a safe location or dropped from an aircraft. Mobile devices permit a dynamic deployment reconfiguration that improves the coverage in terms of completeness and uniformity. In this paper we propose a distributed algorithm for the autonomous deployment of mobile sensors called Push & Pull. According to our proposal, movement decisions are made by each sensor on the basis of locally available information and do not require any prior knowledge of the operating conditions or any manual tuning of key parameters. We formally prove that, when a sufficient number of sensors are available, our approach guarantees a complete and uniform coverage. Furthermore, we demonstrate that the algorithm execution always terminates preventing movement oscillations. Numerous simulations show that our algorithm reaches a complete coverage within reasonable time with moderate energy consumption, even when the target area has irregular shapes. Performance comparisons between Push & Pull and one of the most acknowledged algorithms show how the former one can efficiently reach a more uniform and complete coverage under a wide range of working scenarios.     

Cache-aware optimization of BAN applications

Body-area sensor network or BAN-based health monitoring is increasingly becoming a popular alternative to traditional wired bio-monitoring techniques. However, most biomonitoring applications need continuous processing of large volumes of data, as a result of which both power consumption and computation bandwidth turn out to be serious constraints for sensor network platforms. This has resulted in a lot of recent interest in design methods, modeling and software analysis techniques specifically targeted towards BANs and applications running on them. In this paper we show that appropriate optimization of the application running on the communication gateway of a wireless BAN and accurate modeling of the microarchitectural details of the gateway processor can lead to significantly better resource usage and power savings. In particular, we propose a method for deriving the optimal order in which the different sensors feeding the gateway processor should be sampled, to maximize cache reuse. In addition, we also investigate the effects on cache reuse of different memory layouts of the code processing the different sensor data. The joint optimization of code layout and the order in which the different sensors should be sampled—in order to maximize code cache reuse—turns out to be a difficult combinatorial optimization problem. But our experiments show that optimizing the sampling order of the sensors has a much larger influence on cache reuse, compared to the effects that different code layouts have. Based on this, we also propose a heuristic that obtains near-optimal solutions in jointly optimizing both code layout as well the sensor sampling order. Our case study using a faint fall detection application—from the geriatric care domain—which is fed by a number of smart sensors to detect physiological and physical gait signals of a patient show very attractive power consumption in the underlying processor. Alternatively, our method can be used to improve the sampling frequency of the sensors, leading to higher reliability and better response time of the application.     

Connected sensor cover: self-organization of sensor networks for efficient query execution

Spatial query execution is an essential functionality of a sensor network, where a query gathers sensor data within a specific geographic region. Redundancy within a sensor network can be exploited to reduce the communication cost incurred in execution of such queries. Any reduction in communication cost would result in an efficient use of the battery energy, which is very limited in sensors. One approach to reduce the communication cost of a query is to self-organize the network, in response to a query, into a topology that involves only a small subset of the sensors sufficient to process the query. The query is then executed using only the sensors in the constructed topology. The self-organization technique is beneficial for queries that run sufficiently long to amortize the communication cost incurred in self-organization. In this paper, we design and analyze algorithms for suchself-organization of a sensor network to reduce energy consumption. In particular, we develop the notion of a connected sensor cover and design a centralized approximation algorithm that constructs a topology involving a near-optimal connected sensor cover. We prove that the size of the constructed topology is within an O(logn) factor of the optimal size, where n is the network size. We develop a distributed self-organization version of the approximation algorithm, and propose several optimizations to reduce the communication overhead of the algorithm. We also design another distributed algorithm based on node priorities that has a further lower communication overhead, but does not provide any guarantee on the size of the connected sensor cover constructed. Finally, we evaluate the distributed algorithms using simulations and show that our approaches results in significant communication cost reductions.     

Energy-Efficient Map Interpolation for Sensor Fields Using Kriging

We propose a spatial autocorrelation aware, energy efficient, and error bounded framework for interpolating maps from sensor fields. Specifically, we propose an iterative reporting framework that utilizes spatial interpolation models to reduce communication costs and enforce error control. The framework employs a simple and low overhead in-network coordination among sensors for selecting reporting sensors so that the coordination overhead does not eclipse the communication savings. Due to the probabilistic nature of the first round reporting, the framework is less sensitive to sensor failures and guarantees an error bound for all functional sensors for each epoch. We then propose a graceful integration of temporal data suppression models with our framework. This allows an adaptive utilization of spatial or temporal autocorrelation based on whichever is stronger in different regions of the sensor field. We conducted extensive experiments using data from a real-world sensor network deployment and a large Asian temperature dataset to show that the proposed framework significantly reduces messaging costs and is more resilient to sensor failures. We also implemented our proposed algorithms on a sensor network of MICAz motes. The results show that our algorithms save significant energy and the out of bound errors due to packet loss are below 5%.     

Joint design of fixed-rate source codes and multiresolution channelcodes

We propose three new design algorithms for jointly optimizing source and channel codes. Our optimality criterion is to minimize the average end-to-end distortion. For a given channel SNR and transmission rate, our joint source and channel code designs achieve an optimal allocation of bits between the source and channel coders. Our three techniques include a source-optimized channel code, a channel-optimized source code, and an iterative descent technique combining the design strategies of the other two codes. The joint designs use channel-optimized vector quantization (COVQ) for the source code and rate compatible punctured convolutional (RCPC) coding for the channel code. The optimal bit allocation reduces distortion by up to 6 dB over suboptimal allocations and by up to 4 dB relative to standard COVQ for the source data set considered. We find that all three code designs have roughly the same performance when their bit allocations are optimized. This result follows from the fact that at the optimal bit allocation the channel code removes most of the channel errors, in which case the three design techniques are roughly equivalent. We also compare the robustness of the three techniques to channel mismatch. We conclude the paper by relaxing the fixed transmission rate constraint and jointly optimizing the transmission rate, source code, and channel code     

Approximately Lower Triangular Ensembles of LDPC Codes With Linear Encoding Complexity

The complexity of brute-force encoding of low-density parity-check (LDPC) codes is proportional to the square value of the block length. Richardson and Urbanke have proposed efficient encoding algorithms for LDPC codes. These algorithms permute the parity-check matrix of the code iteratively, such that it becomes approximately lower triangular. We propose a new approach for efficient encoding of LDPC codes in which we modify the code ensemble to force an approximate lower triangular structure, thus eliminating the need to apply the algorithms of Richardson and Urbanke in this ensemble. We prove that the new ensemble has the same asymptotic threshold as the corresponding standard ensemble. The new ensemble can be used for linear time encoding of an arbitrary code profile. Computer simulations confirm that the performances of the standard and new ensembles are also very similar when using finite length codes     

Quasi‐regular rate‐compatible LDPC codes with a novel diagonal‐tailed encoding on noisy channels

It is well known that conventional rate‐compatible (RC) codes, such as Raptor codes, only perform well at long code lengths. However, we propose a class of RC codes with short code lengths in this paper. Particularly, we develop a computational approach to design online‐generated RC low‐density parity‐check (LDPC) codes available on noisy channels. We first propose a diagonal‐tailed encoding to generate Quasi‐regular low‐density generator matrix codes. Then, an optimal encoding profile for RC codes is achieved with a linear interpolation approach that is based on the fixed‐rate quasi‐regular LDPC codes. Finally, we evaluate the rateless and fixed‐rate performances of the proposed RC codes by extensive simulation results on various code rates with different modulations. Copyright © 2013 John Wiley & Sons, Ltd.     

Anti-collusion fingerprinting for multimedia

Digital fingerprinting is a technique for identifying users who use multimedia content for unintended purposes, such as redistribution. These fingerprints are typically embedded into the content using watermarking techniques that are designed to be robust to a variety of attacks. A cost-effective attack against such digital fingerprints is collusion, where several differently marked copies of the same content are combined to disrupt the underlying fingerprints. We investigate the problem of designing fingerprints that can withstand collusion and allow for the identification of colluders. We begin by introducing the collusion problem for additive embedding. We then study the effect that averaging collusion has on orthogonal modulation. We introduce a tree-structured detection algorithm for identifying the fingerprints associated with K colluders that requires O(Klog(n/K)) correlations for a group of n users. We next develop a fingerprinting scheme based on code modulation that does not require as many basis signals as orthogonal modulation. We propose a new class of codes, called anti-collusion codes (ACCs), which have the property that the composition of any subset of K or fewer codevectors is unique. Using this property, we can therefore identify groups of K or fewer colluders. We present a construction of binary-valued ACC under the logical AND operation that uses the theory of combinatorial designs and is suitable for both the on-off keying and antipodal form of binary code modulation. In order to accommodate n users, our code construction requires only O(/spl radic/n) orthogonal signals for a given number of colluders. We introduce three different detection strategies that can be used with our ACC for identifying a suspect set of colluders. We demonstrate the performance of our ACC for fingerprinting multimedia and identifying colluders through experiments using Gaussian signals and real images.     

Diagonal block space-time code design for diversity and coding advantage over flat fading channels

The potential promised by multiple transmit antennas has raised considerable interest in space-time coding for wireless communications. In this paper, we propose a systematic approach for designing space-time trellis codes over flat fading channels with full antenna diversity and good coding advantage. It is suitable for an arbitrary number of transmit antennas with arbitrary signal constellations. The key to this approach is to separate the traditional space-time trellis code design into two parts. It first encodes the information symbols using a one-dimensional (M,1) nonbinary block code, with M being the number of transmit antennas, and then transmits the coded symbols diagonally across the space-time grid. We show that regardless of channel time-selectivity, this new class of space-time codes always achieves a transmit diversity of order M with a minimum number of trellis states and a coding advantage equal to the minimum product distance of the employed block code. Traditional delay diversity codes can be viewed as a special case of this coding scheme in which the repetition block code is employed. To maximize the coding advantage, we introduce an optimal construction of the nonbinary block code for a given modulation scheme. In particular, an efficient suboptimal solution for multilevel phase-shift-keying (PSK) modulation is proposed. Some code examples with 2-6 bits/s/Hz and two to six transmit antennas are provided, and they demonstrate excellent performance via computer simulations. Although it is proposed for flat fading channels, this coding scheme can be easily extended to frequency-selective fading channels.     

Network configuration for optimal utilization efficiency of wireless sensor networks

This paper addresses the problem of configuring wireless sensor networks (WSNs). Specifically, we seek answers to the following questions: how many sensors should be deployed, what is the optimal sensor placement, and which transmission structure should be employed. The design objective is utilization efficiency defined as network lifetime per unit deployment cost. We propose an optimal approach and an approximation approach with reduced complexity to network configuration. Numerical and simulation results demonstrate the near optimal performance of the approximation approach. We also study the impact of sensing range, channel path loss exponent, sensing power consumption, and event arrival rate on the optimal network configuration.     

Lifetime Maximization Based on Coverage and Connectivity in Wireless Sensor Networks

We consider information retrieval in a wireless sensor network deployed to monitor a spatially correlated random field. We address optimal sensor scheduling and information routing under the performance measure of network lifetime. Both single-hop and multi-hop transmissions from sensors to an access point are considered. For both cases, we formulate the problems as integer programming based on the theories of coverage and connectivity in sensor networks. We derive upper bounds for the network lifetime that provide performance benchmarks for suboptimal solutions. Suboptimal sensor scheduling and data routing algorithms are proposed to approach the lifetime upper bounds with reduced complexity. In the proposed algorithms, we consider the impact of both the network geometry and the energy consumption in communications and relaying on the network lifetime. Simulation examples are used to demonstrate the performance of the proposed algorithms as compared to the lifetime upper bounds.     

Markov Decision Process Based Multiple Codes Assignment in UMTS WCDMA Mobile Networks

For achieving high transmission rate in mobile multimedia communications, 3G WCDMA systems adopt the Orthogonal Variable Spreading Factor (OVSF) code tree to assign a single channelization code for each accepted connection. Based on the orthogonal characteristic of an OVSF code tree, an allocated code blocks the channelization codes that are on the descendant branches and the ancestral codes of the allocated code. Several researches have been proposed to overcome the code-blocking problem for maximizing system utilization. By using both the code assignment and reassignment mechanisms, the system utilization and code blocking can be improved. Nevertheless, the data rate of traffic classes in such single code assignment system should be powers of two of the basic rate, which is impractical and wastes the system capacity when the required rate is not powers of two of the basic rate. A good solution is to assign multiple codes to a new connection, but causes two drawbacks: high complexity of handling multiple codes and high cost from using more number of rake combiners. Consequently, there is a trade-off between waste rate and complexity of handling multiple codes assignments. In previous researches, high computation complexity of assigning multiple codes for a connection and large number of reassignment codes suppressed the advantage of reducing waste rate. Therefore, we propose an adaptive efficient partition algorithm with the Markov Decision Process (MDP) analysis approach to reduce the large number of reassignment codes while improving waste rate. There are two main motivations in the proposed approach. First, we propose an adaptive efficient partition algorithm to determine multiple codes based on the current state of the OVSF code tree for the new incoming connection. Second, after determining the multiple codes, we adopt the MDP analysis to assign the least-cost code for each determined code. Numerical results demonstrate that the proposed MDP approach yields the least number of reassignments and the least number of codes per connection while reducing waste rate significantly, as compared to other approaches.     

Joint Monitoring and Routing in Wireless Sensor Networks Using Robust Identifying Codes

Wireless Sensor Networks (WSNs) provide an important means of monitoring the physical world, but their limitations present challenges to fundamental network services such as routing. In this work we utilize an abstraction of WSNs based on the theory of identifying codes. This abstraction has been useful in recent literature for a number of important monitoring problems, such as localization and contamination detection. In our case, we use it to provide a joint infrastructure for efficient and robust monitoring and routing in WSNs. Specifically, we make use of efficient and distributed algorithm for generating robust identifying codes, an NP-hard problem, with a logarithmic performance guarantee based on a reduction to the set k-multicover problem. We also show how this same identifying-code infrastructure provides a natural labeling that can be used for near-optimal routing with very small routing tables. We provide experimental results for various topologies that illustrate the superior performance of our approximation algorithms over previous identifying code heuristics.     

Improved approximation algorithms for connected sensor cover

Wireless sensor networks have recently posed many new system building challenges. One of the main problems is energy conservation since most of the sensors are devices with limited battery life and it is infeasible to replenish energy via replacing batteries. An effective approach for energy conservation is scheduling sleep intervals for some sensors, while the remaining sensors stay active providing continuous service. In this paper we consider the problem of selecting a set of active sensors of minimum cardinality so that sensing coverage and network connectivity are maintained. We show that the greedy algorithm that provides complete coverage has an approximation factor no better than Ω(log n), where n is the number of sensor nodes. Then we present algorithms that provide approximate coverage while the number of nodes selected is a constant factor far from the optimal solution. Finally, we show how to connect a set of sensors that already provides coverage.     

The Augmented State Diagram and its Application to Convolutional and Turbo Codes

Convolutional block codes, which are commonly used as constituent codes in turbo code configurations, accept a block of information bits as input rather than a continuous stream of bits. In this paper, we propose a technique for the calculation of the transfer function of convolutional block codes, both punctured and nonpunctured. The novelty of our approach lies in the augmentation of the conventional state diagram, which allows the enumeration of all codeword sequences of a convolutional block code. In the case of a turbo code, we can readily calculate an upper bound to its bit error rate performance if the transfer function of each constituent convolutional block code has been obtained. The bound gives an accurate estimate of the error floor of the turbo code and, consequently, our method provides a useful analytical tool for determining constituent codes or identifying puncturing patterns that improve the bit error rate performance of a turbo code, at high signal-to-noise ratios.