Paper Abstracts
Best Student Paper Candidates
• A Unified Energy-Efficient Topology for Unicast and Broadcast
Wen-Zhan Song (Washington State University, Vancouver Campus, US), Xiang-Yang Li (Illinois Institute of Technology, US)

We propose a novel localized topology control algorithm for each wireless node to locally select communication neighbors and adjust its transmission power, such that all nodes together self-form a topology that is energy efficient simultaneously for both unicast and broadcast communications. We theoretically prove that the proposed topology is planar, which guarantees packet delivery if a certain localized routing method is used; it is power efficient for unicast-- the energy needed to connect any pair of nodes is within a small constant factor of the minimum; it is also asymptotically optimum for broadcast: the energy consumption for broadcasting data on top of it is asymptotically the best among all structures constructed using only local information; it has a constant bounded logical degree, which will potentially reduce interference and signal contention. We further prove that the average physical degree of all nodes is a small constant. To the best of our knowledge, this is the first localized algorithm to build a structure with all these desirable properties. Previously, only a centralized algorithm was reported in BGS02. Moreover, by assuming that the node ID and its position can be represented in O(log n) bits for a wireless network of n nodes, the total number of messages by our methods is in the range of [5n,13n], where each message is O(log n) bits. We also show that this structure can be efficiently updated using local information for dynamical network environment. Our theoretical results are corroborated in the simulations.

• Improving Loss Resilience with Multi-Radio Diversity in Wireless Networks
Allen Miu (MIT, US), Hari Balakrishnan (MIT, US), Can Emre Koksal (EPFL, CH)

This paper describes the Multi-Radio Diversity (MRD) wireless system, which uses path diversity to improve loss resilience in wireless local area networks (WLANs). MRD coordinates wireless receptions among multiple radios to improve loss resilience in the face of path-dependent frame corruption over the radio. MRD incorporates two techniques to recover from bit errors and lower the loss rates observed by higher layers, without consuming much extra bandwidth. The first technique is frame combining, in which multiple, possibly erroneous, copies of a given frame are combined together in an attempt to recover the frame without retransmission. The second technique is a low-overhead retransmission scheme called request-for-acknowledgment (RFA), which operates above the link layer and below the network layer to attempt to recover from frame combining failures. We present an analysis that determines how the parameters for these algorithms should be chosen.

We have designed and implemented MRD as a fully functional WLAN infrastructure based on 802.11a. In our testbed, we measured throughput gains up to 2.3x over single radio communication schemes employing 802.11's autorate adaptation scheme.

• Architecture and Evaluation of an Unplanned 802.11b Mesh Network
John Bicket (MIT, US), Daniel Aguayo (MIT, US), Sanjit Biswas (MIT, US), Robert Morris (MIT, US)

This paper evaluates the ability of a wireless mesh architecture to provide high performance Internet access while demanding little deployment planning or operational management. The architecture considered in this paper has unplanned node placement (rather than planned topology), omni-directional antennas (rather than directional links), and multi-hop routing (rather than single-hop base stations). These design decisions contribute to ease of deployment, an important requirement for community wireless networks. However, this architecture carries the risk that lack of planning might render the network's performance unusably low.

For example, it might be necessary to place nodes carefully to ensure connectivity; the omni-directional antennas might provide uselessly short radio ranges; or the inefficiency of multi-hop forwarding might leave some users effectively disconnected.

The paper evaluates this unplanned mesh architecture with a case study of the Roofnet 802.11b mesh network. Roofnet consists of 37 nodes spread over four square kilometers of an urban area. The network provides users with usable performance despite lack of planning: the average inter-node throughput is 627 kbits/second, even though the average route has three hops.

The paper evaluates multiple aspects of the architecture: the effect of node density on connectivity and throughput; the characteristics of the links that the routing protocol elects to use; the usefulness of the highly connected mesh afforded by omni-directional antennas for robustness and throughput; and the potential performance of a single-hop network using the same nodes as Roofnet.

• Capacity of Multi-Channel Wireless Networks: Impact of Number of Channels and Interfaces
Pradeep Kyasanur (University of Illinois at Urbana-Champaign, US), Nitin Vaidya (University of Illinois at Urbana-Champaign, US)

