Search

Two robots stand at the origin of the infinite line and are tasked with searching collaboratively for an exit at an unknown location on the line. They can travel at maximum speed $b$ and can change speed or direction at any time. The two robots can communicate with each other at any distance and at any time. The task is completed when the last robot arrives at the exit and evacuates. We study time-energy tradeoffs for the above evacuation problem. The evacuation time is the time it takes the last robot to reach the exit. The energy it takes for a robot to travel a distance $x$ at speed $s$ is measured as $xs^2$. The total and makespan evacuation energies are respectively the sum and maximum of the energy consumption of the two robots while executing the evacuation algorithm. Assuming that the maximum speed is $b$, and the evacuation time is at most $cd$, where $d$ is the distance of the exit from the origin, we study the problem of minimizing the total energy consumption of the robots. We prove that the problem is solvable only for $bc \geq 3$. For the case $bc=3$, we give an optimal algorithm, and give upper bounds on the energy for the case $bc>3$. We also consider the problem of minimizing the evacuation time when the available energy is bounded by $\Delta$. Surprisingly, when $\Delta$ is a constant, independent of the distance $d$ of the exit from the origin, we prove that evacuation is possible in time $O(d^{3/2}\log d)$, and this is optimal up to a logarithmic factor. When $\Delta$ is linear in $d$, we give upper bounds on the evacuation time., Comment: This is the full version of the paper with the same title which will appear in the proceedings of the 26th International Colloquium on Structural Information and Communication Complexity (SIROCCO'19) L'Aquila, Italy during July 1-4, 2019

Assume that \(m \ge 1\) autonomous mobile agents and \(0 \le b \le m\) single-agent transportation devices (called bikes) are initially placed at the left endpoint 0 of the unit interval [0, 1]. The agents are identical in capability and can move at speed one. The bikes cannot move on their own, but any agent riding bike i can move at speed \(v_i > 1\). An agent may ride at most one bike at a time. The agents can cooperate by sharing the bikes; an agent can ride a bike for a time, then drop it to be used by another agent, and possibly switch to a different bike.

Two robots stand at the origin of the infinite line and are tasked with searching collaboratively for an exit at an unknown location on the line. They can travel at maximum speed b and can change speed or direction at any time. The two robots can communicate with each other at any distance and at any time. The task is completed when the last robot arrives at the exit and evacuates. We study time-energy tradeoffs for the above evacuation problem. The evacuation time is the time it takes the last robot to reach the exit. The energy it takes for a robot to travel a distance x at speed s is measured as \(xs^2\). The total and makespan evacuation energies are respectively the sum and maximum of the energy consumption of the two robots while executing the evacuation algorithm.

We consider the problem of monitoring the Euclidean plane using rotating sensors with detection sectors and beam sensors. We assume that intruders can appear anywhere at any time and move arbitrarily fast, and may have full knowledge of the sensor network. We require that such intruders be detected within a finite amount of time. We give an optimal network for this problem consisting of a combination of rotating sensors of angle 0 and beam sensors that uses the minimum number of both types of sensors. We show a trade-off between the density of beam sensors needed and the angle of the detection sector of the rotating sensors. Secondly, we give a family of sensor networks using only rotating sensors for the same problem, that demonstrate a trade-off between the detection time and the density of rotating sensors used. We show that the density of rotating sensors required in this case can be significantly reduced by increasing the angle of detection sectors. Finally, we show that our results on the infinite plane can be used to derive sensor networks that monitor some finite regions using a density of sensors that is asymptotically the same, or close to that of the infinite plane case.

We consider the problem of fault-tolerant parallel search on an infinite line by $n$ robots. Starting from the origin, the robots are required to find a target at an unknown location. The robots can move with maximum speed $1$ and can communicate in wireless mode among themselves. However, among the $n$ robots, there are $f$ robots that exhibit {\em byzantine faults}. A faulty robot can fail to report the target even after reaching it, or it can make malicious claims about having found the target when in fact it has not. Given the presence of such faulty robots, the search for the target can only be concluded when the non-faulty robots have sufficient verification that the target has been found. We aim to design algorithms that minimize the value of $S_d(n,f)$, the time to find a target at a distance $d$ from the origin by $n$ robots among which $f$ are faulty. We give several different algorithms whose running time depends on the ratio $f/n$, the density of faulty robots, and also prove lower bounds. Our algorithms are optimal for some densities of faulty robots., 14 pages

Due to the limited lifetime of the nodes in ad hoc network, energy efficiency needs to be an important design consideration in any routing algorithm for ad hoc and sensor networks. In most of the existing position-based routing algorithms the nodes use the maximum transmission power to discover neighbors, which may cause excessive power consumption. This paper presents several localized power-aware 3D position-based routing algorithms that increase the lifetime of a network by maximizing the average lifetime of its nodes. New algorithms are semi-beaconless, using for neighbor discovery an optimal transmission range (OR) for control packets, and, if needed, maximal transmission range (MR) during routing process, and using adjusted transmission radius for message transmission. PAGR algorithm selects neighbor closest to destination among those within OR if any exists providing progress, or otherwise among those within MR. If greedy progress is not possible, PAGR:CFace(1) variant resorts to face routing on projected network in coordinate plane until recovery is possible, at which point PAGR algorithm resumes. We evaluate our algorithms and compare their power savings with the current power-aware routing algorithms. The simulation results show a significant improvement in the overall network lifetime.

Position-based routing algorithms use the geographic position of the nodes in a network to make the forwarding decisions. Recent research in this field primarily addresses such routing algorithms in two dimensional (2D) space. However, in real applications, nodes may be distributed in three dimensional (3D) environments. In this paper, we propose several randomized position-based routing algorithms and their combination with restricted directional flooding-based algorithms for routing in 3D environments. The first group of algorithms AB3D are extensions of previous randomized routing algorithms from 2D space to 3D space. The second group ABLAR chooses m neighbors according to a space-partition heuristic and forwards the message to all these nodes. The third group T-ABLAR-T uses progress-based routing until a local minimum is reached. The algorithm then switches to ABLAR for one step after which the algorithm switches back to the progress-based algorithm again. The fourth group AB3D-ABLAR uses an algorithm from the AB3D group until a threshold is passed in terms of number of hops. The algorithm then switches to an ABLAR algorithm. The algorithms are evaluated and compared with current routing algorithms. The simulation results on unit disk graphs (UDG) show a significant improvement in delivery rate (up to 99%) and a large reduction of the traffic.

We consider all-to-all routing problem in an optical ring network that uses the wavelength-division multiplexing (WDM). Since 1-hop, all-to-all optical routing in a WDM optical ring of n nodes needs ⌈½⌊n2/4⌋⌉ wavelengths (see Efficient Collective Communication in Optical Networks, Lecture Notes in Computer Science, Vol. 1099, Springer, Berlin, 1996, pp. 574-585), which can be too large even for moderate values of n, we consider in this paper j-hop implementations of all-to-all routing in a WDM optical ring, j ≥ 2. From among the possible routings we focus our attention on uniform routings, in which each node of the ring uses the same communication pattern and the communication load is distributed evenly among the nodes. We show that there exists a uniform 2-hop implementation of all-to-all routing that needs at most (n/4)(3√n+ 3) wavelengths. This value is within multiplicative constants of a lower bound. We then give a uniform 3-hop, 4-hop implementation of all-to-all routing that needs at most (n/2)(7√n/16 + 3), (n/2)(15√n/2 + 6) wavelengths, respectively.

Several papers considered the problem of routing in ad hoc wireless networks using the positions of the mobile hosts. Perimeter routing1, 2 gives an algorithm that guarantees delivery of messages in such networks without the use of flooding of control packets. However, this protocol is likely to fail if the transmission ranges of the mobile hosts vary because of natural or man-made obstacles. It may fail because either some connections are not considered, which effectively results in a disconnection of the network, or because some crossing connections are used, which could misdirect the message. In this paper, we describe a robust routing protocol, a variant of perimeter routing, which tolerates up to 40% of variation in the transmission ranges of the mobile hosts. More precisely, our protocol guarantees message delivery in a connected ad hoc wireless network without the use of message flooding whenever the ratio of the maximum transmission range to the minimum transmission range is at most √2. Copyright © 2003 John Wiley & Sons, Ltd.

Cooperation between mobile robots and wireless sensor networks is a line of research that is currently attracting a lot of attention. In this context, we study the following problem of barrier coverage by stationary wireless sensors that are assisted by a mobile robot with the capacity to move sensors. Assume that \(n\) sensors are initially arbitrarily distributed on a line segment barrier. Each sensor is said to cover the portion of the barrier that intersects with its sensing area. Owing to incorrect initial position, or the death of some of the sensors, the barrier is not completely covered by the sensors. We employ a mobile robot to move the sensors to final positions on the barrier such that barrier coverage is guaranteed. We seek algorithms that minimize the length of the robot’s trajectory, since this allows the restoration of barrier coverage as soon as possible. We give an optimal linear-time offline algorithm that gives a minimum-length trajectory for a robot that starts at one end of the barrier and achieves the restoration of barrier coverage. We also study two different online models: one in which the online robot does not know the length of the barrier in advance, and the other in which the online robot knows it in advance. For the case when the online robot does not know the length of the barrier, we prove a tight bound of \(3/2\) on the competitive ratio, and we give a tight lower bound of \(5/4\) on the competitive ratio in the other case. Thus for each case we give an optimal online algorithm.

Broadcasting has been used in mobile ad hoc networks to send a piece of data to every node throughout the network. Using a simple flooding scheme for such purpose causes redundant rebroadcasting at some nodes. Most approaches developed in the literature assume nodes are aware of the topological changes of the network via beacon messages, which cause an overhead. To address redundant broadcasting at some nodes as well as the inefficiency of the use of beacon messages, in this work we propose a beacon-less broadcasting algorithm for MANETs, where we prove every node in the network receives the message. We also give analysis of our algorithm presenting lower and upper bounds on the number of forwarding nodes.

We consider the problem of routing in networks employing all-optical routing technology. In such networks, information between nodes of the network is transmitted as light on fiber-optic lines without being converted to electronic form in between. We consider switched optical networks that use the wavelength-division multiplexing (or WDM) approach. A WDM network consists of nodes connected by point-to-point fiber-optic links, each of which can support a fixed number of wavelengths. The switches are capable of redirecting incoming streams based on wavelengths, without changing the wavelengths. Different messages may use the same link concurrently if they are assigned distinct wavelengths. However, messages assigned the same wavelength must be assigned edge-disjoint paths. Given a communication instance in a network, the optical routing problem is the assignment of {routes} to communication requests of the instance, as well as wavelengths to routes so that the number of wavelengths used by the instance is minimal. We focus on the all-to-all communication instance I A in a widely studied family of chordal rings of degree 4, called optimal chordal rings . For these networks, we prove exact bounds on the optimal load induced on an edge for I A , over all shortest-path routing schemes. We show an approximation algorithm that solves the optical routing problem for I A using at most 1.006 times the lower bound on the number of wavelengths. The previous best approximation algorithm has a performance ratio of 8. Furthermore, we use a variety of novel techniques to achieve this result, which are applicable to other communication instances and may be applicable to other networks.

We consider the k-barrier coverage problem, that is, the problem of deploying sensors on a border or perimeter to ensure that any intruder would be detected by at least k sensors. With random deployment of sensors, there is always a chance of gaps in coverage, thereby necessitating multiple rounds of deployment. In this paper, we study multi-round wireless sensor deployment on a border modeled as a line segment. We present two different classes of deployment strategies: complete and partial. In complete strategies, in every round, sensors are deployed over the entire border segment, while in partial strategies, sensors are deployed over only some part(s) of the border. First, we analyze the probability of k-coverage for any complete strategy as a function of parameters such as length of barrier to be covered, the width of the intruder, the sensing range of sensors, as well as the density of deployed sensors. Second, we propose two specific deployment strategies - Fixed-Density Complete and Fixed-Density Partial - and analyze the expected number of deployment rounds and expected total number of deployed sensors for each strategy. Next, we present a model for cost analysis of multi-round sensor deployment and calculate, for each deployment strategy, the expected total cost as a function of problem parameters and density of sensor deployment. Finally we find the optimal density of sensors in each round that minimizes the total expected cost of deployment for each deployment strategy. We validate our analysis by extensive simulation results.

We consider the problem of monitoring the Euclidean plane using rotating sensors with detection sectors and beam sensors. We assume that intruders can appear anywhere at any time and move arbitrarily fast, and may have full knowledge of the sensor network. We require that such intruders be detected within a finite amount of time. We give an optimal network for this problem consisting of a combination of rotating sensors and beam sensors that uses the minimum number of both types of sensors. We show a trade-off between the density of beam sensors needed and the angle of the detection sector of the rotating sensors. Secondly, we give a family of sensor networks using only rotating sensors for the same problem, that demonstrate a trade-off between the detection time and the density of rotating sensors used. We show that the density of rotating sensors required in this case can be significantly reduced by increasing the width of detection sectors. Finally, we show that our results on the infinite plane can be used to derive sensor networks that monitor some finite regions using the same asymptotic density of sensors as in the infinite plane case.

We prove that, for any p≤d, there exists a spanning directed p-ary tree of depth at most D⌈logpd⌉; in a de Bruijn digraph B(d,D) or in a Kautz digraph K(d,D) of degree d and diameter D. This result gives directly an upper bound of pD⌈logpd⌉ on the broadcast time of these digraphs, which improves the previously known bounds for d≥15. In the case of de Bruijn digraphs, an upper bound on the broadcast time of B(pq,D) in terms of the broadcast times of B(p,D) and B(q,D) is established. This is used to improve the upper bounds on the broadcast time of B(d,D). We obtain several results which are refinements of the following general statements: 1. (i) for any D⩾2, d⩾2, if 2 kl k , b(B(d, D))⩽( 5 4 k+3)D . 2. (ii) for any k⩾3, if 2k 1

The dynamic nature of mobile ad hoc networks makes it difficult to consider a specific model for their topology which might change in a short period of time. Using the knowledge about the location of nodes, several relatively efficient position based routing algorithms have been proposed but almost all of them are sensitive to the network topology. Ant colony optimization based routing algorithms form another family of routing algorithms that usually converge to optimum routes. In our previous work we proposed POSANT, a position based ant colony routing algorithm for mobile ad-hoc networks. Although POSANT outperforms other routing algorithms in most cases, there are network topologies in which POSANT does not perform well. In this paper we introduce HybNet, a hybrid ant colony optimization based routing algorithm for mobile ad hoc networks which adapts itself to different network topologies. We carry out an empirical analysis of the performance of our algorithm and compare it with other routing algorithms. Our results show that HybNet almost always performs efficiently, even in some complex and variable network topologies.

Position based routing algorithms use the knowledge of the position of nodes for routing of packets in mobile ad-hoc networks. Previously proposed position based routing algorithms may fail to find a route from a source to a destination in some types of ad-hoc networks and if they find a route, it may be much longer than the shortest path. On the other hand, routing algorithms which are based on ant colony optimization find routing paths that are close in length to the shortest paths. The drawback of these algorithms is the large number of control messages that needs to be sent or the long delay before the routes are established from a source to a destination. In this paper we propose a new reactive routing algorithm for mobile ad hoc networks, called POSANT (Position based Ant Colony Routing Algorithm), which combines the idea of ant colony optimization with information about the position of nodes. In contrast to the other ant colony optimization based routing algorithms, our simulations show that POSANT has a relatively short route establishment time while using a small number of control messages which makes it a scalable reactive routing algorithm.

A crucial problem in ad hoc networks is finding an efficient and correct route between a source and a destination; however for many networks, a more important problem is providing an energy efficient route because of, for example, the limited battery life of the wireless nodes. Most previous routing protocols make the routing decision without taking into account the energy budget of the nodes. In addition, when using a fixed transmission power, nodes may waste power by transmitting with more power than is needed for correct reception. In position- based routing algorithms, the nodes use the geographical position of the nodes to make the routing decisions. In this paper we present several localized power-aware 3D position-based routing algorithms that increase the life-time of the network by maximizing the life time of the nodes. These new algorithms use the idea of replacing the constant transmission power of the node with an adjusted transmission power during two stages - first a lower power while discovering the neighboring nodes, and, if needed, a second higher transmission power during the routing process. We evaluate our algorithms and compare their power savings with the current power-aware routing algorithms. The simulation results show a significant improvement in the energy saving (up to 50%).

We present a novel 3D routing algorithm, adaptive least-squares protective FACE routing algorithm, for wireless mobile ad hoc networks. This algorithm is based on three heuristics, least-squares projection (LSP) plane, adaptive behavior scale (ABS) and multi-projection-plane strategy, as well as the algorithm of projective FACE routing on two orthogonal planes. The resultant algorithm of adaptive least-squares projective FACE routing with 16 or more projection planes available gives nearly certain delivery, e.g. a 100% delivery rate shown by our simulations, on the unit disk graph (UDG). We also provide a comparison of performance for routing in 2D and in 3D. Two randomized versions, half-space partition and quadrant-space partition, of certain deterministic routing algorithms are also proposed to accommodate randomized routing in 3D

In position-based routing algorithms for ad-hoc networks, the nodes use the geographical information to make the routing decisions. Recent research in this field primarily addresses such routing algorithms in two dimensional space (2D). However, in real applications, nodes may be distributed in 3D space. In this paper we extend previous randomized routing algorithms from 2D space to 3D space, and we propose two new position-based routing algorithms that combine randomized AB3D routing algorithms with a deterministic CFace (coordinate face) algorithm. The first algorithm AB3D-CFace(1)-AB3D starts with AB3D routing algorithm until a local minimum is reached. The algorithm then switches to CFace routing using one projected coordinate. IfCFace(l) enters a loop, the algorithm switches back to AB3D. The second algorithm AB3D-CFace(3) starts with AB3D, until a local minimum is reached. The algorithm then permanently switches to CFace routing using three projected coordinates, in order. We evaluate our mechanisms and compare them with the current routing algorithms. The simulation results show the significant improvement in delivery rate over pure AB3D randomized routing (97% compared to 70%) and reduction in path dilation (up to 50%) over pure CFace algorithm.

Position-based routing algorithms use the location information to reduce routing overhead in mobile ad-hoc networks. In this paper we propose two position-based routing algorithms which combine progress-based routing with restricted directional flooding-based routing algorithms for routing in 3 dimensional environments (3D). The first algorithm 3D_ABLAR(m) chooses m neighbors according to a space-partition heuristic and forwards the message to all these nodes. The second algorithm (C, G)-3D ABLAR(m)-(C, G) uses progress-based routing until a local minimum is reached. The algorithm then switches to the first algorithm for one step and then progress-based routing is resumed. We evaluate our algorithm and compare it with current routing algorithms. The simulation results show a significant improvement in delivery rate (99% compared to 63%) and reduction in traffic (up to 50%).

Summary form only given. The problem of traversal of planar subdivisions or other graph-like structures without using mark bits is central to many real-world applications. The first such algorithms were able to traverse triangulated subdivisions. Later these algorithms were extended to traverse vertices of an arrangement or a convex polytope. The research progress culminated in an algorithm that can traverse any planar subdivision. We extend the notion of planar subdivision to quasiplanar subdivision in which we allow many edges to cross each other. We describe an algorithm to traverse any quasiplanar subdivision that satisfies a simple requirement. The worst case running time of our algorithm is O(|E| log |E|), which matches the running time of the traversal algorithm for planar subdivisions.

We consider all-to-all routing problem in an optical ring network that uses the wavelength-division multiplexing (WDM). Since one-hop, all-to-all optical routing in a WDM optical ring of n nodes needs \(\stackrel{\rightarrow}{w}(C_n,I_A,1)= \lceil \frac{1}{2}\lfloor \frac{n^2}{4}\rfloor\rceil\) wavelengths which can be too large even for moderate values of n, we consider in this paper j -hop implementations of all-to-all routing in a WDM optical ring, j ≥ 2. ?’From among the possible routings we focus our attention on uniform routings, in which each node of the ring uses the same communication pattern. We show that there exists a uniform 2-hop, 3-hop, and 4-hop implementation of all-to-all routing that needs at most \(\frac{n+3}{3}\sqrt{\frac{n+16}{5}} + \frac{n}{4}\), \( \frac{n}{2}\sqrt[3]{\frac{\lceil n/4 \rceil+4}{5}}\), and \(\frac{n+16}{2}\sqrt[4]{\lceil \frac{n}{4}\rceil+8}\) wavelengths, respectively. These values are within multiplicative constants of lower bounds.

Consider a synchronous system of clients and servers whereby client requests may be satisfied by any one of the servers the clients are assigned to and where the association between clients and servers is determined by an arbitrary but predefined apportionment of the set of servers to clients and of clients to servers. A client can get the required service from any of the servers it is assigned to and at each time step all clients make a request to the servers which then provide the service according to requests. Since clients can make requests simultaneously, if there is no coordination in the "client-to-server" assignment process some clients may have to wait longer if they are assigned simultaneously to a single server when overall performance could improve had they been assigned to separate available servers. Therefore a principal approach to optimizing throughput when assigning client requests to supporting servers, is to keep the client queue sizes well balanced so as to prevent servers from having to remain idle while other servers are being overused. There are several potential examples of such systems involving data gathering and forwarding among sensors in a sensor network or when the servers are base-stations and the clients may be either rotating satellites or other wireless devices, for example. In this paper we consider the problem of finding an assignment of clients to servers that results in all clients receiving a packet while optimally balancing the sizes of remaining queues at the clients. We give a polynomial time algorithm for solving this problem which requires O((m + n)3n) arithmetic operations, where m is the number of client queues and n is the number of servers.

The problem of traversal of planar subdivisions or other graph-like structures without using mark bits is central to many real-world applications [7, 8, 11, 12, 13, 17, 18]. The first such algorithms developed were able to traverse triangulated subdivisions [10]. Later these algorithms were extended to traverse vertices of an arrangement or a convex polytope [3]. The research progress culminated to an algorithm that can traverse any planar subdivision [6, 9]. In this paper, we extend the notion of planar subdivision to quasi-planar subdivision in which we allow many edges to cross each other. We generalize the algorithm from [9] to traverse any quasi-planar subdivision that satisfies a simple geometric requirement. If we use techniques from [6] the worst case running time of our algorithm is O(|E| log |E|); matching the running time of the traversal algorithm for planar subdivisions [6].

International audience; 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 {\em Position Trees} 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.