Sage Journals: Discover world-class research

Abstract

This paper introduces a consensus routing algorithm based on an availability function. Such a function obtains a consensus among a group of nodes by evaluating the idle time in the scheduler of each node, along with the general conditions of the network and determining the next step of the route. In this regard, the algorithm proposed here makes it possible to avoid flooding while reducing bandwidth use and keeping changes of the network only at a local scale.

1. Introduction

A Mobile Distributed System (MDS) is composed of some wireless devices, acting as nodes. Each node exposes not only a relative position with the rest of the mobile devices, but also a state, and it may act as a router: in a MDS, each node communicates with its neighbours not only as a sender or receiver, but also as a router, forwarding packets to nodes that are not within the transmission range of the sender [1].

Commonly, a MDS is described as a dynamic topology since it changes with the movement, entry, and exit of nodes within the range of the MDS. Such a dynamic behaviour makes it difficult to establish and maintain a communication route between two remote nodes, since all the nodes of such a route may not be available for routing at a later time. Traditional routing algorithms are not useful here, since they require knowledge about the network as a whole in order to determine any optimal route. Using a route discovery algorithm every time the topology changes requires constantly generating a global state of the MDS.

For performance purposes regarding the transmission of messages, routing algorithms need to be bandwidth efficient, spend as few resources as possible in the computation of a route, and reconcile conflicting goals such as dynamic adaptation and low resource consumption [2]. Routing algorithms are commonly described as part of routing protocols.

2. Related Work

There are studies about routing protocols in wireless networks, showing that these protocols can be classified into five main types: reactive, proactive, hybrid, hierarchical, and based on coordinates.

Reactive protocols perform on-demand route discovery by flooding the network and delaying packets until the routes are established. Examples of these protocols are [3], DSR [4], and TORA [5].

Proactive protocols maintain routes between all pairs of nodes. The network is flooded with information packets whenever there are changes in the topology but does not incur delays or overhead to display cover routes on demand. DSDV [6], OLSR [7], and WRP [8] are examples of proactive protocols. In general, proactive protocols present a good performance in static scenarios, while reactive protocols do so in mobile scenarios.

Whether reactive or proactive, in both types of protocols, flooding means that every node in the MDS sends all incoming packets to its neighbourhood, except those packets that must receive. Flooding is easy to implement. Nevertheless, it represents a brute force approach. Furthermore, it is inefficient in the sense that it tends to exponentially increase traffic until consuming all bandwidth of communication channels. Since flooding consumes a substantial amount of bandwidth, it is important to reduce the frequency of route discoveries and so network flooding [1].

Hybrid protocols have been proposed to overcome performance problems due to frequent route discovery attempts in on-demand routing protocols. These routing protocols incorporate both proactive and on-demand protocol features [9]. However, for each route request hybrid protocols do not wide-flood the network. It is difficult to balance between the cost of periodically exchanging route information (i.e., proactivity) and route discovery by controlled network flooding (i.e., reactivity) [10]. Other protocols such a geographical or bypass routing reduce the frequency of flooding by allowing a relay node to start a limited route discovery in the event of a route failure [3, 11], or employ local error recovery mechanisms [12, 13]. Hybrid protocols using either controlled flooding or local error recovery have focused on reducing packet drops and not efficiently using bandwidth during route recovery. However, multipath protocols require additional packet drops and delays due to the dependency on potentially stale routes from caches [1]. Hybrid protocols such as ZRP [14] and SHARP [10] achieve good performance across a wider range of scenarios by combining both reactive and proactive components. They divide the network into zones. Nodes maintain routes proactively within their zone by flooding topology changes within the zone. Routes between zones are discovered on demand with an optimised flooding mechanism [15].

Hierarchical and coordinate-based protocols do not flood the network. They use location-dependent addresses in routing. These identifiers can change with mobility and, in some protocols, with congestion and failures [16–18]. Therefore, these protocols use both a fixed identifier and a location-dependent address for each node and they usually require mechanisms to look up the location of a node given its fixed identifier [19]. These mechanisms reduce resilience to failures, introduce overhead, and increase complexity [15]. For example, LANMAR [17] and L+ [16] are hierarchical protocols, and GPSR [20] and BVR [18] are coordinate-based protocols.

