การกำหนดเส้นทางตามความสัมพันธ์เชิงสัมพันธ์

การกำหนดเส้นทางตามการเชื่อมโยง^{[ 1 ] [ 2 ] [ 3 ] [ 4 ]} (โดยทั่วไปเรียกว่าABR ) เป็นโปรโตคอลการกำหนดเส้นทาง เคลื่อนที่ ที่คิดค้นขึ้นสำหรับเครือข่ายไร้สายแบบ ad hocหรือที่รู้จักกันในชื่อเครือข่ายไร้สายแบบ ad hoc (MANET) และเครือข่ายไร้สายแบบ mesh ABR ถูกคิดค้นขึ้นในปี 1993 ยื่นขอสิทธิบัตรในสหรัฐอเมริกาในปี 1996 และได้รับสิทธิบัตรในปี 1999 ABR ถูกคิดค้นโดยChai Keong Tohในขณะที่กำลังศึกษาปริญญาเอกที่มหาวิทยาลัยเคมบริดจ์

ABR ประกอบด้วยสามขั้นตอน ขั้นตอนแรกคือขั้นตอนการค้นหาเส้นทาง เมื่อผู้ใช้เริ่มต้นส่งข้อมูล โปรโตคอลจะดักจับคำขอและส่งแพ็กเก็ตค้นหาผ่านอินเทอร์เฟซไร้สาย ขณะที่แพ็กเก็ตค้นหาแพร่กระจายจากโหนดหนึ่งไปยังอีกโหนดหนึ่ง ข้อมูลประจำตัวของโหนดและข้อมูลความเสถียรจะถูกเพิ่มเข้าไปในแพ็กเก็ต เมื่อแพ็กเก็ตไปถึงโหนดปลายทางในที่สุด มันจะได้รับข้อมูลทั้งหมดที่อธิบายเส้นทางจากต้นทางไปยังปลายทาง เมื่อเป็นเช่นนั้น ปลายทางจะเลือกเส้นทางที่ดีที่สุด (เนื่องจากอาจมีมากกว่าหนึ่งเส้นทางจากต้นทางไปยังปลายทาง) และส่ง REPLY กลับไปยังโหนดต้นทางผ่านเส้นทางที่เลือก

โปรดทราบว่าเมื่อแพ็กเก็ตส่งย้อนกลับจากปลายทางไปยังต้นทาง โหนดกลางแต่ละโหนดจะอัปเดตตารางการกำหนดเส้นทาง ของตน ซึ่งหมายความว่าโหนดเหล่านั้นจะทราบวิธีการกำหนดเส้นทางเมื่อได้รับข้อมูลจากโหนดต้นทาง เมื่อโหนดต้นทางได้รับข้อความตอบกลับ (REPLY) แสดงว่าเส้นทางถูกค้นพบและสร้างขึ้นสำเร็จแล้ว กระบวนการนี้เกิดขึ้นแบบเรียลไทม์และใช้เวลาเพียงไม่กี่มิลลิวินาที

ABR สร้างเส้นทางที่มีอายุการใช้งานยาวนานหรือมีเสถียรภาพในการเชื่อมโยง ดังนั้นเส้นทางส่วนใหญ่ที่สร้างขึ้นจึงแทบจะไม่ประสบปัญหาการเชื่อมต่อขาดหาย อย่างไรก็ตาม หากการเชื่อมต่อหนึ่งรายการหรือมากกว่านั้นขาดหาย ABR จะเรียกใช้ขั้นตอนการสร้างเส้นทางใหม่ (RRC) ทันที โดยพื้นฐานแล้ว RRC จะซ่อมแซมการเชื่อมต่อที่ขาดหายโดยให้โหนดต้นทาง (ซึ่งตรวจพบการเชื่อมต่อขาดหาย) ทำการซ่อมแซมเส้นทางเฉพาะที่ การซ่อมแซมเส้นทางเฉพาะที่นี้ทำได้โดยการส่งคำถามแบบกระจายเสียงเฉพาะที่เพื่อค้นหาเส้นทางย่อยที่มีอายุการใช้งานยาวนานทางเลือกอื่นไปยังปลายทาง

การบำรุงรักษาเส้นทาง ABR ประกอบด้วย:

• (ก) การค้นหาเส้นทางบางส่วน
• (ข) การลบเส้นทางที่ไม่ถูกต้อง
• (c) การอัปเดตเส้นทางที่ถูกต้อง และ
• (d) การค้นหาเส้นทางใหม่ (กรณีที่เลวร้ายที่สุด)

เมื่อเส้นทางที่ค้นพบไม่จำเป็นอีกต่อไป โหนดต้นทางจะเริ่มส่งแพ็กเก็ต RD (Route Delete) เพื่อให้โหนดกลางทั้งหมดในเส้นทางนั้นอัปเดตรายการในตารางการกำหนดเส้นทางและหยุดการส่งต่อแพ็กเก็ตข้อมูลที่เกี่ยวข้องกับเส้นทางที่ถูกลบนี้

นอกจากการใช้ RD เพื่อลบเส้นทางแล้ว ABR ยังสามารถใช้แนวทางสถานะแบบอ่อน (soft state) ได้อีกด้วย โดยที่รายการเส้นทางจะหมดอายุหรือถูกทำให้เป็นโมฆะหลังจากหมดเวลา เมื่อไม่มีกิจกรรมการรับส่งข้อมูลที่เกี่ยวข้องกับเส้นทางนั้นเป็นระยะเวลาหนึ่ง

