Collision-free path coloring with application to minimum-delay gathering in sensor networks

Efficient data gathering is an important challenge in sensor networks. In this paper we address the problem of gathering sensed data to the sink of a sensor network minimizing the time to complete the process. We present optimal time data gathering algorithms for any sensor network topology, in the half-duplex with directional antennas model, when each sensor has one data packet to be gathered and merging of packets is not allowed at intermediate nodes. Our results improve on existing approximation algorithms. We approach the gathering problem by obtaining optimal solutions to a path coloring problem in graphs.     

A self-tuning heuristic for the design of communication networks

This paper addresses the design of communication networks that has a large application area. The problem is to design a minimum cost network subject to a given reliability level. Complexity of the problem is twofold: (1) finding a minimum-cost network topology that every pair of nodes can communicate with each other and (2) computing overall reliability to provide the reliability constraint. Over the last two decades, metaheuristic algorithms have been widely applied to solve this problem due to its NP-hardness. In this study, a self-tuning heuristic (STH), which is a new approach free from parameter tuning, is applied to the design of communication networks. Extensive computational results confirm that STH generates superior solutions to the problem in comparison to some well-known local search metaheuristics, and also more sophisticated metaheuristics proposed in the literature. The practical advantage of STH lies in both its effectiveness and simplicity in application to the design problem.     

Routing-efficient CDS construction in Disk-Containment Graphs

In wireless networks, Connected Dominating Sets (CDSs) are widely used as virtual backbones for communications. On one hand, reducing the backbone size will reduce the maintenance overhead. So how to minimize the CDS size is a critical issue. On the other hand, when evaluating the performance of a wireless network, the hop distance between two communication nodes, which reflect the energy consumption and response delay, is of great importance. Hence how to minimize the routing cost is also a key problem for constructing the network virtual backbone. In this paper, we study the problem of constructing applicable CDS in wireless networks in terms of size and routing cost. We formulate a wireless network as a Disk-Containment Graph (DCG), which is a generalization of the Unit-Disk Graph (UDG), and we develop an efficient algorithm to construct CDS in such kind of graphs. The algorithm contains two parts and is flexible to balance the performance between the two metrics. We also analyze the algorithm theoretically. It is shown that our algorithm has provable performance in minimizing the CDS size and reducing the communication distance for routing.     

The convex hull of two core capacitated network design problems

The network loading problem (NLP) is a specialized capacitated network design problem in which prescribed point-to-point demand between various pairs of nodes of a network must be met by installing (loading) a capacitated facility. We can load any number of units of the facility on each of the arcs at a specified arc dependent cost. The problem is to determine the number of facilities to be loaded on the arcs that will satisfy the given demand at minimum cost.This paper studies two core subproblems of the NLP. The first problem, motivated by a Lagrangian relaxation approach for solving the problem, considers a multiple commodity, single arc capacitated network design problem. The second problem is a three node network; this specialized network arises in larger networks if we aggregate nodes. In both cases, we develop families of facets and completely characterize the convex hull of feasible solutions to the integer programming formulation of the problems. These results in turn strengthen the formulation of the NLP.Research of this author was supported in part by a Faculty Grant from the Katz Graduate School of Business, University of Pittsburgh.     

A cross entropy approach to design of reliable networks

One of the most important parameters determining the performance of communication networks is network reliability. The network reliability strongly depends on not only topological layout of the communication networks but also reliability and availability of the communication facilities. The selection of optimal network topology is an NP-hard problem so that computation time of enumeration-based methods grows exponentially with network size. This paper presents a new solution approach based on cross-entropy method, called NCE, to design of communication networks. The design problem is to find a network topology with minimum cost such that all-terminal reliability is not less than a given level of reliability. To investigate the effectiveness of the proposed NCE, comparisons with other heuristic approaches given in the literature for the design problem are carried out in a three-stage experimental study. Computational results show that NCE is an effective heuristic approach to design of reliable networks.     

A survivable design of last mile communication networks using multi-objective genetic algorithms

In this paper, we are interested in the survivable network design problem (SNDP) for last mile communication networks called (L-SNDP). Given a connected, weighted, undirected graph \(\mathrm{{G}} = (\mathrm{V, E})\); a set of infrastructure nodes and a set of customers C including two customer types where customers in the subset C1 require a single connection (type-1) and customers in the subset C2 need to be redundantly connected (type-2). The aim is to seek a sub-graph of G with the smallest weight in which all customers are connected to infrastructure nodes and the connections are protected against failures. This is a NP-hard problem and it has been solved only with the objective of minimizing the network cost. In this paper, we introduce a new multi-objective approach to solve L-SNDP called ML-SNDP. These objectives are to minimize the network cost (total cost) and to minimize the maximal amount of sharing links between connections. Results of computational experiments reported show the efficiency of our proposal.     

