Abstract Recently, strategic games inspired by Schelling’s influential model of residential segregation have been studied in the TCS and AI literature. In these games, agents of k different types occupy the nodes of a network topology aiming to maximize their utility, which is a function of the fraction of same-type agents they are adjacent to in the network. As such, the agents exhibit similarity-seeking strategic behavior. In this paper, we introduce a class of strategic jump games in which the agents are diversity-seeking : The utility of an agent is defined as the fraction of its neighbors that are of different type than itself. We show that in general it is computationally hard to determine the existence of an equilibrium in such games. However, when the network is a tree, diversity-seeking jump games always admit an equilibrium assignment. For regular graphs and spider graphs with a single empty node, we prove a stronger result: The game is potential, that is, the improving response dynamics always converge to an equilibrium from any initial placement of the agents. We also show (nearly tight) bounds on the price of anarchy and price of stability in terms of the social welfare (the total utility of the agents).

Renting servers in the cloud is a generalization of the bin packing problem , motivated by job allocation to servers in cloud computing applications. Jobs arrive in an online manner, and need to be assigned to servers; their duration and size are known at the time of arrival. There is an infinite supply of identical servers, each having one unit of computational capacity per unit of time. A server can be rented at any time and continues to be rented until all jobs assigned to it finish. The cost of an assignment is the sum of durations of rental periods of all servers. The goal is to assign jobs to servers to minimize the overall cost while satisfying server capacity constraints. We focus on analyzing two natural algorithms, NextFit and FirstFit , for the case of jobs of equal duration. It is known that the competitive ratio of NextFit and FirstFit are at most 3 and 4 respectively for this case. We prove a tight bound of 2 on the competitive ratio of NextFit . For FirstFit , we establish a lower bound of ≈ 2 . 519 on the competitive ratio, even when jobs have only two distinct arrival times 0 and t . Using the weight function technique, we show that this bound is almost tight when there are only two arrival times; we obtain an upper bound of 2.565 on the asymptotic competitive ratio of FirstFit . In fact, we show an upper bound of 168 131 ( 1 + t ) on the asymptotic competitive ratio for any t > 0 . 559 . For the case when jobs have arrival times 0 and 1 and duration 2, we show a lower bound of ≈ 1 . 89 and an upper bound of 2 on the strict competitive ratio of FirstFit . Finally, we show an upper bound of 3 / 2 on the competitive ratio of long-running uniform servers.

Access to a topological map is important to network management. Autonomic Networks have been developed, in part, because they provide a convenient, secure platform for the development of operations, administration and management (OAM) applications, and because they make it possible to substantially reduce the need for human input in many network management situations. Using the definition of Autonomic Networks that has been developed by the Network Management Research Group of the IRTF, and standardized by the ANIMA Working Group of the IETF, we present two methods for discovering and maintaining topological information within an Autonomic Network domain. Our first method is highly distributed, and is based on clustering, while the second method is more centralized, and takes advantage of the already-defined procedure for securely initializing the Autonomic Network. We implemented both solutions on a testbed configured with three different topologies. We report the relative performance of the proposed methods.

A fixed schedule dynamic network has a set of nodes (eg. vehicles or satellites) that move using a known schedule and trajectory, so that the connections between nodes in the network appear and disappear in a predictable manner. We study the problem of finding a foremost journey in such a network: given a query time, source and destination node, we find a temporal path that arrives at the earliest time at the destination. We give a new approach to the problem that uses a timetable sorted in order of the start time of connections, and describe three algorithms using this approach. We prove their correctness and give tight bounds on their worst-case time complexities. We also show extensive experimental results that show that our new algorithms outperform the previous best algorithm given in [1].

We consider evacuation of a group of $n \geq 2$ autonomous mobile agents (or robots) from an unknown exit on an infinite line. The agents are initially placed at the origin of the line and can move with any speed up to the maximum speed $1$ in any direction they wish and they all can communicate when they are co-located. However, the agents have different wireless communication abilities: while some are fully wireless and can send and receive messages at any distance, a subset of the agents are senders, they can only transmit messages wirelessly, and the rest are receivers, they can only receive messages wirelessly. The agents start at the same time and their communication abilities are known to each other from the start. Starting at the origin of the line, the goal of the agents is to collectively find a target/exit at an unknown location on the line while minimizing the evacuation time, defined as the time when the last agent reaches the target. We investigate the impact of such a mixed communication model on evacuation time on an infinite line for a group of cooperating agents. In particular, we provide evacuation algorithms and analyze the resulting competitive ratio ($CR$) of the evacuation time for such a group of agents. If the group has two agents of two different types, we give an optimal evacuation algorithm with competitive ratio $CR=3+2 \sqrt{2}$. If there is a single sender or fully wireless agent, and multiple receivers we prove that $CR \in [2+\sqrt{5},5]$, and if there are multiple senders and a single receiver or fully wireless agent, we show that $CR \in [3,5.681319]$. Any group consisting of only senders or only receivers requires competitive ratio 9, and any other combination of agents has competitive ratio 3.

