Nghiên ứu giao thức định tuyến nguồn động dsr trong mạng ad hoc

CÁC CễNG CỤ Mễ PHỎNG MẠNG ADHOC 54 6.1 Lựa chọn cụng cụ mụ phỏng mạng Adhoc 54 Trang 5 CÁC Kí HIỆU, CHỮ VIẾT TẮT ABR Associativity-Based Routing ACK ACKnowledgment AMRoute Ad hoc Mu

Bộ giáo dục và đào tạo Trờng Đại học bách khoa Hà nội

-

Luận Văn Thạc sỹ khoa học

tuyến nguồn động dsr trong

MỤC LỤC

DANH MỤC CÁC KÝ HIỆU, CHỮ VIẾT TẮT

DANH MỤC CÁC BẢNG

DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ

LỜI NÓI ĐẦU

CHƯƠNG 2 GIAO THỨC ĐỊNH TUYẾN MẠNG AD HOC 13

CHƯƠNG 3 GIAO THỨC ĐỊNH TUYẾN NGUỒN ĐỘN G DSR 20

20 3.1 Tổng quan về DSR

3.2 Một số giả định

23 3.3 Định tuyến nguồn

24 3.4 Khám phá tuyến

4.1.3 Ngăn chặn cơn bão Trả lời tuyến

4.1.5 Hỗ trợ các liên kết đối xứng

36 4.2 Tối ưu trong Duy trì tuyến

4.2.3 Tăng quá trình truyền lan các bản tin lỗi tuyến 37

4.3.2 Chức năng xen rẽ nhánh 38

4.6 So sánh DSR với một số giao thức khác 43

GIAO THỨC ĐỊNH TUYẾN AD HOC

CHƯƠNG 6 CÁC CÔNG CỤ MÔ PHỎNG MẠNG ADHO C 54

6.1.2 So sánh công cụ mô phỏng

60 6.2 Ứng dụng công cụ mô phỏng cho mạng Ad hoc

7.3 Tạo SSID và đặt cấu hình cho Card 70

AODV Ad-hoc On Demand Distance Vector

CGSR Clusterhead Gateway Switch Routing

CSMA Carrier Sense Multiple Access

DSDV Destination Sequenced Distance Vector

DVMRP Distance Vector Multicast Routing Protocol

FIFO First In First Out

FSPL Free Space Propagation Loss

IARP Intrazone Routing Protocol

ICMP Internet Control Message Protocol

IERP Interzone Routing Protocol

IMEP Internet MANET Encapsulation Protocol

IMPORTANT Impact of Mobility on Performance of RouTing protocols

MANET Mobile Ad-hoc NETworks

MAODV Multicast Ad hoc On-Demand Vector routing protocol

SSID Service set Identification

TORA Temporally Ordered Routing Algorithm

D ANH MỤC CÁC BẢNG

Bảng 2.1 So sánh các Giao thức định tuyến (Theo yêu cầu với Theo bảng) 17

Bảng 4.1 So sánh DSR với một số giao thức định tuyến điển hình 43

các cơ chế định tuyến khác nhau

các Yêu cầu tuyến về một phía

Hình 3.5 Duy trì tuyến, nút C không thể chuyển tiếp từ A đến E 29 qua liên kết tới bước nhẩy tiếp theo D của nó

Nút C đang chuyển tiếp gói tới E và nghe lỏm các gói từ X

trả lời cùng một Yêu cầu tuyến từ các Bộ nhớ đệm tuyến của chúng

khi nó nghe lỏm một gói từ A dự định đến B trước tiên

các thiết bị vô tuyến phạm vi ngắn và các nút A, B, C có các

thiết bị truyền thông phạm vi dài

các giao diện mạng không đồng nhất

Chí nh sách ngăn chặn là 6/11 hoặc 54%

LỜI NÓI ĐẦU

Ad Hoc là một phần trong công nghệ thông tin hiện nay, trong đó người sử dụng

có thể trao đổi thông tin trực tiếp với nhau hình thành một mạng tạm thời và không cần đến cơ sở hạ tần mạng sẵn có Mỗi nút trong mạng Ad Hoc vừa có chức năng của máy trạm vừa là một bộ định tuyến, các nút này luôn sẵn sàng chuyển tiếp gói tin trong mạng Chính vì vậy định tuyến trong mạng Adhoc là vấn đề quan trọng và rất được quan tâm Mạng Ad Hoc có khá nhiều điểm khác biệt so với mạng di động

tế bào truyền thống do vậy giao thức định tuyến trong mạng này phải đáp ứng thêm nhiều yêu cầu kỹ thuật mới Điều quan trọng nhất là giao thức định tuyến này phải

có khả năng thích nghi với cấu trúc mạng luôn thay đổi Tiếp theo chúng ta cũng phải kể đến những giới hạn như năng lực của thiết bị, khả năng lưu trữ, CPU, băng thông,…Giao thức định tuyến phải làm giảm lưu lượng điều khiển, đơn giản hoá việc tính toán đường định tuyến Có thể nói giao thức định tuyến đóng vai trò xương sống trong trong hoạt động của mạng Ad Hoc

Luận văn trình bày tổng quan về mạng Ad Hoc, các giao thức định tuyến trong mạng Ad Hoc, đặc biệt luận văn đi sâu nghiên cứu các vấn đề liên quan đến giao thức định tuyến nguồn động DSR, môt số công cụ mô phỏng mạng Ad Hoc và thiết lập một ứng dụng cụ thể của mạng Ad Hoc

Do thời gian có hạn nên luận văn chắc chắn không thể đề cập hết được mọi khía cạnh liên quan đến mạng Ad Hoc Để luận văn ngày một hoàn thiện rất mong nhận được nhiều ý kiến đóng góp quý báu từ các Thày, các Cô và các bạn

Cuối cùng, em xin chân thành cảm ơn thầy giáo TS Lê Đăng Hưng đã tận tình hướng dẫn em hoàn thành luận văn này Qua đây tôi cũng xin được gửi lời cám ơn tới gia đình và bạn bè đã động viên giúp sức cho tôi trong suốt thời gian học và hoàn thành luận văn này

Hà Nội, ngày tháng 11 năm 2005

NguyÔn Huy Th¸i

CHƯƠNG 1

1 1 GIỚI THIỆU CHUNG

Kể từ những năm 1970, trao đổi thông tin vô tuyến giữa những người sử dụng đầu cuối di động đã trở nên phổ biến hơn bao giờ hết Công nghệ truyền thông này ngày càng thu hút được nhiều người sử dụng Số lượng các thiết bị kết nối với nhau gia tăng rất nhanh; việc truy nhập các dịch vụ trực tuyến trở nên quen thuộc phổ cập hơn với các dịch vụ như email, từ điển trực tuyến, thông tin du lịch, thể thao, thông tin thị trường chứng khoán v.v Lý do chính là nhờ sự tiến bộ vượt bậc về công nghệ điện tử gần đây trong các thiết bị như máy tính xách tay, các thiết bị thông tin

dữ liệu vô tuyến, các modem không dây, các mạng Wireless LAN Giá thành của các thiết bị này tương đối hợp lý nhưng cho khả năng kết nối và truyền dữ liệu với tốc độ rất cao

Hiện nay, có hai xu hướng chính trong việc trao đổi thông tin vô tuyến giữa hai nút mạng với nhau:

• Xu hướng I: Sử dụng mạng tế bào truyền thống đang tồn tại để truyền

vô tuyến hiện nay đều phụ thuộc vào các trạm gốc BS Những trạm này kết nối với cơ sở hạ tầng mạng viễn thông sẵn có và chuyển giao lưu lượng đến các trạm khác Do vậy việc mở rộng các dịch vụ vùng phủ sóng

của mạng vô tuyến trong xu hướng này con nhiều hạn chế và phụ thuộc vào cơ sở hạ tầng mạng có sẵn

Vấn đề nảy sinh là nhu cầu liên quan tới các dịch vụ vô tuyến rất nhiều nhưng đôi khi cơ sở hạ tầng mạng tại đó lại chưa sẵn sàng hoặc để xây dựng cơ sở hạ tầng mạng sẽ tốn nhiều chi phí nhưng không mang lại nhiều lợi nhuận cho nhà cung cấp dịch vụ Cấu trúc mạng điều khiển tập trung này vẫn còn khá phổ biến với các mạng

tế bào diện rộng đang tồn tại hiện nay ví dụ như mạng GSM, CDMA, UTMS, PHS

• Xu hướng II: Khi không có sẵn cơ sở hạ tầng mạng nhưng chúng ta lại cần hình thành một mạng kiểu Ad Hoc cho những người có nhu cầu trao đổi thông tin với nhau Khi đó các máy trong mạng Ad Hoc phải sẵn sàng nhận và chuyển tiếp các gói tin và đảm bảo rằng các gói tin

đó đến được đích của chúng Tuy nhiên, mô hình mạng này bị giới hạn bởi bán kính phục vụ (vùng phủ sóng vô tuyến) của mỗi nút mạng Bán kính phục vụ này nhỏ hơn nhiều so với khoảng truyền dẫn của các BS trong mạng tế bào Hiện nay có nhiều giải pháp cho phép người sử dụng thiết bị di động kết nối với nhau thông qua mạng Internet, thông qua DHCP và Mobile IP (MIP) Tuy nhiên nó phụ thuộc vào khả năng của các máy chủ có cho phép các máy tính kết nối hay không? Ngoài

