Paper Abstracts

Transport Protocols

A Receiver-Centric Transport Protocol for Mobile Hosts with Heterogeneous Wireless Interfaces,
Hung-Yun Hsieh, Kyu-Han Kim, Yujie Zhu, and Raghupathy Sivakumar (Georgia Tech)
Numerous transport protocols have been proposed in related work for use by mobile hosts over wireless environments. A common theme among the design of such protocols is that they specifically address the distinct characteristics of the last-hop wireless link, such as random wireless errors, round-trip time variations, black-outs, handoffs, etc. In this paper, we argue that due to the defining role played by the wireless link on a connection's performance, locating the intelligence of a transport protocol at the mobile host that is adjacent to the wireless link can result in distinct performance advantages. To this end, we present a receiver-centric transport protocol called RCP (Reception Control Protocol) that is a TCP clone in its general behavior, but allows for better congestion control, loss recovery, and power management mechanisms compared to sender-centric approaches. More importantly, in the context of recent trends where mobile hosts are increasingly being equipped with multiple interfaces providing access to heterogeneous wireless networks, we show that a receiver-centric protocol such as RCP can enable a powerful and comprehensive transport layer solution for such multi-homed hosts. Specifically, we describe how RCP can be used to provide: (i) a scalable solution to support interface specific congestion control for a single active connection; (ii) seamless server migration capability during handoffs; and (iii) effective bandwidth aggregation when receiving data through multiple interfaces, either from one server, or from multiple replicated servers. We use both packet level simulations, and real Internet experiments to evaluate the proposed protocol.
Enhancing TCP Fairness in Ad Hoc Wireless Networks Using Neighborhood RED,
Kaixin Xu and Mario Gerla (UCLA), Lantao Qi (Tianjin University), and Yantai Shu
Significant TCP unfairness in ad hoc wireless networks has been reported during the past several years. This unfairness results from the nature of the shared wireless medium and location dependency. If we view a node and its interfering nodes to form a "neighborhood", the aggregate of local queues at these nodes represents the distributed queue for this neighborhood. However, this queue is not a FIFO queue. Flows sharing the queue have different, dynamically changing priorities determined by the topology and traffic patterns. Thus,they get different feedback in terms of packet loss rate and packet delay when congestion occurs. In wired networks, the Randomly Early Detection (RED) scheme was found to improve TCP fairness. In this paper, we show that the RED scheme does not work when running on individual queues in wireless nodes. We then propose a Neighborhood RED (NRED) scheme, which extends the RED concept to the distributed neighborhood queue. Simulation studies confirm that the NRED scheme can improve TCP unfairness substantially in ad hoc networks. Moreover, the NRED scheme acts at the network level, without MAC protocol modifications. This considerably simplifies its deployment.
A Comparison of Mechanisms for Improving Mobile IP Handoff Latency for End-to-End TCP,
Robert Hsieh and Aruna Seneviratne (University of New South Wales)
Handoff latency results in packet losses and severe End-to-End TCP performance degradation as TCP, perceiving these losses as congestion, causes source throttling or retransmission. In order to mitigate these effects, various Mobile IP(v6) extensions have been designed to augment the base Mobile IP with hierarchical registration management, address pre-fetching and local retransmission mechanisms. While these methods have reduced the impact of losses on TCP goodput and improved handoff latency, no comparative studies have been done regarding the relative performance amongst them. In this paper, we comprehensively evaluated the impact of layer-3 handoff latency on End-to-End TCP for various Mobile IP(v6) extensions. Five such frameworks are compared with the base Mobile IPv6 framework, namely, i) Hierarchical Mobile IPv6, ii) Hierarchical Mobile IPv6 with Fast-handover, iii) (Flat) Mobile IPv6 with Fast-handover, iv) Simultaneous Bindings, and v) Seamless handoff architecture for Mobile IP (S-MIP). We propose an evaluation model examining the effect of linear and ping-pong movement on handoff latency and TCP goodput, for all above frameworks. Our results show that S-MIP performs best under both ping-pong and linear movements during a handoff, with latency comparable to a layer-2 (access layer) handoff. All other frameworks suffer from packet losses and performance degradation of some sort. We also proposed an optimization for S-MIP which improves the performance by further eliminating the possibility of packets out of order, caused by the local packet forwarding mechanisms of S-MIP.

Wireless Network Performance

