Abstract Nearly all modern smartphones are now equipped with a barometer to sample air pressure. Accessing these samples is deemed harmless, hence does not require permission. In this work, we demonstrate that barometer samples can reveal sensitive information, particularly in smartphones with ingress protection. Using a support-vector machine (SVM) classifier, we demonstrate for the first time that barometer readings, even at a low sampling rate (25 Hz), can reveal smartphone speaker activity. In particular, our classifier achieves $$\ge 95\%$$ ≥ 95 % accuracy in detecting whether the speaker is silent or playing a ringtone. In addition, we show that low-rate barometer samples can be used to 1) detect touchscreen finger taps with nearly $$100\%$$ 100 % accuracy, and 2) gain information about the approximate position of finger taps. Our findings underscore that the barometer sensor, often considered harmless, should be recognized as sensitive with regard to user privacy, and access to this sensor should be carefully managed.

Payment channel networks have great potential to scale cryptocurrency payment systems. However, their scalability power is limited as payments occasionally fail in these networks due to various factors. In this work, we study these factors and analyze their imposing limitations. To this end, we propose a model where a payment channel network is viewed as a compression method. In this model, the compression rate is defined as the ratio of the total number of payments entering the network to the total number of transactions that are placed on the blockchain to handle failed payments or (re)open channels. We analyze the compression rate and its upper limit, referred to as compression capacity, for various payment models, channel-reopening strategies, and network topologies. For networks with a tree topology, we show that the compression rate is inversely proportional to the average path length traversed by payments. For general networks, we show that if payment rates are even slightly asymmetric and channels are not reopened regularly, a constant fraction of payments will always fail regardless of the number of channels, the topology of the network, the routing algorithm used and the amount of allocated funds in the network. We also examine the impact of routing and channel rebalancing on the network’s compression rate. We show that rebalancing and strategic routing can enhance the compression rate in payment channel networks where channels may be reopened, differing from the established literature on credit networks, which suggests these factors do not have an effect.

Battery-powered IoT nodes are vulnerable tosignature-verificationdenial-of-service (DoS): an adversary can flood a device with well-formed but invalid messages, forcing expensive digital-signature verifications. A standard mitigation is to require proof-of-work (PoW) per message, but thissymmetricallyburdens honest and dishonest senders alike. We address this shortcoming with anasymmetricPoW-based mitigation that makes attackers pay while sparing honest parties. A designated Bitcoin miner embeds a request commitment in its coinbase transaction; any non-winning block header whose hash falls below an application-chosen threshold serves as PoW. The sender appends this header and a logarithmic-size Merkle proof; the IoT device first validates this PoW—just a handful of hash evaluations—before attempting the costly signature verification. Because proofs are bound to the miner’s payout address, adversaries cannot piggy-back on recycled work: they must grind fresh headers (or effectively mine on the designated miner’s behalf), preserving a large resource gap in the defender’s favor. We prototype the scheme on an ESP32 MCU and show that PoW verification takes 0.8 ms versus 260 ms for ECDSA (>300× speed-up); proof packages remain < 1 kB, and end-to-end latency is dominated by network RTT even with a moderate-capacity miner; power measurements likewise confirm that hash-based verifications cost orders of magnitude less energy than signatures. The mechanism requires no blockchain modifications, scales to thousands of devices per miner, and immediately hardens firmware updates, certificate rotation, and other unsolicited IoT traffic against signature-verification DoS attacks.

Route discovery in the Lightning Network is challenging because senders observe only static channel capacities while real-time balances remain hidden. Existing locally steered schemes such as SpeedyMurmurs protect path privacy but depend on global landmark trees whose maintenance traffic and detours inflate latency and overhead. We present Ticket to Ride (T2R), a locally steered source-routing framework that encodes the set of channels a payment may traverse into a compact ticket - an approximate-membership filter keyed with per-hop Diffie–Hellman secrets. Each relay learns only whether its own outgoing edges are permitted, yielding the same incident-edge privacy as SpeedyMurmurs while eliminating the need to build and maintain global landmark trees or any other shared routing state. Extensive simulations on real snapshots - incorporating churn, silent shutdowns, and random channel saturation - show that T2R boosts end-to-end success by up to 9% and cuts median delay by 1.6× relative to SpeedyMurmurs, all with < 1 kB total overhead and no extra handshakes. Because tickets are processed hop-by-hop and can be prefixed by a trampoline, T2R remains lightweight enough for resource-constrained IoT nodes.

