In graph theory, Katz centrality is a widely used measure to quantify the influence of a vertex within a network. Unlike simple degree centrality, it considers not only immediate neighbors but also multi-hop directed paths, weighting them by length and inter-hop time delays to reflect indirect influence. Traditional computation assumes a non-temporal graph, where edges lack timestamps, and computes using recursive multiplication of the graph’s adjacency matrix. However, this approach becomes impractical for graphs with billions of vertices due to high time/memory demands, and it overlooks the temporal information available on edges. By contrast, we focus on the problem of processing a streaming temporal graph , where edges are timestamped and arrive sequentially at a central analyzer. We want to online estimate the temporal Katz centrality of each vertex, and identify the top- K influential vertices with the largest Katz centralities. To solve this problem, we propose two solutions: TAS-TKC and ATAS-TKC. Both algorithms are designed to operate with a small constant-memory footprint, but ATAS-TKC builds on TAS-TKC to further improve performance. TAS-TKC avoids memory growth with the number of vertices by using a time-adaptive Count-Min sketch that allows all vertices to share memory for centrality estimation. It also maintains the top- K influential vertices using a min-heap-based tracker updated on each edge arrival. Additionally, ATAS-TKC enhances this design in two key ways: First, it achieves O ( 1 ) lookup time for the top- K vertex tracker by augmenting the min-heap with an auxiliary hash table. Second, it improves estimation accuracy by placing the top- K tracker as a prefilter before the sketch. In the prefilter, the top- K influential vertices are allocated dedicated memory and bypass the sketch entirely, avoiding estimation errors caused by memory sharing. For these two proposed solutions, we have conducted extensive evaluation based on real-world graph datasets. The results show that the average estimation error for all vertices is smaller than 4 % and the identification precision for the top- K vertices can be larger than 97 % when given only 400 KB memory to process a million-vertex graph dataset.

In large-scale Internet of Things (IoT) environments, the reliability and security of complex cloud-edge ecosystems critically depend on accurate anomaly detection from system logs. However, most existing methods rely primarily on log templates, often ignoring the diagnostic signals embedded in heterogeneous fields (e.g., timestamps, components, and severity levels). Furthermore, they struggle to learn discriminative representations for rare anomalies due to severe class imbalance, causing models to become biased toward normal patterns. Finally, these approaches often fail to capture the latent structure of unlabeled data, limiting their ability to generalize to unseen anomalies. These limitations render them unreliable in practice. To address the above challenges, we propose LogRMC, a semi-supervised framework for robust log anomaly detection through multi-field log feature fusion, contrastive representation learning, and pseudo-label refinement. First, LogRMC extracts features from diverse log fields and fuses them into unified contextual embeddings that encode inter-field dependencies. Next, it applies contrastive learning on normal samples to learn discriminative and stable representations, thereby improving the separation of normal and anomalous sequence embeddings. To exploit unlabeled data, LogRMC further introduces a cluster-refined pseudo-labeling strategy: it performs density-based clustering on contrastively learned embeddings and applies density ratio estimation within each cluster to generate confidence-aware pseudo-labels. Finally, an attention-based GRU network is trained jointly on labeled and pseudo-labeled log sequences. Extensive experiments on public log datasets demonstrate that LogRMC outperforms state-of-the-art unsupervised and semi-supervised methods, and achieves performance comparable to fully supervised approaches.

In the field of data stream processing, there are two prevalent models, i.e., insertion-only, and turnstile models. Most previous works were proposed for the insertion-only model, which assumes new elements arrive continuously as a stream, and neglects the possibilities of removing existing elements. In this paper, we make a bounded deletion assumption, putting a constraint on the number of deletions allowed. For such a turnstile stream, we focus on a new problem of universal measurement that estimates multiple kinds of statistical metrics simultaneously using limited memory and in an online fashion, including per-element frequency, heavy hitters, frequency moments, and frequency distribution. There are two key challenges for processing a turnstile stream with bounded deletions. Firstly, most previous methods for detecting heavy hitters cannot ensure a bounded detection error when there are deletion events. Secondly, there is still no prior work to estimate the per-element frequency moments under turnstile model, especially in an online fashion. In this paper, we address the former challenge by proposing a Removable Augmented Sketch, and address the latter by a Removable Universal Sketch, enhanced with an Online Moment Estimator. In addition, we improve the accuracy of frequency estimation by a compressed counter design, which can halve the memory cost of a frequency counter and support addition/minus operations. Our experiments show that our solution outperforms other algorithms by 16%~69% in F1 Score of heavy hitter detection, and improves the throughput of frequency moment estimation by 3.0x10 4 times.

Traditionally, a firewall tracks the per-flow spread of each source and destination IP address to detect network scans and DDoS attacks. It is not designed with hierarchical IP addresses in mind. However, cyberattacks nowadays become more stealthy. To evade the detection, they treat a network subnet instead of a single IP as the victim of an attacking campaign. Therefore, we focus on a new problem: online estimation of each hierarchical flow’s cardinality (or spread), in order to detect the hierarchical super-spreaders (HSSs), which correspond to the IP subnet receiving numerous network connections from an extraordinarily large number of source IPs. For detecting such one-dimensional HSSs, the recent work Hierarchical virtual bitmap estimator (HVE) has been proposed. But it fails to handle the two-dimensional HSSs, and it can not be queried online due to its very high query overhead. In this paper, we propose the Hon-vHLL sketch to address these limitations. It is an innovative hierarchical extension of On-vHLL to support the estimation of conditional spreads for either 1D or 2D hierarchical flows. Hon-vHLL allocates an On-vHLL sketch for each hierarchical level bucket and query conditional spread by merging the virtual estimators of hierarchical flows. We evaluate its performance based on CAIDA network traces. The results show that our Hon-vHLL can improve the query throughput by 578 times than HVE, and also achieve 11% higher HSS detection accuracy.

Approximate Membership Query (AMQ) filter is a group of probabilistic data structures, such as Bloom filter and cuckoo filter, which supports approximate set membership queries under constant memory budget and time cost. It has numerous applications in real-world scenarios, such as connection tracking and IP blacklisting for network management and security. However, dynamic datasets are pervasive in practice, with the number of elements fluctuating significantly over time. This requires an AMQ structure to support the run-time memory reallocation for dynamic set representation. Although previous works exist that enhance the cuckoo filter to be memory elastic, most of them only support coarse-grained memory expansion at the filter level or the mini-filter level. We propose a new AMQ filter named BECF (Bucket-level Elastic Cuckoo Filter) that allows fine-grained expansion and shrinkage at the bucket level. BECF combines cuckoo filter with consistent hashing technique, which one-to-one maps the buckets of a cuckoo filter to the segments of a hashring. To allow the number of segments to increase dynamically, BECF splits an arbitrary segment into two child segments, and adopts a segment re-addressing technique that borrows extra bits from element fingerprint to identify the child segment prefix. We also minimize the data movement between the parent and the child segments (or buckets), and preserve all the good properties of cuckoo filter after the expansion. Our experiments show that BECF attains 37% lower memory cost (while holding the same number of elements), 12% higher insertion speed and 20% faster query speed than other designs.

