Với sự phát triển ngày càng nhanh của các hệ thống mạng máy tính không dây, MANET, Wireless Network, Ad hoc network, Sensor network… đã dẫn tới việc phát triển các thuật toán về định tuyến gói tin (quyết định đường đi cho một gói tin trên mạng máy tính) cho mạng máy tính không dây. Bài viết này mong muốn giới thiệu khái quát về giao thức định tuyến theo thông tin địa lý, chiến lược định tuyến tham lam, và trình bày cách thức tạo một đồ thị phẳng để định tuyến gói tin theo quy tắc bàn tay phải.

Định tuyến không dây theo thông tin vị trí địa lý

Geographic routing protocol (GPRP) là những giao thức định tuyến dùng thông tin vị trí địa lý của các thiết bị trong hệ thống mạng để quyết định đường đi của các gói tin trong mạng. Không giống như những thuật toán định tuyến theo cấu trúc mạng ( như mạng có dây)GPRP không cần phải duy trì thông tin bảng định tuyến (Routing table) mà  sử dụng thông tin vị trí địa lý để định tuyến cho mạng không dây. Rất nhiều thuật toán Geographic routing sử dụng chiến lược tham lam  nhằm cố gắng tiếp cận tới vị trí đích trong mỗi bước chuyển tiếp, ví dụ tại mỗi bước GPRP chọn nút hàng xóm gần nhất với nút đích. Tuy nhiên, chiến lược trong trường hợp có quá ít các nút trong phạm vi định tuyến (void area) chiến lược tham lam sẽ thất bại.

