# A Consensus Routing Algorithm for Mobile Distributed Systems

Authors: Magali Arellano-Vázquez; Héctor Benítez-Pérez; J. Ortega-Arjona
Journal: International Journal of Distributed Sensor Networks
 (2015)

---

## Abstract

This paper introduces aconsensus 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.


---

## Body

## 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. AConsensus 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 timeT.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. Section2 presents an overview of theCRA; 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) withn nodes, consider the following parameters and variables:(i)
Letnode be a data structure per node that includes the following fields:
(1)
Unique ID per node.(2)
Axesx 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)
Letns be thesource node, from which the route discovery process starts, and let nd be thedestination node, to which the route discovery process ends.(iii)
LetdG(i) be thedegree of nodei, that is, the number of links incident to the node i.(iv)
Letk be thetotal number of routing steps of a given route.(v)
Letl beneighbourhood with respect to a node, whose extension is presented in number of hops.(vi)
LetJi 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 Ji. The set Ji can be defined as in(1)Ji=j:xi-xj∧yi-yj≤ρi=1,…,n,j=1,…,n.(vii)
Let|Ji|=m be the number of entries for CRA for each round.(viii)
Letfi,Jikρ∣i=1,…,n be thefunction values of link availability [39]. These values are used as input for the algorithm.(ix)
Letyik be the output of the consensus operation.(x)
A small percentage of nodes are mobile during the route search.The CRA makes use of anavailability function (f(i,Jih)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:(2)fi,Jikρ=e-λJih-Γ2/σ12+hops2/σ22+τ-βJih2/σ32i=1,…,n;h=1,…,m.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 λ(Jih) is given in μs, while β(Jih) is given in k bps. Thus, to avoid inconsistencies, both parameters are scaled to 101. 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 (DG(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 neighbourhoodl 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=ns starts searching for nd by initially searching in a radial neighbourhood of radius ρ. ns gets information about load and idle time in node’s scheduler.For this,ns 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, ns informs to its neighbours to look for nd.Notice that whilens performs a consensus (described in the following steps), the nodes included in Ji simultaneously seek nd in its immediate neighbours. If nd 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 ns and its neighbours.(2)
Calculate the numerical distancesm(m-1)/2 input pairs. The numerical distances are calculated using(3)dJih,Jih+1=fi,Jihkρ-fi,Jih+1kρ,h=1,…,m.(3)
Determine the “degree of closeness,” or “level of agreement,” of allm(m-1)/2 input pairs based on(4)sJih,Jih+1=11+pdJih,Jih+1q,h=1,…,m.This function (known as “agreement indicator”) provides a value for the agreement of inputsJih 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 parametersp 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,Jih)=1 for numerically equivalent input pairs. For differing inputs, it produces a real value in the range (0,1) such that, as d(i,Jih) gets larger, s(i,Jih) tends towards zero [40].(4)
After obtaining the agreement indicator values for all of the input pairs (i,Jih), 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]:(5)wi,Jiω=11+∏h≠ω,h=1msJiω,Jih,0<wi,Jiω<1,ω=1,…,m.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(6)yik=∑h=1mwi,Jihfi,Jihkρ∑h=1mwi,Jih.(6)
The value ofyik 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:(7)min⁡yik-fi,Jihkρ=Gk,h=1,…,m.The node is namedGk and acts as the original source node ns for the next route discovery. Then, the value decided by CRA is Gk. 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 yJihk and may use this value for another route discovery of consensus in a kth future step. This is so since all nodes in Ji have calculated their yJihk regarding their immediate neighbours.(7)
Finally, after several route discoveries, some node should havend in its Ji, and a route has been found between ns and nd. 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:(8)ns⟶G1⟶G2⟶⋯⟶Gk⟶nd.EveryGk 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 ofl-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. Figure1 shows CRA’s behaviour in a network, where the source node (ns) is placed at coordinates (87,71) and the destination node (nd) 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 Table1 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.61Figure 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 Table1 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 Table2, 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.78Figure 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 was41.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.



---

*Source: 510707-2015-10-18.xml*