Overview

• Ph.D. student at UCLA, Computer Science Department, since January 2000.
• M.S. degree in Computer Science - System Architecture, UCLA, December 1999.
• B.S. degree in Computer Science and Engineering, UCLA, June 1998.
• El Camino Real High School, Woodland Hills, CA, July 1994.
• Obrigheim Realschule Obrigheim, Germany, December 1990.
• Prior education in Tehran, Iran.

Current Research Activities

• Wireless Sensor Networks
  Design and development of efficient algorithms for deployment, performance analysis, coverage, decision support, operation optimization, security, and privacy in ad-hoc wireless sensor networks.
  
  
• Communications
  Development and performance analysis of unified programmable front-end receiver (cable, terrestrial, ...) system-on-chip, including efficient timing and carrier recover loops, Viterbi Decoders, Block Decoders, etc.
  
  
• System-On-Chip Bus Network Design
  Algorithms and techniques used in designing efficient bus networks used in multi-core system-on-chip (SOC) designs. My interests include single- and multi-application optimizations, floorplanning-based verification, throughput and latency guarantees, and verification.
  
  
• Design Space Exploration and Application Specific Compilers
  Intelligent automatated design space exploration at all levels, starting from algorithms. Design and implementation of application specific compilers for DSP, wireless, power-critical, security and privacy management, and other domains.
  
  
• Computational Security
  Topics including secure and verifiable program execution, authorship proofs such as watermarking and fingerprinting, ...
  
  

Conference Papers