The Lightning Network (LN) is a second layer system for solving the scalability problem of Bitcoin transactions. In the current implementation of LN, channel capacity (i.e., the sum of individual balances held in the channel) is public information, while individual balances are kept secret for privacy concerns. Attackers may discover a particular balance of a channel by sending multiple fake payments through the channel. Such an attack, however, can hardly threaten the security of the LN system due to its high cost and noticeable intrusions. In this work, we present a novel non-intrusive balance tomography attack, which infers channel balances silently by performing legal transactions between two pre-created LN nodes. To minimize the cost of the attack, we propose an algorithm to compute the optimal payment amount for each transaction and design a path construction method using reinforcement learning to explore the most informative path to conduct the transactions. Finally, we propose two approaches (NIBT-RL and NIBT-RL-β) to accurately and efficiently infer all individual balances using the results of these transactions. Experiments using simulated account balances over actual LN topology show that our method can accurately infer 90% ∼ 94% of all balances in LN with around 12 USD.

Decentralized Finance (DeFi) continues to open up promising opportunities for a broad spectrum of users, with lending pools emerging as a cornerstone of its applications. While prominent platforms like Compound and Aave maintain a large share of the funds in lending pools, numerous other smaller pools also exist. Many of these smaller entities draw heavily from the design principles of their larger counterparts due to the complex nature of lending pool design. This paper asserts that the design approaches that serve larger pools effectively may not necessarily be the most beneficial for smaller lending pools. We identify and elaborate on two liquidity management attacks, which can allow well-funded attackers to exploit specific circumstances within lending pools for personal gain. Although large lending pools, due to their vast and diverse liquidity and high user engagement, are generally less vulnerable to these attacks, smaller lending protocols may need to employ specialized defensive strategies, particularly during periods of low liquidity. We also show that beyond the six leading lending protocols, there exists a market value exceeding $1.75 billion. This considerable sum is dispersed among over 200 liquidity pools, posing a potentially attractive target for bad actors. Furthermore, we evaluate existing designs of lending pools and suggest a novel architecture that distinctly separates the liquidity and logic layers. This unique setup gives smaller pools the adaptability they need to link with larger, well-established pools. Despite encountering certain constraints, these emerging pools can leverage the considerable liquidity from larger pools until they generate sufficient funds to form their own standalone liquidity pools. This design cultivates a setting where multiple lending pools can integrate their liquidity components, thus encouraging a more diverse and robust liquidity environment.

We introduce the Condorcet attack, a new threat to fair transaction ordering. Specifically, the attack undermines batch-order-fairness, the strongest notion of transaction fair ordering proposed to date. The batch-order-fairness guarantees that a transaction tx is ordered before tx' if a majority of nodes in the system receive tx before tx'; the only exception (due to an impossibility result) is when tx and tx' fall into a so-called "Condorcet cycle". When this happens, tx and tx' along with other transactions within the cycle are placed in a batch, and any unfairness inside a batch is ignored. In the Condorcet attack, an adversary attempts to undermine the system’s fairness by imposing Condorcet cycles to the system. In this work, we show that the adversary can indeed impose a Condorcet cycle by submitting as few as two otherwise legitimate transactions to the system. Remarkably, the adversary (e.g., a malicious client) can achieve this even when all the nodes in the system behave honestly. A notable feature of the attack is that it is capable of "trapping" transactions that do not naturally fall inside a cycle, i.e. those that are transmitted at significantly different times (with respect to the network latency). To mitigate the attack, we propose three methods based on three different complementary approaches. We show the effectiveness of the proposed mitigation methods through simulations, and explain their limitations.

Routing protocol for low-power and lossy networks (RPL) is a standard routing protocol for the Internet of Things (IoT). In RPL, point-to-point (P2P) communication is gaining importance as many emerging IoT applications require efficient P2P communications. In this work, we study the quality of the RPL’s P2P paths. In particular, we analyze how much RPL’s P2P paths “stretch” compared to the shortest paths. We prove that the average stretch is a factor of at least two in any RPL network. That is, the RPL’s P2P path between two randomly selected nodes in any network is expected to be at least twice as long as the shortest path between the two nodes. Furthermore, we show that RPL’s stretch factor can be considerably higher than two in some network topology, including linear networks and grid networks. To improve the quality of RPL’s P2P paths, we propose a solution which is simple to implement and fully compatible with RPL. Moreover, our solution does not require nodes to store any routing table; this is important as nodes in LLNs are typically highly resource constrained. We evaluate our proposed solution using the Contiki-NG operating system and show that our proposed solution can significantly improve the quality of RPL’s P2P paths and their end-to-end-delays with a modest overhead. In addition, we evaluate our solution in dynamic networks and show that, when the network’s mobility is moderate, our solution generates nearly the same amount of overhead as RPL yet it achieves lower end-to-end delay and power consumption than RPL.

Atomic Swaps enable exchanging crypto-assets with-out trusting a third party. To enable these swaps, both parties lock funds and let their counterparty withdraw them in exchange for a secret. This leads to the so-called griefing attack, or the emergence of an American Call option, where one party stops participating in the swap, thereby making their counterparty wait for a timelock to expire before they can withdraw their funds. The standard way to mitigate this attack is to make the attacker pay a premium for the emerging American Call option. In these premium-paying approaches, the premium itself ends up being locked for possibly an even longer duration than the swap amount itself. We propose a new Atomic Swap construction, where neither party exposes itself to a griefing attack by their counterparty. Notably, unlike previous constructions, ours can be implemented in Bitcoin as is. Our construction also takes fewer on-chain transactions and has a lower worst-case timelock.

