A column generation based heuristic for sensor placement,activity scheduling and data routing in wireless sensor networks

A wireless sensor network is a network consisting of distributed autonomous electronic devices called sensors. In this work, we develop a mixed-integer linear programming model to maximize the network lifetime by optimally determining locations of sensors and sinks, sensor-to-sink data flows, and activity schedules of the deployed sensors subject to coverage, flow conservation, energy consumption and budget constraints. Since solving this model is difficult except for very small instances, we propose a heuristic method which works on a reformulation of the problem. In the first phase of this heuristic, the linear programming relaxation of the reformulation is solved by column generation. The second phase consists of constructing a feasible solution for the original problem using the columns obtained in the first phase. Computational experiments conducted on a set of test instances indicate that both the accuracy and the efficiency of the proposed heuristic is quite promising.     

Maximizing system lifetime in wireless sensor networks

One of the most critical issues in wireless sensor networks is represented by the limited availability of energy on network nodes; thus, making good use of energy is necessary to increase network lifetime. In this paper, we define network lifetime as the time spanning from the instant when the network starts functioning properly, i.e., satisfying the target level of coverage of the area of interest, until the same level of coverage cannot be guaranteed any more due to lack of energy in sensors. To maximize system lifetime, we propose to exploit sensor spatial redundancy by defining subsets of sensors active in different time periods, to allow sensors to save energy when inactive. Two approaches are presented to maximize network lifetime: the first one, based on column generation, must run in a centralized way, whereas the second one is based on a heuristic algorithm aiming at a distributed implementation. To assess their performance and provide guidance to network design, the two approaches are compared by varying several network parameters. The column generation based approach typically yields better solutions, but it may be difficult to implement in practice. Nevertheless it provides both a good benchmark against which heuristics may be compared and a modeling framework which can be extended to deal with additional features, such as reliability.     

On approximation of dominating tree in wireless sensor networks

We study the following problem: Given a weighted graph G = (V, E, w) with \({w: E \rightarrow \mathbb{Z}^+}\) , the dominating tree (DT) problem asks us to find a minimum total edge weight tree T such that for every \({v \in V}\) , v is either in T or adjacent to a vertex in T. To the best of our knowledge, this problem has not been addressed in the literature. Solving the DT problem can yield a routing backbone for broadcast protocols since (1) each node does not have to construct their own broadcast tree, (2) utilize the virtual backbone to reduce the message overhead, and (3) the weight of backbone representing the energy consumption is minimized. We prove the hardness of this problem, including the inapproximability result and present an approximation algorithm together with an efficient heuristic. Finally, we verify the effectiveness of our proposal through simulation.     

Real-time data gathering in sensor networks

Wireless sensor networks represent a new generation of real-time traffic communications and high data rate sensor applications, such as structural health monitoring and control. We study some problems related to data gathering in sensor networks when the sensors collect the sensed data about their environment and this information should be delivered to a collecting central Base Station. We prove that scheduling messages through the network to minimize the maximal delivery time with restrictions on the total idle time allowed is NP-hard. We also refer to a special case of linear network topology for which we present two polynomial time optimization algorithms: One is for minimizing the maximal lateness and maximal delay, while the other is for minimizing the number of tardy messages.     

Modelling and solving optimal placement problems in wireless sensor networks

In this work, the optimal sensor displacement problem in wireless sensor networks is addressed. It is assumed that a network, consisting of independent, collaborative and mobile nodes, is available. Starting from an initial configuration, the aim is to define a specific sensors displacement, which allows the network to achieve high performance, in terms of energy consumption and travelled distance. To mathematically represent the problem under study, different innovative optimization models are proposed and defined, by taking into account different performance objectives. An extensive computational phase is carried out in order to assess the behaviour of the developed models in terms of solution quality and computational effort. A comparison with distributed approaches is also given, by considering different scenarios.     

Modeling and optimization of energy efficient routing in wireless sensor networks

Wireless sensor networks (WSNs) have important applications in remote environmental monitoring and target tracking. The development of WSNs in recent years has been facilitated by the availability of sensors that are smaller, less expensive, and more intelligent. The design of a WSN depends significantly on its desired applications and must take into account factors such as the environment, the design objectives of the application, the associated costs, the necessary hardware, and any applicable system constraints. In this study, we propose mathematical models for a routing protocol (network design) under particular resource restrictions within a wireless sensor network. We consider two types of constraints: the distance between the linking sensors and the energy used by the sensors. The proposed models aim to identify energy-efficient paths that minimize the energy consumption of the network from the source sensor to the base station. The computational results show that the presented models can be used efficiently and applied to other network design contexts with resource restrictions (e.g., to multi-level supply chain networks).     

