etd@IISc Collection:
http://etd.iisc.ernet.in/2005/18
2018-06-19T00:02:34ZWeighted Average Based Clock Synchronization Protocols For Wireless Sensor Networks
http://etd.iisc.ernet.in/2005/2551
Title: 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 Data
http://etd.iisc.ernet.in/2005/2407
Title: 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 Model
http://etd.iisc.ernet.in/2005/2863
Title: 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:00ZVariants and Generalization of Some Classical Problems in Combinatorial Geometry
http://etd.iisc.ernet.in/2005/3134
Title: Variants and Generalization of Some Classical Problems in Combinatorial Geometry
Authors: Bharadwaj, Subramanya B V
Abstract: In this thesis we consider extensions and generalizations of some classical problems
in Combinatorial Geometry. Our work is an offshoot of four classical problems in
Combinatorial Geometry. A fundamental assumption in these problems is that the
underlying point set is R2. Two fundamental themes entwining the problems considered
in this thesis are: “What happens if we assume that the underlying point set is finite?”, “What happens if we assume that the underlying point set has a special structure?”. Let P ⊂ R2 be a finite set of points in general position. It is reasonable to expect that if |P| is large then certain ‘patterns’ in P always occur. One of the first results was the Erd˝os-Szekeres Theorem which showed that there exists a f(n) such that if |P| ≥ f(n) then there exists a convex subset S ⊆ P, |S| = n i.e., a subset which is a convex polygon of size n. A considerable number of such results have been found since.
Avis et al. in 2001 posed the following question which we call the n-interior point
problem: Is there a finite integer g(n) for every n, such that, every point set P with
g(n) interior points has a convex subset S ⊆ P with n interior points. i.e. a subset
which is a convex polygon that contains exactly n interior points. They showed that
g(1) = 1, g(2) = 4. While it is known that g(3) = 9, it is not known whether g(n) exists for n ≥ 4. In the first part of this thesis, we give a positive solution to the n-interior point problem for point sets with bounded number of convex layers.
We say a family of geometric objects C in Rd has the (l, k)-property if every subfamily
C′ ⊆ C of cardinality at most l is k-piercable. Danzer and Gr¨unbaum posed
the following fundamental question which can be considered as a generalised version of
Helly’s theorem: For every positive integer k, does there exist a finite g(k, d) such that if any family of convex objects C in Rd has the (g(k, d), k)-property, then C is k-piercable? Very few results(mostly negative) are known.
Inspired by the original question of Danzer and Gr¨unbaum we consider their question
in an abstract set theoretic setting. Let U be a set (possibly infinite). Let C be a family of subsets of U with the property that if C1, . . . ,Cp+1 ∈ C are p + 1 distinct subsets, then |C1 ∩ · · · ∩Cp+1| ≤ l. In the second part of this thesis, we show in this setting, the first general positive results for the Danzer Grunbaum problem. As an extension, we show polynomial sized kernels for hitting set and covering problems in our setting.
In the third part of this thesis, we broadly look at hitting and covering questions
with respect to points and families of geometric objects in Rd. Let P be a subset of points(possibly infinite) in Rd and C be a collection of subsets of P induced by objects of a given family. For the system (P, C), let νh be the packing number and νc the dual packing number. We consider the problem of bounding the transversal number τ h and the dual transversal number τ c in terms of νh and νc respectively.
These problems has been well studied in the case when P = R2. We systematically
look at the case when P is finite, showing bounds for intervals, halfspaces, orthants,
unit squares, skylines, rectangles, halfspaces in R3 and pseudo disks. We show bounds for rectangles when P = R2.
Given a point set P ⊆ Rd, a family of objects C and a real number 0 < ǫ < 1, the
strong epsilon net problem is to find a minimum sized subset Q ⊆ P such that any
object C ∈ C with the property that |P ∩C| ≥ ǫn is hit by Q. It is customary to express
the bound on the size of the set Q in terms of ǫ.
Let G be a uniform √n × √n grid. It is an intriguing question as to whether we
get significantly better bounds for ǫ-nets if we restrict the underlying point set to be the grid G. In the last part of this thesis we consider the strong epsilon net problem for families of geometric objects like lines and generalized parallelograms, when the underlying point set is the grid G. We also introduce the problem of finding ǫ-nets for arithmetic progressions and give some preliminary bounds.2018-02-17T18:30:00Z