ra, sử dụng MIP thông tin của hai người sử dụng có vị trí địa lý cạnh nhau sẽ phải định tuyến qua đường ngầm (tunelling) thông qua mạng Internet

Hình 1.1 Mạng điện thoại vô tuyến

Nói chung, khó có thể khẳng định rằng xu hướng I tốt hơn xu hướng II hay ngược lại do nó phụ thuộc nhiều vào điều kiện cụ thể Trong nhiều trường hợp mạng Ad Hoc có nhiều ưu thế hơn mạng tế bào, cụ thể là:

Mạng Ad Hoc không phụ thuộc vào cơ sở hạ tầng mạng có sẵn và do đó có thể được triển khai ở bất kỳ nơi nào (kể cả nơi những nơi chưa có cơ sở hạ tầng mạng) Mạng Ad Hoc rất hữu ích trong các tình huống khẩn cấp như thiên tai, tìm kiếm cứu nạn tại và tại những nơi yêu cầu triển khai nhanh như trong chiến đấu Mạng Ad Hoc cũng rất hữu ích để thiết lập mạng WLAN nhanh phục vụ hội họp tại đó những người tham gia có thể thiết trao đổi thông tin với nhau mà không cần đến hạ tầng mạng có sẵn

Do các nút trong mạng Ad Hoc mạng phải thực hiện việc chuyển tiếp các gói tin cho nhau nên cần có một số các giao thức đặc biệt trong định tuyến Hiện nay quy chuẩn cho các giao thức định tuyến trong mạng Ad Hoc còn hạn chế và chưa thực

sự đáp ứng được mọi vấn đề về kỹ thuật phát sinh Do vậy trong tương lai còn khá nhiều vấn đề kỹ thuật cần phải nghiên cứu, giải quyết và hoàn thiện chúng

1.2 MẠNG AD HOC VÔ TUYẾN

1.2.1 Khái niệm

Mạng Ad Hoc vô tuyến là mạng ngang hàng (peer-to-peer), đa chặng (multi-hop) không quản lý tập trung Nó bao gồm nhiều nút (node) di động và chia sẻ cùng một kênh vô tuyến Các nút trong phạm vi phủ sóng của nhau đóng vai trò như một bộ định tuyến sẵn sàng nhận và chuyển tiếp các gói tin với nhau Trong mạng Ad Hoc không có sự tồn tại trước cơ sở hạ tầng mạng cố định Mạng Ad Hoc có thể được tạo ra và sử dụng "vào bất kỳ thời gian nào, ở bất kỳ đâu" Ngoài ra, mạng Ad Hoc hoạt động ổn định hơn mạng tập trung thông thường rất nhiều bởi tính phân tán của chúng

Mạng Ad Hoc vô tuyến có thể hình dung là tập hợp các nút di động, bán di động hoặc toàn bộ các nút có khả năng di chuyển Bán kính vùng phủ sóng của mỗi nút thường bị giới hạn nên các nút trao đổi thông tin với nhau bằng phương pháp truyền gói tin qua nhiều chặng Do đó kết nối trong mạng Ad Hoc thường là kết nối đa chặng (multi hops) Các nút đóng vai trò như một bộ định tuyến trong mạng để đảm -bảo các gói dữ liệu được chuyển chính xác tới đích của chúng Mỗi nút có một giao diện vô tuyến và giao tiếp với nút mạng khác thông qua sóng vô tuyến hoặc qua giao diện hồng ngoại Máy tính xách tay hoặc PDA là ví dụ về các nút trong mạng

Ad Hoc Nút trong mạng Ad Hoc có thể chuyển động nhưng cũng có thể đứng yên

Ví dụ như điểm truy nhập Internet - AP

Hình 1.2 Mạng Ad Hoc di động MANET trong kiến trúc mạng vô tuyến 4G- Hình 1.3 minh hoạ một mạng Ad Hoc đơn giản gồm 3 nút mạng S và là hai nút Dmạng không nằm trong phạm vi truyền dẫn của nhau, chúng giao tiếp với nhau

thông qua nút R, nút mạng trung gian (relay), để chuyển tiếp gói tin giữa các nút mạng nằm ngoài khoảng cách truyền dẫn, như vậy nó có vai trò như bộ định tuyến (router) Ba nút như vậy hình thành một mạng Ad Hoc.

Các mạng di động Ad Hoc nói chung đã giảm được chi phí quản lý so với các mạng có dây Những mạng này có khả năng tự cấu hình và có khả năng duy trì các kết nối mạng, thông tin định tuyến

Nót m¹ng S

Nót m¹ng D kho

¶ng truyÒn dÉn

kho

¶n

g tr uyÒ

n d Én Nót m¹ng R

Hình 1.3 Mô hình mạng Ad Hoc gồm 3 nút mạng

Đim truy nhp Cerfiticate server

www server

Public server

Hình 1.4 Mạng Ad Hoc vô tuyến

Trong mạng Ad Hoc không tồn tại khái niệm quản lý tập trung Điều này đảm bảo mạng sẽ không gặp sự cố trong trường hợp nút mạng di chuyển ra ngoài vùng phủ sóng của các nút mạng khác Nút mạng có thể ra/vào mạng bất kỳ lúc nào Một nút di động có thể thực hiện đồng thời 2 vai trò trong khi trao đổi thông tin: máy chủ và bộ định tuyến (Host/Router) Trong vai trò một máy chủ, một nút có thể là

nguồn hoặc đích với các dạng lưu lượng khác nhau Với vai trò bộ định tuyến, nó chịu trách nhiệm chuyển tiếp các gói tới đích mong muốn và duy trì các đường định tuyến

Nút mạng có thể bao gồm một router và nhiều máy trạm di động liên kết với nhau như Hình 1.5

Hình 1.5 Sơ đồ khối nút mạng bao gồm router và các host di động

Mạng Ad Hoc còn có khả năng tự thay đổi cấu hình và tự khắc phục sự cố của nút thông qua các thủ tục cấu hình lại mạng Ví dụ: nếu một nút rời khỏi mạng sẽ gây ra sự cố liên kết Khi đó các nút mạng còn lại có thể yêu cầu một định tuyến mới và như vậy vấn đề đã được giải quyết Điều này có thể gây ra khoảng thời gian trễ đáng kể trong mạng Tuy nhiên người sử dụng mạng Ad Hoc không phát hiện ra thời gian trễ này

Hình 1.6 So sánh 2 kiểu mạng di động (MANET và Mobile IP)

Ad Hoc vô tuyến chứa nhiều ưu điểm của mạng vô tuyến thông thường Liên kết giữa các nút mạng được hình thành nhanh khi chúng nằm trong vùng phủ sóng của nhau

Host Host Host

Router

1.2.2 Đặc điểm của mạng Ad Hoc

Trong mạng tế bào hoặc mạng IP di động: các nút di động trao đổi thông tin với nhau thông thông qua các trạm gốc BS cố định Các BS này tạo nên một mạng đa chặng cố định So với cấu trúc mạng nói trên mạng Ad Hoc có một số đặc tính nổi bật khác như sau:

1 Cấu trúc tôpô động: Các nút tự do dịch chuyển do đó tôpô mạng được đặc

trưng bởi tính đa chặng, thay đổi ngẫu nhiên tại các thời điểm không dự báo trước

2 Dải thông hạn hẹp, các liên kết có dung lượng thay đổi: Các đường liên kết vô

tuyến có dung lượng thấp hơn đáng kể so với các đường liên kết có dây Đặc biệt khi sử dụng các ứng dụng đa phương tiện băng thông sử dụng có thể vượt quá dung lượng mạng Bên cạnh đó độ lưu thoát các kênh liên lạc vô tuyến thường nhỏ hơn tốc độ truyền dẫn vô tuyến cực đại do tác động của đa truy nhập, pha đinh, tạp âm

và các trạng thái nhiễu

3 Khả năng của các thiết bị di động trong mạng Ad Hoc bị hạn chế: Các nút

mạng bị giới hạn về khả năng như CPU, bộ nhớ, dung lượng nguồn ắc quy Một số nút trong mạng Ad Hoc hoạt động dựa vào các nguồn ăcquy Đối với những nút này, các tiêu chuẩn thiết kế hệ thống mạng quan trọng nhất là khả năng tiết kiệm năng lượng Sử dụng phương pháp định tuyến nhiều chặng đã khắc phục được rất tốt vấn đề này

4 Tính an toàn vật lý bị giới hạn: Các mạng vô tuyến di động thường bị tấn công

ở mức vật lý nhiều hơn so với các mạng cố định Sự gia tăng khả năng nghe lén, các cuộc tấn công để từ chối dịch vụ cần được xem xét kỹ lưỡng Chính tính phi tập trung trong điều khiển của mạng Ad Hoc đã cung cấp khả năng chống lại vấn đề này

1.2.3 Các ứng dụng