On a high-speed link, there may be tens of millions of IP packets per second and millions of active flows. Maintaining the state of each flow is a fundamental task underlying many network functions, such as load balancing and network anomaly detection. There are two important kinds of per-flow states: per-flow size (e.g., the number of packets received by an arbitrary destination IP) and per-flow cardinality (e.g., the number of distinct source IP addresses that contacted each destination IP). In this paper, we focus on the latter kind of states, and define a new problem: online query of per-flow cardinality, in which we query any given flow’s cardinality entirely on the data plane with low time complexity. For this problem, we propose three solutions named On-vHLL, Ton-vHLL and Aton-vHLL, whose time cost are$O(1)$even for the query operation. Our proposed techniques are three folds. First, we redesign the traditional vHLL with new supplementary data structures called incremental update units (IUUs). When a certain flow’s cardinality is queried, these IUUs can avoid scanning the whole data structure and reduce the time complexity to$O(1)$. Second, we apply a HLL register compression technique called TailCut to the On-vHLL sketch, which can save memory cost by 50%. Third, we add a prefilter based on min-heap, alongside the Ton-vHLL sketch. The prefilter is to give each currently sampled top-$k$superspreader a dedicated HyperLogLog estimator for better accuracy. It can also absorb the superspreaders’ packets bypassing the sketch. We evaluate our new sketches by simulation with CAIDA traces. The results show that our On-vHLL, Ton-vHLL and Aton-vHLL sketches need about 5 memory accesses per packet. The time cost of query operation decreases by hundreds of times than the traditional vHLL that can only be queried offline. Meanwhile, the estimation error of flow spread by our Aton-vHLL is comparable to vHLL.

In computer networks, traffic measurement is a module in a network probe to measure flow-level statistics from an IP packet stream, which are the basis for network performance monitoring and malicious activity detection. This module extracts the flow IDs from incoming IP packets, classifies packets into flows, and counts the number of packets (or bytes) for each flow. It is a great challenge to measure the per-flow statistics for a high-speed network device, using only the size-limited SRAM on its line cards. Therefore, many algorithms using sublinear memory have been proposed, such as CountMin and CountSketch. However, most of previous algorithms are designed for specific measurement tasks. To obtain multiple types of statistics, people have to deploy multiple sketches, which demands more resources of a network device. It is useful to design a universal sketch that can track not only the top-$k$largest individual flows (called heavy hitters) but also the overall traffic distribution statistics (called moments). Prior work named UnivMon successfully tackled this ambitious quest. However, it incurs large and variable per-packet processing overhead, which may result in a significant throughput bottleneck in high-rate packet stream, given that each packet requires 33 hashes and 32 memory accesses on average and many times of that in the worst case. To address this performance issue, we fundamentally redesign the solution architecture from hierarchical sampling to new progressive sampling and from CountSketch to new GenericCM, which ensure that per-packet overhead is a small constant (5 hashes and 8 memory accesses in the worst case), making it more suitable for online operations, especially for hardware pipeline implementation. This new design also makes effort to reduce memory footprint or equivalently improve measurement accuracy under the same memory. Our experiments show that our solution reduces measurement error by roughly 98.1% for second-order moment and by 91.5% for entropy, when given the same 0.2MB memory as UnivMon.

In high-speed networks, flow-level traffic measurement is an essential tool to understand how network bandwidth is being utilized. It can be used to detect anomalous traffic behaviors due to operational or security issues. Perhaps the most important measurement task is to track the heavy hitters (HHs), i.e., the flows occupying the greatest shares of bandwidth. But most existing solutions have no concept of time window: Whenever a measurement period ends, the data sketch, which is deployed in the data plane for monitoring HHs, must be transferred to the control plane and then reset to zeros. It is better to capture network conditions of the continuous recent past by designing a HHs measurement solution that can support time-decaying window. As a result, recently several related works are devoted to tracking the time-decaying heavy hitters, including time-decaying CountMin and time-decaying Space-Saving. However, their memory-accuracy tradeoff is still suboptimal. In this paper, we attain higher performance by proposing a new algorithm named DecayAware Cuckoo Filter along Kicking Path (DAKP-CF). It can be regarded as a variant of cuckoo filter (an improved version of hash table with better memory efficiency), which transforms each bucket into a bucket-level min-heap. Its key advantage is that, when we update the table as a packet arrive, it can discover and replace the most time-decayed flow along the kicking path of a cuckoo filter. We deliberately avoid scanning the entire table to keep the high time efficiency. The experiment results show that our DAKP-CF can reach the same identification accuracy as existing methods with roughly 25% memory cost. In addition, we build a prototype of our DAKP-CF by P4-programmable BMv2 software switch.

Super spreader identification has a lot of applications in network management and security monitoring. It is a more difficult problem than heavy hitter identification because flow spread is harder to measure than flow size due to the requirement of duplicate removal. The prior work either incurs heavy memory overhead or requires heavy computations. This paper designs a new super-spreader monitor capable of identifying all flows whose spreads are greater than a user-specified threshold with a probability that can be arbitrarily set. It introduces a generalized geometric hash function, a generalized geometric counter, and a novel geometric-min filter that blocks out the vast majority of small/medium flows from being tracked, allowing us to focus on a small number of flows in which super spreaders are identified. We provide an analytical way of properly setting the system threshold to meet probabilistically guaranteed identification of super spreaders, and implement it on both hardware (FPGA) and software platforms. We perform extensive experiments based on real Internet traffic traces from CAIDA. The results show that with proper parameter settings, the new monitor can identify more than 99% super spreaders with a low memory requirement, better than the prior art.

Estimating similarity between streaming sets is a fundamental problem with many Internet applications, such as evaluating user similarity in social networks and analyzing similarity of IP hosts' behaviors in communication networks. For a “streaming” data set, its elements arrive in a streaming fashion, and we have only limited memory to process its element stream. To meet the size constraint of high-speed memory, this data set must be stored as a summary called `sketch'. Then, in the distributed scenario, the sketches of all data sets can be efficiently transferred to a central server to calculate the Jaccard similarity between each pair of sets. To balance between memory cost and similarity evaluation accuracy, many sketching methods have been proposed, such as MinHash, virtual odd sketch (VOS) and MaxLogHash. However, both MinHash and MaxLogHash fail to deal with fully dynamic streaming sets that allow the deletion of elements. Although VOS partially solves the deletion problem by adopting the odd sketch structure and enhance it with a physical-virtual structure, its similarity evaluation accuracy will degrade when handling small streaming sets. In this paper, we propose a multi-resolution odd sketch (MROS), which allows more accurate similarity estimation with less memory consumption. Its design is to encode a streaming set into multiple layers of odd sketches with exponentially reducing sampling probabilities. We conduct both experiments and analysis to evaluate our method. Results show that the estimation accuracy of our MROS outperforms existing works, e.g., MinHash and VOS.