The owners of channels in the Bitcoin’s Lightning Network do not disclose their balances in order to protect their privacy, and conceal payment transfers through their channels. Nevertheless, recent studies have shown that channel balances can be discovered using simple probing techniques. These techniques are, however, slow, often rely on specific control messages, and require to open a new channel for every single channel balance discovery or have limited power in discovering balances of remote channels. In this work, we present a powerful balance discovery method called Torrent that overcomes these limitations of existing methods. Unlike the existing techniques, Torrent uses multi-path payments instead of single-path payments. This—together with a novel max flow algorithm designed for the Lightning Network— allows a single probing node to push a large flow of payments through any target channel, making it more likely to discover its balance. Moreover, Torrent can speed-up balance discovery through parallel payment transfers, and pre-computation of payment paths. In addition, Torrent can operate in the absence of routing control messages that are often relied on by the existing channel discovery methods.

We study the destination advertisement object (DAO) induction attack, a new attack against Internet Protocol version 6 (IPv6) routing protocol for low-power and lossy networks (RPL), the standard routing protocol for the Internet of Things (IoT). In the DAO induction attack, a compromised node in the network periodically transmits a special control message. Each of these crafted control messages induces many nodes in the network to transmit in response. We show that transmitting these unnecessary messages can significantly increase the power consumption of nodes, hence reduce the lifetime of battery-operated IoT devices. In addition, we show that the attack severely impacts end-to-end latency and packet delivery ratio, two important network performance metrics. For instance, in a network with 50 nodes, our simulation results show that the attack increases the average end-to-end latency and packet loss ratio by 410% and 260%, respectively. To counter the attack, we propose a lightweight solution. We show that our solution imposes no overhead when the network is in its normal operation (i.e., it is not under attack) and can quickly detect the attack even when the network experiences high packet loss rates.

In a payment network, like the Lightning Network, Alice can transfer a payment to Bob by splitting the payment into partial payments and transferring these partial payments through multiple paths. The transfer, however, delays if any of the partial payments fails or delays. To handle this, one can add redundant payment paths. The challenge in doing so is that Bob may now overdraw funds from the redundant paths. To address this, Bagaria, Neu, and Tse introduced Boomerang, a mechanism based on secret sharing and homomorphic one-way functions, which allows Alice to revert the transfer if Bob overdraws.

The Lightning Network (LN) is a second layer technology for solving the scalability problem of blockchain-based cryptocurrencies such as Bitcoin. The LN nodes (i.e., LN users), linked by payment channels, can make payments to each other directly or through multiple hops of payment channels, subject to the available balances of the serving channels. In current LN implementation, the channel capacity (i.e., the sum of the bidirectional balances in the channel) is open to the public, but the bidirectional balances are kept secret for privacy concerns. Nevertheless, the balances can be directly measured by conducting multiple fake payments to probe the precise value of the balance. Such a method, while effective, creates many fake invoices and incurs high cost when used for discovering balances for multiple users.

In the context of second layer payments in Bitcoin, and specifically the Lightning Network, we propose a design for a lightweight watchtower that does not need to store signed justice transactions. We alter the structure of the opening and commitment transactions in Lightning channels to encode justice transactions as part of the commitment transactions. With that, a watchtower just needs to watch for specific cheating commitment transaction IDs on the blockchain and can extract signed justice transactions directly from these commitment transactions that appear on the blockchain. Our construction saves an order of magnitude in storage over existing watchtower designs. In addition, we let the watchtower prove to each channel that it has access to all the data required to do its job, and can therefore be paid-per-update.

Broadcast is a fundamental network operation, widely used in wireless networks to disseminate messages. The energy-efficiency of broadcast is important particularly when devices in the network are energy constrained. To improve the efficiency of broadcast, different approaches have been taken in the literature. One of these approaches is broadcast with energy accumulation. Through simulations, it has been shown in the literature that broadcast with energy accumulation can result in energy saving. The amount of this saving, however, has only been analyzed for linear multi-hop wireless networks. In this paper, we extend this analysis to two-dimensional (2D) multi-hop networks. The analysis of saving in 2D networks is much more challenging than that in linear networks. It is because, unlike in linear networks, in 2D networks, finding minimum-energy broadcasts with or without energy accumulation are both NP-hard problems. Nevertheless, using a novel approach, we prove that this saving is constant when the path loss exponent α is strictly greater than two. Also, we prove that the saving is θ(log n) when α = 2, where n denotes the number of nodes in the network.

