Open access peer-reviewed chapter - ONLINE FIRST

Ant Algorithms for Routing in Wireless Multi-Hop Networks

By Martina Umlauft and Wilfried Elmenreich

Submitted: November 4th 2020Reviewed: July 28th 2021Published: September 21st 2021

DOI: 10.5772/intechopen.99682

Downloaded: 26

Abstract

Wireless Multi-Hop Networks (such as Mobile Ad hoc Networks, Wireless Sensor Networks, and Wireless Mesh Networks) promise improved flexibility, reliability, and performance compared to conventional Wireless Local Area Networks (WLAN) or sensor installations. They can be deployed quickly to provide network connectivity in areas without existing backbone/back-haul infrastructure, such as disaster areas, impassable terrain, or underserved communities. Due to their distributed nature, routing algorithms for these types of networks have to be self-organized. Ant routing is a bio-inspired self-organized method for routing, which is a promising approach for routing in such Wireless Multi-Hop Networks. This chapter provides an introduction to Wireless Multi-Hop Networks, their specific challenges, and an overview of the ant algorithms available for routing in such networks.

Keywords

  • ant algorithms
  • wireless networks
  • ad hoc networks
  • mesh networks
  • wireless sensor networks
  • multi-hop

1. Introduction

Wireless Mesh Networks (WMNs) and Mobile Ad-Hoc Networks (MANETs) are applied in situations where there is no predefined network structure consisting of routers and base station or where the network is dynamic due to a growing number of nodes or mobile nodes moving into areas that have not been previously covered by a base station. Examples for such networks are Wireless Sensor Networks (WSNs) [1], vehicle ad-hoc networks [2], Wireless Senthe OLPC mesh network for children’s computer in developing countries [3], and open grassroots initiatives to support free computer networks such as the Freifunk initiative in Germany [4] or the Funkfeuer initiative in Austria [5].

Routing of messages is a major challenge in such networks due to the dynamic or not a prioriknown network structure. Besides the problem of finding an optimum (or acceptable route) for a message, there is also a mutual influence of a used route on other routes. This calls for a self-organizing approach [6] of choosing routes that are near-optimal on a global level with a decision based on local information.

Artificial ant algorithms give a promising approach for such algorithms. Artificial ant algorithms are bio-inspired algorithms based on real ants’ foraging behavior using a local gradient-following search strategy with pheromone trails. There are different ways how an ant-inspired algorithm can be implemented in Wireless Multi-Hop Networks, for example, by representing ants via network packets and the pheromone by values assigned to the network nodes. Besides the mapping of biological properties into a computer network, Algorithms differ in how route discovery and maintenance are implemented. This chapter investigates different ant algorithms and discusses their applicability to routing in wireless multi-hop networks.

The following section gives an introduction to ant-inspired emergence and self-organization. In Section 2, three forms of Wireless Multi-Hop Networks are introduced (MANET, WSN, or WMN). Section 3 describes first the seminal ant routing algorithm developed for routing in such networks, AntHocNet, followed by an overview of algorithms which build upon this algorithm. Section 4 provides a summary and concluding remarks.

Advertisement

2. Wireless Multi-Hop Networks

Recent advances in wireless communications have enabled the development of Wireless Multi-Hop Networks. Often also called Wireless Ad-Hoc Networks we will in the following use the term Wireless Multi-Hop Networkto avoid confusion with (Mobile) Ad-Hoc Networks described in the next section. A Wireless Multi-Hop Network is a network where nodes communicate via several hops of wireless transmissions over equivalent nodes instead of a central base station. In this chapter we distinguish between (Mobile) Ad-Hoc Networks, Sensor Networks and Wireless Mesh Networks, which are described in the following.

2.1 (Mobile) Ad-Hoc Networks

An Ad-Hoc Networkis defined as a network where all nodes communicate with one another on an ad-hoc basis without a central base station [7]. While sometimes the term is used in literature to denote a Wireless Multi-Hop Network, we use it here to denote a wireless network that does not differentiate between client nodes and dedicated routing nodes. The typical node is a somewhat powerful device such as a (ruggedized) laptop, smartphone, first-responder communication device, or a device that is integrated in a vehicle, all of which are possibly mobile (see Figure 1). In this case, the network is called a Mobile Ad-Hoc NETwork(MANET). These networks were originally developed for military use to enable troop communications in areas where no communications infrastructure was previously deployed. MANETsare also envisioned for emergency and disaster networking where the borders between MANETsand WMNs(see below) are flowing [8].

Figure 1.

MANET architecture. Nodes connect on an ad-hoc basis without dedicated routers or base stations.

Several “classical” routing algorithms have been developed for MANETs, the most prominent being:

  1. DSR: Dynamic Source Routing Protocol was developed in 1994 by David B. Johnson [9]. It is a reactiveprotocol which means that the protocol only builds routes on-demand. This is advantageous in highly volatile networks where it makes no sense to invest routing overhead to build and maintain routes that might go stale before they are used. On the other hand, traffic incurs a route-setup delay because the route is not built in advance. DSR is being standardized by the IETF [10],

  2. DSDV: Destination-Sequenced Distance-Vector Protocol was developed by Charles Perkins and Pravin Bhagwat in 1994 [11]. It is a pro-activerouting protocol, which means that routes are built in advance. This avoids the route-setup delay incurred by reactive protocols but, in highly volatile networks, a lot of routing overhead might be spent to set up and maintain routes that break before they can be used,

  3. AODV: Ad hoc On-Demand Distance Vector Routing [12] developed 1999 by Charles Perkins and Elizabeth Royer which is a reactive routing protocol, and

  4. OLSR: Optimized Link State Routing Protocol [13] which was developed by Jacquet et al. in 2001. It is a proactive routing protocol and has been standardized by the IETF as experimental RFC 3626 [14].

