TỔNG QUAN VỀ ĐỊNH TUYẾN TRONG MẠNG MANET PHÂN C Ụ M
T ổ ng quan v ề m ạ ng MANET
Mạng MANET (Mobile Ad hoc Network) là một tập hợp các nút di động không dây có khả năng trao đổi dữ liệu linh hoạt mà không cần trạm cơ sở cố định hoặc mạng có dây Mỗi nút di động có phạm vi truyền hạn chế, do đó cần sự hỗ trợ từ các nút lân cận để chuyển tiếp gói dữ liệu Trong một ví dụ, gói tin từ một máy tính cần được chuyển tới một điện thoại thông minh không nằm trong phạm vi truyền của nó, yêu cầu sự giúp đỡ từ các nút trung gian Để thực hiện việc này, các nút mạng cần áp dụng giao thức định tuyến phù hợp cho mạng MANET.
Hình 1.1 Một ví dụ của mạng MANET
Thuật ngữ “Ad hoc” trong mạng không dây chỉ một mạng không có cơ sở hạ tầng cố định, nơi hình thành mạng được tạo ra bởi các nút mạng Chế độ “Ad hoc” của chuẩn IEEE 802.11 cho phép thiết lập mạng đơn chặng Tuy nhiên, các mạng di động không dây kiểu không cấu trúc (MANET) đã phát triển khái niệm “Ad hoc” đa chặng, cho phép một nút mạng định tuyến và chuyển tiếp gói tin từ nút mạng khác Điều này có nghĩa là đường truyền gói tin từ nguồn đến đích có thể bao gồm các nút trung gian, mà sẽ đọc thông tin trong phần header của gói tin và chuyển tiếp chúng tới chặng tiếp theo trong con đường đã được hình thành.
Trong mạng MANET, các nút kết nối và trao đổi thông tin trong một khoảng thời gian, đồng thời vẫn có khả năng di chuyển Điều này đòi hỏi mạng phải có khả năng truyền dữ liệu hiệu quả ngay cả khi cấu trúc mạng thay đổi liên tục Các nút mạng cần có cơ chế tự tổ chức để thiết lập các đường truyền dữ liệu mà không cần sự hỗ trợ từ bên ngoài Trong mô hình này, mỗi nút có thể hoạt động như một nút đầu cuối để chạy ứng dụng của người sử dụng hoặc như một bộ định tuyến để chuyển tiếp các gói tin đến các nút khác.
Mạng MANET là một mạng không dây độc lập, hoạt động mà không cần hạ tầng mạng cơ sở, cho phép các thiết bị di động giao tiếp qua truyền thông đa chặng Các thiết bị trong mạng vừa là đầu cuối vừa là bộ định tuyến, mang lại cho MANET những đặc điểm nổi bật.
Cấu trúc của mạng MANET thường xuyên thay đổi do tính chất di chuyển ngẫu nhiên của các nút mạng, dẫn đến việc thêm hoặc mất các kết nối hai chiều và một chiều vào những thời điểm không xác định trước.
Các liên kết không dây thường có chất lượng băng thông hạn chế hơn so với các liên kết có dây, do ảnh hưởng của cơ chế đa truy cập, suy giảm tín hiệu và nhiễu Kết quả là, băng thông thực tế của các liên kết không dây thường thấp hơn nhiều so với tốc độ truyền tối đa lý thuyết của môi trường truyền không dây.
Trong mạng MANET, các nút di động như bộ cảm biến, điện thoại thông minh và máy tính xách tay thường có tài nguyên hạn chế So với các máy tính trong mạng có dây và không dây truyền thống, những thiết bị này thường gặp khó khăn về tốc độ xử lý, dung lượng bộ nhớ và nguồn năng lượng từ pin, ảnh hưởng đến hiệu suất hoạt động của chúng.
Mạng không dây di động có độ bảo mật thấp hơn so với mạng có dây do dễ bị tác động từ các nguồn gây hại về an ninh Các kỹ thuật như nghe lén, giả mạo và tấn công từ chối dịch vụ thường dễ dàng được triển khai trong mạng MANET, làm tăng nguy cơ mất an ninh hơn so với mạng có dây truyền thống.
Các đặc điểm của mạng MANET có ảnh hưởng lớn đến hiệu năng của nó Để triển khai mạng MANET trong thực tế, cần giải quyết các thách thức phát sinh từ những đặc điểm này, bao gồm khả năng truyền dữ liệu và định tuyến hiệu quả khi kích thước mạng thay đổi, đảm bảo chất lượng dịch vụ (QoS) cho các ứng dụng, chuyển đổi một số dịch vụ từ mô hình client-server, tiết kiệm năng lượng pin để kéo dài thời gian hoạt động của các nút mạng và toàn mạng, đảm bảo an ninh mạng, khả năng hợp tác giữa các nút mạng, và khả năng tự tổ chức của mạng.
Mạng MANET ngày nay có nhiều ứng dụng quan trọng trong đời sống, kinh tế và xã hội, đặc biệt trong các tình huống cần triển khai mạng nhanh chóng và linh động Mạng này được sử dụng rộng rãi từ thương mại, quân sự, khẩn cấp, đến gia đình, văn phòng, giáo dục, giao thông và cảm biến Trong thương mại, người dùng có thể chia sẻ dữ liệu giữa các thiết bị di động trong các cuộc họp mà không cần hạ tầng mạng cố định, tạo thành mạng tạm thời cho truyền thông dữ liệu Ngoài ra, kết nối Internet từ một thiết bị cũng có thể được chia sẻ qua mạng MANET Ứng dụng của mạng MANET trong quân đội cho phép các lính và phương tiện quân sự như xe tăng, máy bay, tàu chiến kết nối và trao đổi thông tin một cách linh hoạt trên chiến trường, không cần hạ tầng mạng cố định.
Trong các vùng chịu ảnh hưởng của thiên tai, hạ tầng truyền thông có thể bị phá hủy hoàn toàn Để khắc phục tình trạng này, các phương tiện như xe cảnh sát, xe cứu hỏa và xe cứu thương có thể được trang bị thiết bị truyền nhận không dây, biến chúng thành các thiết bị đầu cuối di động trong mạng MANET Nhân viên cứu hộ cũng có thể mang theo thiết bị đầu cuối di động, tạo thành một mạng MANET tạm thời để trao đổi thông tin Cấu hình mạng này có thể thay đổi theo thời gian, và các thiết bị đầu cuối không chỉ gửi và nhận thông tin mà còn có khả năng chuyển tiếp thông tin, đóng vai trò như các bộ định tuyến.
Mỗi thiết bị thông minh trong gia đình, điện thoại di động và máy tính trong văn phòng hay trường học đều có thể trở thành nút mạng trong một mạng MANET tạm thời Mạng này không cần hạ tầng mạng cố định, phục vụ cho các ứng dụng chia sẻ thông tin, truyền dữ liệu multimedia, và quản lý ngôi nhà thông minh cũng như lớp học thông minh.
Trong quản lý và hỗ trợ giao thông, mỗi phương tiện được xem như một nút mạng di động trong mạng MANET tạm thời, giúp trao đổi thông tin về tình trạng giao thông Mạng này hỗ trợ tìm đường tránh tắc nghẽn và theo dõi các thiết bị tham gia giao thông, góp phần nâng cao hiệu quả quản lý giao thông.
Cảm biến là thiết bị nhỏ gọn, giá thành thấp, tiết kiệm năng lượng và có khả năng truyền thông không dây cùng xử lý dữ liệu cục bộ Mạng MANET có thể được hình thành từ các nút cảm biến, cho phép chúng hợp tác thực hiện nhiệm vụ như giám sát môi trường (không khí, đất, nước), theo dõi hành vi và dân số động thực vật, dò tìm động chấn, theo dõi tài nguyên, và thực hiện trinh thám quân sự.
V ấn đề b ảo trì thông tin đị nh tuy ế n trong m ạ ng MANET phân c ụ m
Phân cụm là chiến lược hiệu quả cho mạng ad hoc di động (MANET), giúp cải thiện khả năng mở rộng và giảm kích thước bảng định tuyến, từ đó giảm chi phí duy trì thông tin định tuyến Nó cũng tăng tính sẵn có của thông tin mạng bằng cách sao chép dữ liệu giữa các nút trong các cụm khác nhau Khi truyền thông tin kiểu quảng bá hoặc multicast, phân cụm cho phép lan truyền thông tin một cách có chọn lọc, giảm thiểu thông điệp dư thừa Hơn nữa, phân cụm hỗ trợ quản lý tài nguyên hiệu quả để đáp ứng yêu cầu chất lượng dịch vụ (QoS) Nghiên cứu đã xem xét nhiều kỹ thuật phân cụm trong MANET, tập trung vào việc xây dựng các cụm để quản lý tính di động và tối ưu hóa năng lượng Đề tài này giả định rằng mạng đã được phân cụm, nhằm nghiên cứu các kỹ thuật triển khai để quản lý trạng thái động của các cụm, cải thiện hiệu suất ứng dụng trong mạng MANET phân cụm.
Việc duy trì trạng thái của các cụm trong mạng MANET liên quan đến hai hoạt động chính: thu thập và phân phối thông tin Trong giai đoạn thu thập, các nút thu thập thông tin trạng thái từ cụm nội bộ, trong khi ở giai đoạn phân phối, thông tin được chia sẻ với các cụm khác Thách thức lớn trong mạng MANET là tính di động của các nút, dẫn đến sự thay đổi thường xuyên của trạng thái cụm và gia tăng chi phí cho các hoạt động này Một chiến lược bảo trì hiệu quả cần cân bằng tải công việc và mức tiêu thụ năng lượng, đồng thời tối thiểu hóa chi phí và ghi nhận các thay đổi một cách kịp thời Để quản lý thông tin trạng thái, giao thức bảo trì cần thực hiện các hoạt động thu thập và phân phối Trong nghiên cứu này, kết nối logic giữa các cụm được coi là thông tin trạng thái, với hai cụm được xem là có kết nối nếu chúng liền kề và có thể định tuyến trực tiếp thông điệp qua một nút biên Các cụm và kết nối giữa chúng có thể được mô hình hóa như một lớp phủ trên mạng MANET, trong đó các cụm là đỉnh và các kết nối là các cạnh của lớp phủ.
Một cách tiếp cận hiệu quả để giải quyết bài toán bảo trì trạng thái trong mạng MANET phân cụm là giao trách nhiệm cho nút đầu cụm, như được đề xuất trong nghiên cứu [1] Nút đầu cụm sẽ duy trì thông tin của các cụm lân cận và chia sẻ thông tin với các nút đầu cụm khác, đồng thời quản lý các yêu cầu định tuyến liên cụm Các nút khác trong cụm chỉ cần duy trì một con đường đến nút đầu cụm của chúng Bài viết này sẽ nghiên cứu chiến lược bảo trì mạng phủ phân cụm dựa trên nút đứng đầu, gọi là CWHO (Cluster-Based With Head Overlay), nhằm so sánh với các chiến lược bảo trì khác.
Trong thiết kế chiến lược bảo trì thông tin cho mạng MANET, có nhiều cách tiếp cận khác nhau Một trong những phương pháp là chiến lược phân phối đầy đủ, không dựa vào nút đứng đầu, mà trong đó mọi nút đều có trách nhiệm chia sẻ thông tin về các cụm lân cận Phương pháp này cho phép mỗi nút thực hiện các hoạt động định tuyến liên cụm bằng cách chia sẻ thông tin trạng thái của tất cả các cụm trong mạng Do đó, bài viết này cũng nghiên cứu đề xuất triển khai chiến lược bảo trì thông tin định tuyến trong mạng phủ phân cụm không có nút đứng đầu, được gọi là CWOHO (Cluster-Based WithOut Head Overlay).
Hai chiến lược bảo trì thông tin trạng thái cục bộ của các cụm trong mạng có ưu điểm và nhược điểm riêng Chiến lược CWHO đơn giản và hiệu quả trong nhiều tình huống, nhưng có thể gây ra mất cân bằng tải và tiêu thụ năng lượng cao Ngược lại, chiến lược CWOHO giúp tránh những vấn đề này nhưng có chi phí bảo trì cao Giữa hai chiến lược này, chiến lược Phân cụm với thông tin nút lân cận (CNI) cung cấp một phương pháp thu thập thông tin phân tán mà không chia sẻ với toàn bộ mạng, chỉ duy trì thông tin về các cụm lân cận Nghiên cứu giả định rằng mỗi nút có kiến thức về cấu trúc kết nối mạng, cho phép định tuyến liên cụm thông qua quyết định tại mỗi cụm trung gian.
Một chiến lược bảo trì thông tin định tuyến không thể áp dụng đồng nhất cho mọi điều kiện và mô hình di động trong mạng Trong trường hợp các nút di chuyển chậm, chiến lược bảo trì với nút đầu cụm có thể mang lại hiệu suất tốt Ngược lại, với mạng có tính cơ động cao, cần xem xét chiến lược bảo trì phân tán Để đánh giá tác động của tính di động của nút, nghiên cứu này sẽ phân tích hiệu năng của ba chiến lược bảo trì dựa trên hai mô hình di động khác nhau: Random Waypoint và Manhattan Grid thông qua phương pháp mô phỏng.
Đề tài này sẽ thực hiện các công việc sau: (a) Nghiên cứu toàn diện về bảo trì trạng thái trong mạng MANET phân cụm thông qua việc triển khai chiến lược bảo trì với nút đầu cụm CWHO, chiến lược phổ biến nhất hiện nay; (b) Triển khai chiến lược bảo trì CWOHO, nơi các nút kết hợp thông tin từ tất cả các nút biên để xác định khả năng kết nối với các cụm lân cận, và thông tin này được quảng bá cho mọi nút trong mạng; (c) Triển khai chiến lược CNI, tìm kiếm điểm giữa giữa hai chiến lược CWHO và CWOHO; (d) Sử dụng mô phỏng để đánh giá ba chiến lược bảo trì trong các điều kiện mạng khác nhau, từ đó cung cấp cái nhìn sâu sắc cho các chiến lược thiết kế bảo trì thông tin định tuyến.
M ộ t s ố k ỹ thu ậ t phân c ụ m trong m ạ ng MANET
Kỹ thuật phân cụm là phương pháp hiệu quả để giảm chi phí định tuyến và kéo dài thời gian sống của các nút trong mạng Phân cụm phân tán, được nghiên cứu chủ yếu trong mạng ad hoc và cảm biến không dây, dựa trên lý thuyết đồ thị thống trị Tập thống trị của đồ thị G = (V, E) là tập con S ⊆ V, trong đó mọi đỉnh v ∈ V đều nằm trong S hoặc liền kề với một đỉnh của S Một đỉnh trong S được coi là thống trị chính nó và các đỉnh lân cận Các cạnh bị thống trị là những cạnh có ít nhất một đầu mút nằm trong S, trong khi các cạnh còn lại được gọi là cạnh tự do Nhiều kỹ thuật đã được đề xuất để chọn tập thống trị S, bao gồm tập thống trị độc lập (IDS), tập thống trị kết nối (CDS), và tập thống trị kết nối yếu (WCDS) Trong IDS, không có hai đỉnh nào trong S liền kề nhau, trong khi tất cả các đỉnh trong CDS đều được kết nối, dẫn đến số lượng cụm trong IDS ít hơn so với CDS Tuy nhiên, khả năng kết nối của các nút đầu cụm trong CDS lại mang lại lợi thế cho các ứng dụng truyền thông kiểu quảng bá WCDS là một biến thể của CDS, cho phép nới lỏng yêu cầu kết nối trực tiếp giữa các nút thống trị lân cận.
Phương pháp DDR trong nghiên cứu [9] giới thiệu một kỹ thuật phân tán mới để phân cụm các nút thành các vùng không chồng lấp Khác với việc chọn một tập hợp con các nút như trong tập thống trị, DDR sử dụng một thuật toán phân tán để xây dựng một rừng Các cây trong rừng được hình thành thông qua việc trao đổi các thông điệp báo hiệu định kỳ giữa các nút Mỗi cây tạo thành một vùng riêng biệt và được gán một định danh vùng (zone-ID) thông qua thuật toán đặt tên vùng Các vùng này được kết nối với nhau thông qua các nút biên, không thuộc cùng một cây nhưng nằm trong cùng một phạm vi truyền thông.
Một số mạng ad hoc hỗn độn sử dụng nút báo hiệu để phân cụm các nút trong mạng, với các nút này cố gắng thu hút các nút lân cận nhằm tạo thành cụm Phương pháp LABAR nghiên cứu mạng hỗn độn với chỉ một tập hợp các nút G có thông tin vị trí chính xác, trong khi các nút còn lại là nút S Nút G đóng vai trò là nút báo hiệu, tạo thành các vùng bằng cách lôi kéo các nút S xung quanh Phương pháp BEAD nghiên cứu mạng ad hoc phân cấp ba tầng, trong đó các nút di động (MN) ở tầng thấp nhất, tiếp theo là các nút chuyển tiếp (FN) và các điểm truy cập (AP) Các thông điệp báo hiệu định kỳ từ FN và AP được quét bởi MN để xác định nút cha tốt nhất trong mạng Ngoài ra, có một phương pháp khác cũng là kỹ thuật phân cụm dựa trên nút báo hiệu.
Trong mạng MANET, các nút có thể được phân nhóm theo mối quan hệ logic hoặc cách thức hoạt động Các ứng dụng như khắc phục thảm họa hay triển khai quân sự thường yêu cầu sự hợp tác giữa các nhóm nhỏ nút trong mạng Các thành viên trong nhóm có chung mối quan tâm và di chuyển cùng nhau với tốc độ và hướng tương tự Dựa trên đặc điểm này, các nút vật lý có thể được chia thành nhiều nhóm nhỏ thông qua kỹ thuật phân cụm dựa trên nhóm.
Một kỹ thuật phân cụm vật lý phổ biến trong các mạng có nút hỗ trợ GPS là chia nhỏ triển khai thành các lưới địa lý Kỹ thuật này yêu cầu mỗi nút phải nắm rõ thông tin về hình dạng và phân vùng của khu vực triển khai Thông tin này giúp các nút xác định ranh giới của cụm và cụm chứa chúng So với tính di động của nhóm, kỹ thuật này cho phép tính di động của các nút diễn ra ngẫu nhiên, trong khi các phân vùng địa lý lại được cố định.
Ngoài ra, còn nhiều kỹ thuật phân cụm khác được nghiên cứu, đặc biệt trong các mạng không dây Nghiên cứu [14] đã khảo sát các kỹ thuật phân cụm trong mạng MANET, và những kỹ thuật này được tổng kết chi tiết trong Bảng 2.1.
Kỹ thuật phân cụm Đặc điểm Giao thức
Tập thống trị Phân cụm logic bằng cách chọn một tập con các nút trong mạng
Cụm phân tán Phân cụm logic dưới dạng phân tán DDR
Dựa trên báo hiệu Phân cụm logic sử dụng nút báo hiệu
Dựa trên nhóm Phân cụm vật lý dựa trên mối quan hệ logic giữa các nút HSR, LANMAR Phân vùng địa lý
Phân cụm vật lý sử dụng thông tin vị trí và hình trạng mạng
Bảng 2.1 Một số kỹ thuật phân cụm tiêu biểu trong mạng MANET
M ộ t s ố k ỹ thu ậ t b ả o trì thông tin c ụ m trong m ạ ng MANET
Trong mạng có cấu hình động, thông tin trạng thái của các cụm như kết nối, băng thông và kích thước có thể thay đổi thường xuyên Các chiến lược bảo trì thông tin mạng đã được nghiên cứu và đề xuất, có thể chia thành hai nhóm chính: nhóm chiến lược dựa trên nút đứng đầu và nhóm chiến lược phân tán Bài viết sẽ trình bày ngắn gọn về các giao thức triển khai của những chiến lược này.
CBRP Dựa trên nút đứng đầu mỗi cụm thực hiện nhiệm vụ kết nối và định tuyến liên cụm
LABAR, BEAD Sử dụng nút đặc biệt (G-node trong LABER) để bảo trì kết nối và định tuyến cho các vùng
CEDAR và MCEDAR sử dụng các nút lõi để duy trì thông tin về các cụm, trong khi GLIDER áp dụng topo mạng cảm biến phân tán cho từng nút nhằm hỗ trợ quy trình định tuyến hiệu quả.
LANMAR Mỗi nút bảo trì thông tin định tuyến về các nút lân cận và tới các nút mốc
DDR, HARP Mọi nút bảo trì thông tin về khu vực và các vùng lân cận của mình
ZHLS Mọi nút bảo trì thông tin nội bộ về các nút hiện có trong vùng của chúng và kết nối của các vùng
Bảng 2.2 Một số kỹ thuật bảo trì lớp phủ trong mạng phân cụm
1.4.1 Chi ến lượ c d ựa trên nút đứng đầ u
Trong CBRP, các nút đầu cụm lưu trữ thông tin về các nút thành viên trong cụm nội bộ và khả năng kết nối với các cụm lân cận Các nút còn lại duy trì các đường dẫn tới nút đầu cụm của chúng, giúp tối ưu hóa chi phí quảng bá tìm đường tới nút đích.
Trong CEDAR, các nút lõi được chọn thông qua thuật toán tập thống trị phân tán tối thiểu (MDS) nhằm duy trì thông tin lớp phủ cho các cụm ở khoảng cách xa trong mạng Để đảm bảo định tuyến QoS, mỗi nút lõi duy trì cấu trúc liên kết cục bộ và thông tin về băng thông sẵn có của các liên kết bền vững ở khoảng cách xa, trong khi không bảo trì các liên kết băng thông thấp không hữu ích CEDAR áp dụng hai kỹ thuật lan truyền: sóng tăng di chuyển chậm và sóng giảm di chuyển nhanh để cập nhật băng thông có sẵn trên các nút lõi Các nút lõi sử dụng thông tin về các liên kết bền vững băng thông cao để tính toán đường QoS từ miền của nút nguồn đến miền của nút đích.
MCEDAR là một thuật toán multicast được phát triển từ thuật toán CEDAR, sử dụng các nút lõi để duy trì cấu trúc lưới gọi là mgraph cho nhóm multicast Cấu trúc mgraph được hình thành thông qua việc duy trì các đường dự phòng giữa các nút lõi, giúp đảm bảo khả năng phục hồi nhanh chóng khi có lỗi liên kết xảy ra trong mạng MCEDAR gán cho mỗi mgraph một hệ số độ mạnh để điều khiển kết nối giữa các nút lõi, từ đó cải thiện hiệu quả của ứng dụng.
1.4.2 Chi ến lượ c phân tán m ộ t ph ầ n
Một phương pháp để duy trì trạng thái của các cụm trong mạng là phân tán thông tin đến mọi nút Các nghiên cứu đã đề xuất nhiều giao thức như GLIDER, LANMAR, DDR và HARP Trong giao thức GLIDER, các nút mốc phân vùng trường cảm biến thành các tấm lợp có thể định tuyến theo địa lý, mỗi tấm lợp là một tế bào Voronoi được hình thành từ kỹ thuật kết hợp mốc Voronoi phân tán (LVC) Phức hợp đối kháng của LVC, gọi là tam giác tổ hợp Delaunay (CDT), phản ánh sự kết nối giữa các tế bào Voronoi, cung cấp cái nhìn tổng quát về cấu trúc mạng Mỗi nút mốc sử dụng thông tin này để tính toán cây đường đi ngắn nhất và tích hợp vào tế bào Voronoi của mình, từ đó mỗi nút trong GLIDER duy trì thông tin để thực hiện thao tác định tuyến liên vùng giữa các tế bào.
Giao thức HARP áp dụng chiến lược bảo trì phân tán, sử dụng DDR làm giao thức cơ sở để phân vùng các nút thành những vùng không chồng lấp DDR cho phép các nút duy trì thông tin định tuyến đến các nút trong cùng vùng và thông tin về các vùng lân cận Trong HARP, các nút sử dụng thông tin này để định tuyến gói dữ liệu trong vùng theo cách tìm đường trước, trong khi đối với định tuyến liên vùng, chúng áp dụng phương pháp tìm đường theo yêu cầu, bao gồm cả kỹ thuật khám phá và bảo trì đường.
Các giao thức như LANMAR và GLIDER sử dụng các nút mốc để thu thập thông tin tổng thể về các cụm, trong khi DDR và HARP chỉ duy trì thông tin về các cụm lân cận mà không chia sẻ với các nút bên ngoài.
1.4.3 Chi ến lượ c phân tántoàn ph ầ n
Giao thức định tuyến ZHLS sử dụng chiến lược bảo trì phân tán toàn phần, trong đó mỗi nút duy trì topo cấp thấp chứa thông tin kết nối với các nút khác trong khu vực của nó Đồng thời, topo cấp vùng cung cấp thông tin về kết nối giữa các vùng trong toàn mạng Mỗi nút áp dụng thông tin cấp nút để định tuyến trong vùng tương ứng, trong khi thông tin cấp vùng được sử dụng cho định tuyến liên vùng.
Giao thức ZHLS cho phép các nút trong mạng thu thập thông tin về các cụm lân cận thông qua việc trao đổi dữ liệu trong cụm Các nút biên sẽ quảng bá thông tin này ra toàn mạng, nhưng để giảm tải lưu lượng, quảng bá chỉ diễn ra khi có sự thay đổi trong cụm lân cận và loại bỏ các thông điệp dư thừa từ các nút biên khác nhau Nghiên cứu này cũng đề xuất chiến lược bảo trì CWOHO, hoạt động tương tự như ZHLS nhưng với cách triển khai khác.
T ổ ng k ết Chương 1
Mạng MANET khác biệt rõ rệt so với mạng không dây truyền thống với cấu trúc động, chất lượng liên kết không ổn định và hạn chế về năng lượng pin của các nút mạng Mặc dù có độ bảo mật vật lý không cao, mạng MANET đã được ứng dụng rộng rãi trong nhiều lĩnh vực của đời sống, kinh tế và xã hội.
Phân cụm là một chiến lược hiệu quả để cải thiện tính động và khả năng mở rộng của mạng ad hoc di động (MANET) Các giao thức định tuyến dựa trên phân cụm có khả năng mở rộng tốt hơn so với giao thức định tuyến phẳng, đồng thời tăng cường tính sẵn sàng của thông tin mạng, như vị trí của các nút di động Trong quá trình truyền thông tin kiểu quảng bá hoặc đa điểm, phân cụm cho phép lan truyền thông tin một cách có chọn lọc, giảm thiểu thông điệp quảng bá dư thừa Hơn nữa, phân cụm giúp quản lý tài nguyên hiệu quả thông qua việc chia sẻ và dự trữ tài nguyên có kiểm soát, đáp ứng các yêu cầu chất lượng dịch vụ (QoS) của ứng dụng Nhiều kỹ thuật phân cụm đã được nghiên cứu và đề xuất, có thể chia thành các nhóm như: phân cụm dựa trên tập thống trị, phân cụm phân tán, phân cụm dựa trên cơ chế báo hiệu, phân cụm dựa trên nhóm và phân cụm theo phân vùng địa lý.
Trong mạng có cấu hình động, thông tin trạng thái của các cụm như kết nối, băng thông và kích thước có thể thay đổi thường xuyên Đã có nhiều chiến lược bảo trì thông tin mạng được nghiên cứu và đề xuất, trong đó có thể chia thành hai nhóm: nhóm chiến lược dựa trên nút đứng đầu và nhóm chiến lược sử dụng phương pháp phân tán.
Chương này trình bày ba chiến lược bảo trì thông tin định tuyến quan trọng trong mạng MANET phân cụm, bao gồm: chiến lược bảo trì dựa trên nút đứng đầu, chiến lược bảo trì phân tán toàn phần và chiến lược bảo trì phân tán một phần.
CHI ẾN LƯỢ C B ẢO TRÌ THÔNG TIN ĐỊ NH TUY Ế N TRONG
Xây d ự ng l ớ p ph ủ d ự a trên m ạ ng phân c ụ m
Chương này sẽ trình bày ba chiến lược bảo trì thông tin trong các mạng MANET dựa trên cụm Để đảm bảo tính tổng quát, kết nối giữa các cụm được chọn làm thông tin trạng thái, vì nhiều giao thức định tuyến sử dụng thông tin này để nâng cao hiệu suất Kết quả thu được có thể áp dụng để bảo trì các thông tin trạng thái khác của cụm như băng thông và kích thước cụm Các thuật ngữ và ký hiệu được sử dụng trong chương này được liệt kê trong Bảng 2.1.
Kí hiệu/Thuật ngữ Định nghĩa
ClusterID / CellID Định danh cụm
HopCount / MinHops Số chặng (tối thiểu) đểđi tới một ClusterID
NextHopNgh Định danh nút của chặng kế tiếp lân cận
RegNghInfo Gói yêu cầu thông tin từ các nút lân cận 1 chặng
NghInfo Gói trả lời thông tin của các nút lân cận 1 chặng
NbdClusterInfo Gói lan truyền ClusterID của các cụm được kết nối MeshInfo Gói chứa thông tin về các cụm được kết nối
HeadInfo Gói để chọn nút đứng đầu trong một cụm
RoutingTable Bảng định tuyến tới một cụm lân cận
MeshStructure Bảng chứa kết nối logic giữa các cụm
RouteToHead Bảng được sử dụng để tìm tới nút đứng đầu
RouteToNbd-Cluster Bảng được sử dụng để nút đứng đầu tìm tới cụm lân cận
Bảng 2.1 Một số kí hiệu và thuật ngữ
Chương này bắt đầu với việc trình bày cách thực hiện chiến lược bảo trì phân tán toàn phần, đồng thời nêu rõ sự khác biệt giữa giao thức CWOHO và giao thức ZHLS Tiếp theo, nội dung sẽ đề cập đến việc thực hiện chiến lược bảo trì dựa trên nút đứng đầu Cuối cùng, chương sẽ giới thiệu cách triển khai một chiến lược bảo trì phân tán một phần Lưu ý rằng các phương pháp này chỉ là một trong nhiều cách triển khai có thể và được giới thiệu để tạo cơ sở cho nghiên cứu so sánh về ba chiến lược bảo trì trong phần tiếp theo.
Cụm Y được xem là lân cận của cụm X nếu tồn tại một nút n1 trong X kết nối với một nút trong Y, với n1 được gọi là nút biên hoặc nút cổng của cụm X Các nút biên này có vai trò quan trọng trong việc kết nối các cụm khác trong mạng Hình 2.1 minh họa cấu trúc lưới của lớp phủ được hình thành từ việc kết nối các cụm Mỗi cụm được xác định bởi một định danh duy nhất, gọi là ClusterID, và đại diện cho một đỉnh trong lớp phủ kết nối, trong khi các nút biên đảm nhiệm chức năng chuyển tiếp cho truyền thông giữa các cụm.
Hình 2.2 Phân tầng các kỹ thuật bảo trì và phân cụm
Các nút trong mạng có thể được phân cụm bằng bất kỳ thuật toán phân cụm nào đã được đề cập Nghiên cứu này giả định rằng khu vực triển khai được chia thành các ô lưới địa lý cố định, với mỗi cụm được xác định bằng một mã định danh duy nhất Mỗi nút sẽ lưu trữ thông tin về ClusterId của cụm mà nó thuộc hoặc đang di chuyển vào Hình 2.2 minh họa khung nhìn phân tầng của các kỹ thuật phân cụm và bảo trì khác nhau.
Chi ến lượ c b ảo trìkhông có nút đầ u c ụ m CWOHO
Trong chiến lược bảo trì phân tán toàn phần, một thách thức lớn là đưa ra quyết định cụ thể một cách phân tán Ví dụ, trong hai cụm với ClusterID 501 và 231, các nút được xác định bằng NodeID duy nhất Cụm 501 kết nối với cụm 231, với các nút 90, 34 và 49 là các nút biên Vấn đề đặt ra là làm thế nào để xác định sự kết nối giữa các cụm trong môi trường di động và cách chia sẻ thông tin này Việc chọn một nút đứng đầu trong mỗi cụm có thể giúp đơn giản hóa quá trình ra quyết định và chia sẻ thông tin, nhưng trong một môi trường phân tán toàn phần, không tồn tại nút đứng đầu.
Hình 2.3 Xây dựng bảng định tuyến trong CWOHO
Giao thức ZHLS sử dụng các nút biên để xác định khả năng kết nối của cụm với các cụm lân cận và cập nhật các thay đổi trong cụm đó Các nút biên đưa ra quyết định chỉ dựa trên thông tin cục bộ mà không xem xét các nút biên khác trong cùng cụm lân cận, điều này có thể dẫn đến quyết định sai và quảng bá không cần thiết trong mạng Ví dụ, kết nối giữa hai cụm 501 và 231 chỉ bị lỗi nếu tất cả các nút biên trong cụm 501, tức là 90, đều gặp sự cố.
34 và 49, mất kết nối với 231 Do đó, tất cả các nút biên phải được xem xét để xác định kết nối giữa các cụm liền kề
Chiến lược phân tán toàn phần trong CWOHO giúp duy trì kết nối giữa các cụm bằng cách cho phép các cụm thu thập thông tin từ tất cả các nút biên, từ đó đưa ra quyết định kết nối với các cụm lân cận Điều này giúp khắc phục các vấn đề quyết định sai trước đó Một điểm khác biệt quan trọng giữa CWOHO và ZHLS là CWOHO không sử dụng các nút biên để quảng bá các thay đổi trong cụm lân cận; thay vào đó, bất kỳ nút nào trong cụm đều có thể thực hiện hoạt động quảng bá, tạo nên một chiến lược bảo trì phân tán toàn phần hiệu quả.
Trong hoạt động của CWOHO, việc xác định các nút biên của cụm là rất quan trọng Các nút định kỳ thu thập thông tin từ các nút lân cận thông qua gói tin ReqNghInfo, và nhận phản hồi qua gói NghInfo, trong đó chứa ClusterID của cụm lân cận Thông tin này giúp xác định các nút biên của cụm Các nút cũng kiểm tra gói NghInfo để xác định xem có nút lân cận nào thuộc về cụm khác không Chẳng hạn, nút 34 được coi là nút biên của cụm 501 vì nó nhận gói NghInfo từ nút 45 thuộc cụm có ClusterID 231.
Mỗi nút trong mạng duy trì một bảng định tuyến với thông tin về các chặng lân cận tiếp theo Trong giao thức CWOHO, các nút áp dụng Thuật toán 1 để tạo bảng định tuyến, nhằm chuyển tiếp gói dữ liệu đến các cụm lân cận với số chặng nhỏ nhất Các nút biên của cụm sử dụng gói NbdClusterInfo để quảng bá thông tin về cụm lân cận tới tất cả các nút trong cụm, bao gồm ClusterID và HopCount (bằng 1) Gói NbdClusterInfo sẽ bị loại bỏ nếu nó thuộc một cụm khác hoặc nếu nút nhận được gói này từ nút lân cận với số chặng lớn hơn Nếu không, nút sẽ tăng HopCount lên 1 và kiểm tra thông tin về cụm lân cận trong bảng định tuyến của nó.
Xét một nút trong bảng định tuyến có thông tin về cụm lân cận X với số chặngnhỏ nhất là m Có các trường hợp sau sẽ xảy ra:
• Nếu m