Lý do cơ bản để sử dụng các mạng Ad Hoc không phải tính khả thi của nó vào bất kỳ lúc nào và bất kỳ đâu, bởi bất kỳ ai (như trong trường hợp các hệ thống tế bào 2G và 3G) Sức mạnh chủ yếu trên thực tế là khả năng kết nối liên tục (seamless connectivity) giữa các thiết bị trong vùng lân cận Một số ứng dụng có thể được tạo ra sử dụng mạng Ad Hoc:

đó trên máy in nội bộ, e mail bản thuyết trình tới các đồng nghiệp vắng mặt Sử dụng mạng Ad Hoc trong ứng dụng này đã giảm bớt được nhiều chi phí phát sinh như chi phí mua (Hub, Switch, dây cáp, đầu RJ45 )

-Hoạt động cứu hộ

Do mạng Ad Hoc có thể triển khai nhanh nên có thể sử dụng chúng trong các công tác như tìm kiếm cứu hộ tại vùng có thảm hoạ, động đất, hoả hoạn, hay lụt lội Trong những trường hợp như vậy hạ tầng mạng hiện có đã bị hư hại và không sử dụng được do vậy ứng dụng mạng Ad Hoc tại đây trở nên rất hữu hiệu

là giải pháp đơn giản và hữu hiệu nhất

Trong tương lai, mọi người có thể hình dung: nhiều thiết bị tại nhà kết nối mạng

và mọi người điều khiển được chúng từ xa Các thiết bị đó có thể là máy giặt đặt ở

vị trí cố định, máy radio, máy tính xách tay có thể di chuyển Trong trường hợp này, dùng dây dẫn kết nối chúng lại với nhau là không phù hợp do các thiết bị này di chuyển khắp nơi Sử dụng mạng Ad Hoc trong trường hợp này thể hiện thực sự hiệu quả Nó đã khắc phục được mọi vấn đề về tính di động và tính thay đổi trong cấu trúc mạng

Các mạng vùng cá nhân PAN

Mạng vùng cá nhân PAN là mạng của các thiết bị liên quan chặt chẽ đối với mỗi

cá nhân Những thiết bị này có thể được gắn vào quần áo của mỗi người hoặc là được đặt trong túi Trong tương lai, các thiết bị này có thể bao gồm cả các thiết bị thực tế ảo, các thiết bị cảm biến (sense of touch) Khi sự tác động lẫn nhau giữa các mạng PAN là cần thiết thì đặc tính di động trở nên vô cùng quan trọng Để thiết lập thông tin giữa các mạng PAN chuyển động, công nghệ mạng Ad Hoc có thể được

áp dụng

Mạng các Bộ cảm biến

Một số bộ cảm biến nhỏ xếp thành mạng Ad Hoc để cung cấp các thông tin chi tiết về địa lý hay các điều kiện môi trường nguy hiểm Thông qua công nghệ mạng

Ad Hoc, mọi hoạt động và thông tin từ các bộ cảm biến này có thể được thu thập từ

xa thay vì ta phải gửi các nhân viên làm việc tại các môi trường nguy hiểm trên Các

bộ cảm biến là các máy thu phát vô tuyến được phân bố và làm việc thay thế các nhân viên nói trên Ứng dụng này được rất nhiều người quan tâm đặc biệt là ứng dụng trong công nghiệp và quân sự

Các trò chơi

Mạng Ad Hoc không chỉ được sử dụng trong các ứng dụng chuyên nghiệp mà chúng còn được sử dụng trong giải trí gia đình tại đó mọi người không cần biết họ đang chơi với ai Họ có thể chơi một trò chơi chống lại một người ngẫu nhiên trong vùng lân cận Ví dụ có thể hình dung tại bến xe lửa, trên ô tô buýt, trên sân bay, thậm chí ngay cả trên máy bay nơi mọi người tốn nhiều thời gian để chờ đợi Sử dụng công nghệ mạng Ad Hoc trong giải trí đã tạo khả năng vô tận đối với các trò chơi Chi phí cho việc nay là rất ít do không phải sử dụng hạ tầng mạng của bất kỳ nhà cung cấp nào

Quân sự

Không nghi ngờ gì các mạng Ad Hoc còn có thể sử dụng hữu hiệu cho các mục đích quân sự Thực tế Bộ Quốc phòng Mỹ đã tài trợ rất nhiều cho các nghiên cứu về

công nghệ chuyển mạch gói hoạt động không bị hạn chế bởi cơ sở hạ tầng cố định Năm 1972, DARPA đã bắt đầu nghiên cứu và giới thiệu Mạng vô tuyến gói PRN

Do đáp ứng được tính di động và khả năng triển nhanh nên mạng Ad Hoc rất hữu ích trong ngành quân sự

1.3 ĐỊNH TUYẾN TRONG MẠNG AD HOC

Gói tin muốn đến được đích phải chuyển tiếp nút mạng do đó để gói tin đến được đúng đích thì phải sử dụng một phương pháp định tuyến tại các nút mạng đó Giao thức định tuyến này có hai chức năng: tìm/chọn tuyến cho các cặp nguồn đích - khác nhau; và chuyển gói tin đến đúng đích Chức năng thứ hai rất đơn giản có thể

sử dụng nhiều giao thức và cấu trúc dữ liệu (các bảng định tuyến) có sẵn Trong phạm vi giới hạn, luận văn chỉ đề cập đến chức năng thứ nhất của giao thức định tuyến: đó là tìm/chọn tuyến

Giao thức định tuyến là cần thiết, vậy sao không sử dụng các giao thức định tuyến thông thường? Các giao thức thông thường như trạng thái liên kết và vectơ khoảng cách đã được kiểm nghiệm và rất quen thuộc trong truyền thông máy tính Tuy nhiên những giao thức thông thường chỉ thích hợp với mạng có cấu trúc tĩnh

Nó vấp phải những vấn đề gì khi áp dụng cho mạng Ad Hoc có cấu trúc luôn thay đổi?

Các giao thức định tuyến thông thường

Vấn đề chính đối với các giao thức định tuyến thông thường là chúng được thiết

kế cho một tôpô tĩnh Vấn đề lớn mà các giao thức định tuyến thông thường phải đối mặt là sự thay đổi tôpô mạng thường xuyên Trạng thái liên kết và vectơ khoảng cách chỉ hoạt động hiệu quả trong mạng Ad Hoc trong đó các nút mạng ít di động Một vấn đề khác với giao thức định tuyến thông thường là: hoạt động phụ thuộc nhiều vào các bản tin điều khiển định tuyến định kỳ Chúng yêu cầu cập nhật thường xuyên bảng định tuyến của các nút mạng và do đó làm tiêu tốn tài nguyên mạng như băng thông, công suất nguồn, khả năng xử lý của CPU Trạng thái liên kết và vectơ khoảng cách luôn cố gắng duy trì các tuyến tới mọi đích mà không quan tâm nút mạng đó có tham gia truyền thông trong mạng hay không do vậy nó làm tiêu tốn đáng kể tài nguyên mạng

Đặc tính khác của các giao thức định tuyến thông thường là chúng công nhận các liên kết phải là 2 chiều Thực tế trong môi trường vô tuyến, điều này không phải lúc nào cũng như vậy Hiện nay, các giao thức định tuyến được đề xuất cho mạng Ad Hoc đều dựa trên giao thức định tuyến cổ điển Do đó việc tìm hiểu nguyên lý hoạt động của các giao thức định tuyến truyền thống như vectơ khoảng cách, trạng thái liên kết, định tuyến nguồn là hết sức cần thiết Sau đây xin trình bày sơ lược một số giao thức định tuyến thông thường:

Trạng thái liên kết

Phương pháp định tuyến này dựa trên giá trị của mỗi liên kết (cost) và nút mạng phải duy trì cấu trúc mạng theo tham số này Tham số “giá trị” sẽ được cập nhật bằng cách mỗi nút mạng sẽ gửi liên tục thông tin quảng bá về “giá trị ”của các liên kết xuất phát từ nó đến tất cả các nút khác sử dụng thuật toán chọn đường kiểu phát tràn lan (flooding) Mỗi nút mạng khi nhận được các thông tin này sẽ cập nhật cấu trúc mạng và sử dụng thuật toán tìm đường đi ngắn nhất đến nút mạng tiếp theo Liên kết có thể có giá trị không chính xác do nhiều nguyên nhân như trễ đường truyền, sự phân mảnh mạng,… Khi cấu hình mạng thay đổi, vòng định tuyến khép kín (loop) có thể hình thành Tuy nhiên thời gian tồn tại của các vòng định tuyến này rất ngắn vì chúng bị xoá đi ngay khi bản tin đã đi qua

Vectơ khoảng cách

Phương pháp định tuyến dựa trên vector khoảng cách đã có nhiều cải tiến hơn so với phương pháp định tuyến dựa trên trạng thái liên kết trong đó mỗi nút mạng chỉ giám sát giá trị của liên kết xuất phát từ nó Nó không quảng bá thông tin đến tất cả nút trong mạng Theo định kỳ nó sẽ gửi quảng bá đến các nút lân cận thông tin về khoảng cách ngắn nhất đến các nút khác trong mạng Nút mạng nhận được thông tin