In high-speed networks, such as Internet backbone, a router may witness millions of IP packet flows passing through concurrently. Maintaining the state of each flow is a fundamental task underlying many network functions, such as load balancing and network anomaly detection. There are two important kinds of per-flow states: per-flow size (e.g., the number of packets received by an arbitrary destination IP) and per-flow cardinality (e.g., the number of distinct source IP addresses that contacted each destination IP). In this paper, we focus on the latter kind of states, and we propose a new problem: online flow-cardinality query, in which we must query any given flow’s cardinality entirely on the data plane with low time complexity. We propose two solutions named On-vHLL and On-vLLC, whose time cost is $\mathcal{O}(1)$ for the query operation. Our query acceleration techniques are three folds. First, we redesign the traditional vHLL and vLLC with new supplementary data structures called incremental update units. When querying a flow’s cardinality, these units can avoid scanning the whole data structure and reduce the time complexity to $\mathcal{O}(1)$. Second, we adopt LogLogCount estimation formula to avoid floating number calculation. Third, we add a fast path implemented by hash table, alongside the relatively slower On-vHLL or On-vLLC sketch. The fast path can absorb the packets belonging to the top-k superspreaders detected in previous time interval. We evaluate our new sketches by experiments based on CAIDA traffic traces. The results show that our sketches need less than 5 memory accesses per arrival packet. The time cost of our query operation decreases by hundreds of times, and the accuracy of flow cardinality estimation degrades quite modestly by only 20%, as compared with the counterpart vHLL.

Per-flow spread measurement in high-speed networks has many practical applications. It is a more difficult problem than the traditional per-flow size measurement. Most prior work is based on sketches, focusing on reducing their space requirements in order to fit in on-chip cache memory. This design allows the measurement to be performed at the line rate, but it suffers from expensive computation for spread queries (unsuitable for online operations) and large errors in spread estimation for small flows. This paper complements the prior art with a new spread estimator design based on an on-chip/off-chip model. By storing traffic statistics in off-chip memory, our new design faces a key technical challenge to design an efficient online module of non-duplicate sampling that cuts down the off-chip memory access. We first propose a two-stage solution for non-duplicate sampling, which is efficient but cannot handle well a sampling probability that is either too small or too big. We then address this limitation through a three-stage solution that is more space-efficient. Our analysis shows that the proposed spread estimator is highly configurable for a variety of probabilistic performance guarantees. We implement our spread estimator in hardware using FPGA. The experiment results based on real Internet traffic traces show that our estimator produces spread estimation with much better accuracy than the prior art, reducing the mean relative (absolute) error by about one order of magnitude. Moreover, it increases the query throughput by around three orders of magnitude, making it suitable for supporting online queries in real time.

Per-flow spread measurement in high-speed networks has many practical applications. It is a more difficult problem than the traditional per-flow size measurement. Most prior work is based on sketches, focusing on reducing their space requirements in order to fit in on-chip cache memory. This design allows measurement to be performed at the line rate, but it has to accept tradeoff with expensive computation for spread queries (unsuitable for online operations) and large errors in spread estimation for small flows. This paper complements the prior art with a new spread estimator design based on an on-chip/off-chip model which is common in practice. The new estimator supports online queries in real time and produces spread estimation with much better accuracy. By storing traffic data in off-chip memory, our new design faces a key technical challenge of efficient non-duplicate sampling. We propose a two-stage solution with on-chip/off-chip data structures and algorithms, which are not only efficient but also highly configurable for a variety of probabilistic performance guarantees. The experiment results based on real Internet traffic traces show that our estimator reduces the mean relative and absolute error by around one order of magnitude, and achieves both space-efficiency and accuracy-efficiency in flow classification for small flows compared to the prior art.

Traffic measurement is key to many network management tasks such as performance monitoring and cyber-security. Its aim is to inspect the packet stream passing through a network device, classify them into flows according to the header fields, and obtain statistics about the flows. For processing big streaming data in size-limited SRAM of line cards, many space-sublinear algorithms have been proposed, such as CountMin and CountSketch. However, most of them are designed for specific measurement tasks. Implementing multiple independent sketches places burden for online operations of a network device. It is highly desired to design a universal sketch that not only tracks individual large flows (called heavy hitters) but also reports overall traffic distribution statistics (called moments). The prior work UnivMon successfully tackled this ambitious quest. However, it incurs large and variable per-packet processing overhead, which may result in a significant throughput bottleneck in high-rate packet streaming, given that each packet requires 65 hashes and 64 memory accesses on average and many times of that in the worst case. To address this performance issue, we need to fundamentally redesign the solution architecture from hierarchical sampling to new progressive sampling and from CountSketch to new ActiveCM+, which ensure that per-packet overhead is a small constant (4 hash and 4 memory accesses) in the worst case, making it much more suitable for online operations, especially for pipeline implementation. The new design also makes effort to reduce memory footprint or equivalently improve measurement accuracy under the same memory. Our experiments show that our solution incurs just one sixteenth per-packet overhead of UnivMon, while improving measurement accuracy by three times under the same memory.

Determining an object’s spatial pose (including orientation and position) plays a fundamental role in a variety of applications, such as automatic assembly, indoor navigation, and robot driving. In this paper, we design a fine-grained pose sensing system called Tag-Compass that attaches a single tag to an object (whose size may be small) and identifies the tagged object’s pose by determining the spatial orientation and position of the tag. We exploit thepolarizationproperties of the RF waves used in the communications between an RFID reader and the tag on the object. Polarization mismatch between the tag and the reader’s antenna affects the received signal strength at the reader. From the measured signal strength values, we are able to deduce the tag’s pose through a series of transformations and deviation minimization. We propose a system design for Tag-Compass and implement a prototype. We evaluate the performance of Tag-Compass through extensive experiments using the prototype. The experimental results show that Tag-Compass provides accurate estimate of object orientation with a median error of just 2.5° when the tag’s position is known and a median error of 3.8° when the tag’s position is unknown. In the latter case, Tag-Compass will provide an estimate of tag position as a byproduct of orientation sensing, with an accuracy comparable to the state of the art. It is practically appealing to find both the orientation and the position of an object using a single method, instead of having to deploy two different methods.

Cardinality estimation is the task of determining the number of distinct elements (or the cardinality) in a data stream, under a stringent constraint that the input data stream can be scanned by just one single pass. This is a fundamental problem with many practical applications, such as traffic monitoring of high-speed networks and query optimization of Internet-scale database. To solve the problem, we propose an algorithm named HLL-TailCut, which implements the estimation standard error 1.0/√m using the memory units of four or three bits each, whose cost is much smaller than the five-bit memory units used by HyperLogLog, the best previously known cardinality estimator. This makes it possible to reduce the memory cost of HyperLogLog by 20%~45%. For example, when the target estimation error is 1.1%, state-of-the-art HyperLogLog needs 5.6 kilobytes memory. By contrast, our new algorithm only needs 3 kilobytes memory consumption for attaining the same accuracy. Additionally, our algorithm is able to support the estimation of very large stream cardinalities, even on the Tera and Peta scale.

