延遲容忍網路環境下之資料散播

目前有許多應用服務，希望藉由行動裝置，廣播廣告訊息或影音內容，使資訊可以盡快散播。行動裝置僅在處於相近之地理位置時才有連線機會，因此，發送端和接收端之間不存在確切之繞路方式，需要藉由使用者之間之接觸增加傳遞機會。近期已有許多研究探討如何在有限資源之下選擇適當之中繼點，以達到最大化資料傳輸率。在本研究中，我們分析使用者之接觸關聯，估算每位使用者之貢獻度(contribution)，亦即其可協助散佈之使用者數量。此外，由於使用者接觸時間有限，當中繼點轉傳資料時，會利用分群之歷史紀錄，預測其與鄰近點之相遇期間(contact duration)。藉由貢獻度以及相遇時間之預測，決定鄰近點之轉傳順序，目標是在有效時間內，安排傳輸排程，最大化接收訊息之使用者數量，提升數位內容之散播效率。我們開發了解決此問題的背向式歸納演算法：DIFFUSE，可在近似多項式時間內，解決最佳化之排程問題。並且提出了估算使用者之貢獻度與使用者接觸時間之方式，其結果十分接近真實狀況。利用真實記錄模擬的結果，也可看出開發的演算法相較於過去的方法，效能提升許多，甚至接近最佳狀況。

關鍵字

延遲容忍網路；資料散播；使用者貢獻；接觸時間；背向式歸納演算法

並列摘要

Currently, many applications use mobile devices to propagate advertisements or multimedia. Mobile devices can connect to each other only when they are close enough. Therefore, there is no exact routing approach between the sender and the receiver. The way to increase the transmission opportunity is to contact each user more frequently. Recently, there are many researches already studied how to select an appropriate relay node with the limited resources to maximize the content transmission rate. In this paper, we analyze the contact relationship of users to estimate the contribution ( i.e., the number of useful contacts that could encounter after becoming a forwarder). Besides, different contacts may have various contact durations. Because the contact duration between users is restricted, we predict the contact duration between one and its neighbors by cluster-based history record when transmitting data through the relay node. We consider both who can download the copy based on the contribution value and when to relay the copy according to the contact duration. The goal of this research is to solve the forwarding problem and to develop a backward induction algorithm, called DIFFUSE. We also propose the probability-based metrics to predict contribution and contact duration of each contact, which is close to the accurate situation. The simulation which uses the real trace shows that DIFFUSE can improve lots of performance compared to the prior schemes, and even closer to the oracle solution.

並列關鍵字

Delay tolerant networks(DTNs) ； Content diffusion ； user contribution ； contact duration ； backward induction algorithm

參考文獻

[2] A. Balasubramanian, B. Levine, and A. Venkataramani. DTN Routing as a Resource Allocation Problem. In ACM SIGCOMM, 2007.

[3] M. M. Bin Tariq, M. Ammar, and E. Zegura. Message ferry route design for sparse ad hoc networks with mobile nodes. In ACM MobiHoc, pages 37–48, 2006.

[4] J. Burgess, B. Gallagher, D. Jensen, and B. N. Levine. MaxProp: Routing for Vehicle-Based Disruption-Tolerant Networks. In IEEE INFOCOM, 2006.

[6] E. M. Daly and M. Haahr. Social Network Analysis for Routing in Disconnected Delay-Tolerant MANETs. In ACM MobiHoc, 2007.

[8] N. Eagle and A. Pentland. Reality Mining: Sensing Complex Social Systems. Personal and Ubiquitous Computing, 10(4):268, 2006.

國際替代計量

延遲容忍網路環境下之資料散播

全文下載

主題瀏覽