Optimisation problems in wireless sensor networks

This thesis studies optimisation problems related to modern large-scale distributed systems, such as wireless sensor networks and wireless ad-hoc networks. The concrete tasks that we use as motivating examples are the following: (i) maximising the lifetime of a battery-powered wireless sensor network, (ii) maximising the capacity of a wireless communication network, and (iii) minimising the number of sensors in a surveillance application. A sensor node consumes energy both when it is transmitting or forwarding data, and when it is performing measurements. Hence task (i), lifetime maximisation, can be approached from two different perspectives. First, we can seek for optimal data flows that make the most out of the energy resources available in the network; such optimisation problems are examples of so-called max-min linear programs. Second, we can conserve energy by putting redundant sensors into sleep mode; we arrive at the sleep scheduling problem, in which the objective is to find an optimal schedule that determines when each sensor node is asleep and when it is awake. In a wireless network simultaneous radio transmissions may interfere with each other. Task (ii), capacity maximisation, therefore gives rise to another scheduling problem, the activity scheduling problem, in which the objective is to find a minimum-length conflict-free schedule that satisfies the data transmission requirements of all wireless communication links. Task (iii), minimising the number of sensors, is related to the classical graph problem of finding a minimum dominating set. However, if we are not only interested in detecting an intruder but also locating the intruder, it is not sufficient to solve the dominating set problem; formulations such as minimum-size identifying codes and locating–dominating codes are more appropriate. This thesis presents approximation algorithms for each of these optimisation problems, i.e., for max-min linear programs, sleep scheduling, activity scheduling, identifying codes, and locating–dominating codes. Two complementary approaches are taken. The main focus is on local algorithms, which are constant-time distributed algorithms. The contributions include local approximation algorithms for max-min linear programs, sleep scheduling, and activity scheduling. In the case of max-min linear programs, tight upper and lower bounds are proved for the best possible approximation ratio that can be achieved by any local algorithm. The second approach is the study of centralised polynomial-time algorithms in local graphs – these are geometric graphs whose structure exhibits spatial locality. Among other contributions, it is shown that while identifying codes and locating–dominating codes are hard to approximate in general graphs, they admit a polynomial-time approximation scheme in local graphs.

Voluntary Energy Harvesting Relays and Selection in Cooperative Wireless Networks

The use of energy harvesting (EH) nodes as cooperative relays is a promising and emerging solution in wireless systems such as wireless sensor networks. It harnesses the spatial diversity of a multi-relay network and addresses the vexing problem of a relay's batteries getting drained in forwarding information to the destination. We consider a cooperative system in which EH nodes volunteer to serve as amplify-and-forward relays whenever they have sufficient energy for transmission. For a general class of stationary and ergodic EH processes, we introduce the notion of energy constrained and energy unconstrained relays and analytically characterize the symbol error rate of the system. Further insight is gained by an asymptotic analysis that considers the cases where the signal-to-noise-ratio or the number of relays is large. Our analysis quantifies how the energy usage at an EH relay and, consequently, its availability for relaying, depends not only on the relay's energy harvesting process, but also on its transmit power setting and the other relays in the system. The optimal static transmit power setting at the EH relays is also determined. Altogether, our results demonstrate how a system that uses EH relays differs in significant ways from one that uses conventional cooperative relays.

Incipient motion design of sand bed channels affected by bed suction

Seepage through sand bed channels in a downward direction (suction) reduces the stability of particles and initiates the sand movement. Incipient motion of sand bed channel with seepage cannot be designed by using the conventional approach. Metamodeling techniques, which employ a non-linear pattern analysis between input and output parameters and solely based on the experimental observations, can be used to model such phenomena. Traditional approach to find non-dimensional parameters has not been used in the present work. Parameters, which can influence the incipient motion with seepage, have been identified and non-dimensionalized in the present work. Non-dimensional stream power concept has been used to describe the process. By using these non-dimensional parameters; present work describes a radial basis function (RBF) metamodel for prediction of incipient motion condition affected by seepage. The coefficient of determination, R-2 of the model is 0.99. Thus, it can be said that model predicts the phenomena very well. With the help of the metamodel, design curves have been presented for designing the sand bed channel when it is affected by seepage. (C) 2010 Elsevier B.V. All rights reserved.

Mobile Base Stations Placement and Energy Aware Routing in Wireless Sensor Networks

