Luận văn thạc sĩ về kiểm chứng tắc nghẽn trong mạng cảm ứng không dây sử dụng Coloured Petri Net

Khám phá luận văn thạc sĩ về biểu diễn và kiểm chứng tắc nghẽn mạng cảm ứng không dây bằng coloured Petri net trong khoa học máy tính.

• Tác giả: Đào Thị Thu Trang
• Người hướng dẫn: TS. Bùi Hoài Thắng
• Trường học: Đại học Bách Khoa - ĐHQG - HCM
• Chuyên ngành: Khoa học máy tính
• Đề tài: Biểu Diễn Và Kiểm Chứng Tắc Nghẽn Với Xác Suất Trên Mạng Cảm Ứng Không Dây Bằng Coloured Petri Net
• Loại tài liệu: luận văn thạc sĩ
• Năm xuất bản: 2017
• Địa điểm: TP. Hồ Chí Minh

Tóm tắt

I. Tổng quan

Mạng cảm ứng không dây (Wireless Sensor Network - WSN) là một ứng dụng quan trọng trong lĩnh vực Internet of Things. WSN được sử dụng để giám sát các điều kiện môi trường, đặc biệt là ở những khu vực khó tiếp cận. Tuy nhiên, việc phát hiện và kiểm tra các tính chất trong mạng như tắc nghẽn là điều cần thiết để đảm bảo hoạt động hiệu quả. Tắc nghẽn trong WSN xảy ra khi dữ liệu không thể được truyền từ cảm biến nguồn đến cảm biến đích do nhiều yếu tố như hư hỏng thiết bị hoặc quá tải dữ liệu. Đề tài này sẽ tập trung vào việc sử dụng mô hình Coloured Petri Net (CPN) để kiểm chứng tắc nghẽn trong WSN, từ đó đưa ra những giải pháp khả thi để cải thiện hiệu suất mạng.

1.1. Mục tiêu và giới hạn

Mục tiêu chính của luận văn là nghiên cứu và phát triển một mô hình xác suất cho WSN bằng cách sử dụng Coloured Petri Net. Đề tài cũng hướng tới việc xây dựng một công cụ hỗ trợ cho việc mô hình hóa và kiểm tra tắc nghẽn trong WSN. Tuy nhiên, nghiên cứu vẫn có những giới hạn nhất định như số lượng cảm biến trong thử nghiệm còn ít và các yếu tố xác suất chưa được khai thác sâu. Những hạn chế này mở ra cơ hội cho các nghiên cứu tiếp theo nhằm cải thiện tính thực tiễn của mô hình.

II. Kiến thức nền tảng

Phần này sẽ trình bày các kiến thức cần thiết để hiểu rõ về mô hình WSN và Coloured Petri Net. WSN bao gồm các cảm biến được phân bố rộng rãi để thu thập dữ liệu về môi trường. Các cảm biến này có thể gặp phải vấn đề tắc nghẽn trong quá trình truyền dữ liệu. Để giải quyết vấn đề này, mô hình Petri Net đã được sử dụng, cho phép mô hình hóa các trạng thái và hành động của mạng. Coloured Petri Net là một phiên bản nâng cao của Petri Net, cho phép phân biệt các token bằng màu sắc, từ đó cung cấp nhiều thông tin hơn về trạng thái của hệ thống. Mô hình này có thể giúp phát hiện và kiểm tra tắc nghẽn một cách hiệu quả hơn.

2.1. Wireless Sensor Network WSN

WSN là tập hợp các cảm biến tự động phân bố để theo dõi các điều kiện vật lý hoặc môi trường. Các cảm biến này được kết nối với nhau qua mạng không dây, cho phép truyền tải dữ liệu về một nút trung tâm. Tắc nghẽn trong WSN có thể xảy ra do nhiều lý do như hư hỏng thiết bị hoặc quá tải thông tin. Việc xác định và kiểm tra trạng thái tắc nghẽn là rất quan trọng để duy trì hoạt động của mạng.

