TRẦN HUY HOÀNG
CHUYÊN NGÀNH: KỸ THUẬT ĐIỆN TỬ
MÃ SỐ : 60.52.70 TÓM TẮT LUẬN VĂN THẠC SĨ KỸ THUẬT HÀ NỘI - 2011
BỘ GIÁO DỤC VÀ ĐÀO TẠO TẬP ĐOÀN BƯU CHÍNH VIỄN THÔNG VIỆT NAM



Có thể tìm hiểu luận văn tại:
Thư viện Học viện Công nghệ Bưu chính Viễn thông

17

2. Hướng nghiên cứu tiếp theo
- Tiếp tục tìm hiểu, ứng dụng các phương pháp xử lý hàng đợi
retrial vào các mô hình khác nhau.
- Nghiên cứu, tìm hiểu thêm về các giải thuật để cải thiện hơn
nữa các giải pháp xử lý hàng đợi retrial.
3.5. KẾT LUẬN CHƯƠNG
Trong chương này, chúng ta đã phân tích đánh giá hiệu năng hệ
thống hàng đợi retrial sử dụng một số giải pháp xử lý của Domenech
và Tien Van Do. Thuật toán của Tien Van Do có độ chính xác và độ
ổn định số học cao. Đồng thời độ phức tạp thuật toán chỉ là O(c),
trong khi đó độ phức tạp thuật toán của Domenech nói riêng và
phương pháp hình học ma trận nói chung là O(c
3
). Độ phức tạp thuật
toán O(c) giúp cải thiện đáng kể thời gian tính toán cho hệ thống

Do sự phát triển về số lượng thuê bao cũng như độ phức tạp của
hệ thống viễn thông, nên hành vi của khách hàng nói chung và hành
động yêu cầu lại dịch vụ nói riêng có ảnh hưởng lớn tới hiệu năng
mạng. Chúng ta có thể tìm thấy nhiều ví dụ về ảnh hưởng của hàng
đợi retrial đến mạng viễn thông, như trong các mạng vô tuyến (quá
trình chuyển giao, cấp phát kênh), trong mạng Internet (quá trình
truyền dữ liệu)… Vì vậy việc đánh giá và cải thiện hiệu năng của hệ
thống hàng đợi retrial đóng vai trò hết sức quan trọng trong việc thiết
kế cũng như vận hành các hệ thống viễn thông.
Với mục đích đánh giá và cải thiện hiệu năng của hệ thống
hàng đợi retrial, tôi chọn đề tài “Nghiên cứu cải thiện phương pháp
xử lý hàng đợi retrial”. Luận văn sẽ trình bày những nội dung tổng
quan về lý thuyết hàng đợi, về mô hình chuỗi Markov hai chiều, về
mô hình hàng đợi Giả sinh tử, các mô hình và phương pháp xử lý
hàng đợi. Cuối cùng, luận văn sẽ phân tích, đánh giá và so sánh hiệu
năng của một số giải pháp xử lý hàng đợi retrial

Chương 1
TỔNG QUAN VỀ QUÁ TRÌNH GIẢ SINH TỬ
Chương 1 giới thiệu chung về quá trình giả sinh tử và ứng dụng,
sự cần thiết của nó trong một số trường hợp hàng đợi. Trong chương
này cũng đề cập tới một số phương pháp để giải quyết các quá trình
giả sinh tử vô hạn và hữu hạn.
1.1. GIỚI THIỆU VỀ QUÁ TRÌNH GIẢ SINH TỬ
Ngày nay, rất nhiều vấn đề về tính toán hiệu năng của hệ thống
viễn thông được giải quyết bởi mô hình chuỗi Markov hai chiều. Đặc
điểm chung của các chuỗi dạng này là mỗi trạng thái được xác định
bởi một cặp giá trị: pha và mức. Trong một số trường hợp, chỉ có thể
chuyển các mức gần nhau, trường hợp này là một mô hình hàng đợi
có tên QBD (Quasi Birth – Death: Quá trình giả sinh tử). Khái niệm

3.5
4
4.5
5
mur = 0.001, rho = 1.2
Q
Number of iterations
HM1 METHOD
NEW ALGORITHM

Ảnh hưởng của Q tới số bước lặp của thuật toán cải tiến
3.4.2. Thời gian xử lý
0 50 100 150 200 250 300 350 400
0
1
2
3
4
5
6
Number of servers (c)
Processed time (s)
Q = 50, mur = 0.01, rho = 0.8
HM1 METHOD
NEW ALGORITHM

So sánh thời gian xử lý của 2 thuật toán

Ảnh hưởng của Q đến P
ns

