Luận văn Các đề xuất cải tiến giao thức AODV nhằm đảm bảo hỗ trợ QOS

ịnh tương đối của cấu trúc mạng. Sự di chuyển hoặc thay đổi trạng thái của một nút mạng chỉ tác động trong phạm vi của vùng quản lý nó; Chỉ có thông tin điều khiển cấp cao mới được truyền giữa các vùng để giảm tải định tuyến trong mạng. Mỗi nút mạng sẽ có thông tin đầy đủ về các nút mạng khác trong cùng vùng với nó bằng cách sử dụng kỹ thuật định tuyến tìm đường trước. Nếu nút đích và nút nguồn của một yêu cầu truyền dữ liệu thuộc hai vùng khác nhau, kỹ thuật định tuyến liên vùng theo yêu cầu sẽ được sử dụng. Định tuyến liên vùng thường hoạt động theo cơ chế định tuyến theo yêu cầu hoặc cơ chế kết hợp giữa định tuyến tìm đường trước và định tuyến theo yêu cầu. Các giao thức tiêu biểu sử dụng chiến lược định tuyến phân cấp là HSR và CGSR . Hình 2.2 minh họa cho các con đường được hình thành bởi giao thức định tuyến hoạt động theo chiến lược định tuyến phân cấp. Hình 2.2. Đường truyền dữ liệu theo chiến lược định tuyến phân cấp 2.1.4 Định tuyến nguồn và định tuyến từng chặng Có một vài giao thức định tuyến đưa thông tin về toàn bộ con đường vào trong header của các gói tin dữ liệu để các nút trung gian có thể chuyển tiếp những gói tin này theo các thông tin định tuyến mà nó đọc được trong phần header. Chiến lược định tuyến này được gọi là định tuyến nguồn. Ưu điểm của chiến lược định tuyến này là các nút trung gian không cần duy trì thông tin định tuyến cập nhật để tìm đường cho các gói tin chúng chuyển tiếp vì chính trong các gói tin dữ liệu đã chứa thông tin phục vụ cho các quyết định định tuyến. Tuy 18 nhiên, nhược điểm của chiến lược này là làm tăng kích thước của các gói tin dữ liệu, đặc biệt với các con đường dài và trong các mạng có kích thước lớn dẫn đến việc lãng phí băng thông. Giao thức DSR là một trong những giao thức định tuyến nguồn tiêu biểu. Hình 2.3 minh họa cơ chế chuyển tiếp gói tin của giao thức định tuyến nguồn. Hình 2.3. Truyền dữ liệu theo định tuyến nguồn Trong chiến lược định tuyến từng chặng, con đường tới một nút đích được phân bố trong các “chặng kế tiếp” của các nút thuộc con đường này. Khi một nút nhận được một gói tin cần truyền tới một đích xác định, nó sẽ chuyển tiếp gói tin này tới chặng kế tiếp tương ứng trên con đường. Vì mỗi nút mạng không có thông tin đầy đủ về toàn bộ các liên kết trong mạng nên thuật toán định tuyến của các giao thức sử dụng chiến lược định tuyến này phải đảm bảo không chọn các con đường gây ra định tuyến lặp. AODV là một trong những giao thức tiêu biểu sử dụng chiến lược định tuyến từng chặng. Hình 2.4 minh họa kỹ thuật chuyển tiếp gói tin của giao thức hoạt động theo chiến lược định tuyến từng chặng. Hình 2.4. Truyền dữ liệu theo phương pháp định tuyến từng chặng 19 2.1.5 Định tuyến đơn đường và định tuyến đa đường Giao thức định tuyến đơn đường chỉ cài đặt vào bảng định tuyến tối đa là một đường tối ưu theo độ đo định tuyến sau mỗi tiến trình tìm đường mặc dù nút mạng có thể nhận được thông tin về nhiều con đường tới cùng một đích trong cùng một tiến trình tìm đường. Tại mỗi nút mạng, các gói tin được chuyển tiếp theo đường thích hợp có trong bảng định tuyến. Khi một liên kết trên đường đó bị lỗi, nút mạng này phải khởi tạo lại tiến trình tìm đường. Để tiết kiệm tài nguyên hệ thống mạng trong tiến trình tìm đường, giao thức định tuyến đa đường cho phép tìm và cài đặt nhiều hơn một con đường không giao nhau tới cùng một đích vào bảng định tuyến của chúng. Tại một nút, khi có yêu cầu chuyển tiếp dữ liệu tới nút đích, con đường tốt nhất sẽ được sử dụng và những con đường còn lại sẽ đóng vai trò là đường dự phòng. Khi đường chính bị lỗi, các đường dự phòng sẽ được sử dụng để chuyển tiếp các gói tin dữ liệu nếu chúng vẫn trong trạng thái còn hoạt động được. Thêm vào đó, nếu cơ chế cân bằng tải được sử dụng, có thể phân chia dữ liệu cần truyền thành nhiều luồng được truyền song song trên các con đường. Trong số các chiến lược định tuyến đã được trình bày ở trên, chiến lược định tuyến tìm đường trước (proactive) và định tuyến tìm đường theo yêu cầu (on-demand) được sử dụng rất rộng rãi. Với các giao thức sử dụng chiến lược định tuyến tìm đường trước kết hợp với cơ chế điều khiển dạng bảng, đường truyền dữ liệu giữa mọi cặp nút nguồn, đích trong mạng sẽ được khám phá trước khi có yêu cầu truyền dữ liệu. Tuy nhiên, do sự thay đổi ngẫu nhiên với tần suất lớn của các nút mạng trong mạng MANET nên chiến lược định tuyến này chỉ phù hợp với các mô hình mạng MANET tương đối tĩnh, cấu trúc mạng ít có sự thay đổi. Thêm vào đó, việc khám phá tất cả các đường đi giữa các cặp nút nguồn-đích bất kỳ trong mạng là không cần thiết và lãng phí vì có những con đường sẽ không được sử dụng. 2.2 Giao thức DSDV (Destination – Sequenced Distance – Vector) [1] Là một trong những giao thức đầu tiên được phát triển cho mạng Adhoc. DSDV là một biến thể của giao thức định tuyến distance vector theo kiểu chủ ứng (proactive), dựa trên ý tưởng của thuật toán định tuyến kinh điển Bellman– Ford với một chút cải tiến. Cải tiến mới của DSDV là sử dụng kỹ thuật đánh số thứ tự (sequence number). Kỹ thuật này dùng để nhận ra các con đường đi không còn giá trị trong 20 quá trình cập nhật bảng định tuyến, do đó, sẽ tránh được vòng lặp trong quá trình định tuyến. Mỗi nút sẽ tăng số sequence number khi gửi thông tin về bảng định tuyến của nó cho các nút khác trong mạng. Các cơ chế trong DSDV 2.2.1Quản lý bảng định tuyến Mỗi nút luôn duy trì một bảng định tuyến đến các nút khác trong mạng. Thông tin của mộtmục trong bảng định tuyến bao gồm:  Địa chỉ của nút đích  Số hop đến đích (hop – count)  Next hop  Số sequence number của nút đích. Để đảm bảo cho bảng định tuyến luôn luôn phù hợp với những thay đổi trong mạng thì các nút phải thường xuyên cập nhật bảng định tuyến theo một khoảng thời gian nhất định khi mạng có sự thay đổi. Do đó, các nút phải quảng bá thông tin định tuyến của nó cho các nút khác trong mạng bằng cách quảng bá (broadcast) những thay đổi trong bảng định tuyến của nó. Khi một nút nhận gói tin cập nhật bảng định tuyến, nó sẽ kiểm tra số sequence number trong gói tin được cập nhật, nếu số này lớn hơn hoặc bằng với sốsequence number trong bảng định tuyến và số có hopcount nhỏ hơn thì nút sẽ cập nhật thông tin đó vào bảng định tuyến. 2.2.2 Cập nhật bảng định tuyến trong DSDV Bảng định tuyến sẽ được cập nhật theo hai cách: Thứ nhất, cập nhật toàn bộ bảng định tuyến cho các nút láng giềng và có thể phải truyền trong nhiều packet, gọi là full-dump. Thứ hai, cập nhật các phần thay đổi trong bảng định tuyến của nó cho các nút láng giềng và thông tin thay đổi chỉ được gửi đi trong một packet, gọi là incremental – update. Đối với một mạng Adhoc tương đối ổn định, thì kiểu cập nhật incremental – update sẽ thường được sử dụng để hạn chế lưu lượng truyền trên mạng. Trong khi đó, full – dump sẽ được dùng trong những mạng thiếu ổn định. 21 2.2.3 Quản lý sự thay đổi của Topology Khi một nút di chuyển từ nơi này đến nơi khác thì các liên kết của nó với các nút láng giềng có thể không còn hiệu lực. Khi một nút phát hiện rằng liên kết đến chặng kế tiếp (next hop) của nó không còn tồn tại thì đường đi qua next hop đó lập tức sẽ có hop-count là ∞ và số sequence number được tăng lên 1. Sau đó nútsẽ phát broadcast thông tin đó cho tất cả các nút trong mạng và các nútsẽ cậpnhật lại bảng định tuyến của mình. Ưu điểm của DSDV là đảm bảo không có đường định tuyến kín (không có vòng lặp định tuyến) bằng cách sử dụng số thứ tự để đánh dấu mỗi đường. Số thứ tự cho biết mức độ “mới” của đường định tuyến, số càng lớn thì mức độ đảm bảo càng cao (đường R được coi là tốt hơn R’ nếu số thứ tự của R lớn hơn, trong trường hợp có cùng số thứ tự thì R phải có số bước nhỏ hơn). Số thứ tự sẽ tăng khi nút A phát hiện ra đường đến đích D đị phá vỡ, sau đó nút A quảng bá đường định tuyến của nó tới nút D với số bước không giới hạn và số thứ tự sẽ tăng lên. DSDV phụ thuộc vào thông tin quảng bá định kỳ nên nó sẽ tiêu tốn thời gian để tổng hợp thông tin trước khi đường định tuyến được đưa vào sử dụng. Thời gian này là không đáng kể đối với mạng có cấu trúc cố định nói chung (bao gồm cả mạng có dây), nhưng với mạng Adhoc thời gian này là đáng kể, có thể gây ra mất gói tin trước khi tìm ra được định tuyến hợp lý. Ngoài ra, bản tin quảng cáo định kỳ cũng là nguyên nhân gây ra lãng phí tài nguyên mạng, như băng thông, điện năng, thời gian xử lý... 2.3. Giao thức AODV [1] 2.3.1. Tổng quan về giao thức AODV Giao thức AODV sử dụng một cách tiếp cận hoàn toàn mới so với các phương pháp truyền thống để xây dựng các đường đi trong mạng. Khi một nút mạng muốn gửi một gói tin tới một nút nào đó, nó sẽ khởi tạo tiến trình xử lý phát hiện đường (discovery) để định vị nút đích. Nếu không có một đường đi nào được tìm thấy trong một khoảng thời gian xác định, nút khởi tạo sẽ cho rằng không tồn tại đường đi tới nút đích, tiến trình xử lý phát hiện đường (discovery) sẽ kết thúc đồng thời các gói tin tương ứng sẽ hủy bỏ. Ngược lại, nếu nútkhởi tạo tìm được một đường đi phù hợp, nó sẽ cập nhật đường đi này vào bảng định tuyến của nó như một đầu vào (entry) tương ứng với nút đích. 22 Khi một đầu vào mới được tạo ra, tiến trình xử lý việc duy trì (mainternance) tuyến cũng đồng thời được kích hoạt để giám sát tình trạng của đường đi vừa được tạo ra, nếu sau một khoảng thời gian đủ lớn mà đường đi không được sử dụng, nút mạng sẽ xóa đường đi này ra khỏi bảng định tuyến. Nếu có lỗi xuất hiện trên một đường đi có trạng thái tích cực, nút mạng phát hiện chặng có lỗi sẽ lập tức thông báo ngược lại cho nút lân cận ở phía đầu tuyến về chặng bị lỗi bằng một gói tin điều khiển cụ thể. Trong trường hợp nhận được gói thông báo lỗi trên, các nút mạng chịu ảnh hưởng sẽ khởi động lại tiến trình discovery để tìm đường đi thay thế nếu cần thiết. AODV quản lý các thông tin về đường đi theo kiểu phân tán. Điều này có nghĩa là mỗi nút trên đường đi sẽ có một thành phần trong bảng định tuyến tương ứng với nút đích của đường đi đó. Cách quản lý này hoàn toàn trái ngược với phương pháp source routing (tìm đường từ nút nguồn) trong đó chỉ có nút nguồn mới biết đường đi đầy đủ tới nút đích. AODV cũng cho phép mỗi nút chỉ duy trì một và chỉ một đường đi ứng với mỗi nút đích. Tuy nhiên có một số giao thức tìm đường khác cho phép tìm nhiều đường ứng với mỗi nút đích. Trong trường hợp đường đi ban đầu bị lỗi, đường đi thay thế sẽ được sử dụng Các thành phần của bảng định tuyến trong giao thức AODV được định dạng bao gồm các trường như sau: <địa chỉ nút đích, địa chỉ chặng tiếp theo, số thứ tự, khoảngcách, danh sách các nút trước đó (precursor), ngày hết hạn >. Trường số thứ tự được sử dụng để ngăn chặn sự hình thành các vòng lặp và thể hiện mức độ cập nhật của các đường đi. + Khoảng cách là số các bước truyền. Khi một đường đi mất hiệu lực, số thứ tự của nó sẽ tăng lên một và khoảng cách sẽ được đặt là vô cùng. Danh sách precursor chứa tập hợp các nút lân cận, sử dụng thành phần này để chuyển tiếp các gói dữ liệu. Thời gian hết hạn được sử dụng để xác định thời gian tồn tại tối đa của thành phần, sau hạn đó nó sẽ bị xóa bỏ khỏi bảng định tuyến. Tất nhiên giá trị của trường này sẽ được tăng lên mỗi lần thành phần này được sử dụng.[1] 2.3.2 Cơ chế hoạt động 2.3.2.1 Tiến trình Discovery 23 Tiến trình Discovery là một phương pháp kỹ thuật cho phép từng nút nguồn trong một mạng MANET có thể định vị (lấy được địa chỉ IP) một nút đích. Tất nhiên, một nút khởi động tiến trình Discovery chỉ khi nút đích chưa từng được định vị trước đó hoặc không có thành phần nào trong bảng định tuyến tương ứng với nút đích. Nếu đã có một thành phần tồn tại trong bảng định tuyến, gói tin sẽ lập tức được chuyển đi và bước thực hiện tiến trình Discovery được bỏ qua. Khi một nút khởi động cho tiến trình Discovery, nó phải gửi đi một gói tin yêu cầu tìm đường -RREQ (route request) tới tất cả các nút lân cận. Gói tin này được lan truyền tới tất cả các nút khác trong mạng khi một đường đi được xác định 2.3.2.2 Tạo Route Request: Hình 2.5: Quá trình lan truyền của gói tín RREQ Nếu một nút nguồn S muốn tìm một nút đích D trong mạng MANET, S sẽ thông báo cho tất cả các nút khác trong mạng biết nó đang tìm kiếm nút D bằng cách gửi đi gói tin RREQ tới tất cả các nút lân cận. RREQ chứa địa chỉ IP và số thứ tự của cả nguồn và đích. Số thứ tự đích tham chiếu đến số thứ tự của đường đi cuối cùng tới nút D mà nút S biết. Nếu nút nguồn S không dò được một số thứ tự nào của đường đi tới nút D thì số thứ tự đích được đặt mặc định bằng 0. Cấu trúc gói tin RREQ: <địa chỉ nguồn, thứ tự nguồn#, BROADCAST ID, địa chỉ đích, thứ tự đích#, hop-count> Mỗi nút trong mạng khi nhận được gói tin RREQ sẽ lập tức lan truyền tiếp tới các nút lân cận của nó cho đến khi gói tin RREQ tới được nút D hoặc 24 một nút nào đó biết một đường đi đầy đủ và cập nhật tới nút D ( dựa vào số thứ tự đích trong gói tin RREQ). Gói tin RREQ còn chứa hai trường khác là TTL (TIME TO LIVE) và BROADCAST ID. Trường TTL cho phép tiến trình Discovery điều khiển mức độ lantruyền của gói tin RREQ trong mạng. Lấy ví dụ như một gói tin RREQ có trường TTL được đặt bằng 2 sẽ thực hiện nhiều nhất 2 bước truyền tính từ nút gốc. Khi gói tin RREQ truyền đi, nút nguồn sẽ đặt giá trị cho trường TTL và chuyển vào trạng thái chờ. Khoảng thời gian chờ của nút gốc tương ứng với giá trị của trường TTL gói tin RREQ. Nếu không có gì thay đổi, một đường đi được tìm thấy trước khi thời gian chờ kết thúc thì tiến trình khám phá tuyến đường (Discovery) kết thúc thành công. Ngược lại, nếu trong khoảng thời gian chờ của nút nguồn nó không nhận được một gói tin trả lời nào, nút nguồn sẽ gửi lại một gói tin RREQ mới và tiếp tục chờ đợi. Tất nhiên gói tin mới sẽ cần có giá trị của trường TTL lớn hơn và thời gian chờ đợi cũng kéo dài hơn vì thế gói tin RREQ sẽ lan truyền đến được nhiều nút mạng hơn. Nếu vẫn không nhận được trả lời, nút nguồn sẽ gửi tiếp một gói tin RREQ với giá trị tối đa của trường TTL. Sau lần này, tiến trình Discovery sẽ bị hủy bỏ. Kỹ thuật này còn được gọi là kỹ thuật mở rộng dần vòng tìm kiếm. Ngoài ra mỗi gói tin RREQ còn được gán một số thứ tự được gọi là BROADCAST ID. Trường này được dùng cho các nút mạng phân biệt các gói tin nhận được có phải xuất phát từ cùng một nút hay không và nó được nút gửi RREQ tăng lên sau mỗi lần truyền đi. Một cặp là duy nhất cho mỗi gói tin RREQ và các gói tin có giá trị của BROADCAST ID lớn hơn thì mới hơn. Khi một nút nhận được một gói tin RREQ nó sẽ ghi nhớ giá trị của trường BROADCAST ID. Sau đó nếu nút đó tiếp tục nhận được các gói tin RREQ từ cùng một nút nguồn thì chỉ những gói tin có giá trị BROADCAST ID lớn hơn mà nó đã ghi nhớ mới được tiến hành xử lý. Các gói tin có giá trị nhỏ hơn sẽ bị hủy bỏ Trong mỗi gói tin RREQ còn có trường hop-count được dùng để ghi số bước truyền mà gói tin đã được truyền qua. 2.3.2.3 Chuyển tiếp Route Request 25 Giả sử trường hợp một nút I nhận được một gói tin RREQ xuất phát từ nút nguồn S, yêu cầu tìm đường tới nút đích D. Đầu tiên nút I sẽ kiểm tra giá trị của trường BROADCAST ID nhỏ hơn hoặc bằng giá trị mà nút đã ghi nhớ trước đó, nếu giá trị này nhỏ hơn, gói tin RREQ sẽ bị hủy bỏ. Trong trường hợp ngược lại, nút I sẽ xử lý gói tin RREQ. Trước hết nó sẽ tạo hoặc cập nhật lại đường đi ngược tới nút S (hình 2.6). Đường đi này được sử dụng để chuyển thông báo trả lời - Route Reply trở lại nút S trong trường hợp đường đi tới nút D được tìm thấy. Sau khi một đường đi ngược được tạo ra, nút I sẽ kiểm tra xem nó có biết một đường đi đầy đủ và cập nhật tới nút D hay không. Nếu có nút I sẽ tạo ra một gói tin trả lời (route reply packet) và gửi ngược lại theo đường đi ngược vừa tạo ra. Khi đó gói tin RREQ không cần phải tiếp tục phát quảng bá đi nữa. Trong trường hợp ngược lại, nếu không biết một đường đi tới nút D, nút I sẽ tiếp tục lan truyền gói tin RREQ. Trường TTL trong gói tin RREQ sẽ bị giảm đi một, và nếu nó bằng 0, việc lan truyền sẽ chấm dứt. Nếu vẫn tiếp tục được lan truyền, trường hop-count trong gói tin sẽ được tăng lên một. Hình 2.6: Đường đi ngược được tạo ra khi RREQ lan truyền trong môi trường 2.3.2.4 Tạo Route Reply Khi một nút mạng biết một đường đi đầy đủ và cập nhật (hoặc nó chính là nút đích hoặc bảng định tuyến của nó có một thành phần tương ứng với nút đích), nó sẽ tạo một gói tin trả lời RREP gửi ngược lại tới nút nguồn. Gói tin RREP sẽ chứa địa chỉ IP của cả nút nguồn và nút đích và số thứ tự của đường đi vừa tìm được. Gói tin này cũng có trường count và trường lifetime (thời gian sống) chứa giá trị tương ứng với thời gian có hiệu lực của đường đi (nếu sau khoảng thời gian đó đường đi không được sử dụng nó sẽ bị xóa). 2.3.2.5 Chuyển tiếp Route Relay 26 Như trong hình, đường đi từ nút nguồn tới nút đích (forward path) được tạo ra khi gói tin trả lời RREP được truyền đi ngược từ nút đích về nút nguồn. Mỗi nút nhận được gói tin RREP sẽ tạo ra trong bảng định tuyến của mình một thành phần tương ứng với nút đích D. Hai trường số thứ tự và khoảng cách trong thành phần mới tạo ra sẽ nhận giá trị của số thứ tự đích và trường count trong gói tin RREP.Chặng tiếp theo là nút cuối cùng vừa chuyển tiếp gói tin RREP. Hình 2.7: Đường đi từ nút nguồn và nút đích được hình thành. Nếu gói tin RREP tới được nút nguồn S, nút S sẽ tạo một mục trong bảng định tuyến tương ứng với nút đích D và tự động hủy bỏ gói tin RREQ. Tiến trìnhDiscovery cũng kết thúc và một đường đi mới được thiết lập. [1] 2.3.3 Quản lý cục bộ Khi một đường đi tới nút đích được hình thành, mỗi nút mạng có thể sử dụng một số kỹ thuật để giám sát trạng thái của đường đi đó. Nói một cách khác mỗi nút nằm trên đường đi sẽ cố gắng đảm bảo bước truyền tiếp theo trên đường đi luôn trong trạng thái sẵn sàng. Nếu bước truyền tiếp theo ở trạng thái tích cực thì đường đi tương ứng vẫn có giá trị. Trong trường hợp ngược lại, nút hiện thời phải lập tức thông báo cho các nút nằm trước nó trên đường đi. Quá trình giám sát tình trạng các tuyến trong mạng có thể được thực hiện theo hai phương pháp khác nhau: Proactive hoặc Reactive. Đối với phương pháp Proactive, nó sẽ sử dụng một số kiểu hoạt động dự phòng. Mỗi nút mạng sẽ liên tục giám sát trạng thái thực tế của các nút lân cận bằng cách cập nhật bản đồ kết nối cục bộ (local connective map). 27 Bất cứ khi nào nhận được một gói tin thông báo (broadcast packet) gửi đến, nút hiện thời sẽ tiến hành cập nhật hoặc tạo mới thành phần trong bảng định tuyến tương ứng với nút gửi thông báo. Thành phần này có thời gian sống – lifetime ngắn, tương ứng với khoảngcách thời gian lớn nhất mà một nút lân cận được cho phép giữ im lặng trước khi nút hiện thời cho rằng nút này đã mất giá trị. Do đó, khi một nút lân cận vẫn ở trạng thái tích cực, thành phần tương ứng với nó trong bảng định tuyến của nút hiện thời vẫn có giá trị. Trong trường hợp lifetime hết hạn mà không có thông báo mới, nút hiện thời sẽ cho rằng liên kết đã bị phá vỡ và thủ tục thông báo lỗi liên kết (link failurenotification procedure) lập tức được gọi. Tuy nhiên tình trạng ''im lặng'' của một nútcó thể không phản ánh đúng trạng thái hiện tại của nó, do đó để đảm bảo tính chínhxác, AODV còn sử dụng thêm một bản tin (message) ''hello''. Khi không nhận được các gói tin thông báo trạng thái của các liên kết, nút hiện thời sẽ gửi message ''hello'' đến các nút lân cận để kiểm tra tình trạng thật sự của các nút đó. Phương pháp giám sát thứ hai được gọi là phương pháp Reactive. Theo phương pháp này các liên kết bị phá vỡ chỉ bị phát hiện khi có việc truyền dữ liệu. Trong trường hợp này, lỗi liên kết được phát hiện muộn, điều này không phù hợp với mục đích của mạng MANET bởi nó rất dễ gây ra tình trạng quá tải cho mạng. [1] 2.3.4 Duy trì đường đi Khi một lỗi kết nối được phát hiện, các nút mạng sẽlan truyền ngược gói tin báo lỗi RERR (Route Error). Gói tin RERR chứa danh sách các nút đích bị mất và số thứ tựtương ứng của chúng được tăng lên một. Khi nhận được một gói tin RERR, các nút chịu ảnh hưởng sẽ cập nhật lại bảng định tuyến của nó. Đối với mỗi nút đích trong gói tin RERR, nút hiện thời sẽ đặt lại giá trị cho trường khoảng cách thành vô cùng và cập nhật trường số thứ tự bằng cách sao chép số thứ tự của các nút tương ứng trong gói tin RERR. Ngoài ra, nếu trường precursor của nút hiện thời chưa rỗng, gói tin RERR sẽ tiếp tục được truyền ngược lại. Chú ý rằng các nút sẽ chỉ cập nhật lại bảng định tuyến nếu gói tin RERR mà nónhận được xuất phát từ bước truyền tiếp theo của nó trên đường đi tới nút đích. Ví dụ như trong hình 2.8, nút 1' nhận được gói tin RERR thông báo đương đi tới nút D bị lỗi. Nhưng nút 1' sẽ không cập nhật lại bảng định tuyến của nó 28 (thực tế đường đi từ 1' 26 đếnD không có sự cố ) vì gói tin RERR đó được gửi từ nút 2, mà nút 2 không phải là bướctruyền tiếp theo của nút 1' trên đường đi tới nút D. Do đó ở nút 1', gói tin RERR sẽ bị hủy bỏ. [1] Hình 2.8: Lan truyền gói tin RERR 2.3.5 Thời gian hết hạn và việc hủy bỏ một đường đi Trong mô hình AODV nếu một đường đi có trạng thái tích cực không được sử dụng sau một thời gian nhất định nó sẽ bị hủy bỏ. Do đó nếu một đường đi có trạng thái tích cực không được sử dụng trong thời gian cho phép ACTIVE_ROUTE_TIMEOUT thì nút hiện tại sẽ hủy bỏ bằng cách tăng số thứ tự của đường đi và thiết lập giá trị của trường count lên thành vô cùng. Tuy nhiên thành phần tương ứng với đường đi đó trong bảng định tuyến không bị xóa bỏ hẳn khỏi bảng định tuyến, nó chỉ được đánh dấu hết hạn sử dụng. Trên thực tế, thành phần này vẫn tồn tại trong bảng thêm một khoảng thời gian DELETE_PERIOD trước khi bị xóa hoàn toàn. Lý do đằng sau của việc có thêm một khoảng thời gian DELETE_PERIOD là để cho nút mạng có thể giữ được số thứ tự của đường đi đó mức lâu nhất có thể. [1] 29 CHƯƠNG 3. SỬ DỤNG THUẬT TOÁN BẦY KIẾN TRONG TỐI ƯU ĐỊNH TUYẾN MẠNG MANET 3.1. Giới thiệu Mạng adhoc không dây (MANET) là một tập hợp các nút di động không dây, có khả năng tự tổ chức một mạng tạm thời tùy ý. Các nút di động này có khả năng giao tiếp với nhau mà không yêu cầu hạ tầng truyền thông cố định. Mạng MANET có thể được thiết lập nhanh chóng để truyền thông trong các trường hợp khẩn cấp. Nhưng trong MANET, vấn đề định tuyến rất phức tạp do rất nhiều đặc điểm như mô hình mạng thay đổi liên tục, chất lượng dịch vụ (QOS – Quality of Service) thay đổi theo thời điểm, tài nguyên năng lượng có hạn Định tuyến trong MANET vốn đã là một vấn đề được nghiên cứu từ lâu vì MANET là một tập hợp các nút di động có thể liên lạc qua sóng radio. Loại mạng này hết sức linh hoạt, vì thế chúng không cần một hệ thống cơ sở hạ tầng hay quản lý tập trung nào. Từ lý do đó, mạng MANET rất phù hợp cho các kết nối truyền thông tạm thời. Thách thức lớn nhất trong loại mạng này là tìm đường giữa các điểm đầu cuối truyền thông, mà lý do chính là khả năng di động của các nút. Giao thức định tuyến trong mạng dây truyền thống chỉ có thể sử dụng trong điều kiện đảm bảo sức mạng tính toán và băng thông cần thiết để có thể thực hiện việc phát quảng bá trạng thái hay các thuật toán AI yêu cầu xử lý nhiều để tối ưu hóa các vấn đề liên quan tới QOS, định tuyến đảm bảo QOS trở thành một thách thức thực sự trong mạng MANET, vì các nút phải liên tục cập nhật các thông tin về trạng thái kết nối. Và cũng vì bản chất linh hoạt của mạng MANET, duy trì các thông tin về trạng thái kết nối này chính xác là rất khó khăn. Việc định tuyến trong các mạng là rất cần thiết vì các nút mạng không luôn được kết nối trực tiếp. Việc của các giao thức định tuyến chính là điều hướng luồng lưu lượng từ nguồn đến được đích, nhưng ngày nay, vì sự phức tạp trong các mạng hiện đại, các giao thức định tuyến đều gặp phải những thách thức nhất định. Các giao thức định tuyến càng gặp nhiều khó khăn hơn khi mà cấu trúc mạng liên tục thay đổi và tài nguyên mạng thì có giới hạn. Điều này càng đúng trong mạng không dây khi sự di động của các nút và các liên kết thất bại tạo ra các thay đổi liên tục trong cấu trúc mạng. Các giao thức định tuyến thiếu khả năng thích nghi với sự thay đổi cấu trúc liên tục, tài nguyên có hạn và 30 năng lượng có hạn sẽ làm giảm khả năng hoạt động của mạng nói chung. Yêu cầu thực tế về QOS đã liên tục tăng khi Internet liên tục mở rộng. Định tuyến đảm bảo QOS là các kỹ thuật định tuyến mà nhờ đó các tuyến đường được định ra dựa trên khả năng của tài nguyên trong mạng cũng như các yêu cầu về QOS của hệ thống. Mục đích chính của kỹ thuật này là: xác định các tuyến đường có thể di chuyển được với các ràng