In RFID-enabled applications, when a tag is put into use and associated with a specific object, the category-related information (e.g., the brands of clothes) about this object might be preloaded into the tag’s memory for the purpose of live query. Since such information reflects category attributes, all tags in the same category carry identical category information. To collect this information, we do not need to repeatedly interrogate each tag; one tag’s response in a category is sufficient. In this paper, we investigate the problem of category information collection in a multi-category RFID system, which is referred to asinformation sampling. We propose two time-efficiency protocols. The first is a two-phase sampling protocol (TPS) that works in the case of knowing tag IDs. By quickly zooming into a category and isolating a tag from this category, TPS is able to sample a category with small overhead. The second protocol, called back-and-forth sampling protocol (BFS), relaxes a key assumption in TPS and performs the sampling task efficiently without knowing any tag IDs or category IDs. By carrying out a step-forward frame and using the step-backward scheme, BFS is able to interrogate only 1.45 tags (close to the lower bound of one tag) on average for each category. We theoretically analyze the protocol performance of TPS and BFS and discuss the optimal parameter settings that minimize the overall execution time. Extensive simulations show that both the protocols outperform the benchmark, greatly improving the sampling performance.

Radio frequency identification (RFID) technology has rich applications in cyber-physical systems, such as warehouse management and supply chain control. Often in practice, tags are attached to objects belonging to different groups, which may be different product types/manufacturers in a warehouse or different book categories in a library. As RFID technology evolves from single-group to multiple-group systems, there arise several interesting problems. One of them is to identify the popular groups, whose numbers of tags are above a pre-defined threshold. Another is to estimate arbitrary moments of the group size distribution, such as sum, variance, and entropy for the sizes of all groups. In this paper, we consider a new problem which is to estimate all these statistical metrics simultaneously in a time-efficient manner without collecting any tag IDs. We solve this problem by a protocol named generic moment estimator (GME), which allows the tradeoff between estimation accuracy and time cost. According to the results of our theoretical analysis and simulation studies, this GME protocol is several times or even orders of magnitude more efficient than a baseline protocol that takes a random sample of tag groups to estimate each group size.

Radio-frequency identification (RFID) technology has been widely adopted in various industries and people's daily lives. This paper studies a fundamental function of spatial-temporal joint cardinality estimation in distributed RFID systems. It allows a user to make queries over multiple tag sets that are present at different locations and times in a distributed tagged system. It estimates the joint cardinalities of those tag sets with bounded error. This function has many potential applications for tracking product flows in large warehouses and distributed logistics networks. The prior art is either limited to jointly analyzing only two tag sets or is designed for a relative accuracy model, which may cause unbounded time cost. Addressing these limitations, we propose a novel design of the joint cardinality estimation function with two major components. The first component is to record snapshots of the tag sets in a system at different locations and periodically, in a time-efficient way. The second component is to develop accurate estimators that extract the joint cardinalities of chosen tag sets based on their snapshots, with a bounded error that can be set arbitrarily small. We formally analyze the bias and variance of the estimators, and we develop a method for setting their optimal system parameters. The simulation results show that, under predefined accuracy requirements, our new solution reduces time cost by multiple folds when compared with the existing work.

Software-defined networking (SDN) is one of the most prevailing networking paradigms in current and next-generation networks. Basically, the highly featured separation of control and data planes makes SDN a proper solution towards many practical problems that challenge legacy networks, for example, energy efficiency, dynamic network configuration, agile network measurement, and flexible network deployment. Although the SDN and its applications have been extensively studied for several years, the research of SDN security is still in its infancy. Typically, the SDN suffers from architecture defect and OpenFlow protocol loopholes such as single controller problem, deficiency of communication verification, and network resources constraint. Hence, network measurement is a fundamental technique of protecting SDN against the above security threats. Specifically, network measurement aims to understand and quantify a variety of network behaviors to facilitate network management and monitoring, anomaly detection, network troubleshooting, and the establishment of security mechanisms. In this paper, we present a systematic survey on security-aware measurement technology in SDN. In particular, we first review the basic architecture of SDN and corresponding security challenges. Then, we investigate two performance measurement techniques in SDN, namely, link latency and available bandwidth measurements. After that, we further provide a general overview of topology measurement in SDN including intradomain and interdomain topology discovering techniques. Finally, we list three interesting future directions of security-aware measurement in SDN followed by giving conclusion remarks.

Cardinality estimation is the task of determining the number of distinct elements (or the cardinality) in a data stream, under a stringent constraint that the input data stream can be scanned by just a single pass. This is a fundamental problem with many practical applications, such as traffic monitoring of high-speed networks and query optimization of Internetscale database. To solve the problem, we propose an algorithm named HLL-TailCut+, which implements the estimation standard error 1.0/√m using the memory units of three bits each, whose cost is much smaller than the five-bit memory units used by HyperLogLog, the best previously known cardinality estimator. This makes it possible to reduce the memory cost of HyperLogLog by 45%. For example, when the target estimation error is 1.1%, state-of-the-art HyperLogLog needs 5.6 kilobytes memory. By contrast, our new algorithm only needs 3 kilobytes memory consumption for attaining the same accuracy. Additionally, our algorithm is able to support the estimation of very large stream cardinalities, even on the Tera and Peta scale.

Energy saving solutions on smartphone devices can greatly extend a smartphone's lasting time. However, today's push services require keep-alive connections to notify users of incoming messages, which cause costly energy consuming and drain a smartphone's battery quickly in cellular communications. Most keep-alive connections force smartphones to frequently send heartbeat packets that create additional energy-consuming radio-tails. No previous work has addressed the high-energy consumption of keep-alive connections in smartphones push services. In this paper, we propose Single Connection Proxy (SCoP) system based on fog computing to merge multiple keep-alive connections into one, and push messages in an energy-saving way. The new design of SCoP can satisfy a predefined message delay constraint and minimize the smartphone energy consumption for both real-time and delay-tolerant apps. SCoP is transparent to both smartphones and push servers, which does not need any changes on today's push service framework. Theoretical analysis shows that, given the Poisson distribution of incoming messages, SCoP can reduce the energy consumption by up to 50%. We implement SCoP system, including both the local proxy on the smartphone and remote proxy on the “Fog”. Experimental results show that the proposed system consumes 30% less energy than the current push service for real-time apps, and 60% less energy for delay-tolerant apps.