NEW
Vladimir Bychkovskiy, Seapahn Megerian, Deborah Estrin, Miodrag Potkonjak. "Colibration: A Collaborative Approach to In-Place Sensor Calibration." 2nd International Workshop on Information Processing in Sensor Networks (IPSN'03), Palo Alto, CA, April 2003. Accepted for publication.
Sasha Slijepcevic, Seapahn Megerian, Miodrag Potkonjak. "Analysis of Location Error in Wireless Sensor Networks." 2nd International Workshop on Information Processing in Sensor Networks (IPSN'03), Palo Alto, CA, April 2003. Accepted for publication.
Seapahn Megerian, Milenko Drinic, Miodrag Potkonjak. "Watermarking Integer Linear Programming Solutions." 39th IEEE/ACM Design Automation Conference (DAC 2002), pp. 8-13, June 2002.
Jennifer Wong, Seapahn Megerian, Miodrag Potkonjak. "Forward-Looking Objective Functions: Concepts and Applications in High Level Synthesis." 39th IEEE/ACM Design Automation Conference (DAC 2002), pp. 904-909, June 2002.
Jennifer Wong, Seapahn Meguerdichian, Farinaz Koushanfar, Advait Morge, Dusan Petranovic, Miodrag Potkonjak. "Probabilistic Control Search Strategies for Hardware and Software Optimization During Solution Space Exploration." Invited paper, Parallel Computations and Control Problems (PACO 2001), pp. 1-18, October 2001.
Jennifer Wong, Farinaz Koushanfar, Seapahn Meguerdichian, Miodrag Potkonjak, "A Probabilistic Constructive Approach to Optimization Problems." ICCAD 2001, November 2001, pp. 453-456, November 2001.
Seapahn Meguerdichian, Sasa Slijepcevic, Vahag Karayan, Miodrag Potkonjak, "Localized Algorithms in Wireless Ad-Hoc Networks: Location Discovery and Sensor Exposure" MobiHOC 2001, pp. 106-116, October 2001.
Seapahn Meguerdichian, Farinaz Koushanfar, Gang Qu, Miodrag Potkonjak, "Exposure in Wireless Ad Hoc Sensor Networks." Procs. of 7th Annual International Conference on Mobile Computing and Networking (MobiCom '01), pp. 139-150, July 2001. Received the Best Student Paper Award
Seapahn Meguerdichian, Milenko Drinic, Darko Kirovski, "Latency-Driven Design of Multi-Purpose Systems-On-Chip." 38th IEEE/ACM Design Automation Conference (DAC 2001), pp. 27-30, June 2001.
Seapahn Meguerdichian, Farinaz Koushanfar, Advait Mogre, Dusan Petranovic, Miodrag Potkonjak, "MetaCores: Design and Optimization Techniques." 38th IEEE/ACM Design Automation Conference (DAC 2001), pp. 585-590, June 2001.
Seapahn Meguerdichian, Farinaz Koushanfar, Miodrag Potkonjak, Mani Srivastava, "Coverage Problems in Wireless Ad-Hoc Sensor Networks." IEEE Infocom 2001, Vol 3, pp. 1380-1387, April 2001.
Milenko Drinic, Darko Kirovski, Seapahn Meguerdichian, Miodrag Potkonjak, "Latency-Guided On-Chip Bus Network Design." ICCAD 2000, pp. 420-426, November 2000.
Seapahn Meguerdichian, Miodrag Potkonjak "Watermarking While Preserving the Critical Path." 37th IEEE/ACM Design Automation Conference (DAC 2000), pp. 108-111, June 2000.

Journal Papers

Seapahn Megerian, Farinaz Koushanfar, Gang Qu, Giacomino Veltri, Miodrag Potkonjak. "Exposure in Wireless Sensor Networks: Theory and Practical Solutions." Journal of Wireless Networks 8 (5), ACM Kluwer Academic Publishers, pp. 443-454, September 2002.
Sasha Slijepcevic, Seapahn Megerian, Miodrag Potkonjak. "Location Errors in Wireless Embedded Sensor Networks: Sources, Models, and Effects on Applications." ACM Mobile Computing and Communications Review, Vol. 6, No. 3, pp. 67-78, 2002.

Book Chapters

Seapahn Megerian, Miodrag Potkonjak "Wireless Sensor Networks." To appear in the Encyclopedia of Telecomunications, Wiley Publishers, 2002.

Technical Reports

Seapahn Megrian, Miodrag Potkonjak. "Light Sensor Network Middleware: Formulation, Algorithms, and Validation Techniques." UCLA Technical Reports 030003. January 2003.
Seapahn Megerian, Jennifer Wong, Miodrag Potkonjak. "Light Sensor Appliance: Techniques for Quantitative Design and Efficient Use." UCLA Technical Reports 030002. January 2003.
Seapahn Megerian, Miodrag Potkonjak. "Low Power 0/1 Coverage and Scheduling Techniques in Sensor Networks." UCLA Technical Reports 030001. January 2003.
Jennifer Wong, Farinaz Koushanfar, Seapahn Meguerdichian, Miodrag Potkonjak. "A Probabilistic Constructive Approach to Optimization Problems." UCLA Technical Reports 010029. August 2001.

---

Publication Abstracts

• Colibration: A Collaborative Approach to In-Place Sensor Calibration

  Numerous factors contribute to errors in sensor measurements. In order to be useful, any sensor device must be calibrated to adjust its accuracy against the expected measurement scale. In large-scale sensor networks, calibration will be an exceptionally difficult task since sensor nodes are often not easily accessible and manual device-by-device calibration is quite intractable. In this paper, we present a two-phase post-deployment calibration technique for large-scale, dense sensor deployments. In its first phase, the algorithm derives relative calibration relationships between pairs of co-located sensors, while in the second phase, it maximizes the consistency of the pair-wise calibration functions among groups of sensor nodes. The key idea in the first phase is to use temporal correlation of signals received at neighboring sensors when the signals are highly correlated (i.e. sensors are observing the same phenomenon) to derive the function relating their bias in amplitude. We formulate the second phase as an optimization problem and explore potential trade-offs in the size of the input, quality of solution, and complexity. We evaluate the performance of both phases of the algorithm using empirical and simulated data.
  
  

• Analysis of Location Error in Wireless Sensor Networks

  
  
  

• Light Sensor Network Middleware: Formulation, Algorithms, and Validation Techniques

  Sensor data middleware design is an essential step in building functional and reusable sensor networks. The middleware layer processes the raw data collected from sensors and provides meaningful information to the application layers that utilize it for a variety of tasks. We first formulate sensor data middleware as a nonlinear programming problem with a special structure. As our driver example, we focus on a middleware for light sensing that determines the number, positions, and intensities of different light sources in the environment based on sensor measurements. We demonstrate that even under idealized assumptions, the problem is difficult to solve in presence of errors. The errors are unavoidable and can appear in the forms of position and orientation errors of sensors, as well as calibration and noise in measurements. The backbone of the paper is an algorithm for solving the nonlinear programming problem that leverages on knowledge about light properties, and combining combinatorial and existing numerical optimization techniques. Finally, we present an in depth discussion on our validation techniques and extensive experimental studies on the behaviors and prediction capabilities of our models and algorithms.
  
  

• Light Sensor Appliance: Techniques for Quantitative Design and Efficient Use

  Recently, a large number of sensor equipped wireless mobile systems have been developed and deployed. The general common denominators in all of them have been the emphasis on the communication and computation components and the placements of single sensors of each type. However, in order to enable a meaningful interaction between the user and the physical world, it is necessary to equip the system with a proper number of judiciously placed sensors, as well as to develop the corresponding sensor data processing middleware.
  We propose the first sensor-centric, generic, systematic approach for quantitative design of sensor network appliances. We demonstrate its use by designing light appliance devices and middleware. We have developed five models required to make this problem tractable and to undertake the challenging task of designing light sensor appliances. These five models are: (i) physical world, (ii) light sensor, (iii) physical phenomenon, (iv) appliance design, and (v) computational model. Having these models in place, we present the new design methodology that consists of two mains steps: (1) a procedure for placement of individual sensors of the appliance, and (2) error minimization-based sensor data interpretation middleware. We have developed new optimization techniques for both tasks. The portable light sensor system has been designed using the optimization intensive procedure, and its effectiveness has been demonstrated and validated.
  
  

• Low Power 0/1 Coverage and Scheduling Techniques in Sensor Networks

  Distributed embedded systems have recently emerged as an economically attractive and technically challenging research direction. Among such systems, wireless ad-hoc sensor networks have a special place due to their numerous applications and potential to fill the interface gap between the Internet and the physical world. Wireless sensor networks are intrinsically energy constrained and therefore necessitate the design of new low power protocols. Coverage, in its many forms, is a fundamental task in sensor networks. Our focus here is energy efficient operation strategies for sensor networks with sensor coverage as the primary objective. We present several ILP (Integer Linear Program) formulations and strategies to reduce overall energy consumption while maintaining guaranteed coverage levels. We also demonstrate the practicality and effectiveness of these formulations using several examples and provide comparisons with alternative strategies.
  
  

• Wireless Sensor Networks

  Sensor networks consist of a set of sensor nodes, each equipped with one or more sensors, communication subsystems, storage and processing resources, and in some cases actuators. The sensors in a node observe phenomena such as thermal, optic, acoustic, seismic, and acceleration events, while the processing and other components analyze the raw data and formulate answers to specific user requests. Recent advances in technology have paved the way for the design and implementation of new generations of sensor network nodes, packaged in very small and inexpensive form factors with sophisticated computation and wireless communication abilities. Although still at infancy, these new classes of sensor networks, generally referred to as wireless sensor networks (WSN), show great promise and potential with applications ranging in areas that have already been addressed, to domains never before imagined. In this article we provide an overview of this new and exciting field and a brief discussion on the factors pushing the recent flurry of sensor network related research and commercial undertakings. We also provide overview discussions on architectural design characteristics of such networks including physical components, software layers, and higher level services. At each step, we highlight special characteristics of WSNs and discuss why existing approaches and results from wireless communication networks are not necessarily suitable in WSN domains. We conclude by briefly summarizing the state of the art and the future research directions.
  
  

• Forward Looking Objective Functions: Concept and Applications in High Level Synthesis

  The effectiveness of traditional CAD optimization algorithms is proportional to the accuracy of the targeted objective functions. However, behavioral synthesis tools are not used in isolation; they form a strongly connected design flow where each tool optimizes its own objective function without considering the consequences on the optimization goals of the subsequently applied tools. Therefore, efforts to optimize one aspect of a design often have unforeseen negative impacts on other phases of the design process.
  Our objective is to establish a systematic way of developing and validating new types of objective functions that consider the effects on subsequently applied synthesis steps. We demonstrate the generic forward-looking objective function (FLOF) strategy on three main steps in behavioral synthesis: (i) Transformation, (ii) Scheduling, and (iii) Register Assignment. We show how the FLOF can be used in the first two phases to reduce the total number of registers required in the third phase.
  
  

• Watermarking Integer Linear Programming Solutions

  Linear programming (LP) in its many forms has proven to be an indispensable tool for expressing and solving optimization problems in numerous domains. We propose the first set of generic watermarking techniques for integer-LP (ILP). The proof of authorship by watermarking is achieved by introducing additional constraints to limit the solution space and can be used as effective means of intellectual property protection (IPP) and authentication. We classify and analyze the types of constraints in the ILP watermarking domain and show how ILP formulations provide more degrees of freedom for embedding signatures than other existing approaches. To demonstrate the effectiveness of the proposed ILP watermarking techniques, the generic discussion is further concretized using two examples, namely Satisfiability and Scheduling.
  
  

• A Probabilistic Constructive Approach to Optimization Problems

  We propose a new optimization paradigm for solving intractable combinatorial problems. The technique, named probabilistic constructive, combines the advantages of constructive and probabilistic algorithms. Since it is constructive, it has a relatively short run time and is amenable for inclusion of insights through heuristic rules. The probabilistic nature facilitates a flexible trade-off between run-time and the quality of solution, and super imposition of a variety of control strategies and solution selection mechanisms.
  In addition to presenting the generic technique, we apply it to two generic NP-complete problems (maximal independent set, graph coloring) and two synthesis and compilation problems (sequential code covering, scheduling). The extensive experimentation indicates that the new approach provides very attractive trade-offs between the quality of the solution and run time, often outperforming the best previously published approaches.
  
  

• Localized Algorithms in Wireless Ad-Hoc Networks: Location Discovery and Sensor Exposure

  The development of practical, localized algorithms is probably the most needed and most challenging task in wireless ad-hoc sensor networks (WASNs). Localized algorithms are a special type of distributed algorithms where only a subset of nodes in the WASN participate in sensing, communication, and computation. We have developed a generic localized algorithm for solving optimization problems in wireless ad-hoc networks that has five components: (i) data acquisition mechanism, (ii) optimization mechanism, (iii) search expansion rules, (iv) bounding conditions, and (v) termination rules. The main idea is to request and process data only locally and only from nodes who are likely to contribute to rapid formation of the final solution.
  The approach enables two types of optimization: The first, guarantees the fraction of nodes that are contacted while optimizing for solution quality. The second, provides guarantees on solution quality while minimizing the number of nodes that are contacted and/or amount of communication. This localized optimization approach is applied to two fundamental problems in sensor networks: location discovery and exposure-based coverage. We demonstrate its effectiveness on a number of benchmark examples.
  
  

• Exposure in Wireless Ad Hoc Sensor Networks

  Wireless ad-hoc sensor networks will provide one of the missing connections between the Internet and the physical world. One of the fundamental problems in sensor networks is the calculation of coverage. Exposure is directly related to coverage in that it is a measure of how well an object, moving on an arbitrary path, can be observed by the sensor network over a period of time.
  In addition to the informal definition, we formally define exposure and study its properties. We have developed an efficient and effective algorithm for exposure calculation in sensor networks, specifically for finding minimal exposure paths. The minimal exposure path provides valuable information about the worst case exposure-based coverage in sensor networks. The algorithm works for any given distribution of sensors, sensor and intensity models, and characteristics of the network. It provides an unbounded level of accuracy as a function of run time and storage. We provide an extensive collection of experimental results and study the scaling behavior of exposure and the proposed algorithm for its calculation.
  
  

• Latency-Driven Design of Multi-Purpose Systems-On-Chip

  Deep submicron technology has two major ramifications on the design process: (i) critical paths are being dominated by global interconnect rather than gate delays and (ii) ultra high levels of integration mandate designs that encompass numerous intra-synchronous blocks with decreased functional granularity and increased communication demands. These factors emphasize the importance of the on-chip bus network as the crucial high-performance enabler for future systems-on-chip. By using independent functional blocks with programmable connectivity, designers are able to build systems-on-chip capable of supporting different applications with exceptional level of resource sharing. To address challenges in this design paradigm, we have developed a methodology that enables efficient bus network design with approximate timing verification and floorplanning of multi-purpose systems-on-chip in early design stages. The design platform iterates system synthesis and floorplanning to build min-area floorplans that satisfy statistical time constraints of applications. We demonstrate the effectiveness of our bus network design approach using examples from a multimedia benchmark suite.
  
  

• MetaCores: Design and Optimization Techniques

  Currently, hardware intellectual property (IP) is delivered at three levels of abstraction: hard, firm, and soft. In order to further enhance performance, efficiency, and flexibility of IP design, we have developed a new approach for designing hardware and software IP called MetaCores. The new design approach starts at the algorithm level and leverages on the algorithm's intrinsic optimization degrees of freedom. The approach has four main components: (i) Problem formulation and identification of optimization degrees of freedom; (ii) Objective functions and constraints; (iii) Cost evaluation engine; (iv) Multiresolution design space search. From the algorithmic viewpoint, the main contribution is the introduction of multiresolution search in the optimization and synthesis process. We have applied the approach to the development of Viterbi and IIR MetaCores. Experimental results demonstrate the effectiveness of the new approach.
  
  

• Coverage Problems in Wireless Ad-Hoc Sensor Networks

  Wireless ad-hoc sensor networks have recently emerged as a premier research topic. They have great long-term economic potential, ability to transform our lives, and pose many new system-building challenges. Sensor networks also pose a number of new conceptual and optimization problems. Some, such as location, deployment, and tracking, are fundamental issues, in that many applications rely on them for needed information.
  In this paper, we address one of the fundamental problems, namely coverage. Coverage in general, answers the questions about quality of service (surveillance) that can be provided by a particular sensor network. We first define the coverage problem from several points of view including deterministic, statistical, worst and best case, and present examples in each domain. By combining computational geometry and graph theoretic techniques, specifically the Voronoi diagram and graph search algorithms, we establish the main highlight of the paper - optimal polynomial time worst and average case algorithm for coverage calculation. We also present comprehensive experimental results and discuss future research directions related to coverage in sensor networks.
  
  

• Latency-Guided On-Chip Bus Network Design

  Deep submicron technology scaling has two major ramifications on the design process. First, reduced feature size significantly increases wire delay, thus resulting in critical paths being dominated by global interconnect rather than gate delays. Second, ultra high level of integration mandates design of systems-on-chip that encompass numerous intra-synchronous blocks with decreased functional granularity and increased communication demands. The convergence of these two factors emphasizes the importance of the on-chip bus network as one of the crucial high-performance enablers for future systems-on-chip. We have developed an on-chip bus network design methodology and corresponding set of tools which, for the first time, close the synthesis loop between system and physical design. The approach has three components: a communication profiler, a bus network designer, and a fast approximate floorplanner. The communication profiler collects run-time information about the traffic between system cores. The bus network design component optimizes the bus network structure by coordinating information from the other two components. The floorplanner aims at creating a feasible floorplan and to communicate information about the most constrained parts of the network. We have demonstrated the effectiveness of our bus network design approach on a number of multi-core designs.
  
  

• Watermarking While Preserving the Critical Path

  In many modern designs, timing is either a key optimization goal and/or a mandatory constraint. We propose the first intellectual property protection (IPP) technique using watermarking which guarantees preservation of timing constraints. This is accomplished by judiciously selecting parts of the design specification on which watermarking constraints can be imposed. The technique is applied during the mapping of logical elements to instances of realization elements in a physical library. The generic technique is applied to two steps in the design process: combinational logic mapping in logic synthesis and template matching in behavioral synthesis. The technique is fully transparent to the synthesis process, and can be used in conjunction with arbitrary synthesis tools. Several optimization problems associated with the application of the technique have been solved. The effectiveness of the technique is demonstrated on a number of designs at both the logic synthesis and behavioral synthesis designs.