1.3. CÁC PHƯƠNG PHÁP TÍNH TOÁN CHO QUÁ TRÌNH
GIẢ SINH TỬ VÔ HẠN
1.3.1. Phương pháp mở rộng phổ
1.3.2. Phương pháp hình học ma trận
1.3.3. Phương pháp giảm bậc logarit của Latouche
1.3.4. Thuật toán của Naoumov
1.3.5. Phương pháp dựa trên không gian con bất biến
1.4. CÁC PHƯƠNG PHÁP TÍNH TOÁN CHO QUÁ TRÌNH
GIẢ SINH TỬ HỮU HẠN
1.4.1. Phương pháp mở rộng phổ
1.4.2. Phương pháp ma trận hình học, phương pháp của
Latouche và Naoumov
1.4.3. Phương pháp dựa trên không gian con bất biến
1.5. KẾT LUẬN CHƯƠNG
Trong chương này, chúng ta đã đề cập tới một thể loại của chuỗi
Markov, đó là quá trình Giả sinh tử (QBD). Ứng dụng của các quá
trình QBD được sử dụng rộng rãi trong việc phân tích các hệ thống
máy tính và các mạng viễn thông. Chương này cũng đã đưa ra một số
phương pháp xử lý gần đây cho việc phân tích trạng thái ổn định của
các quá trình QBD, nhưng chỉ dừng lại ở mức độ tổng quát nhằm
giúp người đọc có cái nhìn tổng quát về QBD.

Chương 2
CÁC GIẢI PHÁP XỬ LÝ MÔ HÌNH HÀNG ĐỢI
RETRIAL
Chương 2 giới thiệu về một số giải pháp xử lý hàng đợi retrial
điển hình. Đồng thời cũng đưa ra một số nhận xét đánh giá về các
giải pháp đó.
2.1. GIỚI THIỆU CHUNG
Chúng ta cùng xem xét một giả thiết sau: một khách hàng không

Xác suất P
b
tính được:
ρ μ
r
= 0.001 μ
r
= 0.01 μ
r
= 0.1 μ
r
= 1.0
0.4 7.66E-09 7.95E-09 9.30E-09 9.36E-09
0.6 0.000226 0.000257 0.000338 0.000305
0.8 0.025483 0.033178 0.039943 0.028972
1.0 0.245153 0.332842 0.273456 0.171808
1.2 0.298224 0.636863 0.543641 0.354119
1.4 0.332074 0.750309 0.702754 0.503247
Xác suất N
ret
tính được:
ρ μ
r
= 0.001 μ
r
= 0.01 μ
r
= 0.1 μ
r
= 1.0

chỉ tập trung vào từng cell riêng biệt có thể phục vụ được N kết nối
cùng lúc, và giả thiết rằng các kết nối trong các cell khác nhau không
ảnh hưởng tới các cell khác.
Thông thường, trong hệ thống điện thoại di động tổ ong sẽ có
một số kênh dự phòng để tránh chuyển giao thất bại. Điều đó có
nghĩa là, nếu N
H
kênh được dành cho chuyển giao, các yêu cầu cho
cuộc gọi mới chỉ được phục vụ khi có nhiều hơn N
H
kênh rỗi, trong
khi đó các yêu cầu chuyển giao được phục vụ khi có một số kênh còn
rỗi.
Như vậy, các yêu cầu có thể tới cell đó có thể do 4 lý do: cuộc
gọi mới, chuyển giao vào cell, yêu cầu retrial từ các thuê bao có yêu
cầu cuộc gọi mới không được chấp thuận, và yêu cầu retrial từ các
thuê bao có yêu cầu chuyển giao không được chấp thuận (hai lý do
cuối đều là yêu cầu của các thuê bao nằm trong hàng đợi).
2.2.3. Giải pháp Domenech
Domenech Benloch giới thiệu một phương pháp tiếp cận để xử
lý hàng đợi retrial có xét tới sự không kiên nhẫn của khách hàng. Mô
hình của họ không xét tới các cuộc gọi do chuyển giao và các kênh
bảo vệ, tuy nhiên phương pháp tính toán cũng được sử dụng trong
trường hợp có chuyển giao và kênh bảo vệ.
Hệ thống có C server. Người sử dụng yêu cầu dịch vụ tuân theo
phân bố Poisson với tốc độ λ, và yêu cầu thời gian phân bố dịch vụ
với tốc độ µ. Như vậy, tải của hệ thống bằng ρ = λ/(Cµ). Thông
thường, nếu không bị mất mát dữ liệu, coi rằng mỗi người dùng
chiếm dụng một server. Khi có một yêu cầu mới mà tất cả các server
đã bị chiếm dụng, nó sẽ quay lại hàng đợi retrial với xác suất bằng 1

bình trong hàng đợi retrial (N
ret
), xác suất dịch vụ thức thì (P
is
), xác
suất trễ dịch vụ (P
ds
) và xác suất không có được dịch vụ (P
ns
). P
is
là
không chiếm được kênh của cuộc gọi mới và cuộc gọi do chuyển
giao trong mạng di động tổ ong. Tác giả đưa ra giả thiết rằng số
lượng thuê bao trung bình trong hàng đợi có phân bố hình học. Tuy
nhiên, giả thiết này chỉ có giá trị khi không có kênh bảo vệ nào trong
hệ thống.
Giải pháp do Domenech đưa ra có thể xử lý được vấn đề hàng
đợi retrial có tính đến sự thiếu kiên nhẫn của thuê bao. Mô hình mà
Domenech đưa ra không xem xét tới các cuộc gọi do chuyển giao và
không xét tới khái niệm về kênh bảo vệ. Tuy nhiên thời gian tính
toán của phương pháp này tăng nhanh theo số lượng kênh.
Giải pháp do Tien Van Do tập trung vào việc xử lý độ ổn định
số học, tính chính xác trong trường hợp dung lượng hệ thống lớn. Mô
hình hàng đợi sử dụng trong giải pháp này là sự kết hợp giữa các
phân bố hình học và khái niệm về các kênh bảo vệ.
Giải pháp cải tiến của Tien Van Do dựa trên đặc tính toán học
của phương pháp mở rộng phổ, và cải thiện phương pháp xấp xỉ để
tính M. Nhưng đóng góp lớn nhất của giải pháp này là đơn giản hóa
được việc tính ma trận tốc độ R bằng thuật toán đệ quy, làm cho độ