Protocol VRR [15] combines aspects of proactive routing, establishing and maintaining routes without flood routing by combining the use of a logical ring and a physical map. VRR uses a scheme to identify nodes by a random number between 0 and a finite upper limit. This implies the need to have a mechanism for consensus to assign numbers to each node or the existence of a centralised node that is responsible for global identifiers. This restricts the scalability of the protocol.

Routing algorithms for ad hoc networks, such as AODV [3], TORA [5], and OLSR [7], are not useful to solve the problem of calculating a route between a pair of nodes without having a global state, since these algorithms do not take into consideration the status of the local scheduler within each node. Wormhole [21] and vector-based distance and link state [22, 23] algorithms cannot be used here, since they reserve a channel and keep it, but due to the dynamic topology, they do not seem to be a time-efficient option for route construction [24–28].

The WARP algorithm [29] focuses on repairing paths. WARP is reactive and is based on distance vector and detects when the position of the destination node has changed and it makes a spiral search engine around the old position, thus seeking a neighbour node that still maintains communication with the destination node. This algorithm requires a vector distance, which could be inconsistent.

Researches have developed consensus mechanisms for routing protocols. For example, in [30], the authors separate the delivery of the package into two different logical modes: a stable mode, which ensures that the route is selected only after arriving at an agreement that is reached by a state consisting of a global view, and a transient mode, which ensures high availability when a package finds a router that does not have a stable route, due to a fail in the link or because the algorithms are still calculating a stable route. The consensus algorithm is used to calculate a global state of the system, staring from the distributed snapshots that each autonomous system sent.

Opportunistic networks are similar to MDS. However, the routing algorithm used in this kind of networks is the Epidemic Routing [31]. This routing algorithm uses the mobility of nodes to propagate messages over the network: every time a node physically finds another node there is an exchange of distance vectors. Both nodes then compare and update their messages and vectors. This is a costly operation each time, since the network normally tends to have a large number of nodes. Thus, this protocol maximises the rate of message delivery, while minimising latency delivery. Nevertheless, this is costly in terms of bandwidth utilisation and processing on each node.

The algorithm “Adaptive Routing in Mobile Ad Hoc Networks Based on Decision Aid Approach” [32] chooses which routing algorithm is suitable depending on the current network conditions. This algorithm provides three algorithms to choose from: OLSR [7], DSR [4], and AODV [3]. It uses a voting algorithm. This assigns a weight to each node depending on the number of neighbour nodes that have a majority vote.

Consensus algorithms in distributed systems have been used successfully to problems where a team of agents must cooperatively compute logical vector function that returns a set of decisions depending on a set of input events. Agents have partial accessibility to the input events, very simple local computation and broadcast communication capabilities, and may be affected by failures. This issue involves reliable network information diffusion that can be achieved making use of techniques based on Robust Flooding [33]. For dynamic networks, [34] proposes a synchronous consensus model, in which at each round after the network topology it changes completely. It uses a variant connection model and a global clock to synchronise the rounds.

In [35] a consensus algorithm for opportunistic networks is proposed. Each node carries messages and propagates them through the network, using Epidemic Routing [31]. Disconnection of a node is not considered as a fault, but as an expected behaviour. It is expected to reach immediately the neighbourhood of the destination node. The algorithm requires a global view of the network.

Different modelling schemes may be approximated through bounded time delays. This effect can be modelling, for instance, by bounding sampling data to guarantee a transmission rate over a trigger protocol event. For example, the reactive protocol in [36] allows coping several varying time multiple sampling periods, such as current condition in this paper, by entering an artificial induced local delay which is directly related to a known sample data error that can be locally modelled through a proper local control design. In [37] the authors propose an event-triggered communication scheme. This generates the transmission events, utilising information about the system's outputs at a time-varying sampling period and the output error. In this work sampling is performed using a known and bounded time function for a local system on a global network guaranteeing the stability in an exponential response. The variable sampling function is global and its effects are local to each node to interact on this global network. The idea of local influence is used in CRA.

3. Contributions

Our goal here is to propose an algorithm for routing discovery, whose main objective is to reduce flooding. A Consensus Routing Algorithm (CRA) takes into consideration characteristics of the MDS, such as idle time in the scheduler, network's availability, mobility, and the distance between nodes. Idle time in the scheduler node is an important feature because if there is not enough time in node's scheduler to transmit a message then the path is broken. The proposal includes versions for static nodes and for mobile nodes.

