Tài liệu Dịch vụ vị trí phân cấp cho định tuyến trong mạng manet

Đại Học Quốc Gia Tp. Hồ Chí Minh TRƯỜNG ĐẠI HỌC BÁCH KHOA -------------------- NGUYỄN QUANG VINH DỊCH VỤ VỊ TRÍ PHÂN CẤP CHO ĐỊNH TUYẾN TRONG MẠNG MANET Chuyên ngành : KỸ THUẬT ĐIỆN TỬ LUẬN VĂN THẠC SĨ TP. HỒ CHÍ MINH, tháng 07 năm 2009 CÔNG TRÌNH ĐƯỢC HOÀN THÀNH TẠI TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH Cán bộ hướng dẫn khoa học : TS. ĐỖ HỒNG TUẤN (Ghi rõ họ, tên, học hàm, học vị và chữ ký) PGS. TS. PHẠM HỒNG LIÊN (Ghi rõ họ, tên, học hàm, học vị và chữ ký) Cán bộ chấm nhận xét 1 : TS. NGUYỄN MINH HOÀNG (Ghi rõ họ, tên, học hàm, học vị và chữ ký) Cán bộ chấm nhận xét 2 : TS. LƯU THANH TRÀ (Ghi rõ họ, tên, học hàm, học vị và chữ ký) Luận văn thạc sĩ được bảo vệ tại HỘI ĐỒNG CHẤM BẢO VỆ LUẬN VĂN THẠC SĨ TRƯỜNG ĐẠI HỌC BÁCH KHOA, ngày . . . . . tháng 07 năm 2009. ii TRƯỜNG ĐẠI HỌC BÁCH KHOA KHOA ĐIỆN – ĐIỆN TỬ ---------------- CỘNG HOÀ XÃ HỘI CHỦ NGHIÃ VIỆT NAM Độc Lập - Tự Do - Hạnh Phúc ---oOo--Tp. HCM, ngày . . . . . tháng . . . . . năm 2009 NHIỆM VỤ LUẬN VĂN THẠC SĨ Họ và tên học viên: .NGUYỄN QUANG VINH Phái: Nam Ngày, tháng, năm sinh: 19/01/1984 Nơi sinh:Vĩnh Long Chuyên ngành: KỸ THUẬT ĐIỆN TỬ Khóa (Năm trúng tuyển): 2007 - MSHV: 01407366 1- TÊN ĐỀ TÀI: DỊCH VỤ VỊ TRÍ PHÂN CẤP CHO ĐỊNH TUYẾN TRONG MẠNG MANET. 2- NHIỆM VỤ LUẬN VĂN: - Tìm hiểu tổng quan về mạng MANET. - Tìm hiểu các kiểu định tuyến dựa vào thông tin vị trí và các loại dịch vụ vị trí trong mạng MANET. - Tìm hiểu và xây dựng dịch vụ vị trí phân cấp. - Viết và thực hiện chương trình mô phỏng phương pháp đề xuất. - So sánh, nhận xét và đánh giá kết quả. - Kết luận và kiến nghị. 3- NGÀY GIAO NHIỆM VỤ : . . . . . . . . . . . . . . . . . . . . . 4- NGÀY HOÀN THÀNH NHIỆM VỤ : . . . . . . . . . . . . . . . . . . . . . 5- HỌ VÀ TÊN CÁN BỘ HƯỚNG DẪN (Ghi đầy đủ học hàm, học vị ): TS. ĐỖ HỒNG TUẤN và PGS. TS. PHẠM HỒNG LIÊN Nội dung và đề cương Luận văn thạc sĩ đã được Hội Đồng Chuyên Ngành thông qua. CÁN BỘ HƯỚNG DẪN (Họ tên và chữ ký) CHỦ NHIỆM BỘ MÔN QUẢN LÝ CHUYÊN NGÀNH (Họ tên và chữ ký) iii KHOA QL CHUYÊN NGÀNH (Họ tên và chữ ký) LỜI CẢM ƠN Lời đầu tiên, tôi xin gửi lời cảm ơn chân thành đến Thầy TS. Đỗ Hồng Tuấn và Cô PGS. TS. PHẠM HỒNG LIÊN, Thầy Cô đã luôn tận tình chỉ bảo và hướng dẫn tôi trong suốt quá trình hoàn thành luận văn này. Tôi xin cảm ơn Thầy TS. NGUYỄN MINH HOÀNG, Thầy đã nhiệt tình giúp đỡ trong quá trình phản biện luận văn và cho tôi những lời khuyên hết sức ý nghĩa, quan trọng trong việc nghiên cứu khoa học. Bên cạnh đó, tôi luôn ghi nhớ và xin gửi lời cảm ơn đến các Thầy, Cô trong trường Đại Học Bách Khoa TP Hồ Chí Minh, đặc biệt là các Thầy, Cô thuộc bộ môn Viễn Thông, những người đã tận tình giảng dạy và truyền đạt cho tôi những kiến thức trong suốt thời gian thời gian học Cao học cũng như học Đại học tại trường Đại Học Bách Khoa TP Hồ Chí Minh. Xin được gửi lời cảm ơn đến Bố Mẹ, Vợ và những người thân trong gia đình đã luôn ở bên cạnh, có những lời động viên, khuyến khích tôi trong suốt quá trình học tập và thực hiện luận văn. Cuối cùng, tôi xin gửi lời cảm ơn đến các bạn bè, đồng nghiệp, đặc biệt là các thành viên trong lớp cao học kỹ thuật điện tử 2007, các bạn Trung, Hùng, Chiến, Xuân Vinh… Họ đã luôn nhiệt tình giúp đỡ tôi vượt qua các khó khăn trong học tập cũng như chia sẻ trong công việc. TPHCM, tháng 07 năm 2009 Nguyễn Quang Vinh iv TÓM TẮT Với sự phổ biến của các thiết bị định vị và được sự hỗ trợ mạnh mẽ bởi các hệ thống như: GPS (Global Position System - Mỹ), GLONASS (GLObal Navigation Satellite System - Nga) hoặc Galileo (Châu Âu). Các giao thức định tuyến theo vị trí trong mạng MANET (Mobile Ad-hoc NETwork) ngày càng phát triển. Nhiệm vụ quan trọng khi thực hiện định tuyến theo vị trí là xác định được vị trí và khoảng cách của node đích cũng như các node xung quanh. Và việc này được thực hiện thông qua dịch vụ vị trí (location service). Hiệu quả của việc định tuyến theo vị trí sẽ phụ thuộc vào dịch vụ vị trí. Ở đây, luận văn này trình bày một loại hình dịch vụ vị trí phân cấp (ta gọi tắt là HLS - Hierarchical Location Service [33]). HLS chia toàn bộ khu vực bao phủ của mạng thành các vùng phân cấp khác nhau. Vùng có level cao nhất chính là toàn bô mạng. Vùng này sẽ được chia thành các vùng level thấp hơn cho đến khi đạt được level thấp nhất, gọi là cell. Đối với node A, một cell đặc biệt được lựa chọn trong mỗi mức phân cấp của mạng bởi một hàm “hash”. Khi A thay đổi vị trí, nó chuyển các thông tin cập nhật vị trí đến các cell này (gọi là “Responsible Cells” - RCs của A). Nếu một node nào đó muốn xác định vị trí của node A, nó cũng sẽ sử dụng một hàm “hash” tương tự để xác định các cell mà ở đó có thể có thông tin vị trí của node A. Sau đó nó thực hiện việc gửi các “yêu cầu thông vị trí” đến các cell này theo thứ tự phân cấp cho đến khi nó nhận được thông tin phản hồi về vị trí node A. HLS được thực hiện mô phỏng kết hợp với giao thức định tuyến GPSR, các kết quả mô phỏng dưới sự thay đổi của mật độ node, vận tốc chuyển động của node cho ta các kết quả tốt về tỉ lệ thành công và thời gian đáp ứng nhanh. Bên cạnh đó, thông qua việc so sánh với dịch vụ vị trí phổ biến GLS (Grid Location Service) cho ta thấy HLS có tỉ lệ thành công cao hơn, thời gian đáp ứng nhanh hơn tuy nhiên có những thời điểm lượng băng thông tiêu tốn nhiều hơn so với GLS. iv MỤC LỤC CHƯƠNG 1: GIỚI THIỆU ............................................................................ 1 1.1 1.2 1.3 1.4 Giới thiệu vấn đề................................................................................................ 1 Mục tiêu của luận văn ........................................................................................ 2 Phạm vi đề tài .................................................................................................... 4 Bố cục của luận văn ........................................................................................... 4 CHƯƠNG 2: CÁC VẤN ĐỀ TRONG MẠNG MANET................................ 5 2.1 Giới thiệu sơ lược về mạng MANET ....................................................................... 5 2.1.1 Sự ra đời mạng MANET ................................................................................... 5 2.1.2 Giới thiệu về mạng MANET ............................................................................. 5 2.1.3 Nguyên tắc hoạt động........................................................................................ 7 2.2 Những ứng dụng trong mạng MANET..................................................................... 8 2.2.1 Trong quân sự ................................................................................................... 8 2.2.2 Trong mạng cục bộ ........................................................................................... 8 2.2.3 Trong trường hợp khẩn cấp ............................................................................... 8 2.2.4 Mạng cảm biến không dây ................................................................................ 9 2.3 Những thách thức đối với mạng MANET ................................................................ 9 2.3.1 Giao thức định tuyến đa hop.............................................................................. 9 2.3.2 Khả năng mở rộng của mạng........................................................................... 10 2.3.3 Bảo mật .......................................................................................................... 10 2.3.4 Chất lượng dịch vụ.......................................................................................... 10 2.3.5 Tiêu tốn năng lượng ........................................................................................ 11 2.4 Định tuyến trong mạng MANET............................................................................ 11 2.4.1 Các giao thức định tuyến trong mạng cố định.................................................. 11 2.4.2 Các giao thức định tuyến trong mạng MANET................................................ 12 2.4.2.1 Proactive .................................................................................................. 13 2.4.2.2 Reactive ................................................................................................... 14 2.5 Định tuyến dựa vào thông tin vị trí trong mạng MANET ....................................... 17 2.5.1 Giao thức LAR ............................................................................................... 17 2.5.2 Giao thức DREAM ......................................................................................... 19 2.5.3 Giao thức GPSR.............................................................................................. 20 2.5.4 Giao thức Ellipsoid ......................................................................................... 26 2.6 Dịch vụ vị trí ......................................................................................................... 26 2.6.1 Homezone....................................................................................................... 26 2.6.2 GLS (Grid Location Service) .......................................................................... 27 CHƯƠNG 3: DỊCH VỤ VỊ TRÍ PHÂN CẤP HLS ...................................... 31 3.1 Cells ...................................................................................................................... 32 3.1.1 Cấu trúc .......................................................................................................... 32 3.1.2 Responsible Cells............................................................................................ 33 3.2 Cập nhật vị trí ........................................................................................................ 34 3.3 Handovers ............................................................................................................. 37 3.4 Yêu cầu thông tin vị trí .......................................................................................... 38 CHƯƠNG 4: TRIỂN KHAI THỰC HIỆN VỚI NS-2 (PHIÊN BẢN 2.33).. 41 4.1 HLS và NS-2 ......................................................................................................... 41 v 4.1.1 Các thành phần triển khai................................................................................ 41 4.1.2 Các tính năng chưa triển khai .......................................................................... 47 4.1.3 Dạng và kích thước gói dữ liệu HLS ............................................................... 48 4.2 GLS và NS-2 ......................................................................................................... 50 4.2.1 Dạng và kích thước gói dữ liệu GLS ............................................................... 51 4.3 Cách thức mô phỏng các đối tượng không dây di động trong NS-2 ........................ 51 4.4 IEEE 802.11 .......................................................................................................... 55 4.5 Null MAC.............................................................................................................. 55 4.6 BonnMotion .......................................................................................................... 56 4.7 Perl........................................................................................................................ 56 CHƯƠNG 5: MÔ PHỎNG VÀ ĐÁNH GIÁ................................................ 58 5.1 Thông số mô phỏng ............................................................................................... 58 5.1.1 Các khái niệm ................................................................................................. 58 5.1.2 Kịch bản mô phỏng......................................................................................... 59 5.2 Thực hiện mô phỏng .............................................................................................. 60 5.2.1 Các thông số đánh giá ..................................................................................... 61 5.2.2 Kết quả mô phỏng ở chế độ Greedy forwarding .............................................. 61 5.2.2.1 Tỉ lệ thành công........................................................................................ 61 5.2.2.2 Băng thông tiêu tốn (bandwidth consumption).......................................... 65 5.2.2.3 Thời gian đáp ứng (response time) ........................................................... 68 5.2.3 Kết quả mô phỏng ở chế độ Perimeter forwarding........................................... 72 5.2.3.1 Tỉ lệ thành công........................................................................................ 72 5.2.3.2 Băng thông tiêu tốn (bandwidth consumption).......................................... 75 5.2.3.3 Thời gian đáp ứng (response time) ........................................................... 77 5.3 Phân tích các trường hợp thất bại của HLS............................................................. 81 CHƯƠNG 6: KẾT LUẬN............................................................................ 84 6.1 Tổng kết ................................................................................................................ 84 6.2 Hướng nghiên cứu trong tương lai ......................................................................... 85 TÀI LIỆU THAM KHẢO ............................................................................ 88 PHỤ LỤC .................................................................................................... 92 vi DANH MỤC HÌNH Hình 1.1: Nhóm các cell lại thành vùng. ............................................................................ 3 Hình 1.2: Candidate tree với cấu trúc phân cấp đến level-3................................................ 3 Hình 2.1: Mô hình mạng có cấu trúc.................................................................................. 5 Hình 2.2: Ví dụ về mạng MANET..................................................................................... 6 Hình 2.3: Nguyên tắc hoạt động mạng MANET ................................................................ 7 Hình 2.4 Ứng dụng mạng MANET trong quân sự.............................................................. 8 Hình 2.5: Ví dụ minh họa vùng Expected zone và request zone ....................................... 18 Hình 2.6: Ví dụ về thuật toán Greedy .............................................................................. 21 Hình 2.7: Greedy forwarding không thành công .............................................................. 23 Hình 2.8: Quy tắc bàn tay phải ........................................................................................ 24 Hình 2.9: Đồ thị không phẳng.......................................................................................... 25 Hình 2.10: Ví dụ về giải thuật ellipsoid chọn next hop cho việc forward dữ liệu .............. 26 Hình 2.11: Ví dụ về server vị trí trong GLS ..................................................................... 29 Hình 2.12: Ví dụ về yêu cầu thông tin vị trí trong GLS.................................................... 30 Hình 3.1: Nhóm các cell lại thành vùng. .......................................................................... 32 Hình 3.2 Candidate tree với cấu trúc phân nhánh đến level-3........................................... 34 Hình 3.3: Ví dụ về responsible cells của 1 node. .............................................................. 35 Hình 3.4: Cập nhật vị trí trực tiếp .................................................................................... 36 Hình 3.5 Cập nhật vị trí gián tiếp..................................................................................... 37 Hình 3.6: Ví dụ về yêu cầu thông tin vị trí ....................................................................... 40 Hình 4.1. Các candidate cell cho node 11 khi chúng được sử dụng trong mô phỏng......... 42 Hình 4.2: Thông tin trả lời các yêu cầu vị trí tại các level phân cấp khác nhau dựa vào vị trí của node gửi yêu cầu (A) và node đích (B). Các hình vuông mờ là các responsible cell theo hình 4.1. .......................................................................................................................... 45 Hình 4.3 Cơ chế hoạt động của home perimeter............................................................... 47 Hình 4.4: Môi trường mô phỏng mạng di động ................................................................ 52 Hình 4.5: Node di động ................................................................................................... 53 Hình 4.6: Minh họa các thông số cấu hình cho node trong NS-2. ..................................... 54 Hình 5.1: Mô hình chuyển động RandomWaypoint của các node .................................... 59 Hình 5.2: Các node thực hiện yêu cầu tìm vị trí các node khác......................................... 60 Hình 5.3: Tỉ lệ thành công của HLS và GLS ở chế độ Greedy forwarding theo mật độ node. ............................................................................................................................... 63 Hình 5.4: Tỉ lệ thành công của HLS và GLS ở chế độ Greedy forwarding theo vận tốc chuyển động của node. .................................................................................................... 65 Hình 5.5: Băng thông tiêu tốn của HLS và GLS ở chế độ greedy forwarding. .................. 68 Hình 5.6: Thời gian đáp ứng của HLS ............................................................................. 70 Hình 5.7: Thời gian đáp ứng của GLS ............................................................................. 71 Hình 5.8: Tỉ lệ thành công của HLS và GLS ở chế độ Perimeter forwarding theo mật độ node. ............................................................................................................................... 74 Hình 5.9: Tỉ lệ thành công của HLS và GLS ở chế độ Perimeter forwarding theo vận tốc chuyển động của node. .................................................................................................... 75 Hình 5.10: Băng thông tiêu tốn của HLS và GLS ở chế độ perimeter forwarding............. 77 Hình 5.11: Thời gian đáp ứng của HLS ở chế độ perimeter forwarding............................ 79 Hình 5.12: Thời gian đáp ứng của GLS ở chế độ perimeter forwarding............................ 80 Hình 5.13 : Các kết quả có thể xảy ra của query vị trí bởi HLS........................................ 83 vii DANH MỤC BẢNG Bảng 2.1: Hoạt động của DSDV ...................................................................................... 15 Bảng 2.2: Hoạt động của DSR ......................................................................................... 16 Bảng 4.1: Kích thước của các trường được sử dụng trong việc tính toán bandwidth......... 49 Bảng 4.2: Kích thước HLS header của các gói dữ liệu. .................................................... 50 Bảng 4.3: Kích thước gói dữ liệu GLS headers. ............................................................... 51 Bảng 5.1: Các thông số được trình bày trong RFC 2501. ................................................. 58 Bảng 5.2: Các thông số cho việc mô phỏng ..................................................................... 60 viii DANH MỤC TỪ VIẾT TẮT AODV Ad hoc On-demand Distance Vector AP Access Point ARP Address Resolution Protocol CBR Constant Bit Rate DREAM Distance Routing Effect Algorithm for Mobility DSDV Destination Sequence Distance Vector DSR Dynamic Source Routing GLONASS GLObal Navigation Satellite System GLS Grid Location Service GPS Global Position System GPSR Greedy Perimeter Stateless Routing GPSS Geographical Region Summary Service HLS Hierarchical Location Service IEEE Institute of Electrical and Electronic Engineers IFQ InterFace Queue IP Internet Protocol ISO International Organization for Standardization LAN Local Area Network LAR Location-Aided Routing protocol LLC Link Layer Control LS Link-State LSI Location Server Identification LSPs Link-State Packets MAC Medium Access Control MANET Mobile Ad-hoc NETwork MN Mobile Node NS-2 Network Similator 2 ix ODL On-Demand Learning OLSR Optimized Link State Routing OSI Open Systems Interconnection OTcl Object Tool command language PDA Personal Digital Assistant PERL Practical Extraction and Report Language RC Responsible Cell RFC Request For Comment RLS Reactive Location Service RNG Relative Neighborhood Graph RREQ Route REQuest SPA Self Positioning Algorithm TBRPF Topology Broadcast based on Reverse-Path Forwarding TDM Time Division Multiplexing TLR Terminode Local Routing TORA Temporally-Ordered Routing Algorithm TTL Time To Live VINT Virtual InterNetwork Testbed ZRP Zone Routing Protocol WLAN Wireless Local Area Network WPAN Wireless Personal Network x CHƯƠNG 1: GIỚI THIỆU CHƯƠNG 1 GIỚI THIỆU 1.1 Giới thiệu vấn đề Định tuyến trong mạng MANET là một vấn đề phức tạp. Trước đây, các giao thức định tuyến proactive được đề nghị, những giao thức này duy trì thông tin về các đường liên kết trong mạng và thậm chí ngay cả khi các đường này không được dùng đến. Với các mạng MANET tương đối phức tạp, việc luôn duy trì thông tin về các đường định tuyến không sử dụng sẽ dẫn đến hao tốn băng thông và tài nguyên mạng. Sau đó, các giao thức định tuyến reactive được phát triển để tạo nên các đường định tuyến khi cần thiết. Tuy nhiên, các đường định tuyến này cần phải được duy trì trong suốt thời gian kết nối. Đây là vấn đề khó khăn nếu cấu trúc mạng thay đổi thường xuyên. Các giao thức định tuyến trong mạng MANET có thể được phân loại như sau [9, 18]: ¾ Topology-based: o Proactive: luôn duy trì thông tin định tuyến trước khi dữ liệu được gửi, như: DSDV [19], TBRPF [22], OLSR [28]. o Reactive: chỉ thực hiện việc tìm định tuyến khi có yêu cầu thiết lập kết nối, như: DSR [11], AODV [13], TORA [32] o Hybrid: kết hợp giữa proactive và reactive để tăng tính linh động, như: ZRP [20]. ¾ Position-based: các gói dữ liệu được định tuyến theo thông tin vị trí, như: Ellipsoid [11], LAR [6], GPSR [3]. Đối với định tuyến theo vị trí, việc quyết định các đường định tuyến sẽ dựa vào thông tin vị trí của các node, đây là giải pháp được đề nghị khi cấu hình mạng linh động hoặc thay đổi thường xuyên. Để thực hiện được định tuyến theo vị trí, node bắt buộc phải khám phá khu vực của node mà nó muốn giao tiếp hay trao đổi dữ liệu. Nhiệm vụ quan trọng khi thực hiện định tuyến theo vị trí là xác định được vị trí GVHD: TS. ĐỖ HỒNG TUẤN 1 HVTH: NGUYỄN QUANG VINH CHƯƠNG 1: GIỚI THIỆU và khoảng cách của node đích cũng như các node xung quanh. Và việc này được thực hiện thông qua dịch vụ vị trí. Hiệu quả của việc định tuyến theo vị trí sẽ phụ thuộc vào dịch vụ vị trí. Đây là vấn đề sẽ được trình bày và đánh giá trong luận văn. 1.2 Mục tiêu của luận văn Qua quá trình tìm hiểu về các vấn đề định tuyến theo vị trí trong mạng MANET đã và đang được thực hiện hiện nay thông qua các công trình nghiên cứu như: “ Định tuyến dựa vào thông tin vị trí trong mạng MANET”, Nguyễn Thái Hùng, Luận văn Thạc sĩ, Đại học Bách khoa Hồ Chí Minh, 2008 [1]…ta nhận thấy các giải thuật về dịch vụ vị trí vẫn chưa được nghiên cứu nhiều. Ở đây, luận văn này trình bày về dịch vụ vị trí phân cấp (ta gọi tắt là HLS Hierarchical Location Service [33]). Nó cung cấp cho chúng ta một nhận xét và đánh giá về các loại hình dịch vụ vị trí, cũng như ảnh hưởng đến hiệu quả của định tuyến theo vị trí thông qua: cách tổ chức đồ hình mạng, cách thức cập nhật, yêu cầu và trả lời thông tin của các node trong mạng. Các tiêu chí được dùng để đánh giá dịch vụ vị trí bao gồm: tỉ lệ thành công của yêu cầu vị trí, thời gian đáp ứng, lượng băng thông tiêu tốn… Ý tưởng cơ bản của HLS là chia toàn bộ khu vực bao phủ của mạng thành các vùng phân cấp khác nhau. Vùng có level cao nhất chính là toàn bô mạng. Vùng này sẽ được chia thành các vùng level thấp hơn cho đến khi đạt được level thấp nhất, ta gọi vùng thấp nhất này là cell như trong hình 1.1. Đối với một node A, một cell đặc biệt được lựa chọn trong mỗi mức level phân cấp của mạng bởi một hàm “hash”. Khi A thay đổi vị trí, nó chuyển các thông tin cập nhật vị trí đến các cell này (gọi là “responsible cells” của A). Nếu một node nào đó muốn xác định vị trí của node A, nó cũng sẽ sử dụng 1 hàm “hash” tương tự để xác định các cell mà ở đó có thể có thông tin vị trí của node A. Sau đó nó thực hiện việc gửi các gói dữ liệu “yêu cầu thông vị trí” đến các cell này theo thứ tự phân cấp cho đến khi nó nhận được thông tin phản hồi về vị trí node A. GVHD: TS. ĐỖ HỒNG TUẤN 2 HVTH: NGUYỄN QUANG VINH CHƯƠNG 1: GIỚI THIỆU (a) Cell (b) Vùng level 1 (c) Vùng level 2 Hình 1.1: Nhóm các cell lại thành vùng. Nói một cách khác, HLS chia toàn bộ khu vực rộng lớn của mạng thành các vùng nhỏ gọi là các cell và gán mỗi node vào một tập hợp S của các cell. Việc cập nhật và yêu cầu thông tin vị trí của các node sẽ được gửi đến các tập hợp con của tập S này. Việc lựa chọn tập con nào thông qua hàm hash và hoàn toàn phụ thuộc vào: số ID của mỗi node, phân cấp nhóm các cell của tập S và phụ thuộc vào vị trí hiện tại của node trong mạng, như trong hình 1.2 Hình 1.2: Candidate tree với cấu trúc phân cấp đến level-3. Đây là một vấn đề mở và hoàn toàn có thể được phát triển tiếp theo để có những đánh giá chi tiết, cụ thể tùy theo những kịch bản và môi trường khác nhau khi triển khai áp dụng trong thực tế. Bên cạnh đó thì thông qua việc đánh giá với một số dịch vụ vị trí phổ biến như GLS (Grid Location Service) sẽ thể hiện một số ưu điểm của GVHD: TS. ĐỖ HỒNG TUẤN 3 HVTH: NGUYỄN QUANG VINH CHƯƠNG 1: GIỚI THIỆU dịch vụ vị trí phân cấp HLS về tỉ lệ yêu cầu thông tin vị trí thành công, thời gian đáp ứng… 1.3 Phạm vi đề tài Do thời gian tìm hiểu đề tài là có hạn nên luận văn xin được trình bày trong phạm vi sau: Thuật toán định tuyến theo vị trí được sử dụng trong luận văn là GPSR – Greedy Perimeter Stateless Routing, thuật toán này hoàn toàn dựa vào thông tin vị trí của node để chọn đường định tuyến ở các chế độ greedy forwarding và perimeter forwarding. Hàm hash sử dụng đơn giản và cần được tối ưu theo các môi trường triển khai thực tế. Thực hiện mô phỏng và đánh giá với quy mô mạng nhỏ, số lượng node tương đối ít vì bị giới hạn bởi khả năng hỗ trợ tính toán mô phỏng của máy tính. Cập nhật thông tin vị trí theo phương pháp gián tiếp. 1.4 Bố cục của luận văn Luận văn được chia thành 6 chương. Chương 2 trình bày về các khái niệm chung trong mạng MANET, các thuật toán định tuyến proactive, reactive và các thuật toán định tuyến theo theo vị trí như: DSDV, DSR, LAR, GPSR... Đồng thời cũng giới thiệu về các dịch vụ vị trí trong mạng MANET như: Homezone và GLS. Chương 3 là phần chính của luận văn được dành riêng để giới thiệu chi tiết về dịch vụ vị trí phân cấp HLS, thuật toán cho việc cập nhật và yêu cầu thông tin vị trí. Chương 4 trình bày chi tiết về các công việc triển khai thực hiện HLS và GLS với NS phiên bản 2.33, các kiểu định dạng gói dữ liệu và các công cụ hỗ trợ cho việc thực hiện mô phỏng như: Bonnmotion, Perl… Chương 5 trình bày các kết quả mô phỏng được, phân tích và đánh giá dịch vụ vị trí HLS với GLS dựa trên các thông số như: tỉ lệ thành công, thời gian đáp ứng, băng thông tiêu thụ và ảnh hưởng của mật độ, vận tốc chuyển động của node. Chương 6 là phần kết luận và hướng phát triển trong tương lai. GVHD: TS. ĐỖ HỒNG TUẤN 4 HVTH: NGUYỄN QUANG VINH CHƯƠNG 2: CÁC VẤN ĐỀ TRONG MẠNG MANET CHƯƠNG 2 CÁC VẤN ĐỀ TRONG MẠNG MANET 2.1 Giới thiệu sơ lược về mạng MANET 2.1.1 Sự ra đời mạng MANET Ngày nay, với sự phát triển của khoa học kĩ thuật, chúng ta đang tận hưởng những ứng dụng, tiện ích của công nghệ thông tin truyền thông đem lại, mà cụ thể là các ứng dụng không dây. Điện thoại di động, máy tính xách tay đã trở thành một phần không thể thiếu trong nhiều công việc cũng như trong cuộc sống của nhiều người. Tuy nhiên, những thiết bị này đòi hỏi phải có một cơ sở hạ tầng thì mới có thể kết nối mạng với nhau được. Đối với điện thoại di động, chúng ta cần có sự hoạt động của một mạng cell, các máy tính xách tay thì cần các Access Point (AP) [19]. Hình 2.1: Mô hình mạng có cấu trúc Tuy nhiên không phải lúc nào chúng ta cũng có thể lắp đặt các thiết bị hạ tầng này. Đó có thể là những nơi mà điều kiện không cho phép như chiến trường hay những nơi đang bị thiên tai núi lửa, động đất hay lụt lội,… Vậy chúng ta phải làm sao để có thể tiếp tục sử dụng được sự tiện lợi của mạng không dây? Vì thế mạng di động ad-hoc (MANET: Mobile Ad Hoc Network) đã ra đời trong hoàn cảnh đó. 2.1.2 Giới thiệu về mạng MANET GVHD: TS. ĐỖ HỒNG TUẤN 5 HVTH: NGUYỄN QUANG VINH CHƯƠNG 2: CÁC VẤN ĐỀ TRONG MẠNG MANET Tương lai của công nghệ thông tin sẽ dựa chủ yếu vào công nghệ không dây. Những mạng cell và mạng truyền thống vẫn sẽ còn tồn tại. Tuy nhiên ở một khía cạnh nào đó các mạng này sẽ bị hạn chế bởi các kiến trúc hạ tầng mà các mạng này đòi hỏi (chẳng hạn như các trạm thu phát gốc, các bộ định tuyến). Đối với mạng MANET thì những hạn chế này đã được loại bỏ. Hình 2.2: Ví dụ về mạng MANET MANET là chìa khóa cho sự phát triển của các mạng không dây. Mạng MANET thường được tạo nên bởi các node ngang hàng, giao tiếp nhau thông qua kênh truyền vô tuyến mà không cần bất kì bộ điều khiển trung tâm nào. Mặc dù vẫn được dùng chủ yếu trong quân sự, nhưng các ứng dụng về thương mại đã ngày càng được phát triển. Những ứng dụng như nhiệm vụ giải cứu trong các thảm họa thiên nhiên, các mục đích thương mại và giáo dục, mạng cảm biến không dây… ngày càng phát triển [19]. Mạng MANET vẫn bị ảnh hưởng bởi các vấn đề khó khăn của mạng không dây truyền thống như tối ưu băng thông, điều khiển năng lượng, nâng cao về đường truyền. Hơn nữa, với bản chất về đường truyền đa hop và thiếu các hạ tầng cố định đã phát sinh ra các khó khăn mới như cấu hình quảng bá, tìm đường và duy trì tuyến trong quá trình định tuyến. Trong mạng MANET, cấu hình mạng thường xuyên thay đổi một cách ngẫu nhiên. Thêm nữa, sự phân bố của các node và khả năng tự tổ chức đóng một vai trò quan trọng. Những đặc tính chính có thể tổng kết dưới đây: GVHD: TS. ĐỖ HỒNG TUẤN 6 HVTH: NGUYỄN QUANG VINH CHƯƠNG 2: CÁC VẤN ĐỀ TRONG MẠNG MANET • Cấu hình mạng năng động và sự thay đổi thường xuyên là không dự đoán được. • Sử dụng kênh truyền không dây nên có sự hạn chế về dung lượng hơn là mạng có dây truyền thống. • Sự bảo mật là hạn chế do kênh truyền không dây. • Bị ảnh hưởng bởi sự mất mát gói dữ liệu lớn, chịu delay và jitter lớn hơn là mạng cố định do sự lan truyền sóng vô tuyến. • Các node trong mạng MANET chỉ sử dụng pin như là nguồn năng lượng chính. Vì thế, tiết kiệm năng lượng là một tiêu chuẩn quan trọng trong việc thiết kế hệ thống. Ngoài ra, tập hợp các lệnh được thực hiện phụ thuộc vào năng lượng sẵn có của nó (CPU, bộ nhớ,…). Mạng MANET không chỉ dựa trên một công nghệ mà nó tận dụng các công nghệ tiên tiến khác nhau. Ở đây, nhiệm vụ là làm sao định nghĩa các giao diện (interface) để nó có thể được sử dụng bởi các lớp trên mà không làm ảnh hưởng đến việc sử dụng công nghệ mới của lớp vật lý. Thông tin như là sự phân bố các node, mật độ của mạng, link hỏng,… phải được chia sẽ bởi các lớp khác nhau, lớp MAC và lớp mạng phải có sự hợp tác tốt để có cái nhìn tốt về cấu hình mạng và tối ưu số lượng các thông báo trên mạng. Mạng MANET rất độc lập về cấu trúc và quyền ưu tiên, cung cấp một tiềm năng lớn cho người sử dụng. Sự thật là chỉ cần từ 2 node trở lên là có thể tạo nên một mạng MANET miễn là các node đủ gần cho sự lan truyền sóng vô tuyến mà không có bất kì sự can thiệp của bên ngoài. 2.1.3 Nguyên tắc hoạt động Hình 2.3: Nguyên tắc hoạt động mạng MANET GVHD: TS. ĐỖ HỒNG TUẤN 7 HVTH: NGUYỄN QUANG VINH CHƯƠNG 2: CÁC VẤN ĐỀ TRONG MẠNG MANET Hình 2.3 là một ví dụ diễn tả hoạt động của mạng MANET. Ở đây node A truyền nhận dữ liệu trực tiếp (đơn hop) với các node khác (ví dụ node B) miễn là có sẵn một kênh truyền radio giữa chúng. Nếu không, giữa hai node sẽ có sự truyền nhận dữ liệu đa hop trong đó một hay nhiều node trung gian có nhiệm vụ giống như một router. Chẳng hạn nếu không có kênh truyền thẳng giữa A và C lúc đó node B sẽ có nhiệm vụ giống như một router. Đây là điểm đặc biệt của mạng MANET. 2.2 Những ứng dụng trong mạng MANET 2.2.1 Trong quân sự Từ xưa đến nay, các công nghệ kĩ thuật cao luôn được phát triển mạnh trong lĩnh vực quân sự. Vì thế quân sự cũng là động lực chính cho sự phát triển của mạng MANET. Mạng MANET không đòi hỏi sự điều khiển từ trung tâm cũng như là tồn tại một cơ sở hạ tầng sẵn có nên nó rất là hoàn hảo cho các ứng dụng quân sự. Trên chiến trường, binh lính có thể liên lạc với nhau bất cứ lúc nào và bất cứ nơi đâu. Hình 2.4 Ứng dụng mạng MANET trong quân sự 2.2.2 Trong mạng cục bộ Đây là mạng mà có thể gặp được dễ dàng trong các hội nghị hoặc trong lớp học. Khi các node muốn kết nối lại với nhau để có thể truyền và nhận dữ liệu. 2.2.3 Trong trường hợp khẩn cấp GVHD: TS. ĐỖ HỒNG TUẤN 8 HVTH: NGUYỄN QUANG VINH CHƯƠNG 2: CÁC VẤN ĐỀ TRONG MẠNG MANET Do đặc tính không cần hạ tầng cố định cũng như là sự quản trị nên mạng MANET cũng rất phù hợp trong các tình huống mà ở đó hạ tầng mạng đã bị phá hủy hay không sẵn có do một nguyên nhân nào đó. Mục đích của việc thiết lập mạng MANET trong tình huống này là giúp cho các thiết bị di động có thể liên lạc được với nhau và sử dụng được các dịch vụ mạng vốn dĩ rất quan trọng trong các công tác cứu hộ khẩn cấp. Chẳng hạn lính cứu hỏa và cảnh sát có thể liên lạc được với nhau và trao đổi thông tin một cách nhanh chóng khi mà hạ tầng đã bị phá hủy hoặc không có sẵn. 2.2.4 Mạng cảm biến không dây Nhiều nghiên cứu gần đây tập trung vào các mạng gồm những thiết bị cảm biến. Mạng cảm biến không dây (wireless sensor networks) sử dụng các cảm biến để thu thập thông tin và truyền tới một bộ phận xử lý trung tâm. Khi mà một cảm biến được đặt thì vị trí của nó luôn cố định. Công nghệ này rất hữu ích đối với những môi trường mà khó khăn trong việc cung cấp một mạng có cơ sở hạ tầng. Ví dụ trong môi trường bị nhiễm phóng xạ hóa học, thay vì phải gởi đến một đội cứu hộ khẩn cấp thì chúng ta chỉ việc lắp đặt các sensor để tạo thành một mạng ad-hoc. Các thiết bị cảm biến có kích thước nhỏ, năng lượng ít. Do đó tiết kiệm năng lượng là mục tiêu chính của người thiết kế mạng cảm biến. 2.3 Những thách thức đối với mạng MANET Trong mạng MANET, các node di chuyển một cách ngẫu nhiên, tự tổ chức và tự cấu hình lại khi nó di chuyển, tham gia hay rời khỏi mạng, vì thế mà cấu hình mạng thay đổi thường xuyên. Tất cả các node đóng vai trò như nhau trên mạng và các chức năng của mạng được phân phối và được quyết định bởi tất cả các node. Vì thế mạng MANET không cần một máy quản trị trung tâm. Tuy nhiên chính vì nguyên nhân này mà mạng MANET đã gặp phải không ít khó khăn. 2.3.1 Giao thức định tuyến đa hop GVHD: TS. ĐỖ HỒNG TUẤN 9 HVTH: NGUYỄN QUANG VINH