14748622
Power Efficient Algorithms for Computing Fast Fourier Transform over Wireless Sensor Networks
Collaborative signal processing is one of the most promising applications that are currently being investigated for sensor networks. In this paper, we use FFT computation as a vehicle to highlight the issues involved in realizing distributed computations over sensor networks that have global and local communication and synchronization characteristics. We present a power efficient algorithm for computing 1-D Fast Fourier Transform (FFT) over single and multi-hop wireless sensor networks. The proposed algorithm reduces the number of transmissions, eliminates typical redundant computations in a distributed FFT algorithm and uniformly maps complex multiplications over all the sensors nodes by introducing an extra bit-complement permutation stage after first (log2N)/2 iterations. We show that the proposed algorithm improves energy consumption by 36% on the average on multi-hop sensor networks. This saving in energy consumption significantly improves the battery life of the sensor nodes thereby increasing lifetime of the sensor network.
321445
Detection of Masquerade Attacks on Wireless Sensor Networks
We propose two lightweight techniques to detect masquerade attacks on wireless sensor networks (WSN). Our solutions take into consideration, important WSN properties like coverage, connectivity, data aggregation and specific communication patterns. The two proposed techniques complement each other when used concurrently. The mutual guarding (MG) technique does not work when nodes are not completely covered by their neighbors or when adversary has shorter transmission range than the sensor nodes. It also does not protect nodes near the boundary. The SRP technique does not have these drawbacks. In this paper, we present our proposed techniques and analyze their performance in terms of successful masquerade detection rate and traffic and computational overhead.
19327594
Mobility-Pattern-Based Anomaly Detection Algorithm in Mobile Networks
Numerous approaches have been proposed for intrusion detection in immobile networks. However, little research work has been done in actually implementing them, especially for anomaly detection, in mobile networks. In this paper, we present an efficient mobility-pattern-based (MPB) anomaly detection algorithm. It can effectively identify abnormal mobility patterns of the nodes in mobile networks. In the proposed algorithm, the normal mobility profile of a specific node is characterized by a multi-leaf tree structure in which each node corresponds to a possible destination cluster. A normal mobility profile is generated during the training process through data mining and fuzzy logic techniques. More specifically, data mining techniques are used for cluster classifications, and fuzzy logic techniques are used to integrate the 'similar'' pattern strings after the corresponding cluster generation. These two techniques are also used during the testing process for distinguishing abnormal mobility patterns of the node from those of the normal in mobile networks. Simulation results demonstrate that our proposed MPB anomaly detection algorithm can achieve good performance in terms of detection rate and false alarm rate for nodes with regular movement behaviors by fine tuning the design parameter - threshold, that can be chosen efficiently.
17746198
Large—scale parallel numerical integration
We present and analyze strategies which can be used for the parallel computation of large numbers of integrals which may be of different levels of difficulty. Parallelization on the integral level, which is generally used for large numbers of integrals, is combined with parallelization on the subregion level, which enables handling local integration difficulties within individual problems. This results in a new, hierarchical algorithm which incorporates load balancing on the integral level and on the subregion level. We report test results of the software and show that the hierarchical approach leads to a scalable integration algorithm.
1276171
Using Lagrangean Relaxation for Service Location Planning with QoS Constraints in Large-Scale Networks
Current trends in computing indicate that there is a great potential for service oriented computing and similar technologies, such as Cisco's Application Oriented Networks, where services provide a higher-level of abstraction to traditional applications. In such cases, providing and consuming services and establishing a relationship between consumers (users of services) and producers (providers of services) are still challenging and vastly researched aspects. We define a service location planning problem (SLP) that is novel in the approach it takes to match consumers to producers, such that the cost of providing services is minimized while taking into account quality of service constraints of throughput and delay. In previous work, we presented an integer linear programming (ILP) model to formulate the service location planning problem. In this paper, we present Lagrangean Relaxation of the model for large-scale networks. We use the approach of Trick [3] to decrease computational overheads.
155165
Multivariate Integration on Hypercubic and Mesh Networks
Abstract We analyze a class of adaptive algorithms for integration over N-dimensional hyper-rectangular or simplical regions, on distributed systems. An adaptive algorithm attempts to achieve the requested accuracy by refining the subdivision of the integration region, thus allowing for a concentration of subdivisions near singularities. At the subdivision of a region, the error behaves according to a prescribed model, relating the error of the parent region to that of its children. The analysis can also be applied to problems in other areas, as long as the task selection is based on a priority function which behaves according to a suitable model. Using an efficient management of the subregions, we show that an O (p/ log p) speedup can be achieved on a p-processor hypercubic network, such as shuffle exchange, butterfly and hypercube. Furthermore, a speedup of O ( p ) can be achieved on a p × p mesh network. We also show that our algorithms compare favorably with well-known dynamic load balancing strategies.
496243
Mini Track: 'Ethical, Legal and Economic Issues in the Digital Economy: Intellectual Property Rights, Piracy, Trust, Security and Privacy'
The emergence of the Internet as the de facto medium for business has accentuated the role of factors such as intellectual property rights (IPR), consumer privacy, and trust. Newer technologies have it made it a challenging task to protect content for sellers and private information for consumers. This is the second time for this mini track at HICSS and it includes technical, analytical, empirical, and conceptual research spanning diverse research areas and methodologies including the social, behavioral, and economic issues. In his paper “Does drop in copying cost support copyright term extension?” Michael Y. Yuan examines copyright duration and analyzes the validity of the extending copyright duration. Through a simulation of an information product market, this model recommends that decrease in copying cost of information products reduces the optimal duration of copyright. Further, while longer life expectancy may support copyright term extension, this work finds that increase in demand for information products supports reduction in copyright duration.
6504247
Hardware Diagnosis as Program Debugging
Horn clauses provide a useful framework for writing executable structural representations for digital circuits. This paper discusses how these representations can be used to diagnose faulty circuits using algorithmic program debugging techniques developed by Shapiro. The sound theoretical basis of these techniques is one of the major advantages of this approach. This framework also provides a new perspective on some of the hardware diagnosis techniques suggested in the literature.
11409534
Risk profile and consumer shopping behavior in electronic and traditional channels
This paper develops an economic model that captures consumer shopping channel choices based on shopping channel characteristics and consumer risk profiles--risk-neutral or risk-averse. Analyses of results show that after making purchases through one channel, electronic or traditional, risk-averse consumers tend to be more loyal customers than risk-neutral consumers. Further, the two types of consumers may exhibit split channel behavior--risk-neutral consumers prefer one channel and risk-averse consumers prefer the other. However, risk-neutral consumers are not always more likely to prefer electronic channel than risk-averse consumers. Implications for retailer pricing strategies are discussed.
31511581
Mutual Exclusion on a Hypercube
Abstract We present a decentralized, symmetric mutual exclusion algorithm that is tailored to the hypercube architecture. Our algorithm has better time complexity than a suitable hypercube adaptation of Maekawa′s O(√N) Mutual Exclusion algorithm. We show that, in the presence of contention, our algorithm has a shorter Blocking Delay than Maekawa′s algorithm. In the absence of contention, our algorithm achieves optimal Round-trip Delay under both the n-port and the one-port communication models.
30968721
Tracking Deformable Templates Using a Shortest Path Algorithm
This paper proposes a new technique to track deformable templates. We extend the typical graph algorithms that have been used for active contour recovery to incorporate shape information. The advantage of graph algorithms is that they are guaranteed to find the global minimum of the energy function. The difficulty with their traditional use for active contours is that they consider only two pixels at a time when recovering the contour, making it impossible to enforce shape constraints. We define the deformable template as a polygonal contour, demonstrate the proper mapping between the image, the contour, and a graph, and show how to apply Dijkstra's algorithm to track contours in image sequences. Examples are shown for deforming contours, articulated objects, and smooth contours being tracked in simple and complicated backgrounds. We also provide an analysis of the computational requirements.