Consider two robots that start at the origin of the infinite line in search of an exit at an unknown location on the line. The robots can only communicate if they arrive at the same location at exactly the same time, i.e. they use the so-called face-to-face communication model. The group search time is defined as the worst-case time as a function of $d$, the distance of the exit from the origin, when both robots can reach the exit. It has long been known that for a single robot traveling at unit speed, the search time is at least $9d-o(d)$. It was shown recently that $k\geq2$ robots traveling at unit speed also require at least $9d$ group search time. We investigate energy-time trade-offs in group search by two robots, where the energy loss experienced by a robot traveling a distance $x$ at constant speed $s$ is given by $s^2 x$. Specifically, we consider the problem of minimizing the total energy used by the robots, under the constraints that the search time is at most a multiple $c$ of the distance $d$ and the speed of the robots is bounded by $b$. Motivation for this study is that for the case when robots must complete the search in $9d$ time with maximum speed one, a single robot requires at least $9d$ energy, while for two robots, all previously proposed algorithms consume at least $28d/3$ energy. When the robots have bounded memory, we generalize existing algorithms to obtain a family of optimal (and in some cases nearly optimal) algorithms parametrized by pairs of $b,c$ values that can solve the problem for the entire spectrum of these pairs for which the problem is solvable. We also propose a novel search algorithm, with unbounded memory, that simultaneously achieves search time $9d$ and consumes energy $8.42588d$. Our result shows that two robots can search on the line in optimal time $9d$ while consuming less total energy than a single robot within the same search time.

We consider the problem of finding a treasure at an unknown point of an n-dimensional infinite grid, n >= 3, by initially collocated finite automaton agents (scouts/robots). Recently, the problem has been well characterized for 2 dimensions for deterministic as well as randomized agents, both in synchronous and semi-synchronous models [S. Brandt et al., 2018; Y. Emek et al., 2015]. It has been conjectured that n+1 randomized agents are necessary to solve this problem in the n-dimensional grid [L. Cohen et al., 2017]. In this paper we disprove the conjecture in a strong sense: we show that three randomized synchronous agents suffice to explore an n-dimensional grid for any n. Our algorithm is optimal in terms of the number of the agents. Our key insight is that a constant number of finite automaton agents can, by their positions and movements, implement a stack, which can store the path being explored. We also show how to implement our algorithm using: four randomized semi-synchronous agents; four deterministic synchronous agents; or five deterministic semi-synchronous agents. We give a different algorithm that uses 4 deterministic semi-synchronous agents for the 3-dimensional grid. This is provably optimal, and surprisingly, matches the result for 2 dimensions. For n >= 4, the time complexity of the solutions mentioned above is exponential in distance D of the treasure from the starting point of the agents. We show that in the deterministic case, one additional agent brings the time down to a polynomial. Finally, we focus on algorithms that never venture much beyond the distance D. We describe an algorithm that uses O(sqrt{n}) semi-synchronous deterministic agents that never go beyond 2D, as well as show that any algorithm using 3 synchronous deterministic agents in 3 dimensions, if it exists, must travel beyond Omega(D^{3/2}) from the origin.

Target monitoring is an important ConvergeCast application of wireless sensor networks in which sensors monitor a set of targets, and forward the collected data using multi-hop routing to the same location, called the sink. Nearly all previously proposed models only output a set of link transmission configurations, i.e., sets of links that can simultaneously transmit, without providing an ordering of the transmission configurations, nor guaranteeing that such an ordering exists using only the prescribed number of slots. As such, they do not provide a valid schedule to achieve ConvergeCast, and only give a lower bound on the number of slots required for a schedule. In this paper, we propose a first one phase decomposition model and algorithm that outputs a complete and optimum scheduling, i.e., with the output consisting in an ordered sequence of transmission configurations that achieves ConvergeCast. In addition, we show that the resulting transmission graph is not necessarily a tree. The resulting algorithm provides much better schedules, up to 15% less time slots required, than those of the previous best available mathematical programming or heuristic approaches in the literature.