2.2. Coloured Petri Net CPN

Coloured Petri Net là một công cụ mạnh mẽ trong việc mô hình hóa các hệ thống phức tạp. CPN cho phép phân tích các thuộc tính của hệ thống thông qua việc sử dụng các token có màu sắc, điều này giúp mô hình hóa các trạng thái khác nhau của hệ thống. CPN cũng hỗ trợ việc định nghĩa các điều kiện cho phép (guards) và các biểu thức (expressions) để xử lý các token, từ đó cải thiện khả năng kiểm tra và phân tích hiệu suất của WSN.

III. Nghiên cứu liên quan

Nghiên cứu trước đây đã chỉ ra rằng việc sử dụng mô hình Petri Net để mô hình hóa WSN có thể giúp phát hiện tắc nghẽn hiệu quả. Tuy nhiên, nhiều nghiên cứu hiện tại vẫn chưa khai thác hết tiềm năng của Coloured Petri Net trong việc xử lý các yếu tố xác suất. Bằng cách kết hợp yếu tố xác suất vào mô hình CPN, nghiên cứu này sẽ mở ra hướng tiếp cận mới cho việc kiểm chứng tắc nghẽn trong WSN. Các nghiên cứu liên quan khác cũng đã chỉ ra rằng việc áp dụng CPN giúp cải thiện đáng kể khả năng mô hình hóa và phân tích các tình huống phức tạp trong mạng.

3.1. Xây dựng WSN bằng Petri Net

Mô hình hóa WSN bằng Petri Net cho phép phân tích các trạng thái của mạng và phát hiện tắc nghẽn. Tuy nhiên, việc sử dụng Petri Net thông thường có những hạn chế trong việc biểu diễn các đặc điểm phức tạp của WSN. Do đó, việc áp dụng Coloured Petri Net sẽ giúp khắc phục những vấn đề này và nâng cao khả năng mô hình hóa.

IV. Mô hình xác suất CPN cho WSN

Mô hình xác suất cho WSN biểu diễn bằng Coloured Petri Net sẽ cho phép xác định các trạng thái tắc nghẽn với xác suất cụ thể. Việc áp dụng yếu tố xác suất giúp mô hình hóa các tình huống thực tế trong mạng, nơi mà các yếu tố như năng lượng, vị trí cảm biến và điều kiện môi trường có thể ảnh hưởng đến hiệu suất của mạng. Phương pháp phát hiện tắc nghẽn sẽ được xây dựng dựa trên mô hình CPN, từ đó cung cấp một công cụ hữu ích cho việc phân tích và kiểm tra tắc nghẽn trong WSN.

4.1. Định nghĩa mô hình xác suất WSN

Mô hình xác suất cho WSN sẽ được thiết lập dựa trên các yếu tố như khả năng truyền dữ liệu, tần suất gửi gói tin và trạng thái của cảm biến. Các yếu tố này sẽ được đưa vào mô hình CPN để kiểm tra tính chất tắc nghẽn. Việc định nghĩa rõ ràng các yếu tố xác suất giúp tăng cường khả năng phân tích và dự đoán tình huống trong mạng.

V. Xây dựng công cụ WSN Tools

Công cụ WSN Tools được phát triển nhằm hỗ trợ việc mô hình hóa và kiểm tra tính chất tắc nghẽn trong WSN. Công cụ này sẽ cho phép người dùng dễ dàng định nghĩa các mô hình CPN và thực hiện kiểm tra tắc nghẽn một cách hiệu quả. Việc sử dụng công cụ này sẽ giúp tiết kiệm thời gian và công sức trong quá trình nghiên cứu và phát triển các giải pháp cho vấn đề tắc nghẽn trong WSN.

5.1. Kiến trúc tổng quan

Kiến trúc của công cụ WSN Tools bao gồm các thành phần chính như mô hình hóa, kiểm tra và phân tích. Mỗi thành phần sẽ đảm nhiệm một vai trò cụ thể trong việc hỗ trợ người dùng trong quá trình làm việc với mô hình CPN. Công cụ này cũng sẽ cung cấp các báo cáo và phân tích chi tiết về tình trạng tắc nghẽn trong mạng, giúp người dùng đưa ra các quyết định chính xác hơn.

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

