臺灣博碩士論文加值系統

近年來隨著智慧型手機的盛行，社群網路的發展已經相當純熟， 因此本論文研究主要應用在社群網路上，並且特別針對使用者行動裝置已經是在近距離的情況， 我們稱作行動D2D社群網路。有關行動D2D社群網路其中一項重要應用，就是共同資訊的匹配， 所謂的共同資訊的匹配，是指使用者都各自攜帶行動裝置，相遇在某個空間(例如:宴會廳)， 並且這群使用者都感興趣彼此之間共同具有的特性，藉由裝置間短距離通訊(稱作D2D)來傳送使用者的資訊並且完成匹配。舉例來說對於一群相互陌生的使用者，可能會想知道彼此間共同的嗜好、朋友或者是過去曾經都去過某些國家，對於學生而言，可能是想知道共同修過的課程。本論文應用在行動D2D社群網路，並假設每位使用者的裝置都可以和其他裝置直接互相通訊下，制定了三種有關資訊匹配的問題，分別是全共有問題、β-共有問題、前γ熱門的問題， 第一個問題主要是延伸之前的相關研究，而後面兩個問題是此篇論文新制定的。我們提出的方法會根據基本布隆過濾器及疊代布隆過濾器，利用布隆過濾器的特性解決本篇資訊
匹配的三個問題， 最後利用實作來驗證我們提出方法達到將低通訊成本的目標。

Recently, mobile social networks (MSNs) have been widely discussed due to the rapid growth of smart mobile devices. This work focuses on mobile D2D social networks (MDSNs), where users in an MSN are physical neighbors. An important social application of MDSNs is common profile matching (CPM), which refers to the scenario where a group of smartphone users meet in a small region (such as a ball room) and these users are interested in identifying the common attributes among them from their personal profiles efficiently via short-range (such as D2D) communications. For example, a group of strangers may want to find common hobbies, friends, or countries they visited before, and a group of students may want to know the common courses they have ever taken. Assuming that users in an MDSN form a fully connected network, we formulate three versions, namely all -common, β-common, and top-γ-popular, of the CPM problem. The first problem is an extension of an earlier work, while the latter two problems are newly defined. We present solutions based on the basic and the iterative Bloom filters. Evaluation results show that our mechanisms are quite communication-efficient.

Chinese Abstract i
English Abstract ii
Acknowledgement iii
Contents iv
List of Figures v
1 Introduction 1
2 Related Works 4
3 Preliminaries 6
4 Common Profile Matching in an MDSN 8
4.1 System Model 8
4.2 Basic Bloom Filter Solution 9
4.3 Iterative Bloom Filter Solution 10
5 Prototyping Results and Performance Evaluation 13
5.1 Application Prototyping 13
5.2 Evaluation Results 15
6 Conclusions 20
Bibliography 24

