使用網路編碼技術之機會型非同步資訊傳播演算法

Abstract

COPE 是由Katti 等人提出的一種分散式、區域性、嘗錯式網路編碼演算法。 在這篇論文裡我們提出一種新的通用性轉送演算法，此演算法適用於無線網路環境。我們稱這種演算法叫Opportunistic Asynchronous Information Dissemination，我們用英文縮寫OASIS表示。在OASIS裡面，我們繼承了COPE的兩項特性，opportunistic listening 以及 opportunistic coding，並且，我們更進一步發展新的技術，我們稱為opportunistic information dissemination。在這個新技術下，我們嘗試混入更多的原始封包到一個編碼封包裡，即使這些混入的封包不是他們1-hop neighbor所需要的。當這些1-hop neighbor收到這些封包時，他們會將這些封包放入他們的資訊儲存槽，這些封包可以提供更多資訊，以利未來的編碼及解碼的用途。除此之外，由於資訊儲存槽有大小的限制，我們觀察到有效管理資訊儲存槽可以更進一步的提升網路的吞吐量。除了仿效COPE週期性的清除資訊儲存槽內的過期封包，我們更進一步利用該封包的參照次數來幫助我們管理資訊儲存槽。為此我們設計新的儲存槽管理演算法。由實驗結果得知，在平均上，OASIS可以達到的網路吞吐量約為傳統單點傳輸的2.15倍，且是COPE的1.22倍。

COPE, proposed by Katti et al. , is a distributed and localized network coding heuristic for wireless networks. In this thesis, we propose a generic forwarding algorithm for wireless networks, called Opportunistic Asynchronous Information Dissemination (OASIS). OASIS not only inherits two features from COPE, opportunistic listening and opportunistic coding, but also introduces a new feature, opportunistic information dissemination, which aggressively codes as many plain packets as possible into a packet even if those packets are not immediately necessary for neighbors. The neighbors who receive these packets would put these packets into information pool. And these packets would help the future coding and decoding process. In addition, we observe that we can further improve the network throughput if we can properly manage the information pool. We not only periodically clear the out-of-date packets as COPE does but also include a new factor, reference times, to help us manage information pool. Simulation results show that the throughput achieved by OASIS is about 2.15 times than Unicast and 1.22 times than COPE on average.