Độ 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

Nội dung text: Độ 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

1. 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 1 ĐỘ 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 ON THE DELAY OF CONTENT-CENTRIC MOBILE MULTIHOP NETWORKS USING FILE SEGMENTATION Đỗ Trung Anh, Đặng Hồi Bắc Học viện Cơng nghệ Bưu chính Viễn thơng; anhdt@ptit.edu.vn Tĩm tắt - Trong bài báo này, chúng tơi nghiên cứu độ trễ trong Abstract - In this paper, we study the delay performance in a content- mạng ad hoc di động hướng nội dung, với các nút mạng di chuyển centric mobile ad hoc network, where each node moves using multihop sử dụng giao thức multihop theo mơ hình bước ngẫu nhiên và yêu according to the random walk mobility model, and requests a content cầu tải các tệp tin từ thư viện chung của mạng. Mỗi tệp tin được object from the library independently at random, according to a Zipf cấu thành bởi K mảnh tin khác nhau và cĩ kích thước bằng nhau, popularity distribution. In our network model, we assume that each sao cho mỗi nút mạng cĩ thể hồn tất quá trình truyền một mảnh content object consists of K distinct segments of equal size so that each tin tới nút mạng chuyển tiếp ở một khe thời gian. Giá trị biến thiên of n mobile nodes is able to completely transmit one segment to one of của độ trễ sẽ được phân tích dựa trên hai phương pháp thu nhận its neighbor cells in one time slot. Using multihop transmission, the mảnh tin tuần tự và ngẫu nhiên. Trong bài báo này, chúng tơi xây delay scaling law is analyzed based on the two following reception dựng và giải bài tốn tối ưu tương ứng, tìm ra phương pháp đệm strategies to determine how K distinct segments are fully delivered to dữ liệu tối ưu sao cho độ trễ là nhỏ nhất, và sử dụng tính tốn của the requesting node in turn to rebuild the desired content object: a máy tính để khẳng định lại tính chính xác của kết quả phân tích. sequential reception and a random reception. Then, we analyze the Kết quả thu được cho thấy độ trễ khi sử dụng phương pháp thu delay of the content-centric wireless networks and to find the optimal nhận mảnh tin ngẫu nhiên tốt hơn đáng kể so với sử dụng phương cache allocation strategies analytically, which minimize the delay. In pháp tuần tự. addition, computer simulations are performed to validate our analytical results. Our main result indicates that the delay obtained from the random reception strategy outperforms the sequential reception case. Từ khĩa - đệm dữ liệu; mạng ad hoc; mạng hướng dữ liệu; Key words - data caching; mobile ad hoc network; content-centric multihop; phân mảnh tệp tin. network; multihop; file segmentation. 1. Đặt vấn đề hướng nội dung tĩnh, sự biến thiên của thơng lượng đã được Hiện nay, kỹ thuật đệm dữ liệu (data caching) [1] với tính tốn tại [7], [8] dựa trên giao thức truyền dẫn multihop thuộc tính giúp thu ngắn khoảng cách giữa các tệp tin với và đạt mức tốt hơn rất nhiều so với thơng lượng được tính người dùng đang nổi lên, là phương pháp hứa hẹn cĩ thể tốn dựa trên giao thức truyền dẫn single-hop. Thêm vào đĩ, giải quyết được các vấn đề phát sinh khi lưu lượng mạng [9] đã nghiên cứu cả thơng lượng và độ trễ của mạng ad hoc internet đang tăng với tốc độ phi mã [2]. Nhờ vào ưu điểm di động hướng nội dung với nhiều cấp di động khác nhau, và của việc lưu trữ các bản sao chép của tệp tin ở khắp nơi chỉ ra rằng sự tăng lên của mức độ di động của nút mạng sẽ trong mạng, kỹ thuật đệm dữ liệu sẽ đĩng vai trị lớn trong dẫn đến hiệu năng mạng thấp hơn. Những hướng phân tích cơng tác duy trì sự ổn định của mạng vơ tuyến tương lai. này đã được mở rộng trên cấu hình mạng hỗn hợp di động Với việc số lượng người dùng thiết bị di động thơng sử dụng nhiều trạm gốc di động, [10-11], trong đĩ sử dụng minh 푛 đang ngày càng tăng lên, độ biến thiên thơng lượng mơ hình fluid [6] với giả thuyết là kích thước tập tin đủ nhỏ mạng khi 푛 tiến tới vơ cùng đã được quan tâm nghiên cứu sao cho thời gian để truyền xong hồn tồn 01 tệp tin trong nhiều đối với mơ hình mạng vơ tuyến cỡ lớn. Trong tài liệu mỗi khe thời gian. Ở hướng nghiên cứu khác, phương pháp [3], Gupta và Kumar đã chỉ ra rằng, đối với mạng ad hoc đệm dữ liệu sử dụng kỹ thuật phân mảnh tệp tin là thiết lập tĩnh với 푛 cặp đích nguồn phân bố đều trong một khu vực rất phổ biến trong cấu hình đệm dữ liệu mã hĩa [12], [13], đơn vị, thơng lượng của mỗi nút mạng nhận được là trong đĩ, mỗi tệp tin được chia ra thành 퐾 mảnh tin được mã 1 hĩa và mỗi người dùng chỉ cần tài một phần của 퐾 mảnh tin Θ ( ) sử dụng giao thức multihop tìm đường đi gần √푛 log 푛 đĩ là đủ để tái xây dựng lại tệp tin gốc. nhất. Bên cạnh việc sử dụng truyền dẫn multihop, cĩ rất Trong bài báo này, chúng tơi quan tâm đến mơ hình nhiều hướng nghiên cứu đã được thực hiện nhằm cải thiện mạng ad hoc di động hướng nội dung sử dụng kỹ thuật phân thơng lượng như sử dụng phương pháp hợp tác phân cấp mảnh tệp tin, trong đĩ, mỗi nút mạng di chuyển theo [4] và tận dụng thuộc tính di động của nút mạng [5], [6]. phương pháp bước ngẫu nhiên và yêu cầu tải tệp tin độc Khác với các nghiên cứu trong mơ hình mạng ad hoc lập và ngẫu nhiên theo phân bố Zipf. Cụ thể hơn, thay vì truyền thống với các cặp đích nguồn đã được giả thuyết là sử dụng mơ hình fluid, chúng tơi xem xét trường hợp kích đã được thiết lập với vị trí khơng đổi, nghiên cứu mơ hình thước tệp tin rất lớn, đến mức khơng thể truyền đi hồn mạng ad hoc vơ tuyến hướng nội dung đang rất được quan tồn trong mỗi khoảng thời gian tương ứng một khe thời tâm chú ý. Ở mơ hình này, các tệp tin được đệm tại bộ nhớ gian trong mạng. Theo đĩ, mỗi tệp tin sẽ được chia thành của rất nhiều các nốt trong mạng, việc tìm ra nút mạng đang 퐾 mảnh tin khác nhau và cĩ kích thước bằng nhau, sao cho lưu trữ tệp tin được yêu cầu gần nhất và sắp xếp thứ tự các mỗi mảnh tin cĩ thể được truyền đi hồn tồn trong một yêu cầu tải tin là việc làm vơ cùng quan trọng và cĩ ảnh khe thời gian, từ nút mạng nguồn tới một trong những nút hưởng lớn tới thơng lượng của mạng. Trong mạng ad hoc mạng lân cận. Chúng tơi trình bày hai phương pháp nhận
2. 2 Đỗ Trung Anh, Đặng Hồi Bắc mảnh tin để tổng hợp là tuần tự và ngẫu nhiên. Dựa trên hai quan tâm sẽ bị thay đổi một cách độc lập và ngẫu nhiên phương pháp này, sự biến thiên theo số lượng nút mạng 푛 theo thời gian do đặc tính của mơ hình di động. Ở bước của độ trễ sẽ được phân tích và tìm ra. Sau đĩ, chúng tơi truyền tin, mỗi nút mạng sẽ tải từng mảnh tin của tệp tin xây dựng và giải bài tốn tối ưu để tìm ra phương pháp lưu quan tâm từ một trong những nút mạng đang lưu giữ trên trữ tối ưu tại bộ nhớ đệm của các nút mạng sao cho độ trễ tồn mạng, bằng phương pháp multihop. Chúng tơi sử dụng là nhỏ nhất. Kết quả thu được sẽ được kiểm tra lại bằng các mơ hình giao thức được áp dụng ở [3] cho mỗi mảnh tin tính tốn trên máy tính. Kết quả cho thấy rằng, độ trễ nhận được truyền thành cơng. Cụ thể, nếu ( , 푣) là ký hiệu của được nhờ sử dụng phương pháp ngẫu nhiên tốt hơn rất khoảng cách Euclidean giữa nốt và 푣, thì quá trình truyền nhiều so với việc sử dụng phương pháp tuần tự. tin giữa nốt và 푣 được cho là thành cơng khi và chỉ khi Trong bài này, chúng tơi sử dụng các ký hiệu ước lượng ( , 푣) ≤ và khơng cĩ bất kỳ một nút mạng nào thực xấp xỉ theo [14] sau đây: i) ( ) = ( ( )) cĩ nghĩa rằng hiện truyền tin trong bán kính (1 + ∆) từ nút mạng 푣 với tồn tại hai số thực và sao cho ( ) ≤ ( ) với mọi và ∆ là các tham số giao thức được thiết lập trước. ( ) > , ii) ( ) = 표( ( )) nghĩa là lim = 0, Để nhận được tệp tin mong muốn, nút mạng cần phải →∞ ( ) tìm kiếm và tải 퐾 mảnh tin khác nhau của tệp tin được phân iii) ( ) = Ω( ( )) nếu ( ) = ( ( )), bố trên tồn mạng. Trong đĩ, độ trễ truyền tin đối với mỗi iv) ( ) = Θ( ( )) nếu ( ) = ( ( )) và mảnh tin được tính là khoảng thời gian đo được từ thời ( ) = Ω( ( )). điểm nút mạng gửi bản tin yêu cầu tới nút mạng đích đang lưu trữ mảnh tin cho tới thời điểm mảnh tin đĩ được truyền 2. Mơ hình mạng thành cơng tới nút mạng yêu cầu. Dựa vào đĩ, chúng tơi sẽ Chúng tơi nghiên cứu mạng ad hoc di động hướng nội tính độ trễ trung bình của mạng đối với tệp tin khác nhau dung, trong đĩ 푛 nút mạng di động di chuyển theo mơ hình và 푛 nút mạng trong mạng. bước ngẫu nhiên trong một ơ vuơng đơn vị. Ở mỗi khe thời 3. Phương pháp thu nhận tệp tin và giao thức định gian, mỗi nút mạng yêu cầu tải một tệp tin nằm trong thư tuyến truyền tin viện cĩ kích thước = Θ(푛훾) của mạ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 hồn tồ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 tồ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.
3. 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, tồ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 푛 tồ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 tồ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 tố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 tố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 tố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. 4 Đỗ Trung Anh, Đặng Hồi Bắc tin trên tồ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 tố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à tố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 ∗ 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 tố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 tốn 1 và Bài tố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 tồ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
5. 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 tốn 2 nhỏ hơn ở Bài tố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. tốn tối ưu. Kết quả là, chúng tơi đã giải được các bài tố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 tố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, hồn tất thủ tục phản biện: 30/10/2017)