逄愛君臺灣大學:資訊工程學研究所邱柏儒Chiu, Po-JuPo-JuChiu2010-05-182018-07-052010-05-182018-07-052008U0001-2608200811475400http://ntur.lib.ntu.edu.tw//handle/246246/183634近來在點對點網路上的隨按即說服務系統愈受關注，本篇論文提出在點對點網路上隨按即說服務中散佈使用者資訊的問題。透過使用者資訊散佈在點對點網路中不同的方式，隨按即說服務搜尋使用者時所產生的訊息數量也隨之不同。我們證明了要尋找一種使用者資訊的散佈方式使得訊息數量的成本有最小值的問題是NP完全的問題，並且為此問題找出合理的下限。本篇論文提出一種啟發式演算法散佈使用者資訊，有效降低在隨按即說服務中搜尋使用者之成本。透過一系列模擬實驗的結果，我們將展示此啟發式演算法的效能與能力。This paper explores the problem of user information distribution for peer-to-peer (P2P) Push-to-Talk (PTT) service. With different distribution method of user information, the number of messages flow in the network varies. To find a way to distribute user information so that the cost has minimum value will be proved to be NP-Complete and a low bound of this problem will be presented. We design a heuristic mechanism to efficiently reduce the cost of group requests and user registrations. The heuristic mechanism is investigated through our simulations. Series of experiments are conducted to show the capabilities of our heuristic mechanism.口試委員會審定書 #CKNOWLEDGEMENT i要 iiBSTRACT iiiONTENTS ivIST OF FIGURES vIST OF ALGORITHMS vihapter 1 Introduction 1hapter 2 System Design 6.1 System Model 6.2 NP-Completeness 9.3 Our Heuristic Mechanism 12hapter 3 Performance Analysis 16hapter 4 Experimental Results 20hapter 5 Conclusions 25EFERENCES 26application/pdf1013125 bytesapplication/pdfen-US點對點網路隨按即說服務peer-to-peerpush-to-talkthesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/183634/1/ntu-97-R95922089-1.pdf