The algorithm obtains a route through a dynamic topology, by establishing successive consensus among nodes. In a local group, each node obtains routing information from its neighbours while they have an active connection. This provides resilience to local changes of the dynamic topology: any change is kept at a local scale within the MDS; when some change occurs (a mobile node moving, entering, or exiting), it does not affect the overall state of the MDS, but it only affects the local group of the involved nodes. Thus, it is not necessary to recalculate the whole route, but only those groups of nodes affected by the change. The union of the local states of the nodes forms the local network status at a given time T.

In order to determine the cost of sending a packet between two nodes, routing metrics are defined in terms of how long it takes to deliver a packet over a given route. Normally, each routing algorithm has its own metrics, which assign a value to a route, based on a factor such as hop count, bandwidth, and link reliability [38].

The rest of this paper is organised as follows. Section 2 presents an overview of the CRA; Section 3 describes the experiments based on the case studies for one and two hops. Section 4 presents our results. And Section 5 provides conclusions.

4. The Consensus Routing Algorithm (CRA)

For the purposes of this paper, the CRA is analysed considering that the topology is “mobile”; that is, the topology changes through time.

For modelling a distributed system (MDS) with n nodes, consider the following parameters and variables: (i)

Let node be a data structure per node that includes the following fields:

(1)

Unique ID per node.

(2)

Axes x and y.

(3)

Letting β be the field corresponding to idle time in the scheduler of a node when it acts as a router.

(4)

Letting λ be the field corresponding to the load of every link between all pairs of directly connected nodes.

(5)

A field that indicates whether a node can move through network.

(ii)

Let $n_{s}$ be the source node, from which the route discovery process starts, and let $n_{d}$ be the destination node, to which the route discovery process ends.

(iii)

Let $d_{G} (i)$ be the degree of node i, that is, the number of links incident to the node i.

(iv)

Let k be the total number of routing steps of a given route.

(v)

Let l be neighbourhood with respect to a node, whose extension is presented in number of hops.

(vi)

Let $J_{i}$ be the set of nodes belonging to neighbourhood of node i in radial neighbourhood radius ρ. Where ρ is defined by the wireless range of each node, every node into radius ρ is a neighbour of i and belongs to $J_{i}$ . The set $J_{i}$ can be defined as in

\begin{array}{l} J_{i} = \{j : |x_{i} - x_{j}| \land |y_{i} - y_{j}| \leq ρ\} \\ i = 1, \dots, n, j = 1, \dots, n . \end{array}

(1)

(vii)

Let $| J_{i} | = m$ be the number of entries for CRA for each round.

(viii)

Let $f_{i, J_{i}}^{k} (ρ) | i = 1, \dots, n$ be the function values of link availability [39]. These values are used as input for the algorithm.

(ix)

Let $y_{i}^{k}$ be the output of the consensus operation.

(x)

A small percentage of nodes are mobile during the route search.

The CRA makes use of an availability function ( $f_{(i, J_{i}^{h})}^{k} (ρ)$ ) to assess the local conditions of the connection between a pair of nodes. The values of an availability function are used as input to the consensus algorithm, which is based on [40]. Equation (2) describes such an availability function, which is calculated for each node of the MDS:

\begin{array}{l} f_{(i, J_{i})}^{k} (ρ) = e^{- ({(λ (J_{i}^{h}) - Γ)}^{2} / σ_{1}^{2} + {h o p s}^{2} / σ_{2}^{2} + {(τ - β (J_{i}^{h}))}^{2} / σ_{3}^{2})} \\ i = 1, \dots, n; h = 1, \dots, m . \end{array}

(2)

This availability function takes into consideration not only the parameters and variables described above, but also other relevant parameters of the MDS, such as the current available bandwidth per link (τ), the idle time in the scheduler of a node (Γ), and the number of hops between a particular pair of nodes (hops). The value obtained from this function is between 0 and 1, which indicates whether such a link is available to be part of the route. Notice that commonly $λ (J_{i}^{h})$ is given in $μ s$ , while $β (J_{i}^{h})$ is given in k bps. Thus, to avoid inconsistencies, both parameters are scaled to $1 0^{1}$ . Let $σ_{i} | i = 1,2, 3$ be standard deviations of λ, τ and hops, respectively.

The algorithmic complexity of the CRA depends on the size of neighbourhood (l) and the degree of a node, that is, the number of nodes with which each node is directly connected ( $D_{G} (n)$ ).

