Độ trễ trong mạng di động multihop hướng nội dung sử dụng phương pháp phân mảnh tệp tin

ạng với 0 < 훾 < 1 
một cách độc lập và ngẫu nhiên. Trong bài báo này, thay vì 3.1. Phương pháp thu nhận tệp tin 
giả thiết rằng kích thước của các tệp tin đủ nhỏ để quá trình Trong mục này, chúng tôi sẽ mô tả hai phương pháp thu 
truyền tải luôn kết thúc trong một khe thời gian như trường nhận tệp tin được mô tả trong Hình 1, thể hiện cách thức 퐾 
hợp sử dụng mô hình fluid, chúng tôi giả thiết rằng, mỗi mảnh tin của tệp tin yêu cầu được thu thập. 
 훽
tệp tin được cấu thành bởi 퐾 = Θ(푛 ), với 0 < 훽 < 훾, Thu nhận tuần tự: Tất cả 퐾 mảnh tin của tệp tin sẽ được 
mảnh tin rời rạc có kích cỡ bằng nhau, sao cho mỗi mảnh tải một cách tuần tự bởi nút mạng yêu cầu. Như thể hiện ở 
tin có thể được truyền đi hoàn toàn tới nút mạng đích trong Hình 1(a), nút mạng sẽ tìm mảnh tin số 1 gần nhất của tệp tin 
khoảng thời gian tương ứng với một khe thời gian. Mỗi nút , tiếp theo là mảnh tin số 2 gần nhất của tệp tin , và cứ thế 
mạng được trang bị bộ nhớ đệm dữ liệu có khả năng lưu tiếp tục cho đến khi tải đủ 퐾 mảnh tin của tệp tin mong muốn. 
trữ mảnh tin khác nhau. 
 푆 = Θ(퐾) an()
 Chúng tôi giả sử rằng, xác suất yêu cầu đối với tệp tin 
 ∈ ℳ với ℳ = {1,  , } tuân theo phân bố Zipf và 
 −훼 (2) (3)
 Xm,1
được tính theo công thức = , trong đó α là hệ số 
 훼( ) Xm,2
 (1)
 −훼 Xm,3
Zipf và 훼( ) = ∑푖=1 푖 . Đường định tuyến
 Trong mạng vô tuyến hướng nội dung, kỹ thuật đệm dữ Nốt mạng yêu cầu
liệu được thực hiện theo hai bước, bước đệm dữ liệu và 
bước truyền tin. Hai bước này tương ứng với quá trình lập a) Thu nhận tuần tự 
kịch bản lưu trữ các tệp tin tại bộ nhớ đệm của các nút mạng an()
và quá trình định tuyến đường đi cho tệp tin được gửi tới 
 (3)
nút mạng đích. Chúng ta xem xét bước đệm dữ liệu trước, (2)
bước quyết định mỗi mảnh tin sẽ được lưu tại bộ nhớ đệm (1) Xm,1
 Xm,2
của nút mạng nào. ,푖 là ký hiệu của số lượng bản sao của Xm,3
mảnh tin 푖 thuộc tệp tin ∈ ℳ với 푖 ∈ {1,  , 퐾}. Theo Đường định tuyến
 Nốt mạng yêu cầu
đó, chúng ta có thể dễ dàng thấy rằng ,푖 = với mọi 
푖 ∈ {1,  , 퐾}, với là số lượng bản sao của tệp tin trên b) Thu nhận ngẫu nhiên 
toàn mạng. Với giới hạn tổng bộ nhớ đệm tại các nút mạng Hình 1. Phương pháp thu nhận mảnh tin 
là 푛푆, chúng ta có công thức sau: Giao thức định tuyến truyền tin 
 ∑ =1 퐾 ≤ 푛푆. (1) Thu nhận ngẫu nhiên: Nút mạng sẽ tải mảnh tin một 
 Tương tự như các nghiên cứu [7], [9], [11], chúng tôi cách ngẫu nhiên. Như thể hiện trên Hình 1(b), nút mạng 
