Luận văn thạc sĩ thuật toán quảng bá lại thông tin định tuyến nhằm tối thiểu hoá chi phí định tuyến trong mạng ad hoc di động

Luận văn thạc sĩ toán học phân tích thuật toán quảng bá lại thông tin định tuyến nhằm tối thiểu hoá chi phí định tuyến trong mạng ad, đánh giá thực trạng, chỉ ra hạn chế, đề xuất

• Tác giả: Lê Hồng Sơn
• Người hướng dẫn: TS. Đỗ Đình Cường
• Trường học: Đại học Thái Nguyên
• Chuyên ngành: Khoa học máy tính
• Đề tài: Thuật Toán Tối Ưu Chi Phí Định Tuyến Trong Mạng Ad Hoc Di Động
• Loại tài liệu: luận văn thạc sĩ
• Năm xuất bản: 2020
• Địa điểm: Thái Nguyên

Tóm tắt

I. Tổng quan về thuật toán tối ưu chi phí định tuyến trong mạng ad hoc di động

Mạng ad hoc di động là một cấu trúc mạng không dây tự tổ chức, cho phép các nút di động kết nối và giao tiếp mà không cần cơ sở hạ tầng cố định. Thuật toán tối ưu chi phí định tuyến trong mạng này đóng vai trò quan trọng trong việc cải thiện hiệu suất truyền thông. Việc tối ưu hóa chi phí định tuyến không chỉ giúp giảm thiểu tài nguyên sử dụng mà còn nâng cao chất lượng dịch vụ cho người dùng. Các nghiên cứu gần đây đã chỉ ra rằng việc áp dụng các thuật toán tối ưu có thể cải thiện đáng kể hiệu suất mạng.

1.1. Định nghĩa và đặc trưng của mạng ad hoc di động

Mạng ad hoc di động là một tập hợp các nút không dây có khả năng tự tổ chức và giao tiếp với nhau mà không cần sự hỗ trợ của cơ sở hạ tầng. Đặc trưng của mạng này bao gồm tính động, khả năng tự cấu hình và khả năng thích ứng với sự thay đổi của môi trường.

1.2. Vai trò của thuật toán tối ưu trong mạng ad hoc

Thuật toán tối ưu chi phí định tuyến giúp cải thiện hiệu suất mạng bằng cách giảm thiểu chi phí truyền thông và tăng cường khả năng phục hồi của mạng. Điều này đặc biệt quan trọng trong các tình huống khẩn cấp hoặc khi cơ sở hạ tầng bị hỏng.

II. Vấn đề và thách thức trong tối ưu chi phí định tuyến

Mặc dù có nhiều lợi ích, việc tối ưu chi phí định tuyến trong mạng ad hoc di động cũng gặp phải nhiều thách thức. Các vấn đề như độ tin cậy của liên kết, bão quảng bá và sự thay đổi liên tục của cấu trúc mạng là những yếu tố cần được xem xét. Những thách thức này có thể dẫn đến việc tăng chi phí định tuyến và giảm hiệu suất mạng.

2.1. Độ tin cậy của liên kết trong mạng ad hoc

Độ tin cậy của liên kết là một yếu tố quan trọng trong mạng ad hoc. Các liên kết có thể bị đứt do sự di chuyển của các nút, dẫn đến việc tăng chi phí định tuyến và giảm hiệu suất truyền thông.

2.2. Vấn đề bão quảng bá trong giao thức AODV

Bão quảng bá là một vấn đề phổ biến trong giao thức AODV, khi nhiều thông điệp quảng bá được gửi đồng thời, gây tắc nghẽn mạng. Điều này làm tăng chi phí định tuyến và giảm hiệu suất tổng thể của mạng.

III. Phương pháp tối ưu hóa chi phí định tuyến hiệu quả

Để giải quyết các vấn đề trên, nhiều phương pháp tối ưu hóa chi phí định tuyến đã được đề xuất. Các phương pháp này bao gồm việc sử dụng các bộ đếm thời gian, khám phá đường theo xác suất và định tuyến đa đường. Những phương pháp này không chỉ giúp giảm chi phí mà còn cải thiện hiệu suất mạng.

3.1. Sử dụng bộ đếm thời gian để tối ưu hóa

Phương pháp sử dụng bộ đếm thời gian giúp giảm thiểu số lượng thông điệp quảng bá cần thiết, từ đó giảm chi phí định tuyến. Bằng cách điều chỉnh thời gian gửi thông điệp, mạng có thể hoạt động hiệu quả hơn.

3.2. Khám phá đường theo xác suất

Khám phá đường theo xác suất cho phép các nút trong mạng lựa chọn đường đi tối ưu dựa trên xác suất thành công. Phương pháp này giúp cải thiện khả năng phục hồi của mạng và giảm thiểu chi phí định tuyến.

IV. Ứng dụng thực tiễn của thuật toán tối ưu chi phí định tuyến

Các thuật toán tối ưu chi phí định tuyến đã được áp dụng trong nhiều lĩnh vực khác nhau, từ quân sự đến cứu hộ thiên tai. Việc tối ưu hóa chi phí định tuyến không chỉ giúp cải thiện hiệu suất mạng mà còn đảm bảo thông tin được truyền tải một cách hiệu quả trong các tình huống khẩn cấp.

