ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ VŨ HỮU HÀO
ĐÁNH GIÁ THUẬT TOÁN LẬP LỊCH CHO
DỊCH VỤ VOIP TRONG HỆ THỐNG WiMAX LUẬN VĂN THẠC SĨ


LUẬN VĂN THẠC SĨ NGƯỜI HƯỚNG DẪN KHOA HỌC: TS. TRỊNH ANH VŨ Hà Nội – 2008 2
MỤC LỤC

MỤC LỤC 2
TÓM TẮT 4
KÍ HIỆU VIẾT TẮT 5
DANH MỤC BẢNG 9
DANH MỤC HÌNH VẼ 10
MỞ ĐẦU 13
CHƢƠNG 1: GIỚI THIỆU VỀ CÔNG NGHỆ WIMAX 14
1.1 Lịch sử, quá trình phát triển. 14
1.2 WiMax hoạt động nhƣ thế nào? 15
1.3 Các đặc điểm của WiMax 16
1.4. Các tiêu chuẩn của WiMAX 18


3
3.1.3 Thuật toán Weighted Fair Queuing (WFQ) 60
3.2 Các thuật toán lai. 62
3.2.1 Thuật toán lai (EDF+WFQ+FIFO) 62
3.2.2 Thuật toán lai (EDF+WFQ) 63
3.3 Các thuật toán cơ hội. 65
3.3.1 Thuật toán lập lịch xuyên tầng (Cross- Layer) 66
3.3.2 Thuật toán lập lịch lí thuyết hàng đợi (Queuing Theoretic) 68
3.4 Phân tích độ phức tạp 73
CHƢƠNG 4: CÁC THUẬT TOÁN LẬP LỊCH CHO DỊCH VỤ VOIP
TRONG HỆ THỐNG WIMAX 75
4.1. Voice Over IP? 75
4.1.1 Khái niệm VoIP. 75
4.1.2 Mã hóa với kĩ thuật dò tìm thoại VAD (Voice Active Detection). 76
4.1.3 Truyền dẫn tiếng nói qua hệ thống WiMAX. 76
4.2. Các thuật toán lập lịch trong hệ thống WiMAX 76
4.2.1 Thuật toán UGS. 76
4.2.2 Thuật toán rtPS 77
4.2.3 Thuật toán ertPS. 78
4.3 Phân tích và so sánh các thuật toán. 80
4.3.1 Phân tích hiệu quả sử dụng tài nguyên 81
4.3.2 Phân tích dung lƣợng đạt đƣợc cho dịch vụ VoIP. 84
4.3.3 Độ trễ truyền dẫn gói tin. 86
4.4.4 Đánh giá các dịch vụ thông qua mô hình lập lịch WRR. 88
KẾT LUẬN VÀ KIẾN NGHỊ 96
TÀI LIỆU THAM KHẢO 97
Phụ lục 1: 99
gửi dữ liệu là rất cần thiết. Dựa vào các đặc tính của phiên truyền tiếng nói mà
nhiều thuật toán lập lịch ra đời nhằm nâng cao chất lượng dịch vụ. Luận văn này
nghiên cứu, phân tích và đánh giá các thuật toán lập lịch cho dịch vụ VoIP là UGS,
rtPS và ertPS. Luận văn cố gắng đi sâu chi tiết vào kiến trúc của hệ thống
WiMAX, đưa ra các thuật toán lập lịch thông dụng nhằm tạo tiền đề cho việc phân
tích, và đánh giá khả năng của các thuật toán lập lịch UGS, rtPS và ertPS.
5

KÍ HIỆU VIẾT TẮT
A/D
Analog-to-Digital
Chuyển đổi tương tự sang
số
ACK
Acknowledge
Xác nhận
ADSL
Asymmetric Digital
Subscriber Line
Đường dây thuê bao số bất
đối xứng
AMC
Adaptive Modulation and
Coding

mã.
CCI
Co-Channel Interference
Nhiễu kênh chung
CIR
Carrier - to - Interference
Ratio
Tỉ số sóng mang trên nhiễu

6
CP
Cycle Prefix
Tiền tố tuần hoàn
D/A
Digital-to-Analog
Chuyển đổi số sang tương
tự
DAB
Digital Audio Broadcasting
Phát thanh số quảng bá
DL
Downlink
Kênh xuống
DVB
Digital Video Broadcasting
Truyền hình số quảng bá
DVB-T
Digital Video Broadcasting -
Terrestrial
Truyền hình số quảng bá


Chuẩn WLAN (Châu âu)
dựa trên OFDM, với tốc độ
tối đa 54Mbps. Tương tự
như IEEE802.11a
ICI
Inter - Carrier Interference
Nhiễu giữa các sóng mang
IE
Information Element
Phần tử thông tin
IEEE
IEEE (Institute of Electrical
Chuẩn WLAN (Mỹ) dựa

7
802.11a
and Electronics Engineers)
802.11a
trên OFDM, với tốc độ tối
đa 54Mbps. Tương tự như
HiperLAN2
IEEE
802.16
IEEE (Institute of Electrical
and Electronics Engineers)
802.16
Chuẩn truy cập không dây
băng thông rộng
IFFT

None real time Polling Service
Dịch vụ thăm dò phi thời
gian thực
OFDM
Orthogonal Frequency
Division Multiplexing
Ghép kênh phân chia tần số
trực giao
OFDMA
Orthogonal Frequency
Division Multiple Access
Đa truy nhập phân chia tần
số trực giao
PER
Packet Error Rate
Tỉ lệ lỗi gói tin

8
QAM
Quadrature Amplitude
Modulation
Điều chế biên độ cầu
phương
QoS
Quality Of Service
Chất lượng dịch vụ
QPSK
Quadrature Phase Shift
Keying
Khoá dịch pha cầu phương 9
DANH MỤC BẢNG
Bảng 2.1
Nguyên lý mã hóa và điều chế hỗ trợ trong WiMAX
Bảng 2.1
Nguyên lý mã hóa và điều chế hỗ trợ trong WiMAX
Bảng 2.2
Tốc độ dữ liệu tại tầng Vật lý cho một số kênh truyền.
Bảng 2.3
Trường trong gói tin tiêu đề thông thường
Bảng 2.4
Các trường trong gói tin tiêu đề yêu cầu băng thông.
Bảng 2.5
Đặc tính và các tham số của các luồng dịch vụ
Bảng 3.1:
Độ phức tạp của các thuật toán.
Bảng 4.1:
Tỉ lệ các mức tốc độ mã hóa.
Bảng 4.2:
Kích thước gói tin tương ứng các mức mã hóa
Bảng 4.3:
Băng thông cấp phát cho các dịch vụ UGS, rtPS, ertPS
Bảng 4.4:
Lượng tài nguyên tiết kiệm được bởi thuật toán ertPS so với các
thuật toán UGS, rtPS


Hình 2.8:
Một định dạng burst khác.
Hình 2.9:
Cấu trúc khung TDD trong chuẩn 802.16
Hình 2.10:
Tầng MAC và Tầng Vật lý trong hệ thống WiMAX
Hình 2.11:
Cấu trúc tầng MAC của mạng WiMAX
Hình 2.12:
Phân loại và ánh xạ chỉ số kết nối CID (BS sang SS).
Hình 2.13:
Phân loại và ánh xạ chỉ số kết nối CID(SS sang BS).
Hình 2.14:
Quá trình loại bỏ gói tin tiêu đề.
Hình 2.15:
Sơ đồ quá trình loại bỏ gói tin tiêu đề.
Hình 2.16:
Định nghĩa các gói tin SDU và PDU.
Hình 2.17:
Gói PDU tại tầng với các gói tin MAC PDU
Hình 2.18:
Định dạng gói tin PDU
Hình 2.19:
Gói tin tiêu đề của gói PDU thông thường.

11
Hình 2.20:
Gói tin tiêu đề yêu cầu băng thông.
Hình 2.21:
Gói tin tiêu đề phân mảnh con


Hình 3.6:
Mô tả thuật toán lai (EDF+ WFQ+ FIFO) bằng phương pháp giả
mã Pseudo- code.
Hình 3.7:
Mô tả thuật toán lai (EDF+ WFQ) bằng phương pháp giả mã
Pseudo- code.
Hình 3.8:
Mô tả thuật toán xuyên tầng băng phương pháp giả mã Pseudo-

12
code.
Hình 3.9:
Mô tả thuật toán lí thuyết hàng đợi băng phương pháp giả mã
Pseudo- code.
Hình 4.1:
Hoạt động của thuật toán UGS.
Hình 4.2:
Hoạt động của thuật toán rtPS.
Hình 4.3:
Họat động của thuật toán ertPS.
Hình 4.4:
So sánh tài nguyên tiết kiệm được giữa thuật toán ertPS với các
thuật toán UGS và rtPS.
Hình 4.5:
Dung lượng người dùng lớn nhất tương ứng với các mức điều chế
MCS
Hình 4.6:
Độ trễ gói tin của các dịch vụ rtPS, ertPS, UGS
Hình 4.7:

là một tất yếu. Công nghệ WiMAX ngày càng được hoàn thiện thông qua việc liên
tục đưa ra những tiêu chuẩn phù hợp với nhiều lĩnh vực kinh doanh trên thị trường
như là thiết bị di động, thiết bị cầm tay,…
Phát triển chất lượng dịch vụ QoS là một trong những ưu tiên hàng đầu
trong công nghệ WiMAX. Để hỗ trợ nhiều loại hình dịch vụ với các yêu cầu khác
nhau, về QoS, các tiêu chuẩn của WiMAX đã đưa ra nhiều thuật toán lập lịch
nhằm hỗ trợ các loại hình dịch vụ này. Trong khuôn khổ luận văn này, chúng tôi
giới thiệu và thảo luận một số thuật toán lập lịch gói tin thông dụng được sử dụng
trong hệ thống WiMAX, đồng thời cũng đi sâu phân tích và đánh giá các thuật
toán lập lịch hỗ trợ cho dịch vụ VoIP. Luận văn được tổ chức thành các phần như
sau:
Chƣơng 1: Giới thiệu tổng quan về công nghệ WiMAX. Nhằm đưa ra các
thông tin cơ bản như lịch sử hình thành, các tiêu chuẩn, ưu khuyết điểm của hệ
thống WiMAX.
Chƣơng 2: Phân tích chi tiết giao thức, các tổ chức phân lớp cũng như cách
thức hoạt động của WiMAX.
Chƣơng 3: Giới thiệu và đánh giá một số thuật toán lập lịch được hỗ trợ
trong công nghệ WiMAX.
Chƣơng 4: Phân tích, so sánh, đánh giá các thuật toán lập lịch hỗ trợ cho
dịch vụ VoIP trong hệ thống tiêu chuẩn IEEE 802.16e. 14
CHƢƠNG 1: GIỚI THIỆU VỀ CÔNG NGHỆ WIMAX
1.1 Lịch sử, quá trình phát triển.
Chúng ta đã biết đến các công nghệ truy nhập Internet phổ biến hiện nay
như quay số qua Modem thoại, ADSL, hay các đường thuê kênh riêng, hoặc sử
dụng các hệ thống vô tuyến như điện thoại di động, hay mạng WiFi. Mỗi phương
pháp truy cập mạng có đặc điểm riêng. Đối với Modem thoại thì tốc độ quá thấp,
ADSL tốc độ có thể lên đến 8Mbit/s nhưng cần có đường dây kết nối, các đường

Chuẩn IMT-2000 hiện có 5 giao diện vô tuyến CDMA Direct Spread
(thường được biết dưới tên WCDMA), CDMA Multi-Carrier ( thường được biết
dưới tên CDMA 2000), CDMA TDD, TDMA Single-Carrier, FDMA/TDMA. Sau
khi được bổ sung, chuẩn giao diện OFDMA TDD WMAN sẽ là chuẩn giao diện vô
tuyến thứ 6 của họ IMT-2000.
Các chỉ tiêu về đặc tính phát xạ (phát xạ giả, phát xạ ngoài băng) của các
trạm thu phát (BTS) và máy di động (MS) của WiMAX di động cũng đã được bổ
sung vào các chuẩn hiện áp dụng cho IMT-2000.
1.2 WiMax hoạt động nhƣ thế nào?
Thực tế WiMax hoạt động tương tự WiFi nhưng ở tốc độ cao và khoảng
cách lớn hơn rất nhiều cùng với một số lượng lớn người dùng. Một hệ thống
WiMax gồm 2 phần:
- Trạm phát: giống như các trạm BTS trong mạng thông tin di động với công
suất lớn có thể phủ sóng một vùng rộng tới 8000km
2
.
- Trạm thu: có thể là các anten nhỏ như các Card mạng cắm vào hoặc được
thiết lập sẵn trên Mainboard bên trong các máy tính, theo cách mà WiFi vẫn dùng
Các trạm phát BTS được kết nối tới mạng Internet thông qua các đường
truyền tốc độ cao dành riêng hoặc có thể được nối tới một BTS khác như một trạn
trung chuyển bằng đường truyền thẳng (line of sight), và chính vì vậy WiMax có
thể phủ sóng đến những vùng rất xa.

