Tài liệu Toi uu vo tuyen trong cac mang tuy bien

Các giải pháp định tuyến tối ưu trong mạng di động không dây tuỳ biến Trong mạng di động không dây tuỳ biến, mọi nút đều có khả năng di chuyển nên không có một nút mạng cố định nào thực hiện chức năng điều khiển trung tâm. Do đó làm thế nào để các nút mạng “bắt tay nhau” và duy trì được quá trình truyền thông mà không lãng phí tài nguyên mạng là một vấn đề cần đặc biệt quan tâm. TS. Nguyễn Hoàng Cẩm, KS. Trịnh Quang 1. Giới thiệu Trong mạng di động không dây tuỳ biến, mọi nút đều có khả năng di chuyển nên không có một nút mạng cố định nào thực hiện chức năng điều khiển trung tâm [1]. Do đó làm thế nào để các nút mạng “bắt tay nhau” và duy trì được quá trình truyền thông mà không lãng phí tài nguyên mạng là một vấn đề cần đặc biệt quan tâm. Để giải quyết vấn đề trên, đã có nhiều đề xuất về giải pháp định tuyến cho mạng di động tuỳ biến. Các giao thức như thế phải giải quyết những hạn chế đặc biệt của mạng này, trong đó bao gồm các vấn đề như tiêu thụ công suất lớn, băng thông thấp, và tỷ lệ lỗi cao [5]. Bài viết giới thiệu các giải pháp tối ưu hiện nay. 2. Tổng quan về định tuyến trong mạng di động không dây tuỳ biến Có rất nhiều giao thức định tuyến trong mạng di động không dây tuỳ biến. Song nhìn chung có 2 phương thức chính, đó là: Kiểu định tuyến điều khiển bằng bảng ghi và Kiểu định tuyến theo yêu cầu khởi phát từ nguồn (Hình 1). 2.1 Các phương pháp điều khiển theo bảng ghi Các giao thức định tuyến điều khiển theo bảng ghi cố gắng duy trì thông tin định tuyến cập nhật liên tục từ mỗi nút đến mọi nút khác trong mạng. Các giao thức này yêu cầu mỗi nút duy trì một hoặc nhiều bảng ghi để lưu trữ thông tin định tuyến, và chúng đáp ứng những thay đổi trong topo mạng bằng cách phát quảng bá rộng rải các thông tin cập nhật tuyến qua mạng để duy trì tầm kiểm soát mạng một cách liên tục. Những vùng nào khác nhau về số các bảng ghi liên quan đến định tuyến cần thiết và các phương thức thay đổi cấu trúc mạng sẽ được phát quảng bá để cho tất cả mọi nút đều có thể biết được. 2.2 Phương pháp định tuyến theo yêu cầu khởi phát từ nguồn Một phương pháp khác với phương pháp định tuyến điều khiển theo bảng ghi đó là định tuyến theo yêu cầu khởi phát từ nguồn. Phương pháp này chỉ tạo ra các tuyến khi nút nguồn cần đến. Khi một nút yêu cầu một tuyến đến đích, nó phải khởi đầu một quá trình khám phá tuyến. Quá trình này chỉ hoàn tất khi đã tìm ra một tuyến sẵn sàng hoặc tất cả các tuyến khả thi đều đã được kiểm tra. Khi một tuyến đã được khám phá và thiết lập, nó được duy trì bởi một số dạng thủ tục cho đến khi hoặc là tuyến đó không thể truy nhập được từ nút nguồn hoặc là không cần thiết đến nó nữa. 3. Các giải pháp định tuyến cho mạng di động tuỳ biến tối ưu hiện nay 3.1 Giao thức định tuyến không dây (WRP) WRP thuộc lớp thuật toán tìm đường dẫn. Để tránh bài toán phải tính đến vô cùng phải cưỡng bức mỗi nút thực hiện định tuyến liên tục kiểm tra thông tin trước đó được tất cả các nút lân cận báo cáo về. Điều này loại bỏ việc lặp lại không xác định và cho độ hội tụ tuyến nhanh hơn khi xảy ra sự cố trên đường thông [2]. Trong WRP, các nút cần biết về sự tồn tại của các nút lân cận từ một số bản tin đặc biệt. Nếu một nút không phải đang gởi gói, nó phải gửi một bản tin HELLO trong một khoảng thời gian xác định để đảm bảo thông tin kết nối được phản ánh một cách chính xác. Ngược lại, việc thiếu thiếu các bản tin từ nút có thể xác định sự cố đường thông vô tuyến và gây nên cảnh báo sai. Khi một nút thu được bản tin HELLO từ một nút mới, thông tin nút mới đó được thêm vào bảng định tuyến của nó, và nó sẽ gởi đến nút mới một bản sao thông tin bảng định tuyến của nó. WRP phải duy trì 4 bảng, đó là: Bảng cự ly, Bảng định tuyến, Bảng chi phí đường truyền, và Bảng ghi danh sách phát lại bản tin (MRL). Bảng ghi cự ly cho biết số chặng giữa một nút và nút đích của nó. Bảng ghi định tuyến cho biết nút ở chặng kế tiếp. Bảng ghi chi phí đường thông phản ánh độ trễ theo từng đường thông cụ thể. MRL chứa số thứ tự của bản tin cập nhật, bộ đếm số bản tin truyền lại, việc nhận biết vector cờ cần thiết, và danh sách thông tin cập nhật được gởi trong bản tin cập nhật. Các bản tin MRL cập nhật bản tin cần được phát lại và các nút lân cận phải biết về điều này. Để đảm bảo rằng thông tin định tuyến chính xác, các nút phải gởi bản tin cập nhật định kỳ đến các nút lân cận của nó. Bản tin cập nhật chứa thông tin cập nhật (danh sách nút đích, khoảng cách đến đích, các nút trước nút đích) cũng như danh sách các đáp ứng mà nút xác định được phải nhận biết để cập nhật. Một nút gửi các bản tin cập nhật sau khi xử lý thông tin cập nhật từ các nút lân cận hay khi phát hiện có sự thay đổi đường truyền. Khi sự cố đường thông xảy ra, các nút phát hiện sự cố sẽ gởi các bản tin cập nhật đến các nút lân cận của chúng, và các nút này sẽ hiệu chỉnh các thực thể trong Bảng ghi cự ly, đồng thời kiểm tra các đường dẫn mới khả thi thông qua các nút khác [2]. 3.3 Định tuyến vector cự ly theo yêu cầu tuỳ biến (AODV) Giao thức AODV (Ad Hoc On-Demand Distance Vector) dựa trên thuật toán vector khoảng cách được sắp xếp tới đích DSDV (Destination Sequenced Dista-nce Vector) trước đây (Hình 2). AODV tối thiểu hoá số bản tin quảng bá cần thiết bằng cách tạo ra các tuyến trên cơ sở theo yêu cầu, ngược với việc duy trì một danh sách hoàn chỉnh các tuyến như thuật toán DSDV. Khi một nút nguồn muốn gởi một bản tin đến một nút đích nào đó và không biết rằng đã có một tuyến đúng đến đích đó, nó phải khởi đầu một quá trình khám phá đường truyền để xác định nút khác. Nó phát quảng bá một gói yêu cầu tuyến (RREQ) đến các nút lân cận. Nút này sau đó sẽ chuyển tiếp gói yêu cầu đến nút lân cận khác. Quá trình cứ tiếp tục như vậy cho đến khi có một nút trung gian nào đó xác định được một tuyến “đủ tươi” (“fresh enough”) để đạt đến đích. AODV sử dụng số thứ tự đích để đảm bảo rằng tất cả các tuyến không lặp và chứa hầu hết thông tin tuyến hiện tại. Mỗi nút duy trì số tuần tự của nó cùng với một ID quảng bá. ID quảng bá được tăng lên mỗi khi nút khởi đầu một RREQ, và cùng với địa chỉ IP của nút, xác định duy nhất một RREQ. Cùng với số tuần tự và ID quảng bá, nút nguồn bao gồm trong RREQ hầu hết số tuần tự hiện tại của đích mà nó có. Các nút trung gian có thể trả lời RREQ chỉ khi nào chúng có một tuyến đến đích mà số tuần tự đích tương ứng lớn hơn hoặc bằng số tuần tự chứa trong RREQ. Trong suốt quá trình chuyển tiếp RREQ, các nút trung gian ghi vào Bảng định tuyến của chúng địa chỉ của các nút lân cận từ khi nhận được bản sao đầu tiên của gói quảng bá, theo đó thiết lập được một đường dẫn theo thời gian. Nếu các bản sao của cùng một RREQ được nhận sau đó, các gói này sẽ bị huỷ bỏ. Một khi RREQ đã đạt đến đích hay một nút trung gian với tuyến “đủ tươi”, nút đích (hoặc nút trung gian) đáp ứng lại bằng cách phát đơn phương một gói đáp ứng tuyến (RREP) ngược về nút lân cận mà từ đó nó thu được RREQ. Khi RREP được định tuyến ngược theo đường dẫn, các nút trên đường dẫn đó thiết lập các thực thể tuyến chuyển tiếp trong Bảng định tuyến của chỉ nút mà nó nhận được RREP. Các thực thể tuyến chuyển tiếp này chỉ thị tuyến chuyển tiếp tích cực. Cùng với mỗi thực thể tuyến là một bộ định thời tuyến có nhiệm vụ xoá các thực thể nếu nó không được sử dụng trong một thời hạn xác định. Do một RREP chuyển tiếp trên đường dẫn được thiết lập bởi một RREQ nên AODV chỉ hỗ trợ việc sử dụng đường truyền đối xứng. Trong AODV, các tuyến đươc duy trì điều kiện như sau: Nếu một nút nguồn chuyển động, nó phải khởi động lại giao thức khám phá tuyến để tìm ra một tuyến mới đến đích. Nếu một nút trên tuyến chuyển động, nút lân cận luồng lên của nó chú ý đến chuyển động đó và truyền một bản tin Khai báo sự cố đường thông (một RREP không xác định) đến mỗi nút lân cận tích cực luồng lên để thông báo cho các nút này xoá phần tuyến đó. Các nút này thực chất truyền một Thông báo sự cố đường thông đến các nút lân cận luồng lên. Quá trình cứ tiếp tục như vậy cho đến khi đạt đến nút nguồn. Nút nguồn sau đó có thể chọn khởi động lại một quá trình khám phá tuyến cho đích đó nếu một tuyến vẫn cần thiết [4]. Ngoài ra, giao thức này sử dụng bản tin HELLO được phát quảng bá định kỳ bởi một nút để thông báo cho tất cả các nút khác về những nút lân cận của nó. Các bản tin HELLO có thể được sử dụng để duy trì khả năng kết nối cục bộ của một nút. Tuy nhiên, việc sử dụng bản tin HELLO là không cần thiết. Các nút lắng nghe việc truyền lại gói dữ liệu để đảm bảo rằng vẫn đạt đến chặng kế tiếp. Nếu không nghe được việc truyền lại như thế, nút có thể sử dụng một trong số các kỹ thuật, kể cả việc tiếp nhận bản tin HELLO. Các bản tin HELLO có thể liệt kê các nút khác mà từ đó nút di động đã nghe tin báo, do đó tạo ra khả năng liên kết lớn hơn cho mạng. 3.4 Định tuyến nguồn động (DSR) Giao thức DSR (Dynamic Source Routing) là một giao thức định tuyến theo yêu cầu từ nút nguồn. Trong đó, các nút di động cần duy trì bộ nhớ đệm về tuyến chứa các tuyến nguồn mà nút di động nhận biết được. Các thực thể trong bộ nhớ đệm tuyến được cập nhật liên tục. Giao thức này bao gồm 2 giai đoạn chính: a) Khám phá tuyến, b) Duy trì tuyến (Hình 3). Khi một nút di động gởi một gói đến một nút đích nào đó, trước hết nó phải tham vấn bộ nhớ đệm tuyến để xác định là nó đã có một tuyến để đến đích chưa. Nếu nó có một tuyến chưa hết hiệu lực để đến đích, nó sẽ sử dụng tuyến này để gởi gói đi. Trái lại, nếu không có một tuyến như thế, nó phải khởi đầu một quá trình khám phá tuyến bằng cách phát quảng bá một gói yêu cầu tuyến. Bản tin yêu cầu này chứa địa chỉ đích, cùng với địa chỉ nút nguồn và số nhận dạng duy nhất. Mỗi nút nhận được gói này sẽ tiến hành kiểm tra là nó có biết một tuyến nào để đến đích không. Nếu không, nó thêm địa chỉ của nó vào Bảng ghi định tuyến của gói và sau đó chuyển tiếp gói trên các đường truyền ngõ ra. Để giới hạn số yêu cầu tuyến phát trên các đường truyền ngõ ra của nút, một nút chỉ chuyển tiếp yêu cầu tuyến nếu nó chưa biết yêu cầu đó và nếu địa chỉ của nút di động chưa xuất hiện trong Bảng ghi tuyến. Một đáp ứng tuyến được tạo ra khi hoặc là yêu cầu tuyến đạt đến đích hoặc là khi nó đạt đến một nút trung gian chứa trong bộ nhớ đệm tuyến của nó một tuyến đến đích chưa hết hiệu lực. Đến lúc gói có thể đạt đến đích hay đến một nút trung gian như thế, nó chứa một Bảng ghi tuyến cho biết số tuần tự chặng đã trải qua. Nếu nút tạo ra đáp ứng tuyến là đích thì nó đặt Bảng ghi tuyến chứa trong yêu cầu tuyến vào đáp ứng tuyến. Nếu nút tương ứng là một nút trung gian, nó gắn thêm tuyến trong bộ nhớ đệm của nó vào Bảng ghi tuyến và sau đó tạo ra một đáp ứng tuyến. Để trả về đáp ứng tuyến, nút tương ứng phải có một tuyến để khởi đầu. Nếu nó có một tuyến để khởi đầu trong bộ nhớ đệm tuyến của nó, nó có thể sử dụng tuyến đó. Trái lại, nếu các đường truyền đối xứng được hỗ trợ, nút có thể khởi đầu một quá trình khám phá tuyến của nó và tiếp tục gởi đi đáp ứng tuyến trên một yêu cầu tuyến mới. Việc duy trì tuyến được hoàn thành thông qua sử dụng các gói lỗi tuyến và các bản tin xác nhận. Các gói lỗi tuyến được tạo ra ở một nút khi lớp liên kết dữ liệu gặp sự cố đường truyền. Nút nguồn luôn luôn bị dừng khi một tuyến bị cắt xén. Khi nhận được một gói lỗi tuyến, chặng bị lỗi sẽ bị loại bỏ khỏi bộ nhớ đệm tuyến của nút và tất cả các tuyến chứa chặng này đều bị cắt ở điểm đó. Ngoài các bản tin lỗi tuyến, các bản tin xác nhận được sử dụng để xác minh sự hoạt động chính xác của các đường thông tuyến. Các bản tin xác nhận như thế bao gồm cả xác nhận thụ động (khi nút di động có thể nghe việc chuyển tiếp gói ở chặng kế tiếp trên tuyến). 3.5 Thuật toán định tuyến theo thứ tự tạm thời (TORA) TORA (Temporally Orde-red Routing Algorithm) là một thuật toán định tuyến phân bố không lặp vòng và độ thích nghi cao, dựa trên khái niệm đảo ngược đường thông. TORA được đề xuất cho môi trường nối mạng có tính linh động cao. Nó là một giao thức khởi phát từ nguồn và cung cấp đa tuyến cho mọi cặp nút nguồn/đích cần thiết. Nguyên lý chủ đạo trong TORA là định vị các bản tin điều khiển đối với mọi tập hợp các nút gần với nơi xảy ra sự thay đổi topo mạng. Để thực hiện được điều này, các nút cần duy trì thông tin định tuyến về các nút kế cận (chỉ một chặng). Giao thức này thực hiện 3 chức năng cơ bản: Tạo tuyến, Duy trì tuyến, và Xoá tuyến. Trong suốt giai đoạn tạo ra và duy trì tuyến, các nút sử dụng một tham số “độ cao” để thiết lập một DAG (sơ đồ hình xoắn ốc) có gốc ở nút đích. Sau đó, các đường truyền được chỉ định một hướng (luồng lên hay luồng xuống) dựa trên tham số độ cao tương đối của các nút lân cận. Quá trình thiết lập DAG tương tự như quá trình vấn tin/đáp ứng trong LMR (Light-Weight Moblie Routing - Định tuyến di động trọng số thấp). Trong thời gian một nút di chuyển, tuyến DAG bị phá vỡ và việc duy trì tuyến cần để thiết lập lại một DAG có gốc ở cùng đích đó. Khi đường thông luồng xuống cuối cùng bị sự cố thì một nút tạo ra một mức tham chiếu mới dựa vào mức tham chiếu của các nút lân cận, phối hợp hoạt động có hiệu quả để phản ứng lại sự cố đó một cách có cấu trúc. Các đường thông được đảo ngược để phản ánh những thay đổi trong việc thích nghi với mức tham chiếu mới. Việc này có hiệu quả giống như sự đảo hướng của một hay nhiều đường thông khi một nút không có các đường thông luồng xuống. Việc định thời là một yếu tố quan trọng đối với TORA do tham số “độ cao” độc lập với thời gian sự cố đường thông; TORA giả sử rằng tất cả các nút đều có đồng hồ đồng bộ (thực thi qua một nguồn thời gian bên ngoài như hệ thống định vị toàn cầu - GPS) [3]. Các tham số của TORA gồm: a) Thời gian sự cố đường thông, b) ID duy nhất của nút xác định mức tham chiếu mới, c) Bit chỉ thị phản ánh, d) Tham số thứ tự truyền, và e) ID duy nhất của nút. Tham số thứ 3 thể hiện mức tham chiếu một cách có chọn lọc. Một mức tham chiếu mới được xác định mỗi khi một nút không còn đường thông luồng xuống cuối cùng do sự cố đường thông. Giai đoạn xoá tuyến của TORA bao gồm một bản tin quảng bá “Xoá tuyến” (CLR) trong toàn mạng để xoá các tuyến không còn hiệu lực nữa. Trong TORA có một sự biến động tiềm tàng xảy ra, đặc biệt khi nhiều tập hợp các nút đang liên kết là phần hiện đang bị xoá, các tuyến đang xoá, và các tuyến đang xây dựng mới. Do TORA sử dụng toà độ liên nút nên bài toán bất cân bằng của nó tương tự như bài toán tính đến vô cùng trong các giao thức định tuyến theo vector cự ly, ngoại trừ các biến động là tạm thời và sự hội tụ tuyến cuối cùng vẫn đạt được. 4. Kết luận Bài báo đã giới thiệu một số giải pháp định tuyến trong mạng di động không dây tuỳ biến tối ưu hiện nay. Đây là một loại mạng khá mới mẻ nhưng đầy tiện ích. Hy vọng các kỹ thuật định tuyến cho loại mạng này sẽ được phát triển hơn nữa để ngày càng tối ưu độ thông, giảm thiểu sự lãng phí tài nguyên mạng. Tài liệu tham khảo [1]. W.R. Young, Advanced Mobile Phone Service: Introduction, Background & Objectives, in Bell Systems Technical Journal, Vol. 58, 1979. [2]. Theodore S. Rappaport, Wireless Communications, Prentice Hall, 1996. [3]. C.-K. Toh, Ph.D., Ad hoc Mobile Wireless Networks: Protocols and Sytems, Prentice Hall PTR, 2002. [4]. Nguyen Hoang Cam, Trinh Quang, Combined Congestion Control Mechanism for Advanced Intelligent Network, AIC 30th Conference, 2004. [5]. Nguyễn Hoàng Cẩm, Trịnh Quang, Mạng di động không dây tuỳ biến – Một giải pháp công nghệ trong kỷ nguyên thông tin số cá nhân toàn cầu, Tạp chí BCVT&CNTT, Kỳ 1 tháng 01/2005.