In this article, we study efficient and authorized rewriting of transactions already written to a blockchain. Mutable transactions will make a fraction of all blockchain transactions, but will be a necessity to meet the needs of privacy regulations, such as the General Data Protection Regulation (GDPR). The state-of-the-art rewriting approaches have several shortcomings, such as lack of user anonymity, inefficiency, and absence of revocation mechanisms for entities authorized to mutate transactions. To address this challenge we present \(\mathsf{ReTRACe}\) , an efficient framework for blockchain rewrites. \(\mathsf{ReTRACe}\) is designed by composing a revocable chameleon hash scheme with an ephemeral trapdoor, a revocable fast attribute based encryption scheme, and a dynamic group signature scheme. In this article, (i) we discuss \(\mathsf{ReTRACe}\) and its constituent primitives in detail, (ii) present security analyses of the primitives, and (iii) present experimental results to demonstrate the scalability of \(\mathsf{ReTRACe}\) .

In the era of big data, effective feature selection is critical for improving model performance, reducing computational cost, and enhancing interpretability in high-dimensional datasets. This paper introduces a novel filter-based feature selection algorithm, Class-wise Mean Deviation (CMD), which quantifies the discriminative power of features by measuring the absolute deviation of class-wise means from the global mean. Designed for scalability and real-world application, CMD is computationally efficient and particularly effective in handling the severe class imbalance common in large-scale datasets. We evaluate CMD on two large-scale, highly imbalanced benchmark intrusion detection datasets—CICIDS2017 and CICIDS2019—and compare its performance against established filter methods including Variance Threshold, Pearson Correlation, Mutual Information, and Fisher Score. Experimental results demonstrate that CMD consistently achieves competitive or superior classification performance, even with a minimal number of features. These findings highlight CMD’s potential as a robust and interpretable feature selection technique for cybersecurity and other high-dimensional domains.

The growing popularity of Machine Learning (ML) has led to its deployment in various sensitive domains, which has resulted in significant research focused on ML security and privacy. However, in some applications, such as Augmented/Virtual Reality, integrity verification of the outsourced ML tasks is more critical-a facet that has not received much attention. Existing solutions, such as multi-party computation and proof-based systems, impose significant computation overhead, which makes them unfit for real-time applications. We propose Fides, a novel framework for real-time integrity validation of ML-as-a-Service (MLaaS) inference. Fides features a novel and efficient distillation technique-Greedy Distillation Transfer Learning-that dynamically distills and fine-tunes a space and compute-efficient verification model for verifying the corresponding service model while running inside a trusted execution environment. Fides features a client-side attack detection model that uses statistical analysis and divergence measurements to identify, with a high likelihood, if the service model is under attack. Fides also offers a re-classification functionality that predicts the original class whenever an attack is identified. We devised a generative adversarial network framework for training the attack detection and re-classification models. The evaluation shows that Fides achieves an accuracy of up to 98% for attack detection and 94% for re-classification.

Payment channel networks are a promising solution to the scalability challenge of blockchains and are designed for significantly increased transaction throughput compared to the layer one blockchain. Since payment channel networks are essentially decentralized peer-to-peer networks, routing transactions is a fundamental challenge. Payment channel networks have some unique security and privacy requirements that make pathfinding challenging, for instance, network topology is not publicly known, and sender/receiver privacy should be preserved, in addition to providing atomicity guarantees for payments. In this paper, we present an efficient privacy-preserving routing protocol, SPRITE, for payment channel networks that supports concurrent transactions. By finding paths offline and processing transactions online, SPRITE can process transactions in just two rounds, which is more efficient compared to prior work. We evaluate SPRITE's performance using Lightning Network data and prove its security using the Universal Compos-ability framework. In contrast to the current cutting-edge methods that achieve rapid transactions, our approach significantly reduces the message complexity of the system by 3 orders of magnitude while maintaining similar latencies.

Pervasive Edge Computing (PEC), a recent addition to the edge computing paradigm, leverages the computing resources of end-user devices to execute computation tasks in close proximity to users. One of the primary challenges in the PEC environment is determining the appropriate servers for offloading computation tasks based on factors, such as computation latency, response quality, device reliability, and cost of service. Computation outsourcing in the PEC ecosystem requires additional security and privacy considerations. Finally, mechanisms need to be in place to guarantee fair payment for the executed service(s).

Federated learning (FL) is gaining much popularity in designing Intrusion Detection Systems (IDS) due to its ability to maintain data privacy and reduce communication costs. Existing FL-based IDS are generally tested with balanced class distribution for all clients where each client has data with all attack traffic categories. This is a very strong assumption. In reality, we often encounter a local class imbalance issue, which means that each client only has traffic with a few number of attack types. This issue creates a critical challenge in FL by leading to poor model performance and convergence. Several studies have made efforts to solve this issue through the clustering of local model parameters. However, their methods are costly and require either prior knowledge or training to select the number of clusters. In this work, we propose a Multi-Model-based Federated Learning (MMFL) framework, which automatically groups the local models of clients having similar class distribution, and a novel data augmentation method to add instances with unknown attack types to the datasets of local devices. Our extensive experiments with two large latest intrusion detection datasets show that MMFL outperforms the five baselines on the intrusion detection task.

