Search

In wireless networks, the notion of compatible set refers to a set of radio links that can be simultaneously active with a tolerable interference. Finding a compatible set with maximum weighted revenue from the parallel transmissions is an important optimization subproblem for resource management in wireless networks. For this subproblem, two basic ways of expressing the signal-to-interference-plus-noise-ratio within integer programming are used, differing in the number of variables and the quality of the upper bound given by their linear relaxations. To our knowledge, there is no systematic study comparing the effectiveness of these two approaches to the compatible set optimization problem. The contribution of the article is twofold. First, we present a comparison of the two basic approaches, and, second, we introduce matching inequalities that improve the upper bounds achievable with the two basic approaches. The matching inequalities are generated within the branch-and-cut process using a minimum odd-cut generation procedure based on the Gomory–Hu tree algorithm. The article presents results of a numerical study illustrating our statements and findings.

During the last one and a half decades, wireless sensor networks (WSNs) have witnessed significant growth and tremendous development. While enjoying the wide variety of applications, the sensors in WSN have constrained resources, affecting their living lives, working times, assigned tasks, etc. Though a large number of efforts have been devoted into designing protocols that save energy as much as possible, they are still a passive solution. In this paper, we propose a novel approach called policy-based assistance system (PAS) that addresses the issue of resource limitation in a proactive manner. Complementary to existing works which focus on saving energy in individual nodes, our proposed approach further allows sensors with limited resources to make requests to other sensors to help complete the tasks. In this way, the resources in the whole WSN are better utilized and more tasks can be completed with little communication overhead. [ABSTRACT FROM AUTHOR]

Airtime is set as the default routing metric for the ongoing IEEE 802.11s wireless mesh networking standard. The metric is designed to minimize channel resource consumption by accounting for loss rate, bandwidth, and channel characteristics. However, the metric exhibits a noticeable ping-pong effect whose nature is still vague, and the very few references to this in the literature condemn it for being a perilous behavior. In this paper, we present a thorough study of the Airtime ping-pong effect, and highlight its correlation to the underlying rate control algorithms. Using different rate control algorithms (e.g., ARF, AARF, ONOE, AMRR and Constant rate), we establish that transmission rate adaptation is the principal cause behind the effect. We show that the effect is an inherent behavior, and that an accurate characterization of it can help improve network performance. We present a ping-pong-aware mechanism that, by detecting when a link undergoes such an effect, adapts the routing protocol for better network performance. The mechanism is O(1), decentralized, and can be easily integrated into the IEEE 802.11s routing protocol. [ABSTRACT FROM AUTHOR]

In this paper we consider an integrated model for TCP/IP protocols with multipath routing. The model combines a Network Utility Maximization for rate control based on end-to-end queueing delays, with a Markovian Traffic Equilibrium for routing based on total expected delays. We prove the existence of a unique equilibrium state which is characterized as the solution of an unconstrained strictly convex program. A distributed algorithm for solving this optimization problem is proposed, with a brief discussion of how it could be implemented by adapting the current Internet protocols. [ABSTRACT FROM AUTHOR]

Bottleneck congestion games properly model the properties of many real-world network routing applications. They are known to possess strong equilibria—a strengthening of Nash equilibrium to resilience against coalitional deviations. In this paper, we study the computational complexity of pure Nash and strong equilibria in these games. We provide a generic centralized algorithm to compute strong equilibria, which has polynomial running time for many interesting classes of games such as, e.g., matroid or single-commodity bottleneck congestion games. In addition, we examine the more demanding goal to reach equilibria in polynomial time using natural improvement dynamics. Using unilateral improvement dynamics in matroid games pure Nash equilibria can be reached efficiently. In contrast, computing even a single coalitional improvement move in matroid and single-commodity games is strongly NP -hard. In addition, we establish a variety of hardness results and lower bounds regarding the duration of unilateral and coalitional improvement dynamics. They continue to hold even for convergence to approximate equilibria. [ABSTRACT FROM AUTHOR]