Community detection is a well-studied problem in social networks. However most of the research so far has been on static networks. In this paper, we address the problem of community detection in evolving social networks. As social networks evolve, the community structure of the network can change. How can the community structure be updated in an efficient way? How often should community structure be updated? We give two methods based on the Louvain algorithm, to determine when to update the community structure. The first method, called the Edge-Distribution-Analysis algorithm, analyzes the newly added edges in order to make this decision. The second method, called the Modularity-Change-Rate algorithm, finds the rate of modularity change in a given network, and uses it to predict whether or not an update is required.

Consider k robots initially located at the centroid of an equilateral triangle T of sides of length one. The goal of the robots is to evacuate T through an exit at an unknown location on the boundary of T. Each robot can move anywhere in T independently of other robots with maximum speed one. The objective is to minimize the evacuation time, which is defined as the time required for all k robots to reach the exit. We consider the face-to-face communication model for the robots: a robot can communicate with another robot only when they meet in T. In this paper, we give upper and lower bounds for the face-to-face evacuation time by k robots. We show that for any k, any algorithm for evacuating k >= 1 robots from T requires at least sqrt(3) time. This bound is asymptotically optimal, as we show that a straightforward strategy of evacuation by k robots gives an upper bound of sqrt(3) + 3/k. For k = 3, 4, 5, 6, we show significant improvements on the obvious upper bound by giving algorithms with evacuation times of 2.0887, 1.9816, 1.876, and 1.827, respectively. For k = 2 robots, we give a lower bound of 1 + 2/sqrt(3) ~= 2.154, and an algorithm with upper bound of 2.3367 on the evacuation time.

We consider a problem of routing on directed paths and trees to a single destination, with rate-limited, adversarial traffic. In particular, we focus on local buffer management algorithms that ensure no packet loss, while minimizing the size of the required buffers. While a centralized algorithm for the problem that uses constant-sized buffers has been recently shown [21], there is no known local algorithm that achieves a sub-linear buffer size. In this paper we show tight bounds for the maximum buffer size needed by l-local algorithms for information gathering on directed paths and trees, where an algorithm is called l-local if the decision made by each node v depends only on the sizes of the buffers at most l hops away from v.

We consider the scheduling problem for Aggregated ConvergeCast in wireless sensor networks with a physical interference model. Previous work consists of either heuristics without performance guarantees, or approximation algorithms which do not perform well in practice. We propose here a first scalable mathematical SINR (Signal to Interference plus Noise Ratio) model that outputs an optimal Aggregated ConvergeCast schedule. We use large scale optimization techniques, namely a Dantzig-Wolfe decomposition algorithm, to solve it. We perform extensive simulations on networks with upto 70 sensors, and compare our results with the best heuristic in the literature using a SINR model. Results show that schedules output by our new model are significantly better than those output by the best available heuristic, i.e., with TDMA frames that are about 50% shorter.

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 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.

We consider the problem of searching on a line using n mobile robots, of which at most f are faulty, and the remaining are reliable. The robots start at the same location and move in parallel along the line with the same speed. There is a target placed on the line at a location unknown to the robots. Reliable robots can find the target when they reach its location, but faulty robots cannot detect the target. Our goal is to design a parallel algorithm minimizing the competitive ratio, represented by the worst case ratio between the time of arrival of the first reliable robot at the target, and the distance from the source to the target.

We address the problem of minimizing TDMA frame length in a wireless sensor network charged with monitoring a given set of targets. The problem reduces to finding a minimal set of so-called configurations that delivers data from the targets to a specially designated sink node, where each configuration is a set of links that can transmit concurrently without significant interference. We assume a SINR-based interference model. We use a column generation technique to derive near-optimal solutions even when integrality constraints are enforced on coverage and flow variables. We also introduce a heuristic and a hybrid algorithm to efficiently solve the problem by leveraging a wide range of network parameters related to transmission power control, data rates, and routing. Our results show that significant gains in scalability can be obtained by using our methods.

An important application for sensor networks is to collect data sensed from the environment and send it to a data collection point or a sink node using a convergecast tree. Considerable savings in energy can be obtained by aggregating data at intermediate nodes along the way to the sink. We study the problem of finding a minimum latency aggregation tree and transmission schedule in wireless sensor networks. This problem is referred to as Minimum Latency Aggregation Scheduling (MLAS) in the literature and has been proven to be NP-Complete. We present a new algorithm for building an aggregation tree. Furthermore, we propose two new approaches for building a TDMA transmission schedule to perform aggregation on a given tree. We evaluate the performance of our algorithms through extensive simulations on randomly generated graphs and we compare them to the previous state of the art. Our results show that both our new scheduling algorithms when combined with our new tree-building algorithm obtain significantly lower latencies than that of the previous best algorithm.

Network virtualization is regarded as the pillar of cloud computing, enabling the multi-tenancy concept where multiple Virtual Networks (VNs) can cohabit the same substrate network. With network virtualization, the problem of allocating resources to the various tenants, commonly known as the Virtual Network Embedding problem, emerges as a challenge. Its NP-Hard nature has drawn a lot of attention from the research community, many of which however overlooked the type of communication that a given VN may exhibit, assuming that they all exhibit a one-to-one (unicast) communication only. In this paper, we motivate the importance of characterizing the mode of communication in VN requests, and we focus our attention on the problem of embedding VNs with a one-to-many (multicast) communication mode. Throughout this paper, we highlight the unique properties of multicast VNs and its distinct Quality of Service (QoS) requirements, most notably the end-delay and delay-variation constraints for delay-sensitive multicast services. Further, we showcase the limitations of handling a multicast VN as unicast. To this extent, we formally define the VNE problem for Multicast VNs (MVNs) and prove its NP-Hard nature. We propose two novel approach to solve the Multicast VNE (MVNE) problem with end-delay and delay variation constraints: A 3-Step MVNE technique, and a Tabu-Search algorithm. We motivate the intuition behind our proposed embedding techniques, and provide a competitive analysis of our suggested approaches over multiple metrics and against other embedding heuristics.

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 study the barrier coverage problem using relocatable sensor nodes. We assume each sensor can sense an intruder or event inside its sensing range. Sensors are initially located at arbitrary positions on the barrier and can move along the barrier. The goal is to find final positions for sensors so that the entire barrier is covered. In recent years, the problem has been studied extensively in the centralized setting. In this paper, we study the problem in the distributed setting. We assume each sensor repeatedly executes a Look-Compute-Move cycle: based on what it sees in its vicinity, it makes a decision on where to move, and moves to its next position. We make two strong but realistic restrictions on the capabilities of sensors: they have a constant visibility range and can move only a constant distance in every cycle. In this model, we give the first two distributed algorithms that achieve barrier coverage for a line segment barrier when there are enough nodes in the network to cover the entire barrier. Our algorithms are synchronous, and local in the sense that sensors make their decisions independently based only on what they see within their constant visibility range. One of our algorithms is oblivious whereas the other uses two bits of memory at each sensor to store the type of move made in the previous step. We show that our oblivious algorithm terminates within Θ(n2) steps with the barrier fully covered, while the constant-memory algorithm is shown to take Θ(n) steps to terminate in the worst case. Since any algorithm that can only move a constant distance in one step requires Ω(n) steps on some inputs, our second algorithm is asymptotically optimal. Finally, both our algorithms are self-stabilizing, and can be easily extended to the case of non-homogeneous sensors, and for the case when the barrier is a circle.

Assume that n sensors with identical range r = f(n)⁄2n, for some f(n) ≥ 1 for all n, are thrown randomly and independently with the uniform distribution in the unit interval [0, 1]. They are required to move to new positions so as to cover the entire unit interval in the sense that every point in the interval is within the range of a sensor. We obtain tradeoffs between the expected sum and maximum of displacements of the sensors and their range required to accomplish this task. In particular, when f(n) -- 1 the expected total displacement is shown to be Θ(√n). For senors with larger ranges we present two algorithms that prove the upper bound for the sum drops sharply as f(n) increases. The first of these holds for f(n) ≥ 6 and shows the total movement of the sensors is O(√ ln n/f(n)) while the second holds for 12 ≤ f(n) ≤ ln n -- 2 ln ln n and gives an upper bound of O(lnn⁄ f(n)ef(n)/2). Note that the second algorithm improves upon the first for f(n) > ln ln n -- ln ln ln n. Further we show a lower bound, for any 1 < f(n) < √n of Ω(εf(n)ε--(1+ε)f(n)), ε > 0.

