Đồ án Đánh giá thông lượng của các giao thức định tuyến trong mạng Ad hoc

LỜI NÓI ĐẦU Cùng với sự gia tăng nhanh chóng về số lượng cũng như công nghệ của các thiết bị di động kéo theo nhu cầu của người sử dụng công nghệ không dây ngày càng cao và đa dạng.Vì vậy để đáp ứng được xu thế đó, mạng thông tin không dây ngày nay phải gánh vác trọng trách lớn hơn là giải quyết vấn đề về lưu lượng đa phương tiện, tốc độ cao,chất lượng ngày càng phải tốt hơn. Song song với yêu cầu hỗ trợ đa phương tiện với chất lượng dịch vụ (QoS) đảm bảo, các công nghệ giao tiếp không dây khác nhau đã xuất hiện,Ad hoc là một kiểu mạng thông tin không dây linh hoạt.Đó là tập hợp của hai hay nhiều thiết bị được trang bị khả năng nối mạng và truyền thông không dây.Các thiết bị đó có thể giao tiếp với các nút mạng khác ngay lập tức trong vùng phủ sóng hay một thiết bị không dây khác ngoài bên ngoài với điều kiện có các nút trung gian để chuyển tiếp thông tin từ nút nguồn đến nút đích.Ad hoc có khả năng tự tổ chức và thích nghi, khi đã hình thành có thể bị giải tán bất cứ lúc nào mà không cần đến bất cứ sự quản trị hệ thống nào.Ad hoc có nhiều dạng khác nhau và có thể di chuyển,đứng độc lập hay nối mạng.Các nút mạng có thể phát hiện sự có mặt của các thiết bị khác trong giải vô tuyến và thực hiện sự bắt tay cần thiết để cho phép truyền thông, chia sẻ thông tin và dịch vụ.Tôpô của mạng thông tin tùy biến thay đổi động do các thiết bị không bị ràng buộc vào một vị trí cụ thể nên việc truy nhập phương tiện tập trung. Giao thức định tuyến phải giảm lưu lượng điều khiển, đơn giản tính toán đường định tuyến. Chính vì thế giao thức định tuyến đóng vai trò quan trọng trong vận hành mạng Ad hoc. Đồ án là tổng quan về bốn giao thức định tuyến trong mạng Ad hoc, đánh giá thông lượng của các giao thức đó dựa trên công mô phỏng OMNET++. Do thời gian cũng như trình độ còn hạn chế, đồ án không tránh khỏi những thiếu sót, em rất mong nhận được ý kiến đóng góp. Để có thể hoàn thành được đồ án tốt nghiệp này, em đã được học hỏi những kiến thức quí báu từ các thầy, cô giáo của Trường Đại học Bách Khoa Hà Nội trong suốt năm năm đại học. Em vô cùng biết ơn sự dạy dỗ, chỉ bảo tận tình của các thầy, các cô trong thời gian học tập này. Em xin bày tỏ lòng biết ơn của mình tới thầy Nguyễn Trung Dũng – Bộ môn Hệ thống viễn thông – Khoa Điện tử viễn thông – Trường Đại học Bách Khoa Hà Nội, người đã định hướng cho những nghiên cứu của em, người trực tiếp hướng dẫn và chỉ bảo em hoàn thành đồ án này. Cuối cùng, em xin cảm ơn gia đình, bạn bè đã luôn tạo điều kiện thuận lợi, động viên và giúp đỡ em trong suốt thời gian học tập và nghiên cứu đồ án. Ngoài ra, kiến thức thu được từ các thầy cô cũng là nguồn cổ vũ tinh thần lớn nhất giúp em có thể tập trung và hoàn thành tốt đề tài tốt nghiệp này. Hà Nội, tháng 5- 2009 Sinh viên Vũ Huy Cường TÓM TẮT ĐỒ ÁN Mạng Ad hoc là một công nghệ hữu dụng trong mạng không dây. Công nghệ này cho phép các nút mạng giao tiếp trực tiếp với nhau bằng cách sử dụng máy thu phát vô tuyến mà không cần có cơ sở hạ tầng cố định. Đây là một đặc trưng riêng của mạng Ad hoc so với các mạng truyền thống trước đây như mạng cellular hay mạng LAN không dây khi ở đó các nút giao tiếp với nhau thông qua trạm gốc (Base Station). Tuy nhiên, mang Ad hoc phải đối mặt với một số thách thức như giới hạn phạm vi truyền dẫn, vấn đề trạm ẩn, mất gói do lỗi đường truyền, sự chuyển động của các nút mạng làm thay đổi tuyến đường, sự rằng buộc về băng thông và năng lượng. Giao thức định tuyến được sử dụng để Khám phá tuyến giữa các nút giúp cho việc giao tiếp trong mạng dễ dàng hơn. Mục đích chính của một giao thức định tuyến trong mạng Ad hoc là thiết lập tuyến đường chính xác và hiệu quả giữa các cặp nút. Đồ án đưa ra tổng quan về bốn giao thức định tuyến: DYMO, DSR, AODV, OLSR, sử dụng công cụ mô phỏng OMNET++ và đánh giá trễ đầu cuối của các giao thức này dựa trên các thông số đặt ra. Đồ án gồm 5 chương Chương 1: Tổng quan về mạng Ad hoc Chương 2: Định tuyến trong mạng Ad hoc Chương 3: Thông số đánh giá và mô hình chuyển động trong mô phỏng mạng Ad hoc Chương 4: Mô phỏng và đánh giá thông lượng của OLSR, AODV, DSR và DYMO bằng OMNET++ Chương 5: Kết luận ABSTRACT Ad hoc networks are the ultimate frontier in wireless communication. This technology allows network nodes to communicate directly to each other using wireless transceivers without the need for a fixed infrastructure. This is a very distinguishing feature of ad hoc networks with respect to more traditional wireless networks, such as cellular networks and wireless LAN, in which nodes communicate with each other through BS. Some challenges that ad hoc networking faces are limited wireless transmission range, hidden terminal problems, packet losses due to transmission errors, mobility- induced route changes, bandwidth and battery constraints. In order to facilitate communication within the network, a routing protocol is used to discover routes between nodes. The primary goal of such an Ad hoc network routing protocol is correct and efficient route establishment between a pair of nodes so that message may be delivered in a timely manner. This thesis provides an overview of four different routing protocols: DYMO, DSR, AODV, OLSR, uses OMNET++ simulator and evaluates throughput of these protocols based on a given set of parameters. The thesis has a total of 5 chapters: Chapter 1: Overview of Ad hoc network Chapter 2: Routing in Ad hoc network Chapter 3: Protocol Evaluation parameters and Mobility models for Ad hoc network simulation Chapter 4: Simulating and evaluating throughput of AODV, OLSR, DSR and DYMO in OMNET++ Chapter 5: Summary MỤC LỤC DANH SÁCH HÌNH VẼ Hình 1.1 Mô hình mô tả khái niệm mạng Ad hoc 11 Hình 1.2 Ứng dụng cho các dịch vụ khẩn cấp khi có thiên tai 13 Hình 1.3 Ứng dụng trong các hội nghị 14 Hình 1.4 Ứng dụng cho home networking 14 Hình 1.5 Ứng dụng cho mạng cá nhân 15 Hình 1.6 Ứng dụng cho mạng xe cộ 16 Hình 2.1 Hệ tọa độ cơ bản mô tả môi trường mạng Ad Hoc 22 Hình 2.2 Phân loại các giao thức định tuyến trong mạng Ad hoc 25 Hình 2.3 Quá trình phát tràn lan bản tin quảng bá 29 Hình 2.4 Bầu chọn MPR 30 Hình 2.5 Khám phá tuyến trong DSR 33 Hình 2.6 Duy trì tuyến, nút C không thể chuyển tiếp từ A đến E qua 36 liên kết tới bước nhảy tiếp theo D của nó 36 Hình 2.7 Thiết lập tuyến đường đi ngược 40 Hình 2. 8 Thiết lập tuyến đường thuận 41 Hình 2.9: Sự khác nhau giữa AODV và DYMO 43 Hình 3.1 Mô hình di chuyển Random Waypoint 51 Hình 3.2 Mô hình di chuyển hướng ngẫu nhiên 52 Hình 4.1 Các module đơn giản và kết hợp 55 Hình 4.2 Các kết nối 56 Hình 4.3 Lược đồ xây dựng và chạy một chương trình mô phỏng OMNeT++ 61 Hình 4.4 Quá trình gửi bản tin RREQ của DYMO 64 Hình 4.5 Quá trình gửi bản tin RREP của DYMO 65 Hình 4.6 Quá trình gửi gói tin dữ liệu của DYMO 66 Hình 4.7 Quá trình gửi ACK báo nhận của DYMO 67 Hình 4.9 Thông lượng đầu cuối - đầu cuối 69 DANH SÁCH BẢNG BIỂU Bảng 3.1 Bảng các biến trong thông số di chuyển 47 Bảng 4.1 Bảng thông số đánh giá dùng trong mô phỏng 67 CHƯƠNG 1. TỔNG QUAN VỀ AD HOC NETWORK Chương này trình bày các khái niệm tổng quan nhất về mạng Ad hoc, các ứng dụng trong nhiều lĩnh vực cuộc sống của mạng Ad hoc. Đồng thời, đề cập đến các thách thức mà mạng Ad hoc đang phải đối mặt. MỞ ĐẦU Mạng máy tính từ lâu đã trở thành một phần không thể thiếu đối với nhiều lĩnh vực đời sống xã hội, từ các hệ thống mạng cục bộ đến hệ thống mạng toàn cầu như Internet. Mạng máy tính đưa mọi người trên thế giới đến gần nhau hơn, mỗi người được tiếp cận với một nguồn thông tin, tri thức phong phú. Xã hội phát triển, con người vận động không ngừng, một người kết nối vào mạng bằng cáp vật lý thì việc di chuyển của họ bị hạn chế, nhu cầu đặt ra là vừa kết nối vừa có thể di chuyển và có thể kết nối bất cứ đâu một cách đơn giản. Chính nhu cầu này đã kích thích ngành công nghiệp mạng không dây tiềm năng phát triển mạnh mẽ. Mạng Ad hoc là một kiểu mạng không dây rất linh hoạt. Đó là tập hợp của hai hay nhiều thiết bị được trang bị khả năng nối mạng và truyền thông không dây. Các thiết bị như vậy có thể giao tiếp với tất cả thiết bị mạng khác ngay lập tức trong dải vô tuyến (vùng phủ sóng, phạm vi mà thiết bị mạng đó nhận biết được) hay một thiết bị vô tuyến khác nằm ngoài dải vô tuyến của chúng với điều kiện có các node trung gian để chuyển tiếp thông tin từ node nguồn đến node đích. Thiết bị hỗ trợ mạng Ad hoc đa dạng và sử dụng khá phổ biến như laptop, điện thoại di động Internet. Vì có nhiều ưu thế vượt trội và những thách thức cần giải quyết, ngày nay mạng Ad hoc đã và đang được nghiên cứu triển khai thành công ở một số nước mà phổ biến là Mỹ. Mạng Ad hoc đặc biệt hữu ích trong các ứng dụng như khắc phục thảm họa thiên nhiên, quốc phòng, y tế, hội nghị nên có xu hướng ứng dụng rộng rãi trên thế giới. KHÁI NIỆM Mạng Ad hoc là tổ hợp của các node di động được kết nối với nhau bằng các liên kết không dây, các node tự do di chuyển nên kiến trúc mạng có thể thay đổi liên tục mà không dự đoán được. Mỗi node mạng có một giao diện vô tuyến giao tiếp với các node mạng khác thông qua sóng vô tuyến hoặc hồng ngoại. Các mạng này không dùng bất cứ sự hỗ trợ cơ sở hạ tầng mạng cố định hay chịu sự quản lí tập trung nào. Đây là một đặc điểm riêng biệt của mạng Ad hoc so với các mạng không dây truyền thống – mạng chia ô, mạng WLAN, trong đó các node (các thuê bao di động ) liên lạc với nhau thông qua trạm vô tuyến cơ sở. Hình 1.1 Mô hình mô tả khái niệm mạng Ad hoc Trong Ad hoc không tồn tại khái niệm quản lý tập trung, nó đảm bảo mạng sẽ không bị sập vì trường hợp nút mạng di chuyển ra ngoài khoảng truyền dẫn của các nút mạng khác. Nút mạng có thể ra vào bất cứ lúc nào. Do khoảng truyền dẫn của nút mạng là hạn chế nên chúng trao đổi thông tin bằng phương pháp truyền gói tin qua nhiều bước (Multihops). Để làm được điều này, thì tất cả các nút mạng phải có khả năng chuyển tiếp gói tin đến nút mạng khác, do vậy tất cả các nút mạng trong Ad hoc có thể hoạt động như máy trạm và router. Nên nút mạng có thể bao gồm một router và một máy trạm liên kết với nhau. Một router thực hiện các giao thức định tuyến, máy trạm di động có địa chỉ IP. Ad hoc cũng có khả năng thực hiện thay đổi về cấu hình mạng và khắc phục sự cố của nút mạng thông qua thủ tục cấu hình lại mạng. Ví dụ: Nếu nút mạng rời khỏi mạng sẽ gây ra sự cố liên kết, nút mạng bị ảnh hưởng có thể yêu cầu đường định tuyến mới và vấn đề sẽ được giải quyết. Điều này sẽ gây ra trễ trên mạng, tuy nhiên với người sử dụng Ad hoc vẫn hoạt động bình thường. Ad hoc có nhiều ưu điểm của mạng truyền thông vô tuyến thông thường, liên kết giữa các nút mạng được hình thành ngay khi chúng nằm trong khoảng truyền dẫn của nhau ĐẶC ĐIỂM Ad hoc thường được mô tả có cấu trúc mạng thay đổi do sự thay đổi vị trí của các nút mạng. Các giao thức định tuyến có cơ chế tự phát hiện các thay đổi về định tuyến thông qua các thuật toán định tuyến thông thường như vector khoảng cách và trạng thái các liên kết. Một đăc điểm khác của các nút mạng trong mạng Ad hoc: bị giới hạn về khả năng của CPU, bộ nhớ, dung lượng pin và băng thông. Khi năng lượng sử dụng bị giới hạn kéo theo giới hạn về khả năng truyền dẫn. Thiết bị truy nhập, môi trường vô tuyến cũng có các đặc điểm đặc biệt mà người thiết kế cần lưu tâm khi đưa ra các giao thức định tuyến cho Ad hoc. Ví dụ: các liên kết một chiều, nó xuất hiện trong trường hợp 2 nút mạng có công suất phát khác nhau nên có khoảng truyền dẫn khác nhau, chỉ cho phép một nút mạng nghe nút mạng kia. Liên kết một chiều chỉ có trong Ad hoc, không tồn tại trong mạng tế bào. Sử dụng phương pháp định tuyến nhiều bước thì các nút mạng có thể tiết kiệm được năng lượng phát ra. ỨNG DỤNG Ad hoc được ứng dụng cho hội thảo, ứng dụng trong quân sự. Nó cũng được sử dụng cho trường hợp triển khai cơ sở hạ tầng mạng là khó khăn. Ví dụ: khách hàng có thể chia sẻ tệp tin dữ liệu ở sân bay, sinh viên trao đổi thông tin với nhau trong tiết học… Khi máy tính di động giao tiếp thông qua giao diện mạng LAN vô tuyến, thì nhóm các máy tính đó hình thành mạng Ad hoc, khi đó máy tính có thể truy nhập Internet, tài nguyên trên mạng như máy in, máy scan... Dịch vụ khẩn cấp Bất kỳ đâu khi có trường hợp khẩn cẩp xảy ra đều cần có sự kết hợp của các nhân viên cứu hộ. Giải pháp thông thường là dùng thiết bị vô tuyến. Tuy nhiên, khi cơ sở hạ tầng bị hỏng hoặc không còn hoạt động thì giải pháp là gì? Ad hoc chính là câu trả lời nhanh nhất và phù hợp nhất. Điều này có thể không có ý nghĩa với khu vực tổn thất nhỏ, tuy nhiên với thảm họa thiên nhiên có khu vực ảnh hưởng tàn phá rộng lớn, việc liên lạc rất quan trọng nên Ad hoc trở thành giải pháp hữu ích. Hình 1.2 Ứng dụng cho các dịch vụ khẩn cấp khi có thiên tai Hội nghị Trong hội nghị, hội thảo cần trao đổi thông tin giữa các đại biểu hoặc với hội nghị khác. Đây là một nhu cầu lớn trong thời đại phát triển nhanh về thông tin như hiện nay, khi mà giải pháp homenetwork chưa thật sự sẵn sàng. Giải pháp hiện tại là sử dụng các mạng có sẵn cho các đại biểu tham dự tuy nhiên nó có độ trễ lớn, ví dụ giải pháp Mobile IP .Và Ad hoc là giải pháp chiếm ưu thế. Hình 1.3 Ứng dụng trong các hội nghị Home Networking Rõ ràng sự hiện diện của máy tính xách tay và ứng dụng không dây làm nhu cầu về home network tăng cao.Việc sử dụng kỹ thuật của Ad hoc cho phép chúng tự cấu hình và hình thành mạng, điều này tiện lợi cho cả người không thật sự am hiểu về mạng cũng như giảm được chi phí cho xây dựng thiết kế mạng. Hơn nữa, nếu ta có nhu cầu sử dụng máy tính ở công sở, trường học thì khối lượng thông tin quản lý mạng giảm xuống rõ rệt. Hình 1.4 Ứng dụng cho home networking Mạng cá nhân (PAN) Ở thời đại thông tin thì 1 người cần mang theo nhiều công cụ hỗ trợ cho công việc (điện thoại,Palm...) khi chúng được liên kết với nhau hình thành mạng cá nhân PAN thì rõ ràng mang lại nhiều tiện ích hơn cho người sử dụng. PAN là mạng di động do con người không thể ngồi yên một chỗ, tuy nhiên khi kết nối với mạng PAN khác cần trợ giúp của Ad hoc. Hình 1.5 Ứng dụng cho mạng cá nhân Hệ thống nhúng (embeded system) Ngày càng có nhiều máy móc cần kết nối với những vật xung quanh kéo theo nhu cầu của Ad hoc. Nó có thể là đồ chơi có khả năng kết nối mạng, tương tác được với home network để tìm kiếm dữ liệu trên internet hoặc có thể kết nối với điện thoại, có thể điều chỉnh volume của TV khi có cuộc gọi đến....đáp ứng nhiều nhu cầu của người sử dụng. Mạng xe cộ (vehicular network) VANET (Vehicular Ad Hoc Network) gọi là mạng xe cộ Ad hoc, là hệ thống mạng không cần cơ sở hạ tầng, được tạo thành từ các phương tiện xe cộ lưu thông trên đường. Chúng được trang bị thiết bị thu phát để có thể liên lạc, chia sẻ và trao đổi thông tin với nhau giống như một nút trong mạng Ad hoc. Thông tin trao đổi trong mạng VANET bao gồm thông tin về lưu lượng xe cộ, tình trạng kẹt xe, tai nạn giao thông, nguy hiểm cần tránh và cả những dịch vụ thông thường như dịch vụ đa phương tiện, Internet.... Hình 1.6 Ứng dụng cho mạng xe cộ Mạng cảm biến (sensor network) Mạng cảm biến không dây là một ứng dụng điển hình của Ad hoc. Hiện nay đã có những quan tâm đáng kể cho sự phát triển kiểu mạng này,chủ yếu là trong quân sự, công an, tình báo, khảo cổ học, nghiên cứu địa lý....Các bộ cảm biến có thể có kích thước nhỏ nhưng khả năng truyền thông và lưu trữ tương đối tốt. Trong quân sự đã dùng những máy móc hiện đại nhưng kích cỡ gần như hạt bụi nên đối phương rất khó phát hiện và phá hủy chúng. Trong lĩnh vực y tế, các bộ cảm biến cho phép giám sát liên tục thông tin tiêu chuẩn về sự sống. Trong công nghệ thực phẩm, kỹ thuật nhịp cảm biến được áp dụng để giám sát chất lượng có thể giúp ngăn ngừa các sản phẩm không đạt yêu cầu nên tăng mức thỏa mãn cho khách hàng. Trong nông nghiệp, các bộ cảm biến có thể giúp xác định chất lượng đất trồng và độ ẩm, chúng cũng có thể phát hiện các hợp chất khác. Ngoài ra, các bộ cảm biến cũng được sử dụng rộng rãi trong thông tin thời tiết và môi trường. NHỮNG THÁCH THỨC ĐỐI VỚI MẠNG AD HOC Chi phí cho việc sử dụng tần số Hầu hết các mạng Ad hoc thử nghiệm hiện nay đều dựa trên băng tần ISM. Để ngăn ngừa nhiễu, mạng Ad ho phải hoạt động qua một số dải phổ cụ thể nào đó, được cấp phát. Phổ tần không chỉ được cấp phát và giám sát chặt chẽ mà còn cần phải được trả phí. Cơ chế truy nhập Không giống như mạng tế bào, trong mạng Ad hoc không có sự điều khiển tập trung và đồng bộ toàn cục. Do đó các phương pháp đa truy nhập truyền thông như TDMA và FDMA không còn thích hợp nữa. Ngoài ra, nhiều giao thức điều khiển truy nhập phương tiện MAC (Media Access Control) cũng không giải quyết được sự di động của nút mạng. Do vậy, các kỹ thuật lập lịch trình và định thời để hỗ trợ QoS gặp nhiều khó khăn. Trong mạng Ad hoc, do cùng một phương tiện truyền thông được chia sẻ bởi nhiều bên tham gia nên thủ tục truy nhập đến kênh chung phải được thực hiện theo kiểu phân bố nhờ sự hỗ trợ của giao thức MAC. Giao thức MAC phải tính đến truy nhập kênh trong khi đồng thời phải tránh được sự xung đột với các nút lân cận. Do vậy, khi tính toán thiết kế các giao thức MAC cho mạng Ad hoc phải tính đến khả năng di chuyển, vấn đề đầu cuối ẩn và các vấn đề liên quan khác. Định tuyến và chuyển tiếp gói tin trong MANET Đặc tính động của mạng Ad hoc gây ra sự thay đổi thường xuyên và khó đoán trước của topo mạng, làm tăng độ khó và độ phức tạp để định tuyến giữa các nút di động. Nhiều giao thức và thuật toán định tuyến đã được đề xuất cho mạng Ad hoc, tuy nhiên mỗi giao thức lại có một hạn chế riêng. Do vậy, nghiên cứu về các giao thức định tuyến trong Ad hoc là một vấn đề rất quan trọng. Hiệu quả sử dụng nguồn nuôi Hầu hết các giao thức trong mạng hiện nay không quan tâm đến tiêu tốn năng lượng nguồn nuôi vì các máy chủ và các bộ tính tuyến thường được giả định là tĩnh và được cấp nguồn từ nguồn điện chính. Tuy nhiên, các thiết bị dị động hầu hết được cấp nguồn từ nguồn nuôi độc lập.Kỹ thuật nguồn nuôi vẫn thường đi chậm hơn so với kỹ thuật vi xử lý. Thời gian cấp nguồn của pin loại tốt như Li-ionh hiện nay cũng chỉ tối đa từ 2 đến 3 giờ (hiện nay đã có một số laptop có thời gian sử dụng lên đến 8h, tuy nhiên giá thành vẫn còn khá cao). Sự giới hạn thời gian hoạt động như thế nói lên tính cần thiết phải bảo tồn tốt nguồn nuôi. Đặc biệt, đối với mạng Ad hoc, do các thiết bị di động phải thực hiện vai trò của cả hệ thống đầu cuối (tương tác người dùng khi thực hiện các ứng dụng người dùng) lẫn vai trò của một hệ thống trung gian (chuyển tiếp gói tin) nên sẽ tiêu tốn năng lượng nguồn nuôi một cách đáng kể, đặc biệt là các nút trung gian. Đặc tính TCP TCP (Transmission Control Protocol) là một giao thức cuối-cuối được thiết kế phục vụ việc điều khiển nghẽn và điều khiển luồng trong mạng. TCP là một giao thức hướng liên kết nên cần có một giai đoạn thiết lập kết nối ưu tiên cho việc truyền dữ liệu. Kết nối bị loại bỏ khi việc truyền dữ liệu hoàn thành. Với internet hiện nay, giao thức mạng IP là phi kết nối nên cần có một giao thức truyền dẫn hướng kết nối đáng tin cậy qua