sẽ tính toán và cập nhật lại bảng định tuyến của mình thông qua thuật toán tìm đường ngắn nhất bằng cách so sánh vectơ khoảng cách của nó với thông tin vừa nhận được

So với định tuyến dựa theo trạng thái liên kết, định tuyến dựa trên vectơ khoảng cách hiệu quả hơn và dễ thực hiện hơn Phương pháp này yêu cầu ít bộ nhớ lưu trữ Tuy nhiên, định tuyến theo vectơ khoảng cách có thể tạo ra các vòng định tuyến

thời gian ngắn và vòng định tuyến thời gian dài Nguyên nhân chính là do các nút mạng chọn chặng đi tiếp theo dựa trên bảng định tuyến đã được xây dựng từ thông tin quá cũ (không được cập nhật)

Định tuyến nguồn

Định tuyến nguồn hay định tuyến theo yêu cầu là kiểu định tuyến trong đó mỗi gói tin mang theo một đường truyền trọn vẹn (sẽ được truyền trên mạng) trước khi được gửi đi do vậy quyết định định tuyến được thực hiện ngay ở nút nguồn Lợi điểm của phương pháp này là tránh được các vòng lặp định tuyến Tuy nhiên mỗi gói tin đòi hỏi phải có thêm một phần thông tin phụ trội (overhead)

Chọn đường tràn lan (Flooding)

Nhiều giao thức định tuyến đã sử dụng việc phát quảng bá để truyền thông tin điều khiển từ nút gốc tới các nút khác còn lại Việc phát quảng bá các thông tin điều khiển hoạt động như sau: nút nguồn gửi thông tin của nó tới các nút lân cận Trong trường hợp mạng vô tuyến, các nút lân cận đều nằm trong vùng phủ sóng của nút nguồn Sau đó các nút lân cận này tiếp tục chuyển tiếp thông tin điều khiển đó tới lân cận tiếp theo của chúng và cứ như vậy quá trình lặp lại cho đến khi gói tin đã đến toàn bộ các nút trong mạng Một nút mạng chỉ chuyển tiếp gói tin một lần thông qua tham số về thứ tự Khi một gói tin mới đi qua, giá trị của tham số thứ tự này sẽ tăng lên

Định tuyến dựa trên bảng định tuyến xác định trước

Định tuyến dựa trên bảng định tuyến đòi hỏi giao thức luôn phải duy trì, cập nhật thông tin định tuyến từ các nút khác còn lại trong mạng Mỗi nút mạng phải có một hoặc nhiều bảng định tuyến để lưu giữ thông tin định tuyến, dùng các bản tin cập nhật định tuyến truyền trên mạng để đáp ứng lại sự thay đổi về cấu trúc mạng

CHƯƠNG 2 GIAO THỨC ĐỊNH TUYẾN MẠNG AD HOC

2.1 CÁC YÊU CẦU CHUNG

Do các nút trong mạng Ad Hoc luôn di động và có nhiều đặc tính khác biệt nên không thể áp dụng các giao thức định tuyến thông thường Các mạng Ad Hoc thường được đặc trưng bởi một tôpô động do các nút di chuyển và làm thay đổi vị trí vật lý của chúng Đối với mạng Ad Hoc, giao thức định tuyến động tỏ ra hiệu quả và phù hợp hơn các phương pháp định tuyến thông thường ví dụ như giao thức định tuyến dựa trên vectơ khoảng cách và trạng thái liên kết Thách thức trong việc thiết kế các giao thức định tuyến động là khả năng cập nhật được mức di động của nút mạng Chính mức di động này là nguyên nhân làm thay đổi toàn bộ cấu trúc tôpô của mạng Một nút di động thường bị giới hạn bởi khả năng xử lý của CPU, dung lượng lưu trữ, công suất nguồn và dải thông

Môi trường truy nhập, môi trường vô tuyến cũng có những thuộc tính đặc biệt cần phải chú ý khi thiết kế các giao thức cho mạng Ad Hoc Ví dụ các đường truyền

vô hướng Những đường truyền này xuất hiện khi hai nút có cường độ phát khác nhau và cho phép chỉ một nút nghe được nút kia Nhưng chúng cũng có thể xuất hiện do nhiễu từ môi trường xung quanh Đa chặng trong môi trường vô tuyến có thể gây ra tăng ích công suất truyền và tăng ích công suất do mối quan hệ căn bậc hai giữa vùng phủ sóng và công suất phát ra Bằng cách sử dụng đa chặng, các nút

có thể truyền các gói tin đi sử dụng công suất ra thấp

Hình 2.1 mô tả các trục cơ bản có thể sử dụng để đặc tả môi trường mạng Ad Hoc Trục đầu tiên là số các nút trong mạng Trục thứ 2 là tốc độ mà tại đó tôpô mạng thay đổi Trục thứ ba là tải lưu lượng trong mạng Khi môi trường di chuyển

từ gốc của 3 trục, vấn đề định tuyến trở nên khó khăn hơn Tăng số các nút, tăng tốc

độ thay đổi tôpô (nghĩa là tăng tính di động của nút), hoặc tăng tải lưu lượng mong muốn trên mạng là thách thức đối với các giao thức định tuyến trong mạng Ad Hoc

đ ộ th

a y đ ổi tôpô

Hình 2.1 Hệ tọa độ cơ bản mô tả môi trường mạng Ad Hoc

Các giao thức định tuyến trong mạng Ad Hoc có một số thuộc tính mong muốn như sau:

Hoạt động phân tán

Giao thức định tuyến trong mạng Ad Hoc phải là giao thức phân tán yêu cầu độ tin cậy cao Do các nút là di động nên giao thức định tuyến tập trung là không phù hợp Mỗi nút mạng phải đủ thông minh để tạo các quyết định định tuyến sử dụng các nút lân cận khác

Không lặp vòng

Để nâng cao hiệu năng giao thức định tuyến mạng Ad Hoc phải đảm bảo các tuyến được cung cấp không bị lặp vòng Điều này tránh được các lãng phí như: băng thông hoặc công suất sử dụng của CPU

Hoạt động dựa trên yêu cầu

Thuật toán định tuyến trong mạng Ad Hoc phải thích ứng với lưu lượng yêu cầu hoặc nhu cầu cơ bản để sử dụng hiệu quả các tài nguyên năng lượng và dải thông mạng Giao thức đó chỉ tương tác khi cần thiết và giao thức đó không phát quảng bá định kỳ các thông tin điều khiển Điều này làm giảm thiểu phần thông tin điều khiển nhưng lại làm tăng độ trễ

Tính tiên phong (proactive)

Trong một số trường hợp phải tăng thời gian trễ do hoạt động dựa trên yêu cầu là không chấp nhận được Do đó phải sử dụng đặc tính tiên phong nếu tài nguyên của mạng (về mặt dải thông) nằm trong khoảng cho phép

Hỗ trợ liên kết theo một hướng

Môi trường vô tuyến có thể là nguyên nhân hình thành các liên kết theo một hướng Sử dụng các kiểu liên kết này và các kiểu liên kết hai chiều sẽ nâng cao hiệu năng của giao thức định tuyến

Tính bảo mật

Môi trường vô tuyến rất dễ bị tấn công bởi các cuộc tấn công mạo danh Do vậy

để đảm bảo an toàn cho các giao thức định tuyến, chúng ta cần một số biện pháp phòng ngừa Chẳng hạn nhận thực và mã hoá là cách bảo mật thông thường nhất được áp dụng hiện nay Vấn đề ở đây là việc phân bổ các khoá và các nút trong mạng Ad Hoc

Bảo toàn năng lượng

Các nút trong mạng Ad Hoc có thể là các máy tính xách tay, các thiết bị cầm tay PDA trong đó chúng bị giới hạn về năng lượng nguồn và do đó chúng sẽ sử dụng một số phương thức chờ (standby) để tiết kiệm năng lượng Do vậy các giao thức định tuyến trong mạng Ad Hoc phải hỗ trợ được các chế độ hoạt động này

Đa tuyến

Đa tuyến có thể được sử dụng để giảm các tương tác do sự thay đổi về cấu trúc tôpô và trạng thái nghẽn mạng Nếu một tuyến nào đó không còn hiệu lực, một tuyến khác có thể vẫn còn hiệu lực và như vậy giao thức định tuyến không cần phải khởi tạo thủ tục khám phá tuyến mới khác

Hỗ trợ chất lượng dịch vụ QoS

Giao thức định tuyến trong mạng Ad Hoc cần kết hợp một số phương thức hỗ trợ chất lượng dịch vụ QoS Điều này phụ thuộc vào mục đích sử dụng của mạng, ví dụ như mục đích hỗ trợ lưu lượng thời gian thực

Để giải quyết vấn đề định tuyến trong mạng Ad Hoc, nhóm đặc trách kỹ thuật Internet trong IETF đã thành lập ra nhóm công tác mạng Ad Hoc Di động MANET

