In this paper, we study the distance-2 broadcast scheduling problem in synchronous wireless networks of known topology.Two constraints are taken under consideration: the schedule must be collision-free and the nodes at distance 2 must be informed by nodes at distance 1.In general graphs, a tight bound of O(log(n) 2 ) slots to complete the broadcast is known, n being the number of nodes at distance 2. We improve this bound to O(log(n)) in unit disk graphs, and to O(1) when the neighbourhoods of the nodes are circular intervals.

We tackle the makespan minimization coupled-tasks problem in presence of compatibility constraints. In particular, we focus on stretched coupled-tasks, i.e. coupled-tasks having the same sub-tasks execution time and idle time duration. In such context, we propose some complexity results according to several parameters and we design an efficient polynomial-time approximation algorithm.

ABSTRACT This paper addresses the problem of localization in sensor networks where, initially, a certain number of sensors are aware of their positions (either by using GPS or by being hand‐placed) and are referred to as anchors. Our goal is to localize all sensors with high accuracy, while using a limited number of anchors. Sensors can be equipped with different technologies for signal and angle measurements. These measures can be altered by some errors because of the network environment that induces position inaccuracies. In this paper, we propose a family (AT‐Family) of three new distributed localization techniques in wireless sensor networks: free‐measurement (AT‐Free) where sensors have no capability of measure, signal‐measurement (AT‐Dist) where sensors can calculate distances, and angle‐measurement (AT‐Angle) where sensors can calculate angles. These methods determine the position of each sensor while indicating the accuracy of its position. They have two important properties: first, a sensor node can deduce if its estimated position is close to its real position and contribute to the positioning of others nodes; second, a sensor can eliminate wrong information received about its position. This last property allows to manage measure errors that are the main drawback of measure‐based methods such as AT‐Dist and AT‐Angle techniques. By varying the density and the error rate, simulations show that the three proposed techniques achieve good performances in term of high accuracy of localized nodes and less energy consuming while assuming presence of measure errors and considering low number of anchors. Copyright © 2012 John Wiley & Sons, Ltd.

Several routing protocols have been proposed for mobile wireless sensor networks. Some are based on variants of flooding algorithms leading to redundant copies of message unnecessarily. Despite various optimizations, such routing methods still remain inefficient. This paper deals with region-based routing which has been introduced to reduce the number of messages in the network. We propose an energy efficient routing algorithm, called Ellipse-routing, which is based on region-based routing. A virtual ellipse is built thanks to source and destination positions. So, only nodes within this region forward a message. For a given energy consumption model, we select a suitable ellipse factor and a transmission range, leading to a delivery rate close to 100% while minimizing energy consumption. Then, we extend the proposed scheme to take into account position errors. Performances of proposed algorithms are shown thanks to simulations.

Determining where a given sensor is physically located is a challenging issue. In this paper, we address the localization problem where, initially, a certain number of sensors called anchors are aware of their positions. Our goal is to localize all sensors with high accuracy, while using a limited number of anchors. So, we focus on localization techniques based on angle of arrival information between neighbor nodes. This paper proposes an original angle-based localization technique, called AT-Angle, which allows to verify two important properties: first, a sensor node can eliminate wrong received information about its position; second, it deduces if its estimated position is closed to its real position. In this last case, the sensor node becomes an estimated anchor and contributes to the positioning of others nodes. Simulations show that AT-Angle achieves good precision for located nodes despite the introduction of position errors and the small number of anchors.

Mobile wireless sensors need to know their localizations in many control and monitoring applications. Among all sensors, some know their exact position (i.e., they are equipped with GPS or they are positioned by human intervention). These sensors are called anchors. Some sensors can have different capabilities allowing them to calculate either distances or angles when they receive messages from others nodes. So, they only use anchor positions to obtain an estimated position. However, when sensors are mobile they cannot continuously calculate their position because of the energy constraints. This paper concerns the localization problem in the case where all nodes in the network (anchors and others sensors) are mobile. The authors propose three techniques following the capabilities of nodes. Thus, each node obtains either an exact position or an approximate position with the knowledge of the maximal error born. Also, the authors adapt the periods where nodes invoke their localization. Simulation results show the performances of our methods in term of accuracy and determinate the technique the more adapted related to the network configurations.

