Giáo trình Cơ sở mạng thông tin
Cơsởmạng thông tin
Giáo trình dành cho sinh viên đại học ngành
Điện tử - Viễn thông
Nguyễn Hữu Thanh
Nguyễn Thanh Sơn
Nguyễn Xuân Dũng
Phạm Văn Tiến
Lê Nhật Thăng
Chủ biên: Nguyễn Hữu Thanh
Khoa Điện tử Viễn Thông
Trường Đại học Bách khoa Hà nội
2
Các từ viết tắt
Đầy đủ
Viết tắt
CDF
Cumulative distribution function
First-come-first-server
First in first out
Last-come-first-serve
Last in first out
Probability density function
Probability distribution function
FCFS
FIFO
LCFS
LIFO
pdf
PDF
3
Bảng đối chiếu thuật ngữAnh - Việt
Tiếng Anh
Tiếng Việt
Analysis
Phân tích
Arrival process
Tiến trình tới
Base station
Trạm gốc
Biominal distribution
Binomial process
Birth – Death Process
Derparture process
Evaluation
Phân bố nhị thức
Tiến trình nhị thức
Tiến trình sinh tử
Tiến trình đi
Đánh giá
Expectation
Kỳ vọng
Exponential distribution
First in first out / First-come-first-serve
Formal description
Frequency function
Gaussian distribution
Inter-arrival time
Last in first out / Last-come-first-serve
Load
Phân bố mũ
Vào trước phục vụ trước
Mô tả hình thức
Hàm tần suất
Phân bố chuẩn/phân bố Gauss
Thời gian giữa hai sự kiện tới (?)
Vào sau phục vụ trước
Tải
Model
Mô hình
Modeling
Mô hình hóa
Performance
Probability
Đặc tính/chất lượng hoạt động
Xác suất
Probability density function
Probability distribution function
Random experiment
Random event
Random variable
Scale parameter
Server
Service process
Shape parameter
Simulation
Hàm mật độ xác suất
Hàm phân phối xác suất
Phép thử ngẫu nhiên
Sự kiện ngẫu nhiên
Biến ngẫu nhiên
Tham số tỷ lệ
Trạm phục vụ/Server
Tiến trình phục vụ
Tham số hình dạng
Mô phỏng
4
Standard deviation
Steady state
Độ lệch chuẩn
Trạng thái ổn định
Tiến trình ngẫu nhiên
Mật độ lưu lượng
Biến đổi
Stochastic process
Traffic intensity
Transformation
Uniform distribution
Utilization
Phân bố đều
Hiệu suất kênh
Kiểm định tính chính xác
Phương sai
Validation
Variance
5
Mục lục
Các từ viết tắt _________________________________________________________________________ 3
Bảng đối chiếu thuật ngữ Anh - Việt ______________________________________________________ 4
Mục lục _____________________________________________________________________________ 6
Mục lục hình vẽ_______________________________________________________________________ 9
Mục lục bảng biểu____________________________________________________________________ 10
Chương 1 Giới thiệu ___________________________________________________________________ 1
1.1. Mục đích của việc mô hình hóa và đánh giá đặc tính hoạt động của hệ thống _______________________ 1
1.2. Các tham số, tiêu chuẩn và phương pháp đánh giá một hệ thống thông tin _________________________ 3
1.2.1. Các tham số đánh giá đặc tính hoạt động của hệ thống thông tin___________________________________________ 3
1.2.2. Các tiêu chuẩn đánh giá__________________________________________________________________________ 3
1.2.3. Các phương pháp đánh giá _______________________________________________________________________ 4
Chương 2 Các tiến trình ngẫu nhiên ______________________________________________________ 6
2.1. Xác suất và sự kiện _______________________________________________________________________ 6
2.1.1. Phép thử và sự kiện ngẫu nhiên____________________________________________________________________ 6
2.1.2. Xác suất______________________________________________________________________________________ 6
2.2. Biến ngẫu nhiên và các hàm xác suất_________________________________________________________ 7
2.2.1. Biến ngẫu nhiên________________________________________________________________________________ 7
2.2.2. Hàm mật độ và phân phối xác suất _________________________________________________________________ 8
2.2.3. Hàm tần suất và phân phối xác suất của biến ngẫu nhiên rời rạc __________________________________________ 10
2.2.4. Các tham số đặc trưng của biến ngẫu nhiên__________________________________________________________ 12
2.3. Các mô hình phân bố xác suất cơ bản _______________________________________________________ 14
2.3.1. Phân bố Bernoulli (Bernoulli distribution)___________________________________________________________ 14
2.3.2. Phân bố nhị thức (binomial distribution) ____________________________________________________________ 15
2.3.3. Phân bố chuẩn (Gaussian distribution) _____________________________________________________________ 16
2.3.4. Phân bố mũ (exponential distribution)______________________________________________________________ 17
2.3.5. Phân bố Poisson (Poinsson distribution) ____________________________________________________________ 17
2.3.6. Phân bố Gamma (Gamma distribution)_____________________________________________________________ 18
2.3.7. Mối liên hệ giữa phân bố mũ và phân bố Gamma_____________________________________________________ 19
2.4. Tiến trình ngẫu nhiên (stochastic process) ___________________________________________________ 20
2.4.1. Khái niệm và định nghĩa ________________________________________________________________________ 20
2.4.2. Phân loại ____________________________________________________________________________________ 21
2.5. Các đặc tính thông kê của tiến trình ngẫu nhiên ______________________________________________ 22
2.5.1. Các hàm quan hệ xác suất _______________________________________________________________________ 22
2.5.2. Các trung bình thống kê_________________________________________________________________________ 23
2.5.3. Tính dừng ___________________________________________________________________________________ 24
2.6. Các tiến trình ngẫu nhiên thường gặp_______________________________________________________ 27
2.6.1. Tiến trình đếm________________________________________________________________________________ 27
2.6.2. Tiến trình Poisson _____________________________________________________________________________ 28
2.7. Kết luận _______________________________________________________________________________ 28
Chương 3 Hệ thống hàng đợi ___________________________________________________________ 29
3.1. Giới thiệu ______________________________________________________________________________ 29
3.2. Mô hình hàng đợi – Ký hiệu Kendall________________________________________________________ 29
3.2.1. Mô hình hàng đợi đơn __________________________________________________________________________ 29
6
3.2.2. Ký hiệu Kendall ______________________________________________________________________________ 31
3.2.3. Các tham số quan trọng để đánh giá đặc tính của hệ thống hàng đợi_______________________________________ 32
3.3. Hệ thống hàng đợi ở trạng thái ổn định – Định lý Little ________________________________________ 33
3.3.1. Hệ thống hàng đợi ổn định ______________________________________________________________________ 33
3.3.2. Định lý Little _________________________________________________________________________________ 35
3.3.3. Một số đặc tính khác của hệ thống đóng, hoạt động ở trạng thái ổn định____________________________________ 37
3.4. Hàng đợi M/M/1/1 _______________________________________________________________________ 38
3.5. Hàng đợi M/M/1/∞ ______________________________________________________________________ 41
3.5.1. Xác suất có n yêu cầu trong hệ thống ______________________________________________________________ 41
3.5.2. Tính toán các tham số hiệu năng __________________________________________________________________ 43
3.6. Tiến trình sinh – tử (Birth – Death Process) __________________________________________________ 46
3.7. Hàng đợi M/M/1/K ______________________________________________________________________ 46
3.7.1. Xác suất có n yêu cầu trong hệ thống ______________________________________________________________ 47
3.7.2. Tính toán các tham số hiệu năng __________________________________________________________________ 47
3.8. Hàng đợi M/M/c/∞_______________________________________________________________________ 51
3.8.1. Xác suất có n yêu cầu trong hệ thống ______________________________________________________________ 51
Chương 4 Mạng hàng đợi______________________________________________________________ 52
4.1. Mạng nối tiếp ___________________________________________________________________________ 52
Chương 5 Định tuyến trong mạng thông tin _______________________________________________ 53
5.1. Yêu cầu về định tuyến trong mạng thông tin _________________________________________________ 53
5.1.1. Vai trò của định tuyến trong mạng thông tin _________________________________________________________ 53
5.1.2. Các khái niệm trong lý thuyết graph _______________________________________________________________ 53
5.2. Các mô hình định tuyến quảng bá (broadcast routing)_________________________________________ 55
5.2.1. Lan tràn gói (flooding) _________________________________________________________________________ 55
5.2.2. Định tuyến bước ngẫu nhiên (random walk) _________________________________________________________ 56
5.2.3. Định tuyến khoai tây nóng (hot potato) _____________________________________________________________ 56
5.2.4. Định tuyến nguồn (source routing) và mô hình cây (spanning tree) _______________________________________ 57
5.2.5. Duyệt cây ___________________________________________________________________________________ 57
5.3. Các mô hình định tuyến thông dụng ________________________________________________________ 78
5.3.1. Định tuyến ngắn nhất (Shortest path Routing)________________________________________________________ 78
5.4. Bài tập (Pending) _______________________________________________________________________ 101
Chương 6 Điều khiển luồng và chống tắc nghẽn __________________________________________ 102
6.1. Tổng quan_____________________________________________________________________________ 102
6.1.1. Mở đầu ____________________________________________________________________________________ 102
6.1.2. Khái niệm điều khiển luồng_____________________________________________________________________ 105
6.1.3. Khái niệm chống tắc nghẽn _____________________________________________________________________ 106
6.1.4. Nhiệm vụ chủ yếu của điều khiển luồng và chống tắc nghẽn ___________________________________________ 106
6.1.5. Phân loại điều khiển luồng và tránh tắc nghẽn_______________________________________________________ 107
6.2. Tính công bằng_________________________________________________________________________ 108
6.2.1. Định nghĩa__________________________________________________________________________________ 108
6.2.2. Tính công bằng về mặt băng truyền_______________________________________________________________ 108
6.2.3. Tính công bằng về mặt bộ đệm __________________________________________________________________ 109
6.2.4. Cơ chế phát lại ARQ __________________________________________________________________________ 110
6.2.5. Stop-and-Wait ARQ __________________________________________________________________________ 111
6.2.6. Go-back-N ARQ _____________________________________________________________________________ 117
6.2.7. Selective repeat ARQ _________________________________________________________________________ 124
6.3. Điều khiển luồng và tránh tắc nghẽn theo phương pháp cửa sổ_________________________________ 126
6.3.1. Điều khiển luồng theo cửa sổ (Window Flow Control)________________________________________________ 127
6.3.2. Điều khiển tắc nghẽn sử dụng cửa sổ thích ứng (adaptive window) ______________________________________ 132
6.4. Điều khiển luồng và chống tắc nghẽn dựa trên băng thông (rate-based flow control) _______________ 138
6.4.1. Khái niệm __________________________________________________________________________________ 138
7
6.4.2. Điều khiển băng thông theo thuật toán gáo rò (leaky bucket) ___________________________________________ 139
6.4.3. Thuật toán GPS (pending)______________________________________________________________________ 143
6.5. Bài tập (Pending) _______________________________________________________________________ 144
Chương 7 Kỹ thuật mô phỏng__________________________________________________________ 145
7.1. Giới thiệu _____________________________________________________________________________ 145
7.2. Mô phỏng dựa trên các sự kiện rời rạc và các công cụ ________________________________________ 145
7.2.1. Phương pháp mô phỏng dựa trên sự kiện rời rạc _____________________________________________________ 145
7.2.2. Các công cụ mô phỏng thông dụng dựa trên sự kiện rời rạc ____________________________________________ 148
7.3. Công cụ mô phỏng mạng NS2 ____________________________________________________________ 149
7.3.1. Cấu trúc____________________________________________________________________________________ 149
7.3.2. Các tiện ích trong NS hỗ trợ cho mô phỏng mạng [Pending] ___________________________________________ 151
7.3.3. Thí dụ (Pending) _____________________________________________________________________________ 151
7.4. Kết luận (Pending)______________________________________________________________________ 151
7.5. Bài tập (Pending) _______________________________________________________________________ 152
Tài liệu tham khảo___________________________________________________________________ 153
Phụ lục 1 __________________________________________________________________________ 155
8
Mục lục hình vẽ
Hình 1-1. Các bước cơ bản trong mô hình hóa và đánh giá đặc tính hệ thống
3
Hình 2-1. Hàm mật độ xác suất...................................................9
Hình 2-2.Hàm phân phối xác suất...............................................9
Hình 2-3: Kết quả Thí dụ 2-5 .....................................................11
Hình 3-1. Hệ thống hàng đợi với N trạm phục vụ, hàng đợi có độ lớn K 30
Hình 3-2. Round robin................................................................32
Hình 3-3. Mạng đóng .................................................................33
Hình 3-4. Quan hệ giữa số yêu cầu tới và số yêu cầu được phục vụ
36
Hình 3-5.Hệ thống hàng đợi được quan sát với hai ranh giới khác nhau: (a) Hàng đợi và các trạm phục
vụ; (b) Hàng đợi ..................................................................38
Hình 3-6. Hàng đợi M/M/1/1 ......................................................39
Hình 3-7. Khoảng thời gian xét..................................................39
Hình 3-8. Hàng đợi M/M/1/∞......................................................41
Hình 3-9. Cân bằng xác suất tại trạng thái i. Tiến trìnhsinh – tử46
Hình 3-10. Hệ thống M/M/1/K....................................................46
Hình 3-11. Hệ thống hàng đợi M/M/1/K.....................................47
Hình 3-12. Hệ thống M/M/1/K trên quan điểm hệ thống đóng..50
Hình 3-13 Hàng đợi M/M/c/∞.....................................................51
Hình 5-1. Hàng chờ bên trong router.........................................57
Hình 5-2. Duyệt cây ...................................................................58
Hình 5-3. Các thành phần..........................................................62
Hình 5-4. Phép tính Minimum Spanning Tree ( MST)...............70
9
Mục lục bảng biểu
Bảng 2-1. Điểm tương ứng với kết quả tung xúc xắc.................7
Bảng 2-2: Kết quả Thí dụ 2-5.....................................................11
10
Chương 1 Giới thiệu
1.1. Mục đích của việc mô hình hóa và đánh giá đặc tính hoạt động của hệ thống
Trong thực tế, khi khảo sát các hệ phục vụ nói chung, các hệ thống
máy tính và viễn thông nói riêng, hoặc khi nghiên cứu đưa ra các cơ
chế hoạt động mới trong các hệ thống này, một yêu cầu hàng đầu là
phải khảo sát các đặc tính và hiệu năng hoạt động của các hệ thống,
cơ chế đó.
Thí dụ 1-1:
Một nhà cung cấp dịch vụ điện thoại di động GSM muốn mở rộng
vùng phủ sóng của mình. Với các tham số đầu vào cho trước bao
gồm:
• Lưu lượng đầu vào λ, được tính bằng số yêu cầu kết nối trong
một đơn vị thời gian. Tham số này được khảo sát và đo đạc
thực tế tại vùng cần mở rộng.
• Thời gian trung bình của một cuộc gọi di động µ. Tham số này
đã biết trước dựa trên các dữ liệu thống kê của nhà cung cấp
dịch vụ.
• Tải tối đa u của một trạm gốc (base station), chính là số cuộc
gọi tối đa mà trạm gốc có thể cho phép tại một thời điểm.
• Yêu cầu xác suất từ chối dịch vụ tối đa p. Đây là xác suất một
yêu cầu kết nối bị từ chối do trạm gốc không đủ tài nguyên cung
cấp cho cuộc gọi đó.
Từ các yêu cầu đầu vào, nhà cung cấp cần phải tính toán có bao nhiêu
trạm gốc cần phải lắp đặt mới tại vùng đó, để xác suất từ chối dịch vụ
nhỏ hơn p.
Thí dụ 1-2:
Mạng Ethernet có N máy tính, tổng lưu lượng đầu vào đo được là
λ (Mbit/s). Kênh truyền có dung lượng là C (Mbit/s). Phải tính toán hiệu
suất hoạt động của kênh truyền (tính bằng % của lưu dung lượng C),
trễ trung bình (tính bằng s) của một gói tin khi được truyền từ nguồn tới
đích.
Tuy nhiên, quá trình phân tích một hệ thống thực thông thường tương
đối khó khăn và tốn kém. Để khẳng định tính chất của một hệ thống về
hiệu năng hoạt động, tính kinh tế .v.v., thông thường người ta thường
sử dụng các mô hình để miêu tả các hệ thống đó.
Định nghĩa 1-1: Mô hình (model) thông thường là sự đơn giản
hóa một hệ thống thực bằng cách miêu tả các hoạt động và trạng
thái của hệ thống đó cùng với các điều kiện khởi đầu và điều kiện
bờ cho trước.
Mục đích của việc mô hình hóa là nó cho phép đánh giá đặc tính, từ
đó cải thiện chất lượng hoạt động của một hệ thống. Để các thí
nghiệm với mô hình cho ra kết quả chính xác và đáng tin cậy, các dữ
liệu đầu vào của mô hình phải phù hợp với hệ thống thực tế.
Các bước trong quá trình mô hình hóa và đánh giá đặc tính hoạt động
của một hệ thống bao gồm:
•
Mô hình hóa (modeling): được hiểu là quá trình trừu tượng
hóa và đơn giản hóa một hệ thống thực bằng cách bỏ qua các
yếu tố không quan trọng và chỉ tập trung vào một tập hợp hữu
hạn các thông số đáng chú ý được sử dụng để miêu tả hệ
thống. Một điều khó khăn ở bước này là xác định các yếu tố có
thể bỏ qua và các thông số bắt buộc phải được xem xét. Vì vậy
độ chính xác của một mô hình phụ thuộc rất nhiều vào bước
này.
Thông thường có hai phương pháp mô hình hóa là mô hình toán
học và mô hình mô phỏng (xem 1.2.3).
•
•
•
Phân tích (analysis): Được hiểu là quá trình tìm hiểu, khám
phá các đặc điểm hoặc chức năng của hệ thống. Trong bước
này, đặc điểm hoặc phản ứng của một hệ thống sẽ được
nghiên cứu tương ứng với các thông số đầu vào cho trước.
Đánh giá và so sánh (evaluation and comparison): Đặc tính
của một hệ thống với các thông số đầu vào khác nhau sẽ được
kiểm tra và so sánh, thông qua đó có thể đánh giá tính chính
xác của mô hình (validation).
Đưa kết quả đánh giá về hệ thống thực: Các kết quả
được đưa ra từ các bước trên được đưa trở về phục vụ cho hệ
thống thực (thí dụ như để cải thiện chất lượng hoạt động .v.v.).
Hình 1-1 mô tả quá trình đánh giá đặc tính hoạt động hệ thống.
2
Hình 1-1. Các bước cơ bản trong mô hình hóa và đánh giá đặc tính hệ
thống
1.2. Các tham số, tiêu chuẩn và phương pháp đánh giá một hệthống thông tin
1.2.1. Các tham số đánh giá đặc tính hoạt động của hệ thống thông tin
Để đánh giá đặc tính hoạt động của một hệ thống, cần phải lựa chọn
các tham số của mô hình. Các tham số này có thể được phân loai
như sau:
Các tham số liên quan đến thời gian:
• Thời gian hệ thống thực hiện một yêu cầu
• Thời gian đáp ứng của hệ thống.
• Thời gian một yêu cầu lưu lại trong hệ thống .v.v.
Các tham số liên quan đến không gian:
•
Độ lớn của hàng đợi hệ thống (độ lớn bộ đệm .v.v.)
• Yêu cầu về bộ nhớ cho một chương trình .v.v.
Các tham số khác:
• Thông lượng
• Giá thành .v.v.
1.2.2. Các tiêu chuẩn đánh giá
Như chúng ta đã biết, trong quá trình mô hình hóa người ta chỉ giới
hạn xem xét một số thông số quan trọng của hệ thống. Vì vậy kết luận
về đặc tính hoạt động của một hệ thống nào đó bao giờ cũng có dạng:
“Hệ thống A tốt hơn hệ thống B về mặt C”
Việc kết luận chung chung theo kiểu “hệ thống A tốt hơn hệ thống B”
thông thường không chính xác do khi xét theo một tiêu chuẩn đánh giá
nào đó, một hệ thống có thể tối ưu nhưng khi xét theo một tiêu chuẩn
khác, hệ thống đó lại có những nhược điểm đáng kể.
Thí dụ 1-3:
Sau đây là một thí dụ về việc chọn tham số mô hình, quy tắc phục vụ
và các tiêu chuẩn đánh giá:
Tham số mô hình:
• Tham số lưu lượng của yêu cầu đến một hệ thống.
• Tham số đặc trưng cho thời gian phục vụ một yêu cầu.
• Số trạm phục vụ các yêu cầu
Quy tắc phục vụ:
3
• FIFO, LIFO
• Hàng đợi có ưu tiên
Các tiêu chuẩn đánh giá:
• Thời gian lưu lại hệ thống trung bình của một yêu cầu.
• Thời gian chờ đợi của một yêu cầu trong hàng đợi.
• Thông lượng của hệ thống.
• Tải của hệ thống.
1.2.3. Các phương pháp đánh giá
Phương pháp phân tích toán học (mathematical analysis)
Phương pháp phân tích toán học thực hiện các bước sau:
• Mô tả hình thức (formal description) một hệ thống.
•
Định nghĩa các mối quan hệ trong hệ thống, mô tả chúng bằng
các công thức, mô hình toán học.
• Tính toán dựa vào mô hình toán học vừa lập.
Trong quyển sách này chúng tôi chủ yếu tập trung vào phương pháp
này.
Phương pháp xấp xỉ (approximation method)
Trong nhiều trường hợp, phương pháp phân tích toán học quá phức
tạp để có thể mô tả một hệ thống. Phương pháp xấp xỉ cơ thể áp dụng
trong những trường hợp này.
Phương pháp mô phỏng (simulative techniques)
Mô phỏng miêu tả một quá trình xảy ra trong thực tế thông qua các
chương trình máy tính. Mô phỏng sử dụng cở sở xác suất thống kê để
đánh giá đặc tính hoạt động của một hệ thống từ các kết quả thí
nghiệm thu được, thí dụ như giá trị kỳ vọng, phương sai, các phân bố
ngẫu nhiên của kết quả .v.v.
Mô phỏng có ưu điểm là việc xây dựng, phân tích và đánh giá dễ dàng
hơn so với phương pháp toán học. Trong nhiều trường hợp, mô phỏng
là phương pháp khả thi nhất về mặt thời gian và tài chính (không phải
mua một hệ thống thực) để khảo sát và đánh giá đặc tính một hệ
thống.
Phương pháp mô phỏng có những nhược điểm chính như: (1) thời
gian chạy chương trình khá lớn nếu mô phỏng các hệ thống phức tạp.
Do đó thông thường các hệ thống thật cũng phải đơn giản hóa đi khá
nhiều khi chuyển sang mô hình mô phỏng; (2) độ chính xác kết quả
của mô hình mô phỏng tương đối khó kiểm chứng. Một trong các
phương pháp để kiểm tra độ chính xác của mô hình là chạy chương
trình mô phỏng với các tham số đầu vào mà giá trị đầu ra đã được biết
4
trước, sau đó so sánh các kết quả mô phỏng so với kết quả đo đạc
được trong thực tế.
Các công cụ mô phỏng mạng thông dụng được sử dụng hiện nay là
NS-2 (network simulator version 2) [5], OMNET++ [10], OPNET .v.v.
[8]. Các kỹ thuật mô phỏng sẽ được trình bày cụ thể trong Chương 7.
Phương pháp đo đạc (measurement techniques)
Đo đạc được sử dụng để đo các thông số cần thí nghiệm trong các hệ
thống thực (như thông lượng, băng thông, trễ, tuyến đường mà một
gói IP đi qua .v.v.).
Đo đạc được sử dụng để bổ trợ cho phương pháp phân tích toán học
và phương pháp mô phỏng; các tham số đầu vào sử dụng trong các
mô hình toán học và mô phỏng đều được đo đạc trong thực tế. Mặt
khác, đo đạc cũng được sử dụng để kiểm tra độ chính xác của một mô
hình so với hệ thống thực tế.
Các công cụ đo đạc hay được sử dụng trong thực tế bao gồm:
Ethereal, tcpdump, net-snmp, netperf, dbs .v.v. [2].
Phương pháp kết hợp (hybrid techniques)
Phương pháp này kết hợp cả phương pháp phân tích toán học và
phương pháp mô phỏng ở trên. Trong phương pháp này, một hệ
thống sẽ được phân tách thành các khối chức năng. Đối với từng khối,
người ta có thể sử dụng phương pháp mô phỏng hoặc phân tích toán
học.
5
Chương 2 Các tiến trình ngẫu
nhiên
2.1. Xác suất và sựkiện
Trong mục này, các khái niệm cơ bản trong môn xác suất thông kê sẽ
được trình bày.
2.1.1. Phép thử và sự kiện ngẫu nhiên
Định nghĩa 2-1: Một phép thử ngẫu nhiên (random experiment)
là quá trình thử hay quá trình quan sát có thể được lặp đi lặp lại
nhiều lần dưới cùng một điều kiện giống nhau. Kết quả của một
lần thử không thể tiên đoán trước, độc lập với các phép thử trước
đó và có phân bố đồng nhất.
Chú ý rằng tuy kết quả của phép thử ngẫu nhiên không thể tiên đoán
trước, nhưng các kết quả này phải nằm trong một tập giá trị xác định.
Như vậy, nếu gọi e là kết quả của phép thử ngẫu nhiên, Ω là tập hợp
các giá trị của phép thử, ta có:
e∈ Ω;
(PT 2-1)
Thí dụ 2-1: Việc tung đồng xu là một phép thử ngẫu nhiên.
Định nghĩa 2-2: Sự kiện ngẫu nhiên (random event) là kết quả
của một phép thử ngẫu nhiên. Kết quả này nằm trong một tập các
kết quả đã được xác định.
2.1.2. Xác suất
Khái niệm xác suất
Định nghĩa 2-3: Xác suất được định nghĩa là tần suất quan
hệ (relative frequency) của việc xuất hiện một sự kiện ngẫu
nhiên.
Nếu gọi A là sự kiện ngẫu nhiên; sự kiện A xuất hiện nA lần trong một
số lượng lớn các sự kiện n, xác suất của sự kiện A sẽ được định nghĩa
như sau:
6
nA
n
P(A) ≡
;
(PT 2-2)
Một số tính chất của xác suất
• Có thể thấy nếu A không bao giờ xuất hiện P(A) = 0. Mặt khác,
nếu A luôn xuất hiện P(A) = 1. Do đó:
0 ≤ P(A) ≤1;
(PT 2-3)
• Nếu gọi P(A ∪ B) là xác suất xuất hiện của sự kiện A hoặc sự
kiện B. Ta có, trong trường hợp biến A và B tương quan:
P(A ∪ B) = P(A) + P(B) − P(A ∩ B) ; (PT 2-4)
Trong đóP(A∩ B) là xác suất xuất hiện sự kiện A và sự kiện B.
Trong trường hợp A và B độc lập:
P(A ∪ B) = P(A) + P(B) ;
(PT 2-5)
• Nếu gọi P(A/ B) là xác suất có điều kiện (A xuất hiện với điều
kiện B xuất hiện). Trong trường hợp A và B tương quan:
P(A ∩ B) = P(A)⋅ P(B / A) = P(B)⋅ P(A/ B) ; (PT 2-6)
Công thức trên được gọi là công thức Bayes. Mặt khác, nếu A
và B là hai biến độc lập:
P(A ∩ B) = P(A) ⋅ P(B);
(PT 2-7)
2.2. Biến ngẫu nhiên và các hàm xác suất
2.2.1. Biến ngẫu nhiên
Định nghĩa 2-4: Biến ngẫu nhiên được định nghĩa là đại
lượng biến thiên phụ thuộc vào kết cục của một phép thử
ngẫu nhiên nào đó.
Như vậy, nếu gọi X là một biến ngẫu nhiên phụ thuộc vào sự kiện
ngẫu nhiên e, Ω là tập hợp các giá trị của phép thử, ta có:
X ≡ X (e) , e∈ Ω;
(PT 2-8)
Thí dụ 2-2: Trò chơi tung xúc xắc tính điểm với luật chơi sau:
Bảng 2-1. Điểm tương ứng với kết quả tung xúc xắc
Kết quả tung
Điểm
1
2
200
500
7
3
4
5
6
600
1000
1200
1500
Trên Bảng 2-1, kết quả tung chính là sự kiện ngẫu nhiên (kết quả của
phép thử), điểm là biến ngẫu nhiên tương ứng với kết quả đó.
Có hai loại biến ngẫu nhiên là biến ngẫu nhiên rời rạc và biến
ngẫu nhiên liên tục.
Biến ngẫu nhiên rời rạc
Định nghĩa 2-5: Biến ngẫu nhiên rời rạc (discrete random
variable) là biến mà tập giá trị của nó là một tập hữu hạn
hoặc vô hạn đếm được các phần tử.
Nói một cách khác, miền giá trị của một biến ngẫu nhiên rời rạc là một
x1, x2 ,..., xn ,...
dãy số:
có thể hữu hạn hoặc vô hạn.
Thí dụ 2-3: Điểm thi của một sinh viên (từ 1 đến 10); Số cuộc gọi của
một tổng đài trong một đơn vị thời gian.
Biến ngẫu nhiên liên tục
Định nghĩa 2-6: Biến ngẫu nhiên liên tục (continous random
variable) là biến ngẫu nhiên mà tập giá trị của nó lấp kín một
khoảng trên trục số
Nói một cách khác, số phần tử của tập giá trị là vô hạn, không đếm
được theo lý thuyết số. Miền giá trị của một biến ngẫu nhiên liên tục sẽ
[ ]
là một đoạn a,b ∈ℜ.
Thí dụ 2-4: Huyết áp của một bệnh nhân; tuổi thọ của một loại bóng
đèn điện tử.
2.2.2. Hàm mật độ và phân phối xác suất
Hàm mật độ xác suất (probability density function - pdf)
Mật độ xác suất của một biến ngẫu nhiên x liên tục có thể hiểu là xác
suất để biến ngẫu nhiên đó lấy giá trị trong miền [xi , xi + dx]. Nếu gọi
f (x) là hàm mật độ xác xuất của x thì:
8
f (x) ≡ p(xi ≤ x ≤ xi + dx);
(PT 2-9)
Hình 2-1. Hàm mật độ xác suất
Hàm phân phối xác suất (probability distribution function - PDF)
Hàm phân phối xác suất1 của một biến ngẫu nhiên liên tục x là xác
suất để biến ngẫu nhiên đó lấy giá trị trong miền [x1 ≤ x ≤ x2 ]. Nếu gọi
F(x) là hàm phân phối xác suất, ta có định nghĩa hàm phân phối xác
suất như sau:
x2
F(x) ≡ f (x)dx ;
(PT 2-10)
∫
x1
Trong đó f (x) là hàm mật độ xác suất của x.
Hình 2-2.Hàm phân phối xác suất
Từ phương trình trên ta có thể thấy:
∞
F(x) = f (x)dx = 1;
(PT 2-11)
∫
−∞
1 Có hai thuật ngữ tương đương trong sách tiếng Anh biểu thị Hàm phân phối xác suất là: “Probability
Distribution Function” (PDF) và “Cumulative Distribution Function” (CDF).
9
Một số tính chất của hàm mật độ xác suất
Định lý 2-1: Hàm mật độ xác suất của tổng hai biến ngẫu nhiên
độc lập sẽ là tích chập của hai hàm mật độ xác suất thành phần.
Tức là:
∞
fX (x) = fX (y) fX (x − y)dy ;
(PT 2-12)
∫
i
j
∑
−∞
Trong đó: Xi và X j là hai biến ngẫu nhiên, X
= Xi + X j . Hàm
∑
fX (x) , fX (x) và fX (x) là các hàm mật độ xác suất tương ứng.
i
j
∑
Chứng minh: (pending)
2.2.3. Hàm tần suất và phân phối xác suất của biến ngẫu nhiên rời rạc
Xét X là biến ngẫu nhiên rời rạc có tập các giá trị rời rạc x1, x2 ,..., xK .
Hàm tần suất (frequency function) của biến ngẫu nhiên rời rạc
được xác định bởi:
ΡX (xi ) = P(X = xi ) i = 1,2,..., K ;
(PT 2-13)
Xem xét sự kiện a < X ≤ b với a < x1 và xk ≤ b < xk+1 , chúng ta có:
~
~
~
P(a < X ≤ b) = ΡX (x1) + ΡX (x2 ) +K+ ΡX (xk )
k
~
=
=
Ρ (x )
(PT 2-14)
∑
X
i
i=1
P(X ≤ a)
0
Khi đó, hàm phân phối xác suất của của biến ngẫu nhiên rời rạc được
xác định:
0
x < x1
xk ≤ x < xk+1
x ≥ xK
k
~
F (x) =
Ρ (x )
;
(PT 2-15)
(PT 2-16)
∑
X
X
i
i=1
1
FX (xi ) − FX (xi−1) = ΡX (xi )
Thí dụ 2-5: Truyền bản tin số qua kênh nhiễu, xác suất lỗi truyền một
2
5
3
5
số là P(E) = ; xác suất truyền đúng một số là P(C) =1− P(E) =
10
Tải về để xem bản đầy đủ
165 trang
16820
Free
Bạn đang xem 20 trang mẫu của tài liệu "Giáo trình Cơ sở mạng thông tin", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- giao_trinh_co_so_mang_thong_tin.pdf
