waashk/dblp huggingface dataset:
on the absence of isolated nodes in wireless ad-hoc networks with unreliable links - a curious gap. we consider an extension to the disk model in one dimension where communication links established between nodes may fail. with the help of the method of first and second moments, we investigate the zero-one laws for the property that there are no isolated nodes in the underlying random graph. two specific situations are discussed: for the unit circle we prove a full zero-one law and determine its critical scaling. for the unit interval we derive a zero-law and a one-law which capture deviations from different critical scalings; a completely symmetric zero-one law is established under an additional condition. analysis and simulations both indicate the possible presence of a gap between the one-law critical scalings for the unit interval and the unit circle. this discrepancy is quite surprising given that the zeroone laws for the absence of isolated nodes are identical in the geometric random graphs on the unit interval and on the unit circle. connections to recent results by yi et al. are discussed.
wormhole-resilient secure neighbor discovery in underwater acoustic networks. neighbor discovery is a fundamental requirement and need be done frequently in underwater acoustic networks (uans) with floating node mobility. in hostile environments, neighbor discovery is vulnerable to the wormhole attack by which the adversary uses secret wormhole links to make distant nodes falsely accept each other as a neighbor. the wormhole attack may lead to many undesirable consequences and cannot be solved by cryptographic methods. existing wormhole defenses for ground wireless networks cannot be directly applied to uans where most of their assumptions no longer hold. this paper presents a suite of novel protocols to enable wormhole-resilient secure neighbor discovery in uans. our protocols are based on the direction of arrival (doa) estimation of acoustic signals, a basic functionality readily available in current uans. the proposed protocols can thwart the wormhole attack with overwhelming probability without conventional hard requirements on secure and accurate time synchronization and localization. detailed theoretical analysis and simulation results confirm the high performance of the proposed protocols.
measurement data reduction through variation rate metering. we present an efficient network measurement primitive that measures the rate of variations, or unique values for a given characteristic of a traffic flow. the primitive is widely applicable to a variety of data reduction and pre-analysis tasks at the measurement interface, and we show it to be particularly useful for building data-reducing preanalysis stages for scan detection within a multistage network analysis architecture. the presented approach is based upon data structures derived from bloom filters, and as such yields high performance with probabilistic accuracy and controllable worst-case time and memory complexity. this predictability makes it suitable for hardware implementation in dedicated network measurement devices. one key innovation of the present work is that it is self-tuning, adapting to the characteristics of the measured traffic.
bgp skeleton - an alternative to ibgp route reflection. the internet is a composition of ases (autonomous systems), bgp (border gateway protocol) is the routing protocol that is responsible of exchanging routes between these ases. it operates in two modes: external bgp (ebgp) and internal bgp (ibgp). ebgp exchanges routing information between ases, while ibgp propagates that information within the as. bgp full mesh solution (fms) is based on that all the asbrs (autonomous system border routers) should be fully meshed and each internal node should have an ibgp session with all of them. this was because an ibgp node does not have the ability to reflect routes. bgp route reflection was widely employed as an alternative to full mesh to reduce the needed number of ibgp sessions and, in turn, increase the scalability inside the as. under particular configuration, it introduces persistent route oscillation, forwarding loops, and non-optimal egress nodes. skeleton is an alternative to route reflection that overcomes these routing anomalies. skeleton is a subgraph of the physical graph with the same set of nodes, its edges are the ibgp sessions between the nodes. all skeleton nodes have the ability of reflecting routes. skeleton eliminates the use of clusters and establishes ibgp sessions only between single hop neighbors. we prove that it holds the sufficient correctness conditions as well as its robustness against med induced oscillations. we evaluate it on five real world topologies and find that the number of ibgp sessions has a linear relationship with the number of asbrs, where in fms this relationship is quadratic.
overhearing-aware joint routing and rate selection in multi-hop multi-rate uwb-based wpans. ultra-wideband (uwb) communications has emerged as a promising technology for high data rate wireless personal area networks (wpans). in this paper, we address a key issue that impacts the performance of multi-hop, multi-rate uwb-based wpans, namely joint routing and rate selection. arbitrary selection of routes (including direct links) and transmission rates along these routes results in unnecessarily long channel reservation time and high blocking rate for prospective reservations, and leads to low network throughput. to remedy this situation, we propose a novel overhearing-aware joint routing and rate selection (orrs) scheme, which improves the network throughput by exploiting the dependence between the channel reservation time and the multi-rate capability of an uwb system. at the same time, orrs takes advantage of packet overhearing, a typical characteristic of broadcast communications. for a given source-destination pair, orrs aims at selecting a path and its transmission rates that achieve the minimum reservation time, leading to low blocking rate for prospective reservations and high network throughput. we show that achieving this goal while simultaneously exploiting packet overhearing and satisfying a target packet delivery probability over the selected route leads to an np-hard problem. accordingly, orrs resorts to approximate solutions (proactive and reactive) to find a near-optimal result with reasonable computational/communication overhead. we further propose other variants that exploit packet overhearing in different ways to improve orrs performance.
arbor: hang together rather than hang separately in 802.11 wifi networks. with 802.11 wifi networks becoming popular in homes, it is common for an end-user to have access to multiple wifi access points (aps) from residents next door. in general, wireless networks have much higher bandwidth than residential internet (dsl or cable) connections. this provides an incentive for an end-user to simultaneously harness bandwidths from multiple aps. this paper introduces arbor, an 802.11 driver that aggregates broadband connections in a neighborhood and maximizes internet access bandwidth in a secure manner. arbor has four important characteristics. first, arbor can sustain a much longer switching cycle without losing packets queued at different aps. second, it can schedule traffic loads and (in)directly aggregate ap backhaul bandwidths. third, arbor designs and implements a light-weight authentication mechanism that provides sufficient amount of security, and at the same time, ensures fast switching time. finally, arbor is transparent to the upper layers of the network stack. a prototype of arbor has been implemented and extensively evaluated. experiment results show that arbor provides significantly better throughput gains and lower internet access delays.
efficient continuous scanning in rfid systems. rfid is an emerging technology with many potential applications such as inventory management for supply chain. in practice, these applications often need a series of continuous scanning operations to accomplish a task. for example, if one wants to scan all the products with rfid tags in a large warehouse, given a limited reading range of an rfid reader, multiple scanning operations have to be launched at different locations to cover the whole warehouse. usually, this series of scanning operations are not completely independent as some rfid tags can be read by multiple processes. simply scanning all the tags in the reading range during each process is inefficient because it collects a lot of redundant data and consumes a long time. in this paper, we develop efficient schemes for continuous scanning operations defined in both spatial and temporal domains. our basic idea is to fully utilize the information gathered in the previous scanning operations to reduce the scanning time of the succeeding ones. we illustrate in the evaluation that our algorithms dramatically reduce the total scanning time when compared with other solutions.
delay-based network utility maximization. it is well known that max-weight policies based on a queue backlog index can be used to stabilize stochastic networks, and that similar stability results hold if a delay index is used. using lyapunov optimization, we extend this analysis to design a utility maximizing algorithm that uses explicit delay information from the head-of-line packet at each user. the resulting policy is shown to ensure deterministic worst-case delay guarantees, and to yield a throughput-utility that differs from the optimally fair value by an amount that is inversely proportional to the delay guarantee. our results hold for a general class of 1-hop networks, including packet switches and multi-user wireless systems with time varying reliability.
on order gain of backoff misbehaving nodes in csma/ca-based wireless networks. backoff misbehavior, in which a wireless node deliberately manipulates its backoff time, can induce significant network problems, such as severe unfairness and denial-ofservice. although great progress has been made towards the design of countermeasures to backoff misbehavior, little attention has been focused on quantifying the gain of backoff misbehaviors. in this paper, we define and study two general classes of backoff misbehavior to assess the gain that misbehaving nodes can obtain. the first class, called continuous misbehavior, keeps manipulating the backoff time unless it is disabled by countermeasures. the second class is referred to as intermittent misbehavior, which tends to evade the detection by countermeasures by performing misbehavior sporadically. our approach is to introduce a new performance metric, namely order gain, which is to characterize the performance benefits of misbehaving nodes in comparison to legitimate nodes. through analytical studies, simulations, and experiments, we demonstrate the impact of a wide range of backoff misbehaviors on network performance with respect to the number of users in csma/ca-based wireless networks.
asymmetry-aware real-time distributed joint resource allocation in ieee 802.22 wrans. in ieee 802.22 wireless regional area networks (wrans), each base station (bs) solves a complex resource allocation problem of simultaneously determining the channel to reuse, power for adaptive coverage, and consumer premise equipments (cpes) to associate with, while maximizing the total downstream capacity of cpes. although joint power and channel allocation is a classical problem, resource allocation in wrans faces two unique challenges that has not yet been addressed: (1) the presence of small-scale incumbents such as wireless microphones (wms), and (2) asymmetric interference patterns between bss using omnidirectional antennas and cpes using directional antennas. in this paper, we capture this asymmetry in upstream/downstream communications to propose an accurate and realistic wran-wm coexistence model that increases spatial reuse of tv spectrum while protecting small-scale incumbents. based on the proposed model, we formulate the resource-allocation problem as a mixed-integer nonlinear programming (minlp) which is np-hard. to solve the problem in real-time, we propose a suboptimal algorithm based on the genetic algorithm (ga), and extend the basic ga algorithm to a fully-distributed ga algorithm (dga) that distributes computational cost over the network and achieves scalability via local cooperation between neighboring bss. using extensive simulation, the proposed dga is shown to perform as good as 99.4-99.8% of the optimal solution, while reducing the computational cost significantly.
multihop transmission opportunity in wireless multihop networks. wireless multihop communication is becoming more important due to the increasing popularity of wireless sensor networks, wireless mesh networks, and mobile social networks. they are distinguished from conventional multihop networks in terms of scale, traffic intensity and/or node density. being readily-available in most of 802.11 radios, multirate facility appears to be useful to address some of these issues and is particularly helpful in high-density scenarios where inter-node distance is short, demanding a prudent multirate adaptation algorithm. however, communication at high bit rates mandates a large number of hops for a given node pair and thus, can easily be depreciated as per-hop overhead at several layers of network protocol is aggregated over the increased number of hops. this paper presents a novel multihop, multirate adaptation mechanism, called multihop transmission opportunity (mtop), that allows a frame to be forwarded a number of hops consecutively but reduces the mac-layer overhead between hops. this seemingly collision-prone multihop forwarding is proven to be safe via analysis and usrp/gnu radio-based experiment. the idea of mtop is in clear contrast to, but not mutually exclusive with, the conventional opportunistic transmission mechanism, referred to as txop, where a node transmits multiple frames back-to-back when it gets an opportunity. we conducted an extensive simulation study via ns-2, demonstrating the performance advantage of mtop under a wide range of network scenarios.
on distributed time-dependent shortest paths over duty-cycled wireless sensor networks. we revisit the shortest path problem in asynchronous duty-cycled wireless sensor networks, which exhibit time-dependent features. we model the time-varying link cost and distance from each node to the sink as periodic functions. we show that the time-cost function satisfies the fifo property, which makes the time-dependent shortest path problem solvable in polynomial-time. using the β-synchronizer, we propose a fast distributed algorithm to build all-to-one shortest paths with polynomial message complexity and time complexity. the algorithm determines the shortest paths for all discrete times with a single execution, in contrast with multiple executions needed by previous solutions. we further propose an efficient distributed algorithm for time-dependent shortest path maintenance. the proposed algorithm is loop-free with low message complexity and low space complexity of o(maxdeg), where maxdeg is the maximum degree for all nodes. the performance of our solution is evaluated under diverse network configurations. the results suggest that our algorithm is more efficient than previous solutions in terms of message complexity and space complexity.
markov approximation for combinatorial network optimization. many important network design problems can be formulated as a combinatorial optimization problem. a large number of such problems, however, cannot readily be tackled by distributed algorithms. the markov approximation framework studied in this paper is a general technique for synthesizing distributed algorithms. we show that when using the log-sum-exp function to approximate the optimal value of any combinatorial problem, we end up with a solution that can be interpreted as the stationary probability distribution of a class of timereversible markov chains. certain carefully designed markov chains among this class yield distributed algorithms that solve the log-sum-exp approximated combinatorial network optimization problem. by three case studies, we illustrate that markov approximation technique not only can provide fresh perspective to existing distributed solutions, but also can help us generate new distributed algorithms in various domains with provable performance. we believe the markov approximation framework will find applications in many network optimization problems, and this paper serves as a call for participation.
approximate models for general cache networks. many systems employ caches to improve performance. while isolated caches have been studied in-depth, multicache systems are not well understood, especially in networks with arbitrary topologies. in order to gain insight into and manage these systems, a low-complexity algorithm for approximating their behavior is required. we propose a new algorithm, termed a-net, that approximates the behavior of multi-cache networks by leveraging existing approximation algorithms for isolated lru caches. we demonstrate the utility of a-net using both per-cache and network-wide performance measures.we also perform factor analysis of the approximation error to identify system parameters that determine the precision of a-net.
on the impact of mobility on multicast capacity of wireless networks. analogous to the beneficial impact that mobility has on the throughput of unicast networks, this paper establishes that mobility can provide a similar gain in the order-wise growth-rate of the throughput for multicast networks. this paper considers an all-mobile multicast network, and characterizes its multicast capacity scaling. the scaling result shows that the growth-rate of the throughput in the all-mobile multicast network is order-wise higher compared to the all-static multicast network. further, the paper considers a static-mobile hybrid multicast network, and establishes that, if there are sufficient number of mobile nodes (that is order-wise smaller than the total number of nodes) in the network, then mobile nodes can enhance the order behavior of the multicast throughput.
recognizing exponential inter-contact time in vanets. inter-contact time between moving vehicles is one of the key metrics in vehicular ad hoc networks (vanets) and central to forwarding algorithms and the end-to-end delay. due to prohibitive costs, little work has conducted experimental study on inter-contact time in urban vehicular environments. in this paper, we carry out an extensive experiment involving thousands of operational taxies in shanghai city. studying the taxi trace data on the frequency and duration of transfer opportunities between taxies, we observe that the tail distribution of the inter-contact time, that is the time gap separating two contacts of the same pair of taxies, exhibits a light tail such as one of an exponential distribution, over a large range of timescale. this observation is in sharp contrast to recent empirical data studies based on human mobility, in which the distribution of the inter-contact time obeys a power law. by performing a least squares fit, we establish an exponential model that can accurately depict the tail behavior of the inter-contact time in vanets. our results thus provide fundamental guidelines on design of new vehicular mobility models in urban scenarios, new data forwarding protocols and their performance analysis.
on computing compression trees for data collection in wireless sensor networks. we address the problem of efficiently gathering correlated data from a wireless sensor network, with the aim of designing algorithms with provable optimality guarantees, and understanding how close we can get to the known theoretical lower bounds. our proposed approach is based on finding an optimal or a near-optimal compression tree for a given sensor network: a compression tree is a directed tree over the sensor network nodes such that the value of a node is compressed using the value of its parent. we focus on broadcast communication model in this paper, but our results are more generally applicable to a unicast communication model as well. we draw connections between the data collection problem and a previously studied graph concept called weakly connected dominating sets, and we use this to develop novel approximation algorithms for the problem. we present comparative results on several synthetic and real-world datasets showing that our algorithms construct near-optimal compression trees that yield a significant reduction in the data collection cost.
an optimal key distribution scheme for secure multicast group communication. many ip multicast-based applications, such as multimedia conferencing, multiplayer games, require controlling the group memberships of senders and receivers. one common solution is to encrypt the data with a session key shared with all authorized senders/receivers. to efficiently update the session key in the event of member removal, many rooted-tree based group key distribution schemes have been proposed. however, most of the existing rooted-tree based schemes are not optimal. in other words, given the o(logn) storage overhead, the communication overhead is not minimized. on the other hand, although flat table scheme [1] achieves optimality [2], it is rather dismissed due to the vulnerability to collusion attacks. in this paper, we propose a key distribution scheme - egk that attains the same optimality as flat table without collusion vulnerability. additionally, egk provides constant message size and requires o(logn) storage overhead at the group controller, which makes egk suitable for applications containing a large number of multicasting group members. moreover, adding members in egk requires just one multicasting message. egk is the first work with such features and out-performs all existing schemes.
opportunistic routing with congestion diversity in wireless multi-hop networks. this paper considers the problem of routing packets across a multi-hop network consisting of multiple sources of traffic and wireless links with stochastic reliability while ensuring bounded expected delay. each packet transmission can be overheard by a random subset of receiver nodes among which the next relay is selected opportunistically. the main challenge in the design of minimum-delay routing policies is balancing the trade-off between routing the packets along the shortest paths to the destination and distributing traffic across the network. opportunistic variants of shortest path routing may, under heavy traffic scenarios, result in severe congestion and unbounded delay. while the opportunistic variants of backpressure, which ensure a bounded expected delay, are known to exhibit poor delay performance at low to medium traffic conditions. combining important aspects of shortest path routing with those of backpressure routing, this paper provides an opportunistic routing policy with congestion diversity (orcd). orcd uses a measure of draining time to opportunistically identify and route packets along the paths with an expected low overall congestion. previously, orcd was proved to ensure a bounded expected delay for all networks and under any admissible traffic (without any knowledge of traffic statistics). this paper proposes practical implementations and discusses criticality of various aspects of the algorithm. furthermore, the expected delay encountered by the packets in the network under orcd is compared against known existing routing policies via simulations where substantial improvements are observed.