Truyền thông đa mục tiêu trong Mạng cảm biến Không dây
Mạng cảm biến không dây
Mạng Cảm biến Không dây (WSNs) là một hệ thống mạng nội bộ, bao gồm các đơn vị gửi nhận tin gọi là mote, node hay nút mạng, được phân bố ở nhiều vị trí địa lý khác nhau Các thiết bị cảm biến này sử dụng các kết nối không dây như vô tuyến, hồng ngoại hoặc quang học để thu thập dữ liệu một cách phân tán và quy mô lớn Trong WSNs, nút Sink có vai trò quan trọng trong việc tập hợp dữ liệu từ các nút Sensor và gửi thông tin này đến các đơn vị quản lý giám sát, cả trực tiếp lẫn gián tiếp.
Mạng cảm biến không dây (WSNs) gặp phải nhược điểm về khả năng xử lý, lưu trữ và tương tác của các nút mạng do giới hạn tài nguyên, đặc biệt là năng lượng Điều này đã thúc đẩy các nhà khoa học nghiên cứu và cải tiến các cơ chế hoạt động bên trong WSNs để nâng cao hiệu quả hoạt động và thực hiện nhiều tác vụ hơn trong điều kiện hạn chế Luận văn này tập trung vào việc giải quyết vấn đề gia tăng hiệu năng của các nút trong mạng WSNs.
Bài toán truyền thông phân cấp
Theo thời gian, việc truyền thông trong mạng cảm biến không dây (WSNs) ngày càng phức tạp do sự gia tăng các thành phần tham gia trao đổi dữ liệu Sự khác biệt về vai trò và tầm quan trọng của các thành phần này yêu cầu phải có sự phân chia tài nguyên hợp lý Những dữ liệu từ các thành phần có vai trò quan trọng hơn trong các bài toán mà đơn vị sử dụng mạng IoT cần giải quyết sẽ được ưu tiên cấp nhiều tài nguyên hơn.
Bài toán y tế thông minh là một ứng dụng phổ biến của IoT, trong đó truyền thông phân cấp đóng vai trò quan trọng Dữ liệu y tế bao gồm hai loại: dữ liệu tình trạng khẩn cấp và dữ liệu tình huống bình thường Việc truyền tải nhanh chóng dữ liệu tình trạng khẩn cấp là rất cần thiết, vì diễn tiến của các ca cấp cứu diễn ra nhanh chóng và ảnh hưởng lớn đến tính mạng người bệnh Do tài nguyên mạng IoT có hạn, hệ thống cần phân phối tài nguyên một cách hợp lý, đảm bảo rằng dữ liệu khẩn cấp luôn được ưu tiên Điều này giúp giảm độ trễ và mất mát gói tin, cung cấp thông tin nhanh chóng và chính xác cho các bên liên quan, từ đó đưa ra quyết định kịp thời để cứu sống bệnh nhân.
Với dữ liệu thông thường, nếu việc truyền tải diễn ra ổn định, việc tăng độ trễ và giảm độ tin cậy có thể được chấp nhận.
Trong các bài toán truyền thông phân cấp, sẽ có từ hai trở lên loại dữ liệu có độ
Cơ chế truyền thông đa mục tiêu
Đồ án phục vụ cho những mục tiêu sau:
Trong hệ thống mạng cảm biến không dây (WSNs), truyền thông phân cấp được thực hiện thông qua hai loại bản tin: bản tin CD (Critical Data) và bản tin RD (Regular Data) Bản tin CD được ưu tiên hơn bản tin RD, do đó, thuật toán truyền thông cần đảm bảo tài nguyên được sử dụng cho bản tin CD trước, sau đó mới đến bản tin RD Sự khác biệt về hiệu suất giữa truyền thông bản tin CD và RD càng lớn càng cho thấy tính hiệu quả của truyền thông phân cấp trong WSNs.
Để đảm bảo hiệu năng tối ưu cho truyền thông Dữ liệu Phổ thông, các thành phần như RPL, giao thức TSCH – MAC và thuật toán xếp lịch cần được cải biến Giao thức RPL sẽ thiết lập cơ chế đa định tuyến, trong khi TSCH – MAC triển khai cơ chế truyền thông tách biệt, phục vụ cho truyền thông phân cấp Đặc biệt, thuật toán xếp lịch khe thời gian tối ưu áp dụng học máy (TOML) sẽ thay thế thuật toán xếp lịch Orchestra hiện tại, nhằm đảm bảo hiệu suất tối đa cho các tác vụ xếp lịch và nâng cao hiệu quả hoạt động của mạng.
Xây dựng cơ chế định tuyến hai đường truyền với RPL
Khái quát về RPL
Mạng cảm biến không dây (WSNs) là một hệ thống phức tạp, nơi một số nút cảm biến không thể gửi dữ liệu trực tiếp đến nút Sink do khoảng cách xa Để giải quyết vấn đề này, các giao thức định tuyến được phát triển, cho phép các nút gửi thông tin gián tiếp qua các nút trung gian thông qua cơ chế lưu trữ và chuyển tiếp Giao thức Định tuyến cho Mạng Năng lượng và Mất mát thấp (RPL) được thiết kế đặc biệt cho WSNs, tối ưu hóa quá trình định tuyến dữ liệu bằng cách tổ chức theo cấu trúc cây thay vì đồ thị, giúp giảm chi phí xử lý Cây định tuyến, được gọi là Đồ thị Có hướng Không Tuần hoàn (DAG), có nút gốc là nút Sink, trong khi các nút cảm biến khác là các nút con ở các mức cao hơn, đảm bảo rằng các nút kết nối có thể truyền nhận dữ liệu trực tiếp trong vùng phủ sóng của nhau.
Hình 1.1: Cây DAG dựa trên mạng WSNs
Trong Hình 1.1, nút Sink được biểu thị bằng nền trắng chữ đen, trong khi nút Sensor có nền đen chữ trắng Đường kẻ không có mũi tên cho thấy hai nút có thể trao đổi dữ liệu trực tiếp mà không cần nút trung gian, còn đường kẻ có mũi tên hai đầu thể hiện mối quan hệ cha con trong cây DAG, cho phép hai nút thực hiện hop với nhau Mô hình mạng WSNs bên phải Hình 1.1 là mô hình vật lý, trong khi cây DAG là sơ đồ trừu tượng Mỗi cây DAG đại diện cho đường đi dữ liệu từ một nút Sensor cụ thể đến nút Sink, và một mạng có thể có nhiều cây DAG Hình 1.1 cũng cho thấy khả năng xây dựng nhiều cây DAG cho một Mạng WSNs, phụ thuộc vào các thuật toán được sử dụng.
Hiện nay, giao thức RPL sử dụng hai thuật toán định tuyến chính là Hàm mục tiêu Trị số không (OF0) và Hàm mục tiêu Độ trễ (MRHOF) Thuật toán OF0 tính toán chi phí dựa trên mức của nút cha trong cây DAG, không xem xét các yếu tố khác, với mục đích hạn chế dữ liệu đi qua các tuyến đường vòng dài hơn trước khi đến nút Sink Ngược lại, thuật toán MRHOF ước lượng chi phí truyền tải giữa hai nút dựa trên giá trị ETX Bảng 1.1 sẽ so sánh sự khác biệt và tương đồng giữa hai thuật toán này.
Bảng 1.1 Thống kê các thiết bị và giá thành
Hạng mục Thuật toán OF0 Thuật toán MRHOP
Giống nhau Mục đích Là thuật toán định tuyến, có nhiệm vụ tím kiếm nút cha cho mỗi nút theo một tiêu chí xác định
Công thức tính toán dựa trên tổng giá trị OF của các nút cha tiềm năng, kết hợp với chi phí giữa nút cha tiềm năng và nút tính Trong quá trình lựa chọn, giá trị OF nhỏ hơn của nút cha tiềm năng sẽ được ưu tiên hơn so với nút có giá trị OF lớn hơn.
Tiêu chí Tính toán dựa trên số bước nhảy từ nút cha tiềm năng tới nút Sink
Tính toán dựa trên chi phí ước lượng (ETX) từ nút cha tiềm năng tới nút tính toán Ưu điểm Đường truyền được chọn có cây DAG ngắn nhất
Phản ánh chính xác thực tế đường truyền
Không phản ánh chính xác thực tế đường truyền
Phức tạp, khó tính toán
Đề xuất cơ chế truyền thông phân cấp
Thuật toán MRHOF chú trọng vào việc theo dõi tình trạng của mạng cảm biến không dây (WSNs), do đó, định tuyến sử dụng MRHOF sẽ có hiệu suất cao hơn so với thuật toán OF0, vốn chỉ tập trung vào sự đơn giản trong tính toán Mặc dù MRHOF có độ phức tạp tính toán cao hơn, nhưng điều này không làm giảm đáng kể hiệu suất của mạng Từ sự khác biệt giữa MRHOF và OF0, việc phân chia kênh truyền sẽ được thực hiện một cách hiệu quả hơn.
- Truyền thông Dữ liệu Quan trọng định tuyến theo thuật toán MRHOF
- Truyền thông Dữ liệu Phổ thông định tuyến theo thuật toán OF0
Việc truyền thông bản tin có độ ưu tiên cao sẽ sử dụng thuật toán định tuyến hiệu quả hơn, trong khi bản tin có độ ưu tiên thấp sẽ áp dụng thuật toán định tuyến kém hiệu quả hơn Điều này dẫn đến việc truyền thông hai bản tin với độ ưu tiên khác nhau sẽ có cách thức truyền khác nhau, giúp dàn trải việc truyền tin trên các tuyến đường khác nhau trong mạng cảm biến không dây (WSNs).
Việc phân chia định tuyến kênh truyền giúp hạn chế quá tải đường truyền do lượng bản tin lớn trên một tuyến đường Dữ liệu quan trọng sẽ được ưu tiên đi qua tuyến đường có chi phí thấp hơn, trong khi dữ liệu phổ thông sẽ phải chấp nhận đi qua tuyến đường kém thuận lợi hơn để nhường băng thông cho các bản tin quan trọng Hình 1.2 minh họa rõ ràng ưu điểm của phương pháp này.
Hình 1.2: Sự khác biệt giữa phân chia định tuyến kênh truyền
Trong Hình 1.2, hình (a) thể hiện mạng không phân chia định tuyến, trong đó cả bản tin CD và RD đều sử dụng định tuyến MRHOF để truyền dữ liệu từ nút #7 đến nút #1 Ngược lại, hình (b) là mạng phân chia định tuyến, nơi bản tin CD áp dụng thuật toán MRHOF, trong khi bản tin RD sử dụng thuật toán OF0 Định tuyến bằng thuật toán OF0 dựa vào số bước nhảy, đảm bảo đường truyền từ nút #7 đến nút #1 là ngắn nhất Trong khi đó, thuật toán MRHOF dựa trên chi phí đường truyền ETX, cho phép đường truyền dài hơn và đi vòng nhưng vẫn đảm bảo độ trễ thấp hơn so với định tuyến MRHOF.
Xây dựng cơ chế truyền thông tách biệt trong TSCH-MAC
Khái quát về TSCH-MAC
Giao thức Phân khe Nhảy kênh trên tầng MAC (Time Sloted Channel Hop - TSCH) là một giải pháp quản trị tương tranh tối ưu cho IoTs, được phát triển để khai thác lợi ích của giao thức RPL và giải quyết các thách thức trong môi trường IoTs, như quy mô lớn và hạn chế về năng lượng Các đặc điểm nổi bật của giao thức TSCH bao gồm khả năng tối ưu hóa băng thông và nâng cao hiệu suất truyền dữ liệu.
Chia hoạt động của hệ thống thành các khoảng thời gian bằng nhau, gọi là khe thời gian, với mọi nút mạng, và quy định các tác vụ cụ thể cho mỗi nút trong khoảng thời gian đó Danh sách các tác vụ liên kết với khe thời gian được gọi là lịch, và quá trình quy định tác vụ cho khe thời gian được gọi là xếp lịch.
Hoạt động của các nút mạng diễn ra theo chu kỳ, trong đó mỗi chu kỳ bao gồm một giá trị cố định gọi là khung khe Sau một số lượng khe thời gian nhất định, các nút mạng sẽ lặp lại các tác vụ đã thực hiện Các khe thời gian trong khung khe được đánh chỉ số thứ tự từ đầu đến cuối.
Hình 1.3 sẽ cho thấy mô hình hoạt động của giao thức TSCH:
Hình 1.3: Mô hình hoạt động giao thức TSCH
- Nút x là một nút tham gia WSNs
- T là thời gian chạy của WSNs từ khi được khởi chạy
- f(x)i là khung khe thứ i của nút x (i = 0 khi WSNs được khởi chạy)
Khe thời gian t(xi)j là chỉ số j trong khung khe thứ i của nút x Các tác vụ được gán bởi giao thức TSCH đóng vai trò quan trọng trong hoạt động cơ bản của mạng cảm biến không dây (WSNs).
Gửi dữ liệu (Transmit – Tx) là quá trình mà nút mạng yêu cầu gửi một gói dữ liệu qua đường truyền đến nút đích Tác vụ này đòi hỏi nút mạng phải hoạt động và tiêu thụ năng lượng để thực hiện việc truyền tải.
Nghe và nhận dữ liệu (Receive - Rx) là tác vụ yêu cầu nút mạng trực tiếp trên đường truyền để nhận gói tin từ nút nguồn, nếu có Tác vụ này đòi hỏi nút mạng phải hoạt động và tiêu thụ năng lượng.
- Tắt sóng (Sleep – S): Tác vụ yêu cầu nút mạng tắt sóng, không làm bất cứ việc gì và không tiêu thụ năng lượng
Liên hệ với Hình 1.10 biểu diễn giá trị của tác vụ Ta (Task) trong khe thời gian j thuộc chu kỳ I của nút x sẽ theo biểu thức PT 1.1 t (x i) j = Ta PT 1.1
Trong đó, các biến chịu các ràng buộc sau:
- i ϵ [0, m] với m là chỉ số khung khe Khung khe đầu tiên được đánh chỉ số i = 0 khi WSNs khởi chạy
- j ϵ [0, n] với n là độ dài khung khe
Trong mạng, các nút Tx và Rx tiêu tốn năng lượng trong khi nút S không tiêu tốn năng lượng Khi nút mạng được gán nhiều tác vụ S, năng lượng tiêu thụ sẽ giảm Xung đột xảy ra khi có hơn hai nút cùng thực hiện tác vụ Tx trong cùng một khe thời gian và khung khe Việc giới hạn và định danh cụ thể các tác vụ giúp việc phát hiện xung đột trở nên dễ dàng hơn so với các cơ chế cảm biến sóng trong giao thức CSMA/CD.
Đề xuất cơ chế truyền thông tách biệt trên TSCH-MAC
Thuật toán xếp lịch sử dụng phương pháp truyền thông tách biệt, cho phép gửi và nhận một instance cụ thể trong khe thời gian Quy trình hoạt động của nút mạng trong phương pháp này được minh họa qua sơ đồ khối trong Hình 1.4.
Hình 1.4: Cơ chế Truyền thông tách biệt theo loại dữ liệu với hai loại tác vụ
Trong Hình 1.4, i là giá trị instance của bản tin, trong khi j là giá trị instance của bản tin được chấp nhận trong khe thời gian Cả i và j đều thuộc tập giá trị {1, 2} Mặc dù phương pháp truyền thông tách biệt với khe thời gian có nhiều ưu điểm, nhưng cũng tồn tại nhược điểm là các gói tin không phù hợp với loại dữ liệu của khe thời gian sẽ bị xếp hàng chờ, dẫn đến tăng độ trễ Điều này làm giảm hiệu suất, đặc biệt với các bản tin CD Để khắc phục, cần sắp xếp các loại bản tin được phép truyền trong khung khe sao cho thời gian chờ của mỗi gói tin là thấp nhất, ảnh hưởng đến hiệu suất mạng là không đáng kể Cách bố trí tối ưu là theo chu kỳ luân phiên với khoảng cách giữa các khe thời gian.
Khung khe thời gian cho phép truyền bản tin ngắn gọn, với khoảng cách giữa hai khe thời gian cho bản tin CD thấp hơn so với bản tin RD, nhằm phục vụ truyền thông phân cấp Mỗi khung khe sẽ được chia thành một hoặc nhiều chu kỳ instance, tùy thuộc vào độ dài của khung khe Mỗi chu kỳ instance sẽ có hai dải khe thời gian: một cho truyền thông CD và một cho truyền thông RD Do bản tin CD được ưu tiên hơn, việc bố trí dải khe thời gian cần đảm bảo rằng bản tin CD sẽ có thời gian chờ ít hơn so với bản tin RD.
Dải kênh truyền thông bản tin CD sẽ dài hơn dải kênh truyền thông RD Cụ thể, dải kênh dành cho RD chỉ bao gồm từ 1 hoặc 2 kênh.
Trong hệ thống truyền thông, hai khe thời gian sẽ được sử dụng cho dải kênh truyền thông bản tin CD, trong khi các khe thời gian còn lại phục vụ cho bản tin RD Độ dài dải kênh cho bản tin CD sẽ gấp từ 3 đến 4 lần so với bản tin RD, do đó, các gói tin CD chỉ cần chờ tối đa 2 khe thời gian dành cho RD Thời gian chờ này là rất ngắn, không ảnh hưởng đáng kể đến hiệu năng truyền thông của Dữ liệu Quan trọng.
Dải kênh truyền thông bản tin CD sẽ được ưu tiên trước dải kênh truyền thông bản tin RD, đảm bảo rằng khi mạng được khởi tạo, bản tin CD luôn được phát trước Trong các mạng cảm biến không dây (WSNs) quy mô nhỏ và ổn định, điều này không quan trọng do chỉ có một lần khởi chạy Tuy nhiên, trong các mạng quy mô lớn và biến động, nơi các nút mạng thường tham gia và rời đi, việc ưu tiên truyền thông bản tin CD sẽ tạo ra sự khác biệt lớn.
Hình 1.5 minh họa cách bố trí dải kênh, trong đó mỗi ô chữ nhật màu trắng biểu thị một khe thời gian cho bản tin CD, còn mỗi ô chữ nhật có kẻ chéo đại diện cho khe thời gian dành cho bản tin RD.
Hình 1.5: Biểu diễn dài khe thời gian trên một khung khe
Thiết kế dải khe thời gian trong Hình 1.5 đáp ứng các tiêu chí đã đề cập, với số kênh tối đa dành cho instance 2 chỉ là 2 Đồng thời, số kênh dành cho bản tin CD phải gấp ít nhất 3 lần so với số kênh dành cho bản tin RD Cụ thể, độ dài dải kênh cho bản tin RD là 2 khe thời gian, trong khi độ dài dải kênh cho bản tin CD là 8 khe thời gian, gấp 4 lần Do đó, trong trường hợp tối thiểu, độ dài dải kênh cho bản tin RD là 1 khe thời gian.
9 cho bản tin CD tối thiểu phải là 4 khe thời gian và độ dài một chu kỳ instance là
Trong một khung khe thời gian, số lượng chu kỳ instance là yếu tố quan trọng cần xem xét Mỗi nút mạng thực hiện hai tác vụ cơ bản là gửi và nhận tin, do đó, bản tin RD yêu cầu tối thiểu 2 khe thời gian trong một khung khe Điều này có nghĩa là một khung khe cần ít nhất 1 chu kỳ instance nếu mỗi chu kỳ dành 2 khe thời gian truyền bản tin RD, hoặc tối thiểu 2 chu kỳ instance nếu mỗi chu kỳ chỉ dành 1 kênh Để giảm thiểu nguy cơ mất mát gói tin, khung khe nên có 2 chu kỳ instance, ngay cả khi mỗi chu kỳ dành 2 kênh truyền tin Bên cạnh đó, độ dài tối thiểu của khung khe cũng phải đảm bảo đủ khe thời gian cho phép truyền thông bản tin RD, tối thiểu bằng tổng số nút mạng, nhằm đảm bảo mọi nút đều có thể thực hiện tác vụ Tx ở các khe thời gian khác nhau trong khung khe.
CD luôn lớn hơn số khe thời gian cho phép truyền thông bản tin RD Do đó, nếu độ dài khung khe đủ để đáp ứng số khe thời gian cho mọi nút gửi bản tin RD trên các khe thời gian khác nhau, thì nó cũng sẽ đáp ứng điều kiện cho bản tin RD Vì vậy, số khe thời gian trong một khung khe cần phải thỏa mãn bất đẳng thức PT 1.2.
- L là số khe thời gian trong một khung khe
- MCD là số khe thời gian cho phép truyền thông bản tin CD trong một chu kỳ instance
- MRD là số khe thời gian cho phép truyền thông bản tin RD trong một chu kỳ instance
- l là một thừa số tự nhiên, số chu kỳ instance trong một khung khe
- K là tổng số nút trong WSNs
Độ dài khe thời gian trong thuật toán xếp lịch truyền thông phân cấp áp dụng học máy cần thỏa mãn hai tiêu chí quan trọng: đầu tiên, độ dài tối thiểu phải đáp ứng bất đẳng thức PT 1.2 để đảm bảo không xảy ra xung đột khi hai nút cùng gửi tin, đặc biệt là với các bản tin RD Thứ hai, việc triệt tiêu xung đột còn phụ thuộc vào tần suất gửi tin; độ dài khung khe càng lớn thì khả năng xung đột càng thấp Tuy nhiên, giao thức TSCH quản lý theo từng khung khe, vì vậy nếu độ dài khung khe quá lớn, giao thức sẽ yêu cầu nhiều bộ nhớ hơn để lưu trữ thông tin của từng khe thời gian, dẫn đến những ảnh hưởng không mong muốn.
Độ dài khung khe tối thiểu được khuyến cáo trong mạng bình thường là yếu tố quan trọng để duy trì hiệu năng của toàn mạng và đảm bảo mục đích của các cải tiến không bị triệt tiêu Khi tần suất gửi dữ liệu không cao, việc tuân thủ bất đẳng thức PT 1.2 là cần thiết để tối ưu hóa hoạt động mạng.
Xây dựng Thuật toán xếp lịch Khe thời gian Tối ưu dựa trên Học máy 10
Thuật toán xếp lịch Orchestra
Giao thức TSCH chủ yếu phân khe thời gian và gán tác vụ, trong khi việc gán tác vụ cụ thể phụ thuộc vào một danh sách các cơ chế và quy tắc được gọi là thuật toán xếp lịch Thuật toán này bao gồm nhiều phương pháp xếp lịch cho các loại gói tin khác nhau, với nhiệm vụ gán tác vụ cho các nút sao dựa trên các tiêu chí nhất định nhằm đạt được mục tiêu cụ thể Hiện nay, thuật toán xếp lịch phổ biến nhất trong giao thức TSCH là Orchestra.
Thuật toán xếp lịch Orchestra hoạt động dựa trên việc cân bằng giữa nguy cơ xảy ra xung đột và tiêu thụ năng lượng Nếu thuật toán tập trung vào việc triệt tiêu hoàn toàn xung đột, nó sẽ tiêu tốn nhiều năng lượng, trong khi nếu chú trọng tiết kiệm năng lượng, nguy cơ xung đột sẽ tăng cao Để thực hiện xếp lịch, thuật toán đánh chỉ số cho tất cả các nút mạng và chọn một tác vụ mục tiêu từ hai tác vụ Rx và Tx Trong mỗi khung khe, tác vụ mục tiêu sẽ được gán cho các nút theo thứ tự chỉ số, cùng với việc phân bổ các khe thời gian tương ứng Hai cơ chế xếp lịch chính được áp dụng trong quá trình này.
Hướng gửi tin (Sender-based) là một quy trình trong đó tác vụ mục tiêu được thực hiện theo thứ tự, cụ thể là tác vụ Tx (gửi tin) Trong mỗi khe thời gian, các nút khác, ngoại trừ nút thực hiện tác vụ mục tiêu, sẽ thực hiện tác vụ Rx để chờ nhận gói tin từ nút được chỉ định cho tác vụ Tx.
Trong phương pháp nhận tin dựa trên người nhận (Receiver-based), tác vụ mục tiêu chủ yếu là tác vụ nhận tin (Rx) Trong mỗi khe thời gian, các nút không được gán tác vụ mục tiêu sẽ được chia thành hai nhóm: nhóm có gói tin cần gửi đến nút gán tác vụ mục tiêu Rx hoặc nút Sink sẽ được gán tác vụ gửi tin (Tx), trong khi các nút còn lại sẽ được gán tác vụ giữ im lặng (S).
Hình 1.6 sẽ chỉ rõ nguyên tắc làm việc của hai cơ chế này đối với mạng 4 nút và khung khe có 4 khe thời gian:
Hình 1.6: Cơ chế Sender-based và cơ chế Receivered-base
Theo Hình 1.6, trong cơ chế Sender-based, các nút luôn hoạt động, dẫn đến việc tiêu tốn nhiều năng lượng Tuy nhiên, do các tác vụ Tx được gán liên tiếp, xung đột giữa các nút mạng không xảy ra.
Trong môi trường mạng, việc thực hiện 11 tác vụ Tx trong cùng một khe thời gian là không khả thi Ngược lại, cơ chế Receiver-based tiềm ẩn nguy cơ xung đột khi hai nút mạng có thể thực hiện tác vụ Tx đồng thời trong cùng một khe thời gian Bảng 1.2 sẽ trình bày sự so sánh giữa hai cơ chế Sender-based và Receiver-based, nêu rõ những điểm tương đồng và khác biệt giữa chúng.
Bảng 1.2 So sánh Sender-based và Receiver-based
Hạng mục Cơ chế Sender-based Cơ chế Receiver-based
Giống nhau Mục đích Là cơ chế xếp lịch của thuật toán xếp lịch Orchestra phục vụ một mục tiêu cụ thể
Vị trí Thuật toán xếp lịch Orchestra của giao thức TSCH đối với bản tin mạng dữ liệu cảm biến
Cơ chế đếm số nút mạng và độ dài khe thời gian rất quan trọng trong việc xác định và gán tác vụ mục tiêu Điều này đảm bảo rằng không có hai tác vụ mục tiêu nào được gán trên cùng một khe thời gian, giúp tối ưu hóa hiệu suất và quản lý tài nguyên mạng hiệu quả.
Tác vụ mục tiêu Tác vụ Tx Tác vụ Rx
Tác vụ còn lại Tác vụ Rx Tác vụ Rx hoặc S Ưu điểm Không có Xung đột Tiết kiệm năng lượng
Nhược điểm Tiêu tốn năng lượng Xung đột
Tập luật Orchestra đã đạt được mục tiêu của mình với cơ chế Sender-based nhằm triệt tiêu sự tương tranh và cơ chế Receiver-based để tiết kiệm năng lượng Mặc dù thuật toán xếp lịch Orchestra có nhiều ưu điểm, nhưng vẫn tồn tại một số nhược điểm cần lưu ý.
- Hiệu năng bị triệt tiêu lẫn nhau trong tình huống cực đoan:
Orchestra hỗ trợ hai cơ chế: Sender-based nhằm triệt tiêu tương tranh và Receiver-based tập trung vào tiết kiệm năng lượng Tuy nhiên, khi thực hiện một mục tiêu, cả hai cơ chế đều hy sinh mục tiêu còn lại, dẫn đến những hệ quả không tốt do sự tác động qua lại giữa chúng Ví dụ, khi nút mạng cạn kiệt năng lượng, nó sẽ ảnh hưởng đến hoạt động gửi nhận và phân tích gói tin, thậm chí có thể dừng hoạt động mạng Ngược lại, khó khăn trong việc gửi nhận tin cũng làm tiêu tốn năng lượng và kích hoạt các cơ chế xử lý đặc thù Do đó, cần thiết phải có một thuật toán xếp lịch thay thế cho luật Orchestra, nhằm dung hòa giữa tỷ lệ mất gói tin và mức tiêu thụ năng lượng, đảm bảo WSNs hoạt động hiệu quả mà không triệt tiêu lẫn nhau.
- Thuật toán xếp lịch Orchestra dựa hoàn toàn vào các thông số không biểu thị hiệu năng và tình trạng hoạt động của WSNs:
Thuật toán xếp lịch Orchestra trong mạng cảm biến không dây (WSNs) tập trung vào tiêu chí duy nhất là số nút mạng Nó thực hiện việc đánh chỉ số, chọn một tác vụ mục tiêu và gán tác vụ đó cho từng nút một cách tuần tự.
Số lượng nút mạng và chỉ số không phản ánh chính xác hiệu năng và tình trạng hoạt động của các Mạng cảm biến không dây (WSNs) Hiệu năng của WSNs phụ thuộc vào nhiều yếu tố đa dạng như môi trường truyền thông, đặc tính bản tin và loại nút mạng Với sự đa dạng của các WSNs và đặc điểm truyền thông khác nhau, việc chỉ dựa vào số nút mạng để đánh giá hiệu quả truyền thông là không đủ Do đó, luật Orchestra có thể hoạt động hiệu quả với các WSNs thông thường, nhưng có thể không phù hợp với những WSNs có đặc thù truyền thông riêng.
Thuật toán xếp lịch của Orchestra giữ cố định việc gán tác vụ cho các nút mạng từ khi mạng được khởi tạo cho đến khi ngừng hoạt động Trong môi trường mạng quy mô lớn và lâu dài, với nhiều biến động như các nút gia nhập và rời khỏi mạng, thay đổi trong môi trường truyền thông, cấu trúc cây RPL, yêu cầu bài toán và nội dung bản tin, phương thức xếp lịch đều đặn của Orchestra sẽ không phản ánh chính xác tình hình thực tế của mạng Điều này dẫn đến độ vênh và giảm hiệu năng của các mạng cảm biến không dây (WSNs).
Thuật toán xếp lịch Orchestra không hỗ trợ truyền thông phân cấp, điều này khiến nó không còn phù hợp trong bối cảnh phân chia dải kênh theo instance Khi một nút được gán tác vụ gửi nhưng không trùng instance, có thể xảy ra mất mát gói tin hoặc tăng độ trễ không cần thiết Mặc dù hiện tại, những nhược điểm này chưa ảnh hưởng lớn đến hiệu năng mạng WSNs và giao thức TSCH trong giai đoạn thử nghiệm, nhưng khi quy mô mạng tăng lên và ứng dụng vào các bài toán lớn như y tế thông minh hay thành phố thông minh, những vấn đề của thuật toán Orchestra sẽ dần bộc lộ Do đó, việc tìm kiếm một thuật toán xếp lịch thay thế là rất cần thiết, với yêu cầu phải giải quyết các nhược điểm của Orchestra và đảm bảo tương thích với cơ chế phân chia đường truyền.
Tiêu chí đánh giá hiệu năng mạng
Hiệu năng mạng là khái niệm trừu tượng, vì vậy để đánh giá và áp dụng vào thuật toán học máy, cần xây dựng bộ tiêu chí đánh giá hiệu năng Trong số nhiều tiêu chí đánh giá mạng Internet và WSNs, hai tiêu chí quan trọng nhất là Tỉ lệ truyền nhận thành công và độ trễ Đối với truyền thông phân cấp, mỗi loại instance của bản tin sẽ có thông số riêng để tính toán.
13 a) Tỉ lệ truyền nhận thành công:
Tỉ lệ truyền nhận thành công (Packet Delivery Ratio - PDR) là tỷ lệ phần trăm giữa số gói tin đến được đích so với tổng số gói tin được gửi đi PDR cho biết bao nhiêu phần trăm gói tin đã được gửi thành công đến đích Công thức tính PDR của một nút mạng được trình bày trong PT 1.3.
- PDR là Tỉ lệ truyền nhận thành công, đơn vị tính là %
- R là Tống số gói tin mà tất cả các nút mạng nhận được từ nút đo đạc
- S là Tống số gói tin mà nút mạng đã gửi
PDR (Packet Delivery Ratio) càng cao chứng tỏ mạng WSNs hoạt động hiệu quả, với PDR từ 90% trở lên đảm bảo sự ổn định, trong khi PDR dưới 70% có thể dẫn đến tình trạng tê liệt mạng PDR thấp đồng nghĩa với việc ít bản tin đến đích, cản trở hoạt động của các giao thức duy trì mạng, đặc biệt là những giao thức yêu cầu cơ chế bắt tay chặt chẽ Khi PDR quá thấp, giao thức không thể hoạt động thành công, dẫn đến ngừng hoạt động của WSNs và tăng tiêu thụ năng lượng Do đó, PDR là tiêu chí quan trọng phản ánh khả năng truyền tải thông tin an toàn và đầy đủ từ nguồn đến đích trong mạng WSNs.
Tỉ lệ mất gói tin (Packet Loss Ratio - PLR) là chỉ số quan trọng phản ánh số lượng gói tin bị mất trong quá trình truyền thông mạng, đối lập với PDR Công thức tính PLR được thể hiện trong PT 1.4.
- PLR là Tỉ lệ mất gói tin, đơn vị tính là %
- PDR, L và R tương tự PT 1.3
Trong bài viết này, hiệu năng được đo chủ yếu bằng tiêu chí PDR, tuy nhiên, trong một số trường hợp liên quan đến tình trạng mất mát gói tin, PLR cũng sẽ được sử dụng để tăng tính trực quan Độ trễ (Latency) là thời gian trung bình mà một bản tin di chuyển từ nút nguồn đến đích, phản ánh tổng thời gian truyền tải trong môi trường mạng Độ trễ được đo bằng các đơn vị thời gian như giây, mili giây và nano giây Công thức PT 1.5 được áp dụng để tính toán độ trễ của một nút mạng.
- n là Tổng số gói tin đến được đích
Chỉ số i là chỉ số đánh cho tất cả gói tin đến đích theo trình tự thời gian gửi, trong đó gói tin đầu tiên được đánh chỉ số 1 và gói tin gửi gần nhất được đánh chỉ số n.
- T(R)i là thời điểm gói tin chỉ số i mà tất cả các nút trừ nút đo đạc đã nhận
T(S)i là thời điểm mà gói tin chỉ số I bắt đầu được gửi từ nút mạng Độ trễ lớn cho thấy gói tin mất nhiều thời gian để đến đích, điều này chứng tỏ sự chậm trễ trong quá trình truyền tải dữ liệu.
Tuyến đường bản tin ngày càng dài do ảnh hưởng của các hàm OF trong giao thức định tuyến, dẫn đến việc bản tin phải đi vòng để đến đích.
Chất lượng đường truyền kém thường xuất phát từ nhiều yếu tố trong môi trường mạng, bao gồm sự ảnh hưởng của dung môi xung quanh, giao thoa tín hiệu và nhiễu loạn.
Độ trễ trong mạng chủ yếu làm chậm giao thức mà không ảnh hưởng nghiêm trọng đến hoạt động của nó, tuy nhiên, khi độ trễ quá cao, nó có thể dẫn đến việc nhiều gói tin cùng lúc trên đường truyền, gây ra xung đột Hiện tượng này không chỉ giảm tỷ lệ phân phối gói tin (PDR) mà còn làm tăng mức tiêu thụ năng lượng.
Tiền đề áp dụng học máy trong xây dựng thuật toán xếp lịch
Bài toán phân loại trong học máy là việc áp dụng các kỹ thuật học máy để gán nhãn cho một tập dữ liệu dựa trên những đặc điểm chung Hai dữ liệu có nhãn giống nhau sẽ sở hữu những đặc điểm tương tự Phân loại trong học máy được chia thành hai loại chính: phân loại nhiều lớp và phân loại đa nhãn.
Phân loại nhiều lớp là quá trình gán một nhãn duy nhất cho mỗi dữ liệu, tập trung vào việc thống kê số lượng dữ liệu tương ứng với từng nhãn Ví dụ điển hình cho phương pháp này là phân loại giữa các nước phát triển và đang phát triển, như đã đề cập ở phần trước.
Phân loại đa nhãn cho phép gán một hoặc nhiều nhãn vào dữ liệu, thậm chí không gán nhãn nào Bài toán này thường tập trung vào việc thống kê các nhãn có trong dữ liệu, ví dụ như nhận dạng khuôn mặt và gán nhãn đường dẫn trên ảnh của Facebook Sự cần thiết của việc áp dụng kỹ thuật học máy trong phân loại đa nhãn ngày càng trở nên quan trọng để cải thiện độ chính xác và hiệu quả trong việc xử lý dữ liệu phức tạp.
Dựa trên những phân tích ở phần 1.4.1, chúng ta đã nhận diện được những hạn chế của thuật toán xếp lịch Orchestra và sự cần thiết phải thay thế nó bằng một thuật toán xếp lịch tiên tiến hơn Thuật toán mới cần đảm bảo hiệu suất cho mạng cảm biến không dây (WSNs) trong các tình huống khác nhau và có khả năng thay đổi cơ chế gán tác vụ theo thời gian Mục tiêu chính là giảm thiểu tối đa mất mát gói tin Tuy nhiên, với sự đa dạng và phức tạp của mạng WSNs, việc phát triển một thuật toán xếp lịch toàn diện là một thách thức lớn.
Việc thiết kế 15 lịch trình phù hợp cho các loại WSNs khác nhau trong nhiều tình huống và môi trường là một thách thức phức tạp và tốn kém, nhằm giảm thiểu tỉ lệ mất gói tin Kỹ thuật học máy có khả năng giúp máy móc học hỏi từ kinh nghiệm quá khứ thông qua các thử nghiệm, đánh giá hiệu suất dựa trên mục tiêu cụ thể Điều này cho thấy vai trò quan trọng của học máy trong việc phát triển thuật toán xếp lịch linh hoạt, có khả năng thích ứng với nhiều loại mạng và thay đổi theo thời gian để tối ưu hóa việc giảm thiểu tỉ lệ mất gói tin Hơn nữa, việc tự động hóa cao trong quá trình này giảm thiểu sự can thiệp của con người Do đó, việc tích hợp kỹ thuật học máy vào xây dựng tập thuật toán xếp lịch thay thế Orchestra là một giải pháp hiệu quả và đúng hướng.
Mục đích của thuật toán học máy trong xếp lịch TSCH-MAC là xác định tác vụ cho từng nút trong mỗi khe thời gian nhằm giảm thiểu tỉ lệ mất mát gói tin trong toàn bộ mạng cảm biến không dây (WSNs) Thuật toán này sẽ quyết định tác vụ tối ưu cho mỗi nút mạng ở các kênh thời gian cụ thể, đảm bảo hiệu quả hoạt động cao nhất.
Đề xuất thuật toán xếp lịch TOML
1.4.4.1 Quy trình hoạt động của thuật toán học máy
Theo nguyên lý của thuật toán học máy, thuật toán xếp lịch được chia thành hai giai đoạn: giai đoạn học và giai đoạn áp dụng Giai đoạn áp dụng thường kéo dài gấp tối thiểu 9 lần giai đoạn học, với thời gian mỗi giai đoạn phụ thuộc vào đặc điểm bài toán và WSNs Đối với hệ thống thời gian thực, mỗi giây sẽ là một chu trình học máy, trong đó 100 ms đầu là thời gian học và 900 ms sau là thời gian áp dụng Trong các hệ thống khác, thời gian cho chu trình học máy có thể lâu hơn, nhưng vẫn cần đủ ngắn để đạt điểm Good Fit Đối với bài toán xếp lịch trên giao thức TSCH, sự đa dạng dữ liệu hạn chế, chỉ xoay quanh 3 tác vụ chính.
Trong quá trình học máy, việc học từ 20 đến 30 lần cho mỗi tác vụ giúp đảm bảo độ chính xác đạt mức Good Fit Một thách thức tiếp theo là xây dựng cơ chế gán tác vụ cho từng nút trong các khe thời gian cụ thể, cả trong giai đoạn học và giai đoạn kiểm tra.
Mục đích của giai đoạn này là xây dựng kho dữ liệu phục vụ cho việc huấn luyện và lựa chọn Trong giai đoạn này, mọi tác vụ cần được gán vào một khe thời gian để đánh giá hiệu năng của từng kênh trong từng nút mạng Tuy nhiên, trong ba tác vụ, tác vụ S sẽ khiến nút mạng không hoạt động trong quá trình trao đổi mạng, do đó không thể đánh giá được hiệu suất.
16 năng, chính vì lẽ đó, trong giai đoạn học sẽ chỉ có hai tác vụ được gán là tác vụ
Việc loại bỏ tác vụ S trong cơ chế Sender-based của tập luật Orchestra có thể tiêu tốn năng lượng, nhưng vẫn đảm bảo tính ổn định và khả thi Thời gian giai đoạn học không kéo dài, và trong giai đoạn áp dụng sau, tác vụ S sẽ được gán vào khe thời gian phù hợp.
Trong giai đoạn xếp lịch, cần chú ý đảm bảo rằng trong cùng một khe thời gian, hai nút hàng xóm phải được gán tác vụ khác nhau Nhiệm vụ của các nút trong mạng cảm biến không dây (WSNs) là thực hiện các truyền thông, trong đó thông tin sẽ được gửi từ nút gán tác vụ Tx đến nút gán tác vụ Rx Giải pháp đưa ra là tại mỗi khe thời gian, một nút sẽ chọn ngẫu nhiên giữa tác vụ Tx và Rx, theo quy luật xác suất thống kê, số lần khe thời gian được gán Tx và Rx sẽ bằng nhau, mỗi loại là 0.5 Tuy nhiên, thực tế có nhiều yếu tố ngoại cảnh ảnh hưởng đến việc phân bổ này.
Sự chênh lệch giữa Tx và số lần khe thời gian được gán Tx là nhỏ và chiếm tỷ lệ không đáng kể so với không gian mẫu Mặc dù có nhược điểm là khả năng toàn mạng không có cặp nút hàng xóm gán tác vụ khác nhau, nhưng tỷ lệ này giảm khi số nút mạng tăng và thời gian kéo dài, theo quy tắc nhân trong lý thuyết xác suất Giải pháp chọn tác vụ ngẫu nhiên cho thấy hiệu quả cao hơn trong thuật toán học máy, đặc biệt là đối với mạng quy mô lớn và việc lựa chọn nút mạng, và sẽ được áp dụng để gán tác vụ cho các nút mạng trong giai đoạn học.
Trong giai đoạn áp dụng, thuật toán sẽ lựa chọn tác vụ tối ưu từ ba lựa chọn: tác vụ Tx, tác vụ Rx và tác vụ S, dựa trên dữ liệu từ hàm đánh giá Cơ chế vận hành và xây dựng hàm đánh giá sẽ được trình bày chi tiết ở phần sau.
Hoạt động của thuật toán học máy trong thuật toán xếp lịch TOML bao gồm các chu trình học máy, mỗi chu trình có một số lượng khung khe cụ thể và chia thành hai giai đoạn: Giai đoạn học và Giai đoạn áp dụng Trong Giai đoạn học, các nút mạng sẽ gán ngẫu nhiên các tác vụ giữa Tx và Rx để xây dựng tập dữ liệu huấn luyện Sau đó, hàm đánh giá sẽ xác định tác vụ tối ưu nhất cho mỗi khe thời gian, và trong Giai đoạn áp dụng, các nút mạng sẽ gán tác vụ tối ưu đó cho các khung khe.
1.4.4.2 Xây dựng hàm đánh giá
Một trong những nhiệm vụ quan trọng trong việc xây dựng hàm đánh giá là phát triển cơ chế tính giá trị hiệu năng cho từng tác vụ cụ thể, nhằm tối ưu hóa hiệu suất của mạng cảm biến không dây (WSNs) Tương tự như các hàm đánh giá trong học máy khác, thách thức lớn nhất khi xây dựng hàm đánh giá cho xếp lịch trong chế độ TSCH là đảm bảo tính bám sát thực tế, tức là cơ chế tính hiệu năng của thuật toán học máy cần phản ánh chính xác hiệu suất của WSNs.
Xây dựng hàm đánh giá trong cơ chế RL-MAC gặp thách thức lớn khi định nghĩa thành công và thất bại của các tác vụ, nhằm đảm bảo tỷ lệ thành công phản ánh chính xác hiệu năng mạng Mỗi tác vụ có những đặc điểm và ảnh hưởng khác nhau đến hiệu năng mạng, bao gồm hai tiêu chí chính là Tỷ lệ mất gói (PDR) và Độ trễ.
Hàm đánh giá trong thuật toán xếp lịch TOML được phát triển từ nghiên cứu của Tiến sĩ Phùng Kiều Hà tại Đại học Bách Khoa Hà Nội và Giáo sư Kris Steenhaut từ Vrije Universiteit Brussel vào năm 2014 Nghiên cứu này tập trung vào thiết kế cơ chế RL-MAC, bao gồm phân khe thời gian theo giao thức TSCH, và xây dựng một thuật toán xếp lịch cho cơ chế phân kênh Đặc biệt, thuật toán xếp lịch trong RL-MAC đã ứng dụng học máy để tối ưu hóa tác vụ, mang lại một phương pháp xếp lịch tiên tiến và được đánh giá cao, với hàm đánh giá tích hợp các thành tựu về trí tuệ nhân tạo và kỹ thuật học máy.
Việc kế thừa thuật toán xếp lịch từ các thế hệ trước là cần thiết để tận dụng những thành quả tốt nhất, trong đó thuật toán xếp lịch TOML chỉ kế thừa hàm đánh giá các tác vụ sử dụng kỹ thuật học máy mà không sao chép toàn bộ cơ chế RL-MAC Mặc dù RL-MAC có nhiều điểm tương đồng với giao thức TSCH, nhưng các thông số cấu hình và định nghĩa hoạt động lại có sự khác biệt Quan trọng hơn, mã nguồn của cơ chế RL-MAC không được công khai như Orchestra, dẫn đến khó khăn trong việc quan sát cấu hình và tích hợp chính xác Đề xuất của Tiến sĩ Phùng Kiều Hà về định nghĩa tác vụ thành công và thất bại sẽ được trình bày trong Bảng 2.1.
Bảng 1.3 Định nghĩa tác vụ thành công và thất bại trong RL-MAC
Tác vụ Thành công Thất bại
Tx Gói tin đã được gửi trong tác vụ đấy và được nút đích nhận
Gói tin đã được gửi nhưng không đến đích
Rx Nhận được gói tin Không nhận được gói tin
Trong Bảng 2.1, các tác vụ được coi là thành công khi hoàn thành nhiệm vụ của mình: tác vụ gửi Tx yêu cầu nút mạng gửi gói tin, trong khi tác vụ nhận Rx phải nhận được gói tin Nếu nhiệm vụ không được hoàn thành, tác vụ sẽ được định nghĩa là thất bại Để xây dựng dữ liệu đầu vào cho hàm đánh giá, cần áp dụng thuật toán xếp lịch TOML.
Hàm đánh giá trong cơ chế RL-MAC gặp phải nhược điểm là tỉ lệ thành công của các tác vụ không phản ánh chính xác hiệu năng mạng Sự khác biệt trong việc đánh giá tác vụ thành công và tổng số tác vụ là rõ rệt; ví dụ, đối với Rx, tất cả các lần khe thời gian được gán tác vụ Rx (bao gồm cả thành công và thất bại) đều được tính vào mẫu, trong khi đó, đối với Tx, chỉ những lần gán tác vụ Tx có khe thời gian được gửi đi mới được tính Cuối cùng, mẫu chung lại tổng hợp cả số lượng mẫu trong Tx và Rx.
Trong một mạng có tần suất gửi tin thấp, số lượng khe thời gian gửi tin sẽ ít hơn so với số khe thời gian được phân bổ, dẫn đến sự chênh lệch giữa tỉ lệ thành công Tx và Rx Điều này có thể gây ra việc lựa chọn tác vụ Rx trong khi khe thời gian đó thực sự nên được dành cho tác vụ Tx hoặc S Do đó, cần phải điều chỉnh cơ chế tính tỉ lệ thành công để đảm bảo đánh giá công bằng giữa Tx và Rx Giao thức TSCH coi các khe thời gian trong khung khe là bình đẳng, cho phép các nút lưu trữ dữ liệu của tất cả các khe thời gian Từ đó, có thể sử dụng tỉ lệ thành công cao nhất trong một khe thời gian làm giá trị tham chiếu để đánh giá hiệu quả của các khe thời gian khác Cơ chế đánh giá dữ liệu đầu vào sẽ bao gồm hai bước.
- Bước 1: Tính giá trị tham chiếu:
