Tài liệu Ứng dụng lý thuyết xếp hàng trong mạng máy tính

  • Số trang: 92 |
  • Loại file: PDF |
  • Lượt xem: 198 |
  • Lượt tải: 0
nguyetha

Đã đăng 8490 tài liệu

Mô tả:

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN ------------------- LÊ ĐỨC HỢP ỨNG DỤNG LÝ THUYẾT XẾP HÀNG TRONG MẠNG MÁY TÍNH LUẬN VĂN THẠC SĨ KHOA HỌC Hà Nội – Năm 2014 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN ------------------- LÊ ĐỨC HỢP ỨNG DỤNG LÝ THUYẾT XẾP HÀNG TRONG MẠNG MÁY TÍNH Chuyên ngành: Lý thuyết xác suất và thống kê toán học Mã số: 60.460.106 LUẬN VĂN THẠC SĨ KHOA HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC: NCVCC.TS.NGUYỄN HỒNG HẢI Hà Nội – Năm 2014 MỤC LỤC MỞ ĐẦU.................................................................................................................... 1 CHƯƠNG I: GIỚI THIỆU KIẾN THỨC CHUẨN BỊ ................................................. 3 1.1. Những khái niệm cơ bản của lý thuyết xác suất ........................................... 3 1.1.1. Biến ngẫu nhiên ...................................................................................... 3 1.1.2. Những phân phối quan trọng ................................................................... 3 1.1.2.1. Phân phối hình học ............................................................................. 3 1.1.2.2. Phân phối Poisson............................................................................... 3 1.1.2.3. Phân phối mũ ...................................................................................... 3 1.1.2.4. Phân phối Erlang ................................................................................ 4 1.1.2.5. Phân phối siêu mũ (Hyperexponential) ............................................... 4 1.1.2.6. Phân phối dạng Phase ......................................................................... 5 1.1.3. Sơ lược về các quá trình ngẫu nhiên ........................................................ 5 1.1.3.1. Định nghĩa quá trình ngẫu nhiên ......................................................... 5 1.1.3.2. Quá trình Markov ............................................................................... 6 1.1.3.3. Quá trình Poisson ............................................................................... 6 1.2. Quá trình sinh tử ............................................................................................... 8 CHƯƠNG II: TỔNG QUAN VỀ LÝ THUYẾT XẾP HÀNG .................................... 12 2.1 Những mô hình xếp hàng và một số khái niệm cơ bản................................... 12 2.1.1. Mô hình xếp hàng và ký hiệu Kendall ................................................... 12 2.1.2. Tỷ lệ thời gian cư ngụ ........................................................................... 13 2.1.3. Một số đại lượng đặc trưng ................................................................... 14 2.1.4. Định luật Little...................................................................................... 15 2.1.5. Tính chất PASTA ................................................................................. 15 2.2. Mô hình xếp hàng M/M/1 ......................................................................... 15 2.2.1. Cân bằng xác suất ................................................................................. 16 2.2.2. Các đặc trưng trung bình ....................................................................... 16 2.2.3. Phân phối của thời gian lưu trú và thời gian chờ đợi ............................. 17 2.2.4. Các tính chất ......................................................................................... 18 2.2.5. Quyền ưu tiên tuyết đối ......................................................................... 19 2.2.6. Quyền ưu tiên không tuyệt đối .............................................................. 19 2.2.7. Chu kỳ bận............................................................................................ 20 2.2.8. Trung bình chu kỳ bận .......................................................................... 20 2.2.9. Phân phối của chu kỳ bận...................................................................... 21 2.3. Mô hình xếp hàng M/M/c.......................................................................... 22 2.3.1. Cân bằng xác suất ................................................................................. 22 2.3.2. Trung bình độ dài hàng đợi và trung bình thời gian chờ đợi .................. 23 2.3.3. Phân phối thời gian chờ đợi và thời gian lưu trú .................................... 24 2.4. Mô hình xếp hàng M/Er/1.......................................................................... 25 2.4.1. Hai cách mô tả trạng thái ...................................................................... 25 2.4.2. Cân bằng phân phối .............................................................................. 25 2.4.3. Trung bình thời gian đợi ....................................................................... 28 2.4.4. Phân phối thời gian đợi ......................................................................... 29 2.5. Mô hình xếp hàng M/G/1 .......................................................................... 29 2.5.1. Những phân phối giới hạn ..................................................................... 29 2.5.2. Phân phối của sự rời đi.......................................................................... 31 2.5.3. Phân phối của thời gian lưu trú ............................................................. 35 2.5.4. Phân phối của thời gian chờ đợi ............................................................ 37 2.5.5. Phương pháp giá trị trung bình .............................................................. 38 2.5.6. Thời gian phục vụ còn lại...................................................................... 39 2.5.7. Phương sai của thời gian chờ đợi .......................................................... 40 2.5.8. Phân phối của chu kỳ bận...................................................................... 41 2.6. Mô hình xếp hàng G/M/1 .......................................................................... 43 2.6.1. Phân phối khách đến ............................................................................. 44 2.6.2. Phân phối của thời gian lưu trú ............................................................. 47 2.6.3. Thời gian lưu trú trung bình .................................................................. 47 CHƯƠNG III: MẠNG JACKSON ............................................................................ 49 3.1. Mạng mở .................................................................................................. 49 3.2. Mạng đóng ................................................................................................ 53 3.3. Mạng nửa mở ............................................................................................ 55 3.4. Hàm thông lượng ...................................................................................... 58 3.5. Tính thông lượng ...................................................................................... 60 3.5.1. Thuật toán tích chập .............................................................................. 61 3.5.2. Phân tích giá trị trung bình .................................................................... 61 3.6. Sự đảo ngược thời gian ............................................................................. 63 CHƯƠNG IV: MẠNG KELLY ................................................................................. 68 4.1. Mô hình xếp hàng tựa khả nghịch ............................................................. 68 4.2. Mô hình xếp hàng đối xứng ...................................................................... 73 4.2.1. Các phân phố và quá trình dạng Phase .................................................. 73 4.2.2. Mô hình M/PH/l.................................................................................... 75 4.3. Mạng đa lớp .............................................................................................. 79 4.4. Dòng Poisson ............................................................................................ 84 KẾT LUẬN ............................................................................................................... 86 TÀI LIỆU THAM KHẢO ......................................................................................... 87 Luận Văn Thạc Sĩ Khoa Học MỞ ĐẦU Lý thuyết phục vụ đám đông ra đời từ những năm 50 của thế kỷ XX và có rất nhiều ứng dụng trong khoa học cũng như trong thực tế. Lý thuyết xếp hàng được xem như là một nhánh chính của lý thuyết xác xuất ứng dụng. Những lĩnh vực quan trọng ứng dụng của mô hình xếp hàng là mạng viễn thông, mạng máy tính, hệ thống xử lý thông tin. Luận văn với đề tài “ Ứng dụng lý thuyết xếp hàng trong mạng máy tính ” nghiên cứu các mô hình cơ bản của lý thuyết xếp hàng, tính chất của các mô hình xếp hàng. Ứng dụng của lý thuyết xếp hàng vào nghiên cứu các mô hình mạng. Nội dung luận văn gồm bốn chương: Chương 1: Giới thiệu các kiến thức chuẩn bị Trong chương này chúng tôi trình bày về một số phân bố xác suất quan trọng và một số quá trình ngẫy nhiên bao gồm quá trình Poisson, quá trình Markov và đặc biệt là quá trình sinh tử. Chương 2: Tổng quan về lý thuyết xếp hàng Chương này chúng tôi trình bày về các mô hình xếp hàng cơ bản như mô hình M / M / 1, M / M / c , M / E r / ... Chương 3: Mạng Jackson Trong chương này chúng tôi đi sâu vào trình bày mô hình mạng Jackson gồm: mạng Jackson đóng, mạng Jackson mở, mạng Jackson nửa mở và mạng thời gian đảo ngược có cùng phân phối cân bằng và dòng khách hàng đến và rời đi cùng tuân theo quá trình Poisson độc lập. Chương 4: Mạng Kelly Mạng Kelly là mở rộng của mạng Jackson tuy nhiên vẫn giữ lại các giả thiết và các tính chất cơ bản của mạng Jackson. Với sự cố gắng hết mình của bản thân, cùng với sự động viên giúp đỡ, hướng dẫn tận tình của các thầy giáo, bản luận văn đã được hoàn thành. Song do thời gian có hạn cũng như năng lực bản thân còn hạn chế nên chắc chắn luận văn không tránh khỏi 1 Luận Văn Thạc Sĩ Khoa Học những thiếu sót, tôi rất mong nhận được thêm những ý kiến đóng góp cho luận văn này của các thầy cô và các độc giả. Với lòng biết ơn sâu sắc, tôi xin chân thành cảm ơn tới các thầy cô Khoa toán tin – Trường ĐHKHTN Hà Nội đã tận tình giúp đỡ tôi trong suốt quá trình học tập. Đặc biệt tôi muốn tỏ lòng biết ơn sâu sắc tới NCVCC, TS Nguyễn Hồng Hải cán bộ thuộc trung tâm KHKT – BQP, người đã tận tình hướng dẫn về khoa học và giúp đỡ tôi trong suốt quá trình thực hiện luận văn này. Tôi xin chân thành cảm ơn! Hà Nội, Năm 2014 Tác giả Lê Đức Hợp 2 Luận Văn Thạc Sĩ Khoa Học CHƯƠNG I: GIỚI THIỆU KIẾN THỨC CHUẨN BỊ 1.1. Những khái niệm cơ bản của lý thuyết xác suất 1.1.1. Biến ngẫu nhiên Giả sử (  ,ℱ,P) là không gian xác xuất Định nghĩa: Biến ngẫu nhiên X là ánh xạ đo được X: (Ω, ℱ) → ℝ Các đại lượng quan trọng của biến ngẫu nhiên X: kỳ vọng ( trung bình ) EX, phương sai  2  X  , độ lệch chuẩn   X  và hệ số biến thiên cX  X ( hệ số biến E X thiên cX là một thước đo độ biến động của biến ngẫu nhiên X ) 1.1.2. Những phân phối quan trọng 1.1.2.1. Phân phối hình học Biến ngẫu nhiên X có phân phối hình học với tham số p nếu các giá trị của nó là các số nguyên không âm và với mọi k    ta có: P  X  k   1  p  p k . Với phân phối hình học ta có: EX  p p 1 ;  2 (X)  ;C2x  2 1 p (1  p) p 1.1.2.2. Phân phối Poisson Biến ngẫu nhiên X được gọi là có phân phối Poisson với tham số μ nếu các giá trị của nó là các số nguyên không âm và với mọi k    ta có: P(X  k)   k e  k! Với phân phối Poisson ta có: E(X)   2 (X)  ;C2x  1 1.1.2.3. Phân phối mũ Biến ngẫu nhiên liên tục X được gọi là có phân phối mũ với tham số μ nếu hàm mật độ của nó có dạng: e t f t   0 Hàm phân phối: 1  et F t    0 3 t0 t0 t0 t0 Luận Văn Thạc Sĩ Khoa Học Với phân phối mũ ta có: E  X   1 2 1 ;  (X)  2 ;C2x  1   Một tính chất quan trọng của biến ngẫu nhiên có phân phối mũ với tham số μ là: Với x  0 và t  0 P(X  x  t / X  t)  P(X  x)  e t P(X  t  t / X  t)  1  et  t  o(t),(t  0) Trong đó (1.1) o(t)  0 khi t  0 t 1.1.2.4. Phân phối Erlang Biến ngẫu nhiên X có phân phối Erlang - k (k = 1,2,…) với trung bình k nếu  X  X1  X 2  ...  X k . Trong đó: X1 ,X 2 ,..., X k là k biến ngẫu nhiên độc lập cùng phân phối mũ với trung bình Hàm mật độ của E k 1 . Ký hiệu là E k () hoặc E k .  k 1 Hàm phân phối: F(t)  1  k 1 e t (k  1)!  t  được cho bởi f (t)    j e t j!  t  j0 (t  0) . (t  0) Tham số μ được gọi là tham số tỷ lệ, k được gọi là kích thước mẫu. Với biến ngẫu nhiên có phân phối E k ta có: E(X)  k 2 k 1 ;  (X)  2 ;C2x     1.1.2.5. Phân phối siêu mũ (Hyperexponential) Cho Xi là biến ngẫu nhiên có phân phối mũ với trung bình: 1 i Biến ngẫu nhiên X gọi là có phân phối siêu mũ nếu: X = Xi với xác suất pi Ký hiệu: H(p1,…,pk;μ1,...,μk) hoặc Hk k Hàm mật độ của X: f (t)  p  e i i t i i 1 4 (t  0) Luận Văn Thạc Sĩ Khoa Học k Kỳ vọng: EX  pi  i 1 i 1.1.2.6. Phân phối dạng Phase Phân phối dạng phase được đặc trưng bởi xích Markov với không gian trạng thái 1, 2,..., k và ma trận xác suất chuyển P sao cho lim P n  0 ; thời gian lưu trú n  trong trạng thái i có phân phối mũ với trung bình 1 và xích Markov chuyển tại trạng i thái i với xác suất pi . Biến ngẫu nhiên X có phân phối dạng Phase nếu là tổng thời gian lưu trú trong xích Markov. Phân phối phase được ký hiệu là: PH. Chúng ta đề cập đến 2 phân phối dạng Phase quan trọng trù mật trong tất cả các hàm phân phối không âm. Điều này có nghĩa rằng với bất kỳ hàm phân phối không âm F(.) tìm thấy một dãy các hàm phân phối dạng Phase hội tụ điểm tại những điểm liên tục của F(.). Lớp thứ nhất là lớp phân phối Coxian. Ký hiệu: Ck . Lớp thứ là lớp bao gồm hỗn hợp các phân phối Erlang có cùng tham số tỷ lệ. Một biến ngẫu nhiên X có phân phối Coxian bậc k nếu nó phải trải qua k giai đoạn phân phối mũ. Độ dài trung bình của giai đoạn n là: 1 n n  1, 2,..., k . Nó được bắt đầu ở bước 1. Sau bước n nó kết thúc với xác suất 1  p n và đi vào bước tiếp theo với xác suất p n . Hiển nhiên p k  0 . Một biến ngẫu nhiên X có phân phối hỗn hợp Erlang bậc k nếu xác suất p n là tổng của n biến ngẫu nhiên có phân phối mũ với cùng trung bình. 1.1.3. Sơ lược về các quá trình ngẫu nhiên 1.1.3.1. Định nghĩa quá trình ngẫu nhiên Định nghĩa: Với mỗi T    ánh xạ X  t,  :  0;T      được gọi là một quá trình ngẫu nhiên nếu với mỗi t cố định X  t,  là một hàm đo được (để đơn giản ta viết X  t  thay cho X  t, ). 5 Luận Văn Thạc Sĩ Khoa Học Các quá trình ngẫu nhiên thường gặp: quá trình dừng, quá trình Markov, quá trình Poisson, quá trình sinh tử, quá trình nửa Markov. 1.1.3.2. Quá trình Markov   Với quá trình ngẫu nhiên X  X  t  , t  T chúng ta sử dụng các kí hiệu: X  X  t  , t  T  X t , t  T ℱ≤t = σ(Xu, u ≤ t), ℱt = σ(Xu, u > t) ℱ=t = σ(Xu, u = t)   Định nghĩa: Quá trình X t ,t  T; T   được gọi là quá trình Markov nếu với t  T và bất kì biến cố thì hầu chắc chắn P(B/ ℱ≤t ) = P(B/ ℱ=t) Từ định nghĩa suy ra các mệnh đề tương đương sau:   Quá trình X t ,t  T; T   được gọi là quá trình Markov khi và chỉ khi: i) A∈ ℱ≥t, P(A/ ℱ≤t) = P(A/ ℱ=t) ii) Với A∈ ℱt thì P(AB/ ℱ=t) = P(A/ ℱ=t)P(B/ ℱ=t). Ta ký hiệu E tập gồm các giá trị của X(t); E được gọi là không gian trạng thái của X(t). Định nghĩa: Quá trình X t , t  T được gọi là xích Markov nếu X t , t  T là quá trình Markov và E có lực lượng hữu hạn hoặc vô hạn đếm được. 1.1.3.3. Quá trình Poisson Trước khi tìm hiểu quá trình Poisson, chúng ta cần xem xét quá trình đếm thông qua trường hợp cụ thể sau: Giả sử A là biến cố nào đó. Ký hiệu N(t), t ≥0 là số lần biến cố A xuất hiện trong khoảng thời gian từ 0 đến t (kể cả thời điểm t). Khi đó  N(t), t  0 được gọi là quá trình đếm. Nếu N(t) là quá trình đếm thì N(t) là biến ngẫu nhiên có các tính chất sau: 1- N(t)  0 , N(0)  0 2- N(t) là số nguyên không âm 6 Luận Văn Thạc Sĩ Khoa Học 3- N(s)  N(t) 0  s  t 4- N(s;t]  N(t)  N(s) , 0  s  t là số lần biến cố A xuất hiện trong khoảng thời gian (s;t]. N(s;t],0  s  t được gọi là quá trình điểm (ứng với quá trình đếm N(t), t  0 ). Quá trình Poisson là quá trình đếm  N(t), t  0 nếu thỏa mãn các giả thiết sau: 1- Có gia số độc lập, tức là m  2;3;... và 0  t 0  t1  t 2  ...  t m các số gia N(t 0 , t1 ],N(t1 , t 2 ],...,N(t m 1 , t m ] là các biến ngẫu nhiên độc lập. 2- Các gia số dừng, tức là s  0 , 0  t1  t 2 các gia số N(t1  s, t 2  s], N(t1, t 2 ] là các biến ngẫu nhiên có cùng phân phối xác xuất. 3- Tồn tại số λ>0 sao cho với h>0 khá bé thì: P(N(h)  l)  h  o(h) Trong đó o(h) là vô cùng bé bậc cao hơn h khi h  0 4- Với h > 0 khá bé thì P(N(h)  2)  o(h) . Từ các giả thiết này chúng ta thấy N(t) có phân phối Poisson với tham số λt: p n (t)  P(N(t)  n)  (t) n t e n! n=0;1;2;… Định nghĩa: (Quá trình Poisson) ta nói rằng X(t), t  0 là quá trình Poisson với cường độ λ (tham số λ) nếu: a- X(t) nhận các giá trị 0;1;2;… b- X(t), t  0 là quá trình có gia số độc lập, tức là 0  t1  t 2  ...  t n các gia số X(t1 )  X(t 0 ), X(t 2 )  X(t1 ),X(t 3 )  X(t 2 ),...,X(t n )  X(t n 1 ) là các biến ngẫu nhiên độc lập. c- Mỗi gia số X(s  t)  X(t) có phân phối Poisson với tham số λs với mọi s  0, t  0 . d- X(0)=0. 7 Luận Văn Thạc Sĩ Khoa Học Định nghĩa: (quá trình điểm Poisson) ta nói rằng N(s;t],0  s  t là quá trình điểm Poisson với cường độ (tham số) λ > 0 nếu thỏa mãn: a- Với mọi m = 2;3;… với mọi 0  t 0  t1  t 2  ...  t m các biến ngẫu nhiên N(t 0 , t1 ],N(t1 , t 2 ],...,N(t m 1 , t m ] là độc lập. b- Với bất kỳ 0  s  t thì N(s, t] là biến ngẫu nhiên có phân phối Poisson với tham số λ(t-s). Quá trình Poisson đóng vai trò quan trọng trong nghiên cứu lý thuyết phục vụ đám đông. 1.2. Quá trình sinh tử Một lớp quan trọng của quá trình Markov là quá trình sinh – tử với đặc điểm ma trận xác suất chuyển Q = [qij] có tính chất qij= 0 với |i-j|  2 (điều này có nghĩa là việc chuyển trạng thái chỉ xảy ra giữa các trạng thái kề nhau). Từ trạng thái Ek chỉ được phép chuyển tới trạng thái Ek-1, Ek+1 hoặc giữ nguyên trạng thái Ek. Chúng ta chọn tập số nguyên làm không gian trạng thái rời rạc (điều này không làm mất tính tổng quát) và quá trình sinh - tử phải thỏa mãn điều kiện: nếu Xn = i thì Xn+1 = i-1 hoặc i + 1. Quá trình sinh – tử với thời gian rời rạc ít được quan tâm hơn trường hợp thời gian liên tục và do đó không được xem xét ở đây. Quan tâm chính của chúng ta là các quá trình sinh tử với thời gian liên tục trong không gian trạng thái rời rạc. Quá trình sinh – tử phù hợp với mô phỏng sự thay đổi số khách hàng trong hệ phục vụ. Khi quá trình ở trạng thái Ek có nghĩa số khách hàng trong hệ phục vụ tại thời điểm đó là k. Chuyển từ trạng thái Ek tới Ek+1 biểu thị cho sự kiện “sinh” (có một khách hàng tới hệ phục vụ), chuyển từ trạng thái Ek tới trạng thái Ek-1 biểu thị cho sự kiện “tử” (một khách hàng được phục vụ rời khỏi hệ). Tức là, từ trạng thái Ek, hệ phục vụ chỉ có thể chuyển tới một trong các trạng thái Ek-1, Ek+1 hoặc Ek. Đối với một hệ phục vụ ta quan niệm một khách hàng đến hệ là hiện tượng “sinh”, một khách hàng được phục vụ xong rời khỏi hệ là hiện tượng “ tử”. Chúng ta ký hiệu:  k cường độ đến (sinh) của khách hàng khi số khách hàng trong hệ phục vụ là k;  k cường độ phục vụ (tử) khách hàng khi số khách hàng trong hệ là k. 8 Luận Văn Thạc Sĩ Khoa Học Lưu ý rằng, cường độ đến; cường độ phục vụ (tức là cường độ ra khỏi hệ) là độc lập với thời gian và chỉ phụ thuộc vào trạng thái Ek. Quá trình sinh – tử có thể mô tả thông qua sơ đồ chuyển trạng thái sau Hình 1.1: Cường độ chuyển trạng thái của quá trình sinh – tử Trên sơ đồ, các đường nối tương ứng với các chuyển đổi trạng thái cùng với cường độ nhưng không chỉ ra xác suất chuyển trạng thái. Nhân cường độ chuyển trạng thái với dt sẽ nhận được xác suất chuyển (xác suất chuyển trạng thái) trong khoảng thời gian dt tiếp theo. Vấn đề cần giải quyết ở đây là phân phối xác suất của số khách hàng trong hệ phục vụ tại thời điểm t: Pk (t)  P(X(t)  k) (1.2) (X(t) chỉ số khách hàng trong hệ tại thời điểm t) Giả sử tại thời điểm t hệ ở trạng thái Ek, cường độ dòng vào trạng thái Ek là:  k 1Pk 1 (t)   k 1Pk 1 (t) Cường độ dòng ra trạng thái Ek tại thời điểm t: ( k   k )Pk (t) Rõ ràng rằng, hiệu số giữa hai đại lượng này là cường độ dòng vào trạng thái đó: dPk (t)   k 1Pk 1 (t)   k 1Pk 1 (t)  ( k   k )Pk (t) (1.3) dt Chúng ta nhận được hệ phương trình biểu thị hoạt động của hệ phục vụ đang xét:  dPk  t      k   k  Pk  t    k 1Pk 1  t    k 1Pk 1  t   dt   dP0  t    P  t    P  t  0 0 1 1  dt k0 (1.4) k0  Hơn nữa với mọi t luôn có:  P (t)  1 k (1.5) k 0 Gọi (k) là phân phối cân bằng cho trạng thái có k khách hàng: 9 Luận Văn Thạc Sĩ Khoa Học (k)  lim Pk (t) t  dPk (t) 0 t  dt  lim k=0;1;2;… (1.6) k=0;1;2;… (1.7) Trong hệ (1.4) cho t   ta được: 0     k   k    k    k 1  k  1   k 1  k  1 k  0 (1.8)  k0 0   0   0   1 1  0 (0)  1(1)  0  (0)  (   ) (1)   (2)  0 1 1 2  0 1(1)  ( 2   2 )(2)  3(3)  0 Ta có hệ:  (1.9) ....   k 1(k  1)  ( k   k )(k)   k 1(k  1)  0  .... Từ đó ta suy ra: (k  1)  k (k)  k 1 với mọi k = 0;1;2;…tức là: 0  (1)   (0) 1  1 1  0  (2)   (1)    (0) 2 2 1  2  2 1     (1)  2 1 0 (0) (3)  (2)  3 3  2 3  2 1  ....  (k)   k 1 (k  1)  ...   k 1 ...  2 1  0 (0)  k  k 3  2 1   i i 0  i 1 k 1 Như vậy ta có: (k)  (0)  k = 0;1;2;…  k 1 Giả sử S1  i   với điều kiện i0  k 1 i 1  10 (1.10)   (k)  1 ta có: k 1 Luận Văn Thạc Sĩ Khoa Học (0)  1 (1.11)  k 1  1   i i 0  k 1 i 1 Xét sự tồn tại của phân phối (k) . Rõ ràng là (0)  0 . Theo (1.10), (1.11) điều này rõ ràng là áp đặt điều kiện cho các hệ số sinh, tử. Hệ phục vụ phải được thiết kế sao cho hệ ít khi rỗng (không có khách hàng), đây là điều kiện đảm bảo tính ổn   k 1  định. Với: S1    i i 0  k 1 i 1 (1.12) ; S2   k 0 1 k 1  k  i i 0  i 1 (1.13) Quá trình sinh tử là dừng ergodic nếu và chỉ nếu: S1  , S2   Chúng ta thấy rằng, điều kiện để hệ phục vụ ổn định là k 0 : k  k 0 luôn có: k 1 k (1.14) Chúng ta thấy rằng quá trình sinh-tử là cở sở để nghiên cứu một số bài toán quan trọng của lý thuyết đám đông. 11 Luận Văn Thạc Sĩ Khoa Học CHƯƠNG II: TỔNG QUAN VỀ LÝ THUYẾT XẾP HÀNG 2.1 Những mô hình xếp hàng và một số khái niệm cơ bản 2.1.1. Mô hình xếp hàng và ký hiệu Kendall Một mô hình xếp hàng cơ bản được biểu diễn bởi hình sau: Hình 2.1: Mô hình xếp hàng cơ bản Nó có thể được sử dụng để mô hình hóa, ví dụ:mạng thông tin, mạng máy tính, thiết bị xử lý thông tin truyền thông,… Một mô hình xếp hàng được đặc trưng bởi các yếu tố: 1. Quá trình đến của những khách hàng: Thông thường giả sử rằng khoảng thời gian giữa các lần đến là độc lập và có cùng phân phối. Trong nhiều tình huống thực tế những khách hàng đến theo dòng Poisson. Những khách hàng có thể đến một hoặc theo hàng loạt, 2. Hành vi của những khách hàng: Khách hàng có thể kiên nhẫn và sẵn sàng chờ đợi ( trong một thời gian dài) hoặc có thể thiếu kiên nhẫn và rời đi sau một thời gian. Ví dụ tại các trung tâm cuộc gọi khách hàng có thể ngắt sau khi họ phải chờ đợi quá lâu trước khi nhà điều hành có thể phục vụ và họ có thể trở lại sau một thời gian. 3. Số lần phục vụ: Thông thường chúng ta giả sử số lần phục vụ là độc lập có cùng phân phối và chúng độc lập với khoảng thời gian giữa các lần đến. 4. Quy tắc phục vụ 12 Luận Văn Thạc Sĩ Khoa Học Những người khách có thể được phục vụ một hoặc hàng loạt. Chúng ta có nhiều khả năng phục vụ: Đến trước phục vụ trước (FCFS); Đến sau phục vụ trước (LCFS); thứ tự ngẫu nhiên; những quyền ưu tiên… 5. Khả năng phục vụ: Có thể có một máy phục vụ hoặc một nhóm các máy phục vụ khách hàng. 6. Phòng chờ: Có thể giới hạn khách hàng trong hệ thống. 7. Ký hiệu của Kendall: Kendall giới thiệu một ký hiệu để mô tả một loạt các mô hình xếp hàng này. Nó là bộ mã gồm ba phần: A/B/m +) A: biểu thị phân phối khoảng thời gian giữa các lần đến. +) B: biểu thị phân phối của thời gian phục vụ. +) m: biểu thị số lượng máy phục vụ. Đối với A, B thông thường là viết tắt của các phân phối +) M: quá trình Markov +) D: một phân phối tất định và không đổi. +) G: phân phối tổng quát chưa được xác định hầu hết các trường hợp ít nhất trung bình và phương sai đã biết. Ngoài ký hiệu trên đôi khi người ta còn sử dụng ký hiệu A/B/m/K, trong đó: K: là dung lượng hàng đợi. Nếu không sử dụng ký tự cuối ta coi nó là giá trị tùy ý. 2.1.2. Tỷ lệ thời gian cư ngụ Trong một hệ thống đơn máy phục vụ G/G/1 với cường độ đến  và trung bình thời gian phục vụ E(B), số lượng công việc đến trên một đơn vị thời gian bằng  E(B). ( ở đây B là phân phối của thời gian phục vụ). Máy chủ có thể xử lý một đơn vị công việc trên một đơn vị thời gian. Để tránh hàng đợi tiến dẫn đến vô cùng chúng ta yêu cầu: E  B   1. Không đi vào chi tiết chúng ta lưu ý rằng độ dài trung bình hàng đợi cũng sẽ bùng nổ khi E  B   1, ngoại trừ trường hợp D/D/1: nghĩa là hệ thống hoàn toàn không có tính ngẫu nhiên. 13 Luận Văn Thạc Sĩ Khoa Học Ký hiệu:   E  B  Nếu   1 thì  được gọi là tỷ lệ thời gian cư ngụ bởi vì nó là phân số của thời gian máy chủ sẽ làm việc. Trong hệ thống đa máy chủ: G/G/m, đòi hỏi E  B   m . Khi đó tỷ lệ thời gian cư ngụ theo số máy chủ:   E  B  / m . 2.1.3. Một số đại lượng đặc trưng Một số đại lượng đặc trưng trong phân tích các mô hình xếp hàng: - Phân phối của thời gian đợi và thời gian lưu trú của khách hàng. Thời gian lưu trú gồm thời gian đợi cộng với thời gian phục vụ. - Phân phối của số lượng công việc trong hệ thống. Đó là tổng thời gian phục vụ của khách đợi và thời gian phục vụ còn lại của khách hàng trong dịch vụ. - Phân phối của giai đoạn bận của máy chủ. Đây là khoảng thời gian mà máy chủ làm việc liên tục. Đặc biệt ta quan tâm đến một số đại lượng là thước đo, chẳng hạn như thời gian đợi trung bình và thời gian lưu trú trung bình. Bây giờ ta xét mô hình G/G/c. Ký hiệu biến ngẫu nhiên L(t), ký hiệu số khách hàng trong hệ thống tại thời điểm t, Sn là thời gian lưu trú của khách hàng thứ n trong hệ thống. Giả sử:   E  B   1. c Có thể chỉ ra rằng các biến ngẫu nhiên trên có giới hạn khi t   và n   Các phân phối này độc lập với điều kiện ban đầu của hệ thống. Gọi biến ngẫu nhiên L và S là phân phối giới hạn của L(t) và Sn . Do đó: p k  P  L  k   lim P  L(t)  k  t  FS  x   P  S  x   lim P Sn  x  n  Trong đó p k là xác suất có k khách hàng trong hệ thống, FS  x  xác định xác suất mà thời gian lưu trú của một khách hàng bất kỳ đi vào hệ thống là nhỏ hơn hoặc bằng x đơn vị thời gian. 14 Luận Văn Thạc Sĩ Khoa Học t 1 1 n L x dx  E L ; lim     n  Sk  E S t  t  n k 1 0 Hơn nữa với xác suất 1 ta có: lim Vậy số lượng khách hàng trung bình về lâu dài trong hệ thống là E(L) và thời gian lưu trú trung bình về lâu dài là E(S). Một kết quả rất hữu hiệu cho hệ thống xếp hàng liên quan giữa E(L) và E(S) được trình bày sau đây. 2.1.4. Định luật Little Định luật Little xác định một mối liên hệ rất quan trọng giữa E(L)-số khách hàng trung bình trong hệ thống và E(S)-thời gian lưu trú trung bình và  -số lượng khách hàng trung bình đi vào hệ thống trên một đơn vị thời gian. Định luật Little được phát biểu như sau: E  L   E  S  . Áp dụng định luật Little trong xếp hàng ( không bao gồm máy chủ) đưa đến mối quan hệ giữa chiều dài hàng đợi Lq và thời gian đợi W: E  Lq   E  W  Cuối cùng khi áp dụng định luật Little với một máy chủ duy nhất ta thu được:   E  B  . Ở đây  là số lượng khách hàng trung bình tại máy chủ và E(B) là trung bình thời gian phục vụ. 2.1.5. Tính chất PASTA Cho hệ thống xếp hàng với dòng đến Poisson, đối với hệ thống M/./. Một tính chất quan trọng chỉ ra rằng: phân phối của thời gian hệ thống phục vụ ở trạng thái A hoàn toàn giống với phân phối của lượng khách hàng đi đến hệ thống (theo dòng Poisson ) ở trạng thái A. Tính chất này chỉ đúng với dòng đến Poisson. Tính chất của dòng đến Poisson được gọi là tính chất PASTA (Poisson Arrivals See Time Averages). Bằng trực giác tính chất này có thể giải thích bởi thực tế rằng dòng đến Poisson diễn ra hoàn toàn ngẫu nhiên theo thời gian. 2.2. Mô hình xếp hàng M/M/1 Trong phần này ta sẽ phân tích mô hình với khoảng thời gian giữa các lần đến có phân phối mũ với trung bình 1/λ; thời gian phục vụ có phân phối mũ với trung bình 15
- Xem thêm -