16

Hình 1.1: Mô hình truyền thông của WiMAX.
Các anten thu/phát có thể trao đổi thông tin với nhau qua các tia sóng truyền
thẳng hoặc các tia phản xạ. Trong trường hợp truyền thẳng, các anten được đặt cố
định trên các điểm cao, tín hiệu trong trường hợp này ổn định và tốc độ truyền có
thể đạt tối đa. Băng tần sử dụng có thể dùng ở tần số cao đến 66GHz vì ở tần số

 Cho phép sử dụng cả hai công nghệ TDD (Time Division Duplexing)
và FDD (Frequency Division Duplexing) cho việc phân chia truyền dẫn của
hướng lên (Uplink) và hướng xuống (Downlink).
 Về cấu trúc phân lớp, hệ thống WiMax được phân chia thành 4 lớp :
Lớp con hội tụ (Convergence) làm nhiệp vụ giao diện giữa lớp đa truy nhập
và các lớp trên, lớp đa truy nhập (MAC layer), lớp truyền dẫn (Transmission)
và lớp vật lý (Physical). Các lớp này tương đương với hai lớp dưới của mô
hình OSI và được tiêu chuẩn hoá để có thể giao tiếp với nhiều ứng dụng lớp
trên như mô tả ở hình dưới đây. 18

Hình 1.2: Mô hình phân lớp trong hệ thống WiMax so sánh với OSI
1.4. Các tiêu chuẩn của WiMAX
Chuẩn IEEE 802.16: ban đầu được tạo ra với mục đích tạo ra những giao
diện không dây dựa trên một nghi thức MAC (Media Access Control) chung. Kiến
trúc cơ bản của hệ thống theo chuẩn IEEE 802.16 bao gồm một trạm gốc BS (Base
Station) và các thuê bao SS (Subcriber Station). Trong vùng phủ sóng của mình,
trạm gốc BS sẽ điều khiển toàn bộ quá trình truyền dữ liệu. Điều này có nghĩa là sẽ
không có sự trao đổi trực tiếp giữa hai trạm thuê bao với nhau. Quá trình kết nối
giữa BS và SS bao gồm một kênh gửi lên (Uplink) và một kênh gửi xuống
(Downlink). Kênh Uplink được chia sẻ cho nhiều thuê bao, trong khi đó kênh
Downlink sẽ được gửi quảng bá (Broadcast). Trong trường hợp không có vật cản
giữa thuê bao và trạm gốc (line of sight), thông tin sẽ được truyền trên băng tần
cao, ngược lại băng tần thấp sẽ được sử dụng nhằm tăng khả năng chống nhiễu.
Chuẩn IEEE 802.16a: tiêu chuẩn này được xác định hoạt động trong dải tần
từ 2Ghz cho tới 11 GHz. Bởi vì tín hiệu tại tần số thấp có thể xuyên qua chướng
ngại vật và vì vậy khái niệm tầm nhìn thẳng giữa trạm phát và nơi nhận là không
yêu cầu. Các quan tâm thương mại đều tập trung vào dải tần thấp này. Tiêu chuẩn

- Kiến trúc mềm dẻo: WiMAX hỗ trợ một vài kiến trúc hệ thống như điểm
tới điểm (P-P), điểm tới đa điểm (P-MP), hoặc mạng lưới (Mesh)… Trong đó tầng
MAC hỗ trợ hầu hêt các loại hình dịch vụ thông qua quá trình sắp xếp khe thời
gian cho mỗi trạm thuê bao SS. Tất cả các trạm SS khi tham gia vào mạng đều có
thể có cơ hội truyền dữ liệu.
- Bảo mật cao: các chuẩn mã hóa tiên tiến đều được sử dụng trong công
nghệ WiMAX như ASE hay DEX. Bằng cách mã hóa các liên kết giữa trạm gốc
BS và trạm thuê bao SS, WiMAX cung cấp các thuê bao riêng đồng thời bảo mật
thông tin trên giao diện không dây băng thông rộng. WiMAX cũng hỗ trợ công
nghệ mạng lan ảo VLAN nhằm tăng cường bảo mật giữa các người dùng chung
cùng mạng.
- Khả năng triển khai nhanh: so với sự triển khai của các giải pháp hữu
tuyến, WiMAX yêu cầu ít hoặc không cần xây dựng kế hoạch mở. Các nhà khai