The implementation of the CRA is based on a search tree, in which each branch is evaluated to choose the best candidate. As the number of nodes grows, the neighbourhood l of a node tends to grow. Thus, the search tree also grows in depth as the number of neighbours per node increases.

The CRA is developed for the MDS, through the following steps: (1)

$i = n_{s}$ starts searching for $n_{d}$ by initially searching in a radial neighbourhood of radius ρ. $n_{s}$ gets information about load and idle time in node's scheduler.

For this, $n_{s}$ verifies the values, for its direct neighbours; for information about their link load; and $(c)$ λ, checking for the time available in the scheduler of every node in the neighbourhood. In turn, $n_{s}$ informs to its neighbours to look for $n_{d}$ .

Notice that while $n_{s}$ performs a consensus (described in the following steps), the nodes included in $J_{i}$ simultaneously seek $n_{d}$ in its immediate neighbours. If $n_{d}$ is found at this point, the routing finishes. Otherwise, the neighbours start a new consensus, now with their own direct neighbours, by calculating the availability function, using (2). Then values that are proposed to begin the consensus are the values obtained by the availability function on each pair consisting of $n_{s}$ and its neighbours.

(2)

Calculate the numerical distances $m (m - 1) / 2$ input pairs. The numerical distances are calculated using

\begin{matrix} d_{(J_{i}^{h}, J_{i}^{h + 1})} = |f_{(i, J_{i}^{h})}^{k} (ρ) - f_{(i, J_{i}^{h + 1})}^{k} (ρ)|, h = 1, \dots, m . \end{matrix}

(3)

Determine the “degree of closeness,” or “level of agreement,” of all $m (m - 1) / 2$ input pairs based on

\begin{matrix} s_{(J_{i}^{h}, J_{i}^{h + 1})} = \frac{1}{1 + p d_{(J_{i}^{h}, J_{i}^{h + 1})}^{q}}, h = 1, \dots, m . \end{matrix}

(4)

This function (known as “agreement indicator”) provides a value for the agreement of inputs $J_{i}^{h}$ and i, based on their numerical distance. The numerical distance is then considered as the comparison of the availability of each data link between two neighbouring nodes.

In this function, the parameters p and q are used only for tuning purposes. The parameter q tunes the rate of roll-off of this function, while the parameter p is used to set the midpoint value of the function. This function is continuous and generates $s_{(i, J_{i}^{h})} = 1$ for numerically equivalent input pairs. For differing inputs, it produces a real value in the range (0,1) such that, as $d_{(i, J_{i}^{h})}$ gets larger, $s_{(i, J_{i}^{h})}$ tends towards zero [40].

(4)

After obtaining the agreement indicator values for all of the input pairs ( $i, J_{i}^{h}$ ), a weight value is assigned for each input pair based on (5). An input value that differs greatly from the other input values is assigned a smaller weight than an input value that is close to any of the other input values [40]:

\begin{array}{l} w_{(i, J_{i}^{ω})} = \frac{1}{1 + \prod_{h \neq ω, h = 1}^{m} s_{(J_{i}^{ω}, J_{i}^{h})}}, \\ 0 < w_{(i, J_{i}^{ω})} < 1, ω = 1, \dots, m . \end{array}

(5)

This type of weighting directly indicates the influence of the agreement between any particular input and the other inputs on its weight value [40].

(5)

The output of the consensus is obtained using

\begin{matrix} y_{i}^{k} = \frac{\sum_{h = 1}^{m} w_{(i, J_{i}^{h})} f_{(i, J_{i}^{h})}^{k} (ρ)}{\sum_{h = 1}^{m} w_{(i, J_{i}^{h})}} . \end{matrix}

(6)

The value of $y_{i}^{k}$ is compared with the input values, so the node in J corresponding to the input associated with (7) is chosen as the winner of the consensus:

\begin{matrix} \min (|y_{i}^{k} - f_{(i, J_{i}^{h})}^{k} (ρ)|) = G^{k}, h = 1, \dots, m . \end{matrix}

(7)

The node is named $G^{k}$ and acts as the original source node $n_{s}$ for the next route discovery. Then, the value decided by CRA is $G^{k}$ . Moreover, notice that this new route discovery is carried out in a more efficient way, since the nodes that participated in the previous consensus now look up their own $y_{J_{i}^{h}}^{k}$ and may use this value for another route discovery of consensus in a kth future step. This is so since all nodes in $J_{i}$ have calculated their $y_{J_{i}^{h}}^{k}$ regarding their immediate neighbours.