WiFi 5/6 relies on a key feature, Multi-User Multiple-In-Multiple-Out (MU-MIMO), to offer high-volume network throughput and spectrum efficiency. MU-MIMO uses a user selection algorithm, based on each user's channel state information (CSI), to schedule transmission opportunities for a group of users to maximize the service quality and efficiency. In this paper, we discover that such algorithm creates a subtle attack surface for attackers to subvert user selection in MU-MIMO, causing severe disruptions in today's wireless networks. We develop a system, named MU-MIMO user selection strategy inference and subversion (MUSTER), to systematically study the attack strategies and further to seek efficient mitigation. MUSTER is designed to include two major modules: (i) strategy inference, which leverages a new neural group-learning strategy named MC-grouping via combining Recurrent Neural Network (RNN) and Monte Carlo Tree Search (MCTS) to reverseengineer a user selection algorithm, and (ii) user selection subversion, which proactively fabricates CSI to manipulate user selection results for disruption. Experimental evaluation shows that MUSTER achieves a high accuracy rate around 98.6% in user selection prediction and effectively launches the attacks to disrupt the network performance. Finally, we create a Reciprocal Consistency Checking technique to defend against the proposed attacks to secure MU-MIMO user selection.

Edge Computing is a new computing paradigm where applications operate at the network edge, providing low-latency services with augmented user and data privacy. A desirable goal for edge computing is pervasiveness, that is, enabling any capable and authorized entity at the edge to provide desired edge services--pervasive edge computing (PEC). However, efficient access control of users receiving services and edge servers handling user data, without sacrificing performance is a challenge. Current solutions, based on "always-on" authentication servers in the cloud, negate the latency benefits of services at the edge and also do not preserve user and data privacy. In this paper, we present APECS, an advanced access control framework for PEC, which allows legitimate users to utilize any available edge services without need for communication beyond the network edge. The APECS framework leverages multi-authority attribute-based encryption to create a federated authority, which delegates the authentication and authorization tasks to semi-trusted edge servers, thus eliminating the need for an "always-on" authentication server in the cloud. Additionally, APECS prevents access to encrypted content by unauthorized edge servers. We analyze and prove the security of APECS in the Universal Composability framework and provide experimental results on the GENI testbed to demonstrate the scalability and effectiveness of APECS.

In this paper, we study efficient and authorized rewriting of transactions already written to a blockchain. Mutable transactions will make a fraction of all blockchain transactions, but will be a necessity to meet the needs of privacy regulations, such as the General Data Protection Regulation (GDPR). The state-of-the-art rewriting approaches have several shortcomings, such as being coarse-grained, inability to expunge data, absence of revocation mechanisms, lack of user anonymity, and inefficiency. We present ReTRACe, an efficient framework for transaction-level blockchain rewrites, that is fine-grained and supports revocation. ReTRACe is designed by composing a novel revocable chameleon hash with ephemeral trapdoor scheme, a novel revocable fast attribute based encryption scheme, and a dynamic group signature scheme. We discuss ReTRACe, and its constituent primitives in detail, along with their security analyses, and present experimental results to demonstrate scalability.

In today's era of explosion of Internet of Things (IoT) and end-user devices and their data volume emanating at the network's edge, the network should be more in-tune with meeting the needs of these demanding edge computing applications. To this end, we design and prototype Information-Centric edge (ICedge), a general-purpose networking framework that streamlines service invocation and improves the reuse of redundant computation at the edge. ICedge runs on top of named-data networking, a realization of the information-centric networking vision, and handles the “low-level” network communication on behalf of applications. ICedge features a fully distributed design that: 1) enables users to get seamlessly on-boarded onto an edge network; 2) delivers application invoked tasks to edge nodes for execution in a timely manner; and 3) offers naming abstractions and network-based mechanisms to enable (partial or full) reuse of the results of already executed tasks among users, which we call “compute reuse,” resulting in lower task completion times and efficient use of edge computing resources. Our simulation and testbed deployment results demonstrate that ICedge can achieve up to $50\times $ lower task completion times leveraging its network-based compute reuse mechanism compared to cases, where reuse is not available.

Electric vehicles can place a significant load on the power grid due to their unscheduled charging events. One way of improving power grid stability is to schedule electric vehicle charging in advance. Before a charging visit, the electric vehicle provides necessary information to request for charging at a charging station, which prepares and reserves the energy before the visit. However, the reported information can cause privacy leakage of the electric vehicle user. Anonymous information reporting can protect user privacy, but also enables attacks on the charging station by unauthorized users. An anonymous authentication system can address these issues, but cannot detect misbehaviors by authenticated users. One remedy to this is revocable anonymity-based authentication, which can revoke the anonymity of malicious users after their misbehaviors. However, we show that such a system is still vulnerable to application-level Denial of Service attacks, where a malicious user requests for large amounts of energy simultaneously from many charging stations, preventing these stations from serving other users. To address this, we improve upon an existing revocable anonymity-based authentication framework. We propose a permit-based mechanism, where each electric vehicle is only issued with one blind signature-based permit at a time. A request is valid only if it contains a valid and unused permit, which protects the system from the application-level Denial of Service attacks. Security analysis and experiments demonstrate that our framework, while ensuring user anonymity and being robust to the aforementioned attack, is also scalable and lightweight.

Today, with the emergence of various business review sites such as Yelp, Trip Advisor, and Zomato, people can write reviews and provide an assessment (often as 1-5 score rating). The success of a business on the crowd-sourced review platform has taken the form of positive reviews and high star ratings (failure are associated with negative reviews and low star ratings). We often claim that location plays a major role in determining the success or the failure of a given business. This paper attempts to verify this claim and quantifies the impact of location, solely, on business success, using two data sets; a Yelp dataset for business information and reviews, and another Location dataset that gathers location-based information in a city or an area. We perform an empirical study to quantify the impact of (i) relative location to well known landmarks and (ii) parameterized location (such as cost of living in a given zip code), on the success of restaurants. In our study, we found that parameterized location using location characteristic parameters such as housing affordability correlate highly with restaurant success with more than 0.81 correlation ratio. We also observe that the closer the restaurant to a landmark (relative location) the more likelihood it succeeds.