Locally repairable codes (LRCs) have been recently proposed and used in real-world distributed storage systems (DSSs) such as Microsoft Azure Storage and Facebook HDFS-RAID (Hadoop Distributed File System-Redundant Array of Independent Disks). Since information in DSSs is changed frequently, reducing update complexity (UC) of LRCs is of great interest. In this paper, we propose code design algorithms that can reduce UC of existing LRCs without sacrificing their important code parameters such as minimum distance, code rate, or locality. We establish bounds on UC, and use them to show that our algorithms can achieve optimal or near optimal UC for a large class of LRCs.

A linear block code with dimension k, length n, and minimum distance d is called a locally repairable code (LRC) with locality r, if it can retrieve any coded symbol by at most r other coded symbols. LRCs have been recently proposed and used in practice in distributed storage systems, such as Windows Azure Storage and Facebook HDFS-RAID. Theoretical bounds on the maximum locality of LRCs (r) have been established. The average locality of an LRC (r) directly affects the costly repair bandwidth, disk I/O, and the number of nodes involved in the repair process of a missing data block. There is a gap in the literature studying r. In this paper, we establish a lower bound on r of arbitrary (n, k, d) LRCs. Furthermore, we obtain a tight lower bound on r for a practical case where the code rate (R = (k/n)) is greater than (1 - (1/√n))2. Finally, we design three classes of LRCs that achieve the obtained bounds on r. Comparing with the existing LRCs, our proposed codes improve the average locality without sacrificing such crucial parameters as the code rate or minimum distance.

Instantly decodable network codes (IDNCs) are suggested in the literature to mitigate the problem of decoding delay in network coding. IDNC is also suggested for broadcast scenarios, where the goal is to maximize the number of decoded packets by the receivers, e.g., in multimedia broadcast. It is shown that after uncoded transmission of all the packets, one coded packet can be instantly decodable by a large number of users, when the transmitter is sighted, i.e., it has a perfect knowledge of the lost packets by each receiver. We introduce and study blind IDNC for broadcast, where the transmitter has no knowledge of the lost packets. Similar to the sighted IDNC, first all data packets are transmitted uncoded. Then, assuming the same erasure rate for all users, we allow a small number of coded packets (one, two or three), and study how these coded packets should be constructed to recover as many lost packets at the receivers as possible. The optimal solutions when one blind packet or two non-overlapping blind packets are transmitted are found. We see that two blind transmissions have comparable performance to a single optimal sighted transmission. Moreover, we prove that three blind transmissions outperform any single sighted transmission.

Locally repairable codes (LRCs) have been proposed and used in practice as effective coding methods for distributed storage systems (DSSs). In a DSS, information block recovery is a critical task performed in the case of data node permanent failure or temporal unavailability. Temporal node unavailability accounts for 90% of all block recoveries triggered in DSS. Since parity blocks are not needed to be recovered during a temporal node unavailability, special attention should be given to reconstruction of information blocks when trying to minimize the average bandwidth needed for block recovery. Motivated by this, in this work, we study the average locality ofinformation blocks. We obtain a lower bound on the average locality of information blocks of LRCs and design LRCs that achieve the bound. In addition to obtaining the optimal average locality for the information blocks, our codes achieve the optimal maximum locality for all the information blocks as well as some parity blocks (in some cases all the parity blocks).

Erasure codes are recently used in real-world distributed storage systems (DSSs) such as Google File System,Microsoft Azure Storage, and Facebook HDFS-RAID for data reliability. When designing erasure codes for DSSs, special attention is given to the associated costs of data handling operations such as repair or update. For example, locally repairable codes (LRC) are designed and used in DSSs to allow for low-cost repair of failed blocks. Update complexity (defined as the number of blocks that need to be updated when an information block is changed) is yet another design parameter. This parameter can be seen as a measure of the computation, I/O and networking costs associated with updating an information block in a DSS. Since information is frequently updated by many applications, lowering update complexity can result in lower power consumptions in DSSs. In this work, we study the update complexity of LRCs. Based on our study, we propose an improvement over the LRC used by Facebook HDFS-RAID. Keeping the same code parameters including length, storage overhead, minimum distance and cost of repair (locality), we improve the update complexity by more than 16%. Moreover, we show that with these parameters achieving a lower update complexity is impossible.

Data transfers happen frequently in server clusters for software and application deployment, and in parallel computing clusters to transmit intermediate results in batches among servers between computation stages. This paper presents Cooper, an optimized prototype system to speedup multi-batch data transfers among a cluster of servers, leveraging a theoretically proven optimal algorithm called “coded permutation gossip,” which employs a simple random topology control scheme to best utilize bandwidth and decentralized random linear network coding to maximize the useful information transmitted. On a process-level coding-transfer pipeline, we investigate the best block division, batch division and inter-batch scheduling strategies to minimize the broadcast finish time in a realistic setting. For batch-based transfers, we propose a scheduling algorithm with low overhead that overlaps the transfers of consecutive batches and temporarily prioritizes later batches, to further reduce the broadcast finish time. We describe an asynchronous and distributed implementation of Cooper and have deployed it on Amazon EC2 for evaluation. Based on results from real experiments, we show that Cooper can almost double the speed of data transfers in computing clusters, as compared to state-of-the-art content distribution tools like BitTorrent, at a low CPU overhead.