sử dụng phương pháp lưu trữ ngẫu nhiên sao cho các bản trước hết sẽ nhận được mảnh tin số 2 của tệp tin , là mảnh 
sao của mỗi mảnh tin được lưu trữ đều và ngẫu nhiên tại tin gần nó nhất, tiếp theo đó, nút mạng sẽ tải mảnh tin số 2, 
bộ nhớ đệm của các nút mạng. Xin nhắc lại rằng, tại bước là mảnh tin gần nó thứ hai và cứ tiếp tục như thế cho đến 
truyền tin, vị trí của nút mạng đang lưu giữ mảnh tin khi tải đủ 퐾 mảnh tin của tệp tin mong muốn. 
ISSN 1859-1531 - TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ ĐẠI HỌC ĐÀ NẴNG, SỐ 11(120).2017, QUYỂN 2 3 
 Trong mục này, chúng tôi sẽ giới thiệu giao thức định số lượng bản sao của mảnh tin tải mảnh tin 푖 của tệp tin 
tuyến được sử dụng trong truyền tin của mô hình mạng ad được lưu trữ tại bộ nhớ đệm của các nút mạng trong mạng. 
hoc vô tuyến di động hướng nội dung. Để thực hiện truyền Độ trễ truyền tin trong mạng vô tuyến hướng nội dung 
dẫn đa bước multihop, toàn bộ mạng đơn vị sẽ được chia sẽ được phân tích dựa trên hai phương pháp thu nhận tin 
 −1
thành (푛) ô vuông định tuyến giống nhau, với như sau: 
 log 푛
 (푛) = Θ ( ) để đảm bảo rằng mỗi ô vuông định tuyến 
 푛 a. Thu nhận tuần tự 
luôn chứa ít nhất 01 nút mạng với xác suất cao [3]. Giả sử 
 Trong trường hợp này, tất cả 퐾 mảnh tin của mỗi tệp 
rằng mỗi nút mạng luôn biết nút mạng đích đang chứa mảnh 
 tin sẽ được thu nhận một cách tuần tự theo số thứ tự. Từ Bổ 
tin mong muốn ở đâu để gửi bản tin yêu cầu tải. Giao thức 
 đề 1, sử dụng giao thức định tuyến truyền tin được mô tả ở 
đa bước multihop sẽ được thực hiện ở bước truyền tin dựa 푛
 mục trước với Θ ( ) ô vuông định tuyến, chúng ta có thể 
trên các ô vuông định tuyến có kích thước (푛). Do sử dụng log 푛
mô hình giao thức được mô tả ở cuối Mục II, mỗi ô vuông thấy rằng, số lượng bản ghi của mỗi mảnh tin dao động ở 
 푛
định tuyến sẽ hoạt động một cách định kỳ sau mỗi 1 + khe mức Θ ( ) là đủ để đảm bảo để mảnh tin mong muốn có 
thời gian để tránh nhiễu với > 0 là số tự nhiên cho trước. log 푛
 thể được truyền đến nút mạng đích trong khoảng thời gian 
 an() hữu hạn Θ(1). Do đó, chúng tôi thiết lập điều kiện đối với 
 Nốt mạng yêu cầu số lượng bản sao của mỗi tệp tin trong mạng như sau: 
 1 2 푛
 C C Nốt mạng chuyển tiếp ≤ ,
 C3 log 푛
 Nốt mạng đích { (2) 
 ≥ 1
 C0 Các bước truyền tin 
 Định lý sau đây được thiết lập thể hiện cách tính độ trễ 
 Đường đi di động của nốt 
 mạng truyền tải trong cấu hình mạng được thiết lập sử dụng 
 phương pháp thu nhận mảnh tin tuần tự. 
 a) Nút mạng gửi bản tin yêu cầu tải tin Định lý 1: Trong mạng vô tuyến di động hướng nội 
 an() dung với 퐾 mảnh tin của tệp tin bất kỳ được thu nhận theo 
 phương pháp tuần tự, độ trễ truyền tin được tính như sau: 
 Nốt mạng yêu cầu
 3 Nốt mạng chuyển tiếp 퐾
 C (푛) = Θ (∑ ). (3) 
 Nốt mạng đích =1 log 푛
 √ 
 푛 
 C0 Các bước truyền tin
 Chứng minh: Từ Bổ đề 1, chúng ta có thời gian để nút mạng 
 4 Đường đi di động của nốt 
 C mạng
 C5 đích nhận được một mảnh tin bất kỳ của tệp tin thông qua 
 C6
 1
 giao thức multihop là Θ ( ). Theo đó, để nhận được 
 b) Tệp tin được truyền về nút mạng yêu cầu log 푛
 √ 
 Hình 2. Giao thức định tuyến truyền tin 푛
 toàn bộ 퐾 mảnh tin của tệp tin sẽ cần khoảng thời gian là 
 Chúng tôi áp dụng giao thức định tuyến giống như 
