在臨機人際網路上之以機率方式增進資料之傳輸機制

On Using Probabilistic Forwarding to Improve Data Transfer in Opportunistic People Networks

曾全隆(Cheng-Long Tseng)

指導教授 ： 周承復

國立臺灣大學/電機資訊學院/資訊工程學研究所/碩士(2007年)

https://doi.org/10.6342/NTU.2007.00957

摘要

在臨機人際網路上之以機率方式增進
資料之傳輸機制

中文摘要

隨著無線網路的應用越來越普及，適當地處理網路間因為服務範圍限制所造成的暫時網路中斷的議題日趨重要。透過利用攜帶者本身的移動性讓不同使用者移動裝置的無線裝置有“機會”(opportunities) 可互相傳輸資料或交換訊息的網路，我們稱之為“臨機網路”(opportunistic networks) 或是 “臨機人際網路”(opportunistic people networks)。針對這類網路特別設計資料傳輸演算法是十分重要的。在這篇論文中我們針對兩種在臨機人際網路裡常見的應用類型做研究，包括一般的資料檔案傳輸以及專門針對網頁資料的傳輸做研究。根據 H-EC [12] 的方法，我們提出了一個改良的機率式傳輸演算法 HEC-PF (H-EC with Probabilistic Forwarding)。這個改良的機制改善了 H-EC 的侵略式傳輸(aggressive forwarding)階段，在這個階段新增實作了機率式傳輸，也就是根據所遇到節點的傳輸機率(delivery probability)來決定是否要傳輸訊息。除此之外，為了針對網頁資料傳輸做處理，我們利用階層式多重描述編碼(Layered Multiple Description Coding)的概念，讓使用者可以透過階層式編碼法(Layer Coding)，漸進式地得到較高品質的網頁。透過使用實際網路資料的紀錄(trace)和情境來做模擬實驗，針對我們提出的方法採用延遲(latency)、 傳達率(delivery ratio)和實際收到的網頁品質，根據收到的階層(layer)數和相對接收品質(relative quality )等指標來做評估。結果顯示了我們所提出的 HEC-PF 方法在所有的情境中都比 EC 和 H-EC 方法的傳輸效果來得好，並且在網路狀況極不佳時仍能有相對良好的效能。透過調整 HEC-PF 的參數，我們發現增加最大傳輸距離(maximum forwarding hop distance)和傳輸機率的計算深度(hops count)，可以提高訊息的傳達率。除此之外，透過運用階層式多重描述編碼的概念，讓使用者可以在沒收到完整的網頁資料前，就可以根據目前已收到的階層(layer)作網頁的“預先瀏覽”(preview)。並且隨著收到階層(layer)數的累積，能漸進式地得到較高品質的網頁，進而增進整體網頁瀏覽的用戶體驗(user experience)。我們所提出的方法在強韌性和效率性上都是在臨機人際網路上一個有效的資料傳輸和內容散佈方式。

關鍵字

資料路由 ； 網頁瀏覽 ； 階層式多重描述編碼 ； 臨機網路 ； 耐延遲網路

並列摘要

On Using Probabilistic Forwarding to Improve Data Transfer in Opportunistic People Networks

Abstract

With wireless networking technologies extending into every part of our working and living environments, proper handling of intermittent wireless connectivity and network disruptions is important. We use the term “opportunistic networks”or“opportunistic people networks”to refer to data exchanges based on the connection opportunities that arise whenever mobile devices happen to come into wireless range due to the mobility of their users. Propose proper strategies for dealing with communication in such opportunistic network environments are of significance and remained desirable. In this study, we investigated two applications in opportunistic people networks, namely file transfer and Web surfing applications. We propose the HEC-PF scheme, an enhancement of our previous H-EC [12] scheme for effective data forwarding in opportunistic networks. The enhanced scheme modifies the aggressive forwarding phase of the H-EC scheme by implementing a new Probabilistic Forwarding feature, which decides whether to forward a message to a newly encountered node based on the delivery probability. Moreover, targeting Web surfing applications, we designed LMDC (Layered Multiple Description Coding) based techniques that immensely improve the perceived Web quality for end users. Using simulations as well as realistic network scenarios, we evaluate the proposed schemes in terms of latency, and completion ratio. The results show that the HEC-PF scheme outperforms the EC and H-EC schemes in all test cases, and the performance gain is even more substantial when network connectivity is extremely poor. By varying the parameters of the HEC-PF scheme, we show that its completion ratio improves as the maximum forwarding distance or the hop distance considered when calculating the delivery probability increases. Furthermore, we show that using Layered MDC-based techniques leads to higher user perceived quality, since the end user is allowed to “preview” web content, even before the data has been completely transferred. The effectiveness and robustness of our proposed algorithm and their corresponding content dissemination techniques make them ideal solutions that can go a long way toward effective data dissemination in opportunistic people networks.

並列關鍵字

Data Routing ； Web Surfing ； Layered Multiple Description Coding ； Opportunistic Networks ； Delay Tolerant Networks

參考文獻

[2] Delay tolerant network simulator http://www.dtnrg.org/code/dtnsim.tgz

[3] The disruption tolerant networking project at umass. http://prisms.cs.umass.edu/diesel

[8] J. Burgess, B. Gallagher, D. Jensen, and B. N. Levine. Maxprop: Routing for vehicle-based disruption-tolerant networking. In IEEE Infocom, 2006.

[9] T. Camp, J. Boleng, and V. Davies. A survey of mobility models for ad hoc network research. Wireless Communication and Mobile Computing Journal, 2(5):483–502, 2002

[11] A. Chaintreau, P. Hui, J. Crowcroft, C. Diot, R. Gass, and J. Scott. Impact of human mobility on the design of opportunistic forwarding algorithms. In IEEE Infocom, 2006.