We study the problem of finding a minimum energy broadcast tree in duty cycled wireless sensor networks. In such networks, every node has a wakeup schedule and is awake and ready to receive packets or transmit in certain time slots during the schedule and asleep during the rest of the schedule. We assume that a forwarding node needs to stay awake to forward a packet to the next hop neighbor until the neighbor is awake. The minimum energy broadcast tree minimizes the number of additional time units that nodes have to stay awake in order to accomplish broadcast. We show that finding the minimum energy broadcast tree is NP-hard. We give two heuristic algorithms for finding energy-efficient broadcast trees in such networks. We performed extensive simulations to study the performance of these algorithms and compare them with previously proposed algorithms. Our results show that our algorithms exhibit the best performance in terms of average number of additional time units a node needs to be awake, as well as in terms of the number of highly loaded nodes, while being competitive with previous algorithms in terms of total number of transmissions and delay.

In wireless sensor networks connected dominating sets are often used to form a virtual backbone. However, a connected dominating set is often vulnerable due to frequent node failures in sensor networks. Hence, to provide a degree of fault-tolerance, we consider a 2-connected distance-k p-dominating set, denoted D2;k;p, as a virtual backbone for wireless sensor networks. Ideally, the backbone should constitute the smallest percentage of nodes in the network. To find a minimum D2;k;pin unit disk graphs as well as in general graphs is of unknown complexity. We propose two centralized approximation algorithms to construct a D2;k;pin unit disk graphs as well as in general graphs.

We study the load balancing aspect of routing algorithms in wireless ad hoc networks. We define a statistical measure called local coefficient of variance (lcv) to study the smoothness of the load distribution in the network. The importance of keeping lcv as low as possible in designing load balanced routing algorithms is demonstrated. We analyze how number of nodes, transmission range, network area and different routing algorithms can affect this metric. We introduce a class of algorithms called elliptic routing that reduce the maximum load of nodes in the network by avoiding the highly loaded network center at the same time as keeping the lcv of the load distribution low. Experimental results show that our algorithms outperform other existing algorithms in reducing the maximum load of the network. We also give a technique to reduce the lcv of the load distribution, and hence decrease the maximum load of the nodes in the network further. This technique can be combined with any location-based routing algorithm. We evaluate the performance gain obtained by this technique via simulations.

We study the problem of achieving maximum barrier coverage by sensors on a barrier modeled by a line segment, by moving the minimum possible number of sensors, initially placed at arbitrary positions on the line containing the barrier. We consider several cases based on whether or not complete coverage is possible, and whether non-contiguous coverage is allowed in the case when complete coverage is impossible. When the sensors have unequal transmission ranges, we show that the problem of finding a minimum-sized subset of sensors to move in order to achieve maximum contiguous or non-contiguous coverage on a finite line segment barrier is NP-complete. In contrast, if the sensors all have the same range, we give efficient algorithms to achieve maximum contiguous as well as non-contiguous coverage. For some cases, we reduce the problem to finding a maximum-hop path of a certain minimum (maximum) weight on a related graph, and solve it using dynamic programming.

Selfish nodes in an 802.11 network can gain unfair access to the wireless medium by modifying the backoff protocol, for example by choosing smaller backoff values more often than would be dictated by pure chance. Detecting this kind of misbehavior is far from obvious as it is not always possible to deduce the backoff values used by a node. We propose a new backoff scheme called XVBEB in which there are only two backoff values: 0 and CW. We describe how to deduce the backoff values used by an observed node using XVBEB based on observations of transmissions by nodes in the network and the collision timeline. Given a set of backoff values used by a XVBEB node, we describe how to conclude with a specified level of certainty whether the node is indeed adhering to the protocol. We also show that it would take much more effort to detect selfishness for 802.11 nodes following the standard backoff procedure within a comparable misbehaving framework.

A Connected Dominating Set (CDS) can be used as a routing backbone in ad hoc networks and a data gathering/dissemination infrastructure in sensor networks. This virtual backbone can efficiently narrow down the search space for a route to the nodes in the CDS and thus be used by any routing protocol. Ideally, the backbone should constitute the smallest percentage of nodes in the network. However, finding a Minimum CDS (MCDS) is an NP-hard problem. In this paper, we propose an efficient distributed algorithm to construct a CDS in general graphs. The time and message complexity of our algorithm is linear in the number of nodes and degree of the network. Extensive simulations on Unit Disk Graphs (UDGs) show that this algorithm outperforms the distributed algorithms proposed in terms of the size of the CDS. We also present a local implementation of our algorithm in location-aware UDGs. Our algorithm provides the flexibility to arbitrarily adjust the tradeoff between the degree of locality and the size of the generated CDS.

