Luận văn Nghiên cứu các giao thức định tuyến điều khiển theo yêu cầu trên mạng manet

-Ford. Thuật toán Bellmen-Ford thường được áp dụng trong giao thức định tuyến tĩnh RIP để xây dựng bảng định tuyến. Thuật toán này cũng tương tự như thuật toán Dijlkstra nhưng nó không áp dụng phương pháp tham lam trong việc chọn ra đỉnh v có trọng nhỏ nhất lân cận với đỉnh u đang xét. Thuật toán Bellman Ford tính toán đường đi ngắn nhất từ nguồn tới đích được mô tả như sau: Input: Đồ thị (G, w, s); Bellman-Ford-More(G, w, s) Bước 1: Khởi tạo nút nguồn s Bước 2: for i = 1 to V[G] –1 do for mỗi cạnh (u, v) Î E[G] do if d( v) > d(u) + w then {d(u), d(v) là chi phí được tính từ nút gốc đến các đỉnh u, v} d(v) : = d(u) + w; Bước 3: for mỗi cạnh (u,v) Î E[G] do if d[u] + w(u, v) < d[v] then return False; else return True; Output: Cây đường đi ngắn nhất từ nút s đến các nút khác, kết quả hàm là true nếu không có đỉnh nào mà đường đi đến nó có giá trị lớn hơn tổng đường đi đến nút kề đứng trước nó với trọng số trên cạnh nối hai đỉnh u và v, ngược lại hàm trả về giá trị là false. Sử dụng các giao thức định tuyến theo vectơ khoảng cách thường tốn ít tài nguyên của hệ thống. Tuy nhiên, tốc độ đồng bộ giữa các router lại chậm và thông số được sử dụng để chọn đường đi có thể không phù hợp với những hệ thống mạng lớn. Thuật toán trạng thái kết nối (Link State): Trạng thái liên kết là một mô tả đặc điểm các mối liên kết từ bộ định này tới các bộ định tuyến lân cận. Các đặc điểm này bao gồm: địa chỉ IP, mặt nạ, kiểu mạng kết nối, và các bộ định tuyến kết nối mạng đó. Giao thức định tuyến trạng thái liên kết được thực hiện dựa trên các bản tin thông báo trạng thái liên kết (LSA), mỗi bộ định tuyến xây dựng cho mình một cơ sở dữ liệu trạng thái riêng dựa vào nội dung của các bản tin này. Do đó các bộ định tuyến biết rõ và chinh xác thông tin topo về mạng và thực hiện truyền dẫn các gói tin từ nút nguồn đến nút đích trong mạng dễ dàng. Gói thông báo trạng thái liên kết (LSA: Link State Advertisment) là các gói tin nhỏ chứa thông tin định tuyến được truyền qua lại giữa các bộ định tuyến, được làm tràn trên mạng theo định kỳ hay khi có thay đổi thông tin của một bộ định tuyến nào đó trong mạng. Cơ sở dữ liệu trạng thái liên kết (LSDB: Link State Database) được tạo và cập nhật từ thông tin của các bản tin thông báo LSA. Thuật toán trạng thái liên kết được dùng để xây dựng và tính toán đường đi ngắn nhất từ nút nguồn đến tất cả các nút đích trong mạng. Thuật toán Dijkstra được áp dụng trong giao thức định tuyến trạng thái liên kết được thực hiện qua các bước sau: Input: Đồ thị (G, w, s); Dijkstra(G, w, s) Bước 1: Khởi tạo nút nguồn s; Bước 2: S : = {}; {Cuối cùng S sẽ chứa các đỉnh có trọng số đường đi ngắn nhất từ s} Bước 3: Khởi tạo hàng đợi ưu tiên Q : = V[G] {Q chứa các đỉnh trong đồ thị G} Bước 4: While Q {} do u : = EXTRACT_MIN(Q) {Chọn ra đỉnh v trong Q lân cận đỉnh u có trọng số cạnh (u,v) nhỏ nhất gán cho u} Bước 5: S : = S È {u} ; Q : = Q \ {u} Bước 6: for mỗi đỉnh v Î Adj[u] do {v các đỉnh liền kề với u} if d( v) > d(u) + w then {d(u), d(v) là chi phí được tính từ nút gốc đến các đỉnh u, v} d(v) : = d(u) + w; {quay lại Bước 4} Output: Cây đường đi ngắn nhất từ đỉnh s đến các nút trong mạng. Sử dụng giao thức định tuyến trạng thái liên kết sẽ dẫn đến một số nhược điểm: Router sử dụng định tuyến theo trạng thái kết nối sẽ phải cần nhiều bộ nhớ hơn và hoạt động xử lý nhiều hơn là sử dụng định tuyến theo vectơ khoảng cách. Router phải có đủ bộ nhớ để lưu cơ sở dữ liệu về cấu trúc mạng, bảng định tuyến. Khi khởi động việc định tuyến, tất cả các router phải gửi gói LSA cho tất cả các router khác, khi đó băng thông đường truyền sẽ bị chiếm dụng làm cho băng thông dành cho đường truyền dữ liệu của người dùng bị giảm xuống. Tuy nhiên, sau khi các router đã thu thập đủ thông tin để xây dựng cơ sở dữ liệu về cấu trúc mạng thì băng thông đường truyền không bị chiếm dụng nữa. Phân loại các giao thức định tuyến trong mạng MANET Mạng MANET (Mobile Ad hoc Network) là mạng không dây đặc biệt gồm tập hợp các thiết bị di động, giao tiếp không dây, có khả năng truyền thông trực tiếp với nhau hoặc thông qua các nút trung gian làm nhiệm vụ chuyển tiếp. Các nút mạng vừa đóng vai trò như thiết bị truyền thông vừa đóng vai trò như thiết bị định tuyến. Với nguyên tắc hoạt động như vậy, nó không bị phụ thuộc vào cơ sở hạ tầng mạng cố định nên có tính linh động cao, đơn giản trong việc lắp đặt, chi phí triển khai và bảo trì thấp. Như vậy, khi sử dụng các giao thức định tuyến thông thường dựa trên các giải thuật Distance-Vector hoặc Link-State trong mạng Ad Hoc sẽ dẫn đến một số vấn đề phát sinh: [6] Tiêu tốn băng thông mạng và năng lượng nguồn nuôi cho các cập nhật định kỳ: Hầu hết các thiết bị di động trong mạng Ad Hoc sẽ hoạt động dựa trên nguồn pin, việc truyền hoặc nhận gói tin sẽ tiêu tốn đáng kể đến nguồn năng lượng này. Ở các mạng thông thường, việc kết nối các bộ định tuyến nhìn chung là không thay đổi về vị trí, chính vì thế ít xảy ra việc thay đổi cấu hình tôpô mạng nên việc hội tụ mạng là ít xảy ra.Tuy nhiên, trong mạng Ad Hoc, các nút luôn thay đổi vị trí dẫn đến cấu hình tôpô mạng thay đổi, nên đòi hỏi cần phải có sự hội tụ của mạng cho các tuyến mới một cách nhanh chóng. Để thực hiện được việc này, các giao thức định tuyến phải liên tục gửi cập nhật định tuyến, dẫn đến việc tiêu tốn khá nhiều băng thông và năng lượng. Các đường đi dư thừa được tích lũy một cách không cần thiết: Trong môi trường mạng Ad Hoc, có rất nhiều đường đi từ nút nguồn đến nút đích và những đường đi này sẽ được cập nhật tự động vào bảng định tuyến trong các thiết bị định tuyến (thiết bị di động), dẫn đến việc dư thừa đường đi trong bảng định tuyến. Các giao thức định tuyến trong mạng Ad Hoc được chia thành 3 loại: Giao thức định tuyến theo bảng ghi (Table-Driven Routing Protocol), Giao thức định tuyến điều khiển theo yêu cầu (On-Demand Routing Protocol) và Giao thức định tuyến kết hợp (Hybrid Routing Protocol). Ad hoc Routing Protocols Table-Driven On-Demand Hybrid Flat Hierarchical DSDV WRP GSR OLSR DREAM MMWN CGSR HSR LANMAR HOLSR START Flat Hierarchical DSR TORA AODV LAR SSA MSR CBRP Flat Hierarchical ZRP SHARP ZHLS SLURP DST HARP Hình 2.1. Phân loại các giao thức định tuyến trong mạng Ad Hoc Giao thức định tuyến theo bảng ghi (Table-Driven Routing Protocol): Giao thức định tuyến theo bảng ghi còn được gọi là giao thức chủ ứng (Proactive). Theo giao thức này, bất kỳ một nút trong mạng đều luôn duy trì trong bảng định tuyến của nó thông tin định tuyến đến tất cả các nút khác trong mạng. Thông tin định tuyến được phát broadcast trên mạng theo một khoảng thời gian quy định để giúp cho bảng định tuyến luôn cập nhật những thông tin mới nhất. Chính vì vậy, một nút nguồn có thể lấy thông tin định tuyến ngay lập tức khi cần thiết. Tuy nhiên, với những mạng mà các node di chuyển nhiều hoặc các liên kết giữa các node bị đứt thì cần phải có cơ chế tìm kiếm hoặc sửa đổi thông tin của nút bị đứt trong bảng định tuyến, nhưng nếu các liên kết đó không sử dụng thì sẽ trở nên lãng phí tài nguyên, ảnh hưởng đến các băng thông của mạng. Chính vì thế giao thức định tuyến theo bảng ghi chỉ áp dụng trong các mô hình mạng MANET mà các nút ít di chuyển. Các giao thức hoạt động theo kiểu giao thức định tuyến theo bảng ghi như: Giao thức DSDV (Destination Sequenced Distance Vector), Giao thức WRP (Wireless Routing Protocol), Giao thức GSR (Global State Routing)… Giao thức định tuyến điều khiển theo yêu cầu (On-Demand Routing Protocol): Một phương pháp khác với phương pháp định tuyến điều khiển theo bảng ghi đó là định tuyến điều khiển theo yêu cầu còn được gọi là giao thức phản ứng (Reactive). Theo phương pháp này, các con đường đi sẽ được tạo ra nếu như có nhu cầu. Khi một nút yêu cầu một tuyến đến đích, nó phải khởi đầu một quá trình khám phá tuyến để tìm đường đi đến đích (Route Discovery). Quá trình này chỉ hoàn tất khi đã tìm ra một tuyến sẵn sàng hoặc tất cả các tuyến khả thi đều đã được kiểm tra. Khi một tuyến đã được khám phá và thiết lập, nó được duy trì thông số định tuyến (route maintenance) bởi một số dạng thủ tục cho đến khi hoặc là tuyến đó không thể truy nhập được từ nút nguồn hoặc là không cần thiết đến nó nữa. Với các cơ chế đó, các giao thức định tuyến điều khiển theo yêu cầu không phát broadcast đến các nút lân cân về các thay đổi của bảng định tuyến theo thời gian, nên tiết kiệm được tài nguyên mạng. Vì vậy, loại giao thức này có thể sử dụng trong các mạng MANET phức tạp, các node di chuyển nhiều. Một số giao thức định tuyến điều khiển theo yêu cầu tiêu biểu như: Giao thứ CBRP (Cluster Based Routing Protocol), Giao thức AODV (Ad hoc On Demand Distance Vector), Giao thức DSR (Dynamic Source Routing), Giao thức TORA (Temporally Ordered Routing Algorihm)… Giao thức định tuyến kết hợp (Hybrid Routing Protocol): Trong giao thức định tuyến này có kết hợp cả hai cơ chế giao thức định tuyến chủ ứng (Proactive) và giao thức định tuyến phản ứng (Reactive). Giao thức này phù hợp với những mạng quy mô, kích thước lớn, mật độ các nút mạng dày đặc. Trong giao thức định tuyến này, mạng được chia thành các vùng (zone). Mỗi node duy trì cả thông tin về kiến trúc mạng trong vùng của nó và thông tin về các vùng láng giềng. Đều đó có nghĩa là giao thức Hybrid sử dụng giao thức định tuyến phản ứng (Reactive) giữa các zone và giao thức định tuyến chủ ứng (Proactive) cho các node mạng trong cùng zone. Do đó, đường đi đến nỗi node trong cùng một zone được lập mà không cần phải định tuyến ra ngoài zone, trong khi đó các tiến trình khám phá đường và duy trì đường thì được sử dụng để tìm kiếm và duy trì đường đi giữa các zone với nhau. Các giao thức định tuyến tiêu biểu sử dụng kiểu Hybrid: Giao thức ZPR (Zone Routing Protocol), Giao thức ZHLS (Zone-based Hierarchical Link State Routing Protocol)… Giao thức định tuyến điều khiển theo yêu cầu trên mạng MANET: Như chúng ta đã biết, việc định tuyến trên các hệ thống mạng là khá quan trọng, quá trình định tuyến có thể xảy ra trước khi hệ thống có nhu cầu truyền dữ liệu hoặc trong khi hệ thống truyền dữ liệu. Các phương thức này cũng là một trong những yếu tố ảnh hưởng đến sự hoạt động của toàn bộ hệ thống mạng. Định tuyến điều khiển theo yêu cầu là một trong những phương thức định tuyến cơ bản trong hệ thống mạng không dây đặc biệt là hệ thống mạng MANET. Theo phương thức này, việc định tuyến chỉ xảy ra khi hệ thống có nhu cầu truyền dữ liệu. Có rất nhiều giao thức định tuyến sử dụng theo phương thức này. Trong luận văn này, chúng tôi phân tích hai giao thức định tuyến được sử dụng phổ biến nhất hiện nay: giao thức DSR và giao thức AODV. Giao thức DSR (Dynamic Source Routing): DSR (Dynamic Source Routing) là giao thức định tuyến đơn giản và hiệu quả được thiết kế riêng cho mạng MANET. DSR cho phép mạng tự động tổ chức và cấu hình mà không cần đến sự can thiệp của người quản trị hoặc cơ sở hạ tầng sẵn có của mạng. Giao thức DSR là giao thức định tuyến phản ứng (Reactive) sử dụng cơ chế định tuyến nguồn (source routing), nghĩa là bên gửi sẽ biết toàn bộ thông tin về đường đi đến đích. Phần Header của gói dữ liệu sẽ lưu trữ thứ tự các nút mà gói tin cần phải đi qua để đạt tới đích. Do vậy, các nút trung gian chỉ cần giữ liên lạc với các nút hàng xóm của nó để chuyển tiếp các gói tin. Tại mỗi một nút trong mạng luôn duy trì một bộ nhớ đệm (Router Cache), đây là cấu trúc dữ liệu lưu trữ các con đường đã biết. Khi có đường đi tồn tại trong Router Cache, các gói tin sẽ nhận thông tin về đường đi và thực hiện việc truyền tin trên con đường đã chọn. Ngược lại, khi không tồn tại đường đi trong Router Cache hoặc có tồn tại đường đi nhưng không còn hiệu lực, DSR sẽ thực hiện cơ chế phát hiện đường (Route Discovery) bằng cách gởi các gói tin quảng bá Route Request đến các nút lân cận trên toàn bộ mạng. Các nút trung gian nhận được gói tin quảng bá sẽ kiểm tra đường đi trong Route Cache. Khi đường đi được tìm thấy, gói tin Route Reply sẽ chứa thứ tự các chặng tới đích và được truyền trở lại nguồn. Như vậy, hoạt động của giao thức DSR bao gồm hai cơ chế chính: cơ chế tạo thông tin định tuyến (Route Discovery) và cơ chế duy trì thông tin định tuyến (Route Maintanance) [5], [6] Cơ chế tạo thông tin định tuyến (Route Discovery): Route Discovery cho phép các node trong mạng Ad Hoc tìm kiếm đường đi đến đích một cách tự động thông qua các node trung gian. Tiến trình tạo thông tin định tuyến sẽ phát gói tin Route Request (RREQ) đến các node lân cận của nó trong mạng. Ngoài các trường bình thường như: địa chỉ nguồn, địa chỉ đích, đường dẫn…, thông tin trong gói RREQ còn chứa một số request ID là một số được tạo ra bởi node nguồn và là số không trùng nhau. Khi một node nhận gói RREQ thì nó sẽ tiến hành kiểm tra thông tin trong RREQ như sau: Phát RREQ đến các node hàng xóm Trước đó node chưa nhận RREQ? Hủy gói RREQ N Node không có đường đi đến đích trong Route Cache? Y Node không là node đích? Y Phản hồi RREP về nguồn Y - Cập nhật thông tin về nguồn trong Router cache - Cập nhật lại đường dẫn cho gói RREQ N Kết thúc tiến trình khám phá đường Thêm vào Router cache của node Nối đường đi trong RREQ và đường đi đã có trong Router cache, cập nhật vào RREQ N Bắt đầu tiến trình khám phá đường tại nguồn Kết thúc tiến trình xử lý gói RREQ đã nhận Lưu đồ 2.1. Cơ chế xử lý khám phá đường tại node của DSR Bước 1: Thông qua trường request ID, nó sẽ kiểm tra xem đã nhận gói tin này hay chưa? Nếu đã tồn tại thì nó sẽ loại bỏ gói tin đó và không xử lí gì thêm. Ngược lại thì qua bước 2. Bước 2: Nó kiểm tra trong Route Cache của nó có đường đi đến node đích mà còn hiệu lực hay không? Nếu có đường đi đến đích thì nó sẽ phản hồi lại cho node nguồn bằng gói Route Reply (RREP) chứa thông tin về đường đi đến đích và kết thúc tiến trình. Ngược lại thì qua bước 3. Bước 3: Nó kiểm tra địa chỉ đích cần tìm có trùng với điạ chỉ của nó hay không? Nếu trùng thì nó gởi lại cho node nguồn gói Route Reply (RREP) chứa thông tin về đường đi đến đích và kết thúc tiến trình. Ngược lại thì nó sẽ phát broadcast gói tin RREQ đến các node láng giềng của nó. Các nút láng giềng sau khi nhận gói tin RREQ sẽ thực hiện việc kiểm tra thông tin (quay về bước 1) Như vậy, quá trình này cứ tiếp tục cho đến khi node nguồn nhận được thông tin về đường đi đến đích hoặc thông tin rằng không thể định tuyến đến đích. Gói Route Reply (RREP) được gởi đến nguồn bằng cơ chế phát Unicast với Source Route là đảo ngược Source Route trong gói RREQ. Ví dụ: Xét mô hình mạng Ad Hoc với mô hình truyền thông như hình 2.5. Nút S cần truyền dữ liệu đến nút D. S E A F B K G H I S D J Hình 2.2. Mô hình mạng Ad Hoc gồm 12 nút Giả thuyết 1: Trong Route Cache của các nút hiện tại là rỗng. Nút S sẽ phát gói tin Router Request (RREQ) đến các nút lân cận của nó (Hình 2.5.1) Hình 2.2.1. Nút S phát gói tin RREQ đến các nút lân cận A, E, F Nút A, E, F sẽ kiểm tra mình có phải là đích hay không? Nếu không sẽ kiểm tra trong Route Cache về đường đi đến đích. Theo giả thuyết ban đầu thì trong Route Cache sẽ không có thông tin về đường đi đến đích. Do đó, nút E, F, A sẽ cập nhật thông tin về đường đi về nguồn vào Route Cache thông qua gói tin RREQ, đồng thời sẽ phát gói tin RREQ đến các nút lân cận của nó. Bảng 2.1. Thông tin lưu trữ trong Route Cache tại thời điểm 1 Nút A, E, F sẽ phát gói tin RREQ đến các nút lân cận của nó (Hình 2.5.2) Hình 2.2.2. Nút A, F phát gói tin RREQ đến các nút F, B, A, K, G Tại thời điểm này tại A và F đều nhận gói tin RREQ (vì A là nút láng giềng của F và ngược lại). Do đó, hai gói tin này sẽ bị hủy vì đã tồn tại trước đó. Đồng thời, quá trình tìm kiếm đường đi vẫn chưa hoàn thành vì chưa đạt đến đích. Vì vậy, các nút lân cận sẽ lưu trữ thông tin về đường đi đến nguồn trong Route Cache và tiếp tục gửi gói tin RREQ đến các nút lân cận của nó. Bảng 2.2. Thông tin lưu trữ trong Route Cache tại thời điểm 2 Nút B, K, G sẽ phát gói tin RREQ đến các nút lân cận của nó (Hình 2.5.3) Hình 2.2.3. Nút B, K, G phát gói tin RREQ đến các nút C, G, H, K Tại thời điểm này, nút H cùng nhận gói RREQ từ 2 nút K và G. Trong trường hợp này, gói tin nào đến sau sẽ bị loại bỏ. Giả sử gói tin gửi từ K đến sau, vì thế giao thức DSR sẽ loại bỏ gói tin này. Tiến trình khám phá đường đi vẫn tiếp tục thực hiện. Bảng 2.3. Thông tin lưu trữ trong Route Cache tại thời điểm 3 Nút H, C sẽ phát gói tin RREQ đến các nút lân cận của nó (Hình 2.5.4) Hình 2.2.4. Nút H, C phát gói tin RREQ đến các nút láng giềng I, D, J Bảng 2.4. Thông tin lưu trữ trong Route Cache tại thời điểm 4 Tại thời điểm này, D nhận được gói RREQ và kiểm tra biết được mình chính là đích nên tiến trình khám phá đường đến đích dừng. Giao thức DRS sẽ thực hiện các công việc sau: D sẽ phát gói tin phản hồi Route Reply (RREP) về nguồn thông qua đường đã tìm được. Nút I vẫn tiếp tục phát gói RREQ để tìm đường đến D. Tuy nhiên, khi tìm thấy D thì gói tin RREQ sẽ lập tức bị hủy vì D đã nhận gói tin này trước đó, đồng thời D gửi gói tin RREP về nguồn S thông qua đường này. Nút J vẫn tiếp tục phát gói RREQ để tìm đến D. Tuy nhiên, trong trường hợp này nút I không tìm thấy và sẽ gửi gói RREP về nguồn. Trong khi các gói tin RREP được gửi về nguồn, Route Cache sẽ tiếp tục lưu trữ đường đi ngược lại từ đích. Sau khi nút nguồn S nhận được gói tin phản hồi RREP, S sẽ biết được được đường đi đến đích và tiến hành gửi dữ liệu theo con đường này. Hình 2.2.5. Nút D phát gói tin RREP về nút S theo đường đã khám phá Như vậy, trong trường hợp này sẽ có 2 con đường đi từ nút S đến nút D đó là: S,A,B,C,D và S,F,G,H,I,D. Giao thức DSR sẽ sử dụng một trong hai con đường này để truyền dữ liệu từ nút S đến nút D. Trong quá trình truyền dữ liệu nếu đường thứ nhất đang sử dụng bị hỏng thì giao thức sẽ sử dụng đường thứ hai và ngược lại. Trong trường hợp cả hai đường bị hỏng thì tiến trình khám phá đường (Router Discovery) sẽ tự động thực hiện lại. Giả thuyết 2: Trong Route Cache của các nút là không rỗng. Giả sử Route Cache của nút B đã lưu trữ đường đi đến D. Tiến trình khám phá đường đi vẫn thực hiện bình thường như giả thuyết 1. Tuy nhiên, khi đến B giao thức DSR sẽ kiểm tra trong Route Cache và phát hiện được đường đi đến D chính là đích, nên tiến trình khám phá đường sẽ dừng và nút B sẽ gửi gói tin phản hồi RREP về nguồn thông qua đường đi đã xác định. Cơ chế duy trì thông tin định tuyến (Route Maintanance): Route Maintanance cho phép các nút trong hệ thống mạng tự động bảo trì thông tin định tuyến trong Route Cache. Trong giao thức định tuyến DSR, các node khi chuyển gói tin trên mạng đều phải có nhiệm vụ xác nhận rằng các gói tin đó đã chuyển đến node kế tiếp hay chưa (thông qua sự phản hồi thông tin của node nhận) ? Trong một trường hợp nào đó mà node đó phát hiện rằng gói tin không thể truyền đến node kế tiếp. Nó sẽ gởi gói Route Error (RERR) cho node nguồn để thông báo tình trạng hiện thời của liên kết và điạ chỉ của node kế tiếp mà không thể chuyển đi. Khi node nguồn nhận được gói RERR, nó sẽ xóa con đường đi mà liên kết bị hỏng trong Route cache và tìm một đường đi khác mà nó biết trong route cache hoặc sẽ khởi động một tiến trình route discovery mới nếu như không tồn tại đường đi thích hợp trong Route cache. Hình 2.3. Minh họa cơ chế duy trì thông tin định tuyến Giao thức AODV (Ad hoc On Demand Distance Vector): Giao thức định tuyến AODV là một trong những giao thức định tuyến theo cơ chế phản ứng trong hệ thống mạng MANET. Tương tự như giao thức DSR, AODV cũng phát gói tin broadcast để yêu cầu tìm đường khi có nhu cầu. Tuy nhiên điểm khác biệt cơ bản đối với giao thức DSR là AODV sử dụng nhiều cơ chế khác để duy trì thông tin bảng định tuyến, chẳng hạn như nó sử dụng bảng định tuyến truyền thống để lưu trữ thông tin định tuyến với mỗi entry cho một địa chỉ đích. [3] Không sử dụng cơ chế Source Routing và cũng không cần biết thông tin về các node láng giềng của nó, AODV dựa trên các entry của bảng định tuyến để phát gói tin RREP về node nguồn và node nguồn dùng thông tin đó để gởi dữ liệu đến đích. Để đảm bảo rằng thông tin trong bảng định tuyến là mới nhất thì AODV sử dụng kỹ thuậ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 quá trình cập nhật bảng định tuyến) để loại bỏ những đường đi không còn giá trị trong bảng định tuyến. Mỗi node sẽ có một bộ tăng số Sequence Number riêng cho nó. [5] Tương tự như cơ chế hoạt động của DSR, quá trình định tuyến của AODV cũng bao gồm 2 cơ chế chính: cơ chế tạo thông tin định tuyến và cơ chế duy trì thông tin định tuyến. Cơ chế tạo thông tin định tuyến (Route Discovery): Cơ chế tạo thông tin định tuyến sẽ được thiết lập khi một nút nguồn có nhu cầu trao đổi thông tin với một nút khác trong hệ thống mạng. Trong hệ thống mạng MANET hoạt động theo giao thức AODV, mỗi nút trong hệ thống mạng luôn duy trì 2 bộ đếm: Bộ đếm Sequence Number và Bộ đếm REQ_ID. Cặp thông tin là định danh duy nhất cho một gói tin RREQ. Cặp thông tin này sẽ bị thay đổi giá trị khi: [5] Đối với Sequence Number: Trước khi một node khởi động tiến trình route discovery, đều này nhằm chống sự xung đột với các gói tin RREP trước đó. Khi nhận được một gói tin RREP gửi từ nút đích để trả lời gói tin RREQ, nó sẽ cập nhật lại giá trị Sequence number lớn nhất của một trong 2 giá trị: Sequence number hiện hành mà nó lưu giữ đối với Sequence number trong gói RREQ Đối với REQ_ID: Khi có một sự thay đổi trong toàn bộ các nút lân cận của nó dẫn đến sẽ có một số tuyến đường trong bảng định tuyến sẽ không còn hiệu lực. Số REQ_ID sẽ được tăng lên khi node khởi động một tiến trình route discovery mới. Hình 2.4. Các trường trong gói tin RREQ Tiến trình Route Discovery được khởi động khi nào một node muốn trao đổi dữ liệu với một node khác mà trong bảng định tuyến của nó không có thông tin định tuyến đến node đích đó. Khi đó tiến trình sẽ phát broadcast một gói RREQ cho các node láng giềng của nó. Thông tin trong RREQ ngoài địa chỉ đích, địa chỉ nguồn, số hop-count (được khởi tạo giá trị ban đầu là 0),… còn có các trường: số sequence number của node nguồn, số broadcast ID, giá trị sequence number được biết lần cuối cùng của node đích. Khi các node láng giềng nhận được gói RREQ, nó sẽ kiểm tra tuần tự theo các bước: Trước đó node chưa nhận RREQ? Hủy gói RREQ Y Node không là đích? N Không có đường trong Router cache? Hoặc Có đường nhưng DSN của Router cache nhỏ hơn DSN của RREQ N Y Phản hồi RREP về nguồn N - Thiết lập đường dẫn ngược về node phát RREQ - Hop_cnt = Hop_cnt + 1 Y Phát RREQ đến các hàng xóm Thêm vào Router cache của node Bắt đầu tiến trình khám phá đường tại nguồn Kết thúc tiến trình khám phá đường Kết thúc tiến trình xử lý gói RREQ đã nhận Lưu đồ 2.2. Cơ chế xử lý khám phá đường tại node của AODV Bước 1: Xem các gói RREQ đã được xử lý chưa? Nếu đã được xử lý thì nó sẽ loại bỏ gói tin đó và không xử lý thêm. Ngược lại chuyển qua bước 2. Bước 2: Nếu trong bảng định tuyến của nó chứa đường đi đến đích, thì sẽ kiểm tra giá trị Destination sequence number trong entry chứa thông tin về đường đi với số Destination sequence number trong gói RREQ, nếu số Destination sequence number trong RREQ lớn hơn số Destination squence number trong entry thì nó sẽ không sử dụng thông tin trong entry của bảng định tuyến để trả lời cho node nguồn mà nó sẽ tiếp tục phát Broadcast gói RREQ đó đến cho các node láng giềng của nó. Ngược lại nó sẽ phát Unicast cho gói RREP ngược trở lại cho node láng giềng của nó để báo đã nhận gói RREQ. Gói RREP ngoài các thông tin như: địa chỉ nguồn, địa chỉ đích,… còn chứa các thông tin: destination sequence number, hop-count, TTL. Ngược lại thì qua bước 3. Bước 3: Nếu trong bảng định tuyến của nó không có đường đi đến đích thì nó sẽ tăng số Hop-count lên 1, đồng thời nó sẽ tự động thiết lập một đường đi ngược (Reverse path ) từ nó đến node nguồn bằng cách ghi nhận lại địa chỉ của node láng giềng mà nó nhận gói RREQ lần đầu tiên. Entry chứa đường đi ngược này sẽ được tồn tại trong một khoảng thời gian đủ để gói RREQ tìm đường đi đến đích và gói RREP phản hồi cho node nguồn, sau đó entry này sẽ được xóa đi. Hình 2.5. Các trường trong gói tin RREP Quá trình kiểm tra này sẽ lặp tuần tự cho đến khi gặp node đích hoặc một node trung gian mà có các đều kiện thỏa bước 2. Trong quá trình trả về gói RREP, một node có thể nhận cùng lúc nhiều gói RREP, khi đó nó sẽ chỉ xử lý gói RREP có số Destination Sequence number lớn nhất, hoặc nếu cùng số Destination sequence number thì nó sẽ chọn gói RREP có số Hop-count nhỏ nhất. Sau đó nó sẽ cập nhật các thông tin cần thiết vào trong bảng định tuyến của nó và chuyển gói RREP đi. Cơ chế duy trì thông tin định tuyến: Như đã nhận xét ở trên, cơ chế hoạt động của AODV là không cần phải biết thông tin về các nút láng giềng, chỉ cần dựa vào các entry trong bảng định tuyến. Vì vậy, khi một node nhận thấy rằng Next hop (chặng kế tiếp) của nó không thể tìm thấy, thì nó sẽ phát một gói RRER (Route Error) khẩn cấp với số Sequence number bằng số Sequence number trước đó cộng thêm 1, Hop count bằng ∞ và gởi đến tất cả các node láng giềng đang ở trạng thái active, những node đó sẽ tiếp tục chuyển gói tin đó đến các node láng giềng của nó,... và cứ như vậy cho đến khi tất cả các node trong mạng ở trạng thái active nhận được gói tin này. [5] Sau khi nhận thông báo này, các node sẽ xóa tất cả các đường đi có chứa node hỏng, đồng thời có thể sẽ khởi động lại tiến trình Route discovery nếu nó có nhu cầu định tuyến dữ liệu đến node bị hỏng đó bằng cách gởi một gói tin RREQ (với số Sequence number bằng số Sequence number mà nó biết trước đó cộng thêm 1) đến các node láng giềng để tìm đến địa chỉ đích. So sánh hoạt động của các giao thức: AODV và DSR là hai giao thức được sử dụng phổ biến nhất trên hệ thống mạng MANET. Nhìn chung hai giao thức đều thực hiện tốt khả năng tìm đường của mình. Trong phần này, chúng tôi sẽ phân tích các đặc điểm giống nhau và khác nhau của hai giao thức. Giống nhau: Tiến trình khám phá đường đi được thực hiện dựa trên việc gởi quảng bá và nhận phản hồi. Thông tin định tuyến được lưu trữ tại tất cả các nút trung gian. Trong quá trình khám phá tuyến đường, các node trung gian đều có khả năng học đường về đích hoặc ngược về nguồn. Khác nhau: Đối với giao thức DSR, tại mỗi nút luôn duy trì thông tin về toàn bộ đường đi về đích hoặc về nguồn. Đối với giao thức AODV, tại mỗi nút chỉ duy trì thông tin đến các node hàng xóm của nó. Đồng thời, quá trình tìm đường trong giao thức AODV có kiểm tra về độ mới của thông tin đường đi về đích. Do vậy, chúng ta có thể thấy giao thức DSR sẽ duy trì và sử dụng những đường đi không còn hiệu lực cho đến khi phát hiện lỗi trong quá trình truyền, khi đó mới có cơ chế cập nhật lại thông tin về đường đi này. [2], [8] Trong quá trình thiết lập đường dẫn ngược về nguồn (phản hồi gói RREP), AODV có kiểm tra và lựa chọn giá trị Hop_cnt nhỏ nhất trong trường hợp có nhiều đường đến đích. Do vậy, đường đi lựa chọn trong giao thức AODV là tối ưu hơn trong DSR. DSR sử dụng cơ chế định tuyến nguồn, theo đó nó luôn trả lời cho tất cả các yêu cầu tìm đường. Cơ chế này giúp DSR thu thập được nhiều đường đi về đích dẫn đến khả năng phát tin tốt hơn AODV. Tuy nhiên, đều này chỉ tốt trong trường hợp mạng có ít nguồn phát và mức độ di chuyển không cao, trong trường hợp mức di chuyển cao khả năng các nút sẽ bị mất liên lạc với nhau nhiều là nguyên nhân dẫn đến số lượng đường đi mất hiệu lực trong Route cache tăng thêm vào đó là sự gia tăng các thông điệp Reply dẫn đến giảm sút hiệu suất của DSR. Kết luận chương 2: Định tuyến là một cơ chế không thể thiếu trong việc truyền tin trên các hệ thống mạng. Trong chương này, chúng tôi đã nghiên cứu một số thuật toán định tuyến truyền thống, nêu ra những đặc điểm cơ bản mà các giao thức này không hiệu quả trên hệ thống mạng MANET. Qua đó, chúng tôi đã phân loại các giao thức định tuyến và phân tích sâu một số giao thức định tuyến điều khiển theo yêu cầu trên mạng MANET và khả năng áp dụng của các giao thức trong từng môi trường mạng khác nhau. CHƯƠNG 3 MÔ PHỎNG VÀ ĐÁNH GIÁ HIỆU SUẤT MỘT SỐ GIAO THỨC ĐỊNH TUYẾN ĐIỀU KHIỂN THEO YÊU CẦU TRÊN MẠNG MANET Để đánh giá hiệu suất hoạt động của các giao thức thông thường người ta có thể dùng các phương pháp như: phương pháp giải tích, phương pháp thử nghiệm hoặc phương pháp mô phỏng. Trong luận văn này, chúng tôi chọn phương pháp mô phỏng để đánh giá hiệu năng hoạt động của hai giao thức đặc trưng cho giao thức định tuyến điều khiển theo yêu cầu là AODV và DSR dựa trên phần mềm mô phỏng về mạng không dâyNS-2. Giới thiệu môi trường mô phỏng NS: NS (Network Simulation) là phần mềm mô phỏng mạng điều khiển sự kiện riêng lẻ hướng đối tượng, được phát triển tại UC Berkely, viết bằng ngôn ngữ C++ và Otcl [13],[14]. NS rất hữu ích cho việc mô phỏng các hệ thống mạng hữu tuyến và vô tuyến, NS có các đặc điểm cơ bản sau: Khả năng kiểm tra tính ổn định của các giao thức mạng đang tồn tại Khả năng đánh giá các giao thức mạng mới trước khi đưa vào sử dụng Khả năng thực thi những mô hình mạng lớn mà gần như ta không thể thực thi được trong thực tế Khả năng mô phỏng nhiều loại mạng khác nhau NS thực thi các giao thức mạng như: Giao thức điều khiển truyền tải (TCP) và Giao thức gói người dùng (UDP); các dịch vụ nguồn lưu lượng như Giao thức truyền tập tin (FTP), Telnet, Web, Tốc độ bit cố định (CBR) và Tốc độ bit thay đổi (VBR); các kỹ thuật quản lý hàng đợi như Vào trước Ra trước (Drop Tail), Dò sớm ngẫu nhiễn (RED) và CBQ; các thuật toán định tuyến như Dijkstra… NS cũng thực thi multicasting và giao thức lớp Điều khiển truy cập đường truyền (MAC) đối với mô phỏng LAN. NS và Bộ biên dịch Tcl mở rộng hướng đối tượng; bao gồm các đối tượng Bộ lập lịch Sự kiện, các đối tượng Thành phần Mạng và các mô đun Trợ giúp Thiết lập Mạng. Hình 3.1. Tổng quan về NS dưới góc độ người dùng OTcl Script: Kịch bản OTcl Simulation Program: Chương trình Mô phòng Otcl: Bộ biên dịch Tcl mở rộng hướng đối tượng NS Simulation Library: Thư viện Mô phỏng NS Event Scheduler Objects: Các đối tượng Bộ lập lịch Sự kiện Network Component Objects: Các đối tượng Thành phần Mạng Network Setup Helping Modules: Các mô đun Trợ giúp Thiết lập Mạng Plumbling Modules: Các mô đun Plumbling Simulation Results: Các kết quả Mô phỏng Analysis: Phân tích NAM (Network Animator): Minh họa Mạng NAM Để sử dụng NS-2, user lập trình bằng ngôn ngữ kịch bản OTcl. User có thể thêm các mã nguồn Otcl vào NS-2 bằng cách viết các lớp đối tượng mới trong OTcl. Những lớp này khi đó sẽ được biên dịch cùng với mã nguồn gốc. Kịch bản OTcl có thể thực hiện những việc sau: Khởi tạo Bộ lập lịch Sự kiện Thiết lập Mô hình mạng dùng các đối tượng Thành phần Mạng Báo cho nguồn traffic khi nào bắt đầu truyền và ngưng truyền packet trong Bộ lập lịch Sự kiện Thuật ngữ plumbing được dùng để chỉ việc thiết lập mạng, vì thiết lập một mạng nghĩa là xây dựng các đường dữ liệu giữa các đối tượng mạng bằng cách thiết lập con trỏ “neighbour” cho một đối tượng để chỉ đến địa chỉ của đối tượng tương ứng. Mô đun plumbing OTcl trong thực tế thực hiện việc trên rất đơn giản. Plumbing làm nên sức mạnh của NS. Thành phần lớn khác của NS bên cạnh các đối tượng Thành phần Mạng là Bộ lập lịch Sự kiện. Bộ lập lịch Sự kiện trong NS-2 thực hiện những việc sau: Tổ chức Bộ định thời Mô phỏng Huỷ các sự kiện trong hàng đợi sự kiện Gọi các Thành phần Mạng trong mô phỏng Phụ thuộc vào mục đích của user đối với kịch bản mô phỏng OTcl mà kết quả mô phỏng có thể được lưu trữ như file trace. Định dạng file trace sẽ được tải vào trong các ứng dụng khác để thực hiện phân tích: File nam trace (file.nam) được dùng cho công cụ Minh họa mạng NAM File Trace (file.tr) được dùng cho công cụ Lần vết và Giám sát Mô phỏng XGRAPH hay TRACEGRAPH Hình 3.2: Luồng các sự kiện cho file Tcl chạy trong NS NAM Visual Simulation: Mô phỏng ảo NAM Tracing and Monitoring Simulation: Mô phỏng Lần vết và Giám sát Mô phỏng mạng không dây trong môi trường NS: Thực chất mô hình wireless bao gồm MobileNode trong lõi (core) cùng với các đặc tính hỗ trợ thêm vào cho phép các trình mô phỏng của mạng multi-hop với thủ tục Ad Hoc, mạng LAN wireless… Đối tượng MobileNode là một đối tượng tách biệt. Lớp MobileNode trong C++ xuất phát từ lớp cha là lớp Node. Vì vậy, một MobileNode là một đối tượng Node cơ sở cộng thêm các chức năng của wireless, có khả năng di chuyển bên trong một topo và nhận hoặc truyền tín hiệu thông qua một kênh wireless [8],[14]. Hình 3.3. Kiến trúc tầng của NS2 Tạo MobileNode trong NS: MobileNode là đối tượng nsNode cơ sở cùng với các chức năng như sự di chuyển, khả năng truyền và nhận trên một kênh cho phép tạo môi các trường mobile và môi trường wireless. Các tính năng mobile gồm có di chuyển node, cập nhập vị trí định kỳ, duy trì đường biên của topo,… được thực thi trong C++ trong quá trình dò tìm các thành phần của mạng bên trong của MobileNode (như các phân lớp, dmux, LL, Mac, Channel,…) được thực thi trong Otcl. Mã cấu hình MobileNode được viết như sau: $ns node-config -adhocRouting $val(rp) \ -llType $val(ll) \ -macType $val(mac) \ -ifqType $val(ifq) \ -ifqLen $val(ifqlen) \ -antType $val(ant) \ -propType $val(prop) \ -phyType $val(netif) \ -channelType $val(chan) \ -topoInstance $topo \ -agentTrace ON \ -routerTrace ON \ -macTrace ON \ -movementTrace ON\ Tạo sự hoạt động cho Node: MobileNode được hoạt động trên dạng flat (phẳng) với tọa độ X, Y, Z (Z=0). Có hai phương thức đưa ra sự di chuyển trong các MobileNode Phương thức 1: vị trí bắt đầu của node và các đích sau này của nó có thể được thiết lập một cách rõ ràng, có thể được thiết lập bằng cách sử dụng API sau: Hình 3.4. Mã cấu hình sự di chuyển cho Node Tại $time sec, node sẽ bắt đầu hoạt động (moving) từ vị trí bắt đầu của nó là (x1,y1) chuyển tiếp sang đích (x2,y2) với tốc độ (speed) xác định. Trong phương thức này, node-movement-updates được khởi tạo (triggered) bất cứ vị trí nào của node tại thời gian được yêu cầu. Phương thức 2: tận dụng quá trình họat động ngẫu nhiên của node. Mã API thường được sử dụng là $mobilenode start để khởi động mobilenode với một vị trí ngẫu nhiên và thường cập nhập để thay đổi hướng và tốc độ của node. Giá trị đích và tốc độ được tạo ra một cách ngẫu nhiên. Dạng topo không cấu trúc (flat) thông thường được tạo ra dựa vào đặc tả chiều dài và chiều rộng của topo cơ sở. Mã API được viết như sau: set topo [new Topography] $topo load_flatgrid $opt(x) $opt(y) Trong đó opt(x) opt(y) là giới hạn được sử dụng trong trình mô phỏng. Các thành phần cấu thành mạng trong một MobileNode: Ngăn xếp mạng đối với một MobileNode gồm có lớp link (LL), module ARP kết nối đến LL, một hàng đợi ngăn xếp IFq (interface priority queue(IFq)), lớp MAC, giao diện mạng netIF (interface(netIF)), tất cả được kết nối đến kênh channel. Link Layer LL: Thông thường đối với tất cả các packet đi ra từ kênh, các packet được đưa xuống LL nhờ vào agent định tuyến Routing Agent. LL đưa các packet xuống hàng đợi giao tiếp. Đối với các packet gửi vào (từ kênh riêng), lớp MAC đưa các packet lên LL sau đó dừng tại node_entry_ point. Module ARP: giao thức phân giải địa chỉ (Address Resolution Protocol) thực thi ở dạng BSD (implemented in BSD style) nhận các truy vấn từ lớp Link. Nếu ARP có địa chỉ hardware của đích đến, nó ghi địa chỉ đích đến vào header của MAC của packet. Ngược lại, nó gửi broadcasts truy vấn ARP, tạm thời giữ lại packet. Đối với mỗi đích đến không biết được địa chỉ hardware, có một bộ đệm đơn cho packet. Khi gửi thêm các packet đến đích mà đã gửi ARP thì packet ban đầu trong bộ đệm sẽ bị hủy (drop). Khi biết được địa chỉ hardware của packet, packet được thêm vào hàng giao tiếp (interface queue) của hop đó. Interface Queue: Lớp PriQueue được thực thi như một hàng đợi ưu tiên đưa ra các quyền ưu tiên để định tuyến các packet, thêm chúng vào đầu hàng đợi. Nó hỗ trợ quá trình thực thi trên tất cả các packet trong hàng đợi và gỡ bỏ các packet cùng với địa chỉ đích đến. Mac Layer IEEE 802.11: phân phối chức năng tọa độ DCF (distributed coordination function, giao thức MAC được thực thi bởi CMU. Nó sử dụng khuôn dạng RTS/CTS/DATA/ACK cho tất cả các packet unicast và đơn giản là gửi ra data cho tất cả các packet broadcast. Quá trình thực thi sử dụng cả phương thức cảm nhận sóng mang dạng vật lý lẫn dạng ảo. Tap Agents: Các agents mà phân lớp của nó có thể tự đăng ký với đối tượng MAC bằng cách sử dụng phương thức installTap(). Nếu giao thức MAC cụ thể cho phép, Tap sẽ đưa ra các paket nhận được bởi lớp MAC một cách lộn xộn, trước khi quá trình lọc địa chỉ được thực hiện. Network Interfaces: Lớp giao tiếp mạng (Network Interphase) đáp ứng như giao tiếp phần cứng (hardware interface) sử dụng bởi mobilenode để truy suất đến kênh truyền thông. Giao diện của môi trường truyền thong wireless chia sẽ được thực thi như lớp Phy/WirelessPhy. Giao diện này tùy thuộc vào các quá trình collision và mô hình truyền bá radio nhận các packet truyền qua bởi giao diện của node khác đến kênh truyền. Mô hình truyền bá Radio: Sử dụng công thức tính sự suy giảm đối với các khoảng cách gần là 1/r2 và đối với khỏang cách xa là 1/r4. Antenna: được sử dụng với mục đích chung bởi mobilenodes. Các bước viết mã tcl để thực thi mô phỏng mạng wireless: [8] Bước 1: Tạo một thể hiện mô phỏng Bước 2: Tạo file trace để lưu vết mô phỏng Bước 3: Tạo đối tượng topo Bước 4: Thiết lập không gian di chuyển cho các node Bước 5: Tạo đối tượng GOD (Genaral Operations Director), đây là đối tượng được sử dụng để lưu trữ các toàn bộ thông tin về trạng thái của môi trường, mạng, node… GOD được gọi sử dụng tại lớp MAC trong node. Bước 6: Cấu hình node Bước 7: Tạo sự di chuyển cho node (đoạn mã sau mô tả sự di chuyển của node là không ngẫu nhiên) Bước 8: Thiết lập vị trí cho node (trong trường hợp các node di chuyển không ngẫu nhiên) Bước 9: Thiết lập thời điểm 50s node 1 di chuyển về vị trí tương ứng tọa độ (25, 20) với tốc độ di chuyển 15m/s Bước 10: Thiết lập luồng traffic giữa các node (đoạn mã sau thiết lập luồng cho node 0 và node 1) Bước 11: Thiết lập thời gian dừng khi mô phỏng kết thúc Bước 12: Bắt đầu thực thi mô phỏng Thiết kế mô hình mạng để mô phỏng cho các giao thức định tuyến theo yêu cầu trên mạng MANET: Việc thiết kế và thử nghiệm cho các giao thức dựa trên phần mềm mô phỏng NS-2. Mô hình thiết kế cho 50 node mạng di chuyển ngẫu nhiên trong khu vực bán kính 3800m. Các gói tin phát dựa vào dịch vụ CBR (constant bit race), với kích thước gói tin 512 byte/1 gói tin, chu kỳ gửi tin 4 gói/1 giây. Hàng đợi kiểu FIFO, các gói tin định tuyến sẽ có độ ưu tiên cao hơn các gói tin dữ liệu. Hình 3.5. Mô hình mạng MANET gồm 50 node Để so sánh hiệu quả thực hiện của các giao thức, dựa trên kết quả mô phỏng sẽ đánh giá khả năng thích nghi của hai giao thức AODV và DSR trong mô hình mạng MANET gồm 50 node với các trường hợp: Tất cả các node trong hệ thống đứng yên: trong trường hợp này, các node trong hệ thống mạng được xác định tại một tọa độ cho trước và giữ nguyên vị trí trong suốt quá trình thực hiện mô phỏng. Tất cả các node trong hệ thống mạng di động: trong trường hợp này, các node trong hệ thống mạng di chuyển đến một vị trí ngẫu nhiên được xác định trước, với tốc độ từ 0~15m/s Phân tích kết quả mô phỏng: Để đánh giá khả năng hoạt động của các giao thức trong các đều kiện mạng khác nhau, chúng tôi sử dụng phần mềm Tracegraph 2.04 [12] để phân tích kết quả mô phỏng dựa trên các tham số: Tỉ lệ phần trăm gói tin phát thành công Trễ trung bình của hệ thống Khả năng đáp ứng trong trường hợp tôpô mạng thay đổi Trường hợp số nguồn phát thay đổi, tôpô cố định: Sau khi thực hiện mô phỏng với 50 node mạng cố định (không di chuyển), với số lượng nguồn phát ban đầu là 10 nguồn, sau đó sẽ thay đổi tại các thời điểm 10s, 20s tương ứng với số lượng nguồn phát 20 và 30 nguồn, thời gian thực hiện mô phỏng là 40s. Kết quả mô phỏng được thể hiện như sau: Trường hợp số lượng nguồn phát cố định: trong suốt thời gian mô phỏng chúng tôi thực hiện với 10, 15, 20, 25 và 30 nguồn phát chúng tôi thu được biểu đồ như sau: Hình 3.6a. So sánh tỉ lệ phát gói tin thành công của AODV và DSR Hình 3.6a cho thấy trong mọi trường hợp DSR cho kết quả phát gói tin thành công cao hơn AODV. Bên cạnh đó tỉ lệ phát gói tin thành công của hai giao thức giảm khi số lượng nguồn phát tăng dần. DSR cho kết quả tương đối ổn định khoảng 99% trong trường hợp số nguồn phát nhỏ hơn 20, trong trường hợp số nguồn phát lớn hơn 20 thì tỉ lệ này giảm dần. Trong khi đó AODV cho kết quả khoảng 99% trong trường hợp số nguồn phát nhỏ hơn 15, sau đó tỉ lệ giảm dần khi số nguồn phát tăng lên. Kết quả này cho thấy khả năng thích ứng với môi trường mạng cố định của DSR là tốt hơn AODV. Trường hợp số lượng nguồn phát thay đổi: ban đầu 10 nguồn thực hiện trong 10s, sau đó tăng lên 15, 20, 25, 30 nguồn. Hình 3.6b. Kết quả phân phát gói tin thành công của AODV và DSR Hình 3.6b cho thấy DSR cho kết quả tương đối cao và ổn định (khoảng 98%) trong trường hợp số nguồn phát nhỏ hơn 20. Tuy nhiên, kết quả này giảm trong trường hợp số lượng nguồn phát tăng. Bên cạnh đó AODV cho kết quả giảm đều khoảng từ 90% đến 60% trong trường hợp số nguồn phát nhỏ hơn 20. Tuy nhiên, tỉ lệ này tăng đều khi số lượng nguồn phát lớn hơn 20. Kết quả này cho thấy trong trường hợp số nguồn phát tăng sẽ dẫn đến nhu cầu tìm đường đến đích nhiều thì khả năng sử dụng lại đường đi đã khám phá của AODV tốt hơn DSR. Hình 3.6c. Trễ đầu cuối trung bình toàn hệ thống Hình 3.6.c thể hiện độ trễ trung bình toàn bộ hệ thống mạng. Trong trường hợp số lượng nguồn phát cố định, độ trễ trung bình của toàn hệ thống tỉ lệ thuận với số lượng node, AODV có độ trễ trung bình toàn bộ hệ thống lớn hơn DSR. Tuy nhiên, trong trường hợp số lượng nguồn thay đổi trong khoảng từ 10 đến 20 nguồn, AODV có độ trễ tăng dần từ 0.15 đến 0.2s nguồn, DSR có độ trễ giảm dần từ 0.05 đến 0.01s. Trong trường hợp số lượng nguồn phát thay đổi trong khoảng 20 đến 30 nguồn, AODV có độ trễ giảm dần từ 0.2 đên 0.13s, DSR có độ trễ tăng từ 0.01 đến 0.06s. Kết quả này cho thấy trong trường hợp mạng có nhiều thay đổi về số lượng nguồn phát thì khả năng khám phá đường của AODV là tốt hơn DSR. Kết quả mô phỏng trong trường hợp số nguồn phát cố định, tôpô thay đổi theo từng thời điểm: Sau khi thực hiện mô phỏng với 50 node mạng di chuyển đến một vị trí ngẫu nhiên được thiết lập trước, số lượng nguồn phát cố định cho các lần mô phỏng là: 10, 20 và 30. Thời gian thực hiện mô phỏng là 50s. Kết quả mô phỏng được thể hiện như sau: Tỉ lệ phân phát gói tin thành công của giao thức AODV và DSR Hình 3.7a. Tỉ lệ phân phát gói tin thành công trường hợp 10 nguồn Hình 3.7a cho thấy trong khoảng thời gian từ 10 đến 20s, tỉ lệ phát thành công của hai giao thức giảm trong khoảng từ 95% đến 90%, sau đó tỉ lệ này duy trì khá ổn định khoảng 90 % trong các khoảng thời gian còn lại. Kết quả này chứng tỏ trong thời gian khoảng từ 0 đến 20s cả hai giao thức đều thực hiện việc khám phá đường đi. Đến thời điểm 20s trở đi Router cache của các node đã có sẵn đường đi đã khám phá, vì thế trong khoảng thời gian này việc tìm đường của hai giao thức sẽ nhanh chóng hơn. Như vậy, kết quả trên cho thấy cả hai giao thức đều hoạt động tốt trong môi trường mạng di động với số lượng nguồn phát ít. Hình 3.7b. Tỉ lệ phân phát gói tin thành công trường hợp 20 nguồn Hình 3.7b cho thấy AODV cho kết quả phân phát gói tin khá ổn định trong khoảng 81% đến 86% trong mọi thời điểm. Tuy nhiên, trong khoảng từ 10 đến 20s, DSR cho kết quả không ổn định trong khoảng 68% đến 82%, sau đó duy trì kết quả thành công ở mức 82% cho các thời điểm tiếp theo. Kết quả trên chứng tỏ khi số lượng nguồn tăng lên AODV cho kết quả ổn định hơn DSR. Hình 3.7c. Tỉ lệ phân phát gói tin thành công trường hợp 30 nguồn Hình 3.7c cho thấy cả hai giao thức đều cho kết quả phân phát gói tin giảm sút giao động trong khoảng từ 48% đến 70%. Tuy nhiên AODV cho kết quả khá ổn định với mức từ 55% đến 70%. Bên cạnh đó DSR cho kết quả giao động từ 48% đến 70%. Như vậy, theo kết quả phân tích trong phần 3.1.1 trong trường hợp mạng không di chuyển thì kết quả tìm đường của DSR là tốt hơn. Tuy nhiên trong trường hợp mạng có nhiều biến động là nguyên nhân dẫn đến tình trạng đường đi mất hiệu lực trong router cache của các node tăng đột biến. Theo cơ sở lý thuyết AODV có các cơ chế để loại bỏ được các đường đi mất hiệu lực, vì thế khả năng sử dụng đường đi và khám phá đường mới của AODV là tốt hơn DSR dẫn đến tỉ lệ phân phát gói tin thành công của AODV là cao hơn. Thời gian trễ trung bình của toàn hệ thống: Hình 3.8. Thời gian trễ trung bình trường hợp 10, 20 và 30 nguồn Hình 3.8 thể hiện trễ trung bình toàn bộ hệ thống của hai giao thức AODV và DSR. Trong trường hợp số lượng nguồn phát nhỏ 10, 20 nguồn, độ trễ của DSR là tốt hơn AODV. Tuy nhiên trong trường hợp 30 nguồn phát, độ trễ AODV là tốt hơn. Như vậy, chứng tỏ khả năng tìm đường và sử dụng lại các đường đi đã khám phá của AODV là tốt hơn DSR trong các trường hợp các node trong mạng có nhiều thay đổi về vị trí. Kết luận chương 3: Việc triển khai thí nghiệm các hệ thống mạng trong thế giới thực là một công việc khá phức tạp, đòi hỏi tốn nhiều thời gian và chi phí cao. Bên cạnh đó, độ rủi ro không thành công khá cao. Để khắc phục tình trạng này chúng ta cần phải thực hiện các mô phỏng dựa trên các phần mềm ứng dụng mô phỏng mạng. Trong chương này, chúng tôi đã trình bày các bước thực hiện để mô phỏng mạng trong NS-2, các tập lệnh để thiết lập mô phỏng mạng không dây trên NS-2. Từ đó, chúng tôi xây dựng mô hình mạng Ad Hoc để thực hiện mô phỏng cho hai giao thức AODV và DSR và có những đánh giá hiệu năng như sau: Nhìn chung DSR ít bị ảnh hưởng trong trường hợp số lượng nguồn phát thay đổi, đều này cho thấy DSR thu thập được nhiều đường đi đến đích hơn AODV, chứng tỏ khả năng tìm đường của DSR là tốt hơn AODV. Tuy nhiên khi các nút di chuyển, AODV hoạt động với hiệu suất giảm khá rõ rệt với tỉ lệ phát tin thành công cao hơn, ổn định hơn và thời gian trễ nhỏ hơn đối với DSR, đều này chứng tỏ số lượng đường đã khám phá trong DSR bị cũ không còn hiệu lực và DSR không có cơ chế phát hiện để loại bỏ các đường đi không còn hiệu lực trong Router cache. Như vậy giao thức DSR có thể áp dụng trong trường hợp mạng với mức độ di chuyển thấp, AODV có thể áp dụng trong các trường hợp mạng với mức độ di chuyển cao. KẾT LUẬN Mạng MANET hiện đang là một thách thức của các nhà nghiên cứu trong việc tìm ra những giao thức mạng, chuẩn mạng mới với mục đích cuối cùng là đạt được một hệ thống mạng ổn định và hiệu suất khai thác cao trên các dịch vụ truyền thông đa phương tiện. Qua thời gian 6 tháng nghiên cứu một số giao thức định tuyến điều khiển theo yêu cầu trên mạng MANET. Luận văn đã đạt được một số kết quả: Kết quả đạt được: Trình bày một cách tổng quan về hệ thống mạng không dây và mạng MANET; yêu cầu các thiết bị để triển khai hệ thống mạng không dây; phân tích một số công nghệ ứng dụng mạng không dây; tổng quan về các ứng dụng mạng MANET trong cuộc sống. Nghiên cứu hoạt động của các giao thức định tuyến trong mạng MANET. Trên cơ sở đó chúng tôi đã phân tích cơ chế hoạt động của các giao thức định tuyến theo yêu cầu thông qua hai giao thức AODV và DSR. Đánh giá hiệu suất làm việc của hai giao thức để có cơ sở đề xuất việc áp dụng hợp lý các giao thức trong các mô hình mạng cụ thể. Thiết kế một số mô hình mạng MANET trên phần mềm NS-2. Cài đặt mô phỏng giao thức AODV và DSR để minh họa quá trình hoạt động. Từ đó, đánh giá hiệu năng trên các kịch bản khác nhau theo tỉ lệ gói mất, độ trễ trung bình và khả năng đáp ứng khi topo mạng thay đổi. Hướng phát triển: Nghiên cứu một số giao thức để áp dụng cả hai cơ chế định tuyến theo yêu cầu và định tuyến bảng ghi (giao thức lai) Nghiên cứu cải tiến các độ đo hiệu năng để nâng cao chất lượng truyền thông trên mô hình mạng không dây. TÀI LIỆU THAM KHẢO Tiếng Anh Arun Kumar B. R, Lokanatha C. Reddy, Prakash S. Hiremath (2008), Performance Comparison of Wireless Mobile Ad Hoc Network Routing Protocols, International Journal of Computer Science and Network Security, VOL.8 No.6. Geetha Jayakumar, Gopinath Ganapathy (2007), Performance Comparison of Mobile Ad Hoc Network Routing Protocol, International Journal of Computer Science and Network Security, VOL.7 No.11. Georgy Sklyarenko (2005), AODV Routing Protocol, Seminar Technische Informatik, Takustr. 9, D-14195 Berlin, Germany. McGraw-Hill/Osborne, Certified Wireless Network Administrator Official Study Guide, Copyright © by Planet3 Wireless, Inc. Stefano Basagni, Marco Conti, Silvia Giordano, Ivan Stojmenovic, Mobile Ad Hoc Networking, Copyright © 2004 by the Institute of Electrical and Electronics Engineers. Subir Kumar Sarkar, T G Basavaraju, C Puttamadappa, Ad Hoc Mobile Wireless Network, Copyright © 2008 by Taylor & Francis Group, LLC Tao Lin (2004), Mobile Ad Hoc Network Routing Protocols: Methodologies and Applications, Blacksburg, Virginia. Yinfei Pan, Suny Binghamton (2006), Design Routing Protocol Performance Comparison in NS2: AODV comparing to DSR as Example. Yu-Chee Tseng, Wen-Hua Liao, Shih-Lin Wu, Mobile Ad Hoc Networks and Routing Protocols, Handbook of Wireless Networks and Mobile Computing, Edited by Ivan Stojmenovic´Copyright© 2002 John Wiley & Sons, Inc, Chapter 17. Địa chỉ trên Internet The network simulator - ns-2. http:// www. isi.edu/nsnam/ns/ The ns Manual.