An (n, k) erasure code that can recover any coded symbol by at most r other coded symbols is called a locally repairable code (LRC) with locality r. LRCs have been recently implemented in distributed storage systems. Coding complexity reduction can be significantly decreased by using binary LRCs (BLRCs) as they eliminate costly multiplication calculation. In this paper, motivated by the recently erasure codes with d = 4 used in practice, we propose BLRCs when (r + 1) | n and d = 4. We prove that our proposed binary codes are optimal for r ∈ {1, 3}, meaning that neither their locality nor their minimum distance can be improved by non-binary codes. For r ≥ 4, our proposed binary codes offer near-optimal code rate, with a rate gap of O(log r/n) compared with optimal nonbinary codes. While keeping the bulk of code structure binary, we eliminate this rate gap by using fields with sizes as small as r + 2 for only two redundant symbols. These non-binary codes still eliminate the need for costly multiplications in many operations including a single failure repair (a dominant repair scenario). Using the construction of spanning BLRC with d = 4 as a backbone, we also construct LRCs with minimum distance d ≥ 6. Furthermore, we obtain a closed-form equation for the mean-time to data-loss of arbitrary erasure codes.

We use randomized network coding (RNC) with simple connection topology control to approach the theoretical limit on finish time of disseminating k blocks in a server cluster of n nodes. Unlike prior gossip literature which relies on completely random contact, we prove that with RNC, any receiver selection following a simple permutation rule can achieve a broadcast completion time of k + n and that a time-varying random ring topology achieves a completion time of k + o(k) + O(logn), both with high probability. Since the theoretical limit on finish time is k + [log2n], our simple permutation algorithms achieve absolutely optimal (not only order-optimal) block pipelining for the k blocks. Our results hold for both one-to-all (broadcast) and all-to-all transfers. We demonstrate the usefulness of the proposed organized network coded gossip with an application to content distribution in cluster computing systems like MapReduce, and discuss practical block dividing strategies to hide the negative effect of computation overhead of network coding.

We analyze the maximum gain that can be achieved through cooperative broadcast with energy accumulation and memory. We consider a linear network, where a known number of nodes are placed on a line, and derive an upper bound on Gtot, the gain of cooperative broadcast over noncooperative broadcast with respect to total power consumption. Specifically, we prove that, in linear networks with path loss exponent α = 2, Gtot≤ π2/12-π2≈ 4.64, irrespective of the number of devices, the size of the network, the node placement strategy, and the cooperative broadcast strategy. We extend this result to any path loss exponent α ≥ 2. We also show that the cooperation gain in shortrange transmissions, wherein the circuit energy consumption is nonnegligible, is smaller than that in long-range transmissions. We further study the cooperative broadcast gain when the objective is to reduce the maximum transmission power used by any node in the network. In this case, we show that, when nodes are distributed uniformly at random, the maximum cooperation gain will be O(log n), with high probability, where n is the number of nodes in the network. These are important observations that should be considered in designing power-efficient broadcast algorithms in future network-wide cooperative broadcast.

Throughput-delay tradeoff of random access over satellite links is analyzed and scaling laws are derived for the cases of the collision channel and the multipacket reception (MPR) channel as well as repetition random access. It is shown that multiuser detection and repetition schemes improve the multiple access performance in the sense that the inevitable compromise between throughput and delay is mitigated by joint detection capabilities and/or repetitions.

Given a set of positions for wireless nodes, the interference minimization problem is to assign a transmission radius (i.e., a power level) to each node such that the resulting communication graph is connected while minimizing the maximum (respectively, average) interference. We consider the model introduced by von Rickenbach (2005), in which each wireless node is represented by a point in Euclidean space on which is centered a transmission range represented by a ball, and edges in the corresponding graph are symmetric. The problem is NP-complete in two or more dimensions (Buchin 2008), and no polynomial-time approximation algorithm is known. We show how to solve the problem efficiently in settings typical for wireless ad hoc networks. If nodes are represented by a set P of n points selected uniformly and independently at random over a d-dimensional rectangular region, then the topology given by the closure of the Euclidean minimum spanning tree of P has O(log n) maximum interference with high probability and O(1) expected interference. We extend the first bound to a general class of communication graphs over a broad set of probability distributions. We present a local algorithm that constructs a graph from this class; this is the first local algorithm to provide an upper bound on expected maximum interference. Finally, we disprove a conjecture of Devroye and Morin (2012) relating the maximum interference of the Euclidean minimum spanning tree to the optimal maximum interference attainable.