Desynchronization of large scale delayed neural networks

We consider a ring of identical neurons with delayed nearest neighborhood inhibitory interaction. Under general conditions, such a network has a slowly oscillatory synchronous periodic solution which is completely characterized by a scalar delay differential equation with negative feedback. Despite the fact that the slowly oscillatory periodic solution of the scalar equation is stable, we show that the associated synchronous solution is unstable if the size of the network is large.

     

Hybrid approximation for minimum-cost target coverage in wireless sensor networks

This paper presents a hybrid approximation scheme for the Max-SNP-complete minimum-cost target coverage problem in wireless sensor networks. LP-rounding and set-cover selection are polynomial-time approximations for this problem. Our hybrid scheme combines these two methods using a crafted convex combination. We show that the hybrid scheme with appropriately chosen coefficients produces much better approximations than either of the two methods used alone. We show that, through a large number of numerical experiments, the hybrid scheme never exceeds an approximation ratio of 1.14, providing up to 14.86% improvement over the best approximations previously known.     

Global dynamics and control of malicious signal transmission in wireless sensor networks

This paper studies the global dynamics of a discontinuous delayed model of malicious signal transmission in wireless sensor networks under the framework of differential inclusion. The local stability of two types of steady states are investigated for the discontinuous system by studying the corresponding characteristic equation. The sufficient conditions for the existence of two types of globally asymptotically stable steady states are obtained for the discontinuous system by using the comparison arguments method. Furthermore, the optimal control of the discontinuous system is investigated by using Pontryagin’s maximum principle. Numerical simulations of two examples are carried out to illustrate the main theoretical results. The obtained results can help us to better control and predict the spread of malicious signal transmission in wireless sensor networks.     

A branch and price algorithm for the minimum power multicasting problem in wireless sensor networks

The Minimum Power Multicast Problem arises in wireless sensor networks and consists in assigning a transmission power to each node of a network in such a way that the total power consumption over the network is minimized, while a source node is connected to a set of destination nodes, toward which a message has to be sent periodically. A new mixed integer programming model for the problem, based on paths, is presented. A practical exact algorithm based on column generation and branch and price is derived from this model. A comparison with state-of-the-art exact methods is presented, and it is shown that the new approach compares favorably to other algorithms when the number of destination nodes is moderate. Under this condition, the proposed method is able to solve previously unmanageable instances.     

Flexible composition and execution of large scale applications on distributed e-infrastructures

Computer simulation is finding a role in an increasing number of scientific disciplines, concomitant with the rise in available computing power. Marshalling this power facilitates new, more effective and different research than has been hitherto possible. Realizing this inevitably requires access to computational power beyond the desktop, making use of clusters, supercomputers, data repositories, networks and distributed aggregations of these resources. The use of diverse e-infrastructure brings with it the ability to perform distributed multiscale simulations. Accessing one such resource entails a number of usability and security problems; when multiple geographically distributed resources are involved, the difficulty is compounded. In this paper we present a solution, the Application Hosting Environment,³ which provides a Software as a Service layer on top of distributed e-infrastructure resources. We describe the performance and usability enhancements present in AHE version 3, and show how these have led to a high performance, easy to use gateway for computational scientists working in diverse application domains, from computational physics and chemistry, materials science to biology and biomedicine.     

Approximation algorithms for minimum broadcast schedule problem in wireless sensor networks

A wireless sensor network usually consists of a large number of sensor nodes deployed in a field. One of the major communication operations is to broadcast a message from one node to the rest of the others. In this paper, we adopt the conflict-free communication model and study how to compute a transmission schedule that determines when and where a node should forward the message so that all nodes could receive the message in minimum time. We give two approximation algorithms for this NP-hard problem that have better theoretically guaranteed performances than the existing algorithms. The proposed approach could be applied to some other similar problems.     

Approximation algorithm for minimum power partial multi-coverage in wireless sensor networks

Journal of Global Optimization - In this paper, we consider the wireless sensor network in which the power of each sensor is adjustable. Given a set of sensors and a set of targets, we study a...     

Key pre-distribution in a non-uniform rectangular grid for wireless sensor networks

A deterministic key pre-distribution scheme is proposed in the paper. The distribution of keys to the nodes precedes a virtual arrangement of the nodes into a non-uniform rectangular grid structure. Distribution of keys is based on projective planes and pairwise connectivity. With small memory requirements, the nodes induce a network which offers a trade-off between connectivity and resilience. The impact of resilience and connectivity can be controlled by choosing the number of rows and columns suitably. Another significant aspect of the proposed scheme is that the path between any two nodes is not unique, which leads to a well-connected network.