2.2 Sensor Networks

A Sensor Network(or Wireless Sensor Network, WSN) is a wireless network that consists of many sensor nodes which are spatially deployed to cooperatively monitor physical or environmental conditions (see Figure 2). WSNswere initially developed for the military for applications such as battlefield surveillance. However, WSNsare now used in civilian application areas like environmental monitoring [15, 16, 17]. In contrast to MANETssensor nodes are typically tiny (so-called “motes”) and deployed densely in huge numbers, often on inaccessible terrain. Therefore, sensor network protocols must be self-organizing.

Figure 2.

WSN architecture. Sensor nodes are deployed in a sensor field and deliver their measurements through a sink to the Internet.

One of the major problems in sensor networks is the limited power as each sensor only has a small battery. While some sensors use technologies like solar cells to refresh their batteries, routing protocols for sensor networks typically try to optimize for power efficiency [18]. In WSNs, typically the sink initializes routing by issuing a query for measurement data. Sensor nodes answer the query by sending their data back to the sink. To save energy, data may be aggregated along the way (data-centric routing). To facilitate this, the sensor field is often divided into clusters or subnets. All nodes of a cluster first send their data to the respective cluster head, which then processes and routes the data to the sink. If the sensors are equipped with location finding devices like GPS (Global Positioning System), knowledge of the position can be used to ease cluster formation or perform geo-routing. Well known non-ant routing protocols for WSNsinclude:

  1. Gossiping is an early approach derived from flooding [19],

  2. SPIN: Sensor Protocols for Information via Negotiation is a family of protocols based on data-centric routing, developed by Heinzelman et al. in 1999 [20],

  3. GPSR: Greedy Perimeter Stateless Routing in Wireless Networks, a geo-routing algorithm developed by Brad Karp in 2000 [21, 22],

  4. LEACH: Low-Energy Adaptive Clustering Hierarchy developed by Heinzelman et al. in 2000 [23] which is a clustering-based protocol that minimizes energy dissipation,

  5. SAR: Sequential Assignment Routing is an algorithm which selects paths based on energy resources, a QoS metric, and the packet’s priority level. SAR was developed by Sohrabi et al. in 2000 [24] as part of a protocol suite for WSNs, and

  6. Directed Diffusion, an approach using data-centric dissemination, reinforcement-based adaptation to the empirically best path, and in-network data aggregation and caching. Directed Diffusion was developed by Intanagonwiwat et al. in 2000 [25].

2.3 Wireless Mesh Networks

A Wireless Mesh Network(WMN) is a wireless networking architecture in which nodes are connected via a wireless backbone[26]. In contrast to MANETs, though, the wireless backbone in a WMNis typically fixed. Iow. a WMNconsists of non-moving wireless mesh router nodes which constitute the wireless backbone and (potentially mobile) client nodes (see Figure 3). Router nodes can be mesh routers only (so-called Mesh Points, MP [27]) or act as combined WLANMesh Access Points (MAPs)/routers.

Figure 3.

WMN architecture. Client nodes connect via a wireless backbone. MP, Mesh Point; MAP, Mesh Access Point; MPP, Mesh Portal Point.

WMNscan be used as access networks to the Internet, where one or several Mesh Portal Points (MPP) connect the mesh to the Internet. They can also be used in disaster areas, for emergency response teams, and for the military. The boundary towards MANETsis somewhat fluid in these cases [8]. Consider, for example, a rescue operation where wireless routers are installed on top of firetrucks. When the firetrucks arrive at the scene, they stop and provide the wireless backbone for the firefighters’ communication devices. This scenario can be seen as a WMNas well as as a MANET.

Even with a stationary wireless backbone, the characteristics of wireless channels and the interaction of the MAC layer with the higher layers in the network stack make routing in WMNsa hard problem. Wireless links vary over time and problems like the hidden node problem or the exposed node problem influence routing algorithm’s performance. Therefore, a “wireless-aware” routing algorithm is necessary.

WMNshave slightly different constraints and pose different problems than MANETsand sensor networks. For example, the power constraint which is very prominent in sensor networks typically does not exist in WMNs[8]. When WMNsare used as access networks to the Internet “normal internet traffic” has to be assumed. This means application traffic like streaming, web browsing, VoIP (Voice over IP) and video conference traffic, or email, which use the standard TCP (or UDP) protocol stack. Routing algorithms for WMNshave mostly been adapted from the (Mobile) Ad-Hoc Networking Community.

Advertisement

3. Ant Colony Optimization and Ant-Routing Algorithms

Ant algorithms are inspired by the natural foraging behavior of certain species of ants. Based on the famous double bridge experiment, reported on by Goss, Aron, Denebourg and Pasteels in 1989 [28], ant-inspired optimization was then codified into an Ant Colony Optimizationmetaheuristic [29] which was originally implemented in algorithms such as Ant System[30] and Ant Colony System[31].

In general, algorithms using the Ant Colony Optimizationmetaheuristic work as follows: an optimization problem is transformed into a graph G=VE, ants travel along the graph using pheromones (if present) to choose a path stochastically and after the ants have finished their travel, the pheromone values in the graph are updated according to the “goodness” of the solutions found by the ants. Many algorithm variants, also improve their results with a local search phase that is applied before updating the pheromone values. Besides other combinatorial optimization problems, these algorithms have been shown to be able to solve the traveling salesman problem. In Ant System, the first algorithm to implement the Ant Colony Optimizationmetaheuristic, the ants choose their path according to Eq. (1):

