1. Ph.D Theses
Permanent URI for this collectionhttps://idr.nitk.ac.in/handle/1/11
Browse
41 results
Search Results
Item Orchestration Mechanisms for Enabling Distributed Processing In the Fog Computing Environment(National Institute of Technology Karnataka, Surathkal, 2021) Martin, John Paul.; Kandasamy, A.; Chandrasekaran, K.The recent years witnessed the rapid adoption of the Internet of Things (IoT) paradigm across business and non-business realms alike. Usually, IoT-based systems are located at a multi-hop distance apart from the Cloud datacenters. Consequently, relying on Cloud-centric execution results in a performance penalty for the real-time IoT applications. To circumvent this, the Fog computing paradigm emanated as a widespread computing technology to support the execution of the IoT applications. Fog computing extends Cloud services to the vicinity of end devices, thereby enabling the applications to be executed closer to the data sources. Thus, the Fog paradigm aids in reducing the service delivery time and network congestion. Even though this new paradigm opens a set of potential possibilities, it also introduces several additional challenges and complexities arising from its heterogeneity and resource-constrained characteristics. In order to harness the potential of Fog computing environments, it is imperative to adopt efficient orchestration mechanisms that can manage the resources in the system. Application management is an intrinsic component of resource orchestration systems. This involves identifying suitable options for the initial placement of the applications. The placement decisions have significant impacts on the overall performance of the application. Placement schemes for Fog environments must take into consideration the requirements and characteristics of the different entities in the Fog ecosystem, including the Fog nodes, IoT applications and IoT devices. The category of mission critical IoT applications makes reliable service delivery an essential requirement in Fog environments. There is a resolute need for placement schemes that ensure reliable service delivery. Accordingly, in this research, a placement policy that addresses the conflicting criteria of service reliability and monetary cost is proposed. The proposed Cost and Reliability aware Eagle Whale optimizer (CREW) derives placement decisions that maximize the reliability and minimize the cost. Realtime experiments substantiate that the proposed approach succeeds in improving the performance of applications executed in Fog computing environments. User mobility is another particularity in Fog computing environments. Mobility of the end users may result in an increase in the hop distance between the data source and the Fog node. In order to ensure that this does not adversely impact service delivery, application modules must be migrated across Fog nodes with the objective of maintaining low hop distance values. Therefore, this research also presents a Mobility-aware Autonomic Framework (MAMF) to perform migrations in the Fog environment. The developed framework relies on predetermined user locations to take migration decisions. Performance of the approach is evaluated using real-time mobility traces.Item Efficient Domination in Cartesian product of Graphs and its Critical Aspects(National Institute of Technology Karnataka, Surathkal, 2021) Shet, Sujatha V.; Thilak, A Senthil.; Kamath, Shyam S.In a graph G = (V;E), every vertex v 2 V (G) dominates itself and its neighbors. A set S V (G) is a dominating set of G if each vertex in V (G) is either in S or has a neighbor in S. The domination number of G, denoted by (G), is the cardinality of a minimum dominating set of G. It is noted that if S is a dominating set, then the vertices in V S may have more than one neighbor in S. Imposing the additional constraint on a dominating set S that, each vertex in V must have exactly one neighbor in S (inclusive of vertices in S), leads to the notion of efficient domination in graphs. A dominating set S V (G) is an efficient dominating set (EDS) of G, if each vertex in V (G) is either in S or has exactly one neighbor in S. A graph G is efficiently dominatable, if it has an EDS. If S is an EDS of G, then S is also a minimum dominating set of G, but not conversely. Thus, all efficient dominating sets have the same cardinality, namely, (G). Though an EDS of G has the same cardinality as its domination number, it is noted that for a given domination number, the properties of a graph which does not contain an EDS need not be true for an efficiently dominatable graph. This necessitates an exclusive study of the class of efficiently dominatable graphs. Though there is a significant amount of study in the literature related to efficient domination, both from graph theoretical as well as algorithmic perspective, to the best of our knowledge, it has not been much explored relative to the other domination parameters. Further, the concept of efficient domination also finds applications in diverse fields like coding theory, parallel computing, wireless ad hoc networks, etc. Motivated by the applications of efficient domination and the research gap identified in the literature, interest is shown in this thesis to study the concept of efficient domination for an arbitrary graph and for a particular type of graph product, namely cartesian product. The contributions to this thesis are organized into three chapters, namely Chapter 3, 4 and 5. Chapter 3 deals with the study on Efficient domination in general/arbitrary graphs. Some basic results on efficient domination in general graphs including some improved bounds on domination number, efficient domination in trees and some special classes of graphs are discussed. Further, the structural properties of graphs possessing pairwise disjoint efficient dominating sets are studied along with an insight into the applications of such structures in ad hoc and sensor networks. i Chapter 4 focuses on the concept of criticality in the class of efficiently dominatable graphs, where the concept of criticality in general, deals with the study of the behaviour of a graph with respect to a graph parameter, upon the removal of a vertex or a set of vertices, removal or addition of one or more edges. The study in this chapter is restricted to the removal of a single vertex and removal or addition of a single edge, at a time. Based on the research gap identified in the literature, fascinated by the applications of the concept of criticality in the design of fault-tolerant networks and its significance in graph theory, the study is initiated with respect to efficient domination. A vertex whose removal from G alters (G) is referred to as a critical vertex. Similarly, an edge, whose removal from G or whose addition between a pair of non-adjacent vertices in G alters (G) is a critical edge. The collection of such vertices (or edges) is a vertex (or edge) critical set. In this chapter, an attempt is made to explore the properties of critical vertices, critical edges with respect to both removal and addition. The vertex critical sets, edge critical sets and six classes of graphs arising thereof are characterized. Finally, the relationship between all these classes is identified and discussed. Finally, Chapter 5 deals with the study of efficient domination in the cartesian product of graphs. Here, the structural properties of the product in terms of its factors are discussed. The initial focus is on the product of two well-known graphs, followed by the product of an arbitrary graph G with a well-known graph. Further, the class of efficiently dominatable product graphs G K1; p and G Kp, for some positive integer p and an arbitrary graph G are characterized. The problem of deciding whether or not a graph is efficiently dominatable is NP-complete and so also, for the the products mentioned above. So, an attempt is made to design exact exponential time algorithms, to determine whether the products are efficiently dominatable or not. The study is also extended to Hamming graphs.Item Secure Authentication Schemes for Roaming Service in Global Mobility Networks(National Institute of Technology Karnataka, Surathkal, 2021) Suvidha, K S.; Madhusudhan, R.Distribution of resources and services via open network has become the latest trend in information technology. In the open network, hackers can easily obtain the communication data. Therefore, open network demands the security to protect data and information. Hence, network security is the most important requirement in an open network. In the security system, authentication plays a major role. User authentication is a central component of any security infrastructure. Other security measures depend upon verifying the identity of the sender and receiver of information. Authorization grants privileges based upon identity. Audit trails would not provide accountability without authentication. Confidentiality and integrity are broken if we can't reliably differentiate an authorized entity from an unauthorized entity. Remote user authentication is a mechanism to identify the remote users over an insecure communication network. In remote user authentication, password authentication is the simplest method to authenticate the user. But, the limitations in the password authentication approach leads towards the development of two-factor authentication. There are hundreds of remote user authentication schemes have been proposed by many researchers. None of the schemes achieve all the security goals and many schemes fail to provide security against various attacks. Even though some of the schemes provide the security, they are not efficient in terms of computation and communication cost. Hence, it is necessary to design an efficient and secure authentication scheme. This thesis aims to provide efficient and secure remote user authentication schemes in distributed systems and networks. There are many factors involved in authentication schemes and these factors use the characteristics of the password, smart card and biometric. This research concentrates on cryptanalysis and improvements of the smart card based two-factor remote user authentication schemes. Till date, many smart card based remote user authentication schemes have been proposed. But, every scheme has its security flaws. None of the schemes have succeeded to achieve all the security requirements and goals. Also, many schemes do not provide a strong formal proof to prove the security of the scheme. In this thesis, cryptanalysis of the recently proposed remote user authentication schemes has been done to identify the vulnerabilities. New schemes have been proposed to overcome the identified security flaws. Security of i the proposed schemes has been formally analyzed using BAN logic. Furthermore, the proposed schemes have been simulated using Automated Validation of Internet Security Protocols and Applications (AVISPA) tool. Through this simulation, it has been ensured that the proposed scheme is secure against active and passive attacks. Using NS 2 simulator, the performance metrics such as throughput, end to end delivery and packet delivery ratio are calculated for the proposed scheme. In the literature study, it is observed that to avoid the replay attack, many remote user authentication schemes depend on clock synchronization. But the clock synchronization has its own disadvantages. Also, the schemes, which are independent of clock synchronization are vulnerable to replay attack. To fix these weaknesses, a novel authentication scheme has been proposed. By employing the Elliptic Curve Diffie-Hellman (ECDH) key exchange algorithm, the proposed scheme resists the replay attack. Through the security analysis, it is proved that the scheme achieves all the security goals and resists well-known attacks like insider attack, offline password guessing attack, etc. The proposed scheme security have been analyzed using BAN logic and simulated in AVISPA tool. Through these results, it is ensured that the proposed scheme resists all security attacks. The contributions of this thesis is to the improve the security of the existing authentication schemes. In particular, this research analyzes the Gope and Hwang, Fan Wu et al. and Lee et al.'s schemes. However, the analyzed schemes have many security flaws like fail to provide user anonymity and forward secrecy, vulnerable to the stolen smart card attack, insider attack, guessing attack etc. Based on the analysis, this research proposes improved schemes to overcome the identified weaknesses. Furthermore, a novel authentication scheme has been proposed to resist security attacks. Finally, the thesis presents concluding remarks and discusses the future scope.Item Some Applications of S-Transform and its Modifications in Signal and Image Processing(National Institute of Technology Karnataka, Surathkal, 2021) Kamath, Priya R.; Senapati, Kedarnath.Signal analysis generally involves the usage of time-frequency analysis tools. Fourier transform was able to decompose a periodic signal into multiple sine/cosine signals. This led to the development of many transforms which decomposed the signal using various basis functions. Disadvantages associated with Fourier transform paved the way to introduction of other transforms like short-term Fourier transform. S-transform is a time-frequency analysis tool which has close association with Fourier transform. Unlike the short-term Fourier transform (where the window width was kept constant), the S-transform provided a Gaussian window whose standard deviation was frequency dependent. Thus, the S-transform offered improved frequency resolution at high frequencies and good time resolution at lower frequencies. The focus of this thesis is on the suitable modification as well as different applications of S-transform. We have applied S-transform and its variations on varieties of one and twodimensional signals. In addition to proposing a modification of S-transform (which uses a kernel having compact support), we have: 1. Analysed the changes in the phase of an EEG signal, using the conventional S-transform, to identify the eye-blink artifacts. EEG electrodes are used to record signals on the scalp. Due to propagation delay, a phase difference exists between the signal captured by different electrodes. This phase information is used to determine the eye-blink artifacts in the EEG signal . 2. Performed wind speed prediction, using artificial neural network and a modified form of the S-transform (CBST). Experimental results show that this method lowers the prediction errors. To achieve this, we have used CBST to decompose the wind-speed into sub-series. We have performed “one-step-ahead” prediction on the subseries using artificial neural network with backpropagation algorithm. The sub-series predictions are recombined to obtain the wind-speed prediction. 3. Despeckled SAR images using discrete orthonormal S-transform (DOST).We have made use of shock filter, in addition to two-dimensional DOST to remove the speckles in the image. An edge enhancement algorithm is used to enhance the details at the edges. This ensures that the homogenous regions of the SAR image are smooth while retaining the details in the heterogenous regions.Item Degree Restricted Domination in Graphs(National Institute of Technology Karnataka, Surathkal, 2021) M, Rashmi.; Kamath, Shyam S.; Thilak, A Senthil.The thesis mainly involves the study of a new generalization of the domination parameter, kpart degree restricted domination, defined by imposing a restriction on the degree of the vertices in a dominating set. A dominating set D of a graph G is a k-part degree restricted dominating set (k-DRD set), if for all u 2 D, there exists a set Cu ✓ N(u) \ (V D) such that |Cu| ld(u) k m and S u2D Cu = V D. The minimum cardinality of a k-part degree restricted dominating set of a graph G is the k-part degree restricted domination number of G. The thesis includes the detailed study of the k-part degree restricted domination and a particular case when k = 2. Bounds on the k-part degree restricted domination number in terms of covering and independence number. Relation between k-part degree restricted dominating set and some other domination invariants are discussed in the thesis. Further, the complexity of k-part degree restricted domination problem is discussed in detail. The problem of finding minimum k-part degree restricted domination number is proved to be NP-complete for bipartite graphs, chordal graphs, undirected path graphs, chordal bipartite graphs, circle graphs, planar graphs and even when restricted to split graphs. Also, exhibit a polynomial time algorithm to find a minimum k-part degree restricted domination number of trees and an exponential time algorithm to find a minimum k-part degree restricted domination number of interval graphs. The critical aspects of the k-part degree restricted domination number is provided with respect to the removal of vertices and edges from the graph.Item Characterization of Non-Isolated Forts and Stability of an Iterative Functional Equation(National Institute of Technology Karnataka, Surathkal, 2021) Palanivel, R.; Murugan, V.The problem of finding a solution f : X →X of the iterative functional equation f n = F for a given positive integer n ≥ 2 and a function F : X → X on a non-empty set X is known as the iterative root problem. The non-strictly monotone points (or forts) of F play an essential role in finding a continuous solution f of f n = F whenever X is an interval in the real line. In this thesis, we define the forts for any continuous function f : I →J, where I and J are arbitrary intervals in the real line R. We study the non-monotone behavior of forts under composition and characterize the sets of isolated and non-isolated forts of iterates of any continuous self-map on an arbitrary interval I to study the continuous solutions of f n = F. Consequently, we obtain an example of an uncountable measure zero dense set of non-isolated forts in the real line. We define the notions of iteratively closed set in the space of continuous self-maps and the non-monotonicity height of any continuous self-map. We prove that continuous self-maps of non-monotonicity height 1 need not be strictly monotone on its range, unlike continuous piecewise monotone functions. Also, we obtain sufficient conditions for the existence of continuous solutions of f n = F for a class of continuous functions of non-monotonicity height 1. Further, we discuss the Hyers-Ulam stability of the iterative functional equation f n = F for continuous self-maps of non-monotonicity height 0 and 1.Item Perceptually Inspired Variational Retinex Methods for Enhancing and Restoring Images(National Institute of Technology Karnataka, Surathkal, 2021) P, Febin I.; P, Jidesh.Image restoration and enhancement are the two inevitable pre-processing activities that we come across in almost all imaging applications. Apparently, these two requirements contradict each other as one is a complement of the other. The image restoration aims at smoothing out the signal to reduce the noise interventions. On the other hand, enhancement seeks for an image with non-smooth features. Therefore, one should aim for a trade-off between these two requirements when providing a solution. Perceptually inspired frameworks have taken a considerable lead in image restoration and enhancement activities, as they seek for a visually appealing solution in addition to their excellent performance in terms of statistical quantifications. Retinex framework is being explored extensively in the literature to provide the desired enhancement to the images under consideration. This thesis provides an in-depth insight into various restoration frameworks and contributes a set of state-of-the-art restoration and enhancement models to assist the preprocessing step of various imaging applications with specific relevance to satellite and medical imaging. The degradation analysis is the primary step in an automated restoration framework. As one cannot apply a blanket restoration model for all kinds of distortions, the appropriate models are designed in due respect to the noise distribution of the input data. The second chapter of the thesis contributes a fully automated framework for analysing and detecting the noise distribution of the noise from input data. Analysis of noise distribution duly provides an insight to choose appropriate variational model to restore the images from the specific degradation analysed therein. A machine learning approach is employed to analyse the noise distribution from the input image characteristics. Various statistical and geometric features of the images are analysed to arrive at the conclusion regarding the distribution. Subsequent to the noise distribution analysis, the respective retinex based variational models are chosen to restore and enhance the images. One of the major issues with the variational models is that, they converge slowly when explicit numerical schemes are used for solving them. Many models designed under this framework use the explicit schemes due to the ease of implementation. Fast numerical implementations are one of the requirements of a realtime application model. This thesis investigates some of the fast numerical schemes such as Bregman iteration scheme redesigned for the problem under consideration to effectively solve the problems. Moreover, the computational cost is a major matter for i concern among the scientists, as most of the practically viable systems should be computationally efficient to be used under a real-time scenario. This thesis addresses this issue considerably well by employing parallel computing algorithms designed to be executed under multi-processing environments to improve the computational efficiency of the model.Item Cryptanalysis and Improvement of Remote User Authentication Schemes in Telecare Medicine Information System(National Institute of Technology Karnataka, Surathkal, 2021) Nayak, Chaitanya Sadanand.; Madhusudhan, R.The Internet with its high-speed development is making human jobs more easy and less timeconsuming. This has enabled us its usage in all the fields, right from school-going kids to professionals working for Multinational Companies. One can not even imagine a day without the Internet. When this has become the scenario today, personnel from all the fields are trying to make the best out of it and medical health people are also a part of this. The traditional methods of waiting in queues for medical consultancy has been transformed to online consultancy. A patient sitting at one part of world can consult a physician at the other end using the Internet. Medical institutes, researchers in the field are able to work with the required data by obtaining them from the medical servers, where the required information is stored. These topics constitute the connected health care. This is a model for health care that uses technology to provide medical assistance remotely. Telecare Medicine Information System (TMIS) is one such system that supports health care delivery services. The information is stored in a server and since the Internet is open to all, preserving patient’s identity and information is a very important and challenging task. In other words, authentication is most important. In past, this was easy. Two persons would identify each other by visual appearance. But at present, one cannot ’see’ the other in reality. In such case, authentication becomes very complex, specially when the message to be transmitted is confidential. To fulfill this, many authentication schemes using smart cards were and are being proposed. However, many schemes are insecure or they have low efficiency. So, proposing an ideal scheme, which is robust and efficient is the main aim of this research.Item On Dynamics of Continuous Functions(National Institute of Technology Karnataka, Surathkal, 2021) K, Chaitanya G.; Murugan, V.The discrete dynamical system of a continuous self-map is generated by iteration of the map; however, the iteration itself, being an operator on the space of continuous self-maps, may generate unusual dynamical behaviours. In this thesis, we prove that the iteration operator is continuous on the space of all continuous self-maps of a compact metric space and therefore induces a discrete dynamical system on the space. We also show how its fixed points and periodic points are determined, and characterize them in the case that the compact metric space is a compact interval or the unit circle by discussing the Babbage equation. Furthermore, we prove that all orbits of the iteration operator are bounded, but most fixed points are not stable. The boundedness and instability exhibit a complex behaviour of the iteration operation, but we prove that this complex behaviour is not chaotic in Devaney’s sense. Another complicated yet critical discrete dynamical system is that which emanates due to a continuous piecewise monotone self-map on an interval. In the kneading theory developed by Milnor and Thurston, it is proved that the kneading matrix and the kneading determinant associated with such a map are invariants under orientation-preserving conjugacy. We consider whether this result is valid for orientation-reversing conjugacy. We also present applications of obtained results towards the computational complexity of kneading matrices and the classification of maps up to topological conjugacy. Furthermore, a relation between kneading matrices of maps and their iterates for a class of chaotic maps is described. Closely related is the theory of iterative equations. There are obtained many results on solutions of such equations involving a linear combination of iterates, called polynomial-like iterative equations. We investigate an iterative equation with multiplication, a nonlinear combination of iterates, and give results on the existence, uniqueness, stability, and construction of its continuous solutions. Our study not only addresses essential problems in the theory of dynamical systems and iterative equations but also exhibits subtle interplay between these two areas.Item Radio k-Coloring and k-Distance Coloring of Graphs(National Institute of Technology Karnataka, Surathkal, 2021) K, Niranjan P.; Kola, Srinivasa Rao.The frequency assignment problem is the problem of assigning frequencies to transmitters in an optimal way and with no interference. Interference can occur if transmitters located sufficiently close to each other receive close frequencies. The frequency assignment problem motivates many graph coloring problems. Motivated by this, we study radio k-coloring and k-distance coloring of graphs. In this thesis, we study radio k-coloring of paths, trees, Cartesian product of graphs and corona of graphs; k-distance coloring of trees, cycles and cactus graphs. A radio k-coloring of a simple connected graph G is an assignment f of positive integers (colors) to the vertices of G such that for every pair of distinct vertices u and v in G, j f (u) f (v)j is at least 1+kd(u;v). The span of f , rck( f ), is the maximum color assigned by f . The radio k-chromatic number rck(G) is minfrck( f ) : f is a radio k-coloring of Gg. If d is the diameter of G, then a radio d-coloring and the radio d-chromatic number are referred as a radio coloring and the radio number rn(G) of G. Since finding the radio k-chromatic number is highly nontrivial, it is known for very few graphs and that too for some particular values of k only. For k 6, we determine the radio k-chromatic number of path Pn for 2n+1 7 k n4 if k is odd and for 2n4 5 k n5 if k is even. For some classes of trees, we obtain an upper bound for the radio k-chromatic number when k is at least the diameter of the tree. Also, for the same, we give a lower bound which matches with the upper bound when k and the diameter of the tree are of the same parity. Further, we determine the radio d-chromatic number of larger trees constructed from the trees of diameter d in some subclasses of the above classes. We determine the radio number for some classes of the Cartesian product of complete graphs and cycles. We obtain a best possible upper bound for the radio k-chromatic number of corona G H of arbitrary graphs G and H. Also, we obtain a lower bound and an improved upper bound for the radio number of Qn H and P2p+1 H. A k-distance coloring of a simple connected graph G is an assignment f of positive integers to the vertices of G such that no two vertices at distance less than or equal to k receive the same color. If a is the maximum color assigned by f , then f is referred as a k-distance a-coloring. The k-distance chromatic number ck(G) is the minimum a such that G has a k-distance a-coloring. We determine the k-distance chromatic number for trees and cycles. Also, we determine the 2-distance chromatic number of cactus graphs.