As cyber-attacks on networks become stealthier, monitoring techniques relying on low-rate packet sampling may prove insufficient to detect attacks. While various methods, such as truncating packets, flow-based sampling, and adaptive sampling rates, have been proposed to enhance detection rates and ease capability limitations, it remains challenging to perform sufficient sampling at line speed and high rates at a single sampling point due to limited CPU or bandwidth capacity and fluctuating network traffic. To address these challenges, we propose CoordSamp, a system that distributes the sampling workload across multiple sampling points and coordinates their actions to avoid duplicate sampling of the same packet. This design enables scalable, resource-aware monitoring—particularly suited for dynamic, agentless cloud-based environments—relying solely on network-level deployment that can be dynamically assigned and adjusted by the provider. We develop a coordinated sampling algorithm on multiple P4-programmable switches and show that the algorithm ensures coordination among multiple sampling points for each flow, preventing duplicate samples, with negligible network overhead and real-time configurability. At its core, CoordSamp separatesoffline placement—the budgeted selection of sampling points—fromonline allocation—the capacity-aware assignment of sampling tasks—allowing practical deployment in hybrid networks that combine programmable and legacy switches. We formulate sampling point placement as budgeted maximum multi-coverage problems, solving them optimally in pseudo-polynomial time. Our system far outperforms those based on greedy placement along many key dimensions.

Providing a high-quality real-time video streaming experience to mobile users is one of the biggest challenges in cellular networks. This is due to the need of these services for high rates with low variability, i.e., stable throughput, which is not easily accomplished given the competition among (an ever-increasing number of) users for limited network resources and the high variability of their channel conditions. A way to improve the user experience is by exploiting users’ buffers and the ability to provide a constant data rate to everyone, as one of the initially envisioned features of 5G networks. However, it was already shown that the latter is not very efficient, neither in terms of the achievable data rates nor in terms of the amount of resources left unused. In this paper, we provide a theoretical-analysis framework for resource allocation in 5G networks that leads to an improved user experience when watching live video while providing a constant video resolution at almost all times. We do this by solving four problems, in which the objectives are to provide the highest achievable video resolution to all single-class and multi-class users, and to maximize the number of users that experience a given video resolution. The analysis is validated by simulations that are run on publicly-available traces. We also compare the performance of our approach against other techniques for different Quality of Experience metrics. Results show that performance can be improved by at least 15% with our approach compared to state of the art.

Cloud file systems offer organizations a scalable and reliable file storage solution. However, cloud file systems have become prime targets for adversaries, and traditional designs are not equipped to protect organizations against the myriad of attacks that may be initiated by a malicious cloud provider, co-tenant, or end-client. Recently proposed designs leveraging cryptographic techniques and trusted execution environments (TEEs) still force organizations to make undesirable trade-offs, consequently leading to either security, functional, or performance limitations. In this paper, we introduceBFS, a cloud file system that leverages the security capabilities provided by TEEs to bootstrap new security protocols that deliver strong security guarantees, high-performance, and a transparent POSIX-like interface to clients.BFSdelivers stronger security guarantees and up to a$2.5\times$speedup over a state-of-the-art secure file system. Moreover, compared to the industry standard NFS,BFSachieves up to$2.2\times$speedups across micro-benchmarks and incurs$< 1\times$overhead for most macro-benchmark workloads.BFSdemonstrates a holistic cloud file system design that does not sacrifice an organizations’ security yet can embrace all of the functional and performance advantages of outsourcing.

Edge computing has become a very popular service that enables mobile devices to run complex tasks with the help of network-based computing resources. However, edge clouds are often resource-constrained, which makes resource allocation a challenging issue. In addition, edge cloud servers must make allocation decisions with only limited information available, since the arrival of future client tasks might be impossible to predict, and the states and behavior of neighboring servers might be obscured. We focus on a distributed resource allocation method in which servers operate independently and do not communicate with each other, but interact with clients (tasks) to make allocation decisions. We follow a two-round bidding approach to assign tasks to edge cloud servers, and servers are allowed to preempt previous tasks to allocate more useful ones. We evaluate the performance of our system using realistic simulations and real-world trace data from a high-performance computing cluster. Results show that our heuristic improves system-wide performance by 20-25% over previous work when accounting for the time taken by each approach. In this way, an ideal trade-off between performance and speed is achieved.

Software-defined networking (SDN) is a centralized, dynamic, and programmable network management technology that enables flexible traffic control and scalability. SDN facilitates network administration through a centralized view of the underlying physical topology; tampering with this topology view can result in catastrophic damage to network management and security. To underscore this issue, we introduce Marionette, a new topology poisoning technique that manipulates OpenFlow link discovery packet forwarding to alter topology information. Our approach exposes an overlooked yet widespread attack vector, distinguishing itself from traditional link fabrication attacks that tamper, spoof, or relay discovery packets at the data plane. Unlike localized attacks observed in existing methods, our technique introduces a globalized topology poisoning attack that leverages control privileges. Marionette implements a reinforcement learning algorithm to compute a poisoned topology target, and injects flow entries to achieve a long-lived stealthy attack. Our evaluation shows that Marionette successfully attacks five open-source controllers and nine OpenFlow-based discovery protocols. Marionette overcomes the state-of-the-art topology poisoning defenses, showcasing a new class of topology poisoning that initiates on the control plane. This security vulnerability was ethically disclosed to OpenDaylight, and CVE-2024-37018 has been assigned.

As cyber-attacks on networks become more stealthy, monitoring techniques relying on low-rate packet sampling may prove insufficient to detect attacks. While various sampling methods have been proposed to address capacity limitations and enhance detection rates, achieving sampling at line speed at a single point remains challenging due to limited CPU or bandwidth capacity at sampling points. In this paper, we propose harnessing coordinating sampling across switches to create a unified system that can dynamically activate sampling points to meet sampling rate needs. We introduce and implement a coordinated sampling algorithm on multiple P4-programmable switches and show that the algorithm ensures coordination among multiple sampling points for each flow, preventing duplicate samples, with negligible network overhead and real-time configurability. We formulate sampling point placement as budgeted maximum multi-coverage problems, solving them optimally in pseudo-polynomial time. We show our system far outperforms those based on greedy algorithms along many key dimensions.

Through using edge computing services, mobile devices can run complex tasks with the help of network-based computing resources. However, servers in the edge cloud are not only constrained to limited resources, but also must make allocation decisions with only limited information available. The clients requesting computing resources may also have limited information about the servers available to them. We focus on a distributed resource allocation method in which servers operate independently and do not communicate with each other, but interact with clients to make allocation decisions for those clients’ tasks. We follow a two-round bidding approach to assign tasks to edge cloud servers. Servers may choose to preempt previous tasks to allocate more useful ones, and clients may choose to track the outcomes of their tasks to inform their future decisions. Results show that user learning improves system performance by 50-80% when servers are heterogeneous in pricing aggressiveness.

Crowdsourcing data collection from a network of mobile devices is useful in various applications. Mobile devices store a large amount of visual data that can aid in different application scenarios. Trained Convolutional Neural Networks (CNNs) can be deployed on mobile devices to be used in searching for objects of interest. Querying for novel objects, for which models have not been trained yet, presents some unique challenges. When novel objects are queried, new models must be trained and distributed to all edge devices. In this paper, we propose an efficient method and a system, called EDIR, which enables answering these queries while taking into account the bandwidth limitations encountered in wireless networks, as well as the limited energy and computational power on mobile devices. Through extensive experimentation, we show that using distance-based classifiers, specifically those relying on the Cosine distance, leads to more efficient utilization of network resources by reducing the number of false positives. We perform analysis that enables the requester to tune the parameters of interest before issuing the query, and validate our theoretical results. EDIR reduces the amount of transferred data by more than 45% compared to other approaches while simultaneously achieving a good F1 score.

While LTE networks are known to provide relatively high data rates, reaching values as high as tens of Mbps, these rates exhibit considerable variability over time. The rate variability hurts especially the performance of applications and services that require stable data rates, such as real-time video streaming, online gaming, virtual reality, augmented reality, etc. 5G emerged as a solution to this as well as to many other problems. However, it has been shown that strict constant data rates come at the cost of underutilized network resources, resulting in inefficient operation of cellular networks. Therefore, a tradeoff between the data rate stability, important to cellular users, and the efficient utilization of resources, important to network operators, needs to be taken into account. To that end, in this paper, we consider the problem of allocating all the network resources to cellular users in such a way that it provides as high a data rate as possible to all users while limiting the rate variation within tight bounds. We do this for different scenarios in terms of the user activity, user type, and the nature of the policy. Firstly, we consider the case of static allocation policy, irrespective of channel conditions, for users that are always active. Then, for these same users, we look at the case when resources are allocated dynamically over time. Secondly, we consider static and dynamic policies for users that are only intermittently active. Thirdly, we consider the case with users having different Service Level Agreements (SLAs) with the cellular operator. Furthermore, we run extensive simulations with input parameters from real traces. Results show that allocating the resources dynamically improves performance in terms of data rates over static allocation mechanisms by an additional 10%, and that allowing a slightly higher outage in not complying with the guaranteed data rate further increases the user's throughput by at least 20%.

While one of the main features of 5G networks is provisioning very high rates with low (or no) variability to cellular users, it has been shown that this turns out to be very ineffective for operators because it leads to an abundance of unused network resources. Yet, reallocating the unused resources to the same users, after providing them with the same constant rate, increases back the variability in data rates. A more efficient way would be to provide different low-variability data rates to the users depending on their channel conditions while trying to bring the wasted resources to the lowest possible extent. To that end, in this paper, two approaches are considered; one with reserved resources for every user and the other where the amount of resources is decided on the fly, depending on their current channel conditions. Then, for each approach, we look at different allocation policies and derive the corresponding maximum achievable constant rate for every user jointly with the level of resource utilization, showing which policy is more beneficial. Further, the performance is evaluated on a real 5G trace using both extensive simulations and real measurements conducted on OpenAirInterface. Results show that no-resource reservation policies increase the utilization of resources and data rates at the expense of increased rate variability across all the users. Moreover, all the policies proposed in this paper outperform state-of-the-art approaches by at least 2×, bringing the waste of resources down to 15%.

Load balancing in software-defined networks (SDNs) is commonly realized with a centralized architecture. Dynamic load balancing relies on the SDN controller to periodically collect traffic statistics from network switches and make decisions in a timely manner. In this paper, we examine the extent to which an adversary that has compromised a switch can influence the load balancing algorithm by misreporting its own traffic statistics. We design an attack that allows an adversary to perform preliminary reconnaissance, which means learning network traffic distributions and setting attack parameters, and then accurately model and estimate the reward from misreporting while evading detection. Our evaluation offers three insights: 1) network traffic exhibits discernible patterns by reconnaissance; 2) the reconnaissance can be used to design misreporting attacks that can effectively draw unfair proportions of network traffic to the adversary under the guise of honest behavior; and 3) reconnaissance itself can be accelerated by misreporting to launch more targeted attacks.

Competitive demand for network resources has only increased during the emergence of 5G next generation cellular technology. As video streaming accounts for an overwhelming percentage of this demand, the importance of considering the often-neglected Quality of Experience (QoE) metric is essential to ensure network resources are allocated in the most effective manner. Generalized network throughput metrics are insufficient in capturing the full human experience as increased data rates do not necessarily translate to improvements in user utility. Our study compares the efficacy of existing network allocation algorithms and proposes new approaches to 5G network resource allocation schemes using a more inclusive snapshot of user demand. We provide recommendations on which approach provides the highest QoE performance and suggestions for future network-side improvements. We further propose a QoE-driven network resource allocation (QENA) algorithm that shows a 20% improvement in overall average QoE across a large set of heterogeneous users.

As IoT devices are becoming widely deployed, there exist many threats to IoT-based systems due to their inherent vulnerabilities. One effective approach to improving IoT security is to deploy IoT honeypot systems, which can collect attack information and reveal the methods and strategies used by attackers. However, building high-interaction IoT honeypots is challenging due to the heterogeneity of IoT devices. Vulnerabilities in IoT devices typically depend on specific device types or firmware versions, which encourages attackers to perform pre-attack checks to gather device information before launching attacks. Moreover, conventional honeypots are easily detected because their replying logic differs from that of the IoT devices they try to mimic.To address these problems, we develop an adaptive high-interaction honeypot for IoT devices, called em HoneyIoT. We first build a real device based attack trace collection system to learn how attackers interact with IoT devices. We then model the attack behavior through markov decision process and leverage reinforcement learning techniques to learn the best responses to engage attackers based on the attack trace. We also use differential analysis techniques to mutate response values in some fields to generate high-fidelity responses.HoneyIoT has been deployed on the public Internet. Experimental results show that HoneyIoT can effectively bypass the pre-attack checks and mislead the attackers into uploading malware. Furthermore, HoneyIoT is covert against widely used reconnaissance and honeypot detection tools.

Crowdsourced image processing has the potential to vastly impact response timeliness in various emergency situations. Because images can provide extremely important information regarding an event of interest (hits), sending the right images to an analyzer as soon as possible is of crucial importance. In this paper, we consider the problem of optimally assigning resources, both local (CPUs in phones) and remote (network-based GPUs) to mobile devices for processing images, ultimately sending those of interest to a centralized entity while also accounting for the energy consumption at the distributed nodes. To that end, we use the dual-path Network Utility Maximization (NUM) framework, coupled with a hit-ratio estimator and energy costs, to enable a distributed implementation of the system. We include analysis of different hit-ratio estimators using realistic trace data, first considering immediate and then delayed feedback. We address accuracy concerns when estimating the likelihood of future imagehitsand provide a window-based heuristic for scenarios when hit-ratio feedback is severely delayed. Our TCP-inspired window-method predicts both imagehitlikelihood and current wireless network congestion with great effectiveness. Results are validated using both synthetic simulations and real-life traces.

As mobile devices become more prevalent in everyday life and the amount of recorded and stored videos increases, efficient techniques for searching video content become more important. When a user sends a query searching for a specific action in a large amount of data, the goal is to respond to the query accurately and fast. In this paper, we address the problem of responding to queries which search for specific actions in mobile devices in a timely manner by utilizing both visual and audio processing approaches. We build a system, called VidQ, which consists of several stages, and that uses various Convolutional Neural Networks (CNNs) and Speech APIs to respond to such queries. As the state-of-the-art computer vision and speech algorithms are computationally intensive, we use servers with GPUs to assist mobile users in the process. After a query is issued, we identify the different stages of processing that will take place. Then, we identify the order of these stages. Finally, solving an optimization problem that captures the system behavior, we distribute the process among the available network resources to minimize the processing time. Results show that VidQ reduces the completion time by at least 50% compared to other approaches.

Massive Machine-Type Communications (mMTC) are one of the three types of services that should be supported by 5G networks. These are distinguished by the need to serve a large number of devices which are characterized by non-intensive traffic and low energy consumption. While the sporadic nature of the mMTC traffic does not pose an exertion to efficient network operation, multiplexing the traffic from a large number of these devices within the cell certainly does. Therefore, planning carefully the network resources for this traffic is of paramount importance. To do this, the statistics of the traffic pattern that arrives at the base station should be known. To this end, in this paper, we derive the distribution of the inter-arrival times of the traffic at the base station from a general number of mMTC users within the cell, assuming a generic distribution of the traffic pattern by individual users. We validate our results on traces. Results show that adding more mMTC users in the cell increases the variability of the traffic pattern at the base station almost linearly, which is not the case with increasing the traffic generation rates.

Edge computing has become a very popular service that enables mobile devices to run complex tasks with the help of network-based computing resources. However, edge clouds are often resource-constrained, which makes resource allocation a challenging issue. We focus on a distributed resource allocation method in which servers operate independently and do not communicate with each other, but interact with clients (tasks) to make allocation decisions. This provides robustness and does not require service providers to share information about their configurations or workloads. We utilize a two-round bidding approach of assigning tasks to edge cloud servers. We consider a preemption-enabled system in which servers may stop a previous task in order to run a more useful one. We evaluate the performance of our system using realistic simulations and real-world trace data from a high-performance computing cluster. Results show that our approach is reasonably close to optimal assignment, while saving 50–70 % of the original computation time.

The quantity and capabilities of smart devices and sensors deployed as part of the Internet of Things (IoT) and accessible via remote microservices is set to rise dramatically as the provision of interactive data streaming increases. This introduces opportunities to rapidly construct new applications by interconnecting these microservices in different workflow configurations. The challenge is to discover the required microservices, including those from trusted partners and the wider community, whilst being able to operate robustly under diverse networking conditions. This paper outlines a workflow approach that provides decentralized discovery and orchestration of verifiably trustable services in support of multi-party operations. The approach is based on adoption of patterns from self-sovereign identity research, notably Verifiable Credentials, to share information amongst peers based on attestations of service descriptions and prior service usage in a privacy preserving and secure manner. This provides a dynamic, trust-based framework for ratifying and evaluating the qualities of different services. Collating these new service descriptions and integrating with existing decentralized workflow research based on vector symbolic architecture (VSA) provides an enhanced semantic search space for efficient and trusted service discovery that is necessary to support a diverse range of emerging edge-computing environments. An architecture for a dynamic decentralized service discovery system, is designed, and described through application to a scenario which uses trusted peers’ reported experiences of an anomaly detection service to determine service selection.

High quality video streaming for mobile devices implies high energy consumption due to the transmitted data and the variation of wireless signals. As an example, transmissions in mobile scenarios (e.g., inside a moving bus) consumes more energy for devices than when accessing from a static environment (e.g., at home). The QoE for the user does not substantially increase when watching high bitrate videos in a vibrating environment (i.e., a moving vehicle), as the context, in this case vehicle’s vibration, affects the perceived QoE. To address this problem, we propose to save energy by considering the context (environment) of video streaming. To model the impact of context, we exploit the embedded accelerometer in smartphones to record the vibration level during video streaming. Based on quality assessment experiments, we collect traces and model the impact of video bitrate and vibration level on QoE, and model the impact of video bitrate and signal strength on power consumption. Based on the QoE model and the power model, we formulate the context-aware and energy-aware video streaming problem as an optimization problem. We present an optimal algorithm which can maximize QoE and minimize energy. Since the optimal algorithm requires perfect knowledge of future tasks, we propose an online bitrate selection algorithm. To further improve the performance of the online algorithm, we propose a crowdsourcing based bitrate selection algorithm. Through real measurements and trace-driven simulations, we demonstrate that the proposed algorithms can significantly outperform existing approaches when considering both energy and QoE.

Consistent rate provisioning is one of the most prominent features envisioned for the next generation of cellular networks (5G), as a pivotal condition to an improved user experience, especially for services like live video streaming, online gaming, etc. However, prior research has shown that providing a consistent rate, while very beneficial to the QoS of mobile users, can result in a severe underutilization of the available resources, leading to a very inefficient operation of cellular networks. One of the ways of increasing resource allocation efficiency is by reallocating the unused resources to the same users. To this end, in this paper we quantify the benefits offered by different reallocation policies both for the mobile operator and users. We then determine, based on theoretical analysis, the optimal policies to follow for different optimization objectives. First, we focus on increasing the efficiency (total throughput) of the cellular network operator in a cell and then on providing proportional and max-min fairness to mobile users. The analysis captures the correlation of the user's channel quality in contiguous frames by using Markov chains. The outcomes of the analysis hold both for users that are always active in a given cell, and for users whose activity is intermittent. We also analyze the case with two classes of consistent users:premiumandregular. The theoretical analysis is validated by extensive synthetic simulations and simulations run on real-life traces. We also compare the performance of different reallocation policies with that of a benchmark and show that the optimal reallocation policy for a given objective improves the performance by at least 35 percent.

Multilevel security (MLS) systems control access to data by formalizing permissible and impermissible information flows between data sources and destinations (e.g., database servers and clients) fixed with distinct security labels. In computer networks, MLS systems have been used to prevent unauthorized data disclosure in shared-infrastructure settings where network hosts and devices may fall within different trust domains (e.g., in multi-tenant cloud networks or wireless mesh networks). However, current MLS systems assume static network behavior—thus preventing the network from being practically usable in the presence of dynamic network events that frequent unstable network environments, including sudden changes in traffic patterns, link failures, and topology changes as a result of device movement or intermittent device connectivity. In this paper, we introduceMLS-Enforcer, a software-defined networking (SDN) controller application that can efficiently deploy network-level MLS policies while retaining the ability to securely relabel network nodes under changing topology state and network traffic demands. We model network adaptivity as an integer linear programming problem that reflects a given security policy. We then introduce heuristic relabeling algorithms that achieve near-optimal performance and are more tractable and efficient for larger networks. We validateMLS-Enforceron several network topologies and traffic loads, demonstrating that it can relabel the network to route 90%+ of flows under normal conditions and quickly converge (on the order of seconds for the heuristic algorithms) under changing needs—from small network structure changes to catastrophic failures. This shows that formally secured networks can feasibly be deployed in diverse, changing, and unpredictable environments.

Network intrusion detection systems (NIDS) can be evaded by carefully crafted packets that exploit implementation-level discrepancies between how they are processed on the NIDS and at the endhosts. These discrepancies arise due to the plethora of endhost implementations and evolutions thereof. It is prohibitive to proactively employ a large set of implementations at the NIDS and check incoming packets against all of those. Hence, NIDS typically choose simplified implementations that attempt to approximate and generalize across the different endhost implementations. Unfortunately, this solution is fundamentally flawed since such approximations are bound to have discrepancies with some endhost implementations. In this paper, we develop a lightweight system Themis, which empowers the NIDS in identifying these discrepancies and reactively forking its connection states when any packets with "ambiguities" are encountered. Specifically, Themis incorporates an offline phase in which it extracts models from various popular implementations using symbolic execution. During runtime, it maintains a nondeterministic finite automaton to keep track of the states for each possible implementation. Our extensive evaluations show that Themis is extremely effective and can detect all evasion attacks known to date, while consuming extremely low overhead. En route, we also discovered multiple previously unknown discrepancies that can be exploited to bypass current NIDS.

We study the impact of coupling between the communication and the power networks as it affects a SCADA-based preventive control system. Today power grids use power lines to carry control information between components in the grid and a control center using power line carrier communication (PLCC). Thus a failure in the power grid will cause a failure in the control network and may reduce the capability of preventive control that in turn increases the risk of cascading failures. We pose the problem of allocating a limited number of non-PLCC communication links (e.g., microwave links) that are immune to failures in the power grid to maximize our controllability over the grid under power system failures, so as to maximize the total demand served at the end of cascade. By formulating the problem as a nonlinear integer programming problem, we establish its hardness and identify a generic heuristic that can find an approximate solution within controllable time. We further develop a domain-specific heuristic that utilizes both graph-theoretic and power system information to achieve similar performance as the generic heuristic at a much lower computational complexity. Our evaluations based on a 2, 383-bus Polish system demonstrate that only a few non-PLCC links, when placed correctly, can substantially improve the robustness of the grid as measured by the total demand served at the end of cascade.

Crowdsourcing data collection from a network of mobile devices is useful in various applications. Mobile devices store a large amount of visual data that aid in different situations. Trained CNNs can be deployed on mobile devices to be used in searching for objects of interest. Querying for novel objects, for which models have not been trained, presents unique challenges. When novel objects are queried, new models must be trained and distributed to all edge devices, which can be cumbersome. In this paper we propose EDIR, an efficient method and a system that enables answering these queries while taking into account the bandwidth limitations in wireless networks, and the limited energy and computational power on mobile devices. Results show that EDIR reduces the amount of data transfer by 45%compared to other approaches while achieving a good F1 score.

Edge computing has become a very popular service that enables mobile devices to run complex tasks with the help of network-based computing resources. However, edge clouds are often resource-constrained, which makes resource allocation a challenging issue. We focus on a distributed resource allocation method in which servers operate independently and do not communicate with each other, but interact with clients (tasks) to make allocation decisions. This provides robustness and does not require service providers to share information about their configurations or workloads. We propose a two-round bidding approach of assigning tasks to edge cloud servers, while taking into account various processing requirements and server constraints. We consider cases in which all jobs have equal utility, cases where jobs have different utilities but users do not disclose these utilities to servers, and cases where users disclose the utility of their jobs to servers. We evaluate the performance using extensive realistic simulations. Results show that our approach is very close to an optimal assignment, with discrepancy not exceeding 5%.

The level of deployment of 5G networks is increasing every day, making this cellular technology become ubiquitous soon. Therefore, characterizing the channel quality and signal characteristics of 5G networks is of paramount importance as a first step in understanding the achievable performance of cellular users. Then, it can also serve for other important processes, such as resource planning and admission control. In this paper, we use the results of a publicly available measurement campaign of 5G users conducted by a third party and analyze various figures of merit. The analysis shows that the downlink and uplink rates for static and mobile users can be captured either by a lognormal or a Generalized Pareto distribution. Also, the time spent in the same cell by a mobile (driving) user can be captured to the best extent by a Generalized Pareto distribution. We also show some potential practical applications, among which is the prediction of the number of active users in the cell.

Ultra-Reliable Low-Latency Communications (URLLC) are one of the service types supported by 5G. These are characterized by a high reliability of delivering packets within a short deadline. To fulfill these stringent requirements, a special care must be taken to determine the required data rate of a user, given its traffic intensity and channel conditions. Furthermore, with the network resources being limited and the competition between the users in the cell, an important question that arises is that of admission control, so that the admitted users do not experience performance deterioration. In this paper, we provide the analysis that leads to an admission control policy. We do this for two types of users in terms of their traffic intensities and channel conditions: 1) homogeneous users, and 2) heterogeneous users. We validate our results on a trace. Results show that the number of admitted users depends on the traffic intensity and the worst channel conditions. An increase in traffic intensity by 3 times can decrease the number of admitted users by almost 35%.

Mobile devices collect a large amount of visual data that are useful for many applications. Searching for an object of interest over a network of mobile devices can aid human analysts in a variety of situations. However, processing the information on these devices is a challenge owing to the high computational complexity of the state-of-the-art computer vision algorithms that primarily rely on Convolutional Neural Networks (CNNs). Thus, this paper builds PicSys, a system that enables answering visual search queries on a mobile network. The objective of the system is to minimize the maximum completion time over all devices while taking into account the energy consumption of mobile devices as well. First, PicSys carefully divides the computation into multiple filtering stages, such that only a small percentage of images need to run the entire CNN pipeline. Splitting such CNN computation into multiple stages requires understanding the intermediate CNN features and systematically trading off accuracy for the computation speed. Second, PicSys determines where to run each of the stages of the multi-stage pipeline to fully utilize the available resources. Finally, through extensive experimentation, system implementation, and simulation, we show that PicSys performance is close to optimal and significantly outperforms other standard algorithms.

Convolutional Neural Networks (ConvNets/CNNs) have revolutionized the research in computer vision, due to their ability to capture complex patterns, resulting in high inference accuracies. However, the increasingly complex nature of these neural networks means that they are particularly suited for server computers with powerful GPUs. We envision that deep learning applications will be eventually widely deployed on mobile devices, e.g., smartphones, self-driving cars, and drones. Therefore, in this paper, we aim to understand the resource requirements of CNNs on mobile devices in terms of compute time, memory, and power. First, by deploying several popular CNNs on different mobile CPUs and GPUs, we measure and analyze the performance and resource usage for the CNNs on a layerwise granularity. Our findings point out the potential ways of optimizing the CNN pipelines on mobile devices. Second, we model resource requirements of core computations of CNNs. Finally, based on the measurement and modeling, we build and evaluate our modeling tool, Augur, which takes a CNN configuration (descriptor) as the input and estimates the compute time, memory, and power requirements of the CNN, to give insights about whether and how efficiently a CNN can be run on a given mobile platform.

Ensuring that information flowing through a network is secure from manipulation and eavesdropping by unauthorized parties is an important task for network administrators. Many cyber attacks rely on a lack of network-level information flow controls to successfully compromise a victim network. Once an adversary exploits an initial entry point, they can eavesdrop and move laterally within the network (e.g., scan and penetrate internal nodes) to further their malicious goals. In this article, we propose a novel multilevel security (MLS) framework to enforce a secure inter-node information flow policy within the network and therein vastly reduce the attack surface available to an adversary who has penetrated it. In contrast to prior work on multilevel security in computer networks which relied on enforcing the policy at network endpoints, we leverage the centralization of software-defined networks (SDNs) by moving the task to the controller and providing this service transparently to all network nodes. Our framework, MLSNet, formalizes the generation of a policy compliant network configuration (i.e., set of flow rules on the SDN switches) as network optimization problems, with the objectives of (1) maximizing the number of flows satisfying all security constraints and (2) minimizing the security cost of routing any remaining flows to guarantee availability. We demonstrate that MLSNet can securely and efficiently route flows that satisfy the security constraints and route the remaining flows with a minimal security cost (e.g., route >85% of flows, where the heuristic achieves 89% and 87% of the optimal solutions for the optimization problems).

Mobile edge computing provides the opportunity for wireless users to exploit the power of cloud computing without a large communication delay. To serve data-intensive applications (e.g., video analytics, machine learning tasks) from the edge, we need, in addition to computation resources, storage resources for storing server code and data as well as network bandwidth for receiving user-provided data. Moreover, due to time-varying demands, the code and data placement needs to be adjusted over time, which raises concerns of system stability and operation cost. In this paper, we address these issues by proposing a two-time-scale framework that jointly optimizes service (code and data) placement and request scheduling, while considering storage, communication, computation, and budget constraints. First, by analyzing the hardness of various cases, we completely characterize the complexity of our problem. Next, we develop a polynomial-time service placement algorithm by formulating our problem as a set function optimization, which attains a constant-factor approximation under certain conditions. Furthermore, we develop a polynomial-time request scheduling algorithm by computing the maximum flow in a carefully constructed auxiliary graph, which satisfies hard resource constraints and is provably optimal in the special case where requests have homogeneous resource demands. Extensive synthetic and trace-driven simulations show that the proposed algorithms achieve 90% of the optimal performance.

We address energy-efficient placement of data and analytics components of composite analytics services on a wireless network to minimize execution-time energy consumption (computation and communication) subject to compute, storage and network resource constraints. We introduce an expressive analytics service hypergraph model for representing k-ary composability relationships (k ≥ 2) between various analytics and data components and leverage binary quadratic programming (BQP) to minimize the total energy consumption of a given placement of the analytics hypergraph nodes on the network subject to resource availability constraints. Then, after defining a potential energy functional Φ(·) to model the affinities of analytics components and network resources using analogs of attractive and repulsive forces in physics, we propose a decentralized Metropolis Monte Carlo (MMC) sampling method which seeks to minimize Φ by moving analytics and data on the network. Although Φ is non-convex, using a potential game formulation, we identify conditions under which the algorithm provably converges to a local minimum energy equilibrium placement configuration. Trace-based simulations of the placement of a deep-neural-network analytics service on a realistic wireless network show that for smaller problem instances our MMC algorithm yields placements with total energy within a small factor of BQP and more balanced workload distributions; for larger problems, it yields low-energy configurations while the BQP approach fails.

Crowdsourced image processing has the potential to vastly impact response timeliness in various emergency situations. Because images can provide extremely important information regarding an event of interest, sending the right images to an analyzer as soon as possible is of crucial importance. In this paper, we consider the problem of optimally assigning resources, both local (CPUs in phones) and remote (network-based GPUs) to mobile devices for processing images, ultimately sending those of interest to a centralized entity while also accounting for the energy consumption. To that end, we use the Network Utility Maximization (NUM) framework, coupled with a hit-ratio estimator and energy costs, to enable a distributed implementation of the system. Our results are validated using both synthetic simulations and real-life traces.

Eavesdroppers can exploit exposed packet headers towards attacks that profile clients and their data flows. In this paper, we propose FOG, a framework for effective full and partial header blinding using MIMO, to thwart eavesdroppers. FOG effectively tracks header bits as they traverse physical (PHY) layer sub-systems that perform functions like scrambling and interleaving. It combines multiple blinding signals for more effective and less predictable obfuscation, as compared to using a fixed blinding signal. We implement FOG on the WARP platform and demonstrate via extensive experiments that it yields better obfuscation than prior schemes that deploy full packet blinding. It causes a bit error rate (BER) of > 40 % at an eavesdropper if two blinding streams are sent during header transmissions. Furthermore, even with full header blinding, FOG incurs a very small throughput hit of ≈5% with one blinding stream (and 9 % with two streams). Full packet blinding incurs much higher throughput hits (25 % with one stream and 50 % with two streams).

Densely-deployed femtocell networks are used to enhance wireless coverage in public spaces such as office buildings, subways, and academic buildings. These networks can increase user throughput, but edge users can suffer from co-channel interference and service outages. This paper introduces a distributed algorithm for network configuration, called Radius Reduction and Scheduling (RRS), to improve the performance and fairness of the network. RRS works by jointly adapting femtocell transmission power, allocating user to femtocells, and scheduling resource blocks so as to increase fairness and reduce outage probability in dense femtocell networks. RRS produces a network configuration that guarantees either user or area coverage depending on the management needs. A prototype implementation confirms the benefits of RRS in a real environment. Furthermore, extensive simulations show that RRS reduces the outage probability of up to 50%, and provides better fairness, with an increase in Jain's index of 190%, with respect to a baseline algorithm which works with fixed power and best-effort scheduling and to a previous approach to resource management in femtocell networks.

The vast adoption of mobile devices with cameras has greatly contributed to the proliferation of the creation and distribution of videos. For a variety of purposes, valuable information may be extracted from these videos. While the computational capability of mobile devices has greatly improved recently, video processing is still a demanding task for mobile devices. We design an on-demand video processing system, NetVision, that performs distributed video processing using deep learning across a wireless network of mobile and edge devices to answer queries while minimizing the query response time. However, the problem of minimal query response time for processing videos stored across a network is a strongly NP-hard problem. To deal with this, we design a greedy algorithm with bounded performance. To further deal with the dynamics of the transmission rate between mobile and edge devices, we design an adaptive algorithm. We built NetVision and deployed it on a small testbed. Based on the measurements of the testbed and by extensive simulations, we show that the greedy algorithm is close to the optimum and the adaptive algorithm performs better with more dynamic transmission rates. We then perform experiments on the small testbed to examine the realized system performance in both stationary networks and mobile networks.

Providing a consistent data rate to users with a highly dynamic activity in a cellular network is a very important feature of 5G. This will lead to increased user satisfaction with services such as video-streaming, online gaming, etc. Knowing that resources are constrained, operators must limit the number of users in the cell, so that admitted users do not experience performance deterioration. In this paper, we consider the problem of admission control for consistent users in 5G cellular systems. We consider two types of users in terms of their rate distributions: 1) homogeneous users, and 2) heterogeneous users. For each user type, we perform the analysis for two scenarios: constant number of users, and random number of users. The analysis is followed by realistic simulations to show that our models can provide satisfactory results in realistic scenarios as well. We also show that the number of admitted users can be significantly increased (up to 3 ×) by allowing a slight deterioration in the QoS.

Consistent rate provisioning is one of the most prominent features envisioned in next generation of cellular networks (5G). However, it has been shown that providing a consistent data rate to users leads to severe underutilization of the available resources, making the cellular operator function very inefficiently. A possible way to increase the efficiency is by reallocating the unused resources to the same users. In this paper, we quantify the benefits offered by different reallocation policies both for mobile operator and the users. First, we focus on increasing the efficiency (total throughput) of the cellular network operator and then on providing fairness to mobile users. In both cases, we determine the optimal policy. The theoretical analysis is followed by extensive realistic simulations, where we compare the performance of different reallocation policies with that of a benchmark model (fair share of the resources with no consistency), and show that the right reallocation policy improves the performance significantly.

Mobile edge computing allows wireless users to exploit the power of cloud computing without the large communication delay. To serve data-intensive applications (e.g., augmented reality, video analytics) from the edge, we need, in addition to CPU cycles and memory for computation, storage resource for storing server data and network bandwidth for receiving user-provided data. Moreover, the data placement needs to be adapted over time to serve time-varying demands, while considering system stability and operation cost. We address this problem by proposing a two-time-scale framework that jointly optimizes service (data & code) placement and request scheduling, under storage, communication, computation, and budget constraints. We fully characterize the complexity of our problem by analyzing the hardness of various cases. By casting our problem as a set function optimization, we develop a polynomial-time algorithm that achieves a constant-factor approximation under certain conditions. Extensive synthetic and trace-driven simulations show that the proposed algorithm achieves 90% of the optimal performance.

When routing flows in a software defined network (SDN), service disruption and inconsistencies can occur during the updates of routing tables leading to degraded QoS or interruption of existing services. We study the problem of rerouting existing flows in an SDN to enable the admission of new flows while minimizing the disruption of existing flows, under link capacity and Quality of Service (QoS) constraints. We formulate the problem as an integer linear programming problem and propose two randomized rounding algorithms with bounded congestion and demand loss to solve this problem.

Peer-to-peer (p2p) networks and Mobile ad hoc networks (MANET) have been widely studied. However, a real-world deployment for the masses has remained elusive. Ever-increasing density of mobile devices, especially in urban areas, has given rise to new applications of p2p communication. However, the modern smartphone platforms have limited support for such communications. Further, the issues of battery life, range, and trust remain unaddressed. A key question then is, what kinds of applications can the modern mobile platforms support and what challenges remain? This paper identifies a class of applications and presents a novel center-to-peer-to-peer (c2p2p) architecture called Mesh Network Alerts (MNA) to support them. We describe our experiences in deploying MNA as a real-world system to millions of users for relaying severe weather information along with the challenges faced, and the approaches for addressing them.

Mobile devices such as smartphones are enabling users to generate and share videos with increasing rates. In some cases, these videos may contain valuable information, which can be exploited for a variety of purposes. However, instead of centrally collecting and processing videos for information retrieval, we consider crowdprocessing videos, where each mobile device locally processes stored videos. While the computational capability of mobile devices continues to improve, processing videos using deep learning, i.e., convolutional neural networks, is still a demanding task for mobile devices. To this end, we design and build CrowdVision, a computing platform that enables mobile devices to crowdprocess videos using deep learning in a distributed and energy-efficient manner leveraging cloud offload. CrowdVision can quickly and efficiently process videos with offload under various settings and different network connections and greatly outperform the existing computation offload framework (e.g., with a 2× speed-up). In doing so, CrowdVision tackles several challenges: (i) how to exploit the characteristics of the computing of deep learning for video processing; (ii) how to parallelize processing and offloading for acceleration; and (iii) how to optimize both time and energy at runtime by just determining the right moments to offload.

Network recovery after large-scale failures has tremendous cost implications. While numerous approaches have been proposed to restore critical services after large-scale failures, they mostly assume having full knowledge of failure location, which cannot be achieved in real failure scenarios. Making restoration decisions under uncertainty is often further complicated in a large-scale failure. This paper addresses progressive network recovery under the uncertain knowledge of damages. We formulate the problem as a mixed integer linear programming and show that it is NP-hard. We propose an iterative stochastic recovery algorithm (ISR) to recover the network in a progressive manner to satisfy the critical services. At each optimization step, we make a decision to repair a part of the network and gather more information iteratively, until critical services are completely restored. We propose three different approaches: 1) an iterative shortest path algorithm; 2) an approximate branch and bound (ISR-BB); and 3) an iterative multicommodity LP relaxation (ISR-MULT). Further, we compared our approach with the state-of-the-art centrality-based damage assessment and recovery (CeDAR) and iterative split and prune (ISP) algorithms. Our results show that ISR-BB and ISR-MULT outperform the state-of-the-art ISP and CeDAR algorithms while we can configure our choice of tradeoff between the execution time, the number of repairs (cost), and the demand loss. We show that our recovery algorithm, on average, can reduce the total number of repairs by a factor of about 3 with respect to ISP, while satisfying all critical demands.

VM migration is an effective countermeasure against attempts at malicious co-residency. In this paper, our overarching objectives are: (a) to get an in-depth understanding of the ways and effectiveness with which an attacker can launch attacks toward achieving co-residency and (b) to design migration policies that are very effective in thwarting malicious co-residency, but are thrifty in terms of the bandwidth and downtime costs that are incurred with live migration. Toward achieving our goals, we first undertake an experimental study on Amazon EC2 to obtain an in-depth understanding of the side-channels, through which an attacker can use to ascertain co-residency with a victim. Here, in this paper, we identify a new set of stealthy side-channel attacks which we show to be more effective than the currently available attacks toward verifying co-residency. We also build a simple model that can be used for estimating co-residency times based on very few measurements on a given cloud platform, to account for varying attacker capabilities. Based on the study, we develop a set of guidelines to determine under what conditions the victim VM migrations should be triggered, given the performance costs in terms of bandwidth and downtime, which a user is willing to bear. Through extensive experiments on our private in-house cloud, we show that the migrations, using our guidelines, can limit the fraction of the time that an attacker VM co-resides with a victim VM to about 1% of the time with the bandwidth costs of a few MB and downtimes of a few seconds per day per VM migrated.

Malicious coresidency is a precursor to side-channel attacks that target information leakage. In this paper, we seek to understand the interactions between a defender (the cloud service provider) who tries to detect malicious coresidency by an attacker, who in turn attempts to co-reside its VM with a victim VM on the same physical machine by exploiting the VM allocation policy employed by the cloud service provider while at the same time, trying to evade detection. The problem is modeled as a two-player game. Specifically, the attacker chooses how long to keep its VM operational before terminating and relaunching it to increase its odds of success. On the other hand, the defender attempts to detect and penalize malicious VMs based on their activity in a given time window. The defender estimates a maliciousness measure for all active VMs which then modulates the likelihood of a specific VM being migrated to a different physical machine. We study the equilibrium strategies for both players for different ranges of environment parameters and show the non-existence of equilibrium with pure strategies. Subsequently, we characterize the equilibrium of the game with mixed strategies.

Mobile edge computing is an emerging technology to offer resource-intensive yet delay-sensitive applications from the edge of mobile networks, where a major challenge is to allocate limited edge resources to competing demands. While prior works often make a simplifying assumption that resources assigned to different users are non-sharable, this assumption does not hold for storage resources, where users interested in services (e.g., data analytics) based on the same set of data/code can share storage resource. Meanwhile, serving each user request also consumes non-sharable resources (e.g., CPU cycles, bandwidth). We study the optimal provisioning of edge services with non-trivial demands of both sharable (storage) and non-sharable (communication, computation) resources via joint service placement and request scheduling. In the homogeneous case, we show that while the problem is polynomial-time solvable without storage constraints, it is NP-hard even if each edge cloud has unlimited communication or computation resources. We further show that the hardness is caused by the service placement subproblem, while the request scheduling subproblem is polynomial-time solvable via maximum-flow algorithms. In the general case, both subproblems are NP-hard. We develop a constant-factor approximation algorithm for the homogeneous case and efficient heuristics for the general case. Our trace-driven simulations show that the proposed algorithms, especially the approximation algorithm, can achieve near-optimal performance, serving 2-3 times more requests than a baseline solution that optimizes service placement and request scheduling separately.

Eavesdroppers can exploit exposed packet headers towards attacks that profile clients and their data flows. In this paper, we propose FOG, a framework for effective header blinding using MIMO, to thwart eavesdroppers. FOG effectively tracks header bits as they traverse physical (PHY) layer sub-systems that perform functions like scrambling and interleaving. It combines multiple blinding signals for more effective and less predictable obfuscation, as compared to using a fixed blinding signal. We implement FOG on the WARP platform and demonstrate via extensive experiments that it yields better obfuscation than prior schemes that deploy full packet blinding. It causes a bit error rate (BER) of > 40 % at an eavesdropper if two blinding streams are sent during header transmissions. Furthermore, FOG incurs a very small throughput hit of ≈5 % with one blinding stream (and 9 % with two streams). Full packet blinding incurs much higher throughput hits (25 % with one stream and 50 % with two streams).

Mobile devices such as smartphones are enabling users to generate and share videos with increasing rates. In some cases, these videos may contain valuable information, which can be exploited for a variety of purposes. However, instead of centrally collecting and processing videos for information retrieval, we consider crowdprocessing videos, where each mobile device locally processes stored videos. While the computational capability of mobile devices continues to improve, processing videos using deep learning, i.e., convolutional neural networks, is still a demanding task for mobile devices. To this end, we design and build CrowdVision, a computing platform that enables mobile devices to crowdprocess videos using deep learning in a distributed and energy-efficient manner leveraging cloud offload. CrowdVision can quickly and efficiently process videos with offload under various settings and different network connections and greatly outperform the existing computation offload framework (e.g., with a 2× speed-up). In doing so CrowdVision tackles several challenges: (i) how to exploit the characteristics of the computing of deep learning for video processing; (ii) how to parallelize processing and offloading for acceleration; and (iii) how to optimize both time and energy at runtime by just determining the right moments to offload.

Software defined networking (SDN) provides a framework to dynamically adjust and re-program the data plane with the use of flow rules. The realization of highly adaptive SDNs with the ability to respond to changing demands or recover after a network failure in a short period of time, hinges on efficient updates of flow rules. We model the time to deploy a set of flow rules by the update time at the bottleneck switch, and formulate the problem of selecting paths to minimize the deployment time under feasibility constraints as a mixed integer linear program (MILP). To reduce the computation time of determining flow rules, we propose efficient heuristics designed to approximate the minimum-deployment-time solution by relaxing the MILP or selecting the paths sequentially. Through extensive simulations we show that our algorithms outperform current, shortest path-based solutions by reducing the total network configuration time up to 55% while having similar packet loss, in the considered scenarios. We also demonstrate that in a networked environment with a certain fraction of failed links, our algorithms are able to reduce the average time to reestablish disrupted flows by 40%.

Quality of information (QoI) provides a context-dependent measure of the utility that a network delivers to its users by incorporating non-traditional information attributes. Quickly and easily predicting performance and limitations of a network using QoI metrics is a valuable tool for network design. Even more useful is an understanding of how network components like topology, bandwidth, and protocols, impact these limitations. In this paper, we develop a QoI-based framework that can provide accurate estimates for limitations on network size and achievable QoI requirements, focusing on completeness and timeliness. We extend this framework to model competing flows and data loads as random variables to capture the stochastic nature of real networks. We show that our framework can provide a characterization of delays for satisfied queries to further analyze performance when some late arrivals are acceptable. Analysis shows that the large tradeoffs exist between network parameters, such as QoI requirements, topology, and network size. Simulation results also provide evidence that the developed framework can estimate network limits and delays with high accuracy. Finally, this paper also introduces scalably feasible QoI regions, which provide upper bounds on QoI requirements that can be supported for certain network applications.

In this work, we present a framework for handling multiple, simultaneous, natural language queries, in a resource constrained environment, using Quality of Information (QoI). Incoming queries are first parsed into response graphs, tree-like structures designed to formalize a system's understanding of user intent, via a pragmatics toolkit. The system then uses a combination of QoI-awareness, adaptive intent determination, and packing algorithms to maximize the QoI realized by the system. We employ two different methods of evaluation, a one-shot model and an iterative, time-staged model. Under the one-shot model, packed jobs are answered and the rest discarded, and we aim to maximize the total realized QoI. Under the staged model, the system repeatedly packs and offers answers until all jobs are complete; here we aim to maximize time-weighted QoI and minimize completion time. We evaluate the performance of different instantiations of our system through thousands of procedurally-generated simulations.

Live virtual machine (VM) migration is commonly used for enabling dynamic resource or fault management, or for load balancing in datacenters or cloud platforms. A service hosted by a VM may also be migrated to prevent its visibility to an external adversary who may seek to disrupt its operation by launching a DDoS attack against it. We first show that current systems cannot adequately hide a VM migration from an external adversary. The key reason for this is that a migration typically manifests a traffic pattern with distinguishable statistical properties. We introduce two new attacks that can allow an adversary to effectively track a migration in progress, by leveraging observations of these properties. As our primary contribution, we design and implement a stealth migration framework that causes migration traffic to be indistinguishable from regular Internet traffic, with a negligible latency overhead of approximately 0.37 seconds, on average.

Attacker VMs try to co-reside with victim VMs on the same physical infrastructure as a precursor to launching attacks that target information leakage. VM migration is an effective countermeasure against attempts at malicious co-residency. In this paper, we first undertake an experimental study on Amazon EC2 to obtain an in-depth understanding of the side-channels an attacker can use to ascertain co-residency with a victim. Here, we identify a new set of stealthy side-channel attacks which, we show to be more effective than currently available attacks towards verifying co-residency. Based on the study, we develop a set of guidelines to determine under what conditions victim VM migrations should be triggered given performance costs in terms of bandwidth and downtime, that a user is willing to bear. Via extensive experiments on our private in-house cloud, we show that migrations using our guidelines can limit the fraction of the time that an attacker VM co-resides with a victim VM to about 1 % of the time with bandwidth costs of a few MB and downtimes of a few seconds, per day per VM migrated.

After a massive scale failure, the assessment of damages to communication networks requires local interventions and remote monitoring. While previous works on network recovery require complete knowledge of damage extent, we address the problem of damage assessment and critical service restoration in a joint manner. We propose a polynomial algorithm called Centrality based Damage Assessment and Recovery (CeDAR) which performs a joint activity of failure monitoring and restoration of network components. CeDAR works under limited availability of recovery resources and optimizes service recovery over time. We modified two existing approaches to the problem of network recovery to make them also able to exploit incremental knowledge of the failure extent. Through simulations we show that CeDAR outperforms the previous approaches in terms of recovery resource utilization and accumulative flow over time of the critical services.

Convolutional Neural Networks (CNNs) have revolutionized the research in computer vision, due to their ability to capture complex patterns, resulting in high inference accuracies. However, the increasingly complex nature of these neural networks means that they are particularly suited for server computers with powerful GPUs. We envision that deep learning applications will be eventually and widely deployed on mobile devices, e.g., smartphones, self-driving cars, and drones. Therefore, in this paper, we aim to understand the resource requirements (time, memory) of CNNs on mobile devices. First, by deploying several popular CNNs on mobile CPUs and GPUs, we measure and analyze the performance and resource usage for every layer of the CNNs. Our findings point out the potential ways of optimizing the performance on mobile devices. Second, we model the resource requirements of the different CNN computations. Finally, based on the measurement, profiling, and modeling, we build and evaluate our modeling tool, Augur, which takes a CNN configuration (descriptor) as the input and estimates the compute time and resource usage of the CNN, to give insights about whether and how efficiently a CNN can be run on a given mobile platform. In doing so Augur tackles several challenges: (i) how to overcome profiling and measurement overhead; (ii) how to capture the variance in different mobile platforms with different processors, memory, and cache sizes; and (iii) how to account for the variance in the number, type and size of layers of the different CNN configurations.

We introduce a novel mathematical model that treats network security as a game between cyber attackers and network administrators. The model takes the form of a zero-sum repeated game where each sub-game corresponds to a possible state of the attacker. Our formulation views state as the set of compromised edges in a graph opposed to the more traditional node-based view. This provides a more expressive model since it allows the defender to anticipate the direction of attack. Both players move independently and in continuous time allowing for the possibility of one player moving several times before the other does. This model shows that defense-in-depth is not always a rational strategy for budget constrained network administrators. Furthermore, a defender can dissuade a rational attacker from attempting to attack a network if the defense budget is sufficiently high. This means that a network administrator does not need to make their system completely free of vulnerabilities, they only to ensure the penalties for being caught outweigh the potential rewards gained.

Vulnerability due to inter-connectivity of multiple networks has been observed in many complex networks. Previous works mainly focused on robust network design and on recovery strategies after sporadic or massive failures in the case of complete knowledge of failure location. We focus on cascading failures involving the power grid and its communication network with consequent imprecision in damage assessment. We tackle the problem of mitigating the ongoing cascading failure and providing a recovery strategy. We propose a failure mitigation strategy in two steps: 1) Once a cascading failure is detected, we limit further propagation by re-distributing the generator and load's power. 2) We formulate a recovery plan to maximize the total amount of power delivered to the demand loads during the recovery intervention. Our approach to cope with insufficient knowledge of damage locations is based on the use of a new algorithm to determine consistent failure sets (CFS). We show that, given knowledge of the system state before the disruption, the CFS algorithm can find all consistent sets of unknown failures in polynomial time provided that, each connected component of the disrupted graph has at least one line whose failure status is known to the controller.

In this article, we address the problem of autonomously deploying mobile sensors in an unknown complex environment. In such a scenario, mobile sensors may encounter obstacles or environmental sources of noise, so that movement and sensing capabilities can be significantly altered and become anisotropic. Any reduction of device capabilities cannot be known prior to their actual deployment, nor can it be predicted. We propose a new algorithm for autonomous sensor movements and positioning, called DOMINO (DeplOyment of MobIle Networks with Obstacles). Unlike traditional approaches, DOMINO explicitly addresses these issues by realizing a grid-based deployment throughout the Area of Interest (AoI) and subsequently refining it to cover the target area more precisely in the regions where devices experience reduced sensing. We demonstrate the capability of DOMINO to entirely cover the AoI in a finite time. We also give bounds on the number of sensors necessary to cover an AoI with asperities. Simulations show that DOMINO provides a fast deployment with precise movements and no oscillations, with moderate energy consumption. Furthermore, DOMINO provides better performance than previous solutions in all the operative settings.

In this paper, we investigate how to network smartphones for providing communications in disaster recovery. By bridging the gaps among different kinds of wireless networks, we have designed and implemented a system called TeamPhone, which provides smartphones the capabilities of communications in disaster recovery. Specifically, TeamPhone consists of two components: A messaging system and a self-rescue system. The messaging system integrates cellular networking, ad-hoc networking, and opportunistic networking seamlessly, and enables communications among rescue workers. The self-rescue system groups, schedules, and positions the smartphones of trapped survivors. Such a group of smartphones can cooperatively wake up and send out emergency messages in an energy-efficient manner with their location and position information so as to assist rescue operations. We have implemented TeamPhone as a prototype application on the Android platform and deployed it on off-the-shelf smartphones. Experimental results demonstrate that TeamPhone can properly fulfill communication requirements and greatly facilitate rescue operations in disaster recovery.

Advanced targeted cyber attacks often rely on reconnaissance missions to gather information about potential targets, their characteristics and location to identify vulnerabilities in a networked environment. Advanced network scanning techniques are often used for this purpose and are automatically executed by malware infected hosts. In this paper, we formally define network deception to defend reconnaissance and develop a reconnaissance deception system, which is based on software defined networking, to achieve deception by simulating virtual topologies. Our system thwarts network reconnaissance by delaying the scanning techniques of adversaries and invalidating their collected information, while limiting the performance impact on benign network traffic. By simulating the topological as well as physical characteristics of networks, we introduce a system which deceives malicious network discovery and reconnaissance techniques with virtual information, while limiting the information an attacker is able to harvest from the true underlying system. This approach shows a novel defense technique against adversarial reconnaissance missions which are required for targeted cyber attacks such as advanced persistent threats in highly connected environments. The defense steps of our system aim to invalidate an attackers information, delay the process of finding vulnerable hosts and identify the source of adversarial reconnaissance within a network.

This paper addresses the problem of efficiently restoring sufficient resources in a communications network to support the demand of mission critical services after a large-scale disruption. We give a formulation of the problem as a mixed integer linear programming and show that it is NP-hard. We propose a polynomial time heuristic, called iterative split and prune (ISP) that decomposes the original problem recursively into smaller problems, until it determines the set of network components to be restored. ISP's decisions are guided by the use of a new notion of demand-based centrality of nodes. We performed extensive simulations by varying the topologies, the demand intensity, the number of critical services, and the disruption model. Compared with several greedy approaches, ISP performs better in terms of total cost of repaired components, and does not result in any demand loss. It performs very close to the optimal when the demand is low with respect to the supply network capacities, thanks to the ability of the algorithm to maximize sharing of repaired resources.

Images/videos are often uploaded in situations like disasters. This can tax the network in terms of increased load and thereby upload latency, and this can be critical for response activities. In such scenarios, prior work has shown that there is significant redundancy in the content (e.g., similar photos taken by users) transferred. By intelligently suppressing/deferring transfers of redundant content, the load can be significantly reduced, thereby facilitating the timely delivery of unique, possibly critical information. A key challenge here however, is detecting “what content is similar,” given that the content is generated by uncoordinated user devices. Toward addressing this challenge, we propose a framework, wherein a service to which the content is to be uploaded first solicits metadata (e.g., image features) from any device uploading content. By intelligently comparing this metadata with that associated with previously uploaded content, the service effectively identifies (and thus enables the suppression of) redundant content. Our evaluations on a testbed of 20 Android smartphones and via ns3 simulations show that we can identify similar content with a 70% true positive rate and a 1% false positive rate. The resulting reduction in redundant content transfers translates to a latency reduction of 44 % for unique content.

Opportunistic mobile networks consisting of intermittently connected mobile devices have been exploited for various applications, such as computational offloading and mitigating cellular traffic load. In contrast to existing work, in this paper, we focus on cooperatively offloading data among mobile devices to maximally improve the probability of data delivery from a mobile device to intermittently connected infrastructure within a given time constraint, which is referred to as the cooperative offloading problem. Unfortunately, the estimation of data delivery probability over an opportunistic path is difficult and cooperative offloading is NP-hard. To this end, we first propose a probabilistic framework that provides the estimation of such probability. Based on the proposed probabilistic framework, we design a heuristic algorithm to solve cooperative offloading at a low computation cost. Due to the lack of global information, a distributed algorithm is further proposed. The performance of the proposed approaches is evaluated based on both synthetic networks and real traces. Experimental results show that the probabilistic framework can accurately estimate the data delivery probability, cooperative offloading greatly improves the delivery probability, the heuristic algorithm approximates the optimum, and the performance of both the heuristic algorithm and distributed algorithm outperforms other approaches.

This paper addresses the problem of efficiently restoring sufficient resources in a communications network to support the demand of mission critical services after a large scale disruption. We give a formulation of the problem as an MILP and show that it is NP-hard. We propose a polynomial time heuristic, called Iterative Split and Prune (ISP) that decomposes the original problem recursively into smaller problems, until it determines the set of network components to be restored. We performed extensive simulations by varying the topologies, the demand intensity, the number of critical services, and the disruption model. Compared to several greedy approaches ISP performs better in terms of number of repaired components, and does not result in any demand loss. It performs very close to the optimal when the demand is low with respect to the supply network capacities, thanks to the ability of the algorithm to maximize sharing of repaired resources.

In infrastructure-lacking environments, like military areas of operation, the intermittent availability of backhaul networks leads to greater reliance on peer to peer data exchange. In such settings, mobile nodes use Delay Tolerant Network (DTN) protocols for exchanging location specific data. High transmission delay, packet loss and intermittent connectivity increases the need for efficient data transmission in such scenarios. In this paper, we evaluate network coding for efficient data exchange between mobile wireless nodes under the presence of an intermittent backhaul network, like a satellite or cellular link. We analyze the upper bound of savings achievable with network coding for single-hop packet transmission, and introduce a network coding algorithm focused on reducing the required number of packet transmissions in such a setting. Evaluation of our proposed data exchange protocol shows how network coding can be applied to reduce transmission delay and minimize the dependency on an intermittent backhaul network in a communication scenario typical of a military environment.

We consider the problem of placing services in a telecommunication network in the presence of failures. In contrast to existing service placement algorithms that focus on optimizing the quality of service (QoS), we consider the performance of monitoring failures from end-to-end connection states between clients and servers, and investigate service placement algorithms that optimize the monitoring performance subject to QoS constraints. Based on novel performance measures capturing the coverage, the identifiability, and the distinguishability in monitoring failures, we formulate the service placement problem as a set of combinatorial optimizations with these measures as objective functions. In particular, we show that maximizing the distinguishability is equivalent to minimizing the uncertainty in failure localization. We prove that all these optimizations are NP-hard. However, we show that the objectives of coverage and distinguishability have a desirable property that allows them to be approximated to a constant factor by a greedy algorithm. We further show that while the identifiability objective does not have this property, it can be approximated by the maximumdistinguishability placement in the high-identifiability regime. Our evaluations based on real network topologies verify the effectiveness of the proposed algorithms in improving the monitoring performance compared with QoS-based service placement.

The vast adoption of mobile devices with cameras has greatly assisted in the proliferation of the creation and distribution of videos. For a variety of purposes, valuable information may be extracted from these videos. While the computational capability of mobile devices has greatly improved recently, video processing is still a demanding task for mobile devices. Given a network consisting of mobile devices and video-clouds, mobile devices may be able to upload videos to video-clouds, which are more computationally capable for these processing tasks. However, due to networking constraints, when a video processing task is initiated through a query, most videos will not likely have been uploaded to the video-clouds, especially when the query is about a recent event. We investigate the problem of minimal query response time for processing videos stored across a network; however, this problem is a strongly NP-hard problem. To deal with this, we first propose a greedy algorithm with bounded performance. To further deal with the dynamics of the transmission rate between mobile devices and video-clouds, we propose an adaptive algorithm. To evaluate these algorithms, we built an on-demand video processing system. Based on the measurements of the system, we perform simulations to extensively evaluate the proposed algorithms. We also perform experiments on a small testbed to examine the realized system performance. Results show the performance of the greedy algorithm is close to the optimal and much better than other approaches, and the adaptive algorithm performs better with more dynamic transmission rates.

Densely-deployed femtocell networks are used to enhance wireless coverage in public spaces like office buildings, subways, and academic buildings. These networks can increase throughput for users, but edge users can suffer from co-channel interference, leading to service outages. This paper introduces a distributed algorithm for network configuration, called Radius Reduction and Scheduling (RRS), to improve the performance and fairness of the network. RRS determines cell sizes using a Voronoi-Laguerre framework, then schedules users using a scheduling algorithm that includes vacancy requests to increase fairness in dense femtocell networks. We prove that our algorithm always terminate in a finite time, producing a configuration that guarantees user or area coverage. Simulation results show a decrease in outage probability of up to 50%, as well as an increase in Jain's fairness index of almost 200%.

Opportunistic mobile networks consisting of intermittently connected mobile devices have been exploited for various applications, such as computational offloading and mitigating cellular traffic load. Different from existing work, in this paper, we focus on cooperatively offloading data among mobile devices to maximally improve the probability of data delivery from a mobile device to an intermittently connected remote server or data center within a given time constraint, which is referred to as the cooperative offloading problem. Unfortunately, cooperative offloading is NP-hard. To this end, a heuristic algorithm is designed based on the proposed probabilistic framework, which provides the estimation of the probability of successful data delivery over the opportunistic path, considering both data size and contact duration. Due to the lack of global information, a distributed algorithm is further proposed. The performance of the proposed approaches is evaluated based on both synthetic networks and real traces, and simulation results show that cooperative offloading can significantly improve the data delivery probability and the performance of both heuristic algorithm and distributed algorithm outperforms other approaches.

In this paper, we investigate how to network smart-phones for providing communications in disaster recovery. By bridging the gaps among different kinds of wireless networks, we have designed and implemented a system called TeamPhone, which provides smartphones the capabilities of communications in disaster recovery. Specifically, TeamPhone consists of two components: a messaging system and a self-rescue system. The messaging system integrates cellular networking, ad-hoc networking and opportunistic networking seamlessly, and enables communications among rescue workers. The self-rescue system energy-efficiently groups the smartphones of trapped survivor and sends out emergency messages so as to assist rescue operations. We have implemented TeamPhone as a prototype application on the Android platform and deployed it on off-the-shelf smartphones. Experiment results show that TeamPhone can properly fulfill communication requirements and greatly facilitate rescue operations in disaster recovery.

Quality of Information (QoI) provides a context-dependent measure of the utility that a network delivers to its users by incorporating non-traditional information attributes. Quickly and easily predicting performance and limitations of a network using QoI metrics is a valuable tool for network design. Even more useful is an understanding of how network components like topology, bandwidth, protocols, etc. impact these limitations. In this paper, we develop a QoI-based framework that can provide this understanding of limitations and impact by modeling the various contributors to delay in the network, including channel rate and contention, competing traffic flows, and multi-hop propagation effects, and relating them to QoI requirements, especially completeness and timeliness. Analysis shows that large tradeoffs exist between network parameters, such as QoI requirements, topology, and network size. Simulation results also provide evidence that the developed framework can estimate network limits with high accuracy. Finally, this work also introduces scalably feasible QoI regions, which provide upper bounds on QoI requirements that can be supported for certain network applications.

We present a framework and a set of algorithms for determining faults in networks when large scale outages occur. The design principles of our algorithm, netCSI, are motivated by the fact that failures are geographically clustered in such cases. We address the challenge of determining faults with incomplete symptom information due to a limited number of reporting nodes. netCSI consists of two parts: a hypotheses generation algorithm, and a ranking algorithm. When constructing the hypothesis list of potential causes, we make novel use of positive and negative symptoms to improve the precision of the results. In addition, we propose pruning and thresholding along with a dynamic threshold value selector, to reduce the complexity of our algorithm. The ranking algorithm is based on conditional failure probability models that account for the geographic correlation of the network objects in clustered failures. We evaluate the performance of netCSI for networks with both random and realistic topologies. We compare the performance of netCSI with an existing fault diagnosis algorithm, MAX-COVERAGE, and demonstrate an average gain of 128 percent in accuracy for realistic topologies.

Mobile sensor networks are the most promising solution to cover an Area of Interest (AoI) in safety critical scenarios. Mobile devices can coordinate with each other according to a distributed deployment algorithm, without resorting to human supervision for device positioning and network configuration. In this paper, we focus on the vulnerabilities of the deployment algorithms based on Voronoi diagrams to coordinate mobile sensors and guide their movements. We give a geometric characterization of possible attack configurations, proving that a simple attack consisting of a barrier of few compromised sensors can severely reduce network coverage. On the basis of the above characterization, we propose two new secure deployment algorithms, named SecureVor and Secure Swap Deployment (SSD). These algorithms allow a sensor to detect compromised nodes by analyzing their movements, under different and complementary operative settings. We show that the proposed algorithms are effective in defeating a barrier attack, and both have guaranteed termination. We perform extensive simulations to study the performance of the two algorithms and compare them with the original approach. Results show that SecureVor and SSD have better robustness and flexibility and excellent coverage capabilities and deployment time, even in the presence of an attack.

Network coding has been shown to offer significant throughput benefits over certain wireless network topologies. However, the application of network coding may not always improve the network performance. In this paper, we first provide an analytical study, which helps in assessing when network coding is preferable to a traditional store-and-forward approach. Interestingly, our study reveals that in many topological scenarios, network coding can in fact hurt the throughput performance; in such scenarios, applying the store-and-forward approach leads to higher network throughput. We validate our analytical findings via extensive testbed experiments. Guided by our findings as our primary contribution, we design and implement PACE, a Policy-Aware Coding Enforcement logic that enables network coding only when it is expected to offer performance benefits. Specifically, PACE leverages a minimal set of periodic link quality measurements in order to make per-flow online decisions with regards to when network coding should be activated, and when store-and-forward is preferable. It can be easily embedded into network-coding-aware routers as a user-level or kernel-level software utility. We evaluate the efficacy of PACE via: 1) ns-3 simulations, and 2) experiments on a wireless testbed. We observe that our scheme wisely activates network coding only when appropriate, thereby improving the total network throughput by as much as 350% in some scenarios.

Over-provisioned femtocell networks can be used to serve indoor locations that see high peak loads, such as airports or train stations. However, networks designed for high peak loads are mostly under-utilized, which is wasteful from an energy-use perspective. This paper introduces a femtocell selective activation problem. We motivate the use of selective activation in femtocell networks using real femtocell power measurements. We formally define the selective activation problem, and introduce GreenFemto, a distributed femtocell selective activation algorithm. We prove that GreenFemto converges to a locally Pareto optimal solution. Detailed simulations of an LTE wireless system are used to demonstrate the performance of GreenFemto. We find that GreenFemto uses up to 55% fewer femtocells to serve a given load, relative to an existing femtocell power-saving technique. Furthermore, we show that GreenFemto comes within 15% of a globally optimal solution. We conclude that selective activation can be successfully applied to femtocell networks to both reduce power consumption, and reduce outage probabilities.

The heterogeneous and dynamic nature of tactical coalition networks poses several challenges to common network management tasks, due to the lack of complete and accurate network information. In this paper, we consider the problem of redeploying services in mobile tactical networks. We propose M-iTop, an algorithm for inferring the network topology when only partial information is available. M-iTop initially constructs a virtual topology that overestimates the number of network components, and then repeatedly merges links in this topology to resolve it towards the structure of the true network. We perform extensive simulations and show that M-iTop enables an efficient redeployment of services over the network despite the limitation of partial information.

Event monitoring is an important application of sensor networks. Multiple parties, with different surveillance targets, can share the same network, with limited sensing resources, to monitor their events of interest simultaneously. Such a system achieves profit by allocating sensing resources to missions to collect event related information (e.g., Videos, photos, electromagnetic signals). We address the problem of dynamically assigning resources to missions so as to achieve maximum profit with uncertainty in event occurrence. We consider time-varying resource demands and profits, and multiple concurrent surveillance missions. We model each mission as a sequence of monitoring attempts, each being allocated with a certain amount of resources, on a specific set of events that occurs as a Markov process. We propose a Self-Adaptive Resource Allocation algorithm (SARA) to adaptively and efficiently allocate resources according to the results of previous observations. By means of simulations we compare SARA to previous solutions and show SARA's potential in finding higher profit in both static and dynamic scenarios.

Provisioning the capacity of wireless networks is difficult when peak load is significantly higher than average load, for example, in public spaces like airports or train stations. Service providers can use femtocells and small cells to increase local capacity, but deploying enough femtocells to serve peak loads requires a large number of femtocells that will remain idle most of the time, which wastes a significant amount of power. To reduce the energy consumption of over-provisioned femtocell networks, we formulate a femtocell selective activation problem, which we formalize as an integer nonlinear optimization problem. Then we introduce Green Femto, a distributed femtocell selective activation algorithm that deactivates idle femtocells to save power and activates them on-the-fly as the number of users increases. We prove that Green Femto converges to a locally Pareto optimal solution and demonstrate its performance using extensive simulations of an LTE wireless system. Overall, we find that Green Femto requires up to 55% fewer femtocells to serve a given user load, relative to an existing femtocell power-saving procedure, and comes within 15% of a globally optimal solution.

A cyber-physical system (CPS) integrates physical (i.e., sensor) devices with cyber (i.e., informational) components to form a context-sensitive system that responds intelligently to dynamic changes in real-world situations. The CPS has wide applications in scenarios such as environment monitoring, battlefield surveillance, and traffic control. One key research problem of CPS is called mining lines in the sand . With a large number of sensors (sand) deployed in a designated area, the CPS is required to discover all trajectories (lines) of passing intruders in real time. There are two crucial challenges that need to be addressed: (1) the collected sensor data are not trustworthy, and (2) the intruders do not send out any identification information. The system needs to distinguish multiple intruders and track their movements. This study proposes a method called LiSM (Line-in-the-Sand Miner) to discover trajectories from untrustworthy sensor data. LiSM constructs a watching network from sensor data and computes the locations of intruder appearances based on the link information of the network. The system retrieves a cone model from the historical trajectories to track multiple intruders. Finally, the system validates the mining results and updates sensors’ reliability scores in a feedback process. In addition, LoRM (Line-on-the-Road Miner) is proposed for trajectory discovery on road networks— mining lines on the roads . LoRM employs a filtering-and-refinement framework to reduce the distance computational overhead on road networks and uses a shortest-path-measure to track intruders. The proposed methods are evaluated with extensive experiments on big datasets. The experimental results show that the proposed methods achieve higher accuracy and efficiency in trajectory mining tasks.

Full knowledge of the routing topology of the Internet is useful for a multitude of network management tasks. However, the full topology is often not known and is instead estimated using topology inference algorithms. Many of these algorithms use Traceroute to probe paths and then use the collected information to infer the topology. We perform real experiments and show that, in practice, routers may severely disrupt the operation of Traceroute and cause it to only provide partial information. We propose iTop, an algorithm for inferring the network topology when only partial information is available. iTop constructs a virtual topology, which overestimates the number of network components, and then repeatedly merges links in this topology to resolve it toward the structure of the true network. We perform extensive simulations to compare iTop to state-of-the-art inference algorithms. Results show that iTop significantly outperforms previous approaches and its inferred topologies are within 5% of the original networks for all considered metrics. Additionally, we show that the topologies inferred by iTop significantly improve the performance of fault localization algorithms when compared with other approaches.

Traditional routing metrics designed for wireless networks are application-agnostic. In this paper, we consider a wireless network where the application flows consist of video traffic. From a user perspective, reducing the level of video distortion is critical. We ask the question “Should the routing policies change if the end-to-end video distortion is to be minimized?” Popular link-quality-based routing metrics (such as ETX) do not account for dependence (in terms of congestion) across the links of a path; as a result, they can cause video flows to converge onto a few paths and, thus, cause high video distortion. To account for the evolution of the video frame loss process, we construct an analytical framework to, first, understand and, second, assess the impact of the wireless network on video distortion. The framework allows us to formulate a routing policy for minimizing distortion, based on which we design a protocol for routing video traffic. We find via simulations and testbed experiments that our protocol is efficient in reducing video distortion and minimizing the user experience degradation.

Community detection is an important issue due to its wide use in designing network protocols such as data forwarding in Delay Tolerant Networks (DTN) and worm containment in Online Social Networks (OSN). However, most of the existing community detection algorithms focus on binary networks. Since most networks are naturally weighted such as DTN or OSN, in this article, we address the problems of community detection in weighted networks, exploit community for data forwarding in DTN and worm containment in OSN, and demonstrate how community can facilitate these network designs. Specifically, we propose a novel community detection algorithm, and introduce two metrics: intra-centrality and inter-centrality, to characterize nodes in communities, based on which we propose an efficient data forwarding algorithm for DTN and a worm containment strategy for OSN. Extensive trace-driven simulation results show that the proposed community detection algorithm, the data forwarding algorithm, and the worm containment strategy significantly outperform existing works.

We propose a greedy algorithm, Cluster-MAX-COVERAGE (CMC), to efficiently diagnose large-scale clustered failures. We primarily address the challenge of determining faults with incomplete symptoms. CMC makes novel use of both positive and negative symptoms to output a hypothesis list with a low number of false negatives and false positives quickly. CMC requires reports from about half as many nodes as other existing algorithms to determine failures with 100 percent accuracy. Moreover, CMC accomplishes this gain significantly faster (sometimes by two orders of magnitude) than an algorithm that matches its accuracy. When there are fewer positive and negative symptoms at a reporting node, CMC performs much better than existing algorithms. We also propose an adaptive algorithm called Adaptive-MAX-COVERAGE (AMC) that performs efficiently during both independent and clustered failures. During a series of failures that include both independent and clustered, AMC results in a reduced number of false negatives and false positives.

Images/videos are often uploaded in situations like disasters. This can tax the network in terms of increased load and thereby upload latency, and this can be critical for response activities. In such scenarios, prior work has shown that there is significant redundancy in the content (e.g., similar photos taken by users) transferred. By intelligently suppressing/deferring transfers of redundant content, the load can be significantly reduced, thereby facilitating the timely delivery of unique, possibly critical information. A key challenge here however, is detecting 'what content is similar,' given that the content is generated by uncoordinated user devices. Towards addressing this challenge, we propose a framework, wherein a service to which the content is to be uploaded first solicits metadata (e.g, image features) from any device uploading content. By intelligently comparing this metadata with that associated with previously uploaded content, the service effectively identifies (and thus enables the suppression of) redundant content. Our evaluations on a testbed of 20 Android smartphones and via ns3 simulations show that we can identify similar content with a 70% true positive rate and a 1% false positive rate. The resulting reduction in redundant content transfers translates to a latency reduction of 44 % for unique content.

In many deployments of wireless sensor networks (WSNs), the primary goal is to collect and deliver data from many nodes to a data sink. This goal must be met while considering limited resources, such as battery life, in the wireless nodes. In this work, we propose considering the content of generated data to make intelligent data and node selection decisions. We formally present the problem of maximizing coverage of this collected data while restricting individual node costs to remain within a given budget and provide an algorithm that provides the optimal solution. Next we consider the related problem of finding the optimal long-term average coverage subject to average cost constraints and give its solution, which uses Lyapunov Optimization techniques. For real world implementations, we also provide computationally feasible approximation algorithms of both problems along with proven bounds on their performance, including a novel technique that uses virtual queues for the average maximum coverage problem. Finally, we provide simulation results of all proposed algorithms. These results not only demonstrate the benefits of considering data content in scheduling, but also show the advantages from using the long-term average solution and the near-optimal performance of our greedy virtual queue approximation algorithm.

Mobile sensor networks enable the monitoring of remote and hostile environments without requiring human supervision. Several approaches have been proposed in the literature to let mobile sensors self-deploy over a region of interest. In this paper we study, for the first time, the vulnerabilities of one of the most referenced approaches to mobile sensor deployment, namely the Voronoi-based approach. We show that, by compromising a small number of sensors, an attacker can influence the sensor deployment causing a significant reduction of the monitoring capability of the network. We propose a secure deployment algorithm called SecureVOR. We formally prove that SecureVOR has guaranteed termination and that it allows legitimate sensors to detect the malicious behavior of compromised nodes. We also show by extensive simulations that SecureVOR is able to fulfill the network monitoring goals even in presence of an attack, at the expense of a small performance overhead.

Backpressure Routing is a cross-layer control algorithm that makes decisions on routing and resource allocation in mobile ad hoc networks using network state information like queue backlog values and current available channel rates. While it is desirable because of its provable performance guarantees, including providing optimal throughput, the real world problem of implementing backpressure routing in a distributed fashion is often ignored. To gain insight into how scheduling decisions and their impacts on performance are affected by errors, we develop two practical protocols that exchange network state information to allow nodes to make scheduling decisions in a distributed fashion. One protocol represents using the most current network state information, even if that information is inconsistent across different nodes. The second protocol models the situation in which nodes use information that is consistent, but is not current, and therefore, highly likely to contain errors compared to the current network state. We analyze the possible scheduling outcomes, modeling the probability of each, which allows us to compare the protocols' performance. We also provide results from simulations implemented in ns-3 that support the analysis. With this analysis, we are able to show that small magnitude errors have a large impact on performance that is abated as the error grows. We are also able to show the benefits of using consistent information in scheduling, since it fully utilizes available channels.

In this paper, we study the problem of selecting paths to improve the performance of network tomography applications in the presence of network element failures. We model the robustness of paths in network tomography by a metric called expected rank. We formulate an optimization problem to cover two complementary performance metrics: robustness and probing cost. The problem aims at maximizing the expected rank under a budget constraint on the probing cost. We prove that the problem is NP-Hard. Under the assumption that the failure distribution is known, we propose an algorithm called RoMe with guaranteed approximation ratio. Moreover, since evaluating the expected rank is generally hard, we provide a bound which can be evaluated efficiently. We also consider the case in which the failure distribution is not known, and propose a reinforcement learning algorithm to solve our optimization problem, using RoMe as a subroutine. We run a wide range of simulations under realistic network topologies and link failure models to evaluate our solution against a state-of-the-art path selection algorithm. Results show that our approaches provide significant improvements in the performance of network tomography applications under failures.

In this paper, we consider Quality-of-Information (QoI) aware transmission policies for a dynamic environment. In particular, we focus on the time-varying nature of the observation quality of the environment in practical networks which leads to uncertainty in satisfying QoI requirements specified by end users. The goal of this paper is to meet QoI requests from end users with minimum resources. Specifically, power is allocated dynamically depending on observation accuracies and QoI requirements. We formulate a dynamic scheme for scheduling with the objective of minimizing the energy consumption at the network while satisfying constraints on outage probability for QoI. Lyapunov stability arguments are used to define a policy based on the instantaneous observation qualities and QoI requirement satisfaction levels. Numerical results demonstrate that significant improvements in delivered QoI are realized with identical power expenditure using our QoI-aware resource allocation algorithm compared with traditional maximum-rate schedulers.

Large-scale enterprise femtocell deployments can significantly impact the performance and energy consumption of the underlying wireless networks that support them. Naive femtocell deployments can lead to higher overall network energy usage, while optimized femtocell deployments can increase total network connectivity and reduce macrocell energy consumption. This paper approaches femtocell deployment as a combinatorial optimization problem. We first consider accelerated greedy algorithms using one of two metrics: femtocell coverage and area spectral efficiency. Then, motivated by an analysis of the strengths and weaknesses of each metric, we introduce an algorithm that takes the weighted sum of both metrics. We evaluate our algorithms using extensive simulations, and find that our weighted sum algorithm decreases outage probability by up to 30% relative to existing greedy approaches. Furthermore, our algorithm can lead to a reduction in total network energy usage by up to 14%.

Periodic transitions from place to place are inherent in human movements. Through visual examination we detect these periodic movements in traces of user tracking data. However such user tracking data sets tend to be sparse and incomplete. In addition, periodic movements are surrounded by noise: transitions to and from less frequently visited places and transitions to one of a kind visits. In this paper, we present algorithms leveraging techniques and models to detect periodicity in individual user movements. Our algorithms predict a user's next place given only the current context of timestamp and location. We apply these algorithms to real user mobility data sets. Prediction accuracy depends on the ratio of periodic movements to noise in user traces. For majority of users in a movement tracking data set collected over a year, our algorithms achieve next place prediction accuracies of 50% and above.

Driven by the advance of positioning technology and the popularity of location-sharing services, semantic-enriched trajectory data have become unprecedentedly available. The sequential patterns hidden in such data, when properly defined and extracted, can greatly benefit tasks like targeted advertising and urban planning. Unfortunately, classic sequential pattern mining algorithms developed for transactional data cannot effectively mine patterns in semantic trajectories, mainly because the places in the continuous space cannot be regarded as independent "items". Instead, similar places need to be grouped to collaboratively form frequent sequential patterns. That said, it remains a challenging task to mine what we call fine-grained sequential patterns , which must satisfy spatial compactness, semantic consistency and temporal continuity simultaneously. We propose Splitter to effectively mine such fine-grained sequential patterns in two steps. In the first step, it retrieves a set of spatially coarse patterns, each attached with a set of trajectory snippets that precisely record the pattern's occurrences in the database. In the second step, Splitter breaks each coarse pattern into fine-grained ones in a top-down manner, by progressively detecting dense and compact clusters in a higher-dimensional space spanned by the snippets. Splitter uses an effective algorithm called weighted snippet shift to detect such clusters, and leverages a divide-and-conquer strategy to speed up the top-down pattern splitting process. Our experiments on both real and synthetic data sets demonstrate the effectiveness and efficiency of Splitter.

The proliferation and ever-increasing capabilities of mobile devices such as smart phones give rise to a variety of mobile sensing applications. This paper studies how an untrusted aggregator in mobile sensing can periodically obtain desired statistics over the data contributed by multiple mobile users, without compromising the privacy of each user. Although there are some existing works in this area, they either require bidirectional communications between the aggregator and mobile users in every aggregation period, or have high-computation overhead and cannot support large plaintext spaces. Also, they do not consider the Min aggregate, which is quite useful in mobile sensing. To address these problems, we propose an efficient protocol to obtain the Sum aggregate, which employs an additive homomorphic encryption and a novel key management technique to support large plaintext space. We also extend the sum aggregation protocol to obtain the Min aggregate of time-series data. To deal with dynamic joins and leaves of mobile users, we propose a scheme that utilizes the redundancy in security to reduce the communication cost for each join and leave. Evaluations show that our protocols are orders of magnitude faster than existing solutions, and it has much lower communication overhead.

The virtual force approach is at the basis of many solutions proposed for deploying mobile sensors. In this paper we study the vulnerabilities of this approach. We show that by compromising a few mobile sensors, an attacker can influence the movement of other sensors and prevent the achievement of the network coverage goals. We introduce an attack, called opportunistic movement, and give an analytical study of its efficacy. We show that in a typical scenario this attack can reduce coverage by more than 50 percent, by only compromising a 7 percent of the nodes. We propose two algorithms to counteract the above mentioned attack, DRM and SecureVF. DRM is a light-weight algorithm which randomly repositions sensors from overcrowded areas. SecureVF requires a more complex coordination among sensors but, unlike DRM, it enables detection and identification of malicious sensors. We investigate the performance of DRM and SecureVF through simulations. We show that DRM can significantly reduce the effects of the attack, at the expense of an increase in the energy consumption due to additional movements. By contrast, SecureVF completely neutralizes the attack and allows the achievement of the coverage goals of the network even in the presence of localization inaccuracies.

Sensor mission assignment involves matching the sensing resources of a wireless sensor network (WSN) to appropriate tasks (missions), which may come to the network dynamically. Although solutions for WSNs with battery-operated nodes have been proposed for this problem, no attention has been given to networks whose nodes have energy-harvesting capabilities and are powered in part by uncontrollable environmental sources, which impose quite a different energy model. In this article we address this problem by providing both an analytical model and a distributed heuristic, called EN-MASSE, specifically tailored for energy-harvesting mission-centric WSNs. To assess the performance of our proposed solution we have interfaced TelosB nodes with solar cells and performed extensive experiments to derive models and traces of solar energy acquisition. We use such real-life traces in our simulations. A comparative performance evaluation between EN-MASSE and other schemes previously proposed in the literature has shown that our solution significantly outperforms existing energy-harvesting-unaware mission assignment schemes. Moreover, using our analytical model as a benchmark, we also show that the profit earned by EN-MASSE is close to the optimum. Finally, we have implemented our proposed solution in TinyOS and experimentally validated its performance, showing the effectiveness of our approach.

Backup paths are widely used in IP networks to protect IP links from failures. However, existing solutions such as the commonly used independent model and Shared Risk Link Group (SRLG) model do not accurately reflect the correlation between IP link failures, and thus may not choose reliable backup paths. We propose a cross-layer approach for minimizing routing disruption caused by IP link failures. We develop a probabilistically correlated failure (PCF) model to quantify the impact of IP link failure on the reliability of backup paths. With the PCF model, we propose an algorithm to choose multiple reliable backup paths to protect each IP link. When an IP link fails, its traffic is split onto multiple backup paths to ensure that the rerouted traffic load on each IP link does not exceed the usable bandwidth. We evaluate our approach using real ISP networks with both optical and IP layer topologies. Experimental results show that two backup paths are adequate for protecting a logical link. Compared with existing works, the backup paths selected by our approach are at least 18 percent more reliable and the routing disruption is reduced by at least 22 percent. Unlike prior works, the proposed approach prevents the rerouted traffic from interfering with normal traffic.

We study a data dissemination scenario in which data items are to be transmitted to mobile clients via one of the stationary data access points (APs) that the clients pass by en route to their destinations. The scheduler dedicates sequences of consecutive timeslots of an AP to downloading a data item to a client during the time window in which it is in range, which corresponds to assigning a job (the client's download) to a machine (the AP) among many. The transmission rate chosen for each assignment partly corresponds to setting a machine's speed, but it also has subtler effects. The APs may control transmission power to tune its transmission range making sure that no interference occurs with neighboring APs' transmissions. The problem is a generalization of an already NP-hard parallel-machine scheduling problem in which jobs' release times and deadlines depend on the machine to which they are assigned. We define this joint timeslot, power control, and rate assignment problem formally and apply both new algorithms and adaptations of existing algorithms to it. We evaluate these algorithms through simulations which show that our proposed algorithms achieve near-optimal throughput.

The understanding of how humans move is a longstanding challenge in the natural science. An important question is, to what degree is human behavior predictable? The ability to foresee the mobility of humans is crucial from predicting the spread of human to urban planning. Previous research has focused on predicting individual mobility behavior, such as the next location prediction problem. In this paper we study the human mobility behaviors from the perspective of network science. In the human mobility network, there will be a link between two humans if they are physically proximal to each other. We perform both microscopic and macroscopic explorations on the human mobility patterns. From the microscopic perspective, our objective is to answer whether two humans will be in proximity of each other or not. While from the macroscopic perspective, we are interested in whether we can infer the future topology of the human mobility network. In this paper we explore both problems by using link prediction technology, our methodology is demonstrated to have a greater degree of precision in predicting future mobility topology.

Video transfers using smartphones are becoming increasingly popular. To prevent the interception of content from eavesdroppers, video flows must be encrypted. However, encryption results in a cost in terms of processing delays and energy consumed on the user's device. We argue that encrypting only certain parts of the flow can create sufficiently high distortion at an eavesdropper preserving content confidentiality as a result. By selective encryption, one can reduce delay and the battery consumption on the mobile device. We develop a mathematical framework that captures the impact of the encryption process on the delay experienced by a flow, and the distortion seen by an eavesdropper. This provides a quick and efficient way of determining the right parts of a video flow that must be encrypted to preserve confidentiality, while limiting performance penalties. In practice, it can aid a user in choosing the right level of encryption. We validate our model via extensive experiments with different encryption policies using Android smartphones. We observe that by selectively encrypting parts of a video flow one can preserve the confidentiality while reducing delay by as much as 75% and the energy consumption by as much as 92%.

Network coding has been shown to offer significant throughput benefits over store-and-forward routing in certain wireless network topologies. However, the application of network coding may not always improve the network performance. In this paper1, we provide a comprehensive analytical study, which helps in assessing when network coding is preferable to a traditional store-and-forward approach. Interestingly, our study reveals that in many topological scenarios, network coding can in fact hurt the throughput performance; in such scenarios, applying the store-and-forward approach leads to higher network throughput. We validate our analytical findings via extensive testbed experiments, and we extract guidelines on when network coding should be applied instead of store-and-forward.

In this paper we point out the vulnerabilities of the virtual force approach to mobile sensor deployment, which is at the basis of many deployment algorithms. For the first time in the literature, we show that some attacks significantly hinder the capability of these algorithms to guarantee a satisfactory coverage. An attacker can compromise a few mobile sensors and force them to pursue a malicious purpose by influencing the movement of other legitimate sensors. We make an example of a simple and effective attack, called Opportunistic Movement, and give an analytical study of its efficacy. We also show through simulations that, in a typical scenario, this attack can reduce coverage by more than 50% by compromising a number of nodes as low as the 7%. We propose SecureVF, a virtual force deployment algorithm able to neutralize the above mentioned attack. We show that under SecureVF malicious sensors are detected and then ignored whenever their movement is not compliant with the moving strategy provided by SecureVF. We also investigate the performance of SecureVF through simulations, and compare it to one of the most acknowledged algorithms based on virtual forces. We show that SecureVF enables a remarkably improved coverage of the area of interest, at the expense of a low additional energy consumption.

The end-user experience in viewing a video depends on the distortion; however, also of importance is the delay experienced by the packets of the video flow since it impacts the timeliness of the information contained and the playback rate at the receiver. Unfortunately, these performance metrics are in conflict with each other in a wireless network. Packet losses can be minimized by perfectly avoiding interference by separating transmissions in time or frequency; however, this decreases the rate at which transmissions occur, and this increases delay. Relaxing the requirement for interference avoidance can lead to packet losses and thus increase distortion, but can decrease the delay for those packets that are delivered. In this paper, we investigate this trade-off between distortion and delay for video. To understand the trade-off between video quality and packet delay, we develop an analytical framework that accounts for characteristics of the network (e.g. interference, channel variations) and the video content (motion level), assuming as a basis, a simple channel access policy that provides flexibility in managing the interference in the network. We validate our model via extensive simulations. Surprisingly, we find that the trade-off depends on the specific features of the video flow: it is better to trade-off high delay for low distortion with fast motion video, but not with slow motion video. Specifically, for an increase in PSNR (a metric that quantifies distortion) from 20 to 25 dB, the penalty in terms of the increase in mean delay with fast motion video is 91 times that with slow motion video. Our simulation results further quantify the trade-offs in various scenarios.

A Cyber-Physical System (CPS) integrates physical (i.e., sensor) devices with cyber (i.e., informational) components to form a context sensitive system that responds intelligently to dynamic changes in real-world situations. The CPS has wide applications in scenarios such as environment monitoring, battlefield surveillance and traffic control. One key research problem of CPS is called "mining lines in the sand". With a large number of sensors (sand) deployed in a designated area, the CPS is required to discover all the trajectories (lines) of passing intruders in real time. There are two crucial challenges that need to be addressed: (1) the collected sensor data are not trustworthy; (2) the intruders do not send out any identification information. The system needs to distinguish multiple intruders and track their movements. In this study, we propose a method called LiSM (Line-in-the-Sand Miner) to discover trajectories from untrustworthy sensor data. LiSM constructs a watching network from sensor data and computes the locations of intruder appearances based on the link information of the network. The system retrieves a cone-model from the historical trajectories and tracks multiple intruders based on this model. Finally the system validates the mining results and updates the sensor's reliability in a feedback process. Extensive experiments on big datasets demonstrate the feasibility and applicability of the proposed methods.

Support for intelligent and autonomous resource management is one key factor to the success of modern sensor network systems. The limited resources, such as exhaustible battery life, moderate processing ability and finite bandwidth, restrict the system's ability to serve multiple users simultaneously. It always happens that only a subset of tasks is selected with the goal of maximizing total profit. Besides, because of uncertain factors like unreliable wireless medium or variable quality of sensor outputs, it is not practical to assume that both demands and profits of tasks are deterministic and known a priori, both of which may be stochastic following certain distributions. In this paper, we model this resource allocation challenge as a stochastic knapsack problem. We study a specific case in which both demands and profits follow normal distributions, which are then extended to Poisson and Binomial variables. A couple of tunable parameters are introduced to configure two probabilities: one limits the capacity overflow rate with which the combined demand is allowed to exceed the available supply, and the other sets the minimum chance at which expected profit is required to be achieved. We define relative values for random variables in given conditions, and utilize them to search for the best resource allocation solutions. We propose heuristics with different optimality/efficiency tradeoffs, and find that our algorithms run relatively fast and provide results considerably close to the optimum.

Enterprise femtocell deployments present numerous design challenges for network operators due to their high density, poor radio environments, and mixture of public and private users. Among these challenges, femtocell pilot management is particularly important due to its potential impact on both femtocell and macrocell users. Femtocell pilots determine femtocell coverage, but must be designed with consideration for macrocell transmissions and users. We introduce a utility-based femtocell pilot management algorithm that sets femtocell pilots by finding the Nash equilibrium of an N-player strategic game, using a utility function derived from the femtocell coverage radius. Using simulations, we find that the game-theoretic interference management algorithm reduces outage probabilities relative to a naive interference management scheme by up to 43% in the open access femtocell case, and 17% in the closed access femtocell case. Our conclusion is that game theory can be applied to the distributed problem of femtocell pilot estimation, with good results.

A recent topic of research in the network science community is combined or composite networks - these are two or more interacting networks that must be characterized jointly rather than individually. For example, a social network and a communication network sharing some nodes (corresponding to users) may be modeled together as a composite network. This may be useful since the aggregate performance of a composite network may often depend on how the individual networks influence each other. Information may travel faster or slower through composite networks depending on how they are coupled. The above vision was captured in the Call for Papers for this special issue in the IEEE Journal On Selected Areas In Communications, and it was published in June 2012. As a result of this solicitation, we received 62 submissions by the deadline of August 15, 2012. Papers were selected after two rigorous rounds of review. The first round of notifications were sent out on December 17, 2012 to the authors whose papers passed the first round of review. Revised versions of the papers were submitted on January 31, 2013. Finally, after a second round of review, the Guest Editorial board decided on March 12, 2013 to accept 16 high quality papers for publication in this competitive special issue. Papers appearing in this special issue belong to five broad themes, which are not necessarily mutually exclusive: (1) fundamental principles in network science, (2) information propagation models in networks, (3) bringing insights from other genres of networks, (4) economic and game theoretic models, and (5) application of network science principles to communications networking problems.

The advance of mobile technologies leads to huge volumes of spatio-temporal data collected in the form of trajectory data streams. In this study, we investigate the problem of discovering object groups that travel together (i.e., traveling companions ) from trajectory data streams. Such technique has broad applications in the areas of scientific study, transportation management, and military surveillance. To discover traveling companions, the monitoring system should cluster the objects of each snapshot and intersect the clustering results to retrieve moving-together objects. Since both clustering and intersection steps involve high computational overhead, the key issue of companion discovery is to improve the efficiency of algorithms. We propose the models of closed companion candidates and smart intersection to accelerate data processing. A data structure termed traveling buddy is designed to facilitate scalable and flexible companion discovery from trajectory streams. The traveling buddies are microgroups of objects that are tightly bound together. By only storing the object relationships rather than their spatial coordinates, the buddies can be dynamically maintained along the trajectory stream with low cost. Based on traveling buddies, the system can discover companions without accessing the object details. In addition, we extend the proposed framework to discover companions on more complicated scenarios with spatial and temporal constraints, such as on the road network and battlefield. The proposed methods are evaluated with extensive experiments on both real and synthetic datasets. Experimental results show that our proposed buddy-based approach is an order of magnitude faster than the baselines and achieves higher accuracy in companion discovery.

Unpredictable node mobility, low node density, and lack of global information make it challenging to achieve effective data forwarding in Delay-Tolerant Networks (DTNs). Most of the current data forwarding schemes choose the nodes with the best cumulative capability of contacting others as relays to carry and forward data, but these nodes may not be the best relay choices within a short time period due to the heterogeneity of transient node contact characteristics. In this paper, we propose a novel approach to improve the performance of data forwarding with a short time constraint in DTNs by exploiting the transient social contact patterns. These patterns represent the transient characteristics of contact distribution, network connectivity and social community structure in DTNs, and we provide analytical formulations on these patterns based on experimental studies of realistic DTN traces. We then propose appropriate forwarding metrics based on these patterns to improve the effectiveness of data forwarding. When applied to various data forwarding strategies, our proposed forwarding metrics achieve much better performance compared to existing schemes with similar forwarding cost.

Network coding has been proposed as a technique that can potentially increase the transport capacity of a wireless network via mixing data packets at intermediate routers. However, most previous studies either assume a fixed transmission rate or do not consider the impact of using diverse rates on the network coding gain. Since in many cases, network coding implicitly relies on overhearing, the choice of the transmission rate has a big impact on the achievable gains. The use of higher rates works in favor of increasing the native throughput. However, it may in many cases work against effective overhearing. In other words, there is a tension between the achievable network coding gain and the inherent rate gain possible on a link. In this paper, our goal is to drive the network toward achieving the best tradeoff between these two contradictory effects. We design a distributed framework that: facilitates the choice of the best rate on each link while considering the need for overhearing; and dictates the choice of which decoding recipient will acknowledge the reception of an encoded packet. We demonstrate that both of these features contribute significantly toward gains in throughput. We extensively simulate our framework in a variety of topological settings. We also fully implement it on real hardware and demonstrate its applicability and performance gains via proof-of-concept experiments on our wireless testbed. We show that our framework yields throughput gains of up to 390% as compared to what is achieved in a rate-unaware network coding framework.

We study a data dissemination scenario in which data items are to be transmitted to mobile clients via one of the stationary data access points (APs) that the clients pass by en route to their destinations. The scheduler dedicates sequences of consecutive timeslots of an AP to downloading a data item to a client during the time window in which it is in range, which corresponds to assigning a job (the client's download) to a machine (the AP) among many. The transmission rate chosen for each assignment partly corresponds to setting a machine's speed, but it also has subtler effects. The APs may control transmission power to tune its transmission range making sure that no interference occurs with neighboring APs' transmissions. The problem is a generalization of an already NP-hard parallel-machine scheduling problem in which jobs' release times and deadlines depend on the machine to which they are assigned. We define this joint timeslot, power control, and rate assignment problem formally and apply both new algorithms and adaptations of existing algorithms to it. We evaluate these algorithms through simulations which show that our proposed algorithms achieve near-optimal throughput.

Resources in modern computer systems include not only CPU, but also memory, hard disk, bandwidth, etc. To serve multiple users simultaneously, we need to satisfy their requirements in all resource dimensions. Meanwhile, their demands follow a certain distribution and may change over time. Our goal is then to admit as many users as possible to the system without violating the resource capacity more often than a predefined overflow probability. In this paper, we study the problem of allocating multiple resources among a group of users/tasks with stochastic demands. We model it as a stochastic multi-dimensional knapsack problem. We extend and apply the concept of effective bandwidth in order to solve this problem efficiently. Via numerical experiments, we show that our algorithms achieve near-optimal performance with specified overflow probability.

In this paper, we propose an algorithm to efficiently diagnose large-scale clustered failures. The algorithm, Cluster-MAX-COVERAGE (CMC), is based on greedy approach. We address the challenge of determining faults with incomplete symptoms. CMC makes novel use of both positive and negative symptoms to output a hypothesis list with a low number of false negatives and false positives quickly. CMC requires reports from about half as many nodes as other existing algorithms to determine failures with 100% accuracy. Moreover, CMC accomplishes this gain significantly faster (sometimes by two orders of magnitude) than an algorithm that matches its accuracy. Furthermore, we propose an adaptive algorithm called Adaptive-MAX-COVERAGE (AMC) that performs efficiently during both kinds of failures, i.e., independent and clustered. During a series of failues that include both independent and clustered, AMC results in a reduced number of false negatives and false positives.

While network coding can potentially provide significant throughput benefits by combining packets prior to forwarding them, the achievable gains are directly related to the coding opportunities at a relay that performs encoding. If the relay does not have packets destined for distinct destinations, that can be encoded together, the network coding gains could be marginal. Towards increasing the opportunities for network coding, in this paper we propose a queue management scheme, that arbitrates the rate at which distinct transmitters send packets to a common relay which applies network coding. Our queue management approach prioritizes the channel access of nodes that do not have enough enqueued packets at the common relay, thereby essentially attempting to balance the number of packets from the distinct senders at the relay. We perform extensive simulations of our approach (built as a wrapper on top of the popular network coding approach COPE) in multi-rate scenarios. We find that our approach yields throughput gains of up to 57% compared to COPE due to enhanced opportunities towards encoding packets.

Femtocells are tiny, low-cost, customer-deployed cellular base stations that are designed to provide supplementary coverage to existing wireless networks. However, naive femtocell deployments can cause pilot pollution and raise interference levels for users connected to macrocells, particularly when the local density of femtocells is very high, such as in an enterprise setting. We describe three dynamic femtocell pilot adjustment algorithms that balance femtocell coverage and interference: a distributed and two cooperative algorithms that leverage a lightweight, local, interference management server. Using simulations, we find that the interference management algorithms reduce outage probabilities relative to a naive interference management scheme by up to 85%. Exploiting locality through the use of dynamic interference management algorithms is a promising approach to managing femtocell deployments.

Quickly recovering IP networks from failures is critical to enhancing Internet robustness and availability. Due to their serious impact on network routing, large-scale failures have received increasing attention in recent years. We propose an approach called Reactive Two-phase Rerouting (RTR) for intra-domain routing to quickly recover from large-scale failures with the shortest recovery paths. To recover a failed routing path, RTR first forwards packets around the failure area to collect information on failures. Then, in the second phase, RTR calculates a new shortest path and forwards packets along it through source routing. RTR can deal with large-scale failures associated with areas of any shape and location, and is free of permanent loops. For any failure area, the recovery paths provided by RTR are guaranteed to be the shortest. Extensive simulations based on ISP topologies show that RTR can find the shortest recovery paths for more than 98.6% of failed routing paths with reachable destinations. Compared with prior works, RTR achieves better performance for recoverable failed routing paths and uses much less network resources for irrecoverable failed routing paths.

Traditional routing metrics designed for wireless networks are application agnostic. In this paper, we consider a wireless network where the application flows consist of video traffic. From a user-perspective, reducing the level of video distortion is critical. We ask the question “Should the routing policies change if the end-to-end video distortion is to be minimized?” Popular link-quality based routing metrics (such as ETX) do not account for dependence (in terms of congestion) across the links of a path; as a result, they can cause video flows to converge onto a few paths and thus, cause high video distortion. To account for the evolution of the video frame loss process we construct an analytical framework to first, understand and second, assess the impact of the wireless network on video distortion. The framework allows us to formulate a routing policy for minimizing distortion, based on which we design a protocol for routing video traffic. We find via simulations and testbed experiments that our protocol is efficient in reducing video distortion and minimizing the user experience degradation. Specifically, our protocol reduces the distortion by 20% over traditional methods, which significantly improves the video quality perceived by a user.

Content distribution networks (CDNs) using storage clouds have recently started to emerge. Compared to traditional CDNs, storage cloud-based CDNs have the advantage of cost effectively offering hosting services to Web content providers without owning infrastructure. However, existing work on replica placement in CDNs does not readily apply in the cloud. In this paper, we investigated the joint problem of building distribution paths and placing Web server replicas in cloud CDNs to minimize the cost incurred on the CDN providers while satisfying QoS requirements for user requests. We formulate the cost optimization problem with accurate cost models and QoS requirements and show that the monthly cost can be as low as 2.62 US Dollars for a small Web site. We develop a suite of offline, online-static and online-dynamic heuristic algorithms that take as input network topology and work load information such as user location and request rates. We then evaluate the heuristics via Web trace-based simulation, and show that our heuristics behave very close to optimal under various network conditions.

The ubiquity of smartphones and their on-board sensing capabilities motivates crowd-sensing, a capability that harnesses the power of crowds to collect sensor data from a large number of mobile phone users. Unlike previous work on wireless sensing, crowd-sensing poses several novel requirements: support for humans-in-the-loop to trigger sensing actions or review results, the need for incentives, as well as privacy and security. Beyond existing crowd-sourcing systems, crowd-sensing exploits sensing and processing capabilities of mobile devices. In this paper, we design and implement Medusa, a novel programming framework for crowd-sensing that satisfies these requirements. Medusa provides high-level abstractions for specifying the steps required to complete a crowd-sensing task, and employs a distributed runtime system that coordinates the execution of these tasks between smartphones and a cluster on the cloud. We have implemented ten crowd-sensing tasks on a prototype of Medusa. We find that Medusa task descriptions are two orders of magnitude smaller than standalone systems required to implement those crowd-sensing tasks, and the runtime has low overhead and is robust to dynamics and resource attacks.

The ubiquity of smartphones and their on-board sensing capabilities motivates crowd-sensing, a capability that harnesses the power of crowds to collect sensor data from a large number of mobile phone users. Unlike previous work on wireless sensing, crowd-sensing poses several novel requirements: support for humans-in-the-loop to trigger sensing actions or review results, the need for incentives, as well as privacy and security. Beyond existing crowd-sourcing systems, crowd-sensing exploits sensing and processing capabilities of mobile devices. In this paper, we design and implement Medusa, a novel programming framework for crowd-sensing that satisfies these requirements. Medusa provides high-level abstractions for specifying the steps required to complete a crowd-sensing task, and employs a distributed runtime system that coordinates the execution of these tasks between smartphones and a cluster on the cloud. We have implemented ten crowd-sensing tasks on a prototype of Medusa. We find that Medusa task descriptions are two orders of magnitude smaller than standalone systems required to implement those crowd-sensing tasks, and the runtime has low overhead and is robust to dynamics and resource attacks.

A Cyber-Physical System (CPS) integrates physical (i.e., sensor) devices with cyber (i.e., informational) components to form a situation-aware system that responds intelligently to dynamic changes in real-world. It has wide application to scenarios of traffic control, environment monitoring and battlefield surveillance. This study investigates the specific problem of intruder mining in CPS: With a large number of sensors deployed in a designated area, the task is real time detection of intruders who enter the area, based on untrustworthy data. We propose a method called IntruMine to detect and verify the intruders. IntruMine constructs monitoring graphs to model the relationships between sensors and possible intruders, and computes the position and energy of each intruder with the link information from these monitoring graphs. Finally, a confidence rating is calculated for each potential detection, reducing false positives in the results. IntruMine is a generalized approach. Two classical methods of intruder detection can be seen as special cases of IntruMine under certain conditions. We conduct extensive experiments to evaluate the performance of IntruMine on both synthetic and real datasets and the experimental results show that IntruMine has better effectiveness and efficiency than existing methods.

Data-gathering or convergecast problems have traditionally been studied in two combinations of settings: one-shot scheduling of data items with no aggregation, and periodic scheduling of data items with full aggregation meaning that any number of unit-size data items can, if available, be aggregated into a single (unit-size) data item (e.g., by summing or averaging values). In this paper, we extend beyond these problem settings in two ways. First, we study a) one-shot throughput maximization in settings with aggregation and b) periodic scheduling in settings without aggregation. Second, we generalize the notion of aggregatability in both one-shot and periodic scheduling beyond the binary choice of either all sets of items being aggregatable or none being so. Modeling the presence of multiple semantic data types (e.g., target counts to be summed and temperature readings to be averaged), we partition data items into classes, whereby items are aggregatable if they belong to the same class, in both periodic and non-periodic settings. For these two problems we provide guaranteed approximations and heuristics, for a variety of general and special cases. We then evaluate the algorithms in a systematic simulation study, both under the conditions in which our provable guarantees apply and in more general settings, where we find the algorithms continue to perform well on typical problem inputs.

We consider variations of a problem in which data must be delivered to mobile clients en route, as they travel toward their destinations. The data can only be delivered to the mobile clients as they pass within range of wireless base stations. Example scenarios include the delivery of building maps to firefighters responding to multiple alarms. We cast this scenario as a parallel-machine scheduling problem with the little-studied property that jobs may have different release times and deadlines when assigned to different machines. We present new algorithms and also adapt existing algorithms, for both online and offline settings. We evaluate these algorithms on a variety of problem instance types, using both synthetic and real-world data, including several geographical scenarios, and show that our algorithms produce schedules achieving near-optimal throughput.

In-network Processing, involving operations such as filtering, compression, and fusion is a technique widely used in wireless sensor and ad hoc networks for reducing the communication overhead. In many tactical stream-oriented applications, especially in military scenarios, both link bandwidth and node energy are critically constrained resources. For such applications, in-network processing itself imposes nonnegligible computing cost. In this work, we have developed a unified, utility-based closed-loop control framework that permits distributed convergence to both 1) the optimal level of compression performed by a forwarding node on streams, and 2) the best set of nodes where the operators of the stream processing graph should be deployed. We also show how the generalized model can be adapted to more realistic cases, where the in-network operator may be varied only in discrete steps, and where a fusion operation cannot be fractionally distributed across multiple nodes. Finally, we provide a real-time implementation of the protocol on an 802.11b network with a video application and show that the performance of the network is improved significantly in terms of the packet loss, node lifetime, and quality of video received.

Both bandwidth and energy become important resource constraints when multihop wireless networks are used to transport high-data-rate traffic for a moderately long duration. In such networks, it is important to control the traffic rates to not only conform to the link capacity bounds, but also to ensure that the energy of battery-powered forwarding nodes is utilized judiciously to avoid premature exhaustion (i.e., the network lasts as long as the applications require data from the sources) without being unnecessarily conservative (i.e., ensuring that the applications derive the maximum utility possible). Unlike prior work that focuses on the instantaneous distributed optimization of such networks, we consider the more challenging question of how such optimal usage of both link capacity and node energy may be achieved over a time horizon. Our key contributions are twofold. We first show how the formalism of optimal control may be used to derive optimal resource usage strategies over a time horizon, under a variety of both deterministic and statistically uncertain variations in various parameters, such as the duration for which individual applications are active or the time-varying recharge characteristics of renewable energy sources (e.g., solar cell batteries). In parallel, we also demonstrate that these optimal adaptations can be embedded, with acceptably low signaling overhead, into a distributed, utility-based rate adaptation protocol. Simulation studies, based on a combination of synthetic and real data traces, validate the close-to-optimal performance characteristics of these practically realizable protocols.

In order to prolong the lifetime of a wireless sensor network (WSN) devoted to monitoring an area of interest, a useful means is to exploit network redundancy, activating only the sensors that are strictly necessary for coverage and making them work with the minimum necessary sensing radius. In this article, we introduce the first algorithm that reduces sensor coverage redundancy through joint Sensor Activation and sensing Radius Adaptation (SARA) in general application scenarios comprising two classes of devices: sensors with variable sensing radius and sensors with fixed sensing radius. This device heterogeneity is explicitly addressed by modeling the coverage problem through Voronoi-Laguerre diagrams that, differently from Voronoi diagrams, allow for correctly identifying each sensor coverage region depending on the sensor current radius and the radii of its neighboring nodes. SARA executes quickly with guaranteed termination and, given the currently available nodes, it always guarantees maximum coverage. By means of extensive simulations, we show that SARA obtains remarkable improvements with respect to previous solutions, ensuring, in networks with heterogeneous nodes, longer network lifetime and wider coverage.

This article develops a utility-based optimization framework for resource sharing by multiple competing missions in a mission-oriented wireless sensor network (WSN) environment. Prior work on network utility maximization (NUM) based optimization has focused on unicast flows with sender-based utilities in either wireline or wireless networks. In this work, we develop a generalized NUM model to consider three key new features observed in mission-centric WSN environments: i) the definition of the utility of an individual mission (receiver) as a joint function of data from multiple sensor sources; ii) the consumption of each sender's (sensor) data by multiple missions; and iii) the multicast-tree-based dissemination of each sensor's data flow, using link-layer broadcasts to exploit the “wireless broadcast advantage” in data forwarding. We show how a price-based, distributed protocol (WSN-NUM) can ensure optimal and proportionally fair rate allocation across multiple missions, without requiring any coordination among missions or sensors. We also discuss techniques to improve the speed of convergence of the protocol, which is essential in an environment as dynamic as the WSN. Further, we analyze the impact of various network and protocol parameters on the bandwidth utilization of the network, using a discrete-event simulation of a stationary wireless network. Finally, we corroborate our simulation-based performance results of the WSN-NUM protocol with an implementation of an 802.11b network.

Data access is an important issue in Delay Tolerant Networks (DTNs), and a common technique to improve the performance of data access is cooperative caching. However, due to the unpredictable node mobility in DTNs, traditional caching schemes cannot be directly applied. In this paper, we propose DAC, a novel caching protocol adaptive to the challenging environment of DTNs. Specifically, we exploit the social community structure to combat the unstable network topology in DTNs. We propose a new centrality metric to evaluate the caching capability of each node within a community, and solutions based on this metric are proposed to determine where to cache. More importantly, we consider the impact of the contact duration limitation on cooperative caching, which has been ignored by the existing works. We prove that the marginal caching benefit that a node can provide diminishes when more data is cached. We derive an adaptive caching bound for each mobile node according to its specific contact patterns with others, to limit the amount of data it caches. In this way, both the storage space and the contact opportunities are better utilized. To mitigate the coupon collector's problem, network coding techniques are used to further improve the caching efficiency. Extensive trace-driven simulations show that our cooperative caching protocol can significantly improve the performance of data access in DTNs.

In this paper we investigate interference cancellation to faster identify tags in RFID networks. We explore how interference cancellation can be applied to ALOHA and tree-based identification schemes, its limitations, the extent of achievable improvements, and the overhead incurred to obtain effective gains. Analytical and simulation results show that for an ALOHA-based scheme interference cancellation allows us to identify nearly 23% of tags without directly interrogating them. This speeds up tag identification (over 20% faster) while producing little overhead. For a tree-based scheme nearly 50% of the tags are identified by exploiting interference cancellation, resulting in an improvement of the identification rate of over 20%. Finally, we propose an enhancement of the tree-based scheme with interference cancellation that achieves a further identification speed up of 50%.

We propose an analytical framework to study broadcasting performance in multi channel wireless networks in the presence of adversary attacks. In order to reduce the effect of such attacks on the dissemination performance we use network coding and show that it can bring significant benefits to the broadcasting process. We investigate the impact that different medium access, transmission schemes and channel conditions have on the information exchange among all nodes. We analyze such impact in terms of reception delay and robustness with respect to malicious interference generated by adversary nodes. In order to do so, we model the process of data broadcasting as a coupon collector's problem. We derive the average delay required to retrieve partial and complete information by all nodes in the network, and quantify the gains obtained when using a multi channel system. We take into account the presence of different types of adversaries and find the optimum number of channels that nodes have to access in order to minimize the data reception delay.

In this paper we propose an end-to-end algorithm, called NUM-RS, for jointly selecting link transmission rates and source rates in a multi-hop multi-rate wireless network. Prior works on rate selection, including those that explicitly account for opportunistic reception, perform rate selection on a hop-by-hop basis, attempting to maximize the throughput on each link. Our algorithm leverages the Network Utility Maximization (NUM) framework, thus providing end-to-end semantics for rate selection and proportional fairness with low overhead. By using end-to-end semantics NUM-RS considers both source rates and congestion in the vicinity of links used by a flow when selecting link rates. Our results show that NUM-RS increasingly outperforms contemporary hop-by-hop rate selection schemes as the number of hops in the flows increase. For example, 20% and 50% of 8-hop flows exhibit performance gains of at least 36% and 15%, respectively, in terms of end-to-end throughput. In some cases, gains of up to 80% can be achieved.

Sensor mission assignment concerns matching the sensing resources of a wireless sensor network (WSN) to appropriate tasks (missions), which may come to the network dynamically. Although solutions for WSNs with battery-operated nodes have been proposed for this problem, no attention has been given to networks whose nodes have energy harvesting capabilities, which impose quite a different energy model. In this paper we address this problem by providing both an analytical model and a distributed heuristic, called EN-MASSE, for energy harvesting WSNs. The objective of both model and EN-MASSE is to maximize the profit of the network, fully exploiting the harvesting technologies, while ensuring the execution of the most critical missions within a given target WSN lifetime. The performance of EN-MASSE is evaluated by simulations based on real solar energy traces. Our experiments show that EN-MASSE behaves very closely to the optimum provided by our model and significantly outperforms previously proposed solutions.

In this paper we present a framework and a set of algorithms for determining faults in networks when large scale outages occur. The design principles of our algorithm, netCSI, are motivated by the fact that failures are geographically clustered in such cases. We address the challenge of determining faults with incomplete symptom information due to a limited number of reporting nodes in the network. netCSI consists of two parts: hypotheses generation algorithm, and ranking algorithm. When constructing the hypotheses list of potential causes, we make novel use of the positive and negative symptoms to improve the precision of the results. The ranking algorithm is based on conditional failure probability models that account for the geographic correlation of the network objects in clustered failures. We evaluate the performance of netCSI for networks with both random and realistic topologies. We compare the performance of netCSI with an existing fault diagnosis algorithm, MAX-COVERAGE, and achieve an average gain of 128\% in accuracy for realistic topologies.

Abstract Mobile phones have evolved from simple voice terminals into highly‐capable, general‐purpose computing platforms. While people are becoming increasingly more dependent on such devices to perform sensitive operations, protect secret data, and be available for emergency use, it is clear that phone operating systems are not ready to become mission‐critical systems. Through a pair of vulnerabilities and a simulated attack on a cellular network, we demonstrate that there are a myriad of unmanaged mechanisms on mobile phones, and that control of these mechanisms is vital to achieving reliable use. Through such vectors, mobile phones introduce a variety of new threats to their own applications and the telecommunications infrastructure itself. In this paper, we examine the requirements for providing effective mediation and access control for mobile phones. We then discuss the convergence of cellular networks with the Internet and its impact on effective resource management and quality of service. Based on these results, we argue for user devices that enable predictable behavior in a network—where their trusted computing bases can protect key applications and create predictable network impact. Copyright © 2010 John Wiley & Sons, Ltd.

In this paper, we address the problem of deploying heterogeneous mobile sensors over a target area. Traditional approaches to mobile sensor deployment are specifically designed for homogeneous networks. Nevertheless, network and device homogeneity is an unrealistic assumption in most practical scenarios, and previous approaches fail when adopted in heterogeneous operative settings. For this reason, we introduce VorLag, a generalization of the Voronoi-based approach which exploits the Laguerre geometry. We theoretically prove the appropriateness of our proposal to the management of heterogeneous networks. In addition, we demonstrate that VorLag can be extended to deal with dynamically generated events or uneven energy depletion due to communications. Finally, by means of simulations, we show that VorLag provides a very stable sensor behavior, with fast and guaranteed termination and moderate energy consumption. We also show that VorLag performs better than its traditional counterpart and other methods based on virtual forces.

One of the major challenges in the use of Radio Frequency-based Identification (RFID) on a large scale is the ability to read a large number of tags quickly. Central to solving this problem is resolving collisions that occur when multiple tags reply to the query of a reader. To this purpose, several MAC protocols for passive RFID systems have been proposed. These typically build on traditional MAC schemes, such as aloha and tree-based protocols. In this paper, we propose a new performance metric by which to judge these anticollision protocols: time system efficiency. This metric provides a direct measure of the time taken to read a group of tags. We then evaluate a set of well-known RFID MAC protocols in light of this metric. Based on the insights gained, we propose a new anticollision protocol, and show that it significantly outperforms previously proposed mechanisms.

Conserving the energy for motion is an important yet not-well-addressed problem in mobile sensor networks. In this article, we study the problem of optimizing sensor movement for energy efficiency. We adopt a complete energy model to characterize the entire energy consumption in movement. Based on the model, we propose an optimal trapezoidal velocity schedule for minimizing energy consumption when the road condition is uniform; and a corresponding velocity schedule for the variable road condition by using continuous-state dynamic programming. Considering the variety in motion hardware, we also design one velocity schedule for simple microcontrollers, and one velocity schedule for relatively complex microcontrollers, respectively. Simulation results show that our velocity planning may have significant impact on energy conservation.

In this paper, we address congestion of multicast traffic in multihop wireless networks through a combination of network coding and resource reservation. Network coding reduces the number of transmissions required in multicast flows, thus allowing a network to approach its multicast capacity. In addition, it efficiently repairs errors in multicast flows by combining packets lost at different destinations. However, under conditions of extremely high congestion the repair capability of network coding is seriously degraded. In this paper, we propose cooperative channelization, in which portions of the transmission media are allocated to links that are congested at the point where network coding cannot efficiently repair loss. A health metric is proposed to allow comparison of need for channelization of different multicast links. Cooperative channelization considers the impact of channelization on overall network performance before resource reservation is triggered. Our results show that cooperative channelization improves overall network performance while being well suited for wireless networks using network coding.

Proof of a user's identity is not always a sufficient means for making an authorization decision. In an increasing set of circumstances, knowledge of physical location provides additional and necessary context for making decisions about resource access. For example, sensitive information stored on a laptop (e.g. customer records, social security numbers, etc), may require additional protections if a user operates outside of an approved area. However, current localization techniques based on signal strength reporting or specialized hardware fail to achieve this goal. In this paper, we design, develop, deploy and measure a system which securely determines the location of a user to within one meter through using only off-the-shelf 802.11 and Bluetooth equipment. We apply this equipment in a two-phased challenge- response protocol: first determining the general area of the client in the Regionalization phase and then pinpointing it in the Localization phase. Using nearly 32,000 data points collected over 75 days, we argue that the stability of wireless networks over time creates easily distinguishable location profiles by which a client can be positioned. Additionally, we demonstrate the inherent ability of a two-phased protocol to discern a client's location information at a level of granularity no finer than is necessitated by policy. After discussing a number of applications, we build a location-based access control framework that automatically protects a white-listed set of resources through encryption when the user leaves specified areas. Our analyses show that this system provides a realistic and efficient means of incorporating unforgeable location information at the appropriate level of granularity into many authorization decisions.

3G wireless data networks have emerged as the first high speed, ubiquitous data networks. 4G wireless networks are poised to replace 3G networks as the next generation of mobile data networks, but the transition will be lengthy and expensive. Wireless authentication across 3G and 4G data networks is typically an arduous task, requiring complete disconnection from the existing network before performing a lengthy full authentication on the new network. We introduce an efficient interworking method for CDMA2000 1xEVDO and WiMAX data networks that allows existing authentication credentials to be leveraged in more efficient interworking protocols at both tightly- and loosely-coupled network integration levels, as well as a proactive handoff scheme that takes advantage of our tightly-coupled interworking. We perform a detailed simulation and mathematical analysis of our interworking and handoff protocols and find that our interworking scheme reduces interworking delays by up to 75% in the WiMAX to CDMA case and 85% in the CDMA to WiMAX case.

Network coding has been proposed as an alternative to the conventional store-and-forward routing paradigm for data delivery in networks. When deployed in a multi-rate wireless network, network coding has to interact with rate adaptation. When multicasting packets (a requirement of network coding) in a multi-rate IEEE 802.11 wireless network, one must use care when selecting the transmission rate to use. We refer to this problem as rate selection. We analyze the performance of network coding for a small set of scenarios representative of common topologies in a network that lead to coding opportunities. Based on this analysis, we present our Network Coding aware Rate Selection (NCRS) algorithm which takes into account transmission rates used for unicast links to all multicast targets. Simulation results show that in a multi-hop wireless network, network coding with NCRS achieves up to 24% more gain over routing than network coding with other rate selection algorithms.

In this paper we propose GREASE, a distributed algorithm to deploy mobile sensors in an unknown environment with obstacles and field asperities that may cause sensing anisotropies and non uniform device capabilities. These aspects are not taken into account by traditional approaches to the problem of mobile sensor self-deployment. GREASE works by realizing a grid-shaped deployment throughout the Area of Interest (AoI) and adaptively refining the grid to find new sensor positions to cover the target area more precisely in the zones where devices experience reduced movement, sensing and communication capabilities. We give bounds on the number of sensors necessary to cover an AoI with obstacles and noisy zones. Simulations show that GREASE provides a fast deployment with precise movements and no oscillations, with moderate energy consumption.

Network coding has been proposed as a technique that can potentially increase the transport capacity of a wireless network via processing and mixing of data packets at intermediate routers. However, most previous studies either assume a fixed transmission rate or do not consider the impact of using diverse rates on the network coding gain. Since in many cases, network coding implicitly relies on overhearing, the choice of the transmission rate has a big impact on the achievable gains. The use of higher rates works in favor of increasing the native throughput; however, it may in many cases work against effective overhearing. In other words, there is a tension between the achievable network coding gain and the inherent rate gain possible on a link. In this paper our goal is to drive the network towards achieving the best trade-off between these two contradictory effects. Towards this, we design a distributed framework that (a) facilitates the choice of the best rate on each link while considering the need for overhearing and (b) dictates the choice of which decoding recipient will acknowledge the reception of an encoded packet. We demonstrate that both of these features contribute significantly towards gains in throughput. We extensively simulate our framework in a variety of topological settings. We also fully implement it on real hardware and demonstrate its applicability and performance gains via proof-of-concept experiments on our wireless testbed. We show that our framework yields throughput gains of up to 390% as compared to what is achieved in a rate-unaware network coding framework.

We study a problem in which a single sensor is scheduled to observe sites periodically, motivated by applications in which the goal is to maintain up-to-date readings for all the observed sites. In the existing literature, it is typically assumed that the time for a sensor switching from one site to another is negligible. This may not be the case in applications such as camera surveillance of a border, however, in which the camera takes time to pan and tilt to refocus itself to a new geographical location. We formulate a problem with refocusing delay constraints. We prove the problem to be NP-hard and then study a special case in which refocusing is proportional to some Euclidian metric. We give a lower bound on the optimal cost for the scheduling problem. Finally, we provide and experimentally evaluate several heuristic algorithms, some of them based on this computed lower bound.

When a sensor network is deployed, it is typically required to support multiple simultaneous missions. Schemes that assign sensing resources to missions thus become necessary. In this article, we formally define the sensor-mission assignment problem and discuss some of its variants. In its most general form, this problem is NP-hard. We propose algorithms for the different variants, some of which include approximation guarantees. We also propose distributed algorithms to assign sensors to missions which we adapt to include energy-awareness to extend network lifetime. Finally, we show comprehensive simulation results comparing these solutions to an upper bound on the optimal solution.

When a sensor network is deployed in the field it is typically required to support multiple simultaneous missions, which may start and finish at different times. Schemes that match sensor resources to mission demands thus become necessary. In this paper, we consider new sensor-assignment problems motivated by frugality, i.e., the conservation of resources, for both static and dynamic settings. In the most general setting, the problems we study are NP-hard even to approximate, and so we focus on heuristic algorithms that perform well in practice. In the static setting, we propose a greedy centralized solution and a more sophisticated solution that uses the Generalized Assignment Problem model and can be implemented in a distributed fashion. In what we call the dynamic setting, missions arrive over time and have different durations. For this setting, we give heuristic algorithms in which available sensors propose to nearby missions as they arrive. We find that the overall performance can be significantly improved if available sensors sometimes refuse to offer utility to missions they could help, making this decision based on the value of the mission, the sensor's remaining energy, and (if known) the remaining target lifetime of the network. Finally, we evaluate our solutions through simulations.

The vast expansion of interconnectivity with the Internet and the rapid evolution of highly-capable but largely insecure mobile devices threatens cellular networks. In this paper, we characterize the impact of the large scale compromise and coordination of mobile phones in attacks against the core of these networks. Through a combination of measurement, simulation and analysis, we demonstrate the ability of a botnet composed of as few as 11,750 compromised mobile phones to degrade service to area-code sized regions by 93%. As such attacks are accomplished through the execution of network service requests and not a constant stream of phone calls, users are unlikely to be aware of their occurrence. We then investigate a number of significant network bottlenecks, their impact on the density of compromised nodes per base station and how they can be avoided. We conclude by discussing a number of countermeasures that may help to partially mitigate the threats posed by such attacks.

The multiple backhaul mobile access router (MAR) can provide high capacity and high performance Internet access for emerging mobile wireless applications. In this paper we improve the MAR with the capability to stripe traffic from clients over multiple available network devices. The MAR allows different backhauls to be used simultaneously and accommodates diverse policies. We present experimental results to validate the per user striping performance of our MAR and explore trade-offs when integrating switching policies. With the above enhancements, the MAR is able to provide aggregated communication channels to the users, and enhance reliability by switching wireless interfaces when it is necessary.

In this paper we address the problem of deploying heterogeneous mobile sensors over a target area. We show how traditional approaches designed for homogeneous networks fail when adopted in the heterogeneous operative setting.

We consider variations of a problem in which data must be delivered to mobile clients en-route, as they travel towards their destinations. The data can only be delivered to the mobile clients as they pass within range of wireless base stations. Example scenarios include the delivery of building maps to firefighters responding to multiple alarms, and the in-transit ldquoilluminationrdquo of simultaneous surface-to-air missiles. We cast this scenario as a parallel-machine scheduling problem with the little-studied property that jobs may have different release times and deadlines when assigned to different machines. We present new algorithms and also adapt existing algorithms, for both online and offline settings. We evaluate these algorithms on a variety of problem instance types, using both synthetic and real-world data, including several geographical scenarios, and show that our algorithms produce schedules achieving near-optimal throughput.

In many situations it is important to deliver information to personnel as they work in the field. We consider such a specialized content distribution application in wireless mesh networks. When a new mission arrives-for example, when an alarm for a fire is reported-data is pushed to storage nodes at the mission site where it may be retrieved locally by responding personnel (e.g., police, firefighters, paramedics, government officials, and the media). It is important that information is available at low latency, when requested or pulled by the personnel. The total latency experienced will be a combination of the push delay (if the personnel arrive at the mission site before all the data can be pushed), and the pull delay. Each delay component will in turn be a function of 1) the hop distance traveled by the data when pushed or pulled and 2) the congestion on the links. In this paper, we define algorithms and protocols that trade-off the push and pull latencies depending on the type of application. Our goal is to choose a storage node assignment minimizing the total latency-based cost. We start with a simple model in which cost is a function of distance, and then extend the model explicitly taking congestion into account. Since the problem is NP-hard to approximate, our focus is on developing efficient algorithms and distributed protocols that can be easily deployed in wireless mesh networks. In NS2 simulations, we find that our heuristic algorithms achieve on average a cost within at most 15 % of the optimum.

Both bandwidth and energy become important resource constraints when multi-hop wireless networks are used to transport relatively high data rate sensor flows. A particularly challenging problem involves the selection of flow data rates that maximize application (or mission) utilities over a time horizon, especially when different missions are active over different time intervals. Prior works on utility driven adaptation of flow data rates typically focus only on instantaneous utility maximization and are unable to address this temporal variation in mission durations. In this work, we derive an optimal control-based Network Utility Maximization (NUM) framework that is able to maximize the system utility over a lifetime that is known either deterministically or statistically. We first consider a static setup in which all the missions are continuously active for a deterministic duration, and show how the rates can be optimally adapted, via a distributed protocol, to maximize the total utility. Next, we develop adaptive protocols for the dynamic cases when we have (i) complete knowledge about the mission utilities and their arrivals and departures, and (ii) a varying amount of statistical information about the missions. Our simulation results indicate that our protocols are robust, efficient and close to the optimal.

Source location privacy is an important issue in sensor network monitoring applications. It is difficult to be addressed by traditional security mechanisms, because an external attacker may perform simple traffic analysis to trace back to the event source. Solutions such as flooding or using dummy messages have the drawback of introducing a large amount of message overhead. In this paper, we avoid using network-wide dummy messages by utilizing beacons at the MAC layer. Beacons are sent out regularly, which essentially forms a constant-rate of dummy messages. Using beacons to replace the dummy messages may increase the delivery delay of event information because beacons are only sent out at the predefined beacon interval, but this latency can be controlled. To do this, we propose a cross- layer solution in which the event information is first propagated several hops through a MAC-layer beacon. Then, it is propagated at the routing layer to the destination to avoid further beacon delays. Simulation results show that our cross-layer solutions can maintain low message overhead and high privacy, while controlling delay.

Location based services(LBS) are becoming increasingly important to the success and attractiveness of next generation wireless systems. However, a natural tension arises between the need for user privacy and the flexible use of location information. In this paper we present a framework to support privacy enhanced location based services. We classify the services according to several basic criteria and we propose a hierarchical key distribution method to support these services. The key idea behind the system is to hierarchically encrypt location information under different keys, and distribute the appropriate keys only to group members with the necessary permission. Four methods are proposed to deliver hierarchical location information while maintaining privacy. We propose a key tree rebalancing algorithm to maintain the re-keying performance of the group key management. Furthermore, we present a practical LBS system implementation. Hierarchical location information coding offers flexible location information access which enables a rich set of location based services. Our load tests show such a system is highly practical with good efficiency and scalability.

There has been a growing interest in designing mobile systems consisting of special relay nodes whose mobility can be controlled by the underlying network. In this paper, we consider the design of a heterogeneous mobile ad hoc network (MANET) consisting of two kinds of mobile nodes-traditional nodes with limited energy and a few controllable mobile relay nodes with relatively abundant energy resources. We propose a novel relay deployment framework that utilizes mobility prediction and works in tandem with the underlying MANET routing protocol to optimally define the movement of the relay nodes. We present two instances of the relay deployment problem, together with the solutions, to achieve different goals. Instance 1, termed Min-Total, aims to minimize the total energy consumed across all the traditional nodes during data transmission, while instance 2, termed Min-Max, aims to minimize the maximum energy consumed by a traditional node during data transmission. Our solutions also enable the prioritization of individual nodes in the network based on residual energy profiles and contextual significance. We perform an extensive simulation study to understand the trade-offs involved in deploying an increasing fraction of such relay nodes in the network. We also investigate the performance of the proposed framework under different mobility prediction schemes. Results indicate that even when the relay nodes constitute a small fraction of the total nodes in the network, the proposed framework results in significant energy savings. Further, we observed that while both the schemes have their potential advantages, the differences between the two optimization schemes are clearly highlighted in a sparse network.

The widespread acceptance of RFID tags in inventory control applications has allowed the development of increasingly complex and useful inventory management techniques. This paper approaches the problem of real-time inventory querying in a large warehouse. We use a combination of powered, wireless- capable active RFID tags and a mobile RFID reader to design a querying system that uses both a mesh network formed with the active RFID tags and the mobile reader to balance query latency and total network lifetime. We implemented and simulated our system on Crossbow MicaZ motes and a custom robot platform. Our results show that our hybrid algorithm balances query latency and network lifetime more effectively than mesh network- only and mobile reader-only algorithms. In particular, we see network power consumption reduction of up to 60% and a 15% reduction in total distance travelled by the mobile reader. We conclude that introducing a mobile reader to active tag networks allows the design of flexible network algorithms that can reduce the impact of battery life on the network.

When a sensor network is deployed in the field, it is typically required to support multiple simultaneous missions, which may start and finish at different times. Schemes that match sensor resources to mission demands thus become necessary. In this paper, we propose centralized and distributed schemes to assign sensors to missions. We also adapt our distributed scheme to make it energy-aware to extend network lifetime. Finally, we show simulation results comparing these solutions. We find that our greedy algorithm frequently performs near-optimally and that the distributed schemes usually perform nearly as well.

The multiple backhaul mobile access router aims to provide high capacity and high performance Internet access for emerging mobile wireless applications. In this paper we describe the framework and implementation of a modular mobile access router system. A set of backhaul interface monitoring APIs are provided to support flexible handover policies. We present the experimental results to validate the performance of our mobile access router and illustrate tradeoffs when designing handover policies.

Network coding is increasingly being investigated as an alternative to routing to increase throughput in packet networks. Like most data transfer schemes, the effectiveness of network coding may be limited by extreme congestion. When using network coding, these congested conditions are mitigated somewhat, but may still occur. We propose a selective channelization scheme in which links that experience congestion at a level that cannot be overcome by network coding are given reserved communication resources. This method has the following benefits. First, the algorithm proposed allows network coding full opportunity to overcome congestion before performing channelization, thus reducing the number of reserved resources used. Second, when triggered, the channelization of severely congested links greatly improves the end-to-end performance of flows that traverse the channelized link. To determine the point at which channelization should be triggered, we perform a thorough analysis of potential coding gains in a network facing errors due to collisions, and determine the point at which network coding loses its effectiveness.

We extend the existing network utility maximization (NUM) framework for wired networks to wireless sensor networks by formulating it in order to take into account interference among radio links. We study the conditions under which the formulated problem is a feasible convex optimization problem. Under such conditions, a distributed algorithm is proposed to solve the problem optimally. Finally, we provide numerical results, based on computer simulations, to show the performance of the proposed algorithm and the rate of convergence of its solution.

In sensor networks applied to monitoring applications, individual sensors may perform preassigned or on-demand tasks, or missions. Data updates (info-pages) may be sent to sensors from a command center, via a time-division broadcast channel. Sensors are normally put in sleep mode when not actively listening, in order to conserve energy in their batteries. Hence, a schedule is required that specifies when sensors should listen for updates and when they should sleep. The performance of such a schedule is evaluated based on data-related costs and sensor-related costs. Data-related costs reflect the obsoleteness of current sensor data, or the delay while sensors wait for updated instructions. Sensor-related costs reflect the energy that sensors consume while accessing the broadcast channel and while switching between the active and sleeping modes (rebooting). Our goal is a schedule with the minimum total cost. Previous related work has explored data-related costs, but listening cost has been addressed only under the assumption that the rebooting operation is free. This paper formulates a new cost model, which recognizes the cost of sensor rebooting. We derive an optimal schedule for the single-sensor setting. We proceed to consider schedules of multiple sensors, and formulate a mathematical program to find an optimal fractional schedule for this setting. Several heuristics for scheduling multiple sensors are introduced and analyzed, and various tradeoffs among the cost factors are demonstrated.

This paper extends the distributed network utility maximization (NUM) framework to consider the case of resource sharing by multiple competing missions in a military-centric wireless sensor network (WSN) environment. Prior work on NUM-based optimization has considered unicast flows with sender-based utilities in either wireline or wireless networks. We extend the NUM framework to consider three key new features observed in mission-centric WSN environments: i) the definition of an individual mission's utility as a joint function of data from multiple sensor sources ii) the consumption of each senders (sensor) data by multiple receivers (missions) and iii) the multicast-tree based dissemination of each sensors data flow, using link-layer broadcasts to exploit the "wireless broadcast advantage" in data forwarding. We show how a receiver-centric, pricing-based, decentralized algorithm can ensure optimal and proportionally-fair rate allocation across the multiple missions, without requiring any coordination among independent missions (or sensors). We also discuss techniques to improve the speed of convergence of the protocol, which is essential in an environment as dynamic as the WSN.

Significant progress has been made to achieve video streaming over wireless ad hoc networks. However, there is not much work on providing security. Is existing security solution good enough for securing video streaming over ad hoc networks? In this paper, we discover a cross-layer dropping attack against video streaming. We first identify a general IP layer dropping attack and then reveal its destructive impact by leveraging the application layer information (e.g., video streaming). Through simulations, we quantify the impact of this attack as a function of several performance parameters such as delivery ratio, hop number and the number of attackers. The surprising result with this attack is that with a 94% delivery ratio, the receiver still cannot watch the video! We also propose several possible solutions to address the dropping attacks. Due to the unique characteristics of this attack, as long as malicious nodes exist, the network will suffer from this dropping attack.

In typical deployments of infrastructure wireless mesh networks, mesh clients are directly connected to a mesh router. The mesh routers form a multi-hop wireless mesh backbone to provide connectivity to the Internet. In this paper, we propose and evaluate a set of distributed algorithms that enable mesh clients to form a multi-hop wireless relay network to have access to the mesh backbone. The proposed algorithms include path discovery, channel allocation, path selection, and local tuning of the resulting relay network. Results show that the performance of the relay network formed by our algorithms is very close to the optimal performance that the network can achieve.

A major security vulnerability in the mobile telecommunication network is that wireline signaling messages are cleartext. The latest protocol for wireline signaling message security is Mobile Application Part Security (MAPSec), which protects MAP (a signaling message protocol) messages on the link between nodes. MAPSec is a limited solution because it still leaves MAP signaling messages unsecured in intermediate nodes, and also leaves other wireline signaling message protocols unsecured both on the link and in intermediate nodes. Hence, there is a need for a more comprehensive wireline security scheme to protect all types of wireline signaling messages end-to-end i.e., both on the link and in intermediate nodes. As a solution, we propose EndSec, an end-to-end wireline signaling message security protocol for all types of signaling messages. EndSec works by inserting cryptographic checks on data items in signaling messages, has capabilities to self-detect and repair corruption, and identifies the nodes causing corruption.

Cellular networks are a critical component of the economic and social infrastructures in which we live. In addition to voice services, these networks deliver alphanumeric text messages to the vast majority of wireless subscribers. To encourage the expansion of this new service, telecommunications c ompanies offer connections between their networks and the Internet. The ramifications of such connections, however, have not been fully recognized. In this paper, we evaluate the security impact of the SMS interface on the availability of the cellular phone network. Specifically, we describe the ability to deny voice service to cities the size of Washington DC and Manhattan with little more than a cable modem. Moreover, attacks targeting the entire United States are feasible with resources available to medium-sized zombie networks. This analysis begins with an exploration of the structure of cellular networks. We then characterize network behavior and explore a number of reconnaissance techniques aimed at effectively targeting attacks on these systems. We conclude by discussing countermeasures that mitigate or eliminate the threats introduced by these attacks.

Data generated in wireless sensor networks may not all be alike: some data may be more important than others and hence may have different delivery requirements. In this paper, we address differentiated data delivery in the presence of congestion in wireless sensor networks. We propose a class of algorithms that enforce differentiated routing based on the congested areas of a network and data priority. The basic protocol, called congestion-aware routing (CAR), discovers the congested zone of the network that exists between high-priority data sources and the data sink and, using simple forwarding rules, dedicates this portion of the network to forwarding primarily high-priority traffic. Since CAR requires some overhead for establishing the high-priority routing zone, it is unsuitable for highly mobile data sources. To accommodate these, we define MAC-enhanced CAR (MCAR), which includes MAC-layer enhancements and a protocol for forming high-priority paths on the fly for each burst of data. MCAR effectively handles the mobility of high-priority data sources, at the expense of degrading the performance of low-priority traffic. We present extensive simulation results for CAR and MCAR, and an implementation of MCAR on a 48-node testbed.

One practical limitation of structured peer-to-peer (P2P) networks is that they are frequently subject to Sybil attacks: malicious parties can compromise the network by generating and controlling large numbers of shadow identities. In this paper, we propose an admission control system that mitigates Sybil attacks by adaptively constructing a hierarchy of cooperative peers. The admission control system vets joining nodes via client puzzles. A node wishing to join the network is serially challenged by the nodes from a leaf to the root of the hierarchy. Nodes completing the puzzles of all nodes in the chain are provided a cryptographic proof of the vetted identity. We evaluate our solution and show that an adversary must perform days or weeks of effort to obtain even a small percentage of nodes in small P2P networks, and that this effort increases linearly with the size of the network. We further show that we can place a ceiling on the number of IDs any adversary may obtain by requiring periodic reassertion of the IDs continued validity.

Wireless mesh networks are emerging as a means to provide ubiquitous network connectivity using various radio technologies. In this paper we propose and evaluate a set of distributed algorithms to form a multi-hop relay network to access the backbone in wireless mesh networks. The proposed algorithms include path discovery, frequency allocation, path selection, and local tuning of the resulting relay network. Our results show that the performance of the relay network formed by our algorithms is very close to the optimal performance that the network can achieve.

Mobile sensors are useful in many environments because they can move to increase the sensing coverage. In this paper, we present a mobile sensor prototype in which the Mica2 sensor node is used to control the movement of the robot built with commercial off-the-shelf (COTS) components. We use a sensor relocation application to demonstrate the feasibility of our design. In the sensor relocation application, after a sensor node failure creates a coverage hole, a mobile sensor node is relocated to cover the hole in a timely and energy-efficient way. We present a distributed sensor relocation algorithm and provide novel solutions to implement this algorithm in our mobile sensor platform. Experimental results show that our relocation algorithm can reduce the sensor relocation time and balance the energy consumption of the mobile nodes.

Mobile sensors are useful in many environments because they can move to increase the sensing coverage. In this paper, we present a mobile sensor prototype in which the Mica2 sensor node is used to control the movement of the robot built with commercial off-the-shelf (COTS) components. We use a sensor relocation application to demonstrate the feasibility of our design. In the sensor relocation application, after a sensor node failure creates a coverage hole, a mobile sensor node is relocated to cover the hole in a timely and energy-efficient way.

In recent years, there has been a growing interest in designing mobile systems consisting of special relay nodes whose mobility can be controlled by the underlying network. In this paper, we consider the design of a heterogeneous mobile ad hoc network (MANET) consisting of two kinds of mobile nodes - the traditional nodes with limited energy and a few mobility controllable relay nodes with relatively abundant energy resources. We propose the relay deployment problem that aims to optimally position these relay nodes in the network so as to minimize the overall power consumption for data transmission at the traditional nodes. We present a mobility prediction based framework to solve to the relay deployment problem in a truly mobile network. We investigate the performance of the proposed framework through extensive simulation study using three different mobility prediction schemes. We also perform experiments to understand the tradeoffs involved in deploying an increasing fraction of such relay nodes in the network. Results indicate that even when the relay nodes constitute a small percentage of the total nodes in the network, the proposed framework results in significant energy savings.

Many applications that make use of sensor networks require secure communication. Because asymmetric-key solutions are difficult to implement in such a resource-constrained environment, symmetric-key methods coupled with a priori key distribution schemes have been proposed to achieve the goals of data secrecy and integrity. These approaches typically assume that all nodes are similar in terms of capabilities and, hence, deploy the same number of keys in all sensors in a network to provide the aforementioned protections. In this paper, we demonstrate that a probabilistic unbalanced distribution of keys throughout the network that leverages the existence of a small percentage of more capable sensor nodes can not only provide an equal level of security, but also reduce the consequences of node compromise. To fully characterize the effects of the unbalanced key management system, we design, implement, and measure the performance of a complementary suite of key establishment protocols known as LIGER. Using their predeployed keys, nodes operating in isolation from external networks can securely and efficiently establish keys with each other. Should resources such as a backhaul link to a key distribution center (KDC) become available, networks implementing LIGER automatically incorporate and benefit from such facilities. Detailed experiments demonstrate that the unbalanced distribution in combination with the multimodal LIGER suite offers a robust and practical solution to the security needs in sensor networks

Constructing a sensor network with a mix of mobile and static sensors can achieve a balance between sensor coverage and sensor cost. In this paper, we design two bidding protocols to guide the movement of mobile sensors in such sensor networks to increase the coverage to a desirable level. In the protocols, static sensors detect coverage holes locally by using Voronoi diagrams and bid mobile sensors to move. Mobile sensors accept the highest bids and heal the largest holes. Simulation results show that our protocols achieve suitable trade-off between coverage and sensor cost

In wireless sensor networks, sensor nodes are capable of not only measuring real world phenomena, but also storing, processing, and transferring these measurements. Many techniques have been proposed for disseminating sensing data. However, most of them are not efficient in the scenarios where a huge amount of sensing data are generated, but only a small portion of them are queried. In this paper, we first propose an index-based data dissemination scheme to address the problem. With this scheme, sensing data are collected, processed, and stored at the nodes close to the detecting nodes, and the location information of these storing nodes is pushed to some index nodes, which act as the rendezvous points for sinks and sources. To address the issues of fault tolerance and load balance, we extend the scheme with an adaptive ring-based index (ARI) technique in which the index nodes for one event type form a ring surrounding the location which is determined by the event type, and the ring can be dynamically reconfigured. Considering that frequently updating or querying index nodes may cause high overhead, we also propose a lazy index updating (LIU) mechanism and a lazy index querying (LIQ) mechanism to reduce the overhead. Analysis and simulations are conducted to evaluate the performance of the proposed scheme. The results show that the proposed scheme outperforms the external storage-based scheme, the DCS scheme, and the local storage-based schemes with flood-response style. The results also show that using ARI can tolerate clustering failures and achieve load balance and using LIU (LIQ) can further improve the system performance. is pushed to some index nodes,

Abstract — Many applications that make use of sensor networks require secure communication. Because asymmetric-key solutions are difficult to implement in such a resource-constrained environment, symmetric-key methods coupled with a priori key distribution schemes have been proposed to achieve the goals of data secrecy and integrity. These approaches typically assume that all sensors are similar in terms of capabilities, and hence deploy the same number of keys in all sensors in a network to provide the aforementioned protections. In this paper we demonstrate that a probabilistic unbalanced distribution of keys throughout the network that leverages the existence of a small percentage of more capable sensor nodes can not only provide an equal level of security but also reduce the consequences of node compromise. We demonstrate the effectiveness of this approach on small networks using a variety of trust models and then demonstrate the application of this method to very large systems. The approach and analysis presented in this paper can be applied to all protocols that use probabilistic keys including those that employ broadcast mechanisms, hash functions or polynomials for the generation of keys.

The transformation of telecommunications networks from homogeneous closed systems providing only voice services to Internet-connected open networks that provide voice and data services presents significant security challenges. For example, recent research illustrated that a carefully crafted DoS attack via text messaging could incapacitate all voice communications in a metropolitan area with little more than a cable modem. This attack highlights a growing threat to these systems; namely, cellular networks are increasingly exposed to adversaries both in and outside the network. In this paper, we use a combination of modeling and simulation to demonstrate the feasibility of targeted text messaging attacks. Under realistic network conditions, we show that adversaries can achieve blocking rates of more than 70% with only limited resources. We then develop and characterize five techniques from within two broad classes of countermeasures - queue management and resource provisioning. Our analysis demonstrates that these techniques can eliminate or extensively mitigate even the most intense targeted text messaging attacks. We conclude by considering the tradeoffs inherent to the application of these techniques in current and next generation telecommunications networks.

The majority of security schemes available for sensor networks assume deployment in areas without access to a wired infrastructure. More specifically, nodes in these networks are unable to leverage key distribution centers (KDCs) to assist them with key management. In networks with a heterogeneous mix of nodes, however, it is not unrealistic to assume that some more powerful nodes have at least intermittent contact with a backbone network. For instance, an air-deployed battlefield network may have to operate securely for some time until uplinked friendly forces move through the area. We therefore propose LIGER, a hybrid key management scheme for heterogeneous sensor networks that allows systems to operate in both the presence and absence of a KDC. Specifically, when no KDC is available, nodes communicate securely with each other based upon a probabilistic unbalanced method of key management. The ability to access a KDC allows nodes to probabilistically authenticate neighboring devices with which they are communicating. We also demonstrate that this scheme is robust to the compromise of both low and high capability nodes and that the same keys can be used for both modes of operation. Detailed experiments and simulations are used to show that LIGER is a highly practical solution for the current generation of sensors and the unbalanced approach can significantly reduce network initialization time.

Mobility management protocols allow wireless devices to move between networks. These protocols have traditionally supported the mobility of individual nodes and are therefore not optimized to support the migration of groups. Accordingly, the time required to re-establish connectivity, frequency of dropped packets and contention for the air interface increase significantly for mobile groups. We propose a protocol for mobile groups that reduces all of the above by allowing a single node to perform handoffs on behalf of all group members. This "gateway" node eliminates the need for multiple handoff messages by obscuring group membership to external parties. Through extensive simulation and implementation, we show significant reduction in handoff times, message complexity and packet loss for groups of heterogeneous, mobile sensors running AODV and DSDV. By leveraging the naturally occurring hierarchy, we demonstrate that it is possible for groups to efficiently use traditional mobility protocols to support their collective movements.

Secure data dissemination in wireless ad hoc and sensor networks has recently received a great deal of attention. A variety of protocols have been proposed in order to ensure secure data delivery across these systems; however, the majority of these schemes assume the presence of public or pre-established symmetric keys. Accordingly, the cost of key management has not been incorporated into secure routing mechanisms in this setting. This paper considers the expenses incurred by sensor networks implementing secure routing schemes on top of probabilistic symmetric key management schemes. Specifically, we examine the overhead observed from proactive and reactive key establishment mechanisms for networks using a balanced method of key management. Through extensive simulation, we quantify more realistic costs for the application of secure hop-by-hop routing in sensor networks

Abstract-Adequate coverage is very important for sensor networks to fulfill the issued sensing tasks. In many working environments, it is necessary to make use of mobile sensors, which can move to the correct places to provide the required coverage. In this paper, we study the problem of placing mobile sensors to get high coverage. Based on Voronoi diagrams, we design two sets of distributed protocols for controlling the movement of sensors, one favoring communication and one favoring movement. In each set of protocols, we use Voronoi diagrams to detect coverage holes and use one of three algorithms to calculate the target locations of sensors it holes exist. Simulation results show the effectiveness of our protocols and give insight on choosing protocols and calculation algorithms under different application requirements and working conditions.

Cellular networks are a critical component of the economic and social infrastructures in which we live. In addition to voice services, these networks deliver alphanumeric text messages to the vast majority of wireless subscribers. To encourage the expansion of this new service, telecommunications companies offer connections between their networks and the Internet. The ramifications of such connections, however, have not been fully recognized. In this paper, we evaluate the security impact of the SMS interface on the availability of the cellular phone network. Specifically, we demonstrate the ability to deny voice service to cities the size of Washington D.C. and Manhattan with little more than a cable modem. Moreover, attacks targeting the entire United States are feasible with resources available to medium-sized zombie networks. This analysis begins with an exploration of the structure of cellular networks. We then characterize network behavior and explore a number of reconnaissance techniques aimed at effectively targeting attacks on these systems. We conclude by discussing countermeasures that mitigate or eliminate the threats introduced by these attacks.

Location based services are becoming increasingly important to the success and attractiveness of next generation wireless systems. Service providers will use location information to introduce new services and greatly enhance many existing services. Maintaining location privacy is an important requirement that must be met for these services to be widely deployed. It is a challenge to maintain location privacy while still providing the flexible access to location information required to enable a rich set of location based services. In this paper we define a high-level architecture for providing LBS and classify services according to several basic criteria. To support these services we propose a hierarchical key distribution method. Four methods are proposed to deliver hierarchical location information while maintaining privacy. We evaluate the efficiency of the system in terms of message delivery and key management overhead

Summary form only given. Telecommunication networks are evolving from closed systems with limited, standardized services, to open systems which will allow great creativity in building and deploying new services. These systems will heavily leverage Internet technology in an effort to create this open environment. This evolution is being aggressively pursued by wireless service providers (WSPs). Along with the benefits of these networks come increasingly high risks of a variety of attacks that may compromise security. Current, so called second generation (2G) wireless telecommunication networks are implemented using standardized control protocols for user and device authentication, mobility management, session control and services control. These networks are closed in the sense that control messages are exchanged on a private packet-switched network based on the signaling system No. 7 standards. Because of their closed nature, there are few successful attacks on these networks. The next, so called third generation (3G) wireless telecommunication networks are migrating towards IP technology, with the ultimate goal being an all-IP network. Standards for these systems, called the IP multimedia subsystem (IMS) are being defined by the third generation partnership projects (3GPP and 3GPP2). These networks will use IP for transport of information, and Internet protocols such as the session initiation protocol (SIP) and mobile IP, for session control and mobility management. These networks open the possibility for IP-based services and must interwork with 2G networks. Because new services will be introduced in the IP-domain of these networks, new attacks on 3G networks are possible. Because IP networks are more accessible than SS7 networks, the control portion of the 3G networks is now more vulnerable to attack. These attacks may be remote denial of service attacks, or attacks that target the integrity of specific services. The means of the attack may vary depending on the interworking model used and the service being offered. In this talk we discuss the different security risks in IP-based 3G networks, different attack types, and the trade-offs of high performance, open network architectures versus secure network infrastructure.

We propose multi-class signaling overload control algorithms, for telecommunication switches, that are robust against different input traffic patterns and system upgrades. In order to appropriately measure the system load when several classes of signaling traffic are present, we first introduce the concept of equivalent system load measure that converts the multiple system measures associated with different classes of traffic into a single measure with respect to a pre-defined base class. We use this measure to develop three multi-class overload detection and measurement algorithms. Next, we develop a new algorithm for partitioning the allowable equivalent system load across multiple traffic classes, using a strict priority scheme. Using simulations of call flows from mobile telecommunications standards, we compare different multi-class overload algorithms under a variety of overload conditions. Our simulation results indicate that our algorithm that measures system load using a combination of request acceptance rate and processor occupancy provides highly reactive and robust overload control. Last, for the purpose of making the overload control algorithms more robust, we propose a measurement-based simple regression technique to dynamically estimate key system parameters. We find that estimates derived in this manner converge rapidly to their true values.

To achieve high throughput in wireless networks, smart forwarding and processing of packets in access routers are critical for overcoming the effects of the wireless links. However, these services cannot be provided if data sessions are protected using end-to-end encryption as with IPsec, because the information needed by these algorithms resides inside the portion of the packet that is encrypted, and can therefore not be used by the access routers. A previously proposed protocol, called multi-layered IPsec (ML-IPsec) modifies IPsec in a way so that certain portions of the datagram may be exposed to intermediate network elements, enabling these elements to provide performance enhancements. In this paper we extend ML-IPsec to deal with mobility and make it suitable for wireless networks. We define and present performance measurements of an efficient key distribution protocol to enable fast ML-IPsec session initialization, and two mobility protocols that are compatible with mobile IP and maintain ML-IPsec sessions. Our measurements show that, depending on the mobility protocol chosen, integrated mobile IP/ML-IPsec handoffs result in a pause of 56-105 milliseconds, of which only 31-85 milliseconds may be attributed to ML-IPsec. Further, we provide detailed discussion and performance measurements of our ML-IPsec implementation. We find the resulting protocol only marginally reduces throughput compared to scenarios in which IPsec is used (4%), and when coupled with SNOOP, greatly increases throughput over scenarios using standard TCP over IPsec (165% on average).

Recently there has been a great deal of research on using mobility in sensor networks to assist in the initial deployment of nodes. Mobile sensors are useful in this environment because they can move to locations that meet sensing coverage requirements. This paper explores the motion capability to relocate sensors to deal with sensor failure or respond to new events. We define the problem of sensor relocation and propose a two-phase sensor relocation solution: redundant sensors are first identified and then relocated to the target location. We propose a Grid-Quorum solution to quickly locate the closest redundant sensor with low message complexity, and propose to use cascaded movement to relocate the redundant sensor in a timely, efficient and balanced way. Simulation results verify that the proposed solution outperforms others in terms of relocation time, total energy consumption, and minimum remaining energy.

Conserving the energy for motion is an important yet not-well-addressed problem in mobile sensor networks. In this paper, we study the problem of optimizing sensor movement for energy efficiency. We adopt a complete energy model to characterize the entire energy consumption in movement. Based on the model, we propose an optimal velocity schedule for minimizing energy consumption when the road condition is uniform; and a near optimal velocity schedule for the variable road condition by using continuous-state dynamic programming. Considering the variety in motion hardware, we also design one velocity schedule for simple microcontrollers, and one velocity schedule for relatively complex microcontrollers, respectively. Simulation results show that our velocity planning may have significant impact on energy conservation

Nodes forward data on behalf of each other in mobile ad hoc networks. In a civilian application, nodes are assumed to be selfish and rational, i.e., they pursue their own self-interest. Hence, the ability to accurately measure traffic forwarding is critical to ensure proper network operation. These measurements are often used to credit nodes based on their level of participation, or to detect loss. Past solutions employ neighbor monitoring and reporting on node forwarding traffic. These methods are not applicable in civilian networks where neighbor nodes lack the desire or ability to perform the monitoring function. Such environments occur frequently in which neighbor hosts are resource constrained, or in networks where directional antennas are used and reliable monitoring is difficult or impossible. In this paper, we propose a protocol that uses nodes on the data path to securely produce packet forwarding reports. Reporting nodes are chosen randomly and secretly so that malicious nodes cannot modify their behavior based upon the monitoring point. The integrity and authenticity of reports are preserved through the use of secure link layer acknowledgments and monitoring reports. The robustness of the reporting mechanism is strengthened by forwarding the report to multiple destinations (source and destination). We explore the security, cost, and accuracy of our protocol.

Sensor deployment is an important issue in designing sensor networks. We design and evaluate distributed self-deployment protocols for mobile sensors. After discovering a coverage hole, the proposed protocols calculate the target positions of the sensors where they should move. We use Voronoi diagrams to discover the coverage holes and design three movement-assisted sensor deployment protocols, VEC (vector-based), VOR (Voronoi-based), and minimax based on the principle of moving sensors from densely deployed areas to sparsely deployed areas. Simulation results show that our protocols can provide high coverage within a short deploying time and limited movement.

In wireless sensor networks, efficiently disseminating data from a dynamic source to multiple mobile sinks is important for applications such as mobile target detection and tracking. A tree-based multicasting scheme can be used. However, due to the short communication range of each sensor node and the frequent movement of sources and sinks, a sink may fail to receive data due to broken paths, and the tree should frequently be reconfigured to reconnect sources and sinks. To address the problem, we propose a dynamic proxy tree-based framework. A big challenge in implementing the framework is how to reconfigure the proxy tree efficiently as sources and sinks change. We model the problem as on-line construction of a minimum Steiner tree in a Euclidean plane, and propose centralized schemes to solve it. Considering the strict energy constraints in wireless sensor networks, we further propose two distributed on-line schemes, a shortest path-based (SP) scheme and a spanning range-based (SR) scheme. Extensive simulations are conducted to evaluate the schemes. The results show that the distributed schemes have similar performance to the centralized ones, and among the distributed schemes, SR outperforms SP.

To provide satisfactory coverage is very important in many sensor network applications such as military surveillance. In order to obtain the required coverage in harsh environments, mobile sensors are helpful since they can move to cover the area not reachable by static sensors. Previous work on mobile sensor deployment is based on a round by round process, where sensors move iteratively until the maximum coverage is reached. Although these solutions can deploy mobile sensors in a distributed way, the mobile sensors may move in a zig-zag way and waste a lot of energy compared to moving directly to the final location. To address this problem, we propose a proxy-based sensor deployment protocol. Instead of moving iteratively, sensors calculate their target locations based on a distributed iterative algorithm, move logically, and exchange new logical locations with their new logical neighbors. Actual movement only occurs when sensors determine their final locations. Simulation results show that the proposed protocol can significantly reduce the energy consumption compared to previous work, while maintaining similar coverage.

Session-based Internet protocol (IP) applications, such as Internet telephony, are an important component of the emerging mobile Internet. The ubiquitous availability of these services is critical to the success of the mobile Internet. Because all-IP networks will be deployed in phases and current mobile telecommunication systems will be in operation for decades to come, the interworking and migration between current network services and all-IP services is a key problem. In this paper, we address seamless roaming for session initiation protocol-based services across current cellular telecommunication networks and emerging all-IP wireless networks, such as those using third-generation and WiFi networks. We present an abstract mobility model, and map this model to three basic approaches for supporting seamless mobility: a master-slave approach, a federated system, and a unified approach. We discuss the challenges and implementation of an instance of the unified mobility management approach, called the Unified Mobility Manager, and then compare the tradeoffs of the three systems using a comparative performance analysis. We conclude that unified mobility management is most efficient if a great deal of interworking is required, and as more users invoke IP-based services; the federated approach is efficient when a single network technology is dominant and data access is limited, but requires sharing of data across networks; the master-slave approach is the least efficient, but is easy to introduce if the number of network types is small.

In some harsh environments, manually deploying sensors is impossible. Alternative methods may lead to imprecise placement resulting in coverage holes. To provide the required high coverage in these situations, we propose to deploy sensor networks composed of a mixture of mobile and static sensors in which mobile sensors can move from dense areas to sparse areas to improve the overall coverage. This paper presents a bidding protocol to assist the movement of mobile sensors. In the protocol, static sensors detect coverage holes locally by using Voronoi diagrams, and bid for mobile sensors based on the size of the detected hole. Mobile sensors choose coverage holes to heal based on the bid. Simulation results show that our algorithm provides suitable tradeoff between coverage and sensor cost.

In current sensor networks, sensor nodes are capable of not only measuring real world phenomena, but also storing, processing and transferring these measurements. Many data dissemination techniques have been proposed for sensor networks. However, these techniques may not work well in a large scale sensor network where a huge amount of sensing data are generated, but only a small portion of them are queried. In this paper, we propose an index-based data dissemination scheme to address the problem. This scheme is based on the idea that sensing data are collected, processed and stored at the nodes close to the detecting nodes, and the location information of these storing nodes is pushed to some index nodes, which act as the rendezvous points for sinks and sources. We further extend the scheme with an adaptive ring-based index (ARI) technique, in which the index nodes for one event type form a ring surrounding the location which is determined by the event type, and the ring can be dynamically reconfigured for fault tolerance and load balance. Analysis and simulations are conducted to evaluate the performance of the proposed index-based scheme. The results show that the index-based scheme outperforms the external storage-based scheme, the DCS scheme, and the local storage-based schemes with flood-response style. The results also show that using ARI can tolerate clustering failures and achieve load balance.

The idea of true ubiquitous mobile computing, including anywhere, anytime access to a subscriber's data, computing environment, and communications network, has captured the imagination of service providers, equipment vendors, and researchers, as well as the Internet-savvy public. Mobile computing is a confluence of communication technologies (particularly the Internet), computing devices and their components, and access technologies such as wireless. A mobile computing environment will include not only real-time mobility of devices, but also mobility of people across devices. Therefore, the environment includes a wide range of devices, applications, and networks.

Mobile IP is the current standard for supporting macromobility of mobile hosts. However, in the case of micromobility support, there are several competing proposals. We present the design, implementation and performance evaluation of HAWAII (handoff-aware wireless access Internet infrastructure), a domain-based approach for supporting mobility. HAWAII uses specialized path setup schemes which install host-based forwarding entries in specific routers to support intra-domain micromobility. These path setup schemes deliver excellent performance by reducing mobility related disruption to user applications. Also, mobile hosts retain their network address while moving within the domain, simplifying quality-of-service (QoS) support. Furthermore, reliability is achieved through maintaining soft-state forwarding entries for the mobile hosts and leveraging fault detection mechanisms built in existing intra-domain routing protocols. HAWAII defaults to using Mobile IP for macromobility, thus providing a comprehensive solution for mobility support in wide-area wireless networks.

Telecommunication switches implement overload controls to maintain call throughput and delay at acceptable levels during periods of high load. Existing work has mostly focused on controls under sustained overload-they do not meet the demands of modern telecommunication systems where the increased number of services and mobile subscribers often creates fast changing hot spots. We introduce new algorithms that are designed to be highly reactive to sudden bursts of load. One algorithm is a modified version of RED for signaling traffic that measures the queue size. The second algorithm uses two measures: call acceptance rate and processor occupancy. Using simulations of realistic system models, we compare these new algorithms with each other and an existing algorithm that uses processor occupancy only. Our simulation results and qualitative arguments show that the combination of acceptance rate and processor occupancy results in a highly reactive and robust signaling overload control.

In wireless networks, mobile hosts must update the network with their current location in order to get packets delivered. Paging facilitates efficient power management at the mobile host by allowing the host to update the networkless frequently at the cost of providing the network with only approximate location information. The network determines the exact location of a mobile host through paging before delivering packets destined to the mobile host. In this paper, we propose the concept of paging as an IP service. IP paging enables a common infrastructure and protocol to support the different wireless interfaces such as CDMA, GPRS, wireless LAN, avoiding the duplication of several application layer paging implementations and the inter-operability issues that exists today. We present the design, implementation, and detailed qualitative and quantitative evaluation, using measurements and simulation, of three IP-based paging protocols for mobile hosts.

Next generation wireless networks will rely heavily on packet transport for both data and voice services. We describe the Router for Integrated Mobile Access (RIMA) system, which is the core network element of an integrated wireless packet network. RIMA acts as a mobile switching center for standard cellular telephony users, and a mobile router for wireless packet data users. RIMA includes a novel call processing system that supports several types of telephony services, and a new IP mobility protocol, called HAWAII, that efficiently manages the IP mobility of data and packet voice users. We discuss issues with providing wireless packet service, present a network architecture based on RIMA to address those issues, and describe a research prototype of the system.

Wireless networks often employ network-based user agents as proxies for mobile users. In this paper, we consider the fundamental problem of designing migration policies for these user agents. We first introduce a general framework for analyzing user agent migration policies, and then highlight, through analysis and simulation, the numerous parameters and tradeoffs that dictate the design of migration policies. We evaluate these policies in the context of both homogeneous and heterogeneous networks, and in the presence and absence of processing overheads due to migration. Finally, we identify two simple threshold-based policies that deliver very good performance over a wide range of system parameters and configurations. To our knowledge, this is the first paper to propose and evaluate policies for migration of user agents.

Mobile-IP is the current standard for supporting macro-mobility of mobile hosts. However, in the case of micro-mobility support, there are several competing proposals. In this paper we present the design, implementation, and performance evaluation of HAWAII: a domain-based approach for supporting mobility. HAWAII uses specialized path setup schemes which install host-based forwarding entries in specific routers to support intra-domain micro-mobility. These path setup schemes deliver excellent performance by reducing mobility related disruption to user applications. Also, mobile hosts retain their network address while moving within the domain, simplifying QoS support. Furthermore, reliability is achieved through maintaining soft-state forwarding entries for the mobile hosts and leveraging fault detection mechanisms built in existing intra-domain routing protocols. HAWAII defaults to using Mobile IP for macro-mobility, thus providing a comprehensive solution for mobility support in wide-area wireless networks.

In this paper we present techniques for allowing Mobile IP to interwork with wide area cellular networks. As an example, we illustrate a network consisting of a GSM general packet radio service (GPRS) air interface and a Mobile IP backbone network. The advantage of such a solution is that the backbone network may easily be used to support integrated wireless and wired data transfer, and the leveraging of standard data networking protocols and equipment will reduce the cost of wireless data networks. We present issues and suggested solutions for mobility management functions, such as detecting changes in points of attachment to a network, micromobility, roaming, and paging, and security functions, such as authentication and ciphering. We show which elements of each network, GSM and Mobile IP, may be re-used, combined, or eliminated to provide a single, unified network.

Multimedia wireless networks often employ network based user agents as proxies for mobile users. We consider a fundamental question in the design of these networks: should the user agents migrate and if so, what are good user agent migration policies? We first introduce a general framework for analysing user agent migration policies. We then highlight, through analysis and simulation, the numerous parameters and tradeoffs that dictate the design of migration policies. Finally, we identify two simple threshold-based policies that deliver very good performance over a wide range of system parameters and configurations.

Wireless two-way messaging is a new wireless data service that is rapidly gaining popularity. The basic service it provides is acknowledged exchange of short messages among subscribers or network-based servers. Like cellular/PCS systems, wireless two-way messaging systems are cellular in structure, and thus share the location management problem. We study the problem of location management for wireless two-way messaging. We first highlight the unique concerns of location management for wireless two-way messaging, and lay out its differences from cellular/PCS telephony. We then provide a new cost formulation for its study. Based on this formulation, we revisit existing schemes that have been proposed for cellular/PCS telephony to evaluate how they perform under wireless two-way messaging. We then introduce new classes of algorithms, called pending replies and deferred delivery, whose designs take advantage of the unique characteristics of wireless two-way messaging, and show through simulation, that they provide improved performance.

In this paper, we present the design and implementation of a software system that performs the control functions of current mobile switching centers (MSCs) and visitor location registers (VLRs), and provides support for third generation services. The novelty of the system design is in its software architecture. To allow flexible deployment of the system as the migration from second generation to third generation systems occurs, the software is modular. To provide scalability in terms of capacity, distributed processing is used. We show that a deployment of this system using three Sun Ultra workstations achieves a call throughput of 300,000 calls/hour with a latency of below 300 milliseconds. This meets the latency requirements of third generation systems.

Supporting mobility in asynchronous transfer mode (ATM)-based broad-band networks with wireless access links poses many technical challenges. One of the most important of these challenges is the need to reroute ongoing connections to/from mobile users as these users move among base stations. Connection rerouting schemes must exhibit low handoff latency, maintain efficient routes, and limit disruption to continuous media traffic while minimizing reroute updates to the network switches. In this paper we propose, describe an implementation for, and experimentally evaluate the performance of five different connection rerouting schemes. We show that one of these schemes, which operates in two phases, executes very fast reroutes (with a measured latency of 6.5 ms) in a real-time phase and, if necessary, reroutes again in a nonreal-time phase to maintain efficient routing. The scheme also results in negligible disruption to both audio (e.g., a 1-in-100 chance of a single packet loss at CD-quality audio rates of 128 kb/s) and low-bit-rate video (e.g., a 2-in-100 chance of a single packet loss for 1-Mb/s video) traffic during connection rerouting. Based on these results, we conclude that simple handoff schemes coupled with a connection management architecture are sufficient for supporting low-bit-rate continuous media applications over ATM-based wireless networks.

Wireless messaging, in the form of two-way paging, is an integral part of universal Personal Communications Services (PCS). Basic wireless messaging services include providing reliable (acknowledged) message delivery, reply capabilities, and message origination from a messaging device. Many more advanced services can also be envisioned. Wireless networks and end devices impose many limitations on system design. To overcome the problems caused by such an environment, we have introduced network based proxies, called user agents, to assist simple end devices, and a novel way to define messages, called flexible messages, so that advanced messaging services may be offered. In this paper, we describe how user agents and flexible messages assist in providing messaging services in the Pigeon two-way messaging research prototype at Bell Laboratories.

Wireless messaging is an integral component of universal personal communication services (PCSs). Its growth is likely to be further fueled by the availability of new data capabilities in the new PCS air interfaces. Our research focuses on high-level issues such as new messaging functionalities, high-layer protocols, and overall system design. Pigeon is our proposal of a wireless two-way messaging system. The novelty of our system lies in: (1) the techniques used in mitigating the wireless media and end device constraints, (2) the functionalities provided, and (3) its modular architecture. Examples of (1) include the use of asymmetric protocols and the introduction of user agents. Examples of (2) include group addressing, transaction support, and flexible messages. The modularity of Pigeon allows its individual components to be adopted by specific systems, A prototype of Pigeon has been implemented, and is operational at Bell Laboratories. We describe the motivation, design, and functionality of Pigeon. We also present, as an example, a mapping of Pigeon to a standard cellular/PCS messaging system.

In current telecommunication networks, the value-added services available to subscribers are almost exclusively offered by the carrier providing local telephony service. This results from two factors: the processing for services is either based in or triggered from software executing on the access telecommunication switches, and signaling links over which subscribers request services are terminated on these access switches. In a direct signaling system, the signaling link from a subscriber does not necessarily terminate on an access switch, but rather on an intelligent server we call a call server. The call server invokes service functions and coordinates their interactions. This direct signaling system may be overlaid on various types of access networks, including circuit-switched telephony, packet telephony, wireless local loop, cable, etc. We discuss the design, implementation, and performance of a direct signaling system, including procedures that provide varying amounts of integration with current telecommunication systems. Our results show that a direct signaling system using a low-delay direct signaling link and in which no changes are made to existing telecommunicatione switches incurs approximately 100 ms higher postdial delay than a standard ISDN system. A direct signaling system in which telecommunication switches provide open interfaces and coordinate processing with direct signaling servers incurs approximately 100 ms lower postdial delay than a standard ISDN system.

A new class of wireless messaging service, called two-way paging, is emerging. Current research on wireless messaging has mostly been concerned with low-level physical layer transmission issues, e.g., modulation and access. Few efforts have addressed high-level issues such as new messaging functionalities, high layer protocols, and overall system design. Most existing wireless messaging systems are built as monolithic entities in a centralized manner. We contend that the current designs lack flexibility required to meet the demand of next generation messaging needs. Pigeon is our proposal of a two-way messaging system. The novelty of our system lies in (1) the techniques used in mitigating the wireless media and end device constraints, (2) the functionalities provided, and (3) its modular architecture. Examples of (1) include the use of asymmetric protocols and the introduction of user agents. Examples of (2) include group addressing, transaction support and flexible messages. The modularity of Pigeon is especially important when it is mapped onto a specific platform, in which case the components of Pigeon, as opposed to the system as is, may be individually adopted. A prototype of Pigeon has been implemented and is operational at Bell Laboratories. We describe the design of Pigeon. We pay particular attention to motivate its service and system concepts. We also present, as an example, a mapping of Pigeon to cellular messaging.

We present a comparison of the control signaling load of two vastly different architectures for providing personal communication services (PCSs). One architecture is based on current cellular networks. The other architecture, called the wireless distributed call processing architecture (WDCPA), distributes processing from the mobile switching centers and cell sites and executes new procedures for tracking mobile users and locating mobile users to deliver calls. We determine the signaling load generated within each system to support mobility management and call control based on standard assumptions about the operating parameters of a cellular network. Our results show that, when compared to current cellular systems, for simple single-connection services, WDCPA has marginally reduced cross-network signaling loads. For multiconnection calls, WDCPA incurs 35% less total signaling load for mobility management, has reduced cross-network signaling load for mobility management by up to 65%, and depending on the user model (e.g., data or telecommunication), has reduced total cross-network signaling load, including procedures for call/connection and mobility management, by up to 55% when compared to current cellular systems, while more flexibly supporting services.

The performance of the multistream protocol (MSP), a feature-rich flexible transport designed to meet the needs of high-performance applications, is analyzed. The analysis is based on the processing complexity associated with performing certain protocol functions and it highlights the advantages and disadvantages of the implementation of several different protocol mechanisms, such as packet or block mode data transfer. The analysis shows that, if 10-MIPS processors are used to implement the protocol in a parallel architecture and block mode transmission is used, MSP may transfer data at a rate of over 150 Kpackets/s with a block size of 50 packets.>

A transport layer protocol designed to meet the wide-ranging needs of high-speed applications is described. A unique feature of this protocol is that its behavior, defined by a set of functions, may be modified dynamically over the life of a connection without loss of reliable data transfer. This property makes the protocol attractive for supporting applications, such as multimedia applications that require different protocol support for different portions of their traffic streams. The protocol has been verified to reliably deliver data and manage connections and to contain no deadlocks or loops. A parallel architecture for implementing the protocol has also been verified. Analysis of a skeleton implementation shows that the protocol has the potential to receive data at a rate of over 150 kpackets/s if 10-MIPS processors are used in the implementation.>

A performance analysis of the MultiStream Protocol (MSP), a feature-rich flexible transport protocol designed to meet the needs of high-performance applications, is presented. The analysis presents the advantages and disadvantages of the implementation of several different protocol mechanisms, such as packet or block mode data transfer. It is based on the processing complexity associated with executing each protocol function. Results show that a feature-rich transport protocol can be implemented in which the protocol control processing overhead is not prohibitive to providing high performance to an application. Instead, the benefits of a lean protocol are achieved because the protocol services better fit application requirements. Also, the primary bottleneck for data transfer is shown to be the complexity associated with error control, which can reduced through the technique of transmitting packets in blocks.>