臺灣博碩士論文加值系統

隨著科技日新月異，廣告的樣式也愈來愈多，所觀賞者獲得廣告來源也愈來愈多，即使在通勤、搭車或者逛街，有許多機會可以接觸到各種不同的廣告。廣告看板更是傳遞廣告的重要管道，但現有廣告看板更新廣告的速度相當緩慢，播放的廣告往往非觀賞有興趣的，所以有愈來愈多的廣告看板利用網路傳輸動態更新播放的影片，讓觀賞者可以得到更多的資訊；近日更出現可以偵測前方觀賞者的行為、喜好......的資訊，藉由這些資訊動態更新廣告，因而可以對於不同的客群，提供不同的廣告，以達到更有效的推薦效果。
為了達到互動式廣告看板地即時性，便會動態且頻繁的下載廣告，如此伺服器的負擔將會相當重，所需要的頻寬也會相當大。為了可以減少伺服器的上傳頻寬，本論文希望可以利用點對點傳輸技術，有效地降低伺服器的負擔；若直接點對點傳輸技術應用在互動式廣告看板上，則沒有辦法很有效的降低伺服器的上傳頻寬。
本篇論文證明原有的問題為 Set-covering problem 問題(NP-hard)，並提出接近最佳解的演算法，在不影響原有互動性的情形下，減低伺服器的負擔，讓伺服器的最大上傳頻寬有效地下降。
經由最後實驗可看出，本論文的方法相對於不考慮互動式廣告看板特性的點對點傳輸技術有相當顯著的提升；而且隨著廣告看板個數及影片種類增加的情形下，會相當接近理想值，所以本論文的演算法，對於減低互動式廣告看板系統的伺服器上傳頻寬有相當顯著的功用。

With the advancement of technology, the types of advertising become much more diversified, and viewers also can receive this information from much more different devices. Even in commuting, riding, or shopping, there are many opportunities for people to receive different types of advertising. Signage Systems is one of important ways to distribute ads, but they cannot change ads frequently. Therefore, these viewers are usually not interesting the advertising played by signage. Because of these reasons, lots of signage systems transmit ads by network. They can use this method to change ads dynamically. So that viewers can get the information they really care about. More recently there are signage systems which can detect the viewer behavior, interesting, and so on. With this information, signage can dynamically download ads, which can be customized for different groups to achieve more effective recommendation results.
In order to achieve interactive signage systems playing ads in real time, each signage will download the videos frequently. According to the existing framework, the server will have very heavy burden, and its required upload bandwidth will also be considerable. This thesis improves peer-to-peer transmission technology to reduce the server load, but it cannot reduce the server upload bandwidth usefully without improving peer-to-peer transmission technology.
This thesis has the following contribution. First, prove this problem, reforming peer-to-peer to reduce server upload bandwidth, is Set-covering problem(NP-hard). Second, this thesis proposes a greedy approximation algorithm to solve this problem. Without impacting the interactivity, this algorithm can reduce server upload bandwidth effectively.
In the experiment, the proposed method relative to the peer-to-peer transmission technology, which does not take the characteristics of interactive into account, has very significant upgrade. When the number of the signage and the video type increases, greedy approximation algorithm can approach to the ideal bound. So this algorithm proposed by this thesis can significantly reduce the interactive signage systems'' server upload bandwidth.

致謝ii
中文摘要iii
Abstract iv
List of Algorithms x
1 Introduction 1
1.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Thesis Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2 Motivation 4
3 Problem Definition 7
3.1 Over-view . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
3.2 Why does Traditional P2P Approach Not Work? . . . . . . . . . . . . . . 8
3.3 System Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
3.4 Proof . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
4 Algorithm 13
4.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
4.2 AD-clips Scheduling . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
4.3 Bandwidth Allocation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
4.3.1 Channel Resource Index . . . . . . . . . . . . . . . . . . . . . . 16
4.3.2 Peer-to-Peer Grouping . . . . . . . . . . . . . . . . . . . . . . . 16
4.3.3 Locating Source . . . . . . . . . . . . . . . . . . . . . . . . . . 17
4.4 Server Load Balancing . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
5 Performance Evaluation 23
5.1 Impact of Number of Nodes . . . . . . . . . . . . . . . . . . . . . . . . 23
5.2 Impact of Length of Cycle . . . . . . . . . . . . . . . . . . . . . . . . . 25
5.3 Impact of Number of Video Type . . . . . . . . . . . . . . . . . . . . . . 25
6 Conclusion 29
Bibliography 30

[1] aveDia. http://www.avedia.com/.
[2] CAYIN. "http://www.cayintech.com/.
[3] WebDT. http://www.dtresearch.com.tw/.
[4] CoolStreaming/DONet: a data-driven overlay network for peer-to-peer live media
streaming, volume 3, March 2005.
[5] View-Upload Decoupling: A Redesign of Multi-Channel P2P Video Systems, April
2009.
[6] S. Asaduzzaman, Y. Qiao, and G. Bochmann. Cliquestream: An efficient and faultresilient
live streaming network on a clustered peer-to-peer overlay. Peer-to-Peer
Computing, IEEE International Conference on, 0:269–278, 2008.
[7] S. Banerjee, B. Bhattacharjee, and C. Kommareddy. Scalable application layer multicast.
In SIGCOMM ’02: Proceedings of the 2002 conference on Applications, technologies,
architectures, and protocols for computer communications, volume 32,
pages 205–217, New York, NY, USA, October 2002. ACM.
[8] A. R. Bharambe, C. Herley, and V. N. Padmanabhan. Analyzing and improving a
bittorrent network’s performance mechanisms. 2006.
[9] J. Brassil and T. Kim. Large-scale personalized video streaming with program insertion
proxies. Communications Magazine, IEEE, 42(8):104 – 110, aug. 2004.
[10] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms,
chapter 35.3, page 1033. McGraw-Hill Book Company, 2 edition, 2001.
[11] R. Hjelsvold, S. Vdaygiri, and Y. L’eaut’e. Web-based personalization and management
of interactive video. In In Proceedings of the Tenth International World Wide
Web Conference, pages 129–139, 2001.
[12] Z. Ji, I. Ganchev, and M. O’Droma. Efficient collecting, clustering, scheduling, and
indexing schemes for advertisement of services over wireless billboard channels.
In Telecommunications, 2008. ICT 2008. International Conference on, pages 1 –6,
16-19 2008.
[13] Y. Kim, J. Lee, S. Park, and B. Choi. Mobile advertisement system using data push
scheduling based on user preference. In WTS’09: Proceedings of the 2009 conference
on Wireless Telecommunications Symposium, pages 280–284, Piscataway, NJ,
USA, 2009. IEEE Press.
[14] M. Kodialam, T. V. Lakshman, S. Mukherjee, and L. Wang. Online scheduling of
targeted advertisements for iptv. In INFOCOM’10: Proceedings of the 29th conference
on Information communications, pages 1550–1558, Piscataway, NJ, USA,
2010. IEEE Press.
[15] B. Li, Y. Qu, Y. Keung, S. Xie, C. Lin, J. Liu, and X. Zhang. Inside the new coolstreaming:
Principles, measurements and performance implications. In INFOCOM
2008. The 27th Conference on Computer Communications. IEEE, 2008.
[16] T. Locher, R. Meier, S. Schmid, and R. Wattenhofer. Push-to-pull peer-to-peer live
streaming.
[17] Y. Lu, B. Fallica, F. A. Kuipers, R. E. Kooij, and P. V. Mieghem. Assessing the
quality of experience of sopcast. Int. J. Internet Protoc. Technol., 4(1):11–23, 2009.
[18] N. Magharei and A. H. Rasti. Prime: Peer-to-peer receiver-driven mesh-based
streaming. In in Proc. of IEEE INFOCOM 2007, 2007.
[19] J. M‥uller, J. Exeler, M. Buzeck, and A. Kr‥uger. Reflective signs: Digital signs
that adapt to audience attention. In Pervasive ’09: Proceedings of the 7th International
Conference on Pervasive Computing, pages 17–24, Berlin, Heidelberg, 2009.
Springer-Verlag.
[20] V. N. Padmanabhan, H. J. Wang, P. A. Chou, and K. Sripanidkulchai. Distributing
streaming media content using cooperative networking. pages 177–186, 2002.
[21] F. Pianese. Pulse, a flexible p2p live streaming system.
[22] D. A. Tran. Zigzag: An efficient peer-to-peer scheme for media streaming. In In
Proc. of IEEE Infocom, 2003.
[23] F. Wang, Y. Xiong, and J. Liu. mtreebone: A hybrid tree/mesh overlay for
application-layer live video multicast. In in IEEE ICDCS, page 49, 2007.
[24] C.Wu, B. Li, and S. Zhao. Multi-channel live p2p streaming: Refocusing on servers.
In 2008 IEEE INFOCOM - The 27th Conference on Computer Communications,
pages 1355–1363. IEEE, April 2008.
[25] D. J. Xu, S. S. Liao, and Q. Li. Combining empirical experimentation and modeling
techniques: A design research approach for personalized mobile advertising
applications. Decision Support Systems, 44(3):710 – 724, 2008.