Catálogo de publicaciones - libros

We show that face routing, the well-known local routing algorithm for plane graphs introduced by Kranakis and Urrutia, does not in fact succeed for embedded graphs on the torus or higher genus surfaces (contrary to conjecture). We then describe a generalization of face routing, and prove that this algorithm does provide a local routing algorithm for arbitrary graphs embedded in the torus. Finally we discuss extension of this type of algorithm to surfaces of genus g, describing the problems encountered in this setting.

We present a distributed topology control protocol that runs on a -QUDG for  ≥ 1/, and computes a sparse, constant-spanner, both in Euclidean distance and in hop distance. QUDGs (short for Quasi Unit Disk Graphs) generalize Unit Disk Graphs and permit more realistic modeling of wireless networks, allowing for imperfect and non-uniform transmission ranges as well as uncertain node location information.Our protocol is local and runs in (1) rounds. The output topology permits memoryless (geographic) routing with guaranteed delivery. In fact, when our topology control protocol is used as preprocessing step for the geographic routing protocol GOAFR, we get the routing time guarantee of () for any source-destination pair that are units away from each other in the input d-QUDG. The key idea is simple: to obtain planarity, we replace each edge intersection with a and have a real node serve as a proxy for the virtual node. This idea is supported by other parts of our protocol that (i) use clustering to keep the density of edge crossings bounded and (ii) guarantee that an edge between a virtual node and a neighbor is realized by a constant-hop path in the real network. The virtual node idea is simple enough to be useful in many contexts. For example, it can be combined with a scheme recently suggested by Funke and Milosavljević (INFOCOM 2007) to guarantee delivery under uncertain node locations. Similarly, the virtual nodes idea can also be used as a cheap alternative to edge-crossing removal schemes suggested by Kim et al. (DIALM-POMC 2005, SENSYS 2006).

Sensor networks are wireless adhoc networks where all the nodes cooperate for routing messages in the absence of a fixed infrastructure. Non-flooding, guaranteed delivery routing protocols are preferred because sensor networks have limited battery life. Location aware routing protocols are good candidates for sensor network applications, nevertheless they need either an external location service like GPS or Galileo (which are bulky, energy consuming devices) or internal location services providing non-unique virtual coordinates leading to low delivery rates. In this paper we introduce a collision free, distributed labeling algorithm based on hop counting, which embed a spanning tree of the underlying network . The Routing with Position Trees (RTP) is a guaranteed delivery, non-flooding, efficient implicit routing protocol based on Position Trees. We study experimentally the statistical properties of memory requirements and the routing efficiency of the RPT.

OLSR is a proactive routing protocol for mobile ad hoc networks. In OLSR, each node collects two-hop neighbourhood information and periodically sends topology control (TC) messages to update the link state. Rather than sending TC messages periodically, at each interval each node: (1) monitors of its two-hop neighbourhood graph; (2) if the measure is in-control no message is sent, otherwise a TC message is sent. Betweenness, a measure of centrality in a graph first used in social and biological network analysis, appears to correspond closely to the multi-point relay sets of OLSR. Hence a significant change in betweenness indicates a significant change in topology. Using this approach the control overhead in OLSR is reduced by 35-40%, with a corresponding savings in energy, and little impact on throughput or delay.

We present a distributed algorithm for finding a (1 + )-approximation of a in the class of , which includes . In addition, the computed Connected Dominating Set guarantees a constant stretch factor on the length of a shortest path with respect to the original graph and induces a subgraph of constant degree. The nodes do not require any positioning or distance information.

The algorithm runs in synchronous rounds, where is the time for computing a Maximal Independent Set (MIS) in the network graph. Using the fastest known deterministic algorithm for computing a MIS, the total running time is , where is the maximum degree of the network graph. If one allows randomization, the running time reduces to rounds.