MANET là tổ chức nghiên cứu về mạng Ad Hoc, phát triển các đặc tính về định tuyến cho mạng Ad Hoc dựa trên nền IP Tổ chức này đã đưa ra kết quả nghiên cứu dưới dạng bản dự thảo và một số khuyến nghị RFC Hiện nay, chưa có một giao thức chính thống và đầy đủ các tính năng như ở trên được đề xuất trong MANET Các giao thức đề xuất chỉ mới đáp ứng được chức năng chính là: tìm đường đi đến đích, chứ không phải là đáp ứng tìm đường đi ngắn nhất hay tối ưu nhất Tuy nhiên, một số giao thức còn trong giai đoạn phát triển và hy vọng sẽ hỗ trợ nhiều chức năng hơn

2.2 PHÂN LOẠI

Các giao thức định tuyến có thể phân loại thành các dạng khác nhau phụ thuộc vào các thuộc tính của chúng:

- Tập trung (Centralized) ngược với Phân tán (Distributed)

- Tĩnh (Static) ngược với Thích ứng (Adaptive)

- Tương tác (Reactive) ngược với Tiên phong(Proactive) hay là

- Định tuyến nguồn ngược với Chặng–theo–Chặng (Hop-by-hop)

Từ sự phân loại trên, chỉ có 2 loại cuối cùng là thích hợp trong nghiên cứu Các

cơ chế định tuyến tin cậy trong điều khiển tập trung không đáp ứng được trong môi trường mạng Ad Hoc phân tán Tương tự, các lược đồ định tuyến tĩnh cũng không đáp ứng được sự thay đổi của các trạng thái chuyển động

Các giao thức mang tính tiên phong cố gắng đánh giá liên tục các tuyến trong mạng để khi một gói cần phải chuyển tiếp thì tuyến đó đã sẵn sàng để sử dụng Trong thuật toán tiên phong phần phụ trội định tuyến là không đổi đối với các gói định tuyến không dữ liệu Trong các giao thức định tuyến theo bảng, mỗi nút duy trì một hay nhiều bảng bao gồm thông tin định tuyến tới nút khác trong mạng Tất cả các nút mạng sẽ cập nhật các bảng này để duy trì một cách phù hợp thông tin và tình trạng của mạng Khi tôpô mạng thay đổi, các nút truyền các bản tin thông báo cho nhau để cập nhật thông tin về tuyến của toàn bộ mạng Kiểu định tuyến nguồn

là kiểu định tuyến trong đó phần mào đầu của gói tin sẽ chứa thông tin của toàn bộ tuyến Kiểu định tuyến này có ưu điểm là các nút trung gian không cần yêu cầu duy

trì thông tin cập nhật để chuyển tiếp các gói Nhược điểm của định tuyến nguồn là kích cỡ gói có thể tăng lên, đặc biệt là trong các mạng có số nút lớn

Bảng 2.1 So sánh các Giao thức định tuyến (Theo yêu cầu với Theo bảng)

Tính khả dụng của thông tin

định tuyến