Chương 1: Tổng quan Giới thiệu tổng quan về nội dụng, mục tiêu và phạm vi đề tài. Cuối cùng là cấu trúc luận văn. Chương 2: Kiến thức nền tảng Chương này trình bày các kiến thức cần thiết để hiểu và xây dựng mô hình, cụ thể là kiến thức về Petri Net, Coloured Petri Net, Wireless Sensor Network và tắc nghẽn trong mạng Wireless Sensor Network. Chương 3: Nghiên cứu liên quan Phần này nói về các công trình nghiên cứu trước đó, tạo tiền đề và ý tưởng cho việc thực hiện luận văn.

Ở đây có 2 nghiên cứu quan trọng là biểu diễn WSN bằng PN và biểu diễn WSN bằng CPN. Hai chương tiếp theo là nội dung chính của luận văn. Chương 4: Mô hình xác suất CPN cho WSN Phần này sẽ trình bày định nghĩa các yếu tố xác suất trong WSN và cách áp dụng các yếu tố này vào mô hình CPN của WSN. 6 Chương 5: Xây dựng công cụ WSN Tool Nội dung chương này trình bày công cụ hỗ trợ định nghĩa và kiểm tra cho mô hình ở Chương 4.

Chương 6: Thực nghiệm Trình bày việc thực nghiệm cho bài toán. Chương 7: Tổng kết Chương cuối cùng sẽ rút ra những nhận xét trong quá trình thực hiện đề tài, bao gồm những hạn chế và phương hướng phát triển trong tương lai. 7 Chương 2 Kiến thức nền tảng Phần này tóm tắt các kiến thức liên quan được tìm hiểu và sử dụng trong quá trình thực hiện luận văn.1 Wireless Sensor Network (WSN) Một WSN W được định nghĩa là một tập các cảm biến và kênh truyền W = {S,C}, với S là tập các cảm biến (sensors) và C là tập các kênh truyền (channels). Tuỳ thuộc vào chức năng mà các cảm biển được chia làm ba loại nguồn (source), đích (sink) và trung gian (intermediate).

Cảm biến nguồn có nhiệm vụ tạo và gửi gói tin. Các gói tin được nhận bởi các cảm biến trung gian và chuyển đi trong mạng cho tới khi gặp được cảm biến đích. Cảm biến đích nhận các gói tin và xử lý thông tin. Các cảm biến trong mạng có thể được kết nối theo chế độ unicast, multicast hoặc broadcast, tuỳ theo đó mà chỉ ra từng cặp cảm biến có thể trao đổi thông tin hay không.

Nếu hai cảm biến có thể giao tiếp, ta nói có một kênh truyền được hình thành giữa các cảm biến này.1 là ví dụ cho một WSN, trong đó cảm biến 1 và cảm biến 7 lần lượt đóng vai trò là nguồn và đích. Tắc nghẽn trong WSN nghĩa là trong quá trình truyền dữ liệu từ sensor nguồn, dữ liệu có thể bị ngừng ở một điểm nào đó và không tới được sensor đích. Vấn đề này xảy ra có thể do thiết bị bị hư hỏng, hết năng lượng, hoặc do sự 8 Hình 2.1: Ví dụ WSN bùng nổ số lượng gói tin trao đổi trong mạng là rất lớn và dẫn đến tắc nghẽn [4].2 Petri Net (PN) Petri Net là ngôn ngữ mô hình đồ hoạ được sử dụng rộng rãi trong việc mô hình hoá hệ thống mạng và giao thức. Định nghĩa 1 Một Petri net là một bộ N =< P, T, F,W, M0 >, trong đó: • P là tập hữu hạn các places, kí hiệu cho các trạng thái hoặc điều kiện đạt được trước khi một hành động được thực hiện.