We consider the problem of backbone formation in ad hoc wireless networks composed of heterogeneous nodes. A virtual backbone in an ad hoc wireless network provides a hierarchical infrastructure that can be used to address important challenges such as efficient routing, multicasting/broadcasting, activity-scheduling, and energy efficiency. We model a wireless network in which nodes have different transmission ranges by a disk graph. A virtual backbone in such a network can be modeled by a Strongly Connected Dominating and Absorbent Set (SCDAS) in the associated disk graph. For practical reasons, it is desirable to minimize the size of this backbone. In this paper, we propose an efficient distributed algorithm for the construction of an SCDAS in ad hoc networks modeled by disk graphs. Extensive simulation results show that the SCDAS constructed by our algorithm is significantly smaller than those generated by the algorithms prior to our work.

Position-based routing algorithms for mobile ad hoc networks utilize the position or location of the destination node to inform routing decisions. We consider the problem of routing in an ad hoc network where the source node knows the approximate position of the destination node, but is uncertain about its exact current location. We investigate two approaches to this problem: one, based on a traversal of the faces of a planar sub-graph of the graph representing the network, and the second, based on flooding a limited area of the graph that represents the region the destination is likely to be found. We propose several variants of both approaches, and do extensive simulations to analyze the performance of the algorithms. Our results indicate that a simple modification of the basic flooding approach yields the best trade-off for optimizing delivery rate, stretch factor, as well as transmission cost. If however, delivery is required to be guaranteed, then a variant of the face tree approach in P. Bose et al. (2002) that we propose has the best performance

We consider the problem of routing with guaranteed delivery in ad-hoc wireless networks using the positions of the mobile hosts. Such networks can be modeled as geometric graphs. FACE ROUTING [Bose, P et al. (1999), Karp, B et al. (2000)] is a position-based routing algorithm for planar geometric graphs that guarantees delivery of messages without flooding control packets throughout the network. For general ad hoc networks, FACE ROUTING can use a planar sub-graph of the original graph; many local and distributed algorithms have been proposed to extract such a planar sub-graph. However, these planarization algorithms may fail in some situations, such as when the transmission ranges are not the same, for example, due to the presence of obstacles, which in turn may cause a routing failure. In this paper, we describe a generalization of FACE ROUTING that can guarantee delivery in planar graphs with disjoint crossing edges added. Our algorithm needs O(/spl lscr/) memory, where /spl lscr/ is the maximum number of edges in any face in a graph obtained by removing one edge in each pair of crossing edges.

Abstract Several papers considered the problem of routing inad hocwireless networks using the positions of the mobile hosts. Perimeter routing 1 , 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.

In this paper, we consider the problem of shortest path interval routing, a space-efficient strategy for routing in distributed networks. In this scheme, an ordering of the vertices is chosen so that the edges of the network can be labeled with one or more subintervals of the vertex ordering: The resulting routing tables must be deterministic and route along shortest paths between all pairs of vertices. We first show constructively that any interval graph can be labeled with one circular subinterval on each edge; this extends a known result for proper interval graphs. We also provide a partial characterization for networks that admit linear interval routing when edges are labeled with exactly one interval, in terms of the biconnected components of any such network. This is the first such characterization when the paths are required to be shortest paths under the distance metric. Finally, we show that the class of networks that can be labeled with k ≥ 1 subintervals per edge is closed under composition with a certain class of graphs. © 1998 John Wiley & Sons, Inc. Networks 32: 103–113, 1998

we show that sorting an input of size N = n2 can be performed by an n x n mesh-connected processor array in 2.5n + o(n) parallel communication steps and using constant size queues, with high probability.The best previously known algorithm for this problem required 37L + o(n) steps.We also show that selecting the element of rank k out of N = n2 inputs on an n x n mesh can be performed in 1.25n + o(n) steps and using constant size queues, with high probability.The best previously known algorithm for this problem involved sorting, and required 3n + o(n) steps.Both of our algorithms can be generalized to higher dimensions, achieving bounds better than the known results.