pijk=τijαηijβcilNspτilαηilβifcijNsp,0otherwiseE1

where an ant kin a city ichooses the next city jwith probability pijkwith spthe partial solution constructed so far and N(spthe set of possible edges leading only to cities not visited so far. The parameters αand βbalance the importance of pheromone versus the local heuristic ηij=1/dijwith dijthe distance between city iand city j.

Pheromones are updated using the update rule in Eq. (2):

τij1ρτij+k=1mΔτijk.E2

with ρthe evaporation rate, mthe number of ants and Δτijkproportional to the inverse of the lenght of the tour ant ktook if that link was chosen (0otherwise).

A variant aimed specifically at (wired) networks is AntNet[32]. These algorithms were not developed with Wireless Multi-Hop Networks in mind, though. As described above, Wireless Multi-Hop Networks have their own challenges in addition to the challenges of routing in a fixed network.

In the following, we will describe the seminal ant routing algorithm developed for Wireless Multi-Hop Networks, AntHocNet[33], and then give an overview of the typical features of other ant routing algorithms for these types of networks.

3.1 AntHocNet

AntHocNet[33], 2005, by Di Caro, Ducatelle, and Gambardella is the seminal ant algorithm developed for mobile ad-hoc networks. It addresses the special challenges that such wireless networks pose: bandwidth is typically less than in fixed networks, and links can change their quality or break. Therefore, AntHocNetis realized as a hybrid algorithm that combines features from pro-active and reactive routing protocols. In this way, it does not waste resources to set up paths before any packet is sent, which might not exist anymore by the time they are eventually needed.

Like all wireless routing algorithms, nodes running AntHocNetneed to determine which other nodes are reachable by wireless transmission (iow. the one-hop neighborhood). AntHocNetnodes do this by broadcasting very short “hello” messages at regular intervals. Receiving nodes then set up these neighboring nodes in their respective routing tables, but without any routing information yet. These “hello” messages are also used to detect link failures.

When a new data packet is to be sent from a source node sto a destination node d, the algorithm enters its reactive path setup phase. There exist two possibilities: either there already exists routing information for a path between sand d(after the protocol has run for a while and packets have already been sent) or not. Depending on whether routing information already exists or not, AntHocNetsends so-called “forward ants” either by broadcasting them (if no routing information for the required route exists yet) or by unicasting them stochastically along one of the already known routes. For unicasting, the pheromone routing tables at the intermediate nodes are exploited and the next hop ntowards the destination dis chosen stochastically with a probability Pndaccording to Eq. (3):

Pnd=TndiβjNdiTjdiβ,β1.E3

with ithe current node, nthe next hop, Tthe respecitve pheromone value, Ndithe set of possible neighbors and a coefficient βthat controls how explorative the algorithm behavior is.

If there is no pheromone information available yet, the forward ant is broadcasted. To avoid flooding the network with too much traffic, these broadcast ants are restricted in several ways: 1) after a number of hops, they are killed, 2) when a node receives several ants stemming from the same broadcast (that took different paths to reach this node), it will only pass on those ants which came via sufficiently good paths (using the number of hops and travel time as metrics). The threshold for this can be set by a parameter α1. In this way, several parallel paths can be explored while the worst paths are quickly excluded and overhead (which is always of special concern in wireless networks) is kept at a reasonable level. A second parameter α2is used to spread paths more widely among the network: broadcast ants which took a different first hop than previous ants stemming from the same broadcast, this less restrictive parameter α2is applied instead of α1.

Ants memorize the path they travel and when a forward ant has reached the destination node, a so-called backward ant is created which travels back the path P=sn1n2dit came. This backward ant then updates all the pheromone information along the path according to Eq. (4):

Tndi=γTndi+1γτdi,γ01.E4

where τdiis an expression of the “goodness” of the path, based on an estimate of the average time to send a packet over the path Pcalculated from measurements at each node’s MAC layer.

After one or several path(s) has been found and while a data session is running, AntHocNetforwards the data packets stochastically along all the available paths using the same Eq. (3) as the forward ants but with a higher value of β. This means that data packets have a more exploitative behavior than ant packets which explore more.

During a data session, AntHocNetenters its pro-active phase and sends forward ants in addition to the data packets. These again use Eq. (3) but have a small probability of being broadcast instead. The ants that follow the existing path via Eq. (3) update the current quality of the existing path while those ants that are broadcast can potentially find new, better paths which will then be immediately used as potential paths to route data. Due to the way paths are determined and updated during the pro-active phase and due to the stochastic nature of the data routing, data packets are sent in an automatically load-balanced way through the network which expecially helps with wireless transmission as two parallel paths use the same transmission medium and therefore can potentially greatly influence each other.

AntHocNetalso addresses link failures, which occur much more frequently in the wireless domain. As mentioned before, link failure can be detected via “hello” messages – if there has not been an “hello” message for a certain amount of time (several times the regular sending interval), a link to a node will be considered broken. A link is also considered broken if a unicast message to a node fails. The algorithm then enters its local path repair mode where it broadcasts so-called “path repair ants” that work just like the forward ants in reactive mode, except that they are more limited in their maximum number of allowed broadcasts. If a path can be repaired within a certain amount of time, the data packets (which will have been buffered in the meantime) will be sent to the destination node. If the path can not be re-established within a reasonable time limit, the data is discarded and link failure notifications are broadcasted to the surrounding nodes.

3.2 ARA