A probabilistic medium-access control (MAC) protocol is proposed for an uncoordinated network of nodes with multipacket reception (MPR) capability at the receiver. The protocol uses binary feedback at the end of each time slot and uses an extended Kalman filter (EKF) to compute an estimate of the number of currently active nodes in the service area. The estimate is then used to optimize the expected system throughput by adjusting the medium access probability of each node. Simulations show that the proposed MAC protocol succeeds in tracking the number of nodes and achieving near-optimal throughput performance.

We use random linear network coding with simple connection topology control to approach the theoretical limit on finish time of disseminating k blocks in a server cluster of n nodes. Unlike existing gossip schemes which rely on completely random contact, we prove that with random linear network coding, any receiver selection following a simple permutation rule can achieve a broadcast finish time of k + n and that a time-varying random permutation topology achieves a finish time of k + o (k) + O (log n), both with high probability. Since the theoretical limit on finish time is k + log2 n, our simple permutation algorithms achieve absolutely optimal (not only order-optimal) block pipelining for k blocks. Our results hold for both one-to-all (broadcast) and all-to-all transfers. We demonstrate the usefulness of the proposed organized network coded gossip with an application to content distribution in cluster computing systems like MapReduce.

The broadcast throughput in a network is defined as the average number of messages that can be transmitted per unit time from a given source to all other nodes when time goes to infinity. Classical broadcast algorithms treat messages as atomic tokens and route them from the source to the receivers by making intermediate nodes store and forward messages. The more recent network coding approach, in contrast, prompts intermediate nodes to mix and code together messages. It has been shown that certain wired networks have an asymptotic network coding gap, that is, they have asymptotically higher broadcast throughput when using network coding compared to routing. Whether such a gap exists for wireless networks has been an open question of great interest. We approach this question by studying the broadcast throughput of the radio network model which has been a standard mathematical model to study wireless communication. We show that there is a family of radio networks with a tight Θ(log log n) network coding gap, that is, networks in which the asymptotic throughput achievable via routing messages is a Θ(log log n) factor smaller than that of the optimal network coding algorithm. We also provide new tight upper and lower bounds showing that the asymptotic worst-case broadcast throughput over all networks with n nodes is messages-per-round for both routing and network coding.

In much of the theoretical literature on global broadcast algorithms for wireless networks, issues of message dissemination are considered together with issues of contention management. This combination leads to complicated algorithms and analysis, and makes it difficult to extend the work to more difficult communication problems. In this paper, we present results aimed at simplifying such algorithms and analysis by decomposing the treatment into two levels, using abstract “MAC layer” specifications to encapsulate contention management. We use two different abstract MAC layers: the basic layer of [1], [2] and a new probabilistic layer. We first present a typical randomized contention-management algorithm for a standard graph-based radio network model and show that it implements both abstract MAC layers. Then we combine this algorithm with greedy algorithms for single-message and multi-message global broadcast and analyze the combinations, using both abstract MAC layers as intermediate layers. Using the basic MAC layer, we prove a bound of ODlogn∊log(Δ) for the time to deliver a single message everywhere with probability 1 − ∊, where D is the network diameter, n is the number of nodes, and Δ is the maximum node degree. Using the probabilistic layer, we prove a bound of OD+logn∊log(Δ), which matches the best previously-known bound for single-message broadcast over the physical network model. For multi-message broadcast, we obtain bounds of O(D+kΔ)logn∊log(Δ) using the basic layer and OD+kΔlogn∊log(Δ) using the probabilistic layer, for the time to deliver a message everywhere in the presence of at most k concurrent messages.

We present a randomized distributed algorithm that in radio networks with collision detection broadcasts a single message in O(D + log6 n) rounds, with high probability. This time complexity is most interesting because of its optimal additive dependence on the network diameter D. It improves over the currently best known O(Dlogn/D + log2 n) algorithms, due to Czumaj and Rytter [FOCS 2003], and Kowalski and Pelc [PODC 2003]. These algorithms where designed for the model without collision detection and are optimal in that model. However, as explicitly stated by Peleg in his 2007 survey on broadcast in radio networks, it had remained an open question whether the bound can be improved with collision detection.

There are two main approaches, static and dynamic, to broadcast algorithms in wireless ad hoc networks. In the static approach, local algorithms determine the status (forwarding/nonforwarding) of each node proactively based on local topology information and a globally known priority function. In this paper, we first show that local broadcast algorithms based on the static approach cannot achieve a good approximation factor to the optimum solution (an NP-hard problem). However, we show that a constant approximation factor is achievable if (relative) position information is available. In the dynamic approach, local algorithms determine the status of each node "on-the-fly” based on local topology information and broadcast state information. Using the dynamic approach, it was recently shown that local broadcast algorithms can achieve a constant approximation factor to the optimum solution when (approximate) position information is available. However, using position information can simplify the problem. Also, in some applications it may not be practical to have position information. Therefore, we wish to know whether local broadcast algorithms based on the dynamic approach can achieve a constant approximation factor without using position information. We answer this question in the positive-we design a local broadcast algorithm in which the status of each node is decided "on-the-fly” and prove that the algorithm can achieve both full delivery and a constant approximation to the optimum solution.

