以最佳資訊分散法用於容錯性之平行通訊

Abstract

隨著電腦網路及分散式系統的快速發展,對於資訊傳遞的可靠性及安全 性的要求與日俱增,尤其是在無線通訊中,資訊錯誤率比有線傳輸高,對於 可靠性的要求更高.資訊分散法可以用於加速在低傳輸速度網路的傳輸,並 可減少傳輸資料傳送失敗的情況.所謂的資訊分散方法,是傳送節點將一個 訊息分成n個資料小塊,使得接受端從不同頻道上收到任何m個資料小塊,就 足以重構出此訊息.用資訊分散法可以容忍n-m條傳送頻道傳送失敗. 由 於資訊分散法中所傳送的資料小塊(packet)大小,會隨著資訊分散法的m值 而變化.整個資訊分散方法的效果,會受到m值,n值及每個資料小塊傳送成 功率的影響,而單個資料小塊的傳送成功機率又會因資料的大小而改,即因 m而所不同.在本論文中,我們將討論資訊分散法用於無線通訊的情況.我們 將對不同的情況,提出不同的演算法,用來找出最佳的n及m值的組合.其中, 在滿足資料膨脹上限的情況下,我們提出的方法可以將可能的最佳解個數 從O(N^2)降到O(N),其中N為頻道的總數. With the rapid development of computer networks and distributed systems, the need for support of high spped, reliable and secure communication increases, espacially in wireless communications. In order to speed up communications in low rate wirelss communication and tolerate channel failure between two communication parties, information dispersal scheme (IDS) can be used. In an(m,n) IDS, the sender transforms a message M into n pieces, such that any m pieces collected by the receiver suffice for reconstructing M. The (m,n) IDScan be used to tolerate up to n-m path (channel) failures. In (m,n) IDS, the packet size depends on m, and the success probability of data transmission is influenced by the data packet size. Thus the communicationreliability of (m,n) IDS also depends on the value of m. In the thesis, weconstruct a performance model of the (m,n) IDS used in wireless communications.And we propose an algorithm to choose the optimal set of (m,n) with the highestreliability. Our algorithm reduces the complexity of finding the optimal set of(m,n) from O(N^2) to O(N), where N is the maximum number of available subchannels.