This paper studies how the capacity of a static multi-channel network scales as the number of nodes, n, increases. Gupta and Kumar have determined the capacity of single-channel networks, and those bounds are applicable to multi-channel networks as well, provided each node in the network has a dedicated interface per channel. In this work, we establish the capacity of general multi-channel networks wherein the number of interfaces, m, may be smaller than the number of channels, c. We show that the capacity of multi-channel networks exhibits different bounds that are dependent on the ratio between c and m. When the number of interfaces per node is smaller than the number of channels, there is a degradation in the network capacity in many scenarios. However, one important exception is a random network with up to O(log n) channels, wherein the network capacity remains at the Gupta and Kumar bound of Theta(W\sqrt{\frac{n}{\log n}}) bits/sec, independent of the number of interfaces available at each node. Since in many practical networks, number of channels available is small (e.g., IEEE 802.11 networks), this bound is of practical interest. This implies that it may be possible to build capacity-optimal multi-channel networks with as few as one interface per node. We also extend our model to consider the impact of interface switching delay, and show that capacity losses due to switching delay can be avoided by using multiple interfaces.

• Joint Channel Assignment and Routing for Throughput Optimization in Multi-radio Wireless Mesh Networks
Mansoor Alicherry (Bell Labs, Lucent Technologies, US), Randeep Bhatia (Bell Labs, Lucent Technologies, US), Li Li (Bell Labs, Lucent Technologies, US)

Multi-hop infrastructure wireless mesh networks offer increased reliability, coverage and reduced equipment costs over their single-hop counterpart, wireless LANs. Equipping wireless routers with multiple radios further improves the capacity by transmitting over multiple radios simultaneously using orthogonal channels. Efficient channel assignment and routing is essential for throughput optimization of mesh clients. Efficient channel assignment schemes can greatly relieve the interference effect of close-by transmissions; effective routing schemes can alleviate potential congestion on any gateways to the Internet, thereby improving per-client throughput. Unlike previous heuristic approaches, we mathematically formulate the joint channel assignment and routing problem, taking into account the interference constraints, the number of channels in the network and the number of radios available at each mesh router. We then use this formulation to develop a solution for our problem that optimizes the overall network throughput subject to fairness constraints on allocation of scarce wireless capacity among mobile clients. We show that the performance of our algorithms is within a constant factor of that of any optimal algorithm for the joint channel assignment and routing problem. In addition our evaluation shows that the performance of our algorithms is much better than the theoretical worst case bounds.

• Characterizing the Capacity Region in Multi-Radio, Multi-Channel Wireless Mesh Networks
Muralidharan Kodialam (Bell Laboratories, Lucent Technologies, US), Thyaga Nandagopal (Bell Labs, Lucent Technologies, US)

Next generation fixed wireless broadband networks are being increasingly deployed as mesh networks in order to provide and extend access to the internet. These networks are characterized by the use of multiple orthogonal channels and nodes with the ability to simultaneously communicate with many neighbors using multiple radios (interfaces) over orthogonal channels. Networks based on the IEEE 802.11a/b/g and 802.16 standards are examples of these systems. However, due to the limited number of available orthogonal channels, interference is still a factor in such networks. In this paper, we propose a network model that captures the key practical aspects of such systems and characterize the constraints binding their behavior. We provide necessary conditions to verify the feasibility of rate vectors in these networks, and use them to derive upper bounds on the achievable throughput, using a fast primal-dual algorithm. We then develop two channel assignment schemes, one static and the other dynamic, in order to derive lower bounds on the achievable throughput. The methods proposed in this paper can be a valuable tool for network designers in planning network deployment and for optimizing different performance objectives.

Routing Protocols
• MAP: Medial Axis Based Geometric Routing in Sensor Network
Jehoshua Bruck (California Institute of Technology, US), Jie Gao (California Institute of Technology, US), Anxiao Andrew Jiang (Caltech, US)

One of the challenging tasks in the deployment of dense wireless networks (like sensor networks) is in devising a routing scheme for node to node communications. Important considerations are scalability, routing complexity, the length of the communication paths and the load sharing of the routes. In this paper, we show that a compact and expressive abstraction of network connectivity by the medial axis enables efficient and localized routing. The main contribution in this paper is MAP, a Medial Axis based naming and routing Protocol that is location-free (no location information is needed), makes routing decisions locally, and achieves good load balancing. In its preprocessing phase, MAP constructs the medial axis of the nodes, defined as the set of nodes with at least two closest boundary nodes. The medial axis of the network captures both the complex geometry and non-trivial topology of the sensor field. It can be represented compactly by a graph whose size is comparable with the complexity of the geometric features (e.g., the number of holes). Each node is then given a name related to its position with respect to the medial axis. The routing scheme is derived through local decisions by the names of the source and destination nodes and guarantees delivery with reasonable and natural routes.We show by both theoretical analysis and simulations that our medial axis based geometric routing scheme is scalable, produces both short routes and excellent load balancing, and is very robust to variations in network model.

• Effects of Routing Computations in Content-Based Routing Networks with Mobile Data Sources
Vinod Muthusamy (University of Toronto, CA), Milenko Petrovic (University of Toronto, CA), Hans-Arno Jacobsen (University of Toronto, CA)

This paper presents the first quantitative evaluation of the role of routing computations on performance when mobility is introduced to a content-based routing network. Additionally, the paper identifies the factors that affect the performance of a distributed publish/subscribe architecture supporting mobile publishers; formalizes publisher mobility protocols for distributed publish/subscribe systems and develops and evaluates protocols that reduce the costs associated with supporting mobile publishers in publish/subscribe systems. Our results show that ignoring route computation time paints a false picture of the scalability of content-based routing networks, but that with appropriate protocols the adverse effects can be mitigated.

• On Designing Incentive-Compatible Routing and Forwarding Protocols in Wireless Ad-Hoc Networks
Sheng Zhong (Yale University, US), Li Li (Bell Labs, Lucent Technologies, US), Yanbin (Grace) Liu (The University of Texas at Austin, US), Yang Richard Yang (Yale University, US)

In many applications, a wireless ad-hoc network is formed by devices belonging to independent users. Therefore, a challenging problem is to provide incentives to stimulate cooperation. In this paper, we study the routing and packet forwarding games in wireless ad-hoc networks. Unlike previous work which focuses either on routing or on forwarding, we conduct the first comprehensive study on both routing and forwarding. We first uncover a surprising impossibility result --- there does not exist a protocol such that following the protocol to always forward others' traffic is a dominant action. Then we define the concept of a cooperation-optimal protocol and present the design of such a protocol, which consists of a routing protocol and a forwarding protocol. Although our routing protocol also uses the VCG mechanism to compute a lowest cost path for routing, we integrate VCG with a novel cryptographic technique to address the challenge in wireless ad-hoc networks that a link's cost, i.e., its type is determined by two nodes together. We also apply efficient cryptographic techniques to design a forwarding protocol to enforce the routing decision, such that fulfilling the routing decision is the optimal action of each node in the sense that it brings the maximum expected utility to the node. Additionally, we extend our framework to a practical radio propagation model where a transmission is successful with a probability. We evaluate our protocols using simulations. Our evaluations demonstrate that our protocols provide incentives for nodes to forward packets.

Challenge Papers
• Challenges: A Radically New Architecture for Next Generation Mobile Ad-hoc Networks
Ram Ramanathan (BBN Technologies, US)

Despite decades of research and development, mobile ad hoc networks (MANETs) continue to lag behind wireline networks in terms of latency, capacity and robustness. We contend that a key reason for this is the way MANETs are thought about and architected today. We propose a radically new architecture that we believe will elevate MANETs to a performance plane on par with wireline networks. Our design concept for next generation MANETs is based on several revolutionary ideas - 1) a relay-oriented physical layer that selectively switches incoming packets "on-the-fly" without the intervention of the MAC or network layers, 2) a path-centric medium access mechanism that acquires the floor for not just the next, but several hops toward the destination, 3) cooperative transport of packets in stages using diversity combining. Our vision is to enable emerging and future very-low-latency, very-high-bandwidth applications to work seamlessly over large MANETs. Realizing our vision requires solving a number of challenging problems. We enumerate and briefly discuss these exciting new research areas.

• Challenges: Communication through Silence in Wireless Sensor Networks
Yujie Zhu (Georgia Institute of Technology, US), Raghupathy Sivakumar (Georgia Institute of Technology, US)

Wireless sensor networks (WSNs) are typically characterized by a limited energy supply at sensor nodes. Hence, energy efficiency is an important issue in the system design and operation of WSNs. In this paper, we introduce a novel communication paradigm that enables energy-efficient information delivery in wireless sensor networks. Compared with traditional communication strategies, the proposed scheme explores a new dimension - time, to deliver information efficiently. We refer to the strategy as Communication through Silence (CtS). We identify a key drawback of CtS - energy - throughput trade-off, and explore optimization mechanisms that can alleviate the trade-off. We then present several challenges that need to be overcome, primarily at the medium access control layer of the network protocol stack, in order to realize CtS effectively.

• Challenges: CeTV and Ca-Fi - Cellular and Wi-Fi over CATV
Erez Biton (Clariton Networks, IL), Danny Sade (Clariton Networks, IL), Dan Shklarsky (Clariton Networks, IL), Mota Zussman (Clariton Networks, IL), Gil Zussman (MIT, US)

This paper introduces a novel concept that enables transmitting wireless communication over CATV networks. We present the architecture of a system for Cellular Communication over CATV (CeTV) and review the required modifications to the cable network. These modifications affect only the cable network, thereby enabling the system to operate with unmodified cellular phones. In addition to improving in-building coverage, the CeTV system significantly increases the capacity of the cellular network. We also present the architecture of a Wi-Fi (IEEE 802.11) over CATV (Ca-Fi) system. The implementation of the Ca-Fi system requires improving the MAC protocol used by the Access Points that are deployed within the cable network. However, it does not require modifying the users' devices. We present a few alternative MAC protocols which aim at polling 802.11 stations using the Distributed Coordination Function (DCF). These protocols deal with, and take advantage of the special characteristics of the CATV network. The performance of the proposed protocols is evaluated analytically and via simulation.

802.11 Protocols and Usage
• Design and Evaluation of a new MAC Protocol for Long-Distance 802.11 Mesh Networks
Bhaskaran Raman (Indian Institute of Technology, Kanpur, IN), Kameswari Chebrolu (IIT Kanpur, IN)

802.11 has been used well beyond its original intended use of WLANs. Of particular interest to us in this paper is its use in long-distance mesh networks being designed/used for low-cost rural connectivity. We describe in detail a new MAC protocol, called 2P, that is suited for such networks in terms of efficiency. A significant challenge here is the implementation of this protocol on top of off-the-shelf 802.11 hardware, to preserve the cost benefits. We show how this can be achieved, by exploiting the flexibilities available within Prism2-based chipsets. We then present the dependence of 2P on the network topology, and show that it is indeed possible to design in practice, network topologies compatible with 2P. We describe experimental as well as simulation-based evaluations of 2P, and show that 2P achieves significant performance improvement (as much as 20 times more throughput) over 802.11 CSMA/CA in long-distance mesh networks.

• Model T: An Empirical Model for User Registration Patterns in a Campus Wireless LAN
Ravi Jain (NTT DoCoMo USA Labs, US), Dan Lelescu (DoCoMo USA Laboratories, US), Mahadevan Balakrishnan (DoCoMo Communications Labs, USA, US)

We derive an empirical model for the spatial registration patterns of mobile users as they move within a campus wireless local area network (WLAN) environment and register at different access points. Such a model can be very useful in a variety of simulation studies of the performance of mobile wireless systems, such as that of resource management and mobility management protocols. We base the model on extensive experimental data from a campus WiFi LAN installation, representing traces from about 6000 users over a period of about 2 years. We divide the empirical data available to us into training and test data sets, develop the model based on the training set, and evaluate it against the test set. The model shows that user registration patterns exhibit a distinct hierarchy, and that WLAN access points (APs) can be clustered based on registration patterns. Cluster size distributions are highly skewed, as are intra-cluster transition probabilities and intra-cluster trace lengths, which can all be modeled well by the heavy-tailed Weibull distribution. The fraction of popular APs in a cluster, as a function of cluster size, can be modeled by exponential distributions. There is general similarity across hierarchies, in that inter-cluster registration patterns tend to have the same characteristics and distributions as intra-cluster patterns. We define a set of metrics that evaluate how well the model actually captures the empirical features it is trying to represent. We generate synthetic traces for intra-cluster transitions, inter-cluster transitions, and complete traces, and compare them against the corresponding traces derived from the test set. We find that the synthetic traces agree very well with the test set in terms of the metrics. The user of the model has the opportunity to use the model as is, only modifying, for example, the number of mobile users being simulated. We illustrate how the user of the model can also modify other model parameters, such as the degree of randomness in registration patterns. We also compare the model to a simple random walk model as a baseline, and show the latter is not at all representative of the real data. We close with a brief discussion of further work to refine and extend the model.

• Self-Management in Chaotic Wireless Deployments
Aditya Akella (Carnegie Mellon University, US), Glenn Judd (Carnegie Mellon University, US), Srinivasan Seshan (Carnegie Mellon University, US), Peter Steenkiste (Carnegie Mellon University, US)

Over the past few years, wireless networing technologies have made vast forays into our daily lives. Today, one can find 802.11 hardware and other personal wireless technology employed at homes, shopping malls, coffee shops and airports. Present-day wireless network deployments bear two important properties: they are unplanned, with most Access Points (APs) deployed by users in a spontaneous manner, resulting in highly variable AP densities; and they are unmanaged, since manually configuring and managing a wireless network is very complicated. We refer to such wireless deployments as being chaotic. In this paper, we present a study of the impact of interference in chaotic 802.11 deployments on end-client performance. First, using large-scale measurement data from several cities, we show that tens of APs are deployed in close proximity of each other. Moreover, most APs are not configured to minimize interference with their neighbors. We then perform trace-driven simulations to show that the performance of end-clients could suffer significantly in chaotic wireless deployments. Furthermore, we argue that end-client experience could be significantly improved by making chaotic wireless networks self-managing. We design and evaluate automated power control and rate adaptation algorithms (for both APs and clients) to minimize interference among neighboring APs, while ensuring robust end-client performance.

Analytical Models of Wireless Networks
• Modeling Media Access in Embedded Two-Flow Topologies of Multi-hop Wireless Networks
Michele Garetto (Politecnico di Torino, IT), Jingpu Shi (Rice University, US), Edward W. Knightly (Rice University, US)

In this paper, we decompose a large- or small-scale multi-hop wireless network into embedded subgraphs, each consisting of four nodes and two flow pairs. We systematically study all twelve possible topologies that arise according to whether the different nodes are in radio range of each other. We show that under both a random spatial distribution of nodes and random waypoint mobility with shortest-path routing, a critical scenario is a class in which the channel state shared by the two flows is not only incomplete (i.e., the graph is not fully connected), but there is also asymmetry in the state between the two flows. We develop an accurate analytical model validated by simulations to characterize the long-term unfairness that naturally arises when CSMA with two- or four-way handshake is employed as a random access protocol. Moreover, we show that another key class of topologies consists of incomplete but symmetric shared state. We show via modeling and simulations that in this case, the system achieves long-term fairness, yet endures significant durations in which one flow dominates channel access with many repeated transmissions before relinquishing the channel. The model predicts the time-scales of this unfairness as a function of system parameters such as the maximum retransmission limit.

• An analytical model for the dimensioning of a GPRS/EDGE network with a capacity constraint on group of cells
Georges Nogueira (LIP6 - Université Pierre et Marie Curie, FR), Bruno Baynat (Université Pierre et Marie Curie-LIP6, FR), Pierre Eisenmann (Nortel Networks, FR)

This paper is a contribution to the generic problem of having simple and accurate models to dimension radio cells with data traffic on a GPRS or EDGE network. It addresses the issue of capacity limitation in a given cell due to coupling with other cells because of a central equipment or transmission link of limited capacity. A mobile can't access the requested resource although it is alone in a cell, because the global capacity limit is reached due to traffic on other cells. Our objective was to avoid the derivation of any multi-dimensional Markovian (or semi-Markovian) model, where each dimension corresponds to a given cell of the system. Indeed, such direct extensions would be of non-manageable complexity when the number of cells subjected to the global capacity limit is large. Instead, we derive an analytical aggregate'' model that captures in an aggregate way the coupling between cells. We show that the performance parameters of the GPRS/EDGE network can be derived from this model instantaneously and with a very good accuracy. Finally, as our modeling framework allows very fast computations, we show how to use it to perform complex iterative dimensioning studies.

Bazaars, Services, and Systems
• MoB: A Mobile Bazaar for Wide-area Wireless Services
Rajiv Chakravorty (University of Wisconsin-Madison, US), Sulabh Agarwal (Unaffiliated, US), Suman Banerjee (University of Wisconsin-Madison, US), Ian Pratt (Cambridge University, UK)

We introduce MoB, an infratructure for collaborative wide-area wireless data services. MoB proposes to change the current model of data services in the following fundamental ways: (1) it decouples infrastructure providers from services providers and enables fine-grained competition, (2) it allows service interactions on arbitrary timescales, and, (3) it promotes flexible composition of these fine-grained service interactions based on user and application needs. At the heart of MoB is an open market architecture in which mobile users can opportunistically trade various services with each other in a flexible manner. In this paper we first describe the overall architecture of MoB including various enablers like user reputation management, incentive management, and accounting services. We next present our experience from both simulations as well as our prototype implementation of MoB in enhancing application performance in three different scenarios --- peer-to-peer style file searches, media streaming, and location-enhanced services.

• PeopleNet: Engineering A Wireless Virtual Social Network
Mehul Motani (National University of Singapore, SG), Vikram Srinivasan (National University of Singapore, SG), Pavan Nuggehalli (Indian Institute of Science, IN)

People often seek information by asking other people even when they have access to vast reservoirs of information such as the Internet and libraries. This is because people are great sources of unique information, especially information which is location-specific, community-specific and time-specific. Social networking is effective because centralized databases often cannot store this type of information. In this paper, we conceive a wireless virtual social network which mimics the way people seek information via social networking. Specifically, we propose PeopleNet, a simple and scalable architecture for efficient information search in a distributed manner. PeopleNet uses the infrastructure to propagate queries of a given type to users in specific geographic locations, called bazaars. Within each bazaar, the query is further propagated between neighboring nodes via peer-to-peer connectivity until it finds a matching query. The PeopleNet architecture can overlay easily on existing cellular infrastructure and entails minimal software installation. We identify three metrics for system performance viz., (i) probability of a match, (ii) time to find a match and (iii) number of matches found by a query. We describe two simple models, called the swap and spread models, for query propagation within a bazaar. We qualitatively argue that the swap model is better with respect to the performance metrics identified and demonstrate this via simulations . Next, we compute analytically the probability of match for the swap model. We show that the probability of match can be significantly improved if, prior to swapping queries, the nodes exchange some limited information about their buffer contents. We propose a simple greedy algorithm which uses this limited information to decide which queries to swap. We show via simulation that this algorithm achieves significantly better performance. Overall our results demonstrate that PeopleNet, with its bazaar concept and peer-to-peer query propagation, can provide a simple and efficient mechanism for seeking information.

• Experimental Platform for Mobile Information Systems
Rudi Belotti (ETH Zurich, CH), Corsin Decurtins (ETH Zurich, CH), Moira Norrie (ETH Zurich, CH), Beat Signer (ETH Zurich, CH), Ljiljana Vukelja (ETH Zurich, CH)

Interaction design is a major issue for mobile information systems in terms of not only the choice of input-output channels and presentation of information, but also the application of context-awareness. To support experimentation with these factors, we have developed a platform that supports the rapid prototyping of multi-channel, multi-modal, context-aware applications. The paper presents the main components of the platform and describes how it was used to develop a tourist information system for an international arts festival where interaction was based on a combination of speech input-output and interactive paper.