nghiên cứu [11], hoạt động dựa trên sơ đồ mạng sao cho 퐾
 Θ ( ). Sử dụng phép tính trung bình đối với toàn bộ các 
khoảng cách giữa nút mạng yêu cầu và nút mạng đích là log 푛
 √ 
ngắn nhất. Nếu nút mạng đích nằm trong phạm vi truyền của 푛 
nút mạng yêu cầu chứa mảnh tin mong muốn, yêu cầu tải sẽ tệp tin trong thư viện, chúng ta nhận được công thức (3). 
 푛
được phục vụ trong vòng khoảng thời gian tương ứng với Trong trường hợp đặc biệt, khi = với mọi 
một khe thời gian. Nếu không, như thể hiện ở Hình 2, nút log 푛
 ∈ ℳ, (푛) = Θ(퐾) là mức trễ truyền tin tốt nhất chúng 
mạng yêu cầu tải tin sẽ phải tìm kiếm nút mạng nào gần nhất 
 ta có thể nhận được. 
có chứa mảnh tin mong muốn theo khoảng cách Euclidean. 
Sau đó, bản tin yêu cầu tải sẽ được gửi đến nút mạng đích Từ (1), (2), (3) và Định lý 1, chúng ta xây dựng bài toán 
chứa tệp tin mong muốn dọc theo các ô vuông định tuyến tối ưu hóa như sau: 
bằng phương pháp đa bước multihop. Mảnh tin được yêu cầu b. Bài toán 1: Trường hợp thu nhận mảnh tin tuần tự 
tải sẽ được gửi về, đuổi theo ngược lại hướng nút mạng yêu 퐾
 min ∑ (4) 
 =1 log 푛
cầu di chuyển bằng phương pháp đa bước multihop. { } ∈ℳ √ 
 푛 
3.2. Phân tích độ trễ truyền tin 푆
 Điều kiện: ∑ ≤ 푛 
 Độ trễ truyền tin luôn phụ thuộc vào khoảng cách giữa =1 퐾
 푛
nguồn và đích truyền tin. Tương tự như [10], [11] để tính được 1 ≤ ≤ với ∀ ∈ ℳ. 
độ trễ truyền tin của mạng, chúng tôi thiết lập bổ đề sau: log 푛
 c. Bài toán 2: Thu nhận mảnh tin ngẫu nhiên 
 Bổ đề 1: Đối với nút mạng di động yêu cầu tải mảnh 
tin 푖 của tệp tin ∈ ℳ, khoảng cách ban đầu trung bình Trong trường hợp này, nút mạng đích sẽ nhận 퐾 mảnh 
giữa nút mạng yêu cầu tải tin và nút mạng gần nhất đang tin của tệp tin mong muốn theo phương pháp ngẫu nhiên. 
 1
 Xem xét tệp tin bất kỳ ∈ ℳ, ta thấy có tổng 퐾 mảnh 
lưu trữ mảnh tin mong muốn là 훩 ( ), trong đó ,푖 là 
 √ ,푖