(7)

Finally, after several route discoveries, some node should have $n_{d}$ in its $J_{i}$ , and a route has been found between $n_{s}$ and $n_{d}$ . This route is made up by all the winners of every consensus. So, a path of k steps would be made up by the corresponding nodes, which can be represented as a sequence:

\begin{matrix} n_{s} ⟶ G^{1} ⟶ G^{2} ⟶ \dots ⟶ G^{k} ⟶ n_{d} . \end{matrix}

(8)

Every $G^{k}$ is a local minimum, to be maintained if the values of nodes β and λ do not change. This is the case for a mobile topology. The choice of a local minimum provides the most suitable node to transmit among reachable nodes in the kth step.

The objective of this routing algorithm is to consider local conditions. This will allow the nodes to decide a route based on such local, bounded conditions.

This routing algorithm makes use of a consensus algorithm to evaluate such local conditions, allowing “deciding” which neighbour node to use as router and thus going on building a route aiming to the destination node.

The CRA makes use of the concept of l-neighbourhood and achieves the purposes of avoiding a complete flooding of the MDS. The algorithm has been tested considering the number of hops as a parameter for defining the reach of the l-neighbourhood.

5. Experiments

Simulation experiments have been carried out with the CRA for a mobile topology, using a MDS of 100 nodes. These nodes were distributed based on a normal distribution.

All simulations have been implemented using Matlab. Note that, for each step of the route, the CRA is applied until the destination node is found or when a time-out condition is declared. Figure 1 shows CRA's behaviour in a network, where the source node ( $n_{s}$ ) is placed at coordinates $(87, 71)$ and the destination node ( $n_{d}$ ) is placed at coordinates $(95, 89)$ .

Figure 1

Network used in this example.

Using this network, both algorithms (CRA and flooding) were executed with the following results. The results of CRA are presented in Table 1 and Figure 2. Table 1 shows (in time) construction step by step of a route between node A and node B. The first column displays the times CRA has been used before reaching the destination node. The second column shows location of each source node to the start of each execution of CRA. The winner path is shown in columns 2, 3, and 4; it is composed of 3 pairs of coordinates: the first pair of coordinates is the source node for corresponding round, and the second and third pairs of coordinates correspond to source node's direct neighbour and a neighbour of this, which has been evaluated before by CRA as the most suitable path. In round 4 destination node is reached. The total cost of this search is 5.93 units of availability function, and the total distance covered is 64.61 units.

Table 1

CRA's results for searching a route from node placed at (87, 71) to destination node placed at (95, 89).

Round	$n_{s}$		$n_{d}$	Cost	Distance
1	(87, 71)	(84, 57)	(90, 55)	1	20.78
2	(90, 55)	(87, 60)	(84, 57)	1.97	9.99
3	(84, 57)	(88, 67)	(92, 80)	1.97	24.57
4	(92, 80)	(95, 89)		0.99	9.26
				5.93	64.61

Figure 2

CRA's results for searching a route from node placed at $(87, 71)$ to destination node placed at $(95, 89)$ .

The data reported in Table 1 are depicted in Figure 2.

For comparison purposes, using the same network, source node, and destination node, the experiment was replicated using the flooding algorithm. The results are displayed in Table 2, where column 1 displays the number of rounds in which the result was obtained for the corresponding row. In this experiment, the flooding algorithm was run 2 times and 43 results were obtained, of which 7 are of round 1 and the rest of the latter. The route reaching the destination node consists of three nodes, but there were 41 extra parallel transmissions. The total cost of this search is $41.74$ units in the availability function, and the total distance covered is $464.78$ units. The data displayed in Table 2 are shown in Figure 3.

Table 2

Flooding algorithm results for searching a route from node placed at (87, 71) to destination node placed at (95, 89).