Characterizing the Achievable Rates in Multihop Wireless Networks,
Murali Kodialam and Thyagarajan Nandagopal (Lucent Technologies)
This paper considers the problem of determining he achievable rates in multi-hop wireless networks. We consider the problem of jointly routing the flows and scheduling transmissions to achieve a given rate vector. We develop tight necessary and sufficient conditions for the achievability of the rate vector. We develop efficient and easy to implement Fully Polynomial Time Approximation Schemes for solving the routing problem. The scheduling problem is a solved as a graph edge-coloring problem. We show that this approach guarantees that the solution obtained is within 67% of he optimal solution in the worst case and, in practice, is typically within about 80 % of the optimal solution. The approach that we use is quite flexible and is a promising method to handle more sophisticated interference conditions, multiple channels, multiple antennas, and routing with diversity requirements.
Throughput Capacity of Random Ad Hoc Networks with Infrastructure Support,
Ulas Kozat and Leandros Tassiulas (University of Maryland)
In this paper, we consider the transport capacity of ad hoc networks with a random flat topology under the present support of an infinite capacity infrastructure network. Such a network architecture allows ad hoc nodes to communicate with each other by purely using the remaining ad hoc nodes as their relays. In addition, ad hoc nodes can also utilize the existing infrastructure fully or partially by reaching any access point (or gateway) of the infrastructure network in a single or multi-hop fashion. Using the same tools as in [1], we show that the per source node capacity of Θ(W/log(N)) can be achieved in a random network scenario with the following assumptions: (i) The number of ad hoc nodes per access point is bounded above, (ii) each wireless node, including the access points, is able to transmit at W bits/sec using a fixed transmission range, and (iii) N ad hoc nodes, excluding the access points, constitute a connected topology graph. This is a significant improvement over the capacity of random ad hoc networks with no infrastructure support which is found as Θ(W/sqrt(N log(N)) in [1]. Although better capacity figures may be obtained by complex network coding or exploiting mobility in the network, infrastructure approach provides a simpler mechanism that has more practical aspects. We also show that even when less stringent requirements are imposed on topology connectivity, a per source node capacity figure that is arbitrarily close to Θ(1) cannot be obtained. Nevertheless, under these weak conditions, we can further improve per node throughput significantly.
Impact of Interference on Multi-hop Wireless Network Performance,
Kamal Jain, Jitendra Padhye, Venkat Padmanabhan, and Lili Qiu (Microsoft Research)
In this paper, we address the following question: given a specific placement of wireless nodes in physical space and a specific traffic workload, what is the maximum throughput that can be supported by the resulting network? Unlike previous work that has focused on computing asymptotic performance bounds under assumptions of homogeneity or randomness in the network topology and/or workload, we work with any given network and workload specified as inputs.
A key issue impacting performance is wireless interference between neighboring nodes. We model such interference using a conflict graph, and present methods for computing upper an lower bounds on the optimal throughput for the given network an workload. To compute these bounds, we assume that packet transmissions at the individual nodes can be finely controlled and carefully schedule by an omniscient an omnipotent central entity, which is unrealistic. Nevertheless, using ns-2 simulations, we show that the routes derived from our analysis often yield noticeably better throughput than the default shortest path routes even in the presence of uncoordinated packet transmissions and MAC contention. This suggests that there is opportunity for achieving throughput gains by employing an interference-aware routing protocol.

Location Information

Range-Free Localization Schemes for Large Scale Sensor Networks,
Tian He, Chengdu Huang, Brian Blum, John A Stankovic, and Tarek Abdelzaher (University of Virginia)
Wireless Sensor Networks have been proposed for a multitude of location-dependent applications. For such systems, the cost and limitations of the hardware on sensing nodes prevent the use of range-based localization schemes that depend on absolute point-to-point distance estimates. Because coarse accuracy is sufficient for most sensor network applications, solutions in range-free localization are being pursued as a cost-effective alternative to more expensive range-based approaches. In this paper, we present APIT, a novel localization algorithm that is range-free. We show that our APIT scheme performs best when an irregular radio pattern and random node placement are considered, and low communication overhead is desired. We compare our work via extensive simulation, with three state-of-the-art range-free localization schemes to identify the preferable system configurations of each. In addition, we study the effect of location error on routing and tracking performance. We show that routing performance and tracking accuracy are not significantly affected by localization error when the error is less than 0.4 times the communication radio radius.
Geographic Routing without Location Information,
Ananth Rao, Christos Papadimitriou, Sylvia Ratnasamy, Scott Shenker, and Ion Stoica (University of California, Berkeley)
For many years, scalable routing for wireless communication systems was a compelling but elusive goal. Recently, several routing algorithms that exploit geographic information (e.g., GPSR) have been proposed to achieve this goal. These algorithms refer to nodes by their location, not address, and use those coordinates to route greedily, when possible, towards the destination. However, there are many situations where location information is not available at the nodes, and so geographic methods cannot be used. In this paper we define a scalable coordinate-based routing algorithm that does not rely on location information, and thus can be used in a wide variety of ad hoc and sensornet environments.
Efficient Location Area Planning for Personal Communication Systems,
Yigal Bejerano (Lucent Technologies, Bell Labs), Nicole Immorlica (MIT), Joseph Naor (The Technion), and Mark Smith (Lucent Technologies, Bell Labs)
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.

Routing Optimizations

Minimum Energy Disjoint Path Routing in Wireless Ad-Hoc Networks,
Anand Srinivas and Eytan Modiano (MIT)
We develop algorithms for finding minimum energy disjoint paths in an all-wireless network, for both the node and link-disjoint cases. Our major results include a novel polynomial time algorithm that optimally solves the minimum energy 2 link-disjoint paths problem, as well as a polynomial time algorithm for the minimum energy k node-disjoint paths problem. In addition, we present efficient heuristic algorithms for both problems. Our results show that link-disjoint paths consume substantially less energy than node-disjoint paths. We also found that the incremental energy of additional link-disjoint paths is decreasing. This finding is somewhat surprising due to the fact that in general networks additional paths are typically longer than the shortest path. However, in a wireless network, additional paths can be obtained at lower energy due to the broadcast nature of the wireless medium. Finally, we discuss issues regarding distributed implementation and present distributed versions of the optimal centralized algorithms presented in the paper.
A High-Throughput Path Metric for Multi-Hop Wireless Routing,
Douglas De Couto, Daniel Aguayo, John Bicket, and Robert Morris (MIT)
This paper presents the expected transmission count metric (ETX), which finds high-throughput paths on multi-hop wireless networks. ETX minimizes the expected total number of packet transmissions (including retransmissions) required to successfully deliver a packet to the ultimate destination. The ETX metric incorporates the effects of link loss ratios, asymmetry in the loss ratios between the two directions of each link, and interference among the successive links of a path. In contrast, the minimum hop-count metric chooses arbitrarily among the different paths of the same minimum length, regardless of the often large differences in throughput among those paths, and ignoring the possibility that a longer path might offer higher throughput.
This paper describes the design and implementation of ETX as a metric for the DSDV and DSR routing protocols, as well as modifications to DSDV and DSR which allow them to use ETX. Measurements taken from a 29-node 802.11b test-bed demonstrate the poor performance of minimum hop-count, illustrate the causes of that poor performance, and confirm that ETX improves performance. For long paths the throughput improvement is often a factor of two or more, suggesting that ETX will become more useful as networks grow larger and paths become longer.
Reactive Routing Overhead in an Unreliable Grid,
Nianjun Zhou, Huaming Wu, and Alhussein Abouzeid (Rensselaer Polytechnic Institute)
This paper presents a new mathematical and simulative framework for quantifying the overhead of a broad class of reactive routing protocols, such as DSR and AODV, in wireless variable topology (ad-hoc) networks. We focus on situations where the nodes are stationary but unreliable, as is common in the case of sensor networks. We explicitly model the application-level traffic in terms of the statistical description of the number of hops between a source and a destination. The sensor network is modelled by an unreliable regular Manhattan (i.e. degree four) grid, and expressions for various components of the routing overhead are derived. Results are compared against ns-2 simulations for regular and random topologies, which corroborate the essential characteristics of the analytical results. One of the key insights that can be drawn from the mathematical results of this paper is that it is possible to design in infinitely scalable reactive routing protocols for variable topology networks by judicious engineering of the traffic patterns to satisfy the conditions presented in this paper.

Wireless LAN Optimizations

MiSer: An Optimal Low-Energy Transmission Strategy for IEEE 802.11a/h,
Daji Qiao (University of Michigan), Sunghyun Choi (Seoul National University); and Amit Jain and Kang Shin (University of Michigan)
Reducing the energy consumption by wireless communication devices is perhaps the most important issue in the widely-deployed and exponentially-growing IEEE 802.11 Wireless LANs (WLANs). TPC (Transmit Power Control) and PHY (physical layer) rate adaptation have been recognized as two most effective ways to achieve this goal. The emerging 802.11h standard, which is an extension to the current 802.11 MAC and the high-speed 802.11a PHY, will provide a structured means to support intelligent TPC. In this paper, we propose a novel scheme, called MiSer, that minimizes the communication energy consumption in 802.11a/h systems by combining TPC with PHY rate adaptation. The key idea is to compute offline an optimal rate-power combination table, and then at runtime, a wireless station determines the most energy-efficient transmission strategy for each data frame by a simple table lookup. Another key contribution of this paper is to provide a rigorous analysis of the relation among different radio ranges and TPC's effect on the interference in 802.11a/h systems, which justifies MiSer's approach to ameliorating the TPC-caused interference by transmitting the CTS frames at a stronger power level. Our simulation results show that MiSer delivers about 20% more data per unit of energy consumption than the PHY rate adaptation scheme without TPC, while outperforming single-rate TPC schemes significantly thanks to the excellent energy-saving capability of PHY rate adaptation.
Self-Tuning Wireless Network Power Management,
Manish Anand, Edmund Nightingale, and Jason Flinn (University of Michigan)
Current wireless network power management often substantially degrades performance and may even increase overall energy usage when used with latency-sensitive applications. We propose self-tuning power management (STPM) that adapts its behavior to the access patterns and intent of applications, the characteristics of the network interface, and the energy usage of the platform. We have implemented STPM as a Linux kernel module--our results show substantial benefits for distributed file systems, streaming audio, and thin-client applications. Compared to default 802.11b power management, STPM reduces the total energy usage of an iPAQ running the Coda distributed file system by 21% while also reducing interactive file system delay by 80%. Further, STPM adapts to diverse operating conditions: it yields good results on both laptops and handhelds, supports 802.11b network interfaces with substantially different characteristics, and performs well across a range of application network access patterns.
Improving Protocol Capacity with Model-based Frame Scheduling in IEEE 802.11-Operated WLANs,
Hwangnam Kim and Jennifer Hou (University of Illinois at Urbana-Champaign)
In this paper, we develop a model-base frame scheduling scheme, called MFS, to enhance the capacity of IEEE 802.11-operated wireless LANs (WLANs). In MFS each node estimates the current network status by keeping track of the number of collisions it encounters between its two consecutive successful frame transmissions, and, based on the the estimate information, computes the current network utilization. The result is then used to determine a scheduling delay that is introduced (with the objective of avoiding collision) before a node attempts for transmission of its pending frame. In order to accurately calculate the current utilization in WLANs, we develop an analytical model that characterizes data transmission activities in IEEE 802.11-operated WLANs with/without the RTS/CTS mechanism, and validate the model with ns-2 simulation. All the control overhead incurred in the physical and MAC layers, as well as system parameters specified in IEEE 802.11 are figured in.
We have conducted a comprehensive simulation study to evaluate MFS in perspective of number of collisions, achievable throughput, and inter-transmission delay. The simulation results indicate that the performance improvement with respect to protocol capacity can be as high as 20% with RTS/CTS an 150% without RTS/CTS, in a WLAN of up to 300 nodes. In addition, the inter-transmission delay in MFS is smaller and exhibits less variation than that in IEEE 802.11.

Simulation and Implementation Issues

Sound Mobility Models,
Jungkeun Yoon, Mingyan Liu, and Brian Noble (University of Michigan)
Simulation has become an indispensable tool in the construction and evaluation of mobile systems. By using mobility models that describe constituent movement, one can explore large systems, producing repeatable results for comparison between alternatives. Unfortunately, the vast majority of mobility models--including all those in which nodal speed and distance or destination are chosen independently--suffer from decay; average speed decreases until converging to some long-term average. Such decay provides an unsound basis for simulation studies that collect results averaged over time, complicating the experimental process.
This paper shows via analysis that such decay is inevitable in a wide variety of mobility models, including the most common in use today. We derive a general framework for describing this decay, and apply it to a number of practical cases. Furthermore, this framework allows us to transform any given mobility model into a stationary one: choose initial speeds from the steaady-state distribution, and subsequent speeds from the original. This transformation provides sound models for simulation, eliminating variations in average nodal speed.
Towards Realistic Mobility Models for Mobile Ad hoc Networks,
Amit Jardosh, Elizabeth Belding-Royer, Kevin Almeroth, and Subhash Suri (University of California, Santa Barbara)
One of the most important methods for evaluating the characteristics of ad hoc networking protocols is through the use of simulation. Simulation provides researchers with number of significant benefits, including repeatable scenarios, isolation of parameters, and exploration of a variety of metrics. The topology and movement of the nodes in the simulation are key factors in the performance of the network protocol under study. Once the nodes have been initially distributed, the mobility model dictates the movement of the nodes within the network. Because the mobility of the nodes directly impacts the performance of the protocols, simulation results obtained with unrealistic movement models may not correctly reflect the true performance of the protocols. The majority of existing mobility models for ad hoc networks do not provide realistic movement scenarios; they are limited to random walk models without any obstacles. In this paper, we propose to create more realistic movement models through the incorporation of obstacles. These obstacles are utilized to both restrict node movement as well as wireless transmissions. In addition to the inclusion of obstacles, we construct movement paths using the Voronoi diagram of obstacle vertices. Nodes can then be randomly distributed across the paths, and can use shortest path route computations to destinations at randomly chosen obstacles. Simulation results show that the use of obstacles and pathways has significant impact on the performance of ad hoc network protocols.
DIRAC: A Software-based Wireless Router System,
Petros Zerfos, Gary Zhong, Jerry Cheng, Haiyun Luo, and Songwu Lu (UCLA); and Jeffrey Jia-ru Li (HIQ Computers)
Routers are expected to play an important role in the IP-based wireless data network. Although a substantial number of techniques have been proposed to improve wireless network performance under dynamic wireless channel conditions and host mobility, a system support framework is still missing. In this paper, we describe DIRAC, a software-based router system that is designed for wireless networks to facilitate the implementation and evaluation of various channel-adaptive and mobility-aware protocols. DIRAC adopts a distributed architecture that is composed of two parts: a Router Core (RC) shared by the wireless subnets, and a Router Agent (RA) at each access point/base station. RAs expose wireless link-layer information to the RC and enforce the control commands issued by the RC. This approach allows the router to make adaptive decisions based on link-ayer information feedback. It also permits the router to enforce its policies (e.g., policing) more effectively through underlying link-layer mechanisms. As showcases, we implement under DIRAC the prototypes of three wireless network services: link-layer assisted fast handover, channel-adaptive scheduling, and link-layer enforced policing. Our implementation and experiments show that our distributed wireless router provides a flexible framework, which enables advanced network-layer wireless services that are adaptive to channel conditions and host mobility.

Routing and Forwarding

Ad hoc-VCG: A Truthful and Cost-Efficient Routing Protocol for Mobile Ad Hoc Networks with Selfish Agents,
Stephan Eidenbenz (Los Alamos National Laboratory) and Luzi Anderegg (ETH Zurich)
We introduce a game-theoretic setting for routing in a mobile ad hoc network that consists of greedy, selfish agents who accept payments for forwarding data for other agents if the payments cover their individual costs incurred by forwarding data. In this setting, we propose Ad hoc-VCG, a reactive routing protocol that achieves the design objectives of truthfulness (i.e., it is in the agents' best interest to reveal their true costs for forwarding data) and cost-efficiency (i.e., it guarantees that routing is done along the most cost-efficient path) in a game-theoretic sense by paying to the intermediate nodes a premium over their actual costs for forwarding data packets. We show that the total overpayment (i.e., the sum of all premiums paid) is relatively small by giving a theoretical upper bound and by providing experimental evidence. Our routing protocol implements a variation of the well-known mechanism by Vickrey, Clarke, and Groves in a mobile network setting. Finally, we analyze a very natural routing protocol that is an adaptation of the Packet Purse Model [8] with auctions in our setting and show that, unfortunately, it does not achieve cost-efficiency or truthfulness.
Trajectory Based Forwarding and Its Applications,
Dragos Niculescu and Badri Nath (Rutgers)
Trajectory based forwarding (TBF) is a novel method to forward packets in a dense ad hoc network that makes it possible to route a packet along a predefined curve. It is a hybrid between source based routing and Cartesian forwarding in that the trajectory is set by the source, but the forwarding decision is based on the relationship to the trajectory rather than names of intermediate nodes. The fundamental aspects o TBF are: it decouples path naming from the actual path; it provides cheap path diversity; it trades off communication or computation. These aspects address the double scalability issue with respect to mobility rate and network size. In addition, TBF provides a common framework for many services such as: broadcasting, discovery, unicast, multicast and multipath routing in ad hoc networks. TBF requires that nodes know their position relative to a coordinate system. While a global coordinate system afforded by a system such as GPS would be ideal, approximate positioning methods provided by other algorithms are also usable.
Manycast: Exploring the Space Between Anycast and Multicast in Ad Hoc Networks,
Casey Carter, Seung Yi, Prashant Ratanchandani, and Robin Kravets (University of Illinois at Urbana-Champaign)
The characteristics of ad hoc networks naturally encourage the deployment of distributed services. Although current networks implement group communication methods, they do not support the needs of a mobile node that must locate one or more distributed servers. A node should not need detailed knowledge of network topology to choose servers with which it can communicate efficiently.
To this end, manycast is a group communication scheme that enables communication with an arbitrary (user specified) number of group members. Anycast and multicast communication are special cases of manycast in which the target number of group members is one and infinity, respectively. We present manycast and discuss its use as a communication primitive, with specific attention to ad hoc networks. We advocate manycast support at the network layer. A manycast routing protocol enables an application to contact several nearby network nodes that implement a distributed service.
We analyze some approaches to manycast, including some application layer implementations. This evaluation supports our claim that manycast must be implemented in the network layer for effective operation in ad hoc networks. We present several extensions to ad hoc routing protocols that can provide manycast support with minimal implementation effort. Through analysis and extensive simulation, we explore the behavior of these approaches to manycast, finally providing recommendations to implementors.

Ad Hoc and Sensor Networks

Topology Control for Wireless Sensor Networks,
Jianping Pan (Fujitsu), Thomas Hou (Virginia Tech), Lin Cai (University of Waterloo), Yi Shi (Virginia Tech), and Sherman Shen (University of Waterloo)
We consider a two-tiered Wireless Sensor Network (WSN) consisting of sensor clusters deployed around strategic locations and base-stations (BSs) whose locations are relatively flexible. Within a sensor cluster, there are many small sensor nodes (SNs) that capture, encode and transmit relevant information from the designated area, and there is at least one application node (AN) that receives raw data from these SNs, creates a comprehensive local-view, and forwards the composite bit-stream toward a BS. In practice, both SN and AN are battery-powered and energy-constrained, and their node lifetimes directly affect the network lifetime of WSNs. In this paper, we focus on the topology control process for ANs and BSs, which constitute the upper tier of a two-tiered WSN. We propose approaches to maximize the topological network lifetime of the WSN, by arranging BS location and inter-AN relaying optimally. Based on an algorithm in Computational Geometry, we derive the optimal BS locations under three topological lifetime definitions according to mission criticality. In addition, by studying the intrinsic properties of WSNs, we establish the upper and lower bounds of their maximal topological lifetime. When inter-AN relaying becomes feasible and favorable, we continue to develop an optimal parallel relay allocation to further prolong the topological lifetime of the WSN. An equivalent serialized relay schedule is also obtained, so that each AN only needs to have one relay destination at any time throughout the mission. The experimental performance evaluation demonstrates the efficacy of topology control as a vital process to maximize the network lifetime of WSNs.
Power Optimization in Fault-Tolerant Topology Control Algorithms for Wireless Multi-hop Networks,
MohammadTaghi Hajiaghayi, Nicole Immorlica, and Vahab S. Mirrokni (MIT)
In ad hoc wireless networks, it is crucial to minimize power consumption while maintaining key network properties. This work studies power assignment of wireless devices that minimize power while maintaining k-fault tolerance. Specifically, we require all links established by this power setting be symmetric and form a k-vertex connected subgraph of the network graph. This problem is known to be NP-hard. We show current heuristic approaches can use arbitrarily more power than the optimal solution. Hence, we seek approximation algorithms for this problem. We present three approximation algorithms. The first algorithm gives an O(kα) approximation where α is the best approximation factor for the related problem in wired network (the best α so far is in O(log k).) Then,using a more complicated algorithm and careful analysis, we achieve O(k) approximation for general graphs. We then present simple and practical distributed approximation algorithms for the cases of 2- and 3-connectivity in geometric graph. In addition, we demonstrate how we can generalize this algorithm for k-connectivity in geometric graph. Finally, we show that these approximation algorithms compare favorably with existing heuristics. We note that all algorithms presented in this paper can be used to minimize power while maintaining k-edge connectivity with guaranteed approximation factors.
Distributed Algorithms for Guiding Navigation across a Sensor Network,
Qun Li, Michael DeRosa, and Daniela Rus (Dartmouth)
We develop distributed algorithms for self-organizing sensor networks that respond to directing a target through a region. The sensor network models the danger levels sensed across its area and has the ability to adapt to changes. It represents the dangerous areas as obstacles. A protocol that combines the artificial potential field of the sensors with the goal location for the moving object guides the object incrementally across the network to the goal, while maintaining the safest distance to the danger areas. We give the analysis to the protocol and report on hardware experiments using a physical sensor network consisting of Mote sensors.

Cellular and Hybrid Networks

ARC: An Integrated Admission and Rate Control Framework for CDMA Data Networks Based on Non-cooperative Games,
Haitao Lin (University of Texas at Arlington); Mainak Chatterjee (University of Central Florida); and Sajal Das and Kalyan Basu (University of Texas at Arlington)
The competition among wireless data service providers brings in an option for the customers to switch their providers, due to unsatisfactory service or otherwise. However, the existing resource management algorithms for wireless networks fail to fully capture the far-reaching impact of this competitiveness. From this perspective, we propose an integrated admission and rate control (ARC) framework for CDMA based wireless data networks. The admission control is at the session (macro) level while the rate control is at the link layer packet (micro) level. The ARC framework is based on a novel game theoretic formulation which defines non-cooperative games between the service providers and the customers. A user's decision to leave or join a provider is based on a finite set of strategies. A service provider can also construct its game strategy set so as to maximize the utility (revenue) yet attaining its target churn rate (the probability of users leaving the network). We show that the pure strategy Nash equilibrium can be established for both under-loaded and fully-loaded systems such that the providers have clearly defined admission criteria as outcome from this game. Users are categorized into multiple classes and offered differentiated services based on the price they pay and the service degradation they can tolerate. We show that the proposed ARC framework significantly increases the provider's revenue and also successfully offers differentiated QoS to the users.
Wireless Downlink Data Channels: User Performance and Cell Dimensioning,
Thomas Bonald and Alexandre Proutiere (France Telecom)
We consider wireless downlink data channels where the transmission power of each base station is time-shared between a dynamic number of active users as in CDMA/HDR systems. We derive analytical results relating user performance, in terms of blocking probability and data throughput, to cell size and traffic density. These results are used to address a number of practically interesting issues, including the tradeoff between cell coverage and cell capacity and the choice of efficient scheduling and admission control schemes.
UCAN: A Unified Cellular and Ad-Hoc Network Architecture,
Haiyun Luo (UCLA), Ramachandran Ramjee (Lucent Technologies, Bell Labs), Prasun Sinha (University of Illinois at Urbana-Champaign), Li Li (Lucent Technologies, Bell Labs), and Songwu Lu (UCLA)
In third-generation (3G) wireless data networks, mobile users experiencing poor channel quality usually have low data-rate connections with the base-station. Providing service to low data-rate users is required for maintaining fairness, but at the cost of reducing the cell's aggregate throughput. In this paper, we propose the Unified Cellular and Ad-Hoc Network (UCAN) architecture for enhancing cell throughput, while maintaining fairness. In UCAN, a mobile client has both 3G cellular link and IEEE 802.11-based peer-to-peer links. The 3G base station forwards packets for destination clients with poor channel quality to proxy clients with better channel quality. The proxy clients then use an ad-hoc network composed of other mobile clients and IEEE 802.11 wireless links to forward the packets to the appropriate destinations, thereby improving cell throughput. We refine the 3G base station scheduling algorithm so that the throughput gains of active clients are distributed proportional to their average channel rate, thereby maintaining fairness. With the UCAN architecture in place, we propose novel greedy and on-demand protocols for proxy discovery and ad-hoc routing that explicitly leverage the existence of the 3G infrastructure to reduce complexity and improve reliability. We further propose a secure crediting mechanism to motivate users to participate in relaying packets for others. Through extensive simulations with HDR and IEEE 802.11b, we show that the UCAN architecture can improve individual user's throughput by up to 310% and the aggregate throughput of the HDR downlink by up to 60%.