[1] Android sdk. http://developer.android.com/sdk/index.html.
[2] M. Bakht, M. Trower, and R. H. Kravets. Searchlight: won’t you be my neighbor? In Proc. of ACM International Conference on Mobile Computing and Networking (MobiCom), 2012.
[3] B. H. Bloom. Space/time trade-offs in hash coding with allowable errors. Communications of the ACM, 13(7):422–426, 1970.
[4] E. Bresson, O. Chevassut, D. Pointcheval, and J.-J. Quisquater. Provably authenticated group diffie-hellman key exchange. In Proc. of ACM Conference on Computer and Com-
munications Security (CCS), 2001.
[5] A. Broder and M. Mitzenmacher. Network applications of bloom filters: A survey. Internet Mathematics, 1(4):485–509, 2004.
[6] S. Dharmapurikar, P. Krishnamurthy, and D. E. Taylor. Longest prefix matching using bloom filters. In Proc. of ACM Special Interest Group on Data Communication (SIG-COMM), 2003.
[7] P. Dutta and D. Culler. Practical asynchronous neighbor discovery and rendezvous for mobile sensing applications. In Proc. of ACM Conference on Embedded Networked Sensor Systems (SenSys), 2008.
[8] N. Eagle and A. Pentland. Social serendipity: Mobilizing social software. IEEE Pervasive Computing, 4(2):28–34, 2005.
[9] L. Fan, P. Cao, J. Almeida, and A. Z. Broder. Summary cache: A scalable wide-area web cache sharing protocol. ACM Trans. on Networking, 8(3):281–293, 2000.
[10] Foursquare. http://foursquare.com/.21
[11] A. Gupta, A. Kalra, D. Boston, and C. Borcea. Mobisoc: A middleware for mobile social computing applications. Mobile Networks and Applications, 14(1):35–52, 2009.
[12] P. Jokela, A. Zahemszky, C. E. Rothenberg, S. Arianfar, and P. Nikander. Llipsin: Line speed publish/subscribe inter-networking. In Proc. of ACM Special Interest Group on Data Communication (SIGCOMM), 2009.
[13] A. Kandhalu, K. Lakshmanan, and R. R. Rajkumar. U-connect: a low-latency energyefficient asynchronous neighbor discovery protocol. In Proc. of International Conference
on Information Processing in Sensor Networks (IPSN), 2010.
[14] N. Kayastha, D. Niyato, P. Wang, and E. Hossain. Applications, architectures, and protocol design issues for mobile social networks: A survey. Proceedings of the IEEE,
99(12):2130–2158, 2011.
[15] P. K. Y. Lai, S.-M. Yiu, K. P. Chow, and C. F. Chong. An efficient bloom filter based solution for multiparty private matching. In Proc. of International Conference on Security and Management (SAM), 2006.
[16] M. Li, N. Cao, S. Yu, and W. Lou. Findu: Privacy-preserving personal profile matching in mobile social networks. In Proc. of IEEE Conference on Computer Communications(INFOCOM), 2011.
[17] X. Liang, X. Li, K. Zhang, R. Lu, X. Lin, and X. S. Shen. Fully anonymous profile matching
in mobile social networks. In IEEE Journal on Selected Areas in Communications, 2012.
[18] M. C. Little, S. K. Shrivastava, and N. A. Speirs. Using bloom filters to speed-up name lookup in distributed systems. The Computer Journal, 45(6):645–652, 2002.
[19] S. Liu, L. Kang, L. Chen, and L. Ni. Distributed incomplete pattern matching via a novel weighted bloom filter. In Proc. of International Conference on Distributed Computing Systems (ICDCS), 2012.
[20] Loopt. http://www.loopt.com.
[21] Mobiluck. http://www.mobiluck.com.
[22] M. Motani, V. Srinivasan, and P. S. Nuggehalli. Peoplenet: Engineering A wireless virtual social network. In Proc. of ACM International Conference on Mobile Computing and Networking (MobiCom), 2005.22
[23] C. Peng, G. Shen, Y. Zhang, and S. Lu. Point&;Connect: Intention-based device pairing for mobile phone users. In Proc. of International Conference on Mobile Systems, Applications, and Services (MobiSys), 2009.
[24] A.-K. Pietil¨ainen, E. Oliver, J. LeBrun, G. Varghese, and C. Diot. Mobiclique: Middleware for mobile social networking. In Proc. of ACM Workshop on Online Social Networks(WOSN), 2009.
[25] R. Rivest. The MD5 message-digest algorithm. In IETF RFC (1321), 2003.
[26] M. Steiner, G. Tsudik, and M. Waidner. Diffie-hellman key distribution extended to group communication. In Proc. of ACM Conference on Computer and Communications Security
(CCS), 1996.
[27] J. Teng, B. Zhang, X. Li, X. Bai, and D. Xuan. E-shadow: Lubricating social interaction using mobile phones. In Proc. of International Conference on Distributed Computing Systems (ICDCS), 2011.
[28] M. Terry, E. D. Mynatt, K. Ryall, and D. Leigh. Social Net: Using patterns of physical proximity over time to infer shared interests. In Proc. of ACM SIGCHI Conference on
Human Factors in Computing Systems (CHI), 2002.
[29] Y. Wang, T.-T. Zhang, H.-Z. Li, L.-P. He, and J. Peng. Efficient privacy preserving matchmaking for mobile social networking against malicious users. In Proc. of IEEE In-
ternational Conference on Trust, Security and Privacy in Computing and Communications (TrustCom), 2012.
[30] Wi-fi peer-to-peer (P2P) specification. https://www.wi-fi.org/knowledge-center/ published-specifications.
[31] Android 2.2 platform highlights - portable hotspot. http://developer.android.com/
sdk/android-2.2-highlights.html.
[32] F.-J. Wu, F.-I. Chu, and Y.-C. Tseng. Cyber-physical handshake. In Proc. of ACM Special Interest Group on Data Communication (SIGCOMM), 2011.
[33] Z. Yang, B. Zhang, J. Dai, A. C. Champion, D. Xuan, and D. Li. E-SmallTalker: A distributed mobile system for social networking in physical proximity. In Proc. of Inter-national Conference on Distributed Computing Systems (ICDCS), 2010.23
[34] R. Zhang, Y. Zhang, J. Sun, and G. Yan. Fine-grained private matching for proximitybased mobile social networking. In Proc. of IEEE Conference on Computer Communica-tions (INFOCOM), 2012.
[35] Y. Zhao and J. Wu. B-sub: A practical bloom-filter-based publish-subscribe system for
human networks. In Proc. of International Conference on Distributed Computing Systems(ICDCS), 2010.
[36] H. Zhong, L. Bi, Z. Feng, and N. Li. Research on the design method of mobile social network services. In Proc. of International Conference on Information Management, Innovation Management and Industrial Engineering (ICIII), 2008.