4 Đỗ Trung Anh, Đặng Hoài Bắc 
tin trên toàn mạng. Áp dụng Bổ đề 1, ta có khoảng cách truyền (푛) = Θ(퐾). Trường hợp ngược lại, = 휔(푆 log 푛), sử 
 1
tin trung bình đối với mảnh tin đầu tiên là Θ ( ). Khoảng dụng (1), (5) và Định lý 2, chúng tôi thiết lập bài toán tối 
 √퐾 ưu thứ hai như sau: 
cách truyền tin trung bình đối với mảnh tin thứ hai là 
 1
Θ ( ) và tương tự ta có khoảng cách truyền tin trung 퐾
 √(퐾−1) min ∑ 
 { } √log 푛
 ∈ℳ 
bình đối với các mảnh tin được thu nhận tiếp theo. =1 푛 
 푛
 Trước tiên, ta xem xét trường hợp 퐾 ≥ . Đặt 푙 
 log 푛 푆
 Điều kiện: ∑ =1 ≤ 푛 
là số thứ tự nhỏ nhất của các mảnh tin sao cho 퐾
 푛 푛
(퐾 − 푙 + 1) ≤ . Áp dụng Bổ đề 1, ta tính được 1 ≤ ≤ với ∀ ∈ ℳ. 
 log 푛 퐾 log 푛
khoảng thời gian cần thiết để nút mạng đích nhận được đủ Các điều kiện Karush-Kuhn-Tucker (KKT) đối với Bài 
퐾 mảnh tin của tệp tin mong muốn là toán 2 như sau: 
 ∇ℒ
 1
 퐾−1 ∗ = 0 (7)
Θ(푙 − 1)+∑ Θ ( ). Sử dụng thuộc ∇ 
 푗=푙 −1 log 푛 
 √ (퐾−푗) ∗
 푛 휆 ≥ 0 (8)
 ∗
tính của hàm Riemann zeta, ta tính được 휇 ≥ 0 (9)
 ∗ ∗ 푛 
 휇 ( − ) = 0 (10)
 1 √퐾−푙 +1 퐾 log 푛
∑퐾−1 Θ ( ) = Θ ( ). Từ định 
 푗=푙 −1 log 푛 log 푛 
 √ (퐾−푗) √ 푆
 푛 푛 휆∗ ( ∑ ∗ − 푛 ) = 0 (11)
