Associativity-based routing: Difference between revisions

Revision as of 20:13, 18 June 2019

Latest revision as of 18:07, 26 May 2025

(25 intermediate revisions by 13 users not shown)

Line 1:

{{Multiple issues|

{{COI|date=September 2018}}

{{refimprovemore citations needed|date=September 2018}}

}}

'''Associativity-based routing'''<ref>{{cite journal |first=Chai-Keong |last=Toh |title=Associativity-based routing for ad hoc mobile networks |journal=Wireless Personal Communications |date=March 1997 |volume=4 |issue=2 |pages=103–139 |doi=10.1023/A:1008812928561 |s2cid=14335563 |url=https://scholar.google.com/citations?view_op=view_citation&hl=en&user=YTwSsH4AAAAJ&citation_for_view=YTwSsH4AAAAJ:d1gkVwhDpl0C|url-access=subscription }}</ref><ref>{{cite conference |title=A novel distributed routing protocol to support ad-hoc mobile computing |journal=Proc.Proceedings of the IEEE Fifteenth Annual International Phoenix Conference on Computers and Communications |first=Chai-Keong |last=Toh |date=March 1996 |url=https://scholar.google.com/citations?view_op=view_citation&hl=en&user=YTwSsH4AAAAJ&citation_for_view=YTwSsH4AAAAJ:2osOgNQ5qMEC}}</ref><ref name="auto">{{cite book |first=Chai-Keong |last=Toh |title=Ad Hoc Mobile Wireless Networks |publisher=[[Prentice Hall]] |date=December 2001 |isbn=978-0-13-007817-9}}</ref><ref>{{citation |title=Long-lived ad-hoc routing based on the concept of Associativity, IETF Draft 1999 |url=https://www.ietf.org/proceedings/46/I-D/draft-ietf-manet-longlived-adhoc-routing-00.txt}}</ref> (commonly known as '''ABR''') is a mobile routing protocol invented for [[wireless ad hoc network]]s, also known as [[mobile ad hoc network]]s (MANETs) and [[wireless mesh network]]s. ABR was invented in 1993, filed for a [[U.S. patent]] in 1996, and granted the patent in 1999. ABR was invented by [[Chai Keong Toh]] while doing his Ph.D. at Cambridge University.

==Route discovery phase==

ABR has three phases. The first phase is the route discovery phase. When a user initiates to transmit data, the protocol will intercept the request and broadcast a search packet over the wireless interfaces. As the search packet propagates node to node, node identity and stability information are appended to the packet. When the packet eventually reaches the destination node, it would have received all the information describing the path from source to destination. When that happens, the destination then chosechooses the best route (because there may be more than one path from the source to the destination) and sendsends a REPLY back to the source node, over the chosen path.

Note that when the packet transits backwards from destination to the source, each intermediate nodesnode will update their routing table, signifying that it will now know how to route when it receives data from the upstream node. When the source node receives the REPLY, the route is successfully discovered and established. This process is done in real-time and only takes a few milli-scondsseconds.

==Route reconstruction phase==

Line 23 ⟶ 25:

==Route deletion phase==

When a discovered route is no longer needed, a RD (Route Delete) packet will be initiated by the source node so that all intermediate nodes in the route will update their routing table entries and stoppedstop relay data packets associated with this deleted route.

In addition to using RD to delete a route, ABR can also implement a soft state approach where route entries are expired or invalidated after timed out, when there is no traffic activity related to the route over a period of time.

Line 29 ⟶ 31:

==Practicality==

In 1998, ABR was successfully implemented<ref>{{citation |title="Mobile Computing Magazine Interview Article - First practical ad hoc wireless network implementation outdoors, 1999 |url=http://init.unizar.es/images/MobiCompMag1999.pdf}}</ref><ref>{{citation |title=Implementation and evaluation of an adaptive routing protocol for infrastructureless mobile networks, Proceedings of 9th International Conference on Computer Communications and Networks, 2000. |pages=20–27|chapter-url=http://ieeexplore.ieee.org/document/885465/|doi=10.1109/ICCCN.2000.885465|chapter=Implementation and evaluation of an adaptive routing protocol for infrastructureless mobile networks|year=2000|last1=Toh|first1=C.-K.|last2=Lin|first2=G.|last3=Delwar|first3=M.|isbn=978-0-7803-6494-3|s2cid=26834795 }}</ref><ref>{{citation |title=Evaluating the communication performance of an ad hoc wireless network, IEEE Transactions on Wireless Communications, 2000 |url=https://scholar.google.com/citations?view_op=view_citation&hl=en&user=YTwSsH4AAAAJ&citation_for_view=YTwSsH4AAAAJ:WF5omc3nYNoC}}</ref><ref>{{citation |title=Experimenting with an Ad Hoc wireless network, ACM SIGMETRICS Performance Evaluation Review, Volume 28 Issue 3, Dec. 2000 |journal=ACM SigmetricsSIGMETRICS Performance Evaluation Review|volume=28|issue=3|pages=21–29|url=http://dl.acm.org/citation.cfm?id=377622|doi=10.1145/377616.377622|year=2000|last1=Toh|first1=C.-K.|last2=Chen|first2=Richard|last3=Delwar|first3=Minar|last4=Allen|first4=Donald|s2cid=1486812 }}</ref> into the Linux kernel, in various different branded laptops (IBM Thinkpad, COMPAQ, Toshiba, etc.) that are equipped with [[WaveLAN]] 802.11a PCMCIA wireless adapters. A working 6-node wide [[wireless ad hoc network]] spanning a distance of over 600 meters was achieved and the successful event was published in Mobile Computing Magazine in 1999. Various tests were performed with the network:

# Transmission of up to 500MBytes of data from source to destination over a 3-hop route.

# Link breaks and automatic link repairs proven to be working

# Automatic Route Discovery

Line 51 ⟶ 53:

# Impact of beaconing interval on throughput and remaining battery life

An enhanced version of the protocol has beenwas implemented in the field<ref>{{cite journal |title=Next-Generation Tactical Ad Hoc Mobile Wireless Networks |journal=TRW Technology Review Journal |date=2004 |url=https://drive.google.com/file/d/1LJotUZzeYZxHUg1F8YMm2zS5OdNKgguQ/view}}</ref> by defense contractor [[TRW Inc.]] in 2002. The enhancement made to the protocol include: (a) network-layer QoS additions and (b) route precedence capabilities.

==Patent and work extensions==

ABR was granted a US patent 5987011<ref>{{citation |title=A Routing Method for Ad Hoc Mobile Networks, US Patent 5987011, granted 1996, filed 1994. |url=https://wwwpatents.google.com/patentspatent/US5987011}}</ref> and the assignee being [[King's College, Cambridge]], UK.

A few other mobile ad hoc routing protocols have incorporated ABR's stability concept or have done extensions of the ABR protocol, including:

* Signal Stability-based Adaptive Routing Protocol ('''SSA''')<ref>{{citecitation |title="Signal stability based adaptive routing (SSA) for ad-hoc mobile networks"|url=http://dl.acm.org/citation.cfm?id=241244|year = 1996|last1 = Dube|first1 = Rohit|last2 = Rais|first2 = Cynthia D.|last3 = Wang|first3 = Kuang-Yeh|last4 = Tripathi|first4 = Satish K.}}</ref>

* Enhanced Associativity Based Routing Protocol ('''EABR'''){{citation needed|date=March 2020}}

* EnhancedAlternative AssociativityEnhancement of Associativity-Based Routing Protocol ('''EABRAEABR''')<ref>{{citecitation |title="EnhancedAlternative Enhancement of Associativity -Based Routing Protocol"|urldoi=http://thescipub10.com1007/PDF/jcssp.2006.853.858.pdf}}</ref> 978-3-642-11817-3_7

|year=2009

|s2cid=8920485

* Alternative Enhancement of Associativity-Based Routing ('''AEABR''')<ref>{{cite |title="Alternative Enhancement of Associativity-Based Routing"|url=https://link.springer.com/chapter/10.1007%2F978-3-642-11817-3_7#page-1

}}</ref>

* MultipathOptimized Associativity BasedThreshold Routing ('''MABROABTR''')<ref>{{citecitation |title="MultipathOptimized Associativity BasedThreshold Routing"|urlciteseerx=http://dl10.acm1.org/citation1.cfm?id=104403479.8653}}</ref>

* Optimized Associativity-Based ThresholdClustering RoutingProtocol ('''OABTRABCP'''),<ref>{{citecitation |title="Optimized Associativity-Based Clustering ThresholdProtocol for Mobile Ad Hoc Networks Routing"|url=httphttps://citeseerxjan.istnewmarch.psu.eduname/viewdocconferences/ccnc05/DATA/download?doi=10.1-N03-04.1.79.8653&rep=rep1&type=pdfPDF}}</ref>

* Cluster-Based Enhanced Associativity-Based Routing ('''CBE-ABR'''),<REF>{{cite |title="CBE-ABR: A Cluster Based Enhanced Routing Protocol for Ad Hoc Mobile Networks" |url=http://airccse.org/journal/cnc/1009s5.pdf}}</ref>

* Associativity-Based Clustering Protocol ('''ABCP'''), <ref>{{cite |title="Associativity-Based Clustering Protocol for Mobile Ad Hoc Networks" |url=https://jan.newmarch.name/conferences/ccnc05/DATA/1-N03-04.PDF}}</ref>

* Fuzzy Based Trust Associativity-Based Routing ('''Fuzzy-ABR''')

* Cluster-BasedAssociativity Tick EnhancedAveraged Associativity-Based Routing ('''CBEATA-ABRAR'''),<REFref>{{citecitation |title="CBE-ABR:Associativity ATick ClusterAveraged Associativity-Based Enhanced Routing Protocol for Ad HocRealtime Mobile Networks" |url=http://airccsewww.emo.org.tr/journal/cncekler/1009s58a07694d909694a_ek.pdf}}</ref>

* Self-adaptive Q-learning based trust ABR ('''QTABR''')<ref>{{citation |title=Self-Adaptive Trust Based ABR Protocol for MANETs Using Q-Learning |journal= The Scientific World Journal|volume=2014 |pages=452362 |pmc=4164804 |year=2014 |last1=Vijaya Kumar |first1=A. |last2=Jeyapal |first2=A. |pmid=25254243 |doi=10.1155/2014/452362 |doi-access= free}}</ref>

* Associativity Tick Averaged Associativity-Based Routing ('''ATA-AR'''), <ref>{{cite |title="Associativity Tick Averaged Associativity-Based Routing for Realtime Mobile Networks" |url=http://www.emo.org.tr/ekler/8a07694d909694a_ek.pdf}}</ref>

* Quality of Service Extensions to ABR ('''QoSE-ABR''')<ref>{{citation |pages = 631–637|url=http://dl.acm.org/citation.cfm?id=1487990|doi = 10.1109/APSCC.2008.234|isbn = 9780769534732|year = 2008|series = Apscc '08| s2cid=7026878 | chapter=Adding Quality of Service Extensions to the Associativity Based Routing Protocol for Mobile Ad Hoc Networks (MANET) | title=2008 IEEE Asia-Pacific Services Computing Conference | last1=Murad | first1=Ayman Mansour | last2=Al-Mahadeen | first2=Bassam | last3=Murad | first3=Nuha Mansour | url-access=subscription }}</ref>

* SelfAssociativity-adaptive Q-learning based trustMulticast ABRRouting ('''QTABRABAM''')<ref>{{citecitation |title="SelfABAM: On-Adaptive TrustDemand Associativity-Based ABR Protocol for MANETs Using Q-Learning"Multicast |url=https://www.ncbiresearchgate.nlm.nih.gov/pmc/articlesnet/PMC4164804publication/3874369}}</ref>

* Multipath Associativity Based Routing ('''MABR''')<ref>{{citation |chapter=Multipath Associativity Based Routing|chapter-url=http://dl.acm.org/citation.cfm?id=1044034|doi = 10.1109/WONS.2005.24|title = Second Annual Conference on Wireless On-demand Network Systems and Services|pages = 60–69|year = 2005|last1 = Carthy|first1 = P.M.|last2 = Grigoras|first2 = D.|isbn = 0769522904 <!--0-7695-2290-0 is listed on some pages, but it is invalid-->| s2cid=12523282 }}</ref>

* Associativity routing for Wireless Sensor Networks <ref>{{citecitation |title="Associative routing for wireless sensor networks" |urljournal=http:/Computer Communications|volume=34|issue=18|pages=2162–2173|doi=10.1016/wwwj.sciencedirectcomcom.com/science/article/pii/S01403664110003262011.01.010|year=2011|last1=Eltarras|first1=Ramy|last2=Eltoweissy|first2=Mohamed}}</ref>

* Quality of Service Extensions to ABR ('''QoSE-ABR''')<ref>{{cite |title="Adding Quality of Service Extensions to the Associativity Based Routing Protocol for Mobile Ad Hoc Networks"|url=http://dl.acm.org/citation.cfm?id=1487990}}</ref>

* Associative Vehicular Ad Hoc Networks (VANETs) <ref>{{citation |title=A Stable Routing Protocol for Vehicles in Urban Environments |journal=International Journal of Distributed Sensor Networks|volume=9|issue=11|pages=759261|doi=10.1155/2013/759261|year=2013|last1=Yu|first1=Hyun|last2=Ahn|first2=Sanghyun|last3=Yoo|first3=Joon|doi-access=free}}</ref>

* Associativity-based Multicast Routing ('''ABAM''')<ref>{{cite |title="ABAM: On-Demand Associativity-Based Multicast" |url=https://www.researchgate.net/publication/3874369_ABAM_On-Demand_Associativity-Based_Multicast_Routing_for_Ad_Hoc_Mobile_Networks}}</ref>

* Multipath Associativity Based Routing ('''MABR''')<ref>{{cite |title="Multipath Associativity Based Routing"|url=http://dl.acm.org/citation.cfm?id=1044034}}</ref>

* Associativity routing for Wireless Sensor Networks <ref>{{cite |title="Associative routing for wireless sensor networks" |url=http://www.sciencedirect.com/science/article/pii/S0140366411000326}}</ref>

* Associative Vehicular Ad Hoc Networks (VANETs) <ref>{{cite |title="A Stable Routing Protocol for Vehicles in Urban Environments" |url=http://dsn.sagepub.com/content/9/11/759261.full}}</ref>

==References==

Line 93 ⟶ 83:

[[Category:Mobile computers]]

[[Category:Wireless sensor network]]

[[Category:Wireless networking]]

[[Category:Ad hoc routing protocols]]

[[Category:Routing protocols]]