Organized surveillance, especially by governments poses a major challenge to individual privacy, due to the resources governments have at their disposal, and the possibility of overreach. Given the impact of invasive monitoring, in most democratic countries, government surveillance is, in theory, monitored and subject to public oversight to guard against violations. In practice, there is a difficult fine balance between safeguarding individual's privacy rights and not diluting the efficacy of national security investigations, as exemplified by reports on government surveillance programs that have caused public controversy, and have been challenged by civil and privacy rights organizations. Surveillance is generally conducted through a mechanism where federal agencies obtain a warrant from a federal or state judge (e.g., the US FISA court, Supreme Court in Canada) to subpoena a company or service-provider (e.g., Google, Microsoft) for their customers' data. The courts provide annual statistics on the requests (accepted, rejected), while the companies provide annual transparency reports for public auditing. However, in practice, the statistical information provided by the courts and companies is at a very high level, generic, is released after-the-fact, and is inadequate for auditing the operations. Often this is attributed to the lack of scalable mechanisms for reporting and transparent auditing. In this paper, we present SAMPL, a novel auditing framework which leverages cryptographic mechanisms, such as zero knowledge proofs, Pedersen commitments, Merkle trees, and public ledgers to create a scalable mechanism for auditing electronic surveillance processes involving multiple actors. SAMPL is the first framework that can identify the actors (e.g., agencies and companies) that violate the purview of the court orders. We experimentally demonstrate the scalability for SAMPL for handling concurrent monitoring processes without undermining their secrecy and auditability.

Distributed credit networks, such as Ripple~\citeripple and Stellar~\citestellar, are becoming popular as an alternative means for financial transactions. % However, the current designs do not preserve user privacy or are not truly decentralized. % In this paper, we explore the creation of a distributed credit network that preserves user and transaction privacy and unlinkability. We propose BlAnC, a novel, fully decentralized blockchain-based credit network where credit transfer between a sender-receiver pair happens on demand. In BlAnC, multiple concurrent transactions can occur seamlessly, and malicious network actors that do not follow the protocols and/or disrupt operations can be identified efficiently. % for potential debarring by the users from future transactions. % We perform security analysis of our proposed protocols in the universal composability framework to demonstrate its strength, and discuss how our network handles operational dynamics. % We also present preliminary experiments and scalability analyses.

The fast-growing Internet traffic is increasingly becoming content-based and driven by mobile users, with users more interested in data rather than its source. This has precipitated the need for an information-centric Internet architecture. Research in information-centric networks (ICNs) have resulted in novel architectures, e.g., CCN/NDN, DONA, and PSIRP/PURSUIT; all agree on named data based addressing and pervasive caching as integral design components. With network-wide content caching, enforcement of content access control policies become non-trivial. Each caching node in the network needs to enforce access control policies with the help of the content provider. This becomes inefficient and prone to unbounded latencies especially during provider outages. In this paper, we propose an efficient access control framework for ICN, which allows legitimate users to access and use the cached content directly, and does not require verification/authentication by an online provider authentication server or the content serving router. This framework would help reduce the impact of system down-time from server outages and reduce delivery latency by leveraging caching while guaranteeing access only to legitimate users. Experimental/simulation results demonstrate the suitability of this scheme for all users, but particularly for mobile users, especially in terms of the security and latency overheads.

Data-driven and collaborative research has become the trend for today's scientific communities, resulting in large- scale datasets being shared and transported through networks every day. Most of these large data transfers use TCP sockets which are known to be limited in long-distance and high-bandwidth scenarios. UDP, on the other hand, while fast and efficient does not implement any reliability mechanisms. In this paper, we investigate the use of erasure coding techniques, namely fountain codes, on top of UDP to help high speed and reliable data transfer applications to attain high bandwidth in the face of packet losses. We propose RC-UDP, a Raptor Code over UDP framework that enables reliable data transfers for high bandwidth networks. We implement RC-UDP and evaluate its performance using computer simulation (ns-3) and real world testbed experimentations. We compare RC-UDP to HighSpeed and CUBIC TCP. Our results show that RC-UDP, which achieves up to 75X time reduction while incurring minimum overhead, is beneficial when the network is subject to high congestion or packet drop rates.

Pervasive content caching is one of the information-centric networking (ICN) fundamentals. Although advantageous, pervasive caching introduces new challenges. In particular, the high possibility of content providers losing control over their published contents, which clients can access without authenticating themselves. The approaches that constitute the state-of-the-art in access control either have high computation overhead or require an always-online authentication server, thus suffering in terms of scalability for large number of end devices. In this paper, we propose TACTIC, a lightweight access control mechanism for the ICN wireless edge, which allows legitimate clients to utilize the cached content without per-request authentication at the providers. TACTIC delegates the authentication and authorization tasks to the (semi-trusted) routers in an ISP's network to eliminate the need for an always-online authentication server. It prevents delivery of the encrypted content to unauthorized users; a bandwidth-wasteful practice, which may lead to Distributed Denial of Service (DDoS) attack. Experimental results demonstrate the scalability and effectiveness of TACTIC in providing low-overhead access to legitimate clients while preventing malicious users' access.