không chú ý đến nhu cầu Triết lý định tuyến (Lược đồ

định địa chỉ: Phẳng hoặc phân

Phần phụ trội

tin báo định tuyến

Tăng với sự di động tăng lên trong tuyến tích cực

Lớn hơn so với định tuyến theo yêu cầu

Ngược lại, trong các giao thức tương tác: thủ tục xác định tuyến chỉ được gọi theo yêu cầu Khi cần một tuyến, một số thủ tục tìm kiếm tuyến được sử dụng Trong các giao thức tương tác, toàn bộ các tuyến được cập nhật và không được duy trì tại từng nút Thay vào đó các tuyến được tạo ra khi được yêu cầu Khi một nút yêu cầu một tuyến tới đích, nó gọi ra các cơ chế khám phá tuyến để tìm một đường truyền tới đích Quá trình này được hoàn thành khi một tuyến được tìm thấy hoặc toàn bộ các hoán vị tuyến đã được xem xét Khi một tuyến đã được thiết lập, nó sẽ được duy trì bởi một thủ tục là thủ tục duy trì tuyến Các giao thức định tuyến chặng theo chặng như là các giao thức vectơ: chỉ bao gồm thông tin của đích trong phần mào đầu và sử dụng các bảng cục bộ để xác định chặng tiếp theo trong tuyến Ưu điểm của kiểu định tuyến này là giới hạn được kích cỡ gói, nhưng có nhược điểm là các nút luôn phải yêu cầu duy trì và trao đổi thông tin định tuyến

Hình 2.2 minh họa phần phụ trội định tuyến ngược với tính di động đối với các

cơ chế định tuyến khác nhau

Hình 2.2 Phần phụ trội định tuyến và tính di động đối với các cơ chế định tuyến khác nhau

Ưu điểm của lược đồ tiên phong là khi cần một tuyến, tuyến được xác định trong khoảng trễ nhỏ Đối với các giao thức tương tác trễ để xác định tuyến tương đối lớn Ngoài ra, thủ tục tìm kiếm tuyến toàn cục đối với các giao thức tương tác đòi hỏi lưu lượng điều khiển phải đáng kể Các giao thức định tuyến tương tác thuần tuý không áp dụng được trong các ứng dụng thời gian thực

2.2.1 Các giao thức định tuyến đơn hướng

Có 3 loại giao thức định tuyến đơn hướng (Unicast)

- Tiên phong (Proactive) là các giao thức được điều khiển thông qua các bảng định tuyến Nó duy trì một cách thống nhất và luôn cập nhật thông tin về toàn bộ các nút

- Tương tác (Reactive) là các giao thức theo yêu cầu Nó tối thiểu hoá phần phụ

trội bằng cách chỉ thực hiện phát hiện tuyến khi có yêu cầu

- Cuối cùng là các giao thức (Hybrid).Nó là sự kết hợp các tính năng của giao laithức tiên phong và giao thức tương tác

Các lược đồ định tuyến đơn hướng có thể chia nhỏ ra thành 2 loại: Phẳng và Phân cấp

Trong các lược đồ định tuyến phẳng, mỗi nút duy trì một bảng định tuyến với các đầu vào là toàn bộ các nút trong mạng Lược đồ định tuyến phẳng có thể được chấp nhận nếu mật độ người sử dụng nhỏ Tuy nhiên khi số các nút di động tăng lên sẽ làm cho phụ trội tăng đáng kể Do vậy, các thuật toán định tuyến phẳng không thích hợp cho mạng lớn

Định tuyến kết hợp Tiên phong và Tương tác Định tuyến Tiên phong Định tuyến Tương tác

Phần phụ trội định tuyến

tăng lên

Để có khả năng mở rộng mạng, các kỹ thuật phân cấp được áp dụng Trong những kỹ thuật này mạng bao gồm 2 loại nút, các điểm cuối (endpoint) và các chuyển mạch Các điểm cuối mới có thể là các nguồn và đích đối với lưu lượng dữ liệu người sử dụng và chỉ các chuyển mạch mới có thể thực hiện các chức năng định tuyến Để tổ chức các lớp thấp nhất trong phân cấp, các điểm cuối chọn các chuyển mạch thích hợp mà chúng sẽ kết hợp bằng cách kiểm tra chất lượng liên kết vô tuyến Bằng cách tự trị, chúng nhóm với nhau thành các tế bào quanh các chuyển mạch Thủ tục này được gọi là thủ tục "hình thành tế bào"

Ưu điểm chính của định tuyến phân cấp là sử dụng hiệu quả các tài nguyên kênh

vô tuyến và giảm mạnh việc lưu trữ bảng định tuyến, truyền dẫn và xử lý phụ trội

2.2.2 Các giao thức định tuyến đa hướng

Việc gửi bản tin thông báo tới một nhóm các nút được xác định trước gọi là phát

đa hướng (multicast) Các thuật toán của nó được gọi là thuật toán định tuyến đa hướng Định tuyến đa hướng có ý nghĩa quan trọng trong việc giảm băng thông thực hiện đối với việc phân bổ nhiều dữ liệu

Có 3 loại giao thức định tuyến đa hướng:

- Tiên phong là các giao thức tính toán trước đường tới toàn bộ các đích có thể

và lưu trữ thông tin này trong các bảng định tuyến Chúng duy trì, cập nhật cơ sở dữ liệu về thông tin định tuyến được phân bổ định kỳ trong toàn mạng

- Tương tác là các giao thức theo yêu cầu Giao thức này tạo ra đường tới các nút

khác nhau khi có yêu cầu Ý tưởng chính là dựa trên cơ chế đáp ứng xếp hàng hoặc

đa hướng thụ động Trong giai đoạn xếp hàng, một nút khám phá môi trường Khi xếp hàng vươn tới đích, giai đoạn đáp ứng bắt đầu và thiết lập đường

- Cuối cùng là giao thức phát Tràn lan mạng Mỗi một nút sau khi nhận được một bản tin thông báo nó lại tiếp tục phát tới các nút lân cận

tự động bởi giao thức định tuyến DSR

Số các chặng trung gian để đến một đích nào đó luôn thay đổi nên cấu trúc tôpô mạng cũng dễ bị thay đổi nhanh chóng Giao thức DSR cho phép mạng có khả năng

tự tổ chức và sắp xếp mà không cần đến cơ sở hạ tấng mạng hiện có Khi các nút bắt đầu dịch chuyển thì tỷ lệ phần phụ trội gói định tuyến DSR sẽ tự động thay đổi theo để theo dõi các tuyến đang sử dụng Điều này giúp cho giao thức DSR tiết kiệm được băng thông và bảo toàn được năng lượng của nguồn nuôi

Giao thức DSR bao gồm 2 cơ chế cơ bản: Khám phá tuyến (Route Discovery) và Duy trì tuyến (Route Maintenance) Khám phá tuyến và Duy trì tuyến hoạt động

hoàn toàn theo yêu cầu Hình 3.1 chỉ ra hoạt động cơ bản của giao thức DSR

- Khám phá tuyến là cơ chế trong đó nút S muốn gửi một gói tới nút đích D thu được một tuyến nguồn tới Khám phá tuyến được sử dụng chỉ khi S cố gắng gửi Dgói tin tới D và chưa tìm được tuyến tới D Để giảm chi phí của Khám phá tuyến, mỗi node sẽ duy trì một Bộ nhớ tuyến (Route Cache) để chứa các tuyến nguồn mà

nó phải học hoặc nghe lỏm

- Duy trì tuyến là cơ chế trong đó bộ khởi tạo gói S có khả năng phát hiện và duy

trì một tuyến nguồn tới D Khi thủ tục Duy trì tuyến cho biết một tuyến nguồn đã bị đứt, S sẽ cố gắng sử dụng một tuyến khác nó ngẫu nhiên biết tới đích D hoặc có thể gọi lại thủ tục Khám phá tuyến để tìm ra một tuyến mới Duy trì tuyến chỉ được sử dụng khi S thực sự muốn gửi gói tới D

Hình 3.1 DSR bao gồm 2 cơ chế Khám phá tuyến và Duy trì tuyến

Trong DSR, cơ chế Khám phá tuyến và Duy trì tuyến đều có thể thực hiện được trên các liên kết một chiều và các tuyến không đối xứng Trên thực tế, trong mạng

vô tuyến sự liên kết giữa 2 nút có thể không giống nhau đối với cả 2 chiều do sự khác nhau của anten, các mẫu truyền hoặc các nguồn phát tín hiệu Giao thức DSR được xây dựng có sự hỗ trợ của lớp MAC (lớp MAC sẽ thông báo cho giao thức về trạng thái các liên kết) Các liên kết như vậy được sử dụng khi cần thiết làm nâng cao toàn bộ hiệu năng và sự kết nối mạng trong hệ thống

DSR hỗ trợ nhiều kiểu liên kết khác nhau Tuyến nguồn trong DSR là sự kết hợp của tất cả các kiểu mạng nào sẵn có Một số nút trong mạng Ad Hoc có các thiết bị

vô tuyến phạm vi ngắn, trong khi các nút khác có gắn kèm các thiết bị vô tuyến phạm vi dài Sự kết hợp của các nút này tạo thành một mạng Ad Hoc đơn Ngoài ra, định tuyến DSR còn được tích hợp trong định tuyến Internet cơ bản, khi đó một nút cổng được đại diện kết nối với mạng Internet Nút này cũng tham gia trong các giao thức định tuyến mạng Ad Hoc; DSR còn được tích hợp trong IP di động, ở đó nút cổng đại diện đóng vai trò một như một tác nhân bên ngoài IP di động

3.2 MỘT SỐ GIẢ ĐỊNH

- Giả định toàn bộ các nút trong mạng Ad Hoc đều sẵn sàng chuyển tiếp các gói tin đi tới các nút khác còn lại trong mạng

- Số chặng tối thiểu cần thiết để một gói tin đi từ một nút bất kỳ tại biên xa nhất của mạng tới một nút khác được định vị tại biên xa nhất đối diện là đường kính của mạng Ad Hoc Đường kính của mạng Ad Hoc thường nhỏ khoảng 5 đến 10 chặng.

- Các gói tin có thể bị mất hoặc bị lỗi khi truyền dẫn trong mạng vô tuyến Một nút nếu nhận được một gói tin bị lỗi sẽ thực hiện phát hiện lỗi và loại bỏ gói đó đi

- Các nút trong phạm vi mạng Ad Hoc có thể dịch chuyển rất ngẫu nhiên không theo quy luật Ở đây giả thiết tốc độ dịch chuyển của các nút trong mạng phù hợp với thời gian trễ truyền gói và vùng phủ sóng của mạng được sử dụng Thực tế, DSR có thể hỗ trợ tốc độ dịch chuyển nhanh của nút mạng với một điều kiện là các nút không di chuyển với tần xuất quá cao và liên tục trong khi thực hiện phát tràn lan các gói dữ liệu

- Giả thiết các nút có phương thức nhận trong đó không phân biệt giao diện phần cứng mạng do đó phần cứng sẽ chuyển mọi gói tin vừa nhận được tới phần mềm điều khiển mạng mà không lọc dựa trên địa chỉ đích lớp liên kết Phương thức này

sẽ làm tăng phụ trội phần mềm trong CPU

- Khả năng trao đổi thông tin vô tuyến giữa từng cặp nút có thể không như nhau trên cả 2 hướng do sự khác nhau như: anten, các mẫu truyền hoặc các nguồn nhiễu quanh 2 nút Truyền vô tuyến giữa các cặp nút trong nhiều trường hợp là 2 chiều Tuy nhiên, có lúc truyền vô tuyến giữa 2 nút chỉ là một chiều tức là nó cho phép một nút gửi các gói thành công tới một nút khác trong khi không có khả năng truyền các gói tin theo hướng ngược lại Mặc dù rất nhiều giao thức định tuyến chỉ hoạt động tốt trên các liên kết 2 chiều trong khi đó DSR lại hoàn toàn có thể phát hiện và chuyển các gói tin một cách thành công qua các tuyến chứa các liên kết một chiều Một số giao thức tại lớp MAC như MACA, MACAW hoặc IEEE 802.11 lại giới hạn việc truyền các gói dữ liệu đơn hướng trên các tuyến liên kết 2 chiều để tiết kiệm băng thông mạng do nhu cầu trao đổi trao đổi hai chiều các gói tin RTS (Request To Send) và CTS (Clear To Send) trong những giao thức này tương đối lớn Khi sử dụng các thủ tục liên quan đến lớp MAC như đã nói trên, DSR có thể tận dụng thêm được nhiều tối ưu ví dụ như tối ưu đảo chiều của tuyến sẽ được trình bày dưới đây

- Mỗi nút lựa chọn một địa chỉ IP đơn cho chính mình Thông thường một nút có thể có nhiều giao diện vật lý mạng khác nhau, tuy nhiên trong trường hợp này chúng ta yêu cầu mỗi nút chọn một địa chỉ duy nhất và chỉ sử dụng địa chỉ này khi tham gia vào giao thức DSR Điều này cho phép các nút có thể nhận biết được nhau trong mạng Ad Hoc như một thực thể độc lập mà không cần quan tâm đến các nút khác sử dụng giao diện gì khi trao đổi thông tin với chúng Để phù hợp với các thuật ngữ được sử dụng trong IP di động, địa chỉ của mỗi nút trong mạng Ad Hoc được hiểu như là địa chỉ nhà của chúng Địa chỉ nhà của từng nút có thể được gán thông qua bất kỳ cơ chế nào (ví dụ cơ chế gán địa chỉ tĩnh hoặc sử dụng cơ chế gán địa chỉ động DHCP)

3.3 ĐỊNH TUYẾN NGUỒN

DSR phát hiện và sử dụng các tuyến nguồn Nút gửi tin sẽ phải nắm được toàn bộ thông tin về trình tự sắp xếp của các chặng (vị trí các nút) của mạng tới một nút đích Mỗi gói tin được định tuyến sẽ mang thông tin về danh sách các chặng này trong tiêu đề Ưu điểm quan trọng của thủ tục định tuyến nguồn là các nút trung gian không cần duy trì việc cập nhật thông tin định tuyến khi chuyển tiếp các gói tin bởi vì bản thân các gói đã mạng các thông tin quyết định việc định tuyến (danh sách đầy đủ các nút theo trình tự mà gói phải đi qua)

Việc tập hợp thông tin về tôpô mạng tại nút nguồn của mỗi gói cho phép nút nguồn phân phát các gói tin một cách hữu hiệu trong mạng Điều này rất thích hợp với việc quản lý tài nguyên trong mạng Ad Hoc

Giao thức định tuyến dựa trên các tuyến nguồn còn có thêm 2 lợi ích Thứ nhất, giao thức có thể chứng minh được một cách đơn giản tính không lặp vòng bởi vì tuyến nguồn được sử dụng để điều khiển định tuyến các gói Thứ hai, mỗi tuyến nguồn là một bản kê sẵn về một đường truyền cụ thể, tin cậy để truyền các thông tin qua mạng

DSR đã sử dụng các tuyến nguồn và mỗi gói được định tuyến dựa trên một tuyến nguồn khám phá được, tuy nhiên những cải thiện gần đây đối với DSR đã cho phép hầu hết các gói tin không phải mang theo phần tiêu đề chứa thông tin đầy đủ về tuyến nguồn

3.4 KHÁM PHÁ TUYẾN

Khám phá tuyến được thực hiện bằng cách phát tràn lan yêu cầu qua mạng để tìm kiếm một tuyến tới đích nào đó Trong dạng đơn giản nhất, nút nguồn A muốn khám phá một tuyến tới nút đích D thì nút sẽ phát quảng bá gói tin RTS (Yêu cầu Atuyến) và gói này lại tiếp tục được quảng bá bởi các nút trung gian cho đến khi gói tin này đến được nút Trong cơ chế này, nhiều tối ưu hoá được sử dụng để giới Dhạn tần số và phạm vi của các việc Khám phá tuyến

Phương pháp phát tràn lan đặc biệt thích hợp với các mạng vô tuyến Thông thường các kênh thông tin giữa các nút trong mạng vô tuyến thường là các kênh quảng bá

Khi một nút muốn gửi một gói tin đến nút S D nào ó, đ đầu tiên nó sẽ đặt vào phần tiêu đề của gói tin đó một tuyến nguồn trong đó chỉ ra thứ tự của các chặng mà gói tin sẽ phải đi qua Thông thường, nút sẽ đạt được một tuyến nguồn thích hợp S thông qua việc tìm kiếm trong bộ nhớ tuyến của nó các tuyến đã biết trước đây Tuy nhiên nếu không tìm thấy tuyến nào trong bộ nhớ tuyến, nó sẽ khởi tạo thủ tục Tìm kiếm tuyến động để tìm ra một tuyến nguồn tới Trong trường hợp này ta gọi nút D

S là nút nguồn còn nút Dlà nút đích trong thủ tục Khám phá tuyến

Trước khi khởi tạo một gói tin RTS Yêu cầu tuyến, nút nguồn chọn một nhận dạng yêu cầu (Request_id) đặt trong gói tin RTS Cặp <địa chỉ khởi tạo, nhận dạng yêu cầu> là duy nhất

-Hình 3.2 Hoạt động cơ bản của Khám phá tuyến; A là nút nguồn, E là nút đích

khi tới đích Là rỗng khi tin báo được gửi đầu tiên

phép đi qua

trữ trong danh sách này

nhn được gói

Bảng 3.1 Các trường của tin báo Yêu cầu tuyến (Các trường in nghiêng để chỉ thị các tính năng cải tiến của DSR)

Các trường của tin báo Yêu cầu tuyến được đưa ra trong Bảng 3.1

Mỗi khi một nút nhận được gói tin Yêu cầu tuyến nó sẽ xử lý theo các bước sau:

- Nếu cặp (địa chỉ khởi tạo, nhận dạng yêu cầu) này được tìm thấy trong danh sách các yêu cầu tuyến gần đây của nút, thì nó loại bỏ thủ tục gói Yêu cầu tuyến và không xử lý thêm

- Nếu địa chỉ của nút này đã được liệt kê trong bộ nhớ tuyến trong yêu cầu, thì nó loại bỏ gói Yêu cầu tuyến và không xử lý thêm

- Hoặc, nếu nút là nút Đích dự định, bản ghi tuyến được hoàn thành, nút trả lời bằng cách gửi tin báo Trả lời tuyến RREP với một bản sao của tuyến (thông tin đường truyền đảo ngược trở lại về nút nguồn)

- Hoặc, gắn thêm địa chỉ nút vào bản ghi tuyến trong gói Yêu cầu tuyến, và phát lại quảng bá tới các lân cận của nó

- Khi bản tin Yêu cầu tuyến tới một nút có thông tin về tuyến tới nút đích,

nó sẽ gửi một tin báo Trả lời tuyến RREP trở lại nút nguồn và không truyền quảng bá gói Yêu cầu tuyến đi tiếp Bộ nhớ (cache) tuyến được duy trì tại mỗi nút sẽ ghi các tuyến đã biết được để làm giảm phần phụ trội định tuyến tạo ra trong thủ tục khám phá tuyến Bất kỳ nút nào tham gia vào quá trình khám phá tuyến đều có thể tìm được tuyến nhờ việc chuyển tiếp gói Yêu cầu tuyến và thu thập thông tin định tuyến trong bộ nhớ tuyến của nó

Hình 3.2 minh họa quá trình Khám phá tuyến đơn giản; một nút A cố gắng khám phá một tuyến tới nút Để khởi đầu Khám phá tuyến, E A truyền một tin báo Yêu cầu tuyến Mỗi tin báo Yêu cầu tuyến nhận dạng bộ khởi đầu và đích của Khám phá

tuyến Nhận dạng yêu cầu được xác định bởi bộ khởi đầu của Yêu cầu Một Yêu cầu tuyến bao gồm một bản ghi danh sách địa chỉ của từng nút trung gian trong đó tin báo Yêu cầu tuyến được lưu lại qua từng nút trên đường đi của nó Giá trị ban đầu của bản ghi tuyến là một danh sách trống

Trong việc bản tin Trả lời tuyến trở lại nút nguồn trong thủ tục Khám phá tuyến, chẳng hạn nút trả lời nút E A trong Hình 3.2: nút Esẽ kiểm tra Bộ nhớ tuyến của nó xem nếu có một tuyến ngược về nút A.và nếu tìm được nó sẽ sử dụng tuyến này làm tuyến nguồn để phân phát các gói tin bao gồm cả gói Trả lời tuyến Nếu không tìm được một tuyến ngược trờ lại A, E có thể thực hiện thủ tục Khám phá tuyến từ nó tới nút đích Để tránh khả năng quay trở lại vô hạn có thể của các Khám phá Atuyến, nó phải cõng theo bản tin Trả lời tuyến trên chính bản tin Yêu cầu tuyến của

nó đối với nút A Sử dụng cơ chế này nó cũng có khả năng cõng theo các gói dữ liệu nhỏ khác ví dụ như gói TCP SYN trên một bản tin Yêu cầu tuyến Nút E còn có thể đảo vị trí sắp xếp của các chặng trong bản ghi tuyến và sử dụng tuyến đã đảo vị trí này như một tuyến nguồn đối với các gói tin mang bản tin Trả lời tuyến của chính nó Đối với các giao thức thuộc lớp MAC ví dụ giao thức IEEE 802.11 có yêu cầu trao đổi khung 2 chiều, việc đảo tuyến này giúp tránh được phần phụ trội của Khám phá tuyến lần thứ 2 có thể Nó kiểm tra tuyến vừa được khám phá ra để đảm bảo rằng nó là 2 chiều trước khi nút nguồn trong Khám phá tuyến bắt đầu sử dụng chúng Tuy nhiên kỹ thuật này cũng ngăn cản việc khám phá tuyến sử dụng các đường liên kết một chiều Trong môi trường vô tuyến, việc sử dụng các liên kết một chiều là chấp nhận được Trong một số trường hợp, các tuyến liên kết một chiều như vậy lại hiệu quả hơn rất nhiều so với các liên kết 2 chiều

Khi khởi tạo thủ tục Khám phá tuyến, nút đang gửi sẽ lưu lại bản copy của gói tin ban đầu trong bộ nhớ đệm nội bộ (Send Buffer) gọi là Bộ đệm gửi Ngoài ra Send Buffer còn chứa bản sao của các gói tin không truyền đi được do chưa tìm ra một tuyến nguồn tới đích Mỗi gói trong Send Buffer được gán một tem thời gian chỉ ra thời gian chúng tồn tại trong Buffer và gói tin sẽ bị loại bỏ sau khi lưu lại trong Send Buffer quá hạn; để Send Buffer không bị tràn, kỹ thuật FIFO hoặc kỹ thuật

tương đương khác có thể được sử dụng để truyền các gói tin đó đi trước khi chúng hết hạn

Trong trường hợp gói tin còn lưu lại trong Send Buffer mà chưa truyền đi được thì thi thoảng nút mạng lại thiết lập mới thủ tục Khám phá tuyến tuỳ theo địa chỉ đích của các gói Tuy nhiên, tần xuất khởi tạo các Khám phá tuyến mới cần phải được giới hạn do có thể xảy ra trường hợp đích của thủ tục khởi tạo tuyến đã thay đổi và không thể tới được Trên thực tế, do giới hạn về phạm vi truyền dẫn vô tuyến

và sự di chuyển của các nút trong mạng nên nhiều khi cấu trúc mạng bị phân mảnh, nghĩa là không có thứ tự sắp xếp của các chặng mà qua đó gói tin được chuyển tiếp tới đích Kiểu phân mảnh mạng như vậy có thể hiếm gặp hoặc phổ biến tuỳ thuộc vào kiểu di chuyển và mật độ của các nút trong mạng

Hình 3.3 Quá trình thiết lập bản ghi định tuyến của DSR

Trong trường hợp với mỗi gói tin, một thủ tục Khám phá tuyến được khởi tạo thì một số lớn các gói Yêu cầu tuyến không hữu ích được truyền từ nút này tới tất cả các nút trong mạng Ad Hoc Để giảm phần phụ trội tiêu đề từ do các Khám phá tuyến trên người ta phải giới hạn tần xuất khởi tạo các Khám phá tuyến từ một nút bất kỳ đến cùng một đích Nút chỉ được phép khởi tạo thủ tục Khám phá tuyến mới sau khi đợi hết khoảng thời gian tối thiểu cần thiết để có thể thiết lập thủ tục Khám phá tuyến mới Giới hạn tần xuất cực đại trong việc khởi tạo Khám phá tuyến này tương tự cơ chế cần thiết đối với nút trong mạng Internet hạn chế các yêu cầu ARP gửi tới các địa chỉ IP

Từ kết quả của việc kiểm tra bản sao (copy) các tuyến nguồn ghi được, thuật toán Khám phá tuyến đã ngăn chặn được việc lặp các Yêu cầu tuyến trong mạng Đó là một thuộc tính hiệu chỉnh quan trọng và là nguyên nhân tạo ra thuộc tính không lặp vòng của DSR Sử dụng các nhận dạng yêu cầu là một tối ưu đơn giản khi đó các Yêu cầu tuyến ban đầu trải rộng hướng ra phía ngoài so với nút nguồn và rút bớt số các gói Yêu cầu bao quanh bộ khởi tạo, như chỉ ra trên Hình 3.4

Trong khi truyền một Yêu cầu tuyến, các nút trong mạng tuân theo quy tắc thông thường khi xử lý trường đếm chặng (Hop Count) hoặc trường thời gian tồn tại -(Time-to-Live) trong phần tiêu đề IP của gói mang Yêu cầu tuyến Cơ chế này được sử dụng để thực hiện các kỹ thuật tìm kiếm "mở rộng vòng" cho đích, trong đó giới hạn chặng được tăng dần trong khi truyền lại

nút E Trong nhiều trường hợp khẳng định việc nhận gói tin không ảnh hưởng gì đối với giao thức DSR do thực tế đây là một phần của các thủ tục lớp MAC

Hình 3.5 Duy trì tuyến, nút C không thể chuyển tiếp từ A đến E

qua liên kết tới bước nhẩy tiếp theo D của nó

Nếu cơ chế này không tồn tại và sẵn có ở các nút thì khi đó nút gửi tin sẽ dùng một bít thông tin trong phần tiêu đề của gói tin để yêu cầu một phúc đáp từ nút tiếp theo thông qua phần mềm đặc biệt trong DSR Thông thường phúc đáp qua phần mềm này được truyền trực tiếp tới nút gửi tin Tuy nhiên nếu đường liên kết giữa hai nút là liên kết đơn hướng thì phúc đáp này có thể phải đi qua rất nhiều chặng khác nhau để quay trở lại nút gửi tin

Nếu gói tin được truyền lại qua một số chặng và vượt quá số lần cực đại cho phép mà vẫn chưa nhận được khẳng định từ nút tiếp theo, nút này sẽ gửi bản tin ROUTE ERROR (bản tin tuyến có lỗi ) quay trở lại nút đã gửi tin ban đầu để xác minh tuyến bịi lỗi từ nút nào Ví dụ trong Hình 3.5 trên: nếu nút không thể truyền C gói tin tới nút tiếp theo, sẽ gửi bản tin tuyến bị lỗi ROUTE ERROR về nút D C A

và tường trình rằng tuyến từ đến bị đứt Khi đó nút sẽ xoá đường liên kết bị C D A lỗi này khỏi bộ nhớ tuyến của nó Việc truyền lại bản tin ban đầu bây giờ là nhiệm

vụ và chức năng của các thủ tục lớp cao hơn như TCP Trong trường hợp phải gửi lại gói tin tới chính đích E và nếu trong bộ nhớ tuyến của nút có một tuyến khác A tới (ví dụ từ các bản tin Trả lời tuyến từ các thủ tục Khám phá tuyến trước đó E hoặc là từ việc nghe lỏm được các thông tin định tuyến từ các gói tin khác) thì nó

sẽ gửi ngay gói tin sử dung tuyến mới đó Nếu không nó sẽ thực hiện một thủ tục Khám phá tuyến mới tới đích E nói trên

3.6 BỘ NHỚ TUYẾN

Toàn bộ thông tin định tuyến cần thiết đối với một nút khi tham gia trong mạng

Ad Hoc sử dụng giao thức định tuyến DSR được cất giữ trong một Bộ nhớ tuyến

Dữ liệu về các tuyến tại nút đó có thể được lưu trữ dưới nhiều khuôn dạng khác nhau Các tuyến trong bộ nhớ tuyến sẽ hình thành một cây định tuyến, bắt rễ từ nút này tới nút khác trong mạng Bộ nhớ tuyến được lập chỉ mục logic theo địa chỉ nút đích, và hỗ trợ các thao tác sau:

- Void Insert(Route RT) Chèn thông tin được trích từ tuyến nguồn RT vào trong

Bộ nhớ tuyến

- Route Get(Node DEST) Gửi lại một tuyến nguồn từ nút này tới đích DEST (nếu

nó đã biết)

- Void Delete(Node FROM, Node TO) Loại bỏ từ bộ nhớ tuyến bất kỳ tuyến nào

và giả thiết rằng gói được truyền đi từ nút này ( FROM) sẽ được nhận bởi nút đến

(TO)

Một số cải thiện đã được thực hiện trong giao diện Bộ nhớ tuyến Tổ chức của

Bộ nhớ tuyến có một số nguyên tắc chung như sau:

- Bộ nhớ tuyến phải hỗ trợ khả năng lưu trữ nhiều tuyến nguồn đối với một đích nào đó

- Nếu một node S sử dụng một tuyến nguồn tới một đích D nào đó bao gồm nút trung gian N, khi đó phải thu ngắn tuyến tới đích khi nó biết được tuyến tới nút S D

D qua nút ngắn hơn tuyến hiện tại tới Tuy nhiên, bộ nhớ tuyến còn phải có khả N D.năng khôi phục lại các tuyến cũ dài hơn nếu tuyến ngắn hơn không hoạt động

- Chính sách thay thế Bộ nhớ tuyến phải dựa trên "sự ưu tiên" đối với các tuyến

đã được phân loại Các tuyến có độ ưu tiên cao hơn sẽ ít bị loại bỏ khỏi bộ đệm hơn

Một ví dụ về việc sử dụng bộ nhớ tuyến như trong Hình 3.6 Nếu nút di động

F cần gửi một gói tới nút di động , nó sẽ bắt đầu khám phá một tuyến và quảng bá Dmột gói Yêu cầu tuyến Nếu việc quảng bá này là từ nút A, A có thể gửi trả một gói trả lời tuyến tới F bao gồm một tuyến hoàn chỉnh tới D có sắp xếp các chặng là A,

B, C, và D

A B C D

EF

Hình 3.6 Một ví dụ sử dụng bộ nhớ tuyến

DSR chủ yếu sử dụng mobicache (bộ nhớ tuyến di động) Mobicache bao gồm 2

bộ nhớ riêng rẽ: bộ nhớ sơ cấp và bộ nhớ thứ cấp Khi thực hiện thao tác Get(), bộ nhớ sơ cấp được tìm đầu tiên rồi tiếp đến là bộ nhớ thứ cấp Các tuyến được tìm ra

do các Khám phá tuyến hoặc các hoạt động khác được tại nút được chèn vào bộ nhớ

sơ cấp Các tuyến tìm được do nghe lén (mang tính cơ hội) được chèn trong bộ nhớ thứ cấp Chúng sẽ được chuyển sang tới bộ nhớ sơ cấp chỉ khi cần Mỗi bộ nhớ được sử dụng bởi một kỹ thuật thay thế độc lập dựa trên lược đồ quay vòng (round-robin)

Khi một nút chuyển tiếp một gói dữ liệu tới một nút khác trong mạng, nút này sẽ biết được thông tin của toàn tuyến căn cứ vào thông tin trong tiêu đề của gói tin Một nút có thể thêm hoặc bớt các tuyến vào bộ nhớ tuyến mỗi khi nó cập nhật được thông tin về một tuyến mới hoặc thông tin liên quan đến sự thay đổi của tuyến đã có trong bộ nhớ tuyến Trên thực tế, các tuyến nguồn, các bản ghi tuyến trong bản tin Yêu cầu tuyến, các tuyến bị trả lại trong bản tin Trả lời tuyến đều có thể được lưu giữ ở bất kỳ nút nào trong mạng Một trong những hạn chế trong việc lưu giữ các thông tin nghe lén là khả năng xuất hiện các liên kết đơn hướng trong mạng Ad Hoc

Ví dụ, trong Hình 3.7 minh họa tình huống nút A sử dụng một tuyến nguồn để truyền thông với nút E Khi nút C chuyển tiếp dữ liệu dọc theo tuyến từ đến A E,

nó thường ghi thêm vào bộ nhớ tuyến của nó sự xuất hiện của những liên kết hướng chuyển tiếp mà nó học được từ phần tiêu đề của gói tin từ nó tới D và từ D tới E

Tuy nhiên sự đảo hướng của các liên kết (đã được nhận biết trong các phần tiêu đề của gói từ nó ngược lại B và từ đến ) có thể không diễn ra do các liên kết B A