Search

The power industry is in the early stages of a fundamental change, driving the integration of energy, communications, and information technologies into one intelligent utility network, known as the smart grid. This paper investigates data traffic management in smart grid networks, in which huge volumes of data produced by advanced meters cannot be fully delivered to utility data centers due to limited bandwidth. To develop a solution for optimizing traffic flow, we exploit a particular characteristic of this network—power-related applications can benefit from different levels of data quality along the path to the final destination. We thus handle congestion by performing intelligent quality-aware volume reduction of the flows within the network. Our optimization problem is that of computing for each flow the amount of volume reductions in different locations, so as to maximize overall revenue. We address both an off-line scenario, in which all flows are known beforehand, and an online framework, in which new flows can be generated during system operation. For the off-line case, we propose an efficient, near-optimal solution, while for the online case, we derive almost tight polylogarithmic upper and lower bounds on the competitive ratio. We also consider a more restricted dynamic setting, for which we demonstrate how to compute an optimal solution. This paper initiates a rigorous treatment of cross-layer traffic management in the smart grid. [ABSTRACT FROM PUBLISHER]

A major problem in wireless networks is coping with limited resources, such as bandwidth and energy. These issues become a major algorithmic challenge in view of the dynamic nature of the wireless domain. We consider in this paper the single-transmitter power assignment problem under time-varying channels, with the objective of maximizing the data throughput. It is assumed that the transmitter has a limited power budget, to be sequentially divided during the lifetime of the battery. We deviate from the classic work in this area, which leads to explicit “water-filling” solutions, by considering a realistic scenario where the channel state quality changes arbitrarily from one transmission to the other. The problem is accordingly tackled within the framework of competitive analysis, which allows for worst-case performance guarantees in setups with arbitrarily varying channel conditions. We address both a “discrete” case, where the transmitter can transmit only at a fixed power level, and a “continuous” case, where the transmitter can choose any power level out of a bounded interval. For both cases, we propose online power-allocation algorithms with proven worst-case performance bounds. In addition, we establish lower bounds on the worst-case performance of any online algorithm and show that our proposed algorithms are optimal. [ABSTRACT FROM PUBLISHER]

We consider a multicast game with selfish noncooperative players. There is a special source node and each player is interested in connecting to the source by making a routing decision that minimizes its payment. The mutual influence of the players is determined by a cost sharing mechanism, which in our case evenly splits the cost of an edge among the players using it. We consider two different models: an integral model, where each player connects to the source by choosing a single path, and a fractional model where a player is allowed to split the flow it receives from the source between several paths. In both models we explore the overhead incurred in network cost due to the selfish behavior of the users, as well as the computational complexity of finding a Nash equilibrium. The existence of a Nash equilibrium for the integral model was previously established by the means of a potential function. We prove that finding a Nash equilibrium that minimizes the potential function is NP-hard. We focus on the price of anarchy of a Nash equilibrium resulting from the best-response dynamics of a game course, where the players join the game sequentially. For a game with n players, we establish an upper bound of O(√n log² n) on the price of anarchy, and a lower bound of Ω(log n/log log n). For the fractional model, we prove the existence of a Nash equilibrium via a potential function and give a polynomial time algorithm fur computing an equilibrium that minimizes the potential function. Finally, we consider a weighted extension of the multicast game, and prove that in the fractional model, the game always has a Nash equilibrium. [ABSTRACT FROM AUTHOR]

A central problem in personal communication systems is to optimize bandwidth usage, while providing Quality of Service (QoS) guarantees to mobile users. Network mobility management, and in particular, location management, consumes a significant portion of bandwidth, which is a necessary overhead for supporting mobile users. We focus our efforts on minimizing this overhead. Unlike previous works, we concentrate on optimizing existing schemes, and so the algorithms we present are easily incorporated into current networks. We present the first polynomial time approximation algorithms for minimum bandwidth location management. In planar graphs, our algorithm provably generates a solution that uses no more than a constant factor more bandwidth than the optimal solution. In general graphs, our algorithm provably generates a solution that uses just a factor O(log n) more bandwidth than optimal where n is the number of base stations in the network. We show that, in practice, our algorithm produces near-optimal results and outperforms other schemes that are described in the literature. For the important case of the line graph, we present a polynomial-time optimal algorithm. Finally, we illustrate that our algorithm can also be used for optimizing the handoff mechanism. [ABSTRACT FROM AUTHOR]

We consider a network design problem, where applications require various levels of Quality-of-Service (QoS) while connections have limited performance. Suppose that a source needs to send a message to a heterogeneous set of receivers. The objective is to design a low-cost multicast tree from the source that would provide the QoS levels (e.g., bandwidth) requested by the receivers. We assume that the QoS level required on a link is the maximum among the QoS levels of the receivers that are connected to the source through the link. In accordance, we define the cost of a link to be a function of the QoS level that it provides. This definition of cost makes this optimization problem more general than the classical Steiner tree problem. We consider several variants of this problem all of which are proved to be NP-Hard. For the variant where QoS levels of a link can vary arbitrarily and the cost function is linear in its QoS level, we give a heuristic that achieves a multicast tree with cost at most a constant times the cost of an optimal multicast tree. The constant depends on the best constant approximation ratio of the classical Steiner tree problem. For the more general variant, where each link has a given QoS level and cost we present a heuristic that generates a multicast tree with cost O(min{log r, k}) times the cost of an optimal tree, where r denotes the number of receivers, and k denotes the number of different levels of QoS required. We generalize this result to hold for the case of many multicast groups. [ABSTRACT FROM AUTHOR]

Studies the design of handoff rerouting algorithms for reducing the overall session cost in personal communication systems (PCS). Connection-based technologies that serve as the bases for most modern communication systems used as infrastructure for PCS networks; Balance between the session setup cost and the hold cost achieved by the algorithms; Implications on studies of computer networks.