無線網路編碼與壓縮

Abstract

由於通訊技術在這近20年來突飛猛進，無線區域網路(Wireless LANs)的分布密度越來越高，在餐廳、車站或圖書館等公共場合都可以偵測到Wi-Fi的訊號，尤其在人口密集的場所，甚至可以同時偵測到數個無線基地台所發出的訊號。伴隨著無線區域網路以及行動裝置(例如智慧型手機或平板電腦)的高度普及，透過無線區域網路傳遞的資料量越來越多，在這個情況下有效的網路編碼(Network Coding)可以減少傳輸的資料量，促進無線頻寬的利用率。 許多系統利用廣播的特性來提升無線網路的容量及效能，傳統的方法專注於偷聽(overhearing)整個封包，但近年來多數設計者認為偷聽封包的內容會更有效率。針對此方法，我們利用封包內容重複出現的機率，將接收的封包內容建成一棵霍夫曼樹(Huffman tree)，並利用霍夫曼編碼(Huffman code)來編碼封包內容。為了證明我們提出方法的實際性及可行性，我們到許多不同的公共場所蒐集實際的封包資料進行分析，並且將霍夫曼編碼的演算法實作在Linux核心上，利用Linux系統架設的無線路由器來編碼傳遞封包。最後我們根據實做的結果來驗證霍夫曼編碼的可行性，並利用分析資料的結果來驗證實作的正確性。

In the past two decades, communications technologies have been improved. The densiry of wireless Local Area Networks (LANs) becomes higher and higher. Now we can detect Wi-Fi signals in many places, including restaurants, train stations, libraries, especially in densely populated areas. We can even detect several signals from different wireless base stations in the same space. As wireless LANs and mobile devices become much popular, more and more data are transferred through wireless LANs. In many cases, network coding can reduce the amount of data transmitted, and improve channel utilization. Many wireless systems have leveraged the nature of broadcast to improve wireless capacity and performance. While conventional approaches have focused on overhearing entire packets, recent designs have argued that focusing on overheard content may be more effective. For this reason, we utilize the probability of packet repeats to build a Huffman tree. We then use Huffman codes to encode packets. In order to demonstrate the feasibility and practicality of the proposed method, we analyze actual packets collected from different public areas. We also implement the Huffman coding algorithm in Linux kernel and setup a wireless router to encode transmitted packets in Linux system. Finally, we prove the practicality of Huffman encoding by Linux implementation.