The occurrence of congestion has an extremely deleterious impact on the performance of Wireless Sensor Networks (WSNs). This article presents a novel protocol, named COALA (
), which aims to act both ...proactively, in order to avoid the creation of congestion in WSNs, and reactively, so as to mitigate the diffusion of upcoming congestion through alternative path routing. Its operation is based on the utilization of an accumulative cost function, which considers both static and dynamic metrics in order to send data through the paths that are less probable to be congested. COALA is validated through simulation tests, which exhibit its ability to achieve remarkable reduction of loss ratios, transmission delays and energy dissipation. Moreover, the appropriate adjustment of the weighting of the accumulative cost function enables the algorithm to adapt to the performance criteria of individual case scenarios.
Wireless Sensor Networks (WSNs) are considered to be among the most important scientific domains. Yet, the exploitation of WSNs suffers from the severe energy restrictions of their electronic ...components. For this reason there are numerous scientific methods that have been proposed aiming to achieve the extension of the lifetime of WSNs, either by energy saving or energy harvesting or through energy transfer. This study aims to analytically examine all of the existing hardware-based and algorithm-based mechanisms of this kind. The operating principles of 48 approaches are studied, their relative advantages and weaknesses are highlighted, open research issues are discussed, and resultant concluding remarks are drawn.
Transportation Network Companies employ dynamic pricing methods at periods of peak travel to incentivise driver participation and balance supply and demand for rides. Surge pricing multipliers are ...commonly used and are applied following demand and estimates of customer and driver trip valuations. Combinatorial double auctions have been identified as a suitable alternative, as they can achieve maximum social welfare in the allocation by relying on customers and drivers stating their valuations. A shortcoming of current models, however, is that they fail to account for the effects of trip detours that take place in shared trips and their impact on the accuracy of pricing estimates. To resolve this, we formulate a new shared-ride assignment and pricing algorithm using combinatorial double auctions. We demonstrate that this model is reduced to a maximum weighted independent set model, which is known to be APX-hard. A fast local search heuristic is also presented, which is capable of producing results that lie within 10% of the exact approach for practical implementations. Our proposed algorithm could be used as a fast and reliable assignment and pricing mechanism of ride-sharing requests to vehicles during peak travel times.
Ride-sourcing platforms often face imbalances in the demand and supply of rides across areas in their operating road-networks. As such, dynamic pricing methods have been used to mediate these demand ...asymmetries through surge price multipliers, thus incentivising higher driver participation in the market. However, the anticipated commercialisation of autonomous vehicles could transform the current ride-sourcing platforms to fleet operators. The absence of human drivers fosters the need for empty vehicle management to address any vehicle supply deficiencies. Proactive redistribution using integer programming and demand predictive models have been proposed in research to address this problem. A shortcoming of existing models, however, is that they ignore the market structure and underlying customer choice behaviour. As such, current models do not capture the real value of redistribution. To resolve this, we formulate the vehicle redistribution problem as a non-linear minimum cost flow problem which accounts for the relationship of supply and demand of rides, by assuming a customer discrete choice model and a market structure. We demonstrate that this model can have a convex domain, and we introduce an edge splitting algorithm to solve a transformed convex minimum cost flow problem for vehicle redistribution. By testing our model using simulation, we show that our redistribution algorithm can decrease wait times by more than 50%, increase profit up to 10% with less than 20% increase in vehicle mileage. Our findings outline that the value of redistribution is contingent on localised market structure and customer behaviour.
A typical wireless sensor network (WSN) contains wirelessly interconnected devices, called sensor nodes, which have sensing, processing, and communication abilities and are disseminated within an ...area of interest ...
Wireless Sensor Networks (WSNs) not only have a constantly increasing range of applications but also stimulate the amazing growth of 5G mobile communications and the Internet of Things (IoT). Yet, ...the lifetime of WSNs is restricted due to the severe energy limitations of their components. For this reason, the achievement of energy sustainability in WSNs is extremely important. Given that the greatest part of energy consumption in a WSN takes place during data routing, numerous research works are carried out in order to develop protocols for energy efficient routing. This article aims to clarify the most popular subdivision of this category of protocols i.e. the so-called hierarchical energy efficient routing protocols. Specifically, LEACH, which is considered to be the pioneer protocol of this kind, is studied along with 18 of its descendant protocols. A theoretical comparison of these protocols in terms of various metrics is also performed. Additionally, the performance of LEACH is compared with that of 3 descendant protocols through simulation tests that are carried out. Finally, a discussion takes place and concluding remarks are drawn.
Network Pollution Games Anastasiadis, Eleftherios; Deng, Xiaotie; Krysta, Piotr ...
Algorithmica,
01/2019, Volume:
81, Issue:
1
Journal Article
Peer reviewed
Open access
The problem of pollution control has been mainly studied in the environmental economics literature where the methodology of game theory is applied for the pollution control. To the best of our ...knowledge this is the first time this problem is studied from the computational point of view. We introduce a new network model for pollution control and present two applications of this model. On a high level, our model comprises a graph whose nodes represent the agents, which can be thought of as the sources of pollution in the network. The edges between agents represent the effect of spread of pollution. The government who is the regulator, is responsible for the maximization of the social welfare and sets bounds on the levels of emitted pollution in both local areas as well as globally in the whole network. We first prove that the above optimization problem is NP-hard even on some special cases of graphs such as trees. We then turn our attention on the classes of trees and planar graphs which model realistic scenarios of the emitted pollution in water and air, respectively. We derive approximation algorithms for these two kinds of networks and provide deterministic truthful and truthful in expectation mechanisms. In some settings of the problem that we study, we achieve the best possible approximation results under standard complexity theoretic assumptions. Our approximation algorithm on planar graphs is obtained by a novel decomposition technique to deal with constraints on vertices. We note that no known planar decomposition techniques can be used here and our technique can be of independent interest. For trees we design a two level dynamic programming approach to obtain an FPTAS. This approach is crucial to deal with the global pollution quota constraint. It uses a special multiple choice, multi-dimensional knapsack problem where coefficients of all constraints except one are bounded by a polynomial of the input size. We furthermore derive truthful in expectation mechanisms on general networks with bounded degree.
The uptake of Electric Vehicles (EVs) is rapidly changing the landscape of urban mobility services. Transportation Network Companies (TNCs) have been following this trend by increasing the number of ...EVs in their fleets. Recently, major TNCs have explored the prospect of establishing privately owned charging facilities that will enable faster and more economic charging. Given the scale and complexity of TNC operations, such decisions need to consider both the requirements of TNCs and local planning regulations. Therefore, an optimisation approach is presented to model the placement of CSs with the objective of minimising the empty time travelled to the nearest CS for recharging as well as the installation cost. An agent based simulation model has been set in the area of Chicago to derive the recharging spots of the TNC vehicles, and in turn derive the charging demand. A mathematical formulation for the resulting optimisation problem is provided alongside a genetic algorithm that can produce solutions for large problem instances. Our results refer to a representative set of the total data for Chicago and indicate that nearly 180 CSs need to be installed to handle the demand of a TNC fleet of 3000 vehicles.
We study approximation algorithms and design truthful mechanisms for optimization problems in networks that have direct applications in smart cities and urban planning. We present new models and new ...techniques which could be of independent interest. More specifically, in Chapter 2 we introduce a new model for pollution control and propose two applications of this model. This is the first time this problem is studied from the computational perspective. The network is represented by a graph where nodes are the pollutants and edges between pollutants represent the effect of spread of pollution. The government sets bounds on the levels of emitted pollution in both local areas and the whole network. We mainly study the classes of planar graphs and trees which model air and water pollution and design truthful approximate mechanisms.In Chapter 3 we introduce a new mechanism design model for a new model for the budgeted maximum lifetime coverage (BMLC) in wireless sensor networks (wsns). BMLC generalizes the known maximum lifetime coverage problem to the case where sensors are owned by selfish agents, where each agent has a private cost per unit time of how much to be paid for deploying his sensor. We introduce a random instances model for BMLC and design a novel approximate mechanism by reducing BMLC to the fractional knapsack which is truthful under some technical assumptions. For a closely related minimum coverage problem in wsns on unit disk graphs, we generalize a recent PTAS for this problem to obtain a truthful PTAS for the problem where sensors’ costs are agents’ private data.In Chapter 4 we study approximation algorithms which are based on the primal dual method for network connectivity problems. We then prove that these algorithms are monotone and thus can lead to truthful mechanisms.Finally in Chapter 5 we study the problem of facility location on the real line under non utilitarian objective functions. We extend previous models and derive inapproximability bounds for deterministic and randomized truthful mechanisms. As a byproduct we show that the same approximation guarantees hold for the social utility objective.
PDF
