Workshop talks (WT) abstracts
3DLS: Density-Driven Data Location Service for Mobile Ad-Hoc Networks
Roy Friedman (Technion, IL), Noam Mori (Technion, IL)
Finding data items is one of the most basic services of any distributed system. It is particular challenging in ad-hoc networks, due to their inherent decentralized nature and lack of infrastructure. A data location service (DLS) provides this capability. This paper presents 3DLS, a novel density driven data location service. 3DLS is based on performing biased walks over a density based virtual topography. 3DLS also includes an autonomic dynamic configuration mechanism for adapting the lengths of the walks, in order to ensure good performance in varying circumstances and loads. This is without any explicit knowledge of the network characteristics, such as size, mobility speed, etc. Moreover, 3DLS does not rely on geographical knowledge, its decisions are based only on local information, it does not invoke multi-hop routing, and it avoids flooding the network. The paper includes a detailed performance study of 3DLS, carried by simulations, which compares 3DLS to other known approaches. The simulations results validate the viability of 3DLS.
Topology Design and Control: A Game-Theoretic Perspective
Amir Nahir (Technion, IL), Ariel Orda (Technion, IL), Ari Fruend (IBM Research, Israel)
We study the performance of non-cooperative networks in light of three major topology design and control considerations, namely the price of establishing a link, path delay, and path proneness to congestion or interference, the latter being modeled through the "relaying extent" of the nodes. We analyze these considerations and the tradeoffs between them from a game theoretic perspective, where each network element attempts to optimize its individual performance. We show that for all considered cases but one, the existence of a Nash equilibrium point is guaranteed. In addition, we demonstrate that the price of anarchy, i.e., the performance penalty incurred by non-cooperative behavior, may be prohibitively large; yet, we also show that such games usually admit at least one Nash equilibrium that is system-wide optimal, i.e., their price of stability is 1. This finding suggests that a major improvement can be achieved by providing a central ("social") agent with the ability to impose the initial configuration on the system.
Cross-Layer Hybrid FEC/ARQ Reliable Multicast with Adaptive Modulation and Coding in Broadband Wireless Networks
Reuven Cohen (Technion, IL), Guy Grebla (Technion, IL), Liran Katzir (Technion, IL)
In this paper we define and address a new problem that arises when a base station in a broadband wireless network wishes to multicast information to a large group of nodes and to guarantee some level of reliability using Application layer FEC codes. Every data block to be multicast is translated into a sequence of K + n packets, from which every receiver must receive at least K in order to correctly decode the block. The new problem is to determine which PHY layer MCS (Modulation and Coding Scheme) the base station should use for each packet. We present several variants of this problem, which differ in the number of ARQ (Automatic Repeat reQuest) rounds during which the delivery of a data block must be completed. Most of these variants are shown to be NP-hard. However, we present optimal solutions for practical instances, where the number of MCSs is small, and efficient approximations and heuristics for the general case of each variant.
Cross-Layer On-Demand Routing Algorithms for Multi-Hop Wireless CSMA/CA Networks
Ju-Lan Hsu (UCLA, US), Izhak Rubin (UCLA, US)
We investigate the impact of combined multi-rate and routing operations in multi-hop wireless ad hoc networks in which nodes employ 802.11-based CSMA/CA MAC protocols. To measure the ability of the network to transport traffic in a throughput effective manner, we employ the link-flow transport throughput capacity measure as a key routing metric. The latter measure considers multi-rate operations as well as instantaneous topological, loading and capacity availability conditions. We develop on-demand cross layer schemes that employ these transport throughput metrics for route discovery purposes. We compare the performance behavior of our schemes with that exhibited by those that do not use the link-flow transport throughput capacity function as a routing metric. We demonstrate the performance effectiveness of these schemes by evaluating three distinct network scenarios.
RI-MAC: A Receiver Initiated Asynchronous Duty Cycle MAC Protocol for Dynamic Traffic Loads in Wireless Sensor Networks
Yanjun Sun (Rice University, US), Omer Gurewitz (Ben-Gurion University, IL), David B. Johnson (Rice University, US)
The problem of idle listening is one of the most significant sources of energy consumption in wireless sensor nodes, and many techniques have been proposed based on duty cycling to reduce this cost. In this paper, we present a new asynchronous duty cycle MAC protocol, called Receiver-Initiated MAC (RI-MAC), that uses receiver-initiated data transmission in order to efficiently and effectively operate over a wide range of traffic loads. RI-MAC attempts to minimize the time a sender and its intended receiver occupy the wireless medium to find a rendezvous time for exchanging data, while still decoupling the sender and receiver's duty cycle schedules. We show the performance of RI-MAC through detailed ns-2 simulation and through measurements of an implementation in TinyOS in a testbed of MICAz motes. Compared to the prior asynchronous duty cycling approach of X-MAC, RI-MAC achieves higher throughput, packet delivery ratio, and power efficiency under a wide range of traffic loads. Especially when there are contending flows, such as bursty traffic or transmissions from hidden nodes, RI-MAC significantly improves throughput and packet delivery ratio. Even under light traffic load for which X-MAC is optimized, RI-MAC achieves the same high performance in terms of packet delivery ratio and latency while maintaining comparable power efficiency.
MAC for Networks with Multipacket Reception Capability and Spatially Distributed Nodes
Gunar D. Celik (MIT, US), Gil Zussman (Columbia University, US), Wajahat F. Khan (MIT, US), Eytan Modiano (MIT, US)
The physical layer of future wireless networks will be based on novel radio technologies such as UWB and MIMO. One of the important capabilities of such technologies is the ability to capture a few packets simultaneously. This capability has the potential to improve the performance of the MAC layer. However, we show that in networks with spatially distributed nodes, reusing backoff mechanisms originally designed for narrow-band systems (e.g. CSMA/CA) is inefficient. It is well known that when networks with spatially distributed nodes operate with such MAC protocols, the channel may be captured by nodes that are near the destination, leading to unfairness. We show that when the physical layer enables multipacket reception, the negative implications of reusing the legacy protocols include not only such unfairness but also a significant throughput reduction. We present alternative backoff mechanisms and evaluate their performance via Markovian analysis and simulation. We show that our alternative backoff mechanisms can improve both overall throughput and fairness.
Maximum-Lifetime Routing: System Optimization & Game-Theoretic Perspectives
Liane Lewin-Eytan (Technion, IL), Seffi Naor (Technion, IL), Ariel Orda (Technion, IL)
Routing traffic so as to maximize the lifetime of a transmission is a major problem in wireless networks. We address a two-way multicast problem, where a root wishes to transmit data to a subset of nodes, as well as receive data from them. In addition, we consider the anycast problem, wherethere is a subset of nodes that wish to communicate with each other. We consider both a per-hop multi-recipients environment, where over each hop, the transmission is received by all nodes within range, and a per-hop single-recipient environment, where over each hop the transmission is received by a single recipient. For both environments, our work consists of two parts. In the first part we focus on system optimization perspectives of the lifetime maximization problem, while in the second part we investigate the game-theoretic perspective of the respective problems.
We first note that, for the per-hop multi-recipients environment, an optimal solution can be computed in polynomial time. Nevertheless, for the per-hop single-recipient environment, we observe that computing an optimal solution is NP-hard. Accordingly, we provide a polynomial time algorithm that finds a 2-approximate solution for the case of uniform transmission power levels. For different transmission power levels, we provide an O(log2 n) approximation algorithm for the general problem, and an O(log n) approximation algorithm for the special case where the set of terminals equals the set of all nodes, whose size equals n.
For each environment, we consider the corresponding noncooperative game scenario, and prove that by following the natural game course users converge to a Nash equilibrium. For the per-hop multi-recipients environment, we show that if the players join the game sequentially, the Nash equilibrium is (networkwide) optimal. For the per-hop single-recipient environment, we show that the price of anarchy is unbounded. On the other hand, we show that for both environments, the price of stability, where the best Nash equilibrium is considered, is 1; hence, optimal (networkwide) performance can be achieved if the initial configuration can be imposed on the players.
Self-stabilizing and self-organizing mobile networks
Shlomi Dolev (Ben-Gurion University, IL)
Self-stabilization ([Dij74], [Dolev00]) is an important property of any dynamic long-lived system. Self-stabilizing systems may start operating in any arbitrary state, and can therefore recover following a temporary violation of the assumption made by the system designer. Mobile ad-hoc networks are very dynamic in nature and must cope with unreliable and sometimes unpredictable environments. Thus the design of self-stabilizing mobile and ad-hoc networks is of great importance. Self-stabilizing networks are self-organizing if they start to operate as they should in sub-linear time. We overview several recent works demonstrating several directions for creating adaptive infrastructures and abstractions; namely self-stabilizing and self-organizing infrastructures. These infrastructures fit the mobile ad-hoc network characteristic.
Travel delays in wireless networks
Erol Gelenbe (Imperial College London, UK)
We consider a wireless network in which packets are forwarded opportunistically from the source towards the destination, without accurate knowledge of the direction that they should take. A Brownian motion model that includes the effect of packet losses, and subsequent retransmission after a time-out, is used to compute the average travel time of the packet. The results indicate that the average travel time is always finite provided that a time-out is used, and that there is an element of randomness in the manner in which successive nodes are being chosen. We show that the average packet travel time can be minimized by a judicious choice of the time-out, and its optimum value in turn depends on other system parameters such as packet-loss probabilities. We present simulations that illustrate the analytical results.
Random walks techniques for wireless networks
Chen Avin (Ben Gurion University, IL)
In recent years random-walk-based algorithms have been proposed for a variety of networking tasks. These proposals include searching, routing, self-stabilization, and query processing in wireless networks, peer-to-peer networks and other distributed systems. This approach is gaining popularity since random walks present locality, simplicity, low-overhead and inherent robustness to structural changes. Two properties of the random walk on graphs are essential to determine the efficiency of this approach: cover time (the expected time to visit all nodes) and mixing time (in regular graphs, the time to sample a node uniformly). In this talk I will present some of the work on the topic I was involved in, emphasizing results related to applications for wireless networks.
"Not All At Once!" - A Generic Scheme for Estimating the Number of Affected Nodes
Reuven Cohen (Technion, IL), Alex Landau (Technion, IL)
In this talk, we present a generic scheme, called NATO!, for estimating the size of a group of nodes affected by the same event in a large-scale network, such as a grid, a sensor network or a wireless broadband access network, while receiving only a small number of feedback messages from this group. Using the proposed scheme, a centralized gateway analyzes the transmission times of these feedback messages, defines a likelihood function for them, and then uses the Newton-Raphson method to find the number of affected nodes for which this function is maximized. We present complete mathematical analysis for the precision of the proposed algorithm and provide tight upper and lower bounds for the estimation error. We then show how to use NATO! in order to improve the performance of large-scale partially reliable multicast streaming in a broadcast wireless network.
On the Exploitation of CDF based Wireless Scheduling
Udi Ben-Porat (Tel-Aviv University, IL), Anat Bremler-Barr (IDC Herzliya, IL), Hanoch Levy (Tel-Aviv University, IL)
Channel-aware scheduling strategies - such as the CDF Scheduler (CS) algorithm for the CDMA/HDR systems - provide an effective mechanism for utilizing the channel data rate for improving throughput performance in wireless data networks by exploiting channel fluctuations. A highly desired property of such a scheduling strategy is that its algorithm will be stable, in the sense that no user has incentive "cheating" the algorithm in order to increase his/her channel share (on the account of others). We present a scheme by which coordination allows a group of users to gain permanent increase in both their time slot share and in their throughput, on the expense of others, by misreporting their rates. We show that for large populations consisting of regular and coordinated users in equal numbers, the ratio of allocated time slots between a coordinated user and a regular one converges to e-1≈1.7. Our scheme targets the very fundamental principle of CS (as opposed to just attacking implementation aspects), which bases its scheduling decisions on the Cumulative Distribution Function (CDF) of the channel rates reported by users. Our scheme works both for the continuous channel spectrum and the discrete channel spectrum versions of the problem.
Toward Optimal Utilization of Shared Random Access Channels
Seffi Naor (Technion, IL), Danny Raz (Technion, IL), Gabriel Scalosub (University of Toronto, CA)
We consider a multipacket reception channel shared by several communication applications. This is the case, for example, in a single radio mesh network where neighboring cells use the same radio channel. In such scenarios, unlike the common multiple access model, several transmissions may succeed simultaneously, depending on the actual locations of the sending and receiving stations, and thus channel utilization may be greater than 1. Our goal is to derive a decentralized access control mechanism that maximizes the channel utilization, while taking into account fairness among the different users. We focus on a simple case where each user can adjust a single parameter that determines its transmission probability in any time slot, and develop such a protocol for the general problem, where users are distributed arbitrarily, based on strong motivation which is derived from analytical bounds for homogeneous interferences. We further show, using extensive simulations, that this protocol achieves a high utilization of radio resources compared to any other protocol (not necessary based on a simple parameter), while maintaining fairness between all users.
Improved Approximation Algorithms for Relay Placement
Alon Efrat (The University of Arizona, US), Sándor P. Fekete (Braunschweig University of Technology, DE),
Abstract. In the relay placement problem the input is a set of sensors and a number r ≥ 1, the communication range of a relay. In the one-tier version of the problem the objective is to place a minimum number of relays so that between every pair of sensors there is a path through sensors and/or relays such that the consecutive vertices of the path are within distance r if both vertices are relays and within distance 1 otherwise. The two-tier version adds the restrictions that the path must go through relays, and not through sensors. We present a 3.11-approximation algorithm for the one-tier version and a PTAS for the two-tier version. We also show that the one-tier version admits no PTAS, assuming P ≠ NP.