Định tuyến tối ưu trong mạng ADHOC

- ĐÀO HƯNG ĐỊNH TUYẾN TỐI ƯU TRONG MẠNG ADHOC Chuyên ngành : Điện tử viễn thông LUẬN VĂN THẠC SĨ KHOA HỌC ĐIỆN TỬ VIỄN THÔNG NGƯỜI HƯỚNG DẪN KHOA HỌC : 1.TS.
- Hệ đào tạo: Chính quy Thời gian đào tạo: từ 10/2009 đến 04/2012 - Chuyên ngành học: Điện tử Viễn thông - Tên luận văn: Định tuyến tối ưu trong mạng Adhoc - Người hướng dẫn Khoa học: TS.
- Ngày29 tháng 03 năm 2012 NGƯỜI KHAI KÝ TÊN Đào Hưng ảnh 4x6 Luận văn Thạc sĩ khoa học:Định tuyến tối ưu trong mạng Adhoc HVTH:Đào Hưng 2 MỤC LỤC Trang Trang phụ bìa.
- 26 Chương 2 - Định tuyến tối ưu trong mạng Adhoc.
- 28 2.1.1 Định tuyến tối ưu.
- 28 2.1.2 Yêu cầu đối với các giao thức định tuyến trong mạng Adhoc.
- 29 2.1.3 Các tham số định tuyến tối ưu trong mạng Adhoc.
- 30 2.2 Phân loại giao thức định tuyến trong mạng Adhoc.
- 31 Luận văn Thạc sĩ khoa học:Định tuyến tối ưu trong mạng Adhoc HVTH:Đào Hưng 3 2.2.1 Giao thức định tuyến DSDV.
- 34 2.2.2 Giao thức định tuyến DSR.
- 36 2.2.3 Giao thức định tuyến AODV.
- 39 2.2.4 Giao thức định tuyến TORA.
- 44 2.2.5 Giao thức định tuyến GPSR.
- 45 Chương 3 – Mô phỏng và đánh giá hiệu năng các giao thức định tuyến.
- 65 Luận văn Thạc sĩ khoa học:Định tuyến tối ưu trong mạng Adhoc HVTH:Đào Hưng 4 LỜI CAM ĐOAN Tôi xin cam đoan bản luận văn với đề tài:" Định tuyến tối ưu trong mạng Adhoc" do tôi tự thực hiện dưới sự hướng dẫn khoa học của TS.
- 57 Luận văn Thạc sĩ khoa học:Định tuyến tối ưu trong mạng Adhoc HVTH:Đào Hưng 7 Danh mục hình vẽ Hình 1.1 Mô hình mạng không dây.
- 26 Hình 2.1 So sánh chế độ IEEE Adhoc và giao thức định tuyến.
- 28 Hình 2.2 Phân loại giao thức định tuyến trong mạng Adhoc.
- 42 Hình 2.7 Minh họa về thuật toán định tuyến Greedy.
- 46 Hình 2.9 Ví dụ về giao thức định tuyến GPSR.
- 58 Luận văn Thạc sĩ khoa học:Định tuyến tối ưu trong mạng Adhoc HVTH:Đào Hưng 8 Lời nói đầu Ngày nay, khi công nghệ ngày càng phát triển với sự xuất hiện phổ biến của các thiết bị di động cá nhân như Smartphone,PDAs,Laptop.
- Chính vì thế tôi quyết định nghiên cứu đề tài:"Định tuyến tối ưu trong mạng Adhoc".
- Tôi xin chân thành cảm ơn ! Luận văn Thạc sĩ khoa học:Định tuyến tối ưu trong mạng Adhoc HVTH:Đào Hưng 9 Chương 1: Khái quát chung về mạng Adhoc 1.1 Đặt vấn đề Ngày nay, cùng với sự phát triển vượt bậc của khoa học công nghệ nói chung, ngành công nghệ thông tin đang ngày càng được đầu tư và phát triển mạnh mẽ.
- Do đó, cùng với vấn đề bảo mật của mạng không dây thì vấn đề định tuyến trong mạng là vô cùng quan trọng.
- Luận văn Thạc sĩ khoa học:Định tuyến tối ưu trong mạng Adhoc HVTH:Đào Hưng 10 1.1.1 Khái niệm về WLAN WLAN là một mạng cục bộ kết nối hai hay nhiều máy tính với nhau mà không sử dụng dây cáp mạng như các mạng có dây truyền thống.
- Năm 1999 cũng đánh dấu một bước phát triển quan trọng trên thị trường mạng Luận văn Thạc sĩ khoa học:Định tuyến tối ưu trong mạng Adhoc HVTH:Đào Hưng 11 không dây khi hãng máy tính Apple thông báo, chuẩn Wi-Fi sẽ xuất hiện trên dòng máy iBook mới của họ.
- Không giống như mạng có dây truyền thống, để thiết lập mạng chúng ta cần có những tính toán thiết kế hợp lý, tiến hành Luận văn Thạc sĩ khoa học:Định tuyến tối ưu trong mạng Adhoc HVTH:Đào Hưng 12 nhiều thao tác thì với mạng không dây, chỉ cần các thiết bị tuân theo một chuẩn nhất định và một điểm truy cập, hệ thống mạng đã có thể hoạt động bình thường.
- Tuy vậy, theo một số chuẩn mới, ở một số môi trường truyền đặc biệt, việc truyền thông trong mạng không dây cũng có thể đạt được tốc độ cao hơn đáng kể, ví dụ như trong Luận văn Thạc sĩ khoa học:Định tuyến tối ưu trong mạng Adhoc HVTH:Đào Hưng 13 chuẩn 802.11n việc truyền thông có thể đạt tốc độ từ 100-200Mbit/s.
- Luận văn Thạc sĩ khoa học:Định tuyến tối ưu trong mạng Adhoc HVTH:Đào Hưng 14 Hình 1.1 Mô hình mạng không dây  Trong mạng không dây, các nút có thể di chuyển ra khỏi mạng hoặc đi vào trong mạng làm cho topo mạng thay đổi, điều này hiếm khi xảy ra trong mạng có dây.
- Luận văn Thạc sĩ khoa học:Định tuyến tối ưu trong mạng Adhoc HVTH:Đào Hưng 15 1.2.2 Giới thiệu về mạng hạ tầng Trong mạng hạ tầng có các điểm truy cập AP (access-point) cố định đóng vai trò là các điểm truy cập cho các nút di động trong phạm vi phủ sóng của nó.
- Luận văn Thạc sĩ khoa học:Định tuyến tối ưu trong mạng Adhoc HVTH:Đào Hưng 16 Mạng Ad-hoc là mô hình phát triển cuối cùng của thông tin không dây (thông tin vô tuyến).
- Luận văn Thạc sĩ khoa học:Định tuyến tối ưu trong mạng Adhoc HVTH:Đào Hưng 17 Hình 1.3 Mô hình mạng Ad-hoc Trong tương lai, công nghệ mạng Ad-hoc có thể là một lựa chọn rất hữu ích đặc biệt trong những trường hợp không thể xây dựng cơ sở hạ tầng hoặc cơ sở hạ tầng bị phá hủy.
- Chỉ những kết nối giữa các thành viên trong đội cứu hộ đứng gần nhau Luận văn Thạc sĩ khoa học:Định tuyến tối ưu trong mạng Adhoc HVTH:Đào Hưng 18 mới có thể thực hiện được.
- Do đó, chúng ta cần thiết lập một mạng không dây không cần có cơ sở hạ tầng nhưng vẫn đảm bảo cho các thiết bị có Luận văn Thạc sĩ khoa học:Định tuyến tối ưu trong mạng Adhoc HVTH:Đào Hưng 19 thể trao đổi thông tin được với nhau.
- Luận văn Thạc sĩ khoa học:Định tuyến tối ưu trong mạng Adhoc HVTH:Đào Hưng 20 1.3.2 Ví dụ về mạng Ad-hoc Hình 1.4 Ví dụ cơ bản về mạng Ad-hoc Hình trên mô tả một mạng adhoc đơn giản gồm có 5 nút mạng được kí hiệu từ N1 đến N5.
- Luận văn Thạc sĩ khoa học:Định tuyến tối ưu trong mạng Adhoc HVTH:Đào Hưng 21 Mặt khác chúng ta cũng có thể thấy hai nút mạng nằm trong vùng phủ sóng của nhau có thể truyền thông trực tiếp cho nhau.
- Luận văn Thạc sĩ khoa học:Định tuyến tối ưu trong mạng Adhoc HVTH:Đào Hưng 22 - Tính hiệu quả: Trong một số ứng dụng nào đó, nếu sử dụng dịch vụ mạng có cơ sở hạ tầng có thể không có hiệu quả cao bằng việc dùng mạng adhoc.
- Mặt khác, do môi trường truyền được chia sẻ bởi nhiều nút mạng di động tùy biến nên việc truy nhập Luận văn Thạc sĩ khoa học:Định tuyến tối ưu trong mạng Adhoc HVTH:Đào Hưng 23 đến kênh truyền chung phải được thực hiện theo kiểu phân tán thông qua giao thức MAC.
- Vấn đề định tuyến trong mạng adhoc: Do đặc điểm chính của mạng Adhoc là topo động, các nút mạng có thể di chuyển liên tục nên khả năng đứt gẫy liên kết xảy ra là lớn.
- Khi đó, các thuật toán định tuyến của mạng có dây như trạng thái liên kết (link state) hay Vector khoảng cách (distance vector) đều không phù hợp với mạng Adhoc.
- Sự giới hạn về thời gian như thế đòi Luận văn Thạc sĩ khoa học:Định tuyến tối ưu trong mạng Adhoc HVTH:Đào Hưng 24 hỏi phải sử dụng tiết kiệm và bảo trì tốt nguồn điện.
- Luận văn Thạc sĩ khoa học:Định tuyến tối ưu trong mạng Adhoc HVTH:Đào Hưng 25  Định tuyến đa đường: Thuật toán định tuyến không dây cơ bản có thể định tuyến một chặng và nhiều chặng dựa vào các thuộc tính liên kết khác nhau và giao thức định tuyến.
- Luận văn Thạc sĩ khoa học:Định tuyến tối ưu trong mạng Adhoc HVTH:Đào Hưng 26 1.5 Giới thiệu về mạng VANET Mạng VANET (Vehicular Ad-hoc Network) là một công nghệ sử dụng các xe di chuyển như các nút trong một mạng để tạo nên một mạng di động.
- Luận văn Thạc sĩ khoa học:Định tuyến tối ưu trong mạng Adhoc HVTH:Đào Hưng 28 Chương 2: Định tuyến tối ưu trong mạng Ad-hoc 2.1 Khái niệm 2.1.1 Định tuyến tối ưu Định tuyến là quá trình chỉ ra hướng, sự di chuyển của một gói dữ liệu từ mạng nguồn của chúng, hướng tới đích cuối của chúng thông qua các nút trung gian, thiết bị chuyên dùng được gọi là router.
- Chuẩn IEEE Ad-hoc không hỗ trợ việc kết nối đa chặng như vậy, nhưng có thể thực Luận văn Thạc sĩ khoa học:Định tuyến tối ưu trong mạng Adhoc HVTH:Đào Hưng 29 hiện được nếu kết hợp với giao thức định tuyến.
- Thông tin định tuyến có thể là vị trí các nút , chất lượng đường truyền, khả năng của các nút.
- tùy theo từng giao thức định tuyến.
- Giao thức định tuyến thỏa mãn điều kiện này gọi là giao thức định tuyến tối ưu theo tham số, hoặc nhóm tham số đó.
- Một số yêu cầu đối với các giao thức định tuyến trong mạng Ad-hoc.
- Luận văn Thạc sĩ khoa học:Định tuyến tối ưu trong mạng Adhoc HVTH:Đào Hưng 30  Đường định tuyến hở: Để nâng cao chất lượng hoạt động, giao thức định tuyến cần đảm bảo đường định tuyến cung cấp là đường mở, điều này sẽ làm giảm lãng phí băng thông và năng lượng tiêu thụ CPU.
- Hỗ trợ các liên kết một chiều: Kết hợp với các liên kết hai chiều làm tăng chất lượng của giao thức định tuyến.
- Phần tải thông tin định tuyến tối ưu: là tỷ lệ phần tải nhỏ nhất dành cho thông tin định tuyến.
- Luận văn Thạc sĩ khoa học:Định tuyến tối ưu trong mạng Adhoc HVTH:Đào Hưng 31 - Thông lượng từ đầu cuối đến đầu cuối tối ưu: là khối lượng thông tin lớn nhất truyền trên đường truyền trong một đơn vị thời gian (Kbps.
- 2.2 Phân loại giao thức định tuyến trong mạng Ad-hoc Giao thức định tuyến trong mạng di động Ad-hoc có thể được chia thành các loại sau.
- Luận văn Thạc sĩ khoa học:Định tuyến tối ưu trong mạng Adhoc HVTH:Đào Hưng 32 Hình 2.2 Phân loại giao thức định tuyến trong mạng Ad-hoc a.
- Các giao thức định tuyến proactive sử dụng phương pháp tràn lụt (flooding) để quảng bá thông tin tới các thiết bị.
- Giao thức định tuyến liên kết tối ưu OLSR (Optimized Link State Routing) và giao thức định tuyến vector khoảng cách tuần tự đích DSDV ( Dynamic Destination-Sequenced Distance-Vector Routing) là hai ví dụ của giao thức định tuyến Proactive.
- Link state OLSR OSPF Giao thức định tuyến Giao thức định tuyến dựa trên Topo Giao thức định tuyến dựa trên vị trí Proactive Reactive Hybrid Distance vector DSDV AODV DSR TORA ZRP GPCR GPSR Luận văn Thạc sĩ khoa học:Định tuyến tối ưu trong mạng Adhoc HVTH:Đào Hưng 33 b.
- Luận văn Thạc sĩ khoa học:Định tuyến tối ưu trong mạng Adhoc HVTH:Đào Hưng 34 Trái với giao thức định tuyến dựa trên topo mạng, các nút mạng có thể tự xác định vị trí của nó cũng như vị trí của các nút khác trong mạng khi chúng sử dụng giao thức định tuyến dựa trên vị trí.
- Một vài ví dụ của giao thức định tuyến dựa trên vị trí là giao thức GPSR (Greedy Perimeter Stateless Routing) và giao thức GPCR (Greedy Perimeter Coordinate Routing).
- Mỗi nút sẽ Luận văn Thạc sĩ khoa học:Định tuyến tối ưu trong mạng Adhoc HVTH:Đào Hưng 35 tăng 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.
- Quản lý bảng định tuyến Mỗi lút luôn duy trì một bảng định tuyến đến tất cả các nút khác trong mạng.
- Thông tin của một entry trong bảng định tuyến bao gồm.
- Luận văn Thạc sĩ khoa học:Định tuyến tối ưu trong mạng Adhoc HVTH:Đào Hưng 36 b.
- Cập nhật toàn bộ bảng định tuyến cho các nút hàng xóm và có thể truyền trong nhiều gói, gọi là full-dump.
- 2.2.2 Giao thức định tuyến DSR[7] 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.
- Luận văn Thạc sĩ khoa học:Định tuyến tối ưu trong mạng Adhoc HVTH:Đào Hưng 37 Một đặc tính nổi bật khác của DSR là nó sử dụng kỹ thuật định tuyến Source routing, khi bên gởi sẽ biết toàn bộ thông tin đường đi đến đích, điều này giúp cho việc định tuyến trên mạng không bị hiện tượng vòng lặp (loop) làm tăng hiệu năng của mạng.
- Thông tin về bảng định tuyến được lưu trong route cache.
- Nó kiểm tra địa chỉ đích cần tìm có trùng với địa chỉ của nó hay không? nếu trùng thì nó sẽ gửi lại cho nút nguồn gói router reply (RREP) chứa Luận văn Thạc sĩ khoa học:Định tuyến tối ưu trong mạng Adhoc HVTH:Đào Hưng 38 thông tin về đường đi đến đích và kết thúc tiến trình.
- Hình 2.3 Quá trình tìm kiếm đường của DSR Luận văn Thạc sĩ khoa học:Định tuyến tối ưu trong mạng Adhoc HVTH:Đào Hưng 39 Hình 2.4 Gửi trả lại tuyến đường về cho nút nguồn b.
- 2.2.3 Giao thức định tuyến AODV[12] AODV (Ad hoc On-demand Distance Vector) là sự kết hợp giữa hai giao thức định tuyến DSDV và DSR .
- Luận văn Thạc sĩ khoa học:Định tuyến tối ưu trong mạng Adhoc HVTH:Đào Hưng 40 AODV vẫn sử dụng cơ chế tìm đường như trong DSR là sử dụng tiến trình route discovery.
- Tuy nhiên, AODV còn sử dụng nhiều cơ chế khác để duy trì thông tin bảng định tuyến.
- Luận văn Thạc sĩ khoa học:Định tuyến tối ưu trong mạng Adhoc HVTH:Đào Hưng 41 Thông tin trong RREQ ngoài địa chỉ đích, địa chỉ nguồn, số hop count.
- Luận văn Thạc sĩ khoa học:Định tuyến tối ưu trong mạng Adhoc HVTH:Đào Hưng 42 Và quá trình trên cứ lặp lại cho đến khi gặp nút đích hoặc nút trung gian mà có các điều kiện thỏa bước 2.
- Hình 2.5 Quá trình truyền của RREP Hình 2.6 Đường đi của gói tin RREP trở về nguồn Luận văn Thạc sĩ khoa học:Định tuyến tối ưu trong mạng Adhoc HVTH:Đào Hưng 43 b.
- Một entry của bảng Luận văn Thạc sĩ khoa học:Định tuyến tối ưu trong mạng Adhoc HVTH:Đào Hưng 44 định tuyến được xem là active nếu nó được sử dụng bởi các nút láng riềng ở trạng thái active.
- Luận văn Thạc sĩ khoa học:Định tuyến tối ưu trong mạng Adhoc HVTH:Đào Hưng 45 Cơ chế duy trì tuyến đường thực ra chính là phản ứng của TORA với các thay đổi cấu hình trong mạng.
- 2.2.5 Giao thức định tuyến GPSR[19] Giao thức định tuyến GPSR [19] (Greedy perimeter Stateless Routing) là một giao thức định tuyến dựa theo thông tin vị trí địa lý của các nút tham gia trong mạng không dây.
- Luận văn Thạc sĩ khoa học:Định tuyến tối ưu trong mạng Adhoc HVTH:Đào Hưng 46 Hình 2.7 Minh họa về thuật toán định tuyến Greedy.
- Hình 2.8 Nhược điểm của thuật toán chuyển tiếp Greedy Luận văn Thạc sĩ khoa học:Định tuyến tối ưu trong mạng Adhoc HVTH:Đào Hưng 47 Nút S gửi một nút tới nút D, gói này được chuyển tiếp trong chế độ Greedy cho tới khi nó tới được nút F.
- Đường tròn đậm biểu thị khoảng vô tuyến của mỗi nút, còn đường trong đứt đoạn chỉ khoảng Luận văn Thạc sĩ khoa học:Định tuyến tối ưu trong mạng Adhoc HVTH:Đào Hưng 48 cách tới đích khi đươc chuyển sang chế độ perimeter.
- Hình 3.1 Mô hình hiện trường Luận văn Thạc sĩ khoa học:Định tuyến tối ưu trong mạng Adhoc HVTH:Đào Hưng 50 Mô hình của chúng ta gồm 49 node.
- Luận văn Thạc sĩ khoa học:Định tuyến tối ưu trong mạng Adhoc HVTH:Đào Hưng 55  Thông lượng Giao thức DSDV Giao thức AODV Luận văn Thạc sĩ khoa học:Định tuyến tối ưu trong mạng Adhoc HVTH:Đào Hưng 56 Giao thức DSR Ta thấy giao thức DSDV tuy mất nhiều thời gian kết nối nhưng đạt băng thông ổn định 150Kb/s và có thể đạt hơn 200Kb/s.
- Nhận xét: Qua kết quả mô phỏng chúng ta thấy cả 3 giao thức định tuyến đều có ưu nhược điểm riêng.
- Luận văn Thạc sĩ khoa học:Định tuyến tối ưu trong mạng Adhoc HVTH:Đào Hưng 62 Kết luận và hướng nghiên cứu Kết luận chung: Luận văn đã trình bày các kết quả khảo sát đánh giá về ảnh hưởng của sự chuyển động các nút mạng và số lượng các nút mạng(Qua 2 mô hình mô phỏng) đến hiệu suất của một số giao thức định tuyến trong Adhoc.
- Vấn đề năng lượng  Chất lượng dịch vụ  Vấn đề bảo mật,… Luận văn Thạc sĩ khoa học:Định tuyến tối ưu trong mạng Adhoc HVTH:Đào Hưng 63 Tài liệu tham khảo [1] Eitan Altman, Tania Jimenez.
- Luận văn Thạc sĩ khoa học:Định tuyến tối ưu trong mạng Adhoc HVTH:Đào Hưng 64 [14] Jochen H.
- Các giải pháp định tuyến tối ưu trong mạng di động không dây tuỳ biến.
- Định tuyến trong mạng kết nối hình lưới WLAN.
- Luận văn Thạc sĩ khoa học:Định tuyến tối ưu trong mạng Adhoc HVTH:Đào Hưng 65 Phụ lục: Các công cụ mô phỏng A.
- Luận văn Thạc sĩ khoa học:Định tuyến tối ưu trong mạng Adhoc HVTH:Đào Hưng 66 Ban đầu, Linux được phát triển và sử dụng bởi những người say mê.
- Luận văn Thạc sĩ khoa học:Định tuyến tối ưu trong mạng Adhoc HVTH:Đào Hưng 67 B.
- Hai module này có quan hệ mật thiết với nhau: một lớp trong module giao tiếp OTcl có ánh xạ một-một với lớp Luận văn Thạc sĩ khoa học:Định tuyến tối ưu trong mạng Adhoc HVTH:Đào Hưng 68 tương ứng trong module nhân thông qua module liên kết như đã trình bày ở trên.
- Phân loại ứng dụng Luận văn Thạc sĩ khoa học:Định tuyến tối ưu trong mạng Adhoc HVTH:Đào Hưng 70 Trong NS-2 có hai loại ứng dụng cơ bản.
- Các phương thức đã được cài đặt trong NS-2: Luận văn Thạc sĩ khoa học:Định tuyến tối ưu trong mạng Adhoc HVTH:Đào Hưng 71 attach-agent : gắn ứng dụng FTP lên agent vận tải.
- Luận văn Thạc sĩ khoa học:Định tuyến tối ưu trong mạng Adhoc HVTH:Đào Hưng 72 C.
- -topoInstance $topo \ -agentTrace ON \ -routerTrace ON \ -macTrace OFF \ -movementTrace ON #this one is ON to allow movement Luận văn Thạc sĩ khoa học:Định tuyến tối ưu trong mạng Adhoc HVTH:Đào Hưng 73 # Define nodes for {set i 0} {$i < $val(nn.
- $ns_ run Luận văn Thạc sĩ khoa học:Định tuyến tối ưu trong mạng Adhoc HVTH:Đào Hưng 78 Mô hình đường cao tốc # Define options set val(chan) Channel/WirelessChannel.
- Luận văn Thạc sĩ khoa học:Định tuyến tối ưu trong mạng Adhoc HVTH:Đào Hưng 79 set node_($i) [$ns_ node

Xem thử không khả dụng, vui lòng xem tại trang nguồn
hoặc xem Tóm tắt