本篇&;#63809;文探討在雙層式網&;#63799;架構下所形成之長鏈&;#63994;&;#63746;載網&;#63799;的資&;#63934;收集與散佈效&;#63841;議題，典型的應用為具有共同騎乘&;#63799;線的自&;#64008;&;#63746;&;#63746;隊網&;#63799;，其上層網&;#63799;介面為3G/3.5G
，下層為IEEE 802.11 Ad-hoc網&;#63799;。在此自&;#64008;&;#63746;&;#63746;隊網&;#63799;架構中，我們著手研究通訊效能最佳化的問題，&;#63860;所有使用者&;#64038;透過3G/3.5G網&;#63799;&;#63745;新與下載資訊時，將對3G/3.5G網&;#63799;造成頻寬嚴重&;#63847;足與傳輸延遲過長的問題，因此，我們設計出自&;#64008;&;#63746;&;#63746;隊成員分群與群組維護的機制，群組成員使用Ad-hoc通訊&;#63789;交換彼此的資&;#63934;，並由一個最佳的成員負責回報群組資訊以&;#63845;Server分享給其他群組，如此一&;#63789;，藉由在上下層網&;#63799;通訊之間的最佳化，可針對3G/3.5G網&;#63799;在頻寬方面作&;#63745;有效的&;#63965;用及減少&;#63847;必要的花費，模擬實驗與數學分析結果顯示我們所設計的高效&;#63841;資&;#63934;收集與散佈機制可大幅&;#64001;地&;#64009;低3G/3.5G傳輸需求與建&;#63991;&;#63898;線&;#63849;。除此之外，我們設計並實作出一套&;#63746;隊通訊與管&;#63972;系統，&;#63965;用Android智慧型手機作為使用者的手持裝置，可以有效&;#63841;地達成&;#63746;隊成員&;#63745;新位置與&;#63994;態資訊的目的。

The bicycling recently has gained a lot of popularity in many applications, such as transporta-tion, recreation, and exercise. In a cycling fleet, bikers may ride in different speeds due to their body strengthes and bike performance. Fleet members using smart phones form two-tier vehicular long-thin networks (VLTNs) along the common cycling path, which consist of a 3G/3.5G high-tier interface and an IEEE 802.11-based low-tier interface. This paper investi-gates the optimization of data collection and distribution in two-tier VLTNs. As all bikers up-load their data and download the fleet information via 3G/3.5G communications, it causes serious problems of insufficient bandwidth and uncertain delay. To reduce the bandwidth usage and transmission delay of 3G/3.5G communications, we propose a framework consisted of a dynamic grouping mechanism and a group maintenance scheme. For data collection, bikers belonging to the same group locally exchange data with each other via ad-hoc communications, and only the gateway needs to report the group data and obtain the fleet information to/from the backend server via 3G/3.5G communications. For data distribution, the gateway uses multi-hop forwarding to broadcast the fleet information to all group members via ad-hoc communications. Through the cooperation between 3G/3.5G and ad-hoc communications, the high-tier bandwidth usage and transmission delay can be minimized. Analytical and simulation results show our framework outperforms existing works, which can significantly reduce the amount of 3G/3.5G data and the number of 3G/3.5G connections. In addition, we implement a Google Android and Maps-based prototype on smart phones for cycling fleet communications.

Abstract in Chinese i
Abstract ii
Acknowledgement iv
Content v
List of Figures vii
1. Introduction 1
2. Problem Definition 4
3. The Proposed Framework 7
3.1 Dynamic Grouping of Bikers 7
3.2 Group Maintenance Scheme 10
3.2.1 Merging and Splitting of Groups 10
3.2.2 Updating of Transmission Orders 12
4. Analysis of 3G/3.5G Cost 13
5. Performance Evaluation 16
6. Prototype Implementation 20
7. Conclusion 25
Bibliography 26
Vita 28

