Tài liệu Nghiên cứu chiến lược bảo trì thông tinh định tuyến trong mạng ad hoc phân cụm

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG Hoàng Xuân Giang NGHIÊN CỨU CHIẾN LƯỢC BẢO TRÌ THÔNG TIN ĐỊNH TUYẾN TRONG MẠNG AD HOC PHÂN CỤM LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH Thái Nguyên - 2020 ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG Hoàng Xuân Giang NGHIÊN CỨU CHIẾN LƯỢC BẢO TRÌ THÔNG TIN ĐỊNH TUYẾN TRONG MẠNG AD HOC PHÂN CỤM Ngành: Khoa học máy tính Mã số: 8480101 LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH NGƯỜI HƯỚNG DẪN KHOA HỌC PGS.TS. NGUYỄN VĂN TAM Thái Nguyên - 2020 LỜI CẢM ƠN Sau thời gian học tập và rèn luyện tại Trường Đại học Công nghệ thông tin và Truyền thông – Đại học Thái Nguyên, bằng sự biết ơn và kính trọng, tôi xin gửi lời cảm ơn chân thành đến Ban Giám hiệu, Phòng Đào tạo và Khoa Công nghệ thông tin thuộc Trường Đại học Công nghệ thông tin và Truyền thông – Đại học Thái Nguyên cùng các thầy, cô giáo đã nhiệt tình hướng dẫn, giảng dạy và tạo mọi điều kiện thuận lợi giúp đỡ tôi trong suốt quá trình học tập, nghiên cứu và hoàn thiện luận văn này. Đặc biệt, tôi xin bày tỏ lòng biết ơn sâu sắc tới PGS. TS. Nguyễn Văn Tam, người thầy đã trực tiếp hướng dẫn, giúp đỡ em trong quá trình thực hiện đề tài. Xin chân thành cảm ơn gia đình, bạn bè cùng đồng nghiệp đã tạo điều kiện sát, nghiên cứu để hoàn thành đề tài này. Tuy nhiên điều kiện về năng lực bản thân còn hạn chế, luận văn chắc chắn không tránh khỏi những thiếu sót. Kính mong nhận được sự đóng góp ý kiến của các thầy cô giáo, bạn bè và đồng nghiệp để luận văn của tôi được hoàn thiện hơn. Xin trân trọng cảm ơn! Thái Nguyên, ngày … tháng …. năm 2020 Học viên Hoàng Xuân Giang MỤC LỤC MỞ ĐẦU ........................................................................................................... 1 CHƯƠNG 1. TỔNG QUAN VỀ ĐỊNH TUYẾN TRONG MẠNG MANET PHÂN CỤM ...................................................................................................... 4 1.1. Tổng quan về mạng MANET................................................................. 4 1.1.1. Khái niệm mạng MANET ............................................................... 4 1.1.2. Đặc điểm của mạng MANET.......................................................... 5 1.1.3. Ứng dụng của mạng MANET ......................................................... 7 1.2. Vấn đề bảo trì thông tin định tuyến trong mạng MANET phân cụm .... 9 1.3. Một số kỹ thuật phân cụm trong mạng MANET ................................. 12 1.4. Một số kỹ thuật bảo trì thông tin cụm trong mạng MANET ............... 15 1.4.1. Chiến lược dựa trên nút đứng đầu................................................. 16 1.4.2. Chiến lược phân tán một phần ...................................................... 17 1.4.3. Chiến lược phân tántoàn phần....................................................... 17 1.5. Tổng kết Chương 1 .............................................................................. 18 CHƯƠNG 2. CHIẾN LƯỢC BẢO TRÌ THÔNG TIN ĐỊNH TUYẾN TRONG MẠNG MANET PHÂN CỤM ....................................................................... 20 2.1. Xây dựng lớp phủ dựa trên mạng phân cụm ........................................ 20 2.2. Chiến lược bảo trìkhông có nút đầu cụm CWOHO ............................. 22 2.3.Chiến lược bảo trì có nút đầu cụm CWHO ........................................... 28 2.4. Chiến lược bảo trì cụm từ thông tin cụm lân cận CNI ......................... 31 2.5. Phân tích chi phí điều khiển của các chiến lược .................................. 32 2.6. Tổng kết Chương 2 .............................................................................. 34 CHƯƠNG 3. ĐÁNH GIÁ HIỆU QUẢ CỦA CÁC CHIẾN LƯỢC BẢO TRÌ THÔNG TIN ĐỊNH TUYẾN.......................................................................... 36 3.1. Kịch bản mô phỏng và các độ đo đánh giá hiệu năng ......................... 36 3.2. Hiệu năng trên mô hình Random Way Point ....................................... 37 3.2.1. Tác động của số lượng cụm .......................................................... 37 3.2.2. Tác động của tốc độ nút di chuyển ............................................... 39 3.2.3. Tác động của thời gian tạm dừng.................................................. 41 3.2.4. Chi phí điều khiển ......................................................................... 43 3.3. Hiệu năng trên mô hình Manhattan-Grid ............................................. 46 3.4. Hiệu năng khi so sánh với giao thức ZHLS ......................................... 50 3.5. Tổng kết Chương 3 .............................................................................. 52 KẾT LUẬN ..................................................................................................... 54 TÀI LIỆU THAM KHẢO ............................................................................... 56 1 MỞ ĐẦU Được hình thành bởi các kết nối tạm thời giữa các nút mạng di động không có sự hỗ trợ của cơ sở hạ tầng mạng cố định, mạng ad hoc di động (MANET) có nhiều những đặc điểm khác biệt so với mạng không dây và có dây truyền thống làm nảy sinh nhiều thách thức và các hướng nghiên cứu khác nhau: vấn đề định tuyến hiệu quả khi topo mạng thay đổi, đảm bảo chất lượng dịch vụ theo yêu cầu từ chương trình ứng dụng, đảm bảo an ninh mạng, tiết kiệm năng lượng, khả năng tự tổ chức, chuyển đổi các dịch vụ từ mô hình client-server và đảm bảo hiệu năng kích thước mạng thay đổi. Kết quả của nghiên cứu phân loại và đánh giá về số lượng các nghiên cứu theo các hướng khác nhau đối với mạng MANET trong thời gian gần đây cho thấy, hướng nghiên cứu về định tuyến trong mạng MANET đứng đầu về số lượng các nghiên cứu đã được công bố. Như vậy, có thể khẳng định, định tuyến trong mạng MANET đã và đang là một vấn đề rất cần được quan tâm giải quyết trong những nghiên cứu cải tiến hiệu năng mạng MANET. Phân cụm là một chiến lược hiệu quả để giải quyết tính động và khả năng mở rộng của mạng ad hoc di động có quy mô lớn. Các giao thức định tuyến theo cụm có khả năng mở rộng tốt hơn các giao thức định tuyến phẳng vì kỹ thuật phân cụm làm giảm kích thước của bảng định tuyến và chi phí cần thiết để duy trì thông tin định tuyến. Phân cụm có thể làm tăng tính sẵn sàng của thông tin trong mạng, chẳng hạn như vị trí của các nút di động, bằng cách nhân bản thông tin tới các nút trong các cụm khác nhau. Khi triển khai truyền thông quảng bá hoặc truyền thông đa điểm, kỹ thuật phân cụm cho phép lan truyền thông tin một cách có chọn lọc để giảm các gói tin quảng bá dư thừa. Hơn nữa, việc phân cụm sẽ tạo hỗ trợ cho việc quản lý tài nguyên một cách hiệu quả bằng 2 cách kiểm soát được việc chia sẻ và tiết kiệm tài nguyên nhằm đáp ứng các yêu cầu QoS của ứng dụng. Đã có những nghiên cứu đề xuất các kỹ thuật phân cụm trong mạng ad hoc, chẳng hạn như sử dụng tập quản lý cụm, phân cụm phân tán, phân cụm trên cơ sở tín hiệu và trên cơ sở vị trí. Các nghiên cứu này tập trung vào việc xây dựng các cụm để quản lý sự di động của nút hoặc tối ưu hóa sức mạnh/chi phí của các nút quản lý cụm. Trong đề tài này, mạng ad hoc được giả định là đã được phân cụm. Đề tài tập trung nghiên cứu các kỹ thuật và chiến lược khác nhau để triển khai một tầng con phía trên thực hiện nhiệm vụ bảo trì và quản lý trạng thái động của các cụm, bao gồm trạng thái các nút và dữ liệu/tệp sẵn sàng, kết nối mạng, băng thông, khả năng xử lý và những thông tin khác. Ý tưởng của các đề xuất được nghiên cứu trong đề tài là nhằm ẩn đi tính động của các cụm để cải thiện hiệu năng của các ứng dụng trong mạng MANET phân cụm. Duy trì trạng thái của các cụm 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 mạng sẽ thu thập thông tin trạng thái cục bộ trong cụm và trong giai đoạn phân phối, thông tin được chia sẻ với các cụm khác. Vấn đề bảo trì là một thách thức trong mạng MANET vì tính di động của các nút, trạng thái của các cụm có thể thường xuyên thay đổi dẫn đến tăng chi phí thực hiện các hoạt động thu thập và phân phối. Một chiến lược bảo trì tốt sẽ cân bằng giữa khối lượng các công việc và mức tiêu thụ năng lượng của các nút, tối thiểu hoá chi phí và theo dõi các thay đổi một cách kịp thời và chính xác. Để quản lý bất kỳ thông tin trạng thái nào, một giao thức duy trì cần thực hiện các hoạt động thu thập và phân phối. Trong đề tài này, để không mất tính tổng quát, kết nối logic giữa các cụm được xem là thông tin trạng thái. Hai cụm là có kết nối nếu chúng liền kề nhau và có thể định tuyến trực tiếp các thông 3 điệp với nhau qua một nút biên. Có thể mô hình hóa các cụm và kết nối giữa chúng như là một lớp bao phủ trên mạng MANET ban đầu, với mỗi cụm là một đỉnh và mỗi kết nối của chúng là một cạnh. Một cách tiếp cận đơn giản để giải quyết vấn đề duy trì trạng thái trong mạng MANET phân cụm là giao nhiệm vụ duy trì cho các nút quản lý cụm. Điều này liên quan đến việc 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 đầu quản lý cụm khác. Các nút quản lý cụm thường có nhiệm vụ xử lý các yêu cầu định tuyến liên cụm cho các nút trong cụm của mình. Các nút khác trong cụm chỉ cần duy trì đường tới nút quản lý của chúng. Mục đích của đề tài này là nghiên cứu một số chiến lược bảo trì thông tin định tuyến trong mạng MANET phân cụm nhằm nâng cao hiệu quả định tuyến. Các chiến lược này cũng được so sánh, đánh giá về mức độ hiệu quả so với một số chiến lược đã đề xuất khác bằng cách sử dụng phần mềm mô phỏng. Cấu trúc luận văn được trình bày như sau: Chương 1 trình bày tổng quan về mạng MANET và vấn đề định tuyến trong mạng MANET phân cụm. Một số chiến lược bảo trì thông tin định tuyến trong mạng MANET phân cụm được trình bày và phân tích chi tiết trong chương 2. Kết quả của việc cài đặt, mô phỏng, so sánh đánh giá hiệu hiệu quả của một số chiến lược bảo trì thông tin định tuyến trong mạng MANET phân cụm được trình bày trong Chương 3. Nội dung tổng kết và hướng phát triển của đề tài được đưa ra trong phần kết luận. 4 CHƯƠNG 1. TỔNG QUAN VỀ ĐỊNH TUYẾN TRONG MẠNG MANET PHÂN CỤM 1.1. Tổng quan về mạng MANET 1.1.1. Khái niệm mạng MANET Mạng MANET (Mobile Ad hoc Network) [11] là một tập các nút không dây di động có thể trao đổi dữ liệu một cách linh động mà không cần sự hỗ trợ của trạm cơ sở cố định hoặc mạng có dây. Mỗi nút di động có một phạm vi truyền giới hạn, do đó chúng cần sự trợ giúp của các nút láng giềng để chuyển tiếp các gói dữ liệu. Hình 1.1 minh họa một mạng MANET. Trong ví dụ này, các gói tin từ nút nguồn là một máy tính cần chuyển tới một nút đích là một điện thoại thông minh không nằm trong phạm vi truyền của nút nguồn. Vì vậy, cần có sự trợ giúp của các nút trung gian để chuyển tiếp gói tin từ nút nguồn tới nút đích. Để thực hiện được công việc này, các nút mạng phải sử 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” áp dụng cho mạng không dây mô tả một mạng không có cơ sở hạ tầng cố định, trong đó hình trạng mạng được tạo thành bởi chính các nút mạng. Chế độ “Ad hoc” của chuẩn IEEE 802.11 hoạt động theo mô 5 hình này, mặc dù nó chỉ hỗ trợ để thiết lập một mạng đơn chặng. Các mạng di động không dây kiểu không cấu trúc (MANET) đã mở rộng khái niệm “Ad hoc” đa chặng theo nghĩa: một nút mạng có thể định tuyến và chuyển tiếp một gói tin nó nhận được từ một nút mạng khác. Nói cách khác, con đường chuyển tiếp gói tin từ nút nguồn tới nút đích có thể chứa các nút trung gian khác. Các nút trung gian sẽ đọc thông tin trong phần header của các gói tin dữ liệu và chuyển tiếp chúng tới chặng kế tiếp trên một con đường đã được hình thành. Các nút trong mạng MANET thông thường sẽ kết nối với nhau trong một khoảng thời gian để trao đổi thông tin. Trong khi trao đổi thông tin, các nút này vẫn có thể di chuyển, do đó, mạng này phải đáp ứng được yêu cầu truyền dữ liệu trong khi hình trạng mạng có thể thay đổi liên tục. Các nút mạng phải có cơ chế tự tổ chức thành một mạng để 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 mạng có thể đóng vai trò là một nút đầu cuối để chạy các chương trình ứng dụng của người sử dụng hoặc là một bộ định tuyến để chuyển tiếp các gói tin cho các nút mạng khác. 1.1.2. Đặc điểm của mạng MANET Do MANET là một mạng không dây hoạt động không cần sự hỗ trợ của hạ tầng mạng cơ sở trên cơ sở truyền thông đa chặng giữa các thiết bị di động vừa đóng vai trò là thiết bị đầu cuối, vừa đóng vai trò là bộ định tuyến nên mạng MANET còn có một số đặc điểm nổi bật sau:  Cấu trúc động: Do tính chất di chuyển ngẫu nhiên của các nút mạng nên cấu trúc của loại mạng này cũng thường xuyên thay đổi một cách ngẫu nhiên ở những thời điểm không xác định trước. Trong khi thay đổi, cấu trúc của mạng MANET có thêm hoặc mất đi các kết nối hai chiều hoặc kết nối một chiều. 6  Chất lượng liên kết hạn chế: Các liên kết không dây thường có băng thông nhỏ hơn so với các liên kết có dây. Ngoài ra, do ảnh hưởng của cơ chế đa truy cập, vấn đề suy giảm tín hiệu, nhiễu và các yếu tố khác, băng thông thực 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 theo lý thuyết của môi trường truyền không dây.  Các nút mạng có tài nguyên hạn chế: Mỗi nút di động trong mạng MANET có thể là một bộ cảm biến, một điện thoại thông minh hoặc một máy tính xách tay. Thông thường các thiết bị này 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 về tốc độ xử lý, dung lượng bộ nhớ và năng lượng nguồn pin nuôi sống hoạt động của nút.  Độ bảo mật thấp ở mức độ vật lý: Mạng không dây di động thường chịu tác động về mặt vật lý từ các nguồn gây nguy hại về an ninh nhiều hơn so với mạng có dây. Về khía cạnh vật lý, các kỹ thuật gây mất an ninh và bảo mật trong mạng như nghe lén, giả mạo và tấn công từ chối dịch vụ thường dễ triển khai trong mạng MANET hơn là trong mạng có dây truyền thống. Có thể thấy những đặc điểm này là các yếu tố ảnh hưởng rất nhiều đến hiệu năng của mạng MANET. Để có thể triển khai được mạng MANET trong thực tế, các thiết kế mạng MANET phải giải quyết được những thách thức sinh ra do những đặc điểm đã nêu trên của mạng MANET. Những thách thức này gồm các vấn đề kỹ thuật như 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 chương trình ứng dụng; cơ chế chuyển đổi một số dịch vụ từ mô hình clientserver; 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 riêng lẻ và của 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; 7 1.1.3. Ứng dụng của mạng MANET Ngày nay, mạng MANET có nhiều những ứng dụng trong đời sống, kinh tế, xã hội của con người. Mô hình mạng này phù hợp đối với những tình huống cần triển khai hệ thống mạng một cách nhanh chóng, linh động và thường xuyên có sự biến đổi trong cấu trúc mạng. Ngày nay, mạng MANET được ứng dụng trong rất nhiều lĩnh vực từ các ứng dụng trong thương mại tới các ứng dụng trong các hoạt động quân sự, ứng dụng trong các hoạt động khẩn cấp, ứng dụng trong gia đình, văn phòng và giáo dục, mạng giao thông và mạng cảm biến. Đối với các ứng dụng của mạng MANET trong thương mại, những người dùng có thể chia sẻ dữ liệu giữa các thiết bị di động trong một cuộc họp hay hội thảo mà không cần sự hỗ trợ của một cơ sở hạ tầng mạng cố định. Các máy tính của những cá nhân có thể kết nối với nhau để tạo thành một mạng tạm thời phục vụ cho các ứng dụng truyền thông dữ liệu trong một nhóm những người dùng mà không cần sự hiện diện của các bộ thu phát tập trung. Kết nối Internet từ một thiết bị của một người dùng cũng có thể được chia sẻ tới các thiết bị của những người dùng khác thông qua mạng MANET. Ứng dụng mạng MANET trông quân đội là một trong những ý tưởng được đưa ra ngay từ khi mạng MANET được phát triển. Trong mô hình chiến đấu của quân đội trên chiến trường không có sự hỗ trợ về hạ tầng mạng cố định, mỗi người lính hoặc một phương tiện quân sự như xe tăng, máy bay, tàu chiến, tàu thủy đều có thể được kết nối và trao đổi thông tin tạm thời với nhau hoặc với trạm chỉ huy một cách linh động thông qua mạng MANET được hình thành bởi kết nối giữa các thiết bị di động truyền thông không dây được gắn vào các phương tiện quân sự hay những người lính tham gia vào cuộc chiến. Tại các vùng bị thiên tai, thảm họa, có thể tất cả các phương tiện và hạ tầng truyền thông được xây dựng trước đó đều bị phá hủy hoàn toàn. Mỗi chiếc 8 xe của cảnh sát, cứu hỏa, cứu thương,… có thể được trang bị các thiết bị truyền nhận không dây để trở thành một thiết bị đầu cuối di động và là một phần của mạng MANET. Mỗi nhân viên cứu hộ cũng có thể cũng mang theo một thiết bị đầu cuối di động. Các thiết bị đầu cuối này đều liên kết với nhau, hình thành nên một mạng MANET tạm thời nhằm trao đổi thông tin. Cấu hình mạng thay đổi theo những thời điểm khác nhau. Ngoài ra, các thiết bị đầu cuối di động không chỉ cung cấp chức năng gửi và nhận thông tin mà còn có thể chuyển tiếp thông tin như vai trò như các bộ định tuyến. Mỗi thiết bị thông minh trong gia đình, các điên thoại di động thông minh và máy tính của những người sử dụng trong văn phòng, trong môi trường trường học, các lớp học có thể đóng vai trò như một nút mạng trong một mạng MANET được hình thành tạm thời mà không cần sự hỗ trợ của hạ tầng mạng cố định nhằm phục vụ cho các ứng dụng chia sẻ thông tin, truyền dữ liệu multimedia, quản lý ngôi nhà thông minh, quản lý lớp học thông minh,… Trong vấn đề quản lý và hỗ trợ giao thông, mỗi phương tiện giao thông là một nút mạng di động trong mạng MANET được hình thành tạm thời trên một khu vực địa lý nhằm hỗ trợ trao đổi và quản lý các thông tin về tình trạng giao thông, hỗ trợ tìm đường tránh tắc nghẽn giao thông, theo dõi và quản lý các thiết bị tham gia giao thông, v.v. Cảm biến là các thiết bị nhỏ, phân tán, giá thành thấp, tiết kiệm năng lượng, có khả năng truyền thông không dây và xử lý cục bộ. Một mạng MANET có thể là một mạng cảm biến gồm các nút cảm biến. Các nút này hợp tác với nhau để cùng thực hiện một nhiệm vụ cụ thể, ví dụ như: giám sát môi trường (không khí, đất, nước), theo dõi môi trường sống, hành vi, dân số của các loài động, thực vật, dò tìm động chấn, theo dõi tài nguyên, thực hiện trinh thám trong quân đội,... 9 1.2. Vấn đề bảo trì thông tin định tuyến trong mạng MANET phân cụm Phân cụm là một chiến lược hiệu quả để giải quyết tính động và khả năng mở rộng của mạng ad hoc di động (MANET) [2]. Theo [1], các giao thức định tuyến trên cơ sở phân cụm có khả năng mở rộng hơn so với các giao thức định tuyến phẳng, vì việc phân cụm làm giảm kích thước của bảng định tuyến và chi phí định tuyến cần thiết để bảo trì thông tin định tuyến. Phân cụm có thể làm tăng tính sẵn sàng của thông tin mạng, chẳng hạn như vị trí của các nút di động, bằng cách sao chép thông tin giữa các nút trong các cụm khác nhau. Khi thực hiện truyền thông tin kiểu quảng bá hoặc multicast, phân cụm cho phép cơ chế lan truyền thông tin kiểu quảng bá một cách có chọn lọc để giảm các thông điệp quảng bá dư thừa. Hơn nữa, việc phân cụm tạo cơ chế để quản lý tài nguyên hiệu quả bằng cách 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. Đã có công trình nghiên cứu xem xét các kỹ thuật phân cụm khác nhau trong mạng ad hoc [1], chẳng hạn như sử dụng tập quản lý, phân cụm phân tán, cơ chế báo hiệu và dựa vào vị trí. Những nghiên cứu này chủ yếu tập trung vào việc xây dựng các cụm để quản lý tính di động của nút hoặc tối ưu năng lượng cũng như chi phí quản lý của các nút đầu cụm. Trong đề tài này, mạng được giả định là đã được phân cụm để nghiên cứu các kỹ thuật triển khai một tầng con có nhiệm vụ quản lý trạng thái động của các cụm, chẳng hạn như trạng thái sẵn sàng của nút và dữ liệu/tệp có sẵn, kết nối mạng, băng thông, khả năng xử lý và thông tin khác. Ý tưởng của đề tài này là nhằm che giấu tính động của các cụm bên dưới, để cải thiện hiệu suất của các ứng dụng hoạt động trong mạng MANET phân cụm. Việc duy trì trạng thái của các cụm liên quan đến hai hoạt động chính là thu thập và phân phối thông tin. Trong pha thu thập, các nút thu thập thông tin trạng thái trong cụm nội bộ của nó. Trong pha phân phối, thông tin được chia 10 sẻ cho các cụm khác. Bảo trì là một vấn đề thách thức trong mạng MANET vì tính di động của các nút làm thay đổi thường xuyên trạng thái của các cụm và tăng chi phí thực hiện các hoạt động thu thập và phân phối thông tin. Một chiến lược bảo trì tốt sẽ cân bằng tải công việc và mức tiêu thụ năng lượng của các nút, tối thiểu hóa chi phí và lưu vết các thay đổi một cách kịp thời và chính xác. Để quản lý thông tin trạng thái, một 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, để không mất tính tổng quát, kết nối logic giữa các cụm được coi là thông tin trạng thái. Hai cụm được xem là có kết nối, nếu chúng liền kề nhau và có thể định tuyến trực tiếp các thông điệp với nhau thông qua một nút biên. Ta có thể mô hình hóa các cụm và các kết nối giữa chúng như một lớp phủ trên mạng MANET ban đầu với các cụm là các đỉnh và kết nối của chúng là các cạnh của lớp phủ. Theo [1], một cách tiếp cận đơn giản để 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 bảo trì cho nút đầu cụm. Trách nhiệm này liên quan đến việc 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 đầu cụm khác. Các nút đầu cụm thường chịu trách nhiệm quản lý và xử lý các yêu cầu định tuyến liên cụm cho các nút cùng cụm với nó. Khi đó, 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. Đề tài này sẽ nghiên cứu kỹ nghiên cứu [1] đề xuấttriển khai một chiến lược bảo trì mạng phủ phân cụm dựa trên nút đứng đầu, được gọi là CWHO (Cluster-Based With Head Overlay). Đây là chiến lược cơ sở để so sánh với các chiến lược bảo trì khác. Trong thiết kế của các chiến lược bảo trì thông tin trong mạng MANET, còn có những cách tiếp cận khác. Ngược lại với chiến lược CWHO, còn có một chiến lược phân phối đầy đủ, không dựa vào các nút đứng đầu. Theo cách tiếp cận phân tán đầy đủ, mọi nút đều chia sẻ trách nhiệm như nhau trong việc thu 11 thập và phân phối thông tin về các cụm lân cận của chúng. Theo phương pháp này, mọi nút có thể xử lý các hoạt động định tuyến liên cụm, vì chúng chia sẻ thông tin trạng thái của tất cả các cụm trong mạng. Do đó, đề tài này cũng nghiên cứu về đề xuất [1]triển khai một chiến lược bảo trì thông tin định tuyến trong mạng phủ phân cụm không có đứng đầu, được đặt tên là CWOHO (Cluster- Based WithOut Head Overlay). Hai chiến lược bảo trì ở trên có thể được sử dụng để chia sẻ thông tin trạng thái cục bộ của các cụm với toàn bộ mạng. Cả hai đều có những ưu điểm riêng, có thể khác nhau trong các điều kiện mạng khác nhau. Chiến lược CWHO đơn giản và hoạt động tốt trong nhiều tình huống. Tuy nhiên, nó có thể gặp phải các vấn đề như mất cân bằng tải và khả năng tiêu thụ năng lượng, nút đầu cụm bị lỗi hoặc di chuyển và nút đầu cụm chịu tải lưu lượng truy cập bổ sung. Chiến lược CWOHO có thể tránh được những vấn đề này, nhưng chi phí bảo trì có thể cao. Ở giữa hai cách tiếp cận trên, có những cách tiếp cận bảo trì thông tin định tuyến khác. Một trong những cách tiếp cận này là chiến lược Phân cụm với thông tin nút lân cận CNI (Clusters with Neighbor Information) [1]. Chiến lược CNI thực hiện hoạt động thu thập thông tin một cách phân tán như trong chiến lược CWOHO. Tuy nhiên, thông tin thu thập không được chia sẻ với toàn bộ mạng. Các nút chỉ duy trì thông tin về các cụm lân cận của chúng. Với cách tiếp cận này, nghiên cứu giả định rằng mọi nút đều có kiến thức trước về cấu trúc kết nối mạng. Cấu trúc kết nối cho thấy hướng của các cụm và có thể xây dựng được nó bằng cách sử dụng thuật toán phân tán hoặc sử dụng thông tin về vị trí địa lý các nút trong mạng. Trong chiến lược CNI, việc định tuyến liên cụm được thực hiện theo cách tiếp cận sử dụng quyết định định tuyến tại mỗi cụm trung gian. 12 Một chiến lược bảo trì thông tin định tuyến cụ thể nào đó có thể không áp dụng được cho tất cả các điều kiện và mô hình di động của mạng. Ví dụ: nếu các nút di chuyển chậm trong mạng, thì chiến lược bảo trì với nút đầu cụm có thể có hiệu suất tốt. Tuy nhiên, trong trường hợp mạng có tính cơ động cao, có thể cần xem xét đến chiến lược bảo trì phân tán. Để hiểu tác động của tính di động của nút, đề tài này sẽ đánh giá hiệu năng của ba chiến lược bảo trì ở trên theo hai mô hình di động khác nhau, đó là mô hình Random Waypoint và Manhattan Grid bằng phương pháp mô phỏng. Các công việc sẽ được thực hiện trong đề tài này bao gồm: (a) Đưa ra một nghiên cứu toàn diện về vấn đề bảo trì trạng thái trong các mạng MANET phân cụm bằng cách triển khai thiết kế của chiến lược bảo trì với nút đầu cụm CWHO. Đây là chiến lược phổ biến và được sử dụng rộng rãi nhất; (b) Triển khai chiến lược bảo trì một cách gần nhất với cách tiếp cận phân phối đầy đủ, được gọi là CWOHO. Trong CWOHO, 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 của nó với các cụm lân cận. Thông tin này sau đó được quảng bá để chia sẻ cho mọi nút trong mạng; (c) Triển khai chiến lược CNI là lấy điểm giữa giữa hai thái cực chiến lược CWHO và CWOHO; (d) Sử dụng mô phỏng để đánh giá về ba chiến lược bảo trì trong các điều kiện mạng khác nhau. Điều này cung cấp một cái nhìn sâu sắc cho các chiến lược thiết kế khác nhau cho vấn đề bảo trì thông tin định tuyến. 1.3. Một số kỹ thuật phân cụm trong mạng MANET Kỹ thuật phân cụm thường được sử dụng để giảm chi phí định tuyến của mạng và tăng thời gian sống của các nút trong mạng. Kỹ thuật phân cụm phân tán được nghiên cứu rộng rãi nhất trên mạng ad hoc và cảm biến không dây dựa trên lý thuyết đồ thị thống trị. Một tập thống trị [5] của đồ thị G = (V, E) có thể được định nghĩa là một tập con của các đỉnh S ⊆ V sao cho mọi đỉnh v ∈ V đều 13 nằm trong S hoặc liền kề với một đỉnh của S. Một đỉnh của S được xem là thống trị chính nó và các đỉnh lân cận của nó. Một cạnh được gọi là cạnh bị thống trị nếu một trong hai điểm mút của nó nằm trong S và các cạnh khác được gọi là cạnh tự do. Nhiều kỹ thuật đã được đề xuất để chọn tập thống trị S [1], chẳng hạn như 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 trong S liền kề nhau; trong khi đó trong CDS, tất cả các đỉnh trong S đều được kết nối. Do đó, số lượng cụm có thể có trong IDS nhỏ hơn trong CDS. Tuy nhiên, khả năng kết nối của các nút đầu cụm trong CDS được xem là thuận lợi hơn 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, giú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] đề xuất một kỹ thuật phân tán khác để phân cụm các nút thành các vùng không chồng lấp. Đối với việc hình thành vùng, DDR không chọn một tập hợp con các nút trong mạng như trong tập thống trị. Thay vào đó, một thuật toán phân tán được sử dụng để xây dựng một rừng. Các cây trong rừng được hình thành bằng cách 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) bằng cách sử dụng thuật toán đặt tên vùng. Các vùng được kết nối với nhau bởi 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 các nút báo hiệu để phân cụm các nút trong mạng. Các nút báo hiệu cố gắng tác động vào các nút lân cận để thu hút các nút khác nhằm tạo thành cụm. Phương pháp LABAR [4] nghiên cứu về mạng hỗn độn trong đó chỉ có một tập con các nút có thông tin vị trí chính xác của chúng. Các nút có thông tin vị trí được gọi là các nút G và phần còn lại là các nút S. Các nút G đóng vai trò là nút báo hiệu và tạo thành các vùng bằng cách lôi kéo các nút S trong vùng lân cận của chúng. Phương pháp BEAD [7] 14 nghiên cứu mạng ad hoc phân cấp ba tầng với các nút di động (MN) ở tầng thấp nhất, theo sau là các nút chuyển tiếp (FN) và các điểm truy cập (AP) ở các tầng tiếp theo. Các thông điệp báo hiệu định kỳ được gửi bởi FN và AP được quét bởi các MN để xác định nút cha tốt nhất của chúng trong mạng. Phương pháp trong [16] cũng là một dạng kỹ thuật phân cụm dựa trên nút báo hiệu. Các nút trong MANET cũng có thể được nhóm lại kiểu vật lý dựa trên mối quan hệ logic hoặc kiểu hoạt động của chúng. Các ứng dụng như khắc phục thảm họa hoặc triển khai trong quân sự trong một khu vực thường yêu cầu sự hợp tác giữa các nhóm nhỏ các nút trong mạng. Các thành viên trong nhóm có chung mối quan tâm và chúng luôn di chuyển theo nhóm với tốc độ và hướng tương tự như nhau. Từ đặc điểm này, có thể phân chia các nút vật lý thành nhiều nhóm nhỏ. Kỹ thuật này được gọi là 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ý khác, thường được sử dụng trong các mạng hoạt động với các nút có hỗ trợ hệ thống định vị toàn cầu GPS, là phân chia việc triển khai thành các lưới địa lý. Kỹ thuật này đòi hỏi mỗi nút phải biết trước thông tin về hình dạng của khu vực triển khai và phân vùng của khu vực. Thông tin trên giúp mỗi nút xác định ranh giới của cụm và cụm chứa nó. So sánh với tính di động của nhóm, trong kỹ thuật này tính di động của các nút là ngẫu nhiên và các phân vùng địa lý được cố định. Ngoài ra, còn có những kỹ thuật phân cụm khác. Nghiên cứu [14] đã khảo sát các kỹ thuật phân cụm trong các mạng không dây. Các kỹ thuật phân cụm trong mạng MANET được tổng kết trong Bảng 2.1. Kỹ thuật phân cụm Tập thống trị Đặc điểm Giao thức Phân cụm logic bằng cách chọn một tập con các nút trong IDS,CDS, WCDS mạng 15 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 GLIDER, LABAR, BEAD 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 DCS, ZHLS, DLM, GLS Bảng 2.1. Một số kỹ thuật phân cụm tiêu biểu trong mạng MANET 1.4. 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, chẳng hạn như kết nối giữa các cụm, băng thông của các liên kết lớp phủ và kích thước của cụm, có thể thay đổi thường xuyên. Đã có các chiến lược bảo trì thông tin mạng được nghiên cứu và đề xuất [1]. Có thể phân chia các chiến lược bảo trì thông tin mạng thành hai nhóm là nhóm các chiến lược bảo trì dựa trên nút đứng đầu và nhóm các chiến lược sử dụng phương pháp phân tán. Mô tả ngắn gọn về các giao thức triển khai của các chiến lược này được trình bày trong Bảng 2.2. Giao thức Mô tả 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, MCEDAR Sử dụng các nút lõi để bảo trì thông tin về các cụm. GLIDER Topo mạng cảm biến được phân tán cho mọi nút và sử dụng cho định tuyến.