Khóa luận Mạng Ad-hoc và các giao thức định tuyến phổ biến của mạng Ad-hoc

Mạng Adhoc, Khóa luận tốt nghiệp Cử nhân CNTT, Ngô Hải Sơn, 2008 1 Nội dung khóa luận Ngày nay, mạng không dây trong đời sống con người đang ngày càng đóng vị trí quan trọng. Trong số các mạng không dây, mạng adhoc được quan tâm một cách đặc biệt. Không giống như mạng có dây truyền thống hay mạng không dây có sơ sở hạ tầng, với tính linh động cao, dễ dàng thiết lập nên mạng adhoc đang được ứng dụng trong nhiều lĩnh vực của xã hội. Trong đó, vấn đề định tuyến trong mạng adhoc là một trong những vấn đề quan trọng, đang được nghiên cứu rất nhiều vì nó ảnh hưởng rất lớn đến hiệu suất của mạng. Đây là những nội dung chính trong khóa luận này. Khóa luận gồm 4 chương. Chương đầu là khái quát chung về mạng không dây WLAN và mạng adhoc. Chương 2 đi sâu vào trình bày cấu trúc vật lý của mạng không dây theo chuẩn 802.11. Chương ba nói về tầm quan trọng của giao thức định tuyến trong mạng adhoc và trình bày cụ thể một số giao thức định tuyến phổ biến của mạng adhoc. Chương cuối cùng, dựa vào một số thực nghiệm thông qua bộ mô phỏng của những người nghiên cứu trước, tôi rút ra một số đánh giá và so sánh giữa các giao thức định tuyến. Do thời gian có hạn, luận văn của em có thể còn một số thiếu sót, rất mong nhận được sự chỉ bảo, góp ý và thông cảm của các thầy cô. Em hi vọng sau này có thể tiếp tục nghiên cứu sâu hơn về vấn đề này. Mạng Adhoc, Khóa luận tốt nghiệp Cử nhân CNTT, Ngô Hải Sơn, 2008 2 Lời cảm ơn Lời đầu tiên, em xin gửi lời cảm ơn sâu sắc đến PGS. TS. Nguyễn Đình Việt. Thầy đã tận tình chỉ bảo em trong suốt quá trình làm khóa luận này. Em cũng xin chân thành các thầy cô trong trường đã dạy dỗ em trong suốt những năm học tập tại trường. Cuối cùng, em cũng xin gửi lời cảm ơn đến gia đình và bạn bè, những người đã động viên em rất nhiều trong thời gian làm khóa luận. Hà Nội, ngày 1 tháng 6 năm 2008 Ngô Hải Sơn Mạng Adhoc, Khóa luận tốt nghiệp Cử nhân CNTT, Ngô Hải Sơn, 2008 3 Mục Lục Nội dung khóa luận .......................................................................................................................1 Danh sách các từ viết tắt ................................................................................................................5 Chương 1: Giới thiệu chung ...........................................................................................................7 1.1. Đặt vấn đề......................................................................................................................7 1.1.1. Khái niệm về WLAN[1],[3],[6] .....................................................................................7 1.1.2. Lịch sử ra đời mạng WLAN.....................................................................................8 1.1.3. Một số ưu và nhược điểm của WLAN ......................................................................8 1.2. Mạng adhoc......................................................................................................................10 1.2.1. Khái niệm và một số đặc điểm chung của mạng adhoc ..................................................10 1.2.2. Ví dụ về mạng adhoc ..................................................................................................11 1.2.3. Các ứng dụng của mạng adhoc ....................................................................................12 1.2.4. Một số vấn đề cần quan tâm trong mạng adhoc .............................................................13 1.3. Mục tiêu của luận văn .......................................................................................................14 Chương 2: Mạng LAN không dây ...........................................................................................15 2.1. Mạng WLAN theo chuẩn 802.11[1], [2],[6]..............................................................................15 2.1.1. Mạng WLAN có cơ sở hạ tầng ...............................................................................15 2.1.2. Mạng adhoc ..........................................................................................................16 2.2. Kiến trúc giao thức mạng WLAN theo chuẩn 802.11 ......................................................17 2.2.1. Lớp Vật Lý ................................................................................................................18 2.2.2. Lớp điều khiển truy cập môi trường truyền MAC..........................................................22 2.2.3. Lớp quản lý tầng MAC..........................................................................................28 Chương 3: Định tuyến trong mạng adhoc ................................................................................31 3.1. Giới thiệu về thuật toán định tuyến.....................................................................................31 3.2. Yêu cầu của thuật toán định tuyến cho mạng không dây adhoc ........................................31 3.3. Phân loại các thuật toán định tuyến cho mạng adhoc .......................................................35 3.3.1. DSDV (Destination Sequence Distance Vector) ......................................................35 Mạng Adhoc, Khóa luận tốt nghiệp Cử nhân CNTT, Ngô Hải Sơn, 2008 4 3.3.2. AODV (Adhoc On-Demand Distance Vector Routing) ............................................37 3.3.3. DSR (Dynamic Source Routing) ............................................................................38 3.3.4. TORA (Temporally Ordered Routing Algorithm) ....................................................40 Chương 4: Đánh giá hiệu suất các giao thức định tuyến bằng bộ mô phỏng mạng NS2 ....................42 4.1. Giới thiệu bộ mô phỏng NS2[4],[5] .......................................................................................42 4.2. Khả năng mô phỏng các mạng của NS2 ..............................................................................43 4.3. Mô phỏng mạng adhoc và các giao thức định tuyến trong mạng adhoc .................................43 4.3.1. Mô phỏng mạng adhoc................................................................................................43 4.3.2. Mô phỏng các giao thức định tuyến trong mạng adhoc [1, T.Việt], [4], [5].....................................45 4.4. Phân tích và so sánh hiệu suất của các giao thức định tuyến trong mạng adhoc ................48 4.4.1. Các tham số của môi trường: .......................................................................................48 4.4.2. Các thông số đánh giá hiệu suất: ..................................................................................49 4.4.3. Các thí nghiệm mô phỏng [1, T.Việt].................................................................................49 4.4.4. Nhận xét về hiệu suất của các giao thức định tuyến .................................................52 Kết luận......................................................................................................................................54 Phụ Lục......................................................................................................................................55 Tài liệu tham khảo……………………………………………………………………………... 61 Mạng Adhoc, Khóa luận tốt nghiệp Cử nhân CNTT, Ngô Hải Sơn, 2008 5 Danh sách các từ viết tắt 2G second-generation technology 3G third-generation technology ACK Acknowledgement AODV Adhoc On demand Distance Vector ATIM Adhoc Traffic Indication Map BS Base Station CBR Cluster Based Routing CFP Content Free Period CSMA/CA Carrier Sense Multiple Access/ Collision Avoidance CSMA/CD Carrier Sense Multiple Access/ Collision Detection CTS Clear to send DSDV Destination Sequence Distance Vector DIFS Distributed InterFrame Space DSR Dynamic Source Routing DSSS Direct Sequence Spread Spectrum DCF Distributed Coordination Function FCC Federal Communication Commission FDMA Frequency-Division Multiple Access FHSS Frequency Hopping Spread Spectrum GHz Gigahertz IEEE Institute of Electrical and Electronics Engineers ISM Industrial, Scientific and Medical IMEP Internet MANET Encapsulation Protocol Kbps Kilobits per second LAN Local Area Network Mạng Adhoc, Khóa luận tốt nghiệp Cử nhân CNTT, Ngô Hải Sơn, 2008 6 MAC Medium Access Control MANET Mobile Adhoc Networks Mbps Megabits per second MHz Megahertz NS-2 Network Simulation 2 NAV Network Allocation Vector OFDM Orthogonal Frequency-Division Multiplexing Otcl Object Tool Command Language PDA Personal Digital Assistant PLCP Layer Convergence Protocol PMD Physical Medium Dependent RREQ Route Request RREP Route Reply RTS Request To Send SIFS Short InterFrame Space TDMA Time Division Multiple Access TCP Transmission Control Protocol TORA Temporally Ordered Routing Algorithm UDP User Datagram Protocol Wi-Fi Wireless Fidelity WLAN Wireless Local Area Network Mạng Adhoc, Khóa luận tốt nghiệp Cử nhân CNTT, Ngô Hải Sơn, 2008 7 Chương 1: Giới thiệu chung 1.1. Đặt vấn đề Ngày nay, cùng với sự phát triển vượt bậc của khoa học công nghệ nói chung, ngành công nghệ thông tin đang ngày càng được đầu tư và phát triển mạnh mẽ. Khi mà ngày càng nhiều các lĩnh vực trong đời sống xã hội như y tế, giáo dục, xây dựng, kinh tế, ... ứng dụng tin học vào trong công việc thì Internet ngày càng khẳng định vị trí quan trọng của mình trong đời sống xã hội. Khi mà cuộc sống con người ngày càng phát triển thì nhu cầu trao đổi thông tin và giải trí của con người ngày càng cao. Con người muốn mình có thể kết nối với thế giới bất cứ lúc nào, bất cứ nơi đâu. Đó là lý do mà mạng không dây ra đời. Ngày nay, chúng ta có thể thấy được sự hiện diện của mạng không dây ở nhiều nơi như trong các tòa nhà, nơi công sở, bệnh viện hay các quán cà phê. Cùng với sự phát triển của mạng có dây truyền thống, mạng không dây cũng đang có những bước phát triển nhanh chóng nhằm đáp ứng như cầu truyền thông và giải trí của con người một cách tốt nhất. Khi mà mạng không dây ngày càng được quan tâm, đầu tư và phát triển thì ngày càng nhiều mô hình, kiến trúc mạng được đề xuất. Các mô hình, kiến trúc mạng này được đề ra nhằm làm cho mạng không dây dần thoát khỏi hoàn toàn sự phụ thuộc vào cơ sở hạ tầng. Một trong những mô hình mạng được đề xuất đó chính là mạng Adhoc (Mobile Adhoc Network) thường được viết tắt là MANET. Việc các mạng không dây ít phụ thuộc vào cơ sở hạ tầng là một điều rất thuận lợi nhưng lại có những vấn đề khác đặt ra như tốc độ mạng không ổn định như mạng có dây truyền thống, các nút mạng hay di chuyển, ... Do đó, cùng với vấn đề bảo mật của mạng không dây thì vấn đề định tuyến trong mạng là vô cùng quan trọng. Nó quyết định rất lớn đến hiệu suất của toàn mạng. Mạng cục bộ không dây (WLAN) 1.1.1. Khái niệm về WLAN[1],[3],[6] WLAN là một mạng cục bộ kết nối hai hay nhiều máy tính với nhau mà không sử dụng dây cáp mạng như các mạng có dây truyền thống. WLAN hiện nay đã được ứng dụng rộng rãi trong các tòa nhà, trường học, bệnh viện, một số nơi công cộng như quán cafe, ... Hai công nghệ chính được sử dụng để truyền thông trong WLAN là truyền thông bằng tia hồng ngoại (ở bước sóng 900 nm, 1nm = 10-9m) hoặc truyền thông bằng sóng vô tuyến. WLAN cũng có hai dạng kiến trúc là WLAN có cơ sở hạ tầng (sử dụng các Access Point để kết nối phần mạng không dây với phần mạng có dây truyền thống) và mạng không có cơ sở hạ tầng (mạng adhoc). Mạng Adhoc, Khóa luận tốt nghiệp Cử nhân CNTT, Ngô Hải Sơn, 2008 8 1.1.2. Lịch sử ra đời mạng WLAN Công nghệ WLAN lần đầu tiên được xuất hiện vào cuối những năm 90 của thế kỉ trước, khi mà các nhà sản xuất giới thiệu những sản phẩm hoạt động trong băng tần 900 MHz. Những giải pháp (chưa có sự thống nhất giữa các nhà sản xuất) này cung cấp tốc độ truyền dữ liệu 1Mbps, thấp hơn nhiều so với công nghệ sử dụng cáp khi đó (tốc độ truyền dữ liệu là 10Mbps). Năm 1992, các nhà sản xuất bắt đầu bán những sản phẩm WLAN đầu tiên sử dụng băng tần 2.4 GHz. Các sản phẩm này đã có tốc độ truyền dữ liệu cao hơn. Tuy nhiên nó vẫn là những giải pháp riêng biệt của từng nhà sản xuất và không được công bố rộng rãi. Năm 1997, chuẩn IEEE 802.11ra đời, hoạt động ở băng tần 2.4 GHz với tốc độ truyền dữ liệu là 2 Mbps (có thể nâng lên 10 Mbps). Đến cuối năm 1999 và đầu năm 2000, hai chuẩn mới lần lượt được IEEE công bố là chuẩn 802.11b (hoạt động ở dải tần 2.4 GHz) và 802.11a (hoạt động ở dải tần 5- 6GHz). Năm 1999 cũng đánh dấu một bước phát triển quan trọng trên thị trường mạng không dây khi hãng máy tính Apple thông báo, chuẩn Wi-Fi sẽ xuất hiện trên dòng máy iBook mới của họ. Năm 2003, IEEE công bố thêm một sự cải tiến mới là chuẩn 802.11g có thể hoạt động trên cả hai băng tần là 2.4GHz và 5GHz, tốc độ truyền dữ liệu có thể lên đến 54Mbps. 1.1.3. Một số ưu và nhược điểm của WLAN 1.1.3.1. Ưu điểm của WLAN - Sự tiện lợi: Do không cần phải có dây cáp mà chỉ cần một điểm truy cập (Access Point) nên việc tạo ra một mạng không dây là nhanh chóng và dễ dàng đối với người sử dụng. Nó cho phép người dùng có thể dễ dàng truy xuất tài nguyên ở bất cứ nơi đâu có triển khai mạng (tòa nhà hay các văn phòng). Với việc các thiết bị di động nhỏ và dễ dàng di chuyển như PDA, laptop có hỗ trợ Wi-Fi ngày càng được sử dụng nhiều như hiện nay thì đây là một điều vô cùng thuận lợi. - Độ linh động: Tính linh động của mạng không dây được thể hiện rõ nhất ở việc người dùng không còn bị ràng buộc bởi dây cáp. Cùng với sự phát triển của mạng không dây công cộng như hiện nay thì người dùng có thể dễ dàng truy cập mạng ở bất Mạng Adhoc, Khóa luận tốt nghiệp Cử nhân CNTT, Ngô Hải Sơn, 2008 9 kì đâu. Ví dụ điển hình có thể nói tới là các quán cafe wifi, nơi người sử dụng có thể truy cập mạng một cách miễn phí. - Về hiệu quả của công việc: Người dùng có thể dễ dàng duy trì kết nối mạng khi di chuyển từ nơi này đến nơi khác. Đối với việc kinh doanh, điều này vô cùng có lợi. Việc duy trì truyền thông trong khi di chuyển có thể làm tăng thêm hiệu quả công việc của họ. - Thiết kế và triển khai mạng là rất dễ dàng. Không giống như mạng có dây truyền thống, để thiết lập mạng chúng ta cần có những tính toán thiết kế hợp lý, tiến hành nhiều thao tác thì với mạng không dây, chỉ cần các thiết bị tuân theo một chuẩn nhất định và một điểm truy cập, hệ thống mạng đã có thể hoạt động bình thường. Điều này cũng rất có ý nghĩa với những tòa nhà cao tầng hay những công trình cổ, khi mà việc triển khai mạng có dây có thể ảnh hưởng không tốt đến kiến trúc hay kết cấu của chúng. - Một điều thuận lợi nữa của mạng không dây mà chúng ta không thể không nói tới. Đó chính là tính bền vững với sự cố như hỏa hoạn hay thiên tai ... Nếu có thiên tai, hay một sự cố nào đó, việc một mạng có dây bị phá hủy, không thể hoạt động là điều hoàn toàn bình thường, gần như không thể tránh được. Trong những điều kiện như vậy, mạng không dây vẫn có thể hoạt động bình thường hoặc được thiết lập lại một cách nhanh chóng. 1.1.3.2. Nhược điểm của WLAN - Nhược điểm đầu tiên chúng ta có thể nói tới đó chính là vấn đề an toàn và bảo mật dữ liệu trong mạng không dây. Do truyền thông trong mạng không dây là truyền thông trong một môi trường mang tính mở nên việc truy cập tài nguyên mạng trái phép là điều khó tránh khỏi. So với mạng có dây thì tính bảo mật của mạng không dây là không cao bằng. Do đó, vấn đề bảo mật cho mạng không dây là vấn đề vô cùng quan trọng và được quan tâm đặc biệt. Một điểm nữa đó là việc các thiết bị mạng phát sóng radio ra không gian xung quanh có thể ảnh hưởng đến hoạt động của một số thiết bị điện tử khác như các thiết bị trong bệnh viện hay các phòng nghiên cứu. - Thứ hai là chất lượng dịch vụ của mạng không dây. So với mạng có dây thì mạng không dây có tốc độ chậm hơn (chỉ đạt từ 1- 10Mbit/s), độ trễ cao hơn, tỉ lệ lỗi cũng nhiều hơn (tỉ lệ lỗi là 10-4 so với 10-10 của mạng sử dụng cáp quang). Tuy vậy, theo một số chuẩn mới, ở một số môi trường truyền đặc biệt, việc truyền thông trong mạng không dây cũng có thể đạt được tốc độ cao hơn đáng kể, ví dụ như trong chuẩn 802.11n việc truyền thông có thể đạt tốc độ từ 100-200Mbit/s. Mạng Adhoc, Khóa luận tốt nghiệp Cử nhân CNTT, Ngô Hải Sơn, 2008 10 - Thứ ba đó là vấn đề chi phí cho các thiết bị của mạng WLAN. So với giá thành của các thiết bị mạng có dây, thiết bị dành cho mạng không dây là cao hơn khá nhiều. Đây cũng là một trở ngại cho sự phát triển của mạng không dây. - Tiếp đó là vấn đề độc quyền trong các sản phẩm. Nhiều thiết bị và sản phẩm chỉ có thể hoạt động được nếu sử dụng phần cứng hoặc phần mềm của công ty sản xuất nào đó, và phải hoạt động theo quy định của quốc gia mà nó đang được sử dụng. Các tần số phát cũng được các quốc gia quy định nhằm tránh việc xung đột sóng radio của các mạng khác nhau. Do đó, việc sản xuất các sản phẩm cho mạng WLAN cần phải chú ý đến quy định của từng quốc gia. - Cuối cùng là phạm vi phủ sóng của mạng không dây. Các mạng không dây chỉ hoạt động trong phạm vi nhất định. Nếu ra khỏi phạm vi phát sóng của mạng thì chúng ta không thể kết nối mạng. 1.2. Mạng adhoc 1.2.1. Khái niệm và một số đặc điểm chung của mạng adhoc Ngày nay, với sự phát triển nhanh chóng của công nghệ, đời sống con người ngày càng được nâng cao. Việc sở hữu một thiết bị di động như máy tính xách tay, PDA hay các smart phone không còn là quá khó khăn với nhiều người. Điều này đã tạo điều kiện và càng thúc đẩy mạng không dây phát triển. Việc kết nối mạng theo mô hình không dây truyền thống (có sử dụng Access point) đã không còn là xa lạ với chúng ta nữa. Nhưng không phải lúc nào mạng không dây truyền thống cũng có thể phát huy được hiệu quả. Ví dụ như trong vùng mới xảy ra thiên tai hay trong lớp học, người ta cần thiết lập một mạng tạm thời, trong một khoảng thời gian ngắn để có thể trao đổi thông tin với nhau. Lúc này nếu thiết lập một mạng không dây có cơ sở hạ tầng là một điều tốn kém và không hợp lý. Do đó, chúng ta cần thiết lập một mạng không dây không cần có cơ sở hạ tầng nhưng vẫn đảm bảo cho các thiết bị có thể trao đổi thông tin được với nhau. Đây chính là mô hình của mạng adhoc. Chúng ta có thể hiểu mạng adhoc là mạng không cần có cơ sở hạ tầng, nghĩa là không cần một sự quản trị trung tâm nào. Nó là tập hợp của hai hay nhiều thiết bị có hỗ trợ truyền thông và kết nối mạng không dây. Các nút mạng trong mạng có thể trực tiếp nhận và xử lý các gói tin trực tiếp từ nút mạng khác trong mạng – nghĩa là đóng vai trò như các host, đồng thời, chúng cũng có thể làm nhiệm vụ của một router là định tuyến và gửi chuyển tiếp các gói tin đến các nút mạng khác trong mạng. Mạng Adhoc, Khóa luận tốt nghiệp Cử nhân CNTT, Ngô Hải Sơn, 2008 11 Mạng adhoc là một mạng có tính tự thiết lập và thích nghi. Điều đó có nghĩa là các nút mạng có thể di động làm cho topo mạng thay đổi (topo động). Nhưng các nút mạng có thể tự phát hiện ra sự có mặt của các nút mạng khác và thực hiện kết nối cho phép truyền thông tin mà không cần bất kì một sự quản trị trung tâm nào hay một thiết bị điều khiển nào cả. Một điểm cần lưu ý ở đây là các nút mạng không những có thể phát hiện khả năng kết nối của các thiết bị mà nó còn có thể phát hiện ra loại thiết bị và các đặc tính tương ứng của các loại thiết bị đó. Các nút mạng có thể là các thiết bị khác nhau, ví dụ như máy tính xách tay, PDA, hay smart phone, ... nên khả năng tính toán, lưu trữ hay truyền dữ liệu của các nút mạng cũng là khác nhau. Một điều cũng dễ dàng nhận thấy là vấn đề sử dụng và duy trì năng lượng cho các nút mạng của mạng adhoc là vấn đề đáng quan tâm vì các nút mạng thường dùng pin để duy trì sự hoạt động của mình. Ngoài ra, cũng giống như mạng không dây có cơ sở hạ tầng, tính bảo mật trong truyền thông của mạng adhoc là không cao. Truyền th