在無線行動環境之下，廣播資料如果是透過多個頻道的方式散播，則有機會發生資料碰撞的情形。所謂資料碰撞，就一個廣播排程而言，是指當同一個用戶端所要求的資料，分別出現在不同頻道的同一個時間格而言。由於用戶端受限於單一的無線網路介面，因此在一個時間格裡，用戶端只能選擇一個頻道去聆聽資料，故而用戶端擇一聆聽之後，其他在同一個時間格的用戶端資料，用戶端就必須等待下一個廣播循環才能聆聽，如此將大幅增長用戶端對資料的存取時間，進而降低無線廣播的效率。因此，如何避免或減少在多頻無線廣播下的資料碰撞率，是一個值得研究的課題。本篇論文提出一個方法，將資料碰撞的問題轉換成資料配對(Bipartite matching)的問題，再利用Ford-Fulkerson的演算法，有效的降低資料碰撞的機率。 In this paper, we propose a data matching method to reduce the data collision in a multiple-channel wireless broadcasting system. Data collision occurs when two sets of data within a same query were transmitted to a mobile client on two different channels at the same time slot. Since the mobile client can only access one channel at the same time, data collision forces the mobile client to wait for another broadcast cycle. This leads to an increase of the system delay and slows down the system efficiency. Hence, reducing the data collision in data scheduling can improve the utilization of a wireless broadcasting system. The idea of reducing data collision is to find an efficient method to match data on different channels and re-schedule their position on the broadcast schedule. The proposed method is based on the technique of solving the maximum bipartite matching problem. The maximum bipartite matching problem was derived from the problem of finding the maximum flow in a flow network. The Ford-Fulkerson method, which is a solution to solve the maximum flow problem, was introduced to the proposed method. We have shown that the proposed method can reduce the data collision in two-channel broadcast scheduling as well as in multiple-channel broadcast scheduling.