Round	$n_{s}$	$n_{d}$	Cost	Distance
1	(87, 71)	(88, 67)	0.98	5.119
2	(88, 67)	(54, 50)	0.9956	6.98
2	(88, 67)	(58, 52)	0.9914	9.30
2	(88, 67)	(45, 65)	0.9627	10.08
2	(88, 67)	(44, 46)	0.992	10.54
2	(88, 67)	(42, 46)	0.8929	11.42
2	(88, 67)	(56, 65)	0.7344	11.72
2	(88, 67)	(43, 45)	0.986	11.74
2	(88, 67)	(39, 61)	0.986	12.16
2	(88, 67)	(49, 43)	0.9961	12.75
2	(88, 67)	(49, 42)	0.9854	13.42
1	(87, 71)	(95, 72)	0.99	8.663
2	(95, 72)	(16, 22)	0.99	7.87
2	(95, 72)	(6, 7)	0.94	11.39
2	(95, 72)	(3, 13)	0.99	12.38
1	(87, 71)	(92, 80)	0.98	10.46
2	(92, 80)	(95, 18)	0.99	4.34
2	(92, 80)	(90, 17)	0.98	9.38
2	(92, 80)	(87, 25)	0.99	14.02
1	(87, 71)	(87, 60)	0.99	11.02
1	(87, 71)	(76, 62)	0.99	13.31
2	(77, 62)	(82, 94)	0.99	5.18
2	(77, 62)	(95, 89)	0.99	8.84
1	(87, 71)	(91, 84)	0.95	13.47
2	(91, 84)	(80, 4)	0.99	7.88
2	(91, 84)	(78, 7)	0.98	10.02
2	(91, 84)	(97, 1)	0.99	10.19
2	(91, 84)	(76, 6)	0.90	11.36
2	(91, 84)	(99, 2)	0.97	11.48
2	(91, 84)	(90, 17)	0.98	13.64
1	(87, 71)	(84, 57)	0.98	14.42
2	(84, 57)	(49, 42)	0.98	5.51
2	(84, 57)	(49, 43)	0.99	6.06
2	(84, 57)	(49, 29)	0.99	8.02
2	(84, 57)	(44, 46)	0.99	11.02
2	(84, 57)	(43, 45)	0.98	11.15
2	(84, 57)	(42, 46)	0.89	12.29
2	(84, 57)	(41, 26)	0.82	13.79
2	(84, 57)	(54, 50)	0.99	13.90
2	(84, 57)	(40, 27)	0.99	14.14
2	(84, 57)	(40, 26)	0.97	14.61
2	(84, 57)	(37, 31)	0.98	14.68
2	(84, 57)	(52, 22)	0.97	14.87
			41.74	464.78

Figure 3

Flooding algorithm results for searching a route from node placed at $(87, 71)$ to destination node placed at $(95, 89)$ .

6. Results

In the simulations that have been performed, the flooding algorithm established 44 connections while searching exhaustively the destination node, evaluating each link using an “availability function.” The total cost of the search was $41.74$ units and the distance covered was $464.78$ units. Instead, CRA established only 7 links having $5.93$ units of cost, and the distance covered was $64.61$ units.

It often happens that CRA presents a routing-loop, so that the destination node is not reached. In order to prevent the algorithm from reaching a state of completion, a number ξ that will limit the time that a node can be in a cycle before stopping the process is defined. Therefore, a flag is sent and the algorithm will terminate correctly.

The flooding algorithm does not consider the local conditions of a node, so that the choice of nodes belonging to the route is inefficient, in the sense that it is not ensured that these nodes are available to transmit, and this increases the probability of delays during the routing process.

7. Conclusions

The route obtained by the CRA is represented as a sequence of nodes with the best conditions for transmitting like a router and thus reducing the communication efficiency of such a route. By using a limited neighbourhood, the number of active connections is significantly reduced, particularly when compared with flooding. However, the flooding algorithm obtains a route in less time, but this route is more likely to be inefficient compared with the route calculated by the CRA.

Footnotes

Conflict of Interests

The authors declare that there is no conflict of interests regarding the publication of this paper.

Acknowledgments

The authors would like to thank the financial support of PAPIIT UNAM INI00813 and CONACYT 176556 and technical assistance of Ing. Adrian Durán and Ing. Joel Durán.

References

Sengul

Kravets

Bypass routing: an on-demand local recovery protocol for ad hoc networks

Ad Hoc Networks 2006 4 3 380 397

10.1016/j.adhoc.2004.10.004

2-s2.0-29644438328

Marina

M. K.

Das

S. R.

Mohapatra

Krishnamurthy

S. V.

Routing in mobile ad hoc networks

Ad Hoc Networks 2005

New York, NY, USA

Springer

63 90

10.1007/0-387-22690-7_3

Perkins

C. E.

Royer

E. M.

Ad-hoc on-demand distance vector routing

