Tài liệu Định tuyến trong mạng AD HOC (LV thạc sĩ)

HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG --------------------------------------- NGUYỄN MINH THÀNH ĐỊNH TUYẾN TRONG MẠNG AD HOC LUẬN VĂN THẠC SĨ KỸ THUẬT (Theo định hướng ứng dụng) HÀ NỘI – 2017 HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG --------------------------------------- NGUYỄN MINH THÀNH ĐỊNH TUYẾN TRONG MẠNG AD HOC Chuyên ngành: Kỹ thuật viễn thông Mã số: 60.52.02.08 LUẬN VĂN THẠC SĨ KỸ THUẬT (Theo định hướng ứng dụng) NGƯỜI HƯỚNG DẪN KHOA HỌC: TS. LÊ NGỌC THÚY HÀ NỘI – 2017 LỜI CAM ĐOAN Tôi xin cam đoan đây là công trình nghiên cứu của riêng tôi. Các số liệu, kết quả nêu trong luận văn là trung thực và chưa từng được ai công bố trong bất kỳ công trình nào khác. Các kế thừa của các tác giả khác đã được trích dẫn. Tác giả Nguyễn Minh Thành i LỜI CẢM ƠN Để có thể hoàn thành đề tài luận văn thạc sĩ một cách hoàn chỉnh, bên cạnh sự nỗ lực cố gắng của bản thân còn có sự hướng dẫn nhiệt tình của các Thầy, Cô, sự giúp đỡ của bạn bè trong suốt thời gian học tập nghiên cứu và thực hiện luận văn thạc sĩ. Đặc biệt, em xin bày tỏ sự biết ơn sâu sắc đến TS. LÊ NGỌC THÚY, Cô đã trực tiếp hướng dẫn, chỉ bảo tận tình, chu đáo và có những nhận xét, góp ý quý báu giúp em trong suốt quá trình thực hiện cho đến khi luận văn được hoàn thành. Em xin gửi làm cảm ơn đến tất cả Thầy, Cô giáo Học viện Công nghệ Bưu chính Viễn thông đã tận tình chỉ bảo và tạo mọi điều kiện thuận lợi để em được nghiên cứu và học tập trong thời gian qua. Hà Nội, ngày tháng năm 2017 Học viên Nguyễn Minh Thành ii MỤC LỤC CHƯƠNG I: TỔNG QUAN VỀ MẠNG VÔ TUYẾN AD HOC .......................... 1 1.1 Sự ra đời và phát triển của các mạng không dây .................................................. 1 1.2 Một số mạng Ad hoc điển hình ............................................................................. 5 1.3 Các ứng dụng của mạng Ad hoc ........................................................................... 6 1.4 Kết luận chương .................................................................................................... 7 CHƯƠNG II: ĐỊNH TUYẾN TRONG MẠNG VÔ TUYẾN AD HOC ............. 8 2.1 Giới thiệu về định tuyến trong mạng Ad hoc ........................................................ 8 2.2 Các yêu cầu đối với thuật toán định tuyến cho mạng Ad hoc không dây .......... 10 2.3 Phân loại các thuật toán định tuyến trong mạng Ad hoc .................................... 12 2.3.1 Giao thức định tuyến theo bảng ghi (Table-Driven Routing Protocol): .......... 13 2.3.2 Giao thức định tuyến điều khiển theo yêu cầu (On-Demand Routing Protocol): ................................................................................................................... 14 2.3.3 Giao thức định tuyến kết hợp (Hybrid Routing Protocol): .............................. 14 2.4 Một số các giao thức định tuyến trong mạng Ad hoc......................................... 15 2.4.1 Định tuyến theo vectơ khoảng cách tuần tự đích (DSDV - Destination Sequenced Distance Vector) ..................................................................................... 15 2.4.2 Định tuyến theo trạng thái đường liên kết tối ưu (OLSR - Optimized Link State Routing)[4] ................................................................................................................ 16 2.4.3 Ad hoc On-Demand Distance Vector (AODV)[5] .......................................... 19 2.4.4 Định tuyến nguồn động (DSR - Dynamic Source Routing)[3] ........................ 22 2.4.5 TORA[12] ........................................................................................................ 24 2.5 Kết luận chương .................................................................................................. 25 CHƯƠNG III: ĐÁNH GIÁ HIỆU NĂNG CỦA CÁC GIAO THỨC ĐỊNH TUYẾN TRONG MẠNG AD HOC BẰNG BỘ MÔ PHỎNG NS2 ................... 26 3.1 Giới thiệu về bộ mô phỏng NS2 ......................................................................... 26 3.1.1 Mô phỏng mạng không dây trong môi trường NS ........................................... 29 3.1.2 Các mô hình truyền sóng vô tuyến trong NS ................................................... 31 3.1.3 Thực hiện mô phỏng [13] ................................................................................. 45 iii 3.2 Phân tích kết quả mô phỏng ................................................................................ 47 3.2.1 Thông lượng các gói tin được tạo ra của toàn mạng trong thời gian thực hiện mô phỏng ................................................................................................................... 48 3.2.2 Thông lượng các gói tin bị rơi của toàn mạng trong thời gian thực hiện mô phỏng 50 3.2.3 Thông lượng các gói tin chuyển tiếp của tất cả các nút trong thời gian thực hiện mô phỏng ................................................................................................................... 52 3.2.4 Thảo luận chương............................................................................................. 53 3.3 Kết luận chương .................................................................................................. 58 KẾT LUẬN .............................................................................................................. 59 HƯỚNG NGHIÊN CỨU TIẾP THEO ................................................................. 59 TÀI LIỆU THAM KHẢO ...................................................................................... 60 PHỤ LỤC ................................................................................................................. 61 iv v BẢNG KÝ HIỆU CÁC TỪ VIẾT TẮT ACK AODV AP BSS CTS DCF DSDV DSR ESS IEEE IERP LAN MAC MPR MPRs NAM NS2 OLSR PHY QoS RREP RREQ RRER RTS UWB VINT WiMAX WLAN WPAN WUSB WWAN Acknowledgement Ad hoc On-Demand Distance Vector Routing Access Point Basic Service Set Clear to Send Distributed Coordination Function Destination Sequenced Distance Vector Dynamic Source Routing Extended Service sets Institute of Electrical and Electronics Engineers Interzone Routing Protocol Local Area Network Medium Access Control Multipoint Relays Multipoint Relays Selector Network Animator Network Simulation Version 2.0 Optimized Link State Routing Physical Quality of Service Route Reply Route Request Route Error Request To Send Ultra-WideBand Virtual InterNetwork Testbed Worldwide Interoperability for Microwave Access Wireless Local Area Network Wireless Persional Area Network Wireless Universal Serial Bus Wireless Wide Area Network vi DANH MỤC HÌNH VẼ Hình 1.1: Sự phát triển của mạng không dây và di động ............................................ 1 Hình 1.2: Mô hình mạng không dây Ad hoc............................................................... 5 Hình 1.3: Mạng Ad hoc điển hình ............................................................................... 5 Hình 2.1: Ví dụ về việc phân chia vùng trong mạng Ad hoc.................................... 12 Hình 2.2: Phân loại các giao thức định tuyến trong mạng Ad hoc ........................... 13 Hình 2.3: Khi Tôpô mạng thay đổi ........................................................................... 16 Hình 2.4: Bộ chuyển tiếp đa điểm (Multipoint relays) ............................................. 17 Hình 2.5: AODV khám phá và duy trì tuyến ............................................................ 21 Hình 2.6: DSR quá trình khám phá tuyến ................................................................. 24 Hình 3.1: Tổng quan về NS2 dưới góc độ người dùng ............................................. 28 Hình 3.2: Luồng các sự kiện cho file Tcl chạy trong NS.......................................... 29 Hình 3.3: Kiến trúc tầng của NS2 ............................................................................. 30 Hình 3.4: Nút unicast và nút multicast ...................................................................... 39 Hình 3.5: Chèn đối tượng trace ................................................................................. 43 Hình 3.6: Đồ hình mô phỏng 25 nút mạng Ad hoc ................................................... 45 Hình 3.7: Thông tin mô phỏng của giao thức AODV ............................................... 46 Hình 3.8: Thông tin mô phỏng của giao thức DSDV ............................................... 46 Hình 3.9: Thông tin mô phỏng của giao thức DSR .................................................. 47 Hình 3.11: Thông lượng các gói tin được tạo ra của toàn mạng - AODV ................ 48 Hình 3.12 Thông lượng các gói tin được tạo ra của toàn mạng - DSDV ................. 48 Hình 3.13: Thông lượng các gói tin được tạo ra của toàn mạng - DSR ................... 49 Hình 3.13: Thông lượng các gói tin bị rơi của toàn mạng – AODV ........................ 50 Hình 3.14: Thông lượng các gói tin bị rơi của toàn mạng – DSDV ......................... 50 Hình 3.15: Thông lượng các gói tin bị rơi của toàn mạng – DSR ............................ 51 Hình 3.16: Thông lượng các gói tin chuyển tiếp của tất cả các nút – AODV .......... 52 Hình 3.17: Thông lượng các gói tin chuyển tiếp của tất cả các nút – DSDV ........... 53 Hình 3.18: Thông lượng các gói tin chuyển tiếp của tất cả các nút – DSR .............. 53 vii Hình 3.19: Tỷ lệ gói tin truyền thành công của 3 giao thức tại các môi trường mô phỏng 25 nút mạng, 30 nút mạng, 35 nút mạng, 50 nút mạng.................................. 57 Hình 3.20: Lưu lượng gói tin mỗi giao thức tại các môi trường mô phỏng 25 nút mạng, 30 nút mạng, 35 nút mạng, 50 nút mạng ........................................................ 57 viii CHƯƠNG I: TỔNG QUAN VỀ MẠNG VÔ TUYẾN AD HOC Chương này trình bày khái quát về mạng Ad hoc, nêu nội dung, ưu điểm, nhược điểm của mạng Ad hoc, chú trọng việc không phụ thuộc vào cơ sở hạ tầng mạng và đưa ra mô hình mạng Ad hoc. Nêu vấn đề định tuyến trong mạng Ad hoc là rất quan trọng, ảnh hưởng đến hiệu năng của toàn hệ thống mạng. 1.1 Sự ra đời và phát triển của các mạng không dây Mạng không dây được đánh dấu mốc hình thành từ những năm 1887 khi Heinrich Rudolf Hertz chứng minh được thuyết điện từ Maxwell thông qua thực nghiệm. Từ đó đến nay các nhà nghiên cứu đã cho ra đời hàng loạt phát minh sáng chế góp phần đưa công nghệ mạng không dây không ngừng cải tiến vượt trội về tốc độ truyền nhận dữ liệu. Những năm gần đây nền công nghiệp không dây và di động tăng trưởng mạnh mẽ cả về mặt công nghệ lẫn sự bùng nổ ngày càng nhiều các thiết bị di động, hứa hẹn một kỷ nguyên truyền thông số nở rộ trên nền các mạng không dây và di động. Sự phát triển này được minh họa trên hình 1 dưới đây.[8] UMTS, WLAN, DAB, DVB, GSM, cdma2000, TETRA, ... Personal Travel Assistant, PDA, Laptop, GSM, UMTS, WLAN, Bluetooth, ... Hình 1.1: Sự phát triển của mạng không dây và di động Các mốc hình thành và phát triển của mạng không dây: 1 1887 Heinrich Rudolf Hertz đã tạo ra được sóng điện từ. Ông đã chứng minh được thuyết Maxwell thông qua thực nghiệm. 1893 Nikola Tesla truyền thành công sóng radio. 1915 Truyền thành công sóng vô tuyến vượt Đại Tây Dương từ Arlington Virginia tới Pháp. Tháp Eiffel đã được sử dụng để đặt anten thu tín hiệu. 1931 Sóng FM đã được phát triển bởi Edwin H. Armstrong và được sử dụng rộng rãi để truyền thông tin qua sóng vô tuyến. 1895 Guglielmo Marconi: Lần đầu tiên trong lịch sử, 3 dấu chấm (tức chữ S trong bảng ký tự Morse) đã được truyền qua không gian với khoảng cách 3km bằng sóng điện từ. 1982 , 1991 -1982: Hội nghị CEPT đã thống nhất chọn GSM để phát triển thành tiêu chuẩn cho hệ thống điện thoại di động có thể được sử dụng trên khắp châu Âu. - 1991: Các mạng GSM đầu tiên đã được đưa ra bởi Radiolinja ở Phần Lan với kỹ thuật bảo dưỡng cơ sở hạ tầng chung từ Ericsson. 2 1997 1998, 1999 2001 Chuẩn IEEE 802.11 (WiFi) đã được tạo ra, với tốc độ tối đa là 2Mb/s. -1998: Công nghệ Bluetooth đầu tiên được phát triển bởi Ericsson, sau đó được chuẩn hoá bởi Bluetooth Special Interest Group (SIG). Chuẩn IEEE 802.16 được phát hành. Chuẩn này được biết đến dưới cái tên WIMAX. - 1999: Chuẩn 802.11b được phát hành cho tốc độ tối đa lên 11Mb/s. -20/5/1999: Chính thức phát hành chuẩn Bluetooth 1.0 2003 - Chuẩn 802.11g được phát hành với tốc độ tối đa lên tới 54 Mb/s. - Bluetooth 1.2 được công bố. 2004, 2009 *2004: - Phiên bản mới của chuẩn 802.16 được bổ sung, hoàn thiện chuẩn WIMAX. - Phát hành Bluetooth 2.0 chuẩn *2009: - Chuẩn 802.11n được phát hành cho phép tốc độ truyên thông tối đa lên tới 150 Mb/s. 3 2010 Liên minh Wi-Fi và Gigabit không dây đã đạt được thỏa thuận cho phép Wi-Fi hoạt động ở dải tần 60 Ghz nhằm cải thiện tốc độ truyền dữ liệu. Các chuẩn Wi-Fi hiện đang hoạt động ở dải tần từ 2.4 GHz đến 5 GHz.  Tốc độ Wi-Fi sẽ tăng hơn 10 lần so với tốc độ hiện tại Khái niệm và đặc điểm chung của mạng Ad hoc[9] Mạng Ad Hoc là mạng bao gồm các thiết bị di động (máy tính có hỗ trợ card mạng không dây) các thiết bị PDA hay các điện thoại thông minh(smart phone) tập trung lại trong một không gian nhỏ để hình thành lên kết nối ngang hàng (peer-to-peer) giữa chúng. Các thiết bị này có thể trao đổi thông tin trực tiếp với nhau, không cần phải thông qua máy chủ (server) quản trị mạng. Mạng Ad Hoc là mạng mà các nút trong mạng có thể tự thiết lập, tự tổ chức và tự thích nghi khi có một nút mới gia nhập mạng, các nút trong mạng cần có cơ chế phát hiện nút mới gia nhập mạng, thông tin về nút mới sẽ được cập nhật vào bảng định tuyến của các nút hàng xóm và gửi đi. Khi có một nút ra khỏi mạng, thông tin về nút đó sẽ được xóa khỏi bảng định tuyến và hiệu chỉnh lại tuyến, ...Mạng Ad Hoc có nhiều loại thiết bị khác nhau tham gia mạng lên các nút mạng không những phát hiện được khả năng kết nối của các thiết bị, mà còn phải phát hiện ra được loại thiết bị và các đặc tính tương ứng của các loại thiết bị đó (vì các thiết bị khác nhau sẽ có các đặc tính khác nhau ví dụ như: khả năng tính toán, lưu trữ hay truyền dữ liệu trong mạng,...) Mạng Ad hoc được coi như mạng ngang hàng không dây, trong mạng không có máy chủ. Các thiết bị vừa là máy khách, vừa làm nhiệm vụ của router và vừa làm máy chủ. Vấn đề sử dụng và duy trì năng lượng cho các nút mạng của mạng Ad hoc là vấn đề đáng quan tâm vì các nút mạng trong mạng Ad hoc thường dùng pin để duy trì sự hoạt động của mình. Tính bảo mật trong truyền thông của mạng Ad hoc là không cao do truyền thông trong không gian sử dụng sóng vô tuyến(radio) lên khó kiểm soát và dễ bị tấn công hơn so với mạng có dây rất nhiều. Việc thiết lập các mạng Ad hoc có thể thực hiện nhanh chóng và dễ dàng nên chúng thường được thiết lập để truyền thông tin với nhau mà không cần phải sử dụng một thiết bị hay kỹ năng đặc biệt nào. Vì vậy mạng Ad hoc rất thích hợp cho việc truyền thông tin giữa các nút trong các hội nghị thương mại hoặc trong các nhóm làm việc 4 tạm thời. Tuy nhiên chúng có thể có những nhược điểm về vùng phủ sóng bị giới hạn, mọi người sử dụng đều phải nằm trong vùng có thể “nghe” được lẫn nhau. Hình 1.2: Mô hình mạng không dây Ad hoc 1.2 Một số mạng Ad hoc điển hình Hình 1.3: Mạng Ad hoc điển hình Hình trên mô tả một mạng Ad hoc đơn giản gồm có 7 nút, các nút mạng được ký hiệu từ N1 đến N7. Nhìn vào hình vẽ chúng ta có thể dễ dàng thấy được: ở thời điểm t1, các liên kết từ N1 đến N2, N1 đến N4, N2 đến N3, N4 đến N5, N3 đến N7, N2 đến N6 và N6 đến N7 là những liên kết mạnh (good link), còn các liên kết từ N4 đến N1, N6 đến N2, N5 đến N4 và N7 đến N3 là những những liên kết yếu (weak link). Như 5 vậy ở đây một đặc điểm của mạng Ad Hoc đã được thể hiện rõ. Đó là liên kết giữa 2 nút mạng của mạng có thể không giống nhau dù có chung điểm đầu và điểm cuối. Hiện tượng này được gọi là hiện tượng liên kết hai chiều không đối xứng. Liên kết từ N4 đến N5 là liên kết mạnh nhưng liên kết từ N5 đến N4 lại là liên kết yếu. Điều này là do vị trí an-ten của 2 nút mạng khác nhau, hoặc do năng lượng phát của các nút mạng trong mạng là khác nhau... Tương tự chúng ta cũng có thể thấy N3 có thể nhận tín hiệu từ N2 là một liên kết mạnh nhưng mà N2 lại không thu được tín hiệu từ N3. Sang đến thời điểm t2, lúc này topo mạng đã thay đổi do các nút di chuyển đến các vị trí khác nhau do đó các liên kết giữa các nút mạng cũng thay đổi theo. Lúc này, N1 chỉ có liên kết mạnh với N2, liên kết với N4 lại là liên kết yếu và N1 không còn thu được tín hiệu từ N4. Liên kết từ N2 đến N3 và N6 lại là liên kết mạnh. Lúc này, N2 cũng có thể thu được tín hiệu từ N3 mặc dù đó là liên kết yếu. Điều này ở thời điểm t1 là không có. Mặt khác chúng ta cũng có thể thấy hai nút mạng nằm trong vùng phủ sóng của nhau có thể truyền thông trực tiếp cho nhau. Ví dụ như trong thời điểm t1, việc truyền thông giữa hai nút mạng N1 và N4 là trực tiếp với nhau. Tuy nhiên ngay cả khi không nằm trong vùng phủ sóng của nhau thì giữa các nút mạng vẫn hoàn toàn có thể thực hiện việc truyền thông với nhau thông qua các nút mạng trung gian. Ví dụ N1 có thể thực hiện truyền dữ liệu cho N7 thông qua nút mạng trung gian N2 và N3, còn N6 có thể truyền dữ liệu cho N1 thông qua nút mạng N2 1.3 Các ứng dụng của mạng Ad hoc Đáp ứng nhu cầu truyền thông mang tính chất tạm thời: Ở tại địa điểm trong một khoảng thời gian nhất định, giống như trong một lớp học, một cuộc hội thảo hay một cuộc họp, ... việc thiết lập một mạng mang tính chất tạm thời để truyền thông với nhau chỉ diễn ra trong một khoảng thời gian ngắn. Nếu chúng ta thiết lập một mạng có cơ sở hạ tầng, dù là mạng không dây vẫn rất tốn kém tiền bạc cũng như nhân lực, vật lực, thời gian. Do đó, mạng Ad hoc được coi là giải pháp tốt nhất cho những tình huống như thế này. Hỗ trợ khi xảy ra các thiên tai, hỏa hoạn và dịch họa: Khi xảy ra các thiên tai như hỏa hoạn, động đất, cháy rừng ở một nơi nào đó, cơ sở hạ tầng ở đó như đường dây, các 6 máy trạm, máy chủ, ... có thể bị phá hủy dẫn đến hệ thống mạng bị tê liệt là hoàn toàn khó tránh khỏi. Vì thế, việc thiết lập nhanh chóng một mạng cần thời gian ngắn mà lại có độ tin cậy cao và không cần cơ sở hạ tầng để đáp ứng truyền thông, nhằm giúp khắc phục, giảm tổn thất sau thiên tai, hỏa hoạn là cần thiết. Khi đó mạng Ad hoc là một lựa chọn phù hợp nhất cho những tình huống như vậy. Đáp ứng truyền thông tại những nơi xa trung tâm, các vùng sâu, vùng xa: tại những nơi xa trung tâm thành phố, nơi có dân cư thưa thớt như ở vùng sâu, vùng xa, việc thiết lập các hệ thống mạng có cơ sở hạ tầng là rất khó khăn và tốn kém. Vậy ở những nơi này, giải pháp được đưa ra là sử dụng các mạng vệ tinh hoặc mạng Ad Hoc. Tính hiệu quả: Trong một số ứng dụng nào đó, nếu sử dụng dịch vụ mạng có cơ sở hạ tầng có thể không có hiệu quả cao bằng việc dùng mạng Ad hoc. Ví dụ như với một mạng có cơ sở hạ tầng, do được điều khiển bởi một điểm truy cập mạng nên các nút mạng muốn truyền thông với nhau đều phải thông qua nó. Ngay cả khi hai nút mạng ở gần nhau, chúng cũng không thể trực tiếp truyền thông với nhau mà phải chuyển tiếp qua một điểm truy cập trung tâm(Acess Point). Điều đó gây ra một sự lãng phí thời gian và băng thông mạng. Trong khi đó, nếu sử dụng mạng Ad Hoc việc truyền thông giữa hai nút mạng đó lại trở lên vô cùng dễ dàng và nhanh chóng. Hai nút mạng gần nhau có thể truyền thông trực tiếp với nhau mà không cần phải thông qua thiết bị trung gian nào khác. 1.4 Kết luận chương Chương này phản ánh khái quát về mạng Ad hoc và đưa ra mô hình và ứng dụng của nó. Vấn đề định tuyến trong mạng Ad hoc là vấn đề rất đáng được quan tâm vì nó quyết định trực tiếp đến hiệu năng của mạng, và định hướng nghiên cứu cho các chương tiếp theo. 7 CHƯƠNG II: ĐỊNH TUYẾN TRONG MẠNG VÔ TUYẾN AD HOC Việc thiết kế các giao thức định tuyến cho một mạng cần xét đến những tính năng cơ bản như: điều khiển tối đa, hạn chế quá trình xử lý, khả năng định tuyến đa chặng, bảo trì đồ hình động, ngăn ngừa truyền lặp. Với những tính năng trên chương này sẽ trình bày một số giao thức tiêu biểu trong mạng Ad hoc. 2.1 Giới thiệu về định tuyến trong mạng Ad hoc Trong một hệ thống mạng, một trong những yếu tố ảnh hưởng lớn nhất đến hiệu năng hoạt động của mạng đó là thời gian truyền các gói tin từ điểm đầu đến điểm cuối sao cho nhanh và chính xác nhất. Để đạt được điều đó thì cần phải có sự phối hợp của các thiết bị hoạt động ở các tầng khác nhau, trong đó có Router hoạt động ở tầng mạng. Router có nhiệm vụ tìm đường đi cho các gói tin, xác định các router trung gian để chuyển gói tin từ điểm đầu đến điểm cuối. Các thuật toán giúp xác định đường đi như vậy gọi là thuật toán định tuyến. Như vậy chức năng của thuật toán định tuyến chính là xác định đường đi tốt nhất cho gói tin từ bên gửi đến bên nhận sao cho nhanh nhất và chính xác nhất. Đối với mạng không dây có cơ sở hạ tầng, việc truyền thông giữa các nút mạng trong mạng phụ thuộc rất nhiều vào trạm cơ sở (còn gọi là AP). Các nút mạng muốn liên lạc với nhau đều phải nằm trong vùng phủ sóng của trạm cơ sở (nếu một nút mạng mà nằm ngoài vùng phủ sóng của trạm cơ sở thì nó không thể nào liên lạc được với các nút mạng khác). Nhưng với mạng Ad hoc thì lại khác, mạng Ad hoc không có trạm cơ sở, các nút mạng vừa là mạng ngang hàng, vừa là mạng không dây. Các nút mạng dù nằm ngoài hay nằm trong vùng phủ sóng của nhau vẫn có thể liên lạc được với nhau thông qua các nút mạng trung gian. Do đó, việc tìm ra các nút mạng trung gian để truyền gói tin giữa nút mạng đầu và nút mạng cuối là rất quan trọng và là một bài toán tiêu biểu trong nghiên cứu mạng Ad Hoc. Ngoài ra, có một số đặc điểm khác biệt của mạng Ad Hoc so với các mạng khác như các nút mạng có thể di động, dẫn đến topo mạng sẽ bị thay đổi; băng thông của mạng 8 cũng thay đổi liên tục, tốc độ truyền tín hiệu của mạng phụ thuộc nhiều vào tính chất vật lý của các nút mạng, giao diện mạng và khoảng cách giữa các nút trong mạng ... Chính những đặc điểm này làm cho việc thiết kế các giao thức định tuyến cho mạng Ad Hoc là một bài toán rất khó (Strong NP-Hard). Bởi vậy các giao thức định tuyến được thiết kế cần xét đến các tính năng cơ bản sau: Điều khiển tối đa: Điều khiển tin nhắn, tài nguyên xử lý, và năng lượng cho quá trình truyền và nhận dữ liệu. Tại vì độ rộng dải tần là một tài nguyên, các giao thức định tuyến không nên gửi nhiều tin nhắn cần cho thao tác và con số này được thiết kế tương đối nhỏ. Trong khi truyền tiêu tốn năng lượng gần gấp hai lần nhận thì cả hai thao tác này vẫn tiêu hao nguồn cho các thiết bị lưu động. Do đó giảm kiểm soát dữ liệu cũng giúp dự trữ nguồn điện. Hạn chế tối đa quá trình xử lý. Các thuật toán phức tạp đòi hỏi chu trình xử lý quan trọng trong các thiết bị. Tại vì các chu trình xử lý có thể tạo ra những thiết bị lưu động tiêu hao nhiều năng lượng nguồn. Các giao thức này nhỏ, nhẹ và tối thiểu quá trình xử lý của các thiết bị lưu động dự trữ điện nhưng nhiều hơn cho các thao tác định hướng của người sử dụng kéo dài tuổi thọ của nguồn pin. Khả năng định tuyến đa chặng. Tại vì quá trình truyền thông không dây của các nút di động thường xuyên bị hạn chế, các nút nguồn và đích có thể không nằm trong vùng truyền trực tiếp của nhau. Giao thức định tuyến có thể phát hiện ra những đường truyền đặc biệt giữa nguồn và đích đến để việc truyền tin giữa hai nút này diễn ra bình thường. Bảo trì đồ hình động. Khi thiết lập một đường truyền một vài liên kết có thể bị đứt do sự chuyển động của các nút. Để một nguồn có thể đến được đích thì luôn phải có một tuyến đường độc lập, thậm chí ở cả những nút trung gian hoặc ở những nút nguồn và đích. Hơn nữa các liên kết hỏng trong mạng Ad hoc khá thường xuyên lên các liên kết bị hỏng được đưa lên kênh điều khiển để nhanh chóng kết hợp xử lý. Ngăn ngừa truyền lặp. Lặp vòng định tuyến xảy ra khi nút dọc đường truyền chọn bước nhảy liền kề đích thì cũng có một nút khác như vậy xảy ra sớm hơn trên đường truyền. Khi có một sự truyền lặp thì dữ liệu và các gói dữ liệu điều khiển có thể đi 9 ngang qua đường truyền nhiều lần, cho đến khi đường truyền được sửa lại và truyền lặp đó bị loại trừ, hoặc đến khi giá trị TTL bằng 0. Do độ rộng dải thông nhỏ, việc xử lý và chuyển tiếp gói dữ liệu tiêu tốn tài nguyên lên lặp vòng tuyến tiêu tốn rất nhiều nguồn tài nguyên và gây thiệt hại cho mạng. Thậm chí một tuyến lặp vòng chỉ xảy ra trong chốc lát cũng gây nguy hại cho mạng. Do đó phải tuyệt đối tránh việc lặp vòng định tuyến. Với những mục đích trên rất nhiều giao thức định tuyến được phát triển trong mạng Ad hoc, trong chương này sẽ trình bày một số giao thức định tuyến tiêu biểu trong mạng Ad hoc. 2.2 Các yêu cầu đối với thuật toán định tuyến cho mạng Ad hoc không dây Như đã trình bày ở trên, do các đặc điểm khác biệt của mạng Ad hoc, chúng ta không thể áp dụng các thuật toán định tuyến truyền thống như Trạng thái đường liên kết (Link State) hay Véctơ khoảng cách (Distance Vector) cho mạng Ad Hoc được. Khi sử dụng sẽ dẫn đến một số vấn đề phát sinh: [11] Tiêu tốn băng thông mạng và năng lượng nguồn nuôi cho việc cập nhật định kỳ: Hầu hết các thiết bị di động trong mạng Ad Hoc sẽ hoạt động dựa trên nguồn pin, việc truyền, nhận gói tin sẽ tiêu tốn đáng kể đến nguồn năng lượng này. Các mạng thông thường, việc kết nối các bộ định tuyến là không thay đổi về vị trí, chính vì thế ít xảy ra việc thay đổi cấu hình tôpô mạng nên việc hội tụ mạng ít xảy ra.Tuy nhiên, trong mạng Ad Hoc, các nút luôn thay đổi vị trí dẫn đến cấu hình tôpô mạng thay đổi, nên đòi hỏi cần phải có sự hội tụ của mạng cho các tuyến mới một cách nhanh chóng. Để thực hiện được việc này, các giao thức định tuyến phải liên tục gửi thông tin cập nhật định tuyến, dẫn đến việc tiêu tốn khá nhiều băng thông và năng lượng. Các đường đi dư thừa được tích lũy một cách không cần thiết: Trong môi trường mạng Ad Hoc, có rất nhiều đường đi từ nút nguồn đến nút đích và những đường đi này sẽ được cập nhật tự động vào bảng định tuyến trong các thiết bị định tuyến (thiết bị di động), dẫn đến việc dư thừa đường đi trong bảng định tuyến. 10