H
thì cell đó chỉ chấp nhận
thêm một cuộc gọi cho chuyển giao.
 Một cuộc gọi mới bị đưa vào hàng đợi do thiếu tài nguyên
hoặc do chính sách cấp phát tài nguyên (ví dụ như các kênh
bảo vệ) sẽ yêu cầu lại dịch vụ với xác suất θ và với tốc độ
α
0
. Rõ ràng, ở đây θ chỉ thị mức độ kiên nhẫn của thuê bao.
 Các cuộc gọi do chuyển giao sẽ không vào hàng đợi (tức là
các cuộc gọi do chuyển giao sẽ bị từ chối dịch vụ hoàn toàn
khi không có tài nguyên để cấp phát).
 Các cuộc gọi mới (không phải các cuộc gọi phát sinh từ hàng
đợi) chỉ có thể chiếm các kênh bình thường (không phải
kênh bảo vệ).
 Các thuê bao trong hàng đợi yêu cầu lại dịch vụ, và vẫn
không chiếm được kênh sẽ yêu cầu lại lần nữa với xác suất
θ.
 Các cuộc gọi retrial chỉ có thể chiếm các kênh bảo vệ.
2.2.5. Giải thuật cải tiến của Tien Van Do
Trước hết, định nghĩa các tham số như sau: Thời gian các thuê
bao tới hệ thống có phân bố hàm mũ với tốc độ λ, thời gian chiếm
kênh cũng có phân bố hàm mũ với tốc độ μ, số lượng server là c.
Biến ngẫu nhiên I(t) là số lượng server bị chiếm dụng tại thời điểm t
(và do đó 0 ≤ I(t) ≤ c). Thuê bao khi không chiếm dụng được server
sẽ bị đưa vào hàng đợi (do số lượng server có hạn). Gọi J(t) là số thuê
bao trong hàng đợi tại thời điểm t. Mỗi thuê bao từ hàng đợi retrial sẽ
yêu cầu lại dịch vụ với tốc độ μ
r
, do vậy tốc độ yêu cầu dịch vụ tại

thái này là do có thuê bao mới vào chiếm được kênh, hoặc
do một thuê bao rời khỏi hệ thống sau khi kết thúc thời gian
chiếm kênh của mình. Ma trận A
j
có kích thước (c + 1)×(c +
1) với các phần tử A
j
(i, k). Vì A
j
là không phụ thuộc vào j,
nên có thể viết lại thành A
j
= A với mọi j. Các phần tử khác
0 của A
j
là A
j
(i, i – 1) = iμ với i = 1, …, c+1; và A
j
(i, i + 1) =
λ với i = 0, …, c.
9

 B
j
(i, k): ma trận chuyển đổi trạng thái từ (i, j) sang (k, j + 1)
(0 ≤ i, k ≤ c; j = 0, 1, …). Nguyên nhân của việc chuyển đổi
trạng thái này là do có một thuê bao yêu cầu kênh khi tất cả
các server đều bận, do đó thuê bao này bị đưa vào hàng đợi,
J(t) tăng lên 1. Ma trận B

j
(c, c) = P
i
µ
j
trong đó P
i
là xác suất thuê
bao rời khỏi hệ thống sau khi retrial không thành công. Với j ≥ N, ta
có µ
j
= ν = Nµ
r
, do vậy C
j
sẽ không đổi khi j ≥ N, và giả sử C
j
= C
với mọi j ≥ N. Chú ý rằng C
0
= 0 theo định nghĩa ma trận C.
2.3. MỘT SỐ NHẬN XÉT ĐÁNH GIÁ
Phước Trần Gia đưa ra mô hình hàng đợi retrial để tính toán
hiệu năng của mạng di động tổ ong có xét tới khái niệm kênh bảo vệ,
cuộc gọi mới và cuộc gọi do chuyển giao. Tác giả đã sử dụng một
thuật toán đệ quy để tính các xác suất không gian trạng thái. Tuy
nhiên, khi đưa vào ảnh hưởng của các kênh bảo vệ, các kết quả trong
thuật toán đệ quy sẽ có dấu âm. Các kết quả có dấu âm và các giá trị
cực nhỏ sẽ dẫn tới sự mất ổn định số học trong thuật toán đệ quy.
Ajmone Marsan đưa ra mô hình xấp xỉ sử dụng chuỗi Markov