waashk/dblp huggingface dataset:
distance estimation by constructing the virtual ruler in anisotropic sensor networks. distance estimation is fundamental for many functionalities of wireless sensor networks and has been studied intensively in recent years. a critical challenge in distance estimation is handling anisotropic problems in sensor networks. compared with isotropic networks, anisotropic networks are more intractable in that their properties vary according to the directions of measurement. anisotropic properties result from various factors, such as geographic shapes, irregular radio patterns, node densities, and impacts from obstacles. in this paper, we study the problem of measuring irregularity of sensor networks and evaluating its impact on distance estimation. in particular, we establish a new metric to measure irregularity along a path in sensor networks, and identify turning nodes where a considered path is inflected. furthermore, we develop an approach to construct a virtual ruler for distance estimation between any pair of sensor nodes. the construction of a virtual ruler is carried out according to distance measurements among beacon nodes. however, it does not require beacon nodes to be deployed uniformly throughout sensor networks. compared with existing methods, our approach neither assumes global knowledge of boundary recognition nor relies on uniform distribution of beacon nodes. therefore, this approach is robust and applicable in practical environments. simulation results show that our approach outperforms some previous methods, such as dvdistance and pdm.
efficient two-dimensional data allocation in ieee 802.16 ofdma. the ieee 802.16 standard uses orthogonal frequency division multiple access (ofdma) for mobility support. therefore, the medium access control frame extends in two dimensions, i.e., time and frequency. at the beginning of each frame, i.e., every 5 ms, the base station is responsible both for scheduling packets, based on the negotiated quality of service requirements, and for allocating them into the frame, according to the restrictions imposed by 802.16 ofdma. to break down the complexity, a split approach has been proposed in the literature, where the two tasks are solved in separate and subsequent stages. in this paper we focus on the allocation task alone, which is addressed in its full complexity, i.e., by considering that data within the frame must be allocated as bursts with rectangular shape, each consisting of a set of indivisible sub-bursts, and that a variable portion of the frame is reserved for in-band signaling. after proving that the resulting allocation problem is np-hard, we develop an efficient heuristic algorithm, called recursive tiles and stripes (rts), to solve it. rts, in addition to handle a more general problem, is shown to perform better than state-of-the-art solutions via numerical analysis with realistic system parametrization.
an optimization based distributed algorithm for mobile data gathering in wireless sensor networks. recent advances have shown a great potential of anchor based mobile data gathering in wireless sensor networks. in such a scheme, during each periodic data gathering tour, the mobile collector stays at each anchor point for a period of sojourn time and collects data from nearby sensors via multi-hop communications. we provide an optimization based distributed algorithm for such data gathering in this paper. we adopt network utility, which is a properly defined function, to characterize the data gathering performance, and formalize the problem as a network utility maximization problem under the constraint of guaranteed network lifetime. to efficiently solve the problem, we decompose it into two sets of subproblems and solve them in a distributed manner, which facilitates the scalable implementations. finally, we provide numerical results to demonstrate the convergence of the proposed distributed algorithm.
a node-failure-resilient anonymous communication protocol through commutative path hopping. with rising concerns on user privacy over the internet, anonymous communication systems that hide the identity of a participant from its partner or third parties are highly desired. existing approaches either rely on a relative small set of pre-selected relay servers to redirect the messages, or use structured peer-to-peer systems to multicast messages among a set of relay groups. the pre-selection approaches provide good anonymity, but suffer from node failures and scalability problem. the peer-to-peer approaches are subject to node churns and high maintenance overhead, which are the intrinsic problems of p2p systems. in this paper, we present cat, a node-failure-resilient anonymous communication protocol. in this protocol, relay servers are randomly assigned to relay groups. the initiator of a connection selects a set of relay groups instead of relay servers to set up anonymous paths. a valid path consists of relay servers, one from each selected relay group. the initiator explores valid anonymous paths via a probing process. since the relative positions of relay servers in the path are commutative, there exist multiple anonymous yet commutative paths, which form an anonymous tunnel. when a connection encounters a node failure, it quickly switches to a nearest backup path in the tunnel through "path hopping", without tampering the initiator or renegotiating the keys. hence, the protocol is resilient to node failures. we also show that the protocol provides good anonymity even when facing types of active and passive attacks. finally, the operating cost of cat is analyzed and shown to be similar to other node-based anonymous communication protocols.
on the viability of paris metro pricing for communication and service networks. paris metro pricing (pmp) is a simple multi-class flat-rate pricing scheme already practiced by transport systems, specifically by the paris metro at one time. the name is coined after andrew odlyzko proposed it for the internet as a simple way to provide differentiated services. subsequently, there were several analytical studies of this promising idea. the central issue of these studies is whether pmp is viable, namely, whether it will produce more profit for the service provider, or whether it will achieve more social welfare. the previous studies considered similar models, but arrived at different conclusions. in this paper, we point out that the key is how the users react to the congestion externality of the underlying system. we derive sufficient conditions of congestion functions that can guarantee the viability of pmp, and provide the relevant physical meanings of these conditions.
implementation and evaluation of cooperative communication schemes in software-defined radio testbed. cooperative communication is a promising technique for future wireless networks, which significantly improves link capacity and reliability by leveraging broadcast nature of wireless medium and exploiting cooperative diversity. however, most of existing works investigate its performance theoretically or by simulation. it has been widely accepted that simulations often fail to faithfully capture many real-world radio signal propagation effects, which can be overcome through developing physical wireless network testbeds. in this work, we build a cooperative testbed based on gnu radio and universal software radio peripheral (usrp) platform, which is a promising open-source software-defined radio system. both single-relay cooperation and multi-relay cooperation can be supported in our testbed. some key techniques are provided to solve the main challenges during the testbed development: e.g., maximum ratio combine in single-relay transmission and synchronized transmission among multiple relays. extensive experiments are carried out in the testbed to evaluate performance of various cooperative communication schemes. the results show that cooperative transmission achieves significant performance enhancement in terms of link reliability and end-to-end throughput.
resource allocation over network dynamics without timescale separation. we consider a widely applicable model of resource allocation where two sequences of events are coupled: on a continuous time axis (t), network dynamics evolve over time. on a discrete time axis [t], certain control laws update resource allocation variables according to some proposed algorithm. the algorithmic updates, together with exogenous events out of the algorithm's control, change the network dynamics, which in turn changes the trajectory of the algorithm, thus forming a loop that couples the two sequences of events. in between the algorithmic updates at [t - 1] and [t], the network dynamics continue to evolve randomly as influenced by the previous variable settings at time [t - 1]. the standard way used to avoid the subsequent analytic difficulty is to assume the separation of timescales, which in turn unrealistically requires either slow network dynamics or high complexity algorithms. in this paper, we develop an approach that does not require separation of timescales. it is based on the use of stochastic approximation algorithms with continuous-time controlled markov noise. we prove convergence of these algorithms without assuming timescale separation. this approach is applied to develop simple algorithms that solve the problem of utility-optimal random access in multi-channel, multiradio wireless networks.
high-speed per-flow traffic measurement with probabilistic multiplicity counting. on today's high-speed backbone network links, measuring per-flow traffic information has become very challenging. maintaining exact per-flow packet counters on oc-192 or oc-768 links is not practically feasible due to computational and cost constrains. packet sampling as implemented in today's routers results in large approximation errors. here, we present probabilistic multiplicity counting (pmc), a novel data structure that is capable of accounting traffic per flow probabilistically. the pmc algorithm is very simple and highly parallelizable, and therefore allows for efficient implementations in software and hardware. at the same time, it provides very accurate traffic statistics. we evaluate pmc with both artificial and real-world traffic data, demonstrating that it outperforms other approaches.
optimal control of wireless networks with finite buffers. this paper considers network control for wireless networks with finite buffers. we investigate the performance of joint flow control, routing, and scheduling algorithms which achieve high network utility and deterministically bounded backlogs inside the network. our algorithms guarantee that buffers inside the network never overflow. we study the tradeoff between buffer size and network utility and show that if internal buffers have size (n - 1)/ε then a high fraction of the maximum utility can be achieved, where ε captures the loss in utility and n is the number of network nodes. the underlying scheduling/routing component of the considered control algorithms requires ingress queue length information (iqi) at all network nodes. however, we show that these algorithms can achieve the same utility performance with delayed ingress queue length information. numerical results reveal that the considered algorithms achieve nearly optimal network utility with a significant reduction in queue backlog compared to the existing algorithm in the literature. finally, we discuss extension of the algorithms to wireless networks with time-varying links.
the impact of virtualization on network performance of amazon ec2 data center. cloud computing services allow users to lease computing resources from large scale data centers operated by service providers. using cloud services, users can deploy a wide variety of applications dynamically and on-demand. most cloud service providers use machine virtualization to provide flexible and costeffective resource sharing. however, few studies have investigated the impact of machine virtualization in the cloud on networking performance. in this paper, we present a measurement study to characterize the impact of virtualization on the networking performance of the amazon elastic cloud computing (ec2) data center. we measure the processor sharing, packet delay, tcp/udp throughput and packet loss among amazon ec2 virtual machines. our results show that even though the data center network is lightly utilized, virtualization can still cause significant throughput instability and abnormal delay variations. we discuss the implications of our findings on several classes of applications.
worst-case tcam rule expansion. designers of tcams (ternary cams) for packet classification deal with unpredictable sets of rules, resulting in highly variable rule expansions, and rely on heuristic encoding algorithms with no reasonable expansion guarantees. in this paper, given several types of rules, we provide new upper bounds on the tcam worst-case rule expansions. in particular, we prove that a w-bit range can be encoded using w tcam entries, improving upon the previously-known bound of 2w-5. we also propose a modified tcam architecture that uses additional logic to significantly reduce the rule expansions, both in the worst case and in experiments with real-life classification databases.
ripple authentication for network coding. by allowing routers to randomly mix the information content in packets before forwarding them, network coding can maximize network throughput in a distributed manner with low complexity. however, such mixing also renders the transmission vulnerable to pollution attacks, where a malicious node injects corrupted packets into the information flow. in a worst case scenario, a single corrupted packet can end up corrupting all the information reaching a destination. in this paper, we propose ripple, a symmetric key based in-network scheme for network coding authentication. ripple allows a node to efficiently detect corrupted packets and encode only the authenticated ones. despite using symmetric key based homomorphic message authentication code (mac) algorithms, ripple achieves asymmetry by delayed disclosure of the mac keys. our work is the first symmetric key based solution to allow arbitrary collusion among adversaries. it is also the first to consider tag pollution attacks, where a single corrupted mac tag can cause numerous packets to fail authentication farther down the stream, effectively emulating a successful pollution attack.
on the fundamental limits of broadcasting in wireless mobile networks. in this paper, we investigate the fundamental properties of broadcasting in mobile wireless networks. in particular, we characterize broadcast capacity and latency of a mobile network, subject to the condition that the stationary node spatial distribution generated by the mobility model is uniform. we first study the intrinsic properties of broadcasting, and present a broadcasting scheme that simultaneously achieves asymptotically optimal broadcast capacity and latency, subject to a weak upper bound on the maximum node velocity. we then investigate the broadcasting problem when the burden related to selecting relay nodes is taken into account, and present a combined distributed leader election and broadcasting scheme achieving a broadcast capacity and latency which is within a poly-logarithmic factor from optimal.
coupled 802.11 flows in urban channels: model and experimental evaluation. contending flows in multi-hop 802.11 wireless networks compete with two fundamental asymmetries: (i) channel asymmetry, in which one flow has a stronger signal, potentially yielding physical layer capture, and (ii) topological asymmetry, in which one flow has increased channel state information, potentially yielding an advantage in winning access to the channel. prior work has considered these asymmetries independently with a highly simplified view of the other. however, in this work, we perform thousands of measurements on coupled flows in urban environments and build a simple, yet accurate model that jointly considers information and channel asymmetries. we show that if these two asymmetries are not considered jointly, throughput predictions of even two coupled flows are vastly distorted from reality when traffic characteristics are only slightly altered (e.g., changes to modulation rate, packet size, or access mechanism). these performance modes are sensitive not only to small changes in system properties, but also small-scale link fluctuations that are common in an urban mesh network. we analyze all possible capture relationships for two-flow sub-topologies and show that capture of the reverse traffic can allow a previously starving flow to compete fairly. finally, we show how to extend and apply the model in domains such as modulation rate adaptation and understanding the interaction of control and data traffic.
a greedy link scheduler for wireless networks with gaussian multiple access and broadcast channels. information theoretic broadcast channels (bc) and multiple access channels (mac) enable a single node to transmit data simultaneously to multiple nodes, and multiple nodes to transmit data simultaneously to a single node respectively. in this paper, we address the problem of link scheduling in multihop wireless networks containing nodes with bc and mac capabilities. we first propose an interference model that extends protocol interference models, originally designed for point to point channels, to include the possibility of bc and mac. due to the high complexity of optimal link schedulers, we introduce the multiuser greedy maximum weight algorithm for link scheduling in multihop wireless networks containing bcs and macs. given a network graph, we develop new local pooling conditions and show that the performance of our algorithm can be fully characterized using the associated parameter, the multiuser local pooling factor. we provide examples of some network graphs, on which we apply local pooling conditions and derive the multiuser local pooling factor. we prove optimality of our algorithm in tree networks and show that the exploitation of bcs and macs improve the throughput performance considerably in multihop wireless networks.
designing a practical access point association protocol. in a wireless local area network (wlan), the access point (ap) selection of a client heavily influences the performance of its own and others. through theoretical analysis, we reveal that previously proposed association protocols are not effective in maximizing the minimal throughput among all clients. accordingly, we propose an online ap association strategy that not only achieves a minimal throughput (among all clients) that is provably close to the optimum, but also works effectively in practice with a reasonable computational overhead. the association protocol applying this strategy is implemented on the commercial hardware and compatible with legacy aps without any modification. we demonstrate its feasibility and performance through real experiments.
a tractable and accurate cross-layer model for multi-hop mimo networks. mimo-based communications have great potential to improve network capacity for multi-hop wireless networks. although there has been significant progress on mimo at the physical layer or single-hop communication, advances in the theory of mimo for multi-hop wireless networks remain limited. this stagnation is mainly due to the lack of an accurate and more important, analytically tractable model that can be used by networking researchers. in this paper, we propose such a model to enable the networking community to carry out crosslayer research for multi-hop mimo networks. in particular, at the physical layer, we develop a simple model for mimo channel capacity computation that captures the essence of spatial multiplexing and transmit power limit without involving complex matrix operations and the water-filling algorithm. we show that the approximation gap in this model is negligible. at the link layer, we devise a space-time scheduling scheme called obic that significantly advances the existing zero-forcing beamforming (zfbf) to handle interference in a multi-hop network setting. the proposed obic scheme employs simple algebraic computation on matrix dimensions to simplify zfbf in a multi-hop network. as a result, we can characterize link layer scheduling behavior without entangling with beamforming details. finally, we apply both the new physical and link layer models in cross-layer performance optimization for a multi-hop mimo network.
minimizing electricity cost: optimization of distributed internet data centers in a multi-electricity-market environment. the study of cyber-physical system (cps) has been an active area of research. internet data center (idc) is an important emerging cyber-physical system. as the demand on internet services drastically increases in recent years, the power used by idcs has been skyrocketing. while most existing research focuses on reducing power consumptions of idcs, the power management problem for minimizing the total electricity cost has been overlooked. this is an important problem faced by service providers, especially in the current multi-electricity market, where the price of electricity may exhibit time and location diversities. further, for these service providers, guaranteeing quality of service (i.e. service level objectives-slo) such as service delay guarantees to the end users is of paramount importance. this paper studies the problem of minimizing the total electricity cost under multiple electricity markets environment while guaranteeing quality of service geared to the location diversity and time diversity of electricity price. we model the problem as a constrained mixed-integer programming and propose an efficient solution method. extensive evaluations based on reallife electricity price data for multiple idc locations illustrate the efficiency and efficacy of our approach.
maximizing energy efficiency for convergecast via joint duty cycle and route optimization. the energy efficiency of the widely used converge-cast pattern depends substantially on the choice of medium access control (mac) and routing protocol. in this paper, we formalize the maximization of convergecast energy efficiency with respect to its mac and routing as a resource constrained optimization problem. we then analytically show that this maximization problem is linear in the context of two prototypical macs -- a locally synchronized wakeup (as in s-mac) and a locally staggered wakeup mac (as in o-mac)-- assuming low, uniform traffic that is delivered reliably and without interference. with this insight, we present a centralized algorithm, meecast, that solves the optimization problem utilizing linear programming techniques. we also design a distributed version of meecast, for the case where the traffic is ultra-low, and prove that it achieves optimality as well as fast convergence time. notably, this version is self-stabilizing, so it autonomically handles changes in traffic load, network topology, loss of coordination and state corruption. in comparison with dozer, a state-of-the-art convergecast protocol, meecast achieves better energy efficiency and application lifetime in the context of s-mac and identical energy efficiency but better application lifetime in the context of o-mac.
tracking skype voip calls over the internet. peer-to-peer (p2p) voip calls such as those provided by skype have been becoming popular due to their quality-of-service, free of cost, security and convenience. skype is a distributed p2p network with no centralized call servers. calls traverse through a myriad of possible paths before reaching to the destination and each packet is encrypted with 256 bit aes encryption. in this paper, we are particularly interested in tracing out from this entangled web of peer nodes, who has called a target subscriber or to whom the target subscriber is calling. to this end, we present a transparent packet marking scheme that not only determines the origination and destination of a call but also the path taken through various hosts in p2p networks.