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ý 1 đố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 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 trong đị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. 2 thành một cá thể phù hợp trên nhiệm vụ Tj. Đối với bài toán tối ưu hóa liên tục, điều này được thực hiện một cách đơn giản.
Ví dụ, xem xét biến thứ i (xi ), phạm vi của biến này là [Li , Ui ]. Nếu giá trị trên cá thể trong không gian chung là yi , khi ánh xạ sang không gian của bài toán thì xi = Li + (Ui − Li ) ∗ yi. Ngược lại, đối với bài toán tối ưu rời rạc, việc giải mã cá thể thường phụ thuộc vào từng bài toán cụ thể. Các tác giả trong [19] đã quan sát rằng, một cá thể được tạo ra trong MFEA dường như không “tốt” trên tất cả các nhiệm vụ.
Do đó, một cá thể chỉ được đánh giá trên các nhiệm vụ mà nó thực hiện tốt nhất. Để kết hợp đặc tính này vào MFEA một cách đơn giản, các tác giả đã sử dụng phép di truyền văn hóa theo chiều dọc. Trong kế thừa đa nhân tố, việc truyền văn hóa theo chiều dọc là một phương thức kế thừa song song với kế thừa sinh học sao cho các con cái kế thừa được kiểu hình của bố mẹ. Quan sát trên được thực hiện trong MFEA bằng cách cho phép con cái bắt chước (imitate) yếu tố kỹ năng (đặc điểm văn hóa) của cha hoặc mẹ chúng.
Điều này được coi như là một sự bắt chước có chọn lọc (selective imitation). Chi tiết được thực hiện trong thuật toán 1. Do đó, thay vì đánh giá cá thể cho hai nhiệm vụ, chỉ cần đánh giá cá thể này cho một nhiệm vụ. Sự kết hợp này làm giảm đáng kể số lần đánh giá cần thiết.2: Cơ chế đánh giá cá thể 1 Các thể c sẽ có hai cha mẹ (pa và pb ) hoặc có một cha mẹ (pa hoặc pb ).
Xem thuật toán 1.3; 2 if c có hai cha mẹ then 3 Sinh ngẫu nhiên một số thực rand trong khoảng 0 đến 1; 4 if (rand < 0.5) then 5 c bắt chước pa → con lai được đánh giá chỉ cho nhiệm vụ Tτa ; 6 end 7 else 8 c bắt chước pb → con lai được đánh giá chỉ cho nhiệm vụ Tτb ; 9 end 10 end 11 else 12 c bắt chước cá thể cha/mẹ của nó → con lai được đánh giá chỉ cho nhiệm vụ đó với chỉ số kỹ năng phù hợp nhất là của cha mẹ nó; 13 end 14 nhân tố chi phí của c được gán là ∞ cho các nhiệm vụ mà nó không được đánh giá; Thuật toán 1.3: giao phối hợp nhất 1 Lựa chọn hai cá thể pa và pb ngẫu nhiên từ quần thể current-pop; 2 Sinh ngẫu nhiên một số thực rand trong khoảng 0 đến 1; 3 if τa = τb or rand < rmp then 4 Lai ghép hai cha mẹ pa và pb để sinh ra hai cá thể con ca và cb ; 5 end 6 else 7 Đột biến pa để tạo ra con ca ; 8 Đột biến pb để tạo ra con cb ; 9 end 1.3 Một số thuật toán giải bài toán tối ưu đa mục tiêu Các kĩ thuật để giải bài toán tối ưu đa mục tiêu có thể chia thành hai hướng tiếp cận. Trong hướng tiếp cận đầu tiên, bài toán đa mục tiêu sẽ được chuyển về bài toán đơn mục tiêu bằng cách sử dụng các véc tơ trọng số cho từng mục 24 tiêu. Cách tiếp cận thứ hai dựa trên thuật toán tiến hóa. Trong cách tiếp cận này, chúng ta sẽ tối ưu đồng thời các mục tiêu.
Biên Pareto được xấp xỉ bằng cách lặp đi lặp lại quá trình giải bài toán với các tham số được cập nhật qua từng bước. Các thuật toán tiến hóa đa mục tiêu (multiobjective evolutionary algorithms - MOEAs) là hướng tiếp cận dựa trên quần thể phù hợp để giải quyết các bài toán tối ưu đa mục tiêu vì các thuật toán này duy trì đồng thời một tập các lời giải khả thi của quần thể. Điều này cho phép tìm một số phần tử của tập Pareto tối ưu trong một lần chạy thuật toán, thay vì phải thực hiện các bài toán riêng biệt với các trọng số của các mục tiêu khác nhau. Tuy nhiên, thách thức lớn của các thuật toán tiến hóa là làm sao để định hướng quá trình tìm kiếm về tập Pareto tối ưu và duy trì tính đa dạng của quần thể để ngăn việc hội tụ sớm.
Phần tiếp theo sẽ trình bày một số thuật toán MOEAs dựa trên Pareto gồm: thuật toán di truyền sắp xếp không trội (non-dominated sorting genetic algorithm II - NSGA-II ) và thuật toán đa mục tiêu dựa trên phân rã (multiobjective evolutionary algorithm based on decomposition- MOEAD). Các thuật toán này sẽ được sử dụng ở chương sau.1 Thuật toán di truyền sắp xếp không trội Đối với các thuật toán tiến hóa đơn mục tiêu, việc chọn lọc các cá thể diễn ra khá dễ dàng nhờ vào việc so sánh độ thích nghi của các cá thể. Ví dụ như, đối với bài toán cực tiểu hóa, những cá thể nào có độ thích nghi nhỏ thì tốt hơn các cá thể có độ thích nghi lớn. Tuy nhiên, đối với các thuật toán tiến hóa đa mục tiêu, việc so sánh các cá thể trong quần thể khá phức tạp.
Để biết một cá thể có phải là tốt nhất trong quần thể hay không, chúng ta cần phải kiểm tra cá thể đó có bị trội bởi các cá thể khác trong quần thể không (khái niệm trội, bị trội được đưa ra trong định nghĩa 1.