waashk/dblp huggingface dataset:
towards mobile phone localization without war-driving. this paper identifies the possibility of using electronic compasses and accelerometers in mobile phones, as a simple and scalable method of localization without war-driving. the idea is not fundamentally different from ship or air navigation systems, known for centuries. nonetheless, directly applying the idea to human-scale environments is non-trivial. noisy phone sensors and complicated human movements present practical research challenges. we cope with these challenges by recording a person's walking patterns, and matching it against possible path signatures generated from a local electronic map. electronic maps enable greater coverage, while eliminating the reliance on wifi infrastructure and expensive war-driving. measurements on nokia phones and evaluation with real users confirm the anticipated benefits. results show a location accuracy of less than 11m in regions where today's localization services are unsatisfactory or unavailable.
overcoming failures: fault-tolerance and logical centralization in clean-slate network management. we investigate the design of a clean-slate control and management plane for data networks using the abstraction of 4d architecture, utilizing and extending 4d's concept of logically centralized decision plane that is responsible for managing network-wide resources. in this paper, a dynamically adaptable algorithm for assigning data plane devices to a physically distributed decision plane is presented, which enables a network to operate with minimal configuration and human intervention, while providing optimal convergence and robustness against failures. our work is especially relevant in the context of isps and large geographically dispersed enterprise networks, where robust and scalable network-wide control of a large number of heterogeneous devices is desired.
sparsetrack: enhancing indoor pedestrian tracking with sparse infrastructure support. accurate indoor pedestrian tracking has wide applications in the healthcare, retail, and entertainment industries. however, existing approaches to indoor tracking have various limitations. for example, location-fingerprinting approaches are labor-intensive and vulnerable to environmental changes. trilateration approaches require at least three line-of-sight (los) beacons to cover any point in the service area, which results in heavy infrastructure cost. dead reckoning (dr) approaches rely on knowledge of the initial user location and suffer from tracking error accumulation. despite this, we adopt dr for location tracking because of the recent emergence of affordable hand-held devices equipped with low cost dr-enabling sensors. in this paper, we propose an indoor pedestrian tracking system which comprises a dr sub-system implemented on a mobile phone, and a ranging sub-system with a sparse infrastructure. a probabilistic fusion scheme is applied to bound the accumulated tracking error of dr when new range measurements are available from sparsely deployed beacons. experimental results show that the proposed system is able to track users much better than dr alone, with reductions in average error by up to 71.9%. the system is robust and works well even when the initial user location is not available and range updates are intermittent. this highlights the potential of using sparse but reasonably accurate partial information to limit location tracking errors.
diffprobe: detecting isp service discrimination. we propose an active probing method, called differential probing or diffprobe, to detect whether an access isp is deploying forwarding mechanisms such as priority scheduling, variations of wfq, or wred to discriminate against some of its customer flows. diffprobe aims to detect if the isp is doing one or both of delay discrimination and loss discrimination. the basic idea in diffprobe is to compare the delays and packet losses experienced by two flows: an application flow a and a probing flow p. the paper describes the statistical methods that diffprobe uses, a novel method for distinguishing between strict priority and wfq-variant packet scheduling, simulation and emulation experiments, and a few real-world tests at major access isps.
price of anarchy in non-cooperative load balancing. we investigate the price of anarchy of a load balancing game with k dispatchers. the service rates and holding costs are assumed to depend on the server, and the service discipline is assumed to be processor-sharing at each server. the performance criterion is taken to be the weighted mean number of jobs in the system, or equivalently, the weighted mean sojourn time in the system. for this game, we first show that, for a fixed amount of total incoming traffic, the worst-case nash equilibrium occurs when each player routes exactly the same amount of traffic, i.e., when the game is symmetric. for this symmetric game, we provide the expression for the loads on the servers at the nash equilibrium. using this result we then show that, for a system with two or more servers, the price of anarchy, which is the worst-case ratio of the global cost of the nash equilibrium to the global cost of the centralized setting, is lower bounded by k/(2√k - 1) and upper bounded by √k, independently of the number of servers.
an axiomatic theory of fairness in network resource allocation. we present five axioms for fairness measures in resource allocation. a family of fairness measures satisfying the axioms is constructed. special cases of this family include a-fairness, jain's index, and entropy. properties of fairness measures satisfying the axioms are proven, including schurconcavity. among the engineering implications is a generalized jain's index that tunes the resolution of fairness measure, a new understanding of a-fair utility functions, and an interpretation of "larger a is more fair". we also construct an alternative set of axioms to capture system efficiency and feasibility constraints.
universal rigidity: towards accurate and efficient localization of wireless networks. a fundamental problem in wireless ad-hoc and sensor networks is that of determining the positions of nodes. often, such a problem is complicated by the presence of nodes whose positions cannot be uniquely determined. most existing work uses the notion of global rigidity from rigidity theory to address the non-uniqueness issue. however, such a notion is not entirely satisfactory, as it has been shown that even if a network localization instance is known to be globally rigid, the problem of determining the node positions is still intractable in general. in this paper, we propose to use the notion of universal rigidity to bridge such disconnect. although the notion of universal rigidity is more restrictive than that of global rigidity, it captures a large class of networks and is much more relevant to the efficient solvability of the network localization problem. specifically, we show that both the problem of deciding whether a given network localization instance is universally rigid and the problem of determining the node positions of a universally rigid instance can be solved efficiently using semidefinite programming (sdp). then, we give various constructions of universally rigid instances. in particular, we show that trilateration graphs are generically universally rigid, thus demonstrating not only the richness of the class of universally rigid instances, but also the fact that trilateration graphs possess much stronger geometric properties than previously known. finally, we apply our results to design a novel edge sparsification heuristic that can reduce the size of the input network while provably preserving its original localization properties. one of the applications of such heuristic is to speed up existing convex optimization-based localization algorithms. simulation results show that our speedup approach compares very favorably with existing ones, both in terms of accuracy and computation time.
a balanced consistency maintenance protocol for structured p2p systems. a fundamental challenge of managing mutable data replication in a peer-to-peer (p2p) system is efficiently maintaining consistency under various sharing patterns with heterogeneous resource capabilities. this paper presents a framework for balanced consistency maintenance (bcom) in structured p2p systems. replica nodes of each object are organized into a tree for disseminating updates, and a sliding window update protocol is developed to bound the consistency. the effect of window size in response to dynamic network conditions, workload updates and resource limits is analyzed through a queueing model. this enables us to balance availability, performance and consistency strictness for various application requirements. on top of the dissemination tree, two enhancements are proposed: a fast recovery scheme to strengthen the robustness against node and link failures; and a node migration policy to remove and prevent the bottleneck for better system performance. simulations are conducted using p2psim to evaluate bcom in comparison to scope [2]. the experimental results demonstrate that bcom significantly improves the availability of scope by lowering the discard rate from almost 100% to 5% with slight increase in latency.
delay analysis for cognitive radio networks with random access: a fluid queue view. we consider a cognitive radio network where multiple secondary users (sus) contend for spectrum usage, using random access, over available primary user (pu) channels. our focus is on sus' queueing delay performance, for which a systematic understanding is lacking. we take a fluid queue approximation approach to study the steady-state delay performance of sus, for cases with a single pu channel and multiple pu channels. using stochastic fluid models, we represent the queue dynamics as poisson driven stochastic differential equations, and characterize the moments of the sus' queue lengths accordingly. since in practical systems, a secondary user would have no knowledge of other users' activities, its contention probability has to be set based on local information. with this observation, we develop adaptive algorithms to find the optimal contention probability that minimizes the mean queue lengths. moreover, we study the impact of multiple channels and multiple interfaces, on sus' delay performance. as expected, the use of multiple channels and/or multiple interfaces leads to significant delay reduction.
an investigation on the nature of wireless scheduling. the paper studies the complexity of the wireless scheduling problem under interference constraints.we first relate the definition of the capacity region to the weighted fractional coloring problem. then, the scheduling-for-stability problem under deterministic arrivals is studied in light of this relationship. we emphasize the requirement that the scheduling algorithm uses a tractable amount of processing and storage resources. two classes of algorithms are defined and a complexity result is derived for the intersection of the two classes. we also exhibit an algorithm that can achieve the storage requirement by relaxing the processing requirement. the results are used to examine interesting sections of the capacity region. finally, we relate the new interpretation and theory about the capacity region to the notion of set σ-local pooling.
change management in enterprise it systems: process modeling and capacity-optimal scheduling. we provide a formal model for the change management process for enterprise it systems, and develop change scheduling algorithms that seek to attain the "change capacity" of the system. the change management process handles critical updates in the system that often use overlapping sets of servers, resulting in scheduling conflicts between the corresponding change classes. furthermore, applications are typically associated with certain permissible downtime windows, which impose constraints on the timing of the change executions. scheduling of changes for such systems represent a complex dynamic optimization question. in a limiting fluid regime, where changes are assumed nonatomic, we develop a scheduling policy that provably attains the change capacity of the system. we then propose and evaluate an atomic approximation of the optimal fluid scheduling policy, which is well suited for application to a real change management system. simulation results demonstrate that the expected change execution delay and the capacity attained by the approximate policy is close to the best attainable values, when unavoidable capacity losses due to fragmentation effects are taken into account and is significantly better than a randomized scheduling policy.
mobile sensor deployment in unknown fields. 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.
flow control for cost-efficient peer-to-peer streaming. in this paper we address the issue of network cost efficiency for live streaming peer-to-peer systems. we formalize this as an optimization problem, which features a generic cost function. the latter is appropriate to capture not only ispspecific link weights, but also non-linear, congestion-dependent costs. our main contribution is the introduction of the implicit-primal-dual scheme for flow control in live streaming peer-topeer systems. it is fully distributed in that it relies only on local state variable exchanges. moreover, we show that at a fluid scale, combined with random linear network coding, it admits the cost optimal operating point as a fixed point.we also prove asymptotic boundedness of fluid trajectories for particular cost functions.we finally show via experiments that these optimality properties are resilient to operational constraints such as finite generation size and finite field size.
spring: a social-based privacy-preserving packet forwarding protocol for vehicular delay tolerant networks. in this paper, we propose a social-based privacy-preserving packet forwarding protocol, called spring, for vehicular delay tolerant networks (dtns). with spring, roadside units (rsus) deployed along the roadside can assist in packet forwarding to achieve highly reliable transmissions. in specific, we first heuristically define how to evaluate each traffic intersection's social degree in a vehicular dtn. based on the social degree information, we then strategically place rsus at some high-social intersections. as a result, these rsus can provide tremendous assistance in temporarily storing packets and helping packet forwarding to achieve high delivery ratio. performance evaluations via extensive simulations demonstrate the spring's efficiency. in addition, detailed security analyses show that the proposed spring can achieve conditional privacy preservation and resist most attacks existing in vehicular dtns.
metrics for evaluating video streaming quality in lossy ieee 802.11 wireless networks. peak signal-to-noise ratio (psnr) is the simplest and the most widely used video quality evaluation methodology. however, traditional psnr calculations do not take the packet loss into account. this shortcoming, which is amplified in wireless networks, contributes to the inaccuracy in evaluating video streaming quality in wireless communications. such inaccuracy in psnr calculations adversely affects the development of video communications in wireless networks. this paper proposes a novel video quality evaluation methodology. as it not only considers the psnr of a video, but also with modificatioils to handle the packet loss issue, we name this evaluation method mpsnr. mpsnr rectifies the inaccuracies in traditional psnr computation, and helps us to approximate subjective video quality, mean opinion score (mos), more accurately. using psnr values calculated from mpsnr and simple network measurements, we apply linear regression techniques to derive two specific objective video quality metrics, psnr-based objective mos (pomos) and rates-based objective mos (romos). through extensive experiments and human subjective tests, we show that the two metrics demonstrate high correlation with mos. pomos takes the averaged psnr value of a video calculated from mpsnr as the only input. despite its simplicity, it has a pearson correlation of 0.8664 with the mos. by adding a few other simple network measurements, such as the proportion of distorted frames in a video, romos achieves an even higher pearson correlation (0.9350) with the mos. compared with the psnr metric from the traditional psnr calculations, our metrics evaluate video streaming quality in wireless networks with a much higher accuracy while retaining the simplicity of psnr calculation.
peoplerank: social opportunistic forwarding. in opportunistic networks, end-to-end paths between two communicating nodes are rarely available. in such situations, the nodes might still copy and forward messages to nodes that are more likely to meet the destination. the question is which forwarding algorithm offers the best trade off between cost (number of message replicas) and rate of successful message delivery. we address this challenge by developing the peoplerank approach in which nodes are ranked using a tunable weighted social information. similar to the pagerank idea, peoplerank gives higher weight to nodes if they are socially connected to other important nodes of the network. we develop centralized and distributed variants for the computation of peoplerank. we present an evaluation using real mobility traces of nodes and their social interactions to show that peoplerank manages to deliver messages with near optimal success rate (i.e., close to epidemic routing) while reducing the number of message retransmissions by 50% compared to epidemic routing.
optimal sinr-based random access. random access protocols, such as aloha, are commonly modeled in wireless ad-hoc networks by using the protocol model. however, it is well-known that the protocol model is not accurate and particularly it cannot account for aggregate interference from multiple interference sources. in this paper, we use the more accurate physical model, which is based on the signal-to-interference-plus-noise-ratio (sinr), to study optimization-based design in wireless random access systems, where the optimization variables are the transmission probabilities of the users. we focus on throughput maximization, fair resource allocation, and network utility maximization, and show that they entail non-convex optimization problems if the physical model is adopted. we propose two schemes to solve these problems. the first design is centralized and leads to the global optimal solution using a sum-of-squares technique. however, due to its complexity, this approach is only applicable to small-scale networks. the second design is distributed and leads to a close-to-optimal solution using the coordinate ascent method. this approach is applicable to medium-size and large-scale networks. based on various simulations, we show that it is highly preferable to use the physical model for optimization-based random access design. in this regard, even a sub-optimal design based on the physical model can achieve a significantly better performance than an optimal design based on the inaccurate protocol model.
a secondary market for spectrum. dynamic spectrum trading amongst small cognitive users is fundamentally different along two axes: temporal variation, and spatial variation of user demand and channel condition. we advocate that a spectrum secondary market, analogous to the stock market, is to be established for users to dynamically trade among themselves their channel holdings obtained in the primary market from legacy owners. we design a market mechanism based on dynamic double auctions, creating a marketplace in the air to match bandwidth demand with supply. in the analysis we prove important economic properties of the mechanism, notably its truthfulness and asymptotic efficiency in maximizing spectrum utilization. complimentary simulation studies corroborate that spectrum utilization and user performance can be improved by establishing the spectrum secondary market.
chameleon: adaptive peer-to-peer streaming with network coding. layered streaming can be used to adapt to the available download capacity of an end-user, and such adaptation is very much required in real world http media streaming. the multiple layer codec has become more refined, as svc (the scalable extension of the h.264/avc standard) has been standardized with a bit rate overhead of around 10% and an indistinguishable visual quality, compared to the state of the art single layer codec. peer-to-peer streaming systems have also become the reality. the important question is how such layered coding can be used in real world peer-to-peer streaming systems. this paper tries to explore the feasibility of using network coding to make layered peer-to-peer streaming much more realistic, by combining network coding and svc in a fine granularity manner. we present chameleon, our new peer-to-peer streaming algorithm designed to incorporate network coding seamlessly with svc. key components with different design options of chameleon are presented and experimentally evaluated, with the objective of investigating benefits of network coding in combination with svc. we carry out extensive experiments on real stream data to (i) evaluate the performance of chameleon in terms of playback skips and delivered video quality, and (ii) understand its insights. our results demonstrate the feasibility of the approach and bring us one step closer to real adaptive peer-to-peer streaming.
optimal solutions for single fault localization in two dimensional lattice networks. achieving fast, precise, and scalable fault localization has long been a highly desired feature in all-optical mesh networks. monitoring tree (m-tree) is an interesting method that has been introduced as the most general monitoring structure for achieving unambiguous failure localization (ufl). ideally, with j m-trees one can monitor up to 2j - 1 links when a single failure has to be located. such a logarithmic behavior has also been observed in numerous case studies of real life network topologies [1], [2]. it is expected that the m-tree framework will lead to a highly scalable link failure monitoring mechanism for not only all-optical mesh networks, but any possible future information system with mesh topologies, such as all-optical mesh networks, touch panels, quantum computing, and vlsi. it is an important task to investigate the extent such an optimal logarithmic behavior may hold, in particular in practically relevant network topologies. as an endeavor toward this goal, the paper investigates the problem by identifying essentially tight logarithmic bounds for two dimensional lattice networks. experiments are conducted to show the feasibility and performance of the proposed constructions.