Đề tài Tối ưu giao thức AODV-EERS trong mạng Ad-hoc

mong chờ có sự liên lạc hai chiều với node đích. Trong trường hợp này, nếu node nguồn có đường đi tới node đích không thôi là không đủ, node đích cũng phải có đường đi quay lại node nguồn. Để thực hiện được điều này, các node trung gian khi nhận được các bản tin RREQ, RREP, RERR, chúng đều thực hiện lưu thông tin để tạo đường ngược về các node khởi tạo bản tin này. Một node không thực hiện khởi tạo nhiều hơn RREQ_RATELIMIT bản tin RREQ trong 1 giây. Sau khi phát quảng bá 1 bản tin RREQ, node đó sẽ đợi bản tin hồi đáp RREP (hoặc các bản tin điều khiển khác chứa thông tin về về tuyến đường tới node đích đang được tìm kiếm). nếu tuyến đường không nhận trong khoảng thời gian NET_TRAVERSAL_TIME mili giây, node đó có thể tiếp tục phát quảng bá bản tin yêu cầu RREQ để tìm đường, số lần gửi yêu cầu lại không vượt quá RREQ_RETRIES lần. Và với mỗi lần phát lại này, node phải tăng số RREQ ID lên trong 1 trong các bản tin RREQ của mình. Các gói tin dữ liệu sẽ chờ cho tuyến đường được khởi tạo thành công (đợi bản tin RREP sau khi bản tin yêu cầu RREQ được gửi đi) và được lưu vào bộ đệm. Việc lưu vào bộ đệm này tuân theo quy tắc “vào trước ra trước” (First in, first out – FIFO). Nếu quá trình tìm đường đã được thực hiện RREQ_RETRIES lần mà không nhận được bất cứ bản tin RREP nào , tất cả bản tin dữ liệu gửi đến node đích này đều bị drop khỏi hàng đợi và bản tin không tìm thấy node yêu cầu (Destination Unreachable message) sẽ được gửi cho chương trình ở lớp cao hơn. Một node nhận được bản tin RREQ, sẽ thực hiện gửi lại bản tin RREP khi : Nó chính là node đích được chỉ ra trong bản tin RREQ Nó biết đường đi tới node đích được chỉ ra trong bản tin RREQ, số sequence đích trong bảng định tuyến cho node đích này là khả dụng và lớn hơn hoặc bằng số sequence đích trong bản tin RREQ. Bản tin RREP sẽ được truyền đơn hướng về node đầu tiên khởi tạo bản tin RREQ. Tuyến đường sẽ được tạo dựa trên các bảng định tuyến tại các node mà bản tin RREP đi qua. Các bản ghi về node nguồn đầu tiên khởi tạo bản ghi RREQ này đã được tạo ra do các node trung gian tạo đường ngược về node nguồn mỗi khi nhận được bản tin RREQ. Trường Hopcount sẽ tăng lên qua mỗi node, bởi vậy khi bản tin RREP đến được node nguồn, giá trị của trường Hopcount trong bản tin RREP sẽ biểu diễn chiều dài của tuyến đường (theo số node) từ node nguồn đến node đích. Để dễ hiểu, em có thể biểu diễn phương thức AODV thực hiện khởi tạo kết nối bằng cách biểu diễn dưới dạng thuật toán như sau: //S là node nguồn, D là node đích //RT= bảng định tuyến //S muốn kết nối với D If (RT của S có đường đi khả dụng tới D) S sẽ thiết lập kết nối tới D Else S tạo bản tin yêu cầu RREQ và phát quảng bá nó đến các hàng xóm của mình For ( tất cả các node nhận được bản tin RREQ) If (RREQ này đã xử lý từ trước) Bỏ đi bản tin RREQ bị trùng End if If ( nó là D) Gửi bản tin RREP tới node ban đầu gửi đi bản tin RREQ này Else if (N có một tuyến đường tới D với SeqId >= RREQ.Seq) Gửi bản tin RREP Else Lưu lại thông tin node gửi bản tin RREQ này Phát quảng bá bản tin RREQ End if End for S nhận được bản tin RREP S cập nhật RT của nó dựa trên node gửi bản tin RREP S thiết lập kết nối với D End if Sau đây là ví dụ mô tả cách thức tìm đường của giao thức AODV Hình 3.1: Ví dụ bản tin RREQ phần 1 Node S là node nguồn. Các node trong mạng sử dụng giao thức AODV là giao thức định tuyến. Tại thời điểm ban đầu, node S muốn tìm đường đến node D Hình 3.2: Ví dụ bản tin RREQ phần 2 Node S bắt đầu phát quảng bá bản tin RREQ. Node B,C,E nhận được bản tin RREQ. Hình 3.3: Ví dụ bản tin RREQ phần 3 Node B,C,E thấy mình không phải là node đích và cũng không có đường đi khả dụng nào đến node đích trong bảng định tuyến, node B,C,E thực hiện chuyển tiếp bản tin RREQ đó. Trước khi chuyển tiếp, nó thực hiện lưu thông tin bản tin RREQ để tạo đường ngược về node nguồn. Hình 3.4: Ví dụ bản tin RREQ phần 4 Quá trình tiếp tục được thực hiện với node A,H,G,F. Node C nhận được bản tin RREQ từ G và H, nhưng nó không thực hiện chuyển tiếp bản tin này vì node C đã chuyển tiếp bản tin RREQ này một lần. Hình 3.5: Ví dụ bản tin RREQ phần 5 Hình 3.6: Ví dụ bản tin RREQ phần 6 Node D không chuyển tiếp bản tin RREQ nữa, vì node D chính là node được yêu cầu của bản tin RREQ. Hình 3.7: Ví dụ bản tin RREQ phần 7 Node D thực hiện gửi bản tin RREP về node nguồn. Sau khi node S nhận được bản tin RREP, nó sẽ thực hiện gửi các bản tin mang dữ liệu được lưu trong bộ nhớ đệm. 3.3.3 Duy trì kết nối Mỗi node đều phải liên tục theo dõi các kết nối đang được sử dụng bằng cách giữ liên kết với các node tiếp theo trong tuyến đường đi. Một số cách được AODV sử dụng để giữ liên kết với các node kế tiếp được nêu ra ở dưới đây: Nếu có thể sử dụng các báo hiệu ở lớp liên kết, như là các báo hiệu được đưa ra trong chuẩn IEEE 802.11, AODV sẽ sử dụng chúng để kiểm tra trạng thái của liên kết. Mỗi khi có một bản tin được truyền đến một node kế tiếp, node đó sẽ đợi bản tin ACK ở lớp liên kết. Nếu sau một số lần cho phép mà việc truyền lại đều không thành công, điều đó sẽ chỉ răng liên kết với node tiếp theo đã bị gãy. Để giữ liên kết với node kế tiếp, AODV còn sử dụng một bản tin đó là bản tin hello.Một node chỉ thực hiện phát quảng bá bản tin hello nếu nó đang nằm trong một tuyến đường đang được sử dụng để truyền tin. Cứ sau một khoảng thời gian là HELLO_INTERVAL mili giây, node đó sẽ kiểm tra xem nó đã phát quảng bá một bản tin nào chưa (bản tin RREQ hoặc một bản tin lớp 2 thích hợp). Nếu nó chưa, nó sẽ thực hiện phát quảng bá một bản tin HELLO (chính là bản tin RREP với trường TTL = 1, được gọi là bản tin HELLO). Các trường của bản tin Hello bao gồm: Destination IP address: địa chỉ IP của node đó Destination Sequence Number: số sequence hiện tại của node đó. Hop count: 0 Lifetime: thời gian sống = ALLOWED_HELLO_LOSS * HELLO_INTERVAL Một node sẽ xác định trạng thái của liên kết bằng cách lắng nghe bản tin HELLO từ các node lân cận. Nếu trong khoảng thời gian ALLOWED_HELLO_LOSS * HELLO_INTERVAL mili giấy, nó không nhận được bản tin nào từ hàng xóm (bản tin Hello hoặc các bản tin khác), liên kết đó sẽ được coi là bị gãy, node sẽ thực hiện kiểm tra điều kiện xem có thể thực hiện sửa cục bộ. Nếu điều kiện thỏa mãn, node sẽ thực hiện sửa cục bộ, còn nếu không, nó sẽ thực hiện gửi bản tin RERR về node nguồn để báo cho node nguồn thực hiện định tuyến lại. Bất cứ khi nào node nhận được một bản tin Hello từ hàng xóm, node sẽ kiểm tra xem nó có tuyến đường nào đang được sử dụng mà node gửi bản tin Hello đóng vai trò là node kế tiếp hay không, nếu không nó có thể tạo một bản ghi mới nếu cần thiết. Nếu thực sự có tuyến đường sử dụng node hàng xóm đó làm node kế tiếp, nó sẽ thực hiện tăng giá trị của trường thời gian sống (lifetime) trong bảng định tuyến. Những bản ghi trong bảng định tuyến được tạo bởi việc gửi nhận bản tin hello mà không được dùng đến thì khi trường thời gian sống (lifetime) hết hạn, tức là node hàng xóm đã di chuyển ra khỏi vùng phủ sóng hay gặp trục trặc thì node đó sẽ xóa bản ghi đó mà không thực hiện gửi bản tin RERR nào cả. 3.3.4 Xử lý khi có lỗi xảy ra Thông thường, việc xử lý lỗi đường hoặc gãy kết nối đòi hỏi phải thực hiện các bước sau: Đánh dấu tuyến đường bị lỗi. Liệt kê các node đích bị ảnh hưởng Xác định nếu có những node hàng xóm có thể bị ảnh hưởng Gửi bản tin RERR phù hợp tới những node hàng xóm này Bản tin lỗi RERR có thể được phát quảng bá (nếu có nhiều node bị ảnh hưởng), phát đơn hướng (nếu chỉ có 1 node bị ảnh hưởng), hoặc là phát đơn hướng lặp lại (nếu việc phát quảng bá là không phù hợp). Một node sẽ không thực hiện tạo nhiều hơn RERR_RATELIMIT bản tin RERR trong 1 giây. Một node khởi tạo bản tin RERR trong 3 trường hợp sau: Nếu nó phát hiện kết nối bị gãy tới node tiếp theo trong một tuyến đường đang được sử dụng trong bảng định tuyến của nó khi đang thực hiện truyền dữ liệu (và các biện pháp sửa chữa không đạt được thành công) Nếu nó nhận được một bản tin mang dữ liệu đến một node mà nó không có một tuyến đường đi khả dụng nào hay đang phải thực hiện sửa chữa (sửa chữa cục bộ) đến node đó. Nếu nó nhận được bản tin RERR từ node hàng xóm về 1 hoặc nhiều tuyến đường mà nó đang sử dụng. Trong trường hợp 1, đầu tiên, node sẽ đưa ra một danh sách các node bị lỗi bao gồm node hàng xóm bị mất kết nối và các node đích bị ảnh hưởng từ bảng định tuyến của nó mà sử dụng node bị mất kết nối đó là node tiếp theo trong tuyến đường. Trong trường hợp 2, chỉ có duy nhất một node đích bị mất kết nối, đó chính là node có địa chỉ là địa chỉ đích của bản tin mang dữ liệu không thể gửi được đó. Trong trường hợp 3, danh sách các node mất kết nối chính là danh các node trong trường Unreachable Destination Ip address. Khi node nhận được bản tin RERR này, nó sẽ tra trong bảng định tuyến của nó để tìm ra node tiếp theo thích hợp để chuyển tiếp bản tin RERR này. Hình 3.8: Ví dụ bản tin RERR phần 1 S là node nguồn. S thực hiện gửi bản tin RREQ để tìm đường đến node D Hình 3.9: Ví dụ bản tin RERR phần 2 D nhận được bản tin RREQ. Node D thực hiện gửi bản tin RREP lại về node nguồn là node S Hình 3.10: Ví dụ bản tin RERR phần 3 Node S sau khi nhận được bản tin RREP của node D, nó thực hiện gửi các bản tin dữ liệu được lưu ở bộ nhớ đệm tới node D. Hình 3.11: Ví dụ bản tin RERR phần 4 Node D ra khỏi vùng phủ sóng của node đằng trước. Hình 3.12: Ví dụ bản tin RERR phần 5 Node kế trước node D nhận ra liên kết tới node D đã bị gãy. Nó thực hiện gửi bản tin RERR về node nguồn S 3.3.5 Sửa cục bộ Khi một liên kết bị gãy trong 1 tuyến đường đang được sử dụng xảy ra, node đầu tiên trong tuyến đường từ chỗ đứt gẫy hướng về phía nguồn phát sẽ thực hiện sửa cục bộ nếu chiều dài đoạn đường từ node đó đến node nguồn lớn hơn chiều dài từ node đó đến node đích. Do quá trình sửa cục bộ này có thể làm tuyến đường cần sửa dài ra hơn cần thiết, bởi vậy với điều kiện giới hạn số node có thể thực hiện được sửa cục bộ, giao thức có thể hạn chế được số bản tin cần gửi và qua đó có thể tiết kiệm được năng lượng và giảm độ trễ. Để sửa kết nối bị gãy, node sẽ tăng số sequence của node đích cần tìm kiếm lên 1 và sau đó sẽ phát quảng bá bản tin yêu cầu RREQ về node này. Trường TTL của bản tin RREQ sẽ được gán giá trị bằng thời gian trường TTL của node bị mất kết nối đó trong bảng định tuyến. Node thực hiện sửa cục bộ sẽ chờ bản tin hồi đáp RREP cho bản tin RREQ này để thực hiện sửa kết nối. Trong quá trình sửa cục bộ này, các bản tin mang dữ liệu sẽ được lưu vào bộ nhớ đệm. Nếu đến hết thời gian sửa mà node thực hiện sửa không nhận được bản tin RREP nào về node đích bị mất kết nối này, nó sẽ thực hiện gửi bản tin RERR như được trình bày ở mục 1.3.3.4. Mặt khác, nếu node thực hiện sửa nhận được một hoặc nhiều bản tin RREP trong quá trình sửa, node sẽ thực hiện cập nhật lại bảng định tuyến của mình và tiếp tục thực hiện tiếp việc truyền dữ liệu đến node đích Hình 3.13: Ví dụ quá trình sửa cục bộ phần 1 Tuyến đường từ node S đến node D đi qua node 2 và node 5. Hình 3.14: Ví dụ quá trình sửa cục bộ phần 2 Node D ra khỏi vùng phủ sóng của node 5. Node 5 phát hiện liên kết với node D bị gãy Hình 3.15: Ví dụ quá trình sửa cục bộ phần 3 Node 5 kiểm tra điều kiện sửa cục bộ thấy thỏa mãn, nó thực hiện quá trình sửa cục bộ bằng cách quảng bá bản tin RREQ tới node D Hình 3.15: Ví dụ quá trình sửa cục bộ phần 4 Node 1,6,7 nhận được bản tin RREQ và thực hiện chuyển tiếp bản tin RREQ này đi. Trong thời gian này, node S tiếp tục gửi dữ liệu tới node D. Dữ liệu đến node 5 được lưu vào bộ nhớ đệm đới quá trình sửa cục bộ kết thúc Hình 3.16: Ví dụ quá trình sửa cục bộ phần 5 Node D nhận được bản tin RREQ, nó thực hiện gửi bản tin RREP về node 5 Hình 3.17: Ví dụ quá trình sửa cục bộ phần 6 Node 5 nhận được bản tin RREP từ node D. Nó thực hiện cập nhật lại bảng định tuyến của mình và bắt đầu gửi các bản tin dữ liệu được lưu trong bộ nhớ đệm. CHƯƠNG 4: GIAO THỨC ĐỊNH TUYẾN AODV-ERS, AODV-EERS. Các giao thức luôn được nghiên cứu phát triền nhằm đạt hiệu quả tốt hơn trong hoạt động. Giao thức AODV nêu ở chương 3 cũng đã có nhiều phiên bản phát triển. Trong phạm vi đồ án này chúng em xin trình bày hai phiên bản AODV-ERS và AODV-EERS. 4.1 Giao thức định tuyến AODV-ERS Giao thức định tuyến AODV-ERS (Expanding Ring Search) là bước cải tiến đầu tiên của thuật toán AODV gốc.Như ở phần trên ta đã biết cơ chế tìm đường của AODV gốc là truyền bản tin RREQ ra toàn mạng.Điều này dẫn đến tiêu hao năng lượng đáng kể trong mạng.Trước vấn đề đó ERS ra đời nhằm cải thiện năng lượng các node trong mạng 4.1.1 Nguyên tắc định tuyến Điểm mấu chốt của thuật toán AODV-ERS là việc sử dụng trường TTL( Time To Live) trong tìm đường.Trường TTL xác định số node tối đa mà bản tin RREQ có thể truyền qua.Khi các node bắt đầu hoạt động, trường TTL sẽ được khởi tạo giá trị N.Sau đó bản tin RREQ sẽ được quảng bá với bán kính N node.Nếu không có tuyến đường nào đến node đích thì giá trị N này sẽ được tăng lên thêm K và bản tin tiếp tục quảng bá lại với bán kính mới là (N +K) , quá trình này sẽ dừng cho đến khi TTL tăng đến giá trị ngưỡng và không tìm thấy đường đến đích.Trong trường hợp giá trị TTL được khởi tạo vô hạn thì bản tin RREQ sẽ quảng bá toàn mạng giống như AODV gốc. Hình 4.1: Quá trình tìm đường trong AODV-ERS Giả sử node S muốn gửi bản tin đến node D.Nó sẽ tìm đường đến node D bằng cách sử dụng thuật toán ERS. Đầu tiên, node S sẽ quảng bá bản tin RREQ với TTL được khởi tạo N,để đơn giản thường N=1. Điều đó có nghĩa là bán kính tìm kiếm sẽ là một node hàng xóm.Bởi vì node D không ở trong vòng tìm kiếm đầu tiên này nên các node trong vòng không có thông tin gì về node D, do vậy chưa xác định được đường đến node D.Trong kịch bản này ta lấy K= 2 vì vậy node S sẽ tiếp tục quảng bá bản tin RREQ với bán kinh là 3 node.Bán kính cứ tiếp tục tăng cho đến khi tìm được node D và đến một lúc đó TTL sẽ tiến đến giá trị giới hạn và khi đó bản tin RREQ sẽ quảng bá toàn mạng.Node D sẽ nhận bản tin RREQ và gửi trả lại node S bản tin RREP đồng thời đánh dấu tuyến đường từ node S đến node D. Dưới đấy sẽ là lưu đồ thuật toán tìm đường của node nguồn và node trung gian trong ERS. Quá trình xử lý tìm đường tại node nguồn. Trong bước đầu tiên, node nguồn sẽ phát ra bản tin RREQ với TTL = N và tạo T = t + Tc. Giá trị t biểu thị thời gian thực của mạng và Tc là chu kỳ thời gian mà node nguồn đợi nhận bản tin RREP trước khi tiếp tục quảng bá bản tin RREQ. Nếu node nguồn nhận bản tin RREP trong thời gian này,quá trình tìm kiếm sẽ thành công và node nguồn bắt đầu gửi dữ liệu ra mạng.Trong trường hợp khác,node nguồn sẽ tăng giá trị TTL thêm K và đặt T=t+Tc. Khi mà giá trị TTL này lớn hơn giá trị ngưỡng thì giá trị TTL này sẽ thiết lập thành giá trị giới hạn và khi đó bản tin RREQ sẽ quảng bá toàn mạng. Hình 4.2: Quá trình xử lý thông tin tại node nguồn Quá trình xử lý tìm đường tại node trung gian Hình 4.3: Quá trình xử lý thông tin tại node trung gian Khi một node trung gian nhận bản tin RREQ, nó sẽ tìm kiếm thông tin trong bộ đệm của nó