ARA(Ant-Colony-based Routing Algorithm) was proposed for MANETsby Güne s, Sorges and Bouazizi in 2002 [34]. ARAis based on a version of Ant Colony Optimizationwhich the authors call “Simple ACO”. Its main goal is to reduce the overhead of routing as compared to classical routing algorithms. The algorithm consists of three phases: route discovery, route maintenance, and route failure handling. It uses routing tables at each node niwhich consist of records of the form ndnnφi,nwhere ndis the destination node, nnthe next hop node and φi,nthe pheromone value for this link and destination. Ants carry a sequence number and the source address they originated from.

The transition rule looks very much like that of AntHocNet(cf. also Eq. (3)) with a coefficient of β1=1:

pi,n=φi,njNiφi,jnNi0nNiE5

where pi,nis the transition probability of going from the current node nito node nnand Niis the set of one-hop neighbors of ni.

In contrast to AntHocNet, though, ants are used differently as follows:

  • During route discovery, forward ants do not follow the transition rule but are broadcasted instead. Duplicate forward ants can be detected by their sequence number and source address and are not forwarded.

  • On its way through the network, the forward ant immediately updates the pheromone tables at the nodes – for the way back to the source. The forward ant is interpreted similarly to backward ants in AntHocNet. When a forward ant arrives at a node, the routing table entry where ndequals the source address in the ant and nnequals the last hop the ant took is updated. Backward ants are used analogously and establish the path to the destination node as usual.

The pheromone update rule in ARAis quite simple; an ant changes the pheromone value moving from node nito nnby a constant amount:

φi,nφi,n+Δφ.E6

Güneş et al. suggest that the number of hops an ant has traveled to the current node could also be included in the calculation of the new amount of pheromone. Pheromone is evaporated in regular intervals according to the evaporation rule shown in Eq. (7). The authors suggest that the link quality measurements should be incorporated into the evaporation rule rather than into the pheromone update rule as usual. This has the advantage that nodes can update local changes of link quality much more quickly. On the other hand, the disadvantage of this method is that the quality reflected by the amount of pheromone reflects local link quality only instead of end-to-end path quality.

φi,n1qφi,n,q01E7

Route maintenanceis done by observing the traffic flowing through the network. Traffic does not have to be encapsulated in ant packets; rather, nodes autonomously update the pheromone tables according to the pheromone update rule already shown in Eq. (6). For each packet of traffic observed by the node, the pheromone value is increased by the constant amount Δφ. This has the advantage that route reinforcement happens “automatically” without the need for extra ant packets.

To prevent the creation of loops, ARAimplements a simple loop avoidance mechanism. When a node recognizes the duplicate reception of a data packet (identifiable by sequence number and address), it sets an error flag and sends the packet back to the previous node which removes the link from its routing table.

Route failuresare recognized by missing acknowledgements. When a link fails, a node first checks whether it has another route to the required destination in its routing table. If this is the case, it sends the packet via this alternative link. If not, the node informs its neighbors anticipating that they can relay the packet. Failing this, the mechanism tracks back until it arrives back at the source node. In that case, a new route discovery phase has to be initiated by the source node.

3.3 ARAMA

Ant Routing Algorithm for Mobile Ad-hoc networks (ARAMA) was published by Hussein, Saadawi and Lee in 2005 [35]. It is targeted at MANETsand WSNsand focuses on fair resource usage – esp. node energy – across the network. To achieve this, the forward ants carry not only source and destination address and intermediate node IDs but also quality information about the path. To prevent ants from growing too big, the path information is calculated as a normalized local index and computed into a cumulative path index as shown in Eqs. (8) and (9) below. The ant only carries the path index. This novel path index is the main contribution of the paper.

Let pi,mnode i’s normalized optimization parameter mwith 0<pi,m<1. This can be the number of hops, battery power, delay, bandwidth, etc. Then the local normalized index Iifor node iis

Ii=mampi,mE8

where amis the weight of this parameter with mam=1. This leads to 0Ii1. As the forward ant passes a node it updates the path information it carries by calculating the path index Ipathas follows:

Ipath=iIi.E9

Since 0Ii1also 0Ipath1. A bottleneck link on the path correctly influences the overall path index as the value of Ipathis smaller than the smallest Iialong the path. When the forward ant reaches the destination, the path grade ρis computed as

ρ=fIpathIpath,bestE10

where Ipath,bestis the best Ipathreceived in the last Wnumber of ants (Wa suitable window size).

With dthe destination node, ithe current node, and nthe next hop node the transition ruleused by ARAMAis given as

pd,i,n=funτd,i,nηi,njNifunτd,i,jηi,j,nNi0nNiE11

where τd,i,nis the pheromone value for going from current node ito destination dvia next neighbor nand ηi,nis the local heuristic value of the link in. Function funτd,i,nηi,nis chosen to give a high function value when τd,i,nand ηi,nare high; eg. as in the transition rule of AntHocNet.

When the backward ant traverses the network back to the source, the pheromones are updated with the pheromone update rule:

τd,i,nfevapρdτd,i,n)+genfρdifnPathfevapρdτd,i,n)ifnPathE12

with fevapthe evaporation function, genfthe enforcement function, and ρdthe path grade for this path calculated from the information in the forward ant as shown above.

The authors also propose two very interesting extensions to the algorithm:

  1. Negative Backward Ants are sent if a forward ant dies due to running out of TTL (time-to-live) or loop detection. In this case, a negative backward ant is sent which deemphasizes the path by decreasing its pheromone levels.

  2. Destination Trail Ants implement the RARE(Receiver Assisted Routing Enhancement) concept by the same group (Abdelmalek, Hussein, and Saadawi [36]). With this technique, destination nodes send so called “destination trail ants” into the network which randomly mark paths leading to the destination. When forward ants search for this destination there is a probability that they will hit a destination trail left behind by a destination trail ant. This helps to speed up connection setup time.