Radio frequency identification (RFID) technology has been widely used in Applications, such as inventory control, object tracking, and supply chain management. In this domain, an important research problem is called RFID cardinality estimation, which focuses on estimating the number of tags in a certain area covered by one or multiple readers. This paper extends the research in both temporal and spatial dimensions to provide much richer information about the dynamics of distributed RFID systems. Specifically, we focus on estimating the cardinalities of the intersection/differences/union of two arbitrary tag sets (called joint properties for short) that exist in different spatial or temporal domains. With many practical applications, there is, however, little prior work on this problem. We will propose a joint RFID estimation protocol that supports adaptive snapshot construction. Given the snapshots of any two tag sets, although their lengths may be very different depending on the sizes of tag sets they encode, we design a way to combine their information and more importantly, derive closed-form formulas to use the combined information and estimate the joint properties of the two tag sets, with an accuracy that can be arbitrarily set. By formal analysis, we also determine the optimal system parameters that minimize the execution time of taking snapshots, under the constraints of a given accuracy requirement. We have performed extensive simulations, and the results show that our protocol can reduce the execution time by multiple folds, as compared with the best alternative approach in literature.

For many practical applications, it is a fundamental problem to estimate the flow cardinalities over big network data consisting of numerous flows (especially a large quantity of mouse flows mixed with a small number of elephant flows, whose cardinalities follow a power-law distribution). Traditionally the research on this problem focused on using a small amount of memory to estimate each flow's cardinality from a large range (up to ${10}^{{9}}$ ). However, although the memory needed for each individual flow has been greatly compressed, when there is an extremely large number of flows, the overall memory demand can still be very high, exceeding the availability under some important scenarios, such as implementing online measurement modules in network processors using only on-chip cache memory. In this paper, instead of allocating a separated data structure (called estimator) for each flow, we take a different path by viewing all the flows together as a whole: Each flow is allocated with a virtual estimator, and these virtual estimators share a common memory space. We discover that sharing at the multi-bit register level is superior than sharing at the bit level. We propose a unified framework of virtual estimators that allows us to apply the idea of sharing to an array of cardinality estimation solutions, e.g., HyperLogLog and PCSA, achieving far better memory efficiency than the best existing work. Our experiment shows that the new solution can work in a tight memory space of less than 1 bit per flow or even one tenth of a bit per flow - a quest that has never been realized before.

RFID technology has been widely adopted for real-world applications, such as warehouse management, logistic control, and object tracking. This paper focuses on a new angle of applying RFID technology-monitoring the temporal change of a tag set in a certain region, which is called churn estimation. This problem is to provide quick estimations on the number of new tags that have entered a monitored region, and the number of pre-existing tags that have departed from the region, within a predefined time interval. The traditional cardinality estimator for a single tag set cannot be applied here, and the conventional tag identification protocol that collects all tag IDs takes too much time, especially when the churn estimation needs to perform frequently to support real-time monitoring. This paper will take a new solution path, in which a reader periodically scans the tag set in a region to collect their compressed aggregate information in the form of empty/singleton/collision time slots. This protocol can reduce the time cost of attaining pre-set accuracy by at least 35%, when comparing with a previous work that uses only the information of idle/busy slots. Such a dramatic improvement is due to our awareness of collision slot state and the full utilization of slot state changes. Our proposed churn estimator, as shown by the extensive analysis and simulation studies, can be configured to meet any pre-set accuracy requirement with a statistical error bound that can be made arbitrarily small.

Per-flow traffic measurement is a fundamental problem in the era of big network data, providing critical information for many practical applications including capacity planning, traffic engineering, data accounting, resource management, and scan/intrusion detection in modern computer networks. It is challenging to design highly compact data structures for approximate per-flow measurements. In this paper, we show that a highly compact virtual counter architecture can achieve fast processing speed (slightly more than 1 memory access per packet) and provide accurate measurement results under tight memory allocation. Extensive experiments based on real network trace data demonstrate its superior performance over the best existing work.

Radio-frequency identification (RFID) technologies have been widely used in many applications, including inventory management, supply chain, product tracking, transportation, logistics, etc. Tag estimation, which is to estimate the cardinality of a single tag set, is an important research topic. This paper expands the estimation research as follows: It performs joint estimation between two tag sets (which exist at different locations or at the same location but different times). More importantly the estimation is fine-grained in an effort to accommodate common practical scenarios, where each tag set consists of tags belonging to different categories. For any two given tag sets, we want to know the detailed information about the joint property of each category, instead of just the aggregate information of the whole sets. Furthermore, due to the open nature of RFID communications, it is often desirable that tag estimation can be performed in an anonymous way without revealing the tags' ID information. To support these requirements, we develop a new technique called mask bitmap that can encode a tag set without requiring the tags to report their IDs or category IDs. Any two mask bitmaps of different tag sets can be combined to perform category-level joint estimation. Through formal analysis, we determine how to set system parameters to meet a given accuracy requirement that can be arbitrarily set. Extensive simulation results confirm that the proposed solution can yield accurate category-level estimates in an efficient way, and preserve tags' anonymity as well.

Radio-frequency identification (RFID) technologies have been widely used in many applications. Tag estimation, which is to estimate the cardinality of a single tag set, is an important research topic. This paper expands the estimation research as follows: It performs joint estimation between two tag sets, and more importantly the estimation is fine-grained in an effort to accommodate common practical scenarios, where each tag set consists of tags belonging to different categories. For any two given tag sets, we want to know the detailed information about the joint property of each category, instead of just the aggregate information of the whole sets. Furthermore, due to the open nature of RFID communications, it is often desirable that category-level joint estimation can be performed in an anonymous way without revealing the tags' IDs. To support these requirements, we develop a new technique called mask bitmap that can encode a tag set without requiring the tags to report their IDs or category IDs. Any two mask bitmaps that encode different tag sets can be combined to perform category-level joint estimation. Simulation results confirm that the proposed solution can yield accurate category-level estimates and preserve tags' anonymity.

Radio-frequency identification (RFID) technology has been widely adopted by real-world industries. This paper presents a new application for distributively deployed RFID systems, wherein a user chooses multiple tag sets at will from different spatial or temporal domains, and then connects them by set operators (union, intersection and relative complement) to form a set expression. The user is allowed to query for the cardinality of an arbitrary set expression, which is called the joint property of multiple sets. We focus on the problem of estimating the joint property with bounded error, which has many potential applications. One of them is to allow users to check the number of tags in an arbitrary tag flow passing through a distributed RFID system. For this problem, we propose a solution with a novel design that supports versatile snapshot construction: Given the snapshots of multiple tag sets, although their lengths may be very different, our formulas can estimate their joint properties, with an accuracy that can be arbitrarily set. For the proposed estimator, we formally analyze its bias and variance, and also the optimal settings of protocol parameters to minimize the time cost of taking a snapshot of a tag set. The simulation results show that, under predefined accuracy requirement, our solution can reduce time cost by multiple folds as compared with existing works named DiffEstm and CCF, which require all tag sets must be encoded into snapshots with an equal length.

