41727338
Multiobjective Genetic Search for Spanning Tree Problem
A major challenge to solving multiobjective optimization problems is to capture possibly all the (representative) equivalent and diverse solutions at convergence. In this paper, we attempt to solve the generic multi-objective spanning tree (MOST) problem using an evolutionary algorithm (EA). We consider, without loss of generality, edge-cost and tree-diameter as the two objectives, and use a multiobjective evolutionary algorithm (MOEA) that produces diverse solutions without needing a priori knowledge of the solution space. We test this approach for generating (near-) optimal spanning trees, and compare the solutions obtained from other conventional approaches.
5790802
Object-oriented symbol management in syntax-directed compiler systems
Each symbol in a source program has a series of attributes that govern the operations performed on it. In this paper, we explore object-oriented techniques for representing the attributes of symbols and translating the operations performed on them. This approach is shown superior in memory and run-time speed to the procedural style traditionally used for writing compilers. We demonstrate object-oriented symbol management in a compiler for an arithmetic subset of C. We have used C++ --- a single-dispatching language --- to implement the same, but we emphasize the need for multiple dispatching to develop programs in a heavily-object-oriented style.
537233
Evolutionary Multimodal Optimization Revisited
We revisit a class of multimodal function optimizations using evolutionary algorithms reformulated into a multiobjective framework where previous implementations have needed niching/sharing to ensure diversity. In this paper, we use a steady-state multiobjective algorithm which preserves diversity without niching to produce diverse sampling of the Pareto-front with significantly lower computational effort.
39741624
An Efficient Technique for Dynamic Slicing of Concurrent Java Programs
Program slice has many applications such as program debugging, testing, maintenance and complexity measurement. We propose a new dynamic program slicing technique for concurrent Java programs that is more efficient than the related algorithms. We introduce the notion of Concurrent Program Dependence Graph (CPDG). Our algorithm uses CPDG as the intermediate representation and is based on marking and unmarking the edges in the CPDG as and when the dependencies arise and cease during run-time. Our approach eliminates the use of trace files and is more efficient than the existing algorithms.
24684227
Adaptive Control of Anytime Algorithm Parameters
6342150
Frame based fair multiprocessor scheduler: a fast fair algorithm for real-time embedded systems
This paper presents frame based fair multiprocessor scheduler (FBFMS) which provides accurate real-time proportional fair scheduling for a set of dynamic tasks on a symmetric multiprocessor environment with O(1) scheduling overhead. FBFMS meets these seemingly contradictory goals by applying the benefits of virtual time round-robin scheduling mechanism along with a frame based scheduling approach. Simulation results show that the algorithm provides 2.5 to 26 times speedup (over O(lg n) complexity schedulers) with distortion in fairness less than 1% in most cases, and less than 15% in the worst case.
62235343
A simulation-based study of wireless sensor network middleware
Future wireless sensor networks (WSNs) will transport high-bandwidth, low-latency streaming data, and will host sophisticated processing, such as image fusion and object tracking, in-network on sensor network nodes. Recent middleware proposals provide capabilities for in-network processing, reducing energy drain based on communication costs alone. However, hosting complex processing on WSN nodes incurs additional processing energy and latency costs that impact network lifetime and application performance. There is a need for a WSN planning framework to explore energy saving and application performance trade-offs for models of future sensor networks that account for processing costs in addition to communication costs. In this work, we present a simulation framework to analyze the interplay between resource requirements for compute-and communication-intensive in-network processing for streaming applications. We simulate a surveillance application workload with middleware capabilities for data fusion, adaptive policy-driven migration of data fusion computation across network nodes, and prefetching of streaming data inputs for fusion processing. Our study sheds light on application figures of merit such as latency, throughput, and lifetime with respect to migration policy and node CPU and radio characteristics.
8733679
Stochastic Fluid Theory for P2P Streaming Systems
We develop a simple stochastic fluid model that seeks to expose the fundamental characteristics and limitations of P2P streaming systems. This model accounts for many of the essential features of a P2P streaming system, including the peers' realtime demand for content, peer churn (peers joining and leaving), peers with heterogeneous upload capacity, limited infrastructure capacity, and peer buffering and playback delay. The model is tractable, providing closed-form expressions which can be used to shed insight on the fundamental behavior of P2P streaming systems. The model shows that performance is largely determined by a critical value. When the system is of moderate-to-large size, if a certain ratio of traffic loads exceeds the critical value, the system performs well; otherwise, the system performs poorly. Furthermore, large systems have better performance than small systems since they are more resilient to bandwidth fluctuations caused by peer churn. Finally, buffering can dramatically improve performance in the critical region, for both small and large systems. In particular, buffering can bring more improvement than can additional infrastructure bandwidth.
1384171
Efficient Hybrid Security Mechanisms for Heterogeneous Sensor Networks
Many applications that make use of sensor networks require secure communication. Because asymmetric-key solutions are difficult to implement in such a resource-constrained environment, symmetric-key methods coupled with a priori key distribution schemes have been proposed to achieve the goals of data secrecy and integrity. These approaches typically assume that all nodes are similar in terms of capabilities and, hence, deploy the same number of keys in all sensors in a network to provide the aforementioned protections. In this paper, we demonstrate that a probabilistic unbalanced distribution of keys throughout the network that leverages the existence of a small percentage of more capable sensor nodes can not only provide an equal level of security, but also reduce the consequences of node compromise. To fully characterize the effects of the unbalanced key management system, we design, implement, and measure the performance of a complementary suite of key establishment protocols known as LIGER. Using their predeployed keys, nodes operating in isolation from external networks can securely and efficiently establish keys with each other. Should resources such as a backhaul link to a key distribution center (KDC) become available, networks implementing LIGER automatically incorporate and benefit from such facilities. Detailed experiments demonstrate that the unbalanced distribution in combination with the multimodal LIGER suite offers a robust and practical solution to the security needs in sensor networks
7339641
Efficient beacon placement for network tomography
Recent interest in using tomography for network monitoring has raised the fundamental issue of whether it is possible to use only a small number of probing nodes (beacons) for monitoring all edges of a network in the presence of dynamic routing. Past work has shown that minimizing the number of beacons is NP-hard, and has provided approximate solutions that may be fairly suboptimal. In this paper, we use a two-pronged approach to compute an efficient beacon set: (i) we formulate the need for, and design algorithms for, computing the set of edges that can be monitored by a beacon under all possible routing states; and (ii) we minimize the number of beacons used to monitor all network edges. We show that the latter problem is NP-complete and use an approximate placement algorithm that yields beacon sets of sizes within 1+<i>ln</i>(|<i>E</i>|) of the optimal solution, where E is the set of edges to be monitored. Beacon set computations for several Rocketfuel ISP topologies indicate that our algorithm may reduce the number of beacons yielded by past solutions by more than 50%.
2138355
Specification of secure distributed collaboration systems
The focus of this paper is on a specification model for defining security and coordination policies for distributed collaboration and workflow systems. This work is motivated by the objective to build distributed collaboration systems from their high level specifications. We identify here unique requirements for secure collaboration, specifically role admission and activation constraints, separation of duties, dynamic access control, and a model for multiuser participation in a role. We present a role-based model for specifying coordination and dynamic security requirements in collaboration systems. It also supports hierarchical structuring of a large collaboration environment using the concept of activities, which define a naming scope and a protection domain to specify security and coordination policies. We have implemented this specification model in XML and used it to construct the runtime environments for distributed collaboration systems using a policy based middleware.