Wireless network applications such as intelligent buildings and disaster relief operations use large‐scale platforms. In these networks using multiple sinks reduce packet loss. However, finding the optimum locations for the sinks has not been fully studied yet. Therefore, the authors sought to investigate whether the location of sinks can affect network parameters, such as capacity and delay. In this study, two schemes named popular‐location scheme and random scheme are designed based on sink location. In the popular‐location scheme, the sinks (base stations) are located around the popular points (most visited locations) according to the location popularity rule. However, in the random scheme, sinks are distributed randomly. The authors considered a cell‐partitioned network to manage the signal interference between cells. The authors' results demonstrated that there is a trade‐off between capacity and delay in both schemes. Additionally, the effect of packet redundancy on capacity and delay was investigated. Furthermore, by utilising the popularity rule, the network capacity and average delay improved significantly. Moreover, the authors' results indicate that packet redundancy does not affect the capacity, but it improves the delay.

Recent literature suggests that the Internet of Things (IoT) scales much better in an information-centric networking (ICN) model instead of the current host-centric Internet protocol (IP) model. In particular, the named data networking (NDN) project (one of the ICN architecture flavors) offers features exploitable by IoT applications, such as stateful forwarding, in-network caching, and built-in assurance of data provenance. Though NDN-based IoT frameworks have been proposed, none have adequately and holistically addressed concerns related to secure onboarding and routing. Additionally, emerging IoT applications such as smart cities require high scalability and thus pose new challenges to NDN routing. Therefore, in this paper, we propose and evaluate a novel, scalable framework for lightweight authentication and hierarchical routing in the NDN IoT. Our ns-3 based simulation analyses demonstrate that our framework is scalable and efficient. It supports deployment densities as high as 40000 nodes/km2with an average onboarding convergence time of around 250 s and overhead of less than 20 kibibytes per node. This demonstrates its efficacy for emerging large-scale IoT applications such as smart cities.

Distributed Constraint Optimization Problems (DCOPs) are commonly used to model multi-agent coordination problems. However, empirical evaluations of DCOP algorithms are typically done in simulation under the assumption that the communication times between all pairs of agents are identical, which is unrealistic in many real-world applications. In this paper, we investigate the impact of empirically evaluating a DCOP algorithm under the assumption that communication times between pairs of agents can vary and propose the use of ns-2, a de-facto simulator used by the computer networking community, to simulate the communication times. Additionally, we introduce heuristics that exploit the non- uniform communication times to speed up DCOP algorithms that operate on pseudo-trees.

As technology improves in size and the number of smart devices increases, security in personal devices undoubtedly becomes an important aspect of today's life. However, the complexity in hardware and software systems expose vulnerabilities in security. Vulnerabilities may exist in many layers of systems and would require a specific inputs or events to trigger it. Discovery of vulnerabilities require significant time and also system specific knowledge, and even then some are difficult to patch.In this paper, we study open source tools for finding potential vulnerabilities and represent the advantages and disadvantages in their use. We present HardVul, a vulnerability checking tool which can be run on any architecture and reports which vulnerabilities were found from our testbed.

Wireless sensor networks (WSNs) have a wide spectrum of applications, such as disaster relief operations, intelligent building, medicine and health care, etc. WSNs are growing in size and sensory traffic and thus, it is necessary to use multiple sinks to gather such traffic with minimal loss. In a network, there are some locations that nodes visit more often (popular) during their movements. We place sinks' nodes (base stations) on the most popular locations. In this paper, we study the asymptotic throughput-delay performance of a WSN with multiple static sinks utilizing location based popularity rule. Our network is divided into C non-overlapping cells to manage the signal interference between network cells. Also, the partitioning was applied in a way that every cell in the network has an average probability of visit. Moreover, sinks were placed in the most popular cells. According to a modified version of the Grossglauser-Tse 2-hop relay algorithm [1] for information delivery, we derive analytical bounds on throughput capacity and average network delay. We show that by utilizing location popularity rule, network delay has improved significantly, and throughput capacity has increased by a factor of 1.3 compared to randomly distributed sinks over network cells.

In this paper, we present a compressed sensing-based approach, which combines the dictionary learning (DL) method and the approximate message passing (AMP) approach. The approach can be used for efficient communication in the multimedia Internet of Things (IoT). AMP is a signal reconstruction algorithm framework, which can be explained as an iterative denoising process. On the other hand, the DL method seeks an adaptive dictionary for realizing sparse signal representations, and provides good performance in signal denoising. We apply the DL-based denoising method within the AMP algorithm framework and propose a novel DL-AMP framework. We demonstrate our framework's effectiveness for multimedia IoT devices by showing its capability in reducing required communication bandwidth for multimedia communication while improving reconstruction quality (by over 2 dB).

The popularity of online social networks (OSNs) has resulted in them being targeted with Sybil attacks, where an adversary forges many fake identities (called Sybils) to disrupt or control the normal functioning of the system. Several schemes have been proposed to defend against Sybil attacks. Most of these schemes work by computing the landing probability or statistical distribution of visiting frequency of random walks. These schemes usually have high running time cost and are highly dependent upon the proper choice of known trusted nodes. To address these limitations, in this paper we present SybilExposer, an efficient and effective Sybil community detection algorithm, which relies on the properties of social graph communities to rank communities according to their perceived likelihood of being fake or Sybil. Our experiments on several real-world OSN graphs illustrate that SybilExposer has close to 100% true positive rate and nearly zero false positive rate in identifying Sybil communities, and the best running time complexity compared to the state of the art.

Wireless ad hoc networks (WAHNs) consist of autonomous nodes cooperating with each other to transmit/receive data over multiple-hops in the network. Caching is a useful mechanism to leverage this cooperation. Nodes with cached content can satisfy requests from other nodes, thus helping reduce network traffic and energy consumption, and improve latency. With the proliferation of wireless devices on the Internet and the proposal of a future Internet with emphasis on in-network caching, improvements in caching can significantly improve network response while reducing network load. In this paper, we present a holistic caching framework, Split-Cache, which enables a network node to account for the frequency of requests of data items and their presence in the network, and to leverage a split-cache (one part caches popular items and the other caches less popular items) to make caching and cache-eviction decisions. We performed exhaustive simulations to compare Split-Cache with the state-of-the-art: Split-Cache improved the cache request resolution time on an average by 30% (and as high as 72%), and required 15% less average traffic for resolving requests-large savings when considering large number of requests.

In this paper, we present a compressed sensing based framework for a wireless sensor based biological sensing system for recording the frequency of fish electric organ discharge. We investigate the trade-offs between the parameters of compressed sensing, such as sampling matrix, reconstructed signal's signal to noise ratio, and compression ratio. The measured results show that our framework can be used to reduce the transmitted data size by 70% (3×) while maintaining at least 10 dB signal to noise ratio for the reconstructed time domain frequency data. This size reduction with acceptable reconstructed signal quality will help reduce transmission energy and storage requirements for long-term sensing experiments, thus enabling the use of small and low power wireless sensors.

The constrained relay node placement problem in a wireless sensor network seeks the deployment of a minimum number of relay nodes (RNs) in a set of candidate locations in the network to satisfy specific requirements, such as connectivity or survivability. In this paper, we study the constrained relay node placement problem in an energy-harvesting network in which the energy harvesting potential of the candidate locations are known a priori. Our aim is to place a minimum number of relay nodes, to achieve connectivity or survivability, while ensuring that the relay nodes harvest large amounts of ambient energy. We present the connectivity and survivability problems, discuss their NP-hardness, and propose polynomial time${\mbi{\cal O}}$(1)-approximation algorithms with low approximation ratios to solve them. We validate the effectiveness of our algorithms through numerical results to show that the RNs placed by our algorithms harvest 50% more energy on average than those placed by the algorithms unaware of energy harvesting. We also develop a unified-mixed integer linear program (MILP)-based formulation to compute a lower bound of the optimal solution for minimum relay node placement and demonstrate that the results of our proposed algorithms were on average within 1.5 times of the optimal.

Large-scale multi-hop wireless networks have many important applications. However, Gupta and Kumar showed that the capacity of multi-hop wireless networks decreases as the number of nodes in the network increases. Subsequent research efforts to achieve linear capacity scaling have significant limitations such as long latency, high technical complexity, restricted traffic pattern, or infrastructure requirement. We propose to achieve close-to-linear (CTL) capacity scaling through the use of directed energy (DE) links such as laser communications links or highly directional pencil beam links in the EHF band in a hybrid network that also contains traditional omni-directional (OD) antenna links. Our approach has none of limitations mentioned earlier. We show that when the probability distribution of DE links follows the inverse-square law, a distributed scheme with local routing information suffice to achieve CTL capacity scaling.

In this paper, we present a game-theoretic study of the problem of routing in networks with max-min fair congestion control at the link level. The problem is formulated as a noncooperative game, in which each user aims to maximize its own bandwidth by selecting its routing path. We first prove the existence of Nash equilibria. This is important, because at a Nash equilibrium (NE), no user has any incentive to change its routing strategy-leading to a stable state. In addition, we investigate how the selfish behavior of users may affect the performance of the network as a whole. We next introduce a novel concept of observed available bandwidth on each link. It allows a user to find a path with maximum bandwidth under max-min fair congestion control in polynomial time, when paths of other users are fixed. We then present a game-based algorithm to compute an NE and prove that by following the natural game course, the network converges to an NE. Extensive simulations show that the algorithm converges to an NE within 10 iterations and also achieves better fairness compared to other algorithms .

Supercomputers generate vast amounts of data, typically organized into large directory hierarchies on parallel file systems. While the supercomputing applications are parallel, the tools used to process them requiring complete directory traversais, are typically serial. We present an algorithm framework and three fully distributed algorithms for traversing large parallel file systems, and performing file operations in parallel. The first algorithm introduces a randomized work-stealing scheduler; the second improves the first with proximity-awareness; and the third improves upon the second by using a hybrid approach. We have tested our implementation on Cielo, a 1.37 petaflop supercomputer at the Los Alamos National Laboratory and its 7 petabyte file system. Test results show that our algorithms execute orders of magnitude faster than state-of-the-art algorithms while achieving ideal load balancing and low communication cost. We present performance insights from the use of our algorithms in production systems at LANL, performing daily file system operations.

In wireless sensor networks, relay node placement has been proposed to improve energy efficiency. In this paper, we study two-tiered constrained relay node placement problems, where the relay nodes can be placed only at some prespecified candidate locations. To meet the connectivity requirement, we study the connected single-cover problem where each sensor node is covered by a base station or a relay node (to which the sensor node can transmit data), and the relay nodes form a connected network with the base stations. To meet the survivability requirement, we study the 2-connected double-cover problem where each sensor node is covered by two base stations or relay nodes, and the relay nodes form a 2-connected network with the base stations. We study these problems under the assumption that R \ge 2r > 0, where R and r are the communication ranges of the relay nodes and the sensor nodes, respectively. We investigate the corresponding computational complexities, and propose novel polynomial time approximation algorithms for these problems. Specifically, for the connected single-cover problem, our algorithms have {\cal O}(1)-approximation ratios. For the 2-connected double-cover problem, our algorithms have {\cal O}(1)-approximation ratios for practical settings and {\cal O}(\ln n)-approximation ratios for arbitrary settings. Experimental results show that the number of relay nodes used by our algorithms is no more than twice of that used in an optimal solution.

