etd@IISc Collection:http://hdl.handle.net/2005/182018-01-13T11:45:57Z2018-01-13T11:45:57ZWeighted Average Based Clock Synchronization Protocols For Wireless Sensor NetworksSwain, Amulya Ratnahttp://hdl.handle.net/2005/25512018-01-09T06:45:57Z2016-07-11T18:30:00ZTitle: Weighted Average Based Clock Synchronization Protocols For Wireless Sensor Networks
Authors: Swain, Amulya Ratna
Abstract: Wireless Sensor Networks (WSNs) consist of a large number of resource constrained sensor nodes equipped with various sensing devices which can monitor events in the real world. There are various applications such as environmental monitoring, target tracking forest fire detection, etc., which require clock synchronization among the sensor nodes with certain accuracy. However, a major constraint in the design of clock synchronization protocols in WSNs is that sensor nodes of WSNs have limited energy and computing resources. Clock synchronization process in the WSNs is carried out at each sensor node either synchronously, i.e., periodically during the same real-time interval, which we call synchronization phase, or asynchronously, i.e., independently without worrying about what other nodes are doing for clock synchronization. A disadvantage of asynchronous clock synchronization protocols is that they require the sensor nodes to remain awake all the time. Therefore, they cannot be integrated with any sleep-wakeup scheduling scheme of sensor nodes, which is a major technique to reduce energy consumption in WSNs. On the other hand, synchronous clock synchronization protocols can be easily integrated with the synchronous sleep-wakeup scheduling scheme of sensor nodes, and at the same time, they can provide support to achieve sleep-wakeup scheduling of sensor nodes. Essentially, there are two ways to synchronize the clocks of a WSN, viz. internal clock synchronization and external clock synchronization. The existing approaches to internal clock synchronization in WSNs are mostly hop-by-hop in nature, which is difficult to maintain. There are also many application scenarios where external clock synchronization is the only option to synchronize the clocks of a WSN. Besides, it is also desired that the internal clock synchronization protocol used is fault-tolerant to message loss and node failures. Moreover, when the external source fails or reference node fails, the external clock synchronization protocol should revert back to internal clock synchronization protocol with/without using any reference node. Towards this goal, first we propose three fully distributed synchronous clock synchronization protocols, called Energy Efficient and Fault-tolerant Clock Synchronization (EFCS) protocol, Weighted Average Based Internal Clock Synchronization (WICS) protocol, and Weighted Average Based External Clock Synchronization (WECS) protocol, for WSNs making use of peer-to-peer approach. These three protocols are dynamically interchangeable depending upon the availability of external source or reference nodes. In order to ensure consistency of the synchronization error in the long run, the neighboring nodes need to be synchronized with each other at about the same real time, which requires that the synchronization phases of the neighboring nodes always overlap with each other. To realize this objective, we propose a novel technique of pullback, which ensures that the synchronization phases of the neighboring nodes always overlap. In order to further improve the synchronization accuracy of the EFCS, WICS, and WECS protocol, we have proposed a generic technique which can be applied to any of these protocols, and the improved protocols are referred as IEFCS, IWICS, and IWECS respectively. We then give an argument to show that the synchronization error in the improved protocols is much less than that in the original protocols. We have analyzed these protocols for bounds on synchronization error, and shown that the synchronization error is always upper bounded. We have evaluated the performance of these protocols through simulation and experimental studies, and shown that the synchronization accuracy achieved by these protocols is of the order of a few clock ticks even in very large networks. The proposed protocols make use of estimated drift rate to provide logical time from the physical clock value at any instant and at the same time ensure the monotonicity of logical time even though physical clock is updated at the end of each synchronization phase. We have also proposed an energy aware routing protocol with sleep scheduling, which can be integrated with the proposed clock synchronization protocols to reduce energy consumption in WSNs further.2016-07-11T18:30:00ZVisual Analysis Of Interactions In Multifield Scientific DataSuthambhara, Nhttp://hdl.handle.net/2005/24072018-01-09T06:42:38Z2014-11-13T18:30:00ZTitle: Visual Analysis Of Interactions In Multifield Scientific Data
Authors: Suthambhara, N
Abstract: Data from present day scientific simulations and observations of physical processes often consist of multiple scalar fields. It is important to study the interactions between the fields to understand the underlying phenomena. A visual representation of these interactions would assist the scientist by providing quick insights into complex relationships that exist between the fields.
We describe new techniques for visual analysis of multifield scalar data where the relationships can be quantified by the gradients of the individual scalar fields and their mutual alignment. Empirically, gradients along with their mutual alignment have been shown to be a good indicator of the relationships between the different scalar variables.
The Jacobi set, defined as the set of points where the gradients are linearly dependent, describes the relationship between the gradient fields. The Jacobi set of two piecewise linear functions may contain several components indicative of noisy or a feature-rich dataset. For two dimensional domains, we pose the problem of simplification as the extraction of level sets and offset contours and describe a robust technique to simplify and create a multi-resolution representation of the Jacobi set.
Existing isosurface-based techniques for scalar data exploration like Reeb graphs, contour spectra, isosurface statistics, etc., study a scalar field in isolation. We argue that the identification of interesting isovalues in a multifield data set should necessarily be based on the interaction between the different fields. We introduce a variation density function that profiles the relationship between multiple scalar fields over isosurfaces of a given scalar field. This profile serves as a valuable tool for multifield data exploration because it provides the user with cues to identify interesting isovalues of scalar fields.
Finally, we introduce a new multifield comparison measure to capture relationships between scalar variables. We also show that our measure is insensitive to noise in the scalar fields and to noise in their gradients. Further, it can be computed robustly and efficiently. The comparison measure can be used to identify regions of interest in the domain where interactions between the scalar fields are significant. Subsequent visualization of the data focuses on these regions of interest leading to effective visual analysis.
We demonstrate the effectiveness of our techniques by applying them to real world data from different domains like combustion studies, climate sciences and computer graphics.2014-11-13T18:30:00ZVariants of Hegselmann-Krause ModelShiragur, Kirankumar Shivanandhttp://hdl.handle.net/2005/28632018-01-09T06:57:12Z2017-12-03T18:30:00ZTitle: Variants of Hegselmann-Krause Model
Authors: Shiragur, Kirankumar Shivanand
Abstract: The Hegselmann-Krause system (HK system for short) is one of the most popular models for the dynamics of opinion formation in multi agent systems. Agents are modeled as points in opinion space, and at every time step, each agent moves to the mass center of all the agents within unit distance. The rate of convergence of HK systems has been the subject of several recent works and the current best bounds are O(n3) in one dimension and O(n4) in higher dimension where n being the number of agents.
In this work, we investigate the convergence behavior of a few natural variations of the HK system and their e act on the dynamics. In the rest variation, we only allow pairs of agents who are friends in an underlying social network to communicate with each other and we can construct conjurations. In the second variation, only one of the agents updates its position at each time step and selection of such an agent may be at random or based on some preened order; as before, these updates of agents also take social information into consideration. In the third variant, agents may not move exactly to the mass center but somewhere close to it. In the fourth variant, we allow all agents to interact with one another, but instead of assigning equal weights to all neighbors as in the HK model, we assign Gaussian weights which are inversely proportional to the distance between agents. In the fifth variant, we consider the Synchronized Bounded In hence model where the agents have in hence bounds instead of con dance bounds, which changes the way agents interact with each other. In our nil variant, we consider the dynamics of HK systems with strategic agents where we have an additional set of agents called as strategic agents whose opinions are chosen freely at each time step. One of the goals using these strategic agents is to lower the convergence time.
The dynamics of all the variants are qualitatively very different from that of the classical HK system. Nevertheless, we prove convergence or show some other interesting results for all of these models. To be more specific, for the rest and third variant we show that these systems make only polynomial number of non-trivial steps, regardless of the social network in the rest vary-ant and noise patterns in the third variant. For the second variant, however, we again show polynomial number of non-trivial steps but in expectation regardless of the social network and interestingly different dynamics. For the fourth variant, we prove an upper bound for the convergence time of Gaussian weighted HK model. For the fifth variant, we consider a special case of this SBI model and prove convergence for this case. For the final variant, we improve the existing results for the optimal convergence time for dumb-bell and equidistant configurations.2017-12-03T18:30:00ZUsing Explicit State Space Enumeration For Specification Based Regression TestingChakrabarti, Sujit Kumarhttp://hdl.handle.net/2005/7382010-07-08T20:30:37Z2010-07-07T18:30:00ZTitle: Using Explicit State Space Enumeration For Specification Based Regression Testing
Authors: Chakrabarti, Sujit Kumar
Abstract: Regression testing of an evolving software system may involve significant challenges. While, there would be a requirement of maximising the probability of finding out if the latest changes to the system has broken some existing feature, it needs to be done as economically as possible. A particularly important class of software systems are API libraries. Such libraries would typically constitute a very important component of many software systems. High quality requirements make it imperative to continually optimise the internal implementation of such libraries without affecting the external interface. Therefore, it is preferred to guide the regression testing by some kind of formal specification of the library.
The testing problem comprises of three parts: computation of test data, execution of test, and analysis of test results. Current research mostly focuses on the first part. The objective of test data computation is to maximise the probability of uncovering bugs, and to do it with as few test cases as possible. The problem of test data computation for regression testing is to select a subset of the original test suite running which would suffice to test for bugs probably inserted in the modifications done after the last round of testing. A variant of this problem is that of regression testing of API libraries. The regression testing of an API is usually done by making function calls in such a way that the sequence of function calls thus made suffices a test specification. The test specification in turn embodies some concept of completeness.
In this thesis, we focus on the problem of test sequence computation for the regression testing of API libraries. At the heart of this method lies the creation of a state space model of the API library by reverse engineering it by executing the system, with guidance from an formal API specification. Once the state space graph is obtained, it is used to compute test sequences for satisfying some test specification. We analyse the theoretical complexity of the problem of test sequence computation and provide various heuristic algorithms for the same.
State space explosion is a classical problem encountered whenever there is an attempt of creating a finite state model of a program. Our method also faces this limitation. We explore a simple and intuitive method of ameliorating this problem – by simply reducing the size of the state vector. We develop the theoretical insights into this method. Also, we present experimental results indicating the practical effectiveness of this method.
Finally, we bring all this together into the design and implementation of a tool called Modest.2010-07-07T18:30:00Z