Tóm tắt Luận án tiến sĩ Toán học: Một số dạng hàng đợi và các nguyên lý xử lý

Chia sẻ: Phong Tỉ | Ngày: | Loại File: PDF | Số trang:27

Thêm vào BST

Báo xấu

16
lượt xem 4
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Mục đích của luận án nhằm nghiên cứu hai lớp bài toán: lớp bài toán xác định quá trình dòng job luân chuyển trong mạng hàng đợi và lớp bài toán liên quan đến các quá trình trạng thái tại các nút mạng và của mạng hàng đợi.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Tóm tắt Luận án tiến sĩ Toán học: Một số dạng hàng đợi và các nguyên lý xử lý

BỘ GIÁO DỤC VÀ ĐÀO TẠO BỘ QUỐC PHÒNG VIỆN KHOA HỌC VÀ CÔNG NGHỆ QUÂN SỰ --------------------------- NGUYỄN TRUNG DŨNG MỘT SỐ DẠNG HÀNG ĐỢI VÀ CÁC NGUYÊN LÝ XỬ LÝ Chuyên ngành: Cơ sở toán học cho tin học Mã số: 9460110 TÓM TẮT LUẬN ÁN TIẾN SĨ TOÁN HỌC HÀ NỘI - 2018
Công trình được hoàn thành tại: VIỆN KHOA HỌC VÀ CÔNG NGHỆ QUÂN SỰ BỘ QUỐC PHÒNG Người hướng dẫn khoa học: 1. TS. NCVCC Nguyễn Hồng Hải. 2. TS Trần Quang Vinh. Phản biện 1: PGS.TS Phan Viết Thư Trường Đại học Khoa học tự nhiên, Đại học Quốc gia HN. Phản biện 2: PGS.TS Trần Nguyên Ngọc. Học viện Kỹ thuật quân sự. Phản biện 3: PGS.TS Ngô Quỳnh Thu. Đại học Bách khoa Hà Nội. Luận án được bảo vệ tại Hội đồng đánh giá luận án cấp Viện họp tại Viện Khoa học và Công nghệ quân sự vào hồi ….. ngày ….. tháng ..… năm …… Có thể tìm luận án tại thư viện: - Thư viện Viện Khoa học và Công nghệ quân sự. - Thư viện Quốc gia Việt Nam.
1 MỞ ĐẦU 1. Lý do chọn đề tài 1.1. Cùng với sự phát triển của khoa học kỹ thuật, nhiều mạng hàng đợi đã ra đời và được ứng dụng trong thực tế đời sống xã hội như hệ thống mạng viễn thông, hệ thống mạng máy tính, hệ thống dây chuyền sản xuất… Việc nghiên cứu, đánh giá hiệu năng hoạt động của các hệ thống này là một trong những bài toán quan trọng và phức tạp. Để nghiên cứu, đánh giá hiệu năng hoạt động của hệ thống, chúng ta có thể áp dụng nhiều công cụ toán học khác nhau và một trong công cụ toán học quan trọng có thể sử dụng là lý thuyết hàng đợi và lý thuyết mạng hàng đợi. 1.2. Các kết quả nghiên cứu của các tác giả trong và ngoài nước từ trước đến nay nhằm xác định phân phối xác suất của trạng thái mạng hàng đợi và các tham số hiệu năng khác của mạng… chỉ đạt được với mạng hàng đợi thỏa mãn điều kiện như dòng vào là dòng Poisson, thời gian phục vụ của các nút mạng các biến ngẫu nhiên có phân phối mũ, mạng hàng đợi hoạt động ở trạng thái cân bằng. Đối với mạng hàng đợi với giả thiết dòng vào tổng quát, thời gian phục vụ của các nút mạng là các biến ngẫu nhiên có phân phối bất kỳ, các tác giả mới dừng lại ở việc xác định phân phối xác suất gần đúng của trạng thái mạng hàng đợi trong một số điều kiện nhất định. 1.3. Có nhiều vấn đề kể cả từ thực tiễn cũng như từ lý thuyết đòi hỏi phải xét những mô hình mạng hàng đợi với những giả thiết rộng rãi hơn được đặt lên các cấu trúc của mạng hàng đợi như: giả thiết về dòng job từ bên ngoài vào mạng phục vụ; giả thiết về thời gian phục vụ, giả thiết về cơ chế ưu tiên phục vụ; giả thiết về cơ chế xây dựng ma trận xác suất chuyển định tuyến trong mạng hàng đợi… 2. Đối tượng nghiên cứu: Đối tượng nghiên cứu của luận án là mạng hàng đợi dạng tổng quát. 3. Nội dung nghiên cứu chính: Nghiên cứu hai lớp bài toán: lớp bài toán xác định quá trình dòng job luân chuyển trong mạng hàng đợi và lớp bài toán liên quan đến các quá trình trạng thái tại các nút mạng và của mạng hàng đợi. 4. Ý nghĩa khoa học và thực tiễn: Mục tiêu và đích nghiên cứu của đề tài có tính thời sự đã và đang được nhiều tác giả trên thế giới quan tâm nghiên cứu. Nội dung nghiên cứu có tính khoa học và có tính thực tiễn. 5. Phương pháp nghiên cứu: Sử dụng các phương pháp của lý thuyết hàng đợi và mạng hàng đợi, kết hợp với một số phương pháp của lý thuyết xác suất và thống kê toán học để nghiên cứu và giải quyết một số bài toán quan trọng trong mô hình mạng hàng đợi tổng quát.
2 6. Bố cục luận án: Ngoài phần mở đầu; kết luận; các công trình khoa học đã công bố; tài liệu tham khảo; nội dung của luận án được trình bày trong ba chương: Chương 1. Một số vấn đề cơ bản về lý thuyết hàng đợi và mạng hàng đợi. Chương 2. Mạng đa lớp tổng quát – Thuật toán phân rã và tổng hợp. Chương 3. Đánh giá quá trình trạng thái của mạng hàng đợi tổng quát. CHƯƠNG 1 MỘT SỐ VẤN ĐỀ CƠ BẢN VỀ LÝ THUYẾT HÀNG ĐỢI VÀ MẠNG HÀNG ĐỢI Chương 1 trình bày một số kiến thức sẽ được sử dụng cho việc nghiên cứu sâu về mạng hàng đợi trong chương 2 và chương 3. Đồng thời chương 1 trình bày tình hình nghiên cứu trên thế giới từ trước đến nay về mạng hàng đợi từ đó xác định các nội dung cần nghiên cứu trong luận án. 1.1. Một số khái niệm xác suất có liên quan Trong mục này luận án trình bày về một số khái niệm xác suất cơ bản có liên quan đến luận án như biến ngẫu nhiên; Hàm phân phối của biến ngẫu nhiên; Các đặc trưng của biến ngẫu nhiên ([5], [10], [44]). 1.2. Quá trình Markov Trong mục này luận án trình bày về một số khái niệm về quá trình Markov liên quan đến luận án như định nghĩa quá trình ngẫu nhiên; Ma trận xác suất chuyển của xích Markov; Phân phối xác suất của trạng thái xích Markov; Phân phối dừng và phân phối giới hạn của trạng thái xích Markov thuần nhất thời gian rời rạc ([9], [10], [34], [36]). 1.3. Lý thuyết hàng đợi và mạng hàng đợi Trong mục này luận án trình bày về các khái niệm cơ bản liên quan đến hàng đợi và mạng hàng đợi ([19], [20], [29], [32], [33], [34], [36], [47]). 1.3.1. Hàng đợi Về mặt toán học, hàng đợi được ký hiệu bởi: A / B / m / K − Cơ chế ưu tiên phục vụ Trong đó: Thời gian giữa hai lần job đến liên tiếp là các biến ngẫu nhiên độc lập cùng phân phối và phân phối này được ký hiệu là A ; Thời gian phục vụ các job là các biến ngẫu nhiên độc lập, cùng phân phối và phân phối này được ký hiệu là B ; m biểu thị số lượng trạm phục vụ ( m  1 ); K biểu thị kích thước của hàng đợi (là số job lớn nhất có thể có trong hàng đợi). Các ký hiệu sau thường được sử dụng đối với A và B : M (phân phối mũ); Ek , (phân phối Erlang tham số k ,  ); D (phân phối suy biến (nghĩa là thời gian phục vụ job là hằng số)); G (phân phối tổng quát). Cơ chế ưu tiên phục vụ: Có một số cơ chế dòng vào và ưu tiên phục vụ thường được sử dụng như: FIFO (job vào trước thì sẽ ra trước); FCFS (job đến
3 trước thì sẽ được phục vụ trước); LCFS (job đến sau thì sẽ được phục vụ trước); SIRO (job được lựa chọn phục vụ một cách ngẫu nhiên)… Một số thông số hiệu năng của hàng đợi: Phân phối xác suất của trạng thái hàng đợi (số job có trong hàng đợi); Thông lượng của hàng đợi; Trung bình thời gian job ở trong hàng đợi; Trung bình số job có trong hàng đợi… Định nghĩa 1.13. Hàng đợi được gọi là hoạt động cân bằng nếu tổng cường độ dòng job vào hàng đợi bằng tổng cường độ dòng job ra khỏi hàng đợi. 1.3.2. Mạng hàng đợi Định nghĩa 1.14. Mạng hàng đợi được gọi là hoạt động cân bằng nếu tất cả các nút của mạng hoạt động cân bằng. a. Mạng hàng đợi đơn lớp Một mạng hàng đợi đơn lớp (nghĩa là tất cả các job thuộc cùng một lớp) được đặc trưng bởi các thành phần sau đây: - N (hoặc J ): Số nút mạng hàng đợi; ki (hoặc xi ): Số job có trong nút ( i i = 1, N ) và được gọi là trạng thái của nút i ; ( k1 ,..., kN ) : Trạng thái của mạng hàng đợi. - mi : Số trạm (server) phục vụ song song có trong nút i ; i : Cường độ phục vụ của nút i ; 1  : Trung bình thời gian phục vụ một job của nút i . i - pij : Xác suất luân chuyển job từ nút i sang nút j ( i, j = 0, N ) . Trong đó p0j là xác suất job từ bên ngoài mạng hàng đợi vào nút j và pi 0 là xác suất job từ nút i ra ngoài mạng hàng đợi. - 0i : cường độ dòng job từ bên ngoài mạng đến nút i của mạng hàng N đợi; i =   ji : cường độ dòng job vào nút i của mạng hàng đợi trong đó j =0 0i là cường độ dòng job từ bên ngoài mạng hàng đợi vào nút i ,  ji là cường độ dòng job từ nút j ( j = 1, N , j  i ) vào nút i và ii là cường độ dòng job ra khỏi nút i và quay trở lại nút i để được phục vụ tiếp. b. Mạng hàng đợi đa lớp Mạng hàng đợi đa lớp được đặc trưng bởi các thành phần sau đây: - N (hoặc J ): Số nút mạng hàng đợi; R : Số lớp job. - kir ( r = 1, R ) : Số job thuộc lớp r có trong nút i tại thời điểm quan sát; N K r =  kir : Số job thuộc lớp r có trong mạng hàng đợi. i =1
4 - Si = ( ki1 ,..., kiR ) : Trạng thái của nút i . S = ( S1 ,..., S N ) : Trạng thái của mạng hàng đợi. - ir : Cường độ phục vụ job thuộc lớp r của nút i . - pir,js : Xác suất luân chuyển job thuộc lớp r từ nút i sang nút j và trở thành job thuộc lớp s ; p0,js là xác suất job từ bên ngoài mạng hàng đợi vào nút j và trở thành job thuộc lớp s ; pir,0 là xác suất job thuộc lớp r từ nút i ra ngoài mạng hàng đợi. -  : Tổng cường độ dòng job từ bên ngoài vào mạng hàng đợi; 0,ir =  p0,ir : Cường độ dòng job từ bên ngoài mạng hàng đợi vào nút i và trở thành job thuộc lớp r ; ir : cường độ dòng job vào nút i và trở thành job thuộc lớp r . Một số thông số hiệu năng hoạt động của mạng hàng đợi: Với định nghĩa trạng thái của nút mạng i tại thời điểm t là số job có trong nút mạng tại thời điểm t khi đó có một số thông số hiệu năng của mạng hàng đợi như: Phân phối xác suất của trạng thái nút mạng và mạng hàng đợi; Xác suất tắc nghẽn mạng; Thông lượng của nút mạng và của mạng hàng đợi; Trung bình số job có trong nút mạng và trong mạng hàng đợi… d. Lý thuyết hàng đợi ứng dụng trong mạng viễn thông, mạng máy tính Khi xem xét, đánh giá hoạt động của mạng viễn thông và mạng máy tính, chúng ta đặc biệt quan tâm đến yếu tố về lưu lượng dữ liệu truyền nhận trong mạng và dựa vào các công cụ toán học trong đó công cụ toán học về lý thuyết xác suất và lý thuyết quá trình ngẫu nhiên là hai công cụ toán học quan trọng để xem xét và đánh giá hoạt động của mạng viễn thông và mạng máy tính. 1.4. Tình hình nghiên cứu trong nước và ngoài nước về mạng hàng đợi Các kết quả nghiên cứu của các tác giả trong và ngoài nước từ trước đến nay nhằm xác định các tham số hiệu năng của mạng hàng đợi như phân phối xác suất của trạng thái nút mạng và mạng hàng đợi; xác suất tắc nghẽn mạng; thông lượng của nút mạng và của mạng hàng đợi…chỉ đạt được với mạng hàng đợi thỏa mãn điều kiện như dòng vào là dòng Poisson, thời gian phục vụ của các nút mạng các biến ngẫu nhiên có phân phối mũ, mạng hàng đợi hoạt động ở trạng thái cân bằng. Đối với mạng hàng đợi với giả thiết dòng vào tổng quát, thời gian phục vụ của các nút mạng là các biến ngẫu nhiên có phân phối bất kỳ và mạng hàng đợi thỏa mãn một số điều kiện khác khi đó các tác giả mới dừng lại ở việc xác định phân phối xác suất gần đúng của trạng thái mạng hàng đợi. Thực tiễn và lý thuyết đòi hỏi phải xét những mô hình mạng hàng đợi với những giả thiết rộng rãi hơn. Vì vậy luận án tập trung nghiên cứu hai lớp bài
5 toán: lớp bài toán nghiên cứu quá trình trạng thái của các nút mạng, quá trình trạng thái của mạng hàng đợi và lớp bài toán xác định quá trình dòng job luân chuyển trong mạng hàng đợi với đối tượng nghiên cứu là mạng hàng đợi dạng tổng quát. Kết luận chương 1 Trong chương 1, luận án đã trình bày một số khái niệm về xác suất, lý thuyết quá trình Markov và lý thuyết hàng đợi, mạng hàng đợi được sử dụng trong luận án. Đồng thời chương 1 trình bày tình hình nghiên cứu của các tác giả trên thế giới từ trước đến nay về mạng hàng đợi, những vấn đề mở trong các mô hình mạng hàng đợi đã được công bố từ đó luận án xác định hai lớp bài toán cần nghiên cứu đó là lớp bài toán nghiên cứu quá trình trạng thái của các nút mạng, quá trình trạng thái của mạng hàng đợi và lớp bài toán xác định quá trình dòng job luân chuyển trong mạng hàng đợi với đối tượng nghiên cứu là mạng hàng đợi dạng tổng quát. Các nội dung đã trình bày trong chương 1 sẽ được sử dụng cho việc nghiên cứu sâu về mạng hàng đợi trong chương 2 và chương 3 của luận án. CHƯƠNG 2 MẠNG ĐA LỚP TỔNG QUÁT - THUẬT TOÁN PHÂN RÃ VÀ TỔNG HỢP Nội dung của chương 2 sử dụng các kết quả đã được công bố trong hai bài báo [2],[3] thuộc danh mục các công trình đã công bố. Sự luân chuyển của dòng job trong mạng hàng đợi là vấn đề quan tâm số 1 khi nghiên cứu về hàng đợi và mạng hàng đợi. Với một mạng hàng đợi bất kỳ, về mặt lý thuyết thì dòng job từ bên ngoài có thể vào bất kỳ nút nào trong mạng, dòng job sau khi ra khỏi một nút có thể vào bất kỳ nút khác trong mạng hoặc ra ngoài mạng và tại cùng một thời điểm giữa hai nút i và j có thể xảy ra: 1 job a chuyển từ nút i sang nút j, đồng thời 1 job b chuyển từ nút j sang nút i. Bởi vậy việc nghiên cứu dòng job trong mạng hàng đợi là rất phức tạp. Trong luận án này chúng tôi đưa ra kỹ thuật phân rã và tổng hợp để nghiên cứu dòng job luân chuyển trong mạng hàng đợi. 2.1. Phân rã mạng hàng đợi tổng quát thành các mạng thành phần Đối với mạng hàng đợi bất kỳ thì các dòng job luân chuyển giữa các nút trong mạng là các dòng job luân chuyển đan xen nhau và theo các chiều khác nhau. Với mạng hàng đợi được ký hiệu là ( i, j ) ( i, j = 1, J ; J  + ) khi đó dòng job luân chuyển trong mạng hàng đợi ( i, j ) được mô tả bởi ma trận xác suất định tuyến P(i , j ) (t ) =  pk( i,l, j ) (t )  k ,l =0, J trong đó pk( i,l, j ) (t ) là xác suất định tuyến job chuyển từ nút k sang nút l trong mạng hàng đợi ( i, j ) tại thời điểm t
6 ( k , l = 1, J ) , p0,( ik, j ) (t ) là xác suất định tuyến job từ ngoài mạng hàng đợi ( i, j ) vào nút k trong mạng hàng đợi ( i, j ) tại thời điểm t và pl(,0i , j ) (t ) là xác suất định tuyến job chuyển từ nút l trong mạng hàng đợi ( i, j ) ra ngoài mạng hàng đợi ( i, j ) tại thời điểm t . Định nghĩa 2.1. Giả sử mạng có các nút được ký hiệu là 0,1, 2,..., J , J  + (trong đó 0 là nút hình thức được bổ sung vào mạng như nói ở trên) và giả sử i, j 1, 2,..., J  , khi đó mạng thành phần ( i, j ) là một mạng hàng đợi thỏa mãn các điều kiện sau:  p (i , j ) (t )  0  p0,( ii, j ) (t ) = 1 j ,0  ( i , j ) (i )  ( i , j ) ; (ii )  pk ,0 (t ) = 0 k  j , k = 1, J  k ,i p (t ) = 0  k  i , k = 1, J  (i , j )  p j ,l (t ) = 0 l  j , l = 1, J . (2.1)  pk( i,l, j ) (t ) pl(,ik, j ) (t ) = 0 t , k  l (iii )  k , l = 1, J Với định nghĩa 2.1 về mạng thành phần có hướng khi đó chúng ta luôn luôn phân rã một mạng hàng đợi bất kỳ có J nút thành các mạng thành phần có hướng ( i, j ) ( i, j = 1, J ) và tổng số mạng thành phần có hướng là chỉnh hợp lặp chập 2 của J (và bằng J 2 mạng thành phần có hướng). Với lập luận và chứng minh ở trên, chúng ta có định lý sau đây: Định lý 2.1. Một mạng có J nút bất kỳ ( J  + ) luôn luôn được phân rã thành J 2 mạng thành phần có hướng (theo định nghĩa 2.1). 2.2. Tổng hợp mạng hàng đợi tổng quát theo các mạng thành phần Trong mục này trình bày kỹ thuật “chập” các mạng thành phần có hướng. Dựa trên kết quả đó (mà chúng ta gọi là kỹ tổng hợp mạng) chúng ta có thể đưa việc nghiên cứu mạng tổng quát phức tạp về nghiên cứu các mạng thành phần có hướng đơn giản hơn. 2.2.1. Luân chuyển job trong mạng hàng đợi tổng quát G/G/J trong bối cảnh job luân chuyển giữa các mạng thành phần Giả thiết 2.1. Biết dòng job luân chuyển trong các mạng thành phần. Trong mạng chập của các mạng thành phần, các mạng thành phần hoạt động không độc lập với nhau và biết cơ chế luân chuyển job giữa các mạng thành phần (cơ chế luân chuyển này còn được gọi là cơ chế chuyển pha trong mạng hàng đợi). Định nghĩa 2.2. Quá trình luân chuyển job trong mạng chập được phân chia thành các bước và được định nghĩa như sau:
7 Xét quá trình lưu chuyển dòng job trong mạng hàng đợi. Ký hiệu ij ( t ) là lượng job chuyển từ nút i sang nút j tại thời điểm t ( i, j = 0, J ). Trong đó 0j ( t ) là lượng job từ bên ngoài mạng vào trong nút j tại thời điểm t,  j0 ( t ) là lượng job từ nút j ra khỏi mạng tại thời điểm t và ij ( t ) là lượng job chuyển từ nút i sang nút j tại thời điểm t ( i, j = 1, J , i  j ) . Với quy ước  0 là thời điểm quan sát xuất phát ban đầu và thời điểm  n được định nghĩa qui nạp như sau:  J J J   1 = min t   0 | 0j ( t ) +    (t )  0  ij  j =1 i =1 j =0, j i  ...  J J J   n = min t   n−1 |   0j ( t ) +    ( t )  0  , n = 2,3,... ij  j =1 i =1 j =0, j i  Khi đó mỗi một điểm  n ( n = 0,1,...) được xem như là bước luân chuyển thứ n của dòng job trong mạng hàng đợi. Để mô tả dòng job từ các mạng thành phần tại các nút của mạng chập ra ngoài mạng chập và dòng job ngoài mạng chập vào các mạng thành phần tại các nút của mạng chập, chúng ta bổ sung thêm mạng thành phần  = ( 0,0 ) (mạng thành phần hình thức), mạng hình thức này không chứa bất kỳ nút nào của mạng chập (là ký hiệu của môi trường ngoài của mạng chập). Dòng job ngoài mạng chập vào các mạng thành phần tại các nút của mạng chập chính là dòng job từ mạng  = ( 0,0 ) vào các mạng thành phần tại các nút của mạng chập, dòng job ra khỏi các mạng thành phần tại các nút của mạng chập chính là dòng job từ các mạng thành phần tại các nút của mạng chập vào mạng  = ( 0,0 ) . Các ký hiệu: - L = (i, j ) | i, j 1, 2,..., J  là tập tất cả các mạng thành phần của mạng hàng đợi; Li là tập các mạng thành phần có chứa nút i ( i = 1, J ) . Tại bước n ( n = 1,2,...) : + Pc (n) =  pic, j (n)  i , j =0, J là ma trận xác suất định tuyến của mạng thành phần c ( c  L ) trong đó pic, j (n) là xác suất định tuyến job chuyển từ nút i sang nút j trong mạng thành phần c .  0 0  + Si ( n) =   trong đó Si (n) =  Sic,d (n)c,dL là ma trận xác suất chuyển  si (n) Si (n)  i job trong nút i giữa các mạng thành phần với Sic,d (n) là xác suất chuyển job trong nút i từ mạng thành phần c sang mạng thành phần d và
8 ( ) T si (n) = sic (n) cLi là véc tơ xác suất chuyển job từ nút i ra ngoài mạng hàng đợi với sic (n) là xác suất chuyển job từ nút i trong mạng thành phần c ra ngoài mạng hàng đợi. + ai ( n ) = ( aic ( n ) )c L là véc tơ chỉ lưu lượng dòng job đến nút i trong mạng i hàng đợi. Trong đó aic ( n ) là lưu lượng dòng job đến nút i của mạng thành phần c ( c  Li ) và ai ( n ) = 0 . + bi ( n ) = ( bic ( n ) )cL là véc tơ chỉ lưu lượng dòng job tại nút i trong mạng hàng i đợi. Trong đó bic ( n ) là lưu lượng dòng job tại nút i trong mạng thành phần c . + vi ( n ) = ( vic ( n ) )c L là véc tơ chỉ lưu lượng dòng job từ ngoài mạng hàng i đợi vào nút i trong mạng hàng đợi. Trong đó vic ( n ) là lưu lượng dòng job từ bên ngoài vào trong mạng thành phần c ( c  Li ) tại nút i và vi ( n ) = 0 . + di ( n ) là lưu lượng dòng job từ nút i ra khỏi mạng hàng đợi. Từ định nghĩa 2.1 về mạng thành phần khi đó: - Với mọi nút i được mạng thành phần c  L sử dụng tại bước thứ n ta có: sic (n) +  Sic ,d (n) = 1 . (2.2) d Li - Với mọi nút i được mạng thành phần ( h, l )  L sử dụng tại bước n ta có:  p0,i ( h ,l ) (n) = 1 nÕu i = h; pi,h ( h ,l ) (n) = 0 nÕu i  h J  p ( h ,l ) ( n ) = 1  i,j  j =0 . (2.3)  p ( h ,l ) (n) p ( h ,l ) (n) = 0 víi j = 1, J vµ j  i  i,j j,i  p ( h ,l ) (n) = 0 nÕu i  l ; p ( h ,l ) (n) = 0, s ( h ,l ) (n) = 0 nÕu i  l  l ,i i ,0 i - Với mọi nút i không được mạng thành phần ( h, l )  L sử dụng tại bước thứ n ta có:  J ( h ,l )  pi,j (n) + p j,i (n) = 0 ( h ,l )  j =0 . (2.4)  s ( h ,l ) ( n ) = 0  i 2.2.1.1. Xác định dòng job luân chuyển trong mạng hàng đợi Γ được chập bởi hai mạng thành phần (1):=(i1 ,j1) và (2):=(i2 ,j2) Từ đặc điểm về dòng job luân chuyển trong mạng thành phần khi đó: (1),(2) nÕu i1  i2 hoÆc j1  j2 - Nếu i1  j1 và i2  j2 : Li =  . (1) nÕu i1 = i2 vµ j1 = j2
9  L = (1),(2) - Nếu i1  j1 và i2 = j2 :  i 2 .  Li = (1) víi i  i2  Li = (1),(2) - Nếu i1 = j1 và i2  j2 :  1 .  Li = (2) víi i  i1  Li1 = (1)   Li1 = Li2 = (1)  Li = (2)  - Nếu i1 = j1 và i2 = j2 :  2 hoặc  Li = () víi i  i1 .  Li = () víi i  i1 , i  i2 i = i   1 2 i1  i2 - Luân chuyển job trong mạng hàng đợi Γ ở bước n (n≥1) Lưu lượng dòng job từ ngoài mạng vào trong nút i ( i = 1, J ) mạng hàng đợi Γ ở bước n là: vi (n) = ( vic (n) ) . (2.5) c Li Lưu lượng dòng job đến nút i trong mạng hàng đợi Γ ở bước n là: ( ) J ai (n) = aic (n) c Li với aic (n) = vic (n) +  j =1, j  i ,cL j bcj (n − 1) p cji (n − 1) . (2.6) Lưu lượng dòng job luân chuyển giữa các mạng thành phần tại nút i ở bước n là: ( )  ai(1) (n) si(1) (n), ai(1) (n) Si(1),(1) (n) nÕu Li = (1)  ( )  ai(2) (n) si(2) (n), ai(2) (n) Si(2),(2) (n) nÕu Li = (2)  ri (n) =  a (1) (n) s (1) (n) + a (2) (n) s (2) (n), a (1) (n) S (1),(1) (n) + a (2) (n) S (2),(1) (n),  . (2.7)  i  nÕu Li = (1),(2) i i i i i i i  ai(1) (n) Si(1),(2) (n) + ai( 2) (n) Si(2),(2) (n)    Lưu lượng dòng job tại nút i của mạng hàng đợi Γ ở bước n là: ( ai(1) (n) Si(1),(1) (n) + bi(1) (n − 1) pi(1),i (n − 1) ) nÕu Li = (1)  (  ai(2) (n) Si(2),(2) (n) + bi(2) (n − 1) pi(2)  ) ,i ( n − 1) nÕu Li = (2) bi (n) =  a (1) (n) S (1),(1) (n) + a (2) (n) S (2),(1) (n) + b(1) (n − 1) p (1) (n − 1),  . (2.8)   nÕu Li = (1), (2) i i i i i i ,i  ai(1) (n) Si(1),(2) (n) + ai(2) (n) Si(2),(2) (n) + bi(2) (n − 1) pi(2)  ,i ( n − 1)    Và lưu lượng dòng job từ nút i ra ngoài mạng hàng đợi Γ ở bước n là: ai(1) (n) si(1) (n) + bi(1) (n − 1) pi(1),0 (n − 1) nÕu Li = (1)  di (n) = ai(2) (n) si(2) (n) + bi(2) (n − 1) pi(2) ,0 ( n − 1) nÕu Li = (2) .  (1) ai (n) si (n) + ai (n) si (n) + bi (n − 1) pi ,0 (n − 1) + bi (n − 1) pi ,0 (n − 1) nÕu Li = (1),(2) (1) (2) (2) (1) (1) (2) (2) (2.9)
10 Như vậy trong mục này luận án đã trình bày quá trình luân chuyển job của mạng hàng đợi được chập bởi 2 mạng thành phần. Công thức (2.8) thể hiện sự thay đổi về lưu lượng dòng job tại các nút mạng tại các bước qua đó thấy được sự luân chuyển job trong mạng hàng đợi. Công thức (2.9) thể hiện năng lực phục vụ của mạng hàng đợi. 2.2.1.2. Xác định luân chuyển job trong mạng hàng đợi Γ được chập bởi J2 mạng thành phần. - Luân chuyển job trong mạng hàng đợi Γ ở bước n (n≥1) Với lưu lượng dòng job từ ngoài mạng vào trong nút i ( i = 1, J ) của mạng hàng đợi Γ ở bước n là vi ( n ) = ( vic ( n ) )c L . (2.10) i Khi đó lưu lượng dòng job đến nút i của mạng hàng đợi Γ ở bước n là: ( ) J ai (n) = aic (n) c Li với aic (n) = vic (n) +  j =1; j  i :cL j bcj (n − 1) p cji (n − 1) . (2.11) Lưu lượng dòng job luân chuyển giữa các mạng thành phần tại nút i ở bước n là: ri (n) := ai (n)Si (n) . (2.12) Lưu lượng dòng job tại nút i của mạng hàng đợi Γ ở bước n là: bi (n) = ( bic (n) ) với bic (n) = ric (n) + bic (n −1) piic (n −1) . (2.13) cL i Lưu lượng dòng job từ nút i ra ngoài mạng hàng đợi Γ ở bước n là: di (n) =  aic (n)sic (n) + bi(c ) (n − 1) pi(,0c ) (n − 1) . (2.14) cLi Như vậy trong mục này luận án đã trình bày quá trình luân chuyển job của mạng hàng đợi được chập bởi J 2 mạng thành phần. Công thức (2.13) thể hiện sự thay đổi về lưu lượng dòng job tại các nút mạng tại các bước qua đó thấy được sự luân chuyển job trong mạng hàng đợi. Công thức (2.14) thể hiện năng lực phục vụ của mạng hàng đợi tại các bước. Với lập luận và chứng minh ở trên, chúng ta có định lý sau đây: Định lý 2.2. Mọi mạng hàng đợi bất kỳ có J nút luôn luôn có thể biểu diễn là chập của J 2 mạng thành phần có hướng (theo định nghĩa 2.1) và với các lưu lượng của dòng job (các thành phần vi ( n ) , ai ( n ) , bi ( n ) , di ( n ) ) tại bước n được tính theo các công thức (2.10),(2.11),(2.13),(2.14). 2.2.2. Xét trường hợp riêng – trong mạng chập không có sự luân chuyển dòng job giữa các mạng thành phần Các ký hiệu: - L = (i, j ) | i, j 1, 2,..., J  là tập tất cả các mạng thành phần của mạng hàng đợi tổng quát có J nút.
11 - P( h,l ) =  pi,j( h,l ) i , j =0, J là ma trận xác suất định tuyến của mạng thành phần ( h, l ) ( (h, l )  L ). Trong đó pi,j( h,l ) là xác suất định tuyến job chuyển từ nút i sang nút j trong mạng thành phần ( h, l ) tại thời điểm t , p0,i ( h ,l ) là xác suất định tuyến job từ ngoài mạng thành phần ( h, l ) vào nút i trong mạng thành phần ( h, l ) tại thời điểm t và p (j,0h,l ) là xác suất định tuyến job chuyển từ nút j trong mạng thành phần ( h, l ) ra ngoài mạng thành phần ( h, l ) tại thời điểm t ; - P =  pi,j i , j =0, J là ma trận xác suất định tuyến của mạng chập. Trong đó pi,j là xác suất định tuyến job chuyển từ nút i sang nút j trong mạng chập tại thời điểm t , p0,i là xác suất định tuyến job từ ngoài mạng chập vào nút i trong mạng chập tại thời điểm t và p j ,0 là xác suất định tuyến job chuyển từ nút j ra ngoài mạng chập tại thời điểm t . - Ai(,hj,l ) là biến cố job chuyển từ nút i sang nút j trong mạng thành phần ( h, l ) ( (h, l )  L ) tại thời điểm t , A0,( hi,l ) là biến cố job từ ngoài mạng thành phần ( h, l ) vào nút i trong mạng thành phần ( h, l ) tại thời điểm t và A(j h,0,l ) là biến cố job chuyển từ nút j trong mạng thành phần ( h, l ) ra ngoài mạng thành phần ( h, l ) tại thời điểm t ; Ai , j là biến cố job chuyển từ nút i sang nút j trong mạng chập tại thời điểm t , A0,i là biến cố job từ ngoài mạng chập vào nút i trong mạng chập tại thời điểm t và Aj ,0 là biến cố job chuyển từ nút j trong mạng chập ra ngoài mạng chập tại thời điểm t . Giả thiết 2.2. Giả thiết rằng đã biết dòng job luân chuyển trong các mạng thành phần. Trong mạng chập của các mạng thành phần giả thiết rằng dòng job luân chuyển trong các mạng thành phần độc lập với nhau và không có sự luân chuyển job từ mạng thành phần này sang mạng thành phần khác. Từ định nghĩa 2.1 về mạng thành phần khi đó: - Với mọi nút i được mạng thành phần ( h, l )  L sử dụng tại thời điểm t ta có:  J ( h ,l )  pi,j ( t ) = 1  j =0  p ( h ,l ) ( t ) = 0 nÕu i  l  i,0 . (2.15)  p ( h ,l ) ( t ) = 0 nÕu i  h  0,i  p ( h ,l ) ( t ) p ( h ,l ) ( t ) = 0 j = 1, J vµ j  i  i,j j,i - Với mọi nút i không được mạng thành phần ( h, l )  L sử dụng tại thời điểm t ta có:
12 J  p (t ) = 0 . j =0 ( h ,l ) i, j (2.16) 2.2.2.1. Xác định dòng job trong mạng hàng đợi Γ được chập bởi hai mạng thành phần Xét mạng hàng đợi Γ là chập của 2 mạng thành phần ( i1 , j1 ) và ( i2 , j2 ) . Vì Ai(,ij , j ) ( t ) ( k = 1, 2 ) là biến cố job chuyển từ nút i sang nút j trong mạng thành k k phần ( ik , jk ) tại thời điểm t và Ai , j là biến cố job chuyển từ nút i sang nút j trong mạng hàng đợi Γ tại thời điểm t . Khi đó ta có: Ai , j ( t ) = Ai(,ij , j ) ( t ) Ai(,ij , j ) ( t ) . 1 1 2 2 (2.17) Từ giả thiết 2.2 khi đó hai mạng thành phần ( i1 , j1 ) và ( i2 , j2 ) hoạt động độc lập với nhau. Vì vậy ta có:  Ai , j ( t ) = pi(,ij, j ) ( t ) + pi(,ij , j ) ( t ) − pi(,ij, j ) ( t ) pi(,ij , j ) ( t ) . 1 1 2 2 1 1 2 2 (2.18) Từ giả thiết 2.2 và công thức (2.18) ta thấy nếu mạng hàng đợi Γ là chập của hai mạng thành phần và biết xác suất job luân chuyển giữa các nút trong hai mạng thành phần thì sẽ xác định được xác suất job luân chuyển giữa các nút trong mạng hàng đợi Γ. 2.2.2.2. Xác định dòng job trong mạng hàng đợi Γ được chập bởi J2 mạng thành phần Vì mạng hàng đợi có J nút nên mạng hàng đợi Γ được chập bởi J 2 mạng thành phần. Vì vậy ta có: Ai , j ( t ) = Ai(,kj,l ) ( t ) . (2.19) ( k ,l )L Từ giả thiết 2.2 khi đó các mạng thành phần hoạt động độc lập với nhau nghĩa là các biến cố Ai(,kj,l ) ( t ) ( ( k , l )  L ) độc lập với nhau. Nên ta có:  Ai , j ( t )  = 1 −  (1 − pi(,kj,l ) ( t ) ) . (2.20) ( k ,l )L Từ giả thiết của bài toán 2.2 và công thức (2.20) ta thấy nếu biết xác suất job luân chuyển giữa các nút trong tất cả các mạng thành phần thì sẽ xác định được xác suất job luân chuyển giữa các nút trong mạng hàng đợi. 2.3. Về một mô hình mạng hàng đợi cụ thể Trong mục này luận án trình bày về mạng hàng đợi có 5 nút mạng. Áp dụng các kết quả của mục 2.2.1 trong chương 2 để tính toán lưu lượng dòng job luân chuyển trong mạng hàng đợi tại các bước. 2.3.1. Tập các mạng thành phần Để dễ cho việc trình bày, chúng ta thực hiện chỉ số hóa các mạng thành phần lần lượt từ 1 đến 25 theo bảng sau:
13 Bảng 2.1. Chỉ số hóa các mạng thành phần Chỉ số Mạng thành Chỉ số Mạng Chỉ số Mạng hóa phần tương hóa thành phần hóa thành phần ứng tương ứng tương ứng 1 (1,1) 10 (2,5) 19 (4,4) 2 (1,2) 11 (3,1) 20 (4,5) 3 (1,3) 12 (3,2) 21 (5,1) 4 (1,4) 13 (3,3) 22 (5,2) 5 (1,5) 14 (3,4) 23 (5,3) 6 (2,1) 15 (3,5) 24 (5,4) 7 (2,2) 16 (4,1) 25 (5,5) 8 (2,3) 17 (4,2) 9 (2,4) 18 (4,3) Khi đó ta có: - Tập các mạng thành phần chứa nút 1 là: L1 = 1, 2,3, 4,5,6,8,9,10,11,12,14,15,16,17,18, 20, 21, 22, 23, 24 - Tập các mạng thành phần chứa nút 2 là: L2 = 2,3, 4,5,6,7,8,9,10,11,12,14,15,16,17,18, 20, 21, 22, 23, 24 - Tập các mạng thành phần chứa nút 3 là: L3 = 2,3, 4,5,6,8,9,10,11,12,13,14,15,16,17,18, 20, 21, 22, 23, 24 - Tập các mạng thành phần chứa nút 4 là: L4 = 2,3, 4,5,6,8,9,10,11,12,14,15,16,17,18,19, 20, 21, 22, 23, 24 - Tập các mạng thành phần chứa nút 5 là: L5 = 2,3, 4,5,6,8,9,10,11,12,14,15,16,17,18, 20, 21, 22, 23, 24, 25 2.3.2. Dòng job luân chuyển trong mạng hàng đợi tại bước n (n≥1) a. Lưu lượng dòng job từ ngoài mạng vào các nút hàng đợi tại bước n v1 (n) = ( 0, v11 (n), v12 (n), v13 (n), v14 (n), v15 (n),0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 ) v2 (n) = ( 0,0,0,0,0, v26 (n), v27 (n), v28 (n), v29 (n), v10 2 ( n),0,0,0,0,0,0,0,0,0,0,0,0 ) v3 (n) = ( 0,0,0,0,0,0,0,0,0, v311 ( n), v312 ( n), v313 ( n), v314 ( n), v315 ( n),0,0,0,0,0,0,0,0 ) v4 (n) = ( 0,0,0,0,0,0,0,0,0,0,0,0,0, v16 4 ( n), v4 ( n), v4 ( n), v4 ( n), v4 (n),0,0,0,0 ) 17 18 19 20 v5 (n) = ( 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, v521( n), v522 ( n), v523 (n), v524 (n), v525 (n) ) b. Lưu lượng dòng job đến các nút của mạng hàng đợi tại bước n J aic ( n ) = vic ( n ) +  j =1, j i:cL j bcj ( n − 1) p cji ( n − 1) víi c  Li , i = 1,5 . (2.21) c. Lưu lượng dòng job luân chuyển giữa các mạng thành phần tại bước n
14 ri d (n) =  aic (n)Sic ,d (n) d  Li , i = 1,5 . (2.22) cLi d. Lưu lượng dòng job tại các nút của hàng đợi tại bước n bic ( n ) = ric ( n ) + bic ( n − 1) pii (n − 1) c  Li , i = 1,5 . (2.23) e. Lưu lượng dòng job ra ngoài mạng hàng đợi tại bước n - Lưu lượng dòng job ra ngoài mạng tại nút 1: d1 (n) =  a1c (n) s1c (n) + b1c (n − 1) p1,0 c (n − 1) . (2.24) c1,6,11,16,21 - Lưu lượng dòng job ra ngoài mạng tại nút 2: d 2 ( n) =  c2,7,12,17,22 a2c (n) s2c (n) + b2c (n − 1) p2,0 c (n − 1) . (2.25) - Lưu lượng dòng job ra ngoài mạng tại nút 3: d 3 ( n) =  c3,8,13,18,23 a3c (n) s3c (n) + b3c (n − 1) p3,0 c (n − 1) . (2.26) - Lưu lượng dòng job ra ngoài mạng tại nút 4: d 4 ( n) =  c4,9,14,19,24 a4c (n) s4c (n) + b4c (n − 1) p4,0 c (n − 1) . (2.27) - Lưu lượng dòng job ra ngoài mạng tại nút 5: d 5 ( n) =  c5,10,15,20,25 a5c (n) s5c (n) + b5c (n − 1) p5,0 c (n − 1) . (2.28) Như vậy luận án đã thực hiện tính toán lưu lượng dòng job luân chuyển giữa các mạng thành phần tại mỗi nút và lưu lượng dòng job hiện có tại mỗi nút ở các bước qua đó thấy được quá trình luân chuyển dòng job trong mạng hàng đợi có 5 nút. 2.4. Xây dựng chương trình tính toán lưu lượng dòng job luân chuyển trong mạng hàng đợi Chương trình tính toán được thiết kế và xây dựng cho phép tạo lập một mạng hàng đợi với tổng số nút mạng tùy ý. Các tham số của mạng hàng đợi có thể tùy biến và cho phép lưu vào các tệp tin cấu hình cho phép tái sử dụng trong các lần chạy phần mềm thay vì phải thiết lập lại tham số mỗi khi chạy chương trình. Một số kết quả tính toán lưu lượng dòng job luân chuyển trong mạng được thể hiện trực quan dưới dạng biểu đồ thể hiện. Kết luận chương 2 Chương 2 nghiên cứu, đề xuất kỹ thuật phân rã và tổng hợp mạng hàng đợi trong đó kỹ thuật phân rã nhằm phân tách một mạng bất kỳ thành các mạng thành phần có hướng đơn giản hơn và kỹ thuật tổng hợp cho phép “chập” các mạng thành phần có hướng lại với nhau thành một mạng hàng đợi tổng quát cho trước. Với kỹ thuật phân rã và tổng hợp mạng này cho phép chúng ta nghiên cứu mạng hàng đợi tùy ý với các luồng job đa chiều được xem như là mạng “chập” (“chồng chất”) của các mạng thành phần có hướng
15 và từ cơ sở đó dẫn bài toán nghiên cứu mạng hàng đợi tùy ý về xét bài toán trên các mạng thành phần có hướng đơn giản hơn. CHƯƠNG 3 ĐÁNH GIÁ QUÁ TRÌNH TRẠNG THÁI CỦA MẠNG HÀNG ĐỢI DẠNG TỔNG QUÁT Nội dung của chương 3 sử dụng các kết quả đã được công bố trong bài báo [1] thuộc danh mục các công trình đã công bố. Đối với mạng hàng đợi, lớp bài toán nghiên cứu quá trình trạng thái của các nút mạng và của mạng hàng đợi là lớp bài toán vừa có ý nghĩa khoa học vừa có ý nghĩa thực tiễn đã và đang được nhiều tác giả trên thế giới quan tâm. Chương 3 nghiên cứu lớp bài toán này với điều kiện dòng job vào mạng là dòng tổng quát với phân phối bất kỳ và thời gian phục vụ job tại các nút mạng là biến ngẫu nhiên có phân phối bất kỳ. Cụ thể, mạng hàng đợi thỏa mãn giả thiết sau: Giả thiết 3.1. Mạng hàng đợi có J nút ( J  + ); mỗi nút có một trạm phục vụ; dòng job từ bên ngoài vào mạng hàng đợi là dòng tổng quát với phân phối bất kỳ; thời gian phục vụ job tại mỗi nút của mạng hàng đợi là biến ngẫu nhiên có phân phối bất kỳ và độc lập với nút khác; job sau khi được phục vụ xong tại nút i , job sẽ đến nút j để được phục vụ tiếp hoặc job ra ngoài mạng hàng đợi nếu job đã được phục vụ xong hoàn toàn (về mặt nguyên tắc job có thể quay trở lại nút i để được phục vụ tiếp); dòng job từ ngoài vào mạng độc lập với trạng thái của mạng; các dòng job luân chuyển giữa các nút độc lập với nhau và độc lập với trạng thái của nút đến. 3.1. Trạng thái và phương trình chuyển trạng thái của nút mạng 3.1.1. Định nghĩa, ký hiệu Gọi  n là thời điểm lần thứ n ( n = 0,1, 2,...) xuất hiện sự kiện job từ bên ngoài vào mạng hàng đợi hoặc job được phục vụ xong tại nút mạng nào đó (Xem định nghĩa 2.2 trong chương 2), trong đó  0 là thời điểm quan sát xuất phát ban đầu. a. Định nghĩa 3.1. Phân phối tựa nhị thức Cho n ( n  + ) biến ngẫu nhiên độc lập i | i = 1, n có phân phối A(qi ) và ký hiệu là i  A(qi ) (i = 1, n) (ở đây A(qi ) là phân phối của biến ngẫu nhiên n Bernoulli với tham số qi ). Đặt  = i khi đó  được gọi là biến ngẫu nhiên i =1 có phân phối tựa nhị thức và được ký hiệu   B(n; q1,..., qn ) . Tính chất: [ =k] =   ( qi ) (1 − qi ) .  1− i i (3.1) 1 +...+ n = k 0i  n 1 ,..., n 0,1
16 n n E ( ) =  qi và D ( ) =  qi (1 − qi ) . (3.2) i =1 i =1 Trong trường hợp đặc biệt khi qi = q i = 1, n , ta được phân phối nhị thức B(n; q) thông thường. b. Ký hiệu: - X j ( n ) là số job có trong nút j tại thời điểm  n và được gọi là trạng thái nút j tại thời điểm  n ( j = 1, J , n = 1, 2,...) . X ( n ) = ( X1 ( n ),..., X J ( n )) là trạng thái mạng hàng đợi tại thời điểm  n . - pij là xác suất job chuyển từ nút i sang nút j ( i = 1, J , j = 0, J ) , trong đó pi 0 là xác suất job được phục vụ xong tại nút i và ra khỏi mạng hàng đợi; pii là xác suất job vẫn còn tiếp tục được phục vụ tại nút i (trong chương này chúng ta xét xác suất chuyển (xác suất định tuyến) là không thay đổi theo thời gian). - N j là kích thước của hàng đợi tại nút j của mạng ( j = 1, J , N j  ); E j = 0,1,..., N j  . 3.1.2. Phương trình chuyển trạng thái của nút mạng Vì ij ( n ) là số job từ nút i ( i = 1, J ) chuyển sang nút j tại thời điểm  n do vậy tổng số job ra khỏi nút i tại thời điểm  n là: J d ( n ) =  j = 0, j  i ij ( n ) . (3.3) Từ giả thiết về mạng hàng đợi và từ định nghĩa về thời điểm  n khi đó ta có: ij ( n )  A( pij ) i = 1, J  d ( n )  A(1 − pii ) i = 1, J   J . (3.4)   ij ( n )  B( J − 1, p1 j ,..., p j −1, j , p j +1, j ,..., pJj ) i =1,i  j n = 0,1, 2,...  Ký hiệu Aj ( n ) là số job từ bên ngoài vào nút j trong khoảng thời gian  n = ( n−1 , n  . Khi đó số job có trong nút j tại thời điểm  n được xác định như sau: J J X j ( n ) = X j ( n −1 ) + Aj ( n ) −  i =0,i  j  ji ( n ) +  i =1,i  j ij ( n ) . (3.5) Công thức (3.5) chính là phương trình chuyển trạng thái tại nút j của mạng hàng đợi.
17 3.1.3. Phân phối xác suất chuyển trạng thái của nút mạng Ký hiệu Q j ( n ) = q j ( n−1 , xn−1 , n , xn )  x , x E trong đó n−1 n j q j ( n−1 , xn−1 , n , xn ) =  X j ( n ) = xn | X j ( n−1 ) = xn−1  là xác suất chuyển trạng thái của quá trình trạng thái tại nút j từ trạng thái xn−1 tại thời điểm  n−1 sang trạng thái xn tại thời điểm  n . Khi đó: - Nếu xn  xn−1 − 1 : q j ( n−1 , xn−1 , n , xn ) = 0 . (3.6) - Nếu xn = xn−1 − 1 : q j ( n−1, xn−1, n , xn ) = (1 − p jj )  (1 − p ) J ij  Aj ( n ) = 0 . (3.7) i =1,i  j - Nếu xn = xn−1 + k ( k  ) : mink , J −1   ( p ) (1 − p ) J i 1− i q j ( n−1 , xn−1 , n , xn ) = p jj  y =0 1 +...+ n = y i =1;i  j ij ij  Aj ( n ) = k − y  1 ,..., n 0,1 mink +1, J −1 + (1 − p jj )   ( p ) (1 − p ) J i 1− i  y =0 1 +...+ n = y i =1;i  j ij ij  Aj ( n ) = k + 1 − y  1 ,..., n 0,1 (3.8) Từ công thức (3.6), (3.7) và (3.8) ta có lược đồ chuyển trạng thái của ( X j ( n ) ) ; n = 0,1,... sau một bước như sau: 0 1 2 … m-1 m m+1 m+2 … m+k … Hình 3.1. Lược đồ chuyển trạng thái của quá trình trạng thái tại nút mạng 3.2. Phân phối và tính chất của quá trình trạng thái 3.2.1. Phân phối xác suất của trạng thái tại nút mạng sau một bước Giả sử rằng tại thời điểm  n−1 đã biết phân phối xác suất của X j ( n−1 ) khi đó từ phương trình chuyển trạng thái (3.5) và với m  E j ta có: m+1  X j ( n ) = m  =   X j ( n −1 ) = l H j (m, l , n) . (3.9) l =0 1 nÕu l  m Với g (m, l ) =  và 0 nÕu l > m  J  minm−l , J −1  J  H j (m, l , n) = g (m, l )    ji ( n ) = 0     ij ( n ) = y   Aj ( n ) = m − l − y  i =0,i  j  y =0  i =1,i  j  minm +1−l , J −1  J   J  +    ji ( n ) = 1    ij ( n ) = y   Aj ( n ) = m + 1 − l − y  i =0,i  j  y =0  i =1,i  j 
18 Nhận xét 3.1. Nếu biết được phân phối xác suất của trạng thái nút j tại thời điểm hiện tại và phân phối xác suất của dòng job từ bên ngoài mạng vào nút j , khi đó công thức (3.9) cho phép xác định được phân phối xác suất của trạng thái nút j ở bước sau. 3.2.2. Phân phối xác suất của trạng thái tại các nút mạng sau k bước Từ công thức (3.5) khi đó phân phối xác suất của trạng thái nút j sau k bước là: m+1 l +1 n+k l +1 n+2 [ X j ( n+k ) = m] =  H (m, ln+k , n+k )  H (ln+k , ln+k −1, n+k −1 )...  H (ln+2 , ln+1, n+1 ) [ X j ( n ) = ln+1] . (3.10) ln +k =0 ln + k −1 =0 ln +1 =0 Nhận xét 3.2. Nếu biết phân phối xác suất của trạng thái nút j ở thời điểm hiện tại và phân phối xác suất của dòng job từ bên ngoài mạng vào nút j , khi đó công thức (3.10) cho phép xác định được phân phối xác suất của trạng thái nút j sau k bước ( j = 1, J ). 3.2.3. Điều kiện để quá trình trạng thái nút mạng và mạng hàng đợi là Markov a. Điều kiện để quá trình trạng thái tại các nút mạng là quá trình Markov Định nghĩa 3.2. Ma trận ngẫu nhiên Ma trận P =  pij i , jE được gọi là ma trận ngẫu nhiên nếu các điều kiện sau được thỏa mãn: i) pij  0 i, j  E . (3.11) ii)  pij = 1 i  E . (3.12) jE Bổ đề 3.1. i) Nếu X =  X ( n )n=0,1,... là xích Markov xác định trên không gian trạng thái E thì ma trận xác suất chuyển trạng thái Q( n ) =  q( n−1, in−1, n , in )i ,i E là ma trận ngẫu n−1 n nhiên (trong đó q( n−1, in−1, n , in ) =  X ( n ) = in | X ( n−1 ) = in−1  ). ii) Giả sử Q( n ) =  q( n−1, in−1, n , in )i ,i E là ma trận ngẫu nhiên thì tồn tại một n−1 n xích Markov có không gian trạng thái E và nhận ma trận Q( n ) là ma trận xác suất chuyển. Ký hiệu: Q j ( n ) = q j ( n−1, in−1, n , in ) i ,i E với q j ( n−1, in−1, n , in ) =  X j ( n ) = in | X j ( n−1) = in−1  khi đó n−1 n j ta có định lý sau: Định lý 3.1. Với giả thiết 3.1 về mạng hàng đợi khi đó X j =  X j ( n )n=0,1,... là xích Markov xác định trên không gian trạng thái E j nếu và chỉ nếu: