Using Local Geometry for Tunable Topology Control in Sensor Networks

Neighbor-Every-Theta (NET) graphs are such that each node has at least one neighbor in every theta angle sector of its communication range. We show that for thetas < pi, NET graphs are guaranteed to have an edge-connectivity of at least floor (2pi)/thetas, even with an irregular communication range. Our main contribution is to show how this family of graphs can achieve tunable topology control based on a single parameter thetas. Since the required condition is purely local and geometric, it allows for distributed topology control. For a static network scenario, a power control algorithm based on the NET condition is developed for obtaining k-connected topologies and shown to be significantly efficient compared to existing schemes. In controlled deployment of a mobile network, control over positions of nodes can be leveraged for constructing NET graphs with desired levels of network connectivity and sensing coverage. To establish this, we develop a potential fields based distributed controller and present simulation results for a large network of robots. Lastly, we extend NET graphs to 3D and provide an efficient algorithm to check for the NET condition at each node. This algorithm can be used for implementing generic topology control algorithms in 3D.     

Loop-free routing using diffusing computations

A family of distributed algorithms for the dynamic computation of the shortest paths in a computer network or internet is presented, validated, and analyzed. According to these algorithms, each node maintains a vector with its distance to every other node. Update messages from a node are sent only to its neighbors; each such message contains a distance vector of one or more entries, and each entry specifies the length of the selected path to a network destination, as well as an indication of whether the entry constitutes an update, a query, or a reply to a previous query. The new algorithms treat the problem of distributed shortest-path routing as one of diffusing computations, which was first proposed by Dijkstra and Scholten (1980). They improve on a number of algorithms introduced previously. The new algorithms are shown to converge in finite time after an arbitrary sequence of link cost or topological changes, to be loop-free at every instant, and to outperform all other loop-free routing algorithms previously proposed from the standpoint of the combined temporal, message, and storage complexities     

Optimized localization of target nodes using single mobile anchor node in wireless sensor network

In Wireless Sensor Networks (WSNs), main challenges which restrict the performance are data computation, lifetime, routing, task scheduling, security, organization and localization. Recently, numerous Computational Intelligence (CI) based potential solutions for above mentioned challenges have been proposed to fulfill the desired level of performance in WSNs. Use of CI gives autonomous and strong solutions to ascertain precise node location (2D/3D) with least hardware necessity (position finding device, i.e., GPS empowered gadget). Localization of target nodes in static scenario can be done more precisely. However, in case of mobility, determining accurate position of each node in network is a challenging problem. In this paper, a novel idea of localizing target nodes with moving single anchor node is proposed using CI based application of Particle Swarm Optimization (PSO) and H-Best Particle Swarm Optimization (HPSO). The moving anchor node is following the Hilbert trajectory. Proposed algorithms are actualized for range-based, distributed, non-collaborative and isotropic WSNs. Only single moving anchor node is used as a reference node to localize the target nodes in the entire network. In proposed algorithms, problem of Line of Sight (LoS) is minimized due to projection of virtual anchor nodes.     

Computational intelligence based localization of moving target nodes using single anchor node in wireless sensor networks

Wireless Sensor Networks (WSNs) have tremendous ability to interact and collect data from the physical world. The main challenges for WSNs regarding performance are data computation, prolong lifetime, routing, task scheduling, security, deployment and localization. In recent years, many Computational Intelligence (CI) based solutions for above mentioned challenges have been proposed to accomplish the desired level of performance in WSNs. Application of CI provides independent and robust solutions to ascertain accurate node position (2D/3D) with minimum hardware requirement (position finding device, i.e., GPS enabled device). The localization of static target nodes can be determined more accurately. However, in the case of moving target nodes, accurate position of each node in network is a challenging problem. In this paper, a novel concept of projecting virtual anchor nodes for localizing the moving target node is proposed using applications of Particle Swarm Intelligence, H-Best Particle Swarm Optimization, Biogeography Based Optimization and Firefly Algorithm separately. The proposed algorithms are implemented for range-based, distributed, non-collaborative and isotropic WSNs. Only single anchor node is used as a reference node to localize the moving target node in the network. Once a moving target node comes under the range of a anchor node, six virtual anchor nodes with same range are projected in a circle around the anchor node and two virtual anchor nodes (minimum three anchor nodes are required for 2D position) in surrounding (anchor and respective moving target node) are selected to find the 2D position. The performance based results on experimental mobile sensor network data demonstrate the effectiveness of the proposed algorithms by comparing the performance in terms of the number of nodes localized, localization accuracy and scalability. In proposed algorithms, problem of Line of Sight is minimized due to projection of virtual anchor nodes.     

Distributed Computation of Averages Over Wireless Sensor Networks Through Synchronization of Data-Encoded Pulse-Coupled Oscillators

This paper develops an efficient scheme for distributed computation of averages of the node data over wireless sensor networks. The scheme first formulates a data-encoded pulse-coupled oscillator (DE-PCO) model for sensor nodes, in which the node data is encoded into a PCO phase shift, and then it defines a deferred and accumulated coupling (DAC) strategy which describes the data coupling between different nodes. Following the DAC strategy, the coupled DE-PCO converges to a synchronizing equilibrium from which each node can decode the global average of the node data. Compared with the conventional communication network, the DE-PCO-based computation does not require special data routing and medium access control (MAC) protocols. Therefore, the proposed scheme is efficient and easy to implement.     

On distributed power control in full duplex wireless networks

In this paper, we first consider the problem of distributed power control in a Full Duplex (FD) wireless network consisting of multiple pairs of nodes, within which each node needs to communicate with its corresponding node. We aim to find the optimal transmition power for the FD transmitters such that the network-wide capacity is maximized. Based on the high Signal-to-Interference-Plus-Noise Ratio (SINR) approximation and a more general approximation method for logarithm functions, we develop effective distributed power control algorithms with the dual decomposition approach. We also extend the work to the general FD network scenario, which can be decomposed into subproblems of isolated nodes, paths, and cycles. The corresponding power control problem is then be solved with the distributed algorithm. The proposed algorithms are validated with simulation studies.     

Minimum Interference Channel Assignment in Multiradio Wireless Mesh Networks

In this paper, we consider multi-hop wireless mesh networks, where each router node is equipped with multiple radio interfaces and multiple channels are available for communication. We address the problem of assigning channels to communication links in the network with the objective of minimizing overall network interference. Since the number of radios on any node can be less than the number of available channels, the channel assignment must obey the constraint that the number of different channels assigned to the links incident on any node is atmost the number of radio interfaces on that node. The above optimization problem is known to be NP-hard. We design centralized and distributed algorithms for the above channel assignment problem. To evaluate the quality of the solutions obtained by our algorithms, we develop a semidefinite program and a linear program formulation of our optimization problem to obtain lower bounds on overall network interference. Empirical evaluations on randomly generated network graphs show that our algorithms perform close to the above established lower bounds, with the difference diminishing rapidly with increase in number of radios. Also, ns-2 simulations as well as experimental studies on testbed demonstrate the performance potential of our channel assignment algorithms in 802.11-based multi-radio mesh networks.     

Quantized incremental algorithms for distributed optimization

Wireless sensor networks are capable of collecting an enormous amount of data. Often, the ultimate objective is to estimate a parameter or function from these data, and such estimators are typically the solution of an optimization problem (e.g., maximum likelihood, minimum mean-squared error, or maximum a posteriori). This paper investigates a general class of distributed optimization algorithms for "in-network" data processing, aimed at reducing the amount of energy and bandwidth used for communication. Our intuition tells us that processing the data in-network should, in general, require less energy than transmitting all of the data to a fusion center. In this paper, we address the questions: When, in fact, does in-network processing use less energy, and how much energy is saved? The proposed distributed algorithms are based on incremental optimization methods. A parameter estimate is circulated through the network, and along the way each node makes a small gradient descent-like adjustment to the estimate based only on its local data. Applying results from the theory of incremental subgradient optimization, we find that the distributed algorithms converge to an approximate solution for a broad class of problems. We extend these results to the case where the optimization variable is quantized before being transmitted to the next node and find that quantization does not affect the rate of convergence. Bounds on the number of incremental steps required for a certain level of accuracy provide insight into the tradeoff between estimation performance and communication overhead. Our main conclusion is that as the number of sensors in the network grows, in-network processing will always use less energy than a centralized algorithm, while maintaining a desired level of accuracy.     

Geolocation in ad hoc networks using DS-CDMA and generalized successive interference cancellation

Channel estimation and distributed positioning algorithms are presented for geolocation in a wireless ad hoc network. The network uses a direct-sequence code-division multiple-access-based handshaking protocol, in which nodes receive multiple acknowledgment packets in response to a request-to-send waveform. Round-trip travel time (RTT) and angle-of-arrival (AOA) measurements are obtained using the generalized successive interference cancellation/matching pursuits (GSIC/MP) algorithm. The performance of GSIC/MP is evaluated via simulation and comparison to the Crame/spl acute/r-Rao bound. Position estimates are initialized using linearized least-squares and updated by an extended Kalman filter-based algorithm that includes measurement validation for nonline-of-sight error mitigation. The method is generalized for distributed estimation in sparsely connected networks: at each node, position estimates from connected nodes are incorporated via a fusion algorithm and updated using locally processed RTT/AOA measurements. Finally, comprehensive ad hoc network simulations are presented including channel ray tracing, RTT/AOA estimation and validation, and distributed positioning.     

Low computational complexity family of affine projection algorithms over adaptive distributed incremental networks

This paper presents the problem of distributed estimation in an incremental network based on the family of affine projection (AP) adaptive algorithms. The distributed selective partial update normalized least mean squares (dSPU-NLMS), the distributed SPU-AP algorithm (dSPU-APA), the distributed selective regressor APA (dSR-APA), the distributed dynamic selection of APA (dDS-APA), dSPU-SR-APA and dSPU-DS-APA are introduced in a unified way. These algorithms have low computational complexity feature and close convergence speed to ordinary distributed adaptive algorithms. In dSPU-NLMS and dSPU-APA, the weight coefficients are partially updated at each node during the adaptation. In dSR-APA, the optimum number of input regressors is selected during the weight coefficients update. The dynamic selection of input regressors is used in dDS-APA. dSPU-SR-APA and dSPU-DS-APA combine SPU with SR and DS approaches. In these algorithms, the weight coefficients are partially updated and the input regressors are optimally/dynamically selected at every iteration for each node. In addition, a unified approach for mean-square performance analysis of each individual node is presented. This approach can be used to establish a performance analysis of classical distributed adaptive algorithms as well. The theoretical expressions for stability bounds, transient, and steady-state performance analysis of various distributed APAs are introduced. The validity of the theoretical results and the good performance of dAPAs are demonstrated by several computer simulations.     

Fast adaptive optimization of weighted vector median filters

Weighted vector median (WVM) filters are effective tools for multichannel signal processing. To obtain the desired filtering behavior and characteristic, the WVM filter weights must be determined in an appropriate manner. In this paper, we first analyze previously defined approaches for WVM filter optimization and show their drawbacks related to derivative computation and vector direction information utilization. Based on this analysis, we propose two fast adaptive algorithms for WVM filter design. Proposed Algorithm I computes locally optimal weight changes at each iteration and updates the filter weights accordingly. This algorithm does not involve derivative computation, thus eliminating the instability caused by derivative approximations utilized in previous approaches. Proposed Algorithm II extends the results from established marginal weighted median optimization methods to the vector case by error metric generalization. Both algorithms can be applied to WVM filters using the L/sub p/ norm, while Algorithm I can operate on more general distance metrics. The presented simulation results show that both algorithms are effective, fast, and stable; they perform well under a wide range of circumstances.     

Design considerations for transceiver-limited elastic optical networks