nghĩa của tham số , theo luật số lớn và các định nghĩa về 퐾
 푙 { =1
 푛
xấp xỉ ở Mục I, ta có (퐾 − 푙 + 1) = Θ ( ). Theo 
 log 푛 với mọi ∀ ∈ ℳ. Từ (7), ta có: 
 ∗ ∗
đó, ta nhận được độ trễ truyền tải đối với tệp tin được − + 휆 + 휇 = 0 (12) 
 √ ∗3
tính Θ(푙 − 1) + Θ(퐾 − 푙 + 1) = Θ(퐾), là giá trị tương 2 
ứng với mức trễ truyền tải tốt nhất ta có thể nhận được từ 
 Với = 휔(푆 log 푛), chúng ta dễ dàng thấy rằng, luôn 
cấu hình mạng đề xuất. Từ đây, ta có thể nhận thấy rằng, 푛
 tồn tại ít nhất một tệp tin ∈ ℳ sao cho ∗ < . 
số lượng bản sao của mỗi tệp tin trên mạng không cần thiết 퐾 log 푛
 푛 ∗
phải lớn hơn . Chúng tôi thiết lập điều kiện sau: Trong trường hợp này, ta nhận được 휇 = 0 từ (10), điều 
 Klog 푛 này dẫn đến 휆∗ > 0 khi xem xét (12). Sử dụng (11), ta có 
 푛
 ≤ , ∗ 푆
 Klog 푛 ∑ = 푛 . 
 { (5) =1 퐾
 ≥ 1 So sánh với trường hợp độ trễ truyền tin của trường hợp 
 Tiếp theo, chung tôi thiết lập định lý sau đây thể hiện sử dụng phương pháp thu nhận mảnh tin tuần tự, ta thấy rằng, 
 3
cách tính độ trễ truyền tin cho trường hợp thu nhận mảnh với 훼 > , cả hai trường hợp đều đưa ra mức trễ truyền tin 
 2
tin theo phương pháp ngẫu nhiên. 3
 lý tưởng là (푛) = Θ(퐾). Tuy nhiên, với 훼 ≤ , độ trễ 
 Định lý 2: Trong mạng vô tuyến di động hướng nội dung 2
với 퐾 mảnh tin của tệp tin bất kỳ được thu nhận theo phương truyền tin ở trường hợp sử dụng phương pháp thu nhận ngẫu 
pháp ngẫu nhiên, độ trễ truyền tin được tính như sau: nhiên luôn cho kết quả tốt hơn so với trường hợp tuần tự. 
 퐾 3.3. Tính toán máy tính 
 (푛) = Θ (∑ =1 log 푛 ). (6) 
 √ ∗
 푛 Để kiểm tra lại nghiệm tối ưu với ∈ ℳ, chúng 
 Chứng minh: Từ Bổ đề 1, sử dụng thuộc tính của hàm tôi sử dụng phần mềm Mathematica trên máy tính để tìm 
Riemann zeta, chúng ta có thể tính được khoảng thời gian nghiệm với các tham số cụ thể như sau: 푛 = 300; 
cần thiết để nút mạng đích nhận được 퐾 mảnh tin theo = 200; 퐾 = 20; 푆 = 50; 훼 = 1,2. Nghiệm tìm được 
 ∗
 của Bài toán 1 và Bài toán 2 được thể hiện ở Hình 3. 
 1
phương pháp ngẫu nhiên là ∑퐾−1 Θ ( ) =
 푗=1 log 푛
 √ (퐾−푗) 
 푛 
 1 1 퐾
∑퐾−1 Θ ( ) = Θ ( √ ). Sử dụng phép 
 푗=1 √퐾−푗 log 푛 log 푛
 √ √ 
 푛 푛 
tính trung bình đối với toàn bộ các tệp tin trong thư viện, 
chúng ta nhận được công thức (6). 
 Từ thực tế tổng dung lượng lưu trữ của mạng là 푛푆, nếu 
 푆푛
 = ( 푛 ) = (푆 log 푛), chúng ta có thể lưu trữ 
 log 푛 
 푛
Θ ( ) bản sao cho mỗi tệp tin trong mạng, dẫn đến kết Hình 3. So sánh cách thức lưu trữ đệm dữ liệu tối ưu nghiệm ∗ 
 Klog 푛 
 của hai trường hợp thu nhận mảnh tin tuần tự và ngẫu nhiên 
quả là chúng ta luôn nhận được độ trễ truyền tin tốt nhất 
ISSN 1859-1531 - TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ ĐẠI HỌC ĐÀ NẴNG, SỐ 11(120).2017, QUYỂN 2 5 
 Chúng ta nhận thấy rằng, giới hạn trên của nghiệm tối achieves optimal capacity scaling in ad hoc networks”, IEEE Trans. 
 ∗ Inf. Theory, Vol. 53, No. 10, Oct. 2007, pp. 3549–3572. 
ưu nhận được ở Bài toán 2 nhỏ hơn ở Bài toán 1. Điều 
này đúng với các điều kiện tại (2) và (5), phù hợp với kết [5] M. Grossglauser and D. N. C. Tse, “Mobility increases the capacity 
 of ad hoc wireless networks”, IEEE/ACM Trans. Netw., Vol. 10, No. 
quả phân tích tại hai mục trước của phần này. 4, Aug. 2002, pp. 477–486. 
 [6] A. El Gamal, J. Mammen, B. Prabhakar, and D. Shah, “Optimal 
4. Kết luận throughput–delay scaling in wireless networks – Part I: The fluid 
 Trong bài báo này, chúng tôi đã sử dụng kỹ thuật bộ model”, IEEE Trans. Inf. Theory, Vol. 52, No. 6, Jun. 2006, pp. 
nhớ đệm trong mạng vô tuyến hướng nội dung. Độ biến 2568–2592. 
 [7] S. Gitzenis, G. S. Paschos, and L. Tassiulas, “Asymptotic laws for 
thiên của độ trễ truyền tin trong mạng theo số lượng nút joint content replication and delivery in wireless networks”, IEEE 
mạng 풏 được phân tích và sử dụng để xây dựng các bài Trans. Inf. Theory, Vol. 59, No. 5, May. 2013, pp. 2760–2776. 
toán tối ưu. Kết quả là, chúng tôi đã giải được các bài toán [8] S.W. Jeon, S.N. Hong, M. Ji, G. Caire, and A. F. Molisch, “Wireless 
tối ưu để tìm ra phương pháp lưu trữ thông tin tại các bộ multihop device-to-device caching networks”, IEEE Trans. Inf. 
nhớ đệm của các nút mạng một cách tối ưu nhất sao cho độ Theory, Vol. 63, No. 3, Mar. 2017, pp. 1662–1676. 
trễ truyền tin là nhỏ nhất. Kết quả thu được sẽ được kiểm [9] G. Alfano, M. Garetto, and E. Leonardi, “Content-centric wireless 
 networks with limited buffers: When mobility hurts”, IEEE/ACM 
tra và xác nhận lại bằng các tính toán trên máy tính. Kết Trans. Netw., Vol. 24, No. 1, Feb. 2016, pp. 299–311. 
quả cho thấy rằng, độ trễ nhận được nhờ sử dụng phương [10] M. Mahdian and E. Yeh, “Throughput–delay Scaling of content-
pháp ngẫu nhiên tốt hơn rất nhiều so với việc sử dụng centric ad hoc and heterogeneous wireless networks”, IEEE/ACM 
phương pháp tuần tự. Trans. Netw., Vol. 25, No. 5, Oct. 2017, pp. 3030–3043. 
 [11] T.A. Do, S.W. Jeon, and W.Y. Shin, Caching in mobile HetNets: A 
 throughput-delay trade-off perspective, in Proc. IEEE Int. Symp. Inf. 
 TÀI LIỆU THAM KHẢO Theory (ISIT), Barcelona, Spain, Jul. 2016, pp. 1247-1251. 
[1] V. Jacobson, D. K. Smetters, J. D. Thornton, M. F. Plass, N. H. [12] M. Ji, G. Caire, and A. F. Molisch, “Fundamental limits of caching 
 Briggs, and R. L. Braynard, “Networking named content”, Commun. in wireless D2D networks”, IEEE Trans. Inf. Theory, Vol. 62, No. 
 ACM, Vol. 55, No. 1, Jan. 2012, pp. 117–124. 2, Feb. 2016, pp. 849–869. 
[2] Cisco visual networking index: Global mobile data traffic forecast [13] V. Bioglio, F. Gabry, and I. Land, Optimizing MDS codes for 
 update, 2015-2020, Cisco Public Information, Feb. 2016. caching at the edge, in Proc. IEEE Global Telecommun. 
[3] P. Gupta and P. R. Kumar, “The capacity of wireless networks”, (GLOBECOM), San Diego, CA, Dec. 2015, pp. 1–6. 
 IEEE Trans. Inf. Theory, Vol. 46, No. 2, Mar. 2000, pp. 388–404. [14] D. E. Knuth, “Big Omicron and big Omega and big Theta”, ACM 
[4] A. Özgür, O. Lévêque, and D. N. C. Tse, “Hierarchical cooperation SIGACT News, Vol. 8, No. 2, Apr.–Jun. 1976, pp. 18–24. 
 (BBT nhận bài: 13/10/2017, hoàn tất thủ tục phản biện: 30/10/2017)