• T là tập hữu hạn các transitions, biểu diễn cho các hành động (action). • Các tập P và T không giao nhau P ∩ T = 0. / • F ⊆ (P × T ) ∪ (T × P) biểu diễn quan hệ giữa các places và transitions. • W : F → N+ là trọng số của cạnh (arc weight).

• M0 : p → N là marking khởi tạo (initial marking), biểu diễn cho sự phân phối ban đầu của các tokens. 9 Định nghĩa 2 Cho Petri net N = {P, T, F,W, M0 } và M : P → N là một marking của N. Một transition t ∈ T được enabled tại marking M được viết dưới dạng công thức: t M→ − ⇐⇒ ∀p ∈ P : M(p) ≥ W (p,t) Một enabled transition có thể được fire, tạo ra marking M 0 : t − M 0 , ∀p ∈ P : M 0 (p) = M(p) −W (p,t) +W (t, p) M→ 2.3 Coloured Petri Net (CPN) Coloured Petri Nets [7] [8](CPN) là ngôn ngữ mô hình được ứng dụng rất nhiều trong việc mô hình các hệ thống đồng thời và phân tán, từ đó phân tích các tính chất của hệ thống. Ở đây mô hình CPN định nghĩa hành vi tấn công dựa trên chuỗi những sự kiện (events) được xác định liên quan tới sự tấn công.

Những sự kiện đó được biểu diễn bằng mô hình CPN dựa trên thời gian hay nguyên nhân xảy ra. Mô hình biểu diễn topology qua các trạm (workstations), servers, switches và đánh giá thời gian phản hồi của mạng (network response time). Các thông số về phần cứng (hardware) và phần mềm (software) cũng được đưa vào mô hình. Từ đó đưa ra các hướng nghiên cứu về đánh giá hiệu năng, điều kiện ổn định vững bền (steady-stable) cũng như tối ưu lựa chọn về phần cứng.

CPN là ngôn ngữ mô hình nâng cao hơn của PN, là sự kết hợp giữa sức 10 mạnh của PN và ngôn ngữ lập trình hàm. Khác với PN, các tokens trong CPN được phân biệt bằng các "colour" thay vì chỉ là các "chấm đen", nghĩa là tokens sẽ mang nhiều thông tin hơn. Ngoài ra, các cạnh trên CPN bao gồm các biểu thức (expression) mô tả xử lý biến đổi cụ thể các token này, thay vì chỉ chứa thông tin về trọng số trong mô hình PN thông thường. Các "guard" gắn trên các transitions bổ sung thêm các ràng buộc cần thiết để một transition có thể được cho phép thực thi.

Gọi EXP là tập các expression trong CPN. EXP được dùng để diễn tả một số thành phần của CPN như cạnh, hay các guards. Trước khi các expression tính toán giá trị, các biến trong các expression phải được gán giá trị, gọi là binding. Dưới đây là một số định nghĩa trong CPN [14].

Định nghĩa 3 Cho S = {s1 , s2 , .} là tập khác rỗng. Một multiset trên S là hàm số m : S → N, trong đó mỗi phần tử s ∈ S sẽ tương ứng với một số nguyên không âm m(s) ∈ N gọi là số lần xuất hiện của s trong m. Multiset m được viết dưới dạng công thức: + + ∑ m(s)0 s = m(s1)0 s1 + +m(s2)0 s2 + +. s∈S Với m1 , m2 và m là các multiset, các toán thử thuộc, cộng, so sánh, trừ lần lượt được định nghĩa như sau: • ∀s ∈ S : s ∈ m ⇐⇒ m(s) > 0 • ∀s ∈ S : (m1 + +m2 )(s) = m1 (s) + m2 (s) • m1 <<= m2 ⇐⇒ ∀s ∈ S : m1 (s) ≤ m2 (s) • Khi m1 <<= m2 , ∀s ∈ S : (m2 − −m1 )(s) == m2 (s) − m1 (s) Tập hợp tất cả các multiset trên S được kí hiệu là SMS.