The continuous increase of data traffic for present-day applications necessitates the development of Elastic Optical Networks (EONs). Significant advancements in efficient Routing and Spectrum Assignment (RSA) algorithms for EONs have been noticed in the recent past. These existing algorithms did not mention constraints on the number of transceivers per node in a network. However, for the planning of a realistic network, it is necessary to estimate the number of transceivers required at each node for the efficient operation of a network. Therefore, transceiver constraints should be taken into account while designing the RSA algorithms. In this paper, we present the impact of putting a limit to the number of transmitters and receivers available at each node of an EON. Moreover, the cost of a network heavily depends on the number of transceivers that each node in the network may offer. Hence, estimating the required number of transceivers per node in a network is vital to approximate the design cost of a network. Here, we present an Integer Linear Programming (ILP) formulation that includes the transceiver constraints and also develop a transceiver-aware heuristic algorithm for routing and spectrum assignment in EONs. Simulation results help us provide a proper design tool to estimate the number of transceivers per node in elastic optical networks.

     

Distributed algorithms for computing shortest pairs of disjointpaths

Distributed algorithms for finding two disjoint paths of minimum total length from each node to a destination are presented. The algorithms have both node-disjoint and link-disjoint versions and provide each node with information sufficient to forward data on the disjoint paths. It is shown that this problem can be reduced to the problem of finding a minimal shortest path from each node to the destination in a modified network, and a distributed algorithm on the original network that simulates a shortest-paths algorithm running on the modified network is presented. The algorithm has a smaller space complexity than any previous distributed algorithm for the same problem, and a method for forwarding packets is presented that does not require any additional space complexity. A synchronous implementation of the algorithm is also presented and studied     

Power-aware single- and multipath geographic routing in sensor networks

Nodes in a sensor network, operating on power limited batteries, must save power to minimize the need for battery replacement. We note that the range of transmission has a significant effect on the power consumption of both the transmitting node and listeners. This paper first presents a Geographical Power Efficient Routing (GPER) protocol for sensor networks. Each sensor node makes local decisions as to how far to transmit: therefore, the protocol is power efficient, localized, highly distributed, and scalable. In GPER, given a final destination, each node first establishes a subdestination within its maximum radio range. The node, however, may decide to relay the packet to this subdestination through an intermediary node or alter the subdestination if this will preserve power. Traditional deterministic geographic routing algorithms aim at achieving close to the shortest weighted paths. However, they normally stick to the same paths for the same source/destination pairs. This may conversely drain the nodes on these paths and result in short network life when the communication in the network is unevenly distributed. Thus, we further investigate a set of probabilistic multipath routing algorithms, which generate braided multipaths based only on local information. The algorithms have less communication and storage overhead than conventional on-demand multipath routing algorithms, while providing greater resilience to node failures. Simulations on NS2 show that GPER almost halves the power consumption in the network relative to alternative geographic routing algorithms. Furthermore, in situations where the communication tasks are non-uniformly distributed, probabilistic multipath routing contributes up to an additional 30% to network lifetime.     

Fast Distributed Algorithms for Computing Separable Functions

The problem of computing functions of values at the nodes in a network in a fully distributed manner, where nodes do not have unique identities and make decisions based only on local information, has applications in sensor, peer-to-peer, and ad hoc networks. The task of computing separable functions, which can be written as linear combinations of functions of individual variables, is studied in this context. Known iterative algorithms for averaging can be used to compute the normalized values of such functions, but these algorithms do not extend, in general, to the computation of the actual values of separable functions. The main contribution of this paper is the design of a distributed randomized algorithm for computing separable functions. The running time of the algorithm is shown to depend on the running time of a minimum computation algorithm used as a subroutine. Using a randomized gossip mechanism for minimum computation as the subroutine yields a complete fully distributed algorithm for computing separable functions. For a class of graphs with small spectral gap, such as grid graphs, the time used by the algorithm to compute averages is of a smaller order than the time required by a known iterative averaging scheme.     

Second Derivative Algorithms for Minimum Delay Distributed Routing in Networks