Distributed network protocols operate similar to periodic state machines, utilizing internal states and timers for network coordination, which creates opportunities for carefully engineered radio jamming to target the protocol operating periods and disrupt network communications. Such periodic attacks targeting specific protocol period/frequency of operation is referred to as Null Frequency Jamming (NFJ). Our hypothesis is that NFJ is a pervasive phenomenon in dynamic systems, including wireless ad-hoc networks. This paper aims to test the hypothesis by investigating NFJ targeted at the on-demand routing protocols for ad-hoc networks. Our mathematical analysis and simulation results show substantial degradation in end-to-end network throughput at certain null periods/frequencies, where the jamming periodicity self-synchronizes with the route-recovery cycle. We also study an effective countermeasure, randomized route-recovery periods, for eliminating the presence of predictable null frequencies and mitigating the impact of NFJ. Our analytical model and simulation results validate the effectiveness of randomized route recovery with appropriately chosen randomization ranges.

Solar-power can provide a much needed energy source for wireless sensor networks, which are remotely deployed and limited by the short battery lifetime. A challenge in solar-powered sensor network is that solar power is highly dynamic and volatile: sun light intensity varies significantly with time, with the location of the deployment, the weather conditions, solar panel orientation, and obstacles and shading. Therefore, even if all sensors are equipped with solar panels, individual sensors can receive vastly different amount of solar power and a significant portion of sensors may not receive adequate solar power. This paper addresses such a challenge and introduces a sensor data collection scheme called “Green Diffusion” that automatically adapts sensors data dissemination behavior to the solar power received by the sensors. Performance evaluation shows our scheme significantly reduces sensor battery energy consumption and data latency, even when just a fraction of the nodes receive adequate solar power1.

Distributed network protocols operate similar to periodic state machines, utilizing internal states and timers, for network coordination. This creates opportunities for carefully engineered radio jamming to target the protocol operating periods and disrupt network communications. Such periodic attacks targeting specific protocol period/frequency of operation is referred to as Null Frequency Jamming (NFJ). In this paper, we investigate NFJ targeted at the on-demand route recovery procedure, which is a crucial functionality for ad-hoc network operation. We use DSR as the example routing protocol. Our mathematical analysis and simulation results show substantial degradation in network throughput at certain null frequencies, where the jamming periodicity self-synchronizes with the route recovery cycle. Using simulations, we also demonstrate an effective countermeasure, randomized route-recovery periods, for eliminating the presence of predictable null frequencies and mitigating the impact of NFJ.

Black hole attacks occur when an adversary captures and re-programs a set of nodes in the network to block/drop the packets they receive/generate instead of forwarding them towards the base station. As a result any information that enters the black hole region is captured. Black hole attacks are easy to constitute, and they are capable of undermining network effectiveness by partitioning the network, such that important event information do not reach the base stations. Several techniques based on secret sharing and multipath routing have been proposed in the literature to overcome black hole attacks in the network. However, these techniques are not very effective, and as we demonstrate in this paper, they may even end up making black hole attacks more effective. We propose an efficient technique that uses multiple base stations deployed in the network to counter the impact of black holes on data transmission. Our simulation results demonstrate that our technique can achieve more than 99% packet delivery success. We prove that our scheme can identify 100% of the black hole nodes and demonstrate by simulation results that the technique suffers from very little false positives.

An RFID system generally consists of tags, readers, and backend servers with the readers charged with authenticating/identifying the tags with the help of the servers. Two important enhancements have been suggested for widespread adoption of RFIDs, namely the use of low cost (5¢ or less) passive RFID tags and serverless system design to overcome the need for persistent connection between the readers and the servers. Unfortunately, the low cost tags lack computation and storage capabilities to implement sophisticated security protocols to provide tag privacy and anonymous mutual authentication between the readers and the tags. Although several schemes (including some serverless schemes) have been proposed for authentication between tags and readers, they invariably have stringent computation and storage requirements and cannot be implemented in passive tags. In this paper, we propose SAMA, a novel serverless and anonymous mutual authentication scheme for a system consisting of passive tags and readers. Our scheme uses non-linear feedback shift registers and only logical operations to provide robust and anonymous mutual authentication. We perform security analyses and performance evaluation of SAMA and demonstrate its effectiveness and efficiency in comparison with other popular schemes in the literature. Our scheme requires only three message communications between the tag and the reader. Additionally, it requires only 1393 gates and 70 clock cycles at the tag.

The constrained relay node placement problem In a wireless sensor network is concerned with deploying a minimum number of relay nodes (RNs) in a set of candidate locations in the network to satisfy a specific requirement(s), such as connectivity or survivability. In this paper, we study the constrained relay node placement problem in an energy harvesting network. In such a network, it is imperative that the placement be energy harvesting aware, because the more energy the placed nodes can harvest the more effective the network can be. In our study, the RNs are constrained to be placed at only the candidate locations, where the energy harvesting potential of the locations are known a priori. Our aim is to place a minimum number of relay nodes, to achieve connectivity or survivability, while ensuring that the relay nodes harvest large amounts of ambient energy. For both the connectivity and survivability, we study the problems, prove that they are NP-hard, and propose polynomial time O(1) approximation algorithms with low approximation ratios. We also validate the effectiveness and efficiency of our algorithms through simulations and show that the RNs placed by our algorithms harvest 50% more energy on average, in comparison to those placed by the algorithms unaware of energy harvesting.

In this paper, we propose a new privacy preservation scheme, named pseudonymous authentication-based conditional privacy (PACP), which allows vehicles in a vehicular ad hoc network (VANET) to use pseudonyms instead of their true identity to obtain provably good privacy. In our scheme, vehicles interact with roadside units to help them generate pseudonyms for anonymous communication. In our setup, the pseudonyms are only known to the vehicles but have no other entities in the network. In addition, our scheme provides an efficient revocation mechanism that allows vehicles to be identified and revoked from the network if needed. Thus, we provide conditional privacy to the vehicles in the system, that is, the vehicles will be anonymous in the network until they are revoked, at which point, they cease to be anonymous.