Autonomous systems (AS) in the Internet use different protocols for internal and external routing. BGP is the only external protocol. It allows ASes to define their own routing policy independently. Many papers cited in reference deal with a divergence behavior due to this flexibility. In fact, when routing policies are not conflicting, BGP is self-stabilising, which means that whatever the network configuration, BGP converges to a stable solution. Unfortunately, as experienced on the Internet, AS routing policies may be uncoherent, thus generating oscillations. In this paper, we propose a distributed dynamic method for detecting and solving oscillations of BGP. It respects private policy choices and requires only a few low level constraints in order to converge to a stable solution. Essentially, a router has to maintain only local path stateful information to detect instabilities. In this case, it generates and launches a token linked to a route. Each router makes the decision to forward or not the token according to local data and local policy. If the originating router receives back the token, then it marks the route as barred. Nevertheless, routes may furtherly be unmarked. Finally, we express and define what coherence between routing policies means.

Wireless sensor nodes need to know their localizations in many control and monitoring applications such as routing, target tracking, etc... To determine node localization, many techniques have been proposed in the literature. This paper proposes a rule-based method, called MuR (method using rules), that allows to locating nodes with high accuracy. The rules are based on information of located nodes (called anchors). They resolve ambiguity when a node can be located at more than one position. MuR is compatible with existing localization techniques; it can be used as a preliminary step before the execution of one of these techniques. Simulation results show the effectiveness of MuR locating a maximum number of nodes

Abstract In this paper, we show how to give an orientation to the edges of an hypercube so that the inducedorientedhypercube offers approximately the same communication performance as that of the original nonoriented hypercube (routing, broadcasting, connectivity, etc.), that is, we show that it is possible to construct anN‐node oriented hypercube with the same communication and computational power as that of anN‐node hypercube, although with approximately the same pin‐complexity as that of a$\sqrt{N}$ ‐node hypercube. © 2002 Wiley Periodicals, Inc.

The diameter of a directed graph is the maximum of the lengths of the shortest paths between all pairs of vertices. A directed graph is said to be tightly oriented if it has the same diameter as its undirected image graph. Our main result is tight orientations for all sufficiently large toroids, except those whose sizes in both dimensions are odd. We also prove the impossibility of tightly orienting all the toroids for which we do not present tight orientations, and we give partial results for dimensionality higher than two. © 1998 John Wiley & Sons, Inc. Networks 32: 1–11, 1998

We consider a graph theoretical model and study a parallel implementation of the well-known Gaussian elimination method on parallel distributed memory architectures, where the communication delay for the transmission of an elementary data is higher than the computation time of an elementary instruction. We propose and analyze two low-complexity algorithms for scheduling the tasks of the parallel Gaussian elimination on an unbounded number of completely connected processors. We compare these two algorithms with a higher-complexity general-purpose scheduling algorithm, the DSC heuristic, proposed by A. Gerasoulis and T. Yang (1993).

This paper addresses the one-to-all broadcasting problem and the one-to-many broadcasting problem, usually simply called broadcasting and multicasting, respectively. Broadcasting is the information dissemination problem in which a node of a network sends the same piece of information to all the other nodes. Multicasting is a partial broadcasting in the sense that only a subset of nodes forms the destination set. Both operations have many applications in parallel and distributed computing. In this paper, we study these problems in both line model, and cut-through model. The former assumes long distance calls between nonneighboring processors. The latter strengthens the line model by taking into account the use of a routing function. Long distance calls are possible in circuit-switched and wormhole-routed networks, and also in many networks supporting optical facilities. In the line model, it is well known that one can compute in polynomial time a [log/sub 2/n]-round broadcast or multicast protocol for any arbitrary network. Unfortunately such a protocol is often inefficient from a practical point of view because it does not use the resources of the network in a balanced way. In this paper, we present a new algorithm to compute broadcast or multicast protocols. This algorithm applies under both line and cut-through models. Moreover, it returns protocols that efficiently use the bandwidth of the network. From a complexity point of view, we also show that most of the optimization problems relative to the maximization of the efficiency of broadcast or multicast protocols in terms of switching time or vertex load are NP-complete. We have, however, derived polynomial efficient solutions for tree-networks.