We propose a class of algorithms for finding an optimal quasi-static routing in a communication network. The algorithms are based on Gallager's method [1] and provide methods for iteratively updating the routing table entries of each node in a manner that guarantees convergence to a minimum delay routing. Their main feature is that they utilize second derivatives of the objective function and may be viewed as approximations to a constrained version of Newton's method. The use of second derivatives results in improved speed of convergence and automatic stepsize scaling with respect to level of traffic input. These advantages are of crucial importance for the practical implementation of the algorithm using distributed computation in an environment where input traffic statistics gradually change.     

Adaptive linearly constrained minimum variance beamforming for multiuser cooperative relaying using the kalman filter

In this paper, we consider a wireless communication scenario with multiple source-destination pairs communicating through several cooperative amplify-and-forward relay terminals. The relays are equipped with multiple antennas that receive the source signals and transmit them to the destination nodes. We develop two iterative relay beamforming algorithms that can be applied in real-time. In both algorithms, the relay beamforming matrices are jointly designed by minimizing the received power at all the destination nodes while preserving the desired signal at each destination. The first algorithm requires the existence of a local processing center that computes the beamforming coefficients of all the relays. In the second algorithm, each relay can compute its beamforming coefficients locally with the help of some common information that is broadcasted from the other relays. This is achieved at the expense of enforcing the desired signal preservation constraints non-cooperatively. We provide two extensions of the proposed algorithms that allow the relays to control their transmission power and to modify the quality of service provided to different sources. Simulation results are presented validating the ability of the proposed algorithms to perform their beamforming tasks efficiently and to track rapid changes in the operating environment.     

Distributed function calculation and consensus using linear iterative strategies

Given an arbitrary network of interconnected nodes, we develop and analyze a distributed strategy that enables a subset of the nodes to calculate any given function of the node values. Our scheme utilizes a linear iteration where, at each time-step, each node updates its value to be a weighted average of its own previous value and those of its neighbors. We show that this approach can be viewed as a linear dynamical system, with dynamics that are given by the weight matrix of the linear iteration, and with outputs for each node that are captured by the set of values that are available to that node at each time-step. In connected networks with time-invariant topologies, we use observability theory to show that after running the linear iteration for a finite number of time-steps with almost any choice of weight matrix, each node obtains enough information to calculate any arbitrary function of the initial node values. The problem of distributed consensus via linear iterations, where all nodes in the network calculate the same function, is treated as a special case of our approach. In particular, our scheme allows nodes in connected networks with time-invariant topologies to reach consensus on any arbitrary function of the initial node values in a finite number of steps for almost any choice of weight matrix.     

Joint Power and Temperature Aware Routing for implant wireless body area networks

In healthcare IoT, there is a vogueing need for better performing monitoring and reporting services of both medical and non-medical applications. Off late, the solutions are stemming from wireless body area networks (WBAN). Keen, fast, and reliable management of clinical information at every level of the network opens room for researchers to work on the network level of WBAN. Being in the era of Implant Medical Devices, the challenges are versatile. Obtaining the desired throughput, combating node heating, and improvement in energy efficiency are a few challenges. Interestingly, the heterogenous nature of nodes in a WBAN thrusts the next hop selection at the intra-WBAN level advancing into a non-persistent hard problem. To this, we present a Joint Power and Temperature Aware Routing (JPTAR) Scheme with two elements. First is an analytic hierarchy process–based next hop selection method that accommodates, link quality, residual energy, closeness to sink, and node heating for the process. To this an imperceptibly, low computation algorithm for received signal strength indicator (RSSI) estimation-based transmission power control is also added to ensure an optimized energy expenditure. Requisite elements of WBAN network management like QoS goals of emergency data and redundancy removal in transmissions are inherently part of the proposed work. The performance metrics like network lifetime, node temperature rise, throughput, end-to-end delay, and computation time are acquired under the worst-case scenario. The obtained results depict that the proposed JPTAR scheme outperforms state-of-the-art reactive multi-hop routing algorithms (MATTEMPT and SIMPLE).