In a sybil attack, the adversary compromises nodes in the network and assigns them multiple fake identities, commonly referred to as sybil identities. Sybil node attacks can be crippling for a wireless sensor network, which operates under the 'majority is right' assumption. As the sybil nodes behave as normal nodes they are hard to identify. With the nodes in the network being able to regulate their transmission power, identification of sybil nodes becomes more difficult. This is because, the existing identification techniques, which depend on localization of the nodes, will localize the transmission power regulating sybil nodes at positions that are different from the positions of their corresponding compromised nodes. Consequently, it is difficult to differentiate the sybil node from a normal node. In this paper, we propose an enhanced RSSI-based technique to identify sybil nodes when they are regulating their transmission power.We also prove a necessary condition on the placement of the SNs in the network to guarantee zero false positives. Simulation results show that our technique is able to identify more than 98% of the sybil nodes in the network on an average, while suffering from very low false positives.

In this paper, we study the problem of maximizing the number of concurrent requests and the problem of minimizing the number of time-slots needed to schedule all requests in wireless networks under the physical interference model. It has been proved that both problems are NP-complete. Thus either approximation algorithms with guaranteed approximation factors or effective heuristics with practically good performances are desirable. We focus on the latter and present simple and effective heuristic algorithms for these two problems. Extensive experiments show that our algorithm for the first problem outperforms the best approximation algorithm by 62%-72% on average, and our two algorithms for the second problem give the best results among existing algorithms.

In this paper, we study the problem of routing in networks with max-min fair congestion control at the link level. The goal of each user is to maximize its own bandwidth by selecting its path. The problem is formulated as a non-cooperative game. We first prove the existence of Nash Equilibria. This is important, because at a Nash Equilibrium (NE), no user has the incentive to change its routing strategy. In addition, we investigate how the selfish behavior of the users may affect the performance of the network as a whole. We next introduce a novel concept of observed available bandwidth on each link. It allows a user to find a path with maximum bandwidth under max-min fair congestion control in polynomial time. We then present a game based algorithm to compute an NE and prove that by following the natural game course the network converges to an NE. Extensive experiments show that the network can converge to an NE in less than 10 iterations and also significantly improves the fairness compared with other algorithms. Our results have the implication for the future routing protocol design.

In a wireless sensor network, short range multihop transmissions are preferred to prolong the network lifetime due to super-linear nature of energy consumption with communication distance. It has been proposed to deploy some relay nodes such that the sensors can transmit the sensed data to a nearby relay node, which in turn delivers the data to the base stations. In general, the relay node placement problems aim to meet certain connectivity and/or survivability requirements of the network by deploying a minimum number of relay nodes. In this paper, we study two-tiered constrained relay node placement problems, where the relay nodes can only be placed at some pre-specified candidate locations. To meet the connectivity requirement, we study the connected single-cover problem where each sensor node is covered by a relay node (to whom the sensor node can transmit data), and the relay nodes form a connected network with the base stations. To meet the survivability requirement, we study the 2-connected double-cover problem where each sensor node is covered by at least two relay nodes, and the relay nodes form a 2-connected network with the base stations. We focus on the computational complexities of the problems, and propose novel polynomial time approximation algorithms for these problems. For the connected single-cover problem, our algorithms have O(1) approximation ratios. For the 2-connected double-cover problem, our algorithms have O(1) approximation ratios for practical settings and O(lnn) approximation ratios for arbitrary settings. Experimental results show that the number of relay nodes used by our algorithms is no more than twice of the number of relay nodes used in an optimal solution.

Fault tolerance techniques have been widely used in wireless sensor networks. Base station placement to maximize the network lifetime has also been well studied. However, limited research has been done on the joint base station placement and fault-tolerant routing problem. To fill this void, we study this problem and present a fully polynomial time approximation scheme in this paper. Our scheme can compute a (1 - ¿)approximation with a running time bounded by a polynomial in 1/¿ and the input size of the instance. Despite our solution is presented for the model where the base station can be placed anywhere, however it can be easily extended to cases where forbidden areas are present or candidate locations for the base station are given. To the best of our knowledge, this paper is the first theoretical result on this problem.

In this paper, we propose SEAS, a novel privacy preserving, anonymous authentication scheme for RFID tags, which allows the tags to use pseudonyms instead of their true identity for authentication. Using SEAS, a tag generates random numbers and uses them to create a pseudonym as its identity for authentication. The pseudonym does not reveal the identity of the tag and the pseudonyms of multiple authentications appear random and uncorrelated to the adversary. A pseudonym can only be deciphered by the back-end authentication authority to identify the tag. No other entity in the network can link the pseudonym to the identity of the tag. Our scheme is efficient, with a tag needing to perform only simple operations such as XOR, bits shifting, bits concatenation, and random number generation. We perform security analysis of our scheme to show its effectiveness against different forms of attacks. We also perform comparison of our scheme with existing schemes in terms of efficiency in the use of resources. Our scheme performs effectively, while at the same time being better than the other popular schemes in the literature in terms of cost and computation efficiency.