[1] Android Development Tools (ADT) Plugin. http://dl-ssl.google.com/android/eclipse.
[2] Android SDK. http://developer.android.com/sdk/index.html.
[3] Apache HTTP Server. http://www.apache.org/.
[4] C.-C. Hu, H.-K. E. Wu; G.-H. Chen. Stable backbone hosts and stable multicast routes in twotier
mobile ad hoc networks. IEEE Transactions on Vehicular Technology, 58(9):5020–5036, Nov.
2009.
[5] C.-Y. Liang, W.-H. Lin, and B. Chang. Applying Fuzzy Logic Control to an Electric Bicycle. In
First International Conference on Innovative Computing, Information and Control (ICICIC’06),
volume 1, pages 513–516, Aug. 2006.
[6] D. Dubhashi, A. Mei, A. Panconesi, J. Radhakrishnan, and A. Srinivasan. Fast distributed algorithms
for (weakly) connected dominating sets and linear-size skeletons. Journal of Computer and
System Science, 71(4):467–479, Nov. 2005.
[7] E. M. Belding-Royer and C. E. Perkins. Transmission range effects on AODV multicast communication.
ACM/Kluwer Mobile Networking and Applications, 7(6):455–470, Dec. 2002.
[8] Eclipse IDE. http://www.eclipse.org/downloads/.
[9] F. Dai and J. Wu. An extended localized algorithm for connected dominating set formation in ad
hoc wireless networks. IEEE Transactions on Parallel and Distributed System, 15(10):908–920,
Oct. 2004.
[10] Google Maps APIs. http://code.google.com/apis/maps/.
[11] I. Stojmenovic, M. Seddigh, and J. Zunic. Dominating sets and neighbors elimination based broadcasting
algorithms in wireless networks. IEEE Transactions on Parallel and Distributed System,
13(1):14–25, Jan. 2002.
[12] J. J. Garcia-Luna-Aceves and E. L. Madruga. The core-assisted mesh protocol. IEEE Journal on
Selected Areas in Communications, 17(8):1380–1394, Aug. 1999.
[13] J. Xie, R. R. Talpade, A. Mcauley, and M. Liu. AMRoute: Ad hoc multicast routing protocol.
ACM/Kluwer Mobile Networking and Applications, 7(6):429–439, Dec. 2002.
[14] Java Development Kit (JDK). http://java.sun.com.
[15] K. Chan and K. Nahrstedt. Effect location-guided tree construction algorithms for small group
multicast in MANETs. In Proceeding of 21st International Annual Joint Conference of IEEE
Computer and Communications Society (INFOCOM’02), pages 1180–1189, June 2002.
[16] L. Jia, R. Rajaraman, and T. Suel. An efficient distributed algorithm for constructing small dominating
sets. Distributed Computing, 15(4):193–205, Dec. 2002.
[17] M. S. Corson and S. G. Batsell. A reservation-based multicast (RBM) routing protocol for mobile
networks: Initial route construction phase. ACM/Baltzer Wireless Networks, 1(4):427–450, Dec.
[18] M. T. Thai, F.Wang, D. Liu, S. Zhu, and D. Z. Du. Connected dominating sets in wireless networks
with different transmission ranges. IEEE Transactions on Mobile Computing, 6(7):721–730, July
2007.
[19] M. T. Thai, R. Tiwari, and D. Z. Du. On construction of virtual backbone in wireless ad hoc
networks with unidirectional links. IEEE Transactions on Mobile Computing, 7(9):1098–1108,
Sep. 2008.
[20] P.-J.Wan, K. M. Alzoubi, and O. Frieder. Distributed construction of connected dominating sets in
wireless ad hoc networks. ACM/Kluwer Mobile Networking and Applications, 9(2):141–149, Apr.
2004.
[21] PHP: Hypertext Preprocessor. http://php.net/index.php.
[22] PostgreSQL Object-Relational Database Management System (ORDBMS).
http://www.postgresql.org/.
[23] QualNet. http://www.scalable-networks.com/products/qualnet/.
[24] R. Luo and Y. Shen. The Design and Implementation of Public Bike Information System Based on
Google Maps. In International Conference on Environmental Science and Information Application
Technology (ESIAT’09), volume 2, pages 156–159, July 2009.
[25] S. B. Eisenman, E. Miluzzo, N. D. Lane, R. A. Peterson, G.-S. Ahn, and A. T. Campbell. The
BikeNet Mobile Sensing System for Cyclist Experience Mapping. In Fifth ACM Conference on
Embedded Networked Sensor Systems (SenSys’07), pages 87–101, Nov. 2007.
[26] S. J. Lee and M. Gerla. On-demand multicast routing protocol in multihop wireless mobile networks.
ACM/Kluwer Mobile Networking and Applications, 7(6):441–453, Dec. 2002.
[27] S. K. S. Gupta and P. K. Srimani. Cored-based tree with forwarding regions (CBT-FR): A protocol
for reliable multicasting in mobile ad hoc networks. Journal of Parallel and Distributed Computing,61(9):1249–1277, Sep. 2001.