Attack Propagation in Networks

A new model for intrusion and its propagation through various attack schemes in networks is considered. The model is characterized by the number of network nodes n, and two parameters f and g. Parameter f represents the probability of failure of an attack to a node and is a gross measure of the level of security of the attacked system and perhaps of the intruder’s skills; g represents a limit on the number of attacks that the intrusion software can ever try, due to the danger of being discovered, when it issues them from a particular (broken) network node. The success of the attack scheme is characterized by two factors: the number of nodes captured (the spread factor) and the number of virtual links that a defense mechanism has to trace from any node where the attack is active to the origin of the intrusion (the traceability factor). The goal of an intruder is to maximize both factors. In our model we present four different ways (attack schemes) by which an intruder can organize his attacks. Using analytic and experimental methods, we first show that for any 0 < f < 1, there exists a constant g for which any of our attack schemes can achieve a Θ(n) spread and traceability factor with high probability, given sufficient propagation time. We also show for three of our attack schemes that the spread and the traceability factors are, with high probability, linearly related during the whole duration of the attack propagation. This implies that it will not be easy for a detection mechanism to trace the origin of the intrusion, since it will have to trace a number of links proportional to the nodes captured.     

Radiocoloring in planar graphs: Complexity and approximations

The Frequency Assignment Problem (FAP) in radio networks is the problem of assigning frequencies to transmitters, by exploiting frequency reuse while keeping signal interference to acceptable levels. The FAP is usually modelled by variations of the graph coloring problem. A Radiocoloring (RC) of a graph G(V,E) is an assignment function such that |Φ(u)-Φ(v)|2, when u,v are neighbors in G, and |Φ(u)-Φ(v)|1 when the distance of u,v in G is two. The number of discrete frequencies and the range of frequencies used are called order and span, respectively. The optimization versions of the Radiocoloring Problem (RCP) are to minimize the span or the order. In this paper we prove that the radiocoloring problem for general graphs is hard to approximate (unless NP=ZPP) within a factor of n^1/2-ε (for any ), where n is the number of vertices of the graph. However, when restricted to some special cases of graphs, the problem becomes easier. We prove that the min span RCP is NP-complete for planar graphs. Next, we provide an O(nΔ) time algorithm (|V|=n) which obtains a radiocoloring of a planar graph G that approximates the minimum order within a ratio which tends to 2 (where Δ the maximum degree of G). Finally, we provide a fully polynomial randomized approximation scheme (fpras) for the number of valid radiocolorings of a planar graph G with λ colors, in the case where λ4Δ+50.     

Energy balanced data propagation in wireless sensor networks

We study the problem of energy-balanced data propagation in wireless sensor networks. The energy balance property guarantees that the average per sensor energy dissipation is the same for all sensors in the network, during the entire execution of the data propagation protocol. This property is important since it prolongs the network’:s lifetime by avoiding early energy depletion of sensors. We propose a new algorithm that in each step decides whether to propagate data one-hop towards the final destination (the sink), or to send data directly to the sink. This randomized choice balances the (cheap) one-hop transimssions with the direct transimissions to the sink, which are more expensive but “bypass” the sensors lying close to the sink. Note that, in most protocols, these close to the sink sensors tend to be overused and die out early. By a detailed analysis we precisely estimate the probabilities for each propagation choice in order to guarantee energy balance. The needed estimation can easily be performed by current sensors using simple to obtain information. Under some assumptions, we also derive a closed form for these probabilities. The fact (shown by our analysis) that direct (expensive) transmissions to the sink are needed only rarely, shows that our protocol, besides energy-balanced, is also energy efficient. This work has been partially supported by the IST/FET/GC Programme of the European Union under contract numbers IST-2001-33135 (CRESCCO) and 6FP 001907 (DELIS). A perliminary version of the work appeared in WMAN 2004 [11]. Charilaos Efthymiou graduated form the Computer Engineering and Informatics Department (CEID) of the University of Patras, Greece. He received his MSc from the same department with advisor in S. Nikoletseas. He currently continuous his Ph.D studies in CEID with advisor L. Kirousis. His research interest include Probabilistic Techniques and Random Graphs, Randomized Algorithms in Computationally Hard Problems, Stochastic Processes and its Applications to Computer Science. Dr. Sotiris Nikoletseas is currently a Senior Researcher and Managing Director of Research Unit 1 (“Foundations of Computer Science, Relevant Technologies and Applications”) at the Computer Technology Institute (CTI), Patras, Greece and also a Lecturer at the Computer Engineering and Informatics Department of Patras University, Greece. His research interests include Probabilistic Techniques and Random Graphs, Average Case Analysis of Graph Algorithms and Randomized Algorithms, Fundamental Issues in Parallel and Distributed Computing, Approximate Solutions to Computationally Hard Problems. He has published scientific articles in major international conferences and journals and has co-authored (with Paul Spirakis) a book on Probabilistic Techniques. He has been invited speaker in important international scientific events and Universities. He has been a referee for the Theoretical Computer Science (TCS) Journal and important international conferences (ESA, ICALP). He has participated in many EU funded R&D projects (ESPRIT/ALCOM-IT, ESPRIT/GEPPCOM). He currently participates in 6 Fifth Framework projects: ALCOM-FT, ASPIS, UNIVERSAL, EICSTES (IST), ARACNE, AMORE (IMPROVING). Jose Rolim is Full Professor at the Department of Computer Science of the University of Geneva where he leads the Theoretical Computer Science and Sensor Lab (TCSensor Lab). He received his Ph.D. degree in Computer Science at the University of California, Los Angeles working together with Prof. S. Greibach. He has published several articles on the areas of distributed systems, randomization and computational complexity and leads two major projects on the area of Power Aware Computing and Games and Complexity, financed by the Swiss National Science Foundation. Prof. Rolim participates in the editorial board of several journals and conferences and he is the Steering Committee Chair and General Chair of the IEEE Distributed Computing Conference in Sensor Systems.     

