GIỚI THIỆU
Đặt vấn đề
Mạng cảm biến không dây (WSN) là một thành phần thiết yếu trong nền tảng Internet of Things (IoT), được ứng dụng rộng rãi trong giám sát môi trường, nông nghiệp, theo dõi sức khỏe và hoạt động quân sự Một WSN bao gồm các nút cảm biến giá rẻ, tiêu thụ năng lượng thấp và một hoặc nhiều trạm cơ sở (Base Station - BS) Các nút cảm biến thu thập thông tin môi trường, chuyển đổi thành dữ liệu và phối hợp gửi về trạm cơ sở theo định kỳ Trong nông nghiệp thông minh, dữ liệu về nhiệt độ, độ ẩm và hàm lượng nước trong đất từ các nút cảm biến trên cánh đồng được gửi về trạm cơ sở mỗi 30 phút để đánh giá tác động môi trường và theo dõi sự phát triển của cây trồng, từ đó nâng cao năng suất sản xuất.
Theo cách tiếp cận truyền thống, dữ liệu cảm biến được gửi về trạm cơ sở thông qua mô hình định tuyến nhiều bước, nhưng điều này dẫn đến vấn đề điểm nóng, khiến năng lượng của các nút gần trạm cơ sở cạn kiệt nhanh chóng Để khắc phục tình trạng này, việc sử dụng các phương tiện thu thập dữ liệu di động hoạt động như trạm cơ sở di động là một giải pháp hiệu quả, giúp giảm và cân bằng mức tiêu thụ năng lượng giữa các nút cảm biến, từ đó kéo dài tuổi thọ của mạng.
Gần đây, sự phát triển của công nghệ máy bay không người lái (UAV) đã dẫn đến việc ứng dụng rộng rãi trong nhiều lĩnh vực như quân sự, cứu hộ khẩn cấp, và giám sát UAV được xem là giải pháp linh hoạt và tiện lợi để thu thập dữ liệu cảm biến trong các mạng cảm biến lớn nhờ vào chi phí thấp, dễ triển khai và khả năng tránh chướng ngại vật Đặc biệt, đường truyền vô tuyến giữa nút cảm biến và UAV tận dụng hiệu quả đặc tính lan truyền đường ngắm (LoS), giúp tăng độ tin cậy và tốc độ truyền dữ liệu so với phương tiện mặt đất Tuy nhiên, hạn chế về thời lượng pin của UAV dân dụng hiện nay khiến chúng chỉ có thể hoạt động trong thời gian ngắn, thường chỉ khoảng 30 phút cho một UAV cánh quạt điển hình, trước khi cần phải thay pin hoặc sạc lại.
Do thời gian hoạt động hạn chế, việc sử dụng một hoặc nhiều UAV để tiếp cận từng nút cảm biến và thu thập dữ liệu trực tiếp từ mỗi nút thường không khả thi, đặc biệt trong các mạng cảm biến lớn được triển khai trên khu vực rộng.
Trong nông nghiệp thông minh, việc quản lý các cánh đồng canh tác rộng lớn thường sử dụng phương pháp lựa chọn các nút điểm hẹn (rendezvous node) mà UAV sẽ ghé thăm Mỗi nút cảm biến trong mạng có nhiệm vụ chuyển dữ liệu tới một trong các nút điểm hẹn đã được xác định Sau đó, UAV sẽ xuất phát từ trạm cơ sở để thu thập dữ liệu Các nút điểm hẹn lưu trữ dữ liệu từ các nút khác và gửi toàn bộ dữ liệu đã tập hợp đến UAV khi được ghé thăm Để tối ưu hóa thời gian sống của mạng, việc phân bố hợp lý các nút điểm hẹn là cần thiết nhằm giảm thiểu năng lượng tiêu thụ trong quá trình vận chuyển dữ liệu Hơn nữa, do các nút điểm hẹn tiêu tốn nhiều năng lượng cho nhiệm vụ chuyển tiếp dữ liệu, việc tổ chức các nút cảm biến luân phiên thực hiện vai trò làm điểm hẹn là cần thiết để cân bằng mức tiêu hao năng lượng giữa các nút trong mạng.
Luận văn nghiên cứu tổ chức thu hoạch dữ liệu từ mạng cảm biến không dây (WSN) định kỳ về trạm cơ sở bằng UAV, thông qua nút điểm hẹn, nhằm tối ưu hóa thời gian sống của mạng.
Cho một WSN không đồng nhất (heterogenous) bao gồm các nút cảm biến có năng lượng ban đầu và kích thước dữ liệu cần thu hoạch khác nhau và
Mỗi UAV có vị trí xuất phát tại trạm cơ sở và sẽ trở về sau khi hoàn thành nhiệm vụ để nạp năng lượng Trước mỗi chu kỳ thu hoạch dữ liệu, cần thiết lập danh sách các nút điểm hẹn mà UAV sẽ ghé thăm trong thời gian hoạt động cho phép, đồng thời xây dựng các tuyến đường định tuyến trong mạng để vận chuyển dữ liệu từ các nút cảm biến về các điểm hẹn đã xác định Mục tiêu cuối cùng là tối đa hóa số chu kỳ thu hoạch dữ liệu có thể thực hiện cho đến khi nút cảm biến đầu tiên hết năng lượng.
Các đóng góp của luận văn
Bài viết đề xuất hai mô hình quy hoạch số nguyên hỗn hợp tuyến tính (MILP) nhằm tối ưu hóa thời gian sống của mạng cảm biến không dây trong thu hoạch dữ liệu bằng UAV, cụ thể là mô hình 2-index và 3-index Mô hình 2-index sử dụng phương pháp Big M để mô hình hóa các ràng buộc có điều kiện, trong khi mô hình 3-index áp dụng luồng đa hàng hóa để mô hình hóa luồng dữ liệu và đường đi của UAV Mô hình 3-index, nhờ loại bỏ các ràng buộc Big M, cho thời gian giải nhanh hơn và có khả năng xử lý các bài toán lớn hơn so với mô hình 2-index, mặc dù có nhiều biến số và ràng buộc hơn Các đánh giá thực nghiệm cho thấy mô hình MILP đề xuất có khả năng tìm ra lời giải tối ưu cho mạng cảm biến với tối đa 50 nút cảm biến (SN).
Bài viết đề xuất một giải pháp tối ưu hóa quy trình thu thập dữ liệu bằng UAV cho các mạng cảm biến không dây (WSN) quy mô lớn, có hàng nghìn nút cảm biến Giải pháp này dựa trên phương pháp heuristic kết hợp với một mô hình lập trình số nguyên hỗn hợp (MILP) đơn giản, nhằm nâng cao hiệu quả thu hoạch dữ liệu.
, với K là số lượng các cụm/nút điểm hẹn trong mạng
Kế hoạch thu hoạch nhiều chu kỳ được đề xuất nhằm tối đa hóa thời gian sống của mạng bằng cách cấu hình lại các cụm và CHs để cân bằng chi phí năng lượng tại các nút cảm biến (SN) Giải pháp GAMBAC (Gathering data Assisted by Multi-UAV with a load-BAlanced Clustering) cho thấy hiệu quả vượt trội so với các phương án trước đó khi sử dụng một hoặc nhiều UAV trong mạng gồm 1000 SN GAMBAC có khả năng kéo dài thời gian sống của mạng tối thiểu 38% so với các giải pháp sử dụng một UAV và tối thiểu 33% so với các giải pháp nhiều UAV đã có.
Cấu trúc luận văn
Trong CHƯƠNG 2, luận văn khảo sát lý thuyết về mạng cảm biến không dây và thu hoạch dữ liệu, tập trung vào giải pháp thu hoạch dữ liệu bằng phương tiện di động và UAV CHƯƠNG 3 trình bày mô hình mạng và bài toán tối ưu thời gian sống trong thu hoạch dữ liệu từ WSN sử dụng UAV Tiếp theo, CHƯƠNG 4 giới thiệu hai mô hình quy hoạch số nguyên hỗn hợp tuyến tính: mô hình 2-index và 3-index CHƯƠNG 5 phân tích các kịch bản cài đặt WSN đặc biệt, đề xuất ý tưởng heuristic sử dụng phân cụm mạng cân bằng theo sơ đồ Voronoi và giải pháp thu thập dữ liệu hiệu quả CHƯƠNG 6 giới thiệu các kịch bản thực nghiệm và so sánh kết quả của giải pháp đề xuất với các cơ chế khác Cuối cùng, CHƯƠNG 7 tóm tắt những đóng góp chính và thảo luận về các hướng mở rộng có thể có của đề tài.
TỔNG QUAN LÝ THUYẾT
Mạng cảm biến không dây
Mạng cảm biến không dây (WSN) được sử dụng để giám sát và báo cáo các sự kiện như phát hiện cháy rừng và báo động xâm nhập trong các khu vực cụ thể Trong hơn một thập kỷ qua, WSN đã được áp dụng rộng rãi trong nhiều lĩnh vực như quân sự, sinh học, y tế, môi trường và thương mại WSN thực hiện chức năng cảm biến và thu thập thông tin từ môi trường, bao gồm dữ liệu về nhiệt độ, độ ẩm, cường độ ánh sáng, áp suất, độ ồn, tình trạng thổ nhưỡng, chuyển động của vật thể và các chỉ số y tế như mức độ căng thẳng, nhịp tim và chỉ số đường huyết.
Hầu hết các mạng cảm biến không dây bao gồm hai thành phần chính: trạm cơ sở (BS) và nút cảm biến (SN) Trạm cơ sở, còn gọi là nút cửa thoát (sink node), có nhiệm vụ thu thập dữ liệu từ các nút cảm biến qua kết nối không dây và cung cấp thông tin cho người dùng Người dùng có thể truy cập dữ liệu trực tiếp hoặc qua internet để thực hiện các tác vụ xử lý dữ liệu nâng cao Số lượng trạm cơ sở có thể thay đổi tùy thuộc vào kích thước và cấu trúc mạng, và chúng có thể ở trạng thái tĩnh hoặc di động Các trạm cơ sở thường được trang bị nguồn năng lượng dồi dào và khả năng tính toán mạnh mẽ, đóng vai trò quan trọng trong việc kết nối mạng cảm biến với người dùng.
Hình 1 Kiến trúc mạng cảm biến không dây
Với sự phát triển nhanh chóng trong lĩnh vực điện tử và chế tạo vi mạch, các nút cảm biến hiện nay có chi phí sản xuất thấp, kích thước nhỏ gọn và khả năng thực hiện nhiều chức năng với hiệu quả kinh tế cao Các nút cảm biến, thiết bị điện tử được triển khai rộng rãi trong mạng lưới, có khả năng theo dõi thông tin môi trường Mỗi nút cảm biến thường bao gồm ba thành phần chính: thành phần cảm nhận (sensing unit) để thu thập dữ liệu từ môi trường, thành phần xử lý (processing unit) với bộ nhớ lưu trữ và bộ điều khiển để xử lý dữ liệu, và thành phần giao tiếp (communication unit) với mô-đun thu phát vô tuyến cho phép giao tiếp không dây Tất cả các thành phần này hoạt động dựa trên nguồn năng lượng từ pin.
Hình 2 Các thành phần chính của một nút cảm biến
Việc triển khai nút cảm biến có thể diễn ra một cách ngẫu nhiên, chẳng hạn như từ máy bay hoặc robot, dẫn đến sự phân tán tự nhiên trên địa hình Sau khi được triển khai, các nút này tự tổ chức thành một mạng không dây ad hoc, kết nối với nhau qua sóng vô tuyến ngắn bằng mô-đun thu phát công suất thấp Chúng có khả năng hợp tác để thực hiện nhiệm vụ như theo dõi sự lây lan của ô nhiễm hoặc đám cháy Quy trình hoạt động bao gồm thu thập thông tin môi trường, tạo ra gói dữ liệu và truyền tải dữ liệu đến trạm cơ sở hoặc các nút cảm biến khác qua kênh truyền không dây.
Mô-đun thu phát Thành phần giao tiếp
Hình 3 Hoạt động của một nút cảm biến
Do giới hạn về phạm vi truyền thông của mô-đun thu phát, dữ liệu từ nút cảm biến không thể gửi trực tiếp đến trạm cơ sở Thay vào đó, các nút cảm biến khác hoạt động như trung gian để chuyển tiếp dữ liệu Quá trình này có thể liên quan đến nhiều nút cảm biến để nhận và định tuyến gói dữ liệu đến trạm cơ sở Mỗi nút cảm biến có thể đóng vai trò là bộ tạo dữ liệu hoặc bộ định tuyến dữ liệu, được gọi là nút chuyển tiếp Các nút cảm biến gần trạm cơ sở thường thực hiện nhiệm vụ chuyển tiếp gói dữ liệu từ các nút cảm biến xa hơn trong mạng.
Hình 4 Cơ chế định tuyến đa bước trong WSN
Trong mạng cảm biến không dây, các nút cảm biến giao tiếp với nhau qua sóng không dây và thường hoạt động bằng nguồn năng lượng hạn chế như pin Sức mạnh tính toán của các cảm biến này thường yếu hơn so với các trạm cơ sở Khi một nút cảm biến tiêu thụ hết năng lượng từ pin, nó không còn khả năng cung cấp dịch vụ như cảm biến, xử lý dữ liệu hoặc giao tiếp với các nút khác, và lúc này nó sẽ được coi là "chết" và bị loại bỏ khỏi mạng.
Thời gian sống của mạng cảm biến được xác định là khoảng thời gian từ khi triển khai cho đến khi số lượng nút cảm biến "quan trọng" giảm xuống mức không đủ, dẫn đến việc mạng không thể thực hiện chức năng yêu cầu.
Bảy biến "chết" có thể tác động trực tiếp đến toàn bộ thời gian tồn tại của mạng, dẫn đến tổn thất lớn do phải tái cấu trúc các đường định tuyến đến trạm cơ sở và không thể phát hiện, báo cáo các sự kiện trong môi trường Do đó, nghiên cứu các giải pháp tiêu thụ năng lượng hiệu quả và tiết kiệm năng lượng là rất quan trọng để kéo dài thời gian sống của mạng và đảm bảo tính mạnh mẽ của mạng cảm biến trong thiết kế và triển khai cho mục đích sử dụng thực tế.
Các giải pháp thu hoạch dữ liệu trong mạng cảm biến không dây
2.2.1 Vấn đề thu hoạch dữ liệu trong mạng cảm biến không dây
Dữ liệu cảm biến được truyền từ nút nguồn về trạm cơ sở thông qua các nút cảm biến trung gian, trong đó các cảm biến gần trạm cơ sở sẽ phải nhận và chuyển tiếp lượng lớn dữ liệu từ các cảm biến xa hơn Điều này dẫn đến việc các nút cảm biến gần trạm tiêu tốn nhiều năng lượng hơn cho việc tính toán và truyền thông, làm cạn kiệt năng lượng nhanh chóng so với các cảm biến khác Kết quả là, những nút này trở thành các điểm nóng (hotspot), giảm thời gian sống của mạng Khi các nút cảm biến gần trạm cơ sở ngừng hoạt động, một lượng lớn dữ liệu không thể đến được trạm cơ sở, gây suy giảm hiệu suất mạng và có thể dẫn đến sự ngừng hoạt động hoàn toàn.
Hình 5 Khi các nút gần BS (s 0 ) hết năng lượng, dữ liệu không thể gửi về BS
2.2.2 Thu hoạch dữ liệu với cấu trúc phân cụm
Trong mạng cảm biến không dây quy mô lớn, việc truyền trực tiếp toàn bộ dữ liệu đến trạm cơ sở không hiệu quả Thay vào đó, một giải pháp hiệu quả là phân vùng các nút cảm biến thành các cụm rời rạc, mỗi cụm có một nút trưởng để thu thập và tổng hợp dữ liệu trước khi gửi đến trạm cơ sở Phân cụm đã chứng minh là phương pháp hiệu quả trong việc kéo dài tuổi thọ mạng và cải thiện khả năng mở rộng của WSN Nhiều phương pháp phân cụm đã được đề xuất nhằm tối ưu hóa thời gian sống của mạng.
Low Energy Adaptive Clustering Hierarchy (LEACH) là một phương pháp phân cụm tiên phong trong mạng cảm biến không dây (WSN) LEACH hoạt động theo hai giai đoạn chính: giai đoạn chọn trưởng cụm và giai đoạn truyền dữ liệu Trong giai đoạn chọn trưởng cụm, các nút trưởng cụm được xác định dựa trên một ngưỡng xác suất đã được thiết lập trước Một nút cảm biến sẽ trở thành trưởng cụm cho chu kỳ hiện tại nếu giá trị ngẫu nhiên được chọn từ 0 đến 1 nhỏ hơn ngưỡng này.
Trong mô hình LEACH, 𝑃 đại diện cho tỷ lệ phần trăm số nút trưởng cụm mong muốn, 𝑅 là thứ tự chu kỳ hiện tại, và 𝐺 là tập hợp các nút chưa trở thành trưởng cụm trong 1/𝑃 chu kỳ gần nhất Các nút cảm biến được nhóm với nút trưởng cụm gần nhất để hình thành cụm, và trong giai đoạn truyền dữ liệu, các trưởng cụm tổng hợp và gửi dữ liệu trực tiếp đến trạm cơ sở Mặc dù LEACH là một phương pháp phân tán và không yêu cầu thông tin toàn cầu, nó vẫn gặp hai nhược điểm chính: không đạt được cân bằng tải giữa các nút cảm biến do không tính đến năng lượng ban đầu và khoảng cách đến trạm cơ sở, và việc sử dụng giao tiếp liên cụm đơn bước gây tiêu tốn năng lượng cao trong mạng quy mô lớn.
Giao thức Hybrid Energy Efficient Distributed Clustering Protocol (HEED), được O Younis và S Fahmy giới thiệu vào năm 2004, là một phương pháp phân cụm tiên tiến HEED mở rộng cơ chế của LEACH bằng cách sử dụng mức năng lượng còn lại của các nút làm tham số chính, trong khi thông tin về cấu trúc mạng như mật độ nút và khoảng cách đến các nút lân cận chỉ được xem xét như tham số phụ Quá trình phân cụm diễn ra qua nhiều lần lặp, trong đó các nút chưa được bao phủ bởi nút trưởng cụm nào sẽ tăng gấp đôi xác suất trở thành nút trưởng cụm mới Năng lượng còn lại tại mỗi nút đóng vai trò quan trọng trong việc tính toán xác suất này.
Phương pháp chọn ra 9 nút trưởng cụm ban đầu thường được áp dụng trong nhiều cơ chế phân cụm khác nhau Chi phí truyền thông nội cụm là yếu tố quan trọng mà các nút sử dụng để xác định sự tham gia vào cụm Các gói tin tổng hợp dữ liệu sẽ được các nút đại diện gửi về trung tâm thông qua các phương thức truyền tin trực tiếp hoặc qua các mô hình truyền tin đa bước.
Phương pháp phân cụm EECS được đề xuất nhằm kéo dài thời gian sống của mạng, tương tự như LEACH EECS áp dụng xác suất để lựa chọn các nút trưởng cụm và thiết lập giao tiếp trực tiếp giữa các trưởng cụm và trạm cơ sở Điểm khác biệt của EECS so với LEACH là nó xác định nút trưởng cụm dựa trên năng lượng còn lại và khoảng cách từ nút trưởng cụm đến trạm cơ sở, tạo ra các cụm có kích thước động và cân bằng khối lượng công việc giữa các cụm.
Chen và cộng sự đã đề xuất phương pháp phân cụm EEUC nhằm giải quyết vấn đề điểm nóng và cân bằng khối lượng công việc giữa các nút trưởng cụm Vấn đề điểm nóng xảy ra khi các nút gần trạm cơ sở phải chuyển tiếp nhiều dữ liệu hơn, dẫn đến cạn kiệt năng lượng nhanh chóng EEUC là phương pháp phân cụm đầu tiên sử dụng kích thước không bằng nhau, xây dựng các cụm nhỏ hơn cho các nút gần trạm cơ sở, giúp tiết kiệm năng lượng cho quá trình xử lý dữ liệu nội cụm Phương pháp này lựa chọn các nút trưởng cụm dựa trên năng lượng còn lại, khả năng hoạt động của mạng và khoảng cách đến trạm gốc Trong giai đoạn truyền dữ liệu, EEUC thiết lập một cây định tuyến để tối ưu hóa quá trình định tuyến giữa các cụm, chú trọng vào năng lượng còn lại của từng nút trưởng cụm.
Cơ chế Multi-hop Routing with Low Energy Adaptive Clustering Hierarchy (MR-LEACH) được đề xuất bởi Farooq và cộng sự nhằm tối ưu hóa việc giám sát bằng cách chia khu vực thành nhiều tầng và tạo hệ thống phân cấp cụm Trong MR-LEACH, các gói tin từ các nút trong cùng tầng được gửi đến nút trung tâm qua số bước nhảy đồng đều, với nút trưởng cụm được chọn dựa trên năng lượng còn lại lớn nhất trong nhóm hàng xóm Hệ thống tầng cụm này cho phép chuyển tiếp dữ liệu hiệu quả từ các nút đại diện ở tầng thấp hơn lên nút trung tâm, từ đó gia tăng thời gian sống của mạng MR-LEACH cũng cải thiện khả năng mở rộng so với LEACH cơ bản, mặc dù vẫn chưa giải quyết triệt để vấn đề điểm nóng gần nút trung tâm.
2.2.3 Thu hoạch dữ liệu bằng trạm cơ sở/phương tiện di động
Việc áp dụng các thiết bị di động trong thu thập dữ liệu từ mạng cảm biến không dây đã chứng minh hiệu quả trong việc giảm thiểu các vấn đề như điểm nóng, kéo dài tuổi thọ của mạng và giảm thiểu mức tiêu thụ năng lượng.
10 thụ năng lượng và giảm độ trễ dữ liệu so với việc chỉ sử dụng trạm cơ sở tĩnh [10]
Ý tưởng sử dụng phương tiện di động để thu hoạch dữ liệu từ các nút cảm biến dọc theo một tuyến đường xác định có thể giúp giảm tiêu thụ năng lượng và yêu cầu lưu trữ tạm thời Tuy nhiên, nhược điểm là các nút cảm biến tĩnh phải chờ đợi phương tiện ghé thăm, dẫn đến độ trễ có thể không chấp nhận được trong các ứng dụng quan trọng Do đó, việc tối ưu hóa độ dài tuyến đường và lập kế hoạch quỹ đạo di chuyển là rất quan trọng để giảm thiểu độ trễ dữ liệu.
Sử dụng trạm cơ sở di động (Mobile Base Station - MBS) là một giải pháp hiệu quả để cân bằng mức tiêu thụ năng lượng giữa các nút cảm biến trong mạng Theo mô hình thu hoạch dữ liệu đa bước truyền thống, các nút gần trạm cơ sở thường cạn năng lượng sớm hơn do phải chuyển tiếp dữ liệu từ các nút ở xa Để khắc phục điều này, MBS có thể thường xuyên thay đổi vị trí và tạm dừng tại các điểm dừng để thu thập dữ liệu từ các cảm biến gần đó Việc lựa chọn điểm dừng là rất quan trọng nhằm giảm thiểu tiêu thụ năng lượng Mục tiêu chính của các giải pháp dựa trên MBS là cân bằng và giảm tiêu thụ năng lượng giữa các nút cảm biến, đồng thời tối đa hóa thời gian sống của mạng thông qua việc thay đổi đường dẫn đến trạm cơ sở Để đạt được hiệu quả, vị trí của MBS cần được điều chỉnh thường xuyên nhằm cân bằng năng lượng còn lại của các nút cảm biến.
Phương tiện thu hoạch dữ liệu di động (Mobile Data Collector - MDC) có hai cách tiếp cận chính: không sử dụng điểm hẹn và có sử dụng điểm hẹn Trong cách tiếp cận không sử dụng điểm hẹn, MDC di chuyển trong mạng để thu thập dữ liệu từ các nút cảm biến bằng cách tiếp cận trực tiếp từng nút, sau đó chuyển tiếp dữ liệu thu được về trạm cơ sở.
Nghiên cứu trong [17] nhấn mạnh vai trò quan trọng của MDC trong việc thu thập dữ liệu cho các ứng dụng giám sát khu vực cách biệt Trong cùng một khu vực, các cảm biến có khả năng kết nối với nhau, trong khi các cảm biến ở các khu vực khác có thể không kết nối Điều này phù hợp với việc triển khai mạng cảm biến không dây (WSN) trong thực tế, nơi các nút cảm biến được phân bố rải rác trên một vùng cảm biến.
Trong các khu vực cảm biến bị cô lập, một MDC di chuyển giữa các khu vực để thu thập dữ liệu, giúp tiết kiệm năng lượng nhờ giảm khoảng cách truyền tin và số lượng nút trung gian Tuy nhiên, nhược điểm của phương pháp này là có thể gây ra độ trễ cao trong việc truyền dữ liệu, điều này không phù hợp với các ứng dụng nhạy cảm với thời gian.
MÔ HÌNH BÀI TOÁN
Mô hình mạng cảm biến không dây
Luận văn nghiên cứu một mạng cảm biến với N nút cảm biến (sensor node - SN) cố định s1, s2, , sN và một trạm cơ sở (base station - BS) s0, được triển khai trên địa hình phẳng Tập hợp các nút cảm biến được ký hiệu là V = {s1, s2, , sN} và biểu diễn các liên kết không dây có thể thiết lập giữa các cặp nút cảm biến Mô hình mạng cảm biến này có những đặc điểm riêng biệt cần được phân tích.
Các nút cảm biến và trạm cơ sở đã được triển khai ở trạng thái tĩnh, với vị trí của các cảm biến được xác định trước và không thay đổi trong suốt thời gian hoạt động.
Hai nút cảm biến s i và s j có thể kết nối trực tiếp với nhau nếu như khoảng cách Euclide giữa chúng là d ij không vượt quá bán kính truyền tin R
Dữ liệu từ tất cả các cảm biến cần được thu thập định kỳ về trạm cơ sở, và mỗi lần thu thập được gọi là một chu kỳ Mỗi chu kỳ sẽ kéo dài trong thời gian tối đa T max giây, với T max là giá trị cố định được xác định dựa trên yêu cầu của ứng dụng.
Các nút cảm biến trong mạng không đồng nhất, với kích thước dữ liệu cần thu thập tại mỗi nút khác nhau trong từng chu kỳ Giá trị này không thay đổi trong suốt thời gian hoạt động của mạng Đối với mỗi nút cảm biến s_i, b_i đại diện cho lượng dữ liệu cần thu thập tính bằng bit trong chu kỳ, trong khi E_i^0 là năng lượng ban đầu và E_i^r là năng lượng của nút s_i khi bắt đầu chu kỳ thứ r.
M UAV cánh xoay được sử dụng để thu thập dữ liệu từ các nút cảm biến, hoạt động ở độ cao cố định h (m) và với tốc độ bay không đổi v0.
Để các UAV có thể thu thập dữ liệu từ các nút cảm biến, cần đảm bảo rằng độ cao h không vượt quá bán kính truyền tin R của các nút cảm biến.
Luận văn áp dụng mô hình tiêu thụ năng lượng được đề xuất trong tài liệu [27] Mô hình này xem xét hiện tượng suy hao trong không gian tự do, trong đó năng lượng suy hao theo công thức d^2 được áp dụng khi khoảng cách giữa nút gửi và nút nhận nhỏ hơn bán kính truyền tin R Do đó, năng lượng cần thiết để truyền một gói tin có độ dài l-bits qua khoảng cách d sẽ được tính toán dựa trên các yếu tố này.
Năng lượng mà một nút cảm biến phải tiêu thụ để nhận l-bits dữ liệu là:
Để thuận tiện trong việc trình bày, ký hiệu Rx = elec đại diện cho năng lượng mà các nút cần tiêu thụ để nhận một bit dữ liệu Trong khi đó, Tx ij = elec + fs d ij^2 là năng lượng cần thiết để truyền một bit dữ liệu từ nút s i đến s j, với điều kiện d ij ≤ R.
Tx elec fs h thể hiện năng lượng tiêu thụ để gửi một bit từ SN s i tới một UAV bay ở độ cao h
Mô hình tiêu thụ năng lượng giả định rằng không có mất mát gói tin và bỏ qua nhiễu tín hiệu Đồng thời, bài toán cũng cho rằng chi phí năng lượng để phát tán thông tin điều khiển là không đáng kể.
Mô hình thu hoạch dữ liệu bằng UAV trong mạng cảm biến không dây thông qua nút điểm hẹn
Trong mô hình này, vào đầu mỗi chu kỳ, một tập hợp các nút cảm biến được chọn làm nút điểm hẹn, và nhiệm vụ của tất cả các nút trong mạng là chuyển dữ liệu đã thu thập tới các nút điểm hẹn đã xác định Mỗi UAV sẽ nhận danh sách các nút điểm hẹn cần ghé thăm để thu thập dữ liệu Khi UAV đến một nút điểm hẹn, nút này sẽ gửi toàn bộ dữ liệu đã thu thập qua kết nối trực tiếp Sau khi hoàn thành nhiệm vụ thu hoạch, UAV sẽ trở về trạm cơ sở để truyền tải dữ liệu và nạp lại năng lượng cho chu kỳ tiếp theo.
Mô hình thu hoạch dữ liệu trong mạng cảm biến được chia thành các cụm, mỗi cụm có một nút trưởng cụm (CH) làm nút điểm hẹn Ở cấp độ đầu tiên, dữ liệu từ các cảm biến trong mỗi cụm được thu thập về nút CH thông qua mô hình định tuyến đa bước Tiếp theo, các UAV sẽ lần lượt ghé thăm các CH đã được chỉ định để thu hoạch dữ liệu trực tiếp và cuối cùng chuyển về trạm cơ sở.
Sau khi mạng cảm biến hoàn thành r chu kỳ thu hoạch dữ liệu, năng lượng còn lại của nút cảm biến s i sau chu kỳ thứ r là E i r Nhiệm vụ đặt ra là tìm phương án tổ chức thu hoạch dữ liệu cho chu kỳ thứ (r + 1), bao gồm việc phân chia mạng thành K cụm (1 ≤ K ≤ N) và xác định danh sách các nút trưởng cụm - các nút điểm hẹn mà UAV sẽ đi qua, đồng thời cần đảm bảo các điều kiện đã đề ra.
Mỗi cụm cảm biến được mô tả dưới dạng đồ thị cây, với các đỉnh là nút cảm biến và các cạnh là tập con của tập hợp các nút Nút gốc của cây là nút trưởng cụm, và trong mỗi chu kỳ, gói tin chứa dữ liệu từ các nút sẽ được định tuyến về nút trưởng thông qua cấu trúc cây, được gọi là cây chuyển tiếp dữ liệu (DFT) Tập hợp K cây chuyển tiếp dữ liệu của K cụm trong mạng tạo thành một rừng bao trùm cho đồ thị mạng G.
Mỗi nút cảm biến sẽ thuộc về một cây chuyển tiếp dữ liệu duy nhất
Chu trình bay của UAV bao gồm một danh sách các nút CH mà UAV cần ghé thăm theo thứ tự nhất định Mỗi UAV sẽ khởi hành từ vị trí trạm cơ sở, lần lượt đi qua các nút CH trong danh sách và sau đó trở về trạm cơ sở.
Mỗi nút trưởng cụm sẽ nằm trên một chu trình bay duy nhất trong tổng số
Yêu cầu về thời gian hoàn thành cho mỗi chu kỳ và các thông số kỹ thuật của UAV, đặc biệt là thời lượng hoạt động tối đa, quy định rằng chiều dài chu trình của mỗi UAV không được vượt quá giá trị ngưỡng tối đa đã được xác định.
Hình 7 Mô hình thu hoạch dữ liệu bằng UAV trong mạng cảm biến không dây phân cụm
Theo mô hình năng lượng đã trình bày, nếu nút s_i cần chuyển tiếp B_i bit dữ liệu từ các nút con trong cây chuyển tiếp dữ liệu của cụm trong chu kỳ r hiện tại, thì tổng năng lượng tiêu thụ của s_i sau chu kỳ này sẽ được xác định dựa trên các yếu tố liên quan đến quá trình truyền dữ liệu.
( ) ( ) ij ( ) i Rx i Tx i i Rx i Tx i i e B B b B B b
Năng lượng còn lại của s i ở cuối chu kỳ thứ r và đầu chu kỳ ( r 1) là:
Phát biểu bài toán
Bài toán thu hoạch dữ liệu trong mạng cảm biến không dây (WSN) sử dụng nhiều UAV cần xác định K cây chuyển tiếp dữ liệu cho K cụm cảm biến, với mỗi cây có gốc là một nút CH M chu trình UAV sẽ bắt đầu và kết thúc tại trạm cơ sở Mục tiêu chính là tối đa hóa thời gian sống của mạng, được định nghĩa là khoảng thời gian từ khi triển khai đến khi nút cảm biến đầu tiên cạn kiệt năng lượng.
Bài toán tối ưu hóa (OP) nhằm xác định cách phân cụm và chu trình cho các UAV tại chu kỳ thứ r được phát biểu như sau:
Một lời giải của bài toán tối ưu (OP) bao gồm tập hợp K DFT và tập hợp chu trình Π = { 1 , , Π M } của M UAV Mục tiêu của OP là giảm thiểu tổng năng lượng tiêu thụ của các cảm biến mạng (SNs) trong mỗi chu kỳ Ràng buộc (1) quy định rằng mỗi UAV chỉ được phép ghé thăm tối đa Q trạm thu phát (CHs), trong khi ràng buộc (2) đặt giới hạn về độ dài chu trình bay của UAV.
Độ dài của chu trình thứ z được xác định bởi các yếu tố như số lượng UAV và các ràng buộc cần thiết Ràng buộc đảm bảo rằng mỗi CH chỉ có một UAV duy nhất đến thăm để thu thập dữ liệu Đồng thời, ràng buộc yêu cầu sự cân bằng giữa tỷ lệ năng lượng còn lại của các cảm biến mạng (SN), được tính bằng tỷ số giữa năng lượng hiện tại và năng lượng ban đầu Tỷ lệ năng lượng còn lại của SN sau chu kỳ không được thấp hơn giá trị trung bình nhân với hệ số β Điều này yêu cầu phân bố lại các nút trưởng cụm sau mỗi chu kỳ nhằm cân bằng năng lượng, từ đó kéo dài thời gian sống của mạng.
Mô hình hóa bài toán dưới dạng quy hoạch số nguyên hỗn hợp tuyến tính 17
Để giải quyết bài toán nghiên cứu, luận văn áp dụng phương pháp tối ưu hóa bằng cách chuyển đổi bài toán thành quy hoạch số nguyên tuyến tính, sử dụng các công cụ như CPLEX, Gurobi, và lp-solver Trong phần này, luận văn trình bày các mô hình quy hoạch tuyến tính số nguyên hỗn hợp (MILP), bao gồm các tham số đầu vào thể hiện trạng thái mới nhất của các SN, như vị trí, lượng dữ liệu cần thu thập và năng lượng còn lại Kết quả của mô hình sẽ cung cấp phương án tổ chức thu hoạch dữ liệu hiệu quả.
18 liệu hiệu quả nhất bao gồm cách phân cụm mạng và các chu trình bay của UAV cho chu kỳ kế tiếp
Mô hình MILP 2-index được đề xuất nhằm mô hình hóa các ràng buộc có điều kiện trong bài toán bằng phương pháp Big M.
Phương pháp Big M, mặc dù đơn giản với số lượng biến và ràng buộc dạng O(N²), nhưng không hiệu quả khi áp dụng thuật toán nhánh cận Do đó, luận văn đề xuất mô hình thứ hai dựa trên ý tưởng luồng đa hàng hóa (mô hình 3-index) Mặc dù mô hình 3-index có số lượng biến và ràng buộc lớn hơn, cụ thể là O(N³) so với O(N²), nhưng các thực nghiệm cho thấy nó có thời gian giải ngắn hơn và khả năng xử lý các bài toán với kích thước mạng lớn hơn mô hình 2-index.
Hình 8 Minh họa về các cây chuyển tiếp dữ liệu trong mạng
Ký hiệu {0, , } N đại diện cho tập hợp tất cả các ID của các nút, bao gồm cả trạm cơ sở và nút sink, trong khi * {1, , }N là tập hợp các ID của các nút cảm biến, với quy ước rằng trạm cơ sở mang ID 0.
Đồ thị G V ( , ) biểu diễn mạng cảm biến, trong đó V { ,s 1 ,s N } là tập hợp các nút cảm biến và là tập hợp các kết nối không dây khả thi giữa các cặp nút cảm biến (SN).
Một tập hợp các cây chuyển tiếp dữ liệu (DFT) cần tìm được biểu diễn bởi một rừng bao trùm (spanning forest) của G, như mô tả trong Hình 8
Trong các mô hình quy hoạch nguyên, spanning forest được thể hiện qua ma trận X = [xij], với i = 0, ,N và j = 0, ,N Cột đầu tiên của ma trận này xác định xem một nút có phải là CH (nút gốc của một cây) hay không.
Phần còn lại của X cho biết những kết nối nào được sử dụng trong các DFT
Nếu x i j , 1, ( i j , 0) thì s j là nút cha của s i trong và s i sẽ chuyển tiếp dữ liệu đến s j
Trong một cấu trúc cây, nút SN si (i > 0) có thể là một nút chính hoặc là nút con của một nút khác Trường hợp đầu tiên xảy ra khi x i,0 = 1 và x i,j = ∀ j ∈ 0, j*; trong khi trường hợp thứ hai xảy ra khi x i,0 = 0.
Tóm gọn lại cho cả hai trường hợp, ta có:
Ký hiệu A ( N N ) [a i j , ], (i j, N * ) là ma trận kề được sử dụng để biểu diễn đồ thị G V ( , ) Cụ thể a i j , 1 nếu tồn tại kết nối ( ,s s i j ) trong , trái lại thì
, 0 a i j Để là một spanning forest của G thì điều kiện sau phải được thỏa mãn
Chu trình của UAV là một chuỗi các nút CH mà nó sẽ đi qua, với đường bay giữa hai nút CH liên tiếp được gọi là đoạn của chu trình.
Ma trận R có kích thước ((N + 1) x (N + 1)) được biểu diễn dưới dạng [rij], trong đó các biến nhị phân rij cho biết liệu đoạn (si, sj) có phải là một phần của chu trình UAV hay không Cụ thể, rij nhận giá trị 1 nếu một UAV ghé thăm nút CH si và sau đó di chuyển đến nút tiếp theo sj, như minh họa trong Hình 10 Nếu không, rij sẽ bằng 0 Số lần UAV đi đến và rời khỏi nút SN si được tính toán tương ứng.
Số lần UAV đi đến và rời khỏi s i phải bằng 1 nếu s i là nút CH và bằng 0 nếu trái lại
Bên cạnh đó, số lần UAV đi đến và rời khỏi trạm cơ sở không được vượt quá số lượng UAV tối đa được sử dụng M
Ma trận B (N x N) = [B i j] (i, j ∈ N*) được sử dụng để biểu diễn lượng dữ liệu truyền qua mỗi nút cảm biến và kết nối không dây trong mạng Điều này giúp tính toán chi phí năng lượng cho mỗi nút cảm biến (SN).
20 nguyên B i i , , ( i * ) đại diện cho số bit dữ liệu mà nút s i nhận được từ các nút con của nó trên cây DFT Trong khi đó, biến số nguyên B i j , , (
, *, i j i j) đại diện cho số bit dữ liệu được s i gửi đến s j qua kết nốt ( ,s s i j )
Lượng dữ liệu mà nút s i nhận được phải bằng tổng lượng dữ liệu được gửi qua tất cả các kết nối hướng đến nó, điều này được thể hiện qua ràng buộc.
Nếu nút cha s j có nút con s i (x i j, 1), thì lượng dữ liệu qua kết nối (s s i j) sẽ bằng tổng dữ liệu mà s i nhận từ các nút con B i i, cộng với dữ liệu b i mà s i thu thập từ môi trường Điều này được thể hiện qua ràng buộc.
Kỹ thuật big-M trong công thức trên được áp dụng để thể hiện một ràng buộc có điều kiện Cụ thể, nếu s_j là nút cha của s_i và x_ij = 1, thì ràng buộc trở thành B_ii ≤ b_i + B_ij, như đã phân tích trước đó Ngược lại, nếu không thỏa mãn điều kiện này, ràng buộc sẽ không được áp dụng.
, 0 x i j thì bất đẳng thức sẽ trở thành B i n b i B ij e M và luôn nhận giá trị đúng do M được chọn là một giá trị rất lớn
E (N × 1) = [ ]e i , (i ∈ *) là tập hợp các biến số thực e i thể hiện năng lượng tiêu thụ tại s i trong quá trình truyền thông qua từng chu kỳ Bằng cách áp dụng mô hình tiêu thụ năng lượng được trình bày trong CHƯƠNG 2 cùng với ma trận B, các giá trị e i có thể được tính toán một cách chính xác.
Trong ràng buộc này, năng lượng mà nút s i tiêu thụ trong chu kỳ phải luôn lớn hơn hoặc bằng tổng năng lượng mà nút này sử dụng để nhận và gửi dữ liệu, cụ thể là E B Rx i i.