Optimization of the capacity of wireless mesh networks

This is a summary of the authors PhD thesis supervised by Hervé Rivano and defended on 29 October 2009 at the Université de Nice-Sophia Antipolis. The thesis is written in French and is available from . This work deals with the optimization of the capacity of wireless mesh networks, defined as the throughput offered to each flow. We develop optimization models integrating the cross-layer characteristics of radio communications. The joint routing and scheduling is studied and solved using column generation. A linear formulation focusing on the transport capacity available on the network cuts is derived. We prove the equivalence of the models, and adapt the resolution method into a cross line and column generation process. Thorough tests, a contention area located around the gateways which constraints the capacity is highlighted. These results are applied to a quantitative study of the effects of acknowledgments on the capacity. Finally, a stability study of a protocol routing a traffic injected arbitrarily is investigated.     

Efficient and fair routing for mesh networks

Inspired by the One Laptop Per Child project, we consider mesh networks that connect devices that cannot recharge their batteries easily. We study how the mesh should retransmit information to make use of the energy stored in each of the nodes effectively. The solution that minimizes the total energy spent by the whole network may be very unfair to some nodes because they bear a disproportionate burden of the traffic. A Nash equilibrium—achieved when nodes minimize the energy they spend—does not model the situation well because, as retransmissions consume battery without increasing the node’s utility, it predicts that nodes refuse to participate. Actually, there are wireless communication protocols, peer-to-peer networks and other systems that provide incentives or impose penalties to encourage nodes to be active and to participate. We explicitly aim at the solution that minimizes the total energy spent by nodes among those that satisfy a fairness constraint. Although this does not guarantee that the solution is at equilibrium, nodes do not have a big incentive to deviate from the proposed solution since they do not view the situation as extremely unfair to them. This is consistent with the recommendation of Beccaria and Bolelli (Proceedings of the 3rd IEEE Vehicle Navigation & Information Systems Conference, pp. 117–126, Oslo, 1992) who proposed to optimize social welfare keeping user needs as constraints. We propose a distributed and online routing algorithm and compare it to an offline, centralized approach. The centralized approach, besides being unrealistic in terms of information requirements, is also NP-hard to solve. For both reasons, we focus on the former and evaluate it by conducting an extensive set of computational experiments that evaluate the efficiency and fairness achieved by our algorithm.     

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.     

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.     

Hierarchical routing over dynamic wireless networks

The topology of a mobile wireless network changes over time. Maintaining routes between all nodes requires the continuous transmission of control information, which consumes precious power and bandwidth resources. Many routing protocols have been developed, trading off control overhead and route quality. In this paper, we ask whether there exist low‐overhead schemes that produce low‐stretch routes, even in large networks where all the nodes are mobile. We present a scheme that maintains a hierarchical structure within which constant‐stretch routes can be efficiently computed between every pair of nodes. The scheme rebuilds each level of the hierarchy periodically, at a rate that decreases exponentially with the level of the hierarchy. We prove that this scheme achieves constant stretch under a mild smoothness condition on the nodal mobility processes. Furthermore, we prove tight bounds for the network‐wide control overhead under the additional assumption of the connectivity graph forming a doubling metric space. Specifically, we show that for a connectivity model combining the random geometric graph with obstacles, constant‐stretch routes can be maintained with a total overhead of bits of control information per time unit. © 2015 Wiley Periodicals, Inc. Random Struct. Alg., 47, 669–709, 2015     

Design of optimal utility of wireless rechargeable sensor networks via joint spatiotemporal scheduling

In wireless rechargeable sensor networks, how to optimize energy resources for maximizing the sensor data is a challenging problem. In this paper, mobile charging vehicle scheduling, sensor charging time splitting and rate control with battery capacity constraints are considered together to maximize network utility. However, they are considered independently in exist works even though these problems are interdependent. In order to improve network performance through collaborative optimization of three problems, a joint optimization problem is formulated firstly. Then, a multistage approach is developed to jointly optimize the three subproblems iteratively. Furthermore, an accelerated distributed algorithm is integrated to improve the convergence speed of rate control. The results of extended experiments demonstrate that proposed approach can obtain higher network utility and charging efficiency compared to other charging scheduling methods.     

Approximation for a scheduling problem with application in wireless networks

A network of many sensors and a base station that are deployed over a region is considered. Each sensor has a transmission range, an interference range and a carrier sensing range, which are r, αr and βr, respectively. In this paper, we study the minimum latency conflict-aware many-to-one data aggregation scheduling problem: Given locations of sensors along with a base station, a subset of all sensors, and parameters r, α and β, to find a schedule in which the data of each sensor in the subset can be transmitted to the base station with no conflicts, such that the latency is minimized. We designe an algorithm based on maximal independent sets, which has a latency bound of (a + 19b)R + Δb ? a + 5 time slots, where a and b are two constant integers relying on α and β, Δ is the maximum degree of network topology, and R is the trivial lower bound of latency. Here Δ contributes to an additive factor instead of a multiplicative one, thus our algorithm is nearly a constant (a + 19b)-ratio.     