Multiple-message broadcast, or k-broadcast, is one of the fundamental problems in network communication. In short, there are k packets distributed across the network, each of them has to be delivered to all other nodes. We consider this task in the model of multi-hop radio network, in which n nodes interact by transmitting and receiving messages. A message transmitted at a round reaches all neighbors of the transmitter at the end of the same round, but may not be successfully received by some, or even all, of these neighbors. More specifically, a node receives a message at a round if this is the only message that has reached this node in this round. Due to this specific interference-prone nature of radio networks, many communication tasks become more challenging and more costly than in other types of networks, especially in ad-hoc setting in which each node knows only its own id and linear estimates on the basic network parameters, such as the number of nodes n, diameter D and maximum node degree Δ. We design a new randomized k-broadcast algorithm combining the bestof two worlds: efficient randomized transmission schedules and network coding. We show that our algorithm accomplishes multi-broadcast in O(log Δ) amortized number of communication rounds per packet, with high probability. This improves over the best previous solution of Bar-Yehuda, Israeli and Itai, which guarantees only O(log Δ log n) of amortized number of rounds per packet, with high probability.

The complexity of the optimal phase control problem in wireless MIMO systems with scalar feedback quantization and equal-gain transmission is studied. The problem is shown to be NP-hard when the number of receive antennas grows linearly with the number of transmit antennas. For the case where the number of receive antennas is constant, the problem can be solved in polynomial time. An optimal algorithm is explicitly constructed. For practical purposes, a low-complexity algorithm based on local search is presented. Simulation results show that its performance is nearly optimal.

Reliable detection of primary users (PUs) is an important task for cognitive radio (CR) systems. Cooperation among a few spectrum sensors has been shown to offer significant gain in the performance of the CR spectrum-sensing system by countering the shadow-fading effects. We consider a parallel fusion network in which the sensors send their sensing information to an access point which makes the final decision regarding presence or absence of the PU signal. It has been shown in the literature that the presence of malicious users sending false sensing data can severely degrade the performance of such a cooperative sensing system. In this paper, we investigate schemes to identify the malicious users based on outlier detection techniques for a cooperative sensing system employing energy detection at the sensors. We take into consideration constraints imposed by the CR scenario such as the lack of information about the primary signal propagation environment and the small size of the sensing data samples. Considering partial information of the PU activity, we propose a novel method to identify the malicious users. We further propose malicious user detection schemes that take into consideration the spatial information of the CR sensors. The performance of the proposed schemes are studied using simulations.

The contribution of this letter is the computation of exact symbol error probability (SEP) of three-dimensional (3- D) signal constellations over an additive white Gaussian noise (AWGN) channel. The originality of the proposed method is that it can be applied to any arbitrary 3-D constellation whose decision regions may not meet at right angles. We express the SEP in a triple integral form which is further simplified. The simplified form requires a single integral evaluation of standard "erf" function. Using the derived exact SEP formula, we plot SEP for a number of selected 3-D constellations. The SEP obtained using the proposed formula is validated by simulation results. It is also compared with the union bound approximation, an upper bound for SEP.

This paper presents two efficient flooding algorithms based on 1-hop neighbor information. In the first part of the paper, we consider sender-based flooding algorithms, specifically the algorithm proposed by Liu et al. In their paper, Liu et al. propose a sender-based flooding algorithm that can achieve local optimality by selecting the minimum number of forwarding nodes in the lowest computational time complexity O(n logn), where n is the number of neighbors. We show that this optimality only holds for a subclass of sender-based algorithms. We propose an efficient sender-based flooding algorithm based on 1-hop neighbor information that reduces the time complexity of computing forwarding nodes to O(n). In Liu's algorithm, n nodes are selected to forward the message in the worst case, whereas in our proposed algorithm, the number of forwarding nodes in the worst case is 11. In the second part of the paper we propose a simple and highly efficient receiver-based flooding algorithm. When nodes are uniformly distributed, we prove that the probability of two neighbor nodes broadcasting the same messageneighbor nodes broadcasting the same message exponentially decreases when the distance between them decreases or when the node density increases. The analytical results are confirmed using simulation.

In this paper, we analyze the effect of the wormhole attack on shortest-path routing protocols for wireless ad hoc networks. Using analytical and simulation results, we show that a strategic placement of the wormhole when the nodes are uniformly distributed can disrupt/control on average 32% of all communications across the network. We also analyze a scenario in which several attackers make wormholes between each other and a case where two malicious nodes attack a target node in the network. We show how to evaluate the maximum effect of the wormhole attack on a given network topology. Then, we compute the maximum effect of the wormhole attack on grid topology networks and show that the attackers can disrupt/control around 40% to 50% of all communications when the wormhole is strategically placed in the network. Finally, to defend against the wormhole attack, we propose a timing-based countermeasure that avoids the deficiencies of existing timing-based solutions. Using the proposed countermeasure, the nodes do not need synchronized clocks, nor are they required to predict the sending time or to be capable of fast switching between the receive and send modes. Moreover, the nodes do not need one-to-one communication with all their neighbors and do not require to compute a signature while having to timestamp the message with its transmission time.