Proceedings of the 2nd IEEE Workshop on Mobile Computing Systems and Applications (WMCSA ′99)

February 1999

90 100

10.1109/mcsa.1999.749281

2-s2.0-34347349933

Johnson

Maltz

The dynamic source routing protocol (DSR) for mobile ad hoc networks for IPv4

RFC 2007 4728 (Experimental)

IETF

Park

V. D.

Corson

M. S.

A highly adaptive distributed routing algorithm for mobile wireless networks

Proceedings of the 16th Annual Joint Conference of the IEEE Computer and Communications Societies, Driving the Information Revolution (INFOCOM ′97)

1997

1405

Perkins

C. E.

Bhagwat

Highly dynamic Destination-Sequenced Distance-Vector routing (DSDV) for mobile computers

ACM SIGCOMM Computer Communication Review 1994 24 4 234 244

10.1145/190809.190336

Jacquet

Mühlethaler

Clausen

Laouiti

Qayyum

Viennot

Optimized link state routing protocol for ad hoc networks

Proceedings of the IEEE International Multi Topic Conference

2001

62 68

Murthy

Garcia-Luna-Aceves

J. J.

An efficient routing protocol for wireless networks

Mobile Networks and Applications 1996 1 2 183 197

10.1007/BF01193336

2-s2.0-0030264587

Pearlman

M. R.

Haas

Z. J.

Determining the optimal configuration for the zone routing protocol

IEEE Journal on Selected Areas in Communications 1999 17 8 1395 1414

10.1109/49.779922

10.

Ramasubramanian

Haas

Z. J.

Sirer

E. G.

SHARP: a hybrid adaptive routing protocol for mobile ad hoc networks

Proceedings of the 4th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc ′03)

June 2003

New York, NY, USA

ACM

303 314

2-s2.0-0242443766

11.

Toh

C.-K.

Associativity-based routing for ad hoc mobile networks

Wireless Personal Communications 1997 4 2 103 139

10.1023/a:1008812928561

2-s2.0-0031096869

12.

Spohn

Garcia-Luna-Aceves

J. J.

Neighborhood aware source routing

Proceedings of the 2nd ACM International Symposium on Mobile Ad Hoc Networking & Computing (MobiHoc ′01)

2001

11 21

10.1145/501417.501419

13.

Aron

I. D.

Gupta

S. K. S.

Gupta

E. K. S.

Analytical comparison of local and end-to-end error recovery in reactive routing protocols for mobile ad hoc networks

Proceedings of the ACM Workshop on Modeling, Analysis and Simulation of Wireless and Mobile Systems

2000

69 76

14.

Haas

Z. J.

Pearlman

M. R.

Samar

The zone routing protocol (zrp) for ad hoc networks

draft-ietf-manet-zone-zrp-04.txt, 2002

15.

Caesar

Castro

Nightingale

E. B.

O'Shea

Rowstron

Virtual ring routing: network routing inspired by DHTs

Proceedings of the Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications (SIGCOMM ′06)

2006

ACM

351 362

10.1145/1159913.1159954

16.

Chen

Morris

Scalable landmark routing and address lookup for multihop wireless networks

2002 837 Scalable landmark routing and address lookup for multihop wireless networks,

17.

Pei

Gerla

Hong

Lanmar: landmark routing for large scale wireless ad hoc networks with group mobility

Proceedings of the 1st ACM International Symposium on Mobile Ad Hoc Networking & Computing (MobiHoc ′00)

2000

Piscataway, NJ, USA

IEEE Press

11 18

18.

Fonseca

Ratnasamy

Culler

Shenker

Stoica

Beacon vector routing: scalable point-to-point in wireless sensornets

2004 IRB-TR-04-012

Intel Research

19.

Das

S. M.

Pucha

Y. C.

Performance comparison of scalable location services for geographic ad hoc routing

Proceedings of the 24th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM ′05)

March 2005

1228 1239

10.1109/INFCOM.2005.1498349

20.

Karp

Kung

H. T.

Gpsr: greedy perimeter stateless routing for wireless networks

Proceedings of the 6th Annual International Conference on Mobile Computing and Networking (MOBICOM ′00)

August 2000

New York, NY, USA

ACM

243 254

2-s2.0-0034547115

21.

Seydim

A. Y.

Wormhole routing in parallel computers

1998

22.

Cormen

T. H.

Stein

Rivest

R. L.

Leiserson

C. E.

Introduction to Algorithms 2001