Định nghĩa 4 Một Coloured Petri net là một bộ < P, T, F, ∑,V, c, g, f , m0 >, trong đó: 11 • P là tập hữu hạn khác rỗng các places. • T là tập hữu hạn khác rỗng các transitions sao cho P ∩ T = 0. / • F ⊆ PxT ∪ T xP là tập hữu hạn các cạnh có hướng. • ∑ là tập hữu hạn khác rỗng các coloured sets.

• V là tập hữu hạn các kiểu biến sao cho Type[v] ∈ ∑, ∀v ∈ V. • c : p → ∑ là một hàm colour set gán mỗi place p ∈ P với một colour set c(p) ∈ ∑. • g : T → EXP là một hàm guard gán mỗi transition t ∈ T một expression kiểu Boolean. • f : F → EXP là một hàm trên cạnh gán mỗi cạnh a ∈ F một expression của kiểu multiset c(p)MS , với p là place được nối tới cạnh a.

• m0 : P → EXP là hàm khởi tạo gán mỗi place p ∈ P một expression khởi tạo của kiểu multiset c(p)MS. Định nghĩa 5 Với một Coloured Petri Net CPN =< P, T, F, ∑,V, c, g, f , m0 >, ta có một số khái niệm: • Một marking là một hàm M sao cho mỗi place p ∈ P ứng với một multi- set các tokens thoả M(p) ∈ C(p)MS , với m0 là marking ban đầu (initial marking) của CPN. • Các biến của một transition t được kí hiệu Var(t) ∈ V và bao gồm các biến tự do xuất hiện trong hàm guard của t và expression arc của cạnh liên kết với t. • Một phần tử binding (binding element) là một cặp (t, b) thoả t ∈ T và b ∈ B(t).

Tập tất cả các binding element BE(t) cho một transition t được định nghĩa bởi BE(t) = {(t, b)|b ∈ B(t)}. Tập hợp tất cả các binding elements trong môt mô hình CPN được kí hiệu là BE. 12 • Một step Y ∈ BEMS là một multiset hữu hạn, khác rỗng các binding ele- ments. Định nghĩa 6 Một binding element (t, b) ∈ BE được enabled tại marking M nếu và chỉ nếu hai tính chất sau được thoả mãn: • G(t) < b >= true • ∀p ∈ P : E(p,t) < b ><<= M(p) Khi (t, b) được enabled tại M, nó có thể được xảy ra, dẫn đến marking M 0 được định nghĩa bởi: • ∀p ∈ P : M 0 (p) = (M(p) − −E(p,t) < b >) + +E(t, p) < b > (t,b) M 0 đạt được (reachable) trực tiếp từ M được kí hiệu bởi M −−→ M 0.

Tập các markings đạt được từ M được kí hiệu là R(M). Một mô hình CPN có thể được tổ chức dưới dạng tập các module phân cấp. Mô hình CPN với nhiều module còn được gọi là Coloured Petri Net phân cấp (Hierachical Coloured Petri Net - HCPN). Một HCPN cho phép chia một mod- ule thành nhiều module con nhỏ hơn (sub modules) liên kế với nhau qua các interfaces được định nghĩa.

Với mô hình HCPNs, người làm mô hình có thể làm việc với hiều mức trừu tượng và tập trung vào một số chi tiết một lúc, thay vì toàn bộ mô hình. Hơn thế nữa, một module được định nghĩa một lần và có thể được dùng lặp đi lặp lại. Việc này giúp cho việc đọc hiểu cũng như thay đổi một mô tả nào đó khi cần trở nên dễ dàng hơn. 13 Chương 3 Nghiên cứu liên quan Phần này trình bày một số công trình nghiên cứu liên quan đã tìm hiểu, tạo tiền đề cho việc thực hiện luận văn.1 Xây dựng WSN bằng Petri Net Trong phần tiếp theo sẽ trình bày quy trình mô hình hoá WSN bằng PN và quy trình kiểm tra Place/Transition Net.