Adaptive energy efficient sensor scheduling for wireless sensor networks

In this paper, we consider an adaptive energy efficient sensor scheduling mechanism. We consider a wireless sensor network where the sink sends queries form time to time, and sensors are equipped with one or more sensing components. Our goal is to design an adaptive sensor scheduling mechanism to choose sets of active sensors to work alternatively such that different types of queries are served, the global connectivity requirements can be met, and network lifetime is maximized. A connected dominating set (CDS) based localized mechanism is proposed. Initially, a basic backbone is constructed, then when a query is issued, new sensors are activated locally such that to meet the requirements of the query and global connectivity. When a query expires, some sensors return to sleep and the CDS is restored. Our simulation results show that the solution is effective and it improved network lifetime.     

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).     

Dynamic conditional value-at-risk model for routing and scheduling of hazardous material transportation networks

This paper illustrates a dynamic model of conditional value-at-risk (CVaR) measure for risk assessment and mitigation of hazardous material transportation in supply chain networks. The well-established market risk measure, CVaR, which is commonly used by financial institutions for portfolio optimizations, is investigated. In contrast to previous works, we consider CVaR as the main objective in the optimization of hazardous material (hazmat) transportation network. In addition to CVaR minimization and route planning of a supply chain network, the time scheduling of hazmat shipments is imposed and considered in the present study. Pertaining to the general dynamic risk model, we analyzed several scenarios involving a variety of hazmats and time schedules with respect to optimal route selection and CVaR minimization. A solution algorithm is then proposed for solving the model, with verifications made using numerical examples and sensitivity analysis.     

Optimal scheduling and power allocation in wireless networks with heavy traffic

This paper addresses the problem of joint transmit power allocation and time slot scheduling in a wireless communication system with time varying traffic. The system is handled by a single base station transmitting over time varying channels. This may be the case in practice of a hybrid TDMA-CDMA (Time Division Multiple Access-Code Division Multiple Access) system. The operating time horizon is divided into time slots; a fixed amount of power is available at each time slot. The users share each time slot and the power available at this time slot with the objective of minimizing the expected total queue length. The problem is reformulated, via a heavy traffic approximation, as the optimal control of a reflected diffusion in the positive orthant. We establish a closed form solution for the obtained control problem. The main feature that makes it possible is an astute choice of some auxiliary weighting matrices in the cost rate. The proposed solution relies also on the knowledge of the covariance matrix of the non-standard multi-dimensional Wiener process which is the driving process in the reflected diffusion. We then compute this covariance matrix given the stationary distribution of the multi-dimensional channel process. Further stochastic analysis is provided: the cost variance, and the Fokker–Planck equation for the distribution density of the queue length.     

Mixed integer formulations for a routing problem with information collection in wireless networks

We study a routing-collecting problem where a system of stations is considered. A vehicle is responsible for collecting information generated continuously in the stations and to deliver it to a base station. The objective is to determine the vehicle route and the collection operations, both physical and wireless, in order to maximize the amount of information collected during a time horizon. Three mixed integer programming models are introduced and a computational study is reported to compare the performance of a solver based on each one of the models.     

Improved algorithm for broadcast scheduling of minimal latency in wireless ad hoc networks

A wide range of applications for wireless ad hoc networks are time-critical and impose stringent requirement on the communication latency. One of the key communication operations is to broadcast a message from a source node. This paper studies the minimum latency broadcast scheduling problem in wireless ad hoc networks under collision-free transmission model. The previously best known algorithm for this NP-hard problem produces a broadcast schedule whose latency is at least 648（rmax/rmin）^2 times that of the optimal schedule, where rmax and rmin are the maximum and minimum transmission ranges of nodes in a network, respectively. We significantly improve this result by proposing a new scheduling algorithm whose approximation performance ratio is at most （1 ＋ 2rmax/rmin）^2＋32, Moreover, under the proposed scheduling each node just needs to forward a message at most once.     

Optimal placement,scheduling, and routing to maximize lifetime in sensor networks

A wireless sensor network is a network consisting of distributed autonomouselectronic devices called sensors. Sensors have limited energy and capabilityfor sensing, data processing, and communicating, but they can collectivelybehave to provide an effective network that monitors an area and transmitinformation to gateway nodes or sinks, either directly or through other sensornodes. In most applications the network must operate for long periods of time,so the available energy resources of the sensors must be managed efficiently. Inthis paper, we first develop a mixed integer linear programming model tomaximize network lifetime by optimally determining locations of sensors andsinks, activity schedules of deployed sensors, and data flow routes from sensorsto sinks over a finite planning horizon subject to coverage, flow conservation,energy consumption, and budget constraints. Unfortunately, it is difficult tosolve this model exactly even for small instances. Therefore, we propose twoapproximate solution methods: a Lagrangean heuristic and a two-stage heuristicin which sensors are deployed and an activity schedule is found in the firststage, whereas sinks are located and sensor-to-sink data flow routes aredetermined in the second stage. Computational experiments performed on varioustest instances indicate that the Lagrangean heuristic is both efficient andaccurate and also outperforms the two-stage heuristic.     