The most important task for a cognitive radio (CR) system is to identify the primary licensed users over a wide range of spectrum. Cooperation among spectrum sensing devices has been shown to offer various benefits including decrease in sensitivity requirements of the individual sensing devices. However, it has been shown in the literature that the performance of cooperative sensing schemes can be severely degraded due to presence of malicious users sending false sensing data. In this paper, we present techniques to identify such malicious users and mitigate their harmful effect on the performance of the cooperative sensing system.

The common belief is that localized broadcast algorithms are not able to guarantee both full delivery and a good bound on the number of transmissions. In this paper, we propose the first localized broadcast algorithm that guarantees full delivery and a constant approximation ratio to the minimum number of required transmissions in the worst case. The proposed broadcast algorithm is a self-pruning algorithm based on one round of information exchange. Using the proposed algorithm, each node determines its forwarding status in O(D logD), where D is the maximum node degree of the network. By extending the proposed algorithm, we show that localized broadcast algorithms can achieve both full delivery and a constant approximation ratio to the optimum solution with message complexity O(N), where N is the total number of nodes in the network and each message contains a constant number of bits. We also show how to save bandwidth by reducing the size of piggybacked information. Finally, we relax several system-model assumptions, or replace them with practical ones, in order to improve the practicality of the proposed broadcast algorithm.

We consider the problem of finding the number of subsequences when deleting symbols from a string. We present a framework to find closed-form expressions for the number of subsequences, and use it to prove the first explicit formulas for and the first formulas for nonbinary alphabets. We also present the first efficient algorithm to compute the number of subsequences for any string, number of deletions, and alphabet size.

Reducing the number of redundant transmissions is one of the main objectives of efficient broadcast algorithms for wireless ad hoc networks. There are many localized broadcast algorithms proposed to reduce the number of transmissions. However, they do not guarantee a reasonable bound on the number of transmissions in the worst case. In fact, the common belief is that localized broadcast algorithms are not able to guarantee both full delivery and a good bound on the number of transmissions. In this paper, we propose the first localized broadcast algorithm that guarantees full delivery and a constant approximation ratio to the minimum number of required transmissions in the worst case. The proposed broadcast algorithm is a self-pruning algorithm based on 1-hop neighbor information. Our experimental results confirm the analytical analysis of the algorithm and show a significant reduction in the number of transmissions and end-to-end latency compared to one of the best broadcast algorithms based on 1-hop neighbor information.

This paper presents two main results relating to elliptic curve cryptography. First, a double point compression scheme is proposed which allows a compact representation of elliptic curve points without the computational cost associated with ordinary single point compression. A triple point compression scheme is also proposed which can result in more savings in memory and/or bandwidth. Second, a new approach to speeding up random point multiplication is given for the case where the base point is variable but available in a certificate. In this approach, some redundant information (a few multiples of the base point) is added to the certificate. It is shown that a significant speed up can be obtained by optimizing the Moller's algorithm for the case where only a portion of the lookup table is available. It is also shown how to use redundant information to compute random point multiplication using parallel processors. The proposed point compression schemes can be employed to reduce the required bandwidth when single point compression is computationally expensive

The wormhole attack is one of the most severe security attacks in wireless ad hoc networks. In this paper, we analyze the effect of the wormhole attack in shortest path routing protocols. Using analytical and simulation results, we show that a strategic placement of the wormhole can disrupt on average 32% of all communications across the network. We also analyze a more severe attack in which several attackers make wormholes between each other and give an upper bound on the average number of communications that can be disrupted. Finally, we propose a new robust and secure on-demand distance vector routing protocol which is able to route packets as long as there is a non-faulty path between the source and the destination.

We consider the optimal phase control problem in wireless MIMO systems with quantized phases. We show that the problem is NP-hard when number of receive antennas grows linearly with the number of transmit antennas. For the case where the number of receive antennas is constant, we show that the problem is no longer NP-hard by providing a polynomial time algorithm.

This paper introduces a new radix-2 representation with the same average weight as the width-w nonadjacent form (w-NAF). In both w-NAF and the proposed representations, each nonzero digit is an odd integer with absolute value less than M. However, for w-NAF, M is of the form 2/sup w-1/, while, for the proposed representation, it can be any positive integer. Therefore, using the proposed integer representation, we can use the available memory efficiently, which is attractive for devices with limited memory. Another advantage of the proposed representation over-w-NAF is that it can be obtained by scanning the bits from left-to-right. This property is also useful for memory-constrained devices because it can reduce both the time and space complexity of fast point multiplication techniques.