In this paper, we consider an important problem of privacy-preserving point-to-point traffic volume measurement in vehicular cyber physical systems (VCPS), whose focus is utilizing VCPS to enable automatic traffic data collection, and measuring point-to-point traffic volume while preserving the location privacy of all participating vehicles. The novel scheme that we propose tackles the efficiency, privacy, and accuracy problems encountered by previous solutions. Its applicability is demonstrated through both mathematical and numerical analysis. The simulation results also show its superior performance.

Radio-frequency identification (RFID) technology has been widely used in applications such as inventory control, object tracking, supply chain management. An important research is to estimate the number of tags in a certain area covered by readers. This paper extends the research in both temporal and spatial dimensions to provide much richer information for monitoring the dynamics of distributed RFID systems. More specifically, we are interested in estimating the joint properties of any two snapshots taken at arbitrary locations and arbitrary times in a system. With many practical applications, there is however little prior work on this problem. We propose a joint RFID estimation protocol based on a simple yet versatile snapshot construction. Given the snapshots of any two tag sets, although their sizes may be very different, we design a way to combine their information and more importantly derive formulas to extract the joint properties of the two tag sets from the combined information, with an accuracy that can be arbitrarily set. Through formal analysis, we determine the optimal system parameters that minimize the execution time of taking snapshots, under the constraints of a given accuracy requirement. Our simulation results show that the proposed protocol can reduce the execution time by multifold when comparing with the best alternative approach in the literature.

Cardinality estimation over big network data consisting of numerous flows is a fundamental problem with many practical applications. Traditionally the research on this problem focused on using a small amount of memory to estimate each flow's cardinality from a large range (up to $10^9$). However, although the memory needed for each flow has been greatly compressed, when there is an extremely large number of flows, the overall memory demand can still be very high, exceeding the availability under some important scenarios, such as implementing online measurement modules in network processors using only on-chip cache memory. In this paper, instead of allocating a separated data structure (called estimator) for each flow, we take a different path by viewing all the flows together as a whole: Each flow is allocated with a virtual estimator, and these virtual estimators share a common memory space. We discover that sharing at the register (multi-bit) level is superior than sharing at the bit level. We propose a framework of virtual estimators that allows us to apply the idea of sharing to an array of cardinality estimation solutions, achieving far better memory efficiency than the best existing work. Our experiment shows that the new solution can work in a tight memory space of less than 1 bit per flow or even one tenth of a bit per flow --- a quest that has never been realized before.

Data security is a major concern in cloud computing. After clients outsource their data to the cloud, will they lose control of the data? Prior research has proposed various schemes for clients to confirm the existence of their data on the cloud servers, and the goal is to ensure data integrity. This paper investigates a complementary problem: When clients delete data, how can they be sure that the deleted data will never resurface in the future if the clients do not perform the actual data removal themselves? How to confirm the non-existence of their data when the data is not in their possession? One obvious solution is to encrypt the outsourced data, but this solution has a significant technical challenge because a huge amount of key materials may have to be maintained if we allow fine-grained deletion. In this paper, we explore the feasibility of relieving clients from such a burden by outsourcing keys (after encryption) to the cloud. We propose a novel multi-layered key structure, called Recursively Encrypted Red-black Key tree (RERK), that ensures no key materials will be leaked, yet the client is able to manipulate keys by performing tree operations in collaboration with the servers. We implement our solution on the Amazon EC2. The experimental results show that our solution can efficiently support the deletion of outsourced data in cloud computing.

The persistent spread of a destination host is the number of distinct sources that have contacted it persistently in predefined t measurement periods. A persistent spread estimator is a software/hardware component on a router that inspects the arrival packets and estimates the persistent spread of each destination. This is a new primitive for network measurement that can be used to detect long-term stealthy malicious activities, which cannot be recognized by the traditional super spreader detectors that are designed only for "elephant" activities. However, the challenge is to function such an estimator in fast but small memory space (such as on-chip SRAM of line cards), in order to keep up with the high speed of switching fabric for packet forwarding. This paper presents an implementation that can use very tight memory space to deliver high estimation accuracy: Its memory expense is less than one bit per flow element in each time period, Its estimation accuracy is over 90% better than a continuous variant of Flajolet-Martin sketches, Its operating range to produce effective measurements is hundreds of times broader than the traditional bitmap. These advantages originate from a new data structure called multi-virtual bitmap, which is designed to estimate the cardinality of the intersection of an arbitrary number of sets. We have verified the effectiveness of our new estimator using the real network traffic traces from CAIDA.

The ubiquitous use of RFID tags raises concern about potential security risks in RFID systems. Because low-cost tags are extremely resource-constrained devices, common security mechanisms adopted in resource-rich equipment such as computers are no longer applicable to them. Hence, one challenging research topic is to design a lightweight cipher that is suitable for low-cost RFID tags. Traditional cryptography generally assumes that the two communicating parties are equipotent entities. In contrast, there is a large capability gap between readers and tags in RFID systems. We observe that the readers, which are much more powerful, should take more responsibility in RFID cryptographic protocols. In this paper, we make a radical shift from traditional cryptography, and design a novel cipher called Pandaka1, in which most workload is pushed to the readers. As a result, Pandaka is particularly hardware-efficient for tags. We perform extensive simulations to evaluate the effectiveness of Pandaka. In addition, we present security analysis of Pandaka facing different attacks.

BitTorrent (BT) is one of the most common Peer-to-Peer (P2P) file sharing protocols. Rather than downloading a file from a single source, the protocol allows users to join a swarm of peers to download and upload from each other simultaneously. Worms exploiting information from BT servers or trackers can cause serious damage to participating peers, which unfortunately has been neglected previously. In this article, we first present a new worm, called Adaptive BitTorrent worm (A-BT worm), which finds new victims and propagates sending forged requests to trackers. To reduce its abnormal behavior, the worm estimates the ratio of infected peers and adaptively adjusts its propagation speed. We then build a hybrid model to precisely characterize the propagation behavior of the worm. We also propose a statistical method to automatically detect the worm from the tracker by estimating the variance of the time intervals of requests. To slow down the worm propagation, we design a safe strategy in which the tracker returns secured peers when receives a request. Finally, we evaluate the accuracy of the hybrid model, and the effectiveness of our detection method and containment strategy through simulations.

In wireless sensor networks, an important research problem is to use a few anchor nodes with known locations to derive the locations of other nodes deployed in the sensor field. A category of solutions for this problem is the iterative localization, which sequentially merges the elements in a network to finally locate them. Here, a network element is different from its definition in iterative trilateration. It can be either an individual node or a group of nodes. For this approach, we identify a new problem called inflexible body merging, whose objective is to align two small network elements and generate a larger element. It is more generalized than the traditional tools of trilateration and patch stitching and can replace them as a new merging primitive. We solve this problem and make the following contributions. Our primitive can tolerate ranging noise when merging two network elements. It adopts an optimization algorithm based on rigid body dynamics and relaxing springs. Our primitive improves the robustness against flip ambiguities. It uses orthogonal regression to detect the rough collinearity of nodes in the presence of ranging noise, and then enumerate flip ambiguities accordingly. We present a condition to indicate when we can apply this primitive to align two network elements. This condition can unify previous work and thus achieve a higher percentage of localizable nodes. All the declared contributions have been validated by both theoretical analysis and simulation results.

