Đồ án Nghiên cứu và triển khai phân bổ băng thông cho Streaming video VBR qua HTTP

u tố ảnh hưởng tới QoE trong hệ thống HAS Trong giới hạn của đồ án chỉ xét đến yếu tố ảnh hưởng hệ thống. Các yếu tố chính ảnh hưởng tới QoE được điều khiển bởi máy khách trong HAS bao gồm: Độ trễ nạp bộ đệm ban đầu, sự gián đoạn, chất lượng cảm nhận, độ trễ trực tiếp (trong streaming trực tiếp) 10. Độ trễ nạp ban đầu luôn tồn tại trong streaming video vì máy khách cần tải một lượng dữ liệu nhất định vào bộ đệm trước khi hiển thị video trên màn hình. Giả sử ban đầu máy khách cần lưu trữ ít nhất 3 giây vào bộ đệm trước khi trình phát bắt đầu chơi video. Với video có chất lượng 3 Mbps và thông lượng mạng Internet hiện tại là 5 Mbps. Máy khách sẽ tải về 3 giây tương ứng với 9 Mbps như vậy với thông lượng mạng là 5 Mbps người dùng phải đợi gần 2 giây mới có thể xem được video. Quá trình tương tự sẽ tiếp tục khi người dùng tìm kiếm một vị trí mới trong video. Để độ trễ nạp ban đầu hầu hết các nhà cung cấp dịch vụ hiện tại như Youtube tại thời điểm khi mới bắt đầu phiên streaming chỉ cho phép tải video ở mức chất lượng thấp, sau một thời gian thích ứng với thông lượng mạng của người dùng thì mức chất lượng video tương ứng sẽ được tải. Ngoài độ trễ nạp ban đầu trong phiên streaming còn tồn tại các độ trễ khác như độ trễ truyền, độ trễ xử lý tại máy chủ. Sự gián đoạn là sự kiện đang xem video bị dừng do mức dữ liệu trong bộ đệm rỗng. Điều này thường xảy ra khi thông lượng của phiên streaming xuống thấp hơn so với tốc độ bit mã hoá của video. Bộ đệm dữ liệu máy khách sẽ hết dữ liệu phát cho trình phát, việc phát lại chỉ có thể tiếp tục sau khi bộ đệm thu thập một lượng dữ liệu video mới. Sự gián đoạn video gồm hai yếu tố là tần suất gián đoạn và khoảng thời gian gián đoạn đều làm ảnh hưởng mạnh tới QoE. Do vậy, các dịch vụ streaming video đều cố gắng để tránh sự gián đoạn trong phiên streaming một cách tốt nhất có thể. Streaming video tải luỹ tiến do chỉ chọn được một mức chất lượng ngay khi bắt đầu streaming. Điều này làm cho streaming video tải luỹ tiến không đối phó được với sự biến đổi của băng thông dẫn đến tần suất mắc gián đoạn trong phiên streaming cao. Trong khi đó HAS có sự thích ứng mức chất lượng video trong phiên streaming làm giảm được sự gián đoạn đáng kể. Sự gián đoạn này xảy ra trong khi người dùng đang xem video và nó có ảnh hưởng nghiêm trọng hơn là độ trễ ban đầu [15]. Chất lượng cảm nhận được phân thành hai yếu tố là biên độ chất lượng và tần suấ thay đổi chất lượng. Chất lượng cảm nhận là chất lượng của video được đánh giá thông qua độ nét của hình ảnh mà người dùng nhận được, được thể hiện bởi tốc độ bit (đối với video CBR) hoặc tham số lượng tử QP (đối với video VBR). Khi QP rất nhỏ mọi thông tin của video đều được giữ lại, khi tăng QP một số thông tin được loại bỏ để giảm dung lượng và tốc độ bit cho video. Vì vậy, QP được coi là tham số đặc trưng cho mức chất lượng của video có giá trị nằm trong khoảng từ 0 đến 51 [16]. Một video với tốc độ bit cao được mã hoá với một mức tham số lượng tử QP thấp thường cho chất lượng tốt. Tốc độ bit càng cao QP càng thấp thì chất lượng được cung cấp càng tốt. Trong streaming tải luỹ tiến các yếu tố ảnh hưởng chính tới QoE chính là độ trễ ban đầu, sự gián đoạn và biên độ chất lượng chính là mức chất lượng video mà máy khách lựa chọn ban đầu. Tuy nhiên trong HAS, do khả năng thích ứng với thông lượng mạng của máy khách biên độ chất lượng video trong suốt phiên streaming thay đổi liên tục. Trong phiên streaming, việc thay đổi mức chất lượng từ cao xuống thấp có làm giảm QoE, đặc biệt việc thay đổi diễn ra một cách đột ngột từ mức chất lượng cao xuống mức chất lượng rất thấp. Ngược lại, việc thay đổi mức chất lượng từ thấp lên cao sẽ làm tăng QoE. Độ trễ trực tiếp là một yếu tố quan trọng nhất trong streaming video trực tiếp. Đó là thời gian từ lúc video được ghi bởi camara tới lúc thiết bị người dùng cuối hiển thị video trên màn hình. Các thành phần trễ chính bao gồm thời gian từ lúc ghi video tới khi video được xử lý tại phía máy chủ: chuẩn bị nội dung, mã hoá, phân đoạn; thời gian đồng bộ giữa tải phân đoạn và trình phát video; thời gian nạp vào bộ đệm và thời gian giải mã hoá. Để tối đa hoá QoE trong HAS các tham số đã đưa ra cần được xem xét đồng thời. Ví dụ để tránh gián đoạn máy khách có thể tăng thời gian trễ ban đầu, tuy nhiên khi thời gian trễ ban đầu tăng lại gây ảnh hưởng xấu tới QoE. Hay để giảm độ trễ ban đầu có giải pháp là chọn mức chất lượng thấp ngay lúc bắt đầu phiên streaming và chuyển mức chất lượng lên cao sau khi thông lượng mạng ổn định. Tuy nhiên chất lượng video thấp và tần suất thay đổi mức chất lượng cũng gây ảnh hưởng tới QoE. Trong hệ thống HAS các giải pháp thích ứng chất lượng hiện nay thường dựa trên nguyên lý như sau: máy chủ lưu giữ các mức chất lượng video cùng các tệp MPD tương ứng, máy khách sẽ dựa trên thông tin tệp MPD truy vấn từ máy chủ, tình trạng bộ đệm, thông lượng mạng để quyết định phân đoạn video nào sẽ được tải tiếp theo [17]. Như vậy quá trình quyết định chất lượng hoàn toàn phụ thuộc vào máy khách và mỗi máy khách đều cố gắng để đạt được mức chất lượng tối đa. Trong mạng được quản lý (ví dụ IPTV) các tiếp cận trên sẽ dẫn đến tình trạng tranh chấp băng thông khi chúng cùng chia sẻ một đường truyền có băng thông hạn chế. Hành vi tranh chấp này làm cho việc dự đoán thông lượng thiếu chính xác, dẫn đến chất lượng video sẽ bị biến động mạnh. Một số biện pháp được sử dụng tại máy chủ như: thiết kế thuật toán phân bổ băng thông cải thiện QoE [18], thiết kế bộ điều khiển động phân bổ tài nguyên, điều chỉnh số lượng máy ảo trong mạng CDN mang lại lợi ích truy cập nội dung gần với người dùng hơn [19]. Các giải pháp này có đạt được hiệu quả cải thiện QoE, tuy nhiên khi hệ thống ở quy mô lớn, cách tiếp cận thích ứng tại máy chủ là rất khó khăn để thực hiện. Như vậy có thể thấy rằng việc phân bổ băng thông cho hệ thống streaming video VBR trên đường truyền có băng thông hạn chế đang là một vấn đề đáng được quan tâm và nghiên cứu. Kết luận chương Trong Chương 1, đồ án đã trình bày các cơ sở lý thuyết nền tảng liên quan và công nghệ streaming video nói chung, đặc biệt là công nghệ HAS nói riêng. Sau đó đồ án đã phân tích các yếu tố tác động đến QoE trong HAS và đưa ra biện pháp để cải thiện QoE trong dịch vụ streaming video là cần loại bỏ sự gián đoạn video, giảm độ trễ ban đầu và hạn chế tần suất thay đổi biên độ chất lượng video. Đây sẽ là kiến thức nền tảng để có thể thực hiện các chương tiếp theo. NGHIÊN CỨU VÀ TRIỂN KHAI GIẢI PHÁP THÍCH ỨNG CHẤT LƯỢNG CHO VIDEO VBR Trong chương này, đồ án sẽ trình bày mô hình thích ứng chất lượng cho video VBR. Trong mô hình mạng được quản lý, mỗi video được cấp một mức băng thông cố định, với mức băng thông này đồ án áp dụng mô hình thoả hiệp giữa chất lượng và độ trễ để tìm ra giá trị lợi ích tốt nhất cho người dùng. Đồng thời triển khai thực nghiệm mô hình và đánh giá kết quả so với phương pháp truyền thống. Thích ứng tốc độ bit video VBR và tối đa lợi ích người dùng Mô hình thích ứng tốc độ bit video VBR Đối với một video, chất lượng của video phụ thuộc vào tham số lượng tử QP. Khi QP lớn một số nội dung của video bị loại bỏ trong lúc mã hoá để giảm dữ liệu dẫn đến tốc độ bit mã hoá của video cũng giảm theo. Ngược lại khi QP nhỏ hầu hết các thông tin của video được giữ lại, lượng dữ liệu để mã hoá lớn, dẫn đến tốc độ mã hoá lớn. Tuy nhiên trong đường truyền video, mức chất lượng video thường được đại diện thông qua tốc độ bit đại diện (kí hiệu là R) của video đó. Tốc độ bit đại diện càng cao thì chất lượng video càng cao và ngược lại. Đối với video CBR thì tốc độ bit đại diện chính là tốc độ bit dùng để mã hoá video đó. Với video VBR tốc độ bit đại diện liên quan đến hai yếu tố là độ trễ ban đầu và thời điểm máy khách bắt đầu hiển thị video 20. Độ trễ ban đầu được tính là khoảng thời gian mà máy khách bắt đầu nhận video cho tới thời điểm máy khách bắt đầu hiển thị video. Tốc độ bit đại diện cho một mức chất lượng của video được tính dựa vào độ trễ ban đầu d0 và tốc độ bit tức thời tại các phân đoạn của video. Hình 2.1 chỉ ra tốc độ bit R chính là hệ số góc đường tiếp tuyến của đường gấp khúc có hệ số góc là các tốc độ bit tức thời của các phân đoạn video tại một mức chất lượng. Hình 2. 1 Quan hệ giữa tốc độ bit đại diện và độ trễ ban đầu. Độ trễ ban đầu d0=t0-td với td là thời điểm máy khách bắt đầu nhận dữ liệu đến và t0 là thời điểm mà người dùng bắt đầu chơi video. Có thể thấy khi d0 tăng thì hệ số góc đường tiếp tuyến sẽ giảm xuống, tốc độ bit đại diện của video tại mức chất lượng sẽ giảm. Khi tốc độ bit đại diện của mức chất lượng giảm thì máy khách sẽ có cơ hội chọn được mức chất lượng cao hơn trong phiên streaming. Như vậy nếu người xem chấp nhận đợi một khoảng thời gian dài thì sẽ xem được video có chất lượng tốt hơn. Một ví dụ minh hoạ như sau: một video có năm mức chất lượng lần lượt từ thấp tới cao với các tốc độ bit đại diện: 200kbps, 400kbps, 600kbps, 800kbps, 1000kbps. Người xem với băng thông được cấp là 750kbps có thể xem được video với mức chất lượng thứ ba có tốc độ bit đại diện là 600kbps. Bằng cách tăng độ trễ d0 theo mô hình Hình 2.1 tốc độ bit đại diện của video tại một mức chất lượng sẽ giảm. Như vậy, tốc độ bit đại diện cho các mức chất lượng của video ban đầu chỉ còn là 150kbps, 300kbps, 500kbps, 700kbps, 900kbps, do đó người xem sẽ xem được video có mức chất lượng thứ tư ứng với tốc độ bit đại diện là 700kbps. Tuy nhiên nếu d0 quá dài người dùng phải đợi lâu tại thời điểm bắt đầu video thì QoE sẽ bị ảnh hưởng vì vậy cần phải có một mô hình thoả hiệp giữa chất lượng video và độ trễ ban đầu. Một mô hình được đề xuất trong [21] được thực hiện bằng cách thay thế một số phân đoạn có tốc độ bit cao xuống phân đoạn tương ứng có tốc độ bit thấp hơn. Việc thay thế này sẽ dẫn đến hệ số góc của đường tiếp tuyến sẽ bị bé lại tức là hạ được tốc độ bit đại diện cũng như giảm được độ trễ ban đầu sao cho chất lượng video giảm không đáng kể. Mô hình cụ thể như sau: một video C có M mức chất lượng Vi | 1 ≤i ≤M, mỗi mức chất lượng Vi được đặc trưng bởi tham số lượng tử QPi và gồm N phân đoạn với tốc độ bit Bij | 1 ≤j ≤N. Các mức chất lượng đã được sắp xếp từ cao xuống thấp Bij ≥ Bi+1j. Cần thích ứng video này với một mức băng thông được cấp R và một ràng buộc DT là giới hạn của độ trễ ban đầu. Các tác giả trong 21 đã định nghĩa một hàm pε tại mỗi phân đoạn nếu tốc độ bit của nó lớn hơn ε thì được thay thế bởi phân đoạn tương ứng ở mức chất lượng thấp hơn gần nhất mà có tốc độ bit nhỏ hơn ε. Bj*=BMj, BMj> εmaxBij | Bij≤ε, 1≤i ≤ M (2.1) Ngưỡng tốc độ bit ε sẽ được lấy rời rạc. Với mỗi hàm p(ε) ta tìm được một mức chất lượng thích ứng V* có chất lượng Q* và độ trễ ban đầu là d0* từ một tốc độ bit đại diện R được cấp cho video. Tối đa hoá lợi ích người dùng Bài toán đặt ra là với một mức tốc độ bit đại diện R ta cần tìm pε sao cho lợi ích U của người dùng là lớn nhất. Lợi ích U được định nghĩa như là hàm bù trừ giữa chất lượng video và độ trễ ban đầu có giá trị nằm trong khoảng [1,5]. Với giá trị ε lớn hơn tốc độ bit đại diện chất lượng video sẽ được cải thiện hơn so với việc không sử dụng mô hình, tuy nhiên khi ε lớn hơn nhiều so với tốc độ bit đại diện sẽ dẫn đến độ trễ ban đầu lớn hoặc gây gián đoạn trong quá trình streaming. Vì vậy cần thoả hiệp giữa chất lượng video và độ trễ ban đầu để đạt được lợi ích người dùng U tốt nhất. Lợi ích người dùng được công thức hoá sử dụng các mô hình tham số ảnh hưởng tới trải nghiệm người dùng sẽ là giá trị về mặt lý thuyết cho thấy hiệu quả của mô hình thích ứng chất lượng video đối với trải nghiệm người dùng. Như vậy lợi ích U của người dùng sẽ là hàm của các tham số chất lượng và độ trễ như sau: U=f(Q*, d0*) (2.2) Việc tính U được đề xuất thông qua mô hình tuyến tính tại [22] như sau: U= a* Ud+b* Uq (2.3) Với Ud là hàm của độ trễ ban đầu d0 thể hiện sự ảnh hưởng của thời gian chờ đợi đến QoE. Uq là hàm của tham số lượng tử QP thể hiện sự ảnh hưởng của chất lượng đến QoE. Trọng số a và b thể hiện mức độ ảnh hưởng của độ trễ ban đầu và chất lượng video đối với lợi ích người dùng, thường được lấy tương ứng là 0.2 và 0.8 21. Mức chất lượng thích ứng Q* của video là giá trị trung bình của các mức chất lượng từng phân đoạn được thay thế thích ứng, Q* được tính như sau: Q*= 1N j=1SQPj (2.4) Với QPj là tham số lượng tử cho phân đoạn thứ j của mức chất lượng thích ứng. S là số phân đoạn của một video. Công thức để tính Uq được đề xuất trong [23] được tính như sau: Uq= -0.172 × Q*+9.249 (2.5) Để tính độ trễ ban đầu d0 cần dựa vào khái niệm đường bao dữ liệu tích luỹ. Đường bao E của một luồng video tại mỗi thời điểm t là dữ liệu tới hạn có thể được nhận bởi máy khách từ thời điểm bắt đầu nhận tp cho đến thời điểm t [24]. Et=maxA[tp, tp+t] (2.6) Với A[tp, tp+t] là lượng dữ liệu tích luỹ tính từ thời điểm ban đầu nhận được video đến thời điểm t. Hình 2.2 là một ví dụ minh hoạ thể hiện dữ liệu tích luỹ và dữ liệu đường bao theo thời gian của một video. Hình 2. 2 Dữ liệu tích luỹ và đường bao tương ứng. Tại Hình 2.3 đường màu đỏ là đường bao dữ liệu E. Đường thẳng với tốc độ bit đại diện R tiếp tuyến với đường bao sẽ thu được độ trễ ban đầu d0. Hình 2. 3 Mô hình dữ liệu tích luỹ, đường bao dữ liệu. Từ hình 2.3 suy ra: R ×t+d0 ≥Et ≥A[tp, tp +t], ∀t> 0 (2.7) Công thức 2.7 chỉ ra rằng với thời gian chờ ban đầu là d0 và tốc độ bit đại diện R thì lượng dữ liệu đến sẽ luôn lớn hơn lượng dữ liệu lớn nhất có thể đến tại thời điểm t do đó phiên streaming sẽ không bao giờ bị gián đoạn cho dù máy khách hiển thị video tại bất kỳ thời điểm tp nào. Để tính Ud sử dụng mô hình toán học đề xuất trong [25] như sau : Ud= -0.862 ×logd0*+6.718+5 (2.8) Như vậy với mức băng thông được cấp cho video là R, tìm được một mức chất lượng video mạng lại giá trị lợi ích U cao nhất, với điều kiện giới hạn của độ trễ ban đầu d0 ≤DT. Trong mạng IPTV, DT là độ trễ giới hạn cho độ trễ ban đầu, nếu độ trễ ban đầu vượt quá giới hạn 0.5 giây sẽ làm ảnh hưởng tới QoE. Xây dựng thuật toán và triển khai mô hình Dữ liệu đầu vào của bài toán bao gồm : Tốc độ bit đại diện R, Dữ liệu các mức chất lượng video B[Q][S], trong mỗi mức chất lượng video bao gồm dữ liệu các tốc độ bit tức thời của mỗi phân đoạn, như vậy một video có Q phiên bản mức chất lượng, mỗi phiên bản mức chất lượng được chia ra thành S phân đoạn. Các ký hiệu được thể hiện ở Bảng 2.1 Bảng 2. 1 Các ký hiệu và định nghĩa trong sơ đồ khối Hình 2.4 Kí hiệu Định nghĩa R Tốc độ bit đại diện (Mức băng thông được cấp cho video) B[i][j] Dữ liệu tốc độ bit các phân đoạn j của video mức chất lượng i 1 ≤i ≤ Q, 1 ≤j≤ S. ԑ Tốc độ bit thích ứng. p_min Tốc độ bit thấp nhất của phân đoạn video. p_max Tốc độ bit cao nhất của phân đoạn video. B* Dữ liệu tốc độ bit sau khi thích ứng. Q* Chất lượng video thích ứng. d0* Độ trễ ban đầu của video có mức chất lượng thích ứng. s Khoảng cách giữa các tốc độ bit thích ứng. ε là một tập rời rạc được lấy từ tốc độ bit nhỏ nhất của phân đoạn video đến tốc độ bit phân đoạn lớn nhất. Đối với mỗi giá trị ε sẽ tìm được tương ứng một giá trị lợi ích U và độ trễ d0, Do vậy một tập ε sẽ cho kết quả là một tập U và d0 từ đây cần tìm ra giá trị lợi ích U lớn nhất ứng với một độ trễ d0. Cụ thể mô hình được triển khai theo sơ đồ khối Hình 2.4 Hình 2. 4 Sơ đồ khối triển khai thích ứng chất lượng video VBR. Trong đó các hàm thích ứng adapt() để tìm các tốc độ bit thích ứng cho từng phân đoạn và mức chất lượng QP được thực hiện theo công thức 2.1 và 2.4. Hàm tính độ trễ d0 được thực hiện theo thuật toán tìm tiếp tuyến đường bao chi tiết thể hiện ở Thuật toán 1. Ban đầu, env là dữ liệu đường bao được tính bằng cách lựa chọn ra lượng dữ liệu lớn nhất có thể đến máy khách tại thời điểm t (dòng 17 - Thuật toán 1). Thuật toán 1: Tìm độ trễ d0 theo mô hình tiếp tuyến đường bao dữ liệu Input: adapt , S, Ts, R; // adapt dữ liệu sau khi thích ứng thay thế phân đoạn. // S Số phân đoạn của video. // Ts độ dài thời gian của mỗi phân đoạn. Output: d0 // Độ trễ ban đầu ứng với video có mức chất lượng thích ứng 1 // Tính dữ liệu đường bao 2 index=S+1; 3 for 1 ≤i ≤index do 4 datai= 0; 5 end for 6 for 1 ≤i≤S do 7 k = 0; 8 while 1≤ index and k ≤index do 9 datak=datak+adapti+k ×Ts; 10 k=k+1; 11 end while 12 // chọn ra dữ liệu lớn nhất có thể tới tại phân đoạn j 13 for 1 ≤j≤index do 14 maxS=maxS>dataj ?maxS :dataj; 15 end for 16 index=index-1; 17 envelopi=maxS; 18 maxS=0; 19 end for 20 // Tính độ trễ d0 21 for 1 ≤i≤S do 22 deltai=envi-R×Ts×i; 23 end for 24 d0=max(deltai)R; 25 Sau khi có dữ liệu đường bao mô hình tính độ trễ ban đầu d0 tại Hình 2.5 được áp dụng để tính d0. Chi tiết như sau: kẻ đường thẳng có hệ số góc là R đi qua điểm A(0, t0). Tại mỗi mốc thời gian ti tìm độ lệch delta[i] là độ lệnh giữa dữ liệu đường bao và dữ liệu tương ứng với tốc độ R tại phân đoạn thứ i và chọn ra delta lớn nhất. Hình 2. 5 Mô hình tính độ trễ d0 Dịch chuyển đường thẳng có hệ số góc R tiếp tuyến với đường bao tại điểm có delta lớn nhất như vậy thời gian d0 được tính theo công thức: d0= max⁡(deltai)R (3.1) Chi tiết được thể hiện tại Thuật toán 1 dòng 20. Sau khi có được độ trễ ban đầu, các công thức 2.3, 2.5, 2.8 được áp dụng để tìm ra lợi ích U của người dùng tại tốc độ bit thích ứng ε. Cuối cùng với các giá trị U ứng với giá trị ε tìm được, ta tìm ra giá trị U lớn nhất sau khi đã thoả hiệp giữa chất lượng video và độ trễ ban đầu. Kết quả thực nghiệm và đánh giá Tại phần thực nghiệm đồ án sử dụng video Sonny được lấy từ [26], có sáu mức chất lượng tương ứng với các tham số lượng tử QP là 48, 42, 38, 34, 28, 22. Mỗi phiên bản chất lượng video được chia thành 294 phân đoạn với các tốc độ bit mỗi phân đoạn là khác nhau. Độ dài mỗi phân đoạn là 2s. Bảng 2.2 là kết quả thực nghiệm triển khai mô hình thích ứng chất lượng video VBR với 20 mức băng thông khác nhau từ thấp tới cao. Với các mức băng thông tăng dần dẫn đến chất lượng video được cải thiện, tham số lượng tử QP trung bình giảm dần đồng thời lợi ích người dùng U tăng dần. Bảng 2. 2 Kết quả thích ứng chất lượng video Sony. Băng thông (Mbps) Lợi ích người dùng U Độ trễ ban đầu d0 QPavg 494,51 1,99 0,50 44 1136,30 3,26 0,07 35 1778,09 3,70 0,39 32 2419,89 4,04 0,45 29 3061,68 4,15 0,41 28 3703,47 4,32 0,49 27 4345,26 4,50 0,45 26 4987,05 4,63 0,15 25 5628,85 4,74 0,45 24 6270,64 4,77 0,43 24 6912,43 4,80 0,45 24 7554,22 4,86 0,43 23 8196,01 4,89 0,27 23 8837,80 4,90 0,20 23 9479,60 4,94 0,37 23 10121,39 4,97 0,35 22 10763,18 5,00 0,34 22 11404,97 5,00 0,15 22 12046,76 5,00 0,26 22 12688,56 5,00 0,04 22 Kết quả thực nghiệm này được so sánh với phương pháp không thích ứng tốc độ bit. Cụ thể phương pháp thông thường chỉ chọn mức một mức chất lượng cụ thể để thực hiện streaming và chưa sử dụng mô hình thoả hiệp giữa chất lượng và độ trễ ban đầu d0. Hình 2. 6 là kết quả của phương pháp thích ứng chất lượng so với phương pháp thông thường. Hình 2. 6 Giá trị lợi ích người dùng của phương pháp thích ứng so với phương pháp thường. Đối với phương pháp thường các mức chất lượng được tăng từ thấp lên cao tương ứng với năm tham số lượng tử QP. Các đoạn nằm ngang của phương pháp thường từ mức băng thông 4 – 7 và 8 – 18 trong Hình 2.6 cho thấy tại đây độ lớn của tốc độ bit chưa đủ để chuyển đổi mức chất lượng dẫn đến giá trị lợi ích người dùng sẽ không đổi. Đặc biết trong khoảng mức băng thông từ 8 – 18 mức băng thông tăng lên khá lớn tuy nhiên lợi ích người dùng không thay đổi có thể thấy tốc độ bit phân đoạn của video biến động khá mạnh trong khoảng này. Nếu chuyển đổi trong giai đoạn này độ trễ ban đầu sẽ lớn hơn độ trễ giới hạn gây nên hiện tượng gián đoạn video. Như vậy phương pháp thích ứng chất lượng video VBR cho thấy hiệu quả rõ ràng khi lợi ích người dùng được tăng lên trùng bình gần 1 điểm. Kết luận chương Trong Chương 2, đồ án đã thực hiện mô hình thích ứng tốc độ bit cho video VBR và tối ưu lợi ích người dùng bằng việc cân bằng giữa chất lượng và độ trễ d0. Và kết quả cho thấy lợi ích người dùng tăng lên đáng kể so với phương pháp truyền thống. Như vậy, với mỗi tốc độ bit đại diện R luôn có một mức chất lượng thích ứng có lợi ích người dùng cao nhất với độ trễ d0 được giới hạn. Đây chính là dữ liệu để đồ án có thể thực hiện mô hình phân bổ băng thông cho nhiều người dùng streaming video cùng một thời điểm ở chương tiếp theo. TRIỂN KHAI GIẢI PHÁP CẤP PHÁT BĂNG THÔNG CHO HỆ THỐNG STREAMING NHIỀU VIDEO VBR Với kết quả đạt được trong Chương 2, trong chương này đồ án sẽ trình bày mô hình hệ thống streaming nhiều video VBR cùng lúc trên một đường truyền cố định có băng thông giới hạn trong mạng được quản lý. Đồng thời trình bày các thuật toán phân bổ băng thông cho các máy khách cùng truy cập tới máy chủ để mở phiên streaming. Mục đích của việc phân bổ băng thông là tận dụng tối đa tổng băng thông đường truyền,cải thiện lợi ích trung bình của tất cả người dùng. Từ đó tiến hành thực nghiệm và đánh giá các thuật toán thiết kế với các tiêu chí phù hợp với hệ thống streaming video đề xuất. Mô tả bài toán Trong mô hình đề xuất tại phía máy chủ sẽ lưu nhiều video, mỗi video có nhiều mức chất lượng khác nhau. Tại phía máy chủ các video được xử lý trước. Mỗi video sẽ được phân nhiều mức băng thông khác nhau và tương ứng với mỗi băng thông là giá trị lợi ích người dùng và độ trễ tương ứng. Các nhóm máy khách tại những khu vực nhất định như trường học, văn phòng, khu tập thể, sẽ cùng truy cập vào máy chủ tại một thời điểm để xem những video khác nhau. Vấn đề xảy ra ở đây là nếu không phân bổ băng thông cho các máy khách sẽ xảy ra tình trạng tranh chấp băng thông tại các nút cổ chai trên đường truyền, hay nếu chia đều băng thông cho người dùng tại nút cổ chai thì sẽ dẫn đến lãng phí băng thông [25]. Mô hình hệ thống được đề xuất như Hình 3.1. Hình 3. 1 Sơ đồ hệ thống streaming nhiều video trên cùng một đường truyền. Ví dụ A, B, và C cùng truy cập vào máy chủ để xem video. Video A xem có tốc độ bit đại diện là 2000kbps, B là 4000kbps, C là 5000kbps và các video A, B, và C xem là cùng một mức chất lượng. Do khác nhau về kích thước màn hình nên tốc độ bit khác nhau. Nếu tổng băng thông đường truyền là 9000kbps và không có thuật toán cấp phát thì băng thông sẽ được chia đều cho từng người. Kết quả là A sẽ xem video với đúng chất lượng và có sự lãng phí băng thông do chất lượng video của A chỉ có tốc độ bit đại diện là 2000kbps. B sẽ xem video với chất lượng kém hơn chất lượng ban đầu và C là người xem video với chất lượng tệ nhất do C chỉ có băng thông 3000kbps mà video C xem yêu cầu mức băng thông là 5000kbps. Như vậy có thể thấy lợi ích người dùng vẫn chưa được tối ưu. Do B và C chỉ được xem ở video chất lượng thấp. Mục tiêu đặt ra là cần phân bổ băng thông để A, B, C đều có mức chất lượng video như nhau và mức độ hài lòng của ba người là tương đương nhau và không gây lãng phí băng thông. Như vậy để phân bổ băng thông cho nhiều người một cách phù hợp mô hình đề xuất tạo khối điều khiển nhận dữ liệu của server về video như các mức băng thông và giá trị lợi ích U tốt nhất tương ứng với mỗi băng thông được cấp. Mỗi cặp giá trị U, R chính là kết quả đạt được từ Chương II. Bài toán được cụ thể như sau: đối với video C[i] (1 ≤ i ≤ M là số lượng video được xem cùng lúc) được lưu tại máy chủ có Q mức chất lượng. Mỗi video có S phân đoạn. Video C[i] có thể được cấp N mức băng thông khác nhau Rij với (1 ≤j ≤ N). Ứng với mỗi mức băng thông Rij là mức lợi ích tốt nhất Uij với độ trễ d0[i][j] là kết quả của mô hình thích ứng tốc độ bit và thoả hiệp với độ trễ ở chương II. Mục tiêu bài toán là đi tìm giá trị lớn nhất của tất cả lợi ích người dùng U sao cho tổng băng thông sử dụng nhỏ hơn hoặc bằng tổng băng thông cấp phát RT và độ trễ d0[i] ≤DT là độ trễ giới hạn. Bài toán được chuyển hoá thành công thức 3.1 và 3.2 như sau: UT=max⁡(i=1MUi) (3.1) Thoả mãn điều kiện: i=1MRi ≤ RT, d0i ≤DT (3.2) Trong đó U[i] là giá trị lợi ích tốt nhất đạt được tại mức băng thông Ri của video Ci. Với việc phân cấp N mức băng thông cho video Ci thì U[i] và R[i] sẽ được chọn từ tập U[M][N], R[M][N]. Xây dựng và triển khai các thuật toán phân bổ băng thông cho streaming nhiều video VBR Bài toán trên có thể giải bằng thuật toán vét cạn, tức là xét tất cả các trường hợp có thể xảy ra và chọn ra trường hợp cho giá trị lợi ích tổng của người dùng tốt nhất, cách giải này cho kết quả chính xác nhất. Tuy nhiên trong bối cảnh streaming video thời gian thực thuật toán vét cạn mất khá nhiều thời gian thực thi với bộ dữ liệu lớn gây ảnh hưởng đến quá trình streaming. Từ nhược điểm này đồ án sẽ trình bày hai thuật toán để thực hiện phân bổ băng thông đồng thời đánh giá kết quả thực nghiệm của hai thuật toán này với thuật toán vét cạn. Dữ liệu đầu vào của các thuật toán được thiết kế là các điểm dữ liệu. Mỗi điểm sẽ tương ứng với một mức chất lượng của video. Một điểm dữ liệu cơ bản bao gồm một băng thông R và giá trị lợi ích của người dùng tương ứng với băng thông đó. Mỗi video gồm nhiều điểm dữ liệu đồng nghĩa với việc một video được cấp nhiều băng thông để người dùng có thể thích ứng phù hợp với băng thông. Bảng 3.1 là một ví dụ minh hoạ về 15 điểm dữ liệu đầu vào của bài toán với số mức băng thông được cấp là năm và có ba video: Lam, Sony, Tokyo được xem cùng lúc bởi người dùng. Bảng 3. 1 Ví dụ minh hoạ dữ liệu đầu vào cho thuật toán phân bổ băng thông. Video Điểm DL Lam Sony Tokyo R(KB/s) U R(KB/s) U R(KB/s) U 1 117.6 3.24 494.5 2.00 82.1 2.73 2 334.1 4.38 1136.3 3.25 280.9 2.88 3 550.5 4.74 1778.1 3.69 479.7 4.27 4 767.1 4.86 2419.8 4.04 678.6 4.56 5 983.5 4.91 3061.6 4.15 877.5 4.68 Có thể thấy các điểm dữ liệu được sắp xếp theo mức tăng dần của băng thông thì giá trị lợi ích người dùng cũng tăng tương ứng. Thuật toán phân bổ băng thông sử dụng nhân tử Lagrange Từ công thức 3.1 và 3.2 suy ra mục đích của bài toán như sau: Tìm giá trị lớn nhất của hàm số fU[i]= i=1MU[i] (3.3) Sao cho thoả mãn điều kiện: gR[i]= i=1MR[i]- RT≤0 (3.4) Như vậy có thể thấy đây chính là bài toán tìm cực trị (cực đại) của hàm fUi với điều kiện ràng buộc là bất phương trình g(Ri). Phương pháp nhân tử Lagrange là một trong những phương pháp giúp giải quyết những bài toán tìm cực trị của hàm có điều kiện ràng buộc. Với yêu cầu tìm cực trị của hàm f(x, y) thoả mãn điều kiện ràng buộc gx,y=0, phương pháp này sử dụng hàm hỗ trợ sau: Lx, y, λ=fx, y- λg(x, y) (3.5) Ý nghĩa của phương pháp nhân tử Lagrange được hiểu là chuyển từ bài toán tìm cực trị ràng buộc về giải bài toán cực trị không ràng buộc bằng cách sử dụng nhân tử λ đưa điều kiện ràng buộc vào một phương trình mới và giải quyết bài toán với phương trình này. Hàm số Lx, y, λ được gọi là hàm hỗ trợ. Nếu f(x0, y0) là cực trị của hàm f(x, y) thì tồn tại một λ0 sao cho: ∇x, y, λLx0,y0 , λ0=0 (3.6) Khi đó x0, y0, λ0 được gọi là một điểm dừng. Tuy nhiên không phải tất cả các điểm dừng đều là kết quả của bài toán ban đầu. Do vậy phương pháp Lagrange chỉ mang lại một điều kiện cần cho bài toán tối ưu có điều kiện ràng buộc. Biến tối ưu toàn cục có thể được tìm thấy bằng cách so sánh các giá trị của hàm mục tiêu ban đầu tại các điểm dừng thoả mãn điều kiện cần. Quay lại với vấn đề của bài toán phân bổ băng thông hàm hỗ trợ sử dụng theo phương pháp nhân tử Lagrange được xây dựng như sau: LUi, Ri, λ= i=1MUi- λ(i=1MRi- RT) (3.7) Với các giá trị đầu vào là Ui, Ri ta luôn tìm được một điểm mà tại đó tổng lợi ích người dùng là lớn nhất và thoả mãn điều kiện băng thông sử dụng nhỏ hơn hoặc bằng băng thông giới hạn. Hay nói cách khác với các điểm giá trị đầu vào của bài toán ta luôn có một điểm dừng mà tại đó hàm L(Ui, Ri, λ) đạt giá trị lớn nhất. Từ công thức 3.7 ta có : LU[i], Ri, λ= i=1MUi- λRi- λRT= i=1MLi+ λRT (3.8) Theo công thức 3.8 ta cần tìm các giá trị Li lớn nhất tại mỗi λ. Như vậy với tập dữ liệu đã biết ta cần tìm với các điểm dữ liệu U[i][j], R[i][j] nào thuộc tập dữ liệu U[M][N], R[M][N] thì λ tiến tới λ0. Khi đó, điểm dữ liệu đó chính là nghiệm cần tìm. Phương pháp tìm λ0 được trình bày chi tiết trong Thuật toán 2. Bảng 3. 2 Ký hiệu và định nghĩa sử dụng trong thuật toán 2 Kí hiệu Ý nghĩa dataij Điểm dữ liệu thứ j của video i select[i] Dữ liệu đầu ra là chỉ số các điểm dữ liệu của video i được chọn λmin, λmax Giới hạn cho nhân tử Lagrange λ last , first Giới hạn các điểm dữ liệu mid[] Chỉ số các điểm dữ liệu hiện tại đang xét RT Băng thông tổng bwuse Băng thông đang sử dụng tại các điểm dữ liệu được xét Ban đầu, các giới hạn tìm kiếm dữ liệu sẽ được khởi tạo với first , mid là tập chỉ số các điểm có mức băng thông thấp nhất đủ để chơi video với chất lượng thấp nhất với độ trễ khởi tạo giới hạn, last[ ] sẽ là chỉ số các điểm dữ liệu có mức băng thông cao nhất đủ để chơi video chất lượng tốt nhất. Thuật toán 2: Phân bổ băng thông cho hệ thống streaming video VBR sử dụng nhân tử Lagrange Input: data[i][j], RT, 1≤i ≤M, 1 ≤j ≤N Output: select[i], 1≤i ≤M 1 // Gán các chỉ số giới hạn 2 λmin=0; λmax=1; temp=0; 3 for 1 ≤i ≤M do 4 lasti= N; 5 midi=1; 6 firsti=1; 7 end for 8 // Cải thiện chất lượng video sử dụng nhân tử Lagrange 9 while true do 10 bwuse= 0; 11 λnext=λmax+λmin2; 12 for 0≤i ≤M do 13 // Khởi tạo giá trị Li 14 Li= -1000; 15 if firsti=lasti then 16 bwuse=bwuse+dataimidi.r; 17 continue; 18 end if 19 // Tìm kiếm Li max 20 for 0 ≤j≤N do 21 if dataij.u- λnext*dataij.r >Li then 22 Li=dataij.u- λnext*dataij.r; 23 midi=j; 24 end if 25 end for 26 bwuse=bwuse+dataij.r; 27 end for 28 // Kiểm tra điều kiện đủ 29 if bwuse= RT then 30 select =mid ; exit; 31 else if bwuse< RT then 32 first =mid ; λmax= λnext; 33 else if bwuse> RT then 34 last =mid ; λmin= λnext; 35 end if 36 // Kiểm tra điều kiện thoát thuật toán 38 for 1 ≤i ≤M do 39 temp=temp+ lasti-firsti; 40 end for 41 if fist ≠mid and last ≠mid and temp<M and bwuse≤RT then 42 select =first ; 43 end if 44 end while Thuật toán sử dụng vòng lặp while để đưa λ tiệm cận với λ0 là nghiệm tối ưu của bài toán. Ứng với mỗi λ tìm được cần xét lại điều kiện ràng buộc. Li được khởi tạo một giá trị rất bé (dòng 14 – Thuật toán 2) để với các giá trị λ nằm trong khoảng 0;1 luôn tìm được một giá trị Li lớn nhất ứng với các giá trị Ui và Ri nằm trong tập dữ liệu đầu vào. Độ phức tạp của việc tìm ra Li lớn nhất là O(M*N) với M là số video và N là số mức chất lượng của video hay số mức băng thông được cấp cho các video. Để tìm được λ0, trong trường hợp xấu nhất phải duyệt hết tất cả các điểm giữ liệu các giới hạn chỉ dịch chuyển một đơn vị sau mỗi lần xét λ. Độ phức tạp giai đoạn này là O(N). Như vậy độ phức tạp của thuật toán sẽ là O(M*N2). Thuật toán phân bổ băng thông sử dụng hàng đợi ưu tiên Một mức chất lượng của video liên quan tới hai thông số là lợi ích người dùng U và tốc độ bit đại diện R (băng thông). Với một mức chất lượng được cải thiện lợi ích người dùng tăng lên nhưng đồng thời lượng băng thông cũng tăng lên. Đồ án tập trung vào lượng giá trị lợi ích được cải thiện so với mức băng thông tăng lên là bao nhiêu. Do đó giá trị α là tỷ số giữa lợi ích người dùng được cải thiện và mức băng thông tăng lên như là một giá trị để so sánh giữa các lần cải thiện chất lượng video cho người sao cho dùng thoả mãn băng thông tổng. Để thực hiện phân bổ băng thông cho nhiều người dùng điều quan trọng là cần biết người dùng nào nên được cấp thêm băng thông để cải thiện chất lượng video streaming với điều kiện băng thông sử dụng không vượt quá băng thông tổng. Giả sử ban đầu những người dùng streaming video được cấp một mức băng thông thấp nhất đủ để họ xem video với mức chất lượng thấp nhất và độ trễ lớn nhất cho phép. Tại mức chất lượng thứ hai người dùng nào có giá trị α lớn nhất sẽ được cấp thêm băng thông. Hình 3.2 là một ví dụ minh hoạ giá trị α của bốn người dùng tại mức chất lượng thứ nhất cải thiện lên mức hai. User3 có giá trị α cao nhất sẽ được chọn đầu tiên để cải thiện lên mức chất lượng thứ hai. Các user còn lại phải đợi lượt xét tiếp theo. Hình 3. 2 Giá trị tỷ số lợi ích người dùng trên mức băng thông được cải thiện. Như vậy để cải thiện các mức chất lượng video cho người dùng hay nói cách khác là phân bổ băng thông cho người dùng đồ án đề xuất phương pháp sử dụng hàng đợi ưu tiên. Hàng đợi ưu tiên cũng giống như một hàng đợi có tính chất thêm phần tử vào cuối và lấy ra phần tử ở đầu. Tuy nhiên hàng đợi ưu tiên có một tính chất đặc biệt là các phần tử trong hàng đợi ưu tiên được sắp xếp theo mức độ ưu tiên của nó. Phần tử với độ ưu tiên cao nhất sẽ được xếp lên đầu hàng đợi và phần tử có độ ưu tiên thấp nhất sẽ được chuyển xuống cuối. Nhờ cách này các phần tử có độ ưu tiên cao sẽ được phục vụ trước những phần tử có độ ưu tiên thấp. Khi lấy ra hay thêm vào một phần tử thì hàng đợi ưu tiên sẽ sắp xếp lại độ ưu tiên của các phần tử. Hàng đợi ưu tiên sẽ có kích thước hàng đợi bằng với số lượng video được streaming cùng một thời điểm. Ban đầu những người dùng cùng streaming video được cấp phát mức chất lượng thấp nhất (dòng 5 – Thuật toán 3), tính tỉ số lợi ích người dùng trên mức băng thông được cải thiện cho lần tiếp theo α và đưa vào hàng đợi ưu tiên. Video nào có tỉ số α lớn nhất sẽ được xếp lên đầu. Ví dụ Hình 3.3 video 4 (VD4) có tỉ số α lớn nhất sẽ được cải thiện lần đầu tiên. Khi VD4 được cải thiện lên mức chất lượng nếu điều kiện băng thông tổng sử dụng cho các video vẫn thấp hơn băng thông được cấp thì VD4 sẽ được đưa lại vào hàng đợi để chờ lượt cải thiện tiếp theo. Trong trường hợp điều kiện băng thông không thoả mãn thuật toán sẽ dừng và các video chỉ được streaming với mức chất lượng được cải thiện. Hình 3. 3 Nguyên lý phân cấp băng thông sử dụng hàng đợi ưu tiên. Hàng đợi ưu tiên được thiết kết bằng cách sử dụng cấu trúc heap với giá trị đại diện cho mỗi node sẽ là giá trị α. Ngoài ra, mỗi node sẽ có thêm các thuộc tính như chỉ số video vid, chỉ số mức chất lượng được cải thiện rid. Những người dùng cùng streaming video sẽ được cải thiện chất lượng video cho tới khi tổng băng thông sử dụng đạt tới mức băng thông tổng đường truyền hoặc cho tới khi không còn mức chất lượng để cải thiện. Khi không còn mức chất lượng để cải thiện heap rỗng, đồng nghĩa với việc các video đều được chơi ở mức chất lượng cao nhất. Chi tiết thuật toán được thể hiện tại Thuật toán 3. Thuật toán 3: Phân bổ băng thông cho hệ thống streaming nhiều video VBR sử dụng hàng đợi ưu tiên Input: data[i][j], RT , 1≤i ≤M, 1 ≤j ≤N //data[i][j] là điểm dữ liệu thứ j của video i. Output: select[i] , 1≤i ≤M //chỉ số mức chất lượng của video. 1 // Khởi tạo heap 2 heap = heap_init(); 3 bwuse= 0; 4 // Gán cho video i mức chất lượng thấp nhất và đẩy vào heap 5 for 1 ≤i ≤M do 6 node.r = data[i][0].r; 7 node.u = data[i][0].u; 8 node.alpha = data[i][1].u – data[i][0].udata[i][1].r – data[i][0].r; 9 node.vid= i; 10 node.rid= 0; 11 select[node.vid] = node.rid; 12 push_heap(heap, node); 13 bwuse += data[i][0].r; 14 end for 15 // Cải thiện chất lượng video sử dụng hàng đợi ưu tiên – cấu trúc heap 16 while !is_empty(heap) do 17 h = pop_heap(heap); 18 bwuse = bwuse + data[h.vid][h.rid+ 1] –h.r 19 if bw_use ≤ RT and h.r_id + 1≤N 20 h.rid =h.rid + 1; 21 h.u = data[h.vid][h.rid].u; 22 h.r = data[h.vid][h.rid].r; 23 h.alpha =datah.vidh.rid+1.u –h.udatah.vidh.rid+1.r -h.r; 24 select[vid] =h.rid; 25 push_heap(heap, h); 26 else break; 27 end if 28 end while 29 Đối với mỗi lần đưa phần tử vào heap có độ cao log⁡(M) và sắp xếp lại thứ tự ưu tiên của phần tử đó có độ phức tạp là O(logM). Trong trường hợp xấu nhất của thuật toán các video đều đạt mức chất lượng tốt nhất thì số lần cải thiện chất lượng cho M video sẽ là M×N, độ phức tạp cho việc cải thiện chất lượng là OM×N. Do mỗi lần cải thiện chất lượng video là một lần thêm vào heap một mức chất lượng mới vì vậy độ phức tạp của cả thuật toán 3 sẽ là O(M×N×logM). Từ kết quả độ phức tạp của thuật toán sử dụng nhân tử Lagrange (thuật toán 2) so với độ phức tạp của thuật toán sử dụng hàng đợi ưu tiên (thuật toán 3), ta suy ra trong trường hợp xấu nhất thuật toán 2 cho kết quả thực thi nhanh hơn khi số lượng video M>2N. Tuy nhiên, số mức băng thông N được cấp cho video khá cao do vậy thuật toán 3 sẽ cho thời gian thực thi tốt hơn. Kết quả thực nghiệm và đánh giá Tại phần thực nghiệm trong Chương III, đồ án sử dụng mô hình thích ứng chất lượng đã nêu trong Chương II để tạo dữ liệu đầu vào. Cụ thể với năm video Lamb (video 1), Sony (video 2), Star (video 3), Terminate (video 4), Tokyo (video 5) được lấy từ [26], mỗi video sẽ có sáu mức chất lượng tương ứng với các tham số lượng tử QP là 48, 42, 38, 34, 28, 22. Ứng với mỗi mức chất lượng, các video được phân ra thành 294 phân đoạn với tốc độ bit của mỗi phân đoạn là khách nhau. Mỗi video được phân cấp 20 mức băng thông theo mô hình thích ứng chất lượng ở chương II và toàn bộ dữ liệu này sẽ được lưu tại máy chủ. Kết quả chạy của thuật toán Lagrange và thuật toán sử dụng hàng đợi ưu tiên được chỉ ra tại Bảng 3.3 và Bảng 3.4. Với băng thông tổng được cấp cho đường truyền từ 4000Kbps tới 14000Kbps. Bảng 3. 3 Kết quả phân bổ băng thông sử dụng nhân tử Lagrange. BW (Kbps) Video 1 Video 2 Video 3 Video 4 Video 5 BW use R (Kbps) U R (Kbps) U R (Kbps) U R (Kbps) U R (Kbps) U 4000 551 4,74 1136 3,21 365 4,62 1440 3,50 480 4,26 3971 5000 551 4,74 1136 3,21 563 4,82 1440 3,50 679 4,55 4369 6000 551 4,74 2420 4,04 563 4,82 1440 3,50 877 4,67 5851 7000 551 4,74 2420 4,04 563 4,82 1440 3,50 877 4,67 5851 8000 767 4,86 2420 4,04 762 4,93 2240 3,96 1275 4,87 7463 9000 767 4,86 2420 4,04 762 4,93 3039 4,30 1275 4,87 8263 10000 983 4,93 2420 4,04 960 4,99 3839 4,53 1474 4,94 9677 11000 983 4,93 2420 4,04 960 4,99 3839 4,53 1474 4,94 9677 12000 983 4,93 2420 4,04 960 4,99 3839 4,53 1474 4,94 9677 13000 983 4,93 4987 4,62 960 4,99 3839 4,53 1474 4,94 12244 14000 1200 4,97 5629 4,74 960 4,99 4639 4,69 1474 4,94 13902 Bảng 3. 4 Kết quả phân bổ băng thông sử dụng hàng đợi ưu tiên. BW (Kbps) Video 1 Video 2 Video 3 Video 4 Video 5 BW use R (Kbps) U R (Kbps) U R (Kbps) U R (Kbps) U R (Kbps) U 4000 551 4,74 1136 3,21 365 4,62 1440 3,50 480 4,26 3971 5000 551 4,74 1136 3,21 563 4,82 1440 3,50 679 4,55 4369 6000 551 4,74 1778 3,61 663 4,88 1440 3,50 1076 4,76 5507 7000 767 4,86 1778 3,61 762 4,93 2240 3,96 1275 4,87 6822 8000 767 4,86 2420 4,04 762 4,93 2240 3,96 1275 4,87 7463 9000 983 4,93 2420 4,04 861 4,97 3039 4,30 1275 4,87 8579 10000 983 4,93 2420 4,04 861 4,97 3839 4,53 1474 4,94 9577 11000 983 4,93 3703 4,30 861 4,97 3839 4,53 1474 4,94 10861 12000 983 4,93 4345 4,47 861 4,97 3839 4,53 1474 4,94 11503 13000 983 4,93 4987 4,62 1059 5,00 3839 4,53 1474 4,94 12343 14000 1200 4,97 4987 4,62 1059 5,00 4639 4,69 1474 4,94 13359 Như vậy ứng với mỗi mức băng thông tổng của đường truyền các thuật toán luôn tìm được cho mỗi video một mức băng thông mà tại đó giá trị lợi ích U của người dùng được tối đa hoá. Hình 3.4 là mức lợi ích trung bình của hai thuật toán đồ án đề xuất đạt được so với mức lợi ích trung bình của phương pháp thông thường chỉ streaming dữ liệu thích ứng mà không sử dụng mô hình thích ứng thay thế phân đoạn và thoả hiệp giữa chất lượng và độ trễ. Hình 3. 4 Lợi ích trung bình ngươi dùng giữa hai thuật toán đề xuất và phương pháp streaming thông thường. Có thể thấy hai thuật toán đề xuất cho mức lợi ích trung bình gần tương đương nhau. Phương pháp sử dụng hàng đợi ưu tiên có chút tốt hơn ở một số mức băng thông tổng như 7000Kbps hay 12000kbps. So với phương pháp thông thường, lợi ích trung bình được cải thiện lên gần 1 điểm. Để đánh giá hai thuật toán xây dựng đồ án so sánh kết quả của hai thuật toán đạt được với kết quả của thuật toán vét cạn. Hình 3.5 là kết quả mức băng thông sử dụng so với băng thông tổng của từng thuật toán. Có thể thấy, thuật toán vét cạn cho khả năng sử dụng mức băng thông tối đa và gần với mức băng thông tổng của đường truyền nhất. Hình 3. 5 Mức băng thông sử dụng của ba thuật toán. Thuật toán sử dụng hàng đợi ưu tiên với mức băng thông sử dụng rất gần với thuật toán vét cạn do vậy thuật toán này cho kết quả khá chính xác mà thời gian thực hiện thấp hơn nhiều so với thuật toán vét cạn. Hình 3. 6 So sánh ích trung bình của người dùng giữa hai thuật toán đề xuất và thuật toán vét cạn Hình 3.6 cho thấy lợi ích trung bình của người dùng giữa hai phương pháp đề xuất và phương pháp sử dụng thuật toán vét cạn là gần tương đương nhau. Trong khi hai thuật toán đề xuất cho thời gian thực thi tốt hơn nhiều so với thời gian thực thi của thuật toán vét cạn. Hình 3. 7 Thời gian thực hiện của thuật toán vét cạn so với hai thuật toán đề xuất. Hình 3.7 là thời gian thực hiện của thuật toán vét cạn so với hai thuật toán đề xuất trên bộ dữ liệu năm video đã nêu. Các thuật toán được thực hiện trên máy HP-Probook G2 với bộ nhớ 4GB, hai lõi vật lý và tốc độ xử lý 1.7GHz chạy hệ điều hành Ubuntu 16.04. Thuật toán vét cạn với độ phức tạp là O(MN) thời gian thực hiện được biểu diễn bằng đường màu đỏ trên cùng. Có thể thấy thuật toán vét cạn cho thời gian thực hiện ở mức từ 20 đến 35ms lâu hơn rất nhiều so với hai thuật toán còn lại (đường màu vàng và màu tím phía dưới) chỉ ở mức dưới 100μs. Khi số lượng video tăng lên hàng nghìn thì thuật toán vét cạn cho thời gian chạy là rất lớn không khả thi với hệ thống streaming video. Hai thuật toán đề xuất cho thời gian chạy chỉ cỡ ms khi số lượng video tăng lên hàng nghìn video. Hình 3. 8 Thời gian thực hiện của hai thuật toán đề xuất khi số lượng dữ liệu lớn. Hình 3.8 hai thuật toán đề xuất cho thời gian thực hiện chỉ ở cỡ ms nên hoàn toàn phù hợp với hệ thống streamming lớn. Nhìn một cách tổng quan thuật toán sử dụng hàng đợi ưu tiên cho thời gian thực hiện tốt hơn thuật toán sử dụng nhân từ Lagrange. Kết luận chương Trong Chương 3, đồ án đã nghiên cứu, xây dựng và triển khai hai thuật toán phân bổ băng thông cho hệ thống streaming nhiều video có tốc độ bit biến đổi trong đường truyền có hạn chế về băng thông. Kết quả thu được cho thấy lợi ích trung bình của người dùng tăng lên gần 1 điểm. Đồng thời, thời gian thực thi của hai thuật toán là khả thi đối với hệ thống streaming video có số lượng lên đến hàng nghìn người dùng. KẾT LUẬN Kết luận chung Đồ án đã trình bày những cơ sở lý thuyết về truyền thông đa phương tiện. Nêu lên sự phát triển và những đặc điểm của công nghệ streaming video, kiến trúc và nguyên lý hoạt động của công nghệ streaming video thích ứng HAS. Đồng thời phân tích các yếu tố ảnh hưởng trực tiếp đến chất lượng trải nghiệm của người dùng trong hệ thống HAS. Từ đó trình bày mô hình thích ứng tốc độ bit thoả hiệp giữa chất lượng video và độ trễ để có được lợi ích người dùng là lớn nhất. Với kết quả thu được đồ án trình bày hai thuật toán là sử dụng nhân tử Lagrange và hàng đợi ưu tiên để thực hiện phân bổ băng thông cho hệ thống streaming nhiều video VBR. Kết quả thu được là lợi ích người dùng được tính thông qua các mô hình tham số tăng lên trung bình 1 điểm và thời gian thực hiện của các thuật toán đề xuất chỉ cỡ ms khi số lượng video tăng lên hàng nghìn là hoàn toàn khả thi với hệ thống streaming nhiều video. Hướng phát triển Do hạn chế về mặt thời gian thực hiện một số công việc của đồ án vẫn chưa hoàn thành. Trong thời gian tới em sẽ tiếp tục thực hiện một số công việc còn lại bao gồm: Xây dựng hệ thống streaming bao gồm máy chủ, máy khách và khối điều khiển triển khai giải pháp phân bổ băng thông trên mô hình xây dựng được. Thực hiện đánh giá kết quả theo phương pháp chủ quan, kiểm tra quan điểm trải nghiệm của người dùng trên hệ thống thực tế để so sánh với kết quả của các mô hình toán học. TÀI LIỆU THAM KHẢO https://www.renderforest.com/blog/video-marketing-statistics, truy nhập cuối cùng ngày 26/3/2019. Begen, A. C., T. Akgul, and M. Baugher, “Watching video over the web: Part i: Streaming protocols,” IEEE Internet Computing, Vol. 15, pp. 54-63, Mar. 2011. Jiang, J., V. Sekar, and H. Zhang, “Improving fairness, efficiency, and stability in http-based adaptive video streaming with festive,” IEEE/ACM Transactions on Networking, Vol. 22, pp. 326–340, Feb. 2014. Sun, Y., X. Yin, J. Jiang, V. Sekar, F. Lin, N. Wang, T. Liu, and B. Sinopoli, “Cs2p: Improving video bitrate selection and adaptation with data-driven throughput prediction”, ACM Conference, Florianopolis – Brazil, Aug. 2016, pp. 272 – 285. Saamer Akhshabi, Ali C Begen, Constantine Dovrolis, “An experimental evaluation of rate-adaptation algorithms in adaptive streaming over HTTP,” ACM Conference on Multimedia systems, San Jose, USA, Feb. 2011, pp 157 – 168. Steven Benno, Andre Beck, Jairo O Esteban, Les Wu, Ray Miller, “Wilo: A Rate Determination Algorithm for HAS video in wireless network and low-delay applications,” IEEE Globecom Workshop, Atlanta, USA, Dec. 2013. Chao Zhou, Chia-Wen Lin, Xinggong Zhang, Zongming Guo, “A Control-Theoric Approach to Rate Adaption for DASH Over Multiple Content Distribution Servers,” IEEE Transactions on Circuts and Systems for Video Technology, Vol. 24, pp. 681 – 694, April. 2014. Ayub Bokani, Mahbub Hassan, Salil Kanhere, “HTTP-Base Adaptive Streaming for Mobile Clients using Markov Decision Process,” International Packet Video Workshop, San Jose, USA, Dec. 2013. Maxim Claeys, Steven Latre, Jeroen Famaey, Filip De Tunck, “Design and Evaluation of a self-learning HTTP adaptive video streaming client,” IEEE Communications Letters, Vol. 18, pp.716 – 719, Feb. 2014. Le, H. T, “Quality Improvement for HTTP Adaptive Streaming over Mobile Networks,” Ph. D. Thesis, University of Aizu, 2017. Niels Laukens (2011). Adaptive streaming – a brief tutorial. [Online]. Available: https://tech.ebu.ch/docs/techreview/trev_2011-Q1_adaptive-streaming_laukens.pdf. Baochun Li, Zhi Wang, Jiangchuan Liu, Wenwu Zhu, “Two decades of internet video streaming: A retrospective view,” ACM Transactions on Multimedia Computing, Communication, and Application, No. 33, Oct. 2013. T. C. Thang, Q.-D. Ho, J. W. Kang, and A. T. Pham, “Adaptive streaming of audiovisual content using MPEG DASH,” IEEE Transactions on Consumer Electronics, Vol. 58, pp. 78–85, Feb. 2012. Vengatanathan Krishnamoorthi (2018). “Efficent HTTP-based Adaptive Streaming of Linear and Interactive video,” Ph. D. Thesis, Linkoping University. Miran Raha, Jaime Lioret Mauri, Laura Garcia, “Survey of transportation of adaptive multimedia streaming service in Internet,” Network Protocols & Algorithms, Vol. 9, No. 1-2, Apr. 2017. Adarsh Golikeri, Z. Jane Wang, Panos Nasiopoulos, “Robust digital video watermarking scheme for H.264 advanced video coding standard,” Jounal of Electronic Imaging, Vol. 16, Oct. 2007. Nguyen Thi Kim Thoa (2019), “Một số giải pháp nâng cao chất lượng streaming thích ứng trên nền giao thức HTTP,” Luận án Tiến sĩ, Hanoi University of Science and Tecnology. Zhang, D., H. He, and W. Li, “Bitrate allocation among multiple video streams to maximize profit in content delivery networks,” Personal Ubiquitous Comput, Vol. 20, pp. 385–396, Jun. 2016. Cicco, L. D., S. Mascolo, and D. Calamita, “A resource allocation controller for cloud-based adaptive video streaming,” IEEE International Conference on Communications Workshops (ICC), pp. 723–727, Jun. 2013. Truong Cong Thang, Young M. Ro, “Practical estimation techniques of traffic specification for VBR video services,” Proceedings of SPIE – The International Society for Optical Engineering, Santa Clara, USA, May. 2003. Nguyen, D. V., D. M. Nguyen, H. T. Tran, N. P. Ngoc, A. T. Pham, and T. C. Thang, “Quality-delay tradeoff optimization in multi-bitrate adaptive streaming,” IEEE International Conference on Consumer Electronics (ICCE), pp. 66–67, Jan. 2015. Nguyen, D. V., H. T. Le, A. T. Pham, T. C. Thang, J. Y. Lee, and K. Yun, “Adaptive home surveillance system using http streaming,” International Joint Conference on Awareness Science and Technology Ubi-Media Computing (iCAST 2013 UMEDIA 2013), pp. 579–584, Nov. 2013. Marcus Barkowsky, Margret H. Pinson, Romuald Pepion, Patrick Le Callet, “Analysis of Freely Avaliable Dataset for HDTV including coding and transmission distortion,” Fifth International Workshop on Video Processing and Quality Metrics (VPQM), Scottsdale, USA, Jan. 2010. D. E. Wrege, E. W. Knightly, Hui Zhang, J. Liebeherr, “Determinnistic delay bounds for VBR video in packet-switching network: Fundamental limits and practical trade-offs,” IEEE/ACM Transactions on Networking, Vol. 4, pp. 352 – 362, Jun. 1996. T. Hossfeld, S. Egger, R. Scharz, M. Fiedler, K. Masuch, C. Lorentzen, “Initial delay vs. interuptions: Between the devil and the deep blue sea,” 2012 Fourth International Workshop on Quality of Multimedia Experience, Yarra Valley, VIC, Australia, Jul. 2012. Van der Auwera, G., P. David, and M. Reisslein, “Traffic and quality characterization of single-layer video streams encoded with the h.264/mpeg-4 advanced video coding standard and scalable video coding extension,” IEEE Transactions on Broadcasting, Vol. 54, pp. 698–718, Sep. 2008. PHỤ LỤC Phụ lục 1. Hướng dẫn cài đặt mã code. Yêu cầu: Hệ điều hành Ubuntu phiên bản 16.04 trở lên. Trình biên dịch GCC phiên bản 2.7 trở lên. Mã code trương trình. Cài đặt: Bên trong tệp main.c sẽ có các chế độ được định nghĩa như: MAIN: Chế độ chạy thuật toán thích ứng chất lượng (Chương II) và phân bổ băng thông cho dữ liệu tương ứng (Chương III). ONE_VIDEO: Chế độ chạy thích ứng chất lượng cho một video (Chương II). TIMING: Chế độ chạy đo thời gian cho các thuật toán khi số lượng video lớn. Chọn một chế độ và mở terminal tại thư mục chứa tệp main.c và chạy hai câu lệnh bên dưới: $ make $ ./main.c Kết quả của từng chế độ chạy được hiển thị ra màn hình và lưu vào tệp kết quả tương ứng với từng chế độ.