›

Luận văn Cải tiến và đánh giá hiệu năng giao thức định tuyến đi vòng dựa trên phân loại nút theo góc phần tư

pdf 72 trang yendo 4220
Download
Bạn đang xem 20 trang mẫu của tài liệu "Luận văn Cải tiến và đánh giá hiệu năng giao thức định tuyến đi vòng dựa trên phân loại nút theo góc phần tư", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfluan_van_cai_tien_va_danh_gia_hieu_nang_giao_thuc_dinh_tuyen.pdf

Nội dung text: Luận văn Cải tiến và đánh giá hiệu năng giao thức định tuyến đi vòng dựa trên phân loại nút theo góc phần tư

  1. ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ NGUYỄN QUỐC DŨNG CẢI TIẾN VÀ ĐÁNH GIÁ HIỆU NĂNG GIAO THỨC ĐỊNH TUYẾN ĐI VÒNG DỰA TRÊN PHÂN LOẠI NÚT THEO GÓC PHẦN TƯ LUẬN VĂN THẠC SĨ Hà Nội - 2014
  2. ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ NGUYỄN QUỐC DŨNG CẢI TIẾN VÀ ĐÁNH GIÁ HIỆU NĂNG GIAO THỨC ĐỊNH TUYẾN ĐI VÒNG DỰA TRÊN PHÂN LOẠI NÚT THEO GÓC PHẦN TƯ Ngành: Công nghệ thông tin Chuyên ngành: Truyền dữ liệu và Mạng máy tính Mã số: LUẬN VĂN THẠC SĨ NGƯỜI HƯỚNG DẪN KHOA HỌC: TS. HOÀNG XUÂN TÙNG Hà Nội – 2014
  3. LỜI CAM ĐOAN Tôi xin cam đoan luận văn tốt nghiệp này là đề tài nghiên cứu do tôi thực hiện. Các số liệu và kết quả nghiên cứu được trình bày trong luận văn được đo đạc thực nghiệm trung thực và chưa được công bố ở bất kỳ công trình khoa học nào khác. Tất cả tài liệu tham khảo đều có nguồn gốc rõ ràng và được trích dẫn hợp pháp. Tôi xin hoàn toàn chịu trách nhiệm và chịu mọi hình thức kỷ luật theo quy định cho lời cam đoan của mình. Học viên Nguyễn Quốc Dũng
  4. 4 LỜI CẢM ƠN Em xin gửi lời cảm ơn chân thành và sự tri ân sâu sắc đối với các thầy cô của trường Đại học Công Nghệ, Đại học Quốc Gia Hà Nội, đặc biệt là các thầy cô khoa Công nghệ thông tin của trường đã truyền dạy những kiến thức, kinh nghiệm quý báu giúp em hoàn thành khóa học tại trường. Con xin gửi lời cảm ơn tới gia đình, cảm ơn bạn bè đã tạo điều kiện thuận lợi trong quá trình học tập và thực hiện luận văn tốt nghiệp. Đặc biệt em xin chân thành cảm ơn TS. Hoàng Xuân Tùng, giảng viên khoa Công nghệ thông tin. Thầy đã nhiệt tình hướng dẫn em hoàn thành tốt nghiệp. Trong quá trình học tập, cũng như trong quá trình thực hiện luận văn, các sai sót là khó tránh khỏi. Tuy nhiên em đã cố gắng tối đa để đảm bảo chất lượng và các tiêu chí của nghiên cứu khoa học. Kính mong quí thầy cô góp ý để luận văn của em được hoàn thiện hơn. Em xin chân thành cảm ơn! Học viên Nguyễn Quốc Dũng
  5. 5 NHẬN XÉT CỦA GV HƯỚNG DẪN, GV PHẢN BIỆN
  6. 6 MỤC LỤC BẢNG KÝ HIỆU CÁC CHỬ VIẾT TẮT 9 DANH MỤC CÁC BẢNG BIỂU 10 DANH MỤC HÌNH ẢNH 11 LỜI MỞ ĐẦU 12 Chương 1. GIAO THỨC ĐỊNH TUYẾN THEO THÔNG TIN VỊ TRÍ ĐỊA LÝ 15 1.1. Tổng quan về giao thức định tuyến theo thông tin vị trí địa lý 15 1.2. Các chiến lược định tuyến trong định tuyến địa lý 17 1.2.1. Chiến lược định tuyến tham lam 17 1.2.2. Chiến lược định tuyến đi vòng 18 1.2.3. Chiến lược định tuyến phát tràn 19 1.3. Giao thức định tuyến “Greedy Perimeter Stateless Routing” 21 1.3.1. Tổng quan 21 1.3.2. Thuật toán định tuyến GPSR 22 Chương 2. GIAO THỨC ĐỊNH TUYẾN “DETOUR ROUTING BASED ON QUADRANT CLASSIFICATION” 25 2.1. Tổng quan 25 2.2. Chuyển tiếp tham lam và vấn đề vùng trống trong DRQC 26 2.2.1. Chiến lược chuyển tiếp tham lam 26 2.2.2. Vấn đề vùng trống trong giao thức DRQC 27 2.3. Thuật toán định tuyến trong giao thức DRQC 28 2.3.1. Khái niệm, định nghĩa 28 2.3.2. Trạng thái của các nút 28 2.3.3. Định dạng thông điệp gửi 29 2.3.4. Cấu trúc dữ liệu 30 2.3.5. Thuật toán xử lý định tuyến DRQC. 31
  7. 7 Chương 3. GIAO THỨC “DETOUR ROUTING BASED ON COORDINATES ROTATION” 34 3.1. Hạn chế của giao thức định tuyến DRQC 34 3.1.1. Nút tối ưu không thuộc góc với nút đích 34 3.1.2. Ví dụ định tuyến không tối ưu theo DRQC 36 3.2. Đề xuất giải pháp cải tiến giao thức DRQC 37 3.2.1. Giải pháp quay trục tọa độ 37 3.2.2. Phương pháp quay trục áp dụng trong DRQC 40 3.2.3. Ví dụ 41 Chương 4. ĐÁNH GIÁ HIỆU NĂNG 44 4.1. Môi trường cài đặt chương trình mô phỏng 44 4.2. Đánh giá tỷ lệ chuyển gói tin thành công trong mạng 44 4.2.1. Kịch bản mô phỏng 44 4.2.2. Kết quả thực hiện đánh giá 45 4.3. Thông lượng trung bình của các giao thức định tuyến địa lý 47 4.3.1. Kịch bản mô phỏng 47 4.3.2. Kết quả thực nghiệm và phân tích 48 KẾT LUẬN 49 TÀI LIỆU THAM KHẢO 51 PHỤC LỤC 1 52 I. CÔNG CỤ MÔ PHỎNG SỰ KIỆN MẠNG NS-3 52 1.1. Tổng quan về NS-3 52 1.2. Các thành phần của NS-3 53 i. Node 54 ii. Application 54 iii. Channel 54 iv. Net Device 54 3. Cài đặt NS-3 55 i. Các phần mềm cần thiết 55 a) Mercurial 55
  8. 8 b) Waf 55 ii. Cài đặt và kiểm tra và thực hiện mô phỏng 56 a) Cài đặt NS-3 56 iii. Kiểm tra cài đặt và chạy thử chương trình 61 4. Thêm mới module, cài đặt giao thức định tuyến GPSR và DRQC 63 i. Thêm mới module vào dự án NS-3 63 ii. Cài đặt giao thức định tuyến DRQC, GPSR 64 iii. Cài đặt giao thức DRQC 64 iv. Cài đặt giao thức GPSR 70 PHỤ LỤC 2 71
  9. 9 BẢNG KÝ HIỆU CÁC CHỬ VIẾT TẮT STT Chử viết tắt Ý nghĩa 1 AODV Ad-Hoc On-Demad Distance Vector Routing 2 DR-CR Detour Routing based on Coordinates Rotation 3 DRQC Detour Routing Quadrant Classification Protocol 4 DSR Dynamic Source Routing (DSR) [6] 5 GOAFR Greedy Other Adaptive Face Routing 6 GPS Global Positioning System 7 GPSR Geographic Perimeter Stateless Routing Protocol 8 GRP Geographics Routing Protocol 9 NS3 Network Simulator 3
  10. 10 DANH MỤC CÁC BẢNG BIỂU Bảng 2-1: Định dạng thông điệp quảng bá 27 Bảng 2-2: Định dạng thông điệp dữ liệu 28 Bảng 2-3: Định dạng thông điệp phản hồi 28 Bảng 2-4: Định dạng cấu trúc bảng định tuyến 29 Bảng 2-5: Định dạng cấu trúc bảng hàng xóm 30 Bảng 3-1: Danh sách các nút hàng xóm DR-CR 39 Bảng 3-2: Danh sách nút hàng xóm mới DR-CR 40 Bảng 4-1: Bảng thông số kịch bản mô phỏng mạng ngẫu nhiên 42 Bảng 4-2: Kết quả tỷ lệ chuyển gói tin thành công 43 Bảng 4-3: Thông số mô phỏng mạng cố định 45
  11. 11 DANH MỤC HÌNH ẢNH Hình 1-1. Các tiêu chí lựa chọn trong chiến lược tham lam 17 Hình 1-2. Chiến lược định tuyến phẳng trong định tuyến địa lý 19 Hình 1-3. Chuyển tiếp tham lam trong GPSR 22 Hình 1-4. Vấn đề vùng trống trong GPSR 23 Hình 1-5. Quy tắc bàn tay phải 24 Hình 2-1. Định tuyến gói tin theo chiến lược tham lam 26 Hình 2-2. Vùng trống trong giao thức DRQC 27 Hình 2-3. Định nghĩa các nút trong DRQC 28 Hình 2-4. Trạng thái của nút trong DRQC 29 Hình 2-5. Các bước xử lý tìm kiếm đường đi 32 Hình 2-6. Các bước xử lý gói tin phản hồi 33 Hình 3-1. Ví dụ định tuyến DRQC không tối ưu 34 Hình 3-2. Nút tối ưu nằm trên trục tọa độ 35 Hình 3-3. Nút tối ưu không thuộc góc phần tư nút đích 35 Hình 3-4. Ví dụ định tuyến không hiệu quả 36 Hình 3-5. Hệ trục tọa đọ của một nút 37 Hình 3-6. Xoay trục tọa độ của một nút 38 Hình 3-7. Xác định trục tọa độ mới 39 Hình 3-8. Tính góc trục tọa độ mới 40 Hình 3-9. Thuật toán cải tiến định tuyến DRQC 41 Hình 3-10. Ví dụ về định tuyến gói tin DR-CR 42 Hình 3-11. Ví dụ về xoay trục định tuyến gói tin DR-CR 42 Hình 4-1. Cấu trúc mạng gồm 50 nút 45 Hình 4-2. Cấu trúc mạng gồm 100 nút 45 Hình 4-3. Cấu trúc mạng gồm 150 nút 45 Hình 4-4. Cấu trúc mạng gồm 200 nút 45 Hình 4-5. Cấu trúc mạng gồm 250 nút 45 Hình 4-6. Biểu đồ tỷ lệ chuyển gói tin thành công 46 Hình 4-7.Cấu trúc mạng có vị trí cố định 47 Hình 4-8. Thông lượng theo thời gian của các giao thức 48
  12. 12 LỜI MỞ ĐẦU Định tuyến gói tin trong mạng cảm biến không dây (WSN – Wireless Sensor Network) luôn gặp phải rất nhiều thách thức. Thách thức từ chính các cấu trúc mạng luôn thay đổi hoặc những rào cản địa lý như sông, hồ, rừng, núi, Những vấn đề trên là đối tượng nghiên cứu của nhiều giao thức định tuyến của mạng WSN như: Dynamic Source Routing (DSR) [6], Ad-Hoc On-Demad Distance Vector Routing (AODV) [6], Định tuyến theo thông tin vị trí địa lý (geographic routing) là một nhánh nghiên cứu của vấn đề định tuyến trong mạng WSN và có khả năng nâng cao hiệu suất định tuyến một cách đáng kể do các nút không cần lưu trữ và cập nhật bảng định tuyến tới từng nút trong mạng [7]. Có nhiều giao thức định tuyến sử dụng thông tin vị trí địa lý đã được trình bày, đề xuất như GPSR [3], DRQC [8], GOAFR [9] [2]. Tổng hợp lại từ các giao thức đã được đề xuất có thể đúc kết ra một vài chiến lược định tuyến như chiến lược tham lam [7], chiến lược tham lam kết hợp đi vòng [7] chiến lược phát tràn [6], chiến lược phân chia nút theo góc phần tư [1]. Trong đó chiến lược định tuyến phân chia nút theo góc phần tư là một chiến lược có nhiều ưu điểm do kết hợp được tính hiệu quả của chiến lược tham lam và tránh được vùng trống sớm. Trong luận văn này tôi tập trung trình bày về chiến lược định tuyến dựa theo phân chia nút theo góc phần tư. Cụ thể, luận văn nghiên cứu chi tiết giao thức DRQC [8], từ đó đánh giá và phát hiện hạn chế của giao thức này. Dựa trên phân tích về hạn chế của giao thức DRQC, một cải tiến mới cho thuật toán, được đặt tên là DR-CR (Detour Routing based on Coordination Rotation), được đề xuất. Các thí nghiệm mô phỏng đánh giá hiệu năng của đề xuất được thực hiện và cho thấy đề xuất cải tiến có thể nâng cao hiệu năng của định tuyến so với giao thức DRQC gốc và cao hơn giao thức GPSR, một giao thức nổi tiếng và phổ biến trong mạng WSN. Việc mô phỏng, đánh giá hiệu năng được trình bày trong luận văn dựa trên công cụ mô phỏng sự kiện mạng Network Simulation 3 (NS-3) [10][11]. Đây là một công cụ mô phỏng sự kiện mạng được phát triển sau NS-2 và có nhiều cải tiến về mặt cấu trúc để nhà phát triển có thể tự do hơn khi thực thi các giao thức mạng. Đồng thời việc mô phỏng cũng được thực hiện hiệu quả hơn và chi tiết hơn với nhiều khả năng đưa các sự kiện mô phỏng vào hệ thống [10]. Hạn chế của NS-3 so với công cụ NS-2 là số lượng các thư viện giao thức đã được tích
  13. 13 hợp vào NS-3 là ít hơn so với NS-2 do cộng đồng người sử dụng NS-3 còn chưa đông. Để thực hiện luận văn, các giao thức DRQC và DR-CR (DRQC cải tiến) được thực hiện theo các quy định lập trình của NS-3. Phần triển khai của giao thức GPSR là được sử dụng lại mã nguồn GPSR của cộng đồng phát triển NS-3. Việc lựa chọn NS-3 thay vì NS-2 là nhằm mục đích khám phá khả năng của một công cụ phục vụ nghiên cứu mới. Tuy nhiên mục tiêu này không là mục tiêu chính của luận văn. Nội dung của bài Luận văn gồm có 4 chương chính Chương 1- Giao thức định tuyến theo thông tin địa lý Tóm lược tổng quan về giao thức định tuyến theo thông tin vị trí địa lý trong mạng cảm biến không dây, các chiến lược định tuyến trong mạng không dây. Trong chương 1, còn tập trung giới thiệu về giao thức định tuyến “Greedy Perimeter Staless Routing”, là giao thức định tuyến áp dụng chiến lược định tuyến tham lam phổ biến và hiệu quả. Chương 2 – Giao thức định tuyến “Detour Routing Based on Quadrant Classification” Giới thiệu giao thức định tuyến địa lý “Detour Routing Based on Quadrand Classification – DRQC” [8] đã được nhóm tác giả công bố trong một số công trình nghiên cứu của họ. Kiến thức phần chương 2 tập trung phân tích và giới thiệu về giao thức định tuyến đi vòng dựa trên phân loại nút theo góc phần tư giúp làm cơ sở cho sự cải tiến giao thức DR-CR ở chương 3. Chương 3 – Giao thức Detour Routing based on Coordinates Rotation Nội dung chương 3, phân tích một số hạn chế của giao thức DRQC. Trong chương 3, chúng tôi đề xuất giải pháp quay trục giúp cho định tuyến gói tin hiệu quả hơn. Cải tiến mới này được đặt tên là Detour Routing based on Coordination Rotation (DR-CR). Chương 4 – Đánh giá hiệu năng Giới thiệu về kịch bản mô phỏng, đánh giá hiệu năng của ba giao thức định tuyến GPSR, DRQC và DR-CR (cải tiến từ DRQC), cũng như đánh giá và nhận xét về tỷ lệ chuyển tiếp gói tin thành công, thông lượng trung bình của ba giao thức trong từng trường hợp khác nhau.
  14. 14 Kết luận Phần này đưa ra một số kết quả đạt được của quá trình nghiên cứu luận văn, rút ra một số hạn chế, vấn đề gặp phải. Phần này sẽ trình bày một số định hướng tiếp theo giúp hoàn thiện vấn đề nghiên cứu trong tương lai.
  15. 15 Chương 1. GIAO THỨC ĐỊNH TUYẾN THEO THÔNG TIN VỊ TRÍ ĐỊA LÝ 1.1. Tổng quan về giao thức định tuyến theo thông tin vị trí địa lý Với sự phát triển ngày càng nhanh của hệ thống mạng máy tính không dây như: Wireless Network, Ad hoc network, Sensor network cũng như yêu cầu về chất lượng của các dịch vụ của các ứng dụng mạng ngày càng cao dẫn tới phát triển và cải tiến các thuật toán về định tuyến (quyết định đường đi một gói tin trên mạng máy tính) trong mạng máy tính không dây. Có rất nhiều thuật toán định tuyến cho mạng không dây như AODV [6], DSR [6], GPSR [3], Hiện nay những thuật toán định tuyến gói tin theo thông tin vị trí địa lý (Geographic Routing Protocol) đã được nghiên cứu rất nhiều, có hơn 50 giao thức đã được đề xuất [2] trong những năm gần đây. Những thuật toán định tuyến địa lý Geographic Routing Protocols (GRP) dùng thông tin vị trí địa lý của các thiết bị trong hệ thống mạng để quyết định việc gửi gói tin trong mạng. Không giống như những thuật toán định tuyến theo cấu trúc mạng (Mạng máy tính có dây), các thuật toán định tuyến địa lý không cần phải duy trì và cập nhật thông tin bảng định tuyến [7]. GRP sử dụng thông tin địa lý – Global Positioning System (GPS) để định tuyến. Nhiều thuật toán định tuyến theo vị trí địa lý sử dụng chiến lược tham lam (greedy) nhằm cố gắng tiếp cận tới vị trí nút đích trong mỗi bước chuyển tiếp gói tin theo một tiêu chí tối ưu nào đó. Tuy nhiên, nhiều thuật toán tham lam sẽ thất bại hoặc có hiệu suất định tuyến không cao trong các trường hợp có quá ít các nút trong phạm vi định tuyến – vùng trống (void area). Chính vì vậy, có rất nhiều thuật toán cải tiến hoặc kết hợp các chiến lược tìm kiếm khác nhau để xây dựng nên những thuật toán định tuyến tối ưu cho các trường hợp khác nhau (GPSR [3], GOAFR [9]) Định tuyến theo thông tin địa lý – định tuyến địa lý (định tuyến dựa trên vị trí địa lý hoặc là định tuyến theo hình học, là kỹ thuật gửi gói tin trong mạng qua rất nhiều nút trung gian (Hops) bằng cách sử dụng thông tin chính là thông tin vị trí địa lý của mỗi nút. GRP quyết định đường đi gói tin không được xây dựng từ những địa chỉ mạng và bảng định tuyến chứa thông tin về định tuyến mà mỗi nút trong mạng sẽ sử dụng thông tin vị trí địa lý của các nút kề nó (nút hàng xóm). Mỗi một nút có thể chọn một nút hàng xóm là nút chuyển tiếp dựa theo một tiêu chí tối ưu nào đó (ví dụ nút hàng xóm gần nút đích nhất). Nút này sẽ chuyển tiếp thông tin tới nút đích qua các bước tiếp theo. Thực chất mỗi nút sẽ không có bảng định tuyến, cũng không có những thiết bị định tuyến. Các giao thức định
  16. 16 tuyến địa lý rất cần thiết cho những mạng có sự thay đổi về cấu trúc như mạng không dây, mạng ad-hoc, mạng cảm biến, . Trong mạng không dây định tuyến truyền thống sử dụng thông tin bảng định tuyến và trạng thái liên kết là rất tốn kém [7]. Các thuật toán định tuyến truyền thống sử dụng bảng định tuyến yêu cầu chi phí cho xử lý và gửi nhận thông tin quảng bá là rất lớn và thường xuyên phải cập nhật thông tin cho bảng định tuyến đối với những cấu trúc mạng luôn thay đổi. Ngược lại, những thuật toán định tuyến địa lý được thiết kế để làm việc với những cấu trúc mạng có trạng thái luôn thay đổi và hỗ trợ tốc độ cấp phát gói tin cao trong các mạng di động. Tất cả nhũng thuật toán về định tuyến địa lý đều tuân theo nhưng yêu cầu sau [7]: - Một nút có thể xác định thông tin vị trí của chính nút đó. - Một nút có thể biết vị trí của nút hàng xóm với nó. - Trước khi chuyển tiếp thông tin phải biết trước vị trí nút đích. Với yêu cầu thứ nhất, bằng các hệ thống GPS hoặc những hệ thống vệ tinh dò tìm chuyển hướng cơ bản, thông tin về vị trí của những thiết bị rất nhỏ có thể được dễ dàng xác định. Hơn nữa hệ thống dò tìm vị trí cho những ứng dụng trong nhà, các thiết bị có kích thước nhỏ đã được phát triển từ rất sớm và ngày càng phát triển. Với yêu cầu thứ 2, các nút cần quảng bá thông tin vị trí tới những thành phần khác của mạng và thông tin vị trí của một nút sẵn sàng để tính toán các nút tiếp theo gần với nút đích nhất trong quá trình định tuyến. Điều kiện chính để có những yêu cầu giả định trên là phải có hệ thống thông tin vị trí địa lý GPS. Nếu GPS sẵn sàng cho các nút mạng thì định tuyến theo thông tin vị trí sẽ hỗ trợ một cách hiệu quả và mở rộng các giải pháp cho định tuyến trong mạng không dây và di động. Để xác định các nút tiếp theo trong quá trình định tuyến, Có rất nhiều các chiến lược định tuyến và mỗi chiến lược định tuyến đều có những ưu và nhược điểm khác nhau. Các nút mạng luôn bị ràng buộc về phạm vi truyền tải thông tin, khi một nút không có các nút hàng xóm nào trong phạm vi truyền tin của nó, trong trường hợp này gói tin chuyển tiếp sẽ bị giữ lại và bị xóa. Luận văn sẽ trình bày một vài chiến lược tìm kiếm đường đi phổ biến trong định tuyến sử dụng thông tin vị trí địa lý mạng không dây ở phần tiếp theo.
  17. 17 1.2. Các chiến lược định tuyến trong định tuyến địa lý 1.2.1. Chiến lược định tuyến tham lam Một trong những phương pháp được đề xuất đầu tiên cho việc định tuyến địa lý được công bố trong những năm 1980 là chiến lược định tuyến tham lam [7]. Tất cả các giao thức định tuyến áp dụng theo chiến lược tham lam thì tại các nút thực hiện chuyển tiếp sẽ quyết định chuyển tiếp gói tin một cách tối ưu theo một tiêu chí tối ưu nhất so với nút hiện tại đang thực hiện tính toán. Việc lựa chọn nút tiếp theo – next hops (Thiết bị mạng chuyển tiếp gói tin) theo chiến lược chuyển tiếp tham lam dự trên những tiêu chí sau [7]: - Progess (Khoảng cách tới đích): khoảng cách ngắn nhất của hình chiếu các nút trên trục st (trục đích nguồn) (Hình 1-1): - Khoảng cách tới đích ngắn nhất: Là khoảng cách địa lý từ chính các nút đến nút đích (Hình 1-1). - Góc xa, góc tách (góc tạo bởi nút nguồn - nút hàng xóm với trục nguồn đích) (Hình 1-1). Hình 1-1. Các tiêu chí lựa chọn trong chiến lược tham lam1 Ví dụ Hình 1-1, giải thích chi tiết các tiêu chí lựa chọn tham lam tối ưu cho việc định tuyến gói tin trong mạng máy tính không dây. - NC (Nearest closer): Lựa chọn theo tiêu chí nút hàng xóm ngần nút nguồn nhất. - Greedy (Tham lam): Lựa chọn tiêu chí khoảng cách ngắn nhất từ nút đích tới các nút hàng xóm. 1 Nguồn: tài liệu [7]
  18. 18 - CR (Compass Routing): Lựa chọn tiêu chí góc tạo bởi nút hàng xóm, nút nguồn, nút đích là nhỏ nhất. - NFP : Lựa chọn nút hàng xóm có khoảng cách hình chiếu gần nút nguồn nhất. - MFR: Lựa chọn nút hàng xóm có khoảng cách hình chiếu gần nút đích nhất. Chiến lược chuyển tiếp tham lam có một nhược điểm quan trọng: khi số lượng các nút mạng trong một vùng diện tích rất ít hoặc không có hàng xóm nào gần với nút đích nhất trong mọi trường hợp thì việc định tuyến sẽ không thực hiện thành công. Trong trường hợp này chiến lược định tuyến cần tới một vài thao tác đơn giản để tiếp tục định tuyến bằng chiến lược tham lam. Phương thức GEDIR [5] là một chiến lược định tuyến tham lam cùng với các bước quay lui. Khi một thông tin định tuyến tìm thấy vùng trống (void area), thì nó sẽ gửi gói tin về đúng nút đã chuyển tiếp trước đó, áp dụng lại quy tắc tham lam khi thực hiện việc tìm kiếm nút kết thúc từ vùng lựa chọn, đó là chiến thuật lặp tự do. Để cải thiện hiệu suất cho các thuật toán tham lam áp dụng lựa chọn MFR và CR nếu tồn tại sẵn thông tin của nút hàng xóm cấp 2 (2- neighbhors) tương ứng của mỗi nút. Một số thuật toán tham lam sử dụng thông tin của nút hàng xóm cấp 2 đã được thiết kế tuy nhiên có thể làm tăng thời gian của độ trễ truyền tin. Các thuật toán tham lam với hàng xóm cấp 2 có thể được thêm vào các thuật toán thông minh để ngăn chặn những vùng trống trong định tuyến. 1.2.2. Chiến lược định tuyến đi vòng Khi định tuyến gói tin gặp phải vùng trống trong quá trình định tuyến, trong trường hợp này gói tin sẽ không đi qua được các vùng trống theo chiến lược tham lam. Một số thuật toán đã được áp dụng để gói tin có thể vượt qua được các vùng trống. Tuy nhiên, định tuyến theo đồ thị phẳng là chiến lược thường được sử dụng và thường áp dụng cùng với chiến lược tham lam. Định tuyến đồ thị phẳng (Planar Graph Routing) [7] là chiến lược định tuyến theo thông tin địa lý chuyển tiếp gói tin qua những vùng trống (void area) dựa vào các nút xung quanh vùng viên của các mặt phẳng theo quy tắc “bàn tay phải” hoặc “bàn tay trái”. Vùng trống (vùng tối thiểu) luôn tồn tại các nút mạng quanh vùng biên của những vùng trống, tại các vùng biên một nút cần chuyển tiếp gói tin không thể tìm thấy một hàng xóm nào gần với đích hơn chính nó, nút như vậy còn gọi là nút chết. Đồ thị phẳng là một nội dung quan trọng cho quá
  19. 19 trình phục hồi đường định tuyến gói tin từ những vấn đề vùng tối thiểu (Local minimum) (Hình 1-2). Định tuyến đồ thị phẳng được xây dựng trên ý tưởng là mọi liên kết các vị trí là một mạng truyền thông nằm trên các đồ thị phẳng. Và một gói tin có thể chuyển tiếp thành công qua các mặt phẳng của đồ thị. Định tuyến phụ thuộc vào mặt phẳng có nghĩa là các nút của mặt phẳng chuyển tiếp thông tin qua vùng mạng biên bằng cách áp dụng quy tắc “Bàn tay phải” hoặc “Bàn tay trái”. Quy tắc này rất tốt để giải quyết vấn đề chuyển gói tin qua vùng trống. Một nút tìm kiếm các nút khác trong đường định tuyến nhằm để giải quyết vấn đề vùng trống luôn tìm kiếm theo một con đường duy nhất là gửi gói tin đến các nút bên trái hoặc gửi gói tin đến các nút bên phải. Kỹ thuật chuyển tiếp gói tin dựa theo quy tắc bàn tay phải đã được các tác giả trình bày chi tiết trong tài liệu [7]. Hình 1-2. Chiến lược định tuyến phẳng trong định tuyến địa lý2 Hình 1-2, các mặt phẳng F1, F2, F3, F4 được tạo bởi các nút mạng. Khi áp dụng quy tắc bàn tay phải hoặc bàn tay trái. Thuật toán sẽ tìm kiếm một đường chuyển tiếp gói tin từ nút nguồn {s} tới nút đích {t} bằng cách chuyển tiếp qua các đường biên của từng mặt phẳng. 1.2.3. Chiến lược định tuyến phát tràn Phát tràn là một chiến lược định tuyến đơn giản trong việc tìm kiếm đường đi của gói tin. Phát tràn sẽ gửi các gói tin qua tất cả các hàng xóm ngoại trừ nút chuyển tiếp trước nó. Có hai loại thuật toán phát tràn chính là pháp tràn không kiểm soát (Uncontrolled Flooding) và phát tràn có kiểm soát (Control Flooding). Thuật toán phát tràn không kiểm soát có thể gây ra các vấn đề nghiêm trọng trong quá trình quảng bá gói tin. Tất cả các nút có hàng xóm sẽ gửi gói tin 2 Nguồn: tài liệu [7]
  20. 20 quảng bá vô thời hạn. Nếu một nút có nhiều hơn hai hàng xóm thì dẫn đến vấn đề gây bảo gói tin quảng bá. Thuật toán phát tràn có kiểm soát được chia thành hai thuật toán định tuyến chính là phát tràn có kiểm soát số tuần tự - Sequence Number Controlled Flooding (SNCF) và phát tràn đường đi ngược - Reverse Path Flooding (RPF). Trong SNCF, mỗi nút sẽ gửi kèm theo địa chỉ của chính nó và số thứ tự vào gói tin. Mỗi nút đều có một bộ nhớ và lưu số thứ tự. Nếu một nút nào đó nhận được gói tin có số thứ tự và địa chỉ tồn tại trong bộ nhớ, nó sẽ bị loại bỏ tức thì. Trong khi đó RPF thì mỗi nút sẽ gửi duy nhất gói tin chuyển tiếp. Nếu nó nhận được gói tin từ nút tiếp theo phản hồi về, nó sẽ gửi lại thông tin cho nút chuyển tiếp trước đó. Tất cả các giao thức sử dụng chiến lược phát tràn đều có thuật toán làm việc tương đối giống nhau với đặc điểm: - Mỗi nút hoạt động như một thiết bị phát và thiết bị thu. - Mỗi nút sẽ cố gắng gửi tất cả các gói tin tới các nút hàng xóm ngoại trừ nút chuyển tiếp trước đó. Kết quả nhận được là tin nhắn cuối cùng sẽ tìm ra đường đi của gói tin trong mạng. Thuật toán có thể cần nhiều yêu cầu phức tạp hơn nhiều, trong một số trường hợp, sẽ kiểm tra các gói tin nhận được của các nút để tránh sự trùng lặp và gói tin gửi đi vô hạn trong mạng. Một vài giao thức cải tiến của thuật toán phát tràn gọi là phát tràn có chọn lọc nhằm giải quyết vấn đề chỉ gửi gói tin đến những nút có cùng hướng với nút đích. Trong thuật toán phát tràn có chọn lọc các bộ định tuyến không gửi gói tin đến tất cả các nút mà chỉ những nút có cùng hướng với nút đích [6]. Lợi ích của thuật toán Khi gửi một gói tin qua mạng, gói tin sẽ tìm kiếm tất cả các đường đi tới đích để chọn được đường đi ngắn nhất. Đây là thuật toán đơn giản, dễ triển khai, cài đặt. Hạn chế - Phát tràn có thể sẽ gây tốn kém về băng thông. Trong khi một tin nhắn chỉ có một điểm đến, nó phải gửi đi tất cả các nút khác trong mạng. Trong trường hợp này sẽ gây ra quá tải về băng thông và dễ bị tấn công từ chối dịch vụ.
  21. 21 - Gói tin có thể được sao chép và tiếp tục được tải lên mạng và đòi hỏi thuật toán phải xử lý phức tạp để loại bỏ những gói tin này. - Các gói tin trùng lặp có thể lưu trữ mãi mãi. Trừ khi các biện pháp phòng ngừa không được thực hiện. 1.3. Giao thức định tuyến “Greedy Perimeter Stateless Routing” 1.3.1. Tổng quan Greedy Perimeter Stateless Routing (GPSR) là một thuật toán định tuyến cổ điển cho mạng chuyển mạch gói không dây. GPSR dùng thông tin vị trí địa lý của các thiết bị chuyển tiếp (Router) và thông tin vị trí của nút đích để quyết định đường đi tiếp theo cho gói tin. GPSR chuyển tiếp gói tin sử dụng thuật toán tham lam. Thuật toán tham lam dùng duy nhất thông tin vị trí địa lý của các thiết bị trong hệ thống mạng để chuyển tiếp và thông tin vị trí địa lý của hàng xóm hiện thời trong cấu trúc mạng, khi thuật toán tham lam không tìm thấy một nút mạng tiếp theo của đường đi gói tin tới đích thì định tuyến gói tin trên mặt phẳng được áp dụng để chuyển tiếp gói tin và phục hồi lại đường đi (chiến lược phục hồi). Chiến lược phục hồi chuyển tiếp gói tin xung quanh mặt phẳng tạo bởi các vùng trống trong hệ thống mạng, khi các điều kiện áp dụng thuật toán tham lam được phục hồi thì GPSR sẽ áp dụng thuật toán tham lam thay vì định tuyến đồ thị phẳng. GPSR lưu giữ lại duy nhất thông tin cục bộ vị trí của các nút mạng nên GPSR sẽ được mở rộng tốt hơn nếu quy mô mạng tăng hơn các thuật toán short-path và ad-hoc routing theo tài liệu [3]. Trong hệ thống mạng gồm toàn bộ các trạm không dây, giao tiếp qua lại giữa những nút đích và nút nguồn có thể phải qua rất nhiều nút trung gian. Trong cộng đồng các nhà nghiên cứu, nhiều thuật toán định tuyến cho mạng không dây đã được đề xuất, thực hiện và kiểm chứng. Sự thay đổi cấu trúc mạng trong mạng không dây là lớn hơn đối với mạng có dây. Trên hệ thống mạng có dây, việc sử dụng các thuật toán định tuyến Distance Vector (DV) [1] và Link state (LS) [6] là rất hiệu quả và được phát triển từ rất sớm, tuy nhiên một thuật toán định tuyến luôn luôn phụ thuộc vào các yếu tố như: - Tốc độ thay đổi của cấu trúc mạng - Số lượng các nút mạng trong hệ thống Cả hai yếu tố này sẽ làm cho thuật toán DV và LS trở nên phức tạp nếu như áp dụng trong mạng không dây có tốc độ thay đổi cấu trúc lớn và số lượng
  22. 22 các nút mạng nhiều. Vì vậy, một thuật toán định tuyến đã được đề xuất từ rất sớm cho mạng không dây đó là: “Greedy Perimete Stateless Routing (GPSR)”. GPSR mục đích mở rộng số lượng các nút mạng và tăng tốc độ thay đổi cấu trúc mạng. Những yếu tố được sử dụng để đánh giá cho giao thức định tuyến là: - Chi phí giao thức gửi thông điệp: làm thế nào để các gói tin được gửi đi là nhiều nhất. - Tỷ lệ gói tin được gửi thành công: các gói tin gửi và chuyển thành công tới đích như thế nào? - Trạng thái của nút: mỗi nút sẽ lưu trữ dữ liệu thế nào. 1.3.2. Thuật toán định tuyến GPSR Trong giao thức định tuyến GPSR, các gói tin được chuyển tiếp dựa trên sự kết hợp của hai phương thức chuyển tiếp là: Chuyển tiếp tham lam – Greedy forwarding và chuyển tiếp xung quanh vùng trống (Perimeter forwarding). 1.3.2.1. Chuyển tiếp tham lam trong GPSR Hình 1-3. Chuyển tiếp tham lam trong GPSR3 Các gói tin trong mạng được gán các thông tin về vị trí địa lý của nút nguồn và nút đích. Mỗi một nút trong mạng sẽ biết được thông tin về vị trí của các nút hàng xóm với nó. Một nút thực hiện chuyển tiếp sẽ tính toán lựa chọn một trong số các nút hàng xóm của nó ngần với nút đích nhất dựa theo thông tin về vị trí nút đích và nút nguồn gán trong gói tin nó nhận được. Các bước chuyển tiếp sẽ được thực hiện lặp lại tại mỗi nút khi nhận được gói tin cho tới khi gói tin được gửi tới nút đích. 3 Nguồn: tài liệu [3]
  23. 23 Ví dụ chuyển tiếp tham lam trong Hình 1-3, khi nút x nhận được một gói tin gửi đến nút đích D, x xem xét các nút trong phạm vi phủ sóng tín hiệu của nó. Nút x sẽ gửi gói tin tới nút y vì trong phạm vi phủ sóng của nút x không có nút khác ngoài nút y có khoảng cách gần với nút D nhất. Quá trình chuyển tiếp tham lam này sẽ được lặp lại cho tới khi gói tin đến được nút D. Hình 1-4. Vấn đề vùng trống trong GPSR4 Nếu giữa nút D và nút x không tồn tại một nút trung gian nào có khoảng cách gần với đích nhất hơn chính nút x và là hàng xóm của nút x, thì vấn đề vùng trống xảy ra. Trong Hình 1-4, có 2 trường hợp gói tin được chuyển tới nút D như sau: x->y->z->D hoặc x->w->v->D. Tuy nhiên thuật toán chuyển tiếp tham lam sẽ không sử dụng cho hai trường hợp này. 1.3.2.2. Chuyển tiếp vùng biên (Perimeter Forwarding) Trong giao thức định tuyến GPSR, khi một nút không tìm thấy các nút hàng xóm thỏa mãn điều kiện chỉ ra trong lựa chọn tham lam thì chiến lược định tuyến dựa trên đồ thị phẳng và quy tắc bàn tay phải được áp dụng [3]. Việc kết hợp chuyển tiếp tham lam và chuyển tiếp vùng biên trong giao thức định tuyến GPSR giúp cải thiện hiệu suất định tuyến gói tin. 4 Nguồn: tài liệu [3]
  24. 24 Hình 1-5. Quy tắc bàn tay phải5 Hình 1-5, quy tắc bàn tay phải được áp dụng để gửi gói tin qua một mặt phẳng được tạo bởi các nút mạng xung quanh vùng trống. Khi gói tin được gửi qua các nút y, x, z, qua mỗi nút gói tin sẽ được gửi đi theo cạnh bên phải của hình đa giác tạo bởi các nút. Thứ tự gói tin sẽ đi qua mặt phẳng đa giác (Hình 1- 5) là y -> x -> z -> y. 5 Nguồn: tài liệu [3]
  25. 25 Chương 2. GIAO THỨC ĐỊNH TUYẾN “DETOUR ROUTING BASED ON QUADRANT CLASSIFICATION” 2.1. Tổng quan Những vùng trống trong các cấu trúc mạng không dây như sông, hồ, rừng, núi, luôn dẫn đến hiệu suất định tuyến gói tin không hiệu quả. Vấn đề vùng trống trong cấu trúc mạng không dây luôn là thách thức đối với các giao thức định tuyến không dây. Để cải thiện hiệu suất trong các trường hợp này, thuật toán định tuyến sử dụng thông tin vị trí địa lý áp dụng phương pháp tìm kiếm tham lam để tìm kiếm thông tin về đường đi tới nút đích mà không phải lưu trữ và bảo trì thông tin bảng định tuyến. Tuy nhiên, thuật toán tham lam định tuyến gói tin không thành công hoặc hiệu suất thấp nếu gặp các vấn đề về vùng trống (void area). Trong phần này tôi sẽ trình bày và phân tích thuật toán định tuyến dựa trên phân chia góc phân tư “Detour Routing based on Quadrant Classification (DRQC)” đã được tác giả trong tài liệu [8] đề xuất để giảm thiểu xảy ra vấn đề vùng trống bằng cách ngăn chặn gửi gói tin đi, đến các vùng trống trong cấu trúc mạng. Ý tưởng cơ bản của thuật toán là, mỗi nút sẽ biết được thông tin vị trí địa lý của chính nó và thông tin vị trí của các nút hàng xóm cấp 1 (1-hop neighbors) và hàng xóm cấp 2 (2-hop neighbors). Các nút cũng sẽ xác định trạng thái của nó là nút đỏ hoặc nút trắng. Một nút là nút đỏ nếu nó không có vấn đề vùng trống, ngược lại một nút là nút trắng nếu có khả năng xảy ra vấn đề vùng trống. Trong quá trình xử lý định tuyến DRQC yêu cầu mỗi nút phải chọn một hàng xóm cấp 2 là nút đỏ và có khoảng cách tới nút đích là ngắn nhất. Nếu không có nút nào thỏa mãn điều kiện trên thì thuật toán tham lam tìm kiếm với hàng xóm cấp 2 được áp dụng. Vì các kiến trúc mạng không dây luôn thay đổi nên một chiến lược đơn giản cho định tuyến trong mạng Wireless Sensor Network là chiến lược phát tràn (flooding) giúp cho việc tìm kiếm đường đi của gói tin hiệu quả. Tuy nhiên, phương thức này không thực sự hiệu quả trong các kiến trúc mạng quan tâm tới năng lượng và băng thông đường truyền, bởi vì có rất nhiều các nút mạng phải thực hiện chuyển tiếp gói tin quảng bá và các nút cũng phải xử lý rất nhiều gói tin được gửi tới mà không thật sự cần thiết. Có những giao thức định tuyến khác sử dụng thuật toán tham lam để định tuyến, những thuật toán này hiệu quả hơn so với các thuật thoán phát tràn [8]. Thông thường thuật toán tham lam mỗi một nút yêu cầu giao tiếp duy nhất với
  26. 26 hàng xóm cấp 1 của chính nó. Một hàng xóm cấp 1 có khoảng cách gần với đích nhất sẽ được chọn là nút chuyển tiếp (next hop) để chuyển tiếp gói tin. Thuật toán tham lam được đề xuất rất hiệu quả kể cả trong các mạng thường xuyên thay đổi. Tuy nhiên thuật toán có thể định tuyến không thành công khi gặp các vấn đề về rào cản tự nhiên (sông, hồ, núi, đồi ) [8], khi đó một nút không thể tìm được nút chuyển tiếp tiếp theo bởi vì không có hàng xóm nào của nó gần với nút đích hơn chính nó. 2.2. Chuyển tiếp tham lam và vấn đề vùng trống trong DRQC 2.2.1. Chiến lược chuyển tiếp tham lam Với chiến lược định tuyến tham lam, một nút sẽ xử lý các thông tin vị trí một cách tối ưu để quyết định chọn nút tiếp theo cho chuyển tiếp gói tin. Để thực hiện điều đó, một nút phải biết được vị trí của hàng xóm của chính nó để chọn nút hàng xóm có khoảng cách địa lý gần nhất với nút đích. Có hai phương pháp để tối ưu bằng chiến lược tham lam là: Chiến lược định tuyến tham lam với hàng xóm cấp 1 (1- hop greedy) và chiến lược tham lam với hàng xóm cấp 2 (2- hop greedy). Sự khác biệt chính giữa hai chiến lược này là một nút chọn nút tiếp theo của chuyển tiếp bằng cách xem xét mỗi hàng xóm cấp 1 hoặc là hàng xóm cấp 2. Hình 2-1. Định tuyến gói tin theo chiến lược tham lam6 Hình 2-1 minh họa về chiến lược định tuyến tham lam theo hàng xóm cấp 1. Nút nguồn A muốn gửi gói tin tới nút đích J. Nút A sẽ xem xét các hàng xóm cấp 1 liền kề với chính nó là {B;E} khi đó B sẽ được chọn là nút chuyển tiếp bởi vì khoảng cách từ B đến J sẽ ngắn nhất. Khi nút B nhận được gói tin, nút B cũng sẽ thực hiện việc việc lựa chọn nút C là nút chuyển tiếp trong danh sách hàng 6 Nguồn: tài liệu [8]
  27. 27 xóm cấp 1 của chính nút B. Các bước lựa chọn nút chuyển tiếp sẽ lặp lại cho đến khi gói tin đến được nút đích J. Hình 2-1 minh họa về chiến lược chuyển tiếp gói tin tham lam theo hàng xóm cấp 2. Nút nguồn A gửi gói tin đến nút đích J. Tại nút A sẽ xem xét các nút hàng xóm cấp 2 của chính nó là {C;G;H} khi đó nút C sẽ được chọn như là nút chuyển tiếp gói tin vì nút C có khoảng cách gần nhất tới nút đích so với các nút G và H. Thuật toán sẽ tiếp tục thực hiện cho tới khi gói tin được gửi tới nút đich. 2.2.2. Vấn đề vùng trống trong giao thức DRQC Có nhiều giao thức định tuyến địa lý dùng chiến lược tham lam để chuyển tiếp gói tin tới đích, các giao thức chọn nút chuyển tiếp thuộc hàng xóm của nút gửi sao cho nút hàng xóm là nút có khoảng cách ngắn nhất tới nút đích chúng được gọi là các nút tiếp theo (Next hop). Tuy nhiên rào cản trong các địa hình tự nhiên thường dẫn đến chiến lược tham lam sẽ bị lỗi khi tìm kiếm đường đi bởi vì các rào cản tồn tại trong địa hình tự nhiên, khi đó nhiều nút có thể không thể tìm thấy các nút hàng xóm gần với nút đích hơn chính nút đó. Vấn đề này được gọi là vùng tối thiểu - local minima (vùng trống). Khi vấn đề local minima xảy ra trong quá trình chuyển tiếp một gói tin, có nhiều giao thức định tuyến đã xóa gói tin tuy nhiên vẫn có khả năng tìm thấy đường đi tới đích. Hình 2-2. Vùng trống trong giao thức DRQC7 Hình 2-2, nút nguồn A gửi gói tin đến nút đích J, khi gói tin được gửi tới nút tiếp theo là D. Tại nút D các chiến lược tìm kiếm tham lam sẽ so sánh khoảng cách các nút hành xóm của D với chính nút D. Trong trường hợp này sẽ không có nút hàng xóm nào thỏa mãn là hàng xóm của D và có khoảng cách gần nhất với nút đích khác D. Chính vì vậy gói tin gửi tới D sẽ bị xóa, điều đó dẫn đến việc gửi gói tin từ A đến J sẽ không thực hiện thành công đối với các chiến 7 Nguồn: tài liệu [8]
  28. 28 lược tham lam. Để giải quyết vấn đề này, các thuật toán định tuyến đã kết hợp nhiều chiến lược tìm kiếm để có thể gửi gói tin đến nút đích bằng nhiều cách. 2.3. Thuật toán định tuyến trong giao thức DRQC Để giao thức định tuyến DRQC có thể thực hiện được thì phải đảm bảo yêu cầu: - Mỗi nút yêu cầu phải có thông tin về vị trí của nó từ các hệ thống định vị vị trí và quảng bá vị trí của nó tới các nút hàng xóm cấp liền kề với nó. - Các nút trong mạng đều cùng dãi giao tiếp. - Các rào cản trong mạng là cố định (theo rào cản tự nhiên là có định) 2.3.1. Khái niệm, định nghĩa Thuật toán định tuyến trong giao thức DRQC định nghĩa một số khái niệm về nút: - Nút nguồn (Source node): là nút sinh ra gói dữ liệu để gửi đi trong mạng. - Nút đích (Destination node): là nút nhận được gói dữ liệu được gửi đi trong mạng. - Nút xử lý lựa chọn (Prober): là nút xử lý lựa chọn nút tiếp theo trong quá trình định tuyến gói tin. - Nút chuyển tiếp (Forwarder): là nút được chọn bởi nút Prober. Hình 2-3. Định nghĩa các nút trong DRQC Hình 2-3: Nút S gọi là nút nguồn. Nút D là nút đích. Nút {S, X} thực thi lựa chọn nút tiếp theo được gọi là Prober. Nút {X, Z} là nút chuyển tiếp (Forwarder). 2.3.2. Trạng thái của các nút Trong giao thức DRQC định nghĩa mỗi nút có thể mang một trong hai trạng thái là nút đỏ hoặc nút trắng như sau:
  29. 29 - Nút đỏ: Một nút được gọi là nút đỏ nếu có ít nhất một nút hàng xóm cấp 2 tồn tại trong mỗi một góc ¼. - Nút trắng: một nút được gọi là nút trắng nếu không có một nút hàng xóm cấp 2 tồn tại trong ít nhất một góc ¼. Hình 2-4. Trạng thái của nút trong DRQC8 Ví dụ trong hình 2-4: nút S có các hàng xóm cấp 2 ở các góc phần tư do đó nút S có trạng thái là nút đỏ. Ngược lại các nút như H, N, E có trạng thái là nút trắng vì trong các góc phần tư của mỗi nút không tồn tại đầy đủ hàng xóm cấp 2. 2.3.3. Định dạng thông điệp gửi Để gửi và nhận các gói thông tin về vị trí địa lý cũng như các gói thông tin dữ liệu, trong giao thức DRQC đã định nghĩa một số kiểu thông điệp gồm thông tin quảng bá - Hello message dùng để gửi và nhận các gói thông tin quảng bá thông tin của các nút, Thông tin gói dữ liệu - Data packet message dùng để gửi gói dữ liệu, Thông tin phản hồi - Detour message dùng để gửi phản hồi về cho nút chuyển tiếp phía trước khi không tìm thấy các nút chuyển tiếp tiếp theo thỏa mãn điều kiện. - Hello message: Mỗi nút gán tọa độ và trạng thái của nút hàng xóm cấp 1 và nút hàng xóm cấp 2 của nó cũng như chính nó vào Message Hello, và quảng bá thông tin đó đi cho các nút khác “ĐỊNH KỲ”. Bảng 2-1 minh họa định dạng của thông điệp quảng bá (Hello message): Bảng 2-1: Định dạng thông điệp quảng bá Coordinate/States Neighbor_Coordinates/States o Trường 1 (Coordinate States) là tọa độ, trạng thái của chính nút quảng bá. 8 Nguồn: tài liệu [8]
  30. 30 o Trường 2 (Neighbor_Coordinate/States) là tọa độ, trạng thái của nút hàng xóm 1 và hàng xóm 2. - Data packet message: Một nút nguồn giao tiếp với nút đích bằng cách gửi đi một gói dữ liệu có định dạng như Bảng 2-2 bao gồm các thông tin: Bảng 2-2: Định dạng thông điệp dữ liệu Source Destination Prober Forwarder Data o Thông tin của nút gửi (Source) o Thông tin nút đích (Destination) o Thông tin nút prober o Thông tin nút forward. o Thông tin của dữ liệu (Data) - Detour message: khi một nút không tìm thấy một nút chuyển tiếp nút đó sẽ sinh ra một thông điệp phản hồi (DETOUR message) yêu cầu nút forwarder phía trước của gói tin thực hiện lại việc chọn một nút forwarder. DETOUR message được chỉ thấy trong Bảng 2-3 gồm các thông tin: Bảng 2-3: Định dạng thông điệp phản hồi Source Destination Blocker Previous_Forwarder Filter Data o Thông tin nút đích, nút nguồn (Source, Destination). o Thông tin nút sinh ra gói tin Detour message (Blocker). o Thông tin về nút đã gửi gói tin phía trước (Previous_Forwarder). o Thông tin về hàng xóm cấp 1, 2 của nút sinh ra gói tin Detour (Filter) o Thông tin dữ liệu đã gửi (Data). 2.3.4. Cấu trúc dữ liệu Để lưu trữ dữ liệu trong quá trình thực hiện xử lý tính toán, giao thức DRQC đã định nghĩa một số kiểu cấu trúc dữ liệu gồm: bảng thông tin định tuyến (Routing table) và bảng thông tin hàng xóm (Neighbor table) - Bảng định tuyến (Routing table): mỗi một nút sẽ cập nhật và duy trì một bảng định tuyến để lưu trữ những thông tin về các nút chuyển tiếp có được trong quá trình định tuyến. Trong cấu trúc dữ liệu (Bảng 2-4) định tuyến gồm có các phần:
  31. 31 Bảng 2-4: Định dạng cấu trúc bảng định tuyến Destination Next_Forwarder Candidates o Thông tin về nút đích (Destination). o Thông tin về nút chuyển tiếp (Next_Forwarder). o Thông tin về hàng xóm cấp 2 của nút có thể được lựa chọn để gửi thông tin tới nút đích (Candidates). - Bảng hàng xóm (Neighbor table): Mỗi một nút sẽ duy trì và cập nhật một bảng thông tin về các nút hàng xóm cấp 1 và các nút hàng xóm cấp 2 ( Bảng 2-5) cũng như thông tin về các góc phần tư chứa các nút hàng xóm. Bảng 2-5: Định dạng cấu trúc bảng hàng xóm Quadrant N1 N2 o Quadrant là trường chứa thông tin về góc phần tư o N1 là các nút hàng xóm cấp 1 o N2 là các nút hàng xóm cấp 2 2.3.5. Thuật toán xử lý định tuyến DRQC. Luồng xử lý định tuyến trong DRQC gồm 2 phần: (1): Khi một nút nhận một gói dữ liệu. (2): Khi một nút nhận gói DETOUR message. Khi một nút v trong mạng nhận một gói dữ liệu được gửi từ nút vs, trong đó chứa thông tin về nút nhận dữ liệu là vd. Nút chuyển tiếp phía trước là vp, nút v sẽ biết rằng có một đường định tuyến từ vs qua vp để đến nút v. Nút v sẽ giữ lại thông tin định tuyến đến chính nó vào trong bảng định tuyến. Sau đó nút v sẽ tìm kiếm trong các hàng xóm trong bảng hàng xóm (Neighbors table) hoặc trong bảng định tuyến (Routing table) để định tuyến một đường đi tới đích. Nếu một định tuyến đựơc tìm thấy thì nó sẽ chuyển tiếp gói tin tới nút chuyển tiếp tiếp theo. Nếu nút v không tìm thấy một hàng xóm cấp 1 có thông tin là nút đích thì nút v sẽ chọn một hàng xóm cấp 2 có tiêu chí là nút đỏ và cùng góc phần tư với nút đích. Nếu có nhiều hơn một lựa chọn thì nút v sẽ chọn một nút nào đó có khoảng cách ngắn nhất đến đích. Tiêu chí lựa chọn thứ 2 được áp dụng nếu các điều kiện phía trước không xảy ra. Nút v sẽ lựa chọn một hàng xóm cấp 2 có trạng thái là nút trắng và có cùng góc với nút đích. Nếu có nhiều hơn một lựa chọn thì v sẽ chọn nút có khoảng cách ngắn nhất tới nút đích. Tiêu chí lựa chọn cuối cùng là chọn một nút hàng xóm cấp 2 có khoảng cách ngắn nhất tới nút
  32. 32 đích hơn chính nút v. Quá trình xử lý tìm nút chuyển tiếp được miêu tả trong [8] Hình 2-5. Trường hợp xấu nhất là nút v không tìm thấy một nút chuyển tiếp nào tới nút đích từ chính những hàng xóm cấp 2 của nó. Trong trường hợp này nút v sẽ chặn gói tin và nó sẽ sinh ra một thông điệp phản hồi không tìm thấy đường đi (DETOUR message) và gửi nó tới nút chuyển tiếp phía trước nút v. Khi một nút v nhận đựơc DETOUR massage cùng mới nội dung chứa thông tin về Detour_vs là nút gửi và Detour_vd là nút nhận thì quá trình xử lý thông điệp tại nút chuyển tiếp phía trước [8] như hình 2-6. Hình 2-5. Các bước xử lý tìm kiếm đường đi
  33. 33 Hình 2-6. Các bước xử lý gói tin phản hồi
  34. 34 Chương 3. GIAO THỨC “DETOUR ROUTING BASED ON COORDINATES ROTATION” 3.1. Hạn chế của giao thức định tuyến DRQC Khi một nút xác định đường đi của gói tin tới nút đích thì nó sẽ xem xét các nút hàng xóm thuộc cùng góc phần tư với nút đích. Dựa theo điều kiện góc phần tư này mà quá trình tìm kiếm đường đi của một gói tin sẽ giảm được chi phí băng thông và thời gian tìm kiếm. Tuy nhiên, trong quá trình tìm hiểu về thuật toán DRQC, tôi đã nhận thấy rằng, trong trường hợp các nút nằm gần kề với nút đích nhưng không nằm cùng góc với nút đích thì vấn đề xác định góc theo thuật toán sẽ có thể dẫn tới việc tìm kiếm đường đi không tối ưu hoặc không thành công. Hình 3-1. Ví dụ định tuyến DRQC không tối ưu Ví dụ (Hình 3-1), Khi nút nguồn S gửi gói tin tới nút đích D. Theo DRQC, nút S sẽ chọn các nút thuộc góc phần tư với nút D, vì vậy S sẽ chọn nút {3} là nút kế tiếp trong đường đi gói tin từ S tới D. Tiếp tục như vậy giao thức DRQC sẽ lần lượt chọn các nút {4, 5} trong quá trình định tuyến. Đường đi của gói tin theo DRQC sẽ là S -> 3 -> 4 -> 5 -> D. Tuy nhiên ta nhận thấy rằng nếu nút S lựa chọn đường đi S -> 1 -> 2 -> D thì chi phí gửi gói tin sẽ hiệu quả hơn. 3.1.1. Nút tối ưu không thuộc góc với nút đích Trong luận văn tôi định nghĩa một khái niệm gọi là “Nút tối ưu không thuộc góc phần tư nút đích”. Đây là những nút mạng tối ưu trong quá trình định tuyến nhưng không thuộc góc phần tư với nút đích khi nằm trong một hệ trục toạ độ (Hình 3-2, Hình 3-3).
  35. 35 Hình 3-2. Nút tối ưu nằm trên trục tọa độ Trường hợp 1: nút nguồn là nút 1 (Hình 3-2): - Các nút {2, 3, 4} nằm trên trục hoành của trục toạ độ nút 1. - Các nút {8, 15} nằm trên trục tung của trục toạ độ nút 1. Các nút {2,3,4,8,15} gọi là các nút biên của nút 1. Vì mỗi nút chỉ có thể nằm trong một góc phần tư duy nhất nên ta có, nếu nút {2,3,4} nằm ở góc phần tư thứ nhất của nút 1 thì nút {5, 8} nằm ở góc phần tư thứ tư. Khi đó nút nguồn 1 muốn gửi gói tin đến nút đích nút 19 thì theo thuật toán DRQC phải đi qua các nút {2, 9, 16, 15}. Tuy nhiên chúng ta nhận thấy nếu gói tin từ nút 1 đi qua nút 8, nút 15 thì chi phí định tuyến sẽ giảm đi rất nhiều. Hình 3-3. Nút tối ưu không thuộc góc phần tư nút đích
  36. 36 Trường hợp 2: nút nguồn là nút S (hình 3-3) - Các nút {3, 4, 5} thuộc góc phần tư thứ nhất cùng với nút đích D. - Các nút {1,2} thuộc góc phần tư thứ 2 không cùng góc với nút đích. Theo giao thức DRQC nếu gói tin gửi từ nút S tới nút D thì sẽ đi qua các nút S – 3 – 4 – 5 – D. Tuy nhiên chúng ta sẽ thấy nếu gói tin đi qua các nút S – 1 – 2 – D thì chi phí định tuyến gói tin sẽ giảm đi rất nhiều. Các nút {1, 2} là những nút tối ưu không thuộc cùng góc phần tư với nút đích. 3.1.2. Ví dụ định tuyến không tối ưu theo DRQC Hình 3-4 minh họa một hệ thống mạng gồm có 56 nút, thực hiện việc gửi gói tin từ nút số 9 đến nút số 45. Hình 3-4. Ví dụ định tuyến không hiệu quả Trong ví dụ hình 3-4, các nút {10,11,12,13,14} thuộc trục hoành (ox) có gốc tọa độ nút số 9, các nút {16,23,30,37} thuộc trục tung (oy) có gốc là nút số 9. Ví dụ nút đích nút số 45, nút 45 sẽ có vị trí gần với trục oy. Theo thuật toán DRQC, tại nút nguồn nút số 9, sẽ lựa chọn nút số 17 là nút hàng xóm cấp 2 và có góc cùng với nút đích. Tuy nhiên nút 23 cũng là nút hàng xóm cấp 2 và có khoảng cách tới đích gần hơn so với nút số 17. Lý do DRQC không lựa chọn nút số 23 là vì nút 23 không thuộc góc phần tư với nút đích, điều này đã dẫn đến hiệu suất định tuyến không hiệu quả khi xảy ra các trường hợp tương tự như ví dụ Hình 3-4.
  37. 37 3.2. Đề xuất giải pháp cải tiến giao thức DRQC Thuật toán định tuyến trong giao thức DRQC thực hiện tìm kiếm các nút chuyển tiếp theo các tiêu chí: - Nút đích nằm trong bảng hàng xóm cấp 1 hoặc cấp 2 của nút hiện tại không? - Nút đích có nằm trong bảng định tuyến của nút hiện tại không? - Có nút hàng xóm thỏa mãn cùng góc phần tư với nút đích và có trạng thái đỏ không? - Có nút hàng xóm thỏa mãn cùng góc phần tư với nút đích và có trạng thái là trắng không? - Có nút hàng xóm thỏa mãn có khoảng cách ngắn nhất tới đích hơn nút hiện tại không? Trên cơ sở các tiêu chí lựa chọn nút chuyển tiếp như yêu cầu, cho thấy hiệu suất định tuyến của giao thức DRQC phụ thuộc rất nhiều vào việc lựa chọn các nút hàng xóm thuộc góc phần tư với nút đích. Chính vì vậy thuật toán DRQC sẽ đạt hiệu quả tốt nhất nếu tồn tại các nút tối ưu cho lựa chọn chuyển tiếp gói tin đến nút đích thuộc góc phần tư với nút đích. Vì vậy, tôi đề xuất một giải pháp cải tiến giúp cho quá trình định tuyến gói tin bằng giao thức DRQC giúp đạt hiệu quả tốt nhất trong trường hợp “Nút tối ưu không thuộc góc phần tư với nút đích”. Giải pháp cải tiến đó là xoay trục tọa độ của nút hiện tại thực hiện tính toán tìm kiến nút kế tiếp trong đường đi. Giao thức cải tiến mới tạm gọi là “Định tuyến đi vòng dựa trên quay trục tọa độ - Detour Routing based on Coordinates Rotation axis (DR-CR)”. 3.2.1. Giải pháp quay trục tọa độ Trong giao thức DRQC mỗi một nút trong mạng sẽ là gốc của hệ tọa độ ứng với nút đó (Hình 3-5). Hình 3-5. Hệ trục tọa đọ của một nút
  38. 38 Hệ trục tọa độ của một nút như ví dụ hình 3-6 luôn luôn cố định. Giao thức DRQC dựa theo hệ trục tọa độ này để xác định xem các nút hàng xóm cấp 1 và cấp 2 thuộc góc phần tư nào so với nút đó. Do hệ trục tọa độ của một nút là cố định nên có thể dẫn đến việc xác định nút thuộc góc phần tư cùng góc với nút đích sẽ không hiệu quả. Chính vì thế giải pháp đưa ra sẽ là xoay trục tọa độ tại nút đang tính toán đường đi kế tiếp sao cho thỏa mãn nút đích luôn luôn có nhiều sự lựa chọn tối ưu nhất. Hình 3-6. Xoay trục tọa độ của một nút Trong Hình 3-6 cho thấy, trục tọa độ ban đầu của nút 1 là x1y. Khi nút 1 thực hiện việc tính toán tìm đường đi cho gói tin đến nút D. Nút 1 sẽ thực hiện việc xoay trục tọa độ ban đầu thành trục tọa độ mới là x’1y’. Khi đó các tiêu chí để tìm kiếm nút tiếp theo trong đường đi của gói tin sẽ được áp dụng theo trục tọa độ mới x’1y’. 3.2.1.1. Tiêu chí để quay trục tọa độ đó là: Các trục tọa độ mới sẽ được quay phụ thuộc vào vị trí địa lý của nút đích. Nghĩa là các trục tọa độ mới sẽ đảm bảo cách đều bằng nhau tới nút đích. Khi đó đường thẳng nối tâm của tọa độ và nút đích sẽ là đường phân giác của góc phần tư theo trục tọa độ mới tồn tại nút đích. Ví dụ hình 3-7 chúng ta thấy: Khi hạ vuông góc 2 đường thẳng từ nút đích tới hai trục tọa độ 1x’ là DH và 1y’ là DK thì khi đó: DH = DK 3.2.1.2. Phương pháp quay trục (1) Xét phương trình đường thẳng: =  ax+by+c = 0.
  39. 39 Biến đổi phương trình (1) ta có: x(y2-y1) - x1(y2-y1) = y(x2-x1) - y1(x2-x1) x(y2-y1) -y(x2-x1) - x1(y2-y1) + y1(x2-x1) = 0 (y2-y1)x + (-x2 + x1)y + (-x1(y2 - y1) + y1(x2 - x1)) = 0; => a = y2 - y1 b = -x2 + x1 c = (-x1(y2 - y1) + y1(x2 - x1)); (2) Để thuật toán mới DR-CR xác định được hai trục tọa độ ox’ và oy’ ta chỉ cần xác định được hai tọa độ của mỗi trục. Tọa độ thứ nhất là: O (0,0), đây là tọa độ gốc của hệ trục tọa độ cũ và tọa độ gốc của hệ trục tọa độ mới. Tọa độ thứ hai là: H(x’1,y’2) nằm trên trục Ox’ và K(x’2 , y’2). Hai tọa độ H và K chúng ta cần tìm là giao của các đường thẳng vuông góc với trục tọa độ và đường thẳng đi qua tọa độ nút đích KD và HD. Hình 3-7. Xác định trục tọa độ mới Giả thiết mới đặt ra cho thuật toán cải tiến là xác định được hai tọa độ ở trên hai trục tọa độ mới. Để xác định được hai tọa độ trên trục tọa độ ta dựa vào các hàm lượng giác toán học (Hình 3-8): - Tính tan (hàm lượng giác tang) của góc XSD: góc nút đích, tan (XSD) = (dy – sy)/(dx – sx ). - Tính tan góc XSY’: góc tạo bởi trục tọa độ mới oy’ và ox
  40. 40 - Tính tọa độ mới của hai điểm bất kỳ trên hai trục tọa độ khi biết tan(XSY’) và giả thiết cho trước tọa độ thuộc trục Sx. Hình 3-8. Tính góc trục tọa độ mới Khi đó chúng ta thay các giá trị mới vào phương trình (2) ta sẽ được các giá trị a, b, c lần lượt của các trục ox’ và oy’. 3.2.2. Phương pháp quay trục áp dụng trong DRQC Các tiêu chí tìm kiếm nút chuyển tiếp trong giao thức định tuyến DRQC phụ thuộc vào góc phần tư của nút đang thực hiện tính toán. Vì vậy phương pháp quay trục tôi sẽ áp dụng vào tiêu chí thực hiện tính toán nút hàng xóm cấp hai tốn kém nhất đó là: tiêu chí nút hàng xóm cấp 2 có trạng thái là nút đỏ và nút hàng xóm cấp 2 là nút trắng trong trường họp không tìm được nút hàng xóm cấp 2 nào thỏa mãn nằm trong bảng định tuyến hoặc bảng thông tin hàng xóm [8]. Áp dụng xoay trục tọa độ vào hai tiêu chí trên sẽ giúp cho thuật toán DRQC giảm chi phí duyệt qua toàn bộ các nút hàng xóm. Tuy nhiên, để quay trục hiệu quả thì tại bước này thuật toán DRQC mới tính toán các nút hàng xóm thuộc góc phần tư nào của nút đang xử lý (Hình 3-9).
  41. 41 Hình 3-9. Thuật toán cải tiến định tuyến DRQC 3.2.3. Ví dụ Xem xét ví dụ Hình 3-10, Gói tin được gửi từ một nút nguồn tới nút đích D. Khi gói tin được gửi tới nút S, nút S sẽ xử lý tìm kiếm nút hàng xóm cấp 2 để gửi gói tin đi tới đích. Ta có bảng các nút hàng xóm của nút S: Bảng 3-1: Danh sách nút hàng xóm DR-CR Góc Nút hàng xóm 1 Nút hàng xóm 2 1 {3} {7, 4} 2 {1,8} {8,1,2} 3 {9} Null 4 {11, 10} {6} Nút S sẽ thực hiện việc quay trục tọa độ sao cho trục SD là đường phân giác của góc vuông phần tư thứ nhất (Hình 3-11).
  42. 42 Hình 3-10. Ví dụ về định tuyến gói tin DR-CR Hình 3-11. Ví dụ về xoay trục định tuyến gói tin DR-CR Lúc này ta có bảng các nút hàng xóm theo trục mới của nút S: Bảng 3-2: Danh sách nút hàng xóm mới DR-CR Góc Nút hàng xóm 1 Nút hàng xóm 2 1 {1,8} {1,8,2} 2 {null} {null} 3 {9, 11} {6} 4 {3,10} {7,4}
  43. 43 Sau khi thực hiện quay trục tọa độ, nút S sẽ xác định các nút hàng xóm thuộc cùng góc với nút đích D. Các nút {1,8,2} là những nút hàng xóm cấp 2 thuộc cùng góc với nút D. khi này nút S sẽ xem xét các nút hàng xóm cấp 2 có trạng thái là đỏ hay trắng. Trong ví dụ này các nút hàng xóm cấp 2 đều là các nút trắng, vì vậy nút S sẽ chọn nút {2} vì có khoảng cách gần với nút đích D nhất. Gói tin sẽ được chuyển qua nút {1} tới nút {2}. Các bước thực hiện tìm kiếm tiếp tục khi nút {2} nhận được gói tin dữ liệu.
  44. 44 Chương 4. ĐÁNH GIÁ HIỆU NĂNG 4.1. Môi trường cài đặt chương trình mô phỏng Trong phần này, chúng ta sẽ xem xét và đánh giá hiệu năng các giao thức đã được đề cập đến trong luận văn này gồm: giao thức “Greedy Perimeter Stateless Routing (GPSR)”, “Detour Routing Quadrant Classification Protocol (DRQC)” và giao thức định tuyến cải tiến từ giao thức DRQC (DR-CR). Tác giả sử dụng môi trường hệ điều hành mã nguồn mở - Ubuntu 12.04. Các thuật toán được cài đặt trong bộ công cụ mô phỏng sự kiện mạng NS-3. Mã nguồn cài đặt được viết bằng ngôn ngữ C++ dựa trên các thuật toán đã được cài đặt trong NS-3 là AODV. Mã nguồn cài đặt và cách thêm mới một thành phần vào NS-3 chúng ta xem PHỤ LỤC 1. Để đánh giá các thông số hiệu suất của các giao thức chúng ta xem xét hai kịch bản đánh giá ở phần trình bày sau: 4.2. Đánh giá tỷ lệ chuyển gói tin thành công trong mạng 4.2.1. Kịch bản mô phỏng Trong kịch bản mô phỏng gồm 5 cấu trúc mạng (topologys) với số lượng nút mạng thay đổi là 50 nút, 100 nút, 150 nút, 200 nút, 250 nút (bảng 4-1) trong đó các nút có vị trí ngẫu nhiên trong diện tích 500m x 500m. Mỗi cấu trúc mạng chúng ta sẽ thực hiện gửi các gói tin từ các nút nguồn bất kỳ tới các nút đích bất kỳ bằng các giao thức định tuyến GPSR, DRQC, DR-CR (giao thức cải tiến từ giao thức DRQC). Sau đó thu thập thông tin về tỷ lệ phần trăm gói tin chuyển thành công của các giao thức và vẽ đồ thị. Bảng 4-1. Bảng thông số kịch bản mô phỏng mạng ngẫu nhiên STT Mạng Mạng 1 Mạng 2 Mạng 3 Mạng 4 Mạng 5 Thông số Number node 50 100 150 200 250 Time demo (s) 100 100 100 100 100 Data Rate 2 2 2 2 2 (Mbps) Packet Size 64 64 64 64 64 (byte) Transmit 7.5 7.5 7.5 7.5 7.5 Power (dBm)
  45. 45 Hình 4-1. Cấu trúc mạng gồm 50 nút Hình 4-2. Cấu trúc mạng gồm 100 nút Hình 4-3. Cấu trúc mạng gồm 150 nút Hình 4-4. Cấu trúc mạng gồm 200 nút Hình 4-5. Cấu trúc mạng gồm 250 nút 4.2.2. Kết quả thực hiện đánh giá Kết quả sau khi thực hiện các chương trình mô phỏng được phân tích và tính toán, cho ta thấy tỷ lệ chuyển gói tin thành công trong các cấu trúc mạng tương ứng với từng giao thức. Tỷ lệ chuyển gói tin thành công giữa các giao thức tương ứng với mỗi cấu trúc mạng được thể hiện trong Bảng 4-2 và đồ thị Hình 4-6. Bảng 4-2: Kết quả tỷ lệ chuyển gói tin thành công Số TT Nút mạng DRQC GPSR DR-CR 1 50 72,00% 69,00% 72,20%
  46. 46 2 100 80,00% 76,56% 81,00% 3 150 89,56% 84,60% 88,50% 4 200 90,58% 89,58% 90,58% 5 250 93,38% 92,38% 93,00% Hình 4-6. Biểu đồ tỷ lệ chuyển gói tin thành công Kết quả trên cho thấy: Giao thức định tuyến dựa trên phân chia góc phần tư DRQC và DR-CR là những giao thức định tuyến có tỷ lệ chuyển gói tin thành công tương đối cao và luôn luôn có tỷ lệ thành công lớn hơn giao thức GPSR. Đặc biệt, với những cấu trúc mạng có số lượng nút mạng nhỏ 50 nút, 100 nút, 150 nút và phân bố trong một diện tích lớn thì tỷ lệ chuyển gói tin thành công của giao thức DRQC, DR-CR và GPSR có sự chênh lệch tương đối cao cụ thể: - Cấu trúc mạng gồm 50 nút: thì tỷ lệ chuyển thành công DRQC là 75 %, DR-CR là 72,20 % còn GPSR là khoảng 68%. - Cấu trúc mạng gồm 100 nút: thì tỷ lệ chuyển thành công DRQC là trên 80%, DR-CR là 81,00 % còn GPSR là 75%. - Cấu trúc mạng gồm 150 nút: thì tỷ lệ chuyển thành công DRQC là 90 %, DR-CR là 88,50 % còn GPSR thì dưới 85 %. Tuy nhiên khi số lượng các nút mạng tương đối nhiều thì tỷ lệ chuyển tiếp gói tin thành công của cả ba giao thức DRQC, DR-CR và GPSR gần như ngang nhau và đều có tỷ lệ chuyển tiếp thành công khoảng 90 %.
  47. 47 4.3. Thông lượng trung bình của các giao thức định tuyến địa lý 4.3.1. Kịch bản mô phỏng Xem xét mạng có số lượng 150 nút với các vị trí của của các nút được xác định trước (hình 4-7). Trong cấu trúc mạng tồn tại một số vùng trống cố định cho trước. Nút nguồn gửi gói tin và nút đích gửi gói tin cố định cho trước. Thực hiện mô phỏng mạng gửi gói tin từ nút nguồn tới nút đích và thực hiện tính toán thông lượng trung bình theo thời gian của các giao thức (bảng 4-3). Bảng 4-3. Thông số mô phỏng mạng cố định Số TT Tham số Giá trị 1 Số nút 150 (nút) 2 Thời gian mô phỏng 30 (s) 3 Diện tích phân bổ nút mạng 500 x 500(m) 4 Khoảng cách nút 30 m 5 Nút nguồn Nút {18} 6 Nút đích Nút {95} 7 Transmit Power 7.5 dBm 8 Data Rate 9 Packet Size 1024 byte 10 Data rate 2 Mbps Hình 4-7.Cấu trúc mạng có vị trí cố định
  48. 48 4.3.2. Kết quả thực nghiệm và phân tích Kết quả thực hiện chương trình mô phỏng với các giao thức lần lượt là: DRQC, GPSR, DR-CR. Chương trình mô phỏng sinh ra các tập tin .pcap, sau khi sử dụng chương trình phân tích gói tin Wireshark để phân tích. Trích lọc các thông tin cần thiết và thực hiện tính thông lượng trung bình theo thời gian của các giao thức bằng chương trình Perl (Phụ lục 2 kèm theo), kết quả được minh họa ở đồ thị (Hình 4-8). Hình 4-8. Thông lượng theo thời gian của các giao thức Từ kết quả phân tích và hiện thị trong đồ thị Hình 4-8, thấy rằng: Đối với một cấu trúc mạng có các vị trí cố định cho trước, trong một số điều kiện như kịch bản mô phỏng (hình 4-7), kết quả thông lượng trung bình theo thời gian chỉ ra: Giao thức DRQC, DR-CR là hai giao thức định tuyến dựa trên phân chia góc phần tư luôn lớn hơn giao thức GPSR là giao thức dựa trên thuật toán tham lam. Với một cấu trúc mạng có vùng trống xác định và các nút nguồn và nút đích nằm ở những vị trí không tối ưu chúng ta thấy rằng giao thức cải tiến dựa theo phân chia góc phần tư (DR-CR) có thông lượng trung bình lớn hơn giao thức gốc là DRQC.
  49. 49 KẾT LUẬN Với những tìm hiểu, nghiên cứu về các nội dung trong luận văn đã giúp cho tôi có được những kiến thức bổ ích về định tuyến dựa theo thông tin vị trí địa lý trong mạng không dây. Luận văn cũng giúp tôi rất nhiều về kỹ năng thực hành, đánh giá hiệu năng hệ thống mạng. Dù trong quá trình nghiên cứu tôi đã rất cố gắng nhưng chắc chắn không tránh khỏi những sai sót, hạn chế cần bổ sung trong tương lai khi phát triển tiếp đề tài. Vì vậy, tôi xin đưa ra một số kết luận và định hướng như sau: 1. Các kết quả đạt được Luận văn đã trình bày về tổng quan giao thức định tuyến sử dụng thông tin địa lý, cũng như trình bày về giao thức định tuyến địa lý dựa trên phân chia góc phần tư “Detour Routing based on Quadrant Classification Protocol – (DRQC)”. Từ những phân tích và so sánh về giao thức định tuyến DRQC luận văn đã chỉ ra hạn chế của chính giao thức định tuyến này trong trường hợp các nút mạng nằm tại các vị trí không tối ưu. Luận văn cũng đã đề xuất một phương pháp cải tiến thuật toán DRQC là phương pháp quay trục tọa độ của mỗi nút trong mạng khi thực hiện tính toán lựa chọn nút hàng xóm thuộc góc phần tư cùng với nút đích. Luận văn cũng đã cài đặt và thực hiện đánh giá các giao thức định tuyến theo chiến lược tham lam (GPSR), giao thức định tuyến dựa trên phân chia góc phần tư (DRQC) và giao thức cải tiến từ giao thức DRQC bằng công cụ mô phỏng sự kiện mạng NS3. Kết quả thực nghiệm và so sánh các giao thức định tuyến thấy rằng, tỷ lệ chuyển thành công gói tin trong mạng không dây bằng giao thức định tuyến dựa trên phân chia góc phần tư DRQC luôn luôn cao hơn với giao thức sử dụng chiến lược tham lam GPSR cũng như kết quả chỉ ra rằng thông lượng trung bình chuyển gói tin của giao thức định tuyến cải tiến từ giao thức DRQC là tối ưu hơn trong một số trường hợp. Luận văn cũng đã trình bày về công cụ mô phỏng mạng NS3 và cách thức thêm mới thành phần vào trong mã nguồn của công cụ mô phỏng sự kiện mạng NS3 nhằm giúp người học, người nghiên cứu có thể cài đặt mới những nghiên cứu của mình để đánh giá và thử nghiệm kết quả. 2. Những hạn chế của đề tài Luận văn không nghiên cứu và cài đặt so sánh được nhiều giao thức định tuyến sử dụng thông tin vị trí địa lý, mà chỉ giới trong hai giao thức “Greedy
  50. 50 Perimeter Stateless Routing” và “Detour Routing Based on Quadrant Classification”. Luận văn mới chỉ dừng lại nghiên cứu công cụ mô phỏng mạng NS-3 giúp cho việc mở rộng một số giao thức định tuyến sử dụng thông tin vị trí địa lý mà chưa nghiên cứu sâu về công cụ mô phỏng sự kiện mạng NS-3. Ngoài ra luận văn cũng chỉ dừng lại việc đánh giá hiệu năng tỷ lệ chuyển gói tin thành công và thông lượng trung bình của các giao thức mà chưa đánh giá được nhiều hơn các thông số khác. 3. Hướng phát triển Đánh giá và cải tiến chất lượng quá trình định tuyến gói tin rất cần thiết trong các hệ thống mạng máy tính. Vì vậy, để đề tài nghiên cứu hoàn thiện hơn và có giá trị hơn cần tập trung các nội dung sau: - Tìm hiểu sâu hơn về các giao thức định tuyến địa lý khác giúp cho việc đánh giá, so sánh khách quan và toàn diện hơn với giao thức định tuyến địa lý đi vòng dựa theo phân loại nút theo góc phần tư. - Nghiên cứu và đánh giá sâu hơn về giải pháp cải tiến giao thức đi vòng dựa trên phân loại nút theo góc phần tư. - Tìm hiểu công cụ mô phỏng sự kiện mạng NS3 giúp cho việc sử dụng, cài đặt các thành phần khác tốt hơn. - So sánh và đánh giá giao thức định tuyến theo thông tin vị trí địa lý và một số giao thức định tuyến khác trong mạng không dây. - Nghiên cứu về các giao thức định tuyến theo vị trí địa lý giúp tối ưu năng lượng của các nút.
  51. 51 TÀI LIỆU THAM KHẢO [1] Nandan Banerji, Uttam Kumar Kundu, Pulak Majumder, Debabrata Sarddar (2013), “Quadrant Based WSN Routing Technique by Shifting of Origin”, International Journal of Advanced Computer Science and Applications, 4,(3), pp.38 – 41. [2] Ana Maria Popescu, Ion Gabriel Tudorache, Bo Peng, A.H. Kemp (2012), “Surveying Position Based Routing Protocols for Wireless Sensor and Ad-hoc Networks”, International Journal of Communication Networks and Information Security (IJCNIS), 4, (1), pp. 41-67. [3] Brad Krap, H.T.Kung (2000), “GPSR: Greedy Perimeter Stateless Routing for Wireless Networks”, ACM International Conference on Mobile Computing and Networking, pp. 243-245. [4] Basu Dev Shivahare, Charu Wahi, Shalini Shivhare (2012), “Comparison Of Proactive And Reactive Routing Protocols In Mobile Ad-hoc Network Using Routing Protocol Property”, International Journal of Emerging Technology and Advanced Engineering 2, (3), pp. 356-359. [5] I. Stojmenovic, X. Lin (2001), “Loop-free hybrid single-path/flooding routing algorithms with guaranteed delivery for wireless networks,” IEEE Trans. on Parallel and Distributed Systems, 12 (10), pp. 1023–1032. [6] A. Tanenbaum, D. Wetherall (2011), “Computer Networks”, Boston, Massachusetts, United States of America. [7] University of Freiburg, Germany (2009), Theory and Practice of Geographic Routing. [8] Lih-Chyau Wuu, Wen-Ben Li, Wen-Chung Ko (2010), “Detour Routing Protocol for Geographic Sensor Network”, International Conference on Broadband, Wireless Computing, Communication and Applications (122), pp. 505 – 510. [9] Shyjith M.B, V.K.Reshma (2012), “GOAFR: An Optimal Algorithm for Geographic Routing In Wireless Sensor Networks”, International Journal of Computer Networks and Wireless Communications, 2, (2), pp. 131-135. [10] NS3-Tutorial, 21/12/2013, (ngày truy cập 26/12/2013). [11] NS3-Document, (truy cập ngày 12/07/2013).
  52. 52 PHỤC LỤC 1 I. CÔNG CỤ MÔ PHỎNG SỰ KIỆN MẠNG NS-3 1.1. Tổng quan về NS-3 Network simulator (NS-3) [10][11] là một chương trình mô phỏng các sự kiện của hệ thống mạng máy tính. Mục đích chính của NS-3 là dùng mô phỏng các sự kiện mạng trong nghiên cứu và học tập của cộng đồng các nhà nghiên cứu và sinh viên làm việc với hệ thống mạng máy tính. NS-3 là một dự án phần mềm mã nguồn mở (open source), được bắt đầu xây dựng từ năm 2006, giấy phép sử dụng dưới dạng GNU GPLv2 license. Dự án NS-3 cam kết sẽ xây dựng một lõi chương trình mô phỏng chung nhất cũng như một hệ thống tài liệu chuẩn (Doxygen [11]), dễ dàng dùng cho xây dựng và kiểm soát lỗi dự án. NS-3 phục vụ cho toàn bộ nhu cầu mô phỏng, từ những cấu hình để bắt và phân tích gói tin, hơn nữa, các nền tảng ứng dụng, modules được cài đặt trong NS-3 giúp người sử dụng phát triển, cải tiến, thực hiện các mô phỏng. NS-3 còn có thể mô phỏng với các mạng thực tế (emulator), tương tác cùng với mạng thực và NS-3 còn tồn tại một số giao thức phát triển rất hữu dụng trong NS-3. Mô phỏng NS-3 hỗ trợ nghiên cứu về cả hai giao thức cơ bản của mạng là IP và Non-IP. Tuy nhiên, nội dung phần lớn của NS-3 tập trung vào mô phỏng wireless/IP. Cùng với các mô hình liên quan cho Wi-Fi, WiMAX, hoặc LTE thuộc các lớp 1 và 2. NS-3 cũng dùng cho các giao thức định tuyến động như OLSR và AODV cho ứng dụng địa chỉ IP cơ bản. Mỗi một quý 3 tháng NSNAM sẽ phát hành một phiên bản NS-3 ổn định tới cộng đồng người sử dụng [10]. Một số chú ý cần quan tâm khi làm việc với bộ mô phỏng mạng NS-3. NS-3 không phải được thừa kế và mở rộng từ NS2. Đây là một bộ mô phỏng sự kiện mạng mới. Cả hai bộ mô phỏng NS2, NS-3 đều được viết bằng C++, nhưng NS-3 không hỗ trợ các hàm API của NS2. Một số mô đun từ NS2 đã và đang được phát triển và cài đặt trong NS-3. Dự án này sẽ tiếp tục bảo trì công cụ mô phỏng NS2, và phát phát triển mới công cụ mô phỏng NS-3. NS-3 là một phần mềm mã nguồn mở, dự án này được bảo trì và để mở mã nguồn cài đặt, môi trường phát triển nhằm giúp cộng đồng nghiên cứu tìm hiểu và chia sẽ các thuộc tính cũng như các thành phần mở rộng của chính người dùng trên NS-3.
  53. 53 NS-3 sử dụng trong cộng đồng người dùng NS2 Đối với cộng đồng sử dụng bộ mô phỏng NS2, một trong những thay đổi dễ nhìn thấy nhất đó là lựa chọn kịch bản viết mô phỏng. Trong NS2, là những kịch bản Otcl và kết quả của simulator có thể xem (hiện thị trực quan) bằng công cụ mô phỏng trực quan NAM. NS2 không thể mô phỏng hoàn toàn bằng ngôn ngữ C++ mà không dùng tới kịch bản OTcl. Hơn thế nữa có rất nhiều thành phần trong chương trình NS2 đã được viết bằng C++, nhưng một số viết bằng OTcl. Trong chương trình NS-3 mô phỏng được viết hoàn toàn bởi C++ và lựa chọn biên dịch bằng Python. Các công cụ xem trực quan kết quả trong NS-3 cũng đã sãn sàng và đang được tiếp tục phát triển. NS-3 sinh ra tập tin pcap có thể dùng để phân tích kết quả rất là tốt nhờ công cụ phân tích gói tin Wireshare. Một trong những câu hỏi mà chúng ta thường nghe và rất quan tâm là “ Nên dùng NS2 hay chuyển sang dùng NS-3?”. Câu trả lời là tùy thuộc vào những mô phỏng của chúng ta. NS-3 không có tất cả các modules như NS2 hiện tại đang có, nhưng NS-3 lại có khả năng mới như: xử lý nhiều thao tác trên cùng một nút, sử dụng địa chỉ IP liên kết nhiều hơn với các giao thức cũng như thiết kế chi tiết hơn với chuẩn mạng 802.11 [10]. NS-3 cũng cho phép ngươi dùng phát triển và cài đặt thêm các phần mở rộng dễ dàng hơn [10]. 1.2. Các thành phần của NS-3 Tìm hiểu một cách nhìn tổng quát về các thành phần của công cụ mô phỏng mạng NS-3 sẽ giúp cho người sử dụng có thể đọc mã nguồn của dự án NS-3 hoặc có thể thêm, chỉnh sửa các module của dự án. Hình PL. 1 Kiến trúc phần mền NS-3
  54. 54 i. Node Là những máy tính, thiết bị đầu cuối được kết nối vào hệ thống mạng. Trong NS-3, một nút (node) là một khái niệm trừu tượng và được xây dựng trong một lớp node viết bằng ngôn ngư C++. Lớp node hỗ trợ những phương thức dùng để quản lý và đại diện cho một máy tính, một thiết bị trong mô phỏng. Chúng ta nên xem một nút như là một máy tính và trong quá trình mô phỏng được thêm vào các hàm, chức năng khác. Một trong những chức năng quan trọng nhất là Application (thêm ứng dụng mạng vào nút), protocol (thêm giao thức), kết nối các thiết bị ngoại vi khác liên quan để cho phép thực hiện các mô phỏng mạng. Một nút được dùng như một model (mô hình) trong NS-3 [10]. ii. Application Một phần mềm máy tính được chia ra làm hai thành phần cơ bản là phần mềm hệ thống (các hệ điều hành) để điều khiển và liên kết các thiết bị trong một máy tính, và các phần mềm ứng dụng khác. Trong NS-3 một máy tính xem như không có hệ điều hành. Tuy nhiên các máy tính vẫn có các ứng dụng khác giống như là một máy tính thực. Trong NS-3, một chương trình người dùng là một khái niệm trừu tượng được mô phỏng như là một ứng dụng và được phát triển bằng C++, trong lớp Application, lớp Application có các phương thức. Trong các chương trình mô phỏng các nút thường sử dụng các lớp UdpEchoClientApplication và UdpEchoServerApplication được thừa kế từ lớp Application. Các lớp Client/Server được dùng cho việc sinh ra các gói tin trong mạng mô phỏng. iii. Channel Trong mạng thực, kênh kết nối (channel) có thể kết nối một máy tính này với một mạng máy tính khác. Chúng ta có thể kết nối bằng cáp, sóng radio . Trong NS-3 để kết nối một nút tới một đối tượng chúng ta gọi là kênh giao tiếp (Communication channel) hay được gọi là channel và được xây dựng trong một lớp Channel viết bằng C++. Các lớp CsmaChannel, PointToPointChannel, WifiChannel trong các chương trình mô phỏng đại diện cho các đường truyền vật lý trong mạng thực. iv. Net Device Trong trường hợp muốn kết nối các máy tính tới một mạng máy tính, ta phải chỉ ra loại đường truyền kết nối và phải có thiết bị kết nối đường truyền
  55. 55 được gắn vào máy tính, các thiết bị phần cứng đó gọi là thẻ giao tiếp mạng (Network Interface Cards - NICs). Ngày nay các thiết bị NICs được gắn sẵn vào máy tính. NICs sẽ không làm việc nếu chúng không được cài đặt các phần mềm điều khiển (Network drivers). Những thiết bị ngoại vi và NICs sử dụng chương trình điều khiển được gọi chung là thiết bị mạng (Net Device). Trong NS-3, thiết bị mạng được trừu tượng hóa bao gồm cả các phần mềm và phần cứng. Thiết bị mạng được cài đặt vào trong các nút để cho phép các nút có thể giao tiếp với nhau thông qua các kênh giao tiếp (Channels). Một nút cũng có thể kết nối với nhiều nút thông qua nhiều kênh giao tiếp và nhiều card mạng được cài đặt vào nút. Thiết bị mạng được cài đặt trong NS-3 với tên lớp là NetDevice bằng ngôn ngữ C++. Lớp NetDevice chứa các hàm, thuộc tính giúp cho việc kết nối và quản lý thiết bị mạng với khênh kết nối. Chúng ta có một số Netdevice dùng mô phỏng được cài đặt sẵn trong NS-3 như CsmaNetDevice , PointToPointNetDevice , và WifiNetDevice. 3. Cài đặt NS-3 i. Các phần mềm cần thiết a) Mercurial Là một công cụ dùng để quản lý tập tin nguồn (source code) của dự án NS- 3 giúp cho cộng đồng sử dụng dễ dàng quản lý và truy cập các tập tin nguồn của NS-3. Người dùng không nhất thiết tìm hiểu nhiều về Mercurial để cài đặt NS-3. Nếu bạn quan tâm tới Mercurial thì có thể tham khảo tài liệu tại địa chỉ: [10]. b) Waf Waf công cụ dùng để biên dịch tập tin nguồn (source code) của dự án NS-3 thành một chương trình chạy trong các nền tảng hệ điều hành để thực hiện mô phỏng. Waf được hiểu như mà một công cụ biên dịch, nó dùng để biên dịch cả những chương trình có mã code là Python và C++. Trong dự án NS-3 có các chương trình viết bằng Python, tuy nhiên để biên dịch chúng ta không cần quan tâm tới Python, những trình biên dịch Python sẽ được cài đặt sẵn vào máy tính trước khi chúng ta biên dịch bằng công cụ Waf. Để tìm hiểu thêm về Waf có thể tham khảo tại địa chỉ:
  56. 56 ii. Cài đặt và kiểm tra và thực hiện mô phỏng a) Cài đặt NS-3 NS-3 hỗ trợ cài đặt trên các nền tảng hệ điều hành: Linux, Windows, MacOS. Trong phần hướng dẫn cài đặt này tôi chỉ trình bày cách cài đặt và cấu hình, cũng như sử dụng NS-3 trên hệ điều hành Linux phiên bản Ubuntu 12.04, đây cũng là hệ điều hành chủ yếu chạy các thử nghiệm cũng như cài đặt mã nguồn cho các giao thức định tuyến địa lý trong đề tài tốt nghiệp của tôi. NS-3 được phát triển chủ yếu cho nền tảng GNU/Linux. Để thực hiện cài đặt, biên dịch mã nguồn và mô phỏng các sự kiện mạng trên NS-3 máy tính yêu cầu tối thiểu phải là cài đặt đặt các gói phần mềm hỗ trợ như: công cụ biên dịch mã nguồn C++, gcc, gcc-3,4, g ++ -3,4 hoặc cao hơn, và công cụ biên dịch mã nguồn python 2.4 hoặc phiên bản mới hơn. Hướng dẫn cài đặt trên hệ điều hành Linux (Ubuntu 12.04) Phần mềm cần thiết yêu cầu cài đặt trước khi biên dịch NS-3. Thực hiện các lệnh như hướng dẫn phía dưới trong ứng dụng Terminal hoặc trong giao diện hỗ trợ cài đặt phần mềm trong Ubuntu. Cài đặt Gcc, G++: sudo apt-get install gcc g++ python Cài đặt Python: sudo apt-get install gcc g++ python python-dev Cài đặt Mercurial: sudo apt-get install mercurial Update Gcc,G++: sudo apt-get install g++-3.4 gcc-3.4 Download NS-3 sử dụng Mercurial: Di chuyển vào thư mục gốc dùng lưu trữ mã nguồn của NS-3 sau khi tải về và tạo thư mục con lưu trữ nếu cầu thiết. Sử dụng các câu lệnh sau trong chương trình terminal của linux mkdir K18_NS-3 (tạo thư mục chứa source code) cd K18_NS-3 (Di chuyển vào thư mục mới)
  57. 57 hg clone (Download source code NS-3) Kết quả sau khi thực hiện câu lệnh download code NS-3 Kết quả hiện thị trên màn hình chỉ ra các thông tin liên quan và số tập tin đã download về thành công. destination directory: ns-3-allinone requesting all changes adding changesets adding manifests adding file changes added 26 changesets with 40 changes to 7 files 7 files updated, 0 files merged, 0 files removed, 0 files unresolved Di chuyển vào thư mục: ns-3-allinone Các tập tin nằm trong thư mục chúng ta có thể thấy build.py* constants.py dist.py* download.py* README util.py Màn hình dòng lệnh Terminal đang ở thưc mục ns-3-allinone chúng ta thực hiện lệnh: ./download.py Sau khi tải thành công chúng ta có các tập tin và thư mục mới trong ns-3- allinone: build.py* constants.pyc download.py* nsc/ README util.pyc constants.py dist.py* ns-3-dev/ pybindgen/ util.py Biên dịch NS-3 sử dụng công cụ Waf Di chuyển vào thư mục ns-3-dev biên dịch và cấu hình NS-3 bằng cách thực hiện các lệnh ./waf configure ./waf
  58. 58 Kết quả hiện thị Checking for program g++ : ok /usr/bin/g++ Checking for program cpp : ok /usr/bin/cpp Checking for program ar : ok /usr/bin/ar Checking for program ranlib : ok /usr/bin/ranlib Checking for g++ : ok Checking for program pkg-config : ok /usr/bin/pkg-config Checking for -Wno-error=deprecated-declarations support : yes Checking for -Wl, soname=foo support : yes Checking for header stdlib.h : ok Checking for header signal.h : ok Checking for header pthread.h : ok Checking for high precision time implementation : 128-bit integer Checking for header stdint.h : ok Checking for header inttypes.h : ok Checking for header sys/inttypes.h : not found Checking for library rt : ok Checking for header netpacket/packet.h : ok
  59. 59 Checking for pkg-config flags for GSL : ok Checking for header linux/if_tun.h : ok Checking for pkg-config flags for GTK_CONFIG_STORE : ok Checking for pkg-config flags for LIBXML2 : ok Checking for library sqlite3 : ok Checking for NSC location : ok /nsc (guessed) Checking for library dl : ok Checking for NSC supported architecture x86_64 : ok Checking for program python : ok /usr/bin/python Checking for Python version >= 2.3 : ok 2.5.2 Checking for library python2.5 : ok Checking for program python2.5-config : ok /usr/bin/python2.5-config Checking for header Python.h : ok Checking for -fvisibility=hidden support : yes Checking for pybindgen location : ok /pybindgen (guessed) Checking for Python module pybindgen : ok Checking for pybindgen version : ok 0.10.0.640 Checking for Python module pygccxml : ok
  60. 60 Checking for pygccxml version : ok 0.9.5 Checking for program gccxml : ok /usr/local/bin/gccxml Checking for gccxml version : ok 0.9.0 Checking for program sudo : ok /usr/bin/sudo Checking for program hg : ok /usr/bin/hg Checking for program valgrind : ok /usr/bin/valgrind Summary of optional NS-3 features: Threading Primitives : enabled Real Time Simulator : enabled Emulated Net Device : enabled GNU Scientific Library (GSL) : enabled Tap Bridge : enabled GtkConfigStore : enabled XmlIo : enabled SQlite stats data output : enabled Network Simulation Cradle : enabled Python Bindings : enabled Python API Scanning Support : enabled Use sudo to set suid bit : not enabled (option enable-sudo not selected) Build tests : enabled Build examples : enabled Static build : not enabled (option enable-static not selected) 'configure' finished successfully (2.870s Cài đặt trên nền tảng hệ điều hành Windows Để thực hiện cài đặt trên hệ điều hành Windows chúng ta có thể cài đặt các chương trình mô phỏng nền tảng Linux như: Cygwin hoặc MinGW. Tải về và giải nén tập tin ns-3-allinone sử dụng chương trình Cygwin cấu hình và build ns-3-allinone tương tự như cài đặt với Linux giới thiệu ở phần trên.
  61. 61 iii. Kiểm tra cài đặt và chạy thử chương trình Sau khi cài đặt hoàn thành, chúng ta có thể kiểm tra (unit tests) cho NS-3 như sau: Mở chương trình terminal vào thư mục ns-3-dev, gõ lệnh: “./test.py -c core” để chạy test.py script Trên màn hình terminal sẽ hiện thị những thông tin về cài đặt chương trình như số lượng module cài đặt thành công, số lượng module cài đặt không thành công. Hình PL.2. Cài đặt thành công Chạy một chương trình (Run a script) Để biên dịch một chương trình mô phỏng chúng ta sử dụng lệnh ./waf. Chương trình cho phép biên dịch hệ thống đảm bảo nó có thể chia sẽ đường dẫn thư viện phải được thiết lập chính xác và thư viện sẵn sàng để thực thi. Để chạy một chương trình, đơn giản chúng ta gõ “./waf run scriptName” trong terminal application,ví dụ: ./waf run hello-simulator” Trong đó ./waf run là lệnh thực thi một mô phỏng, hello-simulator là tên tập tin chứa hàm chính (Main) của một mô phỏng.
  62. 62 Cấu trúc viết một kịch bản mô phỏng Trong NS-3, những chương trình mô phỏng có thể được viết dưới các ngôn ngữ C++ hoặc python. Trong ví dụ hướng dẫn sau tôi trình bày về một ví dụ đơn giản được viết bằng C++. Đầu tiên của một Script luôn luôn thêm vào (include) những thông tin về bản quyền GNU, thông tin về dự án và bản quyền của script. Chúng ta cần thêm những thông tin này vào nếu như muốn phát hành mã cài đặt ra cộng đồng sử dụng. / * * This program is free software; you can redistribute it and/or modify * it under the terms of the GNU General Public License version 2 as * published by the Free Software Foundation; * * This program is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * You should have received a copy of the GNU General Public License * along with this program; if not, write to the Free Software * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA * / Tiếp theo chúng ta sẽ include những module cần thiết để tực hiện mô phỏng. #include "ns3/core-module.h" #include "ns3/network-module.h" #include "ns3/internet-module.h"
  63. 63 #include "ns3/point-to-point-module.h" #include "ns3/applications-module.h" Script cần được thực hiện trong namespace NS-3 using namespace ns3; Main function (Chương trình chính) Main function { //Khai báo các node mạng /Khai báo kênh truyền dữ liệu (Data rate/ time delay)/Các thành phần //khác phụ thuộc vào sự kiện mạng cần mô phỏng //Thực thi Simulator Simulator::Run (); //Runs the simulation and the function only returns after the sim is finished Simulator::Destroy (); //Clean up the objects created for the sim } 4. Thêm mới module, cài đặt giao thức định tuyến GPSR và DRQC i. Thêm mới module vào dự án NS-3 Khi chúng ta có một mô phỏng, một nghiên cứu mới, hay cần thêm một tính năng mới cho NS-3, chúng ta phải biên dịch và nhúng những module mới vào NS-3. Trong phần này sẽ giới thiệu và hướng dẫn chúng ta cách để thêm mới một module cho NS-3. Thư mục chứa các module của NS-3 /ns-3-allinone/ns-3-dev/src Mỗi một thư mục được tìm thấy sẽ cùng tên với các module có trong NS- 3. ví dụ module aodv có thư mục “aodv”. Tạo module với mẫu quy định sẵn của NS-3 Trong công cụ mô phỏng NS-3, một đoạn mã python được hỗ trợ để tạo ra các module mới nằm trong thư mục /ns3-dev/src, tên tập tin là create- module.py.
  64. 64 Ví dụ chúng ta muốn tạo ra một module tên “new-module”, chúng ta gõ lệnh sau lên giao diện terminal khi đã di chuyển vào thư mục src. ./create-module.py new-module. Sau khi tạo xong module tên là “new-module” chúng ta di chuyển vào thư mục “new-module” nằm trong thư mục src sẽ thấy các thư mục và tập tin đúng với mẫu có sẵn của NS-3 như sau: examples helper model test wscript trong đó các thư mục chứa examples: chứa các mẫu tập tin để mô phỏng module helper: chứa các tập tin dùng để liên kết với các module khác trong NS-3 mode: chứa các tập tin, thư mục liên quan tới mã nguồn cài đặt của module test: chứa các tập tin thực hiện kiểm tra module wscript: là tập tin dùng để biên dịch và làm việc với công cụ waf ii. Cài đặt giao thức định tuyến DRQC, GPSR Các giao thức định tuyến được cài đặt thêm vào công cụ mô phỏng NS-3 đều được tạo ra theo mẫu có sẵn của NS-3 vì vậy về cấu trúc thư mục và các file cấu hình tôi sẽ không nhắc đến trong phần trình bày này. Thay vào đó phần trình bày này tôi sẽ chủ yếu nêu ra một số phần code chính của chương trình được miêu tả trong các giải thuật của giao thức đinh tuyến. Ngoài ra các giao thức DRQC và GPSR đều được thừa kế từ các giao thức định tuyến không dây đã được cài đặt sẵn trong NS-3 vì vậy những hàm xử lý gửi, nhận thông tin bằng socket, chúng ta có thể tham khảo thêm trong các source code của NS-3. iii. Cài đặt giao thức DRQC Hàm xử lý tìm kiếm nút tiếp theo khi nút nhận được gói tin Hàm xử lý thực hiện tìm kiếm nút tiếp theo khi nhận được gói tin gửi tới. Kết quả trả về là địa chỉ IP của nút tiếp theo. Phần code phía dưới được viết bằng ngôn ngữ C++ nằm trong tập tin drqc.cc. Ipv4Address RoutingProtocol::SearchNextHop(Vector sender,
  65. 65 Vector destination, Vector vprober, Vector &vfor, int needUpdate) { Ipv4Address nextHop = Ipv4Address::GetZero(); Vector vf; Vector v; std::list candidates; std::list ltwoNeig; Ptr MM = m_ipv4- >GetObject (); v.x = MM->GetPosition ().x; v.y = MM->GetPosition ().y; Vector vNextHop; if((vprober.x != -1 && vprober.y != -1) && (sender.x != -1 && sender.y != -1) && needUpdate ==1) { updateRoutingTable(sender,vprober,ltwoNeig); //nqdung } if(DestinationExistN1N2(destination,m_neighbors. GetNeighborTable(), vNextHop)) { vfor = destination; nextHop = m_routingTables.GetIPv4(vNextHop); return nextHop; } if(DestinationInRoutingTable(destination, m_routingTables.GetTable1(), vf)) { vNextHop = FindFirstVector(m_neighbors.GetNeighborTable(),v f); vfor = vf;
  66. 66 nextHop = m_routingTables.GetIPv4(vNextHop); return nextHop; } candidates= GetCandidatesRed(m_neighbors.GetNeighborTable(), v, vprober, destination); if(candidates.size() > 0) { Vector vMin = MinPosition(candidates, destination); //count min of node ltwoNeig= GetCandidatesNoRed(m_neighbors.GetNeighborTable( ) , vMin); if((destination.x != -1 && destination.y != -1) && (sender.x != -1 && sender.y != -1)&& needUpdate ==1) { updateRoutingTable(destination,vMin,ltwoNeig); //nqdung } vNextHop = FindFirstVector(m_neighbors.GetNeighborTable(),v Min); vfor = vMin; nextHop = m_routingTables.GetIPv4(vNextHop); return nextHop; } candidates = GetCandidatesWhite(m_neighbors.GetNeighborTable( ),v, vprober, destination); if (candidates.size() > 0) { Vector vMin = MinPosition(candidates, destination); //count min of node
  67. 67 ltwoNeig = GetCandidatesNoRed(m_neighbors.GetNeighborTable( ),vMin); if((destination.x != -1 && destination.y != -1) && (sender.x != -1 && sender.y != -1)&& needUpdate ==1) { updateRoutingTable(destination,vMin,ltwoNeig); //nqdung } vNextHop = FindFirstVector(m_neighbors.GetNeighborTable(), vMin); nextHop = m_routingTables.GetIPv4(vNextHop); vfor = vMin; return nextHop; } std::list ltempN2 = GetCandidatesNoRed(m_neighbors.GetNeighborTable( ),v); if(ltempN2.size()>0) { Vector vMin = MinPosition(ltempN2, destination); //count min of node ltwoNeig = GetCandidatesNoRed(m_neighbors.GetNeighborTable( ),vMin); if((destination.x != -1 && destination.y != -1) && (sender.x != -1 && sender.y != -1)&& needUpdate ==1) } Hàm xử lý xoay trục trong thuật toán DRQC cải tiến
  68. 68 //////////////////////////////////////////////// /////// //Function Name: DefineCoordinate //Description: Use for calculations some factor of straight-line equation //Example: ax + by +c =0; return a, b, c //Input: tan of angle Destination with ox //Output: a,b,c of ox' and oy' straight-line equation //dungnq06@gmail.com //////////////////////////////////////////////// //////// void drqcneigtable::DefineCoordinate(Vector vSr, float tanDes, Vector &vOY, Vector &vOX) { /*ta co: voi hai diem bat ky, phuong trinh duong thang la: * x(y2-y1) - x1(y2-y1) = y(x2-x1) - y1(x2-x1) * x(y2-y1) -y(x2-x1) - x1(y2-y1) + y1(x2- x1) = 0 (y2-y1)x + (-x2 + x1)y + (-x1(y2 - y1) + y1(x2 - x1)) = 0; * => a = y2 - y1 * b = -x2 + x1 * c = (-x1(y2 - y1) + y1(x2 - x1)); * thay cac tham so vao ta co: * */ //goi diem B bat ky: float x2 = vSr.x + 10; //diem B luon lon hon diem A (ban dau) //if tanDes > 0 => Destination thuoc goc 1 hoac 3 (quay theo kim dong ho) //if tanDes Destination thuoc goc 2,4 (quay theo kim dong ho)
  69. 69 float y2,y3 = 0; float tanAnpha = 0; if(tanDes >= 1) { tanAnpha = (tanDes - 1)/(tanDes + 1); // tan 45 = 1; y2 = ((-1)* ((x2-vSr.x) / tanAnpha)) + vSr.y; // costan = y/x; y3 = (x2-vSr.x) * tanAnpha + vSr.y; // tan = x/y => y = x/tan {tanDes > 0 => tanAnpha <0} } else if(tanDes < 1) { tanAnpha = (1 - tanDes)/(tanDes + 1); // tan 45 = 1; y2 = tanAnpha / x2; //tanAnpha = costang(pi/2 -x) y3 = (-1) * tanAnpha * x2; //tanAnpha = costang(pi/2 -x) } //y2 = tanAnpha * 10; //(x2-x1) float ay,by,cy; float ax,bx,cx; //oy ay = y2 - vSr.y; by = (-1 * x2) + vSr.x; cy = ((-1)*vSr.x * (y2 - vSr.y) + vSr.y * (x2 - vSr.x)); //ox ax = y3 - vSr.y; bx = (-1 * x2) + vSr.x; cx = ((-1)*vSr.x * (y3 - vSr.y) + vSr.y * (x2 - vSr.x));
  70. 70 vOY.x = ay; vOY.y = by; vOY.z = cy; vOX.x = ax; vOX.y = bx; vOX.z = cx; } iv. Cài đặt giao thức GPSR Giao thức GPSR là một giao thức phổ biến và đã được cộng đồng nghiên cứu cài đặt, thử nghiệm trên một số công cụ mô phỏng sự kiện mạng. Trong NS- 3, GPSR cũng đã được cộng đồng nghiên cứu cài đặt và thử nghiệm tại địa chỉ Trong nội dung luận văn này, tôi đã tham khảo và download các tập tin liên quan tới giao thức GPSR từ trên trang web đã chỉ ra và tích hợp vào bộ công cụ mô phỏng mạng NS-3 dựa vào phương thức thêm mới một module vào NS-3.
  71. 71 PHỤ LỤC 2 Chương trình thực hiện tính thông lượng trung bình theo thời gian của các giao thức. Chương trình được viết bằng mã lệnh Perl. #Caclator throughput of Protocol #Input: file.txt contain two column, the first column is Time for send and second column is leng of packet #Output: file.txt contain two column $infile=$ARGV[0]; $start_time=-1; $end_time=0; $throughput = 0; $sum=0; open (DATA," ) { @x = split(' '); if ($start_time == -1) { $start_time = $x[0]; } else { $sum += $x[1]; if ($x[0] != $start_time) { $throughput = $sum / ($x[0] - $start_time); #Don vi Kbps #Chuyen so luong bytes ve tong so bits, sau do chuyen bits ve Kbit $throughput = $throughput *8 / 1024; print STDOUT "$x[0] $throughput \n"; } } }
  72. 72 close DATA; exit(0);