20
thác chỉ cần có giấy phép để sử dụng một trong số các băng tần được cấp phát,
hoặc có kế hoạch để sử dụng một trong các băng tần không được cấp phép mà
không cần thiết phải xem xét sâu hơn các ứng dụng cho Chính phủ. Khi các thiết bị
được lắp đặt và cấp nguồn, hệ thống WiMAX sẽ sẵn sàng phục vụ.
- Hỗ trợ chất lượng dịch vụ QoS: WiMAX có thể tối ưu hóa hỗn hợp lưu
lượng mạng thành 5 loại hình dịch vụ cơ bản bao gồm dịch vụ cấp phát tự nguyện
UGS, dịch vụ thăm dò thời gian thực rtPS, dịch vụ đáp ứng thăm dò phi thời gian
thực nrtPS, dịch vụ BE và dịch vụ thăm dò thời gian thực mở rộng ertPS. Sự phân
loại giúp cho WiMAX hỗ trợ tốt hơn cho từng loại hình traffic, tăng cường chất
lượng dịch vụ.
- Dung lượng cao: Sử dụng điều chế bậc cao (64-QAM) và độ rộng băng tần
(hiện tại là 7MHz), các hệ thống WiMAX có thể cung cấp độ rộng băng tần đáng
kể cho người sử dụng đầu cuối.
- Độ bao phủ rộng: công nghệ WiMAX hỗ trợ các phương pháp điều chế đa
mức như BPSK, QPSK, 16-QAM, 64- QAM. Khi được trang bị với một bộ khuếch


22
CHƢƠNG 2: NGUYÊN LÝ VÀ HOẠT ĐỘNG CỦA HỆ THỐNG WIMAX

Hình 2.2: Ghép kênh phân chia tần số trực giao
Trong một hệ thống OFDM, luồng dữ liệu đầu vào được chia thành một số
luồng con song song có tốc độ dữ liệu giảm (làm tăng khoảng symbol) và mỗi
luồng con sẽ được điều chế và phát trên một sóng mang con trực giao riêng. 24
Hình 2.3: Kiến trúc cơ bản của một hệ thống OFDM.
OFDM khai thác phân tập tần số của kênh đa đường bởi mã hóa và đan xen
thông tin qua sóng mang con trước khi truyền dẫn. Điều chế OFDM có thể được
thực hiện hiệu quả với biến đổi Fourrier ngược nhanh (IFFT) song vẫn cho phép
một số lượng lớn sóng mang con với độ phức tạp thấp. Trong một hệ thống
OFDM, tài nguyên khả dụng trong miền thời gian là các symbol OFDM và trong
miền tần số là các sóng mang con. Lượng tài nguyên thời gian và tần số có thể
được sắp xếp thành các kênh con để cấp phát cho từng người sử dụng. OFDM sử
dụng kĩ thuật truyền song song nhiều băng tần con nên kéo dài thời gian truyền kí
tự lên nhiều lần.
Trên kênh truyền dẫn thì nhiếu lựa chọn tần số cũng là một vấn đề ảnh
hưởng lớn đến chất lượng truyền thông tín hiệu. Tuy vậy OFDM của mềm dẻo và
linh hoạt khi giải quyết vấn đề này. OFDM có thể khôi phục lại kênh truyền thông
qua tín hiệu dẫn đường (Pilot) được truyền đi cùng với dòng tín hiệu thông tin.
Ngoài ra với các kênh con suy giảm nghiêm trọng về tần số thì OFDM còn có một
lựa chọn nữa để giảm tỉ lệ lỗi bít là giảm bớt số bít mã hóa cho một tín hiệu điều
chế tại kênh tần số đó.
Một trong các vấn đề quan trọng nhất trong thông tin vô tuyến là trải trễ đa
đường. OFDM giải quyết vấn đề này rất hiệu quả. Vì dòng dữ liệu đầu vào được
chia thành N sóng mang con và thời khoảng ký hiệu sẽ giảm đi N lần, do vậy cũng
làm giảm trải trễ đa đường liên quan đến thời gian ký hiệu một hệ số tương ứng.
Nhiễu giữa các ký hiệu ISI được loại bỏ hoàn toàn bằng đưa vào một thời gian bảo
vệ GI cho mỗi ký hiệu OFDM. Thời gian bảo vệ được chọn lớn hơn trải trễ để các