Fault-tolerant and efficient data propagation in wireless sensor networks using local,additional network information

We propose a new data dissemination protocol for wireless sensor networks, that basically pulls some additional knowledge about the network in order to subsequently improve data forwarding towards the sink. This extra information is still local, limited and obtained in a distributed manner. This extra knowledge is acquired by only a small fraction of sensors thus the extra energy cost only marginally affects the overall protocol efficiency. The new protocol has low latency and manages to propagate data successfully even in the case of low densities. Furthermore, we study in detail the effect of failures and show that our protocol is very robust. In particular, we implement and evaluate the protocol using large scale simulation, showing that it significantly outperforms well known relevant solutions in the state of the art.     

Aggregated mobility-based topology inference for fast sensor data collection

We investigate the problem of efficient data collection in wireless sensor networks where both the sensors and the sink move. We especially study the important, realistic case where the spatial distribution of sensors is non-uniform and their mobility is diverse and dynamic. The basic idea of our protocol is for the sink to benefit of the local information that sensors spread in the network as they move, in order to extract current local conditions and accordingly adjust its trajectory. Thus, sensory motion anyway present in the network serves as a low cost replacement of network information propagation. In particular, we investigate two variations of our method: a) the greedy motion of the sink towards the region of highest density each time and b) taking into account the aggregate density in wider network regions. An extensive comparative evaluation to relevant data collection methods (both randomized and optimized deterministic), demonstrates that our approach achieves significant performance gains, especially in non-uniform placements (but also in uniform ones). In fact, the greedy version of our approach is more suitable in networks where the concentration regions appear in a spatially balanced manner, while the aggregate scheme is more appropriate in networks where the concentration areas are geographically correlated. We also investigate the case of multiple sinks by suggesting appropriate distributed coordination methods.     

Efficient and Robust Protocols for Local Detection and Propagation in Smart Dust Networks

Smart Dust is a set of a vast number of ultra-small fully autonomous computing and communication devices, with very restricted energy and computing capabilities, that co-operate to quickly and efficiently accomplish a large sensing task. Smart Dust can be very useful in practice, i.e., in the local detection of a remote crucial event and the propagation of data reporting its realization. In this work we make an effort towards the research on smart dust from an algorithmic point of view. We first provide a simple but realistic model for smart dust and present an interesting problem, which is how to propagate efficiently information on an event detected locally. Then we present various smart dust protocols for local detection and propagation that are simple enough to be implemented on real smart dust systems, and perform, under some simplifying assumptions, a rigorous average case analysis of their efficiency and energy consumption (and their interplay). This analysis leads to concrete results showing that our protocols are very efficient and robust. We also validate the analytical results by extensive experiments.     

Expander properties and the cover time of random intersection graphs

We investigate important combinatorial and algorithmic properties of _Gn,m,p$G_{n,m,p}$ random intersection graphs. In particular, we prove that with high probability (a) random intersection graphs are expanders, (b) random walks on such graphs are “rapidly mixing” (in particular they mix in logarithmic time) and (c) the cover time of random walks on such graphs is optimal (i.e. it is Θ(nlogn)$\Theta (nlogn)$). All results are proved for p$p$ very close to the connectivity threshold and for the interesting, non-trivial range where random intersection graphs differ from classical _Gn,p$G_{n,p}$ random graphs.     

Efficient sensor network design for continuous monitoring of moving objects

We study the problem of localizing and tracking multiple moving targets in wireless sensor networks, from a network design perspective i.e. towards estimating the least possible number of sensors to be deployed, their positions and operation characteristics needed to perform the tracking task. To avoid an expensive massive deployment, we try to take advantage of possible coverage overlaps over space and time, by introducing a novel combinatorial model that captures such overlaps.