3.4 AMQR

Ant colony based Multi-path QoS-aware Routing (AMQR) was developed for MANETsby Liu and Feng in 2005 [37]. It is based on ARA(introduced in Section 3.2). In contrast to ARAit supports link-disjoint multi-path routing.

Like ARAit uses the transistion rule from AntHocNetwith a factor β1=1(cf. Eq. (3)).

pi,n=φi,njNiφi,j,ifnNi0ifnNiE13

with pi,nthe probability to go from node nito nnand Nithe set of neighbors of niin dependence of the pheromone value φi,n.

As in ARA, forward ants mark the trail back to the source as they move while backward ants update the trail to the destination. The pheromone values are updated as follows:

φi,n1αφi,n+Δφi,nE14

with αthe pheromone decay parameter and Δφi,ncalculated as

Δφi,n=qmhnE15

where qis the delay time and hthe hop count experienced by the ant so far. The parameters mand nare the weights that determine the relative importance of time delay and hop count.

Forward ants use a frame format of nsndSeqNHopCPasNArrT... where nsis the ID of the source node, ndthe ID of the destination node, and SeqNand HopCthe sequence number and hop count of the ant respectively. The list PasNArrTcontains the IDs of the nodes PasNpassed by the ant and the relevant arrival times ArrT. Backward ants use the same frame format as forward ants but without SeqNand HopC.

The routing table has the usual entries ndnnφi,nwith ndthe destination, nnthe next hop and φi,nthe pheromone value for this link.

During route discovery, a source node first sends hello packets to determine its neighbors and then broadcasts a forward ant. Therefore, there is more than one copy of the forward ant in the system. When an intermediate node receives a forward ant more than once and the ant’s hop count HopCnewHopCold+Δhopsanother entry is made in the routing table to record this alternative path. Parameter Δhopsis the threshold for an acceptable additional path length to avoid overly long alternative paths. Backward ants always choose the best path back to the source.

Nodes exchange routing information by additional communication and build their own view of the topology, and only link-disjoint routes are used. The same concept is used in PPRAshown later (see Section 3.6). Load balancing and route failures are handled as in ARA.

To support QoS, nodes monitor their state and the delay recorded in the ants they receive. If the delay in an ant exceeds a certain limit, the pheromone for the respective link is set to 0and the other pheromone values in the routing table are adjusted to eliminate this high-delay link. If the node itself is overloaded, it initiates a new backward ant to the source to change the route.

3.5 Scalable Ant-based Routing

Ohtaki et al. [38] focus on the scalability of ant-based routing for MANETs. Their algorithm is based on uniform ant routing [39] and borrows the TTL-limiting technique from HSLS (Hazy Sighted Link State) routing [40].

As in uniform ant routing, a probability routing table is kept at each node. For each entry dnthere exists a value pdnwhich gives the probability of routing a packet destined for node dvia neighboring node n. Nodes send periodic control messages (ants) of the form hscTTLwhich wander the network randomly. Here, hsis the source address, cthe cost of all links traversed so far, and TTLthe remaining time-to-live. Whenever a node receives such a control message from a neighboring node lit updates its routing table as follows

pdn=pdn+Δp1+Δp,ifn=lpdn1+ΔpifnlE16

with nNithe set of neighbors of the current node iand Δpgiven by

Δp=kfc,k>0E17

where fcis a function of the total cost cand kthe so-called learning rate of the algorithm. It defines the weight of one ant and is generally less than 0.1.

As the number of nodes in the network increases, the number of ants goes up and becomes a burden on the network. To improve scalability, the Scalable Ant-based Routing algorithm borrows a technique from HSLS [40] to limit the TTLof the control packets. The TTLTkof the k-th ant is calculated as

Tk=2xk+1E18

where

xk=minxmaxmaxxk0mod2x.E19

The authors suggest that xmaxshould be set to half the number of nodes in the network.

Another improvement of this algorithm is the novel ant migration scheme. Instead of a purely random walk, ants try to move as far away from the source as possible. The idea is that ants should not “waste” their TTLin the neighborhood but rather try to cover the whole network. They can find the “direction away from the source” by following those links which have a low probability as a way to the source in the routing table. Iow. when an ant originated from source swas received from node mthe probability qjthat node jwill be chosen as next-hop node among all neighboring nodes except mis calculated as

qj=1psjk=1n1psk1psmE20

to find the next link in direction away from the source. In this way, they use their TTL most efficiently to reach nodes as far away from the source as possible and get good coverage of the network.

3.6 PPRA

PPRAPrioritized Pheromone Aided Routing Algorithm was published by Jeon and Kesidis in 2005 [41]. It is a multipath routing algorithm that considers both energy and latency and supports dual-priority traffic. It is aimed at sensor networks (WSNs) and MANETswith battery constraints and based on ARA[34] (see also Section 3.2). Multipath routes are used to guard against route failures; in case of a route breaking, the already set-up backup route can be used without waiting for another route discovery phase. The multiple paths are also used for load balancing. As the primary path’s pheromones degrade, traffic switches to the alternate routes.

The routing tables at each node niconsist of entries of the form ndnnδidneidnor ndnnidneidnwhere ndis the destination node, nnthe next hop node, δidnthe TTL-pheromone or idnthe Delay-pheromone respectively, and eidnthe Energy-pheromone described later.