In this paper, we study the problem of multi-path routing with bandwidth and delay constraints, which arises in applications for video delivery over bandwidth limited networks. Assume that each link in the network has a bandwidth and a delay. For a given source-destination pair and a bandwidth requirement, we want to find a set of source to destination paths such that the delay of the longest path is minimized while the aggregated bandwidth of the set of paths meets the bandwidth requirement. This problem is NP-hard, and the state of the art is a maximum flow based heuristic. We first construct a class of examples showing that the maximum flow based heuristic could have very bad performance. We then present a fully polynomial time approximation scheme that can compute a (1 + epsiv) -approximation with running time bounded by a polynomial in 1/epsiv and the input size of the instance. Given the NP-hardness of the problem, our approximation scheme is the best possible. We also present numerical results confirming the advantage of our scheme over the current state of the art.

The relay node placement problem for wireless sensor networks is concerned with placing a minimum number of relay nodes into a wireless sensor network to meet certain connectivity and survivability requirements. We study constrained versions of the relay node placement problem, where relay nodes can only be placed at a subset of candidate locations. In the connected relay node placement problem, we want to place a minimum number of relay nodes to ensure the connectivity of the sensor nodes and the base stations. In the survivable relay node placement problem, we want to place a minimum number of relay nodes to ensure the biconnectivity of the sensor nodes and the base stations. For each of the two problems, we discuss its computational complexity, and present a framework of polynomial time O(1) -approximation algorithms with small approximation ratios.

In a wireless network (WN), the wireless devices generally localize themselves with the help of anchors that are pre-deployed in the network. Some of the techniques commonly used for localization are time of arrival (ToA), time difference of arrival (TDoA), angle of arrival (AoA), and time of flight (ToF). In the wireless domain, measurements are susceptible to errors resulting from the nature of the medium, the relatively low precision, and the presence of obstacles, which produce non-line of sight (NLOS) errors. The NLOS errors are a major concern as they could result in significant degradation in accuracy. In this paper, we propose an efficient technique that uses the distance estimates of the device from a group of anchors to localize the device with better accuracy in the presence of NLOS errors. Our technique is based on the notion that in general, for any estimate, the proportion of the NLOS error can be upper bounded. Using this upper bound information our technique reduces the uncertainty in the position of the wireless device that is being localized. The technique is distributed and is simple. In comparison to the standard localization procedure, where localization is done independent of the presence of NLOS errors, our technique uses the information about the NLOS error bounds to improve the accuracy of estimation. Simulation results show that our technique reduces the position error of the wireless device by 40% on an average and by at least 80% in the best case. The uncertainty in localization is also reduced significantly.

In a wireless sensor network (WSN), the sensor nodes (SNs) generally localize themselves with the help of anchors that are pre-deployed in the network. Time of Arrival (ToA) is a commonly used mechanism for SNs localization in WSNs. In ToA, the SNs localize themselves using the positions of the anchors and the time difference between the receipt of a radio and ultrasound signal transmitted by each anchor. In this setting, the localization process has a high risk of being subverted by malicious anchors that lie about their position and/or distance from the SNs. In this paper, we propose an efficient scheme that helps identify and revoke these malicious anchors. We use a mobile verifier (MV) that moves throughout the network, in some pre-determined manner, and obtains multiple location references from each anchor. For each anchor, the MV tests the mean and the variance of the collected sample to identify if the anchor is malicious. We show through simulations that our scheme successfully identifies more than 80% of malicious anchors with less than 60 references from each. Also, the percentage of false positives is close to 0.

Two fundamental functions of the sensor nodes in a wireless sensor network are to sense its environment and to transmit sensed information to a basestation. One approach to prolong sensor network lifetime is to deploy some relay nodes whose main function is to communicate with the sensor nodes, other relay nodes, and the basestations. It is desirable to deploy a minimum number of relay nodes to achieve certain connectivity requirement. In this paper, we study four related fault-tolerant relay node placement problems, each of which has been previously studied only in some restricted form. For each of them, we discuss its computational complexity and present a polynomial time O(1)-approximation algorithm with a small approximation ratio. When the problem reduces to a previously studied form, our algorithm either improves the previous best algorithm or reduces to the previous best algorithm.

In this paper, we study the joint spectrum allocation and scheduling problems with the objectives of maximizing through-put and achieving certain fairness in Dynamic Spectrum Access (DSA) wireless networks. A novel Multi-Channel Contention Graph (MCCG) is proposed to characterize the impact of interference under the protocol interference model. Based on MCCG, we present an optimal scheme to compute maximum throughput solutions. As simply maximizing throughput may result in a severe bias on resource allocation, we take fairness into consideration by presenting optimal schemes to compute fair solutions based on a simplified max-min fairness model and the well-known proportional fairness model. Fast and effective heuristics are also proposed to provide high throughput and fair solutions. Numerical results show that compared with the optimal schemes, our heuristic schemes produce very close performance and our proportional fair schemes achieve a good tradeoff between throughput and fairness. In addition, we extend our research to the physical interference model.

In this paper, we propose a simple and efficient scheme for establishing anonymity in clustered wireless sensor networks. This scheme is applied to a clustered sensor network in which the nodes in a neighborhood share pairwise keys for authentic and confidential communication. The scheme, named Simple Anonymity Scheme (SAS), uses a range of pseudonyms as identifiers for a node in the network, to ensure concealment of its true identifier (ID). After deployment, neighboring nodes in the network share their individual pseudonyms and use them to ensure that the communication is anonymous and that a node's true ID is kept private. Even when many nodes in a given neighborhood of the network are compromised and are colluding, our scheme ensures that non-compromised nodes are still guaranteed complete anonymity. The compromised nodes cannot identify the sender or the receiver of communication happening between non-compromised nodes. Our scheme requires reasonably low memory and has very low computation cost, needing no change in other protocols of the network stack. It can be embedded into any wireless sensor network routing protocol to ensure anonymity and privacy during node discovery and routing in the network.