Tóm tắt Luận án Tiến sĩ Khoa học máy tính: Tối ưu hóa thời gian sống của một lớp mạng cảm biến không dây theo hướng tiếp cận xấp xỉ

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:36

Thêm vào BST

Báo xấu

9
lượt xem 6
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Tóm tắt Luận án Tiến sĩ Khoa học máy tính "Tối ưu hóa thời gian sống của một lớp mạng cảm biến không dây theo hướng tiếp cận xấp xỉ" được nghiên cứu với mục tiêu: Nghiên cứu về mạng cảm biến không dây, vấn đề tối ưu thời gian sống trong mạng cảm biến không dây; Nghiên cứu các kỹ thuật để giải quyết bài toán tối ưu thời gian sống cho hai lớp mạng ở trên; Nghiên cứu các phương pháp xây dựng kịch bản mạng, xây dựng các bộ dữ liệu, xây dựng các kịch bản thực nghiệm để đánh giá được hiệu quả của các thuật toán đề xuất.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Tóm tắt Luận án Tiến sĩ Khoa học máy tính: Tối ưu hóa thời gian sống của một lớp mạng cảm biến không dây theo hướng tiếp cận xấp xỉ

BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI Nguyễn Thị Tâm TỐI ƯU HÓA THỜI GIAN SỐNG CỦA MỘT LỚP MẠNG CẢM BIẾN KHÔNG DÂY THEO HƯỚNG TIẾP CẬN XẤP XỈ Ngành : Khoa học máy tính Mã số : 9480101 TÓM TẮT LUẬN ÁN TIẾN SĨ KHOA HỌC MÁY TÍNH Hà Nội - 2021
Công trình được hoàn thành tại: Trường Đại học Bách khoa Hà Nội Người hướng dẫn khoa học: 1. PGS.TS Huỳnh Thị Thanh Bình 2. PGS.TS Lê Trọng Vĩnh Phản biện 1: Phản biện 2: Phản biện 3: Luận án được bảo vệ trước Hội đồng đánh giá luận án tiến sĩ cấp Trường họp tại Trường Đại học Bách khoa Hà Nội Vào hồi . . . . . . .. giờ, ngày . . . .. tháng . . . .. năm . . . . . . . . . Có thể tìm hiểu luận án tại thư viện: 1. Thư viện Tạ Quang Bửu - Trường ĐHBK Hà Nội 2. Thư viện Quốc gia Việt Nam
DANH MỤC CÁC CÔNG TRÌNH ĐÃ CÔNG BỐ CỦA LUẬN ÁN 1. Nguyen Thi Tam, Huynh Thi Thanh Binh, Dinh Anh Dung, Tran Huy Hung, Le Trong Vinh (2019). “Prolong the Network Lifetime of Wireless Underground Sensor Networks by Optimal Relay Node Placement.” International Conference on the Applications of Evolutionary Computation (Part of EvoStar). Springer, Cham, 439-453. 2. Nguyen Thi Tam, Huynh Thi Thanh Binh, Dinh Anh Dung, Phan Ngoc Lan, Le Trong Vinh, Bo Yuan, Xin Yao (2019). “A hybrid clustering and evolutionary approach for wireless underground sensor network lifetime maximization.” Information Sciences 504, 372-393. Q1, IF 5.91. 3. Nguyen Thi Tam, Huynh Thi Thanh Binh, Vi Thanh Dat, Phan Ngoc Lan, Le Trong Vinh (2020). “Towards optimal wireless sensor network lifetime in three dimensional ter- rains using relay placement metaheuristics”. Knowledge-based systems. 206, 106407 Q1, IF 5.92. 4. Nguyen Thi Tam, Dinh Anh Dung, Tran Huy Hung, Huynh Thi Thanh Binh, Shui Yu (2020). “Exploiting relay nodes for maximizing wireless underground sensor network lifetime”. Applied Intelligence. 50(12), 4568-4585 Q2, IF 3.32. 5. Nguyen Thi Tam, Tran Quang Tuan, Huynh Thi Thanh Binh, Ananthram Swami, (2020). “Multifactorial evolutionary optimization for maximizing data aggregation tree lifetime in wireless sensor networks”. In Artificial Intelligence and Machine Learning for Multi-Domain Operations Applications II (Vol. 11413, p. 114130Z). International Society for Optics and Photonics. 6. Nguyen Thi Tam, Tran Son Tung (2020), “An Evolutionary Algorithm for Data Aggre- gation Tree Construction in Three-Dimensional Wireless Sensor Networks”, IEEE Region 10 Conference (TENCON), 732-737. 7. Nguyen Thi Tam, Tran Huy Hung, Huynh Thi Thanh Binh, Le Trong Vinh, (2021). A multi-objective evolutionary decomposition algorithm for optimizing lifetime in three- dimensional wireless sensor networks, Applied Soft Computing,107, p.107365, (Q1, IF 5.47, accepted). 8. Nguyen Thi Tam, Vi Thanh Dat, Phan Ngoc Lan, Huynh Thi Thanh Binh, Le Trong Vinh, and Ananthram Swami (2020). “Multifactorial evolutionary optimization to maxi- mize lifetime of wireless sensor network”, Information Sciences, Q1, IF 5.91, accepted. 9. Tran Cong Dao, Tran Huy Hung, Nguyen Thi Tam and Binh Huynh Thi Thanh.“A multifactorial evolutionary algorithm for minimum energy cost data aggregation tree in wireless sensor networks”. 2021 Congress on Evolutionary Computation (CEC). IEEE, 2021 (accepted).
MỞ ĐẦU Trong những năm gần đây, cùng với sự phát triển nhanh chóng của khoa học công nghệ, mạng cảm biến không dây (wireless sensor networks - WSNs) đã được nhiều nhà khoa học quan tâm nghiên cứu. WSNs là mạng liên kết các nút cảm biến (sensor nodes) với nhau nhờ các liên kết không dây như sóng vô tuyến, hồng ngoại [1]. Mỗi nút cảm biến có chức năng cảm nhận, thu thập, xử lý và truyền dữ liệu. Các nút này thường là các thiết bị đơn giản, nhỏ gọn, giá thành thấp được phân bố trên một phạm vi rộng lớn thường gọi là các khu vực cảm biến (sensor fields). Trong mạng cảm biến, dữ liệu sau khi được thu thập bởi các nút cảm biến sẽ được định tuyến đến các trạm cơ sở (base stations). Các trạm cơ sở sẽ gửi dữ liệu đến người dùng thông qua Internet hay vệ tinh. Các đặc tính như triển khai nhanh chóng, khả năng tự tổ chức và chịu lỗi đã cho thấy mạng cảm biến không dây là một công nghệ đầy triển vọng. Ngày nay, mạng cảm biến không dây được áp dụng trong các lĩnh vực khác của đời sống, từ các ứng dụng trong dân sự như: nông nghiệp, môi trường đến những ứng dụng trong quân sự như giám sát chiến trường, phát hiện vũ khí hóa học [2]. Một trong những đặc trưng riêng biệt của mạng cảm biến không dây chính là hạn chế về khả năng tính toán và năng lượng của các nút cảm biến, do các nút này sử dụng nguồn năng lượng pin hoặc ắc quy để tồn tại. Sau khi triển khai mạng, việc tiếp thêm năng lượng cho các nút cảm biến là không khả thi trong trường hợp mạng được triển khai trong những địa hình khắc nghiệt. Do đó, năng lượng của các cảm biến đóng một vai trò quan trọng, quyết định thời gian sống (thời gian tồn tại) của mạng. Trong nghiên cứu [3], các tác giả đưa ra nhiều định nghĩa khác nhau để tính thời gian sống của mạng dựa vào số lượng các nút còn hoạt động (còn sống) trong mạng. Trong đó, cách định nghĩa thời gian sống của mạng là thời gian từ khi khởi tạo mạng cho đến khi nút đầu tiên trong mạng hết năng lượng được nhiều tác giả sử dụng. Cách định nghĩa này phù hợp đối với các mạng mà vai trò của các nút cảm biến là như nhau, nếu một nút hết năng lượng thì việc phân tích dữ liệu thu thập được sẽ không còn chính xác. Hầu hết các nghiên cứu đã có đều tập trung vào việc tối ưu thời gian sống cho mạng cảm biến không dây trong địa hình hai chiều. Giả định này hợp lý đối với các ứng dụng mà các nút cảm biến được triển khai trên một địa hình tương đối đồng đều, độ cao của các nút không đáng kể so với bán kính truyền thông. Tuy nhiên, trong nhiều ứng dụng thực tế, khi triển khai mạng cần xem xét đến độ cao 1
và độ sâu các nút mạng. Vì vậy, trong luận án này, tác giả tập trung nghiên cứu bài toán tối ưu thời gian sống cho hai loại mạng: mạng cảm biến không dây ngầm (wireless underground sensor networks - WUSNs) với các nút cảm biến được đặt dưới đất và mạng cảm biến không dây địa hình ba chiều (wireless sensor networks in three dimensional terrains - WSN3D) với các nút cảm biến được đặt trong địa hình ba chiều. Nhiều bài toán tối ưu thời gian sống cho mạng WUSNs và mạng WSN3D là bài toán NP-hard. Có hai cách tiếp cận để giải bài toán dạng này: sử dụng thuật toán chính xác và sử dụng thuật toán xấp xỉ. Các thuật toán chính xác đảm bảo tìm được lời giải chính xác cho các bài toán tối ưu thời gian sống của mạng. Tuy nhiên, đối với những bài toán có kích thước dữ liệu lớn, phương pháp này là không khả thi. Việc áp dụng các thuật toán xấp xỉ được ưu tiên sử dụng. Mặc dù các thuật toán xấp xỉ chỉ tìm được lời giải gần đúng, nhưng thời gian thực hiện thuật toán là chấp nhận được cho mọi bộ dữ liệu. Mục tiêu nghiên cứu của luận án Trên cơ sở phân tích ở trên, tác giả chọn đề tài “Tối ưu hóa thời gian sống của một lớp mạng cảm biến không dây theo hướng tiếp cận xấp xỉ ” làm đề tài nghiên cứu cho luận án Tiến sĩ. Luận án hướng đến việc sử dụng các thuật toán meta-heuristic (một lớp các thuật toán xấp xỉ) để giải quyết bài toán tối ưu thời gian sống cho hai loại mạng: mạng WUSNs và mạng WSN3D. Các mục tiêu cụ thể trong luận án bao gồm: Mục tiêu thứ nhất của luận án là nghiên cứu về mạng cảm biến không dây, vấn đề tối ưu thời gian sống trong mạng cảm biến không dây. Đặc biệt, luận án đi sâu vào giải quyết vấn đề tối ưu thời gian sống của hai lớp mạng cảm biến không dây: WUSNs và WSN3D bằng việc sử dụng các nút chuyển tiếp. Mục tiêu thứ hai của luận án là nghiên cứu các kỹ thuật để giải quyết bài toán tối ưu thời gian sống cho hai lớp mạng ở trên. Bởi vì các bài toán được nghiên cứu trong luận án đều là các bài toán NP-hard nên tác giả tiếp cận các giải thuật gần đúng để giải quyết các bài toán này. Mục tiêu thứ ba của luận án là nghiên cứu các phương pháp xây dựng kịch bản mạng, xây dựng các bộ dữ liệu, xây dựng các kịch bản thực nghiệm để đánh giá được hiệu quả của các thuật toán đề xuất. Phạm vi nghiên cứu Trong mạng cảm biến không dây, các nút cảm biến gần nút nguồn/trạm cơ sở có khả năng bị cạn kiệt nguồn năng lượng nhanh hơn do chúng phải định tuyến 2
dữ liệu nhiều hơn. Phương pháp định tuyến truyền thống được sử dụng là phương pháp phân cụm. Trong phương pháp này, các cảm biến sẽ được phân thành các cụm, trong mỗi cụm sẽ có một nút đóng vai trò là cụm đầu. Dữ liệu từ các cảm biến thay vì được gửi trực tiếp đến trạm cơ sở hoặc các nút nguồn sẽ được gửi thông qua các cụm đầu. Cụm đầu chịu trách nhiệm điều hướng hoạt động của các thành viên trong cụm và giao tiếp với các cụm đầu khác hoặc trạm cơ sở. Tuy nhiên, cụm đầu phải chuyển tiếp dữ liệu của tất cả các nút trong cụm sẽ dẫn đến tiêu hao năng lượng nhanh hơn các nút khác. Gần đây, các phương pháp sử dụng các nút chuyển tiếp (relay nodes) để kéo dài thời gian sống của mạng đã được các nhà nghiên cứu quan tâm. Ý tưởng của phương pháp này là sử dụng nút chuyển tiếp để giảm khoảng cách truyền thông từ các nút cảm biến đến trạm cơ sở, từ đó có thể giảm năng lượng tiêu thụ. Các nút chuyển tiếp có nguồn năng lượng giới hạn nên cần cân bằng tải giữa chúng để đảm bảo không có nút nào bị quá tải. Trong các nghiên cứu trước đó, vấn đề này bị bỏ qua, các nút cảm biến được tự động gán cho các nút chuyển tiếp có khoảng cách ngắn nhất hoặc sự suy hao trong quá trình truyền dẫn là ít nhất. Điều này dẫn đến sự phân bố không đồng đều của các nút. Một vài nút chuyển tiếp sẽ phải xử lý nhiều do ở gần nhiều nút cảm biến hơn. Trong khi đó, một vài nút chuyển tiếp khác có thể không có bất kì các nút cảm biến nào được kết nối đến. Cân bằng tải là cách tiếp cận tốt nhất để tăng thông lượng và làm giảm tắc nghẽn trong mạng. Ý tưởng cân bằng tải là chỉ định một khối lượng công việc như nhau cho tất cả các nút chuyển tiếp. Hai cách cân bằng tải cho nút chuyển tiếp có thể có là cân bằng tải về số lượng và cân bằng tải về năng lượng. Trong cách cân bằng tải về số lượng, mỗi nút chuyển tiếp sẽ thực hiện việc tập hợp dữ liệu của một số các nút cảm biến như nhau. Trong cách cân bằng tải về năng lượng, các nút chuyển tiếp sẽ tiêu thụ một lượng năng lượng như nhau. Các nghiên cứu liên quan đến việc triển khai nút chuyển tiếp để kéo dài thời gian sống của mạng có thể chia thành hai loại: có ràng buộc và không có ràng buộc. Các bài toán không có ràng buộc là bài toán triển khai các nút chuyển tiếp tại các vị trí bất kỳ trên địa hình. Ngược lại, trong bài toán triển khai có ràng buộc, các nút chuyển tiếp chỉ được triển khai tại các vị trí xác định trước trên địa hình. Các vị trí này không nằm trong các lỗ hổng vật lý của mạng như sông, suối, ao, hồ,... Từ khía cạnh cấu trúc định tuyến, việc triển khai nút chuyển tiếp theo cách này được phân thành hai loại: kiến trúc đơn tầng (single-tiered ) và kiến trúc hai tầng (two-tiered ). Trong kiến trúc đơn tầng, cả nút cảm biến (SNs) và nút chuyển tiếp (RNs) đều có thể gửi gói tin. Trong khi 3
đó, đối với kiến trúc hai tầng chỉ RNs chuyển tiếp gói tin và SNs chỉ có vai trò thu thập dữ liệu và truyền dữ liệu đến RNs (hoặc BS nếu chúng có thể kết nối trực tiếp đến BS). Luận án tập trung vào giải quyết bài toán có ràng buộc theo cả hai loại kiến trúc mạng. Chi tiết về phạm vi nghiên cứu của luận án được đưa ra như sau: Tối ưu hóa thời gian sống của mạng WUSNs: luận án nghiên cứu bài toán tối ưu thời gian sống của mạng WUSNs với kiến trúc mạng hai tầng dựa trên mô hình tổn thất truyền thông. Mô hình này thường được sử dụng trong các loại mạng cảm biến không dây ngầm. Việc tối ưu thời gian sống của mạng cảm biến không dây dựa trên mô hình tổn thất truyền thông được nhiều các nhà nghiên cứu quan tâm [4, 5, 6, 7]. Lý do cho việc sử dụng mô hình này là do năng lượng tiêu thụ của các nút cảm biến tỉ lệ thuận với tổn thất truyền thông. Việc tối ưu tổn thất truyền thông sẽ dẫn đến tối ưu năng lượng tiêu thụ của các nút, nhờ đó kéo dài thời gian sống của mạng. Đối với với các mạng cảm biến không dây ngầm, việc truyền tín hiệu trong đa môi trường sẽ dẫn đến sự suy giảm của tín hiệu do sự hấp thụ của nhiều yếu tố trong đất và sự phản xạ, khúc xạ ở bền mặt. Sự suy giảm trong môi trường đất phụ thuộc vào một số yếu tố như thành phần của đất, mật độ, hàm lượng nước và thể tích. Ngoài ra, các đặc tính lan truyền của sóng điện từ ở trong đất cũng khác biệt khá nhiều so với trong không khí. Sóng điện từ sẽ bị suy hao do ảnh hưởng của khoảng cách truyền thông. Tối ưu hóa thời gian sống của mạng WSN3D: luận án nghiên cứu bài toán tối ưu hóa thời gian sống của mạng WSN3D theo cả hai loại kiến trúc mạng: đơn tầng và hai tầng dựa trên mô hình suy hao năng lượng. Năng lượng của một nút cảm biến tiêu thụ chủ yếu cho các nhiệm vụ: truyền thông, xử lý dữ liệu, cảm biến dữ liệu [8]. Có nhiều mô hình suy hao năng lượng đã được đề xuất, trong đó mô hình suy hao năng lượng dựa vào khoảng cách đã được nhiều nhà nghiên cứu sử dụng [9, 10, 11, 12]. Trong mô hình này, năng lượng tiêu thụ chủ yếu được tính dựa vào sự suy hao năng lượng khi truyền dữ liệu trong một khoảng cách nhất định. Mô hình này dùng cho các mạng cảm biến được triển khai ở phía trên mặt đất trong địa hình ba chiều. Ngoài ra, trong giao tiếp không dây, hai nút có thể không kết nối được với nhau do hai nguyên nhân chính. Lý do thứ nhất là khoảng cách giao tiếp quá lớn. Lý do thứ hai là đường tầm nhìn (line-of-sight) giữa hai nút có nhiều vật cản. Luận án tuân theo giả định đầu tiên, có nghĩa là, hai nút trong mạng có thể kết nối được với nhau nếu khoảng cách giữa chúng không quá lớn (khoảng cách giữa hai nút nhỏ hơn bán kính truyền thông). 4
Các đóng góp chính của luận án Bài toán 1: tối ưu hóa việc triển khai các nút chuyển tiếp để kéo dài thời gian sống của mạng cảm biến không dây ngầm (WUSNs) dựa trên mô hình tổn thất truyền thông (bài toán MRP). Bài toán này sẽ xem xét ràng buộc cân bằng tải về số lượng cho các nút chuyển tiếp. Trong nghiên cứu [7], các tác giả đề xuất cách tiếp cận hai pha với sáu thuật toán heuristic để giải quyết bài toán MRP. Nhược điểm của các thuật toán đề xuất là chia bài toán thành hai pha riêng biệt, các nút chuyển tiếp đã được lựa chọn trong pha thứ nhất sẽ không thể được thay đổi trong pha thứ hai. Điều này dẫn đến việc, nếu chọn các vị trí không tốt để đặt các nút chuyển tiếp sẽ dẫn đến một lời giải có chất lượng không tốt. Do đó, luận án đề xuất các thuật toán để khắc phục nhược điểm của 6 thuật toán đã có: Đề xuất thuật toán tham lam dựa trên tìm kiếm chùm tia với hàm Genitor (BGS) để tạo ra nhiều lời giải cho bài toán MRP. Tuy nhiên, thuật toán BGS có hạn chế là cách lựa chọn các nút cảm biến để kết nối đến nút chuyển tiếp trong mỗi bước là tham lam. Cách lựa chọn tham lam này chưa chắc đã dẫn đến một lời giải tối ưu toàn cục. Từ hạn chế của thuật toán BGS, luận án đề xuất thuật toán di truyền với khởi tạo phân cụm (MXFGA) để giải quyết bài toán. Ý tưởng của cách tiếp cận này là nếu biết chính xác các vị trí được lựa chọn để đặt nút chuyển tiếp, chúng ta có thể tìm được cách kết nối giữa các nút chuyển tiếp và các nút cảm biến sao cho giá trị tổn thất truyền thông lớn nhất của các cặp kết nối tìm được là nhỏ nhất. Thuật toán MXFGA có nhược điểm là thời gian chạy khá lâu do độ phức tạp của khởi tạo phân cụm và thuật toán di truyền. Ngoài ra, các toán tử lai ghép và đột biến cũng làm thay đổi khá nhiều cấu trúc cụm ban đầu. Để khắc phục hạn chế của BGS và MXFGA, luận án đề xuất phương pháp dựa trên sự kết hợp của thuật toán tìm kiếm chùm tia với hàm phân phối Boltzmann để tạo ra các phương án khả thi cho bài toán tối ưu hóa thời gian sống của mạng. Các cặp kết nối giữa các nút cảm biến và các nút chuyển tiếp sẽ được tìm chính xác bằng cách đưa về bài toán tìm cặp ghép trên đồ thị. Bài toán 2: tối ưu hóa đa mục tiêu việc triển khai các nút chuyển tiếp để kéo dài thời gian sống của mạng cảm biến không dây địa hình ba chiều (bài toán ORP3D) dựa trên mô hình suy hao năng lượng. Bài toán này sẽ xem xét việc cân bằng tải về năng lượng cho các nút chuyển tiếp. Hai cách tiếp cận được đề xuất 5
để giải quyết bài toán này: Đề xuất phương pháp dựa trên tổng trọng số để đưa bài toán đa mục tiêu ORP3D về bài toán tối ưu hóa đơn mục tiêu (OSA3D). Luận án đề xuất mô hình quy hoạch nguyên để tìm được cận dưới của lời giải. Cuối cùng, thuật toán tìm kiếm cục bộ dựa trên luồng cực đại được đề xuất để giải quyết bài toán. Đề xuất thuật toán tiến hóa đa mục tiêu dựa trên phân rã để tìm biên Pareto xấp xỉ biên tối ưu. Bài toán 3: tối ưu hóa thời gian sống cho các loại mạng cảm biến không dây trong địa hình ba chiều với các cấu trúc khác nhau. Luận án đề xuất thuật toán tiến hóa đa nhân tố với cách mã hóa Netkeys để giải quyết bài toán. Cấu trúc của luận án Ngoài phần mở đầu và phần kết luận, nội dung luận án được trình bày trong ba chương như sau: Chương 1: cơ sở lý thuyết. Chương này trình bày cơ sở lý thuyết của bài toán tối ưu, các phương pháp giải bài toán tối ưu đơn mục tiêu và đa mục tiêu. Ngoài ra, các nghiên cứu liên quan đến bài toán tối ưu hóa thời gian sống của mạng cảm biến không dây cũng được trình bày. Chương 2: tối ưu hóa thời gian sống của mạng cảm biến không dây dựa trên mô hình tổn thất truyền thông. Trong chương này, luận án nghiên cứu bài toán triển khai các nút chuyển tiếp để tối ưu thời gian sống của mạng cảm biến không dây ngầm dựa trên mô hình tổn thất truyền thông nhằm đảm bảo ràng buộc cân bằng tải về số lượng giữa các nút chuyển tiếp. Luận án đề xuất ba cách tiếp cận để giải quyết bài toán. Chương 3: tối ưu hóa thời gian sống của mạng cảm biến không dây dựa trên mô hình suy hao năng lượng. Trong chương này, luận án nghiên cứu hai bài toán. Bài toán thứ nhất là bài toán đa mục tiêu triển khai các nút chuyển tiếp để tối ưu hóa thời gian sống của mạng trong địa hình ba chiều. Bài toán này có hai mục tiêu chính: tối thiểu số lượng các nút chuyển tiếp được sử dụng và tối thiểu giá trị tiêu thụ năng lượng tối đa của các nút trong mạng. Để giải quyết bài toán này, hai cách tiếp cận được đề xuất. Bài toán thứ hai là bài toán tối ưu thời gian sống của các mạng có cấu trúc khác nhau: mạng đơn tầng và mạng hai tầng. Luận án đề xuất thuật toán tiến hóa đa nhân tố để giải quyết bài toán này. 6
Chương 1 CƠ SỞ LÝ THUYẾT 1.1 Bài toán tối ưu 1.1.1 Bài toán tối ưu đơn mục tiêu Bài toán tối ưu đơn mục tiêu được định nghĩa như sau: Định nghĩa 1.1 (Bài toán tối ưu đơn mục tiêu (single objective optimization problem - SOOP )[13]). Minimize/Maximize: f (x) (1.1) Ràng buộc: gi (x) ≤ 0 i = 1, ..., q (1.2) hj (x) = 0 j = 1, ..., p (1.3) x ∈ Ω. (1.4) trong đó: x = (x1 , x2 , ..., xn ) với xk là các biến liên tục hoặc rời rạc, k = 1, 2, ..., n. f (x): Rn → R là hàm mục tiêu của bài toán. gi (x) ≤ 0 là các ràng buộc bất đẳng thức, q là số ràng buộc bất đẳng thức. hj (x) = 0 là các ràng buộc đẳng thức, p là số ràng buộc đẳng thức. 1.1.2 Bài toán tối ưu đa mục tiêu Định nghĩa 1.2 (Bài toán tối ưu đa mục tiêu (multiobjective optimization problem - MOO) [14]). Minimize: F(x) = (f1 (x), f2 (x), ..., fm (x)) (1.5) Ràng buộc: gi (x) ≤ 0 i = 1, ..., q (1.6) hj (x) = 0 j = 1, ..., p (1.7) xl ≤ xk ≤ xu k k k = 1, ..., n. (1.8) trong đó, F(x) = (f1 (x), f2 (x), ..., fm (x)) là véc tơ hàm mục tiêu. x = (x1 , x2 , ..., xn ) là véc tơ lời giải. Giá trị xl là cận dưới và xu là cận trên. k k gi (x) ≤ 0 là các ràng buộc bất đẳng thức, q là số ràng buộc bất đẳng thức hj (x) = 0 là các ràng buộc đẳng thức, p là số ràng buộc đẳng thức. 7
1.1.2.1 Không gian thiết kế và không gian mục tiêu Định nghĩa 1.3 (Không gian thiết kế (design space)[14]). Không gian thiết kế Ω ∈ Rn của bài toán MOO là tập các véc tơ x thỏa mãn các ràng buộc 1.6, 1.7, 1.8 của bài toán. Định nghĩa 1.4 (Không gian mục tiêu (objective space) [14]). Không gian mục tiêu được định nghĩa là tập của các giá trị hàm mục tiêu tương ứng với các điểm trong không gian thiết kế. Z = {F(x)|x ∈ Ω}. 1.1.2.2 Tối ưu Pareto Định nghĩa 1.5 (Tối ưu Pareto [14]). Một điểm x∗ ∈ Ω được gọi là tối ưu Pareto nếu và chỉ nếu không tồn tại một điểm x trong không gian thiết kế Ω mà fi (x) ≤ fi (x∗ ) với mọi i và fi (x) < fi (x∗ ) với ít nhất một mục tiêu i, i = 1, ..., m. Định nghĩa 1.6 (Trội (dominated ) và không trội (non-dominated ) [14]). Một véc tơ của các mục tiêu F∗ = F(x∗ ) ∈ Z là không bị trội nếu và chỉ nếu không tồn tại một véc tơ F ∈ Z mà fi (x) ≤ fi (x∗ ) ∀i và fi (x) < fi (x∗ ) với ít nhất một i. Ngược lại, F∗ là bị trội. Định nghĩa 1.7 (Tập tối ưu Pareto (Pareto optimal set [14])). Là tập bao gồm tất cả các lời giải không bị trội bởi bất cứ một lời giải nào P = {x ∈ Ω|¬∃x ∈ Ω, F(x ) F(x)} (1.9) Định nghĩa 1.8 (Biên Pareto (Pareto front [14])). PF = {u = F(x)|x ∈ P} (1.10) Định nghĩa 1.9 (Tối ưu Pareto yếu [14]). Một điểm x∗ ∈ Ω được gọi là tối ưu Pareto yếu nếu và chỉ nếu không tồn tại một điểm x ∈ Ω mà fi (x) < fi (x∗ ) ∀i = 1, ..., m. Định nghĩa 1.10 (Điểm Utopia [14]). Một điểm F0 = {f1 , f2 , ..., fm } trong 0 0 0 không gian mục tiêu được gọi là điểm Utopia nếu fi0 = min{fi (x)|x ∈ Ω} ∀i = 1, ..., m. 1.1.3 Thuật toán di truyền 1.1.3.1 Giới thiệu Thuật toán thuật toán di truyền (Genetic Algorithms - GAs) được nghiên cứu trong [15, 16, 17, 18] 8
1.1.3.2 Sơ đồ của thuật toán di truyền 1.1.4 Thuật toán tiến hóa đa nhân tố Được đề xuất bởi [19] để giải quyết K nhiệm vụ tối ưu đồng thời. 1.1.4.1 Tiến hóa đa nhân tố Định nghĩa 1.11 (nhân tố chi phí (factorial cost) [19]). Chi phí Ψi của cá thể j pi đối với nhiệm vụ Tj là Ψi = λ.δj + fji ; trong đó λ là một hằng số phạt lớn, fji j i i và δj là giá trị mục tiêu và tổng số sự vi phạm ràng buộc tương ứng của pi đối với nhiệm vụ Tj . Do vậy, nếu pi là cá thể hợp lệ đối với nhiệm vụ Tj (sự vi phạm ràng buộc bằng 0) thì Ψi = fji . j Định nghĩa 1.12 (hạng của cá thể với từng tác vụ (factorial rank ) [19]). Hạng i rj của cá thể pi đối với nhiệm vụ Tj là thứ hạng của pi trong quần thể P sau khi được sắp sếp theo thứ tự tăng dần hoặc giảm dần của Ψi .j Định nghĩa 1.13 (hàm thích nghi vô hướng (scalar fitness) [19]). Danh sách các i i i xếp hạng của một cá thể pi trên K nhiệm vụ {r1 , r2 , . . . , rK } có thể được biến đổi sang một hình thức đơn giản hơn là giá trị hàm thích nghi vô hướng ϕi . Giá trị này được tính dựa trên thứ tự xếp hạng tốt nhất của pi trên tất cả các nhiệm vụ, i nghĩa là ϕi = 1/ min {rj }. j∈{1,2,...,K} Định nghĩa 1.14 (chỉ số kỹ năng phù hợp nhất (skill factor ) [19]). Nhân tố kĩ năng τi của cá thể pi là nhiệm vụ mà cá thể pi thực hiện hiệu quả nhất, nghĩa là i τi = arg min {rj }. j∈{1,2,...,K} Định nghĩa 1.15 (tối ưu đa nhân tố (multifactorial optimality) [19]). Một cá thể p∗ , với một danh sách các giá trị mục tiêu {f1 , f2 , ..., fK }, được xem là tối ưu hóa ∗ ∗ ∗ trong ngữ cảnh đa nhân tố nếu và chỉ nếu ∃j ∈ {1, 2, ..., K} sao cho fj∗ ≤ fj (xj ) đối với mọi xj khả thi trong Xj . 1.1.4.2 Thuật toán tiến hóa đa nhân tố 1.2 Một số thuật toán giải bài toán tối ưu đa mục tiêu 1.2.1 Thuật toán di truyền sắp xếp không trội Thuật toán di truyền sắp xếp không trội (non-dominated sorting genetic al- gorithm II - NSGA-II ) được giới thiệu lần đầu tiên vào năm 2000 bởi Deb và Agarwal [20] để giải quyết các bài toán tối ưu đa mục tiêu. 9
1.2.2 Thuật toán tiến hóa đa mục tiêu dựa trên phân rã Thuật toán đa mục tiêu dựa trên phân rã (multiobjective evolutionary algorithm based on decomposition- MOEAD) là thuật toán tiến hóa đầu tiên vào năm 2007 bởi Zang và Li dựa trên ý tưởng tổng hợp các hàm mục tiêu [21]. Phần này sẽ trình bày tổng quan về MOEAD. 1.2.3 Các độ đo đa mục tiêu Phần này trình bày một số độ đo phổ biến thường được sử dụng trong các bài toán tối ưu đa mục tiêu [22]: C -metric, N DS , HV -metric, ∆ - metric. 1.2.4 Bài toán tối ưu thời gian sống cho mạng cảm biến không dây ngầm 1.3 Bài toán tối ưu thời gian sống của mạng cảm biến không dây 1.3.1 Định nghĩa thời gian sống của mạng Thời gian sống là một trong những thách thức quan trọng của mạng cảm biến không dây. Có nhiều cách định nghĩa thời gian sống của mạng dựa vào các yếu tố khác nhau như: i) thời gian sống của mạng dựa vào số nút còn sống [3, 23, 24, 25, 26], ii) thời gian sống của mạng dựa vào bao phủ, kết nối [3, 26, 27, 28, 29]; iii) thời gian sống dựa vào thu thập dữ liệu [3, 26, 30, 31]. Trong luận án này, thời gian sống của mạng được tính dựa vào số lượng các nút còn sống trong mạng. Thời gian sống của mỗi nút trong mạng được tính dựa vào hai yếu tố: năng lượng tiêu thụ và năng lượng còn lại sau một khoảng thời gian. Theo cách tính này, có ba định nghĩa được các tác giả trong nghiên cứu [3] đưa ra: Định nghĩa 1.16. [3] Xét một mạng bao gồm n nút cảm biến được triển khai trong một khu vực mục tiêu. Thời gian sống của mạng là thời gian từ khi khởi tạo mạng đến khi nút đầu tiên trong n nút hết năng lượng. Định nghĩa 1.17. [3] Xét một mạng bao gồm n nút cảm biến được triển khai trong một khu vực mục tiêu. Thời gian sống của mạng là thời gian từ khi khởi tạo mạng đến khi n − k + 1 nút trong mạng hết năng lượng. Định nghĩa 1.18. [3] Xét một mạng bao gồm n nút cảm biến được triển khai trong một khu vực mục tiêu. Tập n nút này được chia làm hai loại: m nút quan trọng và n − m các nút không quan trọng. Thời gian sống của mạng là thời gian từ khi khởi tạo mạng đến khi n − k + 1 nút trong n − m nút không quan trọng hết năng lượng và không có bất cứ nút nào trong m nút quan trọng hết năng lượng. 10
1.3.2 Bài toán tối ưu thời gian sống cho mạng cảm biến không dây ngầm 1.3.2.1 Mô hình tổn thất truyền thông Có hai cấu trúc được triển khai trong WUSNs cấu trúc ngầm hoặc cấu trúc lai [4, 5, 6, 7, 32, 33]. Sau khi triển khai các nút cảm biến, việc tiếp thêm năng lượng cho các nút là không khả thi trong các trường hợp mạng cảm biến được triển khai trong những địa hình mà con người khó tiếp cận được. Do đó, năng lượng của các cảm biến đóng một vai trò quan trọng, quyết định thời gian sống của mạng. Một nút cảm biến tiêu thụ năng lượng chủ yếu cho việc truyền và nhận dữ liệu [34], [35, 36]. 1.3.2.2 Các nghiên cứu liên quan Các nghiên cứu liên quan đến bài toán tối ưu đơn mục tiêu triển khai các nút chuyển tiếp có thể được phân chia làm hai loại: không có ràng buộc [37], [38], [39],[40] và có ràng buộc [41], [42, 43], [44], [45], [46]. 1.3.3 Bài toán tối ưu thời gian sống cho mạng cảm biến không dây địa hình ba chiều 1.3.3.1 Mô hình suy hao năng lượng Phần này xem xét mô hình tổn thất khi truyền dữ liệu khoảng cách xa, và tổn thất khi truyền dữ liệu khoảng cách gần được nghiên cứu [8, 9, 10, 11, 12, 47, 48, 49, 50] 1.3.3.2 Các nghiên cứu liên quan Tối ưu hóa đóng một vai trò qua trọng trong WSNs. Bài toán tối ưu trong mạng WSNs có thể phân loại thành: bài toán tối ưu đơn mục tiêu và bài toán tối ưu đa mục tiêu [51]. Mục đích của tối ưu hóa đơn mục tiêu là cực tiểu hoặc cực đại một mục tiêu nào đó dưới các ràng buộc khác nhau. Trong khi tối ưu hóa đa mục tiêu, nhiều mục tiêu cần được tối ưu hóa một cách đồng thời. Các mục tiêu này có thể xung đột nhau, có nghĩa là việc tối ưu một mục tiêu có thể dẫn đến việc giảm tính tối ưu của các mục tiêu còn lại. Bài toán tối ưu đa mục tiêu liên quan đến thời gian sống của mạng/năng lượng tiêu thụ đã được các nhà nghiên cứu quan tâm trong thời gian gần đây [52, 53, 54],[55], [56], [57, 58, 59], [60], [61, 62], [63], [64], [65]. 1.4 Kết luận chương 11
Chương 2 TỐI ƯU HÓA THỜI GIAN SỐNG CỦA MẠNG CẢM BIẾN KHÔNG DÂY DỰA TRÊN MÔ HÌNH TỔN THẤT TRUYỀN THÔNG 2.1 Đặt vấn đề Mảng cảm biến không dây ngầm có nhiều ứng dụng trong thực tế [66, 67], [68, 69]. Bài toán tối ưu thời gian sống của mạng cảm biến không dây ngầm được các nhà nghiên cứu trong thời gian gần đây do các nút cảm biến được triển khai ở dưới đất khi bị cạn kiện nguồn năng lượng thì rất khó có thể được sạc lại. Chương này đi sâu vào giải quyết bài toán triển khai các nút chuyển tiếp trong mạng cảm biến không dây ngầm để kéo dài thời gian sống của mạng. 2.2 Phát biểu bài toán Bài toán 1 (Bài toán đặt các nút chuyển tiếp kéo dài thời gian sống của mạng và đảm bảo cân bằng tải (Min-Max Relay Placement Problem - MRP )). Cho một tập các cảm biến S = {s1 , s2 , ..., sn } và tập các vị trí khả thi để đặt các nút chuyển tiếp L = {l1 , l2 , ..., lm }. Bài toán yêu cầu tìm y vị trí đặt các nút chuyển tiếp để tối ưu hóa thời gian sống của mạng thỏa mãn các ràng buộc: Mỗi nút cảm biến chỉ kết nối đến duy nhất một nút chuyển tiếp Mỗi nút chuyển tiếp tải đúng n y cảm biến (giả sử n chia hết cho y). 2.3 Thuật toán đề xuất 2.3.1 Thuật toán tìm kiếm chùm tia với hàm Genitor Thuật toán tìm kiếm chùm tia với hàm Genitor (Beam Genitor Search - BGS ) lấy cảm hứng từ phương pháp tìm kiếm chùm tia (Beam Search - BS ) [70], trong đó một lời giải hoàn chỉnh sẽ được tìm thấy bằng cách xây dựng và hoàn thiện các lời giải bộ phận (lời giải thành phần). Từ trạng thái ban đầu (chưa chọn vị trí nào để đặt các nút chuyển tiếp) có thể đi theo m nhánh (tương ứng với m cách lựa chọn), mỗi cách khác nhau chỉ ở cách đặt của một nút mới. Mỗi nhánh trên lại có m − 1 cách đặt thêm các nút chuyển tiếp thứ hai. Lặp lại quá trình như vậy, chúng ta sẽ tìm được tất cả các lời giải có thể có của bài toán. 12
Cụ thể, thuật toán BGS chia quá trình tìm kiếm thành y + 1 bước. Bước đầu tiên xuất phát từ một phương án mà không có một vị trí nút chuyển tiếp nào được lựa chọn. Từ bước thứ hai trở đi sẽ thực hiện hai nhiệm vụ chính: Thêm vị trí lj ∈ L vào để đặt các nút chuyển tiếp; Đối với mỗi cách chọn lj , n nút cảm biến mà có tổn thất truyền thông nhỏ y nhất đến lj (trong số những cảm biến chưa được gán tới bất cứ một nút chuyển tiếp nào) sẽ được lựa chọn để kết nối đến lj . Quá trình này lặp lại cho đến khi chọn đủ y nút chuyển tiếp được chọn. Theo cách sinh này, lời giải cuối cùng sẽ đáp ứng các ràng buộc của bài toán: i) có y nút chuyển tiếp, ii) mỗi nút chuyển tiếp sẽ kết nối được đến n/y cảm biến, iii) mỗi nút cảm biến sẽ chỉ kết nối đến được một nút chuyển tiếp. Thứ tự lựa chọn lj sẽ ảnh hưởng đến hiệu quả của thuật toán, vì mỗi hoán vị của L sẽ dẫn đến các lời giải với các chất lượng khác nhau. Việc lựa chọn những lời giải đưa vào lần lặp sau sẽ dựa trên hàm phân phối xác suất Genitor [71]. Sau quá trình trên, chúng ta sẽ thu được một tập gồm c lời giải hoàn chỉnh cho bài toán. Tập này có thể vẫn chứa những lời giải có giá trị tổn thất truyền thông cao. Một thuật toán tham lam được đề xuất để giảm giá trị của tổn thất truyền thông cho các lời giải này. Ý tưởng chính của thuật toán tham lam này là tìm cách cải thiện các lời giải đã có bằng cách thay đổi kết nối giữa các nút chuyển tiếp và các nút cảm biến. 2.3.2 Thuật toán di truyền với khởi tạo dựa trên phâm cụm 2.3.2.1 Biểu diễn cá thể Thuật toán di truyền với khởi tạo phân cụm (Maxium Flow-based Genetic Al- gorithm - MXFGA) mã hóa mỗi cá thể là một chuỗi nhị phân x = (x1 , x2 , ..., xm ), trong đó xj = 1 nếu vị trí lj được chọn để đặt các nút chuyển tiếp, xj = 0 nếu ngược lại. 2.3.2.2 Khởi tạo quần thể Thuật toán MXFGA sử dụng hai loại khởi tạo: khởi tạo ngẫu nhiên và thuật toán khởi tạo dựa trên phân cụm (Clustering-based heuristic for relay node selec- tion - CluRNS). 2.3.2.3 Hàm thích nghi của các cá thể trong quần thể Phần này đề xuất một cách tính hàm thích nghi chính xác cho cá thể dựa vào việc đưa bài toán xác định kết nối cho các nút cảm biến và nút chuyển tiếp thỏa mãn cân bằng tải (LBSNA) về bài toán luồng cực đại với chi phí cực tiểu (Maxium Flow with Min-max Cost - MXF-MC). 13
Bổ đề 2.3.1. Lời giải tối ưu của bài toán MXF-MC có thể chuyển về lời giải của gán kết nối cho các nút cảm biến đảm bảo cân bằng tải ( Load Balanced Sensor Node Assignment - LBSNA) trong thời gian đa thức. Định lý 2.3.2. Bài toán LBSNA có thể giải được trong thời gian đa thức. 2.3.2.4 Các toán tử di truyền 2.3.2.5 Lựa chọn Thuật toán MXFGA sử dụng chiến lược lựa chọn tranh đấu để chọn các con cháu cho thế hệ sau [72]. 2.3.3 Thuật toán tìm kiếm chùm tia và cặp ghép trong đồ thị 2.3.3.1 Tìm kiếm chùm tia dựa trên phân phối Boltzmann Đối với thuật toán tìm kiếm chùm tia dựa trên phân phối Boltzmman và cặp ghép trong đồ thị (Beam Boltzmann Search and Maximum Bipartite Matching Sensor Nodes Reassignment - BMBM), việc lựa chọn các lời giải sẽ phụ thuộc vào phân phối Boltzmann [73]. 2.3.3.2 Tìm kết nối chính giữa các cặp nút dựa trên bài toán tìm cặp ghép cực đại với chi phí cực tiểu Định nghĩa 2.1. Cho một tập R = {r1 , r2 , ..., ry }, một tập Rh (h = n/y) được định nghĩa như sau: 1 2 h 1 2 h 1 2 h Rh = {r1 , r1 , ..., r1 , r2 , r2 , ..., r2 , ry , ry , ..., ry } trong đó, k k rj = rj ∀rj ∈ R, rj ∈ Rh . Một đồ thị hai phía G(V, E, w) được xây dựng như sau: V là tập các đỉnh: V = S ∪ Rh E là tập các cạnh: k E = {(sj , rj )}, ∀1 ≤ i ≤ n, 1 ≤ j ≤ y, 1 ≤ k ≤ h w là ma trận trọng số biểu diễn cho tổn thất truyền thông giữa các cạnh x x w(si , rj ) = tirj , ∀(si , rj ) ∈ E 14
Bài toán 2 (Bài toán tìm cặp ghép cực đại với chi phí cực tiểu). Cho đồ thị G(V, E, w) với hai tập đỉnh riêng biệt S và Rh . Bài toán đặt ra là tìm cặp ghép cực đại trên đồ G sao cho giá trị trọng số lớn nhất tìm được là nhỏ nhất. Định lý 2.3.3. Bài toán 2 có thể giải được trong thời gian đa thức. 2.4 Thực nghiệm 2.4.1 Dữ liệu thực nghiệm Các thực nghiệm được tiến hành trên hai tập dữ liệu: 1 tập dữ liệu nhỏ gồm 30 bộ trên địa hình kích thước 500m × 500m, và 1 tập dữ liệu lớn 30 bộ trên địa hình kích thước 1000m × 1000m (địa hình này có kích thước tương tự như trong nghiên cứu[7]). Mỗi tập gồm sáu kịch bản dữ liệu. 2.4.2 Cài đặt thực nghiệm 2.4.3 Tiêu chí đánh giá 2.4.4 So sánh và đánh giá kết quả thực nghiệm 2.4.4.1 Thực nghiệm 1: đánh giá ảnh hưởng của tỉ lệ khởi tạo CluRNS trong thuật toán MXFGA 2.4.4.2 Thực nghiệm 2: đánh giá sự ảnh hưởng của các tham số trong thuật toán BMBM 2.4.4.3 Thực nghiệm 3: đánh giá kết quả chung của các thuật toán đề xuất Kết quả của kịch bản 1: Trong kịch bản dữ liệu này, các nút cảm biến và nút chuyển tiếp được rải ngẫu nhiên trên địa hình. Kịch bản này tương tự như kịch bản được sinh ra trong [7]. Các thuật toán đề xuất gồm BGS, MXFGA và BMBM cho kết quả tốt hơn Yuan 5/5 bộ dữ liệu của tập dữ liệu nhỏ và 5/5 bộ dữ liệu của tập dữ liệu lớn. Cụ thể, đối với tập dữ liệu nhỏ, các thuật toán BGS, MXFGA và BMBM cải thiện lần lượt 8.2%, 11.3% và 11.02% so với kết quả của Yuan. Trên tập dữ liệu lớn, các con số này là 9.46%, 13.86% và 12.57%. Kết quả của kịch bản 2: Đối với kịch bản 2, các nút cảm biến rải gần về phía biên, trong khi đó các nút chuyển tiếp được rải ngẫu nhiên trên địa hình. Kịch bản này phù hợp với các ứng dụng của mạng cảm biến mà các nút cảm biến được triển khai bao quanh khu vực mục tiêu. Các bộ dữ liệu trong loại này có xu hướng phân chia một cách rõ ràng giữa các vị trí của nút chuyển tiếp tốt đặt gần biên và các vị trí của các nút 15
chuyển tiếp không tốt đặt gần tâm địa hình. Điều này cho thấy rõ hơn tính hiệu quả của phương pháp chọn nút chuyển tiếp. Thuật toán BGS cải thiện lần lượt là 10.56% và 16.52% so với kết quả của Yuan trên tập dữ liệu nhỏ và tập dữ liệu lớn. Các kết quả của thuật toán MXFGA là 12.96% và 19.40%, của thuật toán BMBM là 15.82% 20.81% trên tập dữ liệu nhỏ và tập dữ liệu lớn. Đối với loại dữ liệu này, thuật toán BMBM cải thiện kết quả trung bình so với MXFGA khoảng 3.29% trên các bộ dữ liệu thuộc tập dữ liệu nhỏ và 1.75% trên các bộ dữ liệu thuộc tập dữ liệu lớn. Kết quả của kịch bản 3: n Kịch bản dữ liệu này tạo ra 2×y cụm, mỗi cụm có 2 × y các cảm biến. Dữ liệu trong kịch bản này phù hợp với các ứng dụng mà mạng ban đầu sẽ chia thành các khu vực, trong đó, mỗi khu vực được giám sát bởi một nhóm các cảm biến. Loại dữ liệu này dự kiến sẽ tốt cho phương pháp phân cụm được đưa ra trong luận án. Bởi vì phân phối của các nút cảm biến gần giống với mô hình các nhóm cảm biến. Thuật toán BMBM cho kết quả tốt nhất trên tập dữ liệu nhỏ. Tổn thất truyền thông thu được của thuật toán BMBM là 105.29 so với tổn thất truyền thông tốt nhất trên tất cả các kịch bản dữ liệu còn lại là 105.92. Tuy nhiên, trên tập dữ liệu lớn, thuật toánMXFGA thu được kết quả tổn thất truyền thông tốt hơn là 124.31, trong khi BMBM là 126.76. Thuật toán BGS cải thiện lần lượt 17.66% và 11.95% so với Yuan trên tập dữ liệu nhỏ và trên tập dữ liệu lớn. Có thể thấy rằng thuật toán MXFGA và BMBM cho kết quả tương tự nhau trên tập dữ liệu nhỏ. Tuy nhiên, trên tập dữ liệu lớn, thuật toán MXFGA cho kết quả tốt hơn BMBM khoảng 1.97%. Điều này cho thấy rõ khả năng áp dụng của thuật toán MXFGA đối với dữ liệu dạng này. Kết quả của kịch bản 4: Trong kịch bản này, các nút cảm biến được triển khai ngẫu nhiên, trong khi các nút chuyển tiếp được triển khai thành các cụm. Mức độ cải thiện của cả ba thuật toán đề xuất so với thuật toán Yuan là không nhiều. Các con số lần lượt cho BMBM, MXFGA và BMBM lần lượt là 3.99%, 4.03% và 4.03% cho tập dữ liệu nhỏ; 6.32%, 6.59% và 6.54% cho tập dữ liệu lớn. Kết quả của kịch bản 5: Tương tự như kịch bản 3, trong kịch bản này các nút cảm biến được sinh trong 2 × n/y cụm, các nút chuyển tiếp được sinh ngẫu nhiên. Kịch bản dữ liệu này là trường hợp khó cho phương pháp phân cụm, vì cách sinh dữ liệu sẽ dẫn đến 16
các cụm thưa, chất lượng cụm thấp. Đây là kịch bản dữ liệu duy nhất mà thuật toán khởi tạo dựa trên phân cụm CluRNS cho kết quả tệ hơn kết quả của Yuan. Do kết quả khởi tạo phân cụm có chất lượng thấp, thuật toán MXFGA lúc này cũng phát huy được lợi thế, chất lượng lời giải cải thiện lần lượt khoảng 14.33% và 26.90% trên tập dữ liệu nhỏ và trên tập dữ liệu lớn. Ngoài ra, đối với kịch bản này, thuật toán MXFGA với khởi tạo phân cụm mặc dù vẫn tốt hơn thuật toán của Yuan trên tất cả các bộ dữ liệu, tuy nhiên, kết quả tệ hơn hai thuật toán đề xuất còn lại là BGS và BMBM. Cụ thể, thuật toán BGS và BMBM cải thiện 13.22% và 14.28%, trong khi MXFGA cải thiện được 11.80% kết quả so với thuật toán Yuan trên tập dữ liệu nhỏ. Đối với tập dữ liệu lớn, MXFGA vẫn cải thiện ít nhất là 26.97%, trong khi BGS cải thiện 29.85% và BMBM cải thiện 30.50% Đối với dữ liệu loại này, thuật toán BMBM cho kết quả khá sát với cận dưới. Kết quả của kịch bản 6: Dữ liệu trong kịch bản này được sinh tương tự như kịch bản 5, tuy nhiên vị trí các nút chuyển tiếp được sinh ra trong 2 × y cụm và các nút cảm biến được sinh ngẫu nhiên. Kết quả tổn thất truyền thông thu được của BGS, MXFGA và BMBM trên tập dữ liệu nhỏ là: 114.71, 111.57 và 111.68, trên tập dữ liệu lớn là 135.7, 134.23, 133.73. Đối với kịch bản dữ liệu này, thuật toán BMBM ó 2/5 bộ đạt tối ưu trên cả tập dữ liệu nhỏ và tập dữ liệu lớn. Tóm tắt kết quả thu được của các thuật toán 2.4.5 Đánh giá độ phức tạp thuật toán 2.5 Kết luận chương 17