A distributed approximation algorithm for the bottleneck connected dominating set problem

Some of the most popular routing protocols for wireless sensor networks require a virtual backbone for efficient communication between the sensors. Connected dominating sets (CDS) have been studied as a method of choosing nodes to be in the backbone. The traditional approach is to assume that the transmission range of each node is given and to minimize the number of nodes in the CDS representing the backbone. A recently introduced alternative strategy is based on the concept of k-bottleneck connected dominating set (k-BCDS), which, given a positive integer k, minimizes the transmission range of the nodes that ensures a CDS of size k exists in the network. This paper provides a 6-approximate distributed algorithm for the k-BCDS problem. The results of empirical evaluation of the proposed algorithm are also included.     

Generalized steiner problem in series-parallel networks

The generalized Steiner problem (GSP) is concerned with the determination of a minimum cost subnetwork of a given network where some (not necessarily all) vertices satisfy certain pairwise (vertex or edge) connectivity requirements. The GSP has applications to the design of water and electricity supply networks, communication networks and other large-scale systems where connectivity requirements ensure the communication between the selected vertices when some vertices and/or edges can become inoperational due to scheduled maintenance, error, or overload. The GSP is known to be NP-complete. In this paper we show that if the subnetwork is required to be respectively biconnected and edge-biconnected, and the underlying network is series-parallel, both problems can be solved in linear time.     

The Infinite-Dimensional Optimal Filtering Problem with Mobile and Stationary Sensor Networks

In this article, we introduce a framework to address filtering and smoothing with mobile sensor networks for distributed parameter systems. The main problem is formulated as the minimization of a functional involving the trace of the solution of a Riccati integral equation with constraints given by the trajectory of the sensor network. We prove existence and develop approximation of the solution to the Riccati equation in certain trace-class spaces. We also consider the corresponding optimization problem. Finally, we employ a Galerkin approximation scheme and implement a descent algorithm to compute optimal trajectories of the sensor network. Numerical examples are given for both stationary and moving sensor networks.     

Routeing in a Network with Multi-Class Links

Consider a communication network with certain nodes and different types of links. In addition to the normal link cost, a transformation cost is charged if the incoming link and the outgoing link are of different types. An optimal routeing from a given node to its destination node is sought. The major difficulty in handling this problem is that the principle of optimality does not hold. A model with node separation is built to overcome this difficulty. By using the new model, the original routeing problem is no more than a shortest-path problem. Hence, we can implement this model to current electronic switching machines.     

Generalized steiner problem in outerplanar networks

The generalized Steiner problem (GSP) is concerned with the determination of a minimum cost subnetwork of a given network where some (not necessarily all) vertices satisfy certain pairwise (vertex or edge) connectivity requirements.The GSP has applications to the design of water and electricity supply networks, communication networks and other large-scale systems where connectivity requirements ensure the communication between the selected vertices when some vertices and/or edges can become inoperational due to scheduled maintenance, error, or overload.The GSP is known to beNP-complete. In this paper we show that if the subnetwork is required to be biconnected or respectively edge-biconnected, and the underlying network is outerplanar, the GSP can be solved in linear time.     

On Cost Allocation in Hub-Like Networks

We consider telecommunication network design in which each pair of nodes can communicate via a direct link and the communication flow can be delivered through any path in the network. The cost of flow through each link is discounted if and only if the amount of flow exceeds a certain threshold. This exploitation of economies of scale encourages the concentration of flows and use of relatively small number of links. We will call such networks hub-like networks. The cost of services delivered through a hub-like network is distributed among its users who may be individuals or organizations with possibly conflicting interests. The cooperation of these users is essential for the exploitation of economies of scale. Consequently, there is a need to find a fair distribution of the cost of providing the service among users of such network. In order to describe this cost allocation problem we formulate the associated cooperative game, to be referred to as the hub-like game. Special attention is paid to users' contribution to economies of scale. We then demonstrate that certain cost allocation solutions (the core and the nucleolus of the hub-like game), which provide users with the incentive to cooperate, can be efficiently characterized.     

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.     

Genetic Algorithm for Network Cost Minimization Using Threshold Based Discounting

We present a genetic algorithm for heuristically solving a cost minimization problem applied to communication networks with threshold based discounting. The network model assumes that every two nodes can communicate and offers incentives to combine of from different sources. Namely, there is a prescribed threshold on every link, and if the total of on a link is greater than the threshold, the cost of this of is discounted by a factor. A heuristic algorithm based on genetic strategy is developed and applied to a benchmark set of problems. The results are compared with former branch and bound results using the CPLEX(r)solver. For larger data instances we were able to obtain improved solutions using less CPU time, confirming the effectiveness of our heuristic approach.     

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.     

Topology design for on-demand dual-path routing in wireless networks