4.1. Ứng dụng trong quân đội

Trong quân đội, mạng ad hoc di động cho phép các đơn vị giao tiếp hiệu quả mà không cần cơ sở hạ tầng cố định. Việc tối ưu hóa chi phí định tuyến giúp cải thiện khả năng truyền thông trong các chiến dịch.

4.2. Ứng dụng trong cứu hộ thiên tai

Trong các tình huống thiên tai, mạng ad hoc di động có thể được triển khai nhanh chóng để hỗ trợ cứu hộ. Tối ưu hóa chi phí định tuyến giúp đảm bảo thông tin được truyền tải một cách nhanh chóng và hiệu quả.

V. Kết luận và tương lai của thuật toán tối ưu chi phí định tuyến

Việc tối ưu chi phí định tuyến trong mạng ad hoc di động là một lĩnh vực nghiên cứu quan trọng và đầy tiềm năng. Các nghiên cứu hiện tại đã chỉ ra rằng việc áp dụng các thuật toán tối ưu có thể cải thiện đáng kể hiệu suất mạng. Tương lai của lĩnh vực này hứa hẹn sẽ có nhiều phát triển mới, đặc biệt là trong bối cảnh công nghệ không ngừng tiến bộ.

5.1. Hướng phát triển trong nghiên cứu

Nghiên cứu trong lĩnh vực tối ưu chi phí định tuyến sẽ tiếp tục phát triển, với nhiều phương pháp mới được đề xuất. Các nghiên cứu này sẽ tập trung vào việc cải thiện hiệu suất mạng và giảm thiểu chi phí.

5.2. Tác động của công nghệ mới

Công nghệ mới như 5G và IoT sẽ có tác động lớn đến mạng ad hoc di động. Việc tích hợp các công nghệ này vào các thuật toán tối ưu sẽ mở ra nhiều cơ hội mới cho việc cải thiện hiệu suất mạng.

Trích đoạn nội dung tài liệu

Chương 1 trình bày tổng quan về mạng ad hoc, giao thức định tuyến AODV và một số phương pháp cải tiến cơ chế quảng bá thông tin định tuyến của giao thức AODV. Phương pháp và thuật toán cải tiến thuật toán quảng bá định tuyến dựa trên thông tin từ các nút lân cận sẽ được trình bày chi tiết trong Chương 2. Kết quả của việc mô phỏng, so sánh đánh giá hiệu năng của giao thức NKR – giao thức triển khai phương pháp cải tiến thuật toán quảng bá định tuyến dựa trên thông tin từ các nút lân cận so với một số giao thức có liên quan được trình bày trong Chương 3. Cuối cùng là phần kết luận đưa ra những tổng kết và hướng phát triển của luận văn.

TỔNG QUAN VỀ MẠNG AD HOC VÀ ỨNG DỤNG 1. Tổng quan về mạng ad hoc 1. Định nghĩa và đặc trưng của mạng ad hoc Theo định nghĩa của Tổ chức IETF (Internet Engineering Task Force), Mạng ad hoc không dây di động là một vùng tự trị (Autonomous System) của các bộ định tuyến được kết nối với nhau bằng liên kết không dây. Mỗi nút mạng vừa đóng vai trò là thiết bị đầu cuối vừa đóng vai trò là bộ định tuyến.

Các nút có thể di chuyển một cách tự do làm cho kiến trúc của mạng thay đổi liên tục. Minh họa mạng ad hoc di động Như vậy có thể thấy mạng ad hoc di động bao gồm 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.1 là một ví dụ minh họa cho một mạng ad hoc di động. 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à 4 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 ad hoc di động. Trong mạng ad hoc, liên kết giữa các nút mạng được đặc trưng bởi khoảng cách giữa các nút và tính sẵn sàng hợp tác để tạo thành mạng mặc dù là tạm thời. Để triển khai thành công được mạng ad hoc, thiết kế và công nghệ mạng phải đáp ứng được các yêu cầu sau:  Đảm bảo kết nối khi nút mạng di chuyển: Khoảng cách giữa các nút hoặc trạng thái ở gần nhau của chúng định nghĩa ranh giới mạng.

Chỉ cần hai hoặc nhiều nút chuyển động trong một bán kính nhất định là tạo thành một mạng ad-hoc. Chính sự chuyển động làm cho khoảng cách giữa các nút thay đổi gây ra bản chất đặc biệt (ad-hoc) của mạng.  Tính sẵn sàng hợp tác: Các nút ở trong khoảng cách đủ gần phải sẵn sàng hợp tác để tạo thành mạng. Nói cách khác, tự bản thân nút quyết định “online” hay “offline”.

 Mạng ngang hàng tạm thời: Tại bất cứ một thời điểm nào, mạng ad-hoc được xác định bởi các nút đang “online” và ở trong một khoảng cách nhất định. Một nút luôn có xu hướng tham gia hay biến mất khỏi mạng. Do đó, mạng được coi là tạm thời. Hơn nữa, do không có một cơ sở hạ tầng mạng cho trước, các nút trong mạng phải truyền thông theo kiểu ngang hàng (peer- to-peer).

