waashk/dblp huggingface dataset:
estimating link reliability in wireless networks: an empirical study and interference modeling. recently, it has been received in the community that the link reliability is strongly related to rssi (or sinr) and the external interference makes it unpredictable, but the unpredictability has not been fully explained yet. in order to examine the causes of the unpredictable link state, we first configured an empirical testbed, performed a measurement study, and observed that the link reliability actually depends on an intra-frame sinr distribution. we also discovered that a rssi (or sinr) value is not always a good indicator to estimate the link state. based on these results, we propose a modeling framework for estimating the link state in the presence of the wireless interference. we vision that the framework can be used for developing link-aware protocols to achieve their optimal performance in a hostile wireless environment.
routing for energy minimization in the speed scaling model. we study network optimization that considers energy minimization as an objective. studies have shown that mechanisms such as speed scaling can significantly reduce the power consumption of telecommunication networks by matching the consumption of each network element to the amount of processing required for its carried traffic. most existing research on speed scaling focuses on a single network element in isolation. we aim for a network-wide optimization. specifically, we study a routing problem with the objective of provisioning guaranteed speed/bandwidth for a given demand matrix while minimizing energy consumption. optimizing the routes critically relies on the characteristic of the energy curve f(s), which is how energy is consumed as a function of the processing speed s. if f is superadditive, we show that there is no bounded approximation in general for integral routing, i.e., each traffic demand follows a single path. this contrasts with the well-known logarithmic approximation for subadditive functions. however, for common energy curves such as polynomials f(s) = µsα, we are able to show a constant approximation via a simple scheme of randomized rounding. the scenario is quite different when a non-zero startup cost σ appears in the energy curve, e.g. f(s) = {0 σ + µsα if s =0 if s > 0. for this case a constant approximation is no longer feasible. in fact, for any α > 1, we show an ω(log1/4 n hardness result under a common complexity assumption. (here n is the size of the network.) on the positive side we present o((σ/µ)1/α) and o(k) approximations, where k is the number of demands.
vbs: maximum lifetime sleep scheduling for wireless sensor networks using virtual backbones. wireless sensor network (wsn) applications require redundant sensors to guarantee fault tolerance. however, the same degree of redundancy is not necessary for multi-hop communication. in this paper, we present a new scheduling method called virtual backbone scheduling (vbs). vbs employs heterogeneous scheduling, where backbone nodes work with duty-cycling to preserve network connectivity, and nonbackbone nodes turn off radios to save energy. we formulate a maximum lifetime backbone scheduling (mlbs) problem to maximize the network lifetime using this scheduling model. because the mlbs problem is np-hard, two approximation solutions based on the schedule transition graph (stg) and virtual scheduling graph (vsg) are proposed. we also present an iterative local replacement (ilr) scheme as an distributed implementation of vbs. the path stretch problem is analyzed in order to explore the impact of vbs on the network structure. we show, through simulations, that vbs significantly prolongs the network lifetime under extensive conditions.
a frequency domain model to predict the estimation accuracy of packet sampling. in network measurement systems, packet sampling techniques are usually adopted to reduce the overall amount of data to collect and process. being based on a subset of packets, they hence introduce estimation errors that have to be properly counteracted by a fine tuning of the sampling strategy and sophisticated inversion methods. this problem has been deeply investigated in the literature with particular attention to the statistical properties of packet sampling and the recovery of the original network measurements. herein, we propose a novel approach to predict the energy of the sampling error on the real time traffic volume estimation, based on a spectral analysis in the frequency domain. we start by demonstrating that errors due to packet sampling can be modeled as an aliasing effect in the frequency domain. then, we exploit this theoretical finding to derive closed-form expressions for the signal-to-noise ratio (snr), able to predict the distortion of traffic volume estimates over time. the accuracy of the proposed snr metric is validated by means of real packet traces.
reliable wireless broadcasting with near-zero feedback. we examine the problem of minimizing feedbacks in reliable wireless broadcasting, by pairing rateless coding with extreme value theory. our key observation is that, in a broadcast environment, this problem resolves into estimating the maximum number of packets dropped among many receivers rather than for each individual receiver.with rateless codes, this estimation relates to the number of redundant transmissions needed at the source in order for all receivers to correctly decode a message with high probability. we develop and analyze two new data dissemination protocols, called random sampling (rs) and full sampling with limited feedback (fslf), based on the moment and maximum likelihood estimators in extreme value theory. both protocols rely on a single-round learning phase, requiring the transmission of a few feedback packets from a small subset of receivers. with fixed overhead, we show that fslf has the desirable property of becoming more accurate as the receivers's population gets larger. our protocols are channel agnostic, in that they do not require a-priori knowledge of (i.i.d.) packet loss probabilities, which may vary among receivers. we provide simulations and an improved full-scale implementation of the rateless deluge overthe-air programming protocol on sensor motes as a demonstration of the practical benefits of our protocols, which translate into about 30% latency and energy consumption savings.
joint random access and power selection for maximal throughput in wireless networks. in wireless networks, how to select transmit power that maximizes throughput is a challenging problem. on one hand, transmissions at a high power level could increase interference to others; on the other hand, transmissions at a low power level are prone to being interfered by others. prior works consider this problem as a search for a fixed optimal power setting that maximizes communication spatial reuse. in this paper, we pursue a novel approach that combines power selection with a random medium access mechanism. for each transmission, a node randomly selects a transmit power from all available power levels to access the medium. in this way, all combinations of network power settings could be selected with some probability. using a recently developed markov chain model, we derive a distributed scheme that determines the access probabilities of each power setting, according to the arrival rate of traffic and the service rate achieved by the scheme. we show that this scheme always converges to the optimal solution. moreover, we also show that the random scheme can attain the maximal throughput region that can be obtained by any time-sharing between power settings, and which is consequently larger than the region any fixed power setting can achieve.
towards automatic creation of usable security configuration. the objective of this work is to create usable security architecture that will minimize network risk while considering usability and budget. we propose and formulate a novel framework for automatic creation of network security architecture including configuration rules and device placements in order to minimize risk while satisfying the business requirements, service usability and budget constraints. our framework also automates the creation of external and internal demilitarized zones (dmz) to improve security by increasing isolation. we formalize this as an optimization problem and show that it is np-hard. we then provide heuristic approximation algorithms. the implemented systems, called secbuilder, were evaluated under different network sizes, topologies and security requirements. our evaluation study shows that the results obtained by secbuilder are close to the theoretical lower bound and the performance is scalable with the network size.
compressive sensing based positioning using rss of wlan access points. the sparse nature of location finding problem makes the theory of compressive sensing desirable for indoor positioning in wireless local area networks (wlans). in this paper, we address the received signal strength (rss)-based localization problem in wlans using the theory of compressive sensing (cs), which offers accurate recovery of sparse signals from a small number of measurements by solving an l1-minimization problem. a pre-processing procedure of orthogonalization is used to induce incoherence needed in the cs theory. in order to mitigate the effects of rss variations due to channel impediments, the proposed positioning system consists of two steps: coarse localization by exploiting affinity propagation, and fine localization by the cs theory. in the fine localization stage, access point selection problem is studied to further increase the accuracy. we implement the positioning system on a wifi-integrated mobile device (hp ipaq hx4700 with windows mobile 2003 pocket pc) to evaluate the performance. experimental results indicate that the proposed system leads to substantial improvements on localization accuracy and complexity over the widely used traditional fingerprinting methods.
a theoretical framework for hierarchical routing games. most theoretical research on routing games in telecommunication networks has so far dealt with reciprocal congestion effects between routed entities. yet in networks that support differentiation between flows, the congestion experienced by a packet depends on its priority level. another differentiation is made by compressing the packets in the low priority flow while leaving the high priority flow intact. in this paper we study such kind of routing scenarios for the case of non-atomic users and we establish conditions for the existence and uniqueness of equilibrium.
path stitching: internet-wide path and delay estimation from existing measurements. many measurement systems have been proposed in recent years to shed light on the internal performance of the internet. their common goal is to allow distributed applications to improve end-user experience. a common hurdle they face is the need to deploy yet another measurement infrastructure. in this work, we demonstrate that without any new measurement infrastructure or active probing we obtain composite performance estimates from as-by-as segments and the estimates are as good as (or even better than) those from existing estimation methodologies that use on-demand, customized active probing. the main contribution of this paper is an estimation algorithm that breaks down measurement data into segments, identifies relevant segments efficiently, and, by carefully stitching segments together, produces delay and path estimates between any two end points. fittingly, we call our algorithm path stitching. our results show remarkably good accuracy: error in delay is below 20 ms in 80% of end-to-end paths.
opportunistic spectrum access with multiple users: learning under competition. the problem of cooperative allocation among multiple secondary users to maximize cognitive system throughput is considered. the channel availability statistics are initially unknown to the secondary users and are learnt via sensing samples. two distributed learning and allocation schemes which maximize the cognitive system throughput or equivalently minimize the total regret in distributed learning and allocation are proposed. the first scheme assumes minimal prior information in terms of pre-allocated ranks for secondary users while the second scheme is fully distributed and assumes no such prior information. the two schemes have sum regret which is provably logarithmic in the number of sensing time slots. a lower bound is derived for any learning scheme which is asymptotically logarithmic in the number of slots. hence, our schemes achieve asymptotic order optimality in terms of regret in distributed learning and allocation.
learning to optimally exploit multi-channel diversity in wireless systems. consider a wireless system where a transmitter may send data to a set of receivers, or on various channels, experiencing random time-varying fading. the transmitter can send data to a single receiver or on a single channel at a time and may adapt its transmission power to the radio conditions of the chosen receiver/channel. its objective is to implement a strategy defining at each time how to select the receiver/channel and transmission power, so as to maximize its throughput, i.e., its average sending rate, under an average power constraint. the optimization problem is easy when the fading conditions of all the receivers/channels are known. in many situations however, the instantaneous fading conditions are not known a priori, instead they have to be acquired, i.e., receivers/channels have to be probed, which consumes resources (time, spectrum, energy) in proportion of the number of probed receivers/channels. hence, the transmitter may choose not to acquire the radio conditions of all the receivers/channels so as to spare resources for actual transmissions. in this paper, we aim at characterizing a joint probing, receiver/channel selection and power control strategy maximizing throughput. we provide an adaptive algorithm converging to the throughput optimal strategy. this algorithm may be used in a wide class of wireless systems with limited information, such as broadcast systems without a priori knowledge of the instantaneous channel-state information (csi). but it can be also used to solve dynamic spectrum access problems such as those arising in cognitive radio systems, where secondary users can access large parts of the spectrum, but have to discover which portions of the spectrum offer more favorable radio conditions or less interference from primary users.
dynamic power allocation under arbitrary varying channels - the multi-user case. we consider the power control problem in a time-slotted wireless channel, shared by a finite number of mobiles that transmit to a common base station. the channel between each mobile and the base station is time varying, and the system objective is to maximize the overall data throughput. it is assumed that each transmitter has a limited power budget, to be sequentially divided during the lifetime of the battery. we deviate from the classic work in this area, by considering a realistic scenario where the channel quality of each mobile changes arbitrarily from one transmission to the other. assuming first that each mobile is aware of the channel quality of all other mobiles, we propose an online power-allocation algorithm, and prove its optimality under mild assumptions. we then indicate how to implement the algorithm when only local state information is available, requiring minimal communication overhead. notably, the competitive ratio of our algorithm (nearly) matches the bound obtained for the (much simpler) single-transmitter case [2], albeit requiring significantly different algorithmic solutions.
maximum damage malware attack in mobile wireless networks. malware attacks constitute a serious security risk that threatens to slow down the large scale proliferation of wireless applications. as a first step towards thwarting this security threat, we seek to quantify the maximum damage inflicted on the system owing to such outbreaks and identify the most vicious attacks. we represent the propagation of malware in a battery-constrained mobile wireless network by an epidemic model in which the worm can dynamically control the rate at which it kills the infected node and also the transmission range and/or the media scanning rate. at each moment of time, the worm at each node faces the following trade-offs: (i) using larger transmission range and media scanning rate to accelerate its spread at the cost of exhausting the battery and thereby reducing the overall infection propagation rate in the long run or (ii) killing the node to inflict a large cost on the network, however at the expense of loosing the chance of infecting more susceptible nodes at later times. we mathematically formulate the decision problems and utilize pontryagin maximum principle from optimal control theory to quantify the damage that the malware can inflict on the network by deploying optimum decision rules. next, we establish structural properties of the optimal strategy of the attacker over time. specifically, we prove that it is optimal for the attacker to defer killing of the infective nodes in the propagation phase for a certain time and then start the slaughter with maximum effort. we also show that in the optimal attack policy, the battery resources are used according to a decreasing function of time, i.e., mostly during the initial phase of the outbreak. finally, our numerical investigations reveal a framework for identifying intelligent defense strategies that can limit the damage by appropriately selecting network parameters.
extending access point connectivity through opportunistic routing in vehicular networks. nowadays, the navigation systems available on cars are becoming more and more sophisticated. they greatly improve the experience of drivers and passengers by enabling them to receive map and traffic updates, news feeds, advertisements, media files, etc. unfortunately, the bandwidth available to each vehicle with the current technology is severely limited. there have been many reports on the inability of 3g networks to cope with large size file downloads, especially in dense and mobile settings. a possible alternative is provided by wifi access points (aps) that are being installed in several countries along the main routes and in popular areas. although this approach significantly increases the available bandwidth, it still does not provide a fully satisfactory solution due to the limited transmission range (usually a few hundred meters). in this paper we present a novel routing protocol, based on opportunistic vehicle to vehicle communication, to enable efficient multi-hop routing capabilities between mobile vehicles and aps. unlike prior work, this protocol fully supports twoway communication, i.e., the traditional vehicle-to-ap as well as the more challenging ap-to-vehicle. we leverage the information offered by the navigation system in terms of final destination and path, to i) route packets to the closest ap and ii) to route replies back to the moving vehicle efficiently.
on approximation of new optimization methods for assessing network vulnerability. assessing network vulnerability before potential disruptive events such as natural disasters or malicious attacks is vital for network planning and risk management. it enables us to seek and safeguard against most destructive scenarios in which the overall network connectivity falls dramatically. existing vulnerability assessments mainly focus on investigating the inhomogeneous properties of graph elements, node degree for example, however, these measures and the corresponding heuristic solutions can provide neither an accurate evaluation over general network topologies, nor performance guarantees to large scale networks. to this end, in this paper, we investigate a measure called pairwise connectivity and formulate this vulnerability assessment problem as a new graph-theoretical optimization problem called β-disruptor, which aims to discover the set of critical node/edges, whose removal results in the maximum decline of the global pairwise connectivity. our results consist of the np-completeness and inapproximability proof of this problem, an o(log n log log n) pseudo-approximation algorithm for detecting the set of critical nodes and an o(log1.5 n) pseudoapproximation algorithm for detecting the set of critical edges. in addition, we devise an efficient heuristic algorithm and validate the performance of the our model and algorithms through extensive simulations.
evaluating potential routing diversity for internet failure recovery. as the internet becomes a critical infrastructure component of our global information-based society, any interruption to its availability can have significant economical and societal impacts. although many researches tried to improve the resilience through the bgp policy-compliant paths, it has been demonstrated that the internet is still highly vulnerable when major failures happen. in this paper, we aim to overcome the inherent constraint of the existing bgp-compliant recovery schemes and propose to seek additional potential routing diversity by relaxing bgp peering links and through internet exchange points (ixps). the focus of this paper is to evaluate the potentiality of these two schemes, rather than on their implementations. by collecting most complete as link map up-to-date with 31k nodes and 142k links, we demonstrate that the proposed potential routing diversity can recover 40% to 80% of the disconnected paths on average beyond bgp-compliant paths. this work suggests a promising venue to address the internet failures.
sample path bounds for long memory fbm traffic. fractional brownian motion (fbm) emerged as a useful model for self-similar and long-range dependent internet traffic. asymptotic, respectively, approximate performance measures are known from large deviations theory for single queuing systems with fbm traffic. in this paper we prove a rigorous sample path envelope for fbm that complements previous results. we find that both approaches agree in their outcome that overflow probabilities for fbm traffic have a weibull tail. we show numerical results on the impact of the variability and the correlation of fbm traffic on the queuing performance.
energy-conserving scheduling in multi-hop wireless networks with time-varying channels. maxweight algorithm, a.k.a., back-pressure algorithm, has received much attention as a viable solution for dynamic link scheduling in multi-hop wireless networks. the basic principle of the maxweight algorithm is to select a set of interference-free links with the maximum overall link weights in the network, where the link weight is determined by the queue difference between the transmitter and the receiver. while the throughput-optimality of the maxweight algorithm is well understood in the literature, the energy consumption induced by the maxweight algorithm is less studied, which is of great interest in energy-constrained wireless networks such as wireless sensor networks. in this paper, we propose an energy-conserving scheduling scheme, a.k.a., minimum energy scheduling (mes) algorithm for multi-hop wireless networks with stochastic traffic arrivals and time-varying channel conditions. we show that our algorithm is energy optimal in the sense that the proposed mes algorithm can achieve an energy consumption which is arbitrarily close to the global minimum solution. moreover, the energy efficiency of the mes algorithm is achieved without losing the throughputoptimality. in other words, the proposed mes algorithm is still throughput optimal whereas the average consumed energy in the network is significantly reduced, as compared to the traditional maxweight algorithm. the theoretical results are substantiated via simulations.