McGraw-Hill Higher Education

23.

Medhi

Ramasamy

Network Routing: Algorithms, Protocols, and Architectures 2007

San Francisco, Calif, USA

Morgan Kaufmann

24.

Saber

R. O.

Richard

Murray

R. M.

Consensus protocols for networks of dynamic agents

Proceedings of the 2003 American Control Conference

June 2003

25.

Broustis

Faloutsos

Routing in vehicular networks: feasibility, modeling, and security

International Journal of Vehicular Technology 2008 2008 8

267513

10.1155/2008/267513

26.

Mohar

The Laplacian spectrum of graphs

Graph Theory, Combinatorics, and Applications 1991

New York, NY, USA

John Wiley & Sons

871 898

MR1170831

27.

Jorstad

DeMenthon

Wang

I.-J.

Burlina

Distributed consensus on camera pose

IEEE Transactions on Image Processing 2010 19 9 2396 2407

10.1109/TIP.2010.2047167

MR2751968

2-s2.0-77955824117

28.

Olfati-Saber

Fax

J. A.

Murray

R. M.

Consensus and cooperation in networked multi-agent systems

Proceedings of the IEEE 2007 95 1 215 233

10.1109/JPROC.2006.887293

29.

Doerr

Goldberg

L. A.

Minder

Sauerwald

Scheideler

Stabilizing consensus with the power of two choices

Proceedings of the 23rd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA ′11)

June 2011

149 158

10.1145/1989493.1989516

2-s2.0-79959660547

30.

John

J. P.

Katz-Bassett

Krishnamurthy

Anderson

Venkataramani

Consensus routing: the internet as a distributed system

Proceedings of the 5th USENIX Symposium on Networked Systems Design and Implementation (NSDI ′08)

2008

Berkeley, Calif, USA

USENIX Association

351 364

31.

Vahdat

Becker

Epidemic Routing for Partially-Connected Ad Hoc Networks 2000

32.

Yazir

Y. O.

Farahbod

Guitouni

Ganti

Coady

Adaptive routing in mobile ad hoc networks based on decision aid approach

Proceedings of the 8th ACM International Symposium on Mobility Management and Wireless Access (MobiWac ′10)

October 2010

1 10

10.1145/1868497.1868499

2-s2.0-78650162647

33.

Fagiolini

Bicchi

On the robust synthesis of logical consensus algorithms for distributed intrusion detection

Automatica 2013 49 8 2339 2350

10.1016/j.automatica.2013.04.033

MR3072625

2-s2.0-84882455560

34.

Kuhn

Oshman

Moses

Coordinated consensus in dynamic networks

Proceedings of the 30th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC ′11)

2011

1 10

10.1145/1993806.1993808

35.

Benchi

Launay

Guidec

Solving consensus in opportunistic networks

Proceedings of the 16th International Conference on Distributed Computing and Networking (ICDCN ′15)

January 2015

Goa, India

36.

Peng

Han

Q.-L.

A novel event-triggered transmission scheme and

L_{2}

control co-design for sampled-data control systems

IEEE Transactions on Automatic Control 2013 58 10 2620 2626

10.1109/TAC.2013.2256015

37.

Peng

Zhang

Event-triggered output-feedback

H_{\infty}

control for networked control systems with time-varying sampling

IET Control Theory & Applications 2015

10.1049/iet-cta.2014.0876

38.

Macfarlane

Network Routing Basics 2005

New York, NY, USA

John Wiley & Sons

39.

Arellano-Vàzquez

Benítez-Pérez

Ortega-Arjona

J. L.

Study of routing algorithms considering real time restrictions using a connectivity function

Towards Autonomous Robotic Systems: 12th Annual Conference, TAROS 2011, Sheffield, UK, August 31-September 2, 2011. Proceedings 2011 6856

Berlin, Germany

Springer

412 413 Lecture Notes in Computer Science

10.1007/978-3-642-23232-9_53

40.

Latif-Shabgahi

G. R.

A novel algorithm for weighted average voting used in fault tolerant computing systems

Microprocessors and Microsystems 2004 28 7 357 361

A Consensus Routing Algorithm for Mobile Distributed Systems

Abstract

1. Introduction

2. Related Work

3. Contributions

4. The Consensus Routing Algorithm (CRA)

5. Experiments

6. Results

7. Conclusions

Footnotes

Conflict of Interests

Acknowledgments

References