Theses supervised by Doç. Dr. İbrahim Körpeoğlu
11 theses · İhsan Doğramacı Bilkent University
Büyük ölçekli sosyal ağların büyük veri platformu kullanarak etkin analizi
In recent years, the rise of very large, rich content networks re-ignited interest to complex/social network analysis at the big data scale, which makes it possible to understand social interactions at large scale while it poses computation challenges to early works with algorithm complexity greater than O($n$). This thesis analyzes social networks at very large-scales to derive important parameters and characteristics in an efficient and effective way using big-data platforms. With the popularization of mobile phone usage, telecommunication networks have turned into a socially binding medium and enables researches to analyze social interactions at very large scales. Degree distribution is one of the most important characteristics of social networks and to study degree characteristics and structural properties in large-scale social networks, in this thesis we first gathered a tera-scale dataset of telecommunication call detail records. Using this data we empirically evaluate some statistical models against the degree distribution of the country's call graph and determine that a Pareto log-normal distribution provides the best fit, despite claims in the literature that power-law distribution is the best model. We also question and derive answers for how network operator, size, density and location affect degree distribution to understand the parameters governing it in social networks. Besides structural property analysis, community identification is of great interest in practice to learn high cohesive subnetworks about different subjects in a social network. In graph theory, $k$-core is a key metric used to identify subgraphs of high cohesion, also known as the `dense' regions of a graph. As the real world graphs such as social network graphs grow in size, the contents get richer and the topologies change dynamically, we are challenged not only to materialize $k$-core subgraphs for one time but also to maintain them in order to keep up with continuous updates. These challenges inspired us to propose a new set of distributed algorithms for k-core view construction and maintenance on a horizontally scaling storage and computing platform. Experimental evaluation results demonstrated orders of magnitude speedup and advantages of maintaining $k$-core incrementally and in batch windows over complete reconstruction approaches. Moreover, the intensity of community engagement can be distinguished at multiple levels, resulting in a multiresolution community representation that has to be maintained over time. We also propose distributed algorithms to construct and maintain a multi-$k$-core graphs, implemented on the scalable big-data platform Apache HBase. Our experimental evaluation results demonstrate orders of magnitude speedup by maintaining multi-$k$-core incrementally over complete reconstruction. Furthermore, we propose a graph aware cache system designed for distributed graph processing. Experimental results demonstrate up to 15x speedup compared to traditional LRU based cache systems.
Ev M2M ağları için IEEE 802.11 tabanlı enerji verimli ıp-bağlanabilirliği
Machine-to-machine communications (M2M) technology enables large-scale communication and networking of devices of various kinds including home devices and appliances. A critical issue for home M2M networks is how to efficiently integrate the already existing home consumer devices and appliances into an IP based wireless M2M network with least modifications to existing components. Due to its popularity and widespread usage in closed spaces, Wi-Fi is a good alternative as a wireless technology to enable M2M networking for home devices. This thesis addresses the energy-efficient integration of home appliances to a Wi-Fi and IP based home M2M network. Towards this goal, we first propose an integration architecture that requires least modifications in existing components. Then, we propose a novel long-term sleep scheduling algorithm to be applied together with the existing 802.11 power save mode (PSM). The proposed scheme utilizes the multicast DNS (mDNS) protocol to maintain device and service availability when devices go into deep sleep mode. We implemented our proposed architecture and algorithm as a prototype to build an M2M network of home appliances as a test-bed. We performed various experiments on this test-bed to evaluate the proper operation and energy savings of our proposal. We also did extensive simulation experiments for larger-scale scenarios. As a result of our test-bed and simulation experiments, we observed energy savings up to 70% compared to the existing infrastructure which applies no sleep mechanism, and up to 20% compared to standard 802.11 PSM scheme, while ensuring device and service availability at the same time.
Kablosuz algılayıcı ağlar için enerji verimli alıcı hareketlilik algoritmaları
A wireless sensor network consists of a large number of tiny sensor nodes which are capable of sensing an environment and sending the collected data to a sink node. For most scenarios, sensor nodes are powered with irreplaceable batteries and this dramatically limits the lifetime of the network, especially due to overloading of the sensor nodes neighboring sink node. Such nodes need to forward more traffic than other nodes in the network. Moving sink node and in this way distributing forwarding-load evenly among sensor nodes is one of the important techniques for improving lifetime of sensor networks. We propose different mobility algorithms for single-sink and multiple-sink mobility problem to efficiently move sink nodes through a predefined set of sink sites. We first provide packet-load and energy-load based sink mobility algorithms, called PLMA and ELMA, in which node-load parameters are incorporated into a table and this table is used to determine which sink site to visit in each round. We also give an integer programming model to get optimal results and do benchmarking. Since routing topology is an important component of sink mobility schemes, we also propose centralized and distributed routing topology construction algorithms to further increase network lifetime. Additionally, we propose an adaptive energy-load based sink movement algorithm, called A-ELMA, which does not require an initial training phase to learn about network topology. It incrementally constructs and updates energy-load table each time it visits a site location. Finally, besides proposing algorithms for single-sink mobility problem, we also propose two different algorithms for multiple-sink mobility problem. Our Multiple Sink Movement Algorithm (MSMA) is a centralized algorithm and effectively limits the sink site combinations to reduce computation and communication overhead in scheduling sink movements without harming network lifetime significantly. Our Prevent and Move Away (PMA) algorithm is a fully distributed algorithm and does not require topology information to be collected. It selects sites based on remaining energy values and distance metrics. We evaluated our algorithms and compared them to some basic approaches in the literature by conducting extensive simulation experiments. Our simulation results show that our algorithms can perform better than some other alternatives in terms of network lifetime, latency and travel distance. We also identify under which conditions our algorithms perform better for each of these metrics. We observed that our algorithms provide simple-to-use, efficient, and effective solutions for single- and multiple-sink mobility problems in wireless sensor networks.
Hedefli saldırılarda kullanılan zararlı yazılımların makine öğrenimi kullanılarak tespiti ve sınıflandırılması
Targeted attacks pose a great threat to governments and commercial entities. Increasing number of targeted attacks, especially Advanced Persistent Threats, are being discovered and exposed in each year by various cyber security organizations. Key characteristics of these attacks are well-funded and skilled actors persistently targeting specific entities, sophisticated tools and tactics, long-time presence in breached environments before detection and stealth operation. Malware plays a crucial role in a targeted attack for various tasks such as compromising systems, maintaining presence, communicating with the operators, carrying out commands, etc. Because of its stealthy nature, malware used in targeted attacks is expected to act different than the traditional malware when it is dynamically analyzed in a sandbox environment. In this thesis we focused on the malware used in targeted attacks and present a method to automatically detect and classify targeted malware through machine learning using behavioral and memory features. It's worth noting that it is a first work published in the literature that classifies targeted malware and incorporates memory features into the dynamic features. The method comprises the steps of running both traditional and targeted malware in a dynamic analysis system along with a memory analysis tool, extracting features from behavioral and memory artifacts found in analysis results and employing machine learning on the extracted features. New behavioral and memory features were defined in order to classify targeted malware more effectively. Method is then evaluated over a dataset comprised of targeted and traditional malware with different supervised learning algorithms. The results show that machine learning can be employed successfully to automatically detect and classify targeted malware from dynamic analysis results using behavioral and memory features.
Bulut bilişim sistemlerinde sanal makineler üzerinde taşıyıcılar ile yığın iş çizelgelemesi
Virtualization and use of virtual machines (VMs) is important for both public and private cloud systems and also for users. The allocation and use of virtual machines can be optimized by using knowledge about expectations of users, such as resource demands, network communication patterns, and total budget. However, both public and private cloud providers do not expose advanced configuration options to make use of custom needs of users. Adding upon to previous research, we propose a new approach for allocating and scheduling user jobs to virtual machines by use of container technologies like Docker, so that VM utilization can be increased and costs for users can be decreased. In our approach, by predicting resource demands, we can schedule different kinds of jobs on a single virtual machine without jobs affecting each other and without degrading performance to unacceptable levels. We also allow cost-performance tradeoff for users. We verified our approach in a real test-bed and evaluated it with extensive simulation experiments. We also adapted our approach into a real web-based application we developed, called PAGS (Programming Assignment Grading System), which enables efficient and convenient testing, submission and evaluation of programming assignments of a large number students in an interactive or batch manner in identical and isolated system environments. Our approach effectively schedules requests from teachers and students so that the system can horizontally scale in a cost efficient manner.
Metrik uzaylarda veri duyarlı yaklaşık sorgulama yöntemleri
Similarity searching is the task of retrieval of relevant information from datasets. We are particularly interested in datasets that contain complex and unstructured data such as images, videos, audio recordings, protein and DNA sequences. The relevant information is typically defined using one of two common query types: a range query involves retrieval of all the objects within a specified distance to the query object; whereas a k-nearest neighbor query deals with obtaining k closest database objects to the query object. A variety of index structures based on the notion of metric spaces have been offered to process these two query types.The query performances of the proposed index structures have not been satisfactory particularly for high dimensional datasets. As a solution, various approximate similarity search methods offering the users a quality/time trade-off have been proposed. The rationale is that the users might be willing to tolerate query precision to retrieve query results relatively faster. The proposed approximate searching schemes usually have strong connections to the underlying data structures, making the comparison of the quality of the essence of their ideas difficult.In this thesis we investigate various approximation approaches to decrease the response time of similarity queries. These approaches use a variety of statistics about the dataset in order to obtain dynamic (at the time of querying) and specific guidance on the approximation for each query object individually. The experiments are performed on top of a simple underlying pivot-based index structure to minimize the effects of the index to our approximation schemes. The results show that it is possible to improve the performance/precision of the approximation based on data and query object sensitive guidance.
Kablosuz algılayıcı ağlarında enerji-verimli veri yığışımı için yol atama ve zaman planlama yöntemleri
A wireless sensor network consists of nodes which are capable of sensing an environment and wirelessly communicating with each other to gather the sensed data to a central location. Besides the advantages for many applications, having very limited irreplaceable energy resources is an important shortcoming of the wireless sensor networks. In this thesis, we present effective routing and node scheduling solutions to improve network lifetime in wireless sensor networks for data gathering applications. Towards this goal, we first investigate the network lifetime problem by developing a theoretical model which assumes perfect data aggregation and power-control capability for the nodes; and we derive an upper-bound on the functional lifetime of a sensor network. Then we propose a routing protocol to improve network lifetime close to this upper-bound on some certain conditions. Our proposed routing protocol, called L-PEDAP, is based on constructing localized, self-organizing, robust and power-aware data aggregation trees. We also propose a node scheduling protocol that can work with our routing protocol together to improve network lifetime further. Our node scheduling protocol, called PENS, keeps an optimal number of nodes active to achieve minimum energy consumption in a round, and puts the remaining nodes into sleep mode for a while. Under some conditions, the optimum number can be greater than the minimum number of nodes required to cover an area. We also derive the conditions under which keeping more nodes alive can be more energy efficient. The extensive simulation experiments we performed to evaluate our PEDAP and PENS protocols show that they can be effective methods to improve wireless sensor network lifetime for data gathering applications where nodes have power-control capability and where perfect data aggregation can be used.
GridRoute: Gecikme toleranslı ağlar için çok katmanlı ağ dizge tabanlı yönlendirme protokolü
This work proposes a new routing protocol for delay-tolerant mobile networks (DTMNs) called GridRoute. The proposed protocol can be adopted considering network requirements such as low message delay or low resource usage. GridRoute is a probabilistic routing protocol that takes advantage of mobility and location information of nodes. It uses a multi-layered grid for contact probability maximization. It requires almost no memory storage of contact or location probabilities for intelligent routing decisions. GridRoute also minimizes the number of redundant messages throughout the network with feasible delay on message delivery, and provides some security advantages like identity secrecy. Our simulation results show that GridRoute outperforms existing routing protocols in terms of memory requirement. It also achieves high delivery ratio, reasonable end-to-end delay and signicantly lower message overhead.
Çok-kanallı kablosuz algılayıcı ağları için ağaç-tabanlı kanal atama yöntemleri
A lot of sensor node platforms used for establishing wireless sensor networks (WSNs) can support multiple radio channels for wireless communication. Therefore, rather than using a radio single channel and sharing it for the whole network, multiple channels can be utilized in a sensor network simultaneously to decrease the overall interference in the network, which may help increasing the aggregate throughout in the network and decrease packet collisions and delay. This requires, however, appropriate channel assignment schemes to be used for assigning channels to the nodes for multi-channel communication in the network. Since, data generated by sensor nodes are usually carried to one or more sinks in the network using routing trees, tree-based channel assignment schemes are a natural approach for assigning channels in a WSN. We present two fast tree-based channel assignment schemes (called BUCA and NCCA) for multi-channel WSNs. We also propose a new network interference metric that is used in our algorithms while making decisions. We evaluate our proposed schemes by extensive simulation experiments and compare them with another well-known tree-based protocol from the literature. The results show that our proposed algorithms can provide better performance, up to 40% performance increase in some cases, compared to the other method. We also discuss in which cases the performance improvement can be achieved.
Çok-radyolu çok-kanallı kablosuz örgüsel ağlarda girişimin incelenmesi ve azaltılması
Wireless mesh networking, which is basically forming a backbone network of mesh routers using wireless links, is becoming increasingly popular for a broad range of applications from last-mile broadband access to disaster networking or P2P communications, because of its easy deployment, self-forming, self-configuration, and self-healing properties. The multi-hop nature of wireless mesh networks (WMNs) aggravates inter-flow interference and causes intra-flow interference and severely limits the network capacity. One technique to mitigate interference and increase network capacity is to equip the mesh routers with multiple radios and use multiple channels. The radios of a mesh router can then simultaneously send or receive packets on different wireless channels. However, careful and intelligent radio resource planning, including flow-radio and channel assignment, is necessary to efficiently make use of multiple radios and channels. This first requires analyzing and modeling the nature of co-channel and adjacent channel interference in a WMN. Through real-world experiments and observations made in an indoor multi-hop multi-radio 802.11b/g mesh networking testbed we established, BilMesh, we first analyze and model the nature of co-channel and adjacent channel interference. We conduct extensive experiments on this testbed to understand the effects of using multi-radio, multi-channel relay nodes in terms of network and application layer performance metrics. We also report our results on using overlapping in addition to orthogonal channels for the radios of the mesh routers. We then turn our attention to modeling and quantifying adjacent channel interference. Extending BilMesh with IEEE 802.15.4 nodes, we propose computational methods to quantify interference between channels of a wireless communication standard and between channels of two different standards (such as Wi-Fi and ZigBee). Majority of the studies in the literature on channel assignment consider only orthogonal channels for the radios of a multi-radio WMN. Having developed quantitative models of interference, next we propose two optimization models, which use overlapping channels, for the joint flow-radio and channel assignment problems in WMNs. Then we propose efficient centralized and distributed heuristic algorithms for coupling flows and assigning channels to the radios of a WMN. The proposed centralized and distributed schemes make use of overlapping channels to increase spectrum utilization. Using solid interference and capacity metrics, we evaluate the performances of the proposed schemes via extensive simulation experiments, and we observe that our schemes can achieve substantial improvement over single-channel and random flow-radio and channel assignment schemes.
Kablosuz algılayıcı ağlar için güç kaynağı bilinçli devingen yol atama
A wireless sensor network (WSN) is a collection of sensor nodes distributed over an area of interest to accomplish a certain task by monitoring environmental and physical conditions and sending the collected data to a special node called sink. Most studies on WSNs consider nodes to be powered with irreplaceable batteries, which limits network lifetime. There are, however, perpetual power source alternatives as well, including mains electricity and energy harvesting mechanisms, which can be utilized by at least some portion of the sensor nodes to further prolong the network lifetime. Our aim here is to increase the lifetime of such WSNs with heterogeneous power sources by centralized or distributed routing algorithms that distinguish battery- and mains-powered nodes in routing, so that energy consuming tasks are carried out mostly by mains-powered nodes. We first propose a framework for a class of routing algorithms, which forms and uses a backbone topology consisting of all mains-powered nodes, including the sinks, and possibly some battery-powered nodes, to route data packets. We propose and evaluate a set of centralized algorithms based on this framework, and our simulation results show that our algorithms can increase network lifetime by up to more than a factor of two. We also propose a fully distributed power-source-aware backbone-based routing algorithm (PSABR) that favors mains-powered nodes as relay nodes. We validate and evaluate our distributed algorithm with extensive ns-2 simulations and our results show that the proposed distributed algorithm can enhance network lifetime significantly with a low control messaging overhead. Besides wireless technology independent routing solutions, we also propose a technology specific power-source-aware routing solution (PSAR) for sensor and ad hoc networks which use 802.15.4/ZigBee as the wireless technology. Our solution is fully distributed, tree-based, and traffic-adaptive. It utilizes some protocol specific properties of ZigBee, such as distributed and hierarchical address assignment, to eliminate battery-powered nodes on the routing paths as much as possible. To validate and evaluate our ZigBee-specific algorithm, we first implemented ZigBee extensions to ns-2 simulator and then implemented and simulated our protocol in this extended ns-2 environment. Our results show that the proposed algorithm operates efficiently and can increase network lifetime without increasing the path lengths significantly, compared to the default ZigBee routing algorithm.