During route discoverythe forward ants are broadcasted. Like in source routing, they carry the source address and record all node addresses along the way. Duplicate forward ants are notdiscarded as in single path algorithms. Instead, they are used to set up alternative routes. Note that out of the paths found by the duplicate ants only those which are link-disjoint are kept. Once a forward ant reaches the destination, a backward ant is created, which takes the path found by the forward ant back to the source. For the measurement of energy and delay, periodic control packets are sent in addition to route discovery ants.

Pheromone types: There are three kinds of pheromones in PPRA: TTL-pheromone (δ), Delay-pheromone (), and Energy-pheromone (e). The algorithm has two variants. Variant 1 uses TTL-pheromone and Energy-pheromone, while Variant 2 uses Delay-pheromone and Energy-pheromone.

  1. TTL-pheromoneis used to express the distance in hops (iow. the time-to-live a packet traveling this path will use) and is calculated as

δidnδidn+β1TTLdnE21

with β1a scaling constant and TTLdnthe number of hops between node dand node n. Evaporation for TTL-pheromone is calculated as

δidnδidnβ2with0<β2<1.E22

For highly volatile networks a higher value of β2can be used to decay stale routes faster.

  1. Energy-pheromonerepresents the battery status of the nodes in the path. Similar to Eq. (21) it is calculated as

eidneidn+α1EmindnE23

with α1a scaling constant. Eminrepresents the energy bottleneck on the path, i.e. the lowest battery level encountered in a node along the path. Evaporation for Energy-pheromone is calculated as

eidneidnα2with0<α2<1.E24

  1. Delay-pheromonemarks the cumulative queuing delay experienced along a path. It is calculated analogously to TTL-pheromone as

idnidn+γ1DdnE25

with γ1a scaling constant and Ddnthe cumulative queuing delay between node dand node n. Evaporation for Delay-pheromone is calculated as

idnidnγ2withγ2>1.E26

The algorithm distinguishes between latency-critical and non-critical traffic. For latency-critical traffic, it always uses both pheromone levels (Energy- and TTL-pheromone or Energy- and Delay-pheromone respectively) to determine the route, for non-critical traffic only Energy-pheromone is considered.

The transition rule for non-critical trafficis given in Eq. (27).

peidn=eidnjNieidjE27

where Nithe set of neighboring nodes of i.

The transition rule for latency-critical trafficis calculated by combining Energy-pheromone and TTL-pheromone (algorithm variant 1) or Energy-pheromone and Delay-pheromone (algorithm variant 2) as shown in Eqs. (28)(31) respectively.

Variant1:platidn=θpeidn+pδidnjNiθpeidj+pδi(dj)E28

where

pδxwz=δxwzjNxδxwjE29

and Nxthe set of neighboring nodes of x.

Variant2:platidn=θpeidn+pδidnjNiθpeidj+pδi(dj)E30

where

pidn=1/idnjNi1/idjE31

and Nithe set of neighboring nodes of i.

3.7 EEABR

Energy-Efficient Ant-Based Routing (EEABR) is a routing algorithm based on the Ant Colony Optimizationmetaheuristic. It was developed for WSNsby Camilo et al. in 2006 [42]. The major goal of this algorithm is to increase energy efficiency. The authors propose three algorithms, basic, improved, and energy-efficient ant routing.

pkrs=τrsαEsβuMkτruαEuβ,ifsMk0ifotherwiseE32

where an ant kchooses with probability pkrsto move from node rto node s, τrsthe amount of pheromone for link rs, and Esbeing the factor ηin the Ant Colony Optimizationmetaheuristic. In this case, Esis calculated from the initial energy level of the nodes Cand esthe actual energy level of the node by

Es=1Ces.E33

The backward ant of forward ant kdrops pheromone according to the pheromone update rule given in Eq. (34).

τkrs1ρτkrs+Δτk.E34

Here, 1ρrepresents the evaporation and Δτkis calculated from the total number of nodes Nand the distance Fdktraveled by forward ant kas

Δτk=1NFdk.E35

The first improvement of this basic algorithm uses a refined function for calculating τkwhere the ant carries an energy vector. From this, the average energy level of the path is calculated when the backward ant is created. While this makes it possible to better monitor the energy level on the path it can lead to quite big forward ants. Since in WSNscommunication costs much more energy than local calculation, the authors propose to save ant size by storing only the average (Eavgk) and minimum energy (Emink) found on the path so far in the forward ant. The pheromone update rule in the final EEABRalgorithm is then given as:

τkrs1ρτkrs+ΔτkφBdkE36

where φis a coefficient, Bdkthe traveled distance of the backward ant in hops and

Δτk=1CEminkFdkEavgkFdk.E37

Through factors φand Bdkthe backward ant loses part of its pheromone strength while it travels back to the source – thereby giving shorter paths an advantage in the routing table.

The authors also reduce the memory Mkof already visited nodes in the forward ant to just the last two nodes visited. This means no full path information is stored in the ant anymore, further reducing its size to achieve a so-called “light-weight” ant. The tasks of loop detection and remembering the path back to the source now fall to the nodes themselves. Nodes keep track of the forward ants using a structure npnsantIDtwhere npis the previous node, nsthe next (forward) node, antIDthe ID of the ant and ta timeout value.

When a forward ant is received, a node checks the table whether this ant has been received before. If yes, the ant is discarded as a loop was detected. If no, the ant is forwarded according to the transition rule. When the backward ant returns to the node, it looks up the way back to the source in this same table. The timeout timer tcontrols how long the node keeps the entry in the table. This also determines the maximum time a backward ant may take to come back via this node.

3.8 DDCHA