Truck routing and scheduling

The problem is part of a complex software solution for truck itinerary construction for one of the largest public road transportation companies in the EU. In practice a minor improvement on the operational cost per tour can decide whether a freight services company is profitable or not. Thus the optimization of routes has key importance in the operation of such companies. Given an initial location and an asset state one must be able to calculate a cost optimal itinerary containing all Point of Interests. Such an itinerary is an executable plan which exactly specifies the location and activity of an asset during the whole timespan of the itinerary. If parking places and gas stations are included in the planning then it is NP hard to find an optimal solution. This means that for long range tours an approximately optimal solution for refueling has to be given within an acceptable running time. Also the corridoring of the trucks is an important problem so that we try to optimize the performance, hence tours cannot be recalculated at each data arrival. The vehicle assignment part of this work is already finished and applied with very good results. The remaining part is subject of an ongoing research which started at January 2014. The company started to apply and test our product in the beginning of 2015 under increased human supervision. As a consequence of the project a large cost saving is anticipated by the company.     

City-courier routing and scheduling problems

This research seeks to propose innovative routing and scheduling strategies to help city couriers reduce operating costs and enhance service level. The strategies are realized by constructing a new type of routing and scheduling problem. The problem directly takes into account the inherent physical and operating constraints associated with riding in city distribution networks, which makes the problem involve multiple objectives and visiting specified nodes and arcs. Through network transformations, this study first formulates the city-courier routing and scheduling problem as a multi-objective multiple traveling salesman problem with strict time windows (MOMTSPSTW) that is NP-hard and new to the literature, and then proposes a multi-objective Scatter Search framework that seeks to find the set of Pareto-optimal solutions to the problem. Various new and improved sub-procedures are embedded in the solution framework. This is followed by an empirical study that shows and analyzes the results of applying the proposed method to a real-life city-courier routing and scheduling problem.     

Computing inter-site distances for routing and scheduling problems

Routing and scheduling problems have received considerable attention in the literature in terms of model building and algorithm development. On these fronts, progress has been substantial. However, one often neglected (yet critical) aspect concerning the use of these models and algorithms is their data requirements. In particular, the distance matrix yielding the shortest distance between each pair of sites (nodes) represents a major portion of the data required by all such problems. Yet, such data are seldom available with the degree of accuracy desired and often are not available at all.This paper describes an efficient method for obtaining this distance matrix that is based on the underlying road structure for the geographic region in question. Thus, the distances obtained reflect ‘actual’ distances. Finally, the paper presents some brief computational experience and discusses an implementation concerning the routing of environmental inspectors in the state of Pennsylvania.     

Maximizing lifetime of a wireless sensor network via joint optimizing sink placement and sensor-to-sink routing

Wireless sensor networks typically contain hundreds of sensors. The sensors collect data and relay it to sinks through single hop or multiple hop paths. Sink deployment significantly influences the performance of a network. Since the energy capacity of each sensor is limited, optimizing sink deployment and sensor-to-sink routing is crucial. In this paper, this problem is modeled as a mixed integer optimization problem. Then, a novel layer-based diffusion particle swarm optimization method is proposed to solve this large-scaled optimization problem. In particular, two sensor-to-sink binding algorithms are combined as inner layer optimization to evaluate the fitness values of the solutions. Compared to existing methods that the sinks are selected from candidate positions, our method can achieve better performance since they can be placed freely within a geometrical plane. Several numerical examples are used to validate and demonstrate the performance of our method. The reported numerical results show that our method is superior to those existing. Furthermore, our method has good scalability which can be used to deploy a large-scaled sensor network.     

Multifleet routing and multistop flight scheduling for schedule perturbation

Efficient and effective incidental scheduling techniques for schedule perturbation are essential to an airline carrier's operations. This research aims at developing a framework to assist carriers in fleet routing and flight scheduling for schedule perturbations in the operations of multifleet and multistop flights. The framework is based on a basic multifleet schedule perturbation model constructed as a timespace network from which strategic models are developed to research incidental scheduling. These network models are formulated as multiple commodity network flow problems. Lagrangian relaxation with subgradient methods accompanied by the network simplex method, a Lagrangian heuristic and a modified subgradient method are developed to solve the problems. A case study regarding the international operations of a major Taiwan airline carrier is presented.