Đặc điểm của mạng ad hoc Do ad hoc 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 ad hoc còn có một số đặc điểm nổi bật sau [11]:  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 ad hoc 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.  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 ad hoc 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 ad hoc hơn là trong mạng có dây truyền thống.

Ứng dụng của mạng ad hoc Mạng ad hoc có rất nhiều ưu thế so với các mạng truyền thống về mặt ứng dụng trong những điều kiện khó có thể triển khai được một cơ sở hạ tầng mạng cố định hoặc việc triển khai là không khả thi do những lý do về mặt thực hành (địa hình,…) hoặc do những lý do về kinh tế (chi phí cáp trong một không gian lớn, chi phí thiết lập nhiều điểm truy cập).  Ứng dụng trong quân đội Những thành tựu mới của công nghệ thông tin thường được áp dụng trong quân sự đầu tiên, và mạng không dây kiểu không cấu trúc cũng không phải là một ngoại lệ. Nhiều năm nay, quân đội đã sử dụng các mạng “packet radios” – một nguyên mẫu đầu tiên của mạng chuyển mạch gói không dây ngày nay. Mạng ad hoc thuần túy thường tuân theo một mô hình điểm ngẫu nhiên, các nút tự do di chuyển theo bất cứ hướng nào, với bất cứ tốc độ nào.

Trong mô hình mạng ad hoc cho quân đội, các nút phân nhóm theo bản chất tự nhiên của chúng khi chúng cùng thực hiện một nhiệm vụ cụ thể. Xu hướng di động ở đây là theo nhóm. Do đó, nếu đưa ra được một mô hình chuyển động theo nhóm, các vấn đề của mạng ad hoc sẽ trở nên cụ thể hơn (ví dụ: định tuyến, sử dụng các ứng dụng thời gian thực như tiếng nói, video,…), cho phép phát triển một giải pháp tối ưu.  Các ứng dụng trong cuộc sống Mạng ad hoc rất lý tưởng trong các trường hợp không có sẵn một cơ sở hạ tầng thông tin, tuy nhiên lại cần phải thành lập một mạng tạm thời nhằm trao đổi thông tin và hợp tác cùng làm việc.

7 Tại các vùng bị thiên tai, thảm họa, khó có thể có được một cơ sở hạ tầng về thông tin vững chắc. Hệ thống có trước đó rất có thể bị hỏng hoặc bị phá hủy hoàn toàn. Tại vùng có thảm họa, tất cả các phương tiện và hệ thống truyền thông đều bị phá hủy hoàn toàn. Mỗi chiếc xe của cảnh sát, cứu hỏa, cứu thương,… đều được trang bị như một thiết bị đầu cuối di động – là một phần của mạng ad-hoc.

Mỗi nhân viên 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 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 – đóng vai trò như router trên Internet.

Đối với ứng dụng chia sẻ tài nguyên trong hội họp, khác với cách làm truyền thống khi những người tham gia hội thảo muốn chia sẻ tài liệu cho nhau là gửi file đính kèm qua email hoặc sao chép qua các thiết bị lưu trữ thứ cấp có khả năng di động, tất cả những người tham dự hội thảo đều có thể sử dụng thiết bị di động để tạo thành một mạng ad-hoc trong suốt thời gian đó. Các thiết bị có thể truyền thông với nhau, truyền/nhận các tài liệu được sử dụng trong hội thảo. Khi hội thảo kết thúc, các thiết bị được tắt nguồn, mạng tự bị hủy bỏ. Đối với ứng dụng trong cuộc sống hàng ngày, môi trường mạng là mạng ad hoc thuần túy, tức là không có cơ sở hạ tầng về cáp, các thiết bị đầu cuối tự cấu hình để thành lập mạng, mà không có sự quản lý tập trung.

Mạng này có thể tự chia nhỏ thành các mạng con. Ví dụ như một mạng riêng giữa em học sinh và bạn của em, một mạng “chung” được khởi tạo bởi người muốn chia sẻ các chương trình trò chơi điện tử trên máy của anh ta. Hai mạng này được trộn lẫn vào nhau một cách linh động. Ví dụ minh họa mạng ad hoc trên xe bus  Mạng cảm biến 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ạng cảm biến là mạng gồm các nút cảm biến (sensor) – 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,. Trước đây mạng cảm biến thường bao gồm một lượng nhỏ các nút cảm biến được kết nối bằng cáp tới một trạm xử lý tập trung. Ngày nay, các nút mạng cảm biến thường là không dây, phân tán để vượt qua các trở ngại vật lý của môi trường, tiết kiệm năng lượng và do trong nhiều trường hợp không thể có được một hạ tầng có sẵn về năng lượng và truyền thông. Công nghệ mạng không dây kiểu không cấu trúc thường được áp dụng để triển khai mạng cảm biến do:  Các nút cảm biến được phân tán trong vùng không có sẵn cơ sở hạ tầng về truyền thông và năng lượng.

Các nút phải tự hình thành kết nối.