The Distributed, Data-Centric, Hierarchical Ant algorithm (DDCHA) is a combination of a data-centric protocol with ants developed for WSNs. To aggregate data, the sensor field is divided into subnets where the biggest distance between nodes is still within communication range. Nodes are location-aware and join a subnet based on their location relative to the sink. In each subnet, a core head and a gateway are chosen with the Distributed Energy-Core Generating Algorithm (DECGA) described in the same paper as follows:

  1. Initially, the sink node is the core head, and all sensor nodes are member nodes.

  2. Every node exchanges information about its function (core head, gateway, member) and energy level with its neighbors periodically.

  3. In every period, every node pcomputes its new state

    • If there is no core head in a subnet, then the node with the largest surplus energy becomes the core head.

    • If pis neither a core head nor gateway but neighbor with at least one node of a different subnet then pbecomes a gateway.

The authors prove that this generates an energy-core Ψin the network graph.

Routingis done with the DDCHAant algorithm on top of this network structure as follows: initially, all pheromone values are 0. Every core head can be seen as an ant nest (source) which sends forward ants towards the sink of the WSN. Forward and backward ants both mark their path with pheromones immediately. Unlike ARA(and closer to ant behavior in nature), the ants do not mark the path back to the source/destination but simply drop a fixed amount +Δof pheromone on the forward path. Ants also do not follow a probabilistic routing table but choose the path with the highest amount of pheromone. If an ant can not move on anymore (i.e., it got caught in a loop) it backtracks its path, decreasing the amount of pheromone by Δon the way until it finds a new path. Loop detection is achieved by keeping a forbidden-list of already visited nodes in the ant. Each member node sends its data to the core head first which aggregates the data. The core head then sends the data onto the sink of the WSN.

3.9 Approaches using colored pheromones

Several algorithms are known which make use of “colored pheromones”. This means that trails can be distinguished not only by the amount of pheromone dropped but also by the “color” of the pheromone. In the following, we introduce three approaches for MANETs, WSNs, and WMNsrespectively.

3.9.1 MACO

The original Ant Colony Optimizationmetaheuristic has some drawbacks in terms of stagnation and adaptiveness. Stagnation occurs when a network reaches convergence, and an optimal path is found and chosen by all ants. This, in turn, reinforces this path so much that the probability of selecting other paths becomes very low, which can lead to congestion on the “optimal” path. Adaptiveness describes the ability of an algorithm to react to changes in the network. MACO(Multiple Ant Colony Optimization) was developed to mitigate these problems in MANETsby Sim and Sun in 2002 [43].

MACOuses several ant colonies in parallel, which each use their own color of pheromone. The colonies are entirely separated and cannot sense pheromone other than that of their own color.

Similar to nature, the forward ants immediately drop pheromone on the paths they take. I.e., a “red” forward ant Arwill drop +τron the forward direction of a link it chooses. The backward ant inherits the color from the forward ant and chooses the path back to the source with the highest amount of pheromone in its respective color. Backward ants also drop additional pheromone on the link on their way back.

Depending on the number of ant colonies used in parallel, several paths from the source to the sink can be found. These paths can then be used as alternative routes for load-balancing. Consider the following example with two ant colonies, “red” and “blue”. Lets assume that there are three paths through the network, one long route R1and two similarly short (=good) ones R2,R3with R1>R2R3. With just one ant colony, the true minimum route would be chosen as the optimal path. With two ant colonies, there is a possibility that one colony will find R2as the shortest path and the other colony R3. In this case, two alternative paths of similar quality were found. Therefore, MACOincreases the probability of exploring alternatives.

3.9.2 Division of labour in SANETS

Wireless SANETs(Sensor/Actuator Networks) are a form of WSNwhich also contains actuators (eg. robots). The same energy constraints as in WSNsapply.

Labella and Dressler develop in [44] an ant-based algorithm for division of labour and the routing of the respective traffic in SANETs. In their model, nodes can perform different tasks (measurement of temperature, recording of sound, recording of video, and movement). The goal is to distribute the tasks evenly in the network to get good measurement coverage and not overload single paths with high-load communications (video and audio transmissions).

Nodes choose tasks by employing the AntHocNettransition rule. The probability for a node to choose task ifrom the task list Tagentis

Pi=τiβtaskkTagentτkβtask.E38

Pheromones are updated depending whether the task could be completed successfully or not by

τiminτmax,τi+ΔτE39

if successful and

τimaxτmin,τiΔτE40

if not.

Since tasks are inherently linked with the traffic they generate (simple temperature values, sound, video, or command traffic for movements) tasks imply traffic classes. To deal with these different classes, the authors employ colored pheromones.

Each node ikeeps separate routing tables cRifor each color c. Each entry cRndifor going from node ivia node nto destination dis of the form thesmvwhere tis an estimation of the transmission time, hthe number of hops in the route, ethe energy required for transmission, sthe minimal signal-to-noise ratio on the path, and mand vare flags that indicate whether a node is mobile and still valid for routing.

The transition rule is taken from AntHocNetand evaluated for each color:

Pndi=rcRndiβjNdircRndiβE41

where Ndiis the set of neighbors for which a path to dis known. A different value for βis used during route discovery and data routing. ris a function r:RR+which evaluates the link statistics.

The algorithm also employs an elaborate probabilistic scheme to filter packets and deliberately drop them to avoid congestion (eg. if a measurement value did not change).

3.10 Other Ant-based Algorithms and Techniques