One way to achieve reliability with low-latency is through multi-path routing and transport protocols that build redundant delivery channels (or data paths) to reduce end-to-end packet losses and retransmissions. However, the applicability and effectiveness of such protocols are limited by the topological constraints of the underlying communication infrastructure. Multiple data delivery paths can only be constructed over networks that are capable of supporting multiple paths. In mission-critical wireless networks, the underlying network topology is directly affected by the terrain, location and environmental interferences, however the settings of the wireless radios at each node can be properly configured to compensate for these effects for multi-path support. In this work we investigate optimization models for topology designs that enable end-to-end dual-path support on a distributed wireless sensor network. We consider the case of a fixed sensor network with isotropic antennas, where the control variable for topology management is the transmission power on network nodes. For optimization modeling, the network metrics of relevance are coverage, robustness and power utilization. The optimization models proposed in this work eliminate some of the typical assumptions made in the pertinent network design literature that are too strong in this application context.     

A robust optimization approach for multicast network coding under uncertain link costs

Network coding is a technique that can be used to improve the performance of communication networks by performing mathematical operations at intermediate nodes. An important problem in coding theory is that of finding an optimal coding subgraph for delivering network data from a source node throughout intermediate nodes to a set of destination nodes with the minimum transmission cost. However, in many real applications, it can be difficult to determine exact values or specific probability distributions of link costs. Establishing minimum-cost multicast connections based on erroneous link costs might exhibit poor performance when implemented. This paper considers the problem of minimum-cost multicast using network coding under uncertain link costs. We propose a robust optimization approach to obtain solutions that protect the system against the worst-case value of the uncertainty in a prespecified set. The simulation results show that a robust solution provides significant improvement in worst-case performance while incurring a small loss in optimality for specific instances of the uncertainty.     

Metaheuristic hybridizations for the regenerator placement and dimensioning problem in sub-wavelength switching optical networks

Physical layer impairments severely limit the reach and capacity of optical systems, thereby hampering the deployment of transparent optical networks (i.e., no electrical signal regenerators are required). Besides, the high cost and power-consumption of regeneration devices makes it unaffordable for network operators to consider the opaque architecture (i.e., regeneration is available at every network node). In this context, translucent architectures (i.e., regeneration is only available at selected nodes) have emerged as the most promising short term solution to decrease costs and energy consumption in optical backbone networks. Concurrently, the coarse granularity and inflexibility of legacy optical technologies have re-fostered great interest in sub-wavelength switching optical networks, which introduce optical switching in the time domain so as to further improve resources utilization. In these networks, the complex regenerator placement and dimensioning problem emerges. In short, this problem aims at minimizing the number of electrical regenerators deployed in the network. To tackle it, in this paper both a greedy randomized adaptive search procedure and a biased random-key genetic algorithm are developed. Further, we enhance their performance by introducing both path-relinking and variable neighborhood descent as effective intensification procedures. The resulting hybridizations are compared among each other as well as against results from optimal and heuristic mixed integer linear programming formulations. Illustrative results over a broad range of network scenarios show that the biased random-key genetic algorithm working in conjunction with these two intensification mechanisms represents a compelling network planning algorithm for the design of future sub-wavelength optical networks.     

Exact approaches for lifetime maximization in connectivity constrained wireless multi-role sensor networks

In this paper, we consider the duty scheduling of sensor activities in wireless sensor networks to maximize the lifetime. We address full target coverage problems contemplating sensors used for sensing data and transmit it to the base station through multi-hop communication as well as sensors used only for communication purposes. Subsets of sensors (also called covers) are generated. Those covers are able to satisfy the coverage requirements as well as the connection to the base station. Thus, maximum lifetime can be obtained by identifying the optimal covers and allocate them an operation time. The problem is solved through a column generation approach decomposed in a master problem used to allocate the optimal time interval during which covers are used and in a pricing subproblem used to identify the covers leading to maximum lifetime. Additionally, Branch-and-Cut based on Benders’ decomposition and constraint programming approaches are used to solve the pricing subproblem. The approach is tested on randomly generated instances. The computational results demonstrate the efficiency of the proposed approach to solve the maximum network lifetime problem in wireless sensor networks with up to 500 sensors.     

Stable network topologies using the notion of covering

An alternative perspective to evaluate networks and network evolution is introduced, based on the notion of covering. For a particular node in a network covering captures the idea of being outperformed by another node in terms of, for example, visibility and possibility of information gathering. In this paper, we focus on networks where these subdued network positions do not exist. We call these networks stable. Within this set we identify the minimal stable networks, which frequently have a ‘bubble-like’ structure. Severing a link in such a network results in at least one of the nodes being covered. In a minimal stable network therefore all nodes cooperate to avoid that one of the nodes ends up in a subdued position. Our results can be applied to, for example, the design of (covert) communication networks and the dynamics of social and information networks.