Định tuyến theo thông tin địa lý (gọi là định tuyến vị trí cơ bản hay định tuyến theo hình học: Đó là công nghệ chuyển tiếp những gói tin tới một nút cùng  mạng thông qua  nút trung gian bởi thông tin chính là thông tin vị trí địa lý. Quyết định chuyển tiếp gói tin không được xây dựng từ địa chỉ mạng (IP) và bảng định tuyến chứa thông tin để định tuyến về phía vị trí đích. Cùng với những hiểu biết về thông tin địa lý nút kề (hàng xóm). Mỗi một nút có thể chọn một nút kế bên nó gần với nút đích nhất. Các nút sẽ chuyển tiếp thông tin tới nút đích qua mỗi bước, thực chất nó không có bảng định tuyến, cũng không có những route tìm kiếm. Trong định tuyến địa lý, việc cần thiết là xây dựng thông tin vị trí địa lý cho các nút của mạng di động như mạng không dây, mạng ad hoc, mạng cảm biến. Những mạng nêu trên, nếusử dụng định tuyến truyền thống cần phải xây dựng và bảo trì thông tin bảng định tuyến rất tốn kém. Định tuyến truyền thống luôn gọi những thông tin truyền tải và yêu cầu năng lượng cũng như băng thông và thường xuyên phải cập nhật bảng định tuyến với những kịch bản luôn thay đổiCấu trúc mạng thay đổi. Ngược lại, trong những thuật toán Greographic làm việc với những trạng thái luôn thay đổi và cung cấp những thông tin chuyển chuyển tiếp trong mạng với vị trí luôn thay đổi của các thiết bị mạng. Tất cả những thuật toán về Geographic đều tuân theo nhưng yêu cầu sau:

-  Trong một hệ thống mạng không dây một nút có thể xác định thông tin vị trí địa lý các nút cùng mạng.

-  Một nút có thể biết vị trí của nút hàng xóm.

-  Phải biết được vị trí của nút đích trước khi chuyển tiếp thông tin.

Cùng với hệ thống định vị thông tin toàn cầu (GPS) hoặc những hệ thống vệ tinh dò tìm chuyển hướng cơ bản, thông tin về vị trí của những thiết bị rất nhỏ có thể được dễ dàng xác định. Thêm vào đó, hệ thống vị trí địa lý cho những ứng dụng trong nhà đã được phát triển từ rất sớm.

Điều kiện tiên quyết để có những giả định là phải có hệ thống định vị thông tin vị trí (GPS). Nếu nó sẵn sàng thì định tuyến theo thông tin vị trí sẽ hỗ trợ một cách hiệu quả và mở rộng giải pháp cho định tuyến trong mạng không dây và di động. Tuy nhiên các nút luôn có giới hạn về phạm vi phát gói tin, vì vậy với một nút không có hàng xóm nào gần vị trí đích nhất thì thông tin định tuyến sẽ bị giữ. Thuật toán tham lam không giải quyết được vấn đề về khoảng cách và vấn đề vị trí tối thiểu của khoảng cách các nút. Để  giải quyết nhược điểm trên, thuật toán định tuyến phải kết hợp với định tuyến theo mặt phẳng và quy tắc định tuyến bàn tay phải.

Chiến lược định tuyến tham lam

Chiến lược định tuyến tham lam là một trong những phương pháp tiếp cận đầu tiên cho việc định tuyến Geographics, ra đời vào khoảng những năm 1980 nhằm hỗ trợ việc chuyển gói trong các mạng vô tuyến và mạng không dây. Thuật toán này giúp các nút sẽ quyết định chuyển tiếp gói tin một cách tối ưu tới đích theo khoảng cách gần nhất.

Việc lựa chọn nút tiếp theo trong chiến lược tham lam theo những điều kiện sau (xem thêm hình 1):

-  Progess (Sự tiến tới đích): Là tiêu chuẩn khoảng cách ngắn nhất của hình chiếu các nút trên trục trục đích nguồn st.

-  Khoảng cách tới đích ngắn nhất của các nút hàng xóm

-  Góc xa, góc tách: (góc tạo bởi nút nguồn - nút hàng xóm với trục nguồn đích)

-  NC (Nearest closer): Lựa chọn theo tiêu chí nút hàng xóm ngần nút nguồn nhất.

-  Greedy (Tham lam): Lựa chọn tiêu chí khoảng cách ngắn nhất từ nút đích tới các nút hàng xóm.

-  CR (Compass Routing): Lựa chọn tiêu chí góc tạo bởi nút hàng xóm, nút nguồn, nút đích là nhỏ nhất.

-  NFP (): Lựa chọn nút hàng xóm có khoảng cách hình chiếu gần nút nguồn nhất.

-  MFR (): Lựa chọn nút hàng xóm có khoảng cách hình chiếu gần nút đích nhất.

Định tuyến đồ thị phẳng và các phương pháp tạo đồ thị

Định tuyến đồ thị phẳng và chiến lược phục hồi

Cách tạo đồ thị phẳng

Thuật toán chuyển tiếp tham lam có một nhược điểm quan trọng đó là: khi số lượng các nút rất ít và không có hàng xóm nào gần với đích nhất trong mọi trường hợp thì việc định tuyến sẽ thất bại,khi đó việc định tuyến cần tới một vài thao tác đơn giản để tiếp tục định tuyến bằng chiến lược tham lam.

Định tuyến đồ thị phẳng (Planar graph routing) là một chiến lược định tuyến thông tin địa lý nó có thể chuyển tiếp gói tin qua những vùng vị trí tối thiểu (void area) của chuyển tiếp gói tin theo chiến lược tham lam. Vùng tối thiểu  tồn tại vùng biên của những vùng trống, nơi mà một nút cần chuyển tiếp gói tin không thể tìm thấy một hàng xóm nào gần với đích hơn chính nó, hay nút như vậy còn gọi là nút chết. Đồ thị phẳng là một nội dung quan trọng cho việc phục hồi từ những vấn đề vùng cục bộ tối thiểu (Local minimum),nó được xây dựng trên ý tưởng là mọi liên kết các vị trí là một mạng truyền thông phẳng và một gói tin có thể chuyển tiếp thành công qua các mặt của đồ thị. Định tuyến phụ thuộc vào mặt phẳng có nghĩa là các nút của mặt phẳng chuyển tiếp thông tin qua vùng mạng biên bằng cách áp dụng quy tắc “Bàn tay phải” hoặc “Bàn tay trái”. Quy tắc này thật sự tốt để giải quyết vấn đề vùng vị trí tối thiểu. Một nút tìm kiếm các nút khác nhằm để giải quyết vấn đề vùng trống là luôn luôn tìm kiếm theo một con đường duy nhất.

Trong một mạng máy tính không dây, các nút mạng luôn được liên kết với nhau theo một cách thức nào đó vì thế có thể dẫn tới một đồ thị chéo (đồ thị có các cạnh là các đường liên kết tới các nút mạng cắt nhau). Trong một đồ thị chéo thì việc định tuyến theo quy tắc bàn tay phải sẽ không thực hiện được, chúng ta phải chuyển các đồ thị chéo thành các đồ thị phẳng để có thể thực hiện việc định tuyến gói tin theo quy tắc bàn tay phải.

Có hai cách tiếp cận để chuyển một đồ thị chéo thành một đồ thị phẳng lồi đó là:

- Đồ thị vùng lân cận tương đối (RNG).

- Gabriel Graph (GG).

(có thể tham khảo thêm tại “Theory Geographic Routing Protocol))

Khi chuyển về đồ thị phẳng thì việc định tuyến gói tin theo mặt phẳng sẽ được áp dụng theo quy tắc bàn tay phải. Quy tắc này chỉ ra rằng tại một nút mạng gói tin sẽ luôn luôn chuyển tiếp gói tin theo một hướng cố định trái hoặc phải cho tới khi nào điều kiện áp dụng thuật toán tham lam có thể thực hiện được. Sự kết hợp của định tuyến mặt phẳng sẽ luôn là một chiến lược phục hồi hiệu quả cho việc định tuyến theo chiến lược tham lam.

Tài liệu tham khảo:

[1]: 2009, “Theory and Practice of Geographic Routing”, University of Freibug, Germany.

[2]:2000, “GPSR: Greedy Perimeter Stateless Routing for Wireless Networks”, Brad Karp and H.T.Kung, Havard University.