Other ant-based algorithms for Wireless Multi-Hop Networks include the following:

  1. AARAI: Ant Colony Algorithm with Adaptive Improvement was developed by Zeng and He in 2005 [45]. It is targeted at MANETs, based on Ant Colony Optimizationand implements multipath routing.

  2. IAQR: Improved Ant colony QoS Routing, developed by Liu et al. in 2007 [46] is based on Ant Colony System[31] and has the goal to improve QoS routing in MANETs. The transition rule is taken from AntHocNet. It measures each link delay, bandwidth, jitter, and cost and for each node queueing delay, packet loss, jitter, and cost. It uses a global update rule for QoS optimization which changes the decay factor of the pheromone to account for link quality.

  3. Ant-AODV: Ant-Ad Hoc On-Demand Distance Vector Routing by Marwaha et al. [47] combines AODV [12] with ants. It is targeted at MANETs. Ants are used during the route discovery phase to reduce route discovery latency.

  4. Zhang, Kuhn, and Fromherz [48] introduce three new ant routing algorithms for WSNs: Sensor-driven and Cost-aware ant routing (SC), Flooded Forward ant routing (FF), and Flooded Piggybacked ant routing (FP). In SC, they introduce the concept of “sensing ants” which can “smell” other nodes from afar. This is facilitated by exchange of cost estimates from neighboring nodes via HELLO-messages. In FF, forward ants are flooded using the broadcast channel of the WSNand in FP forward ants and data ants are combined to save communications overhead.

Other techniques use ants not directly to perform routing but to support the actual routing algorithm. Examples of these are described in the following.

  1. GPSAL: GPS/Ant-Like Routing Algorithm by Câmara and Loureiro [49, 50] is a location based routing algorithm designed for MANETsand WMNs. Its goal is to use location information to reduce the number of routing messages and speed up route recovery. The assumption is that nodes are equipped with location finding devices like GPS (Global Positioning System). Nodes nikeep routing tables which contain ndloccurrdlocprevdTTLlocprevdtypedwhere ndis the destination node, loccurrdthe current location of nd, locprevdthe previous location of nd, TTLlocprevdthe time-to-live of the previous location of nd, and typedthe mobility type (mobile, stationary) of nd. Ants are only used to collect and seminate location information to the routing tables of the nodes. The actual routing is then calculated on the location entries using a shortest-path algorithm.

  2. T-ANT was developed in 2006 by Selvakennedy et al. [51]. It uses ants for cluster head election in WSNs. The algorithm uses elements from Scalable Ant-based Routing[38] described before (see Section 3.5). The actual routing is performed using a greedy routing scheme.

  3. Ant-aggregation was developed by Misra and Mandal in 2006 [52] for use in WSNs. Here, ants are not used for routing but to determine the optimal in-network data-aggregation points (the optimal nodes for data-aggregation in the WSN). The algorithm is based on Ant Colony Optimization.

Advertisement

4. Conclusions

The versatile and dynamic nature of Wireless Multi-Hop Networks requires routing algorithms that are robust, adaptable, and scalable. Ant Algorithms are inspired from the self-organizing foraging behavior of natural ants, which show an incredible ability for robustness, adaptation and scalability despite being based on a set of simple mechanisms. In this chapter, we have first reviewed the seminal ant routing algorithm developed for routing in such networks, AntHocNet. In the following, we investigate more specific algorithms: ARAis a simple version of an ant colony optimization approach for routing in MANETs. ARAMAis targeted at MANETsand WSNsand focuses on fair energy use between the nodes of the network. EEABRis another algorithm focusing on energy efficiency, providing a more fine-grained selection of routing mechanisms. DDCHAis a data-centric protocol which divides a sensor field into subnets of nodes within communication range. AMQRis a routing algorithm for MANETsthat extends upon ARA. A concept for dual-priority traffic, together with a notion of energy and latency constraints, is reported in the PPRAalgorithm. To match requirements of different traffic types, we have also reviewed approaches using colored pheromones – here the colored pheromones form separate routing layers representing different route properties such as latency, jitter, or bandwidth. Two representatives of this class of algorithms are MACOand SANETshave been reviewed in this chapter.

Ant-inspired algorithms can be successfully applied for routing in Wireless Multi-Hop Networks, but due to the difficulty of the problem and different requirements priorities among Wireless Multi-Hop Networks, they have not converged into s single solution. Instead, we are facing an increasing number of algorithms and protocols following this idea. A short insight into this is given in the section on other ant-based algorithms for Wireless Multi-Hop Networks. Considering the constant change of sensor network hardware and software together with probably slightly different requirements, we are expecting this trend to continue and foresee new ant routing algorithms in the future.

Advertisement

Acknowledgments

The publication of this chapter was supported by the University of Klagenfurt.

DOWNLOAD FOR FREE

chapter PDF

© 2021 The Author(s). Licensee IntechOpen. This chapter is distributed under the terms of the Creative Commons Attribution 3.0 License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

How to cite and reference

Link to this chapter Copy to clipboard

Cite this chapter Copy to clipboard

Martina Umlauft and Wilfried Elmenreich (September 21st 2021). Ant Algorithms for Routing in Wireless Multi-Hop Networks [Online First], IntechOpen, DOI: 10.5772/intechopen.99682. Available from:

chapter statistics

26total chapter downloads

More statistics for editors and authors

Login to your personal dashboard for more detailed statistics on your publications.

Access personal reporting

We are IntechOpen, the world's leading publisher of Open Access books. Built by scientists, for scientists. Our readership spans scientists, professors, researchers, librarians, and students, as well as business professionals. We share our knowledge and peer-reveiwed research papers with libraries, scientific and engineering societies, and also work with corporate R&D departments and government entities.

More About Us