We study the algorithmic problem of coordinating transmissions in a wireless network where radio interference constrains concurrent transmissions on wireless links. We focus on pairwise conflicts between the links; these can be described as a conflict graph. Associated with the conflict graph are two fundamental network coordination tasks: (a) finding a nonconflicting set of links with the maximum total weight, and (b) finding a link schedule with the minimum total length. Our work shows that two assumptions on the geometric structure of conflict graphs suffice to achieve polynomial-time constant-factor approximations: (i) bounded density of devices, and (ii) bounded range of interference. We also show that these assumptions are not sufficient to obtain a polynomial-time approximation scheme for either coordination task.

The in-network aggregation and processing of information is what sets a sensor network apart from a pure data acquisition device. One way to model the exchange of information between the network nodes is to distinguish between nodes that are of information, i.e., those that have collected data, detected events, etc., and nodes that are of information, i.e., nodes that seek data or events of certain types. In this paper we aim to support that exchange of information via a so-called scheme. Main features of our proposed scheme are that 1) it works in a location-free setting where nodes are unaware of their geographic locations 2) it is robust to non-regular network topologies and 3) it does not require the information producers and consumers to know of each other. Our proposed scheme employs boundary detection algorithms which only quite recently have been developed to extract geometry and topology information even in location-free network deployments.

We develop level set estimation algorithms for a novel low cost sensor network architecture, where sensors are mounted on agents moving without an explicit objective of sensing. A level set in a planar scalar field is the set of points with field values greater than or equal to a specified value. We model the problem as a classification problem and evaluate a heuristic to reduce the amount of communication assuming that the base station uses a Support Vector Machine classifier. We then develop a fully distributed, low complexity solution which uses opportunistic information exchange to estimate level set boundaries locally at nodes selected using leader election. We observe that the learning rates of the boundary in a locality is proportional to the complexity. Effectiveness of the proposed scheme is evaluated using simulations with data from both synthetic and measured fields. Random way point mobility model is used for node motion and trade off of accuracy and of coverage with communication costs is studied.

In a broadcasting task, a source sends a message to all the nodes of a network. There exist methods for flooding a network intelligently and for scheduling node activities. Dominating sets and neighbor elimination based broadcasting is currently the most efficient broadcasting scheme in terms of the number of retransmitted messages to complete a broadcast. It provides basis for defining other broadcasting protocols by changing the definition of the delay (timeout) function used to decide how long a dominating node should wait before making a retransmission. In this article, we propose thirteen such variants. They are all reliable, meaning that all the nodes connected to a source will receive the message, assuming an ideal MAC layer. Eight of them are hexagonal based; four are distance-based, giving priority to the neighbors that are further or nearer from the retransmitting node; and one is using a random timeout. Beyond these variants, we propose three different ways to update the timeout values during a broadcasting process. Our experimental data shows that the updating process of the timeout values has no significant impact compared to the selected timeout function. From the thirteen variants we deliberately proposed some worst-case timeout functions to see its impact in the broadcasting process. We confirm by our experimental data that indeed the selected timeout function has an impact in the broadcasting process. Although our experimental data shows that the new further distance-based scheme outperforms almost all schemes in terms of number of messages to complete a broadcast, it also shows that a random function (the way IEEE 802.11 works) is a very good choice.

The success of authentication mechanisms, intrusion detection and response systems, and other security measures to protect MANET from attack are very much dependant on nodes’ cooperation. Ensuring a node’s cooperation is very challenging in a MANET environment because of the nature of such a network; consisting of a set of anonymous nodes that operate independently, without the existence of a central authority to enforce them to cooperate. One of the solutions for this problem is by creating a trust chain between nodes to create a trusted community. This paper discusses some of the existing studies that have been proposed to overcome this issue and proposes a novel trust framework based upon a friendship concept. Results from simulation experiments proved that the proposed trust framework is capable of creating a trusted community in MANET, whilst at the same time addressing limitations of existing trust frameworks.