ในปี พ.ศ. 2541 ABR ได้ถูกนำไปใช้งานสำเร็จ^{[ 5 ] [ 6 ] [ 7 ] [ 8 ]}ในเคอร์เนล Linux ในแล็ปท็อปยี่ห้อต่างๆ (IBM Thinkpad, COMPAQ , Toshiba เป็นต้น) ที่ติดตั้ง อะแดปเตอร์ไร้สาย WaveLAN 802.11a PCMCIA เครือข่ายไร้สายแบบ ad hocที่ใช้งานได้จริงขนาด 6 โหนดครอบคลุมระยะทางกว่า 600 เมตร ได้รับการเผยแพร่ และความสำเร็จนี้ได้ถูกตีพิมพ์ใน นิตยสาร Mobile Computingในปี พ.ศ. 2542 มีการทดสอบต่างๆ กับเครือข่ายนี้:

1. การส่งข้อมูลขนาดสูงสุด 500 เมกะไบต์จากต้นทางไปยังปลายทางผ่านเส้นทาง 3 ฮอป
2. การเชื่อมต่อขาดและการซ่อมแซมการเชื่อมต่ออัตโนมัติได้รับการพิสูจน์แล้วว่าใช้งานได้ผล
3. การค้นหาเส้นทางอัตโนมัติ
4. ลบเส้นทาง
5. เว็บเซิร์ฟเวอร์ในโหมด Ad Hoc – โดยที่ต้นทางคือไคลเอนต์และปลายทางคือเว็บเซิร์ฟเวอร์
6. การส่งข้อมูลมัลติมีเดีย (เสียง^{[ 9 ]}และวิดีโอ)
7. เทลเน็ตผ่านแอดฮ็อก
8. FTPผ่าน Ad Hoc
9. HTTPผ่าน Ad Hoc

นอกจากนี้ ยังได้ทำการวัดประสิทธิภาพเครือข่ายในด้านต่อไปนี้ด้วย:

1. ความล่าช้าตั้งแต่ต้นจนจบ
2. อัตราการส่งข้อมูล TCP
3. อัตราส่วนการสูญเสียแพ็กเก็ต
4. ความล่าช้าในการค้นหาเส้นทาง
5. ความล่าช้าในการซ่อมแซมเส้นทาง
6. ผลกระทบของขนาดแพ็กเก็ตต่อปริมาณงาน
7. ผลกระทบของช่วงเวลาการส่งสัญญาณต่อปริมาณงานและอายุการใช้งานแบตเตอรี่ที่เหลืออยู่

โปรโตคอลเวอร์ชันปรับปรุงได้รับการนำไปใช้ในภาคสนาม^{[ 10 ]}โดยผู้รับเหมาด้านการป้องกันประเทศTRW Inc.ในปี 2545 การปรับปรุงโปรโตคอลประกอบด้วย: (ก) การเพิ่ม QoS ระดับเครือข่าย และ (ข) ความสามารถในการจัดลำดับความสำคัญของเส้นทาง

ABR ได้รับสิทธิบัตรของสหรัฐอเมริกาหมายเลข 5987011 ^{[ 11 ]}และผู้รับโอนสิทธิ์คือKing's College, Cambridgeสหราชอาณาจักร

โปรโตคอลการกำหนดเส้นทางแบบ ad hoc สำหรับอุปกรณ์เคลื่อนที่อื่นๆ อีกหลายโปรโตคอลได้นำแนวคิดเรื่องความเสถียรของ ABR มาใช้ หรือได้ต่อยอดโปรโตคอล ABR ซึ่งรวมถึง:

• โปรโตคอลการกำหนดเส้นทางแบบปรับตัวตามความเสถียรของสัญญาณ ( SSA ) ^{[ 12 ]}
• โปรโตคอลการกำหนดเส้นทางตามความสัมพันธ์ที่ได้รับการปรับปรุง ( EABR )
• การปรับปรุงทางเลือกของการกำหนดเส้นทางตามการเชื่อมโยง ( AEABR ) ^{[ 13 ]}
• การกำหนดเส้นทางเกณฑ์การเชื่อมโยงที่ปรับให้เหมาะสม ( OABTR ) ^{[ 14 ]}
• โปรโตคอลการจัดกลุ่มตามความสัมพันธ์ ( ABCP ) ^{[ 15 ]}
• การกำหนดเส้นทางตามความสัมพันธ์เชิงความไว้วางใจโดยใช้หลักการฟัซซี ( Fuzzy-ABR )
• การกำหนดเส้นทางตามความสัมพันธ์โดยเฉลี่ยของค่า Tick ( ATA-AR ) ^{[ 16 ]}
• ABR ที่เชื่อถือได้ตาม Q-learning แบบปรับตัวได้เอง ( QTABR ) ^{[ 17 ]}
• การขยายคุณภาพการบริการสำหรับ ABR ( QoSE-ABR ) ^{[ 18 ]}
• การกำหนดเส้นทางมัลติแคสต์ตามการเชื่อมโยง ( ABAM ) ^{[ 19 ]}
• การกำหนดเส้นทางตามการเชื่อมโยงหลายเส้นทาง ( MABR ) ^{[ 20 ]}
• การกำหนดเส้นทางการเชื่อมโยงสำหรับเครือข่ายเซ็นเซอร์ไร้สาย^{[ 21 ]}
• เครือข่ายยานพาหนะแบบแอดฮ็อกแบบเชื่อมโยง (VANETs) ^{[ 22 ]}