Tomography imaging, applied to seismology, requires a new, decentralized approach if high resolution calculations are to be performed in a sensor network configuration. The real-time data retrieval from a network of large-amount wireless seismic nodes to a central server is virtually impossible due to the sheer data amount and resource limitations. In this paper, we present a distributed multi-resolution evolving tomography algorithm for processing data and inverting volcano tomography in the network, while avoiding costly data collections and centralized computations. The new algorithm distributes the computational burden to sensor nodes and performs real-time tomography inversion under the constraints of network resources. We implemented and evaluated the system design in the CORE emulator. The experiment results validate that our proposed algorithm not only balances the computation load, but also achieves low communication cost and high data loss-tolerance.

Efficient estimation of tag population in RFID systems has many important applications. In this paper, we present a new problem called differential cardinality estimation, which tracks the population changes in a dynamic RFID system where tags are frequently moved in and out. In particular, we want to provide quick estimation on (1) the number of new tags that are moved in and (2) the number of old tags that are moved out, between any two consecutive scans of the system. We show that the traditional cardinality estimators cannot be applied here, and the tag identification protocols are too expensive if the estimation needs to be performed frequently in order to support real-time monitoring. This paper presents the first efficient solution for the problem of differential cardinality estimation. The solution is based on a novel differential estimation framework, and is named zero differential estimator. We show that this estimator can be configured to meet any pre-set accuracy requirement, with a probabilistic error bound that can be made arbitrarily small.

Tomography imaging, applied to seismology, requires a new, decentralized approach if high resolution calculations are to be performed in a sensor network configuration. The real-time data retrieval from a network of large-amount wireless seismic nodes to a central server is virtually impossible due to the sheer data amount and resource limitations. In this paper, we present a distributed multi-resolution evolving tomography algorithm for processing data and inverting volcano tomography in the network, while avoiding costly data collections and centralized computations. The new algorithm distributes the computational burden to sensor nodes and performs real-time tomography inversion under the constraints of network resources. We implemented and evaluated the system design in the CORE emulator. The experiment results validate that our proposed algorithm not only balances the computation load, but also achieves low communication cost and high data loss tolerance.1

SUMMARY As radio frequency identification (RFID) tags become more ubiquitously available, they will stay in dynamic environments where tags can freely enter or leave RFID readers' interrogation range. With such a dynamic tag population, there arises a problem of population monitoring, whose purpose is to identify themissing tagsthat have departed from the reading range and thenew tagsthat have newly entered. This problem is a new problem which cannot be well solved by the conventional tag identification protocols. In this paper, we first show that this traditional approach is inefficient, because it collects all the tag IDs in each scan and ignores the ready‐for‐use knowledge of the tag population in a previous scan. To be more efficient, we present three protocols: (i) a baseline protocol that improves the traditional tag identification protocol by optimizing its length of random number used for collision detection; (ii) a novel one‐phase protocol with easy labor to identify exactly the new tags and the missing tags by fully utilizing the knowledge of previous tag population; and (iii) a hybrid protocol that smartly combines the baseline protocol and the one‐phase protocol. Its purpose is to deal with the situation that the knowledge of previous tag population is highly inconsistent with the current tag population. This hybrid protocol, as shown by our analysis, can improve the tag monitoring accuracy by 25%, and improve the time efficiency by 55.3%, as compared with a recent work (called two‐phase protocol), which also identifies the population changes. Copyright © 2012 John Wiley & Sons, Ltd.

In wireless sensor networks, a critical system service is the localization service that determines the locations of geographically distributed sensor nodes. The raw data used by this service are the distance measurements between neighboring nodes and the position knowledge of anchor nodes. However, these raw data may contain outliers that strongly deviate from their true values, which include both the outlier distances and the outlier anchors. These outliers can severely degrade the accuracy of the localization service. Therefore, we need a robust localization algorithm that can reject these outliers. Previous studies in this field mainly focus on enhancing multilateration with outlier rejection ability, since multilateration is a primitive operation used by localization service. But patch merging, a powerful operation for increasing the percentage of localizable nodes in sparse networks, is almost neglected. We thus propose a robust patch merging operation that can reject outliers for both multilateration and patch merging. Based on this operation, we further propose a robust network localization algorithm called RobustLoc . This algorithm makes two major contributions. (1) RobustLoc can achieve a high percentage of localizable nodes in both dense and sparse networks. In contrast, previous methods based on robust multilateration almost always fail in sparse networks with average degrees between 5 and 7. Our experiments show that RobustLoc can localize about 90% of nodes in a sparse network with 5.5 degrees. (2) As far as we know, RobustLoc is the first to uncover the differences between outlier distances and outlier anchors. Our simulations show that RobustLoc can reject colluding outlier anchors reliably in both convex and concave networks.

Radio-Frequency Identification (RFID) technology brings many innovative applications. Of great importance to RFID applications in production economics is misplaced-tag pinpointing (MTP), because misplacement errors fail optimal inventory placement and thus significantly decrease profit. The existing MTP solution [1], originally proposed from a data-processing perspective, collects and processes a large amount of data. It suffers from time inefficiency (and energy-inefficiency as well if active tags are in use). The problem of finding efficient solutions for the MTP problem from the communication protocol design perspective has never been investigated before. In this paper, we propose a series of protocols toward efficient MTP solutions in large RFID systems. The proposed protocols detect misplaced tags using reader positions instead of tag positions to guarantee the efficiency and scalability as system scale grows, because RFID readers are much fewer than tags. Considering applications that employ active tags, we further propose a solution requiring responses from only a subset of tags in favor of energy saving. We also design a distributed protocol that enables each reader to independently detect misplaced tags. We then investigate how to apply the proposed protocols in scenarios with tag mobility. To evaluate the proposed protocols, we analyze their optimal performances to demonstrate their efficiency potential and also conduct extensive simulation experiments. The results show that the proposed protocols can significantly increase the time efficiency and the energy efficiency by over 70 percent on average when compared with the best existing work.

As RFID tags become more ubiquitously available, e.g., in a supermarket, it is necessary to monitor larger-scale tag populations in a dynamic environment to get updated tag information. This paper considers the problem of monitoring a dynamic tag population, to identify both the missing tags and new tags. Traditional approach can solve the problem by collecting all tag IDs in the current population, which could be slow because it ignores the knowledge of the tag population in a previous scan. To be more efficient, this paper presents two protocols: (1) a baseline protocol with optimized length of random number bits, (2) an improved one-phase protocol with easy labor to identify only the new and missing tags in ALOHA frames by fully utilizing previous tag population knowledge. Our analysis shows that the one-phase protocol can improve the monitoring accuracy by 25% and improve the time efficiency by 55%, as compared with the two-phase protocol proposed in a recent paper which also identifies population changes.