Sensor Networks
• Using Mobile Relays to Prolong the Lifetime of Wireless Sensor Networks
Wang Wei (National University of Singapore, SG), Vikram Srinivasan (National University of Singapore, SG), Chua Kee Chaing (NUS, Singapore, SG)

In this paper we investigate the benefits of a heterogeneous architecture for wireless sensor networks composed of a few resource rich mobile nodes and a large number of simple static nodes. These mobile nodes can either act as mobile relays or mobile sinks. To investigate the performance of these two options and the trade-offs associated with these two options, we first consider a finite network. We then compute the lifetime for different routing algorithms for three cases (i) when the network is all static (ii) when there is one mobile sink and (iii) when there is one mobile relay. We find that using the mobile node as a sink results in the maximum improvement in lifetime. We contend however that in hostile terrains, it might not always be possible for the sink to be mobile. We then investigate the performance of a large dense network with one mobile relay and show that the improvement in network lifetime over an all static network is upper bounded by a factor of four. Also, the proof implies that the mobile relay needs to stay only within a two hop radius of the sink. We then construct a joint mobility and routing algorithm which comes close to the upper bound. However this algorithm requires all the nodes in the network to be aware of the location of the network. We then construct an alternative algorithm, which achieves the same performance, but requires only a limited number of nodes in the network to be aware of the location of the mobile. We finally compare the performance of the mobile relay and mobile sink and show that for a densely deployed sensor field of radius R hops, we require O(R) mobile relays to achieve the same performance as the mobile sink.

• Barrier Coverage With Wireless Sensors
Santosh Kumar (The Ohio State University, US), Ten Hwang Lai (The Ohio State University, US), Anish Arora (The Ohio State University, US)

In old times, castles were surrounded by moats (deep trenches filled with water, and even alligators) to thwart or discourage intrusion attempts. One can now replace such barriers with stealthy and wireless sensors. In this paper, we develop theoretical foundations for laying barriers of wireless sensors. We define the notion of k-barrier coverage of a belt region using wireless sensors. We propose efficient algorithms using which one can quickly determine, after deploying the sensors, whether a region is k-barrier covered. Next, we establish the optimal deployment pattern to achieve k-barrier coverage when deploying sensors deterministically. Finally, we consider barrier coverage with high probability when sensors are deployed randomly. We introduce two notions of probabilistic barrier coverage in a belt region -- weak and strong barrier coverage. While weak barrier-coverage with high probability guarantees the detection of intruders as they cross a barrier of stealthy sensors, a sensor network providing strong barrier-coverage with high probability (at the expense of more sensors) guarantees the detection of all intruders crossing a barrier of sensors, even when the sensors are not stealthy. Both types of barrier coverage require significantly less number of sensors than full-coverage, where every point in the region needs to be covered. We derive critical conditions for weak k-barrier coverage, using which one can compute the minimum number of sensors needed to provide weak k-barrier coverage with high probability in a given belt region. Deriving critical conditions for strong k-barrier coverage for a belt region is still an open problem.

• Cross-Layer Optimization for Routing Data Traffic in UWB based sensor networks
Yi Shi (Virginia Tech, US), Y. Thomas Hou (Virginia Tech, US), Hanif D. Sherali (Virginia Tech, US), Scott F. Midkiff (Virginia Tech, US)

Ultra-wideband (UWB) has great potential for wireless communications in emerging applications such as sensor networks. This paper considers UWB-based sensor networks and studies the following problem: given a set of source sensor nodes in the network each generating a certain data rate, is it possible to relay all these rates successfully to the base-station? We follow a cross-layer optimization approach, with joint consideration of link layer scheduling, power control, and network layer routing. The optimization problem is formulated as a non-linear programming problem. For small sized networks, we develop a powerful approximation solution procedure to this problem based on the branch-and-bound approach and the novel Reformulation-Linearization Technique (RLT). For large-sized networks, we propose an efficient heuristic algorithm by partitioning the sensor network into a core centered around the base-station and an edge that is outside the core. We also provide a closed-form analysis for the maximum rate that a base-station can receive. Simulation results exhibit the efficacy of our proposed optimization solution procedure and demonstrate the importance of the cross-layer approach to UWB-based sensor networks.