Giới thiệu vấn đề
Định tuyến trong mạng MANET là một thách thức phức tạp, với các giao thức định tuyến được chia thành ba loại chính: dựa trên cấu trúc mạng (topology-based), dựa trên vị trí (position-based) và kết hợp (hybrid) Các giao thức dựa trên cấu trúc mạng có thể là proactive, duy trì thông tin định tuyến ngay cả khi không sử dụng, như DSDV và OLSR; hoặc reactive, chỉ tìm kiếm đường định tuyến khi có yêu cầu, như DSR và AODV Giao thức hybrid, như ZRP, kết hợp cả hai phương pháp để tăng tính linh hoạt Đối với định tuyến theo vị trí, các gói dữ liệu được định tuyến dựa trên thông tin vị trí của các node, yêu cầu node phải khám phá khu vực xung quanh và xác định vị trí cũng như khoảng cách đến node đích thông qua dịch vụ vị trí Hiệu quả của phương pháp này phụ thuộc vào độ chính xác của dịch vụ vị trí, một vấn đề sẽ được thảo luận và đánh giá trong luận văn.
Mục tiêu của luận văn
Trong quá trình nghiên cứu về định tuyến theo vị trí trong mạng MANET, các công trình như luận văn của Nguyễn Thái Hùng (2008) đã chỉ ra rằng các giải thuật dịch vụ vị trí chưa được khai thác đầy đủ Luận văn này giới thiệu dịch vụ vị trí phân cấp (HLS - Hierarchical Location Service), đánh giá các loại hình dịch vụ vị trí và tác động của chúng đến hiệu quả định tuyến Các tiêu chí đánh giá bao gồm tỉ lệ thành công yêu cầu vị trí, thời gian đáp ứng và băng thông tiêu tốn HLS chia khu vực mạng thành các vùng phân cấp, với vùng cao nhất là toàn bộ mạng, được chia thành các vùng cấp thấp hơn cho đến vùng thấp nhất gọi là cell Mỗi node sẽ có một cell đặc biệt tại mỗi cấp độ phân cấp, và khi node thay đổi vị trí, thông tin cập nhật sẽ được gửi đến các cell này.
Khi một node muốn xác định vị trí của node A, nó sẽ sử dụng một hàm hash để xác định các "responsible cells" có thể chứa thông tin về vị trí của node A Sau đó, node này gửi các gói dữ liệu yêu cầu thông tin vị trí đến các cell này theo thứ tự phân cấp cho đến khi nhận được phản hồi về vị trí của node A.
( a) Cell (b) Vùng level 1 (c) Vùng level 2
Hình 1.1: Nhóm các cell lại thành vùng
HLS chia mạng thành các vùng nhỏ gọi là cell, gán mỗi node vào một tập hợp S của các cell Việc cập nhật và yêu cầu thông tin vị trí của các node được gửi đến các tập hợp con của S, với việc lựa chọn tập con thông qua hàm hash, phụ thuộc vào số lượng cell.
ID của mỗi node, phân cấp nhóm các cell của tập S và phụ thuộc vào vị trí hiện tại của node trong mạng, như trong hình 1.2
Cây ứng viên với cấu trúc phân cấp đến level-3 mở ra nhiều cơ hội phát triển cho việc đánh giá chi tiết tùy thuộc vào các kịch bản và môi trường thực tế Đặc biệt, việc đánh giá các dịch vụ vị trí phổ biến như GLS (Grid Location Service) sẽ làm nổi bật những ưu điểm của dịch vụ vị trí phân cấp HLS, bao gồm tỷ lệ thành công trong việc yêu cầu thông tin vị trí và thời gian phản hồi.
Phạm vi đề tài
Do thời gian tìm hiểu đề tài là có hạn nên luận văn xin được trình bày trong phạm vi sau:
The routing algorithm utilized in the thesis is GPSR, or Greedy Perimeter Stateless Routing This algorithm relies entirely on the location information of nodes to determine routing paths through greedy forwarding and perimeter forwarding modes.
Hàm hash sử dụng đơn giản và cần được tối ưu theo các môi trường triển khai thực tế
Thực hiện mô phỏng và đánh giá trên một mạng nhỏ với số lượng nút hạn chế do khả năng tính toán của máy tính.
Cập nhật thông tin vị trí theo phương pháp gián tiếp.
CÁC VẤN ĐỀ TRONG MẠNG MANET
Giới thiệu sơ lược về mạng MANET
2.1.1 Sự ra đời mạng MANET
Ngày nay, sự phát triển của công nghệ thông tin và truyền thông, đặc biệt là các ứng dụng không dây, đã mang lại nhiều tiện ích cho cuộc sống Điện thoại di động và máy tính xách tay trở thành những thiết bị thiết yếu trong công việc và sinh hoạt hàng ngày Tuy nhiên, để các thiết bị này có thể kết nối mạng, cần có một cơ sở hạ tầng phù hợp, như mạng cell cho điện thoại di động và các Access Point (AP) cho máy tính xách tay.
Mạng di động ad-hoc (MANET) được phát triển để giải quyết vấn đề kết nối mạng trong những điều kiện khó khăn, như trên chiến trường hoặc trong các khu vực bị thiên tai như núi lửa, động đất, hay lũ lụt Khi không thể lắp đặt các thiết bị hạ tầng mạng truyền thống, MANET cho phép người dùng tiếp tục tận hưởng sự tiện lợi của mạng không dây.
2.1.2 Giới thiệu về mạng MANET
Tương lai công nghệ thông tin sẽ chủ yếu phụ thuộc vào công nghệ không dây, trong khi mạng cell và mạng truyền thống vẫn tồn tại nhưng sẽ bị hạn chế bởi yêu cầu hạ tầng như trạm thu phát gốc và bộ định tuyến Mạng MANET đã khắc phục những hạn chế này, mở ra hướng đi mới cho sự phát triển của công nghệ.
Mạng MANET, một yếu tố quan trọng trong sự phát triển của mạng không dây, được hình thành từ các node ngang hàng giao tiếp qua kênh truyền vô tuyến mà không cần bộ điều khiển trung tâm Mặc dù chủ yếu được sử dụng trong quân sự, các ứng dụng thương mại của MANET đang ngày càng mở rộng, bao gồm nhiệm vụ cứu hộ trong thiên tai, các mục đích thương mại và giáo dục, cũng như mạng cảm biến không dây.
Mạng MANET phải đối mặt với những thách thức tương tự như mạng không dây truyền thống, bao gồm tối ưu băng thông, quản lý năng lượng và cải thiện chất lượng đường truyền Thêm vào đó, do đặc điểm đa hop và thiếu hạ tầng cố định, mạng này còn gặp phải các vấn đề mới như cấu hình quảng bá, tìm đường và duy trì tuyến trong quá trình định tuyến.
Trong mạng MANET, cấu hình mạng liên tục biến đổi ngẫu nhiên, và sự phân bố của các node cùng khả năng tự tổ chức đóng vai trò quan trọng Những đặc tính chính của mạng MANET có thể được tóm tắt như sau:
• Cấu hình mạng năng động và sự thay đổi thường xuyên là không dự đoán được
• Sử dụng kênh truyền không dây nên có sự hạn chế về dung lượng hơn là mạng có dây truyền thống
• Sự bảo mật là hạn chế do kênh truyền không dây
• Bị ảnh hưởng bởi sự mất mát gói dữ liệu lớn, chịu delay và jitter lớn hơn là mạng cố định do sự lan truyền sóng vô tuyến
Trong mạng MANET, các node chủ yếu sử dụng pin làm nguồn năng lượng chính, do đó, việc tiết kiệm năng lượng trở thành tiêu chí quan trọng trong thiết kế hệ thống Hơn nữa, các lệnh thực hiện trên node còn phụ thuộc vào năng lượng sẵn có, bao gồm CPU và bộ nhớ.
Mạng MANET không chỉ dựa vào một công nghệ duy nhất mà còn tận dụng nhiều công nghệ tiên tiến khác nhau Nhiệm vụ chính là định nghĩa các giao diện để các lớp trên có thể sử dụng mà không ảnh hưởng đến công nghệ mới ở lớp vật lý Thông tin về phân bố các node, mật độ mạng và tình trạng link hỏng cần được chia sẻ giữa các lớp khác nhau Sự hợp tác hiệu quả giữa lớp MAC và lớp mạng là cần thiết để có cái nhìn tổng quát về cấu hình mạng và tối ưu hóa số lượng thông báo trên mạng.
Mạng MANET có cấu trúc độc lập và quyền ưu tiên, mang lại tiềm năng lớn cho người dùng Chỉ cần từ 2 node trở lên, một mạng MANET có thể được thiết lập miễn là các node đủ gần để truyền sóng vô tuyến mà không bị can thiệp từ bên ngoài.
Mạng MANET cho phép các node như A truyền nhận dữ liệu trực tiếp (đơn hop) với các node khác như B khi có kênh truyền radio sẵn có Nếu không có kênh truyền thẳng giữa hai node, dữ liệu sẽ được truyền qua nhiều hop, trong đó các node trung gian sẽ hoạt động như router Ví dụ, khi không có kênh truyền trực tiếp giữa A và C, node B sẽ đóng vai trò làm router, thể hiện đặc điểm nổi bật của mạng MANET.
Những ứng dụng trong mạng MANET
Các công nghệ kĩ thuật cao luôn đóng vai trò quan trọng trong lĩnh vực quân sự, và mạng MANET là một trong những sản phẩm phát triển từ đó Không cần sự điều khiển từ trung tâm hay cơ sở hạ tầng sẵn có, mạng MANET trở thành giải pháp lý tưởng cho các ứng dụng quân sự Trên chiến trường, binh lính có thể liên lạc dễ dàng và nhanh chóng mọi lúc, mọi nơi.
Hình 2.4 Ứng dụng mạng MANET trong quân sự
2.2.2 Trong mạng cục bộ Đây là mạng mà có thể gặp được dễ dàng trong các hội nghị hoặc trong lớp học Khi các node muốn kết nối lại với nhau để có thể truyền và nhận dữ liệu
2.2.3 Trong trường hợp khẩn cấp
Mạng MANET, với đặc tính không cần hạ tầng cố định và khả năng quản trị linh hoạt, rất phù hợp trong các tình huống hạ tầng mạng bị phá hủy hoặc không khả dụng Việc thiết lập mạng MANET trong các tình huống khẩn cấp giúp các thiết bị di động liên lạc hiệu quả, cung cấp các dịch vụ mạng quan trọng cho công tác cứu hộ Ví dụ, lính cứu hỏa và cảnh sát có thể nhanh chóng trao đổi thông tin và phối hợp hành động khi hạ tầng đã bị tàn phá.
2.2.4 Mạng cảm biến không dây
Nhiều nghiên cứu gần đây đã chỉ ra rằng mạng cảm biến không dây (wireless sensor networks) sử dụng cảm biến để thu thập thông tin và truyền về một bộ phận xử lý trung tâm Khi được lắp đặt, vị trí của các cảm biến luôn cố định, điều này rất hữu ích trong các môi trường khó khăn trong việc cung cấp hạ tầng mạng Chẳng hạn, trong môi trường bị ô nhiễm phóng xạ hóa học, thay vì gửi đội cứu hộ khẩn cấp, chúng ta có thể lắp đặt các cảm biến để tạo thành một mạng ad-hoc Các thiết bị cảm biến có kích thước nhỏ và tiêu thụ ít năng lượng, do đó, tiết kiệm năng lượng là mục tiêu chính của các nhà thiết kế mạng cảm biến.
Những thách thức đối với mạng MANET
Trong mạng MANET, các node di chuyển ngẫu nhiên và tự tổ chức, tự cấu hình lại khi tham gia hoặc rời khỏi mạng, dẫn đến sự thay đổi thường xuyên của cấu hình mạng Tất cả các node có vai trò ngang nhau và các chức năng mạng được phân phối, không cần máy quản trị trung tâm Tuy nhiên, điều này cũng gây ra nhiều khó khăn cho mạng MANET.
2.3.1 Giao thức định tuyến đa hop
Khoảng cách giữa nguồn và đích trong mạng MANET thường vượt quá khả năng lan truyền sóng từ node, dẫn đến việc các tuyến đường thường là đa hop Việc thiết kế một giao thức định tuyến hiệu quả và tin cậy trở nên khó khăn do giới hạn về băng thông và năng lượng Một giao thức định tuyến tốt cần sử dụng tài nguyên hạn chế một cách hiệu quả, thích ứng với cấu hình mạng thay đổi thường xuyên và điều kiện mạng đa dạng như tốc độ di chuyển của các node, kích thước mạng và lưu lượng Các yêu cầu cho giao thức định tuyến trong mạng MANET bao gồm: không bị lỗi lặp, hiệu quả năng lượng, khả năng mở rộng và tính bảo mật do môi trường không dây Chính vì vậy, các giao thức định tuyến dành cho mạng cố định không thể áp dụng cho mạng MANET.
2.3.2 Khả năng mở rộng của mạng
Khi số lượng node trong mạng tăng, việc mở rộng mạng trở nên quan trọng hơn bao giờ hết Tính mở rộng được định nghĩa là khả năng cung cấp dịch vụ chấp nhận được khi số node lớn Hầu hết các giao thức định tuyến sử dụng mô hình địa chỉ phẳng, trong đó các node có vai trò tương đương, dẫn đến việc tạo ra một lượng lớn gói định tuyến khi số node gia tăng.
Bảo mật trong mạng MANET là một thách thức lớn do sự thiếu vắng máy quản trị trung tâm và tính chất di động của các node Trong khi các mạng cố định có thể dễ dàng quản lý bảo mật nhờ vào cấu hình ổn định và sự hiện diện của các máy quản trị, thì MANET lại không hỗ trợ điều này Các node có khả năng di chuyển tự do và tham gia hoặc rời khỏi mạng một cách linh hoạt, khiến cho các giải pháp bảo mật áp dụng cho mạng cố định không còn hiệu quả trong môi trường MANET.
2.3.4 Chất lượng dịch vụ Đây là một đặc tính quan trọng đối với mạng MANET vì các ứng dụng đa phương tiện ngày càng tăng lên Những ứng dụng này thường đặt ra các yêu cầu nhận dữ liệu tại một tốc độ nào đó hoặc có trễ (delay) xác định Vì băng thông sẵn có dành cho các ứng dụng này của mạng MANET là hạn chế, một phương pháp quản lý băng thông thích hợp là cần thiết để cung cấp cho các ứng dụng và cung cấp chất lượng (QoS) cho người sử dụng Đã có các mô hình QoS được đưa ra cho mạng Internet Tuy nhiên do đặc thù của môi trường không dây, cấu hình mạng thường xuyên thay đổi và thiếu sự hỗ trợ của máy trung tâm nên mô hình QoS của mạng có dây không thể ứng dụng trong MANET
Hầu hết các node di động sử dụng pin làm nguồn năng lượng chính, dẫn đến hạn chế trong việc cung cấp dịch vụ Nghiên cứu gần đây về pin nhiên liệu chưa thể ứng dụng trong tương lai gần, do đó, việc quản lý năng lượng hiệu quả mà không ảnh hưởng đến các ứng dụng là một vấn đề quan trọng trong nghiên cứu mạng MANET.
Định tuyến trong mạng MANET
2.4.1 Các giao thức định tuyến trong mạng cố định
Giao thức định tuyến link-state và distance-vector đã được sử dụng lâu dài trong mạng chuyển mạch gói, cho phép các node xác định hop kế tiếp trên tuyến ngắn nhất đến đích Tuyến ngắn nhất được tính toán dựa trên các tiêu chuẩn như số bước truyền tối thiểu Đối với giao thức link-state, mỗi node cần thu thập trạng thái của các link đến các node lân cận và phân tán thông tin này đến các node khác qua các gói link state packets (LSPs) Quá trình này diễn ra định kỳ hoặc khi có thay đổi về "cost" của các link, với mỗi gói LSPs được gán một số thứ tự để nhận diện độ mới, trong đó gói LSPs mới nhất có số tuần tự lớn nhất.
Mỗi node trong mạng khi nhận LSPs sẽ cập nhật chi phí của các liên kết Dựa trên thông tin này, các node thực hiện thuật toán Dijkstra để tìm đường ngắn nhất và xác định đường tối ưu với chi phí thấp nhất Giao thức Distance Vector là cơ sở cho quá trình này.
Giao thức distance vector sử dụng thuật toán Bellman-Ford, cho phép mỗi node quảng bá toàn bộ bảng định tuyến của mình đến các node lân cận Khi nhận thông tin từ các node neighbor, node sẽ cập nhật bảng định tuyến dựa trên dữ liệu mới Tuy nhiên, hai giao thức này cũng gặp phải một số khó khăn trong quá trình hoạt động.
Cả 2 giải thuật trên đều chứng tỏ được hiệu quả của nó đối với những mạng cố định Tuy nhiên, chúng không thể tương thích với mạng có đồ hình thay đổi thường xuyên Nó không chỉ mất thời gian để tìm tuyến khác khi kết nối bị đứt gãy mà còn tiêu tốn rất nhiều tài nguyên để tìm ra những tuyến mà có thể không bao giờ được sử dụng Do đó, đối với những đặc tính mạng có đồ hình thay đổi thường xuyên (như MANET) đòi hỏi phải có những giải thuật khác phù hợp hơn trong việc định tuyến
2.4.2 Các giao thức định tuyến trong mạng MANET
Trong MANET, định tuyến cần đáp ứng các yêu cầu như phát hiện nhanh sự thay đổi của mạng, xây dựng và lựa chọn tuyến, cũng như truyền dữ liệu hiệu quả Bên cạnh đó, cần chú ý đến lượng thông tin báo hiệu và thời gian trễ trong quá trình truyền gói Các giao thức định tuyến được phân chia thành hai nhóm chính: Proactive và Reactive, tùy thuộc vào cách thức xử lý khi đồ hình mạng thay đổi Ngoài ra, còn nhiều phương pháp định tuyến khác như Flow Oriented Routing, Adaptive Routing, Hybrid, Hierarchical Routing, Geographical Routing, Power Aware Routing, và Multicast Routing Bài viết sẽ tập trung vào ba nhóm định tuyến chính: Proactive, Reactive và Geographical.
Trong các giao thức định tuyến Proactive, mỗi node duy trì cái nhìn toàn cảnh về mạng bằng cách thường xuyên trao đổi thông tin với các node lân cận Khi có sự thay đổi trong đồ hình mạng, thông tin này sẽ kích hoạt các node tính toán lại bảng định tuyến, đảm bảo rằng mỗi node luôn có tuyến đường mới nhất, tốt nhất và nhanh nhất đến tất cả các node trong mạng.
Proactive routing protocols in Mobile Ad hoc Networks (MANETs) include various methods, with Destination-Sequence Distance-Vector (DSDV) being a prominent example DSDV utilizes a unique approach by maintaining up-to-date routing information to ensure efficient data transmission across the network.
Trong giao thức DSDV, các node định kỳ quảng bá thông tin về cấu trúc mạng của chúng cho các node lân cận, từ đó xây dựng bảng định tuyến riêng Bảng này bao gồm danh sách các node trong mạng, số hop cần thiết để đến node đó, node tiếp theo để chuyển gói (next-hop) và số thứ tự (sequence number) của node Ưu điểm nổi bật của DSDV là khả năng tránh lặp đường (loop-free) nhờ vào việc sử dụng số thứ tự Một node chỉ cập nhật bảng định tuyến khi số thứ tự nhận được từ node đích lớn hơn số thứ tự hiện có, hoặc trong trường hợp số thứ tự bằng nhau, chỉ cập nhật khi hop count nhỏ hơn Thông tin chi tiết về hoạt động của DSDV được trình bày trong bảng 2.1.
Giao thức Proactive đảm bảo mỗi node trong mạng có tuyến tốt nhất đến tất cả các node khác mà không cần quan tâm đến việc sử dụng tuyến đó Tuy nhiên, khi số lượng người dùng tăng, lượng thông tin báo hiệu cũng tăng lên đáng kể Ngược lại, giao thức Reactive chỉ cập nhật thông tin mạng khi cần gửi dữ liệu đến một node đích, giúp giảm thiểu thông tin không cần thiết nhưng gây ra độ trễ do phải tìm đường trước khi gửi dữ liệu Giao thức Reactive phù hợp cho các mạng có đồ hình thay đổi thường xuyên Trong số các giao thức định tuyến kiểu Reactive, DSR và AODV là hai ví dụ điển hình Bài viết này sẽ trình bày chi tiết về phương pháp định tuyến DSR, một ví dụ của giao thức Reactive.
Bảng 2.1: Hoạt động của DSDV
Ban đầu, D lưu trữ thông tin đường đi đến F trong bảng định tuyến của nó
F di chuyển và trở thành nút lân cận của
F quảng bá thông tin về vị trí mới của nó đồng thời tăng số thứ tự của nó thêm 1
D bắt đầu cập nhật thông tin của F vào bảng ắ Dynamic Source Routing (DSR)
DSR sử dụng định tuyến Source Routing, khác với Next-hop Routing của DSDV, trong đó mỗi gói dữ liệu chứa danh sách tất cả các node mà nó sẽ đi qua trước khi đến đích Điều này có nghĩa là node nguồn quyết định tuyến đường cho gói, trong khi với Next-hop Routing, node nguồn chỉ xác định node kế tiếp để chuyển gói Lợi ích của Source Routing là các node trung gian không cần lưu trữ hay cập nhật thông tin về tuyến đường, vì thông tin đã được chỉ rõ trong gói Tuy nhiên, nhược điểm là kích thước gói dữ liệu tăng lên do phải chứa thông tin về toàn bộ tuyến, đặc biệt khi có nhiều nút trung gian.
Bảng 2.2: Hoạt động của DSR
A cần gửi dữ liệu đến G,
A gửi yêu cầu RREQ (Route REQuest) cho những nút lân cận (C,B)
Những nút trung gian (D, E, F) khi nhận RREQ chèn thêm địa chỉ của chúng và gửi tiếp cho các nút kế tiếp
Khi RREQ đến G, G chọn tuyến có ít số nút trung gian nhất để gửi trả thông tin RREP (Route REPly) về cho A
A bắt đầu gửi dữ liệu kèm theo danh sách các nút trung gian trong mỗi gói theo tuyến vừa tìm được đến G
Định tuyến dựa vào thông tin vị trí trong mạng MANET
Phương pháp định tuyến theo vị trí sử dụng kỹ thuật Proactive hoặc Reactive kết hợp với thông tin tọa độ địa lý thực từ hệ thống GPS, GLONASS hoặc Galileo, giúp cải thiện việc tìm kiếm các node đích trong mạng lưới lớn Việc biết tọa độ của đích cho phép gửi gói điều khiển và dữ liệu theo hướng chính xác, giảm thiểu overhead điều khiển Tuy nhiên, tất cả các node cần truy cập liên tục thông tin vị trí của chính mình và các node xung quanh để đảm bảo hiệu quả trong việc định tuyến Phần tiếp theo sẽ đi sâu vào định tuyến dựa trên thông tin vị trí trong mạng MANET.
Các giao thức dựa vào vị trí được trình bày dưới đây giả định rằng các node có khả năng xác định chính xác vị trí của chúng trong mạng Những vị trí này có thể được xác định thông qua hệ thống định vị toàn cầu GPS hoặc các phương pháp định vị khác.
The Location-Aided Routing (LAR) protocol is a type of reactive routing protocol that utilizes location information during the route discovery process to minimize overhead caused by flooding techniques This location information can be sourced from Global Positioning System (GPS) technology.
Hình 2.5: Ví dụ minh họa vùng Expected zone và request zone
Giao thức này xác định hai vùng quan trọng: vùng mong đợi (expected zone) và vùng yêu cầu (request zone) Vùng mong đợi chứa vị trí của node đích, được tính toán dựa trên vị trí của node đích tại thời điểm t0 trong quá khứ và ước lượng vận tốc của nó Trong khi đó, vùng yêu cầu là khu vực mà các gói tin route request cần phải nằm trong đó để truyền tới đích.
Gọi vị trí node đích tại thời điểm t0 là D, vận tốc ước lượng là v, thời điểm hiện tại là t1 Vậy vùng expected zone là vòng tròn tâm D, bán kính v(t1 - t0)
Tiến trình tìm tuyến trong LAR tương tự như các giao thức định tuyến reactive khác Khi node nguồn cần xác định đường tuyến tới đích, nó sẽ tạo gói tin route request (RREQ) Nếu node nguồn đã có tuyến tới đích, nó sẽ tính toán vùng expected zone và request zone, sau đó cập nhật tọa độ đường biên của vùng request zone vào thông tin RREQ Ngược lại, nếu nguồn không có thông tin về vị trí của node đích trước đó, nó không thể tính toán các vùng này và sẽ sử dụng thuật toán flooding.
Khi một node nhận RREQ, nó đầu tiên xác định xem có nằm trong vùng request zone được định nghĩa trong RREQ hay không Nếu không nằm trong vùng này, node sẽ không xử lý gói tin Ngược lại, nếu ở trong vùng request zone, node sẽ xử lý gói và tiếp tục quảng bá gói tin hoặc gửi một gói reply, tùy thuộc vào việc có đường tuyến tới đích tại thời điểm đó hay không.
Kích thước của vùng request zone là sự cân bằng giữa overhead điều khiển và khả năng xác định đích Nếu vùng request zone quá nhỏ, khả năng node đích không nằm trong vùng này sẽ cao Ngược lại, nếu vùng request zone quá lớn, overhead điều khiển sẽ gia tăng.
Ngoài phương pháp xác định vùng request zone truyền thống, LAR giới thiệu một phương pháp thứ hai dựa trên khoảng cách từ node nguồn tới đích Khi nhận RREQ, các node lân cận sẽ tính toán khoảng cách của chúng tới đích (DISTi) và so sánh với khoảng cách từ nguồn tới đích trong RREQ (DISTS) Nếu DISTS cộng với một tham số δ nhất định lớn hơn hoặc bằng DISTi, node đó sẽ xử lý request và thay thế DISTS bằng DISTi khi chuyển tiếp gói tin Ngược lại, nếu không đáp ứng điều kiện này, node sẽ không xử lý request.
< DISTi, node sẽ loại bỏ RREQ
Cả hai phương pháp đều sử dụng RREQ để hạn chế việc flooding toàn bộ mạng, giúp giảm băng thông và overhead so với các giao thức dùng kỹ thuật flooding Tuy nhiên, LAR chỉ giới hạn vùng flooding, dẫn đến overhead cao và lãng phí tài nguyên mạng.
Thuật toán DREAM (Distance Routing Effect Algorithm for Mobility) thực hiện định tuyến dựa trên hai quan sát chính: hiệu quả khoảng cách và việc gửi gói tin cập nhật vị trí theo tính di động của các node Thông tin vị trí trong bảng định tuyến được cập nhật dựa trên khoảng cách giữa các node, với tần suất cập nhật thấp hơn cho các node di chuyển chậm hơn Phương pháp này tối ưu hóa tần suất gửi gói tin, giảm băng thông và năng lượng tiêu thụ Bảng định tuyến tại mỗi node chứa thông tin vị trí của các node khác, có thể xác định tọa độ bằng GPS Giao thức này mang tính Proactive, khi các node phải cập nhật thông tin vị trí cho nhau Khi node A muốn gửi thông tin tới node B, nó sử dụng thông tin vị trí của B để xác định hướng và truyền thông tin tới các neighbor trong phạm vi 1 hop, cho đến khi B nhận được thông tin, tạo ra một đường tuyến theo phương pháp on-demand tương tự như phương pháp Reactive.
Trong giao thức này, mỗi node gửi thông tin điều khiển về vị trí hiện tại của nó đến tất cả các node khác Tần suất gửi thông tin điều khiển được xác định dựa trên hiệu ứng khoảng cách và tỷ lệ di động.
Khi một node S muốn gửi thông điệp m đến node nhận R, nó sử dụng Bảng Vị trí (LT) để xác định vị trí của R Dựa trên thông tin này, S chọn các node láng giềng nằm trong hướng của R và chuyển tiếp thông điệp m Mỗi node này cũng thực hiện tương tự, tiếp tục chuyển tiếp thông điệp đến các node láng giềng của nó cho đến khi R nhận được thông điệp.
Như vậy, DREAM có một phương pháp cập nhật vị trí khá phức tạp, do đó giao thức này không thể hoạt động tốt trong những mạng lưới lớn
GPSR (Greedy Perimeter Stateless Routing) là giao thức định tuyến dựa vào thông tin vị trí (geographical routing protocol) được Karp xây dựng [3][4]
Giao thức định tuyến GPSR được thiết kế cho mạng không dây, sử dụng thông tin vị trí của các node lân cận và node đích để quyết định cách chuyển tiếp gói dữ liệu Giao thức này bao gồm hai phương pháp chuyển tiếp: greedy forwarding, được áp dụng khi có thể, và perimeter forwarding, được sử dụng khi greedy forwarding không khả thi.
Trong phương pháp GPSR, header của gói dữ liệu chứa thông tin vị trí của node đích, cho phép node đang forward gói dữ liệu lựa chọn hop kế tiếp dựa trên vị trí này Trong chế độ greedy, node thực hiện việc forward sẽ sử dụng thông tin vị trí của các node lân cận và node đích để tính toán khoảng cách Nó sẽ chọn node kế tiếp dựa trên khoảng cách ngắn nhất từ node đích đến các node lân cận, tiếp tục forward gói dữ liệu cho đến khi đến được node đích.
Thuật toán Greedy là một phương pháp hiệu quả trong việc chuyển tiếp gói tin trong mạng Ví dụ, khi nút x nhận một gói tin cần chuyển đến nút đích D, mà D không phải là hàng xóm 1 hop của x, nó sẽ chọn một nút hàng xóm để forward gói Trong trường hợp này, x chọn y vì khoảng cách từ y đến D là ngắn nhất Quá trình này tiếp tục cho đến khi gói tin đến D Ưu điểm của greedy forwarding là chỉ cần thông tin về các nút hàng xóm và đích, không cần biết thông tin của các nút khác trong mạng Phương pháp này cho phép các nút đưa ra quyết định cục bộ dựa trên vị trí của các hàng xóm, giúp nó linh hoạt hơn khi mạng thay đổi Để thu thập thông tin về các hàng xóm, GPSR sử dụng thuật toán beacon, trong đó các gói tin beacon được phát đi định kỳ, cung cấp thông tin vị trí và địa chỉ MAC của mỗi nút.
DỊCH VỤ VỊ TRÍ PHÂN CẤP HLS
Cells
HLS chia mạng thành các cell và nhóm chúng thành các vùng, mỗi cell và vùng được xác định bởi một ID duy nhất Việc phân chia này là cố định và được biết trước bởi tất cả các node Ví dụ, cell có thể được tổ chức theo hình lục giác đều để bao phủ khu vực với số lượng cell tối thiểu Mỗi node trong một cell có khả năng phát sóng gói dữ liệu đến tất cả các node thành viên trong cell đó, đạt được thông qua thiết kế cell với đường kính nhỏ hơn hoặc bằng tầm giao tiếp vô tuyến của node, hoặc bằng cách triển khai flooding trong toàn bộ cell.
Các cell được tổ chức theo cấu trúc phân cấp, bắt đầu từ các vùng level 1 được hình thành từ các cell liền kề Tiếp theo, các vùng level 1 này kết hợp với nhau để tạo thành vùng level 2, và quá trình này tiếp tục cho đến khi hình thành các vùng ở các level cao hơn Cuối cùng, một vùng bao phủ toàn bộ khu vực mạng sẽ được xác định, được gọi là vùng level cao nhất.
The hash function is applied by combining the node's ID with its current position, assigning a responsible cell (RC) to each node at every level The responsible cell is the one where the selected node serves as the location service.
Node A chọn một số lượng cell có thể trở thành responsible cell, dựa trên ID và vị trí của nó Để xác định vị trí server cho A, một node B khác tính toán số lượng candidate cell bằng cách sử dụng hàm hash dựa trên thông tin ID của A và vị trí hiện tại của B.
Gọi N là tập hợp tất cả các nodes, L là tập hợp các levels, X x Y là khu vực của một node và C là tập hợp các cells Vùng thuộc level l ∈ L, bao phủ vị trí pos ∈ X x Y, được định nghĩa một cách chính xác để xác định mối quan hệ giữa các thành phần trong cấu trúc dữ liệu này.
( , os):= c C| c là thành viên vùng level-l
Hàm hash F có thể được định nghĩa như sau:
( n l p , , os ) → c , Ở đây n∈N, pos ∈X x Y và c ∈ R(l,pos) Hàm hash sẽ được xác định cụ thể với các công thức được thể hiện trong phần mô phỏng 4.1.1 tiếp theo
Cấu trúc phân nhánh sử dụng hàm hash được minh họa qua ví dụ về candidate tree, thể hiện các candidate cell có thể trở thành responsible cell cho node A trong một vùng chia thành 3 level khác nhau Các candidate cell được kết nối theo hình mũi tên, tạo thành một cấu trúc giống như cây, với điểm gốc là một responsible cell tiềm năng ở level cao nhất, gần trung tâm khu vực Candidate tree có thể khác nhau cho từng node và được tính toán dựa trên hàm hash và ID của node Để xác định candidate cell trở thành responsible cell, node A tính toán vùng tại level-1 chứa vị trí của nó và chọn nhánh của cây với điểm kết thúc trong r.
Tất cả các cell trong nhánh này đều là responsible cells, như thể hiện trong hình 3.2, với các RC và vùng được đánh dấu rõ ràng theo cấu trúc phân nhánh hình cây.
Hình 3.2 Candidate tree với cấu trúc phân nhánh đến level-3
Hiệu quả của HLS phụ thuộc vào hàm hash được sử dụng để tính toán các ô chịu trách nhiệm Việc tối ưu hóa hàm hash theo môi trường của mạng MANET là điều cần thiết và sẽ là một vấn đề quan trọng để xem xét trong tương lai.
Cập nhật vị trí
Có 2 phương pháp khác nhau để cập nhật vị trí server vị trí là: cập nhật vị trí trực tiếp và cập nhật vị trí gián tiếp Nếu chúng ta nói node cập nhật vị trí của responsible cell, điều đó có nghĩa là một gói dữ liệu được gửi đến responsible cell và được lưu trữ tại node bất kỳ trong hoặc gần cell mà ở đó node trở thành server vị trí Điều này cho phép các thông tin cập nhật sau đó có thể được chuyển đến các node khác ở trong cùng 1 cell và cell cũng có thể bao gồm nhiều server vị trí cho 1 node Để node cập nhật location services của chính nó theo dạng cập nhật vị trí trực tiếp, node tính toán responsible cell của chính nó được trình bày trong phần 3.1.2 Thông tin cập nhật vị trí được gửi đến tất cả các RCs tại cùng 1 thời điểm Đây gọi là cập nhật trực tiếp bởi vì server vị trí trực tiếp nắm bắt các thông tin vị trí thay đổi của node Trong hình 3.4, thông tin vị trí trong RCs được miêu tả là ký hiệu dấu mũi tên tại vị trí của node Hình 3.4(a) hiển thị thông tin của responsible cell sau khi cập nhật RCs tại tất cả các level đều chứa đựng thông tin chính xác về vị trí của node đó Tất cả các RCs đều phải cập nhật bất cứ khi nào node di chuyển (Hình 3.4(b)) Điều này có thể thực hiện dễ dàng nếu các location services là gần nhau, tuy nhiên việc cập nhật RCs tại các level cao hơn sẽ gây ra các vấn đề về tiêu tốn tài nguyên mạng hoặc xung đột trên đường truyền
Hình 3.3: Ví dụ về responsible cells của 1 node
Việc giảm lưu lượng thông tin có thể đạt được bằng cách sử dụng phương pháp cập nhật vùng ở mức thấp hơn liền kề của node mà không cần biết chính xác vị trí của nó Hình 3.5(a) minh họa rằng chỉ cần cập nhật thông tin tại level-1, trong khi các level-2 và level-3 không cần cập nhật Điều này dẫn đến việc tạo ra cách cập nhật thông tin gián tiếp trong dịch vụ định vị Trong môi trường lý tưởng, một server vị trí tại level-n chỉ cần cập nhật khi một node di chuyển đến vùng level-(n-1) khác Do đó, cell chịu trách nhiệm tại level-1 chỉ cập nhật khi node di chuyển đến đường biên của level-1 (Hình 3.5(b)) Các cell ở các level cao hơn chỉ thực hiện cập nhật khi có sự thay đổi tại các level thấp hơn kế tiếp (Hình 3.5(c), 3.5(d)) Như vậy, phần lớn lưu lượng thông tin cập nhật chỉ diễn ra trong phạm vi một vài hops, trong khi ở khoảng cách xa, việc cập nhật xảy ra ít hơn.
(a) Cập nhật trực tiếp (b) Tất cả các RC đều phải cập nhật
Hình 3.4: Cập nhật vị trí trực tiếp
(a) Cập nhật gián tiếp (b) Cập nhật RC tại level-1
(c) Cập nhật RC tại level-2, thay đổi RC (d) Cập nhật RC tại level-3, thay tại level-1 đổi RC tại level-1 và level-2
Hình 3.5 Cập nhật vị trí gián tiếp
Handovers
Vị trí của node xác định server hoàn toàn phụ thuộc vào vị trí của nó Khi node rời khỏi cell chịu trách nhiệm, nó sẽ không còn lưu trữ thông tin về server vị trí.
RC này Gói dữ liệu handover được chuyển đến node ở trong hoặc gần với cell, nơi mà sẽ trở thành một server vị trí mới
Không thể đảm bảo rằng một cell sẽ luôn chứa một node hoặc thông tin vị trí do các sự cố như server vị trí thất bại, gói dữ liệu bị hủy do xung đột trên đường truyền hoặc các vấn đề khác Đây là một thách thức cần được giải quyết trong tương lai.
TRIỂN KHAI THỰC HIỆN VỚI NS-2 (PHIÊN BẢN 2.33)
Perl
Bài viết trình bày một dịch vụ vị trí phân cấp cho mạng MANET, mô tả giải thuật HLS và đề xuất các hướng mở rộng Dịch vụ này sử dụng cấu trúc phân cấp theo khu vực để tính toán server vị trí cho các node khác, trong đó mật độ server vị trí phụ thuộc vào khoảng cách giữa các node Độ phức tạp yêu cầu thông tin vị trí cũng tương ứng với khoảng cách giữa node yêu cầu và node đích Mạng ad-hoc được chia thành các cell nhỏ, được tổ chức theo nhiều mức độ phân cấp khác nhau Thông qua hàm hash dựa trên ID và vị trí của node, mỗi node có thể xác định tập hợp các cell lưu trữ thông tin vị trí của nó Dịch vụ không chọn node đặc biệt làm server vị trí, mà chỉ chọn các vùng vật lý chứa server Nếu một node di chuyển ra khỏi cell, thông tin vị trí sẽ được chuyển giao cho node khác trong cell Yêu cầu thông tin vị trí được gửi đến các tập cell khác nhau, và hàm hash cần đảm bảo giao giữa các tập là khác rỗng để đảm bảo thông tin đến được server vị trí.
Dịch vụ vị trí phân cấp (HLS) đã được so sánh với dịch vụ vị trí GLS thông qua mô phỏng nhiều kịch bản sử dụng định tuyến GPSR Kết quả cho thấy HLS có tỷ lệ thành công cao hơn GLS, đặc biệt khi mật độ node đạt từ 50 node/km², HLS đạt tỷ lệ thành công lên đến 98%.
Khi mật độ node thấp, các yêu cầu thường thất bại do không tìm thấy dịch vụ vị trí Ngược lại, với mật độ cao hơn, HLS có khả năng phát hiện dịch vụ vị trí trong hầu hết các trường hợp Tuy nhiên, vẫn tồn tại một số yêu cầu vị trí chưa được đáp ứng.