Increasing network lifetime is important in wireless sensor/ad-hoc networks. In this paper, we are concerned with algorithms to increase network lifetime and amount of data delivered during the lifetime by deploying multiple mobile base stations in the sensor network field. Specifically, we allow multiple mobile base stations to be deployed along the periphery of the sensor network field and develop algorithms to dynamically choose the locations of these base stations so as to improve network lifetime. We propose energy efficient low-complexity algorithms to determine the locations of the base stations; they include i) Top-K-max algorithm, ii) maximizing the minimum residual energy (Max-Min-RE) algorithm, and iii) minimizing the residual energy difference (MinDiff-RE) algorithm. We show that the proposed base stations placement algorithms provide increased network lifetimes and amount of data delivered during the network lifetime compared to single base station scenario as well as multiple static base stations scenario, and close to those obtained by solving an integer linear program (ILP) to determine the locations of the mobile base stations. We also investigate the lifetime gain when an energy aware routing protocol is employed along with multiple base stations.

Variation of stream power with seepage in sand-bed channels

Downward seepage (suction) increases the mobility of the channel. In this study, experimental investigations were carried out to analyse the suction effect on stream power along the downstream side of the flume. It was observed that stream power has a major influence on the stability and mobility of the bed particles, due to suction. Stream power is found to be greater at the upstream side and lower at the downstream side. This reduces the increment in the mobility of the sand particles due to suction at the downstream side. Thus, there is more erosion at the upstream side than the downstream side. It was also found that the amount of deposition of sand particles at the downstream side, because of the high stream power at the upstream side, is greater than the amount of erosion of sand particles from the downstream side.

Cooperative Spectrum Sensing Algorithms For OFDM Systems with Frequency Selective Channels

This paper considers the problem of spectrum sensing in cognitive radio networks when the primary user employs Orthogonal Frequency Division Multiplexing (OFDM). We specifically consider the scenario when the channel between the primary and a secondary user is frequency selective. We develop cooperative sequential detection algorithms based on energy detectors. We modify the detectors to mitigate the effects of some common model uncertainties such as timing and frequency offset, IQ-imbalance and uncertainty in noise and transmit power. The performance of the proposed algorithms are studied via simulations. We show that the performance of the energy detector is not affected by the frequency selective channel. We also provide a theoretical analysis for some of our algorithms.

Model Based Target Tracking in a Wireless Network of Passive Infrared Sensor Nodes

We consider the problem of tracking an intruder in a plane region by using a wireless sensor network comprising motes equipped with passive infrared (PIR) sensors deployed over the region. An input-output model for the PIR sensor and a method to estimate the angular speed of the target from the sensor output are proposed. With the measurement model so obtained, we study the centralized and decentralized tracking performance using the extended Kalman filter.

Past Queue Length Based Low-Overhead Link Scheduling in Multi-beam Wireless Mesh Networks

Wireless mesh networks with multi-beam capability at each node through the use of multi-antenna beamforming are becoming practical and attracting increased research attention. Increased capacity due to spatial reuse and increased transmission range are potential benefits in using multiple directional beams in each node. In this paper, we are interested in low-complexity scheduling algorithms in such multi-beam wireless networks. In particular, we present a scheduling algorithm based on queue length information of the past slots in multi-beam networks, and prove its stability. We present a distributed implementation of this proposed algorithm. Numerical results show that significant improvement in delay performance is achieved using the proposed multi-beam scheduling compared to omni-beam scheduling. In addition, the proposed algorithm is shown to achieve a significant reduction in the signaling overhead compared to a current slot queue length approach.

Robust Semi-Blind Estimation for Beamforming Based MIMO Wireless Communication

In this paper, we present robust semi-blind (SB) algorithms for the estimation of beamforming vectors for multiple-input multiple-output wireless communication. The transmitted symbol block is assumed to comprise of a known sequence of training (pilot) symbols followed by information bearing blind (unknown) data symbols. Analytical expressions are derived for the robust SB estimators of the MIMO receive and transmit beamforming vectors. These robust SB estimators employ a preliminary estimate obtained from the pilot symbol sequence and leverage the second-order statistical information from the blind data symbols. We employ the theory of Lagrangian duality to derive the robust estimate of the receive beamforming vector by maximizing an inner product, while constraining the channel estimate to lie in a confidence sphere centered at the initial pilot estimate. Two different schemes are then proposed for computing the robust estimate of the MIMO transmit beamforming vector. Simulation results presented in the end illustrate the superior performance of the robust SB estimators.

Tunable Locally-Optimal Geographical Forwarding in Wireless Sensor Networks with Sleep-Wake Cycling Nodes

