Bài giảng Mô hình hóa và mô phỏng mạng - Mô hình hóa số học (Phần 1) - Nguyễn Đức Tài

Nội dung text: Bài giảng Mô hình hóa và mô phỏng mạng - Mô hình hóa số học (Phần 1) - Nguyễn Đức Tài

1. TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN TPHCM MÔ HÌNH HÓA VÀ MÔ PHỎNG MẠNG Mô hình hóa số học (phần 1) – Các khái niệm cơ bản và mô hình Markov các hệ 1 thống hàng đợi TS. Nguyễn Đức Tài
2. TIẾN TRÌNH NGẪU NHIÊN ĐƯỢC SỬ DỤNG (ĐẾ TÍNH TOÁN) Ở ĐÂU? •Các tiến trình đi vào hoặc truyền dữ liệu trong mạng viễn thông • Tiến trình thực thi các bài toán ; • Trao đổi dữ liệu với thiết bị ngoài trong máy tính, 2
3. KHÁI NIỆM TIẾN TRÌNH NGẪU NHIÊN Khái niệm cơ bản nhất : trạng thái và bước chuyển tiếp từ trạng thái này sang trạng thái khác. Tiến trình ngẫu nhiên ở một trạng thái nào đó nếu nó hoàn toàn được mô tả bởi các giá trị các biến, xác định bởi trạng thái đó. Tiến trình thực hiện một bước chuyển tiếp từ trạng thái này sang trạng thái khác nếu các biến mô tả của nó thay đổi từ giá trị xác định trạng thái này sang giá trị, được xác định bởi các biến khác. Ngẫu nhiên: trạng thái này chuyển tiếp sang trạng thái khác không biết trước. Nếu tiến trình mà có tập hợp các trạng thái là đếm được gọi là tiến trình ngẫu nhiên có 3 trạng thái rời rạc (tiến trình ngẫu nhiên rời rạc).
4. KHÁI NIỆM TIẾN TRÌNH NGẪU NHIÊN Tiến trình ngẫu nhiên có trạng thái rời rạc (a) và liên tục (b) Ví dụ tiến trình ngẫu nhiên rời rạc trong hệ thống hàng đợi đơn giản nhất với luồng yêu cầu đồng nhất, có thể biểu diễn bởi số lượng các yêu cầu trong hệ thống ở bất kỳ một thời điểm nào. Nếu tập hợp các trạng thái không thể đánh số, thì đó là tiến trình ngẫu nhiên với trạng thái liên tục, hoặc gọi ngắn gọn hơn là tiến trình ngẫu nhiên liên tục, đặc trưng bởi sự chuyển tiếp mịn từ trạng thái này 4 sang trạng thái khác. Ví dụ: quá trình thay đổi nhiệt độ của một đối tượng
5. HÁI NIỆM TIẾN TRÌNH NGẪU NHIÊN . K  Khi mô tả các hệ thống rời rạc trong thuật ngữ của tiến trình ngẫu nhiên thì một trong những bước cơ bản là bước mã hóa các trạng thái, [nó] bao gồm việc xác định thành phần các biến và giá trị của nó, được sử dụng để mô tả các trạng thái.  Vì các mô hình hàng đợi là thuộc lớp các hệ thống rời rạc, nên trong tương lai chỉ xem xét đến các tiến trình ngẫu nhiên với trạng thái rời rạc. 5
6. CÁC TIẾN TRÌNH NGẪU NHIÊN VỚI TRẠNG THÁI RỜI RẠC Giả sử rằng, hệ thống có thể ở một trong các trạng thái E1,E2, (thường thì trạng thái được ký hiệu đơn giản bằng các con số 1,2, : E1,E2, : các trạng thái rời rạc). Trạng thái của hệ thống thay đổi đột ngột và phụ thuộc vào một tham số t nào đó, trong khi sự chuyển tiếp từ một trạng thái này sang trạng thái khác là ngẫu nhiên. Gọi Z(t) là tiến trình ngẫu nhiên, mô tả trạng thái hệ thống trong thời điểm thời gian t. Tiến trình ngẫu nhiên Z(t) gọi là tiến trình ngẫu nhiên với thời gian rời rạc, nếu sự chuyển tiếp từ một trạng thái sang một trạng thái chỉ có thể 6 trong những thời điểm xác định cho trước, được đánh số:
7. CÁC TIẾN TRÌNH NGẪU NHIÊN VỚI TRẠNG THÁI RỜI RẠC Nếu khoảng thời gian giữa các chuyển tiếp từ trạng thái này sang trạng thái kia là ngẫu nhiên, và sự chuyển tiếp có thể trong bất cứ thời gian chưa biết trước, thì tiến trình đó gọi là tiến trình ngẫu nhiên với thời gian liên tục. Tiến trình với thời gian rời rạc  Mỗi trạng thái của nó có thể thay đổi chỉ trong những thời điểm (moment) xác định (biết trước).  Để mô tả tiến trình thì biết được trạng thái của hệ thống trong những thời điểm riêng lẻ (như nói: trạng thái Ei trong thời điểm tk hoặc là đơn giản là trong thời điểm k). Tiến trình ngẫu nhiên với trạng thái rời rạc được thể hiện dưới dạng đồ thị chuyển tiếp (các trạng thái) 7
8. CÁC TIẾN TRÌNH NGẪU NHIÊN VỚI TRẠNG THÁI RỜI RẠC Đồ thị chuyển tiếp trong slide vừa rồi gọi là có nhãn (khi trên các cung của đồ thị chỉ ra điều kiện chuyển tiếp ở dạng xác suất chuyển tiếp (đối với các tiến trình với thời gian rời rạc) hoặc bằng cường độ chuyển tiếp (đối với tiến trình với thời gian liên tục)). Trạng thái có thể là:  Không thể quay về, nếu tiến trình sau một số lượng bước chuyển tiếp thì chắc chắn bỏ nó (trạng thái đó);  Hấp thụ, nếu tiến trình ngẫu nhiên đi đến trạng thái này thì bị dừng lại. 8
9. TIẾN TRÌNH NGẪU NHIÊN MARKOV Tiến trình ngẫu nhiên gọi là tiến trình Markov nếu:  Xác suất của bất kỳ trạng thái nào trong tương lai chỉ phụ thuộc vào trạng thái hiện tại;  Xác suất đó cũng không phụ thuộc vào việc rằng, khi nào và bằng cách nào tiến trình đó rơi vào trạng thái đó. Tiến trình Z(t) mô tả hành vi (cách chạy, behaviour) của hệ thống gọi là chuỗi Markov. Để mà một tiến trình ngẫu nhiên với thời gian liên tục là tiến trình Markov thì điều cần thiết là các khoảng thời gian giữa các bước chuyển tiếp cận kề nhau từ một trạng thái sang một trạng thái phân bố theo luật mũ (*). 9
10. TÍNH CHẤT ĐẶC BIỆT CỦA PHÂN BỐ MŨ Tính chất không [gây] hậu quả là một biến ngẫu nhiên, phân bố theo luật mũ → cũng phân bố với cùng một phân bố mũ với cùng một tham số α. không phụ thuộc vào lịch sử trước đó, nghĩa là không phụ thuộc vào, đã bao nhiêu thời gian đã đi qua đến thời điểm . 10
11. CHỨNG MINH (*) Cho biết thời gian mà một tiến trình ngẫu nhiên ở một trạng thái Ei nào đó trước khi chuyển tiếp sang trạng thái Ej phân bố theo luật mũ với hàm phân bố , trong đó - tham số của phân bố, đặc trưng cho tần số chuyển tiếp từ trạng thái Ei sang Ej, được xác định như là giá trị nghịch đảo với thời gian trung bình mà tiến trình ngẫu nhiên ở trong trạng thái Ei trước khi chuyển sang trạng thái Ej. Xác suất mà tiến trình ngẫu nhiên chuyển sang trạng thái Ej trong suốt khoảng thời gian trong điều kiện là, tiến trình trong trạng thái Ei đã ở trong suốt khoảng thời gian . Xác suất chuyển tiếp từ một trạng thái sang trạng thái khác chỉ phụ thuộc vào trạng thái ban đầu Ei và không phụ thuộc vào khoảng thời gian , nghĩa là không phụ thuộc vào tiến trình đã ở bao lâu trong trạng thái Ei và những trạng thái nào 11 đi trước trạng thái Ei.
12. THAM SỐ TIẾN TRÌNH NGẪU NHIÊN MARKOV  Danh sách các trạng thái mà tiến trình có thể ở trong các trạng thái này (→ giải bài toán mã hóa các trạng thái) ; Ví dụ: trạng thái của một hệ thống hàng đợi có thể được cho bởi số lượng các yêu cầu nằm trong hệ thống trong thời điểm được cho, còn trạng thái của mạng hàng đợi được cho bởi sự phân bố các yêu cầu trên các nút trong mạng  Ma trận chuyển tiếp, mô tả các chuyển tiếp của tiến trình ngẫu nhiên giữa các trạng thái ở dạng: Ma trận xác suất chuyển tiếp Q cho các tiến trình với thời gian rời rạc; Ma trận cường độ chuyển tiếp G cho các tiến trình với thời gian liên tục; 12  Các xác suất ban đầu
13. CHUỖI MARKOV (MARKOV CHAIN) Ký hiệu là xác suất điều kiện rằng, vào thời điểm tiến trình ngẫu nhiên chuyển sang trạng thái Ej với điều kiện trước đó tiến trình vào thời điểm là ở trạng thái Ei. Nếu chuyển tiếp từ trạng thái Ei sang Ej chỉ phụ thuộc vào 2 trạng thái này thì xác suất điều kiện không thay đổi lúc đó chúng ta nhận được chuỗi Markov (Markov chain). Chuỗi Markov gọi là đồng nhất, nếu các xác suất chuyển tiếp không phụ thuộc vào thời điểm , và là không đồng nhất nếu các xác suất chuyển tiếp là các hàm của nghĩa là . 13
14. ĐẶC TÍNH TIẾN TRÌNH NGẪU NHIÊN MARKOV Nghiên cứu các tiến trình ngẫu nhiên bao gồm việc xác định xác suất rằng, trong thời điểm t hệ thống ở một trạng thái này hay trạng thái khác. Tập hợp những xác suất như vậy, mà mô tả trạng thái hệ thống ở những thời điểm khác nhau, cho ra được thông tin khá đầy đủ về tiến trình ngẫu nhiên chạy trong hệ thống. Xét hệ thống với số lượng trạng thái hữu hạn E1,E2, ,EN. Ký hiệu là xác suất mà trong thời điểm t hệ thống ở trạng thái Vector trạng thái là đặc tính cơ bản của tiến trình ngẫu nhiên 14 Điều kiện chuẩn mực hóa.
15. TÍNH CHẤT ERGODIC CỦA TIẾN TRÌNH NGẪU NHIÊN Nếu trong suốt khoảng thời gian đủ lớn các xác suất trạng thái tiến đến các giá trị p1,p2, ,pn , không phụ thuộc vào những xác suất ban đầu p1(0),p2(0), ,pn(0), và thời điểm hiện tại, thì có thể nói rằng, tiến trình ngẫu nhiên sở hữu tính chất Ergodic. Tiến trình sở hữu tính chất này: Trong đó – vector xác suất trạng thái của hệ thống, được gọi là xác suất ổn định. Trong hệ thống mà được mô tả bởi tiến trình ngẫu nhiên Markov, sở hữu tính chất Ergodic, khi thì thiết lập một chế độ giới hạn nào đó, trong đó các đặc tính hoạt động của hệ thống không phụ thuộc vào thời gian. →Hệ thống làm việc trong chế độ được thiết lập hoặc chế độ ổn định. Nếu các đặc tính hoạt động của hệ thống phụ thuộc vào thời gian, thì gọi là chế độ 15 [ổn định] không được thiết lập.
16. TIẾN TRÌNH MARKOV VỚI THỜI GIAN RỜI RẠC Các xác suất trạng thái ở thời điểm được xác định trên cơ sở các biểu thức hồi quy (có tính định kỳ): Nếu tiến trình Markov đang xét sở hữu tính chất Ergodic, khi các xác suất trạng thái tiến đến các giá trị ổn định , không phụ thuộc thời điểm và các xác suất ban đầu → hệ phương trình đại số tuyến tính để tính các 16 xác suất trạng thái ổn định của tiến trình Markov.
17. V. Í DỤ TIẾN TRÌNH MARKOV VỚI THỜI GIAN RỜI RẠC Xét hệ thống bao gồm 2 thiết bị Y1 và Y2, mỗi một thiết bị có thể ở một trong 2 trạng thái: 0 – tắt và 1 – mở. Trong các thời điểm xác định các thiết bị có thể tắt hoặc mở. Các trạng thái có thể của hệ thống: Xác suất chuyển tiếp: 17 Các xác suất ban đầu:
18. VÍ DỤ TIẾN TRÌNH MARKOV VỚI THỜI GIAN RỜI RẠC Ở thời điểm t1: Tương tự như vậy có thể tính cho các thời điểm t2,t3,t4 Hệ phương trình đại số tuyến tính Kết quả: Như vậy hệ thống nghỉ khoảng 23.6% thời gian, và hơn 76% hệ thống ở trạng thái làm việc, trong đó gần 30% là 2 thiết đều mở. Số trung bình các thiết bị ở trạng thái 18 mở sẽ bằng: , nghĩa là số trung bình các thiết bị trong tạng thái mở là bằng 1 thiết bị.
19. TIẾN TRÌNH MARKOV VỚI THỜI GIAN LIÊN TỤC Với tiến trình Markov đồng nhất với thời gian liên tục, các xác suất trạng thái ở bất cứ thời điểm t nào được xác định từ hệ phương trình vi phân: Với điều kiện ban đầu: Với hệ thống sở hữu tính chất Ergodic với chế độ ổn định, các xác suất trạng thái , khi không phụ thuộc vào các xác suất ban đầu và thời điểm hiện tại t, và hệ phương trình vi phân với chế độ ổn định được biến đổi thành hệ phương trình đại số tuyến tính: 19
20. VÍ DỤ TIẾN TRÌNH MARKOV VỚI THỜI GIAN LIÊN TỤC Mô hình “sinh tử” Ma trận chuyển tiếp 20
21. VÍ DỤ TIẾN TRÌNH MARKOV VỚI THỜI GIAN LIÊN TỤC Hệ phương trình đại số tuyến tính  Nguyên tắc 1 (theo đồ thị chuyển tiếp).  Nguyên tắc 2 ( theo ma trận các cường độ chuyển tiếp).  Giải hệ phương trình bằng phương pháp phân tích hoặc bằng phương pháp số học, có thể xác định được 21 các giá trị các xác suất ổn định của trạng thái của tiến trình Markov
22. MÔ HÌNH MARKOV CÁC HỆ THỐNG HÀNG ĐỢI Hệ thống hàng đợi một kênh không có lưu trữ (M/M/1/0)  Mô tả hệ thống  Các giả định  Mã hóa các trạng thái của tiến trình ngẫu nhiên E0 - k=0 – trong hệ thống không có yêu cầu nào (thiết bị nghỉ); E1 - k=1 – trong hệ thống có 1 yêu cầu (thiết bị hoạt động).  Đồ thị các chuyển tiếp có nhãn cho tiến trình ngẫu nhiên 22
23. MÔ HÌNH MARKOV CÁC HỆ THỐNG HÀNG ĐỢI Biểu đồ cho hoạt động của hệ thống Những khoảng thời gian τ1,τ2, τ 4, τ 6, τ 8 phân bố theo luật mũ và như vậy thỏa mãn điều kiện ở trên. τ 3, τ 5, τ7 .? Theo tính chất của phân bố mũ, những khoảng này cùng phân bố theo dạng mũ. Tương ứng với tính chất này thì những khoảng thời gian τ 3, τ 5, τ7 có phân bố mũ với tham số λ, 23 và vì vậy cũng thỏa mãn điều kiện ở trên đối với tiến trình Markov.
24. MÔ HÌNH MARKOV CÁC HỆ THỐNG HÀNG ĐỢI Ma trận cường độ chuyển tiếp Hệ phương trình Kết quả: Tính các đặc tính của HTHĐ  Tải ngoài, tải trong,  Hệ số nghỉ  Số yêu cầu trung bình  Xác suất mất mát yêu cầu  Hiệu suất của hệ thống  24 Phân tích tính chất của hệ thống
25. MÔ HÌNH MARKOV CÁC HỆ THỐNG HÀNG ĐỢI Hệ thống hàng đợi một kênh có lưu trữ vô hạn (M/M/1) Mã hóa trạng thái tiến trình ngẫu nhiên  E0: k=0 – trong hệ thống không có yêu cầu;  E1: k=1 – trong hệ thống có 1 yêu cầu được phục vụ trong thiết bị;  E2: k=2 – trong hệ thống có 2 yêu cầu: 1 là ở thiết bị phục vụ, một là ở thiết bị lưu trữ;  Ek: k – trong hệ thống có k yêu cầu: 1 là ở thiết bị phục vụ, (k-1) yêu cầu là ở thiết bị lưu trữ;; 25
26. MÔ HÌNH MARKOV CÁC HỆ THỐNG HÀNG ĐỢI Hệ phương trình Kết quả: Tính các đặc tính của HTHĐ Tải ngoài: - theo định nghĩa; Tải trong: ; Hệ số nghỉ của hệ thống:; Số yêu cầu trung bình trong hàng đợi: Số yêu cầu trung bình trong hệ thống: Xác suất mất mát của yêu cầu: Hiệu suất của hệ thống khi không có việc mất mát trùng với cường độ các yêu cầu đi vào hệ thống: Cường độ luồng yêu cầu không được phục vụ: 26 Thời gian đợi trung bình trong hàng đợi: ; Thời gian ở trung bình trong hệ thống: .
27. NEXT LECTURE: KIỂM TRA ? Pr=90% 27