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.