With the development of various wireless personal area networks (WPANs), the issue of security has become a crucial problem for their applications. Jamming is one of the most important methods of attack to deprive or reduce the communication service of WPANs. Most existing jamming attacks can cause negative interference, but the attack strategies are usually not adjusted against the countermeasures that are currently taken. This paper proposes an effective dynamic jamming attack (EDJam) in an 802.15.4-compliant WPAN. In this attack, a jammer who is aware of a change in the network defense strategy, e.g. the use of a dynamic retransmission mechanism, may choose a better strategy to make more damage to the network with less cost. Similarly, a well-protected network can change its defense strategy against the EDJam. This procedure of competition between the EDJam attacker and defending networks is modeled and formulated as a Stackelberg game, and a unique Nash Equilibrium point is derived in analytical format. Based on an equilibrium analysis, we discuss the condition under which a defense strategy will increase the utility of the network and a dynamic retransmission mechanism defense strategy is proposed accordingly. The simulation results show that EDjam can be more cost-efficient than continuous, random and fixed-period jamming.

The Radio-Frequency Identification (RFID) technology has stimulated many innovative applications. Misplaced-tag pinpointing (MTP) is important to RFID applications in production economics because optimal inventory placement can significantly increase profit. Previous research from the database perspective needs to process a large amount of data which is time-consuming to collect (and energy-consuming if active tags are used). How to efficiently address the MTP problem from the protocol design perspective however has not been investigated. In this paper, we propose a series of protocols toward efficient MTP solution in large RFID systems. The proposed protocols detect misplaced tags based on reader positions instead of tag positions to guarantee the efficiency and scalability as system scale grows, because the number of readers is much smaller than that of tags. Considering applications to employ more and more popular active tags, we further propose a solution requiring responses from only partial tags in favor of energy saving. We analyze the optimal performances of proposed protocols to demonstrate their efficiency potential and conduct extensive simulation experiments to evaluate their performance under various scenarios. The results show that the proposed protocols can significantly increase the time efficiency and the energy efficiency by over 70% on average when compared with the state of the art.

Localization is a fundamental problem in wireless sensor networks and its accuracy impacts the efficiency of location-aware protocols and applications, such as routing and storage. Most previous localization algorithms assume that sensors are distributed in regular areas without holes or obstacles, which often does not reflect real-world conditions, especially for outdoor deployment of wireless sensor networks. In this paper, we propose a novel scheme called reliable anchor-based localization (RAL), which can greatly reduce the localization error due to the irregular deployment areas. We first provide theoretical analysis of the minimum hop length for uniformly distributed networks and then show its close approximation to empirical results, which can assist in the construction of a reliable minimal hop-length table offline. Using this table, we are able to tell whether a path is severely detoured and compute a more accurate average hop length as the basis for distance estimation. At runtime, the RAL scheme 1) utilizes the reliable minimal hop length from the table as the threshold to differentiate between reliable anchors and unreliable ones, and 2) allows each sensor to determine its position utilizing only distance constraints obtained from reliable anchors. The simulation results show that RAL can effectively filter out unreliable anchors and therefore improve the localization accuracy.

This paper focuses on multihop range-free localization in anisotropic wireless sensor networks. In anisotropic networks, geometric distance between a pair of sensor nodes is not always proportional to their hop count distance, which undermines the assumption of many existing range-free localization algorithms. To tolerate network anisotropy, we propose a pattern-driven localization scheme, which is inspired by the observation that in an anisotropic network the hop count field propagated from an anchor exhibits multiple patterns, under the interference of multiple anisotropic factors. Our localization scheme therefore for different patterns adopts different anchor-sensor distance estimation algorithms. The average anchor-sensor distance estimation accuracy of our scheme, as demonstrated by both theoretical analysis and extensive simulations, is improved to be better than 0.4r when the average sensor density is above eight, and the sensor localization accuracy thus is approximately better than 0.5r. This localization accuracy can satisfy the needs of many location-dependent protocols and applications, including geographical routing and tracking. Compared with previous localization algorithms that declares to tolerate network anisotropy, our localization scheme excels in 1) higher accuracy stemming from its ability to tolerate multiple anisotropic factors, including the existence of obstacles, sparse and nonuniform sensor distribution, irregular radio propagation pattern, and anisotropic terrain condition, 2) localization accuracy guaranteed by theoretical analysis, rather than merely by simulations, and 3) a distributed solution with less communication overhead and enhanced robustness to different network topologies.

Worm propagation analysis, including exploring mechanisms of worm propagation and formulating effects of network/worm parameters, has great importance for worm containment and host protection in P2P networks. Previous work only focuses on topological worm propagation where worms search a hosts neighbor-list to find new victims. In BitTorrent (BT) networks, the information from servers or trackers, however, could be fully exploited to design effective worms. In this paper, we propose a new approach for worm propagation in BT-like P2P networks. The worm, called Dynamic Hit-List (DHL) worm, locates new victims and propagates itself by requesting a tracker to build a dynamic hit list, which is a self-stopping BT worm to be stealthy. We construct an analytical model to study the propagation of such a worm: breadth-first propagation and depth-first propagation. The analytical results provide insights of the worm design into choosing parameters that enable the worm to stop itself after compromising a large fraction of vulnerable peers in a P2P network. We finally evaluate the performance of DHL worm through simulations. The simulation results verify the correctness of our model and show the effectiveness of the worm by comparing it with the topological worm.

This paper deals with the problem of guiding mobile sensors (or robots) to a phenomenon across a region covered by static sensors. We present a distributed, reliable and energy-efficient algorithm to construct a smoothed moving trajectory for a mobile robot. The reliable trajectory is realized by first constructing among static sensors a distributed hop count based artificial potential field (DH-APF) with only one local minimum near the phenomenon, and then navigating the robot to that minimum by an attractive force following the reversed gradient of the constructed field. Besides the attractive force towards the phenomenon, our algorithm adopts an additional repulsive force to push the robot away from obstacles, exploiting the fast sensing devices carried by the robot. Compared with previous navigation algorithms that guide the robot along a planned path, our algorithm can (1) tolerate the potential deviation from a planned path, since the DH-APF covers the entire deployment region; (2) mitigate the trajectory oscillation problem; (3) avoid the potential collision with obstacles; (4) save the precious energy of static sensors by configuring a large moving step size, which is not possible for algorithms neglecting the issue of navigation reliability. Our theoretical analysis of the above features considers practical sensor network issues including radio irregularity, packet loss and radio conflict. We implement the proposed algorithm over TinyOS and test its performance on the simulation platform with a high fidelity provided by TOSSIM and Tython. Simulation results verify the reliability and energy efficiency of the proposed mobile sensor navigation algorithm.