We consider a wireless sensor network whose main function is to detect certain infrequent alarm events, and to forward alarm packets to a base station, using geographical forwarding. The nodes know their locations, and they sleep-wake cycle, waking up periodically but not synchronously. In this situation, when a node has a packet to forward to the sink, there is a trade-off between how long this node waits for a suitable neighbor to wake up and the progress the packet makes towards the sink once it is forwarded to this neighbor. Hence, in choosing a relay node, we consider the problem of minimizing average delay subject to a constraint on the average progress. By constraint relaxation, we formulate this next hop relay selection problem as a Markov decision process (MDP). The exact optimal solution (BF (Best Forward)) can be found, but is computationally intensive. Next, we consider a mathematically simplified model for which the optimal policy (SF (Simplified Forward)) turns out to be a simple one-step-look-ahead rule. Simulations show that SF is very close in performance to BF, even for reasonably small node density. We then study the end-to-end performance of SF in comparison with two extremal policies: Max Forward (MF) and First Forward (FF), and an end-to-end delay minimising policy proposed by Kim et al. 1]. We find that, with appropriate choice of one hop average progress constraint, SF can be tuned to provide a favorable trade-off between end-to-end packet delay and the number of hops in the forwarding path.

Bounds on the Lifetime of Wireless Sensor Networks Employing Multiple Data Sinks

Employing multiple base stations is an attractive approach to enhance the lifetime of wireless sensor networks. In this paper, we address the fundamental question concerning the limits on the network lifetime in sensor networks when multiple base stations are deployed as data sinks. Specifically, we derive upper bounds on the network lifetime when multiple base stations are employed, and obtain optimum locations of the base stations (BSs) that maximize these lifetime bounds. For the case of two BSs, we jointly optimize the BS locations by maximizing the lifetime bound using a genetic algorithm based optimization. Joint optimization for more number of BSs is complex. Hence, for the case of three BSs, we optimize the third BS location using the previously obtained optimum locations of the first two BSs. We also provide simulation results that validate the lifetime bounds and the optimum locations of the BSs.

Receiver-Only Optimized Vector Quantization for Noisy Channels

This paper considers the design and analysis of a filter at the receiver of a source coding system to mitigate the excess Mean-Squared Error (MSE) distortion caused due to channel errors. It is assumed that the source encoder is channel-agnostic, i.e., that a Vector Quantization (VQ) based compression designed for a noiseless channel is employed. The index output by the source encoder is sent over a noisy memoryless discrete symmetric channel, and the possibly incorrect received index is decoded by the corresponding VQ decoder. The output of the VQ decoder is processed by a receive filter to obtain an estimate of the source instantiation. In the sequel, the optimum linear receive filter structure to minimize the overall MSE is derived, and shown to have a minimum-mean squared error receiver type structure. Further, expressions are derived for the resulting high-rate MSE performance. The performance is compared with the MSE obtained using conventional VQ as well as the channel optimized VQ. The accuracy of the expressions is demonstrated through Monte Carlo simulations.

Seepage effects on sand-bed channels

ExperimentS were conducted to find the effects of seepage on flow over a sand bed in a straight rectangular flume under two conditions: (1) When the channel bed is plane, horizontal, and nontransporting; and (2) when the bed is transporting at a constant sediment concentration. Effects of both injection and suction, caused by seepage flow into and out of the channel bed, are studied for condition 1; and only suction effects are studied for condition 2, Three sands, sizes 0.34 mm, 0.53 mm, and 0.80 mm, are used in the study. It is found that seepage can cause an increase or decrease in the bed shear stress relative to no seepage for the two conditions. The change in bed shear stress depends on the relative magnitudes of the bed shear stress and the critical shear stress of particles under the no-seepage condition, sediment concentration, and the seepage rate. Quantitative relationships giving the ratio of bed shear stresses with and without seepage are presented for both conditions of the bed. A procedure to estimate the changes in bed shear stress, friction factor, Manning's n, and stream power due to seepage for known initial conditions of the channel and the amount of applied seepage is presented

A numerical study of division of flow in open channels

A two-dimensional numerical model which employs the depth-averaged forms of continuity and momentum equations along with k-e turbulence closure scheme is used to simulate the flow at the open channel divisions. The model is generalised to flows of arbitrary geometries and MacCormack finite volume method is used for solving governing equations. Application of cartesian version of the model to analyse the flow at right-angled junction is presented. The numerical predictions are compared with experimental data of earlier investigators and measurements made as part of the present study. Performance of the model in predicting discharge distribution, surface profiles, separation zone parameters and energy losses is evaluated and discussed in detail. To illustrate the application of the numerical model to analyse the flow in acute angled offtakes and streamlined branch entries, a few computational results are presented.