MỞ ĐẦU Với những cải tiến trong công nghệ truyền thông không dây, những thiết bị thu phát có năng lực mạnh và giá thành thấp đã được sử dụng rộng rãi trong nhiều ứng dụng di động. Trong những năm gần đây các mạng di động thu hút được sự quan tâm đáng kể vì đặc tính rất linh hoạt và có giá thành giảm. So với các mạng có dây, mạng di động có những đặc tính rất độc đáo. Trong các mạng di động, sự di chuyển của nút có thể dẫn tới việc hình trạng mạng thay đổi thường xuyên, điều này hiếm khi xảy ra với mạng có dây.
Mạng có dây có dung lượng liên kết ổn định trong khi đó dung lượng của liên kết không dây thường xuyên thay đổi vì ảnh hưởng của nguồn phát, độ nhậy của máy thu, nhiễu, pha đinh và xuyên nhiễu. Ngoài ra, các mạng di động không dây còn có tỷ lệ lỗi cao, bị giới hạn về công suất và băng thông [2], [3]. Tùy thuộc vào cơ sở hạ tầng cố định, các mạng di động có thể được phân chia thành mạng có cơ sở hạ tầng và mạng adhoc di động (MANET). Trong mạng di động có cơ sở hạ tầng, các nút di động có các điểm truy nhập có dây (hoặc các trạm gốc) trong cự ly truyền dẫn của chúng.
Những điểm truy nhập này tạo nên đường trục (backbone) cho mạng hạ tầng. Trái lại, các mạng adhoc di động là các mạng tự tổ chức mà không cần hỗ trợ hạ tầng. Trong mạng adhoc di động, các nút di chuyển tùy biến vì thế mạng có thể thay đổi hình trạng rất nhanh chóng và khó đoán trước. Ngoài ra vì nút trong các mạng adhoc di động thường có cự ly truyền dẫn giới hạn nên một số nút không thể truyền thông trực tiếp với nhau.
Vì vậy các đường định tuyến trong mạng adhoc di động có thể có nhiều chặng và mỗi nút trong mạng adhoc di động có thể làm việc như một bộ định tuyến. Các mạng adhoc di động ban đầu được đề xuất trong dự án của DARPA (Cục các dự án tiên tiến của Bộ quốc phòng Chính phủ Mỹ), PRNet (Mạng vô tuyến gói) và SURAN. Với hạ tầng độc lập thiết lập trước, các mạng adhoc di động có những ưu điểm như triển khai dễ và nhanh, cải thiện độ linh hoạt và chi phí giảm. Các mạng adhoc di động phù hợp với những ứng dụng di động kể cả trong môi trường bất lợi nơi không có 8 sẵn cơ sở hạ tầng hay trong các ứng dụng di động thiết lập tạm thời mà giá thành lại là vấn đề quan trọng.
Trong những năm gần đây, ứng dụng của các mạng adhoc di động đã ngày càng quan trọng hơn trong các tổ chức công cộng phi quân sự và trong những lĩnh vực thương mại và công nghiệp. Những ứng dụng điển hình nhất là cứu hộ, hoạt động thực thi pháp luật, robot công nghiệp hợp tác, điều hành giao thông và hoạt động giáo dục trong trường học. Những nghiên cứu chủ động cho các mạng adhoc di động được thực hiện chủ yếu trong các lĩnh vực điều khiển truy nhập môi trường (MAC), định tuyến, quản lý tài nguyên, điều khiển năng lượng và an toàn. Vì sự quan trọng của các giao thức định tuyến trong các mạng đa bước động, rất nhiều giao thức định tuyến mạng adhoc di động đã được đề xuất trong những năm gần đây.
Có một vài thách thức là cho sự thiết kế các giao thức định tuyến mạng adhoc di động trở nên khó khăn. Thứ nhất, trong các mạng adhoc di động sự di chuyển của nút làm cho hình trạng mạng thường xuyên thay đổi và gián đoạn. Thứ hai, vì dung lượng của các liên kết không dây là thay đổi và không thể đoán trước nên có thể thường xuyên xảy ra hiện tượng mất gói tin. Hơn nữa, bản chất quảng bá tự nhiên của môi trường không dây dẫn đến hiện tượng đầu cuối bị ẩn và nảy sinh nhiều bài toán về đầu cuối.
Ngoài ra, các nút di động bị giới hạn về tài nguyên như năng lượng, khả năng tính toán và băng thông nên yêu cầu có những cơ cấu định tuyến hiệu quả. Là kiểu mạng hứa hẹn cho những ứng dụng di động tương lai, các mạng adhoc di động là chủ đề ngày càng hấp dẫn các nhà nghiên cứu. Trong mạng có dây có hai giải thuật định tuyến chính được sử dụng là trạng thái liên kết và vector khoảng cách. Việc cập nhật thường xuyên và định kỳ của hai giải thuật này khiến nó khó có thể mở rộng trong mạng MANET lớn vì nó tiêu tốn một phần đáng kể băng thông, làm tăng việc cạnh tranh kênh truyền và tiêu hao nhiều năng lượng.
Để khắc phục vấn đề này có rất nhiều giao thức định tuyến cho mạng Ad hoc đã được đưa ra, có nhiều phương pháp để phân biệt các giao thức định tuyến này như dựa vào cách trao đổi thông tin định tuyến giữa các nút di động (dựa trên sự phản ứng); dựa vào vị trí địa lý; dựa vào hình trạng mạng (phẳng hay phân cấp); dựa vào năng lượng; dựa vào sự thích nghi; dựa vào sự an toàn hay dựa vào cách truyền multicast…[1], [2], [3], [4], [10], [11]. 9 Một trong những phương pháp phân loại phổ biến nhất là dựa vào cách trao đổi thông tin định tuyến giữa các nút di động, thông qua phương pháp này, có ba nhóm giao thức chính. Các giao thức định tuyến trong MANET (dựa vào cách trao đổi thông tin định tuyến) Các giao thức định tuyến chủ động DSDV OLSR FSR … Các giao thức định tuyến lai ZPR TORA … Các giao thức định tuyến theo yêu cầu DSR AODV ACOR … Hình 2.1: Một số giao thức định tuyến trong mạng MANET + Định tuyến chủ động hay định tuyến theo bảng (proactive routing/table-driven) + Định tuyến theo yêu cầu (reactive routing/on-demand routing) + Định tuyến lai (hybrid routing) Chương này sẽ giới thiệu một số vấn đề liên quan tới việc thiết kế các giao thức định tuyến trong mạng Adhoc và giới thiệu về một số giao thức định tuyến điển hình trong mạng Ad hoc. NHỮNG VẤN ĐỀ THIẾT KẾ CÁC GIAO THỨC ĐỊNH TUYẾN CHO MẠNG ADHOC 2.
Kiến trúc định tuyến 10 Kiến trúc định tuyến của mạng tự tổ chức có thể ở dạng phân cấp hoặc phẳng. Trong hầu hết các mạng tự tổ chức, các trạm (host) sẽ hoạt động như thiết bị định tuyến độc lập, có nghĩa là kiến trúc định tuyến coi như là phẳng, nghĩa là mỗi địa chỉ được nhận dạng duy nhất và không chứa bất kỳ thông tin gì về một trạm nào khác. Trong mạng tự tổ chức có kiến trúc phẳng thì không cần quản lý tính di động vì tất cả các nút có thể thấy nhau qua giao thức định tuyến. Trong các giải thuật định tuyến phẳng như DSDV (Destination Sequenced Distance Vector) và WRP (Wireless Routing Protocol), các bảng định tuyến có thông tin tới tất cả các trạm trong mạng tự tổ chức.
Tuy nhiên giải thuật định tuyến phẳng không có khả năng mở rộng tốt. Tiêu đề định tuyến tăng nhanh chóng khi mạng mở rộng. Vì vậy để điều khiển tái sử dụng không gian kênh (tần số, thời gian hay mã trải phổ) và giảm tiêu đề thông tin định tuyến, cần triển khai cơ cấu phân cấp. Phân cụm là kỹ thuật thông dụng nhất được dùng trong kiến trúc định tuyến phân cấp.
Ý tưởng ẩn sau định tuyến phân cấp là chia các trạm của mạng tự tổ chức thành một số cụm tách rời hoặc chồng lấn. Một nút được cử làm cụm chủ cho mỗi cụm. Cụm chủ này chứa thông tin của các thành viên trong cụm. Các nút không phải là cụm chủ sẽ được coi là nút bình thường.
Khi một nút bình thường gửi gói, nút có thể gửi gói tới cụm chủ để rồi gói được định tuyến tiếp tới đích. CGSR (Clusterhead Gateway Switch Routing) và CBRP (Cluster-Based Routing Protocol) là giao thức định tuyến loại này. Định tuyến phân cấp liên quan tới việc phân cụm, quản lý địa chỉ và tính di động. Hỗ trợ các liên kết đơn hướng Hầu hết giao thức định tuyến hiện tại có xu hướng coi toàn bộ liên kết là song hướng.
Tuy nhiên, có một số yếu tố sẽ làm liên kết không dây trở thành đơn hướng, đó là: + Tính năng vô tuyến khác biệt: Trong một mạng vô tuyến có thể có công suất phát hoặc độ nhạy máy thu khác nhau. Điều này tương tự trong môi trường quân sự khi có thiết bị cho con người và thiết bị xe cộ không dây. Với môi trường vô tuyến của xe cộ, vì ít bị giới hạn về kích thước và trọng lượng nên thiết bị thường 11 có công suất phát hớn hơn 12dB so với thiết bị theo người. Các liên kết đơn hướng sẽ thường gặp trong các mạng quân sự.
+ Nhiễu: Nhiễu do đài nhiễu âm đối địch hay do xen nhiễu lân cận, nó sẽ làm giảm độ nhạy của các máy thu ở gần. Ví dụ: Trạm A có thể nhận gói gửi từ trạm B vì có rất ít nhiễu trong vùng lân cận của A. Tuy nhiên B có thể nằm trong vùng nhiễu của một nút khác và vì vậy không thể nhận gói từ A. Do đó, liên kết giữa A và B có hướng từ B sang A.
+ Yêu cầu quảng bá bản tin: Việc quảng bá bản tin trên một vùng rộng có tầm quan trọng lớn. Các máy phát vệ tinh được dùng cho đường xuống trong khi đường lên sử dụng các đường luân phiên. + Chế độ câm: Trong trường hợp cực kỳ cá biệt, chỉ ứng dụng trong các mạng di động chiến sự là khi các trạm không thể phát do mối nguy hại sắp xảy ra. Trong trường hợp này, vẫn cần thu nhận thông tin, tuy nhiên không thể truyền thông song hướng.
+ Trạng thái hướng liên kết thay đổi theo thời gian: Trạng thái về hướng của liên kết không dây có thể ổn định hoặc là nhất thời. Tần suất của sự chuyển dịch và khoảng thời gian ở mỗi trạng thái sẽ là hàm của lưu lượng sắp đặt, địa thế, sự di động, mưa và năng lượng. Sử dụng siêu trạm Các giao thức định tuyến hiện tại đều giả sử rằng tất cả các trạm di động đều có đặc tính giống nhau do mạng tự tổ chức có cấu trúc ngang hàng, sử dụng các dịch vụ của nhau để truyền thông. Mặc dù trong một số trường hợp điều này là đúng, tuy nhiên cũng có những trường hợp khác là mạng có các trạm có băng thông vượt trội, cung cấp công suất đảm bảo và liên kết không dây có tốc độ cao.
Những trạm này được gọi là siêu trạm (SuperHost). Ví dụ, một công ty trong môi trường quân sự gồm nhiều lính bộ binh được trang bị theo người thiết bị không dây dung lượng thấp và một số xe tăng có phương tiện vô tuyến dung lượng cao.